[PATCH 0/2] bpf: calls to bpf_loop() should have an SCC and accumulate backedges

[PATCH 0/2] bpf: calls to bpf_loop() should have an SCC and accumulate backedges

[Eduard Zingerman]

This is a correctness fix for the verification of BPF programs that
work with callback-calling functions. The problem is the same as the
issue fixed by series [1] for iterator-based loops: some of the states
created while processing the callback function body might have
incomplete read or precision marks.

An example of an unsafe program that is accepted without this fix can
be found in patch #2.

There is some impact on verification performance:

File                             Program               Insns (A)  Insns (B)  Insns      (DIFF)
-------------------------------  --------------------  ---------  ---------  -----------------
pyperf600_bpf_loop.bpf.o         on_event                   4247       9985   +5738 (+135.11%)
setget_sockopt.bpf.o             skops_sockopt              5719       7446    +1727 (+30.20%)
setget_sockopt.bpf.o             socket_post_create         1253       1603     +350 (+27.93%)
strobemeta_bpf_loop.bpf.o        on_event                   3424       7224   +3800 (+110.98%)
test_tcp_custom_syncookie.bpf.o  tcp_custom_syncookie      11929      38307  +26378 (+221.12%)
xdp_synproxy_kern.bpf.o          syncookie_tc              13986      23035    +9049 (+64.70%)
xdp_synproxy_kern.bpf.o          syncookie_xdp             13881      21022    +7141 (+51.44%)

Total progs: 4172
Old success: 2520
New success: 2520
total_insns diff min:    0.00%
total_insns diff max:  221.12%
0 -> value: 0
value -> 0: 0
total_insns abs max old: 837,487
total_insns abs max new: 837,487
   0 .. 5    %: 4163
   5 .. 15   %: 2
  25 .. 35   %: 2
  50 .. 60   %: 1
  60 .. 70   %: 1
 110 .. 120  %: 1
 135 .. 145  %: 1
 220 .. 225  %: 1

[1] https://lore.kernel.org/bpf/174968344350.3524559.14906547029551737094.git-patchwork-notify@kernel.org/

---
Eduard Zingerman (2):
      bpf: bpf_scc_visit instance and backedges accumulation for bpf_loop()
      selftests/bpf: test cases for bpf_loop SCC and state graph backedges

 kernel/bpf/verifier.c                     | 13 ++++--
 tools/testing/selftests/bpf/progs/iters.c | 75 +++++++++++++++++++++++++++++++
 2 files changed, 84 insertions(+), 4 deletions(-)
---
base-commit: f14cdb1367b947d373215e36cfe9c69768dbafc9
change-id: 20251219-scc-for-callbacks-d6d94faa2e43

[PATCH 1/2] bpf: bpf_scc_visit instance and backedges accumulation for bpf_loop()

[Eduard Zingerman]

Calls like bpf_loop() or bpf_for_each_map_elem() introduce loops that
are not explicitly present in the control-flow graph. The verifier
processes such calls by repeatedly interpreting the callback function
body within the same verification path (until the current state
converges with a previous state).

Such loops require a bpf_scc_visit instance in order to allow the
accumulation of the state graph backedges. Otherwise, certain
checkpoint states created within the bodies of such loops will have
incomplete precision marks.

See the next patch for an example of a program that leads to the
verifier accepting an unsafe program.

Fixes: 96c6aa4c63af ("bpf: compute SCCs in program control flow graph")
Fixes: c9e31900b54c ("bpf: propagate read/precision marks over state graph backedges")
Reported-by: Breno Leitao <leitao@debian.org>
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 kernel/bpf/verifier.c | 13 +++++++++----
 1 file changed, 9 insertions(+), 4 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 2de1a736ef69514fcf599de498aae56eaf24fe33..0baae7828af220accd4086b9bad270e745f4aff9 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -19830,8 +19830,10 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 				}
 			}
 			if (bpf_calls_callback(env, insn_idx)) {
-				if (states_equal(env, &sl->state, cur, RANGE_WITHIN))
+				if (states_equal(env, &sl->state, cur, RANGE_WITHIN)) {
+					loop = true;
 					goto hit;
+				}
 				goto skip_inf_loop_check;
 			}
 			/* attempt to detect infinite loop to avoid unnecessary doomed work */
@@ -25071,15 +25073,18 @@ static int compute_scc(struct bpf_verifier_env *env)
 			}
 			/*
 			 * Assign SCC number only if component has two or more elements,
-			 * or if component has a self reference.
+			 * or if component has a self reference, or if instruction is a
+			 * callback calling function (implicit loop).
 			 */
