linux-kernel - Re: [PATCH v12 01/11] 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]

Date:   Tue, 26 Mar 2019 10:43:45 +0100
From:   Lukas Wunner <lukas@...ner.de>
To:     William Breathitt Gray <vilhelm.gray@...il.com>
Cc:     linus.walleij@...aro.org, bgolaszewski@...libre.com,
        akpm@...ux-foundation.org, linux-gpio@...r.kernel.org,
        linux-arch@...r.kernel.org, linux-kernel@...r.kernel.org,
        andriy.shevchenko@...ux.intel.com, linux@...musvillemoes.dk,
        yamada.masahiro@...ionext.com,
        linux-arm-kernel@...ts.infradead.org, linux-pm@...r.kernel.org,
        geert@...ux-m68k.org, preid@...ctromag.com.au,
        Andy Shevchenko <andy.shevchenko@...il.com>,
        Arnd Bergmann <arnd@...db.de>
Subject: Re: [PATCH v12 01/11] bitops: Introduce the for_each_set_clump8 macro

On Tue, Mar 26, 2019 at 12:14:22PM +0900, William Breathitt Gray wrote:
> On Mon, Mar 25, 2019 at 10:38:54AM +0100, Lukas Wunner wrote:
> > On Mon, Mar 25, 2019 at 03:22:23PM +0900, William Breathitt Gray wrote:
> > > +/**
> > > + * find_next_clump8 - find next 8-bit clump with set bits in a memory region
> > > + * @clump: location to store copy of found clump
> > > + * @addr: address to base the search on
> > > + * @offset: bit offset at which to start searching
> > > + * @size: bitmap size in number of bits
> > > + *
> > > + * Returns the bit offset for the next set clump; the found clump value is
> > > + * copied to the location pointed by @clump. If no bits are set, returns @size.
> > > + */
> > > +unsigned int find_next_clump8(unsigned long *const clump,
> > > +			      const unsigned long *const addr,
> > > +			      unsigned int offset, const unsigned int size)
> > > +{
> > > +	for (; offset < size; offset += 8) {
> > > +		*clump = bitmap_get_value8(addr, size, offset);
> > > +		if (!*clump)
> > > +			continue;
> > > +
> > > +		return offset;
> > > +	}
> > > +
> > > +	return size;
> > > +}
> > > +EXPORT_SYMBOL(find_next_clump8);
> > 
> > Just use find_first_bit() / find_next_bit() to use optimized arch-specific
> > bitops instead of open-coding the iteration over the bitmap.
> > 
> > See max3191x_get_multiple() for an example.
> 
> Is this the sort of implementation you had in mind:
> 
>         offset = find_next_bit(addr, size, offset);
>         if (offset == size)
>                 return size;
> 
>         offset -= offset % 8;
>         *clump = bitmap_get_value8(addr, size, offset);
> 
>         return offset;

Almost.  I'd use round_down() instead of "offset -= offset % 8".
Then it's just a single cheap logical and operation at runtime.

I'd try to avoid copying around the clump value and use a pointer
to u8 instead.

I don't understand the calculations in bitmap_get_value8() at all.
Why is it so complicated, does it allow passing in a start value
that's not a multiple of 8?  Do you really need that?  I imagine
a simplification is possible if that assumption can be made (and
is spelled out in the kerneldoc).


> Should the offset and size parameters be redefined as unsigned long to
> match the find_first_bit/find_next_bit function parameters?

Yes, probably.  It's just the CPU's native length anyway.

Thanks,

Lukas