Differential D90948
[WebAssembly] call_indirect issues table number relocs Authored by wingo on Nov 6 2020, 7:50 AM.
Details If the reference-types feature is enabled, call_indirect will explicitly Also, as before, address-taken functions can also cause the function
Diff Detail
Unit Tests Event TimelineThere are a very large number of changes, so older changes are hidden. Show Older Changes
Comment Actions I don't have a really representative corpus, but if you consider the old epic zen garden demo, only 6.8% of call sites are call_indirect. Tested via wasm-objdump -d $file | grep -c call_indirect and dividing that by grep -c call.
Right now with the MVP, there will only ever be at most one table, so it will always get allocated to 0 -- no problem. If we ever have a use case for multiple function tables synthesized by the linker, perhaps for CFI reasons, perhaps we'd need another kind of reloc -- i.e. TABLE_INDEX, but with respect to a specific indirect function table. I agree with your assessment of pros and cons of always emitting TABLE_NUMBER relocs btw. Comment Actions Current status: CodeGen and MC tests working. Need to think about ways to get the getOrCreateWasmFunctionTableSymbol stuff out of MCContext if possible. Need to address any tests outside of CodeGen and MC. Might need to split ImportName change for globals into separate patch. Comment Actions OMG I am such an idiot. So the call_indirect instructions had a "flags" argument. I never investigated what this was, assuming it was just some weird thing that LLVM was threading around; I just preserved it. Turns out it was just always zero -- as the table number reference was in the MVP. I.e. the flags field became the table number field. Will fix.
Comment Actions Rebase; still a WIP. In https://reviews.llvm.org/D91637, we refrained from actually writing Comment Actions Okeydoke, finally ready for review. Probably needs more tests for multi-table linking. Probably should follow up to remove the "legacy" handling of __indirect_function_table in the linker. Or should wasm-ld support old object files for a while? Comment Actions We should avoid dropping support for older object files. If we even do that we should bump the object file version so that llvm can show a clear message when passed an old object file. However, if we can avoid that completely than I think we should. Comment Actions Well, this patch was a bit of a journey! But finally it's ready, having calved off a number of precursor patches that landed already. Notably we needed to fix wasm-ld to be able to understand table symbols, before emitting them here. So in this patch, we add a "table" operand to call_indirect, causing call_indirect instructions to emit TABLE_NUMBER relocs. We add support for this operand in the asm parser; if the table is not given, it defaults to __indirect_function_table as usual. Likewise, lowering in codegen synthesizes a reference to the __indirect_function_table when making call_indirect MC instructions. The end result is that MC and CodeGen tests end up making more relocs, the call_indirect instructions have 5-byte LEBs for the table number, and there are symbols in the output for tables. Comment Actions Great!
Comment Actions Thanks, will land tomorrow if no emscripten build problems.
Comment Actions Update to use feature detection to know when to emit symbolic reference or not almost ready, will upload tomorrow first thing. Comment Actions OK this was unexpectedly gnarly as we had to undo a number of tests. The interdiff between the two latest revisions shows what changed relative to the previously reviewed patch. I was surprised how hard it was to get the current subtarget feature set from the places where I needed it. Since the subtarget features can change during the compilation unit apparently, I used the "used-in-reloc" flag on the symbol to indicate whether a table should be included in the symbol table or not. This works -- except in the case of function pointers, where they get emitted not as part of an instruction but rather during lowering, and the fragment has no STI. Baffling. Is there a better way? Tested MC, CodeGen, and lld wasm tests, and all passing with this fixup, having also reapplied https://reviews.llvm.org/D92215.
Comment Actions I'm beginning to (re-)wonder if we should leave the current "call_indirect" as special in that it always implicitly refers the magic table zero.. then we would introduce a new instruction for call_indirect_explict that could be used if and only if reference types is enabled and would have the relocation. Data and function addresses will always be special in llvm so I think its OK to reflect that if it makes things simpler. I guess it would make things simpler in some ways and more complex in other? (Sorry if I'm re-litigating prior decisions here). Comment Actions Thanks for your thoughtful answers, @wingo! I like the idea of treating table zero as a magical table that is assumed to always exist and that all "normal" function pointers and indirect calls implicitly refer to, even when reference-types is enabled. That's how the table used to work, right? This would solve the problem of making sure the table is live when there are call_indirects or function pointers present in an object -- table 0 would always be live. Then table symbols would only be used for additional user-defined tables from @pmatos's work, so they would only be used at all when reference-types is enabled. I don't think we even need a new kind of call_indirect instruction for this, since we will be able to differentiate "normal" indirect calls to table zero from other indirect calls by the address space of the called function pointer. Comment Actions I am having a hard time seeing what a new instruction would buy us. I would think there is already a sufficiently clear difference between call_indirect with an immediate table operand -- which was the case before I started, and is still the case now if reference-types is disabled -- and call_indirect with a symbol reference. There would only need to be a relocation in the latter case. I think this goes against what was already done in D91637 and D92840. If individual object files can signal their use of the indirect function table via the presence or absence of the __indirect_function_table import, the linker can then only include it in the final linking stage when needed -- a minor win. I can see the point in treating __indirect_function_table as a good default, and which in the absence of reference-types will be table number 0, but reserving table 0 only complicates things when reference types *are* enabled -- because then you have two kinds of tables. Comment Actions Just to be clear -- here is my use case. https://github.com/Igalia/ref-cpp/blob/master/milestones/m3/test.S#L76 WAT version here: https://github.com/Igalia/ref-cpp/blob/master/milestones/m3/test.wat#L47 Basically I am implementing a side table mapping externref to index, in webassembly instead of in JS. I want to have named table symbols so I can have different mappings, and to be able to table.get / table.set / etc on them, but to do this I need to solve the table linking problem. But to solve table linking I had to fix call_indirect. That's why I'm here. I can see how address spaces may relate to this on an IR level, but on the MC level (where I am right now) I think I can probably ignore it. Comment Actions I agree that we just need a single call_indirect that can take either a constant zero table operand or a symbolic table operand. Both types of operands need to be able to coexist in the same link or even in the same object file to make MVP object files linkable with reference-types object files. I suggest that codegen only produce symbolic table operands to refer to user-defined funcref tables, not the default MVP indirect call table (table 0) because that will give us the nice property that objects will contain new table symbols and relocations only if they use reference-types features, not just if they enable reference-types features. This property should also remove the need to do any form of feature detection in the WasmObjectWriter.
Yes, I agree that it's better not to emit the table at all if it's not needed. I'm not totally clear on whether those patches to emit the table only when necessary are ABI-breaking changes, though. Do I understand correctly that they are not ABI-breaking because wasm-ld previously ignored the presence of the table import and that those patches signal whether the table is used by the presence of the import in the object file and not via new symbol or relocation types? If so, I agree that table 0 (i.e. '__indirect_function_table') should be live only if necessary. I think the crux of the matter is whether there should be two kinds of tables, though. AFAICT, wasm-ld needs to support two kinds of tables (hard-coded 0 and symbolic) if we want to keep supporting the MVP object ABI. Since we need to support both types of tables anyway, it seems simpler to let usage rather than enabled features determine when each kind of table is used. Normal function pointers and indirect calls to function pointers should use the hard-coded table 0, just as they do in MVP object files and all indirect calls into user-defined funcref tables should use symbolic tables. This scheme prevents the MC layer from having to do any feature detection and maintains compatibility with the MVP ABI. I'm very excited for this all to come together :) You're right that address spaces won't show up in the MC layer at all. I mentioned them only to point out that the choice of whether to use a hard-coded table 0 or a symbolic table operand for call_indirect can be done in codegen rather than in the MC layer. Comment Actions Thanks for the comments, tlively :) Whoa -- is linking MVP object files with reference-types object files a requirement? This was totally not on my radar. Note that with feature flags, we can prohibit linking between MVP and reftypes object files.
This is correct, yes. Old object files always have an __indirect_function_table import, and the old linker always produces __indirect_function_table. Newer object files may omit __indirect_function_table if it is not needed, and newer linkers may omit __indirect_function_table in the output if no imput file requires it. It is always safe (but can be suboptimal) to emit an indirect function table, so old linkers can work with new object files. New linkers can also work with old object files, because the __indirect_function_table import is always present, so the table will not be omitted. So no ABI break AFAIU. Comment Actions
Yes, I expect we will receive bug reports from confused users if we don't allow linking MVP and reftypes object files together. Consider a library author who has no use for reference types and wants their library to run on as many engines as possible, including those that may not support reference types. That library author might distribute just a single build of their library that does not have the reference-types feature enabled. An application author who does use reference types should still be able to link against that library without requiring a separate build. Although you're right that we could just make that an error, that would inconvenience the library author who now has to distribute two builds of their library, even though the builds do not differ in the features they use.
Thanks for confirming! Comment Actions Thanks again for comments! I would like to preserve the property that allows the linker to omit __indirect_function_table if it is not needed. Right now the linker has two ways it treats incoming files: if the input has table symtab entries, the input is assumed to have symbols for all tables and relocs for all table references. Otherwise, if the input has tables (import or not) but no symbols, it is an MVP input which requires an indirect function table. It would be sufficient to link the two if we ensure that the indirect function table is allocated table number 0. Is the suggestion that for reftypes objects, we would omit the symbol for __indirect_function_table, and omit relocations against it? It would mean that the linker would have to grovel reftypes inputs for table imports that aren't in the symtab, in order to know if a reftypes object uses the indirect function table. This is doable but it is less optimal: since the linker doesn't have a precise idea of where the indirect function table is used, it has to assume that if it's live in the input, it's live in the output. If each table reference has a reloc, this isn't the case, and we can have more precise GC. But given the tradeoffs, do you prefer that solution? Comment Actions When you say "the linker would have to grovel reftypes inputs for table imports that aren't in the symtab" are you referring to the way things work today with MVP object files? I can't remember exactly how the mechanism works but we currently have to imply the existence of the table based on TABLE_INDEX relocations right? Sorry I've not been following all the comments here. Are you saying you want to improve on the status quo (make this more precise), or are you concerned about a regression (i.e. becoming less precise about the GC of the table in the final output). Comment Actions I'm also not 100% sure of how things work today, but I hope it wouldn't be too difficult to emit the MVP table precisely when necessary by seeing whether or not it would be empty immediately before writing out the final binary. I'm perfectly willing to believe that I'm missing something that prevents that from working, though. Comment Actions Unfortunately this is not the case. You can still have void call(void (*f)(void)) {
f();
}in the compilation unit, causing call_indirect to be emitted but no function pointer definition. Comment Actions I meant that the linker should choose whether to emit the table into the final binary by checking whether it would be empty or not. So in this example, whether or not this compilation unit had a table in its object file, the linker would see that some function has its address taken (in the caller of call) and needs to be allocated a table slot. Since the table wouldn't be empty, the linker emits the table in the final binary. Comment Actions Yes. I thought it would be a stopgap mechanism but this would make it be more permanent, happening both for reftypes and non-reftypes binaries.
No, the linker can be a bit more dumb than that -- it implies the existence of a table based on whether an input needs it. MVP inputs declare that they need a table by having a table import. An input needs the function table if it has an indirect call or a function pointer (bitcast). The latter case coresponds to TABLE_INDEX relocs, but the former has no relocs in MVP inputs.
AFAIU Thomas was initially suggesting always reserving table 0 -- always having a table import in input object files, the linker always includes a table in the output. Then no symbols or relocations are needed to refer to the indirect function table; it's just assumed that the linker will assign it table number 0. I was saying that as long as inputs signal their need for a table, the linker shouldn't have to write a table output. The linker would just have to assign table number 0 to __indirect_function_table, if it is there; otherwise table 0 could be assigned to no table at all, if there are no tables, or some other table, for reftypes inputs that declare other tables. If this works for you all I can hack this up. Will be Monday though as I have a day of meetings today. Comment Actions This doesn't work. You can have a file with call_indirect but no declared function pointers. In that case the final binary will not validate. Comment Actions Ah yes I remember what that doesn't work. Because you can have this code: a.o void call(void (*f)(void)) {
if (f) {
f();
}
}b.o: void foo() {
call(NULL);
}Now you have a program that contains call_indirect but no function pointers. Its kind of annoying that the wasm standard makes this invalid but that is the current state. I think I have bought this up before in the standards discussions but perhaps we could re-litigate? WTYT tlively, would this make sense as a spec change? Comment Actions Ah tricky. I understand why we can't just look at whether the table would have any non-null contents now. Thanks for explanations!
Yes, this sounds good, although you're right that purely using the imports is not as precise as using relocations because they don't allow the linker to GC unnecessary tables. What do you think about this scheme:
This scheme has the following valuable properties:
I know this has somewhat come full circle and this scheme is close to what you've already implemented. Thanks for bearing with me as I've wrapped my head around all the issues! Comment Actions
Any reason this has to happen right away? why not leave normal call_indirect to the default table alone for now (so reftypes object and MVP objects are the same in this regard for now)? We can always change our mind later and add this if we want to increase the GC precision (this can be done as a followup or not at all). Comment Actions Leaving that part as a follow-on sounds fine to me. No need to stabilize the reference-types object ABI any time soon. My impression is that the table symbols and relocations are mostly implemented already, though, so if @wingo's interested in getting that part working, I don't see a reason to delay. Comment Actions Hi :) Just for clarity, this differs from where I was initially going in two ways:
So I will first add the logic to the linker that it will assign table number 0 to __indirect_function_table, if it is present.
Agreed.
It's "fullish" precision. TABLE_INDEX relocations for function pointer bitcasts don't explicitly reference the table, so instead they setNoStrip on the indirect function table. There can be cases where the linker omits the function pointer, causing the function table to no longer be necessary, but the linker can't know that.
Yes, for call_indirect. But when we emit a function pointer at the MC layer -- either in data or in code -- we need that to cause the function table to be present. For function pointers in code, i think we can find the feature set just fine, so that for reftypes we cause a symtab entry to be emitted for the function table. But for function pointers in data I don't know a good way to do feature detection; do you have any ideas here? Thanks for your patience with this small but gnarly problem! Comment Actions Gentle ping regarding this point -- this is why I was mucking with features in the writer. I plan on having another look in lowering but if you have other ideas they are welcome. Comment Actions OK one nit I just realized. It would be nice to allow linking MVP and reftypes inputs. However this will not be possible if the reftypes input imports a table. This is because table numbers are assigned first to imports, then to module-local definitions. The MVP input would have call_indirect against table 0, expecting it to be the indirect function table, but instead it is an import from the reftypes module. I guess the linker just emits an error in that case. It would be possible to have a command-line tool to migrate an MVP object file to a reftypes object file, parsing function code and reconstructing relocs. I guess the linker itself isn't the right place for that though. Comment Actions Yup that does sounds like a showstopper for linking mixed inputs. Should we have the linker error out in only cases were there are imported tables? Or should error out on any kind of mixed inputs? I guess it depends how useful linking mixed object files is, and how often folks will be using table imports. I think maybe we should start out by making mixed inputs a hard error. We could try to relax it later if there is demand. Does that sounds reasonable @tlively ? Comment Actions Would it be possible to do this feature detection and addition of a table in WebAssemblyAsmPrinter.cpp, which is the transition from the MachineInstr layer to the MC layer? This is the last point where the original LLVM Module is still available, so in the worst case you could traverse the Module's global data to find function pointers. Comment Actions I would prefer to error out only when a reftypes object imports a table. This seems similar to what we do when linking MVP and atomics-enabled objects, i.e. allow the link when we know it to be safe and possible. That's certainly been useful in practice, so I expect that allowing MVP+reftypes links will be useful as well as reftypes picks up adoption. Being permissive and having good error messages from the start will save us a lot of support emails and Emscripten issues down the line :) Of course this relaxation doesn't have to be in the initial patch, but I don't think we should wait to implement it until users complain. Comment Actions Thanks for patience with the delay here. Paging this back in -- I will move the logic from MC/WasmObjectWriter.cpp to WebAssemblyAsmPrinter.cpp -- there I will iterate over all functions in the module, and if any of them hasAddressTaken, then I will ensure an __indirect_function_table definition exists and will be written to the output (setNoStrip). We keep the hack that table symbols only go to the symbol table if they are marked as used in relocations. If the reference types feature is enabled and an address-taken function is present in the module, the indirect function table will be explicitly marked isUsedInReloc. Just broadcasting intention here so that there are no more late surprises :) Comment Actions Actually, one question.
It seems like it would be simpler to not create a symbol table in the first place in cases where it will not be emitted into the binary anyway. In LowerCallResults, can we do MIB.addSym(WebAssembly::getOrCreateFunctionTableSymbol(
MF.getContext(), "__indirect_function_table"));only if MF.getSubtarget<WebAssemblySubtarget>().hasReferenceTypes() and otherwise continue doing MIB.addImm(0)? Comment Actions This could work, but the issue comes as to whether or not to emit the __indirect_function_table import. Currently the mechanism from D91637 (which, looking at it now, landed in November already -- how has this task gone on for so long???) is that the __indirect_function_table import is added the output file only if needed. We need some way for a compilation unit to record that it actually needs the indirect function table. Currently we use the presence of the table symbol in the symtab. Comment Actions Logic ensuring function-to-pointer casts cause __indirect_function_table to be present moved to WebAssemblyAsmPrinter; bug pending for WebAssemblyAsmParser though. Comment Actions @tlively: So, this appears to work. However I ran into a problem in WebAssemblyAsmParser -- it needs to do this same logic, if a function-to-pointer cast happens in assembly, we should ensure that the indirect function table is present in the output. Before, this case was caught by WasmObjectWriter. E.g. test/MC/WebAssembly/weak-alias.s has: load_hidden_func:
.functype load_hidden_func () -> (i32)
global.get __table_base
i32.const hidden_func@TBREL
i32.add
end_functionBut with no call_indirect, the output doesn't have __indirect_function_table, as it should. I could check if any instruction is i32.const or i64.const with the operand being a symbol, and check that the symbol is a function, but that is gross :/ I will continue to think about this but any pointers you might have would be welcome. I lean towards my previous solution, fwiw. Comment Actions Thinking about this a bit more after a nap -- how about I put some ensure-there's-a-function-table logic back to WasmObjectWriter in response to a TABLE_INDEX reloc, but I remove the feature detection from there. I remove the logic from AsmPrinter (maybe; see below). I have a new idea about how to determine when to write a symtab entry for __indirect_function_table. How about, in WasmObjectWriter, we only write table symtab entries if they are needed. If any table symtab entry is needed, all tables should have symtab entries.
With this strategy, we may get a reference-types file which needs a __indirect_function_table because of a function bitcast, but it's not used in a reloc so no symtab entry is emitted. That's fine with the linker logic from D96001. The indirect function table will not be relocatable in that case but that's fine; the indirect function table will be assigned table number 0 anyway. Only way that can fail is if the linker output defines __indirect_function_table locally but some other compilation unit imports a table; perhaps that is an argument for not removing the AsmPrinter case. Comment Actions Thinking again. Apologies for the late tergiversations -- if you have a compilation unit with a function bitcast but no call_indirect and no other tables, in practice you have a relocatable table. The linker can assign __indirect_function_table to any table number because there are no uses to relocate. (I had locally added a hasNonRelocatableUses flag to the MCSymbolWasm for tracking this.) But, a linker would only assign non-zero table numbers if there is a table symtab entry, and old linkers won't accept table symtab entries, so you really need to gate the presence of the symtab entry on the reference-types feature. You can't decide automatically :/ I think this problem is important to solve so I will continue to think about it. The previous feature-detection-in-the-writer appeared to solve the problem fwiw. Comment Actions Gently ping here; this is the next patch to land, and as we have few overnights left in the week it would be great to get review tonight. I know it's long; my apologies! Comment Actions I have two remaining concerns about this patch:
I do want to continue discussing those points, but I know this is a largish patch that has been outstanding for a while and is blocking further work. If you feel it would be more efficient, I would be fine landing this as-is and addressing those points in follow-ups.
Comment Actions Moin :) Revisiting -- as you suggest I am going to land as-is, then follow up with a patch to not "magically" refer to __indirect_function_table in +reference-types files. If you reach a conclusion about argument order in this evening's wasm-tools meeting, please let me know and I can follow up as necessary there too. Comment Actions Yaargh, bit by the "phab description is not necessarily what gets committed" issue -- patch committed is fine but description was outdated. In mozilla for example they land patches instead via "lando", a phab service that applies the patch as reviewed instead of opening space for errors like this one. Anyway, my apologies for the commit note mismatch. Comment Actions I think this broke the LLVM roll on Emscripten CI. I don't have time to bisect atm, but this is the only wasm-related commit in the range, and the compiler crash is on a file and function modified in this patch: llvm::WebAssembly::getOrCreateFunctionTableSymbol(llvm::MCContext&, llvm::WebAssemblySubtarget const*) WebAssemblyUtilities.cpp Regression range: https://chromium-review.googlesource.com/c/emscripten-releases/+/2711978 Crash is when building system/lib/libc/musl/src/stdio/stderr.c in libc. Comment Actions We're also seeing this in Mozilla's build of https://github.com/WebAssembly/wasi-sdk, and our bisect indeed pointed to this commit. In case having a second set of repro steps helps, we're doing a relatively vanilla make : https://searchfox.org/mozilla-central/source/taskcluster/scripts/misc/build-wasi-sysroot.sh#9 Comment Actions Thanks for the reports, I will revert this patch and reland when I test against emscripten.
Comment Actions We have an internal codebase the triggers an error after this change. We have a repro case in https://bugs.llvm.org/show_bug.cgi?id=50408 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Move this comment down to reset?