Merge tag 'for_linus' of git://git.kernel.org/pub/scm/linux/kernel/git/mst/vhost
[linux-2.6-microblaze.git] / Documentation / kbuild / kconfig-language.rst
1 ================
2 Kconfig Language
3 ================
4
5 Introduction
6 ------------
7
8 The configuration database is a collection of configuration options
9 organized in a tree structure::
10
11         +- Code maturity level options
12         |  +- Prompt for development and/or incomplete code/drivers
13         +- General setup
14         |  +- Networking support
15         |  +- System V IPC
16         |  +- BSD Process Accounting
17         |  +- Sysctl support
18         +- Loadable module support
19         |  +- Enable loadable module support
20         |     +- Set version information on all module symbols
21         |     +- Kernel module loader
22         +- ...
23
24 Every entry has its own dependencies. These dependencies are used
25 to determine the visibility of an entry. Any child entry is only
26 visible if its parent entry is also visible.
27
28 Menu entries
29 ------------
30
31 Most entries define a config option; all other entries help to organize
32 them. A single configuration option is defined like this::
33
34   config MODVERSIONS
35         bool "Set version information on all module symbols"
36         depends on MODULES
37         help
38           Usually, modules have to be recompiled whenever you switch to a new
39           kernel.  ...
40
41 Every line starts with a key word and can be followed by multiple
42 arguments.  "config" starts a new config entry. The following lines
43 define attributes for this config option. Attributes can be the type of
44 the config option, input prompt, dependencies, help text and default
45 values. A config option can be defined multiple times with the same
46 name, but every definition can have only a single input prompt and the
47 type must not conflict.
48
49 Menu attributes
50 ---------------
51
52 A menu entry can have a number of attributes. Not all of them are
53 applicable everywhere (see syntax).
54
55 - type definition: "bool"/"tristate"/"string"/"hex"/"int"
56
57   Every config option must have a type. There are only two basic types:
58   tristate and string; the other types are based on these two. The type
59   definition optionally accepts an input prompt, so these two examples
60   are equivalent::
61
62         bool "Networking support"
63
64   and::
65
66         bool
67         prompt "Networking support"
68
69 - input prompt: "prompt" <prompt> ["if" <expr>]
70
71   Every menu entry can have at most one prompt, which is used to display
72   to the user. Optionally dependencies only for this prompt can be added
73   with "if".
74
75 - default value: "default" <expr> ["if" <expr>]
76
77   A config option can have any number of default values. If multiple
78   default values are visible, only the first defined one is active.
79   Default values are not limited to the menu entry where they are
80   defined. This means the default can be defined somewhere else or be
81   overridden by an earlier definition.
82   The default value is only assigned to the config symbol if no other
83   value was set by the user (via the input prompt above). If an input
84   prompt is visible the default value is presented to the user and can
85   be overridden by him.
86   Optionally, dependencies only for this default value can be added with
87   "if".
88
89  The default value deliberately defaults to 'n' in order to avoid bloating the
90  build. With few exceptions, new config options should not change this. The
91  intent is for "make oldconfig" to add as little as possible to the config from
92  release to release.
93
94  Note:
95         Things that merit "default y/m" include:
96
97         a) A new Kconfig option for something that used to always be built
98            should be "default y".
99
100         b) A new gatekeeping Kconfig option that hides/shows other Kconfig
101            options (but does not generate any code of its own), should be
102            "default y" so people will see those other options.
103
104         c) Sub-driver behavior or similar options for a driver that is
105            "default n". This allows you to provide sane defaults.
106
107         d) Hardware or infrastructure that everybody expects, such as CONFIG_NET
108            or CONFIG_BLOCK. These are rare exceptions.
109
110 - type definition + default value::
111
112         "def_bool"/"def_tristate" <expr> ["if" <expr>]
113
114   This is a shorthand notation for a type definition plus a value.
115   Optionally dependencies for this default value can be added with "if".
116
117 - dependencies: "depends on" <expr>
118
119   This defines a dependency for this menu entry. If multiple
120   dependencies are defined, they are connected with '&&'. Dependencies
121   are applied to all other options within this menu entry (which also
122   accept an "if" expression), so these two examples are equivalent::
123
124         bool "foo" if BAR
125         default y if BAR
126
127   and::
128
129         depends on BAR
130         bool "foo"
131         default y
132
133 - reverse dependencies: "select" <symbol> ["if" <expr>]
134
135   While normal dependencies reduce the upper limit of a symbol (see
136   below), reverse dependencies can be used to force a lower limit of
137   another symbol. The value of the current menu symbol is used as the
138   minimal value <symbol> can be set to. If <symbol> is selected multiple
139   times, the limit is set to the largest selection.
140   Reverse dependencies can only be used with boolean or tristate
141   symbols.
142
143   Note:
144         select should be used with care. select will force
145         a symbol to a value without visiting the dependencies.
146         By abusing select you are able to select a symbol FOO even
147         if FOO depends on BAR that is not set.
148         In general use select only for non-visible symbols
149         (no prompts anywhere) and for symbols with no dependencies.
150         That will limit the usefulness but on the other hand avoid
151         the illegal configurations all over.
152
153 - weak reverse dependencies: "imply" <symbol> ["if" <expr>]
154
155   This is similar to "select" as it enforces a lower limit on another
156   symbol except that the "implied" symbol's value may still be set to n
157   from a direct dependency or with a visible prompt.
158
159   Given the following example::
160
161     config FOO
162         tristate "foo"
163         imply BAZ
164
165     config BAZ
166         tristate "baz"
167         depends on BAR
168
169   The following values are possible:
170
171         ===             ===             =============   ==============
172         FOO             BAR             BAZ's default   choice for BAZ
173         ===             ===             =============   ==============
174         n               y               n               N/m/y
175         m               y               m               M/y/n
176         y               y               y               Y/m/n
177         n               m               n               N/m
178         m               m               m               M/n
179         y               m               n               M/n
180         y               n               *               N
181         ===             ===             =============   ==============
182
183   This is useful e.g. with multiple drivers that want to indicate their
184   ability to hook into a secondary subsystem while allowing the user to
185   configure that subsystem out without also having to unset these drivers.
186
187   Note: If the combination of FOO=y and BAR=m causes a link error,
188   you can guard the function call with IS_REACHABLE()::
189
190         foo_init()
191         {
192                 if (IS_REACHABLE(CONFIG_BAZ))
193                         baz_register(&foo);
194                 ...
195         }
196
197   Note: If the feature provided by BAZ is highly desirable for FOO,
198   FOO should imply not only BAZ, but also its dependency BAR::
199
200     config FOO
201         tristate "foo"
202         imply BAR
203         imply BAZ
204
205 - limiting menu display: "visible if" <expr>
206
207   This attribute is only applicable to menu blocks, if the condition is
208   false, the menu block is not displayed to the user (the symbols
209   contained there can still be selected by other symbols, though). It is
210   similar to a conditional "prompt" attribute for individual menu
211   entries. Default value of "visible" is true.
212
213 - numerical ranges: "range" <symbol> <symbol> ["if" <expr>]
214
215   This allows to limit the range of possible input values for int
216   and hex symbols. The user can only input a value which is larger than
217   or equal to the first symbol and smaller than or equal to the second
218   symbol.
219
220 - help text: "help"
221
222   This defines a help text. The end of the help text is determined by
223   the indentation level, this means it ends at the first line which has
224   a smaller indentation than the first line of the help text.
225
226 - misc options: "option" <symbol>[=<value>]
227
228   Various less common options can be defined via this option syntax,
229   which can modify the behaviour of the menu entry and its config
230   symbol. These options are currently possible:
231
232   - "defconfig_list"
233     This declares a list of default entries which can be used when
234     looking for the default configuration (which is used when the main
235     .config doesn't exists yet.)
236
237   - "modules"
238     This declares the symbol to be used as the MODULES symbol, which
239     enables the third modular state for all config symbols.
240     At most one symbol may have the "modules" option set.
241
242   - "allnoconfig_y"
243     This declares the symbol as one that should have the value y when
244     using "allnoconfig". Used for symbols that hide other symbols.
245
246 Menu dependencies
247 -----------------
248
249 Dependencies define the visibility of a menu entry and can also reduce
250 the input range of tristate symbols. The tristate logic used in the
251 expressions uses one more state than normal boolean logic to express the
252 module state. Dependency expressions have the following syntax::
253
254   <expr> ::= <symbol>                           (1)
255            <symbol> '=' <symbol>                (2)
256            <symbol> '!=' <symbol>               (3)
257            <symbol1> '<' <symbol2>              (4)
258            <symbol1> '>' <symbol2>              (4)
259            <symbol1> '<=' <symbol2>             (4)
260            <symbol1> '>=' <symbol2>             (4)
261            '(' <expr> ')'                       (5)
262            '!' <expr>                           (6)
263            <expr> '&&' <expr>                   (7)
264            <expr> '||' <expr>                   (8)
265
266 Expressions are listed in decreasing order of precedence.
267
268 (1) Convert the symbol into an expression. Boolean and tristate symbols
269     are simply converted into the respective expression values. All
270     other symbol types result in 'n'.
271 (2) If the values of both symbols are equal, it returns 'y',
272     otherwise 'n'.
273 (3) If the values of both symbols are equal, it returns 'n',
274     otherwise 'y'.
275 (4) If value of <symbol1> is respectively lower, greater, lower-or-equal,
276     or greater-or-equal than value of <symbol2>, it returns 'y',
277     otherwise 'n'.
278 (5) Returns the value of the expression. Used to override precedence.
279 (6) Returns the result of (2-/expr/).
280 (7) Returns the result of min(/expr/, /expr/).
281 (8) Returns the result of max(/expr/, /expr/).
282
283 An expression can have a value of 'n', 'm' or 'y' (or 0, 1, 2
284 respectively for calculations). A menu entry becomes visible when its
285 expression evaluates to 'm' or 'y'.
286
287 There are two types of symbols: constant and non-constant symbols.
288 Non-constant symbols are the most common ones and are defined with the
289 'config' statement. Non-constant symbols consist entirely of alphanumeric
290 characters or underscores.
291 Constant symbols are only part of expressions. Constant symbols are
292 always surrounded by single or double quotes. Within the quote, any
293 other character is allowed and the quotes can be escaped using '\'.
294
295 Menu structure
296 --------------
297
298 The position of a menu entry in the tree is determined in two ways. First
299 it can be specified explicitly::
300
301   menu "Network device support"
302         depends on NET
303
304   config NETDEVICES
305         ...
306
307   endmenu
308
309 All entries within the "menu" ... "endmenu" block become a submenu of
310 "Network device support". All subentries inherit the dependencies from
311 the menu entry, e.g. this means the dependency "NET" is added to the
312 dependency list of the config option NETDEVICES.
313
314 The other way to generate the menu structure is done by analyzing the
315 dependencies. If a menu entry somehow depends on the previous entry, it
316 can be made a submenu of it. First, the previous (parent) symbol must
317 be part of the dependency list and then one of these two conditions
318 must be true:
319
320 - the child entry must become invisible, if the parent is set to 'n'
321 - the child entry must only be visible, if the parent is visible::
322
323     config MODULES
324         bool "Enable loadable module support"
325
326     config MODVERSIONS
327         bool "Set version information on all module symbols"
328         depends on MODULES
329
330     comment "module support disabled"
331         depends on !MODULES
332
333 MODVERSIONS directly depends on MODULES, this means it's only visible if
334 MODULES is different from 'n'. The comment on the other hand is only
335 visible when MODULES is set to 'n'.
336
337
338 Kconfig syntax
339 --------------
340
341 The configuration file describes a series of menu entries, where every
342 line starts with a keyword (except help texts). The following keywords
343 end a menu entry:
344
345 - config
346 - menuconfig
347 - choice/endchoice
348 - comment
349 - menu/endmenu
350 - if/endif
351 - source
352
353 The first five also start the definition of a menu entry.
354
355 config::
356
357         "config" <symbol>
358         <config options>
359
360 This defines a config symbol <symbol> and accepts any of above
361 attributes as options.
362
363 menuconfig::
364
365         "menuconfig" <symbol>
366         <config options>
367
368 This is similar to the simple config entry above, but it also gives a
369 hint to front ends, that all suboptions should be displayed as a
370 separate list of options. To make sure all the suboptions will really
371 show up under the menuconfig entry and not outside of it, every item
372 from the <config options> list must depend on the menuconfig symbol.
373 In practice, this is achieved by using one of the next two constructs::
374
375   (1):
376   menuconfig M
377   if M
378       config C1
379       config C2
380   endif
381
382   (2):
383   menuconfig M
384   config C1
385       depends on M
386   config C2
387       depends on M
388
389 In the following examples (3) and (4), C1 and C2 still have the M
390 dependency, but will not appear under menuconfig M anymore, because
391 of C0, which doesn't depend on M::
392
393   (3):
394   menuconfig M
395       config C0
396   if M
397       config C1
398       config C2
399   endif
400
401   (4):
402   menuconfig M
403   config C0
404   config C1
405       depends on M
406   config C2
407       depends on M
408
409 choices::
410
411         "choice" [symbol]
412         <choice options>
413         <choice block>
414         "endchoice"
415
416 This defines a choice group and accepts any of the above attributes as
417 options. A choice can only be of type bool or tristate.  If no type is
418 specified for a choice, its type will be determined by the type of
419 the first choice element in the group or remain unknown if none of the
420 choice elements have a type specified, as well.
421
422 While a boolean choice only allows a single config entry to be
423 selected, a tristate choice also allows any number of config entries
424 to be set to 'm'. This can be used if multiple drivers for a single
425 hardware exists and only a single driver can be compiled/loaded into
426 the kernel, but all drivers can be compiled as modules.
427
428 A choice accepts another option "optional", which allows to set the
429 choice to 'n' and no entry needs to be selected.
430 If no [symbol] is associated with a choice, then you can not have multiple
431 definitions of that choice. If a [symbol] is associated to the choice,
432 then you may define the same choice (i.e. with the same entries) in another
433 place.
434
435 comment::
436
437         "comment" <prompt>
438         <comment options>
439
440 This defines a comment which is displayed to the user during the
441 configuration process and is also echoed to the output files. The only
442 possible options are dependencies.
443
444 menu::
445
446         "menu" <prompt>
447         <menu options>
448         <menu block>
449         "endmenu"
450
451 This defines a menu block, see "Menu structure" above for more
452 information. The only possible options are dependencies and "visible"
453 attributes.
454
455 if::
456
457         "if" <expr>
458         <if block>
459         "endif"
460
461 This defines an if block. The dependency expression <expr> is appended
462 to all enclosed menu entries.
463
464 source::
465
466         "source" <prompt>
467
468 This reads the specified configuration file. This file is always parsed.
469
470 mainmenu::
471
472         "mainmenu" <prompt>
473
474 This sets the config program's title bar if the config program chooses
475 to use it. It should be placed at the top of the configuration, before any
476 other statement.
477
478 '#' Kconfig source file comment:
479
480 An unquoted '#' character anywhere in a source file line indicates
481 the beginning of a source file comment.  The remainder of that line
482 is a comment.
483
484
485 Kconfig hints
486 -------------
487 This is a collection of Kconfig tips, most of which aren't obvious at
488 first glance and most of which have become idioms in several Kconfig
489 files.
490
491 Adding common features and make the usage configurable
492 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
493 It is a common idiom to implement a feature/functionality that are
494 relevant for some architectures but not all.
495 The recommended way to do so is to use a config variable named HAVE_*
496 that is defined in a common Kconfig file and selected by the relevant
497 architectures.
498 An example is the generic IOMAP functionality.
499
500 We would in lib/Kconfig see::
501
502   # Generic IOMAP is used to ...
503   config HAVE_GENERIC_IOMAP
504
505   config GENERIC_IOMAP
506         depends on HAVE_GENERIC_IOMAP && FOO
507
508 And in lib/Makefile we would see::
509
510         obj-$(CONFIG_GENERIC_IOMAP) += iomap.o
511
512 For each architecture using the generic IOMAP functionality we would see::
513
514   config X86
515         select ...
516         select HAVE_GENERIC_IOMAP
517         select ...
518
519 Note: we use the existing config option and avoid creating a new
520 config variable to select HAVE_GENERIC_IOMAP.
521
522 Note: the use of the internal config variable HAVE_GENERIC_IOMAP, it is
523 introduced to overcome the limitation of select which will force a
524 config option to 'y' no matter the dependencies.
525 The dependencies are moved to the symbol GENERIC_IOMAP and we avoid the
526 situation where select forces a symbol equals to 'y'.
527
528 Adding features that need compiler support
529 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
530
531 There are several features that need compiler support. The recommended way
532 to describe the dependency on the compiler feature is to use "depends on"
533 followed by a test macro::
534
535   config STACKPROTECTOR
536         bool "Stack Protector buffer overflow detection"
537         depends on $(cc-option,-fstack-protector)
538         ...
539
540 If you need to expose a compiler capability to makefiles and/or C source files,
541 `CC_HAS_` is the recommended prefix for the config option::
542
543   config CC_HAS_ASM_GOTO
544         def_bool $(success,$(srctree)/scripts/gcc-goto.sh $(CC))
545
546 Build as module only
547 ~~~~~~~~~~~~~~~~~~~~
548 To restrict a component build to module-only, qualify its config symbol
549 with "depends on m".  E.g.::
550
551   config FOO
552         depends on BAR && m
553
554 limits FOO to module (=m) or disabled (=n).
555
556 Compile-testing
557 ~~~~~~~~~~~~~~~
558 If a config symbol has a dependency, but the code controlled by the config
559 symbol can still be compiled if the dependency is not met, it is encouraged to
560 increase build coverage by adding an "|| COMPILE_TEST" clause to the
561 dependency. This is especially useful for drivers for more exotic hardware, as
562 it allows continuous-integration systems to compile-test the code on a more
563 common system, and detect bugs that way.
564 Note that compile-tested code should avoid crashing when run on a system where
565 the dependency is not met.
566
567 Architecture and platform dependencies
568 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
569 Due to the presence of stubs, most drivers can now be compiled on most
570 architectures. However, this does not mean it makes sense to have all drivers
571 available everywhere, as the actual hardware may only exist on specific
572 architectures and platforms. This is especially true for on-SoC IP cores,
573 which may be limited to a specific vendor or SoC family.
574
575 To prevent asking the user about drivers that cannot be used on the system(s)
576 the user is compiling a kernel for, and if it makes sense, config symbols
577 controlling the compilation of a driver should contain proper dependencies,
578 limiting the visibility of the symbol to (a superset of) the platform(s) the
579 driver can be used on. The dependency can be an architecture (e.g. ARM) or
580 platform (e.g. ARCH_OMAP4) dependency. This makes life simpler not only for
581 distro config owners, but also for every single developer or user who
582 configures a kernel.
583
584 Such a dependency can be relaxed by combining it with the compile-testing rule
585 above, leading to:
586
587   config FOO
588         bool "Support for foo hardware"
589         depends on ARCH_FOO_VENDOR || COMPILE_TEST
590
591 Kconfig recursive dependency limitations
592 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
593
594 If you've hit the Kconfig error: "recursive dependency detected" you've run
595 into a recursive dependency issue with Kconfig, a recursive dependency can be
596 summarized as a circular dependency. The kconfig tools need to ensure that
597 Kconfig files comply with specified configuration requirements. In order to do
598 that kconfig must determine the values that are possible for all Kconfig
599 symbols, this is currently not possible if there is a circular relation
600 between two or more Kconfig symbols. For more details refer to the "Simple
601 Kconfig recursive issue" subsection below. Kconfig does not do recursive
602 dependency resolution; this has a few implications for Kconfig file writers.
603 We'll first explain why this issues exists and then provide an example
604 technical limitation which this brings upon Kconfig developers. Eager
605 developers wishing to try to address this limitation should read the next
606 subsections.
607
608 Simple Kconfig recursive issue
609 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
610
611 Read: Documentation/kbuild/Kconfig.recursion-issue-01
612
613 Test with::
614
615   make KBUILD_KCONFIG=Documentation/kbuild/Kconfig.recursion-issue-01 allnoconfig
616
617 Cumulative Kconfig recursive issue
618 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
619
620 Read: Documentation/kbuild/Kconfig.recursion-issue-02
621
622 Test with::
623
624   make KBUILD_KCONFIG=Documentation/kbuild/Kconfig.recursion-issue-02 allnoconfig
625
626 Practical solutions to kconfig recursive issue
627 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
628
629 Developers who run into the recursive Kconfig issue have two options
630 at their disposal. We document them below and also provide a list of
631 historical issues resolved through these different solutions.
632
633   a) Remove any superfluous "select FOO" or "depends on FOO"
634   b) Match dependency semantics:
635
636         b1) Swap all "select FOO" to "depends on FOO" or,
637
638         b2) Swap all "depends on FOO" to "select FOO"
639
640 The resolution to a) can be tested with the sample Kconfig file
641 Documentation/kbuild/Kconfig.recursion-issue-01 through the removal
642 of the "select CORE" from CORE_BELL_A_ADVANCED as that is implicit already
643 since CORE_BELL_A depends on CORE. At times it may not be possible to remove
644 some dependency criteria, for such cases you can work with solution b).
645
646 The two different resolutions for b) can be tested in the sample Kconfig file
647 Documentation/kbuild/Kconfig.recursion-issue-02.
648
649 Below is a list of examples of prior fixes for these types of recursive issues;
650 all errors appear to involve one or more "select" statements and one or more
651 "depends on".
652
653 ============    ===================================
654 commit          fix
655 ============    ===================================
656 06b718c01208    select A -> depends on A
657 c22eacfe82f9    depends on A -> depends on B
658 6a91e854442c    select A -> depends on A
659 118c565a8f2e    select A -> select B
660 f004e5594705    select A -> depends on A
661 c7861f37b4c6    depends on A -> (null)
662 80c69915e5fb    select A -> (null)              (1)
663 c2218e26c0d0    select A -> depends on A        (1)
664 d6ae99d04e1c    select A -> depends on A
665 95ca19cf8cbf    select A -> depends on A
666 8f057d7bca54    depends on A -> (null)
667 8f057d7bca54    depends on A -> select A
668 a0701f04846e    select A -> depends on A
669 0c8b92f7f259    depends on A -> (null)
670 e4e9e0540928    select A -> depends on A        (2)
671 7453ea886e87    depends on A > (null)           (1)
672 7b1fff7e4fdf    select A -> depends on A
673 86c747d2a4f0    select A -> depends on A
674 d9f9ab51e55e    select A -> depends on A
675 0c51a4d8abd6    depends on A -> select A        (3)
676 e98062ed6dc4    select A -> depends on A        (3)
677 91e5d284a7f1    select A -> (null)
678 ============    ===================================
679
680 (1) Partial (or no) quote of error.
681 (2) That seems to be the gist of that fix.
682 (3) Same error.
683
684 Future kconfig work
685 ~~~~~~~~~~~~~~~~~~~
686
687 Work on kconfig is welcomed on both areas of clarifying semantics and on
688 evaluating the use of a full SAT solver for it. A full SAT solver can be
689 desirable to enable more complex dependency mappings and / or queries,
690 for instance on possible use case for a SAT solver could be that of handling
691 the current known recursive dependency issues. It is not known if this would
692 address such issues but such evaluation is desirable. If support for a full SAT
693 solver proves too complex or that it cannot address recursive dependency issues
694 Kconfig should have at least clear and well defined semantics which also
695 addresses and documents limitations or requirements such as the ones dealing
696 with recursive dependencies.
697
698 Further work on both of these areas is welcomed on Kconfig. We elaborate
699 on both of these in the next two subsections.
700
701 Semantics of Kconfig
702 ~~~~~~~~~~~~~~~~~~~~
703
704 The use of Kconfig is broad, Linux is now only one of Kconfig's users:
705 one study has completed a broad analysis of Kconfig use in 12 projects [0]_.
706 Despite its widespread use, and although this document does a reasonable job
707 in documenting basic Kconfig syntax a more precise definition of Kconfig
708 semantics is welcomed. One project deduced Kconfig semantics through
709 the use of the xconfig configurator [1]_. Work should be done to confirm if
710 the deduced semantics matches our intended Kconfig design goals.
711
712 Having well defined semantics can be useful for tools for practical
713 evaluation of dependencies, for instance one such case was work to
714 express in boolean abstraction of the inferred semantics of Kconfig to
715 translate Kconfig logic into boolean formulas and run a SAT solver on this to
716 find dead code / features (always inactive), 114 dead features were found in
717 Linux using this methodology [1]_ (Section 8: Threats to validity).
718
719 Confirming this could prove useful as Kconfig stands as one of the leading
720 industrial variability modeling languages [1]_ [2]_. Its study would help
721 evaluate practical uses of such languages, their use was only theoretical
722 and real world requirements were not well understood. As it stands though
723 only reverse engineering techniques have been used to deduce semantics from
724 variability modeling languages such as Kconfig [3]_.
725
726 .. [0] https://www.eng.uwaterloo.ca/~shshe/kconfig_semantics.pdf
727 .. [1] https://gsd.uwaterloo.ca/sites/default/files/vm-2013-berger.pdf
728 .. [2] https://gsd.uwaterloo.ca/sites/default/files/ase241-berger_0.pdf
729 .. [3] https://gsd.uwaterloo.ca/sites/default/files/icse2011.pdf
730
731 Full SAT solver for Kconfig
732 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
733
734 Although SAT solvers [4]_ haven't yet been used by Kconfig directly, as noted
735 in the previous subsection, work has been done however to express in boolean
736 abstraction the inferred semantics of Kconfig to translate Kconfig logic into
737 boolean formulas and run a SAT solver on it [5]_. Another known related project
738 is CADOS [6]_ (former VAMOS [7]_) and the tools, mainly undertaker [8]_, which
739 has been introduced first with [9]_.  The basic concept of undertaker is to
740 extract variability models from Kconfig and put them together with a
741 propositional formula extracted from CPP #ifdefs and build-rules into a SAT
742 solver in order to find dead code, dead files, and dead symbols. If using a SAT
743 solver is desirable on Kconfig one approach would be to evaluate repurposing
744 such efforts somehow on Kconfig. There is enough interest from mentors of
745 existing projects to not only help advise how to integrate this work upstream
746 but also help maintain it long term. Interested developers should visit:
747
748 https://kernelnewbies.org/KernelProjects/kconfig-sat
749
750 .. [4] https://www.cs.cornell.edu/~sabhar/chapters/SATSolvers-KR-Handbook.pdf
751 .. [5] https://gsd.uwaterloo.ca/sites/default/files/vm-2013-berger.pdf
752 .. [6] https://cados.cs.fau.de
753 .. [7] https://vamos.cs.fau.de
754 .. [8] https://undertaker.cs.fau.de
755 .. [9] https://www4.cs.fau.de/Publications/2011/tartler_11_eurosys.pdf