[PATCH] xen/bitops: Fix break with in a for_each_set_bit() loop

[PATCH] xen/bitops: Fix break with in a for_each_set_bit() loop

[Andrew Cooper]

for_each_set_bit()'s use of a double for loop had an accidental bug with a
break in the inner loop leading to an infinite outer loop.

Adjust for_each_set_bit() to avoid this behaviour, and add extend
test_for_each_set_bit() with a test case for this.

Fixes: ed26376f20bf ("xen/bitops: Introduce for_each_set_bit()")
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
---
CC: Jan Beulich <JBeulich@suse.com>
CC: Roger Pau Monné <roger.pau@citrix.com>
CC: Frediano Ziglio <frediano.ziglio@cloud.com>
CC: Stefano Stabellini <sstabellini@kernel.org>
CC: Julien Grall <julien@xen.org>

Both GCC and Clang seem happy with this, even at -O1:

  https://godbolt.org/z/o6ohjrzsY
---
 xen/common/bitops.c      | 16 ++++++++++++++++
 xen/include/xen/bitops.h |  2 +-
 2 files changed, 17 insertions(+), 1 deletion(-)

diff --git a/xen/common/bitops.c b/xen/common/bitops.c
index 91ae961440af..0edd62d25c28 100644
--- a/xen/common/bitops.c
+++ b/xen/common/bitops.c
@@ -110,6 +110,22 @@ static void __init test_for_each_set_bit(void)
 
     if ( ull != ull_res )
         panic("for_each_set_bit(uint64) expected %#"PRIx64", got %#"PRIx64"\n", ull, ull_res);
+
+    /* Check that we break from the middle of the loop */
+    ui = HIDE(0x80001008U);
+    ui_res = 0;
+    for_each_set_bit ( i, ui )
+    {
+        static __initdata unsigned int count;
+
+        if ( count++ > 1 )
+            break;
+
+        ui_res |= 1U << i;
+    }
+
+    if ( ui_res != 0x1008 )
+        panic("for_each_set_bit(break) expected 0x1008, got %#x\n", ui_res);
 }
 
 static void __init test_multiple_bits_set(void)
diff --git a/xen/include/xen/bitops.h b/xen/include/xen/bitops.h
index 79615fb89d04..448b2d3e0937 100644
--- a/xen/include/xen/bitops.h
+++ b/xen/include/xen/bitops.h
@@ -299,7 +299,7 @@ static always_inline attr_const unsigned int fls64(uint64_t x)
  * A copy of @val is taken internally.
  */
 #define for_each_set_bit(iter, val)                     \
-    for ( typeof(val) __v = (val); __v; )               \
+    for ( typeof(val) __v = (val); __v; __v = 0 )       \
         for ( unsigned int (iter);                      \
               __v && ((iter) = ffs_g(__v) - 1, true);   \
               __v &= __v - 1 )

base-commit: e0058760a0c7935ad0690d8b9babb9050eceedf0
-- 
2.39.5

Re: [PATCH] xen/bitops: Fix break with in a for_each_set_bit() loop

[Frediano Ziglio]

On Thu, Nov 21, 2024 at 2:50 PM Andrew Cooper <andrew.cooper3@citrix.com> wrote:
>
> for_each_set_bit()'s use of a double for loop had an accidental bug with a
> break in the inner loop leading to an infinite outer loop.
>
> Adjust for_each_set_bit() to avoid this behaviour, and add extend
> test_for_each_set_bit() with a test case for this.
>
> Fixes: ed26376f20bf ("xen/bitops: Introduce for_each_set_bit()")
> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
> ---
> CC: Jan Beulich <JBeulich@suse.com>
> CC: Roger Pau Monné <roger.pau@citrix.com>
> CC: Frediano Ziglio <frediano.ziglio@cloud.com>
> CC: Stefano Stabellini <sstabellini@kernel.org>
> CC: Julien Grall <julien@xen.org>
>
> Both GCC and Clang seem happy with this, even at -O1:
>
>   https://godbolt.org/z/o6ohjrzsY
> ---
>  xen/common/bitops.c      | 16 ++++++++++++++++
>  xen/include/xen/bitops.h |  2 +-
>  2 files changed, 17 insertions(+), 1 deletion(-)
>
> diff --git a/xen/common/bitops.c b/xen/common/bitops.c
> index 91ae961440af..0edd62d25c28 100644
> --- a/xen/common/bitops.c
> +++ b/xen/common/bitops.c
> @@ -110,6 +110,22 @@ static void __init test_for_each_set_bit(void)
>
>      if ( ull != ull_res )
>          panic("for_each_set_bit(uint64) expected %#"PRIx64", got %#"PRIx64"\n", ull, ull_res);
> +
> +    /* Check that we break from the middle of the loop */
> +    ui = HIDE(0x80001008U);
> +    ui_res = 0;
> +    for_each_set_bit ( i, ui )
> +    {
> +        static __initdata unsigned int count;
> +
> +        if ( count++ > 1 )
> +            break;
> +
> +        ui_res |= 1U << i;
> +    }
> +
> +    if ( ui_res != 0x1008 )
> +        panic("for_each_set_bit(break) expected 0x1008, got %#x\n", ui_res);
>  }
>
>  static void __init test_multiple_bits_set(void)
> diff --git a/xen/include/xen/bitops.h b/xen/include/xen/bitops.h
> index 79615fb89d04..448b2d3e0937 100644
> --- a/xen/include/xen/bitops.h
> +++ b/xen/include/xen/bitops.h
> @@ -299,7 +299,7 @@ static always_inline attr_const unsigned int fls64(uint64_t x)
>   * A copy of @val is taken internally.
>   */
>  #define for_each_set_bit(iter, val)                     \
> -    for ( typeof(val) __v = (val); __v; )               \
> +    for ( typeof(val) __v = (val); __v; __v = 0 )       \
>          for ( unsigned int (iter);                      \
>                __v && ((iter) = ffs_g(__v) - 1, true);   \
>                __v &= __v - 1 )
>
> base-commit: e0058760a0c7935ad0690d8b9babb9050eceedf0

