[v2,net-next,2/6] bitmap: add a couple more helpers to work with arrays of u32s
Commit Message
Add two new functions to work on arr32s:
* bitmap_arr32_size() - takes number of bits to be stored in arr32
and returns number of bytes required to store such arr32, can be
useful when allocating memory for arr32 containers;
* bitmap_validate_arr32() - takes pointer to an arr32 and its size
in bytes, plus expected number of bits. Ensures that the size is
valid (must be a multiply of `sizeof(u32)`) and no bits past the
number is set.
Also add BITMAP_TO_U64() macro to help return a u64 from
a DECLARE_BITMAP(1-64) (it may pick one or two longs depending
on the platform).
Signed-off-by: Alexander Lobakin <alexandr.lobakin@intel.com>
---
include/linux/bitmap.h | 20 +++++++++++++++++++-
lib/bitmap.c | 40 ++++++++++++++++++++++++++++++++++++++++
2 files changed, 59 insertions(+), 1 deletion(-)
Comments
On Tue, Oct 18, 2022 at 04:00:23PM +0200, Alexander Lobakin wrote:
> Add two new functions to work on arr32s:
>
> * bitmap_arr32_size() - takes number of bits to be stored in arr32
> and returns number of bytes required to store such arr32, can be
> useful when allocating memory for arr32 containers;
> * bitmap_validate_arr32() - takes pointer to an arr32 and its size
> in bytes, plus expected number of bits. Ensures that the size is
> valid (must be a multiply of `sizeof(u32)`) and no bits past the
> number is set.
>
> Also add BITMAP_TO_U64() macro to help return a u64 from
> a DECLARE_BITMAP(1-64) (it may pick one or two longs depending
> on the platform).
Can you make BITMAP_TO_U64() a separate patch? Maybe fold it into a
first patch that uses it, but I think it worth to be a real commit.
> Signed-off-by: Alexander Lobakin <alexandr.lobakin@intel.com>
> ---
> include/linux/bitmap.h | 20 +++++++++++++++++++-
> lib/bitmap.c | 40 ++++++++++++++++++++++++++++++++++++++++
> 2 files changed, 59 insertions(+), 1 deletion(-)
>
> diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
> index 79d12e0f748b..c737b0fe2f41 100644
> --- a/include/linux/bitmap.h
> +++ b/include/linux/bitmap.h
> @@ -7,7 +7,7 @@
> #include <linux/align.h>
> #include <linux/bitops.h>
> #include <linux/find.h>
> -#include <linux/limits.h>
> +#include <linux/overflow.h>
> #include <linux/string.h>
> #include <linux/types.h>
>
> @@ -75,6 +75,8 @@ struct device;
> * bitmap_from_arr64(dst, buf, nbits) Copy nbits from u64[] buf to dst
> * bitmap_to_arr32(buf, src, nbits) Copy nbits from buf to u32[] dst
> * bitmap_to_arr64(buf, src, nbits) Copy nbits from buf to u64[] dst
> + * bitmap_validate_arr32(buf, len, nbits) Validate u32[] buf of len bytes
> + * bitmap_arr32_size(nbits) Get size of u32[] arr for nbits
> * 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
> *
> @@ -324,6 +326,20 @@ static inline void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap,
> __bitmap_to_arr32(buf, bitmap, nbits);
> }
>
> +bool bitmap_validate_arr32(const u32 *arr, size_t len, size_t nbits);
> +
> +/**
> + * bitmap_arr32_size - determine the size of array of u32s for a number of bits
> + * @nbits: number of bits to store in the array
> + *
> + * Returns the size in bytes of a u32s-array needed to carry the specified
> + * number of bits.
> + */
> +static inline size_t bitmap_arr32_size(size_t nbits)
> +{
> + return array_size(BITS_TO_U32(nbits), sizeof(u32));
To me this looks simpler: round_up(nbits, 32) / BITS_PER_BYTE.
Can you check which generates better code?
> +}
This is not specific to bitmaps in general. Can you put it somewhere in
include/linux/bitops.h next to BITS_TO_U32().
Regarding a name - maybe BITS_TO_U32_SIZE()? Not very elegant, but
assuming that size is always measured in bytes, it should be
understandable
> /*
> * On 64-bit systems bitmaps are represented as u64 arrays internally. On LE32
> * machines the order of hi and lo parts of numbers match the bitmap structure.
> @@ -571,9 +587,11 @@ static inline void bitmap_next_set_region(unsigned long *bitmap,
> */
> #if __BITS_PER_LONG == 64
> #define BITMAP_FROM_U64(n) (n)
> +#define BITMAP_TO_U64(map) ((u64)(map)[0])
> #else
> #define BITMAP_FROM_U64(n) ((unsigned long) ((u64)(n) & ULONG_MAX)), \
> ((unsigned long) ((u64)(n) >> 32))
> +#define BITMAP_TO_U64(map) (((u64)(map)[1] << 32) | (u64)(map)[0])
> #endif
>
> /**
> diff --git a/lib/bitmap.c b/lib/bitmap.c
> index e3eb12ff1637..e0045ecf34d6 100644
> --- a/lib/bitmap.c
> +++ b/lib/bitmap.c
> @@ -1495,6 +1495,46 @@ void __bitmap_to_arr32(u32 *buf, const unsigned long *bitmap, unsigned int nbits
> EXPORT_SYMBOL(__bitmap_to_arr32);
> #endif
>
> +/**
> + * bitmap_validate_arr32 - perform validation of a u32-array bitmap
> + * @arr: array of u32s, the dest bitmap
> + * @len: length of the array, in bytes
> + * @nbits: expected/supported number of bits in the bitmap
> + *
> + * Returns true if the array passes the checks (see below), false otherwise.
> + */
In kernel-docs this would look completely useless. Can you explain
what it checks in the comment too?
> +bool bitmap_validate_arr32(const u32 *arr, size_t len, size_t nbits)
> +{
> + size_t word = (nbits - 1) / BITS_PER_TYPE(u32);
> + u32 pos = (nbits - 1) % BITS_PER_TYPE(u32);
What if nbits == 0? What if arr == NULL or unaligned? Assuming you don't
trust caller too much, you'd check arguments better.
> +
> + /* Must consist of 1...n full u32s */
> + if (!len || len % sizeof(u32))
> + return false;
Can you check this before calculating word and pos?
> + /*
> + * If the array is shorter than expected, assume we support
> + * all of the bits set there.
> + */
> + if (word >= len / sizeof(u32))
> + return true;
If an array is shorter than expected, it usually means ENOMEM. Is
there a real use-case for this check?
> + /* Last word must not contain any bits past the expected number */
> + if (arr[word] & (u32)~GENMASK(pos, 0))
> + return false;
We have BITMAP_LAST_WORD_MASK() macro for this.
> + /*
> + * If the array is longer than expected, make sure all the bytes
> + * past the expected length are zeroed.
> + */
> + len -= bitmap_arr32_size(nbits);
> + if (memchr_inv(&arr[word + 1], 0, len))
> + return false;
Instead of true/false, I would return a meaningful error or 0. In this
case, ERANGE or EDOM would seemingly fit well.
> +
> + return true;
> +}
> +EXPORT_SYMBOL(bitmap_validate_arr32);
> +
> #if (BITS_PER_LONG == 32) && defined(__BIG_ENDIAN)
> /**
> * bitmap_from_arr64 - copy the contents of u64 array of bits to bitmap
> --
> 2.37.3
On Wed, Oct 19, 2022 at 05:21:01PM -0700, Yury Norov wrote:
> On Tue, Oct 18, 2022 at 04:00:23PM +0200, Alexander Lobakin wrote:
...
> > +static inline size_t bitmap_arr32_size(size_t nbits)
> > +{
> > + return array_size(BITS_TO_U32(nbits), sizeof(u32));
>
> To me this looks simpler: round_up(nbits, 32) / BITS_PER_BYTE.
> Can you check which generates better code?
It's not only about better code, but also about overflow protection, which your
proposal is missing.
> > +}
On Thu, Oct 20, 2022 at 04:18:08PM +0300, Andy Shevchenko wrote:
> On Wed, Oct 19, 2022 at 05:21:01PM -0700, Yury Norov wrote:
> > On Tue, Oct 18, 2022 at 04:00:23PM +0200, Alexander Lobakin wrote:
>
> ...
>
> > > +static inline size_t bitmap_arr32_size(size_t nbits)
> > > +{
> > > + return array_size(BITS_TO_U32(nbits), sizeof(u32));
> >
> > To me this looks simpler: round_up(nbits, 32) / BITS_PER_BYTE.
> > Can you check which generates better code?
>
> It's not only about better code, but also about overflow protection, which your
> proposal is missing.
Can you explain how this may overflow?
#define __round_mask(x, y) ((__typeof__(x))((y)-1))
#define round_up(x, y) ((((x)-1) | __round_mask(x, y))+1)
Thanks,
Yury
@@ -7,7 +7,7 @@
#include <linux/align.h>
#include <linux/bitops.h>
#include <linux/find.h>
-#include <linux/limits.h>
+#include <linux/overflow.h>
#include <linux/string.h>
#include <linux/types.h>
@@ -75,6 +75,8 @@ struct device;
* bitmap_from_arr64(dst, buf, nbits) Copy nbits from u64[] buf to dst
* bitmap_to_arr32(buf, src, nbits) Copy nbits from buf to u32[] dst
* bitmap_to_arr64(buf, src, nbits) Copy nbits from buf to u64[] dst
+ * bitmap_validate_arr32(buf, len, nbits) Validate u32[] buf of len bytes
+ * bitmap_arr32_size(nbits) Get size of u32[] arr for nbits
* 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
*
@@ -324,6 +326,20 @@ static inline void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap,
__bitmap_to_arr32(buf, bitmap, nbits);
}
+bool bitmap_validate_arr32(const u32 *arr, size_t len, size_t nbits);
+
+/**
+ * bitmap_arr32_size - determine the size of array of u32s for a number of bits
+ * @nbits: number of bits to store in the array
+ *
+ * Returns the size in bytes of a u32s-array needed to carry the specified
+ * number of bits.
+ */
+static inline size_t bitmap_arr32_size(size_t nbits)
+{
+ return array_size(BITS_TO_U32(nbits), sizeof(u32));
+}
+
/*
* On 64-bit systems bitmaps are represented as u64 arrays internally. On LE32
* machines the order of hi and lo parts of numbers match the bitmap structure.
@@ -571,9 +587,11 @@ static inline void bitmap_next_set_region(unsigned long *bitmap,
*/
#if __BITS_PER_LONG == 64
#define BITMAP_FROM_U64(n) (n)
+#define BITMAP_TO_U64(map) ((u64)(map)[0])
#else
#define BITMAP_FROM_U64(n) ((unsigned long) ((u64)(n) & ULONG_MAX)), \
((unsigned long) ((u64)(n) >> 32))
+#define BITMAP_TO_U64(map) (((u64)(map)[1] << 32) | (u64)(map)[0])
#endif
/**
@@ -1495,6 +1495,46 @@ void __bitmap_to_arr32(u32 *buf, const unsigned long *bitmap, unsigned int nbits
EXPORT_SYMBOL(__bitmap_to_arr32);
#endif
+/**
+ * bitmap_validate_arr32 - perform validation of a u32-array bitmap
+ * @arr: array of u32s, the dest bitmap
+ * @len: length of the array, in bytes
+ * @nbits: expected/supported number of bits in the bitmap
+ *
+ * Returns true if the array passes the checks (see below), false otherwise.
+ */
+bool bitmap_validate_arr32(const u32 *arr, size_t len, size_t nbits)
+{
+ size_t word = (nbits - 1) / BITS_PER_TYPE(u32);
+ u32 pos = (nbits - 1) % BITS_PER_TYPE(u32);
+
+ /* Must consist of 1...n full u32s */
+ if (!len || len % sizeof(u32))
+ return false;
+
+ /*
+ * If the array is shorter than expected, assume we support
+ * all of the bits set there.
+ */
+ if (word >= len / sizeof(u32))
+ return true;
+
+ /* Last word must not contain any bits past the expected number */
+ if (arr[word] & (u32)~GENMASK(pos, 0))
+ return false;
+
+ /*
+ * If the array is longer than expected, make sure all the bytes
+ * past the expected length are zeroed.
+ */
+ len -= bitmap_arr32_size(nbits);
+ if (memchr_inv(&arr[word + 1], 0, len))
+ return false;
+
+ return true;
+}
+EXPORT_SYMBOL(bitmap_validate_arr32);
+
#if (BITS_PER_LONG == 32) && defined(__BIG_ENDIAN)
/**
* bitmap_from_arr64 - copy the contents of u64 array of bits to bitmap