Page MenuHomePhabricator

[WebAssembly] Add support for table linking to wasm-ld

Authored by wingo on Nov 20 2020, 8:02 AM.



This patch adds support to wasm-ld for linking multiple table references together, in a manner similar to wasm globals. The indirect function table is synthesized as needed.

To manage the transitional period in which the compiler doesn't yet produce TABLE_NUMBER relocations and doesn't residualize table symbols, the linker will detect object files which have table imports or definitions, but no table symbols. In that case it will synthesize symbols for the defined and imported tables.

As a change, relocatable objects are now written with table symbols, which can cause symbol renumbering in some of the tests. If no object file requires an indirect function table, none will be written to the file. Note that for legacy ObjFile inputs, this test is conservative: as we don't have relocs for each use of the indirecy function table, we just assume that any incoming indirect function table should be propagated to the output.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
sbc100 added inline comments.Dec 1 2020, 12:04 PM

We use a slightly different naming convention in lld.

I think the plan is to transition all of llvm eventually to this style and we are trying it out. So locals and parameters start with lowercase, but are otherwise camelcase.


Could we make this separate function just to split it up?

How about:

if (!haveTableSymbol)

The other globally-known symbols are kept in Symbols.h:WasmSym .. seems like maybe this should go there too?


Why this new include?


This looks unused.


This last seems a little out of place since its not assigning indexes. Would this make more sense alongside wherever out.elemSec is populated once we know its complete?

sbc100 added inline comments.Dec 1 2020, 12:13 PM

How is (2) handled after this change?

Imagine a program that contains just this code:

 void call_func(func_ptr f) {

Now we a call_indirect instruction but no TABLE_INDEX relocations.

In fact we have no relocations at all, but the resulting program needs to have a table in order to validate.

I guess once you move to new relocation model to call_indirect this program *will* have a TABLE_NUMBER relocation. But we need to support the case where this code was compiled with the old model too.

The change to lld/test/wasm/stack-pointer.ll looks a little suspicious because it removes the table from the object file which would potentially make it fail to validate.

wingo added inline comments.Dec 2 2020, 8:01 AM

Humm this is a head-scratcher! I think may have introduced a bad state.

Backing up -- The intention with the change here is that any object file that needs an indirect function table should either

  • have a TABLE_NUMBER reloc against the table ("new" object file with call_indirect)
  • have the table marked as no-strip ("new" object file, caused by assembler recording a TABLE_INDEX reloc)
  • or, if the incoming object file is "old" (has table import or definition but no table symbols), then those tables are treated as having no-strip symbols.

For new files, this works fine. For very old files, also fine -- they always have an __indirect_function_table import. But since, there can be object files which refer to __indirect_function_table via call_indirect, but which don't have TABLE_INDEX relocs. In that case the object file will lack the __indirect_function_table import.

The problem is mitigated in that if any other linker input imports __indirect_function_table, then the result is an output file that validates.

wingo marked 4 inline comments as done.Dec 8 2020, 1:54 AM

New patch addresses micro-feedback, but still thinking if a patch split is possible. Probably also want to land a precursor also to ensure that the compiler produces __indirect_function_table imports for object files with call_indirect but no TABLE_INDEX relocs.


We can't fit a WasmTableType in a TableSymbol without growing the symbol size, so instead TableSymbol has a WasmTableType*, with the precondition that the symbol's lifespan is a subset of the WasmTableType's lifespan.

But in TableSymbol::setLimits, we can't just fiddle the limits in place, because they are embedded in a WasmTableType that doesn't belong to the symbol; we need to allocate a fresh table type in the arena. So Memory.h allow us to allocate a new WasmTableType using make<>.

Did I get the memory management right? Feedback very welcome.


Sure. I tried initially putting it in TableSection::finalizeContents but of course this symbol might be imported, so I instead arranged to call it just after populating elemSec.

wingo updated this revision to Diff 310112.Dec 8 2020, 1:54 AM
wingo marked an inline comment as done.

Address feedback

wingo edited the summary of this revision. (Show Details)Dec 8 2020, 1:59 AM
wingo marked an inline comment as done.Dec 8 2020, 6:10 AM

Maybe there are two logical parts we can separate here:

  1. Support for first class tables in input files
  1. Support for the special __indirect_function_table

I guess they are somewhat intertwined by I can imagine landing (1) without changing the way we handle the special table 0. Maybe its not worth the work to split up?

For what it is worth, this was the first tack that I took, but I couldn't find a useful intermediate point where we still had consistent files. Simple things like whether __indirect_function_table is imported, exported, or neither end up propagating into special cases all over the place -- at least that was my conclusion at the time and I think it might still hold. It seemed cleaner to me to make something more conventional using symbols and relocs like everything else in the linker, and then adapt the current input files to that newer more conventional machinery. Dunno. WDYT?

wingo planned changes to this revision.Tue, Jan 5, 3:14 AM

Will split this one.

wingo updated this revision to Diff 314554.Tue, Jan 5, 3:15 AM

Split from D94075

wingo updated this revision to Diff 316598.Thu, Jan 14, 2:23 AM

Rebase to include synthetic tables

wingo added a comment.Thu, Jan 14, 4:50 AM

I think this one is ready for review @sbc100, when you have a moment :)

Nice. I like that we were able to delete almost as much code as was added here.

Just a few more comments but mostly lgtm.


provide seems like a slightly odd verb. (Or is it just me?) How about calling this createIndirectFunctionTable or defineIndirectFunctionTable?

