Re: [PATCH] bpf/verifier: optimize precision backtracking by skipping precise bits

[Eduard Zingerman]

On Thu, 2026-01-15 at 23:04 +0800, wujing wrote:
> 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 <realwujing@xxxxxxxxx>
> Signed-off-by: Qiliang Yuan <yuanql9@xxxxxxxxxxxxxxx>
> ---

__mark_chain_precision already stops propagation at states boundary.
States are introduced often, so I don't think this patch solves a real
world problem. In any case, the correct place to put such checks is
the bt setup code in __mark_chain_precision:

  static int __mark_chain_precision(...)
  {
	...
        func = st->frame[bt->frame];
        if (regno >= 0) {
                reg = &func->regs[regno];
                if (reg->type != SCALAR_VALUE) {
                        verifier_bug(env, "backtracking misuse");
                        return -EFAULT;
                }
		>>>>> add a condition here <<<<<
                bt_set_reg(bt, regno);
        }
	...
  }

But unless you see real measurable performance improvement,
I don't think the code should be changed.

[...]