Latest Posts (20 found)
Farid Zakaria 2 days ago

beer.drv.drv.drv

Have you heard about dynamic derivations ? They are an experimental-feature in Nix that lets a derivation produce other derivations as its output. Why ? This lets you dynamically create your build graph, instead of having to know it all at evaluation time. It’s Nix’s answer to try and match the build speed of other build systems like Bazel or buck2 . There is not much written about dynamic derivations, and the documentation is sparse. I have written a few posts about them, so I sometimes get questions about them. Recently, I got a DM from Evan Porter over LinkedIn , the ultimate bug triaging network, about whether it is possible to query the deriver of a dynamic derivation to get the initial derivation. For dynamic derivations let’s say I have a .drv.drv file. This file outputs a derivation. Is it usually possible to query deriver the output derivation to obtain the initial derivation? They had tried it and got this: That should work. 🤨 Every path a build registers carries a , the that produced it, and a that came out of a build is still a path a build registered. When I tried it, it worked. 🤷 You will need in your to drive the samples in this post. Turns out, there is a case where you do get if you set on the producer. If the producer is content-addressed, its output path is not known until after the build, and Nix does not fill in the of a path that already exists. I filed NixOS/nix#16823 . The question though made me wonder how far back you can walk the chain of dynamic derivations. I had to try it. 😈 Let’s pick a fun example to see how far we can go. Here is a derivation that imitates the classic song 99 bottles of beer by producing a chain of derivations, each one outputting the next verse. 1 Tip A derivation whose output is a must set . In our example we are using a content-addressed derivation, but the same idea works with an input-addressed one, but it’s more work to compute the output path in the shell, unless you are using to do it for you with recursive Nix. The Nix side builds the first derivation and then follows once per bottle. While working through this example, I hit a bug in Nix that made me set on the top derivation. That is not necessary for a derivation that outputs a , but it works around the bug. I filed NixOS/nix#16830 . You might notice that we limit the number of beers to 50. Why 50 and not 99? Well, 50 is the most that fits in a store path. The maximum length of a store path is 211 characters . A derivation’s store path must include the suffix, and every in a chain adds four characters. The top derivation is named and if you add 51 s we get 208 characters. No room for any more beer. 🍻 Let’s build sing it. Fifty-one builds, one after another 2 . Evaluation knows about only the first one. Nix discovers each of the other 50 by building the one before it. 🍺 Back to the original question: can we query the deriver of the output derivation to get the initial derivation? Yes, we can. Let’s put in a loop that walks from the result all the way back to the top. We have the result plus 51 derivations. 💪 Since every derivation in the chain was built, every one has a build log, and you can ask any of them to sing its verse again. I’m very excited for the future of dynamic derivations. tomberek is leading a working-group to finalize the feature and are currently meeting weekly. With dynamic derivations, Nix will be able to compete with other build systems in terms of speed and flexibility and take over the world . Nix the world. The builder writes the next derivation by hand in ATerm , so there is no recursive Nix and no involved.  ↩ A single trivial build takes about 1.5 seconds on my laptop, so the cost of building 51 derivations is about 75 seconds largely due to substituter lookups. If you disable substituters , the builds take about 1.3 seconds in total.  ↩ The builder writes the next derivation by hand in ATerm , so there is no recursive Nix and no involved.  ↩ A single trivial build takes about 1.5 seconds on my laptop, so the cost of building 51 derivations is about 75 seconds largely due to substituter lookups. If you disable substituters , the builds take about 1.3 seconds in total.  ↩

0 views
Farid Zakaria 1 weeks ago

What if every Nix build were bit-reproducible?

The holy grail of build systems and package managers is bit-reproducible 1 builds. This is such a desired trait that nearly every Linux distribution has a reproducible builds project to track the progress and validity of their builds. Why is bit-reproducibility so important? Trust. You can trust that the software you are running has not been tampered with and is the same as what the developers intended if you can verify that when built from source, the output is identical. Making software bit-reproducible though is hard. There are a lot of ways that can introduce non-determinism into a build: timestamps, random seeds, thread scheduling, and more. Most distributions that have achieved “reproducible builds” have done so for only a subset of their packages, usually those that comprise the core of the ISO or distribution. Nix’s default model, the extensional model (input-addressed), famously works around the need for bit-reproducibility by hashing the inputs to a build and using that hash as the store path. This lets the build be repeatable even if the output is not bit-for-bit identical. It is an incredibly pragmatic solution to making builds repeatable, but it does not solve the problem of trust. We are still trusting the outputs uploaded to cache.nixos.org have not been tampered with. Nix also has an experimental content-addressed model (intensional model) where the paths are based on the content of the output, but crucially, it does not guarantee that the builds are bit-reproducible. This leaves us with an undesirable situation regardless of the model. For the extensional model, the smallest change in the inputs changes the store path which causes a cascade of rebuilds. For the intensional model, a single derivation can produce multiple different outputs. What if every build could be bit-reproducible? What would that mean for Nix and the extensional model? I have been working on Rewind , a deterministic virtual machine. It runs builds in a deterministic environment, which so far has mostly been used to investigate bugs. I have been thinking about what else a platform that runs builds deterministically makes possible. I started this thought by exploring how to make profile-guided optimization reproducible but I was just scratching the surface. When we try to make a build bit-reproducible, we usually go hunting for the sources of non-determinism: timestamps, random seeds, thread order. These are inputs the derivation does not account for, so they are not hashed into the store path. A simpler approach is to run the whole build inside a deterministic machine. Eelco’s thesis says outright that the extensional model assumes the builder is impure (§5.7). Build operations in general are not pure: the contents that a builder stores in the output path can depend on impure factors such as the system time. […] Thus, while any derivation can have a potentially infinite set of output path contents that can be produced by an execution of its builder, we view the elements of that set as interchangeable. But this is a model—an assumption about builders. Running a build within Rewind captures all of the implicit inputs to a build and makes them explicit, which makes any build bit-reproducible. 🤯 Aside: New to Rewind? Start with a flaky build you only catch once and dafuq is a deterministic VM? We can wrap any derivation in Rewind with a Nix function. takes the machine’s inputs and a derivation, and returns the same derivation with its builder running inside Rewind: 2 It works on any derivation and the resulting derivation is bit-reproducible every time. 3 Let’s look at a simple example of a build that is not bit-reproducible, and how when wrapped in Rewind, it becomes bit-reproducible. Here is a simple C program that prints a greeting and depends on a library. The derivation adds a build id and a build time to the output similar to what release builds often do to “stamp” their builds. The build id and build time are two common sources of non-determinism in builds. We have wrapped the derivation in a function to control whether the build runs in Rewind or not, and whether the build is content-addressed or not. Built on the host under the input-addressed model, fails : Built in Rewind, the same derivation passes: The UUID still comes from the kernel’s random pool and the time still comes from the clock. They are the same on every build because the pool’s seed and the clock’s start are initialized from the same values. Nice! We just got a build that is bit-reproducible even if it’s not content-addressed. You can find more details of the library and even making Rewind a Nix on Rewind’s Nix build reference . What does that mean for the content-addressed model? Since the outputs are not bit-reproducible, the same derivation gets a different path on each rebuild. 4 Producing multiple variants is problematic and the thesis notes the consequence (§6.4.1): you can end up with a closure that contains more than one variant of the same derivation. The fact that a derivation can resolve to any number of output paths due to impurity, leads to the problem that we might end up with a closure that contains more than one element from the output equivalence class of a derivation. With , both stores build the same bytes and print the same path: 5 One derivation, one path, in every store. Bit-reproducible outputs also mean cache hits across machines. If the bytes are the same, the content address is the same, and a path one machine built is a hit for every other: early cutoff optimization ftw! When we make every build bit-reproducible, the two models collapse into one. What does this mean for the extensional model? The extensional model was a wonderful pragmatic solution to a world where determinism was not guaranteed but it came at a cost: a single change in the inputs cascades through every downstream derivation. Adoption to content-addressed derivations has been slow similarly because producing multiple outputs makes it hard to reason about the closure of a derivation. When we have guaranteed bit-reproducibility, both problems disappear. Having a stable platform with which to build software reproducibly might completely change the toil of working to make software reproducible and change the economics of whether to leverage content-addressed derivations. The usefulness of a reproducible environment is not well explored and I think there are other interesting use cases for it. One that I’m exploring is to use it to make the act of performing a benchmark reproducible. Aside The cost is that the machine is now an input, Rewind included. Upgrade Rewind and every wrapped derivation rebuilds. Build on an Intel machine and you get a different, equally reproducible, output than on AMD. A tool that was designed for bug investigation and reproducibility of builds might have a larger impact on the software ecosystem than I had originally thought. It is a tool that can be used to make software more trustworthy, and all the wonderful beefits that come with it. It’s lame that I have to keep clarifying it as “bit” reproducible but the term is overloaded.  ↩ Rewind is a KVM-based virtual machine, so it requires a host with KVM support. It also requires the or system feature to be advertised by the host.  ↩ On the same Rewind version and the same CPU vendor. Fixed-output derivations are refused, because they need the network and the VM has none.  ↩ Two stores are used to illustrate buids on different machines.  ↩ Nix 2.35 changed how it hashes an output that mentions its own path, so the content address of such an output depends on the Nix version.  ↩ It’s lame that I have to keep clarifying it as “bit” reproducible but the term is overloaded.  ↩ Rewind is a KVM-based virtual machine, so it requires a host with KVM support. It also requires the or system feature to be advertised by the host.  ↩ On the same Rewind version and the same CPU vendor. Fixed-output derivations are refused, because they need the network and the VM has none.  ↩ Two stores are used to illustrate buids on different machines.  ↩ Nix 2.35 changed how it hashes an output that mentions its own path, so the content address of such an output depends on the Nix version.  ↩

0 views
Farid Zakaria 1 weeks ago

The intensional model in disguise

