[lld][WebAssembly] Add support for -Bsymbolic

[sbc100]

Summary

This flag works in a similar way to the ELF linker in that it
will resolve any defined symbols to their local definition with
a shared library.

This is also the default behavior for or -pie executables.

[sbc100]

comments

[sbc100]

comments

[sbc100]

This change will allows us to remove the corresponding binaryen code: https://github.com/WebAssembly/binaryen/pull/3211 and instead pass -Bsymbolic when linking MAIN_MODULE's in emscripten.

[MaskRay]

lld/wasm/Driver.cpp

496

In ELF, -Bsymbolic is redundant for executables (-no-pie or -pie).

[sbc100]

lld/wasm/Driver.cpp

496

Interesting, so you are saying the -Bsymbolic is basically the default for executable?

Wouldn't that mean that, for example, LD_PRELOAD would not work for symbols in the main executable? My understanding is that -Bsymbolic would prevent LD_PRELOAD from overriding symbols because they would be bound locally. Although I guess I am wrong?

[sbc100]

lld/wasm/Driver.cpp

496

Indeed you are right, it looks like LD_PRELOAD as no effect on the main executable itself. TIL!

[sbc100]

feedback

[sbc100]

revert

[MaskRay]

lld/wasm/Driver.cpp

496

-Bsymbolic is basically the default for executable.
The symbol resolution order: exe, preloaded, needed

In preloaded, the LD_PRELOADed library is listed in a breadth-first search order.
needed is similar.

[jhenderson]

sbc100 edited reviewers, ... removed: jhenderson.

