linux-kernel - Re: [PATCH v9 1/9] 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:   Fri, 8 Mar 2019 17:57:33 +0900
From:   William Breathitt Gray <vilhelm.gray@...il.com>
To:     Linus Walleij <linus.walleij@...aro.org>
Cc:     Andrew Morton <akpm@...ux-foundation.org>,
        "open list:GPIO SUBSYSTEM" <linux-gpio@...r.kernel.org>,
        linux-arch@...r.kernel.org,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
        Rasmus Villemoes <linux@...musvillemoes.dk>,
        Masahiro Yamada <yamada.masahiro@...ionext.com>,
        Bartosz Golaszewski <bgolaszewski@...libre.com>,
        Linux ARM <linux-arm-kernel@...ts.infradead.org>,
        Andy Shevchenko <andy.shevchenko@...il.com>,
        Arnd Bergmann <arnd@...db.de>
Subject: Re: [PATCH v9 1/9] bitops: Introduce the for_each_set_clump8 macro

On Fri, Mar 08, 2019 at 09:31:00AM +0100, Linus Walleij wrote:
> On Sun, Mar 3, 2019 at 8:47 AM William Breathitt Gray
> <vilhelm.gray@...il.com> wrote:
> 
> > This macro iterates for each 8-bit 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_value8 and bitmap_set_value8 functions are introduced to
> > respectively get and set an 8-bit value in a bitmap memory region.
> >
> > Suggested-by: Andy Shevchenko <andy.shevchenko@...il.com>
> > Suggested-by: Rasmus Villemoes <linux@...musvillemoes.dk>
> > Cc: Arnd Bergmann <arnd@...db.de>
> > Cc: Andrew Morton <akpm@...ux-foundation.org>
> > Reviewed-by: Andy Shevchenko <andy.shevchenko@...il.com>
> > Reviewed-by: Linus Walleij <linus.walleij@...aro.org>
> > Signed-off-by: William Breathitt Gray <vilhelm.gray@...il.com>
> 
> Andrew: would you be OK with this being merged in v5.1?
> 
> If we need to move the code to drivers/gpio that's OK (though
> I think it's generally useful) but I need to know to proceed with
> the William's nice optimization of these drivers.
> 
> Yours,
> Linus Walleij

I was waiting on Andy to suggest some examples out of the GPIO realm,
but he may be under a heavy workload right so I decided to do a quick
search for one.

In drivers/of/unittest.c, there is loop across a bitmap in the
of_unittest_destroy_tracked_overlays function:

	for (id = MAX_UNITTEST_OVERLAYS - 1; id >= 0; id--) {
		if (!(overlay_id_bits[BIT_WORD(id)] & BIT_MASK(id)))
			continue;

This section of code is checking each bit individually, and skipping if
that bit is not set. This looping can be optimized by using the
for_each_set_clump8 macro to skip clumps of nonset bits (not to mention
make the logic of the code much simpler and easier to follow by reducing
the code to a single line):

	for_each_set_clump8(id, clump, overlay_id_bits, MAX_UNITTEST_OVERLAYS-1)

The for_each_set_clump8 macro is not specific to the GPIO subsystem; I
just happen to use it in these GPIO drivers simply because I am most
familar with this section of the kernel (it's where most of my
contributions occur afterall).

Consider this, if I am able to find a use for this macro outside of the
GPIO subsystem within a matter minutes, then there must be some benefit
in allowing the rest of the kernel to use the for_each_set_clump8 macro.
So let's put it in bitops.h rather than restrict it to just the GPIO
subsystem.

William Breathitt Gray