[PATCH bpf v1 0/2] bpf: Compare stack frames in exact register states

[PATCH bpf v1 0/2] bpf: Compare stack frames in exact register states

[Kumar Kartikeya Dwivedi]

regs_exact() compares the value-bearing portion of bpf_reg_state and its
IDs, but excludes frameno. regsafe() compensates for that omission in its
PTR_TO_STACK case. An EXACT comparison returns through regs_exact() before
reaching that case, however, so infinite-loop detection can equate pointers
to the same offset in different stack frames.

A finite loop can expose the problem by first reading zero from fp-8 in its
caller, then changing its pointer to fp-8 in the callee, where the slot holds
one. The current verifier reports an infinite loop at the second visit even
though the next load makes the loop exit. A spilled pointer has the same
problem.

Include frameno in regs_exact() so every caller observes it. Keep precise
excluded: a precision mark records whether pruning may
ignore scalar ranges, while exact comparison already compares those ranges
unconditionally. Precision marks can also change through backtracking while
an ancestor state is still active.

The second patch adds register and spill variants of the finite loop. Both
are rejected with "infinite loop detected" before the fix and pass after it.

Kumar Kartikeya Dwivedi (2):
  bpf: Compare stack frames in regs_exact()
  selftests/bpf: Cover frame changes in bounded loops

 kernel/bpf/states.c                           |  8 +--
 .../selftests/bpf/progs/verifier_loops1.c     | 66 +++++++++++++++++++
 2 files changed, 69 insertions(+), 5 deletions(-)


base-commit: ee363e055895364039bf28348ff13c615afad4ba
-- 
2.53.0

[PATCH bpf v1 1/2] bpf: Compare stack frames in regs_exact()

[Kumar Kartikeya Dwivedi]

regs_exact() compares the register state up to id, followed by the ID
mappings, but does not compare frameno. The PTR_TO_STACK case in regsafe()
checks frameno separately, which is bypassed when exact comparison is
requested. Consequently, infinite-loop detection can treat pointers to
different stack frames as the same pointer and reject a finite loop.

For example, initialize fp-8 to zero in the caller and to one in the
callee, then pass the caller's fp-8 to the callee as r1:

    loop:
        r0 = *(u64 *)(r1 + 0);
        if r0 != 0 goto done;
        r1 = r10;
        r1 += -8;
        goto loop;
    done:
        exit;

The loop terminates after reading the callee's slot on its second
iteration. At the loop header, however, the only relevant difference is
r1's frameno, so exact comparison incorrectly reports an infinite loop.
The same problem occurs when the pointer is spilled to the stack.

Include frameno in regs_exact() so both exact and ordinary stack-pointer
comparisons enforce it. The field stays zero for other register types.

Continue to ignore precise. Precision marks control whether pruning may
ignore scalar ranges; they do not change the represented values, and exact
comparison already compares those ranges unconditionally. Marks can also
change through backtracking while an ancestor state is still being
explored.

Fixes: d5b892fd607a ("bpf: make infinite loop detection in is_state_visited() exact")
Reported-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
---
 kernel/bpf/states.c | 8 +++-----
 1 file changed, 3 insertions(+), 5 deletions(-)

diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
index 66fb11b6c6a7..827038ec18b7 100644
--- a/kernel/bpf/states.c
+++ b/kernel/bpf/states.c
@@ -491,7 +491,8 @@ static bool regs_exact(const struct bpf_reg_state *rold,
 {
 	return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
 	       check_ids(rold->id, rcur->id, idmap) &&
-	       check_ids(rold->parent_id, rcur->parent_id, idmap);
+	       check_ids(rold->parent_id, rcur->parent_id, idmap) &&
+	       rold->frameno == rcur->frameno;
 }
 
 enum exact_level {
@@ -639,10 +640,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 		return range_within(rold, rcur) &&
 		       tnum_in(rold->var_off, rcur->var_off);
 	case PTR_TO_STACK:
-		/* two stack pointers are equal only if they're pointing to
-		 * the same stack frame, since fp-8 in foo != fp-8 in bar
-		 */
-		return regs_exact(rold, rcur, idmap) && rold->frameno == rcur->frameno;
+		return regs_exact(rold, rcur, idmap);
 	case PTR_TO_ARENA:
 		return true;
 	case PTR_TO_INSN:
-- 
2.53.0

Re: [PATCH bpf v1 1/2] bpf: Compare stack frames in regs_exact()

[Eduard Zingerman]

On Mon, 2026-09-14 at 18:13 +0200, Kumar Kartikeya Dwivedi wrote:
> regs_exact() compares the register state up to id, followed by the ID
> mappings, but does not compare frameno. The PTR_TO_STACK case in regsafe()
> checks frameno separately, which is bypassed when exact comparison is
> requested. Consequently, infinite-loop detection can treat pointers to
> different stack frames as the same pointer and reject a finite loop.
> 
> For example, initialize fp-8 to zero in the caller and to one in the
> callee, then pass the caller's fp-8 to the callee as r1:
> 
>     loop:
>         r0 = *(u64 *)(r1 + 0);
>         if r0 != 0 goto done;
>         r1 = r10;
>         r1 += -8;
>         goto loop;
>     done:
>         exit;
> 
> The loop terminates after reading the callee's slot on its second
> iteration. At the loop header, however, the only relevant difference is
> r1's frameno, so exact comparison incorrectly reports an infinite loop.
> The same problem occurs when the pointer is spilled to the stack.
> 
> Include frameno in regs_exact() so both exact and ordinary stack-pointer
> comparisons enforce it. The field stays zero for other register types.
> 
> Continue to ignore precise. Precision marks control whether pruning may
> ignore scalar ranges; they do not change the represented values, and exact
> comparison already compares those ranges unconditionally. Marks can also
> change through backtracking while an ancestor state is still being
> explored.
> 
> Fixes: d5b892fd607a ("bpf: make infinite loop detection in is_state_visited() exact")
> Reported-by: Eduard Zingerman <eddyz87@gmail.com>
> Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
> ---

I'm going to land '[PATCH bpf v3 0/7] Misc bug fixes - part 5',
which would be in conflict with this one.
After that, could you please respin, but try to move frameno inside
the bpf_reg_state's union or near the delta field?

...

Re: [PATCH bpf v1 1/2] bpf: Compare stack frames in regs_exact()

[Kumar Kartikeya Dwivedi]

On Mon Sep 14, 2026 at 6:33 PM CEST, Eduard Zingerman wrote:
> On Mon, 2026-09-14 at 18:13 +0200, Kumar Kartikeya Dwivedi wrote:
>> regs_exact() compares the register state up to id, followed by the ID
>> mappings, but does not compare frameno. The PTR_TO_STACK case in regsafe()
>> checks frameno separately, which is bypassed when exact comparison is
>> requested. Consequently, infinite-loop detection can treat pointers to
>> different stack frames as the same pointer and reject a finite loop.
>>
>> For example, initialize fp-8 to zero in the caller and to one in the
>> callee, then pass the caller's fp-8 to the callee as r1:
>>
>>     loop:
>>         r0 = *(u64 *)(r1 + 0);
>>         if r0 != 0 goto done;
>>         r1 = r10;
>>         r1 += -8;
>>         goto loop;
>>     done:
>>         exit;
>>
>> The loop terminates after reading the callee's slot on its second
>> iteration. At the loop header, however, the only relevant difference is
>> r1's frameno, so exact comparison incorrectly reports an infinite loop.
>> The same problem occurs when the pointer is spilled to the stack.
>>
>> Include frameno in regs_exact() so both exact and ordinary stack-pointer
>> comparisons enforce it. The field stays zero for other register types.
>>
>> Continue to ignore precise. Precision marks control whether pruning may
>> ignore scalar ranges; they do not change the represented values, and exact
>> comparison already compares those ranges unconditionally. Marks can also
>> change through backtracking while an ancestor state is still being
>> explored.
>>
>> Fixes: d5b892fd607a ("bpf: make infinite loop detection in is_state_visited() exact")
>> Reported-by: Eduard Zingerman <eddyz87@gmail.com>
>> Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
>> ---
>
> I'm going to land '[PATCH bpf v3 0/7] Misc bug fixes - part 5',
> which would be in conflict with this one.
> After that, could you please respin, but try to move frameno inside
> the bpf_reg_state's union or near the delta field?
>
> ...

Makes sense, will do.

Re: [PATCH bpf v1 1/2] bpf: Compare stack frames in regs_exact()

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 6193 bytes --]

> diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
> index 66fb11b6c6a76..827038ec18b7a 100644
> --- a/kernel/bpf/states.c
> +++ b/kernel/bpf/states.c
> @@ -491,7 +491,8 @@ static bool regs_exact(const struct bpf_reg_state *rold,
>  {
>  	return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
>  	       check_ids(rold->id, rcur->id, idmap) &&
> -	       check_ids(rold->parent_id, rcur->parent_id, idmap);
> +	       check_ids(rold->parent_id, rcur->parent_id, idmap) &&
> +	       rold->frameno == rcur->frameno;
>  }

The frameno comparison is moved into regs_exact(), but regs_exact() is
not PTR_TO_STACK-specific. It is called from two other places:

states.c:509   if (exact == EXACT)
                       return regs_exact(rold, rcur, idmap);

states.c:650   default:
                       return regs_exact(rold, rcur, idmap);

The change depends on frameno staying zero for non-stack register types,
as the changelog states. Can that invariant actually be maintained?

Looking at bpf_reg_state.frameno writes, there is exactly one assignment:

verifier.c:2284  regs[BPF_REG_FP].frameno = state->frameno;

and one clearing mechanism, the memset in
bpf_mark_reg_unknown_imprecise():

verifier.c:2193  void bpf_mark_reg_unknown_imprecise(struct bpf_reg_state *reg)
                 { memset(reg, 0, sizeof(*reg)); ... }

The other reset helper does NOT clear frameno, and deliberately clears
only id and parent_id:

verifier.c:1860  static void __mark_reg_known(struct bpf_reg_state *reg, u64 imm)
                 {
                         /* Clear off and union(map_ptr, range) */
                         memset(((u8 *)reg) + sizeof(reg->type), 0,
                                offsetof(struct bpf_reg_state, var_off) - sizeof(reg->type));
                         reg->id = 0;
                         reg->parent_id = 0;
                         ___mark_reg_known(reg, imm);
                 }

So any site that turns a register into a non-stack pointer with
mark_reg_known_zero() followed by a type assignment carries over whatever
frameno the register previously held. Is mark_btf_ld_reg() this shape?

verifier.c:2249  case PTR_TO_BTF_ID:
                         mark_reg_known_zero(env, regs, regno);
                         regs[regno].type = PTR_TO_BTF_ID | flag;

And the LDX destination is not cleared before that:

verifier.c:6666  err = check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK);

Concrete path inside any subprogram (frameno == 1):

    if r7 == 0 goto L1
    r1 = r10                  /* PTR_TO_STACK, frameno = 1 */
    goto L2
L1: r1 = 0                    /* DST_OP -> mark_reg_unknown -> memset -> frameno = 0 */
L2: r1 = *(u64 *)(r6 + 0)     /* r6 is PTR_TO_BTF_ID; check_ptr_to_btf_access() ->
                                 mark_btf_ld_reg(PTR_TO_BTF_ID) -> frameno survives */
    ... common tail using r1 ...

At the join point r1 is PTR_TO_BTF_ID with frameno == 1 on one path and
frameno == 0 on the other. frameno is meaningless for PTR_TO_BTF_ID, yet
regsafe()'s default: arm now rejects the pair. Before this patch
regs_exact() ignored frameno there and the states pruned.

This is a pruning regression. The change is monotonically stricter, and
the states_equal(..., EXACT) call sits inside `if (sl->state.branches)`
whose every exit is `goto miss`, so a failed exact compare never falls
through to pruning. The patch cannot cause an infinite loop to be
accepted. The cost is duplicate state exploration, which for a program
near the complexity limit turns a loadable program into one rejected as
too complex.

Could frameno be kept in the PTR_TO_STACK arm of regsafe() and also added
to the exact == EXACT early return? Or could frameno be normalized in
__mark_reg_known() alongside id and parent_id?

[ ... ]

> @@ -639,10 +640,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
>  		return range_within(rold, rcur) &&
>  		       tnum_in(rold->var_off, rcur->var_off);
>  	case PTR_TO_STACK:
> -		/* two stack pointers are equal only if they're pointing to
> -		 * the same stack frame, since fp-8 in foo != fp-8 in bar
> -		 */
> -		return regs_exact(rold, rcur, idmap) && rold->frameno == rcur->frameno;
> +		return regs_exact(rold, rcur, idmap);
>  	case PTR_TO_ARENA:
>  		return true;
>  	case PTR_TO_INSN:

[ ... ]

Regarding the commit message:

>     Include frameno in regs_exact() so both exact and ordinary stack-pointer
>     comparisons enforce it. The field stays zero for other register types.

Is "The field stays zero for other register types" accurate?

bpf_reg_state.frameno is written in exactly one place (verifier.c:2284,
R10 in init_reg_state()) and is only cleared as a side effect of the
memset in bpf_mark_reg_unknown_imprecise() (verifier.c:2193).

__mark_reg_known() clears id and parent_id explicitly but leaves frameno
alone (verifier.c:1860-1868), so mark_btf_ld_reg()'s PTR_TO_BTF_ID arm
(verifier.c:2249-2253) produces a register with a stale non-zero frameno
whenever the LDX destination previously held a stack pointer.

Non-stack register types do not keep frameno at zero. frameno is
unmaintained for them, and only PTR_TO_STACK ever reads it.

Should the changelog either drop this claim and state the pruning
consequence, or should the patch establish the invariant it asserts?

Also, Eduard Zingerman requested in the v1 review that frameno should be
moved inside the bpf_reg_state's union or near the delta field for better
struct layout. You agreed to make this change but it has not been
implemented yet.

The v1 review comment:
https://lore.kernel.org/bpf/9c64f514a0afb6a491ff316246ec6cefa4adeff7.camel@gmail.com/

Eduard wrote: "After that, could you please respin, but try to move
frameno inside the bpf_reg_state's union or near the delta field?"

Currently, frameno is still at the end of the struct after parent_id, not
inside the union or near delta. Are you planning to make this change?


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/34868467454

[PATCH bpf v1 2/2] selftests/bpf: Cover frame changes in bounded loops

[Kumar Kartikeya Dwivedi]

Add two finite loops whose progress is represented only by changing the
frame number of a stack pointer. Each loop first reads zero from the
caller's stack, switches to the same offset in the callee's stack, and
exits after reading one on its next iteration.

Keep the pointer in a register in one test and spill it in the other to
exercise both regsafe() and stacksafe() during exact state comparison.
Force frequent checkpoints so the tests exercise infinite-loop detection,
and check that both programs return one when run.

Without the frameno comparison in regs_exact(), both programs are
rejected with an "infinite loop detected" diagnostic instead of loading
successfully.

Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
---
 .../selftests/bpf/progs/verifier_loops1.c     | 66 +++++++++++++++++++
 1 file changed, 66 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_loops1.c b/tools/testing/selftests/bpf/progs/verifier_loops1.c
index d248ce877f14..f8b7ba1bf6b8 100644
--- a/tools/testing/selftests/bpf/progs/verifier_loops1.c
+++ b/tools/testing/selftests/bpf/progs/verifier_loops1.c
@@ -303,4 +303,70 @@ __naked void maybe_exit_scc_bug1(void)
 	::: __clobber_all);
 }
 
