[v9,1/9] bitops: Introduce the for_each_set_clump8 macro

Commit Message

William Breathitt Gray March 3, 2019, 7:48 a.m. UTC

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 <[e-mail]>
Suggested-by: Rasmus Villemoes <[e-mail]>
Cc: Arnd Bergmann <[e-mail]>
Cc: Andrew Morton <[e-mail]>
Reviewed-by: Andy Shevchenko <[e-mail]>
Reviewed-by: Linus Walleij <[e-mail]>
Signed-off-by: William Breathitt Gray <[e-mail]>
---
 include/asm-generic/bitops/find.h | 14 ++++++
 include/linux/bitops.h            |  5 ++
 lib/find_bit.c                    | 81 +++++++++++++++++++++++++++++++
 3 files changed, 100 insertions(+)

Comments

Linus Walleij March 8, 2019, 8:31 a.m. UTC | #1

On Sun, Mar 3, 2019 at 8:47 AM William Breathitt Gray
<[e-mail]> 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 <[e-mail]>
> Suggested-by: Rasmus Villemoes <[e-mail]>
> Cc: Arnd Bergmann <[e-mail]>
> Cc: Andrew Morton <[e-mail]>
> Reviewed-by: Andy Shevchenko <[e-mail]>
> Reviewed-by: Linus Walleij <[e-mail]>
> Signed-off-by: William Breathitt Gray <[e-mail]>

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

William Breathitt Gray March 8, 2019, 8:57 a.m. UTC | #2

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
> <[e-mail]> 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 <[e-mail]>
> > Suggested-by: Rasmus Villemoes <[e-mail]>
> > Cc: Arnd Bergmann <[e-mail]>
> > Cc: Andrew Morton <[e-mail]>
> > Reviewed-by: Andy Shevchenko <[e-mail]>
> > Reviewed-by: Linus Walleij <[e-mail]>
> > Signed-off-by: William Breathitt Gray <[e-mail]>
> 
> 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

Andy Shevchenko March 8, 2019, 9:19 a.m. UTC | #3

On Fri, Mar 8, 2019 at 10:56 AM William Breathitt Gray
<[e-mail]> wrote:
> 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
> > <[e-mail]> 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.

> > 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

Yeah, sorry for that. I will use your helpers in the future for sure
in the suitable parts of the code inside and outside of GPIO, just not
in a highest priority to me.

> so I decided to do a quick
> 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.

As I mentioned earlier I'm pretty sure I found as well opportunity to
use this new API
outside of GPIO realm. I just want to be sure (means of testing on real HW).

Andrew Morton March 12, 2019, 1:01 a.m. UTC | #4

On Fri, 8 Mar 2019 09:31:00 +0100 Linus Walleij <[e-mail]> wrote:

> On Sun, Mar 3, 2019 at 8:47 AM William Breathitt Gray
> <[e-mail]> 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 <[e-mail]>
> > Suggested-by: Rasmus Villemoes <[e-mail]>
> > Cc: Arnd Bergmann <[e-mail]>
> > Cc: Andrew Morton <[e-mail]>
> > Reviewed-by: Andy Shevchenko <[e-mail]>
> > Reviewed-by: Linus Walleij <[e-mail]>
> > Signed-off-by: William Breathitt Gray <[e-mail]>
> 
> Andrew: would you be OK with this being merged in v5.1?

Yup.  We have quite a few users there.  I assume this will go via the
gpio tree?

Feel free to add Acked-by: Andrew Morton <[e-mail]>,
although it probably isn't worth churning the git tree to do so at this
late stage - your cvall.

Masahiro Yamada March 12, 2019, 3:52 a.m. UTC | #5

