[PATCH v2 net-next 0/6] netlink: add universal 'bigint' attribute type

[PATCH v2 net-next 0/6] netlink: add universal 'bigint' attribute type

[Alexander Lobakin]

Add a new type of Netlink attribute -- big integer.

Basically bigints are just arrays of u32s, but can carry anything,
with 1 bit precision. Using variable-length arrays of a fixed type
gives the following:

* versatility: one type can carry scalars from u8 to u64, bitmaps,
  binary data etc.;
* scalability: the same Netlink attribute can be changed to a wider
  (or shorter) data type with no compatibility issues, same for
  growing bitmaps;
* optimization: 4-byte units don't require wasting slots for empty
  padding attributes (they always have natural alignment in Netlink
  messages).

The only downside is that get/put functions sometimes are not just
direct assignment inlines due to the internal representation using
bitmaps (longs) and the bitmap API. The first patch in the series
partially addresses that.

Basic consumer functions/macros are:
* nla_put_bigint() and nla_get_bigint() -- to easily put a bigint to
  an skb or get it from a received message (only pointer to an
  unsigned long array and the number of bits in it are needed);
* nla_put_bigint_{u,be,le,net}{8,16,32,64}() -- alternatives to the
  already existing family to send/receive scalars using the new type
  (instead of distinct attr types);
* nla_total_size_bigint*() -- to provide estimate size in bytes to
  Netlink needed to store a bigint/type;
* NLA_POLICY_BIGINT*() -- to declare a Netlink policy for a bigint
  attribute.

There are also *_bitmap() aliases for the *_bigint() helpers which
have no differences and designed to distinguish bigints from bitmaps
in the call sites (for readability).

Netlink policy for a bigint can have an optional bitmap mask of bits
supported by the code -- for example, to filter out obsolete bits
removed some time ago or limit value to n bits (e.g. 53 instead of
64). Without it, Netlink will just make sure no bits past the passed
number are set. Both variants can be requested from the userspace
and the kernel will put a mask into a new policy attribute
(%NL_POLICY_TYPE_ATTR_BIGINT_MASK).
Unlike BITFIELD32 or Ethtool bitsets, bigints don't implement
"selectors" as a basic feature, but it's pretty easy to emulate it
with just sending both selector and value in one data chunk (as these
bigints are dynamically-sized) and masking unused gaps between them
with the bitmap mask policy feature.

An example of using this API can be found in my IP tunnel tree[0]
(to be submitted after that one hits the repo), the actual average
number of locs to start both sending and receiving bitmaps in one
subsys is ~10. And it looks like that some of the already existing
APIs could be later converted to Netlink bigints or expanded as
well.

And here's sample userspace output for failed in-kernel validation --
IP tunnel flags attribute was declared as 17-bit bitmap/bigint, but
the modified userspace passed data with the 20th bit set:

$ ip/ip r add 14.0.1.8 encap ip id 30001 dst 10.0.18.210 dev vxlan1
Policy: type: BIGINT, mask: 0x0003ffff
Error: Attribute failed policy validation.

From v1[1]:
 - use u32-array representation instead of u64-array to conserve
   attributes (no need to have "padding" dummy attrs) and some bytes
   (4-byte step instead of 8-byte) (Jakub);
 - try to resolve arr32 <-> bitmap conversions on 64-bit LEs to
   inline code at compile-time to reduce get/set overhead (me);
 - drop Endianness shenanigans: it makes no sense to encode bitmaps/
   arrays to a specific Endian (Jakub);
 - rename it from 'bitmap' to 'bigint' to increase usecase coverage
   (Jakub);
 - introduce helpers to send scalars (u8-u64) via the API to make it
   universal / more useful (Jakub);
 - change kfree() to bitmap_free() when freeing allocated bitmaps
   (Andy);
 - make BYTES_TO_BITS() treewide-available and use it (Andy);
 - make bitmap_validate_arr32() return `bool`: there were only two
   return values possible (Andy);
 - drop redundant `!!len` check before memchr_inv() call: the
   function does that itself (Andy);
 - expand the #if 0 presence explanation (Andy);
 - add runtime tests for the new arr32 functions: 5 test cases that
   cover all condition branches (Andy);
 - run make includecheck, ensure including <linux/bitmap.h> to
   <net/netlink.h> doesn't introduce compile time regressions,
   mention that in the commitmsg (Andy);
 - drop more redundant `if (len)` condition checks before string
   operations (Andy);
 - make bitmap_arr32_compat() and bitmap_{from,to}_arr32() a bit
   more readable (Andy);
 - don't use `min_t(typeof())`, specify types explicitly (Andy);
 - don't initialize the bitmap two times in a row in
   __netlink_policy_dump_write_attr_bigint() and use more simple
   bitmap_fill(): nla_put_bigint() will then clear the tail
   properly itself (Andy).

The series is also available on my open GitHub: [2]

[0] https://github.com/alobakin/linux/commits/ip_tunnel
[1] https://lore.kernel.org/all/20220721155950.747251-1-alexandr.lobakin@intel.com
[2] https://github.com/alobakin/linux/commits/netlink_bitmap

Alexander Lobakin (6):
  bitmap: try to optimize arr32 <-> bitmap on 64-bit LEs
  bitmap: add a couple more helpers to work with arrays of u32s
  lib/test_bitmap: verify intermediate arr32 when converting <-> bitmap
  lib/test_bitmap: test the newly added arr32 functions
  bitops: make BYTES_TO_BITS() treewide-available
  netlink: add universal 'bigint' attribute type

 include/linux/bitmap.h         |  71 ++++++++---
 include/linux/bitops.h         |   1 +
 include/net/netlink.h          | 208 ++++++++++++++++++++++++++++++++-
 include/uapi/linux/netlink.h   |   6 +
 kernel/trace/trace_probe.c     |   2 -
 lib/bitmap.c                   |  52 ++++++++-
 lib/nlattr.c                   |  42 ++++++-
 lib/test_bitmap.c              |  47 ++++++++
 net/netlink/policy.c           |  40 +++++++
 tools/include/linux/bitops.h   |   1 +
 tools/perf/util/probe-finder.c |   2 -
 11 files changed, 445 insertions(+), 27 deletions(-)


base-commit: f00909e2e6fe4ac6b2420e3863a0c533fe4f15e0
-- 
2.37.3

[PATCH v2 net-next 1/6] bitmap: try to optimize arr32 <-> bitmap on 64-bit LEs

[Alexander Lobakin]

Unlike bitmap_{from,to}_arr64(), when there can be no out-of-bounds
accesses (due to u64 always being no shorter than unsigned long),
it can't be guaranteed with arr32s due to that on 64-bit platforms:

bits     BITS_TO_U32 * sizeof(u32)    BITS_TO_LONGS * sizeof(long)
1-32     4                            8
33-64    8                            8
95-96    12                           16
97-128   16                           16

and so on.
That is why bitmap_{from,to}_arr32() are always defined there as
externs. But quite often @nbits is a compile-time constant, which
means we could suggest whether it can be inlined or not at
compile-time basing on the number of bits (above).

So, try to determine that at compile time and, in case of both
containers having the same size in bytes, resolve it to
bitmap_copy_clear_tail() on Little Endian. No changes here for
Big Endian or when the number of bits *really* is variable.

Signed-off-by: Alexander Lobakin <alexandr.lobakin@intel.com>
---
 include/linux/bitmap.h | 51 ++++++++++++++++++++++++++++++------------
 lib/bitmap.c           | 12 +++++-----
 2 files changed, 43 insertions(+), 20 deletions(-)

diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 7d6d73b78147..79d12e0f748b 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -283,24 +283,47 @@ static inline void bitmap_copy_clear_tail(unsigned long *dst,
  * On 32-bit systems bitmaps are represented as u32 arrays internally. On LE64
  * machines the order of hi and lo parts of numbers match the bitmap structure.
  * In both cases conversion is not needed when copying data from/to arrays of
- * u32. But in LE64 case, typecast in bitmap_copy_clear_tail() may lead
- * to out-of-bound access. To avoid that, both LE and BE variants of 64-bit
- * architectures are not using bitmap_copy_clear_tail().
+ * u32. But in LE64 case, typecast in bitmap_copy_clear_tail() may lead to
+ * out-of-bound access. To avoid that, LE variant of 64-bit architectures uses
+ * bitmap_copy_clear_tail() only when @bitmap and @buf containers have the same
+ * size in memory (known at compile time), and 64-bit BEs never use it.
  */
-#if BITS_PER_LONG == 64
-void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf,
-							unsigned int nbits);
-void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap,
-							unsigned int nbits);
+#if BITS_PER_LONG == 32
+#define bitmap_arr32_compat(nbits)		true
+#elif defined(__LITTLE_ENDIAN)
+#define bitmap_arr32_compat(nbits)		\
+	(__builtin_constant_p(nbits) &&		\
+	 BITS_TO_U32(nbits) * sizeof(u32) ==	\
+	 BITS_TO_LONGS(nbits) * sizeof(long))
 #else
