[lld][WebAssembly] -Bsymbolic creates indirect function table if needed

[wingo]

Summary

It can be that while processing relocations, we realize that in the end
we need an indirect function table. Ensure that one is present, in that
case, to avoid writing invalid object files.

Fixes https://bugs.llvm.org/show_bug.cgi?id=49397.

[sbc100]

lgtm % comments / nits

lld/wasm/Driver.cpp

800

This function can probably just be removed now.

lld/wasm/SymbolTable.cpp

683

Remove this line?

lld/wasm/SyntheticSections.cpp

304

you can do resolveIndirectFunctionTable(/*required =*/true); to avoid the extra local

Perhaps the early return is then overkill if if the body is just one line anyway?

315

How about calling this ensureIndirectFunctionTable ?

lld/wasm/Writer.cpp

748

This kind of ordering violation kind of makes me sad, but I'm not sure I have any better ideas.

748

Can this be replaced by:

// In some cases indirectFunctionTable is added during scanRelocations and therefore was not
// added to the import list at the normal time. 
if (shouldImport(WasmSym::indirectFunctionTable) && !WasmSym::indirectFunctionTable.hasTableNumber()) {
    ...
`

This would avoid the extra indirectFunctionTablePresentWhenComputingImports variable which would simplify the patch a little I think (you could revert the conversion of finalizeIndirectFunctionTable to a member for example).

Its still ugly but less intrusive maybe.

[wingo]

lld/wasm/Writer.cpp

748

Yeah I feel the pain here -- I did try to add a clause in the earlier resolveIndirectFunctionTable routine, but at that point it's too hard to know if there are GOT function pointers. Sad indeed.

Thanks for the review!

[wingo]

Address feedback

lld/test/wasm/bsymbolic.s

 // RUN: llvm-mc -filetype=obj -triple=wasm32-unknown-unknown %s -o %t.o
 // RUN: wasm-ld --no-entry -Bsymbolic %t.o -o %t.wasm 2>&1 | FileCheck -check-prefix=WARNING %s
 // WARNING: warning: -Bsymbolic is only meaningful when combined with -shared
 
 // RUN: wasm-ld --experimental-pic -shared %t.o -o %t0.so
 // RUN: obj2yaml %t0.so | FileCheck -check-prefix=NOOPTION %s
 
 // RUN: wasm-ld --experimental-pic -shared -Bsymbolic %t.o -o %t1.so
 // RUN: obj2yaml %t1.so | FileCheck -check-prefix=SYMBOLIC %s
 
-// NOOPTION  - Type:            IMPORT
-// NOOPTION:            - Module:          GOT.func
-// NOOPTION-NEXT:         Field:           foo
-// NOOPTION-NEXT:         Kind:            GLOBAL
-// NOOPTION-NEXT:         GlobalType:      I32
-// NOOPTION-NEXT:         GlobalMutable:   true
-// NOOPTION-NEXT:       - Module:          GOT.mem
-// NOOPTION-NEXT:         Field:           bar
-// NOOPTION-NEXT:         Kind:            GLOBAL
-// NOOPTION-NEXT:         GlobalType:      I32
-// NOOPTION-NEXT:         GlobalMutable:   true
+// NOOPTION:       - Type:            IMPORT
+// NOOPTION-NEXT:    Imports:
+// NOOPTION-NEXT:      - Module:          env
+// NOOPTION-NEXT:        Field:           memory
+// NOOPTION-NEXT:        Kind:            MEMORY
+// NOOPTION-NEXT:        Memory:
+// NOOPTION-NEXT:          Initial:         0x1
+// NOOPTION-NEXT:      - Module:          env
+// NOOPTION-NEXT:        Field:           __memory_base
+// NOOPTION-NEXT:        Kind:            GLOBAL
+// NOOPTION-NEXT:        GlobalType:      I32
+// NOOPTION-NEXT:        GlobalMutable:   false
+// NOOPTION-NEXT:      - Module:          env
+// NOOPTION-NEXT:        Field:           __table_base
+// NOOPTION-NEXT:        Kind:            GLOBAL
+// NOOPTION-NEXT:        GlobalType:      I32
+// NOOPTION-NEXT:        GlobalMutable:   false
+// NOOPTION-NEXT:      - Module:          GOT.func
+// NOOPTION-NEXT:        Field:           foo
+// NOOPTION-NEXT:        Kind:            GLOBAL
+// NOOPTION-NEXT:        GlobalType:      I32
+// NOOPTION-NEXT:        GlobalMutable:   true
+// NOOPTION-NEXT:      - Module:          GOT.mem
+// NOOPTION-NEXT:        Field:           bar
+// NOOPTION-NEXT:        Kind:            GLOBAL
+// NOOPTION-NEXT:        GlobalType:      I32
+// NOOPTION-NEXT:        GlobalMutable:   true
+// NOOPTION-NEXT:  - Type:            FUNCTION
 
 //      NOOPTION:  - Type:            GLOBAL
 // NOOPTION-NEXT:    Globals:
 // NOOPTION-NEXT:      - Index:           4
 // NOOPTION-NEXT:        Type:            I32
 // NOOPTION-NEXT:        Mutable:         false
 // NOOPTION-NEXT:        InitExpr:
 // NOOPTION-NEXT:          Opcode:          I32_CONST
 // NOOPTION-NEXT:          Value:           0
 // NOOPTION-NEXT:  - Type:            EXPORT
 
 // SYMBOLIC-NOT:   - Module:          GOT.mem
 // SYMBOLIC-NOT:   - Module:          GOT.func
 
+// SYMBOLIC:       - Type:            IMPORT
+// SYMBOLIC-NEXT:    Imports:
+// SYMBOLIC-NEXT:      - Module:          env
+// SYMBOLIC-NEXT:        Field:           memory
+// SYMBOLIC-NEXT:        Kind:            MEMORY
+// SYMBOLIC-NEXT:        Memory:
+// SYMBOLIC-NEXT:          Initial:         0x1
+// SYMBOLIC-NEXT:      - Module:          env
+// SYMBOLIC-NEXT:        Field:           __memory_base
+// SYMBOLIC-NEXT:        Kind:            GLOBAL
+// SYMBOLIC-NEXT:        GlobalType:      I32
+// SYMBOLIC-NEXT:        GlobalMutable:   false
+// SYMBOLIC-NEXT:      - Module:          env
+// SYMBOLIC-NEXT:        Field:           __table_base
+// SYMBOLIC-NEXT:        Kind:            GLOBAL
+// SYMBOLIC-NEXT:        GlobalType:      I32
+// SYMBOLIC-NEXT:        GlobalMutable:   false
+// SYMBOLIC-NEXT:      - Module:          env
+// SYMBOLIC-NEXT:        Field:           __indirect_function_table
+// SYMBOLIC-NEXT:        Kind:            TABLE
+// SYMBOLIC-NEXT:        Table:
+// SYMBOLIC-NEXT:          Index:           0
+// SYMBOLIC-NEXT:          ElemType:        FUNCREF
+// SYMBOLIC-NEXT:          Limits:
+// SYMBOLIC-NEXT:            Initial:         0x1
+// SYMBOLIC-NEXT:  - Type:            FUNCTION
+
 // SYMBOLIC:       - Type:            GLOBAL
 // SYMBOLIC-NEXT:    Globals:
 // SYMBOLIC-NEXT:      - Index:           2
 // SYMBOLIC-NEXT:        Type:            I32
 // SYMBOLIC-NEXT:        Mutable:         true
 // SYMBOLIC-NEXT:        InitExpr:
 // SYMBOLIC-NEXT:          Opcode:          I32_CONST
 // SYMBOLIC-NEXT:          Value:           0

lld/wasm/Driver.cpp

for (size_t i = 0, e = syms.size(); i != e; ++i)
         syms[i] = s;
   });
 
   // Update pointers in the symbol table.
   for (const WrappedSymbol &w : wrapped)
     symtab->wrap(w.sym, w.real, w.wrap);
 }
 
-static TableSymbol *createDefinedIndirectFunctionTable(StringRef name) {
-  const uint32_t invalidIndex = -1;
-  WasmLimits limits{0, 0, 0}; // Set by the writer.
-  WasmTableType type{uint8_t(ValType::FUNCREF), limits};
-  WasmTable desc{invalidIndex, type, name};
-  InputTable *table = make<InputTable>(desc, nullptr);
-  uint32_t flags = config->exportTable ? 0 : WASM_SYMBOL_VISIBILITY_HIDDEN;
-  TableSymbol *sym = symtab->addSyntheticTable(name, flags, table);
-  sym->markLive();
-  sym->forceExport = config->exportTable;
-  return sym;
-}
-
 static TableSymbol *resolveIndirectFunctionTable() {
-  Symbol *existing = symtab->find(functionTableName);
-  if (existing) {
-    if (!isa<TableSymbol>(existing)) {
-      error(Twine("reserved symbol must be of type table: `") +
-            functionTableName + "`");
-      return nullptr;
-    }
-    if (existing->isDefined()) {
-      error(Twine("reserved symbol must not be defined in input files: `") +
-            functionTableName + "`");
-      return nullptr;
-    }
-  }
-
-  if (config->importTable) {
-    return cast_or_null<TableSymbol>(existing);
-  } else if ((existing && existing->isLive()) || config->exportTable) {
-    // A defined table is required.  Either because the user request an exported
-    // table or because the table symbol is already live.  The existing table is
-    // guaranteed to be undefined due to the check above.
-    return createDefinedIndirectFunctionTable(functionTableName);
-  }
-
-  // An indirect function table will only be present in the symbol table if
-  // needed by a reloc; if we get here, we don't need one.
-  return nullptr;
+  const bool required = false;
+  return symtab->resolveIndirectFunctionTable(required);
 }
 
 void LinkerDriver::linkerMain(ArrayRef<const char *> argsArr) {
   WasmOptTable parser;
   opt::InputArgList args = parser.parse(argsArr.slice(1));
 
   // Handle --help
   if (args.hasArg(OPT_help)) {
if (entrySym)
     entrySym->setHidden(false);
 
   if (errorCount())
     return;
 
   // Do size optimizations: garbage collection
   markLive();
 
-  // Provide the indirect funciton table if needed.
+  // Provide the indirect function table if needed.
   WasmSym::indirectFunctionTable = resolveIndirectFunctionTable();
 
   if (errorCount())
     return;
 
   // Write the result to the file.
   writeResult();
 }
 
 } // namespace wasm
 } // namespace lld

