From: Donglin Peng <pengdonglin@xiaomi.com>
This introduces a new BTF sorting phase that specifically sorts
BTF types by name in ascending order, so that the binary search
can be used to look up types.
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: Ihor Solodrai <ihor.solodrai@linux.dev>
Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
---
tools/bpf/resolve_btfids/main.c | 64 +++++++++++++++++++++++++++++++++
1 file changed, 64 insertions(+)
diff --git a/tools/bpf/resolve_btfids/main.c b/tools/bpf/resolve_btfids/main.c
index df39982f51df..343d08050116 100644
--- a/tools/bpf/resolve_btfids/main.c
+++ b/tools/bpf/resolve_btfids/main.c
@@ -850,6 +850,67 @@ static int dump_raw_btf(struct btf *btf, const char *out_path)
return 0;
}
+/*
+ * Sort types by name in ascending order resulting in all
+ * anonymous types being placed before named types.
+ */
+static int cmp_type_names(const void *a, const void *b, void *priv)
+{
+ struct btf *btf = (struct btf *)priv;
+ const struct btf_type *ta = btf__type_by_id(btf, *(__u32 *)a);
+ const struct btf_type *tb = btf__type_by_id(btf, *(__u32 *)b);
+ const char *na, *nb;
+
+ na = btf__str_by_offset(btf, ta->name_off);
+ nb = btf__str_by_offset(btf, tb->name_off);
+ return strcmp(na, nb);
+}
+
+static int sort_btf_by_name(struct btf *btf)
+{
+ __u32 *permute_ids = NULL, *id_map = NULL;
+ int nr_types, i, err = 0;
+ __u32 start_id = 0, start_offs = 1, id;
+
+ if (btf__base_btf(btf)) {
+ start_id = btf__type_cnt(btf__base_btf(btf));
+ start_offs = 0;
+ }
+ nr_types = btf__type_cnt(btf) - start_id;
+
+ permute_ids = calloc(nr_types, sizeof(*permute_ids));
+ if (!permute_ids) {
+ err = -ENOMEM;
+ goto out;
+ }
+
+ id_map = calloc(nr_types, sizeof(*id_map));
+ if (!id_map) {
+ err = -ENOMEM;
+ goto out;
+ }
+
+ for (i = 0, id = start_id; i < nr_types; i++, id++)
+ permute_ids[i] = id;
+
+ qsort_r(permute_ids + start_offs, nr_types - start_offs,
+ sizeof(*permute_ids), cmp_type_names, btf);
+
+ for (i = 0; i < nr_types; i++) {
+ id = permute_ids[i] - start_id;
+ id_map[id] = i + start_id;
+ }
+
+ err = btf__permute(btf, id_map, nr_types, NULL);
+ if (err)
+ pr_err("FAILED: btf permute: %s\n", strerror(-err));
+
+out:
+ free(permute_ids);
+ free(id_map);
+ return err;
+}
+
static inline int make_out_path(char *buf, u32 buf_sz, const char *in_path, const char *suffix)
{
int len = snprintf(buf, buf_sz, "%s%s", in_path, suffix);
@@ -1025,6 +1086,9 @@ int main(int argc, const char **argv)
if (load_btf(&obj))
goto out;
+ if (sort_btf_by_name(obj.btf))
+ goto out;
+
if (elf_collect(&obj))
goto out;
--
2.34.1On Fri, Jan 9, 2026 at 5:00 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> From: Donglin Peng <pengdonglin@xiaomi.com>
>
> This introduces a new BTF sorting phase that specifically sorts
> BTF types by name in ascending order, so that the binary search
> can be used to look up types.
>
> 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: Ihor Solodrai <ihor.solodrai@linux.dev>
> Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
> Acked-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
> tools/bpf/resolve_btfids/main.c | 64 +++++++++++++++++++++++++++++++++
> 1 file changed, 64 insertions(+)
>
> diff --git a/tools/bpf/resolve_btfids/main.c b/tools/bpf/resolve_btfids/main.c
> index df39982f51df..343d08050116 100644
> --- a/tools/bpf/resolve_btfids/main.c
> +++ b/tools/bpf/resolve_btfids/main.c
> @@ -850,6 +850,67 @@ static int dump_raw_btf(struct btf *btf, const char *out_path)
> return 0;
> }
>
> +/*
> + * Sort types by name in ascending order resulting in all
> + * anonymous types being placed before named types.
> + */
> +static int cmp_type_names(const void *a, const void *b, void *priv)
> +{
> + struct btf *btf = (struct btf *)priv;
> + const struct btf_type *ta = btf__type_by_id(btf, *(__u32 *)a);
> + const struct btf_type *tb = btf__type_by_id(btf, *(__u32 *)b);
> + const char *na, *nb;
> +
> + na = btf__str_by_offset(btf, ta->name_off);
> + nb = btf__str_by_offset(btf, tb->name_off);
> + return strcmp(na, nb);
let's disambiguate the case when strcmp() == 0:
int r = strcmp(na, nb);
if (r != 0)
return r;
/* preserve original relative order of anonymous or same-named types */
return *(__u32 *)a < *(__u32 *)b ? -1 : 1;
(please send as a follow up)
> +}
> +
> +static int sort_btf_by_name(struct btf *btf)
> +{
> + __u32 *permute_ids = NULL, *id_map = NULL;
> + int nr_types, i, err = 0;
> + __u32 start_id = 0, start_offs = 1, id;
> +
> + if (btf__base_btf(btf)) {
> + start_id = btf__type_cnt(btf__base_btf(btf));
> + start_offs = 0;
with the above cmp_type_names disambiguation sorting becomes stable,
so you won't need this start_offs thing here, you can safely compare
VOID with any other type and it will stay the very first one
(please include in the follow up as well)
> + }
> + nr_types = btf__type_cnt(btf) - start_id;
> +
> + permute_ids = calloc(nr_types, sizeof(*permute_ids));
> + if (!permute_ids) {
> + err = -ENOMEM;
> + goto out;
> + }
> +
> + id_map = calloc(nr_types, sizeof(*id_map));
> + if (!id_map) {
> + err = -ENOMEM;
> + goto out;
> + }
> +
> + for (i = 0, id = start_id; i < nr_types; i++, id++)
> + permute_ids[i] = id;
> +
> + qsort_r(permute_ids + start_offs, nr_types - start_offs,
> + sizeof(*permute_ids), cmp_type_names, btf);
> +
> + for (i = 0; i < nr_types; i++) {
> + id = permute_ids[i] - start_id;
> + id_map[id] = i + start_id;
> + }
> +
> + err = btf__permute(btf, id_map, nr_types, NULL);
> + if (err)
> + pr_err("FAILED: btf permute: %s\n", strerror(-err));
> +
> +out:
> + free(permute_ids);
> + free(id_map);
> + return err;
> +}
> +
> static inline int make_out_path(char *buf, u32 buf_sz, const char *in_path, const char *suffix)
> {
> int len = snprintf(buf, buf_sz, "%s%s", in_path, suffix);
> @@ -1025,6 +1086,9 @@ int main(int argc, const char **argv)
> if (load_btf(&obj))
> goto out;
>
> + if (sort_btf_by_name(obj.btf))
> + goto out;
> +
> if (elf_collect(&obj))
> goto out;
>
> --
> 2.34.1
>
On Wed, Jan 14, 2026 at 8:29 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Fri, Jan 9, 2026 at 5:00 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
> >
> > From: Donglin Peng <pengdonglin@xiaomi.com>
> >
> > This introduces a new BTF sorting phase that specifically sorts
> > BTF types by name in ascending order, so that the binary search
> > can be used to look up types.
> >
> > 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: Ihor Solodrai <ihor.solodrai@linux.dev>
> > Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> > Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
> > Acked-by: Eduard Zingerman <eddyz87@gmail.com>
> > ---
> > tools/bpf/resolve_btfids/main.c | 64 +++++++++++++++++++++++++++++++++
> > 1 file changed, 64 insertions(+)
> >
> > diff --git a/tools/bpf/resolve_btfids/main.c b/tools/bpf/resolve_btfids/main.c
> > index df39982f51df..343d08050116 100644
> > --- a/tools/bpf/resolve_btfids/main.c
> > +++ b/tools/bpf/resolve_btfids/main.c
> > @@ -850,6 +850,67 @@ static int dump_raw_btf(struct btf *btf, const char *out_path)
> > return 0;
> > }
> >
> > +/*
> > + * Sort types by name in ascending order resulting in all
> > + * anonymous types being placed before named types.
> > + */
> > +static int cmp_type_names(const void *a, const void *b, void *priv)
> > +{
> > + struct btf *btf = (struct btf *)priv;
> > + const struct btf_type *ta = btf__type_by_id(btf, *(__u32 *)a);
> > + const struct btf_type *tb = btf__type_by_id(btf, *(__u32 *)b);
> > + const char *na, *nb;
> > +
> > + na = btf__str_by_offset(btf, ta->name_off);
> > + nb = btf__str_by_offset(btf, tb->name_off);
> > + return strcmp(na, nb);
>
> let's disambiguate the case when strcmp() == 0:
>
> int r = strcmp(na, nb);
> if (r != 0)
> return r;
>
> /* preserve original relative order of anonymous or same-named types */
> return *(__u32 *)a < *(__u32 *)b ? -1 : 1;
Thanks, I see.
>
> (please send as a follow up)
Ok.
>
>
> > +}
> > +
> > +static int sort_btf_by_name(struct btf *btf)
> > +{
> > + __u32 *permute_ids = NULL, *id_map = NULL;
> > + int nr_types, i, err = 0;
> > + __u32 start_id = 0, start_offs = 1, id;
> > +
> > + if (btf__base_btf(btf)) {
> > + start_id = btf__type_cnt(btf__base_btf(btf));
> > + start_offs = 0;
>
> with the above cmp_type_names disambiguation sorting becomes stable,
> so you won't need this start_offs thing here, you can safely compare
> VOID with any other type and it will stay the very first one
Great, I will fix it in v13 of this patch.
>
> (please include in the follow up as well)
Okay, thanks.
>
>
>
> > + }
> > + nr_types = btf__type_cnt(btf) - start_id;
> > +
> > + permute_ids = calloc(nr_types, sizeof(*permute_ids));
> > + if (!permute_ids) {
> > + err = -ENOMEM;
> > + goto out;
> > + }
> > +
> > + id_map = calloc(nr_types, sizeof(*id_map));
> > + if (!id_map) {
> > + err = -ENOMEM;
> > + goto out;
> > + }
> > +
> > + for (i = 0, id = start_id; i < nr_types; i++, id++)
> > + permute_ids[i] = id;
> > +
> > + qsort_r(permute_ids + start_offs, nr_types - start_offs,
> > + sizeof(*permute_ids), cmp_type_names, btf);
> > +
> > + for (i = 0; i < nr_types; i++) {
> > + id = permute_ids[i] - start_id;
> > + id_map[id] = i + start_id;
> > + }
> > +
> > + err = btf__permute(btf, id_map, nr_types, NULL);
> > + if (err)
> > + pr_err("FAILED: btf permute: %s\n", strerror(-err));
> > +
> > +out:
> > + free(permute_ids);
> > + free(id_map);
> > + return err;
> > +}
> > +
> > static inline int make_out_path(char *buf, u32 buf_sz, const char *in_path, const char *suffix)
> > {
> > int len = snprintf(buf, buf_sz, "%s%s", in_path, suffix);
> > @@ -1025,6 +1086,9 @@ int main(int argc, const char **argv)
> > if (load_btf(&obj))
> > goto out;
> >
> > + if (sort_btf_by_name(obj.btf))
> > + goto out;
> > +
> > if (elf_collect(&obj))
> > goto out;
> >
> > --
> > 2.34.1
> >
© 2016 - 2026 Red Hat, Inc.