Skip to contentSkip to conversation

linux/bitmap.h: fix BITMAP_LAST_WORD_MASK

PATCH Superseded Wei Wang 4 participants 14 messages Jul 26, 2018 – Aug 14, 2018 Bitmap API

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Wei Wang

author
#0 lore raw

PATCH 1/1 linux/bitmap.h: fix BITMAP_LAST_WORD_MASK

The existing BITMAP_LAST_WORD_MASK macro returns 0xffffffff if nbits is
0. This patch changes the macro to return 0 when there is no bit needs to be masked.

Cc Andrew Morton <[email protected]>
Cc Rasmus Villemoes <[email protected]>
Cc Yury Norov <[email protected]>
---
 include/linux/bitmap.h | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)
include/linux/bitmap.h +4 -1
index 1ee46f4..12af3d7 100644
@@ -194,7 +194,10 @@ extern int bitmap_print_to_pagebuf(bool list, char *buf,
 				   const unsigned long *maskp, int nmaskbits);
 
 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
-#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
+#define BITMAP_LAST_WORD_MASK(nbits)				\
+(								\
+	nbits ? (~0UL >> (-(nbits) & (BITS_PER_LONG - 1))) : 0	\
+)
 
 #define small_const_nbits(nbits) \
 	(__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)
Signature · 1 line
2.7.4
#1 lore raw
Quoted 4 lines · Wei Wang

The existing BITMAP_LAST_WORD_MASK macro returns 0xffffffff if nbits is
0. This patch changes the macro to return 0 when there is no bit needs to be masked.

Can you provide a practical example of what's going wrong before this patch applied?

Quoted 27 lines
Cc Andrew Morton <[email protected]>
Cc Rasmus Villemoes <[email protected]>
Cc Yury Norov <[email protected]>
---
 include/linux/bitmap.h | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)
include/linux/bitmap.h +4 -2
index 1ee46f4..12af3d7 100644
@@ -194,7 +194,10 @@ extern int bitmap_print_to_pagebuf(bool list, char *buf,
                                   const unsigned long *maskp, int nmaskbits);
 
 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
-#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
+#define BITMAP_LAST_WORD_MASK(nbits)                           \
+(                                                              \
+       nbits ? (~0UL >> (-(nbits) & (BITS_PER_LONG - 1))) : 0  \
+)
 
 #define small_const_nbits(nbits) \
        (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)
--

2.7.4

Signature · 2 lines
With Best Regards,
Andy Shevchenko
author
#2 lore raw
Quoted 8 lines · Andy Shevchenko
Quoted 4 lines · Wei Wang

The existing BITMAP_LAST_WORD_MASK macro returns 0xffffffff if nbits is
0. This patch changes the macro to return 0 when there is no bit needs to be masked.

Can you provide a practical example of what's going wrong before this patch applied?

The reason of making this patch is that I saw some other software which ports this function and has possibilities to fall into bugs with usages which pass 0 to the macro. So I wonder if it would be necessary to make such changes in case we would get a similar bug. Or adding something to explain that "0" is not applicable to this macro as a reminder to people who would use it.

Best,
Wei

#3 lore raw
Quoted 8 lines · Wei Wang
Quoted 7 lines · Andy Shevchenko
Quoted 5 lines · Wei Wang

The existing BITMAP_LAST_WORD_MASK macro returns 0xffffffff if nbits is
0. This patch changes the macro to return 0 when there is no bit needs to be masked.

Quoted 7 lines
Quoted 3 lines

Can you provide a practical example of what's going wrong before this patch applied?

The reason of making this patch is that I saw some other software which ports this function and has possibilities to fall into bugs with usages which pass 0 to the macro.

No problems in the kernel, right?

Quoted 4 lines

So I wonder if it would be necessary to make such
changes in case we would get a similar bug. Or adding something to explain that "0" is not applicable to this macro as a reminder to people who would use it.

Comment can be added, yes.

Signature · 2 lines
With Best Regards,
Andy Shevchenko
#4 lore raw
In reply to Wei Wang
Quoted 3 lines · Wei Wang

The existing BITMAP_LAST_WORD_MASK macro returns 0xffffffff if nbits is
0. This patch changes the macro to return 0 when there is no bit needs to be masked.

I think this is intentional behavour. Previous version did return ~0UL explicitly in this case. See patch 89c1e79eb3023 (linux/bitmap.h: improve BITMAP_{LAST,FIRST}_WORD_MASK) from Rasmus.

