Message-ID: <5B69445D.1000107@intel.com>
Date:   Tue, 07 Aug 2018 15:03:57 +0800
From:   Wei Wang <wei.w.wang@...el.com>
To:     Rasmus Villemoes <linux@...musvillemoes.dk>,
        Yury Norov <ynorov@...iumnetworks.com>
CC:     linux-kernel@...r.kernel.org, akpm@...ux-foundation.org,
        corbet@....net, dgilbert@...hat.com,
        Andy Shevchenko <andy.shevchenko@...il.com>
Subject: Re: [PATCH] linux/bitmap.h: fix BITMAP_LAST_WORD_MASK

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

Powered by blists - more mailing lists