bpf: Relax 8 frame limitation for global subprogs
Subsystems (4)
Emil Tsalapatis
reviewerv5 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
=========
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
include/linux/bpf_verifier.h | 9 ++ kernel/bpf/verifier.c | 62 ++++++++---- .../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 +++++++++++++++++++ 5 files changed, 158 insertions(+), 28 deletions(-) create mode 100644 tools/testing/selftests/bpf/progs/test_global_func_deep_stack.c
Signature · 1 line
2.49.0
Emil Tsalapatis
reviewerPATCH v5 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.
--- include/linux/bpf_verifier.h | 9 +++ kernel/bpf/verifier.c | 62 +++++++++++++------ .../selftests/bpf/progs/test_global_func3.c | 18 +++--- 3 files changed, 61 insertions(+), 28 deletions(-)
include/linux/bpf_verifier.h +9 -0
@@ -742,6 +742,12 @@ struct bpf_scc_info {struct bpf_liveness ; +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 */ +}; +/* single container for all structs * one verifier_env per bpf_check() call */
@@ -851,6 +857,9 @@ struct bpf_verifier_env {u32 scc_cnt;struct bpf_iarray *succ;struct bpf_iarray *gotox_tmp_buf; + +/* temporary state used for call frame depth calculation */ +struct bpf_subprog_call_depth_info *dinfo; };static inline struct bpf_func_info_aux *subprog_aux (struct bpf_verifier_env *env,int subprog)
kernel/bpf/verifier.c +43 -19
137 lines not on this page · raw message
tools/testing/selftests/bpf/progs/test_global_func3.c +9 -9
@@ -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
[email protected]
AI reviewRe: [PATCH bpf-next v5 1/2] bpf: Only enforce 8 frame call stack limit for all-static stacks
The function header comment above this hunk still reads:
Quoted 6 lines
kernel/bpf/verifier.c +0
-0@@ -6733,9 +6733,11 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,struct bpf_insn *insn = env->prog->insnsi;
kernel/bpf/verifier.c static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx, · line 6740
Quoted 10 lines
kernel/bpf/verifier.c +5
-3int 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 */ + env->dinfo[idx].caller =-1 ;
The function header comment above this hunk still reads:
Since recursion is prevented by check_cfg() this algorithm only needs a local stack of MAX_CALL_FRAMES to remember callsites
The local stack arrays (ret_insn[] and ret_prog[]) have been removed in favor of per-subprog dinfo fields. Should this comment be updated to reflect the new approach?
This was also noted during the v3 and v4 reviews:
https://lore.kernel.org/bpf/ad397307a9cd76c9739ee05f4642c7b6a881b7dfb8a2facefa6b2062ffe328ea@mail.kernel.org/
[ ... ]
Quoted 4 lines
tools/testing/selftests/bpf/progs/test_global_func3.c +0
-0
[ ... ]
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 this be "the call stack of 8 frames" rather than 9?
The test has 9 subprogs total (global_func3 plus f1 through f8), but only 8 call levels. The entry function global_func3 starts at frame 0 and is not itself counted by the frame increment. Each static call increments frame by one:
check_max_stack_depth_subprog() {
...
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 matches MAX_CALL_FRAMES. The verifier would print "the call stack of 8 frames is too deep" and the __msg substring check for "9 frames" would not match, causing the test to fail.
The old test with global functions also had 8 call levels and expected "8 frames", since frame++ produced the same count of 8.
---
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/22968848938
Emil Tsalapatis
reviewerRe: [PATCH bpf-next v5 1/2] bpf: Only enforce 8 frame call stack limit for all-static stacks
Quoted 59 lines · bot+bpf-ci
Quoted 6 lines
kernel/bpf/verifier.c +0
-0@@ -6733,9 +6733,11 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,struct bpf_insn *insn = env->prog->insnsi;kernel/bpf/verifier.c static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx, · line 6740
Quoted 10 lines
kernel/bpf/verifier.c +5
-3int 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 */ + env->dinfo[idx].caller =-1 ;The function header comment above this hunk still reads:
Since recursion is prevented by
check_cfg()this algorithm only needs a local stack ofMAX_CALL_FRAMESto remember callsitesThe local stack arrays (ret_insn[] and ret_prog[]) have been removed in favor of per-subprog dinfo fields. Should this comment be updated to reflect the new approach?
This was also noted during the v3 and v4 reviews:
https://lore.kernel.org/bpf/ad397307a9cd76c9739ee05f4642c7b6a881b7dfb8a2facefa6b2062ffe328ea@mail.kernel.org/[ ... ]
Quoted 4 lines
tools/testing/selftests/bpf/progs/test_global_func3.c +0
-0[ ... ]
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 this be "the call stack of 8 frames" rather than 9?
The test has 9 subprogs total (
global_func3plus f1 through f8), but only 8 call levels. The entry functionglobal_func3starts at frame 0 and is not itself counted by the frame increment. Each static call increments frame by one:check_max_stack_depth_subprog() { ... 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 8 lines
With 8 static calls (
global_func3-> f8 -> f7 -> ... -> f1), frame reaches 8, which matchesMAX_CALL_FRAMES. The verifier would print "the call stack of 8 frames is too deep" and the__msgsubstring check for "9 frames" would not match, causing the test to fail.The old test with global functions also had 8 call levels and expected "8 frames", since frame++ produced the same count of 8.
I'd say no to either suggestion. The updated expected failure message is correct, and the old comment still applies for consecutive static stack frames even if we don't refer to a single stack-allocated call stack anymore.
Quoted 6 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.mdCI run summary: https://github.com/kernel-patches/bpf/actions/runs/22968848938
Re: [PATCH bpf-next v5 1/2] bpf: Only enforce 8 frame call stack limit for all-static stacks
In reply to Emil TsalapatisQuoted 48 lines · Emil Tsalapatis
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.cselftest to use static functions, since with the new patch it would otherwise unexpectedly pass verification.Acked-by Mykyta Yatsenko <[email protected]>Acked-by Eduard Zingerman <[email protected]>Signed-off-by Emil Tsalapatis <[email protected]>--- include/linux/bpf_verifier.h | 9 +++ kernel/bpf/verifier.c | 62 +++++++++++++------ .../selftests/bpf/progs/test_global_func3.c | 18 +++--- 3 files changed, 61 insertions(+), 28 deletions(-)include/linux/bpf_verifier.h +6
-0@@ -742,6 +742,12 @@ struct bpf_scc_info {struct bpf_liveness ; +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 */ +}; +/* single container for all structs * one verifier_env per bpf_check() call */
include/linux/bpf_verifier.h struct bpf_verifier_env { · line 862
Quoted 6 lines
include/linux/bpf_verifier.h +3
-0@@ -851,6 +857,9 @@ struct bpf_verifier_env {u32 scc_cnt;struct bpf_iarray *succ;struct bpf_iarray *gotox_tmp_buf; + +/* temporary state used for call frame depth calculation */ +struct bpf_subprog_call_depth_info *dinfo;
It doesn't have to be part of env, right?
Could you just pass it as another argument to check_max_stack_depth_subprog() ?
'env' is for things that need to be around for most of the verifier's duration.
This one was added to 'env' just to avoid an extra argument between check_max_stack_depth() and check_max_stack_depth_subprog(). Why?
Seems like a wrong tradeoff.
and with that struct bpf_subprog_call_depth_info can be local in verifier.c?
pw-bot: cr
Emil Tsalapatis
reviewerRe: [PATCH bpf-next v5 1/2] bpf: Only enforce 8 frame call stack limit for all-static stacks
Quoted 66 lines · Alexei Starovoitov
Quoted 48 lines · Emil Tsalapatis
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.cselftest to use static functions, since with the new patch it would otherwise unexpectedly pass verification.Acked-by Mykyta Yatsenko <[email protected]>Acked-by Eduard Zingerman <[email protected]>Signed-off-by Emil Tsalapatis <[email protected]>--- include/linux/bpf_verifier.h | 9 +++ kernel/bpf/verifier.c | 62 +++++++++++++------ .../selftests/bpf/progs/test_global_func3.c | 18 +++--- 3 files changed, 61 insertions(+), 28 deletions(-)include/linux/bpf_verifier.h +6
-0@@ -742,6 +742,12 @@ struct bpf_scc_info {struct bpf_liveness ; +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 */ +}; +/* single container for all structs * one verifier_env per bpf_check() call */ include/linux/bpf_verifier.h struct bpf_verifier_env { · line 862
Quoted 6 lines
include/linux/bpf_verifier.h +3
-0@@ -851,6 +857,9 @@ struct bpf_verifier_env {u32 scc_cnt;struct bpf_iarray *succ;struct bpf_iarray *gotox_tmp_buf; + +/* temporary state used for call frame depth calculation */ +struct bpf_subprog_call_depth_info *dinfo;It doesn't have to be part of env, right?
Could you just pass it as another argument tocheck_max_stack_depth_subprog()?'env' is for things that need to be around for most of the verifier's duration.
This one was added to 'env' just to avoid an extra argument betweencheck_max_stack_depth()andcheck_max_stack_depth_subprog(). Why?
Seems like a wrong tradeoff.
Quoted 3 lines
and with that struct
bpf_subprog_call_depth_infocan be local inverifier.c?
Moving the struct out of env and into verifier.c is a strict improvement over the current version, I will adjust the patch and respin.
Quoted 1 line
pw-bot: cr
Emil Tsalapatis
reviewerPATCH v5 2/2 selftests/bpf: Add deep call stack selftests
In reply to Emil TsalapatisAdd 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
@@ -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