Repository navigation
How Deterministic Simulation Works
This page is the theory behind Hairspring, written for a developer who has never met deterministic simulation testing. It starts with why concurrency bugs are hard to reproduce, explains how controlling scheduling and time fixes that, and then looks at how Hairspring's Linux backend does it for real programs using Hermit. It ends with an honest list of what is and is not deterministic.
Every new term is defined where it first appears. The Glossary has them all in one place.
A thread is one line of execution inside a program; a program with several threads can do several things at once. The operating system's scheduler decides which thread runs on which CPU, and for how long. It can stop a running thread at almost any instruction to let another one run. That interruption is called preemption, and the stretch a thread runs before being preempted is its timeslice.
The order in which the instructions of different threads end up running is called an interleaving. Most interleavings are harmless. A few are not.
Take the classic lost update. Two threads each add one to a shared counter. "Add one" is really three steps: read the value, add one, write it back. If the scheduler happens to switch threads between the read and the write, one update is lost:
sequenceDiagram
participant A as Thread A
participant M as counter (memory)
participant B as Thread B
A->>M: read counter (0)
Note over A,B: scheduler preempts A here
B->>M: read counter (0)
B->>M: write 1
Note over A,B: A resumes
A->>M: write 1
Note over M: two increments, but the counter is 1
The repository's C language fixture has exactly this kind of planted race: in buggy mode, its property
c.counter_exact (the final counter equals 4,000) can fail.
Why is this hard to test?
- The bad interleaving is rare. The switch has to land in a window a few instructions wide. On most runs it does not.
- You do not control it. The scheduler's choices depend on machine load, other processes, CPU caches, interrupts and timing you cannot see or set.
- Running again does not help. The next run takes a different interleaving. The repository's measurements on a 4-thread racy C program found that 100 native runs were "essentially every run different".
Threads are not the only source of this. Anything whose order or value comes from outside your code adds the same problem: the clock, random numbers, the network, files. Hairspring's architecture document lists exactly these as the things a deterministic target must route through the runtime: "time, randomness, scheduling, network, files".
If the trouble is that the outside world makes choices you cannot see, the fix is to take those choices away from the outside world. A controller makes every choice instead: which thread runs next, when it is preempted, what time the clock says, which message is delivered first. And it makes them from a seed, a number that starts a pseudo-random sequence.
flowchart LR
S1[seed 1] --> E[controller makes<br/>every choice]
S2[seed 2] --> E
S3[seed 3] --> E
E --> I1[interleaving X]
E --> I2[interleaving Y]
E --> I3[interleaving Z]
Two consequences follow:
- Exploration. Different seeds give different interleavings, so running many seeds tries many interleavings on purpose rather than by luck.
- Replay. The same seed gives the same interleaving. A failing seed is a recipe for the failure.
The program becomes a function of its seed, as far as ordering goes. That is what "deterministic" means here: same inputs (including the seed), same execution.
Hairspring offers three backends, which take control at different levels. The repository's determinism document describes them as three levels:
| Level | Meaning | Result recorded in the repository |
|---|---|---|
| 1. Simulation | Code written against Hairspring's runtime gives the same result for the same seed | Verified on macOS arm64 and Linux x86-64: identical trace hashes and identical exploration statistics |
| 2. WASM | A guest program using the host-provided choose/rand/fail imports |
Verified: the golden trace hash recorded on macOS arm64 is identical on Linux x86-64 |
| 3. System | An unmodified Linux program, scheduled deterministically | Verified on Intel bare metal with Hermit. Not possible on macOS |
You model your system as a state machine in Rust. The model says which actions are possible next (enabled), what
state results from one (apply), and whether the current state breaks the rule (violated). There are no real
threads: Hairspring picks the next action itself.
Because the whole state is ordinary data, copying it is a snapshot. The explorer keeps a collection of states that
looked new (by an abstract signature you provide) and branches from the least-visited ones, rather than always
restarting from the beginning. On one toy target the repository measured this as about 3.5 times fewer steps than
restarting from scratch (median 235 against 814 steps over 300 trials), and is clear that "your system will differ".
Failing paths are recorded as lists of stable action ids and shrunk by delta debugging, a method that repeatedly removes parts of the failing path and keeps any shorter path that still fails the same way.
Your code runs as a WebAssembly module. Whenever it needs a decision it calls the host's choose(n), and the sequence
of answers is the trace. Shrinking deletes decisions while the same kind of failure persists. WebAssembly is a good
sandbox for this: the backend canonicalises NaN values (so floating-point results do not vary), meters execution with
fuel, and limits memory.
Here you change nothing. You hand Hairspring an ordinary Linux program, with real threads and sockets, and Hairspring runs it under Hermit. The rest of this page is mostly about this level, because it is the least obvious.
Hermit is a deterministic-execution tool for Linux created at Meta (BSD-3-Clause, Copyright Meta Platforms, Inc. and affiliates). Hairspring builds against the maintained fork at rrnewton/hermit; its installer builds a pinned commit of a fork of that fork with a small backport patch. Hermit is not part of Hairspring: you install it separately, Hairspring runs it as an external command, and no Hermit source code is in Hairspring's repository or binaries. Hairspring's process backend would not exist without it.
The repository's showcase pages summarise Hermit in one sentence: it "runs a Linux x86-64 program one thread at a time under a seeded scheduler with virtual time". Taking that apart:
- One thread at a time. Hermit takes over scheduling from the operating system. Only one guest thread runs at any moment, and Hermit decides which. It does this by tracing the program (the quick start notes "Hermit traces the program", which is why the kernel's ptrace restrictions matter when you install it).
-
A seeded scheduler. Which thread runs next, and how long it runs, is decided by a pseudo-random sequence started
from
--sched-seed. Hairspring passes a different seed for each trial. -
Virtual time. The guest does not see the real clock. Hairspring starts every run at a fixed epoch (it passes
--epochto Hermit), and the time the program reads comes from Hermit, not from the wall clock. So "what time is it?" gets the same answer on every run with the same seed.
flowchart TD
H[Hairspring trial<br/>seed N] -->|hermit run --sched-seed=N ... -- your program| R[Hermit]
R --> P[pick next thread<br/>from seeded sequence]
P --> X[run that thread for one timeslice<br/>counted in retired branches]
X --> Q{program finished?}
Q -- no --> P
Q -- yes --> V[exit status + output + guest events]
V --> J[Hairspring judges the trial]
To stop a thread at the same point on every run, Hermit cannot use real time: real time varies from run to run. Instead it counts something that depends only on the code the thread executes. The showcase pages say Hermit's timeslices are "measured in retired conditional branches":
- A conditional branch is an instruction where the CPU chooses between two paths, like the jump at the end of an
ifor a loop. - Retired means the instruction actually completed (modern CPUs start some instructions speculatively and throw them away; those do not count).
- The count comes from the CPU's performance monitoring unit (PMU), hardware that counts events such as retired
branches. The quick start puts it plainly: "Hermit counts hardware events to schedule threads deterministically."
This is why the
processbackend needs hardware performance counters: bare metal, or a virtual machine that passes them through.
The same code with the same inputs retires the same branches, so "preempt after this many branches" lands at the same instruction each time. That is what makes a schedule repeatable.
The target's settings choose the strategy. From the starter configuration that hairspring init writes:
- the default is seeded random scheduling (
heuristic = "random"); -
chaos = truerandomises thread priorities each timeslice, and the starter file notes that races inside a few instructions "need a short timeslice with chaos mode, not the random heuristic"; -
max_timeslice_nssets the longest timeslice (smaller finds finer races, costs more); -
skid_marginsets a safety margin for the counter (see below).
The showcases describe chaos mode as ending timeslices "at random points, measured in retired conditional branches" and giving threads random priorities. Ending slices at random points is what gives a seed the chance to preempt a thread inside a narrow window like the lost update above.
Performance-counter interrupts do not always arrive at exactly the instruction requested; they can land slightly late.
This is called skid. If a preemption lands late, the schedule is no longer the one the seed describes, and replay
would silently stop matching. When skid_margin is set, Hairspring also asks Hermit to panic on an overshoot, so the
problem is loud rather than silent. Hairspring reports such a trial as an infrastructure failure, not as a verdict on
your program. Limits-and-Honesty describes how this shows up in practice.
The repository measured this on a 4-thread racy C program, on Intel bare metal:
| Test | Result |
|---|---|
| Native, 100 runs | essentially every run different |
| Hermit (maintained fork), 100 runs | 100/100 identical |
Hermit, 20 seeds with --sched-heuristic=random
|
8 distinct interleavings; each seed gave the same result in 5 of 5 runs |
So under Hermit, one seed gives one behaviour, and different seeds give different behaviours.
A record/replay tool such as rr records one real execution and can play it back exactly. The repository measured
rr too: 30 of 30 record-then-replay pairs were exact. But rr cannot steer or branch, so the determinism document
calls it "a debugger, not an exploration engine". Hermit's seeded scheduler does both jobs: seeds explore, and a failing
seed replays.
When a trial fails, Hairspring writes a bundle. For the process backend, the architecture document describes it as
"the seed plus the pinned environment".
Why the environment? Because, as the next section shows, the machine itself is an input. The bundle records fields such as the kernel release, CPU model, a hash of the CPU feature list, hashes of the dynamic loader cache, libc and the dynamic loader, whether it ran in a container, the Hermit executable's hash and version, the names (not values) of the guest's environment variables, and the target program's hash. No path, host name or user name is stored.
On replay, Hairspring compares those fields with the current machine:
- if anything differs it warns, naming the fields, and still runs;
- if a loader hash differs it refuses (exit 2), because the schedule itself is unreliable; you can override with
--allow-environment-change; - if the replay does not fail on a changed machine, the exit code is 3: inconclusive, "not evidence the bug is fixed".
This is the most important section for using Hairspring well.
Deterministic, as measured in the repository:
-
simandwasmtargets give the same trace for the same seed, across macOS arm64 and Linux x86-64. - Under Hermit, on the measured setups, the same seed with the same flags gave identical results run after run.
Not deterministic, or not guaranteed:
- The host is part of the program. Hermit's guest can see host files and the environment, and results depend on their contents. The repository found this the hard way: a Python program's first run under Hermit after a native run differed, because Python rewrote its cached bytecode files. The backend now starts programs from a minimal pinned environment and freezes Python's bytecode caches, but "other mutable host state (caches, config) can still change results".
-
A package upgrade can change the schedule. In one case recorded in the repository, a package install regenerated
/etc/ld.so.cache, the same seed then ran a different number of loader branches, and old recordings stopped replaying. This is why loader hashes are recorded and a change refuses replay. - A different machine or Hermit build is a different schedule. The quick start says: "If you move from one machine to another, expect to record again." A rebuilt Hermit is not expected to have the same hash, and bundles record it.
-
Instrumentation changes the schedule. Adding an SDK or turning on logging changes what the program does at the
system-call level. The showcases label SDK builds
instrumentedfor this reason, and a target with Hermit logging enabled cannot be confirmed. - macOS has no system-level determinism. There is no supported path. Apple Silicon cannot run Hermit, and Hermit is x86-64 Linux only. macOS gets levels 1 and 2.
- Ordinary cloud VMs were not tested. Only bare metal was. Many VMs and containers do not expose the performance counters.
- Skid overshoot can stop a run (see above).
Two tools help:
-
hairspring doctor <target>runs seeded walks twice and compares a per-step hash, reporting the first divergence. The README notes the doctor is probabilistic for in-process leaks (for example, iteration order of a hash map), so check several seeds. Running it in CI is recommended in the architecture document. -
hairspring doctor --process-backendreports whether a Linux machine can run theprocessbackend at all: Hermit found, hardware counters available, ptrace restrictions, kernel, and loader files.
For a failure you intend to rely on, use the confirmation pipeline described in Sweeps-and-Confirmation.
- docs/determinism.md: the measurements in full.
- docs/architecture.md: the three exploration models and the determinism contract.
- Hermit and its maintained fork rrnewton/hermit.
Understand
- What-is-Hairspring
- Concepts-and-Vocabulary
- How-Deterministic-Simulation-Works
- Sweeps-and-Confirmation
- Limits-and-Honesty
Use
- Installation
- Your-First-Run
- Running-Your-Own-Software
- Guest-SDKs-by-Language
- Examples-Overview
- Hairspring-in-CI
- Operate-a-Server
- Upgrading-and-Versions
- Troubleshooting
Reference