Introducing conditional branch would affect performance. All existing code checks nbits for 0 before handling last word where needed explicitly. So I think we'd better change nothing here.

Yury

Quoted 26 lines
Cc Andrew Morton <[email protected]>
Cc Rasmus Villemoes <[email protected]>
Cc Yury Norov <[email protected]>
---
 include/linux/bitmap.h | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)
include/linux/bitmap.h +4 -2
index 1ee46f4..12af3d7 100644
@@ -194,7 +194,10 @@ extern int bitmap_print_to_pagebuf(bool list, char *buf,
                                   const unsigned long *maskp, int nmaskbits);
 
 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
-#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
+#define BITMAP_LAST_WORD_MASK(nbits)                           \
+(                                                              \
+       nbits ? (~0UL >> (-(nbits) & (BITS_PER_LONG - 1))) : 0  \
+)
 
 #define small_const_nbits(nbits) \
        (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)
--

2.7.4

author
#5 lore raw
Quoted 7 lines · Yury Norov
Quoted 3 lines · Wei Wang

The existing BITMAP_LAST_WORD_MASK macro returns 0xffffffff if nbits is
0. This patch changes the macro to return 0 when there is no bit needs to be masked.

I think this is intentional behavour. Previous version did return ~0UL explicitly in this case. See patch 89c1e79eb3023 (linux/bitmap.h: improve BITMAP_{LAST,FIRST}_WORD_MASK) from Rasmus.

Yes, I saw that. But it seems confusing for the corner case that nbits=0 (no bits to mask), the macro returns with all the bits set.

Quoted 4 lines

Introducing conditional branch would affect performance. All existing code checks nbits for 0 before handling last word where needed explicitly. So I think we'd better change nothing here.

I think that didn't save the conditional branch essentially, because it's just moved from inside this macro to the caller as you mentioned. If callers missed the check for some reason and passed 0 to the macro, they will get something unexpected.

Current callers like __bitmap_weight, __bitmap_equal, and others, they have

if (bits % BITS_PER_LONG)

    w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));

we could remove the "if" check by "w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits % BITS_PER_LONG));" the branch is the same.

Best,
Wei

#6 lore raw
Quoted 25 lines · Wei Wang

External Email

Quoted 7 lines · Yury Norov
Quoted 3 lines · Wei Wang

The existing BITMAP_LAST_WORD_MASK macro returns 0xffffffff if nbits is
0. This patch changes the macro to return 0 when there is no bit needs to be masked.

I think this is intentional behavour. Previous version did return ~0UL explicitly in this case. See patch 89c1e79eb3023 (linux/bitmap.h: improve BITMAP_{LAST,FIRST}_WORD_MASK) from Rasmus.

Yes, I saw that. But it seems confusing for the corner case that nbits=0 (no bits to mask), the macro returns with all the bits set.

Quoted 4 lines

Introducing conditional branch would affect performance. All existing code checks nbits for 0 before handling last word where needed explicitly. So I think we'd better change nothing here.

I think that didn't save the conditional branch essentially, because it's just moved from inside this macro to the caller as you mentioned. If callers missed the check for some reason and passed 0 to the macro, they will get something unexpected.

Quoted 7 lines

Current callers like __bitmap_weight, __bitmap_equal, and others, they have

if (bits % BITS_PER_LONG)

    w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));

we could remove the "if" check by "w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits % BITS_PER_LONG));" the branch is the same.

But your patch doesn't remove external conditional, and it fact introduces overhead, right? Also, in some cases it's not so trivial to remove it. Consider __bitmap_intersects() for example.

Anyway, this patch changes the very basic API. In that case you should check every user of the macro to be safe against the change, including possible performance downsides.

If you find this corner case behavior of macro confusing, I think that the better option would be introducing detailed comment to the BITMAP_LAST_WORD_MASK(), or writing wrapper around it that handles nbits == 0 as you expect.

Thanks,
Yury

author
#7 lore raw
Quoted 34 lines · Yury Norov
Quoted 22 lines · Wei Wang

External Email

Quoted 7 lines · Yury Norov
Quoted 3 lines · Wei Wang

The existing BITMAP_LAST_WORD_MASK macro returns 0xffffffff if nbits is
0. This patch changes the macro to return 0 when there is no bit needs to be masked.

I think this is intentional behavour. Previous version did return ~0UL explicitly in this case. See patch 89c1e79eb3023 (linux/bitmap.h: improve BITMAP_{LAST,FIRST}_WORD_MASK) from Rasmus.