-			assign_scc = stack[stack_sz - 1] != w;
-			for (j = 0; j < succ->cnt; ++j) {
+			assign_scc = stack[stack_sz - 1] != w;	/* two or more elements? */
+			for (j = 0; j < succ->cnt; ++j) {	/* self reference? */
 				if (succ->items[j] == w) {
 					assign_scc = true;
 					break;
 				}
 			}
+			if (bpf_calls_callback(env, w)) /* implicit loop? */
+				assign_scc = true;
 			/* Pop component elements from stack */
 			do {
 				t = stack[--stack_sz];

-- 
2.52.0

[PATCH 2/2] selftests/bpf: test cases for bpf_loop SCC and state graph backedges

[Eduard Zingerman]

Test for state graph backedges accumulation for SCCs formed by
bpf_loop(). Equivalent to the following C program:

  int main(void) {
    1: fp[-8] = bpf_get_prandom_u32();
    2: fp[-16] = -32;                       // used in a memory access below
    3: bpf_loop(7, loop_cb4, fp, 0);
    4: return 0;
  }

  int loop_cb4(int i, void *ctx) {
    5: if (unlikely(ctx[-8] > bpf_get_prandom_u32()))
    6:   *(u64 *)(fp + ctx[-16]) = 42;      // aligned access expected
    7: if (unlikely(fp[-8] > bpf_get_prandom_u32()))
    8:   ctx[-16] = -31;                    // makes said access unaligned
    9: return 0;
  }

If state graph backedges are not accumulated properly at the SCC
formed by loop_cb4() call from bpf_loop(), the state {ctx[-16]=-32}
injected at instruction 9 on verification path 1,2,3,5,7,9,4 would be
considered fully verified and would lack precision mark for ctx[-16].
This would lead to early pruning of verification path 1,2,3,5,7,8,9 in
state {ctx[-16]=-31}, which in turn leads to the incorrect assumption
that the above program is safe.

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 tools/testing/selftests/bpf/progs/iters.c | 75 +++++++++++++++++++++++++++++++
 1 file changed, 75 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/iters.c b/tools/testing/selftests/bpf/progs/iters.c
index 7dd92a303bf6b3f0fc2962f6ce6cc453350561e3..69061f0309579eada74e5f2a68640470ff94a8b3 100644
--- a/tools/testing/selftests/bpf/progs/iters.c
+++ b/tools/testing/selftests/bpf/progs/iters.c
@@ -1926,4 +1926,79 @@ static int loop1_wrapper(void)
 	);
 }
 
+/*
+ * This is similar to a test case absent_mark_in_the_middle_state(),
+ * but adapted for use with bpf_loop().
+ */
+SEC("raw_tp")
+__flag(BPF_F_TEST_STATE_FREQ)
+__failure __msg("math between fp pointer and register with unbounded min value is not allowed")
+__naked void absent_mark_in_the_middle_state4(void)
+{
+	/*
+	 * Equivalent to a C program below:
+	 *
+	 * int main(void) {
+	 *   fp[-8] = bpf_get_prandom_u32();
+	 *   fp[-16] = -32;                    // used in a memory access below
+	 *   bpf_loop(7, loop_cb4, fp, 0);
+	 *   return 0;
+	 * }
+	 *
+	 * int loop_cb4(int i, void *ctx) {
+	 *   if (unlikely(ctx[-8] > bpf_get_prandom_u32()))
+	 *     *(u64 *)(fp + ctx[-16]) = 42;   // aligned access expected
+	 *   if (unlikely(fp[-8] > bpf_get_prandom_u32()))
+	 *     ctx[-16] = -31;                 // makes said access unaligned
+	 *   return 0;
+	 * }
+	 */
+	asm volatile (
+		"call %[bpf_get_prandom_u32];"
+		"r8 = r0;"
+		"*(u64 *)(r10 - 8) = r0;"
+		"*(u64 *)(r10 - 16) = -32;"
+		"r1 = 7;"
+		"r2 = loop_cb4 ll;"
+		"r3 = r10;"
+		"r4 = 0;"
+		"call %[bpf_loop];"
+		"r0 = 0;"
+		"exit;"
+		:
+		: __imm(bpf_loop),
+		  __imm(bpf_get_prandom_u32)
+		: __clobber_all
+	);
+}
+
+__used __naked
+static void loop_cb4(void)
+{
+	asm volatile (
+		"r9 = r2;"
+		"r8 = *(u64 *)(r9 - 8);"
+		"r6 = *(u64 *)(r9 - 16);"
+		"call %[bpf_get_prandom_u32];"
+		"if r0 > r8 goto use_fp16_%=;"
+	"1:"
+		"call %[bpf_get_prandom_u32];"
+		"if r0 > r8 goto update_fp16_%=;"
+	"2:"
+		"r0 = 0;"
+		"exit;"
+	"use_fp16_%=:"
+		"r1 = r10;"
+		"r1 += r6;"
+		"*(u64 *)(r1 + 0) = 42;"
+		"goto 1b;"
+	"update_fp16_%=:"
+		"*(u64 *)(r9 - 16) = -31;"
+		"goto 2b;"
+		:
+		: __imm(bpf_get_prandom_u32)
+		: __clobber_all
+	);
+}
+
 char _license[] SEC("license") = "GPL";

-- 
2.52.0

Re: [PATCH 1/2] bpf: bpf_scc_visit instance and backedges accumulation for bpf_loop()

[Breno Leitao]

On Mon, Dec 29, 2025 at 11:13:07PM -0800, Eduard Zingerman wrote:
> Calls like bpf_loop() or bpf_for_each_map_elem() introduce loops that
> are not explicitly present in the control-flow graph. The verifier
> processes such calls by repeatedly interpreting the callback function
> body within the same verification path (until the current state
> converges with a previous state).
> 
> Such loops require a bpf_scc_visit instance in order to allow the
> accumulation of the state graph backedges. Otherwise, certain
> checkpoint states created within the bodies of such loops will have
> incomplete precision marks.
> 
> See the next patch for an example of a program that leads to the
> verifier accepting an unsafe program.
> 
> Fixes: 96c6aa4c63af ("bpf: compute SCCs in program control flow graph")
> Fixes: c9e31900b54c ("bpf: propagate read/precision marks over state graph backedges")
> Reported-by: Breno Leitao <leitao@debian.org>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>

Tested-by: Breno Leitao <leitao@debian.org>

Re: [PATCH 0/2] bpf: calls to bpf_loop() should have an SCC and accumulate backedges

[Eduard Zingerman]

On Mon, 2025-12-29 at 23:13 -0800, Eduard Zingerman wrote:
> This is a correctness fix for the verification of BPF programs that
> work with callback-calling functions. The problem is the same as the
> issue fixed by series [1] for iterator-based loops: some of the states
> created while processing the callback function body might have
> incomplete read or precision marks.