lld/wasm/SymbolTable.h

Symbol *addUndefinedGlobal(StringRef name,
                              uint32_t flags, InputFile *file,
                              const WasmGlobalType *type);
   Symbol *addUndefinedTable(StringRef name,
                             llvm::Optional<StringRef> importName,
                             llvm::Optional<StringRef> importModule,
                             uint32_t flags, InputFile *file,
                             const WasmTableType *type);
 
+  TableSymbol *resolveIndirectFunctionTable(bool required);
+
   void addLazy(ArchiveFile *f, const llvm::object::Archive::Symbol *sym);
 
   bool addComdat(StringRef name);
 
   DefinedData *addSyntheticDataSymbol(StringRef name, uint32_t flags);
   DefinedGlobal *addSyntheticGlobal(StringRef name, uint32_t flags,
                                     InputGlobal *global);
   DefinedFunction *addSyntheticFunction(StringRef name, uint32_t flags,
private:
   std::pair<Symbol *, bool> insertName(StringRef name);
 
   bool getFunctionVariant(Symbol* sym, const WasmSignature *sig,
                           const InputFile *file, Symbol **out);
   InputFunction *replaceWithUnreachable(Symbol *sym, const WasmSignature &sig,
                                         StringRef debugName);
   void replaceWithUndefined(Symbol *sym);
 
+  TableSymbol *createDefinedIndirectFunctionTable(StringRef name);
+  TableSymbol *createUndefinedIndirectFunctionTable(StringRef name);
+
   // Maps symbol names to index into the symVector.  -1 means that symbols
   // is to not yet in the vector but it should have tracing enabled if it is
   // ever added.
   llvm::DenseMap<llvm::CachedHashStringRef, int> symMap;
   std::vector<Symbol *> symVector;
 
   // For certain symbols types, e.g. function symbols, we allow for multiple
   // variants of the same symbol with different signatures.

lld/wasm/SymbolTable.cpp

replaceSymbol<UndefinedTable>(s, name, importName, importModule, flags,
                                   file, type);
   else if (auto *lazy = dyn_cast<LazySymbol>(s))
     lazy->fetch();
   else if (s->isDefined())
     checkTableType(s, file, type);
   return s;
 }
 
