  The ability to record and replay program executions with low overhead enables
many applications, such as reverse-execution debugging, debugging of
hard-to-reproduce test failures, and "black box" forensic analysis of failures
in deployed systems. Existing record-and-replay approaches limit deployability
by recording an entire virtual machine (heavyweight), modifying the OS kernel
(adding deployment and maintenance costs), requiring pervasive code
instrumentation (imposing significant performance and complexity overhead), or
modifying compilers and runtime systems (limiting generality). We investigated
whether it is possible to build a practical record-and-replay system avoiding
all these issues. The answer turns out to be yes - if the CPU and operating
system meet certain non-obvious constraints. Fortunately modern Intel CPUs,
Linux kernels and user-space frameworks do meet these constraints, although
this has only become true recently. With some novel optimizations, our system
'rr' records and replays real-world low-parallelism workloads with low
overhead, with an entirely user-space implementation, using stock hardware,
compilers, runtimes and operating systems. "rr" forms the basis of an
open-source reverse-execution debugger seeing significant use in practice. We
present the design and implementation of 'rr', describe its performance on a
variety of workloads, and identify constraints on hardware and operating system
design required to support our approach.
