Farid Zakaria

16 min read

Dafuq is a deterministic VM?

The life of a system call inside Rewind VM.

Since I started writing about Rewind VM, the question I get most from friends is not “does it work?” but “how does it actually work?” 🤔

D’uh! It is a virtual machine that only gets interrupted when it asks to be.

Dafuq did I just read meme: Samuel Johnson squints at a book that says "It is a VM that only gets interrupted when it asks to be", then looks up, baffled: "Dafuq did I just read"

That seems to not have helped much, so let’s go deeper.

We will follow a tiny C program through the machine and, at each step, look at where non-determinism would have crept in and what Rewind does about it.

Aside: If you have not seen Rewind before, start with a flaky build you only catch once.

§Life is deterministic

CPUs must be deterministic. If they were not, we would have a very bad time trusting them to do anything.

Give a CPU the same registers, the same memory and the same instructions, and it computes the same result.

What does change? Why are machines not deterministic?

They are not closed systems. They interact with the outside world and that interaction is not deterministic. A timer interrupt can land at any instruction or a disk read can complete at any time.

Aside: Computers can’t actually make random numbers. A deterministic machine can only fake it with pseudo-randomness: run the same algorithm from the same seed and you get the same numbers back. The real stuff has to come from the physical world. My favorite example is how Cloudflare keeps a wall of 100 lava lamps in its San Francisco office with a camera pointed at it, feeding its encryption keys.

If we could capture all external influences, we could replay the external world and get the same run again. That is what Rewind does.

Every source from the outside world is either removed or replaced with a value derived from a stored seed. Time, for instance, is a clock managed by Rewind. Interrupts arrive only at points we choose. ⏱️

One more outside influence is easy to miss: other CPUs. On two cores, which thread wins a race comes down to cache misses and pipeline stalls, so Rewind provides a single virtual CPU and the threads take turns on it.

two cores core 0 thread A core 1 thread B lock both reach the lock at once the winner depends on the cache Rewind: one vCPU vCPU A B A exits threads switch only at an exit the same order every run

§A step is a VM exit

To control the outside world, Rewind needs moments where the software stops and Rewind can step in. At those moments it writes down what just happened, hands over the current time, or delivers an interrupt. So how do you stop the software at the same place on every run?

One answer is to make the hardware do it. CPUs have performance counters that can interrupt after a set number of instructions. Unfortunately, the interrupt may arrive a few instructions late, and the amount varies.11Intel’s counter is good enough that you can single-step the rest of the way to the exact instruction. I have an AMD laptop. 🙃 

Rewind uses a cooperative approach: let the software tell us when something happens!

Rewind runs the guest under KVM, the hypervisor built into Linux. The guest’s code runs directly on the real CPU until it touches a device. The CPU then stops the guest and hands control to the program running the VM, Rewind’s monitor (rewind-vmm). That hand-off is a VM exit.

Rewind patches the guest kernel so that whenever it needs something only the outside world has, such as the time, a timer, or “I have nothing to do”, it makes an exit and asks the monitor. Reporting what happened, like a process starting or a line of output, is an exit too.

Each exit the guest makes is called a step, and they are numbered starting from boot.

If we assume the guest is deterministic up to step N, step N happens at the same instruction on every run.

The monitor’s loop, sketched in Python:

step, clock, deadline = 0, 0, None

while True:
    # The guest runs natively until it exits.
    exit = vcpu.run()

    # The host's own business: not a step, and nothing is sent.
    if exit.reason == HOST_INTERRUPT:
        continue

    # An exit the guest made. Time moves only here.
    step += 1
    clock += QUANTUM

    # Read the clock, arm a timer, log an event...
    deadline = handle(exit, step)

    # Interrupts go in only here, with the guest stopped.
    if deadline is not None and clock >= deadline:
        vcpu.inject(TIMER_INTERRUPT)
        deadline = None
normal VM a different instruction each run run 1 timer run 2 timer Rewind step N, every run run 1 (recording) step N run 2 (replay) step N an exit the guest made: one step the monitor's interrupt each line is the guest's instructions, left to right

This is true on the first run too. Nothing gets recorded, and a replay just runs the same inputs again.

Three pieces make this work, and your program doesn’t need to know about any of them.

A patched Linux kernel. The guest kernel is the piece that cooperates. A small patch teaches it to take its clock, its timer and its idle loop from the monitor instead of from hardware, and to report what processes do: exec, exit, output, files written. The monitor also hides the CPU features that would leak the outside world in, such as the hardware cycle counter and the random number instruction, so the kernel never uses them.

