We're bad at marketing

We can admit it, marketing is not our strong suit. Our strength is writing the kind of articles that developers, administrators, and free-software supporters depend on to know what is going on in the Linux world. Please subscribe today to help us keep doing that, and so we don’t have to get good at marketing.

This year's edition of the Free and Open Source Software Yearly conference, better known as "FOSSY", moved north to the beautiful (and enormous) campus of the University of British Columbia (UBC) in Vancouver, Canada from its home for the three previous editions: Portland, Oregon, in the US. There were many different types of talks at FOSSY, from deeply technical kernel-track topics, through talks on legal and community issues, to the "FOSS in Daily Life" talks. In the "Toolchains and Other Development Tools" track, Timothy Sample gave a presentation about bootstrappable builds, which is somewhat less well-known than its cousin, reproducible builds, though LWN did look at the topic just over two years ago. In short, a bootstrappable build is one that starts with a tiny program that can build another slightly larger program, which can build yet another, and so on, until the entirety of a modern Linux user space is built from a small seed. Ultimately, it results in code with a completely understood origin—unlike a typical Linux user space today.

He began by asking attendees whether they had heard of bootstrappable builds and whether they were generally familiar with the idea; he seemed impressed that the majority knew the term and that roughly half of the audience knew more than that. He said that he embarked on the path toward bootstrappable builds almost ten years ago when he started using GNU Guix (which he pronounced "geeks"—surprising me). At that time, if you were using Guix, you were contributing to it, he said with a chuckle. Guix is a "functional package manager" that is similar to (and inspired by) Nix.

For both Guix and Nix, all of the software in the system is represented in a "derivation graph", which describes how to build each of its programs. There are various inputs required in order to be able to build a particular program, which are specified in the graph. The way to build each of the inputs (and, of course, the inputs to the inputs and so on) is also represented in the graph. "There's hundreds and hundreds of nodes in modern software, which is terrifyingly complex."

He gave the example of a Python program. It, obviously, requires Python in order to run, but Python is a C program, so a C compiler is needed. That C compiler is written in some language, so a compiler for that language will be needed. And so on. Guix collects all of that into the graph, which is an object that can be looked at and explored. "So you start wondering who compiles my compiler's compiler compiler and where does it stop?"

For a system like Debian, it stops at a C compiler binary that someone has uploaded to the repositories. For Guix, the original stopping point was a 250MB statically linked blob of GNU user-space programs. The answer to where all of that code came from is not entirely clear, of course, which was unsatisfying to Guix developers. That blob could be built reproducibly, which is good, Sample said, but does not solve the entire problem.

Bootstrappable

The basic idea behind bootstrappable builds is to create a system that can be built without relying on pre-built artifacts. "Can we go from zero to the modern day without having to just assume the existence of these already-built-for-us artifacts?" The classic recipe for yogurt requires some yogurt to start the process, which is like how we normally build a C compiler today—we start with an existing C compiler binary. You might think about making sourdough bread with your grandmother's starter brought over from the old country; "we're basically making C compilers with Dennis Ritchie's starter carried over from Bell Labs".

It is not just C, of course, as it is true for most languages. It is something of a point of pride for languages to "self host" by writing the compiler and other tools in the language itself. It is natural for the language developers to do that, because obviously their language is the best, but it leaves something of a chicken-and-egg problem behind. Bootstrappable builds is an effort to move beyond that and to build these tools "from scratch".

Reproducible builds allow people to "have more confidence that the binary you are using, which is actually executing on the computer, corresponds to the source code". A user can receive a binary that purports to come from a set of source code files, but how can they be sure that it does? With a reproducible build, they can create the binary themselves and check to ensure that it is bit-for-bit the same as what they were given.

Bootstrappable builds do exactly the same thing, but they handle a different failure mode. If a reproducible build fails to verify, that's because the person who built the binary is lying or mistaken about where it came from. Bootstrappable builds can prevent the kinds of problems that Ken Thompson described in his famous Turing Award lecture: Reflections on Trusting Trust.

An example that Thompson gave in that lecture asked where in a C compiler you can find the definition of "\n", Sample said. Looking in the source code of the compiler will not show a definition, it will simply provide the circular definition that "\n" is "\n"; the conversion of "\n" to ASCII ten is embodied in the C compiler binary itself. Thompson continued his lecture by noting that something rather more dangerous, such as a backdoor for the login program, could also be hidden in the compiler in the same way.