+TableSymbol *SymbolTable::createUndefinedIndirectFunctionTable(StringRef name) {
+  WasmLimits limits{0, 0, 0}; // Set by the writer.
+  WasmTableType *type = make<WasmTableType>();
+  type->ElemType = uint8_t(ValType::FUNCREF);
+  type->Limits = limits;
+  StringRef module(defaultModule);
+  uint32_t flags = config->exportTable ? 0 : WASM_SYMBOL_VISIBILITY_HIDDEN;
+  flags |= WASM_SYMBOL_UNDEFINED;
+  Symbol *sym = addUndefinedTable(name, name, module, flags, nullptr, type);
+  sym->markLive();
+  sym->forceExport = config->exportTable;
+  return cast<TableSymbol>(sym);
+}
+
+TableSymbol *SymbolTable::createDefinedIndirectFunctionTable(StringRef name) {
+  const uint32_t invalidIndex = -1;
+  WasmLimits limits{0, 0, 0}; // Set by the writer.
+  WasmTableType type{uint8_t(ValType::FUNCREF), limits};
+  WasmTable desc{invalidIndex, type, name};
+  InputTable *table = make<InputTable>(desc, nullptr);
+  uint32_t flags = config->exportTable ? 0 : WASM_SYMBOL_VISIBILITY_HIDDEN;
+  TableSymbol *sym = addSyntheticTable(name, flags, table);
+  sym->markLive();
+  sym->forceExport = config->exportTable;
+  return sym;
+}
+
+// Whether or not we need an indirect function table is usually a function of
+// whether an input declares a need for it.  However sometimes it's possible for
+// no input to need the indirect function table, but then a late
+// addInternalGOTEntry causes a function to be allocated an address.  In that
+// case address we synthesize a definition at the last minute.
+TableSymbol *SymbolTable::resolveIndirectFunctionTable(bool required) {
+  Symbol *existing = find(functionTableName);
+  if (existing) {
+    if (!isa<TableSymbol>(existing)) {
+      error(Twine("reserved symbol must be of type table: `") +
+            functionTableName + "`");
+      return nullptr;
+    }
+    if (existing->isDefined()) {
+      error(Twine("reserved symbol must not be defined in input files: `") +
+            functionTableName + "`");
+      return nullptr;
+    }
+  }
+
+  if (config->importTable) {
+    if (existing)
+      return cast<TableSymbol>(existing);
+    if (required)
+      return createUndefinedIndirectFunctionTable(functionTableName);
+    return nullptr;
+  } else if ((existing && existing->isLive()) || config->exportTable ||
+             required) {
+    // A defined table is required.  Either because the user request an exported
+    // table or because the table symbol is already live.  The existing table is
+    // guaranteed to be undefined due to the check above.
+    return createDefinedIndirectFunctionTable(functionTableName);
+  }
+
+  // An indirect function table will only be present in the symbol table if
+  // needed by a reloc; if we get here, we don't need one.
+  return nullptr;
+}
+
 void SymbolTable::addLazy(ArchiveFile *file, const Archive::Symbol *sym) {
   LLVM_DEBUG(dbgs() << "addLazy: " << sym->getName() << "\n");
   StringRef name = sym->getName();
 
   Symbol *s;
   bool wasInserted;
   std::tie(s, wasInserted) = insertName(name);
 

lld/wasm/SyntheticSections.cpp

void GlobalSection::assignIndexes() {
   uint32_t globalIndex = out.importSec->getNumImportedGlobals();
   for (InputGlobal *g : inputGlobals)
     g->assignIndex(globalIndex++);
   for (Symbol *sym : internalGotSymbols)
     sym->setGOTIndex(globalIndex++);
   isSealed = true;
 }
 
+static void handleIndirectFunctionTableLateRequirement() {
+  if (WasmSym::indirectFunctionTable)
+    return;
+  const bool required = true;
+  WasmSym::indirectFunctionTable =
+      symtab->resolveIndirectFunctionTable(required);
+}
+
 void GlobalSection::addInternalGOTEntry(Symbol *sym) {
   assert(!isSealed);
   if (sym->requiresGOT)
     return;
   LLVM_DEBUG(dbgs() << "addInternalGOTEntry: " << sym->getName() << " "
                     << toString(sym->kind()) << "\n");
   sym->requiresGOT = true;
-  if (auto *F = dyn_cast<FunctionSymbol>(sym))
+  if (auto *F = dyn_cast<FunctionSymbol>(sym)) {
+    handleIndirectFunctionTableLateRequirement();
     out.elemSec->addEntry(F);
+  }
   internalGotSymbols.push_back(sym);
 }
 
 void GlobalSection::generateRelocationCode(raw_ostream &os) const {
   unsigned opcode_ptr_const = config->is64.getValueOr(false)
                                   ? WASM_OPCODE_I64_CONST
                                   : WASM_OPCODE_I32_CONST;
   unsigned opcode_ptr_add = config->is64.getValueOr(false)

lld/wasm/Writer.cpp

private:
   void createCommandExportWrapper(uint32_t functionIndex, DefinedFunction *f);
 
   void assignIndexes();
   void populateSymtab();
   void populateProducers();
   void populateTargetFeatures();
   void calculateInitFunctions();
   void calculateImports();
+  void finalizeIndirectFunctionTable();
   void calculateExports();
   void calculateCustomSections();
   void calculateTypes();
   void createOutputSegments();
   void combineOutputSegments();
   void layoutMemory();
   void createHeader();
 
   void addSection(OutputSection *sec);
 
   void addSections();
 
   void createCustomSections();
   void createSyntheticSections();
   void createSyntheticSectionsPostLayout();
   void finalizeSections();
 
   // Custom sections
   void createRelocSections();
 
   void writeHeader();
   void writeSections();
 
+  bool indirectFunctionTablePresentWhenComputingImports = false;
+
   uint64_t fileSize = 0;
 
   std::vector<WasmInitEntry> initFunctions;
   llvm::StringMap<std::vector<InputSection *>> customSectionMapping;
 
   // Stable storage for command export wrapper function name strings.
   std::list<std::string> commandExportWrapperNames;
 
static bool shouldImport(Symbol *sym) {
 
   return false;
 }
 
 void Writer::calculateImports() {
   // Some inputs require that the indirect function table be assigned to table
   // number 0, so if it is present and is an import, allocate it before any
   // other tables.
-  if (WasmSym::indirectFunctionTable &&
-      shouldImport(WasmSym::indirectFunctionTable))
+  if (WasmSym::indirectFunctionTable) {
+    if (shouldImport(WasmSym::indirectFunctionTable))
       out.importSec->addImport(WasmSym::indirectFunctionTable);
+    indirectFunctionTablePresentWhenComputingImports = true;
+  }
 
   for (Symbol *sym : symtab->getSymbols()) {
     if (!shouldImport(sym))
       continue;
     if (sym == WasmSym::indirectFunctionTable)
       continue;
     LLVM_DEBUG(dbgs() << "import: " << sym->getName() << "\n");
     out.importSec->addImport(sym);
for (auto *f : toWrap) {
     f->forceExport = false;
 
     out.functionSec->addFunction(func);
 
     createCommandExportWrapper(f->getFunctionIndex(), def);
   }
 }
 
-static void finalizeIndirectFunctionTable() {
+void Writer::finalizeIndirectFunctionTable() {
   if (!WasmSym::indirectFunctionTable)
     return;
 
+  if (!indirectFunctionTablePresentWhenComputingImports &&
+      shouldImport(WasmSym::indirectFunctionTable)) {
+    // Processing -Bsymbolic relocations resulted in a late requirement that the
+    // indirect function table be present, and we are running in --import-table
+    // mode.  Add the table now to the imports section.  Otherwise it will be
+    // added to the tables section later in assignIndexes.
+    out.importSec->addImport(WasmSym::indirectFunctionTable);
+  }
+
   uint32_t tableSize = config->tableBase + out.elemSec->numEntries();
   WasmLimits limits = {0, tableSize, 0};
   if (WasmSym::indirectFunctionTable->isDefined() && !config->growableTable) {
     limits.Flags |= WASM_LIMITS_FLAG_HAS_MAX;
     limits.Maximum = limits.Initial;
   }
   WasmSym::indirectFunctionTable->setLimits(limits);
 }