-#define bitmap_from_arr32(bitmap, buf, nbits)			\
-	bitmap_copy_clear_tail((unsigned long *) (bitmap),	\
-			(const unsigned long *) (buf), (nbits))
-#define bitmap_to_arr32(buf, bitmap, nbits)			\
-	bitmap_copy_clear_tail((unsigned long *) (buf),		\
-			(const unsigned long *) (bitmap), (nbits))
+#define bitmap_arr32_compat(nbits)		false
 #endif
 
+void __bitmap_from_arr32(unsigned long *bitmap, const u32 *buf, unsigned int nbits);
+void __bitmap_to_arr32(u32 *buf, const unsigned long *bitmap, unsigned int nbits);
+
+static inline void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf,
+				     unsigned int nbits)
+{
+	const unsigned long *src = (const unsigned long *)buf;
+
+	if (bitmap_arr32_compat(nbits))
+		bitmap_copy_clear_tail(bitmap, src, nbits);
+	else
+		__bitmap_from_arr32(bitmap, buf, nbits);
+}
+
+static inline void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap,
+				   unsigned int nbits)
+{
+	unsigned long *dst = (unsigned long *)buf;
+
+	if (bitmap_arr32_compat(nbits))
+		bitmap_copy_clear_tail(dst, bitmap, nbits);
+	else
+		__bitmap_to_arr32(buf, bitmap, nbits);
+}
+
 /*
  * 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.
diff --git a/lib/bitmap.c b/lib/bitmap.c
index 1c81413c51f8..e3eb12ff1637 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -1449,12 +1449,12 @@ EXPORT_SYMBOL_GPL(devm_bitmap_zalloc);
 
 #if BITS_PER_LONG == 64
 /**
- * bitmap_from_arr32 - copy the contents of u32 array of bits to bitmap
+ * __bitmap_from_arr32 - copy the contents of u32 array of bits to bitmap
  *	@bitmap: array of unsigned longs, the destination bitmap
  *	@buf: array of u32 (in host byte order), the source bitmap
  *	@nbits: number of bits in @bitmap
  */
-void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf, unsigned int nbits)
+void __bitmap_from_arr32(unsigned long *bitmap, const u32 *buf, unsigned int nbits)
 {
 	unsigned int i, halfwords;
 
@@ -1469,15 +1469,15 @@ void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf, unsigned int nbits
 	if (nbits % BITS_PER_LONG)
 		bitmap[(halfwords - 1) / 2] &= BITMAP_LAST_WORD_MASK(nbits);
 }
-EXPORT_SYMBOL(bitmap_from_arr32);
+EXPORT_SYMBOL(__bitmap_from_arr32);
 
 /**
- * bitmap_to_arr32 - copy the contents of bitmap to a u32 array of bits
+ * __bitmap_to_arr32 - copy the contents of bitmap to a u32 array of bits
  *	@buf: array of u32 (in host byte order), the dest bitmap
  *	@bitmap: array of unsigned longs, the source bitmap
  *	@nbits: number of bits in @bitmap
  */
-void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap, unsigned int nbits)
+void __bitmap_to_arr32(u32 *buf, const unsigned long *bitmap, unsigned int nbits)
 {
 	unsigned int i, halfwords;
 
@@ -1492,7 +1492,7 @@ void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap, unsigned int nbits)
 	if (nbits % BITS_PER_LONG)
 		buf[halfwords - 1] &= (u32) (UINT_MAX >> ((-nbits) & 31));
 }
-EXPORT_SYMBOL(bitmap_to_arr32);
+EXPORT_SYMBOL(__bitmap_to_arr32);
 #endif
 
 #if (BITS_PER_LONG == 32) && defined(__BIG_ENDIAN)
-- 
2.37.3

[PATCH v2 net-next 2/6] bitmap: add a couple more helpers to work with arrays of u32s

[Alexander Lobakin]

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(-)

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
-- 
2.37.3

[PATCH v2 net-next 3/6] lib/test_bitmap: verify intermediate arr32 when converting <-> bitmap

[Alexander Lobakin]

When testing converting bitmaps from/to arr32, use
bitmap_validate_arr32() to test whether the tail of the intermediate
array was cleared correctly. Previously there were checks only for
the actual bitmap generated with the double-conversion.
Note that we pass bitmap_arr32_size() instead of `sizeof(arr)`, as
we poison the bytes past the last used word with 0xa5s. Also, for
@nbits == 0, the validation function must return false, account that
case as well.

Signed-off-by: Alexander Lobakin <alexandr.lobakin@intel.com>
---
 lib/test_bitmap.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
index a8005ad3bd58..c40ab3dfa776 100644
--- a/lib/test_bitmap.c
+++ b/lib/test_bitmap.c
@@ -605,6 +605,7 @@ static void __init test_bitmap_arr32(void)
 	unsigned int nbits, next_bit;
 	u32 arr[EXP1_IN_BITS / 32];
 	DECLARE_BITMAP(bmap2, EXP1_IN_BITS);
+	bool valid;
 
 	memset(arr, 0xa5, sizeof(arr));
 
@@ -620,6 +621,9 @@ static void __init test_bitmap_arr32(void)
 				" tail is not safely cleared: %d\n",
 				nbits, next_bit);
 
+		valid = bitmap_validate_arr32(arr, bitmap_arr32_size(nbits), nbits);
+		expect_eq_uint(!!nbits, valid);
+
 		if (nbits < EXP1_IN_BITS - 32)
 			expect_eq_uint(arr[DIV_ROUND_UP(nbits, 32)],
 								0xa5a5a5a5);
-- 
2.37.3

[PATCH v2 net-next 4/6] lib/test_bitmap: test the newly added arr32 functions

[Alexander Lobakin]

Add a couple of trivial test cases, which will trial three newly
added helpers to work with arr32s:

* bitmap_validate_arr32() -- test all the branches the function can
  take when validating;
* bitmap_arr32_size() -- sometimes is also called inside the
  previous one;
* BITMAP_TO_U64() -- testing it casted to u32 against arr32[0].

Suggested-by: Andy Shevchenko <andy.shevchenko@linux.intel.com>
Signed-off-by: Alexander Lobakin <alexandr.lobakin@intel.com>
---
 lib/test_bitmap.c | 43 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 43 insertions(+)

diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
index c40ab3dfa776..f168f0a79e4f 100644
--- a/lib/test_bitmap.c
+++ b/lib/test_bitmap.c
@@ -600,6 +600,36 @@ static void __init test_bitmap_parse(void)
 	}
 }
 
+static const struct {
+	DECLARE_BITMAP(bitmap, 128);
+	u32 nbits;
+	u32 msglen;
+	u32 exp_size;
+	u32 exp_valid:1;
+} arr32_test_cases[] __initconst = {
+#define BITMAP_ARR32_CASE(h, l, nr, len, ev, es) {	\
+	.bitmap = {					\
+		BITMAP_FROM_U64(l),			\
+		BITMAP_FROM_U64(h),			\
+	},						\
+	.nbits = (nr),					\
+	.msglen = (len),				\
+	.exp_valid = (ev),				\
+	.exp_size = (es),				\
+}
+	/* fail: msglen is not a multiple of 4 */
+	BITMAP_ARR32_CASE(0x00000000, 0x0000accedeadfeed, 48,  6, false,  8),
+	/* pass: kernel supports more bits than received */
+	BITMAP_ARR32_CASE(0x00000000, 0xacdcbadadd0afc18, 90,  8, true,  12),
+	/* fail: unsupported bits set within the last supported word */
+	BITMAP_ARR32_CASE(0xfa588103, 0xd3d0a58544864a9c, 88, 12, false, 12),
+	/* fail: unsupported bits set past the last supported word */
+	BITMAP_ARR32_CASE(0x00b84e53, 0x0000a3bafb6484f8, 64, 16, false,  8),
+	/* pass: kernel supports less bits than received, no unsupported set */
+	BITMAP_ARR32_CASE(0x00000000, 0x848d7a2acc7ff31e, 64, 16, true,   8),
+#undef BITMAP_ARR32_CASE
+};
+
 static void __init test_bitmap_arr32(void)
 {
 	unsigned int nbits, next_bit;
@@ -628,6 +658,19 @@ static void __init test_bitmap_arr32(void)
 			expect_eq_uint(arr[DIV_ROUND_UP(nbits, 32)],
 								0xa5a5a5a5);
 	}
