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