[WebAssembly] Apply data relocations at runtime in shared objects

[sbc100]

Summary

See: https://github.com/WebAssembly/tool-conventions/blob/master/DynamicLinking.md

Data section relocations in wasm shared libraries are applied by the library
itself at static constructor time. This change adds a new synthetic function
that applies relocations to relevant memory locations on startup.

[sbc100]

• clang-format
• comments
• cleanup

[sbc100]

• comments

[ruiu]

lld/wasm/Driver.cpp

283

Is the combination of --entry and --relocatable valid? Maybe we should reject that combination in the driver?

lld/wasm/InputChunks.cpp

296

Instead of creating a table for the run-time loader to fix these addresses, do we generate code in the linker to do it as part of process initialization?

297

Should be uint32_t?

[sbc100]

lld/wasm/InputChunks.cpp

296

Yes. And only for the data section. The keeps the dynamic linker very simple avoids the need to spec an ABI for runtime relocations.

[sbc100]

• rebase

[sbc100]

• feedback

lld/wasm/Driver.cpp

283

We already do check for this in checkOptions (see error("entry point specified for relocatable output file"))

[ruiu]

LGTM

lld/test/wasm/shared.ll

 ; RUN: llc -O0 -filetype=obj %s -o %t.o
 ; RUN: wasm-ld -shared -o %t.wasm %t.o
 ; RUN: obj2yaml %t.wasm | FileCheck %s
 
 target triple = "wasm32-unknown-unknown"
 
-@data = hidden global i32 2, align 4
+@data1 = hidden global i32 2, align 4
 @indirect_func = local_unnamed_addr global i32 ()* @foo, align 4
 @indirect_func_external = local_unnamed_addr global void ()* @func_external, align 4
 
+@data_addr = local_unnamed_addr global i32* @data1, align 4
+@data_addr_external = local_unnamed_addr global i32* @data_external, align 4
+
 define default i32 @foo() {
 entry:
   ; To ensure we use __stack_pointer
   %ptr = alloca i32
-  %0 = load i32, i32* @data, align 4
+  %0 = load i32, i32* @data1, align 4
   %1 = load i32, i32* @data_external, align 4
   %2 = load i32 ()*, i32 ()** @indirect_func, align 4
   call i32 %2()
   ret i32 %1
 }
 
 declare void @func_external()
 
 @data_external = external global i32
 
 
 ; check for dylink section at start
 
 ; CHECK:      Sections:
 ; CHECK-NEXT:   - Type:            CUSTOM
 ; CHECK-NEXT:     Name:            dylink
-; CHECK-NEXT:     MemorySize:      8
+; CHECK-NEXT:     MemorySize:      20
 ; CHECK-NEXT:     MemoryAlignment: 2
 ; CHECK-NEXT:     TableSize:       2
 ; CHECK-NEXT:     TableAlignment:  0
 
 ; check for import of __table_base and __memory_base globals
 
 ; CHECK:        - Type:            IMPORT
 ; CHECK-NEXT:     Imports:

 ; CHECK-NEXT:         Kind:            GLOBAL
 ; CHECK-NEXT:         GlobalType:      I32
 ; CHECK-NEXT:         GlobalMutable:   true
 ; CHECK-NEXT:       - Module:          env
 ; CHECK-NEXT:         Field:           func_external
 ; CHECK-NEXT:         Kind:            FUNCTION
 ; CHECK-NEXT:         SigIndex:        1
 
+; CHECK:        - Type:            EXPORT
+; CHECK-NEXT:     Exports:
+; CHECK-NEXT:       - Name:            memory
+; CHECK-NEXT:         Kind:            MEMORY
+; CHECK-NEXT:         Index:           0
+; CHECK-NEXT:       - Name:            __wasm_call_ctors
+; CHECK-NEXT:         Kind:            FUNCTION
+; CHECK-NEXT:         Index:           1
+
 ; check for elem segment initialized with __table_base global as offset
 
 ; CHECK:        - Type:            ELEM
 ; CHECK-NEXT:     Segments:
 ; CHECK-NEXT:       - Offset:
 ; CHECK-NEXT:           Opcode:          GLOBAL_GET
 ; CHECK-NEXT:           Index:           2
