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
next prev parent reply other threads:[~2026-11-16 19:21 UTC|newest]
Thread overview: 29+ 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 21:17 ` sashiko-bot
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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.