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"
23 #include "llvm/ADT/STLExtras.h"
26 using namespace llvm::object;
27 using namespace llvm::ELF;
30 using namespace lld::elf;
32 // All input object files must be for the same architecture
33 // (e.g. it does not make sense to link x86 object files with
34 // MIPS object files.) This function checks for that error.
35 template <class ELFT> static bool isCompatible(InputFile *F) {
36 if (!isa<ELFFileBase<ELFT>>(F) && !isa<BitcodeFile>(F))
39 if (F->EKind == Config->EKind && F->EMachine == Config->EMachine) {
40 if (Config->EMachine != EM_MIPS)
42 if (isMipsN32Abi(F) == Config->MipsN32Abi)
46 if (!Config->Emulation.empty())
47 error(toString(F) + " is incompatible with " + Config->Emulation);
49 error(toString(F) + " is incompatible with " + toString(Config->FirstElf));
53 // Add symbols in File to the symbol table.
54 template <class ELFT> void SymbolTable<ELFT>::addFile(InputFile *File) {
55 if (!isCompatible<ELFT>(File))
59 if (auto *F = dyn_cast<BinaryFile>(File)) {
60 BinaryFiles.push_back(F);
66 if (auto *F = dyn_cast<ArchiveFile>(File)) {
72 if (auto *F = dyn_cast<LazyObjectFile>(File)) {
78 outs() << toString(File) << "\n";
81 if (auto *F = dyn_cast<SharedFile<ELFT>>(File)) {
82 // DSOs are uniquified not by filename but by soname.
84 if (ErrorCount || !SoNames.insert(F->getSoName()).second)
86 SharedFiles.push_back(F);
92 if (auto *F = dyn_cast<BitcodeFile>(File)) {
93 BitcodeFiles.push_back(F);
94 F->parse<ELFT>(ComdatGroups);
98 // Regular object file
99 auto *F = cast<ObjectFile<ELFT>>(File);
100 ObjectFiles.push_back(F);
101 F->parse(ComdatGroups);
104 // This function is where all the optimizations of link-time
105 // optimization happens. When LTO is in use, some input files are
106 // not in native object file format but in the LLVM bitcode format.
107 // This function compiles bitcode files into a few big native files
108 // using LLVM functions and replaces bitcode symbols with the results.
109 // Because all bitcode files that consist of a program are passed
110 // to the compiler at once, it can do whole-program optimization.
111 template <class ELFT> void SymbolTable<ELFT>::addCombinedLTOObject() {
112 if (BitcodeFiles.empty())
115 // Compile bitcode files and replace bitcode symbols.
116 LTO.reset(new BitcodeCompiler);
117 for (BitcodeFile *F : BitcodeFiles)
120 for (InputFile *File : LTO->compile()) {
121 ObjectFile<ELFT> *Obj = cast<ObjectFile<ELFT>>(File);
122 DenseSet<CachedHashStringRef> DummyGroups;
123 Obj->parse(DummyGroups);
124 ObjectFiles.push_back(Obj);
128 template <class ELFT>
129 DefinedRegular<ELFT> *SymbolTable<ELFT>::addAbsolute(StringRef Name,
133 addRegular(Name, Visibility, STT_NOTYPE, 0, 0, Binding, nullptr, nullptr);
134 return cast<DefinedRegular<ELFT>>(Sym->body());
137 // Add Name as an "ignored" symbol. An ignored symbol is a regular
138 // linker-synthesized defined symbol, but is only defined if needed.
139 template <class ELFT>
140 DefinedRegular<ELFT> *SymbolTable<ELFT>::addIgnored(StringRef Name,
141 uint8_t Visibility) {
142 SymbolBody *S = find(Name);
143 if (!S || !S->isUndefined())
145 return addAbsolute(Name, Visibility);
148 // Set a flag for --trace-symbol so that we can print out a log message
149 // if a new symbol with the same name is inserted into the symbol table.
150 template <class ELFT> void SymbolTable<ELFT>::trace(StringRef Name) {
151 Symtab.insert({CachedHashStringRef(Name), {-1, true}});
154 // Rename SYM as __wrap_SYM. The original symbol is preserved as __real_SYM.
155 // Used to implement --wrap.
156 template <class ELFT> void SymbolTable<ELFT>::wrap(StringRef Name) {
157 SymbolBody *B = find(Name);
160 Symbol *Sym = B->symbol();
161 Symbol *Real = addUndefined(Saver.save("__real_" + Name));
162 Symbol *Wrap = addUndefined(Saver.save("__wrap_" + Name));
164 // We rename symbols by replacing the old symbol's SymbolBody with the new
165 // symbol's SymbolBody. This causes all SymbolBody pointers referring to the
166 // old symbol to instead refer to the new symbol.
167 memcpy(Real->Body.buffer, Sym->Body.buffer, sizeof(Sym->Body));
168 memcpy(Sym->Body.buffer, Wrap->Body.buffer, sizeof(Wrap->Body));
171 static uint8_t getMinVisibility(uint8_t VA, uint8_t VB) {
172 if (VA == STV_DEFAULT)
174 if (VB == STV_DEFAULT)
176 return std::min(VA, VB);
179 // Find an existing symbol or create and insert a new one.
180 template <class ELFT>
181 std::pair<Symbol *, bool> SymbolTable<ELFT>::insert(StringRef Name) {
182 auto P = Symtab.insert(
183 {CachedHashStringRef(Name), SymIndex((int)SymVector.size(), false)});
184 SymIndex &V = P.first->second;
185 bool IsNew = P.second;
189 V = SymIndex((int)SymVector.size(), true);
194 Sym = new (BAlloc) Symbol;
195 Sym->InVersionScript = false;
196 Sym->Binding = STB_WEAK;
197 Sym->Visibility = STV_DEFAULT;
198 Sym->IsUsedInRegularObj = false;
199 Sym->ExportDynamic = false;
200 Sym->Traced = V.Traced;
201 Sym->VersionId = Config->DefaultSymbolVersion;
202 SymVector.push_back(Sym);
204 Sym = SymVector[V.Idx];
209 // Construct a string in the form of "Sym in File1 and File2".
210 // Used to construct an error message.
211 static std::string conflictMsg(SymbolBody *Existing, InputFile *NewFile) {
212 return "'" + toString(*Existing) + "' in " + toString(Existing->File) +
213 " and " + toString(NewFile);
216 // Find an existing symbol or create and insert a new one, then apply the given
218 template <class ELFT>
219 std::pair<Symbol *, bool>
220 SymbolTable<ELFT>::insert(StringRef Name, uint8_t Type, uint8_t Visibility,
221 bool CanOmitFromDynSym, InputFile *File) {
222 bool IsUsedInRegularObj = !File || File->kind() == InputFile::ObjectKind;
225 std::tie(S, WasInserted) = insert(Name);
227 // Merge in the new symbol's visibility.
228 S->Visibility = getMinVisibility(S->Visibility, Visibility);
229 if (!CanOmitFromDynSym && (Config->Shared || Config->ExportDynamic))
230 S->ExportDynamic = true;
231 if (IsUsedInRegularObj)
232 S->IsUsedInRegularObj = true;
233 if (!WasInserted && S->body()->Type != SymbolBody::UnknownType &&
234 ((Type == STT_TLS) != S->body()->isTls()))
235 error("TLS attribute mismatch for symbol " + conflictMsg(S->body(), File));
237 return {S, WasInserted};
240 template <class ELFT> Symbol *SymbolTable<ELFT>::addUndefined(StringRef Name) {
241 return addUndefined(Name, /*IsLocal=*/false, STB_GLOBAL, STV_DEFAULT,
243 /*CanOmitFromDynSym*/ false, /*File*/ nullptr);
246 static uint8_t getVisibility(uint8_t StOther) { return StOther & 3; }
248 template <class ELFT>
249 Symbol *SymbolTable<ELFT>::addUndefined(StringRef Name, bool IsLocal,
250 uint8_t Binding, uint8_t StOther,
251 uint8_t Type, bool CanOmitFromDynSym,
255 std::tie(S, WasInserted) =
256 insert(Name, Type, getVisibility(StOther), CanOmitFromDynSym, File);
258 S->Binding = Binding;
259 replaceBody<Undefined<ELFT>>(S, Name, IsLocal, StOther, Type, File);
262 if (Binding != STB_WEAK) {
263 if (S->body()->isShared() || S->body()->isLazy())
264 S->Binding = Binding;
265 if (auto *SS = dyn_cast<SharedSymbol<ELFT>>(S->body()))
266 SS->file()->IsUsed = true;
268 if (auto *L = dyn_cast<Lazy>(S->body())) {
269 // An undefined weak will not fetch archive members, but we have to remember
270 // its type. See also comment in addLazyArchive.
273 else if (InputFile *F = L->fetch())
279 // We have a new defined symbol with the specified binding. Return 1 if the new
280 // symbol should win, -1 if the new symbol should lose, or 0 if both symbols are
281 // strong defined symbols.
282 static int compareDefined(Symbol *S, bool WasInserted, uint8_t Binding) {
285 SymbolBody *Body = S->body();
286 if (Body->isLazy() || Body->isUndefined() || Body->isShared())
288 if (Binding == STB_WEAK)
295 // We have a new non-common defined symbol with the specified binding. Return 1
296 // if the new symbol should win, -1 if the new symbol should lose, or 0 if there
297 // is a conflict. If the new symbol wins, also update the binding.
298 template <typename ELFT>
299 static int compareDefinedNonCommon(Symbol *S, bool WasInserted, uint8_t Binding,
300 bool IsAbsolute, typename ELFT::uint Value) {
301 if (int Cmp = compareDefined(S, WasInserted, Binding)) {
303 S->Binding = Binding;
306 SymbolBody *B = S->body();
307 if (isa<DefinedCommon>(B)) {
308 // Non-common symbols take precedence over common symbols.
309 if (Config->WarnCommon)
310 warn("common " + S->body()->getName() + " is overridden");
312 } else if (auto *R = dyn_cast<DefinedRegular<ELFT>>(B)) {
313 if (R->Section == nullptr && Binding == STB_GLOBAL && IsAbsolute &&
320 template <class ELFT>
321 Symbol *SymbolTable<ELFT>::addCommon(StringRef N, uint64_t Size,
322 uint64_t Alignment, uint8_t Binding,
323 uint8_t StOther, uint8_t Type,
327 std::tie(S, WasInserted) = insert(N, Type, getVisibility(StOther),
328 /*CanOmitFromDynSym*/ false, File);
329 int Cmp = compareDefined(S, WasInserted, Binding);
331 S->Binding = Binding;
332 replaceBody<DefinedCommon>(S, N, Size, Alignment, StOther, Type, File);
333 } else if (Cmp == 0) {
334 auto *C = dyn_cast<DefinedCommon>(S->body());
336 // Non-common symbols take precedence over common symbols.
337 if (Config->WarnCommon)
338 warn("common " + S->body()->getName() + " is overridden");
342 if (Config->WarnCommon)
343 warn("multiple common of " + S->body()->getName());
345 Alignment = C->Alignment = std::max(C->Alignment, Alignment);
347 replaceBody<DefinedCommon>(S, N, Size, Alignment, StOther, Type, File);
352 static void print(const Twine &Msg) {
353 if (Config->AllowMultipleDefinition)
359 static void reportDuplicate(SymbolBody *Existing, InputFile *NewFile) {
360 print("duplicate symbol " + conflictMsg(Existing, NewFile));
363 template <class ELFT>
364 static void reportDuplicate(SymbolBody *Existing,
365 InputSectionBase<ELFT> *ErrSec,
366 typename ELFT::uint ErrOffset) {
367 DefinedRegular<ELFT> *D = dyn_cast<DefinedRegular<ELFT>>(Existing);
368 if (!D || !D->Section || !ErrSec) {
369 reportDuplicate(Existing, ErrSec ? ErrSec->getFile() : nullptr);
373 std::string OldLoc = D->Section->getLocation(D->Value);
374 std::string NewLoc = ErrSec->getLocation(ErrOffset);
376 print(NewLoc + ": duplicate symbol '" + toString(*Existing) + "'");
377 print(OldLoc + ": previous definition was here");
380 template <typename ELFT>
381 Symbol *SymbolTable<ELFT>::addRegular(StringRef Name, uint8_t StOther,
382 uint8_t Type, uintX_t Value, uintX_t Size,
384 InputSectionBase<ELFT> *Section,
388 std::tie(S, WasInserted) = insert(Name, Type, getVisibility(StOther),
389 /*CanOmitFromDynSym*/ false, File);
390 int Cmp = compareDefinedNonCommon<ELFT>(S, WasInserted, Binding,
391 Section == nullptr, Value);
393 replaceBody<DefinedRegular<ELFT>>(S, Name, /*IsLocal=*/false, StOther, Type,
394 Value, Size, Section, File);
396 reportDuplicate(S->body(), Section, Value);
400 template <typename ELFT>
401 Symbol *SymbolTable<ELFT>::addSynthetic(StringRef N,
402 const OutputSectionBase *Section,
403 uintX_t Value, uint8_t StOther) {
406 std::tie(S, WasInserted) = insert(N, STT_NOTYPE, getVisibility(StOther),
407 /*CanOmitFromDynSym*/ false, nullptr);
408 int Cmp = compareDefinedNonCommon<ELFT>(S, WasInserted, STB_GLOBAL,
409 /*IsAbsolute*/ false, /*Value*/ 0);
411 replaceBody<DefinedSynthetic>(S, N, Value, Section);
413 reportDuplicate(S->body(), nullptr);
417 template <typename ELFT>
418 void SymbolTable<ELFT>::addShared(SharedFile<ELFT> *F, StringRef Name,
420 const typename ELFT::Verdef *Verdef) {
421 // DSO symbols do not affect visibility in the output, so we pass STV_DEFAULT
422 // as the visibility, which will leave the visibility in the symbol table
426 std::tie(S, WasInserted) =
427 insert(Name, Sym.getType(), STV_DEFAULT, /*CanOmitFromDynSym*/ true, F);
428 // Make sure we preempt DSO symbols with default visibility.
429 if (Sym.getVisibility() == STV_DEFAULT) {
430 S->ExportDynamic = true;
431 // Exporting preempting symbols takes precedence over linker scripts.
432 if (S->VersionId == VER_NDX_LOCAL)
433 S->VersionId = VER_NDX_GLOBAL;
435 if (WasInserted || isa<Undefined<ELFT>>(S->body())) {
436 replaceBody<SharedSymbol<ELFT>>(S, F, Name, Sym, Verdef);
442 template <class ELFT>
443 Symbol *SymbolTable<ELFT>::addBitcode(StringRef Name, uint8_t Binding,
444 uint8_t StOther, uint8_t Type,
445 bool CanOmitFromDynSym, BitcodeFile *F) {
448 std::tie(S, WasInserted) =
449 insert(Name, Type, getVisibility(StOther), CanOmitFromDynSym, F);
450 int Cmp = compareDefinedNonCommon<ELFT>(S, WasInserted, Binding,
451 /*IsAbs*/ false, /*Value*/ 0);
453 replaceBody<DefinedRegular<ELFT>>(S, Name, /*IsLocal=*/false, StOther, Type,
456 reportDuplicate(S->body(), F);
460 template <class ELFT> SymbolBody *SymbolTable<ELFT>::find(StringRef Name) {
461 auto It = Symtab.find(CachedHashStringRef(Name));
462 if (It == Symtab.end())
464 SymIndex V = It->second;
467 return SymVector[V.Idx]->body();
470 template <class ELFT>
471 void SymbolTable<ELFT>::addLazyArchive(ArchiveFile *F,
472 const object::Archive::Symbol Sym) {
475 StringRef Name = Sym.getName();
476 std::tie(S, WasInserted) = insert(Name);
478 replaceBody<LazyArchive>(S, *F, Sym, SymbolBody::UnknownType);
481 if (!S->body()->isUndefined())
484 // Weak undefined symbols should not fetch members from archives. If we were
485 // to keep old symbol we would not know that an archive member was available
486 // if a strong undefined symbol shows up afterwards in the link. If a strong
487 // undefined symbol never shows up, this lazy symbol will get to the end of
488 // the link and must be treated as the weak undefined one. We already marked
489 // this symbol as used when we added it to the symbol table, but we also need
490 // to preserve its type. FIXME: Move the Type field to Symbol.
492 replaceBody<LazyArchive>(S, *F, Sym, S->body()->Type);
495 std::pair<MemoryBufferRef, uint64_t> MBInfo = F->getMember(&Sym);
496 if (!MBInfo.first.getBuffer().empty())
497 addFile(createObjectFile(MBInfo.first, F->getName(), MBInfo.second));
500 template <class ELFT>
501 void SymbolTable<ELFT>::addLazyObject(StringRef Name, LazyObjectFile &Obj) {
504 std::tie(S, WasInserted) = insert(Name);
506 replaceBody<LazyObject>(S, Name, Obj, SymbolBody::UnknownType);
509 if (!S->body()->isUndefined())
512 // See comment for addLazyArchive above.
514 replaceBody<LazyObject>(S, Name, Obj, S->body()->Type);
516 MemoryBufferRef MBRef = Obj.getBuffer();
517 if (!MBRef.getBuffer().empty())
518 addFile(createObjectFile(MBRef));
522 // Process undefined (-u) flags by loading lazy symbols named by those flags.
523 template <class ELFT> void SymbolTable<ELFT>::scanUndefinedFlags() {
524 for (StringRef S : Config->Undefined)
525 if (auto *L = dyn_cast_or_null<Lazy>(find(S)))
526 if (InputFile *File = L->fetch())
530 // This function takes care of the case in which shared libraries depend on
531 // the user program (not the other way, which is usual). Shared libraries
532 // may have undefined symbols, expecting that the user program provides
533 // the definitions for them. An example is BSD's __progname symbol.
534 // We need to put such symbols to the main program's .dynsym so that
535 // shared libraries can find them.
536 // Except this, we ignore undefined symbols in DSOs.
537 template <class ELFT> void SymbolTable<ELFT>::scanShlibUndefined() {
538 for (SharedFile<ELFT> *File : SharedFiles)
539 for (StringRef U : File->getUndefinedSymbols())
540 if (SymbolBody *Sym = find(U))
541 if (Sym->isDefined())
542 Sym->symbol()->ExportDynamic = true;
545 // Initialize DemangledSyms with a map from demangled symbols to symbol
546 // objects. Used to handle "extern C++" directive in version scripts.
548 // The map will contain all demangled symbols. That can be very large,
549 // and in LLD we generally want to avoid do anything for each symbol.
550 // Then, why are we doing this? Here's why.
552 // Users can use "extern C++ {}" directive to match against demangled
553 // C++ symbols. For example, you can write a pattern such as
554 // "llvm::*::foo(int, ?)". Obviously, there's no way to handle this
555 // other than trying to match a pattern against all demangled symbols.
556 // So, if "extern C++" feature is used, we need to demangle all known
558 template <class ELFT>
559 StringMap<std::vector<SymbolBody *>> &SymbolTable<ELFT>::getDemangledSyms() {
560 if (!DemangledSyms) {
561 DemangledSyms.emplace();
562 for (Symbol *Sym : SymVector) {
563 SymbolBody *B = Sym->body();
564 if (B->isUndefined())
566 if (Optional<std::string> S = demangle(B->getName()))
567 (*DemangledSyms)[*S].push_back(B);
569 (*DemangledSyms)[B->getName()].push_back(B);
572 return *DemangledSyms;
575 template <class ELFT>
576 std::vector<SymbolBody *> SymbolTable<ELFT>::findByVersion(SymbolVersion Ver) {
578 return getDemangledSyms().lookup(Ver.Name);
579 if (SymbolBody *B = find(Ver.Name))
580 if (!B->isUndefined())
585 template <class ELFT>
586 std::vector<SymbolBody *>
587 SymbolTable<ELFT>::findAllByVersion(SymbolVersion Ver) {
588 std::vector<SymbolBody *> Res;
589 StringMatcher M(Ver.Name);
591 if (Ver.IsExternCpp) {
592 for (auto &P : getDemangledSyms())
593 if (M.match(P.first()))
594 Res.insert(Res.end(), P.second.begin(), P.second.end());
598 for (Symbol *Sym : SymVector) {
599 SymbolBody *B = Sym->body();
600 if (!B->isUndefined() && M.match(B->getName()))
606 // If there's only one anonymous version definition in a version
607 // script file, the script does not actually define any symbol version,
608 // but just specifies symbols visibilities. We assume that the script was
609 // in the form of { global: foo; bar; local *; }. So, local is default.
610 // In this function, we make specified symbols global.
611 template <class ELFT> void SymbolTable<ELFT>::handleAnonymousVersion() {
612 for (SymbolVersion &Ver : Config->VersionScriptGlobals) {
613 if (Ver.HasWildcard) {
614 for (SymbolBody *B : findAllByVersion(Ver))
615 B->symbol()->VersionId = VER_NDX_GLOBAL;
618 for (SymbolBody *B : findByVersion(Ver))
619 B->symbol()->VersionId = VER_NDX_GLOBAL;
623 // Set symbol versions to symbols. This function handles patterns
624 // containing no wildcard characters.
625 template <class ELFT>
626 void SymbolTable<ELFT>::assignExactVersion(SymbolVersion Ver, uint16_t VersionId,
627 StringRef VersionName) {
631 // Get a list of symbols which we need to assign the version to.
632 std::vector<SymbolBody *> Syms = findByVersion(Ver);
634 if (Config->NoUndefinedVersion)
635 error("version script assignment of '" + VersionName + "' to symbol '" +
636 Ver.Name + "' failed: symbol not defined");
640 // Assign the version.
641 for (SymbolBody *B : Syms) {
642 Symbol *Sym = B->symbol();
643 if (Sym->InVersionScript)
644 warn("duplicate symbol '" + Ver.Name + "' in version script");
645 Sym->VersionId = VersionId;
646 Sym->InVersionScript = true;
650 template <class ELFT>
651 void SymbolTable<ELFT>::assignWildcardVersion(SymbolVersion Ver,
652 uint16_t VersionId) {
653 if (!Ver.HasWildcard)
655 std::vector<SymbolBody *> Syms = findAllByVersion(Ver);
657 // Exact matching takes precendence over fuzzy matching,
658 // so we set a version to a symbol only if no version has been assigned
659 // to the symbol. This behavior is compatible with GNU.
660 for (SymbolBody *B : Syms)
661 if (B->symbol()->VersionId == Config->DefaultSymbolVersion)
662 B->symbol()->VersionId = VersionId;
665 // This function processes version scripts by updating VersionId
666 // member of symbols.
667 template <class ELFT> void SymbolTable<ELFT>::scanVersionScript() {
668 // Symbol themselves might know their versions because symbols
669 // can contain versions in the form of <name>@<version>.
670 // Let them parse their names.
671 if (!Config->VersionDefinitions.empty())
672 for (Symbol *Sym : SymVector)
673 Sym->body()->parseSymbolVersion();
675 // Handle edge cases first.
676 if (!Config->VersionScriptGlobals.empty()) {
677 handleAnonymousVersion();
681 if (Config->VersionDefinitions.empty())
684 // Now we have version definitions, so we need to set version ids to symbols.
685 // Each version definition has a glob pattern, and all symbols that match
686 // with the pattern get that version.
688 // First, we assign versions to exact matching symbols,
689 // i.e. version definitions not containing any glob meta-characters.
690 for (SymbolVersion &Ver : Config->VersionScriptLocals)
691 assignExactVersion(Ver, VER_NDX_LOCAL, "local");
692 for (VersionDefinition &V : Config->VersionDefinitions)
693 for (SymbolVersion &Ver : V.Globals)
694 assignExactVersion(Ver, V.Id, V.Name);
696 // Next, we assign versions to fuzzy matching symbols,
697 // i.e. version definitions containing glob meta-characters.
698 // Note that because the last match takes precedence over previous matches,
699 // we iterate over the definitions in the reverse order.
700 for (SymbolVersion &Ver : Config->VersionScriptLocals)
701 assignWildcardVersion(Ver, VER_NDX_LOCAL);
702 for (VersionDefinition &V : llvm::reverse(Config->VersionDefinitions))
703 for (SymbolVersion &Ver : V.Globals)
704 assignWildcardVersion(Ver, V.Id);
707 template class elf::SymbolTable<ELF32LE>;
708 template class elf::SymbolTable<ELF32BE>;
709 template class elf::SymbolTable<ELF64LE>;
710 template class elf::SymbolTable<ELF64BE>;