Revert "bpf: use common instruction history across all states"
Subsystems (4)
Eduard Zingerman
maintainerPATCH v3 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;
@@ -776,9 +775,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.47.1
Eduard Zingerman
maintainerPATCH v3 2/11 bpf: compute SCCs in program control flow graph
Compute 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
@@ -609,6 +609,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.47.1
Eduard Zingerman
maintainerPATCH v3 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
@@ -1964,6 +1964,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;
@@ -18790,9 +18798,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))
@@ -19687,6 +19693,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.47.1
Eduard Zingerman
maintainerPATCH v3 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
@@ -4677,12 +4677,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;
@@ -4693,7 +4694,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
@@ -4757,7 +4758,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) {
@@ -4845,7 +4846,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); }
@@ -4854,15 +4855,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)
@@ -9515,7 +9517,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;
@@ -18939,7 +18941,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.47.1
Eduard Zingerman
maintainerPATCH v3 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
@@ -4678,7 +4678,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;
@@ -4686,13 +4688,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);
@@ -4738,8 +4741,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 ; }
@@ -4798,10 +4803,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));
@@ -4816,10 +4823,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,
@@ -4855,7 +4864,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
@@ -4864,7 +4873,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)
@@ -18893,7 +18902,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;
@@ -18941,7 +18952,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;
@@ -19264,7 +19275,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.47.1
Eduard Zingerman
maintainerPATCH v3 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
@@ -18856,12 +18856,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);
@@ -18880,6 +18883,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]); }
@@ -18891,6 +18895,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; }
@@ -19266,7 +19271,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.47.1
Eduard Zingerman
maintainerPATCH v3 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
@@ -18305,10 +18305,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]); }
@@ -18363,6 +18359,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.47.1
Eduard Zingerman
maintainerPATCH v3 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].
@@ -723,6 +727,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 */
@@ -819,6 +854,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.47.1
Eduard Zingerman
maintainerPATCH v3 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.47.1
Eduard Zingerman
maintainerPATCH v3 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
@@ -733,6 +733,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
@@ -822,6 +823,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
@@ -1648,7 +1648,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); }
@@ -1949,6 +1949,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); }
@@ -1977,6 +1980,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.47.1
Eduard Zingerman
maintainerPATCH v3 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()))
5: r6 = -31;
6: for (;;) {
7: if (!bpf_iter_num_next(&fp[-8]))
8: break;
9: if (unlikely(bpf_get_prandom_u32()))
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())) {
r6 = -31;
+ jump_into_loop:
+ goto +0;
+ goto loop;
+ }
+ if (unlikely(bpf_get_prandom_u32()))
+ goto jump_into_loop;
+ loop:
for (;;) {
if (!bpf_iter_num_next(&fp[-8]))
break;
if (unlikely(bpf_get_prandom_u32()))
*(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;
if (unlikely(bpf_get_prandom_u32()))
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())) +* r6 = -31; +* while (bpf_iter_num_next(&fp[-8])) { +* if (unlikely(bpf_get_prandom_u32())) +* *(fp + r6) = 7; +* } +* bpf_iter_num_destroy(&fp[-8]) +* return 0 +*/ + asmvolatile ( +"call %[bpf_get_prandom_u32];" +"r8 = r0;" +"r7 = 0;" +"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())) { +* r6 = -31; +* jump_into_loop: +* goto +0; +* goto loop; +* } +* if (unlikely(bpf_get_prandom_u32())) +* goto jump_into_loop; +* loop: +* while (bpf_iter_num_next(&fp[-8])) { +* if (unlikely(bpf_get_prandom_u32())) +* *(fp + r6) = 7; +* } +* bpf_iter_num_destroy(&fp[-8]) +* return 0 +*/ + asmvolatile ( +"call %[bpf_get_prandom_u32];" +"r8 = r0;" +"r7 = 0;" +"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) { +* r6 = num; +* r7 = iter; +* while (bpf_iter_num_next(r7)) { +* if (unlikely(bpf_get_prandom_u32())) +* *(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; +* if (unlikely(bpf_get_prandom_u32())) +* 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.47.1
Quoted 7 lines · Eduard Zingerman
This reverts commit
96a30e469ca1d2b8cc7811b40911f8614b558241. Next patches in the series modifypropagate_precision()to allow arbitrary starting state. Precision propagation requires access to jump history, and arbitrary states represent history not belonging toenv->cur_state.
Quoted 5 lines
Signed-off-by Eduard Zingerman <[email protected]>--- include/linux/bpf_verifier.h | 19 +++---- kernel/bpf/verifier.c | 107 ++++++++++++++++++----------------- 2 files changed, 63 insertions(+), 63 deletions(-)
This wasn't a clean revert. It broke the build with:
../kernel/bpf/verifier.c: In function ‘check_cond_jmp_op’:../kernel/bpf/verifier.c:16503:23: error: implicit declaration of function ‘push_insn_history’; did you mean ‘push_jmp_history’? [-Wimplicit-function-declaration]
16503 | err = push_insn_history(env, this_branch,
insn_flags, 0);
| ^~~~~~~~~~~~~~~~~
| push_jmp_historyThough it's fixed later in patch 8 as:
- err = push_insn_history(env, this_branch, insn_flags, 0);
+ err = push_jmp_history(env, this_branch, insn_flags, 0);
It would have been a bisect issue if not caught by CI:
https://netdev.bots.linux.dev/static/nipa/971030/14115002/build_clang/summary
I fixed up patch 1 and 8 while applying.
Pls pay attention to such things in the future.
Eduard Zingerman
maintainerOn Wed, 2025-06-11 at 15:45 -0700, Alexei Starovoitov wrote:
[...]
Quoted 9 lines
Though it's fixed later in patch 8 as:
(quoted diff) +1
-1- err = push_insn_history(env, this_branch, insn_flags, 0); + err = push_jmp_history(env, this_branch, insn_flags, 0);It would have been a bisect issue if not caught by CI:
https://netdev.bots.linux.dev/static/nipa/971030/14115002/build_clang/summaryI fixed up patch 1 and 8 while applying.
Pls pay attention to such things in the future.
Ack, sorry, it's a rebase artefact, squashed the change on top of the wrong commit.