Deep Dive

Recently, I was working on a project on Nvidia's Jetson Nano platform [1]. The project required me to build certain kernel drivers. Of course, I looked through the requisite driver makefiles to determine which CONFIG options needed to be enabled. However, when I ran make menuconfig, I noticed that, while I could search through the kernel for the particular CONFIG option, I couldn't actually navigate to the menu to enable it. Furthermore, when I tried to modify tegra_defconfig, which is the standard kernel configuration for Nvidia platforms, to include the required CONFIG option, the kernel simply ignored it. Unfortunately, the kernel gave no indication as to why the specific CONFIG option was ignored. While I ultimately determined that there was another CONFIG option that needed to be enabled (which should have been handled by menuconfig if the particular Nvidia CONFIG options were detected), I wanted to dig deeper to understand how Kconfig works and share my findings. While this article does not go into substantial detail on some of the requisite topics (such as grammars, Flex [2], and Bison [3]), this article strives to provide enough detail to provide an understanding of how Kconfig works.

Now, most people will not use the Jetson Nano as their daily driver. However, even if you are using an x86_64 platform, such as one that is based on the Intel or AMD processors that are present in most modern-day laptops and desktops, it's important to get comfortable navigating the kernel configuration. For example, there may be a device that you wish to connect to your Linux PC that does not function. Specifically, it may be not automatically detected by the kernel because support for the device (via a device driver) is not enabled. Enabling the driver is done through an invocation to make menuconfig, which results in the image shown in Figure 1, locating the appropriate configuration option and enabling it; under the hood, a specific kernel CONFIG option is enabled. However, enabling that particular option may not be straightforward. For example, the driver configuration option might be buried under another higher level configuration option that needs to be enabled first.

Figure 1: Configuring the kernel through a simple graphical interface.

Specifically, let's say you'd like to connect a Sony PS4 controller to a tablet or convertible laptop, on which you've installed Linux. When you plug in the controller in an available USB port on your tablet, you notice that it isn't automatically detected as you'd hoped. After running make menuconfig on the downloaded source code of your version of the kernel, you discover that the option to enable the PS4 (under Device Drivers | HID support | Special HID drivers) is not checked off, as shown in Figure 2.

Figure 2: Support for the Sony PS4 controller is not enabled.

You check off that particular option, save the configuration, rebuild your kernel, install it on your system, and reboot. After rebooting, you discover that the controller has been detected by your system, and you can use it to play the desired video game!

Continuing with the example of using a tablet, let's say you are having an issue where the display of the tablet does not automatically rotate when you are switching from portrait to landscape (or vice versa). One debugging technique would be to confirm that the Intel ISH HID configuration option is enabled in the kernel. Recent Intel processors have a built-in sensor hub that allows them to detect and control certain aspects of a tablet, such as backlight and auto rotation. If you are having issues where the display orientation is not rotating as you are rotating the tablet, one of the first things to do would be to confirm that the INTEL_ISH_HID feature is enabled in the kernel. This can be done by running make menuconfig, enter the forward slash (/) key to search through all of the configs, and typing INTEL_ISH. This will bring up the message shown in Figure 3.

Figure 3: Searching for INTEL_ISH in kernel config.

If =n is shown in the search message (instead of =y), this indicates that support for the Intel sensor hub isn't compiled in the kernel. The first step to resolve the issue would be to enable this feature, recompile the kernel, install it, and reboot your system.

Kconfig

The system for configuring the Linux kernel is generally referred to as the Kconfig system. Kconfig is a configuration database that ultimately defines which modules and features are built in the final kernel. Kconfig defines its own language (and grammar) that supports configuration management, including dependencies across options.

Users configure settings for the build system through a number of optional interfaces called targets, which are defined in the appropriate makefiles. The menuconfig option described in the previous section is a Kconfig target that allows users to enter information in a rudimentary menu system. Other targets support other input methods (see Table 1).

