diff mbox series

xen/bitmap: Consistently use unsigned bits values

Message ID 20240201103339.549307-1-andrew.cooper3@citrix.com (mailing list archive)
State New, archived
Headers show
Series xen/bitmap: Consistently use unsigned bits values | expand

Commit Message

Andrew Cooper Feb. 1, 2024, 10:33 a.m. UTC
Right now, most of the static inline helpers take an unsigned nbits quantity,
and most of the library functions take a signed quanity.  Because
BITMAP_LAST_WORD_MASK() is expressed as a divide, the compiler is forced to
emit two different paths to get the correct semantics for signed division.

Swap all signed bit-counts to being unsigned bit-counts for the simple cases.
This includes the return value of bitmap_weight().

Bloat-o-meter for a random x86 build reports:
  add/remove: 0/0 grow/shrink: 8/19 up/down: 167/-413 (-246)

which all comes from compiler not emitting "dead" logic paths for negative bit
counts.

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>

Found when investigating negative-shift UBSAN, because each of the library
functions ended up being instrumented.

There is much more wanting cleaning up here, but we have to start somewhere.
Some observations:

 * Various of the boolean-like return values have -1 for zero-length bitmaps.
   I can't spot any callers which care, so this seems like a waste.
 * bitmap_zero() and similar clear predate us switching to use
   __builtin_memset(), because there's no need for bitmap_switch().
 * Should we consolidate 'bits' vs 'nbits'?
 * The internals of these helpers want converting too.  Other helpers need
   more than just a parameter conversion.
---
 xen/common/bitmap.c      | 24 +++++++++++-----------
 xen/include/xen/bitmap.h | 43 ++++++++++++++++++++--------------------
 2 files changed, 34 insertions(+), 33 deletions(-)

Comments

Jan Beulich Feb. 1, 2024, 10:45 a.m. UTC | #1
On 01.02.2024 11:33, Andrew Cooper wrote:
> Right now, most of the static inline helpers take an unsigned nbits quantity,
> and most of the library functions take a signed quanity.  Because
> BITMAP_LAST_WORD_MASK() is expressed as a divide, the compiler is forced to
> emit two different paths to get the correct semantics for signed division.
> 
> Swap all signed bit-counts to being unsigned bit-counts for the simple cases.
> This includes the return value of bitmap_weight().
> 
> Bloat-o-meter for a random x86 build reports:
>   add/remove: 0/0 grow/shrink: 8/19 up/down: 167/-413 (-246)
> 
> which all comes from compiler not emitting "dead" logic paths for negative bit
> counts.
> 
> No functional change.
> 
> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>

Reviewed-by: Jan Beulich <jbeulich@suse.com>
albeit with a question at the bottom.

> There is much more wanting cleaning up here, but we have to start somewhere.
> Some observations:
> 
>  * Various of the boolean-like return values have -1 for zero-length bitmaps.
>    I can't spot any callers which care, so this seems like a waste.
>  * bitmap_zero() and similar clear predate us switching to use
>    __builtin_memset(), because there's no need for bitmap_switch().
>  * Should we consolidate 'bits' vs 'nbits'?

This looks desirable to me.

>  * The internals of these helpers want converting too.  Other helpers need
>    more than just a parameter conversion.

This may or may not relate to my question; it's not exactly clear what you
mean here.

> --- a/xen/include/xen/bitmap.h
> +++ b/xen/include/xen/bitmap.h
> @@ -66,25 +66,25 @@
>   * lib/bitmap.c provides these functions:
>   */
>  
> -extern int __bitmap_empty(const unsigned long *bitmap, int bits);
> -extern int __bitmap_full(const unsigned long *bitmap, int bits);
> -extern int __bitmap_equal(const unsigned long *bitmap1,
> -                	const unsigned long *bitmap2, int bits);
> -extern void __bitmap_complement(unsigned long *dst, const unsigned long *src,
> -			int bits);
> -extern void __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
> -			const unsigned long *bitmap2, int bits);
> -extern void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
> -			const unsigned long *bitmap2, int bits);
> -extern void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
> -			const unsigned long *bitmap2, int bits);
> -extern void __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
> -			const unsigned long *bitmap2, int bits);
> -extern int __bitmap_intersects(const unsigned long *bitmap1,
> -			const unsigned long *bitmap2, int bits);
> -extern int __bitmap_subset(const unsigned long *bitmap1,
> -			const unsigned long *bitmap2, int bits);
> -extern int __bitmap_weight(const unsigned long *bitmap, int bits);
> +int __bitmap_empty(const unsigned long *bitmap, unsigned int bits);
> +int __bitmap_full(const unsigned long *bitmap, unsigned int bits);
> +int __bitmap_equal(const unsigned long *bitmap1,
> +                   const unsigned long *bitmap2, unsigned int bits);
> +void __bitmap_complement(unsigned long *dst, const unsigned long *src,
> +                         unsigned int bits);
> +void __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
> +                  const unsigned long *bitmap2, unsigned int bits);
> +void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
> +                 const unsigned long *bitmap2, unsigned int bits);
> +void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
> +                  const unsigned long *bitmap2, unsigned int bits);
> +void __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
> +                     const unsigned long *bitmap2, unsigned int bits);
> +int __bitmap_intersects(const unsigned long *bitmap1,
> +                        const unsigned long *bitmap2, unsigned int bits);
> +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);

