Engineering Record And Replay For Deployability: Extended Technical Report

1 Introduction

• Existing approaches can require whole-VM recording, modified kernels, compiler or runtime changes, custom hardware, or pervasive instrumentation, limiting deployability.Whole-VM approaches also capture operating-system state when users may only care about particular processes.Source: §1 · p. 1
• RR targets unmodified user-space applications on stock Linux, compilers, runtimes, and x86/x86-64 CPUs, with a fully user-space implementation that needs no special privileges or pervasive instrumentation.Source: §1 · p. 1
• The system combines ptrace-based recording of system-call results and signals, single-thread-at-a-time execution to avoid nondeterministic data races, and hardware performance counters to time asynchronous events.Source: §1 · p. 2
• Less than a factor of two: RR's recording and replay slowdown on important application workloads, with low-parallelism overhead lower than other approaches with comparable deployability.Source: §1 · p. 2
• In-process system-call interception removes ptrace-induced context switches, the main performance bottleneck identified for low-parallelism workloads such as Firefox's test suite.Source: §1 · p. 2
• RR relies on hardware and OS features near the edge of feasibility and cannot be implemented on ARM CPUs; its foundation is an open-source reverse-execution debugger used with complex applications.Source: §1 · p. 2

2.1 Summary

• RR replays user-space execution by preserving memory, registers, control flow, and layout while replaying recorded system-call effects instead of reproducing most kernel state.The recording boundary is the user-space/kernel interface; replay creates corresponding threads, address spaces, and mappings.Source: §2.1 · p. 2

2.2 Avoiding Data Races

• Running one tracee thread at a time avoids races among tracee threads, but limits performance for workloads with consistently high parallelism.RR records preemptive context-switch timing; data-race bugs may be observed if a switch occurs at the right point, but weak-memory-model bugs cannot.Source: §2.2 · pp. 2–3

2.3 System Calls

• RR supervises system calls with ptrace and models which user-space memory each call can modify; scratch buffers isolate blocked-call outputs until other threads stop running.Tracee ptrace operations are emulated because Linux allows only one ptrace supervisor per thread.Source: §2.3 · p. 3, §2.3.1 · p. 3, §2.3.2 · p. 3

2.3 Performing System Calls In Tracee Context; 2.3.4 Kernel Namespaces

• RR performs needed system calls in tracee context and reserves a file descriptor to let sandboxed processes access RR-created temporary files or sockets.The reserved descriptor refers to the root directory as seen by RR; a malicious tracee could exploit this sandbox hole.Source: §2.3.3 · p. 4, §2.3.4 · p. 4

2.3.5 Seccomp

• RR accommodates seccomp-bpf by exempting its privileged tracee-context calls from filters and recording filter effects on ordinary calls through observed kernel behavior.Source: §2.3.5 · p. 4

2.3.6 System Call Modeling In Practice

• System-call memory modeling assumes user-space observations can bound modified locations, but ioctl conventions are inconsistent and keeping the syscall model current takes substantial work.RR has built-in knowledge of many ioctls, but this coverage is incomplete and must be extended for new applications.Source: §2.3.6 · p. 4

2.3.7 Replay; 2.3.8 Replaying Complex System Calls

• During replay, RR uses a temporary breakpoint to skip an intercepted system call and apply recorded changes, falling back to PTRACE_SYSEMU when writable or shared code makes breakpoints unreliable.For complex calls, RR recreates recorded mappings; for execve it rebuilds the address space to match recording.Source: §2.3.7 · pp. 4–5, §2.3.8 · p. 5

2.3.9 Signal Handlers; 2.3.10 Signal Handling And Interrupted System Calls

• RR records signal-handler frames and registers, then replays handler entry by restoring that state without delivering real signals; interrupted-call restarts are tracked with a parameter-register heuristic.The heuristic has no foolproof way to distinguish a restarted call from a new one.Source: §2.3.9 · p. 5, §2.3.10 · p. 5

2.4 Asynchronous Events

• RR treats preemptive context switches as signals and must deliver each asynchronous event when the program is in the same state as during recording.Source: §2.4 · pp. 5–6

2.4.1 Nondeterministic Performance Counters

• Modern Intel CPUs provide a deterministic retired conditional branches (RCB) counter, which RR pairs with general-purpose registers to identify replay points.The RCB count alone does not uniquely identify an execution point; repeated states can still occur in rare cases.Source: §2.4.1 · p. 6
• For reverse-execution debugging, RR augments registers and RCB counts with stack data because distinct states can otherwise share the same identifiers.The authors report this approach has appeared robust, with no new issues encountered for a couple of years.Source: §2.4.1 · p. 6

