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 "LinkerScript.h"
  20 #include "Symbols.h"
  21 #include "SyntheticSections.h"
  22 #include "lld/Common/ErrorHandler.h"
  23 #include "lld/Common/Memory.h"
  24 #include "lld/Common/Strings.h"
  25 #include "llvm/ADT/STLExtras.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 SymbolTable *elf::Symtab;
  35
  36 static InputFile *getFirstElf() {
  37   if (!ObjectFiles.empty())
  38     return ObjectFiles[0];
  39   if (!SharedFiles.empty())
  40     return SharedFiles[0];
  41   return BitcodeFiles[0];
  42 }
  43
  44 // All input object files must be for the same architecture
  45 // (e.g. it does not make sense to link x86 object files with
  46 // MIPS object files.) This function checks for that error.
  47 static bool isCompatible(InputFile *F) {
  48   if (!F->isElf() && !isa<BitcodeFile>(F))
  49     return true;
  50
  51   if (F->EKind == Config->EKind && F->EMachine == Config->EMachine) {
  52     if (Config->EMachine != EM_MIPS)
  53       return true;
  54     if (isMipsN32Abi(F) == Config->MipsN32Abi)
  55       return true;
  56   }
  57
  58   if (!Config->Emulation.empty())
  59     error(toString(F) + " is incompatible with " + Config->Emulation);
  60   else
  61     error(toString(F) + " is incompatible with " + toString(getFirstElf()));
  62   return false;
  63 }
  64
  65 // Add symbols in File to the symbol table.
  66 template <class ELFT> void SymbolTable::addFile(InputFile *File) {
  67   if (!isCompatible(File))
  68     return;
  69
  70   // Binary file
  71   if (auto *F = dyn_cast<BinaryFile>(File)) {
  72     BinaryFiles.push_back(F);
  73     F->parse();
  74     return;
  75   }
  76
  77   // .a file
  78   if (auto *F = dyn_cast<ArchiveFile>(File)) {
  79     F->parse<ELFT>();
  80     return;
  81   }
  82
  83   // Lazy object file
  84   if (auto *F = dyn_cast<LazyObjFile>(File)) {
  85     LazyObjFiles.push_back(F);
  86     F->parse<ELFT>();
  87     return;
  88   }
  89
  90   if (Config->Trace)
  91     message(toString(File));
  92
  93   // .so file
  94   if (auto *F = dyn_cast<SharedFile<ELFT>>(File)) {
  95     // DSOs are uniquified not by filename but by soname.
  96     F->parseDynamic();
  97     if (errorCount())
  98       return;
  99
 100     // If a DSO appears more than once on the command line with and without
 101     // --as-needed, --no-as-needed takes precedence over --as-needed because a
 102     // user can add an extra DSO with --no-as-needed to force it to be added to
 103     // the dependency list.
 104     DenseMap<StringRef, InputFile *>::iterator It;
 105     bool WasInserted;
 106     std::tie(It, WasInserted) = SoNames.try_emplace(F->SoName, F);
 107     cast<SharedFile<ELFT>>(It->second)->IsNeeded |= F->IsNeeded;
 108     if (!WasInserted)
 109       return;
 110
 111     SharedFiles.push_back(F);
 112     F->parseRest();
 113     return;
 114   }
 115
 116   // LLVM bitcode file
 117   if (auto *F = dyn_cast<BitcodeFile>(File)) {
 118     BitcodeFiles.push_back(F);
 119     F->parse<ELFT>(ComdatGroups);
 120     return;
 121   }
 122
 123   // Regular object file
 124   ObjectFiles.push_back(File);
 125   cast<ObjFile<ELFT>>(File)->parse(ComdatGroups);
 126 }
 127
 128 // This function is where all the optimizations of link-time
 129 // optimization happens. When LTO is in use, some input files are
 130 // not in native object file format but in the LLVM bitcode format.
 131 // This function compiles bitcode files into a few big native files
 132 // using LLVM functions and replaces bitcode symbols with the results.
 133 // Because all bitcode files that the program consists of are passed
 134 // to the compiler at once, it can do whole-program optimization.
 135 template <class ELFT> void SymbolTable::addCombinedLTOObject() {
 136   if (BitcodeFiles.empty())
 137     return;
 138
 139   // Compile bitcode files and replace bitcode symbols.
 140   LTO.reset(new BitcodeCompiler);
 141   for (BitcodeFile *F : BitcodeFiles)
 142     LTO->add(*F);
 143
 144   for (InputFile *File : LTO->compile()) {
 145     DenseSet<CachedHashStringRef> DummyGroups;
 146     auto *Obj = cast<ObjFile<ELFT>>(File);
 147     Obj->parse(DummyGroups);
 148     for (Symbol *Sym : Obj->getGlobalSymbols())
 149       Sym->parseSymbolVersion();
 150     ObjectFiles.push_back(File);
 151   }
 152 }
 153
 154 // Set a flag for --trace-symbol so that we can print out a log message
 155 // if a new symbol with the same name is inserted into the symbol table.
 156 void SymbolTable::trace(StringRef Name) {
 157   SymMap.insert({CachedHashStringRef(Name), -1});
 158 }
 159
 160 void SymbolTable::wrap(Symbol *Sym, Symbol *Real, Symbol *Wrap) {
 161   // Swap symbols as instructed by -wrap.
 162   int &Idx1 = SymMap[CachedHashStringRef(Sym->getName())];
 163   int &Idx2 = SymMap[CachedHashStringRef(Real->getName())];
 164   int &Idx3 = SymMap[CachedHashStringRef(Wrap->getName())];
 165
 166   Idx2 = Idx1;
 167   Idx1 = Idx3;
 168
 169   // Now renaming is complete. No one refers Real symbol. We could leave
 170   // Real as-is, but if Real is written to the symbol table, that may
 171   // contain irrelevant values. So, we copy all values from Sym to Real.
 172   StringRef S = Real->getName();
 173   memcpy(Real, Sym, sizeof(SymbolUnion));
 174   Real->setName(S);
 175 }
 176
 177 static uint8_t getMinVisibility(uint8_t VA, uint8_t VB) {
 178   if (VA == STV_DEFAULT)
 179     return VB;
 180   if (VB == STV_DEFAULT)
 181     return VA;
 182   return std::min(VA, VB);
 183 }
 184
 185 // Find an existing symbol or create and insert a new one.
 186 std::pair<Symbol *, bool> SymbolTable::insertName(StringRef Name) {
 187   // <name>@@<version> means the symbol is the default version. In that
 188   // case <name>@@<version> will be used to resolve references to <name>.
 189   //
 190   // Since this is a hot path, the following string search code is
 191   // optimized for speed. StringRef::find(char) is much faster than
 192   // StringRef::find(StringRef).
 193   size_t Pos = Name.find('@');
 194   if (Pos != StringRef::npos && Pos + 1 < Name.size() && Name[Pos + 1] == '@')
 195     Name = Name.take_front(Pos);
 196
 197   auto P = SymMap.insert({CachedHashStringRef(Name), (int)SymVector.size()});
 198   int &SymIndex = P.first->second;
 199   bool IsNew = P.second;
 200   bool Traced = false;
 201
 202   if (SymIndex == -1) {
 203     SymIndex = SymVector.size();
 204     IsNew = true;
 205     Traced = true;
 206   }
 207
 208   if (!IsNew)
 209     return {SymVector[SymIndex], false};
 210
 211   auto *Sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
 212   Sym->SymbolKind = Symbol::PlaceholderKind;
 213   Sym->Visibility = STV_DEFAULT;
 214   Sym->IsUsedInRegularObj = false;
 215   Sym->ExportDynamic = false;
 216   Sym->CanInline = true;
 217   Sym->Traced = Traced;
 218   Sym->VersionId = Config->DefaultSymbolVersion;
 219   SymVector.push_back(Sym);
 220   return {Sym, true};
 221 }
 222
 223 // Find an existing symbol or create and insert a new one, then apply the given
 224 // attributes.
 225 std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name,
 226                                               uint8_t Visibility,
 227                                               bool CanOmitFromDynSym,
 228                                               InputFile *File) {
 229   Symbol *S;
 230   bool WasInserted;
 231   std::tie(S, WasInserted) = insertName(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 (!File || File->kind() == InputFile::ObjKind)
 240     S->IsUsedInRegularObj = true;
 241
 242   return {S, WasInserted};
 243 }
 244
 245 static uint8_t getVisibility(uint8_t StOther) { return StOther & 3; }
 246
 247 template <class ELFT>
 248 Symbol *SymbolTable::addUndefined(StringRef Name, uint8_t Binding,
 249                                   uint8_t StOther, uint8_t Type,
 250                                   bool CanOmitFromDynSym, InputFile *File) {
 251   Symbol *S;
 252   bool WasInserted;
 253   uint8_t Visibility = getVisibility(StOther);
 254   std::tie(S, WasInserted) = insert(Name, Visibility, CanOmitFromDynSym, File);
 255
 256   // An undefined symbol with non default visibility must be satisfied
 257   // in the same DSO.
 258   if (WasInserted || (isa<SharedSymbol>(S) && Visibility != STV_DEFAULT)) {
 259     replaceSymbol<Undefined>(S, File, Name, Binding, StOther, Type);
 260     return S;
 261   }
 262
 263   if (S->isShared() || S->isLazy() || (S->isUndefined() && Binding != STB_WEAK))
 264     S->Binding = Binding;
 265
 266   if (S->isLazy()) {
 267     // An undefined weak will not fetch archive members. See comment on Lazy in
 268     // Symbols.h for the details.
 269     if (Binding == STB_WEAK) {
 270       S->Type = Type;
 271       return S;
 272     }
 273
 274     // Do extra check for --warn-backrefs.
 275     //
 276     // --warn-backrefs is an option to prevent an undefined reference from
 277     // fetching an archive member written earlier in the command line. It can be
 278     // used to keep compatibility with GNU linkers to some degree.
 279     // I'll explain the feature and why you may find it useful in this comment.
 280     //
 281     // lld's symbol resolution semantics is more relaxed than traditional Unix
 282     // linkers. For example,
 283     //
 284     //   ld.lld foo.a bar.o
 285     //
 286     // succeeds even if bar.o contains an undefined symbol that has to be
 287     // resolved by some object file in foo.a. Traditional Unix linkers don't
 288     // allow this kind of backward reference, as they visit each file only once
 289     // from left to right in the command line while resolving all undefined
 290     // symbols at the moment of visiting.
 291     //
 292     // In the above case, since there's no undefined symbol when a linker visits
 293     // foo.a, no files are pulled out from foo.a, and because the linker forgets
 294     // about foo.a after visiting, it can't resolve undefined symbols in bar.o
 295     // that could have been resolved otherwise.
 296     //
 297     // That lld accepts more relaxed form means that (besides it'd make more
 298     // sense) you can accidentally write a command line or a build file that
 299     // works only with lld, even if you have a plan to distribute it to wider
 300     // users who may be using GNU linkers. With --warn-backrefs, you can detect
 301     // a library order that doesn't work with other Unix linkers.
 302     //
 303     // The option is also useful to detect cyclic dependencies between static
 304     // archives. Again, lld accepts
 305     //
 306     //   ld.lld foo.a bar.a
 307     //
 308     // even if foo.a and bar.a depend on each other. With --warn-backrefs, it is
 309     // handled as an error.
 310     //
 311     // Here is how the option works. We assign a group ID to each file. A file
 312     // with a smaller group ID can pull out object files from an archive file
 313     // with an equal or greater group ID. Otherwise, it is a reverse dependency
 314     // and an error.
 315     //
 316     // A file outside --{start,end}-group gets a fresh ID when instantiated. All
 317     // files within the same --{start,end}-group get the same group ID. E.g.
 318     //
 319     //   ld.lld A B --start-group C D --end-group E
 320     //
 321     // A forms group 0. B form group 1. C and D (including their member object
 322     // files) form group 2. E forms group 3. I think that you can see how this
 323     // group assignment rule simulates the traditional linker's semantics.
 324     bool Backref =
 325         Config->WarnBackrefs && File && S->File->GroupId < File->GroupId;
 326     fetchLazy<ELFT>(S);
 327
 328     // We don't report backward references to weak symbols as they can be
 329     // overridden later.
 330     if (Backref && S->Binding != STB_WEAK)
 331       warn("backward reference detected: " + Name + " in " + toString(File) +
 332            " refers to " + toString(S->File));
 333   }
 334   return S;
 335 }
 336
 337 // Using .symver foo,foo@@VER unfortunately creates two symbols: foo and
 338 // foo@@VER. We want to effectively ignore foo, so give precedence to
 339 // foo@@VER.
 340 // FIXME: If users can transition to using
 341 // .symver foo,foo@@@VER
 342 // we can delete this hack.
 343 static int compareVersion(Symbol *S, StringRef Name) {
 344   bool A = Name.contains("@@");
 345   bool B = S->getName().contains("@@");
 346   if (A && !B)
 347     return 1;
 348   if (!A && B)
 349     return -1;
 350   return 0;
 351 }
 352
 353 // We have a new defined symbol with the specified binding. Return 1 if the new
 354 // symbol should win, -1 if the new symbol should lose, or 0 if both symbols are
 355 // strong defined symbols.
 356 static int compareDefined(Symbol *S, bool WasInserted, uint8_t Binding,
 357                           StringRef Name) {
 358   if (WasInserted)
 359     return 1;
 360   if (!S->isDefined())
 361     return 1;
 362   if (int R = compareVersion(S, Name))
 363     return R;
 364   if (Binding == STB_WEAK)
 365     return -1;
 366   if (S->isWeak())
 367     return 1;
 368   return 0;
 369 }
 370
 371 // We have a new non-common defined symbol with the specified binding. Return 1
 372 // if the new symbol should win, -1 if the new symbol should lose, or 0 if there
 373 // is a conflict. If the new symbol wins, also update the binding.
 374 static int compareDefinedNonCommon(Symbol *S, bool WasInserted, uint8_t Binding,
 375                                    bool IsAbsolute, uint64_t Value,
 376                                    StringRef Name) {
 377   if (int Cmp = compareDefined(S, WasInserted, Binding, Name))
 378     return Cmp;
 379   if (auto *R = dyn_cast<Defined>(S)) {
 380     if (R->Section && isa<BssSection>(R->Section)) {
 381       // Non-common symbols take precedence over common symbols.
 382       if (Config->WarnCommon)
 383         warn("common " + S->getName() + " is overridden");
 384       return 1;
 385     }
 386     if (R->Section == nullptr && Binding == STB_GLOBAL && IsAbsolute &&
 387         R->Value == Value)
 388       return -1;
 389   }
 390   return 0;
 391 }
 392
 393 Symbol *SymbolTable::addCommon(StringRef N, uint64_t Size, uint32_t Alignment,
 394                                uint8_t Binding, uint8_t StOther, uint8_t Type,
 395                                InputFile &File) {
 396   Symbol *S;
 397   bool WasInserted;
 398   std::tie(S, WasInserted) = insert(N, getVisibility(StOther),
 399                                     /*CanOmitFromDynSym*/ false, &File);
 400
 401   int Cmp = compareDefined(S, WasInserted, Binding, N);
 402   if (Cmp < 0)
 403     return S;
 404
 405   if (Cmp > 0) {
 406     auto *Bss = make<BssSection>("COMMON", Size, Alignment);
 407     Bss->File = &File;
 408     Bss->Live = !Config->GcSections;
 409     InputSections.push_back(Bss);
 410
 411     replaceSymbol<Defined>(S, &File, N, Binding, StOther, Type, 0, Size, Bss);
 412     return S;
 413   }
 414
 415   auto *D = cast<Defined>(S);
 416   auto *Bss = dyn_cast_or_null<BssSection>(D->Section);
 417   if (!Bss) {
 418     // Non-common symbols take precedence over common symbols.
 419     if (Config->WarnCommon)
 420       warn("common " + S->getName() + " is overridden");
 421     return S;
 422   }
 423
 424   if (Config->WarnCommon)
 425     warn("multiple common of " + D->getName());
 426
 427   Bss->Alignment = std::max(Bss->Alignment, Alignment);
 428   if (Size > Bss->Size) {
 429     D->File = Bss->File = &File;
 430     D->Size = Bss->Size = Size;
 431   }
 432   return S;
 433 }
 434
 435 static void reportDuplicate(Symbol *Sym, InputFile *NewFile,
 436                             InputSectionBase *ErrSec, uint64_t ErrOffset) {
 437   if (Config->AllowMultipleDefinition)
 438     return;
 439
 440   Defined *D = cast<Defined>(Sym);
 441   if (!D->Section || !ErrSec) {
 442     error("duplicate symbol: " + toString(*Sym) + "\n>>> defined in " +
 443           toString(Sym->File) + "\n>>> defined in " + toString(NewFile));
 444     return;
 445   }
 446
 447   // Construct and print an error message in the form of:
 448   //
 449   //   ld.lld: error: duplicate symbol: foo
 450   //   >>> defined at bar.c:30
 451   //   >>>            bar.o (/home/alice/src/bar.o)
 452   //   >>> defined at baz.c:563
 453   //   >>>            baz.o in archive libbaz.a
 454   auto *Sec1 = cast<InputSectionBase>(D->Section);
 455   std::string Src1 = Sec1->getSrcMsg(*Sym, D->Value);
 456   std::string Obj1 = Sec1->getObjMsg(D->Value);
 457   std::string Src2 = ErrSec->getSrcMsg(*Sym, ErrOffset);
 458   std::string Obj2 = ErrSec->getObjMsg(ErrOffset);
 459
 460   std::string Msg = "duplicate symbol: " + toString(*Sym) + "\n>>> defined at ";
 461   if (!Src1.empty())
 462     Msg += Src1 + "\n>>>            ";
 463   Msg += Obj1 + "\n>>> defined at ";
 464   if (!Src2.empty())
 465     Msg += Src2 + "\n>>>            ";
 466   Msg += Obj2;
 467   error(Msg);
 468 }
 469
 470 Defined *SymbolTable::addDefined(StringRef Name, uint8_t StOther, uint8_t Type,
 471                                  uint64_t Value, uint64_t Size, uint8_t Binding,
 472                                  SectionBase *Section, InputFile *File) {
 473   Symbol *S;
 474   bool WasInserted;
 475   std::tie(S, WasInserted) = insert(Name, getVisibility(StOther),
 476                                     /*CanOmitFromDynSym*/ false, File);
 477   int Cmp = compareDefinedNonCommon(S, WasInserted, Binding, Section == nullptr,
 478                                     Value, Name);
 479   if (Cmp > 0)
 480     replaceSymbol<Defined>(S, File, Name, Binding, StOther, Type, Value, Size,
 481                            Section);
 482   else if (Cmp == 0)
 483     reportDuplicate(S, File, dyn_cast_or_null<InputSectionBase>(Section),
 484                     Value);
 485   return cast<Defined>(S);
 486 }
 487
 488 template <typename ELFT>
 489 void SymbolTable::addShared(StringRef Name, SharedFile<ELFT> &File,
 490                             const typename ELFT::Sym &Sym, uint32_t Alignment,
 491                             uint32_t VerdefIndex) {
 492   // DSO symbols do not affect visibility in the output, so we pass STV_DEFAULT
 493   // as the visibility, which will leave the visibility in the symbol table
 494   // unchanged.
 495   Symbol *S;
 496   bool WasInserted;
 497   std::tie(S, WasInserted) = insert(Name, STV_DEFAULT,
 498                                     /*CanOmitFromDynSym*/ true, &File);
 499   // Make sure we preempt DSO symbols with default visibility.
 500   if (Sym.getVisibility() == STV_DEFAULT)
 501     S->ExportDynamic = true;
 502
 503   // An undefined symbol with non default visibility must be satisfied
 504   // in the same DSO.
 505   auto Replace = [&](uint8_t Binding) {
 506     replaceSymbol<SharedSymbol>(S, File, Name, Binding, Sym.st_other,
 507                                 Sym.getType(), Sym.st_value, Sym.st_size,
 508                                 Alignment, VerdefIndex);
 509   };
 510
 511   if (WasInserted)
 512     Replace(Sym.getBinding());
 513   else if (S->Visibility == STV_DEFAULT && (S->isUndefined() || S->isLazy()))
 514     Replace(S->Binding);
 515 }
 516
 517 Symbol *SymbolTable::addBitcode(StringRef Name, uint8_t Binding,
 518                                 uint8_t StOther, uint8_t Type,
 519                                 bool CanOmitFromDynSym, BitcodeFile &F) {
 520   Symbol *S;
 521   bool WasInserted;
 522   std::tie(S, WasInserted) =
 523       insert(Name, getVisibility(StOther), CanOmitFromDynSym, &F);
 524   int Cmp = compareDefinedNonCommon(S, WasInserted, Binding,
 525                                     /*IsAbs*/ false, /*Value*/ 0, Name);
 526   if (Cmp > 0)
 527     replaceSymbol<Defined>(S, &F, Name, Binding, StOther, Type, 0, 0, nullptr);
 528   else if (Cmp == 0)
 529     reportDuplicate(S, &F, nullptr, 0);
 530   return S;
 531 }
 532
 533 Symbol *SymbolTable::find(StringRef Name) {
 534   auto It = SymMap.find(CachedHashStringRef(Name));
 535   if (It == SymMap.end())
 536     return nullptr;
 537   if (It->second == -1)
 538     return nullptr;
 539   return SymVector[It->second];
 540 }
 541
 542 template <class ELFT>
 543 void SymbolTable::addLazyArchive(StringRef Name, ArchiveFile &File,
 544                                  const object::Archive::Symbol Sym) {
 545   Symbol *S;
 546   bool WasInserted;
 547   std::tie(S, WasInserted) = insertName(Name);
 548   if (WasInserted) {
 549     replaceSymbol<LazyArchive>(S, File, STT_NOTYPE, Sym);
 550     return;
 551   }
 552   if (!S->isUndefined())
 553     return;
 554
 555   // An undefined weak will not fetch archive members. See comment on Lazy in
 556   // Symbols.h for the details.
 557   if (S->isWeak()) {
 558     replaceSymbol<LazyArchive>(S, File, S->Type, Sym);
 559     S->Binding = STB_WEAK;
 560     return;
 561   }
 562
 563   if (InputFile *F = File.fetch(Sym))
 564     addFile<ELFT>(F);
 565 }
 566
 567 template <class ELFT>
 568 void SymbolTable::addLazyObject(StringRef Name, LazyObjFile &File) {
 569   Symbol *S;
 570   bool WasInserted;
 571   std::tie(S, WasInserted) = insertName(Name);
 572   if (WasInserted) {
 573     replaceSymbol<LazyObject>(S, File, STT_NOTYPE, Name);
 574     return;
 575   }
 576   if (!S->isUndefined())
 577     return;
 578
 579   // An undefined weak will not fetch archive members. See comment on Lazy in
 580   // Symbols.h for the details.
 581   if (S->isWeak()) {
 582     replaceSymbol<LazyObject>(S, File, S->Type, Name);
 583     S->Binding = STB_WEAK;
 584     return;
 585   }
 586
 587   if (InputFile *F = File.fetch())
 588     addFile<ELFT>(F);
 589 }
 590
 591 template <class ELFT> void SymbolTable::fetchLazy(Symbol *Sym) {
 592   if (auto *S = dyn_cast<LazyArchive>(Sym)) {
 593     if (InputFile *File = S->fetch())
 594       addFile<ELFT>(File);
 595     return;
 596   }
 597
 598   auto *S = cast<LazyObject>(Sym);
 599   if (InputFile *File = cast<LazyObjFile>(S->File)->fetch())
 600     addFile<ELFT>(File);
 601 }
 602
 603 // Initialize DemangledSyms with a map from demangled symbols to symbol
 604 // objects. Used to handle "extern C++" directive in version scripts.
 605 //
 606 // The map will contain all demangled symbols. That can be very large,
 607 // and in LLD we generally want to avoid do anything for each symbol.
 608 // Then, why are we doing this? Here's why.
 609 //
 610 // Users can use "extern C++ {}" directive to match against demangled
 611 // C++ symbols. For example, you can write a pattern such as
 612 // "llvm::*::foo(int, ?)". Obviously, there's no way to handle this
 613 // other than trying to match a pattern against all demangled symbols.
 614 // So, if "extern C++" feature is used, we need to demangle all known
 615 // symbols.
 616 StringMap<std::vector<Symbol *>> &SymbolTable::getDemangledSyms() {
 617   if (!DemangledSyms) {
 618     DemangledSyms.emplace();
 619     for (Symbol *Sym : SymVector) {
 620       if (!Sym->isDefined())
 621         continue;
 622       if (Optional<std::string> S = demangleItanium(Sym->getName()))
 623         (*DemangledSyms)[*S].push_back(Sym);
 624       else
 625         (*DemangledSyms)[Sym->getName()].push_back(Sym);
 626     }
 627   }
 628   return *DemangledSyms;
 629 }
 630
 631 std::vector<Symbol *> SymbolTable::findByVersion(SymbolVersion Ver) {
 632   if (Ver.IsExternCpp)
 633     return getDemangledSyms().lookup(Ver.Name);
 634   if (Symbol *B = find(Ver.Name))
 635     if (B->isDefined())
 636       return {B};
 637   return {};
 638 }
 639
 640 std::vector<Symbol *> SymbolTable::findAllByVersion(SymbolVersion Ver) {
 641   std::vector<Symbol *> Res;
 642   StringMatcher M(Ver.Name);
 643
 644   if (Ver.IsExternCpp) {
 645     for (auto &P : getDemangledSyms())
 646       if (M.match(P.first()))
 647         Res.insert(Res.end(), P.second.begin(), P.second.end());
 648     return Res;
 649   }
 650
 651   for (Symbol *Sym : SymVector)
 652     if (Sym->isDefined() && M.match(Sym->getName()))
 653       Res.push_back(Sym);
 654   return Res;
 655 }
 656
 657 // If there's only one anonymous version definition in a version
 658 // script file, the script does not actually define any symbol version,
 659 // but just specifies symbols visibilities.
 660 void SymbolTable::handleAnonymousVersion() {
 661   for (SymbolVersion &Ver : Config->VersionScriptGlobals)
 662     assignExactVersion(Ver, VER_NDX_GLOBAL, "global");
 663   for (SymbolVersion &Ver : Config->VersionScriptGlobals)
 664     assignWildcardVersion(Ver, VER_NDX_GLOBAL);
 665   for (SymbolVersion &Ver : Config->VersionScriptLocals)
 666     assignExactVersion(Ver, VER_NDX_LOCAL, "local");
 667   for (SymbolVersion &Ver : Config->VersionScriptLocals)
 668     assignWildcardVersion(Ver, VER_NDX_LOCAL);
 669 }
 670
 671 // Handles -dynamic-list.
 672 void SymbolTable::handleDynamicList() {
 673   for (SymbolVersion &Ver : Config->DynamicList) {
 674     std::vector<Symbol *> Syms;
 675     if (Ver.HasWildcard)
 676       Syms = findAllByVersion(Ver);
 677     else
 678       Syms = findByVersion(Ver);
 679
 680     for (Symbol *B : Syms) {
 681       if (!Config->Shared)
 682         B->ExportDynamic = true;
 683       else if (B->includeInDynsym())
 684         B->IsPreemptible = true;
 685     }
 686   }
 687 }
 688
 689 // Set symbol versions to symbols. This function handles patterns
 690 // containing no wildcard characters.
 691 void SymbolTable::assignExactVersion(SymbolVersion Ver, uint16_t VersionId,
 692                                      StringRef VersionName) {
 693   if (Ver.HasWildcard)
 694     return;
 695
 696   // Get a list of symbols which we need to assign the version to.
 697   std::vector<Symbol *> Syms = findByVersion(Ver);
 698   if (Syms.empty()) {
 699     if (!Config->UndefinedVersion)
 700       error("version script assignment of '" + VersionName + "' to symbol '" +
 701             Ver.Name + "' failed: symbol not defined");
 702     return;
 703   }
 704
 705   // Assign the version.
 706   for (Symbol *Sym : Syms) {
 707     // Skip symbols containing version info because symbol versions
 708     // specified by symbol names take precedence over version scripts.
 709     // See parseSymbolVersion().
 710     if (Sym->getName().contains('@'))
 711       continue;
 712
 713     if (Sym->VersionId != Config->DefaultSymbolVersion &&
 714         Sym->VersionId != VersionId)
 715       error("duplicate symbol '" + Ver.Name + "' in version script");
 716     Sym->VersionId = VersionId;
 717   }
 718 }
 719
 720 void SymbolTable::assignWildcardVersion(SymbolVersion Ver, uint16_t VersionId) {
 721   if (!Ver.HasWildcard)
 722     return;
 723
 724   // Exact matching takes precendence over fuzzy matching,
 725   // so we set a version to a symbol only if no version has been assigned
 726   // to the symbol. This behavior is compatible with GNU.
 727   for (Symbol *B : findAllByVersion(Ver))
 728     if (B->VersionId == Config->DefaultSymbolVersion)
 729       B->VersionId = VersionId;
 730 }
 731
 732 // This function processes version scripts by updating VersionId
 733 // member of symbols.
 734 void SymbolTable::scanVersionScript() {
 735   // Handle edge cases first.
 736   handleAnonymousVersion();
 737   handleDynamicList();
 738
 739   // Now we have version definitions, so we need to set version ids to symbols.
 740   // Each version definition has a glob pattern, and all symbols that match
 741   // with the pattern get that version.
 742
 743   // First, we assign versions to exact matching symbols,
 744   // i.e. version definitions not containing any glob meta-characters.
 745   for (VersionDefinition &V : Config->VersionDefinitions)
 746     for (SymbolVersion &Ver : V.Globals)
 747       assignExactVersion(Ver, V.Id, V.Name);
 748
 749   // Next, we assign versions to fuzzy matching symbols,
 750   // i.e. version definitions containing glob meta-characters.
 751   // Note that because the last match takes precedence over previous matches,
 752   // we iterate over the definitions in the reverse order.
 753   for (VersionDefinition &V : llvm::reverse(Config->VersionDefinitions))
 754     for (SymbolVersion &Ver : V.Globals)
 755       assignWildcardVersion(Ver, V.Id);
 756
 757   // Symbol themselves might know their versions because symbols
 758   // can contain versions in the form of <name>@<version>.
 759   // Let them parse and update their names to exclude version suffix.
 760   for (Symbol *Sym : SymVector)
 761     Sym->parseSymbolVersion();
 762 }
 763
 764 template void SymbolTable::addFile<ELF32LE>(InputFile *);
 765 template void SymbolTable::addFile<ELF32BE>(InputFile *);
 766 template void SymbolTable::addFile<ELF64LE>(InputFile *);
 767 template void SymbolTable::addFile<ELF64BE>(InputFile *);
 768
 769 template Symbol *SymbolTable::addUndefined<ELF32LE>(StringRef, uint8_t, uint8_t,
 770                                                     uint8_t, bool, InputFile *);
 771 template Symbol *SymbolTable::addUndefined<ELF32BE>(StringRef, uint8_t, uint8_t,
 772                                                     uint8_t, bool, InputFile *);
 773 template Symbol *SymbolTable::addUndefined<ELF64LE>(StringRef, uint8_t, uint8_t,
 774                                                     uint8_t, bool, InputFile *);
 775 template Symbol *SymbolTable::addUndefined<ELF64BE>(StringRef, uint8_t, uint8_t,
 776                                                     uint8_t, bool, InputFile *);
 777
 778 template void SymbolTable::addCombinedLTOObject<ELF32LE>();
 779 template void SymbolTable::addCombinedLTOObject<ELF32BE>();
 780 template void SymbolTable::addCombinedLTOObject<ELF64LE>();
 781 template void SymbolTable::addCombinedLTOObject<ELF64BE>();
 782
 783 template void
 784 SymbolTable::addLazyArchive<ELF32LE>(StringRef, ArchiveFile &,
 785                                      const object::Archive::Symbol);
 786 template void
 787 SymbolTable::addLazyArchive<ELF32BE>(StringRef, ArchiveFile &,
 788                                      const object::Archive::Symbol);
 789 template void
 790 SymbolTable::addLazyArchive<ELF64LE>(StringRef, ArchiveFile &,
 791                                      const object::Archive::Symbol);
 792 template void
 793 SymbolTable::addLazyArchive<ELF64BE>(StringRef, ArchiveFile &,
 794                                      const object::Archive::Symbol);
 795
 796 template void SymbolTable::addLazyObject<ELF32LE>(StringRef, LazyObjFile &);
 797 template void SymbolTable::addLazyObject<ELF32BE>(StringRef, LazyObjFile &);
 798 template void SymbolTable::addLazyObject<ELF64LE>(StringRef, LazyObjFile &);
 799 template void SymbolTable::addLazyObject<ELF64BE>(StringRef, LazyObjFile &);
 800
 801 template void SymbolTable::fetchLazy<ELF32LE>(Symbol *);
 802 template void SymbolTable::fetchLazy<ELF32BE>(Symbol *);
 803 template void SymbolTable::fetchLazy<ELF64LE>(Symbol *);
 804 template void SymbolTable::fetchLazy<ELF64BE>(Symbol *);
 805
 806 template void SymbolTable::addShared<ELF32LE>(StringRef, SharedFile<ELF32LE> &,
 807                                               const typename ELF32LE::Sym &,
 808                                               uint32_t Alignment, uint32_t);
 809 template void SymbolTable::addShared<ELF32BE>(StringRef, SharedFile<ELF32BE> &,
 810                                               const typename ELF32BE::Sym &,
 811                                               uint32_t Alignment, uint32_t);
 812 template void SymbolTable::addShared<ELF64LE>(StringRef, SharedFile<ELF64LE> &,
 813                                               const typename ELF64LE::Sym &,
 814                                               uint32_t Alignment, uint32_t);
 815 template void SymbolTable::addShared<ELF64BE>(StringRef, SharedFile<ELF64BE> &,
 816                                               const typename ELF64BE::Sym &,
 817                                               uint32_t Alignment, uint32_t);