How many ways are there to configure the Linux kernel?

There are a large number of ways to configure the 6.16 Linux kernel. It has 32,468 different configuration options on x86_64, and a comparable number for other platforms. Exploring the ways the kernel can be configured is sufficiently difficult that it requires specialized tools. These show the number of possible configurations that options can be combined in has 6,550 digits. How has that number changed over the history of the kernel, and what does it mean for testing?

Analyzing Kconfigs

With so many configuration options to consider, it can be difficult to even figure out which options are redundant, unused, or otherwise amenable to simplification. For our problem of counting the number of ways to configure the kernel, we need to consider the relationships between different configuration options as well. Happily, there is some software to manage the growing complexity.

The kernel uses a custom configuration language, Kconfig, to describe how the build can be customized. While Kconfig has spread to a handful of related projects, it remains a mostly home-grown, Linux-specific system. Paul Gazzillo, along with a handful of other contributors, wrote kmax, a GPL-2.0-licensed software suite for analyzing Kconfig declarations. That project includes tools to determine which configuration options need to be enabled in order to test a patch, to find configuration bugs, and to export Kconfig declarations in a language that can be understood by more tools. It has been integrated into the Intel 0-day test suite, finding a number of bugs in the kernel's configuration in the process.

One of the project's programs, klocalizer, can output the set of relationships between different options in SMT-LIB 2 or DIMACS format — the standard input formats for modern SAT solvers. This makes it much simpler to write custom ad-hoc analysis of the kernel's configuration options. For example, one could use Z3's Python bindings to load the output from klocalizer and explore how options relate to one another. A SAT solver such as Z3 produces (when possible) a single solution to a set of constraints — in this case, a single valid way to configure the kernel.

Calculating the number of valid solutions is a related but much harder problem called #SAT. While there are a number of approximation techniques that can be used to solve #SAT probabilistically, in this case the constraints in the kernel's configuration are simple enough for a precise counter called ganak to solve the problem exactly.

The numbers

So, with these tools in hand, one can analyze how many ways to configure the kernel there really are. The growth in the number of configuration parameters in the kernel has been roughly linear, leading to exponential growth in the number of ways the kernel can be configured. The following chart shows two trend lines: the logarithm of the actual number of ways to configure the kernel in blue, and the number of configuration options (scaled appropriately to sit on the same axis; see below) in red. The red line represents the theoretical maximum that the blue line could obtain. Plotting 6,000 digit numbers directly proved to be too much for both LibreOffice Calc and Google Sheets, hence the logarithms.

There are a few things that can be immediately seen from this chart. For example, there are more than twice as many configuration options available in version 6.16 compared to version 2.6.37 (the earliest version that kmax can understand). In some sense, this is not surprising — the Linux kernel keeps adding support for new features and new hardware; the number of configuration options is just growing along with the code. But there is a subtler trend that is arguably more important: configuration options are becoming more interdependent over time.

If every configuration option could be enabled independently of every other configuration option, there would be 2^N ways to configure the kernel given N configuration options. The red line is the number of configuration options scaled by ^ln(2)⁄_ln(10) — that is, it represents the logarithm of 2^N. That way the two lines are directly comparable. The actual number of ways to configure the kernel sits below this theoretical maximum because configuration options can depend on or exclude each other. This chart shows the difference between the red and blue lines:

Note that this result is still on a logarithmic scale, so this value is the logarithm of the number of ways to configure the kernel that are ruled out by dependencies between different options. As the difference grows, it shows that more configuration options are interacting with each other. This is not, in itself, a problem — but those interactions are likely associated with interdependent pieces of code. The number of places where kernel code depends on multiple related configuration options is growing.

With the number of possible configurations, it is certain that not all of them have been tested individually. If the configuration options were independent, testing a kernel with everything enabled and one with everything disabled would theoretically suffice. Many options, especially ones that are specific to a particular hardware driver, are genuinely independent. But when options can influence each other and interact (even outside of Kconfig interactions), the number of scenarios that need to be tested grows quickly.

Linux's testing is largely distributed — it is done by individual patch contributors and reviewers, several different automatic unit testing and fuzzing robots, distribution QA teams, companies, and normal Linux users. With the decentralized nature of open source, and the large number of possible configurations, it's hard to tell exactly how many configurations are being covered. The kernels used by popular distributions are well-tested, but enabling other configuration options is a fast route into uncharted territory. The Linux kernel isn't going to stop getting new features — so the only real solution to the problem is to try to simplify existing configuration options when possible. The recent work to remove special uniprocessor support from the scheduler is an example of that.

Ultimately, among the many challenges of kernel development, this is not the most urgent or important. It is worth keeping an eye on, though, for the sake of the sanity of anyone trying to configure a kernel, if nothing else.