[PATCH] linux/bitmap.h: fix BITMAP_LAST_WORD_MASK

[PATCH] linux/bitmap.h: fix BITMAP_LAST_WORD_MASK

[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.

Signed-off-by: Wei Wang <wei.w.wang@intel.com>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
Cc: Yury Norov <ynorov@caviumnetworks.com>
---
 include/linux/bitmap.h | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 1ee46f4..12af3d7 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -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

Re: [PATCH] linux/bitmap.h: fix BITMAP_LAST_WORD_MASK

[Andy Shevchenko]

On Thu, Jul 26, 2018 at 11:07 AM, Wei Wang <wei.w.wang@intel.com> wrote:
> 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?

> Signed-off-by: Wei Wang <wei.w.wang@intel.com>
> Cc: Andrew Morton <akpm@linux-foundation.org>
> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
> Cc: Yury Norov <ynorov@caviumnetworks.com>
> ---
>  include/linux/bitmap.h | 5 ++++-
>  1 file changed, 4 insertions(+), 1 deletion(-)
>
> diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
> index 1ee46f4..12af3d7 100644
> --- a/include/linux/bitmap.h
> +++ b/include/linux/bitmap.h
> @@ -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
>



-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH] linux/bitmap.h: fix BITMAP_LAST_WORD_MASK

[Wei Wang]

On 07/26/2018 04:48 PM, Andy Shevchenko wrote:
> On Thu, Jul 26, 2018 at 11:07 AM, Wei Wang <wei.w.wang@intel.com> wrote:
>> 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

Re: [PATCH] linux/bitmap.h: fix BITMAP_LAST_WORD_MASK

[Andy Shevchenko]

On Thu, Jul 26, 2018 at 1:08 PM, Wei Wang <wei.w.wang@intel.com> wrote:
> On 07/26/2018 04:48 PM, Andy Shevchenko wrote:
>>
>> On Thu, Jul 26, 2018 at 11:07 AM, Wei Wang <wei.w.wang@intel.com> wrote:
>>>
>>> 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.

No problems in the kernel, right?

> 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.

-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH] linux/bitmap.h: fix BITMAP_LAST_WORD_MASK

[Yury Norov]

On Thu, Jul 26, 2018 at 04:07:51PM +0800, Wei Wang wrote:
> 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

> Signed-off-by: Wei Wang <wei.w.wang@intel.com>
> Cc: Andrew Morton <akpm@linux-foundation.org>
> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
> Cc: Yury Norov <ynorov@caviumnetworks.com>
> ---
>  include/linux/bitmap.h | 5 ++++-
>  1 file changed, 4 insertions(+), 1 deletion(-)
> 
> diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
> index 1ee46f4..12af3d7 100644
> --- a/include/linux/bitmap.h
> +++ b/include/linux/bitmap.h
> @@ -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

Re: [PATCH] linux/bitmap.h: fix BITMAP_LAST_WORD_MASK

[Wei Wang]

On 07/26/2018 05:37 PM, Yury Norov wrote:
> On Thu, Jul 26, 2018 at 04:07:51PM +0800, Wei Wang wrote:
>> 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.


>
> 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

Re: [PATCH] linux/bitmap.h: fix BITMAP_LAST_WORD_MASK

[Yury Norov]

On Thu, Jul 26, 2018 at 06:15:59PM +0800, Wei Wang wrote:
> External Email
> 
> On 07/26/2018 05:37 PM, Yury Norov wrote:
> > On Thu, Jul 26, 2018 at 04:07:51PM +0800, Wei Wang wrote:
> > > 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.
> 
> 
> > 
> > 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.

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

Re: [PATCH] linux/bitmap.h: fix BITMAP_LAST_WORD_MASK

[Wei Wang]

On 07/26/2018 08:10 PM, Yury Norov wrote:
> On Thu, Jul 26, 2018 at 06:15:59PM +0800, Wei Wang wrote:
>> External Email
>>
>> On 07/26/2018 05:37 PM, Yury Norov wrote:
>>> On Thu, Jul 26, 2018 at 04:07:51PM +0800, Wei Wang wrote:
>>>> 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.
>>
>>
>>> 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.
> 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.
>

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

Re: [PATCH] linux/bitmap.h: fix BITMAP_LAST_WORD_MASK

[Rasmus Villemoes]

On 2018-07-26 12:15, Wei Wang wrote:
> On 07/26/2018 05:37 PM, Yury Norov wrote:
>> On Thu, Jul 26, 2018 at 04:07:51PM +0800, Wei Wang wrote:
>>> 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.
> 
> 
>>
>> 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.

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

Re: [PATCH] linux/bitmap.h: fix BITMAP_LAST_WORD_MASK

[Wei Wang]

On 08/07/2018 07:30 AM, Rasmus Villemoes wrote:
> On 2018-07-26 12:15, Wei Wang wrote:
>> On 07/26/2018 05:37 PM, Yury Norov wrote:
>>> On Thu, Jul 26, 2018 at 04:07:51PM +0800, Wei Wang wrote:
>>>> 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.
>>
>>
>>> 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.
> 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.

>
> 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.

> 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.


>
> 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.


> 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

Re: [PATCH] linux/bitmap.h: fix BITMAP_LAST_WORD_MASK

[Wei Wang]

On 08/07/2018 03:03 PM, Wei Wang wrote:
> On 08/07/2018 07:30 AM, Rasmus Villemoes wrote:
>> On 2018-07-26 12:15, Wei Wang wrote:
>>> On 07/26/2018 05:37 PM, Yury Norov wrote:
>>>> On Thu, Jul 26, 2018 at 04:07:51PM +0800, Wei Wang wrote:
>>>>> 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.
>>>
>>>
>>>> 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.
>> 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"?

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

Re: [PATCH] linux/bitmap.h: fix BITMAP_LAST_WORD_MASK

[Andy Shevchenko]

On Tue, Aug 7, 2018 at 10:03 AM, Wei Wang <wei.w.wang@intel.com> wrote:
> On 08/07/2018 07:30 AM, Rasmus Villemoes wrote:
>> On 2018-07-26 12:15, Wei Wang wrote:

>>> 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"?

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?

>> 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?

>> 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?!

>> 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

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

> 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.

-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH] linux/bitmap.h: fix BITMAP_LAST_WORD_MASK

[Wei Wang]

On 08/07/2018 06:26 PM, Andy Shevchenko wrote:
>> 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"?
> 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?

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.


>
>>> 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)

>> 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

Re: [PATCH] linux/bitmap.h: fix BITMAP_LAST_WORD_MASK

[Andy Shevchenko]

On Tue, Aug 7, 2018 at 2:22 PM, Wei Wang <wei.w.wang@intel.com> wrote:
> 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.

>>> 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.

-- 
With Best Regards,
Andy Shevchenko