2.4.2 Alternative Approaches to Nondeterministic Counters

• RR favors the RCB approach over branch-count alternatives because those counters can include invisible hardware-interrupt activity; at the time of writing, most cloud providers did not virtualize performance counters.RR therefore did not work on most cloud providers, with Digital Ocean cited as an exception.Source: §2.4.2 · p. 6

2.4.3 Late Interrupt Firing

• Because performance-counter interrupts may arrive dozens of instructions late, RR triggers them early and repeatedly runs to a temporary breakpoint until the recorded RCB count and registers match.Source: §2.4.3 · p. 6

• RR disables shared-memory paths with PulseAudio, X, and direct GPU access, and patches vdso implementations to use real system calls instead of kernel-shared memory.The identified common cases also include writes by kernel graphics drivers and GPUs.Source: §2.5 · p. 7
• Sharing memory with other non-recorded processes can still cause problems, but the authors say this is rare and can often be addressed by recording a larger process group.Source: §2.5 · p. 7

2.6 Nondeterministic Instructions

• RR traps and records RDTSC because Linux can configure the CPU to trap this nondeterministic timestamp instruction.Source: §2.6 · p. 7
• RR patches the GNU libstdc++ use of RDRAND, which the authors had encountered in one place.Source: §2.6 · p. 7
• RR pins tracee threads to a fixed core because CPUID can expose the running core index, which can change when the kernel migrates a process.Source: §2.6 · p. 7
• The authors describe CPUID faulting as a way to mask features such as RDRAND and record exact CPU-returned values, noting Linux 4.12 had just added a user-accessible API.Source: §2.6 · p. 7

2.6.1 Transactional Instructions

• RTM exposes transaction success or failure through XBEGIN and XEND, while HLE uses XACQUIRE and XRELEASE as backward-compatible performance hints without visible semantic changes.Source: §2.6.1 · p. 7
• RR disables RTM use in the system pthreads library because transaction outcomes depend on CPU state, and plans to mask the RTM feature bit in CPUID.Source: §2.6.1 · p. 7
• HLE can make RCB counts nondeterministic, so RR counts committed-transaction events with an IN_TXCP counter while a separate counter triggers early interrupts.Linux cannot configure an IN_TXCP counter to interrupt after a specified event count because transaction rollback can produce repeated interrupts.Source: §2.6.1 · p. 7

2.7 Reducing Trace Sizes

• Hard links preserve old executable and library data when updates or recompiles replace files, avoiding copies to the trace on every execution.This approach works well in practice.Source: §2.7 · p. 8
• Copy-on-write cloning of mapped files is essentially free in time and space until the original file is modified or deleted.RR uses cloning when the mapped file and trace are on the same filesystem and that filesystem supports cloning.Source: §2.7 · p. 8
• Trace data other than cloned files and blocks is compressed with zlib deflate, although better compression algorithms exist.With these optimizations, trace storage is a non-issue in practice.Source: §2.7 · p. 8

3 In-process System-call Interception

• An injected library intercepts common system calls without ptrace traps and records their results to a shared buffer, avoiding context switches that can dwarf syscall costs.RR flushes the buffer to its trace when it receives a synchronous stop notification.Source: §3 · p. 8

3.1 Intercepting System Calls; 3.2 Selectively Trapping System Calls

• RR patches common syscall instructions to call library stubs, then uses seccomp-bpf to allow the library’s designated untraced instruction; uncommon calls retain ptrace trapping.Dynamic-linking wrappers were insufficient because applications may issue direct syscalls and vary in their library or preloading requirements.Source: §3.1 · p. 8, §3.2 · pp. 8–9

3.3 Detecting Blocked System Calls

• For potentially blocking untraced calls, perf context-switch events trigger ptrace notifications so RR can suspend the blocked thread and run another.An interrupted intercepted call is restarted and recorded through the regular traced path.Source: §3.3 · p. 9

3.4 Signal Handling; 3.5 Interrupted System Calls

• RR stashes signals during interception, blocks further delivery while one is pending, and routes untraced sigprocmask retries through traced calls; handler reentry disables the untraced fast path.This handling addresses signal-delivery edge cases and prevents reentry into interception code while a signal handler runs.Source: §3.4 · pp. 9–10, §3.5 · p. 10

3.6 Thread-Local Storage; 3.7 Stack Handling

• To handle applications with raw-clone TLS gaps, RR swaps a fixed thread-locals page on context switches; trampolines also use a scratch stack to preserve the x86-64 red zone.After a fork, RR’s thread-local values start initialized to zero; the stack switch could affect signal handlers, though this has not been a problem in practice.Source: §3.6 · p. 10, §3.7 · p. 10