Despite how different they look on the surface, Nix, Bazel and buck2 are remarkably similar under the hood. Don’t believe me? I built a prototype in one store, two frontends to prove it. Turns out though that the similarities are even deeper than I realized. Upon further reflection, I realized that the intensional model is an even more substantial common denominator. What is the intensional model? TIP I’ve written before about Nix’s intensional model , better known as content-addressed (CA) derivations. It has been “experimental” in Nix for years. 🧪 In the intensional model, outputs are addressed by their content , and actions refer to their inputs by content as well. The extensional model instead addresses an output by the recipe and inputs that produced it. Nix also calls this “content-addressed derivations” (CA derivations). Bazel and buck2 don’t name their model, but they use content-addressing as well. Consider this coincidence: Eelco’s PhD thesis was published in 2006, the same year that Google started development on Blaze, the predecessor of Bazel [ cite ]. Let’s take a closer look at the three systems with a simple C example and see how all three implement the intensional model. 🥸 In the traditional extensional model (input-addressed), a change anywhere upstream of a build action invalidates the action’s output. This occurs even if the change is irrelevant to the output, such as a comment change in a source file. In contrast, the intensional model (content-addressed) only invalidates an action’s output if the content of the output itself changes. In our C example, if we were to change the comment in from to , the compiled object file would still be byte-for-byte identical, as the comment does not affect the compiled output. In the ideal world, the linking of would not need to be redone, as its inputs have not changed in content. By default, Nix uses the extensional (input-addressed) model. If we edit the comment and rebuild: Everything rebuilt. 😩 The store path in the extensional model is a hash of the recipe , and the recipe for includes the recipe for . Recursion is fun! Change one byte anywhere upstream and every path downstream changes with it. 🌀 Warning The two binaries are not even byte-identical: the cc-wrapper puts in the , so the binary contains its own store path. The extensional model leaks into the bytes. 🙃 If we enable the build to use content-addressed derivations we observe rebuilt, but did not. 🎉 You can read demystifying Nix’s intensional model for a more detailed explanation of how CA derivations work, but the short version is that Nix rewrites to point at ’s content-addressed output instead of . The resolved is the same one we built before the edit. Since no “input” changed, Nix avoids the rebuild. This is the same behavior as Bazel and buck2, which are intensional by default. If we edit the comment and rebuild with Bazel or buck2, we see that the compile ran, but the link was an action cache hit . Bazel and buck2 do not have an input-addressed mode. They always use the intensional model. An action’s key is a hash of its command line (to force rebuilds) and the content digests of its inputs. A change only travels as far as the bytes actually change. This optimization is called early cutoff , and it is the whole selling point of the intensional model. There is a clear mapping between Nix’s CA derivations and Bazel’s action cache. A resolved derivation is a Bazel/buck2 action. 🤯 You may see the output paths in Bazel and buck2 and think they are extensional (i.e. ), but they are just a convenient place on disk. The real addresses are the digests. can even make this explicit with . Until dynamic derivations stabilize, people will continue to reach for Bazel and buck2 for the granularity on large builds. The intensional model is a big part of why they are so fast, and Nix has the same model. The two implementations are nearly identical in concept. Nix described the intensional model in 2006. Google started building on it the same year. Twenty years later, maybe it’s time they compared notes. 🥸

0 views
Farid Zakaria 1 weeks ago

Rewinding by fast-forwarding

Debuggers are an incredibly powerful and useful tool, but they mostly show you only the present and let you move forward. 1 Inspecting the present can help you understand the past, but is that a limitation we must accept? What if you could travel back in time to see what happened? What if you could see the exact moment a value was written, and who wrote it? What if you could run your debugger backwards ? Rewind is a deterministic virtual machine that records a program’s execution once, and then lets you replay it identically, many times. This lets you run the debugger backwards, and see the history of a value in memory, including who last read and wrote it. Turns out that you can go backwards by fast-forwarding. Going backwards changes how you debug: you can see how a value got there, not just what it is now. In who wrote this byte? found the program that wrote a byte of a file. That was the easy case. Every write to a file goes through the kernel, and Rewind’s kernel logs each one. Writes to memory don’t go through the kernel, so there is no log to read. So instead we go backwards, by running forwards again . This is how can tell us who last read and wrote a value in memory, and it is the same trick that lets gdb run backwards as well. Let’s see how it works. Aside: New to Rewind? Start with a flaky build you only catch once and dafuq is a deterministic VM? Let’s use the example from Nix wrote half of my debugger . Two tellers each deposit 10, twenty times, into one account: In our example, crucially, there is no lock around the read and write of . If the other teller runs in between, one of the deposits is lost. runs the program under different thread schedules until one fails: narrows schedule 1’s failure down to steps 3,245 and 3,246 and records that run, , which is the one we will dig into. We expected 400 and got 310. Nine deposits are gone. 😬 Our program prints the balance at step 3,291. We can run at that step and the variable 2 to see who last wrote it: Rewind goes “backwards” through the run, looking for the last write to that value. We can see that the last write was at step 3,282, by teller 2 (thread 141) on line 41. But wait, 300 + 10 is 310. That write is fine! 🤔 The last write is rarely the bug. The money went missing earlier, when a teller wrote a value it had read much earlier. We need to augment with the reads too, to see that. lists every read and write of the value, back to the start of the process. Here are the rows around where it goes wrong: Reading the chronology, we can see that teller 2 read the balance at step 3,248, and then teller 1 made nine deposits, taking the balance from 110 to 200. Then at step 3,263 teller 2 wrote its stale value of 120, overwriting the balance and losing the nine deposits (90). 💣 In this example, the bug is obvious, but in a real program it can be hard to find. The option shows you the whole history of a value, and you can often see where it went wrong without ever setting a breakpoint. You can even see the bug in the plot of the balance over time: The example is simple and the fix is obvious: a lock around the read and write. In a real program, the bug can be subtle and the fix complex. Seeing the history of a value, and who last wrote it, can be invaluable in tracking down the root cause. The Rewind app gives the same information but in a more interactive way. The source panel underlines every value that can watch: You can click on the value to see who wrote it, and then click Show reads too to see the whole history of that value. Show reads too draws every access, one lane per thread. Teller 2’s lone read sits in the middle of teller 1’s deposits, and that one dot is the bug. 🙌 If you would rather drive, can go backwards too by setting a watchpoint and . Here it is forked at step 3,264, just after teller 2’s stale write: You can navigate the stack, inspect variables, and step backwards with and . How does this all work? How do you run a VM backwards? You don’t. 😅 Rewind replays are completely deterministic: the same run produces the same result every time. Turns out that a simpler way to go backwards is to run forwards again, but stop one instruction sooner than last time. That is all and do. Rewind keeps a checkpoint of the machine at the start of a step. It rewinds to that checkpoint and then runs forward back to the step you want to inspect making note of every read and write along the way. If no reads or writes are found, it rewinds to the previous checkpoint and runs forward again. It keeps doing this until it finds the last read or write before the step you want to inspect. 3 keyframe keyframe step 3291: who wrote balance? 1 restore the latest keyframe before the step 2 replay forward, debug registers watching balance 3 the last trap is the answer: step 3282, teller 2, 300 → 310 teller 1 writes teller 2 writes no trap in the window? do it again from here Deterministic replay is what makes this work, and it keeps the implementation simple: going back is just going forward again from earlier. I’ve been having a lot of fun debugging my own programs this way. It’s a bit like time travel without the paradoxes. You can see the whole history of a value, and who wrote it, without setting a breakpoint and restarting the program. It’s git blame for your program’s memory. 🔍 Tools like rr and Undo record a process and let you run its replay backwards. Rewind records the whole machine, the kernel included, so the same inputs make the same run every time.  ↩ The expression can be a variable, a pointer dereference, or a struct field.  ↩ A step can be millions of instructions, so this can take a little bit.  ↩ keyframe keyframe step 3291: who wrote balance? 1 restore the latest keyframe before the step 2 replay forward, debug registers watching balance 3 the last trap is the answer: step 3282, teller 2, 300 → 310 teller 1 writes teller 2 writes no trap in the window? do it again from here Deterministic replay is what makes this work, and it keeps the implementation simple: going back is just going forward again from earlier. I’ve been having a lot of fun debugging my own programs this way. It’s a bit like time travel without the paradoxes. You can see the whole history of a value, and who wrote it, without setting a breakpoint and restarting the program. It’s git blame for your program’s memory. 🔍 Tools like rr and Undo record a process and let you run its replay backwards. Rewind records the whole machine, the kernel included, so the same inputs make the same run every time.  ↩ The expression can be a variable, a pointer dereference, or a struct field.  ↩ A step can be millions of instructions, so this can take a little bit.  ↩

