1 //===- SymbolTable.cpp ----------------------------------------------------===//
2 //
3 // The LLVM Linker
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
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
13 // the symbol types.
14 //
15 //===----------------------------------------------------------------------===//
16
17 #include "SymbolTable.h"
18 #include "Config.h"
19 #include "LinkerScript.h"
20 #include "Symbols.h"
21 #include "SyntheticSections.h"
22 #include "lld/Common/ErrorHandler.h"
23 #include "lld/Common/Memory.h"
24 #include "lld/Common/Strings.h"
25 #include "llvm/ADT/STLExtras.h"
26
27 using namespace llvm;
28 using namespace llvm::object;
29 using namespace llvm::ELF;
30
31 using namespace lld;
32 using namespace lld::elf;
33
34 SymbolTable *elf::Symtab;
35
getFirstElf()36 static InputFile *getFirstElf() {
37 if (!ObjectFiles.empty())
38 return ObjectFiles[0];
39 if (!SharedFiles.empty())
40 return SharedFiles[0];
41 return BitcodeFiles[0];
42 }
43
44 // All input object files must be for the same architecture
45 // (e.g. it does not make sense to link x86 object files with
46 // MIPS object files.) This function checks for that error.
isCompatible(InputFile * F)47 static bool isCompatible(InputFile *F) {
48 if (!F->isElf() && !isa<BitcodeFile>(F))
49 return true;
50
51 if (F->EKind == Config->EKind && F->EMachine == Config->EMachine) {
52 if (Config->EMachine != EM_MIPS)
53 return true;
54 if (isMipsN32Abi(F) == Config->MipsN32Abi)
55 return true;
56 }
57
58 if (!Config->Emulation.empty())
59 error(toString(F) + " is incompatible with " + Config->Emulation);
60 else
61 error(toString(F) + " is incompatible with " + toString(getFirstElf()));
62 return false;
63 }
64
65 // Add symbols in File to the symbol table.
addFile(InputFile * File)66 template <class ELFT> void SymbolTable::addFile(InputFile *File) {
67 if (!isCompatible(File))
68 return;
69
70 // Binary file
71 if (auto *F = dyn_cast<BinaryFile>(File)) {
72 BinaryFiles.push_back(F);
73 F->parse();
74 return;
75 }
76
77 // .a file
78 if (auto *F = dyn_cast<ArchiveFile>(File)) {
79 F->parse<ELFT>();
80 return;
81 }
82
83 // Lazy object file
84 if (auto *F = dyn_cast<LazyObjFile>(File)) {
85 LazyObjFiles.push_back(F);
86 F->parse<ELFT>();
87 return;
88 }
89
90 if (Config->Trace)
91 message(toString(File));
92
93 // .so file
94 if (auto *F = dyn_cast<SharedFile<ELFT>>(File)) {
95 // DSOs are uniquified not by filename but by soname.
96 F->parseSoName();
97 if (errorCount())
98 return;
99
100 // If a DSO appears more than once on the command line with and without
101 // --as-needed, --no-as-needed takes precedence over --as-needed because a
102 // user can add an extra DSO with --no-as-needed to force it to be added to
103 // the dependency list.
104 DenseMap<StringRef, InputFile *>::iterator It;
105 bool WasInserted;
106 std::tie(It, WasInserted) = SoNames.try_emplace(F->SoName, F);
107 cast<SharedFile<ELFT>>(It->second)->IsNeeded |= F->IsNeeded;
108 if (!WasInserted)
109 return;
110
111 SharedFiles.push_back(F);
112 F->parseRest();
113 return;
114 }
115
116 // LLVM bitcode file
117 if (auto *F = dyn_cast<BitcodeFile>(File)) {
118 BitcodeFiles.push_back(F);
119 F->parse<ELFT>(ComdatGroups);
120 return;
121 }
122
123 // Regular object file
124 ObjectFiles.push_back(File);
125 cast<ObjFile<ELFT>>(File)->parse(ComdatGroups);
126 }
127
128 // This function is where all the optimizations of link-time
129 // optimization happens. When LTO is in use, some input files are
130 // not in native object file format but in the LLVM bitcode format.
131 // This function compiles bitcode files into a few big native files
132 // using LLVM functions and replaces bitcode symbols with the results.
133 // Because all bitcode files that the program consists of are passed
134 // to the compiler at once, it can do whole-program optimization.
addCombinedLTOObject()135 template <class ELFT> void SymbolTable::addCombinedLTOObject() {
136 if (BitcodeFiles.empty())
137 return;
138
139 // Compile bitcode files and replace bitcode symbols.
140 LTO.reset(new BitcodeCompiler);
141 for (BitcodeFile *F : BitcodeFiles)
142 LTO->add(*F);
143
144 for (InputFile *File : LTO->compile()) {
145 DenseSet<CachedHashStringRef> DummyGroups;
146 auto *Obj = cast<ObjFile<ELFT>>(File);
147 Obj->parse(DummyGroups);
148 for (Symbol *Sym : Obj->getGlobalSymbols())
149 Sym->parseSymbolVersion();
150 ObjectFiles.push_back(File);
151 }
152 }
153
154 // Set a flag for --trace-symbol so that we can print out a log message
155 // if a new symbol with the same name is inserted into the symbol table.
trace(StringRef Name)156 void SymbolTable::trace(StringRef Name) {
157 SymMap.insert({CachedHashStringRef(Name), -1});
158 }
159
wrap(Symbol * Sym,Symbol * Real,Symbol * Wrap)160 void SymbolTable::wrap(Symbol *Sym, Symbol *Real, Symbol *Wrap) {
161 // Swap symbols as instructed by -wrap.
162 int &Idx1 = SymMap[CachedHashStringRef(Sym->getName())];
163 int &Idx2 = SymMap[CachedHashStringRef(Real->getName())];
164 int &Idx3 = SymMap[CachedHashStringRef(Wrap->getName())];
165
166 Idx2 = Idx1;
167 Idx1 = Idx3;
168
169 // Now renaming is complete. No one refers Real symbol. We could leave
170 // Real as-is, but if Real is written to the symbol table, that may
171 // contain irrelevant values. So, we copy all values from Sym to Real.
172 StringRef S = Real->getName();
173 memcpy(Real, Sym, sizeof(SymbolUnion));
174 Real->setName(S);
175 }
176
getMinVisibility(uint8_t VA,uint8_t VB)177 static uint8_t getMinVisibility(uint8_t VA, uint8_t VB) {
178 if (VA == STV_DEFAULT)
179 return VB;
180 if (VB == STV_DEFAULT)
181 return VA;
182 return std::min(VA, VB);
183 }
184
185 // Find an existing symbol or create and insert a new one.
insertName(StringRef Name)186 std::pair<Symbol *, bool> SymbolTable::insertName(StringRef Name) {
187 // <name>@@<version> means the symbol is the default version. In that
188 // case <name>@@<version> will be used to resolve references to <name>.
189 //
190 // Since this is a hot path, the following string search code is
191 // optimized for speed. StringRef::find(char) is much faster than
192 // StringRef::find(StringRef).
193 size_t Pos = Name.find('@');
194 if (Pos != StringRef::npos && Pos + 1 < Name.size() && Name[Pos + 1] == '@')
195 Name = Name.take_front(Pos);
196
197 auto P = SymMap.insert({CachedHashStringRef(Name), (int)SymVector.size()});
198 int &SymIndex = P.first->second;
199 bool IsNew = P.second;
200 bool Traced = false;
201
202 if (SymIndex == -1) {
203 SymIndex = SymVector.size();
204 IsNew = true;
205 Traced = true;
206 }
207
208 if (!IsNew)
209 return {SymVector[SymIndex], false};
210
211 auto *Sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
212 Sym->SymbolKind = Symbol::PlaceholderKind;
213 Sym->Visibility = STV_DEFAULT;
214 Sym->IsUsedInRegularObj = false;
215 Sym->ExportDynamic = false;
216 Sym->CanInline = true;
217 Sym->Traced = Traced;
218 Sym->VersionId = Config->DefaultSymbolVersion;
219 SymVector.push_back(Sym);
220 return {Sym, true};
221 }
222
223 // Find an existing symbol or create and insert a new one, then apply the given
224 // attributes.
insert(StringRef Name,uint8_t Visibility,bool CanOmitFromDynSym,InputFile * File)225 std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name,
226 uint8_t Visibility,
227 bool CanOmitFromDynSym,
228 InputFile *File) {
229 Symbol *S;
230 bool WasInserted;
231 std::tie(S, WasInserted) = insertName(Name);
232
233 // Merge in the new symbol's visibility.
234 S->Visibility = getMinVisibility(S->Visibility, Visibility);
235
236 if (!CanOmitFromDynSym && (Config->Shared || Config->ExportDynamic))
237 S->ExportDynamic = true;
238
239 if (!File || File->kind() == InputFile::ObjKind)
240 S->IsUsedInRegularObj = true;
241
242 return {S, WasInserted};
243 }
244
getVisibility(uint8_t StOther)245 static uint8_t getVisibility(uint8_t StOther) { return StOther & 3; }
246
247 template <class ELFT>
addUndefined(StringRef Name,uint8_t Binding,uint8_t StOther,uint8_t Type,bool CanOmitFromDynSym,InputFile * File)248 Symbol *SymbolTable::addUndefined(StringRef Name, uint8_t Binding,
249 uint8_t StOther, uint8_t Type,
250 bool CanOmitFromDynSym, InputFile *File) {
251 Symbol *S;
252 bool WasInserted;
253 uint8_t Visibility = getVisibility(StOther);
254 std::tie(S, WasInserted) = insert(Name, Visibility, CanOmitFromDynSym, File);
255
256 // An undefined symbol with non default visibility must be satisfied
257 // in the same DSO.
258 if (WasInserted || (isa<SharedSymbol>(S) && Visibility != STV_DEFAULT)) {
259 replaceSymbol<Undefined>(S, File, Name, Binding, StOther, Type);
260 return S;
261 }
262
263 if (S->isShared() || S->isLazy() || (S->isUndefined() && Binding != STB_WEAK))
264 S->Binding = Binding;
265
266 if (S->isLazy()) {
267 // An undefined weak will not fetch archive members. See comment on Lazy in
268 // Symbols.h for the details.
269 if (Binding == STB_WEAK) {
270 S->Type = Type;
271 return S;
272 }
273
274 // Do extra check for --warn-backrefs.
275 //
276 // --warn-backrefs is an option to prevent an undefined reference from
277 // fetching an archive member written earlier in the command line. It can be
278 // used to keep compatibility with GNU linkers to some degree.
279 // I'll explain the feature and why you may find it useful in this comment.
280 //
281 // lld's symbol resolution semantics is more relaxed than traditional Unix
282 // linkers. For example,
283 //
284 // ld.lld foo.a bar.o
285 //
286 // succeeds even if bar.o contains an undefined symbol that has to be
287 // resolved by some object file in foo.a. Traditional Unix linkers don't
288 // allow this kind of backward reference, as they visit each file only once
289 // from left to right in the command line while resolving all undefined
290 // symbols at the moment of visiting.
291 //
292 // In the above case, since there's no undefined symbol when a linker visits
293 // foo.a, no files are pulled out from foo.a, and because the linker forgets
294 // about foo.a after visiting, it can't resolve undefined symbols in bar.o
295 // that could have been resolved otherwise.
296 //
297 // That lld accepts more relaxed form means that (besides it'd make more
298 // sense) you can accidentally write a command line or a build file that
299 // works only with lld, even if you have a plan to distribute it to wider
300 // users who may be using GNU linkers. With --warn-backrefs, you can detect
301 // a library order that doesn't work with other Unix linkers.
302 //
303 // The option is also useful to detect cyclic dependencies between static
304 // archives. Again, lld accepts
305 //
306 // ld.lld foo.a bar.a
307 //
308 // even if foo.a and bar.a depend on each other. With --warn-backrefs, it is
309 // handled as an error.
310 //
311 // Here is how the option works. We assign a group ID to each file. A file
312 // with a smaller group ID can pull out object files from an archive file
313 // with an equal or greater group ID. Otherwise, it is a reverse dependency
314 // and an error.
315 //
316 // A file outside --{start,end}-group gets a fresh ID when instantiated. All
317 // files within the same --{start,end}-group get the same group ID. E.g.
318 //
319 // ld.lld A B --start-group C D --end-group E
320 //
321 // A forms group 0. B form group 1. C and D (including their member object
322 // files) form group 2. E forms group 3. I think that you can see how this
323 // group assignment rule simulates the traditional linker's semantics.
324 bool Backref =
325 Config->WarnBackrefs && File && S->File->GroupId < File->GroupId;
326 fetchLazy<ELFT>(S);
327
328 // We don't report backward references to weak symbols as they can be
329 // overridden later.
330 if (Backref && S->Binding != STB_WEAK)
331 warn("backward reference detected: " + Name + " in " + toString(File) +
332 " refers to " + toString(S->File));
333 }
334 return S;
335 }
336
337 // Using .symver foo,foo@@VER unfortunately creates two symbols: foo and
338 // foo@@VER. We want to effectively ignore foo, so give precedence to
339 // foo@@VER.
340 // FIXME: If users can transition to using
341 // .symver foo,foo@@@VER
342 // we can delete this hack.
compareVersion(Symbol * S,StringRef Name)343 static int compareVersion(Symbol *S, StringRef Name) {
344 bool A = Name.contains("@@");
345 bool B = S->getName().contains("@@");
346 if (A && !B)
347 return 1;
348 if (!A && B)
349 return -1;
350 return 0;
351 }
352
353 // We have a new defined symbol with the specified binding. Return 1 if the new
354 // symbol should win, -1 if the new symbol should lose, or 0 if both symbols are
355 // strong defined symbols.
compareDefined(Symbol * S,bool WasInserted,uint8_t Binding,StringRef Name)356 static int compareDefined(Symbol *S, bool WasInserted, uint8_t Binding,
357 StringRef Name) {
358 if (WasInserted)
359 return 1;
360 if (!S->isDefined())
361 return 1;
362 if (int R = compareVersion(S, Name))
363 return R;
364 if (Binding == STB_WEAK)
365 return -1;
366 if (S->isWeak())
367 return 1;
368 return 0;
369 }
370
371 // We have a new non-common defined symbol with the specified binding. Return 1
372 // if the new symbol should win, -1 if the new symbol should lose, or 0 if there
373 // is a conflict. If the new symbol wins, also update the binding.
compareDefinedNonCommon(Symbol * S,bool WasInserted,uint8_t Binding,bool IsAbsolute,uint64_t Value,StringRef Name)374 static int compareDefinedNonCommon(Symbol *S, bool WasInserted, uint8_t Binding,
375 bool IsAbsolute, uint64_t Value,
376 StringRef Name) {
377 if (int Cmp = compareDefined(S, WasInserted, Binding, Name))
378 return Cmp;
379 if (auto *R = dyn_cast<Defined>(S)) {
380 if (R->Section && isa<BssSection>(R->Section)) {
381 // Non-common symbols take precedence over common symbols.
382 if (Config->WarnCommon)
383 warn("common " + S->getName() + " is overridden");
384 return 1;
385 }
386 if (R->Section == nullptr && Binding == STB_GLOBAL && IsAbsolute &&
387 R->Value == Value)
388 return -1;
389 }
390 return 0;
391 }
392
addCommon(StringRef N,uint64_t Size,uint32_t Alignment,uint8_t Binding,uint8_t StOther,uint8_t Type,InputFile & File)393 Symbol *SymbolTable::addCommon(StringRef N, uint64_t Size, uint32_t Alignment,
394 uint8_t Binding, uint8_t StOther, uint8_t Type,
395 InputFile &File) {
396 Symbol *S;
397 bool WasInserted;
398 std::tie(S, WasInserted) = insert(N, getVisibility(StOther),
399 /*CanOmitFromDynSym*/ false, &File);
400
401 int Cmp = compareDefined(S, WasInserted, Binding, N);
402 if (Cmp < 0)
403 return S;
404
405 if (Cmp > 0) {
406 auto *Bss = make<BssSection>("COMMON", Size, Alignment);
407 Bss->File = &File;
408 Bss->Live = !Config->GcSections;
409 InputSections.push_back(Bss);
410
411 replaceSymbol<Defined>(S, &File, N, Binding, StOther, Type, 0, Size, Bss);
412 return S;
413 }
414
415 auto *D = cast<Defined>(S);
416 auto *Bss = dyn_cast_or_null<BssSection>(D->Section);
417 if (!Bss) {
418 // Non-common symbols take precedence over common symbols.
419 if (Config->WarnCommon)
420 warn("common " + S->getName() + " is overridden");
421 return S;
422 }
423
424 if (Config->WarnCommon)
425 warn("multiple common of " + D->getName());
426
427 Bss->Alignment = std::max(Bss->Alignment, Alignment);
428 if (Size > Bss->Size) {
429 D->File = Bss->File = &File;
430 D->Size = Bss->Size = Size;
431 }
432 return S;
433 }
434
reportDuplicate(Symbol * Sym,InputFile * NewFile,InputSectionBase * ErrSec,uint64_t ErrOffset)435 static void reportDuplicate(Symbol *Sym, InputFile *NewFile,
436 InputSectionBase *ErrSec, uint64_t ErrOffset) {
437 if (Config->AllowMultipleDefinition)
438 return;
439
440 Defined *D = cast<Defined>(Sym);
441 if (!D->Section || !ErrSec) {
442 error("duplicate symbol: " + toString(*Sym) + "\n>>> defined in " +
443 toString(Sym->File) + "\n>>> defined in " + toString(NewFile));
444 return;
445 }
446
447 // Construct and print an error message in the form of:
448 //
449 // ld.lld: error: duplicate symbol: foo
450 // >>> defined at bar.c:30
451 // >>> bar.o (/home/alice/src/bar.o)
452 // >>> defined at baz.c:563
453 // >>> baz.o in archive libbaz.a
454 auto *Sec1 = cast<InputSectionBase>(D->Section);
455 std::string Src1 = Sec1->getSrcMsg(*Sym, D->Value);
456 std::string Obj1 = Sec1->getObjMsg(D->Value);
457 std::string Src2 = ErrSec->getSrcMsg(*Sym, ErrOffset);
458 std::string Obj2 = ErrSec->getObjMsg(ErrOffset);
459
460 std::string Msg = "duplicate symbol: " + toString(*Sym) + "\n>>> defined at ";
461 if (!Src1.empty())
462 Msg += Src1 + "\n>>> ";
463 Msg += Obj1 + "\n>>> defined at ";
464 if (!Src2.empty())
465 Msg += Src2 + "\n>>> ";
466 Msg += Obj2;
467 error(Msg);
468 }
469
addDefined(StringRef Name,uint8_t StOther,uint8_t Type,uint64_t Value,uint64_t Size,uint8_t Binding,SectionBase * Section,InputFile * File)470 Defined *SymbolTable::addDefined(StringRef Name, uint8_t StOther, uint8_t Type,
471 uint64_t Value, uint64_t Size, uint8_t Binding,
472 SectionBase *Section, InputFile *File) {
473 Symbol *S;
474 bool WasInserted;
475 std::tie(S, WasInserted) = insert(Name, getVisibility(StOther),
476 /*CanOmitFromDynSym*/ false, File);
477 int Cmp = compareDefinedNonCommon(S, WasInserted, Binding, Section == nullptr,
478 Value, Name);
479 if (Cmp > 0)
480 replaceSymbol<Defined>(S, File, Name, Binding, StOther, Type, Value, Size,
481 Section);
482 else if (Cmp == 0)
483 reportDuplicate(S, File, dyn_cast_or_null<InputSectionBase>(Section),
484 Value);
485 return cast<Defined>(S);
486 }
487
488 template <typename ELFT>
addShared(StringRef Name,SharedFile<ELFT> & File,const typename ELFT::Sym & Sym,uint32_t Alignment,uint32_t VerdefIndex)489 void SymbolTable::addShared(StringRef Name, SharedFile<ELFT> &File,
490 const typename ELFT::Sym &Sym, uint32_t Alignment,
491 uint32_t VerdefIndex) {
492 // DSO symbols do not affect visibility in the output, so we pass STV_DEFAULT
493 // as the visibility, which will leave the visibility in the symbol table
494 // unchanged.
495 Symbol *S;
496 bool WasInserted;
497 std::tie(S, WasInserted) = insert(Name, STV_DEFAULT,
498 /*CanOmitFromDynSym*/ true, &File);
499 // Make sure we preempt DSO symbols with default visibility.
500 if (Sym.getVisibility() == STV_DEFAULT)
501 S->ExportDynamic = true;
502
503 // An undefined symbol with non default visibility must be satisfied
504 // in the same DSO.
505 auto Replace = [&](uint8_t Binding) {
506 replaceSymbol<SharedSymbol>(S, File, Name, Binding, Sym.st_other,
507 Sym.getType(), Sym.st_value, Sym.st_size,
508 Alignment, VerdefIndex);
509 };
510
511 if (WasInserted)
512 Replace(Sym.getBinding());
513 else if (S->Visibility == STV_DEFAULT && (S->isUndefined() || S->isLazy()))
514 Replace(S->Binding);
515 }
516
addBitcode(StringRef Name,uint8_t Binding,uint8_t StOther,uint8_t Type,bool CanOmitFromDynSym,BitcodeFile & F)517 Symbol *SymbolTable::addBitcode(StringRef Name, uint8_t Binding,
518 uint8_t StOther, uint8_t Type,
519 bool CanOmitFromDynSym, BitcodeFile &F) {
520 Symbol *S;
521 bool WasInserted;
522 std::tie(S, WasInserted) =
523 insert(Name, getVisibility(StOther), CanOmitFromDynSym, &F);
524 int Cmp = compareDefinedNonCommon(S, WasInserted, Binding,
525 /*IsAbs*/ false, /*Value*/ 0, Name);
526 if (Cmp > 0)
527 replaceSymbol<Defined>(S, &F, Name, Binding, StOther, Type, 0, 0, nullptr);
528 else if (Cmp == 0)
529 reportDuplicate(S, &F, nullptr, 0);
530 return S;
531 }
532
find(StringRef Name)533 Symbol *SymbolTable::find(StringRef Name) {
534 auto It = SymMap.find(CachedHashStringRef(Name));
535 if (It == SymMap.end())
536 return nullptr;
537 if (It->second == -1)
538 return nullptr;
539 return SymVector[It->second];
540 }
541
542 template <class ELFT>
addLazyArchive(StringRef Name,ArchiveFile & File,const object::Archive::Symbol Sym)543 void SymbolTable::addLazyArchive(StringRef Name, ArchiveFile &File,
544 const object::Archive::Symbol Sym) {
545 Symbol *S;
546 bool WasInserted;
547 std::tie(S, WasInserted) = insertName(Name);
548 if (WasInserted) {
549 replaceSymbol<LazyArchive>(S, File, STT_NOTYPE, Sym);
550 return;
551 }
552 if (!S->isUndefined())
553 return;
554
555 // An undefined weak will not fetch archive members. See comment on Lazy in
556 // Symbols.h for the details.
557 if (S->isWeak()) {
558 replaceSymbol<LazyArchive>(S, File, S->Type, Sym);
559 S->Binding = STB_WEAK;
560 return;
561 }
562
563 if (InputFile *F = File.fetch(Sym))
564 addFile<ELFT>(F);
565 }
566
567 template <class ELFT>
addLazyObject(StringRef Name,LazyObjFile & File)568 void SymbolTable::addLazyObject(StringRef Name, LazyObjFile &File) {
569 Symbol *S;
570 bool WasInserted;
571 std::tie(S, WasInserted) = insertName(Name);
572 if (WasInserted) {
573 replaceSymbol<LazyObject>(S, File, STT_NOTYPE, Name);
574 return;
575 }
576 if (!S->isUndefined())
577 return;
578
579 // An undefined weak will not fetch archive members. See comment on Lazy in
580 // Symbols.h for the details.
581 if (S->isWeak()) {
582 replaceSymbol<LazyObject>(S, File, S->Type, Name);
583 S->Binding = STB_WEAK;
584 return;
585 }
586
587 if (InputFile *F = File.fetch())
588 addFile<ELFT>(F);
589 }
590
fetchLazy(Symbol * Sym)591 template <class ELFT> void SymbolTable::fetchLazy(Symbol *Sym) {
592 if (auto *S = dyn_cast<LazyArchive>(Sym)) {
593 if (InputFile *File = S->fetch())
594 addFile<ELFT>(File);
595 return;
596 }
597
598 auto *S = cast<LazyObject>(Sym);
599 if (InputFile *File = cast<LazyObjFile>(S->File)->fetch())
600 addFile<ELFT>(File);
601 }
602
603 // Initialize DemangledSyms with a map from demangled symbols to symbol
604 // objects. Used to handle "extern C++" directive in version scripts.
605 //
606 // The map will contain all demangled symbols. That can be very large,
607 // and in LLD we generally want to avoid do anything for each symbol.
608 // Then, why are we doing this? Here's why.
609 //
610 // Users can use "extern C++ {}" directive to match against demangled
611 // C++ symbols. For example, you can write a pattern such as
612 // "llvm::*::foo(int, ?)". Obviously, there's no way to handle this
613 // other than trying to match a pattern against all demangled symbols.
614 // So, if "extern C++" feature is used, we need to demangle all known
615 // symbols.
getDemangledSyms()616 StringMap<std::vector<Symbol *>> &SymbolTable::getDemangledSyms() {
617 if (!DemangledSyms) {
618 DemangledSyms.emplace();
619 for (Symbol *Sym : SymVector) {
620 if (!Sym->isDefined())
621 continue;
622 if (Optional<std::string> S = demangleItanium(Sym->getName()))
623 (*DemangledSyms)[*S].push_back(Sym);
624 else
625 (*DemangledSyms)[Sym->getName()].push_back(Sym);
626 }
627 }
628 return *DemangledSyms;
629 }
630
findByVersion(SymbolVersion Ver)631 std::vector<Symbol *> SymbolTable::findByVersion(SymbolVersion Ver) {
632 if (Ver.IsExternCpp)
633 return getDemangledSyms().lookup(Ver.Name);
634 if (Symbol *B = find(Ver.Name))
635 if (B->isDefined())
636 return {B};
637 return {};
638 }
639
findAllByVersion(SymbolVersion Ver)640 std::vector<Symbol *> SymbolTable::findAllByVersion(SymbolVersion Ver) {
641 std::vector<Symbol *> Res;
642 StringMatcher M(Ver.Name);
643
644 if (Ver.IsExternCpp) {
645 for (auto &P : getDemangledSyms())
646 if (M.match(P.first()))
647 Res.insert(Res.end(), P.second.begin(), P.second.end());
648 return Res;
649 }
650
651 for (Symbol *Sym : SymVector)
652 if (Sym->isDefined() && M.match(Sym->getName()))
653 Res.push_back(Sym);
654 return Res;
655 }
656
657 // If there's only one anonymous version definition in a version
658 // script file, the script does not actually define any symbol version,
659 // but just specifies symbols visibilities.
handleAnonymousVersion()660 void SymbolTable::handleAnonymousVersion() {
661 for (SymbolVersion &Ver : Config->VersionScriptGlobals)
662 assignExactVersion(Ver, VER_NDX_GLOBAL, "global");
663 for (SymbolVersion &Ver : Config->VersionScriptGlobals)
664 assignWildcardVersion(Ver, VER_NDX_GLOBAL);
665 for (SymbolVersion &Ver : Config->VersionScriptLocals)
666 assignExactVersion(Ver, VER_NDX_LOCAL, "local");
667 for (SymbolVersion &Ver : Config->VersionScriptLocals)
668 assignWildcardVersion(Ver, VER_NDX_LOCAL);
669 }
670
671 // Handles -dynamic-list.
handleDynamicList()672 void SymbolTable::handleDynamicList() {
673 for (SymbolVersion &Ver : Config->DynamicList) {
674 std::vector<Symbol *> Syms;
675 if (Ver.HasWildcard)
676 Syms = findAllByVersion(Ver);
677 else
678 Syms = findByVersion(Ver);
679
680 for (Symbol *B : Syms) {
681 if (!Config->Shared)
682 B->ExportDynamic = true;
683 else if (B->includeInDynsym())
684 B->IsPreemptible = true;
685 }
686 }
687 }
688
689 // Set symbol versions to symbols. This function handles patterns
690 // containing no wildcard characters.
assignExactVersion(SymbolVersion Ver,uint16_t VersionId,StringRef VersionName)691 void SymbolTable::assignExactVersion(SymbolVersion Ver, uint16_t VersionId,
692 StringRef VersionName) {
693 if (Ver.HasWildcard)
694 return;
695
696 // Get a list of symbols which we need to assign the version to.
697 std::vector<Symbol *> Syms = findByVersion(Ver);
698 if (Syms.empty()) {
699 if (!Config->UndefinedVersion)
700 error("version script assignment of '" + VersionName + "' to symbol '" +
701 Ver.Name + "' failed: symbol not defined");
702 return;
703 }
704
705 // Assign the version.
706 for (Symbol *Sym : Syms) {
707 // Skip symbols containing version info because symbol versions
708 // specified by symbol names take precedence over version scripts.
709 // See parseSymbolVersion().
710 if (Sym->getName().contains('@'))
711 continue;
712
713 if (Sym->VersionId != Config->DefaultSymbolVersion &&
714 Sym->VersionId != VersionId)
715 error("duplicate symbol '" + Ver.Name + "' in version script");
716 Sym->VersionId = VersionId;
717 }
718 }
719
assignWildcardVersion(SymbolVersion Ver,uint16_t VersionId)720 void SymbolTable::assignWildcardVersion(SymbolVersion Ver, uint16_t VersionId) {
721 if (!Ver.HasWildcard)
722 return;
723
724 // Exact matching takes precendence over fuzzy matching,
725 // so we set a version to a symbol only if no version has been assigned
726 // to the symbol. This behavior is compatible with GNU.
727 for (Symbol *B : findAllByVersion(Ver))
728 if (B->VersionId == Config->DefaultSymbolVersion)
729 B->VersionId = VersionId;
730 }
731
732 // This function processes version scripts by updating VersionId
733 // member of symbols.
scanVersionScript()734 void SymbolTable::scanVersionScript() {
735 // Handle edge cases first.
736 handleAnonymousVersion();
737 handleDynamicList();
738
739 // Now we have version definitions, so we need to set version ids to symbols.
740 // Each version definition has a glob pattern, and all symbols that match
741 // with the pattern get that version.
742
743 // First, we assign versions to exact matching symbols,
744 // i.e. version definitions not containing any glob meta-characters.
745 for (VersionDefinition &V : Config->VersionDefinitions)
746 for (SymbolVersion &Ver : V.Globals)
747 assignExactVersion(Ver, V.Id, V.Name);
748
749 // Next, we assign versions to fuzzy matching symbols,
750 // i.e. version definitions containing glob meta-characters.
751 // Note that because the last match takes precedence over previous matches,
752 // we iterate over the definitions in the reverse order.
753 for (VersionDefinition &V : llvm::reverse(Config->VersionDefinitions))
754 for (SymbolVersion &Ver : V.Globals)
755 assignWildcardVersion(Ver, V.Id);
756
757 // Symbol themselves might know their versions because symbols
758 // can contain versions in the form of <name>@<version>.
759 // Let them parse and update their names to exclude version suffix.
760 for (Symbol *Sym : SymVector)
761 Sym->parseSymbolVersion();
762 }
763
764 template void SymbolTable::addFile<ELF32LE>(InputFile *);
765 template void SymbolTable::addFile<ELF32BE>(InputFile *);
766 template void SymbolTable::addFile<ELF64LE>(InputFile *);
767 template void SymbolTable::addFile<ELF64BE>(InputFile *);
768
769 template Symbol *SymbolTable::addUndefined<ELF32LE>(StringRef, uint8_t, uint8_t,
770 uint8_t, bool, InputFile *);
771 template Symbol *SymbolTable::addUndefined<ELF32BE>(StringRef, uint8_t, uint8_t,
772 uint8_t, bool, InputFile *);
773 template Symbol *SymbolTable::addUndefined<ELF64LE>(StringRef, uint8_t, uint8_t,
774 uint8_t, bool, InputFile *);
775 template Symbol *SymbolTable::addUndefined<ELF64BE>(StringRef, uint8_t, uint8_t,
776 uint8_t, bool, InputFile *);
777
778 template void SymbolTable::addCombinedLTOObject<ELF32LE>();
779 template void SymbolTable::addCombinedLTOObject<ELF32BE>();
780 template void SymbolTable::addCombinedLTOObject<ELF64LE>();
781 template void SymbolTable::addCombinedLTOObject<ELF64BE>();
782
783 template void
784 SymbolTable::addLazyArchive<ELF32LE>(StringRef, ArchiveFile &,
785 const object::Archive::Symbol);
786 template void
787 SymbolTable::addLazyArchive<ELF32BE>(StringRef, ArchiveFile &,
788 const object::Archive::Symbol);
789 template void
790 SymbolTable::addLazyArchive<ELF64LE>(StringRef, ArchiveFile &,
791 const object::Archive::Symbol);
792 template void
793 SymbolTable::addLazyArchive<ELF64BE>(StringRef, ArchiveFile &,
794 const object::Archive::Symbol);
795
796 template void SymbolTable::addLazyObject<ELF32LE>(StringRef, LazyObjFile &);
797 template void SymbolTable::addLazyObject<ELF32BE>(StringRef, LazyObjFile &);
798 template void SymbolTable::addLazyObject<ELF64LE>(StringRef, LazyObjFile &);
799 template void SymbolTable::addLazyObject<ELF64BE>(StringRef, LazyObjFile &);
800
801 template void SymbolTable::fetchLazy<ELF32LE>(Symbol *);
802 template void SymbolTable::fetchLazy<ELF32BE>(Symbol *);
803 template void SymbolTable::fetchLazy<ELF64LE>(Symbol *);
804 template void SymbolTable::fetchLazy<ELF64BE>(Symbol *);
805
806 template void SymbolTable::addShared<ELF32LE>(StringRef, SharedFile<ELF32LE> &,
807 const typename ELF32LE::Sym &,
808 uint32_t Alignment, uint32_t);
809 template void SymbolTable::addShared<ELF32BE>(StringRef, SharedFile<ELF32BE> &,
810 const typename ELF32BE::Sym &,
811 uint32_t Alignment, uint32_t);
812 template void SymbolTable::addShared<ELF64LE>(StringRef, SharedFile<ELF64LE> &,
813 const typename ELF64LE::Sym &,
814 uint32_t Alignment, uint32_t);
815 template void SymbolTable::addShared<ELF64BE>(StringRef, SharedFile<ELF64BE> &,
816 const typename ELF64BE::Sym &,
817 uint32_t Alignment, uint32_t);
818