Analysing the Linux kernel feature model changes using FMDiff

In this work, we assimilate configuration options declared in the Kconfig language to features and the set of options with their constraints to a feature model [37]. The models created using Kconfig will differ from more standard feature models declared using FODA notation [18], but the constructs of both notations of can be mapped to one another [34].

In the Kconfig language, features have at least a name (following the config keyword on line 3) and a type. The type attribute specifies what kind of values can be associated with a feature. A feature of type Boolean can either be selected (with value y for ‘yes’) or not selected (with value n for ‘no’). Tristate features have a second selected state (m for ‘module’), implying that the features are selected and are meant to be added to the kernel in the form of a loadable kernel module. Finally, features can be of type integer (int or hex) or type string. In our example, the ACPI_AC feature is of type tristate (line 4). Features can also have default values, in our example the feature is selected by default (y on line 5), provided that the condition following the if keyword is satisfied. The text following the type on line 4 is the prompt attribute. It defines whether the feature is visible in the configuration tools during the configuration process. The absence of such text means the feature is not visible.

Kconfig supports two types of dependencies. The first one represents prerequisites, using the depends (or depends on) statement followed by an expression of features (see line 6). If the expression is satisfied, the feature becomes selectable. The second one, expressing reverse-dependencies, is declared by the select statement. If the feature is selected, then the target of the select will be selected as well (POWER_SUPPLY is the target of the select statement on line 7). The select statement may be conditional. In such cases, an if statement is appended. depends, select and constrained default statements are used to specify the cross-tree constraints of the Linux kernel FM. A feature can have any number of such statements.

Furthermore, Kconfig provides the means to express constraints on sets of features, such as the if statement shown on line 1. This statement implies that all features declared inside the if block depend on the ACPI feature. This is equivalent to adding a depends ACPI statement to every feature declared within the if block. Another possibility is to use choices. Such statement provides constructs similar to “alternative” (1 of) and “or” feature constraints (1 or more of) found in the FODA feature modelling notation [18]. A choice itself can also be subjected to constraints and have dependencies expressed using depends statement.

Finally, features can have the “option” attribute, allowing the definition is a wide range of key/value pairs associated with features. This is used to flag features to be used in default (or generated) configurations for instance—option with the key “def_conf_list”. Another usage is to tune the module resolution mechanism or import additional variables.

Kconfig offers the possibility to define a feature hierarchy using menus and menuconfigs. Those objects are used to express logical grouping of features and organize the presentation of features in the kernel configurator. The configurator may also rely on the dependencies declared between features to create the displayed hierarchy. Constrains defined on menus and menuconfigs are applicable to all elements within. Menu can have the “visible” attribute, associated with a Boolean expression of features, complementing the “prompt” attribute. More details about the Kconfig language can be found in the official documentation.²

Such tools use the textual descriptions of the Linux features contained with Kconfig files as an input and provide a collection of selected features as an output, in the form of a list of feature names. During the configuration process, the configurator identifies the files to include and the features to display, depending on constraints expressed in those files. Constraints on file selection, or selectability of features, are resolved using naming convention based on feature names.

The choice of the target hardware architecture (e.g. X86, ARM, SPARC) does not follow this rule. Because the choice of target architecture defines which file should be read first, it uses another mechanism. The name of the chosen architecture is defined during start-up (and can be modified later on) and stored in a variable used to build the first visualization of the FM ($SRCARCH, visible in “./Kconfig”). If no target architecture is given when starting the tool, it uses the architecture of the machine on which it is run by default. As a result, no parts of the Linux kernel FM represent the choice between architectures, while the architectures themselves are present as features.

This becomes important when rebuilding the Linux FM: without knowing which hardware architecture is being considered, we do not know which files to consider when rebuilding the FM. To avoid this problem, the methodology commonly applied is to rebuild a partial Linux FM per supported hardware architecture [21, 23]. In this study, we use this specific approach when rebuilding the Linux FMs and analysing FM changes.

A prerequisite to our approach is to be able to extract feature definitions from Kconfig files. For this, we use an existing tool, Undertaker, to translate Kconfig features into an easier to process format [43]. This tool has been used in the past for similar purposes. Undertaker uses it to reformat the Kconfig model before using it to determine feature presence conditions. It produces a set of “.rsf” files, containing annotated triplets formatted according to the “Rigi Standard Format” [40]. Each file contains an architecture-specific FM, i.e. an instance of the Linux FM where the choice of hardware architecture is predetermined.

