bpf: calls to bpf_loop() should have an SCC and accumulate backedges
Subsystems (4)
Eduard Zingerman
maintainercover 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: 0total_insns abs max old: 837,487total_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
---
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
Eduard Zingerman
maintainerPATCH 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.
--- kernel/bpf/verifier.c | 13 +++++++++---- 1 file changed, 9 insertions(+), 4 deletions(-)
kernel/bpf/verifier.c +9 -4
@@ -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
Re: [PATCH 1/2] bpf: bpf_scc_visit instance and backedges accumulation for bpf_loop()
Quoted 11 lines · Eduard Zingerman
Calls like
bpf_loop()orbpf_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_visitinstance 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")Reported-by Breno Leitao <[email protected]>Signed-off-by Eduard Zingerman <[email protected]>
Eduard Zingerman
maintainerPATCH 2/2 selftests/bpf: test cases for bpf_loop SCC and state graph backedges
In reply to Eduard ZingermanTest 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
@@ -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; +* } +*/ + asmvolatile ( +"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 ) +{ + asmvolatile ( +"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
Eduard Zingerman
maintainerQuoted 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.
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
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 infoAfter 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.
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: 0total_insnsabs max old: 837,487total_insnsabs max new: 837,4870 .. 5 %: 4163 5 .. 15 %: 2 25 .. 35 %: 2 50 .. 60 %: 1 60 .. 70 %: 1 110 .. 120 %: 1 135 .. 145 %: 1 220 .. 225 %: 1---
Eduard Zingerman (2):
bpf:bpf_scc_visitinstance and backedges accumulation forbpf_loop()selftests/bpf: test cases forbpf_loopSCC and state graph backedgeskernel/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
Eduard Zingerman
maintainerQuoted 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_loopcalls as follows so I think the impact on it is expected.(entry point) func
trace_exec_common
-> (bpf_loop) callbackread_stringsfor reading ARGV -> (bpf_loop) callbackread_stringsfor 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 infoAfter the patch, I find that I need to comment out the
bpf_loop(BITS_PER_LONG, read_fdset_word, &subctx, 0)statement inread_fds_implfunction 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
Thanks,
LeviQuoted 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: 0total_insnsabs max old: 837,487total_insnsabs max new: 837,4870 .. 5 %: 4163 5 .. 15 %: 2 25 .. 35 %: 2 50 .. 60 %: 1 60 .. 70 %: 1 110 .. 120 %: 1 135 .. 145 %: 1 220 .. 225 %: 1---
Eduard Zingerman (2):
bpf:bpf_scc_visitinstance and backedges accumulation forbpf_loop()selftests/bpf: test cases forbpf_loopSCC and state graph backedgeskernel/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
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_loopcalls as follows so I think the impact on it is expected.(entry point) func
trace_exec_common
-> (bpf_loop) callbackread_stringsfor reading ARGV -> (bpf_loop) callbackread_stringsfor 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 infoAfter the patch, I find that I need to comment out the
bpf_loop(BITS_PER_LONG, read_fdset_word, &subctx, 0)statement inread_fds_implfunction 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,
EduardQuoted 38 lines
Thanks,
LeviQuoted 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: 0total_insnsabs max old: 837,487total_insnsabs max new: 837,4870 .. 5 %: 4163 5 .. 15 %: 2 25 .. 35 %: 2 50 .. 60 %: 1 60 .. 70 %: 1 110 .. 120 %: 1 135 .. 145 %: 1 220 .. 225 %: 1---
Eduard Zingerman (2):
bpf:bpf_scc_visitinstance and backedges accumulation forbpf_loop()selftests/bpf: test cases forbpf_loopSCC and state graph backedgeskernel/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
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_loopcalls as follows so I think the impact on it is expected.(entry point) func
trace_exec_common
-> (bpf_loop) callbackread_stringsfor reading ARGV
-> (bpf_loop) callbackread_stringsfor reading ENVP
-> (call)read_fds
-> (bpf_loop) callbackread_fds_implfor iterating over the fdset -> (bpf_loop) callbackread_fdset_wordfor reading a single word in the fdset -> (call)_read_fdfor getting information from a single fd -> (call)read_send_pathwhich reads the absolute path and mount infoAfter the patch, I find that I need to comment out the
bpf_loop(BITS_PER_LONG, read_fdset_word, &subctx, 0)statement inread_fds_implfunction 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.
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_insn46total_states48940peak_states103941mark_read0From 7.0-rc2:
BPF program is too large. Processed 1000001 insn
processed 1000001 insns (limit 1000000)max_states_per_insn55total_states46639peak_states99877mark_read0So 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,
LeviQuoted 44 lines
[1] https://lore.kernel.org/bpf/[email protected]/
Thanks,
EduardQuoted 38 lines
Thanks,
LeviQuoted 32 lines
Total progs: 4172
Old success: 2520
New success: 2520total_insnsdiff min: 0.00%total_insnsdiff max: 221.12%
0 -> value: 0
value -> 0: 0total_insnsabs max old: 837,487total_insnsabs 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---
Eduard Zingerman (2):
bpf:bpf_scc_visitinstance and backedges accumulation forbpf_loop()selftests/bpf: test cases forbpf_loopSCC and state graph backedgeskernel/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
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".
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
Eduard Zingerman
maintainerQuoted 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".
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 0i 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.
On 3/27/26 4:10 PM, Eduard Zingerman wrote:?
Quoted 14 lines
If not, here are a few generic tips:
- If there isbpf_fororbpf_loopbased 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_loopterms.
'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, seetools/testing/selftests/bpf/progs/arena_htab.cvariable '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
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
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.
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
Emil Tsalapatis
reviewerQuoted 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
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!