Yes, I saw that. But it seems confusing for the corner case that nbits=0 (no bits to mask), the macro returns with all the bits set.

Quoted 3 lines

Introducing conditional branch would affect performance. All existing code checks nbits for 0 before handling last word where needed explicitly. So I think we'd better change nothing here.

I think that didn't save the conditional branch essentially, because it's just moved from inside this macro to the caller as you mentioned. If callers missed the check for some reason and passed 0 to the macro, they will get something unexpected.

Quoted 7 lines

Current callers like __bitmap_weight, __bitmap_equal, and others, they have

if (bits % BITS_PER_LONG)

     w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));

we could remove the "if" check by "w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits % BITS_PER_LONG));" the branch is the same.

But your patch doesn't remove external conditional, and it fact introduces overhead, right? Also, in some cases it's not so trivial to remove it. Consider __bitmap_intersects() for example.

Quoted 9 lines

Anyway, this patch changes the very basic API. In that case you should check every user of the macro to be safe against the change, including possible performance downsides.

If you find this corner case behavior of macro confusing, I think that the better option would be introducing detailed comment to the BITMAP_LAST_WORD_MASK(), or writing wrapper around it that handles nbits == 0 as you expect.

OK. Thanks Yury and Andy for the discussion. It seems the more preferred way is just to add comments as a note. Agree with that.

Best,
Wei

#8 lore raw
In reply to Wei Wang
Quoted 24 lines · Wei Wang
Quoted 8 lines · Yury Norov
Quoted 4 lines · Wei Wang

The existing BITMAP_LAST_WORD_MASK macro returns 0xffffffff if nbits is
0. This patch changes the macro to return 0 when there is no bit needs to
be masked.

I think this is intentional behavour. Previous version did return ~0UL explicitly in this case. See patch 89c1e79eb3023 (linux/bitmap.h: improve BITMAP_{LAST,FIRST}_WORD_MASK) from Rasmus.

Yes, I saw that. But it seems confusing for the corner case that nbits=0 (no bits to mask), the macro returns with all the bits set.

Quoted 4 lines

Introducing conditional branch would affect performance. All existing code checks nbits for 0 before handling last word where needed explicitly. So I think we'd better change nothing here.

I think that didn't save the conditional branch essentially, because it's just moved from inside this macro to the caller as you mentioned. If callers missed the check for some reason and passed 0 to the macro, they will get something unexpected.

Quoted 7 lines

Current callers like __bitmap_weight, __bitmap_equal, and others, they have

if (bits % BITS_PER_LONG)
    w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));

we could remove the "if" check by "w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits % BITS_PER_LONG));" the branch is the same.

Absolutely not! That would access bitmap[lim] (the final value of the k variable) despite that word not being part of the bitmap.

More generally, look at the name of the macro: last_word_mask. It's a mask to apply to the last word of a bitmap. If the bitmap happens to consist of a multiple of BITS_PER_LONG bits, than that mask is and must be ~0UL. So for nbits=64, 128, etc., that is what we want.

OTOH, for nbits=0, there _is_ no last word (since there are no words at all), so by the time you want to apply the result of BITMAP_LAST_WORD_MASK(0) to anything, you already have a bug, probably either having read or being about to write into bitmap[0], which you cannot do. Please check that user-space port and see if there are bugs of that kind.

So no, the existing users of BITMAP_LAST_WORD_MASK do not check for nbits being zero, they check for whether there is a partial last word, which is something different. And they mostly (those in lib/bitmap.c) do that because they've already handled _all_ the full words. Then there are some users in include/linux/bitmap.h, that check for small_const_nbits(nbits), and in those cases, we really want ~0UL when nbits is BITS_PER_LONG, because small_const_nbits implies there is exactly one word. Yeah, there's an implicit assumption that the bitmap routines are never called with a compile-time constant nbits==0 (see the unconditional accesses to *src and *dst), but changing the semantics of BITMAP_LAST_WORD_MASK and making it return different values for nbits=0 vs nbits=64 wouldn't fix that latent bug.

Andrew, you may consider this a NAK of the v2 patch. Callers should indeed avoid using BITMAP_LAST_WORD_MASK with nbits==0, but not because the macro returns a wrong or unexpected value in that case, but simply because it is meaningless to use it at all.

Rasmus

author
#9 lore raw
Quoted 24 lines · Rasmus Villemoes
Quoted 23 lines · Wei Wang
Quoted 8 lines · Yury Norov
Quoted 4 lines · Wei Wang

