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. Signed-off-by: Emil Tsalapatis --- 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(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 8355b585cd18..9f7fc990f380 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -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 */ diff --git a/tools/testing/selftests/bpf/progs/test_global_func3.c b/tools/testing/selftests/bpf/progs/test_global_func3.c index 142b682d3c2f..7a0b7c4b9274 100644 --- a/tools/testing/selftests/bpf/progs/test_global_func3.c +++ b/tools/testing/selftests/bpf/progs/test_global_func3.c @@ -53,9 +53,57 @@ int f8(struct __sk_buff *skb) return f7(skb); } +__attribute__ ((noinline)) +int f9(struct __sk_buff *skb) +{ + return f8(skb); +} + +__attribute__ ((noinline)) +int f10(struct __sk_buff *skb) +{ + return f9(skb); +} + +__attribute__ ((noinline)) +int f11(struct __sk_buff *skb) +{ + return f10(skb); +} + +__attribute__ ((noinline)) +int f12(struct __sk_buff *skb) +{ + return f11(skb); +} + +__attribute__ ((noinline)) +int f13(struct __sk_buff *skb) +{ + return f12(skb); +} + +__attribute__ ((noinline)) +int f14(struct __sk_buff *skb) +{ + return f13(skb); +} + +__attribute__ ((noinline)) +int f15(struct __sk_buff *skb) +{ + return f14(skb); +} + +__attribute__ ((noinline)) +int f16(struct __sk_buff *skb) +{ + return f15(skb); +} + SEC("tc") -__failure __msg("the call stack of 8 frames") +__failure __msg("the call stack of 16 frames") int global_func3(struct __sk_buff *skb) { - return f8(skb); + return f16(skb); } diff --git a/tools/testing/selftests/bpf/progs/verifier_loops1.c b/tools/testing/selftests/bpf/progs/verifier_loops1.c index fbdde80e7b90..0970f25f9c60 100644 --- a/tools/testing/selftests/bpf/progs/verifier_loops1.c +++ b/tools/testing/selftests/bpf/progs/verifier_loops1.c @@ -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 (" \ diff --git a/tools/testing/selftests/bpf/verifier/calls.c b/tools/testing/selftests/bpf/verifier/calls.c index 9ca83dce100d..077db99d6a1f 100644 --- a/tools/testing/selftests/bpf/verifier/calls.c +++ b/tools/testing/selftests/bpf/verifier/calls.c @@ -455,7 +455,7 @@ BPF_EXIT_INSN(), }, .prog_type = BPF_PROG_TYPE_TRACEPOINT, - .errstr = "the call stack of 9 frames is too deep", + .errstr = "the call stack of 17 frames is too deep", .result = REJECT, }, { @@ -812,7 +812,7 @@ BPF_EXIT_INSN(), }, .prog_type = BPF_PROG_TYPE_TRACEPOINT, - .errstr = "the call stack of 9 frames is too deep", + .errstr = "the call stack of 17 frames is too deep", .result = REJECT, }, { @@ -824,7 +824,7 @@ BPF_EXIT_INSN(), }, .prog_type = BPF_PROG_TYPE_TRACEPOINT, - .errstr = "the call stack of 9 frames is too deep", + .errstr = "the call stack of 17 frames is too deep", .result = REJECT, }, { @@ -1219,6 +1219,30 @@ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call H */ BPF_EXIT_INSN(), /* H */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call I */ + BPF_EXIT_INSN(), + /* I */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call J */ + BPF_EXIT_INSN(), + /* J */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call K */ + BPF_EXIT_INSN(), + /* K */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call L */ + BPF_EXIT_INSN(), + /* L */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call M */ + BPF_EXIT_INSN(), + /* M */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call N */ + BPF_EXIT_INSN(), + /* N */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call O */ + BPF_EXIT_INSN(), + /* O */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P */ + BPF_EXIT_INSN(), + /* P */ BPF_MOV64_IMM(BPF_REG_0, 0), BPF_EXIT_INSN(), }, @@ -1257,6 +1281,30 @@ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call H */ BPF_EXIT_INSN(), /* H */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call I */ + BPF_EXIT_INSN(), + /* I */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call J */ + BPF_EXIT_INSN(), + /* J */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call K */ + BPF_EXIT_INSN(), + /* K */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call L */ + BPF_EXIT_INSN(), + /* L */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call M */ + BPF_EXIT_INSN(), + /* M */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call N */ + BPF_EXIT_INSN(), + /* N */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call O */ + BPF_EXIT_INSN(), + /* O */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P */ + BPF_EXIT_INSN(), + /* P */ BPF_MOV64_IMM(BPF_REG_0, 0), BPF_EXIT_INSN(), }, -- 2.49.0