Introduce the markers_cnt variable for readability.

No functional change intended.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>

pacman is the package manager used by Arch Linux and its derivates.
Creating native packages from the kernel tree has multiple advantages:

* The package triggers the correct hooks for initramfs generation and
  bootloader configuration
* Uninstallation is complete and also invokes the relevant hooks
* New UAPI headers can be installed without any manual bookkeeping

The PKGBUILD file is a modified version of the one used for the
downstream Arch Linux "linux" package.
Extra steps that should not be necessary for a development kernel have
been removed and an UAPI header package has been added.
Signed-off-by: Thomas Weißschuh <linux@weissschuh.net>
Reviewed-by: Nathan Chancellor <nathan@kernel.org>
Tested-by: Nathan Chancellor <nathan@kernel.org>
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>

Use macros provided by hashtable.h
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>

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 <masahiroy@kernel.org>

Kbuild provides scripts/Makefile.host to build host programs used for
building the kernel. Unfortunately, there are two exceptions that opt
out of Kbuild. The build system under tools/ is a cheesy replica, and
cause issues. I was recently poked about a problem in the tools build
system, which I do not maintain (and nobody maintains). [1]

Without a comment, people might believe this is the right location
because that is where objtool lives, even if a more robust Kbuild
syntax satisfies their needs. [2]

[1]: https://lore.kernel.org/linux-kbuild/ZnIYWBgrJ-IJtqK8@google.com/T/#m8ece130dd0e23c6f2395ed89070161948dee8457
[2]: https://lore.kernel.org/all/20240618200501.GA1611012@google.com/Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
Acked-by: Nicolas Schier <nicolas@fjasle.eu>
Reviewed-by: Brian Norris <briannorris@chromium.org>
Reviewed-by: Sami Tolvanen <samitolvanen@google.com>

These lines have been here for more than a year. Remove them.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>

This prevents segfault when getting filename and lineno in recursive
checks.

If the following snippet is found in Kconfig:

[Test code 1]

config FOO
        bool
        depends on BAR
        select BAR

... without BAR defined; then there is a segfault.

  Kconfig:34:error: recursive dependency detected!
  Kconfig:34:	symbol FOO depends on BAR
  make[4]: *** [scripts/kconfig/Makefile:85: allnoconfig] Segmentation fault

This is because of the following. BAR is a fake entry created by
sym_lookup() with prop being NULL. In the recursive check, there is a
NULL check for prop to fall back to stack->sym->prop if stack->prop is
NULL. However, in this case, stack->sym points to the fake BAR entry
created by sym_lookup(), so prop is still NULL. prop was then referenced
without additional NULL checks, causing segfault.

As the previous email thread suggests, the file and lineno for select is
also wrong:

[Test code 2]

config FOO
       bool

config BAR
       bool

config FOO
       bool "FOO"
       depends on BAR
       select BAR

  $ make defconfig
  *** Default configuration is based on 'x86_64_defconfig'
  Kconfig:1:error: recursive dependency detected!
  Kconfig:1: symbol FOO depends on BAR
  Kconfig:4: symbol BAR is selected by FOO
  [...]

Kconfig:4 should be Kconfig:10.

This patch deletes the wrong and segfault-prone filename/lineno
inference completely. With this patch, Test code 1 yields:

error: recursive dependency detected!
	symbol FOO depends on BAR
	symbol BAR is selected by FOO
Signed-off-by: HONG Yifan <elsk@google.com>
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>

Fix the following rpmbuild warning:

  $ make srcrpm-pkg
  ...
  RPM build warnings:
      source_date_epoch_from_changelog set but %changelog is missing
Signed-off-by: Rafael Aquini <aquini@redhat.com>
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>

Commit cf8e8658 ("arch: Remove Itanium (IA-64) architecture")
removed the last use of the absolute kallsyms.
Signed-off-by: Jann Horn <jannh@google.com>
Acked-by: Arnd Bergmann <arnd@arndb.de>
Link: https://lore.kernel.org/all/20240221202655.2423854-1-jannh@google.com/
[masahiroy@kernel.org: rebase the code and reword the commit description]
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>

