BPF List
 help / color / mirror / Atom feed
From: sashiko-bot@kernel.org
To: "Alexei Starovoitov" <alexei.starovoitov@gmail.com>, bpf@vger.kernel.org
Subject: Re: [PATCH bpf-next v2 13/21] bpf: Keep the call graph in lists of edges
Date: Mon, 16 Nov 2026 19:21:20 +0000	[thread overview]
Message-ID: <sashiko-outbox-217549@kernel.org> (raw)
In-Reply-To: <20261116152626.4032587-14-alexei.starovoitov@gmail.com>

Thank you for your contribution! Sashiko AI review found 1 potential
issue to consider:
- [Medium] bpf: stale recursive flag on dead subprogs in
  check_recursion()
--

commit 539e11dd4eb699b7232e8c0101b8c5c17216cd6e
Author: Alexei Starovoitov <ast@kernel.org>

bpf: Keep the call graph in lists of edges

This commit replaces the bitmap-based call graph with edge lists sorted via
Tarjan's algorithm and restricts post-verification call graph analysis to
instructions seen during the main pass.

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index c5a44c887adaa..5fe15a4b3bd8e 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
[ ... ]
> @@ -5447,122 +5385,75 @@ static int round_up_stack_depth(struct bpf_verifier_env *env, int stack_depth)
[ ... ]
>  static int build_call_graph(struct bpf_verifier_env *env, struct bpf_call_graph *cg)
>  {
>  	struct bpf_subprog_info *si = env->subprog_info;
>  	struct bpf_insn *insn = env->prog->insnsi;
> -	int cnt = env->subprog_cnt, words = BITS_TO_LONGS(cnt);
> -	int i, j, s;
[ ... ]
> +	err = bpf_call_graph_init(cg, cnt);
>  	for (s = 0; s < cnt; s++) {
> -		for (i = si[s].start; i < si[s + 1].start; i++) {
> -			/* the subprog that takes the address of a subprog counts as its caller */
> -			if (!bpf_pseudo_call(insn + i) && !bpf_pseudo_func(insn + i))
> -				continue;
[ ... ]
> -		}
> -		/* the callees of callx and the callbacks of helpers, see record_callx_edge() */
> -		for (j = next_callx_callee(env, s, 0); j >= 0; j = next_callx_callee(env, s, j + 1))
> -			__set_bit(j, subprog_calls(cg, s));
> +		for (i = si[s].start; i < si[s + 1].start && !err; i++)
> +			if (bpf_pseudo_call(insn + i) && env->insn_aux_data[i].seen)
> +				err = bpf_call_graph_add(cg, s, bpf_find_subprog(env,
> +							 i + insn[i].imm + 1));
> +		/* the callees of callx and the callbacks of helpers */
> +		for (i = si[s].callx_edge; i && !err; i = env->callx_edges[i - 1].next)
> +			err = bpf_call_graph_add(cg, s, env->callx_edges[i - 1].callee);
>  	}
> -	memcpy(cg->reach, cg->calls, cnt * words * sizeof(long));
> -	close_call_graph(cg->reach, cnt);
> +	if (err)
> +		return err;
> +	bpf_call_graph_sort(cg, 0);
>  
>  	for (s = 0; s < cnt; s++)
>  		if (!s || si[s].is_async_cb)
> -			add_reach(cg, cg->live, s);
> +			cg->marks[s] = CG_LIVE;
> +	bpf_call_graph_mark_callees(cg, CG_LIVE);
[ ... ]
> @@ -5611,8 +5498,8 @@ static int check_recursion(struct bpf_verifier_env *env, struct bpf_call_graph *
>  {
>  	int j, s;
>  
> -	for_each_set_bit(s, cg->live, cg->cnt) {
> -		if (!test_bit(s, subprog_reach(cg, s))) {
> +	for_each_marked_subprog(cg, s, CG_LIVE) {
> +		if (!bpf_call_graph_recursive(cg, s)) {
>  			env->subprog_info[s].recursive = false;
>  			continue;
>  		}

[Severity: Medium]
Does check_recursion() leave env->subprog_info[s].recursive set on
subprogs that are not marked CG_LIVE?

Before the main pass, mark_recursive_subprogs() builds a conservative call
graph over all instructions and sets si[s].recursive = true for every
subprog on a cycle.  After the main pass, build_call_graph() ignores unseen
bpf_pseudo_call instructions and bpf_pseudo_func address loads, so a
subprog reachable only from a dead call or an uncalled address load is no
longer marked CG_LIVE and check_recursion() skips it without clearing
env->subprog_info[s].recursive.

Later, bpf_insert_recursion_checks() runs before bpf_opt_remove_dead_code()
and inspects si[s].recursive across all subprogs regardless of CG_LIVE:

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;
	...
}

This patches recursion checks into the dead subprog and sets
prog->jit_required = 1, causing bpf_fixup_call_args() to reject valid
non-JITed programs with -EINVAL.

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

  reply	other threads:[~2026-11-16 19:21 UTC|newest]

Thread overview: 28+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2026-11-16 15:26 [PATCH bpf-next v2 00/21] bpf: Remove the limits on maps, kfuncs, subprogs and special fields Alexei Starovoitov
2026-11-16 15:26 ` [PATCH bpf-next v2 01/21] bpf: Stop a load only when the loader is killed or has to freeze Alexei Starovoitov
2026-11-16 16:15   ` sashiko-bot
2026-11-16 15:26 ` [PATCH bpf-next v2 02/21] bpf: Fail the load when there is no memory Alexei Starovoitov
2026-11-16 16:06   ` bot+bpf-ci
2026-11-16 15:26 ` [PATCH bpf-next v2 03/21] bpf: Give a syscall program the largest context when it does tail calls Alexei Starovoitov
2026-11-16 15:26 ` [PATCH bpf-next v2 04/21] bpf: Do not inline bpf_loop() when its callback is dead code Alexei Starovoitov
2026-11-16 15:26 ` [PATCH bpf-next v2 05/21] bpf: Dump programs that have more than 524288 insns Alexei Starovoitov
2026-11-16 15:26 ` [PATCH bpf-next v2 06/21] bpf: Resolve BTF structs and arrays first Alexei Starovoitov
2026-11-16 17:40   ` sashiko-bot
2026-11-16 15:26 ` [PATCH bpf-next v2 07/21] bpf: Remove the limits on maps, BTFs and fd_array of a program Alexei Starovoitov
2026-11-16 15:26 ` [PATCH bpf-next v2 08/21] bpf: Do not scan all maps for each insn and each subprog Alexei Starovoitov
2026-11-16 15:26 ` [PATCH bpf-next v2 09/21] bpf: Remove the limits on kfuncs of a program Alexei Starovoitov
2026-11-16 15:26 ` [PATCH bpf-next v2 10/21] bpf: Remove the limits on tables of functions Alexei Starovoitov
2026-11-16 15:26 ` [PATCH bpf-next v2 11/21] libbpf: Size the tables of the loader program from the object Alexei Starovoitov
2026-11-16 16:06   ` bot+bpf-ci
2026-11-16 15:26 ` [PATCH bpf-next v2 12/21] bpf: Relax jumps that patches push out of range Alexei Starovoitov
2026-11-16 15:26 ` [PATCH bpf-next v2 13/21] bpf: Keep the call graph in lists of edges Alexei Starovoitov
2026-11-16 19:21   ` sashiko-bot [this message]
2026-11-16 15:26 ` [PATCH bpf-next v2 14/21] bpf: Find the effects of callees on the call graph Alexei Starovoitov
2026-11-16 15:26 ` [PATCH bpf-next v2 15/21] bpf: Link the decl tags of a type Alexei Starovoitov
2026-11-16 15:26 ` [PATCH bpf-next v2 16/21] bpf: Remove BPF_MAX_SUBPROGS Alexei Starovoitov
2026-11-16 15:26 ` [PATCH bpf-next v2 17/21] bpf: Walk each type once when looking for special fields Alexei Starovoitov
2026-11-16 15:26 ` [PATCH bpf-next v2 18/21] bpf: Raise the limit on the length of BTF names Alexei Starovoitov
2026-11-16 15:26 ` [PATCH bpf-next v2 19/21] bpf: Find dominators in O(n log n) Alexei Starovoitov
2026-11-16 15:26 ` [PATCH bpf-next v2 20/21] selftests/bpf: Test programs above the old limits Alexei Starovoitov
2026-11-16 15:26 ` [PATCH bpf-next v2 21/21] selftests/bpf: Test limits of the load with raw programs Alexei Starovoitov
2026-11-16 19:00 ` [PATCH bpf-next v2 00/21] bpf: Remove the limits on maps, kfuncs, subprogs and special fields patchwork-bot+netdevbpf

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=sashiko-outbox-217549@kernel.org \
    --to=sashiko-bot@kernel.org \
    --cc=alexei.starovoitov@gmail.com \
    --cc=bpf@vger.kernel.org \
    --cc=sashiko-reviews@lists.linux.dev \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox