Skip to contentSkip to conversation

bpf: calls to bpf_loop() should have an SCC and accumulate backedges

PATCH Applied Eduard Zingerman 7 participants 18 messages Dec 30, 2025 – Apr 4

Subsystems (4)
lore
Share & tools
lore

Eduard Zingerman

author maintainer
#0 lore raw

cover bpf: calls to bpf_loop() should have an SCC and accumulate backedges

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

author maintainer
#1 lore raw

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

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")
---
 kernel/bpf/verifier.c | 13 +++++++++----
 1 file changed, 9 insertions(+), 4 deletions(-)
kernel/bpf/verifier.c +9 -4
index 2de1a736ef69514fcf599de498aae56eaf24fe33..0baae7828af220accd4086b9bad270e745f4aff9 100644
@@ -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];
Signature · 1 line
2.52.0
Tested-by on v1 1/2
#2 lore raw

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

Quoted 11 lines · 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.

Quoted 7 lines

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")
author maintainer
#3 lore raw

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

In reply to 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.

---
 tools/testing/selftests/bpf/progs/iters.c | 75 +++++++++++++++++++++++++++++++
 1 file changed, 75 insertions(+)
tools/testing/selftests/bpf/progs/iters.c +75 -0
index 7dd92a303bf6b3f0fc2962f6ce6cc453350561e3..69061f0309579eada74e5f2a68640470ff94a8b3 100644
@@ -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";
Signature · 1 line
2.52.0
author maintainer
#4 lore raw
In reply to Eduard Zingerman
Quoted 5 lines · 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.

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.

#5 lore raw
In reply to Eduard Zingerman
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:

Hello:

This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:

Quoted 10 lines · 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!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html
#6 lore raw
In reply to Eduard Zingerman

Hi Eduard,

Quoted 11 lines · 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:

Quoted 9 lines
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

Quoted 33 lines
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

author maintainer
#7 lore raw
Quoted 58 lines · Levi Zim

Hi Eduard,

Quoted 11 lines · 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:

Quoted 9 lines
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?

Quoted 5 lines

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/[email protected]/

Thanks,
Eduard

Quoted 40 lines

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

Thanks,
Levi

Quoted 33 lines
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

#8 lore raw
Quoted 58 lines · Eduard Zingerman
Quoted 57 lines · Levi Zim

Hi Eduard,

Quoted 11 lines · 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:

Quoted 9 lines
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?

Quoted 6 lines
Quoted 5 lines

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!

Quoted 4 lines

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

Quoted 44 lines

[1] https://lore.kernel.org/bpf/[email protected]/

Thanks,
Eduard

Quoted 38 lines

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

Thanks,
Levi

Quoted 32 lines
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

#9 lore raw
Quoted 59 lines · Levi Zim
Quoted 58 lines · Eduard Zingerman
Quoted 57 lines · Levi Zim

Hi Eduard,

Quoted 11 lines · 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:

Quoted 9 lines

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?

Quoted 5 lines
Quoted 5 lines
Quoted 5 lines

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

Quoted 77 lines
Quoted 1 line

Hi Levi,

Hi Eduard,

Thanks for your quick reply!

Quoted 4 lines

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

Quoted 44 lines

[1] https://lore.kernel.org/bpf/[email protected]/

Thanks,
Eduard

Quoted 38 lines

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

Thanks,
Levi

Quoted 32 lines

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

#10 lore raw
In reply to Eduard Zingerman

hi everyone -

Quoted 1 line · Eduard Zingerman

On Fri, 2026-03-06 at 16:20 +0800, Levi Zim wrote:

...

Quoted 3 lines
Quoted 3 lines

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.

...

Quoted 7 lines

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/[email protected]/

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

author maintainer
#11 lore raw
Quoted 22 lines · Barret Rhoden

hi everyone -

Quoted 1 line · Eduard Zingerman

On Fri, 2026-03-06 at 16:20 +0800, Levi Zim wrote:

...

Quoted 3 lines
Quoted 3 lines

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.

...

Quoted 7 lines

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/[email protected]/

i'm in a similar situation - my scheduling program, which uses bpf_loop(), won't load with the dreaded E2BIG:

Quoted 6 lines
	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.

#12 lore raw

On 3/27/26 4:10 PM, Eduard Zingerman wrote:?

Quoted 14 lines

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.          }
Quoted 16 lines

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

#13 lore raw
In reply to Barret Rhoden
Quoted 1 line · Barret Rhoden

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

#14 lore raw
Quoted 11 lines · Barret Rhoden
Quoted 1 line · Barret Rhoden

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.

#15 lore raw
Quoted 2 lines · Alexei Starovoitov

See Ed's reply.

thanks for the hints!

Quoted 3 lines

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

#16 lore raw
In reply to Barret Rhoden
Quoted 9 lines · Barret Rhoden
Quoted 1 line · Barret Rhoden

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.

Quoted 5 lines

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

thanks,

barret

#17 lore raw
Quoted 3 lines · Emil Tsalapatis

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!