Backtracking is one of the most expensive parts of the verifier. When marking precision, currently the verifier always triggers the full __mark_chain_precision even if the target register or stack slot is already marked as precise. Since a precise mark in a state implies that all necessary ancestors have already been backtracked and marked accordingly, we can safely skip the backtracking process if the bit is already set. This patch implements early exit logic in: 1. mark_chain_precision: Check if the register is already precise. 2. propagate_precision: Skip registers and stack slots that are already precise in the current state when propagating from an old state. This significantly reduces redundant backtracking in complex BPF programs with frequent state pruning and merges. Signed-off-by: wujing Signed-off-by: Qiliang Yuan --- kernel/bpf/verifier.c | 19 +++++++++++++++++-- 1 file changed, 17 insertions(+), 2 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 6220dde41107..378341e1177f 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -4927,6 +4927,14 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int mark_chain_precision(struct bpf_verifier_env *env, int regno) { + struct bpf_reg_state *reg; + + if (regno >= 0) { + reg = &env->cur_state->frame[env->cur_state->curframe]->regs[regno]; + if (reg->precise) + return 0; + } + return __mark_chain_precision(env, env->cur_state, regno, NULL); } @@ -19527,19 +19535,23 @@ static int propagate_precision(struct bpf_verifier_env *env, struct bpf_verifier_state *cur, bool *changed) { - struct bpf_reg_state *state_reg; - struct bpf_func_state *state; + struct bpf_reg_state *state_reg, *cur_reg; + struct bpf_func_state *state, *cur_state; int i, err = 0, fr; bool first; for (fr = old->curframe; fr >= 0; fr--) { state = old->frame[fr]; + cur_state = cur->frame[fr]; state_reg = state->regs; first = true; for (i = 0; i < BPF_REG_FP; i++, state_reg++) { if (state_reg->type != SCALAR_VALUE || !state_reg->precise) continue; + cur_reg = &cur_state->regs[i]; + if (cur_reg->precise) + continue; if (env->log.level & BPF_LOG_LEVEL2) { if (first) verbose(env, "frame %d: propagating r%d", fr, i); @@ -19557,6 +19569,9 @@ static int propagate_precision(struct bpf_verifier_env *env, if (state_reg->type != SCALAR_VALUE || !state_reg->precise) continue; + cur_reg = &cur_state->stack[i].spilled_ptr; + if (cur_reg->precise) + continue; if (env->log.level & BPF_LOG_LEVEL2) { if (first) verbose(env, "frame %d: propagating fp%d", -- 2.39.5