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 "Error.h"
  20 #include "LinkerScript.h"
  21 #include "Memory.h"
  22 #include "Symbols.h"
  23 #include "llvm/ADT/STLExtras.h"
  24
  25 using namespace llvm;
  26 using namespace llvm::object;
  27 using namespace llvm::ELF;
  28
  29 using namespace lld;
  30 using namespace lld::elf;
  31
  32 SymbolTable *elf::Symtab;
  33
  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))
  39     return true;
  40
  41   if (F->EKind == Config->EKind && F->EMachine == Config->EMachine) {
  42     if (Config->EMachine != EM_MIPS)
  43       return true;
  44     if (isMipsN32Abi(F) == Config->MipsN32Abi)
  45       return true;
  46   }
  47
  48   if (!Config->Emulation.empty())
  49     error(toString(F) + " is incompatible with " + Config->Emulation);
  50   else
  51     error(toString(F) + " is incompatible with " + toString(Config->FirstElf));
  52   return false;
  53 }
  54
  55 // Add symbols in File to the symbol table.
  56 template <class ELFT> void SymbolTable::addFile(InputFile *File) {
  57   if (!Config->FirstElf && isa<ELFFileBase<ELFT>>(File))
  58     Config->FirstElf = File;
  59
  60   if (!isCompatible<ELFT>(File))
  61     return;
  62
  63   // Binary file
  64   if (auto *F = dyn_cast<BinaryFile>(File)) {
  65     BinaryFile::Instances.push_back(F);
  66     F->parse<ELFT>();
  67     return;
  68   }
  69
  70   // .a file
  71   if (auto *F = dyn_cast<ArchiveFile>(File)) {
  72     F->parse<ELFT>();
  73     return;
  74   }
  75
  76   // Lazy object file
  77   if (auto *F = dyn_cast<LazyObjFile>(File)) {
  78     F->parse<ELFT>();
  79     return;
  80   }
  81
  82   if (Config->Trace)
  83     message(toString(File));
  84
  85   // .so file
  86   if (auto *F = dyn_cast<SharedFile<ELFT>>(File)) {
  87     // DSOs are uniquified not by filename but by soname.
  88     F->parseSoName();
  89     if (ErrorCount || !SoNames.insert(F->SoName).second)
  90       return;
  91     SharedFile<ELFT>::Instances.push_back(F);
  92     F->parseRest();
  93     return;
  94   }
  95
  96   // LLVM bitcode file
  97   if (auto *F = dyn_cast<BitcodeFile>(File)) {
  98     BitcodeFile::Instances.push_back(F);
  99     F->parse<ELFT>(ComdatGroups);
 100     return;
 101   }
 102
 103   // Regular object file
 104   auto *F = cast<ObjFile<ELFT>>(File);
 105   ObjFile<ELFT>::Instances.push_back(F);
 106   F->parse(ComdatGroups);
 107 }
 108
 109 // This function is where all the optimizations of link-time
 110 // optimization happens. When LTO is in use, some input files are
 111 // not in native object file format but in the LLVM bitcode format.
 112 // This function compiles bitcode files into a few big native files
 113 // using LLVM functions and replaces bitcode symbols with the results.
 114 // Because all bitcode files that consist of a program are passed
 115 // to the compiler at once, it can do whole-program optimization.
 116 template <class ELFT> void SymbolTable::addCombinedLTOObject() {
 117   if (BitcodeFile::Instances.empty())
 118     return;
 119
 120   // Compile bitcode files and replace bitcode symbols.
 121   LTO.reset(new BitcodeCompiler);
 122   for (BitcodeFile *F : BitcodeFile::Instances)
 123     LTO->add(*F);
 124
 125   for (InputFile *File : LTO->compile()) {
 126     ObjFile<ELFT> *Obj = cast<ObjFile<ELFT>>(File);
 127     DenseSet<CachedHashStringRef> DummyGroups;
 128     Obj->parse(DummyGroups);
 129     ObjFile<ELFT>::Instances.push_back(Obj);
 130   }
 131 }
 132
 133 template <class ELFT>
 134 DefinedRegular *SymbolTable::addAbsolute(StringRef Name, uint8_t Visibility,
 135                                          uint8_t Binding) {
 136   Symbol *Sym = addRegular<ELFT>(Name, Visibility, STT_NOTYPE, 0, 0, Binding,
 137                                  nullptr, nullptr);
 138   return cast<DefinedRegular>(Sym->body());
 139 }
 140
 141 // Add Name as an "ignored" symbol. An ignored symbol is a regular
 142 // linker-synthesized defined symbol, but is only defined if needed.
 143 template <class ELFT>
 144 DefinedRegular *SymbolTable::addIgnored(StringRef Name, uint8_t Visibility) {
 145   SymbolBody *S = find(Name);
 146   if (!S || S->isInCurrentDSO())
 147     return nullptr;
 148   return addAbsolute<ELFT>(Name, Visibility);
 149 }
 150
 151 // Set a flag for --trace-symbol so that we can print out a log message
 152 // if a new symbol with the same name is inserted into the symbol table.
 153 void SymbolTable::trace(StringRef Name) {
 154   Symtab.insert({CachedHashStringRef(Name), {-1, true}});
 155 }
 156
 157 // Rename SYM as __wrap_SYM. The original symbol is preserved as __real_SYM.
 158 // Used to implement --wrap.
 159 template <class ELFT> void SymbolTable::addSymbolWrap(StringRef Name) {
 160   SymbolBody *B = find(Name);
 161   if (!B)
 162     return;
 163   Symbol *Sym = B->symbol();
 164   Symbol *Real = addUndefined<ELFT>(Saver.save("__real_" + Name));
 165   Symbol *Wrap = addUndefined<ELFT>(Saver.save("__wrap_" + Name));
 166
 167   // Tell LTO not to eliminate this symbol
 168   Wrap->IsUsedInRegularObj = true;
 169
 170   Config->RenamedSymbols[Real] = {Sym, Real->Binding};
 171   Config->RenamedSymbols[Sym] = {Wrap, Sym->Binding};
 172 }
 173
 174 // Creates alias for symbol. Used to implement --defsym=ALIAS=SYM.
 175 template <class ELFT>
 176 void SymbolTable::addSymbolAlias(StringRef Alias, StringRef Name) {
 177   SymbolBody *B = find(Name);
 178   if (!B) {
 179     error("-defsym: undefined symbol: " + Name);
 180     return;
 181   }
 182   Symbol *Sym = B->symbol();
 183   Symbol *AliasSym = addUndefined<ELFT>(Alias);
 184
 185   // Tell LTO not to eliminate this symbol
 186   Sym->IsUsedInRegularObj = true;
 187   Config->RenamedSymbols[AliasSym] = {Sym, AliasSym->Binding};
 188 }
 189
 190 // Apply symbol renames created by -wrap and -defsym. The renames are created
 191 // before LTO in addSymbolWrap() and addSymbolAlias() to have a chance to inform
 192 // LTO (if LTO is running) not to include these symbols in IPO. Now that the
 193 // symbols are finalized, we can perform the replacement.
 194 void SymbolTable::applySymbolRenames() {
 195   for (auto &KV : Config->RenamedSymbols) {
 196     Symbol *Dst = KV.first;
 197     Symbol *Src = KV.second.Target;
 198     Dst->body()->copy(Src->body());
 199     Dst->File = Src->File;
 200     Dst->Binding = KV.second.OriginalBinding;
 201   }
 202 }
 203
 204 static uint8_t getMinVisibility(uint8_t VA, uint8_t VB) {
 205   if (VA == STV_DEFAULT)
 206     return VB;
 207   if (VB == STV_DEFAULT)
 208     return VA;
 209   return std::min(VA, VB);
 210 }
 211
 212 // Find an existing symbol or create and insert a new one.
 213 std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name) {
 214   // <name>@@<version> means the symbol is the default version. In that
 215   // case <name>@@<version> will be used to resolve references to <name>.
 216   size_t Pos = Name.find("@@");
 217   if (Pos != StringRef::npos)
 218     Name = Name.take_front(Pos);
 219
 220   auto P = Symtab.insert(
 221       {CachedHashStringRef(Name), SymIndex((int)SymVector.size(), false)});
 222   SymIndex &V = P.first->second;
 223   bool IsNew = P.second;
 224
 225   if (V.Idx == -1) {
 226     IsNew = true;
 227     V = SymIndex((int)SymVector.size(), true);
 228   }
 229
 230   Symbol *Sym;
 231   if (IsNew) {
 232     Sym = make<Symbol>();
 233     Sym->InVersionScript = false;
 234     Sym->Binding = STB_WEAK;
 235     Sym->Visibility = STV_DEFAULT;
 236     Sym->IsUsedInRegularObj = false;
 237     Sym->ExportDynamic = false;
 238     Sym->Traced = V.Traced;
 239     Sym->VersionId = Config->DefaultSymbolVersion;
 240     SymVector.push_back(Sym);
 241   } else {
 242     Sym = SymVector[V.Idx];
 243   }
 244   return {Sym, IsNew};
 245 }
 246
 247 // Find an existing symbol or create and insert a new one, then apply the given
 248 // attributes.
 249 std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name, uint8_t Type,
 250                                               uint8_t Visibility,
 251                                               bool CanOmitFromDynSym,
 252                                               InputFile *File) {
 253   bool IsUsedInRegularObj = !File || File->kind() == InputFile::ObjectKind;
 254   Symbol *S;
 255   bool WasInserted;
 256   std::tie(S, WasInserted) = insert(Name);
 257
 258   // Merge in the new symbol's visibility.
 259   S->Visibility = getMinVisibility(S->Visibility, Visibility);
 260
 261   if (!CanOmitFromDynSym && (Config->Shared || Config->ExportDynamic))
 262     S->ExportDynamic = true;
 263
 264   if (IsUsedInRegularObj)
 265     S->IsUsedInRegularObj = true;
 266
 267   if (!WasInserted && S->body()->Type != SymbolBody::UnknownType &&
 268       ((Type == STT_TLS) != S->body()->isTls())) {
 269     error("TLS attribute mismatch: " + toString(*S->body()) +
 270           "\n>>> defined in " + toString(S->File) + "\n>>> defined in " +
 271           toString(File));
 272   }
 273
 274   return {S, WasInserted};
 275 }
 276
 277 template <class ELFT> Symbol *SymbolTable::addUndefined(StringRef Name) {
 278   return addUndefined<ELFT>(Name, /*IsLocal=*/false, STB_GLOBAL, STV_DEFAULT,
 279                             /*Type*/ 0,
 280                             /*CanOmitFromDynSym*/ false, /*File*/ nullptr);
 281 }
 282
 283 static uint8_t getVisibility(uint8_t StOther) { return StOther & 3; }
 284
 285 template <class ELFT>
 286 Symbol *SymbolTable::addUndefined(StringRef Name, bool IsLocal, uint8_t Binding,
 287                                   uint8_t StOther, uint8_t Type,
 288                                   bool CanOmitFromDynSym, InputFile *File) {
 289   Symbol *S;
 290   bool WasInserted;
 291   uint8_t Visibility = getVisibility(StOther);
 292   std::tie(S, WasInserted) =
 293       insert(Name, Type, Visibility, CanOmitFromDynSym, File);
 294   // An undefined symbol with non default visibility must be satisfied
 295   // in the same DSO.
 296   if (WasInserted ||
 297       (isa<SharedSymbol>(S->body()) && Visibility != STV_DEFAULT)) {
 298     S->Binding = Binding;
 299     replaceBody<Undefined>(S, File, Name, IsLocal, StOther, Type);
 300     return S;
 301   }
 302   if (Binding != STB_WEAK) {
 303     SymbolBody *B = S->body();
 304     if (B->isShared() || B->isLazy() || B->isUndefined())
 305       S->Binding = Binding;
 306     if (auto *SS = dyn_cast<SharedSymbol>(B))
 307       SS->getFile<ELFT>()->IsUsed = true;
 308   }
 309   if (auto *L = dyn_cast<Lazy>(S->body())) {
 310     // An undefined weak will not fetch archive members, but we have to remember
 311     // its type. See also comment in addLazyArchive.
 312     if (S->isWeak())
 313       L->Type = Type;
 314     else if (InputFile *F = L->fetch())
 315       addFile<ELFT>(F);
 316   }
 317   return S;
 318 }
 319
 320 // Using .symver foo,foo@@VER unfortunately creates two symbols: foo and
 321 // foo@@VER. We want to effectively ignore foo, so give precedence to
 322 // foo@@VER.
 323 // FIXME: If users can transition to using
 324 // .symver foo,foo@@@VER
 325 // we can delete this hack.
 326 static int compareVersion(Symbol *S, StringRef Name) {
 327   bool A = Name.contains("@@");
 328   bool B = S->body()->getName().contains("@@");
 329   if (A && !B)
 330     return 1;
 331   if (!A && B)
 332     return -1;
 333   return 0;
 334 }
 335
 336 // We have a new defined symbol with the specified binding. Return 1 if the new
 337 // symbol should win, -1 if the new symbol should lose, or 0 if both symbols are
 338 // strong defined symbols.
 339 static int compareDefined(Symbol *S, bool WasInserted, uint8_t Binding,
 340                           StringRef Name) {
 341   if (WasInserted)
 342     return 1;
 343   SymbolBody *Body = S->body();
 344   if (!Body->isInCurrentDSO())
 345     return 1;
 346
 347   if (int R = compareVersion(S, Name))
 348     return R;
 349
 350   if (Binding == STB_WEAK)
 351     return -1;
 352   if (S->isWeak())
 353     return 1;
 354   return 0;
 355 }
 356
 357 // We have a new non-common defined symbol with the specified binding. Return 1
 358 // if the new symbol should win, -1 if the new symbol should lose, or 0 if there
 359 // is a conflict. If the new symbol wins, also update the binding.
 360 static int compareDefinedNonCommon(Symbol *S, bool WasInserted, uint8_t Binding,
 361                                    bool IsAbsolute, uint64_t Value,
 362                                    StringRef Name) {
 363   if (int Cmp = compareDefined(S, WasInserted, Binding, Name)) {
 364     if (Cmp > 0)
 365       S->Binding = Binding;
 366     return Cmp;
 367   }
 368   SymbolBody *B = S->body();
 369   if (isa<DefinedCommon>(B)) {
 370     // Non-common symbols take precedence over common symbols.
 371     if (Config->WarnCommon)
 372       warn("common " + S->body()->getName() + " is overridden");
 373     return 1;
 374   } else if (auto *R = dyn_cast<DefinedRegular>(B)) {
 375     if (R->Section == nullptr && Binding == STB_GLOBAL && IsAbsolute &&
 376         R->Value == Value)
 377       return -1;
 378   }
 379   return 0;
 380 }
 381
 382 Symbol *SymbolTable::addCommon(StringRef N, uint64_t Size, uint32_t Alignment,
 383                                uint8_t Binding, uint8_t StOther, uint8_t Type,
 384                                InputFile *File) {
 385   Symbol *S;
 386   bool WasInserted;
 387   std::tie(S, WasInserted) = insert(N, Type, getVisibility(StOther),
 388                                     /*CanOmitFromDynSym*/ false, File);
 389   int Cmp = compareDefined(S, WasInserted, Binding, N);
 390   if (Cmp > 0) {
 391     S->Binding = Binding;
 392     replaceBody<DefinedCommon>(S, File, N, Size, Alignment, StOther, Type);
 393   } else if (Cmp == 0) {
 394     auto *C = dyn_cast<DefinedCommon>(S->body());
 395     if (!C) {
 396       // Non-common symbols take precedence over common symbols.
 397       if (Config->WarnCommon)
 398         warn("common " + S->body()->getName() + " is overridden");
 399       return S;
 400     }
 401
 402     if (Config->WarnCommon)
 403       warn("multiple common of " + S->body()->getName());
 404
 405     Alignment = C->Alignment = std::max(C->Alignment, Alignment);
 406     if (Size > C->Size)
 407       replaceBody<DefinedCommon>(S, File, N, Size, Alignment, StOther, Type);
 408   }
 409   return S;
 410 }
 411
 412 static void warnOrError(const Twine &Msg) {
 413   if (Config->AllowMultipleDefinition)
 414     warn(Msg);
 415   else
 416     error(Msg);
 417 }
 418
 419 static void reportDuplicate(SymbolBody *Sym, InputFile *NewFile) {
 420   warnOrError("duplicate symbol: " + toString(*Sym) + "\n>>> defined in " +
 421               toString(Sym->getFile()) + "\n>>> defined in " +
 422               toString(NewFile));
 423 }
 424
 425 template <class ELFT>
 426 static void reportDuplicate(SymbolBody *Sym, InputSectionBase *ErrSec,
 427                             typename ELFT::uint ErrOffset) {
 428   DefinedRegular *D = dyn_cast<DefinedRegular>(Sym);
 429   if (!D || !D->Section || !ErrSec) {
 430     reportDuplicate(Sym, ErrSec ? ErrSec->File : nullptr);
 431     return;
 432   }
 433
 434   // Construct and print an error message in the form of:
 435   //
 436   //   ld.lld: error: duplicate symbol: foo
 437   //   >>> defined at bar.c:30
 438   //   >>>            bar.o (/home/alice/src/bar.o)
 439   //   >>> defined at baz.c:563
 440   //   >>>            baz.o in archive libbaz.a
 441   auto *Sec1 = cast<InputSectionBase>(D->Section);
 442   std::string Src1 = Sec1->getSrcMsg<ELFT>(D->Value);
 443   std::string Obj1 = Sec1->getObjMsg<ELFT>(D->Value);
 444   std::string Src2 = ErrSec->getSrcMsg<ELFT>(ErrOffset);
 445   std::string Obj2 = ErrSec->getObjMsg<ELFT>(ErrOffset);
 446
 447   std::string Msg = "duplicate symbol: " + toString(*Sym) + "\n>>> defined at ";
 448   if (!Src1.empty())
 449     Msg += Src1 + "\n>>>            ";
 450   Msg += Obj1 + "\n>>> defined at ";
 451   if (!Src2.empty())
 452     Msg += Src2 + "\n>>>            ";
 453   Msg += Obj2;
 454   warnOrError(Msg);
 455 }
 456
 457 template <typename ELFT>
 458 Symbol *SymbolTable::addRegular(StringRef Name, uint8_t StOther, uint8_t Type,
 459                                 uint64_t Value, uint64_t Size, uint8_t Binding,
 460                                 SectionBase *Section, InputFile *File) {
 461   Symbol *S;
 462   bool WasInserted;
 463   std::tie(S, WasInserted) = insert(Name, Type, getVisibility(StOther),
 464                                     /*CanOmitFromDynSym*/ false, File);
 465   int Cmp = compareDefinedNonCommon(S, WasInserted, Binding, Section == nullptr,
 466                                     Value, Name);
 467   if (Cmp > 0)
 468     replaceBody<DefinedRegular>(S, File, Name, /*IsLocal=*/false, StOther, Type,
 469                                 Value, Size, Section);
 470   else if (Cmp == 0)
 471     reportDuplicate<ELFT>(S->body(),
 472                           dyn_cast_or_null<InputSectionBase>(Section), Value);
 473   return S;
 474 }
 475
 476 template <typename ELFT>
 477 void SymbolTable::addShared(SharedFile<ELFT> *File, StringRef Name,
 478                             const typename ELFT::Sym &Sym,
 479                             const typename ELFT::Verdef *Verdef) {
 480   // DSO symbols do not affect visibility in the output, so we pass STV_DEFAULT
 481   // as the visibility, which will leave the visibility in the symbol table
 482   // unchanged.
 483   Symbol *S;
 484   bool WasInserted;
 485   std::tie(S, WasInserted) = insert(Name, Sym.getType(), STV_DEFAULT,
 486                                     /*CanOmitFromDynSym*/ true, File);
 487   // Make sure we preempt DSO symbols with default visibility.
 488   if (Sym.getVisibility() == STV_DEFAULT)
 489     S->ExportDynamic = true;
 490
 491   SymbolBody *Body = S->body();
 492   // An undefined symbol with non default visibility must be satisfied
 493   // in the same DSO.
 494   if (WasInserted ||
 495       (isa<Undefined>(Body) && Body->getVisibility() == STV_DEFAULT)) {
 496     replaceBody<SharedSymbol>(S, File, Name, Sym.st_other, Sym.getType(), &Sym,
 497                               Verdef);
 498     if (!S->isWeak())
 499       File->IsUsed = true;
 500   }
 501 }
 502
 503 Symbol *SymbolTable::addBitcode(StringRef Name, uint8_t Binding,
 504                                 uint8_t StOther, uint8_t Type,
 505                                 bool CanOmitFromDynSym, BitcodeFile *F) {
 506   Symbol *S;
 507   bool WasInserted;
 508   std::tie(S, WasInserted) =
 509       insert(Name, Type, getVisibility(StOther), CanOmitFromDynSym, F);
 510   int Cmp = compareDefinedNonCommon(S, WasInserted, Binding,
 511                                     /*IsAbs*/ false, /*Value*/ 0, Name);
 512   if (Cmp > 0)
 513     replaceBody<DefinedRegular>(S, F, Name, /*IsLocal=*/false, StOther, Type, 0,
 514                                 0, nullptr);
 515   else if (Cmp == 0)
 516     reportDuplicate(S->body(), F);
 517   return S;
 518 }
 519
 520 SymbolBody *SymbolTable::find(StringRef Name) {
 521   auto It = Symtab.find(CachedHashStringRef(Name));
 522   if (It == Symtab.end())
 523     return nullptr;
 524   SymIndex V = It->second;
 525   if (V.Idx == -1)
 526     return nullptr;
 527   return SymVector[V.Idx]->body();
 528 }
 529
 530 SymbolBody *SymbolTable::findInCurrentDSO(StringRef Name) {
 531   if (SymbolBody *S = find(Name))
 532     if (S->isInCurrentDSO())
 533       return S;
 534   return nullptr;
 535 }
 536
 537 template <class ELFT>
 538 Symbol *SymbolTable::addLazyArchive(ArchiveFile *F,
 539                                     const object::Archive::Symbol Sym) {
 540   Symbol *S;
 541   bool WasInserted;
 542   StringRef Name = Sym.getName();
 543   std::tie(S, WasInserted) = insert(Name);
 544   if (WasInserted) {
 545     replaceBody<LazyArchive>(S, F, Sym, SymbolBody::UnknownType);
 546     return S;
 547   }
 548   if (!S->body()->isUndefined())
 549     return S;
 550
 551   // Weak undefined symbols should not fetch members from archives. If we were
 552   // to keep old symbol we would not know that an archive member was available
 553   // if a strong undefined symbol shows up afterwards in the link. If a strong
 554   // undefined symbol never shows up, this lazy symbol will get to the end of
 555   // the link and must be treated as the weak undefined one. We already marked
 556   // this symbol as used when we added it to the symbol table, but we also need
 557   // to preserve its type. FIXME: Move the Type field to Symbol.
 558   if (S->isWeak()) {
 559     replaceBody<LazyArchive>(S, F, Sym, S->body()->Type);
 560     return S;
 561   }
 562   std::pair<MemoryBufferRef, uint64_t> MBInfo = F->getMember(&Sym);
 563   if (!MBInfo.first.getBuffer().empty())
 564     addFile<ELFT>(createObjectFile(MBInfo.first, F->getName(), MBInfo.second));
 565   return S;
 566 }
 567
 568 template <class ELFT>
 569 void SymbolTable::addLazyObject(StringRef Name, LazyObjFile &Obj) {
 570   Symbol *S;
 571   bool WasInserted;
 572   std::tie(S, WasInserted) = insert(Name);
 573   if (WasInserted) {
 574     replaceBody<LazyObject>(S, &Obj, Name, SymbolBody::UnknownType);
 575     return;
 576   }
 577   if (!S->body()->isUndefined())
 578     return;
 579
 580   // See comment for addLazyArchive above.
 581   if (S->isWeak())
 582     replaceBody<LazyObject>(S, &Obj, Name, S->body()->Type);
 583   else if (InputFile *F = Obj.fetch())
 584     addFile<ELFT>(F);
 585 }
 586
 587 // Process undefined (-u) flags by loading lazy symbols named by those flags.
 588 template <class ELFT> void SymbolTable::scanUndefinedFlags() {
 589   for (StringRef S : Config->Undefined)
 590     if (auto *L = dyn_cast_or_null<Lazy>(find(S)))
 591       if (InputFile *File = L->fetch())
 592         addFile<ELFT>(File);
 593 }
 594
 595 // This function takes care of the case in which shared libraries depend on
 596 // the user program (not the other way, which is usual). Shared libraries
 597 // may have undefined symbols, expecting that the user program provides
 598 // the definitions for them. An example is BSD's __progname symbol.
 599 // We need to put such symbols to the main program's .dynsym so that
 600 // shared libraries can find them.
 601 // Except this, we ignore undefined symbols in DSOs.
 602 template <class ELFT> void SymbolTable::scanShlibUndefined() {
 603   for (SharedFile<ELFT> *File : SharedFile<ELFT>::Instances) {
 604     for (StringRef U : File->getUndefinedSymbols()) {
 605       SymbolBody *Sym = find(U);
 606       if (!Sym || !Sym->isDefined())
 607         continue;
 608       Sym->symbol()->ExportDynamic = true;
 609
 610       // If -dynamic-list is given, the default version is set to
 611       // VER_NDX_LOCAL, which prevents a symbol to be exported via .dynsym.
 612       // Set to VER_NDX_GLOBAL so the symbol will be handled as if it were
 613       // specified by -dynamic-list.
 614       Sym->symbol()->VersionId = VER_NDX_GLOBAL;
 615     }
 616   }
 617 }
 618
 619 // Initialize DemangledSyms with a map from demangled symbols to symbol
 620 // objects. Used to handle "extern C++" directive in version scripts.
 621 //
 622 // The map will contain all demangled symbols. That can be very large,
 623 // and in LLD we generally want to avoid do anything for each symbol.
 624 // Then, why are we doing this? Here's why.
 625 //
 626 // Users can use "extern C++ {}" directive to match against demangled
 627 // C++ symbols. For example, you can write a pattern such as
 628 // "llvm::*::foo(int, ?)". Obviously, there's no way to handle this
 629 // other than trying to match a pattern against all demangled symbols.
 630 // So, if "extern C++" feature is used, we need to demangle all known
 631 // symbols.
 632 StringMap<std::vector<SymbolBody *>> &SymbolTable::getDemangledSyms() {
 633   if (!DemangledSyms) {
 634     DemangledSyms.emplace();
 635     for (Symbol *Sym : SymVector) {
 636       SymbolBody *B = Sym->body();
 637       if (B->isUndefined())
 638         continue;
 639       if (Optional<std::string> S = demangle(B->getName()))
 640         (*DemangledSyms)[*S].push_back(B);
 641       else
 642         (*DemangledSyms)[B->getName()].push_back(B);
 643     }
 644   }
 645   return *DemangledSyms;
 646 }
 647
 648 std::vector<SymbolBody *> SymbolTable::findByVersion(SymbolVersion Ver) {
 649   if (Ver.IsExternCpp)
 650     return getDemangledSyms().lookup(Ver.Name);
 651   if (SymbolBody *B = find(Ver.Name))
 652     if (!B->isUndefined())
 653       return {B};
 654   return {};
 655 }
 656
 657 std::vector<SymbolBody *> SymbolTable::findAllByVersion(SymbolVersion Ver) {
 658   std::vector<SymbolBody *> Res;
 659   StringMatcher M(Ver.Name);
 660
 661   if (Ver.IsExternCpp) {
 662     for (auto &P : getDemangledSyms())
 663       if (M.match(P.first()))
 664         Res.insert(Res.end(), P.second.begin(), P.second.end());
 665     return Res;
 666   }
 667
 668   for (Symbol *Sym : SymVector) {
 669     SymbolBody *B = Sym->body();
 670     if (!B->isUndefined() && M.match(B->getName()))
 671       Res.push_back(B);
 672   }
 673   return Res;
 674 }
 675
 676 // If there's only one anonymous version definition in a version
 677 // script file, the script does not actually define any symbol version,
 678 // but just specifies symbols visibilities.
 679 void SymbolTable::handleAnonymousVersion() {
 680   for (SymbolVersion &Ver : Config->VersionScriptGlobals)
 681     assignExactVersion(Ver, VER_NDX_GLOBAL, "global");
 682   for (SymbolVersion &Ver : Config->VersionScriptGlobals)
 683     assignWildcardVersion(Ver, VER_NDX_GLOBAL);
 684   for (SymbolVersion &Ver : Config->VersionScriptLocals)
 685     assignExactVersion(Ver, VER_NDX_LOCAL, "local");
 686   for (SymbolVersion &Ver : Config->VersionScriptLocals)
 687     assignWildcardVersion(Ver, VER_NDX_LOCAL);
 688 }
 689
 690 // Set symbol versions to symbols. This function handles patterns
 691 // containing no wildcard characters.
 692 void SymbolTable::assignExactVersion(SymbolVersion Ver, uint16_t VersionId,
 693                                      StringRef VersionName) {
 694   if (Ver.HasWildcard)
 695     return;
 696
 697   // Get a list of symbols which we need to assign the version to.
 698   std::vector<SymbolBody *> Syms = findByVersion(Ver);
 699   if (Syms.empty()) {
 700     if (Config->NoUndefinedVersion)
 701       error("version script assignment of '" + VersionName + "' to symbol '" +
 702             Ver.Name + "' failed: symbol not defined");
 703     return;
 704   }
 705
 706   // Assign the version.
 707   for (SymbolBody *B : Syms) {
 708     // Skip symbols containing version info because symbol versions
 709     // specified by symbol names take precedence over version scripts.
 710     // See parseSymbolVersion().
 711     if (B->getName().contains('@'))
 712       continue;
 713
 714     Symbol *Sym = B->symbol();
 715     if (Sym->InVersionScript)
 716       warn("duplicate symbol '" + Ver.Name + "' in version script");
 717     Sym->VersionId = VersionId;
 718     Sym->InVersionScript = true;
 719   }
 720 }
 721
 722 void SymbolTable::assignWildcardVersion(SymbolVersion Ver, uint16_t VersionId) {
 723   if (!Ver.HasWildcard)
 724     return;
 725
 726   // Exact matching takes precendence over fuzzy matching,
 727   // so we set a version to a symbol only if no version has been assigned
 728   // to the symbol. This behavior is compatible with GNU.
 729   for (SymbolBody *B : findAllByVersion(Ver))
 730     if (B->symbol()->VersionId == Config->DefaultSymbolVersion)
 731       B->symbol()->VersionId = VersionId;
 732 }
 733
 734 // This function processes version scripts by updating VersionId
 735 // member of symbols.
 736 void SymbolTable::scanVersionScript() {
 737   // Handle edge cases first.
 738   handleAnonymousVersion();
 739
 740   // Now we have version definitions, so we need to set version ids to symbols.
 741   // Each version definition has a glob pattern, and all symbols that match
 742   // with the pattern get that version.
 743
 744   // First, we assign versions to exact matching symbols,
 745   // i.e. version definitions not containing any glob meta-characters.
 746   for (VersionDefinition &V : Config->VersionDefinitions)
 747     for (SymbolVersion &Ver : V.Globals)
 748       assignExactVersion(Ver, V.Id, V.Name);
 749
 750   // Next, we assign versions to fuzzy matching symbols,
 751   // i.e. version definitions containing glob meta-characters.
 752   // Note that because the last match takes precedence over previous matches,
 753   // we iterate over the definitions in the reverse order.
 754   for (VersionDefinition &V : llvm::reverse(Config->VersionDefinitions))
 755     for (SymbolVersion &Ver : V.Globals)
 756       assignWildcardVersion(Ver, V.Id);
 757
 758   // Symbol themselves might know their versions because symbols
 759   // can contain versions in the form of <name>@<version>.
 760   // Let them parse and update their names to exclude version suffix.
 761   for (Symbol *Sym : SymVector)
 762     Sym->body()->parseSymbolVersion();
 763 }
 764
 765 template void SymbolTable::addSymbolWrap<ELF32LE>(StringRef);
 766 template void SymbolTable::addSymbolWrap<ELF32BE>(StringRef);
 767 template void SymbolTable::addSymbolWrap<ELF64LE>(StringRef);
 768 template void SymbolTable::addSymbolWrap<ELF64BE>(StringRef);
 769
 770 template Symbol *SymbolTable::addUndefined<ELF32LE>(StringRef);
 771 template Symbol *SymbolTable::addUndefined<ELF32BE>(StringRef);
 772 template Symbol *SymbolTable::addUndefined<ELF64LE>(StringRef);
 773 template Symbol *SymbolTable::addUndefined<ELF64BE>(StringRef);
 774
 775 template Symbol *SymbolTable::addUndefined<ELF32LE>(StringRef, bool, uint8_t,
 776                                                     uint8_t, uint8_t, bool,
 777                                                     InputFile *);
 778 template Symbol *SymbolTable::addUndefined<ELF32BE>(StringRef, bool, uint8_t,
 779                                                     uint8_t, uint8_t, bool,
 780                                                     InputFile *);
 781 template Symbol *SymbolTable::addUndefined<ELF64LE>(StringRef, bool, uint8_t,
 782                                                     uint8_t, uint8_t, bool,
 783                                                     InputFile *);
 784 template Symbol *SymbolTable::addUndefined<ELF64BE>(StringRef, bool, uint8_t,
 785                                                     uint8_t, uint8_t, bool,
 786                                                     InputFile *);
 787
 788 template void SymbolTable::addSymbolAlias<ELF32LE>(StringRef, StringRef);
 789 template void SymbolTable::addSymbolAlias<ELF32BE>(StringRef, StringRef);
 790 template void SymbolTable::addSymbolAlias<ELF64LE>(StringRef, StringRef);
 791 template void SymbolTable::addSymbolAlias<ELF64BE>(StringRef, StringRef);
 792
 793 template void SymbolTable::addCombinedLTOObject<ELF32LE>();
 794 template void SymbolTable::addCombinedLTOObject<ELF32BE>();
 795 template void SymbolTable::addCombinedLTOObject<ELF64LE>();
 796 template void SymbolTable::addCombinedLTOObject<ELF64BE>();
 797
 798 template Symbol *SymbolTable::addRegular<ELF32LE>(StringRef, uint8_t, uint8_t,
 799                                                   uint64_t, uint64_t, uint8_t,
 800                                                   SectionBase *, InputFile *);
 801 template Symbol *SymbolTable::addRegular<ELF32BE>(StringRef, uint8_t, uint8_t,
 802                                                   uint64_t, uint64_t, uint8_t,
 803                                                   SectionBase *, InputFile *);
 804 template Symbol *SymbolTable::addRegular<ELF64LE>(StringRef, uint8_t, uint8_t,
 805                                                   uint64_t, uint64_t, uint8_t,
 806                                                   SectionBase *, InputFile *);
 807 template Symbol *SymbolTable::addRegular<ELF64BE>(StringRef, uint8_t, uint8_t,
 808                                                   uint64_t, uint64_t, uint8_t,
 809                                                   SectionBase *, InputFile *);
 810
 811 template DefinedRegular *SymbolTable::addAbsolute<ELF32LE>(StringRef, uint8_t,
 812                                                            uint8_t);
 813 template DefinedRegular *SymbolTable::addAbsolute<ELF32BE>(StringRef, uint8_t,
 814                                                            uint8_t);
 815 template DefinedRegular *SymbolTable::addAbsolute<ELF64LE>(StringRef, uint8_t,
 816                                                            uint8_t);
 817 template DefinedRegular *SymbolTable::addAbsolute<ELF64BE>(StringRef, uint8_t,
 818                                                            uint8_t);
 819
 820 template DefinedRegular *SymbolTable::addIgnored<ELF32LE>(StringRef, uint8_t);
 821 template DefinedRegular *SymbolTable::addIgnored<ELF32BE>(StringRef, uint8_t);
 822 template DefinedRegular *SymbolTable::addIgnored<ELF64LE>(StringRef, uint8_t);
 823 template DefinedRegular *SymbolTable::addIgnored<ELF64BE>(StringRef, uint8_t);
 824
 825 template Symbol *
 826 SymbolTable::addLazyArchive<ELF32LE>(ArchiveFile *,
 827                                      const object::Archive::Symbol);
 828 template Symbol *
 829 SymbolTable::addLazyArchive<ELF32BE>(ArchiveFile *,
 830                                      const object::Archive::Symbol);
 831 template Symbol *
 832 SymbolTable::addLazyArchive<ELF64LE>(ArchiveFile *,
 833                                      const object::Archive::Symbol);
 834 template Symbol *
 835 SymbolTable::addLazyArchive<ELF64BE>(ArchiveFile *,
 836                                      const object::Archive::Symbol);
 837
 838 template void SymbolTable::addLazyObject<ELF32LE>(StringRef, LazyObjFile &);
 839 template void SymbolTable::addLazyObject<ELF32BE>(StringRef, LazyObjFile &);
 840 template void SymbolTable::addLazyObject<ELF64LE>(StringRef, LazyObjFile &);
 841 template void SymbolTable::addLazyObject<ELF64BE>(StringRef, LazyObjFile &);
 842
 843 template void SymbolTable::addShared<ELF32LE>(SharedFile<ELF32LE> *, StringRef,
 844                                               const typename ELF32LE::Sym &,
 845                                               const typename ELF32LE::Verdef *);
 846 template void SymbolTable::addShared<ELF32BE>(SharedFile<ELF32BE> *, StringRef,
 847                                               const typename ELF32BE::Sym &,
 848                                               const typename ELF32BE::Verdef *);
 849 template void SymbolTable::addShared<ELF64LE>(SharedFile<ELF64LE> *, StringRef,
 850                                               const typename ELF64LE::Sym &,
 851                                               const typename ELF64LE::Verdef *);
 852 template void SymbolTable::addShared<ELF64BE>(SharedFile<ELF64BE> *, StringRef,
 853                                               const typename ELF64BE::Sym &,
 854                                               const typename ELF64BE::Verdef *);
 855
 856 template void SymbolTable::scanUndefinedFlags<ELF32LE>();
 857 template void SymbolTable::scanUndefinedFlags<ELF32BE>();
 858 template void SymbolTable::scanUndefinedFlags<ELF64LE>();
 859 template void SymbolTable::scanUndefinedFlags<ELF64BE>();
 860
 861 template void SymbolTable::scanShlibUndefined<ELF32LE>();
 862 template void SymbolTable::scanShlibUndefined<ELF32BE>();
 863 template void SymbolTable::scanShlibUndefined<ELF64LE>();
 864 template void SymbolTable::scanShlibUndefined<ELF64BE>();