[v9,1/2] lib/bitmap: add bitmap_{read,write}()
Commit Message
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.
Cc: Arnd Bergmann <arnd@arndb.de>
Signed-off-by: Syed Nayyar Waris <syednwaris@gmail.com>
Signed-off-by: William Breathitt Gray <william.gray@linaro.org>
Link: https://lore.kernel.org/lkml/fe12eedf3666f4af5138de0e70b67a07c7f40338.1592224129.git.syednwaris@gmail.com/
Suggested-by: Yury Norov <yury.norov@gmail.com>
Co-developed-by: Alexander Potapenko <glider@google.com>
Signed-off-by: Alexander Potapenko <glider@google.com>
---
This patch was previously part of the "Implement MTE tag compression for
swapped pages" series
(https://lore.kernel.org/linux-arm-kernel/20231011172836.2579017-4-glider@google.com/T/)
This patch was previously called "lib/bitmap: add
bitmap_{set,get}_value()"
(https://lore.kernel.org/lkml/20230720173956.3674987-2-glider@google.com/)
v8:
- as suggested by Andy Shevchenko, handle reads/writes of more than
BITS_PER_LONG bits, add a note for 32-bit systems
v7:
- Address comments by Yury Norov, Andy Shevchenko, Rasmus Villemoes:
- update code comments;
- get rid of GENMASK();
- s/assign_bit/__assign_bit;
- more vertical whitespace for better readability;
- more compact code for bitmap_write() (now for real)
v6:
- As suggested by Yury Norov, do not require bitmap_read(..., 0) to
return 0.
v5:
- Address comments by Yury Norov:
- updated code comments and patch title/description
- replace GENMASK(nbits - 1, 0) with BITMAP_LAST_WORD_MASK(nbits)
- more compact bitmap_write() implementation
v4:
- Address comments by Andy Shevchenko and Yury Norov:
- prevent passing values >= 64 to GENMASK()
- fix commit authorship
- change comments
- check for unlikely(nbits==0)
- drop unnecessary const declarations
- fix kernel-doc comments
- rename bitmap_{get,set}_value() to bitmap_{read,write}()
---
include/linux/bitmap.h | 81 ++++++++++++++++++++++++++++++++++++++++++
1 file changed, 81 insertions(+)
Comments
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).
@@ -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 */