[PATCH] x86/bitmap: Even more signed-ness fixes

Andrew Cooper posted 1 patch 2 weeks, 5 days ago
Patches applied successfully (tree, apply log)
git fetch https://gitlab.com/xen-project/patchew/xen tags/patchew/20240205151413.1919983-1-andrew.cooper3@citrix.com
xen/common/bitmap.c      | 76 ++++++++++++++++++++++------------------
xen/include/xen/bitmap.h | 15 ++++----
2 files changed, 50 insertions(+), 41 deletions(-)
[PATCH] x86/bitmap: Even more signed-ness fixes
Posted by Andrew Cooper 2 weeks, 5 days ago
Further to commit 558e84b7ffec ("xen/bitmap: Consistently use unsigned bits
values"), it turns out that GCC's range analysis isn't good enough to notice
that 'bits / BITS_PER_LONG' is always within the unsigned range of k.

As a consequence, it re-sign-extends 'k' when calculating the pointer holding
'bitmap[k]' on each loop iteration.  Switch all internal variables to unsigned
int, which allows for better-still code generation.

Also clean up the prototypes for __bitmap_{set,clear} and the *_region()
helpers, along with the internal variables.

Bloat-o-meter for a random x86 build reports:
  add/remove: 0/0 grow/shrink: 0/10 up/down: 0/-277 (-277)

No functional change.

Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
---
CC: George Dunlap <George.Dunlap@citrix.com>
CC: Jan Beulich <JBeulich@suse.com>
CC: Stefano Stabellini <sstabellini@kernel.org>
CC: Wei Liu <wl@xen.org>
CC: Julien Grall <julien@xen.org>

Full bloat-o-meter details:

  add/remove: 0/0 grow/shrink: 0/10 up/down: 0/-277 (-277)
  Function                                     old     new   delta
  __bitmap_equal                               105     102      -3
  bitmap_find_free_region                      135     129      -6
  __bitmap_subset                              121     115      -6
  __bitmap_intersects                          105      99      -6
  __bitmap_full                                 91      85      -6
  __bitmap_empty                                90      84      -6
  bitmap_release_region                         68      45     -23
  bitmap_allocate_region                       104      72     -32
  __bitmap_clear                               136      43     -93
  __bitmap_set                                 136      40     -96
  Total: Before=4063985, After=4063708, chg -0.01%

Other functions have changes, but no net change.
---
 xen/common/bitmap.c      | 76 ++++++++++++++++++++++------------------
 xen/include/xen/bitmap.h | 15 ++++----
 2 files changed, 50 insertions(+), 41 deletions(-)

diff --git a/xen/common/bitmap.c b/xen/common/bitmap.c
index 9d9ff09f3dde..18e23e2f0e18 100644
--- a/xen/common/bitmap.c
+++ b/xen/common/bitmap.c
@@ -57,7 +57,8 @@ static void clamp_last_byte(uint8_t *bp, unsigned int nbits)
 
 int __bitmap_empty(const unsigned long *bitmap, unsigned int bits)
 {
-	int k, lim = bits/BITS_PER_LONG;
+	unsigned int k, lim = bits / BITS_PER_LONG;
+
 	for (k = 0; k < lim; ++k)
 		if (bitmap[k])
 			return 0;
@@ -72,7 +73,8 @@ EXPORT_SYMBOL(__bitmap_empty);
 
 int __bitmap_full(const unsigned long *bitmap, unsigned int bits)
 {
-	int k, lim = bits/BITS_PER_LONG;
+	unsigned int k, lim = bits / BITS_PER_LONG;
+
 	for (k = 0; k < lim; ++k)
 		if (~bitmap[k])
 			return 0;
@@ -88,7 +90,8 @@ EXPORT_SYMBOL(__bitmap_full);
 int __bitmap_equal(const unsigned long *bitmap1,
                    const unsigned long *bitmap2, unsigned int bits)
 {
-	int k, lim = bits/BITS_PER_LONG;
+	unsigned int k, lim = bits / BITS_PER_LONG;
+
 	for (k = 0; k < lim; ++k)
 		if (bitmap1[k] != bitmap2[k])
 			return 0;
@@ -103,7 +106,8 @@ EXPORT_SYMBOL(__bitmap_equal);
 
 void __bitmap_complement(unsigned long *dst, const unsigned long *src, unsigned int bits)
 {
-	int k, lim = bits/BITS_PER_LONG;
+	unsigned int k, lim = bits / BITS_PER_LONG;
+
 	for (k = 0; k < lim; ++k)
 		dst[k] = ~src[k];
 
@@ -115,8 +119,7 @@ EXPORT_SYMBOL(__bitmap_complement);
 void __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
                   const unsigned long *bitmap2, unsigned int bits)
 {
-	int k;
-	int nr = BITS_TO_LONGS(bits);
+	unsigned int k, nr = BITS_TO_LONGS(bits);
 
 	for (k = 0; k < nr; k++)
 		dst[k] = bitmap1[k] & bitmap2[k];
@@ -126,8 +129,7 @@ EXPORT_SYMBOL(__bitmap_and);
 void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
                  const unsigned long *bitmap2, unsigned int bits)
 {
-	int k;
-	int nr = BITS_TO_LONGS(bits);
+	unsigned int k, nr = BITS_TO_LONGS(bits);
 
 	for (k = 0; k < nr; k++)
 		dst[k] = bitmap1[k] | bitmap2[k];
@@ -137,8 +139,7 @@ EXPORT_SYMBOL(__bitmap_or);
 void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
                   const unsigned long *bitmap2, unsigned int bits)
 {
-	int k;
-	int nr = BITS_TO_LONGS(bits);
+	unsigned int k, nr = BITS_TO_LONGS(bits);
 
 	for (k = 0; k < nr; k++)
 		dst[k] = bitmap1[k] ^ bitmap2[k];
@@ -148,8 +149,7 @@ EXPORT_SYMBOL(__bitmap_xor);
 void __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
                      const unsigned long *bitmap2, unsigned int bits)
 {
-	int k;
-	int nr = BITS_TO_LONGS(bits);
+	unsigned int k, nr = BITS_TO_LONGS(bits);
 
 	for (k = 0; k < nr; k++)
 		dst[k] = bitmap1[k] & ~bitmap2[k];
@@ -159,7 +159,8 @@ EXPORT_SYMBOL(__bitmap_andnot);
 int __bitmap_intersects(const unsigned long *bitmap1,
                         const unsigned long *bitmap2, unsigned int bits)
 {
-	int k, lim = bits/BITS_PER_LONG;
+	unsigned int k, lim = bits / BITS_PER_LONG;
+
 	for (k = 0; k < lim; ++k)
 		if (bitmap1[k] & bitmap2[k])
 			return 1;
@@ -174,7 +175,8 @@ EXPORT_SYMBOL(__bitmap_intersects);
 int __bitmap_subset(const unsigned long *bitmap1,
                     const unsigned long *bitmap2, unsigned int bits)
 {
-	int k, lim = bits/BITS_PER_LONG;
+	unsigned int k, lim = bits / BITS_PER_LONG;
+
 	for (k = 0; k < lim; ++k)
 		if (bitmap1[k] & ~bitmap2[k])
 			return 0;
@@ -200,11 +202,11 @@ unsigned int __bitmap_weight(const unsigned long *bitmap, unsigned int bits)
 }
 EXPORT_SYMBOL(__bitmap_weight);
 
-void __bitmap_set(unsigned long *map, unsigned int start, int len)
+void __bitmap_set(unsigned long *bitmap, unsigned int start, unsigned int len)
 {
-	unsigned long *p = map + BIT_WORD(start);
+	unsigned long *p = bitmap + BIT_WORD(start);
 	const unsigned int size = start + len;
-	int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
+	unsigned int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
 	unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
 
 	while (len - bits_to_set >= 0) {
@@ -220,11 +222,11 @@ void __bitmap_set(unsigned long *map, unsigned int start, int len)
 	}
 }
 
-void __bitmap_clear(unsigned long *map, unsigned int start, int len)
+void __bitmap_clear(unsigned long *bitmap, unsigned int start, unsigned int len)
 {
-	unsigned long *p = map + BIT_WORD(start);
+	unsigned long *p = bitmap + BIT_WORD(start);
 	const unsigned int size = start + len;
-	int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
+	unsigned int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
 	unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
 
 	while (len - bits_to_clear >= 0) {
@@ -255,11 +257,11 @@ void __bitmap_clear(unsigned long *map, unsigned int start, int len)
  *
  * Returns either beginning of region or negative error
  */
-int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
+int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, unsigned int order)
 {
 	unsigned long mask;
-	int pages = 1 << order;
-	int i;
+	unsigned int pages = 1 << order;
+	unsigned int i;
 
 	if(pages > BITS_PER_LONG)
 		return -EINVAL;
@@ -270,8 +272,9 @@ int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
 
 	/* run up the bitmap pages bits at a time */
 	for (i = 0; i < bits; i += pages) {
-		int index = i/BITS_PER_LONG;
-		int offset = i - (index * BITS_PER_LONG);
+		unsigned int index = i / BITS_PER_LONG;
+		unsigned int offset = i - (index * BITS_PER_LONG);
+
 		if((bitmap[index] & (mask << offset)) == 0) {
 			/* set region in bimap */
 			bitmap[index] |= (mask << offset);
@@ -291,23 +294,26 @@ EXPORT_SYMBOL(bitmap_find_free_region);
  * This is the complement to __bitmap_find_free_region and releases
  * the found region (by clearing it in the bitmap).
  */
-void bitmap_release_region(unsigned long *bitmap, int pos, int order)
+void bitmap_release_region(unsigned long *bitmap, unsigned int pos,
+			   unsigned int order)
 {
-	int pages = 1 << order;
+	unsigned int pages = 1 << order;
 	unsigned long mask = (1ul << (pages - 1));
-	int index = pos/BITS_PER_LONG;
-	int offset = pos - (index * BITS_PER_LONG);
+	unsigned int index = pos / BITS_PER_LONG;
+	unsigned int offset = pos - (index * BITS_PER_LONG);
+
 	mask += mask - 1;
 	bitmap[index] &= ~(mask << offset);
 }
 EXPORT_SYMBOL(bitmap_release_region);
 
-int bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
+int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos,
+			   unsigned int order)
 {
-	int pages = 1 << order;
+	unsigned int pages = 1 << order;
 	unsigned long mask = (1ul << (pages - 1));
-	int index = pos/BITS_PER_LONG;
-	int offset = pos - (index * BITS_PER_LONG);
+	unsigned int index = pos/BITS_PER_LONG;
+	unsigned int offset = pos - (index * BITS_PER_LONG);
 
 	/* We don't do regions of pages > BITS_PER_LONG.  The
 	 * algorithm would be a simple look for multiple zeros in the
@@ -328,7 +334,7 @@ static void bitmap_long_to_byte(uint8_t *bp, const unsigned long *lp,
 				unsigned int nbits)
 {
 	unsigned long l;
-	int i, j, b;
+	unsigned int i, j, b;
 
 	for (i = 0, b = 0; nbits > 0; i++, b += sizeof(l)) {
 		l = lp[i];
@@ -345,7 +351,7 @@ static void bitmap_byte_to_long(unsigned long *lp, const uint8_t *bp,
 				unsigned int nbits)
 {
 	unsigned long l;
-	int i, j, b;
+	unsigned int i, j, b;
 
 	for (i = 0, b = 0; nbits > 0; i++, b += sizeof(l)) {
 		l = 0;
diff --git a/xen/include/xen/bitmap.h b/xen/include/xen/bitmap.h
index b9f980e91930..4e71b4350f59 100644
--- a/xen/include/xen/bitmap.h
+++ b/xen/include/xen/bitmap.h
@@ -85,12 +85,15 @@ int __bitmap_intersects(const unsigned long *bitmap1,
 int __bitmap_subset(const unsigned long *bitmap1,
                     const unsigned long *bitmap2, unsigned int bits);
 unsigned int __bitmap_weight(const unsigned long *bitmap, unsigned int bits);
-extern void __bitmap_set(unsigned long *map, unsigned int start, int len);
-extern void __bitmap_clear(unsigned long *map, unsigned int start, int len);
-
-extern int bitmap_find_free_region(unsigned long *bitmap, int bits, int order);
-extern void bitmap_release_region(unsigned long *bitmap, int pos, int order);
-extern int bitmap_allocate_region(unsigned long *bitmap, int pos, int order);
+void __bitmap_set(unsigned long *bitmap, unsigned int start, unsigned int len);
+void __bitmap_clear(unsigned long *bitmap, unsigned int start, unsigned int len);
+
+int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits,
+                            unsigned int order);
+void bitmap_release_region(unsigned long *bitmap, unsigned int pos,
+                           unsigned int order);
+int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos,
+                           unsigned int order);
 
 #define BITMAP_LAST_WORD_MASK(nbits)					\
 (									\
-- 
2.30.2
Re: [PATCH] x86/bitmap: Even more signed-ness fixes
Posted by Julien Grall 2 weeks, 5 days ago
Hi Andrew,

title: s/x86// as this is common code.

On 05/02/2024 15:14, Andrew Cooper wrote:
> Further to commit 558e84b7ffec ("xen/bitmap: Consistently use unsigned bits
> values"), it turns out that GCC's range analysis isn't good enough to notice
> that 'bits / BITS_PER_LONG' is always within the unsigned range of k.

I would suggest to add the compiler version. This would be helpful if we 
need to revisit this decision in the future. Althougth, I don't expect 
to be the case here (switching the bitmap functions to unsigned is a 
good move and IIRC was discussed during the MISRA meeting).

> 
> As a consequence, it re-sign-extends 'k' when calculating the pointer holding
> 'bitmap[k]' on each loop iteration.  Switch all internal variables to unsigned
> int, which allows for better-still code generation.
> 
> Also clean up the prototypes for __bitmap_{set,clear} and the *_region()
> helpers, along with the internal variables.
> 
> Bloat-o-meter for a random x86 build reports:
>    add/remove: 0/0 grow/shrink: 0/10 up/down: 0/-277 (-277)
> 
> No functional change.

I am not sure about this...

> 
> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>

[...]

> -int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
> +int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, unsigned int order)
>   {
>   	unsigned long mask;
> -	int pages = 1 << order;
> -	int i;
> +	unsigned int pages = 1 << order;
> +	unsigned int i;

... I think your other patch is fixing a latent bug you introduced here. 
Before hand, if bits was "negative", we would return -ENOMEM. Now if we 
pass 2GB or higher, we would go through the loop.

So I would fold the hunk from common/bitmap.c here.

>   
>   	if(pages > BITS_PER_LONG)
>   		return -EINVAL;

[...]

> -int bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
> +int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos,
> +			   unsigned int order)
>   {
> -	int pages = 1 << order;
> +	unsigned int pages = 1 << order;
>   	unsigned long mask = (1ul << (pages - 1));
> -	int index = pos/BITS_PER_LONG;
> -	int offset = pos - (index * BITS_PER_LONG);
> +	unsigned int index = pos/BITS_PER_LONG; 
NIT: While you modify the line, can you add a space before after / as 
you did above?

Cheers,

-- 
Julien Grall
Re: [PATCH] x86/bitmap: Even more signed-ness fixes
Posted by Jan Beulich 2 weeks, 4 days ago
On 05.02.2024 17:02, Julien Grall wrote:
> On 05/02/2024 15:14, Andrew Cooper wrote:
>> -int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
>> +int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, unsigned int order)
>>   {
>>   	unsigned long mask;
>> -	int pages = 1 << order;
>> -	int i;
>> +	unsigned int pages = 1 << order;
>> +	unsigned int i;
> 
> ... I think your other patch is fixing a latent bug you introduced here. 
> Before hand, if bits was "negative", we would return -ENOMEM. Now if we 
> pass 2GB or higher, we would go through the loop.
> 
> So I would fold the hunk from common/bitmap.c here.
> 
>>   
>>   	if(pages > BITS_PER_LONG)
>>   		return -EINVAL;
> 
> [...]
> 
>> -int bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
>> +int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos,
>> +			   unsigned int order)
>>   {
>> -	int pages = 1 << order;
>> +	unsigned int pages = 1 << order;
>>   	unsigned long mask = (1ul << (pages - 1));
>> -	int index = pos/BITS_PER_LONG;
>> -	int offset = pos - (index * BITS_PER_LONG);
>> +	unsigned int index = pos/BITS_PER_LONG; 
> NIT: While you modify the line, can you add a space before after / as 
> you did above?

Instead of any of this - how about we finally purge this dead code? All
of bitmap_*_region() were dead in 3.2 (and perhaps even before), and they
are still dead.

Jan