1 //===- SymbolTable.cpp ----------------------------------------------------===//
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Symbol table is a bag of all known symbols. We put all symbols of
11 // all input files to the symbol table. The symbol table is basically
12 // a hash table with the logic to resolve symbol name conflicts using
15 //===----------------------------------------------------------------------===//
17 #include "SymbolTable.h"
20 #include "LinkerScript.h"
22 #include "SymbolListFile.h"
24 #include "llvm/Bitcode/ReaderWriter.h"
25 #include "llvm/Support/StringSaver.h"
28 using namespace llvm::object;
29 using namespace llvm::ELF;
32 using namespace lld::elf;
34 // All input object files must be for the same architecture
35 // (e.g. it does not make sense to link x86 object files with
36 // MIPS object files.) This function checks for that error.
37 template <class ELFT> static bool isCompatible(InputFile *F) {
38 if (!isa<ELFFileBase<ELFT>>(F) && !isa<BitcodeFile>(F))
40 if (F->EKind == Config->EKind && F->EMachine == Config->EMachine)
42 StringRef A = F->getName();
43 StringRef B = Config->Emulation;
45 B = Config->FirstElf->getName();
46 error(A + " is incompatible with " + B);
50 // Add symbols in File to the symbol table.
52 void SymbolTable<ELFT>::addFile(std::unique_ptr<InputFile> File) {
53 InputFile *FileP = File.get();
54 if (!isCompatible<ELFT>(FileP))
58 if (auto *F = dyn_cast<ArchiveFile>(FileP)) {
59 ArchiveFiles.emplace_back(cast<ArchiveFile>(File.release()));
65 if (auto *F = dyn_cast<LazyObjectFile>(FileP)) {
66 LazyObjectFiles.emplace_back(cast<LazyObjectFile>(File.release()));
72 outs() << getFilename(FileP) << "\n";
75 if (auto *F = dyn_cast<SharedFile<ELFT>>(FileP)) {
76 // DSOs are uniquified not by filename but by soname.
78 if (!SoNames.insert(F->getSoName()).second)
81 SharedFiles.emplace_back(cast<SharedFile<ELFT>>(File.release()));
87 if (auto *F = dyn_cast<BitcodeFile>(FileP)) {
88 BitcodeFiles.emplace_back(cast<BitcodeFile>(File.release()));
89 F->parse<ELFT>(ComdatGroups);
93 // Regular object file
94 auto *F = cast<ObjectFile<ELFT>>(FileP);
95 ObjectFiles.emplace_back(cast<ObjectFile<ELFT>>(File.release()));
96 F->parse(ComdatGroups);
99 // This function is where all the optimizations of link-time
100 // optimization happens. When LTO is in use, some input files are
101 // not in native object file format but in the LLVM bitcode format.
102 // This function compiles bitcode files into a few big native files
103 // using LLVM functions and replaces bitcode symbols with the results.
104 // Because all bitcode files that consist of a program are passed
105 // to the compiler at once, it can do whole-program optimization.
106 template <class ELFT> void SymbolTable<ELFT>::addCombinedLtoObject() {
107 if (BitcodeFiles.empty())
110 // Compile bitcode files.
111 Lto.reset(new BitcodeCompiler);
112 for (const std::unique_ptr<BitcodeFile> &F : BitcodeFiles)
114 std::vector<std::unique_ptr<InputFile>> IFs = Lto->compile();
116 // Replace bitcode symbols.
117 for (auto &IF : IFs) {
118 ObjectFile<ELFT> *Obj = cast<ObjectFile<ELFT>>(IF.release());
120 DenseSet<StringRef> DummyGroups;
121 Obj->parse(DummyGroups);
122 ObjectFiles.emplace_back(Obj);
126 template <class ELFT>
127 DefinedRegular<ELFT> *SymbolTable<ELFT>::addAbsolute(StringRef Name,
128 uint8_t Visibility) {
129 return cast<DefinedRegular<ELFT>>(
130 addRegular(Name, STB_GLOBAL, Visibility)->body());
133 // Add Name as an "ignored" symbol. An ignored symbol is a regular
134 // linker-synthesized defined symbol, but is only defined if needed.
135 template <class ELFT>
136 DefinedRegular<ELFT> *SymbolTable<ELFT>::addIgnored(StringRef Name,
137 uint8_t Visibility) {
140 return addAbsolute(Name, Visibility);
143 // Set a flag for --trace-symbol so that we can print out a log message
144 // if a new symbol with the same name is inserted into the symbol table.
145 template <class ELFT> void SymbolTable<ELFT>::trace(StringRef Name) {
146 Symtab.insert({Name, {-1, true}});
149 // Rename SYM as __wrap_SYM. The original symbol is preserved as __real_SYM.
150 // Used to implement --wrap.
151 template <class ELFT> void SymbolTable<ELFT>::wrap(StringRef Name) {
152 SymbolBody *B = find(Name);
155 StringSaver Saver(Alloc);
156 Symbol *Sym = B->symbol();
157 Symbol *Real = addUndefined(Saver.save("__real_" + Name));
158 Symbol *Wrap = addUndefined(Saver.save("__wrap_" + Name));
159 // We rename symbols by replacing the old symbol's SymbolBody with the new
160 // symbol's SymbolBody. This causes all SymbolBody pointers referring to the
161 // old symbol to instead refer to the new symbol.
162 memcpy(Real->Body.buffer, Sym->Body.buffer, sizeof(Sym->Body));
163 memcpy(Sym->Body.buffer, Wrap->Body.buffer, sizeof(Wrap->Body));
166 static uint8_t getMinVisibility(uint8_t VA, uint8_t VB) {
167 if (VA == STV_DEFAULT)
169 if (VB == STV_DEFAULT)
171 return std::min(VA, VB);
174 // Find an existing symbol or create and insert a new one.
175 template <class ELFT>
176 std::pair<Symbol *, bool> SymbolTable<ELFT>::insert(StringRef Name) {
177 auto P = Symtab.insert({Name, {(int)SymVector.size(), false}});
178 SymIndex &V = P.first->second;
179 bool IsNew = P.second;
183 V = {(int)SymVector.size(), true};
188 Sym = new (Alloc) Symbol;
189 Sym->Binding = STB_WEAK;
190 Sym->Visibility = STV_DEFAULT;
191 Sym->IsUsedInRegularObj = false;
192 Sym->ExportDynamic = false;
193 Sym->VersionId = Config->DefaultSymbolVersion;
194 Sym->Traced = V.Traced;
195 SymVector.push_back(Sym);
197 Sym = SymVector[V.Idx];
202 // Find an existing symbol or create and insert a new one, then apply the given
204 template <class ELFT>
205 std::pair<Symbol *, bool>
206 SymbolTable<ELFT>::insert(StringRef Name, uint8_t Type, uint8_t Visibility,
207 bool CanOmitFromDynSym, bool IsUsedInRegularObj,
211 std::tie(S, WasInserted) = insert(Name);
213 // Merge in the new symbol's visibility.
214 S->Visibility = getMinVisibility(S->Visibility, Visibility);
215 if (!CanOmitFromDynSym && (Config->Shared || Config->ExportDynamic))
216 S->ExportDynamic = true;
217 if (IsUsedInRegularObj)
218 S->IsUsedInRegularObj = true;
219 if (!WasInserted && S->body()->Type != SymbolBody::UnknownType &&
220 ((Type == STT_TLS) != S->body()->isTls()))
221 error("TLS attribute mismatch for symbol: " +
222 conflictMsg(S->body(), File));
224 return {S, WasInserted};
227 // Construct a string in the form of "Sym in File1 and File2".
228 // Used to construct an error message.
229 template <typename ELFT>
230 std::string SymbolTable<ELFT>::conflictMsg(SymbolBody *Existing,
231 InputFile *NewFile) {
232 std::string Sym = Existing->getName();
233 if (Config->Demangle)
235 return Sym + " in " + getFilename(Existing->File) + " and " +
236 getFilename(NewFile);
239 template <class ELFT> Symbol *SymbolTable<ELFT>::addUndefined(StringRef Name) {
240 return addUndefined(Name, STB_GLOBAL, STV_DEFAULT, /*Type*/ 0,
241 /*CanOmitFromDynSym*/ false, /*File*/ nullptr);
244 template <class ELFT>
245 Symbol *SymbolTable<ELFT>::addUndefined(StringRef Name, uint8_t Binding,
246 uint8_t StOther, uint8_t Type,
247 bool CanOmitFromDynSym,
251 std::tie(S, WasInserted) =
252 insert(Name, Type, StOther & 3, CanOmitFromDynSym,
253 /*IsUsedInRegularObj*/ !File || !isa<BitcodeFile>(File), File);
255 S->Binding = Binding;
256 replaceBody<Undefined>(S, Name, StOther, Type, File);
259 if (Binding != STB_WEAK) {
260 if (S->body()->isShared() || S->body()->isLazy())
261 S->Binding = Binding;
262 if (auto *SS = dyn_cast<SharedSymbol<ELFT>>(S->body()))
263 SS->file()->IsUsed = true;
265 if (auto *L = dyn_cast<Lazy>(S->body())) {
266 // An undefined weak will not fetch archive members, but we have to remember
267 // its type. See also comment in addLazyArchive.
270 else if (auto F = L->fetch())
271 addFile(std::move(F));
276 // We have a new defined symbol with the specified binding. Return 1 if the new
277 // symbol should win, -1 if the new symbol should lose, or 0 if both symbols are
278 // strong defined symbols.
279 static int compareDefined(Symbol *S, bool WasInserted, uint8_t Binding) {
282 SymbolBody *Body = S->body();
283 if (Body->isLazy() || Body->isUndefined() || Body->isShared())
285 if (Binding == STB_WEAK)
292 // We have a new non-common defined symbol with the specified binding. Return 1
293 // if the new symbol should win, -1 if the new symbol should lose, or 0 if there
294 // is a conflict. If the new symbol wins, also update the binding.
295 static int compareDefinedNonCommon(Symbol *S, bool WasInserted, uint8_t Binding) {
296 if (int Cmp = compareDefined(S, WasInserted, Binding)) {
298 S->Binding = Binding;
301 if (isa<DefinedCommon>(S->body())) {
302 // Non-common symbols take precedence over common symbols.
303 if (Config->WarnCommon)
304 warning("common " + S->body()->getName() + " is overridden");
310 template <class ELFT>
311 Symbol *SymbolTable<ELFT>::addCommon(StringRef N, uint64_t Size,
312 uint64_t Alignment, uint8_t Binding,
313 uint8_t StOther, uint8_t Type,
317 std::tie(S, WasInserted) =
318 insert(N, Type, StOther & 3, /*CanOmitFromDynSym*/ false,
319 /*IsUsedInRegularObj*/ true, File);
320 int Cmp = compareDefined(S, WasInserted, Binding);
322 S->Binding = Binding;
323 replaceBody<DefinedCommon>(S, N, Size, Alignment, StOther, Type, File);
324 } else if (Cmp == 0) {
325 auto *C = dyn_cast<DefinedCommon>(S->body());
327 // Non-common symbols take precedence over common symbols.
328 if (Config->WarnCommon)
329 warning("common " + S->body()->getName() + " is overridden");
333 if (Config->WarnCommon)
334 warning("multiple common of " + S->body()->getName());
336 C->Size = std::max(C->Size, Size);
337 C->Alignment = std::max(C->Alignment, Alignment);
342 template <class ELFT>
343 void SymbolTable<ELFT>::reportDuplicate(SymbolBody *Existing,
344 InputFile *NewFile) {
345 std::string Msg = "duplicate symbol: " + conflictMsg(Existing, NewFile);
346 if (Config->AllowMultipleDefinition)
352 template <typename ELFT>
353 Symbol *SymbolTable<ELFT>::addRegular(StringRef Name, const Elf_Sym &Sym,
354 InputSectionBase<ELFT> *Section) {
357 std::tie(S, WasInserted) =
358 insert(Name, Sym.getType(), Sym.getVisibility(),
359 /*CanOmitFromDynSym*/ false, /*IsUsedInRegularObj*/ true,
360 Section ? Section->getFile() : nullptr);
361 int Cmp = compareDefinedNonCommon(S, WasInserted, Sym.getBinding());
363 replaceBody<DefinedRegular<ELFT>>(S, Name, Sym, Section);
365 reportDuplicate(S->body(), Section->getFile());
369 template <typename ELFT>
370 Symbol *SymbolTable<ELFT>::addRegular(StringRef Name, uint8_t Binding,
374 std::tie(S, WasInserted) =
375 insert(Name, STT_NOTYPE, StOther & 3, /*CanOmitFromDynSym*/ false,
376 /*IsUsedInRegularObj*/ true, nullptr);
377 int Cmp = compareDefinedNonCommon(S, WasInserted, Binding);
379 replaceBody<DefinedRegular<ELFT>>(S, Name, StOther);
381 reportDuplicate(S->body(), nullptr);
385 template <typename ELFT>
386 Symbol *SymbolTable<ELFT>::addSynthetic(StringRef N,
387 OutputSectionBase<ELFT> *Section,
391 std::tie(S, WasInserted) =
392 insert(N, STT_NOTYPE, STV_HIDDEN, /*CanOmitFromDynSym*/ false,
393 /*IsUsedInRegularObj*/ true, nullptr);
394 int Cmp = compareDefinedNonCommon(S, WasInserted, STB_GLOBAL);
396 replaceBody<DefinedSynthetic<ELFT>>(S, N, Value, Section);
398 reportDuplicate(S->body(), nullptr);
402 template <typename ELFT>
403 void SymbolTable<ELFT>::addShared(SharedFile<ELFT> *F, StringRef Name,
405 const typename ELFT::Verdef *Verdef) {
406 // DSO symbols do not affect visibility in the output, so we pass STV_DEFAULT
407 // as the visibility, which will leave the visibility in the symbol table
411 std::tie(S, WasInserted) =
412 insert(Name, Sym.getType(), STV_DEFAULT, /*CanOmitFromDynSym*/ true,
413 /*IsUsedInRegularObj*/ false, F);
414 // Make sure we preempt DSO symbols with default visibility.
415 if (Sym.getVisibility() == STV_DEFAULT)
416 S->ExportDynamic = true;
417 if (WasInserted || isa<Undefined>(S->body())) {
418 replaceBody<SharedSymbol<ELFT>>(S, F, Name, Sym, Verdef);
424 template <class ELFT>
425 Symbol *SymbolTable<ELFT>::addBitcode(StringRef Name, bool IsWeak,
426 uint8_t StOther, uint8_t Type,
427 bool CanOmitFromDynSym, BitcodeFile *F) {
430 std::tie(S, WasInserted) = insert(Name, Type, StOther & 3, CanOmitFromDynSym,
431 /*IsUsedInRegularObj*/ false, F);
433 compareDefinedNonCommon(S, WasInserted, IsWeak ? STB_WEAK : STB_GLOBAL);
435 replaceBody<DefinedBitcode>(S, Name, StOther, Type, F);
437 reportDuplicate(S->body(), F);
441 template <class ELFT> SymbolBody *SymbolTable<ELFT>::find(StringRef Name) {
442 auto It = Symtab.find(Name);
443 if (It == Symtab.end())
445 SymIndex V = It->second;
448 return SymVector[V.Idx]->body();
451 // Returns a list of defined symbols that match with a given glob pattern.
452 template <class ELFT>
453 std::vector<SymbolBody *> SymbolTable<ELFT>::findAll(StringRef Pattern) {
454 std::vector<SymbolBody *> Res;
455 for (Symbol *Sym : SymVector) {
456 SymbolBody *B = Sym->body();
457 if (!B->isUndefined() && globMatch(Pattern, B->getName()))
463 template <class ELFT>
464 void SymbolTable<ELFT>::addLazyArchive(ArchiveFile *F,
465 const object::Archive::Symbol Sym) {
468 std::tie(S, WasInserted) = insert(Sym.getName());
470 replaceBody<LazyArchive>(S, *F, Sym, SymbolBody::UnknownType);
473 if (!S->body()->isUndefined())
476 // Weak undefined symbols should not fetch members from archives. If we were
477 // to keep old symbol we would not know that an archive member was available
478 // if a strong undefined symbol shows up afterwards in the link. If a strong
479 // undefined symbol never shows up, this lazy symbol will get to the end of
480 // the link and must be treated as the weak undefined one. We already marked
481 // this symbol as used when we added it to the symbol table, but we also need
482 // to preserve its type. FIXME: Move the Type field to Symbol.
484 replaceBody<LazyArchive>(S, *F, Sym, S->body()->Type);
487 MemoryBufferRef MBRef = F->getMember(&Sym);
488 if (!MBRef.getBuffer().empty())
489 addFile(createObjectFile(MBRef, F->getName()));
492 template <class ELFT>
493 void SymbolTable<ELFT>::addLazyObject(StringRef Name, LazyObjectFile &Obj) {
496 std::tie(S, WasInserted) = insert(Name);
498 replaceBody<LazyObject>(S, Name, Obj, SymbolBody::UnknownType);
501 if (!S->body()->isUndefined())
504 // See comment for addLazyArchive above.
506 replaceBody<LazyObject>(S, Name, Obj, S->body()->Type);
508 MemoryBufferRef MBRef = Obj.getBuffer();
509 if (!MBRef.getBuffer().empty())
510 addFile(createObjectFile(MBRef));
514 // Process undefined (-u) flags by loading lazy symbols named by those flags.
515 template <class ELFT> void SymbolTable<ELFT>::scanUndefinedFlags() {
516 for (StringRef S : Config->Undefined)
517 if (auto *L = dyn_cast_or_null<Lazy>(find(S)))
518 if (std::unique_ptr<InputFile> File = L->fetch())
519 addFile(std::move(File));
522 // This function takes care of the case in which shared libraries depend on
523 // the user program (not the other way, which is usual). Shared libraries
524 // may have undefined symbols, expecting that the user program provides
525 // the definitions for them. An example is BSD's __progname symbol.
526 // We need to put such symbols to the main program's .dynsym so that
527 // shared libraries can find them.
528 // Except this, we ignore undefined symbols in DSOs.
529 template <class ELFT> void SymbolTable<ELFT>::scanShlibUndefined() {
530 for (std::unique_ptr<SharedFile<ELFT>> &File : SharedFiles)
531 for (StringRef U : File->getUndefinedSymbols())
532 if (SymbolBody *Sym = find(U))
533 if (Sym->isDefined())
534 Sym->symbol()->ExportDynamic = true;
537 // This function process the dynamic list option by marking all the symbols
538 // to be exported in the dynamic table.
539 template <class ELFT> void SymbolTable<ELFT>::scanDynamicList() {
540 for (StringRef S : Config->DynamicList)
541 if (SymbolBody *B = find(S))
542 B->symbol()->ExportDynamic = true;
545 static bool hasWildcard(StringRef S) {
546 return S.find_first_of("?*") != StringRef::npos;
549 static void setVersionId(SymbolBody *Body, StringRef VersionName,
550 StringRef Name, uint16_t Version) {
551 if (!Body || Body->isUndefined()) {
552 if (Config->NoUndefinedVersion)
553 error("version script assignment of " + VersionName + " to symbol " +
554 Name + " failed: symbol not defined");
558 Symbol *Sym = Body->symbol();
559 if (Sym->VersionId != Config->DefaultSymbolVersion)
560 warning("duplicate symbol " + Name + " in version script");
561 Sym->VersionId = Version;
564 template <class ELFT>
565 std::map<std::string, SymbolBody *> SymbolTable<ELFT>::getDemangledSyms() {
566 std::map<std::string, SymbolBody *> Result;
567 for (Symbol *Sym : SymVector) {
568 SymbolBody *B = Sym->body();
569 Result[demangle(B->getName())] = B;
574 static bool hasExternCpp() {
575 for (VersionDefinition &V : Config->VersionDefinitions)
576 for (SymbolVersion Sym : V.Globals)
582 // This function processes the --version-script option by marking all global
583 // symbols with the VersionScriptGlobal flag, which acts as a filter on the
584 // dynamic symbol table.
585 template <class ELFT> void SymbolTable<ELFT>::scanVersionScript() {
586 // If version script does not contain versions declarations,
587 // we just should mark global symbols.
588 if (!Config->VersionScriptGlobals.empty()) {
589 for (SymbolVersion &Sym : Config->VersionScriptGlobals)
590 if (SymbolBody *B = find(Sym.Name))
591 B->symbol()->VersionId = VER_NDX_GLOBAL;
595 if (Config->VersionDefinitions.empty())
598 // If we have symbols version declarations, we should
599 // assign version references for each symbol.
600 // Current rules are:
601 // * If there is an exact match for the mangled name or we have extern C++
602 // exact match, then we use it.
603 // * Otherwise, we look through the wildcard patterns. We look through the
604 // version tags in reverse order. We use the first match we find (the last
605 // matching version tag in the file).
606 // Handle exact matches and build a map of demangled externs for
607 // quick search during next step.
608 std::map<std::string, SymbolBody *> Demangled;
610 Demangled = getDemangledSyms();
612 for (VersionDefinition &V : Config->VersionDefinitions) {
613 for (SymbolVersion Sym : V.Globals) {
614 if (hasWildcard(Sym.Name))
616 SymbolBody *B = Sym.IsExternCpp ? Demangled[Sym.Name] : find(Sym.Name);
617 setVersionId(B, V.Name, Sym.Name, V.Id);
622 for (size_t I = Config->VersionDefinitions.size() - 1; I != (size_t)-1; --I) {
623 VersionDefinition &V = Config->VersionDefinitions[I];
624 for (SymbolVersion &Sym : V.Globals)
625 if (hasWildcard(Sym.Name))
626 for (SymbolBody *B : findAll(Sym.Name))
627 if (B->symbol()->VersionId == Config->DefaultSymbolVersion)
628 B->symbol()->VersionId = V.Id;
632 // Returns the size of the longest version name.
633 static int getMaxVersionLen() {
635 for (VersionDefinition &V : Config->VersionDefinitions)
636 Len = std::max(Len, V.Name.size());
640 // Parses a symbol name in the form of <name>@<version> or <name>@@<version>.
641 static std::pair<StringRef, uint16_t>
642 getSymbolVersion(SymbolBody *B, int MaxVersionLen) {
643 StringRef S = B->getName();
645 // MaxVersionLen was passed so that we don't need to scan
646 // all characters in a symbol name. It is effective because
647 // versions are usually short and symbol names can be very long.
648 size_t Pos = S.find('@', std::max(0, int(S.size()) - MaxVersionLen - 2));
649 if (Pos == 0 || Pos == StringRef::npos)
652 StringRef Name = S.substr(0, Pos);
653 StringRef Verstr = S.substr(Pos + 1);
657 // '@@' in a symbol name means the default version.
658 // It is usually the most recent one.
659 bool IsDefault = (Verstr[0] == '@');
661 Verstr = Verstr.substr(1);
663 for (VersionDefinition &V : Config->VersionDefinitions) {
664 if (V.Name == Verstr)
665 return {Name, IsDefault ? V.Id : (V.Id | VERSYM_HIDDEN)};
668 // It is an error if the specified version was not defined.
669 error("symbol " + S + " has undefined version " + Verstr);
673 // Versions are usually assigned to symbols using version scripts,
674 // but there's another way to assign versions to symbols.
675 // If a symbol name contains '@', the string after it is not
676 // actually a part of the symbol name but specifies a version.
677 // This function takes care of it.
678 template <class ELFT> void SymbolTable<ELFT>::scanSymbolVersions() {
679 if (Config->VersionDefinitions.empty())
682 int MaxVersionLen = getMaxVersionLen();
684 // Unfortunately there's no way other than iterating over all
685 // symbols to look for '@' characters in symbol names.
686 // So this is inherently slow. A good news is that we do this
687 // only when versions have been defined.
688 for (Symbol *Sym : SymVector) {
689 // Symbol versions for exported symbols are by nature
690 // only for defined global symbols.
691 SymbolBody *B = Sym->body();
694 uint8_t Visibility = B->getVisibility();
695 if (Visibility != STV_DEFAULT && Visibility != STV_PROTECTED)
698 // Look for '@' in the symbol name.
701 std::tie(Name, Version) = getSymbolVersion(B, MaxVersionLen);
706 Sym->VersionId = Version;
710 template class elf::SymbolTable<ELF32LE>;
711 template class elf::SymbolTable<ELF32BE>;
712 template class elf::SymbolTable<ELF64LE>;
713 template class elf::SymbolTable<ELF64BE>;