xen/common/bitmap.c | 24 +++++++++++----------- xen/include/xen/bitmap.h | 43 ++++++++++++++++++++-------------------- 2 files changed, 34 insertions(+), 33 deletions(-)
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(-)
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);
}
--
2.30.2On 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
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
© 2016 - 2024 Red Hat, Inc.