linux-kernel - Re: [PATCH v3 1/5] lib/bitmap: add bitmap_{set,get}

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]

Message-ID: <ZLbF3ZO7TvJGJOeo@yury-ThinkPad>
Date:   Tue, 18 Jul 2023 10:03:25 -0700
From:   Yury Norov <yury.norov@...il.com>
To:     Andy Shevchenko <andriy.shevchenko@...ux.intel.com>
Cc:     Alexander Potapenko <glider@...gle.com>, catalin.marinas@....com,
        will@...nel.org, pcc@...gle.com, andreyknvl@...il.com,
        linux@...musvillemoes.dk, linux-kernel@...r.kernel.org,
        linux-arm-kernel@...ts.infradead.org, eugenis@...gle.com,
        syednwaris@...il.com, william.gray@...aro.org,
        Arnd Bergmann <arnd@...db.de>
Subject: Re: [PATCH v3 1/5] lib/bitmap: add bitmap_{set,get}_value()

On Tue, Jul 18, 2023 at 05:01:28PM +0300, Andy Shevchenko wrote:
> On Tue, Jul 18, 2023 at 11:30:00AM +0200, Alexander Potapenko wrote:
> > On Mon, Jul 17, 2023 at 5:51 PM Yury Norov <yury.norov@...il.com> wrote:
> > > On Mon, Jul 17, 2023 at 01:37:04PM +0200, Alexander Potapenko wrote:
> 
> ...
> 
> > > When nbits == 0, copy-like functions shouldn't touch any memory. See how
> > > other bitmap and find_bit functions hold it.
> > 
> > I think this is different from what other bitmap functions do, but it
> > should be enough to bail out on !nbits, i.e.:
> > 
> >     if (!nbits)
> >         return 0;
> > 
> > You probably meant adding a __builtin_constant_p() (which is used all
> > over the place in bitmap.h), but:

No, I didn't mean that.

> >  - the compiler won't have problem optimizing away the code for a
> > constant nbits=0;

Look at your code, having nbits == 0 in mind:

       const size_t index = BIT_WORD(start);
       const unsigned long offset = start % BITS_PER_LONG;
       const unsigned long space = BITS_PER_LONG - offset;
       unsigned long value_low, value_high;

       if (space >= nbits) // This is always the case
               return (map[index] >> offset) & GENMASK(nbits - 1, 0);
       ...             ^^                      ^^
                       Unconditional fetch     Wshift-count-overflow

Thanks to GENMASK() implementation, you'll be warned by GENMASK_INPUT_CHECK()
if nbits is a compile-time variable. In case of runtime, it's a pure undef,
not mentioning useless, expensive and dangerous fetch.

> >  - we anyway need a dynamic check for the case nbits is not constant
> > (for both bitmap_get_value() and bitmap_set_value(), I assume).
> > 
> > What do you think?

I think that instead of speculations, it's better to cover nbits == 0
with the explicit tests for run- and compile-time. That way you're
always on a safe side.

bitmap_get_val(NULL, 0, 0) shouldn't crash the kernel.

> The idea behind is to eliminate the code completely for the cases nbits != 0.
> In your case the dynamic check will be there. That's what we want to avoid.

Alexander is right - we can't avoid testing against 0 if we need to
test for 0... In case of other functions we have inline and outline
implementations, controlled by small_const_nbits().

As you can see, the small_const_nbits() tests against 0 explicitly,
although it's free at compile time. But if nbits == 0, we pick
outline version of a function regardless.

On their turn, outline versions again do their test against nbits == 0,
but most of the time implicitly.

In case of bitmap_set_val, we are touching at max 2 words, and there's
no reason for outline version, so we have to test nbits against 0
inside inline code. 

Having all that in mind, and because nbits == 0 is most likely an
error we'd follow the following rules:
 - no memory must be touched as we're potentially in error condition,
   and pointer may be corrupted;
 - the cost of the check must be as minimal as possible.

So I suggest:

        if (unlikely(nbits == 0))
                return;

For readers that would literally mean: we don't expect that, and we find
it suspicious, but we'll handle that as correct as we can.

By the way, Alexander, please drop that 'const' things. Those are for
pointers or some global variables, not for inline functions with 4
lines of code. (If you think it helps the code to be safe than no - it's
unsafe even with consts.)

Thanks,
Yury