I did not apply proper bpf-next tag to the patch-set.
Will wait a few days for comments and resend,
so that patchworks can pick this up.

Re: [PATCH 0/2] bpf: calls to bpf_loop() should have an SCC and accumulate backedges

[patchwork-bot+netdevbpf]

Hello:

This series was applied to bpf/bpf-next.git (master)
by Alexei Starovoitov <ast@kernel.org>:

On Mon, 29 Dec 2025 23:13:06 -0800 you wrote:
> This is a correctness fix for the verification of BPF programs that
> work with callback-calling functions. The problem is the same as the
> issue fixed by series [1] for iterator-based loops: some of the states
> created while processing the callback function body might have
> incomplete read or precision marks.
> 
> An example of an unsafe program that is accepted without this fix can
> be found in patch #2.
> 
> [...]

Here is the summary with links:
  - [1/2] bpf: bpf_scc_visit instance and backedges accumulation for bpf_loop()
    https://git.kernel.org/bpf/bpf-next/c/f597664454bd
  - [2/2] selftests/bpf: test cases for bpf_loop SCC and state graph backedges
    https://git.kernel.org/bpf/bpf-next/c/e6f2612f0e7c

You are awesome, thank you!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html

Re: [PATCH 0/2] bpf: calls to bpf_loop() should have an SCC and accumulate backedges

[Levi Zim]

Hi Eduard,

On 2025-12-30 15:13, Eduard Zingerman wrote:
> This is a correctness fix for the verification of BPF programs that
> work with callback-calling functions. The problem is the same as the
> issue fixed by series [1] for iterator-based loops: some of the states
> created while processing the callback function body might have
> incomplete read or precision marks.
>
> An example of an unsafe program that is accepted without this fix can
> be found in patch #2.
>
> There is some impact on verification performance:
>
> File                             Program               Insns (A)  Insns (B)  Insns      (DIFF)
> -------------------------------  --------------------  ---------  ---------  -----------------
> pyperf600_bpf_loop.bpf.o         on_event                   4247       9985   +5738 (+135.11%)
> setget_sockopt.bpf.o             skops_sockopt              5719       7446    +1727 (+30.20%)
> setget_sockopt.bpf.o             socket_post_create         1253       1603     +350 (+27.93%)
> strobemeta_bpf_loop.bpf.o        on_event                   3424       7224   +3800 (+110.98%)
> test_tcp_custom_syncookie.bpf.o  tcp_custom_syncookie      11929      38307  +26378 (+221.12%)
> xdp_synproxy_kern.bpf.o          syncookie_tc              13986      23035    +9049 (+64.70%)
> xdp_synproxy_kern.bpf.o          syncookie_xdp             13881      21022    +7141 (+51.44%)

I see that the first patch in the series causes some impact on 
verification performance.
The patch contains "Fixes:" tag for two commits that landed in 6.17 kernel:

c9e31900b54c ("bpf: propagate read/precision marks over state graph backedges")
96c6aa4c63af ("bpf: compute SCCs in program control flow graph")

I have a BPF program [1] that is badly affected by the patch that it no 
longer loads on 6.19.5 due to
E2BIG error.

The program consists of multiple nested bpf_loop calls as follows so I 
think the impact on it is expected.

(entry point) func trace_exec_common
-> (bpf_loop) callback read_strings for reading ARGV
-> (bpf_loop) callback read_strings for reading ENVP
-> (call) read_fds
    -> (bpf_loop) callback read_fds_impl for iterating over the fdset
       -> (bpf_loop) callback read_fdset_word for reading a single word in the fdset
           -> (call) _read_fd for getting information from a single fd
               -> (call) read_send_path which reads the absolute path and mount info


After the patch, I find that I need to comment out the 
bpf_loop(BITS_PER_LONG, read_fdset_word, &subctx, 0)
statement in read_fds_impl function to make the eBPF program load.

Does it mean that after the patch, the verification performance degraded 
significantly compared to older
versions of kernel, e.g. 6.6 LTS? Or is it that older kernels are also 
impacted with the same sort of bug and
currently waiting to be fixed?

I am also exploring ways to fix my bpf program so that it could work on 
6.19.4 and later kernels.
It would be greatly appreciated if you could share some insights for 
fixing bpf programs that are badly
affected by this patch.

[1]: 
https://github.com/kxxt/tracexec/blob/main/crates/tracexec-backend-ebpf/src/bpf/tracexec_system.bpf.c

Thanks,
Levi

>
> Total progs: 4172
> Old success: 2520
> New success: 2520
> total_insns diff min:    0.00%
> total_insns diff max:  221.12%
> 0 -> value: 0
> value -> 0: 0
> total_insns abs max old: 837,487
> total_insns abs max new: 837,487
>     0 .. 5    %: 4163
>     5 .. 15   %: 2
>    25 .. 35   %: 2
>    50 .. 60   %: 1
>    60 .. 70   %: 1
>   110 .. 120  %: 1
>   135 .. 145  %: 1
>   220 .. 225  %: 1
>
> [1] https://lore.kernel.org/bpf/174968344350.3524559.14906547029551737094.git-patchwork-notify@kernel.org/
>
> ---
> Eduard Zingerman (2):
>        bpf: bpf_scc_visit instance and backedges accumulation for bpf_loop()
>        selftests/bpf: test cases for bpf_loop SCC and state graph backedges
>
>   kernel/bpf/verifier.c                     | 13 ++++--
>   tools/testing/selftests/bpf/progs/iters.c | 75 +++++++++++++++++++++++++++++++
>   2 files changed, 84 insertions(+), 4 deletions(-)
> ---
> base-commit: f14cdb1367b947d373215e36cfe9c69768dbafc9
> change-id: 20251219-scc-for-callbacks-d6d94faa2e43
>

