lld/COFF/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 #include "SymbolTable.h"
  11 #include "Config.h"
  12 #include "Driver.h"
  13 #include "Error.h"
  14 #include "LTO.h"
  15 #include "Memory.h"
  16 #include "Symbols.h"
  17 #include "llvm/IR/LLVMContext.h"
  18 #include "llvm/Support/Debug.h"
  19 #include "llvm/Support/raw_ostream.h"
  20 #include <utility>
  21
  22 using namespace llvm;
  23
  24 namespace lld {
  25 namespace coff {
  26
  27 enum SymbolPreference {
  28   SP_EXISTING = -1,
  29   SP_CONFLICT = 0,
  30   SP_NEW = 1,
  31 };
  32
  33 /// Checks if an existing symbol S should be kept or replaced by a new symbol.
  34 /// Returns SP_EXISTING when S should be kept, SP_NEW when the new symbol
  35 /// should be kept, and SP_CONFLICT if no valid resolution exists.
  36 static SymbolPreference compareDefined(Symbol *S, bool WasInserted,
  37                                        bool NewIsCOMDAT) {
  38   // If the symbol wasn't previously known, the new symbol wins by default.
  39   if (WasInserted || !isa<Defined>(S->body()))
  40     return SP_NEW;
  41
  42   // If the existing symbol is a DefinedRegular, both it and the new symbol
  43   // must be comdats. In that case, we have no reason to prefer one symbol
  44   // over the other, and we keep the existing one. If one of the symbols
  45   // is not a comdat, we report a conflict.
  46   if (auto *R = dyn_cast<DefinedRegular>(S->body())) {
  47     if (NewIsCOMDAT && R->isCOMDAT())
  48       return SP_EXISTING;
  49     else
  50       return SP_CONFLICT;
  51   }
  52
  53   // Existing symbol is not a DefinedRegular; new symbol wins.
  54   return SP_NEW;
  55 }
  56
  57 SymbolTable *Symtab;
  58
  59 void SymbolTable::addFile(InputFile *File) {
  60   log("Reading " + toString(File));
  61   File->parse();
  62
  63   MachineTypes MT = File->getMachineType();
  64   if (Config->Machine == IMAGE_FILE_MACHINE_UNKNOWN) {
  65     Config->Machine = MT;
  66   } else if (MT != IMAGE_FILE_MACHINE_UNKNOWN && Config->Machine != MT) {
  67     fatal(toString(File) + ": machine type " + machineToStr(MT) +
  68           " conflicts with " + machineToStr(Config->Machine));
  69   }
  70
  71   if (auto *F = dyn_cast<ObjFile>(File)) {
  72     ObjFile::Instances.push_back(F);
  73   } else if (auto *F = dyn_cast<BitcodeFile>(File)) {
  74     BitcodeFile::Instances.push_back(F);
  75   } else if (auto *F = dyn_cast<ImportFile>(File)) {
  76     ImportFile::Instances.push_back(F);
  77   }
  78
  79   StringRef S = File->getDirectives();
  80   if (S.empty())
  81     return;
  82
  83   log("Directives: " + toString(File) + ": " + S);
  84   Driver->parseDirectives(S);
  85 }
  86
  87 void SymbolTable::reportRemainingUndefines() {
  88   SmallPtrSet<SymbolBody *, 8> Undefs;
  89   for (auto &I : Symtab) {
  90     Symbol *Sym = I.second;
  91     auto *Undef = dyn_cast<Undefined>(Sym->body());
  92     if (!Undef)
  93       continue;
  94     if (!Sym->IsUsedInRegularObj)
  95       continue;
  96     StringRef Name = Undef->getName();
  97     // A weak alias may have been resolved, so check for that.
  98     if (Defined *D = Undef->getWeakAlias()) {
  99       // We resolve weak aliases by replacing the alias's SymbolBody with the
 100       // target's SymbolBody. This causes all SymbolBody pointers referring to
 101       // the old symbol to instead refer to the new symbol. However, we can't
 102       // just blindly copy sizeof(Symbol::Body) bytes from D to Sym->Body
 103       // because D may be an internal symbol, and internal symbols are stored as
 104       // "unparented" SymbolBodies. For that reason we need to check which type
 105       // of symbol we are dealing with and copy the correct number of bytes.
 106       if (isa<DefinedRegular>(D))
 107         memcpy(Sym->Body.buffer, D, sizeof(DefinedRegular));
 108       else if (isa<DefinedAbsolute>(D))
 109         memcpy(Sym->Body.buffer, D, sizeof(DefinedAbsolute));
 110       else
 111         // No other internal symbols are possible.
 112         Sym->Body = D->symbol()->Body;
 113       continue;
 114     }
 115     // If we can resolve a symbol by removing __imp_ prefix, do that.
 116     // This odd rule is for compatibility with MSVC linker.
 117     if (Name.startswith("__imp_")) {
 118       Symbol *Imp = find(Name.substr(strlen("__imp_")));
 119       if (Imp && isa<Defined>(Imp->body())) {
 120         auto *D = cast<Defined>(Imp->body());
 121         replaceBody<DefinedLocalImport>(Sym, Name, D);
 122         LocalImportChunks.push_back(
 123             cast<DefinedLocalImport>(Sym->body())->getChunk());
 124         continue;
 125       }
 126     }
 127     // Remaining undefined symbols are not fatal if /force is specified.
 128     // They are replaced with dummy defined symbols.
 129     if (Config->Force)
 130       replaceBody<DefinedAbsolute>(Sym, Name, 0);
 131     Undefs.insert(Sym->body());
 132   }
 133   if (Undefs.empty())
 134     return;
 135   for (SymbolBody *B : Config->GCRoot)
 136     if (Undefs.count(B))
 137       warn("<root>: undefined symbol: " + B->getName());
 138   for (ObjFile *File : ObjFile::Instances)
 139     for (SymbolBody *Sym : File->getSymbols())
 140       if (Undefs.count(Sym))
 141         warn(toString(File) + ": undefined symbol: " + Sym->getName());
 142   if (!Config->Force)
 143     fatal("link failed");
 144 }
 145
 146 std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name) {
 147   Symbol *&Sym = Symtab[CachedHashStringRef(Name)];
 148   if (Sym)
 149     return {Sym, false};
 150   Sym = make<Symbol>();
 151   Sym->IsUsedInRegularObj = false;
 152   Sym->PendingArchiveLoad = false;
 153   return {Sym, true};
 154 }
 155
 156 Symbol *SymbolTable::addUndefined(StringRef Name, InputFile *F,
 157                                   bool IsWeakAlias) {
 158   Symbol *S;
 159   bool WasInserted;
 160   std::tie(S, WasInserted) = insert(Name);
 161   if (!F || !isa<BitcodeFile>(F))
 162     S->IsUsedInRegularObj = true;
 163   if (WasInserted || (isa<Lazy>(S->body()) && IsWeakAlias)) {
 164     replaceBody<Undefined>(S, Name);
 165     return S;
 166   }
 167   if (auto *L = dyn_cast<Lazy>(S->body())) {
 168     if (!S->PendingArchiveLoad) {
 169       S->PendingArchiveLoad = true;
 170       L->File->addMember(&L->Sym);
 171     }
 172   }
 173   return S;
 174 }
 175
 176 void SymbolTable::addLazy(ArchiveFile *F, const Archive::Symbol Sym) {
 177   StringRef Name = Sym.getName();
 178   Symbol *S;
 179   bool WasInserted;
 180   std::tie(S, WasInserted) = insert(Name);
 181   if (WasInserted) {
 182     replaceBody<Lazy>(S, F, Sym);
 183     return;
 184   }
 185   auto *U = dyn_cast<Undefined>(S->body());
 186   if (!U || U->WeakAlias || S->PendingArchiveLoad)
 187     return;
 188   S->PendingArchiveLoad = true;
 189   F->addMember(&Sym);
 190 }
 191
 192 void SymbolTable::reportDuplicate(Symbol *Existing, InputFile *NewFile) {
 193   error("duplicate symbol: " + toString(*Existing->body()) + " in " +
 194         toString(Existing->body()->getFile()) + " and in " +
 195         (NewFile ? toString(NewFile) : "(internal)"));
 196 }
 197
 198 Symbol *SymbolTable::addAbsolute(StringRef N, COFFSymbolRef Sym) {
 199   Symbol *S;
 200   bool WasInserted;
 201   std::tie(S, WasInserted) = insert(N);
 202   S->IsUsedInRegularObj = true;
 203   if (WasInserted || isa<Undefined>(S->body()) || isa<Lazy>(S->body()))
 204     replaceBody<DefinedAbsolute>(S, N, Sym);
 205   else if (!isa<DefinedCOFF>(S->body()))
 206     reportDuplicate(S, nullptr);
 207   return S;
 208 }
 209
 210 Symbol *SymbolTable::addAbsolute(StringRef N, uint64_t VA) {
 211   Symbol *S;
 212   bool WasInserted;
 213   std::tie(S, WasInserted) = insert(N);
 214   S->IsUsedInRegularObj = true;
 215   if (WasInserted || isa<Undefined>(S->body()) || isa<Lazy>(S->body()))
 216     replaceBody<DefinedAbsolute>(S, N, VA);
 217   else if (!isa<DefinedCOFF>(S->body()))
 218     reportDuplicate(S, nullptr);
 219   return S;
 220 }
 221
 222 Symbol *SymbolTable::addSynthetic(StringRef N, Chunk *C) {
 223   Symbol *S;
 224   bool WasInserted;
 225   std::tie(S, WasInserted) = insert(N);
 226   S->IsUsedInRegularObj = true;
 227   if (WasInserted || isa<Undefined>(S->body()) || isa<Lazy>(S->body()))
 228     replaceBody<DefinedSynthetic>(S, N, C);
 229   else if (!isa<DefinedCOFF>(S->body()))
 230     reportDuplicate(S, nullptr);
 231   return S;
 232 }
 233
 234 Symbol *SymbolTable::addRegular(InputFile *F, StringRef N, bool IsCOMDAT,
 235                                 const coff_symbol_generic *Sym,
 236                                 SectionChunk *C) {
 237   Symbol *S;
 238   bool WasInserted;
 239   std::tie(S, WasInserted) = insert(N);
 240   if (!isa<BitcodeFile>(F))
 241     S->IsUsedInRegularObj = true;
 242   SymbolPreference SP = compareDefined(S, WasInserted, IsCOMDAT);
 243   if (SP == SP_CONFLICT) {
 244     reportDuplicate(S, F);
 245   } else if (SP == SP_NEW) {
 246     replaceBody<DefinedRegular>(S, F, N, IsCOMDAT, /*IsExternal*/ true, Sym, C);
 247   } else if (SP == SP_EXISTING && IsCOMDAT && C) {
 248     C->markDiscarded();
 249     // Discard associative chunks that we've parsed so far. No need to recurse
 250     // because an associative section cannot have children.
 251     for (SectionChunk *Child : C->children())
 252       Child->markDiscarded();
 253   }
 254   return S;
 255 }
 256
 257 Symbol *SymbolTable::addCommon(InputFile *F, StringRef N, uint64_t Size,
 258                                const coff_symbol_generic *Sym, CommonChunk *C) {
 259   Symbol *S;
 260   bool WasInserted;
 261   std::tie(S, WasInserted) = insert(N);
 262   if (!isa<BitcodeFile>(F))
 263     S->IsUsedInRegularObj = true;
 264   if (WasInserted || !isa<DefinedCOFF>(S->body()))
 265     replaceBody<DefinedCommon>(S, F, N, Size, Sym, C);
 266   else if (auto *DC = dyn_cast<DefinedCommon>(S->body()))
 267     if (Size > DC->getSize())
 268       replaceBody<DefinedCommon>(S, F, N, Size, Sym, C);
 269   return S;
 270 }
 271
 272 Symbol *SymbolTable::addImportData(StringRef N, ImportFile *F) {
 273   Symbol *S;
 274   bool WasInserted;
 275   std::tie(S, WasInserted) = insert(N);
 276   S->IsUsedInRegularObj = true;
 277   if (WasInserted || isa<Undefined>(S->body()) || isa<Lazy>(S->body()))
 278     replaceBody<DefinedImportData>(S, N, F);
 279   else if (!isa<DefinedCOFF>(S->body()))
 280     reportDuplicate(S, nullptr);
 281   return S;
 282 }
 283
 284 Symbol *SymbolTable::addImportThunk(StringRef Name, DefinedImportData *ID,
 285                                     uint16_t Machine) {
 286   Symbol *S;
 287   bool WasInserted;
 288   std::tie(S, WasInserted) = insert(Name);
 289   S->IsUsedInRegularObj = true;
 290   if (WasInserted || isa<Undefined>(S->body()) || isa<Lazy>(S->body()))
 291     replaceBody<DefinedImportThunk>(S, Name, ID, Machine);
 292   else if (!isa<DefinedCOFF>(S->body()))
 293     reportDuplicate(S, nullptr);
 294   return S;
 295 }
 296
 297 std::vector<Chunk *> SymbolTable::getChunks() {
 298   std::vector<Chunk *> Res;
 299   for (ObjFile *File : ObjFile::Instances) {
 300     std::vector<Chunk *> &V = File->getChunks();
 301     Res.insert(Res.end(), V.begin(), V.end());
 302   }
 303   return Res;
 304 }
 305
 306 Symbol *SymbolTable::find(StringRef Name) {
 307   auto It = Symtab.find(CachedHashStringRef(Name));
 308   if (It == Symtab.end())
 309     return nullptr;
 310   return It->second;
 311 }
 312
 313 Symbol *SymbolTable::findUnderscore(StringRef Name) {
 314   if (Config->Machine == I386)
 315     return find(("_" + Name).str());
 316   return find(Name);
 317 }
 318
 319 StringRef SymbolTable::findByPrefix(StringRef Prefix) {
 320   for (auto Pair : Symtab) {
 321     StringRef Name = Pair.first.val();
 322     if (Name.startswith(Prefix))
 323       return Name;
 324   }
 325   return "";
 326 }
 327
 328 StringRef SymbolTable::findMangle(StringRef Name) {
 329   if (Symbol *Sym = find(Name))
 330     if (!isa<Undefined>(Sym->body()))
 331       return Name;
 332   if (Config->Machine != I386)
 333     return findByPrefix(("?" + Name + "@@Y").str());
 334   if (!Name.startswith("_"))
 335     return "";
 336   // Search for x86 C function.
 337   StringRef S = findByPrefix((Name + "@").str());
 338   if (!S.empty())
 339     return S;
 340   // Search for x86 C++ non-member function.
 341   return findByPrefix(("?" + Name.substr(1) + "@@Y").str());
 342 }
 343
 344 void SymbolTable::mangleMaybe(SymbolBody *B) {
 345   auto *U = dyn_cast<Undefined>(B);
 346   if (!U || U->WeakAlias)
 347     return;
 348   StringRef Alias = findMangle(U->getName());
 349   if (!Alias.empty())
 350     U->WeakAlias = addUndefined(Alias);
 351 }
 352
 353 SymbolBody *SymbolTable::addUndefined(StringRef Name) {
 354   return addUndefined(Name, nullptr, false)->body();
 355 }
 356
 357 std::vector<StringRef> SymbolTable::compileBitcodeFiles() {
 358   LTO.reset(new BitcodeCompiler);
 359   for (BitcodeFile *F : BitcodeFile::Instances)
 360     LTO->add(*F);
 361   return LTO->compile();
 362 }
 363
 364 void SymbolTable::addCombinedLTOObjects() {
 365   if (BitcodeFile::Instances.empty())
 366     return;
 367   for (StringRef Object : compileBitcodeFiles()) {
 368     auto *Obj = make<ObjFile>(MemoryBufferRef(Object, "lto.tmp"));
 369     Obj->parse();
 370     ObjFile::Instances.push_back(Obj);
 371   }
 372 }
 373
 374 } // namespace coff
 375 } // namespace lld