Skip to contentSkip to conversation

bpf: Add a generic bits iterator

PATCH Superseded Yafang Shao 3 participants 11 messages Feb 25, 2024 – Mar 1, 2024

Subsystems (3)

v2 of 8 Superseded Latest is v8 →

lore
Share & tools
lore
#0 lore raw

v2 cover bpf: Add a generic bits iterator

Three new kfuncs, namely bpf_iter_bits_{new,next,destroy}, have been added for the new bpf_iter_bits functionality. These kfuncs enable the iteration of the bits from a given address and a given number of bits.

- 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 to be iterated over is (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 can be used in any context and on any address.

In our specific use case, we leverage the cgroup iterator to traverse percpu data, subsequently exposing it to userspace through a seq file. Refer to example in patch #2 for the usage.

Changes:
- v1->v2:
- Simplify the CPU number verification code to avoid the failure on s390x (Eduard)
- bpf: Add bpf_iter_cpumask
https://lwn.net/Articles/961104/
- bpf: Add new bpf helper bpf_for_each_cpu
https://lwn.net/Articles/939939/

Yafang Shao (2):
bpf: Add bits iterator
selftests/bpf: Add selftest for bits iter

 kernel/bpf/helpers.c                          | 100 +++++++++++++
 .../selftests/bpf/prog_tests/bits_iter.c      | 132 ++++++++++++++++++
 .../bpf/progs/test_bits_iter_failure.c        |  54 +++++++
 .../bpf/progs/test_bits_iter_success.c        | 112 +++++++++++++++
 4 files changed, 398 insertions(+)
 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
Signature · 1 line
2.39.1
#1 lore raw

PATCH v2 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 | 100 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 100 insertions(+)
kernel/bpf/helpers.c +100 -0
index 93edf730d288..052f63891834 100644
@@ -2542,6 +2542,103 @@ __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 {
+	unsigned long *bits;
+	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->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);
+		kit->bits = NULL;
+		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;
+	const unsigned long *bits = kit->bits;
+	int bit;
+
+	if (!bits)
+		return NULL;
+
+	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->bits)
+		return;
+	bpf_mem_free(&bpf_global_ma, kit->bits);
+}
+
 __bpf_kfunc_end_defs();
 
 BTF_KFUNCS_START(generic_btf_ids)
@@ -2618,6 +2715,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
#2 lore raw

Re: [PATCH v2 bpf-next 1/2] bpf: Add bits iterator

Quoted 60 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 | 100 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 100 insertions(+)
kernel/bpf/helpers.c +33 -0
index 93edf730d288..052f63891834 100644
@@ -2542,6 +2542,103 @@ __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 {
+       unsigned long *bits;
+       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) !=

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

Quoted 10 lines
kernel/bpf/helpers.c +10 -0
+                    __alignof__(struct bpf_iter_bits));
+
+       if (!unsafe_ptr__ign || !nr_bits) {
+               kit->bits = NULL;
+               return -EINVAL;
+       }
+
+       kit->bits = bpf_mem_alloc(&bpf_global_ma, size);
+       if (!kit->bits)
+               return -ENOMEM;

it's probably going to be a pretty common case to do bits iteration for nr_bits<=64, right? So as an optimization, instead of doing bpf_mem_alloc() for this case, you can just copy up to 8 bytes and store it in a union of unsigned long *bits and unsigned long bits_copy. As a performance optimization (and to reduce dependency on memory allocation). WDYT?

Quoted 70 lines
kernel/bpf/helpers.c +57 -1
+
+       err = bpf_probe_read_kernel_common(kit->bits, size, unsafe_ptr__ign);
+       if (err) {
+               bpf_mem_free(&bpf_global_ma, kit->bits);
+               kit->bits = NULL;
+               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;
+       const unsigned long *bits = kit->bits;
+       int bit;
+
+       if (!bits)
+               return NULL;
+
+       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->bits)
+               return;
+       bpf_mem_free(&bpf_global_ma, kit->bits);
+}
+
 __bpf_kfunc_end_defs();
 
 BTF_KFUNCS_START(generic_btf_ids)
@@ -2618,6 +2715,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

#3 lore raw

Re: [PATCH v2 bpf-next 1/2] bpf: Add bits iterator

Quoted 67 lines · Andrii Nakryiko
Quoted 65 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 | 100 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 100 insertions(+)
kernel/bpf/helpers.c +38 -0
index 93edf730d288..052f63891834 100644
@@ -2542,6 +2542,103 @@ __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 {
+       unsigned long *bits;
+       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 2587

Quoted 5 lines
kernel/bpf/helpers.c +5 -0
+       }
+
+       kit->bits = bpf_mem_alloc(&bpf_global_ma, size);
+       if (!kit->bits)
+               return -ENOMEM;