+
+	for (u32 i = 0; i < ARRAY_SIZE(arr32_test_cases); i++) {
+		typeof(*arr32_test_cases) *test = &arr32_test_cases[i];
+
+		memset(arr, 0, sizeof(arr));
+		bitmap_to_arr32(arr, test->bitmap, BYTES_TO_BITS(test->msglen));
+
+		valid = bitmap_validate_arr32(arr, test->msglen, test->nbits);
+		expect_eq_uint(test->exp_valid, valid);
+
+		expect_eq_uint(test->exp_size, bitmap_arr32_size(test->nbits));
+		expect_eq_uint((u32)BITMAP_TO_U64(test->bitmap), arr[0]);
+	}
 }
 
 static void __init test_bitmap_arr64(void)
-- 
2.37.3

[PATCH v2 net-next 5/6] bitops: make BYTES_TO_BITS() treewide-available

[Alexander Lobakin]

Avoid open-coding that simple expression each time by moving
BYTES_TO_BITS() from the probes code to <linux/bitops.h> to export
it to the rest of the kernel.
Do the same for the tools ecosystem as well (incl. its version of
bitops.h).

Suggested-by: Andy Shevchenko <andy.shevchenko@linux.intel.com>
Signed-off-by: Alexander Lobakin <alexandr.lobakin@intel.com>
---
 include/linux/bitops.h         | 1 +
 kernel/trace/trace_probe.c     | 2 --
 tools/include/linux/bitops.h   | 1 +
 tools/perf/util/probe-finder.c | 2 --
 4 files changed, 2 insertions(+), 4 deletions(-)

diff --git a/include/linux/bitops.h b/include/linux/bitops.h
index 2ba557e067fe..e11f19f96853 100644
--- a/include/linux/bitops.h
+++ b/include/linux/bitops.h
@@ -20,6 +20,7 @@
 #define BITS_TO_U64(nr)		__KERNEL_DIV_ROUND_UP(nr, BITS_PER_TYPE(u64))
 #define BITS_TO_U32(nr)		__KERNEL_DIV_ROUND_UP(nr, BITS_PER_TYPE(u32))
 #define BITS_TO_BYTES(nr)	__KERNEL_DIV_ROUND_UP(nr, BITS_PER_TYPE(char))
+#define BYTES_TO_BITS(nb)	((nb) * BITS_PER_LONG / sizeof(long))
 
 extern unsigned int __sw_hweight8(unsigned int w);
 extern unsigned int __sw_hweight16(unsigned int w);
diff --git a/kernel/trace/trace_probe.c b/kernel/trace/trace_probe.c
index 36dff277de46..89e73eebc72c 100644
--- a/kernel/trace/trace_probe.c
+++ b/kernel/trace/trace_probe.c
@@ -523,8 +523,6 @@ parse_probe_arg(char *arg, const struct fetch_type *type,
 	return ret;
 }
 
