Skip to content
The methodOpen data
Back to the collection

Engineering Record And Replay For Deployability: Extended Technical Report

Robert O'Callahan, Chris Jones, Nathan Froyd

Show all 6 authors

Kyle Huey, Albert Noll, Nimrod Partush

2017 · arXiv

Computer systemsProgramming languagesAlgorithms
Read the paper
HN score
0
Mentions
10
Readers
7
Months
6
What’s in a score?

From the abstract

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.

Metadata: arXiv. Abstracts retain their original authors’ rights.

In the conversation

Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels

10 selected excerpts · 10 total mentions

alehander42
Neutral mention · rule
We are currently working on two "backends" where recording works in different ways. For the scripting languages and smart contract/ZK languages, we instrument the interpreters using high level hooking API-s or direct patches, and we produce a trace. For system languages, we directly build on top of RR[1] recordings for now: RR can record multiple processes, and it works in userland. IIRC it doesn't support modifications of shared memory outside of the recording. It's very well documented in their paper: Engineering Record And Replay For Deployability: Extended Technical Report[2]. 1: https://rr-project.org/ 2: https://arxiv.org/abs/1705.05937
Original comment Show HN: CodeTracer – A time-traveling debugger implemented in Nim and Rust
roca
Neutral mention · rule
The two approaches are completely different. gdb singlesteps the program and, before each instruction, records the state of registers and memory that will be changed by that instruction --- an undo log. Then you can reverse-execute an instruction by restoring the state from the undo log. This is incredibly slow because singlestepping requires a full context switch for each instruction executed. rr, on the other hand, intercepts all system calls and other sources of nondeterminism but regular CPU instructions execute normally with no overhead. The details about rr are here: https://arxiv.org/abs/1705.05937
Original comment rr – record and replay debugger for C/C++
bqmjjx0kac
Neutral mention · rule
Yeah, the reason it only works for these coarser race conditions is that RR only has one thread executing at a time. Chaos mode randomizes the durations of time allotted to each thread before it is preempted. This may be out of date. I believe I read it in the Extended Technical Report from 2017: https://arxiv.org/pdf/1705.05937
Original comment rr – record and replay debugger for C/C++
sfink
Neutral mention · rule
No, that has been done but is much slower. It records all communication with the external world. The full answer is well described in https://arxiv.org/pdf/1705.05937.pdf which I'll quote here: > We identify a boundary around state and computation, record all sources of nondeterminism within the boundary and all inputs crossing into the boundary, and reexecute the computation within the boundary by replaying the nondeterminism and inputs. If all inputs and nondeterminism have truly been captured, the state and computation within the boundary during replay will match that during recording. So for any chunk of time spent entirely in user space doing computation, the replay…
Read the full comment
starts out in the same situation and executes in exactly the same way the original process did, with zero overhead. That's what enables rr to be so low overhead overall; most programs spend the bulk of their time computing stuff and reading/writing memory. The replayed process has no way of knowing that its file descriptors aren't actually open, since anything it does with them will be provided by the recording. Quoting again: > In particular, user-space memory and register values are preserved exactly, with a few exceptions noted later in the paper. This implies CPU-level control flow is identical between recording and replay, as is memory layout.
Original comment What rr does
garaetjjte
Neutral mention · rule
By capturing all external inputs to application, it can replay it many times and results will be always identical. https://arxiv.org/pdf/1705.05937
Original comment Debuggers Suck
scott_s
Neutral mention · rule
Being slower is not, I think, the major downside. It is that an entire class of errors - race conditions - are basically outside of the scope of the tool. Which is understandable! Race conditions are hard, and when I read about the tool, my first thought was "How are they handling race conditions?" and it turns out, essentially, they're not. But race conditions are also the hardest part about debugging multithreaded applications. I'm not sure if the tool ensures deterministic scheduling of threads on the single core, but I doubt that it does. If it does not, then playbacks will not be deterministic on playback, which means you could encounter different race condition…
Read the full comment
outcomes on playback. If it does, then while you may have deterministic playback, the tool is unlikely to help with the class of race conditions that require simultaneous execution. To be clear: I'm not criticizing the tool or the work of the people. If I were to design such a tool, I would probably start with a single core as well. It seems like a valuable tool and great progress for software debugging. But I do think race conditions in multithreaded programs are a current limitation. edit: The technical report says that they deterministically schedule threads (https://arxiv.org/pdf/1705.05937.pdf): "RR preemptively schedules these threads, so context switch timing is nondeterminism that must be recorded. Data race bugs can still be observed if a context switch occurs at the right point in the execution (though bugs due to weak memory models cannot be observed)." The "weak memory model" part means it won't help with, say, debugging lock-free algorithms where you screw up the semantics.
Original comment rr: lightweight recording and deterministic debugging
pm215
Neutral mention · rule
rr has an "extended technical report" at https://arxiv.org/pdf/1705.05937.pdf which explains the principles it uses. In general they are inherently rather complicated -- in order to get to anything resembling useful speed of execution, you need to play clever tricks of one kind or another to avoid having to record absolutely everything about the process under debug.
Original comment rr: lightweight recording and deterministic debugging
roca
Neutral mention · rule
Some small-ish items: -- Virtualization of rr's required PMU features on Azure and GCP -- Virtualization of Intel's CPUID faulting on AWS and other cloud providers (Linux KVM has it, but it's not enabled in AWS) -- Fix the reliability bug(s) in the retired-conditional-branches counter on AMD Ryzen so rr works there -- Implement CPUID faulting in AMD Ryzen -- Reliable instructions-retired counter on AMD/Intel (for more reliable/simpler operation) -- Trap on LL/SC failures on ARM (AArch64 I guess) and other archs (so we can port rr there), with Linux kernel APIs to expose that to userspace -- Similar traps for Intel HTM (XBEGIN/XEND) (less important now that's mostly been…
Read the full comment
disabled for security reasons) Bigger items: -- Invest in kernel-integrated record-and-replay for Linux and other OSes -- Implement QuickRec or some other hardware support for multicore record-replay on at least some CPU SKUs (If anyone thinks they can help with any of that, talk to me!) > what do you think is keeping the overhead so high in the average case described in the post (50%)? I assume you've read https://arxiv.org/abs/1705.05937 ? For many workloads the major unavoidable cost is context switching. With rr's approach every regular tracee context switch (intra or inter process) turns into at least 2 inter-process context switches (tracee to rr, rr to tracee). This is bad for thread ping/pong-like behaviour. For many other workloads the cost is simply the loss of parallelism as we force everything onto a single core. For other workloads there is a high cost due to system calls that require context switches to rr because we don't currently accelerate them with "syscall buffering". The last one can be mostly engineered around, the former two are inherent to rr's approach. Who do you work for? :-)
Original comment Time Traveling Linux Bug Reporting: Coming in Julia 1.5
roca
Neutral mention · rule
You should read https://arxiv.org/abs/1705.05937 so you don't need to speculate. rr absolutely does guarantee that threads are scheduled the same way during replay as during recording, otherwise it wouldn't work at all on applications like Firefox which use a lot of threads. Also, rr definitely is very useful for debugging race conditions. For example Mozilla developers have debugged lots of race conditions using it. One thing that really helps is rr's "chaos mode", which randomizes thread scheduling in an intelligent way to discover possible races. See https://robert.ocallahan.org/2016/02/introducing-rr-chaos-mo... and https://robert.ocallahan.org/2016/02/deeper-into-chaos.html and https://robert.ocallahan.org/2018/05/rr-chaos-mode-improveme....
Original comment rr: lightweight recording and deterministic debugging
roca
Neutral mention · rule
The basic idea is the same as ReVirt, but there are a lot of different details because rr has to run as a pure user-space Linux application whereas ReVirt was baked into the hypervisor. For rr to run efficiently we have to use Linux APIs in creative ways. https://arxiv.org/abs/1705.05937 has more details.
Original comment rr: lightweight recording and deterministic debugging

Keep following the thread.

More in Computer systems

More from the same topics.