Since commit 95573cac25 ("kconfig: cache expression values"), xconfig
emits a lot of false-positive "unmet direct dependencies" warnings.
While conf_read() clears val_is_valid flags, 'make xconfig' calculates
symbol values even before the conf_read() call. This is another issue
that should be addressed separately, but it has revealed that the
val_is_valid field is not initialized.
Fixes: 95573cac25 ("kconfig: cache expression values")
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
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 e983b7b17a ("kconfig/menu.c: fix
multiple references to expressions in menu_add_prop()").
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
Currently, expr_eliminate_dups() passes two identical pointers down to
expr_eliminate_dups1(), which later skips processing identical leaves.
This approach is somewhat tricky and, more importantly, it will not work
with the refactoring made in the next commit.
This commit slightly changes the recursion logic; it deduplicates both
the left and right arms, and then passes them to expr_eliminate_dups1().
expr_eliminate_dups() should produce the same result.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
I do not think the macros 'e1' and 'e2' are readable.
The statement:
e1 = expr_alloc_symbol(...);
affects the caller's variable, but this is not sufficiently clear from the code.
Remove the macros. No functional change intended.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
Kconfig simplifies expressions, but redundant '&&' and '||' operators
involving constant symbols 'y' and 'n' are sometimes trimmed and
sometimes not.
[Test Code]
config DEP
def_bool y
config A
bool "A"
depends on DEP && y
config B
bool "B"
depends on DEP && y && y
[Result]
$ make helpnewconfig
[ snip ]
-----
There is no help available for this option.
Symbol: A [=n]
Type : bool
Defined at Kconfig:4
Prompt: A
Depends on: DEP [=y] && y [=y]
Location:
-> A (A [=n])
-----
-----
There is no help available for this option.
Symbol: B [=n]
Type : bool
Defined at Kconfig:8
Prompt: B
Depends on: DEP [=y]
Location:
-> B (B [=n])
-----
The dependency for A, 'DEP && y', remains as-is, while that for B,
'DEP && y && y', has been reduced to 'DEP'.
Currently, expr_eliminate_dups() calls expr_eliminate_yn() only when
trans_count != 0, in other words, only when expr_eliminate_dups1() has
trimmed at least one leaf. It fails to trim a single '&& y', etc.
To fix this inconsistent behavior, expr_eliminate_yn() should be called
at least once even if no leaf has been trimmed.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
E_LIST was preveously used to form an expression tree consisting of
choice members.
It is no longer used.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
The condition (t2 == 0) never becomes true because the zero value
(i.e., E_NONE) is only used as a dummy type for prevtoken. It can
be passed to t1, but not to t2.
The caller of this function only checks expr_compare_type() > 0.
Therefore, the distinction between 0 and -1 is unnecessary.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
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 <masahiroy@kernel.org>
Acked-by: Randy Dunlap <rdunlap@infradead.org>
The check for 'sym1 == sym2' is redundant here because it has already
been done a few lines above:
if (sym1 != sym2)
return NULL;
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
Kconfig makes a distinction between dependencies (defined by "depends
on" expressions and enclosing "if" blocks) and visibility (which
includes all dependencies, but also includes inline "if" expressions of
individual properties as well as, for prompts, "visible if" expressions
of enclosing menus).
Before commit bcdedcc1af ("menuconfig: print more info for symbol
without prompts"), the "Depends on" lines of a symbol's help text
indicated the visibility of the prompt property they appeared under.
After bcdedcc1af, there was always only a single "Depends on" line,
which indicated the visibility of the first P_SYMBOL property of the
symbol. Since P_SYMBOLs never have inline if expressions, this was in
effect the same as the dependencies of the menu item that the P_SYMBOL
was attached to.
Neither of these situations accurately conveyed the dependencies of a
symbol--the first because it was actually the visibility, and the second
because it only showed the dependencies from a single definition.
With this series, we are back to printing separate dependencies for each
definition, but we print the actual dependencies (rather than the
visibility) in the "Depends on" line. However, it can still be useful to
know the visibility of a prompt, so this patch adds a "Visible if" line
that shows the visibility only if the visibility is different from the
dependencies (which it isn't for most prompts in Linux).
Before:
Symbol: THUMB2_KERNEL [=n]
Type : bool
Defined at arch/arm/Kconfig:1417
Prompt: Compile the kernel in Thumb-2 mode
Depends on: (CPU_V7 [=y] || CPU_V7M [=n]) && !CPU_V6 [=n] && !CPU_V6K [=n]
Location:
-> Kernel Features
Selects: ARM_UNWIND [=n]
After:
Symbol: THUMB2_KERNEL [=n]
Type : bool
Defined at arch/arm/Kconfig:1417
Prompt: Compile the kernel in Thumb-2 mode
Depends on: (CPU_V7 [=y] || CPU_V7M [=n]) && !CPU_V6 [=n] && !CPU_V6K [=n]
Visible if: (CPU_V7 [=y] || CPU_V7M [=n]) && !CPU_V6 [=n] && !CPU_V6K [=n] && !CPU_THUMBONLY [=n]
Location:
-> Kernel Features
Selects: ARM_UNWIND [=n]
Signed-off-by: Thomas Hebb <tommyhebb@gmail.com>
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
NULL expressions are taken to always be true, as implemented by the
expr_is_yes() macro and by several other functions in expr.c. As such,
they ought to be valid inputs to expr_eq(), which compares two
expressions.
Signed-off-by: Thomas Hebb <tommyhebb@gmail.com>
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
I want to compile each C file independently instead of including all
of them from zconf.y.
Split out confdata.c, expr.c, symbol.c, and preprocess.c .
These are low-hanging fruits.
Signed-off-by: Masahiro Yamada <yamada.masahiro@socionext.com>
All files in lxdialog/ are licensed under GPL-2.0+, and the rest are
under GPL-2.0. I added GPL-2.0 tags to test scripts in tests/.
Documentation/process/license-rules.rst does not suggest anything
about the flex/bison files. Because flex does not accept the C++
comment style at the very top of a file, I used the C style for
zconf.l, and so for zconf.y for consistency.
Signed-off-by: Masahiro Yamada <yamada.masahiro@socionext.com>
The only possibility of k_invalid being returned was when
expr_parse_sting() parsed S_OTHER type symbol. This actually never
happened, and this is even clearer since S_OTHER has gone.
Clean up unreachable code.
Signed-off-by: Masahiro Yamada <yamada.masahiro@socionext.com>
Currently, the unmet dependency warnings end up with endlessly long
expressions, most of which are false positives.
Here is test code to demonstrate how it currently works.
[Test Case]
config DEP1
def_bool y
config DEP2
bool "DEP2"
config A
bool "A"
select E
config B
bool "B"
depends on DEP2
select E
config C
bool "C"
depends on DEP1 && DEP2
select E
config D
def_bool n
select E
config E
bool
depends on DEP1 && DEP2
[Result]
$ make config
scripts/kconfig/conf --oldaskconfig Kconfig
*
* Linux Kernel Configuration
*
DEP2 (DEP2) [N/y/?] (NEW) n
A (A) [N/y/?] (NEW) y
warning: (A && B && D) selects E which has unmet direct
dependencies (DEP1 && DEP2)
Here, I see some points to be improved.
First, '(A || B || D)' would make more sense than '(A && B && D)'.
I am not sure if this is intentional, but expr_simplify_unmet_dep()
turns OR expressions into AND, like follows:
case E_OR:
return expr_alloc_and(
Second, we see false positives. 'A' is a real unmet dependency.
'B' is false positive because 'DEP1' is fixed to 'y', and 'B' depends
on 'DEP2'. 'C' was correctly dropped by expr_simplify_unmet_dep().
'D' is also false positive because it has no chance to be enabled.
Current expr_simplify_unmet_dep() cannot avoid those false positives.
After all, I decided to use the same helpers as used for printing
reverse dependencies in the help.
With this commit, unreadable warnings (most of the reported symbols are
false positives) in the real world:
$ make ARCH=score allyesconfig
scripts/kconfig/conf --allyesconfig Kconfig
warning: (HWSPINLOCK_QCOM && AHCI_MTK && STMMAC_PLATFORM &&
DWMAC_IPQ806X && DWMAC_LPC18XX && DWMAC_OXNAS && DWMAC_ROCKCHIP &&
DWMAC_SOCFPGA && DWMAC_STI && TI_CPSW && PINCTRL_GEMINI &&
PINCTRL_OXNAS && PINCTRL_ROCKCHIP && PINCTRL_DOVE &&
PINCTRL_ARMADA_37XX && PINCTRL_STM32 && S3C2410_WATCHDOG &&
VIDEO_OMAP3 && VIDEO_S5P_FIMC && USB_XHCI_MTK && RTC_DRV_AT91SAM9 &&
LPC18XX_DMAMUX && VIDEO_OMAP4 && COMMON_CLK_GEMINI &&
COMMON_CLK_ASPEED && COMMON_CLK_NXP && COMMON_CLK_OXNAS &&
COMMON_CLK_BOSTON && QCOM_ADSP_PIL && QCOM_Q6V5_PIL && QCOM_GSBI &&
ATMEL_EBI && ST_IRQCHIP && RESET_IMX7 && PHY_HI6220_USB &&
PHY_RALINK_USB && PHY_ROCKCHIP_PCIE && PHY_DA8XX_USB) selects
MFD_SYSCON which has unmet direct dependencies (HAS_IOMEM)
warning: (PINCTRL_AT91 && PINCTRL_AT91PIO4 && PINCTRL_OXNAS &&
PINCTRL_PISTACHIO && PINCTRL_PIC32 && PINCTRL_MESON &&
PINCTRL_NOMADIK && PINCTRL_MTK && PINCTRL_MT7622 && GPIO_TB10X)
selects OF_GPIO which has unmet direct dependencies (GPIOLIB && OF &&
HAS_IOMEM)
warning: (FAULT_INJECTION_STACKTRACE_FILTER && LATENCYTOP && LOCKDEP)
selects FRAME_POINTER which has unmet direct dependencies
(DEBUG_KERNEL && (CRIS || M68K || FRV || UML || SUPERH || BLACKFIN ||
MN10300 || METAG) || ARCH_WANT_FRAME_POINTERS)
will be turned into:
$ make ARCH=score allyesconfig
scripts/kconfig/conf --allyesconfig Kconfig
WARNING: unmet direct dependencies detected for MFD_SYSCON
Depends on [n]: HAS_IOMEM [=n]
Selected by [y]:
- PINCTRL_STM32 [=y] && PINCTRL [=y] && (ARCH_STM32 ||
COMPILE_TEST [=y]) && OF [=y]
- RTC_DRV_AT91SAM9 [=y] && RTC_CLASS [=y] && (ARCH_AT91 ||
COMPILE_TEST [=y])
- RESET_IMX7 [=y] && RESET_CONTROLLER [=y]
- PHY_HI6220_USB [=y] && (ARCH_HISI && ARM64 ||
COMPILE_TEST [=y])
- PHY_RALINK_USB [=y] && (RALINK || COMPILE_TEST [=y])
- PHY_ROCKCHIP_PCIE [=y] && (ARCH_ROCKCHIP && OF [=y] ||
COMPILE_TEST [=y])
WARNING: unmet direct dependencies detected for OF_GPIO
Depends on [n]: GPIOLIB [=y] && OF [=y] && HAS_IOMEM [=n]
Selected by [y]:
- PINCTRL_MTK [=y] && PINCTRL [=y] && (ARCH_MEDIATEK ||
COMPILE_TEST [=y]) && OF [=y]
- PINCTRL_MT7622 [=y] && PINCTRL [=y] && (ARCH_MEDIATEK ||
COMPILE_TEST [=y]) && OF [=y] && (ARM64 || COMPILE_TEST [=y])
WARNING: unmet direct dependencies detected for FRAME_POINTER
Depends on [n]: DEBUG_KERNEL [=y] && (CRIS || M68K || FRV || UML ||
SUPERH || BLACKFIN || MN10300 || METAG) || ARCH_WANT_FRAME_POINTERS [=n]
Selected by [y]:
- LATENCYTOP [=y] && DEBUG_KERNEL [=y] && STACKTRACE_SUPPORT [=y] &&
PROC_FS [=y] && !MIPS && !PPC && !S390 && !MICROBLAZE && !ARM_UNWIND &&
!ARC && !X86
Signed-off-by: Masahiro Yamada <yamada.masahiro@socionext.com>
Reviewed-by: Petr Vorel <petr.vorel@gmail.com>
Surprisingly or not, disabling a CONFIG option (which is assumed to
be unneeded) may be not so trivial. Especially it is not trivial, when
this CONFIG option is selected by a dozen of other configs. Before the
moment commit 1ccb271433 ("kconfig: make "Selected by:" and
"Implied by:" readable") popped up in v4.16-rc1, it was an absolute pain
to break down the "Selected by" reverse dependency expression in order
to identify all those configs which select (IOW *do not allow
disabling*) a certain feature (assumed to be not needed).
This patch tries to make one step further by putting at users'
fingertips the revdep top level OR sub-expressions grouped/clustered by
the tristate value they evaluate to. This should allow the users to
directly concentrate on and tackle the _active_ reverse dependencies.
To give some numbers and quantify the complexity of certain reverse
dependencies, assuming commit 617aebe6a9 ("Merge tag
'usercopy-v4.16-rc1' of
git://git.kernel.org/pub/scm/linux/kernel/git/kees/linux"), ARCH=arm64
and vanilla arm64 defconfig, here is the top 10 CONFIG options with
the highest amount of top level "||" sub-expressions/tokens that make
up the final "Selected by" reverse dependency expression.
| Config | All revdep | Active revdep |
|-------------------|------------|---------------|
| REGMAP_I2C | 212 | 9 |
| CRC32 | 167 | 25 |
| FW_LOADER | 128 | 5 |
| MFD_CORE | 124 | 9 |
| FB_CFB_IMAGEBLIT | 114 | 2 |
| FB_CFB_COPYAREA | 111 | 2 |
| FB_CFB_FILLRECT | 110 | 2 |
| SND_PCM | 103 | 2 |
| CRYPTO_HASH | 87 | 19 |
| WATCHDOG_CORE | 86 | 6 |
The story behind the above is that users need to visually
review/evaluate 212 expressions which *potentially* select REGMAP_I2C
in order to identify the expressions which *actually* select REGMAP_I2C,
for a particular ARCH and for a particular defconfig used.
To make this experience smoother, change the way reverse dependencies
are displayed to the user from [1] to [2].
[1] Old representation of DMA_ENGINE_RAID:
Selected by:
- AMCC_PPC440SPE_ADMA [=n] && DMADEVICES [=y] && (440SPe || 440SP)
- BCM_SBA_RAID [=m] && DMADEVICES [=y] && (ARM64 [=y] || ...
- FSL_RAID [=n] && DMADEVICES [=y] && FSL_SOC && ...
- INTEL_IOATDMA [=n] && DMADEVICES [=y] && PCI [=y] && X86_64
- MV_XOR [=n] && DMADEVICES [=y] && (PLAT_ORION || ARCH_MVEBU [=y] ...
- MV_XOR_V2 [=y] && DMADEVICES [=y] && ARM64 [=y]
- XGENE_DMA [=n] && DMADEVICES [=y] && (ARCH_XGENE [=y] || ...
- DMATEST [=n] && DMADEVICES [=y] && DMA_ENGINE [=y]
[2] New representation of DMA_ENGINE_RAID:
Selected by [y]:
- MV_XOR_V2 [=y] && DMADEVICES [=y] && ARM64 [=y]
Selected by [m]:
- BCM_SBA_RAID [=m] && DMADEVICES [=y] && (ARM64 [=y] || ...
Selected by [n]:
- AMCC_PPC440SPE_ADMA [=n] && DMADEVICES [=y] && (440SPe || ...
- FSL_RAID [=n] && DMADEVICES [=y] && FSL_SOC && ...
- INTEL_IOATDMA [=n] && DMADEVICES [=y] && PCI [=y] && X86_64
- MV_XOR [=n] && DMADEVICES [=y] && (PLAT_ORION || ARCH_MVEBU [=y] ...
- XGENE_DMA [=n] && DMADEVICES [=y] && (ARCH_XGENE [=y] || ...
- DMATEST [=n] && DMADEVICES [=y] && DMA_ENGINE [=y]
Suggested-by: Masahiro Yamada <yamada.masahiro@socionext.com>
Signed-off-by: Eugeniu Rosca <erosca@de.adit-jv.com>
Reviewed-by: Petr Vorel <pvorel@suse.cz>
Reviewed-by: Ulf Magnusson <ulfalizer@gmail.com>
Signed-off-by: Masahiro Yamada <yamada.masahiro@socionext.com>
This commit splits out the special E_OR handling ('-' instead of '||')
into a dedicated helper expr_print_revdev().
Restore the original expr_print() prior to commit 1ccb271433
("kconfig: make "Selected by:" and "Implied by:" readable").
This makes sense because:
- We need to chop those expressions only when printing the reverse
dependency, and only when E_OR is encountered
- Otherwise, it should be printed as before, so fall back to
expr_print()
This also improves the behavior; for a single line, it was previously
displayed in the same line as "Selected by", like this:
Selected by: A [=n] && B [=n]
This will be displayed in a new line, consistently:
Selected by:
- A [=n] && B [=n]
Signed-off-by: Masahiro Yamada <yamada.masahiro@socionext.com>
Reviewed-by: Petr Vorel <pvorel@suse.cz>