If INSTALL_PATH is not a valid directory, create it, like what
modules_install and dtbs_install will do in the same situation.
Signed-off-by: Zhang Bingwu <xtexchooser@duck.com>
Reviewed-by: Nicolas Schier <nicolas@jasle.eu>
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>

Setting '-e' flag tells shells to exit with error exit code immediately
after any of commands fails, and causes make(1) to regard recipes as
failed.

Before this, make will still continue to succeed even after the
installation failed, for example, for insufficient permission or
directory does not exist.
Signed-off-by: Zhang Bingwu <xtexchooser@duck.com>
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>

This flag is unneeded because a choice member can be detected by
other means.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>

Clarify that the given structures are not modified.
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>

${DEBFULLNAME-${user}} falls back to ${user} when DEBFULLNAME is unset.
It is more reasonable to do so when DEBFULLNAME is unset or null.

Otherwise, the command:

  $ DEBFULLNAME= make deb-pkg

will leave the name field blank.

The same applies to KBUILD_BUILD_USER and KBUILD_BUILD_HOST.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
Reviewed-by: Nathan Chancellor <nathan@kernel.org>

/usr/include/elf.h, which originates from the glibc/musl, defines
R_ARM_THM_PC22 instead of R_ARM_THM_CALL.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
Reviewed-by: Nathan Chancellor <nathan@kernel.org>

