bpf: Add a generic bits iterator
Subsystems (3)
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
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
@@ -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
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 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 | 100 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 100 insertions(+)kernel/bpf/helpers.c +33
-0@@ -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
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 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 | 100 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 100 insertions(+)kernel/bpf/helpers.c +38
-0@@ -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 ofunsigned long *bitsandunsigned long bits_copy. As a performance optimization (and to reduce dependency on memory allocation). WDYT?
Signature · 2 lines
Regards Yafang
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 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 | 100 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 100 insertions(+)kernel/bpf/helpers.c +38
-0@@ -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 ofunsigned long *bitsandunsigned long bits_copy. As a performance optimization (and to reduce dependency on memory allocation). WDYT?--
Regards
Yafang
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 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 | 100 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 100 insertions(+)kernel/bpf/helpers.c +33
-0@@ -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_statein verifier code, which has u32reg_maskand u64stack_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 ofunsigned long *bitsandunsigned long bits_copy. As a performance optimization (and to reduce dependency on memory allocation). WDYT?--
Regards
Yafang
Signature · 2 lines
Regards Yafang
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 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 | 100 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 100 insertions(+)kernel/bpf/helpers.c +33
-0@@ -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_statein verifier code, which has u32reg_maskand u64stack_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 ofunsigned long *bitsandunsigned 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
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 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 | 100 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 100 insertions(+)kernel/bpf/helpers.c +33
-0@@ -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_statein verifier code, which has u32reg_maskand u64stack_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
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 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 | 100 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 100 insertions(+)kernel/bpf/helpers.c +33
-0@@ -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_statein verifier code, which has u32reg_maskand u64stack_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
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 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]>---
[...]
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_statein verifier code, which has u32reg_maskand u64stack_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 thefind_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
PATCH v2 2/2 selftests/bpf: Add selftest for bits iter
In reply to Yafang ShaoAdd 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
@@ -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