bpf: Add bits iterator
Subsystems (3)
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
@@ -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
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
@@ -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
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 callingbpf_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 callingbpf_iter_bits_new()-
bpf_iter_bits_destroy()can only destroy an initialized iter
-bpf_iter_bits_next()must use an initialized iterThis 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
Signed-off-by Yafang Shao <[email protected]>--- 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.ctools/testing/selftests/bpf/DENYLIST.s390x +2
-1@@ -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 (?)
[...]
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 callingbpf_iter_cpumask_next()
- It can work as expected when invalid arguments are passed-
bits_iter_failure
-bpf_iter_bits_destroy()is required after callingbpf_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
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 abpf_iter_bits
-bpf_iter_bits_destroy
Destroy abpf_iter_bitsThe 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.
Signed-off-by Yafang Shao <[email protected]>--- kernel/bpf/helpers.c | 117 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 117 insertions(+)kernel/bpf/helpers.c +37
-0@@ -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
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 abpf_iter_bits
-bpf_iter_bits_destroy
Destroy abpf_iter_bitsThe 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.
Signed-off-by Yafang Shao <[email protected]>--- kernel/bpf/helpers.c | 117 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 117 insertions(+)kernel/bpf/helpers.c +41
-0@@ -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_bitsso subsequentnext()calls keep returning NULL (sticky iterator behavior)
Good suggestion. will change it.
Signature · 2 lines
Regards Yafang