Rewind VM: a flaky build you only catch once
If a test fails on CI and nobody can reproduce it, did it really fail? 🧘 Nix gives me a build that is a function of its inputs via the extensional model. The same derivation, produces the same store path, and if I am lucky, the same bytes. What Nix does not give me is the same run . 1 A test suite with a race in it may pass on my laptop, fail once on CI, and when I rebuild it to look, it passes again. If you have experienced bugs like this, you know that it can be frustrating. You are effectively at times trying to find the needle in the haystack . I wrote recently that the Nix sandbox is a hidden input to a derivation. The same is true of the thread schedule. The order the kernel happens to run your processes in decides whether some builds pass, and nothing within the derivation records it. These are the hidden inputs to a build that can make it flaky. Are we left to hoping that we will find the needle in the haystack? Or is there a way to make the run a function of its inputs too? I built Rewind VM to make the schedule an input too. It runs a Nix build, a test suite or any Linux command inside a KVM virtual machine whose every run is a function of its inputs. The same inputs give the same run, at the same steps, every time . You can replay a failure, scrub through it, read any file as it was at any point, and fork it under a different thread interleaving. ✨ Confused? Yes it sounds like magic. The best way to explain it is with short demo. Let’s investigate the dining philosophers problem. The problem is that the five philosophers sit at a round table with a fork between each of them. A philosopher needs both forks beside them to eat. A philosopher may pick up one fork at a time. 2 f0 f1 f2 f3 f4 P0 eats P1 eats P2 eats P3 eats P4 eats five philosophers, five forks P0 picks up f0 P0 picks up f1 and eats P0 puts both down P2 picks up f2 P2 picks up f3 and eats P2 puts both down everyone reaches for the left fork each waits on a neighbor's fork nobody can ever eat: deadlock The philosophers take turns, until all five pick up their left fork at once. If all five pick up their left fork before any of them reaches for a right one, every fork is taken and every philosopher waits on a neighbor who is also waiting. Deadlock . 3 On my laptop 14 of 100 rebuilds deadlocked. 💣 builds the same derivation the way the Nix sandbox would, inside the deterministic VM. Oh darn, it passed! That means it will pass forever right? Not quite. The VM is deterministic, but the guest kernel’s scheduler is not. It can reschedule threads at different points in the program, and that can change the outcome. To find the other interleavings, runs the build again under perturbed schedules , we effectively ask the guest kernel to reschedule at different steps which causes a different sequence of events. runs one VM per core by default and stops after the first batch of schedules where the exit code differs. Note A failing schedule on its own is not that super helpful. Schedule 1 which had deadlocked likely perturbs every step from the start of the build to the end, and most of those perturbations have nothing to do with the deadlock. To help with this, narrows it: it shrinks the window of steps the schedule may perturb, first pulling in the end and then the start, reruns the build for each candidate window, and keeps the smallest one that still deadlocks. For our deadlock problem, it might be easier to see the last few lines of the log and see that all five philosophers have picked up their left fork and are waiting for the right one. We can also inspect the events, which are the same as the log but with timestamps and thread IDs. What if I’m not familiar with the VM? Can we look around? Yes! drops you into a shell inside the VM at any step, in a process’s working directory, with the build’s environment, while everything else in the VM stays stopped. We can use to bring gdb into that shell, and gdb can attach to the stuck process. 4 All five philosophers are on line 27, waiting for their second fork. f0 f1 f2 f3 f4 P0 P1 P2 P3 P4 left fork first every wait is on a held fork: a ring , and each work on a “throwaway” fork of the run at a step, so nothing they do changes the recording. You can use to do a “real” fork: it branches a run at a step under another schedule. A recording does not have to stay on the machine that made it. packs a run into a single file, with the VM’s kernel, its input image and the keyframes, so another machine with the same CPU vendor can replay it. 5 You are no longer beholden to a random flake on CI. Run the tests under on a CI machine with KVM, upload the failing run’s as a build artifact, and you can reproduce the bug perfectly on your machine. How do we fix the deadlock? We number the forks and always pick up the lower numbered one first. The last Philosopher now reaches for fork 0 before fork 4, so the waits can never cause a deadlock. f0 f1 f2 f3 f4 P0 P1 P2 P3 eats P4 lower numbered fork first P4 holds nothing, so f4 stays free We can then run to test the fix. Before the fix, 9 of the same 64 schedules deadlocked. Rewind VM includes some tutorials with more examples of using to find and fix bugs if you want to explore further. The VM has a single vCPU on stock KVM, so guest code runs on the real CPU at close to native speed. 6 What breaks determinism in a normal VM is everything that reaches the guest from outside its instruction stream: timer interrupts, clocks, random numbers, I/O completions, and any other event Rewind removes each of those or replaces it with a value it controls. Keeping account of every event and the step it happened at, it can replay the same run. If you squint, a run is a derivation. Its inputs are the kernel, the initramfs, a root filesystem (a Nix closure packed into a read-only image), the command, a seed and a schedule. Change any of them and you get a different run. Change none of them and you get the same one. The command is open source under the MIT license. 7 There is also a desktop app that gives a friendlier view of a recorded run. You can drag the playhead, view the build log, the process tree and the files at any event. “Open shell” and “Attach gdb” open a terminal pane on a fork at the playhead. I pointed Rewind at some tools I use every day to see what we can find. Each of these is reported upstream with a fix. On NixOS there is a module: If you have a test that fails on CI once a week, I would like to hear whether Rewind catches it and helped you debug it. Don’t just add a and paper over your concurrecy failures anymore, replay them. 🔁 A run is the sequence of events that happen in a process to produce a result. A build is a run of a derivation. ↩ The world is a metaphor for the thread scheduler. Each philosopher is a thread and each fork a mutex. ↩ The program stops making progress and never exits, so the check phase runs it under , which kills it and exits with status 124. ↩ There is actually native support for gdb in the VM already. You can also use to bring in any other tool you want to use. ↩ Without , writes only the run’s trace, its events and output, and leaves out the kernel, the input image and the keyframes. The file is much smaller and enough to read the run with and . It can’t be replayed or forked, though, so , and need the full export. ↩ GNU hello build from nixpkgs takes 11.7 s in the VM vs. 14.3 s without it on the same laptop. ↩ The guest kernel patch is GPL-2.0 alongside Linux. ↩ The NixOS module can do it automatically for you and without the setting Rewind falls back to a coarser clock. ↩ f0 f1 f2 f3 f4 P0 eats P1 eats P2 eats P3 eats P4 eats five philosophers, five forks P0 picks up f0 P0 picks up f1 and eats P0 puts both down P2 picks up f2 P2 picks up f3 and eats P2 puts both down everyone reaches for the left fork each waits on a neighbor's fork nobody can ever eat: deadlock The philosophers take turns, until all five pick up their left fork at once. If all five pick up their left fork before any of them reaches for a right one, every fork is taken and every philosopher waits on a neighbor who is also waiting. Deadlock . 3 On my laptop 14 of 100 rebuilds deadlocked. 💣 builds the same derivation the way the Nix sandbox would, inside the deterministic VM. Oh darn, it passed! That means it will pass forever right? Not quite. The VM is deterministic, but the guest kernel’s scheduler is not. It can reschedule threads at different points in the program, and that can change the outcome. To find the other interleavings, runs the build again under perturbed schedules , we effectively ask the guest kernel to reschedule at different steps which causes a different sequence of events. runs one VM per core by default and stops after the first batch of schedules where the exit code differs. Note A failing schedule on its own is not that super helpful. Schedule 1 which had deadlocked likely perturbs every step from the start of the build to the end, and most of those perturbations have nothing to do with the deadlock. To help with this, narrows it: it shrinks the window of steps the schedule may perturb, first pulling in the end and then the start, reruns the build for each candidate window, and keeps the smallest one that still deadlocks. For our deadlock problem, it might be easier to see the last few lines of the log and see that all five philosophers have picked up their left fork and are waiting for the right one. We can also inspect the events, which are the same as the log but with timestamps and thread IDs. What if I’m not familiar with the VM? Can we look around? Yes! drops you into a shell inside the VM at any step, in a process’s working directory, with the build’s environment, while everything else in the VM stays stopped. We can use to bring gdb into that shell, and gdb can attach to the stuck process. 4 All five philosophers are on line 27, waiting for their second fork. f0 f1 f2 f3 f4 P0 P1 P2 P3 P4 left fork first every wait is on a held fork: a ring , and each work on a “throwaway” fork of the run at a step, so nothing they do changes the recording. You can use to do a “real” fork: it branches a run at a step under another schedule. A recording does not have to stay on the machine that made it. packs a run into a single file, with the VM’s kernel, its input image and the keyframes, so another machine with the same CPU vendor can replay it. 5 You are no longer beholden to a random flake on CI. Run the tests under on a CI machine with KVM, upload the failing run’s as a build artifact, and you can reproduce the bug perfectly on your machine. How do we fix the deadlock? We number the forks and always pick up the lower numbered one first. The last Philosopher now reaches for fork 0 before fork 4, so the waits can never cause a deadlock. f0 f1 f2 f3 f4 P0 P1 P2 P3 eats P4 lower numbered fork first P4 holds nothing, so f4 stays free We can then run to test the fix. Before the fix, 9 of the same 64 schedules deadlocked. Rewind VM includes some tutorials with more examples of using to find and fix bugs if you want to explore further. What is Rewind VM? The VM has a single vCPU on stock KVM, so guest code runs on the real CPU at close to native speed. 6 What breaks determinism in a normal VM is everything that reaches the guest from outside its instruction stream: timer interrupts, clocks, random numbers, I/O completions, and any other event Rewind removes each of those or replaces it with a value it controls. Keeping account of every event and the step it happened at, it can replay the same run. If you squint, a run is a derivation. Its inputs are the kernel, the initramfs, a root filesystem (a Nix closure packed into a read-only image), the command, a seed and a schedule. Change any of them and you get a different run. Change none of them and you get the same one. The command is open source under the MIT license. 7 There is also a desktop app that gives a friendlier view of a recorded run. You can drag the playhead, view the build log, the process tree and the files at any event. “Open shell” and “Attach gdb” open a terminal pane on a fork at the playhead. Footguns One vCPU. Threads interleave but never run in parallel, so races that need two cores at once are out of reach. No preemption between system calls. A thread spinning on a flag without yielding stalls the VM. AMD needs once per boot for the exact clock. 8 A run replays only on the CPU vendor it was made on , AMD from Zen 2 on. No network besides loopback, and x86_64 Linux hosts with KVM only. Nix : dies of when exits between two writes. It never failed in 20,000 runs on my laptop and failed on the first run in Rewind. #16546 , fixed by #16547 ( case study ). Nix : several processes creating a new store at once fail with “database is busy”, as seen on Hydra. #15987 , fixed by #16554 . nixd : formatter output over 64 KiB hangs the language server. #899 , fixed by #900 . jujutsu : three tests fail about half the time on tmpfs, because operations ending in the same millisecond are ordered by a random id. #10306 , fixed by #10307 . A run is the sequence of events that happen in a process to produce a result. A build is a run of a derivation. ↩ The world is a metaphor for the thread scheduler. Each philosopher is a thread and each fork a mutex. ↩ The program stops making progress and never exits, so the check phase runs it under , which kills it and exits with status 124. ↩ There is actually native support for gdb in the VM already. You can also use to bring in any other tool you want to use. ↩ Without , writes only the run’s trace, its events and output, and leaves out the kernel, the input image and the keyframes. The file is much smaller and enough to read the run with and . It can’t be replayed or forked, though, so , and need the full export. ↩ GNU hello build from nixpkgs takes 11.7 s in the VM vs. 14.3 s without it on the same laptop. ↩ The guest kernel patch is GPL-2.0 alongside Linux. ↩ The NixOS module can do it automatically for you and without the setting Rewind falls back to a coarser clock. ↩
AI
Programming
Entertainment
Gaming
C++
Python
Linux
Sql
Security
Media
Culture
Rust
C
Writing
Business
Design
DevOps
Shell
Cloud
Hardware
Testing
Go
JavaScript
Node.js
Web Development
HTML
CSS