Re: [PATCH bpf-next v3 22/45] bpf: Allow recursive subprogs

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 4 potential issue(s) to consider:
- [Medium] bpf: off-by-one frame count for recursion in compute_call_depth()
- [Medium] bpf: uncleared recursive marks on non-live subprogs in check_recursion()
- [Medium] bpf: async callback edge mismatch in mark_recursive_subprogs()
- [Medium] bpf: spurious budget exit on loop back-edge in check_recursion_guard()
--

commit 3e4e0bb05c4c0b3219c8960f2496445434c33bfc
Author: Alexei Starovoitov <ast@kernel.org>

bpf: Allow recursive subprogs

This commit allows recursive static subprograms in BPF programs by identifying
cycles in the call graph prior to main verification, verifying runtime
recursion guard edges at subprogram entry, and adjusting liveness and stack
depth checks for recursive call cycles.

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index b61166f670945..e29fc3ee363a9 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
[ ... ]
> @@ -5975,20 +5979,45 @@ static int check_exception_cb(struct bpf_verifier_env *env, struct bpf_call_grap
>  	return 0;
>  }
>  
> +static bool bpf_prog_reenters_datapath(const struct bpf_prog *prog);
> +
>  /*
> - * The DFS of sort_subprogs_topo() follows the address of a function like a call, and
> - * tolerates a cycle only when such address closes it, since it doesn't know what it is
> - * taken for. Such cycle counts as a recursion, unless the function is an async callback:
> - * its address is not an edge of the graph. The main verification pass limits the
> - * depth of the recursion, but it doesn't follow calls of global functions.
> + * Every subprog on a cycle has to check the stack at run time. mark_recursive_subprogs()
> + * didn't see the cycle coming when a helper got the callback from a table of
> + * functions, or from another subprog. A subprog that it marked for callx, which turned out
> + * to call something else, needs no check.
>   */
>  static int check_recursion(struct bpf_verifier_env *env, struct bpf_call_graph *cg)
>  {
>  	int j, s;
>  
>  	for_each_set_bit(s, cg->live, cg->cnt) {
> -		if (!test_bit(s, subprog_reach(cg, s)))
> +		if (!test_bit(s, subprog_reach(cg, s))) {
> +			env->subprog_info[s].recursive = false;
>  			continue;
> +		}

[Severity: Medium]
As reported by bot+bpf-ci@kernel.org on v2 [1], check_recursion() only
iterates over cg->live when clearing env->subprog_info[s].recursive.

Before the main pass, mark_recursive_subprogs() scans all subprograms from 0
to env->subprog_cnt - 1, adds every subprogram in env->func_ptrs and
BPF_PSEUDO_FUNC instructions to taken, and connects every subprogram
containing callx to all subprograms in taken. If an uncalled subprogram s in a
function pointer table has callx or is part of a cycle in that
over-approximated graph, mark_recursive_subprogs() sets si[s].recursive =
true.

When the main pass never calls s via callx, record_callx_edge() does not
record an edge to s and build_call_graph() leaves s out of cg->live. Because
check_recursion() only walks cg->live, si[s].recursive remains true and skips
the bpf_enable_priv_stack(), bpf_prog_reenters_datapath(), and
bpf_prog_has_invocation_budget() checks.

Later in bpf_check(), bpf_insert_recursion_checks() runs before dead code
elimination and scans all subprograms:

kernel/bpf/fixups.c:bpf_insert_recursion_checks() {
	for (s = 1; s < env->subprog_cnt; s++)
		found |= si[s].recursive;
	if (!found)
		return 0;
	env->prog->jit_required = 1;

	for (s = 1; s < env->subprog_cnt; s++) {
		if (!si[s].recursive)
			continue;
		...
}

Doesn't this leave si[s].recursive set on unreachable subprograms, forcing
env->prog->jit_required = 1 and patching recursion checks into dead
subprograms even on architectures or program types that do not support
recursion?

[ ... ]
> @@ -6134,11 +6164,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]
As reported by Sashiko on v2 [2], in compute_call_depth(), dinfo[0].frame
starts at 0 for the main program, and check_call_depth() checks
dinfo[s].frame >= MAX_CALL_FRAMES and dinfo[s].frame >= MAX_CALL_FRAMES_INTERP
directly without adding 1 for subprogram s itself.

When a non-recursive caller s (!si[s].recursive) calls a recursive callee j
(si[j].recursive), frame = dinfo[s].frame + !si[j].recursive adds 0 on entry
into the recursion, 0 on edges within the recursion, and 1 only for a
subsequent non-recursive callee k when exiting the recursion. This causes the
entire recursive component to count as 0 frames instead of 1 frame in
dinfo[].frame, allowing a static call chain containing recursive subprograms
to exceed MAX_CALL_FRAMES (32) or MAX_CALL_FRAMES_INTERP (16) without being
rejected by check_call_depth().

Should frame be incremented by (!si[s].recursive || !si[j].recursive) to match
the condition used for depth and arena_depth right above it, so that a
recursion counts as one frame in the static call chain?

[ ... ]
> @@ -6302,6 +6342,151 @@ static int check_call_depth(struct bpf_verifier_env *env, struct bpf_call_graph
>  	return err;
>  }
>  
> +/*
> + * The address of the callback at @idx goes nowhere but to a helper that keeps it for
> + * later: a timer, a work queue, call_rcu.
> + */
> +static bool func_is_kept_for_later(struct bpf_verifier_env *env, int idx, int end)
> +{
> +	struct bpf_insn *insn = env->prog->insnsi;
> +	u8 class, reg = insn[idx].dst_reg;
> +	int i;
> +
> +	if (reg < BPF_REG_1 || reg > BPF_REG_5)
> +		return false;
> +	for (i = idx + 2; i < end; i++) {
> +		class = BPF_CLASS(insn[i].code);
> +		if (class == BPF_JMP || class == BPF_JMP32)
> +			return bpf_is_async_callback_calling_insn(&insn[i]);
> +		if (insn[i].dst_reg == reg)
> +			return false;
> +		if (bpf_is_ldimm64(&insn[i]))
> +			i++;
> +		else if (insn[i].src_reg == reg)
> +			return false;
> +	}
> +	return false;
> +}
> +
> +/*
> + * Find the subprogs on cycles of the call graph. It is not known yet what callx
> + * calls: it may be any subprog whose address is taken. A subprog that is
> + * marked for no reason is treated like a recursive one all the same.
> + */
> +static int mark_recursive_subprogs(struct bpf_verifier_env *env)
> +{
[ ... ]
> +				/*
> +				 * The helper that takes a callback calls it, or keeps it: the
> +				 * callback that arms itself again doesn't call itself.
> +				 */
> +				if (bpf_pseudo_call(&insn[i]) ||
> +				    !func_is_kept_for_later(env, i, si[s + 1].start))
> +					__set_bit(j, calls + s * words);

[Severity: Medium]
As reported by Sashiko on v2 [3], mark_recursive_subprogs() and
build_call_graph() use different criteria to decide whether a bpf_pseudo_func
instruction for an async callback forms a call edge:

1. In mark_recursive_subprogs(), func_is_kept_for_later() syntactically checks
whether bpf_pseudo_func loads into R1-R5 and reaches an async callback helper
or kfunc with no intervening jumps, calls, or register copies. If an async
callback registration in a live subprogram is on an untaken branch during
do_check_all(), func_is_kept_for_later() returns true (so si[j].recursive is
false), while push_callback_call() is never reached (so si[j].is_async_cb
remains false). When build_call_graph() later scans all instructions of
subprograms, it only skips bpf_pseudo_func when si[j].is_async_cb is set:

kernel/bpf/verifier.c:build_call_graph() {
	...
	if (si[j].is_async_cb && !bpf_pseudo_call(insn + i))
		continue;
	__set_bit(j, subprog_calls(cg, s));
}

If the callback re-arms itself, build_call_graph() adds the cycle to cg->live
and check_recursion() rejects the program because si[j].recursive was not set.

2. Conversely, if a live async callback that re-arms itself (directly or via a
helper subprog) loads its bpf_pseudo_func address into a callee-saved
register, copies the register, or has an intervening branch or call before the
async callback helper, func_is_kept_for_later() returns false and
mark_recursive_subprogs() marks the subprogs on the cycle as recursive = true
before the main pass. Even though si[j].is_async_cb becomes true during the
main pass, the premature recursive mark causes false rejections in
mark_recursive_subprogs() (for BPF_PROG_TYPE_EXT), in analyze_subprog() (when
passing stack pointers between the subprogs), and in check_recursion_guard()
(which injects a synthetic R0 = 0 early exit at subprog entry).

Can mark_recursive_subprogs() and build_call_graph() use a consistent analysis
for async callbacks so valid programs with timers, workqueues, or RCU
callbacks are not rejected?

[ ... ]
> @@ -22021,6 +22207,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]
As reported by Sashiko on v2 [4], in bpf_insert_recursion_checks(), the
runtime recursion check is inserted before si[s].start via
bpf_patch_list_insert(), so only calls enter the check while intra-subprogram
jumps to si[s].start land after the check.

However, in do_check_block(), check_recursion_guard() calls push_budget_exit()
every time env->insn_idx == sub->start, without checking whether the state
just entered the subprogram or arrived via an intra-subprogram loop back-edge
to sub->start.

If a recursive subprogram has a loop header at sub->start and holds a
reference, spinlock, RCU lock, or IRQ state across the back-edge to sub->start
that is released later in the loop or after the loop exits, won't
check_recursion_guard() push a spurious exit branch with those resources still
held and cause verification to fail?

[1] https://lore.kernel.org/r/b77dd21709ea9d7691f0ffeb58635a660aef73738c24b1c059a01a1da42d5af4@mail.kernel.org
[2] https://lore.kernel.org/r/20261105204513.2230344-23-alexei.starovoitov@gmail.com
[3] https://lore.kernel.org/r/20261105204513.2230344-23-alexei.starovoitov@gmail.com
[4] https://lore.kernel.org/r/20261105204513.2230344-23-alexei.starovoitov@gmail.com

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