Bootstrappable builds: how and why [LWN.net]

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.

$ sudo subscribe today

Subscribe today and elevate your LWN privileges. You’ll have
access to all of LWN’s high-quality articles as soon as they’re
published, and help support LWN in the process. Act now and you can start with a free trial subscription.

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

The LWN site is currently under high scraper load, so comment
display has been suppressed for anonymous users.
If you are a
human, you may read the comments by clicking the button below:

Note: you can avoid this step in the future by logging
into your LWN account.