It is not just C compilers, or even just compilers, that can have this sort of flaw; any self-hosting program can potentially fall prey to it. Programs of this sort can remove details from the source code and have them persist in binary form. As he was preparing for the talk, a colleague pointed him at a recent paper ("Trusting-Trust Attack against an Entire Linux Distribution through Binary Manipulation") that showed an actual attack of this sort. The researchers inserted a backdoor into the strip program on NixOS, which is run on nearly every binary that is built on the system. "They were able to backdoor basically every single program on the system in a way that's completely invisible from source-code analysis." That is the kind of attack that bootstrappable builds is meant to thwart.

While the security angle is the largest benefit of bootstrappable builds, Sample said that there are software-freedom aspects too. Being able to read the source code is useful, but knowing that the source code corresponds to the running program is important as well. There is also a sense of pride that many programmers have in making their code clear and understandable. Ensuring that the code can be inspected and that all of its details exist in some available body of source code is part of that.

The best way to handle bootstrapping is proactively, he said. Before a compiler is self-hosted, it is normally written in some other language; preserving that code and maintaining it alongside the self-hosted version provides a means to ensure that nothing is hidden in the binary. That is what the GNU Guile project does; it is a version of Scheme that is used by Guix and various other projects. Guile still has a C implementation of the language available to use for bootstrapping the compiler. GNU Make has a makefile, of course, but it also has a shell script in case no make is available. "We recognize that we're a fundamental build tool and that there should be another on-ramp here."

For tools that only support a self-hosted build, there are some techniques that he and others in the bootstrappable-builds community use to circumvent that lack. The first is an "archaeological dig", which uses the history of the project to find a non-self-hosted version; that version is built using the tools from that era. "Then you move through history, version after version [...] until you get to the modern tool." Sometimes some of the version steps can be skipped, but overall it is a slow process. "In some ways, it just sort of kicks the can down the road; technically, you do have all of the source code", but asking someone to look at, say, 12 different versions of a tool is rather daunting; it would be nice for there to just be one version to verify.

An audience member asked if this was like using the OCaml version of the Rust compiler to bootstrap to current Rust; Sample said that it was, except that the OCaml Rust compiler is no longer available. Another attendee noted that the Plan 9 C compiler that was used to build the Go programming language is still available, as is the earlier Plan 9 C compiler that built that C compiler. Those kinds of build chains are normal for Guix, Sample said. For Rust, it currently starts with the C++-based mrustc to build Rust version 1.54 or 1.56; modern Rust is 1.97 and nearly every version in between must be built, which is quite slow. When rebuilding a Guix system, Sample said, "it's very depressing when you hit this chain of Rust compiles"; an attendee said it took them three days to build that on their Arm laptop.

The end result of those chains is not all that nice because of the number of steps that need to be verified. An alternative is to "purpose-build a new tool for bringing something up", which is exactly what mrustc is. The result is nicer, with a single code base to inspect, but "it takes forever" to develop a bespoke tool of that sort. He has done some of that and the result is unsatisfying at some level because the tool simply exists to enable another tool to be bootstrapped. Beyond that, the tool will require maintenance to keep up with the target tool, but it is not particularly exciting work that might attract other developers.

The most successful bootstrappable builds use a combination of the two approaches. As with Rust and mrustc, they go back in time to a simpler version that can be built with an alternative bespoke tool, then move forward to the present-day version. In fact, mrustc can now build Rust 1.90, but that has not been integrated into Guix yet; he plans to do so in the near future.

Projects

He returned to Guix and its seed, which is only around 256 bytes these days, rather than the 250MB blob. It consists of a program called hex0, which can "build up through many many layers and eventually gets to GCC 2, GCC 4, and modern GCC, and modern Guile and all these tools". While that's "super cool", there are a lot of caveats; the biggest is that a statically linked Guile is still used "to do a bunch of stuff". That is "absolutely cheating", he said, but there are plans to fix that, which he is working on, but it is going to take some time to achieve.