What about these two, and the subsequent (in the .c file at least)
bitmap_*_region()? That last remark above may mean you deliberately
left them out for now (which is okay - as you say, this is merely a
1st step).

Jan
Andrew Cooper Feb. 1, 2024, 10:53 a.m. UTC | #2
On 01/02/2024 10:45 am, Jan Beulich wrote:
> On 01.02.2024 11:33, Andrew Cooper wrote:
>> Right now, most of the static inline helpers take an unsigned nbits quantity,
>> and most of the library functions take a signed quanity.  Because
>> BITMAP_LAST_WORD_MASK() is expressed as a divide, the compiler is forced to
>> emit two different paths to get the correct semantics for signed division.
>>
>> Swap all signed bit-counts to being unsigned bit-counts for the simple cases.
>> This includes the return value of bitmap_weight().
>>
>> Bloat-o-meter for a random x86 build reports:
>>   add/remove: 0/0 grow/shrink: 8/19 up/down: 167/-413 (-246)
>>
>> which all comes from compiler not emitting "dead" logic paths for negative bit
>> counts.
>>
>> No functional change.
>>
>> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
> Reviewed-by: Jan Beulich <jbeulich@suse.com>

Thanks.

> albeit with a question at the bottom.
>
>> There is much more wanting cleaning up here, but we have to start somewhere.
>> Some observations:
>>
>>  * Various of the boolean-like return values have -1 for zero-length bitmaps.
>>    I can't spot any callers which care, so this seems like a waste.
>>  * bitmap_zero() and similar clear predate us switching to use
>>    __builtin_memset(), because there's no need for bitmap_switch().
>>  * Should we consolidate 'bits' vs 'nbits'?
> This looks desirable to me.
>
>>  * The internals of these helpers want converting too.  Other helpers need
>>    more than just a parameter conversion.
> This may or may not relate to my question; it's not exactly clear what you
> mean here.
>
>> --- a/xen/include/xen/bitmap.h
>> +++ b/xen/include/xen/bitmap.h
>> @@ -66,25 +66,25 @@
>>   * lib/bitmap.c provides these functions:
>>   */
>>  
>> -extern int __bitmap_empty(const unsigned long *bitmap, int bits);
>> -extern int __bitmap_full(const unsigned long *bitmap, int bits);
>> -extern int __bitmap_equal(const unsigned long *bitmap1,
>> -                	const unsigned long *bitmap2, int bits);
>> -extern void __bitmap_complement(unsigned long *dst, const unsigned long *src,
>> -			int bits);
>> -extern void __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
>> -			const unsigned long *bitmap2, int bits);
>> -extern void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
>> -			const unsigned long *bitmap2, int bits);
>> -extern void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
>> -			const unsigned long *bitmap2, int bits);
>> -extern void __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
>> -			const unsigned long *bitmap2, int bits);
>> -extern int __bitmap_intersects(const unsigned long *bitmap1,
>> -			const unsigned long *bitmap2, int bits);
>> -extern int __bitmap_subset(const unsigned long *bitmap1,
>> -			const unsigned long *bitmap2, int bits);
>> -extern int __bitmap_weight(const unsigned long *bitmap, int bits);
>> +int __bitmap_empty(const unsigned long *bitmap, unsigned int bits);
>> +int __bitmap_full(const unsigned long *bitmap, unsigned int bits);
>> +int __bitmap_equal(const unsigned long *bitmap1,
>> +                   const unsigned long *bitmap2, unsigned int bits);
>> +void __bitmap_complement(unsigned long *dst, const unsigned long *src,
>> +                         unsigned int bits);
>> +void __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
>> +                  const unsigned long *bitmap2, unsigned int bits);
>> +void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
>> +                 const unsigned long *bitmap2, unsigned int bits);
>> +void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
>> +                  const unsigned long *bitmap2, unsigned int bits);
>> +void __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
>> +                     const unsigned long *bitmap2, unsigned int bits);
>> +int __bitmap_intersects(const unsigned long *bitmap1,
>> +                        const unsigned long *bitmap2, unsigned int bits);
>> +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);
> What about these two, and the subsequent (in the .c file at least)
> bitmap_*_region()? That last remark above may mean you deliberately
> left them out for now (which is okay - as you say, this is merely a
> 1st step).

