1 //===- SymbolTable.cpp ----------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "SymbolTable.h"
10 #include "Config.h"
11 #include "InputChunks.h"
12 #include "InputEvent.h"
13 #include "InputGlobal.h"
14 #include "InputTable.h"
15 #include "WriterUtils.h"
16 #include "lld/Common/ErrorHandler.h"
17 #include "lld/Common/Memory.h"
18 #include "llvm/ADT/SetVector.h"
19
20 #define DEBUG_TYPE "lld"
21
22 using namespace llvm;
23 using namespace llvm::wasm;
24 using namespace llvm::object;
25
26 namespace lld {
27 namespace wasm {
28 SymbolTable *symtab;
29
addFile(InputFile * file)30 void SymbolTable::addFile(InputFile *file) {
31 log("Processing: " + toString(file));
32
33 // .a file
34 if (auto *f = dyn_cast<ArchiveFile>(file)) {
35 f->parse();
36 return;
37 }
38
39 // .so file
40 if (auto *f = dyn_cast<SharedFile>(file)) {
41 sharedFiles.push_back(f);
42 return;
43 }
44
45 if (config->trace)
46 message(toString(file));
47
48 // LLVM bitcode file
49 if (auto *f = dyn_cast<BitcodeFile>(file)) {
50 f->parse();
51 bitcodeFiles.push_back(f);
52 return;
53 }
54
55 // Regular object file
56 auto *f = cast<ObjFile>(file);
57 f->parse(false);
58 objectFiles.push_back(f);
59 }
60
61 // This function is where all the optimizations of link-time
62 // optimization happens. When LTO is in use, some input files are
63 // not in native object file format but in the LLVM bitcode format.
64 // This function compiles bitcode files into a few big native files
65 // using LLVM functions and replaces bitcode symbols with the results.
66 // Because all bitcode files that the program consists of are passed
67 // to the compiler at once, it can do whole-program optimization.
addCombinedLTOObject()68 void SymbolTable::addCombinedLTOObject() {
69 // Prevent further LTO objects being included
70 BitcodeFile::doneLTO = true;
71
72 if (bitcodeFiles.empty())
73 return;
74
75 // Compile bitcode files and replace bitcode symbols.
76 lto.reset(new BitcodeCompiler);
77 for (BitcodeFile *f : bitcodeFiles)
78 lto->add(*f);
79
80 for (StringRef filename : lto->compile()) {
81 auto *obj = make<ObjFile>(MemoryBufferRef(filename, "lto.tmp"), "");
82 obj->parse(true);
83 objectFiles.push_back(obj);
84 }
85 }
86
find(StringRef name)87 Symbol *SymbolTable::find(StringRef name) {
88 auto it = symMap.find(CachedHashStringRef(name));
89 if (it == symMap.end() || it->second == -1)
90 return nullptr;
91 return symVector[it->second];
92 }
93
replace(StringRef name,Symbol * sym)94 void SymbolTable::replace(StringRef name, Symbol* sym) {
95 auto it = symMap.find(CachedHashStringRef(name));
96 symVector[it->second] = sym;
97 }
98
insertName(StringRef name)99 std::pair<Symbol *, bool> SymbolTable::insertName(StringRef name) {
100 bool trace = false;
101 auto p = symMap.insert({CachedHashStringRef(name), (int)symVector.size()});
102 int &symIndex = p.first->second;
103 bool isNew = p.second;
104 if (symIndex == -1) {
105 symIndex = symVector.size();
106 trace = true;
107 isNew = true;
108 }
109
110 if (!isNew)
111 return {symVector[symIndex], false};
112
113 Symbol *sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
114 sym->isUsedInRegularObj = false;
115 sym->canInline = true;
116 sym->traced = trace;
117 sym->forceExport = false;
118 symVector.emplace_back(sym);
119 return {sym, true};
120 }
121
insert(StringRef name,const InputFile * file)122 std::pair<Symbol *, bool> SymbolTable::insert(StringRef name,
123 const InputFile *file) {
124 Symbol *s;
125 bool wasInserted;
126 std::tie(s, wasInserted) = insertName(name);
127
128 if (!file || file->kind() == InputFile::ObjectKind)
129 s->isUsedInRegularObj = true;
130
131 return {s, wasInserted};
132 }
133
reportTypeError(const Symbol * existing,const InputFile * file,llvm::wasm::WasmSymbolType type)134 static void reportTypeError(const Symbol *existing, const InputFile *file,
135 llvm::wasm::WasmSymbolType type) {
136 error("symbol type mismatch: " + toString(*existing) + "\n>>> defined as " +
137 toString(existing->getWasmType()) + " in " +
138 toString(existing->getFile()) + "\n>>> defined as " + toString(type) +
139 " in " + toString(file));
140 }
141
142 // Check the type of new symbol matches that of the symbol is replacing.
143 // Returns true if the function types match, false is there is a signature
144 // mismatch.
signatureMatches(FunctionSymbol * existing,const WasmSignature * newSig)145 static bool signatureMatches(FunctionSymbol *existing,
146 const WasmSignature *newSig) {
147 const WasmSignature *oldSig = existing->signature;
148
149 // If either function is missing a signature (this happend for bitcode
150 // symbols) then assume they match. Any mismatch will be reported later
151 // when the LTO objects are added.
152 if (!newSig || !oldSig)
153 return true;
154
155 return *newSig == *oldSig;
156 }
157
checkGlobalType(const Symbol * existing,const InputFile * file,const WasmGlobalType * newType)158 static void checkGlobalType(const Symbol *existing, const InputFile *file,
159 const WasmGlobalType *newType) {
160 if (!isa<GlobalSymbol>(existing)) {
161 reportTypeError(existing, file, WASM_SYMBOL_TYPE_GLOBAL);
162 return;
163 }
164
165 const WasmGlobalType *oldType = cast<GlobalSymbol>(existing)->getGlobalType();
166 if (*newType != *oldType) {
167 error("Global type mismatch: " + existing->getName() + "\n>>> defined as " +
168 toString(*oldType) + " in " + toString(existing->getFile()) +
169 "\n>>> defined as " + toString(*newType) + " in " + toString(file));
170 }
171 }
172
checkEventType(const Symbol * existing,const InputFile * file,const WasmEventType * newType,const WasmSignature * newSig)173 static void checkEventType(const Symbol *existing, const InputFile *file,
174 const WasmEventType *newType,
175 const WasmSignature *newSig) {
176 auto existingEvent = dyn_cast<EventSymbol>(existing);
177 if (!isa<EventSymbol>(existing)) {
178 reportTypeError(existing, file, WASM_SYMBOL_TYPE_EVENT);
179 return;
180 }
181
182 const WasmEventType *oldType = cast<EventSymbol>(existing)->getEventType();
183 const WasmSignature *oldSig = existingEvent->signature;
184 if (newType->Attribute != oldType->Attribute)
185 error("Event type mismatch: " + existing->getName() + "\n>>> defined as " +
186 toString(*oldType) + " in " + toString(existing->getFile()) +
187 "\n>>> defined as " + toString(*newType) + " in " + toString(file));
188 if (*newSig != *oldSig)
189 warn("Event signature mismatch: " + existing->getName() +
190 "\n>>> defined as " + toString(*oldSig) + " in " +
191 toString(existing->getFile()) + "\n>>> defined as " +
192 toString(*newSig) + " in " + toString(file));
193 }
194
checkTableType(const Symbol * existing,const InputFile * file,const WasmTableType * newType)195 static void checkTableType(const Symbol *existing, const InputFile *file,
196 const WasmTableType *newType) {
197 if (!isa<TableSymbol>(existing)) {
198 reportTypeError(existing, file, WASM_SYMBOL_TYPE_TABLE);
199 return;
200 }
201
202 const WasmTableType *oldType = cast<TableSymbol>(existing)->getTableType();
203 if (newType->ElemType != oldType->ElemType) {
204 error("Table type mismatch: " + existing->getName() + "\n>>> defined as " +
205 toString(*oldType) + " in " + toString(existing->getFile()) +
206 "\n>>> defined as " + toString(*newType) + " in " + toString(file));
207 }
208 // FIXME: No assertions currently on the limits.
209 }
210
checkDataType(const Symbol * existing,const InputFile * file)211 static void checkDataType(const Symbol *existing, const InputFile *file) {
212 if (!isa<DataSymbol>(existing))
213 reportTypeError(existing, file, WASM_SYMBOL_TYPE_DATA);
214 }
215
addSyntheticFunction(StringRef name,uint32_t flags,InputFunction * function)216 DefinedFunction *SymbolTable::addSyntheticFunction(StringRef name,
217 uint32_t flags,
218 InputFunction *function) {
219 LLVM_DEBUG(dbgs() << "addSyntheticFunction: " << name << "\n");
220 assert(!find(name));
221 syntheticFunctions.emplace_back(function);
222 return replaceSymbol<DefinedFunction>(insertName(name).first, name,
223 flags, nullptr, function);
224 }
225
226 // Adds an optional, linker generated, data symbol. The symbol will only be
227 // added if there is an undefine reference to it, or if it is explicitly
228 // exported via the --export flag. Otherwise we don't add the symbol and return
229 // nullptr.
addOptionalDataSymbol(StringRef name,uint64_t value)230 DefinedData *SymbolTable::addOptionalDataSymbol(StringRef name,
231 uint64_t value) {
232 Symbol *s = find(name);
233 if (!s && (config->exportAll || config->exportedSymbols.count(name) != 0))
234 s = insertName(name).first;
235 else if (!s || s->isDefined())
236 return nullptr;
237 LLVM_DEBUG(dbgs() << "addOptionalDataSymbol: " << name << "\n");
238 auto *rtn = replaceSymbol<DefinedData>(s, name, WASM_SYMBOL_VISIBILITY_HIDDEN);
239 rtn->setVirtualAddress(value);
240 rtn->referenced = true;
241 return rtn;
242 }
243
addSyntheticDataSymbol(StringRef name,uint32_t flags)244 DefinedData *SymbolTable::addSyntheticDataSymbol(StringRef name,
245 uint32_t flags) {
246 LLVM_DEBUG(dbgs() << "addSyntheticDataSymbol: " << name << "\n");
247 assert(!find(name));
248 return replaceSymbol<DefinedData>(insertName(name).first, name, flags);
249 }
250
addSyntheticGlobal(StringRef name,uint32_t flags,InputGlobal * global)251 DefinedGlobal *SymbolTable::addSyntheticGlobal(StringRef name, uint32_t flags,
252 InputGlobal *global) {
253 LLVM_DEBUG(dbgs() << "addSyntheticGlobal: " << name << " -> " << global
254 << "\n");
255 assert(!find(name));
256 syntheticGlobals.emplace_back(global);
257 return replaceSymbol<DefinedGlobal>(insertName(name).first, name, flags,
258 nullptr, global);
259 }
260
addOptionalGlobalSymbols(StringRef name,uint32_t flags,InputGlobal * global)261 DefinedGlobal *SymbolTable::addOptionalGlobalSymbols(StringRef name,
262 uint32_t flags,
263 InputGlobal *global) {
264 LLVM_DEBUG(dbgs() << "addOptionalGlobalSymbols: " << name << " -> " << global
265 << "\n");
266 Symbol *s = find(name);
267 if (!s || s->isDefined())
268 return nullptr;
269 syntheticGlobals.emplace_back(global);
270 return replaceSymbol<DefinedGlobal>(s, name, flags, nullptr, global);
271 }
272
addSyntheticTable(StringRef name,uint32_t flags,InputTable * table)273 DefinedTable *SymbolTable::addSyntheticTable(StringRef name, uint32_t flags,
274 InputTable *table) {
275 LLVM_DEBUG(dbgs() << "addSyntheticTable: " << name << " -> " << table
276 << "\n");
277 Symbol *s = find(name);
278 assert(!s || s->isUndefined());
279 if (!s)
280 s = insertName(name).first;
281 syntheticTables.emplace_back(table);
282 return replaceSymbol<DefinedTable>(s, name, flags, nullptr, table);
283 }
284
shouldReplace(const Symbol * existing,InputFile * newFile,uint32_t newFlags)285 static bool shouldReplace(const Symbol *existing, InputFile *newFile,
286 uint32_t newFlags) {
287 // If existing symbol is undefined, replace it.
288 if (!existing->isDefined()) {
289 LLVM_DEBUG(dbgs() << "resolving existing undefined symbol: "
290 << existing->getName() << "\n");
291 return true;
292 }
293
294 // Now we have two defined symbols. If the new one is weak, we can ignore it.
295 if ((newFlags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK) {
296 LLVM_DEBUG(dbgs() << "existing symbol takes precedence\n");
297 return false;
298 }
299
300 // If the existing symbol is weak, we should replace it.
301 if (existing->isWeak()) {
302 LLVM_DEBUG(dbgs() << "replacing existing weak symbol\n");
303 return true;
304 }
305
306 // Neither symbol is week. They conflict.
307 error("duplicate symbol: " + toString(*existing) + "\n>>> defined in " +
308 toString(existing->getFile()) + "\n>>> defined in " +
309 toString(newFile));
310 return true;
311 }
312
addDefinedFunction(StringRef name,uint32_t flags,InputFile * file,InputFunction * function)313 Symbol *SymbolTable::addDefinedFunction(StringRef name, uint32_t flags,
314 InputFile *file,
315 InputFunction *function) {
316 LLVM_DEBUG(dbgs() << "addDefinedFunction: " << name << " ["
317 << (function ? toString(function->signature) : "none")
318 << "]\n");
319 Symbol *s;
320 bool wasInserted;
321 std::tie(s, wasInserted) = insert(name, file);
322
323 auto replaceSym = [&](Symbol *sym) {
324 // If the new defined function doesn't have signature (i.e. bitcode
325 // functions) but the old symbol does, then preserve the old signature
326 const WasmSignature *oldSig = s->getSignature();
327 auto* newSym = replaceSymbol<DefinedFunction>(sym, name, flags, file, function);
328 if (!newSym->signature)
329 newSym->signature = oldSig;
330 };
331
332 if (wasInserted || s->isLazy()) {
333 replaceSym(s);
334 return s;
335 }
336
337 auto existingFunction = dyn_cast<FunctionSymbol>(s);
338 if (!existingFunction) {
339 reportTypeError(s, file, WASM_SYMBOL_TYPE_FUNCTION);
340 return s;
341 }
342
343 bool checkSig = true;
344 if (auto ud = dyn_cast<UndefinedFunction>(existingFunction))
345 checkSig = ud->isCalledDirectly;
346
347 if (checkSig && function && !signatureMatches(existingFunction, &function->signature)) {
348 Symbol* variant;
349 if (getFunctionVariant(s, &function->signature, file, &variant))
350 // New variant, always replace
351 replaceSym(variant);
352 else if (shouldReplace(s, file, flags))
353 // Variant already exists, replace it after checking shouldReplace
354 replaceSym(variant);
355
356 // This variant we found take the place in the symbol table as the primary
357 // variant.
358 replace(name, variant);
359 return variant;
360 }
361
362 // Existing function with matching signature.
363 if (shouldReplace(s, file, flags))
364 replaceSym(s);
365
366 return s;
367 }
368
addDefinedData(StringRef name,uint32_t flags,InputFile * file,InputSegment * segment,uint64_t address,uint64_t size)369 Symbol *SymbolTable::addDefinedData(StringRef name, uint32_t flags,
370 InputFile *file, InputSegment *segment,
371 uint64_t address, uint64_t size) {
372 LLVM_DEBUG(dbgs() << "addDefinedData:" << name << " addr:" << address
373 << "\n");
374 Symbol *s;
375 bool wasInserted;
376 std::tie(s, wasInserted) = insert(name, file);
377
378 auto replaceSym = [&]() {
379 replaceSymbol<DefinedData>(s, name, flags, file, segment, address, size);
380 };
381
382 if (wasInserted || s->isLazy()) {
383 replaceSym();
384 return s;
385 }
386
387 checkDataType(s, file);
388
389 if (shouldReplace(s, file, flags))
390 replaceSym();
391 return s;
392 }
393
addDefinedGlobal(StringRef name,uint32_t flags,InputFile * file,InputGlobal * global)394 Symbol *SymbolTable::addDefinedGlobal(StringRef name, uint32_t flags,
395 InputFile *file, InputGlobal *global) {
396 LLVM_DEBUG(dbgs() << "addDefinedGlobal:" << name << "\n");
397
398 Symbol *s;
399 bool wasInserted;
400 std::tie(s, wasInserted) = insert(name, file);
401
402 auto replaceSym = [&]() {
403 replaceSymbol<DefinedGlobal>(s, name, flags, file, global);
404 };
405
406 if (wasInserted || s->isLazy()) {
407 replaceSym();
408 return s;
409 }
410
411 checkGlobalType(s, file, &global->getType());
412
413 if (shouldReplace(s, file, flags))
414 replaceSym();
415 return s;
416 }
417
addDefinedEvent(StringRef name,uint32_t flags,InputFile * file,InputEvent * event)418 Symbol *SymbolTable::addDefinedEvent(StringRef name, uint32_t flags,
419 InputFile *file, InputEvent *event) {
420 LLVM_DEBUG(dbgs() << "addDefinedEvent:" << name << "\n");
421
422 Symbol *s;
423 bool wasInserted;
424 std::tie(s, wasInserted) = insert(name, file);
425
426 auto replaceSym = [&]() {
427 replaceSymbol<DefinedEvent>(s, name, flags, file, event);
428 };
429
430 if (wasInserted || s->isLazy()) {
431 replaceSym();
432 return s;
433 }
434
435 checkEventType(s, file, &event->getType(), &event->signature);
436
437 if (shouldReplace(s, file, flags))
438 replaceSym();
439 return s;
440 }
441
addDefinedTable(StringRef name,uint32_t flags,InputFile * file,InputTable * table)442 Symbol *SymbolTable::addDefinedTable(StringRef name, uint32_t flags,
443 InputFile *file, InputTable *table) {
444 LLVM_DEBUG(dbgs() << "addDefinedTable:" << name << "\n");
445
446 Symbol *s;
447 bool wasInserted;
448 std::tie(s, wasInserted) = insert(name, file);
449
450 auto replaceSym = [&]() {
451 replaceSymbol<DefinedTable>(s, name, flags, file, table);
452 };
453
454 if (wasInserted || s->isLazy()) {
455 replaceSym();
456 return s;
457 }
458
459 checkTableType(s, file, &table->getType());
460
461 if (shouldReplace(s, file, flags))
462 replaceSym();
463 return s;
464 }
465
466 // This function get called when an undefined symbol is added, and there is
467 // already an existing one in the symbols table. In this case we check that
468 // custom 'import-module' and 'import-field' symbol attributes agree.
469 // With LTO these attributes are not available when the bitcode is read and only
470 // become available when the LTO object is read. In this case we silently
471 // replace the empty attributes with the valid ones.
472 template <typename T>
setImportAttributes(T * existing,Optional<StringRef> importName,Optional<StringRef> importModule,uint32_t flags,InputFile * file)473 static void setImportAttributes(T *existing, Optional<StringRef> importName,
474 Optional<StringRef> importModule,
475 uint32_t flags, InputFile *file) {
476 if (importName) {
477 if (!existing->importName)
478 existing->importName = importName;
479 if (existing->importName != importName)
480 error("import name mismatch for symbol: " + toString(*existing) +
481 "\n>>> defined as " + *existing->importName + " in " +
482 toString(existing->getFile()) + "\n>>> defined as " + *importName +
483 " in " + toString(file));
484 }
485
486 if (importModule) {
487 if (!existing->importModule)
488 existing->importModule = importModule;
489 if (existing->importModule != importModule)
490 error("import module mismatch for symbol: " + toString(*existing) +
491 "\n>>> defined as " + *existing->importModule + " in " +
492 toString(existing->getFile()) + "\n>>> defined as " +
493 *importModule + " in " + toString(file));
494 }
495
496 // Update symbol binding, if the existing symbol is weak
497 uint32_t binding = flags & WASM_SYMBOL_BINDING_MASK;
498 if (existing->isWeak() && binding != WASM_SYMBOL_BINDING_WEAK) {
499 existing->flags = (existing->flags & ~WASM_SYMBOL_BINDING_MASK) | binding;
500 }
501 }
502
addUndefinedFunction(StringRef name,Optional<StringRef> importName,Optional<StringRef> importModule,uint32_t flags,InputFile * file,const WasmSignature * sig,bool isCalledDirectly)503 Symbol *SymbolTable::addUndefinedFunction(StringRef name,
504 Optional<StringRef> importName,
505 Optional<StringRef> importModule,
506 uint32_t flags, InputFile *file,
507 const WasmSignature *sig,
508 bool isCalledDirectly) {
509 LLVM_DEBUG(dbgs() << "addUndefinedFunction: " << name << " ["
510 << (sig ? toString(*sig) : "none")
511 << "] IsCalledDirectly:" << isCalledDirectly << " flags=0x"
512 << utohexstr(flags) << "\n");
513 assert(flags & WASM_SYMBOL_UNDEFINED);
514
515 Symbol *s;
516 bool wasInserted;
517 std::tie(s, wasInserted) = insert(name, file);
518 if (s->traced)
519 printTraceSymbolUndefined(name, file);
520
521 auto replaceSym = [&]() {
522 replaceSymbol<UndefinedFunction>(s, name, importName, importModule, flags,
523 file, sig, isCalledDirectly);
524 };
525
526 if (wasInserted) {
527 replaceSym();
528 } else if (auto *lazy = dyn_cast<LazySymbol>(s)) {
529 if ((flags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK) {
530 lazy->setWeak();
531 lazy->signature = sig;
532 } else {
533 lazy->fetch();
534 }
535 } else {
536 auto existingFunction = dyn_cast<FunctionSymbol>(s);
537 if (!existingFunction) {
538 reportTypeError(s, file, WASM_SYMBOL_TYPE_FUNCTION);
539 return s;
540 }
541 if (!existingFunction->signature && sig)
542 existingFunction->signature = sig;
543 auto *existingUndefined = dyn_cast<UndefinedFunction>(existingFunction);
544 if (isCalledDirectly && !signatureMatches(existingFunction, sig)) {
545 // If the existing undefined functions is not called directly then let
546 // this one take precedence. Otherwise the existing function is either
547 // directly called or defined, in which case we need a function variant.
548 if (existingUndefined && !existingUndefined->isCalledDirectly)
549 replaceSym();
550 else if (getFunctionVariant(s, sig, file, &s))
551 replaceSym();
552 }
553 if (existingUndefined)
554 setImportAttributes(existingUndefined, importName, importModule, flags,
555 file);
556 }
557
558 return s;
559 }
560
addUndefinedData(StringRef name,uint32_t flags,InputFile * file)561 Symbol *SymbolTable::addUndefinedData(StringRef name, uint32_t flags,
562 InputFile *file) {
563 LLVM_DEBUG(dbgs() << "addUndefinedData: " << name << "\n");
564 assert(flags & WASM_SYMBOL_UNDEFINED);
565
566 Symbol *s;
567 bool wasInserted;
568 std::tie(s, wasInserted) = insert(name, file);
569 if (s->traced)
570 printTraceSymbolUndefined(name, file);
571
572 if (wasInserted) {
573 replaceSymbol<UndefinedData>(s, name, flags, file);
574 } else if (auto *lazy = dyn_cast<LazySymbol>(s)) {
575 if ((flags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK)
576 lazy->setWeak();
577 else
578 lazy->fetch();
579 } else if (s->isDefined()) {
580 checkDataType(s, file);
581 }
582 return s;
583 }
584
addUndefinedGlobal(StringRef name,Optional<StringRef> importName,Optional<StringRef> importModule,uint32_t flags,InputFile * file,const WasmGlobalType * type)585 Symbol *SymbolTable::addUndefinedGlobal(StringRef name,
586 Optional<StringRef> importName,
587 Optional<StringRef> importModule,
588 uint32_t flags, InputFile *file,
589 const WasmGlobalType *type) {
590 LLVM_DEBUG(dbgs() << "addUndefinedGlobal: " << name << "\n");
591 assert(flags & WASM_SYMBOL_UNDEFINED);
592
593 Symbol *s;
594 bool wasInserted;
595 std::tie(s, wasInserted) = insert(name, file);
596 if (s->traced)
597 printTraceSymbolUndefined(name, file);
598
599 if (wasInserted)
600 replaceSymbol<UndefinedGlobal>(s, name, importName, importModule, flags,
601 file, type);
602 else if (auto *lazy = dyn_cast<LazySymbol>(s))
603 lazy->fetch();
604 else if (s->isDefined())
605 checkGlobalType(s, file, type);
606 return s;
607 }
608
addUndefinedTable(StringRef name,Optional<StringRef> importName,Optional<StringRef> importModule,uint32_t flags,InputFile * file,const WasmTableType * type)609 Symbol *SymbolTable::addUndefinedTable(StringRef name,
610 Optional<StringRef> importName,
611 Optional<StringRef> importModule,
612 uint32_t flags, InputFile *file,
613 const WasmTableType *type) {
614 LLVM_DEBUG(dbgs() << "addUndefinedTable: " << name << "\n");
615 assert(flags & WASM_SYMBOL_UNDEFINED);
616
617 Symbol *s;
618 bool wasInserted;
619 std::tie(s, wasInserted) = insert(name, file);
620 if (s->traced)
621 printTraceSymbolUndefined(name, file);
622
623 if (wasInserted)
624 replaceSymbol<UndefinedTable>(s, name, importName, importModule, flags,
625 file, type);
626 else if (auto *lazy = dyn_cast<LazySymbol>(s))
627 lazy->fetch();
628 else if (s->isDefined())
629 checkTableType(s, file, type);
630 return s;
631 }
632
addLazy(ArchiveFile * file,const Archive::Symbol * sym)633 void SymbolTable::addLazy(ArchiveFile *file, const Archive::Symbol *sym) {
634 LLVM_DEBUG(dbgs() << "addLazy: " << sym->getName() << "\n");
635 StringRef name = sym->getName();
636
637 Symbol *s;
638 bool wasInserted;
639 std::tie(s, wasInserted) = insertName(name);
640
641 if (wasInserted) {
642 replaceSymbol<LazySymbol>(s, name, 0, file, *sym);
643 return;
644 }
645
646 if (!s->isUndefined())
647 return;
648
649 // The existing symbol is undefined, load a new one from the archive,
650 // unless the existing symbol is weak in which case replace the undefined
651 // symbols with a LazySymbol.
652 if (s->isWeak()) {
653 const WasmSignature *oldSig = nullptr;
654 // In the case of an UndefinedFunction we need to preserve the expected
655 // signature.
656 if (auto *f = dyn_cast<UndefinedFunction>(s))
657 oldSig = f->signature;
658 LLVM_DEBUG(dbgs() << "replacing existing weak undefined symbol\n");
659 auto newSym = replaceSymbol<LazySymbol>(s, name, WASM_SYMBOL_BINDING_WEAK,
660 file, *sym);
661 newSym->signature = oldSig;
662 return;
663 }
664
665 LLVM_DEBUG(dbgs() << "replacing existing undefined\n");
666 file->addMember(sym);
667 }
668
addComdat(StringRef name)669 bool SymbolTable::addComdat(StringRef name) {
670 return comdatGroups.insert(CachedHashStringRef(name)).second;
671 }
672
673 // The new signature doesn't match. Create a variant to the symbol with the
674 // signature encoded in the name and return that instead. These symbols are
675 // then unified later in handleSymbolVariants.
getFunctionVariant(Symbol * sym,const WasmSignature * sig,const InputFile * file,Symbol ** out)676 bool SymbolTable::getFunctionVariant(Symbol* sym, const WasmSignature *sig,
677 const InputFile *file, Symbol **out) {
678 LLVM_DEBUG(dbgs() << "getFunctionVariant: " << sym->getName() << " -> "
679 << " " << toString(*sig) << "\n");
680 Symbol *variant = nullptr;
681
682 // Linear search through symbol variants. Should never be more than two
683 // or three entries here.
684 auto &variants = symVariants[CachedHashStringRef(sym->getName())];
685 if (variants.empty())
686 variants.push_back(sym);
687
688 for (Symbol* v : variants) {
689 if (*v->getSignature() == *sig) {
690 variant = v;
691 break;
692 }
693 }
694
695 bool wasAdded = !variant;
696 if (wasAdded) {
697 // Create a new variant;
698 LLVM_DEBUG(dbgs() << "added new variant\n");
699 variant = reinterpret_cast<Symbol *>(make<SymbolUnion>());
700 variant->isUsedInRegularObj =
701 !file || file->kind() == InputFile::ObjectKind;
702 variant->canInline = true;
703 variant->traced = false;
704 variant->forceExport = false;
705 variants.push_back(variant);
706 } else {
707 LLVM_DEBUG(dbgs() << "variant already exists: " << toString(*variant) << "\n");
708 assert(*variant->getSignature() == *sig);
709 }
710
711 *out = variant;
712 return wasAdded;
713 }
714
715 // Set a flag for --trace-symbol so that we can print out a log message
716 // if a new symbol with the same name is inserted into the symbol table.
trace(StringRef name)717 void SymbolTable::trace(StringRef name) {
718 symMap.insert({CachedHashStringRef(name), -1});
719 }
720
wrap(Symbol * sym,Symbol * real,Symbol * wrap)721 void SymbolTable::wrap(Symbol *sym, Symbol *real, Symbol *wrap) {
722 // Swap symbols as instructed by -wrap.
723 int &origIdx = symMap[CachedHashStringRef(sym->getName())];
724 int &realIdx= symMap[CachedHashStringRef(real->getName())];
725 int &wrapIdx = symMap[CachedHashStringRef(wrap->getName())];
726 LLVM_DEBUG(dbgs() << "wrap: " << sym->getName() << "\n");
727
728 // Anyone looking up __real symbols should get the original
729 realIdx = origIdx;
730 // Anyone looking up the original should get the __wrap symbol
731 origIdx = wrapIdx;
732 }
733
734 static const uint8_t unreachableFn[] = {
735 0x03 /* ULEB length */, 0x00 /* ULEB num locals */,
736 0x00 /* opcode unreachable */, 0x0b /* opcode end */
737 };
738
739 // Replace the given symbol body with an unreachable function.
740 // This is used by handleWeakUndefines in order to generate a callable
741 // equivalent of an undefined function and also handleSymbolVariants for
742 // undefined functions that don't match the signature of the definition.
replaceWithUnreachable(Symbol * sym,const WasmSignature & sig,StringRef debugName)743 InputFunction *SymbolTable::replaceWithUnreachable(Symbol *sym,
744 const WasmSignature &sig,
745 StringRef debugName) {
746 auto *func = make<SyntheticFunction>(sig, sym->getName(), debugName);
747 func->setBody(unreachableFn);
748 syntheticFunctions.emplace_back(func);
749 // Mark new symbols as local. For relocatable output we don't want them
750 // to be exported outside the object file.
751 replaceSymbol<DefinedFunction>(sym, debugName, WASM_SYMBOL_BINDING_LOCAL,
752 nullptr, func);
753 // Ensure the stub function doesn't get a table entry. Its address
754 // should always compare equal to the null pointer.
755 sym->isStub = true;
756 return func;
757 }
758
replaceWithUndefined(Symbol * sym)759 void SymbolTable::replaceWithUndefined(Symbol *sym) {
760 // Add a synthetic dummy for weak undefined functions. These dummies will
761 // be GC'd if not used as the target of any "call" instructions.
762 StringRef debugName = saver.save("undefined_weak:" + toString(*sym));
763 replaceWithUnreachable(sym, *sym->getSignature(), debugName);
764 // Hide our dummy to prevent export.
765 sym->setHidden(true);
766 }
767
768 // For weak undefined functions, there may be "call" instructions that reference
769 // the symbol. In this case, we need to synthesise a dummy/stub function that
770 // will abort at runtime, so that relocations can still provided an operand to
771 // the call instruction that passes Wasm validation.
handleWeakUndefines()772 void SymbolTable::handleWeakUndefines() {
773 for (Symbol *sym : getSymbols()) {
774 if (sym->isUndefWeak()) {
775 if (sym->getSignature()) {
776 replaceWithUndefined(sym);
777 } else {
778 // It is possible for undefined functions not to have a signature (eg.
779 // if added via "--undefined"), but weak undefined ones do have a
780 // signature. Lazy symbols may not be functions and therefore Sig can
781 // still be null in some circumstance.
782 assert(!isa<FunctionSymbol>(sym));
783 }
784 }
785 }
786 }
787
createUndefinedStub(const WasmSignature & sig)788 DefinedFunction *SymbolTable::createUndefinedStub(const WasmSignature &sig) {
789 if (stubFunctions.count(sig))
790 return stubFunctions[sig];
791 LLVM_DEBUG(dbgs() << "createUndefinedStub: " << toString(sig) << "\n");
792 auto *sym = reinterpret_cast<DefinedFunction *>(make<SymbolUnion>());
793 sym->isUsedInRegularObj = true;
794 sym->canInline = true;
795 sym->traced = false;
796 sym->forceExport = false;
797 sym->signature = &sig;
798 replaceSymbol<DefinedFunction>(
799 sym, "undefined_stub", WASM_SYMBOL_VISIBILITY_HIDDEN, nullptr, nullptr);
800 replaceWithUnreachable(sym, sig, "undefined_stub");
801 stubFunctions[sig] = sym;
802 return sym;
803 }
804
reportFunctionSignatureMismatch(StringRef symName,FunctionSymbol * a,FunctionSymbol * b,bool isError)805 static void reportFunctionSignatureMismatch(StringRef symName,
806 FunctionSymbol *a,
807 FunctionSymbol *b, bool isError) {
808 std::string msg = ("function signature mismatch: " + symName +
809 "\n>>> defined as " + toString(*a->signature) + " in " +
810 toString(a->getFile()) + "\n>>> defined as " +
811 toString(*b->signature) + " in " + toString(b->getFile()))
812 .str();
813 if (isError)
814 error(msg);
815 else
816 warn(msg);
817 }
818
819 // Remove any variant symbols that were created due to function signature
820 // mismatches.
handleSymbolVariants()821 void SymbolTable::handleSymbolVariants() {
822 for (auto pair : symVariants) {
823 // Push the initial symbol onto the list of variants.
824 StringRef symName = pair.first.val();
825 std::vector<Symbol *> &variants = pair.second;
826
827 #ifndef NDEBUG
828 LLVM_DEBUG(dbgs() << "symbol with (" << variants.size()
829 << ") variants: " << symName << "\n");
830 for (auto *s: variants) {
831 auto *f = cast<FunctionSymbol>(s);
832 LLVM_DEBUG(dbgs() << " variant: " + f->getName() << " "
833 << toString(*f->signature) << "\n");
834 }
835 #endif
836
837 // Find the one definition.
838 DefinedFunction *defined = nullptr;
839 for (auto *symbol : variants) {
840 if (auto f = dyn_cast<DefinedFunction>(symbol)) {
841 defined = f;
842 break;
843 }
844 }
845
846 // If there are no definitions, and the undefined symbols disagree on
847 // the signature, there is not we can do since we don't know which one
848 // to use as the signature on the import.
849 if (!defined) {
850 reportFunctionSignatureMismatch(symName,
851 cast<FunctionSymbol>(variants[0]),
852 cast<FunctionSymbol>(variants[1]), true);
853 return;
854 }
855
856 for (auto *symbol : variants) {
857 if (symbol != defined) {
858 auto *f = cast<FunctionSymbol>(symbol);
859 reportFunctionSignatureMismatch(symName, f, defined, false);
860 StringRef debugName = saver.save("signature_mismatch:" + toString(*f));
861 replaceWithUnreachable(f, *f->signature, debugName);
862 }
863 }
864 }
865 }
866
867 } // namespace wasm
868 } // namespace lld
869