Page MenuHomePhabricator

[WebAssembly] Handle weak undefined functions with a synthetic stub
ClosedPublic

Authored by ncw on Mar 2 2018, 9:58 AM.

Diff Detail

Repository
rLLD LLVM Linker

Event Timeline

ncw created this revision.Mar 2 2018, 9:58 AM
sbc100 added inline comments.Mar 2 2018, 10:02 AM
wasm/InputFiles.cpp
88

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 added inline comments.Mar 2 2018, 10:03 AM
wasm/InputFiles.cpp
94

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

ncw added inline comments.Mar 2 2018, 10:14 AM
wasm/InputFiles.cpp
88

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.

94

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 added inline comments.Mar 2 2018, 10:21 AM
wasm/InputFiles.cpp
94

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 added a comment.Mar 5 2018, 4:37 AM

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

sbc100 added a comment.Mar 5 2018, 8:30 AM

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 planned changes to this revision.Mar 6 2018, 1:17 AM

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 updated this revision to Diff 137183.Mar 6 2018, 6:18 AM
ncw retitled this revision from [WebAssembly] Add message for relocation against weak undefined symbol to [WebAssembly] Handle weak undefined globals and functions.
ncw edited the summary of this revision. (Show Details)

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.

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
89

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
7 ↗(On Diff #137183)

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

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 added inline comments.Mar 6 2018, 12:58 PM
test/wasm/undefined-weak-call.test
1 ↗(On Diff #136783)

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

2 ↗(On Diff #136783)

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

ncw marked 2 inline comments as done.Mar 6 2018, 2:46 PM
ncw added inline comments.
test/wasm/undefined-weak-call.ll
89

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 ↗(On Diff #136783)

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
7 ↗(On Diff #137183)

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

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 added inline comments.Mar 6 2018, 3:04 PM
wasm/MarkLive.cpp
84

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 this revision to Diff 137367.Mar 7 2018, 5:28 AM

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

ncw marked 5 inline comments as done.Mar 7 2018, 5:29 AM
ncw retitled this revision from [WebAssembly] Handle weak undefined globals and functions to [WebAssembly] Handle weak undefined functions with a synthetic stub.Mar 7 2018, 5:36 AM
ncw edited the summary of this revision. (Show Details)
ruiu added a comment.Mar 7 2018, 8:46 AM

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 added a comment.Mar 7 2018, 9:56 AM

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.

  1. 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 added inline comments.Mar 7 2018, 10:04 AM
wasm/Driver.cpp
369

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 added a comment.Mar 7 2018, 10:13 AM

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 added a comment.Mar 7 2018, 10:14 AM

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

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

You are not using this function.

125–127

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

sbc100 added inline comments.Mar 7 2018, 10:52 AM
wasm/MarkLive.cpp
78–85

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 this revision to Diff 137434.Mar 7 2018, 10:54 AM

Updated: addressed comments, clang-formatted

ncw marked 4 inline comments as done.Mar 7 2018, 10:56 AM
ncw added inline comments.
wasm/MarkLive.cpp
78–85

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 added inline comments.Mar 7 2018, 11:03 AM
wasm/MarkLive.cpp
78–85

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 added inline comments.Mar 7 2018, 11:08 AM
wasm/MarkLive.cpp
78–85

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 added inline comments.Mar 7 2018, 11:14 AM
wasm/MarkLive.cpp
78–85

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 added inline comments.Mar 7 2018, 11:19 AM
wasm/MarkLive.cpp
78–85

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 added inline comments.Mar 7 2018, 11:26 AM
wasm/MarkLive.cpp
78–85

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 added inline comments.Mar 7 2018, 1:17 PM
wasm/MarkLive.cpp
78–85

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 accepted this revision.Mar 7 2018, 1:22 PM

Yes. LGTM. Thanks!

This revision is now accepted and ready to land.Mar 7 2018, 1:22 PM
This revision was automatically updated to reflect the committed changes.
ncw added a comment.Mar 9 2018, 9:13 AM

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 added inline comments.Mar 9 2018, 12:44 PM
wasm/Symbols.h
315

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.