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 "InputChunks.h"
13 #include "InputGlobal.h"
14 #include "WriterUtils.h"
15 #include "lld/Common/ErrorHandler.h"
16 #include "lld/Common/Memory.h"
17 #include "llvm/ADT/SetVector.h"
18 
19 #define DEBUG_TYPE "lld"
20 
21 using namespace llvm;
22 using namespace llvm::wasm;
23 using namespace lld;
24 using namespace lld::wasm;
25 
26 SymbolTable *lld::wasm::Symtab;
27 
28 void SymbolTable::addFile(InputFile *File) {
29   log("Processing: " + toString(File));
30   File->parse();
31 
32   if (auto *F = dyn_cast<ObjFile>(File))
33     ObjectFiles.push_back(F);
34 }
35 
36 void SymbolTable::reportRemainingUndefines() {
37   SetVector<Symbol *> Undefs;
38   for (Symbol *Sym : SymVector) {
39     if (Sym->isUndefined() && !Sym->isWeak() &&
40         Config->AllowUndefinedSymbols.count(Sym->getName()) == 0) {
41       Undefs.insert(Sym);
42     }
43   }
44 
45   if (Undefs.empty())
46     return;
47 
48   for (ObjFile *File : ObjectFiles)
49     for (Symbol *Sym : File->getSymbols())
50       if (Undefs.count(Sym))
51         error(toString(File) + ": undefined symbol: " + toString(*Sym));
52 
53   for (Symbol *Sym : Undefs)
54     if (!Sym->getFile())
55       error("undefined symbol: " + toString(*Sym));
56 }
57 
58 Symbol *SymbolTable::find(StringRef Name) {
59   return SymMap.lookup(CachedHashStringRef(Name));
60 }
61 
62 std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name) {
63   Symbol *&Sym = SymMap[CachedHashStringRef(Name)];
64   if (Sym)
65     return {Sym, false};
66   Sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
67   SymVector.emplace_back(Sym);
68   return {Sym, true};
69 }
70 
71 static void reportTypeError(const Symbol *Existing, const InputFile *File,
72                             llvm::wasm::WasmSymbolType Type) {
73   error("symbol type mismatch: " + toString(*Existing) + "\n>>> defined as " +
74         toString(Existing->getWasmType()) + " in " +
75         toString(Existing->getFile()) + "\n>>> defined as " + toString(Type) +
76         " in " + toString(File));
77 }
78 
79 static void checkFunctionType(const Symbol *Existing, const InputFile *File,
80                               const WasmSignature *NewSig) {
81   auto ExistingFunction = dyn_cast<FunctionSymbol>(Existing);
82   if (!ExistingFunction) {
83     reportTypeError(Existing, File, WASM_SYMBOL_TYPE_FUNCTION);
84     return;
85   }
86 
87   const WasmSignature *OldSig = ExistingFunction->getFunctionType();
88   if (OldSig && NewSig && *NewSig != *OldSig) {
89     warn("Function type mismatch: " + Existing->getName() +
90          "\n>>> defined as " + toString(*OldSig) + " in " +
91          toString(Existing->getFile()) + "\n>>> defined as " +
92          toString(*NewSig) + " in " + toString(File));
93   }
94 }
95 
96 // Check the type of new symbol matches that of the symbol is replacing.
97 // For functions this can also involve verifying that the signatures match.
98 static void checkGlobalType(const Symbol *Existing, const InputFile *File,
99                             const WasmGlobalType *NewType) {
100   if (!isa<GlobalSymbol>(Existing)) {
101     reportTypeError(Existing, File, WASM_SYMBOL_TYPE_GLOBAL);
102     return;
103   }
104 
105   const WasmGlobalType *OldType = cast<GlobalSymbol>(Existing)->getGlobalType();
106   if (*NewType != *OldType) {
107     error("Global type mismatch: " + Existing->getName() + "\n>>> defined as " +
108           toString(*OldType) + " in " + toString(Existing->getFile()) +
109           "\n>>> defined as " + toString(*NewType) + " in " + toString(File));
110   }
111 }
112 
113 static void checkDataType(const Symbol *Existing, const InputFile *File) {
114   if (!isa<DataSymbol>(Existing))
115     reportTypeError(Existing, File, WASM_SYMBOL_TYPE_DATA);
116 }
117 
118 DefinedFunction *SymbolTable::addSyntheticFunction(StringRef Name,
119                                                    uint32_t Flags,
120                                                    InputFunction *Function) {
121   LLVM_DEBUG(dbgs() << "addSyntheticFunction: " << Name << "\n");
122   assert(!find(Name));
123   SyntheticFunctions.emplace_back(Function);
124   return replaceSymbol<DefinedFunction>(insert(Name).first, Name, Flags,
125                                         nullptr, Function);
126 }
127 
128 DefinedData *SymbolTable::addSyntheticDataSymbol(StringRef Name,
129                                                  uint32_t Flags) {
130   LLVM_DEBUG(dbgs() << "addSyntheticDataSymbol: " << Name << "\n");
131   assert(!find(Name));
132   return replaceSymbol<DefinedData>(insert(Name).first, Name, Flags);
133 }
134 
135 DefinedGlobal *SymbolTable::addSyntheticGlobal(StringRef Name, uint32_t Flags,
136                                                InputGlobal *Global) {
137   LLVM_DEBUG(dbgs() << "addSyntheticGlobal: " << Name << " -> " << Global
138                     << "\n");
139   assert(!find(Name));
140   SyntheticGlobals.emplace_back(Global);
141   return replaceSymbol<DefinedGlobal>(insert(Name).first, Name, Flags, nullptr,
142                                       Global);
143 }
144 
145 static bool shouldReplace(const Symbol *Existing, InputFile *NewFile,
146                           uint32_t NewFlags) {
147   // If existing symbol is undefined, replace it.
148   if (!Existing->isDefined()) {
149     LLVM_DEBUG(dbgs() << "resolving existing undefined symbol: "
150                       << Existing->getName() << "\n");
151     return true;
152   }
153 
154   // Now we have two defined symbols. If the new one is weak, we can ignore it.
155   if ((NewFlags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK) {
156     LLVM_DEBUG(dbgs() << "existing symbol takes precedence\n");
157     return false;
158   }
159 
160   // If the existing symbol is weak, we should replace it.
161   if (Existing->isWeak()) {
162     LLVM_DEBUG(dbgs() << "replacing existing weak symbol\n");
163     return true;
164   }
165 
166   // Neither symbol is week. They conflict.
167   error("duplicate symbol: " + toString(*Existing) + "\n>>> defined in " +
168         toString(Existing->getFile()) + "\n>>> defined in " +
169         toString(NewFile));
170   return true;
171 }
172 
173 Symbol *SymbolTable::addDefinedFunction(StringRef Name, uint32_t Flags,
174                                         InputFile *File,
175                                         InputFunction *Function) {
176   LLVM_DEBUG(dbgs() << "addDefinedFunction: " << Name << "\n");
177   Symbol *S;
178   bool WasInserted;
179   std::tie(S, WasInserted) = insert(Name);
180 
181   if (WasInserted || S->isLazy()) {
182     replaceSymbol<DefinedFunction>(S, Name, Flags, File, Function);
183     return S;
184   }
185 
186   checkFunctionType(S, File, &Function->Signature);
187 
188   if (shouldReplace(S, File, Flags))
189     replaceSymbol<DefinedFunction>(S, Name, Flags, File, Function);
190   return S;
191 }
192 
193 Symbol *SymbolTable::addDefinedData(StringRef Name, uint32_t Flags,
194                                     InputFile *File, InputSegment *Segment,
195                                     uint32_t Address, uint32_t Size) {
196   LLVM_DEBUG(dbgs() << "addDefinedData:" << Name << " addr:" << Address
197                     << "\n");
198   Symbol *S;
199   bool WasInserted;
200   std::tie(S, WasInserted) = insert(Name);
201 
202   if (WasInserted || S->isLazy()) {
203     replaceSymbol<DefinedData>(S, Name, Flags, File, Segment, Address, Size);
204     return S;
205   }
206 
207   checkDataType(S, File);
208 
209   if (shouldReplace(S, File, Flags))
210     replaceSymbol<DefinedData>(S, Name, Flags, File, Segment, Address, Size);
211   return S;
212 }
213 
214 Symbol *SymbolTable::addDefinedGlobal(StringRef Name, uint32_t Flags,
215                                       InputFile *File, InputGlobal *Global) {
216   LLVM_DEBUG(dbgs() << "addDefinedGlobal:" << Name << "\n");
217   Symbol *S;
218   bool WasInserted;
219   std::tie(S, WasInserted) = insert(Name);
220 
221   if (WasInserted || S->isLazy()) {
222     replaceSymbol<DefinedGlobal>(S, Name, Flags, File, Global);
223     return S;
224   }
225 
226   checkGlobalType(S, File, &Global->getType());
227 
228   if (shouldReplace(S, File, Flags))
229     replaceSymbol<DefinedGlobal>(S, Name, Flags, File, Global);
230   return S;
231 }
232 
233 Symbol *SymbolTable::addUndefinedFunction(StringRef Name, uint32_t Flags,
234                                           InputFile *File,
235                                           const WasmSignature *Sig) {
236   LLVM_DEBUG(dbgs() << "addUndefinedFunction: " << Name << "\n");
237 
238   Symbol *S;
239   bool WasInserted;
240   std::tie(S, WasInserted) = insert(Name);
241 
242   if (WasInserted)
243     replaceSymbol<UndefinedFunction>(S, Name, Flags, File, Sig);
244   else if (auto *Lazy = dyn_cast<LazySymbol>(S))
245     Lazy->fetch();
246   else if (S->isDefined())
247     checkFunctionType(S, File, Sig);
248   return S;
249 }
250 
251 Symbol *SymbolTable::addUndefinedData(StringRef Name, uint32_t Flags,
252                                       InputFile *File) {
253   LLVM_DEBUG(dbgs() << "addUndefinedData: " << Name << "\n");
254 
255   Symbol *S;
256   bool WasInserted;
257   std::tie(S, WasInserted) = insert(Name);
258 
259   if (WasInserted)
260     replaceSymbol<UndefinedData>(S, Name, Flags, File);
261   else if (auto *Lazy = dyn_cast<LazySymbol>(S))
262     Lazy->fetch();
263   else if (S->isDefined())
264     checkDataType(S, File);
265   return S;
266 }
267 
268 Symbol *SymbolTable::addUndefinedGlobal(StringRef Name, uint32_t Flags,
269                                         InputFile *File,
270                                         const WasmGlobalType *Type) {
271   LLVM_DEBUG(dbgs() << "addUndefinedGlobal: " << Name << "\n");
272 
273   Symbol *S;
274   bool WasInserted;
275   std::tie(S, WasInserted) = insert(Name);
276 
277   if (WasInserted)
278     replaceSymbol<UndefinedGlobal>(S, Name, Flags, File, Type);
279   else if (auto *Lazy = dyn_cast<LazySymbol>(S))
280     Lazy->fetch();
281   else if (S->isDefined())
282     checkGlobalType(S, File, Type);
283   return S;
284 }
285 
286 void SymbolTable::addLazy(ArchiveFile *File, const Archive::Symbol *Sym) {
287   LLVM_DEBUG(dbgs() << "addLazy: " << Sym->getName() << "\n");
288   StringRef Name = Sym->getName();
289 
290   Symbol *S;
291   bool WasInserted;
292   std::tie(S, WasInserted) = insert(Name);
293 
294   if (WasInserted) {
295     replaceSymbol<LazySymbol>(S, Name, File, *Sym);
296     return;
297   }
298 
299   // If there is an existing undefined symbol, load a new one from the archive.
300   if (S->isUndefined()) {
301     LLVM_DEBUG(dbgs() << "replacing existing undefined\n");
302     File->addMember(Sym);
303   }
304 }
305 
306 bool SymbolTable::addComdat(StringRef Name) {
307   return Comdats.insert(CachedHashStringRef(Name)).second;
308 }
309