Skip to contentSkip to conversation

bpf: Add bits iterator

PATCH Superseded Yafang Shao 2 participants 6 messages Mar 5, 2024 – Mar 6, 2024

Subsystems (3)

v3 of 8 Superseded Latest is v8 →

lore
Share & tools
lore
#0 lore raw

PATCH v3 1/2 bpf: Add bits iterator

Add three new kfuncs for the bits iterator:
- bpf_iter_bits_new
Initialize a new bits iterator for a given memory area. Due to the limitation of bpf memalloc, the max number of bits that can be iterated over is limited to (4096 * 8).
- bpf_iter_bits_next
Get the next bit in a bpf_iter_bits
- bpf_iter_bits_destroy
Destroy a bpf_iter_bits

The bits iterator facilitates the iteration of the bits of a memory area, such as cpumask. It can be used in any context and on any address.

---
 kernel/bpf/helpers.c | 117 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 117 insertions(+)
kernel/bpf/helpers.c +117 -0
index a89587859571..a769561b65ae 100644
@@ -2545,6 +2545,120 @@ __bpf_kfunc void bpf_throw(u64 cookie)
 	WARN(1, "A call to BPF exception callback should never return\n");
 }
 
+struct bpf_iter_bits {
+	__u64 __opaque[2];
+} __aligned(8);
+
+struct bpf_iter_bits_kern {
+	union {
+		unsigned long *bits;
+		unsigned long bits_copy;
+	};
+	u32 nr_bits;
+	int bit;
+} __aligned(8);
+
+/**
+ * bpf_iter_bits_new() - Initialize a new bits iterator for a given memory area
+ * @it: The new bpf_iter_bits to be created
+ * @unsafe_ptr__ign: A ponter pointing to a memory area to be iterated over
+ * @nr_bits: The number of bits to be iterated over. Due to the limitation of
+ * memalloc, it can't greater than (4096 * 8).
+ *
+ * This function initializes a new bpf_iter_bits structure for iterating over
+ * a memory area which is specified by the @unsafe_ptr__ign and @nr_bits. It
+ * copy the data of the memory area to the newly created bpf_iter_bits @it for
+ * subsequent iteration operations.
+ *
+ * On success, 0 is returned. On failure, ERR is returned.
+ */
+__bpf_kfunc int
+bpf_iter_bits_new(struct bpf_iter_bits *it, const void *unsafe_ptr__ign, u32 nr_bits)
+{
+	struct bpf_iter_bits_kern *kit = (void *)it;
+	u32 size = BITS_TO_BYTES(nr_bits);
+	int err;
+
+	BUILD_BUG_ON(sizeof(struct bpf_iter_bits_kern) != sizeof(struct bpf_iter_bits));
+	BUILD_BUG_ON(__alignof__(struct bpf_iter_bits_kern) !=
+		     __alignof__(struct bpf_iter_bits));
+
+	if (!unsafe_ptr__ign || !nr_bits) {
+		kit->bits = NULL;
+		return -EINVAL;
+	}
+
+	kit->nr_bits = 0;
+	/* Optimization for u64/u32 mask */
+	if (nr_bits <= 64) {
+		err = bpf_probe_read_kernel_common(&kit->bits_copy, size, unsafe_ptr__ign);
+		if (unlikely(err))
+			return -EFAULT;
+
+		kit->nr_bits = nr_bits;
+		kit->bit = -1;
+		return 0;
+	}
+
+	/* Fallback to memalloc */
+	kit->bits = bpf_mem_alloc(&bpf_global_ma, size);
+	if (!kit->bits)
+		return -ENOMEM;
+
+	err = bpf_probe_read_kernel_common(kit->bits, size, unsafe_ptr__ign);
+	if (err) {
+		bpf_mem_free(&bpf_global_ma, kit->bits);
+		return err;
+	}
+
+	kit->nr_bits = nr_bits;
+	kit->bit = -1;
+	return 0;
+}
+
+/**
+ * bpf_iter_bits_next() - Get the next bit in a bpf_iter_bits
+ * @it: The bpf_iter_bits to be checked
+ *
+ * This function returns a pointer to a number representing the value of the
+ * next bit in the bits.
+ *
+ * If there are no further bit available, it returns NULL.
+ */
+__bpf_kfunc int *bpf_iter_bits_next(struct bpf_iter_bits *it)
+{
+	struct bpf_iter_bits_kern *kit = (void *)it;
+	u32 nr_bits = kit->nr_bits;
+	const unsigned long *bits;
+	int bit;
+
+	if (nr_bits == 0)
+		return NULL;
+
+	bits = nr_bits <= 64 ? &kit->bits_copy : kit->bits;
+	bit = find_next_bit(bits, kit->nr_bits, kit->bit + 1);
+	if (bit >= kit->nr_bits)
+		return NULL;
+
+	kit->bit = bit;
+	return &kit->bit;
+}
+
+/**
+ * bpf_iter_bits_destroy() - Destroy a bpf_iter_bits
+ * @it: The bpf_iter_bits to be destroyed
+ *
+ * Destroy the resource associated with the bpf_iter_bits.
+ */
+__bpf_kfunc void bpf_iter_bits_destroy(struct bpf_iter_bits *it)
+{
+	struct bpf_iter_bits_kern *kit = (void *)it;
+
+	if (kit->nr_bits <= 64)
+		return;
+	bpf_mem_free(&bpf_global_ma, kit->bits);
+}
+
 __bpf_kfunc_end_defs();
 
 BTF_KFUNCS_START(generic_btf_ids)
