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 "Memory.h"
15 #include "Symbols.h"
16 #include "lld/Common/ErrorHandler.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))
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)) {
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 static void errorOrWarn(const Twine &S) {
88   if (Config->Force)
89     warn(S);
90   else
91     error(S);
92 }
93 
94 void SymbolTable::reportRemainingUndefines() {
95   SmallPtrSet<Symbol *, 8> Undefs;
96 
97   for (auto &I : Symtab) {
98     Symbol *Sym = I.second;
99     auto *Undef = dyn_cast<Undefined>(Sym);
100     if (!Undef)
101       continue;
102     if (!Sym->IsUsedInRegularObj)
103       continue;
104 
105     StringRef Name = Undef->getName();
106 
107     // A weak alias may have been resolved, so check for that.
108     if (Defined *D = Undef->getWeakAlias()) {
109       // We want to replace Sym with D. However, we can't just blindly
110       // copy sizeof(SymbolUnion) bytes from D to Sym because D may be an
111       // internal symbol, and internal symbols are stored as "unparented"
112       // Symbols. For that reason we need to check which type of symbol we
113       // are dealing with and copy the correct number of bytes.
114       if (isa<DefinedRegular>(D))
115         memcpy(Sym, D, sizeof(DefinedRegular));
116       else if (isa<DefinedAbsolute>(D))
117         memcpy(Sym, D, sizeof(DefinedAbsolute));
118       else
119         memcpy(Sym, D, sizeof(SymbolUnion));
120       continue;
121     }
122 
123     // If we can resolve a symbol by removing __imp_ prefix, do that.
124     // This odd rule is for compatibility with MSVC linker.
125     if (Name.startswith("__imp_")) {
126       Symbol *Imp = find(Name.substr(strlen("__imp_")));
127       if (Imp && isa<Defined>(Imp)) {
128         auto *D = cast<Defined>(Imp);
129         replaceSymbol<DefinedLocalImport>(Sym, Name, D);
130         LocalImportChunks.push_back(cast<DefinedLocalImport>(Sym)->getChunk());
131         continue;
132       }
133     }
134 
135     // Remaining undefined symbols are not fatal if /force is specified.
136     // They are replaced with dummy defined symbols.
137     if (Config->Force)
138       replaceSymbol<DefinedAbsolute>(Sym, Name, 0);
139     Undefs.insert(Sym);
140   }
141 
142   if (Undefs.empty())
143     return;
144 
145   for (Symbol *B : Config->GCRoot)
146     if (Undefs.count(B))
147       errorOrWarn("<root>: undefined symbol: " + B->getName());
148 
149   for (ObjFile *File : ObjFile::Instances)
150     for (Symbol *Sym : File->getSymbols())
151       if (Undefs.count(Sym))
152         errorOrWarn(toString(File) + ": undefined symbol: " + Sym->getName());
153 }
154 
155 std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name) {
156   Symbol *&Sym = Symtab[CachedHashStringRef(Name)];
157   if (Sym)
158     return {Sym, false};
159   Sym = (Symbol *)make<SymbolUnion>();
160   Sym->IsUsedInRegularObj = false;
161   Sym->PendingArchiveLoad = false;
162   return {Sym, true};
163 }
164 
165 Symbol *SymbolTable::addUndefined(StringRef Name, InputFile *F,
166                                   bool IsWeakAlias) {
167   Symbol *S;
168   bool WasInserted;
169   std::tie(S, WasInserted) = insert(Name);
170   if (!F || !isa<BitcodeFile>(F))
171     S->IsUsedInRegularObj = true;
172   if (WasInserted || (isa<Lazy>(S) && IsWeakAlias)) {
173     replaceSymbol<Undefined>(S, Name);
174     return S;
175   }
176   if (auto *L = dyn_cast<Lazy>(S)) {
177     if (!S->PendingArchiveLoad) {
178       S->PendingArchiveLoad = true;
179       L->File->addMember(&L->Sym);
180     }
181   }
182   return S;
183 }
184 
185 void SymbolTable::addLazy(ArchiveFile *F, const Archive::Symbol Sym) {
186   StringRef Name = Sym.getName();
187   Symbol *S;
188   bool WasInserted;
189   std::tie(S, WasInserted) = insert(Name);
190   if (WasInserted) {
191     replaceSymbol<Lazy>(S, F, Sym);
192     return;
193   }
194   auto *U = dyn_cast<Undefined>(S);
195   if (!U || U->WeakAlias || S->PendingArchiveLoad)
196     return;
197   S->PendingArchiveLoad = true;
198   F->addMember(&Sym);
199 }
200 
201 void SymbolTable::reportDuplicate(Symbol *Existing, InputFile *NewFile) {
202   error("duplicate symbol: " + toString(*Existing) + " in " +
203         toString(Existing->getFile()) + " and in " +
204         (NewFile ? toString(NewFile) : "(internal)"));
205 }
206 
207 Symbol *SymbolTable::addAbsolute(StringRef N, COFFSymbolRef Sym) {
208   Symbol *S;
209   bool WasInserted;
210   std::tie(S, WasInserted) = insert(N);
211   S->IsUsedInRegularObj = true;
212   if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S))
213     replaceSymbol<DefinedAbsolute>(S, N, Sym);
214   else if (!isa<DefinedCOFF>(S))
215     reportDuplicate(S, nullptr);
216   return S;
217 }
218 
219 Symbol *SymbolTable::addAbsolute(StringRef N, uint64_t VA) {
220   Symbol *S;
221   bool WasInserted;
222   std::tie(S, WasInserted) = insert(N);
223   S->IsUsedInRegularObj = true;
224   if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S))
225     replaceSymbol<DefinedAbsolute>(S, N, VA);
226   else if (!isa<DefinedCOFF>(S))
227     reportDuplicate(S, nullptr);
228   return S;
229 }
230 
231 Symbol *SymbolTable::addSynthetic(StringRef N, Chunk *C) {
232   Symbol *S;
233   bool WasInserted;
234   std::tie(S, WasInserted) = insert(N);
235   S->IsUsedInRegularObj = true;
236   if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S))
237     replaceSymbol<DefinedSynthetic>(S, N, C);
238   else if (!isa<DefinedCOFF>(S))
239     reportDuplicate(S, nullptr);
240   return S;
241 }
242 
243 Symbol *SymbolTable::addRegular(InputFile *F, StringRef N, bool IsCOMDAT,
244                                 const coff_symbol_generic *Sym,
245                                 SectionChunk *C) {
246   Symbol *S;
247   bool WasInserted;
248   std::tie(S, WasInserted) = insert(N);
249   if (!isa<BitcodeFile>(F))
250     S->IsUsedInRegularObj = true;
251   SymbolPreference SP = compareDefined(S, WasInserted, IsCOMDAT);
252   if (SP == SP_CONFLICT) {
253     reportDuplicate(S, F);
254   } else if (SP == SP_NEW) {
255     replaceSymbol<DefinedRegular>(S, F, N, IsCOMDAT, /*IsExternal*/ true, Sym,
256                                   C);
257   } else if (SP == SP_EXISTING && IsCOMDAT && C) {
258     C->markDiscarded();
259     // Discard associative chunks that we've parsed so far. No need to recurse
260     // because an associative section cannot have children.
261     for (SectionChunk *Child : C->children())
262       Child->markDiscarded();
263   }
264   return S;
265 }
266 
267 Symbol *SymbolTable::addCommon(InputFile *F, StringRef N, uint64_t Size,
268                                const coff_symbol_generic *Sym, CommonChunk *C) {
269   Symbol *S;
270   bool WasInserted;
271   std::tie(S, WasInserted) = insert(N);
272   if (!isa<BitcodeFile>(F))
273     S->IsUsedInRegularObj = true;
274   if (WasInserted || !isa<DefinedCOFF>(S))
275     replaceSymbol<DefinedCommon>(S, F, N, Size, Sym, C);
276   else if (auto *DC = dyn_cast<DefinedCommon>(S))
277     if (Size > DC->getSize())
278       replaceSymbol<DefinedCommon>(S, F, N, Size, Sym, C);
279   return S;
280 }
281 
282 DefinedImportData *SymbolTable::addImportData(StringRef N, ImportFile *F) {
283   Symbol *S;
284   bool WasInserted;
285   std::tie(S, WasInserted) = insert(N);
286   S->IsUsedInRegularObj = true;
287   if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S)) {
288     replaceSymbol<DefinedImportData>(S, N, F);
289     return cast<DefinedImportData>(S);
290   }
291 
292   reportDuplicate(S, F);
293   return nullptr;
294 }
295 
296 DefinedImportThunk *SymbolTable::addImportThunk(StringRef Name,
297                                                DefinedImportData *ID,
298                                                uint16_t Machine) {
299   Symbol *S;
300   bool WasInserted;
301   std::tie(S, WasInserted) = insert(Name);
302   S->IsUsedInRegularObj = true;
303   if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S)) {
304     replaceSymbol<DefinedImportThunk>(S, Name, ID, Machine);
305     return cast<DefinedImportThunk>(S);
306   }
307 
308   reportDuplicate(S, ID->File);
309   return nullptr;
310 }
311 
312 std::vector<Chunk *> SymbolTable::getChunks() {
313   std::vector<Chunk *> Res;
314   for (ObjFile *File : ObjFile::Instances) {
315     std::vector<Chunk *> &V = File->getChunks();
316     Res.insert(Res.end(), V.begin(), V.end());
317   }
318   return Res;
319 }
320 
321 Symbol *SymbolTable::find(StringRef Name) {
322   auto It = Symtab.find(CachedHashStringRef(Name));
323   if (It == Symtab.end())
324     return nullptr;
325   return It->second;
326 }
327 
328 Symbol *SymbolTable::findUnderscore(StringRef Name) {
329   if (Config->Machine == I386)
330     return find(("_" + Name).str());
331   return find(Name);
332 }
333 
334 StringRef SymbolTable::findByPrefix(StringRef Prefix) {
335   for (auto Pair : Symtab) {
336     StringRef Name = Pair.first.val();
337     if (Name.startswith(Prefix))
338       return Name;
339   }
340   return "";
341 }
342 
343 StringRef SymbolTable::findMangle(StringRef Name) {
344   if (Symbol *Sym = find(Name))
345     if (!isa<Undefined>(Sym))
346       return Name;
347   if (Config->Machine != I386)
348     return findByPrefix(("?" + Name + "@@Y").str());
349   if (!Name.startswith("_"))
350     return "";
351   // Search for x86 stdcall function.
352   StringRef S = findByPrefix((Name + "@").str());
353   if (!S.empty())
354     return S;
355   // Search for x86 fastcall function.
356   S = findByPrefix(("@" + Name.substr(1) + "@").str());
357   if (!S.empty())
358     return S;
359   // Search for x86 vectorcall function.
360   S = findByPrefix((Name.substr(1) + "@@").str());
361   if (!S.empty())
362     return S;
363   // Search for x86 C++ non-member function.
364   return findByPrefix(("?" + Name.substr(1) + "@@Y").str());
365 }
366 
367 void SymbolTable::mangleMaybe(Symbol *B) {
368   auto *U = dyn_cast<Undefined>(B);
369   if (!U || U->WeakAlias)
370     return;
371   StringRef Alias = findMangle(U->getName());
372   if (!Alias.empty()) {
373     log(U->getName() + " aliased to " + Alias);
374     U->WeakAlias = addUndefined(Alias);
375   }
376 }
377 
378 Symbol *SymbolTable::addUndefined(StringRef Name) {
379   return addUndefined(Name, nullptr, false);
380 }
381 
382 std::vector<StringRef> SymbolTable::compileBitcodeFiles() {
383   LTO.reset(new BitcodeCompiler);
384   for (BitcodeFile *F : BitcodeFile::Instances)
385     LTO->add(*F);
386   return LTO->compile();
387 }
388 
389 void SymbolTable::addCombinedLTOObjects() {
390   if (BitcodeFile::Instances.empty())
391     return;
392   for (StringRef Object : compileBitcodeFiles()) {
393     auto *Obj = make<ObjFile>(MemoryBufferRef(Object, "lto.tmp"));
394     Obj->parse();
395     ObjFile::Instances.push_back(Obj);
396   }
397 }
398 
399 } // namespace coff
400 } // namespace lld
401