Slacked fuel metering

[pepyakin]

wasmtime right now has the fuel mechanism. It allows precise control of how many instructions are executed before suspending execution, at least at a basic block granularity. The price is a rather significant performance hit.

I believe we can do better in case the user only wants to know if the execution exceeded some fuel limit. The cost to pay is that condition is detected with a delay, hence slacked. Therefore, this works similarly to the fuel metering mechanism only if there are no side effects when the execution reaches its deadline. For instance, all changes performed are rolled back if a DB transaction exceeds its fuel allowance.

The idea is to take the existing fuel mechanism, remove the compare & conditional jumps, and check the out-of-fuel condition asynchronously.

The tricky part is the asynchronous fuel variable checking and suspending the execution.

We could leverage HotSpot-style safepoints to implement this. Such a safepoint could be implemented just as access to a page. Suspending the execution could be triggered by mprotect-ing the page. Similarly to epoch interruption, we could place safepoints when entering a function and loop backedges. We would need to extract the fuel counter while handling the page fault signal. We assume that the codegen thoughtfully left us a mapping where the fuel counter is saved: either a register or an offset for a spilled variable. Having recovered the fuel counter, we'd check if it exceeded the limit and yield if so.

I realized that this is not trivial to benchmark. I tried removing fuel_check, but that would lead to DCE of the now unused fuel value. I would appreciate suggestions on how to benchmark that properly.

• Does this sound sensible? Am I missing something obvious?
• Is this something that could be considered to be accepted upstream?

[alexcrichton]

One of the primary reasons for fuel as oppose to epochs is due to the deterministic nature of fuel, which I think is why a scheme like you've proposed where with asynchronous checks wouldn't entirely supplant fuel but would perhaps be another method of limiting wasm execution in Wasmtime. In some sense though what it seems like you're looking for is a hybrid of epochs (asynchronous cancellation, low overhead) and fuel (the measure of cancellation being how much code has run). I wonder if that might make more sense? For example if you could read (but not write) fuel from another thread then you could increment the epoch when fuel runs out or something like that.

In terms of the cost of fuel, though, I believe the main cost associated with it is not the checks for out-of-fuel but rather the management of the fuel counter itself which has lots of loads and, critically, stores to memory. The repeated memory traffic ends up being quite costly as oppose to epochs which is simply always reading the same memory location which should be more efficient (and from our benchmarking the efficiency of epochs is much better).

I suppose that I can put this a little differently in that if the fuel check was moved asynchronously I'm not sure it would buy much. If the check itself is moved externally then that loses the determinism of fuel, and I also think that the main cost associated with fuel will still be present, namely the management of the fuel counter itself.

[cfallin]

There does seem to be some utility to a "count the ops but don't interrupt" configuration for fuel, in that some users may be interested in basically a perf counter/stat but don't need to set limits. I agree that the removal of the control flow will only remove a part of the overhead for fuel; but it should significantly shrink code size, which is something.

I guess mostly I'd love to see measurements: @pepyakin have you experimented with this already? If not, would you be willing to hack something together? It shouldn't be too complex: basically we want to return from a codegen helper here (just after fuel_increment_var, before we create the blocks and add the compare/branch).

[cfallin]

