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 v2 33/49] bpf: Verify a static function once for each instance
Date: Sat, 21 Nov 2026 04:46:07 +0000	[thread overview]
Message-ID: <sashiko-outbox-226643@kernel.org> (raw)
In-Reply-To: <20261120204959.614908-34-alexei.starovoitov@gmail.com>

Thank you for your contribution! Sashiko AI review found 3 potential
issues to consider:
- [Medium] bpf: uncharged instance cost in flow_grow_instance() after
  first instance
- [Medium] bpf: missing FLOW_AGAIN kind on re-queued call state in
  flow_apply_exit()
- [Medium] bpf: missed non-NULL marking for returned parent_id in
  bpf_flow_return()
--

commit 086da59f5b2496a96c0c9a8141af31c675e376ed
Author: Alexei Starovoitov <ast@kernel.org>

bpf: Verify a static function once for each instance

This commit verifies static subprograms that do not depend on caller frames
once per instance, joining call states only at the subprogram entry point
and dividing a verification budget among functions with multiple instances.

> diff --git a/kernel/bpf/flow.c b/kernel/bpf/flow.c
> index c10fa54cdf91b..b5d65dd2d07a2 100644
> --- a/kernel/bpf/flow.c
> +++ b/kernel/bpf/flow.c
[ ... ]
> @@ -1345,6 +1358,301 @@ int bpf_flow_deliver(struct bpf_verifier_env *env, struct bpf_verifier_state *st
>  	return flow_add(env, s, false);
>  }
>  
> +/* @x is an exit state of the instance of the call @w. @w can leave the instance. */
> +static int flow_apply_exit(struct bpf_verifier_env *env, struct flow_state *w,
> +			   struct flow_state *x)
> +{
> +	int call_idx = w->st.insn_idx, err;
> +	struct bpf_verifier_state st = {};
> +
> +	err = bpf_copy_verifier_state(env, &st, &w->st) ?:
> +	      bpf_flow_return(env, &st, &x->st, call_idx);
> +	if (!err)
> +		err = bpf_flow_deliver(env, &st, call_idx + 1, call_idx, false);
> +	else if (err < 0 && st.speculative)
> +		err = min(bpf_flow_edge_unproven(env, &st, call_idx + 1, err), 0);
> +	else if (err < 0)
> +		err = min(bpf_flow_edge_unproven(env, &x->st, x->prev_insn_idx, err), 0);
> +	bpf_free_verifier_state(env, &st, false);
> +	if (err <= 0)
> +		return err;
> +
> +	/* The call is checked again in the frames of the caller */
> +	flow_unlink(env, w);
> +	flow_find(env, w);
> +	flow_link(env, w);
> +	return 0;
> +}

[Severity: Medium]
Should flow_apply_exit() set w->kind = FLOW_AGAIN before re-linking w, the
same way bpf_flow_deliver() does when again is true?

w was allocated with w->kind == FLOW_AT after passing pre-instruction join
and flow_keep() handling at call_idx, and after do_check_insn() mutated the
state for the call (such as check_func_callx_set() clearing reg->func_set
and setting reg->subprogno to one subprogram from the set).  When
bpf_flow_return() returns BPF_EXIT_NEEDS_CALLER and w is re-inserted into
state_tree as FLOW_AT at a join point, flow_prune_or_join() can join w with
other states at call_idx (clobbering a split callx target register to
NOT_INIT) and flow_keep() does not take its FLOW_AGAIN early return,
re-running flow_keep_peeled() if call_idx is a peeled loop header.

[ ... ]

