eta_sched (eta v0.1.0)
Copy MarkdownA serializing scheduler for BEAM processes — Phase 0 of the DST framework
(design: docs/design.md).
Runs exactly one process at a time, to quiescence, so the interleaving of a concurrent system is determined entirely by this scheduler's sequence of choices. A seeded choice sequence therefore replays bit-for-bit.
This module is system-agnostic: it knows about pids, mailboxes, and scheduling, and nothing about what the processes do. A replicated process registry was its first consumer, not its subject.
Why controlling who runs is enough
It is tempting to think a deterministic scheduler must intercept every message to control delivery order. It does not. Erlang already guarantees FIFO between an ordered pair of processes, so once only one process runs at a time, the global order of message delivery follows from the order in which senders were stepped. Controlling scheduling alone determinises the whole system, which is what makes this approach tractable without rewriting the code under test.
Quiescence, and why the naive check is wrong
A process has finished its step when it is blocked on a receive it cannot
satisfy. The obvious test — status waiting and an empty mailbox — is wrong, and
wrong in a way that matters: a process blocked in
receive {reply, Ref, V} -> V endwith a non-matching message queued is waiting with a non-empty mailbox. That
is not an edge case; it is what every gen_server:call/3 does. Treating it as
runnable makes the scheduler spin on a process that can never progress, and makes
"no runnable process" — the termination condition — unreachable.
The two questions are separated properly:
- Quiescent?
waitingis definitive: the process is blocked in a receive. Detected fromrunningtrace events, not by polling. Checking status straight aftererlang:resume_process/1is a trap — a blocked process still readswaitingbefore it has been scheduled in, so the step would conclude without the process ever running.inis awaited first, as proof it got the CPU. - Runnable? Has messages, and is not known to be blocked at this exact mailbox
state. A
receiveblocks only after failing to match every queued message, so after any step the remaining mailbox is known not to match; the process is recorded as blocked at that queue length and skipped until the queue grows. Selective receive is then handled by construction, and the skip is self-correcting: a new non-matching message costs one wasted step and re-arms the block.
Measuring progress
Consumption is computed from the queue-length delta, corrected for messages the process sent to itself (nothing else runs, so those are the only arrivals).
The 'receive' trace flag cannot be used for this, which is worth stating because
the opposite is the natural assumption: it fires when a receive scans a message,
matching or not, so a non-matching message produces a 'receive' event and stays
in the queue.
The scheduler owns its own process and mailbox
It runs as a gen_server and is the tracer for every process it owns, so trace
events land in its mailbox rather than the driver's.
That was not always so, and the reason it changed is worth keeping. Phase 0 ran
the scheduler in the calling process, on the argument that a scheduler process
would itself need scheduling — which is false: nothing under test ever calls the
scheduler, so it is never part of the system being serialized. The cost of the
original arrangement was a whole class of bug that only discipline prevented. An
early version used a catch-all receive while awaiting trace events, which
consumed and discarded whatever the system under test had sent the driver — a
gen_server reply, vanishing, with its caller exiting :normal. Every receive
here still matches trace-shaped messages only, but that is now a tidiness
property rather than the only thing standing between the framework and a
mystifying failure.
It also matters for the driver. A eta_run-style helper that waits on a
predicate has to interleave stepping with checks on the system under test, so it
needs a mailbox the scheduler is not also reading.
sched() is a handle, not a value
The API threads a sched() through, and every function that took one still
returns one, so call sites read as they always did. It now names a process rather
than carrying state, and the value returned is the same handle rather than an
updated copy.
This removes a false affordance rather than adding one. The old record was never
usable as a value: the scheduler's real state is the suspend/resume status of live
OS processes, so holding on to an earlier sched() and stepping it again was
never going to replay anything — the processes had already moved.
release/1 ends the scheduler's life, so inspect (choices/1, stats/1) before
releasing, not after.
Determinism boundary
Timers. A process blocked in
receive ... after Nwakes on the real clock unless its module declares-eta_after(true)alongsideeta_transform, which puts the timeout on the virtual clock. Without it, a system under test must avoid real-time-dependent receives (useinfinityin simulation).Spawn races. A child spawned with a plain
erlang:spawnis adopted viaset_on_spawntracing, which reports the spawn after the child exists — so it runs briefly, on the real scheduler, before it is suspended.stats/1'sadopted_latecounts these.spawn/1and friends close the window by starting the child blocked;eta_transformpoints a transformed module's spawns there, so a system under simulation should showadopted_lateat or near zero. A run with a high count is a run whose interleaving is partly wall-clock.Steps that never finished. A step ends when the process blocks in a receive. If no scheduling event arrives for it at all, the scheduler eventually suspends it wherever it happens to be, and that suspension point was chosen by wall clock rather than by the schedule.
stats/1'stimeoutscounts these and a warning is logged for each. It should be 0; anything else means the run is not replayable.The wait is deliberately generous and condition-based rather than a deadline — the scheduler keeps waiting while the process is alive and not suspended, since the event is then in flight. Only a process that is dead, or that did not resume at all, ends a step this way in practice.
Cold code. A process that reaches a module it has not loaded yet makes a synchronous call into
code_server, which this scheduler does not own. From here that is indistinguishable from a process blocked in a receive, so if it is the last thing standing the run ends at what looks exactly like quiescence, having done a fraction of the work, and reports success.stats/1'scold_codenames the processes caught doing it and the line each was on; it should be[], and the fix iseta_run:preload/1.
This documentation is LLM-generated. See the AI disclosure in README.md.
Summary
Functions
Whether a scheduler is running in this VM. When false, spawn/1 and friends are
plain erlang spawns.
The choice sequence, oldest first. Feed to replay/2.
The scheduler running in this VM, or undefined.
Every known process id, ascending. Ids are assigned in registration order, or
taken from the trace when one is driving — see pin/2.
Starts a scheduler and returns a handle to it. seed fixes the choice sequence.
The scheduler's pid. For tests that need to assert on the process itself.
Hands the scheduler the ids to give the next processes it adopts.
Whether ids come from the trace (true) or from the counter (false, the
default).
Every known process, by id.
Takes ownership of a pid (or a list of them): suspends it and begins tracing it.
register/2 and take_adopted/1, in one round trip.
Resumes every process, stops tracing, and shuts the scheduler down.
Replays a recorded choice sequence exactly, ignoring the RNG.
Steps processes, choosing from the seeded RNG, until nothing is runnable or
MaxSteps is reached.
run/2 with an idle callback — the discrete-event loop.
Ids that have work to do: a non-empty mailbox they are not known to be blocked against. See the module doc on selective receive.
erlang:spawn/1 for a system under simulation: the child starts blocked and
runs only once the scheduler owns it.
gen_server:start_monitor/3 for a system under simulation: the child is gated, so
the scheduler owns it before it runs a line of init/1.
gen_statem:start_link/3 for a system under simulation — the gen_statem half
of start_link/3, on the same terms and for the same reasons.
Run statistics: steps taken, processes known, how many have exited, how many children were adopted after they had already started running, how many steps ended without the process reaching a receive, and any process caught waiting on the code server at the moment a run gave up.
Runs one process until it blocks, then suspends it again.
step/2 and take_adopted/1, in one round trip. See register_adopting/2.
The process the scheduler is stepping right now, or undefined between steps.
The ids adopted since the last call, oldest first, and clears the record.
Types
-type id() :: non_neg_integer() | {fresh, non_neg_integer()}.
-type outcome() :: progress | no_progress | exited.
-opaque sched()
Functions
-spec active() -> boolean().
Whether a scheduler is running in this VM. When false, spawn/1 and friends are
plain erlang spawns.
The choice sequence, oldest first. Feed to replay/2.
-spec current() -> sched() | undefined.
The scheduler running in this VM, or undefined.
For code that is handed no sched() and still has to ask the scheduler something —
in practice, an invariant asking whether the system is quiescent. A property
that only holds once the system has stopped moving (a registry's replicas agree
only after speculation settles) is otherwise unstateable: check/1 receives
the system under test, not the schedule, so it cannot tell "diverged" from "still
in flight" on its own.
Safe to call from an invariant. The scheduler is never part of the system it
serializes, so it is not suspended, and runnable/1 is a read.
Every known process id, ascending. Ids are assigned in registration order, or
taken from the trace when one is driving — see pin/2.
-spec new() -> sched().
A fresh scheduler with the default seed. See new/1.
Starts a scheduler and returns a handle to it. seed fixes the choice sequence.
Linked to the caller, so a driver that dies takes the scheduler with it — and with it every suspend it holds, which lets the system under test run free rather than leaving it frozen for the rest of the VM's life.
The scheduler's pid. For tests that need to assert on the process itself.
Hands the scheduler the ids to give the next processes it adopts.
Ids are otherwise assigned by counting, and a counter is positional: it makes an
id mean "the Nth process this run created", so deleting the operation that created
the third one renumbers every process after it. That is survivable in a run and
fatal in a shrink, where eta_shrink deletes entries and replays what is left —
the surviving {step, Id} entries stop naming what they named, the replay skips
them, and the shrinker concludes the deletion mattered when all that happened was
arithmetic.
So a replay does not recount. eta_run records, on each trace entry, the ids that
entry created, and hands them back here before replaying it. An id then means
"the process the trace called 7", which no deletion elsewhere can change.
Ids is consumed in adoption order and is not an obligation: leftovers are
discarded when the entry closes, which is what removing an operation looks like
from here — the processes it would have created never arrive, and nothing else
moves. An entry that creates nobody therefore need not call this at all; the
supply is already empty.
Only meaningful under pin_mode/2; a generating run has nothing to pin.
Whether ids come from the trace (true) or from the counter (false, the
default).
The mode is per run rather than per entry because an entry that pins nothing is
ambiguous on its own: it means "this one created nobody" in a recorded trace and
"this trace predates pinning" in one that has no id information at all. eta_run
decides once, by looking at the trace it was given.
Under true, a process adopted with nothing left to pin gets a {fresh, _} id
rather than the next integer, so it cannot collide with an id a later entry is
still going to hand out.
Every known process, by id.
Ids are what a trace records and pids are what a caller recognises, so anything
that wants to say something about a recorded step needs this mapping. eta_run
uses it to turn {step, 7} into a name at teardown.
Includes processes that have exited, because a trace can name one.
Takes ownership of a pid (or a list of them): suspends it and begins tracing it.
Register every process before any of them is allowed to run, or the run starts from a state this scheduler did not choose.
register/2 and take_adopted/1, in one round trip.
Two calls are not two calls' worth of latency here, they are two drains: the
second waits behind every trace event the first one's work produced, which is time
the caller spent doing nothing, and how much of it depends on how many processes
the system has. The driver asks this after every operation and step_adopting/2
after every step, so a trace costs one round trip per entry rather than two.
-spec release(sched()) -> ok.
Resumes every process, stops tracing, and shuts the scheduler down.
The system runs freely again. Inspect (choices/1, stats/1) before calling
this — the handle is dead afterwards.
Replays a recorded choice sequence exactly, ignoring the RNG.
A choice naming a process that is not currently runnable is a divergence — the run did not follow the same path — and is reported rather than skipped, because silently continuing would produce a "replay" that is not one.
Steps up to 10000 times. See run/2.
-spec run(sched(), non_neg_integer()) -> sched().
Steps processes, choosing from the seeded RNG, until nothing is runnable or
MaxSteps is reached.
choices/1 then gives the sequence to replay.
-spec run(sched(), non_neg_integer(), fun(() -> boolean())) -> sched().
run/2 with an idle callback — the discrete-event loop.
OnIdle is invoked only when nothing is runnable, and returns whether it
created new work. That is the hook virtual time plugs into:
eta_sched:run(Sched, MaxSteps, fun eta_time:advance_to_next/0)so the clock jumps straight to the next deadline once the current instant has nothing left to do, and the run ends when neither processes nor timers have anything pending. Time therefore advances in jumps between events rather than in ticks, and never while work remains at the current instant — which is both what makes the ordering deterministic and why waiting out a long timeout is free.
The scheduler deliberately knows nothing about time: it asks "is there more work?"
and the caller decides what that means. An idle callback that returns true
counts against MaxSteps, so a callback that always says yes terminates rather
than spinning.
OnIdle runs in the scheduler's process, not the caller's. eta_time is ETS
and callable from anywhere, so the usual callback is unaffected; a callback that
wants the driver's mailbox is not, and should not be one.
Ids that have work to do: a non-empty mailbox they are not known to be blocked against. See the module doc on selective receive.
erlang:spawn/1 for a system under simulation: the child starts blocked and
runs only once the scheduler owns it.
set_on_spawn tracing adopts a child after the fact, which is not the same thing
and is not enough. Between the spawn and the scheduler handling the trace event the
child runs on the real scheduler, so anything it does in that window is ordered by
wall clock rather than by the schedule. Porting a distributed registry measured the
cost: 1212 of a run's 1233 processes were adopted late, because that system spawns a
short-lived helper for almost every operation — and a seed consequently did not
reproduce its own schedule.
Gating closes it. The child blocks on a token before running anything, so there is
no window; the scheduler suspends it, adopts it, and sends the token, after which it
is runnable and stepped like anything else. stats/1's adopted_late then counts
only genuinely ungated children.
The child is spawned by MFA rather than as a fun so that the spawn trace event
carries {eta_sched, gated, _} — that is how the scheduler tells a gated child from
one it must chase. gated_plib and statem_gated are recognised the same way;
adding a gated entry point means adding it to is_gated/1 and to handle_trace/2
as well, or its children wait on a token nobody sends.
Inert with no scheduler running, exactly as eta_time is with no clock, so a
transformed module behaves normally outside a simulation.
-spec start_monitor(module(), term(), list()) -> {ok, {pid(), reference()}} | ignore | {error, term()}.
gen_server:start_monitor/3 for a system under simulation: the child is gated, so
the scheduler owns it before it runs a line of init/1.
Why this exists rather than a shadowed proc_lib
The child of a gen_server:start_* is spawned inside OTP —
gen:do_spawn/5 calls proc_lib:start_monitor/5, which calls
erlang:spawn_opt(proc_lib, init_p, …). No transform of the system under test
reaches that, so its children are adopted late and the run stops being replayable.
On that registry it was one child per group commit, and that alone was enough to
make a seed produce a different schedule each time.
The obvious fix is to shadow proc_lib with a transformed copy. It is worse than
it sounds:
- stdlib is sticky. Loading a replacement fails with
sticky_directory; it takes a deliberatecode:unstick_dir/1on stdlib's ebin first. - The blast radius is the VM. Every OTP process start goes through
proc_lib, including ExUnit's and Logger's. With a deliberately broken copy loaded,Agent.start_link/1fails immediately withundef. - It is 1600 lines of copied OTP that must track releases, and a mismatch is a subtle breakage rather than a loud one.
So the child is built rather than intercepted. A gated process sets up the two
process-dictionary entries init_p/3 in proc_lib would have set, runs init/1
itself, acknowledges, and then becomes the gen_server through
gen_server:enter_loop/3. Verified to produce a genuine OTP process: sys:get_state/1,
sys:get_status/1 and sys:suspend/1 all work on it, and $initial_call reads
as it should.
What it covers, and what it refuses
init/1 returning {ok, State}, {ok, State, {continue, C}} — including a
continue chaining into another, which enter_loop/3 does not do for you —
{stop, Reason} and ignore. Anything else raises rather than guessing: this is
a stand-in for a start path, and a stand-in that silently mishandles a shape is
worse than one that stops.
A start timeout in Options is ignored. Waiting on one would be a real-clock
dependency in the middle of a simulated run, which is the thing the framework
exists to remove, and no caller seen so far passes one.
Inert with no scheduler running: delegates straight to gen_server.
-spec statem_start_monitor(module(), term(), list()) -> {ok, {pid(), reference()}} | ignore | {error, term()}.
gen_statem:start_link/3 for a system under simulation — the gen_statem half
of start_link/3, on the same terms and for the same reasons.
The child is gated identically: it waits for the scheduler's token, sets the two
process-dictionary entries proc_lib would have set, registers its name, runs
init/1 itself, acknowledges, and then becomes the state machine through
gen_statem:enter_loop/6 — which is the same enter/8 gen_statem's own
init_it/6 converges on, so the callback mode is read and the initial state
enter call is made exactly as in a real start.
init/1 returning {ok, State, Data} and {ok, State, Data, Actions} is
covered, along with {stop, Reason} and ignore. Anything else raises rather
than being guessed at.
Inert with no scheduler running: delegates straight to gen_statem.
Run statistics: steps taken, processes known, how many have exited, how many children were adopted after they had already started running, how many steps ended without the process reaching a receive, and any process caught waiting on the code server at the moment a run gave up.
adopted_late, timeouts and cold_code are all determinism failures, and
should read 0, 0 and []. See the module doc's determinism boundary.
cold_code is a list of cold/0 — the process, and the frame in the system
under test that reached a module it had not loaded yet:
#{cold_code := [#{id := 3, pid := Pid, at := {my_client, commit, 2}}]} =
eta_sched:stats(Sched).A non-empty list means the run's quiescence was a lie: at least one process was
about to be woken by the code server rather than by anything the schedule chose,
so a run that ended here ended early and everything after this point is wall
clock. The fix is eta_run:preload/1, and at names the application to give
it. See note_cold_code/1.
Runs one process until it blocks, then suspends it again.
Returns progress (it consumed at least one message), no_progress (it blocked
without consuming — a selective receive that matched nothing), or exited.
step/2 and take_adopted/1, in one round trip. See register_adopting/2.
-spec stepping() -> pid() | undefined.
The process the scheduler is stepping right now, or undefined between steps.
Exactly one process runs during a step — every other one the scheduler owns is suspended — so this is the sharpest available statement of "on the schedule". A side effect caused by any other process while this is set happened at a moment wall-clock timing chose, not one the seed did.
undefined is not the opposite of that. Between steps the driver itself is
running, and a harness injecting an operation there is doing something the trace
records; nothing is off-schedule merely because no step is in progress.
Read out of band, from ETS, because the answer is wanted by processes that could
not ask for it: the scheduler is a gen_server and a call into it from inside a
step would deadlock against the step.
The ids adopted since the last call, oldest first, and clears the record.
This is the recording half of pin/2: what a run writes into its trace so that a
later replay can give the same processes the same names. Reading it takes it,
because the question is always "since when" and the answer is always "since I last
asked".