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                             StringRef Type) {
73   error("symbol type mismatch: " + toString(*Existing) + "\n>>> defined as " +
74         toString(Existing->getWasmType()) + " in " +
75         toString(Existing->getFile()) + "\n>>> defined as " + Type + " in " +
76         toString(File));
77 }
78 
79 static void checkFunctionType(const Symbol *Existing, const InputFile *File,
80                               const WasmSignature *NewSig) {
81   if (!isa<FunctionSymbol>(Existing)) {
82     reportTypeError(Existing, File, "Function");
83     return;
84   }
85 
86   const WasmSignature *OldSig =
87       cast<FunctionSymbol>(Existing)->getFunctionType();
88   if (OldSig && *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, "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, "Data");
116 }
117 
118 DefinedFunction *SymbolTable::addSyntheticFunction(StringRef Name,
119                                                    uint32_t Flags,
120                                                    InputFunction *Function) {
121   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   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   DEBUG(dbgs() << "addSyntheticGlobal: " << Name << " -> " << Global << "\n");
138   assert(!find(Name));
139   SyntheticGlobals.emplace_back(Global);
140   return replaceSymbol<DefinedGlobal>(insert(Name).first, Name, Flags, nullptr,
141                                       Global);
142 }
143 
144 static bool shouldReplace(const Symbol *Existing, InputFile *NewFile,
145                           uint32_t NewFlags) {
146   // If existing symbol is undefined, replace it.
147   if (!Existing->isDefined()) {
148     DEBUG(dbgs() << "resolving existing undefined symbol: "
149                  << Existing->getName() << "\n");
150     return true;
151   }
152 
153   // Now we have two defined symbols. If the new one is weak, we can ignore it.
154   if ((NewFlags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK) {
155     DEBUG(dbgs() << "existing symbol takes precedence\n");
156     return false;
157   }
158 
159   // If the existing symbol is weak, we should replace it.
160   if (Existing->isWeak()) {
161     DEBUG(dbgs() << "replacing existing weak symbol\n");
162     return true;
163   }
164 
165   // Neither symbol is week. They conflict.
166   error("duplicate symbol: " + toString(*Existing) + "\n>>> defined in " +
167         toString(Existing->getFile()) + "\n>>> defined in " +
168         toString(NewFile));
169   return true;
170 }
171 
172 Symbol *SymbolTable::addDefinedFunction(StringRef Name, uint32_t Flags,
173                                         InputFile *File,
174                                         InputFunction *Function) {
175   DEBUG(dbgs() << "addDefinedFunction: " << Name << "\n");
176   Symbol *S;
177   bool WasInserted;
178   std::tie(S, WasInserted) = insert(Name);
179 
180   if (WasInserted || S->isLazy()) {
181     replaceSymbol<DefinedFunction>(S, Name, Flags, File, Function);
182     return S;
183   }
184 
185   checkFunctionType(S, File, &Function->Signature);
186 
187   if (shouldReplace(S, File, Flags))
188     replaceSymbol<DefinedFunction>(S, Name, Flags, File, Function);
189   return S;
190 }
191 
192 Symbol *SymbolTable::addDefinedData(StringRef Name, uint32_t Flags,
193                                     InputFile *File, InputSegment *Segment,
194                                     uint32_t Address, uint32_t Size) {
195   DEBUG(dbgs() << "addDefinedData:" << Name << " addr:" << Address << "\n");
196   Symbol *S;
197   bool WasInserted;
198   std::tie(S, WasInserted) = insert(Name);
199 
200   if (WasInserted || S->isLazy()) {
201     replaceSymbol<DefinedData>(S, Name, Flags, File, Segment, Address, Size);
202     return S;
203   }
204 
205   checkDataType(S, File);
206 
207   if (shouldReplace(S, File, Flags))
208     replaceSymbol<DefinedData>(S, Name, Flags, File, Segment, Address, Size);
209   return S;
210 }
211 
212 Symbol *SymbolTable::addDefinedGlobal(StringRef Name, uint32_t Flags,
213                                       InputFile *File, InputGlobal *Global) {
214   DEBUG(dbgs() << "addDefinedGlobal:" << Name << "\n");
215   Symbol *S;
216   bool WasInserted;
217   std::tie(S, WasInserted) = insert(Name);
218 
219   if (WasInserted || S->isLazy()) {
220     replaceSymbol<DefinedGlobal>(S, Name, Flags, File, Global);
221     return S;
222   }
223 
224   checkGlobalType(S, File, &Global->getType());
225 
226   if (shouldReplace(S, File, Flags))
227     replaceSymbol<DefinedGlobal>(S, Name, Flags, File, Global);
228   return S;
229 }
230 
231 Symbol *SymbolTable::addUndefinedFunction(StringRef Name, uint32_t Flags,
232                                           InputFile *File,
233                                           const WasmSignature *Sig) {
234   DEBUG(dbgs() << "addUndefinedFunction: " << Name << "\n");
235 
236   Symbol *S;
237   bool WasInserted;
238   std::tie(S, WasInserted) = insert(Name);
239 
240   if (WasInserted)
241     replaceSymbol<UndefinedFunction>(S, Name, Flags, File, Sig);
242   else if (auto *Lazy = dyn_cast<LazySymbol>(S))
243     Lazy->fetch();
244   else if (S->isDefined())
245     checkFunctionType(S, File, Sig);
246   return S;
247 }
248 
249 Symbol *SymbolTable::addUndefinedData(StringRef Name, uint32_t Flags,
250                                       InputFile *File) {
251   DEBUG(dbgs() << "addUndefinedData: " << Name << "\n");
252 
253   Symbol *S;
254   bool WasInserted;
255   std::tie(S, WasInserted) = insert(Name);
256 
257   if (WasInserted)
258     replaceSymbol<UndefinedData>(S, Name, Flags, File);
259   else if (auto *Lazy = dyn_cast<LazySymbol>(S))
260     Lazy->fetch();
261   else if (S->isDefined())
262     checkDataType(S, File);
263   return S;
264 }
265 
266 Symbol *SymbolTable::addUndefinedGlobal(StringRef Name, uint32_t Flags,
267                                         InputFile *File,
268                                         const WasmGlobalType *Type) {
269   DEBUG(dbgs() << "addUndefinedGlobal: " << Name << "\n");
270 
271   Symbol *S;
272   bool WasInserted;
273   std::tie(S, WasInserted) = insert(Name);
274 
275   if (WasInserted)
276     replaceSymbol<UndefinedGlobal>(S, Name, Flags, File, Type);
277   else if (auto *Lazy = dyn_cast<LazySymbol>(S))
278     Lazy->fetch();
279   else if (S->isDefined())
280     checkGlobalType(S, File, Type);
281   return S;
282 }
283 
284 void SymbolTable::addLazy(ArchiveFile *File, const Archive::Symbol *Sym) {
285   DEBUG(dbgs() << "addLazy: " << Sym->getName() << "\n");
286   StringRef Name = Sym->getName();
287 
288   Symbol *S;
289   bool WasInserted;
290   std::tie(S, WasInserted) = insert(Name);
291 
292   if (WasInserted) {
293     replaceSymbol<LazySymbol>(S, Name, File, *Sym);
294     return;
295   }
296 
297   // If there is an existing undefined symbol, load a new one from the archive.
298   if (S->isUndefined()) {
299     DEBUG(dbgs() << "replacing existing undefined\n");
300     File->addMember(Sym);
301   }
302 }
303 
304 bool SymbolTable::addComdat(StringRef Name) {
305   return Comdats.insert(CachedHashStringRef(Name)).second;
306 }
307