Re: [PATCH v2 bpf-next 1/2] bpf: Avoid one round of bounds deduction

[Eduard Zingerman <eddyz87@gmail.com>]

On Fri, 2026-03-13 at 10:17 +0800, Shung-Hsi Yu wrote:

[...]

> The problem is that I'm operating on a simplified assumption of "not
> being able to converage to a fix-point is bad because it could lead to
> bound invariant violation". So taking this chance to ask, does that all
> ties back to is_scalar_branch_taken and reg_set_min_max (or was it
> regs_refine_cond_op) difference?
> 
> Also, when we fail to reach a fix-point, it does not become a problem
> immediately, but only becomes a invariant violation some where down the
> line when we again do bound deduction?
> 
> I haven't actually look into an invariant violation myself, so details
> are rather hazy. 

I don't think failing to reach fixed point causes invariant violation.
The root cause for invariant violation is that decisions in
is_scalar_branch_taken() for e.g. >=, <= are taken based on ranges,
but additional information in tnum is not taken into account.
Later reg_set_min_max() will call reg_bounds_sync() and it might turn
out that updated ranges do not intersect with tnums.
The inverse might happen for tnum based decisions in
is_scalar_branch_taken().

So, if we don't reach fixed point in reg_bounds_sync() we just leave
some precision on the table w/o other negative consequences,
as far as I understand.

One solution for invariants violation looks as follows:
- Adjust is_scalar_branch_taken():
  - Do not make predictions directly, instead apply range and tnum
    changes corresponding to the operation (e.g. for true branch of
    the `rX <= 0` operation intersect `rX` range with [-∞, 0]).
  - Call reg_set_min_max() and check if resulting registers are in a
    valid state. If they are for some branch but not another a
    prediction can be made.
- Adjust check_cond_jmp_op() to use registers computed by
  is_scalar_branch_taken() for true and false verifier states.
- Adjust reg_bounds_sync() to consistently bail out if invariants
  violation is encountered. I think it has a few places with implicit
  assumption that ranges/tnums must overlap.

I have a stale branch with these changes, need to pull my act together
and finish with those changes.