[WebAssembly] Handle weak undefined functions with a synthetic stub

[ncw]

Summary

This error case is described in Linking.md. The operand for call requires generation of a synthetic stub.

Add test for this case.

[sbc100]

wasm/InputFiles.cpp

91

i'm curious, is llc capable of generating such a call or will it always using call_indirect in this case?

if possible I'd rather generate the test inputs from bitcode (or ever better assembly) rather than basically checking in binary code.

[sbc100]

wasm/InputFiles.cpp

97

Would it make more sense to check !Sym->isDefined()?

[ncw]

wasm/InputFiles.cpp

91

Yes, llc can generate such a call. But I regard that as a bug and I'm going to submit a patch for it when I get round to it!

(I've filed this one in Bugzilla)

If you have code like this, then clang will currently generate an unlinkable object file:

void __attribute__((weak)) maybeFn(void);

void callOrSkip() {
  if (maybeFn) maybeFn();
}

There's really no other way to use weak undefined symbols! Yet currently we write out Wasm like this:

(func callOrSkip
  if (const.i32 @R_TABLE_INDEX_SLEB(maybeFn))
    call @R_FUNCTION_INDEX_SLEB(maybe)
)

It can't link because the call won't validate the Wasm type checker....

I reckon that the frontend should use call_indirect for all calls to weak functions that aren't defined in the translation unit, otherwise it's basically unusable.

97

You think? We're calling getOutputIndex on the line below, it seems like it's the obvious way to check whether that will succeed/fail!

[sbc100]

wasm/InputFiles.cpp

97

But the error message says the thing is undefined.

Actually, rethinking this I think you are right. Since we can actually have undefined functions that do have their output index set in which case we don't want to fail here.

I kind of want there to be a better why to check for this particular case though, some kind of "isNeitherDefinedNorUndefined()".. but I'm ok with this for now.

[ncw]

You said "I'm OK with this for now" in the last comment - is the PR as a whole OK to merge then?

[sbc100]

How about this for a longer term solution: When a relocation like this is found the linker can create a linker synthetic function which will abort.. a simple one might be "call_indirect 0" which we know.

For globals I think we can ban weak references, since there is no way to checking the address of a global before calling get_global in it.

I'm happy with the code change for now, but can you write the test as minimal piece of bitcode rather than yaml. (Is there some reason you didn't do that already?)

[ncw]

In D44028#1027253, @sbc100 wrote:

How about this for a longer term solution: When a relocation like this is found the linker can create a linker synthetic function which will abort.. a simple one might be "call_indirect 0" which we know.

I thought about that too... the synthetic function would just be (func (type) unreachable) of course! It's messy as you need a separate one for each type signature. It adds quite a bit of "weight" and machinery to LLD.

It basically comes down to whether you think this should be "fixed" in LLD or LLC; should we make a dummy unreachable function in LLD or bodge LLC to emit call_indirect for weak-undefined calls. This patch is currently operating on the basis that the fix will be in LLC... but actually maybe you could convince me otherwise. We shouldn't really use call_indirect for things that aren't truly indirect, so even though it's a nuisance, maybe the linker-synthetic functions are right after all.

For globals I think we can ban weak references, since there is no way to checking the address of a global before calling get_global in it.

Hm, on reflection, I agree. We should disallow undefined globals, even if weak.

I'm happy with the code change for now, but can you write the test as minimal piece of bitcode rather than yaml. (Is there some reason you didn't do that already?)

I'm not sure I can, for the global case (there's no way to emit globals other than __stack_pointer currently). For the "call" case, I can change over to bitcode, OK.

[ncw]

OK, here's the new approach! It's basically the complete opposite of the previous approach. Weak undefined globals are disallowed entirely, and weak undefined functions are allowed and supported via some new synthetic stubs.

The tests have good coverage: they check that the synthetic stubs are eligible for GC, and check that the stub is emitted when needed.

[sbc100]

Thanks. Looks like a good approach. Good that we already had support for synthetic functions.

Lets see if there is any feedback on https://github.com/WebAssembly/tool-conventions/issues/46 before we land this.

test/wasm/undefined-weak-call.ll

88 ↗