The first line shows the declaration of a feature (Item) with name ACPI_AC and type tristate. The second line declares a prompt attribute for feature ACPI_AC and its value is set to true (1). The third line declares the default value of the ACPI_AC feature, which is set to y if the expression X86&& ACPI evaluates to true. Line 4 adds a select statement reading when ACPI_AC is selected the feature POWER_SUPPLY is selected as well, if the expression X86&& ACPI evaluates to true. Finally, the last line adds a cross-tree constraint reading feature ACPI_AC is selectable (depends) only if X86&& ACPI evaluates to true.

Undertaker eases feature extraction but modifies their declaration. Among the applied modifications, two are most important for our approach: first, Undertaker flattens the feature hierarchy and then resolves features depends statements. Concerning the flattening of the hierarchy, Undertaker modifies the depends statement of each feature to mirror the effects of its hierarchy. For instance, Undertaker propagates surrounding if conditions to the depends statements of all features contained in the if-block. This explains the addition of ACPI to the condition of the depends statement on line 5 of Listing 2. Concerning the resolution of depends statements, Undertaker propagates conditions expressed in the depends statement of a feature to its default and select conditions. This explains the condition X86&& ACPI that has been added to the select (ItemSelects) and default value (Default) statements. Such transformations will influence the results of the comparison process and the interpretation of the captured changes. However, it has to be noted that the changes preserve the Kconfig semantics as described in [33].

The main objective of FMDiff is to automate the extraction of changes occurring on the Linux FM and classify those changes according to the scheme presented in the previous section. The extraction of feature changes is performed in several steps as depicted in Fig. 2.

FMDiff’s value lies in its ability to accurately capture changes occurring on the Linux feature model (consistency) and its ability to provide information that would be otherwise difficult to obtain (interestingness). To evaluate FMDiff with respect to those two aspects, we compare it with the information on changes that we obtained by manually analysing the textual differences between two versions of Kconfig files. We consider FMDiff data to be consistent if it contains all changes seen in Kconfig files, and its data interesting if it provides more information than what can be obtained using textual differences. We start by describing the data set used for the evaluation and then assess them separately.

FMs, as central elements of the design and maintenance of SPLs, have attracted substantial attention over the past few years in the research community. For example, several studies describe practical SPL evolution scenarios related to FM changes [25, 30, 32], focusing mostly on addition and removal of features. An open question, however, is whether the changes commonly studied are also the most frequent ones on large scale systems. This leads us to our first research question, which we answer using FMDiff data. RQ1: What are the most common operations performed on features in the Linux kernel feature model?

Let us consider the highest level of changes that FMDiff captures: addition, removal and modification of features. We use our database to query, for a given architecture, features that were changed during a specific release. Listing 3 shows an example of such query, giving us the number of features modified during release 3.0 for a single architecture. We compute, for sixteen releases, the total number of changed features and the number of modified, added and removed features in each architecture-specific FM, using only the first level of our change classification. To obtain an overview of the changes occurring in each release, we average number of modified, added and removed features per architecture.

As shown in Fig. 4, during release 3.0, the average number of feature changes in architecture-specific FMs were 722. About 70 % of those changes are modifications of existing features, 22 % are additions of new features, and only about 8 % of those changes are feature removals. Note that the total number of architectures taken into account varies over time. In Fig. 4, the number of architectures used for the computation of the graph is noted in parenthesis above each column.

Over the 14 studied releases, on average per architecture, creation of new features accounts for 10–50 % of feature changes. Deletion of features accounts for 5–20 % of all feature changes, and modification of existing features accounts for 30–80 % of all feature changes.

In this case, modifications of existing features include modification of their “depend statement”. Such statements are affected by direct developer action (edition of the feature attribute in a Kconfig file) or by changes in the feature hierarchy, as the hierarchy is used during FM extraction (see Sect. 2).

With this information, we can answer our first research question. Modifications of existing features account, on average, for more than 50 % of the feature changes in most releases (13 out of 16), making them the most frequent high-level feature change occurring on the Linux kernel FM. This clearly shows that modifications of existing features is a common operation during the evolution of the Linux FM compared to the other changes (adding and removing features). This conclusion above is specific to certain types of representations of FMs. In the most common FODA notation, cross-tree constraints refer to features, but are attached to a FM rather than to the features themselves. A modification to a cross-tree constraint is arguably different than a feature modification. In this specific case, because cross-tree constraints are part of the definition of a given, well-specified feature, we can make such claim.

