Use virtual memory tricks to make interrupt checks smaller and faster

[fitzgen]

Right now, to check if for interrupts:

• we load the interrupts pointer from the vmctx
• we dereference it to get the maybe-interrupted value
• we compare that against the interrupt-has-been-requested value
• and finally we conditionally trap when the comparison returned true.

There is no fast/slow path split here. Interrupts happen rarely, but we always perform those four steps.

By using virtual memory tricks, we can create a fast path for the common case when no interrupts are requested. We reserve a page of memory as the "interrupt page" and point to it from the vmctx. This replaces the current interrupt pointer on the vmctx. When interrupts are not requested, this page is readable. When an interrupt is requested, remove the readable bit via mprotect, and wait.

Now, all that our loop headers do is:

• load the pointer to the interrupts page from the vmctx
• (attempt to) read the first byte from the interrupts page

When the interrupts page is readable and an interrupt is not requested, we just have those two loads as our fast path.

When the interrupts page is not readable because an interrupt is requested, a signal is generated, so our signal handler needs to recognize+handle this case.

IIRC, essentially this same trick is used in some JVMs for synchronizing at safepoints for stop-the-world GC phases (e.g. root marking).

The one open question is how to detect stack overflows with this setup, since our interrupt handling and stack overflow code is very intertwined. Not totally sure here.

+cc @alexcrichton

[alexcrichton]

Seems like a great idea! One thing that would be good to measure before committing to this is the overhead of the current strategy to see how much of an improvement this trick is. That way if it's like a 20% speedup even if we can't figure it out for stack checks it seems worthwhile.

For stack checks I think they'll fundamentally always need to have a comparison of some kind, but we could still have stack checks and interrupt checks in loops check the same memory location. We could basically "malloc a word for the stack check limit" by allocating a page from the OS, and then on interrupt we unmap it.

[fitzgen]

Brief summary of an evolution of this idea that came up from discussion between @cfallin, @aturon, and myself:

• Instead of removing read permissions from a well-known page, Wasmtime removes read and write permissions from the Wasm instance's stack(s). This will cause the Wasm guest to fault the next time it touches the stack.
• We don't need to emit any additional loads in function prologues (as long as the function touches the stack at any point, i.e. is not a leaf function) or loop headers (as long as the loop body touches the stack at some point).
• Otherwise, we emit dead loads from the stack in the necessary places (function prologue and loop headers). Note that this is still an improvement over what was described in the OP, which required chained loads through the vmctx.
• We need to be careful about when we are touching the Wasm stack from host code, for example when capturing a Wasm backtrace, and set a flag somewhere that means "we are running host code" that the signal handler can see and use to cooperate with the host code. In general there are a lot of potential TOCTOU bugs here between checking any flags and unmapping the stack.
  • If we unmap the stack and host code execution trips the signal handler, then in the signal handler we can set a interrupt-requested-during-host-code flag in the vmctx or somewhere, remap the stack, and then setcontext to the trapping host code and continue. Every call/return from host code to Wasm would check whether an interrupt was requested during the host code's execution and raise a trap or whatever as appropriate.

Compared to the current epoch system, this gets us faster Wasm execution at the cost of making interruption more expensive. Given that the performance trade offs are different, it may make sense to support both, rather than replace epochs with this proposed virtual memory system.

[posborne]

This question probably stems from a degree of naivety, but I'm wondering why, with appropriate guards in place, it would be preferred to have a trap be caused by accessing stack memory over just having a signal be raised on the thread executing guest code (e.g. using tkill on linux).

In either case, I think we need some synchronization around guest entry/exit to indicate "we are running host code" which would seem like it might be enough to guard against inadvertently guard against having the signal handler go off while in host code (but maybe not).

If that approach was feasible, it seems like it would potentially have a couple benefits:

1. We're able to preempt at points outside of when the guest code is touching the stack. I can't think of specific cases where this would be problematic but I'm far from being an expert here and could see this being where there are problems.
2. This would remove the need to insert dead loads or similar in leaf code that doesn't touch the stack.

This definitely seems very promising regardless given that I think most production use cases have some need for preemption to enforce timeouts and/or interact better with async schedulers, etc. I'm also curious to see if guest profiling accuracy is able to benefit from this for some workloads.

I briefly reviewed the trap handling code but am still filling in a lot of knowledge gaps.

[fitzgen]

I'm wondering why, with appropriate guards in place, it would be preferred to have a trap be caused by accessing stack memory over just having a signal be raised on the thread executing guest code (e.g. using tkill on linux).

The tricky bits here are:

1. Handling when VM or host code is running, rather than Wasm. We could probably use the same technique described in Use virtual memory tricks to make interrupt checks smaller and faster #1749 (comment) though.
2. A Wasm guest isn't pinned to a particular thread, and can migrate across different threads between polls, so we don't automatically know which thread to tkill. We could grab the thread id whenever we call into wasm, but that might add unacceptable overhead to our host-to-wasm call path. I don't have a sense of the overheads involved here.