it's probably going to be a pretty common case to do bits iteration for nr_bits<=64, right?

It's highly unlikely.
Consider the CPU count as an example; There are 256 CPUs on our AMD EPYC servers.

Quoted 6 lines

So as an optimization, instead of doing
bpf_mem_alloc() for this case, you can just copy up to 8 bytes and store it in a union of unsigned long *bits and unsigned long bits_copy. As a performance optimization (and to reduce dependency on memory allocation). WDYT?

Signature · 2 lines
Regards
Yafang
#4 lore raw

Re: [PATCH v2 bpf-next 1/2] bpf: Add bits iterator

Quoted 79 lines · Yafang Shao
Quoted 67 lines · Andrii Nakryiko
Quoted 65 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 | 100 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 100 insertions(+)
kernel/bpf/helpers.c +38 -0
index 93edf730d288..052f63891834 100644
@@ -2542,6 +2542,103 @@ __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 {
+       unsigned long *bits;
+       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 2587

Quoted 5 lines
kernel/bpf/helpers.c +5 -0
+       }
+
+       kit->bits = bpf_mem_alloc(&bpf_global_ma, size);
+       if (!kit->bits)
+               return -ENOMEM;

it's probably going to be a pretty common case to do bits iteration for nr_bits<=64, right?

Quoted 3 lines

It's highly unlikely.
Consider the CPU count as an example; There are 256 CPUs on our AMD EPYC servers.

Also consider u64-based bit masks (like struct backtrack_state in verifier code, which has u32 reg_mask and u64 stack_mask). This iterator is a generic bits iterator, there are tons of cases of u64/u32 masks in practice.

Quoted 11 lines
Quoted 7 lines

So as an optimization, instead of doing
bpf_mem_alloc() for this case, you can just copy up to 8 bytes and store it in a union of unsigned long *bits and unsigned long bits_copy. As a performance optimization (and to reduce dependency on memory allocation). WDYT?

--
Regards
Yafang

#5 lore raw

Re: [PATCH v2 bpf-next 1/2] bpf: Add bits iterator

Quoted 81 lines · Andrii Nakryiko
Quoted 79 lines · Yafang Shao
Quoted 75 lines · Andrii Nakryiko
Quoted 60 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 | 100 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 100 insertions(+)
kernel/bpf/helpers.c +33 -0
index 93edf730d288..052f63891834 100644
@@ -2542,6 +2542,103 @@ __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 {
+       unsigned long *bits;
+       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) !=

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

Quoted 10 lines
kernel/bpf/helpers.c +10 -0
+                    __alignof__(struct bpf_iter_bits));
+
+       if (!unsafe_ptr__ign || !nr_bits) {
+               kit->bits = NULL;
+               return -EINVAL;
+       }
+
+       kit->bits = bpf_mem_alloc(&bpf_global_ma, size);
+       if (!kit->bits)
+               return -ENOMEM;

it's probably going to be a pretty common case to do bits iteration for nr_bits<=64, right?

Quoted 8 lines
Quoted 3 lines

It's highly unlikely.
Consider the CPU count as an example; There are 256 CPUs on our AMD EPYC servers.

Also consider u64-based bit masks (like struct backtrack_state in verifier code, which has u32 reg_mask and u64 stack_mask). This iterator is a generic bits iterator, there are tons of cases of u64/u32 masks in practice.

Should we optimize it as follows?

    if (nr_bits <= 64) {
        // do the optimization
    } else {
        // fallback to memalloc
    }
Quoted 12 lines
Quoted 12 lines
Quoted 8 lines

So as an optimization, instead of doing
bpf_mem_alloc() for this case, you can just copy up to 8 bytes and store it in a union of unsigned long *bits and unsigned long bits_copy. As a performance optimization (and to reduce dependency on memory allocation). WDYT?

--
Regards
Yafang

Signature · 2 lines
Regards
Yafang
#6 lore raw

Re: [PATCH v2 bpf-next 1/2] bpf: Add bits iterator

Quoted 93 lines · Yafang Shao
Quoted 81 lines · Andrii Nakryiko
Quoted 79 lines · Yafang Shao
Quoted 75 lines · Andrii Nakryiko
Quoted 60 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 | 100 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 100 insertions(+)
kernel/bpf/helpers.c +33 -0
index 93edf730d288..052f63891834 100644
@@ -2542,6 +2542,103 @@ __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 {
+       unsigned long *bits;
+       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) !=

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

