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 #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   auto It = SymMap.find(CachedHashStringRef(Name));
60   if (It == SymMap.end())
61     return nullptr;
62   return It->second;
63 }
64 
65 std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name) {
66   Symbol *&Sym = SymMap[CachedHashStringRef(Name)];
67   if (Sym)
68     return {Sym, false};
69   Sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
70   SymVector.emplace_back(Sym);
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 // Check the type of new symbol matches that of the symbol is replacing.
81 // For functions this can also involve verifying that the signatures match.
82 static void checkSymbolTypes(const Symbol &Existing, const InputFile &F,
83                              bool NewIsFunction, const WasmSignature *NewSig) {
84   if (Existing.isLazy())
85     return;
86 
87   // First check the symbol types match (i.e. either both are function
88   // symbols or both are data symbols).
89   if (Existing.isFunction() != NewIsFunction) {
90     error("symbol type mismatch: " + Existing.getName() + "\n>>> defined as " +
91           (Existing.isFunction() ? "Function" : "Global") + " in " +
92           toString(Existing.getFile()) + "\n>>> defined as " +
93           (NewIsFunction ? "Function" : "Global") + " in " + F.getName());
94     return;
95   }
96 
97   // For function symbols, optionally check the function signature matches too.
98   auto *ExistingFunc = dyn_cast<FunctionSymbol>(&Existing);
99   if (!ExistingFunc || !Config->CheckSignatures)
100     return;
101 
102   // Skip the signature check if the existing function has no signature (e.g.
103   // if it is an undefined symbol generated by --undefined command line flag).
104   if (!ExistingFunc->hasFunctionType())
105     return;
106 
107   DEBUG(dbgs() << "checkSymbolTypes: " << ExistingFunc->getName() << "\n");
108   assert(NewSig);
109 
110   const WasmSignature &OldSig = ExistingFunc->getFunctionType();
111   if (*NewSig == OldSig)
112     return;
113 
114   error("function signature mismatch: " + ExistingFunc->getName() +
115         "\n>>> defined as " + toString(OldSig) + " in " +
116         toString(ExistingFunc->getFile()) + "\n>>> defined as " +
117         toString(*NewSig) + " in " + F.getName());
118 }
119 
120 static void checkSymbolTypes(const Symbol &Existing, const InputFile &F,
121                              bool IsFunction, const InputChunk *Chunk) {
122   const WasmSignature *Sig = nullptr;
123   if (auto *F = dyn_cast_or_null<InputFunction>(Chunk))
124     Sig = &F->Signature;
125   return checkSymbolTypes(Existing, F, IsFunction, Sig);
126 }
127 
128 DefinedFunction *SymbolTable::addSyntheticFunction(StringRef Name,
129                                                    const WasmSignature *Type,
130                                                    uint32_t Flags) {
131   DEBUG(dbgs() << "addSyntheticFunction: " << Name << "\n");
132   Symbol *S;
133   bool WasInserted;
134   std::tie(S, WasInserted) = insert(Name);
135   assert(WasInserted);
136   return replaceSymbol<DefinedFunction>(S, Name, Flags, Type);
137 }
138 
139 DefinedGlobal *SymbolTable::addSyntheticGlobal(StringRef Name, uint32_t Flags) {
140   DEBUG(dbgs() << "addSyntheticGlobal: " << Name << "\n");
141   Symbol *S;
142   bool WasInserted;
143   std::tie(S, WasInserted) = insert(Name);
144   assert(WasInserted);
145   return replaceSymbol<DefinedGlobal>(S, Name, Flags);
146 }
147 
148 Symbol *SymbolTable::addDefined(bool IsFunction, StringRef Name, uint32_t Flags,
149                                 InputFile *F, InputChunk *Chunk,
150                                 uint32_t Address) {
151   if (IsFunction)
152     DEBUG(dbgs() << "addDefined: func:" << Name << "\n");
153   else
154     DEBUG(dbgs() << "addDefined: global:" << Name << " addr:" << Address
155                  << "\n");
156   Symbol *S;
157   bool WasInserted;
158   bool Replace = false;
159   bool CheckTypes = false;
160 
161   std::tie(S, WasInserted) = insert(Name);
162   if (WasInserted) {
163     Replace = true;
164   } else if (S->isLazy()) {
165     // Existing symbol is lazy. Replace it without checking types since
166     // lazy symbols don't have any type information.
167     DEBUG(dbgs() << "replacing existing lazy symbol: " << Name << "\n");
168     Replace = true;
169   } else if (!S->isDefined()) {
170     // Existing symbol is undefined: replace it, while check types.
171     DEBUG(dbgs() << "resolving existing undefined symbol: " << Name << "\n");
172     Replace = true;
173     CheckTypes = true;
174   } else if ((Flags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK) {
175     // the new symbol is weak we can ignore it
176     DEBUG(dbgs() << "existing symbol takes precedence\n");
177   } else if (S->isWeak()) {
178     // the existing symbol is, so we replace it
179     DEBUG(dbgs() << "replacing existing weak symbol\n");
180     Replace = true;
181     CheckTypes = true;
182   } else {
183     // neither symbol is week. They conflict.
184     reportDuplicate(S, F);
185   }
186 
187   if (Replace) {
188     if (CheckTypes)
189       checkSymbolTypes(*S, *F, IsFunction, Chunk);
190     if (IsFunction)
191       replaceSymbol<DefinedFunction>(S, Name, Flags, F, Chunk);
192     else
193       replaceSymbol<DefinedGlobal>(S, Name, Flags, F, Chunk, Address);
194   }
195   return S;
196 }
197 
198 Symbol *SymbolTable::addUndefined(StringRef Name, Symbol::Kind Kind,
199                                   uint32_t Flags, InputFile *F,
200                                   const WasmSignature *Type) {
201   DEBUG(dbgs() << "addUndefined: " << Name << "\n");
202   Symbol *S;
203   bool WasInserted;
204   std::tie(S, WasInserted) = insert(Name);
205   bool IsFunction = Kind == Symbol::UndefinedFunctionKind;
206   if (WasInserted) {
207     if (IsFunction)
208       replaceSymbol<UndefinedFunction>(S, Name, Flags, F, Type);
209     else
210       replaceSymbol<UndefinedGlobal>(S, Name, Flags, F);
211   } else if (auto *LazySym = dyn_cast<LazySymbol>(S)) {
212     DEBUG(dbgs() << "resolved by existing lazy\n");
213     auto *AF = cast<ArchiveFile>(LazySym->getFile());
214     AF->addMember(&LazySym->getArchiveSymbol());
215   } else if (S->isDefined()) {
216     DEBUG(dbgs() << "resolved by existing\n");
217     checkSymbolTypes(*S, *F, IsFunction, Type);
218   }
219   return S;
220 }
221 
222 void SymbolTable::addLazy(ArchiveFile *F, const Archive::Symbol *Sym) {
223   DEBUG(dbgs() << "addLazy: " << Sym->getName() << "\n");
224   StringRef Name = Sym->getName();
225   Symbol *S;
226   bool WasInserted;
227   std::tie(S, WasInserted) = insert(Name);
228   if (WasInserted) {
229     replaceSymbol<LazySymbol>(S, Name, F, *Sym);
230   } else if (S->isUndefined()) {
231     // There is an existing undefined symbol.  The can load from the
232     // archive.
233     DEBUG(dbgs() << "replacing existing undefined\n");
234     F->addMember(Sym);
235   }
236 }
237 
238 bool SymbolTable::addComdat(StringRef Name, ObjFile *F) {
239   DEBUG(dbgs() << "addComdat: " << Name << "\n");
240   ObjFile *&File = ComdatMap[CachedHashStringRef(Name)];
241   if (File) {
242     DEBUG(dbgs() << "COMDAT already defined\n");
243     return false;
244   }
245   File = F;
246   return true;
247 }
248 
249 ObjFile *SymbolTable::findComdat(StringRef Name) const {
250   auto It = ComdatMap.find(CachedHashStringRef(Name));
251   return It == ComdatMap.end() ? nullptr : It->second;
252 }
253