nordisk/heimdall

Prepared graph follower benchmarks

This benchmark tests transition work per event, rather than selecting a table because its total size fits a cache. Immutable tables are shared; each thread owns a bounded cursor, including its signal frames. Ordinary calls allocate nothing and take no shared lock. The existing seccomp floor is still required for syscall permissions, arguments and architecture checks.

The code is in heimdall-graph: tables_for_lanes prepares deterministic states for individual thread entries as well as the existing union for an unidentified child; minimize optionally merges equivalent futures; prepared offers four layouts. An identified lane requires a trusted assignment by the runtime. The library does not identify a thread's role from a thread name or workload tag.

For executable graphs, machine::compile explores only reachable (entry, positions, last-call) frames and folds the last call into the state id. machine::Runner therefore stores one number per signal frame. Its dfa-words layout uses four-byte destinations indexed by state and raw syscall number; dfa-offsets precomputes row offsets, and dfa-compact maps syscall columns. The dfa-min-* variants merge states with equivalent futures before preparation. All keep independent thread cursors and shared immutable tables.

The legacy minimizer checks both next and again. An absent ordinary transition denies; an absent repeated-call transition retains the current position. It preserves entry starts and signal metadata and keeps the original last syscall number in each cursor. It uses conservative partition refinement, not history truncation. Long chains may make this offline algorithm expensive. Minimization and row sharing are optional, not automatic performance choices.

minimize::coalesce optionally merges equivalent syscall sites before determinization. Its equivalence includes syscall labels, thread-entry membership and successors; it preserves per-entry first sites and retains an original-site map. This can reduce the intermediate graph, but it does not remove the general exponential worst case of subset construction.

Run from the repository root on x86_64 Linux:

bench/graph-lookup/measure.sh /tmp/graph-results

CARGO_TARGET_DIR selects the build cache. GRAPH_BENCH_CPU (default 4) pins lookup replay; GRAPH_WORKLOAD_CPUS (default 4-21) limits the cooperative workload. Use CPU ids available on the machine. GRAPH_BENCH_CALLS (2,000,000), GRAPH_BENCH_SAMPLES (7), GRAPH_WORKLOAD_ITERS (50,000), and GRAPH_WORKLOAD_THREADS (1,4,16) control run length. Threads counts are foreground workers, plus one collector. Avoid concurrent builds while measuring. Environment, CPU pressure, compiler, binary digests, raw CSV and a JSON summary are retained. Results directories are never overwritten.

lookup_bench imports the checked-in Mímir abcdf and real broker graphs using their computed SHA-256 pins. It constructs traces by walking the graph sites independently of the transition tables. Terminal paths explicitly reset the cursor. Synthetic cases use state-dependent permissions and compare a small recurring region with the full state range in tables of 64, 4,096 and 32,768 states. Their traces also include invalid calls. Every layout must produce the same rejection count. Two alternating calls connect every synthetic state; hot traces omit those calls, leaving a reachable cold region. An example test checks that path and runs in ordinary cargo test through test = true in the package manifest. Minimized variants are measured separately. Preparation time is outside the timed loop and reported separately. payload_bytes excludes metadata, allocator overhead and preparation's temporary allocations; hash memory is unmeasured. The default preparation payload budget is 256 MiB and can be overridden through Prepared::with_limit; it is a resource bound, not a cache target. The hash comparison is against the existing complete Rust follower, including its vector cursor and event dispatch. Comparisons among prepared layouts share the same fixed cursor and call path, isolating their storage choices more closely.

External executable syscall graphs can be measured with:

bench/graph-lookup/measure.sh /tmp/external-results program.exec.nodes.arrow program.exec.edges.arrow

This consumes the existing Mímir executable syscall projection, not raw C/MIR/ASM function graphs. The C graph producer must supply that projection upstream. A legacy compiler budget failure removes only that comparison; the reachable state compiler is measured if it fits. A missing hash baseline produces a null speedup, never an invented comparison. Unmapped C functions or an oversized reachable machine are reported as refusals; they are never made permissive to obtain a benchmark number. An external refusal exits with status 1. GRAPH_BENCH_COALESCE=1 enables the optional graph-site pass. GRAPH_BENCH_MAX_ENTRIES and GRAPH_BENCH_BYTES allow explicitly budgeted larger offline experiments. Runtime storage limits must still be checked after minimization; the default construction and runtime paths retain their existing limits. Raising a construction budget does not guarantee success.