Quoted 10 lines
kernel/bpf/helpers.c +10 -0
+                    __alignof__(struct bpf_iter_bits));
+
+       if (!unsafe_ptr__ign || !nr_bits) {
+               kit->bits = NULL;
+               return -EINVAL;
+       }
+
+       kit->bits = bpf_mem_alloc(&bpf_global_ma, size);
+       if (!kit->bits)
+               return -ENOMEM;

it's probably going to be a pretty common case to do bits iteration for nr_bits<=64, right?

Quoted 8 lines
Quoted 3 lines

It's highly unlikely.
Consider the CPU count as an example; There are 256 CPUs on our AMD EPYC servers.

Also consider u64-based bit masks (like struct backtrack_state in verifier code, which has u32 reg_mask and u64 stack_mask). This iterator is a generic bits iterator, there are tons of cases of u64/u32 masks in practice.

Quoted 8 lines

Should we optimize it as follows?

    if (nr_bits <= 64) {
        // do the optimization
    } else {
        // fallback to memalloc
    }

Yep, that's what I'm proposing

Quoted 18 lines
Quoted 9 lines
Quoted 9 lines
Quoted 8 lines

So as an optimization, instead of doing
bpf_mem_alloc() for this case, you can just copy up to 8 bytes and store it in a union of unsigned long *bits and unsigned long bits_copy. As a performance optimization (and to reduce dependency on memory allocation). WDYT?

Quoted 3 lines
Quoted 3 lines

--
Regards
Yafang

--
Regards
Yafang

#7 lore raw

Re: [PATCH v2 bpf-next 1/2] bpf: Add bits iterator

Quoted 96 lines · Andrii Nakryiko
Quoted 95 lines · Yafang Shao
Quoted 81 lines · Andrii Nakryiko
Quoted 79 lines · Yafang Shao
Quoted 75 lines · Andrii Nakryiko
Quoted 60 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 | 100 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 100 insertions(+)
kernel/bpf/helpers.c +33 -0
index 93edf730d288..052f63891834 100644
@@ -2542,6 +2542,103 @@ __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 {
+       unsigned long *bits;
+       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) !=

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

Quoted 10 lines
kernel/bpf/helpers.c +10 -0
+                    __alignof__(struct bpf_iter_bits));
+
+       if (!unsafe_ptr__ign || !nr_bits) {
+               kit->bits = NULL;
+               return -EINVAL;
+       }
+
+       kit->bits = bpf_mem_alloc(&bpf_global_ma, size);
+       if (!kit->bits)
+               return -ENOMEM;

it's probably going to be a pretty common case to do bits iteration for nr_bits<=64, right?

Quoted 8 lines
Quoted 3 lines

It's highly unlikely.
Consider the CPU count as an example; There are 256 CPUs on our AMD EPYC servers.

Also consider u64-based bit masks (like struct backtrack_state in verifier code, which has u32 reg_mask and u64 stack_mask). This iterator is a generic bits iterator, there are tons of cases of u64/u32 masks in practice.

Should we optimize it as follows?

Quoted 8 lines
Quoted 6 lines
    if (nr_bits <= 64) {
        // do the optimization
    } else {
        // fallback to memalloc
    }

Yep, that's what I'm proposing

When I suggested why not just open code this in BPF earlier I was mostly thinking of these u64 and u32 masks we have lots of them in our code base as well.

I have something like this which might be even better than 3 calls depending on your use case,

int find_next_bit(uint64_t bits, int last_bit)

 {
    int i = last_bit;
    for (i = 0; i < sizeof(uint64_t) * 8; i++) {
        if (bits & (1 << i))
           return i;
    }
    return -1;

}

Verifier seems plenty happy with above.

Thanks,
John

#8 lore raw

Re: [PATCH v2 bpf-next 1/2] bpf: Add bits iterator

Quoted 122 lines · John Fastabend
Quoted 96 lines · Andrii Nakryiko
Quoted 95 lines · Yafang Shao
Quoted 81 lines · Andrii Nakryiko
Quoted 79 lines · Yafang Shao
Quoted 75 lines · Andrii Nakryiko
Quoted 60 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 | 100 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 100 insertions(+)
kernel/bpf/helpers.c +33 -0
index 93edf730d288..052f63891834 100644
@@ -2542,6 +2542,103 @@ __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 {
+       unsigned long *bits;
+       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) !=

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

Quoted 10 lines
kernel/bpf/helpers.c +10 -0
+                    __alignof__(struct bpf_iter_bits));
+
+       if (!unsafe_ptr__ign || !nr_bits) {
+               kit->bits = NULL;
+               return -EINVAL;
+       }
+
+       kit->bits = bpf_mem_alloc(&bpf_global_ma, size);
+       if (!kit->bits)
+               return -ENOMEM;

