kconfig: cache expression values

Cache expression values to avoid recalculating them repeatedly.

Signed-off-by: Masahiro Yamada <[email protected]>

kconfig: use hash table to reuse expressions

Currently, every expression in Kconfig files produces a new abstract
syntax tree (AST), even if it is identical to a previously encountered
one.

Conside

kconfig: use hash table to reuse expressions

Currently, every expression in Kconfig files produces a new abstract
syntax tree (AST), even if it is identical to a previously encountered
one.

Consider the following code:

config FOO
bool "FOO"
depends on (A || B) && C

config BAR
bool "BAR"
depends on (A || B) && C

config BAZ
bool "BAZ"
depends on A || B

The "depends on" lines are similar, but currently a separate AST is
allocated for each one.

The current data structure looks like this:

FOO->dep ==> AND BAR->dep ==> AND BAZ->dep ==> OR
/ \ / \ / \
OR C OR C A B
/ \ / \
A B A B

This is redundant; FOO->dep and BAR->dep have identical ASTs but
different memory instances.

We can optimize this; FOO->dep and BAR->dep can share the same AST, and
BAZ->dep can reference its sub tree.

The optimized data structure looks like this:

FOO->dep, BAR->dep ==> AND
/ \
BAZ->dep ==> OR C
/ \
A B

This commit introduces a hash table to keep track of allocated
expressions. If an identical expression is found, it is reused.

This does not necessarily result in memory savings, as menu_finalize()
transforms expressions without freeing up stale ones. This will be
addressed later.

One optimization that can be easily implemented is caching the
expression's value. Once FOO's dependency, (A || B) && C, is calculated,
it can be cached, eliminating the need to recalculate it for BAR.