The existing BITMAP_LAST_WORD_MASK macro returns 0xffffffff if nbits is
0. This patch changes the macro to return 0 when there is no bit needs to
be masked.

I think this is intentional behavour. Previous version did return ~0UL explicitly in this case. See patch 89c1e79eb3023 (linux/bitmap.h: improve BITMAP_{LAST,FIRST}_WORD_MASK) from Rasmus.

Yes, I saw that. But it seems confusing for the corner case that nbits=0 (no bits to mask), the macro returns with all the bits set.

Quoted 3 lines

Introducing conditional branch would affect performance. All existing code checks nbits for 0 before handling last word where needed explicitly. So I think we'd better change nothing here.

I think that didn't save the conditional branch essentially, because it's just moved from inside this macro to the caller as you mentioned. If callers missed the check for some reason and passed 0 to the macro, they will get something unexpected.

Current callers like __bitmap_weight, __bitmap_equal, and others, they have

Quoted 7 lines
Quoted 5 lines

if (bits % BITS_PER_LONG)

     w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));

we could remove the "if" check by "w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits % BITS_PER_LONG));" the branch is the same.

Absolutely not! That would access bitmap[lim] (the final value of the k variable) despite that word not being part of the bitmap.

Probably it's more clear to post the entire function here for a discussion:

int __bitmap_weight(const unsigned long *bitmap, unsigned int bits)

{
        unsigned int k, lim = bits/BITS_PER_LONG;
        int w = 0;

        for (k = 0; k < lim; k++)
                w += hweight_long(bitmap[k]);

        if (bits % BITS_PER_LONG)

==> w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));

        return w;
}

When the execution reaches "==>", isn't "k=lim"?

For example, assume bits = 70, then the point of that line is to check the remaining 6 bits (i.e. 70 % 64).

* BITMAP_LAST_WORD_MASK(70) is effectively the same as BITMAP_LAST_WORD_MASK(6).

If having doubts about the * statement above, please check below the old implementation (replaced by 89c1e79eb3), which has a more straightforward logic to understand

#define BITMAP_LAST_WORD_MASK(nbits) \

( \
       ((nbits) % BITS_PER_LONG) ?                                     \
               (1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL               \

)

I think having the branch in the macro would be much easier than having it in each caller.

Quoted 5 lines

More generally, look at the name of the macro: last_word_mask. It's a mask to apply to the last word of a bitmap. If the bitmap happens to consist of a multiple of BITS_PER_LONG bits, than that mask is and must be ~0UL. So for nbits=64, 128, etc., that is what we want.

For nbits=64, it is correct to return ~0UL, since it just asks to check all the remaining 64 bits, thus keeping the entire 64 bits set.

Quoted 6 lines

OTOH, for nbits=0, there _is_ no last word (since there are no words at all), so by the time you want to apply the result of BITMAP_LAST_WORD_MASK(0) to anything, you already have a bug, probably either having read or being about to write into bitmap[0], which you cannot do. Please check that user-space port and see if there are bugs of that kind.

Yes, some callers there don't check for nbits=0, that's why I think it is better to offload that check to the macro. The macro itself can be robust to handle all the cases.

Quoted 4 lines

So no, the existing users of BITMAP_LAST_WORD_MASK do not check for nbits being zero, they check for whether there is a partial last word, which is something different.

Yes, but "partial" could be "0". If the macro doesn't handle that case, I think that wouldn't be a robust macro.

We shouldn't assume how the callers will use this macro. Please check bitmap_shift_right, I think the bug is already there:

        if (small_const_nbits(nbits))
                *dst = (*src & BITMAP_LAST_WORD_MASK(nbits)) >> shift;

*dst should be 0 if nbits=0, but nbits=0 will pass the
small_const_nbits(nbits) check above, and BITMAP_LAST_WORD_MASK(0) returning 0xffffffff will take *src value to *dst.

Quoted 10 lines

And they mostly (those in lib/bitmap.c) do
that because they've already handled _all_ the full words. Then there are some users in include/linux/bitmap.h, that check for small_const_nbits(nbits), and in those cases, we really want ~0UL when nbits is BITS_PER_LONG, because small_const_nbits implies there is exactly one word. Yeah, there's an implicit assumption that the bitmap routines are never called with a compile-time constant nbits==0 (see the unconditional accesses to *src and *dst), but changing the semantics of BITMAP_LAST_WORD_MASK and making it return different values for nbits=0 vs nbits=64 wouldn't fix that latent bug.

nbits=0, means there is no bit needs to mask
nbits=64, means all the 64 bits need to mask

The two are different cases, I'm not sure why we let the macro to return the same value.

Best,
Wei

author
#10 lore raw
Quoted 44 lines · Wei Wang
Quoted 24 lines · Rasmus Villemoes
Quoted 23 lines · Wei Wang
Quoted 8 lines · Yury Norov
Quoted 4 lines · Wei Wang

The existing BITMAP_LAST_WORD_MASK macro returns 0xffffffff if nbits is
0. This patch changes the macro to return 0 when there is no bit needs to
be masked.

I think this is intentional behavour. Previous version did return ~0UL explicitly in this case. See patch 89c1e79eb3023 (linux/bitmap.h: improve BITMAP_{LAST,FIRST}_WORD_MASK) from Rasmus.

Yes, I saw that. But it seems confusing for the corner case that nbits=0 (no bits to mask), the macro returns with all the bits set.

Quoted 3 lines

Introducing conditional branch would affect performance. All existing code checks nbits for 0 before handling last word where needed explicitly. So I think we'd better change nothing here.

I think that didn't save the conditional branch essentially, because it's just moved from inside this macro to the caller as you mentioned. If callers missed the check for some reason and passed 0 to the macro, they will get something unexpected.

Current callers like __bitmap_weight, __bitmap_equal, and others, they have

Quoted 7 lines
Quoted 5 lines

if (bits % BITS_PER_LONG)

     w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));

