3 ms·

Does anyone know how rr implements the rewind capability? It seems that it has to keep a snapshot of the entire program memory at every step, or are there any t

by kubb 6y ago

Does anyone know how rr implements the rewind capability? It seems that it has to keep a snapshot of the entire program memory at every step, or are there any techniques it uses to optimize this in specific cases?

ynik 6y ago
It records the results of syscalls. In replay mode, the program is executed again, but rr will replay the recorded syscall effects instead of doing actual syscalls. As a result, the program will deterministically behave the same way it did the first time around. There's a bunch of more magic to make other things (incl. multi-threading) behave deterministically. rr uses hardware performance counters (telling the CPU things like "trigger an interrupt after executing N conditional branches") to seek to a particular time in the program's execution. So as a first approximation, "step back" can be implemented as "re-run from beginning, programming the perf counter break after N-1 steps". This is where the trouble with certain CPU models comes into play -- these perf counters aren't always perfectly reliable, and rr needs different workarounds for each CPU generation. And I guess rr has some full program snapshots as well at regular intervals so that the replay doesn't need to start all over from scratch on every "step back".
DSingularity 6y ago
If you take a snapshot initially then all you need is the results of anything non-deterministic - ie anything which cannot be produced by program instructions themselves. For those you can pretty much get them all by logging the results of system calls. All that is left is things like RDTSC, RDRND, and thread interleaving of a multi threaded application.
- sanxiyn 6y ago
  This works in theory, but if your program has been running for a minute, going back a second by re-executing from the beginning will take a minute. rr snapshots every second so that going back takes similar time to going forward, rounded to seconds, adjusted for overhead.
  - DSingularity 6y ago
    True — modulo speed ups from materializing ND values from the log itself.
sanxiyn 6y ago
rr keeps snapshots roughly every second. To rewind, rr executes forward from snapshots, sequentially from the last snapshot to the first.

by kubb 6y ago

ynik 6y ago

It records the results of syscalls. In replay mode, the program is executed again, but rr will replay the recorded syscall effects instead of doing actual syscalls. As a result, the program will deterministically behave the same way it did the first time around. There's a bunch of more magic to make other things (incl. multi-threading) behave deterministically. rr uses hardware performance counters (telling the CPU things like "trigger an interrupt after executing N conditional branches") to seek to a particular time in the program's execution. So as a first approximation, "step back" can be implemented as "re-run from beginning, programming the perf counter break after N-1 steps". This is where the trouble with certain CPU models comes into play -- these perf counters aren't always perfectly reliable, and rr needs different workarounds for each CPU generation. And I guess rr has some full program snapshots as well at regular intervals so that the replay doesn't need to start all over from scratch on every "step back".

DSingularity 6y ago

If you take a snapshot initially then all you need is the results of anything non-deterministic - ie anything which cannot be produced by program instructions themselves. For those you can pretty much get them all by logging the results of system calls. All that is left is things like RDTSC, RDRND, and thread interleaving of a multi threaded application.

sanxiyn 6y ago
This works in theory, but if your program has been running for a minute, going back a second by re-executing from the beginning will take a minute. rr snapshots every second so that going back takes similar time to going forward, rounded to seconds, adjusted for overhead.
- DSingularity 6y ago
  True — modulo speed ups from materializing ND values from the log itself.

sanxiyn 6y ago

rr keeps snapshots roughly every second. To rewind, rr executes forward from snapshots, sequentially from the last snapshot to the first.