Re: [PATCH 0/2] bpf: calls to bpf_loop() should have an SCC and accumulate backedges

[Eduard Zingerman]

On Fri, 2026-03-06 at 16:20 +0800, Levi Zim wrote:
> Hi Eduard,
> 
> On 2025-12-30 15:13, Eduard Zingerman wrote:
> > This is a correctness fix for the verification of BPF programs that
> > work with callback-calling functions. The problem is the same as the
> > issue fixed by series [1] for iterator-based loops: some of the states
> > created while processing the callback function body might have
> > incomplete read or precision marks.
> > 
> > An example of an unsafe program that is accepted without this fix can
> > be found in patch #2.
> > 
> > There is some impact on verification performance:
> > 
> > File                             Program               Insns (A)  Insns (B)  Insns      (DIFF)
> > -------------------------------  --------------------  ---------  ---------  -----------------
> > pyperf600_bpf_loop.bpf.o         on_event                   4247       9985   +5738 (+135.11%)
> > setget_sockopt.bpf.o             skops_sockopt              5719       7446    +1727 (+30.20%)
> > setget_sockopt.bpf.o             socket_post_create         1253       1603     +350 (+27.93%)
> > strobemeta_bpf_loop.bpf.o        on_event                   3424       7224   +3800 (+110.98%)
> > test_tcp_custom_syncookie.bpf.o  tcp_custom_syncookie      11929      38307  +26378 (+221.12%)
> > xdp_synproxy_kern.bpf.o          syncookie_tc              13986      23035    +9049 (+64.70%)
> > xdp_synproxy_kern.bpf.o          syncookie_xdp             13881      21022    +7141 (+51.44%)
> 
> I see that the first patch in the series causes some impact on 
> verification performance.
> The patch contains "Fixes:" tag for two commits that landed in 6.17 kernel:
> 
> c9e31900b54c ("bpf: propagate read/precision marks over state graph backedges")
> 96c6aa4c63af ("bpf: compute SCCs in program control flow graph")
> 
> I have a BPF program [1] that is badly affected by the patch that it no 
> longer loads on 6.19.5 due to
> E2BIG error.
> 
> The program consists of multiple nested bpf_loop calls as follows so I 
> think the impact on it is expected.
> 
> (entry point) func trace_exec_common
> -> (bpf_loop) callback read_strings for reading ARGV
> -> (bpf_loop) callback read_strings for reading ENVP
> -> (call) read_fds
>     -> (bpf_loop) callback read_fds_impl for iterating over the fdset
>        -> (bpf_loop) callback read_fdset_word for reading a single word in the fdset
>            -> (call) _read_fd for getting information from a single fd
>                -> (call) read_send_path which reads the absolute path and mount info
> 
> 
> After the patch, I find that I need to comment out the 
> bpf_loop(BITS_PER_LONG, read_fdset_word, &subctx, 0)
> statement in read_fds_impl function to make the eBPF program load.
> 
> Does it mean that after the patch, the verification performance degraded 
> significantly compared to older
> versions of kernel, e.g. 6.6 LTS? Or is it that older kernels are also 
> impacted with the same sort of bug and
> currently waiting to be fixed?
> 
> I am also exploring ways to fix my bpf program so that it could work on 
> 6.19.4 and later kernels.
> It would be greatly appreciated if you could share some insights for 
> fixing bpf programs that are badly
> affected by this patch.

Hi Levi,

I'll take a detailed look tomorrow, but am curious if patch-set [1]
helps with your program? As far as I understand it is not a part of
6.19, as it was not marked as "fixes".

[1] https://lore.kernel.org/bpf/20251230-loop-stack-misc-pruning-v1-0-585cfd6cec51@gmail.com/

Thanks,
Eduard

> 
> [1]: 
> https://github.com/kxxt/tracexec/blob/main/crates/tracexec-backend-ebpf/src/bpf/tracexec_system.bpf.c
> 
> Thanks,
> Levi
> 
> > 
> > Total progs: 4172
> > Old success: 2520
> > New success: 2520
> > total_insns diff min:    0.00%
> > total_insns diff max:  221.12%
> > 0 -> value: 0
> > value -> 0: 0
> > total_insns abs max old: 837,487
> > total_insns abs max new: 837,487
> >     0 .. 5    %: 4163
> >     5 .. 15   %: 2
> >    25 .. 35   %: 2
> >    50 .. 60   %: 1
> >    60 .. 70   %: 1
> >   110 .. 120  %: 1
> >   135 .. 145  %: 1
> >   220 .. 225  %: 1
> > 
> > [1] https://lore.kernel.org/bpf/174968344350.3524559.14906547029551737094.git-patchwork-notify@kernel.org/
> > 
> > ---
> > Eduard Zingerman (2):
> >        bpf: bpf_scc_visit instance and backedges accumulation for bpf_loop()
> >        selftests/bpf: test cases for bpf_loop SCC and state graph backedges
> > 
> >   kernel/bpf/verifier.c                     | 13 ++++--
> >   tools/testing/selftests/bpf/progs/iters.c | 75 +++++++++++++++++++++++++++++++
> >   2 files changed, 84 insertions(+), 4 deletions(-)
> > ---
> > base-commit: f14cdb1367b947d373215e36cfe9c69768dbafc9
> > change-id: 20251219-scc-for-callbacks-d6d94faa2e43
> > 

Re: [PATCH 0/2] bpf: calls to bpf_loop() should have an SCC and accumulate backedges

[Levi Zim]