They want map->bitmap and int len -> unsigned int bits for consistency,
which is more than just a typechange.

I also wasn't totally certain of the correctness of the internal logic. 
I don't have time to investigate further in the immediate future, so
left it unchanged out of caution.

~Andrew
diff mbox series

Patch

diff --git a/xen/common/bitmap.c b/xen/common/bitmap.c
index 7d4551f78283..c57b35f0042c 100644
--- a/xen/common/bitmap.c
+++ b/xen/common/bitmap.c
@@ -55,7 +55,7 @@  static void clamp_last_byte(uint8_t *bp, unsigned int nbits)
 		bp[nbits/8] &= (1U << remainder) - 1;
 }
 
-int __bitmap_empty(const unsigned long *bitmap, int bits)
+int __bitmap_empty(const unsigned long *bitmap, unsigned int bits)
 {
 	int k, lim = bits/BITS_PER_LONG;
 	for (k = 0; k < lim; ++k)
@@ -70,7 +70,7 @@  int __bitmap_empty(const unsigned long *bitmap, int bits)
 }
 EXPORT_SYMBOL(__bitmap_empty);
 
-int __bitmap_full(const unsigned long *bitmap, int bits)
+int __bitmap_full(const unsigned long *bitmap, unsigned int bits)
 {
 	int k, lim = bits/BITS_PER_LONG;
 	for (k = 0; k < lim; ++k)
@@ -86,7 +86,7 @@  int __bitmap_full(const unsigned long *bitmap, int bits)
 EXPORT_SYMBOL(__bitmap_full);
 
 int __bitmap_equal(const unsigned long *bitmap1,
-		const unsigned long *bitmap2, int bits)
+                   const unsigned long *bitmap2, unsigned int bits)
 {
 	int k, lim = bits/BITS_PER_LONG;
 	for (k = 0; k < lim; ++k)
@@ -101,7 +101,7 @@  int __bitmap_equal(const unsigned long *bitmap1,
 }
 EXPORT_SYMBOL(__bitmap_equal);
 
-void __bitmap_complement(unsigned long *dst, const unsigned long *src, int bits)
+void __bitmap_complement(unsigned long *dst, const unsigned long *src, unsigned int bits)
 {
 	int k, lim = bits/BITS_PER_LONG;
 	for (k = 0; k < lim; ++k)
@@ -113,7 +113,7 @@  void __bitmap_complement(unsigned long *dst, const unsigned long *src, int bits)
 EXPORT_SYMBOL(__bitmap_complement);
 
 void __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
-				const unsigned long *bitmap2, int bits)
+                  const unsigned long *bitmap2, unsigned int bits)
 {
 	int k;
 	int nr = BITS_TO_LONGS(bits);
@@ -124,7 +124,7 @@  void __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
 EXPORT_SYMBOL(__bitmap_and);
 
 void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
-				const unsigned long *bitmap2, int bits)
+                 const unsigned long *bitmap2, unsigned int bits)
 {
 	int k;
 	int nr = BITS_TO_LONGS(bits);
@@ -135,7 +135,7 @@  void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
 EXPORT_SYMBOL(__bitmap_or);
 
 void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
-				const unsigned long *bitmap2, int bits)
+                  const unsigned long *bitmap2, unsigned int bits)
 {
 	int k;
 	int nr = BITS_TO_LONGS(bits);
@@ -146,7 +146,7 @@  void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
 EXPORT_SYMBOL(__bitmap_xor);
 
 void __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
-				const unsigned long *bitmap2, int bits)
+                     const unsigned long *bitmap2, unsigned int bits)
 {
 	int k;
 	int nr = BITS_TO_LONGS(bits);
@@ -157,7 +157,7 @@  void __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
 EXPORT_SYMBOL(__bitmap_andnot);
 
 int __bitmap_intersects(const unsigned long *bitmap1,
-				const unsigned long *bitmap2, int bits)
+                        const unsigned long *bitmap2, unsigned int bits)
 {
 	int k, lim = bits/BITS_PER_LONG;
 	for (k = 0; k < lim; ++k)
@@ -172,7 +172,7 @@  int __bitmap_intersects(const unsigned long *bitmap1,
 EXPORT_SYMBOL(__bitmap_intersects);
 
 int __bitmap_subset(const unsigned long *bitmap1,
-				const unsigned long *bitmap2, int bits)
+                    const unsigned long *bitmap2, unsigned int bits)
 {
 	int k, lim = bits/BITS_PER_LONG;
 	for (k = 0; k < lim; ++k)
@@ -187,7 +187,7 @@  int __bitmap_subset(const unsigned long *bitmap1,
 EXPORT_SYMBOL(__bitmap_subset);
 
 #if BITS_PER_LONG == 32
-int __bitmap_weight(const unsigned long *bitmap, int bits)
+unsigned int __bitmap_weight(const unsigned long *bitmap, unsigned int bits)
 {
 	int k, w = 0, lim = bits/BITS_PER_LONG;
 
@@ -200,7 +200,7 @@  int __bitmap_weight(const unsigned long *bitmap, int bits)
 	return w;
 }
 #else
-int __bitmap_weight(const unsigned long *bitmap, int bits)
+unsigned int __bitmap_weight(const unsigned long *bitmap, unsigned int bits)
 {
 	int k, w = 0, lim = bits/BITS_PER_LONG;
 
diff --git a/xen/include/xen/bitmap.h b/xen/include/xen/bitmap.h
index 657390e32ebc..b9f980e91930 100644
--- a/xen/include/xen/bitmap.h
+++ b/xen/include/xen/bitmap.h
@@ -66,25 +66,25 @@ 
  * lib/bitmap.c provides these functions:
  */
 
-extern int __bitmap_empty(const unsigned long *bitmap, int bits);
-extern int __bitmap_full(const unsigned long *bitmap, int bits);
-extern int __bitmap_equal(const unsigned long *bitmap1,
-                	const unsigned long *bitmap2, int bits);
-extern void __bitmap_complement(unsigned long *dst, const unsigned long *src,
-			int bits);
-extern void __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
-			const unsigned long *bitmap2, int bits);
-extern void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
-			const unsigned long *bitmap2, int bits);
-extern void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
-			const unsigned long *bitmap2, int bits);
-extern void __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
-			const unsigned long *bitmap2, int bits);
-extern int __bitmap_intersects(const unsigned long *bitmap1,
-			const unsigned long *bitmap2, int bits);
-extern int __bitmap_subset(const unsigned long *bitmap1,
-			const unsigned long *bitmap2, int bits);
-extern int __bitmap_weight(const unsigned long *bitmap, int bits);
+int __bitmap_empty(const unsigned long *bitmap, unsigned int bits);
+int __bitmap_full(const unsigned long *bitmap, unsigned int bits);
+int __bitmap_equal(const unsigned long *bitmap1,
+                   const unsigned long *bitmap2, unsigned int bits);
+void __bitmap_complement(unsigned long *dst, const unsigned long *src,
+                         unsigned int bits);
+void __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
+                  const unsigned long *bitmap2, unsigned int bits);
+void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
+                 const unsigned long *bitmap2, unsigned int bits);
+void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
+                  const unsigned long *bitmap2, unsigned int bits);
+void __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
+                     const unsigned long *bitmap2, unsigned int bits);
+int __bitmap_intersects(const unsigned long *bitmap1,
+                        const unsigned long *bitmap2, unsigned int bits);
+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);
 
@@ -117,7 +117,7 @@  static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)
 		memset(dst, 0, bitmap_bytes(nbits)));
 }
 
-static inline void bitmap_fill(unsigned long *dst, int nbits)
+static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)
 {
 	size_t nlongs = BITS_TO_LONGS(nbits);
 
@@ -224,7 +224,8 @@  static inline int bitmap_full(const unsigned long *src, unsigned int nbits)
 		return __bitmap_full(src, nbits));
 }
 
-static inline int bitmap_weight(const unsigned long *src, int nbits)
+static inline unsigned int bitmap_weight(const unsigned long *src,
+                                         unsigned int nbits)
 {
 	return __bitmap_weight(src, nbits);
 }