All of lore.kernel.org
 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 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

  reply	other threads:[~2026-11-20  8:04 UTC|newest]

Thread overview: 83+ 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  8:24   ` bot+bpf-ci
2026-11-20  7:41 ` [PATCH bpf-next 03/49] bpf: Delete the old main pass of the verifier Alexei Starovoitov
2026-11-20  8:25   ` bot+bpf-ci
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  8:25   ` bot+bpf-ci
2026-11-20 17:50     ` Alexei Starovoitov
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 17:50     ` Alexei Starovoitov
2026-11-20  8:25   ` bot+bpf-ci
2026-11-20 17:51     ` Alexei Starovoitov
2026-11-20  7:41 ` [PATCH bpf-next 06/49] bpf: Record what each insn reads and writes Alexei Starovoitov
2026-11-20  8:25   ` bot+bpf-ci
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  8:25   ` bot+bpf-ci
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  8:25   ` bot+bpf-ci
2026-11-20  8:39   ` sashiko-bot
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  8:25   ` bot+bpf-ci
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  8:25   ` bot+bpf-ci
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  8:18   ` sashiko-bot
2026-11-20  8:25   ` bot+bpf-ci
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  8:25   ` bot+bpf-ci
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  8:24   ` bot+bpf-ci
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  8:25   ` bot+bpf-ci
2026-11-20  7:41 ` [PATCH bpf-next 16/49] bpf: Add equations and their arithmetic Alexei Starovoitov
2026-11-20  8:24   ` bot+bpf-ci
2026-11-20  7:41 ` [PATCH bpf-next 17/49] bpf: Keep a table of equations in each state Alexei Starovoitov
2026-11-20  8:17   ` sashiko-bot
2026-11-20  8:25   ` bot+bpf-ci
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  8:25   ` bot+bpf-ci
2026-11-20  8:26   ` sashiko-bot
2026-11-20  7:41 ` [PATCH bpf-next 20/49] bpf: Delete the equations that say nothing Alexei Starovoitov
2026-11-20  8:25   ` bot+bpf-ci
2026-11-20  7:41 ` [PATCH bpf-next 21/49] bpf: Compare states by join_key, then by value Alexei Starovoitov
2026-11-20  8:22   ` sashiko-bot
2026-11-20 17:52     ` 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  8:25   ` sashiko-bot
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  8:22   ` sashiko-bot
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  8:33   ` sashiko-bot
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  8:30   ` sashiko-bot
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 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.