it's probably going to be a pretty common case to do bits iteration for nr_bits<=64, right?

Quoted 8 lines
Quoted 3 lines

It's highly unlikely.
Consider the CPU count as an example; There are 256 CPUs on our AMD EPYC servers.

Also consider u64-based bit masks (like struct backtrack_state in verifier code, which has u32 reg_mask and u64 stack_mask). This iterator is a generic bits iterator, there are tons of cases of u64/u32 masks in practice.

Should we optimize it as follows?

Quoted 8 lines
Quoted 6 lines
    if (nr_bits <= 64) {
        // do the optimization
    } else {
        // fallback to memalloc
    }

Yep, that's what I'm proposing

When I suggested why not just open code this in BPF earlier I was mostly thinking of these u64 and u32 masks we have lots of them in our code base as well.

I have something like this which might be even better than 3 calls depending on your use case,

int find_next_bit(uint64_t bits, int last_bit)

 {
    int i = last_bit;
    for (i = 0; i < sizeof(uint64_t) * 8; i++) {
        if (bits & (1 << i))
           return i;
    }
    return -1;
Quoted 3 lines

}

Verifier seems plenty happy with above.

I'm not quite following.
Regarding the find_next_bit() function you mentioned, it seems it only retrieves one bit at a time, necessitating a for loop for execution, correct? Consequently, the verifier will likely fail the for loop.

Signature · 2 lines
Regards
Yafang
#9 lore raw

Re: [PATCH v2 bpf-next 1/2] bpf: Add bits iterator

Quoted 30 lines · Yafang Shao
Quoted 29 lines · John Fastabend
Quoted 27 lines · Andrii Nakryiko
Quoted 26 lines · Yafang Shao
Quoted 23 lines · Andrii Nakryiko
Quoted 21 lines · Yafang Shao
Quoted 18 lines · Andrii Nakryiko
Quoted 16 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.

---

[...]

