linux-kernel - Re: [PATCH] linux/bitmap.h: fix BITMAP_LAST_WORD

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Tue, 7 Aug 2018 13:26:02 +0300
From:   Andy Shevchenko <andy.shevchenko@...il.com>
To:     Wei Wang <wei.w.wang@...el.com>
Cc:     Rasmus Villemoes <linux@...musvillemoes.dk>,
        Yury Norov <ynorov@...iumnetworks.com>,
        Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
        Andrew Morton <akpm@...ux-foundation.org>,
        Jonathan Corbet <corbet@....net>, dgilbert@...hat.com
Subject: Re: [PATCH] linux/bitmap.h: fix BITMAP_LAST_WORD_MASK

On Tue, Aug 7, 2018 at 10:03 AM, Wei Wang <wei.w.wang@...el.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