Serve the non-blocking futex shapes from EL1

[alanhc]

Summary

Issue #292 established that futex is 56.4% of the guest syscalls in the
sampled corpus. What that ranking cannot say is how many of those calls
actually block. A FUTEX_WAIT that returns EAGAIN because the word already
moved, and a FUTEX_WAKE that finds no waiter, both cost a full HVC round trip
today and neither needs anything the host knows.

I instrumented sys_futex to find out, and would like direction before writing
any EL1 assembly.

What the instrumentation shows

A host-side matrix counting every futex call by (command, outcome), gated on an
env var and dumped at exit. Across five runs of tests/bench-futex-pingpong
(70k - 76k futex calls per run):

shape	share of all futex calls
untimed FUTEX_WAIT returning EAGAIN	40.5% - 45.9%
FUTEX_WAKE returning 0	10.4% - 24.8%
combined	~60%

The two trade off against one another across runs, which is what a ping-pong
should do. This is a microbenchmark, not a workload - I am not claiming the
ratio holds for a JVM. If there is a reproducible recipe for the corpus behind
#292, I am happy to run it and report real numbers before anything else is
decided.

This is not ELFUSE_STARTUP_TRACE=syscalls in a different shape.
src/debug/syscall-hist.c freezes at the first execve and is keyed by
syscall number alone, so it answers which syscalls dominate linker bring-up.
This asks what shape the futex traffic of a steady-state run has.

Candidate A: answer a value-compare miss at EL1

futex_wait() (src/runtime/futex.c:668) takes the bucket lock, loads the
guest word, and returns -EAGAIN when it does not match.

futex_os_sync_wait() (:501) - the path plain FUTEX_WAIT actually takes on
macOS 14.4 and later - already makes that same check with no bucket lock at
all: a plain futex_word_load and an early -EAGAIN.

So the tree already treats a mismatch as safe to answer lock-free, and it is.
The bucket lock orders the enqueue against a concurrent wake, but the futex
word is guest memory that another guest thread stores to without holding it. A
mismatch means a waker already moved the word, so no wakeup can be lost and the
caller's userspace loop re-checks. Moving that check to EL1 is not a new
invariant, only an earlier place to make it.

The mechanics already exist in src/core/shim.S:

• the SVC fast-path dispatch at :441-452
• the at s1e0w / PAR_EL1 translation probe at :558 (a futex read needs
  only s1e0r)
• handle_el1_data_abort_recover at :970, which turns a fault inside a named
  code range into -EFAULT instead of halting the VM

so the shape is cmp x10, #98 plus a body modeled on urandom_read_fast.

Bails to HVC on: any command outside FUTEX_WAIT / FUTEX_WAIT_BITSET, a zero
bitset, unaligned uaddr, a set attention bit, and a failed AT probe. The
EINVAL cases (zero bitset, unaligned address) and the EFAULT case (probe
failure) stay on the host so their ordering against the rest is untouched; the
attention bit is the gate every existing fast path already honors.

The one real problem. Both wait paths build the deadline before checking
the word, so an invalid timespec combined with a mismatched word currently
returns EINVAL/EFAULT, not EAGAIN. Linux orders it the same way, since
get_timespec64 runs at syscall entry. Preserving that from EL1 means either:

1. bail whenever the timeout argument is non-zero - simple and obviously
   correct, but it gives up the timed waits, which is where parkNanos,
   sem_timedwait and pthread_cond_timedwait live; or
2. validate the guest timespec at EL1 too, so the ordering is preserved and
   the timed waits stay eligible - more EL1 code, and a second guest structure
   to probe.

Q1: which of those two do you want? My instrumentation splits timed from
untimed rows precisely so this can be decided on numbers rather than taste.

Candidate B: answer a wake with no waiter at EL1

Larger, and it needs host bookkeeping that does not exist yet.

Waiters live in two places. futex_wake() (:879) walks the hash bucket, then
futex_wake_topup_osync() (:656) drains the Darwin queue. The second has no
count at all - futex_os_sync_wake_n() (:464) simply calls
os_sync_wake_by_address_any and watches for a negative return. So EL1 has
nothing to consult today.

A host-published occupancy bitmap in shim_data, indexed by a hash of uaddr,
would give it one. SHIM_URANDOM_OFF_BITMAP (src/core/shim-globals.h:137) is
the existing precedent for exactly this shape of host-maintained summary.

Two things make it harder than the urandom bitmap:

• Ordering is load-bearing. A false positive costs one wasted HVC. A false
  negative is a lost wakeup and a hang. The waiter must publish its bit before
  re-reading the word, and the waker must dmb ish after storing the word and
  before reading the bitmap - the usual store-buffer pattern.
• Both queues must be covered. futex_os_sync_wait() bypasses the bucket
  entirely, so it needs to maintain the bitmap too, on a path that is currently
  free of that bookkeeping.

futex_hash() (:174) spreads over 64 buckets, which is probably too coarse
here - a bitmap over it would read as occupied nearly always under a thread
pool. The right width depends on how many distinct futex addresses are live at
once, which the instrumentation does not record today. I can add that if the
direction is worth pursuing.

Q2: is a host-published waiter bitmap in shim_data an acceptable direction
at all, or does the added invariant on the wait paths outweigh the round trips
it saves?

What is not proposed

Blocking at EL1. The shim has no scheduler, so a wait that must sleep has to
leave. Only the calls that were never going to block are in scope. LOCK_PI,
REQUEUE, CMP_REQUEUE and WAKE_OP stay on the host path.

Sequencing, and #307

Candidate A touches the shim.S dispatch and Candidate B touches the
shim_data layout - both of which #307 is currently rewriting. I would rather
not create that conflict.

Proposed order:

1. the measurement patch alone: host-side only, no shim.S, no shim_data,
   zero conflict surface with mmap/munmap EL1 fastpath #307. It is also independently useful - "which
   futex shapes does this run have" is a question worth being able to ask
   whether or not a fast path ever lands.
2. Candidate A, after mmap/munmap EL1 fastpath #307 settles.
3. Candidate B, only if the answer to Q2 is yes.

Q3: is step 1 welcome as its own PR? It is written and passing locally
(make check minus the test-hello lane, which needs a toolchain I cannot
install on this machine). It is +866/-32 across 11 files, but 766 of those
lines are three new files - src/runtime/futex-stats.c, its header, and a host
unit test; the change to existing code is small. I can open it whenever.