1. Introduction of Process Record and Replay
This document tell you how to records the execution of an ordinary Linux program and later replays it deterministically. This can be designed to help debug interactive or distributed programs, that communicate with the operating system or other computers in a complex fashion.
Traditional debuggers, such as gdb, provide comprehensive support for debugging single-node, sequential programs, but they are not as useful for distributed or interactive programs. We identify three key problems and discuss how to alleviate them.
First, the execution of such programs is inherently nondeterministic. The behavior of each process will diverge, depending on interactions with the OS, the user, or other processes. As trivial examples, the time system call returns values depending on the time of day, and the select system call returns values depending on the state of the kernel network buffer at the moment. This helps debug such non-deterministic programs by recording the execution of a process, logging every non-deterministic choice made by the program, and replaying it later as many times as the developer wishes. Thus, debugging for a non-deterministic program is reduced to that for a sequential, repeatable program.
Second, these programs often run for a long period of time, either because they need lots of resources (e.g., scientific computation), or they are server programs (e.g., distributed hash tables), or they need substantial user interactions (e.g., spreadsheet). Simply reproducing the bug in such a system often tests a developer’s patience. This way solves this problem by allowing checkpointing of the process state during execution. The developer can replay execution from any checkpoint and easily “time-travel” through executions to diagnose what exactly is wrong with the program.
Third, running a distributed system requires starting multiple processes on multiple computers, which is cumbersome and increases the turn-around time for program development. This alleviates this problem because this way can record and replay an individual process—after running and recording the whole system, the developer can replay each process using a traditional debugger. Of course, this is also a limitation: could be less useful when one wants to look at the execution of multiple processes at once.
1.1 Goals and approaches
The goal is achieved by recording and replaying events at a fairly low level—system calls and CPU instructions. User-space implementation poses challenges and limitations. First, it cannot handle events such as thread context switching or shared-memory communications. Second, because recorder and the target program run in the same protection domain, recorder fundamentally cannot prevent a malicious program from destroying recorder. Efficiency is a secondary goal for recorder. The recorder is intended for use only during testing and debugging. Thus, as long as the slowdown by recorder does not qualitatively change the program’s behavior, developers should be able to live with some performance degradation.
2. Implementation of Process Record and Replay
To record a process, you should performs the following tasks upon program startup.
(1) For each system call in libc with timing- or contextdependent effects, recorder rewrites its first few instructions and intercepts calls to it. The Recorder currently intercepts 78 Linux system calls, including gettimeofday, recvfrom, and select. The recorder logs the values generated by these calls during recording, and replays the log without actually executing the calls.
(2) The recorder does the same for CPU instructions with nondeterministic effects. We currently only patch rdtsc, the x86 instruction for reading the CPU’s timestampcounter (cycle counter). It is used, for example, as apseudo random-number generator in libc.
(3) The recorder checkpoints the process state just before returning control to the target program. In the “replay” mode, The recorder simply loads the checkpoint. Checkpointing is needed to ensure that the target sees the same set of environment variables and command line parameters during both record and replay.
(4) The recorder transfers control to the target program. The target runs as if recorder does not exist. Recorder becomes active only when the target executes a system call or a non-deterministic CPU instruction. The next section describes the first two steps in more detail.
2.1 Instruction patching
Figure 1 shows how the gettimeofday system call is recorded and replayed.
Figure 1 Recording and replaying gettimeofday.
(a) shows the first few instructions of the gettimeofday function in libc.so. When recorder starts, it writes a jmp instruction in the first 5 bytes of the function, as shown in (b). If the 5th byte is in the middle of another instruction, as is the case with gettimeofday, recorder overwrites up to the next instruction boundary (and fills the memory with nop, if necessary). In (c), recorder also copies the original first 5 bytes (6 bytes for gettimeofday) of the function to a newly allocated memory region to allow recorder to run the old implementation if necessary. (d) shows the entry point for the new implementation of gettimeofday. The recorder dynamically generates this code so that it can execute on a separate stack and avoid corrupting target memory. Finally, (e) shows newgettimeofday, Recorder’s implementation of gettimeofday. While recording, newgettimeofday calls the original gettimeofday (c) and logs the returned value. Upon recording, it simply supplies the value from the log without actually performing the system call.
One might wonder why libjockey.so does not just provide a new implementation of a system call with the same name. — LD PRELOAD is frequently used to do exactly that. The reason is that doing so will miss system calls made inside libc or ld.so, for example, a call to read that would be made by getc. These internal calls are preresolved by the static linker (ld), and cannot be overridden by redefining in LD PRELOAD.
Recorder rewrites all offending CPU instructions found in the target process. Recorder first reads the special file /proc/N/maps (N is the target process ID) that shows the virtual-memory mappings of the target process. It then reads the ELF header of each mapped shared object, discovers the locations of the text sections, and scans each text section. Then find non-deterministic CPU instructions in the section (if any), and patches them. The recorder also intercepts calls to mmap and does the same.
2.2 Segregating resource usage
The recorder and the target application run as part of the same process. They share resources, including memory and file descriptors. Recorder must segregate the use of such resources to prevent recorder from unnecessarily changing the target’s behavior, and to minimize the chance of a misbehaving target program from breaking the recorder. We discuss recorder’s handling of three such resources, heap, stack, and file descriptors.
Heap: Recorder cannot use standard libc functions, such as malloc or sbrk, to manage its own data. Doing so increases the likelihood of a misbehaving target program destroying Recorder’s data. Moreover, it changes the memory layout of the target process during record and replay. It would become impossible to correctly replay invalid memory accesses, e.g., accessing free’ed memory, which is one of the more common programming errors. Instead, the recorder stores all its internal data in a mmaped region at a virtual address (0x63000000) that is unlikely to be used accidentally by the target program. The recorder uses its own internal malloc-like library to carve the memory out to individual data structures and builds a custom C++ STL memory allocator on top of it. Thus, the recorder code has full access to STL features, including maps and dynamic vectors. This design has considerably simplified the development of recorder.One restriction is that the recorder cannot make calls to libc functions that internally call malloc or free. Examples include high-level I/O functions (FILE, std::fstream) and DNS resolvers (gethostbyname).
Stack: The recorder also segregates the use of stack. This is necessary to properly replay programs that access data beyond the stack pointer (e.g., accessing an on-stack array with a negative index). Figure 1, step (d) shows how this is done. In the first few instructions after it intercepts the call to trampoline, the recorder saves the stack pointer to an internal static variable, switches the stack pointer register to its internal memory, copies the parameters to gettimeofday (a pointer of 4 bytes) from the old to the new stack, and calls newgettimeofday. Once the new implementation returns, it then restores the stack pointer. This allows for deterministic replay even for a buggy program because the target’s stack is not used above the original stack pointer.
File descriptors: recorder must do its own file accesses every so often, for example, when opening an event log file, displaying a message, or taking checkpoints. Because recorder and the target process share the same file-descriptor table, recorder must ensure that its file operations do not alter the descriptor allocation scheme seen by the target. For this purpose, each file descriptor opened by recorder is moved to a range that is not likely to be used by the application (430 and up). This is done by performing dup2 immediately after open.
Gdb poses another problem. When starting the target process, gdb, for some reason, opens a few extra file descriptors in addition to the usual stdin, stdout, and stderr. Thus, if execution is recorded under a normal shell and then replayed under gdb, the files opened by the target processes will be assigned different descriptors, which makes replaying divergent. We solve this problem by letting recorder open dummy files for descriptors 0 to 9 on startup before returning control to the target program (it leaves descriptors in-herited from the parent process untouched). Assuming that gdb opens at most 10 descriptors when it starts the target, we can ensure that the target has the same set of files open upon record and replay. This technique is valid for other situations when the target program is started with more than the standard number (three) of inherited file descriptors.
