Add an --inline option to extract LOC_PARAM, LOC_PROTO and LOCSEC types to a new inline split .BTF.inline while sorting BTF.
Move LOC_PARAM, LOC_PROTO, and LOCSEC types to the split BTF. Also move a FUNC when it is referenced only by LOCSEC, has no defined STT_FUNC symbol, and is not used by .BTF_ids. Move its FUNC_PROTO when no retained BTF type references that prototype. Collect defined ELF function symbols to distinguish fully inlined functions from functions that still have an out-of-line implementation. The resulting .BTF.inline therefore contains only fully inlined FUNCs (or any which have name collisions with other uninlined functions). Sort types so transferred FUNCs, eligible FUNC_PROTOs, and LOC* types form a self-contained split BTF. Sort LOCSEC records by projected function BTF ID, instruction offset, and location-prototype ID before permuting, preserving lookup order after IDs are remapped. The end state is - strings are moved to split BTF along with inline-related types when they do not have another consumer in vmlinux BTF; the goal is to minimum cost for vmlinux of inline info - partially-inlined functions referred to in LOCSEC are in vmlinux BTF - fully inlined functions are in vmlinux inline BTF - LOCSEC data is sorted by FUNC type id as the pattern for inline tracers will be to look up the function by name; once that is done a binary search based on FUNC type id can quickly identify relevant entries in LOCSEC Signed-off-by: Alan Maguire <[email protected]> --- tools/bpf/resolve_btfids/main.c | 336 +++++++++++++++++++++++++++++++- 1 file changed, 330 insertions(+), 6 deletions(-) diff --git a/tools/bpf/resolve_btfids/main.c b/tools/bpf/resolve_btfids/main.c index 37d7e7224207..20b228c4d678 100644 --- a/tools/bpf/resolve_btfids/main.c +++ b/tools/bpf/resolve_btfids/main.c @@ -142,7 +142,9 @@ struct object { struct btf *btf; struct btf *base_btf; + struct btf *inline_btf; bool distill_base; + bool extract_inline; struct { int fd; @@ -154,6 +156,10 @@ struct object { size_t strtabidx; unsigned long idlist_addr; int encoding; + const char **func_symbols; + u32 func_symbols_cnt; + u32 func_symbols_cap; + bool func_symbols_collected; } efile; struct rb_root sets; @@ -572,6 +578,58 @@ static const char *find_name_by_addr(struct object *obj, Elf64_Addr addr) return res ? res->name : NULL; } +static int cmp_func_symbol(const void *a, const void *b) +{ + const char * const *name = a; + const char * const *other = b; + + return strcmp(*name, *other); +} + +static int collect_func_symbols(struct object *obj) +{ + Elf_Scn *scn; + GElf_Shdr sh; + int n, i; + + if (obj->efile.symbols_shndx == -1) + return 0; + + scn = elf_getscn(obj->efile.elf, obj->efile.symbols_shndx); + if (!scn || gelf_getshdr(scn, &sh) != &sh) + return -EINVAL; + n = sh.sh_size / sh.sh_entsize; + + for (i = 0; i < n; i++) { + GElf_Sym sym; + const char *name; + + if (!gelf_getsym(obj->efile.symbols, i, &sym)) + return -EINVAL; + if (GELF_ST_TYPE(sym.st_info) != STT_FUNC || + sym.st_shndx == SHN_UNDEF || !sym.st_name) + continue; + name = elf_strptr(obj->efile.elf, obj->efile.strtabidx, sym.st_name); + if (!name) + return -EINVAL; + if (ensure_mem(&obj->efile.func_symbols, &obj->efile.func_symbols_cap, + obj->efile.func_symbols_cnt + 1)) + return -ENOMEM; + obj->efile.func_symbols[obj->efile.func_symbols_cnt++] = name; + } + + qsort(obj->efile.func_symbols, obj->efile.func_symbols_cnt, + sizeof(*obj->efile.func_symbols), cmp_func_symbol); + obj->efile.func_symbols_collected = true; + return 0; +} + +static bool has_func_symbol(const struct object *obj, const char *name) +{ + return bsearch(&name, obj->efile.func_symbols, obj->efile.func_symbols_cnt, + sizeof(*obj->efile.func_symbols), cmp_func_symbol) != NULL; +} + static int symbols_collect(struct object *obj) { Elf_Scn *scn = NULL; @@ -1514,14 +1572,193 @@ static int btf2btf(struct object *obj) * Sort types by name in ascending order resulting in all * anonymous types being placed before named types. */ +struct btf_name_sort { + struct btf *btf; + bool extract_inline; + bool *transfer_funcs; + bool *transfer_protos; +}; + +static int btf_inline_kind_order(const struct btf_type *t, bool transfer_func, + bool transfer_proto) +{ + if (transfer_func) + return 1; + if (transfer_proto) + return 2; + if (btf_is_loc_param(t)) + return 3; + if (btf_is_loc_proto(t)) + return 4; + if (btf_is_locsec(t)) + return 5; + return 0; +} + +enum inline_ref_kind { + INLINE_REF_FUNC, + INLINE_REF_FUNC_PROTO, +}; + +static void mark_inline_ref(struct btf *btf, bool *refs, int start_id, + int type_cnt, __u32 type_id, enum inline_ref_kind ref_kind) +{ + const struct btf_type *t; + + if (type_id < start_id || type_id >= type_cnt) + return; + t = btf__type_by_id(btf, type_id); + if ((ref_kind == INLINE_REF_FUNC && btf_is_func(t)) || + (ref_kind == INLINE_REF_FUNC_PROTO && btf_is_func_proto(t))) + refs[type_id] = true; +} + +static void mark_inline_type_refs(struct btf *btf, bool *refs, int start_id, + int type_cnt, const struct btf_type *t, + enum inline_ref_kind ref_kind) +{ + /* + * These are the only BTF kinds that can directly reference a FUNC or + * FUNC_PROTO (aside from LOCSEC). + */ + switch (btf_kind(t)) { + case BTF_KIND_CONST: + case BTF_KIND_VOLATILE: + case BTF_KIND_RESTRICT: + case BTF_KIND_PTR: + case BTF_KIND_TYPEDEF: + case BTF_KIND_FUNC: + case BTF_KIND_VAR: + case BTF_KIND_DECL_TAG: + case BTF_KIND_TYPE_TAG: + mark_inline_ref(btf, refs, start_id, type_cnt, t->type, ref_kind); + break; + default: + return; + } +} + +/* A FUNC can move to inline BTF only when LOCSEC is its sole BTF user. */ +static int find_inline_funcs(struct object *obj, bool **transfer_funcsp, + bool **transfer_protosp) +{ + bool *locsec_refs, *other_refs, *proto_candidates, *proto_base_refs; + int i, type_cnt, start_id = 0; + struct btf *btf = obj->btf; + + type_cnt = btf__type_cnt(btf); + *transfer_funcsp = NULL; + *transfer_protosp = NULL; + if (btf__base_btf(btf)) + start_id = btf__type_cnt(btf__base_btf(btf)); + + locsec_refs = calloc(type_cnt, sizeof(*locsec_refs)); + other_refs = calloc(type_cnt, sizeof(*other_refs)); + proto_candidates = calloc(type_cnt, sizeof(*proto_candidates)); + proto_base_refs = calloc(type_cnt, sizeof(*proto_base_refs)); + if (!locsec_refs || !other_refs || !proto_candidates || !proto_base_refs) + goto err; + + /* First identify locsec FUNC references */ + for (i = start_id; i < type_cnt; i++) { + const struct btf_type *t = btf__type_by_id(btf, i); + const struct btf_loc *loc; + int j; + + if (!btf_is_locsec(t)) + continue; + loc = btf_locsec_locs(t); + for (j = 0; j < btf_vlen(t); j++, loc++) { + if (loc->func >= start_id && loc->func < type_cnt && + btf_is_func(btf__type_by_id(btf, loc->func))) + locsec_refs[loc->func] = true; + } + } + + /* + * Then mark any additional references to them; references outside + * of LOCSEC make the FUNC ineligible for transfer. + */ + for (i = start_id; i < type_cnt; i++) { + const struct btf_type *t = btf__type_by_id(btf, i); + + if (btf_is_locsec(t)) + continue; + mark_inline_type_refs(btf, other_refs, start_id, type_cnt, t, + INLINE_REF_FUNC); + } + + for (i = start_id; i < type_cnt; i++) { + const struct btf_type *t = btf__type_by_id(btf, i); + const char *name; + + /* If there are no locsec references, or we find additional + * non-locsec references, skip as ineligible. + */ + if (!locsec_refs[i] || other_refs[i]) + continue; + name = btf__name_by_offset(btf, t->name_off); + /* Keep out-of-line functions and BTF ID users in the main BTF. */ + if (!obj->efile.func_symbols_collected || has_func_symbol(obj, name) || + btf_id__find(&obj->funcs, name)) + locsec_refs[i] = false; + } + + for (i = start_id; i < type_cnt; i++) { + const struct btf_type *t; + + if (!locsec_refs[i]) + continue; + t = btf__type_by_id(btf, i); + proto_candidates[t->type] = true; + } + + /* Mark every FUNC_PROTO directly needed by retained base BTF types. */ + for (i = start_id; i < type_cnt; i++) { + const struct btf_type *t = btf__type_by_id(btf, i); + + if (locsec_refs[i] || proto_candidates[i] || + btf_is_loc_param(t) || btf_is_loc_proto(t) || + btf_is_locsec(t)) + continue; + mark_inline_type_refs(btf, proto_base_refs, start_id, type_cnt, t, + INLINE_REF_FUNC_PROTO); + } + for (i = start_id; i < type_cnt; i++) + proto_candidates[i] &= !proto_base_refs[i]; + + free(other_refs); + *transfer_funcsp = locsec_refs; + *transfer_protosp = proto_candidates; + free(proto_base_refs); + return 0; +err: + free(locsec_refs); + free(other_refs); + free(proto_candidates); + free(proto_base_refs); + return -ENOMEM; +} + static int cmp_type_names(const void *a, const void *b, void *priv) { - struct btf *btf = (struct btf *)priv; + struct btf_name_sort *sort = priv; + struct btf *btf = sort->btf; 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; + int inline_order; int r; + if (sort->extract_inline) { + inline_order = btf_inline_kind_order(ta, sort->transfer_funcs[*(__u32 *)a], + sort->transfer_protos[*(__u32 *)a]) - + btf_inline_kind_order(tb, sort->transfer_funcs[*(__u32 *)b], + sort->transfer_protos[*(__u32 *)b]); + if (inline_order) + return inline_order; + } + na = btf__str_by_offset(btf, ta->name_off); nb = btf__str_by_offset(btf, tb->name_off); r = strcmp(na, nb); @@ -1532,8 +1769,60 @@ static int cmp_type_names(const void *a, const void *b, void *priv) return *(__u32 *)a < *(__u32 *)b ? -1 : 1; } -static int sort_btf_by_name(struct btf *btf) +struct loc_sort { + const __u32 *id_map; + __u32 start_id; +}; + +static __u32 projected_type_id(const struct loc_sort *sort, __u32 id) +{ + if (id < sort->start_id) + return id; + return sort->id_map[id - sort->start_id] & ~BTF_PERMUTE_ID_TRANSFER; +} + +static int cmp_loc(const void *a, const void *b, void *priv) { + const struct loc_sort *sort = priv; + const struct btf_loc *la = a, *lb = b; + __u32 afunc = projected_type_id(sort, la->func); + __u32 bfunc = projected_type_id(sort, lb->func); + __u32 aproto = projected_type_id(sort, la->loc_proto); + __u32 bproto = projected_type_id(sort, lb->loc_proto); + + if (afunc != bfunc) + return afunc < bfunc ? -1 : 1; + if (la->offset != lb->offset) + return la->offset < lb->offset ? -1 : 1; + if (aproto != bproto) + return aproto < bproto ? -1 : 1; + return 0; +} + +static void sort_locsecs(struct btf *btf, const __u32 *id_map, __u32 start_id, + int nr_types) +{ + struct loc_sort sort = { .id_map = id_map, .start_id = start_id }; + int i; + + for (i = 0; i < nr_types; i++) { + struct btf_type *t = (struct btf_type *)btf__type_by_id(btf, start_id + i); + + if (btf_is_locsec(t)) + qsort_r(btf_locsec_locs(t), btf_vlen(t), sizeof(struct btf_loc), + cmp_loc, &sort); + } +} + +static int sort_btf_by_name(struct object *obj) +{ + struct btf *btf = obj->btf; + bool *transfer_funcs = NULL, *transfer_protos = NULL; + struct btf_name_sort sort = { + .btf = btf, + .extract_inline = obj->extract_inline, + }; + LIBBPF_OPTS(btf_permute_opts, opts); __u32 *permute_ids = NULL, *id_map = NULL; int nr_types, i, err = 0; __u32 start_id = 0, id; @@ -1541,6 +1830,13 @@ static int sort_btf_by_name(struct btf *btf) if (btf__base_btf(btf)) start_id = btf__type_cnt(btf__base_btf(btf)); nr_types = btf__type_cnt(btf) - start_id; + if (obj->extract_inline) { + err = find_inline_funcs(obj, &transfer_funcs, &transfer_protos); + if (err) + goto out; + sort.transfer_funcs = transfer_funcs; + sort.transfer_protos = transfer_protos; + } permute_ids = calloc(nr_types, sizeof(*permute_ids)); if (!permute_ids) { @@ -1557,21 +1853,37 @@ static int sort_btf_by_name(struct btf *btf) 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); + qsort_r(permute_ids, nr_types, sizeof(*permute_ids), cmp_type_names, &sort); for (i = 0; i < nr_types; i++) { id = permute_ids[i] - start_id; id_map[id] = i + start_id; + if (obj->extract_inline && + btf_inline_kind_order(btf__type_by_id(btf, permute_ids[i]), + transfer_funcs[permute_ids[i]], + transfer_protos[permute_ids[i]])) + id_map[id] |= BTF_PERMUTE_ID_TRANSFER; } - err = btf__permute(btf, id_map, nr_types, NULL); + /* + * Key LOCSEC records by their post-permutation function ID and offset + * since the tracer pattern will be to look up FUNC by name, then + * find LOCSEC records for that function. + */ + sort_locsecs(btf, id_map, start_id, nr_types); + + if (obj->extract_inline) + opts.transfer_btf = &obj->inline_btf; + err = btf__permute(btf, id_map, nr_types, + obj->extract_inline ? &opts : NULL); if (err) pr_err("FAILED: btf permute: %s\n", strerror(-err)); out: free(permute_ids); free(id_map); + free(transfer_funcs); + free(transfer_protos); return err; } @@ -1599,7 +1911,7 @@ static int finalize_btf(struct object *obj) obj->btf = btf; } - err = sort_btf_by_name(obj->btf); + err = sort_btf_by_name(obj); if (err) { pr_err("FAILED to sort BTF: %s\n", strerror(errno)); goto out_err; @@ -1773,6 +2085,8 @@ int main(int argc, const char **argv) "turn warnings into errors"), OPT_BOOLEAN(0, "distill_base", &obj.distill_base, "distill --btf_base and emit .BTF.base section data"), + OPT_BOOLEAN(0, "inline", &obj.extract_inline, + "extract location BTF into a .BTF.inline file"), OPT_STRING(0, "patch_btfids", &btfids_path, "file", "path to .BTF_ids section data blob to patch into ELF file"), OPT_END() @@ -1791,6 +2105,8 @@ int main(int argc, const char **argv) if (elf_collect(&obj)) goto out; + if (obj.extract_inline && collect_func_symbols(&obj)) + goto out; /* * We did not find .BTF_ids section or symbols section, @@ -1841,11 +2157,18 @@ int main(int argc, const char **argv) if (err) goto out; } + if (obj.inline_btf) { + err = make_out_path(out_path, sizeof(out_path), obj.path, BTF_ELF_SEC ".inline"); + err = err ?: dump_raw_btf(obj.inline_btf, out_path); + if (err) + goto out; + } if (!(fatal_warnings && warnings)) err = 0; out: btf__free(obj.base_btf); + btf__free(obj.inline_btf); btf__free(obj.btf); btf_id__free_all(&obj.structs); btf_id__free_all(&obj.unions); @@ -1853,6 +2176,7 @@ int main(int argc, const char **argv) btf_id__free_all(&obj.funcs); btf_id__free_all(&obj.sets); free(obj.addr_syms); + free(obj.efile.func_symbols); if (obj.efile.elf) { elf_end(obj.efile.elf); close(obj.efile.fd); -- 2.43.5
