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

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

[Alexei Starovoitov]

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>
---
 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

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

[Mahe Tardy]

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

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

[patchwork-bot+netdevbpf]

Hello:

This patch was applied to bpf/bpf.git (master)
by Alexei Starovoitov <ast@kernel.org>:

On Fri, 23 Oct 2026 15:03:02 +0000 you 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.
> 
> [...]

Here is the summary with links:
  - [bpf-next] bpf: Don't re-sort subprog_info[] for every new subprogram
    https://git.kernel.org/bpf/bpf/c/c8a8a68d3ab4

You are awesome, thank you!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html