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