rewind-init. The special PID 1 is a small program that mounts the input image (a Nix closure or a root filesystem), runs the command, reports its exit status and powers the machine off. The image is mapped straight into guest memory, so reading a file is reading memory, and there is no disk to finish a read at a random moment.

rewind-vmm. The monitor owns time, decides when interrupts go in, and keeps the trace of everything the kernel reports.

Inputs Nix closure or rootfs → erofs Guest VM · 1 vCPU on stock KVM Code runs natively on the real CPU Build / test processes nix build, make check rewind-init PID 1, mounts erofs Patched Linux + Rewind platform Clock, timer, idle and events go through the host VM exit = one step Interrupt only at an exit Host: rewind-vmm Owns time, ordering and memory Virtual clock exits + branch count Event trace processes, files, output Keyframes dedup page store Seeded randomness Same inputs + seed → same run

§The life of a system call

Here is the program. It reads the clock, draws a random number, prints both with the address of a stack variable, sleeps for a second, then reads the clock again.

#include <stdio.h>
#include <sys/random.h>
#include <time.h>
#include <unistd.h>

int main(void) {
  struct timespec ts;
  unsigned int r;

  clock_gettime(CLOCK_REALTIME, &ts);
  getrandom(&r, sizeof r, 0);
  printf("time=%ld.%09ld random=%u stack=%p\n", ts.tv_sec, ts.tv_nsec, r, (void *)&r);
  fflush(stdout);

  sleep(1);

  clock_gettime(CLOCK_REALTIME, &ts);
  printf("time=%ld.%09ld\n", ts.tv_sec, ts.tv_nsec);
  return 0;
}

On my laptop every run prints something new. In Rewind, every run prints the same thing, down to the nanosecond, until you change the seed:

$ rewind run --root root -- /bin/hello
time=1792886400.001006990 random=166963147 stack=0x7fff2bad5e4c
time=1792886401.001132684
rewind: run 85a03383f7d917d9 exited:0 after 432 steps, 1.002s virtual, 1.139s wall (poweroff)

$ rewind run --root root -- /bin/hello
time=1792886400.001006990 random=166963147 stack=0x7fff2bad5e4c
time=1792886401.001132684
rewind: run 85a03383f7d917d9 exited:0 after 432 steps, 1.002s virtual, 0.394s wall (poweroff)

# a different seed is a different input, so a different run
$ rewind run --root root --seed 1 -- /bin/hello
time=1792886400.001006990 random=2117056732 stack=0x7ffdd58e5bdc
time=1792886401.001132680
rewind: run 59c7da84895c210a exited:0 after 432 steps, 1.002s virtual, 0.848s wall (poweroff)

They're the same picture meme: Pam holds up two papers labelled "the run that failed on CI" and "rewind replay of that run", and says "They're the same picture."

Same inputs, same run id, same 432 steps. Oh, and the program slept for a second, yet the whole VM finished in 0.39 seconds. 🤓

Normally, reading the time never enters the kernel: a bit of code in every process reads a hardware counter directly. Rewind hides that counter, so the read goes to the kernel, and the kernel asks the monitor.

guest host hello user space guest kernel Rewind platform KVM host kernel rewind-vmm host process syscall no hardware counter read the clock an I/O port VM exit made by the guest count a step clock += 5 µs + work leave the time in memory timer due? interrupt run the guest again resume the guest return the time …400.001006990

Rewind hides the CPU’s random number instruction, so the only thing available to the guest kernel is the seed Rewind passes at boot. The kernel’s random number generator is seeded with that value, so every run of the same program with the same seed gets the same random numbers.

Most system calls never leave the guest. The few that need the outside world make an exit, and the monitor writes down what happened. The guest kernel also reports when it is idle, so the monitor can jump its clock to the next timer interrupt.22sleep(N) costs no real time. The monitor jumps its clock straight to the deadline and delivers the timer interrupt. 

Control those few doors and the guest is deterministic: the outside world shows up at the same step on every run.

So, dafuq is a deterministic VM? Like I said at the start, it’s a VM that only gets interrupted when it asks to be. Hopefully that makes a bit more sense now. 😅

Expanding brain meme: "Re-run the flaky test until it passes", "Add sleep(1) before the assert", "Record where every interrupt landed and replay it", and, brightest, "Only take an interrupt when the guest asks for one"