Skip to contentSkip to conversation

bpf: better error reporting when verifier hits 1M instructions limit

RFC PATCH Superseded Eduard Zingerman 3 participants 13 messages May 26

Subsystems (4)

v2 of 3 Superseded Latest is v3 →

lore
Share & tools
lore

Eduard Zingerman

author maintainer
#0 lore raw

v2 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

author maintainer
#1 lore raw

RFC 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
index 0aadfbae0acc..16d030fdd83a 100644
@@ -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
index c8d980fdd709..3d569e36128c 100644
@@ -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
index 401152b2b64f..923572df4bbf 100644
@@ -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
author maintainer
#2 lore raw

RFC PATCH v2 2/6 bpf: compute loops hierarchy

In reply to Eduard Zingerman

Add 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
index 5cbad3b64130..d0a1fb135cbf 100644
@@ -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
index 4dc41bf5780c..787d183ba5b4 100644
@@ -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
index 12739add2dda..57294524dab8 100644
@@ -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
index 3d569e36128c..2b3584712ad2 100644
@@ -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
#3 lore raw

Re: [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
new file mode 100644
index 0000000000000..1f0b10c57957a

[ ... ]

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
author maintainer
#4 lore raw

Re: [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 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
new file mode 100644
index 0000000000000..1f0b10c57957a

[ ... ]

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 call cond_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;
+}
author maintainer
#5 lore raw

RFC PATCH v2 3/6 selftests/bpf: test cases for loop hierarchy computation

In reply to Eduard Zingerman

Test 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
index 219ff2969868..35d92d176c1f 100644
@@ -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
author maintainer
#6 lore raw

RFC PATCH v2 4/6 bpf: report hot simulated callchains when 1M instructions limit is met

In reply to Eduard Zingerman

When 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
index d0a1fb135cbf..347a155d8e21 100644
@@ -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
author maintainer
#7 lore raw

RFC PATCH v2 5/6 bpf: report register diff summary for hot callchains

In reply to Eduard Zingerman

When 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
index 347a155d8e21..cc83359774f5 100644
@@ -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
#8 lore raw

Re: [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
index 54b7ad65b7fc..d09c014462f1 100644

[ ... ]

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

author maintainer
#9 lore raw

Re: [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
index 54b7ad65b7fc..d09c014462f1 100644

[ ... ]

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.

Quoted 3 lines

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?

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.md

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

#10 lore raw

Re: [PATCH RFC bpf-next v2 5/6] bpf: report register diff summary for hot callchains

In reply to Eduard Zingerman
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]…

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
index 8773381360095..79e76bc2d1712 100644

[ ... ]

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
index 54b7ad65b7fc1..d09c014462f13 100644

[ ... ]

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 -0
 			verbose(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
author maintainer
#11 lore raw

Re: [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
index 8773381360095..79e76bc2d1712 100644

[ ... ]

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 in func_states_equal() which relies on live_regs_before for 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 nested list_for_each loops 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 of states_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
index 54b7ad65b7fc1..d09c014462f13 100644

[ ... ]

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]
If print_hotspots() returns an error (like -ENOMEM from kvrealloc()), does this mask the primary -E2BIG complexity 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.

author maintainer
#12 lore raw

RFC PATCH v2 6/6 selftests/bpf: test budget exhaustion profiling report

In reply to Eduard Zingerman

Add 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
index 35d92d176c1f..61a732a499b0 100644
@@ -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