[WebAssembly] Add export/import for function pointer table

[ncw]

Summary

This enables callback-style programming where the JavaScript environment can call back into the Wasm environment using a function pointer received from the module.

---

Currently Emscripten post-processes the Wasm file to add stub functions to enable this. Alon was concerned that when the function table was exported, performance might suffer? I'll do some quick tests to confirm this.

Edit: I've now done some benchmarking. Whether the table is exported or not has no observable effect on performance that I could find (results: https://github.com/kripken/emscripten/issues/6155)

Whether you use the JS Table object to jump into Wasm, rather than using a named dynCall stub, may have a performance effect, but exporting the table doesn't force that decision in any way.

[dschuff]

I don't think import or export should be on by default (even if emscripten decides to do that) but the option should be there. It's still pretty early days for the VMs and just because they don't optimize better today doesn't mean they never will.

[ncw]

Since callback APIs are so common (eg high usage of dynCall in Emscripten applications) it would be nice if engines could optimise table-based access so that it's usable. Why standardise an API for doing an indirect call from JS, then tell users, "write a Wasm trampoline instead since that's faster than the browser-provided method".

I agree that things could get a lot faster in future - but it would be a shame (to me) if the official API were to become uncompetitively slow, so that people don't want to use it.

Agreed that I can put it behind a flag if you'd prefer.

[sbc100]

lgtm, but I agree we should remove the export-by-default. At least for now, if only to keep this change small.

That way this change is also NFC for existing users, which is a nice feature.

[ncw]

Updated to not export by default, and creates export/import based on last-specified of --export-table and --import-table

[ruiu]

wasm/Driver.cpp

308

Config members are named after their command line options, so this member should be "ImportTable" or "ExportTable" and have a boolean value.

wasm/Writer.cpp

42

Does it make sense to add const to constexpr?

[ncw]

wasm/Driver.cpp

308

Good point. In this case, it's a tri-state, where the Table is either imported/exported, or neither, and I want to import/export based on the last-specified of those two options.

I'll expand that into two booleans ImportTable and ExportTable, if that's more idiomatic.

Done in rLLD328700.

wasm/Writer.cpp

42

Yes it does (in this case).

constexpr char * would be a const pointer to a non-const char.

constexpr const char * is equivalent to const char* const ie a const pointer to a const char.

Something like constexpr const int is silly/redundant, and constexpr const char *const would also be redundant.

test/wasm/export-table.test

+# RUN: llc -filetype=obj %p/Inputs/start.ll -o %t.start.o
+# RUN: wasm-ld --check-signatures --export-table -o %t.wasm %t.start.o
+# RUN: obj2yaml %t.wasm | FileCheck %s
+
+# Verify the --export-table flag creates a table export
+
+# CHECK:        - Type:            TABLE
+# CHECK-NEXT:     Tables:
+# CHECK-NEXT:       - ElemType:        ANYFUNC
+# CHECK-NEXT:         Limits:
+# CHECK-NEXT:           Flags:           [ HAS_MAX ]
+# CHECK-NEXT:           Initial:         0x00000001
+# CHECK-NEXT:           Maximum:         0x00000001
+# CHECK-NEXT:   - Type:
+# CHECK:        - Type:            EXPORT
+# CHECK-NEXT:     Exports:
+# CHECK:            - Name:            __indirect_function_table
+# CHECK-NEXT:         Kind:            TABLE
+# CHECK-NEXT:         Index:           0

test/wasm/import-table.test

+# RUN: llc -filetype=obj %p/Inputs/start.ll -o %t.start.o
+# RUN: wasm-ld --check-signatures --import-table -o %t.wasm %t.start.o
+# RUN: obj2yaml %t.wasm | FileCheck %s
+
+# Verify the --import-table flag creates a table import
+
+# CHECK:       - Type:            IMPORT
+# CHECK-NEXT:    Imports:
+# CHECK-NEXT:      - Module:          env
+# CHECK-NEXT:        Field:           __indirect_function_table
+# CHECK-NEXT:        Kind:            TABLE
+# CHECK-NEXT:        Table:
+# CHECK-NEXT:          ElemType:        ANYFUNC
+# CHECK-NEXT:          Limits:
+# CHECK-NEXT:            Flags:           [ HAS_MAX ]
+# CHECK-NEXT:            Initial:         0x00000001
+# CHECK-NEXT:            Maximum:         0x00000001
+