The other thing that often disappoints people is that there is no answer for how to bootstrap the kernel. Guix assumes there is a kernel; "it'll bootstrap all of userland from nothing, but the kernel is outside of the scope of this discussion".

A related project is live-bootstrap, which works with Guix and uses many of the same tools and approaches; live-bootstrap moves more quickly than Guix, however, and has explored bootstrapping kernels using the Fiwix kernel. Live-bootstrap regenerates any of the machine-created files that might accompany a source release (e.g. configure) as well; it is "very admirable how thoroughgoing they are", but the "downside is it's extremely complicated".

To demonstrate that, he put up the 182-step process to bootstrap the system. It lists tools that need to be built in the order needed to arrive at a base Linux system. It starts with hex0, builds various different tools, including multiple C compilers of increasing complexity, many versions of Perl in order to bootstrap Automake and Autoconf, and so on. It does not include tools like Rust and Go; "it's just the modern GNU/Linux base system".

"It's great that they've done that work, it's pretty wild and complicated, and it would be nice to improve that", Sample said.

The hex0 program provides a way to turn a string of hexadecimal text into a binary with those bytes. Normally, that is used to build hex1 and hex2, which are also hexadecimal converters adding single-character labels (hex1) and more complete labels that allow fancier addressing modes (hex2). Using those, M0 can be built, which allows using assembly mnemonics, rather than hex opcodes.

Sample said that he had omitted a few steps but that eventually M2-Planet can be built, which "is almost like C"; code can be compiled, but sometimes certain C features will be missing so it will need to be rewritten to avoid them. At that point, everything switches over to use GNU Mes, which is a Scheme interpreter written in the M2-Planet dialect of C. Mes has a C library (Meslibc) and a C compiler written in Scheme (MesCC). Those allow building the Tiny C Compiler (TCC), which "is a simple C compiler but much more complete than MesCC". Modern development tools can then be built using TCC.

Germ

That is the path taken by both Guix and live-bootstrap. "It works, [...] but everything is super complicated." He is working on a different approach, called Germ (or Germ Lisp), which is introduced in a blog post on his site. In that post, he pointed out that the existing mechanism goes from C to Scheme and back to C, all to end up in Guix, which is Scheme-based. But, he recognized, that "a primitive Lisp interpreter is not much more complicated than a primitive assembler."

He works on Mes and likes it; "sometimes I get paid to work on Mes, Mes is great". But he is also writing a Mes replacement, which is not all that uncommon. There are Mes replacements being written in Haskell and ML, for example; everyone who looks at the problem immediately wants to write the replacement in Forth, he said. Bootstrapping Forth via a hex monitor is an obvious use of the language, but most developers do not want write the rest of the code in Forth, he thinks; "I would rather read the binary". From the audience, Keith Packard said: "Assembly is easier to write than Forth."

Scheme folks are different, Sample said, and are willing to write code in that language. The intent of Germ is jump over all of the intermediate steps and have a Scheme interpreter from the start. "It just says: 'Scheme, go!', well it has two stages, but almost 'Scheme, go!'." It is how Mes was designed originally, he said; it took some shortcuts that allowed it to succeed early, "but now it's getting stuck".

Germ is about 2.25KB; he wanted it to be 2KB, but missed that goal by a little. It is a binary that "can run almost-Scheme"; it is just enough Scheme that it can run an assembler written in Scheme. That assembler is used to build the second stage, which is "kind of just like a Scheme interpreter". It has contiguous bytes and vectors, features for I/O and working with the kernel, and it will almost run unmodified Guix build scripts (there are still a few dangling items to fully make that work). It uses MesCC to compile C code and has a Scheme shell that he wrote years ago for handling shell scripts; "eventually it'll run awk scripts and sed scripts".

Sample said that attendees might be expecting a demo at that point in his talk, but that he had been giving one throughout, as his slides were running on his laptop using Germ. He added an interface to SDL, provided a "draw pixel" function for Germ, and loaded in the font information. As was guessed by an audience member (winning the 1000-nerd-point prize), the font he used was from the original Symbolics Lisp machine.

He took a brief tour of the Germ code, showing the Scheme-based assembly (like that in memory.scm), while noting that he maintains a regular assembly version (memory.s) in parallel. There is a practical side to that choice, as well, since by using a real assembler "you get debugging symbols and everything, with the other one you most certainly don't", he said with a laugh.

