The Yocto Project 3.0 release

This update contains the usual things people have come to expect from a Yocto Project release, such as upgrades to the latest versions of many of the software components including GCC 9.2, glibc 2.30, and the 5.2 and 4.19 kernels. But there is more to it than that.

One major development in this release was the addition of the ability to run the toolchain test suites. The project is proud of its ability to run builds of complete Linux software stacks for multiple architectures from source, boot them under QEMU, and run extensive software tests on them, all in around five hours. In that time we can now include tests for GCC, glibc, and binutils on each of the principal architectures. As a result, the test report for the release now has around two-million test results.

Build change equivalence

What is slightly less usual is a small line in the release notes starting with "build change equivalence". This innocuous-sounding line covers what could become one of the most useful enhancements to the project in recent years and may also be a first for large-scale distribution compilation in general. In basic terms, it allows detection of build-output equivalence and hence reuse of previously built binaries — but in a way never seen before — by building on technology already used by the project.

While the project has been able to reuse binaries resulting from identical input configurations for some time, 3.0 allows the reuse of previously built binaries when the output of the intermediate steps in the build process is the same. This avoids much rebuilding, leading to faster development times, more efficient builds, reduced binary artifact storage, and also a reduction in work like testing, allowing build and test resources to focus on "real" changes. In short, it addresses one of the complaints many Yocto Project users have about the system: its "continual building from source".

In some ways focusing on this feature is unfair to 3.0, as there are many other, smaller features in there, many of which are small, incremental improvements to things the project has already done well. One other feature of note is that the change equivalence work led naturally into more efficient "multiconfig" builds where multiple different configurations can be built in parallel. These are now optimized when the builds share artifacts. The Yocto Project is one of the few where you can build components for different architectures or operating systems (e.g. an RTOS) in parallel and combine them all in one build.

The Yocto Project/OpenEmbedded build process

To understand more about what build change equivalence means and how it works, it first makes sense to understand how prebuilt binaries were already being handled. There is a common misconception that the Yocto Project (or OpenEmbedded, the underlying build system) always builds everything from source. This may have been true ten years ago but, in modern times, the project maintains what it terms its shared-state cache (or "sstate"). This cache contains binaries from previous builds that the system can reuse under the right conditions.

When building software with OpenEmbedded, there are a series of steps that are followed. The project's execution engine, "BitBake" takes these steps ("tasks" in BitBake terms), builds a dependency tree, and executes them in the correct order. These tasks are usually written in Python or the shell and, ultimately, are effectively represented by key/value pairs of data. These data pairs could be the topic of an article in their own right but, in short, they are how OpenEmbedded manages to be customizable and configurable. It does this through this data store and its ability to "override" values and stack configuration files from different sources, all of which can all potentially manipulate the values. An example could be the following configuration fragment:

    PARALLELISM ?= ""

    MAKE = "make"
    MAKE_specialmake = "new-improved-make"

    OVERRIDES = "${@random.choice(['', 'specialmake'])}"

    do_compile () {
        ${MAKE} ${PARALLELISM}
    }
    addtask compile after configure before install

This fragment illustrates some of the capabilities of the syntax. Several keys are defined, including do_compile, which is promoted to a task with some ordering constraints on when it needs to run. The "do_" prefix is simply a convention to make it obvious which keys are tasks. A user could set PARALLELISM elsewhere to pass options like -j to make, speeding up compilation, or to turn it off if some source code doesn't support parallel building.

Also shown is a simple override where MAKE is changed to a different tool when specialmake is added to OVERRIDES. In this case, it is being triggered randomly just to show the ability to inject Python code to handle more complex situations. There is much more to the syntax, but the idea is you build up functions and tasks that are executed to build software, and these functions are highly customizable depending on many different kinds of input, including the target architecture, the specific target device, the policies being used for the software stack, and so on. The BitBake data store is the place where all the different inputs are combined together to build the system.

There is code in BitBake that knows how to parse these shell and Python configuration fragments — in the Python case using Python's own abstract-syntax-tree code — and from this figure out which keys and associated values were used to build the functions that represent the tasks. Once you know the values that are going into a given task, you can represent them as a hash. If the input data changes, the hash changes. Some values, such as the directory where the build is happening, can be filtered out of the hash but, in general, they're sensitive and accurate representations of the configuration being used as the input. In addition, hashes of files being added to the build are included.

