diff mbox series

[v10,1/2] lib/bitmap: add bitmap_{read,write}()

Message ID 20231026135912.1214302-1-glider@google.com
State New
Headers
Series [v10,1/2] lib/bitmap: add bitmap_{read,write}() |

Commit Message

Alexander Potapenko Oct. 26, 2023, 1:59 p.m. UTC 
  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/)

v10:
 - update comments as requested by Andy Shevchenko

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 | 78 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 78 insertions(+)

Comments

Andy Shevchenko Oct. 26, 2023, 2:24 p.m. UTC | #1 
On Thu, Oct 26, 2023 at 03:59:11PM +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.

Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>

One nit below, though.

...

> +/**
> + * 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));
> + *
> + * For @nbits > BITS_PER_LONG no writes are performed.

nbits == 0 hasn't been mentioned.

(no, the main nit below)

> + */
> +static inline void bitmap_write(unsigned long *map,
> +				unsigned long value,
> +				unsigned long start, unsigned long nbits)

While noticing strange indentation (you have space for the parameter on
the previous line, I realized that this is a counter-intuitive interface.
Can you actually make value the last parameter?
Alexander Potapenko Oct. 26, 2023, 2:48 p.m. UTC | #2 
>
> Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>

Thanks!

> One nit below, though.
>
> ...
>
> > +/**
> > + * 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));
> > + *
> > + * For @nbits > BITS_PER_LONG no writes are performed.
>
> nbits == 0 hasn't been mentioned.

I can mention it explicitly, but it is already covered by the for-loop
above: if nbits==0, no bits are assigned.

>
> (no, the main nit below)
>
> > + */
> > +static inline void bitmap_write(unsigned long *map,
> > +                             unsigned long value,
> > +                             unsigned long start, unsigned long nbits)
>
> While noticing strange indentation (you have space for the parameter on
> the previous line,

I believe I do not, maybe that's something on your side?
There are tabs in the source, and in the original email.

> I realized that this is a counter-intuitive interface.
> Can you actually make value the last parameter?

It is consistent with bitmap_set_value8(map, value, start), and in all
the functions above @nbits is the last parameter.
Andy Shevchenko Oct. 26, 2023, 8:14 p.m. UTC | #3 
On Thu, Oct 26, 2023 at 04:48:46PM +0200, Alexander Potapenko wrote:

...

> > > +static inline void bitmap_write(unsigned long *map,
> > > +                             unsigned long value,
> > > +                             unsigned long start, unsigned long nbits)
> >
> > While noticing strange indentation (you have space for the parameter on
> > the previous line,
> 
> I believe I do not, maybe that's something on your side?
> There are tabs in the source, and in the original email.

I meant that you can use 2 lines instead of 3:

static inline void bitmap_write(unsigned long *map, unsigned long value,
				unsigned long start, unsigned long nbits)

> > I realized that this is a counter-intuitive interface.
> > Can you actually make value the last parameter?
> 
> It is consistent with bitmap_set_value8(map, value, start), and in all
> the functions above @nbits is the last parameter.

Oh, then I leave this to Yury.
Alexander Potapenko Oct. 27, 2023, 8:03 a.m. UTC | #4 
On Thu, Oct 26, 2023 at 10:14 PM Andy Shevchenko
<andriy.shevchenko@linux.intel.com> wrote:
>
> On Thu, Oct 26, 2023 at 04:48:46PM +0200, Alexander Potapenko wrote:
>
> ...
>
> > > > +static inline void bitmap_write(unsigned long *map,
> > > > +                             unsigned long value,
> > > > +                             unsigned long start, unsigned long nbits)
> > >
> > > While noticing strange indentation (you have space for the parameter on
> > > the previous line,
> >
> > I believe I do not, maybe that's something on your side?
> > There are tabs in the source, and in the original email.
>
> I meant that you can use 2 lines instead of 3:
>
> static inline void bitmap_write(unsigned long *map, unsigned long value,
>                                 unsigned long start, unsigned long nbits)
>
> > > I realized that this is a counter-intuitive interface.
> > > Can you actually make value the last parameter?
> >
> > It is consistent with bitmap_set_value8(map, value, start), and in all
> > the functions above @nbits is the last parameter.
Oh, I see. Let me fix that.
Alexander Potapenko Oct. 27, 2023, 8:11 a.m. UTC | #5 
On Thu, Oct 26, 2023 at 10:14 PM Andy Shevchenko
<andriy.shevchenko@linux.intel.com> wrote:
>
> On Thu, Oct 26, 2023 at 04:48:46PM +0200, Alexander Potapenko wrote:
>
> ...
>
> > > > +static inline void bitmap_write(unsigned long *map,
> > > > +                             unsigned long value,
> > > > +                             unsigned long start, unsigned long nbits)
> > >
> > > While noticing strange indentation (you have space for the parameter on
> > > the previous line,
> >
> > I believe I do not, maybe that's something on your side?
> > There are tabs in the source, and in the original email.
>
> I meant that you can use 2 lines instead of 3:
>
> static inline void bitmap_write(unsigned long *map, unsigned long value,
>                                 unsigned long start, unsigned long nbits)
>

Sorry, my previous reply was incorrectly attributed. I will fix bitmap_write.
diff mbox series

Patch

diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 03644237e1efb..f5745b505a194 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,80 @@  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 bits located at the @start bit offset within the
+ * @map memory region. For @nbits = 0 and @nbits > BITS_PER_LONG the return
+ * value is undefined.
+ */
+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));
+ *
+ * For @nbits > BITS_PER_LONG no writes are performed.
+ */
+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 */