(For clarity, if this shows a sufficient benefit for your use-case, then I agree with Alex's suggested hybrid approach above: the way to go is to make it a config option to count fuel without interrupts, and then use epoch interruption to actually halt execution asynchronously.)

[pepyakin]

In some sense though what it seems like you're looking for is a hybrid of epochs (asynchronous cancellation, low overhead) and fuel (the measure of cancellation being how much code has run). I wonder if that might make more sense? For example if you could read (but not write) fuel from another thread then you could increment the epoch when fuel runs out or something like that.

Yes, this is similar to what I was looking for.

Although I would still clarify,

1. I am interested in if a given program finished executing within a given number of steps.
2. If it was not able to finish, I am not interested in the results.
3. I am also ok with allowing some time slack until the detection that the program exceeded the number of steps.

Given point 2 this can be deterministic: ignoring timing, multiple executions of the same program with the same inputs will lead to the same outcome.

I was also wondering about the same construction that you propose. I assumed that that approach would require memory writes on each loop header & function call and those have to be atomic, and I assumed that would be even more overhead.

In terms of the cost of fuel, though, I believe the main cost associated with it is not the checks for out-of-fuel but rather the management of the fuel counter itself which has lots of loads and, critically, stores to memory. The repeated memory traffic ends up being quite costly as oppose to epochs which is simply always reading the same memory location which should be more efficient (and from our benchmarking the efficiency of epochs is much better).

I might have explained myself poorly.

All this faffing around with safepoints I proposed was in the hope, that we can avoid not only compare&branch but the memory writing as well. It is avoiding, not eliminating though since the fuel counter still can be spilled.

I guess mostly I'd love to see measurements: @pepyakin have you experimented with this already? If not, would you be willing to hack something together? It shouldn't be too complex: basically we want to return from a codegen helper here (just after fuel_increment_var, before we create the blocks and add the compare/branch).

So all of the above are just uneducated guesses, turns out. I've tried to make a benchmark but then I realized that did a mickey mouse mistake, the one about DCE I mentioned in OP.

I'm too will love to see measurements and willing to hack. I am not sure what would be the best way to do that though.

[cfallin]

So all of the above are just uneducated guesses, turns out. I've tried to make a benchmark but then I realized that did a mickey mouse mistake, the one about DCE I mentioned in OP.

Ah, sorry, I had missed that note; but it's a little surprising given that here we call fuel_save_from_var to store the value back to memory, and this is invoked at every function exit. Stores shouldn't be DCE'd (since they are side-effecting). Can you dump the CLIF (RUST_LOG=trace should show it buried among a bunch of other output) and see what it looks like just after wasm translation?

[alexcrichton]

I assumed that that approach would require memory writes on each loop header & function call and those have to be atomic, and I assumed that would be even more overhead.

With epochs the increment of the epoch is an atomic write but all the reads are "just" atomic reads which in practice ends up being quite fast. The instrumented code itself doesn't do any atomic writes anywhere (same for fuel, not atomic writes anywhere)

Given your clarification (thanks!) it does sort of sound like you want fuel + epochs without the actual interruption of fuel though, just the accounting. This may also need to be specialized a bit in codegen to make things a bit more optimal but otherwise seems pretty close?

[pepyakin]

Ah, sorry, I had missed that note; but it's a little surprising given that here we call fuel_save_from_var to store the value back to memory, and this is invoked at every function exit. Stores shouldn't be DCE'd (since they are side-effecting). Can you dump the CLIF (RUST_LOG=trace should show it buried among a bunch of other output) and see what it looks like just after wasm translation?

Was a mistake on my part, I was doing something else. Modifying fuel_check skipping everything after fuel_increment_var as you proposed works.

So the results with my microbenchmarks are:

fuel overhead with interrupts 24-34%,
fuel overhead without interrupts 10-25%

which is something, but ideally we lower it even more.

This may also need to be specialized a bit in codegen to make things a bit more optimal but otherwise seems pretty close?

Could you elaborate on this bit?

[pepyakin]

FWIW, enabling epoch interrupts and consuming fuel (but without fuel interrupts) gives 28-40% overhead.

[cfallin]

ideally we lower it even more.

So, some fairly complex ideas incoming: there are at least research-level ideas floating around (I can't find any papers at the moment unfortunately but I know I've seen it before) on how to minimally/optimally record the trace (path taken through a program). Counting ops is equivalent to this problem so I think the same ideas apply. It goes something like: choose a set of "profiling points" (here, points at which you increment the counter), such that every branch outcome can be deduced from the points that are reached.

The simple/intuitive cases are loops (one profiling point in the header) and if/then diamonds (one profiling point in each branch) and in fact that's what we do today, rather than a profiling point in every block. But it actually starts to get interesting even with the if/else: we really only need a profiling point in one branch of the diamond. E.g., if the if-path takes 10 ops, and the else-path takes 15 ops, then we unconditionally add 10 (probably as part of the profiling point at the top of the function or enclosing loop), and add 5 more only on the else-path. Bonus points if we choose the rare path for the additional increment.

The general answer to this problem I think will have something to do with dom/postdom relations -- as a first pass, can we merge a block's profiling point (fuel increment amount) into the increment of any block it postdominates? And then there might be another transform where we draw a "postdom cut" across N blocks relative to some block, and hoist some common factor k out of all of those blocks (i.e., if anywhere we go will eventually increment by at least 10, let's hoist that). It has to be a little more subtle than that because loop bodies can postdom the post-loop tail, so we really need some sort of "1-to-1 execution count" relation. But I'd have to sit down and think more (or just find the papers on this!).

[cfallin]

