bpf: propagate read/precision marks over state graph backedges
Subsystems (4)
Eduard Zingerman
maintainerv2 cover bpf: propagate read/precision marks over state graph backedges
Current loop_entry-based states comparison logic does not handle the following case:
.-> A --. Assume the states are visited in the order A, B, C. | | | Assume that state B reaches a state equivalent to state A. | v v At this point, state C is not processed yet, so state A '-- B C has not received any read or precision marks from C.
As a result, these marks won't be propagated to B.
If B has incomplete marks, it is unsafe to use it in states_equal() checks. This issue was first reported in [1].
This patch-set
--------------
Here is the gist of the algorithm implemented by this patch-set:
- Compute strongly connected components (SCCs) in the program CFG.
- When a verifier state enters an SCC, that state is recorded as the SCC's entry point.
- When a verifier state is found to be equivalent to another (e.g., B to A in the example above), it is recorded as a states-graph backedge.
- Backedges are accumulated per SCC (*).
- When an SCC entry state reaches branches == 0, propagate read and precision marks through the backedges until a fixed point is reached (e.g., from A to B, from C to A, and then again from A to B).
(*) This is an oversimplification, see patch #8 for details.
Unfortunately, this means that commit [2] needs to be reverted, as precision propagation requires access to jump history, and backedges represent history not belonging to env->cur_state.
Details are provided in patch #8; a comment in is_state_visited() explains most of the mechanics.
Patch #2 adds a compute_scc() function, which computes SCCs in the program CFG. This function was tested using property-based testing in [3], but it is not included in selftests.
Previous attempt
----------------
A previous attempt to fix this is described in [4]:
1. Within the states loop, states_equal(... RANGE_WITHIN) ignores read and precision marks.
2. For states outside the loop, all registers for states within the loop are marked as read and precise.
This approach led to an 86x regression on the cond_break1 selftest. In that test, one loop was followed by another, and a certain variable was incremented in the second loop. This variable was marked as precise due to rule (2), which hindered convergence in the first loop.
After some off-list discussion, it was decided that this might be a typical case and such regressions are undesirable.
This patch-set avoids such eager precision markings.
Alternatives
------------
Another option is to associate a mask of read/written/precise stack slots with each instruction. This mask can be populated during verifier states exploration. Upon reaching an EXIT instruction or an equivalent state, the accumulated masks can be used to propagate read/written/precise bits across the program's control flow graph using an analysis similar to use-def.
Unfortunately, a naive implementation of this approach [5] results in a 10x regression in veristat for some sched_ext programs due to the inability to express the must-write property. This issue requires further investigation.
Changes in verification performance
-----------------------------------
There are some veristat regressions when comparing with master using selftests and sched_ext BPF binaries. The comparison is done using master from [6] and this patch-set from [7] where memory accounting logic is added to veristat.
========= selftests: master vs patch-set =========
File Program Insns Peak memory (KiB) ------------------------------- ----------------------------------- ----- ---- ---------------- ---- ----- ---------------- arena_list.bpf.o arena_list_add 374 406 +32 (+8.56%) 0 0 +0 (+0.00%) dynptr_success.bpf.o test_copy_from_user_str_dynptr 268 284 +16 (+5.97%) 768 1024 +256 (+33.33%) dynptr_success.bpf.o test_probe_read_kernel_dynptr 994 1101 +107 (+10.76%) 1024 1240 +216 (+21.09%) dynptr_success.bpf.o test_probe_read_user_dynptr 1000 1107 +107 (+10.70%) 1024 1240 +216 (+21.09%) iters.bpf.o checkpoint_states_deletion 1211 1216 +5 (+0.41%) 512 1288 +776 (+151.56%) iters.bpf.o clean_live_states 588 620 +32 (+5.44%) 256 764 +508 (+198.44%) pyperf600_iter.bpf.o on_event 2591 5929 +3338 (+128.83%) 4648 11320 +6672 (+143.55%)
Total progs: 3600
Old success: 2084
New success: 2084
total_insns diff min : 0.00 % total_insns diff max : 128.83 % total_insns abs max old : 837,487 total_insns abs max new : 837,487 0 .. 5 %: 3592 5 .. 15 %: 6 20 .. 30 %: 1 125 .. 130 %: 1
mem_peak diff min : -100.00 %mem_peak diff max : 198.44 %mem_peak abs max old : 269,312 KiBmem_peak abs max new : 269,312 KiB
-100 .. -95 %: 63 -60 .. -50 %: 1 -10 .. 0 %: 20 0 .. 5 %: 3413 5 .. 15 %: 6 20 .. 30 %: 4 30 .. 40 %: 7 40 .. 50 %: 1 50 .. 60 %: 3 60 .. 70 %: 1 140 .. 150 %: 1 150 .. 160 %: 1 195 .. 200 %: 1
0 -> something: 78
========= scx: master vs patch-set =========
Program Insns Peak memory (KiB) ------------------------ ----- ----- --------------- ----- ----- ----------------- arena_topology_node_init 2129 2391 +262 (+12.31%) 768 768 +0 (+0.00%) arena_topology_node_init 2129 2391 +262 (+12.31%) 768 768 +0 (+0.00%) arena_topology_print 591 826 +235 (+39.76%) 256 256 +0 (+0.00%) arena_topology_print 591 826 +235 (+39.76%) 256 256 +0 (+0.00%) chaos_init 4261 5090 +829 (+19.46%) 2540 3032 +492 (+19.37%) lavd_cpu_offline 5074 5706 +632 (+12.46%) 3940 6304 +2364 (+60.00%) lavd_cpu_online 5074 5706 +632 (+12.46%) 3940 6304 +2364 (+60.00%) lavd_dispatch 41769 47578 +5809 (+13.91%) 6208 29200 +22992 (+370.36%) lavd_enqueue 24190 27749 +3559 (+14.71%) 22740 42872 +20132 (+88.53%) lavd_init 6748 7474 +726 (+10.76%) 5096 6864 +1768 (+34.69%) lavd_select_cpu 27243 30802 +3559 (+13.06%) 26056 45048 +18992 (+72.89%) layered_dispatch 8909 13295 +4386 (+49.23%) 7976 18028 +10052 (+126.03%) layered_dump 1890 2097 +207 (+10.95%) 2036 3036 +1000 (+49.12%) layered_init 4149 4531 +382 (+9.21%) 2716 2896 +180 (+6.63%) layered_runnable 2566 2601 +35 (+1.36%) 748 1244 +496 (+66.31%) p2dq_init 3640 4474 +834 (+22.91%) 2004 2504 +500 (+24.95%) refresh_layer_cpumasks 735 1048 +313 (+42.59%) 256 756 +500 (+195.31%) rusty_init_task 31104 31104 +0 (+0.00%) 2164 2368 +204 (+9.43%) rusty_select_cpu 1110 1110 +0 (+0.00%) 768 1004 +236 (+30.73%)
tp_cgroup_attach_task 149 203 +54 (+36.24%) 0 0 +0 (+0.00%)
Total progs: 147 Old success: 134 New success: 134 total_insns diff min : 0.00 % total_insns diff max : 49.23 % total_insns abs max old : 72,434 total_insns abs max new : 72,434 0 .. 5 %: 132 5 .. 15 %: 9 15 .. 25 %: 2 35 .. 45 %: 3 45 .. 50 %: 1
mem_peak diff min : -0.95 % mem_peak diff max : 370.36 % mem_peak abs max old : 26,056 KiB mem_peak abs max new : 45,048 KiB -5 .. 0 %: 4 0 .. 5 %: 128 5 .. 15 %: 2 15 .. 25 %: 2 30 .. 40 %: 2 45 .. 55 %: 1 60 .. 70 %: 3 70 .. 80 %: 1 85 .. 95 %: 1 125 .. 135 %: 1 195 .. 205 %: 1 370 .. 375 %: 1
Changelog
---------
v1: https://lore.kernel.org/bpf/[email protected]/
v1 -> v2:
- Rebase
- added mem_peak statistics (Alexei)
- selftests: fixed comments and removed useless r7 assignments (Yonghong)
Links
-----
[1] https://lore.kernel.org/bpf/[email protected]/
[2] commit 96a30e469ca1 ("bpf: use common instruction history across all states")
[3] https://github.com/eddyz87/scc-test
[4] https://lore.kernel.org/bpf/[email protected]/
[5] https://github.com/eddyz87/bpf/tree/propagate-read-and-precision-in-cfg
[6] https://github.com/eddyz87/bpf/tree/veristat-memory-accounting
[7] https://github.com/eddyz87/bpf/tree/scc-accumulate-backedges
Eduard Zingerman (11):
Revert "bpf: use common instruction history across all states"
bpf: compute SCCs in program control flow graph
bpf: frame_insn_idx() utility function
bpf: starting_state parameter for __mark_chain_precision()
bpf: set 'changed' status if propagate_precision() did any updates
bpf: set 'changed' status if propagate_liveness() did any updates
bpf: move REG_LIVE_DONE check to clean_live_states()
bpf: propagate read/precision marks over state graph backedges
bpf: remove {update,get}_loop_entry functions
bpf: include backedges in peak_states stat selftests/bpf: tests with a loop state missing read/precision mark
include/linux/bpf_verifier.h | 77 +- kernel/bpf/verifier.c | 970 +++++++++++++++------- tools/testing/selftests/bpf/progs/iters.c | 277 ++++++ 3 files changed, 998 insertions(+), 326 deletions(-)
Signature · 1 line
2.48.1
Eduard Zingerman
maintainerPATCH v2 1/11 Revert "bpf: use common instruction history across all states"
This reverts commit 96a30e469ca1d2b8cc7811b40911f8614b558241. Next patches in the series modify propagate_precision() to allow arbitrary starting state. Precision propagation requires access to jump history, and arbitrary states represent history not belonging to env->cur_state.
--- include/linux/bpf_verifier.h | 19 +++---- kernel/bpf/verifier.c | 107 ++++++++++++++++++----------------- 2 files changed, 63 insertions(+), 63 deletions(-)
include/linux/bpf_verifier.h +8 -11
@@ -344,7 +344,7 @@ struct bpf_func_state {#define MAX_CALL_FRAMES 8 -/* instruction history flags, used in bpf_insn_hist_entry.flags field */ +/* instruction history flags, used in bpf_jmp_history_entry.flags field */ enum {/* instruction references stack slot through PTR_TO_STACK register; * we also store stack's frame number in lower 3 bits (MAX_CALL_FRAMES is 8)
@@ -366,7 +366,7 @@ enum {static_assert (INSN_F_FRAMENO_MASK +1 >=MAX_CALL_FRAMES );static_assert (INSN_F_SPI_MASK +1 >=MAX_BPF_STACK /8 ); -struct bpf_insn_hist_entry { +struct bpf_jmp_history_entry {u32 idx;/* insn idx can't be bigger than 1 million */ u32 prev_idx :20 ;
@@ -459,14 +459,13 @@ struct bpf_verifier_state {* See get_loop_entry() for more information. */ struct bpf_verifier_state *loop_entry; -/* Sub-range of env->insn_hist[] corresponding to this state's -* instruction history. -* Backtracking is using it to go from last to first. -* For most states instruction history is short, 0-3 instructions. +/* jmp history recorded from first to last. +* backtracking is using it to go from last to first. +* For most states jmp_history_cnt is [0-3]. * For loops can go up to ~40. */ -u32 insn_hist_start; -u32 insn_hist_end; +struct bpf_jmp_history_entry *jmp_history; +u32 jmp_history_cnt;u32 dfs_depth;u32 callback_unroll_depth;u32 may_goto_depth;
@@ -775,9 +774,7 @@ struct bpf_verifier_env {int cur_postorder; } cfg;struct backtrack_state bt; -struct bpf_insn_hist_entry *insn_hist; -struct bpf_insn_hist_entry *cur_hist_ent; -u32 insn_hist_cap; +struct bpf_jmp_history_entry *cur_hist_ent;u32 pass_cnt;/* number of times do_check() was called */ u32 subprog_cnt;/* number of instructions analyzed by the verifier */
kernel/bpf/verifier.c +55 -52
264 lines not on this page · raw message
Signature · 1 line
2.48.1
Eduard Zingerman
maintainerPATCH v2 2/11 bpf: compute SCCs in program control flow graph
In reply to Eduard ZingermanCompute strongly connected components in the program CFG. Assign an SCC number to each instruction, recorded in env->insn_aux[*].scc. Use Tarjan's algorithm for SCC computation adapted to run non-recursively.
For debug purposes print out computed SCCs as a part of full program dump in compute_live_registers() at log level 2, e.g.:
func#0 @0
Live regs before insn:
0: .......... (b4) w6 = 10
2 1: ......6... (18) r1 = 0xffff88810bbb5565
2 3: .1....6... (b4) w2 = 2
2 4: .12...6... (85) call bpf_trace_printk#6
2 5: ......6... (04) w6 += -1
2 6: ......6... (56) if w6 != 0x0 goto pc-6
7: .......... (b4) w6 = 5
1 8: ......6... (18) r1 = 0xffff88810bbb5567
1 10: .1....6... (b4) w2 = 2
1 11: .12...6... (85) call bpf_trace_printk#6
1 12: ......6... (04) w6 += -1
1 13: ......6... (56) if w6 != 0x0 goto pc-6
14: .......... (b4) w0 = 0
15: 0......... (95) exit ^^^
SCC number for the instruction
--- include/linux/bpf_verifier.h | 5 + kernel/bpf/verifier.c | 182 +++++++++++++++++++++++++++++++++++ 2 files changed, 187 insertions(+)
include/linux/bpf_verifier.h +5 -0
@@ -608,6 +608,11 @@ struct bpf_insn_aux_data {* accepts callback function as a parameter. */ bool calls_callback; +/* +* CFG strongly connected component this instruction belongs to, +* zero if it is a singleton SCC. +*/ +u32 scc;/* registers alive before this instruction. */ u16 live_regs_before; };
kernel/bpf/verifier.c +182 -0
200 lines not on this page · raw message
Signature · 1 line
2.48.1
Eduard Zingerman
maintainerPATCH v2 3/11 bpf: frame_insn_idx() utility function
In reply to Eduard ZingermanA function to return IP for a given frame in a call stack of a state. Will be used by a next patch.
The state->insn_idx = env->insn_idx; assignment in the do_check() allows to use frame_insn_idx with env->cur_state.
At the moment bpf_verifier_state->insn_idx is set when new cached state is added in is_state_visited() and accessed only in the contexts when the state is already in the cache. Hence this assignment does not change verifier behaviour.
--- kernel/bpf/verifier.c | 13 ++++++++++--- 1 file changed, 10 insertions(+), 3 deletions(-)
kernel/bpf/verifier.c +10 -3
@@ -1963,6 +1963,14 @@ static void update_loop_entry(struct bpf_verifier_env *env, } } +/* Return IP for a given frame in a call stack */ +static u32 frame_insn_idx (struct bpf_verifier_state *st,u32 frame) +{ +return frame == st->curframe + ? st->insn_idx + : st->frame[frame +1 ]->callsite; +} +static void update_branch_counts (struct bpf_verifier_env *env,struct bpf_verifier_state *st) {struct bpf_verifier_state_list *sl =NULL , *parent_sl;
@@ -18775,9 +18783,7 @@ static bool states_equal(struct bpf_verifier_env *env,* and all frame states need to be equivalent */ for (i =0 ; i <= old->curframe; i++) { - insn_idx = i == old->curframe - ? env->insn_idx - : old->frame[i +1 ]->callsite; + insn_idx =frame_insn_idx (old, i);if (old->frame[i]->callsite != cur->frame[i]->callsite)return false;if (!func_states_equal (env, old->frame[i], cur->frame[i], insn_idx, exact))
@@ -19470,6 +19476,7 @@ static int do_check(struct bpf_verifier_env *env) } state->last_insn_idx = env->prev_insn_idx; + state->insn_idx = env->insn_idx;if (is_prune_point (env, env->insn_idx)) { err =is_state_visited (env, env->insn_idx);
Signature · 1 line
2.48.1
Eduard Zingerman
maintainerPATCH v2 4/11 bpf: starting_state parameter for __mark_chain_precision()
In reply to Eduard ZingermanAllow mark_chain_precision() to run from an arbitrary starting state by replacing direct references to env->cur_state with a parameter.
--- kernel/bpf/verifier.c | 24 +++++++++++++----------- 1 file changed, 13 insertions(+), 11 deletions(-)
kernel/bpf/verifier.c +13 -11
@@ -4664,12 +4664,13 @@ static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_* mark_all_scalars_imprecise() to hopefully get more permissive and generic * finalized states which help in short circuiting more future states. */ -static int __mark_chain_precision (struct bpf_verifier_env *env,int regno) +static int __mark_chain_precision (struct bpf_verifier_env *env, +struct bpf_verifier_state *starting_state,int regno) { +struct bpf_verifier_state *st = starting_state;struct backtrack_state *bt = &env->bt; -struct bpf_verifier_state *st = env->cur_state;int first_idx = st->first_insn_idx; -int last_idx = env->insn_idx; +int last_idx = starting_state->insn_idx;int subseq_idx =-1 ;struct bpf_func_state *func;struct bpf_reg_state *reg;
@@ -4680,7 +4681,7 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)return 0 ;/* set frame number from which we are starting to backtrack */ -bt_init (bt, env->cur_state->curframe); +bt_init (bt, starting_state->curframe);/* Do sanity checks against current state of register and/or stack * slot, but don't set precise flag in current state, as precision
@@ -4744,7 +4745,7 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno) err =backtrack_insn (env, i, subseq_idx, hist, bt); }if (err == -ENOTSUPP ) { -mark_all_scalars_precise (env, env->cur_state); +mark_all_scalars_precise (env, starting_state);bt_reset (bt);return 0 ; }else if (err) {
@@ -4832,7 +4833,7 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)* fallback to marking all precise */ if (!bt_empty (bt)) { -mark_all_scalars_precise (env, env->cur_state); +mark_all_scalars_precise (env, starting_state);bt_reset (bt); }
@@ -4841,15 +4842,16 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)int mark_chain_precision (struct bpf_verifier_env *env,int regno) { -return __mark_chain_precision (env, regno); +return __mark_chain_precision (env, env->cur_state, regno); }/* mark_chain_precision_batch() assumes that env->bt is set in the caller to * desired reg and stack masks across all relevant frames */ -static int mark_chain_precision_batch (struct bpf_verifier_env *env) +static int mark_chain_precision_batch (struct bpf_verifier_env *env, +struct bpf_verifier_state *starting_state) { -return __mark_chain_precision (env,-1 ); +return __mark_chain_precision (env, starting_state,-1 ); }static bool is_spillable_regtype (enum bpf_reg_type type)
@@ -9502,7 +9504,7 @@ static int get_constant_map_key(struct bpf_verifier_env *env,* to prevent pruning on it. */ bt_set_frame_slot (&env->bt, key->frameno, spi); - err =mark_chain_precision_batch (env); + err =mark_chain_precision_batch (env, env->cur_state);if (err <0 )return err;
@@ -18924,7 +18926,7 @@ static int propagate_precision(struct bpf_verifier_env *env,verbose (env,"\n" ); } - err =mark_chain_precision_batch (env); + err =mark_chain_precision_batch (env, env->cur_state);if (err <0 )return err;
Signature · 1 line
2.48.1
Eduard Zingerman
maintainerPATCH v2 5/11 bpf: set 'changed' status if propagate_precision() did any updates
In reply to Eduard ZingermanAdd an out parameter to propagate_precision() to record whether any new precision bits were set during its execution.
--- kernel/bpf/verifier.c | 35 +++++++++++++++++++++++------------ 1 file changed, 23 insertions(+), 12 deletions(-)
kernel/bpf/verifier.c +23 -12
@@ -4665,7 +4665,9 @@ static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_* finalized states which help in short circuiting more future states. */ static int __mark_chain_precision (struct bpf_verifier_env *env, -struct bpf_verifier_state *starting_state,int regno) +struct bpf_verifier_state *starting_state, +int regno, +bool *changed) {struct bpf_verifier_state *st = starting_state;struct backtrack_state *bt = &env->bt;
@@ -4673,13 +4675,14 @@ static int __mark_chain_precision(struct bpf_verifier_env *env,int last_idx = starting_state->insn_idx;int subseq_idx =-1 ;struct bpf_func_state *func; +bool tmp, skip_first = true;struct bpf_reg_state *reg; -bool skip_first = true;int i, fr, err;if (!env->bpf_capable)return 0 ; + changed = changed ?: &tmp;/* set frame number from which we are starting to backtrack */ bt_init (bt, starting_state->curframe);
@@ -4725,8 +4728,10 @@ static int __mark_chain_precision(struct bpf_verifier_env *env,for_each_set_bit (i, mask,32 ) { reg = &st->frame[0 ]->regs[i];bt_clear_reg (bt, i); -if (reg->type ==SCALAR_VALUE ) +if (reg->type ==SCALAR_VALUE ) { reg->precise = true; + *changed = true; + } }return 0 ; }
@@ -4785,10 +4790,12 @@ static int __mark_chain_precision(struct bpf_verifier_env *env,bt_clear_frame_reg (bt, fr, i);continue ; } -if (reg->precise) +if (reg->precise) {bt_clear_frame_reg (bt, fr, i); -else + }else { reg->precise = true; + *changed = true; + } }bitmap_from_u64 (mask,bt_frame_stack_mask (bt, fr));
@@ -4803,10 +4810,12 @@ static int __mark_chain_precision(struct bpf_verifier_env *env,continue ; } reg = &func->stack[i].spilled_ptr; -if (reg->precise) +if (reg->precise) {bt_clear_frame_slot (bt, fr, i); -else + }else { reg->precise = true; + *changed = true; + } }if (env->log.level &BPF_LOG_LEVEL2 ) { fmt_reg_mask(env->tmp_str_buf, TMP_STR_BUF_LEN,
@@ -4842,7 +4851,7 @@ static int __mark_chain_precision(struct bpf_verifier_env *env,int mark_chain_precision (struct bpf_verifier_env *env,int regno) { -return __mark_chain_precision (env, env->cur_state, regno); +return __mark_chain_precision (env, env->cur_state, regno,NULL ); }/* mark_chain_precision_batch() assumes that env->bt is set in the caller to
@@ -4851,7 +4860,7 @@ int mark_chain_precision(struct bpf_verifier_env *env, int regno)static int mark_chain_precision_batch (struct bpf_verifier_env *env,struct bpf_verifier_state *starting_state) { -return __mark_chain_precision (env, starting_state,-1 ); +return __mark_chain_precision (env, starting_state,-1 ,NULL ); }static bool is_spillable_regtype (enum bpf_reg_type type)
@@ -18878,7 +18887,9 @@ static int propagate_liveness(struct bpf_verifier_env *env,* propagate them into the current state */ static int propagate_precision (struct bpf_verifier_env *env, -const struct bpf_verifier_state *old) +const struct bpf_verifier_state *old, +struct bpf_verifier_state *cur, +bool *changed) {struct bpf_reg_state *state_reg;struct bpf_func_state *state;
@@ -18926,7 +18937,7 @@ static int propagate_precision(struct bpf_verifier_env *env,verbose (env,"\n" ); } - err =mark_chain_precision_batch (env, env->cur_state); + err =__mark_chain_precision (env, cur,-1 , changed);if (err <0 )return err;
@@ -19249,7 +19260,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)*/ if (is_jmp_point (env, env->insn_idx)) err = err ? :push_jmp_history (env, cur,0 ,0 ); - err = err ? :propagate_precision (env, &sl->state); + err = err ? :propagate_precision (env, &sl->state, cur,NULL );if (err)return err;return 1 ;
Signature · 1 line
2.48.1
Eduard Zingerman
maintainerPATCH v2 6/11 bpf: set 'changed' status if propagate_liveness() did any updates
In reply to Eduard ZingermanAdd an out parameter to propagate_liveness() to record whether any new liveness bits were set during its execution.
--- kernel/bpf/verifier.c | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-)
kernel/bpf/verifier.c +7 -2
@@ -18841,12 +18841,15 @@ static int propagate_liveness_reg(struct bpf_verifier_env *env,*/ static int propagate_liveness (struct bpf_verifier_env *env,const struct bpf_verifier_state *vstate, -struct bpf_verifier_state *vparent) +struct bpf_verifier_state *vparent, +bool *changed) {struct bpf_reg_state *state_reg, *parent_reg;struct bpf_func_state *state, *parent;int i, frame, err =0 ; +bool tmp; + changed = changed ?: &tmp;if (vparent->curframe != vstate->curframe) {WARN (1 ,"propagate_live: parent frame %d current frame %d\n" , vparent->curframe, vstate->curframe);
@@ -18865,6 +18868,7 @@ static int propagate_liveness(struct bpf_verifier_env *env, &parent_reg[i]);if (err <0 )return err; + *changed |= err >0 ;if (err ==REG_LIVE_READ64 )mark_insn_zext (env, &parent_reg[i]); }
@@ -18876,6 +18880,7 @@ static int propagate_liveness(struct bpf_verifier_env *env, state_reg = &state->stack[i].spilled_ptr; err =propagate_liveness_reg (env, state_reg, parent_reg); + *changed |= err >0 ;if (err <0 )return err; }
@@ -19251,7 +19256,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)* they'll be immediately forgotten as we're pruning * this state and will pop a new one. */ - err =propagate_liveness (env, &sl->state, cur); + err =propagate_liveness (env, &sl->state, cur,NULL );/* if previous state reached the exit with precision and * current state is equivalent to it (except precision marks)
Signature · 1 line
2.48.1
Eduard Zingerman
maintainerPATCH v2 7/11 bpf: move REG_LIVE_DONE check to clean_live_states()
In reply to Eduard ZingermanThe next patch would add some relatively heavy-weight operation to clean_live_states(), this operation can be skipped if REG_LIVE_DONE is set. Move the check from clean_verifier_state() to clean_verifier_state() as a small refactoring commit.
--- kernel/bpf/verifier.c | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-)
kernel/bpf/verifier.c +3 -4
@@ -18290,10 +18290,6 @@ static void clean_verifier_state(struct bpf_verifier_env *env, {int i; -if (st->frame[0 ]->regs[0 ].live ®_LIVE_DONE ) -/* all regs in this state in all frames were already marked */ -return ; -for (i =0 ; i <= st->curframe; i++)clean_func_state (env, st->frame[i]); }
@@ -18348,6 +18344,9 @@ static void clean_live_states(struct bpf_verifier_env *env, int insn,if (sl->state.insn_idx != insn || !same_callsites (&sl->state, cur))continue ; +if (sl->state.frame[0 ]->regs[0 ].live ®_LIVE_DONE ) +/* all regs in this state in all frames were already marked */ +continue ;clean_verifier_state (env, &sl->state); } }
Signature · 1 line
2.48.1
Eduard Zingerman
maintainerPATCH v2 8/11 bpf: propagate read/precision marks over state graph backedges
In reply to Eduard ZingermanCurrent loop_entry-based exact states comparison logic does not handle the following case:
.-> A --. Assume the states are visited in the order A, B, C. | | | Assume that state B reaches a state equivalent to state A. | v v At this point, state C is not processed yet, so state A '-- B C has not received any read or precision marks from C.
As a result, these marks won't be propagated to B.
If B has incomplete marks, it is unsafe to use it in states_equal() checks.
This commit replaces the existing logic with the following:
- Strongly connected components (SCCs) are computed over the program's control flow graph (intraprocedurally).
- When a verifier state enters an SCC, that state is recorded as the SCC entry point.
- When a verifier state is found equivalent to another (e.g., B to A in the example), it is recorded as a states graph backedge. Backedges are accumulated per SCC.
- When an SCC entry state reaches branches == 0, read and precision marks are propagated through the backedges (e.g., from A to B, from C to A, and then again from A to B).
To support nested subprogram calls, the entry state and backedge list are associated not with the SCC itself but with an object called bpf_scc_callchain. A callchain is a tuple (callsite*, scc_id), where callsite is the index of a call instruction for each frame except the last.
See the comments added in is_state_visited() and compute_scc_callchain() for more details.
--- include/linux/bpf_verifier.h | 38 +++ kernel/bpf/verifier.c | 454 +++++++++++++++++++++++++++++------ 2 files changed, 423 insertions(+), 69 deletions(-)
include/linux/bpf_verifier.h +38 -0
@@ -459,6 +459,10 @@ struct bpf_verifier_state {* See get_loop_entry() for more information. */ struct bpf_verifier_state *loop_entry; +/* if this state is a backedge state then equal_state +* records cached state to which this state is equal. +*/ +struct bpf_verifier_state *equal_state;/* jmp history recorded from first to last. * backtracking is using it to go from last to first. * For most states jmp_history_cnt is [0-3].
@@ -722,6 +726,37 @@ struct bpf_idset {u32 ids[BPF_ID_MAP_SIZE ]; }; +/* see verifier.c:compute_scc_callchain() */ +struct bpf_scc_callchain { +/* call sites from bpf_verifier_state->frame[*]->callsite leading to this SCC */ +u32 callsites[MAX_CALL_FRAMES -1 ]; +/* last frame in a chain is identified by SCC id */ +u32 scc; +}; + +/* verifier state waiting for propagate_backedges() */ +struct bpf_scc_backedge { +struct bpf_scc_backedge *next; +struct bpf_verifier_state state; +}; + +struct bpf_scc_visit { +struct bpf_scc_callchain callchain; +/* first state in current verification path that entered SCC +* identified by the callchain +*/ +struct bpf_verifier_state *entry_state; +struct bpf_scc_backedge *backedges;/* list of backedges */ +}; + +/* An array of bpf_scc_visit structs sharing tht same bpf_scc_callchain->scc +* but having different bpf_scc_callchain->callsites. +*/ +struct bpf_scc_info { +u32 num_visits; +struct bpf_scc_visit visits[]; +}; +/* single container for all structs * one verifier_env per bpf_check() call */
@@ -818,6 +853,9 @@ struct bpf_verifier_env {char tmp_str_buf[TMP_STR_BUF_LEN ];struct bpf_insn insn_buf[INSN_BUF_SIZE ];struct bpf_insn epilogue_buf[INSN_BUF_SIZE ]; +/* array of pointers to bpf_scc_info indexed by SCC id */ +struct bpf_scc_info **scc_info; +u32 scc_cnt; };static inline struct bpf_func_info_aux *subprog_aux (struct bpf_verifier_env *env,int subprog)
kernel/bpf/verifier.c +385 -69
606 lines not on this page · raw message
Signature · 1 line
2.48.1
Eduard Zingerman
maintainerPATCH v2 9/11 bpf: remove {update,get}_loop_entry functions
In reply to Eduard ZingermanThe previous patch switched read and precision tracking for iterator-based loops from state-graph-based loop tracking to control-flow-graph-based loop tracking.
This patch removes the now-unused update_loop_entry() and get_loop_entry() functions, which were part of the state-graph-based logic.
--- include/linux/bpf_verifier.h | 15 ---- kernel/bpf/verifier.c | 165 +---------------------------------- 2 files changed, 1 insertion(+), 179 deletions(-)
include/linux/bpf_verifier.h +0 -15
@@ -449,16 +449,6 @@ struct bpf_verifier_state {/* first and last insn idx of this verifier state */ u32 first_insn_idx;u32 last_insn_idx; -/* If this state is a part of states loop this field points to some -* parent of this state such that: -* - it is also a member of the same states loop; -* - DFS states traversal starting from initial state visits loop_entry -* state before this state. -* Used to compute topmost loop entry for state loops. -* State loops might appear because of open coded iterators logic. -* See get_loop_entry() for more information. -*/ -struct bpf_verifier_state *loop_entry;/* if this state is a backedge state then equal_state * records cached state to which this state is equal. */
@@ -473,11 +463,6 @@ struct bpf_verifier_state {u32 dfs_depth;u32 callback_unroll_depth;u32 may_goto_depth; -/* If this state was ever pointed-to by other state's loop_entry field -* this flag would be set to true. Used to avoid freeing such states -* while they are still in use. -*/ -u32 used_as_loop_entry; };#define bpf_get_spilled_reg (slot, frame, mask) \
kernel/bpf/verifier.c +1 -164
196 lines not on this page · raw message
Signature · 1 line
2.48.1
Eduard Zingerman
maintainerPATCH v2 10/11 bpf: include backedges in peak_states stat
In reply to Eduard ZingermanCount states accumulated in bpf_scc_visit->backedges in env->peak_states.
--- include/linux/bpf_verifier.h | 2 ++ kernel/bpf/verifier.c | 8 +++++++- 2 files changed, 9 insertions(+), 1 deletion(-)
include/linux/bpf_verifier.h +2 -0
@@ -732,6 +732,7 @@ struct bpf_scc_visit {*/ struct bpf_verifier_state *entry_state;struct bpf_scc_backedge *backedges;/* list of backedges */ +u32 num_backedges; };/* An array of bpf_scc_visit structs sharing tht same bpf_scc_callchain->scc
@@ -821,6 +822,7 @@ struct bpf_verifier_env {u32 longest_mark_read_walk;u32 free_list_size;u32 explored_states_size; +u32 num_backedges;bpfptr_t fd_array;/* bit mask to keep track of whether a register has been accessed
kernel/bpf/verifier.c +7 -1
@@ -1647,7 +1647,7 @@ static void update_peak_states(struct bpf_verifier_env *env) {u32 cur_states; - cur_states = env->explored_states_size + env->free_list_size; + cur_states = env->explored_states_size + env->free_list_size + env->num_backedges; env->peak_states =max (env->peak_states, cur_states); }
@@ -1948,6 +1948,9 @@ static int maybe_exit_scc(struct bpf_verifier_env *env, struct bpf_verifier_statif (env->log.level &BPF_LOG_LEVEL2 )verbose (env,"SCC exit %s\n" ,format_callchain (env, &callchain)); visit->entry_state =NULL ; + env->num_backedges -= visit->num_backedges; + visit->num_backedges =0 ; +update_peak_states (env);return propagate_backedges (env, visit); }
@@ -1976,6 +1979,9 @@ static int add_scc_backedge(struct bpf_verifier_env *env,verbose (env,"SCC backedge %s\n" ,format_callchain (env, &callchain)); backedge->next = visit->backedges; visit->backedges = backedge; + visit->num_backedges++; + env->num_backedges++; +update_peak_states (env);return 0 ; }
Signature · 1 line
2.48.1
Eduard Zingerman
maintainerPATCH v2 11/11 selftests/bpf: tests with a loop state missing read/precision mark
In reply to Eduard ZingermanThe test case absent_mark_in_the_middle_state is equivalent of the following C program:
1: r8 = bpf_get_prandom_u32();
2: r6 = -32;
3: bpf_iter_num_new(&fp[-8], 0, 10);
4: if (unlikely(bpf_get_prandom_u32() == r8))
5: r6 = -31;
6: for (;;) {
7: if (!bpf_iter_num_next(&fp[-8]))
8: break;
9: if (unlikely(bpf_get_prandom_u32() == r8))
10: *(u64 *)(fp + r6) = 7;
11: }
12: bpf_iter_num_destroy(&fp[-8]);
13: return 0;W/o a fix that instructs verifier to ignore branches count for loop entries verification proceeds as follows:
- 1-4, state is {r6=-32,fp-8=active};
- 6, checkpoint A is created with {r6=-32,fp-8=active};
- 7, checkpoint B is created with {r6=-32,fp-8=active},
push state {r6=-32,fp-8=active} from 7 to 9;- 8,12,13, {r6=-32,fp-8=drained}, exit;
- pop state with {r6=-32,fp-8=active} from 7 to 9;
- 9, push state {r6=-32,fp-8=active} from 9 to 10;
- 6, checkpoint C is created with {r6=-32,fp-8=active};
- 7, checkpoint A is hit, no precision propagated for r6 to C;
- pop state {r6=-32,fp-8=active} from 9 to 10;
- 10, state is {r6=-31,fp-8=active}, r6 is marked as read and precise, these marks are propagated to checkpoints A and B (but not C, as it is not the parent of current state;
- 6, {r6=-31,fp-8=active} checkpoint C is hit, because r6 is not
marked precise for this checkpoint;
- the program is accepted, despite a possibility of unaligned u64 stack access at offset -31.
The test case absent_mark_in_the_middle_state2 is similar except the following change:
r8 = bpf_get_prandom_u32();
r6 = -32;
bpf_iter_num_new(&fp[-8], 0, 10);
if (unlikely(bpf_get_prandom_u32() == r8)) {
r6 = -31;
+ jump_into_loop:
+ goto +0;
+ goto loop;
+ }
+ if (unlikely(bpf_get_prandom_u32() == r8))
+ goto jump_into_loop;
+ loop:
for (;;) {
if (!bpf_iter_num_next(&fp[-8]))
break;
if (unlikely(bpf_get_prandom_u32() == r8))
*(u64 *)(fp + r6) = 7;
}
bpf_iter_num_destroy(&fp[-8])
return 0The goal is to check that read/precision marks are propagated to checkpoint created at 'goto +0' that resides outside of the loop.
The test case absent_mark_in_the_middle_state3 is a bit different and is equivalent to the C program below:
int absent_mark_in_the_middle_state3(void)
{
bpf_iter_num_new(&fp[-8], 0, 10)
loop1(-32, &fp[-8])
loop1_wrapper(&fp[-8])
bpf_iter_num_destroy(&fp[-8])
}
int loop1(num, iter)
{
while (bpf_iter_num_next(iter)) {
if (unlikely(bpf_get_prandom_u32()))
*(fp + num) = 7;
}
return 0
}
int loop1_wrapper(iter)
{
r6 = -32;
r8 = bpf_get_prandom_u32();
if (unlikely(bpf_get_prandom_u32() == r8))
r6 = -31;
loop1(r6, iter);
return 0;
}The unsafe state is reached in a similar manner, but the loop is located inside a subprogram that is called from two locations in the main subprogram. This detail is important for exercising bpf_scc_visit->backedges memory management.
--- tools/testing/selftests/bpf/progs/iters.c | 277 ++++++++++++++++++++++ 1 file changed, 277 insertions(+)
tools/testing/selftests/bpf/progs/iters.c +277 -0
@@ -1649,4 +1649,281 @@ int clean_live_states(const void *ctx)return 0 ; } +SEC("?raw_tp") +__flag (BPF_F_TEST_STATE_FREQ) +__failure __msg("misaligned stack access off 0+-31+0 size 8") +__naked int absent_mark_in_the_middle_state (void ) +{ +/* This is equivalent to C program below. +* +* r8 = bpf_get_prandom_u32(); +* r6 = -32; +* bpf_iter_num_new(&fp[-8], 0, 10); +* if (unlikely(bpf_get_prandom_u32() == r8)) +* r6 = -31; +* while (bpf_iter_num_next(&fp[-8])) { +* if (unlikely(bpf_get_prandom_u32() == r8)) +* *(fp + r6) = 7; +* } +* bpf_iter_num_destroy(&fp[-8]) +* return 0 +*/ + asmvolatile ( +"call %[bpf_get_prandom_u32];" +"r8 = r0;" +"r6 = -32;" +"r0 = 0;" +"*(u64 *)(r10 - 16) = r0;" +"r1 = r10;" +"r1 += -8;" +"r2 = 0;" +"r3 = 10;" +"call %[bpf_iter_num_new];" +"call %[bpf_get_prandom_u32];" +"if r0 == r8 goto change_r6_%=;" +"loop_%=:" +"call noop;" +"r1 = r10;" +"r1 += -8;" +"call %[bpf_iter_num_next];" +"if r0 == 0 goto loop_end_%=;" +"call %[bpf_get_prandom_u32];" +"if r0 == r8 goto use_r6_%=;" +"goto loop_%=;" +"loop_end_%=:" +"r1 = r10;" +"r1 += -8;" +"call %[bpf_iter_num_destroy];" +"r0 = 0;" +"exit;" +"use_r6_%=:" +"r0 = r10;" +"r0 += r6;" +"r1 = 7;" +"*(u64 *)(r0 + 0) = r1;" +"goto loop_%=;" +"change_r6_%=:" +"r6 = -31;" +"goto loop_%=;" + : + : __imm(bpf_iter_num_new), +__imm (bpf_iter_num_next), +__imm (bpf_iter_num_destroy), +__imm (bpf_get_prandom_u32) + : __clobber_all + ); +} + +__used __naked +static int noop (void ) +{ + asmvolatile ( +"r0 = 0;" +"exit;" + ); +} + +SEC("?raw_tp") +__flag (BPF_F_TEST_STATE_FREQ) +__failure __msg("misaligned stack access off 0+-31+0 size 8") +__naked int absent_mark_in_the_middle_state2 (void ) +{ +/* This is equivalent to C program below. +* +* r8 = bpf_get_prandom_u32(); +* r6 = -32; +* bpf_iter_num_new(&fp[-8], 0, 10); +* if (unlikely(bpf_get_prandom_u32() == r8)) { +* r6 = -31; +* jump_into_loop: +* goto +0; +* goto loop; +* } +* if (unlikely(bpf_get_prandom_u32() == r8)) +* goto jump_into_loop; +* loop: +* while (bpf_iter_num_next(&fp[-8])) { +* if (unlikely(bpf_get_prandom_u32() == r8)) +* *(fp + r6) = 7; +* } +* bpf_iter_num_destroy(&fp[-8]) +* return 0 +*/ + asmvolatile ( +"call %[bpf_get_prandom_u32];" +"r8 = r0;" +"r6 = -32;" +"r0 = 0;" +"*(u64 *)(r10 - 16) = r0;" +"r1 = r10;" +"r1 += -8;" +"r2 = 0;" +"r3 = 10;" +"call %[bpf_iter_num_new];" +"call %[bpf_get_prandom_u32];" +"if r0 == r8 goto change_r6_%=;" +"call %[bpf_get_prandom_u32];" +"if r0 == r8 goto jump_into_loop_%=;" +"loop_%=:" +"r1 = r10;" +"r1 += -8;" +"call %[bpf_iter_num_next];" +"if r0 == 0 goto loop_end_%=;" +"call %[bpf_get_prandom_u32];" +"if r0 == r8 goto use_r6_%=;" +"goto loop_%=;" +"loop_end_%=:" +"r1 = r10;" +"r1 += -8;" +"call %[bpf_iter_num_destroy];" +"r0 = 0;" +"exit;" +"use_r6_%=:" +"r0 = r10;" +"r0 += r6;" +"r1 = 7;" +"*(u64 *)(r0 + 0) = r1;" +"goto loop_%=;" +"change_r6_%=:" +"r6 = -31;" +"jump_into_loop_%=: " +"goto +0;" +"goto loop_%=;" + : + : __imm(bpf_iter_num_new), +__imm (bpf_iter_num_next), +__imm (bpf_iter_num_destroy), +__imm (bpf_get_prandom_u32) + : __clobber_all + ); +} + +SEC("?raw_tp") +__flag (BPF_F_TEST_STATE_FREQ) +__failure __msg("misaligned stack access off 0+-31+0 size 8") +__naked int absent_mark_in_the_middle_state3 (void ) +{ +/* +* bpf_iter_num_new(&fp[-8], 0, 10) +* loop1(-32, &fp[-8]) +* loop1_wrapper(&fp[-8]) +* bpf_iter_num_destroy(&fp[-8]) +*/ + asmvolatile ( +"r1 = r10;" +"r1 += -8;" +"r2 = 0;" +"r3 = 10;" +"call %[bpf_iter_num_new];" +/* call #1 */ +"r1 = -32;" +"r2 = r10;" +"r2 += -8;" +"call loop1;" +"r1 = r10;" +"r1 += -8;" +"call %[bpf_iter_num_destroy];" +/* call #2 */ +"r1 = r10;" +"r1 += -8;" +"r2 = 0;" +"r3 = 10;" +"call %[bpf_iter_num_new];" +"r1 = r10;" +"r1 += -8;" +"call loop1_wrapper;" +/* return */ +"r1 = r10;" +"r1 += -8;" +"call %[bpf_iter_num_destroy];" +"r0 = 0;" +"exit;" + : + : __imm(bpf_iter_num_new), +__imm (bpf_iter_num_destroy), +__imm (bpf_get_prandom_u32) + : __clobber_all + ); +} + +__used __naked +static int loop1 (void ) +{ +/* +* int loop1(num, iter) { +* r8 = bpf_get_prandom_u32(); +* r6 = num; +* r7 = iter; +* while (bpf_iter_num_next(r7)) { +* if (unlikely(bpf_get_prandom_u32() == r8)) +* *(fp + r6) = 7; +* } +* return 0 +* } +*/ + asmvolatile ( +"r6 = r1;" +"r7 = r2;" +"call %[bpf_get_prandom_u32];" +"r8 = r0;" +"loop_%=:" +"r1 = r7;" +"call %[bpf_iter_num_next];" +"if r0 == 0 goto loop_end_%=;" +"call %[bpf_get_prandom_u32];" +"if r0 == r8 goto use_r6_%=;" +"goto loop_%=;" +"loop_end_%=:" +"r0 = 0;" +"exit;" +"use_r6_%=:" +"r0 = r10;" +"r0 += r6;" +"r1 = 7;" +"*(u64 *)(r0 + 0) = r1;" +"goto loop_%=;" + : + : __imm(bpf_iter_num_next), +__imm (bpf_get_prandom_u32) + : __clobber_all + ); +} + +__used __naked +static int loop1_wrapper (void ) +{ +/* +* int loop1_wrapper(iter) { +* r6 = -32; +* r7 = iter; +* r8 = bpf_get_prandom_u32(); +* if (unlikely(bpf_get_prandom_u32() == r8)) +* r6 = -31; +* loop1(r6, r7); +* return 0; +* } +*/ + asmvolatile ( +"r6 = -32;" +"r7 = r1;" +"call %[bpf_get_prandom_u32];" +"r8 = r0;" +"call %[bpf_get_prandom_u32];" +"if r0 == r8 goto change_r6_%=;" +"loop_%=:" +"r1 = r6;" +"r2 = r7;" +"call loop1;" +"r0 = 0;" +"exit;" +"change_r6_%=:" +"r6 = -31;" +"goto loop_%=;" + : + : __imm(bpf_iter_num_next), +__imm (bpf_get_prandom_u32) + : __clobber_all + ); +} + char _license[] SEC("license") = "GPL";
Signature · 1 line
2.48.1