On 2026-03-06 16:27, Eduard Zingerman wrote:
> On Fri, 2026-03-06 at 16:20 +0800, Levi Zim wrote:
>> Hi Eduard,
>>
>> On 2025-12-30 15:13, Eduard Zingerman wrote:
>>> This is a correctness fix for the verification of BPF programs that
>>> work with callback-calling functions. The problem is the same as the
>>> issue fixed by series [1] for iterator-based loops: some of the states
>>> created while processing the callback function body might have
>>> incomplete read or precision marks.
>>>
>>> An example of an unsafe program that is accepted without this fix can
>>> be found in patch #2.
>>>
>>> There is some impact on verification performance:
>>>
>>> File                             Program               Insns (A)  Insns (B)  Insns      (DIFF)
>>> -------------------------------  --------------------  ---------  ---------  -----------------
>>> pyperf600_bpf_loop.bpf.o         on_event                   4247       9985   +5738 (+135.11%)
>>> setget_sockopt.bpf.o             skops_sockopt              5719       7446    +1727 (+30.20%)
>>> setget_sockopt.bpf.o             socket_post_create         1253       1603     +350 (+27.93%)
>>> strobemeta_bpf_loop.bpf.o        on_event                   3424       7224   +3800 (+110.98%)
>>> test_tcp_custom_syncookie.bpf.o  tcp_custom_syncookie      11929      38307  +26378 (+221.12%)
>>> xdp_synproxy_kern.bpf.o          syncookie_tc              13986      23035    +9049 (+64.70%)
>>> xdp_synproxy_kern.bpf.o          syncookie_xdp             13881      21022    +7141 (+51.44%)
>> I see that the first patch in the series causes some impact on
>> verification performance.
>> The patch contains "Fixes:" tag for two commits that landed in 6.17 kernel:
>>
>> c9e31900b54c ("bpf: propagate read/precision marks over state graph backedges")
>> 96c6aa4c63af ("bpf: compute SCCs in program control flow graph")
>>
>> I have a BPF program [1] that is badly affected by the patch that it no
>> longer loads on 6.19.5 due to
>> E2BIG error.
>>
>> The program consists of multiple nested bpf_loop calls as follows so I
>> think the impact on it is expected.
>>
>> (entry point) func trace_exec_common
>> -> (bpf_loop) callback read_strings for reading ARGV
>> -> (bpf_loop) callback read_strings for reading ENVP
>> -> (call) read_fds
>>      -> (bpf_loop) callback read_fds_impl for iterating over the fdset
>>         -> (bpf_loop) callback read_fdset_word for reading a single word in the fdset
>>             -> (call) _read_fd for getting information from a single fd
>>                 -> (call) read_send_path which reads the absolute path and mount info
>>
>>
>> After the patch, I find that I need to comment out the
>> bpf_loop(BITS_PER_LONG, read_fdset_word, &subctx, 0)
>> statement in read_fds_impl function to make the eBPF program load.
>>
>> Does it mean that after the patch, the verification performance degraded
>> significantly compared to older
>> versions of kernel, e.g. 6.6 LTS? Or is it that older kernels are also
>> impacted with the same sort of bug and
>> currently waiting to be fixed?
>>
>> I am also exploring ways to fix my bpf program so that it could work on
>> 6.19.4 and later kernels.
>> It would be greatly appreciated if you could share some insights for
>> fixing bpf programs that are badly
>> affected by this patch.
> Hi Levi,

Hi Eduard,

Thanks for your quick reply!
>
> I'll take a detailed look tomorrow, but am curious if patch-set [1]
> helps with your program? As far as I understand it is not a part of
> 6.19, as it was not marked as "fixes".

The patch-set is in v7.0-rc2 so I tested my program on v7.0-rc2 but it 
still doesn't load.
However, the logs are slightly different.

The log from v7.0-rc2 is shorter than the one I got from v6.19.4 and the 
metrics are slightly different:

 From 6.19.4:

BPF program is too large. Processed 1000001 insn
processed 1000001 insns (limit 1000000) max_states_per_insn 46 total_states 48940 peak_states 103941 mark_read 0

 From 7.0-rc2:

BPF program is too large. Processed 1000001 insn
processed 1000001 insns (limit 1000000) max_states_per_insn 55 total_states 46639 peak_states 99877 mark_read 0

So I think the patch-set helped but still couldn't make the program load 
again.

If you want me to test the patch-set by applying it on top of 6.19.4, 
feel free to tell me.

Thanks,
Levi

>
> [1] https://lore.kernel.org/bpf/20251230-loop-stack-misc-pruning-v1-0-585cfd6cec51@gmail.com/
>
> Thanks,
> Eduard
>
>> [1]:
>> https://github.com/kxxt/tracexec/blob/main/crates/tracexec-backend-ebpf/src/bpf/tracexec_system.bpf.c
>>
>> Thanks,
>> Levi
>>
>>> Total progs: 4172
>>> Old success: 2520
>>> New success: 2520
>>> total_insns diff min:    0.00%
>>> total_insns diff max:  221.12%
>>> 0 -> value: 0
>>> value -> 0: 0
>>> total_insns abs max old: 837,487
>>> total_insns abs max new: 837,487
>>>      0 .. 5    %: 4163
>>>      5 .. 15   %: 2
>>>     25 .. 35   %: 2
>>>     50 .. 60   %: 1
>>>     60 .. 70   %: 1
>>>    110 .. 120  %: 1
>>>    135 .. 145  %: 1
>>>    220 .. 225  %: 1
>>>
>>> [1] https://lore.kernel.org/bpf/174968344350.3524559.14906547029551737094.git-patchwork-notify@kernel.org/
>>>
>>> ---
>>> Eduard Zingerman (2):
>>>         bpf: bpf_scc_visit instance and backedges accumulation for bpf_loop()
>>>         selftests/bpf: test cases for bpf_loop SCC and state graph backedges
>>>
>>>    kernel/bpf/verifier.c                     | 13 ++++--
>>>    tools/testing/selftests/bpf/progs/iters.c | 75 +++++++++++++++++++++++++++++++
>>>    2 files changed, 84 insertions(+), 4 deletions(-)
>>> ---
>>> base-commit: f14cdb1367b947d373215e36cfe9c69768dbafc9
>>> change-id: 20251219-scc-for-callbacks-d6d94faa2e43
>>>

