xen/common/bitmap.c | 76 ++++++++++++++++++++++------------------ xen/include/xen/bitmap.h | 15 ++++---- 2 files changed, 50 insertions(+), 41 deletions(-)
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.2Hi 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
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
© 2016 - 2024 Red Hat, Inc.