Today, the operating system Linux is widely used in diverse environments, as its kernel can be configured flexibly. In many configurable systems, managing such variability can be facilitated in all development phases with product-line analyses. These analyses often require knowledge about the system’s features and their dependencies, which are documented in a feature model. Despite their potential, product-line analyses are rarely applied to the Linux kernel in practice, as its feature model still challenges scalability and accuracy of analyses. Unfortunately, these challenges also severely limit our knowledge about two fundamental metrics of the kernel’s configurability, namely its number of features and configurations. We identify four key limitations in the literature related to the scalability, accuracy, and influence factors of these metrics, and, by extension, other product-line analyses: (1) Analysis results for the Linux kernel are not comparable, because relevant information is not reported; (2) there is no consensus on how to define features in Linux, which leads to flawed analysis results; (3) only few versions of the Linux kernel have ever been analyzed, none of which are recent; and (4) the kernel is perceived as complex, although we lack empirical evidence that supports this claim. In this article, we address these limitations with a comprehensive, empirical study of the Linux kernel’s configurability, which spans its feature model’s entire history from 2002 to 2024. We address the above limitations as follows: (1) We characterize parameters that are relevant when reporting analysis results; (2) we propose and evaluate a novel definition of features in Linux as a standardization effort; (3) we contribute torte , a tool that analyzes arbitrary versions of the Linux kernel’s feature model; and (4) we investigate the current and possible future configurability of the kernel on more than 3,000 feature-model versions. Based on our results, we highlight 11 major insights into the Linux kernel’s configurability and make 7 actionable recommendations for researchers and practitioners.

This is the RCR report accompanying our TOSEM’25 paper How Configurable Is the Linux Kernel? Analyzing Two Decades of Feature-Model History . In this report, we bundle all data relevant to our paper for the purpose of reproducibility and long-term archival. This includes the feature-model extraction tool torte , as well as a comprehensive feature-model dataset and experimental results.

Feature models are commonly used to specify valid configurations of a product line. In industry, feature models are often complex due to numerous features and constraints. Thus, a multitude of automated analyses have been proposed. Many of those rely on computing the number of valid configurations, which typically depends on solving a # SAT problem, a computationally expensive operation. Even worse, most counting-based analyses require evaluation for multiple features or partial configurations resulting in numerous # SAT computations on the same feature model. Instead of repetitive computations on highly similar formulas, we aim to improve the performance by reusing knowledge between these computations. In this work, we are the first to propose reusing d-DNNFs for performing repetitive counting queries on features and partial configurations. In our experiments, reusing d-DNNFs saved up-to \(\sim\) 99.98% compared to repetitive invocations of # SAT solvers even when including compilation times. Overall, our tool ddnnife combined with the d-DNNF compiler d4 appears to be the most promising option when dealing with many repetitive feature-model counting queries.

Abstract Product lines are widely used to manage families of products that share a common base of features. Typically, not every combination (configuration) of features is valid. Feature models are a de facto standard to specify valid configurations and allow standardized analyses on the variability of the underlying system. A large variety of such analyses depends on computing the number of valid configurations. To analyze feature models, they are typically translated to propositional logic. This allows to employ SAT solvers that compute the number of satisfying assignments of the propositional formula translated from a feature model. However, the SAT problem is generally assumed to be even harder than SAT and its scalability when applied to feature models has only been explored sparsely. Our main contribution is an investigation of the performance of off-the-shelf SAT solvers on computing the number of valid configurations for industrial feature models. We empirically evaluate 21 publicly available SAT solvers on 130 feature models from 15 subject systems. Our results indicate that current solvers master a majority of the evaluated systems (13/15) with the fastest solvers requiring less than one second for each successfully evaluated feature model. However, there are two complex systems for which none of the evaluated solvers scales. For the given experiment design, the solvers that consumed the least runtime are (2.5 seconds in sum for the 13 systems) and (3.5 seconds).