Feature detection section in binary modules?

icefoxen commented 6 years ago

Okay, I've read the cpuid opcode discussion #1161 and associated stuff, and would like to suggest an alternative to a cpuid instruction: Add an section type to the wasm binary format that, one way or another, allows a program to declare what features it requires. It seems that this would be a very modest extension to implementations, would make life much easier for programmers targeting wasm, and would be a self-detecting feature to begin with (since sections can be omitted and potentially ignored(?)).

Advantages:

Feature checking can be faster and simpler than attempting to validate a myriad of tiny canonical (and hence write-once) stub modules and track which ones work and which don't
Implementations can easily advertise to programs what features they do and do not support, and more easily report to the user what's going on when a feature is unsupported instead of "some module failed to validate"
It's easier for programs that manipulate wasm binaries to make sure that the results are actually sensible and consistent with each other (trivial example, if you're building a program that needs to run on an implementation with no threads, your linker/bundler program can assure you that none of your libraries require the thread feature).
If it's easy to find out what features a module requires, it's also easy for an implementation to provide functionality to shuffle through a set of modules built with different features to find one that is supported. Otherwise the module programmer to re-write the (uninteresting) code to do this themselves and needs some kind of consistent hook to retrieve error message from the validator.

Disadvantages:

???

eholk commented 6 years ago

If I understand your proposal right, it sounds like implementations would check the required features section and if the module declares it needs features the implementation doesn't support, the implementation would just report a failure early. Is this right? If so, what advantage does this provide over trying to compile and failing during the validation step?

icefoxen commented 6 years ago

It's easier (ie, possible) to have programs that inspect other programs and make intelligent decisions about them or provide useful information. For instance, an objdump program can list what extensions a module requires, without needing an entire wasm validator, even if it doesn't recognize a particular extension.

Comparing a list of features in a section is faster than trying to validate 100 tiny autoconf-style test programs.

We don't need 100 tiny autoconf-style test programs, an autoconf-style runner program, and the associated baggage along with every program that might want to ever use a feature.

It's easier for an implementation to give useful information when it knows what you're actually trying to do. (It can say "Unsupported feature: threads" instead of "Unknown opcode: 0xFEDC".)

You can force implementers to actually list their custom extensions and how to test for them in a sensible fashion instead of providing autoconf-style test programs which may clash with each other.

What advantage does trying to compile and failing during the validation step provide over explicitly stating what features a module requires?

rossberg commented 6 years ago

You don't need a 100 small programs, a single one would do -- at least in those cases where the proposed section would help.

icefoxen commented 6 years ago

You don't need a 100 small programs, a single one would do -- at least in those cases where the proposed section would help.

This seems at odds with the previous discussion of the matter that suggests you would have a tiny standalone program to attempt to validate each feature: https://github.com/WebAssembly/design/issues/416#issuecomment-188505172 #1000 . So, if you have N features you want to test at once, and there are no dependencies between them, you need N modules to test for them.

Which cases have I described where the proposed section would not help?

jfbastien commented 6 years ago

It would be useful to understand which features we're talking about detecting. Right now I don't think anyone uses any feature detection, but when we ship say threads or SIMD or GC, would you try to detect all three separately and have different binaries for each combination?

icefoxen commented 6 years ago

What features we're talking about detecting are any features that are not described in the MVP, and at least all the ones described in future features.

I'm imagining, at the simplest level, just a section in the module's binary with a list of flags described by unique strings. So if a program used threads and SIMD this section would contain the strings standard.threads and standard.simd. If a SIMD v2 specification got published and the module wanted to use it the feature section could include standard.simd2 as well. If a vendor decided to make a non-standard or experimental extension it could be called mozilla.experimental.simd3 or whatever. An implementation would know what features it supports, and would check during validation to make sure it provides everything the module needs.

The agreement from previous issues seems to be that someone writing wasm programs should offer separate binaries for each different combination of features they wish to support. The intent of this is to just to provide more information in a wasm module about what features it needs, and to allow implementations to provide more information about what features they implement, for the sake of both tools and users.

jfbastien commented 6 years ago

