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

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>
Link: https://patch.msgid.link/20261023150302.4097865-1-alexei.starovoitov@gmail.com

1 files changed, 13 insertions, 16 deletions

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 02b2915f0014..26a5ee0708a3 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2617,12 +2617,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)
 {
@@ -2657,26 +2651,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)