Re: [PATCH v3] kconfig: nconf: stop endless search loops

[Masahiro Yamada]

On Thu, Apr 15, 2021 at 4:28 PM Mihai Moldovan <ionic@xxxxxxxx> wrote:
>
> If the user selects the very first entry in a page and performs a
> search-up operation, or selects the very last entry in a page and
> performs a search-down operation that will not succeed (e.g., via
> [/]asdfzzz[Up Arrow]), nconf will never terminate searching the page.
>
> The reason is that in this case, the starting point will be set to -1
> or n, which is then translated into (n - 1) (i.e., the last entry of
> the page) or 0 (i.e., the first entry of the page) and finally the
> search begins. This continues to work fine until the index reaches 0 or
> (n - 1), at which point it will be decremented to -1 or incremented to
> n, but not checked against the starting point right away. Instead, it's
> wrapped around to the bottom or top again, after which the starting
> point check occurs... and naturally fails.
>
> My original implementation added another check for -1 before wrapping
> the running index variable around, but Masahiro Yamada pointed out that
> the actual issue is that the comparison point (starting point) exceeds
> bounds (i.e., the [0,n-1] interval) in the first place and that,
> instead, the starting point should be fixed.
>
> This has the welcome side-effect of also fixing the case where the
> starting point was n while searching down, which also lead to an
> infinite loop.
>
> OTOH, this code is now essentially all his work.
>
> Amazingly, nobody seems to have been hit by this for 11 years - or at
> the very least nobody bothered to debug and fix this.
>
> Signed-off-by: Mihai Moldovan <ionic@xxxxxxxx>
> ---

Applied to linux-kbuild. Thanks.


> v2: swap constant in comparison to right side, as requested by
>     Randy Dunlap <rdunlap@xxxxxxxxxxxxx>
> v3: reimplement as suggested by Masahiro Yamada <masahiroy@xxxxxxxxxx>,
>     which has the side-effect of also fixing endless looping in the
>     symmetric down-direction
>
>  scripts/kconfig/nconf.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/scripts/kconfig/nconf.c b/scripts/kconfig/nconf.c
> index e0f965529166..af814b39b876 100644
> --- a/scripts/kconfig/nconf.c
> +++ b/scripts/kconfig/nconf.c
> @@ -504,8 +504,8 @@ static int get_mext_match(const char *match_str, match_f flag)
>         else if (flag == FIND_NEXT_MATCH_UP)
>                 --match_start;
>
> +       match_start = (match_start + items_num) % items_num;
>         index = match_start;
> -       index = (index + items_num) % items_num;
>         while (true) {
>                 char *str = k_menu_items[index].str;
>                 if (strcasestr(str, match_str) != NULL)
> --
> 2.30.1
>


-- 
Best Regards
Masahiro Yamada