Quoted 74 lines
Quoted 74 lines
Quoted 48 lines
Quoted 48 lines
Quoted 37 lines
Quoted 37 lines
Quoted 36 lines
Quoted 23 lines
(quoted diff) +23 -0
+/**
+ * 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) !=

Review

Quoted 10 lines
(quoted diff) +10 -0
+                    __alignof__(struct bpf_iter_bits));
+
+       if (!unsafe_ptr__ign || !nr_bits) {
+               kit->bits = NULL;
+               return -EINVAL;
+       }
+
+       kit->bits = bpf_mem_alloc(&bpf_global_ma, size);
+       if (!kit->bits)
+               return -ENOMEM;

it's probably going to be a pretty common case to do bits iteration for nr_bits<=64, right?

Quoted 8 lines
Quoted 3 lines

It's highly unlikely.
Consider the CPU count as an example; There are 256 CPUs on our AMD EPYC servers.

Also consider u64-based bit masks (like struct backtrack_state in verifier code, which has u32 reg_mask and u64 stack_mask). This iterator is a generic bits iterator, there are tons of cases of u64/u32 masks in practice.

Should we optimize it as follows?

Quoted 8 lines
Quoted 6 lines
    if (nr_bits <= 64) {
        // do the optimization
    } else {
        // fallback to memalloc
    }

Yep, that's what I'm proposing

When I suggested why not just open code this in BPF earlier I was mostly thinking of these u64 and u32 masks we have lots of them in our code base as well.

I have something like this which might be even better than 3 calls depending on your use case,

int find_next_bit(uint64_t bits, int last_bit)

 {
    int i = last_bit;
    for (i = 0; i < sizeof(uint64_t) * 8; i++) {
        if (bits & (1 << i))
           return i;
    }
    return -1;

}

Quoted 6 lines
Quoted 1 line

Verifier seems plenty happy with above.

I'm not quite following.
Regarding the find_next_bit() function you mentioned, it seems it only retrieves one bit at a time, necessitating a for loop for execution, correct? Consequently, the verifier will likely fail the for loop.

In practice for small sizes uint64_t and uint32_t we don't see any issue. Just a comment that this can be open coded without much trouble in many cases. Not against the helper at all.

Quoted 4 lines
Signature · 3 lines
-- 
Regards
Yafang
#10 lore raw

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

In reply to 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

---
 .../selftests/bpf/prog_tests/bits_iter.c      | 132 ++++++++++++++++++
 .../bpf/progs/test_bits_iter_failure.c        |  54 +++++++
 .../bpf/progs/test_bits_iter_success.c        | 112 +++++++++++++++
 3 files changed, 298 insertions(+)
 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/prog_tests/bits_iter.c new file +132 -0
new file mode 100644
index 000000000000..8148b8991276
@@ -0,0 +1,132 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2024 Yafang Shao <[email protected]> */
+
+#define _GNU_SOURCE
+#include <sched.h>
+
+#include <test_progs.h>
+#include "test_bits_iter_success.skel.h"
+#include "test_bits_iter_failure.skel.h"
+#include "cgroup_helpers.h"
+
+static const char * const positive_testcases[] = {
+	"cpumask_iter",
+};
+
+static const char * const negative_testcases[] = {
+	"null_pointer",
+	"zero_bit",
+	"no_mem",
+};
+
+static int read_percpu_data(struct bpf_link *link)
+{
+	int iter_fd, len;
+	char buf[128];
+	size_t left;
+	char *p;
+
+	iter_fd = bpf_iter_create(bpf_link__fd(link));
+	if (!ASSERT_GE(iter_fd, 0, "iter_fd"))
+		return -1;
+
+	memset(buf, 0, sizeof(buf));
+	left = ARRAY_SIZE(buf);
+	p = buf;
+	while ((len = read(iter_fd, p, left)) > 0) {
+		p += len;
+		left -= len;
+	}
+
+	close(iter_fd);
+	return 0;
+}
+
+static void verify_iter_success(const char *prog_name, bool negative)
+{
+	DECLARE_LIBBPF_OPTS(bpf_iter_attach_opts, opts);
+	struct test_bits_iter_success *skel;
+	union bpf_iter_link_info linfo;
+	struct bpf_program *prog;
+	struct bpf_link *link;
+	int cgrp_fd, err, i;
+	cpu_set_t set;
+
+	if (setup_cgroup_environment())
+		return;
+
+	/* Utilize the cgroup iter */
+	cgrp_fd = get_root_cgroup();
+	if (!ASSERT_GE(cgrp_fd, 0, "create_cgrp"))
+		goto cleanup;
+
+	skel = test_bits_iter_success__open();
+	if (!ASSERT_OK_PTR(skel, "cpumask_iter_success__open"))
+		goto close_fd;
+
+	skel->bss->pid = getpid();
+
+	err = test_bits_iter_success__load(skel);
+	if (!ASSERT_OK(err, "cpumask_iter_success__load"))
+		goto destroy;
+
+	prog = bpf_object__find_program_by_name(skel->obj, prog_name);
+	if (!ASSERT_OK_PTR(prog, "bpf_object__find_program_by_name"))
+		goto destroy;
+
+	memset(&linfo, 0, sizeof(linfo));
+	linfo.cgroup.cgroup_fd = cgrp_fd;
+	linfo.cgroup.order = BPF_CGROUP_ITER_SELF_ONLY;
+	opts.link_info = &linfo;
+	opts.link_info_len = sizeof(linfo);
+	link = bpf_program__attach_iter(prog, &opts);
+	if (!ASSERT_OK_PTR(link, "bpf_program__attach"))
+		goto destroy;
+
+	if (negative)
+		goto negative;
+
+	CPU_ZERO(&set);
+	for (i = 0; i < libbpf_num_possible_cpus(); i++)
+		CPU_SET(i, &set);
+	err = sched_setaffinity(skel->bss->pid, sizeof(set), &set);
+	if (!ASSERT_OK(err, "setaffinity_all_cpus"))
+		goto free_link;
+	err = read_percpu_data(link);
+	if (!ASSERT_OK(err, "read_percpu_data"))
+		goto free_link;
+
+negative:
+	ASSERT_OK(skel->bss->err, "not_zero");
+
+free_link:
+	bpf_link__destroy(link);
+destroy:
+	test_bits_iter_success__destroy(skel);
+close_fd:
+	close(cgrp_fd);
+cleanup:
+	cleanup_cgroup_environment();
+}
+
+void test_bits_iter(void)
+{
+	int i;
+
+	for (i = 0; i < ARRAY_SIZE(positive_testcases); i++) {
+		if (!test__start_subtest(positive_testcases[i]))
+			continue;
+
+		verify_iter_success(positive_testcases[i], true);
+	}
+
+	for (i = 0; i < ARRAY_SIZE(negative_testcases); i++) {
+		if (!test__start_subtest(negative_testcases[i]))
+			continue;
+
+		verify_iter_success(negative_testcases[i], true);
+	}
+
+	RUN_TESTS(test_bits_iter_success);
+	RUN_TESTS(test_bits_iter_failure);
+}
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 +112 -0

112 lines not on this page · raw message

Signature · 1 line
2.39.1