(I've got a herald rule to auto-add myself to reviews touching llvm-readobj amongst other tools - no point trying to work around it!)

llvm/tools/llvm-readobj/WasmDumper.cpp

186–190

Shouldn't this bit have some dedicated llvm-readobj testing?

[sbc100]

In D89152#2324369, @jhenderson wrote:

sbc100 edited reviewers, ... removed: jhenderson.

(I've got a herald rule to auto-add myself to reviews touching llvm-readobj amongst other tools - no point trying to work around it!)

Sorry, didn't mean to try to work around your herald stuff, I also use herald to be notified about WebAssembly related thing. I think I was just trying to be precise about who I thought would be good reviewer. I won't remove your name anymore from that field.

In general, would it would make sense to add yourself to subscriber rather than reviewer if you want to monitor all changes in these areas? You could then add yourself as a reviewer to change that you care about? Or do you want to actually be a reviewer all of all change to lld? For example, this specific change, do you want to be a reviewer?

[sbc100]

llvm/tools/llvm-readobj/WasmDumper.cpp

186–190

Yes, actually I think I will revert this part since I'm not actually using readobj in the testing anymore.

I will land this separately with its own test.

[sbc100]

In D89152#2324938, @sbc100 wrote:

In D89152#2324369, @jhenderson wrote:

sbc100 edited reviewers, ... removed: jhenderson.

(I've got a herald rule to auto-add myself to reviews touching llvm-readobj amongst other tools - no point trying to work around it!)

Sorry, didn't mean to try to work around your herald stuff, I also use herald to be notified about WebAssembly related thing. I think I was just trying to be precise about who I thought would be good reviewer. I won't remove your name anymore from that field.

In general, would it would make sense to add yourself to subscriber rather than reviewer if you want to monitor all changes in these areas? You could then add yourself as a reviewer to change that you care about? Or do you want to actually be a reviewer all of all change to lld? For example, this specific change, do you want to be a reviewer?

Sorry, I see now that it was probably the fact that I touched objdump here that added you as a reviewer. My comment is less relevant in that case I guess.

[jhenderson]

In D89152#2324952, @sbc100 wrote:

In D89152#2324938, @sbc100 wrote:

In D89152#2324369, @jhenderson wrote:

sbc100 edited reviewers, ... removed: jhenderson.

(I've got a herald rule to auto-add myself to reviews touching llvm-readobj amongst other tools - no point trying to work around it!)

Sorry, didn't mean to try to work around your herald stuff, I also use herald to be notified about WebAssembly related thing. I think I was just trying to be precise about who I thought would be good reviewer. I won't remove your name anymore from that field.

In general, would it would make sense to add yourself to subscriber rather than reviewer if you want to monitor all changes in these areas? You could then add yourself as a reviewer to change that you care about? Or do you want to actually be a reviewer all of all change to lld? For example, this specific change, do you want to be a reviewer?

Sorry, I see now that it was probably the fact that I touched objdump here that added you as a reviewer. My comment is less relevant in that case I guess.

No problem! I'm keen to keep an eye on patches in the LLVM binutils (readelf, objdump etc), mostly for ELF, but I often chip in on other platforms too, in an effort to maintain consistency, make sure documentation is sorted etc. I'm not bothered by LLD (and don't have a herald rule setup for that), though I do sometimes help out with reviews in the ELF part of LLD too.

[sbc100]

Revert readobj part

[sbc100]

bsymbol is the default baviour for executables

[sbc100]

comment

[sbc100]

• typo

[kripken]

I'm not an expert on the LLVM details here, but, the logic looks correct and that it properly corresponds to the original idea of this optimization (that this will replace).

[MaskRay]

lld/wasm/Driver.cpp

496

I was wrong about the symbol resolution order.

In musl, LD_PRELOAD libraries are prepended to the DT_NEEDED list. The resolution order is a breadth-first search order starting from the executable, i.e. the order may be:
exe, preload0, preload1, needed0, needed1, needd0_of_preload0, needed1_of_preload0, needd0_of_needed0, ...

[sbc100]

lld/wasm/Driver.cpp

496

Thanks for the update. The only thing that this change does now is to bind symbols in the executable (and -Bsymbolic libraries) to local definition (if they exist).

We have no concept of LD_PRELOAD yet in the WebAssembly (or emscripten) world.

Any objections to landing this change?

[MaskRay]

lld/wasm/Driver.cpp

496

No objection (just wanted to mention that in ELF linkers, they don't warn about this combo).

The nice thing with the ELF behavior is that: if a project deliberately uses -Bsymbolic, it does not need to differentiate executable linker options from shared object linker options.

I know really little about wasm, though.

[sbc100]

lld/wasm/Driver.cpp

496

I think eventually we will most likely do the same, but starting off more restrictive is probably safer.. we can always relax later, but tightening up restrictions is hard (because it can break people, as I'm sure you understand).

Our PIC ABI and shared library loading ABI still experimental so we actually don't want to encourage the use of this (or -pie or -shared) right now.

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 %t2.so 2>&1 | FileCheck -check-prefix=WARNING %s
+// WARNING: warning: -Bsymbolic is only meaningful when combined with -shared, or -pie
+
+// 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:            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:            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
+// SYMBOLIC-NEXT:      - Index:           3
+// SYMBOLIC-NEXT:        Type:            I32
+// SYMBOLIC-NEXT:        Mutable:         true
+// SYMBOLIC-NEXT:        InitExpr:
+// SYMBOLIC-NEXT:          Opcode:          I32_CONST
+// SYMBOLIC-NEXT:          Value:           0
+// SYMBOLIC-NEXT:      - Index:           4
+// SYMBOLIC-NEXT:        Type:            I32
+// SYMBOLIC-NEXT:        Mutable:         false
+// SYMBOLIC-NEXT:        InitExpr:
+// SYMBOLIC-NEXT:          Opcode:          I32_CONST
+// SYMBOLIC-NEXT:          Value:           0
+// SYMBOLIC-NEXT:  - Type:            EXPORT
+
+.globl foo
+foo:
+  .functype foo () -> ()
+  end_function
+
+.globl get_foo_address
+get_foo_address:
+  .functype get_foo_address () -> (i32)
+  global.get foo@GOT
+  end_function
+
+.globl get_bar_address
+get_bar_address:
+  .functype get_bar_address () -> (i32)
+  global.get bar@GOT
+  end_function
+
+.globl bar
+.section  .data.bar,"",@
+bar:
+  .int 42
+.size bar, 4

lld/wasm/Config.h

 namespace wasm {
 
 // This struct contains the global configuration for the linker.
 // Most fields are direct mapping from the command line options
 // and such fields have the same name as the corresponding options.
 // Most fields are initialized by the driver.
 struct Configuration {
   bool allowUndefined;
+  bool bsymbolic;
   bool checkFeatures;
   bool compressRelocations;
   bool demangle;
   bool disableVerify;
   bool experimentalPic;
   bool emitRelocs;
   bool exportAll;
   bool exportDynamic;

lld/wasm/Driver.cpp

static StringRef getEntry(opt::InputArgList &args) {
   if (arg->getOption().getID() == OPT_no_entry)
     return "";
   return arg->getValue();
 }
 
 // Initializes Config members by the command line options.
 static void readConfigs(opt::InputArgList &args) {
   config->allowUndefined = args.hasArg(OPT_allow_undefined);
+  config->bsymbolic = args.hasArg(OPT_Bsymbolic);
   config->checkFeatures =
       args.hasFlag(OPT_check_features, OPT_no_check_features, true);
   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->emitRelocs = args.hasArg(OPT_emit_relocs);
   config->experimentalPic = args.hasArg(OPT_experimental_pic);
   config->entry = getEntry(args);
if (config->shared) {
       warn("creating shared libraries, with -shared, is not yet stable");
     }
 
     // -pie will change meaning when Module Linking is implemented.
     if (config->pie) {
       warn("creating PIEs, with -pie, is not yet stable");
     }
   }
+
+  if (config->bsymbolic && (!config->pie && !config->shared)) {
+    warn("-Bsymbolic is only meaningful when combined with -shared, or -pie");
+  }
 }
 
 // Force Sym to be entered in the output. Used for -u or equivalent.
 static Symbol *handleUndefined(StringRef name) {
   Symbol *sym = symtab->find(name);
   if (!sym)
     return nullptr;
 

lld/wasm/Options.td

 }
 
 multiclass B<string name, string help1, string help2> {
   def NAME: Flag<["--", "-"], name>, HelpText<help1>;
   def no_ # NAME: Flag<["--", "-"], "no-" # name>, HelpText<help2>;
 }
 
 // The following flags are shared with the ELF linker
+def Bsymbolic: F<"Bsymbolic">, HelpText<"Bind defined symbols locally">;
+
 def color_diagnostics: F<"color-diagnostics">,
   HelpText<"Use colors in diagnostics">;
 
 def color_diagnostics_eq: J<"color-diagnostics=">,
   HelpText<"Use colors in diagnostics; one of 'always', 'never', 'auto'">;
 
 def compress_relocations: F<"compress-relocations">,
   HelpText<"Compress the relocation targets in the code section.">;

lld/wasm/Relocations.cpp

 #include "InputChunks.h"
 #include "SyntheticSections.h"
 
 using namespace llvm;
 using namespace llvm::wasm;
 
 namespace lld {
 namespace wasm {
+
 static bool requiresGOTAccess(const Symbol *sym) {
-  return config->isPic && !sym->isHidden() && !sym->isLocal();
+  if (!config->isPic)
+    return false;
+  if (sym->isHidden() || sym->isLocal())
+    return false;
+  // With `-Bsymbolic` we skip the GOT import for symbols that are defined
+  // within the current module.
+  if (config->bsymbolic && sym->isDefined())
+    return false;
+  return true;
 }
 
 static bool allowUndefined(const Symbol* sym) {
   // Undefined functions and globals with explicit import name are allowed to be
   // undefined at link time.
   if (auto *f = dyn_cast<UndefinedFunction>(sym))
     if (f->importName)
       return true;
   if (auto *g = dyn_cast<UndefinedGlobal>(sym))
     if (g->importName)
       return true;
   return (config->allowUndefined ||
           config->allowUndefinedSymbols.count(sym->getName()) != 0);
 }
 
 static void reportUndefined(const Symbol* sym) {
   assert(sym->isUndefined());
   assert(!sym->isWeak());
   if (!allowUndefined(sym))
     error(toString(sym->getFile()) + ": undefined symbol: " + toString(*sym));
 }
 
 static void addGOTEntry(Symbol *sym) {
-  // In PIC mode a GOT entry is an imported global that the dynamic linker
-  // will assign.
-  // In non-PIC mode (i.e. when code compiled as fPIC is linked into a static
-  // binary) we create an internal wasm global with a fixed value that takes the
-  // place of th GOT entry and effectivly acts as an i32 const. This can
-  // potentially be optimized away at runtime or with a post-link tool.
-  // TODO(sbc): Linker relaxation might also be able to optimize this away.
-  if (config->isPic)
+  if (requiresGOTAccess(sym))
     out.importSec->addGOTEntry(sym);
   else
-    out.globalSec->addStaticGOTEntry(sym);
+    out.globalSec->addInternalGOTEntry(sym);
 }
 
 void scanRelocations(InputChunk *chunk) {
   if (!chunk->live)
     return;
   ObjFile *file = chunk->file;
   ArrayRef<WasmSignature> types = file->getWasmObj()->types();
   for (const WasmRelocation &reloc : chunk->getRelocations()) {

lld/wasm/SyntheticSections.h

 };
 
 class GlobalSection : public SyntheticSection {
 public:
   GlobalSection() : SyntheticSection(llvm::wasm::WASM_SEC_GLOBAL) {}
   uint32_t numGlobals() const {
     assert(isSealed);
     return inputGlobals.size() + dataAddressGlobals.size() +
-           staticGotSymbols.size();
+           internalGotSymbols.size();
   }
   bool isNeeded() const override { return numGlobals() > 0; }
   void assignIndexes() override;
   void writeBody() override;
   void addGlobal(InputGlobal *global);
   void addDataAddressGlobal(DefinedData *global);
-  void addStaticGOTEntry(Symbol *sym);
+
+  // Add an internal GOT entry global that corresponds to the given symbol.
+  // Normally GOT entries are imported and assigned by the external dynamic
+  // linker.  However, when linking PIC code statically or when linking with
+  // -Bsymbolic we can internalize GOT entries by declaring globals the hold
+  // symbol addresses.
+  //
+  // For the static linking case these internal globals can be completely
+  // elimiantred by a post-link optimizer such as wasm-opt.
+  //
+  // TODO(sbc): Another approach to optimizing these away could be to use
+  // specific relocation types combined with linker relaxation which could
+  // transform a `global.get` to an `i32.const`.
+  void addInternalGOTEntry(Symbol *sym);
+  void generateRelocationCode(raw_ostream &os) const;
 
   std::vector<const DefinedData *> dataAddressGlobals;
 
 protected:
   bool isSealed = false;
   std::vector<InputGlobal *> inputGlobals;
-  std::vector<Symbol *> staticGotSymbols;
+  std::vector<Symbol *> internalGotSymbols;
 };
 
 class ExportSection : public SyntheticSection {
 public:
   ExportSection() : SyntheticSection(llvm::wasm::WASM_SEC_EXPORT) {}
   bool isNeeded() const override { return exports.size() > 0; }
   void writeBody() override;
 

lld/wasm/SyntheticSections.cpp

void EventSection::addEvent(InputEvent *event) {
   event->setEventIndex(eventIndex);
   inputEvents.push_back(event);
 }
 
 void GlobalSection::assignIndexes() {
   uint32_t globalIndex = out.importSec->getNumImportedGlobals();
   for (InputGlobal *g : inputGlobals)
     g->setGlobalIndex(globalIndex++);
-  for (Symbol *sym : staticGotSymbols)
+  for (Symbol *sym : internalGotSymbols)
     sym->setGOTIndex(globalIndex++);
   isSealed = true;
 }
 
-void GlobalSection::addStaticGOTEntry(Symbol *sym) {
+void GlobalSection::addInternalGOTEntry(Symbol *sym) {
   assert(!isSealed);
   if (sym->requiresGOT)
     return;
-  LLVM_DEBUG(dbgs() << "addStaticGOTEntry: " << sym->getName() << " "
+  LLVM_DEBUG(dbgs() << "addInternalGOTEntry: " << sym->getName() << " "
                     << toString(sym->kind()) << "\n");
   sym->requiresGOT = true;
   if (auto *F = dyn_cast<FunctionSymbol>(sym))
     out.elemSec->addEntry(F);
-  staticGotSymbols.push_back(sym);
+  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)
+                                ? WASM_OPCODE_I64_ADD
+                                : WASM_OPCODE_I32_ADD;
+
+  for (const Symbol *sym : internalGotSymbols) {
+    if (auto *d = dyn_cast<DefinedData>(sym)) {
+      // Get __memory_base
+      writeU8(os, WASM_OPCODE_GLOBAL_GET, "GLOBAL_GET");
+      writeUleb128(os, WasmSym::memoryBase->getGlobalIndex(), "__memory_base");
+
+      // Add the virtual address of the data symbol
+      writeU8(os, opcode_ptr_const, "CONST");
+      writeSleb128(os, d->getVirtualAddress(), "offset");
+    } else if (auto *f = dyn_cast<FunctionSymbol>(sym)) {
+      // Get __table_base
+      writeU8(os, WASM_OPCODE_GLOBAL_GET, "GLOBAL_GET");
+      writeUleb128(os, WasmSym::tableBase->getGlobalIndex(), "__table_base");
+
+      // Add the table index to __table_base
+      writeU8(os, opcode_ptr_const, "CONST");
+      writeSleb128(os, f->getTableIndex(), "offset");
+    } else {
+      assert(isa<UndefinedData>(sym));
+      continue;
+    }
+    writeU8(os, opcode_ptr_add, "ADD");
+    writeU8(os, WASM_OPCODE_GLOBAL_SET, "GLOBAL_SET");
+    writeUleb128(os, sym->getGOTIndex(), "got_entry");
+  }
 }
 
 void GlobalSection::writeBody() {
   raw_ostream &os = bodyOutputStream;
 
   writeUleb128(os, numGlobals(), "global count");
   for (InputGlobal *g : inputGlobals)
     writeGlobal(os, g->global);
   // TODO(wvo): when do these need I64_CONST?
-  for (const Symbol *sym : staticGotSymbols) {
+  for (const Symbol *sym : internalGotSymbols) {
     WasmGlobal global;
-    global.Type = {WASM_TYPE_I32, false};
+    global.Type = {WASM_TYPE_I32, config->isPic};
     global.InitExpr.Opcode = WASM_OPCODE_I32_CONST;
     if (auto *d = dyn_cast<DefinedData>(sym))
       global.InitExpr.Value.Int32 = d->getVirtualAddress();
     else if (auto *f = dyn_cast<FunctionSymbol>(sym))
       global.InitExpr.Value.Int32 = f->getTableIndex();
     else {
       assert(isa<UndefinedData>(sym));
       global.InitExpr.Value.Int32 = 0;

lld/wasm/Writer.cpp

 // 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");
+
+    // First apply relocations to any internalized GOT entries.  These
+    // are the result of relaxation when building with -Bsymbolic.
+    out.globalSec->generateRelocationCode(os);
+
+    // Next apply any realocation to the data section by reading GOT entry
+    // globals.
     for (const OutputSegment *seg : segments)
       for (const InputSegment *inSeg : seg->inputSegments)
         inSeg->generateRelocationCode(os);
+
     writeU8(os, WASM_OPCODE_END, "END");
   }
 
   createFunction(WasmSym::applyRelocs, bodyContent);
 }
 
 // Create synthetic "__wasm_call_ctors" function based on ctor functions
 // in input object.

llvm/tools/llvm-readobj/WasmDumper.cpp

case wasm::WASM_SEC_DATA: {
         DictScope Group(W, "Segment");
         if (!Seg.Name.empty())
           W.printString("Name", Seg.Name);
         W.printNumber("Size", static_cast<uint64_t>(Seg.Content.size()));
         if (Seg.Offset.Opcode == wasm::WASM_OPCODE_I32_CONST)
           W.printNumber("Offset", Seg.Offset.Value.Int32);
         else if (Seg.Offset.Opcode == wasm::WASM_OPCODE_I64_CONST)
           W.printNumber("Offset", Seg.Offset.Value.Int64);
-        else
+        else if (Seg.Offset.Opcode == wasm::WASM_OPCODE_GLOBAL_GET) {
+          ListScope Group(W, "Offset");
+          W.printNumber("Global", Seg.Offset.Value.Global);
+        } else
           llvm_unreachable("unknown init expr opcode");
       }
       break;
     }
     case wasm::WASM_SEC_MEMORY:
       ListScope Group(W, "Memories");
       for (const wasm::WasmLimits &Memory : Obj->memories()) {
         DictScope Group(W, "Memory");
         W.printNumber("InitialPages", Memory.Initial);