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