The configuration database begins with the contents of the Kconfig file at the source root, then additional settings configured through the Kconfig target are added to the mix (you'll see how additional directories are traversed later). The configuration information is ultimately used to create a .config file, which is then used to enable and disable certain kernel configurations. These configuration options also define whether certain components, such as drivers, are built as part of the final kernel binary or as separate "kernel modules," which can be loaded during runtime.

The versatile Kconfig system makes it easy for a user to build a custom Linux kernel with minimal programming and maximum automation, but it is also something of a mystery. I decided to explore what really goes on under the hood when the Kconfig system integrates user-defined configuration settings.

Just a word of warning up front: you might need some knowledge of programming to follow all the nuances of this article, which relies on some standard software debugging tools. But even if you're not a veteran coder, this discussion should offer some insights on the inner workings of the Kconfig system.

Going Deeper

You might encounter situations where an option that you absolutely need to enable might not be visible in the interface. In that case, it is useful to understand the entire Kconfig infrastructure of the kernel in more detail. As mentioned, when you have a clean checkout of the kernel and wish to build it for a specific target platform and application, you must first configure the kernel. Previously, I discussed using the simple menuconfig interface to interactively enable and disable certain options in the kernel, but another method allows for a file to predefine the desired kernel configuration in order to support a more automated workflow. For my Jetson Nano, this is done by invoking make, as shown in Listing 1, which configures the kernel using the tegra_defconfig file under the ARM64 architecture.

01 make ARCH=arm64 tegra_defconfig

When you look at stdout during this process, you will see that the kernel builds the source files under scripts/kconfig/ into an application called conf and runs that application. To understand how conf works, it would be extremely helpful to step through it using gdb (the GNU Debugger). However, that requires a build of conf with debugging enabled. This can be achieved by simply opening the top-level makefile (at the root of the checkout directory) and modifying HOSTCFLAGS to reflect what is shown in Listing 2.

01 HOSTCFLAGS   := -g -Wall -Wmissing-prototypes -Wstrict-prototypes -O0 -fomit-frame-pointer -std=gnu89

Now when you invoke make, as shown in Listing 1, the conf application will be built with debugging symbols and you can step through it to understand how the application works. If you search for the main function under scripts/kconfig, you discover that it is present in conf.c. When you look in conf.c, you can see that it takes action depending on the arguments that are passed into it, as shown in Listing 3.

01 while ((opt = getopt_long(ac, av, "s", long_opts, NULL)) != -1) {
02 ...

In order to properly run gdb against the conf application, you'll need to know the appropriate arguments to pass the application. Although you can navigate through the makefiles to decipher the arguments, there is a simpler way. You can add a simple for loop, as shown in Listing 4, that prints out the arguments passed in to the application.

01 ...
02 for (i = 0; i < ac; i++) {
03         printf("arg %d: %s\n", i, av[i]);
04 }
05 ...

When you add the for loop and rerun the command in Listing 1, you can see that the arguments passed to conf are those shown in Listing 5.

01 arg 0: scripts/kconfig/conf
02 arg 1: --defconfig=arch/arm64/configs/tegra_defconfig
03 arg 2: Kconfig

You can now run gdb, set a breakpoint in main, and pass it the two arguments listed above, as shown in Listing 6.

01 $> gdb scripts/kconfig/conf
02 (gdb) break main
03 (gdb) r --defconfig=arch/arm64/configs/tegra_defconfig Kconfig

When you step through conf with these specific arguments, you see that the first switch block falls through to the defconfig case statement, where the path to the tegra_defconfig file (i.e., arch/arm64/configs/tegra_defconfig) is stored in defconfig_file. Then, you can see that the name variable obtains Kconfig, which is passed to the function conf_parse, which is defined in zconf.y. That is not a typo! zconf.y is a special type of source file that isn't directly compiled but is converted into a C source file by Bison. I'll get into the specifics of how Bison and Flex (and their corresponding files) are used to convert the contents of a Kconfig file later in this article; for now I'll focus on the implementation of conf_parse. The relevant portions are shown in Listing 7.

01 ...
02 zconf_initscan(name);
03
04 sym_init();
05 ...
06 zconfparse();
07 ...
08 for_all_symbols(i, sym) {
09         if (sym_check_deps(sym))
10                 zconfnerrs++;
11 }
12 ...

The first line, zconf_initscan(name) invokes a function defined in zconf.l. This file is similar to zconf.y in that it is converted into a C file to parse text input and take some action. Generally, Flex and Bison go hand-in-hand to parse a text file with a structured format, which Kconfig files have. Specifically, Flex, which generates a lexical scanner, is used to parse and extract tokens in a file such as Kconfig. The input to Flex is a file with a .l extension, which contains a set of rules that define what action should be taken if a token is detected. Bison generates a parser that takes actions when given a certain input; these actions are defined by "production rules" defined in the .y file. Both of these files usually define C functions that provide the crux of the actions to take, which you can see by the fact the zconf_initscan is defined in the zconf.l file, and that conf_parse is defined in zconf.y. zconf_initscan is simply priming the lexical scanner to point it to the Kconfig file, which is passed in via the name argument, for token extraction.

Returning back to conf_parse, you can see that the next relevant line is the call to sym_init(), which is defined in symbol.c. The key function in sym_init is the call to sym_lookup. sym_lookup takes a handful of actions relevant to the symbol table; a "symbol" is a data structure that contains the relevant information associated with a CONFIG option. First, it checks if the symbol being requested is one of three specific symbols: a "yes" symbol, "no" symbol, or "mod" symbol. If so, it simply returns the corresponding hard-coded data structure. If not, it then checks to see if the symbol exists in the symbol table. The symbol table is simply a hash map of all the CONFIG options in the kernel. Specifically, it's an array of the CONFIG options, where the index into the array is a hash of the string corresponding to the option. Additionally, each element in the array consists of a linked list, to mitigate any possible hash collisions. Figure 4 shows the layout of the symbol table.

Figure 4: Structure of symbol_hash hash_map.

To determine if the symbol exists in the symbol table, sym_lookup first calculates the hash of the symbol name, modulo the hash size. Then, it searches through the linked list corresponding to the particular element in the hash table to determine if the symbol exists. If it does, it simply returns it. However, if the symbol doesn't exist, it allocates memory for the symbol data structure, adds it to the beginning of the linked list in the appropriate hash entry, and returns the symbol.

Returning to conf_parse in Listing 7, the next function to be called after sym_init() is zconfparse(). However, when you search for zconfparse in either zconf.y or zconf.l, you will see that it isn't defined. But, if you step into the function, you see that yyparse is called instead. This is because Bison redefines some of the internal functions (such as yyparse) to zconfparse, so they are accessible outside of the Bison namespace. zconfparse is the crux of the Bison parser, where it performs the parsing of the input Kconfig file. I will return to the actual parsing itself later, but for now, assume that zconfparse populates the sym_hash data structure with all of the symbols in all Kconfig files in the kernel source. The next set of statements in Listing 7 are simply confirming that there are no dependency issues in the symbol_hash data structure. If you look at the function sym_check_deps, you will see that conf is navigating through the symbol_hash data structure and ensuring that a few conditions are met; the relevant portions of the function are reproduced in Listing 8.

01 ...
02 if (sym->flags & SYMBOL_CHECK) {
03         sym_check_print_recursive(sym);
04         return sym;
05 }
06 if (sym->flags & SYMBOL_CHECKED)
07         return NULL;
08 if (sym_is_choice_value(sym)) {
09 ...
10 } else if (sym_is_choice(sym)) {
11         sym2 = sym_check_choice_deps(sym);
12 } else {
13         sym->flags |= (SYMBOL_CHECK | SYMBOL_CHECKED);
14         sym2 = sym_check_sym_deps(sym);
15         sym->flags &= ~SYMBOL_CHECK;
16 }

First, sym_check_deps checks to make sure that there are no recursive dependencies. Second, for all "choice value" entries, it confirms that there is a corresponding "choice" block. Similarly, for all "choice" blocks, it ensures there are valid "choice value" entries. Finally, the function does a general check on all symbols in the hash table to confirm that the relevant dependencies have been met.

With that, all of the Kconfig files in the entire kernel source directory have been added to the symbol_hash data structure, along with all of their properties (such as whether it's a choice, or whether it can be compiled as a separate kernel module), and their dependencies have been confirmed. What's interesting is that I only passed in a single Kconfig file to the conf application. How did the program navigate throughout the entire kernel, and then extract and parse all of the Kconfig files? The answer is in the snippet from zconf.y shown in Listing 9.

01 %token <id>T_SOURCE
02 ...
03 %token T_EOL
04 ...
05 %type <string> prompt
06 ...
07 start: mainmenu_stmt stmt_list | no_mainmenu_stmt stmt_list;
08 ...
09 stmt_list:
10           /* empty */
11         | stmt_list common_stmt
12 ...
13 common_stmt:
14           T_EOL
15         | if_stmt
16         | comment_stmt
17         | config_stmt
18         | menuconfig_stmt
19         | source_stmt
20 ;
21 ...
22 source_stmt: T_SOURCE prompt T_EOL
23 {
24         printd(DEBUG_PARSE, "%s:%d:source %s\n", zconf_curname(), zconf_lineno(), $2);
25         zconf_nextfile($2);
26 };

The file that is input to Bison to generate a parser has a very rigid structure. The statements in Listing 9 demonstrate "productions," which are rules for converting one statement into another and what actions should be taken when a particular statement has been detected. All productions begin with start. You can see in Listing 9 that stmt_list is one valid replacement for start. Further below, you can see that common_stmt is a valid replacement for stmt_list. Then, you see that source_stmt is a valid replacement for common_stmt. Finally, T_SOURCE prompt T_EOL is a valid replacement for source_stmt. If you search for T_SOURCE, you can see that it's defined as a token. A token is simply a member of a predefined set of strings that are valid inputs to the program. In this case, T_SOURCE is defined in zconf.gperf. zconf.gperf is a file that is used by the gperf tool to return hashes associated with certain strings. prompt, as seen in Listing 9, is any string that has been detected by the parser. T_EOL is also a token, but it's defined in zconf.l. As mentioned before, zconf.l is a file used by Flex to create a lexical analyzer, which parses strings in a given input file and returns tokens that these strings represent. Regular expressions are mostly used to extract tokens, and you can see how a T_EOL token is extracted from the snippet of zconf.l in Listing 10.

01 [ \t]*#.*\n   |
02 [ \t]*\n      {
03         current_file->lineno++;
04         return T_EOL;
05 }

This snippet simply looks for any number of tabs at the start of a line, followed by any number of characters, followed by a newline, and returns the T_EOL token (along with some internal Flex/Bison bookkeeping). Going back to Listing 9, a source_stmt rule would be replaced by source <string> \n, which is exactly how Kconfig files reference other Kconfig files. As a matter of fact, when the parser created by Bison detects source <string> \n in any input, it actually works backwards to figure out the appropriate production rule that this string matches. In this case, since it matches the source_stmt rule, the parser takes the action specified in the curly braces. It simply invokes zconf_nextfile and passes in <string> to the function, where <string> is the path to another Kconfig file in the kernel. If you look at zconf_nextfile, you can see that it simply updates Flex and Bison to point to the appropriate file for parsing.

While this concludes the different nuances in navigating the kernel to extract all of the available CONFIG options, you need to understand how a specific configuration (such as tegra_defconfig) is applied. If you go back to conf.c, the relevant portion to process a specific defconfig file is given by Listing 11.

01 ...
02 switch (input_mode) {
03         case defconfig:
04                 if (!defconfig_file)
05                         defconfig_file = conf_get_default_confname();
06                 if (conf_read(defconfig_file)) {
07                         printf(_("***\n"
08                                 "*** Can't find default configuration \"%s\"!\n"
09                                 "***\n"), defconfig_file);
10                         exit(1);
11                 }
12                 break;

The conf_read function, which is defined in confdata.c, invokes the conf_read_simple function. This function simply performs some checks to determine whether to enable or disable a particular CONFIG option in the symbol_hash data structure that exists from scanning the kernel. The relevant snippets are reproduced in Listing 12.

01 while (compat_getline(&line, &line_asize, in) != -1) {
02 ...
03         if (line[0] == '#') {
04                 if (memcmp(line + 2, CONFIG_, strlen(CONFIG_)))
05                         continue;
06                 p = strchr(line + 2 + strlen(CONFIG_), ' ');
07                 if (!p)
08                         continue;
09                 *p++ = 0;
10                 if (strncmp(p, "is not set", 10))
11                         continue;
12                 if (def == S_DEF_USER) {
13                         sym = sym_find(line + 2 + strlen(CONFIG_));
14                         if (!sym) {
15                                 sym_add_change_count(1);
16                                 goto setsym;
17                         }
18                 } else {
19                         sym = sym_lookup(line + 2 + strlen(CONFIG_), 0);
20                         if (sym->type == S_UNKNOWN)
21                                 sym->type = S_BOOLEAN;
22                 }
23                 if (sym->flags & def_flags) {
24                         conf_warning("override: reassigning to symbol %s", sym->name);
25                 }
26                 switch (sym->type) {
27                         case S_BOOLEAN:
28                         case S_TRISTATE:
29                                 sym->def[def].tri = no;
30                                 sym->flags |= def_flags;
31                                 break;
32                         default:
33                                 ;
34                 }
35         }

Listing 12 shows the checks that are performed and how a particular CONFIG option is disabled. For each line, the function checks to see if it begins with a hash. If so, it then checks that CONFIG_ follows immediately after the hash. If so, it checks that the exact string "is not set" follows. If that check passes, then it searches the symbol table for the corresponding CONFIG option. If a symbol exists in the table, it sets the TRISTATE value of the symbol to no. A similar process exists for when a CONFIG option is enabled in the defconfig file. Finally, a check is done to ensure that the updated symbol table data structure is still valid.

Lastly, you know that a .config file is produced. How does that happen? You can look towards the end of the main function in conf.c to answer that question. Ultimately, a call to conf_write is made and NULL is passed in. In the conf_write function, calls are made to the conf_write_heading and conf_write_symbol functions to populate the final .config file.

Conclusion

The kernel Kconfig infrastructure is a pretty complex system that cleverly uses different paradigms and tools in computer science beyond just standard development. The use of Flex and Bison by Kconfig is an interesting case study in how to leverage seemingly irrelevant tools for an optimal solution.