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