Re: [PATCH bpf-next v4 22/46] bpf: Allow recursive subprogs

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 2 potential
issues to consider:
- [Medium] bpf: off-by-one frame count for recursion in
  compute_call_depth()
- [Medium] bpf: spurious budget exit on loop back-edge in
  check_recursion_guard()
--

commit 7c6074f7480e70a1121bc45054dfaf6385da6057
Author: Alexei Starovoitov <ast@kernel.org>

bpf: Allow recursive subprogs

This commit allows recursive static subprograms by detecting cycles in the
call graph, bounding their static stack accounting, and verifying the
runtime recursion guard exit path.

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 3c3d1c8ea4529..ef68796c04ddf 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c

[ ... ]

> @@ -6143,11 +6175,17 @@ static void compute_call_depth(struct bpf_verifier_env *env, struct bpf_call_gra
>  		for_each_set_bit(s, cg->live, cg->cnt) {
>  			if (dinfo[s].depth < 0)
>  				continue;
> -			depth = dinfo[s].depth + subprog_stack_size(env, s);
> -			arena_depth = dinfo[s].arena_depth + si[s].arena_stack_depth;
>  			for_each_set_bit(j, subprog_calls(cg, s), cg->cnt) {
>  				callee = &dinfo[j];
> -				frame = bpf_subprog_is_global(env, j) ? 0 : dinfo[s].frame + 1;
> +				depth = dinfo[s].depth;
> +				arena_depth = dinfo[s].arena_depth;
> +				if (!si[s].recursive || !si[j].recursive) {
> +					depth += subprog_stack_size(env, s);
> +					arena_depth += si[s].arena_stack_depth;
> +				}
> +				frame = dinfo[s].frame + !si[j].recursive;
> +				if (bpf_subprog_is_global(env, j))
> +					frame = 0;

[Severity: Medium]
Should this increment frame by (!si[s].recursive || !si[j].recursive),
matching the depth and arena_depth calculation above?

When a non-recursive subprogram s calls a recursive subprogram j,
!si[j].recursive is 0, so entering the recursion does not increment
dinfo[j].frame and edges within the recursion also add 0.  A recursion
therefore counts as 0 frames instead of 1 in dinfo[].frame, allowing a
static call chain with recursive subprograms to bypass the MAX_CALL_FRAMES
and MAX_CALL_FRAMES_INTERP checks in check_call_depth().

[ ... ]

> @@ -22106,6 +22294,21 @@ static int flow_drain(struct bpf_verifier_env *env)
>  	return err;
>  }
>  
> +/*
> + * A subprog on a cycle of the call graph checks the stack at run time, see
> + * bpf_insert_recursion_checks(). When there is no room, or the time slice is over, it leaves
> + * at once with 0 in place of the result: it unwinds if it can, see bail_unwinds, otherwise
> + * it returns and callers have to be fine with that.
> + */
> +static int check_recursion_guard(struct bpf_verifier_env *env)
> +{
> +	struct bpf_subprog_info *sub = &env->subprog_info[cur_func(env)->subprogno];
> +
> +	if (!sub->recursive || env->insn_idx != sub->start)
> +		return 0;
> +	return push_budget_exit(env);
> +}

[Severity: Medium]
Does check_recursion_guard() push a spurious exit when sub->start is also a
loop header reached via an intra-subprogram back-edge?

In bpf_insert_recursion_checks(), bpf_patch_list_insert() redirects only
calls to the runtime recursion check, while intra-subprogram jumps to
sub->start land after the check.  Here, check_recursion_guard() calls
push_budget_exit() every time env->insn_idx == sub->start without checking
whether the state just entered the subprogram or looped back from inside
it.  If a loop headed at sub->start holds a reference, lock, or RCU read
lock across the back-edge, that branch reaches sub->bail_insn with the
resource still held and causes the verifier to reject the program.

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261107033758.1547725-1-alexei.starovoitov@gmail.com?part=22