Overall, Germ hits his goals well. It quickly rises to a high level of abstraction that exactly fits the Guix use case. All of the Guix build scripts are written in Scheme; Guix avoids using shell scripts for the most part.

It's conceptually simple. Now I know not everyone loves Lisp or Scheme—somehow it's controversial—but regular old, plain Scheme has got to be better than this tower of bespoke assemblers and compilers for languages that don't quite exist.

That statement was met with some laughter from the audience as might be guessed—Lisp/Scheme are controversial and somewhat divisive, after all. The biggest problem that Germ faces is not surprising, he said: performance. He is writing a Scheme in the same way that the original Lisp interpreters were written in the 1950s, using assembly language. "I can't bring to bear all of the modern techniques because writing in assembly is hard and keeping things small is hard."

Germ is "faster than Mes, technically", at least on a micro-benchmark of making function calls. But whenever a real program is being run, Mes is much faster because nearly everything in Germ runs in Scheme (e.g. loops). For a comparison, it takes about 100 seconds for Mes to compile itself on his desktop, or 60 seconds if the experimental bytecode compiler is used. Compiling Mes on Germ, with a bunch of optimizations that he is testing enabled, takes around 140-150 seconds. The problem with that is that Mes is "unbearably slow", so being worse than Mes is something of a non-starter.

In addition, Germ is less portable than Mes, which can run on Arm and RISC-V, while Germ is x86_64-only at this point. Another problem Germ faces is that "people just hate parens", which is irrational, but he can relate because he was one of the haters until he ran into Guix. Scheme is a relatively easy language to implement, though, and, since it meshes well with Guix, makes a lot of sense for bootstrapping.

Future

Looking ahead, he would like to integrate Germ with Guix "in a way that's exciting for everyone". Currently, Guix depends on %bootstrap-guile, which is the statically linked Guile binary, but Germ could potentially replace that; it could also be replaced with Mes, but either way would be a nice step forward.

He would also like to work on the performance of Germ; moving some of the looping constructs into the assembly code is some low-hanging fruit. "That feels like band-aids", however, and he wonders if he should simply write a compiler; there is a need for a compiler backend for C, so maybe the two could be combined. He has some starting work toward a RISC-V port that he would like to finish as well.

He ended the talk there, but there was lively Q&A session after that. Packard asked how much of Scheme was implemented in Germ; was it R5RS compliant, for example? Sample said that it is a Guile Scheme, but does not have extras like the Guile Object Oriented Programming System (GOOPS); it is effectively an R7RS Scheme, but he took some shortcuts like removing floating-point numbers since he does not need them.

Mark Wielaard asked how many of the 182 steps were removed by this work. Sample said that in his "dreaming mind", Germ would serve as a wedge that others would use to create Scheme-based shortcuts to remove some of the long chains of builds (e.g. Perl and autoconf) and reduce the problem further. He acknowledged Wielaard's estimate of more than 80 steps still remaining; Wielaard pointed out that someone could sabotage step 73 and it is likely that it would go unnoticed. Sample agreed that it was a known flaw in the approach, but that the number of steps was being reduced to slowly improve the ability to verify everything.

The seed could be smaller than the 2.25KB if he wanted, an attendee said. He agreed and noted that he could simply use hex0 to load the first stage of Germ, but "I don't want to play games, I want to actually get results". He did not want to start any fights and respected those who use hex0, but it feels a bit like cheating to him.

The final question was whether Germ had a read-eval-print loop (REPL); the answer was yes, of course, since he had been displaying his slides using it. He showed the REPL and his use of the (next-slide) and (prev-slide) functions; he also demonstrated that it gives a backtrace on errors. "I program in this all the time, it can't be driving me crazy; it has to have a few creature comforts." He took some shortcuts (e.g. no floating-point numbers), but it has some extras too, such as delimited continuations.

He closed by noting that Germ has "the fanciest macros", including a working syntax-case form. He had to implement that himself, since, ironically, there is no bootstrappable syntax-case—it is written using syntax-case.

[I would like to thank the Linux Foundation, LWN's travel sponsor, for helping with my travel expenses to Vancouver for FOSSY.]