BPF open-coded iterators
Subsystems (5)
Andrii Nakryiko
maintainercover 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 patch #15). 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.
Patches #1 through #12 are various preparatory patches, first eitht of them are from preliminaries patch set ([0]) which haven't landed yet, so I just merged them together to let CI do end-to-end testing of everything properly. Few new patches further adds some necessary functionality in verifier (like fixed-size read-only memory access for int *-returning kfuncs).
The meat of verifier-side logic is in lucky patch #13. Patch #14 implements numbers iterator. I kept them separate to have clean reference for how to integrate new iterator types. And it makes verifier core logic changes abstracted from any particularities of numbers iterator. Patch #15 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 #16 is verification tests, based on numbers iterator (as the only available right now). Patch #17 actually tests runtime behavior of numbers iterator.
Most of the relevant details are in corresponding commit messages or code comments.
[0] https://patchwork.kernel.org/project/netdevbpf/list/?series=725996&state=*
Andrii Nakryiko (17):
bpf: improve stack slot state printing
bpf: improve regsafe() checks for PTR_TO_{MEM,BUF,TP_BUFFER} selftests/bpf: enhance align selftest's expected log matching
bpf: honor env->test_state_freq flag in is_state_visited() selftests/bpf: adjust log_fixup's buffer size for proper truncation
bpf: clean up visit_insn()'s instruction processing
bpf: fix visit_insn()'s detection of BPF_FUNC_timer_set_callback
helper
bpf: ensure that r0 is marked scratched after any function call
bpf: move kfunc_call_arg_meta higher in the file
bpf: mark PTR_TO_MEM as non-null register type
bpf: generalize dynptr_get_spi to be usable for iters
bpf: add support for fixed-size memory pointer returns for kfuncs
bpf: add support for open-coded iterator loops
bpf: implement number iterator
selftests/bpf: add bpf_for_each(), bpf_for(), and bpf_repeat() macros selftests/bpf: add iterators tests
selftests/bpf: add number iterator tests
include/linux/bpf.h | 19 +- include/linux/bpf_verifier.h | 22 +- include/uapi/linux/bpf.h | 6 + kernel/bpf/bpf_iter.c | 71 ++ kernel/bpf/helpers.c | 3 + kernel/bpf/verifier.c | 851 ++++++++++++++++-- tools/include/uapi/linux/bpf.h | 6 + .../testing/selftests/bpf/prog_tests/align.c | 18 +- .../bpf/prog_tests/bpf_verif_scale.c | 6 + .../testing/selftests/bpf/prog_tests/iters.c | 62 ++ .../selftests/bpf/prog_tests/log_fixup.c | 2 +- .../bpf/prog_tests/uprobe_autoattach.c | 1 - tools/testing/selftests/bpf/progs/bpf_misc.h | 77 ++ 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 | 455 ++++++++++ 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 - 21 files changed, 2641 insertions(+), 111 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/pyperf600_iter.c
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerPATCH 1/17 bpf: improve stack slot state printing
Improve stack slot state printing to provide more useful and relevant information, especially for dynptrs. While previously we'd see something like:
8: (85) call bpf_ringbuf_reserve_dynptr#198 ; R0_w=scalar() fp-8_w=dddddddd fp-16_w=dddddddd refs=2
Now we'll see way more useful:
8: (85) call bpf_ringbuf_reserve_dynptr#198 ; R0_w=scalar() fp-16_w=dynptr_ringbuf(ref_id=2) refs=2
I experimented with printing the range of slots taken by dynptr, something like:
fp-16..8_w=dynptr_ringbuf(ref_id=2)
But it felt very awkward and pretty useless. So we print the lowest address (most negative offset) only.
The general structure of this code is now also set up for easier extension and will accommodate ITER slots naturally.
--- kernel/bpf/verifier.c | 75 ++++++++++++++++++++++++++++--------------- 1 file changed, 49 insertions(+), 26 deletions(-)
kernel/bpf/verifier.c +49 -26
@@ -705,6 +705,25 @@ static const char *kernel_type_name(const struct btf* btf, u32 id)return btf_name_by_offset (btf,btf_type_by_id (btf, id)->name_off); } +static const char *dynptr_type_str (enum bpf_dynptr_type type) +{ +switch (type) { +case BPF_DYNPTR_TYPE_LOCAL : +return "local" ; +case BPF_DYNPTR_TYPE_RINGBUF : +return "ringbuf" ; +case BPF_DYNPTR_TYPE_SKB : +return "skb" ; +case BPF_DYNPTR_TYPE_XDP : +return "xdp" ; +case BPF_DYNPTR_TYPE_INVALID : +return "<invalid>" ; +default : +WARN_ONCE (1 ,"unknown dynptr type %d\n" , type); +return "<unknown>" ; + } +} +static void mark_reg_scratched (struct bpf_verifier_env *env,u32 regno) { env->scratched_regs |=1U << regno;
@@ -1176,26 +1195,49 @@ static void print_verifier_state(struct bpf_verifier_env *env,for (j =0 ; j <BPF_REG_SIZE ; j++) {if (state->stack[i].slot_type[j] !=STACK_INVALID ) valid = true; - types_buf[j] = slot_type_char[ - state->stack[i].slot_type[j]]; + types_buf[j] = slot_type_char[state->stack[i].slot_type[j]]; } types_buf[BPF_REG_SIZE ] =0 ;if (!valid)continue ;if (!print_all && !stack_slot_scratched (env, i))continue ; -verbose (env," fp%d" , (-i -1 ) *BPF_REG_SIZE ); -print_liveness (env, state->stack[i].spilled_ptr.live); -if (is_spilled_reg (&state->stack[i])) { +switch (state->stack[i].slot_type[BPF_REG_SIZE -1 ]) { +case STACK_SPILL : reg = &state->stack[i].spilled_ptr; t = reg->type; + +verbose (env," fp%d" , (-i -1 ) *BPF_REG_SIZE ); +print_liveness (env, reg->live);verbose (env,"=%s" , t ==SCALAR_VALUE ?"" :reg_type_str (env, t));if (t ==SCALAR_VALUE && reg->precise)verbose (env,"P" );if (t ==SCALAR_VALUE &&tnum_is_const (reg->var_off))verbose (env,"%lld" , reg->var_off.value + reg->off); - }else { +break ; +case STACK_DYNPTR : + i +=BPF_DYNPTR_NR_SLOTS -1 ; + reg = &state->stack[i].spilled_ptr; + +verbose (env," fp%d" , (-i -1 ) *BPF_REG_SIZE ); +print_liveness (env, reg->live); +verbose (env,"=dynptr_%s" ,dynptr_type_str (reg->dynptr.type)); +if (reg->ref_obj_id) +verbose (env,"(ref_id=%d)" , reg->ref_obj_id); +break ; +case STACK_MISC : +case STACK_ZERO : +default : + reg = &state->stack[i].spilled_ptr; + +for (j =0 ; j <BPF_REG_SIZE ; j++) + types_buf[j] = slot_type_char[state->stack[i].slot_type[j]]; + types_buf[BPF_REG_SIZE ] =0 ; + +verbose (env," fp%d" , (-i -1 ) *BPF_REG_SIZE ); +print_liveness (env, reg->live);verbose (env,"=%s" , types_buf); +break ; } }if (state->acquired_refs && state->refs[0 ].id) {
@@ -6312,28 +6354,9 @@ static int process_dynptr_func(struct bpf_verifier_env *env, int regno, int insn/* Fold modifiers (in this case, MEM_RDONLY) when checking expected type */ if (!is_dynptr_type_expected (env, reg, arg_type & ~MEM_RDONLY )) { -const char *err_extra ="" ; - -switch (arg_type &DYNPTR_TYPE_FLAG_MASK ) { -case DYNPTR_TYPE_LOCAL : - err_extra ="local" ; -break ; -case DYNPTR_TYPE_RINGBUF : - err_extra ="ringbuf" ; -break ; -case DYNPTR_TYPE_SKB : - err_extra ="skb " ; -break ; -case DYNPTR_TYPE_XDP : - err_extra ="xdp " ; -break ; -default : - err_extra ="<unknown>" ; -break ; - }verbose (env,"Expected a dynptr of type %s as arg #%d\n" , - err_extra, regno); +dynptr_type_str (arg_to_dynptr_type (arg_type)), regno);return -EINVAL ; }
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerPATCH 2/17 bpf: improve regsafe() checks for PTR_TO_{MEM,BUF,TP_BUFFER}
In reply to Andrii NakryikoTeach regsafe() logic to handle PTR_TO_MEM, PTR_TO_BUF, and PTR_TO_TP_BUFFER similarly to PTR_TO_MAP_{KEY,VALUE}. That is, instead of exact match for var_off and range, use tnum_in() and range_within() checks, allowing more general verified state to subsume more specific current state. This allows to match wider range of valid and safe states, speeding up verification and detecting wider range of equivalent states for upcoming open-coded iteration looping logic.
--- kernel/bpf/verifier.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-)
kernel/bpf/verifier.c +5 -1
@@ -14114,13 +14114,17 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,tnum_in (rold->var_off, rcur->var_off);case PTR_TO_MAP_KEY :case PTR_TO_MAP_VALUE : +case PTR_TO_MEM : +case PTR_TO_BUF : +case PTR_TO_TP_BUFFER :/* If the new min/max/var_off satisfy the old ones and * everything else matches, we are OK. */ return memcmp (rold, rcur, offsetof(struct bpf_reg_state , var_off)) ==0 &&range_within (rold, rcur) &&tnum_in (rold->var_off, rcur->var_off) && -check_ids (rold->id, rcur->id, idmap); +check_ids (rold->id, rcur->id, idmap) && +check_ids (rold->ref_obj_id, rcur->ref_obj_id, idmap);case PTR_TO_PACKET_META :case PTR_TO_PACKET :/* We must have at least as much range as the old ptr
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerPATCH 3/17 selftests/bpf: enhance align selftest's expected log matching
In reply to Andrii NakryikoAllow to search for expected register state in all the verifier log output that's related to specified instruction number.
See added comment for an example of possible situation that is happening due to a simple enhancement done in the next patch, which fixes handling of env->test_state_freq flag in state checkpointing logic.
--- tools/testing/selftests/bpf/prog_tests/align.c | 18 ++++++++++++------ 1 file changed, 12 insertions(+), 6 deletions(-)
tools/testing/selftests/bpf/prog_tests/align.c +12 -6
@@ -660,16 +660,22 @@ static int do_test_single(struct bpf_align_test *test)* func#0 @0 * 0: R1=ctx(off=0,imm=0) R10=fp0 * 0: (b7) r3 = 2 ; R3_w=2 +* +* Sometimes it's actually two lines below, e.g. when +* searching for "6: R3_w=scalar(umax=255,var_off=(0x0; 0xff))": +* from 4 to 6: R0_w=pkt(off=8,r=8,imm=0) R1=ctx(off=0,imm=0) R2_w=pkt(off=0,r=8,imm=0) R3_w=pkt_end(off=0,imm=0) R10=fp0 +* 6: R0_w=pkt(off=8,r=8,imm=0) R1=ctx(off=0,imm=0) R2_w=pkt(off=0,r=8,imm=0) R3_w=pkt_end(off=0,imm=0) R10=fp0 +* 6: (71) r3 = *(u8 *)(r2 +0) ; R2_w=pkt(off=0,r=8,imm=0) R3_w=scalar(umax=255,var_off=(0x0; 0xff)) */ -if (!strstr (line_ptr, m.match)) { +while (!strstr (line_ptr, m.match)) { cur_line =-1 ; line_ptr =strtok (NULL ,"\n" ); -sscanf (line_ptr,"%u: " , &cur_line); +sscanf (line_ptr ?:"" ,"%u: " , &cur_line); +if (!line_ptr || cur_line != m.line) +break ; } -if (cur_line != m.line || !line_ptr || - !strstr (line_ptr, m.match)) { -printf ("Failed to find match %u: %s\n" , - m.line, m.match); +if (cur_line != m.line || !line_ptr || !strstr (line_ptr, m.match)) { +printf ("Failed to find match %u: %s\n" , m.line, m.match); ret =1 ;printf ("%s" , bpf_vlog);break ;
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerPATCH 4/17 bpf: honor env->test_state_freq flag in is_state_visited()
In reply to Andrii Nakryikoenv->test_state_freq flag can be set by user by passing BPF_F_TEST_STATE_FREQ program flag. This is used in a bunch of selftests to have predictable state checkpoints at every jump and so on.
Currently, bounded loop handling heuristic ignores this flag if number of processed jumps and/or number of processed instructions is below some thresholds, which throws off that reliable state checkpointing.
Honor this flag in all circumstances by disabling heuristic if env->test_state_freq is set.
--- kernel/bpf/verifier.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)
kernel/bpf/verifier.c +2 -1
@@ -14556,7 +14556,8 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)* This threshold shouldn't be too high either, since states * at the end of the loop are likely to be useful in pruning. */ -if (env->jmps_processed - env->prev_jmps_processed <20 && +if (!env->test_state_freq && + env->jmps_processed - env->prev_jmps_processed <20 && env->insn_processed - env->prev_insn_processed <100 ) add_new_state = false; goto miss;
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerPATCH 5/17 selftests/bpf: adjust log_fixup's buffer size for proper truncation
In reply to Andrii NakryikoAdjust log_fixup's expected buffer length to fix the test. It's pretty finicky in its length expectation, but it doesn't break often. So just adjust the length to work on current kernel and with follow up iterator changes as well.
--- tools/testing/selftests/bpf/prog_tests/log_fixup.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
tools/testing/selftests/bpf/prog_tests/log_fixup.c +1 -1
@@ -141,7 +141,7 @@ void test_log_fixup(void)if (test__start_subtest ("bad_core_relo_trunc_partial" ))bad_core_relo (300 ,TRUNC_PARTIAL /* truncate original log a bit */ );if (test__start_subtest ("bad_core_relo_trunc_full" )) -bad_core_relo (250 ,TRUNC_FULL /* truncate also libbpf's message patch */ ); +bad_core_relo (210 ,TRUNC_FULL /* truncate also libbpf's message patch */ );if (test__start_subtest ("bad_core_relo_subprog" ))bad_core_relo_subprog ();if (test__start_subtest ("missing_map" ))
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerPATCH 6/17 bpf: clean up visit_insn()'s instruction processing
In reply to Andrii NakryikoInstead of referencing processed instruction repeatedly as insns[t] throughout entire visit_insn() function, take a local insn pointer and work with it in a cleaner way.
It makes enhancing this function further a bit easier as well.
--- kernel/bpf/verifier.c | 25 ++++++++++++------------- 1 file changed, 12 insertions(+), 13 deletions(-)
kernel/bpf/verifier.c +12 -13
@@ -13389,44 +13389,43 @@ static int visit_func_call_insn(int t, struct bpf_insn *insns,*/ static int visit_insn (int t,struct bpf_verifier_env *env) { -struct bpf_insn *insns = env->prog->insnsi; +struct bpf_insn *insns = env->prog->insnsi, *insn = &insns[t];int ret; -if (bpf_pseudo_func (insns + t)) +if (bpf_pseudo_func (insn))return visit_func_call_insn (t, insns, env, true);/* All non-branch instructions have a single fall-through edge. */ -if (BPF_CLASS (insns[t].code) !=BPF_JMP && -BPF_CLASS (insns[t].code) !=BPF_JMP32 ) +if (BPF_CLASS (insn->code) !=BPF_JMP && +BPF_CLASS (insn->code) !=BPF_JMP32 )return push_insn (t, t +1 ,FALLTHROUGH , env, false); -switch (BPF_OP (insns[t].code)) { +switch (BPF_OP (insn->code)) {case BPF_EXIT :return DONE_EXPLORING ;case BPF_CALL : -if (insns[t].imm == BPF_FUNC_timer_set_callback) +if (insn->imm == BPF_FUNC_timer_set_callback)/* Mark this call insn as a prune point to trigger * is_state_visited() check before call itself is * processed by __check_func_call(). Otherwise new * async state will be pushed for further exploration. */ mark_prune_point (env, t); -return visit_func_call_insn (t, insns, env, - insns[t].src_reg ==BPF_PSEUDO_CALL ); +return visit_func_call_insn (t, insns, env, insn->src_reg ==BPF_PSEUDO_CALL );case BPF_JA : -if (BPF_SRC (insns[t].code) !=BPF_K ) +if (BPF_SRC (insn->code) !=BPF_K )return -EINVAL ;/* unconditional jump with single edge */ - ret =push_insn (t, t + insns[t].off +1 ,FALLTHROUGH , env, + ret =push_insn (t, t + insn->off +1 ,FALLTHROUGH , env, true);if (ret)return ret; -mark_prune_point (env, t + insns[t].off +1 ); -mark_jmp_point (env, t + insns[t].off +1 ); +mark_prune_point (env, t + insn->off +1 ); +mark_jmp_point (env, t + insn->off +1 );return ret;
@@ -13438,7 +13437,7 @@ static int visit_insn(int t, struct bpf_verifier_env *env)if (ret)return ret; -return push_insn (t, t + insns[t].off +1 ,BRANCH , env, true); +return push_insn (t, t + insn->off +1 ,BRANCH , env, true); } }
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerPATCH 7/17 bpf: fix visit_insn()'s detection of BPF_FUNC_timer_set_callback helper
In reply to Andrii NakryikoIt's not correct to assume that any BPF_CALL instruction is a helper call. Fix visit_insn()'s detection of bpf_timer_set_callback() helper by also checking insn->code == 0. For kfuncs insn->code would be set to BPF_PSEUDO_KFUNC_CALL, and for subprog calls it will be BPF_PSEUDO_CALL.
--- kernel/bpf/verifier.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/bpf/verifier.c +1 -1
@@ -13405,7 +13405,7 @@ static int visit_insn(int t, struct bpf_verifier_env *env)return DONE_EXPLORING ;case BPF_CALL : -if (insn->imm == BPF_FUNC_timer_set_callback) +if (insn->src_reg ==0 && insn->imm == BPF_FUNC_timer_set_callback)/* Mark this call insn as a prune point to trigger * is_state_visited() check before call itself is * processed by __check_func_call(). Otherwise new
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerPATCH 8/17 bpf: ensure that r0 is marked scratched after any function call
In reply to Andrii Nakryikor0 is important (unless called function is void-returning, but that's taken care of by print_verifier_state() anyways) in verifier logs. Currently for helpers we seem to print it in verifier log, but for kfuncs we don't.
Instead of figuring out where in the maze of code we accidentally set r0 as scratched for helpers and why we don't do that for kfuncs, just enforce that after any function call r0 is marked as scratched.
Also, perhaps, we should reconsider "scratched" terminology, as it's mightily confusing. "Touched" would seem more appropriate. But I left that for follow ups for now.
--- kernel/bpf/verifier.c | 2 ++ 1 file changed, 2 insertions(+)
kernel/bpf/verifier.c +2 -0
@@ -15001,6 +15001,8 @@ static int do_check(struct bpf_verifier_env *env) err =check_helper_call (env, insn, &env->insn_idx);if (err)return err; + +mark_reg_scratched (env,BPF_REG_0 ); }else if (opcode ==BPF_JA ) { if (BPF_SRC(insn->code) != BPF_K || insn->imm != 0 ||
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerPATCH 9/17 bpf: move kfunc_call_arg_meta higher in the file
In reply to Andrii NakryikoMove struct bpf_kfunc_call_arg_meta higher in the file and put it next to struct bpf_call_arg_meta, so it can be used from more functions.
--- kernel/bpf/verifier.c | 70 +++++++++++++++++++++---------------------- 1 file changed, 35 insertions(+), 35 deletions(-)
kernel/bpf/verifier.c +35 -35
@@ -270,6 +270,41 @@ struct bpf_call_arg_meta {struct btf_field *kptr_field; }; +struct bpf_kfunc_call_arg_meta { +/* In parameters */ +struct btf *btf; +u32 func_id; +u32 kfunc_flags; +const struct btf_type *func_proto; +const char *func_name; +/* Out parameters */ +u32 ref_obj_id; +u8 release_regno; +bool r0_rdonly; +u32 ret_btf_id; +u64 r0_size; +u32 subprogno; +struct { +u64 value; +bool found; + } arg_constant; +struct { +struct btf *btf; +u32 btf_id; + } arg_obj_drop; +struct { +struct btf_field *field; + } arg_list_head; +struct { +struct btf_field *field; + } arg_rbtree_root; +struct { +enum bpf_dynptr_type type; +u32 id; + } initialized_dynptr; +u64 mem_size; +}; +struct btf *btf_vmlinux;static DEFINE_MUTEX (bpf_verifier_lock);
@@ -8712,41 +8747,6 @@ static void mark_btf_func_reg_size(struct bpf_verifier_env *env, u32 regno, } } -struct bpf_kfunc_call_arg_meta { -/* In parameters */ -struct btf *btf; -u32 func_id; -u32 kfunc_flags; -const struct btf_type *func_proto; -const char *func_name; -/* Out parameters */ -u32 ref_obj_id; -u8 release_regno; -bool r0_rdonly; -u32 ret_btf_id; -u64 r0_size; -u32 subprogno; -struct { -u64 value; -bool found; - } arg_constant; -struct { -struct btf *btf; -u32 btf_id; - } arg_obj_drop; -struct { -struct btf_field *field; - } arg_list_head; -struct { -struct btf_field *field; - } arg_rbtree_root; -struct { -enum bpf_dynptr_type type; -u32 id; - } initialized_dynptr; -u64 mem_size; -}; -static bool is_kfunc_acquire (struct bpf_kfunc_call_arg_meta *meta) {return meta->kfunc_flags &KF_ACQUIRE ;
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerPATCH 10/17 bpf: mark PTR_TO_MEM as non-null register type
In reply to Andrii NakryikoPTR_TO_MEM register without PTR_MAYBE_NULL is indeed non-null. This is important for BPF verifier to be able to prune guaranteed not to be taken branches. This is always the case with open-coded iterators.
--- kernel/bpf/verifier.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)
kernel/bpf/verifier.c +2 -1
@@ -487,7 +487,8 @@ static bool reg_type_not_null(enum bpf_reg_type type) type ==PTR_TO_TCP_SOCK || type ==PTR_TO_MAP_VALUE || type ==PTR_TO_MAP_KEY || - type ==PTR_TO_SOCK_COMMON ; + type ==PTR_TO_SOCK_COMMON || + type ==PTR_TO_MEM ; }static bool type_is_ptr_alloc_obj (u32 type)
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerPATCH 11/17 bpf: generalize dynptr_get_spi to be usable for iters
In reply to Andrii NakryikoGeneralize the logic of fetching special stack slot object state using spi (stack slot index). This will be used by STACK_ITER logic next.
--- kernel/bpf/verifier.c | 18 ++++++++++++------ 1 file changed, 12 insertions(+), 6 deletions(-)
kernel/bpf/verifier.c +12 -6
@@ -710,32 +710,38 @@ static bool is_spi_bounds_valid(struct bpf_func_state *state, int spi, int nr_slreturn spi - nr_slots +1 >=0 && spi < allocated_slots; } -static int dynptr_get_spi (struct bpf_verifier_env *env,struct bpf_reg_state *reg) +static int stack_slot_obj_get_spi (struct bpf_verifier_env *env,struct bpf_reg_state *reg, +const char *obj_kind,int nr_slots) {int off, spi;if (!tnum_is_const (reg->var_off)) { -verbose (env,"dynptr has to be at a constant offset\n" ); +verbose (env,"%s has to be at a constant offset\n" , obj_kind);return -EINVAL ; } off = reg->off + reg->var_off.value;if (off %BPF_REG_SIZE ) { -verbose (env,"cannot pass in dynptr at an offset=%d\n" , off); +verbose (env,"cannot pass in %s at an offset=%d\n" , obj_kind, off);return -EINVAL ; } spi =__get_spi (off); -if (spi <1 ) { -verbose (env,"cannot pass in dynptr at an offset=%d\n" , off); +if (spi +1 < nr_slots) { +verbose (env,"cannot pass in %s at an offset=%d\n" , obj_kind, off);return -EINVAL ; } -if (!is_spi_bounds_valid (func (env, reg), spi,BPF_DYNPTR_NR_SLOTS )) +if (!is_spi_bounds_valid (func (env, reg), spi, nr_slots))return -ERANGE ;return spi; } +static int dynptr_get_spi (struct bpf_verifier_env *env,struct bpf_reg_state *reg) +{ +return stack_slot_obj_get_spi (env, reg,"dynptr" ,BPF_DYNPTR_NR_SLOTS ); +} +static const char *kernel_type_name (const struct btf * btf,u32 id) {return btf_name_by_offset (btf,btf_type_by_id (btf, id)->name_off);
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerPATCH 12/17 bpf: add support for fixed-size memory pointer returns for kfuncs
In reply to Andrii NakryikoSupport direct fixed-size (and for now, read-only) memory access when kfunc's return type is a pointer to non-struct type. Calculate type size and let BPF program access that many bytes directly. This is crucial for numbers iterator.
--- kernel/bpf/verifier.c | 8 ++++++++ 1 file changed, 8 insertions(+)
kernel/bpf/verifier.c +8 -0
@@ -10241,6 +10241,14 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,return -EFAULT ; } }else if (!__btf_type_is_struct (ptr_type)) { +if (!meta.r0_size) { +__u32 sz; + +if (!IS_ERR (btf_resolve_size (desc_btf, ptr_type, &sz))) { + meta.r0_size = sz; + meta.r0_rdonly = true; + } + }if (!meta.r0_size) { ptr_type_name =btf_name_by_offset (desc_btf, ptr_type->name_off);
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerPATCH 13/17 bpf: add support for open-coded iterator loops
In reply to Andrii NakryikoTeach verifier about the concept of 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 version of iterator (number iterator for implementing for loop). Such split allows to have more focused commits for verifier logic and separate commit that we could point later to what it takes to add new kind of iterator.
First, we add new fixed-size opaque struct bpf_iter (24-byte long) to contain runtime state of any possible iterator. struct bpf_iter state is supposed to be on BPF program's stack, so there will be no way to change its size later on. 24 bytes are chosen as a compromise between using too much stack and providing too little pre-allocated space for future iterator types. Numbers iterator in the next patch needs only 8, and thus fits perfectly and won't require any runtime memory allocation. But if some other iterator implementation would require more than 24 bytes to represent iterator runtime state, we'd have to perform runtime allocation for extra state, which leads to performance hit and general unreliability (especially in restricted environments of NMI or IRQ). 3 words were chosen to at least accommodate 1 pointer to "collection" (e.g., bpf_map), 1 pointer to "current/next element", and still leaving 1 word for extra parameters and flags. As such it should hopefully make a lot of other iterator implementations much simpler and reliable.
The way BPF verifier logic is implemented, there are no artificial restrictions on a number of active iterators, it should work correctly using multiple at the same time. This also means you can have multiple nested iteration loops. struct bpf_iter 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 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.
In the above example, we see a trio of function:
- constructor, bpf_iter_num_new(), which initializes iterator state (struct bpf_iter it) on the stack. If any on 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. One NULL is returned, subsequent next calls should keep returning NULL. In the case of numbers iterator, bpf_iter_num_next() returns a pointer to int (where current integer value itself is stored inside iterator state), which can be dereferenced after according NULL check.
- once done with the iterator, it's mandated that user cleans up its state with destructor, bpf_iter_num_destroy() in this case. Destructor frees up any resources and marks stack space used by struct bpf_iter 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 into, say, cgroup iterator's next method.
It is important to keep naming consistent to be able to create generic helpers/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.
**So it is expected that new iterator implementations will follow bpf_iter_<kind>_{new,next,destroy}() naming.**
At the implementation level, iterator state tracking for verification purposes is very similar to dynptr. We add STACK_ITER stack slot type, reserve 3 slots, keep track of necessary extra state in the "main" slot. Other slots are marked as STACK_ITER, but having invalid iterator type. This seems simpler than having a separate "is_first_slot" flag. We should consider reworking STACK_DYNPTR to follow similar approach.
Another big distinction is that STACK_ITER is *always refcounted*, which simplifies implementation a bit 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 simpler.
As far as verification logic, there are two extensive comments, in process_iter_next_call() and iter_active_depths_differ(), please refer to them for details.
But from 10,000-foot point of view, next methods are the points of forking, which are conceptually similar to what verifier is doing when validating conditional jump. We branch out at call bpf_iter_<type>_next instruction and simulate two situations: NULL (iteration is done) and non-NULL (new element 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. 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 verifier state, so running 1, 2, 10, or a million doesn't matter). But taking into the account the contract that iterator next method *has to* return NULL eventually, we can conclude that loop body is safe. 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 kfunc infrastructure to allow implementing iterator constructor, destructor, and next methods.
--- include/linux/bpf.h | 7 + include/linux/bpf_verifier.h | 22 +- include/uapi/linux/bpf.h | 6 + kernel/bpf/verifier.c | 621 ++++++++++++++++++++++++++++++++- tools/include/uapi/linux/bpf.h | 6 + 5 files changed, 653 insertions(+), 9 deletions(-)
include/linux/bpf.h +7 -0
@@ -620,6 +620,8 @@ enum bpf_type_flag {#define DYNPTR_TYPE_FLAG_MASK (DYNPTR_TYPE_LOCAL | DYNPTR_TYPE_RINGBUF | DYNPTR_TYPE_SKB \ | DYNPTR_TYPE_XDP) +#define ITER_TYPE_FLAG_MASK (0) +/* Max number of base types. */ #define BPF_BASE_TYPE_LIMIT (1UL << BPF_BASE_TYPE_BITS)
@@ -663,6 +665,7 @@ enum bpf_arg_type {ARG_PTR_TO_TIMER ,/* pointer to bpf_timer */ ARG_PTR_TO_KPTR ,/* pointer to referenced kptr */ ARG_PTR_TO_DYNPTR ,/* pointer to bpf_dynptr. See bpf_type_flag for dynptr type */ +ARG_PTR_TO_ITER ,/* pointer to bpf_iter. See bpf_type_flag for iter type */ __BPF_ARG_TYPE_MAX,/* Extended arg_types. */
@@ -1162,6 +1165,10 @@ enum bpf_dynptr_type {int bpf_dynptr_check_size (u32 size);u32 bpf_dynptr_get_size (const struct bpf_dynptr_kern *ptr); +enum bpf_iter_type { +BPF_ITER_TYPE_INVALID , +}; +#ifdef CONFIG_BPF_JIT int bpf_trampoline_link_prog (struct bpf_tramp_link *link,struct bpf_trampoline *tr);int bpf_trampoline_unlink_prog (struct bpf_tramp_link *link,struct bpf_trampoline *tr);
include/linux/bpf_verifier.h +21 -1
@@ -59,6 +59,12 @@ struct bpf_active_lock {u32 id; }; +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;
@@ -103,6 +109,13 @@ struct bpf_reg_state {bool first_slot; } dynptr; +/* For bpf_iter stack slots */ +struct { +enum bpf_iter_type type; +enum bpf_iter_state state; +int depth; + } iter; +/* Max size from any of the above. */ struct {unsigned long raw1;
@@ -141,6 +154,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
@@ -211,11 +226,16 @@ 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) +#define BPF_DYNPTR_NR_SLOTS (BPF_DYNPTR_SIZE / BPF_REG_SIZE) + +#define BPF_ITER_SIZE sizeof(struct bpf_iter) +#define BPF_ITER_NR_SLOTS (BPF_ITER_SIZE / BPF_REG_SIZE)struct bpf_stack_state {struct bpf_reg_state spilled_ptr;
include/uapi/linux/bpf.h +6 -0
@@ -6927,6 +6927,12 @@ struct bpf_dynptr { __u64 :64 ; } __attribute__((aligned(8))); +struct bpf_iter { + __u64 :64; + __u64 :64; + __u64 :64; +} __attribute__((aligned (8 ))); +struct bpf_list_head { __u64 :64; __u64 :64;
kernel/bpf/verifier.c +613 -8
807 lines not on this page · raw message
tools/include/uapi/linux/bpf.h +6 -0
@@ -6927,6 +6927,12 @@ struct bpf_dynptr { __u64 :64 ; } __attribute__((aligned(8))); +struct bpf_iter { + __u64 :64; + __u64 :64; + __u64 :64; +} __attribute__((aligned (8 ))); +struct bpf_list_head { __u64 :64; __u64 :64;
Signature · 1 line
2.30.2
Re: [PATCH bpf-next 13/17] bpf: add support for open-coded iterator loops
Quoted 10 lines · Andrii Nakryiko
Teach verifier about the concept of open-coded (or inline) iterators.
This patch adds generic iterator loop verification logic, new
STACK_ITERstack slot type to contain iterator state, and necessary kfunc plumbing for iterator's constructor, destructor and next "methods". Next patch implements first specific version of iterator (number iterator for implementing for loop). Such split allows to have more focused commits for verifier logic and separate commit that we could point later to what it takes to add new kind of iterator.
Quoted 2 lines
First, we add new fixed-size opaque struct
bpf_iter(24-byte long) to contain runtime state of any possible iterator. structbpf_iterstate is
Looking at the verifier changes it seems that it should be possible to support any sized iterator and we don't have to fit all of them in 24-bytes. The same bpf_iter_<kind>_{new,next,destroy}() naming convention can apply to types and we can have 8-byte struct bpf_iter_num
The bpf_for() macros would work with bpf_iter_<kind> too.
iirc that was your plan earlier (to have different structs).
What prompted you to change that plan?
Quoted 5 lines
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 into, say, cgroup iterator's next method.
is_iter_type_compatible() does that, right?
Quoted 5 lines
kernel/bpf/verifier.c +5
-0+ +static int mark_stack_slots_iter (struct bpf_verifier_env *env,struct bpf_reg_state *reg, +enum bpf_arg_type arg_type,int insn_idx) +{ +struct bpf_func_state *state =func (env, reg);
kernel/bpf/verifier.c static bool is_dynptr_type_expected(struct bpf_verifier_env *env, struct bpf_reg · line 1180
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+enum bpf_iter_type type; +int spi, i, j, id; + + spi =iter_get_spi (env, reg); +if (spi <0 ) +return spi; + + type =arg_to_iter_type (arg_type); +if (type ==BPF_ITER_TYPE_INVALID ) +return -EINVAL ;
Do we need destroy_if_dynptr_stack_slot() equivalent here?
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+ id =acquire_reference_state (env, insn_idx); +if (id <0 ) +return id; + +for (i =0 ; i <BPF_ITER_NR_SLOTS ; i++) { +struct bpf_stack_state *slot = &state->stack[spi - i]; +struct bpf_reg_state *st = &slot->spilled_ptr; + +__mark_reg_known_zero (st); + st->type =PTR_TO_STACK ;/* we don't have dedicated reg type */
kernel/bpf/verifier.c static bool is_dynptr_type_expected(struct bpf_verifier_env *env, struct bpf_reg · line 1201
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+ st->live |=REG_LIVE_WRITTEN ; + st->ref_obj_id = i ==0 ? id :0 ; + st->iter.type = i ==0 ? type :BPF_ITER_TYPE_INVALID ; + st->iter.state =BPF_ITER_STATE_ACTIVE ; + st->iter.depth =0 ; + +for (j =0 ; j <BPF_REG_SIZE ; j++) + slot->slot_type[j] =STACK_ITER ; + +mark_stack_slot_scratched (env, spi - i);
dynptr needs similar mark_stack_slot_scratched() fix, right?
Quoted 4 lines
kernel/bpf/verifier.c +4
-0+ } + +return 0 ; +}
...
kernel/bpf/verifier.c static int check_stack_write_fixed_off(struct bpf_verifier_env *env, · line 3934
Quoted 10 lines
kernel/bpf/verifier.c +2
-2@@ -3691,8 +3928,8 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,/* regular write of data into stack destroys any spilled ptr */ state->stack[spi].spilled_ptr.type =NOT_INIT ; -/* Mark slots as STACK_MISC if they belonged to spilled ptr. */ -if (is_spilled_reg (&state->stack[spi])) +/* Mark slots as STACK_MISC if they belonged to spilled ptr/dynptr/iter. */ +if (is_stack_slot_special (&state->stack[spi]))for (i =0 ; i <BPF_REG_SIZE ; i++)scrub_spilled_slot (&state->stack[spi].slot_type[i]);
It fixes something for dynptr, right?
Quoted 29 lines
kernel/bpf/verifier.c +29
-0+static int process_iter_next_call (struct bpf_verifier_env *env,int insn_idx, +struct bpf_kfunc_call_arg_meta *meta) +{ +struct bpf_verifier_state *cur_st = env->cur_state, *queued_st; +struct bpf_func_state *cur_fr = cur_st->frame[cur_st->curframe], *queued_fr; +struct bpf_reg_state *cur_iter, *queued_iter; +int iter_frameno = meta->iter.frameno; +int iter_spi = meta->iter.spi; + +BTF_TYPE_EMIT (struct bpf_iter ); + + cur_iter = &env->cur_state->frame[iter_frameno]->stack[iter_spi].spilled_ptr; + +if (cur_iter->iter.state !=BPF_ITER_STATE_ACTIVE && + cur_iter->iter.state !=BPF_ITER_STATE_DRAINED ) { +verbose (env,"verifier internal error: unexpected iterator state %d (%s)\n" , + cur_iter->iter.state,iter_state_str (cur_iter->iter.state)); +return -EFAULT ; + } + +if (cur_iter->iter.state ==BPF_ITER_STATE_ACTIVE ) { +/* branch out active iter state */ + queued_st =push_stack (env, insn_idx +1 , insn_idx, false); +if (!queued_st) +return -ENOMEM ; + + queued_iter = &queued_st->frame[iter_frameno]->stack[iter_spi].spilled_ptr; + queued_iter->iter.state =BPF_ITER_STATE_ACTIVE ; + queued_iter->iter.depth++;
kernel/bpf/verifier.c static int process_dynptr_func(struct bpf_verifier_env *env, int regno, int insn · line 6804
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+ + queued_fr = queued_st->frame[queued_st->curframe]; +mark_ptr_not_null_reg (&queued_fr->regs[BPF_REG_0 ]); + } + +/* switch to DRAINED state, but keep the depth unchanged */ +/* mark current iter state as drained and assume returned NULL */ + cur_iter->iter.state =BPF_ITER_STATE_DRAINED ; +__mark_reg_known_zero (&cur_fr->regs[BPF_REG_0 ]); + cur_fr->regs[BPF_REG_0 ].type =SCALAR_VALUE ;
__mark_reg_const_zero() instead?
Quoted 3 lines
kernel/bpf/verifier.c +3
-0+ +return 0 ; +}
...
Quoted 18 lines
kernel/bpf/verifier.c +18
-0+static bool is_iter_next_insn (struct bpf_verifier_env *env,int insn_idx,int *reg_idx) +{ +struct bpf_insn *insn = &env->prog->insnsi[insn_idx]; +const struct btf_param *args; +const struct btf_type *t; +const struct btf *btf; +int nargs, i; + +if (!bpf_pseudo_kfunc_call (insn)) +return false; +if (!is_iter_next_kfunc (insn->imm)) +return false; + + btf =find_kfunc_desc_btf (env, insn->off); +if (IS_ERR (btf)) +return false; + + t =btf_type_by_id (btf, insn->imm);/* FUNC */
kernel/bpf/verifier.c static bool states_maybe_looping(struct bpf_verifier_state *old, · line 14987
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+ t =btf_type_by_id (btf, t->type);/* FUNC_PROTO */ + + args =btf_params (t); + nargs =btf_vlen (t); +for (i =0 ; i < nargs; i++) { +if (is_kfunc_arg_iter (btf, &args[i])) { + *reg_idx =BPF_REG_1 + i; +return true; + } + }
This is some future-proofing ?
The commit log says that all iterators has to in the form:
bpf_iter_<kind>_next(struct bpf_iter* it)
Should we check for one and only arg here instead?
Quoted 32 lines
kernel/bpf/verifier.c +32
-0+ +return false; +} + +/* is_state_visited() handles iter_next() (see process_iter_next_call() for +* terminology) calls specially: as opposed to bounded BPF loops, it *expects* +* state matching, which otherwise looks like an infinite loop. So while +* iter_next() calls are taken care of, we still need to be careful and +* prevent erroneous and too eager declaration of "ininite loop", when +* iterators are involved. +* +* Here's a situation in pseudo-BPF assembly form: +* +* 0: again: ; set up iter_next() call args +* 1: r1 = &it ; <CHECKPOINT HERE> +* 2: call bpf_iter_num_next ; this is iter_next() call +* 3: if r0 == 0 goto done +* 4: ... something useful here ... +* 5: goto again ; another iteration +* 6: done: +* 7: r1 = &it +* 8: call bpf_iter_num_destroy ; clean up iter state +* 9: exit +* +* This is a typical loop. Let's assume that we have a prune point at 1:, +* before we get to `call bpf_iter_num_next` (e.g., because of that `goto +* again`, assuming other heuristics don't get in a way). +* +* When we first time come to 1:, let's say we have some state X. We proceed +* to 2:, fork states, enqueue ACTIVE, validate NULL case successfully, exit. +* Now we come back to validate that forked ACTIVE state. We proceed through +* 3-5, come to goto, jump to 1:. Let's assume our state didn't change, so we
kernel/bpf/verifier.c static bool states_maybe_looping(struct bpf_verifier_state *old, · line 15029
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+* are converging. But the problem is that we don't know that yet, as this +* convergence has to happen at iter_next() call site only. So if nothing is +* done, at 1: verifier will use bounded loop logic and declare infinite +* looping (and would be *technically* correct, if not for iterator "eventual +* sticky NULL" contract, see process_iter_next_call()). But we don't want +* that. So what we do in process_iter_next_call() when we go on another +* ACTIVE iteration, we bump slot->iter.depth, to mark that it's a different +* iteration. So when we detect soon-to-be-declared infinite loop, we also +* check if any of *ACTIVE* iterator state's depth differs. If yes, we pretend +* we are not looping and wait for next iter_next() call.
'depth' part of bpf_reg_state will be checked for equality in regsafe(), right? Everytime we branch out in process_iter_next_call() there is depth++
So how come we're able to converge with:
+ if (is_iter_next_insn(env, insn_idx, &iter_arg_reg_idx)) {
+ if (states_equal(env, &sl->state, cur)) {
That's because states_equal() is done right before doing process_iter_next_call(), right?
So depth counts the number of times bpf_iter*_next() was processed. In other words it's a number of ways the body of the loop can be walked?
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+if (is_iter_next_insn (env, insn_idx, &iter_arg_reg_idx)) { +if (states_equal (env, &sl->state, cur)) { +struct bpf_func_state *cur_frame; +struct bpf_reg_state *iter_state, *iter_reg; +int spi; + +/* current state is valid due to states_equal(), +* so we can assume valid iter state, no need for extra +* (re-)validations +*/
kernel/bpf/verifier.c static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) · line 15154
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+ cur_frame = cur->frame[cur->curframe]; + iter_reg = &cur_frame->regs[iter_arg_reg_idx]; + spi =iter_get_spi (env, iter_reg); +if (spi <0 ) +return spi; + iter_state = &func (env, iter_reg)->stack[spi].spilled_ptr; +if (iter_state->iter.state ==BPF_ITER_STATE_ACTIVE ) + goto hit; + } + goto skip_inf_loop_check;
This goto is "optional", right?
Meaning that if we remove it the states_maybe_looping() + states_equal() won't match anyway. The goto avoids wasting cycles.
kernel/bpf/verifier.c static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) · line 15157
Quoted 3 lines
kernel/bpf/verifier.c +3
-0+ } +/* attempt to detect infinite loop to avoid unnecessary doomed work */ + if (states_maybe_looping(&sl->state, cur) &&
Maybe cleaner is to remove above 'goto' and do '} else if (states_maybe_looping' here ?
Quoted 5 lines
kernel/bpf/verifier.c +2
-0+ states_equal(env, &sl->state, cur) && + !iter_active_depths_differ(&sl->state, cur)) {verbose_linfo (env, insn_idx,"; " );verbose (env,"infinite loop detected at insn %d\n" , insn_idx);return -EINVAL ;
Re: [PATCH bpf-next 13/17] bpf: add support for open-coded iterator loops
Quoted 15 lines · Alexei Starovoitov
Quoted 10 lines · Andrii Nakryiko
Teach verifier about the concept of open-coded (or inline) iterators.
This patch adds generic iterator loop verification logic, new
STACK_ITERstack slot type to contain iterator state, and necessary kfunc plumbing for iterator's constructor, destructor and next "methods". Next patch implements first specific version of iterator (number iterator for implementing for loop). Such split allows to have more focused commits for verifier logic and separate commit that we could point later to what it takes to add new kind of iterator.Quoted 2 lines
First, we add new fixed-size opaque struct
bpf_iter(24-byte long) to contain runtime state of any possible iterator. structbpf_iterstate is
Quoted 7 lines
Looking at the verifier changes it seems that it should be possible to support any sized iterator and we don't have to fit all of them in 24-bytes. The same bpf_iter_<kind>_{new,next,destroy}() naming convention can apply to types and we can have 8-byte struct
bpf_iter_num
Thebpf_for()macros would work with bpf_iter_<kind> too.
iirc that was your plan earlier (to have different structs).
What prompted you to change that plan?
Not really, single user-facing struct bpf_iter was what I was going for from the very beginning, similar to single struct bpf_dynptr. But I guess they are a bit different in that there are many generic operations applicable across different types of dynptr (bpf_dynptr_read, write, data, slice, etc), so it makes sense to abstract it behind single type.
Here, with iterators, besides something like "is iterator exhausted" (not that I'm planning to add something like that), there isn't much generic to be shared, so yeah, we can switch to one public UAPI struct per each type of iterator and then those can be tailored to each particular type. This will automatically work better for kfuncs as new/next/destroy trios will have the same struct bpf_iter_<type> * and it won't be possible to accidentally pass wrong bpf_iter_<type> to wrong new/next/destroy method.
Quoted 8 lines
Quoted 6 lines
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 into, say, cgroup iterator's next method.
is_iter_type_compatible()does that, right?
yep. Currently it also anticipates generic iterator functions, but as I mentioned above, I don't think we'll have any common methods anyways.
Quoted 10 lines
Quoted 10 lines
kernel/bpf/verifier.c +9
-0+ +static int mark_stack_slots_iter (struct bpf_verifier_env *env,struct bpf_reg_state *reg, +enum bpf_arg_type arg_type,int insn_idx) +{ +struct bpf_func_state *state =func (env, reg); +enum bpf_iter_type type; +int spi, i, j, id; + + spi =iter_get_spi (env, reg);
Quoted 8 lines
kernel/bpf/verifier.c static bool is_dynptr_type_expected(struct bpf_verifier_env *env, struct bpf_reg · line 1180
Quoted 6 lines
kernel/bpf/verifier.c +6
-0+if (spi <0 ) +return spi; + + type =arg_to_iter_type (arg_type); +if (type ==BPF_ITER_TYPE_INVALID ) +return -EINVAL ;Do we need
destroy_if_dynptr_stack_slot()equivalent here?
no, because bpf_iter is always ref-counted, so we'll always have explicit unmark_stack_slots_iter() call, which will reset slot types
destroy_if_dynptr_stack_slot() was added because LOCAL dynptr doesn't require explicit destruction. I mentioned this difference (simplification for bpf_iter case) somewhere in the commit message.
Quoted 15 lines
Quoted 15 lines
kernel/bpf/verifier.c +14
-0+ id =acquire_reference_state (env, insn_idx); +if (id <0 ) +return id; + +for (i =0 ; i <BPF_ITER_NR_SLOTS ; i++) { +struct bpf_stack_state *slot = &state->stack[spi - i]; +struct bpf_reg_state *st = &slot->spilled_ptr; + +__mark_reg_known_zero (st); + st->type =PTR_TO_STACK ;/* we don't have dedicated reg type */ + st->live |=REG_LIVE_WRITTEN ; + st->ref_obj_id = i ==0 ? id :0 ; + st->iter.type = i ==0 ? type :BPF_ITER_TYPE_INVALID ; + st->iter.state =BPF_ITER_STATE_ACTIVE ;
Quoted 8 lines
kernel/bpf/verifier.c static bool is_dynptr_type_expected(struct bpf_verifier_env *env, struct bpf_reg · line 1201
Quoted 6 lines
kernel/bpf/verifier.c +6
-0+ st->iter.depth =0 ; + +for (j =0 ; j <BPF_REG_SIZE ; j++) + slot->slot_type[j] =STACK_ITER ; + +mark_stack_slot_scratched (env, spi - i);dynptr needs similar
mark_stack_slot_scratched()fix, right?
probably yes. destroy_if_dynptr_stack_slot() is scratching slots, but we don't call that on OBJ_RELEASE (in unmark_stack_slots_dynptr), so yeah, we should add this for dynptrs as well
Quoted 10 lines
Quoted 5 lines
kernel/bpf/verifier.c +4
-0+ } + +return 0 ; +}...
Quoted 2 lines
(quoted diff) +0
-0@@ -3691,8 +3928,8 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
Quoted 10 lines
kernel/bpf/verifier.c static int check_stack_write_fixed_off(struct bpf_verifier_env *env, · line 3934
Quoted 8 lines
kernel/bpf/verifier.c +2
-2/* regular write of data into stack destroys any spilled ptr */ state->stack[spi].spilled_ptr.type =NOT_INIT ; -/* Mark slots as STACK_MISC if they belonged to spilled ptr. */ -if (is_spilled_reg (&state->stack[spi])) +/* Mark slots as STACK_MISC if they belonged to spilled ptr/dynptr/iter. */ +if (is_stack_slot_special (&state->stack[spi]))for (i =0 ; i <BPF_REG_SIZE ; i++)scrub_spilled_slot (&state->stack[spi].slot_type[i]);It fixes something for dynptr, right?
It's convoluted, I think it might not have a visible effect. This is the situation of partial (e.g., single byte) overwrite of STACK_DYNPTR/STACK_ITER, and without this change we'll leave some slot_types as STACK_MISC, while others as STACK_DYNPTP/STACK_ITER. This is unexpected state, but I think existing code always checks that for STACK_DYNPTR's all 8 slots are STACK_DYNPTR.
So I think it's a good clean up, but no consequences for dynptr correctness. And for STACK_ITER I don't have to worry about such mix, if any of the slot_type[i] is STACK_ITER, then it's a correct iterator.
Quoted 34 lines
Quoted 34 lines
kernel/bpf/verifier.c +33
-0+static int process_iter_next_call (struct bpf_verifier_env *env,int insn_idx, +struct bpf_kfunc_call_arg_meta *meta) +{ +struct bpf_verifier_state *cur_st = env->cur_state, *queued_st; +struct bpf_func_state *cur_fr = cur_st->frame[cur_st->curframe], *queued_fr; +struct bpf_reg_state *cur_iter, *queued_iter; +int iter_frameno = meta->iter.frameno; +int iter_spi = meta->iter.spi; + +BTF_TYPE_EMIT (struct bpf_iter ); + + cur_iter = &env->cur_state->frame[iter_frameno]->stack[iter_spi].spilled_ptr; + +if (cur_iter->iter.state !=BPF_ITER_STATE_ACTIVE && + cur_iter->iter.state !=BPF_ITER_STATE_DRAINED ) { +verbose (env,"verifier internal error: unexpected iterator state %d (%s)\n" , + cur_iter->iter.state,iter_state_str (cur_iter->iter.state)); +return -EFAULT ; + } + +if (cur_iter->iter.state ==BPF_ITER_STATE_ACTIVE ) { +/* branch out active iter state */ + queued_st =push_stack (env, insn_idx +1 , insn_idx, false); +if (!queued_st) +return -ENOMEM ; + + queued_iter = &queued_st->frame[iter_frameno]->stack[iter_spi].spilled_ptr; + queued_iter->iter.state =BPF_ITER_STATE_ACTIVE ; + queued_iter->iter.depth++; + + queued_fr = queued_st->frame[queued_st->curframe]; +mark_ptr_not_null_reg (&queued_fr->regs[BPF_REG_0 ]); + }
Quoted 8 lines
kernel/bpf/verifier.c static int process_dynptr_func(struct bpf_verifier_env *env, int regno, int insn · line 6804
Quoted 6 lines
kernel/bpf/verifier.c +6
-0+ +/* switch to DRAINED state, but keep the depth unchanged */ +/* mark current iter state as drained and assume returned NULL */ + cur_iter->iter.state =BPF_ITER_STATE_DRAINED ; +__mark_reg_known_zero (&cur_fr->regs[BPF_REG_0 ]); + cur_fr->regs[BPF_REG_0 ].type =SCALAR_VALUE ;
__mark_reg_const_zero()instead?
sure, didn't know about it
Quoted 30 lines
Quoted 4 lines
kernel/bpf/verifier.c +3
-0+ +return 0 ; +}...
Quoted 25 lines
kernel/bpf/verifier.c +25
-0+static bool is_iter_next_insn (struct bpf_verifier_env *env,int insn_idx,int *reg_idx) +{ +struct bpf_insn *insn = &env->prog->insnsi[insn_idx]; +const struct btf_param *args; +const struct btf_type *t; +const struct btf *btf; +int nargs, i; + +if (!bpf_pseudo_kfunc_call (insn)) +return false; +if (!is_iter_next_kfunc (insn->imm)) +return false; + + btf =find_kfunc_desc_btf (env, insn->off); +if (IS_ERR (btf)) +return false; + + t =btf_type_by_id (btf, insn->imm);/* FUNC */ + t =btf_type_by_id (btf, t->type);/* FUNC_PROTO */ + + args =btf_params (t); + nargs =btf_vlen (t); +for (i =0 ; i < nargs; i++) { +if (is_kfunc_arg_iter (btf, &args[i])) { + *reg_idx =BPF_REG_1 + i;
Quoted 8 lines
kernel/bpf/verifier.c static bool is_dynptr_type_expected(struct bpf_verifier_env *env, struct bpf_reg · line 1260
Quoted 3 lines
kernel/bpf/verifier.c +3
-0+return true; + } + }This is some future-proofing ?
The commit log says that all iterators has to in the form:
bpf_iter_<kind>_next(struct bpf_iter* it)
Should we check for one and only arg here instead?
Yeah, a bit of generality. For a long time I had an assumption hardcoded about first argument being struct bpf_iter *, but that felt unclean, so I generalized that before submission.
But I can't think why we wouldn't just dictate (and enforce) that struct bpf_iter * is first. It makes sense, it's clean, and we lose nothing. This is another thing that differs between dynptr and iter, for dynptr such restriction wouldn't make sense.
Where would be a good place to enforce this for iter kfuncs?
Quoted 37 lines
Quoted 37 lines
kernel/bpf/verifier.c +36
-0+ +return false; +} + +/* is_state_visited() handles iter_next() (see process_iter_next_call() for +* terminology) calls specially: as opposed to bounded BPF loops, it *expects* +* state matching, which otherwise looks like an infinite loop. So while +* iter_next() calls are taken care of, we still need to be careful and +* prevent erroneous and too eager declaration of "ininite loop", when +* iterators are involved. +* +* Here's a situation in pseudo-BPF assembly form: +* +* 0: again: ; set up iter_next() call args +* 1: r1 = &it ; <CHECKPOINT HERE> +* 2: call bpf_iter_num_next ; this is iter_next() call +* 3: if r0 == 0 goto done +* 4: ... something useful here ... +* 5: goto again ; another iteration +* 6: done: +* 7: r1 = &it +* 8: call bpf_iter_num_destroy ; clean up iter state +* 9: exit +* +* This is a typical loop. Let's assume that we have a prune point at 1:, +* before we get to `call bpf_iter_num_next` (e.g., because of that `goto +* again`, assuming other heuristics don't get in a way). +* +* When we first time come to 1:, let's say we have some state X. We proceed +* to 2:, fork states, enqueue ACTIVE, validate NULL case successfully, exit. +* Now we come back to validate that forked ACTIVE state. We proceed through +* 3-5, come to goto, jump to 1:. Let's assume our state didn't change, so we +* are converging. But the problem is that we don't know that yet, as this +* convergence has to happen at iter_next() call site only. So if nothing is +* done, at 1: verifier will use bounded loop logic and declare infinite +* looping (and would be *technically* correct, if not for iterator "eventual
Quoted 8 lines
Quoted 6 lines
+ * sticky NULL" contract, see
process_iter_next_call()). But we don't want
+ * that. So what we do inprocess_iter_next_call()when we go on another
+ * ACTIVE iteration, we bumpslot->iter.depth, to mark that it's a different
+ * iteration. So when we detect soon-to-be-declared infinite loop, we also
+ * check if any of *ACTIVE* iterator state's depth differs. If yes, we pretend
+ * we are not looping and wait for nextiter_next()call.'depth' part of
bpf_reg_statewill be checked for equality inregsafe(), right?
no, it is explicitly skipped (and it's actually stacksafe(), not regsafe()). I can add explicit comment that we *ignore* depth
I was considering adding a flag to states_equal() whether to check depth or not (that would make iter_active_depths_differ unnecessary), but it doesn't feel right. Any preferences one way or the other?
Quoted 5 lines
Everytime we branch out in
process_iter_next_call()there is depth++
So how come we're able to converge with:
+ if (is_iter_next_insn(env, insn_idx, &iter_arg_reg_idx)) {
+ if (states_equal(env, &sl->state, cur)) {
That's becausestates_equal()is done right before doingprocess_iter_next_call(), right?
Yes, we check convergence before we process_iter_next_call. We do converge because we ignore depth, as I mentioned above.
Quoted 3 lines
So depth counts the number of times bpf_iter*_next() was processed. In other words it's a number of ways the body of the loop can be walked?
More or less, yes. It's a number of sequential unrolls of loop body, each time with a different starting state. But all that only in the current code path. So it's not like "how many different loop states we could have" in total. It's number of loop unrols with the condition "assuming current code path that led to start of iterator loop". Some other code path could lead to the state (before iterator loop starts) that converges faster or slower, which is why I'm pointing out the distinction.
But I think "yes" would be the answer to the question you had in mind.
Quoted 22 lines
Quoted 11 lines
kernel/bpf/verifier.c +10
-0+if (is_iter_next_insn (env, insn_idx, &iter_arg_reg_idx)) { +if (states_equal (env, &sl->state, cur)) { +struct bpf_func_state *cur_frame; +struct bpf_reg_state *iter_state, *iter_reg; +int spi; + +/* current state is valid due to states_equal(), +* so we can assume valid iter state, no need for extra +* (re-)validations +*/ kernel/bpf/verifier.c static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) · line 15154
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+ cur_frame = cur->frame[cur->curframe]; + iter_reg = &cur_frame->regs[iter_arg_reg_idx]; + spi =iter_get_spi (env, iter_reg); +if (spi <0 ) +return spi; + iter_state = &func (env, iter_reg)->stack[spi].spilled_ptr; +if (iter_state->iter.state ==BPF_ITER_STATE_ACTIVE ) + goto hit; + } + goto skip_inf_loop_check;
Quoted 3 lines
This goto is "optional", right?
Meaning that if we remove it thestates_maybe_looping()+states_equal()won't match anyway. The goto avoids wasting cycles.
yes, avoids doing this check again, but also felt cleaner to be explicit about skipping infinite loop check
Quoted 6 lines
kernel/bpf/verifier.c static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) · line 15157
Quoted 4 lines
kernel/bpf/verifier.c +3
-0+ } +/* attempt to detect infinite loop to avoid unnecessary doomed work */ + if (states_maybe_looping(&sl->state, cur) &&Maybe cleaner is to remove above 'goto' and do '} else if (
states_maybe_looping' here ?
I can undo this, it felt cleaner with explicit "skip infinite loop check" both for new code and for that async_entry_cnt check above. But I can revert to if/else if/else if pattern, though I find it harder to follow, given all this code (plus comments) is pretty long, so it's easy to lose track when reading
Quoted 6 lines
Quoted 6 lines
kernel/bpf/verifier.c +2
-0+ states_equal(env, &sl->state, cur) && + !iter_active_depths_differ(&sl->state, cur)) {verbose_linfo (env, insn_idx,"; " );verbose (env,"infinite loop detected at insn %d\n" , insn_idx);return -EINVAL ;
Re: [PATCH bpf-next 13/17] bpf: add support for open-coded iterator loops
Quoted 4 lines · Andrii Nakryiko
particular type. This will automatically work better for kfuncs as new/next/destroy trios will have the same
struct bpf_iter_<type> *and it won't be possible to accidentally pass wrong bpf_iter_<type> to wrong new/next/destroy method.
Exactly.
Quoted 19 lines
Quoted 10 lines
Quoted 10 lines
kernel/bpf/verifier.c +9
-0+ +static int mark_stack_slots_iter (struct bpf_verifier_env *env,struct bpf_reg_state *reg, +enum bpf_arg_type arg_type,int insn_idx) +{ +struct bpf_func_state *state =func (env, reg); +enum bpf_iter_type type; +int spi, i, j, id; + + spi =iter_get_spi (env, reg);Quoted 8 lines
kernel/bpf/verifier.c static bool is_dynptr_type_expected(struct bpf_verifier_env *env, struct bpf_reg · line 1180
Quoted 6 lines
kernel/bpf/verifier.c +6
-0+if (spi <0 ) +return spi; + + type =arg_to_iter_type (arg_type); +if (type ==BPF_ITER_TYPE_INVALID ) +return -EINVAL ;Do we need
destroy_if_dynptr_stack_slot()equivalent here?
Quoted 6 lines
no, because
bpf_iteris always ref-counted, so we'll always have explicitunmark_stack_slots_iter()call, which will reset slot types
destroy_if_dynptr_stack_slot()was added because LOCAL dynptr doesn't require explicit destruction. I mentioned this difference (simplification forbpf_itercase) somewhere in the commit message.
I see. Makes sense.
Quoted 19 lines
Quoted 11 lines
kernel/bpf/verifier.c static int check_stack_write_fixed_off(struct bpf_verifier_env *env, · line 3934
Quoted 9 lines
/* regular write of data into stack destroys any spilled ptr */ state->stack[spi].spilled_ptr.type = NOT_INIT;kernel/bpf/verifier.c +2
-2-/* Mark slots as STACK_MISC if they belonged to spilled ptr. */ -if (is_spilled_reg (&state->stack[spi])) +/* Mark slots as STACK_MISC if they belonged to spilled ptr/dynptr/iter. */ +if (is_stack_slot_special (&state->stack[spi]))for (i =0 ; i <BPF_REG_SIZE ; i++)scrub_spilled_slot (&state->stack[spi].slot_type[i]);It fixes something for dynptr, right?
It's convoluted, I think it might not have a visible effect. This is the situation of partial (e.g., single byte) overwrite of STACK_DYNPTR/STACK_ITER, and without this change we'll leave some
slot_typesasSTACK_MISC, while others as STACK_DYNPTP/STACK_ITER. This is unexpected state, but I think existing code always checks that for STACK_DYNPTR's all 8 slots areSTACK_DYNPTR.
Quoted 4 lines
So I think it's a good clean up, but no consequences for dynptr correctness. And for
STACK_ITERI don't have to worry about such mix, if any of the slot_type[i] isSTACK_ITER, then it's a correct iterator.
agree. I was just curious.
Quoted 38 lines
Quoted 25 lines
Quoted 25 lines
kernel/bpf/verifier.c +25
-0+static bool is_iter_next_insn (struct bpf_verifier_env *env,int insn_idx,int *reg_idx) +{ +struct bpf_insn *insn = &env->prog->insnsi[insn_idx]; +const struct btf_param *args; +const struct btf_type *t; +const struct btf *btf; +int nargs, i; + +if (!bpf_pseudo_kfunc_call (insn)) +return false; +if (!is_iter_next_kfunc (insn->imm)) +return false; + + btf =find_kfunc_desc_btf (env, insn->off); +if (IS_ERR (btf)) +return false; + + t =btf_type_by_id (btf, insn->imm);/* FUNC */ + t =btf_type_by_id (btf, t->type);/* FUNC_PROTO */ + + args =btf_params (t); + nargs =btf_vlen (t); +for (i =0 ; i < nargs; i++) { +if (is_kfunc_arg_iter (btf, &args[i])) { + *reg_idx =BPF_REG_1 + i;Quoted 8 lines
kernel/bpf/verifier.c static bool is_dynptr_type_expected(struct bpf_verifier_env *env, struct bpf_reg · line 1260
Quoted 3 lines
kernel/bpf/verifier.c +3
-0+return true; + } + }This is some future-proofing ?
The commit log says that all iterators has to in the form:
bpf_iter_<kind>_next(struct bpf_iter* it)
Should we check for one and only arg here instead?Yeah, a bit of generality. For a long time I had an assumption hardcoded about first argument being struct
bpf_iter*, but that felt unclean, so I generalized that before submission.
Quoted 6 lines
But I can't think why we wouldn't just dictate (and enforce) that
struct bpf_iter *is first. It makes sense, it's clean, and we lose nothing. This is another thing that differs between dynptr and iter, for dynptr such restriction wouldn't make sense.Where would be a good place to enforce this for iter kfuncs?
I would probably just remove is_iter_next_insn() completely, hard code BPF_REG_1 and add a big comment for now.
In the follow up we can figure out how to:BUILD_BUG_ON(!__same_type(bpf_iter_num_next, some canonical proto for iter_next));
Like we do:
BUILD_BUG_ON(!__same_type(ops->map_lookup_elem,
(void *(*)(struct bpf_map *map, void *key))NULL));
Quoted 5 lines
Quoted 2 lines
'depth' part of
bpf_reg_statewill be checked for equality inregsafe(), right?no, it is explicitly skipped (and it's actually
stacksafe(), notregsafe()). I can add explicit comment that we *ignore* depth
Ahh. That's stacksafe() indeed.
Would be great to add a comment to:
+ if (old_reg->iter.type != cur_reg->iter.type ||
+ old_reg->iter.state != cur_reg->iter.state ||
+ !check_ids(old_reg->ref_obj_id, cur_reg->ref_obj_id, idmap))
+ return false;
that depth is explicitly not compared.
Quoted 3 lines
I was considering adding a flag to
states_equal()whether to check depth or not (that would makeiter_active_depths_differunnecessary), but it doesn't feel right. Any preferences one way or the other?
probably overkill. just comment should be enough.
Quoted 13 lines
Quoted 5 lines
Everytime we branch out in
process_iter_next_call()there is depth++
So how come we're able to converge with:
+ if (is_iter_next_insn(env, insn_idx, &iter_arg_reg_idx)) {
+ if (states_equal(env, &sl->state, cur)) {
That's becausestates_equal()is done right before doingprocess_iter_next_call(), right?Yes, we check convergence before we
process_iter_next_call. We do converge because we ignore depth, as I mentioned above.Quoted 3 lines
So depth counts the number of times bpf_iter*_next() was processed. In other words it's a number of ways the body of the loop can be walked?
Quoted 8 lines
More or less, yes. It's a number of sequential unrolls of loop body, each time with a different starting state. But all that only in the current code path. So it's not like "how many different loop states we could have" in total. It's number of loop unrols with the condition "assuming current code path that led to start of iterator loop". Some other code path could lead to the state (before iterator loop starts) that converges faster or slower, which is why I'm pointing out the distinction.
got it. I know the comments are big and extensive already, but little bit more won't hurt.
Quoted 5 lines
Quoted 5 lines
Quoted 4 lines
kernel/bpf/verifier.c +3
-0+ } +/* attempt to detect infinite loop to avoid unnecessary doomed work */ + if (states_maybe_looping(&sl->state, cur) &&
Quoted 7 lines
Quoted 1 line
Maybe cleaner is to remove above 'goto' and do '} else if (
states_maybe_looping' here ?I can undo this, it felt cleaner with explicit "skip infinite loop check" both for new code and for that
async_entry_cntcheck above. But I can revert to if/else if/else if pattern, though I find it harder to follow, given all this code (plus comments) is pretty long, so it's easy to lose track when reading
I'm fine whichever way. I just remembered that you typically try to avoid goto-s and seeing goto here that could have easily been 'else' raised my internal alarm that I could be missing something subtle in the code here.
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
kernel/bpf/verifier.c +2
-0+ states_equal(env, &sl->state, cur) && + !iter_active_depths_differ(&sl->state, cur)) {verbose_linfo (env, insn_idx,"; " );verbose (env,"infinite loop detected at insn %d\n" , insn_idx);return -EINVAL ;
Re: [PATCH bpf-next 13/17] bpf: add support for open-coded iterator loops
Quoted 9 lines · Alexei Starovoitov
Quoted 4 lines · Andrii Nakryiko
particular type. This will automatically work better for kfuncs as new/next/destroy trios will have the same
struct bpf_iter_<type> *and it won't be possible to accidentally pass wrong bpf_iter_<type> to wrong new/next/destroy method.Exactly.
cool, I'll change this to struct bpf_iter_<type>
[...]
Quoted 49 lines
Quoted 39 lines
Quoted 26 lines
Quoted 26 lines
kernel/bpf/verifier.c +25
-0+static bool is_iter_next_insn (struct bpf_verifier_env *env,int insn_idx,int *reg_idx) +{ +struct bpf_insn *insn = &env->prog->insnsi[insn_idx]; +const struct btf_param *args; +const struct btf_type *t; +const struct btf *btf; +int nargs, i; + +if (!bpf_pseudo_kfunc_call (insn)) +return false; +if (!is_iter_next_kfunc (insn->imm)) +return false; + + btf =find_kfunc_desc_btf (env, insn->off); +if (IS_ERR (btf)) +return false; + + t =btf_type_by_id (btf, insn->imm);/* FUNC */ + t =btf_type_by_id (btf, t->type);/* FUNC_PROTO */ + + args =btf_params (t); + nargs =btf_vlen (t); +for (i =0 ; i < nargs; i++) { +if (is_kfunc_arg_iter (btf, &args[i])) { + *reg_idx =BPF_REG_1 + i;Quoted 8 lines
kernel/bpf/verifier.c static bool is_dynptr_type_expected(struct bpf_verifier_env *env, struct bpf_reg · line 1260
Quoted 3 lines
kernel/bpf/verifier.c +3
-0+return true; + } + }This is some future-proofing ?
The commit log says that all iterators has to in the form:
bpf_iter_<kind>_next(struct bpf_iter* it)
Should we check for one and only arg here instead?Yeah, a bit of generality. For a long time I had an assumption hardcoded about first argument being struct
bpf_iter*, but that felt unclean, so I generalized that before submission.Quoted 6 lines
But I can't think why we wouldn't just dictate (and enforce) that
struct bpf_iter *is first. It makes sense, it's clean, and we lose nothing. This is another thing that differs between dynptr and iter, for dynptr such restriction wouldn't make sense.Where would be a good place to enforce this for iter kfuncs?
I would probably just remove
is_iter_next_insn()completely, hard codeBPF_REG_1and add a big comment for now.
Quoted 7 lines
In the follow up we can figure out how to:
BUILD_BUG_ON(!__same_type(bpf_iter_num_next, some canonical proto for iter_next));Like we do:
BUILD_BUG_ON(!__same_type(ops->map_lookup_elem,(void *(*)(struct bpf_map *map, void *key))NULL));
I ended up adding proper enforcement of iter kfunc prototypes and generalizing everything with new KF_ITER_xxx flags. It's a pretty major change that allows implementing new iterators even easier, please see v2. It's now possible to define iterators in kernel modules as well, thanks to not having to update core verifier logic for each new set of iter functions.
Quoted 13 lines
Quoted 5 lines
Quoted 2 lines
'depth' part of
bpf_reg_statewill be checked for equality inregsafe(), right?no, it is explicitly skipped (and it's actually
stacksafe(), notregsafe()). I can add explicit comment that we *ignore* depthAhh. That's
stacksafe()indeed.
Would be great to add a comment to:kernel/bpf/verifier.c +4
-0+if (old_reg->iter.type != cur_reg->iter.type || + old_reg->iter.state != cur_reg->iter.state || + !check_ids (old_reg->ref_obj_id, cur_reg->ref_obj_id, idmap)) +return false;
Quoted 1 line
that depth is explicitly not compared.
ok, added
Quoted 7 lines
Quoted 4 lines
I was considering adding a flag to
states_equal()whether to check depth or not (that would makeiter_active_depths_differunnecessary), but it doesn't feel right. Any preferences one way or the other?probably overkill. just comment should be enough.
[...]
Quoted 14 lines
Quoted 6 lines
Quoted 6 lines
Quoted 5 lines
kernel/bpf/verifier.c +3
-0+ } +/* attempt to detect infinite loop to avoid unnecessary doomed work */ + if (states_maybe_looping(&sl->state, cur) &&Quoted 7 lines
Quoted 1 line
Maybe cleaner is to remove above 'goto' and do '} else if (
states_maybe_looping' here ?I can undo this, it felt cleaner with explicit "skip infinite loop check" both for new code and for that
async_entry_cntcheck above. But I can revert to if/else if/else if pattern, though I find it harder to follow, given all this code (plus comments) is pretty long, so it's easy to lose track when reading
Quoted 3 lines
I'm fine whichever way. I just remembered that you typically try to avoid goto-s and seeing goto here that could have easily been 'else' raised my internal alarm that I could be missing something subtle in the code here.
Well, it depends, as usual. I certainly don't like something like "goto process_bpf_exit" in do_check(), which jumps into the middle of a completely unrelated if/else branch, so there's that. But these "skip a bunch of checks" gotos are cleaner, IMO, if we are talking about a bunch of complicated if/else if/else checks. Let's go with explicit goto for now, we can always revert.
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
kernel/bpf/verifier.c +2
-0+ states_equal(env, &sl->state, cur) && + !iter_active_depths_differ(&sl->state, cur)) {verbose_linfo (env, insn_idx,"; " );verbose (env,"infinite loop detected at insn %d\n" , insn_idx);return -EINVAL ;
Andrii Nakryiko
maintainerPATCH 14/17 bpf: implement number iterator
In reply to Andrii NakryikoImplement 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, while end is exclusive).
- bpf_iter_num_next() which will keep returning 4-byte 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, that 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 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/enforced, they are runtime values only.
While 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 and 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 | 14 +++++++-- kernel/bpf/bpf_iter.c | 71 +++++++++++++++++++++++++++++++++++++++++++ kernel/bpf/helpers.c | 3 ++ kernel/bpf/verifier.c | 24 +++++++++++++-- 4 files changed, 107 insertions(+), 5 deletions(-)
include/linux/bpf.h +11 -3
@@ -613,6 +613,9 @@ enum bpf_type_flag {/* DYNPTR points to xdp_buff */ DYNPTR_TYPE_XDP =BIT (16 +BPF_BASE_TYPE_BITS ), +/* ITER of integers */ +ITER_TYPE_NUM =BIT (17 +BPF_BASE_TYPE_BITS ), + __BPF_TYPE_FLAG_MAX, __BPF_TYPE_LAST_FLAG = __BPF_TYPE_FLAG_MAX - 1, };
@@ -620,7 +623,7 @@ enum bpf_type_flag {#define DYNPTR_TYPE_FLAG_MASK (DYNPTR_TYPE_LOCAL | DYNPTR_TYPE_RINGBUF | DYNPTR_TYPE_SKB \ | DYNPTR_TYPE_XDP) -#define ITER_TYPE_FLAG_MASK (0) +#define ITER_TYPE_FLAG_MASK (ITER_TYPE_NUM)/* Max number of base types. */ #define BPF_BASE_TYPE_LIMIT (1UL << BPF_BASE_TYPE_BITS)
@@ -1167,6 +1170,7 @@ u32 bpf_dynptr_get_size(const struct bpf_dynptr_kern *ptr);enum bpf_iter_type {BPF_ITER_TYPE_INVALID , +BPF_ITER_TYPE_NUM , };#ifdef CONFIG_BPF_JIT
@@ -1622,8 +1626,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 | \
kernel/bpf/bpf_iter.c +71 -0
80 lines not on this page · raw message
kernel/bpf/helpers.c +3 -0
@@ -2398,6 +2398,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) +BTF_ID_FLAGS(func, bpf_iter_num_next, KF_RET_NULL) +BTF_ID_FLAGS(func, bpf_iter_num_destroy)BTF_SET8_END (common_btf_ids) static const struct btf_kfunc_id_set common_kfunc_set = {
kernel/bpf/verifier.c +22 -2
@@ -779,6 +779,8 @@ static const char *dynptr_type_str(enum bpf_dynptr_type type)static const char *iter_type_str (enum bpf_iter_type type) {switch (type) { +case BPF_ITER_TYPE_NUM : +return "num" ;case BPF_ITER_TYPE_INVALID :return "<invalid>" ;default :
@@ -1157,6 +1159,8 @@ static bool is_dynptr_type_expected(struct bpf_verifier_env *env, struct bpf_regstatic enum bpf_dynptr_type arg_to_iter_type (enum bpf_arg_type arg_type) {switch (arg_type &ITER_TYPE_FLAG_MASK ) { +case ITER_TYPE_NUM : +return BPF_ITER_TYPE_NUM ;default :return BPF_ITER_TYPE_INVALID ; }
@@ -9445,6 +9449,9 @@ enum special_kfunc_type { KF_bpf_dynptr_from_xdp, KF_bpf_dynptr_slice, KF_bpf_dynptr_slice_rdwr, + KF_bpf_iter_num_new, + KF_bpf_iter_num_next, + KF_bpf_iter_num_destroy, };BTF_SET_START (special_kfunc_set)
@@ -9483,6 +9490,9 @@ BTF_ID(func, bpf_dynptr_from_skb) BTF_ID(func, bpf_dynptr_from_xdp) BTF_ID(func, bpf_dynptr_slice) BTF_ID(func, bpf_dynptr_slice_rdwr) +BTF_ID(func, bpf_iter_num_new) +BTF_ID(func, bpf_iter_num_next) +BTF_ID(func, bpf_iter_num_destroy)static bool is_kfunc_bpf_rcu_read_lock (struct bpf_kfunc_call_arg_meta *meta) {
@@ -9496,7 +9506,7 @@ static bool is_kfunc_bpf_rcu_read_unlock(struct bpf_kfunc_call_arg_meta *meta)static bool is_iter_next_kfunc (int btf_id) { -return false; +return btf_id == special_kfunc_list[KF_bpf_iter_num_next]; } static enum kfunc_ptr_arg_type
@@ -10278,7 +10288,17 @@ static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_if (is_kfunc_arg_uninit (btf, &args[i])) iter_arg_type |=MEM_UNINIT ; - ret =process_iter_arg (env, regno, insn_idx, iter_arg_type, meta); +if (meta->func_id == special_kfunc_list[KF_bpf_iter_num_new] || + meta->func_id == special_kfunc_list[KF_bpf_iter_num_next]) { + iter_arg_type |=ITER_TYPE_NUM ; + }else if (meta->func_id == special_kfunc_list[KF_bpf_iter_num_destroy]) { + iter_arg_type |=ITER_TYPE_NUM |OBJ_RELEASE ; + }else { +verbose (env,"verifier internal error: unrecognized iterator kfunc\n" ); +return -EFAULT ; + } + + ret =process_iter_arg (env, regno, insn_idx, iter_arg_type, meta);if (ret <0 )return ret;break ;
Signature · 1 line
2.30.2
Re: [PATCH bpf-next 14/17] bpf: implement number iterator
kernel/bpf/verifier.c static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_ · line 10295
Quoted 12 lines · Andrii Nakryiko
static enum
kfunc_ptr_arg_typekernel/bpf/verifier.c +5
-1@@ -10278,7 +10288,17 @@ static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_if (is_kfunc_arg_uninit (btf, &args[i])) iter_arg_type |=MEM_UNINIT ; - ret =process_iter_arg (env, regno, insn_idx, iter_arg_type, meta); +if (meta->func_id == special_kfunc_list[KF_bpf_iter_num_new] || + meta->func_id == special_kfunc_list[KF_bpf_iter_num_next]) { + iter_arg_type |=ITER_TYPE_NUM ; + }else if (meta->func_id == special_kfunc_list[KF_bpf_iter_num_destroy]) { + iter_arg_type |=ITER_TYPE_NUM |OBJ_RELEASE ;
Since OBJ_RELEASE is set pretty late here and kfuncs are not marked with KF_RELEASE, the arg_type_is_release() in check_func_arg_reg_off() won't trigger. So I'm confused why there is:
+ if (arg_type_is_iter(arg_type))
+ return 0;
in the previous patch.
Will it ever trigger?
Separate question: What happens when the user does:bpf_iter_destroy(&it); bpf_iter_destroy(&it);
+ if (!is_iter_reg_valid_init(env, reg)) {
+ verbose(env, "expected an initialized iter as arg #%d\n", regno);
will trigger, right?
I didn't find such selftest.
Re: [PATCH bpf-next 14/17] bpf: implement number iterator
Quoted 8 lines · Alexei Starovoitov
Quoted 6 lines · Andrii Nakryiko
static enum
kfunc_ptr_arg_typekernel/bpf/verifier.c +0
-0@@ -10278,7 +10288,17 @@ static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_if (is_kfunc_arg_uninit (btf, &args[i])) iter_arg_type |=MEM_UNINIT ;
Quoted 9 lines
kernel/bpf/verifier.c static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_ · line 10295
Quoted 6 lines
kernel/bpf/verifier.c +5
-1- ret =process_iter_arg (env, regno, insn_idx, iter_arg_type, meta); +if (meta->func_id == special_kfunc_list[KF_bpf_iter_num_new] || + meta->func_id == special_kfunc_list[KF_bpf_iter_num_next]) { + iter_arg_type |=ITER_TYPE_NUM ; + }else if (meta->func_id == special_kfunc_list[KF_bpf_iter_num_destroy]) { + iter_arg_type |=ITER_TYPE_NUM |OBJ_RELEASE ;Since
OBJ_RELEASEis set pretty late here and kfuncs are not marked withKF_RELEASE, thearg_type_is_release()incheck_func_arg_reg_off()won't trigger.
yeah, I had troubles with doing this release using existing scheme. KF_RELEASE doesn't work, as it makes some extra assumptions about what was acquired, it didn't fit iters. And I didn't have a precedent in dynptr to learn from, as RINGBUF dynptr is "acquired" and "released" using helper. Basically, we don't have dynptr release kfunc yet.
So I set the OBJ_RELEASE flag for process_iter_arg to do an explicit release.
I'd appreciate guidance on how to do this cleaner. Naive attempt to set KF_ACQUIRE for bpf_iter_num_new() and KF_RELEASE for bpf_iter_num_destroy() didn't work.
Quoted 5 lines
So I'm confused why there is:
(quoted diff) +2
-0+ if (arg_type_is_iter(arg_type)) + return 0;in the previous patch.
Will it ever trigger?
maybe not, just followed what dynptr is doing
Quoted 4 lines
Separate question: What happens when the user does:
bpf_iter_destroy(&it);bpf_iter_destroy(&it);
After the first destroy stack slots are marked STACK_INVALID, so next bpf_iter_destroy(&it) will complain about not seeing the initialized iterator.
Quoted 5 lines
(quoted diff) +2
-0+ if (!is_iter_reg_valid_init(env, reg)) { + verbose(env, "expected an initialized iter as arg #%d\n", regno);will trigger, right?
I didn't find such selftest.
yep, that's the idea, I just checked, I do have such test, it's in iters_state_safety.c:
__failure __msg("expected an initialized iter as arg #1") int double_destroy_fail(void *ctx)
There is also next_after_destroy_fail, next_without_new_fail, and other obvious error conditions. But it would be good for few people to check that with a fresh eye. I added them a long time ago, and might have missed something.
Re: [PATCH bpf-next 14/17] bpf: implement number iterator
Quoted 26 lines · Andrii Nakryiko
Quoted 8 lines · Alexei Starovoitov
Quoted 6 lines · Andrii Nakryiko
static enum
kfunc_ptr_arg_typekernel/bpf/verifier.c +0
-0@@ -10278,7 +10288,17 @@ static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_if (is_kfunc_arg_uninit (btf, &args[i])) iter_arg_type |=MEM_UNINIT ;Quoted 9 lines
kernel/bpf/verifier.c static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_ · line 10295
Quoted 6 lines
kernel/bpf/verifier.c +5
-1- ret =process_iter_arg (env, regno, insn_idx, iter_arg_type, meta); +if (meta->func_id == special_kfunc_list[KF_bpf_iter_num_new] || + meta->func_id == special_kfunc_list[KF_bpf_iter_num_next]) { + iter_arg_type |=ITER_TYPE_NUM ; + }else if (meta->func_id == special_kfunc_list[KF_bpf_iter_num_destroy]) { + iter_arg_type |=ITER_TYPE_NUM |OBJ_RELEASE ;Since
OBJ_RELEASEis set pretty late here and kfuncs are not marked withKF_RELEASE, thearg_type_is_release()incheck_func_arg_reg_off()won't trigger.yeah, I had troubles with doing this release using existing scheme.
KF_RELEASEdoesn't work, as it makes some extra assumptions about what was acquired, it didn't fit iters. And I didn't have a precedent in dynptr to learn from, as RINGBUF dynptr is "acquired" and "released" using helper. Basically, we don't have dynptr release kfunc yet.
Quoted 5 lines
So I set the
OBJ_RELEASEflag forprocess_iter_argto do an explicit release.I'd appreciate guidance on how to do this cleaner. Naive attempt to set
KF_ACQUIREforbpf_iter_num_new()andKF_RELEASEforbpf_iter_num_destroy()didn't work.
yep. KF_ACQUIRE and KF_RELEASE don't fit here, since they need the register to be ref_obj_id-ed while here it's in the stack.
The current patch is fine. We can generalize iter and dynptr later in the follow up.
Quoted 24 lines
Quoted 6 lines
So I'm confused why there is:
(quoted diff) +2
-0+ if (arg_type_is_iter(arg_type)) + return 0;in the previous patch.
Will it ever trigger?maybe not, just followed what dynptr is doing
Quoted 4 lines
Separate question: What happens when the user does:
bpf_iter_destroy(&it);bpf_iter_destroy(&it);After the first destroy stack slots are marked
STACK_INVALID, so nextbpf_iter_destroy(&it)will complain about not seeing the initialized iterator.Quoted 5 lines
(quoted diff) +2
-0+ if (!is_iter_reg_valid_init(env, reg)) { + verbose(env, "expected an initialized iter as arg #%d\n", regno);will trigger, right?
I didn't find such selftest.
Quoted 5 lines
yep, that's the idea, I just checked, I do have such test, it's in
iters_state_safety.c:
__failure__msg("expected an initialized iter as arg #1")intdouble_destroy_fail(void *ctx)
See it now. Thanks for checking.
Quoted 4 lines
There is also
next_after_destroy_fail,next_without_new_fail, and other obvious error conditions. But it would be good for few people to check that with a fresh eye. I added them a long time ago, and might have missed something.
Andrii Nakryiko
maintainerPATCH 15/17 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 macro utilize cleanup attribute to ensure proper destruction of the iterator and thanks to that manage to provide an ergonomic very close to C language for construct. Typical integer 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 mean as a simple "repeat action N times":
bpf_repeat(N) { /* whatever */ }
Note that break and continue 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 (right now hypothetical) bpf_iter_cgroup_{new,next,destroy}() functions to form a loop over cgroups, where some, input, args are passed verbatim into constructor asbpf_iter_cgroup_new(&it, some, input, args).
As a demonstration, add pyperf variant based on bpf_for() loop.
Also clean up few tests that either included bpf_misc.h header unnecessarily from user-space or included it before any common types are defined.
--- .../bpf/prog_tests/bpf_verif_scale.c | 6 ++ .../bpf/prog_tests/uprobe_autoattach.c | 1 - tools/testing/selftests/bpf/progs/bpf_misc.h | 76 +++++++++++++++++++ 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, 101 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 +76 -0
81 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.30.2
Re: [PATCH bpf-next 15/17] selftests/bpf: add bpf_for_each(), bpf_for(), and bpf_repeat() macros
Quoted 114 lines · Andrii Nakryiko
Add
bpf_for_each(),bpf_for()andbpf_repeat()macros that make writing open-coded iterator-based loops much more convenient and natural. These macro utilize cleanup attribute to ensure proper destruction of the iterator and thanks to that manage to provide an ergonomic very close to C language for construct. Typical integer 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 mean as a simple "repeat action N times":
bpf_repeat(N){ /* whatever */ }Note that break and continue 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 (right now hypothetical) bpf_iter_cgroup_{new,next,destroy}() functions to form a loop over cgroups, where
some, input, argsare passed verbatim into constructor asbpf_iter_cgroup_new(&it, some, input, args).As a demonstration, add pyperf variant based on
bpf_for()loop.Also clean up few tests that either included
bpf_misc.hheader unnecessarily from user-space or included it before any common types are defined.Signed-off-by Andrii Nakryiko <[email protected]>--- .../bpf/prog_tests/bpf_verif_scale.c | 6 ++ .../bpf/prog_tests/uprobe_autoattach.c | 1 - tools/testing/selftests/bpf/progs/bpf_misc.h | 76 +++++++++++++++++++ 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, 101 insertions(+), 10 deletions(-) create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_iter.ctools/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 +21
-0@@ -75,5 +75,81 @@#define FUNC_REG_ARG_CNT 5#endif +struct bpf_iter ; + +extern int bpf_iter_num_new(struct bpf_iter *it__uninit, int start, int end) __ksym; +extern int *bpf_iter_num_next (struct bpf_iter *it) __ksym; +extern void bpf_iter_num_destroy(struct bpf_iter *it) __ksym; + +#ifndef bpf_for_each +/* bpf_for_each(iter_kind, elem, args...) provides generic construct for using BPF +* open-coded iterators without having to write mundane explicit low-level +* loop. Instead, it provides for()-like generic construct that can be used +* pretty naturally. E.g., for some hypothetical cgroup iterator, you'd write: +* +* struct cgroup *cg, *parent_cg = <...>; +* +* bpf_for_each(cgroup, cg, parent_cg, CG_ITER_CHILDREN) { +* bpf_printk("Child cgroup id = %d", cg->cgroup_id); +* if (cg->cgroup_id == 123) +* break; +* } +* +* I.e., it looks almost like high-level for each loop in other languages,
tools/testing/selftests/bpf/progs/bpf_misc.h line 108
Quoted 10 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +10
-0+* supports continue/break, and is verifiable by BPF verifier. +* +* For iterating integers, the difference betwen bpf_for_each(num, i, N, M) +* and bpf_for(i, N, M) is in that bpf_for() provides additional proof to +* verifier that i is in [N, M) range, and in bpf_for_each() case i is `int +* *`, not just `int`. So for integers bpf_for() is more convenient. +*/ +#define bpf_for_each(type, cur, args...) for ( \ + /* initialize and define destructor */ \ + struct bpf_iter ___it __attribute__((cleanup(bpf_iter_##type##_destroy))), \
We should probably say somewhere that it requires C99 with some flag that allows declaring variables inside the loop.
Also what are the rules for attr(cleanup()).
When does it get called?
My understanding that the visibility of ___it is only within for() body. So when the prog does:bpf_for(i, 0, 10) sum += i;bpf_for(i, 0, 10) sum += i;
the compiler should generate bpf_iter_num_destroy right after each bpf_for() ? Or will it group them at the end of function body and destroy all iterators ? Will compiler reuse the stack space used by ___it in case there are multiple bpf_for-s ?
Quoted 16 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +16
-0+/* ___p pointer is just to call bpf_iter_##type##_new() *once* to init ___it */ \ + *___p = (bpf_iter_##type##_new(&___it, ##args), \ + /* this is a workaround for Clang bug: it currently doesn't emit BTF */ \ +/* for bpf_iter_##type##_destroy when used from cleanup() attribute */ \ + (void)bpf_iter_##type##_destroy, (void *)0); \ + /* iteration and termination check */ \ + ((cur = bpf_iter_##type##_next(&___it))); \ +/* nothing here */ \ +) +#endif /* bpf_for_each */ + +#ifndef bpf_for +/* bpf_for(i, start, end) proves to verifier that i is in [start, end) */ +#define bpf_for(i, start, end) for ( \ + /* initialize and define destructor */ \ + struct bpf_iter ___it __attribute__((cleanup(bpf_iter_num_destroy))), \
tools/testing/selftests/bpf/progs/bpf_misc.h line 134
Quoted 10 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +10
-0+/* ___p pointer is necessary to call bpf_iter_num_new() *once* to init ___it */ \ + *___p = (bpf_iter_num_new (&___it, (start), (end)), \ +/* this is a workaround for Clang bug: it currently doesn't emit BTF */ \ +/* for bpf_iter_num_destroy when used from cleanup() attribute */ \ + (void )bpf_iter_num_destroy, (void *)0 ); \ + ({ \ + /* iteration step */ \ + int *___t = bpf_iter_num_next(&___it); \ + /* termination and bounds check */ \ + (___t && ((i) = *___t, i >= (start) && i < (end))); \
The i >= (start) && i < (end) is necessary to make sure that the verifier tightens the range of 'i' inside the body of the loop and
when the program does arr[i] access the verifier will know that 'i' is within bounds, right?
In such case should we add __builtin_constant_p() check for 'start' and 'end' ? int arr[100];
if (var < 100)
bpf_for(i, 0, global_var) sum += arr[i];
will fail the verifier and the users might complain of dumb verifier.
Also if start and end are variables they potentially can change between bpf_iter_num_new() and in each iteration of the loop.__builtin_constant_p() might be too restrictive.
May be read start/end once, at least?
Quoted 5 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +5
-0+ }); \ +/* nothing here */ \ +) +#endif /* bpf_for */ +
Re: [PATCH bpf-next 15/17] selftests/bpf: add bpf_for_each(), bpf_for(), and bpf_repeat() macros
Quoted 121 lines · Alexei Starovoitov
Quoted 119 lines · Andrii Nakryiko
Add
bpf_for_each(),bpf_for()andbpf_repeat()macros that make writing open-coded iterator-based loops much more convenient and natural. These macro utilize cleanup attribute to ensure proper destruction of the iterator and thanks to that manage to provide an ergonomic very close to C language for construct. Typical integer 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 mean as a simple "repeat action N times":
bpf_repeat(N){ /* whatever */ }Note that break and continue 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 (right now hypothetical) bpf_iter_cgroup_{new,next,destroy}() functions to form a loop over cgroups, where
some, input, argsare passed verbatim into constructor asbpf_iter_cgroup_new(&it, some, input, args).As a demonstration, add pyperf variant based on
bpf_for()loop.Also clean up few tests that either included
bpf_misc.hheader unnecessarily from user-space or included it before any common types are defined.Signed-off-by Andrii Nakryiko <[email protected]>--- .../bpf/prog_tests/bpf_verif_scale.c | 6 ++ .../bpf/prog_tests/uprobe_autoattach.c | 1 - tools/testing/selftests/bpf/progs/bpf_misc.h | 76 +++++++++++++++++++ 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, 101 insertions(+), 10 deletions(-) create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_iter.ctools/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 +26
-0@@ -75,5 +75,81 @@#define FUNC_REG_ARG_CNT 5#endif +struct bpf_iter ; + +extern int bpf_iter_num_new(struct bpf_iter *it__uninit, int start, int end) __ksym; +extern int *bpf_iter_num_next (struct bpf_iter *it) __ksym; +extern void bpf_iter_num_destroy(struct bpf_iter *it) __ksym; + +#ifndef bpf_for_each +/* bpf_for_each(iter_kind, elem, args...) provides generic construct for using BPF +* open-coded iterators without having to write mundane explicit low-level +* loop. Instead, it provides for()-like generic construct that can be used +* pretty naturally. E.g., for some hypothetical cgroup iterator, you'd write: +* +* struct cgroup *cg, *parent_cg = <...>; +* +* bpf_for_each(cgroup, cg, parent_cg, CG_ITER_CHILDREN) { +* bpf_printk("Child cgroup id = %d", cg->cgroup_id); +* if (cg->cgroup_id == 123) +* break; +* } +* +* I.e., it looks almost like high-level for each loop in other languages, +* supports continue/break, and is verifiable by BPF verifier. +* +* For iterating integers, the difference betwen bpf_for_each(num, i, N, M) +* and bpf_for(i, N, M) is in that bpf_for() provides additional proof to +* verifier that i is in [N, M) range, and in bpf_for_each() case i is `int
Quoted 8 lines
tools/testing/selftests/bpf/progs/bpf_misc.h line 108
Quoted 5 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +5
-0+* *`, not just `int`. So for integers bpf_for() is more convenient. +*/ +#define bpf_for_each(type, cur, args...) for ( \ + /* initialize and define destructor */ \ + struct bpf_iter ___it __attribute__((cleanup(bpf_iter_##type##_destroy))), \We should probably say somewhere that it requires C99 with some flag that allows declaring variables inside the loop.
yes, I'll add a comment. I think cleanup attribute isn't standard as well, I'll mention it. This shouldn't be restrictive, though, as we expect very modern Clang (or eventually GCC), which definitely will support all of that. And I feel like most people don't restrict their BPF-side code to strict C89 anyways.
Quoted 3 lines
Also what are the rules for attr(cleanup()).
When does it get called?
From GCC documentation:
Quoted 1 line
The cleanup attribute runs a function when the variable goes out of scope.
So given ___it is bound to for loop, any code path that leads to loop exit (so, when condition turns false or *breaking* out of the loop, which is why I use cleanup, this was a saving grace for this approach to work at all).
Quoted 1 line
My understanding that the visibility of
___itis only withinfor()body.
right
Quoted 5 lines
So when the prog does:
bpf_for(i, 0, 10)sum += i;bpf_for(i, 0, 10)sum += i;the compiler should generate
bpf_iter_num_destroyright after eachbpf_for()?
Conceptually, yes, but see the note about breaking out of the loop above. How actual assembly code is generated is beyond our control. If the compiler generates multiple separate code paths, each with its own destroy, that's fine as well. No assumptions are made in the verifier, we just need to see one bpf_iter_<type>_destroy() for each instance of iterator.
Quoted 1 line
Or will it group them at the end of function body and destroy all iterators ?
That would be a bug, as documentation states that clean up happens as soon as a variable goes out of scope. Delaying clean up could result in program logic bugs. I.e., we rely on destructors to be called as soon as possible.
Quoted 1 line
Will compiler reuse the stack space used by
___itin case there are multiple bpf_for-s ?
That's the question to compiler developers, but I'd assume that, yes, it should. Why not?
And looking at, for example, iter_pass_iter_ptr_to_subprog which has 4 sequential bpf_for() loops:
0000000000002328 <iter_pass_iter_ptr_to_subprog>:
1125: bf a6 00 00 00 00 00 00 r6 = r10
1126: 07 06 00 00 28 ff ff ff r6 += -216 <-- THIS IS ITER
1127: bf 61 00 00 00 00 00 00 r1 = r6
1128: b4 02 00 00 00 00 00 00 w2 = 0
1129: b4 03 00 00 10 00 00 00 w3 = 16
1130: 85 10 00 00 ff ff ff ff call -1
0000000000002350: R_BPF_64_32 bpf_iter_num_new
1131: bf a7 00 00 00 00 00 00 r7 = r10
1132: 07 07 00 00 c0 ff ff ff r7 += -64
1133: bf 61 00 00 00 00 00 00 r1 = r6
1134: bf 72 00 00 00 00 00 00 r2 = r7
1135: b4 03 00 00 10 00 00 00 w3 = 16
1136: b4 04 00 00 02 00 00 00 w4 = 2
1137: 85 10 00 00 53 00 00 00 call 83
0000000000002388: R_BPF_64_32 .text
1138: bf 61 00 00 00 00 00 00 r1 = r6
1139: 85 10 00 00 ff ff ff ff call -1
0000000000002398: R_BPF_64_32 bpf_iter_num_destroy
1140: bf 61 00 00 00 00 00 00 r1 = r6 <<--- HERE WE REUSE
1141: b4 02 00 00 00 00 00 00 w2 = 0
1142: b4 03 00 00 20 00 00 00 w3 = 32
1143: 85 10 00 00 ff ff ff ff call -1
00000000000023b8: R_BPF_64_32 bpf_iter_num_newNote that r6 is set to fp-216 and is just reused as is for second bpf_for loop (second bpf_iter_num_new) call.
Quoted 23 lines
Quoted 23 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +22
-0+/* ___p pointer is just to call bpf_iter_##type##_new() *once* to init ___it */ \ + *___p = (bpf_iter_##type##_new(&___it, ##args), \ + /* this is a workaround for Clang bug: it currently doesn't emit BTF */ \ +/* for bpf_iter_##type##_destroy when used from cleanup() attribute */ \ + (void)bpf_iter_##type##_destroy, (void *)0); \ + /* iteration and termination check */ \ + ((cur = bpf_iter_##type##_next(&___it))); \ +/* nothing here */ \ +) +#endif /* bpf_for_each */ + +#ifndef bpf_for +/* bpf_for(i, start, end) proves to verifier that i is in [start, end) */ +#define bpf_for(i, start, end) for ( \ + /* initialize and define destructor */ \ + struct bpf_iter ___it __attribute__((cleanup(bpf_iter_num_destroy))), \ + /* ___p pointer is necessary to call bpf_iter_num_new() *once* to init ___it */ \ + *___p = (bpf_iter_num_new(&___it, (start), (end)), \ + /* this is a workaround for Clang bug: it currently doesn't emit BTF */ \ + /* for bpf_iter_num_destroy when used from cleanup() attribute */ \ + (void)bpf_iter_num_destroy, (void *)0); \ + ({ \
Quoted 8 lines
tools/testing/selftests/bpf/progs/bpf_misc.h line 134
Quoted 4 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +4
-0+/* iteration step */ \ +int *___t =bpf_iter_num_next (&___it); \ +/* termination and bounds check */ \ + (___t && ((i) = *___t, i >= (start ) && i < (end))); \The i >= (start) && i < (end) is necessary to make sure that the verifier tightens the range of 'i' inside the body of the loop and
when the program does arr[i] access the verifier will know that 'i' is within bounds, right?
yes, it feels like a common pattern, but I was contemplating to add bpf_for_uncheck() where we "expose" i value, but don't do check. I decided to keep it simple, as most examples actually required bounds checks anyways. And for cases where we don't, often bpf_repeat() suffices. One other way would be to expose i from bpf_repeat(), just no checks.
One restriction with this approach is that I can't define both struct bpf_iter __it and int i inside for loop, so cur/i has to be declared and passed into bpf_for/bpf_for_each by user explicitly. So for bpf_repeat() to expose i would require always doing:
int i;
bpf_repeat(i, 100) { /* i is set to 0, 1, ..., 99 */ }
which, if you don't care about iteration number, is a bit of waste. So don't know, I'm undecided on bpf_repeat with i.
Quoted 2 lines
In such case should we add
__builtin_constant_p()check for 'start' and 'end' ?
that seems to defy the purpose, as if you know start/end statically, you might as well just write either unrolled loop or bounded for() loop
Quoted 4 lines
int arr[100];
if (var < 100)
bpf_for(i, 0, global_var)sum += arr[i];
will fail the verifier and the users might complain of dumb verifier.
but I'm not following this example, so maybe the answer to above would be different if I would. What's var and global_var? Are they supposed to be the same thing? If yes, why would that bpf_for() loop fail?
I suspect you are conflating the other pattern I pointed out with:
int cnt = 0;
bpf_for_each(...) {
if (cnt++ > 100)
break; }
It's different, as cnt comes from outside the loop and is updated on each iteration. While for
bpf_for(i, 0, var) {
if (i > 100)
break; }
it should work fine, as i is originally unknowable, then narrowed to *a range* [0, 99]. But that [0, 99] knowledge is part of "inner loop body" state, so it will still converge as it's going to be basically ignored during the equivalence check on next bpf_iter_num_next() (old state didn't know about i yet).
Quoted 4 lines
Also if start and end are variables they potentially can change between
bpf_iter_num_new()and in each iteration of the loop.__builtin_constant_p()might be too restrictive.
yep, I think so
Quoted 1 line
May be read start/end once, at least?
I can't do that, as for() allows only one type of variables to be defined (note *___p hack as well), so there is no place to remember start/end, unfortunately...
So it's a tradeoff. I can drop range validation, but then every example and lots of production code would be re-checking these conditions.
Quoted 6 lines
Quoted 6 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +5
-0+ }); \ +/* nothing here */ \ +) +#endif /* bpf_for */ +
Re: [PATCH bpf-next 15/17] selftests/bpf: add bpf_for_each(), bpf_for(), and bpf_repeat() macros
Quoted 132 lines · Andrii Nakryiko
Quoted 121 lines · Alexei Starovoitov
Quoted 119 lines · Andrii Nakryiko
Add
bpf_for_each(),bpf_for()andbpf_repeat()macros that make writing open-coded iterator-based loops much more convenient and natural. These macro utilize cleanup attribute to ensure proper destruction of the iterator and thanks to that manage to provide an ergonomic very close to C language for construct. Typical integer 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 mean as a simple "repeat action N times":
bpf_repeat(N){ /* whatever */ }Note that break and continue 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 (right now hypothetical) bpf_iter_cgroup_{new,next,destroy}() functions to form a loop over cgroups, where
some, input, argsare passed verbatim into constructor asbpf_iter_cgroup_new(&it, some, input, args).As a demonstration, add pyperf variant based on
bpf_for()loop.Also clean up few tests that either included
bpf_misc.hheader unnecessarily from user-space or included it before any common types are defined.Signed-off-by Andrii Nakryiko <[email protected]>--- .../bpf/prog_tests/bpf_verif_scale.c | 6 ++ .../bpf/prog_tests/uprobe_autoattach.c | 1 - tools/testing/selftests/bpf/progs/bpf_misc.h | 76 +++++++++++++++++++ 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, 101 insertions(+), 10 deletions(-) create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_iter.ctools/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 +26
-0@@ -75,5 +75,81 @@#define FUNC_REG_ARG_CNT 5#endif +struct bpf_iter ; + +extern int bpf_iter_num_new(struct bpf_iter *it__uninit, int start, int end) __ksym; +extern int *bpf_iter_num_next (struct bpf_iter *it) __ksym; +extern void bpf_iter_num_destroy(struct bpf_iter *it) __ksym; + +#ifndef bpf_for_each +/* bpf_for_each(iter_kind, elem, args...) provides generic construct for using BPF +* open-coded iterators without having to write mundane explicit low-level +* loop. Instead, it provides for()-like generic construct that can be used +* pretty naturally. E.g., for some hypothetical cgroup iterator, you'd write: +* +* struct cgroup *cg, *parent_cg = <...>; +* +* bpf_for_each(cgroup, cg, parent_cg, CG_ITER_CHILDREN) { +* bpf_printk("Child cgroup id = %d", cg->cgroup_id); +* if (cg->cgroup_id == 123) +* break; +* } +* +* I.e., it looks almost like high-level for each loop in other languages, +* supports continue/break, and is verifiable by BPF verifier. +* +* For iterating integers, the difference betwen bpf_for_each(num, i, N, M) +* and bpf_for(i, N, M) is in that bpf_for() provides additional proof to +* verifier that i is in [N, M) range, and in bpf_for_each() case i is `int Quoted 8 lines
tools/testing/selftests/bpf/progs/bpf_misc.h line 108
Quoted 5 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +5
-0+* *`, not just `int`. So for integers bpf_for() is more convenient. +*/ +#define bpf_for_each(type, cur, args...) for ( \ + /* initialize and define destructor */ \ + struct bpf_iter ___it __attribute__((cleanup(bpf_iter_##type##_destroy))), \We should probably say somewhere that it requires C99 with some flag that allows declaring variables inside the loop.
Quoted 5 lines
yes, I'll add a comment. I think cleanup attribute isn't standard as well, I'll mention it. This shouldn't be restrictive, though, as we expect very modern Clang (or eventually GCC), which definitely will support all of that. And I feel like most people don't restrict their BPF-side code to strict C89 anyways.
yep. No UX concerns. A comment to manage expectations should be enough.
Quoted 4 lines
Quoted 3 lines
Also what are the rules for attr(cleanup()).
When does it get called?
Quoted 8 lines
From GCC documentation:
Quoted 1 line
The cleanup attribute runs a function when the variable goes out of scope.
So given
___itis bound to for loop, any code path that leads to loop exit (so, when condition turns false or *breaking* out of the loop, which is why I use cleanup, this was a saving grace for this approach to work at all).
+1
Quoted 58 lines
Quoted 2 lines
My understanding that the visibility of
___itis only withinfor()body.right
Quoted 5 lines
So when the prog does:
bpf_for(i, 0, 10)sum += i;bpf_for(i, 0, 10)sum += i;the compiler should generate
bpf_iter_num_destroyright after eachbpf_for()?Conceptually, yes, but see the note about breaking out of the loop above. How actual assembly code is generated is beyond our control. If the compiler generates multiple separate code paths, each with its own destroy, that's fine as well. No assumptions are made in the verifier, we just need to see one bpf_iter_<type>_destroy() for each instance of iterator.
Quoted 1 line
Or will it group them at the end of function body and destroy all iterators ?
That would be a bug, as documentation states that clean up happens as soon as a variable goes out of scope. Delaying clean up could result in program logic bugs. I.e., we rely on destructors to be called as soon as possible.
Quoted 1 line
Will compiler reuse the stack space used by
___itin case there are multiple bpf_for-s ?That's the question to compiler developers, but I'd assume that, yes, it should. Why not?
And looking at, for example,
iter_pass_iter_ptr_to_subprogwhich has 4 sequentialbpf_for()loops:0000000000002328 <
iter_pass_iter_ptr_to_subprog>:1125: bf a6 00 00 00 00 00 00 r6 = r10 1126: 07 06 00 00 28 ff ff ff r6 += -216 <-- THIS IS ITER 1127: bf 61 00 00 00 00 00 00 r1 = r6 1128: b4 02 00 00 00 00 00 00 w2 = 0 1129: b4 03 00 00 10 00 00 00 w3 = 16 1130: 85 10 00 00 ff ff ff ff call -1 0000000000002350: R_BPF_64_32 bpf_iter_num_new 1131: bf a7 00 00 00 00 00 00 r7 = r10 1132: 07 07 00 00 c0 ff ff ff r7 += -64 1133: bf 61 00 00 00 00 00 00 r1 = r6 1134: bf 72 00 00 00 00 00 00 r2 = r7 1135: b4 03 00 00 10 00 00 00 w3 = 16 1136: b4 04 00 00 02 00 00 00 w4 = 2 1137: 85 10 00 00 53 00 00 00 call 83 0000000000002388: R_BPF_64_32 .text 1138: bf 61 00 00 00 00 00 00 r1 = r6 1139: 85 10 00 00 ff ff ff ff call -1 0000000000002398: R_BPF_64_32 bpf_iter_num_destroy 1140: bf 61 00 00 00 00 00 00 r1 = r6 <<--- HERE WE REUSE 1141: b4 02 00 00 00 00 00 00 w2 = 0 1142: b4 03 00 00 20 00 00 00 w3 = 32 1143: 85 10 00 00 ff ff ff ff call -1 00000000000023b8: R_BPF_64_32 bpf_iter_num_new
Quoted 2 lines
Note that r6 is set to fp-216 and is just reused as is for second
bpf_forloop (secondbpf_iter_num_new) call.
Great. Thanks for checking. I was worried that attr(cleanup) will force compiler to think that different objects cannot reuse the stack slots which will lead to stack exhaustion. Especially with 24-bytes bpf_iter-s and our tiny 512 limit.
Quoted 44 lines
Quoted 23 lines
Quoted 23 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +22
-0+/* ___p pointer is just to call bpf_iter_##type##_new() *once* to init ___it */ \ + *___p = (bpf_iter_##type##_new(&___it, ##args), \ + /* this is a workaround for Clang bug: it currently doesn't emit BTF */ \ +/* for bpf_iter_##type##_destroy when used from cleanup() attribute */ \ + (void)bpf_iter_##type##_destroy, (void *)0); \ + /* iteration and termination check */ \ + ((cur = bpf_iter_##type##_next(&___it))); \ +/* nothing here */ \ +) +#endif /* bpf_for_each */ + +#ifndef bpf_for +/* bpf_for(i, start, end) proves to verifier that i is in [start, end) */ +#define bpf_for(i, start, end) for ( \ + /* initialize and define destructor */ \ + struct bpf_iter ___it __attribute__((cleanup(bpf_iter_num_destroy))), \ + /* ___p pointer is necessary to call bpf_iter_num_new() *once* to init ___it */ \ + *___p = (bpf_iter_num_new(&___it, (start), (end)), \ + /* this is a workaround for Clang bug: it currently doesn't emit BTF */ \ + /* for bpf_iter_num_destroy when used from cleanup() attribute */ \ + (void)bpf_iter_num_destroy, (void *)0); \ + ({ \Quoted 8 lines
tools/testing/selftests/bpf/progs/bpf_misc.h line 134
Quoted 4 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +4
-0+/* iteration step */ \ +int *___t =bpf_iter_num_next (&___it); \ +/* termination and bounds check */ \ + (___t && ((i) = *___t, i >= (start ) && i < (end))); \The i >= (start) && i < (end) is necessary to make sure that the verifier tightens the range of 'i' inside the body of the loop and
when the program does arr[i] access the verifier will know that 'i' is within bounds, right?yes, it feels like a common pattern, but I was contemplating to add
bpf_for_uncheck()where we "expose" i value, but don't do check. I decided to keep it simple, as most examples actually required bounds checks anyways. And for cases where we don't, oftenbpf_repeat()suffices. One other way would be to expose i frombpf_repeat(), just no checks.One restriction with this approach is that I can't define both
struct bpf_iter __itandint iinside for loop, so cur/i has to be declared and passed into bpf_for/bpf_for_each by user explicitly. So forbpf_repeat()to expose i would require always doing:
Quoted 6 lines
int i;
bpf_repeat(i, 100){ /* i is set to 0, 1, ..., 99 */ }which, if you don't care about iteration number, is a bit of waste. So don't know, I'm undecided on
bpf_repeatwith i.
It feels that the proposed bpf_repeat() without 'i' is cleaner.
Quoted 7 lines
Quoted 2 lines
In such case should we add
__builtin_constant_p()check for 'start' and 'end' ?that seems to defy the purpose, as if you know start/end statically, you might as well just write either unrolled loop or bounded
for()loop
Quoted 8 lines
Quoted 4 lines
int arr[100];
if (var < 100)
bpf_for(i, 0, global_var)sum += arr[i];
will fail the verifier and the users might complain of dumb verifier.but I'm not following this example, so maybe the answer to above would be different if I would. What's var and
global_var?
typo. I meant the same var in both places.
Quoted 31 lines
Are they supposed
to be the same thing? If yes, why would thatbpf_for()loop fail?I suspect you are conflating the other pattern I pointed out with:
int cnt = 0;
bpf_for_each(...) { if (cnt++ > 100) break; }It's different, as cnt comes from outside the loop and is updated on each iteration. While for
bpf_for(i, 0, var) { if (i > 100) break; }it should work fine, as i is originally unknowable, then narrowed to *a range* [0, 99]. But that [0, 99] knowledge is part of "inner loop body" state, so it will still converge as it's going to be basically ignored during the equivalence check on next
bpf_iter_num_next()(old state didn't know about i yet).Quoted 4 lines
Also if start and end are variables they potentially can change between
bpf_iter_num_new()and in each iteration of the loop.__builtin_constant_p()might be too restrictive.
Quoted 7 lines
yep, I think so
Quoted 1 line
May be read start/end once, at least?
I can't do that, as
for()allows only one type of variables to be defined (note*___phack as well), so there is no place to remember start/end, unfortunately...
I see. Abusing bpf_iter like:
for (struct bpf_iter_num __it, *___p, start_end = (struct bpf_iter_num) {start, end}; is probably too ugly just to READ_ONCE(start).
Especially since bpf_iter_num is opaque.
Please add a comment to warn users that if start/end are variables they better not change during bpf_for().
I guess plain C loop: for (int i = 0; i < j; i++) will go crazy too if 'j' changes. I'm not sure what standard says here.
Whether compiler has to reload 'j' every iteration or not.
Quoted 3 lines
So it's a tradeoff. I can drop range validation, but then every example and lots of production code would be re-checking these conditions.
Understood. Keep it as-is.
Quoted 3 lines
Quoted 3 lines
tools/testing/selftests/bpf/progs/bpf_misc.h line 136
Quoted 3 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +2
-0+ }); \ +/* nothing here */ \
btw that 'nothing here' comment is distracting when reading this macro.
Re: [PATCH bpf-next 15/17] selftests/bpf: add bpf_for_each(), bpf_for(), and bpf_repeat() macros
Quoted 134 lines · Alexei Starovoitov
Quoted 132 lines · Andrii Nakryiko
Quoted 129 lines · Alexei Starovoitov
Quoted 114 lines · Andrii Nakryiko
Add
bpf_for_each(),bpf_for()andbpf_repeat()macros that make writing open-coded iterator-based loops much more convenient and natural. These macro utilize cleanup attribute to ensure proper destruction of the iterator and thanks to that manage to provide an ergonomic very close to C language for construct. Typical integer 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 mean as a simple "repeat action N times":
bpf_repeat(N){ /* whatever */ }Note that break and continue 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 (right now hypothetical) bpf_iter_cgroup_{new,next,destroy}() functions to form a loop over cgroups, where
some, input, argsare passed verbatim into constructor asbpf_iter_cgroup_new(&it, some, input, args).As a demonstration, add pyperf variant based on
bpf_for()loop.Also clean up few tests that either included
bpf_misc.hheader unnecessarily from user-space or included it before any common types are defined.Signed-off-by Andrii Nakryiko <[email protected]>--- .../bpf/prog_tests/bpf_verif_scale.c | 6 ++ .../bpf/prog_tests/uprobe_autoattach.c | 1 - tools/testing/selftests/bpf/progs/bpf_misc.h | 76 +++++++++++++++++++ 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, 101 insertions(+), 10 deletions(-) create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_iter.ctools/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 +21
-0@@ -75,5 +75,81 @@#define FUNC_REG_ARG_CNT 5#endif +struct bpf_iter ; + +extern int bpf_iter_num_new(struct bpf_iter *it__uninit, int start, int end) __ksym; +extern int *bpf_iter_num_next (struct bpf_iter *it) __ksym; +extern void bpf_iter_num_destroy(struct bpf_iter *it) __ksym; + +#ifndef bpf_for_each +/* bpf_for_each(iter_kind, elem, args...) provides generic construct for using BPF +* open-coded iterators without having to write mundane explicit low-level +* loop. Instead, it provides for()-like generic construct that can be used +* pretty naturally. E.g., for some hypothetical cgroup iterator, you'd write: +* +* struct cgroup *cg, *parent_cg = <...>; +* +* bpf_for_each(cgroup, cg, parent_cg, CG_ITER_CHILDREN) { +* bpf_printk("Child cgroup id = %d", cg->cgroup_id); +* if (cg->cgroup_id == 123) +* break; +* } +* +* I.e., it looks almost like high-level for each loop in other languages, tools/testing/selftests/bpf/progs/bpf_misc.h line 108
Quoted 10 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +10
-0+* supports continue/break, and is verifiable by BPF verifier. +* +* For iterating integers, the difference betwen bpf_for_each(num, i, N, M) +* and bpf_for(i, N, M) is in that bpf_for() provides additional proof to +* verifier that i is in [N, M) range, and in bpf_for_each() case i is `int +* *`, not just `int`. So for integers bpf_for() is more convenient. +*/ +#define bpf_for_each(type, cur, args...) for ( \ + /* initialize and define destructor */ \ + struct bpf_iter ___it __attribute__((cleanup(bpf_iter_##type##_destroy))), \We should probably say somewhere that it requires C99 with some flag that allows declaring variables inside the loop.
Quoted 8 lines
Quoted 5 lines
yes, I'll add a comment. I think cleanup attribute isn't standard as well, I'll mention it. This shouldn't be restrictive, though, as we expect very modern Clang (or eventually GCC), which definitely will support all of that. And I feel like most people don't restrict their BPF-side code to strict C89 anyways.
yep. No UX concerns. A comment to manage expectations should be enough.
added
Quoted 33 lines
Quoted 4 lines
Quoted 3 lines
Also what are the rules for attr(cleanup()).
When does it get called?Quoted 8 lines
From GCC documentation:
Quoted 1 line
The cleanup attribute runs a function when the variable goes out of scope.
So given
___itis bound to for loop, any code path that leads to loop exit (so, when condition turns false or *breaking* out of the loop, which is why I use cleanup, this was a saving grace for this approach to work at all).+1
Quoted 18 lines
Quoted 2 lines
My understanding that the visibility of
___itis only withinfor()body.right
Quoted 5 lines
So when the prog does:
bpf_for(i, 0, 10)sum += i;bpf_for(i, 0, 10)sum += i;the compiler should generate
bpf_iter_num_destroyright after eachbpf_for()?Conceptually, yes, but see the note about breaking out of the loop above. How actual assembly code is generated is beyond our control. If the compiler generates multiple separate code paths, each with its own destroy, that's fine as well. No assumptions are made in the verifier, we just need to see one bpf_iter_<type>_destroy() for each instance of iterator.
[...]
Quoted 5 lines
Quoted 5 lines
One restriction with this approach is that I can't define both
struct bpf_iter __itandint iinside for loop, so cur/i has to be declared and passed into bpf_for/bpf_for_each by user explicitly. So forbpf_repeat()to expose i would require always doing:
Quoted 9 lines
Quoted 6 lines
int i;
bpf_repeat(i, 100){ /* i is set to 0, 1, ..., 99 */ }which, if you don't care about iteration number, is a bit of waste. So don't know, I'm undecided on
bpf_repeatwith i.It feels that the proposed
bpf_repeat()without 'i' is cleaner.
agreed, I'm keeping it as is
Quoted 13 lines
Quoted 13 lines
Quoted 2 lines
In such case should we add
__builtin_constant_p()check for 'start' and 'end' ?that seems to defy the purpose, as if you know start/end statically, you might as well just write either unrolled loop or bounded
for()loopQuoted 4 lines
int arr[100];
if (var < 100)
bpf_for(i, 0, global_var)sum += arr[i];
will fail the verifier and the users might complain of dumb verifier.
[...]
Quoted 9 lines
Quoted 4 lines
I can't do that, as
for()allows only one type of variables to be defined (note*___phack as well), so there is no place to remember start/end, unfortunately...I see. Abusing
bpf_iterlike:
for (structbpf_iter_num__it,*___p,start_end= (structbpf_iter_num) {start, end}; is probably too ugly just toREAD_ONCE(start).
Especially sincebpf_iter_numis opaque.
yeah, that seems like too much
Quoted 6 lines
Please add a comment to warn users that if start/end are variables they better not change during
bpf_for().
I guess plain C loop: for (int i = 0; i < j; i++) will go crazy too if 'j' changes. I'm not sure what standard says here.
Whether compiler has to reload 'j' every iteration or not.
no idea, but yep, will add a comment
Quoted 5 lines
Quoted 4 lines
So it's a tradeoff. I can drop range validation, but then every example and lots of production code would be re-checking these conditions.
Quoted 7 lines
Understood. Keep it as-is.
Quoted 3 lines
Quoted 3 lines
tools/testing/selftests/bpf/progs/bpf_misc.h
Quoted 3 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +2
-0+ }); \ +/* nothing here */ \btw that 'nothing here' comment is distracting when reading this macro.
ok, dropped this
Andrii Nakryiko
maintainerPATCH 16/17 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.
We also make use of bpf_for(), bpf_for_each(), bpf_repeat() macros.
--- .../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 | 455 +++++++++++ 5 files changed, 1354 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 +455 -0
455 lines not on this page · raw message
Signature · 1 line
2.30.2
Re: [PATCH bpf-next 16/17] selftests/bpf: add iterators tests
Review
Quoted 2 lines · Andrii Nakryiko
(quoted diff) +2
-0+ +#ifdef REAL_TEST
Looks like REAL_TEST is never set.
and all bpf_printk-s in tests are never executed, because the test are 'load-only' to check the verifier?
It looks like all of them can be run (once printks are removed and converted to if-s). That would nicely complement patch 17 runners.
It can be a follow up, of course.
Great stuff overall!
Re: [PATCH bpf-next 16/17] selftests/bpf: add iterators tests
Quoted 7 lines · Alexei Starovoitov
Review
Quoted 2 lines · Andrii Nakryiko
(quoted diff) +2
-0+ +#ifdef REAL_TESTLooks like
REAL_TESTis never set.
Quoted 6 lines
and all bpf_printk-s in tests are never executed, because the test are 'load-only' to check the verifier?
It looks like all of them can be run (once printks are removed and converted to if-s). That would nicely complement patch 17 runners.
Yes, it's a bit sloppy. I used these also as manual tests during development. I did have an ad-hoc test that attaches and triggers these programs. And I just manually looked at printk output in trace_pipe to confirm it does actually work as expected.
And I felt sorry to drop all that, so just added that REAL_TEST hack to make program code simpler (no extra states for those pid conditions), it was simpler to debug verification failures, less states to consider.
I did try to quickly extend RUN_TESTS with the ability to specify a callback that will be called on success, but it's not trivial if we want to preserve skeletons, so I abandoned that effort, trying to save a bit of time. I still want to have RUN_TESTS with ability to specify callback in the form of:
static void on_success(struct <my_skeleton_type> *skel, struct
bpf_program *prog) {
...
}but it needs more thought and macro magic (or something else), so I postponed it and wrote simple number iterator tests in patch #17.
Quoted 1 line
It can be a follow up, of course.
yep, let's keep bpf_printks, as they currently serve as consumers of variables, preventing the compiler from optimizing loops too much. This shouldn't be a problem for verification-only kind of tests. And then with RUN_TESTS() additions, we can actually start executing this.
Quoted 2 lines
Great stuff overall!
Thanks!
Re: [PATCH bpf-next 16/17] selftests/bpf: add iterators tests
Quoted 32 lines · Andrii Nakryiko
Quoted 7 lines · Alexei Starovoitov
Review
Quoted 2 lines · Andrii Nakryiko
(quoted diff) +2
-0+ +#ifdef REAL_TESTLooks like
REAL_TESTis never set.Quoted 6 lines
and all bpf_printk-s in tests are never executed, because the test are 'load-only' to check the verifier?
It looks like all of them can be run (once printks are removed and converted to if-s). That would nicely complement patch 17 runners.
Yes, it's a bit sloppy. I used these also as manual tests during development. I did have an ad-hoc test that attaches and triggers these programs. And I just manually looked at printk output in
trace_pipeto confirm it does actually work as expected.And I felt sorry to drop all that, so just added that
REAL_TESThack to make program code simpler (no extra states for those pid conditions), it was simpler to debug verification failures, less states to consider.I did try to quickly extend
RUN_TESTSwith the ability to specify a callback that will be called on success, but it's not trivial if we want to preserve skeletons, so I abandoned that effort, trying to save a bit of time. I still want to haveRUN_TESTSwith ability to specify callback in the form of:
Quoted 7 lines
static void on_success(struct <
my_skeleton_type> *skel, structbpf_program *prog) { ... }but it needs more thought and macro magic (or something else), so I postponed it and wrote simple number iterator tests in patch #17.
Sounds good to me. Follow up is fine.
Quoted 6 lines
Quoted 1 line
It can be a follow up, of course.
yep, let's keep
bpf_printks, as they currently serve as consumers of variables, preventing the compiler from optimizing loops too much. This shouldn't be a problem for verification-only kind of tests. And then withRUN_TESTS()additions, we can actually start executing this.
+1
Re: [PATCH bpf-next 16/17] selftests/bpf: add iterators tests
In reply to Andrii NakryikoOn Thu, Mar 02, 2023 at 03:50:14PM -0800, Andrii Nakryiko wrote:
SNIP
Quoted 26 lines
tools/testing/selftests/bpf/progs/iters.c new file +26
-0+ +SEC("raw_tp") +__success +int iter_pass_iter_ptr_to_subprog (const void *ctx) +{ +int arr1[16 ], arr2[32 ]; +struct bpf_iter it; +int n, sum1, sum2; + +MY_PID_GUARD (); + +/* fill arr1 */ + n =ARRAY_SIZE (arr1); +bpf_iter_num_new (&it,0 , n); +fill (&it, arr1, n,2 ); +bpf_iter_num_destroy (&it); + +/* fill arr2 */ + n =ARRAY_SIZE (arr2); +bpf_iter_num_new (&it,0 , n); +fill (&it, arr2, n,10 ); +bpf_iter_num_destroy (&it); + +/* sum arr1 */ + n =ARRAY_SIZE (arr1); +bpf_iter_num_new (&it,0 , n);
tools/testing/selftests/bpf/progs/iters.c line 715
Quoted 10 lines
tools/testing/selftests/bpf/progs/iters.c new file +10
-0+ sum1 =sum (&it, arr1, n); +bpf_iter_num_destroy (&it); + +/* sum arr2 */ + n =ARRAY_SIZE (arr2); +bpf_iter_num_new (&it,0 , n); + sum1 =sum (&it, arr2, n); +bpf_iter_num_destroy (&it); + +bpf_printk ("sum1=%d, sum2=%d" , sum1, sum2);
got to remove this to compile it, debug leftover?
jirka
Quoted 5 lines
tools/testing/selftests/bpf/progs/iters.c new file +5
-0+ +return 0 ; +} + +char _license[] SEC("license") = "GPL";
SNIP
Re: [PATCH bpf-next 16/17] selftests/bpf: add iterators tests
Quoted 30 lines · Jiri Olsa
On Thu, Mar 02, 2023 at 03:50:14PM -0800, Andrii Nakryiko wrote:
SNIP
Quoted 25 lines
tools/testing/selftests/bpf/progs/iters.c new file +25
-0+ +SEC("raw_tp") +__success +int iter_pass_iter_ptr_to_subprog (const void *ctx) +{ +int arr1[16 ], arr2[32 ]; +struct bpf_iter it; +int n, sum1, sum2; + +MY_PID_GUARD (); + +/* fill arr1 */ + n =ARRAY_SIZE (arr1); +bpf_iter_num_new (&it,0 , n); +fill (&it, arr1, n,2 ); +bpf_iter_num_destroy (&it); + +/* fill arr2 */ + n =ARRAY_SIZE (arr2); +bpf_iter_num_new (&it,0 , n); +fill (&it, arr2, n,10 ); +bpf_iter_num_destroy (&it); + +/* sum arr1 */ + n =ARRAY_SIZE (arr1);
Quoted 8 lines
tools/testing/selftests/bpf/progs/iters.c line 712
Quoted 8 lines
tools/testing/selftests/bpf/progs/iters.c new file +8
-0+bpf_iter_num_new (&it,0 , n); + sum1 =sum (&it, arr1, n); +bpf_iter_num_destroy (&it); + +/* sum arr2 */ + n =ARRAY_SIZE (arr2); +bpf_iter_num_new (&it,0 , n); + sum1 =sum (&it, arr2, n);
this should have been sum2, not sum1, mechanical mistake
Quoted 5 lines
tools/testing/selftests/bpf/progs/iters.c line 715
Quoted 3 lines
tools/testing/selftests/bpf/progs/iters.c new file +3
-0+bpf_iter_num_destroy (&it); + +bpf_printk ("sum1=%d, sum2=%d" , sum1, sum2);got to remove this to compile it, debug leftover?
nope, sum1->sum2 typo, which wasn't caught because Dave's patch to error out on uninitialized variable reads landed a bit later
I'll fix this in v2, of course.
Quoted 10 lines
jirka
Quoted 5 lines
tools/testing/selftests/bpf/progs/iters.c new file +5
-0+ +return 0 ; +} + +char _license[] SEC("license") = "GPL";SNIP
Andrii Nakryiko
maintainerPATCH 17/17 selftests/bpf: add number iterator tests
In reply to Andrii NakryikoAdd number iterator (bpf_iter_num_{new,next,destroy}()) specific tests, validating its correct handling of various corner cases *at runtime*.
--- .../testing/selftests/bpf/prog_tests/iters.c | 47 ++++ tools/testing/selftests/bpf/progs/iters_num.c | 242 ++++++++++++++++++ 2 files changed, 289 insertions(+) create mode 100644 tools/testing/selftests/bpf/progs/iters_num.c
tools/testing/selftests/bpf/prog_tests/iters.c +47 -0
@@ -6,10 +6,57 @@#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); + +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.30.2
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 4 lines · On Thu, 2 Mar 2023 15:49:58 -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.
Quoted 8 lines
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 patch #15). 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.[...]
Here is the summary with links:
- [bpf-next,01/17] bpf: improve stack slot state printing
https://git.kernel.org/bpf/bpf-next/c/d54e0f6c1adf - [bpf-next,02/17] bpf: improve regsafe() checks for PTR_TO_{MEM,BUF,TP_BUFFER} https://git.kernel.org/bpf/bpf-next/c/567da5d253cd - [bpf-next,03/17] selftests/bpf: enhance align selftest's expected log matching https://git.kernel.org/bpf/bpf-next/c/6f876e75d316 - [bpf-next,04/17] bpf: honor env->test_state_freq flag in is_state_visited() https://git.kernel.org/bpf/bpf-next/c/98ddcf389d1b - [bpf-next,05/17] selftests/bpf: adjust log_fixup's buffer size for proper truncation https://git.kernel.org/bpf/bpf-next/c/fffc893b6bf2 - [bpf-next,06/17] bpf: clean up visit_insn()'s instruction processing https://git.kernel.org/bpf/bpf-next/c/653ae3a874ac - [bpf-next,07/17] bpf: fix visit_insn()'s detection of BPF_FUNC_timer_set_callback helper https://git.kernel.org/bpf/bpf-next/c/c1ee85a9806a - [bpf-next,08/17] bpf: ensure that r0 is marked scratched after any function call https://git.kernel.org/bpf/bpf-next/c/553a64a85c5d - [bpf-next,09/17] bpf: move kfunc_call_arg_meta higher in the file https://git.kernel.org/bpf/bpf-next/c/d0e1ac227945 - [bpf-next,10/17] bpf: mark PTR_TO_MEM as non-null register type https://git.kernel.org/bpf/bpf-next/c/d5271c5b1950 - [bpf-next,11/17] bpf: generalize dynptr_get_spi to be usable for iters https://git.kernel.org/bpf/bpf-next/c/a461f5adf177 - [bpf-next,12/17] bpf: add support for fixed-size memory pointer returns for kfuncs https://git.kernel.org/bpf/bpf-next/c/f4b4eee6169b
- [bpf-next,13/17] bpf: add support for open-coded iterator loops
(no matching commit)
- [bpf-next,14/17] bpf: implement number iterator
(no matching commit)
- [bpf-next,15/17] selftests/bpf: add bpf_for_each(), bpf_for(), and bpf_repeat() macros (no matching commit)
- [bpf-next,16/17] selftests/bpf: add iterators tests
(no matching commit)
- [bpf-next,17/17] selftests/bpf: add number iterator tests
(no matching commit)
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html