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