(On Diff #137183)

Is it OK that all these will have the same name?

Perhaps its worth adding a test for two function with the same sig? And two functions with different sigs? (Either in this test file or separate).

test/wasm/undefined-weak-getglobal.test

8

Shall we make this even stronger and say that WEAK undefined symbols are not allowed for global at all, then we can put this check in the object file reader and we would need this check or this test in lld?

There is no point in having WEAK undefined symbols if they can't actually undefined at link time is there? Then it might as well be strong?

wasm/MarkLive.cpp

84 ↗

(On Diff #137183)

What would be the harm in marking them as live here?

wasm/SymbolTable.h

52 ↗

(On Diff #137183)

This formatting looks off (Can you run git clang-format origin/master?)

wasm/Writer.cpp

738 ↗

(On Diff #137183)

Is it worth making this getSyntheticFunctions, and then we can add the __wasm_call_ctors function to this list and it will get added via AddDefinedFunction too?

[ruiu]

test/wasm/undefined-weak-call.test

1

Use of yaml2obj is not encouraged. Is there any way to write it in .s or in .ll?

2

Please use wasm-ld. lld as a command is essentially deprecated.

[ncw]

test/wasm/undefined-weak-call.ll

88 ↗

(On Diff #137183)

Yes it should be OK. I'll check in a test though, you're right it's necessary.

test/wasm/undefined-weak-call.test

2

Already done in one case, I'll squash the other too. Thanks!

I've got rid of one of the yaml2obj uses, I'll get rid of the other based on Sam's improvement to push the check back into WasmObjectFile.

test/wasm/undefined-weak-getglobal.test

8

D'oh, of course, I somehow rationalised it to myself but yes, there's no point allowing the Weak flag on undefined globals at all, if it's only legal to link when the symbol is actually defined.

Then we'll all be happy because this test case can go, and we won't need to use yaml2obj, etc.

wasm/MarkLive.cpp

84 ↗

(On Diff #137183)

If they were marked live, they'd be included in the final binary even if never called. Just harmless bloat. Some of our existing tests do this - only ever call a weak undefined indirectly via its address. Since the address evaluates to zero, the stub is as dead as can be and seems a reasonable candidate for GC.

wasm/Writer.cpp

738 ↗

(On Diff #137183)

With some wider refactoring... there's a chicken-and-egg problem though.

Building the body (InputFunction) for CallCtors happens at the very end, since it doesn't have relocations and so needs all the function indexes to have been previously assigned. Hence we can't have the InputFunction for CallCtors available here in Writer::assignIndexes, where the indexes are set for the first time!

CallCtors is naturally a "late defined" synthetic (again assuming it's generated without relocs), and the weak stubs are naturally "early defined" (because to me it makes most sense to build them just before calling reportRemainingUndefines, since they do similar things).

If you want CallCtors to be processed via Writer::assignIndexes, then we'd have to generate the CallCtors body much earlier and actually generate relocs for it. That might actually be the better option - but it's for another commit.

[sbc100]

wasm/MarkLive.cpp

84 ↗

(On Diff #137183)

Hmm I think I see.. since the table index is 0, it can have its address taken, without needing the function body to be including. This is pretty obscure. Maybe a clearer comment.. its not the fact that it has an index already, but specifically that the index is 0 that allows us to do this, right? Otherwise the address taking would necessitate the liveness of the body, right?

[ncw]

Updated: addressed feeback; removed globals (split out into D44201); clang-formatted

[ruiu]

I have a few questions because I don't know much about this wasm feature...

1. Let's say WeakFunc is a weak function symbol that is not defined at link time. Then if (WeakFunc) should be evaluated to false... but how does it actually be translated to wasm instructions? Is it compiled to a indirect call with function index 0?
2. I'm not 100% sure why we need to provide a dummy function for an unresolved weak undefined symbols. Is it for catching an error when a program accidentally calls an undefined weak symbol at runtime? Then, I wonder if we want a function that prints out a better error message (e.g. "unresolved weak function foo is invoked`"), instead of just killing itself with a UB instruction.

[sbc100]

In D44028#1030026, @ruiu wrote:

I have a few questions because I don't know much about this wasm feature...

1. Let's say WeakFunc is a weak function symbol that is not defined at link time. Then if (WeakFunc) should be evaluated to false... but how does it actually be translated to wasm instructions? Is it compiled to a indirect call with function index 0?

The address of a function is its table index in the indirection function call table. For weak undefined functions (or null functions) this will be zero. However the following call is *direct* call, not a call_indirect. And direct calls are more efficient we do want continue to use direct calls wherever we can.

2. I'm not 100% sure why we need to provide a dummy function for an unresolved weak undefined symbols. Is it for catching an error when a program accidentally calls an undefined weak symbol at runtime? Then, I wonder if we want a function that prints out a better error message (e.g. "unresolved weak function foo is invoked`"), instead of just killing itself with a UB instruction.

Yes, its for catching that specific case. In this case the linker needs insert some valid function index into the direct call instruction. It it doesn't insert a valid function index with the correct signature, the module will fail to validate (i.e. will fail to load). We could generate a better synthetic function with a nice error message. However, that would add complexity to the code generation, and I think we are already on shakey ground adding any kind of code generation to the linker. Also, simply crashing is what existing platforms do, so I think that can/should be expected. At least, I don't think we should block this change on making an nice error message, unless you want to push the code generation part into the compiler instead?

[sbc100]

wasm/Driver.cpp

328 ↗

(On Diff #137367)

I'm not sure this makes sense to be part of the symbol table itself. Can this be a local function here in Driver.cpp?

[ncw]

Good questions. So the call pattern we want to support is fairly common in libraries like libc - you have an optional function that's called only if the linker pulls it in.

For C code looking like this:

int foo() __attribute__((weak));

void callFooOrSkip() {
  if (&foo)
    foo();
}

On x86, you get code like this:

00000000 <callFooOrSkip>:
   0:   b8 00 00 00 00          mov    $0x0,%eax
                        1: R_386_32     foo
   5:   85 c0                   test   %eax,%eax
   7:   74 05                   je     e <callFooOrSkip+0xe>
   9:   e9 fc ff ff ff          jmp    a <callFooOrSkip+0xa>
                        a: R_386_PC32   foo
   e:   c3                      ret

There's a relocation for the function pointer, and a second one for the operand of the call. At link time, the linker can just put null in there for both values, or garbage - if the CPU ever were to take the "if" branch, or if the call to foo() were not guarded with an if, it wouldn't matter if process were to crash with SIGSEGV. The jmp doesn't need to legal - only if it's ever actually taken.

On Wasm, you get code like this:

block
  i32.const @R_WEBASSEMBLY_TABLE_INDEX(foo)  ; push function index to stack
  i32.eqz             ; pop value from stack, push bool to stack whether it's equal
  br_if               ; pop value from stack, break out of block if it's true
  call @R_WEBASSEMBLY_FUNC_INDEX(foo) ; call and push rv to stack
  drop           ; pop ignored rv from stack
end

Again there are two relocations. But here's the difference - you can't put null/zero as the operand to the call instruction. The Wasm validator is precisely designed to make it impossible to write code that fails with SIGSEGV! Regardless of whether the branch is ever taken, there has to be _something_ to go there. Hence the creation of the linker-synthetic functions. We don't expect the stubs to be called, they just have to exist to make the Wasm legal (and abort sensibly if they are somehow called).

[ruiu]

The address of a function is its table index in the indirection function call table. For weak undefined functions (or null functions) this will be zero. However the following call is *direct* call, not a call_indirect. And direct calls are more efficient we do want continue to use direct calls wherever we can.

I see. Thank you for the explanation!

Yes, its for catching that specific case. In this case the linker needs insert some valid function index into the direct call instruction. It it doesn't insert a valid function index with the correct signature, the module will fail to validate (i.e. will fail to load). We could generate a better synthetic function with a nice error message. However, that would add complexity to the code generation, and I think we are already on shakey ground adding any kind of code generation to the linker. Also, simply crashing is what existing platforms do, so I think that can/should be expected. At least, I don't think we should block this change on making an nice error message, unless you want to push the code generation part into the compiler instead?

It shouldn't block this change indeed. I was just trying to understand this patch.

I'm not too worried that we generate wasm instructions in the linker. Unlike other file formats, wasm supports and will support only one machine instruction -- that's the wasm instructions. So, if something is easy or natural to implement in a linker instead of a compiler, I think we shouldn't hesitate to do that.

wasm/MarkLive.cpp

78–85 ↗

(On Diff #137367)

Adding a special rule for a weak symbol seems a bit odd to me because they are orthogonal in concept. What if you create functions after you garbage-collect symbols? Then you can remove this logic, can't you?

wasm/SymbolTable.cpp

36 ↗

(On Diff #137367)

I believe in LLVM style global variables are written in the same way as local variables. So it is UnreachableFn.

41 ↗

(On Diff #137367)

This needs comment. Please describe the semantics of the weak undefined functions in wasm and what we are doing in this function.

42 ↗

(On Diff #137367)

I'm not too worried about the use of a hash table in this function because I believe the number of weak symbols in a program is small. But I'd like to reiterate that doing something like this (use a hash table for all symbols) is in general discouraged in lld as it makes the linker noticeably slow.

wasm/Symbols.h

65 ↗

(On Diff #137367)

You are not using this function.

126–128 ↗

(On Diff #137367)

I'd remove this function and inline it because it's too small and both hasTableIndex and getTableIndex is externally available.

[sbc100]

wasm/MarkLive.cpp

78–85 ↗

(On Diff #137367)

I also find this part of the change a little bit strange. And I think the hasNullTableIndex() method helps to describe what is going on here. However, inlineing hasNullTableIndex() along with a good comment is OK too.

[ncw]

Updated: addressed comments, clang-formatted

[ncw]

wasm/MarkLive.cpp

78–85 ↗

(On Diff #137367)

It's not a super-special rule: it's generic in the sense that it would apply to any symbol that had the (weird) property of needing to compare equal to the null pointer. It's not checking for weakness, it's checking something that's actually relevant to the relocation we're considering here. I agree it's not ideal, but I think it's OK (there's already a decent comment above).

[ruiu]

wasm/MarkLive.cpp

78–85 ↗

(On Diff #137367)

I'm little confused -- why do we need this in the first place? Even if a weak symbol is resolved to function table index zero, you can still call it, and if you call it, it should abort with UB, no?

[sbc100]

wasm/MarkLive.cpp

78–85 ↗

(On Diff #137367)

This is an GC optimization, for the case where such as function is address taken but never called, in that case we want to GC the dummy function (which is why we don't mark it live here). Normally one cannot determine that address taken functions are never called.. but in this case we can.

I you think it makes sense, I'd be OK with forgoing this optimization for the sake of clarity, since its hard to imagine a case where it would make a big difference to codesize.

[ruiu]

wasm/MarkLive.cpp

78–85 ↗

(On Diff #137367)

If a program takes an address of a function, that function might be called somewhere using a indirect call instruction, so I don't think that we cannot really guarantee that the function we are trying to eliminate here isn't called at runtime.

Or, in wasm, can you guarantee that?

[sbc100]

wasm/MarkLive.cpp

78–85 ↗

(On Diff #137367)

Indeed, that is the (perhaps too) clever trick here. For these functions we know that their address is 0 (table index that is)... we don't need to include the stub for indirect calls, since indirect calls to 0 are handled separably. The stub function is *only* for the direct calls which have different relocation type.

[ruiu]

wasm/MarkLive.cpp

78–85 ↗

(On Diff #137367)

since indirect calls to 0 are handled separably

... by the runtime? If so, this code makes sense to me. Can you describe that in the comment explicitly? I'd say something like...

A weak function is resolved to function table index 0 with a stub function body that aborts with undefined instruction exception. We need a stub function as a indirect branch target, but we don't need it for function table index 0, since the runtime handles it as an invalid function for us. So, if all references to a stub function goes through the index 0, we can eliminate that function. Thus we don't exclude that case here.

[ncw]

wasm/MarkLive.cpp

78–85 ↗

(On Diff #137367)

I'll expand the comment along those lines, thanks.

Is it "approved" with a better comment? (Not that I can commit until D44150 is merged...)

[ruiu]

Yes. LGTM. Thanks!

[ncw]

I hope this is OK, but when I committed I made one additional change, that I think makes sense.

Rather than being stingy and emitting one stub per type, I'm now emitting one per function - the stubs are very small, and the advantage is that you'll now get a nice stack trace if these things ever should be called (since they can be named sensibly, to indicate which function was missing).

[ruiu]

wasm/Symbols.h

315 ↗

(On Diff #137773)

Please revert this change. toString() is supposed to be a stringize function for an object, so it should print out only the information of object itself, and no information should be included other than that. Passing a second argument for "supplemental" purpose break that principle.

test/wasm/undefined-weak-call.test

+# RUN: yaml2obj %s > %t.o
+# RUN: not lld -flavor wasm --no-entry %t.o -o %t.wasm 2>&1 | FileCheck %s
+
+# Check linking fails when the input file contains weak symbols, and relocations
+# which reference those symbols and cannot be resolved.
+
+# CHECK: Cannot generate relocation against undefined function: weakFunc
+
+--- !WASM
+FileHeader:
+  Version:         0x00000001
+Sections:
+  - Type:            TYPE
+    Signatures:
+      - Index:           0
+        ReturnType:      NORESULT
+        ParamTypes:
+  - Type:            IMPORT
+    Imports:
+      - Module:          env
+        Field:           weakFunc
+        Kind:            FUNCTION
+        SigIndex:        0
+  - Type:            FUNCTION
+    FunctionTypes:   [ 0 ]
+  - Type:            CODE
+    Relocations:
+      - Type:            R_WEBASSEMBLY_FUNCTION_INDEX_LEB
+        Index:           0
+        Offset:          0x00000004
+    Functions:
+      - Index:           1
+        Locals:
+        Body:            1080808080000F0B
+  - Type:            CUSTOM
+    Name:            linking
+    SymbolTable:
+      - Index:           0
+        Kind:            FUNCTION
+        Name:            weakFunc
+        Flags:           [ UNDEFINED, BINDING_WEAK ]
+        Function:        0
+      - Index:           1
+        Kind:            FUNCTION
+        Name:            callWeakFunc
+        Flags:           [  ]
+        Function:        1

test/wasm/undefined-weak-getglobal.test

+# RUN: yaml2obj %s > %t.o
+# RUN: not lld -flavor wasm --no-entry %t.o -o %t.wasm 2>&1 | FileCheck %s
+
+# Check linking fails when the input file contains weak symbols, and relocations
+# which reference those symbols and cannot be resolved.
+
+# CHECK: Cannot generate relocation against undefined global: weakGlobal
+
+--- !WASM
+FileHeader:
+  Version:         0x00000001
+Sections:
+  - Type:            TYPE
+    Signatures:
+      - Index:           0
+        ReturnType:      NORESULT
+        ParamTypes:
+  - Type:            IMPORT
+    Imports:
+      - Module:          env
+        Field:           weakGlobal
+        Kind:            GLOBAL
+        GlobalType:      I32
+        GlobalMutable:   true
+  - Type:            FUNCTION
+    FunctionTypes:   [ 0 ]
+  - Type:            CODE
+    Relocations:
+      - Type:            R_WEBASSEMBLY_GLOBAL_INDEX_LEB
+        Index:           0
+        Offset:          0x00000004
+    Functions:
+      - Index:           0
+        Locals:
+        Body:            2380808080001A0F0B
+  - Type:            CUSTOM
+    Name:            linking
+    SymbolTable:
+      - Index:           0
+        Kind:            GLOBAL
+        Name:            weakGlobal
+        Flags:           [ UNDEFINED, BINDING_WEAK ]
+        Global:          0
+      - Index:           1
+        Kind:            FUNCTION
+        Name:            getWeakGlobal
+        Flags:           [  ]
+        Function:        0

wasm/InputFiles.cpp

uint32_t ObjFile::calcNewValue(const WasmRelocation &Reloc) const {
   case R_WEBASSEMBLY_MEMORY_ADDR_SLEB:
   case R_WEBASSEMBLY_MEMORY_ADDR_I32:
   case R_WEBASSEMBLY_MEMORY_ADDR_LEB:
     if (auto *Sym = dyn_cast<DefinedData>(getDataSymbol(Reloc.Index)))
       return Sym->getVirtualAddress() + Reloc.Addend;
     return Reloc.Addend;
   case R_WEBASSEMBLY_TYPE_INDEX_LEB:
     return TypeMap[Reloc.Index];
-  case R_WEBASSEMBLY_FUNCTION_INDEX_LEB:
-    return getFunctionSymbol(Reloc.Index)->getOutputIndex();
-  case R_WEBASSEMBLY_GLOBAL_INDEX_LEB:
-    return getGlobalSymbol(Reloc.Index)->getOutputIndex();
+  case R_WEBASSEMBLY_FUNCTION_INDEX_LEB: {
+    Symbol *Sym = getFunctionSymbol(Reloc.Index);
+    if (!Sym->hasOutputIndex()) {
+      // This happens if someone tries to use a `call` instruction to invoke a
+      // weak undefined function: if it's not found in the final link, then we
+      // must fail because there's nothing for the `call` to target.
+      fatal("Cannot generate relocation against undefined function: " +
+            toString(*Sym));
+    }
+    return Sym->getOutputIndex();
+  }
+  case R_WEBASSEMBLY_GLOBAL_INDEX_LEB: {
+    Symbol *Sym = getGlobalSymbol(Reloc.Index);
+    if (!Sym->hasOutputIndex()) {
+      // This happens if someone tries to use a `get/set_global` instruction to
+      // use a weak undefined global: if it's not found in the final link, then
+      // we must fail because there's nothing for the instruction to target.
+      fatal("Cannot generate relocation against undefined global: " +
+            toString(*Sym));
+    }
+    return Sym->getOutputIndex();
+  }
   default:
     llvm_unreachable("unknown relocation type");
   }
 }
 
 void ObjFile::parse() {
   // Parse a memory buffer as a wasm file.
   DEBUG(dbgs() << "Parsing object: " << toString(this) << "\n");