-; CHECK-NEXT:         Functions:       [ 1, 0 ]
+; CHECK-NEXT:         Functions:       [ 3, 0 ]
+
+; check the generated code in __wasm_call_ctors and __wasm_apply_relocs functions
+; TODO(sbc): Disassemble and verify instructions.
+
+; CHECK:        - Type:            CODE
+; CHECK-NEXT:     Functions:
+; CHECK-NEXT:       - Index:           1
+; CHECK-NEXT:         Locals:          []
+; CHECK-NEXT:         Body:            10020B
+; CHECK-NEXT:       - Index:           2
+; CHECK-NEXT:         Locals:          []
+; CHECK-NEXT:         Body:            230141046A230241006A360002230141086A230241016A3600022301410C6A230141006A360002230141106A23033600020
 
 ; check the data segment initialized with __memory_base global as offset
 
 ; CHECK:        - Type:            DATA
 ; CHECK-NEXT:     Segments:
 ; CHECK-NEXT:       - SectionOffset:   6
 ; CHECK-NEXT:         InitFlags:       0
 ; CHECK-NEXT:         Offset:
 ; CHECK-NEXT:           Opcode:          GLOBAL_GET
 ; CHECK-NEXT:           Index:           1
-; CHECK-NEXT:         Content:         '0000000001000000'
+; CHECK-NEXT:         Content:         '0200000000000000010000000000000000000000'

lld/wasm/Driver.cpp

case OPT_whole_archive:
       break;
     case OPT_no_whole_archive:
       InWholeArchive = false;
       break;
     }
   }
 }
 
