linux-kernel - Re: [PATCH 1/6] bitops: Introduce the 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: <20200424150828.GA5034@icarus>
Date:   Fri, 24 Apr 2020 11:09:26 -0400
From:   William Breathitt Gray <vilhelm.gray@...il.com>
To:     Lukas Wunner <lukas@...ner.de>
Cc:     Syed Nayyar Waris <syednwaris@...il.com>,
        akpm@...ux-foundation.org, andriy.shevchenko@...ux.intel.com,
        arnd@...db.de, Linus Walleij <linus.walleij@...aro.org>,
        linux-arch@...r.kernel.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH 1/6] bitops: Introduce the the for_each_set_clump macro

On Fri, Apr 24, 2020 at 05:00:58PM +0200, Lukas Wunner wrote:
> On Fri, Apr 24, 2020 at 08:22:38PM +0530, Syed Nayyar Waris wrote:
> > On Fri, Apr 24, 2020 at 7:40 PM Lukas Wunner <lukas@...ner.de> wrote:
> > >
> > > On Fri, Apr 24, 2020 at 05:55:21PM +0530, Syed Nayyar Waris wrote:
> > > > +static inline void bitmap_set_value(unsigned long *map,
> > > > +                                 unsigned long value,
> > > > +                                 unsigned long start, unsigned long nbits)
> > > > +{
> > > > +     const size_t index = BIT_WORD(start);
> > > > +     const unsigned long offset = start % BITS_PER_LONG;
> > > > +     const unsigned long ceiling = roundup(start + 1, BITS_PER_LONG);
> > > > +     const unsigned long space = ceiling - start;
> > > > +
> > > > +     value &= GENMASK(nbits - 1, 0);
> > > > +
> > > > +     if (space >= nbits) {
> > > > +             map[index] &= ~(GENMASK(nbits + offset - 1, offset));
> > > > +             map[index] |= value << offset;
> > > > +     } else {
> > > > +             map[index] &= ~BITMAP_FIRST_WORD_MASK(start);
> > > > +             map[index] |= value << offset;
> > > > +             map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits);
> > > > +             map[index + 1] |= (value >> space);
> > > > +     }
> > > > +}
> > >
> > > Sorry but what's the advantage of using this complicated function
> > > as a replacement for the much simpler bitmap_set_value8()?
> > >
> > > The drivers calling bitmap_set_value8() *know* that 8-bit accesses
> > > are possible and take advantage of that knowledge by using a small,
> > > speed-optimized function.  Replacing that with a more complicated
> > > (potentially less performant) function doesn't seem to be a step
> > > forward.
> > 
> > Actually this generic function can work with n-bits of any size (less
> > than equal to BITS_PER_LONG), while the earlier bitmap_set_value8
> > worked with n-bits having size of 8 bits only.
> > 
> > In the case when n-bits is 8-bits, this new bitmap_set_value()
> > function would behave very similar to the earlier bitmap_set_value8()
> > function. For example,  in case of n-bits being 8-bits it will always
> > execute the 'if' condition and not the 'else' condition, hence
> > offering the same performance (because of encountering similar code
> > statements) as earlier bitmap_set_value8() function, most probably.
> > 
> > There is an additional advantage (this can happen when n-bits is not 8
> > bits): 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.
> > 
> > So, this function preserves the behaviour of earlier
> > bitmap_set_value8() function and also adds extra functionality to
> > that.
> 
> Please leave drivers as is which use exclusively 8-bit accesses,
> e.g. gpio-max3191x.c and gpio-74x164.c.  I'm fearing a performance
> regression if your new generic variant is used.  They work perfectly
> fine the way they are and I don't see any benefit this series may have
> for them.
> 
> If there are other drivers which benefit from the flexibility of your
> generic variant then I'm not opposed to changing those.
> 
> Thanks,
> 
> Lukas

We can leave of course bitmap_set_value8 alone, but for 8-bit values the
difference in latency I suspect is primarily due to the conditional test
for the word boundaries. This latency is surely overshadowed by the I/O
latency of the GPIO drivers, so I don't think there's much harm in
changing those to use the generic function when the bottleneck will not
be due to the bitmap_set_value/bitmap_get_value operations.

William Breathitt Gray

Download attachment "signature.asc" of type "application/pgp-signature" (834 bytes)