we could remove the "if" check by "w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits % BITS_PER_LONG));" the branch is the same.

Absolutely not! That would access bitmap[lim] (the final value of the k variable) despite that word not being part of the bitmap.

Probably it's more clear to post the entire function here for a discussion:

int __bitmap_weight(const unsigned long *bitmap, unsigned int bits)

{
        unsigned int k, lim = bits/BITS_PER_LONG;
        int w = 0;

        for (k = 0; k < lim; k++)
                w += hweight_long(bitmap[k]);

        if (bits % BITS_PER_LONG)
Quoted 6 lines

==> w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));

        return w;
}

When the execution reaches "==>", isn't "k=lim"?

And accessing to bitmap[lim] which does not exist should be a case considered by the caller rather than the macro. For example, with "BITMAP_LAST_WORD_MASK(bits) & bitmap[k]", making BITMAP_LAST_WORD_MASK(0) be 0 will not be a problem. Anyway, my point is that we could make the macro itself robust.

Best,
Wei

#11 lore raw
In reply to Wei Wang
Quoted 23 lines · Wei Wang
Quoted 10 lines · Rasmus Villemoes
Quoted 5 lines · Wei Wang

if (bits % BITS_PER_LONG)

     w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));

we could remove the "if" check by "w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits % BITS_PER_LONG));" the branch is the same.

Absolutely not! That would access bitmap[lim] (the final value of the k variable) despite that word not being part of the bitmap.

Probably it's more clear to post the entire function here for a discussion:

int __bitmap_weight(const unsigned long *bitmap, unsigned int bits)

{
        unsigned int k, lim = bits/BITS_PER_LONG;
        int w = 0;

        for (k = 0; k < lim; k++)
                w += hweight_long(bitmap[k]);

        if (bits % BITS_PER_LONG)
Quoted 6 lines

==> w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));

        return w;
}

When the execution reaches "==>", isn't "k=lim"?

Let's check again, if bits == 0, bits % whatever == 0 as well, thus, no execution. When bits < BITS_PER_LONG, the execution is fine (k = 0 and still 0).
When bits >= BITS_PER_LONG, but not aligned, k goes from 0 to lim and last word is exactly the partially filled one. No problem here. Las case if bits % BITS_PER_LONG == 0, but hey, we have a guard against this.

So, where is the problem exactly?

Quoted 10 lines
Quoted 6 lines

OTOH, for nbits=0, there _is_ no last word (since there are no words at all), so by the time you want to apply the result of BITMAP_LAST_WORD_MASK(0) to anything, you already have a bug, probably either having read or being about to write into bitmap[0], which you cannot do. Please check that user-space port and see if there are bugs of that kind.

Yes, some callers there don't check for nbits=0, that's why I think it is better to offload that check to the macro. The macro itself can be robust to handle all the cases.

Where they are? Can't you point out?

Quoted 5 lines
Quoted 3 lines

So no, the existing users of BITMAP_LAST_WORD_MASK do not check for nbits being zero, they check for whether there is a partial last word, which is something different.