On Sun, Mar 3, 2019 at 4:48 PM William Breathitt Gray
<[e-mail]> 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 <[e-mail]>
> Suggested-by: Rasmus Villemoes <[e-mail]>
> Cc: Arnd Bergmann <[e-mail]>
> Cc: Andrew Morton <[e-mail]>
> Reviewed-by: Andy Shevchenko <[e-mail]>
> Reviewed-by: Linus Walleij <[e-mail]>
> Signed-off-by: William Breathitt Gray <[e-mail]>
> ---
>  include/asm-generic/bitops/find.h | 14 ++++++
>  include/linux/bitops.h            |  5 ++
>  lib/find_bit.c                    | 81 +++++++++++++++++++++++++++++++
>  3 files changed, 100 insertions(+)
>
> diff --git a/include/asm-generic/bitops/find.h b/include/asm-generic/bitops/find.h
> index 8a1ee10014de..9a76adff59c6 100644
> --- a/include/asm-generic/bitops/find.h
> +++ b/include/asm-generic/bitops/find.h
> @@ -80,4 +80,18 @@ extern unsigned long find_first_zero_bit(const unsigned long *addr,
>
>  #endif /* CONFIG_GENERIC_FIND_FIRST_BIT */
>
> +unsigned long bitmap_get_value8(const unsigned long *const bitmap,
> +                               const unsigned int size,
> +                               const unsigned int start);
> +
> +void bitmap_set_value8(unsigned long *const bitmap, const unsigned int size,
> +                      const unsigned long value, const unsigned int start);
> +
> +unsigned int find_next_clump8(unsigned long *const clump,
> +                             const unsigned long *const addr,
> +                             unsigned int offset, const unsigned int size);
> +
> +#define find_first_clump8(clump, bits, size) \
> +       find_next_clump8((clump), (bits), 0, (size))
> +
>  #endif /*_ASM_GENERIC_BITOPS_FIND_H_ */
> diff --git a/include/linux/bitops.h b/include/linux/bitops.h
> index 705f7c442691..61c10f20079e 100644
> --- a/include/linux/bitops.h
> +++ b/include/linux/bitops.h
> @@ -40,6 +40,11 @@ extern unsigned long __sw_hweight64(__u64 w);
>              (bit) < (size);                                    \
>              (bit) = find_next_zero_bit((addr), (size), (bit) + 1))
>
> +#define for_each_set_clump8(start, clump, bits, size) \
> +       for ((start) = find_first_clump8(&(clump), (bits), (size)); \
> +            (start) < (size); \
> +            (start) = find_next_clump8(&(clump), (bits), (start) + 8, (size)))
> +
>  static inline int get_bitmask_order(unsigned int count)
>  {
>         int order;
> diff --git a/lib/find_bit.c b/lib/find_bit.c
> index ee3df93ba69a..c2af1f013ea2 100644
> --- a/lib/find_bit.c
> +++ b/lib/find_bit.c
> @@ -218,3 +218,84 @@ EXPORT_SYMBOL(find_next_bit_le);
>  #endif
>
>  #endif /* __BIG_ENDIAN */
> +
> +/**
> + * bitmap_get_value8 - get an 8-bit value within a memory region
> + * @bitmap: address to the bitmap memory region
> + * @size: bitmap size in number of bits
> + * @start: bit offset of the 8-bit value
> + *
> + * Returns the 8-bit value located at the @start bit offset within the @bitmap
> + * memory region.
> + */
> +unsigned long bitmap_get_value8(const unsigned long *const bitmap,
> +                               const unsigned int size,
> +                               const unsigned int start)


A bunch of 'const' qualifiers are eyesore.

The first 'const' of bitmap is the only useful one.


unsigned long bitmap_get_value8(const unsigned long *bitmap, unsigned int size,
                                unsigned int start)

is enough.





> +{
> +       const size_t index = BIT_WORD(start);
> +       const unsigned int offset = start % BITS_PER_LONG;
> +       const unsigned int low_width = (offset + 8 > BITS_PER_LONG) ?
> +                                      BITS_PER_LONG - offset : 8;
> +       const unsigned long low = bitmap[index] >> offset;
> +       const unsigned long high = (low_width < 8 && start + 8 <= size) ?
> +                                  bitmap[index + 1] << low_width : 0;


Meh.



> +
> +       return (low | high) & 0xFF;
> +}
> +EXPORT_SYMBOL(bitmap_get_value8);
> +
> +/**
> + * bitmap_set_value8 - set an 8-bit value within a memory region
> + * @bitmap: address to the bitmap memory region
> + * @size: bitmap size in number of bits
> + * @value: the 8-bit value; values wider than 8 bits may clobber bitmap
> + * @start: bit offset of the 8-bit value
> + */
> +void bitmap_set_value8(unsigned long *const bitmap, const unsigned int size,
> +                      const unsigned long value, const unsigned int start)
> +{
> +       const size_t index = BIT_WORD(start);
> +       const unsigned int offset = start % BITS_PER_LONG;
> +       const unsigned int low_width = (offset + 8 > BITS_PER_LONG) ?
> +                                      BITS_PER_LONG - offset : 8;
> +       const unsigned long low_mask = GENMASK(offset + low_width - 1, offset);
> +       const unsigned int high_width = 8 - low_width;
> +       const unsigned long high_mask = GENMASK(high_width - 1, 0);
> +
> +       /* set lower portion */
> +       bitmap[index] &= ~low_mask;
> +       bitmap[index] |= value << offset;
> +
> +       /* set higher portion if space available in bitmap */
> +       if (high_width && start + 8 <= size) {
> +               bitmap[index + 1] &= ~high_mask;
> +               bitmap[index + 1] |= value >> low_width;
> +       }
> +}
> +EXPORT_SYMBOL(bitmap_set_value8);
> +
> +/**
> + * 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);
> --
> 2.21.0
>

Masahiro Yamada March 12, 2019, 5:03 a.m. UTC | #6

On Sun, Mar 3, 2019 at 4:48 PM William Breathitt Gray
<[e-mail]> 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 <[e-mail]>
> Suggested-by: Rasmus Villemoes <[e-mail]>
> Cc: Arnd Bergmann <[e-mail]>
> Cc: Andrew Morton <[e-mail]>
> Reviewed-by: Andy Shevchenko <[e-mail]>
> Reviewed-by: Linus Walleij <[e-mail]>
> Signed-off-by: William Breathitt Gray <[e-mail]>
> ---
>  include/asm-generic/bitops/find.h | 14 ++++++
>  include/linux/bitops.h            |  5 ++
>  lib/find_bit.c                    | 81 +++++++++++++++++++++++++++++++
>  3 files changed, 100 insertions(+)
>
> diff --git a/include/asm-generic/bitops/find.h b/include/asm-generic/bitops/find.h
> index 8a1ee10014de..9a76adff59c6 100644
> --- a/include/asm-generic/bitops/find.h
> +++ b/include/asm-generic/bitops/find.h
> @@ -80,4 +80,18 @@ extern unsigned long find_first_zero_bit(const unsigned long *addr,
>
>  #endif /* CONFIG_GENERIC_FIND_FIRST_BIT */
>
> +unsigned long bitmap_get_value8(const unsigned long *const bitmap,
> +                               const unsigned int size,
> +                               const unsigned int start);
> +
> +void bitmap_set_value8(unsigned long *const bitmap, const unsigned int size,
> +                      const unsigned long value, const unsigned int start);
> +
> +unsigned int find_next_clump8(unsigned long *const clump,
> +                             const unsigned long *const addr,
> +                             unsigned int offset, const unsigned int size);
> +
> +#define find_first_clump8(clump, bits, size) \
> +       find_next_clump8((clump), (bits), 0, (size))
> +
>  #endif /*_ASM_GENERIC_BITOPS_FIND_H_ */
> diff --git a/include/linux/bitops.h b/include/linux/bitops.h
> index 705f7c442691..61c10f20079e 100644
> --- a/include/linux/bitops.h
> +++ b/include/linux/bitops.h
> @@ -40,6 +40,11 @@ extern unsigned long __sw_hweight64(__u64 w);
>              (bit) < (size);                                    \
>              (bit) = find_next_zero_bit((addr), (size), (bit) + 1))
>
> +#define for_each_set_clump8(start, clump, bits, size) \
> +       for ((start) = find_first_clump8(&(clump), (bits), (size)); \
> +            (start) < (size); \
> +            (start) = find_next_clump8(&(clump), (bits), (start) + 8, (size)))
> +
>  static inline int get_bitmask_order(unsigned int count)
>  {
>         int order;
> diff --git a/lib/find_bit.c b/lib/find_bit.c
> index ee3df93ba69a..c2af1f013ea2 100644
> --- a/lib/find_bit.c
> +++ b/lib/find_bit.c
> @@ -218,3 +218,84 @@ EXPORT_SYMBOL(find_next_bit_le);
>  #endif
>
>  #endif /* __BIG_ENDIAN */
> +
> +/**
> + * bitmap_get_value8 - get an 8-bit value within a memory region
> + * @bitmap: address to the bitmap memory region
> + * @size: bitmap size in number of bits
> + * @start: bit offset of the 8-bit value
> + *
> + * Returns the 8-bit value located at the @start bit offset within the @bitmap
> + * memory region.
> + */
> +unsigned long bitmap_get_value8(const unsigned long *const bitmap,
> +                               const unsigned int size,
> +                               const unsigned int start)


The comment says this function returns '8-bit value'.

The return type should be 'u8' instead of 'unsigned long', then.

Same for other helpers.



> +{
> +       const size_t index = BIT_WORD(start);
> +       const unsigned int offset = start % BITS_PER_LONG;
> +       const unsigned int low_width = (offset + 8 > BITS_PER_LONG) ?
> +                                      BITS_PER_LONG - offset : 8;
> +       const unsigned long low = bitmap[index] >> offset;
> +       const unsigned long high = (low_width < 8 && start + 8 <= size) ?
> +                                  bitmap[index + 1] << low_width : 0;


I do not know if we have a usecase
where the 'start' is not multiple of 8, though.

Masahiro Yamada March 12, 2019, 5:36 a.m. UTC | #7

On Fri, Mar 8, 2019 at 5:57 PM William Breathitt Gray
<[e-mail]> wrote:
>
> 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
> > <[e-mail]> 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 <[e-mail]>
> > > Suggested-by: Rasmus Villemoes <[e-mail]>
> > > Cc: Arnd Bergmann <[e-mail]>
> > > Cc: Andrew Morton <[e-mail]>
> > > Reviewed-by: Andy Shevchenko <[e-mail]>
> > > Reviewed-by: Linus Walleij <[e-mail]>
> > > Signed-off-by: William Breathitt Gray <[e-mail]>
> >
> > 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


Probably no.


I see this comment before the loop.
/* remove in reverse order */


Also, the unittest code handles per-bit
whereas your helper does per-byte.





> 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.


If we do not find useful cases in other subsystem,
this patch set looks over-engineering to me.






> William Breathitt Gray


--
Best Regards
Masahiro Yamada

Andy Shevchenko March 12, 2019, 7:14 a.m. UTC | #8

On Tue, Mar 12, 2019 at 7:04 AM Masahiro Yamada
<[e-mail]> wrote:
> On Sun, Mar 3, 2019 at 4:48 PM William Breathitt Gray
> <[e-mail]> 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.

> > +/**
> > + * bitmap_get_value8 - get an 8-bit value within a memory region
> > + * @bitmap: address to the bitmap memory region
> > + * @size: bitmap size in number of bits
> > + * @start: bit offset of the 8-bit value
> > + *
> > + * Returns the 8-bit value located at the @start bit offset within the @bitmap
> > + * memory region.
> > + */
> > +unsigned long bitmap_get_value8(const unsigned long *const bitmap,
> > +                               const unsigned int size,
> > +                               const unsigned int start)
>
>
> The comment says this function returns '8-bit value'.
>
> The return type should be 'u8' instead of 'unsigned long', then.
>
> Same for other helpers.

This is done in a way to be consistent with the rest of bitmap API.
None of them returns boolean, for example, for single bit.

William Breathitt Gray March 12, 2019, 7:22 a.m. UTC | #9

On Tue, Mar 12, 2019 at 02:36:21PM +0900, Masahiro Yamada wrote:
> On Fri, Mar 8, 2019 at 5:57 PM William Breathitt Gray
> <[e-mail]> wrote:
> >
> > 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
> > > <[e-mail]> 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 <[e-mail]>
> > > > Suggested-by: Rasmus Villemoes <[e-mail]>
> > > > Cc: Arnd Bergmann <[e-mail]>
> > > > Cc: Andrew Morton <[e-mail]>
> > > > Reviewed-by: Andy Shevchenko <[e-mail]>
> > > > Reviewed-by: Linus Walleij <[e-mail]>
> > > > Signed-off-by: William Breathitt Gray <[e-mail]>
> > >
> > > 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
> 
> 
> Probably no.
> 
> 
> I see this comment before the loop.
> /* remove in reverse order */

You're right, for_each_set_clump8 wouldn't work in this case since it
does not loop in reverse order. I shouldn't have rushed to find a case
and ignored the context of the code like that.

Since Andy appears to have hardware outside of the GPIO subsystem he's
testing, let's wait for that and see how it turns out.

William Breathitt Gray

> 
> 
> Also, the unittest code handles per-bit
> whereas your helper does per-byte.
> 
> 
> 
> 
> 
> > 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.
> 
> 
> If we do not find useful cases in other subsystem,
> this patch set looks over-engineering to me.
> 
> 
> 
> 
> 
> 
> > William Breathitt Gray
> 
> 
> --
> Best Regards
> Masahiro Yamada

William Breathitt Gray March 12, 2019, 10:43 a.m. UTC | #10

On Mon, Mar 11, 2019 at 06:01:13PM -0700, Andrew Morton wrote:
> On Fri, 8 Mar 2019 09:31:00 +0100 Linus Walleij <[e-mail]> wrote:
> 
> > On Sun, Mar 3, 2019 at 8:47 AM William Breathitt Gray
> > <[e-mail]> 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 <[e-mail]>
> > > Suggested-by: Rasmus Villemoes <[e-mail]>
> > > Cc: Arnd Bergmann <[e-mail]>
> > > Cc: Andrew Morton <[e-mail]>
> > > Reviewed-by: Andy Shevchenko <[e-mail]>
> > > Reviewed-by: Linus Walleij <[e-mail]>
> > > Signed-off-by: William Breathitt Gray <[e-mail]>
> > 
> > Andrew: would you be OK with this being merged in v5.1?
> 
> Yup.  We have quite a few users there.  I assume this will go via the
> gpio tree?
> 
> Feel free to add Acked-by: Andrew Morton <[e-mail]>,
> although it probably isn't worth churning the git tree to do so at this
> late stage - your cvall.

Linus,

I discovered a bug in this version of the patchset. I'll release a
version 10 once I've resolved the issue.

William Breathitt Gray

Andy Shevchenko March 12, 2019, 2:54 p.m. UTC | #11

On Tue, Mar 12, 2019 at 04:22:22PM +0900, William Breathitt Gray wrote:

> Since Andy appears to have hardware outside of the GPIO subsystem he's
> testing, let's wait for that and see how it turns out.

Since I have still not much time, here is the driver I'm talking about
drivers/thermal/intel/intel_soc_dts_iosf.c

If you have a chance to look at it (add_dts_thermal_zone(), for example) and
prepare a patch, I will be able to test it on real hardware.

Patch

diff --git a/include/asm-generic/bitops/find.h b/include/asm-generic/bitops/find.h
index 8a1ee10014de..9a76adff59c6 100644
--- a/include/asm-generic/bitops/find.h
+++ b/include/asm-generic/bitops/find.h
@@ -80,4 +80,18 @@  extern unsigned long find_first_zero_bit(const unsigned long *addr,
 
 #endif /* CONFIG_GENERIC_FIND_FIRST_BIT */
 
+unsigned long bitmap_get_value8(const unsigned long *const bitmap,
+				const unsigned int size,
+				const unsigned int start);
+
+void bitmap_set_value8(unsigned long *const bitmap, const unsigned int size,
+		       const unsigned long value, const unsigned int start);
+
+unsigned int find_next_clump8(unsigned long *const clump,
+			      const unsigned long *const addr,
+			      unsigned int offset, const unsigned int size);
+
+#define find_first_clump8(clump, bits, size) \
+	find_next_clump8((clump), (bits), 0, (size))
+
 #endif /*_ASM_GENERIC_BITOPS_FIND_H_ */
diff --git a/include/linux/bitops.h b/include/linux/bitops.h
index 705f7c442691..61c10f20079e 100644
--- a/include/linux/bitops.h
+++ b/include/linux/bitops.h
@@ -40,6 +40,11 @@  extern unsigned long __sw_hweight64(__u64 w);
 	     (bit) < (size);					\
 	     (bit) = find_next_zero_bit((addr), (size), (bit) + 1))
 
+#define for_each_set_clump8(start, clump, bits, size) \
+	for ((start) = find_first_clump8(&(clump), (bits), (size)); \
+	     (start) < (size); \
+	     (start) = find_next_clump8(&(clump), (bits), (start) + 8, (size)))
+
 static inline int get_bitmask_order(unsigned int count)
 {
 	int order;
diff --git a/lib/find_bit.c b/lib/find_bit.c
index ee3df93ba69a..c2af1f013ea2 100644
--- a/lib/find_bit.c
+++ b/lib/find_bit.c
@@ -218,3 +218,84 @@  EXPORT_SYMBOL(find_next_bit_le);
 #endif
 
 #endif /* __BIG_ENDIAN */
+
+/**
+ * bitmap_get_value8 - get an 8-bit value within a memory region
+ * @bitmap: address to the bitmap memory region
+ * @size: bitmap size in number of bits
+ * @start: bit offset of the 8-bit value
+ *
+ * Returns the 8-bit value located at the @start bit offset within the @bitmap
+ * memory region.
+ */
+unsigned long bitmap_get_value8(const unsigned long *const bitmap,
+				const unsigned int size,
+				const unsigned int start)
+{
+	const size_t index = BIT_WORD(start);
+	const unsigned int offset = start % BITS_PER_LONG;
+	const unsigned int low_width = (offset + 8 > BITS_PER_LONG) ?
+				       BITS_PER_LONG - offset : 8;
+	const unsigned long low = bitmap[index] >> offset;
+	const unsigned long high = (low_width < 8 && start + 8 <= size) ?
+				   bitmap[index + 1] << low_width : 0;
+
+	return (low | high) & 0xFF;
+}
+EXPORT_SYMBOL(bitmap_get_value8);
+
+/**
+ * bitmap_set_value8 - set an 8-bit value within a memory region
+ * @bitmap: address to the bitmap memory region
+ * @size: bitmap size in number of bits
+ * @value: the 8-bit value; values wider than 8 bits may clobber bitmap
+ * @start: bit offset of the 8-bit value
+ */
+void bitmap_set_value8(unsigned long *const bitmap, const unsigned int size,
+		       const unsigned long value, const unsigned int start)
+{
+	const size_t index = BIT_WORD(start);
+	const unsigned int offset = start % BITS_PER_LONG;
+	const unsigned int low_width = (offset + 8 > BITS_PER_LONG) ?
+				       BITS_PER_LONG - offset : 8;
+	const unsigned long low_mask = GENMASK(offset + low_width - 1, offset);
+	const unsigned int high_width = 8 - low_width;
+	const unsigned long high_mask = GENMASK(high_width - 1, 0);
+
+	/* set lower portion */
+	bitmap[index] &= ~low_mask;
+	bitmap[index] |= value << offset;
+
+	/* set higher portion if space available in bitmap */
+	if (high_width && start + 8 <= size) {
+		bitmap[index + 1] &= ~high_mask;
+		bitmap[index + 1] |= value >> low_width;
+	}
+}
+EXPORT_SYMBOL(bitmap_set_value8);
+
+/**
+ * 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);