Skip to contentSkip to conversation

bitmap: get last word mask from nr directly

PATCH RESEND Superseded Wei Yang 2 participants 5 messages Jul 17, 2019

v1 of 3 Superseded Latest is v3 →

lore
Share & tools
lore

Wei Yang

author
#0 lore raw

PATCH RESEND 1/1 bitmap: get last word mask from nr directly

The value left in nr is the number of bits for the last word, which could be calculate the last word mask directly.

Remove the unnecessary size.

---
resend with wider audience

---
 util/bitmap.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)
util/bitmap.c +2 -4
index cb618c65a5..5aa60b8717 100644
@@ -160,7 +160,6 @@ int slow_bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
 void bitmap_set(unsigned long *map, long start, long nr)
 {
     unsigned long *p = map + BIT_WORD(start);
-    const long size = start + nr;
     int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
     unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
 
@@ -174,7 +173,7 @@ void bitmap_set(unsigned long *map, long start, long nr)
         p++;
     }
     if (nr) {
-        mask_to_set &= BITMAP_LAST_WORD_MASK(size);
+        mask_to_set &= BITMAP_LAST_WORD_MASK(nr);
         *p |= mask_to_set;
     }
 }
@@ -221,7 +220,6 @@ void bitmap_set_atomic(unsigned long *map, long start, long nr)
 void bitmap_clear(unsigned long *map, long start, long nr)
 {
     unsigned long *p = map + BIT_WORD(start);
-    const long size = start + nr;
     int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
     unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
 
@@ -235,7 +233,7 @@ void bitmap_clear(unsigned long *map, long start, long nr)
         p++;
     }
     if (nr) {
-        mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
+        mask_to_clear &= BITMAP_LAST_WORD_MASK(nr);
         *p &= ~mask_to_clear;
     }
 }
Signature · 1 line
2.17.1
#1 lore raw
Quoted 2 lines · Wei Yang

The value left in nr is the number of bits for the last word, which could be calculate the last word mask directly.

Is it true even if start does not align to BITS_PER_LONG?

Quoted 51 lines

Remove the unnecessary size.

---
resend with wider audience

---
 util/bitmap.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)
util/bitmap.c +2 -4
index cb618c65a5..5aa60b8717 100644
@@ -160,7 +160,6 @@ int slow_bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
 void bitmap_set(unsigned long *map, long start, long nr)
 {
     unsigned long *p = map + BIT_WORD(start);
-    const long size = start + nr;
     int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
     unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
 
@@ -174,7 +173,7 @@ void bitmap_set(unsigned long *map, long start, long nr)
         p++;
     }
     if (nr) {
-        mask_to_set &= BITMAP_LAST_WORD_MASK(size);
+        mask_to_set &= BITMAP_LAST_WORD_MASK(nr);
         *p |= mask_to_set;
     }
 }
@@ -221,7 +220,6 @@ void bitmap_set_atomic(unsigned long *map, long start, long nr)
 void bitmap_clear(unsigned long *map, long start, long nr)
 {
     unsigned long *p = map + BIT_WORD(start);
-    const long size = start + nr;
     int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
     unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
 
@@ -235,7 +233,7 @@ void bitmap_clear(unsigned long *map, long start, long nr)
         p++;
     }
     if (nr) {
-        mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
+        mask_to_clear &= BITMAP_LAST_WORD_MASK(nr);
         *p &= ~mask_to_clear;
     }
 }
Signature · 1 line
2.17.1

Regards,

Signature · 1 line
Peter Xu
author
#2 lore raw
Quoted 6 lines · Peter Xu
Quoted 2 lines · Wei Yang

The value left in nr is the number of bits for the last word, which could be calculate the last word mask directly.

Is it true even if start does not align to BITS_PER_LONG?

Yes. Let me see how to explain this.

When you look into the definition of BITMAP_LAST_WORD_MASK, it takes the number of total bits and give the number of bits in last word. While the value matters for the input is the number of last word. This means the following equation stands

BITMAP_LAST_WORD_MASK(size) == BITMAP_FIRST_WORD_MASK(size % BITS_PER_LONG)

Now let look at the calculation for nr. In each iteration, nr will be truncated to be aligned to BITS_PER_LONG. So when we exit the loop, nr keeps the number of bits in last word.

