The previous commit implemented BTF sorting verification and binary
search algorithm in libbpf. This patch enables this functionality in
the kernel.

Cc: Eduard Zingerman <eddyz87@gmail.com>
Cc: Alexei Starovoitov <ast@kernel.org>
Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
Cc: Alan Maguire <alan.maguire@oracle.com>
Cc: Song Liu <song@kernel.org>
Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
Signed-off-by: Donglin Peng <dolinux.peng@gmail.com>
---
v2->v3:
- Include btf_sort.c directly in btf.c to reduce function call overhead
---
 kernel/bpf/btf.c | 34 ++++++++++++++++++----------------
 1 file changed, 18 insertions(+), 16 deletions(-)

diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index 0de8fc8a0e0b..df258815a6ca 100644
--- a/kernel/bpf/btf.c
+++ b/kernel/bpf/btf.c
@@ -33,6 +33,7 @@
 #include <net/sock.h>
 #include <net/xdp.h>
 #include "../tools/lib/bpf/relo_core.h"
+#include "../tools/lib/bpf/btf_sort.h"
 
 /* BTF (BPF Type Format) is the meta data format which describes
  * the data types of BPF program/map.  Hence, it basically focus
@@ -259,6 +260,7 @@ struct btf {
 	void *nohdr_data;
 	struct btf_header hdr;
 	u32 nr_types; /* includes VOID for base BTF */
+	u32 nr_sorted_types; /* All named types in the sorted BTF instance */
 	u32 types_size;
 	u32 data_size;
 	refcount_t refcnt;
@@ -527,6 +529,11 @@ static bool btf_type_is_decl_tag_target(const struct btf_type *t)
 	       btf_type_is_var(t) || btf_type_is_typedef(t);
 }
 
+static u32 btf_start_id(const struct btf *btf)
+{
+	return btf->start_id + (btf->base_btf ? 0 : 1);
+}
+
 bool btf_is_vmlinux(const struct btf *btf)
 {
 	return btf->kernel_btf && !btf->base_btf;
@@ -546,22 +553,7 @@ u32 btf_nr_types(const struct btf *btf)
 
 s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind)
 {
-	const struct btf_type *t;
-	const char *tname;
-	u32 i, total;
-
-	total = btf_nr_types(btf);
-	for (i = 1; i < total; i++) {
-		t = btf_type_by_id(btf, i);
-		if (BTF_INFO_KIND(t->info) != kind)
-			continue;
-
-		tname = btf_name_by_offset(btf, t->name_off);
-		if (!strcmp(tname, name))
-			return i;
-	}
-
-	return -ENOENT;
+	return _btf_find_by_name_kind(btf, 1, name, kind);
 }
 
 s32 bpf_find_btf_id(const char *name, u32 kind, struct btf **btf_p)
