BPF open-coded iterators
Subsystems (6)
Andrii Nakryiko
maintainerv5 cover BPF open-coded iterators
Add support for open-coded (aka inline) iterators in BPF world. This is a next evolution of gradually allowing more powerful and less restrictive looping and iteration capabilities to BPF programs.
We set up a framework for implementing all kinds of iterators (e.g., cgroup, task, file, etc, iterators), but this patch set only implements numbers iterator, which is used to implement ergonomic bpf_for() for-like construct (see patches #4-#5). We also add bpf_for_each(), which is a generic foreach-like construct that will work with any kind of open-coded iterator implementation, as long as we stick with bpf_iter_<type>_{new,next,destroy}() naming pattern (which we now enforce on the kernel side).
Patch #1 is preparatory refactoring for easier way to check for special kfunc calls. Patch #2 is adding iterator kfunc registration and validation logic, which is mostly independent from the rest of open-coded iterator logic, so is separated out for easier reviewing.
The meat of verifier-side logic is in patch #3. Patch #4 implements numbers iterator. I kept them separate to have clean reference for how to integrate new iterator types (now even simpler to do than in v1 of this patch set). Patch #5 adds bpf_for(), bpf_for_each(), and bpf_repeat() macros to bpf_misc.h, and also adds yet another pyperf test variant, now with bpf_for() loop. Patch #6 is verification tests, based on numbers iterator (as the only available right now). Patch #7 actually tests runtime behavior of numbers iterator.
Finally, with changes in v2, it's possible and trivial to implement custom iterators completely in kernel modules, which we showcase and test by adding a simple iterator returning same number a given number of times to bpf_testmod. Patch #8 is where all this happens and is tested.
Most of the relevant details are in corresponding commit messages or code comments.
v4->v5:
- fixing missed inner for() in is_iter_reg_valid_uninit, and fixed return
false (kernel test robot);
- typo fixes and comment/commit description improvements throughout the
patch set;v3->v4:
- remove unused variable from is_iter_reg_valid_init (kernel test robot);v2->v3:
- remove special kfunc leftovers for bpf_iter_num_{new,next,destroy};
- add iters/testmod_seq* to DENYLIST.s390x, it doesn't support kfuncs in
modules yet (CI);
v1->v2:
- rebased on latest, dropping previously landed preparatory patches;
- each iterator type now have its own struct bpf_iter_<type> which allows each iterator implementation to use exactly as much stack space as necessary, allowing to avoid runtime allocations (Alexei);
- reworked how iterator kfuncs are defined, no verifier changes are required
when adding new iterator type;
- added bpf_testmod-based iterator implementation;
- address the rest of feedback, comments, commit message adjustment, etc.
Andrii Nakryiko (8):
bpf: factor out fetching basic kfunc metadata
bpf: add iterator kfuncs registration and validation logic
bpf: add support for open-coded iterator loops
bpf: implement numbers iterator
selftests/bpf: add bpf_for_each(), bpf_for(), and bpf_repeat() macros selftests/bpf: add iterators tests
selftests/bpf: add number iterator tests
selftests/bpf: implement and test custom testmod_seq iterator
include/linux/bpf.h | 8 +- include/linux/bpf_verifier.h | 25 + include/linux/btf.h | 4 + include/uapi/linux/bpf.h | 8 + kernel/bpf/bpf_iter.c | 70 ++ kernel/bpf/btf.c | 112 ++- kernel/bpf/helpers.c | 3 + kernel/bpf/verifier.c | 687 ++++++++++++++++- tools/include/uapi/linux/bpf.h | 8 + tools/testing/selftests/bpf/DENYLIST.s390x | 1 + .../selftests/bpf/bpf_testmod/bpf_testmod.c | 42 +- .../selftests/bpf/bpf_testmod/bpf_testmod.h | 6 + .../bpf/prog_tests/bpf_verif_scale.c | 6 + .../testing/selftests/bpf/prog_tests/iters.c | 106 +++ .../bpf/prog_tests/uprobe_autoattach.c | 1 - tools/testing/selftests/bpf/progs/bpf_misc.h | 100 +++ tools/testing/selftests/bpf/progs/iters.c | 720 ++++++++++++++++++ .../selftests/bpf/progs/iters_looping.c | 163 ++++ tools/testing/selftests/bpf/progs/iters_num.c | 242 ++++++ .../selftests/bpf/progs/iters_state_safety.c | 426 +++++++++++ .../selftests/bpf/progs/iters_testmod_seq.c | 79 ++ tools/testing/selftests/bpf/progs/lsm.c | 4 +- tools/testing/selftests/bpf/progs/pyperf.h | 14 +- .../selftests/bpf/progs/pyperf600_iter.c | 7 + .../selftests/bpf/progs/pyperf600_nounroll.c | 3 - 25 files changed, 2790 insertions(+), 55 deletions(-) create mode 100644 tools/testing/selftests/bpf/prog_tests/iters.c create mode 100644 tools/testing/selftests/bpf/progs/iters.c create mode 100644 tools/testing/selftests/bpf/progs/iters_looping.c create mode 100644 tools/testing/selftests/bpf/progs/iters_num.c create mode 100644 tools/testing/selftests/bpf/progs/iters_state_safety.c create mode 100644 tools/testing/selftests/bpf/progs/iters_testmod_seq.c create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_iter.c
Signature · 1 line
2.34.1
Andrii Nakryiko
maintainerPATCH v5 1/8 bpf: factor out fetching basic kfunc metadata
Factor out logic to fetch basic kfunc metadata based on struct bpf_insn. This is not exactly short or trivial code to just copy/paste and this information is sometimes necessary in other parts of the verifier logic. Subsequent patches will rely on this to determine if an instruction is a kfunc call to iterator next method.
No functional changes intended, including that verbose() warning behavior when kfunc is not allowed for a particular program type.
--- kernel/bpf/verifier.c | 92 +++++++++++++++++++++++++++---------------- 1 file changed, 59 insertions(+), 33 deletions(-)
kernel/bpf/verifier.c +59 -33
@@ -10079,24 +10079,21 @@ static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_return 0 ; } -static int check_kfunc_call (struct bpf_verifier_env *env,struct bpf_insn *insn, -int *insn_idx_p) +static int fetch_kfunc_meta (struct bpf_verifier_env *env, +struct bpf_insn *insn, +struct bpf_kfunc_call_arg_meta *meta, +const char **kfunc_name) { -const struct btf_type *t, *func, *func_proto, *ptr_type; -u32 i, nargs, func_id, ptr_type_id, release_ref_obj_id; -struct bpf_reg_state *regs =cur_regs (env); -const char *func_name, *ptr_type_name; -bool sleepable, rcu_lock, rcu_unlock; -struct bpf_kfunc_call_arg_meta meta; -int err, insn_idx = *insn_idx_p; -const struct btf_param *args; -const struct btf_type *ret_t; +const struct btf_type *func, *func_proto; +u32 func_id, *kfunc_flags; +const char *func_name;struct btf *desc_btf; -u32 *kfunc_flags; -/* skip for now, but return error when we find this in fixup_kfunc_call */ +if (kfunc_name) + *kfunc_name =NULL ; +if (!insn->imm) -return 0 ; +return -EINVAL ; desc_btf =find_kfunc_desc_btf (env, insn->off);if (IS_ERR (desc_btf))
@@ -10105,22 +10102,51 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, func_id = insn->imm; func =btf_type_by_id (desc_btf, func_id); func_name =btf_name_by_offset (desc_btf, func->name_off); +if (kfunc_name) + *kfunc_name = func_name; func_proto =btf_type_by_id (desc_btf, func->type); kfunc_flags =btf_kfunc_id_set_contains (desc_btf,resolve_prog_type (env->prog), func_id);if (!kfunc_flags) { -verbose (env,"calling kernel function %s is not allowed\n" , - func_name);return -EACCES ; } -/* Prepare kfunc call metadata */ -memset (&meta,0 ,sizeof (meta)); - meta.btf = desc_btf; - meta.func_id = func_id; - meta.kfunc_flags = *kfunc_flags; - meta.func_proto = func_proto; - meta.func_name = func_name; +memset (meta,0 ,sizeof (*meta)); + meta->btf = desc_btf; + meta->func_id = func_id; + meta->kfunc_flags = *kfunc_flags; + meta->func_proto = func_proto; + meta->func_name = func_name; + +return 0 ; +} + +static int check_kfunc_call (struct bpf_verifier_env *env,struct bpf_insn *insn, +int *insn_idx_p) +{ +const struct btf_type *t, *ptr_type; +u32 i, nargs, ptr_type_id, release_ref_obj_id; +struct bpf_reg_state *regs =cur_regs (env); +const char *func_name, *ptr_type_name; +bool sleepable, rcu_lock, rcu_unlock; +struct bpf_kfunc_call_arg_meta meta; +struct bpf_insn_aux_data *insn_aux; +int err, insn_idx = *insn_idx_p; +const struct btf_param *args; +const struct btf_type *ret_t; +struct btf *desc_btf; + +/* skip for now, but return error when we find this in fixup_kfunc_call */ +if (!insn->imm) +return 0 ; + + err =fetch_kfunc_meta (env, insn, &meta, &func_name); +if (err == -EACCES && func_name) +verbose (env,"calling kernel function %s is not allowed\n" , func_name); +if (err) +return err; + desc_btf = meta.btf; + insn_aux = &env->insn_aux_data[insn_idx];if (is_kfunc_destructive (&meta) && !capable (CAP_SYS_BOOT )) {verbose (env,"destructive kfunc calls require CAP_SYS_BOOT capability\n" );
@@ -10173,7 +10199,7 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, err =release_reference (env, regs[meta.release_regno].ref_obj_id);if (err) {verbose (env,"kfunc %s#%d reference has not been acquired before\n" , - func_name, func_id); + func_name, meta.func_id);return err; } }
@@ -10185,14 +10211,14 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, err =ref_convert_owning_non_owning (env, release_ref_obj_id);if (err) {verbose (env,"kfunc %s#%d conversion of owning ref to non-owning failed\n" , - func_name, func_id); + func_name, meta.func_id);return err; } err =release_reference (env, release_ref_obj_id);if (err) {verbose (env,"kfunc %s#%d reference has not been acquired before\n" , - func_name, func_id); + func_name, meta.func_id);return err; } }
@@ -10202,7 +10228,7 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, set_rbtree_add_callback_state);if (err) {verbose (env,"kfunc %s#%d failed callback verification\n" , - func_name, func_id); + func_name, meta.func_id);return err; } }
@@ -10211,7 +10237,7 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,mark_reg_not_init (env, regs, caller_saved[i]);/* Check return type */ - t =btf_type_skip_modifiers (desc_btf, func_proto->type,NULL ); + t =btf_type_skip_modifiers (desc_btf, meta.func_proto->type,NULL );if (is_kfunc_acquire (&meta) && !btf_type_is_struct_ptr (meta.btf, t)) {/* Only exception is bpf_obj_new_impl */
@@ -10260,11 +10286,11 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, regs[BPF_REG_0 ].btf = ret_btf; regs[BPF_REG_0 ].btf_id = ret_btf_id; - env->insn_aux_data[insn_idx].obj_new_size = ret_t->size; - env->insn_aux_data[insn_idx].kptr_struct_meta = + insn_aux->obj_new_size = ret_t->size; + insn_aux->kptr_struct_meta =btf_find_struct_meta (ret_btf, ret_btf_id); }else if (meta.func_id == special_kfunc_list[KF_bpf_obj_drop_impl]) { - env->insn_aux_data[insn_idx].kptr_struct_meta = + insn_aux->kptr_struct_meta =btf_find_struct_meta (meta.arg_obj_drop.btf, meta.arg_obj_drop.btf_id); } else if (meta.func_id == special_kfunc_list[KF_bpf_list_pop_front] ||
@@ -10397,8 +10423,8 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, regs[BPF_REG_0 ].id = ++env->id_gen; }/* else { add_kfunc_call() ensures it is btf_type_is_void(t) } */ - nargs =btf_type_vlen (func_proto); - args = (const struct btf_param *)(func_proto +1 ); + nargs =btf_type_vlen (meta.func_proto); + args = (const struct btf_param *)(meta.func_proto +1 );for (i =0 ; i < nargs; i++) {u32 regno = i +1 ;
Signature · 1 line
2.34.1
Andrii Nakryiko
maintainerPATCH v5 2/8 bpf: add iterator kfuncs registration and validation logic
In reply to Andrii NakryikoAdd ability to register kfuncs that implement BPF open-coded iterator contract and enforce naming and function proto convention. Enforcement happens at the time of kfunc registration and significantly simplifies the rest of iterators logic in the verifier.
More details follow in subsequent patches, but we enforce the following conditions.
All kfuncs (constructor, next, destructor) have to be named consistenly as bpf_iter_<type>_{new,next,destroy}(), respectively. <type> represents iterator type, and iterator state should be represented as a matching struct bpf_iter_<type> state type. Also, all iter kfuncs should have a pointer to this struct bpf_iter_<type> as the very first argument.
Additionally:
- Constructor, i.e., bpf_iter_<type>_new(), can have arbitrary extra number of arguments. Return type is not enforced either.
- Next method, i.e., bpf_iter_<type>_next(), has to return a pointer type and should have exactly one argument: struct bpf_iter_<type> * (const/volatile/restrict and typedefs are ignored).
- Destructor, i.e., bpf_iter_<type>_destroy(), should return void and should have exactly one argument, similar to the next method.
- struct bpf_iter_<type> size is enforced to be positive and a multiple of 8 bytes (to fit stack slots correctly).
Such strictness and consistency allows to build generic helpers abstracting important, but boilerplate, details to be able to use open-coded iterators effectively and ergonomically (see bpf_for_each() in subsequent patches). It also simplifies the verifier logic in some places. At the same time, this doesn't hurt generality of possible iterator implementations. Win-win.
Constructor kfunc is marked with a new KF_ITER_NEW flags, next method is marked with KF_ITER_NEXT (and should also have KF_RET_NULL, of course), while destructor kfunc is marked as KF_ITER_DESTROY.
Additionally, we add a trivial kfunc name validation: it should be a valid non-NULL and non-empty string.
--- include/linux/bpf_verifier.h | 2 + include/linux/btf.h | 4 ++ kernel/bpf/btf.c | 112 ++++++++++++++++++++++++++++++++++- 3 files changed, 117 insertions(+), 1 deletion(-)
include/linux/bpf_verifier.h +2 -0
@@ -59,6 +59,8 @@ struct bpf_active_lock {u32 id; }; +#define ITER_PREFIX "bpf_iter_" +struct bpf_reg_state {/* Ordering of fields matters. See states_equal() */ enum bpf_reg_type type;
include/linux/btf.h +4 -0
@@ -71,6 +71,10 @@#define KF_SLEEPABLE (1 << 5)/* kfunc may sleep */ #define KF_DESTRUCTIVE (1 << 6)/* kfunc performs destructive actions */ #define KF_RCU (1 << 7)/* kfunc takes either rcu or trusted pointer arguments */ +/* only one of KF_ITER_{NEW,NEXT,DESTROY} could be specified per kfunc */ +#define KF_ITER_NEW (1 << 8)/* kfunc implements BPF iter constructor */ +#define KF_ITER_NEXT (1 << 9)/* kfunc implements BPF iter next method */ +#define KF_ITER_DESTROY (1 << 10)/* kfunc implements BPF iter destructor */ /* * Tag marking a kernel function as a kfunc. This is meant to minimize the
kernel/bpf/btf.c +111 -1
131 lines not on this page · raw message
Signature · 1 line
2.34.1
Andrii Nakryiko
maintainerPATCH v5 3/8 bpf: add support for open-coded iterator loops
In reply to Andrii NakryikoTeach verifier about the concept of the open-coded (or inline) iterators.
This patch adds generic iterator loop verification logic, new STACK_ITER stack slot type to contain iterator state, and necessary kfunc plumbing for iterator's constructor, destructor and next methods. Next patch implements first specific iterator (numbers iterator for implementing for() loop logic). Such split allows to have more focused commits for verifier logic and separate commit that we could point later to demonstrating what does it take to add a new kind of iterator.
Each kind of iterator has its own associated struct bpf_iter_<type>, where <type> denotes a specific type of iterator. struct bpf_iter_<type> state is supposed to live on BPF program stack, so there will be no way to change its size later on without breaking backwards compatibility, so choose wisely! But given this struct is specific to a given <type> of iterator, this allows a lot of flexibility: simple iterators could be fine with just one stack slot (8 bytes), like numbers iterator in the next patch, while some other more complicated iterators might need way more to keep their iterator state. Either way, such design allows to avoid runtime memory allocations, which otherwise would be necessary if we fixed on-the-stack size and it turned out to be too small for a given iterator implementation.
The way BPF verifier logic is implemented, there are no artificial restrictions on a number of active iterators, it should work correctly using multiple active iterators at the same time. This also means you can have multiple nested iteration loops. struct bpf_iter_<type> reference can be safely passed to subprograms as well.
General flow is easiest to demonstrate with a simple example using number iterator implemented in next patch. Here's the simplest possible loop:
struct bpf_iter_num it;
int *v;
bpf_iter_num_new(&it, 2, 5);
while ((v = bpf_iter_num_next(&it))) {
bpf_printk("X = %d", *v);
}
bpf_iter_num_destroy(&it);Above snippet should output "X = 2", "X = 3", "X = 4". Note that 5 is exclusive and is not returned. This matches similar APIs (e.g., slices in Go or Rust) that implement a range of elements, where end index is non-inclusive.
In the above example, we see a trio of function:
- constructor, bpf_iter_num_new(), which initializes iterator state (struct bpf_iter_num it) on the stack. If any of the input arguments are invalid, constructor should make sure to still initialize it such that subsequent bpf_iter_num_next() calls will return NULL. I.e., on error, return error and construct empty iterator.
- next method, bpf_iter_num_next(), which accepts pointer to iterator state and produces an element. Next method should always return a pointer. The contract between BPF verifier is that next method will always eventually return NULL when elements are exhausted. Once NULL is returned, subsequent next calls should keep returning NULL. In the case of numbers iterator, bpf_iter_num_next() returns a pointer to an int (storage for this integer is inside the iterator state itself), which can be dereferenced after corresponding NULL check.
- once done with the iterator, it's mandated that user cleans up its state with the call to destructor, bpf_iter_num_destroy() in this case. Destructor frees up any resources and marks stack space used by struct bpf_iter_num as usable for something else.
Any other iterator implementation will have to implement at least these three methods. It is enforced that for any given type of iterator only applicable constructor/destructor/next are callable. I.e., verifier ensures you can't pass number iterator state into, say, cgroup iterator's next method.
It is important to keep the naming pattern consistent to be able to create generic macros to help with BPF iter usability. E.g., one of the follow up patches adds generic bpf_for_each() macro to bpf_misc.h in selftests, which allows to utilize iterator "trio" nicely without having to code the above somewhat tedious loop explicitly every time. This is enforced at kfunc registration point by one of the previous patches in this series.
At the implementation level, iterator state tracking for verification purposes is very similar to dynptr. We add STACK_ITER stack slot type, reserve necessary number of slots, depending on sizeof(struct bpf_iter_<type>), and keep track of necessary extra state in the "main" slot, which is marked with non-zero ref_obj_id. Other slots are also marked as STACK_ITER, but have zero ref_obj_id. This is simpler than having a separate "is_first_slot" flag.
Another big distinction is that STACK_ITER is *always refcounted*, which simplifies implementation without sacrificing usability. So no need for extra "iter_id", no need to anticipate reuse of STACK_ITER slots for new constructors, etc. Keeping it simple here.
As far as the verification logic goes, there are two extensive comments:
in process_iter_next_call() and iter_active_depths_differ() explaining some important and sometimes subtle aspects. Please refer to them for details.
But from 10,000-foot point of view, next methods are the points of forking a verification state, which are conceptually similar to what verifier is doing when validating conditional jump. We branch out at a call bpf_iter_<type>_next instruction and simulate two outcomes:
NULL (iteration is done) and non-NULL (new element is returned). NULL is simulated first and is supposed to reach exit without looping. After that non-NULL case is validated and it either reaches exit (for trivial examples with no real loop), or reaches another call bpf_iter_<type>_next instruction with the state equivalent to already (partially) validated one. State equivalency at that point means we technically are going to be looping forever without "breaking out" out of established "state envelope" (i.e., subsequent iterations don't add any new knowledge or constraints to the verifier state, so running 1, 2, 10, or a million of them doesn't matter). But taking into account the contract stating that iterator next method *has to* return NULL eventually, we can conclude that loop body is safe and will eventually terminate. Given we validated logic outside of the loop (NULL case), and concluded that loop body is safe (though potentially looping many times), verifier can claim safety of the overall program logic.
The rest of the patch is necessary plumbing for state tracking, marking, validation, and necessary further kfunc plumbing to allow implementing iterator constructor, destructor, and next methods.
--- include/linux/bpf_verifier.h | 23 ++ kernel/bpf/verifier.c | 595 ++++++++++++++++++++++++++++++++++- 2 files changed, 610 insertions(+), 8 deletions(-)
include/linux/bpf_verifier.h +23 -0
@@ -61,6 +61,12 @@ struct bpf_active_lock {#define ITER_PREFIX "bpf_iter_" +enum bpf_iter_state { +BPF_ITER_STATE_INVALID ,/* for non-first slot */ +BPF_ITER_STATE_ACTIVE , +BPF_ITER_STATE_DRAINED , +}; +struct bpf_reg_state {/* Ordering of fields matters. See states_equal() */ enum bpf_reg_type type;
@@ -105,6 +111,18 @@ struct bpf_reg_state {bool first_slot; } dynptr; +/* For bpf_iter stack slots */ +struct { +/* BTF container and BTF type ID describing +* struct bpf_iter_<type> of an iterator state +*/ +struct btf *btf; +u32 btf_id; +/* packing following two fields to fit iter state into 16 bytes */ +enum bpf_iter_state state:2 ; +int depth:30 ; + } iter; +/* Max size from any of the above. */ struct {unsigned long raw1;
@@ -143,6 +161,8 @@ struct bpf_reg_state {* same reference to the socket, to determine proper reference freeing. * For stack slots that are dynptrs, this is used to track references to * the dynptr to determine proper reference freeing. +* Similarly to dynptrs, we use ID to track "belonging" of a reference +* to a specific instance of bpf_iter. */ u32 id;/* PTR_TO_SOCKET and PTR_TO_TCP_SOCK could be a ptr returned
@@ -213,9 +233,11 @@ enum bpf_stack_slot_type {* is stored in bpf_stack_state->spilled_ptr.dynptr.type */ STACK_DYNPTR , + STACK_ITER, };#define BPF_REG_SIZE 8/* size of eBPF register in bytes */ +#define BPF_DYNPTR_SIZE sizeof(struct bpf_dynptr_kern)#define BPF_DYNPTR_NR_SLOTS (BPF_DYNPTR_SIZE / BPF_REG_SIZE)
@@ -450,6 +472,7 @@ struct bpf_insn_aux_data {bool sanitize_stack_spill;/* subject to Spectre v4 sanitation */ bool zext_dst;/* this insn zero extends dst reg */ bool storage_get_func_atomic;/* bpf_*_storage_get() with atomic memory alloc */ +bool is_iter_next;/* bpf_iter_<type>_next() kfunc call */ u8 alu_state;/* used in combination with alu_limit */ /* below fields are initialized once */
kernel/bpf/verifier.c +587 -8
733 lines not on this page · raw message
Signature · 1 line
2.34.1
Andrii Nakryiko
maintainerPATCH v5 4/8 bpf: implement numbers iterator
In reply to Andrii NakryikoImplement the first open-coded iterator type over a range of integers.
It's public API consists of:
- bpf_iter_num_new() constructor, which accepts [start, end) range (that is, start is inclusive, end is exclusive).
- bpf_iter_num_next() which will keep returning read-only pointer to int until the range is exhausted, at which point NULL will be returned. If bpf_iter_num_next() is kept calling after this, NULL will be persistently returned.
- bpf_iter_num_destroy() destructor, which needs to be called at some point to clean up iterator state. BPF verifier enforces that iterator destructor is called at some point before BPF program exits.
Note that start = end = X is a valid combination to setup an empty iterator. bpf_iter_num_new() will return 0 (success) for any such combination.
If bpf_iter_num_new() detects invalid combination of input arguments, it returns error, resets iterator state to, effectively, empty iterator, so any subsequent call to bpf_iter_num_next() will keep returning NULL.
BPF verifier has no knowledge that returned integers are in the [start, end) value range, as both start and end are not statically known and enforced: they are runtime values.
While the implementation is pretty trivial, some care needs to be taken to avoid overflows and underflows. Subsequent selftests will validate correctness of [start, end) semantics, especially around extremes (INT_MIN and INT_MAX).
Similarly to bpf_loop(), we enforce that no more than BPF_MAX_LOOPS can be specified.
bpf_iter_num_{new,next,destroy}() is a logical evolution from bounded BPF loops and bpf_loop() helper and is the basis for implementing ergonomic BPF loops with no statically known or verified bounds. Subsequent patches implement bpf_for() macro, demonstrating how this can be wrapped into something that works and feels like a normal for() loop in C language.
--- include/linux/bpf.h | 8 +++- include/uapi/linux/bpf.h | 8 ++++ kernel/bpf/bpf_iter.c | 70 ++++++++++++++++++++++++++++++++++ kernel/bpf/helpers.c | 3 ++ tools/include/uapi/linux/bpf.h | 8 ++++ 5 files changed, 95 insertions(+), 2 deletions(-)
include/linux/bpf.h +6 -2
@@ -1617,8 +1617,12 @@ struct bpf_array {#define BPF_COMPLEXITY_LIMIT_INSNS 1000000/* yes. 1M insns */ #define MAX_TAIL_CALL_CNT 33 -/* Maximum number of loops for bpf_loop */ -#define BPF_MAX_LOOPS BIT(23) +/* Maximum number of loops for bpf_loop and bpf_iter_num. +* It's enum to expose it (and thus make it discoverable) through BTF. +*/ +enum { +BPF_MAX_LOOPS =8 *1024 *1024 , +};#define BPF_F_ACCESS_MASK (BPF_F_RDONLY | \ BPF_F_RDONLY_PROG | \
include/uapi/linux/bpf.h +8 -0
@@ -7112,4 +7112,12 @@ enum { BPF_F_TIMER_ABS = (1ULL << 0), }; +/* BPF numbers iterator state */ +struct bpf_iter_num { +/* opaque iterator state; having __u64 here allows to preserve correct +* alignment requirements in vmlinux.h, generated from BTF +*/ +__u64 __opaque[1 ]; +} __attribute__((aligned (8 ))); +#endif /* _UAPI__LINUX_BPF_H__ */
kernel/bpf/bpf_iter.c +70 -0
73 lines not on this page · raw message
kernel/bpf/helpers.c +3 -0
@@ -2411,6 +2411,9 @@ BTF_ID_FLAGS(func, bpf_rcu_read_lock) BTF_ID_FLAGS(func, bpf_rcu_read_unlock) BTF_ID_FLAGS(func, bpf_dynptr_slice, KF_RET_NULL) BTF_ID_FLAGS(func, bpf_dynptr_slice_rdwr, KF_RET_NULL) +BTF_ID_FLAGS(func, bpf_iter_num_new, KF_ITER_NEW) +BTF_ID_FLAGS(func, bpf_iter_num_next, KF_ITER_NEXT | KF_RET_NULL) +BTF_ID_FLAGS(func, bpf_iter_num_destroy, KF_ITER_DESTROY)BTF_SET8_END (common_btf_ids) static const struct btf_kfunc_id_set common_kfunc_set = {
tools/include/uapi/linux/bpf.h +8 -0
@@ -7112,4 +7112,12 @@ enum { BPF_F_TIMER_ABS = (1ULL << 0), }; +/* BPF numbers iterator state */ +struct bpf_iter_num { +/* opaque iterator state; having __u64 here allows to preserve correct +* alignment requirements in vmlinux.h, generated from BTF +*/ +__u64 __opaque[1 ]; +} __attribute__((aligned (8 ))); +#endif /* _UAPI__LINUX_BPF_H__ */
Signature · 1 line
2.34.1
Andrii Nakryiko
maintainerPATCH v5 5/8 selftests/bpf: add bpf_for_each(), bpf_for(), and bpf_repeat() macros
In reply to Andrii NakryikoAdd bpf_for_each(), bpf_for(), and bpf_repeat() macros that make writing open-coded iterator-based loops much more convenient and natural. These macros utilize cleanup attribute to ensure proper destruction of the iterator and thanks to that manage to provide the ergonomics that is very close to C language's for() construct. Typical loop would look like:
int i;
int arr[N];
bpf_for(i, 0, N) {
/* verifier will know that i >= 0 && i < N, so could be used to
* directly access array elements with no extra checks
*/
arr[i] = i;
}bpf_repeat() is very similar, but it doesn't expose iteration number and is meant as a simple "repeat action N times" loop:
bpf_repeat(N) { /* whatever, N times */ }
Note that break and continue statements inside the {} block work as expected.
bpf_for_each() is a generalization over any kind of BPF open-coded iterator allowing to use for-each-like approach instead of calling low-level bpf_iter_<type>_{new,next,destroy}() APIs explicitly. E.g.:
struct cgroup *cg;
bpf_for_each(cgroup, cg, some, input, args) {
/* do something with each cg */
}would call (not-yet-implemented) bpf_iter_cgroup_{new,next,destroy}() functions to form a loop over cgroups, where some, input, args are passed verbatim into constructor as
bpf_iter_cgroup_new(&it, some, input, args).
As a first demonstration, add pyperf variant based on the bpf_for() loop.
Also clean up a few tests that either included bpf_misc.h header unnecessarily from the user-space, which is unsupported, or included it before any common types are defined (and thus leading to unnecessary compilation warnings, potentially).
--- .../bpf/prog_tests/bpf_verif_scale.c | 6 ++ .../bpf/prog_tests/uprobe_autoattach.c | 1 - tools/testing/selftests/bpf/progs/bpf_misc.h | 99 +++++++++++++++++++ tools/testing/selftests/bpf/progs/lsm.c | 4 +- tools/testing/selftests/bpf/progs/pyperf.h | 14 ++- .../selftests/bpf/progs/pyperf600_iter.c | 7 ++ .../selftests/bpf/progs/pyperf600_nounroll.c | 3 - 7 files changed, 124 insertions(+), 10 deletions(-) create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_iter.c
tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c +6 -0
@@ -144,6 +144,12 @@ void test_verif_scale_pyperf600_nounroll()scale_test ("pyperf600_nounroll.bpf.o" ,BPF_PROG_TYPE_RAW_TRACEPOINT , false); } +void test_verif_scale_pyperf600_iter () +{ +/* open-coded BPF iterator version */ +scale_test ("pyperf600_iter.bpf.o" ,BPF_PROG_TYPE_RAW_TRACEPOINT , false); +} +void test_verif_scale_loop1 () {scale_test ("loop1.bpf.o" ,BPF_PROG_TYPE_RAW_TRACEPOINT , false);
tools/testing/selftests/bpf/prog_tests/uprobe_autoattach.c +0 -1
@@ -3,7 +3,6 @@#include <test_progs.h> #include "test_uprobe_autoattach.skel.h" -#include "progs/bpf_misc.h" /* uprobe attach point */ static noinline int autoattach_trigger_func(int arg1, int arg2, int arg3,
tools/testing/selftests/bpf/progs/bpf_misc.h +99 -0
104 lines not on this page · raw message
tools/testing/selftests/bpf/progs/lsm.c +2 -2
@@ -4,12 +4,12 @@* Copyright 2020 Google LLC. */ -#include "bpf_misc.h" #include "vmlinux.h" +#include <errno.h> #include <bpf/bpf_core_read.h> #include <bpf/bpf_helpers.h> #include <bpf/bpf_tracing.h> -#include <errno.h> +#include "bpf_misc.h" struct { __uint(type, BPF_MAP_TYPE_ARRAY);
tools/testing/selftests/bpf/progs/pyperf.h +10 -4
@@ -7,6 +7,7 @@#include <stdbool.h> #include <linux/bpf.h> #include <bpf/bpf_helpers.h> +#include "bpf_misc.h" #define FUNCTION_NAME_LEN 64#define FILE_NAME_LEN 128
@@ -294,17 +295,22 @@ int __on_event(struct bpf_raw_tracepoint_args *ctx) if (ctx.done) return 0; #else -#ifdef NO_UNROLL +#if defined(USE_ITER) +/* no for loop, no unrolling */ +#elif defined(NO_UNROLL) #pragma clang loop unroll(disable) -#else -#ifdef UNROLL_COUNT +#elif defined(UNROLL_COUNT) #pragma clang loop unroll_count(UNROLL_COUNT) #else #pragma clang loop unroll(full) -#endif #endif /* NO_UNROLL */ /* Unwind python stack */ +#ifdef USE_ITER + int i; + bpf_for(i, 0, STACK_MAX_LEN) { +#else /* !USE_ITER */ for (int i = 0; i < STACK_MAX_LEN; ++i) { +#endif if (frame_ptr && get_frame_data(frame_ptr, pidData, &frame, &sym)) { int32_t new_symbol_id = *symbol_counter * 64 + cur_cpu; int32_t *symbol_id = bpf_map_lookup_elem(&symbolmap, &sym);
tools/testing/selftests/bpf/progs/pyperf600_iter.c new file +7 -0
@@ -0,0 +1,7 @@ +// SPDX-License-Identifier: GPL-2.0 +// Copyright (c) 2023 Meta Platforms, Inc. and affiliates. +#define STACK_MAX_LEN 600 +#define SUBPROGS +#define NO_UNROLL +#define USE_ITER +#include "pyperf.h"
tools/testing/selftests/bpf/progs/pyperf600_nounroll.c +0 -3
@@ -2,7 +2,4 @@// Copyright (c) 2019 Facebook #define STACK_MAX_LEN 600#define NO_UNROLL -/* clang will not unroll at all. -* Total program size is around 2k insns -*/ #include "pyperf.h"
Signature · 1 line
2.34.1
Andrii Nakryiko
maintainerPATCH v5 6/8 selftests/bpf: add iterators tests
In reply to Andrii NakryikoAdd various tests for open-coded iterators. Some of them excercise various possible coding patterns in C, some go down to low-level assembly for more control over various conditions, especially invalid ones.
We also make use of bpf_for(), bpf_for_each(), bpf_repeat() macros in some of these tests.
--- .../testing/selftests/bpf/prog_tests/iters.c | 15 + tools/testing/selftests/bpf/progs/bpf_misc.h | 1 + tools/testing/selftests/bpf/progs/iters.c | 720 ++++++++++++++++++ .../selftests/bpf/progs/iters_looping.c | 163 ++++ .../selftests/bpf/progs/iters_state_safety.c | 426 +++++++++++ 5 files changed, 1325 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/iters.c create mode 100644 tools/testing/selftests/bpf/progs/iters.c create mode 100644 tools/testing/selftests/bpf/progs/iters_looping.c create mode 100644 tools/testing/selftests/bpf/progs/iters_state_safety.c
tools/testing/selftests/bpf/prog_tests/iters.c new file +15 -0
@@ -0,0 +1,15 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2023 Meta Platforms, Inc. and affiliates. */ + +#include <test_progs.h> + +#include "iters.skel.h" +#include "iters_state_safety.skel.h" +#include "iters_looping.skel.h" + +void test_iters (void ) +{ +RUN_TESTS (iters_state_safety); +RUN_TESTS (iters_looping); +RUN_TESTS (iters); +}
tools/testing/selftests/bpf/progs/bpf_misc.h +1 -0
@@ -36,6 +36,7 @@#define __clobber_common "r0", "r1", "r2", "r3", "r4", "r5", "memory"#define __imm (name) [name]"i"(name)#define __imm_addr (name) [name]"i"(&name) +#define __imm_ptr (name) [name]"p"(&name)#if defined(__TARGET_ARCH_x86)#define SYSCALL_WRAPPER 1
tools/testing/selftests/bpf/progs/iters.c new file +720 -0
720 lines not on this page · raw message
tools/testing/selftests/bpf/progs/iters_looping.c new file +163 -0
163 lines not on this page · raw message
tools/testing/selftests/bpf/progs/iters_state_safety.c new file +426 -0
426 lines not on this page · raw message
Signature · 1 line
2.34.1
Andrii Nakryiko
maintainerPATCH v5 7/8 selftests/bpf: add number iterator tests
In reply to Andrii NakryikoAdd number iterator (bpf_iter_num_{new,next,destroy}()) tests, validating the correct handling of various corner and common cases *at runtime*.
--- .../testing/selftests/bpf/prog_tests/iters.c | 49 ++++ tools/testing/selftests/bpf/progs/iters_num.c | 242 ++++++++++++++++++ 2 files changed, 291 insertions(+) create mode 100644 tools/testing/selftests/bpf/progs/iters_num.c
tools/testing/selftests/bpf/prog_tests/iters.c +49 -0
@@ -6,10 +6,59 @@#include "iters.skel.h" #include "iters_state_safety.skel.h" #include "iters_looping.skel.h" +#include "iters_num.skel.h" + +static void subtest_num_iters (void ) +{ +struct iters_num *skel; +int err; + + skel =iters_num__open_and_load (); +if (!ASSERT_OK_PTR (skel,"skel_open_and_load" )) +return ; + + err =iters_num__attach (skel); +if (!ASSERT_OK (err,"skel_attach" )) + goto cleanup; + +usleep (1 ); +iters_num__detach (skel); + +#define VALIDATE_CASE (case_name) \ + ASSERT_EQ(skel->bss->res_##case_name, \ + skel->rodata->exp_##case_name, \ + #case_name) + +VALIDATE_CASE (empty_zero); +VALIDATE_CASE (empty_int_min); +VALIDATE_CASE (empty_int_max); +VALIDATE_CASE (empty_minus_one); + +VALIDATE_CASE (simple_sum); +VALIDATE_CASE (neg_sum); +VALIDATE_CASE (very_neg_sum); +VALIDATE_CASE (neg_pos_sum); + +VALIDATE_CASE (invalid_range); +VALIDATE_CASE (max_range); +VALIDATE_CASE (e2big_range); + +VALIDATE_CASE (succ_elem_cnt); +VALIDATE_CASE (overfetched_elem_cnt); +VALIDATE_CASE (fail_elem_cnt); + +#undef VALIDATE_CASE + +cleanup: +iters_num__destroy (skel); +}void test_iters (void ) {RUN_TESTS (iters_state_safety);RUN_TESTS (iters_looping);RUN_TESTS (iters); + +if (test__start_subtest ("num" )) +subtest_num_iters (); }
tools/testing/selftests/bpf/progs/iters_num.c new file +242 -0
242 lines not on this page · raw message
Signature · 1 line
2.34.1
Andrii Nakryiko
maintainerPATCH v5 8/8 selftests/bpf: implement and test custom testmod_seq iterator
In reply to Andrii NakryikoImplement a trivial iterator returning same specified integer value N times as part of bpf_testmod kernel module. Add selftests to validate everything works end to end.
We also reuse these tests as "verification-only" tests to validate that kernel prints the state of custom kernel module-defined iterator correctly:
fp-16=iter_testmod_seq(ref_id=1,state=drained,depth=0)
"testmod_seq" part is an iterator type, and is coming from module's BTF data dynamically at runtime.
--- tools/testing/selftests/bpf/DENYLIST.s390x | 1 + .../selftests/bpf/bpf_testmod/bpf_testmod.c | 42 +++++++++- .../selftests/bpf/bpf_testmod/bpf_testmod.h | 6 ++ .../testing/selftests/bpf/prog_tests/iters.c | 42 ++++++++++ .../selftests/bpf/progs/iters_testmod_seq.c | 79 +++++++++++++++++++ 5 files changed, 169 insertions(+), 1 deletion(-) create mode 100644 tools/testing/selftests/bpf/progs/iters_testmod_seq.c
tools/testing/selftests/bpf/DENYLIST.s390x +1 -0
@@ -8,6 +8,7 @@ dynptr/test_dynptr_skb_data dynptr/test_skb_readonly fexit_sleep # fexit_skel_load fexit skeleton failed (trampoline) get_stack_raw_tp # user_stack corrupted user stack (no backchain userspace) +iters/testmod_seq* # s390x doesn't support kfuncs in modules yet kprobe_multi_bench_attach # bpf_program__attach_kprobe_multi_opts unexpected error: -95 kprobe_multi_test # relies on fentry ksyms_module # test_ksyms_module__open_and_load unexpected error: -9 (?)
tools/testing/selftests/bpf/bpf_testmod/bpf_testmod.c +41 -1
60 lines not on this page · raw message
tools/testing/selftests/bpf/bpf_testmod/bpf_testmod.h +6 -0
@@ -22,4 +22,10 @@ struct bpf_testmod_test_writable_ctx { int val; }; +/* BPF iter that returns *value* *n* times in a row */ +struct bpf_iter_testmod_seq { +s64 value; +int cnt; +}; +#endif /* _BPF_TESTMOD_H */
tools/testing/selftests/bpf/prog_tests/iters.c +42 -0
60 lines not on this page · raw message
tools/testing/selftests/bpf/progs/iters_testmod_seq.c new file +79 -0
79 lines not on this page · raw message
Signature · 1 line
2.34.1
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Hello:
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Quoted 12 lines · On Wed, 8 Mar 2023 10:41:13 -0800 you wrote:
Add support for open-coded (aka inline) iterators in BPF world. This is a next evolution of gradually allowing more powerful and less restrictive looping and iteration capabilities to BPF programs.
We set up a framework for implementing all kinds of iterators (e.g., cgroup, task, file, etc, iterators), but this patch set only implements numbers iterator, which is used to implement ergonomic
bpf_for()for-like construct (see patches #4-#5). We also addbpf_for_each(), which is a generic foreach-like construct that will work with any kind of open-coded iterator implementation, as long as we stick with bpf_iter_<type>_{new,next,destroy}() naming pattern (which we now enforce on the kernel side).
Quoted 1 line
[...]
Here is the summary with links:
- [v5,bpf-next,1/8] bpf: factor out fetching basic kfunc metadata
https://git.kernel.org/bpf/bpf-next/c/07236eab7a31 - [v5,bpf-next,2/8] bpf: add iterator kfuncs registration and validation logic https://git.kernel.org/bpf/bpf-next/c/215bf4962f6c - [v5,bpf-next,3/8] bpf: add support for open-coded iterator loops https://git.kernel.org/bpf/bpf-next/c/06accc8779c1 - [v5,bpf-next,4/8] bpf: implement numbers iterator https://git.kernel.org/bpf/bpf-next/c/6018e1f407cc - [v5,bpf-next,5/8] selftests/bpf: add bpf_for_each(), bpf_for(), and bpf_repeat() macros https://git.kernel.org/bpf/bpf-next/c/8c2b5e90505e - [v5,bpf-next,6/8] selftests/bpf: add iterators tests https://git.kernel.org/bpf/bpf-next/c/57400dcce6c2 - [v5,bpf-next,7/8] selftests/bpf: add number iterator tests https://git.kernel.org/bpf/bpf-next/c/f59b14609265 - [v5,bpf-next,8/8] selftests/bpf: implement and test custom testmod_seq iterator https://git.kernel.org/bpf/bpf-next/c/7e86a8c4ac8d
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html