bpf: Bump maximum call stack depth to 16
Subsystems (4)
Emil Tsalapatis
reviewerPATCH 1/1 bpf: Bump maximum call stack depth to 16
The BPF verifier currently limits the maximum call stack depth 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.
Bump the maximum call stack depth to 16 stack frames. This does not adjust the maximum stack size of 512.
Also adjust selftests that assume the max call stack depth is 8.
--- include/linux/bpf_verifier.h | 18 +++---- .../selftests/bpf/progs/test_global_func3.c | 52 +++++++++++++++++- .../selftests/bpf/progs/verifier_loops1.c | 2 +- tools/testing/selftests/bpf/verifier/calls.c | 54 +++++++++++++++++-- 4 files changed, 111 insertions(+), 15 deletions(-)
include/linux/bpf_verifier.h +9 -9
@@ -317,25 +317,25 @@ struct bpf_func_state {int allocated_stack; }; -#define MAX_CALL_FRAMES 8 +#define MAX_CALL_FRAMES 16/* instruction history flags, used in bpf_jmp_history_entry.flags field */ enum {/* instruction references stack slot through PTR_TO_STACK register; -* we also store stack's frame number in lower 3 bits (MAX_CALL_FRAMES is 8) +* we also store stack's frame number in lower 4 bits (MAX_CALL_FRAMES is 16) * and accessed stack slot's index in next 6 bits (MAX_BPF_STACK is 512, * 8 bytes per slot, so slot index (spi) is [0, 63]) */ -INSN_F_FRAMENO_MASK =0x7 ,/* 3 bits */ +INSN_F_FRAMENO_MASK =0xf ,/* 4 bits */ INSN_F_SPI_MASK =0x3f ,/* 6 bits */ -INSN_F_SPI_SHIFT =3 ,/* shifted 3 bits to the left */ +INSN_F_SPI_SHIFT =4 ,/* shifted 4 bits to the left */ -INSN_F_STACK_ACCESS =BIT (9 ), +INSN_F_STACK_ACCESS =BIT (10 ), -INSN_F_DST_REG_STACK =BIT (10 ),/* dst_reg is PTR_TO_STACK */ -INSN_F_SRC_REG_STACK =BIT (11 ),/* src_reg is PTR_TO_STACK */ -/* total 12 bits are used now. */ +INSN_F_DST_REG_STACK =BIT (11 ),/* dst_reg is PTR_TO_STACK */ +INSN_F_SRC_REG_STACK =BIT (12 ),/* src_reg is PTR_TO_STACK */ +/* total 13 bits are used now. */ };static_assert (INSN_F_FRAMENO_MASK +1 >=MAX_CALL_FRAMES );
@@ -346,7 +346,7 @@ struct bpf_jmp_history_entry {/* insn idx can't be bigger than 1 million */ u32 prev_idx : 20;/* special INSN_F_xxx flags */ - u32 flags : 12; + u32 flags : 13;/* additional registers that need precision tracking when this * jump is backtracked, vector of six 10-bit records */
tools/testing/selftests/bpf/progs/test_global_func3.c +50 -2
59 lines not on this page · raw message
tools/testing/selftests/bpf/progs/verifier_loops1.c +1 -1
@@ -139,7 +139,7 @@ SEC("tracepoint") __description("bounded recursion") __failure /* verifier limitation in detecting max stack depth */ -__msg("the call stack of 8 frames is too deep !") +__msg("the call stack of 16 frames is too deep !")__naked void bounded_recursion (void ) { asm volatile (" \
tools/testing/selftests/bpf/verifier/calls.c +51 -3
84 lines not on this page · raw message
Signature · 1 line
2.49.0
[email protected]
AI reviewWas LR_FRAMENO_BITS in kernel/bpf/verifier.c intended to remain at 3 bits?
Quoted 10 lines
include/linux/bpf_verifier.h +1
-1@@ -317,25 +317,25 @@ struct bpf_func_state {int allocated_stack; }; -#define MAX_CALL_FRAMES 8 +#define MAX_CALL_FRAMES 16
[ ... ]
include/linux/bpf_verifier.h struct bpf_jmp_history_entry { · line 352
Quoted 9 lines
include/linux/bpf_verifier.h +1
-1@@ -346,7 +346,7 @@ struct bpf_jmp_history_entry {/* insn idx can't be bigger than 1 million */ u32 prev_idx : 20;/* special INSN_F_xxx flags */ - u32 flags : 12; + u32 flags : 13;/* additional registers that need precision tracking when this * jump is backtracked, vector of six 10-bit records */
Was LR_FRAMENO_BITS in kernel/bpf/verifier.c intended to remain at 3 bits?
The linked_regs packing uses LR_FRAMENO_BITS to encode frame numbers:
#define LR_FRAMENO_BITS 3
#define LR_FRAMENO_MASK ((1ull << LR_FRAMENO_BITS) - 1)With MAX_CALL_FRAMES now at 16, frame numbers can be 0-15, but the 3-bit mask (0x7) will truncate frames 8-15:
collect_linked_regs():
for (i = vstate->curframe; i >= 0; i--)
__collect_linked_regs(linked_regs, reg, id, i, j, true);
^
frameno can be 0-15
linked_regs_unpack():
e->frameno = val & LR_FRAMENO_MASK;
^^^^^^^^^^^^^^^^^
mask is 0x7, truncates 8-15This means frame 8 becomes 0, frame 9 becomes 1, etc., causing sync_linked_regs() to update registers in the wrong stack frame during precision backtracking.
The comment at linked_regs_pack() still documents "3-bits frameno" which now conflicts with the 16-frame 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/21610711856
AI-authorship-score: low
AI-authorship-explanation: The commit follows standard kernel conventions with concise technical language; the oversight of LR_FRAMENO_BITS is characteristic of human error rather than AI-generated code which would typically catch all related constants.
issues-found: 1
issue-severity-score: medium
issue-severity-explanation: LR_FRAMENO_BITS remaining at 3 bits causes frame number truncation for frames 8-15, leading to incorrect precision tracking in the verifier which could cause incorrect program acceptance or rejection.
Emil Tsalapatis
reviewerQuoted 44 lines · bot+bpf-ci
Quoted 10 lines
include/linux/bpf_verifier.h +1
-1@@ -317,25 +317,25 @@ struct bpf_func_state {int allocated_stack; }; -#define MAX_CALL_FRAMES 8 +#define MAX_CALL_FRAMES 16[ ... ]
include/linux/bpf_verifier.h struct bpf_jmp_history_entry { · line 352
Quoted 9 lines
include/linux/bpf_verifier.h +1
-1@@ -346,7 +346,7 @@ struct bpf_jmp_history_entry {/* insn idx can't be bigger than 1 million */ u32 prev_idx : 20;/* special INSN_F_xxx flags */ - u32 flags : 12; + u32 flags : 13;/* additional registers that need precision tracking when this * jump is backtracked, vector of six 10-bit records */ Was
LR_FRAMENO_BITSinkernel/bpf/verifier.cintended to remain at 3 bits?The
linked_regspacking usesLR_FRAMENO_BITSto encode frame numbers:#define LR_FRAMENO_BITS 3 #define LR_FRAMENO_MASK ((1ull << LR_FRAMENO_BITS) - 1)With
MAX_CALL_FRAMESnow at 16, frame numbers can be 0-15, but the 3-bit mask (0x7) will truncate frames 8-15:collect_linked_regs(): for (i = vstate->curframe; i >= 0; i--) __collect_linked_regs(linked_regs, reg, id, i, j, true); ^ frameno can be 0-15 linked_regs_unpack(): e->frameno = val & LR_FRAMENO_MASK; ^^^^^^^^^^^^^^^^^ mask is 0x7, truncates 8-15
Quoted 8 lines
This means frame 8 becomes 0, frame 9 becomes 1, etc., causing
sync_linked_regs()to update registers in the wrong stack frame during precision backtracking.The comment at
linked_regs_pack()still documents "3-bits frameno" which now conflicts with the 16-frame limit.
The AI is right, we must also adjust the packed linked register masks.
This complicates things, we now need 66 bits instead of 60 for the linked registers and cannot typecast the struct linked_reg into a u64 anymore. We need one more byte for this for the linked registers.
An option is making a new struct to replace the u64 for linked registers with a buffer of 7 bytes, like so:
/* A buffer of 72 bytes to store linked registers in a packed representation. */
struct linked_regs_packed {
u8 data[9];
}struct bpf_jmp_history_entry {
u32 idx;
/* insn idx can't be bigger than 1 million */
u32 prev_idx : 20;
/* special INSN_F_xxx flags */
u32 flags : 13;
/* additional registers that need precision tracking when this
* jump is backtracked, vector of six 11-bit records (66 bits).
*/
struct linked_regs_packed linked_regs;
};This actually brings down the struct's total size down from 24 to 20 bytes (tested with gcc 14.2) as the struct does not need to be aligned to an 8-byte boundary. It would complicate packing and unpacking the linked registers though, and we'd need to see how the new code affects verification speed.
Quoted 11 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/21610711856
AI-authorship-score: low
AI-authorship-explanation: The commit follows standard kernel conventions with concise technical language; the oversight ofLR_FRAMENO_BITSis characteristic of human error rather than AI-generated code which would typically catch all related constants.
issues-found: 1
issue-severity-score: medium
issue-severity-explanation:LR_FRAMENO_BITSremaining at 3 bits causes frame number truncation for frames 8-15, leading to incorrect precision tracking in the verifier which could cause incorrect program acceptance or rejection.
Quoted 81 lines · Emil Tsalapatis
Quoted 44 lines · bot+bpf-ci
Quoted 10 lines
include/linux/bpf_verifier.h +1
-1@@ -317,25 +317,25 @@ struct bpf_func_state {int allocated_stack; }; -#define MAX_CALL_FRAMES 8 +#define MAX_CALL_FRAMES 16[ ... ]
include/linux/bpf_verifier.h struct bpf_jmp_history_entry { · line 352
Quoted 9 lines
include/linux/bpf_verifier.h +1
-1@@ -346,7 +346,7 @@ struct bpf_jmp_history_entry {/* insn idx can't be bigger than 1 million */ u32 prev_idx : 20;/* special INSN_F_xxx flags */ - u32 flags : 12; + u32 flags : 13;/* additional registers that need precision tracking when this * jump is backtracked, vector of six 10-bit records */ Was
LR_FRAMENO_BITSinkernel/bpf/verifier.cintended to remain at 3 bits?The
linked_regspacking usesLR_FRAMENO_BITSto encode frame numbers:#define LR_FRAMENO_BITS 3 #define LR_FRAMENO_MASK ((1ull << LR_FRAMENO_BITS) - 1)With
MAX_CALL_FRAMESnow at 16, frame numbers can be 0-15, but the 3-bit mask (0x7) will truncate frames 8-15:collect_linked_regs(): for (i = vstate->curframe; i >= 0; i--) __collect_linked_regs(linked_regs, reg, id, i, j, true); ^ frameno can be 0-15 linked_regs_unpack(): e->frameno = val & LR_FRAMENO_MASK; ^^^^^^^^^^^^^^^^^ mask is 0x7, truncates 8-15Quoted 8 lines
This means frame 8 becomes 0, frame 9 becomes 1, etc., causing
sync_linked_regs()to update registers in the wrong stack frame during precision backtracking.The comment at
linked_regs_pack()still documents "3-bits frameno" which now conflicts with the 16-frame limit.The AI is right, we must also adjust the packed linked register masks.
This complicates things, we now need 66 bits instead of 60 for the linked registers and cannot typecast the struct
linked_reginto a u64 anymore. We need one more byte for this for the linked registers.An option is making a new struct to replace the u64 for linked registers with a buffer of 7 bytes, like so:
/* A buffer of 72 bytes to store linked registers in a packed representation. */
struct linked_regs_packed { u8 data[9]; }struct bpf_jmp_history_entry { u32 idx; /* insn idx can't be bigger than 1 million */ u32 prev_idx : 20; /* special INSN_F_xxx flags */ u32 flags : 13; /* additional registers that need precision tracking when this * jump is backtracked, vector of six 11-bit records (66 bits). */ struct linked_regs_packed linked_regs; };
Quoted 4 lines
This actually brings down the struct's total size down from 24 to 20 bytes (tested with gcc 14.2) as the struct does not need to be aligned to an 8-byte boundary. It would complicate packing and unpacking the linked registers though, and we'd need to see how the new code affects verification speed.
That may be ok, but before digging into it further please collect performance numbers for the verifier time and memory consumption across all selftest/scx/meta progs.
struct callchain will double its size and it's hot in liveness analysis.
Instead of bumping the main limit could you introduce and bump a new limit for global functions in the call chain. I think we can keep 8 for static functions and no data structures need to change.
pw-bot: cr
Emil Tsalapatis
reviewerQuoted 92 lines · Alexei Starovoitov
Quoted 81 lines · Emil Tsalapatis
Quoted 44 lines · bot+bpf-ci
Quoted 10 lines
include/linux/bpf_verifier.h +1
-1@@ -317,25 +317,25 @@ struct bpf_func_state {int allocated_stack; }; -#define MAX_CALL_FRAMES 8 +#define MAX_CALL_FRAMES 16[ ... ]
include/linux/bpf_verifier.h struct bpf_jmp_history_entry { · line 352
Quoted 9 lines
include/linux/bpf_verifier.h +1
-1@@ -346,7 +346,7 @@ struct bpf_jmp_history_entry {/* insn idx can't be bigger than 1 million */ u32 prev_idx : 20;/* special INSN_F_xxx flags */ - u32 flags : 12; + u32 flags : 13;/* additional registers that need precision tracking when this * jump is backtracked, vector of six 10-bit records */ Was
LR_FRAMENO_BITSinkernel/bpf/verifier.cintended to remain at 3 bits?The
linked_regspacking usesLR_FRAMENO_BITSto encode frame numbers:#define LR_FRAMENO_BITS 3 #define LR_FRAMENO_MASK ((1ull << LR_FRAMENO_BITS) - 1)With
MAX_CALL_FRAMESnow at 16, frame numbers can be 0-15, but the 3-bit mask (0x7) will truncate frames 8-15:collect_linked_regs(): for (i = vstate->curframe; i >= 0; i--) __collect_linked_regs(linked_regs, reg, id, i, j, true); ^ frameno can be 0-15 linked_regs_unpack(): e->frameno = val & LR_FRAMENO_MASK; ^^^^^^^^^^^^^^^^^ mask is 0x7, truncates 8-15Quoted 8 lines
This means frame 8 becomes 0, frame 9 becomes 1, etc., causing
sync_linked_regs()to update registers in the wrong stack frame during precision backtracking.The comment at
linked_regs_pack()still documents "3-bits frameno" which now conflicts with the 16-frame limit.The AI is right, we must also adjust the packed linked register masks.
This complicates things, we now need 66 bits instead of 60 for the linked registers and cannot typecast the struct
linked_reginto a u64 anymore. We need one more byte for this for the linked registers.An option is making a new struct to replace the u64 for linked registers with a buffer of 7 bytes, like so:
/* A buffer of 72 bytes to store linked registers in a packed representation. */
struct linked_regs_packed { u8 data[9]; }struct bpf_jmp_history_entry { u32 idx; /* insn idx can't be bigger than 1 million */ u32 prev_idx : 20; /* special INSN_F_xxx flags */ u32 flags : 13; /* additional registers that need precision tracking when this * jump is backtracked, vector of six 11-bit records (66 bits). */ struct linked_regs_packed linked_regs; };Quoted 4 lines
This actually brings down the struct's total size down from 24 to 20 bytes (tested with gcc 14.2) as the struct does not need to be aligned to an 8-byte boundary. It would complicate packing and unpacking the linked registers though, and we'd need to see how the new code affects verification speed.
That may be ok, but before digging into it further please collect performance numbers for the verifier time and memory consumption across all selftest/scx/meta progs.
struct callchain will double its size and it's hot in liveness analysis.
Quoted 5 lines
Instead of bumping the main limit could you introduce and bump a new limit for global functions in the call chain. I think we can keep 8 for static functions and no data structures need to change.
Ack, that would solve the issue since most programs what hit call stack depth limits do so because they heavily use global functions.
Quoted 1 line
pw-bot: cr