Re: [PATCH bpf-next] bpf: Don't re-sort subprog_info[] for every new subprogram

[Mahe Tardy <mahe.tardy@gmail.com>]

On Fri, Oct 23, 2026 at 03:03:02PM +0000, Alexei Starovoitov wrote:
> From: Alexei Starovoitov <ast@kernel.org>
> 
> add_subprog() appends new subprog to env->subprog_info[] and calls sort()
> on the whole array, though only the last entry can be out of order.
> Move subprogs that start after the new one up by one entry instead.
> 'start' is unique, so the order of the array doesn't change. The new entry
> can land in a used slot, so initialize all of it.
> 
> add_subprog() returns the index of the new subprog instead of the last
> one. The callers check for error only.
> 
> It's a trivial prep for rust-bpf [1] that bumps BPF_MAX_SUBPROGS to 1024.
> Rust crates have more than 256 functions that are not inlined.
> 
> Time in add_subprogs() when veristat loads sched_ext schedulers from scx
> repo, 8 cpu VM, usec:
> 
>                  subprogs  before  after
>  arena_selftest       101     386     27
>  lavd_enqueue          52      96     16
>  lavd_dispatch         48      78     11
> 
> [1] https://github.com/4ast/rust-bpf
> 
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>

Reviewed-by: Mahe Tardy <mahe.tardy@gmail.com>

Looks good, why not take advantage from the sorted array! (I know it's
kinda trivial but trying to review the small patches around here.)

> ---
>  kernel/bpf/verifier.c | 29 +++++++++++++----------------
>  1 file changed, 13 insertions(+), 16 deletions(-)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 5601d2056218..676566f80d97 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -2605,12 +2605,6 @@ static struct bpf_verifier_state *push_async_cb(struct bpf_verifier_env *env,
>  	return &elem->st;
>  }
>  
> -static int cmp_subprogs(const void *a, const void *b)
> -{
> -	return ((struct bpf_subprog_info *)a)->start -
> -	       ((struct bpf_subprog_info *)b)->start;
> -}
> -
>  /* Find subprogram that contains instruction at 'off' */
>  struct bpf_subprog_info *bpf_find_containing_subprog(struct bpf_verifier_env *env, int off)
>  {
> @@ -2645,26 +2639,29 @@ int bpf_find_subprog(struct bpf_verifier_env *env, int off)
>  
>  static int add_subprog(struct bpf_verifier_env *env, int off)
>  {
> +	struct bpf_subprog_info *subprog = env->subprog_info;
>  	int insn_cnt = env->prog->len;
> -	int ret;
> +	int i;
>  
>  	if (off >= insn_cnt || off < 0) {
>  		verbose(env, "call to invalid destination\n");
>  		return -EINVAL;
>  	}
> -	ret = bpf_find_subprog(env, off);
> -	if (ret >= 0)
> -		return ret;
> +	i = bpf_find_subprog(env, off);
> +	if (i >= 0)
> +		return i;
>  	if (env->subprog_cnt >= BPF_MAX_SUBPROGS) {
>  		verbose(env, "too many subprograms\n");
>  		return -E2BIG;
>  	}
> -	/* determine subprog starts. The end is one before the next starts */
> -	env->subprog_info[env->subprog_cnt].exit_idx = U32_MAX;
> -	env->subprog_info[env->subprog_cnt++].start = off;
> -	sort(env->subprog_info, env->subprog_cnt,
> -	     sizeof(env->subprog_info[0]), cmp_subprogs, NULL);
> -	return env->subprog_cnt - 1;
> +	/*
> +	 * Determine subprog starts. The end is one before the next starts.
> +	 * The array stays sorted: subprogs that start after 'off' move up.
> +	 */
> +	for (i = env->subprog_cnt++; i > 0 && subprog[i - 1].start > off; i--)
> +		subprog[i] = subprog[i - 1];
> +	subprog[i] = (struct bpf_subprog_info){ .start = off, .exit_idx = U32_MAX };
> +	return i;
>  }
>  
>  static int bpf_find_exception_callback_insn_off(struct bpf_verifier_env *env)
> 
> base-commit: b116ac6087541d3d98031e786adbe9c733cd6df3
> -- 
> 2.55.0