But if these hurdles can be overcome, then this sounds pretty promising, since we won't even need compiler changes to implement this, just runtime changes.

[cfallin]

@posborne that's a great question. In general we have shied away from signal-based solutions because (i) they're not as portable (to Windows at least?), (ii) signal-handler code is (as I'm sure you know!) very limited in what it can do, and has to be careful about race conditions. That said, the underlying mechanism to catch a page fault per this issue's idea is to catch a SIGSEGV so perhaps it's not so different -- the main thing is that in the case of a munmap-based approach, we have a deterministic location we know this trap will occur, while with a signal, it may come in odd places in trampolines, etc.

I suppose the main question to answer would be: do we need signal-masking at any point to avoid race conditions when entering and leaving Wasm code; if so, that probably tips the balance away, as we want close to zero cost in the common (non-interrupting) case and syscalls on entry/exit would be fatal to that.

[cfallin]

Ah -- thread migration is an interesting case -- one needs some answer for the TOCTOU problem (I look up the tid running a guest; guest calls to host and host does an async suspend, and async executor thread goes off and does something completely different; then I send signal). I suppose signal handler registration is global to the ambient environment, so we would still catch the signal, and we would need to examine TLS and see that we're not active in Wasm (and just ignore the signal probably).

[alexcrichton]

One thing I can note is that our current signal handler is definitely not async-signal-safe. The signal handler calls test_if_trap which calls lookup_code which acquires a global rwlock. This is "mostly ok" for signals today where none of them are asynchronous and it'd only be problematic if we segfaulted in the host while holding the write lock (which is unlikely). With async signals though this is naturally unsafe since we could get a signal during the write lock for the thread holding the write lock.

I'd also second @cfallin's point ab out TOCTOU, historically I've never known how to safely construct a list of threads at any one point in time that need interruption. Coupled with the possible overhead of scheduling interruptions and synchronization around interruption it didn't seem the most appealing to me

[posborne]

Thanks for the responses, the reasoning seems solid to me, especially given that the host/guest transition is itself going to be hit pretty heavily in a lot of workloads. I did a little bit of benchmarking with epoch interrupts enabled/disabled and the savings looked very promising (was seeing between ~2-15% improvement depending on the benchmark with many being >10% improvement). Given that we should still see an improvement even if we need to emit dead loads in loop headers I'm still anticipating we could see a very respectable improvement from the optimization based on munmap.

Definitely don't want to add any significant overhead to the host/guest boundary since that's probably more relevant to a lot of real-world workloads than what we typically end up hitting with most synthetic benchmarks primarily focused on guest execution.

[erikrose]

Would someone assign this to me, please? Thanks!

[erikrose]

Here is my work in progress. I am approaching it incrementally, first using the simpler "interrupt page" (per Store, i.e. per thread) method and then, once that works end to end, replacing it with a protected stack. It will be interesting to measure the difference between them.

So far, I've added a new epoch-interruption-via-mmu option and got dead loads from the interrupt page generating in function prologues and loop headers. I'm now working on a way to trigger an interrupt (by protecting a page). Finally I'll see about the signal handler.

[alexcrichton]

We had some more discussion about this in a meeting at some point a few moons ago and forgot to update here, but @erikrose before you go too far down the implementation road I wanted to try to recall what we were talking about long ago and write it down here too.

The main concrete point I remember is that signal handlers are extremely tricky and their viability requires carefully balancing various other concerns too. As-is Wasmtime uses a sigaltstack for signals which means that it's not possible to implement interrupt checks with virtual tricks. An epoch change requires stack-switching off the wasm stack for example, and that's not possible to do from the shared resource of the sigaltstack in a signal handler. That would, for example, try to later resume to frames on the stack which have possibly been clobbered by other signals.

A possible fix for this is to remove the sigaltstack, but that removes any sort of possible indicator when a stack overflow happens (e.g. as opposed to the "you overflowed the stack" message that's printed out by the Rust standard library). This is a relatively invasive fix though because I've found such a message to be extremely useful historically. This additionally requires total knowledge of the signal handler in the process so this would likely need to be an unsafe and off-by-default option because otherwise Wasmtime is designed to play nicely with other signal handlers in the process.

Overall I'd recommend considering the signal handler side of things first rather than last because it's often the trickiest part of the system. Where possible I'd recommend doing anything nontrivial in signal handlers altogether. For example for debugging Chris is working on a Cranelift extension for breakpoints and something like that might be suitable here too. The ideal signal handler, IMO, resumes back to the wasm code, possibly with updated state, so that way the signal handler is entirely out of the picture. For example ideally the interrupt check could be a special CLIF instruction or something like that where metadata indicates how to resume it (e.g. a special stub, special ABI, etc). That way when an interrupt happens due to a fault the wasm code would be resumed, at a different location, and the new location would be the one that actually does the suspension.