[PATCH] kconfig: nconf: stop endless search-up loops

[PATCH] kconfig: nconf: stop endless search-up loops

[Mihai Moldovan]

If the user selects the very first entry in a page and performs a
search-up operation (e.g., via [/][a][Up Arrow]), nconf will never
terminate searching the page.

The reason is that in this case, the starting point will be set to -1,
which is then translated into (n - 1) (i.e., the last entry of the
page) and finally the search begins. This continues to work fine until
the index reaches 0, at which point it will be decremented to -1, but
not checked against the starting point right away. Instead, it's
wrapped around to the bottom again, after which the starting point
check occurs... and naturally fails.

We can easily avoid it by checking against the starting point directly
if the current index is -1 (which should be safe, since it's the only
magic value that can occur) and terminate the matching function.

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@ionic.de>
---
 scripts/kconfig/nconf.c | 9 +++++++++
 1 file changed, 9 insertions(+)

diff --git a/scripts/kconfig/nconf.c b/scripts/kconfig/nconf.c
index e0f965529166..92a5403d8afa 100644
--- a/scripts/kconfig/nconf.c
+++ b/scripts/kconfig/nconf.c
@@ -515,6 +515,15 @@ static int get_mext_match(const char *match_str, match_f flag)
 			--index;
 		else
 			++index;
+		/*
+		 * It's fine for index to become negative - think of an
+		 * initial value for match_start of 0 with a match direction
+		 * of up, eventually making it -1.
+		 *
+		 * Handle this as a special case.
+		 */
+		if ((-1 == index) && (index == match_start))
+			return -1;
 		index = (index + items_num) % items_num;
 		if (index == match_start)
 			return -1;
-- 
2.30.1

Re: [PATCH] kconfig: nconf: stop endless search-up loops

[Randy Dunlap]

On 3/27/21 5:01 AM, Mihai Moldovan wrote:
> If the user selects the very first entry in a page and performs a
> search-up operation (e.g., via [/][a][Up Arrow]), nconf will never
> terminate searching the page.
> 
> The reason is that in this case, the starting point will be set to -1,
> which is then translated into (n - 1) (i.e., the last entry of the
> page) and finally the search begins. This continues to work fine until
> the index reaches 0, at which point it will be decremented to -1, but
> not checked against the starting point right away. Instead, it's
> wrapped around to the bottom again, after which the starting point
> check occurs... and naturally fails.
> 
> We can easily avoid it by checking against the starting point directly
> if the current index is -1 (which should be safe, since it's the only
> magic value that can occur) and terminate the matching function.
> 
> 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@ionic.de>

Nice catch.

> ---
>  scripts/kconfig/nconf.c | 9 +++++++++
>  1 file changed, 9 insertions(+)
> 
> diff --git a/scripts/kconfig/nconf.c b/scripts/kconfig/nconf.c
> index e0f965529166..92a5403d8afa 100644
> --- a/scripts/kconfig/nconf.c
> +++ b/scripts/kconfig/nconf.c
> @@ -515,6 +515,15 @@ static int get_mext_match(const char *match_str, match_f flag)
>  			--index;
>  		else
>  			++index;
> +		/*
> +		 * It's fine for index to become negative - think of an
> +		 * initial value for match_start of 0 with a match direction
> +		 * of up, eventually making it -1.
> +		 *
> +		 * Handle this as a special case.
> +		 */
> +		if ((-1 == index) && (index == match_start))

