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 "InputElement.h"
13#include "WriterUtils.h"
14#include "lld/Common/CommonLinkerContext.h"
15#include <optional>
16
17#define DEBUG_TYPE "lld"
18
19using namespace llvm;
20using namespace llvm::wasm;
21using namespace llvm::object;
22
23namespace lld::wasm {
24SymbolTable *symtab;
25
26void SymbolTable::addFile(InputFile *file, StringRef symName) {
27 log(msg: "Processing: " + toString(file));
28
29 // Lazy object file
30 if (file->lazy) {
31 if (auto *f = dyn_cast<BitcodeFile>(Val: file)) {
32 ctx.lazyBitcodeFiles.push_back(Elt: f);
33 f->parseLazy();
34 } else {
35 cast<ObjFile>(Val: file)->parseLazy();
36 }
37 return;
38 }
39
40 // .so file
41 if (auto *f = dyn_cast<SharedFile>(Val: file)) {
42 // If we are not reporting undefined symbols that we don't actualy
43 // parse the shared library symbol table.
44 f->parse();
45 ctx.sharedFiles.push_back(Elt: f);
46 return;
47 }
48
49 // stub file
50 if (auto *f = dyn_cast<StubFile>(Val: file)) {
51 f->parse();
52 ctx.stubFiles.push_back(Elt: f);
53 return;
54 }
55
56 if (ctx.arg.trace)
57 message(msg: toString(file));
58
59 // LLVM bitcode file
60 if (auto *f = dyn_cast<BitcodeFile>(Val: file)) {
61 // This order, first adding to `bitcodeFiles` and then parsing is necessary.
62 // See https://github.com/llvm/llvm-project/pull/73095
63 ctx.bitcodeFiles.push_back(Elt: f);
64 f->parse(symName);
65 return;
66 }
67
68 // Regular object file
69 auto *f = cast<ObjFile>(Val: file);
70 f->parse(ignoreComdats: false);
71 ctx.objectFiles.push_back(Elt: f);
72}
73
74// This function is where all the optimizations of link-time
75// optimization happens. When LTO is in use, some input files are
76// not in native object file format but in the LLVM bitcode format.
77// This function compiles bitcode files into a few big native files
78// using LLVM functions and replaces bitcode symbols with the results.
79// Because all bitcode files that the program consists of are passed
80// to the compiler at once, it can do whole-program optimization.
81void SymbolTable::compileBitcodeFiles() {
82 // Prevent further LTO objects being included
83 BitcodeFile::doneLTO = true;
84
85 // Compile bitcode files and replace bitcode symbols.
86 lto.reset(p: new BitcodeCompiler);
87 for (BitcodeFile *f : ctx.bitcodeFiles)
88 lto->add(f&: *f);
89
90 for (auto &file : lto->compile()) {
91 auto *obj = cast<ObjFile>(Val: file);
92 obj->parse(ignoreComdats: true);
93 ctx.objectFiles.push_back(Elt: obj);
94 }
95}
96
97Symbol *SymbolTable::find(StringRef name) {
98 auto it = symMap.find(Val: CachedHashStringRef(name));
99 if (it == symMap.end() || it->second == -1)
100 return nullptr;
101 return symVector[it->second];
102}
103
104void SymbolTable::replace(StringRef name, Symbol *sym) {
105 auto it = symMap.find(Val: CachedHashStringRef(name));
106 symVector[it->second] = sym;
107}
108
109std::pair<Symbol *, bool> SymbolTable::insertName(StringRef name) {
110 bool trace = false;
111 auto p = symMap.insert(KV: {CachedHashStringRef(name), (int)symVector.size()});
112 int &symIndex = p.first->second;
113 bool isNew = p.second;
114 if (symIndex == -1) {
115 symIndex = symVector.size();
116 trace = true;
117 isNew = true;
118 }
119
120 if (!isNew)
121 return {symVector[symIndex], false};
122
123 Symbol *sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
124 sym->isUsedInRegularObj = false;
125 sym->canInline = true;
126 sym->traced = trace;
127 sym->forceExport = false;
128 sym->referenced = !ctx.arg.gcSections;
129 symVector.emplace_back(args&: sym);
130 return {sym, true};
131}
132
133std::pair<Symbol *, bool> SymbolTable::insert(StringRef name,
134 const InputFile *file) {
135 Symbol *s;
136 bool wasInserted;
137 std::tie(args&: s, args&: wasInserted) = insertName(name);
138
139 if (!file || file->kind() == InputFile::ObjectKind)
140 s->isUsedInRegularObj = true;
141
142 return {s, wasInserted};
143}
144
145static void reportTypeError(const Symbol *existing, const InputFile *file,
146 llvm::wasm::WasmSymbolType type) {
147 error(msg: "symbol type mismatch: " + toString(sym: *existing) + "\n>>> defined as " +
148 toString(type: existing->getWasmType()) + " in " +
149 toString(file: existing->getFile()) + "\n>>> defined as " + toString(type) +
150 " in " + toString(file));
151}
152
153// Check the type of new symbol matches that of the symbol is replacing.
154// Returns true if the function types match, false is there is a signature
155// mismatch.
156static bool signatureMatches(FunctionSymbol *existing,
157 const WasmSignature *newSig) {
158 const WasmSignature *oldSig = existing->signature;
159
160 // If either function is missing a signature (this happens for bitcode
161 // symbols) then assume they match. Any mismatch will be reported later
162 // when the LTO objects are added.
163 if (!newSig || !oldSig)
164 return true;
165
166 return *newSig == *oldSig;
167}
168
169static void checkGlobalType(const Symbol *existing, const InputFile *file,
170 const WasmGlobalType *newType) {
171 if (!isa<GlobalSymbol>(Val: existing)) {
172 reportTypeError(existing, file, type: WASM_SYMBOL_TYPE_GLOBAL);
173 return;
174 }
175
176 const WasmGlobalType *oldType = cast<GlobalSymbol>(Val: existing)->getGlobalType();
177 if (*newType != *oldType) {
178 error(msg: "Global type mismatch: " + existing->getName() + "\n>>> defined as " +
179 toString(type: *oldType) + " in " + toString(file: existing->getFile()) +
180 "\n>>> defined as " + toString(type: *newType) + " in " + toString(file));
181 }
182}
183
184static void checkTagType(const Symbol *existing, const InputFile *file,
185 const WasmSignature *newSig) {
186 const auto *existingTag = dyn_cast<TagSymbol>(Val: existing);
187 if (!isa<TagSymbol>(Val: existing)) {
188 reportTypeError(existing, file, type: WASM_SYMBOL_TYPE_TAG);
189 return;
190 }
191
192 const WasmSignature *oldSig = existingTag->signature;
193 if (*newSig != *oldSig)
194 warn(msg: "Tag signature mismatch: " + existing->getName() +
195 "\n>>> defined as " + toString(sig: *oldSig) + " in " +
196 toString(file: existing->getFile()) + "\n>>> defined as " +
197 toString(sig: *newSig) + " in " + toString(file));
198}
199
200static void checkTableType(const Symbol *existing, const InputFile *file,
201 const WasmTableType *newType) {
202 if (!isa<TableSymbol>(Val: existing)) {
203 reportTypeError(existing, file, type: WASM_SYMBOL_TYPE_TABLE);
204 return;
205 }
206
207 const WasmTableType *oldType = cast<TableSymbol>(Val: existing)->getTableType();
208 if (newType->ElemType != oldType->ElemType) {
209 error(msg: "Table type mismatch: " + existing->getName() + "\n>>> defined as " +
210 toString(type: *oldType) + " in " + toString(file: existing->getFile()) +
211 "\n>>> defined as " + toString(type: *newType) + " in " + toString(file));
212 }
213 // FIXME: No assertions currently on the limits.
214}
215
216static void checkDataType(const Symbol *existing, const InputFile *file) {
217 if (!isa<DataSymbol>(Val: existing))
218 reportTypeError(existing, file, type: WASM_SYMBOL_TYPE_DATA);
219}
220
221DefinedFunction *SymbolTable::addSyntheticFunction(StringRef name,
222 uint32_t flags,
223 InputFunction *function) {
224 LLVM_DEBUG(dbgs() << "addSyntheticFunction: " << name << "\n");
225 assert(!find(name));
226 ctx.syntheticFunctions.emplace_back(Args&: function);
227 return replaceSymbol<DefinedFunction>(s: insertName(name).first, arg&: name, arg&: flags,
228 arg: nullptr, arg&: function);
229}
230
231// Adds an optional, linker generated, data symbol. The symbol will only be
232// added if there is an undefine reference to it, or if it is explicitly
233// exported via the --export flag. Otherwise we don't add the symbol and return
234// nullptr.
235DefinedData *SymbolTable::addOptionalDataSymbol(StringRef name,
236 uint64_t value) {
237 Symbol *s = find(name);
238 if (!s && (ctx.arg.exportAll || ctx.arg.exportedSymbols.contains(key: name)))
239 s = insertName(name).first;
240 else if (!s || s->isDefined())
241 return nullptr;
242 LLVM_DEBUG(dbgs() << "addOptionalDataSymbol: " << name << "\n");
243 auto *rtn = replaceSymbol<DefinedData>(
244 s, arg&: name, arg: WASM_SYMBOL_VISIBILITY_HIDDEN | WASM_SYMBOL_ABSOLUTE);
245 rtn->setVA(value);
246 rtn->referenced = true;
247 return rtn;
248}
249
250DefinedData *SymbolTable::addSyntheticDataSymbol(StringRef name,
251 uint32_t flags) {
252 LLVM_DEBUG(dbgs() << "addSyntheticDataSymbol: " << name << "\n");
253 assert(!find(name));
254 return replaceSymbol<DefinedData>(s: insertName(name).first, arg&: name,
255 arg: flags | WASM_SYMBOL_ABSOLUTE);
256}
257
258DefinedGlobal *SymbolTable::addSyntheticGlobal(StringRef name, uint32_t flags,
259 InputGlobal *global) {
260 LLVM_DEBUG(dbgs() << "addSyntheticGlobal: " << name << " -> " << global
261 << "\n");
262 assert(!find(name));
263 ctx.syntheticGlobals.emplace_back(Args&: global);
264 return replaceSymbol<DefinedGlobal>(s: insertName(name).first, arg&: name, arg&: flags,
265 arg: nullptr, arg&: global);
266}
267
268DefinedGlobal *SymbolTable::addOptionalGlobalSymbol(StringRef name,
269 InputGlobal *global) {
270 Symbol *s = find(name);
271 if (!s && (ctx.arg.exportAll || ctx.arg.exportedSymbols.contains(key: name)))
272 s = insertName(name).first;
273 else if (!s || s->isDefined())
274 return nullptr;
275 LLVM_DEBUG(dbgs() << "addOptionalGlobalSymbol: " << name << " -> " << global
276 << "\n");
277 ctx.syntheticGlobals.emplace_back(Args&: global);
278 return replaceSymbol<DefinedGlobal>(s, arg&: name, arg: WASM_SYMBOL_VISIBILITY_HIDDEN,
279 arg: nullptr, arg&: global);
280}
281
282DefinedTable *SymbolTable::addSyntheticTable(StringRef name, uint32_t flags,
283 InputTable *table) {
284 LLVM_DEBUG(dbgs() << "addSyntheticTable: " << name << " -> " << table
285 << "\n");
286 Symbol *s = find(name);
287 assert(!s || s->isUndefined());
288 if (!s)
289 s = insertName(name).first;
290 ctx.syntheticTables.emplace_back(Args&: table);
291 return replaceSymbol<DefinedTable>(s, arg&: name, arg&: flags, arg: nullptr, arg&: table);
292}
293
294static bool shouldReplace(const Symbol *existing, InputFile *newFile,
295 uint32_t newFlags) {
296 // If existing symbol is undefined, replace it.
297 if (!existing->isDefined()) {
298 LLVM_DEBUG(dbgs() << "resolving existing undefined symbol: "
299 << existing->getName() << "\n");
300 return true;
301 }
302
303 // Now we have two defined symbols. If the new one is weak, we can ignore it.
304 if ((newFlags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK) {
305 LLVM_DEBUG(dbgs() << "existing symbol takes precedence\n");
306 return false;
307 }
308
309 // If the existing symbol is weak, we should replace it.
310 if (existing->isWeak()) {
311 LLVM_DEBUG(dbgs() << "replacing existing weak symbol\n");
312 return true;
313 }
314
315 // Similarly with shared symbols
316 if (existing->isShared()) {
317 LLVM_DEBUG(dbgs() << "replacing existing shared symbol\n");
318 return true;
319 }
320
321 // Neither symbol is week. They conflict.
322 if (ctx.arg.allowMultipleDefinition)
323 return false;
324
325 errorOrWarn(msg: "duplicate symbol: " + toString(sym: *existing) + "\n>>> defined in " +
326 toString(file: existing->getFile()) + "\n>>> defined in " +
327 toString(file: newFile));
328 return true;
329}
330
331static void reportFunctionSignatureMismatch(StringRef symName,
332 FunctionSymbol *sym,
333 const WasmSignature *signature,
334 InputFile *file,
335 bool isError = true) {
336 std::string msg =
337 ("function signature mismatch: " + symName + "\n>>> defined as " +
338 toString(sig: *sym->signature) + " in " + toString(file: sym->getFile()) +
339 "\n>>> defined as " + toString(sig: *signature) + " in " + toString(file))
340 .str();
341 if (isError)
342 error(msg);
343 else
344 warn(msg);
345}
346
347static void reportFunctionSignatureMismatch(StringRef symName,
348 FunctionSymbol *a,
349 FunctionSymbol *b,
350 bool isError = true) {
351 reportFunctionSignatureMismatch(symName, sym: a, signature: b->signature, file: b->getFile(),
352 isError);
353}
354
355Symbol *SymbolTable::addSharedTag(StringRef name, uint32_t flags,
356 InputFile *file, const WasmSignature *sig) {
357 LLVM_DEBUG(dbgs() << "addSharedTag: " << name << " [" << toString(*sig)
358 << "]\n");
359 Symbol *s;
360 bool wasInserted;
361 std::tie(args&: s, args&: wasInserted) = insert(name, file);
362
363 auto replaceSym = [&](Symbol *sym) {
364 replaceSymbol<SharedTagSymbol>(s: sym, arg&: name, arg&: flags, arg&: file, arg&: sig);
365 };
366
367 // same as addSharedFunction, but this is in its own function
368 if (wasInserted || s->isLazy()) {
369 replaceSym(s);
370 return s;
371 }
372
373 auto *existingTag = dyn_cast<TagSymbol>(Val: s);
374 if (!existingTag) {
375 reportTypeError(existing: s, file, type: WASM_SYMBOL_TYPE_TAG);
376 return s;
377 }
378
379 if (s->isDefined()) {
380 return s;
381 }
382
383 // undefined existing sym
384 const WasmSignature *oldSig = existingTag->signature;
385 if (oldSig && sig && *oldSig != *sig)
386 error(msg: "Tag signature mismatch: " + name + "\n>>> defined as " +
387 toString(sig: *oldSig) + " in " + toString(file: existingTag->getFile()) +
388 "\n>>> defined as " + toString(sig: *sig) + " in " + toString(file));
389 replaceSym(s);
390 return s;
391}
392
393Symbol *SymbolTable::addSharedFunction(StringRef name, uint32_t flags,
394 InputFile *file,
395 const WasmSignature *sig) {
396 LLVM_DEBUG(dbgs() << "addSharedFunction: " << name << " [" << toString(*sig)
397 << "]\n");
398 Symbol *s;
399 bool wasInserted;
400 std::tie(args&: s, args&: wasInserted) = insert(name, file);
401
402 auto replaceSym = [&](Symbol *sym) {
403 replaceSymbol<SharedFunctionSymbol>(s: sym, arg&: name, arg&: flags, arg&: file, arg&: sig);
404 };
405
406 if (wasInserted || s->isLazy()) {
407 replaceSym(s);
408 return s;
409 }
410
411 auto existingFunction = dyn_cast<FunctionSymbol>(Val: s);
412 if (!existingFunction) {
413 reportTypeError(existing: s, file, type: WASM_SYMBOL_TYPE_FUNCTION);
414 return s;
415 }
416
417 // Shared symbols should never replace locally-defined ones
418 if (s->isDefined()) {
419 return s;
420 }
421
422 LLVM_DEBUG(dbgs() << "resolving existing undefined symbol: " << s->getName()
423 << "\n");
424
425 bool checkSig = true;
426 if (auto ud = dyn_cast<UndefinedFunction>(Val: existingFunction))
427 checkSig = ud->isCalledDirectly;
428
429 if (checkSig && !signatureMatches(existing: existingFunction, newSig: sig)) {
430 if (ctx.arg.shlibSigCheck) {
431 reportFunctionSignatureMismatch(symName: name, sym: existingFunction, signature: sig, file);
432 } else {
433 // With --no-shlib-sigcheck we ignore the signature of the function as
434 // defined by the shared library and instead use the signature as
435 // expected by the program being linked.
436 sig = existingFunction->signature;
437 }
438 }
439
440 replaceSym(s);
441 return s;
442}
443
444Symbol *SymbolTable::addSharedData(StringRef name, uint32_t flags,
445 InputFile *file) {
446 LLVM_DEBUG(dbgs() << "addSharedData: " << name << "\n");
447 Symbol *s;
448 bool wasInserted;
449 std::tie(args&: s, args&: wasInserted) = insert(name, file);
450
451 if (wasInserted || s->isLazy()) {
452 replaceSymbol<SharedData>(s, arg&: name, arg&: flags, arg&: file);
453 return s;
454 }
455
456 // Shared symbols should never replace locally-defined ones
457 if (s->isDefined()) {
458 return s;
459 }
460
461 checkDataType(existing: s, file);
462 replaceSymbol<SharedData>(s, arg&: name, arg&: flags, arg&: file);
463 return s;
464}
465
466Symbol *SymbolTable::addDefinedFunction(StringRef name, uint32_t flags,
467 InputFile *file,
468 InputFunction *function) {
469 LLVM_DEBUG(dbgs() << "addDefinedFunction: " << name << " ["
470 << (function ? toString(function->signature) : "none")
471 << "]\n");
472 Symbol *s;
473 bool wasInserted;
474 std::tie(args&: s, args&: wasInserted) = insert(name, file);
475
476 auto replaceSym = [&](Symbol *sym) {
477 // If the new defined function doesn't have signature (i.e. bitcode
478 // functions) but the old symbol does, then preserve the old signature
479 const WasmSignature *oldSig = s->getSignature();
480 auto *newSym =
481 replaceSymbol<DefinedFunction>(s: sym, arg&: name, arg&: flags, arg&: file, arg&: function);
482 if (!newSym->signature)
483 newSym->signature = oldSig;
484 };
485
486 if (wasInserted || s->isLazy()) {
487 replaceSym(s);
488 return s;
489 }
490
491 auto existingFunction = dyn_cast<FunctionSymbol>(Val: s);
492 if (!existingFunction) {
493 reportTypeError(existing: s, file, type: WASM_SYMBOL_TYPE_FUNCTION);
494 return s;
495 }
496
497 bool checkSig = true;
498 if (auto ud = dyn_cast<UndefinedFunction>(Val: existingFunction))
499 checkSig = ud->isCalledDirectly;
500
501 if (checkSig && function &&
502 !signatureMatches(existing: existingFunction, newSig: &function->signature)) {
503 Symbol *variant;
504 if (getFunctionVariant(sym: s, sig: &function->signature, file, out: &variant))
505 // New variant, always replace
506 replaceSym(variant);
507 else if (shouldReplace(existing: s, newFile: file, newFlags: flags))
508 // Variant already exists, replace it after checking shouldReplace
509 replaceSym(variant);
510
511 // This variant we found take the place in the symbol table as the primary
512 // variant.
513 replace(name, sym: variant);
514 return variant;
515 }
516
517 // Existing function with matching signature.
518 if (shouldReplace(existing: s, newFile: file, newFlags: flags))
519 replaceSym(s);
520
521 return s;
522}
523
524Symbol *SymbolTable::addDefinedData(StringRef name, uint32_t flags,
525 InputFile *file, InputChunk *segment,
526 uint64_t address, uint64_t size) {
527 LLVM_DEBUG(dbgs() << "addDefinedData:" << name << " addr:" << address
528 << "\n");
529 Symbol *s;
530 bool wasInserted;
531 std::tie(args&: s, args&: wasInserted) = insert(name, file);
532
533 auto replaceSym = [&]() {
534 replaceSymbol<DefinedData>(s, arg&: name, arg&: flags, arg&: file, arg&: segment, arg&: address, arg&: size);
535 };
536
537 if (wasInserted || s->isLazy()) {
538 replaceSym();
539 return s;
540 }
541
542 checkDataType(existing: s, file);
543
544 if (shouldReplace(existing: s, newFile: file, newFlags: flags))
545 replaceSym();
546 return s;
547}
548
549Symbol *SymbolTable::addDefinedGlobal(StringRef name, uint32_t flags,
550 InputFile *file, InputGlobal *global) {
551 LLVM_DEBUG(dbgs() << "addDefinedGlobal:" << name << "\n");
552
553 Symbol *s;
554 bool wasInserted;
555 std::tie(args&: s, args&: wasInserted) = insert(name, file);
556
557 auto replaceSym = [&]() {
558 replaceSymbol<DefinedGlobal>(s, arg&: name, arg&: flags, arg&: file, arg&: global);
559 };
560
561 if (wasInserted || s->isLazy()) {
562 replaceSym();
563 return s;
564 }
565
566 checkGlobalType(existing: s, file, newType: &global->getType());
567
568 if (shouldReplace(existing: s, newFile: file, newFlags: flags))
569 replaceSym();
570 return s;
571}
572
573Symbol *SymbolTable::addDefinedTag(StringRef name, uint32_t flags,
574 InputFile *file, InputTag *tag) {
575 LLVM_DEBUG(dbgs() << "addDefinedTag:" << name << "\n");
576
577 Symbol *s;
578 bool wasInserted;
579 std::tie(args&: s, args&: wasInserted) = insert(name, file);
580
581 auto replaceSym = [&]() {
582 replaceSymbol<DefinedTag>(s, arg&: name, arg&: flags, arg&: file, arg&: tag);
583 };
584
585 if (wasInserted || s->isLazy()) {
586 replaceSym();
587 return s;
588 }
589
590 checkTagType(existing: s, file, newSig: &tag->signature);
591
592 if (shouldReplace(existing: s, newFile: file, newFlags: flags))
593 replaceSym();
594 return s;
595}
596
597Symbol *SymbolTable::addDefinedTable(StringRef name, uint32_t flags,
598 InputFile *file, InputTable *table) {
599 LLVM_DEBUG(dbgs() << "addDefinedTable:" << name << "\n");
600
601 Symbol *s;
602 bool wasInserted;
603 std::tie(args&: s, args&: wasInserted) = insert(name, file);
604
605 auto replaceSym = [&]() {
606 replaceSymbol<DefinedTable>(s, arg&: name, arg&: flags, arg&: file, arg&: table);
607 };
608
609 if (wasInserted || s->isLazy()) {
610 replaceSym();
611 return s;
612 }
613
614 checkTableType(existing: s, file, newType: &table->getType());
615
616 if (shouldReplace(existing: s, newFile: file, newFlags: flags))
617 replaceSym();
618 return s;
619}
620
621// This function get called when an undefined symbol is added, and there is
622// already an existing one in the symbols table. In this case we check that
623// custom 'import-module' and 'import-field' symbol attributes agree.
624// With LTO these attributes are not available when the bitcode is read and only
625// become available when the LTO object is read. In this case we silently
626// replace the empty attributes with the valid ones.
627static void
628updateExistingUndefined(Symbol *existing, uint32_t flags, InputFile *file,
629 std::optional<StringRef> importName = {},
630 std::optional<StringRef> importModule = {}) {
631 if (importName) {
632 if (!existing->importName)
633 existing->importName = importName;
634 if (existing->importName != importName)
635 error(msg: "import name mismatch for symbol: " + toString(sym: *existing) +
636 "\n>>> defined as " + *existing->importName + " in " +
637 toString(file: existing->getFile()) + "\n>>> defined as " + *importName +
638 " in " + toString(file));
639 }
640
641 if (importModule) {
642 if (!existing->importModule)
643 existing->importModule = importModule;
644 if (existing->importModule != importModule)
645 error(msg: "import module mismatch for symbol: " + toString(sym: *existing) +
646 "\n>>> defined as " + *existing->importModule + " in " +
647 toString(file: existing->getFile()) + "\n>>> defined as " +
648 *importModule + " in " + toString(file));
649 }
650
651 // Update symbol binding, if the existing symbol is weak
652 uint32_t binding = flags & WASM_SYMBOL_BINDING_MASK;
653 if (existing->isWeak() && binding != WASM_SYMBOL_BINDING_WEAK) {
654 existing->flags = (existing->flags & ~WASM_SYMBOL_BINDING_MASK) | binding;
655 }
656
657 // Certain flags such as NO_STRIP should be maintianed if either old or
658 // new symbol is marked as such.
659 existing->flags |= flags & WASM_SYMBOL_NO_STRIP;
660}
661
662Symbol *SymbolTable::addUndefinedFunction(StringRef name,
663 std::optional<StringRef> importName,
664 std::optional<StringRef> importModule,
665 uint32_t flags, InputFile *file,
666 const WasmSignature *sig,
667 bool isCalledDirectly) {
668 LLVM_DEBUG(dbgs() << "addUndefinedFunction: " << name << " ["
669 << (sig ? toString(*sig) : "none")
670 << "] IsCalledDirectly:" << isCalledDirectly << " flags=0x"
671 << utohexstr(flags) << "\n");
672 assert(flags & WASM_SYMBOL_UNDEFINED);
673
674 Symbol *s;
675 bool wasInserted;
676 std::tie(args&: s, args&: wasInserted) = insert(name, file);
677 if (s->traced)
678 printTraceSymbolUndefined(name, file);
679
680 auto replaceSym = [&]() {
681 replaceSymbol<UndefinedFunction>(s, arg&: name, arg&: importName, arg&: importModule, arg&: flags,
682 arg&: file, arg&: sig, arg&: isCalledDirectly);
683 };
684
685 if (wasInserted) {
686 replaceSym();
687 } else if (auto *lazy = dyn_cast<LazySymbol>(Val: s)) {
688 if ((flags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK) {
689 lazy->setWeak();
690 lazy->signature = sig;
691 } else {
692 lazy->extract();
693 if (!ctx.arg.whyExtract.empty())
694 ctx.whyExtractRecords.emplace_back(Args: toString(file), Args: s->getFile(), Args&: *s);
695 }
696 } else {
697 auto existingFunction = dyn_cast<FunctionSymbol>(Val: s);
698 if (!existingFunction) {
699 reportTypeError(existing: s, file, type: WASM_SYMBOL_TYPE_FUNCTION);
700 return s;
701 }
702 if (!existingFunction->signature && sig)
703 existingFunction->signature = sig;
704 auto *existingUndefined = dyn_cast<UndefinedFunction>(Val: existingFunction);
705 if (isCalledDirectly && !signatureMatches(existing: existingFunction, newSig: sig)) {
706 if (existingFunction->isShared()) {
707 // Special handling for when the existing function is a shared symbol
708 if (ctx.arg.shlibSigCheck) {
709 reportFunctionSignatureMismatch(symName: name, sym: existingFunction, signature: sig, file);
710 } else {
711 existingFunction->signature = sig;
712 }
713 }
714 // If the existing undefined functions is not called directly then let
715 // this one take precedence. Otherwise the existing function is either
716 // directly called or defined, in which case we need a function variant.
717 else if (existingUndefined && !existingUndefined->isCalledDirectly)
718 replaceSym();
719 else if (getFunctionVariant(sym: s, sig, file, out: &s))
720 replaceSym();
721 }
722 if (existingUndefined) {
723 updateExistingUndefined(existing: existingUndefined, flags, file, importName,
724 importModule);
725 if (isCalledDirectly)
726 existingUndefined->isCalledDirectly = true;
727 }
728 }
729
730 return s;
731}
732
733Symbol *SymbolTable::addUndefinedData(StringRef name, uint32_t flags,
734 InputFile *file) {
735 LLVM_DEBUG(dbgs() << "addUndefinedData: " << name << "\n");
736 assert(flags & WASM_SYMBOL_UNDEFINED);
737
738 Symbol *s;
739 bool wasInserted;
740 std::tie(args&: s, args&: wasInserted) = insert(name, file);
741 if (s->traced)
742 printTraceSymbolUndefined(name, file);
743
744 if (wasInserted) {
745 replaceSymbol<UndefinedData>(s, arg&: name, arg&: flags, arg&: file);
746 } else if (auto *lazy = dyn_cast<LazySymbol>(Val: s)) {
747 if ((flags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK)
748 lazy->setWeak();
749 else
750 lazy->extract();
751 } else if (s->isDefined()) {
752 checkDataType(existing: s, file);
753 } else {
754 updateExistingUndefined(existing: s, flags, file);
755 }
756 return s;
757}
758
759Symbol *SymbolTable::addUndefinedGlobal(StringRef name,
760 std::optional<StringRef> importName,
761 std::optional<StringRef> importModule,
762 uint32_t flags, InputFile *file,
763 const WasmGlobalType *type) {
764 LLVM_DEBUG(dbgs() << "addUndefinedGlobal: " << name << "\n");
765 assert(flags & WASM_SYMBOL_UNDEFINED);
766
767 Symbol *s;
768 bool wasInserted;
769 std::tie(args&: s, args&: wasInserted) = insert(name, file);
770 if (s->traced)
771 printTraceSymbolUndefined(name, file);
772
773 if (wasInserted)
774 replaceSymbol<UndefinedGlobal>(s, arg&: name, arg&: importName, arg&: importModule, arg&: flags,
775 arg&: file, arg&: type);
776 else if (auto *lazy = dyn_cast<LazySymbol>(Val: s))
777 lazy->extract();
778 else if (s->isDefined())
779 checkGlobalType(existing: s, file, newType: type);
780 else
781 updateExistingUndefined(existing: s, flags, file, importName, importModule);
782 return s;
783}
784
785Symbol *SymbolTable::addUndefinedTable(StringRef name,
786 std::optional<StringRef> importName,
787 std::optional<StringRef> importModule,
788 uint32_t flags, InputFile *file,
789 const WasmTableType *type) {
790 LLVM_DEBUG(dbgs() << "addUndefinedTable: " << name << "\n");
791 assert(flags & WASM_SYMBOL_UNDEFINED);
792
793 Symbol *s;
794 bool wasInserted;
795 std::tie(args&: s, args&: wasInserted) = insert(name, file);
796 if (s->traced)
797 printTraceSymbolUndefined(name, file);
798
799 if (wasInserted)
800 replaceSymbol<UndefinedTable>(s, arg&: name, arg&: importName, arg&: importModule, arg&: flags,
801 arg&: file, arg&: type);
802 else if (auto *lazy = dyn_cast<LazySymbol>(Val: s))
803 lazy->extract();
804 else if (s->isDefined())
805 checkTableType(existing: s, file, newType: type);
806 else
807 updateExistingUndefined(existing: s, flags, file, importName, importModule);
808 return s;
809}
810
811Symbol *SymbolTable::addUndefinedTag(StringRef name,
812 std::optional<StringRef> importName,
813 std::optional<StringRef> importModule,
814 uint32_t flags, InputFile *file,
815 const WasmSignature *sig) {
816 LLVM_DEBUG(dbgs() << "addUndefinedTag: " << name << "\n");
817 assert(flags & WASM_SYMBOL_UNDEFINED);
818
819 Symbol *s;
820 bool wasInserted;
821 std::tie(args&: s, args&: wasInserted) = insert(name, file);
822 if (s->traced)
823 printTraceSymbolUndefined(name, file);
824
825 if (wasInserted)
826 replaceSymbol<UndefinedTag>(s, arg&: name, arg&: importName, arg&: importModule, arg&: flags, arg&: file,
827 arg&: sig);
828 else if (auto *lazy = dyn_cast<LazySymbol>(Val: s))
829 lazy->extract();
830 else if (s->isDefined())
831 checkTagType(existing: s, file, newSig: sig);
832 else
833 updateExistingUndefined(existing: s, flags, file, importName, importModule);
834 return s;
835}
836
837TableSymbol *SymbolTable::createUndefinedIndirectFunctionTable(StringRef name) {
838 LLVM_DEBUG(llvm::dbgs() << "createUndefinedIndirectFunctionTable\n");
839 WasmLimits limits{.Flags: 0, .Minimum: 0, .Maximum: 0, .PageSize: 0}; // Set by the writer.
840 WasmTableType *type = make<WasmTableType>();
841 type->ElemType = ValType::FUNCREF;
842 type->Limits = limits;
843 uint32_t flags = ctx.arg.exportTable ? 0 : WASM_SYMBOL_VISIBILITY_HIDDEN;
844 flags |= WASM_SYMBOL_UNDEFINED;
845 Symbol *sym =
846 addUndefinedTable(name, importName: name, importModule: defaultModule, flags, file: nullptr, type);
847 sym->markLive();
848 sym->forceExport = ctx.arg.exportTable;
849 return cast<TableSymbol>(Val: sym);
850}
851
852TableSymbol *SymbolTable::createDefinedIndirectFunctionTable(StringRef name) {
853 LLVM_DEBUG(llvm::dbgs() << "createDefinedIndirectFunctionTable\n");
854 const uint32_t invalidIndex = -1;
855 WasmLimits limits{.Flags: 0, .Minimum: 0, .Maximum: 0, .PageSize: 0}; // Set by the writer.
856 WasmTableType type{.ElemType: ValType::FUNCREF, .Limits: limits};
857 WasmTable desc{.Index: invalidIndex, .Type: type, .SymbolName: name};
858 InputTable *table = make<InputTable>(args&: desc, args: nullptr);
859 uint32_t flags = ctx.arg.exportTable ? 0 : WASM_SYMBOL_VISIBILITY_HIDDEN;
860 TableSymbol *sym = addSyntheticTable(name, flags, table);
861 sym->markLive();
862 sym->forceExport = ctx.arg.exportTable;
863 return sym;
864}
865
866// Whether or not we need an indirect function table is usually a function of
867// whether an input declares a need for it. However sometimes it's possible for
868// no input to need the indirect function table, but then a late
869// addInternalGOTEntry causes a function to be allocated an address. In that
870// case address we synthesize a definition at the last minute.
871TableSymbol *SymbolTable::resolveIndirectFunctionTable(bool required) {
872 Symbol *existing = find(name: functionTableName);
873 if (existing) {
874 if (!isa<TableSymbol>(Val: existing)) {
875 error(msg: Twine("reserved symbol must be of type table: `") +
876 functionTableName + "`");
877 return nullptr;
878 }
879 if (existing->isDefined()) {
880 error(msg: Twine("reserved symbol must not be defined in input files: `") +
881 functionTableName + "`");
882 return nullptr;
883 }
884 }
885
886 if (ctx.arg.importTable) {
887 if (existing) {
888 existing->importModule = defaultModule;
889 existing->importName = functionTableName;
890 return cast<TableSymbol>(Val: existing);
891 }
892 if (required)
893 return createUndefinedIndirectFunctionTable(name: functionTableName);
894 } else if ((existing && existing->isLive()) || ctx.arg.exportTable ||
895 required) {
896 // A defined table is required. Either because the user request an exported
897 // table or because the table symbol is already live. The existing table is
898 // guaranteed to be undefined due to the check above.
899 return createDefinedIndirectFunctionTable(name: functionTableName);
900 }
901
902 // An indirect function table will only be present in the symbol table if
903 // needed by a reloc; if we get here, we don't need one.
904 return nullptr;
905}
906
907void SymbolTable::addLazy(StringRef name, InputFile *file) {
908 LLVM_DEBUG(dbgs() << "addLazy: " << name << "\n");
909
910 Symbol *s;
911 bool wasInserted;
912 std::tie(args&: s, args&: wasInserted) = insertName(name);
913
914 if (wasInserted) {
915 replaceSymbol<LazySymbol>(s, arg&: name, arg: 0, arg&: file);
916 return;
917 }
918
919 if (!s->isUndefined())
920 return;
921
922 // The existing symbol is undefined, load a new one from the archive,
923 // unless the existing symbol is weak in which case replace the undefined
924 // symbols with a LazySymbol.
925 if (s->isWeak()) {
926 const WasmSignature *oldSig = nullptr;
927 // In the case of an UndefinedFunction we need to preserve the expected
928 // signature.
929 if (auto *f = dyn_cast<UndefinedFunction>(Val: s))
930 oldSig = f->signature;
931 LLVM_DEBUG(dbgs() << "replacing existing weak undefined symbol\n");
932 auto newSym =
933 replaceSymbol<LazySymbol>(s, arg&: name, arg: WASM_SYMBOL_BINDING_WEAK, arg&: file);
934 newSym->signature = oldSig;
935 return;
936 }
937
938 LLVM_DEBUG(dbgs() << "replacing existing undefined\n");
939 const InputFile *oldFile = s->getFile();
940 LazySymbol(name, 0, file).extract();
941 if (!ctx.arg.whyExtract.empty())
942 ctx.whyExtractRecords.emplace_back(Args: toString(file: oldFile), Args: s->getFile(), Args&: *s);
943}
944
945bool SymbolTable::addComdat(StringRef name) {
946 return comdatGroups.insert(V: CachedHashStringRef(name)).second;
947}
948
949// The new signature doesn't match. Create a variant to the symbol with the
950// signature encoded in the name and return that instead. These symbols are
951// then unified later in handleSymbolVariants.
952bool SymbolTable::getFunctionVariant(Symbol *sym, const WasmSignature *sig,
953 const InputFile *file, Symbol **out) {
954 LLVM_DEBUG(dbgs() << "getFunctionVariant: " << sym->getName() << " -> "
955 << " " << toString(*sig) << "\n");
956 Symbol *variant = nullptr;
957
958 // Linear search through symbol variants. Should never be more than two
959 // or three entries here.
960 auto &variants = symVariants[CachedHashStringRef(sym->getName())];
961 if (variants.empty())
962 variants.push_back(x: sym);
963
964 for (Symbol *v : variants) {
965 if (*v->getSignature() == *sig) {
966 variant = v;
967 break;
968 }
969 }
970
971 bool wasAdded = !variant;
972 if (wasAdded) {
973 // Create a new variant;
974 LLVM_DEBUG(dbgs() << "added new variant\n");
975 variant = reinterpret_cast<Symbol *>(make<SymbolUnion>());
976 variant->isUsedInRegularObj =
977 !file || file->kind() == InputFile::ObjectKind;
978 variant->canInline = true;
979 variant->traced = false;
980 variant->forceExport = false;
981 variants.push_back(x: variant);
982 } else {
983 LLVM_DEBUG(dbgs() << "variant already exists: " << toString(*variant)
984 << "\n");
985 assert(*variant->getSignature() == *sig);
986 }
987
988 *out = variant;
989 return wasAdded;
990}
991
992// Set a flag for --trace-symbol so that we can print out a log message
993// if a new symbol with the same name is inserted into the symbol table.
994void SymbolTable::trace(StringRef name) {
995 symMap.insert(KV: {CachedHashStringRef(name), -1});
996}
997
998void SymbolTable::wrap(Symbol *sym, Symbol *real, Symbol *wrap) {
999 // Swap symbols as instructed by -wrap.
1000 int &origIdx = symMap[CachedHashStringRef(sym->getName())];
1001 int &realIdx = symMap[CachedHashStringRef(real->getName())];
1002 int &wrapIdx = symMap[CachedHashStringRef(wrap->getName())];
1003 LLVM_DEBUG(dbgs() << "wrap: " << sym->getName() << "\n");
1004
1005 // Anyone looking up __real symbols should get the original
1006 realIdx = origIdx;
1007 // Anyone looking up the original should get the __wrap symbol
1008 origIdx = wrapIdx;
1009}
1010
1011static const uint8_t unreachableFn[] = {
1012 0x03 /* ULEB length */, 0x00 /* ULEB num locals */,
1013 0x00 /* opcode unreachable */, 0x0b /* opcode end */
1014};
1015
1016// Replace the given symbol body with an unreachable function.
1017// This is used by handleWeakUndefines in order to generate a callable
1018// equivalent of an undefined function and also handleSymbolVariants for
1019// undefined functions that don't match the signature of the definition.
1020InputFunction *SymbolTable::replaceWithUnreachable(Symbol *sym,
1021 const WasmSignature &sig,
1022 StringRef debugName) {
1023 auto *func = make<SyntheticFunction>(args: sig, args: sym->getName(), args&: debugName);
1024 func->setBody(unreachableFn);
1025 ctx.syntheticFunctions.emplace_back(Args&: func);
1026 // Mark new symbols as local. For relocatable output we don't want them
1027 // to be exported outside the object file.
1028 replaceSymbol<DefinedFunction>(s: sym, arg&: debugName, arg: WASM_SYMBOL_BINDING_LOCAL,
1029 arg: nullptr, arg&: func);
1030 // Ensure the stub function doesn't get a table entry. Its address
1031 // should always compare equal to the null pointer.
1032 sym->isStub = true;
1033 return func;
1034}
1035
1036void SymbolTable::replaceWithUndefined(Symbol *sym) {
1037 // Add a synthetic dummy for weak undefined functions. These dummies will
1038 // be GC'd if not used as the target of any "call" instructions.
1039 StringRef debugName = saver().save(S: "undefined_weak:" + toString(sym: *sym));
1040 replaceWithUnreachable(sym, sig: *sym->getSignature(), debugName);
1041 // Hide our dummy to prevent export.
1042 sym->setHidden(true);
1043}
1044
1045// For weak undefined functions, there may be "call" instructions that reference
1046// the symbol. In this case, we need to synthesise a dummy/stub function that
1047// will abort at runtime, so that relocations can still provided an operand to
1048// the call instruction that passes Wasm validation.
1049void SymbolTable::handleWeakUndefines() {
1050 for (Symbol *sym : symbols()) {
1051 if (sym->isUndefWeak() && sym->isUsedInRegularObj) {
1052 if (sym->getSignature()) {
1053 replaceWithUndefined(sym);
1054 } else {
1055 // It is possible for undefined functions not to have a signature (eg.
1056 // if added via "--undefined"), but weak undefined ones do have a
1057 // signature. Lazy symbols may not be functions and therefore Sig can
1058 // still be null in some circumstance.
1059 assert(!isa<FunctionSymbol>(sym));
1060 }
1061 }
1062 }
1063}
1064
1065DefinedFunction *SymbolTable::createUndefinedStub(const WasmSignature &sig) {
1066 if (auto it = stubFunctions.find(Val: sig); it != stubFunctions.end())
1067 return it->second;
1068 LLVM_DEBUG(dbgs() << "createUndefinedStub: " << toString(sig) << "\n");
1069 auto *sym = reinterpret_cast<DefinedFunction *>(make<SymbolUnion>());
1070 sym->isUsedInRegularObj = true;
1071 sym->canInline = true;
1072 sym->traced = false;
1073 sym->forceExport = false;
1074 sym->signature = &sig;
1075 replaceSymbol<DefinedFunction>(
1076 s: sym, arg: "undefined_stub", arg: WASM_SYMBOL_VISIBILITY_HIDDEN, arg: nullptr, arg: nullptr);
1077 replaceWithUnreachable(sym, sig, debugName: "undefined_stub");
1078 stubFunctions[sig] = sym;
1079 return sym;
1080}
1081
1082// Remove any variant symbols that were created due to function signature
1083// mismatches.
1084void SymbolTable::handleSymbolVariants() {
1085 for (auto pair : symVariants) {
1086 // Push the initial symbol onto the list of variants.
1087 StringRef symName = pair.first.val();
1088 std::vector<Symbol *> &variants = pair.second;
1089
1090#ifndef NDEBUG
1091 LLVM_DEBUG(dbgs() << "symbol with (" << variants.size()
1092 << ") variants: " << symName << "\n");
1093 for (auto *s : variants) {
1094 auto *f = cast<FunctionSymbol>(s);
1095 LLVM_DEBUG(dbgs() << " variant: " + f->getName() << " "
1096 << toString(*f->signature) << "\n");
1097 }
1098#endif
1099
1100 // Find the one definition.
1101 DefinedFunction *defined = nullptr;
1102 for (auto *symbol : variants) {
1103 if (auto f = dyn_cast<DefinedFunction>(Val: symbol)) {
1104 defined = f;
1105 break;
1106 }
1107 }
1108
1109 // If there are no definitions, and the undefined symbols disagree on
1110 // the signature, there is not we can do since we don't know which one
1111 // to use as the signature on the import.
1112 if (!defined) {
1113 reportFunctionSignatureMismatch(symName,
1114 a: cast<FunctionSymbol>(Val: variants[0]),
1115 b: cast<FunctionSymbol>(Val: variants[1]));
1116 return;
1117 }
1118
1119 for (auto *symbol : variants) {
1120 if (symbol != defined) {
1121 auto *f = cast<FunctionSymbol>(Val: symbol);
1122 reportFunctionSignatureMismatch(symName, a: f, b: defined, isError: false);
1123 StringRef debugName =
1124 saver().save(S: "signature_mismatch:" + toString(sym: *f));
1125 replaceWithUnreachable(sym: f, sig: *f->signature, debugName);
1126 }
1127 }
1128 }
1129}
1130
1131} // namespace lld::wasm
1132