So we can leverage the result, no matter the start is aligned or not.

Quoted 56 lines
Quoted 51 lines

Remove the unnecessary size.

---
resend with wider audience

---
 util/bitmap.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)
util/bitmap.c +2 -4
index cb618c65a5..5aa60b8717 100644
@@ -160,7 +160,6 @@ int slow_bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
 void bitmap_set(unsigned long *map, long start, long nr)
 {
     unsigned long *p = map + BIT_WORD(start);
-    const long size = start + nr;
     int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
     unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
 
@@ -174,7 +173,7 @@ void bitmap_set(unsigned long *map, long start, long nr)
         p++;
     }
     if (nr) {
-        mask_to_set &= BITMAP_LAST_WORD_MASK(size);
+        mask_to_set &= BITMAP_LAST_WORD_MASK(nr);
         *p |= mask_to_set;
     }
 }
@@ -221,7 +220,6 @@ void bitmap_set_atomic(unsigned long *map, long start, long nr)
 void bitmap_clear(unsigned long *map, long start, long nr)
 {
     unsigned long *p = map + BIT_WORD(start);
-    const long size = start + nr;
     int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
     unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
 
@@ -235,7 +233,7 @@ void bitmap_clear(unsigned long *map, long start, long nr)
         p++;
     }
     if (nr) {
-        mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
+        mask_to_clear &= BITMAP_LAST_WORD_MASK(nr);
         *p &= ~mask_to_clear;
     }
 }
Signature · 1 line
2.17.1

Regards,

Signature · 1 line
Peter Xu
Signature · 2 lines
Wei Yang
Help you, Help me
#3 lore raw
Quoted 15 lines · Wei Yang
Quoted 6 lines · Peter Xu
Quoted 2 lines · Wei Yang

The value left in nr is the number of bits for the last word, which could be calculate the last word mask directly.

Is it true even if start does not align to BITS_PER_LONG?

Yes. Let me see how to explain this.

When you look into the definition of BITMAP_LAST_WORD_MASK, it takes the number of total bits and give the number of bits in last word. While the value matters for the input is the number of last word. This means the following equation stands

Quoted 7 lines

BITMAP_LAST_WORD_MASK(size) == BITMAP_FIRST_WORD_MASK(size % BITS_PER_LONG)

Now let look at the calculation for nr. In each iteration, nr will be truncated to be aligned to BITS_PER_LONG. So when we exit the loop, nr keeps the number of bits in last word.

So we can leverage the result, no matter the start is aligned or not.

Yes, you are right.

Do you have plan to write some unit tests for these functions? :)

It'll be tests/test-bitmap.c. IMHO the test cases could be even more helpful to the QEMU project as a whole comparing to this patch to guarantee changes like your patch won't break.

At the meantime I think you can also do that to bitmap_set_atomic.

Thanks,

Signature · 1 line
Peter Xu
author
#4 lore raw
Quoted 24 lines · Peter Xu
Quoted 15 lines · Wei Yang
Quoted 6 lines · Peter Xu
Quoted 2 lines · Wei Yang

The value left in nr is the number of bits for the last word, which could be calculate the last word mask directly.

Is it true even if start does not align to BITS_PER_LONG?

Yes. Let me see how to explain this.

When you look into the definition of BITMAP_LAST_WORD_MASK, it takes the number of total bits and give the number of bits in last word. While the value matters for the input is the number of last word. This means the following equation stands

Quoted 7 lines

BITMAP_LAST_WORD_MASK(size) == BITMAP_FIRST_WORD_MASK(size % BITS_PER_LONG)

Now let look at the calculation for nr. In each iteration, nr will be truncated to be aligned to BITS_PER_LONG. So when we exit the loop, nr keeps the number of bits in last word.

So we can leverage the result, no matter the start is aligned or not.

Quoted 7 lines

Yes, you are right.

Do you have plan to write some unit tests for these functions? :)

It'll be tests/test-bitmap.c. IMHO the test cases could be even more helpful to the QEMU project as a whole comparing to this patch to guarantee changes like your patch won't break.

Let me have a try. :-)

Quoted 7 lines

At the meantime I think you can also do that to bitmap_set_atomic.

Thanks,

Signature · 1 line
Peter Xu
Signature · 2 lines
Wei Yang
Help you, Help me