# Lockstep testing methodology — the playbook
How to apply Lockstep to a real BEAM library to find (or rule out)
concurrency bugs. This is the field guide we wrote while testing
Cachex, ConCache, lud/mutex, nimble_pool, and Hammer.
The bug-finding rate so far: **1 in 5 libraries**. Hammer's
`Hammer.Atomic.FixWindow.inc/4` had a real lost-update race against
`hit/5`. The other four are concurrency-correct under their public
APIs — which is itself useful information.
This doc is the recipe for getting to that signal.
## Contents
1. [When to reach for Lockstep](#when-to-reach-for-lockstep)
2. [Two paths: compile-rewrite vs test-only dep](#two-paths-compile-rewrite-vs-test-only-dep)
3. [The model-based linearizability template](#the-model-based-linearizability-template)
4. [Writing the model](#writing-the-model)
5. [Picking a strategy](#picking-a-strategy)
6. [Iteration counts and tuning](#iteration-counts-and-tuning)
7. [Beyond linearizability: fault injection, time-skew](#beyond-linearizability-fault-injection-time-skew)
8. [What Lockstep can and cannot reach](#what-lockstep-can-and-cannot-reach)
9. [Anti-patterns](#anti-patterns)
10. [Case studies](#case-studies)
## When to reach for Lockstep
Lockstep makes sense when you're testing code where:
- Multiple processes interact through shared mutable state (ETS,
atomics, persistent_term, registered names).
- You need a *reproducible* failing schedule — vanilla concurrent
ExUnit tests find races but throw away the trace.
- You suspect a race exists at non-trivial depth (3+ scheduling
decisions away from a clear "first send wins").
It's overkill when:
- The code is sequential or has only one writer.
- You just want stress testing — `Task.async_stream` in a loop is
cheaper.
- The race is already easy to catch (tight `:erlang.spawn` loops
catch lost-updates 99% of the time, see the README's "Why bother").
## Two paths: compile-rewrite vs test-only dep
There are two ways to point Lockstep at a library, with very
different tradeoffs.
### Path A: test-only Hex dep (workers controlled, library raw)
Add the library to `mix.exs` as `only: :test`. Workers run as
`Lockstep.Task.async/1` (controlled), call into the library, and
record into `Lockstep.History`. The library itself runs un-rewritten
on the real BEAM scheduler.
You get:
- Real-world concurrent behavior of the library (real scheduler).
- Lockstep manages worker scheduling and history recording.
- Linearizability checking against your model.
You don't get:
- PCT scheduling *into* the library's GenServer mailbox dispatch.
Internal races aren't actively explored — you're hoping the BEAM
scheduler hits them naturally.
Use this when the library is too heavy to compile-rewrite (heavy
macros, many transitive deps, kernel-level features). **Cachex** and
**Phoenix.PubSub** fit here.
### Path B: compile-rewrite via `Lockstep.MixCompiler` (full pipeline)
Clone the source, run it through `Lockstep.MixCompiler.compile/1`,
and `Code.compile_file/1` the rewritten output. The library's
internal `:ets`, `:atomics`, `Process.send_after`, `GenServer.call`,
`Process.monitor`, and friends all become Lockstep sync points.
You get:
- PCT (or any other strategy) scheduling *into* the library's
internals — handle_call dispatch ordering, monitor cleanup
ordering, message arrival sequencing.
- A genuinely-stronger correctness signal: bugs at depth 3-6 inside
the SUT are findable.
You pay for it with:
- Source must be cloneable and compilable. Heavy macro libraries
(Cachex's record-style state, Hammer's `__before_compile__`)
may need partial workarounds.
- Some OTP idioms aren't reachable: `{:via, Registry, ...}` was
blocked until [we added rewriting](lib/lockstep/rewriter.ex)
for the via tuple itself; `:"$ancestors"` propagation is also
needed for libs that read `Process.get(:"$ancestors")`.
Use this when the library is small-medium (≤ 2k LOC, few transitive
deps) and you actually want to find concurrency bugs in *its* logic.
## The model-based linearizability template
The reusable shape for any read/write API:
```elixir
defmodule Lockstep.MyLibTest do
use ExUnit.Case, async: false
setup_all do
# Compile through Lockstep.MixCompiler if you want path B.
# Otherwise add the lib as a test dep and skip this.
...
end
defmodule MyModel do
@behaviour Lockstep.Model
alias Lockstep.History.Event
@impl true
def init, do: %{} # whatever shape your reference state is
@impl true
def step(state, %Event{f: :get, value: k}, %Event{type: :ok, value: v}) do
if Map.get(state, k) == v do
{:ok, state}
else
{:error, "stale read"}
end
end
def step(state, %Event{f: :put, value: {k, v}}, %Event{type: :ok}) do
{:ok, Map.put(state, k, v)}
end
# ... one clause per (op kind, completion type)
# Generic completion catch-alls (always include these):
def step(state, _, %Event{type: :fail}), do: {:ok, state}
def step(state, _, %Event{type: :info}), do: {:ok, state}
end
test "linearizability" do
Lockstep.Runner.run(
&body/0,
iterations: 200,
strategy: :pct,
max_steps: 5_000,
seed: 1,
iter_timeout: 30_000,
progress: 25,
suite: "mylib_lin"
)
end
defp body do
# 1. Set up a fresh SUT instance (unique name per iteration).
{:ok, sut} = MyLib.start_link(...)
# 2. Start a History recorder.
history = Lockstep.History.start_link!()
# 3. Spawn workers, each pulling from a Generator.
n_workers = 4
ops_per_worker = 6
workers =
for w <- 1..n_workers do
Lockstep.Task.async(fn ->
gen =
Lockstep.Generator.weighted(
[
{{:get, "k"}, 4},
{{:put, "k", w * 100}, 2},
# ... your op pool ...
],
seed: w * 1_000_003
)
|> Lockstep.Generator.take(ops_per_worker)
Lockstep.Generator.each(gen, fn op -> apply_op(history, sut, op) end)
end)
end
Lockstep.Task.await_many(workers, 30_000)
# 4. Check the history against the model.
events = Lockstep.History.events(history)
case Lockstep.Checker.Linearizable.check(events, MyModel) do
{:ok, _} -> :ok
{:error, info} ->
msg = Lockstep.Checker.Linearizable.format_violation(info)
raise "non-linearizable history found:\n\n#{msg}"
end
end
defp apply_op(history, sut, {:get, k}) do
Lockstep.History.op(history, :get, k, fn -> MyLib.get(sut, k) end)
end
defp apply_op(history, sut, {:put, k, v}) do
Lockstep.History.op(history, :put, {k, v}, fn -> MyLib.put(sut, k, v) end)
end
end
```
`Lockstep.History.op/4` records an `:invoke` before the function, an
`:ok` (with the function's return value) on normal return, or an
`:info` (with the exception message) on raise. The
`Lockstep.Checker.Linearizable` then tries to find a serial order
that's consistent with both real-time precedence and the model.
## Writing the model
A model is a sequential reference implementation. Its job is to
answer: "given the recorded operations applied in *some* serial
order, is this completion consistent?"
### One clause per (op kind, completion shape) pair
```elixir
def step(state, %Event{f: :put, value: {k, v}}, %Event{type: :ok, value: :ok}) do
{:ok, Map.put(state, k, v)}
end
def step(state, %Event{f: :insert_new, value: {k, v}}, %Event{type: :ok, value: :ok}) do
if Map.has_key?(state, k) do
{:error, "insert_new returned :ok but key already exists"}
else
{:ok, Map.put(state, k, v)}
end
end
def step(state, %Event{f: :insert_new, value: {k, _v}}, %Event{type: :ok, value: {:error, :already_exists}}) do
if Map.has_key?(state, k) do
{:ok, state}
else
{:error, "insert_new returned :already_exists but key didn't exist"}
end
end
```
Each clause encodes both branches: "what state updates if this
completion is consistent" and "what's the proof it's *not*
consistent." The Linearizability checker uses this to backtrack
through serial orderings.
### Always include the catch-alls
```elixir
def step(state, _invoke, %Event{type: :fail}), do: {:ok, state}
def step(state, _invoke, %Event{type: :info}), do: {:ok, state}
```
`:fail` is an explicit "didn't apply" — the op had no effect on
state. `:info` is an unknown outcome (the worker crashed
mid-call) — for now, treat as no-apply, which is the conservative
default. (A more sophisticated checker would branch and try both.)
### Be careful with return values
Probe the library's actual return shapes before writing the model.
We had several "compile fails" or "function clause" errors traced
back to incorrect assumptions:
- `Cachex.get/2` returns `{:ok, value}`, not `value | nil`.
- `Cachex.get_and_update/3` returns `{:commit, new_v}` directly,
*not* `{:ok, {:commit, new_v}}`.
- `Mutex.lock/2` returns `{:ok, %Mutex.Lock{}}` or `{:error, :busy}`.
- `Mutex.await/3` returns `%Mutex.Lock{}` directly (or raises).
Run a quick `mix run --eval 'IO.inspect(MyLib.foo(...))'` first.
### State scope: single-key first, multi-key second
Start with all ops on the same key. The contention is highest, the
model is simplest, and most race patterns surface there. Once that
passes, expand to multi-key — the model is just `%{key => value}`
instead of `value`.
## Picking a strategy
Lockstep ships five strategies. Rule of thumb:
| Strategy | Best at | When to skip |
|----------|---------|--------------|
| `:pct` (default) | Classic data races (lost-update, TOCTOU) at depth ≤ 3. | When you need long runs of one process picked consecutively (POS is better). |
| `:pos` | Bugs that need the strategy to consistently pick the *same* proc over many sync points (e.g., async replication patterns). | When PCT depth-bounded probability is what you need. |
| `:fair_pct` | Long-running tests where infrastructure (heartbeats, timers) would otherwise dominate. | When you need full PCT for the whole run. |
| `:idpct` | Unknown bug depth + many iterations (≥ 1000). Cycles depth in `[d_min, d_max]` per iteration. | When iteration count is small and you want predictable depth. |
| `:random` | Sanity check or cheap stress. | When you want adversarial scheduling. |
**Workflow**: start with `:pct` (default depth 3). If 200-500
iterations don't surface the bug, try `:pos`. If neither, switch to
`:idpct` and run thousands of iterations. If still nothing, the
suspected bug probably doesn't exist.
The Hammer bug was found by `:pct` at depth 3 with 5000 iterations
on a 4-worker `1 inc + 3 hit` workload. ConCache's lock manager and
nimble_pool's checkout queue have been tested to ≥100 iterations of
mixed workloads under `:pct` with no findings.
## Iteration counts and tuning
PCT's bug-finding probability per iteration is `1 / (n · k^(d-1))`
where `n` is step count, `k` is process count, `d` is bug depth.
A rough sizing table for a typical 5-worker test:
| Bug depth | Per-iter probability | Iterations for 99% confidence |
|-----------|----------------------|-------------------------------|
| 2 | ~1% | ~500 |
| 3 | ~0.05% | ~10,000 |
| 4 | ~0.0025% | ~200,000 |
In practice:
- Start at **100 iterations** during development. If your test is
flaky, fix the *test* before scaling iterations.
- Push to **1,000 iterations** for a real correctness check.
- For confidence at depth 3+, **5,000-10,000 iterations**. Each
takes ~1ms wall-time for typical workloads, so 10k is ~10s.
- If you've gone past 50,000 and still nothing, the bug almost
certainly isn't in your concurrency surface. Move on.
## Beyond linearizability: fault injection, time-skew
The Linearizability template covers ~80% of useful tests. The
remaining 20% need targeted directed tests.
### Fault injection (kill a process holding a resource)
```elixir
defp fault_body do
{:ok, mutex} = Mutex.start_link([])
parent = self()
ref = make_ref()
# Worker A: acquires the lock, signals, then exits without releasing.
Lockstep.spawn(fn ->
{:ok, _lock} = Mutex.lock(mutex, "k")
Lockstep.send(parent, {ref, :a_acquired})
# No release. fn returns → A exits :normal → :DOWN fires.
end)
Lockstep.recv_first(fn {^ref, :a_acquired} -> true; _ -> false end)
# B (us) awaits — should block until A's :DOWN, then acquire.
lock = Mutex.await(mutex, "k", :infinity)
:ok = Mutex.release(mutex, lock)
end
```
Lockstep's controller delivers `:DOWN` automatically when a managed
process exits, AND treats monitor-observed deaths as expected (no
`:bug` flag). PCT explores orderings of: A's exit, the `:DOWN`
delivery to B, B's pending `await` recv, B's retry.
### Time-skew (force a timer to fire mid-operation)
Lockstep's virtual time advances when no process is runnable.
`Lockstep.sleep/1` parks the calling process and lets virtual time
tick. Combined with aggressive timer config in the SUT (e.g.,
`expiry: 0`, `cleanup_interval: 1`), you can force timer events to
interleave with concurrent ops:
```elixir
defp time_skew_body do
# Example: a circuit-breaker style state machine with periodic cleanup.
{:ok, _} = MyBreaker.start_link(cleanup_interval: 1)
{:ok, _} = MyBreaker.register("api", max_attempts: 3, expiry: 0)
# Auto-open with 3 failures.
MyBreaker.failure("api")
MyBreaker.failure("api")
MyBreaker.failure("api")
# Concurrent: cleanup tick fires + worker does another failure.
Lockstep.spawn(fn -> MyBreaker.failure("api") end)
Lockstep.sleep(10) # advances virtual time, fires cleanup tick
# Final state must be valid (state machine consistent under interleaving).
{:ok, info} = MyBreaker.status("api")
if info.state not in [:open, :half_open], do: raise(...)
end
```
Note: `System.system_time/1` is *not* rewritten by Lockstep. Real
wall-clock time still ticks. If your library's expiry comparison
uses `System.system_time`, you need very low `expiry` values for the
comparison to fire under fast iterations.
## What Lockstep can and cannot reach
### Reaches
- All `Lockstep.*` wrapped primitives: `:ets.*`, `:atomics.*`,
`:persistent_term.*`, `GenServer.{call, cast}`, `Process.{monitor,
demonitor, send_after, link, unlink, flag, alive?}`, `spawn`,
`spawn_link`, `Lockstep.send`, `Lockstep.recv*`.
- OTP `{:via, Registry, ...}` registration (rewriter transforms the
via tuple to `Lockstep.Registry`).
- `Process.get(:"$ancestors")` / `:"$ancestors"` is propagated on
every spawn.
### Doesn't reach
- BEAM kernel messages: `:ETS-TRANSFER` (heir mechanism), `:nodedown`,
port messages. These bypass the controller's mailbox. Libraries
that depend on these (e.g., `Eternal`'s ETS HEIR) won't work
cleanly under Lockstep without additional wrapping.
- Macro-generated code in user modules. The rewriter operates on
source files passed to `Lockstep.MixCompiler`. If a library uses
`__before_compile__` to inject functions into the user's module
(Hammer does this), the user's module isn't rewritten by default.
Workaround: bypass the macro and call the underlying algorithm
modules directly (which *are* rewritten).
- `System.system_time/1`, `:erlang.system_time/1`, `:os.timestamp/0`.
Real wall-clock is real wall-clock. If a library's correctness
depends on time progression, it interacts oddly with Lockstep's
fast iteration loop.
- NIFs other than the wrapped set. If a lib calls into a custom NIF,
Lockstep treats it as opaque.
### Library-side compile quirks we've hit
- **Compile-time `File.read!("README.md")`**: nimble_pool's
`@moduledoc` reads README at compile time. Rewritten file lives in
a different cwd, so `File.read!` fails. Pre-process the rewritten
source to replace the line.
- **Macro-heavy state records**: Cachex uses Erlang record syntax via
macros. Compiling all of Cachex through Lockstep.MixCompiler is a
rabbit hole; we use Path A (test-only Hex dep) instead.
- **Compile-time `Code.ensure_loaded!`**: some libraries assert
another module is loaded at compile time. The rewritten file is
loaded fresh, so this can fail unless dependencies load first.
Order rewritten files by leaf-to-root in your `setup_all`.
## Anti-patterns
### Strict equality assertions where the API returns floats
We've seen rate-limiter smoke tests assert `{:allow, 3.0} = ...` —
which fails ~25% of the time because `(now - last) / interval *
refill` produces `3.0000001` if even a microsecond of real time
elapsed. Use `assert_in_delta` or `is_number/1` for float-shaped
returns.
### Single-iteration tests for known-deep bugs
Running with `iterations: 1` means PCT picks one schedule and stops.
That's fine for a directed test of a specific known interleaving
(e.g., shrinking output) but not for hunting unknown races. Default
to `iterations: 200` minimum.
### Ignoring `:info` completions in the model
The catch-all `def step(state, _, %Event{type: :info}), do: {:ok,
state}` treats unknown outcomes as no-applies. This is fine for
correctness (conservative), but if you want to detect bugs that
manifest *only* under crashed operations (e.g., the operation
applied but the caller never saw the response), you need to branch.
### Sharing state across iterations
If you `Cachex.start_link(:my_cache, ...)` once in `setup_all`, all
iterations write to the same cache. State leaks. Use a per-iteration
unique name: `name = String.to_atom("c_#{:erlang.unique_integer([:positive])}")`.
## Case studies
### Cachex (1.5M downloads): linearizability confirmed
Test: 200 iterations × 6 workers × 8 mixed ops + 500 iterations of
get_and_update R-M-W + 200 iterations multi-key. All linearizable.
Compiled un-rewritten (Path A) due to 5 transitive deps. Cachex's
basic ops are ETS-atomic; `get_and_update` serializes through a
per-cache locksmith Queue GenServer.
### lud/mutex: linearizability + fault-injection both pass
Test: 200 iterations linearizability on 5 workers × 4 lock/release
cycles + 100 iterations fault injection (kill holder, verify monitor
cleanup). Full pipeline. The fault test exercises the
`Process.monitor` cleanup path — Lockstep delivers `:DOWN`
automatically when a managed process exits.
### ConCache (~600k downloads): linearizability confirmed
Test: 100 iterations × 4 workers × 6 mixed ops on single key, with
PCT scheduling INTO ConCache.Lock's GenServer (the lock manager +
waiter queue + monitor-based cleanup). All linearizable. Required
two Lockstep core fixes:
1. AST rewriter handles `{:via, Registry, term}` → `{:via,
Lockstep.Registry, term}` (OTP's `:via` dispatch otherwise routes
to the real Registry which isn't started under Lockstep).
2. `Lockstep.spawn` propagates `:"$ancestors"` (ConCache.Owner reads
it via `hd(Process.get(:"$ancestors"))` to find its parent).
### nimble_pool (used by Finch, Postgrex): clean
Test: 100 iterations × 5 client tasks × 3 checkout cycles on
pool_size 2. Full pipeline. All cycles complete. Tests the
`checkout!` queueing, `Process.monitor` on clients, and worker
selection logic.
### Hammer (~rate limiter): **bug found**
Test: 4-worker `1 inc + 3 hit` workload, 5000 iterations under PCT.
Found a real lost-update race in `Hammer.Atomic.FixWindow.inc/4`:
```elixir
case :ets.lookup(table, full_key) do
[{_, atomic}] -> ...
[] ->
:ets.insert(table, {full_key, :atomics.new(2, signed: false)}) # OVERWRITES
inc(table, key, scale, increment)
end
```
`:ets.insert` overwrites whereas `hit/5` correctly uses
`:ets.insert_new`. Under interleaved hit+inc on a fresh key,
increments to the first atomic can be clobbered when the second
process's `inc` overwrites with a fresh atomic.
This was the seventh library tested with the template — the first
to surface a real concurrency bug. The other six are correctly
designed; Hammer's mismatch between hit/5 and inc/4 is an
implementation gap, not a documented design choice.
---
## Appendix: minimal test scaffolding for compile-rewrite (Path B)
```elixir
defmodule Lockstep.MyLibTest do
use ExUnit.Case, async: false
@src "/tmp/mylib"
@rewritten_dir "/tmp/mylib_lockstep"
setup_all do
cond do
not File.exists?(@src) ->
IO.puts(:stderr, "\n[mylib] skipped: clone to #{@src}")
{:ok, available: false}
true ->
File.rm_rf!(@rewritten_dir)
source_paths = [
Path.join(@src, "lib/mylib.ex")
# ... add all .ex files in dependency order
]
case Lockstep.MixCompiler.compile(%{paths: source_paths, output: @rewritten_dir}) do
{:ok, rewritten} ->
# Sort leaf-to-root to satisfy module-level deps.
ordered = Enum.sort_by(rewritten, &order_key/1)
for path <- ordered do
try do
Code.compile_file(path)
IO.puts(:stderr, "[mylib] compiled #{Path.basename(path)}")
rescue
e -> IO.puts(:stderr, "compile FAILED: #{Exception.message(e)}")
end
end
{:ok, available: Code.ensure_loaded?(MyLib)}
_ ->
{:ok, available: false}
end
end
end
defp order_key(path) do
case Path.basename(path) do
"leaf_module.ex" -> 0
"mid_module.ex" -> 1
"main_module.ex" -> 2
_ -> 99
end
end
test "lin", ctx do
if not ctx.available, do: assert(true), else: lin_test()
end
defp lin_test do
Lockstep.Runner.run(&body/0,
iterations: 200,
strategy: :pct,
max_steps: 5_000,
seed: 1,
iter_timeout: 30_000,
progress: 25,
suite: "mylib_lin"
)
end
defp body, do: ...
end
```
