We are delighted and somewhat relieved to announce that the thirdreduction of the Guix bootstrap binaries has now been merged in themain branch of Guix! If you run guix pull today, you get a packagegraph of more than 22,000 nodes rooted in a 357-byte program—somethingthat had never been achieved, to our knowledge, since the birth of Unix.
We refer to this as the Full-Source Bootstrap. In this post, weexplain what this means concretely. This is a major milestone—if not themajor milestone—in our quest for building everything from source, allthe way down.
How did we get there, and why? In two previousblogposts,we elaborated on why this reduction and bootstrappability in generalis so important.
One reason is to properly address supply chain security concerns. TheBitcoin community was one of the first to recognize its importancewell enough to put the idea into practice. At the Breaking Bitcoinconference 2020, Carl Dong gave a funand remarkably gentleintroduction.At the end of the talk, Carl states:
The holy grail for bootstrappability will be connecting
hex0tomes.
Two years ago, at FOSDEM 2021, I (Janneke)gave a short talk about how wewere planning to continue this quest.
If you think one should always be able to build software from source,then it follows that the “trustingtrust”attack is only a symptom of an incomplete or missing bootstrap story.
Three years ago, the bootstrap binaries were reduced to just GNUMes andMesCC-Tools (andthe driver to build Guix packages: a staticbuildof GNU Guile 2.0.9).
The new Full-Source Bootstrap, merged in Guix master yesterday,removes the binaries for Mes and MesCC-Tools and replaces them by bootstrap-seeds. For x86-linux (which is also used by the x86\_64-linux build), this means this programhex0-seed, with ASCII-equivalenthex0\_x86.hex0. Hex0 is self-hosting and its source looks like this:
; Where the ELF Header is going to hit ; Simply jump to \_start ; Our main function # :\_start ; (0x8048054) 58 # POP\_EAX ; Get the number of arguments you can spot two types of line-comment: hex0 (;) and assembly (#).The only program-code in this snippet is 58: two hexidecimal digitsthat are taken as two nibbles and compiled into the corresponding bytewith binary value 58.
Starting from this 357-byte hex0-seed binary provided by thebootstrap-seeds, the stage0-posixpackage created by JeremiahOrians first builds hex0 and then all the way up: hex1, catm, hex2,M0, cc\_x86, M1, M2, get\_machine (that's all of MesCC-Tools), andfinally M2-Planet.
The new GNU Mes v0.24 release can be built withM2-Planet. This time with only a remarkably smallchange, the bottom of the packagegraph now looks like this (woohoo!):
gcc-mesboot (4.9.4) ^ | (...) ^ | binutils-mesboot (2.20.1a), glibc-mesboot (2.2.5), gcc-core-mesboot (2.95.3) ^ | patch-mesboot (2.5.9) ^ | bootstrappable-tcc (0.9.26+31 patches) ^ | gnu-make-mesboot0 (3.80) ^ | gzip-mesboot (1.2.4) ^ | tcc-boot (0.9.27) ^ | mes-boot (0.24.2) ^ | stage0-posix (hex0..M2-Planet) ^ | gash-boot, gash-utils-boot ^ | * bootstrap-seeds (357-bytes for x86) ~~~ [bootstrap-guile-2.0.9 driver (~25 MiB)]We are excited that the NLnet Foundation has beensponsoring this work!
However, we aren't done yet; far from it.
The idea of reproducible builds and bootstrappable software is notverynew.Much of that was implemented for the GNU tools in the early 1990s.Working to recreate it in present time shows us much of that practicewas forgotten.
Most bootstrap problems or loops are not so easy to solve andsometimes there are no obvious answers, for example:
In 2013, the year that ReproducibleBuilds started to gain sometraction, the GNU Compiler Collection releasedversion 4.8.0,making C++ a build requirement, and
Even more recently (2018), the GNU C Library glibc-2.28 adds Pythonas a buildrequirement,
While these examples make for a delightful puzzle from abootstrappability perspective, we would love to see the maintainers ofGNU packages consider bootstrappability and start taking moreresponsibility for the bootstrap story of their packages.
Despite this major achievement, there is still work ahead.
First, while the package graph is rooted in a 357-byte program, the setof binaries from which packages are built includes a 25 MiBstatically-linked Guile, guile-bootstrap, that Guix uses as its driverto build the initial packages. 25 MiB is a tenth of what the initialbootstrap binaries use to weigh, but it is a lot compared to those 357bytes. Can we get rid of this driver, and how?
A development effort with Timothy Sample addresses the dependency onguile-bootstrap of Gash andGash-Utils, thepure-Scheme POSIX shell implementation central to our secondmilestone.On the one hand, Mes is gaining a higher level of Guile compatibility:hash table interface, record interface, variables and variable-lookup,and Guile (source) module loading support. On the other hand, Gashand Gash-Utils are getting Mes compatibility for features that Mes islacking (notably syntax-case macros). If we pull this off,guile-bootstrap will only be used as a dependency of bootar and asthe driver for Guix.
Second, the full-source bootstrap that just landed in Guix master islimited to x86\_64-linux and i686-linux, but ARM and RISC-V will bejoining soon. We are most grateful and excited that the NLnetFoundation has decided to continue sponsoring thiswork!
Some time ago, Wladimir van der Laan contributed initial RISC-Vsupport for Mes but a major obstacle for the RISC-V bootstrap is thatthe “vintage” GCC-2.95.3 that was such a helpful stepping stone doesnot support RISC-V. Worse, the RISC-V port of GCC was introduced onlyin GCC 7.5.0—a version that requires C++ and cannot bebootstrapped! To this end, we have been improving MesCC, the Ccompiler that comes with Mes, so it is able tobuild GCC 4.6.5; meanwhile, Ekaitz Zarragabackported RISC-V support to GCC4.6.5, and backported RISC-Vsupport from the latest tcc to ourbootstrappable-tcc.
The full-source bootstrap was once deemed impossible. Yet, here we are,building the foundations of a GNU/Linux distro entirely from source, along way towards the ideal that the Guix project has been aiming forfrom thestart.
There are still some daunting tasks ahead. For example, what about theLinux kernel? The good news is that the bootstrappable community hasgrown a lot, from two people six years ago there are now around 100people in the #bootstrappable IRC channel. Interesting times ahead!
Software is bootstrappable when it does not depend on a binary seedthat cannot be built from source. Software that is notbootstrappable---even if it is free software---is a serious securityrisk (supply chain security)foravarietyofreasons.The Bootstrappable Builds project aimsto reduce the number and size of binary seeds to a bare minimum.
GNU Mes is closely related to theBootstrappable Builds project. Mes is used in the full-sourcebootstrap path for the Guix System.
Currently, Mes consists of a mutual self-hosting scheme interpreterand C compiler. It also implements a C library. Mes, the schemeinterpreter, is written in about 5,000 lines of code of simple C andcan be built with M2-Planet.MesCC, the C compiler, is written in scheme. Together, Mes and MesCCcan compile bootstrappable TinyCCthat is self-hosting. Using this TinyCC and the Mes C library, theentire Guix System for i686-linux and x86\_64-linux is bootstrapped.
GNU Guix is a transactional package manager andan advanced distribution of the GNU system that respects userfreedom.Guix can be used on top of any system running the Hurd or the Linuxkernel, or it can be used as a standalone operating system distributionfor i686, x86\_64, ARMv7, AArch64 and POWER9 machines.
In addition to standard package management features, Guix supportstransactional upgrades and roll-backs, unprivileged package management,per-user profiles, and garbage collection. When used as a standaloneGNU/Linux distribution, Guix offers a declarative, stateless approach tooperating system configuration management. Guix is highly customizableand hackable through Guileprogramming interfaces and extensions to theScheme language.