Re: [PATCH 0/2] bpf: calls to bpf_loop() should have an SCC and accumulate backedges

[Levi Zim]

On 3/6/26 5:41 PM, Levi Zim wrote:
> On 2026-03-06 16:27, Eduard Zingerman wrote:
>> On Fri, 2026-03-06 at 16:20 +0800, Levi Zim wrote:
>>> Hi Eduard,
>>>
>>> On 2025-12-30 15:13, Eduard Zingerman wrote:
>>>> This is a correctness fix for the verification of BPF programs that
>>>> work with callback-calling functions. The problem is the same as the
>>>> issue fixed by series [1] for iterator-based loops: some of the states
>>>> created while processing the callback function body might have
>>>> incomplete read or precision marks.
>>>>
>>>> An example of an unsafe program that is accepted without this fix can
>>>> be found in patch #2.
>>>>
>>>> There is some impact on verification performance:
>>>>
>>>> File                             Program               Insns (A)  Insns (B)  Insns      (DIFF)
>>>> -------------------------------  --------------------  ---------  ---------  -----------------
>>>> pyperf600_bpf_loop.bpf.o         on_event                   4247       9985   +5738 (+135.11%)
>>>> setget_sockopt.bpf.o             skops_sockopt              5719       7446    +1727 (+30.20%)
>>>> setget_sockopt.bpf.o             socket_post_create         1253       1603     +350 (+27.93%)
>>>> strobemeta_bpf_loop.bpf.o        on_event                   3424       7224   +3800 (+110.98%)
>>>> test_tcp_custom_syncookie.bpf.o  tcp_custom_syncookie      11929      38307  +26378 (+221.12%)
>>>> xdp_synproxy_kern.bpf.o          syncookie_tc              13986      23035    +9049 (+64.70%)
>>>> xdp_synproxy_kern.bpf.o          syncookie_xdp             13881      21022    +7141 (+51.44%)
>>> I see that the first patch in the series causes some impact on
>>> verification performance.
>>> The patch contains "Fixes:" tag for two commits that landed in 6.17 kernel:
>>>
>>> c9e31900b54c ("bpf: propagate read/precision marks over state graph backedges")
>>> 96c6aa4c63af ("bpf: compute SCCs in program control flow graph")
>>>
>>> I have a BPF program [1] that is badly affected by the patch that it no
>>> longer loads on 6.19.5 due to
>>> E2BIG error.
>>>
>>> The program consists of multiple nested bpf_loop calls as follows so I
>>> think the impact on it is expected.
>>>
>>> (entry point) func trace_exec_common
>>> -> (bpf_loop) callback read_strings for reading ARGV
>>> -> (bpf_loop) callback read_strings for reading ENVP
>>> -> (call) read_fds
>>>      -> (bpf_loop) callback read_fds_impl for iterating over the fdset
>>>         -> (bpf_loop) callback read_fdset_word for reading a single word in the fdset
>>>             -> (call) _read_fd for getting information from a single fd
>>>                 -> (call) read_send_path which reads the absolute path and mount info
>>>
>>>
>>> After the patch, I find that I need to comment out the
>>> bpf_loop(BITS_PER_LONG, read_fdset_word, &subctx, 0)
>>> statement in read_fds_impl function to make the eBPF program load.
>>>
>>> Does it mean that after the patch, the verification performance degraded
>>> significantly compared to older
>>> versions of kernel, e.g. 6.6 LTS? Or is it that older kernels are also
>>> impacted with the same sort of bug and
>>> currently waiting to be fixed?
>>>
>>> I am also exploring ways to fix my bpf program so that it could work on
>>> 6.19.4 and later kernels.
>>> It would be greatly appreciated if you could share some insights for
>>> fixing bpf programs that are badly
>>> affected by this patch.

I do find a workaround in the end. For my special case, I am iterating over
an fd bitmap with hand-written bpf code.

After switching [1] to using bpf_iter_bits (introduced in v6.11), the bpf program
could load again.

So it appears that after this patch, the verifier is no longer happy about my hand-written
iteration over a bitmap using bpf_loop, find_next_bit and generic___ffs.

[1]: https://github.com/kxxt/tracexec/compare/b2764f1346325546c2afc54035c9210a7cbea809...3ce0af209399add4566a4bdb316a103890d4a6b4

