| Message ID | 497dc4b5b1f668b54e008e10a43d4108f4a41213.1553661964.git.vilhelm.gray@gmail.com (mailing list archive) |
|---|---|
| State | Not Applicable, archived |
| Headers | show |
| Series | Introduce the for_each_set_clump8 macro | expand |
On Wed, Mar 27, 2019 at 01:58:45PM +0900, William Breathitt Gray 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. I would have preferred static inlines for bitmap_get_value8(), bitmap_set_value8() and find_next_clump8() to make this as fast as possible in the callers because I've personally worked with an industrial application where the GPIO pins of a 74x164 are written every 250 usec. But apart from that I like this series a lot, thanks for working on it. Lukas
On Wed, Mar 27, 2019 at 01:58:45PM +0900, William Breathitt Gray 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. > +unsigned long bitmap_get_value8(const unsigned long *addr, unsigned long start) > +{ > + const size_t idx = BIT_WORD(start); > + const unsigned long offset = start % BITS_PER_LONG; > + > + return (addr[idx] >> offset) & 0xFF; I would spell index instead of idx, but it's minor and up to you. > +}
On Wed, Mar 27, 2019 at 07:42:54AM +0100, Lukas Wunner wrote: > On Wed, Mar 27, 2019 at 01:58:45PM +0900, William Breathitt Gray 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. > > I would have preferred static inlines for bitmap_get_value8(), > bitmap_set_value8() and find_next_clump8() to make this as fast > as possible in the callers because I've personally worked with > an industrial application where the GPIO pins of a 74x164 are > written every 250 usec. > > But apart from that I like this series a lot, thanks for working on it. > > Lukas I'm not sure these can be static inline since the symbols are exported for use outside this file. However, in theory I have no objection from a performance standpoint. Since my devices don't have such strict realtime requirements as your 74x164 application, I'll defer this decision to someone more knowledgeable in this area; perhaps someone else can comment in this thread with their advice and suggestions. William Breathitt Gray
On Thu, Mar 28, 2019 at 01:30:13PM +0900, William Breathitt Gray wrote: > On Wed, Mar 27, 2019 at 07:42:54AM +0100, Lukas Wunner wrote: > > On Wed, Mar 27, 2019 at 01:58:45PM +0900, William Breathitt Gray 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. > > > > I would have preferred static inlines for bitmap_get_value8(), > > bitmap_set_value8() and find_next_clump8() to make this as fast > > as possible in the callers because I've personally worked with > > an industrial application where the GPIO pins of a 74x164 are > > written every 250 usec. > > I'm not sure these can be static inline since the symbols are exported > for use outside this file. By static inlines I meant that the functions are moved to the appropriate header file in include/linux/. You don't need to worry about exporting in that case as the code is local to each module. For smallish functions like these, static inlines are usually fine. See drivers/dma/virt-dma.h for an extreme case of static inlines (as compared to the much smaller virt-dma.c). Thanks, Lukas
diff --git a/include/asm-generic/bitops/find.h b/include/asm-generic/bitops/find.h index 8a1ee10014de..b0a99035f64f 100644 --- a/include/asm-generic/bitops/find.h +++ b/include/asm-generic/bitops/find.h @@ -80,4 +80,15 @@ 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 *addr, unsigned long start); + +void bitmap_set_value8(unsigned long *addr, unsigned long value, + unsigned long start); + +unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr, + unsigned long size, unsigned long offset); + +#define find_first_clump8(clump, bits, size) \ + find_next_clump8((clump), (bits), (size), 0) + #endif /*_ASM_GENERIC_BITOPS_FIND_H_ */ diff --git a/include/linux/bitops.h b/include/linux/bitops.h index 602af23b98c7..1d9b5efb9bd4 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), (size), (start) + 8)) + 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..71a4e0a31e40 100644 --- a/lib/find_bit.c +++ b/lib/find_bit.c @@ -218,3 +218,61 @@ EXPORT_SYMBOL(find_next_bit_le); #endif #endif /* __BIG_ENDIAN */ + +/** + * bitmap_get_value8 - get an 8-bit value within a memory region + * @addr: address to the bitmap memory region + * @start: bit offset of the 8-bit value; must be a multiple of 8 + * + * Returns the 8-bit value located at the @start bit offset within the @addr + * memory region. + */ +unsigned long bitmap_get_value8(const unsigned long *addr, unsigned long start) +{ + const size_t idx = BIT_WORD(start); + const unsigned long offset = start % BITS_PER_LONG; + + return (addr[idx] >> offset) & 0xFF; +} +EXPORT_SYMBOL(bitmap_get_value8); + +/** + * bitmap_set_value8 - set an 8-bit value within a memory region + * @addr: address to the bitmap memory region + * @value: the 8-bit value; values wider than 8 bits may clobber bitmap + * @start: bit offset of the 8-bit value; must be a multiple of 8 + */ +void bitmap_set_value8(unsigned long *addr, unsigned long value, + unsigned long start) +{ + const size_t idx = BIT_WORD(start); + const unsigned long offset = start % BITS_PER_LONG; + + addr[idx] &= ~(0xFF << offset); + addr[idx] |= value << offset; +} +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 + * @size: bitmap size in number of bits + * @offset: bit offset at which to start searching + * + * 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 long find_next_clump8(unsigned long *clump, const unsigned long *addr, + unsigned long size, unsigned long offset) +{ + offset = find_next_bit(addr, size, offset); + if (offset == size) + return size; + + offset = round_down(offset, 8); + *clump = bitmap_get_value8(addr, offset); + + return offset; +} +EXPORT_SYMBOL(find_next_clump8);
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@gmail.com> Suggested-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Suggested-by: Lukas Wunner <lukas@wunner.de> Cc: Arnd Bergmann <arnd@arndb.de> Cc: Andrew Morton <akpm@linux-foundation.org> Cc: Andy Shevchenko <andy.shevchenko@gmail.com> Cc: Linus Walleij <linus.walleij@linaro.org> Signed-off-by: William Breathitt Gray <vilhelm.gray@gmail.com> --- include/asm-generic/bitops/find.h | 11 ++++++ include/linux/bitops.h | 5 +++ lib/find_bit.c | 58 +++++++++++++++++++++++++++++++ 3 files changed, 74 insertions(+)