+/*
+ * The loop reads zero from the caller's stack on its first iteration and
+ * one from the callee's stack on its second iteration. At the loop header,
+ * only the frame number of the pointer in r1 changes.
+ */
+static __naked __noinline __used
+void loop_stack_frames_reg(void)
+{
+	asm volatile ("*(u64 *)(r10 - 8) = 1;"
+	"1: r0 = *(u64 *)(r1 + 0);"
+	"if r0 != 0 goto 2f;"
+	"r1 = r10;"
+	"r1 += -8;"
+	"goto 1b;"
+	"2: exit;"
+	::: __clobber_all);
+}
+
+SEC("xdp")
+__description("bounded loop changing stack frame in a register")
+__success __retval(1)
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void bounded_loop_stack_frames_reg(void)
+{
+	asm volatile ("*(u64 *)(r10 - 8) = 0;"
+	"r1 = r10;"
+	"r1 += -8;"
+	"call loop_stack_frames_reg;"
+	"exit;"
+	::: __clobber_all);
+}
+
+/*
+ * Exercise the same frame change through a spilled pointer. All registers
+ * at the loop header are identical, while fp-16 points to a different frame.
+ */
+static __naked __noinline __used
+void loop_stack_frames_spill(void)
+{
+	asm volatile ("*(u64 *)(r10 - 8) = 1;"
+	"*(u64 *)(r10 - 16) = r1;"
+	"1: r1 = *(u64 *)(r10 - 16);"
+	"r0 = *(u64 *)(r1 + 0);"
+	"if r0 != 0 goto 2f;"
+	"r1 = r10;"
+	"r1 += -8;"
+	"*(u64 *)(r10 - 16) = r1;"
+	"goto 1b;"
+	"2: exit;"
+	::: __clobber_all);
+}
+
+SEC("xdp")
+__description("bounded loop changing stack frame in a spill")
+__success __retval(1)
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void bounded_loop_stack_frames_spill(void)
+{
+	asm volatile ("*(u64 *)(r10 - 8) = 0;"
+	"r1 = r10;"
+	"r1 += -8;"
+	"call loop_stack_frames_spill;"
+	"exit;"
+	::: __clobber_all);
+}
+
 char _license[] SEC("license") = "GPL";
-- 
2.53.0