wasm/Config.h

 
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/BinaryFormat/Wasm.h"
 
 namespace lld {
 namespace wasm {
 
+enum class ExposeAs { IMPORT, EXPORT, NONE };
+
 struct Configuration {
   bool AllowUndefined;
   bool CheckSignatures;
   bool Demangle;
   bool GcSections;
   bool ImportMemory;
   bool PrintGcSections;
   bool Relocatable;
   bool StripAll;
   bool StripDebug;
+  ExposeAs Table;
   uint32_t GlobalBase;
   uint32_t InitialMemory;
   uint32_t MaxMemory;
   uint32_t ZStackSize;
   llvm::StringRef Entry;
   llvm::StringRef OutputFile;
 
   llvm::StringSet<> AllowUndefinedSymbols;

wasm/Driver.cpp

static StringRef getEntry(opt::InputArgList &Args, StringRef Default) {
   auto *Arg = Args.getLastArg(OPT_entry, OPT_no_entry);
   if (!Arg)
     return Default;
   if (Arg->getOption().getID() == OPT_no_entry)
     return "";
   return Arg->getValue();
 }
 
+static ExposeAs getExpose(opt::InputArgList &Args, unsigned Import,
+                          unsigned Export) {
+  auto *Arg = Args.getLastArg(Import, Export);
+  if (!Arg)
+    return ExposeAs::NONE;
+  return Arg->getOption().getID() == Import ? ExposeAs::IMPORT
+                                            : ExposeAs::EXPORT;
+}
+
 static const uint8_t UnreachableFn[] = {
     0x03 /* ULEB length */, 0x00 /* ULEB num locals */,
     0x00 /* opcode unreachable */, 0x0b /* opcode end */
 };
 
 // For weak undefined functions, there may be "call" instructions that reference
 // the symbol. In this case, we need to synthesise a dummy/stub function that
 // will abort at runtime, so that relocations can still provided an operand to
void LinkerDriver::link(ArrayRef<const char *> ArgsArr) {
   Config->Relocatable = Args.hasArg(OPT_relocatable);
   Config->GcSections =
       Args.hasFlag(OPT_gc_sections, OPT_no_gc_sections, !Config->Relocatable);
   Config->PrintGcSections =
       Args.hasFlag(OPT_print_gc_sections, OPT_no_print_gc_sections, false);
   Config->SearchPaths = args::getStrings(Args, OPT_L);
   Config->StripAll = Args.hasArg(OPT_strip_all);
   Config->StripDebug = Args.hasArg(OPT_strip_debug);
+  Config->Table = getExpose(Args, OPT_import_table, OPT_export_table);
   errorHandler().Verbose = Args.hasArg(OPT_verbose);
   ThreadsEnabled = Args.hasFlag(OPT_threads, OPT_no_threads, true);
 
   Config->InitialMemory = args::getInteger(Args, OPT_initial_memory, 0);
   Config->GlobalBase = args::getInteger(Args, OPT_global_base, 1024);
   Config->MaxMemory = args::getInteger(Args, OPT_max_memory, 0);
   Config->ZStackSize =
       args::getZOptionValue(Args, OPT_z, "stack-size", WasmPageSize);

wasm/Options.td

 
 defm check_signatures: B<"check-signatures",
     "Check function signatures",
     "Don't check function signatures">;
 
 defm export: Eq<"export">,
   HelpText<"Force a symbol to be exported">;
 
+def export_table: F<"export-table">,
+  HelpText<"Export function table to the environment">;
+
 def global_base: J<"global-base=">,
   HelpText<"Where to start to place global data">;
 
 def import_memory: F<"import-memory">,
   HelpText<"Import memory from the environment">;
 
+def import_table: F<"import-table">,
+  HelpText<"Import function table from the environment">;
+
 def initial_memory: J<"initial-memory=">,
   HelpText<"Initial size of the linear memory">;
 
 def max_memory: J<"max-memory=">,
   HelpText<"Maximum size of the linear memory">;
 
 def no_entry: F<"no-entry">,
   HelpText<"Do not output any entry point">;
 
 // Aliases
 def alias_entry_e: JoinedOrSeparate<["-"], "e">, Alias<entry>;
 def alias_entry_entry: J<"entry=">, Alias<entry>;
 def alias_initial_memory_i: Flag<["-"], "i">, Alias<initial_memory>;
 def alias_max_memory_m: Flag<["-"], "m">, Alias<max_memory>;
 def alias_relocatable_r: Flag<["-"], "r">, Alias<relocatable>;
 def alias_undefined_u: JoinedOrSeparate<["-"], "u">, Alias<undefined>;

wasm/Writer.cpp

 
 using namespace llvm;
 using namespace llvm::wasm;
 using namespace lld;
 using namespace lld::wasm;
 
 static constexpr int kStackAlignment = 16;
 static constexpr int kInitialTableOffset = 1;
+static constexpr const char *kFunctionTableName = "__indirect_function_table";
 
 namespace {
 
 // An init entry to be written to either the synthetic init func or the
 // linking metadata.
 struct WasmInitEntry {
   const FunctionSymbol *Sym;
   uint32_t Priority;

 };
 
 } // anonymous namespace
 
 void Writer::createImportSection() {
   uint32_t NumImports = ImportedSymbols.size();
   if (Config->ImportMemory)
     ++NumImports;
+  if (Config->Table == ExposeAs::IMPORT)
+    ++NumImports;
 
   if (NumImports == 0)
     return;
 
   SyntheticSection *Section = createSyntheticSection(WASM_SEC_IMPORT);
   raw_ostream &OS = Section->getStream();
 
   writeUleb128(OS, NumImports, "import count");
 
   if (Config->ImportMemory) {
     WasmImport Import;
     Import.Module = "env";
     Import.Field = "memory";
     Import.Kind = WASM_EXTERNAL_MEMORY;
     Import.Memory.Flags = 0;
     Import.Memory.Initial = NumMemoryPages;
     if (MaxMemoryPages != 0) {
       Import.Memory.Flags |= WASM_LIMITS_FLAG_HAS_MAX;
       Import.Memory.Maximum = MaxMemoryPages;
     }
     writeImport(OS, Import);
   }
 
+  if (Config->Table == ExposeAs::IMPORT) {
+    uint32_t TableSize = kInitialTableOffset + IndirectFunctions.size();
+    WasmImport Import;
+    Import.Module = "env";
+    Import.Field = kFunctionTableName;
+    Import.Kind = WASM_EXTERNAL_TABLE;
+    Import.Table.ElemType = WASM_TYPE_ANYFUNC;
+    Import.Table.Limits = {WASM_LIMITS_FLAG_HAS_MAX, TableSize, TableSize};
+    writeImport(OS, Import);
+  }
+
   for (const Symbol *Sym : ImportedSymbols) {
     WasmImport Import;
     Import.Module = "env";
     Import.Field = Sym->getName();
     if (auto *FunctionSym = dyn_cast<FunctionSymbol>(Sym)) {
       Import.Kind = WASM_EXTERNAL_FUNCTION;
       Import.SigIndex = lookupType(*FunctionSym->getFunctionType());
     } else {
for (const DefinedData *Sym : DefinedFakeGlobals) {
     Global.Type = {WASM_TYPE_I32, false};
     Global.InitExpr.Opcode = WASM_OPCODE_I32_CONST;
     Global.InitExpr.Value.Int32 = Sym->getVirtualAddress();
     writeGlobal(OS, Global);
   }
 }
 
 void Writer::createTableSection() {
-  // Always output a table section, even if there are no indirect calls.
-  // There are two reasons for this:
+  if (Config->Table == ExposeAs::IMPORT)
+    return;
+
+  // Always output a table section (or table import), even if there are no
+  // indirect calls.  There are two reasons for this:
   //  1. For executables it is useful to have an empty table slot at 0
   //     which can be filled with a null function call handler.
   //  2. If we don't do this, any program that contains a call_indirect but
   //     no address-taken function will fail at validation time since it is
   //     a validation error to include a call_indirect instruction if there
   //     is not table.
   uint32_t TableSize = kInitialTableOffset + IndirectFunctions.size();
 
   SyntheticSection *Section = createSyntheticSection(WASM_SEC_TABLE);
   raw_ostream &OS = Section->getStream();
 
   writeUleb128(OS, 1, "table count");
-  writeU8(OS, WASM_TYPE_ANYFUNC, "table type");
-  writeUleb128(OS, WASM_LIMITS_FLAG_HAS_MAX, "table flags");
-  writeUleb128(OS, TableSize, "table initial size");
-  writeUleb128(OS, TableSize, "table max size");
+  WasmLimits Limits = {WASM_LIMITS_FLAG_HAS_MAX, TableSize, TableSize};
+  writeTableType(OS, WasmTable{WASM_TYPE_ANYFUNC, Limits});
 }
 
 void Writer::createExportSection() {
   bool ExportMemory = !Config->Relocatable && !Config->ImportMemory;
+  bool ExportTable = !Config->Relocatable && Config->Table == ExposeAs::EXPORT;
 
-  uint32_t NumExports = (ExportMemory ? 1 : 0) + ExportedSymbols.size();
+  uint32_t NumExports =
+      (ExportMemory ? 1 : 0) + (ExportTable ? 1 : 0) + ExportedSymbols.size();
   if (!NumExports)
     return;
 
   SyntheticSection *Section = createSyntheticSection(WASM_SEC_EXPORT);
   raw_ostream &OS = Section->getStream();
 
   writeUleb128(OS, NumExports, "export count");
 
   if (ExportMemory)
     writeExport(OS, {"memory", WASM_EXTERNAL_MEMORY, 0});
+  if (ExportTable)
+    writeExport(OS, {kFunctionTableName, WASM_EXTERNAL_TABLE, 0});
 
   unsigned FakeGlobalIndex = NumImportedGlobals + InputGlobals.size();
 
   for (const Symbol *Sym : ExportedSymbols) {
     StringRef Name = Sym->getName();
     WasmExport Export;
     DEBUG(dbgs() << "Export: " << Name << "\n");
 

wasm/WriterUtils.h

 void writeInitExpr(raw_ostream &OS, const llvm::wasm::WasmInitExpr &InitExpr);
 
 void writeLimits(raw_ostream &OS, const llvm::wasm::WasmLimits &Limits);
 
 void writeGlobalType(raw_ostream &OS, const llvm::wasm::WasmGlobalType &Type);
 
 void writeGlobal(raw_ostream &OS, const llvm::wasm::WasmGlobal &Global);
 
+void writeTableType(raw_ostream &OS, const llvm::wasm::WasmTable &Type);
+
 void writeImport(raw_ostream &OS, const llvm::wasm::WasmImport &Import);
 
 void writeExport(raw_ostream &OS, const llvm::wasm::WasmExport &Export);
 
 } // namespace wasm
 
 std::string toString(llvm::wasm::ValType Type);
 std::string toString(const llvm::wasm::WasmSignature &Sig);
 std::string toString(const llvm::wasm::WasmGlobalType &Sig);
 
 } // namespace lld
 
 #endif // LLD_WASM_WRITERUTILS_H

wasm/WriterUtils.cpp

void wasm::writeGlobalType(raw_ostream &OS, const WasmGlobalType &Type) {
   writeU8(OS, Type.Mutable, "global mutable");
 }
 
 void wasm::writeGlobal(raw_ostream &OS, const WasmGlobal &Global) {
   writeGlobalType(OS, Global.Type);
   writeInitExpr(OS, Global.InitExpr);
 }
 
+void wasm::writeTableType(raw_ostream &OS, const llvm::wasm::WasmTable &Type) {
+  writeU8(OS, WASM_TYPE_ANYFUNC, "table type");
+  writeLimits(OS, Type.Limits);
+}
+
 void wasm::writeImport(raw_ostream &OS, const WasmImport &Import) {
   writeStr(OS, Import.Module, "import module name");
   writeStr(OS, Import.Field, "import field name");
   writeU8(OS, Import.Kind, "import kind");
   switch (Import.Kind) {
   case WASM_EXTERNAL_FUNCTION:
     writeUleb128(OS, Import.SigIndex, "import sig index");
     break;
   case WASM_EXTERNAL_GLOBAL:
     writeGlobalType(OS, Import.Global);
     break;
   case WASM_EXTERNAL_MEMORY:
     writeLimits(OS, Import.Memory);
     break;
+  case WASM_EXTERNAL_TABLE:
+    writeTableType(OS, Import.Table);
+    break;
   default:
     fatal("unsupported import type: " + Twine(Import.Kind));
   }
 }
 
 void wasm::writeExport(raw_ostream &OS, const WasmExport &Export) {
   writeStr(OS, Export.Name, "export name");
   writeU8(OS, Export.Kind, "export kind");
   switch (Export.Kind) {
   case WASM_EXTERNAL_FUNCTION:
     writeUleb128(OS, Export.Index, "function index");
     break;
   case WASM_EXTERNAL_GLOBAL:
     writeUleb128(OS, Export.Index, "global index");
     break;
   case WASM_EXTERNAL_MEMORY:
     writeUleb128(OS, Export.Index, "memory index");
     break;
+  case WASM_EXTERNAL_TABLE:
+    writeUleb128(OS, Export.Index, "table index");
+    break;
   default:
     fatal("unsupported export type: " + Twine(Export.Kind));
   }
 }
 } // namespace lld
 
 std::string lld::toString(ValType Type) {
   switch (Type) {