Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
MIME-Version: 1.0
In-Reply-To: <5B69445D.1000107@intel.com>
References: <1532592471-21177-1-git-send-email-wei.w.wang@intel.com>
 <20180726093728.GA9069@yury-thinkpad> <5B599F5F.2070705@intel.com>
 <08410774-8b10-d620-064c-fdf4399d7336@rasmusvillemoes.dk> <5B69445D.1000107@intel.com>
From:   Andy Shevchenko <andy.shevchenko@gmail.com>
Date:   Tue, 7 Aug 2018 13:26:02 +0300
Message-ID: <CAHp75VeQaHGaRgN8o1t7bA2BTjshZqO1GUO+D9BBqp1cVVrV2A@mail.gmail.com>
Subject: Re: [PATCH] linux/bitmap.h: fix BITMAP_LAST_WORD_MASK
To:     Wei Wang <wei.w.wang@intel.com>
Cc:     Rasmus Villemoes <linux@rasmusvillemoes.dk>,
        Yury Norov <ynorov@caviumnetworks.com>,
        Linux Kernel Mailing List <linux-kernel@vger.kernel.org>,
        Andrew Morton <akpm@linux-foundation.org>,
        Jonathan Corbet <corbet@lwn.net>, dgilbert@redhat.com
Content-Type: text/plain; charset="UTF-8"
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

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