> +/* @s gets to the first insn. @t is there and does not subsume @s. */
> +static int flow_grow_instance(struct bpf_verifier_env *env, struct flow_state *t,
> +			      struct flow_state *s, struct bpf_loop *leftover_loop)
> +{
> +	u64 args = flow_readable_args(t->st.frame[0]);
> +	struct flow_instance *old = t->started_instance, *instance = old;
> +	int err;
> +
> +	if (!old->entry_state) {
> +		instance = flow_new_instance(env, t);
> +		if (!instance)
> +			return -ENOMEM;
> +		instance->cost = old->cost;
> +	}

[Severity: Medium]
Does copying instance->cost = old->cost leave the new instance uncharged
when old is the first instance of the subprogram?

In bpf_flow_call(), the first instance is free, so (*cost)++ increments
env->flow->cost[subprog] from 0 to 1 while leaving
t->started_instance->cost as NULL.  When that first instance has already
started (!old->entry_state) and a later call grows it into a second
instance here, instance->cost is also set to NULL and budget_func_cnt is
not incremented, so bpf_flow_next() never charges the cost of the grown
instances to env->flow->cost[subprog] and flow_may_add_instance() never
throttles them.

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index fac44fceccfbf..58a483fed88be 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
[ ... ]
> @@ -11700,6 +11706,9 @@ int bpf_flow_return(struct bpf_verifier_env *env, struct bpf_verifier_state *cal
>  		reg->id = returned_id(reg->id);
>  		reg->parent_id = returned_id(reg->parent_id);
>  		reg->map_uid = returned_id(reg->map_uid);
> +		/* the function saw that a reference of the caller is not NULL */
> +		if (reg->id && !type_may_be_null(reg->type))
> +			mark_ptr_or_null_regs(caller, ret_regs[i], false);
>  	}
>  	return 0;
>  }

[Severity: Medium]
What if the callee checks a caller reference n for NULL and returns a
non-NULL child pointer derived from it, where reg->parent_id carries n's
reference ID and reg->id is 0?

For example, a recursive static subprogram verified on its own can take an
inherited PTR_MAYBE_NULL reference n, check if (!n) bpf_throw(), and return
a PTR_TRUSTED member loaded from n (which sets reg->parent_id to n's
reference ID in check_ptr_to_btf_access() while reg->id is 0).  Because
only reg->id is checked here, n in the caller keeps PTR_MAYBE_NULL; if the
caller then tests if (!n), mark_ptr_or_null_regs() drops n from
caller->refs[] via release_reference_nomark() without invalidating the
returned child register whose parent_id still refers to n.

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261120204959.614908-1-alexei.starovoitov@gmail.com?part=33

  reply	other threads:[~2026-11-21  4:46 UTC|newest]

