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".

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.

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.

True — modulo speed ups from materializing ND values from the log itself.

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