Yes, but "partial" could be "0".

How come?!

Quoted 11 lines
Quoted 10 lines

And they mostly (those in lib/bitmap.c) do
that because they've already handled _all_ the full words. Then there are some users in include/linux/bitmap.h, that check for small_const_nbits(nbits), and in those cases, we really want ~0UL when nbits is BITS_PER_LONG, because small_const_nbits implies there is exactly one word. Yeah, there's an implicit assumption that the bitmap routines are never called with a compile-time constant nbits==0 (see the unconditional accesses to *src and *dst), but changing the semantics of BITMAP_LAST_WORD_MASK and making it return different values for nbits=0 vs nbits=64 wouldn't fix that latent bug.

Quoted 1 line

nbits=0, means there is no bit needs to mask

Like Rasmus said it's rather broken input and here you can consider nbits==0 brings _rightfully_ UB to the caller's code.

Quoted 4 lines

nbits=64, means all the 64 bits need to mask

The two are different cases, I'm not sure why we let the macro to return the same value.

The point is macro mustn't be called when nbits==0.

Signature · 2 lines
With Best Regards,
Andy Shevchenko
author
#12 lore raw
Quoted 25 lines · Andy Shevchenko
Quoted 11 lines

Probably it's more clear to post the entire function here for a discussion:

int __bitmap_weight(const unsigned long *bitmap, unsigned int bits)

{
         unsigned int k, lim = bits/BITS_PER_LONG;
         int w = 0;

         for (k = 0; k < lim; k++)
                 w += hweight_long(bitmap[k]);

         if (bits % BITS_PER_LONG)
Quoted 6 lines

==> w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));

         return w;
}

When the execution reaches "==>", isn't "k=lim"?

Let's check again, if bits == 0, bits % whatever == 0 as well, thus, no execution. When bits < BITS_PER_LONG, the execution is fine (k = 0 and still 0).
When bits >= BITS_PER_LONG, but not aligned, k goes from 0 to lim and last word is exactly the partially filled one. No problem here. Las case if bits % BITS_PER_LONG == 0, but hey, we have a guard against this.

Quoted 1 line

So, where is the problem exactly?

There is no problem here. All the discussions here are about if it is better to
1) put this guard to the macro or 2) have each callers to do it.

If we go with 2) as we discussed before, then do we need to add notes above the macro to people who will use/port this macro.

Quoted 11 lines
Quoted 10 lines
Quoted 7 lines

OTOH, for nbits=0, there _is_ no last word (since there are no words at all), so by the time you want to apply the result of BITMAP_LAST_WORD_MASK(0) to anything, you already have a bug, probably either having read or being about to write into bitmap[0], which you cannot do. Please check that user-space port and see if there are bugs of that kind.

Yes, some callers there don't check for nbits=0, that's why I think it is better to offload that check to the macro. The macro itself can be robust to handle all the cases.

Where they are? Can't you point out?

"there", I meant that user-space port, not in the kernel.
e.g.
Line 225 at https://github.com/qemu/qemu/blob/master/include/qemu/bitmap.h
(there are a couple of other places)

Quoted 6 lines
Quoted 4 lines

nbits=64, means all the 64 bits need to mask

The two are different cases, I'm not sure why we let the macro to return the same value.

The point is macro mustn't be called when nbits==0.

Yes, I fully agree with that point, but it seems Rasmus NAK-ed that point.

To conclude the point of the discussion: with the current macro, there is no doc saying 0 can't be given to this macro and "BITMAP_LAST_WORD_MASK(0)=0xffffffff" doesn't seem correct to me.

Best,
Wei

#13 lore raw
Quoted 6 lines · Wei Wang

On 08/07/2018 06:26 PM, Andy Shevchenko wrote:

"there", I meant that user-space port, not in the kernel.
e.g.
Line 225 at https://github.com/qemu/qemu/blob/master/include/qemu/bitmap.h
(there are a couple of other places)

So, means no problems in Linux kernel project.
Thus -> NAK.

Quoted 9 lines
Quoted 7 lines
Quoted 5 lines

nbits=64, means all the 64 bits need to mask

The two are different cases, I'm not sure why we let the macro to return the
same value.

The point is macro mustn't be called when nbits==0.

Yes, I fully agree with that point, but it seems Rasmus NAK-ed that point.

No, we are talking about different things. Rasmus pretty much right that the caller should have already known nbits and avoid calling this macro if it's zero.

Signature · 2 lines
With Best Regards,
Andy Shevchenko