3.8 Handling Replay

• Replay keeps interception-library control flow aligned: recording directs syscall outputs to trace buffers, while replay skips the call and copies recorded data to application buffers.For large in-out parameters, replay also makes the initial input-buffer copy a no-op to preserve recorded results.Source: §3.8 · pp. 10–11

3.9 Optimizing Reads With Block Cloning

• For large block-aligned reads from clone-capable filesystems, RR clones input blocks into per-thread trace files, reducing time and space overhead but leaving a read/write race.Reading from the cloned file instead would perform poorly because it defeats Linux readahead optimizations.Source: §3.9 · p. 11

3.10 Retrospective

• In-process interception is a large maintenance burden, must behave like regular syscalls and work unchanged in recording and replay, and cannot protect against malicious applications.The authors state that without interception RR could not meet its performance targets.Source: §3.10 · p. 11

4.1 Workloads

• The workloads cover file copying, parallel builds, CPU-intensive JavaScript, Firefox HTML forms tests, and Samba UDP echo tests.The benchmarks were selected to reflect strengths, weaknesses, and real-world use, and generally fit in memory and ran for about 30 seconds.Source: §4.1 · p. 11

4.2 Overhead

• Run-time results are normalized to baseline configurations, with separate tests for single-core execution, disabled interception or cloning, and DynamoRio’s null tool.Results use the geometric mean of five runs after discarding the first; they represent warm-cache performance.Source: §4.2 · p. 12, Table 1 · p. 13

4.3 Observations

• Make has significantly higher overhead than other workloads, partly because single-core execution slows it and interception misses early calls in its many short-lived processes.Make forks and execs 2,430 processes; at least 80 system calls occur before the interception library loads.Source: §4.3 · p. 12
• Excluding make, RR’s recording slowdown is less than a factor of two, and replay overhead is lower than recording overhead.Replay can be faster than normal execution in cp because system calls do less work.Source: §4.3 · p. 12, Figure 4 · p. 12
• System-call interception sharply reduces recording and replay overhead, while block cloning mainly improves cp recording.Block cloning has essentially no effect on the other workloads.Source: §4.3 · p. 12, Figure 5 · p. 12
• DynamoRio overhead is similar to RR recording on make and sambatest, low on make, and very high on htmltest.The authors expect record-and-replay built on dynamic instrumentation to add significant overhead beyond DynamoRio’s null tool.Source: §4.3 · pp. 12–13, Figure 6 · p. 13

4.4 Storage Space Usage

• Trace storage rates vary substantially by workload, but several MB/s are manageable on modern systems, and trace storage has not been a practical concern.Reported storage data cover general trace data and cloned file blocks.Source: §4.4 · p. 13, Table 2 · p. 13

4.5 Memory Usage

• RR’s memory overhead was not a practical issue in these runs, though recording increased application memory in octane and replay sharply reduced htmltest memory by omitting its harness.The workloads ran on an otherwise unloaded 16GB machine with all data fitting in cache and no memory pressure.Source: §4.5 · pp. 13–14

5.1 Hardware

• RR requires deterministic hardware performance counters; reliable counter virtualization matters, and VMware’s VM-exit clustering must be disabled because it breaks RCB-counter determinism.Hardware and OS support for trapping CPUID and other nondeterministic instructions would improve control; transaction-failure signals would enable support for hardware transactional memory.Source: §5.1 · p. 14
• ARM porting failed because load-linked/store-conditional atomic operations can fail due to unobservable activity, making progress counts nondeterministic; x86 atomic operations are deterministic in user-space state.The ARM operations are inlined across many code locations, making patching infeasible without pervasive instrumentation or compiler changes.Source: §5.1 · p. 14

5.2 Software

• RR depends on Linux features including seccomp-bpf, context-switch performance events, and copy-on-write file and block cloning APIs to reduce system-call and I/O overhead.Applications must also be configured not to share memory with processes outside the recording.Source: §5.2 · p. 14
• RR’s replay boundary is mostly the kernel–user-space interface, which suits Linux because it is stable across OS versions, documented, and allows user-space event counting.Windows’s less documented, more complex, and less stable interface would make implementation and maintenance considerably more challenging outside the OS vendor.Source: §5.2 · pp. 14–15
• RR relies on per-system-call models to identify modified user-space memory, so fewer and simpler system-call interfaces reduce the modeling work.Source: §5.2 · p. 15

6.1 Deployability and Usage

