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