-#define BYTES_TO_BITS(nb)	((BITS_PER_LONG * (nb)) / sizeof(long))
-
 /* Bitfield type needs to be parsed into a fetch function */
 static int __parse_bitfield_probe_arg(const char *bf,
 				      const struct fetch_type *t,
diff --git a/tools/include/linux/bitops.h b/tools/include/linux/bitops.h
index f18683b95ea6..aee8667ce941 100644
--- a/tools/include/linux/bitops.h
+++ b/tools/include/linux/bitops.h
@@ -19,6 +19,7 @@
 #define BITS_TO_U64(nr)		DIV_ROUND_UP(nr, BITS_PER_TYPE(u64))
 #define BITS_TO_U32(nr)		DIV_ROUND_UP(nr, BITS_PER_TYPE(u32))
 #define BITS_TO_BYTES(nr)	DIV_ROUND_UP(nr, BITS_PER_TYPE(char))
+#define BYTES_TO_BITS(nb)	((nb) * BITS_PER_LONG / sizeof(long))
 
 extern unsigned int __sw_hweight8(unsigned int w);
 extern unsigned int __sw_hweight16(unsigned int w);
diff --git a/tools/perf/util/probe-finder.c b/tools/perf/util/probe-finder.c
index 50d861a80f57..2a0b7aacabc0 100644
--- a/tools/perf/util/probe-finder.c
+++ b/tools/perf/util/probe-finder.c
@@ -304,8 +304,6 @@ static int convert_variable_location(Dwarf_Die *vr_die, Dwarf_Addr addr,
 	return ret2;
 }
 
-#define BYTES_TO_BITS(nb)	((nb) * BITS_PER_LONG / sizeof(long))
-
 static int convert_variable_type(Dwarf_Die *vr_die,
 				 struct probe_trace_arg *tvar,
 				 const char *cast, bool user_access)
-- 
2.37.3

[PATCH v2 net-next 6/6] netlink: add universal 'bigint' attribute type

[Alexander Lobakin]

Add a new type of Netlink attribute -- big integer.

Basically bigints are just arrays of u32s, but can carry anything,
with 1 bit precision. Using variable-length arrays of a fixed type
gives the following:

* versatility: one type can carry scalars from u8 to u64, bitmaps,
  binary data etc.;
* scalability: the same Netlink attribute can be changed to a wider
  (or shorter) data type with no compatibility issues, same for
  growing bitmaps;
* optimization: 4-byte units don't require wasting slots for empty
  padding attributes (they always have natural alignment in Netlink
  messages).

The only downside is that get/put functions sometimes are not just
direct assignment inlines due to the internal representation using
bitmaps (longs) and the bitmap API.

Basic consumer functions/macros are:
* nla_put_bigint() and nla_get_bigint() -- to easily put a bigint to
  an skb or get it from a received message (only pointer to an
  unsigned long array and the number of bits in it are needed);
* nla_put_bigint_{u,be,le,net}{8,16,32,64}() -- alternatives to the
  already existing family to send/receive scalars using the new type
  (instead of distinct attr types);
* nla_total_size_bigint*() -- to provide estimate size in bytes to
  Netlink needed to store a bigint/type;
* NLA_POLICY_BIGINT*() -- to declare a Netlink policy for a bigint
  attribute.

There are also *_bitmap() aliases for the *_bigint() helpers which
have no differences and designed to distinguish bigints from bitmaps
in the call sites (for readability).

Netlink policy for a bigint can have an optional bitmap mask of bits
supported by the code -- for example, to filter out obsolete bits
removed some time ago or limit value to n bits (e.g. 53 instead of
64). Without it, Netlink will just make sure no bits past the passed
number are set. Both variants can be requested from the userspace
and the kernel will put a mask into a new policy attribute
(%NL_POLICY_TYPE_ATTR_BIGINT_MASK).

Note on including <linux/bitmap.h> into <net/netlink.h>: seems to
introduce no visible compilation time regressions, make includecheck
doesn't see anything illegit as well. Hiding everything inside
lib/nlattr.c would require making a couple dozens optimizable
inlines external, doesn't sound optimal.

Suggested-by: Jakub Kicinski <kuba@kernel.org> # NLA_BITMAP -> NLA_BIGINT
Signed-off-by: Alexander Lobakin <alexandr.lobakin@intel.com>
---
 include/net/netlink.h        | 208 ++++++++++++++++++++++++++++++++++-
 include/uapi/linux/netlink.h |   6 +
 lib/nlattr.c                 |  42 ++++++-
 net/netlink/policy.c         |  40 +++++++
 4 files changed, 294 insertions(+), 2 deletions(-)

diff --git a/include/net/netlink.h b/include/net/netlink.h
index 4418b1981e31..2b7194e7a540 100644
--- a/include/net/netlink.h
+++ b/include/net/netlink.h
@@ -2,7 +2,7 @@
 #ifndef __NET_NETLINK_H
 #define __NET_NETLINK_H
 
-#include <linux/types.h>
+#include <linux/bitmap.h>
 #include <linux/netlink.h>
 #include <linux/jiffies.h>
 #include <linux/in6.h>
@@ -180,6 +180,7 @@ enum {
 	NLA_S32,
 	NLA_S64,
 	NLA_BITFIELD32,
+	NLA_BIGINT,
 	NLA_REJECT,
 	__NLA_TYPE_MAX,
 };
@@ -235,12 +236,15 @@ enum nla_policy_validation {
  *                         given type fits, using it verifies minimum length
  *                         just like "All other"
  *    NLA_BITFIELD32       Unused
+ *    NLA_BIGINT           Number of bits in the big integer
  *    NLA_REJECT           Unused
  *    All other            Minimum length of attribute payload
  *
  * Meaning of validation union:
  *    NLA_BITFIELD32       This is a 32-bit bitmap/bitselector attribute and
  *                         `bitfield32_valid' is the u32 value of valid flags
+ *    NLA_BIGINT           `bigint_mask` is a pointer to the mask of the valid
+ *                         bits of the given bigint to perform the validation.
  *    NLA_REJECT           This attribute is always rejected and `reject_message'
  *                         may point to a string to report as the error instead
  *                         of the generic one in extended ACK.
@@ -327,6 +331,7 @@ struct nla_policy {
 			s16 min, max;
 			u8 network_byte_order:1;
 		};
+		const unsigned long *bigint_mask;
 		int (*validate)(const struct nlattr *attr,
 				struct netlink_ext_ack *extack);
 		/* This entry is special, and used for the attribute at index 0
@@ -451,6 +456,35 @@ struct nla_policy {
 }
 #define NLA_POLICY_MIN_LEN(_len)	NLA_POLICY_MIN(NLA_BINARY, _len)
 
+/**
+ * NLA_POLICY_BIGINT - represent &nla_policy for a bigint attribute
+ * @nbits - number of bits in the bigint
+ * @... - optional pointer to a bitmap carrying a mask of supported bits
+ */
+#define NLA_POLICY_BIGINT(nbits, ...) {					\
+	.type = NLA_BIGINT,						\
+	.len = (nbits),							\
+	.bigint_mask =							\
+		(typeof((__VA_ARGS__ + 0) ? : NULL))(__VA_ARGS__ + 0),	\
+	.validation_type = (__VA_ARGS__ + 0) ? NLA_VALIDATE_MASK : 0,	\
+}
+
+/* Simplify (and encourage) using the bigint type to send scalars */
+#define NLA_POLICY_BIGINT_TYPE(type, ...)				\
+	NLA_POLICY_BIGINT(BITS_PER_TYPE(type), ##__VA_ARGS__)
+
+#define NLA_POLICY_BIGINT_U8		NLA_POLICY_BIGINT_TYPE(u8)
+#define NLA_POLICY_BIGINT_U16		NLA_POLICY_BIGINT_TYPE(u16)
+#define NLA_POLICY_BIGINT_U32		NLA_POLICY_BIGINT_TYPE(u32)
+#define NLA_POLICY_BIGINT_U64		NLA_POLICY_BIGINT_TYPE(u64)
+
+/* Transparent alias (for readability purposes) */
+#define NLA_POLICY_BITMAP(nbits, ...)					\
+	NLA_POLICY_BIGINT((nbits), ##__VA_ARGS__)
+
+#define nla_policy_bigint_mask(pt)	((pt)->bigint_mask)
+#define nla_policy_bigint_nbits(pt)	((pt)->len)
+
 /**
  * struct nl_info - netlink source information
  * @nlh: Netlink message header of original request
@@ -1556,6 +1590,28 @@ static inline int nla_put_bitfield32(struct sk_buff *skb, int attrtype,
 	return nla_put(skb, attrtype, sizeof(tmp), &tmp);
 }
 
+/**
+ * nla_put_bigint - Add a bigint Netlink attribute to a socket buffer
+ * @skb: socket buffer to add attribute to
+ * @attrtype: attribute type
+ * @bigint: bigint to put, as array of unsigned longs
+ * @nbits: number of bits in the bigint
+ */
+static inline int nla_put_bigint(struct sk_buff *skb, int attrtype,
+				 const unsigned long *bigint,
+				 size_t nbits)
+{
+	struct nlattr *nla;
+
+	nla = nla_reserve(skb, attrtype, bitmap_arr32_size(nbits));
+	if (unlikely(!nla))
+		return -EMSGSIZE;
+
+	bitmap_to_arr32(nla_data(nla), bigint, nbits);
+
+	return 0;
+}
+
 /**
  * nla_get_u32 - return payload of u32 attribute
  * @nla: u32 netlink attribute
@@ -1749,6 +1805,134 @@ static inline struct nla_bitfield32 nla_get_bitfield32(const struct nlattr *nla)
 	return tmp;
 }
 
+/**
+ * nla_get_bigint - Return a bigint from u32-array bigint Netlink attribute
+ * @nla: %NLA_BIGINT Netlink attribute
+ * @bigint: target container, as array of unsigned longs
+ * @nbits: expected number of bits in the bigint
+ */
+static inline void nla_get_bigint(const struct nlattr *nla,
+				  unsigned long *bigint,
+				  size_t nbits)
+{
+	size_t diff = BITS_TO_LONGS(nbits);
+
+	/* Core validated nla_len() is (n + 1) * sizeof(u32), leave a hint */
+	nbits = clamp_t(size_t, BYTES_TO_BITS(nla_len(nla)),
+			BITS_PER_TYPE(u32), nbits);
+	bitmap_from_arr32(bigint, nla_data(nla), nbits);
+
+	diff -= BITS_TO_LONGS(nbits);
+	memset(bigint + BITS_TO_LONGS(nbits), 0, diff * sizeof(long));
+}
+
+/* The macros below build the following set of functions, allowing to
+ * easily use the %NLA_BIGINT API to send scalar values. Their fake
+ * declarations are provided under #if 0, so that source code indexers
+ * could build references to them.
+ */
+#if 0
+int nla_put_bigint_s8(struct sk_buff *skb, int attrtype, __s8 value);
+__s8 nla_get_bigint_s8(const struct nlattr *nla);
+int nla_put_bigint_s16(struct sk_buff *skb, int attrtype, __s16 value);
+__s16 nla_get_bigint_s16(const struct nlattr *nla);
+int nla_put_bigint_s32(struct sk_buff *skb, int attrtype, __s32 value);
+__s32 nla_get_bigint_s32(const struct nlattr *nla);
+int nla_put_bigint_s64(struct sk_buff *skb, int attrtype, __s64 value);
+__s64 nla_get_bigint_s64(const struct nlattr *nla);
+
+int nla_put_bigint_u8(struct sk_buff *skb, int attrtype, __u8 value);
+__u8 nla_get_bigint_u8(const struct nlattr *nla);
+int nla_put_bigint_u16(struct sk_buff *skb, int attrtype, __u16 value);
+__u16 nla_get_bigint_u16(const struct nlattr *nla);
+int nla_put_bigint_u32(struct sk_buff *skb, int attrtype, __u32 value);
+__u32 nla_get_bigint_u32(const struct nlattr *nla);
+int nla_put_bigint_u64(struct sk_buff *skb, int attrtype, __u64 value);
+__u64 nla_get_bigint_u64(const struct nlattr *nla);
+
+int nla_put_bigint_be16(struct sk_buff *skb, int attrtype, __be16 value);
+__be16 nla_get_bigint_be16(const struct nlattr *nla);
+int nla_put_bigint_be32(struct sk_buff *skb, int attrtype, __be32 value);
+__be32 nla_get_bigint_be32(const struct nlattr *nla);
+int nla_put_bigint_be64(struct sk_buff *skb, int attrtype, __be64 value);
+__be64 nla_get_bigint_be64(const struct nlattr *nla);
+
+int nla_put_bigint_le16(struct sk_buff *skb, int attrtype, __le16 value);
+__le16 nla_get_bigint_le16(const struct nlattr *nla);
+int nla_put_bigint_le32(struct sk_buff *skb, int attrtype, __le32 value);
+__le32 nla_get_bigint_le32(const struct nlattr *nla);
+int nla_put_bigint_le64(struct sk_buff *skb, int attrtype, __le64 value);
+__le64 nla_get_bigint_le64(const struct nlattr *nla);
+
+int nla_put_bigint_net16(struct sk_buff *skb, int attrtype, __be16 value);
+__be16 nla_get_bigint_net16(const struct nlattr *nla);
+int nla_put_bigint_net32(struct sk_buff *skb, int attrtype, __be32 value);
+__be32 nla_get_bigint_net32(const struct nlattr *nla);
+int nla_put_bigint_net64(struct sk_buff *skb, int attrtype, __be64 value);
+__be64 nla_get_bigint_net64(const struct nlattr *nla);
+#endif
+
+#define NLA_BUILD_BIGINT_TYPE(type)					 \
+static inline int							 \
+nla_put_bigint_##type(struct sk_buff *skb, int attrtype, __##type value) \
+{									 \
+	DECLARE_BITMAP(bigint, BITS_PER_TYPE(u64)) = {			 \
+		BITMAP_FROM_U64((__force u64)value),			 \
+	};								 \
+									 \
+	return nla_put_bigint(skb, attrtype, bigint,			 \
+			      BITS_PER_TYPE(__##type));			 \
+}									 \
+									 \
+static inline __##type							 \
+nla_get_bigint_##type(const struct nlattr *nla)				 \
+{									 \
+	DECLARE_BITMAP(bigint, BITS_PER_TYPE(u64));			 \
+									 \
+	nla_get_bigint(nla, bigint, BITS_PER_TYPE(__##type));		 \
+									 \
+	return (__force __##type)BITMAP_TO_U64(bigint);			 \
+}
+
+#define NLA_BUILD_BIGINT_NET(width)					 \
+static inline int							 \
+nla_put_bigint_net##width(struct sk_buff *skb, int attrtype,		 \
+			  __be##width value)				 \
+{									 \
+	return nla_put_bigint_be##width(skb,				 \
+					attrtype | NLA_F_NET_BYTEORDER,  \
+					value);				 \
+}									 \
+									 \
+static inline __be##width						 \
+nla_get_bigint_net##width(const struct nlattr *nla)			 \
+{									 \
+	return nla_get_bigint_be##width(nla);				 \
+}
+
+#define NLA_BUILD_BIGINT_ORDER(order)					 \
+	NLA_BUILD_BIGINT_TYPE(order##16);				 \
+	NLA_BUILD_BIGINT_TYPE(order##32);				 \
+	NLA_BUILD_BIGINT_TYPE(order##64)
+
+NLA_BUILD_BIGINT_TYPE(s8);
+NLA_BUILD_BIGINT_TYPE(u8);
+
+NLA_BUILD_BIGINT_ORDER(s);
+NLA_BUILD_BIGINT_ORDER(u);
+NLA_BUILD_BIGINT_ORDER(be);
+NLA_BUILD_BIGINT_ORDER(le);
+
+NLA_BUILD_BIGINT_NET(16);
+NLA_BUILD_BIGINT_NET(32);
+NLA_BUILD_BIGINT_NET(64);
+
+/* Aliases for readability */
+#define nla_put_bitmap(skb, attrtype, bitmap, nbits)			 \
+	nla_put_bigint((skb), (attrtype), (bitmap), (nbits))
+#define nla_get_bitmap(nlattr, bitmap, nbits)				 \
+	nla_get_bigint((nlattr), (bitmap), (nbits))
+
 /**
  * nla_memdup - duplicate attribute memory (kmemdup)
  * @src: netlink attribute to duplicate from
@@ -1921,6 +2105,28 @@ static inline int nla_total_size_64bit(int payload)
 		;
 }
 
+/**
+ * nla_total_size_bigint - get total size of Netlink attr for a number of bits
+ * @nbits: number of bits to store in the attribute
+ *
+ * Returns the size in bytes of a Netlink attribute needed to carry
+ * the specified number of bits.
+ */
+static inline size_t nla_total_size_bigint(size_t nbits)
+{
+	return nla_total_size(bitmap_arr32_size(nbits));
+}
+
+#define nla_total_size_bigint_type(type)		\
+	nla_total_size_bigint(BITS_PER_TYPE(type))
+
+#define nla_total_size_bigint_u8()	nla_total_size_bigint_type(u8)
+#define nla_total_size_bigint_u16()	nla_total_size_bigint_type(u16)
+#define nla_total_size_bigint_u32()	nla_total_size_bigint_type(u32)
+#define nla_total_size_bigint_u64()	nla_total_size_bigint_type(u64)
+
+#define nla_total_size_bitmap(nbits)	nla_total_size_bigint(nbits)
+
 /**
  * nla_for_each_attr - iterate over a stream of attributes
  * @pos: loop counter, set to current attribute
diff --git a/include/uapi/linux/netlink.h b/include/uapi/linux/netlink.h
index e2ae82e3f9f7..15e599961b23 100644
--- a/include/uapi/linux/netlink.h
+++ b/include/uapi/linux/netlink.h
@@ -298,6 +298,8 @@ struct nla_bitfield32 {
  *	entry has attributes again, the policy for those inner ones
  *	and the corresponding maxtype may be specified.
  * @NL_ATTR_TYPE_BITFIELD32: &struct nla_bitfield32 attribute
+ * @NL_ATTR_TYPE_BIGINT: array of 32-bit unsigned integers which form
+ *	one big integer or bitmap. Validated by an optional bitmask.
  */
 enum netlink_attribute_type {
 	NL_ATTR_TYPE_INVALID,
@@ -322,6 +324,7 @@ enum netlink_attribute_type {
 	NL_ATTR_TYPE_NESTED_ARRAY,
 
 	NL_ATTR_TYPE_BITFIELD32,
+	NL_ATTR_TYPE_BIGINT,
 };
 
 /**
@@ -351,6 +354,8 @@ enum netlink_attribute_type {
  *	bitfield32 type (U32)
  * @NL_POLICY_TYPE_ATTR_MASK: mask of valid bits for unsigned integers (U64)
  * @NL_POLICY_TYPE_ATTR_PAD: pad attribute for 64-bit alignment
+ * @NL_POLICY_TYPE_ATTR_BIGINT_MASK: array with mask of valid
+ *	bits for bigints
  *
  * @__NL_POLICY_TYPE_ATTR_MAX: number of attributes
  * @NL_POLICY_TYPE_ATTR_MAX: highest attribute number
@@ -369,6 +374,7 @@ enum netlink_policy_type_attr {
 	NL_POLICY_TYPE_ATTR_BITFIELD32_MASK,
 	NL_POLICY_TYPE_ATTR_PAD,
 	NL_POLICY_TYPE_ATTR_MASK,
+	NL_POLICY_TYPE_ATTR_BIGINT_MASK,
 
 	/* keep last */
 	__NL_POLICY_TYPE_ATTR_MAX,
diff --git a/lib/nlattr.c b/lib/nlattr.c
index 40f22b177d69..c923ee6d2876 100644
--- a/lib/nlattr.c
+++ b/lib/nlattr.c
@@ -81,6 +81,33 @@ static int validate_nla_bitfield32(const struct nlattr *nla,
 	return 0;
 }
 
+static int nla_validate_bigint_mask(const struct nla_policy *pt,
+				    const struct nlattr *nla,
+				    struct netlink_ext_ack *extack)
+{
+	unsigned long *bigint;
+	size_t nbits;
+	bool res;
+
+	nbits = min_t(size_t, BYTES_TO_BITS(nla_len(nla)),
+		      nla_policy_bigint_nbits(pt));
+
+	bigint = bitmap_alloc(nbits, in_task() ? GFP_KERNEL : GFP_ATOMIC);
+	if (!bigint)
+		return -ENOMEM;
+
+	nla_get_bigint(nla, bigint, nbits);
+	res = bitmap_andnot(bigint, bigint, nla_policy_bigint_mask(pt), nbits);
+	bitmap_free(bigint);
+
+	if (res) {
+		NL_SET_ERR_MSG_ATTR_POL(extack, nla, pt, "unexpected bit set");
+		return -EINVAL;
+	}
+
+	return 0;
+}
+
 static int nla_validate_array(const struct nlattr *head, int len, int maxtype,
 			      const struct nla_policy *policy,
 			      struct netlink_ext_ack *extack,
@@ -365,6 +392,8 @@ static int nla_validate_mask(const struct nla_policy *pt,
 	case NLA_U64:
 		value = nla_get_u64(nla);
 		break;
+	case NLA_BIGINT:
+		return nla_validate_bigint_mask(pt, nla, extack);
 	default:
 		return -EINVAL;
 	}
@@ -445,6 +474,15 @@ static int validate_nla(const struct nlattr *nla, int maxtype,
 			goto out_err;
 		break;
 
+	case NLA_BIGINT:
+		if (!bitmap_validate_arr32(nla_data(nla), nla_len(nla),
+					   nla_policy_bigint_nbits(pt))) {
+			err = -EINVAL;
+			goto out_err;
+		}
+
+		break;
+
 	case NLA_NUL_STRING:
 		if (pt->len)
 			minlen = min_t(int, attrlen, pt->len + 1);
@@ -672,7 +710,9 @@ nla_policy_len(const struct nla_policy *p, int n)
 	int i, len = 0;
 
 	for (i = 0; i < n; i++, p++) {
-		if (p->len)
+		if (p->type == NLA_BIGINT)
+			len += nla_total_size_bigint(nla_policy_bigint_nbits(p));
+		else if (p->len)
 			len += nla_total_size(p->len);
 		else if (nla_attr_len[p->type])
 			len += nla_total_size(nla_attr_len[p->type]);
diff --git a/net/netlink/policy.c b/net/netlink/policy.c
index 87e3de0fde89..79f8caeb8a77 100644
--- a/net/netlink/policy.c
+++ b/net/netlink/policy.c
@@ -234,6 +234,10 @@ int netlink_policy_dump_attr_size_estimate(const struct nla_policy *pt)
 		       2 * (nla_attr_size(0) + nla_attr_size(sizeof(u64)));
 	case NLA_BITFIELD32:
 		return common + nla_attr_size(sizeof(u32));
+	case NLA_BIGINT:
+		/* maximum is common, aligned validation mask as u32-arr */
+		return common +
+		       nla_total_size_bigint(nla_policy_bigint_nbits(pt));
 	case NLA_STRING:
 	case NLA_NUL_STRING:
 	case NLA_BINARY:
@@ -247,6 +251,36 @@ int netlink_policy_dump_attr_size_estimate(const struct nla_policy *pt)
 	return 0;
 }
 
+static bool
+__netlink_policy_dump_write_attr_bigint(struct sk_buff *skb,
+					const struct nla_policy *pt)
+{
+	if (pt->validation_type == NLA_VALIDATE_MASK) {
+		if (nla_put_bigint(skb, NL_POLICY_TYPE_ATTR_BIGINT_MASK,
+				   nla_policy_bigint_mask(pt),
+				   nla_policy_bigint_nbits(pt)))
+			return false;
+	} else {
+		unsigned long *mask;
+		int ret;
+
+		mask = bitmap_alloc(nla_policy_bigint_nbits(pt),
+				    in_task() ? GFP_KERNEL : GFP_ATOMIC);
+		if (!mask)
+			return false;
+
+		bitmap_fill(mask, nla_policy_bigint_nbits(pt));
+		ret = nla_put_bigint(skb, NL_POLICY_TYPE_ATTR_BIGINT_MASK,
+				     mask, nla_policy_bigint_nbits(pt));
+		bitmap_free(mask);
+
+		if (ret)
+			return false;
+	}
+
+	return true;
+}
+
 static int
 __netlink_policy_dump_write_attr(struct netlink_policy_dump_state *state,
 				 struct sk_buff *skb,
@@ -346,6 +380,12 @@ __netlink_policy_dump_write_attr(struct netlink_policy_dump_state *state,
 				pt->bitfield32_valid))
 			goto nla_put_failure;
 		break;
+	case NLA_BIGINT:
+		if (!__netlink_policy_dump_write_attr_bigint(skb, pt))
+			goto nla_put_failure;
+
+		type = NL_ATTR_TYPE_BIGINT;
+		break;
 	case NLA_STRING:
 	case NLA_NUL_STRING:
 	case NLA_BINARY:
-- 
2.37.3

Re: [PATCH v2 net-next 6/6] netlink: add universal 'bigint' attribute type

[Andy Shevchenko]

On Tue, Oct 18, 2022 at 04:00:27PM +0200, Alexander Lobakin wrote:
> Add a new type of Netlink attribute -- big integer.
> 
> Basically bigints are just arrays of u32s, but can carry anything,
> with 1 bit precision. Using variable-length arrays of a fixed type
> gives the following:
> 
> * versatility: one type can carry scalars from u8 to u64, bitmaps,
>   binary data etc.;
> * scalability: the same Netlink attribute can be changed to a wider
>   (or shorter) data type with no compatibility issues, same for
>   growing bitmaps;
> * optimization: 4-byte units don't require wasting slots for empty
>   padding attributes (they always have natural alignment in Netlink
>   messages).
> 
> The only downside is that get/put functions sometimes are not just
> direct assignment inlines due to the internal representation using
> bitmaps (longs) and the bitmap API.
> 
> Basic consumer functions/macros are:
> * nla_put_bigint() and nla_get_bigint() -- to easily put a bigint to
>   an skb or get it from a received message (only pointer to an
>   unsigned long array and the number of bits in it are needed);
> * nla_put_bigint_{u,be,le,net}{8,16,32,64}() -- alternatives to the
>   already existing family to send/receive scalars using the new type
>   (instead of distinct attr types);
> * nla_total_size_bigint*() -- to provide estimate size in bytes to
>   Netlink needed to store a bigint/type;
> * NLA_POLICY_BIGINT*() -- to declare a Netlink policy for a bigint
>   attribute.
> 
> There are also *_bitmap() aliases for the *_bigint() helpers which
> have no differences and designed to distinguish bigints from bitmaps
> in the call sites (for readability).
> 
> Netlink policy for a bigint can have an optional bitmap mask of bits
> supported by the code -- for example, to filter out obsolete bits
> removed some time ago or limit value to n bits (e.g. 53 instead of
> 64). Without it, Netlink will just make sure no bits past the passed
> number are set. Both variants can be requested from the userspace
> and the kernel will put a mask into a new policy attribute
> (%NL_POLICY_TYPE_ATTR_BIGINT_MASK).
> 
> Note on including <linux/bitmap.h> into <net/netlink.h>: seems to
> introduce no visible compilation time regressions, make includecheck
> doesn't see anything illegit as well. Hiding everything inside
> lib/nlattr.c would require making a couple dozens optimizable
> inlines external, doesn't sound optimal.

...

>  #ifndef __NET_NETLINK_H
>  #define __NET_NETLINK_H
>  
> -#include <linux/types.h>
> +#include <linux/bitmap.h>

types.h is not guaranteed to be included by bitmap.h. So, if you want to
clean up the headers in this header, do it in a separate change.

Also I would suggest to check what Ingo did in his 2000+ patch series
to see if there is anything interesting towards this header.

>  #include <linux/netlink.h>
>  #include <linux/jiffies.h>
>  #include <linux/in6.h>

-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH v2 net-next 6/6] netlink: add universal 'bigint' attribute type

[Jakub Kicinski]

On Tue, 18 Oct 2022 16:00:27 +0200 Alexander Lobakin wrote:
> @@ -235,12 +236,15 @@ enum nla_policy_validation {
>   *                         given type fits, using it verifies minimum length
>   *                         just like "All other"
>   *    NLA_BITFIELD32       Unused
> + *    NLA_BIGINT           Number of bits in the big integer

Should we say "Max number...", otherwise someone may think that user
must match this exactly, since other members specify if it's max or min.

>   *    NLA_REJECT           Unused
>   *    All other            Minimum length of attribute payload
>   *
>   * Meaning of validation union:
>   *    NLA_BITFIELD32       This is a 32-bit bitmap/bitselector attribute and
>   *                         `bitfield32_valid' is the u32 value of valid flags
> + *    NLA_BIGINT           `bigint_mask` is a pointer to the mask of the valid
> + *                         bits of the given bigint to perform the validation.
>   *    NLA_REJECT           This attribute is always rejected and `reject_message'
>   *                         may point to a string to report as the error instead
>   *                         of the generic one in extended ACK.
> @@ -327,6 +331,7 @@ struct nla_policy {
>  			s16 min, max;
>  			u8 network_byte_order:1;
>  		};
> +		const unsigned long *bigint_mask;

kdoc missing

Can we pretend this is an UINT type and reuse the existing validation
types (enum nla_policy_validation)? This way simple cases (<= 32bit
mask, small min/max values) can be defined quite trivially in-place
and things will only get complicated for people who actually need their
values to grow.

>  		int (*validate)(const struct nlattr *attr,
>  				struct netlink_ext_ack *extack);
>  		/* This entry is special, and used for the attribute at index 0
> @@ -451,6 +456,35 @@ struct nla_policy {
>  }
>  #define NLA_POLICY_MIN_LEN(_len)	NLA_POLICY_MIN(NLA_BINARY, _len)
>  
> +/**
> + * NLA_POLICY_BIGINT - represent &nla_policy for a bigint attribute
> + * @nbits - number of bits in the bigint
> + * @... - optional pointer to a bitmap carrying a mask of supported bits
> + */
> +#define NLA_POLICY_BIGINT(nbits, ...) {					\
> +	.type = NLA_BIGINT,						\
> +	.len = (nbits),							\
> +	.bigint_mask =							\
> +		(typeof((__VA_ARGS__ + 0) ? : NULL))(__VA_ARGS__ + 0),	\
> +	.validation_type = (__VA_ARGS__ + 0) ? NLA_VALIDATE_MASK : 0,	\
> +}
> +
> +/* Simplify (and encourage) using the bigint type to send scalars */
> +#define NLA_POLICY_BIGINT_TYPE(type, ...)				\
> +	NLA_POLICY_BIGINT(BITS_PER_TYPE(type), ##__VA_ARGS__)
> +
> +#define NLA_POLICY_BIGINT_U8		NLA_POLICY_BIGINT_TYPE(u8)
> +#define NLA_POLICY_BIGINT_U16		NLA_POLICY_BIGINT_TYPE(u16)
> +#define NLA_POLICY_BIGINT_U32		NLA_POLICY_BIGINT_TYPE(u32)
> +#define NLA_POLICY_BIGINT_U64		NLA_POLICY_BIGINT_TYPE(u64)

Yes, these seem confusing to me. What I was expecting was that user
would say:

	[FAMILY_A_HATCHET]        = NLA_POLICY_MASK(NLA_BIGINT,	HATCHET_BITS),

So very close to existing U8/16/32/64 policies. Inversely your new
mask pointer should be reusable with NLA_U64.

> +/* Transparent alias (for readability purposes) */
> +#define NLA_POLICY_BITMAP(nbits, ...)					\
> +	NLA_POLICY_BIGINT((nbits), ##__VA_ARGS__)
> +
> +#define nla_policy_bigint_mask(pt)	((pt)->bigint_mask)
> +#define nla_policy_bigint_nbits(pt)	((pt)->len)
> +
>  /**
>   * struct nl_info - netlink source information
>   * @nlh: Netlink message header of original request
> @@ -1556,6 +1590,28 @@ static inline int nla_put_bitfield32(struct sk_buff *skb, int attrtype,
>  	return nla_put(skb, attrtype, sizeof(tmp), &tmp);
>  }
>  
> +/**
> + * nla_put_bigint - Add a bigint Netlink attribute to a socket buffer
> + * @skb: socket buffer to add attribute to
> + * @attrtype: attribute type
> + * @bigint: bigint to put, as array of unsigned longs
> + * @nbits: number of bits in the bigint
> + */
> +static inline int nla_put_bigint(struct sk_buff *skb, int attrtype,
> +				 const unsigned long *bigint,
> +				 size_t nbits)
> +{
> +	struct nlattr *nla;
> +
> +	nla = nla_reserve(skb, attrtype, bitmap_arr32_size(nbits));
> +	if (unlikely(!nla))
> +		return -EMSGSIZE;
> +
> +	bitmap_to_arr32(nla_data(nla), bigint, nbits);
> +
> +	return 0;
> +}
> +
>  /**
>   * nla_get_u32 - return payload of u32 attribute
>   * @nla: u32 netlink attribute
> @@ -1749,6 +1805,134 @@ static inline struct nla_bitfield32 nla_get_bitfield32(const struct nlattr *nla)
>  	return tmp;
>  }
>  
> +/**
> + * nla_get_bigint - Return a bigint from u32-array bigint Netlink attribute
> + * @nla: %NLA_BIGINT Netlink attribute
> + * @bigint: target container, as array of unsigned longs
> + * @nbits: expected number of bits in the bigint
> + */
> +static inline void nla_get_bigint(const struct nlattr *nla,
> +				  unsigned long *bigint,
> +				  size_t nbits)
> +{
> +	size_t diff = BITS_TO_LONGS(nbits);
> +
> +	/* Core validated nla_len() is (n + 1) * sizeof(u32), leave a hint */
> +	nbits = clamp_t(size_t, BYTES_TO_BITS(nla_len(nla)),
> +			BITS_PER_TYPE(u32), nbits);
> +	bitmap_from_arr32(bigint, nla_data(nla), nbits);
> +
> +	diff -= BITS_TO_LONGS(nbits);
> +	memset(bigint + BITS_TO_LONGS(nbits), 0, diff * sizeof(long));
> +}
> +
> +/* The macros below build the following set of functions, allowing to
> + * easily use the %NLA_BIGINT API to send scalar values. Their fake
> + * declarations are provided under #if 0, so that source code indexers
> + * could build references to them.
> + */

How many of those do we _actually_ need? Can we codegen them with a
simple script and make it a separate file?

> +#if 0
> +int nla_put_bigint_s8(struct sk_buff *skb, int attrtype, __s8 value);

Any chance we can shorten the names?

	nla_put_s8bi()?

Netlink code already has crazy long lines :S

> +__s8 nla_get_bigint_s8(const struct nlattr *nla);
> +int nla_put_bigint_s16(struct sk_buff *skb, int attrtype, __s16 value);
> +__s16 nla_get_bigint_s16(const struct nlattr *nla);
> +int nla_put_bigint_s32(struct sk_buff *skb, int attrtype, __s32 value);
> +__s32 nla_get_bigint_s32(const struct nlattr *nla);
> +int nla_put_bigint_s64(struct sk_buff *skb, int attrtype, __s64 value);
> +__s64 nla_get_bigint_s64(const struct nlattr *nla);
> +

>  static int nla_validate_array(const struct nlattr *head, int len, int maxtype,
>  			      const struct nla_policy *policy,
>  			      struct netlink_ext_ack *extack,
> @@ -365,6 +392,8 @@ static int nla_validate_mask(const struct nla_policy *pt,
>  	case NLA_U64:
>  		value = nla_get_u64(nla);
>  		break;
> +	case NLA_BIGINT:
> +		return nla_validate_bigint_mask(pt, nla, extack);

I'd think that if someone wants NLA_VALIDATE_MASK they must mean the
32bit in place mask from the policy, not the big one via the pointer.

>  	default:
>  		return -EINVAL;
>  	}
> @@ -445,6 +474,15 @@ static int validate_nla(const struct nlattr *nla, int maxtype,
>  			goto out_err;
>  		break;
>  
> +	case NLA_BIGINT:
> +		if (!bitmap_validate_arr32(nla_data(nla), nla_len(nla),
> +					   nla_policy_bigint_nbits(pt))) {

And here I would not make the assumption that bigint must mean mask
validation.

If the range validation is requested with the in-policy values we
should convert to a small scalar and make sure the top bits are 0.
IOW punt on u128+ for now.

> +			err = -EINVAL;
> +			goto out_err;
> +		}
> +
> +		break;
> +

Very good stuff, the validation vs type separation is the big question.

Re: [PATCH v2 net-next 5/6] bitops: make BYTES_TO_BITS() treewide-available

[Jakub Kicinski]

On Tue, 18 Oct 2022 16:00:26 +0200 Alexander Lobakin wrote:
> Avoid open-coding that simple expression each time by moving
> BYTES_TO_BITS() from the probes code to <linux/bitops.h> to export
> it to the rest of the kernel.
> Do the same for the tools ecosystem as well (incl. its version of
> bitops.h).

This needs to be before patch 4?

Re: [PATCH v2 net-next 1/6] bitmap: try to optimize arr32 <-> bitmap on 64-bit LEs

[Yury Norov]

On Tue, Oct 18, 2022 at 04:00:22PM +0200, Alexander Lobakin wrote:
> Unlike bitmap_{from,to}_arr64(), when there can be no out-of-bounds
> accesses (due to u64 always being no shorter than unsigned long),
> it can't be guaranteed with arr32s due to that on 64-bit platforms:
> 
> bits     BITS_TO_U32 * sizeof(u32)    BITS_TO_LONGS * sizeof(long)
> 1-32     4                            8
> 33-64    8                            8
> 95-96    12                           16
> 97-128   16                           16
> 
> and so on.
> That is why bitmap_{from,to}_arr32() are always defined there as
> externs. But quite often @nbits is a compile-time constant, which
> means we could suggest whether it can be inlined or not at
> compile-time basing on the number of bits (above).
> 
> So, try to determine that at compile time and, in case of both
> containers having the same size in bytes, resolve it to
> bitmap_copy_clear_tail() on Little Endian. No changes here for
> Big Endian or when the number of bits *really* is variable.

You're saying 'try to optimize', but don't show any numbers. What's
the target for your optimization? Can you demonstrate how it performs
in test or in real work?
 
> Signed-off-by: Alexander Lobakin <alexandr.lobakin@intel.com>
> ---
>  include/linux/bitmap.h | 51 ++++++++++++++++++++++++++++++------------
>  lib/bitmap.c           | 12 +++++-----
>  2 files changed, 43 insertions(+), 20 deletions(-)
> 
> diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
> index 7d6d73b78147..79d12e0f748b 100644
> --- a/include/linux/bitmap.h
> +++ b/include/linux/bitmap.h
> @@ -283,24 +283,47 @@ static inline void bitmap_copy_clear_tail(unsigned long *dst,
>   * On 32-bit systems bitmaps are represented as u32 arrays internally. On LE64
>   * machines the order of hi and lo parts of numbers match the bitmap structure.
>   * In both cases conversion is not needed when copying data from/to arrays of
> - * u32. But in LE64 case, typecast in bitmap_copy_clear_tail() may lead
> - * to out-of-bound access. To avoid that, both LE and BE variants of 64-bit
> - * architectures are not using bitmap_copy_clear_tail().
> + * u32. But in LE64 case, typecast in bitmap_copy_clear_tail() may lead to
> + * out-of-bound access. To avoid that, LE variant of 64-bit architectures uses
> + * bitmap_copy_clear_tail() only when @bitmap and @buf containers have the same
> + * size in memory (known at compile time), and 64-bit BEs never use it.
>   */
> -#if BITS_PER_LONG == 64
> -void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf,
> -							unsigned int nbits);
> -void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap,
> -							unsigned int nbits);
> +#if BITS_PER_LONG == 32
> +#define bitmap_arr32_compat(nbits)		true
> +#elif defined(__LITTLE_ENDIAN)
> +#define bitmap_arr32_compat(nbits)		\

'Compat' is reserved for a compatibility layer between kernel and
user spaces running different ABIs. Can you pick some other word?

> +	(__builtin_constant_p(nbits) &&		\
> +	 BITS_TO_U32(nbits) * sizeof(u32) ==	\
> +	 BITS_TO_LONGS(nbits) * sizeof(long))

I think it should be:
        round_up(nbits, 32) == round_up(nbits, 64)

>  #else
> -#define bitmap_from_arr32(bitmap, buf, nbits)			\
> -	bitmap_copy_clear_tail((unsigned long *) (bitmap),	\
> -			(const unsigned long *) (buf), (nbits))
> -#define bitmap_to_arr32(buf, bitmap, nbits)			\
> -	bitmap_copy_clear_tail((unsigned long *) (buf),		\
> -			(const unsigned long *) (bitmap), (nbits))

Can you keep this part untouched? I'd like to have a clear meaning -
on 32-bit arch, bitmap_to_arr32 is a simple copy.

> +#define bitmap_arr32_compat(nbits)		false
>  #endif
>  
> +void __bitmap_from_arr32(unsigned long *bitmap, const u32 *buf, unsigned int nbits);
> +void __bitmap_to_arr32(u32 *buf, const unsigned long *bitmap, unsigned int nbits);
> +
> +static inline void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf,
> +				     unsigned int nbits)
> +{
> +	const unsigned long *src = (const unsigned long *)buf;
> +
> +	if (bitmap_arr32_compat(nbits))
> +		bitmap_copy_clear_tail(bitmap, src, nbits);
> +	else
> +		__bitmap_from_arr32(bitmap, buf, nbits);

If you would really want to optimize it, I'd suggest something like
this:
    #ifdef __LITTLE_ENDIAN
        /*copy as many full 64-bit words as we can */
        bitmap_copy(bitmap, src, round_down(nbits, BITS_PER_LONG)); 

        /* now copy part of last word per-byte */
        ...
    #else
	__bitmap_from_arr32(bitmap, buf, nbits);
    #endif

This should be better because it uses fast bitmap_copy() regardless
the number of bits. Assuming bitmap_copy() is significantly faster
than bitmap_from_arr(), people will be surprised by the difference of
speed of copying, say, 2048 and 2049-bit bitmaps. Right?

But unless we'll see real numbers, it's questionable to me if that's
worth the effort.

Thanks,
Yury

Re: [PATCH v2 net-next 1/6] bitmap: try to optimize arr32 <-> bitmap on 64-bit LEs

[Alexander Lobakin]

From: Yury Norov <yury.norov@gmail.com>
Date: Tue, 18 Oct 2022 15:41:46 -0700

> On Tue, Oct 18, 2022 at 04:00:22PM +0200, Alexander Lobakin wrote:
> > Unlike bitmap_{from,to}_arr64(), when there can be no out-of-bounds
> > accesses (due to u64 always being no shorter than unsigned long),
> > it can't be guaranteed with arr32s due to that on 64-bit platforms:
> > 
> > bits     BITS_TO_U32 * sizeof(u32)    BITS_TO_LONGS * sizeof(long)
> > 1-32     4                            8
> > 33-64    8                            8
> > 95-96    12                           16
> > 97-128   16                           16
> > 
> > and so on.
> > That is why bitmap_{from,to}_arr32() are always defined there as
> > externs. But quite often @nbits is a compile-time constant, which
> > means we could suggest whether it can be inlined or not at
> > compile-time basing on the number of bits (above).
> > 
> > So, try to determine that at compile time and, in case of both
> > containers having the same size in bytes, resolve it to
> > bitmap_copy_clear_tail() on Little Endian. No changes here for
> > Big Endian or when the number of bits *really* is variable.
> 
> You're saying 'try to optimize', but don't show any numbers. What's
> the target for your optimization? Can you demonstrate how it performs
> in test or in real work?

I had them somewhere, but given that you provided a different
approach to try, I'd better retest each of them and collect some
fresh numbers. If it's not worth it, I'll simply drop the patch
from the series / include stats in the commitmsg otherwise.

>  
> > Signed-off-by: Alexander Lobakin <alexandr.lobakin@intel.com>
> > ---
> >  include/linux/bitmap.h | 51 ++++++++++++++++++++++++++++++------------
> >  lib/bitmap.c           | 12 +++++-----
> >  2 files changed, 43 insertions(+), 20 deletions(-)

[...]

> > +#if BITS_PER_LONG == 32
> > +#define bitmap_arr32_compat(nbits)		true
> > +#elif defined(__LITTLE_ENDIAN)
> > +#define bitmap_arr32_compat(nbits)		\
> 
> 'Compat' is reserved for a compatibility layer between kernel and
> user spaces running different ABIs. Can you pick some other word?

Yeah, sure. I was also thinking of this as it didn't sound good to
me as well, but didn't find anything better at the top of my head
and then forgot about it at all.

> 
> > +	(__builtin_constant_p(nbits) &&		\
> > +	 BITS_TO_U32(nbits) * sizeof(u32) ==	\
> > +	 BITS_TO_LONGS(nbits) * sizeof(long))
> 
> I think it should be:
>         round_up(nbits, 32) == round_up(nbits, 64)

Ah, correct.

> 
> >  #else
> > -#define bitmap_from_arr32(bitmap, buf, nbits)			\
> > -	bitmap_copy_clear_tail((unsigned long *) (bitmap),	\
> > -			(const unsigned long *) (buf), (nbits))
> > -#define bitmap_to_arr32(buf, bitmap, nbits)			\
> > -	bitmap_copy_clear_tail((unsigned long *) (buf),		\
> > -			(const unsigned long *) (bitmap), (nbits))
> 
> Can you keep this part untouched? I'd like to have a clear meaning -
> on 32-bit arch, bitmap_to_arr32 is a simple copy.

Sure, why not, I don't have a strong preference here.

> 
> > +#define bitmap_arr32_compat(nbits)		false
> >  #endif
> >  
> > +void __bitmap_from_arr32(unsigned long *bitmap, const u32 *buf, unsigned int nbits);
> > +void __bitmap_to_arr32(u32 *buf, const unsigned long *bitmap, unsigned int nbits);
> > +
> > +static inline void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf,
> > +				     unsigned int nbits)
> > +{
> > +	const unsigned long *src = (const unsigned long *)buf;
> > +
> > +	if (bitmap_arr32_compat(nbits))
> > +		bitmap_copy_clear_tail(bitmap, src, nbits);
> > +	else
> > +		__bitmap_from_arr32(bitmap, buf, nbits);
> 
> If you would really want to optimize it, I'd suggest something like
> this:
>     #ifdef __LITTLE_ENDIAN
>         /*copy as many full 64-bit words as we can */
>         bitmap_copy(bitmap, src, round_down(nbits, BITS_PER_LONG)); 
> 
>         /* now copy part of last word per-byte */
>         ...
>     #else
> 	__bitmap_from_arr32(bitmap, buf, nbits);
>     #endif
> 
> This should be better because it uses fast bitmap_copy() regardless
> the number of bits. Assuming bitmap_copy() is significantly faster
> than bitmap_from_arr(), people will be surprised by the difference of
> speed of copying, say, 2048 and 2049-bit bitmaps. Right?
> 
> But unless we'll see real numbers, it's questionable to me if that's
> worth the effort.

Nice suggestion, thanks! I'll retest all I have and then we'll see.

> 
> Thanks,
> Yury

Thanks,
Olek

Re: [PATCH v2 net-next 5/6] bitops: make BYTES_TO_BITS() treewide-available

[Alexander Lobakin]

From: Jakub Kicinski <kuba@kernel.org>
Date: Tue, 18 Oct 2022 12:55:20 -0700

> On Tue, 18 Oct 2022 16:00:26 +0200 Alexander Lobakin wrote:
> > Avoid open-coding that simple expression each time by moving
> > BYTES_TO_BITS() from the probes code to <linux/bitops.h> to export
> > it to the rest of the kernel.
> > Do the same for the tools ecosystem as well (incl. its version of
> > bitops.h).
> 
> This needs to be before patch 4?

Indeed :s Thanks for catching.

Olek

Re: [PATCH v2 net-next 6/6] netlink: add universal 'bigint' attribute type

[Alexander Lobakin]

From: Jakub Kicinski <kuba@kernel.org>
Date: Tue, 18 Oct 2022 12:53:58 -0700

> On Tue, 18 Oct 2022 16:00:27 +0200 Alexander Lobakin wrote:
> > @@ -235,12 +236,15 @@ enum nla_policy_validation {
> >   *                         given type fits, using it verifies minimum length
> >   *                         just like "All other"
> >   *    NLA_BITFIELD32       Unused
> > + *    NLA_BIGINT           Number of bits in the big integer

[...]

> > +		break;
> > +
> 
> Very good stuff, the validation vs type separation is the big question.

Another round of great comments, copied to the TODO. Will dig out
everything and return with v3, for now at least most of those sound
possible and reasonable.

Thanks,
Olek

Re: [PATCH v2 net-next 2/6] bitmap: add a couple more helpers to work with arrays of u32s

[Yury Norov]

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

Re: [PATCH v2 net-next 2/6] bitmap: add a couple more helpers to work with arrays of u32s

[Andy Shevchenko]

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.

> > +}

-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH v2 net-next 2/6] bitmap: add a couple more helpers to work with arrays of u32s

[Yury Norov]

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