Browser-side, validation already does feature detection as needed. It's strictly more work, and potential bug, for a browser to also support a feature detection section.

I'm not saying it's useless, though.

What I'm rather asking is: are there concrete real-world cases where a feature detection section is clearly better from a WebAssembly user's perpective than using small module validation? I understand the general scheme you're painting, but I'm still unconvinced.

icefoxen commented 6 years ago

Not that I have any data for! It just seems an obvious but incremental improvement. If you want I can write a couple implementations that have useful extensions that are are difficult and error prone to detect via small modules. :-P I just don't see how matching a string in a section is strictly more work and a potential bug compared to writing, maintaining, distributing, fetching, and testing small modules.

Besides, there's the use case I've already mentioned: You can see what features a module expects without needing a full validator that knows about every possible feature. Even if it doesn't know what the features are. This seems like a useful thing to have in a disassembler or possibly a debugger, and the alternative is having the disassembler say "this module is invalid and I don't know why".

Besides, when has there ever been any software platform which had more than one implementation that didn't have irritating and hard-to-detect inconsistencies between them?

runvnc commented 6 years ago

This sounds similar to #363 .. actually if you substitute 'small self contained modules declared as imports' for 'feature detection' it seems very similar. Can someone mention a reference for "small module validation"?

Also can someone reference any issues documenting serious design work that brings any input or output features (such as graphics, DOM, keyboard, etc.) from JS land into web assembly code. Or is this still 'future features' indefinitely.

nileshgulia1 commented 6 years ago

Hello , Do anyone know how to check whether webassembly is supported in my browser or not? I have implemented this code but it returns nothing: @icefoxen can you help?

constructor(props){
    super(props);
    this.state = {wasm : false};
    }

    componentDidMount(){
            if (typeof WebAssembly === "object"
                && typeof WebAssembly.instantiate === "function") {
                  this.setState({wasm: true})
            }
    console.log(this.state.wasm ? "WebAssembly is supported" : "WebAssembly is not supported");
    }

jfbastien commented 6 years ago

@nileshgulia1 you probably want to check StackOverflow for questions like these.

gnzlbg commented 6 years ago

I just finished exposing the WASM SIMD ISA in the Rust's standard library, and feature detection is the main concern I currently have about WASM.

I am late to the party, but have read the following discussions related to this issue:

Please if I missed any important discussion about this feel encouraged to refer me to it.

In those discussions I've seen the statement:

WASM is a low-level ISA, therefore it won't have many features, and these will appear slowly.

This and similar statements were made a long time ago and are false today: we already have at least 4 features in llvm and this number will go to >10 very soon if the current rate of WASM evolution continues.

There are follow ups to this statement that conclude that eval is all the feature detection you need 0 , since if you have a wasm module, you can try to compile it, and if that fails, then you know that the features used in the module are not available in your compiler, and can choose another module instead.

While that's technically true, that is in my opinion a very poor technical solution to the problem.

The approach proposed in this issue makes this a bit better, by making the features a top-level property of the module, so that code generators can bail out early, but there are still significant problems with this approach.

If I understood things correctly (which I am not sure I do), the main problem with the proposed approaches is a combinatorial explosion of WASM modules / binaries that have to be produced by native languages to make use of most features.

Suppose you are writing C code or Rust. If a WASM machine code generator doesn't support a feature, it will fail to validate the WASM binary. This means that those compiling C and Rust to WASM have to potentially provide a combinatorial explosion of binaries for every combination of features that the WASM machine code generator might support, rank them, and choose the best one.

Example: Machine code generator A supports WASM+Threads, while B supports WASM+SIMD, and C supports WASM+Atomics. Rust users cannot compile a WASM+Threads+SIMD+Atomics binary, it has to provide WASM (worst), WASM+SIMD (works on B), WASM+Atomics (works on C), WASM+Threads (works on AB), WASM+SIMD+Atomics, WASM+SIMD+Threads, WASM+Atomics+Threads, WASM+Atomics+Threads+SIMD (best). These binaries can be a whole application, with a full dependency graph of libraries.