Thanks to Undertaker hierarchy and attribute expansion, FMDiff not only captures changes visible in Kconfig files, but also the side effects of those changes (indirect matches). It makes explicit FM changes that would otherwise only be visible by manually expanding dependencies and conditions of features and feature attributes. Such an analysis requires expertise in the Kconfig language as well as in-depth knowledge of Linux feature structures. As mentioned in Sect. 4.2, FMDiff captures accurately a large majority of feature changes applied to the Linux kernel FM. Using FMDiff, feature changes are stored as lists of statement changes with the attribute values before and after the change (following our classification). Developers and maintainers modifying Kconfig files can use our tool to assess the effect of the changes they perform on the feature hierarchy. By querying FMDiff data, they can obtain the list of feature changes between their local version and the latest release. This will give them insight on the spread of a change by answering questions such as “which features are impacted?” and “should this feature be impacted?”. Moreover, developers can follow the impact of changes performed by others on their subsystem, by looking at changes occurring on features of their sub-system.

The extraction of fine-grained feature changes allowed to show that modification of existing features was a very frequent change occurring on the Linux feature model. If we look at previous research on the evolution of highly variable systems [17, 21, 25, 27, 30], we can see that the focus is put mostly on scenarios leading to the apparition or removal of features (such as add, remove, merge or split). In the context of Linux, extending those studies to cover the modification of existing features would be beneficial. The data collected by FMDiff will help in such endeavours, pinpointing instances of such scenarios in this history of Linux kernel FM.

The comparison of architecture-specific FMs evolution showed us that those FMs evolved differently. The proportion of feature changes affecting all architectures varies between releases from 10 to more than 50 %. We also see that, if a change affects all architectures, in almost every cases, the change is the same in all architectures. This limits the validity of extrapolating observations about FM evolution from one architecture to others. However, it is interesting to note that, once we determine that a change is visible in all architectures, we can safely assume that the modification is the same. Future studies of the Linux kernel feature model evolution using a similar feature model reconstruction technique should be clear about the studied architectures, as this will influence the results.

For this study, we focused on feature changes that affected exactly all architectures. An alternative would have been to identify clusters of architectures evolving more similarly than others. For instance, we can imagine that the evolution of the ARM has more in common with the ARM64 architecture than the X86. Then, it would be possible to extrapolate observations, not to all, but to a well- defined set of architecture-specific FMs. The data collected during this study could be of use to identify such clusters.

The amount of changes affecting all architectures puts us at odd with respect to the development practices of the Linux developers. On the one hand, our data show that feature changes visible in all architectures occur in every release, in large proportion. On the other hand, in Sect. 5.2, we show anecdotal evidence that developers are not inclined to cross-compile. We can assume that the delivered assets compile—at least for the architecture on which the developer was working. With more than 13,000 features, the number of possible configurations of the kernel is immense. Given that modifications to features will only affect specific configurations, only the developers and experts will know which configurations should be tested. So the changes might remain untested and a faulty feature could be delivered. Then, if this happens, the criticality of such problems will depend on how frequently this feature is used on the various platforms. We have to keep in mind that as long as the feature is not mandatory for a system, the problem can simply be fixed by not including it in the configured kernel image. Perhaps such errors are not critical nor frequent enough to warrant the use of much heavier testing practices.

Nonetheless, as shown by our data, cross-architecture feature changes occur frequently. In such situations, developers do not seem to have the means to identify which architectures might be affected by their changes and do not consistently test. A tool, such as FMDiff, can capture the impact of feature changes across architectures. With this additional information, developers would have a better view of how often their modifications affect different architectures, making them more aware to such situations. If they wish to cross-compile their code, then FMDiff would give them a list of the impacted architectures to consider first.

A threat to the validity of our study is the representativeness of changes observed on a transformed version of the Linux FM when reasoning about its evolution. After extracting the Linux FM using Undertaker, the hierarchy is flattened and the constraints propagated on feature attributes. As a consequence, the changes captured by FMDiff include the edits performed by developers on Kconfig files as well as their consequences on the other features of the model. After the model transformation, we cannot differentiate between developer edits in the Kconfig files (human operation) and the propagated effect of those changes on other features. Following this, we transform the Undertaker model into an EMF model for comparison purposes; further modifying the data, we use for this study. We argue that both developer edits and their propagated effects are relevant for the study of the evolution of the Linux FM. The transformation performed by Undertaker adheres to the Kconfig semantics as described in [33] (except for the “range” attribute, which is not extracted). This comforts us in the idea that the transformed model in the “.rsf” format produced by Undertaker can be used as a mean to study the evolution of the Linux FM. The model transformation from “.rsf” to EMF does not preserve the semantics of the Kconfig language, as we do not keep track of the order of certain attributes (such as default statements), and we do not consider CHOICE elements. Our data set cannot be used to reflect on the evolution of the allowed configurations of the Linux kernel: we cannot tell which configurations were added or removed by looking at the feature changes captured by FMDiff. But, as we have shown in Sect. 4.2, the changes captured by FMDiff are consistent with the changes observed in Kconfig files. For those reasons, we are confident that the gathered data can be used to observe and reflect on feature changes occurring in Kconfig models.

