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 "Strings.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 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   std::unordered_set<Symbol *> Undefs;
38   for (auto &I : SymMap) {
39     Symbol *Sym = I.second;
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   return {Sym, true};
72 }
73 
74 void SymbolTable::reportDuplicate(Symbol *Existing, InputFile *NewFile) {
75   error("duplicate symbol: " + toString(*Existing) + "\n>>> defined in " +
76         toString(Existing->getFile()) + "\n>>> defined in " +
77         toString(NewFile));
78 }
79 
80 // Get the signature for a given function symbol, either by looking
81 // it up in function sections (for defined functions), of the imports section
82 // (for imported functions).
83 static const WasmSignature *getFunctionSig(const ObjFile &Obj,
84                                            const WasmSymbol &Sym) {
85   DEBUG(dbgs() << "getFunctionSig: " << Sym.Name << "\n");
86   const WasmObjectFile *WasmObj = Obj.getWasmObj();
87   uint32_t FunctionType;
88   if (Obj.isImportedFunction(Sym.ElementIndex)) {
89     const WasmImport &Import = WasmObj->imports()[Sym.ImportIndex];
90     FunctionType = Import.SigIndex;
91   } else {
92     uint32_t FuntionIndex = Sym.ElementIndex - Obj.NumFunctionImports();
93     FunctionType = WasmObj->functionTypes()[FuntionIndex];
94   }
95   return &WasmObj->types()[FunctionType];
96 }
97 
98 // Check the type of new symbol matches that of the symbol is replacing.
99 // For functions this can also involve verifying that the signatures match.
100 static void checkSymbolTypes(const Symbol &Existing, const InputFile &F,
101                              const WasmSymbol &New,
102                              const WasmSignature *NewSig) {
103   if (Existing.isLazy())
104     return;
105 
106   bool NewIsFunction = New.Type == WasmSymbol::SymbolType::FUNCTION_EXPORT ||
107                        New.Type == WasmSymbol::SymbolType::FUNCTION_IMPORT;
108 
109   // First check the symbol types match (i.e. either both are function
110   // symbols or both are data symbols).
111   if (Existing.isFunction() != NewIsFunction) {
112     error("symbol type mismatch: " + New.Name + "\n>>> defined as " +
113           (Existing.isFunction() ? "Function" : "Global") + " in " +
114           toString(Existing.getFile()) + "\n>>> defined as " +
115           (NewIsFunction ? "Function" : "Global") + " in " + F.getName());
116     return;
117   }
118 
119   // For function symbols, optionally check the function signature matches too.
120   if (!NewIsFunction || !Config->CheckSignatures)
121     return;
122 
123   DEBUG(dbgs() << "checkSymbolTypes: " << New.Name << "\n");
124   assert(NewSig);
125 
126   const WasmSignature &OldSig = Existing.getFunctionType();
127   if (*NewSig == OldSig)
128     return;
129 
130   error("function signature mismatch: " + New.Name + "\n>>> defined as " +
131         toString(OldSig) + " in " + toString(Existing.getFile()) +
132         "\n>>> defined as " + toString(*NewSig) + " in " + F.getName());
133 }
134 
135 Symbol *SymbolTable::addDefinedGlobal(StringRef Name) {
136   DEBUG(dbgs() << "addDefinedGlobal: " << Name << "\n");
137   Symbol *S;
138   bool WasInserted;
139   std::tie(S, WasInserted) = insert(Name);
140   if (WasInserted)
141     S->update(Symbol::DefinedGlobalKind);
142   else if (!S->isGlobal())
143     error("symbol type mismatch: " + Name);
144   return S;
145 }
146 
147 Symbol *SymbolTable::addDefined(InputFile *F, const WasmSymbol *Sym,
148                                 const InputSegment *Segment) {
149   DEBUG(dbgs() << "addDefined: " << Sym->Name << "\n");
150   Symbol *S;
151   bool WasInserted;
152   Symbol::Kind Kind = Symbol::DefinedFunctionKind;
153   const WasmSignature *NewSig = nullptr;
154   if (Sym->Type == WasmSymbol::SymbolType::GLOBAL_EXPORT)
155     Kind = Symbol::DefinedGlobalKind;
156   else
157     NewSig = getFunctionSig(*cast<ObjFile>(F), *Sym);
158 
159   std::tie(S, WasInserted) = insert(Sym->Name);
160   if (WasInserted) {
161     S->update(Kind, F, Sym, Segment, NewSig);
162   } else if (S->isLazy()) {
163     // The existing symbol is lazy. Replace it without checking types since
164     // lazy symbols don't have any type information.
165     DEBUG(dbgs() << "replacing existing lazy symbol: " << Sym->Name << "\n");
166     S->update(Kind, F, Sym, Segment, NewSig);
167   } else if (!S->isDefined()) {
168     // The existing symbol table entry is undefined. The new symbol replaces
169     // it, after checkign the type matches
170     DEBUG(dbgs() << "resolving existing undefined symbol: " << Sym->Name
171                  << "\n");
172     checkSymbolTypes(*S, *F, *Sym, NewSig);
173     S->update(Kind, F, Sym, Segment, NewSig);
174   } else if (Sym->isWeak()) {
175     // the new symbol is weak we can ignore it
176     DEBUG(dbgs() << "existing symbol takes precensence\n");
177   } else if (S->isWeak()) {
178     // the new symbol is not weak and the existing symbol is, so we replace
179     // it
180     DEBUG(dbgs() << "replacing existing weak symbol\n");
181     checkSymbolTypes(*S, *F, *Sym, NewSig);
182     S->update(Kind, F, Sym, Segment, NewSig);
183   } else {
184     // niether symbol is week. They conflict.
185     reportDuplicate(S, F);
186   }
187   return S;
188 }
189 
190 Symbol *SymbolTable::addUndefinedFunction(StringRef Name,
191                                           const WasmSignature *Type) {
192   Symbol *S;
193   bool WasInserted;
194   std::tie(S, WasInserted) = insert(Name);
195   if (WasInserted) {
196     S->update(Symbol::UndefinedFunctionKind, nullptr, nullptr, nullptr, Type);
197   } else if (!S->isFunction()) {
198     error("symbol type mismatch: " + Name);
199   }
200   return S;
201 }
202 
203 Symbol *SymbolTable::addUndefined(InputFile *F, const WasmSymbol *Sym) {
204   DEBUG(dbgs() << "addUndefined: " << displayName(Sym->Name) << "\n");
205   Symbol *S;
206   bool WasInserted;
207   Symbol::Kind Kind = Symbol::UndefinedFunctionKind;
208   const WasmSignature *NewSig = nullptr;
209   if (Sym->Type == WasmSymbol::SymbolType::GLOBAL_IMPORT)
210     Kind = Symbol::UndefinedGlobalKind;
211   else
212     NewSig = getFunctionSig(*cast<ObjFile>(F), *Sym);
213   std::tie(S, WasInserted) = insert(Sym->Name);
214   if (WasInserted) {
215     S->update(Kind, F, Sym, nullptr, NewSig);
216   } else if (S->isLazy()) {
217     DEBUG(dbgs() << "resolved by existing lazy\n");
218     auto *AF = cast<ArchiveFile>(S->getFile());
219     AF->addMember(&S->getArchiveSymbol());
220   } else if (S->isDefined()) {
221     DEBUG(dbgs() << "resolved by existing\n");
222     checkSymbolTypes(*S, *F, *Sym, NewSig);
223   }
224   return S;
225 }
226 
227 void SymbolTable::addLazy(ArchiveFile *F, const Archive::Symbol *Sym) {
228   DEBUG(dbgs() << "addLazy: " << displayName(Sym->getName()) << "\n");
229   StringRef Name = Sym->getName();
230   Symbol *S;
231   bool WasInserted;
232   std::tie(S, WasInserted) = insert(Name);
233   if (WasInserted) {
234     S->update(Symbol::LazyKind, F);
235     S->setArchiveSymbol(*Sym);
236   } else if (S->isUndefined()) {
237     // There is an existing undefined symbol.  The can load from the
238     // archive.
239     DEBUG(dbgs() << "replacing existing undefined\n");
240     F->addMember(Sym);
241   }
242 }
243