linux-kernel - Re: [PATCH v11 1/4] bitops: Introduce the for_each_set

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: <CACG_h5pYL+HbJpPcCTp=dR8rDbm07RsRDaX8Uc0HYc2LG--w_Q@mail.gmail.com>
Date:   Fri, 16 Oct 2020 04:23:05 +0530
From:   Syed Nayyar Waris <syednwaris@...il.com>
To:     Andy Shevchenko <andriy.shevchenko@...ux.intel.com>
Cc:     Linus Walleij <linus.walleij@...aro.org>,
        Andrew Morton <akpm@...ux-foundation.org>,
        William Breathitt Gray <vilhelm.gray@...il.com>,
        Arnd Bergmann <arnd@...db.de>,
        Linux-Arch <linux-arch@...r.kernel.org>,
        Linux Kernel Mailing List <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH v11 1/4] bitops: Introduce the for_each_set_clump macro

On Tue, Oct 6, 2020 at 4:56 PM Andy Shevchenko
<andriy.shevchenko@...ux.intel.com> wrote:
>
> On Tue, Oct 06, 2020 at 02:52:16PM +0530, Syed Nayyar Waris wrote:
> > This macro iterates for each group of bits (clump) with set bits,
> > within a bitmap memory region. For each iteration, "start" is set to
> > the bit offset of the found clump, while the respective clump value is
> > stored to the location pointed by "clump". Additionally, the
> > bitmap_get_value() and bitmap_set_value() functions are introduced to
> > respectively get and set a value of n-bits in a bitmap memory region.
> > The n-bits can have any size less than or equal to BITS_PER_LONG.
> > Moreover, during setting value of n-bit in bitmap, if a situation arise
> > that the width of next n-bit is exceeding the word boundary, then it
> > will divide itself such that some portion of it is stored in that word,
> > while the remaining portion is stored in the next higher word. Similar
> > situation occurs while retrieving the value from bitmap.
>
> ...
>
> > @@ -75,7 +75,11 @@
> >   *  bitmap_from_arr32(dst, buf, nbits)          Copy nbits from u32[] buf to dst
> >   *  bitmap_to_arr32(buf, src, nbits)            Copy nbits from buf to u32[] dst
> >   *  bitmap_get_value8(map, start)               Get 8bit value from map at start
> > + *  bitmap_get_value(map, start, nbits)              Get bit value of size
> > + *                                           'nbits' from map at start
> >   *  bitmap_set_value8(map, value, start)        Set 8bit value to map at start
> > + *  bitmap_set_value(map, value, start, nbits)       Set bit value of size 'nbits'
> > + *                                           of map at start
>
> Formatting here is done with solely spaces, no TABs.

Okay. Done

>
> ...
>
> > +/**
> > + * bitmap_get_value - get a value of n-bits from the memory region
> > + * @map: address to the bitmap memory region
> > + * @start: bit offset of the n-bit value
> > + * @nbits: size of value in bits (must be between 1 and BITS_PER_LONG inclusive).
>
>
> > + *   nbits less than 1 or more than BITS_PER_LONG causes undefined behaviour.
>
> Please, detach this from field description and move to a main description.

Okay. Done.
>
> > + *
> > + * Returns value of nbits located at the @start bit offset within the @map
> > + * memory region.
> > + */
>
> ...
>
> > +             return (map[index] >> offset) & GENMASK(nbits - 1, 0);
>
> Have you considered to use rather BIT{_ULL}(nbits) - 1?
> It maybe better for code generation.

Yes I have considered using BIT{_ULL} in earlier versions of patchset.
It has a problem:

This macro when used in both bitmap_get_value and
bitmap_set_value functions, it will give unexpected results when nbits or clump
size is BITS_PER_LONG (32 or 64 depending on arch).

Actually when nbits (clump size) is 64 (BITS_PER_LONG is 64, for example),
(BIT(nbits) - 1)
gives a value of zero and when this zero is ANDed with any value, it
makes it full zero. This is unexpected, and incorrect calculation occurs.

What actually happens is in the macro expansion of BIT(64), that is 1
<< 64, the '1' overflows from leftmost bit position (most significant
bit) and re-enters at the rightmost bit position (least significant
bit), therefore 1 << 64 becomes '0x1', and when another '1' is
subtracted from this, the final result becomes 0.

This is undefined behavior in the C standard (section 6.5.7 in the N1124)

>
> ...
>
> > +/**
> > + * bitmap_set_value - set n-bit value within a memory region
> > + * @map: address to the bitmap memory region
> > + * @value: value of nbits
> > + * @start: bit offset of the n-bit value
> > + * @nbits: size of value in bits (must be between 1 and BITS_PER_LONG inclusive).
>
> > + *   nbits less than 1 or more than BITS_PER_LONG causes undefined behaviour.
>
> Please, detach this from field description and move to a main description.

Okay. Done

>
> > + */
>
> ...
>
> > +     value &= GENMASK(nbits - 1, 0);
>
> Ditto.
>
> > +             map[index] &= ~(GENMASK(nbits + offset - 1, offset));
>
> Last time I checked such GENMASK) use, it gave a lot of code when
> GENMASK(nbits - 1, 0) << offset works much better, but see also above.

Yes I have incorporated your suggestion to use the '<<' operator. Thank You.


>
> --
> With Best Regards,
> Andy Shevchenko
>
>