Over time, the Kconfig language has evolved, and modifications to the constructs of the language should influence our change classification and comparison process. We did not take this into account for this study, and we might miss new attributes or attempt to capture information no longer relevant. This constitutes our second threat to validity. To mitigate the effects of potential language evolution, we restricted the scope of releases we studied. Release 2.6.38, the first of our study, is the oldest release for which our version of Undertaker was able to extract all architecture-specific FMs. We extended the scope of releases from there up to the most recent release at the time of writing (3.14). Using Git, we manually inspected the history of the Kconfig parser and grammar in the Linux repository (the “./scripts/kconfig” folder). We found a minor modification to value attribute (long integer allowed on value based features for instance).¹³ We also found modifications to the allowed values on feature attribute “option” ¹⁴ as mentioned in Sect. 2, irrelevant in the context of this study. The other changes occurring during the studied releases were, as far as we can see, modifications to Kconfig internals, with no impact on the information captured by FMDiff. We have to consider that for a study over a longer period of time, we would have to take into account those changes, adapt the tool and classification in accordance to the evolution of the language.

As reported in Sect. 3 and mentioned here, information is lost during the model transformation and comparison process. The third threat to validity we consider is the influence of the missing information on our validity of the resulting data set. The “range” feature attribute is not extracted and as such not used during comparison. CHOICE structures, present but with a specific naming convention, are removed from our intermediate model. However, the range attribute is not used widely (less than 170 occurrences in 3.10 kernel, for over 12,000 features), and for this reason, we do not believe that this influenced our results or conclusions. During our manual evaluation of FMDiff, we found no occurrence of changes on CHOICE structures, comforting us in the idea that this is not a common change. But we assume that such changes can occur and would be overlooked by FMDiff. Changes to CHOICE structure would impact the contained features—the hierarchy flattening transformation ensures this. While we do not capture CHOICE changes, we can still observe their effects on features. For those reasons, we believe the loss of information has a minimal impact on our observations but must be taken into account for further analysis.

A threat to the internal validity of our study is the effect of the hierarchy flattening transformation on the number of observed feature modifications. When a Menu, Menuconfig, Choice or If construct is modified by developers, changes to its dependencies will be reflected on the features it contains. As direct consequence, we will observe more feature modifications than if we looked at the actual edits performed by the developers, increasing the number of observed modifications of existing features. We would argue here first that the modifications do occur: the features are indeed modified, but indirectly. In that sense, the captured information is accurate and does reflect the actual state of features in the feature model. Considering the overwhelming majority of modification of existing features in certain releases (more than 70 % in release 3.7), we believe that our conclusion holds: feature modifications are, if not the most, at least a very common type of change on every observed release.

The first threat to the external validity of this approach is the use of a specific Kconfig-centred change classification. Our feature change classification is tightly linked to the Kconfig language and would be difficult to reuse in other contexts. However, Kconfig is used in a number of highly variable systems [6], all of which could reuse directly our change classification.

The second threat to the external validity is the lack of application of FMDiff on other systems than Linux. The implementation of FMDiff ties us to a specific type of system. Moreover, the Kconfig-based change classification has a pervasive effect on the different components of the tool, making adaptation potentially complicated. But the approach presented in this paper could be applicable to highly variable systems having an explicit variability model, as often found in the software product line domain for instance. While the Linux kernel is not a software product line, it does have the main technical characteristics of such systems [36] hinting that our approach could be applicable in this larger context. Existing feature change classifications [8, 26] can be adapted, as we did in this work, to match other feature notations. Then, one will have to adapt the feature model comparison process to support that new classification. Previous work on feature models showed that their maintenance can be complex and error prone [5, 15]. With an approach such as FMDiff, it would be possible to extract new information about the evolution of the features using already existing artefacts, at the cost of adapting our tool.

Finally, the last threat to the external validity of our study concerns the Linux-specific character of the comparison of the evolution of architecture-specific FMs. While not all SPLs are affected by the hardware architecture they run on, we can often find a set of high-level features that can be used to define “sub-product lines” as we did using the architectures with the Linux kernel FM. In such cases, one can apply the methodology presented in this work to analyse the co-evolution of those different “sub-product lines”. For instance, in the automotive domain, one can use this approach to identify which feature changes affected the variability model of the “sport”, “city” and “family” variants of a car, where each variant is a product line on its own. Such view of the effect of changes can be of use in area other than the Linux kernel.