Ah, one more idea that just came to mind: we could potentially remove a lot of the memory-traffic overhead of fuel counting by defining a new ABI with a "pinned fuel counter". Then it only needs to be loaded from the vmctx in host-to-wasm trampolines, and we could "spill" to vmctx at callsites to non-pinned-fuel-counter ABIs (direct calls to imported host functions for example).

[pepyakin]

So, some fairly complex ideas incoming...

Oh, right, something like this also crossed my mind.

It looks that the ABI idea is easier to hack though. You don't mean literal new ABI (as in a new variant in CallConv), since it seems to me that you can get away with changes only in crates/cranelift though, right?

[cfallin]

It looks that the ABI idea is easier to hack though. You don't mean literal new ABI (as in a new variant in CallConv), since it seems to me that you can get away with changes only in crates/cranelift though, right?

We could do it that way; but passing the value then has to be explicit (argument into every function, and extra return value from every function). Also slightly less efficient since those would be different registers, so some extra moves.

I had been thinking a flag on the Cranelift options that means "reserve a register that is globally allocated for this purpose, and provide CLIF ops to get and set it", but actually we already have that: I realized that we aren't using the "pinned reg" for anything in Wasmtime's wasm-to-CLIF lowering right now, so we could set that option and then use get_pinned_reg / set_pinned_reg to "load" and "store" the fuel count.

We'd still need to transfer it to and from the vmctx when transitioning from host to Wasm code (in the trampoline) and from Wasm to host code (this one is a little trickier).

[pepyakin]

Well, I went ahead and implemented the explicit value passing. It's messy and now I stumbled upon some problem in the wasm translation code. I suspect there is some hidden dependency on the fact that there are only two hidden params. I am debugging it right now. The trampoline code is already in place though.

Regarding get_pinned_reg/set_pinned_reg, that's funny, I looked at it but thought it's not worth of exploration thinking that it's a remnant of the old style backend. If that works, that means cranelift always has a reserved register that is not used for anything then?

UPD: Nvm, I see there is enable_pinned_reg.

[alexcrichton]

IIRC there's a fair bit of open-coding about our two implicit VMContext parameters. I think it would be great to reduce this open-coding if we can, though. But if you're hitting issues with our current two hidden parameters that's probably what's happening.

Otherwise though one important bit about ABI details and pinned registers is that right now Wasmtime's API relies on the fact that trampolines can be defined natively in Rust. This is tested currently and will break if there's ABI details Rust can't uphold (like preserving the pinned register). Overall I personally feel this is a mis-feature of Wasmtime as the only thing it buys us is the ability to Func::call a native function wrapped up via a Func, which no one really wants to do. Instead I think we should use the trampoline registration system that is already in place for modules and just simply require that lookup succeeds (e.g. documenting that Func::call in a store with no modules will panic). That would mean that we no longer have to define trampolines in Rust (and that host_trampoline function could be deleted) and all trampolines would be assembled by Cranelift. We'd still have to define a host ABI for the trampolines to talk to Rust but having that transition point where Cranelift is always in control seems prudent.

This latter point though of refactoring how trampolines-to-imported-host-functions work would require some relatively deep refactorings. I think something about the VMContext would have to change to support host trampolines, but I'm not sure precisely what having not designed it yet.

Basically I just wanted to mention that dealing with a pinned register and/or non-System-V ABIs I think is a good idea and something we should enable, but I don't believe it can trivially be done so today without more significant refactorings of what a trampoline looks like when wasm enters the host. (and enabling this all would probably best be done as a separate PR)

[pepyakin]

Hacking on the explicit passing of the fuel counter without storing it in the memory, I bumped on a bug. It manifests with fuel metering and the unreachable instruction. Basically, the transfer of control out of there means the fuel counter should be flushed just before the trap. That's easy enough.

However, other traps are tricky: memory accesses (at least with the eliminated bounds checked / mprotect) and stack overflows. If we were to flush the fuel counter, it would have to be done pretty much everywhere. I think it's not impossible that it would fare worse than vanilla fuel metering. Am I missing something?

The pinned fuel counter approach proposed by @cfallin might work in this case. I assume traps always transfer control through a signal handler. We could extract the contents of the pinned register from the last frame before the trap from within the signal handler and then flush it to VMRuntimeLimits.

I read from @alexcrichton's post that the codebase is not ready for this change yet. However, I am trying to get a sense of potential wins here, not a final solution. Do you folks see any roadblocks to hacking the solution here? If not, I might try to tackle that approach then.