Variability Modeling in the Real - Generative Software Development
Contents
1. 600 400 200 TE _ ieee T 0 5 10 15 20 Number of referenced features Number of features S099 Figure 4 Feature dependencies per feature re parentings move packages in the hierarchy however 10 options and 2 components were re parented as well For ex ample the CYGBLD_GLOBAL_OPTIONS component from CYG PKG_HAL_I386_PC package was promoted to the top level and in addition to its syntactic children two new options were re parented under this component Still since rela tively few features 3 in eCos 5 in Linux violate hierar chical rules of feature modeling we observe that practition ers find hierarchical organization of dependencies natural Constraints The vast majority of features surprisingly 86 both for Linux and eCos declare constraints of some sort configuration visibility or defaults Fig 4 shows his tograms with dependencies per feature defined as the num ber of features referenced in constraints of a given feature In Linux most features refer to 2 4 other features this range is much lower in eCos with typically 1 2 dependencies Some features declare a large number of dependencies the maxi mum is 56 in Linux and 21 in eCos Table 4 summarizes the use of visibility conditions and defaults Both Linux and eCos models use visibility condi tions In Linux 3 of features have an explicitly specified prompt condition like JFFS2_COMPRESS rather than just via depends on an2. 82 7 Literals 632 10 775 62 Conditionally derived 198 3 N A Unconditionally derived 736 12 218 18 Table 4 Visibility and default statistics to be reconfigured to enable the selection A rudimentary propagation support is offered by the select construct it enforces a selection of a single feature when the feature host ing the statement is selected The selection is made without respecting any constraints This imperative behaviour can lead to illegal configurations and requires Kconfig developers to explicitly specify any transitive dependencies to maintain consistency For example LATENCY_TOP contains selects for both KALLSYM and KALLSYM_ALL KALLSYM_ALL depends on KALLSYM thus the sole selection of KALLSYM_ALL would be sufficient if the configurator used a propagating reasoner In fact the official documentation and the Linux kernel com mit log contain multiple warnings and complaints about the error proneness of using this construct 11 Still the Linux model is full of select statements as this is the only way to obtain limited propagation in the configurator The CDL configurator is far more intelligent than its Kcon fig counterpart When the user modifies a configuration the tool detects all constraint violations and offers the user sup port to resolve them via an inference engine Every change to the model is wrapped in a transaction and the configurator checks for any constraint violation
3. tem version 2 JFFS2 supported by both OSs In fact eCos s JFFS2 implementation was ported from Linux JFFS2 is one of very few of such ports but it makes an ideal ex ample to illustrate the similarities and differences between Kconfig and CDL To give a realistic impression of both lan guages we keep the examples close to the originals in partic ular we retain the original identifiers which differ somewhat from the names in Fig 1 The few lines introduced purely for the purpose of the example are underlined we also left out unnecessary parts of the corresponding sources Our dis cussion will follow Table 1 as an outline The table summa rizes the similarities and differences among Kconfig CDL and FODA based feature modeling and provides citations for concepts that go beyond the original FODA notation Features A feature is a label that can take one or more of the following roles 1 User feature a configuration option that can be set by the user in a configurator 2 Grouping feature a label grouping a set of other re lated features such as a menu 3 Implementation feature a configuration option accessed by the build system or a generator and 4 Derived feature a configuration option automatically computed via constraints Kconfig and CDL are domain specific languages providing specialized keywords for various kinds of features Tbl 1 row 1 Feature kinds in Kconfig reflect their appearance in the configu
4. www informatik uni leipzig de berger cdl_semantics pdf 3 Q Boucher A Classen P Faber and P Heymans Introducing TVL a text based feature modelling language In VaMoS 2010 4 K Czarnecki and U W Eisenecker Generative Programming Methods Tools and Applications Addison Wesley Boston MA 2000 5 D Dhungana P Heymans and R Rabiser A formal semantics for decision oriented variability modeling with DOPLER In VaMoS 2010 6 D Dhungana R Rabiser P Griinbacher and T Neumayer Integrated tool support for software product line engineering In ASE 2007 7 P Griinbacher R Rabiser D Dhungana and M Lehofer Model based customization and deployment of Eclipse based tools Industrial experiences In ASE 2009 8 A Hubaux A Classen M Mendonga and P Heymans A preliminary review on the application of feature diagrams in practice In VaMoS 2010 9 M Janota G Botterweck R Grigore and J P M Silva How to complete an interactive configuration process In SOFSEM 2010 0 K Kang S Cohen J Hess W Nowak and S Peterson Feature oriented domain analysis FODA feasibility study Tech Rep CMU SEI 90 TR 21 1990 1 R Lotufo S She T Berger K Czarnecki and A W sowski Evolution of the Linux kernel variability model In SPLC 2010 2 M Mendonca A Wasowski K Czarnecki and D D Cowan Efficient compilation techniques for large scale feature models In GPCE 2008 3 M Mendonga A Was
5. If one occurs the inference engine tries to resolve the conflict by a heuristics based recursive search algorithm It builds a tree of transactions starting a transaction for each new sub conflict that arises when testing conflict resolutions The en gine estimates the benefit of particular sub conflict resolu tion by using the number of required changes and source of the values being changed e g user default or inference If a sub resolution is beneficial it gets committed to the parent transaction If one overall solution is found for the top level conflict the tool lists necessary changes and requests confir mation Otherwise the conflict requires manual resolution We investigated the inference engine s source code with respect to correctness and completeness The resolution is correct since the proposed resolutions are verified against the model constraints The resolution is incomplete as e The inference rules are incomplete For example the engine has rules for handling cardinality constraints on interfaces of 0 or 1 but not for arbitrary bounds e The recursion depth is limited to 3 levels thus reason ing on transitive requires dependencies is incomplete e The engine uses a greedy search evaluating resolutions to sub conflicts in separation and pruning all but the optimal one This may prune all successful branches Although the inference engine is less powerful than general CSP solvers it performs very wel
6. None menu none mandatory Specification syntactic and computed syntactic and reparenting syntactic Child to parent impl visibility configuration amp visibility configuration 2 Root synthetic synthetic explicit 2 Mutex 0 1 optional Boolean choice interface constraint INT lt 1 MUTEX group 4 Or 1 mandatory tristate choice interface constraint INT gt 1 OR group 4 2 Xor 1 1 mandatory Boolean choice interface constraint INT 1 XOR group 8 s group Interval m n N A interface constraint m lt INT lt n m n group 16 Configuration Value restrictions select range requires active_if legal_values cross tree constraint cross tree constraint Derived features non prompt default calculated interface rare 5 2 Defaults prompt default default_value rare 4 o Visibility conditions prompt condition active_if rare 5 22 Expression operators amp amp also inequality arithm and str ops unspecified 28 Binding modes three value logic N A rare 4 Textual content prompt help display description description Modularization textual inclusion dynamic loading unloading rare 3 5 Build symbols one to one one to many unspecified Code mappings no uses KBuild m n yes 1 n and build specifications N A Table 1 Mapping of concepts between Kconfig CDL and feature modeling Feature representation The semantics of a feature model is a set of configurations A configu
7. a list e g requires is_substr LIBS lib target a Such constraints implement code mappings In Linux these are computed in KBuild outside of the model Summary Let us now summarize the main lessons learnt Core FODA concepts Tbl 1 are used in both models Boolean features are the basic and most common type the constraint language should support arbitrary Bool ean constraints including mutual exclusion e Linux uses heavily the three state logics for controlling binding mode more than half features are tristate e The languages benefit from being domain specific Do main vocabulary increases understandability Integer features are important for embedded systems eCos uses arithmetic operators and comparisons e Strings are mostly used for file names string opera tions other than equality tests seem essential if the build system lacks appropriate support e Group constraints dependent on a remote feature im prove modularity in the eCos model Since only basic cardinalities are used the interfaces appear overly gen eral It suffices to include n ary XOR OR and MUTEX operators in the constraint language e Separating configuration hierarchy from syntactic hier archy helps maintain modularity of the developer view separately from the user view Like in feature modeling child to parent implications are enforced in CDL and in most of the Linux model Default values also computed are used a lot in prac tice
8. are available We reported early findings on the Linux model in a previ ous workshop paper 19 however the present paper differs significantly The previous work was to extract a FODA feature model from Linux and compare it with feature mod els from research papers The present work compares two languages and models in their full richness beyond FODA including their formal semantics and a different set of statis tics The resulting findings Sections 2 4 are new We also studied the evolution of the Linux model 11 showing that the number of dependencies has grown proportionally to the number of features over the last five years Table 1 provides references to research on feature model ing concepts Most of them were present in FODA however computed defaults visibility conditions and derived fea tures are marked as rare State of the art feature modeling languages such as TVL 3 and pure variants do not support them Computed defaults were proposed by researchers 4 but not provided by feature modeling languages None of the other variability languages supports binding modes via three valued logics Interestingly Dopler sup ports visibility conditions Although it has been defined as a decision modeling language 5 it shares many characteris tics with feature modeling The connection between Kcon fig and feature modeling was made in 20 We advance this work by studying Kconfig s semantics and the Linux model I
9. is visible Invisible features can not be part of a configuration Derived features comprise in terfaces as well as other feature kinds with the calculated keyword which carry an expression that computes their values for example line c 25 A feature can either use default_value or calculated but not both Thus com plex conditionally derived features do not appear in CDL A unique feature of Kconfig is its first class support for a three valued logic Its main operators are defined as follows eval e 2 eval e eval e amp amp e2 min eval ez eval e2 eval ei e2 max eval e1 eval e2 The semantics of expressions follows the logic of Kleene where mod corresponds to the unknown state The equality test is defined only between constants i e tristate int hex and string and features state It evaluates to y 2 if the values match and to n 0 otherwise Textual content Both Kconfig and CDL allow providing natural language descriptions for features Tbl 1 row 6 a short text called prompt k 7 and display c 7 that is displayed to the user to elicit a configuration decision and a longer description called help k 19 and description c 19 that explains the feature in detail Modularization Modularization allows division of specifica tions into parts Kconfig and CDL have modularization ca pabilities that range from static source inclusion in Kconfig to more complex mechanisms for dynamic loadi
10. kconfig language txt avail able in the kernel tree at kernel org seen 2009 11 23
11. support conflict resolution in reconfiguration for rich languages such as Kconfig and CDL remains an in teresting open problem Kconfig and CDL are interesting and highly relevant study objects Designed not by researchers but by developers of large industrial strength product lines they are tailored to satisfy the needs of these large projects M SLOC for Linux and 0 9M SLOC for eCos The size of the models 6320 features for Linux and 1244 features for eCos witnesses the scalability of the respective modeling approaches Since both Linux and eCos are open source their usage can be studied openly and researchers can independently validate and replicate such studies Both languages sup port quite different systems the kernel of a general purpose OS Linux vs the entire real time OS for embedded ap plications eCos They were developed independently from each other and independently from the feature modeling languages with research origin Since they share many sim ilar concepts they can confirm the importance of the mod eling constructs discussed in the literature Although our analysis is limited to variability languages and models from the OS domain we believe that other projects such as RT embedded systems that require static configuration will likely have similar requirements Thus our findings are of interest to a growing audience of vari ability modeling language and tool designers especially in efforts such as the de
12. the empty value can be seen as a present feature with that value or an absent feature the two cases are indistinguishable In CDL every feature has two values an enabled state and a data value The enabled state is a Boolean and encodes the presence or absence of the feature the data value is dynamically typed and used to store numbers and strings Thus a configuration maps features to value pairs o F 0 1 x Val and if o f e d then d type of f CDL refers to the type of a feature as a flavor The available flavors map neatly to FODA features as follows none gt Mandatory with no attribute bool Optional with no attribute data Mandatory with attribute booldata gt Optional with attribute More precisely features with the flavors none and data can be made optional by specifying a configuration constraint explained later Still an optional feature with flavor none or data differs from its respective bool or booldata counter part the latter two are shown as user selectable checkboxes in the configurator whereas the former two have no check boxes since their presence is controlled via visibility condi tions Figure 3 includes features assuming numeric values CYGOPT_FS_JFFS2_DEBUG Bool values CYGOPT_JFFS2_ NAND or strings CYGOPT_FS_JFFS2_COMPRESS_CMODE Hierarchy Typical modeling languages organize features into hierarchies Tbl 1 row 3 We distinguish between syn tactic and configuration hierarch
13. various kinds of features including architectural terms CDL such as compo nents and interfaces or terms related to the configura tor UI Kconfig such as menus The vocabularies are specific to the two projects and likely improve the un derstandability of the models within the communities For the second objective the study reveals interesting differ ences in how Kconfig and CDL provide the above concepts e Feature representation Kconfig treats each feature as a variable either of Boolean integer or String type CDL in addition also supports composite features that contain both a Boolean component encoding fea ture presence and a numeric or string value e Feature hierarchy For both languages the hierarchy shown to users in a configurator largely follows the syn tactic nesting in the corresponding model still both D ROM filesystem zm Sonics j CYGPKG_POSIX_CLOCKS Unsatisfied Ri Y 4 JFFS2 filesystem ARE gt os i ee ERES CYGHWR_IO_FLASH_DEVICE Unsatisfied R i OOE amid CYGPKG_FILEIO_FNMATCH Unsatisfied RI PM Include write support for JFFS2 I Support for NAND flash n gt i E Debug level 0 Property Value v VE ress data URL refifileio html F Compress data using zlib Macro CYGOPT_FS_JFFS2_COMPRESS Ml Compress data using rtime File fhome shshe Dev ecos ecos 3 0 I compress data using rubin oe Ld iid Set the default compression mod priority 2vor anei Mi eee aloaia Define JFFS
14. 2_COMPRESSION ab Memory pool size o ag TE ab Additional compiler flags D_ECOS ab Suppressed compiler flags e Compression and decompression are entirely handled by the file system and are fully GB JFFS2 FS tests ransparent to applications However selecting oe _ this option increases the amount of RAM required 2 as inac compatiblity lever land slows down read and write operations D Zlib compress and decompress package considerably if you have a slow CPU D VNC Server x Figure 2 The eCos Configtool GUI languages offer some mechanisms to control the con figuration hierarchy separately from syntactic nesting e Group constraints Kconfig supports feature grouping constructs with group cardinalities limited to XOR MU TEX and OR CDL is more flexible allowing integer intervals as group cardinalities however the studied models only use XOR MUTEX and OR cardinalities In feature modeling and Kconfig only parents can impose group constraints on their children in CDL features can impose group constraints on any other features and eCos makes use of it e Visibility and computed defaults Both languages sup port two types of conditions on a feature conditions defining only configuration dependencies and condi tions defining both such dependencies and visibility Further visibility and computed defaults are used to gether to provide derived features automatically com puted features not shown to the u
15. Variability Modeling in the Real A Perspective from the Operating Systems Domain Thorsten Berger University of Leipzig Steven She University of Waterloo berger informatik uni leipzig de shshe gsd uwaterloo ca Rafael Lotufo University of Waterloo rlotufo gsd uwaterloo ca ABSTRACT Variability models represent the common and variable fea tures of products in a product line Several variability mod eling languages have been proposed in academia and indus try however little is known about the practical use of such languages We study and compare the constructs seman tics usage and tools of two variability modeling languages Kconfig and CDL We provide empirical evidence for the real world use of the concepts known from variability mod eling research Since variability models provide basis for automated tools feature dependency checkers and product configurators we believe that our findings will be of interest to variability modeling language and tool designers Categories and Subject Descriptors D 2 2 Software Engineering Design Tools and Tech niques D 2 8 Software Engineering Metrics General Terms Design Languages Measurement Keywords Configuration empirical software engineering feature mod els product line architectures variability modeling 1 INTRODUCTION Variability models represent the common and variable char acteristics or features of products in a product line Prod uct line de
16. con straints are used to model the case where a given package defines an interface required by its implementation and mul tiple other packages provide alternative implementations of that interface In total we had 81 such constraints in eCos Hierarchy Both Linux and eCos have shallow configura tion hierarchies with an average depth of 4 for Linux and 3 for eCos and maximum depth of 8 and 6 respectively The number of features with a given number of children decreases sharply with the increase of the number of children the ma jority of features are leaves 5316 and 947 respectively the second largest class are single child parents 452 and 76 followed by two child parents 161 and 72 Nevertheless the maximum number of children branching is as much 158 and 29 respectively This indicates a need to develop modeling interfaces that support high variation in branch ing from very limited to very wide Recall that unlike feature modeling and CDL Kconfig uses hierarchy to depict a visibility relation instead of a presence condition allowing a child feature to be configured without its parent This possibility is indeed exploited in the Linux model We verified with a SAT solver applied to a derived boolean semantics of the Linux model that 300 fea tures do not imply their parents like JFFS2_ZLIB in Fig 3 We found 39 3 re parented features in eCos Most 1200 1000 800 600 400 200 o 800 xnul
17. config 175 2 8 packages 56 4 5 3 255 4 321 26 a XOR 39 0 6 XOR 11 0 9 ZE or 3 0 05 OR 0 0 5 MUTEX 0 0 MUTEX 1 0 08 2 a Es Ss oc 58 42 0 7 12 1 Table 3 Grouping statistics cf Tbl 1 row 4 4 THE MODELS Let us turn from the languages to their use We now discuss the models of Linux and eCos expressed in Kconfig and CDL respectively Again we will use Table 1 as an outline Features and grouping The Linux model has 6320 features the eCos model is one fifth of this size Table 2 shows the breakdown of features by type The majority of features 95 in the Linux model are bool or tristate with only 3 7 having integer or string types In contrast more than half of the features in eCos are data features this is interesting since the majority of the examples found in the literature have few or no such features 19 Note that we listed booldata features both as switch and data features to reflect their dual nature the percentages are given with respect to the total number of features which counts them only once We established the following reasons for the large percentage of data features in eCos First some feature kinds contain data values by default even though they are not intended to be directly set by the user interfaces carry the count of the number of implementing features selected in a configuration and packages always have the type booldata with the data part representing the package version as a string The
18. d 10 of features in eCos use active_if Further 15 of Linux features specify explicit defaults eCos makes heavy use of explicit defaults 69 of features Only a small part of features is computed via expressions 2 for Linux and 7 for eCos the remaining defaults are specified as literals Recall that Linux supports conditionally derived features i e features that are derived or user changeable with a default value depending on a condition 3 of Linux features belong into this category Finally 12 Linux and 18 eCos of features are unconditionally derived Let us look at some examples of constraints Linux con straints are mostly logical expressions such as a single fea ture or more complex expressions e g SMP amp amp X86_32 amp amp X86_VOYAGER X86_64 Linux constraints often reference integer or string features using equality tests In a single case an integer feature in Linux uses another feature as a bound in a range constraint Many eCos constraints are logical expressions too but arithmetic and string operations are not uncommon For example requires CYGNUM_FS_FAT_NODE_POOL_SIZE gt C CYGNUM_FILEIO_NFILE 2 String concatenation denoted by is often used to produce lists of test or implementation source files calculated tests sprintfl tests sprintf2 CCFILEIO amp amp RAM tests fileio Other constraints check whether a particular file name is included in
19. dels are tree like menus of configuration op tions or features with cross tree constraints among the fea tures Fig 1 presents a sample feature model in the FODA notation which illustrates the core concepts shared by many feature modeling languages The sample model shows the variability of the Journalling Flash File System one of the nu merous files systems supported in both Linux and eCos The boxes represent features The hierarchy represents depen dencies for instance the Default Compression feature allows a further choice of sub features that refine it None Prior ity or Size Filled dots mark mandatory features like De bug Level which must be selected if the parent is Hol low dots represent optional features which do not have this constraint Further several features can be related by a group constraint the sub features of Default Compression are connected by an arc denoting the XOR group constraint exactly one of the three choices has to be selected Finally textual cross tree constraints are listed to the right Our goal is 1 to provide quantitative and qualitative em pirical evidence whether the concepts researched in feature modeling are used in real world modeling languages and product lines and if so how they are used 2 to widen the understanding of the design space for the studied concepts We analyzed the two languages and the models expressed in them the Linux kernel model and the eCos model We
20. died version 3 0 of eCos supports 116 hardware architectures called targets and comprises almost a mil lion lines of code The code base is divided into packages each one containing the source code and a set of CDL files declaring the configurability of the package Each target de fines a set of packages specific to the architecture So called templates aggregate packages with more cross architecture functionality In the configurator a user first selects a target and then one of the templates finally the user may decide to load additional packages into the configuration tree We scope our analysis to the x86 architecture in Linux and i386PC target with the all template in eCos We extended the configurators to export the configuration tree together with all the information necessary for our analysis 3 THE LANGUAGES To compare Kconfig and CDL we reverse engineered for mal semantics specification for each of them 18 2 by an alyzing user manuals testing the tools on examples and inspecting tool implementations This step allowed us to discover many subtle differences and connections Here we summarize the key similarities and differences between the languages using the feature model in Fig 1 as the running example Fig 3 shows the same model in Kcon fig to the left and CDL to the right Both snippets are in fact extracted from the original Linux and eCos models They define the features of the Journalling Flash File Sys
21. efault y choice prompt Default compression if JFFS2_COMPRESS default JFFS2_CMODE_PRIORITY depends on JFFS2_FS config JFFS2_CMODE_NONE bool no compression config JFFS2_CMODE_PRIORITY bool priority config JFFS2_CMODE_SIZE bool size EXPERIMENTAL endchoice endif c 1 c2 c3 c4 c 5 c 6 c 7 c 8 c 9 c 10 c 11 c 12 c 13 c 14 c 15 c 16 c 17 c 18 c 19 c 20 c 21 c 22 c 23 c 24 c 25 c 26 c 27 c 28 c 29 c 30 c 31 c 32 c 33 c 34 c 35 c 36 c 37 c 38 c 39 c 40 c 41 c 42 c 43 c 44 c 45 c 46 c 47 c 48 c 49 cdl_component MISC_FILESYSTEMS display Miscellaneous filesystems flavor none l cdl_package CYGPKG_FS_JFFS2 display Journalling Flash File System requires CYGPKG_CRC implements CYGINT_IO_FILEIO parent MISC_FILESYSTEMS active_if MTD cdl_option CYGOPT_FS_JFFS2_DEBUG display Debug level flavor data default_value 0 legal_values 0 to 2 define CONFIG_JFFS2_FS_DEBUG description Debug verbosity of cdl_option CYGOPT_FS_JFFS2_NAND flavor bool define CONFIG_JFFS2_FS_WRITEBUFFER calculated HAS_IOMEM cdl_component CYGOPT_FS_JFFS2_COMPRESS display Compress data default_value 1 cdl_option CYGOPT_FS_JFFS2_COMPRESS ZLIB display Compress data using zlib requires CYGPKG_COMPRESS_ZLIB default_value 1 cdl_option CYGOPT_FS_JFFS2_COMPRESS_CMODE display Set the default compression mode flavor data default_value PRIORITY
22. have instrumented the native tools supporting the languages to build an infrastructure for collecting quantitative data about the models Guided by the collected statistics we inspected large parts of the models to study actual usage patterns In order to also compare the languages directly as opposed to via models we also compared their semantics Many semantic differences turned out to be subtle and not immediately obvious from the syntax With respect to the first objective our study shows that the core concepts of FODA feature modeling are supported by both Kconfig and CDL and are used in both the Linux and the eCos models These include Boolean optional integer and string features a hierarchy group constraints and cross tree constraints Interestingly both languages and models use concepts that are beyond FODA and have not been as widely studied as the core concepts e Visibility Both languages allow controlling the visi bility of features in the user interface UI of the con figuration tool via visibility conditions e Computed defaults They both support computing de fault values of features using values of other features e Binding modes Kconfig uses three valued logics to specify whether a feature implementation is linked stat ically built for dynamic linking or absent FODA uses much more space if representing this in Boolean logic e Domain specific vocabulary Both languages provide specialized vocabularies for
23. istate and the empty string for string int and hex in CDL the assumed defaults for boolean and data values is 0 In Kconfig visibility conditions defaults and configura tion constraints interact in intricate ways If the visibility condition of a feature is false its default value specification becomes a configuration constraint because the feature can not be accessed by the user to modify the default value We refer to such invisible features with calculated values as de rived features JFFS_FS_WRITEBUFFER in line k 22 is derived since it has no prompt declared thus has a false visibility condition but has a default that determines its value Notice that this feature was not shown in Fig 1 as FODA notation does not include syntax for invisible derived features An example of a conditionally derived feature is JFFS2_ZLIB with a stronger visibility condition prompt and depends on than its default condition just depends on Thus when the feature is not visible its value is derived using its de fault This happens even if its parent JFFS2_COMPRESS is not selected Consequently JFFS2_ZLIB does not establish a child parent implication as in feature modeling notations CDL clearly separates defaults which can be overridden by the user and have no configuration semantics from de rived features which cannot be changed directly by the user Default values are specified using default_value and only take effect when the feature
24. l on the actual eCos model The support for MUTEX and XOR groups is particularly ef fective and the resolution of requires dependencies is far more maintainable than the select statement in Kconfig The main limitation of the CDL configurator is that if several resolutions exist it finds at most one and possibly not the desired one The following comment on the mail ing list sourceware org ml ecos discuss 2001 11 msg00161 html indicates that developers struggle with this problem if CYGPKG_MYPKG_OP1 is active make sure that the list of tests for that package is a substring of CYGDAT_MYPKG_ACTIVE_TESTS This works 50 of the time Problem is the other 50 of the time rather than fiddling with the substrings it enables disables my subpackage Our findings underscore the importance of building con figurators based on strong reasoners Tools employing com plete reasoners do exist for package configuration involving simple use dependencies and version ranges For example p2 in Eclipse is using a SAT solver However scalable reason ing to support conflict resolution for rich languages such as Kconfig and CDL remains an interesting open problem 6 THREATS TO VALIDITY The main threat to the external validity of our findings is that they are based on two languages and two operating systems only On the other hand both are large indepen dently developed real world projects with different objec tives Linux is a general purpo
25. legal_values NONE PRIORITY SIZE Figure 3 A model excerpt expressed in Kconfig left and CDL right Corresponding definitions are aligned they cannot be nested syntactically For example a group of consecutive configs declaring dependency on the same par ent lines k 13 25 is placed under this parent JFFS2_FS In CDL the configuration hierarchy mostly follows the syntactic nesting of features unless declared otherwise Re parenting is a mechanism to explicitly specify a parent from a different syntactic scope see Line c 10 It allows adjust ing the developer oriented structure of the model to make it more user oriented before it is shown in the configurator An important property of the configuration hierarchy in FODA like languages is that the presence of a child feature implies the presence of its parent for each edge from child c to parent p we have that o c o p The configuration hierarchy in CDL has this property too In contrast the configuration hierarchy in Kconfig only enforces the child to parent implications for the visibility conditions So the parent of a feature that is visible in the configurator must be visible However if the parent is not selected a feature can still be selected automatically unlike in other known feature modeling languages Finally both Kconfig and CDL configurators show a syn thetic root a fresh root node that is not explicitly specified in the model This enables w
26. ng of pack ages during configuration in CDL Mapping to code All configs and menuconfigs in Kconfig correspond directly to symbols controlling the build system and to the preprocessor directives of the same name These symbols and their values are referenced in presence condi tions inside the KBuild system and control the inclusion of particular source files from the Linux codebase Although these presence conditions can be of any form they are a disjunction or conjunction of symbols in most cases In CDL feature names do not always correspond directly to symbols for the build and the preprocessor Instead a more fine grained control over symbols is supported such as suppressing symbols defining additional ones or changing their formatting Line c 18 shows an example of a feature defining a build symbol CONFIG_JFFS2_FS_DEBUG which actually appears in the code ported from Linux to eCos Linux ftrs ftrs eCos ftrs ftrs bool type 2313 37 bool flavor 455 37 S tristate type 3692 58 booldata flavor 192 15 3 6005 95 647 52 int type 175 2 8 g hex type 32 0 5 data flavor 489 39 string type 28 0 4 booldata flavor 192 15 235 3 7 681 55 2 menu 80 1 3 component 108 9 2 notype flavor none Total 6320 100 Total 1244 100 1 Repeated as booldata is both switch and data feature type Table 2 Representation statistics cf Tbl 1 row 2 Linux ftrs ftrs eCos ftrs ftrs gt menu 80 1 3 components 265 21 menu
27. nteractive support for resolving variability was ranked highest in a recent expert survey of requirements for prod uct derivation 15 A variety of reasoners have been used to create feature model analyzers and configurators includ ing CSP solvers 23 SAT solvers 21 13 and BDD pack ages 12 These works tested the reasoners on either small meaningful models or large automatically generated models however it is not clear how these tools will scale to handle the Linux and eCos model This remains future work 8 CONCLUSION Our study provides empirical evidence for the use of vari ability modeling in real world large scale systems The study confirms that feature modeling concepts from FODA are used in practice however it shows that more advanced con cepts such as visibility conditions derived features and binding mode are also needed Our language comparison showed intricate semantic interactions among the advanced concepts deepening our understanding of such languages We also identified significant limitations of existing configur ators a call to arms for future research We believe our findings will be of interest to variability modeling language and tool designers 9 REFERENCES 1 D Benavides S Segura and A Ruiz Cortes Automated analysis of feature models 20 years later a literature review Information Systems 2010 2 T Berger and S She Formal semantics of the CDL language Technical Note Available at
28. odeling is re flected in the rise of industrial tools such as pure variants by Pure Systems GmbH and Gears by Big Lever Software Inc Recognizing the interest the OMG currently seeks proposals for a Common Variability Language CVL standard 14 Although variability modeling languages have been de signed both in academia 10 5 3 and industry pure var iants Gears little is known on their practical use A recent survey 8 lists many research contributions on feature mod els but no empirical studies of industrial practice of feature modeling Our work addresses this gap We study and com pare two variability modeling languages and their use Kcon fig 24 and Component Description Language CDL 22 Both were developed as part of open source operating sys tems OSs Kconfig is used to describe the variability of the Linux kernel CDL is part of eCos a real time RT op erating system for embedded devices Both Linux and eCos have vast configuration spaces with thousands of features which explains their need for variability management We compare the constructs the semantics and the usage of Kconfig and CDL while using the well researched con cepts of feature modeling as a reference Feature models were originally introduced as part of the Feature Oriented Domain Analysis FODA 10 They gained popularity with product lines researchers and practitioners alike mostly due to the simple and intuitive notation Feature mo
29. on figuration hierarchy an explicit visibility condition allows non parent features to control the visibility too For exam ple the visibility of CYGPKG_FS_JFFS2 is controlled by the parent c 10 and another feature MTD c 11 In Kconfig the visibility of a feature is controlled by a prompt condition A prompt is a string that follows a type declaration k 7 It is shown to the user when the feature is visible the condition is satisfied The condition is spec ified after the prompt here MTD in line k 7 Note that the select statement in line k 8 is also conditioned on the same condition as the prompt This pattern of guarding other con straints by the prompt condition is frequent in Kconfig thus the language provides a syntactic sugar for it The depends on statement adds a condition to the prompt and all other constraints of a feature For example the prompt default and range specifications of JFFS2_FS_DEBUG are only active if JFFS2_FS is selected as specified in line k 15 Constraint expressions in Kconfig can use logical operators and equality tests over bool tristate integers and strings Range restrictions on integer values are specified using range in Kconfig and legal_values in CDL k 17 c 17 the latter can also be used to specify valid string values c 42 Default values are specified using default in Kconfig k 16 and default_value in CDL c 16 If no default value is specified Kconfig assumes 0 for bool and tr
30. orking with diagrams that are forests and not trees like in FODA Group constraints In feature modeling group constraints restrict the number of sibling features to be selected if their parent is selected Tbl 1 row 4 exactly one child for xor at least one for OR and at most one for MUTEX Alterna tively the constraint can be given as an interval In Kconfig a choice groups a set of features and imposes a group constraint on them Choices are either bool or tristate with a mandatory or optional modifier flag If not specified otherwise a choice is bool and mandatory thus the choice in line k 38 is an XOR group Note that eCos developers decided to model this group differently c 38 with a data flavoured option holding one of three string values encoding the three compression modes CDL interfaces are a more expressive construct for re stricting cardinality of a set of features The value of an interface counts the number of its selected implementations concrete features Restricting this value introduces a car dinality constraint In contrast to FODA like languages CDL does not require that all implementing features are siblings the feature activating the group constraint need not be a parent of the constrained features Feature Constraints CDL and Kconfig support three types of constraints Tbl 1 row 5 1 configuration constraints restrict the legal combinations and values of features 2 de faults provide defa
31. oup con straints are used in practice The three OR groups in Linux are motivated by binding time the OR constraint in the model allows including multiple alternative features in the configured kernel as dynamically loadable modules only one of them will be loaded at runtime The only MUTEX group in eCos represents three alternative random number gen erators There are no MUTEX groups in Linux a possible reason is the need to define a build symbol even when no group member is selected cf JFFS_CMODE_NONE in Fig 3 Recall that CDL interfaces generalize group cardinality constraints This generality is not exploited in practice though We did not find a single instance of a group car dinality constraint which is a proper m n interval as op posed to intervals with lower bound being 0 or 1 and upper bound being 1 or Moreover although an interface can place a group constraint on features that are not siblings all interfaces are implemented by sibling features Still the in terface and the implementing features are usually far apart i e do not have a common parent and are implemented across different packages In other words the group con straint is activated implied by the parent of the interface which is not the parent of the set of constrained features This form of a group constraint is more general than what is found in feature modeling where the parent of the group activates the group constraint Such generalized group
32. owski and K Czarnecki SAT based analysis of feature models is easy In SPLC 2009 14 Object Management Group Common variability language CVL RFP Document ad 2009 12 03 2009 5 R Rabiser P Gr nbacher and D Dhungana Requirements for product derivation support Results from a systematic literature review and an expert survey Information and Software Technology 52 3 2010 6 M Riebisch K B llert D Streitferdt and I Philippow Extending feature diagrams with UML multiplicities 7 P Y Schobbens P Heymans J C Trigaux and Y Bontemps Generic semantics of feature diagrams Comput Netw 51 2 456 479 2007 8 S She and T Berger Formal semantics of the Kconfig language Technical Note Available at eng uwaterloo ca shshe kconfig_semantics pdf 9 S She R Lotufo T Berger A Wasowski and K Czarnecki The variability model of the Linux kernel In VaMoS 2010 20 J Sincero and W Schr der Preikschat The Linux kernel configurator as a feature modeling tool In SPLC ASPL 2008 21 T Thiim D Batory and C Kastner Reasoning about edits to feature models In ICSE 2009 22 B Veer and J Dallaway The eCos component writer s guide Seen Mar 2010 at ecos sourceware org ecos docs latest cdl guide cdl guide html 23 J White D Schmidt D Benavides P Trinidad and A Cort s Automated diagnosis of product line configuration errors in feature models In SPLC 2008 24 R Zippel and contributors
33. ration specifies the presence or absence of each feature and a value for the related integer or string if the feature is present when applicable Kconfig and CDL differ in the ways they represent con figurations see Tbl 1 row 2 In Kconfig a configuration assigns a single value to each feature If F is the set of all features in the model and Val is a set of all possible values then a particular configuration o maps features to values a Fe Val and if o f v then v E type of f Table 1 lists the possible feature types in three categories switch data and none Switch features appear as a checkbox in the configurator Data features allow the user to input a value in a text box Kconfig s menus have no type which corresponds to features of type none in CDL The Kconfig type bool has two values y and n internally represented by 2 and 0 0 denotes feature absence while 2 means that the feature s implementation is compiled stati cally into the kernel Tristate resembles bool except for the additional m value represented internally by 1 which de notes that the feature should be compiled as a dynamically loadable module For example JFFS2_ZLIB k 32 has type bool and JFFS2_FS k 6 is tristate Kconfig supports two integer types int decimal and hex hexadecimal Both types also allow an empty value which is used to encode the absence of an integer feature The type string is ambiguous in this respect a string feature with
34. rator UI menus are pure grouping features menuconfigs are menus that can be enabled and disabled by clicking choices are like menus or menuconfigs except that they also impose grouping constraints on their chil dren and configs are individual options The menucon fig MISC_FILESYSTEMS Fig 3 Linek 1 corresponds to the root in Fig 1 It contains the choice k 38 corresponding to the parent feature of the XOR group Default Compression and eight configs corresponding to the remaining features of Fig 1 all enclosed in if k 4 and endif k 49 CDL feature kinds reflect types of implementation entities they map to packages are top level containers for features mapping to eCos packages Components are nested features grouping other features Options are simple configuration options leaves Several possibly exclusive features can pro vide equivalent functionality required elsewhere Interfaces are abstractions allowing imposing cardinality constraints in such cases Line c 9 states that CYGPKG_FS_JFFS2 imple ments the interface CYGINT_IO_FILEIO not shown concept Kconfig CDL feature models 10 23 Grouping menu menuconfig choice package component interface feature 2 Individual config option feature amp Composition single value bool value w opt data value bool value w opt attribute amp Feature type vS Switch bool tristate bool booldata optional 50 Data hex int string booldata data integer string SS
35. re are 130 data or booldata interfaces and 56 booldata packages in eCos Further 24 of data or booldata features represent enumerations similar to the last option in Fig 3 Interestingly they accept 117 legal values in total which is the number of additional bool features that we would need to express these enumerations in Kconfig as shown in Fig 3 There are also 72 data or booldata features representing compiler flags 4 representing linker flags and 40 holding names of files with test code The remaining 355 data or booldata features or 28 of all features represent diverse configuration constants such as priorities buffer sizes and supported IO ports Many of these constants are specific to a RTOS and would either be set dynamically or not be configurable in Linux As many as a quarter of all eCos features are explicit grouping features Table 3 as opposed to Linux s 4 This is unexpected given that the percentages of non leaf features in both models are comparable 16 for Linux and 24 for eCos some components in eCos are leaves The reason is that Linux also allows nesting of configs so configs can also take a grouping role Whereas menus and menuconfigs cre ate a separate menu structure requiring explicit drill down by the user config hierarchies are shown by indentation and are thus more lightweight to navigate Less than 1 of features in eCos and Linux impose group constraints on their children Let us see how gr
36. saving the user unnecessary configuration work e Visibility control is essential in both models Two con structs are useful a pure configuration condition like requires and a combined configuration and visibility condition like active_if Configuration indepen dent of visibility leads to intricate semantics e Derived features are mostly used to perform calcula tions that otherwise would be hidden in the build sys tem this way feature dependencies are specified uni formly and explicitly in one model 5 THE CONFIGURATORS Kconfig and CDL are supported by GUI based configu rators that both support a configuration process known as reconfiguration The tool is initialized with a configuration loaded from a file or based on default values which is mod ified by the user to reach a desired state Each of the two configurators takes a different approach to ensure that the user reaches a valid configuration The Kconfig configura tor prevents the user from modifications that violate con straints the eCos configurator allows such modifications but it detects violations and helps in resolving them The Kconfig configurator offers little support for prop agating user configuration choices If the dependencies of a given feature are not satisfied the tool prohibits select ing it The user has to find out which other features need Concept Linux eCos Visibility conditions 200 3 Explicit defaults Computed expressions 104 2
37. se kernel and eCos is an en tire specialized RTOS for embedded systems We believe that other related domains especially embedded RT such as automotive and avionic control software will share many characteristics with the studied systems Further compar ison to other feature modeling languages shows that both are representative of the space of feature modeling Projects such as Mozilla Firefox or Eclipse IDE are or ganized as plug in architectures with dynamically loadable extensions Such extensions are often listed on marketplace sites rather than managed centrally in a closed feature hi erarchy Variability languages for these systems extension manifests only capture use dependencies and required ver sion ranges but no exclusions or other complex constraints Our study does not apply to such systems We only look at the available artifacts the languages manuals models and mailing lists We have not interviewed developers and users We plan to perform such interviews in future work We only examined one architecture per OS however both architectures represent large and mature por tions of the systems Linux s x86 architecture covers 61 of the total of 10415 features and 67 of the total of 8M SLOC the eCos s i386PC covers 44 of the total of 2859 features and 33 of the total of 0 9M SLOC An internal threat is that our statistics are incorrect To reduce this risk we instrumented the native tools to gather the statis
38. ser in the UI De rived features are used to simplify constraints or define implementation features used in the build system e Constraint language Both languages support arbi trary Boolean constraints Kconfig supports also equal ity tests on integer and string values CDL adds vari ous arithmetic and string operations and a few built in functions The models reveal that arithmetic opera tions are likely needed for embedded software as in eCos whereas string operations could be dealt with in the build system outside of the models as in Linux We observed limitations in the configurators for Kconfig and CDL see Fig 2 for the UI of the eCos tool Particularly the Kconfig configurator lacks reasoning procedures to sup port choice propagation To mitigate this the Kconfig lan guage includes an imperative construct for specifying choice propagation which delegates this task to model developers however both the Kconfig user manual and many devel oper comments in the Linux revision history 11 acknowl edge that using the construct is very error prone The eCos configurator is far more intelligent thanks to an inference engine however the engine offers incomplete reasoning and may propose configuration choices that would not be desir able for the user Interestingly both configurators follow a reconfiguration paradigm any configuration task starts with an initial possibly default configuration However scalable reasoning to
39. tics rather than building our own parsers We thor oughly tested our infrastructure using synthetic test cases and cross checked overlapping statistics We tested our for mal semantics specification against the native configurators and cross reviewed the specifications We used the Boolean abstraction of the semantics to translate both models into Boolean formulas and run a SAT solver on them to find dead always inactive features We found 114 dead features in Linux and 28 in eCos We manually confirmed that all of them are indeed dead either because they depended on fea tures from another architecture or they were intentionally deactivated 7 RELATED WORK Semantics of academic variability modeling languages were studied before 17 5 We focus on languages originating from practice A survey on the use of feature models 8 identified only five papers reporting practical experience References 14 16 17 in 8 are experiences from researchers applying feature modeling to sample problems from indus try References 31 37 therein are self reported industry ex periences the first on using feature modeling tool prototype on automotive control software and the second one on man aging avionic control software with feature models but with few details on the languages and tools used A notable ex ception is the report on the industrial use of Dopler for vari ability modeling and product derivation 7 Sadly neither the models nor data
40. ult values for features possibly depending on other features computed defaults they can be overrid den by the user 3 visibility conditions control the visibility of features in the configurator UI Features whose visibility condition is false are not shown or otherwise disabled for user input Computed defaults and visibility conditions have not been widely considered in feature modeling Unlike configu ration constraints defaults and visibility conditions have no direct impact on the configuration semantics However they interact with each other in complex ways that may impact configuration semantics We will explain this soon A configuration constraint is expressed using select in Kconfig and requires or active_if in CDL For instance the constraint Support ZLIB 2ZLIB Inflate of Fig 1 is expressed as a select in line k 35 and as a requires in c 34 Both select and requires take a condition say p and denote the configuration constraint f p where f is the feature in which they are defined While p can only be a feature iden tifier for select Kconfig it can be an arbitrary Boolean expression for requires CDL possibly accessing multiple features via logical arithmetic and string operators CDL s active_if has the same syntactic form and config uration semantics as requires except that it also enforces a visibility condition While the visibility of a child in both Kconfig and CDL is inherited from its parent in the c
41. velopers use them to manage the addition and evolution of features and their dependencies Product line users derive concrete products from variability models A range of automated tools support these activities analyz ers verify model consistency or detect dead features 1 and Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page To copy otherwise to republish to post on servers or to redistribute to lists requires prior specific permission and or a fee ASE 10 September 20 24 2010 Antwerp Belgium Copyright 2010 ACM 978 1 4503 0116 9 10 09 10 00 Andrzej Wasowski IT University of Copenhagen wasowski itu dk Krzysztof Czarnecki University of Waterloo kczarnec gsd uwaterloo ca Misc Filesystems Support ZLIB ZLIB Inflate o JFFS2 CRC A MTD Journalling Flash File System 0 lt Debug Level lt 2 Debug Level int Compress Data Support ZLIB Default Compression None Priority Size Figure 1 Feature model interpretation of JFFS2 graphical configuration tools configurators for short sup port intelligent choice propagation and model completion 6 23 9 Practical significance of variability m
42. velopment of OMG s CVL standard 2 THE SYSTEMS The implementation of the Kconfig language is distributed together with the Linux kernel source Kconfig has been used to specify build time dependencies of the kernel since 2002 The Linux configurator reads the Kconfig model and allows the user to select features in a graphical UI closely resembling the CDL configurator of Fig 2 It outputs a set of feature value mappings that are referenced in Makefiles and in the source code as preprocessor directives The studied version 2 6 32 of the Linux kernel supports 23 hardware architectures The code base spans 1880 direc tories and 701 Kconfig files Kconfig models are distributed over multiple files organized according to the source code hi erarchy Each Kconfig specification is placed alongside the related code An architecture specific Kconfig file is used as a starting point for the specification a simple inclusion mechanism is used to include other files CDL was designed for the purposes of the configurable em bedded operating system eCos ecos sourceware org Unlike Kconfig which is a standalone language CDL is embed ded in Tcl a dynamic and highly extensible scripting lan guage CDL inherits characteristics from Tcl such as syn tactic nesting of blocks dynamic typing of values and a rich set of operators in constraint expressions CDL s configura tor Fig 2 offers an inference engine for conflict resolution The stu
43. y The former is given by the syntactic nesting of features such as the nesting of con figs in menus or choices in Kconfig or options and compo nents in other components and packages in CDL The config uration hierarchy is shown to the user in a configurator cf Fig 2 In the notation of Fig 1 the diagrammatic tree rep resents both the intended configuration hierarchy and the syntactic nesting In Kconfig and CDL the configuration hierarchy can deviate from the syntactic one In Kconfig syntactic nesting within menuconfigs and choices will be reflected in the configuration hierarchy however con figs can also appear as children of other configs even though k1 menuconfig MISC_FILESYSTEMS k 2 bool Miscellaneous filesystems k4 if MISC_FILESYSTEMS k 6 config JFFS2_FS k 7 tristate Journalling Flash File System if MTD k 8 select CRC32 if MTD k 10 config JFFS2_FS_DEBUG int JFFS2 Debug level quiet 2 noisy depends on JFFS2_FS default 0 range 0 2 help Debug verbosity of config JFFS2_FS_WRITEBUFFER bool depends on JFFS2_FS default HAS _IOMEM k 23 k 24 k 25 k 26 k 27 k 28 k 29 k 30 k 31 k 32 k 33 k 34 k 35 k 36 k 37 k 38 k 39 k 40 k 41 k 42 k 43 k 44 k 45 k 46 k 47 k 48 k 49 config JFFS2_COMPRESS bool Advanced compression options for JFFS2 depends on JFFS2_FS config JFFS2_ZLIB bool Compress w zlib if JFFS2_ COMPRESS depends on JFFS2_FS select ZLIB_INFLATE d
Download Pdf Manuals
Related Search