contrib/llvm/tools/lld/ELF/SymbolTable.cpp

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