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 
12 #include "Config.h"
13 #include "InputChunks.h"
14 #include "WriterUtils.h"
15 #include "lld/Common/ErrorHandler.h"
16 #include "lld/Common/Memory.h"
17 
18 #include <unordered_set>
19 
20 #define DEBUG_TYPE "lld"
21 
22 using namespace llvm;
23 using namespace llvm::wasm;
24 using namespace lld;
25 using namespace lld::wasm;
26 
27 SymbolTable *lld::wasm::Symtab;
28 
29 void SymbolTable::addFile(InputFile *File) {
30   log("Processing: " + toString(File));
31   File->parse();
32 
33   if (auto *F = dyn_cast<ObjFile>(File))
34     ObjectFiles.push_back(F);
35 }
36 
37 void SymbolTable::reportRemainingUndefines() {
38   std::unordered_set<Symbol *> Undefs;
39   for (Symbol *Sym : SymVector) {
40     if (Sym->isUndefined() && !Sym->isWeak() &&
41         Config->AllowUndefinedSymbols.count(Sym->getName()) == 0) {
42       Undefs.insert(Sym);
43     }
44   }
45 
46   if (Undefs.empty())
47     return;
48 
49   for (ObjFile *File : ObjectFiles)
50     for (Symbol *Sym : File->getSymbols())
51       if (Undefs.count(Sym))
52         error(toString(File) + ": undefined symbol: " + toString(*Sym));
53 
54   for (Symbol *Sym : Undefs)
55     if (!Sym->getFile())
56       error("undefined symbol: " + toString(*Sym));
57 }
58 
59 Symbol *SymbolTable::find(StringRef Name) {
60   auto It = SymMap.find(CachedHashStringRef(Name));
61   if (It == SymMap.end())
62     return nullptr;
63   return It->second;
64 }
65 
66 std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name) {
67   Symbol *&Sym = SymMap[CachedHashStringRef(Name)];
68   if (Sym)
69     return {Sym, false};
70   Sym = make<Symbol>(Name, false);
71   SymVector.emplace_back(Sym);
72   return {Sym, true};
73 }
74 
75 void SymbolTable::reportDuplicate(Symbol *Existing, InputFile *NewFile) {
76   error("duplicate symbol: " + toString(*Existing) + "\n>>> defined in " +
77         toString(Existing->getFile()) + "\n>>> defined in " +
78         toString(NewFile));
79 }
80 
81 // Check the type of new symbol matches that of the symbol is replacing.
82 // For functions this can also involve verifying that the signatures match.
83 static void checkSymbolTypes(const Symbol &Existing, const InputFile &F,
84                              Symbol::Kind Kind, const WasmSignature *NewSig) {
85   if (Existing.isLazy())
86     return;
87 
88   bool NewIsFunction = Kind == Symbol::Kind::UndefinedFunctionKind ||
89                        Kind == Symbol::Kind::DefinedFunctionKind;
90 
91   // First check the symbol types match (i.e. either both are function
92   // symbols or both are data symbols).
93   if (Existing.isFunction() != NewIsFunction) {
94     error("symbol type mismatch: " + Existing.getName() + "\n>>> defined as " +
95           (Existing.isFunction() ? "Function" : "Global") + " in " +
96           toString(Existing.getFile()) + "\n>>> defined as " +
97           (NewIsFunction ? "Function" : "Global") + " in " + F.getName());
98     return;
99   }
100 
101   // For function symbols, optionally check the function signature matches too.
102   if (!NewIsFunction || !Config->CheckSignatures)
103     return;
104   // Skip the signature check if the existing function has no signature (e.g.
105   // if it is an undefined symbol generated by --undefined command line flag).
106   if (!Existing.hasFunctionType())
107     return;
108 
109   DEBUG(dbgs() << "checkSymbolTypes: " << Existing.getName() << "\n");
110   assert(NewSig);
111 
112   const WasmSignature &OldSig = Existing.getFunctionType();
113   if (*NewSig == OldSig)
114     return;
115 
116   error("function signature mismatch: " + Existing.getName() +
117         "\n>>> defined as " + toString(OldSig) + " in " +
118         toString(Existing.getFile()) + "\n>>> defined as " + toString(*NewSig) +
119         " in " + F.getName());
120 }
121 
122 static void checkSymbolTypes(const Symbol &Existing, const InputFile &F,
123                              Symbol::Kind Kind, const InputChunk *Chunk) {
124   const WasmSignature *Sig = nullptr;
125   if (auto *F = dyn_cast_or_null<InputFunction>(Chunk))
126     Sig = &F->Signature;
127   return checkSymbolTypes(Existing, F, Kind, Sig);
128 }
129 
130 Symbol *SymbolTable::addDefinedFunction(StringRef Name,
131                                         const WasmSignature *Type,
132                                         uint32_t Flags) {
133   DEBUG(dbgs() << "addDefinedFunction: " << Name << "\n");
134   Symbol *S;
135   bool WasInserted;
136   std::tie(S, WasInserted) = insert(Name);
137   if (WasInserted) {
138     S->update(Symbol::DefinedFunctionKind, nullptr, Flags);
139     S->setFunctionType(Type);
140   } else if (!S->isFunction()) {
141     error("symbol type mismatch: " + Name);
142   } else if (!S->isDefined()) {
143     DEBUG(dbgs() << "resolving existing undefined function: " << Name << "\n");
144     S->update(Symbol::DefinedFunctionKind, nullptr, Flags);
145   }
146   return S;
147 }
148 
149 Symbol *SymbolTable::addDefinedGlobal(StringRef Name) {
150   DEBUG(dbgs() << "addDefinedGlobal: " << Name << "\n");
151   Symbol *S;
152   bool WasInserted;
153   std::tie(S, WasInserted) = insert(Name);
154   if (WasInserted) {
155     S->update(Symbol::DefinedGlobalKind);
156   } else if (!S->isGlobal()) {
157     error("symbol type mismatch: " + Name);
158   } else {
159     DEBUG(dbgs() << "resolving existing undefined global: " << Name << "\n");
160     S->update(Symbol::DefinedGlobalKind);
161   }
162   return S;
163 }
164 
165 Symbol *SymbolTable::addDefined(StringRef Name, Symbol::Kind Kind,
166                                 uint32_t Flags, InputFile *F, InputChunk *Chunk,
167                                 uint32_t Address) {
168   DEBUG(dbgs() << "addDefined: " << Name << " addr:" << Address << "\n");
169   Symbol *S;
170   bool WasInserted;
171 
172   std::tie(S, WasInserted) = insert(Name);
173   if (WasInserted) {
174     S->update(Kind, F, Flags, Chunk, Address);
175   } else if (S->isLazy()) {
176     // The existing symbol is lazy. Replace it without checking types since
177     // lazy symbols don't have any type information.
178     DEBUG(dbgs() << "replacing existing lazy symbol: " << Name << "\n");
179     S->update(Kind, F, Flags, Chunk, Address);
180   } else if (!S->isDefined()) {
181     // The existing symbol table entry is undefined. The new symbol replaces
182     // it, after checking the type matches
183     DEBUG(dbgs() << "resolving existing undefined symbol: " << Name << "\n");
184     checkSymbolTypes(*S, *F, Kind, Chunk);
185     S->update(Kind, F, Flags, Chunk, Address);
186   } else if ((Flags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK) {
187     // the new symbol is weak we can ignore it
188     DEBUG(dbgs() << "existing symbol takes precedence\n");
189   } else if (S->isWeak()) {
190     // the new symbol is not weak and the existing symbol is, so we replace
191     // it
192     DEBUG(dbgs() << "replacing existing weak symbol\n");
193     checkSymbolTypes(*S, *F, Kind, Chunk);
194     S->update(Kind, F, Flags, Chunk, Address);
195   } else {
196     // neither symbol is week. They conflict.
197     reportDuplicate(S, F);
198   }
199   return S;
200 }
201 
202 Symbol *SymbolTable::addUndefinedFunction(StringRef Name,
203                                           const WasmSignature *Type) {
204   DEBUG(dbgs() << "addUndefinedFunction: " << Name << "\n");
205   Symbol *S;
206   bool WasInserted;
207   std::tie(S, WasInserted) = insert(Name);
208   if (WasInserted) {
209     S->update(Symbol::UndefinedFunctionKind);
210     S->setFunctionType(Type);
211   } else if (!S->isFunction()) {
212     error("symbol type mismatch: " + Name);
213   }
214   return S;
215 }
216 
217 Symbol *SymbolTable::addUndefined(StringRef Name, Symbol::Kind Kind,
218                                   uint32_t Flags, InputFile *F,
219                                   const WasmSignature *Type) {
220   DEBUG(dbgs() << "addUndefined: " << Name << "\n");
221   Symbol *S;
222   bool WasInserted;
223   std::tie(S, WasInserted) = insert(Name);
224   if (WasInserted) {
225     S->update(Kind, F, Flags);
226     if (Type)
227       S->setFunctionType(Type);
228   } else if (S->isLazy()) {
229     DEBUG(dbgs() << "resolved by existing lazy\n");
230     auto *AF = cast<ArchiveFile>(S->getFile());
231     AF->addMember(&S->getArchiveSymbol());
232   } else if (S->isDefined()) {
233     DEBUG(dbgs() << "resolved by existing\n");
234     checkSymbolTypes(*S, *F, Kind, Type);
235   }
236   return S;
237 }
238 
239 void SymbolTable::addLazy(ArchiveFile *F, const Archive::Symbol *Sym) {
240   DEBUG(dbgs() << "addLazy: " << Sym->getName() << "\n");
241   StringRef Name = Sym->getName();
242   Symbol *S;
243   bool WasInserted;
244   std::tie(S, WasInserted) = insert(Name);
245   if (WasInserted) {
246     S->update(Symbol::LazyKind, F);
247     S->setArchiveSymbol(*Sym);
248   } else if (S->isUndefined()) {
249     // There is an existing undefined symbol.  The can load from the
250     // archive.
251     DEBUG(dbgs() << "replacing existing undefined\n");
252     F->addMember(Sym);
253   }
254 }
255 
256 bool SymbolTable::addComdat(StringRef Name, ObjFile *F) {
257   DEBUG(dbgs() << "addComdat: " << Name << "\n");
258   ObjFile *&File = ComdatMap[CachedHashStringRef(Name)];
259   if (File) {
260     DEBUG(dbgs() << "COMDAT already defined\n");
261     return false;
262   }
263   File = F;
264   return true;
265 }
266 
267 ObjFile *SymbolTable::findComdat(StringRef Name) const {
268   auto It = ComdatMap.find(CachedHashStringRef(Name));
269   return It == ComdatMap.end() ? nullptr : It->second;
270 }
271