From: "Alexei Starovoitov" <alexei.starovoitov@gmail.com>
To: <sashiko-reviews@lists.linux.dev>
Cc: <bpf@vger.kernel.org>
Subject: Re: [PATCH bpf-next 06/17] bpf: Add callx calls to the call graph
Date: Tue, 22 Sep 2026 02:54:33 +0000 [thread overview]
Message-ID: <DLLI8DZ44BSN.35MO12IZJET8H@gmail.com> (raw)
In-Reply-To: <20260922012711.C2F581F000FF@smtp.kernel.org>
On Tue, Sep 22, 2026 at 01:27 AM sashiko-bot@kernel.org <sashiko-bot@kernel.org> wrote:
>> + if (bpf_is_callx(insn + i)) {
>> + /*
>> + * Walk the callees recorded by the main verification
>> + * pass one by one, returning to this insn after each.
>> + */
>> + if (dinfo[idx].callx_insn != i) {
>> + dinfo[idx].callx_insn = i;
>> + dinfo[idx].callx_next = 0;
>> + }
>> + sidx = next_callx_callee(env, idx, dinfo[idx].callx_next);
>
> [Severity: High]
> Could this lead to a quadratic path explosion and unbounded CPU time in the
> verifier?
>
> The callx_edges bitmap appears to aggregate all distinct callees for an
> entire caller subprogram. If I am reading this correctly,
> check_max_stack_depth_subprog iterates over this entire aggregate bitmap
> for every single callx instruction in that subprogram.
>
> If a subprogram has K callx instructions and M distinct callees, would the
> verifier evaluate K * M edges here instead of just K edges? Across nested
> subprogram calls, it seems like this combinatorial amplification could
> evaluate paths exponentially. Since this pass lacks state pruning or
> complexity bounds, could this bypass the verifier complexity limits and hang
> the kernel thread?
Not a bug. K * M is intentional. The edges are recorded per caller,
not per insn.
next prev parent reply other threads:[~2026-09-22 2:54 UTC|newest]
Thread overview: 44+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-09-22 1:13 [PATCH bpf-next 00/17] bpf: Indirect calls of bpf subprogs (callx) Alexei Starovoitov
2026-09-22 1:13 ` [PATCH bpf-next 01/17] bpf: Fix infinite loop in check_max_stack_depth() Alexei Starovoitov
2026-09-22 2:01 ` bot+bpf-ci
2026-09-22 2:56 ` Alexei Starovoitov
2026-09-23 22:35 ` Eduard Zingerman
2026-09-22 1:13 ` [PATCH bpf-next 02/17] selftests/bpf: Test recursion through a global function and a callback Alexei Starovoitov
2026-09-22 1:13 ` [PATCH bpf-next 03/17] bpf: Don't fold loads from insn_array maps into constants Alexei Starovoitov
2026-09-23 22:39 ` Eduard Zingerman
2026-09-23 23:12 ` Alexei Starovoitov
2026-09-24 0:19 ` bot+bpf-ci
2026-09-22 1:13 ` [PATCH bpf-next 04/17] bpf: Prepare static analysis passes for callx instruction Alexei Starovoitov
2026-09-23 23:10 ` Eduard Zingerman
2026-09-23 23:51 ` Alexei Starovoitov
2026-09-22 1:13 ` [PATCH bpf-next 05/17] bpf: Add callx instruction to call bpf subprogs indirectly Alexei Starovoitov
2026-09-24 0:09 ` Eduard Zingerman
2026-09-22 1:13 ` [PATCH bpf-next 06/17] bpf: Add callx calls to the call graph Alexei Starovoitov
2026-09-22 1:27 ` sashiko-bot
2026-09-22 2:54 ` Alexei Starovoitov [this message]
2026-09-22 1:13 ` [PATCH bpf-next 07/17] bpf, x86: Add JIT support for callx Alexei Starovoitov
2026-09-22 1:27 ` sashiko-bot
2026-09-22 2:53 ` Alexei Starovoitov
2026-09-22 1:13 ` [PATCH bpf-next 08/17] bpf, arm64: " Alexei Starovoitov
2026-09-22 15:05 ` Puranjay Mohan
2026-09-22 1:13 ` [PATCH bpf-next 09/17] bpf: Discover subprogs described by func_info Alexei Starovoitov
2026-09-22 1:13 ` [PATCH bpf-next 10/17] bpf: Recognize pointers to functions in read-only maps Alexei Starovoitov
2026-09-22 1:31 ` sashiko-bot
2026-09-22 3:01 ` Alexei Starovoitov
2026-09-24 0:46 ` bot+bpf-ci
2026-09-24 2:12 ` Alexei Starovoitov
2026-09-22 1:13 ` [PATCH bpf-next 11/17] libbpf: Support pointers to static functions in data when linking Alexei Starovoitov
2026-09-22 1:13 ` [PATCH bpf-next 12/17] libbpf: Resolve pointers to functions in read-only data Alexei Starovoitov
2026-09-24 0:33 ` bot+bpf-ci
2026-09-24 2:13 ` Alexei Starovoitov
2026-09-22 1:13 ` [PATCH bpf-next 13/17] libbpf: Treat .data.rel.ro as " Alexei Starovoitov
2026-09-22 1:13 ` [PATCH bpf-next 14/17] libbpf: Support pointers to functions in read-only data in light skeleton Alexei Starovoitov
2026-09-22 2:01 ` bot+bpf-ci
2026-09-22 2:55 ` Alexei Starovoitov
2026-09-22 1:13 ` [PATCH bpf-next 15/17] selftests/bpf: Add tests for callx Alexei Starovoitov
2026-09-24 0:33 ` bot+bpf-ci
2026-09-24 2:13 ` Alexei Starovoitov
2026-09-22 1:13 ` [PATCH bpf-next 16/17] selftests/bpf: Add tests for callx through pointers in read-only data Alexei Starovoitov
2026-09-22 2:01 ` bot+bpf-ci
2026-09-24 0:33 ` bot+bpf-ci
2026-09-22 1:13 ` [PATCH bpf-next 17/17] bpf, docs: Document callx instruction Alexei Starovoitov
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=DLLI8DZ44BSN.35MO12IZJET8H@gmail.com \
--to=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.