These binaries do not have to be shipped to the client. One could compile tiny modules for the purposes of detection, ship those over the network, find the best feature set, and then just download the best "application". However, the application would still need to be compiled potentially for the whole combinatorial explosion of features.

I think this is already a problem for applications, but it is an even bigger problem for toolchains. In Rust, we have to provide two standard libraries, one compiled with SIMD, and one without. Once we add atomics, we have to provide WASM, WASM+SIMD, WASM+ATOMICS, WASM+SIMD+ATOMICS, and once we add threads, I already show it above. This is not sustainable. Not for toolchains, and particularly not for users who on deployment could potentially need to recompile the whole world for every feature combination.

And this is just so that the WASM can be compiled to machine code. We are not even talking about whether the machine code generator or the hardware actually does a good job at this, e.g., does the actual hardware support atomics, or threads, or SIMD? Does the machine code generator is good at polyfilling SIMD, or should the binary for that particular generator just disable SIMD and use scalar code? Does the machine code generator have a bug that is triggered in my application? I think these are orthogonal problem, and not as pressing as this one.

I don't have a good proposal to tackle this issue, but I don't think this should be tackled for a whole binary / module.

I would prefer if there was a directive that tells the wasm machine code generator: "if you do not support feature F version x.y.z, ignore the next N bytes of the binary, and put a guard on it so that trying to access it (e.g. via a call, jump, ...) traps". This together with a way for the user to query if the machine code generator supports a feature, maybe coupled with a conditional jump or similar, would allow the user to generate binaries containing code for all feature combinations, and for the code itself to decide what to do depending on what the machine code generator can do.

That's obviously extremely hand-wavy, but I'd prefer such a direction over the ones that are being proposed because that would fix the combinatorial explosion of binaries that users and toolchains have to deal with.

kumpera commented 6 years ago

With mono we face a similar situation as described by @gnzlbg. We can't simply ship every combination possible.

What we're planning to do is group features based on adoption by all major browser platforms.

lukewagner commented 6 years ago

Agreed that it is attractive to try to have a single .wasm that Just Works under a variety of conditions. This problem is kindof tricky because features don't just add operators (for which the concept "trap if this is executed" makes sense): they add types (which can show up everywhere), sections, subsections, flags to existing LEB128 flag fields, etc. Thus, for a load-time-ifdef type of feature to work, it has to be usable over the entire binary, not just function bodies. That means this polyfilling feature is more like a "layer 1 macro".

That doesn't mean we shouldn't do it, just that this feature was outside the scope of the MVP which only focused on layer 0. In theory, such a feature could be prototyped and polyfilled by manipulating the bytes of the wasm ArrayBuffer or Response.body stream directly.

icefoxen commented 6 years ago

Or one could just say "wasm 1.1 MUST include the following features..." and group releases that way. You have a set of features that are de-facto Supported Everywhere, and can test for them as a unit without a combinatorial explosion of possible feature combinations, however the testing is actually performed. This ends up equivalent to "group features based on adoption by all major browser platforms", just with more guarantees, and more bureaucracy.

The problem also gets a little easier when one considers features that depend on other features. If one has a threading feature, it may depend on an atomics feature and a shared memory feature, so you just need binary version "with threading" or "without threading", not "with threading+atomics+shmem", "with threading+atomics without shmem", "with threading without atomics+shmem", etc. The more orthogonal the features are the harder this becomes.

Also, I think to some extent this whole issue is a great example of Conway's Law... :grin:

alexcrichton commented 6 years ago

@gnzlbg I was thinking about this a bit and I think that @lukewagner's idea of polyfilling this for now is actually pretty plausible (even in the context of Rust).

Let's say for example that the Rust standard library, like on other targets, doesn't enable simd128 for itself but provides intrinsics that downstream consumers can use. It similarly provides an is_wasm_feature_detcted!(...) macro like we have for x86 which ends up importing a global from the environement like __SIMD_DETECTED. The module won't be directly instantiable, but it'd be relatively trivial to postprocess this module in one of two ways:

First, a client locally discovers that its browser supports SIMD, so it sends a request to a server for the wasm file saying "I also have SIMD available". The server takes the wasm module, fills in __SIMD_DETECTED with a const of true, maybe even runs wasm-opt real quick to const-propagate that value, and then sends it to the client.
Alternatively, the client discovers that it doesn't support SIMD, and the server request says so. In this case the server postprocesses the wasm file to have __SIMD_DETECTED to be false but also removes all usage of the v128 type. All SIMD instructions would be replaced with unreachable/trap instructions and v128 arguments would be removed. In theory this is still a workable binary if it correctly uses the detection macro.

In that sense we could have a "userland-defined" system (or something like a bundler convention) where for all features if it's supported everything works just fine and if it's not supported it's either polyfilled (like atomics becoming non-atomic operations) or becomes traps (like SIMD).

None of this (AFAIK at least) is implemented for sure, but it does mean that we don't necessarily need to have native wasm support for feature detection, but rather a tool which can "dumb down" a wasm module from using newer features to only using older features (along with coding practices to continue to operate correctly when only using older features)

gnzlbg commented 6 years ago

@alexcrichton

Thanks for chiming in.

It similarly provides an is_wasm_feature_detcted!(...) macro like we have for x86 which ends up importing a global from the environement like __SIMD_DETECTED.

Yes, I think this is something we want to do anyways and is more or less what I had in mind with: "This together with a way for the user to query if the machine code generator supports a feature, maybe coupled with a conditional jump or similar, [..] and for the code itself to decide what to do depending on what the machine code generator can do." I didn't have a concrete proposal, but yours is good.

I also thought that it would make sense for the machine code generator to fill these values depending on which features it support, but I think your approach makes more sense since it allows this to happen either on the client or the server, and allows the application to decide whether it wants to run wasm-opt or not.

but also removes all usage of the v128 type. [...]

Let's say for example that the Rust standard library, like on other targets, doesn't enable simd128 for itself but provides intrinsics that downstream consumers can use.

So what wasm would these intrinsics contain? Would they be compiled with simd128 in isolation? Or would they just be "macros" that are replaced with "something" when __SIMD_DETECTED is substituted in the binary? This something could be either wasm that uses simd128 or traps (or polyfilled scalar versions), and would also need to be in the binary so that it can be properly replaced, right?

I think that this could work and that it would solve our problems.

A couple of thoughts on this idea - don't know if they are positive or negative, I am undecided:

As @lukewagner says we are inventing macros for wasm. This is not something that can be prevented, as in, people can do this already. Maybe it would make sense to develop a spec for this in tandem with the implementation, since it would be good if all tools would understand macros. For example, the machine code generator could expect (or not) macros to be fully expanded, the same could apply to wasm-opt. It would be nice if these tools would error nicely when the user inevitably passes them a wasm binary with unexpanded macros. We might also need a wasm-expand tool that takes a binary containing macros, and expands all or some of them. Avoiding a proliferation of "macro systems" on top of wasm could be a good thing (although if someone wants to invent and use their own, there is nothing that we can do to prevent that beyond saying "the default one that all tools understand can do that better than yours").
The rust toolchain would need to compile not to wasm, but to wasm with unexpanded macros. The SIMD intrinsics would compile down to a macro that can be expanded, and would be expanded to some wasm using v128 and SIMD instructions if __SIMD_DETECTED is true, or to scalar code/traps/... if __SIMD_DETECTED is false. So we need to be able to generate and embed wasm with and without the simd128 feature into the same binary. Can be done, but it would probably be helpful if LLVM would cooperate with us here by supporting WASM features to be enabled only in certain LLVM modules, functions, etc. and maybe even generating macros. That is, if llvm would have a "wasm-macros" target.
wasm-opt might need to become really clever to handle "from macros expanded wasm modules" properly: the binaries passed to wasm-opt might only use SIMD in some restricted places, and the rest of the binary has been compiled without SIMD. However, if the binary uses SIMD anywhere, that means that the whole binary can use SIMD, so a tool like wasm-opt might need to go through the whole binary, turning scalar wasm into vector wasm if it sees v128 being used anywhere. I am a bit afraid that at the end of the day, if wasm-opt isn't clever enough to do this properly, what people would do is compile their application using N combination of features into the same wasm module, and just use the macros at the top level to select one version depending on the features available. This might not be a bad idea per se, but at that point, we are pretty much where we started and have just invented a way to package N wasm modules into the same one.