Or maybe creatDefinedIndirectFunctionTable to match the function below?


I don't think it ever make sense to pass StringRef by reference does it?


I guess this is existing behaviour. However I wonder if it would be better (in the future) to have --import-table and --export-table only effect the table if exists?


Can you just use functionTableName directly below rather than adding this local?


Could you add a comment about the purpose of this function either in the header or here. IIUC this can be removed if ever drop support for older objects files, is that right?




In other places we use saver which is StringSaver defined in lld/include/lld/Common/Memory.h


Ah.. I see you added a comment here rather than in the definition. Seems reasonable.


IIUC this is only need to support legacy object files? Perhaps add a TODO or a note here that to that effect?


Can/should we call this after scanRelocations in the caller?

There are many other things that need to happen only after relocations are scanned. I don't see why this one should inlined, unless I'm missing something?

wingo updated this revision to Diff 316666.Thu, Jan 14, 8:05 AM
wingo marked 9 inline comments as done.

Address feedback


Good point :)


Good question. Is it reasonable to make the rest of the toolchain inspect the output module to see if it actually needed a table? My initial thought was "well they asked for it, let's give them what they expect" but perhaps this is not the right thing.


Good point! And yes it could be dropped in some future.


What does this mean? :)


Good tip, thanks. Though, I think the comment was actually erroneous; shouldn't the name be just (e.g.) "__indirect_function_table" ?


The updated patch includes a comment both places; lmk if i should remove one / change something / etc.


I think not, actually -- before, there was some custom logic to reify an __indirect_function_table as part of the writer. Now, for all files, if an indirect function table definition is needed, it will be made with respect to a synthesized InputTable. So this vector will only ever have 1 or 0 elements.


Sure, no prob.

sbc100 accepted this revision.Thu, Jan 14, 8:10 AM
This revision is now accepted and ready to land.Thu, Jan 14, 8:10 AM

Would you mind formatting the commit message to wrap at 80 chars? I know llvm commits are bit all over the place on the style used but I find wrapped commit message easier to read myself.

Thanks for the review!

Would you mind formatting the commit message to wrap at 80 chars? I know llvm commits are bit all over the place on the style used but I find wrapped commit message easier to read myself.

Yeah no problem -- actually the local commit message is wrapped, I just unwrapped it for phab. Incidentally I find it weird that we can land patches from local commits where the message doesn't have to correspond with what was in phab!

This revision was automatically updated to reflect the committed changes.

This seems to have a bug that we discovered on the emscripten builders where it's exporting the table twice.
The output (from wasm-objdump):

 - memory[0] -> "memory"
 - table[0] -> "__indirect_function_table"
 - func[3] <__wasm_call_ctors> -> "__wasm_call_ctors"
 - func[5] <main> -> "main"
 - table[0] -> "__indirect_function_table"
 - func[6] <stackSave> -> "stackSave"
 - func[7] <stackRestore> -> "stackRestore"
 - func[8] <stackAlloc> -> "stackAlloc"
 - func[9] <emscripten_stack_init> -> "emscripten_stack_init"
 - func[10] <emscripten_stack_get_free> -> "emscripten_stack_get_free"
 - func[11] <emscripten_stack_get_end> -> "emscripten_stack_get_end"
 - func[12] <saveSetjmp> -> "saveSetjmp"
 - func[13] <testSetjmp> -> "testSetjmp"
 - func[14] <setThrew> -> "setThrew"

I'll see if I can find a more useful reproducer

it's funny, since this CL doesn't really modify the export behavior.
I'm going to go ahead and revert it though ("revert first and ask questions later" being the usual LLVM practice), until we can figure out what's happening.

Thanks for the sherriffing, I'll get on it :)

wingo reopened this revision.Mon, Jan 18, 1:34 AM

Reopening, as that will let the diff to the previously landed patch be legible; lmk if you prefer a new rev.

This revision is now accepted and ready to land.Mon, Jan 18, 1:34 AM
wingo updated this revision to Diff 317287.Mon, Jan 18, 1:55 AM

Fix double-export of __indirect_function_table

wingo requested review of this revision.Mon, Jan 18, 1:58 AM

PTAL @sbc100 -- the problem was that I had neglected to remove some special logic regarding export of the indirect function table. Instead it's now handled in the usual way, as a flag on the symbol.

Added a test that succeeds either way with the current patch, but which starts failing once MC writes table symbols in with the older version of this patch.

Tested llvm-lit on MC, CodeGen, and LLD with this change with the whole patch series, and all pass.

sbc100 accepted this revision.Mon, Jan 18, 7:02 AM

Thanks andy! Still lgtm.

I think re-using the same review makes sense (although I don't know the conventions/rules are around that).

1 ↗(On Diff #317287)

Can we come up with a better name for this new test? I don't have any great idea but just calling it "-test-2" doesn't seem useful.

How about export-table-explicit.test? Since this test includes and explicit declaration of the __indirect_function_table?

This revision is now accepted and ready to land.Mon, Jan 18, 7:02 AM
wingo updated this revision to Diff 317352.Mon, Jan 18, 7:20 AM

Rename new test to export-table-explicit.test

wingo marked an inline comment as done.Mon, Jan 18, 7:21 AM
wingo added inline comments.
1 ↗(On Diff #317287)

Good idea; done :)

This revision was automatically updated to reflect the committed changes.
wingo marked an inline comment as done.