Commit f5983dab ("modpost: define more R_ARM_* for old
distributions") added self-definitions for the R_ARM_* macros to fix
build errors on CentOS 7.

RHEL/CentOS 7 were retired at the end of June.

Remove all the R_ARM_* definitions (except for R_ARM_THM_CALL), which
should be available in recent distributions.

glibc and musl added most of R_ARM_* macros in 2013. [1] [2]

[1]: https://sourceware.org/git/?p=glibc.git;a=commitdiff;h=08cbd996d33114ca50644d060fbe3a08260430fb
[2]: https://git.musl-libc.org/cgit/musl/commit/?id=268375c1c017c0bdefeed1a330811e433c4dfaefSigned-off-by: Masahiro Yamada <masahiroy@kernel.org>
Reviewed-by: Nathan Chancellor <nathan@kernel.org>

RHEL/CentOS 7, popular distributions that install GNU Make 3.82, reached
EOM/EOL on June 30, 2024. While you may get extended support, it is a
good time to raise the minimum GNU Make version.

The new requirement, GNU Make 4.0, was released in October, 2013.

I did not touch the Makefiles under tools/ because I do not know the
requirements for building tools. I do not find any GNU Make version
checks under tools/.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
Reviewed-by: Nathan Chancellor <nathan@kernel.org>

As commit afa974b7 ("kbuild: add real-prereqs shorthand for
$(filter-out FORCE,$^)") explained, $(real-prereqs) is not just a list
of objects when linking a multi-object module. If a single-object module
is turned into a multi-object module, $^ (and therefore $(real-prereqs)
as well) contains header files recorded in the *.cmd file. Such headers
must be filtered out.

Now that a DTB can be built either from a single source or multiple
source files, the same issue can occur.

Consider the following scenario:

First, foo.dtb is implemented as a single-blob device tree.

The code looks something like this:

[Sample Code 1]

  Makefile:

      dtb-y += foo.dtb

  foo.dts:

    #include <dt-bindings/gpio/gpio.h>
    /dts-v1/;
    / { };

When it is compiled, .foo.dtb.cmd records that foo.dtb depends on
scripts/dtc/include-prefixes/dt-bindings/gpio/gpio.h.

Later, foo.dtb is split into a base and an overlay. The code looks
something like this:

[Sample Code 2]

  Makefile:

      dtb-y += foo.dtb
      foo-dtbs := foo-base.dtb foo-addon.dtbo

  foo-base.dts:

    #include <dt-bindings/gpio/gpio.h>
    /dts-v1/;
    / { };

  foo-addon.dtso:

    /dts-v1/;
    /plugin/;
    / { };

If you rebuild foo.dtb without 'make clean', you will get this error:

    Overlay 'scripts/dtc/include-prefixes/dt-bindings/gpio/gpio.h' is incomplete

$(real-prereqs) contains not only foo-base.dtb and foo-addon.dtbo but
also scripts/dtc/include-prefixes/dt-bindings/gpio/gpio.h, which is
passed to scripts/dtc/fdtoverlay.

Fixes: 15d16d6d ("kbuild: Add generic rule to apply fdtoverlay")
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>

Set -e to make these scripts fail on the first error.

Set -u because these scripts are invoked by Makefile, and do not work
properly without necessary variables defined.

I tweaked mkdebian to cope with optional environment variables.

Remove the explicit "test -n ..." from install-extmod-build.

Both options are described in POSIX. [1]

[1]: https://pubs.opengroup.org/onlinepubs/009604499/utilities/set.htmlSigned-off-by: Masahiro Yamada <masahiroy@kernel.org>
Reviewed-by: Nicolas Schier <nicolas@fjasle.eu>

Commit d5940c60 ("kbuild: deb-pkg improve maintainer address
generation") supported the "name <email>" form for DEBEMAIL, with
behavior slightly different from devscripts.

In Kbuild, if DEBEMAIL is given in the form "name <email>", it is used
as-is, and DEBFULLNAME is ignored.

In contrast, debchange takes the name from DEBFULLNAME (or NAME) if set,
as described in 'man debchange':

  If this variable has the form "name <email>", then the maintainer name
  will also be taken from here if neither DEBFULLNAME nor NAME is set.

This commit removes support for the "name <email> form for DEBEMAIL,
as the current behavior is already different from debchange, and the
Debian manual suggests setting the email address and name separately in
DEBEMAIL and DEBFULLNAME. [1]

If there are any complaints about this removal, we can re-add it,
with better alignment with the debchange implementation. [2]

[1]: https://www.debian.org/doc/manuals/debmake-doc/ch03.en.html#email-setup
[2]: https://salsa.debian.org/debian/devscripts/-/blob/v2.23.7/scripts/debchange.pl#L802Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
Reviewed-by: Nicolas Schier <nicolas@fjasle.eu>

Commit edec611d ("kbuild, deb-pkg: improve maintainer
identification") added the EMAIL and NAME environment variables.

Commit d5940c60 ("kbuild: deb-pkg improve maintainer address
generation") removed support for NAME, but kept support for EMAIL.

The EMAIL and NAME environment variables are supported by some tools
(see 'man debchange'), but not by all.

We should support both of them, or neither of them. We should not stop
halfway.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
Reviewed-by: Nicolas Schier <nicolas@fjasle.eu>

Improve the error messages and clean up redundant code.

[1] remove redundant next_sym->name checks

If 'next_sym' is a choice, the first 'if' block is executed. In the
subsequent 'else if' blocks, 'next_sym" is not a choice, hence
next_sym->name is not NULL.

[2] remove redundant sym->name checks

A choice is never selected or implied by anyone because it has no name
(it is syntactically impossible). If it is, sym->name is not NULL.

[3] Show the location of choice instead of "<choice>"

"part of choice <choice>" does not convey useful information. Since a
choice has no name, it is more informative to display the file name and
line number.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>

Kconfig detects recursive dependencies in a choice block, but the error
message is unclear.

[Test Code]

    choice
            prompt "choose"
            depends on A

    config A
            bool "A"

    config B
            bool "B"

    endchoice

[Result]

    Kconfig:1:error: recursive dependency detected!
    Kconfig:1:      choice <choice> contains symbol A
    Kconfig:5:      symbol A is part of choice <choice>
    For a resolution refer to Documentation/kbuild/kconfig-language.rst
    subsection "Kconfig recursive dependency limitations"

The phrase "contains symbol A" does not accurately describe the problem.
The issue is that the choice depends on A, which is a member of itself.

The first if-block does not print a sensible message. Remove it.

This commit improves the error message to:

    Kconfig:1:error: recursive dependency detected!
    Kconfig:1:      symbol <choice> symbol is visible depending on A
    Kconfig:5:      symbol A is part of choice <choice>
    For a resolution refer to Documentation/kbuild/kconfig-language.rst
    subsection "Kconfig recursive dependency limitations"
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>

A choice member must not depend on another member within the same choice
block.

Kconfig detects this, but the error message is not sensible.

[Test Code]

    choice
            prompt "choose"

    config A
            bool "A"
            depends on B

    config B
            bool "B"

    endchoice

[Result]

    Kconfig:1:error: recursive dependency detected!
    Kconfig:1:      choice <choice> contains symbol A
    Kconfig:4:      symbol A is part of choice B
    Kconfig:8:      symbol B is part of choice <choice>
    For a resolution refer to Documentation/kbuild/kconfig-language.rst
    subsection "Kconfig recursive dependency limitations"

The phrase "part of choice B" is weird because B is not a choice block,
but a choice member.

To determine whether the current symbol is a part of a choice block,
sym_is_choice(next_sym) must be checked.

This commit improves the error message to:

    Kconfig:1:error: recursive dependency detected!
    Kconfig:1:      choice <choice> contains symbol A
    Kconfig:4:      symbol A symbol is visible depending on B
    Kconfig:8:      symbol B is part of choice <choice>
    For a resolution refer to Documentation/kbuild/kconfig-language.rst
    subsection "Kconfig recursive dependency limitations"
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>

When a prompt is followed by "if <expr>", the symbol is configurable
when the if-conditional evaluates to true.

A typical usage is as follows:

    menuconfig BLOCK
            bool "Enable the block layer" if EXPERT
            default y

When EXPERT=n, the prompt is hidden, but this config entry is still
active, and BLOCK is set to its default value 'y'. When EXPERT=y, the
prompt is shown, making BLOCK a user-configurable option.

This usage is common throughout the kernel tree, but it has never worked
within a choice block.

[Test Code]

    config EXPERT
            bool "Allow expert users to modify more options"

    choice
            prompt "Choose" if EXPERT

    config A
            bool "A"

    config B
            bool "B"

    endchoice

[Result]

    # CONFIG_EXPERT is not set

When the prompt is hidden, the choice block should produce the default
without asking for the user's preference. Hence, the output should be:

    # CONFIG_EXPERT is not set
    CONFIG_A=y
    # CONFIG_B is not set

Removing unnecessary hacks fixes the issue.

This commit also changes the behavior of 'select' by choice members.

[Test Code 2]

    config MODULES
            def_bool y
            modules

    config DEP
            def_tristate m

    if DEP

    choice
            prompt "choose"

    config A
            bool "A"
            select C

    endchoice

    config B
            def_bool y
            select D

    endif

    config C
            tristate

    config D
            tristate

The current output is as follows:

    CONFIG_MODULES=y
    CONFIG_DEP=m
    CONFIG_A=y
    CONFIG_B=y
    CONFIG_C=y
    CONFIG_D=m

With this commit, the output will be changed as follows:

    CONFIG_MODULES=y
    CONFIG_DEP=m
    CONFIG_A=y
    CONFIG_B=y
    CONFIG_C=m
    CONFIG_D=m

CONFIG_C will be changed to 'm' because 'select C' will inherit the
dependency on DEP, which is 'm'.

This change is aligned with the behavior of 'select' outside a choice
block; 'select D' depends on DEP, therefore D is selected by (B && DEP).

Note:

With this commit, allmodconfig will set CONFIG_USB_ROLE_SWITCH to 'm'
instead of 'y'. I did not see any build regression with this change.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>

While Documentation/kbuild/kconfig-language.rst provides a brief
explanation, there are recurring confusions regarding the usage of a
prompt followed by 'if <expr>'. This conditional controls _only_ the
prompt.

A typical usage is as follows:

    menuconfig BLOCK
            bool "Enable the block layer" if EXPERT
            default y

When EXPERT=n, the prompt is hidden, but this config entry is still
active, and BLOCK is set to its default value 'y'. This is reasonable
because you are likely want to enable the block device support. When
EXPERT=y, the prompt is shown, allowing you to toggle BLOCK.

Please note that it is different from 'depends on EXPERT', which would
enable and disable the entire config entry.

However, this conditional prompt has never worked in a choice block.

The following two work in the same way: when EXPERT is disabled, the
choice block is entirely disabled.

[Test Code 1]

    choice
            prompt "choose" if EXPERT

    config A
            bool "A"

    config B
            bool "B"

    endchoice

[Test Code 2]

    choice
            prompt "choose"
            depends on EXPERT

    config A
            bool "A"

    config B
            bool "B"

    endchoice

I believe the first case should hide only the prompt, producing the
default:

   CONFIG_A=y
   # CONFIG_B is not set

The next commit will change (fix) the behavior of the conditional prompt
in choice blocks.

I see several choice blocks wrongly using a conditional prompt, where
'depends on' makes more sense.

To preserve the current behavior, this commit converts such misuses.

I did not touch the following entry in arch/x86/Kconfig:

    choice
            prompt "Memory split" if EXPERT
            default VMSPLIT_3G

This is truly the correct use of the conditional prompt; when EXPERT=n,
this choice block should silently select the reasonable VMSPLIT_3G,
although the resulting PAGE_OFFSET will not be affected anyway.

Presumably, the one in fs/jffs2/Kconfig is also correct, but I converted
it to 'depends on' to avoid any potential behavioral change.
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>

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 <masahiroy@kernel.org>

Choices and their members are associated via the P_CHOICE property.

Currently, prop_get_symbol(sym_get_choice_prop()) is used to obtain
the choice of the given choice member.

Replace it with sym_get_choice_menu(), which retrieves the choice
without relying on P_CHOICE.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>

Choices and their members are associated via the P_CHOICE property.

Currently, prop_get_symbol(sym_get_choice_prop()) is used to obtain
the choice of the given choice member.

Replace it with sym_get_choice_menu(), which retrieves the choice
without relying on P_CHOICE.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>

Choices and their members are associated via the P_CHOICE property.

Currently, prop_get_symbol(sym_get_choice_prop()) is used to obtain
the choice of the given choice member.

Replace it with sym_get_choice_menu(), which retrieves the choice
without relying on P_CHOICE.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>

All users of this macro have been converted. Remove it.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>

Choices and their members are associated via the P_CHOICE property.

Currently, sym_get_choice_prop() and expr_list_for_each_sym() are
used to iterate on choice members.

Replace them with menu_for_each_sub_entry(), which achieves the same
without relying on P_CHOICE.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>

Change the argument of sym_choice_default() to ease further cleanups.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>

This variable is unnecessary. Call conf_set_changed(true) directly.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>

sym_get_choice_value(menu->sym) is equivalent to sym_calc_choice(menu).

Convert all call sites of sym_get_choice_value() and then remove it.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>

Handling choices has always been in a PITA in Kconfig.

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

 - 422c809f ("kconfig: fix randomising choice entries in presence of KCONFIG_ALLCONFIG")
 - 23a5dfda ("Revert "kconfig: fix randomising choice entries in presence of KCONFIG_ALLCONFIG"")
 - 8357b485 ("kconfig: fix randomising choice entries in presence of KCONFIG_ALLCONFIG")
 - 490f1617 ("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 <masahiroy@kernel.org>

Import more macros from include/linux/list.h.

These will be used in the next commit.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>