bpf: better error reporting when verifier hits 1M instructions limit
Subsystems (4)
Eduard Zingerman
maintainerv2 cover bpf: better error reporting when verifier hits 1M instructions limit
When the BPF verifier exceeds the 1M instruction budget, the current error output shows a random execution trace that happens to be active at the moment, which is not very helpful for debugging.
This series improves the error report using a profiler-inspired
approach: collect and count "callchain" stack traces that the verifier visits during program validation, and report the top 3 hottest traces when the budget is exhausted. To minimize performance an memory impact of such profiling, only collect samples when verifier visits loop headers, iterator next, may_goto and callback-calling instructions.
For callchains ending at iterator next, may_goto, or callback-calling instructions, identify which registers or stack slots most frequently differ between cached and current states.
Here is an example of the report for scx lavd_dispatch, with verifier limited to 200K instructions to trigger the error:
lavd_dispatch():
; void BPF_STRUCT_OPS(lavd_dispatch, s32 cpu, struct task_struct *prev) @ main.bpf.c:889 ... disassembly ...
consume_task():
; bool consume_task(u64 cpu_dsq_id, u64 cpdom_dsq_id) @ balance.bpf.c:410
... disassembly ...#1 most visited simulated stacktrace (visited 1807 times):
lavd_dispatch/124 (.../scx/scheds/rust/scx_lavd/src/bpf/main.bpf.c:1107)
consume_task/2715 (.../scx/scheds/rust/scx_lavd/src/bpf/balance.bpf.c:316)#2 most visited simulated stacktrace (visited 1682 times):
lavd_dispatch/124 (.../scx/scheds/rust/scx_lavd/src/bpf/main.bpf.c:1107)
consume_task/2994 (.../scx/scheds/rust/scx_lavd/src/bpf/balance.bpf.c:386) #3 most visited simulated stacktrace (visited 8 times):
lavd_dispatch/255 (.../scx/scheds/rust/scx_lavd/src/bpf/main.bpf.c:1022)
Most varying: R7 (frame 0)
BPF program is too large. Processed 200001 insn
Changelog:
v1 -> v2 (bots):
- Use kvfree() in bpf_compute_loops().
- Adjust fwd_edges_no_loop test case to avoid dead code elimination converting 'if' to 'goto'.
- Use GFP_KERNEL_ACCOUNT for callchain entry allocation in update_callchain_profile().
- Zero-initialize 'cc' in update_callchain_profile() to avoid copying uninitialized stack memory to the heap.
- Use %td instead of %ld for ptrdiff_t format specifier in print_callchain_entry() and disasm_subprog().
- Size printed_subs bitmap as BPF_MAX_SUBPROGS + 2 to account for fake and exception subprograms.
- Fix bpf_sample_state_diffs() inner loop to iterate from head instead of pos_i, avoiding container_of() on the dummy list head.
- Add DIFF_OTHER to distinguish states that differ because of idmap or other inconsistencies.
v1: https://lore.kernel.org/bpf/[email protected]/T/
---
Eduard Zingerman (6):
bpf: move live registers and scc printout to a standalone function
bpf: compute loops hierarchy
selftests/bpf: test cases for loop hierarchy computation
bpf: report hot simulated callchains when 1M instructions limit is met
bpf: report register diff summary for hot callchains
selftests/bpf: test budget exhaustion profiling report
include/linux/bpf_verifier.h | 39 ++++ kernel/bpf/Makefile | 2 +- kernel/bpf/fixups.c | 5 + kernel/bpf/liveness.c | 22 +- kernel/bpf/loops.c | 184 ++++++++++++++++ kernel/bpf/states.c | 180 ++++++++++++++-- kernel/bpf/verifier.c | 233 +++++++++++++++++++++ tools/testing/selftests/bpf/prog_tests/verifier.c | 4 + .../selftests/bpf/progs/verifier_budget_report.c | 175 ++++++++++++++++ .../selftests/bpf/progs/verifier_live_stack.c | 2 +- .../selftests/bpf/progs/verifier_loop_hierarchy.c | 233 +++++++++++++++++++++ 11 files changed, 1034 insertions(+), 45 deletions(-)
---
base-commit: 8496d9020ff37a33c2a7b2fc84350fd03ffbde78
change-id: 20260525-better-1m-reporting-1d795a21cf72
Eduard Zingerman
maintainerRFC PATCH v2 1/6 bpf: move live registers and scc printout to a standalone function
Tests for multiple analyses performed by the verifier need the verifier log to contain analysis results alongside the program disassembly. This patch moves log level 2 program dump from bpf_compute_live_registers() to a standalone function called from bpf_check(), in order to provide a common logging function for such analyses (and thus avoid printing program disassembly multiple times).
This is a preparatory refactoring, subsequent commit extends this log with loop hierarchy.
--- kernel/bpf/liveness.c | 22 +-------------- kernel/bpf/verifier.c | 31 ++++++++++++++++++++++ .../selftests/bpf/progs/verifier_live_stack.c | 2 +- 3 files changed, 33 insertions(+), 22 deletions(-)
kernel/bpf/liveness.c +1 -21
@@ -2209,7 +2209,7 @@ int bpf_compute_live_registers(struct bpf_verifier_env *env)struct bpf_insn *insns = env->prog->insnsi;struct insn_live_regs *state;int insn_cnt = env->prog->len; -int err =0 , i, j; +int err =0 , i;bool changed;/* Use the following algorithm:
@@ -2270,26 +2270,6 @@ int bpf_compute_live_registers(struct bpf_verifier_env *env)for (i =0 ; i < insn_cnt; ++i) insn_aux[i].live_regs_before = state[i].in; -if (env->log.level &BPF_LOG_LEVEL2 ) { -verbose (env,"Live regs before insn:\n" ); -for (i =0 ; i < insn_cnt; ++i) { -if (env->insn_aux_data[i].scc) -verbose (env,"%3d " , env->insn_aux_data[i].scc); -else -verbose (env," " ); -verbose (env,"%3d: " , i); -for (j =BPF_REG_0 ; j <BPF_REG_10 ; ++j) -if (insn_aux[i].live_regs_before &BIT (j)) -verbose (env,"%d" , j); -else -verbose (env,"." ); -verbose (env," " ); -bpf_verbose_insn (env, &insns[i]); -if (bpf_is_ldimm64 (&insns[i])) - i++; - } - } - out:kvfree (state);return err;
kernel/bpf/verifier.c +31 -0
@@ -19619,6 +19619,34 @@ int bpf_fixup_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,return 0 ; } +/* Various log level 2 information about the program */ +static void log_program (struct bpf_verifier_env *env) +{ +struct bpf_insn_aux_data *insn_aux = env->insn_aux_data; +struct bpf_insn *insns = env->prog->insnsi; +u32 insn_cnt = env->prog->len; +u32 i, j; + +verbose (env,"Program dump (scc? insn#: live_regs_before):\n" ); +for (i =0 ; i < insn_cnt; ++i) { +verbose_linfo (env, i," ; " ); +if (env->insn_aux_data[i].scc) +verbose (env,"%3d " , env->insn_aux_data[i].scc); +else +verbose (env," " ); +verbose (env,"%3d: " , i); +for (j =BPF_REG_0 ; j <BPF_REG_10 ; ++j) +if (insn_aux[i].live_regs_before &BIT (j)) +verbose (env,"%d" , j); +else +verbose (env,"." ); +verbose (env," " ); +bpf_verbose_insn (env, &insns[i]); +if (bpf_is_ldimm64 (&insns[i])) + i++; + } +} +int bpf_check (struct bpf_prog **prog,union bpf_attr *attr,bpfptr_t uattr,struct bpf_log_attr *attr_log) {
@@ -19771,6 +19799,9 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr,if (ret <0 ) goto skip_full_check; +if (env->log.level &BPF_LOG_LEVEL2 ) +log_program (env); + ret =mark_fastcall_patterns (env);if (ret <0 ) goto skip_full_check;
tools/testing/selftests/bpf/progs/verifier_live_stack.c +1 -1
@@ -64,7 +64,7 @@ SEC("socket") __log_level(2) __msg("stack use/def subprog#0 must_write_not_same_slot (d0,cs0):") __msg("6: (7b) *(u64 *)(r2 +0) = r0{{$}}") -__msg("Live regs before insn:") +__msg("Program dump")__naked void must_write_not_same_slot (void ) { asm volatile (
Signature · 1 line
2.54.0
Eduard Zingerman
maintainerRFC PATCH v2 2/6 bpf: compute loops hierarchy
In reply to Eduard ZingermanAdd an analysis phase computing the loops hierarchy to the bpf verifier. The algorithm is based on the paper:
"A New Algorithm for Identifying Loops in Decompilation" by Wei et al, adapted to be non-recursive.
Record the loops hierarchy per instruction:
- The field insn_aux_data->loop_header records the innermost loop header containing it.
- The field insn_aux_data->loop records additional information about the loop if this instruction is a loop header (at the moment it only tracks irreduciblity of the loop, additional information will be added later).
Subsequent patches use loop header entries as sampling points for callchain profiling, for better error reports when the 1M instruction budget is exhausted.
--- include/linux/bpf_verifier.h | 10 +++ kernel/bpf/Makefile | 2 +- kernel/bpf/fixups.c | 5 ++ kernel/bpf/loops.c | 184 +++++++++++++++++++++++++++++++++++++++++++ kernel/bpf/verifier.c | 10 ++- 5 files changed, 209 insertions(+), 2 deletions(-)
include/linux/bpf_verifier.h +10 -0
@@ -656,6 +656,10 @@ struct bpf_iarray {u32 items[]; }; +struct bpf_loop { +bool irreducible; +}; +struct bpf_insn_aux_data {union {enum bpf_reg_type ptr_type;/* pointer type for load/store insns */
@@ -742,6 +746,10 @@ struct bpf_insn_aux_data {u16 const_reg_map_mask;u16 const_reg_subprog_mask;u32 const_reg_vals[10 ]; +/* index of a loop header of the innermost loop containing this instruction, -1 if none */ +s32 loop_header; +/* additional information about the loop if this instruction is a loop header */ +struct bpf_loop *loop; };#define MAX_USED_MAPS 64/* max number of maps accessed by one eBPF program */
@@ -1608,4 +1616,6 @@ int bpf_jit_subprogs(struct bpf_verifier_env *env);int bpf_fixup_call_args (struct bpf_verifier_env *env);int bpf_do_misc_fixups (struct bpf_verifier_env *env); +int bpf_compute_loops (struct bpf_verifier_env *env); +#endif /* _LINUX_BPF_VERIFIER_H */
kernel/bpf/Makefile +1 -1
@@ -6,7 +6,7 @@ cflags-nogcse-$(CONFIG_X86)$(CONFIG_CC_IS_GCC) := -fno-gcse endif CFLAGS_core.o += -Wno-override-init $(cflags-nogcse-yy) -obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o inode.o helpers.o tnum.o cnum.o log.o token.o liveness.o const_fold.o +obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o inode.o helpers.o tnum.o cnum.o log.o token.o liveness.o const_fold.o loops.o obj-$(CONFIG_BPF_SYSCALL) += bpf_iter.o map_iter.o task_iter.o prog_iter.o link_iter.o obj-$(CONFIG_BPF_SYSCALL) += hashtab.o arraymap.o percpu_freelist.o bpf_lru_list.o lpm_trie.o map_in_map.o bloom_filter.o obj-$(CONFIG_BPF_SYSCALL) += local_storage.o queue_stack_maps.o ringbuf.o bpf_insn_array.o
kernel/bpf/fixups.c +5 -0
@@ -450,6 +450,11 @@ void bpf_clear_insn_aux_data(struct bpf_verifier_env *env, int start, int len) aux_data[i].jt =NULL ; } +if (aux_data[i].loop) { +kvfree (aux_data[i].loop); + aux_data[i].loop =NULL ; + } +if (bpf_is_ldimm64 (&insns[i])) i++; }
kernel/bpf/loops.c new file +184 -0
184 lines not on this page · raw message
kernel/bpf/verifier.c +9 -1
@@ -19627,13 +19627,17 @@ static void log_program(struct bpf_verifier_env *env)u32 insn_cnt = env->prog->len;u32 i, j; -verbose (env,"Program dump (scc? insn#: live_regs_before):\n" ); +verbose (env,"Program dump (scc? loop_header? insn#: live_regs_before):\n" );for (i =0 ; i < insn_cnt; ++i) {verbose_linfo (env, i," ; " );if (env->insn_aux_data[i].scc)verbose (env,"%3d " , env->insn_aux_data[i].scc);else verbose (env," " ); +if (env->insn_aux_data[i].loop_header >=0 ) +verbose (env,"%3d " , env->insn_aux_data[i].loop_header); +else +verbose (env," " );verbose (env,"%3d: " , i);for (j =BPF_REG_0 ; j <BPF_REG_10 ; ++j)if (insn_aux[i].live_regs_before &BIT (j))
@@ -19791,6 +19795,10 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr,if (ret <0 ) goto skip_full_check; + ret =bpf_compute_loops (env); +if (ret <0 ) + goto skip_full_check; + ret =bpf_compute_scc (env);if (ret <0 ) goto skip_full_check;
Signature · 1 line
2.54.0
[email protected]
AI reviewRe: [PATCH RFC bpf-next v2 2/6] bpf: compute loops hierarchy
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider: - [High] Worst-case O(N^2) algorithmic complexity in assign_header() lacking cond_resched() leads to soft…
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] Worst-case O(N^2) algorithmic complexity in assign_header() lacking cond_resched() leads to soft lockup. --
commit 5ba437ec70f22b36c162a26467753448539086e8
Author: Eduard Zingerman <[email protected]>
bpf: compute loops hierarchy
This commit introduces an analysis phase to the bpf verifier that computes the loops hierarchy using a non-recursive adaptation of the Wei et al. algorithm. It records the innermost loop header per instruction to be used as sampling points for callchain profiling.
Quoted 5 lines
kernel/bpf/loops.c new file +0
-0
[ ... ]
Quoted 17 lines
kernel/bpf/loops.c new file +17
-0+static int assign_header (struct bpf_verifier_env *env,struct loops_dfs *dfs,int n,int h) +{ +struct bpf_insn_aux_data *aux = env->insn_aux_data; +int *dfs_pos = dfs->dfs_pos; +int err, nh; + + err =mark_header (env, h); +if (err) +return err; + +/* Don't encode self-loops, otherwise can't reflect loops nesting structure. */ +if (n == h) +return 0 ; + +/* Make sure that loop headers up the chain are sorted by dfs_pos. */ +while (aux[n].loop_header !=-1 ) { + nh = aux[n].loop_header;
kernel/bpf/loops.c line 61
Quoted 10 lines
kernel/bpf/loops.c new file +10
-0+if (nh == h) +return 0 ; +if (dfs_pos[nh] < dfs_pos[h]) { + aux[n].loop_header = h; + n = h; + h = nh; + }else { + n = nh; + } + }
[Severity: High]
Could this while loop lead to a cpu soft lockup under specific pathological conditions?
With deeply nested loops and cross-edges, it appears possible to force repeated O(n) traversals of this header chain for O(n) nodes without actually modifying the chain. Given the 1 million bpf instruction limit, this worst-case O(n^2) algorithmic complexity might result in a massive number of iterations.
Because neither this chain traversal nor the surrounding search algorithm in compute_loops_in_subprog() seem to call cond_resched(), does this risk stalling the cpu core long enough to trigger a system soft lockup or a local denial of service?
Quoted 3 lines
kernel/bpf/loops.c new file +3
-0+ aux[n].loop_header = h; +return 0 ; +}
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=2
Eduard Zingerman
maintainerRe: [PATCH RFC bpf-next v2 2/6] bpf: compute loops hierarchy
Quoted 60 lines · On Tue, 2026-05-26 at 20:26 +0000, [email protected] wrote:
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] Worst-case O(N^2) algorithmic complexity inassign_header()lackingcond_resched()leads to soft lockup. --commit
5ba437ec70f22b36c162a26467753448539086e8
Author: Eduard Zingerman <[email protected]>bpf: compute loops hierarchy
This commit introduces an analysis phase to the bpf verifier that computes the loops hierarchy using a non-recursive adaptation of the Wei et al. algorithm. It records the innermost loop header per instruction to be used as sampling points for callchain profiling.
Quoted 5 lines
kernel/bpf/loops.c new file +0
-0[ ... ]
Quoted 17 lines
kernel/bpf/loops.c new file +17
-0+static int assign_header (struct bpf_verifier_env *env,struct loops_dfs *dfs,int n,int h) +{ +struct bpf_insn_aux_data *aux = env->insn_aux_data; +int *dfs_pos = dfs->dfs_pos; +int err, nh; + + err =mark_header (env, h); +if (err) +return err; + +/* Don't encode self-loops, otherwise can't reflect loops nesting structure. */ +if (n == h) +return 0 ; + +/* Make sure that loop headers up the chain are sorted by dfs_pos. */ +while (aux[n].loop_header !=-1 ) { + nh = aux[n].loop_header;kernel/bpf/loops.c line 61
Quoted 10 lines
kernel/bpf/loops.c new file +10
-0+if (nh == h) +return 0 ; +if (dfs_pos[nh] < dfs_pos[h]) { + aux[n].loop_header = h; + n = h; + h = nh; + }else { + n = nh; + } + }[Severity: High]
Could this while loop lead to a cpu soft lockup under specific pathological conditions?With deeply nested loops and cross-edges, it appears possible to force repeated O(n) traversals of this header chain for O(n) nodes without actually modifying the chain. Given the 1 million bpf instruction limit, this worst-case O(n^2) algorithmic complexity might result in a massive number of iterations.
Quoted 4 lines
Because neither this chain traversal nor the surrounding search algorithm in
compute_loops_in_subprog()seem to callcond_resched(), does this risk stalling the cpu core long enough to trigger a system soft lockup or a local denial of service?
This is a known algorithmic trade off, favoring implementation simplicity. Neither paper authors nor me hit the pathological case why testing with real-life programs. Some safeguard counter can be added if people feel paranoid.
Quoted 3 lines
Quoted 3 lines
kernel/bpf/loops.c new file +3
-0+ aux[n].loop_header = h; +return 0 ; +}
Eduard Zingerman
maintainerRFC PATCH v2 3/6 selftests/bpf: test cases for loop hierarchy computation
In reply to Eduard ZingermanTest cases covering the following branches in bpf_compute_loops():
- Case B: simple backedge creating a loop (loop_single)
- Case B: two independent loops (loop_two_independent)
- Case B + D: nested loops where inner header's loop_header points to outer (loop_nested)
- Case C: diamond CFG with no loops (fwd_edges_no_loop)
- Case D: sibling inner loops within one outer loop (loop_nested_siblings)
- Three levels of loop nesting (loop_three_levels)
- Loop with if-else body containing forward branches (loop_with_if_else)
--- tools/testing/selftests/bpf/prog_tests/verifier.c | 2 + .../selftests/bpf/progs/verifier_loop_hierarchy.c | 233 +++++++++++++++++++++ 2 files changed, 235 insertions(+)
tools/testing/selftests/bpf/prog_tests/verifier.c +2 -0
@@ -57,6 +57,7 @@#include "verifier_live_stack.skel.h" #include "verifier_liveness_exp.skel.h" #include "verifier_load_acquire.skel.h" +#include "verifier_loop_hierarchy.skel.h" #include "verifier_loops1.skel.h" #include "verifier_lwt.skel.h" #include "verifier_map_in_map.skel.h"
@@ -208,6 +209,7 @@ void test_verifier_leak_ptr(void) { RUN(verifier_leak_ptr); }void test_verifier_linked_scalars (void ) {RUN (verifier_linked_scalars); }void test_verifier_live_stack (void ) {RUN (verifier_live_stack); }void test_verifier_liveness_exp (void ) {RUN (verifier_liveness_exp); } +void test_verifier_loop_hierarchy (void ) {RUN (verifier_loop_hierarchy); }void test_verifier_loops1 (void ) {RUN (verifier_loops1); }void test_verifier_lwt (void ) {RUN (verifier_lwt); }void test_verifier_map_in_map (void ) {RUN (verifier_map_in_map); }
tools/testing/selftests/bpf/progs/verifier_loop_hierarchy.c new file +233 -0
233 lines not on this page · raw message
Signature · 1 line
2.54.0
Eduard Zingerman
maintainerRFC PATCH v2 4/6 bpf: report hot simulated callchains when 1M instructions limit is met
In reply to Eduard ZingermanWhen the verifier exceeds the 1M instruction budget, the current error output shows a random execution trace that happens to be active when the limit is hit, which is not very helpful for debugging.
To rectify this, employ a profiler-inspired technique:
collect and count "callchain" stack traces that the verifier visits during program validation and report the top 3 hot traces. Sample callchains at instructions marked as force checkpoints and loop header entries.
When 1M instructions is met, print a report containing:
- callchains verifier visited most often;
- disassembly of the subprograms referenced from the printed callchains.
Here is an example of the report:
budget_nested_call_loop():
; asm volatile (" \ @ verifier_budget_report.c:44
0: (b7) r0 = 0
1: (85) call pc+1
2: (95) exit budget_nested_call_loop__inner():
; asm volatile (" \ @ verifier_budget_report.c:54
3: (b7) r0 = 0
4: (07) r0 += 1
5: (05) goto pc-2#1 most visited simulated stacktrace (visited 499999 times):
budget_nested_call_loop/1 (.../verifier_budget_report.c:44)
budget_nested_call_loop__inner/4 (.../verifier_budget_report.c:54)--- include/linux/bpf_verifier.h | 14 ++++ kernel/bpf/verifier.c | 155 +++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 169 insertions(+)
include/linux/bpf_verifier.h +14 -0
@@ -9,6 +9,8 @@#include <linux/filter.h> /* for MAX_BPF_STACK */ #include <linux/tnum.h> #include <linux/cnum.h> +#include <linux/hashtable.h> +#include <linux/jhash.h> /* Maximum variable offset umax_value permitted when resolving memory accesses. * In practice this is far bigger than any realistic pointer offset; this limit
@@ -660,6 +662,17 @@ struct bpf_loop {bool irreducible; }; +struct bpf_callchain { +u32 insn_idx[MAX_CALL_FRAMES ]; +u32 curframe; +}; + +struct bpf_callchain_entry { +struct hlist_node node; +struct bpf_callchain cc; +u64 count; +}; +struct bpf_insn_aux_data {union {enum bpf_reg_type ptr_type;/* pointer type for load/store insns */
@@ -1043,6 +1056,7 @@ struct bpf_verifier_env {u32 scc_cnt;struct bpf_iarray *succ;struct bpf_iarray *gotox_tmp_buf; +DECLARE_HASHTABLE (callchain_htab,8 ); };static inline struct bpf_func_info_aux *subprog_aux (struct bpf_verifier_env *env,int subprog)
kernel/bpf/verifier.c +155 -0
185 lines not on this page · raw message
Signature · 1 line
2.54.0
Eduard Zingerman
maintainerRFC PATCH v2 5/6 bpf: report register diff summary for hot callchains
In reply to Eduard ZingermanWhen a hot callchain ends at a iter_next, may_goto, or callback-calling instruction, compare cached states from explored_states to identify which registers or stack slots most frequently differ between states. Report the top 3 most varying locations.
The full states diff computation would require some statistical analysis similar to k-means. To keep things simple, approximate this by modifying states_equal() to return the first location where old and current states differ, and counting most frequent diff locations.
--- include/linux/bpf_verifier.h | 15 ++++ kernel/bpf/states.c | 180 +++++++++++++++++++++++++++++++++++++------ kernel/bpf/verifier.c | 57 +++++++++++--- 3 files changed, 221 insertions(+), 31 deletions(-)
include/linux/bpf_verifier.h +15 -0
@@ -662,6 +662,17 @@ struct bpf_loop {bool irreducible; }; +struct bpf_state_diff { +u8 slot; +u8 frame; +enum { +DIFF_OTHER , +DIFF_REG , +DIFF_STACK , +DIFF_ARG , + } kind; +}; +struct bpf_callchain {u32 insn_idx[MAX_CALL_FRAMES ];u32 curframe;
@@ -1631,5 +1642,9 @@ int bpf_fixup_call_args(struct bpf_verifier_env *env);int bpf_do_misc_fixups (struct bpf_verifier_env *env);int bpf_compute_loops (struct bpf_verifier_env *env); +int bpf_sample_state_diffs (struct bpf_verifier_env *env, +struct bpf_callchain *cc, +struct bpf_state_diff *top_diffs, +int *nr_diffs);#endif /* _LINUX_BPF_VERIFIER_H */
kernel/bpf/states.c +158 -22
342 lines not on this page · raw message
kernel/bpf/verifier.c +48 -9
106 lines not on this page · raw message
Signature · 1 line
2.54.0
[email protected]
AI reviewRe: [PATCH RFC bpf-next v2 5/6] bpf: report register diff summary for hot callchains
Should diagnostic allocation failures mask the complexity limit verdict?
Quoted 4 lines
kernel/bpf/verifier.c +0
-0
[ ... ]
kernel/bpf/verifier.c static int do_check(struct bpf_verifier_env *env) · line 17572
Quoted 11 lines
kernel/bpf/verifier.c +3
-1@@ -17527,7 +17564,9 @@ static int do_check(struct bpf_verifier_env *env) insn_aux = &env->insn_aux_data[env->insn_idx];if (++env->insn_processed >BPF_COMPLEXITY_LIMIT_INSNS ) { -print_hotspots (env); + err =print_hotspots (env); +if (err) +return err;verbose (env,"BPF program is too large. Processed %d insn\n" , env->insn_processed);
Should diagnostic allocation failures mask the complexity limit verdict?
When the verifier hits BPF_COMPLEXITY_LIMIT_INSNS, do_check() now calls print_hotspots() and returns its error before emitting the standard "BPF program is too large" message.
If bpf_sample_state_diffs() returns -ENOMEM from kvrealloc() during diagnostic printing, do_check() propagates that error to userspace instead of the expected -E2BIG. The program is correctly rejected, but the user-visible error shifts from "program too large" to "out of memory" purely because diagnostic output failed to allocate.
Would it be better to ignore or log-and-discard errors from print_hotspots() so that -E2BIG and the "too large" message are always produced when the complexity limit is reached?
This concern was raised in v1 by [email protected]:
https://lore.kernel.org/bpf/e98190c9cf56e356e517d69e5409b8fa34ee99342287c612418fbfe57319e1c4@mail.kernel.org/
---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
CI run summary: https://github.com/kernel-patches/bpf/actions/runs/26471389564
Eduard Zingerman
maintainerRe: [PATCH RFC bpf-next v2 5/6] bpf: report register diff summary for hot callchains
Quoted 31 lines · On Tue, 2026-05-26 at 20:17 +0000, [email protected] wrote:
Quoted 4 lines
kernel/bpf/verifier.c +0
-0[ ... ]
kernel/bpf/verifier.c static int do_check(struct bpf_verifier_env *env) · line 17572
Quoted 11 lines
kernel/bpf/verifier.c +3
-1@@ -17527,7 +17564,9 @@ static int do_check(struct bpf_verifier_env *env) insn_aux = &env->insn_aux_data[env->insn_idx]; if (++env->insn_processed > BPF_COMPLEXITY_LIMIT_INSNS) { -print_hotspots (env); + err =print_hotspots (env); +if (err) +return err; verbose(env, "BPF program is too large. Processed %d insn\n", env->insn_processed);Should diagnostic allocation failures mask the complexity limit verdict?
When the verifier hits
BPF_COMPLEXITY_LIMIT_INSNS,do_check()now callsprint_hotspots()and returns its error before emitting the standard "BPF program is too large" message.If
bpf_sample_state_diffs()returns-ENOMEMfromkvrealloc()during diagnostic printing,do_check()propagates that error to userspace instead of the expected-E2BIG. The program is correctly rejected, but the user-visible error shifts from "program too large" to "out of memory" purely because diagnostic output failed to allocate.
Quoted 3 lines
Would it be better to ignore or log-and-discard errors from
print_hotspots()so that-E2BIGand the "too large" message are always produced when the complexity limit is reached?
I don't think this is a real life concern. If system can't allocate 10-20Kb of memory, there are bigger problems on the host.
Quoted 9 lines
This concern was raised in v1 by [email protected]:
https://lore.kernel.org/bpf/e98190c9cf56e356e517d69e5409b8fa34ee99342287c612418fbfe57319e1c4@mail.kernel.org/---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.mdCI run summary: https://github.com/kernel-patches/bpf/actions/runs/26471389564
[email protected]
AI reviewRe: [PATCH RFC bpf-next v2 5/6] bpf: report register diff summary for hot callchains
In reply to Eduard ZingermanThank you for your contribution! Sashiko AI review found 4 potential issue(s) to consider: - [High] O(N^2) state comparisons without cond_resched() can cause CPU lockups - [Medium]…
Thank you for your contribution! Sashiko AI review found 4 potential issue(s) to consider:
- [High] O(N^2) state comparisons without cond_resched() can cause CPU lockups
- [Medium] callchain_matches_state() does not check the leaf instruction index
- [Medium] print_hotspots() failure masks the primary -E2BIG complexity limit error
- [Low] Integer overflow in state_diff_cmp sorting function
--
commit 33b39095313d5bead6d88744178c2d3f55d7b64b
Author: Eduard Zingerman <[email protected]>
bpf: report register diff summary for hot callchains
This commit introduces a feature to report the most frequently varying locations (registers or stack slots) when a hot callchain ends. It modifies states_equal() to identify the first differing location between states and counts occurrences across explored states to approximate a diff summary.
Quoted 4 lines
kernel/bpf/states.c +0
-0
[ ... ]
Quoted 7 lines
kernel/bpf/states.c +3
-0@@ -1588,3 +1629,98 @@ int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx)list_add (&new_sl->node, head);return 0 ; } + +static bool callchain_matches_state (struct bpf_callchain *cc, +struct bpf_verifier_state *st)
kernel/bpf/states.c int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx) · line 1644
Quoted 10 lines
kernel/bpf/states.c +10
-0+{ +int i; + +if (st->curframe != cc->curframe) +return false; +for (i =0 ; i < (int )cc->curframe; i++) +if (st->frame[i +1 ]->callsite != cc->insn_idx[i]) +return false; +return true; +}
[Severity: Medium]
Does this function need to verify the leaf instruction index (st->insn_idx == cc->insn_idx[cc->curframe])?
States for different instructions can hash to the same bucket via (insn_idx ^ callsite) % env->prog->len. Without checking the leaf instruction, a hash collision could cause states from different instructions to be incorrectly matched, violating assumptions in func_states_equal() which relies on live_regs_before for a specific instruction.
kernel/bpf/states.c int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx) · line 1654
Quoted 10 lines
kernel/bpf/states.c +10
-0+ +struct state_diff_cnt { +struct bpf_state_diff diff; +u32 cnt; +}; + +static int state_diff_cmp (const void *a,const void *b) +{ +return ((struct state_diff_cnt *)b)->cnt - ((struct state_diff_cnt *)a)->cnt; +}
[Severity: Low]
Can this subtraction overflow?
The cnt fields are unsigned 32-bit integers, and the function returns a signed 32-bit integer. If the difference exceeds INT_MAX, the subtraction will overflow into a negative value, resulting in an inverted sort order.
Quoted 25 lines
kernel/bpf/states.c +25
-0+ +static bool state_diff_eq (struct bpf_state_diff *a,struct bpf_state_diff *b) +{ +return a->frame == b->frame && a->slot == b->slot && a->kind == b->kind; +} + +int bpf_sample_state_diffs (struct bpf_verifier_env *env, +struct bpf_callchain *cc, +struct bpf_state_diff *top_diffs, +int *nr_diffs) +{ +struct bpf_verifier_state_list *sl_i, *sl_j; +struct state_diff_cnt *diff_cnts =NULL ; +struct list_head *pos_i, *pos_j, *head; +u32 leaf_insn, callsite, hash_idx; +int i, cap =0 , nr_locs =0 ; + + leaf_insn = cc->insn_idx[cc->curframe]; + callsite = cc->curframe >0 ? cc->insn_idx[cc->curframe -1 ] :BPF_MAIN_FUNC ; + hash_idx = (leaf_insn ^ callsite) % env->prog->len; + head = &env->explored_states[hash_idx]; + +list_for_each (pos_i, head) { + sl_i = container_of(pos_i, struct bpf_verifier_state_list, node); +if (!callchain_matches_state (cc, &sl_i->state))
kernel/bpf/states.c int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx) · line 1689
Quoted 10 lines
kernel/bpf/states.c +10
-0+continue ; +list_for_each (pos_j, head) { +struct bpf_state_diff diff = {}; + +if (pos_i == pos_j) +continue ; + sl_j = container_of(pos_j, struct bpf_verifier_state_list, node); +if (!callchain_matches_state (cc, &sl_j->state)) +continue ; +if (states_equal (env, &sl_i->state, &sl_j->state,NOT_EXACT , &diff))
[Severity: High]
Can these nested list_for_each loops cause a CPU soft lockup?
A single hash bucket can accumulate tens to hundreds of thousands of cached states for a single instruction in complex programs. Without cond_resched() calls within these O(N^2) loops, billions of states_equal() comparisons could execute, monopolizing the CPU and leading to a local DoS.
[ ... ]
Quoted 4 lines
kernel/bpf/verifier.c +0
-0
[ ... ]
kernel/bpf/verifier.c static int do_check(struct bpf_verifier_env *env) · line 17569
Quoted 8 lines
kernel/bpf/verifier.c +3
-1@@ -17527,7 +17564,9 @@ static int do_check(struct bpf_verifier_env *env) insn_aux = &env->insn_aux_data[env->insn_idx];if (++env->insn_processed >BPF_COMPLEXITY_LIMIT_INSNS ) { -print_hotspots (env); + err =print_hotspots (env); +if (err) +return err;
[Severity: Medium]
If print_hotspots() returns an error (like -ENOMEM from kvrealloc()), does this mask the primary -E2BIG complexity limit error?
Returning err directly will skip logging "BPF program is too large" and return a misleading error code to the user, who might attribute it to system memory exhaustion instead of hitting the verifier complexity limit.
Quoted 3 lines
kernel/bpf/verifier.c +0
-0verbose (env,"BPF program is too large. Processed %d insn\n" , env->insn_processed);
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=5
Eduard Zingerman
maintainerRe: [PATCH RFC bpf-next v2 5/6] bpf: report register diff summary for hot callchains
On Tue, 2026-05-26 at 21:31 +0000, [email protected] wrote:
[...]
Quoted 27 lines
Quoted 4 lines
kernel/bpf/states.c +0
-0[ ... ]
Quoted 7 lines
kernel/bpf/states.c +3
-0@@ -1588,3 +1629,98 @@ int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx) list_add(&new_sl->node, head); return 0; } + +static bool callchain_matches_state (struct bpf_callchain *cc, + struct bpf_verifier_state *st)kernel/bpf/states.c int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx) · line 1644
Quoted 10 lines
kernel/bpf/states.c +10
-0+{ +int i; + +if (st->curframe != cc->curframe) +return false; +for (i =0 ; i < (int )cc->curframe; i++) +if (st->frame[i +1 ]->callsite != cc->insn_idx[i]) +return false; +return true; +}[Severity: Medium]
Does this function need to verify the leaf instruction index (st->insn_idx== cc->insn_idx[cc->curframe])?
Quoted 5 lines
States for different instructions can hash to the same bucket via (
insn_idx^ callsite) %env->prog->len. Without checking the leaf instruction, a hash collision could cause states from different instructions to be incorrectly matched, violating assumptions infunc_states_equal()which relies onlive_regs_beforefor a specific instruction.
This should be fixed.
Quoted 14 lines
kernel/bpf/states.c int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx) · line 1654
Quoted 10 lines
kernel/bpf/states.c +10
-0+ +struct state_diff_cnt { +struct bpf_state_diff diff; +u32 cnt; +}; + +static int state_diff_cmp (const void *a,const void *b) +{ +return ((struct state_diff_cnt *)b)->cnt - ((struct state_diff_cnt *)a)->cnt; +}[Severity: Low]
Can this subtraction overflow?
Quoted 3 lines
The cnt fields are unsigned 32-bit integers, and the function returns a signed 32-bit integer. If the difference exceeds
INT_MAX, the subtraction will overflow into a negative value, resulting in an inverted sort order.
I don't think overflow can happen here.
But I'll rewrite to make the robot happy.
Quoted 39 lines
Quoted 25 lines
kernel/bpf/states.c +25
-0+ +static bool state_diff_eq (struct bpf_state_diff *a,struct bpf_state_diff *b) +{ +return a->frame == b->frame && a->slot == b->slot && a->kind == b->kind; +} + +int bpf_sample_state_diffs (struct bpf_verifier_env *env, + struct bpf_callchain *cc, + struct bpf_state_diff *top_diffs, + int *nr_diffs) +{ +struct bpf_verifier_state_list *sl_i, *sl_j; +struct state_diff_cnt *diff_cnts =NULL ; +struct list_head *pos_i, *pos_j, *head; +u32 leaf_insn, callsite, hash_idx; +int i, cap =0 , nr_locs =0 ; + + leaf_insn = cc->insn_idx[cc->curframe]; + callsite = cc->curframe >0 ? cc->insn_idx[cc->curframe -1 ] :BPF_MAIN_FUNC ; + hash_idx = (leaf_insn ^ callsite) % env->prog->len; + head = &env->explored_states[hash_idx]; + +list_for_each (pos_i, head) { + sl_i = container_of(pos_i, struct bpf_verifier_state_list, node); +if (!callchain_matches_state (cc, &sl_i->state))kernel/bpf/states.c int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx) · line 1689
Quoted 10 lines
kernel/bpf/states.c +10
-0+continue ; +list_for_each (pos_j, head) { +struct bpf_state_diff diff = {}; + +if (pos_i == pos_j) +continue ; + sl_j = container_of(pos_j, struct bpf_verifier_state_list, node); +if (!callchain_matches_state (cc, &sl_j->state)) +continue ; +if (states_equal (env, &sl_i->state, &sl_j->state,NOT_EXACT , &diff))[Severity: High]
Can these nestedlist_for_eachloops cause a CPU soft lockup?
Quoted 4 lines
A single hash bucket can accumulate tens to hundreds of thousands of cached states for a single instruction in complex programs. Without
cond_resched()calls within these O(N^2) loops, billions ofstates_equal()comparisons could execute, monopolizing the CPU and leading to a local DoS.
I'll add cond_resched().
Quoted 19 lines
[ ... ]
Quoted 4 lines
kernel/bpf/verifier.c +0
-0[ ... ]
kernel/bpf/verifier.c static int do_check(struct bpf_verifier_env *env) · line 17569
Quoted 8 lines
kernel/bpf/verifier.c +0
-0@@ -17527,7 +17564,9 @@ static int do_check(struct bpf_verifier_env *env) insn_aux = &env->insn_aux_data[env->insn_idx];
if (++env->insn_processed >BPF_COMPLEXITY_LIMIT_INSNS) {kernel/bpf/verifier.c +3
-1-print_hotspots (env); + err =print_hotspots (env); +if (err) +return err;[Severity: Medium]
Ifprint_hotspots()returns an error (like-ENOMEMfromkvrealloc()), does this mask the primary-E2BIGcomplexity limit error?
Quoted 7 lines
Returning err directly will skip logging "BPF program is too large" and return a misleading error code to the user, who might attribute it to system memory exhaustion instead of hitting the verifier complexity limit.
Quoted 3 lines
verbose(env,
"BPF program is too large. Processed %d insn\n",env->insn_processed);
Replied already.
Eduard Zingerman
maintainerRFC PATCH v2 6/6 selftests/bpf: test budget exhaustion profiling report
In reply to Eduard ZingermanAdd verifier selftests that exhaust the 1M instruction budget and verify that the new profiling report is produced:
- nested function calls with inner loop, check that stack trace is print correctly;
- two loops on the same level, check that both are reported;
- iterator-based loop with non-converging register, check that register is in the report;
- iterator-based loop with non-converging stack slot, check that stack slot is in the report.
--- tools/testing/selftests/bpf/prog_tests/verifier.c | 2 + .../selftests/bpf/progs/verifier_budget_report.c | 175 +++++++++++++++++++++ 2 files changed, 177 insertions(+)
tools/testing/selftests/bpf/prog_tests/verifier.c +2 -0
@@ -14,6 +14,7 @@#include "verifier_basic_stack.skel.h" #include "verifier_bitfield_write.skel.h" #include "verifier_bounds.skel.h" +#include "verifier_budget_report.skel.h" #include "verifier_bounds_deduction.skel.h" #include "verifier_bounds_deduction_non_const.skel.h" #include "verifier_bounds_mix_sign_unsign.skel.h"
@@ -169,6 +170,7 @@ void test_verifier_bounds(void) { RUN(verifier_bounds); }void test_verifier_bounds_deduction (void ) {RUN (verifier_bounds_deduction); }void test_verifier_bounds_deduction_non_const (void ) {RUN (verifier_bounds_deduction_non_const); }void test_verifier_bounds_mix_sign_unsign (void ) {RUN (verifier_bounds_mix_sign_unsign); } +void test_verifier_budget_report (void ) {RUN (verifier_budget_report); }void test_verifier_bpf_get_stack (void ) {RUN (verifier_bpf_get_stack); }void test_verifier_bpf_trap (void ) {RUN (verifier_bpf_trap); }void test_verifier_bswap (void ) {RUN (verifier_bswap); }
tools/testing/selftests/bpf/progs/verifier_budget_report.c new file +175 -0
175 lines not on this page · raw message
Signature · 1 line
2.54.0