This commit also reverts commit e983b7b17ad1 ("kconfig/menu.c: fix
multiple references to expressions in menu_add_prop()").

Signed-off-by: Masahiro Yamada <[email protected]>

show more ...

kconfig: change some expr_*() functions to bool

This clarifies the behavior of these functions.

Signed-off-by: Masahiro Yamada <[email protected]>

kconfig: remove P_SYMBOL property

P_SYMBOL is a pseudo property that was previously used for data linking
purposes.

It is no longer used except for debug prints. Remove it.

Signed-off-by: Masahiro

kconfig: remove P_SYMBOL property

P_SYMBOL is a pseudo property that was previously used for data linking
purposes.

It is no longer used except for debug prints. Remove it.

Signed-off-by: Masahiro Yamada <[email protected]>

show more ...

kbuild: move some helper headers from scripts/kconfig/ to scripts/include/

Move array_size.h, hashtable.h, list.h, list_types.h from scripts/kconfig/
to scripts/include/.

These headers will be usef

kbuild: move some helper headers from scripts/kconfig/ to scripts/include/

Move array_size.h, hashtable.h, list.h, list_types.h from scripts/kconfig/
to scripts/include/.

These headers will be useful for other host programs.

Remove scripts/mod/list.h.

Signed-off-by: Masahiro Yamada <[email protected]>

show more ...

kconfig: remove SYMBOL_CHOICEVAL flag

This flag is unneeded because a choice member can be detected by
other means.

Signed-off-by: Masahiro Yamada <[email protected]>

kconfig: add const qualifiers to several function arguments

Clarify that the given structures are not modified.

Signed-off-by: Masahiro Yamada <[email protected]>

kconfig: remove E_LIST expression type

E_LIST was preveously used to form an expression tree consisting of
choice members.

It is no longer used.

Signed-off-by: Masahiro Yamada <[email protected]

kconfig: remove E_LIST expression type

E_LIST was preveously used to form an expression tree consisting of
choice members.

It is no longer used.

Signed-off-by: Masahiro Yamada <[email protected]>

show more ...

kconfig: remove P_CHOICE property

P_CHOICE is a pseudo property used to link a choice with its members.

There is no more code relying on this, except for some debug code.

Signed-off-by: Masahiro Y

kconfig: remove P_CHOICE property

P_CHOICE is a pseudo property used to link a choice with its members.

There is no more code relying on this, except for some debug code.

Signed-off-by: Masahiro Yamada <[email protected]>

show more ...

kconfig: remove expr_list_for_each_sym() macro

All users of this macro have been converted. Remove it.

Signed-off-by: Masahiro Yamada <[email protected]>

kconfig: refactor choice value calculation

Handling choices has always been in a PITA in Kconfig.

For example, fixes and reverts were repeated for randconfig with
KCONFIG_ALLCONFIG:

- 422c809f03f

kconfig: refactor choice value calculation

Handling choices has always been in a PITA in Kconfig.

For example, fixes and reverts were repeated for randconfig with
KCONFIG_ALLCONFIG:

- 422c809f03f0 ("kconfig: fix randomising choice entries in presence of KCONFIG_ALLCONFIG")
- 23a5dfdad22a ("Revert "kconfig: fix randomising choice entries in presence of KCONFIG_ALLCONFIG"")
- 8357b48549e1 ("kconfig: fix randomising choice entries in presence of KCONFIG_ALLCONFIG")
- 490f16171119 ("Revert "kconfig: fix randomising choice entries in presence of KCONFIG_ALLCONFIG"")

As these commits pointed out, randconfig does not randomize choices when
KCONFIG_ALLCONFIG is used. This issue still remains.

[Test Case]

choice
prompt "choose"

config A
bool "A"

config B
bool "B"

endchoice

$ echo > all.config
$ make KCONFIG_ALLCONFIG=1 randconfig

The output is always as follows:

CONFIG_A=y
# CONFIG_B is not set

Not only randconfig, but other all*config variants are also broken with
KCONFIG_ALLCONFIG.

With the same Kconfig,

$ echo '# CONFIG_A is not set' > all.config
$ make KCONFIG_ALLCONFIG=1 allyesconfig

You will get this:

CONFIG_A=y
# CONFIG_B is not set

This is incorrect because it does not respect all.config.

The correct output should be:

# CONFIG_A is not set
CONFIG_B=y

To handle user inputs more accurately, this commit refactors the code
based on the following principles:

- When a user value is given, Kconfig must set it immediately.
Do not defer it by setting SYMBOL_NEED_SET_CHOICE_VALUES.

- The SYMBOL_DEF_USER flag must not be cleared, unless a new config
file is loaded. Kconfig must not forget user inputs.

In addition, user values for choices must be managed with priority.
If user inputs conflict within a choice block, the newest value wins.
The values given by randconfig have lower priority than explicit user
inputs.

This commit implements it by using a linked list. Every time a choice
block gets a new input, it is moved to the top of the list.

Let me explain how it works.

Let's say, we have a choice block that consists of five symbols:
A, B, C, D, and E.

Initially, the linked list looks like this:

A(=?) --> B(=?) --> C(=?) --> D(=?) --> E(=?)

Suppose randconfig is executed with the following KCONFIG_ALLCONFIG:

CONFIG_C=y
# CONFIG_A is not set
CONFIG_D=y

First, CONFIG_C=y is read. C is set to 'y' and moved to the top.

C(=y) --> A(=?) --> B(=?) --> D(=?) --> E(=?)

Next, '# CONFIG_A is not set' is read. A is set to 'n' and moved to
the top.

A(=n) --> C(=y) --> B(=?) --> D(=?) --> E(=?)

Then, 'CONFIG_D=y' is read. D is set to 'y' and moved to the top.

D(=y) --> A(=n) --> C(=y) --> B(=?) --> E(=?)

Lastly, randconfig shuffles the order of the remaining symbols,
resulting in:

D(=y) --> A(=n) --> C(=y) --> B(=y) --> E(=y)
or
D(=y) --> A(=n) --> C(=y) --> E(=y) --> B(=y)

When calculating the output, the linked list is traversed and the first
visible symbol with 'y' is taken. In this case, it is D if visible.

If D is hidden by 'depends on', the next node, A, is examined. Since
it is already specified as 'n', it is skipped. Next, C is checked, and
selected if it is visible.

If C is also invisible, either B or E is chosen as a result of the
randomization.

If B and E are also invisible, the linked list is traversed in the
reverse order, and the least prioritized 'n' symbol is chosen. It is
A in this case.

Now, Kconfig remembers all user values. This is a big difference from
the previous implementation, where Kconfig would forget CONFIG_C=y when
CONFIG_D=y appeared in the same input file.

The new appaorch respects user-specified values as much as possible.

Signed-off-by: Masahiro Yamada <[email protected]>

show more ...

kconfig: remove wrong expr_trans_bool()

expr_trans_bool() performs an incorrect transformation.

[Test Code]

config MODULES
def_bool y
modules

config A

kconfig: remove wrong expr_trans_bool()

expr_trans_bool() performs an incorrect transformation.

[Test Code]

config MODULES
def_bool y
modules

config A
def_bool y
select C if B != n

config B
def_tristate m

config C
tristate

[Result]

CONFIG_MODULES=y
CONFIG_A=y
CONFIG_B=m
CONFIG_C=m

This output is incorrect because CONFIG_C=y is expected.

Documentation/kbuild/kconfig-language.rst clearly explains the function
of the '!=' operator:

If the values of both symbols are equal, it returns 'n',
otherwise 'y'.

Therefore, the statement:

select C if B != n

should be equivalent to:

select C if y

Or, more simply:

select C

Hence, the symbol C should be selected by the value of A, which is 'y'.

However, expr_trans_bool() wrongly transforms it to:

select C if B

Therefore, the symbol C is selected by (A && B), which is 'm'.

The comment block of expr_trans_bool() correctly explains its intention:

* bool FOO!=n => FOO
^^^^

If FOO is bool, FOO!=n can be simplified into FOO. This is correct.

However, the actual code performs this transformation when FOO is
tristate:

if (e->left.sym->type == S_TRISTATE) {
^^^^^^^^^^

While it can be fixed to S_BOOLEAN, there is no point in doing so
because expr_tranform() already transforms FOO!=n to FOO when FOO is
bool. (see the "case E_UNEQUAL" part)

expr_trans_bool() is wrong and unnecessary.

Signed-off-by: Masahiro Yamada <[email protected]>
Acked-by: Randy Dunlap <[email protected]>

show more ...

kconfig: remove unused expr_is_no()

This has not been used since commit e911503085ae ("Kconfig: Remove
bad inference rules expr_eliminate_dups2()").

Signed-off-by: Masahiro Yamada <masahiroy@kernel

kconfig: remove unused expr_is_no()

This has not been used since commit e911503085ae ("Kconfig: Remove
bad inference rules expr_eliminate_dups2()").

Signed-off-by: Masahiro Yamada <[email protected]>

show more ...

kconfig: remove SYMBOL_NO_WRITE flag

This flag is set to symbols that are not intended to be written
to the .config file.

Since commit b75b0a819af9 ("kconfig: change defconfig_list option to
enviro

kconfig: remove SYMBOL_NO_WRITE flag

This flag is set to symbols that are not intended to be written
to the .config file.

Since commit b75b0a819af9 ("kconfig: change defconfig_list option to
environment variable"), SYMBOL_NO_WRITE is only set to choices.

Therefore, (sym->flags & SYMBOL_NO_WRITE) is equivalent to
sym_is_choice(sym). This flag is no longer necessary.

Signed-off-by: Masahiro Yamada <[email protected]>

show more ...

kconfig: remove 'optional' property support

The 'choice' statement is primarily used to exclusively select one
option, but the 'optional' property allows all entries to be disabled.

In the followin

kconfig: remove 'optional' property support

The 'choice' statement is primarily used to exclusively select one
option, but the 'optional' property allows all entries to be disabled.

In the following example, both A and B can be disabled simultaneously:

choice
prompt "choose A, B, or nothing"
optional

config A
bool "A"

config B
bool "B"

endchoice

You can achieve the equivalent outcome by other means.

A common solution is to add another option to guard the choice block.
In the following example, you can set ENABLE_A_B_CHOICE=n to disable
the entire choice block:

choice
prompt "choose A or B"
depends on ENABLE_A_B_CHOICE

config A
bool "A"

config B
bool "B"

endchoice

Another approach is to insert one more entry:

choice
prompt "choose A, B, or disable both"

config A
bool "A"

config B
bool "B"

config DISABLE_A_AND_B
bool "choose this to disable both A and B"

endchoice

Some real examples are DEBUG_INFO_NONE, INITRAMFS_COMPRESSION_NONE,
LTO_NONE, etc.

The 'optional' property is even more unnecessary for a tristate choice.

Without the 'optional' property, you can disable A and B; you can set
'm' in the choice prompt, and disable A and B individually:

choice
prompt "choose one built-in or make them modular"

config A
tristate "A"

config B
tristate "B"

endchoice

In conclusion, the 'optional' property was unneeded.

Signed-off-by: Masahiro Yamada <[email protected]>
Reviewed-by: Nicolas Schier <[email protected]>

show more ...

kconfig: remove SYMBOL_CHOICE flag

All symbols except choices have a name.

Previously, choices were allowed to have a name, but commit c83f020973bc
("kconfig: remove named choice support") eliminat

kconfig: remove SYMBOL_CHOICE flag

All symbols except choices have a name.

Previously, choices were allowed to have a name, but commit c83f020973bc
("kconfig: remove named choice support") eliminated that possibility.

Now, it is easy to distinguish choices from normal symbols; if the name
is NULL, it is a choice.

Signed-off-by: Masahiro Yamada <[email protected]>
Reviewed-by: Nicolas Schier <[email protected]>

show more ...

kconfig: link menus to a symbol

Currently, there is no direct link from (struct symbol) to (struct menu).

It is still possible to access associated menus through the P_SYMBOL
property, because prop

kconfig: link menus to a symbol

Currently, there is no direct link from (struct symbol) to (struct menu).

It is still possible to access associated menus through the P_SYMBOL
property, because property::menu is the relevant menu entry, but it
results in complex code, as seen in get_symbol_str().

Use a linked list for simpler traversal of relevant menus.

Signed-off-by: Masahiro Yamada <[email protected]>
Reviewed-by: Nicolas Schier <[email protected]>

show more ...

kconfig: use generic macros to implement symbol hashtable

Use helper macros in hashtable.h for generic hashtable implementation.

We can git rid of the hash head index of for_all_symbols().

Signed-

kconfig: use generic macros to implement symbol hashtable

Use helper macros in hashtable.h for generic hashtable implementation.

We can git rid of the hash head index of for_all_symbols().

Signed-off-by: Masahiro Yamada <[email protected]>

show more ...

kconfig: split list_head into a separate header

The struct list_head is often embedded in other structures, while other
code is used in C functions.

By separating struct list_head into its own head

kconfig: split list_head into a separate header

The struct list_head is often embedded in other structures, while other
code is used in C functions.

By separating struct list_head into its own header, other headers are no
longer required to include the entire list.h.

This is similar to the kernel space, where struct list_head is defined
in <linux/types.h> instead of <linux/list.h>.

Signed-off-by: Masahiro Yamada <[email protected]>

show more ...

kconfig: change file_lookup() to return the file name

Currently, file_lookup() returns a pointer to (struct file), but the
callers use only file->name.

Make it return the ->name member directly.

T

kconfig: change file_lookup() to return the file name

Currently, file_lookup() returns a pointer to (struct file), but the
callers use only file->name.

Make it return the ->name member directly.

This adjustment encapsulates struct file and file_list as internal
implementation.

Signed-off-by: Masahiro Yamada <[email protected]>

show more ...

kconfig: make file::name a flexible array member

Call malloc() just once to allocate needed memory.

Signed-off-by: Masahiro Yamada <[email protected]>

kconfig: move the file and lineno in struct file to struct buffer

struct file has two link nodes, 'next' and 'parent'.

The former is used to link files in the 'file_list' linked list,
which manages

kconfig: move the file and lineno in struct file to struct buffer

struct file has two link nodes, 'next' and 'parent'.

The former is used to link files in the 'file_list' linked list,
which manages the list of Kconfig files seen so far.

The latter is used to link files in the 'current_file' linked list,
which manages the inclusion ("source") tree.

The latter should be tracked together with the lexer state.

Signed-off-by: Masahiro Yamada <[email protected]>

show more ...

kconfig: associate struct property with file name directly

struct property is linked to struct file for diagnostic purposes.
It is always used to retrieve the file name through prop->file->name.

As

kconfig: associate struct property with file name directly

struct property is linked to struct file for diagnostic purposes.
It is always used to retrieve the file name through prop->file->name.

Associate struct property with the file name directly.

Signed-off-by: Masahiro Yamada <[email protected]>

show more ...

kconfig: associate struct menu with file name directly

struct menu is linked to struct file for diagnostic purposes.
It is always used to retrieve the file name through menu->file->name.

Associate

kconfig: associate struct menu with file name directly

struct menu is linked to struct file for diagnostic purposes.
It is always used to retrieve the file name through menu->file->name.

Associate struct menu with the file name directly.

Signed-off-by: Masahiro Yamada <[email protected]>

show more ...

kconfig: remove orphan lookup_file() declaration

There is no definition, no caller for lookup_file().

Signed-off-by: Masahiro Yamada <[email protected]>