• RR is packaged by some Linux distributions and otherwise easy to build or download; it generally works unprivileged, though many distributions require enabling non-root access to a perf event.The authors identify this low barrier to entry as important for encouraging adoption.Source: §6.1 · p. 15
• The authors chose good performance on low-parallelism applications over mediocre performance across all applications, accepting high slowdown for highly parallel applications.Replay speed matters because reverse execution may replay code many times for each recording.Source: §6.1 · p. 15
• RR’s space and time overhead is mostly a non-issue for users of low-parallelism workloads, and for many users is smaller than the difference between optimized and debug builds.Reported performance problems often involve system calls without a fast interception path, RR bugs, or denied direct GPU access.Source: §6.1 · p. 15
• RR’s process-level design enables cheap checkpoints: fork-based, mostly copy-on-write creation typically takes less than ten milliseconds.Replay-only checkpoint restoration is simpler than general Linux process checkpointing because it reproduces only minimal kernel state.Source: §6.1 · p. 15

6.2 Engineering RR

• RR’s reliance on poorly documented hardware and OS features has exposed the project to difficult-to-diagnose hardware, kernel, hypervisor, and RR bugs.Source: §6.2 · p. 15
• The team uses strict consistency assertions, logging, an emergency debugger, memory checksums and checkpoints, and tests to detect and diagnose failures; understanding kernel behavior has sometimes required reading source code.The authors note that implementing a system like RR without full OS source access would be daunting.Source: §6.2 · p. 16

7.1 Whole-System Replay

• Whole-system replay records an entire VM, which can be inconvenient when applications must be moved into a VM and makes checkpoints more expensive than process-level checkpoints.ReVirt, VMware Workstation, Simics, QEMU, and Xen are cited as whole-system approaches.Source: §7.1 · p. 16

7.2 Replaying User-Space With Kernel Support

• Kernel-based systems such as Scribe, dOS, and Arnold add record-and-replay functionality to the OS, increasing maintenance and deployment difficulty unless integrated into the base OS.The authors note that invasive kernel features carry risks when user-space implementation is feasible.Source: §7.2 · p. 16

7.3 Pure User-Space Replay

• Among systems supporting asynchronous events, RR achieves lower overhead by avoiding code instrumentation; PinPlay and iDNA instrument all loads to support parallel recording with data races, at higher overhead.Earlier pure user-space systems MEC, Jockey, and liblog did not handle asynchronous event timing and other OS features.Source: §7.3 · p. 17

7.4 Higher-Level Replay

• Higher-level replay systems instrument runtimes, bytecode, or library interfaces and are narrower in scope than replaying general user-space execution.Examples include DejaVu, IntelliTrace, Chronon, Dolos, and R2.Source: §7.4 · p. 17

7.5 Parallel Replay

• Low-overhead parallel recording with data races remains challenging: existing approaches incur high overhead, constrain replay reliability, or require compiler and runtime changes.Hardware support is presented as the best hope for general, low-overhead parallel recording.Source: §7.5 · p. 17

Future Work

• Lack of virtualized hardware performance counters in major cloud providers is identified as probably the main current barrier to RR deployment.Source: §8 · p. 17
• RR does not yet well support transporting recordings between machines; widespread CPUID faulting support would make that easier to implement.Source: §8 · p. 17
• Because RR perturbs execution by forcing threads onto one core, it can miss bugs that manifest outside RR; the authors report that chaos mode can reproduce more bugs by randomizing scheduling decisions.Source: §8 · p. 17
• Small kernel extensions could improve user-space replay performance, including potentially eliminating in-process system-call interception and recording data passed through copy-to-user.Kernel support could also reduce the cost of recording context switches.Source: §8 · p. 17
• Parallel recording may be feasible for processes that do not share memory, while techniques inspired by SMP-ReVirt, dthreads, or Castor may work for some shared-memory workloads.Source: §8 · p. 17
• Record-and-replay could support high-overhead dynamic analysis during replay and correlate recording-time performance data with richer replay analysis; always-on replay could help find and fix field bugs.Source: §8 · pp. 17–18

9 Conclusions

• Linux on commodity x86 CPUs enables low-overhead, single-core user-space record-and-replay without pervasive code instrumentation, but only just.The report identifies this capability as recent and dependent on Linux and hardware features not available five years earlier.Source: §9 · p. 18
• The approach relies on software and hardware features used for purposes they were not designed to serve.The authors point to seccomp-bpf, Linux file-cloning APIs, and deterministic hardware performance counters usable from userspace.Source: §9 · p. 18
• The authors hope identifying these features’ utility will encourage broader future support and enable more compelling applications.They describe rr as an open-source, easy-to-deploy, production-ready record-and-replay framework.Source: §9 · p. 18