From: Alexei Starovoitov The verifier rejected recursion, because it cannot calculate the depth of the stack at load time. Now a prog with recursion loads, and the kernel limits the recursion at run time. Each recursive subprog starts with a check of the stack and of the number of calls. When the check fails, the subprog returns 0. test the recursion result -------------------------------------- --------------------- --------- callx_unbounded_recursion never stops returns 0 callx_bounded_recursion counts down to 0 returns 0 callx_mutual_recursion two subprogs loads callx_rodata_recursion pointer from .rodata loads recursion_via_global_func_and_callback global subprog and loads bpf_loop() callback calls: recursive call. test1 a call insn is its rejected own target BPF_PSEUDO_FUNC reference to the main the main prog is a rejected program timer callback The verifier rejected the first five progs. It continues to reject the last two, with new messages: "calls itself" and "recursive call of the main program". Other changes: - MAX_CALL_FRAMES is 32. The two chains of calls that must be too deep get 16 more subprogs. - "calls: conditional call 6" is a loop that can spin forever. The verifier rejected it with "infinite loop detected". Now the verifier adds may_goto to such a loop, and the prog loads. - callx_retval_is_tracked and callx_precision expected "to caller at" and mark_precise lines. The log does not have these lines. Expect the values of the registers. Signed-off-by: Alexei Starovoitov --- .../selftests/bpf/progs/verifier_callx.c | 22 ++-- .../bpf/progs/verifier_callx_rodata.c | 2 +- .../bpf/progs/verifier_global_subprogs.c | 7 +- tools/testing/selftests/bpf/verifier/calls.c | 101 +++++++++++++++++- .../selftests/bpf/verifier/pseudo_func.c | 2 +- 5 files changed, 110 insertions(+), 24 deletions(-) diff --git a/tools/testing/selftests/bpf/progs/verifier_callx.c b/tools/testing/selftests/bpf/progs/verifier_callx.c index 7e59188d9fca..5594bce7601c 100644 --- a/tools/testing/selftests/bpf/progs/verifier_callx.c +++ b/tools/testing/selftests/bpf/progs/verifier_callx.c @@ -245,8 +245,7 @@ __naked void callx_scratches_args(void) /* return value of the callee is tracked */ SEC("socket") __success __log_level(2) -__msg("to caller at 4:") -__msg("R0=6") +__msg("4: R0=6 R10=fp0") __naked void callx_retval_is_tracked(void) { asm volatile ( @@ -523,9 +522,9 @@ static unsigned long self(void) ); } -/* unbounded recursion is caught by the main verification pass */ +/* unbounded recursion is stopped at run time */ SEC("socket") -__failure __msg("frames is too deep") +__success __retval(0) __naked void callx_unbounded_recursion(void) { asm volatile ( @@ -551,12 +550,8 @@ static unsigned long countdown(void) ); } -/* - * The depth of the recursion is known to the main verification pass, - * but recursive calls are not allowed regardless. - */ SEC("socket") -__failure __msg("recursive call from countdown() to countdown()") +__success __retval(0) __naked void callx_bounded_recursion(void) { asm volatile ( @@ -603,7 +598,7 @@ static unsigned long pong(void) } SEC("socket") -__failure __msg("recursive call from") +__success __naked void callx_mutual_recursion(void) { asm volatile ( @@ -926,11 +921,8 @@ long long vals[] SEC(".data.vals") = {1, 2, 3, 4}; SEC("socket") __success __log_level(2) -__msg("mark_precise: frame0: regs=r0 stack= before 12: (95) exit") -__msg("mark_precise: frame1: regs=r0 stack= before 11: (bf) r0 = r1") -__msg("mark_precise: frame1: regs=r1 stack= before 4: (8d) callx r2") -__msg("mark_precise: frame0: regs=r1 stack= before 3: (bf) r1 = r6") -__msg("mark_precise: frame0: regs=r6 stack= before 2: (b7) r6 = 3") +__msg("5: R0=3 R10=fp0") +__msg("8: (0f) r1 += r0 ; R0=24 R1=map_value(map=.data.vals,ks=4,vs=32,imm=24)") __retval(4) __naked void callx_precision(void) { diff --git a/tools/testing/selftests/bpf/progs/verifier_callx_rodata.c b/tools/testing/selftests/bpf/progs/verifier_callx_rodata.c index 6cf58ca9ac5b..85141cd73298 100644 --- a/tools/testing/selftests/bpf/progs/verifier_callx_rodata.c +++ b/tools/testing/selftests/bpf/progs/verifier_callx_rodata.c @@ -571,7 +571,7 @@ static unsigned long selfcall(void) } SEC("socket") -__failure __msg("recursive call from selfcall() to selfcall()") +__success __naked void callx_rodata_recursion(void) { asm volatile ( diff --git a/tools/testing/selftests/bpf/progs/verifier_global_subprogs.c b/tools/testing/selftests/bpf/progs/verifier_global_subprogs.c index 574b26b5a7df..9f5898feb437 100644 --- a/tools/testing/selftests/bpf/progs/verifier_global_subprogs.c +++ b/tools/testing/selftests/bpf/progs/verifier_global_subprogs.c @@ -556,12 +556,11 @@ __noinline int global_calls_loop(int x) /* * loop_cb_calls_static() -> static_calls_global() -> global_calls_loop() -> - * bpf_loop() -> loop_cb_calls_static() is an unbounded recursion that the - * main verification pass can't see, because it doesn't follow calls of global - * functions. None of the functions use stack. + * bpf_loop() -> loop_cb_calls_static() is an unbounded recursion through a global + * function and a helper. It's stopped at run time. None of the functions use stack. */ SEC("?raw_tp") -__failure __msg("recursive call from global_calls_loop() to loop_cb_calls_static()") +__success int recursion_via_global_func_and_callback(const void *ctx) { return loop_cb_calls_static(0, NULL); diff --git a/tools/testing/selftests/bpf/verifier/calls.c b/tools/testing/selftests/bpf/verifier/calls.c index 0af237c02ddf..330421e9c164 100644 --- a/tools/testing/selftests/bpf/verifier/calls.c +++ b/tools/testing/selftests/bpf/verifier/calls.c @@ -559,8 +559,7 @@ BPF_EXIT_INSN(), }, .prog_type = BPF_PROG_TYPE_SCHED_CLS, - .errstr = "infinite loop detected", - .result = REJECT, + .result = ACCEPT, }, { "calls: using r0 returned by callee", @@ -812,7 +811,7 @@ BPF_EXIT_INSN(), }, .prog_type = BPF_PROG_TYPE_TRACEPOINT, - .errstr = "recursive call", + .errstr = "calls itself", .result = REJECT, }, { @@ -1325,6 +1324,54 @@ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P */ BPF_EXIT_INSN(), /* P */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P1 */ + BPF_EXIT_INSN(), + /* P1 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P2 */ + BPF_EXIT_INSN(), + /* P2 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P3 */ + BPF_EXIT_INSN(), + /* P3 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P4 */ + BPF_EXIT_INSN(), + /* P4 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P5 */ + BPF_EXIT_INSN(), + /* P5 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P6 */ + BPF_EXIT_INSN(), + /* P6 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P7 */ + BPF_EXIT_INSN(), + /* P7 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P8 */ + BPF_EXIT_INSN(), + /* P8 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P9 */ + BPF_EXIT_INSN(), + /* P9 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P10 */ + BPF_EXIT_INSN(), + /* P10 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P11 */ + BPF_EXIT_INSN(), + /* P11 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P12 */ + BPF_EXIT_INSN(), + /* P12 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P13 */ + BPF_EXIT_INSN(), + /* P13 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P14 */ + BPF_EXIT_INSN(), + /* P14 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P15 */ + BPF_EXIT_INSN(), + /* P15 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P16 */ + BPF_EXIT_INSN(), + /* P16 */ BPF_MOV64_IMM(BPF_REG_0, 0), BPF_EXIT_INSN(), }, @@ -1387,6 +1434,54 @@ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P */ BPF_EXIT_INSN(), /* P */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P1 */ + BPF_EXIT_INSN(), + /* P1 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P2 */ + BPF_EXIT_INSN(), + /* P2 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P3 */ + BPF_EXIT_INSN(), + /* P3 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P4 */ + BPF_EXIT_INSN(), + /* P4 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P5 */ + BPF_EXIT_INSN(), + /* P5 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P6 */ + BPF_EXIT_INSN(), + /* P6 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P7 */ + BPF_EXIT_INSN(), + /* P7 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P8 */ + BPF_EXIT_INSN(), + /* P8 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P9 */ + BPF_EXIT_INSN(), + /* P9 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P10 */ + BPF_EXIT_INSN(), + /* P10 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P11 */ + BPF_EXIT_INSN(), + /* P11 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P12 */ + BPF_EXIT_INSN(), + /* P12 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P13 */ + BPF_EXIT_INSN(), + /* P13 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P14 */ + BPF_EXIT_INSN(), + /* P14 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P15 */ + BPF_EXIT_INSN(), + /* P15 */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P16 */ + BPF_EXIT_INSN(), + /* P16 */ BPF_MOV64_IMM(BPF_REG_0, 0), BPF_EXIT_INSN(), }, diff --git a/tools/testing/selftests/bpf/verifier/pseudo_func.c b/tools/testing/selftests/bpf/verifier/pseudo_func.c index 63c5c67d51de..44d36b01aa6d 100644 --- a/tools/testing/selftests/bpf/verifier/pseudo_func.c +++ b/tools/testing/selftests/bpf/verifier/pseudo_func.c @@ -30,7 +30,7 @@ .prog_type = BPF_PROG_TYPE_TRACEPOINT, .fixup_map_timer = { 3, 9 }, .result = REJECT, - .errstr = "callback function cannot be the main program", + .errstr = "recursive call of the main program", .func_info = { { 0, 4 /* main_prog */ } }, .func_info_cnt = 1, .btf_strings = "\0int\0ctx\0main_prog", -- 2.55.0