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 nullptr;
  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     F->parse<ELFT>();
  86     return;
  87   }
  88
  89   if (Config->Trace)
  90     message(toString(File));
  91
  92   // .so file
  93   if (auto *F = dyn_cast<SharedFile<ELFT>>(File)) {
  94     // DSOs are uniquified not by filename but by soname.
  95     F->parseSoName();
  96     if (errorCount() || !SoNames.insert(F->SoName).second)
  97       return;
  98     SharedFiles.push_back(F);
  99     F->parseRest();
 100     return;
 101   }
 102
 103   // LLVM bitcode file
 104   if (auto *F = dyn_cast<BitcodeFile>(File)) {
 105     BitcodeFiles.push_back(F);
 106     F->parse<ELFT>(ComdatGroups);
 107     return;
 108   }
 109
 110   // Regular object file
 111   ObjectFiles.push_back(File);
 112   cast<ObjFile<ELFT>>(File)->parse(ComdatGroups);
 113 }
 114
 115 // This function is where all the optimizations of link-time
 116 // optimization happens. When LTO is in use, some input files are
 117 // not in native object file format but in the LLVM bitcode format.
 118 // This function compiles bitcode files into a few big native files
 119 // using LLVM functions and replaces bitcode symbols with the results.
 120 // Because all bitcode files that consist of a program are passed
 121 // to the compiler at once, it can do whole-program optimization.
 122 template <class ELFT> void SymbolTable::addCombinedLTOObject() {
 123   if (BitcodeFiles.empty())
 124     return;
 125
 126   // Compile bitcode files and replace bitcode symbols.
 127   LTO.reset(new BitcodeCompiler);
 128   for (BitcodeFile *F : BitcodeFiles)
 129     LTO->add(*F);
 130
 131   for (InputFile *File : LTO->compile()) {
 132     DenseSet<CachedHashStringRef> DummyGroups;
 133     auto *Obj = cast<ObjFile<ELFT>>(File);
 134     Obj->parse(DummyGroups);
 135     for (Symbol *Sym : Obj->getGlobalSymbols())
 136       Sym->parseSymbolVersion();
 137     ObjectFiles.push_back(File);
 138   }
 139 }
 140
 141 Defined *SymbolTable::addAbsolute(StringRef Name, uint8_t Visibility,
 142                                   uint8_t Binding) {
 143   Symbol *Sym =
 144       addRegular(Name, Visibility, STT_NOTYPE, 0, 0, Binding, nullptr, nullptr);
 145   return cast<Defined>(Sym);
 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 void SymbolTable::trace(StringRef Name) {
 151   SymMap.insert({CachedHashStringRef(Name), -1});
 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::addSymbolWrap(StringRef Name) {
 157   Symbol *Sym = find(Name);
 158   if (!Sym)
 159     return;
 160   Symbol *Real = addUndefined<ELFT>(Saver.save("__real_" + Name));
 161   Symbol *Wrap = addUndefined<ELFT>(Saver.save("__wrap_" + Name));
 162   WrappedSymbols.push_back({Sym, Real, Wrap});
 163
 164   // We want to tell LTO not to inline symbols to be overwritten
 165   // because LTO doesn't know the final symbol contents after renaming.
 166   Real->CanInline = false;
 167   Sym->CanInline = false;
 168
 169   // Tell LTO not to eliminate these symbols.
 170   Sym->IsUsedInRegularObj = true;
 171   Wrap->IsUsedInRegularObj = true;
 172 }
 173
 174 // Apply symbol renames created by -wrap. The renames are created
 175 // before LTO in addSymbolWrap() to have a chance to inform LTO (if
 176 // LTO is running) not to include these symbols in IPO. Now that the
 177 // symbols are finalized, we can perform the replacement.
 178 void SymbolTable::applySymbolWrap() {
 179   // This function rotates 3 symbols:
 180   //
 181   // __real_sym becomes sym
 182   // sym        becomes __wrap_sym
 183   // __wrap_sym becomes __real_sym
 184   //
 185   // The last part is special in that we don't want to change what references to
 186   // __wrap_sym point to, we just want have __real_sym in the symbol table.
 187
 188   for (WrappedSymbol &W : WrappedSymbols) {
 189     // First, make a copy of __real_sym.
 190     Symbol *Real = nullptr;
 191     if (W.Real->isDefined()) {
 192       Real = (Symbol *)make<SymbolUnion>();
 193       memcpy(Real, W.Real, sizeof(SymbolUnion));
 194     }
 195
 196     // Replace __real_sym with sym and sym with __wrap_sym.
 197     memcpy(W.Real, W.Sym, sizeof(SymbolUnion));
 198     memcpy(W.Sym, W.Wrap, sizeof(SymbolUnion));
 199
 200     // We now have two copies of __wrap_sym. Drop one.
 201     W.Wrap->IsUsedInRegularObj = false;
 202
 203     if (Real)
 204       SymVector.push_back(Real);
 205   }
 206 }
 207
 208 static uint8_t getMinVisibility(uint8_t VA, uint8_t VB) {
 209   if (VA == STV_DEFAULT)
 210     return VB;
 211   if (VB == STV_DEFAULT)
 212     return VA;
 213   return std::min(VA, VB);
 214 }
 215
 216 // Find an existing symbol or create and insert a new one.
 217 std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name) {
 218   // <name>@@<version> means the symbol is the default version. In that
 219   // case <name>@@<version> will be used to resolve references to <name>.
 220   //
 221   // Since this is a hot path, the following string search code is
 222   // optimized for speed. StringRef::find(char) is much faster than
 223   // StringRef::find(StringRef).
 224   size_t Pos = Name.find('@');
 225   if (Pos != StringRef::npos && Pos + 1 < Name.size() && Name[Pos + 1] == '@')
 226     Name = Name.take_front(Pos);
 227
 228   auto P = SymMap.insert({CachedHashStringRef(Name), (int)SymVector.size()});
 229   int &SymIndex = P.first->second;
 230   bool IsNew = P.second;
 231   bool Traced = false;
 232
 233   if (SymIndex == -1) {
 234     SymIndex = SymVector.size();
 235     IsNew = Traced = true;
 236   }
 237
 238   Symbol *Sym;
 239   if (IsNew) {
 240     Sym = (Symbol *)make<SymbolUnion>();
 241     Sym->InVersionScript = false;
 242     Sym->Visibility = STV_DEFAULT;
 243     Sym->IsUsedInRegularObj = false;
 244     Sym->ExportDynamic = false;
 245     Sym->CanInline = true;
 246     Sym->Traced = Traced;
 247     Sym->VersionId = Config->DefaultSymbolVersion;
 248     SymVector.push_back(Sym);
 249   } else {
 250     Sym = SymVector[SymIndex];
 251   }
 252   return {Sym, IsNew};
 253 }
 254
 255 // Find an existing symbol or create and insert a new one, then apply the given
 256 // attributes.
 257 std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name, uint8_t Type,
 258                                               uint8_t Visibility,
 259                                               bool CanOmitFromDynSym,
 260                                               InputFile *File) {
 261   Symbol *S;
 262   bool WasInserted;
 263   std::tie(S, WasInserted) = insert(Name);
 264
 265   // Merge in the new symbol's visibility.
 266   S->Visibility = getMinVisibility(S->Visibility, Visibility);
 267
 268   if (!CanOmitFromDynSym && (Config->Shared || Config->ExportDynamic))
 269     S->ExportDynamic = true;
 270
 271   if (!File || File->kind() == InputFile::ObjKind)
 272     S->IsUsedInRegularObj = true;
 273
 274   if (!WasInserted && S->Type != Symbol::UnknownType &&
 275       ((Type == STT_TLS) != S->isTls())) {
 276     error("TLS attribute mismatch: " + toString(*S) + "\n>>> defined in " +
 277           toString(S->File) + "\n>>> defined in " + toString(File));
 278   }
 279
 280   return {S, WasInserted};
 281 }
 282
 283 template <class ELFT> Symbol *SymbolTable::addUndefined(StringRef Name) {
 284   return addUndefined<ELFT>(Name, STB_GLOBAL, STV_DEFAULT,
 285                             /*Type*/ 0,
 286                             /*CanOmitFromDynSym*/ false, /*File*/ nullptr);
 287 }
 288
 289 static uint8_t getVisibility(uint8_t StOther) { return StOther & 3; }
 290
 291 template <class ELFT>
 292 Symbol *SymbolTable::addUndefined(StringRef Name, uint8_t Binding,
 293                                   uint8_t StOther, uint8_t Type,
 294                                   bool CanOmitFromDynSym, InputFile *File) {
 295   Symbol *S;
 296   bool WasInserted;
 297   uint8_t Visibility = getVisibility(StOther);
 298   std::tie(S, WasInserted) =
 299       insert(Name, Type, Visibility, CanOmitFromDynSym, File);
 300   // An undefined symbol with non default visibility must be satisfied
 301   // in the same DSO.
 302   if (WasInserted || (isa<SharedSymbol>(S) && Visibility != STV_DEFAULT)) {
 303     replaceSymbol<Undefined>(S, File, Name, Binding, StOther, Type);
 304     return S;
 305   }
 306   if (S->isShared() || S->isLazy() || (S->isUndefined() && Binding != STB_WEAK))
 307     S->Binding = Binding;
 308   if (Binding != STB_WEAK) {
 309     if (auto *SS = dyn_cast<SharedSymbol>(S))
 310       if (!Config->GcSections)
 311         SS->getFile<ELFT>().IsNeeded = true;
 312   }
 313   if (auto *L = dyn_cast<Lazy>(S)) {
 314     // An undefined weak will not fetch archive members. See comment on Lazy in
 315     // Symbols.h for the details.
 316     if (Binding == STB_WEAK)
 317       L->Type = Type;
 318     else if (InputFile *F = L->fetch())
 319       addFile<ELFT>(F);
 320   }
 321   return S;
 322 }
 323
 324 // Using .symver foo,foo@@VER unfortunately creates two symbols: foo and
 325 // foo@@VER. We want to effectively ignore foo, so give precedence to
 326 // foo@@VER.
 327 // FIXME: If users can transition to using
 328 // .symver foo,foo@@@VER
 329 // we can delete this hack.
 330 static int compareVersion(Symbol *S, StringRef Name) {
 331   bool A = Name.contains("@@");
 332   bool B = S->getName().contains("@@");
 333   if (A && !B)
 334     return 1;
 335   if (!A && B)
 336     return -1;
 337   return 0;
 338 }
 339
 340 // We have a new defined symbol with the specified binding. Return 1 if the new
 341 // symbol should win, -1 if the new symbol should lose, or 0 if both symbols are
 342 // strong defined symbols.
 343 static int compareDefined(Symbol *S, bool WasInserted, uint8_t Binding,
 344                           StringRef Name) {
 345   if (WasInserted)
 346     return 1;
 347   if (!S->isDefined())
 348     return 1;
 349   if (int R = compareVersion(S, Name))
 350     return R;
 351   if (Binding == STB_WEAK)
 352     return -1;
 353   if (S->isWeak())
 354     return 1;
 355   return 0;
 356 }
 357
 358 // We have a new non-common defined symbol with the specified binding. Return 1
 359 // if the new symbol should win, -1 if the new symbol should lose, or 0 if there
 360 // is a conflict. If the new symbol wins, also update the binding.
 361 static int compareDefinedNonCommon(Symbol *S, bool WasInserted, uint8_t Binding,
 362                                    bool IsAbsolute, uint64_t Value,
 363                                    StringRef Name) {
 364   if (int Cmp = compareDefined(S, WasInserted, Binding, Name))
 365     return Cmp;
 366   if (auto *R = dyn_cast<Defined>(S)) {
 367     if (R->Section && isa<BssSection>(R->Section)) {
 368       // Non-common symbols take precedence over common symbols.
 369       if (Config->WarnCommon)
 370         warn("common " + S->getName() + " is overridden");
 371       return 1;
 372     }
 373     if (R->Section == nullptr && Binding == STB_GLOBAL && IsAbsolute &&
 374         R->Value == Value)
 375       return -1;
 376   }
 377   return 0;
 378 }
 379
 380 Symbol *SymbolTable::addCommon(StringRef N, uint64_t Size, uint32_t Alignment,
 381                                uint8_t Binding, uint8_t StOther, uint8_t Type,
 382                                InputFile &File) {
 383   Symbol *S;
 384   bool WasInserted;
 385   std::tie(S, WasInserted) = insert(N, Type, getVisibility(StOther),
 386                                     /*CanOmitFromDynSym*/ false, &File);
 387   int Cmp = compareDefined(S, WasInserted, Binding, N);
 388   if (Cmp > 0) {
 389     auto *Bss = make<BssSection>("COMMON", Size, Alignment);
 390     Bss->File = &File;
 391     Bss->Live = !Config->GcSections;
 392     InputSections.push_back(Bss);
 393
 394     replaceSymbol<Defined>(S, &File, N, Binding, StOther, Type, 0, Size, Bss);
 395   } else if (Cmp == 0) {
 396     auto *D = cast<Defined>(S);
 397     auto *Bss = dyn_cast_or_null<BssSection>(D->Section);
 398     if (!Bss) {
 399       // Non-common symbols take precedence over common symbols.
 400       if (Config->WarnCommon)
 401         warn("common " + S->getName() + " is overridden");
 402       return S;
 403     }
 404
 405     if (Config->WarnCommon)
 406       warn("multiple common of " + D->getName());
 407
 408     Bss->Alignment = std::max(Bss->Alignment, Alignment);
 409     if (Size > Bss->Size) {
 410       D->File = Bss->File = &File;
 411       D->Size = Bss->Size = Size;
 412     }
 413   }
 414   return S;
 415 }
 416
 417 static void warnOrError(const Twine &Msg) {
 418   if (Config->AllowMultipleDefinition)
 419     warn(Msg);
 420   else
 421     error(Msg);
 422 }
 423
 424 static void reportDuplicate(Symbol *Sym, InputFile *NewFile) {
 425   warnOrError("duplicate symbol: " + toString(*Sym) + "\n>>> defined in " +
 426               toString(Sym->File) + "\n>>> defined in " + toString(NewFile));
 427 }
 428
 429 static void reportDuplicate(Symbol *Sym, InputSectionBase *ErrSec,
 430                             uint64_t ErrOffset) {
 431   Defined *D = cast<Defined>(Sym);
 432   if (!D->Section || !ErrSec) {
 433     reportDuplicate(Sym, ErrSec ? ErrSec->File : nullptr);
 434     return;
 435   }
 436
 437   // Construct and print an error message in the form of:
 438   //
 439   //   ld.lld: error: duplicate symbol: foo
 440   //   >>> defined at bar.c:30
 441   //   >>>            bar.o (/home/alice/src/bar.o)
 442   //   >>> defined at baz.c:563
 443   //   >>>            baz.o in archive libbaz.a
 444   auto *Sec1 = cast<InputSectionBase>(D->Section);
 445   std::string Src1 = Sec1->getSrcMsg(*Sym, D->Value);
 446   std::string Obj1 = Sec1->getObjMsg(D->Value);
 447   std::string Src2 = ErrSec->getSrcMsg(*Sym, ErrOffset);
 448   std::string Obj2 = ErrSec->getObjMsg(ErrOffset);
 449
 450   std::string Msg = "duplicate symbol: " + toString(*Sym) + "\n>>> defined at ";
 451   if (!Src1.empty())
 452     Msg += Src1 + "\n>>>            ";
 453   Msg += Obj1 + "\n>>> defined at ";
 454   if (!Src2.empty())
 455     Msg += Src2 + "\n>>>            ";
 456   Msg += Obj2;
 457   warnOrError(Msg);
 458 }
 459
 460 Symbol *SymbolTable::addRegular(StringRef Name, uint8_t StOther, uint8_t Type,
 461                                 uint64_t Value, uint64_t Size, uint8_t Binding,
 462                                 SectionBase *Section, InputFile *File) {
 463   Symbol *S;
 464   bool WasInserted;
 465   std::tie(S, WasInserted) = insert(Name, Type, getVisibility(StOther),
 466                                     /*CanOmitFromDynSym*/ false, File);
 467   int Cmp = compareDefinedNonCommon(S, WasInserted, Binding, Section == nullptr,
 468                                     Value, Name);
 469   if (Cmp > 0)
 470     replaceSymbol<Defined>(S, File, Name, Binding, StOther, Type, Value, Size,
 471                            Section);
 472   else if (Cmp == 0)
 473     reportDuplicate(S, dyn_cast_or_null<InputSectionBase>(Section), Value);
 474   return S;
 475 }
 476
 477 template <typename ELFT>
 478 void SymbolTable::addShared(StringRef Name, SharedFile<ELFT> &File,
 479                             const typename ELFT::Sym &Sym, uint32_t Alignment,
 480                             uint32_t VerdefIndex) {
 481   // DSO symbols do not affect visibility in the output, so we pass STV_DEFAULT
 482   // as the visibility, which will leave the visibility in the symbol table
 483   // unchanged.
 484   Symbol *S;
 485   bool WasInserted;
 486   std::tie(S, WasInserted) = insert(Name, Sym.getType(), STV_DEFAULT,
 487                                     /*CanOmitFromDynSym*/ true, &File);
 488   // Make sure we preempt DSO symbols with default visibility.
 489   if (Sym.getVisibility() == STV_DEFAULT)
 490     S->ExportDynamic = true;
 491
 492   // An undefined symbol with non default visibility must be satisfied
 493   // in the same DSO.
 494   if (WasInserted || ((S->isUndefined() || S->isLazy()) &&
 495                       S->getVisibility() == STV_DEFAULT)) {
 496     uint8_t Binding = S->Binding;
 497     bool WasUndefined = S->isUndefined();
 498     replaceSymbol<SharedSymbol>(S, File, Name, Sym.getBinding(), Sym.st_other,
 499                                 Sym.getType(), Sym.st_value, Sym.st_size,
 500                                 Alignment, VerdefIndex);
 501     if (!WasInserted) {
 502       S->Binding = Binding;
 503       if (!S->isWeak() && !Config->GcSections && WasUndefined)
 504         File.IsNeeded = true;
 505     }
 506   }
 507 }
 508
 509 Symbol *SymbolTable::addBitcode(StringRef Name, uint8_t Binding,
 510                                 uint8_t StOther, uint8_t Type,
 511                                 bool CanOmitFromDynSym, BitcodeFile &F) {
 512   Symbol *S;
 513   bool WasInserted;
 514   std::tie(S, WasInserted) =
 515       insert(Name, Type, getVisibility(StOther), CanOmitFromDynSym, &F);
 516   int Cmp = compareDefinedNonCommon(S, WasInserted, Binding,
 517                                     /*IsAbs*/ false, /*Value*/ 0, Name);
 518   if (Cmp > 0)
 519     replaceSymbol<Defined>(S, &F, Name, Binding, StOther, Type, 0, 0, nullptr);
 520   else if (Cmp == 0)
 521     reportDuplicate(S, &F);
 522   return S;
 523 }
 524
 525 Symbol *SymbolTable::find(StringRef Name) {
 526   auto It = SymMap.find(CachedHashStringRef(Name));
 527   if (It == SymMap.end())
 528     return nullptr;
 529   if (It->second == -1)
 530     return nullptr;
 531   return SymVector[It->second];
 532 }
 533
 534 template <class ELFT>
 535 Symbol *SymbolTable::addLazyArchive(StringRef Name, ArchiveFile &F,
 536                                     const object::Archive::Symbol Sym) {
 537   Symbol *S;
 538   bool WasInserted;
 539   std::tie(S, WasInserted) = insert(Name);
 540   if (WasInserted) {
 541     replaceSymbol<LazyArchive>(S, F, Sym, Symbol::UnknownType);
 542     return S;
 543   }
 544   if (!S->isUndefined())
 545     return S;
 546
 547   // An undefined weak will not fetch archive members. See comment on Lazy in
 548   // Symbols.h for the details.
 549   if (S->isWeak()) {
 550     replaceSymbol<LazyArchive>(S, F, Sym, S->Type);
 551     S->Binding = STB_WEAK;
 552     return S;
 553   }
 554   std::pair<MemoryBufferRef, uint64_t> MBInfo = F.getMember(&Sym);
 555   if (!MBInfo.first.getBuffer().empty())
 556     addFile<ELFT>(createObjectFile(MBInfo.first, F.getName(), MBInfo.second));
 557   return S;
 558 }
 559
 560 template <class ELFT>
 561 void SymbolTable::addLazyObject(StringRef Name, LazyObjFile &Obj) {
 562   Symbol *S;
 563   bool WasInserted;
 564   std::tie(S, WasInserted) = insert(Name);
 565   if (WasInserted) {
 566     replaceSymbol<LazyObject>(S, Obj, Name, Symbol::UnknownType);
 567     return;
 568   }
 569   if (!S->isUndefined())
 570     return;
 571
 572   // See comment for addLazyArchive above.
 573   if (S->isWeak())
 574     replaceSymbol<LazyObject>(S, Obj, Name, S->Type);
 575   else if (InputFile *F = Obj.fetch())
 576     addFile<ELFT>(F);
 577 }
 578
 579 // If we already saw this symbol, force loading its file.
 580 template <class ELFT> void SymbolTable::fetchIfLazy(StringRef Name) {
 581   if (Symbol *B = find(Name)) {
 582     // Mark the symbol not to be eliminated by LTO
 583     // even if it is a bitcode symbol.
 584     B->IsUsedInRegularObj = true;
 585     if (auto *L = dyn_cast<Lazy>(B))
 586       if (InputFile *File = L->fetch())
 587         addFile<ELFT>(File);
 588   }
 589 }
 590
 591 // This function takes care of the case in which shared libraries depend on
 592 // the user program (not the other way, which is usual). Shared libraries
 593 // may have undefined symbols, expecting that the user program provides
 594 // the definitions for them. An example is BSD's __progname symbol.
 595 // We need to put such symbols to the main program's .dynsym so that
 596 // shared libraries can find them.
 597 // Except this, we ignore undefined symbols in DSOs.
 598 template <class ELFT> void SymbolTable::scanShlibUndefined() {
 599   for (InputFile *F : SharedFiles) {
 600     for (StringRef U : cast<SharedFile<ELFT>>(F)->getUndefinedSymbols()) {
 601       Symbol *Sym = find(U);
 602       if (!Sym || !Sym->isDefined())
 603         continue;
 604       Sym->ExportDynamic = true;
 605
 606       // If -dynamic-list is given, the default version is set to
 607       // VER_NDX_LOCAL, which prevents a symbol to be exported via .dynsym.
 608       // Set to VER_NDX_GLOBAL so the symbol will be handled as if it were
 609       // specified by -dynamic-list.
 610       Sym->VersionId = VER_NDX_GLOBAL;
 611     }
 612   }
 613 }
 614
 615 // Initialize DemangledSyms with a map from demangled symbols to symbol
 616 // objects. Used to handle "extern C++" directive in version scripts.
 617 //
 618 // The map will contain all demangled symbols. That can be very large,
 619 // and in LLD we generally want to avoid do anything for each symbol.
 620 // Then, why are we doing this? Here's why.
 621 //
 622 // Users can use "extern C++ {}" directive to match against demangled
 623 // C++ symbols. For example, you can write a pattern such as
 624 // "llvm::*::foo(int, ?)". Obviously, there's no way to handle this
 625 // other than trying to match a pattern against all demangled symbols.
 626 // So, if "extern C++" feature is used, we need to demangle all known
 627 // symbols.
 628 StringMap<std::vector<Symbol *>> &SymbolTable::getDemangledSyms() {
 629   if (!DemangledSyms) {
 630     DemangledSyms.emplace();
 631     for (Symbol *Sym : SymVector) {
 632       if (!Sym->isDefined())
 633         continue;
 634       if (Optional<std::string> S = demangleItanium(Sym->getName()))
 635         (*DemangledSyms)[*S].push_back(Sym);
 636       else
 637         (*DemangledSyms)[Sym->getName()].push_back(Sym);
 638     }
 639   }
 640   return *DemangledSyms;
 641 }
 642
 643 std::vector<Symbol *> SymbolTable::findByVersion(SymbolVersion Ver) {
 644   if (Ver.IsExternCpp)
 645     return getDemangledSyms().lookup(Ver.Name);
 646   if (Symbol *B = find(Ver.Name))
 647     if (B->isDefined())
 648       return {B};
 649   return {};
 650 }
 651
 652 std::vector<Symbol *> SymbolTable::findAllByVersion(SymbolVersion Ver) {
 653   std::vector<Symbol *> Res;
 654   StringMatcher M(Ver.Name);
 655
 656   if (Ver.IsExternCpp) {
 657     for (auto &P : getDemangledSyms())
 658       if (M.match(P.first()))
 659         Res.insert(Res.end(), P.second.begin(), P.second.end());
 660     return Res;
 661   }
 662
 663   for (Symbol *Sym : SymVector)
 664     if (Sym->isDefined() && M.match(Sym->getName()))
 665       Res.push_back(Sym);
 666   return Res;
 667 }
 668
 669 // If there's only one anonymous version definition in a version
 670 // script file, the script does not actually define any symbol version,
 671 // but just specifies symbols visibilities.
 672 void SymbolTable::handleAnonymousVersion() {
 673   for (SymbolVersion &Ver : Config->VersionScriptGlobals)
 674     assignExactVersion(Ver, VER_NDX_GLOBAL, "global");
 675   for (SymbolVersion &Ver : Config->VersionScriptGlobals)
 676     assignWildcardVersion(Ver, VER_NDX_GLOBAL);
 677   for (SymbolVersion &Ver : Config->VersionScriptLocals)
 678     assignExactVersion(Ver, VER_NDX_LOCAL, "local");
 679   for (SymbolVersion &Ver : Config->VersionScriptLocals)
 680     assignWildcardVersion(Ver, VER_NDX_LOCAL);
 681 }
 682
 683 // Handles -dynamic-list.
 684 void SymbolTable::handleDynamicList() {
 685   for (SymbolVersion &Ver : Config->DynamicList) {
 686     std::vector<Symbol *> Syms;
 687     if (Ver.HasWildcard)
 688       Syms = findAllByVersion(Ver);
 689     else
 690       Syms = findByVersion(Ver);
 691
 692     for (Symbol *B : Syms) {
 693       if (!Config->Shared)
 694         B->ExportDynamic = true;
 695       else if (B->includeInDynsym())
 696         B->IsPreemptible = true;
 697     }
 698   }
 699 }
 700
 701 // Set symbol versions to symbols. This function handles patterns
 702 // containing no wildcard characters.
 703 void SymbolTable::assignExactVersion(SymbolVersion Ver, uint16_t VersionId,
 704                                      StringRef VersionName) {
 705   if (Ver.HasWildcard)
 706     return;
 707
 708   // Get a list of symbols which we need to assign the version to.
 709   std::vector<Symbol *> Syms = findByVersion(Ver);
 710   if (Syms.empty()) {
 711     if (Config->NoUndefinedVersion)
 712       error("version script assignment of '" + VersionName + "' to symbol '" +
 713             Ver.Name + "' failed: symbol not defined");
 714     return;
 715   }
 716
 717   // Assign the version.
 718   for (Symbol *Sym : Syms) {
 719     // Skip symbols containing version info because symbol versions
 720     // specified by symbol names take precedence over version scripts.
 721     // See parseSymbolVersion().
 722     if (Sym->getName().contains('@'))
 723       continue;
 724
 725     if (Sym->InVersionScript)
 726       warn("duplicate symbol '" + Ver.Name + "' in version script");
 727     Sym->VersionId = VersionId;
 728     Sym->InVersionScript = true;
 729   }
 730 }
 731
 732 void SymbolTable::assignWildcardVersion(SymbolVersion Ver, uint16_t VersionId) {
 733   if (!Ver.HasWildcard)
 734     return;
 735
 736   // Exact matching takes precendence over fuzzy matching,
 737   // so we set a version to a symbol only if no version has been assigned
 738   // to the symbol. This behavior is compatible with GNU.
 739   for (Symbol *B : findAllByVersion(Ver))
 740     if (B->VersionId == Config->DefaultSymbolVersion)
 741       B->VersionId = VersionId;
 742 }
 743
 744 // This function processes version scripts by updating VersionId
 745 // member of symbols.
 746 void SymbolTable::scanVersionScript() {
 747   // Handle edge cases first.
 748   handleAnonymousVersion();
 749   handleDynamicList();
 750
 751   // Now we have version definitions, so we need to set version ids to symbols.
 752   // Each version definition has a glob pattern, and all symbols that match
 753   // with the pattern get that version.
 754
 755   // First, we assign versions to exact matching symbols,
 756   // i.e. version definitions not containing any glob meta-characters.
 757   for (VersionDefinition &V : Config->VersionDefinitions)
 758     for (SymbolVersion &Ver : V.Globals)
 759       assignExactVersion(Ver, V.Id, V.Name);
 760
 761   // Next, we assign versions to fuzzy matching symbols,
 762   // i.e. version definitions containing glob meta-characters.
 763   // Note that because the last match takes precedence over previous matches,
 764   // we iterate over the definitions in the reverse order.
 765   for (VersionDefinition &V : llvm::reverse(Config->VersionDefinitions))
 766     for (SymbolVersion &Ver : V.Globals)
 767       assignWildcardVersion(Ver, V.Id);
 768
 769   // Symbol themselves might know their versions because symbols
 770   // can contain versions in the form of <name>@<version>.
 771   // Let them parse and update their names to exclude version suffix.
 772   for (Symbol *Sym : SymVector)
 773     Sym->parseSymbolVersion();
 774 }
 775
 776 template void SymbolTable::addSymbolWrap<ELF32LE>(StringRef);
 777 template void SymbolTable::addSymbolWrap<ELF32BE>(StringRef);
 778 template void SymbolTable::addSymbolWrap<ELF64LE>(StringRef);
 779 template void SymbolTable::addSymbolWrap<ELF64BE>(StringRef);
 780
 781 template Symbol *SymbolTable::addUndefined<ELF32LE>(StringRef);
 782 template Symbol *SymbolTable::addUndefined<ELF32BE>(StringRef);
 783 template Symbol *SymbolTable::addUndefined<ELF64LE>(StringRef);
 784 template Symbol *SymbolTable::addUndefined<ELF64BE>(StringRef);
 785
 786 template Symbol *SymbolTable::addUndefined<ELF32LE>(StringRef, uint8_t, uint8_t,
 787                                                     uint8_t, bool, InputFile *);
 788 template Symbol *SymbolTable::addUndefined<ELF32BE>(StringRef, uint8_t, uint8_t,
 789                                                     uint8_t, bool, InputFile *);
 790 template Symbol *SymbolTable::addUndefined<ELF64LE>(StringRef, uint8_t, uint8_t,
 791                                                     uint8_t, bool, InputFile *);
 792 template Symbol *SymbolTable::addUndefined<ELF64BE>(StringRef, uint8_t, uint8_t,
 793                                                     uint8_t, bool, InputFile *);
 794
 795 template void SymbolTable::addCombinedLTOObject<ELF32LE>();
 796 template void SymbolTable::addCombinedLTOObject<ELF32BE>();
 797 template void SymbolTable::addCombinedLTOObject<ELF64LE>();
 798 template void SymbolTable::addCombinedLTOObject<ELF64BE>();
 799
 800 template Symbol *
 801 SymbolTable::addLazyArchive<ELF32LE>(StringRef, ArchiveFile &,
 802                                      const object::Archive::Symbol);
 803 template Symbol *
 804 SymbolTable::addLazyArchive<ELF32BE>(StringRef, ArchiveFile &,
 805                                      const object::Archive::Symbol);
 806 template Symbol *
 807 SymbolTable::addLazyArchive<ELF64LE>(StringRef, ArchiveFile &,
 808                                      const object::Archive::Symbol);
 809 template Symbol *
 810 SymbolTable::addLazyArchive<ELF64BE>(StringRef, ArchiveFile &,
 811                                      const object::Archive::Symbol);
 812
 813 template void SymbolTable::addLazyObject<ELF32LE>(StringRef, LazyObjFile &);
 814 template void SymbolTable::addLazyObject<ELF32BE>(StringRef, LazyObjFile &);
 815 template void SymbolTable::addLazyObject<ELF64LE>(StringRef, LazyObjFile &);
 816 template void SymbolTable::addLazyObject<ELF64BE>(StringRef, LazyObjFile &);
 817
 818 template void SymbolTable::addShared<ELF32LE>(StringRef, SharedFile<ELF32LE> &,
 819                                               const typename ELF32LE::Sym &,
 820                                               uint32_t Alignment, uint32_t);
 821 template void SymbolTable::addShared<ELF32BE>(StringRef, SharedFile<ELF32BE> &,
 822                                               const typename ELF32BE::Sym &,
 823                                               uint32_t Alignment, uint32_t);
 824 template void SymbolTable::addShared<ELF64LE>(StringRef, SharedFile<ELF64LE> &,
 825                                               const typename ELF64LE::Sym &,
 826                                               uint32_t Alignment, uint32_t);
 827 template void SymbolTable::addShared<ELF64BE>(StringRef, SharedFile<ELF64BE> &,
 828                                               const typename ELF64BE::Sym &,
 829                                               uint32_t Alignment, uint32_t);
 830
 831 template void SymbolTable::fetchIfLazy<ELF32LE>(StringRef);
 832 template void SymbolTable::fetchIfLazy<ELF32BE>(StringRef);
 833 template void SymbolTable::fetchIfLazy<ELF64LE>(StringRef);
 834 template void SymbolTable::fetchIfLazy<ELF64BE>(StringRef);
 835
 836 template void SymbolTable::scanShlibUndefined<ELF32LE>();
 837 template void SymbolTable::scanShlibUndefined<ELF32BE>();
 838 template void SymbolTable::scanShlibUndefined<ELF64LE>();
 839 template void SymbolTable::scanShlibUndefined<ELF64BE>();