@@ -6230,6 +6222,7 @@ static struct btf *btf_parse_base(struct btf_verifier_env *env, const char *name
 	if (err)
 		goto errout;
 
+	btf_check_sorted(btf, 1);
 	refcount_set(&btf->refcnt, 1);
 
 	return btf;
@@ -6362,6 +6355,7 @@ static struct btf *btf_parse_module(const char *module_name, const void *data,
 		base_btf = vmlinux_btf;
 	}
 
+	btf_check_sorted(btf, btf_nr_types(base_btf));
 	btf_verifier_env_free(env);
 	refcount_set(&btf->refcnt, 1);
 	return btf;
@@ -9577,3 +9571,11 @@ bool btf_param_match_suffix(const struct btf *btf,
 	param_name += len - suffix_len;
 	return !strncmp(param_name, suffix, suffix_len);
 }
+
+/*
+ * btf_sort.c is included directly to avoid function call overhead
+ * when accessing BTF private data, as this file is shared between
+ * libbpf and kernel and may be called frequently (especially when
+ * funcgraph-args or func-args tracing options are enabled).
+ */
+#include "../../tools/lib/bpf/btf_sort.c"
-- 
2.34.1

On Mon, Oct 27, 2025 at 6:54 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> The previous commit implemented BTF sorting verification and binary
> search algorithm in libbpf. This patch enables this functionality in
> the kernel.
>
> Cc: Eduard Zingerman <eddyz87@gmail.com>
> Cc: Alexei Starovoitov <ast@kernel.org>
> Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> Cc: Alan Maguire <alan.maguire@oracle.com>
> Cc: Song Liu <song@kernel.org>
> Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> Signed-off-by: Donglin Peng <dolinux.peng@gmail.com>
> ---
> v2->v3:
> - Include btf_sort.c directly in btf.c to reduce function call overhead
> ---
>  kernel/bpf/btf.c | 34 ++++++++++++++++++----------------
>  1 file changed, 18 insertions(+), 16 deletions(-)
>
> diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
> index 0de8fc8a0e0b..df258815a6ca 100644
> --- a/kernel/bpf/btf.c
> +++ b/kernel/bpf/btf.c
> @@ -33,6 +33,7 @@
>  #include <net/sock.h>
>  #include <net/xdp.h>
>  #include "../tools/lib/bpf/relo_core.h"
> +#include "../tools/lib/bpf/btf_sort.h"

I don't believe in code reuse for the sake of code reuse. This code
sharing just makes everything more entangled and complicated.
Reimplementing binary search is totally fine, IMO.

[...]

On Wed, Oct 29, 2025 at 2:40 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Mon, Oct 27, 2025 at 6:54 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
> >
> > The previous commit implemented BTF sorting verification and binary
> > search algorithm in libbpf. This patch enables this functionality in
> > the kernel.
> >
> > Cc: Eduard Zingerman <eddyz87@gmail.com>
> > Cc: Alexei Starovoitov <ast@kernel.org>
> > Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> > Cc: Alan Maguire <alan.maguire@oracle.com>
> > Cc: Song Liu <song@kernel.org>
> > Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> > Signed-off-by: Donglin Peng <dolinux.peng@gmail.com>
> > ---
> > v2->v3:
> > - Include btf_sort.c directly in btf.c to reduce function call overhead
> > ---
> >  kernel/bpf/btf.c | 34 ++++++++++++++++++----------------
> >  1 file changed, 18 insertions(+), 16 deletions(-)
> >
> > diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
> > index 0de8fc8a0e0b..df258815a6ca 100644
> > --- a/kernel/bpf/btf.c
> > +++ b/kernel/bpf/btf.c
> > @@ -33,6 +33,7 @@
> >  #include <net/sock.h>
> >  #include <net/xdp.h>
> >  #include "../tools/lib/bpf/relo_core.h"
> > +#include "../tools/lib/bpf/btf_sort.h"
>
> I don't believe in code reuse for the sake of code reuse. This code
> sharing just makes everything more entangled and complicated.
> Reimplementing binary search is totally fine, IMO.

Thanks. Would you be open to the approach from v2, where we place
the common code in btf_sort.c and compile it separately rather than
including it directly?

>
> [...]

On Tue, Oct 28, 2025 at 7:03 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> On Wed, Oct 29, 2025 at 2:40 AM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> > On Mon, Oct 27, 2025 at 6:54 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
> > >
> > > The previous commit implemented BTF sorting verification and binary
> > > search algorithm in libbpf. This patch enables this functionality in
> > > the kernel.
> > >
> > > Cc: Eduard Zingerman <eddyz87@gmail.com>
> > > Cc: Alexei Starovoitov <ast@kernel.org>
> > > Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> > > Cc: Alan Maguire <alan.maguire@oracle.com>
> > > Cc: Song Liu <song@kernel.org>
> > > Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> > > Signed-off-by: Donglin Peng <dolinux.peng@gmail.com>
> > > ---
> > > v2->v3:
> > > - Include btf_sort.c directly in btf.c to reduce function call overhead
> > > ---
> > >  kernel/bpf/btf.c | 34 ++++++++++++++++++----------------
> > >  1 file changed, 18 insertions(+), 16 deletions(-)
> > >
> > > diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
> > > index 0de8fc8a0e0b..df258815a6ca 100644
> > > --- a/kernel/bpf/btf.c
> > > +++ b/kernel/bpf/btf.c
> > > @@ -33,6 +33,7 @@
> > >  #include <net/sock.h>
> > >  #include <net/xdp.h>
> > >  #include "../tools/lib/bpf/relo_core.h"
> > > +#include "../tools/lib/bpf/btf_sort.h"
> >
> > I don't believe in code reuse for the sake of code reuse. This code
> > sharing just makes everything more entangled and complicated.
> > Reimplementing binary search is totally fine, IMO.
>
> Thanks. Would you be open to the approach from v2, where we place
> the common code in btf_sort.c and compile it separately rather than
> including it directly?
>

No, the code is too trivial to try to reuse it. Kernel and user space
libbpf code are run with different constraints, sharing it is
necessary evil (like for BPF CO-RE relocations), not something that
should be encouraged.

> >
> > [...]

On Sat, Nov 1, 2025 at 12:51 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Tue, Oct 28, 2025 at 7:03 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
> >
> > On Wed, Oct 29, 2025 at 2:40 AM Andrii Nakryiko
> > <andrii.nakryiko@gmail.com> wrote:
> > >
> > > On Mon, Oct 27, 2025 at 6:54 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
> > > >
> > > > The previous commit implemented BTF sorting verification and binary
> > > > search algorithm in libbpf. This patch enables this functionality in
> > > > the kernel.
> > > >
> > > > Cc: Eduard Zingerman <eddyz87@gmail.com>
> > > > Cc: Alexei Starovoitov <ast@kernel.org>
> > > > Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> > > > Cc: Alan Maguire <alan.maguire@oracle.com>
> > > > Cc: Song Liu <song@kernel.org>
> > > > Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> > > > Signed-off-by: Donglin Peng <dolinux.peng@gmail.com>
> > > > ---
> > > > v2->v3:
> > > > - Include btf_sort.c directly in btf.c to reduce function call overhead
> > > > ---
> > > >  kernel/bpf/btf.c | 34 ++++++++++++++++++----------------
> > > >  1 file changed, 18 insertions(+), 16 deletions(-)
> > > >
> > > > diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
> > > > index 0de8fc8a0e0b..df258815a6ca 100644
> > > > --- a/kernel/bpf/btf.c
> > > > +++ b/kernel/bpf/btf.c
> > > > @@ -33,6 +33,7 @@
> > > >  #include <net/sock.h>
> > > >  #include <net/xdp.h>
> > > >  #include "../tools/lib/bpf/relo_core.h"
> > > > +#include "../tools/lib/bpf/btf_sort.h"
> > >
> > > I don't believe in code reuse for the sake of code reuse. This code
> > > sharing just makes everything more entangled and complicated.
> > > Reimplementing binary search is totally fine, IMO.
> >
> > Thanks. Would you be open to the approach from v2, where we place
> > the common code in btf_sort.c and compile it separately rather than
> > including it directly?
> >
>
> No, the code is too trivial to try to reuse it. Kernel and user space
> libbpf code are run with different constraints, sharing it is
> necessary evil (like for BPF CO-RE relocations), not something that
> should be encouraged.

Thanks, I will implement it separately as recommended.

>
> > >
> > > [...]

On Mon, Oct 27, 2025 at 6:54 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> +
> +/*
> + * btf_sort.c is included directly to avoid function call overhead
> + * when accessing BTF private data, as this file is shared between
> + * libbpf and kernel and may be called frequently (especially when
> + * funcgraph-args or func-args tracing options are enabled).
> + */
> +#include "../../tools/lib/bpf/btf_sort.c"

function call overhead? I don't believe it's measurable.

Don't do it on libbpf side either.

pw-bot: cr

On Tue, Oct 28, 2025 at 3:56 AM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Mon, Oct 27, 2025 at 6:54 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
> >
> > +
> > +/*
> > + * btf_sort.c is included directly to avoid function call overhead
> > + * when accessing BTF private data, as this file is shared between
> > + * libbpf and kernel and may be called frequently (especially when
> > + * funcgraph-args or func-args tracing options are enabled).
> > + */
> > +#include "../../tools/lib/bpf/btf_sort.c"
>
> function call overhead? I don't believe it's measurable.

Thank you. Since the overhead is primarily due to the function graph tracer,
I have reverted to the v2 approach and added the notrace attribute to the
relevant functions.

>
> Don't do it on libbpf side either.

Yes.

>
> pw-bot: cr