Not a fun of static variables but it's just in the test,

Reviewed-by: Frediano Ziglio <frediano.ziglio@cloud.com>

Frediano

Re: [PATCH] xen/bitops: Fix break with in a for_each_set_bit() loop

[Andrew Cooper]

On 21/11/2024 3:19 pm, Frediano Ziglio wrote:
> On Thu, Nov 21, 2024 at 2:50 PM Andrew Cooper <andrew.cooper3@citrix.com> wrote:
>> for_each_set_bit()'s use of a double for loop had an accidental bug with a
>> break in the inner loop leading to an infinite outer loop.
>>
>> Adjust for_each_set_bit() to avoid this behaviour, and add extend
>> test_for_each_set_bit() with a test case for this.
>>
>> Fixes: ed26376f20bf ("xen/bitops: Introduce for_each_set_bit()")
>> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
>> ---
>> CC: Jan Beulich <JBeulich@suse.com>
>> CC: Roger Pau Monné <roger.pau@citrix.com>
>> CC: Frediano Ziglio <frediano.ziglio@cloud.com>
>> CC: Stefano Stabellini <sstabellini@kernel.org>
>> CC: Julien Grall <julien@xen.org>
>>
>> Both GCC and Clang seem happy with this, even at -O1:
>>
>>   https://godbolt.org/z/o6ohjrzsY
>> ---
>>  xen/common/bitops.c      | 16 ++++++++++++++++
>>  xen/include/xen/bitops.h |  2 +-
>>  2 files changed, 17 insertions(+), 1 deletion(-)
>>
>> diff --git a/xen/common/bitops.c b/xen/common/bitops.c
>> index 91ae961440af..0edd62d25c28 100644
>> --- a/xen/common/bitops.c
>> +++ b/xen/common/bitops.c
>> @@ -110,6 +110,22 @@ static void __init test_for_each_set_bit(void)
>>
>>      if ( ull != ull_res )
>>          panic("for_each_set_bit(uint64) expected %#"PRIx64", got %#"PRIx64"\n", ull, ull_res);
>> +
>> +    /* Check that we break from the middle of the loop */
>> +    ui = HIDE(0x80001008U);
>> +    ui_res = 0;
>> +    for_each_set_bit ( i, ui )
>> +    {
>> +        static __initdata unsigned int count;
>> +
>> +        if ( count++ > 1 )
>> +            break;
>> +
>> +        ui_res |= 1U << i;
>> +    }
>> +
>> +    if ( ui_res != 0x1008 )
>> +        panic("for_each_set_bit(break) expected 0x1008, got %#x\n", ui_res);
>>  }
>>
>>  static void __init test_multiple_bits_set(void)
>> diff --git a/xen/include/xen/bitops.h b/xen/include/xen/bitops.h
>> index 79615fb89d04..448b2d3e0937 100644
>> --- a/xen/include/xen/bitops.h
>> +++ b/xen/include/xen/bitops.h
>> @@ -299,7 +299,7 @@ static always_inline attr_const unsigned int fls64(uint64_t x)
>>   * A copy of @val is taken internally.
>>   */
>>  #define for_each_set_bit(iter, val)                     \
>> -    for ( typeof(val) __v = (val); __v; )               \
>> +    for ( typeof(val) __v = (val); __v; __v = 0 )       \
>>          for ( unsigned int (iter);                      \
>>                __v && ((iter) = ffs_g(__v) - 1, true);   \
>>                __v &= __v - 1 )
>>
>> base-commit: e0058760a0c7935ad0690d8b9babb9050eceedf0
> Not a fun of static variables but it's just in the test,