@@ -2621,6 +2735,9 @@ BTF_ID_FLAGS(func, bpf_dynptr_is_null)
 BTF_ID_FLAGS(func, bpf_dynptr_is_rdonly)
 BTF_ID_FLAGS(func, bpf_dynptr_size)
 BTF_ID_FLAGS(func, bpf_dynptr_clone)
+BTF_ID_FLAGS(func, bpf_iter_bits_new, KF_ITER_NEW)
+BTF_ID_FLAGS(func, bpf_iter_bits_next, KF_ITER_NEXT | KF_RET_NULL)
+BTF_ID_FLAGS(func, bpf_iter_bits_destroy, KF_ITER_DESTROY)
 BTF_KFUNCS_END(common_btf_ids)
 
 static const struct btf_kfunc_id_set common_kfunc_set = {
Signature · 1 line
2.39.1
#1 lore raw

PATCH v3 2/2 selftests/bpf: Add selftest for bits iter

Add selftests for the newly added bits iter.
- bits_iter_success
- percpu data extracted from the percpu struct should be expected
- RCU lock is not required
- It is fine without calling bpf_iter_cpumask_next()
- It can work as expected when invalid arguments are passed

- bits_iter_failure
- bpf_iter_bits_destroy() is required after calling

    bpf_iter_bits_new()

- bpf_iter_bits_destroy() can only destroy an initialized iter
- bpf_iter_bits_next() must use an initialized iter

This test case can't work correctly on s390x for unknonw reason, thus it is added to DENYLIST.s390x.

---
 tools/testing/selftests/bpf/DENYLIST.s390x    |   3 +-
 .../selftests/bpf/prog_tests/bits_iter.c      | 137 ++++++++++++++++++
 .../bpf/progs/test_bits_iter_failure.c        |  54 +++++++
 .../bpf/progs/test_bits_iter_success.c        | 122 ++++++++++++++++
 4 files changed, 315 insertions(+), 1 deletion(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/bits_iter.c
 create mode 100644 tools/testing/selftests/bpf/progs/test_bits_iter_failure.c
 create mode 100644 tools/testing/selftests/bpf/progs/test_bits_iter_success.c
tools/testing/selftests/bpf/DENYLIST.s390x +2 -1
index 1a63996c0304..0cd6d2bf1ff4 100644
@@ -1,5 +1,6 @@
 # TEMPORARY
 # Alphabetical order
-exceptions				 # JIT does not support calling kfunc bpf_throw				       (exceptions)
+bits_iter                                # cpumask iter can't work as expected                                         (?)
+exceptions                               # JIT does not support calling kfunc bpf_throw                                (exceptions)
 get_stack_raw_tp                         # user_stack corrupted user stack                                             (no backchain userspace)
 stacktrace_build_id                      # compare_map_keys stackid_hmap vs. stackmap err -2 errno 2                   (?)
tools/testing/selftests/bpf/prog_tests/bits_iter.c new file +137 -0

137 lines not on this page · raw message

tools/testing/selftests/bpf/progs/test_bits_iter_failure.c new file +54 -0

54 lines not on this page · raw message

tools/testing/selftests/bpf/progs/test_bits_iter_success.c new file +122 -0

122 lines not on this page · raw message

Signature · 1 line
2.39.1
#2 lore raw

Re: [PATCH v3 bpf-next 2/2] selftests/bpf: Add selftest for bits iter

Quoted 8 lines · Yafang Shao

Add selftests for the newly added bits iter.
- bits_iter_success
- percpu data extracted from the percpu struct should be expected
- RCU lock is not required
- It is fine without calling bpf_iter_cpumask_next()
- It can work as expected when invalid arguments are passed

Quoted 8 lines

- bits_iter_failure
- bpf_iter_bits_destroy() is required after calling

    bpf_iter_bits_new()

- bpf_iter_bits_destroy() can only destroy an initialized iter
- bpf_iter_bits_next() must use an initialized iter

This test case can't work correctly on s390x for unknonw reason, thus it is added to DENYLIST.s390x.

That's an unusual way of handling "doesn't work for unknown reason" :) This might be an endianness issue I pointed out in patch #1.

pw-bot: cr

Quoted 24 lines
---
 tools/testing/selftests/bpf/DENYLIST.s390x    |   3 +-
 .../selftests/bpf/prog_tests/bits_iter.c      | 137 ++++++++++++++++++
 .../bpf/progs/test_bits_iter_failure.c        |  54 +++++++
 .../bpf/progs/test_bits_iter_success.c        | 122 ++++++++++++++++
 4 files changed, 315 insertions(+), 1 deletion(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/bits_iter.c
 create mode 100644 tools/testing/selftests/bpf/progs/test_bits_iter_failure.c
 create mode 100644 tools/testing/selftests/bpf/progs/test_bits_iter_success.c
tools/testing/selftests/bpf/DENYLIST.s390x +2 -1
index 1a63996c0304..0cd6d2bf1ff4 100644
@@ -1,5 +1,6 @@
 # TEMPORARY
 # Alphabetical order
-exceptions                              # JIT does not support calling kfunc bpf_throw                                (exceptions)
+bits_iter                                # cpumask iter can't work as expected                                         (?)
+exceptions                               # JIT does not support calling kfunc bpf_throw                                (exceptions)
 get_stack_raw_tp                         # user_stack corrupted user stack                                             (no backchain userspace)
 stacktrace_build_id                      # compare_map_keys stackid_hmap vs. stackmap err -2 errno 2                   (?)

[...]

#3 lore raw

Re: [PATCH v3 bpf-next 2/2] selftests/bpf: Add selftest for bits iter

Quoted 16 lines · Andrii Nakryiko
Quoted 14 lines · Yafang Shao

Add selftests for the newly added bits iter.
- bits_iter_success
- percpu data extracted from the percpu struct should be expected
- RCU lock is not required
- It is fine without calling bpf_iter_cpumask_next()
- It can work as expected when invalid arguments are passed

- bits_iter_failure
- bpf_iter_bits_destroy() is required after calling

    bpf_iter_bits_new()

- bpf_iter_bits_destroy() can only destroy an initialized iter
- bpf_iter_bits_next() must use an initialized iter

Quoted 7 lines
Quoted 2 lines

This test case can't work correctly on s390x for unknonw reason, thus it is added to DENYLIST.s390x.

That's an unusual way of handling "doesn't work for unknown reason" :) This might be an endianness issue I pointed out in patch #1.

pw-bot: cr

Thanks for your reminder.
will check it.

Signature · 2 lines
Regards
Yafang
#4 lore raw
In reply to Yafang Shao
Quoted 64 lines · Yafang Shao

Add three new kfuncs for the bits iterator:
- bpf_iter_bits_new
Initialize a new bits iterator for a given memory area. Due to the limitation of bpf memalloc, the max number of bits that can be iterated over is limited to (4096 * 8).
- bpf_iter_bits_next
Get the next bit in a bpf_iter_bits
- bpf_iter_bits_destroy
Destroy a bpf_iter_bits

The bits iterator facilitates the iteration of the bits of a memory area, such as cpumask. It can be used in any context and on any address.

---
 kernel/bpf/helpers.c | 117 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 117 insertions(+)
kernel/bpf/helpers.c +37 -0
index a89587859571..a769561b65ae 100644
@@ -2545,6 +2545,120 @@ __bpf_kfunc void bpf_throw(u64 cookie)
        WARN(1, "A call to BPF exception callback should never return\n");
 }
 
+struct bpf_iter_bits {
+       __u64 __opaque[2];
+} __aligned(8);
+
+struct bpf_iter_bits_kern {
+       union {
+               unsigned long *bits;
+               unsigned long bits_copy;
+       };
+       u32 nr_bits;
+       int bit;
+} __aligned(8);
+
+/**
+ * bpf_iter_bits_new() - Initialize a new bits iterator for a given memory area
+ * @it: The new bpf_iter_bits to be created
+ * @unsafe_ptr__ign: A ponter pointing to a memory area to be iterated over
+ * @nr_bits: The number of bits to be iterated over. Due to the limitation of
+ * memalloc, it can't greater than (4096 * 8).
+ *
+ * This function initializes a new bpf_iter_bits structure for iterating over
+ * a memory area which is specified by the @unsafe_ptr__ign and @nr_bits. It
+ * copy the data of the memory area to the newly created bpf_iter_bits @it for
+ * subsequent iteration operations.
+ *
+ * On success, 0 is returned. On failure, ERR is returned.
+ */
+__bpf_kfunc int
+bpf_iter_bits_new(struct bpf_iter_bits *it, const void *unsafe_ptr__ign, u32 nr_bits)
+{
+       struct bpf_iter_bits_kern *kit = (void *)it;
+       u32 size = BITS_TO_BYTES(nr_bits);
+       int err;
+
+       BUILD_BUG_ON(sizeof(struct bpf_iter_bits_kern) != sizeof(struct bpf_iter_bits));
+       BUILD_BUG_ON(__alignof__(struct bpf_iter_bits_kern) !=
+                    __alignof__(struct bpf_iter_bits));

kernel/bpf/helpers.c __bpf_kfunc void bpf_throw(u64 cookie) · line 2594

Quoted 10 lines
kernel/bpf/helpers.c +10 -0
+
+       if (!unsafe_ptr__ign || !nr_bits) {
+               kit->bits = NULL;
+               return -EINVAL;
+       }
+
+       kit->nr_bits = 0;
+       /* Optimization for u64/u32 mask */
+       if (nr_bits <= 64) {
+               err = bpf_probe_read_kernel_common(&kit->bits_copy, size, unsafe_ptr__ign);

it probably would be better to zero-initialize kit->bits_copy?

but also, please check that this works on big-endian right

Quoted 36 lines
kernel/bpf/helpers.c +36 -0
+               if (unlikely(err))
+                       return -EFAULT;
+
+               kit->nr_bits = nr_bits;
+               kit->bit = -1;
+               return 0;
+       }
+
+       /* Fallback to memalloc */
+       kit->bits = bpf_mem_alloc(&bpf_global_ma, size);
+       if (!kit->bits)
+               return -ENOMEM;
+
+       err = bpf_probe_read_kernel_common(kit->bits, size, unsafe_ptr__ign);
+       if (err) {
+               bpf_mem_free(&bpf_global_ma, kit->bits);
+               return err;
+       }
+
+       kit->nr_bits = nr_bits;
+       kit->bit = -1;
+       return 0;
+}
+
+/**
+ * bpf_iter_bits_next() - Get the next bit in a bpf_iter_bits
+ * @it: The bpf_iter_bits to be checked
+ *
+ * This function returns a pointer to a number representing the value of the
+ * next bit in the bits.
+ *
+ * If there are no further bit available, it returns NULL.
+ */
+__bpf_kfunc int *bpf_iter_bits_next(struct bpf_iter_bits *it)
+{
+       struct bpf_iter_bits_kern *kit = (void *)it;

kernel/bpf/helpers.c __bpf_kfunc void bpf_throw(u64 cookie) · line 2640

Quoted 10 lines
kernel/bpf/helpers.c +10 -0
+       u32 nr_bits = kit->nr_bits;
+       const unsigned long *bits;
+       int bit;
+
+       if (nr_bits == 0)
+               return NULL;
+
+       bits = nr_bits <= 64 ? &kit->bits_copy : kit->bits;
+       bit = find_next_bit(bits, kit->nr_bits, kit->bit + 1);
+       if (bit >= kit->nr_bits)

zero out nr_bits so subsequent next() calls keep returning NULL (sticky iterator behavior)

Quoted 37 lines
kernel/bpf/helpers.c +24 -1
+               return NULL;
+
+       kit->bit = bit;
+       return &kit->bit;
+}
+
+/**
+ * bpf_iter_bits_destroy() - Destroy a bpf_iter_bits
+ * @it: The bpf_iter_bits to be destroyed
+ *
+ * Destroy the resource associated with the bpf_iter_bits.
+ */
+__bpf_kfunc void bpf_iter_bits_destroy(struct bpf_iter_bits *it)
+{
+       struct bpf_iter_bits_kern *kit = (void *)it;
+
+       if (kit->nr_bits <= 64)
+               return;
+       bpf_mem_free(&bpf_global_ma, kit->bits);
+}
+
 __bpf_kfunc_end_defs();
 
 BTF_KFUNCS_START(generic_btf_ids)
@@ -2621,6 +2735,9 @@ BTF_ID_FLAGS(func, bpf_dynptr_is_null)
 BTF_ID_FLAGS(func, bpf_dynptr_is_rdonly)
 BTF_ID_FLAGS(func, bpf_dynptr_size)
 BTF_ID_FLAGS(func, bpf_dynptr_clone)
+BTF_ID_FLAGS(func, bpf_iter_bits_new, KF_ITER_NEW)
+BTF_ID_FLAGS(func, bpf_iter_bits_next, KF_ITER_NEXT | KF_RET_NULL)
+BTF_ID_FLAGS(func, bpf_iter_bits_destroy, KF_ITER_DESTROY)
 BTF_KFUNCS_END(common_btf_ids)
 
 static const struct btf_kfunc_id_set common_kfunc_set = {
--

2.39.1

#5 lore raw
Quoted 70 lines · Andrii Nakryiko
Quoted 68 lines · Yafang Shao

Add three new kfuncs for the bits iterator:
- bpf_iter_bits_new
Initialize a new bits iterator for a given memory area. Due to the limitation of bpf memalloc, the max number of bits that can be iterated over is limited to (4096 * 8).
- bpf_iter_bits_next
Get the next bit in a bpf_iter_bits
- bpf_iter_bits_destroy
Destroy a bpf_iter_bits

The bits iterator facilitates the iteration of the bits of a memory area, such as cpumask. It can be used in any context and on any address.

---
 kernel/bpf/helpers.c | 117 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 117 insertions(+)
kernel/bpf/helpers.c +41 -0
index a89587859571..a769561b65ae 100644
@@ -2545,6 +2545,120 @@ __bpf_kfunc void bpf_throw(u64 cookie)
        WARN(1, "A call to BPF exception callback should never return\n");
 }
 
+struct bpf_iter_bits {
+       __u64 __opaque[2];
+} __aligned(8);
+
+struct bpf_iter_bits_kern {
+       union {
+               unsigned long *bits;
+               unsigned long bits_copy;
+       };
+       u32 nr_bits;
+       int bit;
+} __aligned(8);
+
+/**
+ * bpf_iter_bits_new() - Initialize a new bits iterator for a given memory area
+ * @it: The new bpf_iter_bits to be created
+ * @unsafe_ptr__ign: A ponter pointing to a memory area to be iterated over
+ * @nr_bits: The number of bits to be iterated over. Due to the limitation of
+ * memalloc, it can't greater than (4096 * 8).
+ *
+ * This function initializes a new bpf_iter_bits structure for iterating over
+ * a memory area which is specified by the @unsafe_ptr__ign and @nr_bits. It
+ * copy the data of the memory area to the newly created bpf_iter_bits @it for
+ * subsequent iteration operations.
+ *
+ * On success, 0 is returned. On failure, ERR is returned.
+ */
+__bpf_kfunc int
+bpf_iter_bits_new(struct bpf_iter_bits *it, const void *unsafe_ptr__ign, u32 nr_bits)
+{
+       struct bpf_iter_bits_kern *kit = (void *)it;
+       u32 size = BITS_TO_BYTES(nr_bits);
+       int err;
+
+       BUILD_BUG_ON(sizeof(struct bpf_iter_bits_kern) != sizeof(struct bpf_iter_bits));
+       BUILD_BUG_ON(__alignof__(struct bpf_iter_bits_kern) !=
+                    __alignof__(struct bpf_iter_bits));
+
+       if (!unsafe_ptr__ign || !nr_bits) {
+               kit->bits = NULL;
+               return -EINVAL;
Quoted 8 lines

kernel/bpf/helpers.c __bpf_kfunc void bpf_throw(u64 cookie) · line 2594

Quoted 6 lines
kernel/bpf/helpers.c +6 -0
+       }
+
+       kit->nr_bits = 0;
+       /* Optimization for u64/u32 mask */
+       if (nr_bits <= 64) {
+               err = bpf_probe_read_kernel_common(&kit->bits_copy, size, unsafe_ptr__ign);

it probably would be better to zero-initialize kit->bits_copy?

will do it.

Quoted 1 line

but also, please check that this works on big-endian right

will check.

Quoted 42 lines
Quoted 42 lines
kernel/bpf/helpers.c +41 -0
+               if (unlikely(err))
+                       return -EFAULT;
+
+               kit->nr_bits = nr_bits;
+               kit->bit = -1;
+               return 0;
+       }
+
+       /* Fallback to memalloc */
+       kit->bits = bpf_mem_alloc(&bpf_global_ma, size);
+       if (!kit->bits)
+               return -ENOMEM;
+
+       err = bpf_probe_read_kernel_common(kit->bits, size, unsafe_ptr__ign);
+       if (err) {
+               bpf_mem_free(&bpf_global_ma, kit->bits);
+               return err;
+       }
+
+       kit->nr_bits = nr_bits;
+       kit->bit = -1;
+       return 0;
+}
+
+/**
+ * bpf_iter_bits_next() - Get the next bit in a bpf_iter_bits
+ * @it: The bpf_iter_bits to be checked
+ *
+ * This function returns a pointer to a number representing the value of the
+ * next bit in the bits.
+ *
+ * If there are no further bit available, it returns NULL.
+ */
+__bpf_kfunc int *bpf_iter_bits_next(struct bpf_iter_bits *it)
+{
+       struct bpf_iter_bits_kern *kit = (void *)it;
+       u32 nr_bits = kit->nr_bits;
+       const unsigned long *bits;
+       int bit;
+
+       if (nr_bits == 0)
Quoted 8 lines

kernel/bpf/helpers.c __bpf_kfunc void bpf_throw(u64 cookie) · line 2640

Quoted 5 lines
kernel/bpf/helpers.c +5 -0
+               return NULL;
+
+       bits = nr_bits <= 64 ? &kit->bits_copy : kit->bits;
+       bit = find_next_bit(bits, kit->nr_bits, kit->bit + 1);
+       if (bit >= kit->nr_bits)

zero out nr_bits so subsequent next() calls keep returning NULL (sticky iterator behavior)

Good suggestion. will change it.

Signature · 2 lines
Regards
Yafang