rr

Low overhead recording and replay of applications (trees of processes and threads).

Record nondeterministic inputs, replay deterministically.

Offline debugging: record intermittent test failures "at scale" online, debug the recordings offline at leisure.

Deterministic debugging: record nondeterministic failure once, replay deterministically forever.

Omniscient debugging: step backwards in time; issue queries over program state changes.

rr record prog --args
→saves recording to trace/

rr replay trace/
→debugger socket drives replay

Most of an application's execution is deterministic.

rr records the nondeterministic parts.

Examples of nondeterministic inputs

clock_gettime(...&now);
read(fd, buf, 4096);
__asm__("rdtsc")
ioctl(...)
UNIX signals...

Then during replay, emulate system calls and rdtsc 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.

Scheduling tasks

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 of x.

Simulate task preemption with HPC interrupts.

Idea: program insns-retired counter to interrupt after k ^✱. That k approximates a time slice.

Replaying preemption

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.

Basic requirements

x86 userspace (x86-64 kernel OK)
linux with "precise event-based sampling" (PEBS; perf events) support: >= 3.0
(optional) linux with seccomp-bpf support: >= 3.5

rr touches low-level details of machine architecture, by necessity; f.e. kernel syscall ABI.

Supporting more ISAs is "just work"; expect x86-64 soon.

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 region".
(So replay point is technically indeterminate. But doesn't seem to be a problem in practice, yet.)

seccomp-bpf enables rr to selectively trace syscalls.

Trace traps are slow; only trap to rr for syscalls that can't be handled in the tracee.

seccomp-bpf support is technically optional...

... but rr can record over 100x faster with syscall buffering enabled.

Tasks are controlled through the ptrace API.

HPCs are controlled through the perf event API.

The first traced task is forked from rr. After that, clone() and fork()from tracees add new tasks.

And tasks die at exit().

Simplified recorder loop

    while live_task():
        task t = schedule()
        if not status_changed(t):
            resume_execution(t)
        handle_event(t)

Scheduling a task

    task schedule():
        for each task t, round-robin:
            if is_runnable(t)
               or status_changed(t):
                return t
        tid = waitpid(ANY_CHILD_TASK)
        return task_map[tid]

Tasks changing status

    bool status_changed(task t):
        # Non-blocking
        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 syscall.^†

Multiple running tasks are nondeterministic

TODO EXAMPLE RACE, SYSCALL DIVERGENCE

Resuming a task, simplified

    void resume_execution(task t):
        ptrace(PTRACE_SYSCALL, t.tid)
        waitpid(t.tid)  # Blocking

    # Again, deceptively simple: traps
    # for syscalls, signals, ptrace
    # events ...

Most recorder work is done for handle_event(task t).

But before looking at it, a few digressions ...

Generating time-slice interrupts

perf_event_open() fd for retired-conditional-branches; details are microarch specific
Set event "sample period" to k
Make event fd O_ASYNC and set tracee task as owner
→ tracee sent SIGIO 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 and insn is emulated

Tracees generate ptrace events by executing fork, clone, exit, and some other syscalls.

ptrace events exist for linux reasons that aren't interesting.

(rr tracees can share memory mappings with other processes.

Nondeterministic input that must be recorded, but for now, assume "don't do that".)

Tracee events seen by `handle_event()`

"Pseudo"-signal delivered by implementation of rdtsc or time-slice interrupts
Other, "real", signals
ptrace events
Syscall entry and exit

Some syscalls must be executed atomically; can't switch task until syscall finishes.

TODO mmap example

On the other hand, some syscalls require switching; syscall can't finish until the task switches.

TODO waitpid example

Delivering unhandled signals

TODO

^†This breaks the rr scheduling invariant.

ptrace traps are expensive. Do as much work in tracee process as possible.

Use seccomp-bpf to selectively trap syscalls.

LD_PRELOAD a lib that wraps libc functions.

Wrapper functions record kernel return value and outparam data to the syscall buffer.

Upside: works "out of the box"; no recompilation necessary.

Downside: Exposes rr to glibc internals. And rr can't wrap syscalls made by glibc itself.

Untraced syscalls are recorded to syscallbuf by tracee. Traced events recorded by the rr process "flush" the tracee's syscallbuf.

Lib falls back on traced syscalls.

Simplified example of wrapper function

int close(int fd)
{
   long ret;
   if (!start_buffer_syscall(SYS_close))
     /* Fall back on traced syscall. */
     return syscall(SYS_close, fd);
   /* Buffer this close() call. */
   ret = untraced_syscall1(SYS_close, fd);
   return commit_syscall(SYS_close, ret);
}

How untraced syscalls are made

Create single "untraced" kernel entry point

asm("_untraced_syscall:\n\t"
    "int $0x80");

Install filter that passes calls from _untraced_syscall, traps to rr otherwise.

Trace directory contents

TODO
arg_env
trace
mmaps
raw_data
syscall_input

Emulate most syscalls using trace data.

Actually execute a small number.

Built around PTRACE_SYSEMU

TODO show difference from PTRACE_SYSCALL

Replaying time-slice interrupts, in practice

TODOCompare register files to approximate exact execution point
TODOSet a breakpoint on target $ip to avoid single-stepping

(gdb) set i 10 can cause replay divergence.

So you're not allowed to do it.

SIGTRAP, SIGTRAP, SIGTRAP; breakpoints, int3, stepi

TODOdistinguishing causes of traps

Port, port, port

TODO

ARM
GPU drivers (NVIDIA, ATI, ...)
Windows NT kernel
Darwin kernel

How rr works

Why?

Overview

Examples of nondeterministic inputs

Scheduling tasks

Hardware performance counters (HPCs)

Replaying preemption

System requirements

Basic requirements

✱Performance counters are messier in reality

Buffer syscalls; flush buffer as "super event"

No ASLR or ptrace hardening

Recorder implementation

Simplified recorder loop

Scheduling a task

Tasks changing status

Resuming task execution

Multiple running tasks are nondeterministic

Resuming a task, simplified

Generating time-slice interrupts

Trapping tracees at rdtsc

Tracee events seen by handle_event()

handle_event() structure

Non-nestable events

Scratch buffers for blocking syscalls

POSIX signals 101

Linux signals 202

Recording signal delivery

Finishing signal handlers

Delivering unhandled signals

Syscall buffer

Simplified example of wrapper function

How untraced syscalls are made

resume_execution changes for PTRACE_SECCOMP events

Syscallbuf wrappers of blocking syscalls

perf events to the rescue: "descheduled" event

Handling "desched notifications"

Saved traces

Trace directory contents

Replayer implementation

Built around PTRACE_SYSEMU

Main loop overview

Replaying time-slice interrupts, in theory

Replaying time-slice interrupts, in practice

Delivering signals

Replaying buffered syscalls

Debugger interface

Light wrapper around gdb protocol

Replayer core passes through to ptrace requests of tracee

SIGTRAP, SIGTRAP, SIGTRAP; breakpoints, int3, stepi

Future work

Roadmap for near future

Checkpointing

Omniscient debugging

Exploratory scheduling; targeted recording

Copy traces across machines

Record shared memory mappings

Record ptrace API

Port, port, port

Thanks from the rr team!

^✱Performance counters are messier in reality

Tracee events seen by `handle_event()`