| Message ID | 20231025083812.456916-1-glider@google.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | [v9,1/2] lib/bitmap: add bitmap_{read,write}() | expand |
On Wed, Oct 25, 2023 at 10:38:11AM +0200, Alexander Potapenko wrote: > From: Syed Nayyar Waris <syednwaris@gmail.com> > > The two new functions allow reading/writing values of length up to > BITS_PER_LONG bits at arbitrary position in the bitmap. > > The code was taken from "bitops: Introduce the for_each_set_clump macro" > by Syed Nayyar Waris with a number of changes and simplifications: > - instead of using roundup(), which adds an unnecessary dependency > on <linux/math.h>, we calculate space as BITS_PER_LONG-offset; > - indentation is reduced by not using else-clauses (suggested by > checkpatch for bitmap_get_value()); > - bitmap_get_value()/bitmap_set_value() are renamed to bitmap_read() > and bitmap_write(); > - some redundant computations are omitted. ... > * bitmap_to_arr64(buf, src, nbits) Copy nbits from buf to u64[] dst > * bitmap_get_value8(map, start) Get 8bit value from map at start > * bitmap_set_value8(map, value, start) Set 8bit value to map at start > + * bitmap_read(map, start, nbits) Read an nbits-sized value from > + * map at start > + * bitmap_write(map, value, start, nbits) Write an nbits-sized value to > + * map at start I still didn't get the grouping you implied with this... > * Note, bitmap_zero() and bitmap_fill() operate over the region of > * unsigned longs, that is, bits behind bitmap till the unsigned long ... > +/** > + * bitmap_read - read a value of n-bits from the memory region > + * @map: address to the bitmap memory region > + * @start: bit offset of the n-bit value > + * @nbits: size of value in bits, nonzero, up to BITS_PER_LONG > + * > + * Returns: value of nbits located at the @start bit offset within the @map > + * memory region. > + * > + * Note: callers on 32-bit systems must be careful to not attempt reading more > + * than sizeof(unsigned long). sizeof() here is misleading, We talk about bits, BITS_PER_LONG (which is 32), here it's better to be explicit that reading more than 32 bits at a time on 32-bit platform will return 0. Actually what you need is to describe... > + */ > +static inline unsigned long bitmap_read(const unsigned long *map, > + unsigned long start, > + unsigned long nbits) > +{ > + size_t index = BIT_WORD(start); > + unsigned long offset = start % BITS_PER_LONG; > + unsigned long space = BITS_PER_LONG - offset; > + unsigned long value_low, value_high; > + > + if (unlikely(!nbits || nbits > BITS_PER_LONG)) > + return 0; ...this return in the Return section. > + > + if (space >= nbits) > + return (map[index] >> offset) & BITMAP_LAST_WORD_MASK(nbits); > + > + value_low = map[index] & BITMAP_FIRST_WORD_MASK(start); > + value_high = map[index + 1] & BITMAP_LAST_WORD_MASK(start + nbits); > + return (value_low >> offset) | (value_high << space); > +} ... > +/** > + * bitmap_write - write n-bit value within a memory region > + * @map: address to the bitmap memory region > + * @value: value to write, clamped to nbits > + * @start: bit offset of the n-bit value > + * @nbits: size of value in bits, nonzero, up to BITS_PER_LONG. > + * > + * bitmap_write() behaves as-if implemented as @nbits calls of __assign_bit(), > + * i.e. bits beyond @nbits are ignored: > + * > + * for (bit = 0; bit < nbits; bit++) > + * __assign_bit(start + bit, bitmap, val & BIT(bit)); > + * Note: callers on 32-bit systems must be careful to not attempt writing more > + * than sizeof(unsigned long). Ditto. > + */
On Thu, Oct 26, 2023 at 03:15:40PM +0300, Andy Shevchenko wrote: > On Wed, Oct 25, 2023 at 10:38:11AM +0200, Alexander Potapenko wrote: ... > > * bitmap_to_arr64(buf, src, nbits) Copy nbits from buf to u64[] dst > > * bitmap_get_value8(map, start) Get 8bit value from map at start > > * bitmap_set_value8(map, value, start) Set 8bit value to map at start > > + * bitmap_read(map, start, nbits) Read an nbits-sized value from > > + * map at start > > + * bitmap_write(map, value, start, nbits) Write an nbits-sized value to > > + * map at start > > I still didn't get the grouping you implied with this... Ah, sorry, I haven't noticed the descriptions are two-liners.
> > * bitmap_to_arr64(buf, src, nbits) Copy nbits from buf to u64[] dst > > * bitmap_get_value8(map, start) Get 8bit value from map at start > > * bitmap_set_value8(map, value, start) Set 8bit value to map at start > > + * bitmap_read(map, start, nbits) Read an nbits-sized value from > > + * map at start > > + * bitmap_write(map, value, start, nbits) Write an nbits-sized value to > > + * map at start > > I still didn't get the grouping you implied with this... Given your second reply, I can disregard this one, right? > > > * Note, bitmap_zero() and bitmap_fill() operate over the region of > > * unsigned longs, that is, bits behind bitmap till the unsigned long > > ... > > > +/** > > + * bitmap_read - read a value of n-bits from the memory region > > + * @map: address to the bitmap memory region > > + * @start: bit offset of the n-bit value > > + * @nbits: size of value in bits, nonzero, up to BITS_PER_LONG > > + * > > + * Returns: value of nbits located at the @start bit offset within the @map > > + * memory region. > > + * > > + * Note: callers on 32-bit systems must be careful to not attempt reading more > > + * than sizeof(unsigned long). > > sizeof() here is misleading, We talk about bits, BITS_PER_LONG (which is 32), > here it's better to be explicit that reading more than 32 bits at a time on > 32-bit platform will return 0. Actually what you need is to describe... > > > + */ > > +static inline unsigned long bitmap_read(const unsigned long *map, > > + unsigned long start, > > + unsigned long nbits) > > +{ > > + size_t index = BIT_WORD(start); > > + unsigned long offset = start % BITS_PER_LONG; > > + unsigned long space = BITS_PER_LONG - offset; > > + unsigned long value_low, value_high; > > + > > + if (unlikely(!nbits || nbits > BITS_PER_LONG)) > > + return 0; > > ...this return in the Return section. > Parameter description for @nbits actually mentions BITS_PER_LONG already, so would it be ok to drop the Note: and extend the Returns: section as follows: + * Returns: value of nbits located at the @start bit offset within the @map + * memory region. For @nbits = 0 and @nbits > BITS_PER_LONG the return value + * is undefined. ? (Yury didn't want the zero return value to be part of the contract here).
On Thu, Oct 26, 2023 at 03:28:25PM +0200, Alexander Potapenko wrote: ... > > I still didn't get the grouping you implied with this... > > Given your second reply, I can disregard this one, right? Yes. ... > > > + if (unlikely(!nbits || nbits > BITS_PER_LONG)) > > > + return 0; > > > > ...this return in the Return section. > > > > Parameter description for @nbits actually mentions BITS_PER_LONG > already, so would it be ok to drop the Note: and extend the Returns: > section as follows: > > + * Returns: value of nbits located at the @start bit offset within the @map > + * memory region. For @nbits = 0 and @nbits > BITS_PER_LONG the return value > + * is undefined. > > ? Fine to me. > (Yury didn't want the zero return value to be part of the contract here).
diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index 03644237e1efb..d63d5e4b4ab54 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -77,6 +77,10 @@ struct device; * bitmap_to_arr64(buf, src, nbits) Copy nbits from buf to u64[] dst * bitmap_get_value8(map, start) Get 8bit value from map at start * bitmap_set_value8(map, value, start) Set 8bit value to map at start + * bitmap_read(map, start, nbits) Read an nbits-sized value from + * map at start + * bitmap_write(map, value, start, nbits) Write an nbits-sized value to + * map at start * * Note, bitmap_zero() and bitmap_fill() operate over the region of * unsigned longs, that is, bits behind bitmap till the unsigned long @@ -599,6 +603,83 @@ static inline void bitmap_set_value8(unsigned long *map, unsigned long value, map[index] |= value << offset; } +/** + * bitmap_read - read a value of n-bits from the memory region + * @map: address to the bitmap memory region + * @start: bit offset of the n-bit value + * @nbits: size of value in bits, nonzero, up to BITS_PER_LONG + * + * Returns: value of nbits located at the @start bit offset within the @map + * memory region. + * + * Note: callers on 32-bit systems must be careful to not attempt reading more + * than sizeof(unsigned long). + */ +static inline unsigned long bitmap_read(const unsigned long *map, + unsigned long start, + unsigned long nbits) +{ + size_t index = BIT_WORD(start); + unsigned long offset = start % BITS_PER_LONG; + unsigned long space = BITS_PER_LONG - offset; + unsigned long value_low, value_high; + + if (unlikely(!nbits || nbits > BITS_PER_LONG)) + return 0; + + if (space >= nbits) + return (map[index] >> offset) & BITMAP_LAST_WORD_MASK(nbits); + + value_low = map[index] & BITMAP_FIRST_WORD_MASK(start); + value_high = map[index + 1] & BITMAP_LAST_WORD_MASK(start + nbits); + return (value_low >> offset) | (value_high << space); +} + +/** + * bitmap_write - write n-bit value within a memory region + * @map: address to the bitmap memory region + * @value: value to write, clamped to nbits + * @start: bit offset of the n-bit value + * @nbits: size of value in bits, nonzero, up to BITS_PER_LONG. + * + * bitmap_write() behaves as-if implemented as @nbits calls of __assign_bit(), + * i.e. bits beyond @nbits are ignored: + * + * for (bit = 0; bit < nbits; bit++) + * __assign_bit(start + bit, bitmap, val & BIT(bit)); + * + * Note: callers on 32-bit systems must be careful to not attempt writing more + * than sizeof(unsigned long). + */ +static inline void bitmap_write(unsigned long *map, + unsigned long value, + unsigned long start, unsigned long nbits) +{ + size_t index; + unsigned long offset; + unsigned long space; + unsigned long mask; + bool fit; + + if (unlikely(!nbits || nbits > BITS_PER_LONG)) + return; + + mask = BITMAP_LAST_WORD_MASK(nbits); + value &= mask; + offset = start % BITS_PER_LONG; + space = BITS_PER_LONG - offset; + fit = space >= nbits; + index = BIT_WORD(start); + + map[index] &= (fit ? (~(mask << offset)) : ~BITMAP_FIRST_WORD_MASK(start)); + map[index] |= value << offset; + if (fit) + return; + + map[index + 1] &= BITMAP_FIRST_WORD_MASK(start + nbits); + map[index + 1] |= (value >> space); +} + #endif /* __ASSEMBLY__ */ #endif /* __LINUX_BITMAP_H */