A clock made of branches

What is time inside a machine you want to replay? 🧘

When building Rewind, a deterministic VM, you come face-to-face with the idea of how to represent time very quickly. You need a way to measure time inside the guest so that on subsequent replays, the guest sees the same time and makes the same decisions. Time is the ultimate variable.

You can’t simply record the wall-clock time of the host because time spent between two interception points depends on things outside the guest, like host load, CPU frequency, caches and other processes. Therefore the same guest work can take a different amount of time on the host.

In dafuq is a deterministic VM? I explained how the clock inside Rewind VM moves 5 microseconds per step. More specifically, that clock, exit time, moves only when the guest exits such as from a syscall. It treats everything the program does between two exits as instant. Therefore a program that is CPU bound such as doing nothing but math for a full second between two system calls, sees only 5µs go by. 🤦🏻‍♂️

Rewind has a second clock mode as well, counter time, that tries to account for the work. The clock advances one nanosecond for every conditional branch the guest retired.¹1This is the same approach popularized by the rr debugger. The rr paper calls it deterministic time.

Aside: New to Rewind? Start with a flaky build you only catch once and dafuq is a deterministic VM?

Still confused about what I mean by “free” and “branches”? Let’s look at a simple example to distinguish between the two clocks.

The counter time tries to account for the work whereas the exit time only advanced the clock on exits.²2The 5µs was my guess at a reasonable cost of a system call and context switch on current hardware. The 1ns is roughly what a conditional branch costs on a current core.

Why branches, though?

§What is time in a replayed machine?

We already understand that we cannot rely on the wall-clock time of the host. We need something to measure that is the same for every run of the same program so that we can equate it to time spent.

What is the same on every run?

The guest’s instruction stream! The CPU is a deterministic machine: the same input, the same registers, the same memory, and the same instructions produce the same next state.

We can measure time by measuring progress through the instruction stream. 💡

Turns out that CPU manufacturers even ship a hardware counter for exactly that. Is it reliable? Let’s see. 🧐

Let’s use this simple program: count down from a billion.

int main(void) {
  long i = 1000000000;
  do {
    i--;
  } while (i != 0);
  return 0;
}

_start:
    mov  rcx, 1000000000
.loop:
    dec  rcx
    jnz  .loop
    mov  eax, 60    ; exit(0)
    xor  edi, edi
    syscall

The assembly equivalent contains a mov, a billion dec+jnz (conditional branch) pairs, then three instructions to exit for a total of 2,000,000,004 instructions.

Let’s run it on the CPU twice and count the instructions and conditional branches with perf stat:

$ nasm -felf64 loop.asm && ld -o loop loop.o
$ taskset -c 5 perf stat -e instructions:u,ex_ret_cond:u ./loop
     2,000,001,025      instructions:u     1,000,000,000      ex_ret_cond:u

$ taskset -c 5 perf stat -e instructions:u,ex_ret_cond:u ./loop
     2,000,001,054      instructions:u     1,000,000,000      ex_ret_cond:u

The same program and input gives the same conditional branch count, but the instruction count is off by a thousand or so. Why?

Although this loop is CPU bound and only decrements a register, it is still not isolated from the effects of the outside world. Timers tick, network packets arrive, other cores send inter-processor interrupts (IPIs). The program can’t see any of that, but the instruction counter we are probing can.

I pinned the loop to a single CPU 5 and counted how many interrupts that CPU took during each run, from /proc/interrupts.

The dashed line is one extra count per interrupt, and the instruction counter is almost perfectly on it.³3The fit is 0.94 rather than 1 because /proc/interrupts also catches the interrupts that land while perf and taskset start up and tear down, before and after the loop runs. The conditional branch counter on the other hand, stays at zero no matter how many interrupts land.

Interrupts from the outside-world are not the only thing that can skew the instruction count. The program can also page fault, which is an interrupt too. The instruction counter sees the kernel’s detour to handle the fault, but the program does not.

Tip Out of the box, AMD Zen also overcounts conditional branches, a few in tens of millions, from a speculation optimization known as SpecLockMap. The fix is to set a particular bit in the PMU MSR, which Rewind does automatically as does rr#2034.

§So, what time is it?

In order to rewind history, we need a measurement of time that is reliable and deterministic. Our traditional wall-clock time is unreliable due to the effects of the outside world but we do have a reliable measurement of progress through the instruction stream: the conditional branch counter.

Using the conditional branch counter as a proxy for time turns out to be a relatively decent approximation.

Clock	Time inside the VM	Time on the host
Exit time	2.1 s	15.7 s
Counter time	11.7 s	14.2 s

Why do we care about having a “realistic” representation of time?

Plenty of programs read the clock and make decisions with it, so the guest’s clock has to be at least somewhat realistic. Under exit time, computing is “free”. A test that checks some work “finishes within 1 s” always passes. If the bug you’re chasing is a timeout, exit time will never reproduce it. 🙃

Races get skewed too with an unrealistic clock. With exit time, a whole burst of work lands in the same instant, which crowds the threads together, so a race can fire far more often in the VM than it ever would on real hardware.

Some say time is an illusion. I say it’s a jnz counter.