>> Hi Levi,
> 
> Hi Eduard,
> 
> Thanks for your quick reply!
>>
>> I'll take a detailed look tomorrow, but am curious if patch-set [1]
>> helps with your program? As far as I understand it is not a part of
>> 6.19, as it was not marked as "fixes".
> 
> The patch-set is in v7.0-rc2 so I tested my program on v7.0-rc2 but it still doesn't load.
> However, the logs are slightly different.
> 
> The log from v7.0-rc2 is shorter than the one I got from v6.19.4 and the metrics are slightly different:
> 
> From 6.19.4:
> 
> BPF program is too large. Processed 1000001 insn
> processed 1000001 insns (limit 1000000) max_states_per_insn 46 total_states 48940 peak_states 103941 mark_read 0
> 
> From 7.0-rc2:
> 
> BPF program is too large. Processed 1000001 insn
> processed 1000001 insns (limit 1000000) max_states_per_insn 55 total_states 46639 peak_states 99877 mark_read 0
> 
> So I think the patch-set helped but still couldn't make the program load again.
> 
> If you want me to test the patch-set by applying it on top of 6.19.4, feel free to tell me.
> 
> Thanks,
> Levi
> 
>>
>> [1] https://lore.kernel.org/bpf/20251230-loop-stack-misc-pruning-v1-0-585cfd6cec51@gmail.com/
>>
>> Thanks,
>> Eduard
>>
>>> [1]:
>>> https://github.com/kxxt/tracexec/blob/main/crates/tracexec-backend-ebpf/src/bpf/tracexec_system.bpf.c
>>>
>>> Thanks,
>>> Levi
>>>
>>>> Total progs: 4172
>>>> Old success: 2520
>>>> New success: 2520
>>>> total_insns diff min:    0.00%
>>>> total_insns diff max:  221.12%
>>>> 0 -> value: 0
>>>> value -> 0: 0
>>>> total_insns abs max old: 837,487
>>>> total_insns abs max new: 837,487
>>>>      0 .. 5    %: 4163
>>>>      5 .. 15   %: 2
>>>>     25 .. 35   %: 2
>>>>     50 .. 60   %: 1
>>>>     60 .. 70   %: 1
>>>>    110 .. 120  %: 1
>>>>    135 .. 145  %: 1
>>>>    220 .. 225  %: 1
>>>>
>>>> [1] https://lore.kernel.org/bpf/174968344350.3524559.14906547029551737094.git-patchwork-notify@kernel.org/
>>>>
>>>> ---
>>>> Eduard Zingerman (2):
>>>>         bpf: bpf_scc_visit instance and backedges accumulation for bpf_loop()
>>>>         selftests/bpf: test cases for bpf_loop SCC and state graph backedges
>>>>
>>>>    kernel/bpf/verifier.c                     | 13 ++++--
>>>>    tools/testing/selftests/bpf/progs/iters.c | 75 +++++++++++++++++++++++++++++++
>>>>    2 files changed, 84 insertions(+), 4 deletions(-)
>>>> ---
>>>> base-commit: f14cdb1367b947d373215e36cfe9c69768dbafc9
>>>> change-id: 20251219-scc-for-callbacks-d6d94faa2e43
>>>>
> 

Re: [PATCH 0/2] bpf: calls to bpf_loop() should have an SCC and accumulate backedges

[Barret Rhoden]

hi everyone -

On 3/6/26 3:27 AM, Eduard Zingerman wrote:
> On Fri, 2026-03-06 at 16:20 +0800, Levi Zim wrote:

...

>> I have a BPF program [1] that is badly affected by the patch that it no
>> longer loads on 6.19.5 due to
>> E2BIG error.
...

> 
> I'll take a detailed look tomorrow, but am curious if patch-set [1]
> helps with your program? As far as I understand it is not a part of
> 6.19, as it was not marked as "fixes".
> 
> [1] https://lore.kernel.org/bpf/20251230-loop-stack-misc-pruning-v1-0-585cfd6cec51@gmail.com/
> 
i'm in a similar situation - my scheduling program, which uses 
bpf_loop(), won't load with the dreaded E2BIG:

	processed 1000001 insns (limit 1000000) max_states_per_insn 76
	total_states 59608 peak_states 171016 mark_read 0

i tried the patch at [1], and no luck there either.

are there any tricks with this new SCC stuff to help with verification?

thanks,
barret

Re: [PATCH 0/2] bpf: calls to bpf_loop() should have an SCC and accumulate backedges

[Eduard Zingerman]

On Fri, 2026-03-27 at 12:41 -0700, Barret Rhoden wrote:
> hi everyone -
>
> On 3/6/26 3:27 AM, Eduard Zingerman wrote:
> > On Fri, 2026-03-06 at 16:20 +0800, Levi Zim wrote:
>
> ...
>
> > > I have a BPF program [1] that is badly affected by the patch that it no
> > > longer loads on 6.19.5 due to
> > > E2BIG error.
> ...
>
> >
> > I'll take a detailed look tomorrow, but am curious if patch-set [1]
> > helps with your program? As far as I understand it is not a part of
> > 6.19, as it was not marked as "fixes".
> >
> > [1] https://lore.kernel.org/bpf/20251230-loop-stack-misc-pruning-v1-0-585cfd6cec51@gmail.com/
> >
> i'm in a similar situation - my scheduling program, which uses
> bpf_loop(), won't load with the dreaded E2BIG:
>
> 	processed 1000001 insns (limit 1000000) max_states_per_insn 76
> 	total_states 59608 peak_states 171016 mark_read 0
>
> i tried the patch at [1], and no luck there either.
>
> are there any tricks with this new SCC stuff to help with verification?

Hi Barret,

Is it possible for you to share the program code?
If not, here are a few generic tips:
- If there is bpf_for or bpf_loop based loop and you hit 1M
  instructions limit, this means that internal loop state does not
  converge to some previously visited state from verifier point of
  view.
- Most likely there is a pattern like this:

    v = 0;                            v = 0;
    bpf_for(i, ...) {                 bpf_for(i, ...) {
      ...                               ...
      v += 1;                - or -     v += 1;
    }                                   use v for memory access
    use v for memory access.          }

  Or its equivalent in bpf_loop terms.
  'v' might also be a pointer incremented inside a loop.
  Unfortunately, we don't have a simple way to identify which variable
  is a culprit. We do have a way to identify which loop fails to converge:
  the 'veristat' tool executed with --top-src-lines=N option will
  print out C lines corresponding to instructions that verifier
  visited most-often before giving up.
