In recent months, I’ve found myself discussing the pros and cons of different approaches used for building complete operating systems (desktops or appliances), or lets say software build topologies. What I’ve found, is that frequently I lack vocabulary to categorize existing build topologies or describe some common characteristics of build systems, the decisions and tradeoffs which various projects have made. This is mostly just a curiosity piece; a writeup of some of my observations on different build topologies.
Self Hosting Build Topologies
Broadly, one could say that the vast majority of build systems use one form or another of self hosting build topology. We use this term to describe tools which build themselves, wikipedia says that self hosting is:
the use of a computer program as part of the toolchain or operating system that produces new versions of that same program
While this term does not accurately describe a category of build topology, I’ve been using this term loosely to describe build systems which use software installed on the host to build the source for that same host, it’s a pretty good fit.
Within this category, there are, I can observe 2 separate topologies used, lets call these the Mirror Build and the Sequential Build for lack of any existing terminology I can find.
The Mirror Build
This topology is one where the system has already been built once, either on your computer or another one. This build process treats the bootstrapping of an operating system as an ugly and painful process for the experts, only to be repeated when porting the operating system to a new architecture.
The basic principle here is that once you have an entire system that is already built, you can use that entire system to build a complete new set of packages for the next version of that system. Thus the next version is a sort of reflection of the previous version.
One of the negative results of this approach is that circular dependencies tend to crop up unnoticed, since you already have a complete set of the last version of everything. For example: it’s easy enough to have perl require autotools to build, even though you needed perl to build autotools in the first place. This doesn’t matter because you already have both installed on the host.
Of course circular dependencies become a problem when you need to bootstrap a system like this for a new architecture, and so you end up with projects like this one, specifically tracking down cropped up circular dependencies to ensure that a build from scratch actually remains possible.
One common characteristic of build systems which are based on the Mirror Build is that they are usually largely non-deterministic. Usually, whatever tools and library versions happen to be lying around on the system can be used to build a new version of a given module, so long as each dependency of that module is satisfied. A dependency here is usually quite loosely specified as a lower minimal bound dependency: the oldest version of foo which can possibly be used to build or link against, will suffice to build bar.
This Mirror Build is historically the most popular, born of the desire to allow the end user to pick up some set of sources and compile the latest version, while encountering the least resistance to do so.
While the famous RPM and Debian build systems have their roots in this build topology, it’s worth noting that surrounding tooling has since evolved to build RPMs or Debian packages under a different topology. For instance, when using OBS to build RPMs or Debian packages: each package is built in sequence, staging only the dependencies which the next package needs from previous builds into a minimal VM. Since we are bootstrapping often and isolating the environment for each build to occur in sequence from a predefined manifest of specifically versioned package, it is much more deterministic and becomes a Sequential Build instead.
The Sequential Build
The Sequential Build, again for the lack of any predefined terminology I can find, is one where the entire OS can be built from scratch. Again and again.
The LFS build, without any backing build system per se, I think is a prime example of this topology.
This build can still be said to be self hosting, indeed; one previously built package is used to build the next package in sequence. Aside from the necessary toolchain bootstrapping: the build host where all the tools are executed is also the target where all software is intended to run. The distinction I make here is that only packages (and those package versions) which are part of the resulting OS are ever used to build that same OS, so a strict order must be enforced, and in some cases the same package needs to be built more than once to achieve the end result, however determinism is favored.
It’s also noteworthy that this common property, where host = target, is what is generally expected by most project build scripts. While cross compiles (more on that below) typically have to struggle and force things to build in some contorted way.
While the Ports, Portage, and Pacman build systems, which encourage the build to occur on your own machine, seem to lend themselves better to the Sequential Build, this only seems to be true at bootstrap time (I would need to look more closely into these systems to say more). Also, these system are not without their own set of problems. With gentoo’s Portage, one can also fall into circular dependency traps where one needs to build a given package twice while tweaking the USE flags along the way. Also with Portage, package dependencies are not strictly defined but again loosely defined as lower minimal bound dependencies.
I would say that a Sequential Self Hosted Build lends itself better to determinism and repeatability, but a build topology which is sequential is not inherently deterministic.
Cross Compiles
The basic concept of Cross Compiling is simple: Use a compiler that runs on host and outputs binary to be later run on target.
But the activity of cross compiling an entire OS is much more complex than just running a compiler on your host and producing binary output for a target.
Direct Cross Build
It is theoretically possible to compile everything for the target using only host tools and a host installed cross compiler, however I have yet to encounter any build system which uses such a topology.
This is probably primarily because it would require that many host installed tools be sysroot aware beyond just the cross compiler. Hence we resort to a Multi Stage Cross Build.
Multi Stage Cross Build
This Multi Stage Cross Build, which can be observed in projects such as Buildroot and Yocto shares some common ground with the Sequential Self Hosted Build topology, except that the build is run in multiple stages.
In the first stage, all the tools which might be invoked during the cross build are built into sysroot prefix for host runnable tooling. This is where you will find your host -> target cross compiler along with autotools, pkg-config, flex, bison, and basically every tool you may need to run on your host during the build. These tools installed in your host tooling sysroot are specially configured so that when they are run they find their comrades in the same sysroot but look for other payload assets (like shared libraries) in the eventual target sysroot.
Only after this stage, which may have involved patching some tooling to make it behave well for the next stage, do we really start cross compiling.
In the second stage we use only tools built into the toolchain’s sysroot to build the target. Starting by cross compiling a C library and a native compiler for your target architecture.
Asides from this defining property, that a cross compile is normally done in separate stages, there is the detail that pretty much everything under the sun besides the toolchain itself (which must always support bootstrapping and cross compiling) needs to be coerced into cooperation with added obscure environment variables, or sometimes beaten into submission with patches.
Virtual Cross Build
While a cross compile will always be required for the base toolchain, I am hopeful that with modern emulation, tools like Scratchbox 2 and approaches such as Aboriginal Linux; we can ultimately abolish the Multi Stage Cross Build topology entirely from existence. The added work involved in maintaining build scripts which are cross build aware and constant friction with downstream communities which insist on cross building upstream software is just not worth the effort when a self hosting build can be run in a virtual environment.
Some experimentation already exists, the Mer Project was successful in running OBS builds inside a Scratchbox 2 environment to cross compile RPMSs without having to deal with the warts of traditional cross compiles. I also did some experimentation this year building the GNU/Linux/GNOME stack with Aboriginal Linux.
This kind of virtual cross compile does not constitute a unique build topology since it in fact uses one of the Self Hosting topologies inside a virtual environment to produce a result for a new architecture.
Finally
In closing, there are certainly a great variety of build systems out there, all of which have made different design choices and share common properties. Not much vocabulary exists to describe these characteristics. This suggests that the area of building software remains somewhat unexplored, and that the tooling we use for such tasks is largely born of necessity, barely holding together with lots of applied duct tape. With interesting new developments for distributing software such as Flatpak, and studies into how to build software reliably and deterministically, such as the reproducible builds project, hopefully we can expect some improvements in this area.
I hope you’ve enjoyed my miscellaneous ramblings of the day.