alexcrichton commented 6 years ago

So what wasm would these intrinsics contain? Would they be compiled with simd128 in isolation?

I'd expected them to be like our x86 intrinsics where each intrinsic doesn't actually have any machine code in libstd (since they're inlined), but when machine code is generated they're compiled with simd128 in isolation. That is, each intrinsic would generate the corresponding SIMD instruction. These instructions would be what's replaced with traps by the postprocessing stage.

Note that it's on the user to detect features (at some point reading __SIMD_DETECTED) and relying on dynamic runtime behavior to avoid the unreachable instructions in the case where SIMD isn't available.

As @lukewagner says we are inventing macros for wasm. This is not something that can be prevented, as in, people can do this already. Maybe it would make sense to develop a spec for this in tandem with the implementation, since it would be good if all tools would understand macros.

An excellent point! This is sort of the catch-22 we're facing with wasm-bindgen as well. Ideally it'll be largely supported by engines natively one day, but in the meantime we're pretty loose about "spec" things per se. It definitely seems to be the case, though, that having a strong and solid technical MVP is a great way to prove out a technology!

The rust toolchain would need to compile not to wasm, but to wasm with unexpanded macros. The

Correct! This would be a big ask for rustc, to be clear. I'm not sure how we'd want to handle this and we'd definitely want community consenus (at least in Rust) about doing something like this before actually codifying it. We'd want to be sure (likely) to have a suite of tools ready to transform Rust binaries into production-ready binaries (or integration in common servers like Webpack)

kripken commented 6 years ago

I like the idea to rely on wasm-opt or similar tools to help out here. It seems like this could work as mentioned above, that is, one or both of the following two approaches:

For SIMD (and the same for other features) there is a wasm global has_SIMD, and code everywhere looks like if (has_SIMD) { .. } else { .. }. Then we can set the constant to 1 or 0, then run the standard wasm-opt optimizer passes, and those optimizations would remove the global, the if checks, the unneeded arms of the ifs, and any global types etc. that are no longer necessary.
We can add a lower-SIMD pass to wasm-opt, that completely replaces all SIMD code with scalar. We'd probably want to run the optimizer afterwards too, as a lowering pass like that probably creates some temporary stuff that can be optimized out.

1 is probably not enough by itself, as a lowering pass would be needed for stuff we can't put in an if, like if a SIMD type is used in a function parameter. On the other hand 1 can have more tailored code in the if arms. Another difference is that 1 puts most of the work on the frontend compiler, while 2 puts most of the work on wasm-opt. I'm not sure how hard 1 would be for frontends, but 2 seems pretty easy to do in binaryen. (@gnzlbg, you mention some special cleverness might be needed here, I think maybe I'm missing something?)

kumpera commented 6 years ago

Having a feature section in wasm modules would be useful for toolchain authors when linking/validating programs made out of multiple wasm modules.

The same could be used by package managers - one could argue that a dependency should not depend on more features than the module using it.

At runtime, a features section is not that useful, but having a way to query the host for extensions would save us multiple roundtrips when figuring out which wasm module to download - instead of downloading probe module(s) then the fallback/optimized module, we'd be able to hit the right one straight away.

On the idea of using globals and wasm-opt as a way to polyfill our way out. That should work just fine for things that can be trivially polyfilled like SIMD, but it won't be useful at all with GC or Threading. With C#, at least, those will require completely different modules and assets.

Overall, piecemeal polyfilling does not lead to very practical testing due to its exponential testing matrix. It's more practical to test with "wasm-2017", "wasm-2019" and so on.

gnzlbg commented 6 years ago

@kripken

(@gnzlbg, you mention some special cleverness might be needed here, I think maybe I'm missing something?)

Under the "macro expansion" approach being discussed here (by luke, alex, et al.) the C or Rust compiler generates scalar code everywhere (without SIMD) except in some parts of the module that are only included conditionally into the final binary via macro expansion. That is, most of the binary uses scalar code, while only a tiny fraction of it uses SIMD instructions.

OTOH, when one targets WASM from C or Rust and enables unconditionally SIMD for the target upfront, LLVM scalar and loop vectorizers will try to use SIMD instructions everywhere.

That is, there is a potentially a huge performance cliff between deciding to use SIMD upfront (that is, not supporting targets without SIMD), and the "using SIMD behind macro expansion" approach.

So what did I meant with wasm-opt would need to become more clever? I meant that it would be tempting for wasm-opt to try to recover this performance by trying to vectorize scalar code if it can prove that SIMD is available. Proving this is easy: if it finds a SIMD instruction somewhere, SIMD is available for the whole binary, but vectorizing the scalar code is a very difficult thing to do: it would need to start by trying to find loops since all the semantic information available in the C / Rust / LLVM-IR has been lost at this point...

@alexcrichton already mentioned that LLVM is going to have to cooperate with C / Rust front-ends for any of this to work anyway, so I think it makes more sense for LLVM to do the same thing it does for other targets: when it can prove that's its worth it, LLVM would generate two versions of a loop, one that uses WASM SIMD, and one that uses scalar code, and use the macro system so that the right version is included on macro expansion.

This is just another example where the whole toolchain needs to cooperate when it comes to macros to produce a good result.

kripken commented 6 years ago

I see, thanks @gnzlbg - yeah, I agree vectorizing is very hard, I doubt wasm-opt would want to try. This would need to be coordinated across the whole toolchain for it to make sense, as you said. I'd volunteer to help on the binaryen side, if we plan to go that route.

Also agree with @kumpera - may make sense to group features in wasm-2018 etc. We can polyfill away on the client stuff like SIMD, non-trapping conversions, etc., but yeah, for the big things like GC and threads, separate builds are necessary, and grouping them may therefore be best. For that, it maybe it might be nice if wasm had an official grouping, as in, a linear order where a browser wouldn't support GC without supporting threads (or however that order makes sense)?

tlively commented 6 years ago

I've added an agenda item to the next wasm CG meeting to discuss formally specifying such dependencies between wasm features (https://github.com/WebAssembly/meetings/blob/master/2018/CG-08-21.md). This would limit the number of feature combinations that a spec-compliant engine could possibly expose. If the feature dependence DAG has low fanout, it approximates the "wasm-2017", "wasm-2019" checkpointing idea without introducing artificial checkpoints.

jeff-hykin commented 3 years ago

Maybe my inexperience is hiding an obvious reason this would fail; but wouldn't it suit everyone's needs for WASM to add a fallback to module imports?

Basically, optional features like SIMD would be imported as a module. As part of the import syntax, there would be an if-successful and if-failed branch. This could handle both the macro-conditional case, and the polyfill case.

For the polyfill, the fail branch would implement the same interface as the one attempting to be imported.

For the macro case, the two branches would act like an #ifdef with alternative definitions of functions. For example, the success branch would define a computeStuff function implementation that used the imported SIMD tools and the fail branch would define a computeStuff implementation without the SIMD tools. This way the wasm runtime, even JIT runtimes, could do minimal static analysis to cut out whichever branch wasn't ever going to be executed.

tlively commented 3 years ago

The feature detection proposal would allow for a compilation scheme that falls back to calling imported polyfill functions, but my expectation is that the call overhead would make it more attractive to have fallback code paths directly in the module rather than depending on an external polyfill.

The reason we don't spec new core wasm features as standardized imports is that we don't have a mechanism to spec imports that should be available on all engines. We've discussed having "intrinsic" imports before, but there was never sufficient motivation to pursue them instead of the well-lit path of adding new instructions to core Wasm.

jeff-hykin commented 3 years ago

we don't have a mechanism to spec imports that should be available on all engines

Why would it need to be available on all engines? The purpose is that the module is specifically not available in some engines. Does the scope of feature detection include individual core features?

We've discussed having "intrinsic" imports

Okay I'll search for that and have a read

fallback code paths directly in the module rather than depending on an external polyfill

Since I forgot to mention it directly, I did intend for the success/fail branches to be inline rather than external.

WebAssembly / design

Feature detection section in binary modules? #1173