rr records nondeterministic executions and debugs them
Practical tool; version 1.2 is latest release. Used to debug
Deterministic debugging: record nondeterministic failure once,
debug deterministically forever.
Record intermittent test failures "at scale" online, debug the
recordings offline at leisure.
Omniscient debugging: issue queries over program state changes;
go backwards in time.
rr record prog --args
→debugger socket drives
replay of most recent recording
Most of an application's execution is deterministic.
rr records the nondeterministic parts.
Examples of nondeterministic inputs
- UNIX signals...
Then during replay, emulate system calls and
by writing the saved nondeterministic data back to the tracee.
Shared-memory multitasking is a nondeterministic "input".
... but modern hardware can't record it efficiently. So rr
doesn't record truly parallel executions.
Can switch tasks at syscalls. Must preempt straight-line code
too; and replay the preemptions deterministically.
Hardware performance counters (HPCs)
Recent chips count instructions-retired, branches-retired,
..., and can be programmed to interrupt after a count
Simulate task preemption with HPC interrupts.
Idea: program insns-retired counter to interrupt
after k ✱. That k approximates
a time slice.
Record the insn-retired counter value v to the trace file.
During replay, program the interrupt for v. Voilà.
UNIX signals are recorded and replayed like task preemptions.
Record counter value v and signum. Replay by interrupting
after v and "delivering" signum.
- Intel chip with Nehalem (2010) or later µarch1. VM
with perf counter virtualization is OK.
- x86 userspace. x86-64 kernel is OK.
- linux with
PTRACE_INTERRUPT support: ≥
- (strongly encouraged) linux with seccomp-bpf support:
rr touches low-level details of machine architecture, by
necessity; f.e. kernel syscall ABI.
Supporting more ISAs is "just work". x86-64 coming.
ARM chips don't have the performance counters that rr requires.
So no ARM support is possible at the moment.
Precise HPC events identify points in execution.
Precise replay of signals and preemption requires interrupting
tracees at these events.
✱Performance counters are messier in reality
- Insns-retired counter is imprecise. Use precise
retired-branch counter instead.
- Counter interrupts can overshoot. Subtract a "skid
- (So replay point is technically indeterminate. But
doesn't seem to be a problem in practice, yet.)
seccomp-bpf enables rr to selectively trace
Only trap to rr for syscalls that can't be handled in the tracee.
Over 100x faster in µbenchmarks.
Buffer syscalls; flush buffer as "super event"
Tasks are controlled through the ptrace API.
HPCs are controlled through the perf event API.
The first traced task is forked from rr. After
add new tasks.
And tasks die at
Simplified recorder loop
task t = schedule()
if not status_changed(t):
Scheduling a task
for each task t, round-robin:
tid = waitpid(ANY_CHILD_TASK)
Tasks changing status
bool status_changed(task t):
return waitpid(t.tid, WNOHANG)
# Deceptively simple: includes
# syscalls, signals, ptrace
# events ...
Resuming task execution
Invariant: At most one task is running userspace code.
All other tasks are either idle or awaiting completion of a
Multiple running tasks suffer from shared-memory
rr doesn't attempt to record these hazards, so can't replay them
Resuming a task, simplified
void resume_execution(task t):
waitpid(t.tid) # Blocking
# Again, deceptively simple: traps
# for syscalls, signals, ptrace
# events ...
Most recorder work is done
But before looking at it, a few digressions ...
Generating time-slice interrupts
perf_event_open() fd for
retired-conditional-branches; details are µarch
- Set event "sample period" to k
- Make event fd O_ASYNC and set tracee task as owner
- → tracee sent SIGSTKFLT at rbc ≈ k
Trapping tracees at rdtsc
prctl(PR_SET_TSC, PR_TSC_SIGSEGV) → tracees
executing rdtsc trap to SIGSEGV
- rr examines which instruction triggered SIGSEGV
- if rdtsc, value is recorded by rr tracer and tracee insn is
Tracees generate ptrace events by executing fork, clone, exit,
and some other syscalls.
ptrace events exist for linux reasons that aren't
(rr tracees can share memory mappings with other processes.
Not possible to record efficiently in SW; needs kernel and/or HW
support. Unsupported until then.)
Tracee events recorded
- "Pseudo"-signals delivered by implementation of rdtsc or
- Other, "real", signals
- ptrace events
- Syscall entry and exit
Some syscalls must be executed atomically; can't switch task
until syscall finishes.
mmap modifies address space, can race other
On the other hand, some syscalls require switching;
syscall can't finish until the task switches.
waitpid() only returns after child runs, changes
Problem: kernel writes non-atomic syscall outparams in
an order that rr can't record.
Kernel outparam writes race rr tracees in userspace, syscalls.
Solution: allocate scratch space for the outparams of
non-atomic syscalls. At syscall exit, write scratch data back to
→ rr orders outparam writes
POSIX signals can arrive at practically any point in execution
and invoke signal handler code.
→ tracee code can be (almost) arbitrarily
Linux exits tracees out of syscalls with
ERESTART* error code before delivering signals.
Syscall not always restarted after signal.
When a signal becomes pending
- consult sighandler table to see if there's a registered
- if so,
SINGLESTEP into the sighandler frame and
struct sigframe set up by kernel. Also
record sighandler registers.
- otherwise, deliver the signal using the ptrace API
Sighandlers exit using the
rr uses these calls to help determine whether interrupted syscalls
Tracees exit in unpredictable order at fatal signals like
waitpid() calls deadlock.
exit_group: same problem.
"Unstable" tracee exit
rr solves this by detaching and not waiting on affected tracees.
†Breaks rr scheduling invariant.
ptrace traps are expensive. Better to do as much work in tracee
process as possible.
Use seccomp-bpf to selectively trap syscalls.
Syscall hooks are
LD_PRELOAD'd into tracees.
Hook functions record kernel return value and outparam data to
the syscall buffer.
__kernel_vsyscall() in vdso to jump
to rr trampoline.
Trampoline calls dispatcher, which calls rr hook if
Untraced syscalls are recorded to syscallbuf by tracee.
Traced events recorded by the rr process "flush" the
Lib falls back on traced syscalls.
Simplified example of syscallbuf hook function
static int sys_close(int fd)
/* Fall back on traced syscall.
* This generates a ptrace trap. */
return syscall(SYS_close, fd);
/* Untraced syscall. Does not generate
* ptrace trap.*/
ret = untraced_syscall1(SYS_close, fd);
/* Save the result to syscall buffer. */
return commit_syscall(SYS_close, ret);
How untraced syscalls are made
seccomp-bpf traps generate
rr can then
PTRACE_SYSCALL the tracee into traced
Problem: buffered syscalls don't trap to rr, by design.
But may-block syscalls (f.e.
waitpid()) require rr to
schedule another task.
perf events to the rescue: "descheduled" event
Set event to fire on tracee context switch. Event traps to rr.
Buffered syscall blocks → context switch → rr
Generating desched events
- In tracee,
perf_event_open() fd for
- Set event "sample period" to
1 (i.e. next context
switch) just before buffered syscall
- Disarm event just after buffered syscall.
- → tracee sent SIGSYS if context switched during
Traces are saved to
~/.rr by default.
Stored on disk uncompressed. Trace compression is planned.
Trace directory contents
args_env: command-line args and environment
pairs used to
execvpe() initial tracee
events: sequence of syscalls, signals, and
various other execution events
mmaps: metadata about mmap'd files
data_header: all recorded data,
along with metadata about when it was recorded
version: trace format version number
Emulate most syscalls using trace data.
Actually execute a small number.
Built around PTRACE_SYSEMU
SYSCALL runs tracee to syscall, executes it.
SYSEMU runs to syscall, doesn't execute it.
rr replays side effects.
Replaying time-slice interrupts, in theory
Program instructions counter to interrupt after the
recorded t number of instructions.
Tracee stops at t.
Replaying time-slice interrupts, in practice
- have to use retired-conditional-branch counter (RBC)
- RBC interrupts aren't precise. Can overshoot by up to 70
- RBC counter value doesn't uniquely identify a point in
execution (unlike retired-insn counter value)
Finding execution target, in practice
- program RBC interrupt for target-rbc - SKID_SIZE
- after RBC interrupt, set breakpoint on target
to avoid single-stepping when possible
- when breakpoint hit, compare RBC value and register files to
guess if at execution target. If RBC and regs match what was
To reiterate, this is not sound.
Deterministic signals were raised by program execution. For
*NULL = 42;
Replayed "naturally" in the course of execution.
Async signals were raised externally at some execution point
Replay to that execution point just as for time-slice
Replay signal delivery by emulating
If there was a sighandler, restore recorded
and registers at sighandler entry.
Otherwise, nothing else to do.
Replaying buffered syscalls
Read saved buffer from trace.
Replay each syscall as normal, but restore outparam data from
records in the read buffer.
Common commands supported.
c, s, si, b, bt, watch, info regs, thr, info thr ...
(gdb) call foo() can cause replay divergence.
So you're not allowed to do it … for now. Support coming.
Small stub translates from and to gdb remote protocol.
Then passes debugger requests up to rr replayer.
Replayer fulfills requests using
ptrace() or cached
And resumes tracee execution when asked.
$ip, breakpoint table, gdb request,
$DR6 decode trap.
Make a "deep fork" of tracee tree during replay.
Run code (or whatever) in copied tree, return to original.
instrumentation to generate execution DB.
Query state changes in DB.
execution search; targeted recording
At each scheduling decision, make a checkpoint.
If execution reaches bad state, done. Else, resume checkpoint.
- Copy traces across machines
- Integrate hardware shared-memory multithreading recorder
- Record ptrace API;
rr record rr record…
- Handle GPU drivers (NVIDIA, ATI, ...)
- Port to Darwin kernel
- Port to Windows NT kernel
ARM port not possible with current generation of chips
Appendix: rr for RnR people
- Run on modern, commodity hardware and software:
install rr; rr record…
- Aspire to general tool, focus on Firefox initially
- Record nondeterministic test failures at scale (e.g., Firefox
build/test infra), debug offline
- "Super-debugger" for local development
- Search execution space to actively find bugs
- Commodity HW → only record single HW thread (for
- Commodity SW → stick to higher-level userspace APIs
(e.g., ptrace, PEBS)
- Record tests at scale → record perf must be "economical",
but not mission-critical
- "Super-debugger" → the usual, plus queries over execution
history; pretty fast replay
- Search exe space → flexible scheduling and
rr recorder overview
- Record "applications" consisting of linux tasks
- Schedule CPU slices by programming precise counter interrupt
(retired branches, RBC) for k
- Time slice is special case of signal: time-slice recorded as
(0, rec-RBC), signals (signum, rec-RBC)
- Record kernel-created signal stack
- Syscall "outparams" and
rdtsc generate trace
traps; results saved to log
- Plus a "faster" mode we'll cover later
Trade-off: scheduling from userspace
- While it's great to fully control scheduling ...
- ... we have to approximate timeslices; can be unfair
- ... interactive programs don't "feel" native; rr has its own
- ... can be slower
- Future work is to have the option of both
Headache: kernel writes racing with userspace
- rr doesn't (can't efficiently) record reads/writes of memory
shared outside of tracee application.
- But there are still hazards with the kernel:
- ... kernel-write/task-read hazard on syscall outparam buffers
→ rr replaces user buffers with scratch and serializes
- ... kernel-write/task-read on random futexes,
e.g. CLONE_CHILD_CLEARTID → no good solution yet;
rr replayer overview
- Replay signal/time-slice (signum, rec-RBC) by
programming interrupt for rec-RBC
- Emulate signals by restoring signal stack and regs
- Emulate syscalls by restoring outparams where possible
- Execute non-emulatable clone/mmap/et al. as required
- Serve debugger requests (maybe covered later)
Replayer headache: slack in counter interrupts
- Interrupt programmed for RBC = k may actually fire at
up to RBC = k + slack
- (Slack empirically seen to be >= 70 branches)
- So we program interrupt for RBC = k - slack and then
advance by breakpoint+stepi
- "At target" when rec-RBC == rep-RBC and [rec-regs]
- Replay target therefore technically indeterminate
Recorder "fast mode": syscall buffering
- ptrace traps are slow
- Idea: avoid them when possible by buffering log data
in tracee task
- Implementation: LD_PRELOAD a helper library with hooks for
common syscalls (read, write, gettimeofday, etc.)
- Hook makes fast untraced syscall, saves outparams in
- Flush buffer at traced event (including buffer overflow)
Headache: many syscalls made internally in glibc
- Those syscalls can't be wrapped by usual approach of
interposing exported symbol using LD_PRELOAD
- Solution: monkeypatch
- Syscalls directly made through
int $0x80 still
can't be buffered.
- We hope this terrible hack evolves into kernel support.
Headache: buffering syscalls that may block
- read/write/… may block if buffer empty/full/…
- But, untraced syscall from wrapper means no trap to
rr for scheduling arbitration
- If another tracee is blocked too, then may deadlock
- Solution: libc wrapper programs perf_event interrupt triggered
by next context-switch of task
- If the syscall blocks, task is switched out, and rr tracer
gets interrupt (SIGIO from perf_event)
Fun debugging tricks
- Save register / RBC info at all events, verify in replay
- Generate memory checksums at selected events, verify in
- LLVM pass to add "execution path logging" (Bell-Larus): poor
man's log of retired branches. Save to "magic fd" in recording,
verify in replay.
- Hack replayer itself to efficiently log arbitrary info at