- There are several possible remedies for the pattern above:
  - hide exact value of 'v' from verifier by initializing
    it using a global, see tools/testing/selftests/bpf/progs/arena_htab.c
    variable 'zero'.
  - change the logic to rely on 'i' instead of 'v',
    for 'i' verifier does not know exact value, but knows its range.
- Another generic advice is to split program into global subprograms.
  Global subprograms called from the loop body won't inflate the callers
  verification budget.

It is hard to provide more specific advice w/o seeing the program
code.

Thanks,
Eduard

P.S.
  I know that loops handling is a major pita, we are working on a
  solution but it's a complex problem.

Re: [PATCH 0/2] bpf: calls to bpf_loop() should have an SCC and accumulate backedges

[Barret Rhoden]

On 3/27/26 3:41 PM, Barret Rhoden wrote:
> are there any tricks with this new SCC stuff to help with verification?

i was able to work around it, at least for now, by taking the guts of 
whatever i was calling from within bpf_loop() and making it a global 
function, thereby making the loop function easy to verify.

hope i don't run out of stack space or depth...  =)

please let me know if you have any other tips for bpf_loop().

thanks,

barret

Re: [PATCH 0/2] bpf: calls to bpf_loop() should have an SCC and accumulate backedges

[Alexei Starovoitov]

On Fri, Mar 27, 2026 at 1:10 PM Barret Rhoden <brho@google.com> wrote:
>
> On 3/27/26 3:41 PM, Barret Rhoden wrote:
> > are there any tricks with this new SCC stuff to help with verification?
>
> i was able to work around it, at least for now, by taking the guts of
> whatever i was calling from within bpf_loop() and making it a global
> function, thereby making the loop function easy to verify.
>
> hope i don't run out of stack space or depth...  =)
>
> please let me know if you have any other tips for bpf_loop().

See Ed's reply.

I'll double down on request to share your prog that hits 1M.
We're working on removing the limit completely,
so the more tests the better.

Re: [PATCH 0/2] bpf: calls to bpf_loop() should have an SCC and accumulate backedges

[Barret Rhoden]

On 3/27/26 4:10 PM, Eduard Zingerman wrote:?
> If not, here are a few generic tips:
> - If there is bpf_for or bpf_loop based loop and you hit 1M
>    instructions limit, this means that internal loop state does not
>    converge to some previously visited state from verifier point of
>    view.
> - Most likely there is a pattern like this:
> 
>      v = 0;                            v = 0;
>      bpf_for(i, ...) {                 bpf_for(i, ...) {
>        ...                               ...
>        v += 1;                - or -     v += 1;
>      }                                   use v for memory access
>      use v for memory access.          }
> 
>    Or its equivalent in bpf_loop terms.
>    'v' might also be a pointer incremented inside a loop.
>    Unfortunately, we don't have a simple way to identify which variable
>    is a culprit. We do have a way to identify which loop fails to converge:
>    the 'veristat' tool executed with --top-src-lines=N option will
>    print out C lines corresponding to instructions that verifier
>    visited most-often before giving up.
> - There are several possible remedies for the pattern above:
>    - hide exact value of 'v' from verifier by initializing
>      it using a global, see tools/testing/selftests/bpf/progs/arena_htab.c
>      variable 'zero'.
>    - change the logic to rely on 'i' instead of 'v',
>      for 'i' verifier does not know exact value, but knows its range.
> - Another generic advice is to split program into global subprograms.
>    Global subprograms called from the loop body won't inflate the callers
>    verification budget.

great tips, thanks!  i opted for the global function one; it's a common 
sledgehammer in my "fight the verifier" toolkit.  =)

the loop function was calling a very large function, so that was 
probably the right tool for the job.  next time i'll take a look at 
veristat.

thanks,

barret

Re: [PATCH 0/2] bpf: calls to bpf_loop() should have an SCC and accumulate backedges

[Barret Rhoden]

On 3/27/26 9:29 PM, Alexei Starovoitov wrote:
> 
> See Ed's reply.

thanks for the hints!

> I'll double down on request to share your prog that hits 1M.
> We're working on removing the limit completely,
> so the more tests the better.

unfortunately, i can't easily do that since the program hooks into 
ghost's BPF prog_types and not sched_ext's.

that said, we're working on porting my "flux" framework (which is what 
my scheduler uses) to sched_ext.  so one of these days we'll have 
something you can build.

thanks,
barret

Re: [PATCH 0/2] bpf: calls to bpf_loop() should have an SCC and accumulate backedges

[Emil Tsalapatis]

On Fri Mar 27, 2026 at 4:10 PM EDT, Barret Rhoden wrote:
> On 3/27/26 3:41 PM, Barret Rhoden wrote:
>> are there any tricks with this new SCC stuff to help with verification?
>
> i was able to work around it, at least for now, by taking the guts of 
> whatever i was calling from within bpf_loop() and making it a global 
> function, thereby making the loop function easy to verify.
>
> hope i don't run out of stack space or depth...  =)
>

Late reply, but while in bpf-next there are still stack space
limitations, the maximum call depth of 8 is now gone as of commit
6c8e1a9eee0.

> please let me know if you have any other tips for bpf_loop().
>
> thanks,
>
> barret

Re: [PATCH 0/2] bpf: calls to bpf_loop() should have an SCC and accumulate backedges

[Barret Rhoden]

On 4/3/26 5:58 PM, Emil Tsalapatis wrote:
> Late reply, but while in bpf-next there are still stack space
> limitations, the maximum call depth of 8 is now gone as of commit
> 6c8e1a9eee0.

sweet, thanks!