checkpatch doesn't complain about this (and I wonder how it's missed), but
kernel style is (mostly) "constant goes on right hand side of comparison",
so
		if ((index == -1) &&

Otherwise LGTM.
Thanks.

> +			return -1;
>  		index = (index + items_num) % items_num;
>  		if (index == match_start)
>  			return -1;
> 


-- 
~Randy

Re: [PATCH] kconfig: nconf: stop endless search-up loops

[Mihai Moldovan]

[-- Attachment #1.1: Type: text/plain, Size: 735 bytes --]

* On 3/27/21 4:58 PM, Randy Dunlap wrote:
> On 3/27/21 5:01 AM, Mihai Moldovan wrote:
>> +		if ((-1 == index) && (index == match_start))
> 
> checkpatch doesn't complain about this (and I wonder how it's missed), but
> kernel style is (mostly) "constant goes on right hand side of comparison",
> so
> 		if ((index == -1) &&

I can naturally send a V2 with that swapped.

To my rationale: I made sure to use checkpatch, saw that it was accepted and
even went for a quick git grep -- '-1 ==', which likewise returned enough
results for me to call this consistent with the current code style.

Maybe those matches were just frowned-upon, but forgotten-to-be-critized
examples of this pattern being used.



Mihai



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 840 bytes --]

Re: [PATCH] kconfig: nconf: stop endless search-up loops

[Randy Dunlap]

On 3/27/21 3:12 PM, Mihai Moldovan wrote:
> * On 3/27/21 4:58 PM, Randy Dunlap wrote:
>> On 3/27/21 5:01 AM, Mihai Moldovan wrote:
>>> +		if ((-1 == index) && (index == match_start))
>>
>> checkpatch doesn't complain about this (and I wonder how it's missed), but
>> kernel style is (mostly) "constant goes on right hand side of comparison",
>> so
>> 		if ((index == -1) &&
> 
> I can naturally send a V2 with that swapped.
> 
> To my rationale: I made sure to use checkpatch, saw that it was accepted and
> even went for a quick git grep -- '-1 ==', which likewise returned enough
> results for me to call this consistent with the current code style.
> 
> Maybe those matches were just frowned-upon, but forgotten-to-be-critized
> examples of this pattern being used.

There is a test for it in checkpatch.pl but I also used checkpatch.pl
without it complaining, so I don't know what it takes to make the script
complain.

			if ($lead !~ /(?:$Operators|\.)\s*$/ &&
			    $to !~ /^(?:Constant|[A-Z_][A-Z0-9_]*)$/ &&
			    WARN("CONSTANT_COMPARISON",
				 "Comparisons should place the constant on the right side of the test\n" . $herecurr) &&

cheers.
-- 
~Randy

Re: [PATCH] kconfig: nconf: stop endless search-up loops

[Mihai Moldovan]

* On 3/27/21 11:26 PM, Randy Dunlap wrote:
> There is a test for it in checkpatch.pl but I also used checkpatch.pl
> without it complaining, so I don't know what it takes to make the script
> complain.
> 
> 			if ($lead !~ /(?:$Operators|\.)\s*$/ &&
> 			    $to !~ /^(?:Constant|[A-Z_][A-Z0-9_]*)$/ &&
> 			    WARN("CONSTANT_COMPARISON",
> 				 "Comparisons should place the constant on the right side of the test\n" . $herecurr) &&

There are multiple issues, err, "challenges" there:
  - literal "Constant" instead of "$Constant"
  - the left part is misinterpreted as an operation due to the minus sign
    (arithmetic operator)
  - $Constant is defined as "qr{$Float|$Binary|$Octal|$Hex|$Int}" (which is
    okay), but all these types do not include their negative range.

As far as I can tell, the latter is intentional. Making these types compatible
with negative values causes a lot of other places to break, so I'm not keen on
changing this.

The minus sign being misinterpreted as an operator is highly difficult to fix
in a sane manner. The original intention was to avoid misinterpreting
expressions like (var - CONSTANT real_op ...) as a constant-on-left expression
(and, more importantly, to not misfix it when --fix is given).

The general idea is sane and we probably shouldn't change that, but it would
be good to handle negative values as well.

At first, I was thinking of overriding this detection by checking if the
leading part matches "(-\s*$", which should only be true for negative values,
assuming that there is always an opening parenthesis as part of a conditional
statement/loop (if, while). After playing around with this and composing this
message for a few hours, it dawned on me that there can easily be free-
standing forms (for instance as part of for loops or assignment lines), so
that wouldn't cut it.

It really goes downhill from here.

I assume that false negatives are nuisances due to stylistic errors in the
code, but false positives actually harmful since a lot of them make code
review by maintainers very tedious.

So far, minus signs were always part of the leading capture group. I'd
actually like to have them in the constant capture group instead:

-		    $line =~ /^\+(.*)\b($Constant|[A-Z_][A-Z0-9_]*)\s*($Compare)\s*($LvalOrFunc)/) {
+		    $line =~ /^\+(.*)(-?\s*$Constant|[A-Z_][A-Z0-9_]*)\s*($Compare)\s*($LvalOrFunc)/) {

With that sorted, the next best thing I could come up with to weed out
preceding variables was this (which shouldn't influence non-negative
constants):

-			if ($lead !~ /(?:$Operators|\.)\s*$/ &&
+			if ($lead !~ /(?:$Operators|\.|[a-z])\s*$/ &&


There still are a lot of expressions that won't match this, like
"-1 + 0 == var" (i.e., "CONSTANT <arith_op> CONSTANT <op> ...") or
constellations like a simple "(CONSTANT) <op> ..." (e.g.,
"(1) == var").

This is all fuzzy and getting this right would involve moving away from
trying to make sense of C code with regular expressions in Perl, but actually
parsing it to extract the semantics. Not exactly something I'd like to do...

Thoughts on my workaround for this issue? Did I miss anything crucial or
introduce a new bug inadvertently?

Re: [PATCH] kconfig: nconf: stop endless search-up loops

[Joe Perches]

On Sun, 2021-03-28 at 11:27 +0200, Mihai Moldovan wrote:
> * On 3/27/21 11:26 PM, Randy Dunlap wrote:
> > There is a test for it in checkpatch.pl but I also used checkpatch.pl
> > without it complaining, so I don't know what it takes to make the script
> > complain.
> > 
> > 			if ($lead !~ /(?:$Operators|\.)\s*$/ &&
> > 			    $to !~ /^(?:Constant|[A-Z_][A-Z0-9_]*)$/ &&
> > 			    WARN("CONSTANT_COMPARISON",
> > 				 "Comparisons should place the constant on the right side of the test\n" . $herecurr) &&
> 
> There are multiple issues, err, "challenges" there:
>   - literal "Constant" instead of "$Constant"
>   - the left part is misinterpreted as an operation due to the minus sign
>     (arithmetic operator)
>   - $Constant is defined as "qr{$Float|$Binary|$Octal|$Hex|$Int}" (which is
>     okay), but all these types do not include their negative range.
> 
> As far as I can tell, the latter is intentional. Making these types compatible
> with negative values causes a lot of other places to break, so I'm not keen on
> changing this.
> 
> The minus sign being misinterpreted as an operator is highly difficult to fix
> in a sane manner. The original intention was to avoid misinterpreting
> expressions like (var - CONSTANT real_op ...) as a constant-on-left expression
> (and, more importantly, to not misfix it when --fix is given).
> 
> The general idea is sane and we probably shouldn't change that, but it would
> be good to handle negative values as well.
> 
> At first, I was thinking of overriding this detection by checking if the
> leading part matches "(-\s*$", which should only be true for negative values,
> assuming that there is always an opening parenthesis as part of a conditional
> statement/loop (if, while). After playing around with this and composing this
> message for a few hours, it dawned on me that there can easily be free-
> standing forms (for instance as part of for loops or assignment lines), so
> that wouldn't cut it.
> 
> It really goes downhill from here.
> 
> I assume that false negatives are nuisances due to stylistic errors in the
> code, but false positives actually harmful since a lot of them make code
> review by maintainers very tedious.
> 
> So far, minus signs were always part of the leading capture group. I'd
> actually like to have them in the constant capture group instead:
> 
> -		    $line =~ /^\+(.*)\b($Constant|[A-Z_][A-Z0-9_]*)\s*($Compare)\s*($LvalOrFunc)/) {
> +		    $line =~ /^\+(.*)(-?\s*$Constant|[A-Z_][A-Z0-9_]*)\s*($Compare)\s*($LvalOrFunc)/) {
> 
> With that sorted, the next best thing I could come up with to weed out
> preceding variables was this (which shouldn't influence non-negative
> constants):
> 
> -			if ($lead !~ /(?:$Operators|\.)\s*$/ &&
> +			if ($lead !~ /(?:$Operators|\.|[a-z])\s*$/ &&
> 
> 
> There still are a lot of expressions that won't match this, like
> "-1 + 0 == var" (i.e., "CONSTANT <arith_op> CONSTANT <op> ...") or
> constellations like a simple "(CONSTANT) <op> ..." (e.g.,
> "(1) == var").
> 
> This is all fuzzy and getting this right would involve moving away from
> trying to make sense of C code with regular expressions in Perl, but actually
> parsing it to extract the semantics. Not exactly something I'd like to do...
> 
> Thoughts on my workaround for this issue?

Making $Constant not include negative values was very intentional.

> Did I miss anything crucial or introduce a new bug inadvertently?

Not as far as I can tell from a trivial read.
My best guess as to what is best or necessary to do is nothing.
checkpatch isn't a real parser and never will be.

It can miss stuff.  It's imperfect.  It doesn't bother me.

Re: [PATCH] kconfig: nconf: stop endless search-up loops

[Joe Perches]

On Sat, 2021-03-27 at 15:26 -0700, Randy Dunlap wrote:
> On 3/27/21 3:12 PM, Mihai Moldovan wrote:
> > * On 3/27/21 4:58 PM, Randy Dunlap wrote:
> > > On 3/27/21 5:01 AM, Mihai Moldovan wrote:
> > > > +		if ((-1 == index) && (index == match_start))
> > > 
> > > checkpatch doesn't complain about this (and I wonder how it's missed), but
> > > kernel style is (mostly) "constant goes on right hand side of comparison",
> > > so
> > > 		if ((index == -1) &&
> > 
> > I can naturally send a V2 with that swapped.
> > 
> > To my rationale: I made sure to use checkpatch, saw that it was accepted and
> > even went for a quick git grep -- '-1 ==', which likewise returned enough
> > results for me to call this consistent with the current code style.
> > 
> > Maybe those matches were just frowned-upon, but forgotten-to-be-critized
> > examples of this pattern being used.
> 
> There is a test for it in checkpatch.pl but I also used checkpatch.pl
> without it complaining, so I don't know what it takes to make the script
> complain.
> 
> 			if ($lead !~ /(?:$Operators|\.)\s*$/ &&
> 			    $to !~ /^(?:Constant|[A-Z_][A-Z0-9_]*)$/ &&
> 			    WARN("CONSTANT_COMPARISON",
> 				 "Comparisons should place the constant on the right side of the test\n" . $herecurr) &&

Negative values aren't parsed well by the silly script as checkpatch
isn't a real parser.

Basically, checkpatch only recognizes positive ints as constants.

So it doesn't recognize uses like:

	a * -5 > b

It doesn't parse -5 as a negative constant.

Though here it does seem the line with
 			    $to !~ /^(?:Constant|[A-Z_][A-Z0-9_]*)$/ &&
should be
 			    $to !~ /^(?:$Constant|[A-Z_][A-Z0-9_]*)$/ &&

You are welcome to try to improve checkpatch, but it seems non-trivial
and a relatively uncommon use in the kernel, so I won't.

Most all of the existing uses seem to be in drivers/scsi/pm8001/pm8001_hwi.c

$ git grep -P 'if\s*\(\s*\-\d+\s*(?:<=|>=|==|<|>)' -- '*.[ch]'
drivers/media/i2c/msp3400-driver.c:		if (-1 == scarts[out][in + 1])
drivers/media/pci/bt8xx/bttv-driver.c:		if (-1 == formats[i].fourcc)
drivers/media/pci/saa7134/saa7134-tvaudio.c:	if (-1 == secondary)
drivers/media/pci/saa7146/mxb.c:			if (-1 == mxb_saa7740_init[i].length)
drivers/media/usb/s2255/s2255drv.c:		if (-1 == formats[i].fourcc)
drivers/net/ieee802154/mrf24j40.c:	} else if (-1000 >= mbm && mbm > -2000) {
drivers/net/ieee802154/mrf24j40.c:	} else if (-2000 >= mbm && mbm > -3000) {
drivers/net/ieee802154/mrf24j40.c:	} else if (-3000 >= mbm && mbm > -4000) {
drivers/net/wireless/broadcom/brcm80211/brcmsmac/phy/phy_lcn.c:	if (-1 == *gain_index) {
drivers/parisc/eisa_enumerator.c:		if (-1==init_slot(i+1, es)) {
drivers/scsi/pm8001/pm8001_hwi.c:	if (-1 == pm8001_bar4_shift(pm8001_ha,
drivers/scsi/pm8001/pm8001_hwi.c:	if (-1 == pm8001_bar4_shift(pm8001_ha,
drivers/scsi/pm8001/pm8001_hwi.c:	if (-1 == pm8001_bar4_shift(pm8001_ha,
drivers/scsi/pm8001/pm8001_hwi.c:	if (-1 == pm8001_bar4_shift(pm8001_ha,
drivers/scsi/pm8001/pm8001_hwi.c:		if (-1 == pm8001_bar4_shift(pm8001_ha, GSM_SM_BASE)) {
drivers/scsi/pm8001/pm8001_hwi.c:	if (-1 == check_fw_ready(pm8001_ha)) {
drivers/scsi/pm8001/pm8001_hwi.c:		if (-1 == pm8001_bar4_shift(pm8001_ha, GSM_SM_BASE)) {
drivers/scsi/pm8001/pm8001_hwi.c:		if (-1 == pm8001_bar4_shift(pm8001_ha, RB6_ACCESS_REG)) {
drivers/scsi/pm8001/pm8001_hwi.c:	if (-1 == pm8001_bar4_shift(pm8001_ha, MBIC_AAP1_ADDR_BASE)) {
drivers/scsi/pm8001/pm8001_hwi.c:	if (-1 == pm8001_bar4_shift(pm8001_ha, MBIC_IOP_ADDR_BASE)) {
drivers/scsi/pm8001/pm8001_hwi.c:	if (-1 == pm8001_bar4_shift(pm8001_ha, GSM_ADDR_BASE)) {
drivers/scsi/pm8001/pm8001_hwi.c:	if (-1 == pm8001_bar4_shift(pm8001_ha, GPIO_ADDR_BASE)) {
drivers/scsi/pm8001/pm8001_hwi.c:	if (-1 == pm8001_bar4_shift(pm8001_ha, SPC_TOP_LEVEL_ADDR_BASE)) {
drivers/scsi/pm8001/pm8001_hwi.c:	if (-1 == pm8001_bar4_shift(pm8001_ha, GSM_ADDR_BASE)) {
drivers/scsi/pm8001/pm8001_hwi.c:	if (-1 == pm8001_bar4_shift(pm8001_ha, SPC_TOP_LEVEL_ADDR_BASE)) {
drivers/scsi/pm8001/pm8001_hwi.c:				if (-1 == pm8001_bar4_shift(pm8001_ha,
drivers/scsi/pm8001/pm8001_hwi.c:				if (-1 == pm80xx_bar4_shift(pm8001_ha,
drivers/scsi/pm8001/pm8001_hwi.c:	if (-1 == pm8001_bar4_shift(pm8001_ha, 0))
drivers/scsi/pm8001/pm8001_sas.c:			if (-1 == pm8001_bar4_shift(pm8001_ha,
drivers/scsi/pm8001/pm80xx_hwi.c:	if (-1 == check_fw_ready(pm8001_ha)) {
drivers/scsi/pm8001/pm80xx_hwi.c:	if (-1 == check_fw_ready(pm8001_ha)) {
drivers/scsi/scsi_debug.c:	if (-1 == res)
drivers/scsi/scsi_debug.c:	if (-1 == ret) {
drivers/staging/fbtft/fb_agm1264k-fl.c:			if (-1 == coeff) {
fs/btrfs/check-integrity.c:		if (-1 == sf->i) {
fs/btrfs/check-integrity.c:		if (-1 == sf->i) {
fs/btrfs/check-integrity.c:		} else if (-1 == btrfsic_check_all_ref_blocks(state,
fs/isofs/util.c:		if (-52 <= tz && tz <= 52)
lib/test_bpf.c:		"JMP_JSLT_K: Signed jump: if (-2 < -1) return 1",
lib/test_bpf.c:		"JMP_JSLT_K: Signed jump: if (-1 < -1) return 0",
lib/test_bpf.c:		"JMP_JSGT_K: Signed jump: if (-1 > -2) return 1",
lib/test_bpf.c:		"JMP_JSGT_K: Signed jump: if (-1 > -1) return 0",
lib/test_bpf.c:		"JMP_JSLE_K: Signed jump: if (-2 <= -1) return 1",
lib/test_bpf.c:		"JMP_JSLE_K: Signed jump: if (-1 <= -1) return 1",
lib/test_bpf.c:		"JMP_JSGE_K: Signed jump: if (-1 >= -2) return 1",
lib/test_bpf.c:		"JMP_JSGE_K: Signed jump: if (-1 >= -1) return 1",
lib/test_bpf.c:		"JMP_JGT_K: Unsigned jump: if (-1 > 1) return 1",
lib/test_bpf.c:		"JMP_JSGT_X: Signed jump: if (-1 > -2) return 1",
lib/test_bpf.c:		"JMP_JSGT_X: Signed jump: if (-1 > -1) return 0",
lib/test_bpf.c:		"JMP_JSLT_X: Signed jump: if (-2 < -1) return 1",
lib/test_bpf.c:		"JMP_JSLT_X: Signed jump: if (-1 < -1) return 0",
lib/test_bpf.c:		"JMP_JSGE_X: Signed jump: if (-1 >= -2) return 1",
lib/test_bpf.c:		"JMP_JSGE_X: Signed jump: if (-1 >= -1) return 1",
lib/test_bpf.c:		"JMP_JSLE_X: Signed jump: if (-2 <= -1) return 1",
lib/test_bpf.c:		"JMP_JSLE_X: Signed jump: if (-1 <= -1) return 1",
lib/test_bpf.c:		"JMP_JGT_X: Unsigned jump: if (-1 > 1) return 1",
sound/pci/rme9652/hdspm.c:	if (-1 == val)
sound/usb/usx2y/usbusx2y.c:		if (-2 == us428ctls->CtlSnapShotLast) {
tools/testing/selftests/net/mptcp/mptcp_connect.c:		if (-1 == setsockopt(sock, SOL_SOCKET, SO_REUSEADDR, &one,

Re: [PATCH] kconfig: nconf: stop endless search-up loops

[Randy Dunlap]

On 3/28/21 3:32 AM, Joe Perches wrote:
> On Sat, 2021-03-27 at 15:26 -0700, Randy Dunlap wrote:
>> On 3/27/21 3:12 PM, Mihai Moldovan wrote:
>>> * On 3/27/21 4:58 PM, Randy Dunlap wrote:
>>>> On 3/27/21 5:01 AM, Mihai Moldovan wrote:
>>>>> +		if ((-1 == index) && (index == match_start))
>>>>
>>>> checkpatch doesn't complain about this (and I wonder how it's missed), but
>>>> kernel style is (mostly) "constant goes on right hand side of comparison",
>>>> so
>>>> 		if ((index == -1) &&
>>>
>>> I can naturally send a V2 with that swapped.
>>>
>>> To my rationale: I made sure to use checkpatch, saw that it was accepted and
>>> even went for a quick git grep -- '-1 ==', which likewise returned enough
>>> results for me to call this consistent with the current code style.
>>>
>>> Maybe those matches were just frowned-upon, but forgotten-to-be-critized
>>> examples of this pattern being used.
>>
>> There is a test for it in checkpatch.pl but I also used checkpatch.pl
>> without it complaining, so I don't know what it takes to make the script
>> complain.
>>
>> 			if ($lead !~ /(?:$Operators|\.)\s*$/ &&
>> 			    $to !~ /^(?:Constant|[A-Z_][A-Z0-9_]*)$/ &&
>> 			    WARN("CONSTANT_COMPARISON",
>> 				 "Comparisons should place the constant on the right side of the test\n" . $herecurr) &&
> 
> Negative values aren't parsed well by the silly script as checkpatch
> isn't a real parser.

Yes, I get that.

> Basically, checkpatch only recognizes positive ints as constants.

OK, good to know.

> So it doesn't recognize uses like:
> 
> 	a * -5 > b
> 
> It doesn't parse -5 as a negative constant.
> 
> Though here it does seem the line with
>  			    $to !~ /^(?:Constant|[A-Z_][A-Z0-9_]*)$/ &&
> should be
>  			    $to !~ /^(?:$Constant|[A-Z_][A-Z0-9_]*)$/ &&
> 
> You are welcome to try to improve checkpatch, but it seems non-trivial
> and a relatively uncommon use in the kernel, so I won't.

I get that too.

> Most all of the existing uses seem to be in drivers/scsi/pm8001/pm8001_hwi.c

[snip]


thanks.
-- 
~Randy

[PATCH v2] kconfig: nconf: stop endless search-up loops

[Mihai Moldovan]

If the user selects the very first entry in a page and performs a
search-up operation (e.g., via [/][a][Up Arrow]), nconf will never
terminate searching the page.

The reason is that in this case, the starting point will be set to -1,
which is then translated into (n - 1) (i.e., the last entry of the
page) and finally the search begins. This continues to work fine until
the index reaches 0, at which point it will be decremented to -1, but
not checked against the starting point right away. Instead, it's
wrapped around to the bottom again, after which the starting point
check occurs... and naturally fails.

We can easily avoid it by checking against the starting point directly
if the current index is -1 (which should be safe, since it's the only
magic value that can occur) and terminate the matching function.

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@ionic.de>
---
v2: swap constant in comparison to right side, as requested by
    Randy Dunlap <rdunlap@infradead.org>

 scripts/kconfig/nconf.c | 9 +++++++++
 1 file changed, 9 insertions(+)

diff --git a/scripts/kconfig/nconf.c b/scripts/kconfig/nconf.c
index e0f965529166..db0dc46bc5ee 100644
--- a/scripts/kconfig/nconf.c
+++ b/scripts/kconfig/nconf.c
@@ -515,6 +515,15 @@ static int get_mext_match(const char *match_str, match_f flag)
 			--index;
 		else
 			++index;
+		/*
+		 * It's fine for index to become negative - think of an
+		 * initial value for match_start of 0 with a match direction
+		 * of up, eventually making it -1.
+		 *
+		 * Handle this as a special case.
+		 */
+		if ((index == -1) && (index == match_start))
+			return -1;
 		index = (index + items_num) % items_num;
 		if (index == match_start)
 			return -1;
-- 
2.30.1

Re: [PATCH v2] kconfig: nconf: stop endless search-up loops

[Masahiro Yamada]

On Sun, Mar 28, 2021 at 6:52 PM Mihai Moldovan <ionic@ionic.de> wrote:
>
> If the user selects the very first entry in a page and performs a
> search-up operation (e.g., via [/][a][Up Arrow]), nconf will never
> terminate searching the page.
>
> The reason is that in this case, the starting point will be set to -1,
> which is then translated into (n - 1) (i.e., the last entry of the
> page) and finally the search begins. This continues to work fine until
> the index reaches 0, at which point it will be decremented to -1, but
> not checked against the starting point right away. Instead, it's
> wrapped around to the bottom again, after which the starting point
> check occurs... and naturally fails.
>
> We can easily avoid it by checking against the starting point directly
> if the current index is -1 (which should be safe, since it's the only
> magic value that can occur) and terminate the matching function.
>
> 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@ionic.de>
> ---
> v2: swap constant in comparison to right side, as requested by
>     Randy Dunlap <rdunlap@infradead.org>
>
>  scripts/kconfig/nconf.c | 9 +++++++++
>  1 file changed, 9 insertions(+)
>
> diff --git a/scripts/kconfig/nconf.c b/scripts/kconfig/nconf.c
> index e0f965529166..db0dc46bc5ee 100644
> --- a/scripts/kconfig/nconf.c
> +++ b/scripts/kconfig/nconf.c
> @@ -515,6 +515,15 @@ static int get_mext_match(const char *match_str, match_f flag)
>                         --index;
>                 else
>                         ++index;
> +               /*
> +                * It's fine for index to become negative - think of an
> +                * initial value for match_start of 0 with a match direction
> +                * of up, eventually making it -1.
> +                *
> +                * Handle this as a special case.
> +                */
> +               if ((index == -1) && (index == match_start))
> +                       return -1;

We know 'index' is -1 in the second comparison.
So, you can also write like this:

       if (match_start == -1 && index == -1)
                return -1;



But, it is not the correct fix, either.

The root cause of the bug is match_start
becoming -1.


The following is the correct way to fix the bug
without increasing the number of lines.



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)







-- 
Best Regards
Masahiro Yamada

Re: [PATCH v2] kconfig: nconf: stop endless search-up loops

[Mihai Moldovan]

* On 4/10/21 7:47 AM, Masahiro Yamada wrote:
> On Sun, Mar 28, 2021 at 6:52 PM Mihai Moldovan <ionic@ionic.de> wrote:
>> +               if ((index == -1) && (index == match_start))
>> +                       return -1;
> 
> We know 'index' is -1 in the second comparison.
> So, you can also write like this:
> 
>        if (match_start == -1 && index == -1)
>                 return -1;

I know, but I sided for the other form for semantic reasons - this more closely
directly describes what we actually care about (both being the same value and
either one being -1).


> But, it is not the correct fix, either.
> 
> The root cause of the bug is match_start
> becoming -1.
> 
> 
> The following is the correct way to fix the bug
> without increasing the number of lines.
> 
> 
> 
> diff --git a/scripts/kconfig/nconf.c b/scripts/kconfig/nconf.c
> index e0f965529166..af814b39b876 100644
> [...]
> +       match_start = (match_start + items_num) % items_num;
>         index = match_start;
> -       index = (index + items_num) % items_num;

This is probably more elegant and fixes two issues at the same time: match_start
becoming -1 or n (which is likewise invalid, but was implicitly handled through
the remainder operation).

No objections from my side.



Mihai

Re: [PATCH v2] kconfig: nconf: stop endless search-up loops

[Masahiro Yamada]

On Sat, Apr 10, 2021 at 4:00 PM Mihai Moldovan <ionic@ionic.de> wrote:
>
> * On 4/10/21 7:47 AM, Masahiro Yamada wrote:
> > On Sun, Mar 28, 2021 at 6:52 PM Mihai Moldovan <ionic@ionic.de> wrote:
> >> +               if ((index == -1) && (index == match_start))
> >> +                       return -1;
> >
> > We know 'index' is -1 in the second comparison.
> > So, you can also write like this:
> >
> >        if (match_start == -1 && index == -1)
> >                 return -1;
>
> I know, but I sided for the other form for semantic reasons - this more closely
> directly describes what we actually care about (both being the same value and
> either one being -1).
>
>
> > But, it is not the correct fix, either.
> >
> > The root cause of the bug is match_start
> > becoming -1.
> >
> >
> > The following is the correct way to fix the bug
> > without increasing the number of lines.
> >
> >
> >
> > diff --git a/scripts/kconfig/nconf.c b/scripts/kconfig/nconf.c
> > index e0f965529166..af814b39b876 100644
> > [...]
> > +       match_start = (match_start + items_num) % items_num;
> >         index = match_start;
> > -       index = (index + items_num) % items_num;
>
> This is probably more elegant and fixes two issues at the same time: match_start
> becoming -1 or n (which is likewise invalid, but was implicitly handled through
> the remainder operation).
>
> No objections from my side.


Could you send v3 please?

Then, I will apply it.



-- 
Best Regards
Masahiro Yamada

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

[Mihai Moldovan]

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@ionic.de>
---
v2: swap constant in comparison to right side, as requested by
    Randy Dunlap <rdunlap@infradead.org>
v3: reimplement as suggested by Masahiro Yamada <masahiroy@kernel.org>,
    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

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

[Masahiro Yamada]

On Thu, Apr 15, 2021 at 4:28 PM Mihai Moldovan <ionic@ionic.de> 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@ionic.de>
> ---

Applied to linux-kbuild. Thanks.


> v2: swap constant in comparison to right side, as requested by
>     Randy Dunlap <rdunlap@infradead.org>
> v3: reimplement as suggested by Masahiro Yamada <masahiroy@kernel.org>,
>     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

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

[Mihai Moldovan]

* On 4/16/21 7:40 AM, Masahiro Yamada wrote:
> Applied to linux-kbuild. Thanks.


Thank you for your review and input. :)



Mihai