Message-ID: <CAErzpmvJ+D2c_3pLG-t5ZD2cj7kDJX=JDnJ0CxNUf5pYR24a+g@mail.gmail.com>
Date: Fri, 21 Nov 2025 23:36:55 +0800
From: Donglin Peng <dolinux.peng@...il.com>
To: Ihor Solodrai <ihor.solodrai@...ux.dev>
Cc: ast@...nel.org, andrii.nakryiko@...il.com, eddyz87@...il.com, 
	zhangxiaoqin@...omi.com, linux-kernel@...r.kernel.org, bpf@...r.kernel.org, 
	Donglin Peng <pengdonglin@...omi.com>, Alan Maguire <alan.maguire@...cle.com>, 
	Song Liu <song@...nel.org>
Subject: Re: [RFC PATCH v7 3/7] tools/resolve_btfids: Add --btf_sort option
 for BTF name sorting

On Fri, Nov 21, 2025 at 5:34 AM Ihor Solodrai <ihor.solodrai@...ux.dev> wrote:
>
> On 11/18/25 7:15 PM, Donglin Peng wrote:
> > From: Donglin Peng <pengdonglin@...omi.com>
> >
> > This patch introduces a new --btf_sort option that leverages libbpf's
> > btf__permute interface to reorganize BTF layout. The implementation
> > sorts BTF types by name in ascending order, placing anonymous types at
> > the end to enable efficient binary search lookup.
> >
> > Cc: Eduard Zingerman <eddyz87@...il.com>
> > Cc: Alexei Starovoitov <ast@...nel.org>
> > Cc: Andrii Nakryiko <andrii.nakryiko@...il.com>
> > Cc: Alan Maguire <alan.maguire@...cle.com>
> > Cc: Song Liu <song@...nel.org>
> > Cc: Xiaoqin Zhang <zhangxiaoqin@...omi.com>
> > Signed-off-by: Donglin Peng <pengdonglin@...omi.com>
> > ---
> >  scripts/Makefile.btf            |   2 +
> >  scripts/Makefile.modfinal       |   1 +
> >  scripts/link-vmlinux.sh         |   1 +
> >  tools/bpf/resolve_btfids/main.c | 200 ++++++++++++++++++++++++++++++++
> >  4 files changed, 204 insertions(+)
> >
> > diff --git a/scripts/Makefile.btf b/scripts/Makefile.btf
> > index db76335dd917..d5eb4ee70e88 100644
> > --- a/scripts/Makefile.btf
> > +++ b/scripts/Makefile.btf
> > @@ -27,6 +27,7 @@ pahole-flags-$(call test-ge, $(pahole-ver), 130) += --btf_features=attributes
> >
> >  ifneq ($(KBUILD_EXTMOD),)
> >  module-pahole-flags-$(call test-ge, $(pahole-ver), 128) += --btf_features=distilled_base
> > +module-resolve_btfid-flags-y = --distilled_base
> >  endif
> >
> >  endif
> > @@ -35,3 +36,4 @@ pahole-flags-$(CONFIG_PAHOLE_HAS_LANG_EXCLUDE)              += --lang_exclude=rust
> >
> >  export PAHOLE_FLAGS := $(pahole-flags-y)
> >  export MODULE_PAHOLE_FLAGS := $(module-pahole-flags-y)
> > +export MODULE_RESOLVE_BTFID_FLAGS := $(module-resolve_btfid-flags-y)
> > diff --git a/scripts/Makefile.modfinal b/scripts/Makefile.modfinal
> > index 542ba462ed3e..4481dda2f485 100644
> > --- a/scripts/Makefile.modfinal
> > +++ b/scripts/Makefile.modfinal
> > @@ -40,6 +40,7 @@ quiet_cmd_btf_ko = BTF [M] $@
> >               printf "Skipping BTF generation for %s due to unavailability of vmlinux\n" $@ 1>&2; \
> >       else                                                            \
> >               LLVM_OBJCOPY="$(OBJCOPY)" $(PAHOLE) -J $(PAHOLE_FLAGS) $(MODULE_PAHOLE_FLAGS) --btf_base $(objtree)/vmlinux $@; \
> > +             $(RESOLVE_BTFIDS) -b $(objtree)/vmlinux $(MODULE_RESOLVE_BTFID_FLAGS) --btf_sort $@;    \
> >               $(RESOLVE_BTFIDS) -b $(objtree)/vmlinux $@;             \
> >       fi;
> >
> > diff --git a/scripts/link-vmlinux.sh b/scripts/link-vmlinux.sh
> > index 433849ff7529..f21f6300815b 100755
> > --- a/scripts/link-vmlinux.sh
> > +++ b/scripts/link-vmlinux.sh
> > @@ -288,6 +288,7 @@ if is_enabled CONFIG_DEBUG_INFO_BTF; then
> >       if is_enabled CONFIG_WERROR; then
> >               RESOLVE_BTFIDS_ARGS=" --fatal_warnings "
> >       fi
> > +     ${RESOLVE_BTFIDS} ${RESOLVE_BTFIDS_ARGS} --btf_sort "${VMLINUX}"
> >       ${RESOLVE_BTFIDS} ${RESOLVE_BTFIDS_ARGS} "${VMLINUX}"
> >  fi
> >
> > diff --git a/tools/bpf/resolve_btfids/main.c b/tools/bpf/resolve_btfids/main.c
> > index d47191c6e55e..dc0badd6f375 100644
> > --- a/tools/bpf/resolve_btfids/main.c
> > +++ b/tools/bpf/resolve_btfids/main.c
> > @@ -768,6 +768,195 @@ static int symbols_patch(struct object *obj)
> >       return err < 0 ? -1 : 0;
> >  }
> >
> > +/* Anonymous types (with empty names) are considered greater than named types
> > + * and are sorted after them. Two anonymous types are considered equal. Named
> > + * types are compared lexicographically.
> > + */
> > +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;
> > +
> > +     if (!ta->name_off && tb->name_off)
> > +             return 1;
> > +     if (ta->name_off && !tb->name_off)
> > +             return -1;
> > +     if (!ta->name_off && !tb->name_off)
> > +             return 0;
> > +
> > +     na = btf__str_by_offset(btf, ta->name_off);
> > +     nb = btf__str_by_offset(btf, tb->name_off);
> > +     return strcmp(na, nb);
> > +}
> > +
> > +static int update_btf_section(const char *path, const struct btf *btf,
>
> Hi Dongling.
>
> Thanks for working on this, it's a great optimization. Just want to
> give you a heads up that I am preparing a patchset changing
> resolve_btfids behavior.

Thanks. I'm curious about the new behavior of resolve_btfids. Does it
replace pahole and generate the sorted .BTF data directly from the
DWARF data? Also, does its sorting method differ from the cmp_type_names
approach mentioned above — specifically, does it place named types
before all anonymous types? I'm asking because the search method
needs to be compatible with this sorting approach.

>
> In particular, instead of updating the .BTF_ids section (and now with
> your and upcoming changes the .BTF section) *in-place*, resolve_btfids
> will only emit the data for the sections. And then it'll be integrated
> into vmlinux with objcopy and linker. We already do a similar thing
> with .BTF for vmlinux [1].
>
> For your patchset it means that the parts handling ELF update will be
> unnecessary.
>
> Also I think the --btf_sort flag is unnecessary. We probably want
> kernel BTF to always be sorted in this way. And if resolve_btfids will
> be handling more btf2btf transformation, we should avoid adding a
> flags for every one of them.
>
> [1] https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/scripts/link-vmlinux.sh#n110
>
>
> > +                               const char *btf_secname)
> > +{
> > +     GElf_Shdr shdr_mem, *shdr;
> > +     Elf_Data *btf_data = NULL;
> > +     Elf_Scn *scn = NULL;
> > +     Elf *elf = NULL;
> > +     const void *raw_btf_data;
> > +     uint32_t raw_btf_size;
> > +     int fd, err = -1;
> > +     size_t strndx;
> > +
> > +     fd = open(path, O_RDWR);
> > +     if (fd < 0) {
> > +             pr_err("FAILED to open %s\n", path);
> > +             return -1;
> > +     }
> > +
> > +     if (elf_version(EV_CURRENT) == EV_NONE) {
> > +             pr_err("FAILED to set libelf version");
> > +             goto out;
> > +     }
> > +
> > +     elf = elf_begin(fd, ELF_C_RDWR, NULL);
> > +     if (elf == NULL) {
> > +             pr_err("FAILED to update ELF file");
> > +             goto out;
> > +     }
> > +
> > +     elf_flagelf(elf, ELF_C_SET, ELF_F_LAYOUT);
> > +
> > +     elf_getshdrstrndx(elf, &strndx);
> > +     while ((scn = elf_nextscn(elf, scn)) != NULL) {
> > +             char *secname;
> > +
> > +             shdr = gelf_getshdr(scn, &shdr_mem);
> > +             if (shdr == NULL)
> > +                     continue;
> > +             secname = elf_strptr(elf, strndx, shdr->sh_name);
> > +             if (strcmp(secname, btf_secname) == 0) {
> > +                     btf_data = elf_getdata(scn, btf_data);
> > +                     break;
> > +             }
> > +     }
> > +
> > +     raw_btf_data = btf__raw_data(btf, &raw_btf_size);
> > +
> > +     if (btf_data) {
> > +             if (raw_btf_size != btf_data->d_size) {
> > +                     pr_err("FAILED: size mismatch");
> > +                     goto out;
> > +             }
> > +
> > +             btf_data->d_buf = (void *)raw_btf_data;
> > +             btf_data->d_type = ELF_T_WORD;
> > +             elf_flagdata(btf_data, ELF_C_SET, ELF_F_DIRTY);
> > +
> > +             if (elf_update(elf, ELF_C_WRITE) >= 0)
> > +                     err = 0;
> > +     }
> > +
> > +out:
> > +     if (fd != -1)
> > +             close(fd);
> > +     if (elf)
> > +             elf_end(elf);
> > +     return err;
> > +}
> > +
> > +static int sort_update_btf(struct object *obj, bool distilled_base)
> > +{
> > +     struct btf *base_btf = NULL;
> > +     struct btf *btf = NULL;
> > +     int start_id = 1, nr_types, id;
> > +     int err = 0, i;
> > +     __u32 *permute_ids = NULL, *id_map = NULL, btf_size;
> > +     const void *btf_data;
> > +     int fd;
> > +
> > +     if (obj->base_btf_path) {
> > +             base_btf = btf__parse(obj->base_btf_path, NULL);
> > +             err = libbpf_get_error(base_btf);
> > +             if (err) {
> > +                     pr_err("FAILED: load base BTF from %s: %s\n",
> > +                            obj->base_btf_path, strerror(-err));
> > +                     return -1;
> > +             }
> > +     }
> > +
> > +     btf = btf__parse_elf_split(obj->path, base_btf);
> > +     err = libbpf_get_error(btf);
> > +     if (err) {
> > +             pr_err("FAILED: load BTF from %s: %s\n", obj->path, strerror(-err));
> > +             goto out;
> > +     }
> > +
> > +     if (base_btf)
> > +             start_id = btf__type_cnt(base_btf);
> > +     nr_types = btf__type_cnt(btf) - start_id;
> > +     if (nr_types < 2)
> > +             goto out;
> > +
> > +     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, nr_types, 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));
> > +             goto out;
> > +     }
> > +
> > +     if (distilled_base) {
> > +             struct btf *new_btf = NULL, *distilled_base = NULL;
> > +
> > +             if (btf__distill_base(btf, &distilled_base, &new_btf) < 0) {
> > +                     pr_err("FAILED to generate distilled base BTF: %s\n",
> > +                             strerror(errno));
> > +                     goto out;
> > +             }
> > +
> > +             err = update_btf_section(obj->path, new_btf, BTF_ELF_SEC);
> > +             if (!err) {
> > +                     err = update_btf_section(obj->path, distilled_base, BTF_BASE_ELF_SEC);
> > +                     if (err < 0)
> > +                             pr_err("FAILED to update '%s'\n", BTF_BASE_ELF_SEC);
> > +             } else {
> > +                     pr_err("FAILED to update '%s'\n", BTF_ELF_SEC);
> > +             }
> > +
> > +             btf__free(new_btf);
> > +             btf__free(distilled_base);
> > +     } else {
> > +             err = update_btf_section(obj->path, btf, BTF_ELF_SEC);
> > +             if (err < 0) {
> > +                     pr_err("FAILED to update '%s'\n", BTF_ELF_SEC);
> > +                     goto out;
> > +             }
> > +     }
> > +
> > +out:
> > +     free(permute_ids);
> > +     free(id_map);
> > +     btf__free(base_btf);
> > +     btf__free(btf);
> > +     return err;
> > +}
> > +
> >  static const char * const resolve_btfids_usage[] = {
> >       "resolve_btfids [<options>] <ELF object>",
> >       NULL
> > @@ -787,6 +976,8 @@ int main(int argc, const char **argv)
> >               .sets     = RB_ROOT,
> >       };
> >       bool fatal_warnings = false;
> > +     bool btf_sort = false;
> > +     bool distilled_base = false;
> >       struct option btfid_options[] = {
> >               OPT_INCR('v', "verbose", &verbose,
> >                        "be more verbose (show errors, etc)"),
> > @@ -796,6 +987,10 @@ int main(int argc, const char **argv)
> >                          "path of file providing base BTF"),
> >               OPT_BOOLEAN(0, "fatal_warnings", &fatal_warnings,
> >                           "turn warnings into errors"),
> > +             OPT_BOOLEAN(0, "btf_sort", &btf_sort,
> > +                         "sort BTF by name in ascending order"),
> > +             OPT_BOOLEAN(0, "distilled_base", &distilled_base,
> > +                         "distill base"),
> >               OPT_END()
> >       };
> >       int err = -1;
> > @@ -807,6 +1002,11 @@ int main(int argc, const char **argv)
> >
> >       obj.path = argv[0];
> >
> > +     if (btf_sort) {
> > +             err = sort_update_btf(&obj, distilled_base);
> > +             goto out;
> > +     }
> > +
> >       if (elf_collect(&obj))
> >               goto out;
> >
>

Powered by blists - more mailing lists