Re: [PATCH v4 bpf-next 2/2] bpf: test the proper verification of tail calls

Eduard Zingerman
2025-11-06T19:50:53Z

On Thu, 2025-11-06 at 11:52 +0100, Martin Teichmann wrote:

[...]

> +SEC("socket")
> +__log_level(2)
> +__msg("19: (85) call bpf_tail_call#12")
> +__msg("(0) frame 0 insn 1 +written -8")
> +__msg("(0) live stack update done in 2 iterations")
> +__msg("14: (95) exit")
> +__msg("(0) frame 0 insn 13 +live -8")
> +__msg("(0) live stack update done in 2 iterations")
> +__msg("22: (95) exit")
> +__msg("(9,15) frame 0 insn 20 +written -8")
> +__msg("(9,15) live stack update done in 2 iterations")
> +__msg("14: (95) exit")
> +__msg("(0) frame 0 insn 13 +live -16")
> +__naked unsigned long caller_stack_write_tail_call(void)
> +{
> + asm volatile (
> + "r6 = r1;"
> + "*(u64 *)(r10 - 8) = -8;"
> + "call %[bpf_get_prandom_u32];"
> + "if r0 != 42 goto 1f;"
> + "goto 2f;"
> + "1:"
> + "*(u64 *)(r10 - 8) = -1024;"
> + "2:"
> + "r1 = r6;"
> + "r2 = r10;"
> + "r2 += -8;"
> + "call write_tail_call;"
> + "r1 = *(u64 *)(r10 - 8);"
> + "r2 = r10;"
> + "r2 += r1;"
> + "r0 = *(u64 *)(r2 + 0);"
> + "exit;"
> + :: __imm(bpf_get_prandom_u32)
> + : __clobber_all);
> +}

This program is not safe, but verifier accepts it as safe.
Note the following log:

0: R1=ctx() R10=fp0
; asm volatile ( @ verifier_live_stack.c:318
0: (bf) r6 = r1 ; R1=ctx() R6=ctx()
1: (7a) *(u64 *)(r10 -8) = -8 ; R10=fp0 fp-8=-8
2: (85) call bpf_get_prandom_u32#7 ; R0=scalar()
3: (55) if r0 != 0x2a goto pc+1 ; R0=42
4: (05) goto pc+1
6: (bf) r1 = r6 ; R1=ctx() R6=ctx()
7: (bf) r2 = r10 ; R2=fp0 R10=fp0
8: (07) r2 += -8 ; R2=fp-8
9: (85) call pc+5
...
from 3 to 5: R0=scalar() R6=ctx() R10=fp0 fp-8=-8
5: R0=scalar() R6=ctx() R10=fp0 fp-8=-8
5: (7a) *(u64 *)(r10 -8) = -1024 ; R10=fp0 fp-8=-1024
6: (bf) r1 = r6 ; R1=ctx() R6=ctx()
7: (bf) r2 = r10 ; R2=fp0 R10=fp0
8: (07) r2 += -8
9: safe

First time instruction #9 is verified for fp-8 == -8,
on a seocnd time verifier does not proceed with abstract
interpretation when fp-8 == -1024.

This happens because verifier assumes that call at (9) always sets
fp-8 to -16.

And it does so, because bpf_insn_successors() does not tell it about
possible function exit after tail call. Note that sack liveness marks
are propagated over the program control flow graph as defined by
bpf_insn_successors().
kernel/bpf/liveness.c has extensive comments about that.

W/o tweak to bpf_insn_successors() verifier assumes that
write_tail_call always sets fp-8 to -16, from which verifier infers
that fp-8 is dead at instruction (9). Verifier does not compare
states for dead stack slots when considering states_equal() in
is_state_visited(). Hence it proceeds with state pruning logic and
stops.

Please adjust check_cfg() in a way, similar to visit_gotox_insn(): for
tail calls, store env->insn_aux_data[t].jt pointing either to the next
instruciton or to program exit. And use this information in
bpf_insn_successors().

(You will need to rebase to do that, the changes for
visit_gotox_insn() landed just yesterday).

> +static __used __naked unsigned long write_tail_call(void)
> +{
> + asm volatile (
> + "r6 = r2;"
> + "r2 = %[map_array] ll;"
> + "r3 = 0;"
> + "call %[bpf_tail_call];"
> + "*(u64 *)(r6 + 0) = -16;"
> + "r0 = 0;"
> + "exit;"
> + :
> + : __imm(bpf_tail_call),
> + __imm_addr(map_array)
> + : __clobber_all);
> +} …