lane_workload performs real 4 KiB pread and /dev/null writes from a prepared 1 MiB file, with a collector alternating getrusage and sched_yield. Each selected syscall has an explicit check before its libc wrapper. Each thread has its own cursor and assigned entry, sharing the same tables. A checksum and exact operation counts verify that all variants perform the same foreground work. Thread creation and file setup are outside timing; barrier release and joins are included. The input is page-cache resident and writes go to /dev/null: this measures a syscall-heavy loop, not disk throughput. The collector performs an identical fixed operation count in each variant.

One warmup batch is retained as sample 0 and excluded from summaries. Layout order rotates between samples. Ranges and medians describe batch averages, not p99 individual-call latency. A spread above 25% is flagged as noisy. Wall time divided by concurrent call counts is not single-call latency.

The cooperative workload graph is supplied by construction for its measured loops. Both legacy and minimized state-only runners execute the same work. It is not the Mímir-derived graph of its executable. Startup, scheduler, signals and shutdown are not intercepted. Neither benchmark installs a filter or proves security enforcement. Kernel follower cost and host-wide idle cost remain unmeasured. Kernel tests belong in throwaway VMs, not host containers. Replay already has the thread's cursor, and cooperative workers own theirs directly. Thread-id lookup, kernel map helpers, hook invocation and event delivery are not included in these lookup timings.

The integration target is youki's SeccompBackend trait, already implemented by runtime/heimdall-youki. That backend compiles the static floor; it does not attach a graph follower. This work adds a Rust runtime model without changing that contract. Current real youki shim graphs remain refused for unmapped C functions; those refusals must remain intact until the graph producer resolves them.

Oden measurements, 2026-11-08

Raw samples, environment, preparation logs, binary digests and summaries are in results/oden-20261108-replay (commit 4e50e7d) and results/oden-20261108-lanes (commit 9b3694d). The latter adds state-only variants to the concurrent workload. Both use the commands and defaults above: seven measured batches after warmup, pinned replay on CPU 4, workload CPUs 4–21, rustc 1.99.0, AMD Threadripper PRO 3975WX. Oden was shared with other work, including CI in a VM restricted to CPUs 0–3 and 22–31. CPU pinning does not isolate memory bandwidth or scheduling noise. These are observed batch averages, not a deployment latency guarantee.

Representative replay results from oden-20261108-lanes:

The broker executable graph has 101 imported sites. Import plus reachable-frame construction took 9.51 ms, yielding 544 states and 13,304 transitions. The legacy construction exceeded its 1,048,576-transition budget, so there is no broker hash speedup comparison. Minimization reduced the machine to 178 states. In the prior run, broker offsets measured 3.190 ns/event before minimization and 3.193 after it. The smaller payload did not materially change that trace's lookup cost. The same-size hot/broad synthetic results also show why total table size alone is not a useful optimization target. Access pattern and dependent operations matter.

The abcdf hash comparison includes the old follower's vector cursor and event dispatch. It measures the whole Rust follower replacement, not hash lookup alone. The state-only offsets implementation currently retains eight-byte cells from the legacy layout; words uses four-byte destinations. A smaller cell is not assumed faster: the measured offset layout avoids a per-event row multiplication.

Concurrent workload results were noisy. Each foreground worker performed 50,000 reads and 50,000 writes; one collector performed 50,000 getrusage/yield pairs. All variants matched the expected byte count and checksum.

Every row above exceeds the 25% spread threshold. In particular, checked runs appearing faster than unchecked runs do not establish a throughput improvement. The workload verifies that shared immutable tables and independent role cursors operate under concurrent real I/O; it does not resolve small end-to-end overheads on this shared host. Replay and workload samples remain available without filtering out unfavorable batches.

The youki shim fixtures still fail import because of unmapped C code. The benchmark regression test preserves that refusal. The existing SeccompBackend adapter remains the floor integration point; a graph follower cannot be attached there or assigned trusted thread roles by this library alone. No youki graph enforcement or kernel-hook performance is claimed by these results.