Re: [PATCH bpf-next 02/11] bpf: do not intersect with current register range on clamp

[Eduard Zingerman <eddyz87@gmail.com>]

On Sat, 2026-10-24 at 22:10 -0700, Alexei Starovoitov wrote:
> On Sat, Oct 24, 2026 at 6:03 PM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> >
> > On Sat Oct 24, 2026 at 6:57 AM UTC, Eduard Zingerman wrote:
> > > On Sat, 2026-10-24 at 00:41 +0000, bot+bpf-ci@kernel.org wrote:
> > >
> > > ...
> > >
> > > > Since bisection can land on this commit, could that change be folded into
> > > > this patch or ordered before it?
> > >
> > > Commits should remain separate for documentation purposes.
> > > Full test suite passes on both.
> > >
> > > > A related question about the end of the series.  cf18840bc068 only helps
> > > > when the current frame has no active loop.  Consider states inside an inner
> > > > loop that is entered again on the second iteration of a terminating outer
> > > > loop.  current_loop() finds the inner loop in both states, but its
> > > > entry_state differs, because handle_loop_entry_exit() splits a new one on
> > > > each entry.  So the EXACT check runs, and loop_stack_safe() does not
> > > > compare entry_state.
> > > >
> > > > With the outer induction variable now the same on every outer iteration, a
> > > > program like the one below looks like it would still hit "infinite loop
> > > > detected" after cf18840bc068 (with the old code the outer induction
> > > > variable was [1..9] on the second outer iteration and the EXACT compare
> > > > failed):
> > > >
> > > >     w1 = 1;
> > > >     *(u32 *)(r10 - 8) = r1;
> > > >     r6 = 0;
> > > > 1:  r7 = 0;
> > > > 2:  *(u32 *)(r10 - 4) = 1;   /* fp-8 spill -> STACK_MISC */
> > > >     r7 += 1;
> > > >     if r7 < 3 goto 2b;
> > > >     r6 += 1;
> > > >     if r6 < 10 goto 1b;
> > > >     r0 = *(u32 *)(r10 - 8);
> > > >     exit;
> > > >
> > > > Is that case covered somewhere I missed?
> > >
> > > This example is valid. Need to relax the condition in the
> > > current_loop() or bpf_is_state_visited().
> >
> > so you're going to respin it or follow up?
> >
> > It's fine to ignore CI in patch 3.
> > We'll be removing states.c soon.
>
> respin. The better fix is probably:
> -               bounds.r64 = cnum64_intersect(reg->r64, bounds.r64);
> -               bounds.r32 = cnum32_intersect(reg->r32, bounds.r32);
> -               if (cnum64_is_empty(bounds.r64)) {
> -                       verifier_bug(env, "scev clamp produced empty
> range for r%d", r);
> -                       return -EFAULT;
> +               r64 = cnum64_intersect(reg->r64, bounds.r64);
> +               r32 = cnum32_intersect(reg->r32, bounds.r32);
> +               /*
> +                * The state at the head doesn't know how the
> variables depend on each other.
> +                * It lets r6 = 0, r7 = 9 into the loop when both
> count from 0, and r7 = 10
> +                * comes back. No run gets here like that, so any
> range is right for r7.
> +                * Take the one it has at the head: the rest of the
> state is still compared
> +                * with the head, and what was pruned on the way here
> relies on that.
> +                */
> +               if (!cnum64_is_empty(r64) && !cnum32_is_empty(r32)) {
> +                       bounds.r64 = r64;
> +                       bounds.r32 = r32;

Well, it's a minimal change, but I think it is still prone to
counter-examples. I'd still like to remove the clamping logic
altogether and adjust the bpf_is_state_visited() as follows:

--- a/kernel/bpf/states.c
+++ b/kernel/bpf/states.c
@@ -1532,10 +1532,10 @@ int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx)
                         */
                        old_loop = current_loop(&sl->state);
                        cur_loop = current_loop(cur);
-                       if (old_loop && cur_loop &&
-                           old_loop->terminates && cur_loop->terminates &&
-                           old_loop->entry_state == cur_loop->entry_state) {
-                               if (states_equal(env, &sl->state, cur, RANGE_WITHIN)) {
+                       if (old_loop && cur_loop) {
+                               if (old_loop->terminates && cur_loop->terminates &&
+                                   old_loop->entry_state == cur_loop->entry_state &&
+                                   states_equal(env, &sl->state, cur, RANGE_WITHIN)) {
                                        loop = true;
                                        goto hit;
                                }

Because of the `goto skip_inf_loop_check` check immediately after that
it would avoid the whole set of such problems. (And will be in the
same line as iterators).

An alternative, if we want to preserve clamping (but I see no reason to),
would be an additional check in check_cond_jmp_op(),
when jump prediction is done. There, for a latch condition,
a call to scev.c can be made, checking if induction variables would
have an empty range.