From: sashiko-bot@kernel.org
To: "Alexei Starovoitov" <alexei.starovoitov@gmail.com>, bpf@vger.kernel.org
Subject: Re: [PATCH bpf-next 04/49] bpf: Delete scalar evolution
Date: Fri, 20 Nov 2026 08:03:59 +0000 [thread overview]
Message-ID: <sashiko-outbox-224677@kernel.org> (raw)
In-Reply-To: <20261120074430.2704488-5-alexei.starovoitov@gmail.com>
Thank you for your contribution! Sashiko AI review found 1 potential
issue to consider:
- [High] bpf: call to undeclared bpf_add_cost() and BPF_COST_SCAN in
find_latch()
--
commit e5e45ce256ee98d6b03c38ed44f64ae0c972a296
Author: Alexei Starovoitov <ast@kernel.org>
bpf: Delete scalar evolution
This commit removes the scalar evolution pre-pass (scev.c), its callers,
and helpers that were only used by it, and simplifies loop exit and latch
tracking to record only the first exit target and latch.
> diff --git a/kernel/bpf/loops.c b/kernel/bpf/loops.c
> index 1101976850515..8a63bb1799a78 100644
> --- a/kernel/bpf/loops.c
> +++ b/kernel/bpf/loops.c
[ ... ]
> @@ -340,100 +291,23 @@ int bpf_loop_at_index(struct bpf_verifier_env *env, u32 idx)
> }
>
> /*
> - * Collect conditional jumps within n's loop that dominate 'n' and leave
> - * the loop on one edge, see bpf_edge_leaves_loop(), nearest first.
> - * A jump that cannot count the iterations takes no place, see bpf_scev_jump_counts().
> + * The backedge->from and its latch can reside in an inner loop of @h, e.g.:
> + *
> + * 1: r7 += 1;
> + * 2: r6 += 1;
> + * if r7 == 2 goto 1b;
> + * if r6 < 2 goto 2b;
> + *
> + * For now, let's assume that latches are unknown for such cases.
> + * (GCC/LLVM handle this by inserting artificial cfg nodes).
> */
> -static int find_dominating_conditions(struct bpf_verifier_env *env, int n,
> - struct bpf_backedge *backedge)
> +static int find_latch(struct bpf_verifier_env *env, int h, int n)
> {
> - struct bpf_insn *insns = env->prog->insnsi;
> - bool t_exits_loop, f_exits_loop;
> - int *idoms = env->idoms;
> - int n_loop, counts;
> -
> - n_loop = bpf_loop_at_index(env, n);
> - if (idoms_intersect(env, n, n_loop) != n_loop)
> - return 0;
> - while (n >= 0) {
> - if (is_cond_jmp_insn(&insns[n]) && bpf_loop_at_index(env, n) == n_loop) {
> - t_exits_loop = bpf_edge_leaves_loop(env, n_loop, n, n + insns[n].off + 1);
> - f_exits_loop = bpf_edge_leaves_loop(env, n_loop, n, n + 1);
> - /* latches[0] is the latch: it has to leave the loop itself */
> - if ((t_exits_loop || f_exits_loop) &&
> - (backedge->latches_cnt || bpf_jump_leaves_loop(env, n_loop, n))) {
> - counts = !backedge->latches_cnt ? 1 :
> - bpf_scev_jump_counts(env, n_loop, n, t_exits_loop);
> - if (counts < 0)
> - return counts;
> - if (!counts)
> - goto next;
> - if (backedge->latches_cnt == MAX_LATCHES)
> - return 0;
> - if (t_exits_loop)
> - backedge->taken_leaves |= BIT(backedge->latches_cnt);
> - backedge->latches[backedge->latches_cnt++] = n;
> - }
> - }
> -next:
> - if (n == n_loop)
> - break;
> - n = idoms[n];
> - }
> - return 0;
> -}
> -
> -/*
> - * Without @flags: the jumps that leave a loop themselves. That tells where the verifier may add
> - * may_goto. It takes the constants that hold with these edges to follow a flag.
> - * Once more after scalar evolution, which knows the jumps that count. The flags that were found
> - * are remembered.
> - */
> -int bpf_find_latches(struct bpf_verifier_env *env, bool flags)
> -{
> - struct bpf_insn_aux_data *aux = env->insn_aux_data;
> - struct bpf_backedge *backedge;
> - struct bpf_loop *loop;
> - int i, j, k, err;
> -
> - if (flags) {
> - err = bpf_compute_leave_conds(env);
> - if (err)
> - return err;
> - }
> - for (i = 0; i < env->prog->len; i++) {
> - loop = aux[i].loop;
> - if (!loop)
> - continue;
> - for (j = 0; j < loop->backedges_cnt; j++) {
> - backedge = &loop->backedges[j];
> - backedge->latches_cnt = 0;
> - backedge->taken_leaves = 0;
> - /*
> - * In theory, the backedge->from and it's latch can reside in
> - * an inner loop of `i`, e.g.:
> - *
> - * 1: r7 += 1;
> - * 2: r6 += 1;
> - * if r7 == 2 goto 1b;
> - * if r6 < 2 goto 2b;
> - *
> - * For now, let's assume that latches are unknown for such cases.
> - * (GCC/LLVM handle this by inserting artificial cfg nodes).
> - */
> - if (bpf_loop_at_index(env, backedge->from) != i)
> - continue;
> - err = find_dominating_conditions(env, backedge->from, backedge);
> - if (err)
> - return err;
> - for (k = 1; flags && k < backedge->latches_cnt; k++)
> - if ((env->log.level & BPF_LOG_LEVEL2) &&
> - !bpf_jump_leaves_loop(env, i, backedge->latches[k]))
> - bpf_log(&env->log, "loop at %d, exit by way of a flag at %d\n",
> - i, backedge->latches[k]);
> - }
> - }
> - return 0;
> + if (bpf_loop_at_index(env, n) != h || idoms_intersect(env, n, h) != h)
> + return -1;
> + for (; n >= 0 && !bpf_insn_leaves_loop(env, h, n); n = n == h ? -1 : env->idoms[n])
> + bpf_add_cost(env, 1, BPF_COST_SCAN);
> + return n;
> }
[Severity: High]
Does find_latch() break the build at this commit by calling bpf_add_cost()
with BPF_COST_SCAN before they are defined? Those symbols are only
introduced in the following patch in the series, commit "bpf: Limit the
cost and the memory of a load", so kernel/bpf/loops.o fails to compile
with CONFIG_BPF_SYSCALL=y here, breaking bisection.
--
Sashiko AI review · https://sashiko.dev/#/patchset/20261120074430.2704488-1-alexei.starovoitov@gmail.com?part=4
next prev parent reply other threads:[~2026-11-20 8:04 UTC|newest]
Thread overview: 53+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-11-20 7:41 [PATCH bpf-next 00/49] bpf: Verify in passes, with equations in the state Alexei Starovoitov
2026-11-20 7:41 ` [PATCH bpf-next 01/49] bpf: Look for bpf_clone_redirect() once in check_recursion() Alexei Starovoitov
2026-11-20 7:41 ` [PATCH bpf-next 02/49] bpf: Make stack liveness faster Alexei Starovoitov
2026-11-20 8:01 ` sashiko-bot
2026-11-20 7:41 ` [PATCH bpf-next 03/49] bpf: Delete the old main pass of the verifier Alexei Starovoitov
2026-11-20 7:41 ` [PATCH bpf-next 04/49] bpf: Delete scalar evolution Alexei Starovoitov
2026-11-20 8:03 ` sashiko-bot [this message]
2026-11-20 7:41 ` [PATCH bpf-next 05/49] bpf: Limit the cost and the memory of a load Alexei Starovoitov
2026-11-20 8:00 ` sashiko-bot
2026-11-20 7:41 ` [PATCH bpf-next 06/49] bpf: Record what each insn reads and writes Alexei Starovoitov
2026-11-20 7:41 ` [PATCH bpf-next 07/49] bpf: Name an id after the xreg that has it Alexei Starovoitov
2026-11-20 7:41 ` [PATCH bpf-next 08/49] bpf: Do not fail a check because a state has fewer values Alexei Starovoitov
2026-11-20 7:41 ` [PATCH bpf-next 09/49] bpf: Check fixups in the main pass and keep a snapshot of them Alexei Starovoitov
2026-11-20 7:41 ` [PATCH bpf-next 10/49] bpf: Reject a program with a call that needs two rewrites Alexei Starovoitov
2026-11-20 7:41 ` [PATCH bpf-next 11/49] bpf: Put a barrier where no mask fits Alexei Starovoitov
2026-11-20 7:41 ` [PATCH bpf-next 12/49] bpf: Keep more of what is known about a number Alexei Starovoitov
2026-11-20 7:41 ` [PATCH bpf-next 13/49] bpf: Remember how many bytes of a packet are checked Alexei Starovoitov
2026-11-20 7:41 ` [PATCH bpf-next 14/49] bpf: Mark a state that no run of the program has Alexei Starovoitov
2026-11-20 7:41 ` [PATCH bpf-next 15/49] bpf: Peel the first trips of a loop and join the other trips Alexei Starovoitov
2026-11-20 7:41 ` [PATCH bpf-next 16/49] bpf: Add equations and their arithmetic Alexei Starovoitov
2026-11-20 7:41 ` [PATCH bpf-next 17/49] bpf: Keep a table of equations in each state Alexei Starovoitov
2026-11-20 7:41 ` [PATCH bpf-next 18/49] bpf: Refine all related numbers after a jump Alexei Starovoitov
2026-11-20 7:41 ` [PATCH bpf-next 19/49] bpf: Make equations from ALU, spill, fill and call insns Alexei Starovoitov
2026-11-20 7:41 ` [PATCH bpf-next 20/49] bpf: Delete the equations that say nothing Alexei Starovoitov
2026-11-20 7:41 ` [PATCH bpf-next 21/49] bpf: Compare states by join_key, then by value Alexei Starovoitov
2026-11-20 7:41 ` [PATCH bpf-next 22/49] bpf: Continue a pass after an unproven insn Alexei Starovoitov
2026-11-20 7:41 ` [PATCH bpf-next 23/49] bpf: Find the xregs that an unproven insn depends on Alexei Starovoitov
2026-11-20 7:41 ` [PATCH bpf-next 24/49] bpf: Keep two states apart if data and control deps differ Alexei Starovoitov
2026-11-20 7:41 ` [PATCH bpf-next 25/49] bpf: Join any two states that have the same join_key Alexei Starovoitov
2026-11-20 7:41 ` [PATCH bpf-next 26/49] bpf: Check the equations when a state is pruned or joined Alexei Starovoitov
2026-11-20 7:41 ` [PATCH bpf-next 27/49] bpf: Guess the equations of a join Alexei Starovoitov
2026-11-20 7:42 ` [PATCH bpf-next 28/49] bpf: Prune or join each state that arrives Alexei Starovoitov
2026-11-20 7:42 ` [PATCH bpf-next 29/49] bpf: Order the pending states and free the states that are done Alexei Starovoitov
2026-11-20 7:42 ` [PATCH bpf-next 30/49] bpf: Get the trip count from the trip index Alexei Starovoitov
2026-11-20 7:42 ` [PATCH bpf-next 31/49] bpf: Give a loop a checked trip count or may_goto Alexei Starovoitov
2026-11-20 7:42 ` [PATCH bpf-next 32/49] bpf: Use the equations in the join rule Alexei Starovoitov
2026-11-20 7:42 ` [PATCH bpf-next 33/49] bpf: Verify a static function once for each instance Alexei Starovoitov
2026-11-20 7:42 ` [PATCH bpf-next 34/49] bpf: Partition the states after an error Alexei Starovoitov
2026-11-20 7:42 ` [PATCH bpf-next 35/49] bpf: Reproduce an error on one path, with no joins Alexei Starovoitov
2026-11-20 7:42 ` [PATCH bpf-next 36/49] bpf: Do not let a join raise what a program requires Alexei Starovoitov
2026-11-20 7:42 ` [PATCH bpf-next 37/49] bpf: Verify in passes Alexei Starovoitov
2026-11-20 7:42 ` [PATCH bpf-next 38/49] bpf: Make a returned pointer to the stack unreadable Alexei Starovoitov
2026-11-20 7:42 ` [PATCH bpf-next 39/49] bpf: Keep two states apart if a live xreg has two types Alexei Starovoitov
2026-11-20 7:42 ` [PATCH bpf-next 40/49] bpf: Check the body of a counted loop once Alexei Starovoitov
2026-11-20 7:42 ` [PATCH bpf-next 41/49] bpf: Refine the copies of a number that AND or OR splits Alexei Starovoitov
2026-11-20 7:42 ` [PATCH bpf-next 42/49] bpf: Allow a range of offsets for a constant string Alexei Starovoitov
2026-11-20 7:42 ` [PATCH bpf-next 43/49] bpf: Keep spilled pointers at a range of stack offsets Alexei Starovoitov
2026-11-20 7:42 ` [PATCH bpf-next 44/49] selftests/bpf: Adjust tests to the new log text Alexei Starovoitov
2026-11-20 7:42 ` [PATCH bpf-next 45/49] selftests/bpf: Adjust tests that get another verdict or may_goto Alexei Starovoitov
2026-11-20 7:42 ` [PATCH bpf-next 46/49] selftests/bpf: Test barriers and far pointers Alexei Starovoitov
2026-11-20 7:42 ` [PATCH bpf-next 47/49] selftests/bpf: Test passes, instances, precision and the failing path Alexei Starovoitov
2026-11-20 7:42 ` [PATCH bpf-next 48/49] selftests/bpf: Test equations Alexei Starovoitov
2026-11-20 7:42 ` [PATCH bpf-next 49/49] bpf, docs: Rewrite verifier.rst 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=sashiko-outbox-224677@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