Message-ID: <08410774-8b10-d620-064c-fdf4399d7336@rasmusvillemoes.dk>
Date:   Tue, 7 Aug 2018 01:30:56 +0200
From:   Rasmus Villemoes <linux@...musvillemoes.dk>
To:     Wei Wang <wei.w.wang@...el.com>,
        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 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

Powered by blists - more mailing lists