bpf: Add a generic bits iterator
Subsystems (3)
v5 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.
Changes:
- v4->v5:
- Simplify test cases (Andrii)
- v3->v4:
- Fix endianness error on s390x (Andrii)
- zero-initialize kit->bits_copy and zero out nr_bits (Andrii)
- v2->v3:
- Optimization for u64/u32 mask (Andrii)
- 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 | 120 ++++++++++++++++++ .../selftests/bpf/prog_tests/verifier.c | 2 + .../selftests/bpf/progs/verifier_bits_iter.c | 57 +++++++++ 3 files changed, 179 insertions(+) create mode 100644 tools/testing/selftests/bpf/progs/verifier_bits_iter.c
Signature · 1 line
2.39.1
PATCH v5 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 | 120 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 120 insertions(+)
kernel/bpf/helpers.c +120 -0
@@ -2549,6 +2549,123 @@ __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) +{ +u32 size =BITS_TO_LONGS (nr_bits) *sizeof (unsigned long ); +struct bpf_iter_bits_kern *kit = (void *)it; +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 ; + kit->bits_copy =0 ; +/* Optimization for u64/u32 mask */ +if (nr_bits <=64 ) { + err =bpf_probe_read_kernel_common (&kit->bits_copy, size, unsafe_ptr__ign); +if (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, nr_bits, kit->bit +1 ); +if (bit >= nr_bits) { + kit->nr_bits =0 ; +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)
@@ -2626,6 +2743,9 @@ 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_modify_return_test_tp) +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.30.1 (Apple Git-130)
PATCH v5 2/2 selftests/bpf: Add selftest for bits iter
In reply to Yafang ShaoAdd test cases for the bits iter:
- 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/verifier.c | 2 + .../selftests/bpf/progs/verifier_bits_iter.c | 57 +++++++++++++++++++ 2 files changed, 59 insertions(+) create mode 100644 tools/testing/selftests/bpf/progs/verifier_bits_iter.c
tools/testing/selftests/bpf/prog_tests/verifier.c +2 -0
@@ -84,6 +84,7 @@#include "verifier_xadd.skel.h" #include "verifier_xdp.skel.h" #include "verifier_xdp_direct_packet_access.skel.h" +#include "verifier_bits_iter.skel.h" #define MAX_ENTRIES 11
@@ -198,6 +199,7 @@ void test_verifier_var_off(void) { RUN(verifier_var_off); }void test_verifier_xadd (void ) {RUN (verifier_xadd); }void test_verifier_xdp (void ) {RUN (verifier_xdp); }void test_verifier_xdp_direct_packet_access (void ) {RUN (verifier_xdp_direct_packet_access); } +void test_verifier_bits_iter (void ) {RUN (verifier_bits_iter); }static int init_test_val_map (struct bpf_object *obj,char *map_name) {
tools/testing/selftests/bpf/progs/verifier_bits_iter.c new file +57 -0
57 lines not on this page · raw message
Signature · 1 line
2.30.1 (Apple Git-130)
Quoted 14 lines · Yafang Shao
Three new kfuncs, namely bpf_iter_bits_{new,next,destroy}, have been added for the new
bpf_iter_bitsfunctionality. 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 abpf_iter_bits
-bpf_iter_bits_destroy
Destroy abpf_iter_bits
Quoted 5 lines
The bits iterator can be used in any context and on any address.
Changes:
-v4->v5:
- Simplify test cases (Andrii)
hm... I think you oversimplified them :) Your negative tests are good, but there is now no "positive" test that shows that iterator functions properly. I'd suggest to add few positive tests (still within RUN_TESTS framework) using __retval (grep for other use cases using it) to check actual values.
I think you need to validate that iterator works for:
a) bit mask smaller than 8 bytes (and also maybe number of bits that are not multiple of 8, e.g., have 20 bit bitmask, but set entire 32-bit value to 1s, check that you get only 20 iterator next() returns)
b) a typical case of having 8-byte bit mask (you can have some irregular pattern of bits, like 0b1111000111001101, and calculate a sum of bit positions, returned for __retval check. This will catch endianness issues, if there are still any.
c) another typical case where bit mask is > 8 bytes (same idea with position sum would work, but probably just counting number of bits would be enough)
pw-bot: cr
Quoted 26 lines
-
v3->v4:
- Fix endianness error on s390x (Andrii)
- zero-initializekit->bits_copyand zero outnr_bits(Andrii)
-v2->v3:
- Optimization for u64/u32 mask (Andrii)
-v1->v2:
- Simplify the CPU number verification code to avoid the failure on s390x (Eduard)
- bpf: Addbpf_iter_cpumask
https://lwn.net/Articles/961104/
- bpf: Add new bpf helperbpf_for_each_cpu
https://lwn.net/Articles/939939/Yafang Shao (2):
bpf: Add bits iterator
selftests/bpf: Add selftest for bits iterkernel/bpf/helpers.c | 120 ++++++++++++++++++ .../selftests/bpf/prog_tests/verifier.c | 2 + .../selftests/bpf/progs/verifier_bits_iter.c | 57 +++++++++ 3 files changed, 179 insertions(+) create mode 100644 tools/testing/selftests/bpf/progs/verifier_bits_iter.c--
2.39.1
Quoted 16 lines · Andrii Nakryiko
Quoted 14 lines · Yafang Shao
Three new kfuncs, namely bpf_iter_bits_{new,next,destroy}, have been added for the new
bpf_iter_bitsfunctionality. 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 abpf_iter_bits
-bpf_iter_bits_destroy
Destroy abpf_iter_bits
Quoted 7 lines
Quoted 5 lines
The bits iterator can be used in any context and on any address.
Changes:
-v4->v5:
- Simplify test cases (Andrii)hm... I think you oversimplified them :) Your negative tests are good,
I misinterpreted your earlier comment :(
Quoted 12 lines
but there is now no "positive" test that shows that iterator functions properly. I'd suggest to add few positive tests (still within
RUN_TESTSframework) using__retval(grep for other use cases using it) to check actual values.I think you need to validate that iterator works for:
a) bit mask smaller than 8 bytes (and also maybe number of bits that are not multiple of 8, e.g., have 20 bit bitmask, but set entire 32-bit value to 1s, check that you get only 20 iterator
next()returns)
Quoted 8 lines
b) a typical case of having 8-byte bit mask (you can have some irregular pattern of bits, like
0b1111000111001101, and calculate a sum of bit positions, returned for__retvalcheck. This will catch endianness issues, if there are still any.c) another typical case where bit mask is > 8 bytes (same idea with position sum would work, but probably just counting number of bits would be enough)
Thank you for providing such a detailed explanation. I will take some time to carefully consider it.
Signature · 2 lines
Regards Yafang