The sstate cache is therefore a store of output from tasks, indexed by a hash that represents the configuration and other inputs used to create that output. If the configuration (hash) matches, the object can be pulled from the cache and used instead of rebuilding it from scratch. This, however, is old technology; the project has been using sstate since 2010. One potential issue with this approach is how sensitive it is to changes. If you add some white space to a patch being applied to some piece of software early in the build process, it will change the input hashes to almost everything in the system and cause a full rebuild. There has, therefore, been a long-held desire to be more intelligent about when to rebuild. Solving a case of white space changes may be possible through optimization, but there are many other cases that could be optimized too, and the question becomes how to do this in a more generic way.

Better optimization

This is where the new work in 3.0 comes into play. So far, we've only talked about configuration inputs, but these inputs result in some kind of output such as, in the case of the example above, some generated object files. The project would usually be most interested in the output from "make install", which would be generated by a do_install() function following do_compile(). For more efficient builds, it became clear that the project should start analyzing the output from the intermediate tasks, so it came up with a way of representing the output of a task as a hash too. The algorithm currently chosen to do this looks at the checksums of the output files, but it ignores their timestamps. There are lots of potential future features that could be added here, such as representing the ABI of a library instead of its checksum but, for now, even this simplistic model is proving effective.

Once you have this output hash, you can compare it to hashes of previous builds of this task. If the output hashes from two builds match, then the input hashes from those two builds are deemed to be "equivalent". This means that the current build matched the previous build up to this point; it follows that anything beyond this point should also match, assuming the same subsequent configuration, even though the input configurations before this point were different. At this point, the build can therefore stop building things from scratch and start reusing prebuilt objects from sstate.

To make this work, the system needs to store information about these "equivalences", so the project added a "hash equivalence server" — a server that stores which input hashes generate the same output data as other input hashes and are thus equivalent. The first input hash given to the server is deemed to be the "base" hash and used to resolve any other matching hashes to that value. This server is written as a network service so that multiple different builds can feed it data and benefit from its equivalence data to speed up their builds.

This is all good, but BitBake itself required major surgery to be able to use this data. Previously, it would look for prebuilt objects from sstate, install them, then proceed with anything it needed to build from source. Installing from sstate is a different operation, since the task ordering is reversed compared to normal task execution. To understand why, consider that, in some cases, if an sstate object is available for some task late in the build, you can skip all the earlier tasks leading up to that object, as those objects aren't needed. That means you need to start with the tasks that would normally be last to run, then work backward up the dependency tree, installing the sstate objects in reverse order, stopping when no dependencies are needed. In simpler terms, this that means mixing sstate tasks and normal tasks is hard.

To do this, 3.0 BitBake now has to have two different task queues — sstate tasks and non-sstate tasks — and both queues need to be able to execute in parallel. When sstate equivalence is detected, tasks are "rehashed" with the new hashes, and tasks can possibly migrate back to the sstate queue. The build can alternate between these two states many times during a build as different equivalences are found and objects from sstate become valid. It makes for a fascinating scheduling problem.

Reproducibility and more

There is a further consideration here: reproducibility. This is a hot topic for many distributions, so there have been many people quietly working away at making software builds generate consistent binary output. The Yocto Project is no exception and has been trying to do its part, including sending patches to upstream projects where it can (including the Linux kernel). This ties in well for hash equivalence, since the higher the reproducibility of the output, the larger the number of equivalent hashes that should be found. In 3.0, automated tests for reproducibility were added. The project has this working for building the minimal core image, including its toolchain, and will continue to improve this feature in the next release.

While this is a beta feature in 3.0 that is not enabled by default, the project believes it represents a significant optimization in working with source builds. Perhaps the Yocto Project can finally put the reputation of "always building from source" behind it.

Finally, its also worth mentioning a quick follow-up to a previous article that discussed how the project found a Linux kernel bug with its automated testing. As the Yocto Project was approaching the 3.0 release and switching to the 5.2 kernel, a similar situation occurred where developers noticed that the "ptest" tests for the strace recipe were hanging. "ptests" are where the project has packaged up the upstream tests that come with software; they are run in the target environment. This was discussed on LKML and ultimately found to be a bug that only appeared when preemption was enabled.

The takeaway from all this is that "from scratch" source builds for the Yocto Project should be something that happens less frequently in the future, particularly as build reproducibility continues to improve. Along with the obvious benefits faster builds bring to developers, they reduce storage and load requirements and reduce testing requirements too. This is particularly important when you consider security updates for end-user devices, where little of the system should change for a given update. Minimizing rebuilding allows more focused testing and, thus, reduced risk of unintended side effects, which in turn may encourage more updates to be made.

The project plans to make this functionality the default in the near future and is looking forward to further improvements in reproducibility as it works on finalizing its long-term support plans within which these developments can play a key role.

[Richard Purdie is one of the founders of the Yocto Project and its technical lead.]