Implement stable fuel metering

[Robbepop]

Currently Wasmi support fuel metering of its internal Wasmi bytecode.
The fuel is metered to the Wasmi bytecode that is resulting after the entire translation process with all the optimizations.
This means that Wasmi's fuel usage usually is less than the fuel usage of a hypothetical Wasm VM that executes Wasm bytecode directly because a single Wasmi bytecode instruction may represent multiple Wasm bytecode instructions and the Wasmi optimizer might even remove whole blocks of Wasm bytecode entirely.

Some users face problems with this approach: namely when wanting to switch to a new Wasmi version and having the requirement that code executed with the new Wasmi version runs out of fuel at the same time as the older version. This is not guaranteed with the current fuel metering approach since even a single new Wasmi bytecode optimization might change the big picture.

Solution

To resolve this issue for users we might want to introduce a new fuel metering approach that we call "stable fuel metering" because it guarantees a stable fuel consumption throughout Wasmi versions. The trick is to apply fuel usage to the input Wasm bytecode instead of the resulting Wasmi bytecode. This might lead to more fuel consumption but should always consume the same amount of fuel for the same Wasm binary and execution independent of the Wasmi version used.

Research

Research is needed to know when this "stable" fuel metering will still result in different fuel consumption with the same Wasm binary and different Wasmi versions so that we can either eliminate these situations or clearly document them.

[juntyr]

I have my own (very simplistic) implementation of fuel. I think it would be great if the community could converge on one runtime-agnostic utility crate that implements a stable fuel cost function for WASM instructions, e.g. based on the wasmparser types, so that all runtimes could provide this stable option.

[Robbepop]

@juntyr this sounds interesting. do you have a link to your stable fuel metering? Ideally the stable fuel metering was both stable and kinda efficient. Before Wasmi had built-in fuel metering people had to adjust the Wasm binary with fuel metering Wasm instructions. While this resulted in stable fuel metering, it also was extremely costly, unfortunately. This is why we now have built-in fuel metering in Wasmi.

[juntyr]

The code is part of a larger repo, but I pulled it into a snippet: https://gist.github.com/juntyr/dbe5a32707e0b154a7d7c5d9e65cfe9e#file-instcnt-rs-L176-L197

My implementation must be runtime-independent, platform-independent, and stable and is thus implemented as a transformation on the instruction sequence of a wasm module. On the other hand, I was able to make some simplifications for my case:

• I only care about reading the fuel (instruction count) before and after the top-level host calls a wasm function (I don't care about reading it inside callbacks from wasm to the host)
• I never need to react based on the fuel, therefore my count is implemented as a global that is imported by the module (but for another usecase, one could simply replace the instruction counter update at https://gist.github.com/juntyr/dbe5a32707e0b154a7d7c5d9e65cfe9e#file-instcnt-rs-L218-L228)
• I only care about core wasm modules, since I use the wasm-component-layer crate for components, which maps them back into core modules

My implementation is also the most simple one possible - every bytecode instruction counts for one fuel unit, even though this is of course demonstrably wrong for e.g. the bulk memory operations. This is where a community standard crate would be most helpful as we could all agree on a standardised stable fuel cost per bytecode instruction (for memory copy this would probably need to read the parameters).

While there is definitely some room for optimisation, my implementation is reasonably efficient as it only updates the instruction counter whenever control flow diverges. Of course this could be even further optimised e.g. by using locals inside functions, only updating the global on return, and by merging local updates when different branches have the same cost. Again, a community crate would be helpful here as the injection code could be collectively optimised as long as the stable costs are maintained.

What are your thoughts?

[Robbepop]

What you describe with your gas metering sounds extremely similar to what has been done some years ago in the wasm-instrument crate, together with other Wasm instrumentation such as stack height metering. Have you taken a look at that crate prior?
Link: https://github.com/paritytech/wasm-instrument

Wasmi's built-in gas metering also only charges for fuel on diverging branches. Also due to better knowledge of the code generation it can do better than an external tool ever could. And furthermore, its built-in gas metering is MUCH more efficient. We once tested it against the old gas metering from wasm-instrument and it was roughly 5-10% slower than no gas metering at all whereas the gas metering via wasm-instrument was like ~2-3x slower overall IIRC.

Since this is an important topic for many Wasm users and solutions provided by external tools are inefficient while solutions provided by VMs themselves (e.g. Wasmi) are usually not stable across other VMs it might make sense to have a proper standard in place. This is probably a lot of work but with proper motivation I could see it fit into the Wasm standard somewhere.

[juntyr]

What you describe with your gas metering sounds extremely similar to what has been done some years ago in the wasm-instrument crate, together with other Wasm instrumentation such as stack height metering. Have you taken a look at that crate prior? Link: https://github.com/paritytech/wasm-instrument

There are a few very similar implementations of this problem. I think I originally wrote my own (after trying out metering in wasmi and wasmtime and maybe even the instrument crate - I don’t fully remember) because I only need to monitor but never act on the fuel count, I wanted exact control over how much different instructions cost, and I did not want to pay for function calls that are not needed.

Wasmi's built-in gas metering also only charges for fuel on diverging branches. Also due to better knowledge of the code generation it can do better than an external tool ever could. And furthermore, its built-in gas metering is MUCH more efficient. We once tested it against the old gas metering from wasm-instrument and it was roughly 5-10% slower than no gas metering at all whereas the gas metering via wasm-instrument was like ~2-3x slower overall IIRC.

Wow, that’s quite the difference! Since wasmi already has access to some instruction counter, it makes sense that doing the metering in native and not interpreted code is a lot faster. I wonder how much of that slowdown comes from wasm-instrument not inlining their counter updates, and what the benchmarks are for wasmtime where both the native and bytecode based approaches are compiled.

One thing to note is that I am a proponent for unifying the different runtime interfaces and not stashing too much special API surface into each. It would be unfortunate if this young ecosystem gets its own vendor lock-in.

Since this is an important topic for many Wasm users and solutions provided by external tools are inefficient while solutions provided by VMs themselves (e.g. Wasmi) are usually not stable across other VMs it might make sense to have a proper standard in place. This is probably a lot of work but with proper motivation I could see it fit into the Wasm standard somewhere.

I think a good first step would be an external tool that defines the stable instruction count / fuel consumption and has extensible counter updates, so that users like me who don’t need branching don’t need to pay for it. Then different runtimes could implement their optimised versions to match this behaviour. Perhaps at some point, e.g. via a custom section, the external tool variant could also be made transparent to runtimes so they could optimise it out.

[Robbepop]

I just started a discussion in WebAssembly discord about this in case you want to join:
https://discord.com/channels/453584038356058112/1259413291709628529