| Message ID | 9afc30a574ce3e6a86b51dd522146a1d2156dedd.1553494625.git.vilhelm.gray@gmail.com (mailing list archive) |
|---|---|
| State | Not Applicable, archived |
| Headers | show |
| Series | Introduce the for_each_set_clump8 macro | expand |
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. Thanks, Lukas
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. Actually a good point.
On Mon, Mar 25, 2019 at 03:22:23PM +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. This seems to miss Randy's (IIRC) comment about too many const specifiers. > Suggested-by: Andy Shevchenko <andy.shevchenko@gmail.com> > Suggested-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> > Cc: Arnd Bergmann <arnd@arndb.de> > Acked-by: Andrew Morton <akpm@linux-foundation.org> > Reviewed-by: Andy Shevchenko <andy.shevchenko@gmail.com> > Reviewed-by: Linus Walleij <linus.walleij@linaro.org> > Signed-off-by: William Breathitt Gray <vilhelm.gray@gmail.com> > --- > 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 602af23b98c7..f19a7bc8f559 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..1b6f8a6f1957 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(low_width - 1, 0) << 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 >
On Mon, Mar 25, 2019 at 03:12:36PM +0200, Andy Shevchenko wrote: > On Mon, Mar 25, 2019 at 03:22:23PM +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. > > > This seems to miss Randy's (IIRC) comment about too many const specifiers. I disagree with removing the const qualifiers; I believe they are useful and do not significantly impact the clarity of the code (in fact, I'd argue the opposite). The const qualifiers make it clear these values are constant, allowing readers at a glace to know these values never change within this function. Although I believe GCC is smart enough in this case to deduce implicitly that these are constant values, generally speaking const qualifiers do make it easier for compilers to optimize sections of code (OoO execution, algorithm simplification, etc.), so I believe it's useful in a technical sense as well. I added the const qualifier to these variables because they really are constant, and I believe there is merit in making it explicit in the code. If the primary reason for removing the const qualifiers is for aesthetics, then I must dissent with that decision. However, it is difficult to read the definitions that wrap around to a second line. These definitions are long enough that even removing the const qualifiers would not help prevent the wrapping, so perhaps it would make to let these stay on a single line. Do you think it would help to ignore the 80-character maximum line width coding style rule for these cases here? William Breathitt Gray > > > Suggested-by: Andy Shevchenko <andy.shevchenko@gmail.com> > > Suggested-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> > > Cc: Arnd Bergmann <arnd@arndb.de> > > Acked-by: Andrew Morton <akpm@linux-foundation.org> > > Reviewed-by: Andy Shevchenko <andy.shevchenko@gmail.com> > > Reviewed-by: Linus Walleij <linus.walleij@linaro.org> > > Signed-off-by: William Breathitt Gray <vilhelm.gray@gmail.com> > > --- > > 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 602af23b98c7..f19a7bc8f559 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..1b6f8a6f1957 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(low_width - 1, 0) << 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 > > > > -- > With Best Regards, > Andy Shevchenko > >
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. > > Thanks, > > Lukas 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; Yes, this does seem more efficient to leverage the existing find_next_bit function. Should the offset and size parameters be redefined as unsigned long to match the find_first_bit/find_next_bit function parameters? William Breathitt Gray
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
On Tue, Mar 26, 2019 at 10:43:45AM +0100, Lukas Wunner wrote: > 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: > > 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. u8 might be inconvenient in environment where everything else is type of unsigned long.
On Tue, Mar 26, 2019 at 10:43:45AM +0100, Lukas Wunner wrote: > 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. All right I'll try this setup using round_down() then. > > I'd try to avoid copying around the clump value and use a pointer > to u8 instead. Although in this case we are handling 8-bit clumps, I anticipate device drivers in the future which may benefit from larger size clumps (e.g. GPIO devices with 24-bit ports). It'll be better to define clumps similar to how we're defining bitmaps now (unsigned long *) so that we can support these sizes if need be in the future without requiring data type changes. > > 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). That's a good point. Originally, I had envisioned the possibility of calling bitmap_get_value8/bitmap_set_value8 at odd start offsets; this would open up the possibility of a clump landing as a split between 2 words, thus requiring this complicated case handling code. However, I'm not sure how often users would need this case; none of the drivers right now require clumps at odd offsets. Andy, would you have any objection to restricting the start offset values for bitmap_get_value8/bitmap_set_value8 to multiples of 8? That would prevent the split word case, and thus allow the implementation for those functions to be a lot simpler. William Breathitt Gray > > > > 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
On Tue, Mar 26, 2019 at 07:08:18PM +0900, William Breathitt Gray wrote: > On Tue, Mar 26, 2019 at 10:43:45AM +0100, Lukas Wunner wrote: > > On Tue, Mar 26, 2019 at 12:14:22PM +0900, William Breathitt Gray wrote: > > 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). > > That's a good point. Originally, I had envisioned the possibility of > calling bitmap_get_value8/bitmap_set_value8 at odd start offsets; this > would open up the possibility of a clump landing as a split between 2 > words, thus requiring this complicated case handling code. However, I'm > not sure how often users would need this case; none of the drivers right > now require clumps at odd offsets. > > Andy, would you have any objection to restricting the start offset > values for bitmap_get_value8/bitmap_set_value8 to multiples of 8? That > would prevent the split word case, and thus allow the implementation for > those functions to be a lot simpler. No, I have no objection.
On Tue, Mar 26, 2019 at 12:19:33PM +0200, Andy Shevchenko wrote: > On Tue, Mar 26, 2019 at 07:08:18PM +0900, William Breathitt Gray wrote: > > On Tue, Mar 26, 2019 at 10:43:45AM +0100, Lukas Wunner wrote: > > > On Tue, Mar 26, 2019 at 12:14:22PM +0900, William Breathitt Gray wrote: > > > > 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). > > > > That's a good point. Originally, I had envisioned the possibility of > > calling bitmap_get_value8/bitmap_set_value8 at odd start offsets; this > > would open up the possibility of a clump landing as a split between 2 > > words, thus requiring this complicated case handling code. However, I'm > > not sure how often users would need this case; none of the drivers right > > now require clumps at odd offsets. > > > > Andy, would you have any objection to restricting the start offset > > values for bitmap_get_value8/bitmap_set_value8 to multiples of 8? That > > would prevent the split word case, and thus allow the implementation for > > those functions to be a lot simpler. > > No, I have no objection. > > -- > With Best Regards, > Andy Shevchenko In this case, bitmap_get_value8 could be simplified to something like this: index = BIT_WORD(start); offset = start % BITS_PER_LONG; return (bitmap[index] >> offset) & 0xFF; Or if you prefer a single line: (bitmap[BIT_WORD(start)] >> (start % BITS_PER_LONG)) & 0xFF; Would it be better to define bitmap_get_value8 as a macro then? William Breathitt Gray
On Tue, Mar 26, 2019 at 11:54:59AM +0900, William Breathitt Gray wrote: > On Mon, Mar 25, 2019 at 03:12:36PM +0200, Andy Shevchenko wrote: > > On Mon, Mar 25, 2019 at 03:22:23PM +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. > > > > > > This seems to miss Randy's (IIRC) comment about too many const specifiers. > > I disagree with removing the const qualifiers; I believe they are useful > and do not significantly impact the clarity of the code (in fact, I'd > argue the opposite). Had you checked the assembly? I'm talking about const for values on the stack. I think if you put less const there compiler can keep something in the registers instead of using direct constants or accessing stack. I might be mistaken, so, I can't argue without evidence of either. > The const qualifiers make it clear these values are > constant, allowing readers at a glace to know these values never change > within this function. Although I believe GCC is smart enough in this > case to deduce implicitly that these are constant values, generally > speaking const qualifiers do make it easier for compilers to optimize > sections of code (OoO execution, algorithm simplification, etc.), so I > believe it's useful in a technical sense as well. Again, what the difference do you see in assembly if any? > I added the const qualifier to these variables because they really are > constant, and I believe there is merit in making it explicit in the > code. If the primary reason for removing the const qualifiers is for > aesthetics, then I must dissent with that decision. The point is, if there is no difference, I would prefer one which will be better to read, otherwise check the assembly. > However, it is difficult to read the definitions that wrap around to a > second line. These definitions are long enough that even removing the > const qualifiers would not help prevent the wrapping, so perhaps it > would make to let these stay on a single line. Do you think it would > help to ignore the 80-character maximum line width coding style rule for > these cases here? 80-characters rule can be slightly bended depending on the context. Here, I think, we might continue discussing the matter after having an evidence how const qualifiers affect the code.
On Tue, Mar 26, 2019 at 02:03:19PM +0100, Lukas Wunner wrote: > On Tue, Mar 26, 2019 at 07:08:18PM +0900, William Breathitt Gray wrote: > > On Tue, Mar 26, 2019 at 10:43:45AM +0100, Lukas Wunner wrote: > > In this case, bitmap_get_value8 could be simplified to something like > > this: > > > > index = BIT_WORD(start); > > offset = start % BITS_PER_LONG; > > return (bitmap[index] >> offset) & 0xFF; > > Hm, shouldn't that be "offset = round_down(start, 8)" ? No, the index points to the word, the offset points to the offset inside word. > (I prefer the multi-line version FWIW.) +1 here. > > Would it be better to define bitmap_get_value8 as a macro then? > > Or a static inline. Please, no macro. It disadvantages in terms of type checking.
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 602af23b98c7..f19a7bc8f559 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..1b6f8a6f1957 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(low_width - 1, 0) << 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);