Thread overview: 65+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2026-11-20 20:49 [PATCH bpf-next v2 00/49] bpf: Verify in passes, with equations in the state Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 01/49] bpf: Look for bpf_clone_redirect() once in check_recursion() Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 02/49] bpf: Make stack liveness faster Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 03/49] bpf: Delete the old main pass of the verifier Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 04/49] bpf: Delete scalar evolution Alexei Starovoitov
2026-11-20 21:51   ` bot+bpf-ci
2026-11-20 20:49 ` [PATCH bpf-next v2 05/49] bpf: Limit the cost and the memory of a load Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 06/49] bpf: Record what each insn reads and writes Alexei Starovoitov
2026-11-20 21:28   ` bot+bpf-ci
2026-11-20 20:49 ` [PATCH bpf-next v2 07/49] bpf: Name an id after the xreg that has it Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 08/49] bpf: Do not fail a check because a state has fewer values Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 09/49] bpf: Check fixups in the main pass and keep a snapshot of them Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 10/49] bpf: Reject a program with a call that needs two rewrites Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 11/49] bpf: Put a barrier where no mask fits Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 12/49] bpf: Keep more of what is known about a number Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 13/49] bpf: Remember how many bytes of a packet are checked Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 14/49] bpf: Mark a state that no run of the program has Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 15/49] bpf: Peel the first trips of a loop and join the other trips Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 16/49] bpf: Add equations and their arithmetic Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 17/49] bpf: Keep a table of equations in each state Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 18/49] bpf: Refine all related numbers after a jump Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 19/49] bpf: Make equations from ALU, spill, fill and call insns Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 20/49] bpf: Delete the equations that say nothing Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 21/49] bpf: Compare states by join_key, then by value Alexei Starovoitov
2026-11-20 21:51   ` bot+bpf-ci
2026-11-20 20:49 ` [PATCH bpf-next v2 22/49] bpf: Continue a pass after an unproven insn Alexei Starovoitov
2026-11-20 21:51   ` bot+bpf-ci
2026-11-20 20:49 ` [PATCH bpf-next v2 23/49] bpf: Find the xregs that an unproven insn depends on Alexei Starovoitov
2026-11-20 21:51   ` bot+bpf-ci
2026-11-20 20:49 ` [PATCH bpf-next v2 24/49] bpf: Keep two states apart if data and control deps differ Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 25/49] bpf: Join any two states that have the same join_key Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 26/49] bpf: Check the equations when a state is pruned or joined Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 27/49] bpf: Guess the equations of a join Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 28/49] bpf: Prune or join each state that arrives Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 29/49] bpf: Order the pending states and free the states that are done Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 30/49] bpf: Get the trip count from the trip index Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 31/49] bpf: Give a loop a checked trip count or may_goto Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 32/49] bpf: Use the equations in the join rule Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 33/49] bpf: Verify a static function once for each instance Alexei Starovoitov
2026-11-21  4:46   ` sashiko-bot [this message]
2026-11-20 20:49 ` [PATCH bpf-next v2 34/49] bpf: Partition the states after an error Alexei Starovoitov
2026-11-20 21:51   ` bot+bpf-ci
2026-11-20 20:49 ` [PATCH bpf-next v2 35/49] bpf: Reproduce an error on one path, with no joins Alexei Starovoitov
2026-11-20 21:51   ` bot+bpf-ci
2026-11-20 20:49 ` [PATCH bpf-next v2 36/49] bpf: Do not let a join raise what a program requires Alexei Starovoitov
2026-11-20 21:51   ` bot+bpf-ci
2026-11-20 20:49 ` [PATCH bpf-next v2 37/49] bpf: Verify in passes Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 38/49] bpf: Make a returned pointer to the stack unreadable Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 39/49] bpf: Keep two states apart if a live xreg has two types Alexei Starovoitov
2026-11-20 21:51   ` bot+bpf-ci
2026-11-20 20:49 ` [PATCH bpf-next v2 40/49] bpf: Check the body of a counted loop once Alexei Starovoitov
2026-11-20 21:51   ` bot+bpf-ci
2026-11-20 20:49 ` [PATCH bpf-next v2 41/49] bpf: Refine the copies of a number that AND or OR splits Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 42/49] bpf: Allow a range of offsets for a constant string Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 43/49] bpf: Keep spilled pointers at a range of stack offsets Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 44/49] selftests/bpf: Adjust tests to the new log text Alexei Starovoitov
2026-11-20 21:51   ` bot+bpf-ci
2026-11-20 20:49 ` [PATCH bpf-next v2 45/49] selftests/bpf: Adjust tests that get another verdict or may_goto Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 46/49] selftests/bpf: Test barriers and far pointers Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 47/49] selftests/bpf: Test passes, instances, precision and the failing path Alexei Starovoitov
2026-11-20 20:49 ` [PATCH bpf-next v2 48/49] selftests/bpf: Test equations Alexei Starovoitov
2026-11-20 21:51   ` bot+bpf-ci
2026-11-20 20:49 ` [PATCH bpf-next v2 49/49] bpf, docs: Rewrite verifier.rst Alexei Starovoitov
2026-11-20 21:28   ` bot+bpf-ci
2026-11-21  4:30 ` [PATCH bpf-next v2 00/49] bpf: Verify in passes, with equations in the state 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-226643@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.