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