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