Oh, I guess I can do it with just a local variable.  Incremental diff is:

@@ -86,7 +86,7 @@ static void __init test_fls(void)
 
 static void __init test_for_each_set_bit(void)
 {
-    unsigned int  ui,  ui_res = 0;
+    unsigned int  ui,  ui_res = 0, tmp;
     unsigned long ul,  ul_res = 0;
     uint64_t      ull, ull_res = 0;
 
@@ -113,12 +113,11 @@ static void __init test_for_each_set_bit(void)
 
     /* Check that we break from the middle of the loop */
     ui = HIDE(0x80001008U);
+    tmp = 0;
     ui_res = 0;
     for_each_set_bit ( i, ui )
     {
-        static __initdata unsigned int count;
-
-        if ( count++ > 1 )
+        if ( tmp++ > 1 )
             break;
 
         ui_res |= 1U << i;


> Reviewed-by: Frediano Ziglio <frediano.ziglio@cloud.com>

Thanks.  This turns out to be a whole lot easier than I was fearing.

~Andrew

Re: [PATCH] xen/bitops: Fix break with in a for_each_set_bit() loop

[Jan Beulich]

On 21.11.2024 15:50, Andrew Cooper wrote:
> for_each_set_bit()'s use of a double for loop had an accidental bug with a
> break in the inner loop leading to an infinite outer loop.
> 
> Adjust for_each_set_bit() to avoid this behaviour, and add extend
> test_for_each_set_bit() with a test case for this.
> 
> Fixes: ed26376f20bf ("xen/bitops: Introduce for_each_set_bit()")
> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>

Reviewed-by: Jan Beulich <jbeulich@suse.com>

Nit: In the title, isn't it supposed to be "within"? And in the 2md paragraph
there looks to be a stray "add".

Jan

Re: [PATCH] xen/bitops: Fix break with in a for_each_set_bit() loop

[Andrew Cooper]

On 21/11/2024 4:07 pm, Jan Beulich wrote:
> On 21.11.2024 15:50, Andrew Cooper wrote:
>> for_each_set_bit()'s use of a double for loop had an accidental bug with a
>> break in the inner loop leading to an infinite outer loop.
>>
>> Adjust for_each_set_bit() to avoid this behaviour, and add extend
>> test_for_each_set_bit() with a test case for this.
>>
>> Fixes: ed26376f20bf ("xen/bitops: Introduce for_each_set_bit()")
>> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
> Reviewed-by: Jan Beulich <jbeulich@suse.com>

Thanks.

>
> Nit: In the title, isn't it supposed to be "within"?

Yes, already noticed and fixed.

>  And in the 2md paragraph
> there looks to be a stray "add".

Will fix.

~Andrew

Re: [PATCH] xen/bitops: Fix break with in a for_each_set_bit() loop

[Roger Pau Monné]

On Thu, Nov 21, 2024 at 02:50:00PM +0000, Andrew Cooper wrote:
> for_each_set_bit()'s use of a double for loop had an accidental bug with a
> break in the inner loop leading to an infinite outer loop.
> 
> Adjust for_each_set_bit() to avoid this behaviour, and add extend
> test_for_each_set_bit() with a test case for this.
> 
> Fixes: ed26376f20bf ("xen/bitops: Introduce for_each_set_bit()")
> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>

Reviewed-by: Roger Pau Monné <roger.pau@citrix.com>

I have to admit it took me a while to understand what was going on.

Subject should likely be "Fix break usage in for_each_set_bit() loop"

Or similar?

> ---
> CC: Jan Beulich <JBeulich@suse.com>
> CC: Roger Pau Monné <roger.pau@citrix.com>
> CC: Frediano Ziglio <frediano.ziglio@cloud.com>
> CC: Stefano Stabellini <sstabellini@kernel.org>
> CC: Julien Grall <julien@xen.org>
> 
> Both GCC and Clang seem happy with this, even at -O1:
> 
>   https://godbolt.org/z/o6ohjrzsY
> ---
>  xen/common/bitops.c      | 16 ++++++++++++++++
>  xen/include/xen/bitops.h |  2 +-
>  2 files changed, 17 insertions(+), 1 deletion(-)
> 
> diff --git a/xen/common/bitops.c b/xen/common/bitops.c
> index 91ae961440af..0edd62d25c28 100644
> --- a/xen/common/bitops.c
> +++ b/xen/common/bitops.c
> @@ -110,6 +110,22 @@ static void __init test_for_each_set_bit(void)
>  
>      if ( ull != ull_res )
>          panic("for_each_set_bit(uint64) expected %#"PRIx64", got %#"PRIx64"\n", ull, ull_res);
> +
> +    /* Check that we break from the middle of the loop */
> +    ui = HIDE(0x80001008U);
> +    ui_res = 0;
> +    for_each_set_bit ( i, ui )
> +    {
> +        static __initdata unsigned int count;

Preferably as you suggested without the static variable, I may suggest
that you use ui_tmp instead of plain tmp as the variable name?

Thanks, Roger.

Re: [PATCH] xen/bitops: Fix break with in a for_each_set_bit() loop

[Andrew Cooper]

On 21/11/2024 4:32 pm, Roger Pau Monné wrote:
> On Thu, Nov 21, 2024 at 02:50:00PM +0000, Andrew Cooper wrote:
>> for_each_set_bit()'s use of a double for loop had an accidental bug with a
>> break in the inner loop leading to an infinite outer loop.
>>
>> Adjust for_each_set_bit() to avoid this behaviour, and add extend
>> test_for_each_set_bit() with a test case for this.
>>
>> Fixes: ed26376f20bf ("xen/bitops: Introduce for_each_set_bit()")
>> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
> Reviewed-by: Roger Pau Monné <roger.pau@citrix.com>

Thanks.

>
> I have to admit it took me a while to understand what was going on.
>
> Subject should likely be "Fix break usage in for_each_set_bit() loop"
>
> Or similar?

I'll adjust.

>
>> ---
>> CC: Jan Beulich <JBeulich@suse.com>
>> CC: Roger Pau Monné <roger.pau@citrix.com>
>> CC: Frediano Ziglio <frediano.ziglio@cloud.com>
>> CC: Stefano Stabellini <sstabellini@kernel.org>
>> CC: Julien Grall <julien@xen.org>
>>
>> Both GCC and Clang seem happy with this, even at -O1:
>>
>>   https://godbolt.org/z/o6ohjrzsY
>> ---
>>  xen/common/bitops.c      | 16 ++++++++++++++++
>>  xen/include/xen/bitops.h |  2 +-
>>  2 files changed, 17 insertions(+), 1 deletion(-)
>>
>> diff --git a/xen/common/bitops.c b/xen/common/bitops.c
>> index 91ae961440af..0edd62d25c28 100644
>> --- a/xen/common/bitops.c
>> +++ b/xen/common/bitops.c
>> @@ -110,6 +110,22 @@ static void __init test_for_each_set_bit(void)
>>  
>>      if ( ull != ull_res )
>>          panic("for_each_set_bit(uint64) expected %#"PRIx64", got %#"PRIx64"\n", ull, ull_res);
>> +
>> +    /* Check that we break from the middle of the loop */
>> +    ui = HIDE(0x80001008U);
>> +    ui_res = 0;
>> +    for_each_set_bit ( i, ui )
>> +    {
>> +        static __initdata unsigned int count;
> Preferably as you suggested without the static variable, I may suggest
> that you use ui_tmp instead of plain tmp as the variable name?

For this, I'd prefer not to.

For ui, ul and ull, there are a pair of variables with precise usage.

This is one random number that gets as far as 2.  And it's test code.

~Andrew

Re: [PATCH] xen/bitops: Fix break with in a for_each_set_bit() loop

[Roger Pau Monné]

On Thu, Nov 21, 2024 at 05:35:16PM +0000, Andrew Cooper wrote:
> On 21/11/2024 4:32 pm, Roger Pau Monné wrote:
> > On Thu, Nov 21, 2024 at 02:50:00PM +0000, Andrew Cooper wrote:
> >> diff --git a/xen/common/bitops.c b/xen/common/bitops.c
> >> index 91ae961440af..0edd62d25c28 100644
> >> --- a/xen/common/bitops.c
> >> +++ b/xen/common/bitops.c
> >> @@ -110,6 +110,22 @@ static void __init test_for_each_set_bit(void)
> >>  
> >>      if ( ull != ull_res )
> >>          panic("for_each_set_bit(uint64) expected %#"PRIx64", got %#"PRIx64"\n", ull, ull_res);
> >> +
> >> +    /* Check that we break from the middle of the loop */
> >> +    ui = HIDE(0x80001008U);
> >> +    ui_res = 0;
> >> +    for_each_set_bit ( i, ui )
> >> +    {
> >> +        static __initdata unsigned int count;
> > Preferably as you suggested without the static variable, I may suggest
> > that you use ui_tmp instead of plain tmp as the variable name?
> 
> For this, I'd prefer not to.
> 
> For ui, ul and ull, there are a pair of variables with precise usage.
> 
> This is one random number that gets as far as 2.  And it's test code.

My suggestion was on the basis that we might need to add more 'tmp'
variables of different types in the future maybe?  No strong opinion
anyway, I'm fine if you prefer to leave as plain 'tmp'.

Thanks, Roger.