Skip to contentSkip to conversation

bpf: Relax 8 frame limitation for global subprogs

PATCH Applied Emil Tsalapatis 3 participants 6 messages Mar 16

Subsystems (4)
lore
Share & tools
lore

Emil Tsalapatis

author reviewer
#0 lore raw

v6 cover bpf: Relax 8 frame limitation for global subprogs

The BPF verifier currently limits the maximum runtime call stack to 8 frames. Larger BPF programs like sched-ext schedulers routinely fail verification because they exceed this limit, even as they use very little actual stack space for each frame.

Relax the verifier to permit call stacks > 8 frames deep when the call stacks include global subprogs. The old 8 stack frame limit now only applies to call stacks composed entirely of static function calls. This works because global functions are each verified in isolation, so the verifier does not need to cross-reference verification state across the function call boundary, which has been the reason for limiting the call stack size in the first place.

This patch does not change the verification time limit of 8 stack frames. Static functions that are inlined for verification purposes still only go 8 frames deep to avoid changing the verifier's internal data structures used for verification. These data structures only support holding information on up to 8 stack frames.

This patch also does not adjust the actual maximum stack size of 512.

CHANGELOG
=========

v5 -> v6 (https://lore.kernel.org/bpf/[email protected]/)
- Make bpf_subprog_call_depth_info internal to verifier.c (Alexei)

v4 -> v5 (https://lore.kernel.org/bpf/[email protected]/)
- Move depth tracking state to verifier (Eduard) and free it after verification (Alexei)
- Fix selftest patch title and formatting errors (Yonghong)

v3 -> v4 (https://lore.kernel.org/bpf/[email protected]/)
- Factor out temp call depth tracking info into its own struct (Eduard)
- Bring depth calculation loop in line with the other instances (Mykyta)
- Add comment on why selftest call stack is 16 bytes/frame (Eduard)
- Rename "cidx" to "caller" for clarity (Mykyta, Eduard)

v2 -> v3 (https://lore.kernel.org/bpf/[email protected]/)
- Change logic to remove arbitrary limit on call depth (Eduard)
- Add additional selftests (Eduard)

v1 -> v2 (https://lore.kernel.org/bpf/[email protected])
- Adjust patch to only increase the runtime stack depth, leaving the verification-time stack depth unchanged (Alexei)

Emil Tsalapatis (2):
bpf: Only enforce 8 frame call stack limit for all-static stacks selftests/bpf: Add deep call stack selftests

 kernel/bpf/verifier.c                         | 76 ++++++++++-----
 .../bpf/prog_tests/test_global_funcs.c        |  2 +
 .../selftests/bpf/progs/test_global_func3.c   | 18 ++--
 .../bpf/progs/test_global_func_deep_stack.c   | 95 +++++++++++++++++++
 4 files changed, 160 insertions(+), 31 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/test_global_func_deep_stack.c
Signature · 1 line
2.49.0
author reviewer
#1 lore raw

PATCH v6 1/2 bpf: Only enforce 8 frame call stack limit for all-static stacks

The BPF verifier currently enforces a call stack depth of 8 frames, regardless of the actual stack space consumption of those frames. The limit is necessary for static call stacks, because the bookkeeping data structures used by the verifier when stepping into static functions during verification only support 8 stack frames. However, this limitation only matters for static stack frames: Global subprogs are verified by themselves and do not require limiting the call depth.

Relax this limitation to only apply to static stack frames. Verification now only fails when there is a sequence of 8 calls to non-global subprogs. Calling into a global subprog resets the counter. This allows deeper call stacks, provided all frames still fit in the stack.

The change does not increase the maximum size of the call stack, only the maximum number of frames we can place in it.

Also change the progs/test_global_func3.c selftest to use static functions, since with the new patch it would otherwise unexpectedly pass verification.

---
 kernel/bpf/verifier.c                         | 76 +++++++++++++------
 .../selftests/bpf/progs/test_global_func3.c   | 18 ++---
 2 files changed, 63 insertions(+), 31 deletions(-)
kernel/bpf/verifier.c +54 -22
index 4fbacd2149cd..625b0189cc61 100644
@@ -6720,22 +6720,30 @@ static int round_up_stack_depth(struct bpf_verifier_env *env, int stack_depth)
 	return round_up(max_t(u32, stack_depth, 1), 32);
 }
 
+/* temporary state used for call frame depth calculation */
+struct bpf_subprog_call_depth_info {
+	int ret_insn; /* caller instruction where we return to. */
+	int caller; /* caller subprogram idx */
+	int frame; /* # of consecutive static call stack frames on top of stack */
+};
+
 /* starting from main bpf function walk all instructions of the function
  * and recursively walk all callees that given function can call.
  * Ignore jump and exit insns.
- * Since recursion is prevented by check_cfg() this algorithm
- * only needs a local stack of MAX_CALL_FRAMES to remember callsites
  */
 static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
+					 struct bpf_subprog_call_depth_info *dinfo,
 					 bool priv_stack_supported)
 {
 	struct bpf_subprog_info *subprog = env->subprog_info;
 	struct bpf_insn *insn = env->prog->insnsi;
 	int depth = 0, frame = 0, i, subprog_end, subprog_depth;
 	bool tail_call_reachable = false;
-	int ret_insn[MAX_CALL_FRAMES];
-	int ret_prog[MAX_CALL_FRAMES];
-	int j;
+	int total;
+	int tmp;
+
+	/* no caller idx */
+	dinfo[idx].caller = -1;
 
 	i = subprog[idx].start;
 	if (!priv_stack_supported)
@@ -6787,8 +6795,12 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
 	} else {
 		depth += subprog_depth;
 		if (depth > MAX_BPF_STACK) {
+			total = 0;
+			for (tmp = idx; tmp >= 0; tmp = dinfo[tmp].caller)
+				total++;
+
 			verbose(env, "combined stack size of %d calls is %d. Too large\n",
-				frame + 1, depth);
+				total, depth);
 			return -EACCES;
 		}
 	}
@@ -6802,10 +6814,8 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
 
 			if (!is_bpf_throw_kfunc(insn + i))
 				continue;
-			if (subprog[idx].is_cb)
-				err = true;
-			for (int c = 0; c < frame && !err; c++) {
-				if (subprog[ret_prog[c]].is_cb) {
+			for (tmp = idx; tmp >= 0 && !err; tmp = dinfo[tmp].caller) {
+				if (subprog[tmp].is_cb) {
 					err = true;
 					break;
 				}
@@ -6821,8 +6831,6 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
 		if (!bpf_pseudo_call(insn + i) && !bpf_pseudo_func(insn + i))
 			continue;
 		/* remember insn and function to return to */
-		ret_insn[frame] = i + 1;
-		ret_prog[frame] = idx;
 
 		/* find the callee */
 		next_insn = i + insn[i].imm + 1;
@@ -6842,7 +6850,16 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
 				return -EINVAL;
 			}
 		}
+
+		/* store caller info for after we return from callee */
+		dinfo[idx].frame = frame;
+		dinfo[idx].ret_insn = i + 1;
+
+		/* push caller idx into callee's dinfo */
+		dinfo[sidx].caller = idx;
+
 		i = next_insn;
+
 		idx = sidx;
 		if (!priv_stack_supported)
 			subprog[idx].priv_stack_mode = NO_PRIV_STACK;
@@ -6850,7 +6867,7 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
 		if (subprog[idx].has_tail_call)
 			tail_call_reachable = true;
 
-		frame++;
+		frame = subprog_is_global(env, idx) ? 0 : frame + 1;
 		if (frame >= MAX_CALL_FRAMES) {
 			verbose(env, "the call stack of %d frames is too deep !\n",
 				frame);
@@ -6864,12 +6881,12 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
 	 * tail call counter throughout bpf2bpf calls combined with tailcalls
 	 */
 	if (tail_call_reachable)
-		for (j = 0; j < frame; j++) {
-			if (subprog[ret_prog[j]].is_exception_cb) {
+		for (tmp = idx; tmp >= 0; tmp = dinfo[tmp].caller) {
+			if (subprog[tmp].is_exception_cb) {
 				verbose(env, "cannot tail call within exception cb\n");
 				return -EINVAL;
 			}
-			subprog[ret_prog[j]].tail_call_reachable = true;
+			subprog[tmp].tail_call_reachable = true;
 		}
 	if (subprog[0].tail_call_reachable)
 		env->prog->aux->tail_call_reachable = true;
@@ -6877,23 +6894,33 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
 	/* end of for() loop means the last insn of the 'subprog'
 	 * was reached. Doesn't matter whether it was JA or EXIT
 	 */
-	if (frame == 0)
+	if (frame == 0 && dinfo[idx].caller < 0)
 		return 0;
 	if (subprog[idx].priv_stack_mode != PRIV_STACK_ADAPTIVE)
 		depth -= round_up_stack_depth(env, subprog[idx].stack_depth);
-	frame--;
-	i = ret_insn[frame];
-	idx = ret_prog[frame];
+
+	/* pop caller idx from callee */
+	idx = dinfo[idx].caller;
+
+	/* retrieve caller state from its frame */
+	frame = dinfo[idx].frame;
+	i = dinfo[idx].ret_insn;
+
 	goto continue_func;
 }
 
 static int check_max_stack_depth(struct bpf_verifier_env *env)
 {
 	enum priv_stack_mode priv_stack_mode = PRIV_STACK_UNKNOWN;
+	struct bpf_subprog_call_depth_info *dinfo;
 	struct bpf_subprog_info *si = env->subprog_info;
 	bool priv_stack_supported;
 	int ret;
 
+	dinfo = kvcalloc(env->subprog_cnt, sizeof(*dinfo), GFP_KERNEL_ACCOUNT);
+	if (!dinfo)
+		return -ENOMEM;
+
 	for (int i = 0; i < env->subprog_cnt; i++) {
 		if (si[i].has_tail_call) {
 			priv_stack_mode = NO_PRIV_STACK;
@@ -6915,9 +6942,12 @@ static int check_max_stack_depth(struct bpf_verifier_env *env)
 	for (int i = env->subprog_cnt - 1; i >= 0; i--) {
 		if (!i || si[i].is_async_cb) {
 			priv_stack_supported = !i && priv_stack_mode == PRIV_STACK_ADAPTIVE;
-			ret = check_max_stack_depth_subprog(env, i, priv_stack_supported);
-			if (ret < 0)
+			ret = check_max_stack_depth_subprog(env, i, dinfo,
+					priv_stack_supported);
+			if (ret < 0) {
+				kvfree(dinfo);
 				return ret;
+			}
 		}
 	}
 
@@ -6928,6 +6958,8 @@ static int check_max_stack_depth(struct bpf_verifier_env *env)
 		}
 	}
 
+	kvfree(dinfo);
+
 	return 0;
 }
 
tools/testing/selftests/bpf/progs/test_global_func3.c +9 -9
index 142b682d3c2f..974fd8c19561 100644
@@ -5,56 +5,56 @@
 #include <bpf/bpf_helpers.h>
 #include "bpf_misc.h"
 
-__attribute__ ((noinline))
+static __attribute__ ((noinline))
 int f1(struct __sk_buff *skb)
 {
 	return skb->len;
 }
 
-__attribute__ ((noinline))
+static __attribute__ ((noinline))
 int f2(int val, struct __sk_buff *skb)
 {
 	return f1(skb) + val;
 }
 
-__attribute__ ((noinline))
+static __attribute__ ((noinline))
 int f3(int val, struct __sk_buff *skb, int var)
 {
 	return f2(var, skb) + val;
 }
 
-__attribute__ ((noinline))
+static __attribute__ ((noinline))
 int f4(struct __sk_buff *skb)
 {
 	return f3(1, skb, 2);
 }
 
-__attribute__ ((noinline))
+static __attribute__ ((noinline))
 int f5(struct __sk_buff *skb)
 {
 	return f4(skb);
 }
 
-__attribute__ ((noinline))
+static __attribute__ ((noinline))
 int f6(struct __sk_buff *skb)
 {
 	return f5(skb);
 }
 
-__attribute__ ((noinline))
+static __attribute__ ((noinline))
 int f7(struct __sk_buff *skb)
 {
 	return f6(skb);
 }
 
-__attribute__ ((noinline))
+static __attribute__ ((noinline))
 int f8(struct __sk_buff *skb)
 {
 	return f7(skb);
 }
 
 SEC("tc")
-__failure __msg("the call stack of 8 frames")
+__failure __msg("the call stack of 9 frames")
 int global_func3(struct __sk_buff *skb)
 {
 	return f8(skb);
Signature · 1 line
2.49.0
#2 lore raw

Re: [PATCH bpf-next v6 1/2] bpf: Only enforce 8 frame call stack limit for all-static stacks

Should the expected message here be "the call stack of 8 frames" rather than 9?
Quoted 4 lines
kernel/bpf/verifier.c +0 -0
index e29f15419fcb..01c18f4268de 100644

[ ... ]

Quoted 1 line
kernel/bpf/verifier.c +0 -0
@@ -6854,7 +6854,16 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,

[ ... ]

Quoted 5 lines
kernel/bpf/verifier.c +1 -1
-		frame++;
+		frame = subprog_is_global(env, idx) ? 0 : frame + 1;
 		if (frame >= MAX_CALL_FRAMES) {
 			verbose(env, "the call stack of %d frames is too deep !\n",
 				frame);

[ ... ]

Quoted 4 lines
tools/testing/selftests/bpf/progs/test_global_func3.c +0 -0
index 142b682d3c2f..974fd8c19561 100644

[ ... ]

tools/testing/selftests/bpf/progs/test_global_func3.c line 60

Quoted 6 lines

SEC("tc")

tools/testing/selftests/bpf/progs/test_global_func3.c +1 -1
-__failure __msg("the call stack of 8 frames")
+__failure __msg("the call stack of 9 frames")
 int global_func3(struct __sk_buff *skb)
 {
 	return f8(skb);

Should the expected message here be "the call stack of 8 frames" rather than 9?

The test has 9 functions total (global_func3 plus f1 through f8), but only 8 call transitions, and frame starts at 0. Each static call increments frame by one:

    frame = subprog_is_global(env, idx) ? 0 : frame + 1;
    if (frame >= MAX_CALL_FRAMES) {
        verbose(env, "the call stack of %d frames is too deep !\n",
            frame);

With 8 static calls (global_func3 -> f8 -> f7 -> ... -> f1), frame reaches 8 which triggers the check since MAX_CALL_FRAMES is 8. The verifier would print "the call stack of 8 frames is too deep" and the __msg substring match for "9 frames" would not match, causing the test to fail.

The old test with global functions also had 8 call transitions and expected "8 frames", since frame++ produced the same value of 8 at the limit.

---
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/23154616737

author reviewer
#3 lore raw

Re: [PATCH bpf-next v6 1/2] bpf: Only enforce 8 frame call stack limit for all-static stacks

Quoted 51 lines · bot+bpf-ci
Quoted 4 lines
kernel/bpf/verifier.c +0 -0
index e29f15419fcb..01c18f4268de 100644

[ ... ]

Quoted 1 line
kernel/bpf/verifier.c +0 -0
@@ -6854,7 +6854,16 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,

[ ... ]

Quoted 5 lines
kernel/bpf/verifier.c +1 -1
-		frame++;
+		frame = subprog_is_global(env, idx) ? 0 : frame + 1;
 		if (frame >= MAX_CALL_FRAMES) {
 			verbose(env, "the call stack of %d frames is too deep !\n",
 				frame);

[ ... ]

Quoted 4 lines
tools/testing/selftests/bpf/progs/test_global_func3.c +0 -0
index 142b682d3c2f..974fd8c19561 100644

[ ... ]

tools/testing/selftests/bpf/progs/test_global_func3.c line 60

Quoted 6 lines

SEC("tc")

tools/testing/selftests/bpf/progs/test_global_func3.c +1 -1
-__failure __msg("the call stack of 8 frames")
+__failure __msg("the call stack of 9 frames")
 int global_func3(struct __sk_buff *skb)
 {
 	return f8(skb);

Should the expected message here be "the call stack of 8 frames" rather than 9?

The test has 9 functions total (global_func3 plus f1 through f8), but only 8 call transitions, and frame starts at 0. Each static call increments frame by one:

    frame = subprog_is_global(env, idx) ? 0 : frame + 1;
    if (frame >= MAX_CALL_FRAMES) {
        verbose(env, "the call stack of %d frames is too deep !\n",
            frame);

With 8 static calls (global_func3 -> f8 -> f7 -> ... -> f1), frame reaches 8 which triggers the check since MAX_CALL_FRAMES is 8. The verifier would print "the call stack of 8 frames is too deep" and the __msg substring match for "9 frames" would not match, causing the test to fail.

Quoted 4 lines

The old test with global functions also had 8 call transitions and expected "8 frames", since frame++ produced the same value of 8 at the limit.

Same answer as in the previous version, the test passes fine.

Quoted 5 lines

---
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/23154616737

author reviewer
#4 lore raw

PATCH v6 2/2 selftests/bpf: Add deep call stack selftests

In reply to Emil Tsalapatis

Add tests that demonstrate the verifier support for deep call stacks while still enforcing maximum stack size limits.

---
 .../bpf/prog_tests/test_global_funcs.c        |  2 +
 .../bpf/progs/test_global_func_deep_stack.c   | 95 +++++++++++++++++++
 2 files changed, 97 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/test_global_func_deep_stack.c
tools/testing/selftests/bpf/prog_tests/test_global_funcs.c +2 -0
index e905cbaf6b3d..500446808908 100644
@@ -18,6 +18,7 @@
 #include "test_global_func15.skel.h"
 #include "test_global_func16.skel.h"
 #include "test_global_func17.skel.h"
+#include "test_global_func_deep_stack.skel.h"
 #include "test_global_func_ctx_args.skel.h"
 
 #include "bpf/libbpf_internal.h"
@@ -155,6 +156,7 @@ void test_test_global_funcs(void)
 	RUN_TESTS(test_global_func15);
 	RUN_TESTS(test_global_func16);
 	RUN_TESTS(test_global_func17);
+	RUN_TESTS(test_global_func_deep_stack);
 	RUN_TESTS(test_global_func_ctx_args);
 
 	if (test__start_subtest("ctx_arg_rewrite"))
tools/testing/selftests/bpf/progs/test_global_func_deep_stack.c new file +95 -0

95 lines not on this page · raw message

Signature · 1 line
2.49.0
#5 lore raw
In reply to Emil Tsalapatis
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 13 lines · On Mon, 16 Mar 2026 12:12:23 -0400 you wrote:

The BPF verifier currently limits the maximum runtime call stack to 8 frames. Larger BPF programs like sched-ext schedulers routinely fail verification because they exceed this limit, even as they use very little actual stack space for each frame.

Relax the verifier to permit call stacks > 8 frames deep when the call stacks include global subprogs. The old 8 stack frame limit now only applies to call stacks composed entirely of static function calls. This works because global functions are each verified in isolation, so the verifier does not need to cross-reference verification state across the function call boundary, which has been the reason for limiting the call stack size in the first place.

Quoted 1 line

[...]

Here is the summary with links:
- [bpf-next,v6,1/2] bpf: Only enforce 8 frame call stack limit for all-static stacks

    https://git.kernel.org/bpf/bpf-next/c/ad95d3c758d8
  - [bpf-next,v6,2/2] selftests/bpf: Add deep call stack selftests
    https://git.kernel.org/bpf/bpf-next/c/01d5d2f7d93d

You are awesome, thank you!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html