On Fri, 2024-05-10 at 11:30 +0100, Alan Maguire wrote:
Looks good to me, but I think that comparison function should be
extended to include 'size' to cover some corner cases, see below.
[...]
> +/* Simple string comparison used for sorting within BTF, since all distilled types are
> + * named.
> + */
> +static int cmp_btf_types(const void *id1, const void *id2, void *priv)
> +{
> + const struct btf *btf = priv;
> + const struct btf_type *t1 = btf_type_by_id(btf, *(__u32 *)id1);
> + const struct btf_type *t2 = btf_type_by_id(btf, *(__u32 *)id2);
> +
> + return strcmp(btf__name_by_offset(btf, t1->name_off),
> + btf__name_by_offset(btf, t2->name_off));
> +}
> +
> +/* Comparison between base BTF type (search type) and distilled base types (target).
> + * Because there is no bsearch_r() we need to use the search key - which also is
> + * the first element of struct btf_relocate * - as a means to retrieve the
> + * struct btf_relocate *.
> + */
> +static int cmp_base_and_distilled_btf_types(const void *idbase, const void *iddist)
> +{
> + struct btf_relocate *r = (struct btf_relocate *)idbase;
> + const struct btf_type *tbase = btf_type_by_id(r->base_btf, *(__u32 *)idbase);
> + const struct btf_type *tdist = btf_type_by_id(r->dist_base_btf, *(__u32 *)iddist);
> +
> + return strcmp(btf__name_by_offset(r->base_btf, tbase->name_off),
> + btf__name_by_offset(r->dist_base_btf, tdist->name_off));
> +}
Interestingly, comparison by name might not be sufficient.
E.g. in my test kernel there are a few STRUCT/UNION types with duplicate names:
$ comm -3 <(bpftool btf dump file vmlinux | grep '^[\[0-9\]\+] \(STRUCT\|UNION\)' \
| grep -v "'(anon)'" | awk '{ print $3 }' | sort) \
<(bpftool btf dump file vmlinux | grep '^[\[0-9\]\+] \(STRUCT\|UNION\)' \
| grep -v "'(anon)'" | awk '{ print $3 }' | sort -u)
'chksum_desc_ctx'
'console'
'disklabel'
'dma_chan'
'd_partition'
'getdents_callback'
'irq_info'
'netlbl_domhsh_walk_arg'
'pci_root_info'
'perf_aux_event'
'perf_aux_event'
'port'
'syscall_tp_t'
I checked 'disklabel' and 'dma_chan', these are legit structures with
different size and number of members. The number of members is not
stored in the distilled BPF, but size could be used for additional
disambiguation.
> +
> +/* Build a map from distilled base BTF ids to base BTF ids. To do so, iterate
> + * through base BTF looking up distilled type (using binary search) equivalents.
> + *
> +static int btf_relocate_map_distilled_base(struct btf_relocate *r)
> +{
> + struct btf_type *t;
> + const char *name;
> + __u32 id;
> +
> + /* generate a sort index array of type ids sorted by name for distilled
> + * base BTF to speed lookups.
> + */
> + for (id = 1; id < r->nr_dist_base_types; id++)
> + r->dist_base_index[id] = id;
> + qsort_r(r->dist_base_index, r->nr_dist_base_types, sizeof(__u32), cmp_btf_types,
> + (struct btf *)r->dist_base_btf);
> +
> + for (id = 1; id < r->nr_base_types; id++) {
> + struct btf_type *dist_t;
> + int dist_kind, kind;
> + bool compat_kind;
> + __u32 *dist_id;
> +
> + t = btf_type_by_id(r->base_btf, id);
> + kind = btf_kind(t);
> + /* distilled base consists of named types only. */
> + if (!t->name_off)
> + continue;
> + switch (kind) {
> + case BTF_KIND_INT:
> + case BTF_KIND_FLOAT:
> + case BTF_KIND_ENUM:
> + case BTF_KIND_ENUM64:
> + case BTF_KIND_FWD:
> + case BTF_KIND_STRUCT:
> + case BTF_KIND_UNION:
> + break;
> + default:
> + continue;
> + }
> + r->search_id = id;
> + dist_id = bsearch(&r->search_id, r->dist_base_index, r->nr_dist_base_types,
> + sizeof(__u32), cmp_base_and_distilled_btf_types);
> + if (!dist_id)
> + continue;
> + if (!*dist_id || *dist_id > r->nr_dist_base_types) {
> + pr_warn("base BTF id [%d] maps to invalid distilled base BTF id [%d]\n",
> + id, *dist_id);
> + return -EINVAL;
> + }
> + /* validate that kinds are compatible */
> + dist_t = btf_type_by_id(r->dist_base_btf, *dist_id);
> + dist_kind = btf_kind(dist_t);
> + name = btf__name_by_offset(r->dist_base_btf, dist_t->name_off);
> + compat_kind = dist_kind == kind;
> + if (!compat_kind) {
> + switch (dist_kind) {
> + case BTF_KIND_FWD:
> + compat_kind = kind == BTF_KIND_STRUCT || kind == BTF_KIND_UNION;
> + break;
> + case BTF_KIND_ENUM:
> + compat_kind = kind == BTF_KIND_ENUM64;
> + break;
> + default:
> + break;
> + }
> + if (!compat_kind) {
> + pr_warn("kind incompatibility (%d != %d) between distilled base type '%s'[%d] and base type [%d]\n",
> + dist_kind, kind, name, *dist_id, id);
> + return -EINVAL;
> + }
> + }
> + /* validate that int, float struct, union sizes are compatible;
> + * distilled base BTF encodes an empty STRUCT/UNION with
> + * specific size for cases where a type is embedded in a split
> + * type (so has to preserve size info). Do not error out
> + * on mismatch as another size match may occur for an
> + * identically-named type.
> + */
> + switch (btf_kind(dist_t)) {
> + case BTF_KIND_INT:
Nit: INT is followed by u32 with additional information,
maybe that should be compared as well.
> + case BTF_KIND_FLOAT:
> + case BTF_KIND_STRUCT:
> + case BTF_KIND_UNION:
> + if (t->size == dist_t->size)
> + break;
> + continue;
> + default:
> + break;
> + }
> + r->map[*dist_id] = id;
> + }
> + /* ensure all distilled BTF ids have a mapping... */
> + for (id = 1; id < r->nr_dist_base_types; id++) {
> + t = btf_type_by_id(r->dist_base_btf, id);
> + name = btf__name_by_offset(r->dist_base_btf, t->name_off);
> + if (!r->map[id]) {
> + pr_warn("distilled base BTF type '%s' [%d] is not mapped to base BTF id\n",
> + name, id);
> + return -EINVAL;
> + }
Nit: maybe rewrite this like below?
if (r->map[id])
continue;
t = btf_type_by_id(r->dist_base_btf, id);
name = btf__name_by_offset(r->dist_base_btf, t->name_off);
pr_warn("distilled base BTF type '%s' [%d] is not mapped to base BTF id\n",
name, id);
> + }
> + return 0;
> +}
[...]