-static StringRef getEntry(opt::InputArgList &Args, StringRef Default) {
+static StringRef getEntry(opt::InputArgList &Args) {
   auto *Arg = Args.getLastArg(OPT_entry, OPT_no_entry);
-  if (!Arg)
-    return Default;
+  if (!Arg) {
+    if (Args.hasArg(OPT_relocatable))
+      return "";
+    if (Args.hasArg(OPT_shared))
+      return "__wasm_call_ctors";
+    return "_start";
+  }
   if (Arg->getOption().getID() == OPT_no_entry)
     return "";
   return Arg->getValue();
 }
 
 // Some Config members do not directly correspond to any particular
 // command line options, but computed based on other Config values.
 // This function initialize such members. See Config.h for the details
 // of these values.
 static void setConfigs(opt::InputArgList &Args) {
   Config->AllowUndefined = Args.hasArg(OPT_allow_undefined);
   Config->CompressRelocations = Args.hasArg(OPT_compress_relocations);
   Config->Demangle = Args.hasFlag(OPT_demangle, OPT_no_demangle, true);
   Config->DisableVerify = Args.hasArg(OPT_disable_verify);
-  Config->Entry = getEntry(Args, Args.hasArg(OPT_relocatable) ? "" : "_start");
+  Config->Entry = getEntry(Args);
   Config->ExportAll = Args.hasArg(OPT_export_all);
   Config->ExportDynamic = Args.hasFlag(OPT_export_dynamic,
       OPT_no_export_dynamic, false);
   Config->ExportTable = Args.hasArg(OPT_export_table);
   errorHandler().FatalWarnings =
       Args.hasFlag(OPT_fatal_warnings, OPT_no_fatal_warnings, false);
   Config->ImportMemory = Args.hasArg(OPT_import_memory);
   Config->SharedMemory = Args.hasArg(OPT_shared_memory);

 
 // Create ABI-defined synthetic symbols
 static void createSyntheticSymbols() {
   static WasmSignature NullSignature = {{}, {}};
   static llvm::wasm::WasmGlobalType GlobalTypeI32 = {WASM_TYPE_I32, false};
   static llvm::wasm::WasmGlobalType MutableGlobalTypeI32 = {WASM_TYPE_I32,
                                                             true};
 
-  if (!Config->Relocatable)
+  if (!Config->Relocatable) {
     WasmSym::CallCtors = Symtab->addSyntheticFunction(
         "__wasm_call_ctors", WASM_SYMBOL_VISIBILITY_HIDDEN,
         make<SyntheticFunction>(NullSignature, "__wasm_call_ctors"));
 
+    if (Config->Pic) {
+      // For PIC code we create a synthetic function call __wasm_apply_relocs
+      // and add this as the first call in __wasm_call_ctors.
+      // We also unconditionally export 
+      WasmSym::ApplyRelocs = Symtab->addSyntheticFunction(
+          "__wasm_apply_relocs", WASM_SYMBOL_VISIBILITY_HIDDEN,
+          make<SyntheticFunction>(NullSignature, "__wasm_apply_relocs"));
+    }
+  }
+
   // The __stack_pointer is imported in the shared library case, and exported
   // in the non-shared (executable) case.
   if (Config->Shared) {
     WasmSym::StackPointer =
         createUndefinedGlobal("__stack_pointer", &MutableGlobalTypeI32);
   } else {
     llvm::wasm::WasmGlobal Global;
     Global.Type = {WASM_TYPE_I32, true};
void LinkerDriver::link(ArrayRef<const char *> ArgsArr) {
   Config->Pic = Config->Pie || Config->Shared;
 
   if (Config->Pic) {
     if (Config->ExportTable)
       error("-shared/-pie is incompatible with --export-table");
     Config->ImportTable = true;
   }
 
-  if (Config->Shared) {
-    Config->ExportDynamic = true;
-    Config->AllowUndefined = true;
-  }
-
   // Handle --trace-symbol.
   for (auto *Arg : Args.filtered(OPT_trace_symbol))
     Symtab->trace(Arg->getValue());
 
   if (!Config->Relocatable)
     createSyntheticSymbols();
 
+  if (Config->Shared) {
+    Config->ExportDynamic = true;
+    Config->AllowUndefined = true;
+  }
+
   createFiles(Args);
   if (errorCount())
     return;
 
   // Add all files to the symbol table. This will add almost all
   // symbols that we need to the symbol table.
   for (InputFile *F : Files)
     Symtab->addFile(F);
   if (errorCount())
     return;
 
   // Handle the `--undefined <sym>` options.
   for (auto *Arg : Args.filtered(OPT_undefined))
     handleUndefined(Arg->getValue());
 
   Symbol *EntrySym = nullptr;
-  if (!Config->Relocatable) {
-    if (!Config->Shared && !Config->Entry.empty()) {
-      EntrySym = handleUndefined(Config->Entry);
-      if (EntrySym && EntrySym->isDefined())
-        EntrySym->ForceExport = true;
-      else
-        error("entry symbol not defined (pass --no-entry to supress): " +
-              Config->Entry);
-    }
-  }
+  if (!Config->Relocatable && !Config->Entry.empty()) {
 
   if (errorCount())
     return;
 
   // Handle the `--export <sym>` options
   // This works like --undefined but also exports the symbol if its found
   for (auto *Arg : Args.filtered(OPT_export))
     handleUndefined(Arg->getValue());

lld/wasm/InputChunks.h

 // each global variable.
 class InputSegment : public InputChunk {
 public:
   InputSegment(const WasmSegment &Seg, ObjFile *F)
       : InputChunk(F, InputChunk::DataSegment), Segment(Seg) {}
 
   static bool classof(const InputChunk *C) { return C->kind() == DataSegment; }
 
+  void generateRelocationCode(raw_ostream &OS) const;
+
   uint32_t getAlignment() const { return Segment.Data.Alignment; }
   StringRef getName() const override { return Segment.Data.Name; }
   StringRef getDebugName() const override { return StringRef(); }
   uint32_t getComdat() const override { return Segment.Data.Comdat; }
   uint32_t getInputSectionOffset() const override {
     return Segment.SectionOffset;
   }
 

lld/wasm/InputChunks.cpp

for (const WasmRelocation &Rel : Relocations) {
     LastRelocEnd = SecStart + Rel.Offset + getRelocWidthPadded(Rel);
   }
 
   unsigned ChunkSize = End - LastRelocEnd;
   LLVM_DEBUG(dbgs() << "  write final chunk: " << ChunkSize << "\n");
   memcpy(Buf, LastRelocEnd, ChunkSize);
   LLVM_DEBUG(dbgs() << "  total: " << (Buf + ChunkSize - Orig) << "\n");
 }
+
+// Generate code to apply relocations to the data section at runtime.
+// This is only called when generating shared libaries (PIC) where address are
+// not known at static link time.
+void InputSegment::generateRelocationCode(raw_ostream &OS) const {
+  int32_t SegmentVA = OutputSeg->StartVA + OutputSegmentOffset;
+  for (const WasmRelocation &Rel : Relocations) {
+    uint32_t Offset = Rel.Offset - getInputSectionOffset();
+    uint32_t OutputVA = SegmentVA + Offset;
+
+    // Get __memory_base
+    writeU8(OS, WASM_OPCODE_GLOBAL_GET, "GLOBAL_GET");
+    writeUleb128(OS, WasmSym::MemoryBase->getGlobalIndex(), "memory_base");
+
+    // Add the offset of the relocation
+    writeU8(OS, WASM_OPCODE_I32_CONST, "I32_CONST");
+    writeSleb128(OS, OutputVA, "offset");
+    writeU8(OS, WASM_OPCODE_I32_ADD, "ADD");
+
+    // Now figure out what we want to store
+    switch (Rel.Type) {
+    case R_WASM_TABLE_INDEX_I32:
+      // Add the table index to the __table_base
+      writeU8(OS, WASM_OPCODE_GLOBAL_GET, "GLOBAL_GET");
+      writeUleb128(OS, WasmSym::TableBase->getGlobalIndex(), "table_base");
+      writeU8(OS, WASM_OPCODE_I32_CONST, "CONST");
+      writeSleb128(OS, File->calcNewValue(Rel), "new table index");
+      writeU8(OS, WASM_OPCODE_I32_ADD, "ADD");
+      break;
+    case R_WASM_MEMORY_ADDR_I32: {
+      Symbol *Sym = File->getSymbol(Rel);
+      if (auto *UD = dyn_cast<UndefinedData>(Sym)) {
+        // Undefined global addresses are accessed via imported globals
+        writeU8(OS, WASM_OPCODE_GLOBAL_GET, "GLOBAL_GET");
+        writeUleb128(OS, UD->getGlobalIndex(), "global index");
+      } else {
+        // Defined global data is accessed via offset from __memory_base
+        writeU8(OS, WASM_OPCODE_GLOBAL_GET, "GLOBAL_GET");
+        writeUleb128(OS, WasmSym::MemoryBase->getGlobalIndex(), "memory_base");
+        writeU8(OS, WASM_OPCODE_I32_CONST, "CONST");
+        writeSleb128(OS, File->calcNewValue(Rel), "new memory offset");
+        writeU8(OS, WASM_OPCODE_I32_ADD, "ADD");
+      }
+      break;
+    }
+    default:
+      llvm_unreachable("unexpected relocation type in data segment");
+    }
+
+    // Store that value at the virtual address
+    writeU8(OS, WASM_OPCODE_I32_STORE, "I32_STORE");
+    writeUleb128(OS, 0, "offset");
+    writeUleb128(OS, 2, "align");
+  }
+}

lld/wasm/InputFiles.h

public:
   const WasmObjectFile *getWasmObj() const { return WasmObj.get(); }
 
   void dumpInfo() const;
 
   uint32_t calcNewIndex(const WasmRelocation &Reloc) const;
   uint32_t calcNewValue(const WasmRelocation &Reloc) const;
   uint32_t calcNewAddend(const WasmRelocation &Reloc) const;
   uint32_t calcExpectedValue(const WasmRelocation &Reloc) const;
+  Symbol *getSymbol(const WasmRelocation &Reloc) const {
+    return Symbols[Reloc.Index];
+  };
 
   const WasmSection *CodeSection = nullptr;
   const WasmSection *DataSection = nullptr;
   const WasmSection *ProducersSection = nullptr;
 
   // Maps input type indices to output type indices
   std::vector<uint32_t> TypeMap;
   std::vector<bool> TypeIsUsed;

lld/wasm/MarkLive.cpp

void lld::wasm::markLive() {
   if (Config->Relocatable) {
     for (const ObjFile *Obj : Symtab->ObjectFiles) {
       const WasmLinkingData &L = Obj->getWasmObj()->linkingData();
       for (const WasmInitFunc &F : L.InitFunctions)
         Enqueue(Obj->getFunctionSymbol(F.Symbol));
     }
   }
 
+  if (Config->Pic) {
+    Enqueue(WasmSym::CallCtors);
+    Enqueue(WasmSym::ApplyRelocs);
+  }
+
   // Follow relocations to mark all reachable chunks.
   while (!Q.empty()) {
     InputChunk *C = Q.pop_back_val();
 
     for (const WasmRelocation Reloc : C->getRelocations()) {
       if (Reloc.Type == R_WASM_TYPE_INDEX_LEB)
         continue;
       Symbol *Sym = C->File->getSymbol(Reloc.Index);

lld/wasm/Symbols.h

struct WasmSym {
   // memory following this address is not used by the linked code and can
   // therefore be used as a backing store for brk()/malloc() implementations.
   static DefinedData *HeapBase;
 
   // __wasm_call_ctors
   // Function that directly calls all ctors in priority order.
   static DefinedFunction *CallCtors;
 
+  // __wasm_apply_relocs
+  // Function that applies relocations to data segment post-instantiation.
+  static DefinedFunction *ApplyRelocs;
+
   // __dso_handle
   // Symbol used in calls to __cxa_atexit to determine current DLL
   static DefinedData *DsoHandle;
 
   // __table_base
   // Used in PIC code for offset of indirect function table
   static UndefinedGlobal *TableBase;
 

lld/wasm/Symbols.cpp

 #define DEBUG_TYPE "lld"
 
 using namespace llvm;
 using namespace llvm::wasm;
 using namespace lld;
 using namespace lld::wasm;
 
 DefinedFunction *WasmSym::CallCtors;
+DefinedFunction *WasmSym::ApplyRelocs;
 DefinedData *WasmSym::DsoHandle;
 DefinedData *WasmSym::DataEnd;
 DefinedData *WasmSym::HeapBase;
 GlobalSymbol *WasmSym::StackPointer;
 UndefinedGlobal *WasmSym::TableBase;
 UndefinedGlobal *WasmSym::MemoryBase;
 
 WasmSymbolType Symbol::getWasmType() const {

lld/wasm/Writer.cpp

public:
   void run();
 
 private:
   void openFile();
 
   uint32_t lookupType(const WasmSignature &Sig);
   uint32_t registerType(const WasmSignature &Sig);
 
-  void createCtorFunction();
+  void createApplyRelocationsFunction();
+  void createCallCtorsFunction();
+
   void calculateInitFunctions();
   void assignIndexes();
   void calculateImports();
   void calculateExports();
   void calculateCustomSections();
   void assignSymtab();
   void calculateTypes();
   void createOutputSegments();
for (InputSegment *Segment : File->Segments) {
         Segments.push_back(S);
       }
       S->addInputSegment(Segment);
       LLVM_DEBUG(dbgs() << "added data: " << Name << ": " << S->Size << "\n");
     }
   }
 }
 
-static const int OPCODE_CALL = 0x10;
-static const int OPCODE_END = 0xb;
+// For -shared (PIC) output, we create create a synthetic function which will
+// apply any relocations to the data segments on startup.  This function is
+// called __wasm_apply_relocs and is added at the very beginning of
+// __wasm_call_ctors before any of the constructors run.
+void Writer::createApplyRelocationsFunction() {
+  LLVM_DEBUG(dbgs() << "createApplyRelocationsFunction\n");
+  // First write the body's contents to a string.
+  std::string BodyContent;
+  {
+    raw_string_ostream OS(BodyContent);
+    writeUleb128(OS, 0, "num locals");
+    for (const OutputSegment *Seg : Segments)
+      for (const InputSegment *InSeg : Seg->InputSegments)
+        InSeg->generateRelocationCode(OS);
+    writeU8(OS, WASM_OPCODE_END, "END");
+  }
+
+  // Once we know the size of the body we can create the final function body
+  std::string FunctionBody;
+  {
+    raw_string_ostream OS(FunctionBody);
+    writeUleb128(OS, BodyContent.size(), "function size");
+    OS << BodyContent;
+  }
+
+  ArrayRef<uint8_t> Body = arrayRefFromStringRef(Saver.save(FunctionBody));
+  cast<SyntheticFunction>(WasmSym::ApplyRelocs->Function)->setBody(Body);
+}
 
 // Create synthetic "__wasm_call_ctors" function based on ctor functions
 // in input object.
-void Writer::createCtorFunction() {
+void Writer::createCallCtorsFunction() {
   if (!WasmSym::CallCtors->isLive())
     return;
 
   // First write the body's contents to a string.
   std::string BodyContent;
   {
     raw_string_ostream OS(BodyContent);
     writeUleb128(OS, 0, "num locals");
+    if (Config->Pic) {
+      writeU8(OS, WASM_OPCODE_CALL, "CALL");
+      writeUleb128(OS, WasmSym::ApplyRelocs->getFunctionIndex(),
+                   "function index");
+    }
     for (const WasmInitEntry &F : InitFunctions) {
-      writeU8(OS, OPCODE_CALL, "CALL");
+      writeU8(OS, WASM_OPCODE_CALL, "CALL");
       writeUleb128(OS, F.Sym->getFunctionIndex(), "function index");
     }
-    writeU8(OS, OPCODE_END, "END");
+    writeU8(OS, WASM_OPCODE_END, "END");
   }
 
   // Once we know the size of the body we can create the final function body
   std::string FunctionBody;
   {
     raw_string_ostream OS(FunctionBody);
     writeUleb128(OS, BodyContent.size(), "function size");
     OS << BodyContent;
if (!Config->Pic)
     TableBase = 1;
 
   log("-- calculateImports");
   calculateImports();
   log("-- assignIndexes");
   assignIndexes();
   log("-- calculateInitFunctions");
   calculateInitFunctions();
-  if (!Config->Relocatable)
-    createCtorFunction();
   log("-- calculateTypes");
   calculateTypes();
   log("-- layoutMemory");
   layoutMemory();
+  if (!Config->Relocatable) {
+    if (Config->Pic)
+      createApplyRelocationsFunction();
+    createCallCtorsFunction();
+  }
   log("-- calculateExports");
   calculateExports();
   log("-- calculateCustomSections");
   calculateCustomSections();
   log("-- assignSymtab");
   assignSymtab();
 
   if (errorHandler().Verbose) {

llvm/include/llvm/BinaryFormat/Wasm.h

enum : unsigned {
   WASM_EXTERNAL_MEMORY = 0x2,
   WASM_EXTERNAL_GLOBAL = 0x3,
   WASM_EXTERNAL_EVENT = 0x4,
 };
 
 // Opcodes used in initializer expressions.
 enum : unsigned {
   WASM_OPCODE_END = 0x0b,
+  WASM_OPCODE_CALL = 0x10,
   WASM_OPCODE_GLOBAL_GET = 0x23,
+  WASM_OPCODE_I32_STORE = 0x36,
   WASM_OPCODE_I32_CONST = 0x41,
   WASM_OPCODE_I64_CONST = 0x42,
   WASM_OPCODE_F32_CONST = 0x43,
   WASM_OPCODE_F64_CONST = 0x44,
+  WASM_OPCODE_I32_ADD = 0x6a,
 };
 
 enum : unsigned {
   WASM_LIMITS_FLAG_HAS_MAX = 0x1,
   WASM_LIMITS_FLAG_IS_SHARED = 0x2,
 };
 
 enum : unsigned {