rr Captured Linux Program Runs for Deterministic Replay, Trading Multicore Speed to Trace Elusive Bugs Backward

By March 2014, Mozilla developers including Robert O’Callahan had released version 1.0 of rr, an open-source tool built around a deliberate constraint: run only one application thread at a time. The tool traded multicore speed for the ability to record a Linux program’s execution once and replay the same failure deterministically as many times as needed.

Traditional debugging workflows break down when an error depends on subtle timing differences. A race condition might trigger a crash once in several thousand test runs, but attaching a traditional debugger or inserting print statements alters execution speed, causing the bug to vanish. For decades, computer scientists sought practical record-and-replay systems to capture such transient failures. Yet earlier systems suffered from steep deployment hurdles: they demanded custom kernel patches, required full virtual machine capture, or relied on pervasive code instrumentation that added performance and implementation overhead.

The Architecture of Deterministic Replay

The Mozilla team—whose work was documented in a May 2017 technical report co-authored by O’Callahan, Chris Jones, Nathan Froyd, Kyle Huey, Albert Noll, and Nimrod Partush—designed rr to operate within strict practical constraints. It ran entirely in user space on stock Linux kernels and compatible Intel x86 processors, without kernel modifications or a hypervisor. On many distributions, however, enabling unprivileged access to the required performance events first required changing a kernel setting.

To accomplish this, rr established a strict recording boundary between user-space processes and the Linux kernel. During recording, rr captures kernel inputs such as system call return codes, memory buffer outputs, and operating system signals, together with nondeterministic effects of processor instructions such as timestamp reads. During replay, rr reproduces the recorded inputs and register states exactly, creating an identical instruction-level execution path.

The central design choice was how rr handled multithreaded applications. On multicore processors, unsynchronized reads and writes to shared memory generate nondeterministic data races that are exceptionally difficult to record efficiently. Rather than tracking individual memory accesses with heavy instrumentation, rr enforced a simple constraint: only one application thread runs at any given moment. By preemptively scheduling threads on a single core, rr avoided simultaneous execution on multiple cores while retaining thread interleavings, but could not expose bugs caused by weak memory models. Interleaving bugs could still be captured whenever a context switch happened to occur at a critical moment in execution.

Branch Counters and In-Process Interception

Deterministic replay also required precise timing for asynchronous events such as timer signals and context switches. Delivering a signal during replay even one instruction before or after its recorded point could cause the entire execution to diverge. Yet retired-instruction counters on the x86 processors examined were not deterministic: for example, an instruction restarted after a page fault could be counted twice. Modern Intel processors, however, provide a deterministic performance counter: retired conditional branches (RCB). rr paired the RCB count with general-purpose registers and some stack data to identify execution points; the authors reported that this worked robustly in practice, without claiming guaranteed uniqueness.

Supervising every system call using standard Linux ptrace operations originally incurred heavy performance penalties, requiring four context switches per system call. To make recording viable for large codebases like the Firefox web browser, rr introduced in-process system-call interception. By injecting a lightweight library into the application and using Linux seccomp-bpf system-call filters, rr allowed common, non-blocking system calls to write results directly to shared trace buffers without trapping into the supervisor process. Performance-event notifications let rr detect when an intercepted call blocked and schedule another thread, avoiding a potential deadlock; the implementation also handled spurious notifications.

Debugging Backward in Time

Because deterministic replay guarantees identical memory addresses and register values across runs, it transformed the debugging experience inside the GNU Debugger (GDB). Instead of restarting a program and hoping to land on the right breakpoint, developers could take advantage of true reverse execution.

When a program crashes on a corrupted pointer or wrong value, the symptom appears long after the erroneous write occurred. Under rr, a developer sets a hardware data watchpoint on the damaged variable and executes the reverse-continue command. The debugger travels backward through the execution history, stopping precisely at the instruction that modified the memory location. This can reduce speculative forward stepping, though the last write may itself have received an already incorrect value.

Chaos Mode: Triggering the Elusive Race

Deterministic replay has a basic limitation: a debugger can only replay a bug that has already occurred. If an intermittent defect fails to trigger during recording, replaying that passing test cannot reveal the missing failure. In February 2016, O’Callahan highlighted this limitation with a real-world concurrency bug in Firefox’s ImageBridge thread that occurred intermittently on Android devices but did not reproduce in thousands of runs under rr; an inserted pause could trigger it reliably on desktop Linux.

Triggering the bug required keeping the ImageBridge thread unscheduled while the main thread waited for a 500-millisecond timeout. Because ImageBridge was the only runnable thread during that interval, a scheduler that merely chose among runnable threads could not create the required delay. To solve this, O’Callahan introduced “chaos mode” (invoked via rr record with the -h flag). Chaos mode randomized thread priorities and time-slice lengths, periodically starving low-priority threads for intervals of up to several seconds even when no other threads were runnable. By simulating extreme scheduling pressure, chaos mode allowed rare timeout races to trigger during recording, producing traces that could then be inspected backward.

Trade-Offs and Engineering Lessons

The design of rr represents a series of conscious engineering compromises. Forcing all threads onto a single core means heavily parallel workloads experience substantial slowdowns; in the 2017 report, recording a parallel build of DynamoRIO took 7.85 times as long as baseline execution. The report’s four other workloads, including a Firefox web-form test at 1.49 times baseline, recorded at 1.49 to 1.79 times baseline.

Applications that share memory with unrecorded processes outside the process tree remain unsupported, and operating system updates occasionally require updating rr’s internal system call models. Nevertheless, the tool became the foundation for advanced debugging platforms like Pernosco and is used by developers of large systems software projects. rr illustrates a practical trade-off: sacrificing multicore execution can make a captured failure repeatable, letting developers trace backward to the modification they need to inspect.

Explore

Stay connected