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 "LTO.h"
14 #include "PDB.h"
15 #include "Symbols.h"
16 #include "lld/Common/ErrorHandler.h"
17 #include "lld/Common/Memory.h"
18 #include "lld/Common/Timer.h"
19 #include "llvm/IR/LLVMContext.h"
20 #include "llvm/Support/Debug.h"
21 #include "llvm/Support/raw_ostream.h"
22 #include <utility>
23 
24 using namespace llvm;
25 
26 namespace lld {
27 namespace coff {
28 
29 static Timer LTOTimer("LTO", Timer::root());
30 
31 SymbolTable *Symtab;
32 
33 void SymbolTable::addFile(InputFile *File) {
34   log("Reading " + toString(File));
35   File->parse();
36 
37   MachineTypes MT = File->getMachineType();
38   if (Config->Machine == IMAGE_FILE_MACHINE_UNKNOWN) {
39     Config->Machine = MT;
40   } else if (MT != IMAGE_FILE_MACHINE_UNKNOWN && Config->Machine != MT) {
41     fatal(toString(File) + ": machine type " + machineToStr(MT) +
42           " conflicts with " + machineToStr(Config->Machine));
43   }
44 
45   if (auto *F = dyn_cast<ObjFile>(File)) {
46     ObjFile::Instances.push_back(F);
47   } else if (auto *F = dyn_cast<BitcodeFile>(File)) {
48     BitcodeFile::Instances.push_back(F);
49   } else if (auto *F = dyn_cast<ImportFile>(File)) {
50     ImportFile::Instances.push_back(F);
51   }
52 
53   StringRef S = File->getDirectives();
54   if (S.empty())
55     return;
56 
57   log("Directives: " + toString(File) + ": " + S);
58   Driver->parseDirectives(S);
59 }
60 
61 static void errorOrWarn(const Twine &S) {
62   if (Config->Force)
63     warn(S);
64   else
65     error(S);
66 }
67 
68 // Returns the name of the symbol in SC whose value is <= Addr that is closest
69 // to Addr. This is generally the name of the global variable or function whose
70 // definition contains Addr.
71 static StringRef getSymbolName(SectionChunk *SC, uint32_t Addr) {
72   DefinedRegular *Candidate = nullptr;
73 
74   for (Symbol *S : SC->File->getSymbols()) {
75     auto *D = dyn_cast_or_null<DefinedRegular>(S);
76     if (!D || D->getChunk() != SC || D->getValue() > Addr ||
77         (Candidate && D->getValue() < Candidate->getValue()))
78       continue;
79 
80     Candidate = D;
81   }
82 
83   if (!Candidate)
84     return "";
85   return Candidate->getName();
86 }
87 
88 static std::string getSymbolLocations(ObjFile *File, uint32_t SymIndex) {
89   struct Location {
90     StringRef SymName;
91     std::pair<StringRef, uint32_t> FileLine;
92   };
93   std::vector<Location> Locations;
94 
95   for (Chunk *C : File->getChunks()) {
96     auto *SC = dyn_cast<SectionChunk>(C);
97     if (!SC)
98       continue;
99     for (const coff_relocation &R : SC->Relocs) {
100       if (R.SymbolTableIndex != SymIndex)
101         continue;
102       std::pair<StringRef, uint32_t> FileLine =
103           getFileLine(SC, R.VirtualAddress);
104       StringRef SymName = getSymbolName(SC, R.VirtualAddress);
105       if (!FileLine.first.empty() || !SymName.empty())
106         Locations.push_back({SymName, FileLine});
107     }
108   }
109 
110   if (Locations.empty())
111     return "\n>>> referenced by " + toString(File) + "\n";
112 
113   std::string Out;
114   llvm::raw_string_ostream OS(Out);
115   for (Location Loc : Locations) {
116     OS << "\n>>> referenced by ";
117     if (!Loc.FileLine.first.empty())
118       OS << Loc.FileLine.first << ":" << Loc.FileLine.second
119          << "\n>>>               ";
120     OS << toString(File);
121     if (!Loc.SymName.empty())
122       OS << ":(" << Loc.SymName << ')';
123   }
124   OS << '\n';
125   return OS.str();
126 }
127 
128 void SymbolTable::reportRemainingUndefines() {
129   SmallPtrSet<Symbol *, 8> Undefs;
130   DenseMap<Symbol *, Symbol *> LocalImports;
131 
132   for (auto &I : SymMap) {
133     Symbol *Sym = I.second;
134     auto *Undef = dyn_cast<Undefined>(Sym);
135     if (!Undef)
136       continue;
137     if (!Sym->IsUsedInRegularObj)
138       continue;
139 
140     StringRef Name = Undef->getName();
141 
142     // A weak alias may have been resolved, so check for that.
143     if (Defined *D = Undef->getWeakAlias()) {
144       // We want to replace Sym with D. However, we can't just blindly
145       // copy sizeof(SymbolUnion) bytes from D to Sym because D may be an
146       // internal symbol, and internal symbols are stored as "unparented"
147       // Symbols. For that reason we need to check which type of symbol we
148       // are dealing with and copy the correct number of bytes.
149       if (isa<DefinedRegular>(D))
150         memcpy(Sym, D, sizeof(DefinedRegular));
151       else if (isa<DefinedAbsolute>(D))
152         memcpy(Sym, D, sizeof(DefinedAbsolute));
153       else
154         memcpy(Sym, D, sizeof(SymbolUnion));
155       continue;
156     }
157 
158     // If we can resolve a symbol by removing __imp_ prefix, do that.
159     // This odd rule is for compatibility with MSVC linker.
160     if (Name.startswith("__imp_")) {
161       Symbol *Imp = find(Name.substr(strlen("__imp_")));
162       if (Imp && isa<Defined>(Imp)) {
163         auto *D = cast<Defined>(Imp);
164         replaceSymbol<DefinedLocalImport>(Sym, Name, D);
165         LocalImportChunks.push_back(cast<DefinedLocalImport>(Sym)->getChunk());
166         LocalImports[Sym] = D;
167         continue;
168       }
169     }
170 
171     // Remaining undefined symbols are not fatal if /force is specified.
172     // They are replaced with dummy defined symbols.
173     if (Config->Force)
174       replaceSymbol<DefinedAbsolute>(Sym, Name, 0);
175     Undefs.insert(Sym);
176   }
177 
178   if (Undefs.empty() && LocalImports.empty())
179     return;
180 
181   for (Symbol *B : Config->GCRoot) {
182     if (Undefs.count(B))
183       errorOrWarn("<root>: undefined symbol: " + B->getName());
184     if (Config->WarnLocallyDefinedImported)
185       if (Symbol *Imp = LocalImports.lookup(B))
186         warn("<root>: locally defined symbol imported: " + Imp->getName() +
187              " (defined in " + toString(Imp->getFile()) + ") [LNK4217]");
188   }
189 
190   for (ObjFile *File : ObjFile::Instances) {
191     size_t SymIndex = -1ull;
192     for (Symbol *Sym : File->getSymbols()) {
193       ++SymIndex;
194       if (!Sym)
195         continue;
196       if (Undefs.count(Sym))
197         errorOrWarn("undefined symbol: " + Sym->getName() +
198                     getSymbolLocations(File, SymIndex));
199       if (Config->WarnLocallyDefinedImported)
200         if (Symbol *Imp = LocalImports.lookup(Sym))
201           warn(toString(File) + ": locally defined symbol imported: " +
202                Imp->getName() + " (defined in " + toString(Imp->getFile()) +
203                ") [LNK4217]");
204     }
205   }
206 }
207 
208 std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name) {
209   Symbol *&Sym = SymMap[CachedHashStringRef(Name)];
210   if (Sym)
211     return {Sym, false};
212   Sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
213   Sym->IsUsedInRegularObj = false;
214   Sym->PendingArchiveLoad = false;
215   return {Sym, true};
216 }
217 
218 Symbol *SymbolTable::addUndefined(StringRef Name, InputFile *F,
219                                   bool IsWeakAlias) {
220   Symbol *S;
221   bool WasInserted;
222   std::tie(S, WasInserted) = insert(Name);
223   if (!F || !isa<BitcodeFile>(F))
224     S->IsUsedInRegularObj = true;
225   if (WasInserted || (isa<Lazy>(S) && IsWeakAlias)) {
226     replaceSymbol<Undefined>(S, Name);
227     return S;
228   }
229   if (auto *L = dyn_cast<Lazy>(S)) {
230     if (!S->PendingArchiveLoad) {
231       S->PendingArchiveLoad = true;
232       L->File->addMember(&L->Sym);
233     }
234   }
235   return S;
236 }
237 
238 void SymbolTable::addLazy(ArchiveFile *F, const Archive::Symbol Sym) {
239   StringRef Name = Sym.getName();
240   Symbol *S;
241   bool WasInserted;
242   std::tie(S, WasInserted) = insert(Name);
243   if (WasInserted) {
244     replaceSymbol<Lazy>(S, F, Sym);
245     return;
246   }
247   auto *U = dyn_cast<Undefined>(S);
248   if (!U || U->WeakAlias || S->PendingArchiveLoad)
249     return;
250   S->PendingArchiveLoad = true;
251   F->addMember(&Sym);
252 }
253 
254 void SymbolTable::reportDuplicate(Symbol *Existing, InputFile *NewFile) {
255   error("duplicate symbol: " + toString(*Existing) + " in " +
256         toString(Existing->getFile()) + " and in " + toString(NewFile));
257 }
258 
259 Symbol *SymbolTable::addAbsolute(StringRef N, COFFSymbolRef Sym) {
260   Symbol *S;
261   bool WasInserted;
262   std::tie(S, WasInserted) = insert(N);
263   S->IsUsedInRegularObj = true;
264   if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S))
265     replaceSymbol<DefinedAbsolute>(S, N, Sym);
266   else if (!isa<DefinedCOFF>(S))
267     reportDuplicate(S, nullptr);
268   return S;
269 }
270 
271 Symbol *SymbolTable::addAbsolute(StringRef N, uint64_t VA) {
272   Symbol *S;
273   bool WasInserted;
274   std::tie(S, WasInserted) = insert(N);
275   S->IsUsedInRegularObj = true;
276   if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S))
277     replaceSymbol<DefinedAbsolute>(S, N, VA);
278   else if (!isa<DefinedCOFF>(S))
279     reportDuplicate(S, nullptr);
280   return S;
281 }
282 
283 Symbol *SymbolTable::addSynthetic(StringRef N, Chunk *C) {
284   Symbol *S;
285   bool WasInserted;
286   std::tie(S, WasInserted) = insert(N);
287   S->IsUsedInRegularObj = true;
288   if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S))
289     replaceSymbol<DefinedSynthetic>(S, N, C);
290   else if (!isa<DefinedCOFF>(S))
291     reportDuplicate(S, nullptr);
292   return S;
293 }
294 
295 Symbol *SymbolTable::addRegular(InputFile *F, StringRef N,
296                                 const coff_symbol_generic *Sym,
297                                 SectionChunk *C) {
298   Symbol *S;
299   bool WasInserted;
300   std::tie(S, WasInserted) = insert(N);
301   if (!isa<BitcodeFile>(F))
302     S->IsUsedInRegularObj = true;
303   if (WasInserted || !isa<DefinedRegular>(S))
304     replaceSymbol<DefinedRegular>(S, F, N, /*IsCOMDAT*/ false,
305                                   /*IsExternal*/ true, Sym, C);
306   else
307     reportDuplicate(S, F);
308   return S;
309 }
310 
311 std::pair<Symbol *, bool>
312 SymbolTable::addComdat(InputFile *F, StringRef N,
313                        const coff_symbol_generic *Sym) {
314   Symbol *S;
315   bool WasInserted;
316   std::tie(S, WasInserted) = insert(N);
317   if (!isa<BitcodeFile>(F))
318     S->IsUsedInRegularObj = true;
319   if (WasInserted || !isa<DefinedRegular>(S)) {
320     replaceSymbol<DefinedRegular>(S, F, N, /*IsCOMDAT*/ true,
321                                   /*IsExternal*/ true, Sym, nullptr);
322     return {S, true};
323   }
324   if (!cast<DefinedRegular>(S)->isCOMDAT())
325     reportDuplicate(S, F);
326   return {S, false};
327 }
328 
329 Symbol *SymbolTable::addCommon(InputFile *F, StringRef N, uint64_t Size,
330                                const coff_symbol_generic *Sym, CommonChunk *C) {
331   Symbol *S;
332   bool WasInserted;
333   std::tie(S, WasInserted) = insert(N);
334   if (!isa<BitcodeFile>(F))
335     S->IsUsedInRegularObj = true;
336   if (WasInserted || !isa<DefinedCOFF>(S))
337     replaceSymbol<DefinedCommon>(S, F, N, Size, Sym, C);
338   else if (auto *DC = dyn_cast<DefinedCommon>(S))
339     if (Size > DC->getSize())
340       replaceSymbol<DefinedCommon>(S, F, N, Size, Sym, C);
341   return S;
342 }
343 
344 DefinedImportData *SymbolTable::addImportData(StringRef N, ImportFile *F) {
345   Symbol *S;
346   bool WasInserted;
347   std::tie(S, WasInserted) = insert(N);
348   S->IsUsedInRegularObj = true;
349   if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S)) {
350     replaceSymbol<DefinedImportData>(S, N, F);
351     return cast<DefinedImportData>(S);
352   }
353 
354   reportDuplicate(S, F);
355   return nullptr;
356 }
357 
358 DefinedImportThunk *SymbolTable::addImportThunk(StringRef Name,
359                                                DefinedImportData *ID,
360                                                uint16_t Machine) {
361   Symbol *S;
362   bool WasInserted;
363   std::tie(S, WasInserted) = insert(Name);
364   S->IsUsedInRegularObj = true;
365   if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S)) {
366     replaceSymbol<DefinedImportThunk>(S, Name, ID, Machine);
367     return cast<DefinedImportThunk>(S);
368   }
369 
370   reportDuplicate(S, ID->File);
371   return nullptr;
372 }
373 
374 std::vector<Chunk *> SymbolTable::getChunks() {
375   std::vector<Chunk *> Res;
376   for (ObjFile *File : ObjFile::Instances) {
377     ArrayRef<Chunk *> V = File->getChunks();
378     Res.insert(Res.end(), V.begin(), V.end());
379   }
380   return Res;
381 }
382 
383 Symbol *SymbolTable::find(StringRef Name) {
384   return SymMap.lookup(CachedHashStringRef(Name));
385 }
386 
387 Symbol *SymbolTable::findUnderscore(StringRef Name) {
388   if (Config->Machine == I386)
389     return find(("_" + Name).str());
390   return find(Name);
391 }
392 
393 StringRef SymbolTable::findByPrefix(StringRef Prefix) {
394   for (auto Pair : SymMap) {
395     StringRef Name = Pair.first.val();
396     if (Name.startswith(Prefix))
397       return Name;
398   }
399   return "";
400 }
401 
402 StringRef SymbolTable::findMangle(StringRef Name) {
403   if (Symbol *Sym = find(Name))
404     if (!isa<Undefined>(Sym))
405       return Name;
406   if (Config->Machine != I386)
407     return findByPrefix(("?" + Name + "@@Y").str());
408   if (!Name.startswith("_"))
409     return "";
410   // Search for x86 stdcall function.
411   StringRef S = findByPrefix((Name + "@").str());
412   if (!S.empty())
413     return S;
414   // Search for x86 fastcall function.
415   S = findByPrefix(("@" + Name.substr(1) + "@").str());
416   if (!S.empty())
417     return S;
418   // Search for x86 vectorcall function.
419   S = findByPrefix((Name.substr(1) + "@@").str());
420   if (!S.empty())
421     return S;
422   // Search for x86 C++ non-member function.
423   return findByPrefix(("?" + Name.substr(1) + "@@Y").str());
424 }
425 
426 void SymbolTable::mangleMaybe(Symbol *B) {
427   auto *U = dyn_cast<Undefined>(B);
428   if (!U || U->WeakAlias)
429     return;
430   StringRef Alias = findMangle(U->getName());
431   if (!Alias.empty()) {
432     log(U->getName() + " aliased to " + Alias);
433     U->WeakAlias = addUndefined(Alias);
434   }
435 }
436 
437 Symbol *SymbolTable::addUndefined(StringRef Name) {
438   return addUndefined(Name, nullptr, false);
439 }
440 
441 std::vector<StringRef> SymbolTable::compileBitcodeFiles() {
442   LTO.reset(new BitcodeCompiler);
443   for (BitcodeFile *F : BitcodeFile::Instances)
444     LTO->add(*F);
445   return LTO->compile();
446 }
447 
448 void SymbolTable::addCombinedLTOObjects() {
449   if (BitcodeFile::Instances.empty())
450     return;
451 
452   ScopedTimer T(LTOTimer);
453   for (StringRef Object : compileBitcodeFiles()) {
454     auto *Obj = make<ObjFile>(MemoryBufferRef(Object, "lto.tmp"));
455     Obj->parse();
456     ObjFile::Instances.push_back(Obj);
457   }
458 }
459 
460 } // namespace coff
461 } // namespace lld
462