From: sashiko-bot@kernel.org
To: "Alexei Starovoitov" <alexei.starovoitov@gmail.com>, bpf@vger.kernel.org
Subject: Re: [PATCH bpf-next 13/21] bpf: Keep the call graph in lists of edges
Date: Mon, 16 Nov 2026 06:39:59 +0000 [thread overview]
Message-ID: <sashiko-outbox-216293@kernel.org> (raw)
In-Reply-To: <20261116055638.4171529-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()
It also noticed 1 related pre-existing issue this patch does not
introduce:
- [Critical] bpf: tail call kernel stack overflow in
check_max_stack_depth_subprog() [1]
--
commit 05343e493dd94aadf6b39ccc572d2107a34ec086
Author: Alexei Starovoitov <ast@kernel.org>
bpf: Keep the call graph in lists of edges
This commit replaces the bitmap-based call graph representation with edge
lists sorted via Tarjan's algorithm, and ignores unseen instructions in
dead code when building the post-verification call graph and subprogram
properties.
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index e29eb7d7162b6..35b94ab7ba97f 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
[ ... ]
> @@ -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 dead
subprograms?
Before the main pass, mark_recursive_subprogs() sets si[s].recursive = true
using a conservative call graph built from all instructions, including dead
calls and every addr_taken subprogram when callx is present. After this
change, build_call_graph() only adds seen call edges and recorded
callx_edges, so a subprogram that was conservatively marked recursive may
no longer be marked CG_LIVE.
Because check_recursion() only iterates over CG_LIVE subprograms,
si[s].recursive stays true on non-live subprograms.
bpf_insert_recursion_checks() runs before bpf_opt_remove_dead_code() and
scans all subprograms, so a stale recursive flag sets
env->prog->jit_required = 1 and causes bpf_do_misc_fixups() to reject valid
non-JITed programs with -EINVAL.
[ ... ]
> @@ -5924,7 +5809,7 @@ static int check_call_depth(struct bpf_verifier_env *env, struct bpf_call_graph
> */
> depth = dinfo[s].depth;
> /* nor of the frames of recursive subprogs, see bpf_insert_recursion_checks() */
> - si[s].in_recursion = test_bit(s, cg->in_recursion);
> + si[s].in_recursion = cg->marks[s] & CG_IN_RECURSION;
> if (si[s].in_recursion)
> depth += THREAD_SIZE / 2;
> if (s && si[s].has_tail_call && depth >= 256) {
[Severity: Critical]
This problem wasn't introduced by this patch, but can the 256-byte caller
frame limit for tail calls in check_call_depth() overflow the x86-64
exception stack [1]?
Across a chain of 32 tail calls, allowing up to 256 bytes of caller frames
to remain on the stack per tail call accumulates up to 7936 bytes, and the
final program can still use a 512-byte frame (MAX_BPF_STACK) for a total of
8448 bytes. Because tail calls disable the private stack, a perf_event
program running in NMI context on x86-64 without KASAN executes on the
8192-byte hardware exception stack (EXCEPTION_STKSZ) and overflows it.
[1] https://sashiko.dev/#/bug/linux-d03fddb6-2a86-4813-a8c6-9b07915dc3d1
--
Sashiko AI review · https://sashiko.dev/#/patchset/20261116055638.4171529-1-alexei.starovoitov@gmail.com?part=13
next prev parent reply other threads:[~2026-11-16 6:40 UTC|newest]
Thread overview: 36+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-11-16 5:56 [PATCH bpf-next 00/21] bpf: Remove the limits on maps, kfuncs, subprogs and special fields Alexei Starovoitov
2026-11-16 5:56 ` [PATCH bpf-next 01/21] bpf: Stop a load only when the loader is killed or has to freeze Alexei Starovoitov
2026-11-16 6:39 ` bot+bpf-ci
2026-11-16 6:49 ` sashiko-bot
2026-11-16 5:56 ` [PATCH bpf-next 02/21] bpf: Fail the load when there is no memory Alexei Starovoitov
2026-11-16 6:29 ` sashiko-bot
2026-11-16 5:56 ` [PATCH bpf-next 03/21] bpf: Give a syscall program the largest context when it does tail calls Alexei Starovoitov
2026-11-16 5:56 ` [PATCH bpf-next 04/21] bpf: Do not inline bpf_loop() when its callback is dead code Alexei Starovoitov
2026-11-16 5:56 ` [PATCH bpf-next 05/21] bpf: Dump programs that have more than 524288 insns Alexei Starovoitov
2026-11-16 5:56 ` [PATCH bpf-next 06/21] bpf: Resolve BTF structs and arrays first Alexei Starovoitov
2026-11-16 6:13 ` sashiko-bot
2026-11-16 5:56 ` [PATCH bpf-next 07/21] bpf: Remove the limits on maps, BTFs and fd_array of a program Alexei Starovoitov
2026-11-16 6:39 ` bot+bpf-ci
2026-11-16 5:56 ` [PATCH bpf-next 08/21] bpf: Do not scan all maps for each insn and each subprog Alexei Starovoitov
2026-11-16 6:16 ` sashiko-bot
2026-11-16 5:56 ` [PATCH bpf-next 09/21] bpf: Remove the limits on kfuncs of a program Alexei Starovoitov
2026-11-16 6:39 ` bot+bpf-ci
2026-11-16 5:56 ` [PATCH bpf-next 10/21] bpf: Remove the limits on tables of functions Alexei Starovoitov
2026-11-16 6:14 ` sashiko-bot
2026-11-16 5:56 ` [PATCH bpf-next 11/21] libbpf: Size the tables of the loader program from the object Alexei Starovoitov
2026-11-16 6:20 ` sashiko-bot
2026-11-16 5:56 ` [PATCH bpf-next 12/21] bpf: Relax jumps that patches push out of range Alexei Starovoitov
2026-11-16 6:52 ` bot+bpf-ci
2026-11-16 5:56 ` [PATCH bpf-next 13/21] bpf: Keep the call graph in lists of edges Alexei Starovoitov
2026-11-16 6:39 ` sashiko-bot [this message]
2026-11-16 5:56 ` [PATCH bpf-next 14/21] bpf: Find the effects of callees on the call graph Alexei Starovoitov
2026-11-16 5:56 ` [PATCH bpf-next 15/21] bpf: Link the decl tags of a type Alexei Starovoitov
2026-11-16 5:56 ` [PATCH bpf-next 16/21] bpf: Remove BPF_MAX_SUBPROGS Alexei Starovoitov
2026-11-16 5:56 ` [PATCH bpf-next 17/21] bpf: Walk each type once when looking for special fields Alexei Starovoitov
2026-11-16 5:56 ` [PATCH bpf-next 18/21] bpf: Raise the limit on the length of BTF names Alexei Starovoitov
2026-11-16 5:56 ` [PATCH bpf-next 19/21] bpf: Find dominators in O(n log n) Alexei Starovoitov
2026-11-16 5:56 ` [PATCH bpf-next 20/21] selftests/bpf: Test programs above the old limits Alexei Starovoitov
2026-11-16 6:33 ` sashiko-bot
2026-11-16 6:39 ` bot+bpf-ci
2026-11-16 5:56 ` [PATCH bpf-next 21/21] selftests/bpf: Test limits of the load with raw programs Alexei Starovoitov
2026-11-16 6:39 ` sashiko-bot
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-216293@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