| Message ID | 20221018140027.48086-3-alexandr.lobakin@intel.com (mailing list archive) |
|---|---|
| State | Changes Requested |
| Delegated to: | Netdev Maintainers |
| Headers | show |
| Series | netlink: add universal 'bigint' attribute type | expand |
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
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)); +} + /* * 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. + */ +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
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(-)