0 views
Farid Zakaria 2 weeks ago

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 . 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. 1 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. 2 Why branches, though? 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. The assembly equivalent contains a , a billion + (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 : 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 . The dashed line is one extra count per interrupt , and the instruction counter is almost perfectly on it. 3 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 . 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. 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 counter. This is the same approach popularized by the rr debugger. The rr paper calls it deterministic time .  ↩ The 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.  ↩ The fit is 0.94 rather than 1 because also catches the interrupts that land while and start up and tear down, before and after the loop runs.  ↩ exit time +5 µs +0 +5 µs +0, free! +5 µs +0 +5 µs 20 µs counter time +5 µs +2 µs +5 µs +1 s +5 µs +3 µs +5 µs 1.000025 s exit time: only exits move the clock. Work between two exits is instant. counter time: exits, plus 1 ns for every conditional branch of work. The counter time tries to account for the work whereas the exit time only advanced the clock on exits. 2 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. The assembly equivalent contains a , a billion + (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 : 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 . The dashed line is one extra count per interrupt , and the instruction counter is almost perfectly on it. 3 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 counter. This is the same approach popularized by the rr debugger. The rr paper calls it deterministic time .  ↩ The 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.  ↩ The fit is 0.94 rather than 1 because also catches the interrupts that land while and start up and tear down, before and after the loop runs.  ↩

0 views
Farid Zakaria 2 weeks ago

Reading the code is the hard part

I have been stress testing Rewind VM , a deterministic VM, to work through the kinks, bugs and dog-fooding the user-experience. Even having developed it myself, I continue to be wild-eye amazed at the magic of what it can do. Despite the magic, the ease of claiming to have a bug “reproduced deterministically”, and the ease of narrowing it down to a single step, the hard part is still reading the code and understanding why it failed. Rewind can tell you what went wrong, but it cannot read the code. This is a particular area that is ripe for AI assistance. Agents can already read the code and often find bugs. Unsurprisingly, when given a wealth of reliable data about what went wrong, they can pinpoint the bug in a way that is much more efficient than reading the code alone. The combination of deterministic runs and AI agents is incredibly powerful. 🪄 Finding the bugs in Rewind is easy. replays a test, script, or binary under many different thread schedules until one fails, then narrows the failure down to the single step. That leaves you, though, with a step number and potentially a large codebase, one you are unfamiliar with. The hard part is reading the code and understanding why it failed. Rewind can tell you what went wrong, but it cannot read the code for you. Rewind does however give you, or an agent , a lot of information about what went wrong. I pointed Rewind VM at a cornicopia of tools, and unsurprisingly, it found bugs… many bugs . The best part is that it found them in a way that is reproducible and debuggable, which has led to the agents also easily providing the fixes as well. 1 Aside: New to Rewind? Start with a flaky build you only catch once and dafuq is a deterministic VM? This is a small example of a bug that Rewind found in git, and how I used Rewind to find the bug and the line of code that caused it. The bug is in , which attaches a note to a commit without changing the commit. The bug is that two notes, on two different commits, at the same time, can lose one of the notes. 2 attaches a note to a commit without changing the commit. We can start with an idea for a simple test 3 : create two notes, on two different commits, at the same time concurrently. When executed by Rewind, fifteen of thirty-two schedules lose a git-note, yet every still exits successfully. 4 A run in Rewind is a full trace of the build: every process, every file it wrote, and any file’s contents at any step, that you replay to any point in time. That is a lot of data . Rewind does make it a little simpler to comb through the data though that help narrow the culprit. what ended differently? rewind diff who wrote it, and what did it read? rewind blame which line wrote it? rewind where None of those three commands knows anything about git, locks or races. They work on any program. compares the files the two runs left behind. This is like diffoscope but on steroids 💉: it can compare any two runs, and it can compare the files at any step in the run, not just the final outputs. 5 Our clue is that is the ref that points at the latest notes commit, and it points at different commits in the two runs. takes two runs and a file: In this example, Rewind has given us pretty close to the smoking gun. The second read the notes before the first one had saved its own, then saved its version over the top: a read-modify-write race. We can visualize this exact step in the Rewind GUI at the deciding step: both processes are alive (top box), and the first is halfway through saving, with its lock file written but not yet renamed into place (bottom box). If we have access to debug symbols, which Nixpkgs provides, shows where in git’s own code a process was at a step. Here is pid 56 when it wrote the ref: We can then look at the code at a very specific line, and try to understand why it failed. In this case, updates the ref without checking that it still points where it did when the command loaded the notes with a lock. Three questions, three commands, and I read one line of git. 🤓 The git notes failure is 2,936 steps and 1,937 events in one run, and made 33 runs. Going through one run is a lot of work, and going through all thirty-three is unrealistic. Recently, a friend told me AI has been really useful for parsing the CAN bus of cars. The CAN bus is a firehose of messages from the car from every sensor, every button, every switch, and every light. LLMs have made managing the firehose of data easier. I see the same emergence in Rewind. The run is also a firehose of events, and similarly, LLMs can help parse the firehose of events and find the bugs. Telling an LLM to investigate a bug with Rewind has been very effective. Narrowing the bug down to a single step and source lines, is especially helpful for an LLM as it keeps the context small and focused. At that point, the LLM can read the code and understand what went wrong, and very likely suggest a fix. LLMs have a lot of stochasticity built into them. I have found that pairing them with more deterministic technologies such as Nix and Rewind makes them more effective. I’m very optimistic about the leveraging the combination of deterministic runs and LLMs to find and fix bugs in large codebases. LLMs induce many of these bugs but now they can also fix them. 🙃 You can find all the bugs on the bugs page .  ↩ I submitted an upstream patch for the bug as well.  ↩ This test demonstrates the race condition in when adding notes concurrently. We can easily build this as a Nix derivation using .  ↩ On a normal Linux machine, 25 of 30 runs lose one too, so this is not a Rewind-onlybug.  ↩ I have a lengthier post about how Rewind can help make your build bit-for-bit reproducible.  ↩ who wrote it, and what did it read? rewind blame which line wrote it? rewind where None of those three commands knows anything about git, locks or races. They work on any program. What ended differently? compares the files the two runs left behind. This is like diffoscope but on steroids 💉: it can compare any two runs, and it can compare the files at any step in the run, not just the final outputs. 5 Our clue is that is the ref that points at the latest notes commit, and it points at different commits in the two runs. Who wrote it, and what did it read? takes two runs and a file: In this example, Rewind has given us pretty close to the smoking gun. The second read the notes before the first one had saved its own, then saved its version over the top: a read-modify-write race. We can visualize this exact step in the Rewind GUI at the deciding step: both processes are alive (top box), and the first is halfway through saving, with its lock file written but not yet renamed into place (bottom box). Which line wrote it? If we have access to debug symbols, which Nixpkgs provides, shows where in git’s own code a process was at a step. Here is pid 56 when it wrote the ref: We can then look at the code at a very specific line, and try to understand why it failed. In this case, updates the ref without checking that it still points where it did when the command loaded the notes with a lock. Three questions, three commands, and I read one line of git. 🤓 Who reads all of this? The git notes failure is 2,936 steps and 1,937 events in one run, and made 33 runs. Going through one run is a lot of work, and going through all thirty-three is unrealistic. Recently, a friend told me AI has been really useful for parsing the CAN bus of cars. The CAN bus is a firehose of messages from the car from every sensor, every button, every switch, and every light. LLMs have made managing the firehose of data easier. I see the same emergence in Rewind. The run is also a firehose of events, and similarly, LLMs can help parse the firehose of events and find the bugs. Telling an LLM to investigate a bug with Rewind has been very effective. Narrowing the bug down to a single step and source lines, is especially helpful for an LLM as it keeps the context small and focused. At that point, the LLM can read the code and understand what went wrong, and very likely suggest a fix. LLMs have a lot of stochasticity built into them. I have found that pairing them with more deterministic technologies such as Nix and Rewind makes them more effective. I’m very optimistic about the leveraging the combination of deterministic runs and LLMs to find and fix bugs in large codebases. LLMs induce many of these bugs but now they can also fix them. 🙃 You can find all the bugs on the bugs page .  ↩ I submitted an upstream patch for the bug as well.  ↩ This test demonstrates the race condition in when adding notes concurrently. We can easily build this as a Nix derivation using .  ↩ On a normal Linux machine, 25 of 30 runs lose one too, so this is not a Rewind-onlybug.  ↩ I have a lengthier post about how Rewind can help make your build bit-for-bit reproducible.  ↩

0 views
Farid Zakaria 3 weeks ago

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 . 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 . 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. 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. 1 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 ( ). 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: 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. 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: 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. 2 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. 😅 Intel’s counter is good enough that you can single-step the rest of the way to the exact instruction. I have an AMD laptop. 🙃  ↩ costs no real time. The monitor jumps its clock straight to the deadline and delivers the timer interrupt.  ↩ 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. 1 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 ( ). 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: 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. 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: 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. 2 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. 😅 Intel’s counter is good enough that you can single-step the rest of the way to the exact instruction. I have an AMD laptop. 🙃  ↩ costs no real time. The monitor jumps its clock straight to the deadline and delivers the timer interrupt.  ↩

0 views
Farid Zakaria 3 weeks ago

Who wrote this byte?

git blame for your build’s bytes. 🔍 A build is bit reproducible when the same inputs give the same bytes. Why does reproducibility matter? They provide certainty that software is genuine and has not been tampered with. See reproducible-builds.org . Nix is infamously not bit reproducible, but rather input-addressed : the hash of a package is calculated from the inputs rather than the output. We still prefer though to have bit reproducibility, because it allows us to verify that the package we downloaded is the same as the one built from source. It is something many packages aspire to achieve. When the outputs differ, you want to know why. The first step is to find the bytes that differ, and the second is to find the program that wrote them. Finding the cause of a difference has traditionally been the challenging part of process making builds reproducible…until now! I have been building Rewind VM , a deterministic virtual machine that can record and replay builds, and it now has a new command to find the program that wrote a byte that differs between two runs: . Aside: I wrote about Rewind VM first in a flaky build you only catch once , and then about properties . Let’s see how it works, first with a small example. Let’s start with a made-up library, , that writes its pkg-config file with a short Python script. 1 The script collects the packages the library links against into a : Python iterates a set of strings in an order drawn from its hash seed , which is random for every new process. In Rewind the seed is an input: decides every random number the build draws. Let’s build under eight seeds: The third column from the end is the start of the output’s hash (i.e. ), and the last is the run id. We did eight builds and got five different outputs. 😬 Our build is not reproducible. shows what differs between two runs, without leaving Rewind: You could ascertain this from tools like diffoscope but would be left to figure out what program wrote the differing bytes. does that for you. takes two runs and a file, and names the program that wrote the first byte that differs: The output is a little long, but it is all relevant and the first line has the answer: wrote that byte at step 2,909. 2 The rest of the text is how the tool determined the provenance of the byte change. The tool highlights that the difference was made inside python3, and we know that the seed is the one input that changed. 🎯 $out/…/tiles.pc differs at byte 178 install copied it, step 3,157 its source already differed: not the cause /build/tiles/tiles.pc python3 wrote byte 178, step 2,909 the first writer: the difference starts here python3 gen-pc.py same command line same gen-pc.py in both runs → the cause is inside python3: its hash seed The fix is straightforward, we wrap the list with , and every seed then builds the same . 🙌 How can the command deduce the lineage of a byte? The trick is that blame does not have to search for the write. The run already recorded it.😯 Every Rewind run records each program’s starts, exits, opens for writing and renames, each at its step. 3 For , the guest’s Linux kernel also keeps two kinds of record: The records are written to a buffer in the guest kernel’s memory, a 1MiB buffer, and Rewind copies them into at the intervals it has stop the VM anyways. This keeps the runs identical and performant. write open step step step buffer buffer buffer trace.bin: the records, saved with the run I measured the cost of the records in Rewind 0.9.0, and it is small enough to leave them on for every run. With the records, blame finds the write that set the byte by reading the trace, without replaying either run. It only replays to read a file’s contents at a step. The Rewind app shows the same thing visually. Open the two runs side by side: The Compare tab now lists the files that differ between the two runs: We can also click a file to see it from both runs. Here that is step 2,909, with in the process tree and its command in the build log: At that moment, we can explore the complete VM state: the files as they were, the process tree, a fork, or gdb. The app shows the same information as , but visually and interactively. In order to capture possibilities of non-determinism, we need to vary any input that can change the output. The seed decides random numbers. also varies the schedule , the order threads take turns, which is how parallel and end up with different outputs. Turns out there is a third input that can change the output: the order of directories. The order of files in a directory is not guaranteed to be the same across machines, or even across runs on the same machine although many builds assume it to be. We can also vary the order of directories in Rewind which helps catch even more non-determinism with . This is useful for builds that depend on the order of files in a directory. writes an index of the plugins it ships, in the order returns them. It builds the same output under every seed, but not under every directory order: 4 We have four directory orders, and four different outputs. Each one lists the same five plugins in another order: The fix is the same as before: , and every key builds the same index. Look closely and both examples are the same bug. Python iterates a set in hash order, and ext4 lists a directory in hash order. Change the seed behind the hash and the order changes with it. Finding the cause of a difference has traditionally been the challenging part of process making builds reproducible. Many tools exist to help detect nondeterminism but few actually give you the root cause. Lowering the barrier to making builds reproducible is a goal of Rewind VM, and is a step in that direction. Rewind VM is purpose built to work in the Nix ecosystem and helping make more Nix packages reproducible is a worthy goal. If you want a deeper dive on this subject, check out the reproducible builds tutorial , which walks through both examples step by step, including the directory-order one. If you maintain a package that does not reproduce and you do not know why, try blame on it, and tell me what it finds. I would love to add it to the leaderboard . 🏆 nixpkgs sets that circumvents this bug.  ↩ The output is real, with long lines wrapped to fit and the store path shortened.  ↩ A step is a moment the virtual machine stops and hands control to Rewind, such as when a program starts or writes to the terminal. Step 2,909 is the same moment every time you replay the run.  ↩ It is the second example in the reproducible builds tutorial .  ↩ The file in was copied there by . The file it copied from already differed, so the copy is not to blame. That file, , was first written by pid 112. It was still when it opened the file for the redirect, and then became . One write of 227 bytes set byte 178. had the same command line in both runs, and the only file from the build it read, , was the same in both runs. install copied it, step 3,157 its source already differed: not the cause /build/tiles/tiles.pc python3 wrote byte 178, step 2,909 the first writer: the difference starts here python3 gen-pc.py same command line same gen-pc.py in both runs → the cause is inside python3: its hash seed The fix is straightforward, we wrap the list with , and every seed then builds the same . 🙌 How it knows How can the command deduce the lineage of a byte? The trick is that blame does not have to search for the write. The run already recorded it.😯 Every Rewind run records each program’s starts, exits, opens for writing and renames, each at its step. 3 For , the guest’s Linux kernel also keeps two kinds of record: a write record for every write to a file: which thread, which file, where in the file and how many bytes; an open record for every file a program opens, for reading or for writing. step step step buffer buffer buffer trace.bin: the records, saved with the run I measured the cost of the records in Rewind 0.9.0, and it is small enough to leave them on for every run. With the records, blame finds the write that set the byte by reading the trace, without replaying either run. It only replays to read a file’s contents at a step. In the app The Rewind app shows the same thing visually. Open the two runs side by side: The Compare tab now lists the files that differ between the two runs: We can also click a file to see it from both runs. Here that is step 2,909, with in the process tree and its command in the build log: At that moment, we can explore the complete VM state: the files as they were, the process tree, a fork, or gdb. The app shows the same information as , but visually and interactively. Beyond seeds In order to capture possibilities of non-determinism, we need to vary any input that can change the output. The seed decides random numbers. also varies the schedule , the order threads take turns, which is how parallel and end up with different outputs. Turns out there is a third input that can change the output: the order of directories. The order of files in a directory is not guaranteed to be the same across machines, or even across runs on the same machine although many builds assume it to be. We can also vary the order of directories in Rewind which helps catch even more non-determinism with . This is useful for builds that depend on the order of files in a directory. writes an index of the plugins it ships, in the order returns them. It builds the same output under every seed, but not under every directory order: 4 We have four directory orders, and four different outputs. Each one lists the same five plugins in another order: stock order sharpen rotate resize crop blur dirents=1 sharpen crop blur rotate resize dirents=2 sharpen resize crop rotate blur sorted() blur crop resize rotate sharpen The fix is the same as before: , and every key builds the same index. Look closely and both examples are the same bug. Python iterates a set in hash order, and ext4 lists a directory in hash order. Change the seed behind the hash and the order changes with it. Try it Finding the cause of a difference has traditionally been the challenging part of process making builds reproducible. Many tools exist to help detect nondeterminism but few actually give you the root cause. Lowering the barrier to making builds reproducible is a goal of Rewind VM, and is a step in that direction. Rewind VM is purpose built to work in the Nix ecosystem and helping make more Nix packages reproducible is a worthy goal. If you want a deeper dive on this subject, check out the reproducible builds tutorial , which walks through both examples step by step, including the directory-order one. If you maintain a package that does not reproduce and you do not know why, try blame on it, and tell me what it finds. I would love to add it to the leaderboard . 🏆 nixpkgs sets that circumvents this bug.  ↩ The output is real, with long lines wrapped to fit and the store path shortened.  ↩ A step is a moment the virtual machine stops and hands control to Rewind, such as when a program starts or writes to the terminal. Step 2,909 is the same moment every time you replay the run.  ↩ It is the second example in the reproducible builds tutorial .  ↩

0 views
Farid Zakaria 3 weeks ago

No quarter for gaps

The advent of large language models has changed the economics of closing gaps in software stacks. This is in the nixpkgs manual, in the Ruby section, under “Platform-specific gems” [ref] . The pull request ( PR#68 ) it points to was opened in October 2019 and closed, unmerged, in August 2026, with: “Closing as stale. I no longer work with bundix. Feel free to take it over.” [cite] Aside There are alternatives that have sprung up but they all have unique gaps or are not widely communicated as blessed solutions. The manual itself also does recommend a workaround for the issue, but I found it to not work in practice. Every ecosystem has gaps everyone has learned to step around. They survive because there is just too much stuff to do. We live with these warts and gaps because the cost of fixing them is either too high or there are more important things to do. That economics is gone. We can have and expect amazing perfectly correct software stacks, because the cost of fixing gaps is now low enough that it is worth doing. The economics of software have changed. The multiple days of typing are now an afternoon, or less , of directing and reading to an AI agent. In the case of Nix and Ruby, I wrote the Nix side of a Bundler lockfile solution, gemlock.nix , within an hour, removing days of misery I hit while running this blog. While AI generated code may suffer from slop, it is a growing skill how to wield AI to produce correct verifyable code. Nix is amazingly well-suited as it gives the agents a reproducible test-bed with which to verify the correctness of the code they produce. The economics of software have changed, and we can now expect to have no quarter for gaps in our stacks.

0 views
Farid Zakaria 1 months ago

Always, sometimes, never

Exit 0 means your program exited 0. That’s it. That’s all it means. 🍞 I have been working on a deterministic VM called Rewind VM , where “a run” (i.e. test, command etc.) is a function of its inputs including the thread schedule. The determinism comes from the tool recording every step which lets you replay it exactly. This alone is a pretty good way to find flaky tests: run the test under Rewind, then runs it under many different thread schedules, with some slight latency added, and failures often crop up. 🐛 Feedback however was that it was not enough: the tool could find a failing schedule, but it could not tell you if that schedule was actually a bug. It only knew that the run ended differently than the original schedule, which could be a crash, a timeout, or just a different exit code. That is not enough to say “this is a bug”. Someone pointed out that I had built most of a property-based testing tool, but I only had one property: matching exit codes. What is property-based testing ? If you have used QuickCheck or Hypothesis , you have already used the idea. You write a property, or constraint, that must hold for every input. The tool generates lots of inputs, and when one breaks the property, it shrinks it down to the smallest input that still fails. already did the generating and the shrinking. The inputs are thread schedules, and narrowing shrinks a failing schedule down to the one step that causes the failure. The only property though was “the run ends the same way schedule 0 did”: the same exit code and the same outputs. That’s a pretty low bar, but easy to improve. 🙃 Rewind now lets specify properties that must be true for every run, or must be true for at least one run, or must never be true in any run. Let’s keep the bank from last time : two tellers deposit into one account from two threads, without a lock . This time the example is in Java as a JUnit 5 suite to appeal to my Enterprise brethren. 1 A teller that runs between the other’s read and store writes a stale balance over the other’s deposit. 💥 We include a “typical” test suite: one teller, two tellers concurrently, and a new account being empty. We run it and see all tests pass and head home for the day. 🍺 Is the code correct? Let’s use Rewind to dig further. Before even looking at the balance, Rewind knows a lot about what a run did . Every open, write, rename, close, fork and exit is in the trace, with the step it happened at. Rewind ships properties computed from the trace alone: Let’s throw a few at the bank and only run schedule 0: Interesting! writes its performance counters to 2 . It has nothing to do with our bug, but I included it because I learned something new and it could have been a bug if it did not include the process ID. The file properties shine for bugs between processes. The properties tutorial has a program that rewrites its config in place while another process rereads it. Its own test fails only when a read lands between the truncate and the last write, but flags it on the very first run. 😲 The bank’s real invariant is not in any syscall though. It lives in memory in our example: the balance variable must add up . For that there is the Rewind SDK , a tiny library you call from your program. Each call writes one line to , a device in Rewind’s VM, and the trace keeps it with the step, process and thread that wrote it. 3 must be true every time the program reaches it. is its opposite: a run that reaches it at all fails. These are your typical , except we get the whole replay if it fails. is the one I find the most interesting and tough to think through at times. 🤓 It tests the search: its condition must be true in at least one of the runs check tries, and it never fails a run. In model-checking terms, is a safety property (nothing bad happens in any run) and is a reachability property (some run gets there). Here it asks whether any run had both tellers inside at the same time. Look at the output above again: The suite passed under schedule 0, but one teller always finished its deposit before the other started. That pass told us nothing about the race. 🤷 Let try its default 64 schedules: That took 40 seconds on my laptop 4 and we found that two deposits went missing. The first line is the again: of the 17 runs check tried before it found the failure, 11 had both tellers inside at once. The fix is the obvious one: hold a lock from the read to the store. Every schedule passes, but is that enough to make us feel warm and fuzzy? The line is what gives me the warm embrace: in 42 of the 65 runs the tellers ran concurrently, but the lock prevented the bug. ✅ 5 A condition that is only true when the bug happens can never be true once the bug is fixed. 💡 Java developers though love writing JUnit tests. Fear not my FizzBuzzEnterprise colleagues, Rewind has you covered: the SDK has a JUnit 5 extension. Put on the test class and it marks each test’s start and result. If you can’t touch the code, reads the XML reports the runner wrote instead: Maven’s surefire, Gradle, pytest’s , whatever writes the format. The Rewind app shows the timeline of a run, with the tests and the build log. The failing test is red, and the event card names the assertion that failed. The strip under the timeline has a span per test: green passed, red failed. Each include a helpeful tooltip with the test name and the steps it ran. All the other Rewind features can then be used to help isolate the cause: the source panel, gdb on a fork at any step, the thread lanes and Check from here. There is a SDK for many languages already included in the Rewind repository. They are tiny, and the only dependency is the Rewind VM itself. The SDK is a single file or two per language, and you can copy it into your project. 6 The properties tutorial goes through each piece step by step, and the advanced tutorial has script properties and a file of properties to keep beside your tests for the more adventurous. If you happen to find any interesting bugs with Rewind let me know. I am keeping track of a small leaderboard of the best ones. 🏆 It is in the Rewind repository, next to the C version.  ↩ turns it off.  ↩ Outside Rewind the device does not exist and every call does nothing, so the calls can stay in your code.  ↩ The JVM is chatty: 148,479 steps for three tests, where the C equivalent takes about 4,500.  ↩ This counter must sit outside the lock. With , the second teller would wait before it reaches the counter.  ↩ The SDK’s README has the format instrunctions if you want to write one for another language.  ↩ C and C++ : , Go : and for Python : , and a pytest plugin that loads itself Java : and the JUnit 5 extension It is in the Rewind repository, next to the C version.  ↩ turns it off.  ↩ Outside Rewind the device does not exist and every call does nothing, so the calls can stay in your code.  ↩ The JVM is chatty: 148,479 steps for three tests, where the C equivalent takes about 4,500.  ↩ This counter must sit outside the lock. With , the second teller would wait before it reaches the counter.  ↩ The SDK’s README has the format instrunctions if you want to write one for another language.  ↩

0 views
Farid Zakaria 1 months ago

Nix wrote half of my debugger

A few days ago I wrote about Rewind VM , a deterministic VM where every run of a Nix build is a pure function of its inputs, thread schedule included! I have been using it to find, reproduce and solve numerous race conditions in Nix builds, but it’s been making me feel a little crazy . What is this superpower, and why is nobody else using it? The tool has quickly grown a source panel, stack frames, bookmarks, a “Compare” tab, a lot more gdb support, thread lanes, which show who held the CPU at every step, and “Check from here”, which helps find the exact step where a race condition happens. I went into each new feature thinking it would be a big code-lift but I kept running into the same thing: the hard part of each feature was already done, and Nix had done it. A debugger for instance, needs the exact inputs of the program, its debug symbols, its sources, the sources of every library under it, and a way for someone else to get all of that on their machine. That’s exactly what a derivation is, and Nix makes that easy. A classic simple example of a race condition is two threads depositing into one bank account. Each deposit reads the balance, writes a line to the ledger, then stores the balance plus the deposit. If one teller runs between the other’s read and store, it writes a stale balance over the other’s deposits. 💥 A teller that runs between the other’s read and store writes a stale balance over the other’s deposits. 1 teller 1 balance teller 2 read 150 read 150 store 200 store 150 + 10 160 teller 1's last deposit is gone Rewind’s VM has one CPU, so its first run passes too. runs the build again under perturbed schedules, each asking the guest kernel to reschedule at different steps, and narrows the first failure down to one step: Running this check on my laptop took 11 seconds. The two runs are the same machine, exit for exit, until step 3237, where only the failing one gets a reschedule. The argument to is a derivation and can be a flake reference. The beauty of Nix is that it knows the inputs of a derivation, so that’s all we need to make sure the run is reproducible. The derivation’s inputs are the source, the compiler, the libraries, the kernel, and the VM’s configuration realises the derivation’s inputs, packs the closure into a read-only erofs image, and boots the VM on it. The run’s id is a hash of its inputs, the way a store path is, and prints the command that makes it again: When the build succeeds, the guest reports each output’s NAR hash, and checks it against the host’s copy and against every binary cache Nix substitutes from, by fetching only the : This helps us validate that the build within the VM is the same as the build on my laptop, and that the VM’s run is reproducible by Nix. Debugging code is much simpler when you are looking at the source. A new panel in the Rewind app or in the terminal shows the source of the program at the playhead, and the stack frames that called it. The debugger needs to know where the sources are, and Nix gives us that for free too. nixpkgs builds the packages with , and the debug info is cached on cache.nixos.org as a output. We can leverage debuginfod to fetch the debug info and the sources by build ID, so we can see the source of any binary in the VM, including the Linux kernel! 😲 Sometimes though, the source is not enough, and we need to see the state of the program. opens gdb on a fork of the run at the playhead, with every thread of the process. The debugger can set breakpoints, watchpoints, and inspect memory, registers and variables. At step 3249, just before teller 2 gets the CPU back, we can watch the variable and continue until it changes. Nothing gdb does changes the recording, and we can rewind to the same step and fork again, or fork at any other step, and gdb will see the same state. If gdb is not enough, opens a shell in the VM at a step with any package from nixpkgs on its . It is one more closure packed into one more image. Rewind makes it very easy to compare two runs. The Compare tab in the app, or in the terminal, shows the last shared events of both runs, and the first event that differs. The Compare tab puts both runs’ events side by side from just before they part, with what differs marked. Teller 2 starts from 150 in the failing run and from 200 in the passing one: Rewind’s VM has one CPU, so at any step exactly one thread is running. A race is a question of order: which thread ran when. The trace does not answer that directly. It records what threads did, a write, an open, a fork, an exit, a signal, but not who was running in the gaps between those events. Rewind can fill in the gaps without recording anything new. Every run replays exactly, so it can walk any stretch of a run one step at a time and, at each step, ask the guest kernel which thread is on the CPU. In the failing run, teller 1 (Thread 140) is interrupted at step 3238, halfway through a deposit: it has read the balance but not stored it. Teller 2 (Thread 141) gets the CPU for a single step, 3239, long enough to read the balance, and then teller 1 gets it back and finishes. 2 Finding one bad interleaving raises the next question: how likely is it? Is the passing run the normal case, or did it get lucky? normally answers that by building the whole derivation again under many schedules. With , it starts from a run you already have instead, at any step you pick_. It forks the run there once per schedule, each fork taking a different order of threads from that step on, and counts how many end differently. Everything before the step stays exactly as it was. We can apply this technique to the bank example, starting from the step where the two runs diverged, 3,221. When we run 16 schedules from there, all 16 lose money 3 : We can do the same thing from the Rewind App with “Check from here” in the context menu of the playhead. It forks the run at the playhead and runs each fork under a different schedule, counting how many end differently. bookmarks the playhead’s step with a note. Bookmarks are kept with the run, and they travel in its export, so the person I hand the run to opens it with my notes on the timeline: Each one is a derivation in the flake, with one bug and one fix: Most of the hard work of a debugger is already done by Nix. Rewind adds a little more, but the rest is already there: the inputs, the sources, the debug symbols, and a way for someone else to get all of that on their machine. When you start with something hermetic like a Nix derivation, you can get a debugger for free. On my 16-core laptop, lost money in 396 of 1,000 runs. Pinned to a single core with , it lost money in none of 1,000: one core alone rarely switches threads in the middle of a deposit, which is why Rewind perturbs the schedule.  ↩ It is a little hard to see since the event from Teller 2 is tucked underneath the Orange bar.  ↩ Schedule 0 is the run itself, which passed. Every other line is a fork, and is failing because the balance came up short.  ↩ read 150 read 150 store 200 store 150 + 10 160 teller 1's last deposit is gone Rewind’s VM has one CPU, so its first run passes too. runs the build again under perturbed schedules, each asking the guest kernel to reschedule at different steps, and narrows the first failure down to one step: Running this check on my laptop took 11 seconds. The two runs are the same machine, exit for exit, until step 3237, where only the failing one gets a reschedule. Free thing one: the inputs The argument to is a derivation and can be a flake reference. The beauty of Nix is that it knows the inputs of a derivation, so that’s all we need to make sure the run is reproducible. The derivation’s inputs are the source, the compiler, the libraries, the kernel, and the VM’s configuration realises the derivation’s inputs, packs the closure into a read-only erofs image, and boots the VM on it. The run’s id is a hash of its inputs, the way a store path is, and prints the command that makes it again: When the build succeeds, the guest reports each output’s NAR hash, and checks it against the host’s copy and against every binary cache Nix substitutes from, by fetching only the : This helps us validate that the build within the VM is the same as the build on my laptop, and that the VM’s run is reproducible by Nix. Free thing two: every symbol and every source Debugging code is much simpler when you are looking at the source. A new panel in the Rewind app or in the terminal shows the source of the program at the playhead, and the stack frames that called it. The debugger needs to know where the sources are, and Nix gives us that for free too. nixpkgs builds the packages with , and the debug info is cached on cache.nixos.org as a output. We can leverage debuginfod to fetch the debug info and the sources by build ID, so we can see the source of any binary in the VM, including the Linux kernel! 😲 gdb, on a fork of any step Sometimes though, the source is not enough, and we need to see the state of the program. opens gdb on a fork of the run at the playhead, with every thread of the process. The debugger can set breakpoints, watchpoints, and inspect memory, registers and variables. At step 3249, just before teller 2 gets the CPU back, we can watch the variable and continue until it changes. Nothing gdb does changes the recording, and we can rewind to the same step and fork again, or fork at any other step, and gdb will see the same state. If gdb is not enough, opens a shell in the VM at a step with any package from nixpkgs on its . It is one more closure packed into one more image. Compare two runs Rewind makes it very easy to compare two runs. The Compare tab in the app, or in the terminal, shows the last shared events of both runs, and the first event that differs. The Compare tab puts both runs’ events side by side from just before they part, with what differs marked. Teller 2 starts from 150 in the failing run and from 200 in the passing one: Who had the CPU Rewind’s VM has one CPU, so at any step exactly one thread is running. A race is a question of order: which thread ran when. The trace does not answer that directly. It records what threads did, a write, an open, a fork, an exit, a signal, but not who was running in the gaps between those events. Rewind can fill in the gaps without recording anything new. Every run replays exactly, so it can walk any stretch of a run one step at a time and, at each step, ask the guest kernel which thread is on the CPU. In the failing run, teller 1 (Thread 140) is interrupted at step 3238, halfway through a deposit: it has read the balance but not stored it. Teller 2 (Thread 141) gets the CPU for a single step, 3239, long enough to read the balance, and then teller 1 gets it back and finishes. 2 Check from here Finding one bad interleaving raises the next question: how likely is it? Is the passing run the normal case, or did it get lucky? normally answers that by building the whole derivation again under many schedules. With , it starts from a run you already have instead, at any step you pick_. It forks the run there once per schedule, each fork taking a different order of threads from that step on, and counts how many end differently. Everything before the step stays exactly as it was. We can apply this technique to the bank example, starting from the step where the two runs diverged, 3,221. When we run 16 schedules from there, all 16 lose money 3 : We can do the same thing from the Rewind App with “Check from here” in the context menu of the playhead. It forks the run at the playhead and runs each fork under a different schedule, counting how many end differently. Bookmarks bookmarks the playhead’s step with a note. Bookmarks are kept with the run, and they travel in its export, so the person I hand the run to opens it with my notes on the timeline: Other examples to try Each one is a derivation in the flake, with one bug and one fix: : the deadlock from the last post. : the lost update above. : a SIGCHLD that arrives between a flag check and , so the parent sleeps until ’s ten second timeout kills it. : one process rewrites a config file in place while another rereads it. On many cores it fails nearly every time; on one CPU only some schedules land the reader between the truncate and the last write. On my 16-core laptop, lost money in 396 of 1,000 runs. Pinned to a single core with , it lost money in none of 1,000: one core alone rarely switches threads in the middle of a deposit, which is why Rewind perturbs the schedule.  ↩ It is a little hard to see since the event from Teller 2 is tucked underneath the Orange bar.  ↩ Schedule 0 is the run itself, which passed. Every other line is a fork, and is failing because the balance came up short.  ↩

0 views
Farid Zakaria 1 months ago

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

0 views
Farid Zakaria 1 months ago

Hiding my AI slop from my Nix friends

Warning If you are pissed off reading this, you can start here and work your way back. I am using AI a lot . I am public about my use of it and when required make the necessary disclosures: “Assited-By” trailers or having to say “I used an AI to help write this software” on every Discourse post. 1 For those of you in the “Anti-AI” crowd, it might surprise you to learn that those of us who enjoy using it also don’t want to read “slop”. I also don’t want anything I create to read like I used AI a lot. Commit messages, READMEs, code comments. I’m reading it also! Being a Nix person, my instructions to the agent are of course declarative. My (and Codex’s ) is generated by home-manager from agent-settings.nix . It has a whole section titled “Writing style: no LLM tells” that I stitched together from Wikipedia’s Signs of AI writing and Simon Willison’s LLM cliche highlighter . The code-style tries to ban many AI-isms as they emerge such as: “it’s not X, it’s Y”, “dvelve”, “byte-order”, minimal em-dashes and so forth. I even came across Fabien Sanglard ’s code style rules from this HackerNews thread that I have enjoyed incorporating as well. Why not have my agent write code that mimics engineers I admire!? Despite this, I still found my agents continuing to use these banned words and phrases. 😒 I was a little annoyed I had to keep re-prompting my preferred writing style but I often reflect on the bitter lesson and generally try to avoid any additional work while I wait for the model’s capabilities to improve. I was however surprised when upon one such occasion I realized that the agent itself had itself gotten frustrated at forgetting my writing style and turned it into a flake check. During the creation of omnibin.dev , I noticed the agent had created tools/check-prose.py to check for banned words and phrases in the source tree. It is a simple Python script that walks the repo and fails on a banned word, phrase, or a single em dash anywhere. I had begun setting up a distinct pattern of how I like my repositories laid out so it was funny to see it automatically include this check in the CI of my build. Despite the bitter lesson , I might try leveraging this check in my other repos. What I like about deterministic checks rather than a markdown context-file is that it’s verifyable and reproducible. I’m not left guessing whether the agent is following my style or not. I can run the check myself and see if it passes or fails. Let’s be honest with myself and do some introspection. How much has AI-isms crept into my writing? I applied the same check to my own blog posts. Clearly I was not a fan of em dashes in the last five years, then suddenly I found 21 uses in two, which happen to coincide with the proliferation of AI. 2 🤔 We seem to be all worried about how many em dashes are in our text. Goodhart’s law teaches us that at that point, that is no longer a good measure of AI slop. Treat each other kindly. Seems like whether or not you use AI, I feel more compelled just to disclose I did to avoid the “you didn’t disclose it” argument. Such is life.  ↩ The top offender is at 51 hits. I used it in 2021 and 2022 too. Some tells are just mine.  ↩ Seems like whether or not you use AI, I feel more compelled just to disclose I did to avoid the “you didn’t disclose it” argument. Such is life.  ↩ The top offender is at 51 hits. I used it in 2021 and 2022 too. Some tells are just mine.  ↩

0 views
Farid Zakaria 1 months ago

Every package is already installed

tl;dr; omnibin is a FUSE filesystem that puts every binary nixpkgs ever shipped on your . Nothing is installed. Nothing needs building. 0 bytes on disk until something actually reads a file. 😈 It’s 2026, why am I still installing packages individually? 1 Why must I go through the ritual of adding a package to my , running or succumb to the hellscape of . Nix gives us the power of having packages installed side-by-side without conflict. Why do I have to pick which ones I want to install? Why can’t I just have them all? What if the machine just had all of them? That is over fifty thousand 2 top-level binaries available on my , from 2013 to 2026 built by Nixpkgs , available on-demand, without installing anything. This is the magic 🧙‍♂️ of Nix , but it’s not restricted to Nix. Everyone seems to still love Docker and OCI , why am I still picking which base image to use? Why can’t I just have them all? Is this the ultimate agent harness? It’s a container with everything in it, right from the start. Try it at fmzakari/omnibin . Of course, I cannot forget our NixOS friends. You no longer have to curate your or , you can just have them all. What is “package management” if every package is already installed? Turns out that Hydra writes a file next to every single narinfo on cache.nixos.org that describes the contents of the archive as JSON: That metadata turns out to be the perfect index for a FUSE filesystem that can lazily fetch the NARs from the cache and unpack them on-demand. 🤓 None of this would mean anything without nixpkgs-multiverse , which already resolves any in nixpkgs history to the store path Hydra built for it on cache.nixos.org . When you combine the two, you get a filesystem that can answer the question “where is ” and then fetch it from the cache and unpack it for you, all without ever having to install it. I crawled all of it the files in under twelve minutes. 🤯 Once you have that, the filesystem writes itself: That is CPython 3.6.2, from 2017. That downloaded nothing , it is answered from the pre-crawled index. Agents are “a thing”. Making them useful is a thing. Making them useful without installing anything is a thing. If your agent tried to and stat every single entry, it would have a really bad time. There are 881,933 binaries in the tree, and it would take a long time to stat them all. To help the agents out a bit, lists only the bare names, one per executable, each resolving to the newest package that provides it. The versioned forms all resolve, but they are not listed. For example, resolves to the latest Python 3, which is 3.14.6 at the time of writing, but resolves to the 2017 version. For everything else there is the index, which is sitting right there in the mount: That UX is a little rough, so you can also use the CLI to query the index: Lastly, there is a /omnibin/README.md whose entire job is to tell whatever is exploring the filesystem to stop exploring the filesystem and query the database instead. 🤖 At this point it should be obvious, but you pay for this on startup for the first access. The first run took 2.7 seconds to fetch the NARs and unpack them, the second run was instantaneous because the store paths were already present. Other than that? Not really, which is pretty amazing. For any long-lived machine, you would expect your to already be warmed up with the packages you need, so the first access penalty is not a big deal. I remember one of the first things that blew my mind and sold me on Nix, was seeing a demo by @burke on comma . The capability to test a package, at a single nixpkgs revision, without “installing it”; revolutionary! I believe this to be a spiritual successor and I hope to imbue others with the same sense of wonder and amazement that I felt back then as a beacon of the power of Nix. The repo is at github.com/fzakaria/omnibin . Please responsibly. Yes, I am a little inspired after watching DHH’s keynote at RailsConf 2026 . I feel the same way about package management.  ↩ There are actually 881,933 binaries in the tree, but only lists the latest version of each binary. The versioned forms are still available, but they are not listed.  ↩ Yes, I am a little inspired after watching DHH’s keynote at RailsConf 2026 . I feel the same way about package management.  ↩ There are actually 881,933 binaries in the tree, but only lists the latest version of each binary. The versioned forms are still available, but they are not listed.  ↩

0 views
Farid Zakaria 1 months ago

A build graph that rolls dice

We are right around the corner from NixCon 2026 . Another year where I sadly won’t be present. I looked at the lineup and saw quite a few talks on dynamic derivations, along with some recent other posts on the topic such as cargo-dyndrv which had me thinking about revisting the topic since my earlier posts on the subject. I wanted to better understand the implications of dynamic derivations and how they change the build graph. Originally, I was focused on how it could replace the lang2nix style of build graph generation, but I realized that the implications are much broader than that. The graph does not need to be known up front. It can be defined as the build progresses. 🧐 What do I mean? Traditionally, Nix requires you to ask it to build anything and it will tell you exactly the steps it will take ahead of time as the “derivations” that comprise the build graph. This is an important property of Nix. It is what makes it possible to reason about builds without running them by understanding what will be built. Many Nix tools rely on this property via . For instance, nix-diff tells you why two closures differ without building either . Why does dynamic derivations change this? In functional languages it’s very easy to get abstract and use fancy words like “applicative” and “monadic” to describe the difference between types of computation. The difference is subtle, but it is profound. Nix traditionally was an “applicative” build system. Dynamic derivations make it a “monadic” build system. The difference is that in an applicative build system, the entire build graph is known up front, while in a monadic build system, the graph can be defined as the build progresses. 1 One way to think about the difference is to look at the type signatures of the two operations that define them: (applicative) takes a value known ahead of time and returns the result . You can see the entire graph before you run it. (monadic) takes , a function , to return . You cannot see the entire graph before you run it. Applicative can be thought of writing the shopping list before you leave the house. You read the recipe, you write down every ingredient, you drive to the store once. The list is a function of the recipe and nothing else. Monadic is a recipe with a step that says taste it, and if it is too salty, go buy a potato . You cannot write that shopping list up front. Whether the potato is on it depends on the saltiness, and the saltiness does not exist until you have already done some of the cooking. Nix used to be solely the former, dynamic derivations add the latter. Okay, I guess I should have said “Nix is now monadic in the scheduler”. Nix has always had bind in the evaluator. We have been doing monadic builds for years. We call it import from derivation . on a derivation output is a bind in exactly the sense above: what to build next is a function of a value that does not exist yet. The Nix evaluator cannot produce the graph without that value, and the only way to get it is to stop evaluating and run a builder. Unfortunately, this has a lot of footguns, such as causing to take ten seconds , and why nixpkgs bans the technique outright . Whereas import from derivation is a bind in the evaluator, dynamic derivations now adds bind in the scheduler. The difference is that the scheduler can run builders in parallel, ship them to remote machines, and it can substitute their results from a cache. The evaluator cannot do any of that. Dynamic derivations do not add the bind. The bind was always there. What changes is which layer performs it. 🤓 Many of the examples of dynamic derivations have been focused on build graph generation via lang2nix tooling, but I wanted to explore the implications of dynamic derivations in a more general sense. In the true monadic sense, the build graph can be defined as the build progresses. The next step in the build graph can depend on the result of a previous step. Here is a really simple example, & , that rolls a die and either stops or continues the chain by adding a new derivation step to the build graph. The depth of the chain is random, and the result of the build is how deep we got. Only the leftmost box exists when you run . Everything to the right of it is written by a builder, while the build is already underway. The general idea of this derivation is: Either way the file copied into is a , so works the same on a chain that stopped and a chain that kept going. 2 We can see the build graph grow in the denominator as the build progresses. If we try to introspect the graph with or , we get nothing. Since the graph is not known yet, our tools cannot see it. Dynamic derivations introduce a second graph that exists only after the build, and the ecosystem has no way to introspect it yet. I ran the build 900 times and logged the length of the chain. Rolling a six-sided die is one of the most classic ways to simulate geometric decay and we can see the results in the histogram below. The mean is 6.18, median 4, longest 46. The math maths. Every dynamic derivations demo so far, mine included, has been a build system: MakeNix for C, NpmNix for node, cargo-dyndrv for Rust, nix-ninja for ninja. That is a reasonable place to start but it does not capture the full power of the primitive. What other ideas can we explore? Mario. In Super Mario Derivations the attribute path is the button sequence and I have to supply the press count. The dynamic version emulates until Mario dies. The stopping condition is data, discovered mid-build, and the run is however long it turns out to be. Searching a state space. Swap the die for a predicate and you have a search where each frontier node is a derivation. Model checking, puzzle solvers, a fuzzer that only expands inputs which found new coverage. States you reach twice collapse onto one store path, and they survive a reboot. Crawling. Fetch a page, parse the links, emit one derivation per link. The frontier is discovered rather than declared, the crawl resumes because the store remembers every page already fetched, and the dependency graph of the result is the link graph. What are the bounds of this primitive? I don’t know. The size of the graph now is only limited by whether Nix stops emitting successors. There is no depth limit for the store layer, no equivalent. My longest honest chain in the die-roll was 46 deep, but I had rigged examples that went to 500. How far can it go? I am so brainwashed to thinking about making a plan before I start for my build systems, that the idea of making it up as I go is a little scary. 😨 The paper Build Systems à la Carte is the defacto read on this topic.  ↩ We actually need a depth parameter to avoid infinite recursion and so that the store-path of the derivations are different since they are content-addressed.  ↩ roll a six and we write a derivation that echoes the depth. Ordinary, nothing dynamic about it. This terminates the build graph. roll anything else and we write a passthrough : a derivation whose only job is , where is . The paper Build Systems à la Carte is the defacto read on this topic.  ↩ We actually need a depth parameter to avoid infinite recursion and so that the store-path of the derivations are different since they are content-addressed.  ↩

0 views
Farid Zakaria 2 months ago

Visualizing Nix closures

tl;dr seenix.dev lays every byte of a Nix closure out on a map, one pixel per byte, and lets you zoom from a whole NixOS system down to the hex of . Try hello , firefox or a GNOME desktop . Nothing runs on a server. With the advent of LLMs I keep tugging at any crazy question I ask myself. I know there is the anti-AI crowd and they will happily proclaim anything pursued in this vein as “slop” but I am feeling fortunate to be able to explore these questions. My recent itch was to ask “what does a Nix closure look like?” and to answer it in a way that is interactive and visual . I wanted to see the bytes, not just the store paths. I had come across binvis.io on Hacker News and I found it a compelling way to look at data. I personally never found a need for it, but I found it fascinating none-the-less. 1 The timing for this itch was perfect. I noticed a trending thread on X where a Python binary seemingly includes and . 🤷 I built that tool. You can check it out at seenix.dev . It is a single-page web app that runs entirely in your browser, with no server. It fetches the narinfos of a closure and lays them out on a map, one pixel per byte, and lets you zoom in to see the bytes themselves. We can visualize the closure of that binary, , and see if it really does include those two packages. Turns out it does not. The closure is 41 store paths and 234 MiB, with no and no among them. Turns out those dependencies are build-time and are not included in the final runtime closure. We can visualize much larger closures. Here is a GNOME desktop: 1,324 store paths and 5.3 GiB, each colour one package. That picture needed zero NAR downloads. It was laid out in 3 ms from the narinfos alone. 🤯 The “trick” I learned to make this visualization possible, is the Hilbert curve . A Hilbert curve is a single, unbroken line that folds back and forth such that it completely fills up a flat square. It is a fractal . Every store path in the closure is sorted by name (the root first) and their NARs are concatenated into one long line of bytes. The Hilbert curve folds that line into a square, so byte n is pixel n along the curve. The Hilbert curve has two properties that lend itself nicely to visualize binaries and as a result Nix closures: Bytes that are near each other in a file stay near each other on the map. A NAR is a single contiguous range of bytes, so a store path is a single contiguous region on the map. A file inside that store path is a smaller contiguous region, and a section inside that file is smaller still and so forth. Squares are just byte ranges. Here’s a tiny 4×4 map. Each number is the byte that lands on that pixel: That means we can easily place a store path on the map by knowing its starting byte and its size. That’s what makes the map cheap to draw. 2 The layout only needs each path’s , which every narinfo carries, so the whole map exists before a single NAR is downloaded. Hovering already tells you which store path you are pointing at, its size, its retained size (the bytes that would leave the closure without it) and a “why is this here” chain back to the root. As you zoom in, the NARs on screen are fetched from the cache and the color fills in. Here is ’s closure, most of which is glibc: Blue is printable ASCII, red is high bytes, green is control bytes and black is . The speckled top is machine code. The big solid blue area at the bottom is glibc’s locale data, which is plain text. Keep zooming and every pixel becomes a byte you can read. Hovering names the file inside the NAR, and for ELF files, the section. That is of , in your browser tab, fetched from cache.nixos.org , without any server . 😈 Does everything need a purpose? Sometimes something is fun to make and to use with no real purpose. For fun, I even added a Save PNG button, and it saves the view at the canvas’s full resolution. The ultimate ricing of your NixOS system: a pixel image of your desktop closure. Can Omarchy do that? 😎 Anything you can export works: Drop the file and see the map. You can provide additional Nix binary caches to fetch NARs from as well. The source is at github.com/fzakaria/seenix . Go look at something big. Build without purpose. Have fun. Aldo Cortesi’s writing on visualising binaries is a great resource on this.  ↩ This is why the world is always a power of four bytes. hello’s closure is 36 MiB, which fills a bit over half of a 64 MiB square, and the rest is drawn as background.  ↩ Aldo Cortesi’s writing on visualising binaries is a great resource on this.  ↩ This is why the world is always a power of four bytes. hello’s closure is 36 MiB, which fills a bit over half of a 64 MiB square, and the rest is drawn as background.  ↩

0 views
Farid Zakaria 2 months ago

Orange Site Vanity

“Curiosity is only vanity. We usually only want to know something so that we can talk about it” – Blaise Pascal, Pensées I enjoy writing. Most of the time I write for myself, or that is what I tell myself. The act of writing is me trying to deeply understand something and then recording my thought process. It has paid dividends already as I have gone back numerous times to reference myself. When I am honest with myself though, I deeply enjoy knowing when others read my work as well. Knowing that something I found interesting and insightful landed for someone else too is incredibly satisfying. If I could have helped someone understand something better while having done so for myself, pure joy. The peak of that vanity seems to be when the Hacker News crowd has deemed your content “worthy” to have made it on the front page . There is a sort of inner satisfaction when someone else messages me to let me know one of my posts has made it onto Mount Olympus. I have for years added Google Analytics tracking to my site to understand engagement but I rarely went any deeper with the metrics to understand it, until now! 🤓 I have put my vanity on public display by collecting metrics pertaining to my readership . 🪞 The numbers deflate the myth a little. As of writing, my writing has been submitted to Hacker News 127 times, and 26 of those reached the front page. Those 26 bought me 121 hours up there in total, under five hours each 1 , and exactly one ever touched #1. Mount Olympus turns out to be crowded, and difficult to climb. Turns out building the vanity site was itself rewarding. I got a better understanding of the metrics I am collecting through Google Analytics & Search Console. I also tied my writings to submissions to Reddit , Lobsters & Hacker News . The data is fetched offline and periodically updated via a GitHub Actions workflow and included in the site, of course, as a Nix derivation. Pascal was probably right. I tell myself I write to understand things, and that part is true, but I have now built a daily pipeline whose only job is to tell me who else was listening. Curiosity is only vanity. My curiosity now has a dashboard. A goal of mine is to have Fareed Zakaria mistaken for me instead of the other way around. 😅 A mean, which I have previously argued means nothing.  ↩ A mean, which I have previously argued means nothing.  ↩

0 views
Farid Zakaria 2 months ago

A Nix store is three functions

While building trynix I needed somewhere to host a store-path that did not exist on cache.nixos.org . 1 I wanted to demonstrate that non-Nixpkgs store paths could be booted just as easily. The only requirement seemed to be a lenient Cross-Origin Resource Sharing (CORS) policy, , because the fetch happens in JavaScript. Turns out that GitHub Pages sets that header on every file it serves. 😈 I committed the output of to my Git repository and voilà, I have a free Nix substituter. I seem to be late to the party on this discovery. tomberek’s github-store is a cache assembled out of GitHub release assets. 2 GitHub Pages or Releases are a static file server. It has no idea what Nix is. If a humble file server can be a Nix binary cache, what else could we use? Turns out that in order to be a Nix binary cache, you must implement only three simple functions. The Nix client does not care what medium you use to implement them although HTTP is the most common and included by default in CppNix 3 . Anything that can answer those three requests can be used as a remote Nix store . 4 The reason we can be this careless about transport is that Nix does not trust it. A narinfo’s signature ( ) field covers , , and . It does not cover , , or . Once the archive is fetched, Nix decompresses it and checks that the matches. This is the special sauce of how packages that were signed by cache.nixos.org can be fetched from any other binary cache as an intermediary, and the signature still validates. The field does not even have to be on the same host as the narinfo. It can be anywhere on the internet, and it can be a different protocol than HTTP. Nix does not care. The only thing that matters is that the archive fetched from has the same as the narinfo. For protocols that are not included by default in the Nix client, you can always write an HTTP proxy that translates the three functions to whatever medium you want. In research for this post, I found a few interesting ones. gachix : puts the archives in git’s object database. Git content-addresses and delta-compresses blobs already, so the store dedupes itself; the author reports roughly 82% smaller than the equivalent plain cache. DNS : I wrote a proof-of-concept that puts the narinfo and 4 KiB slices of the archive in TXT records. The narinfo is small enough to fit on one record but the archive needs to be chunked. pastebin : a pastebin can hold the narinfo and the archive. The narinfo is small enough to fit on one paste, but the archive needs to be chunked. Many pastebins have an expiry policy which acts as a natural garbage collector. nixcache-oci : uses an OCI registry to store Nix archives. infinite storage glitch : encodes data within a video and uploads it to YouTube. “Everything is available on npm” – Some person on the internet Unsurprisingly, npm is a great binary cache and it has some interesting properties for release management we can ab use. emits a directory and npm publishes directories: a match made in heaven. 💑 Let’s walk through a small example. It is dynamically linked against glibc, so the closure is five paths and roughly ~36 MiB: We copy it to a local cache, signed with our own key, and add the one file npm needs ( ): then dutifully packages our complete closure for us: is now a real package on the public npm registry. It is now a substituter you can point Nix at directly: Note We have to use to run the binary because is a chroot store and all the are still under . If we had relocatable binaries we could run it directly. That is Nix fetching the complete closure from npm and running it. 🤯 We can distribute Nix packages to non-Nix users, let the infection spread! As an added bonus, similar to Nixpkg and NixOS we can get nice “channel” semantics by using npm’s dist-tags. The tag is mutable and points to the latest version, while each version is immutable and points to a specific store path. The major downside of this approach is that npm ahs no incremental publishing. Every version is a whole tarball, so fifty closures sharing glibc upload glibc fifty times. We could fix that by publishing each store path as a separate package, and then having a small index package that points at them. Each store path would then be uploaded exactly once. I won’t build that though as it’s not in good faith to the npm ecosystem. What other store implementations can we find? I was also waiting for @domenkozar to enable CORS on cache.nixos.org so I could use it.  ↩ In order to be a Nix binary cache, the prefix is stripped from the field in the narinfo, because GitHub releases are a flat namespace.  ↩ You can write a Nix plugin to implement a new protocol if you wanted.  ↩ We will see that that they must not all be all on the same medium, protocol or domain even!  ↩ I was also waiting for @domenkozar to enable CORS on cache.nixos.org so I could use it.  ↩ In order to be a Nix binary cache, the prefix is stripped from the field in the narinfo, because GitHub releases are a flat namespace.  ↩ You can write a Nix plugin to implement a new protocol if you wanted.  ↩ We will see that that they must not all be all on the same medium, protocol or domain even!  ↩

0 views
Farid Zakaria 2 months ago

Review a pull request by booting it

tl;dr; trynix-preview is a GitHub action that comments a link on a pull request which lets you boot the PR’s build in the browser using https://trynix.dev . No servers, just browsers. I ended my earlier trynix post with a list of ideas I think we could accomplish now that we can boot arbitrary paths in the browser. The most obvious one was to let a reviewer boot a pull request’s build in the browser for testing, validation and feedback. That is now real. 🤯 A demo is worth a 1000 words: here is a pull request ( PR#31 ) against my sqlelf project, from a fork , with the comment our action left on it: Click the link and a Linux machine boots in your tab with that PR’s on . You did not clone anything, you did not build anything. No servers, no SSH, no VPN, no Docker, no VM, no cloud. Just a browser and a link. 😈 As with any GitHub action, it’s just a few lines to add to your workflow. The caveat is that you must have built and cached the path already, so the action can link to it. The action does not build or cache anything. The action publishes and builds nothing. Whatever already fills your cache keeps doing it, and the action’s whole job is to simply provide the store paths via and hand the cache’s URL and public key to the browser. It is not Nix cache provider specific, but I do recommend Cachix because it is free for open source up to 5GiB. 1 You can checkout my trynix.yaml workflow for the full example. You have to set in the step because the workflow runs on a fork’s pull request, and that has security implications. 2 If that is not your cup of tea, there is a version where a maintainer types on the pull request which kicks off the workflow. In either case, the workflow runs on the default branch and checks out the pull request’s code, so a fork cannot edit the workflow that builds it. Did I just upend all CI products by easily letting reviewers boot a PR? Unfortunately, no. 🥲 The performance for large binaries is pretty bad. Even with many of the improvements I AI-assisted into the engine, large binaries can still take 1-2 minutes to execute. 3 Nevertheless, this is still a pretty amazing workflow and showcases the power of Nix. Maybe as we get closer to AGI, our AI overlords will be able to optimize the engine to execute large binaries in a few seconds, but for now, the action is best suited for small to medium-sized binaries. You should definitely sign up for Cachix but you can test this out without it since the free tier is very generous.  ↩ I recommend a private segregated cache for pull request builds, so that a fork cannot push to your main cache.  ↩ I added a benchmark page, https://trynix.dev/bench/ , to the site with a lot of rich data on boot and run times for various applications.  ↩ You should definitely sign up for Cachix but you can test this out without it since the free tier is very generous.  ↩ I recommend a private segregated cache for pull request builds, so that a fork cannot push to your main cache.  ↩ I added a benchmark page, https://trynix.dev/bench/ , to the site with a lot of rich data on boot and run times for various applications.  ↩

0 views
Farid Zakaria 2 months ago

How safe is follows?

I recently wrote about omniflake , accessible via https://omniflake.com , which indexes over 12,000 flakes and makes them available through a single flake input. One of the earliest requests I had was to support something similar to my tool nix-auto-follows to consolidate every flake’s inputs to a single coherent set. This is the same pattern you see often in every guide to flakes, often highlighting the attribute without much explanation of what it does or why it is used. The attribute consolidates a flake’s inputs to a single source, often used for . This reduces the number of distinct nixpkgs revisions in the dependency graph, which can speed up evaluation and reduce overall closure size. Those with more experience with flakes have a strong opinion about . While it improves evaluation speed and closure size, it can introduce subtle breakages and deviates from the original author’s intent which is counter to the philosophy of Nix which deems “reproducibility” as a core principle. I wanted to dig into the question of how safe it is to use in practice. The folklore is that it is dangerous, but I wanted to see if that was true. Turns out that https://omniflake.com is the perfect tool to try and answer this question. As I mentioned above, lets you consolidate a flake’s inputs to a single source. In the case of nixpkgs, this means that you are asking a flake to build against a nixpkgs revision that its author may never have evaluated it with. This can lead to breakages if the flake relies on specific behavior or attributes of the original nixpkgs revision. Often the delta between the two revisions is a good measure of how likely it is to break. If the nixpkgs revision you are following is only a few days or weeks newer than the original, it is likely to be safe. If it is several months or years newer, the risk of breakage increases. We can look at every flake within omniflake and see how old the nixpkgs revision is that it locks. 11,936 flakes are indexed in the omniflake index, 10,754 of them lock a nixpkgs and between them they name 3,261 distinct nixpkgs revisions . Here is every distinct revisions, placed by the date it was locked by the number of flakes that pinned it. Quite a lot of revisions are pinned by only a single flake. We can also visualize how old each nixpkgs revision is as of August 31, 2026. Half of all flakes are pinned to a nixpkgs older than 506 days , nearly a year and a half, and a twentieth are past 1,768 days (five years). The channels follow the distribution one would largely expect: (red line) pins are the freshest, which is unsurprising for a channel that moves daily. The darwin channel seems scary to replace with , barely 5% of those pins are under a year old What does this all mean? If we consider the median, when you add a line you are, typically, asking a flake to replace it with a nixpkgs likely a year and a half newer than anything its author ever tested. One time in twenty you are asking it to consolidate across five years. 😬 Not all nixpkgs are equal. A flake pinned to a nixpkgs that was a channel bump was built by Hydra and therefore received testing and is available for substitution from https://cache.nixos.org . We can audit the nix release archive to determine whether a given nixpkgs was ever a channel bump. Every channel bump ever published is a directory under , named for the commit it pointed at: If we enumerate all 74 channels, every and channel, we discover 30,850 (commit, channel) pairs to check against. 1 The majority of revisions, four in five, were a published channel bump. That is better than I expected and means that most flakes are pinned to a nixpkgs that was built by Hydra and therefore received testing and is available for substitution from the cache. Few flakes are pinned to a nixpkgs that was never a channel bump. The most common revisions that are shared amongst the flakes are relatively recent as well. The top 8 revisions are all from 2026, and the oldest revision in the top 8 is from May 4, 2026. It was good to see that the most common revisions across flakes are relatively recent. Personally, I enjoy running a release or two behind my personal NixOS laptop to avoid unecessary churn while all the kinks are worked out. How common is that? For each flake, we can take the gap between when the flake was last touched and the date of the nixpkgs it locks. That is how stale the pin was at the moment its author chose it , this is very different than the earlier graph which is how stale it is as of today . The original stateleness is depicted by the green line. It is the age of Nixpkgs the day it was written whereas red is the same pin today. Half of every flake in the index picked a nixpkgs less than three week old, and a quarter picked one inside three days! The shades region is simply time passing. It is how stale the pin has become over time. It is a frequency of how often a flake is updated. So essentially nobody deliberately pins an old nixpkgs. They run , get whatever was current that week, and stop . The ecosystem’s year and a half median is the result of a year and a half of neglect on each flake. Not realy but it was fun to look at the data. omniflake includes an easy way to unify all flake inputs . We could use it to see how many flakes would break if we replaced their nixpkgs with a single revision, but that would only tell us whether it could evaluate. A flake can evaluate perfectly and then fail to build. That’s a lot harder to measure. For now, I still recommend being mindful when you use . It is a powerful primitive that can improve evaluation speed and closure size, but it can also introduce subtle breakages, especially if you rely on . 🤫 The data for this post came from omniflake’s own index, joined against the release archive. It is one file, on a gist using a shebang and the standard library, so it needs nothing installed. Beware of bugs in the above code; I have only proved it correct, not tried it – Donald Knuth Earlier releases used shorter revisions and has no channel directory, its releases sit under .  ↩ Earlier releases used shorter revisions and has no channel directory, its releases sit under .  ↩

0 views