Re: [PATCH v3 bpf-next 07/11] libbpf: split BTF relocation

[Eduard Zingerman <eddyz87@gmail.com>]

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;
> +}

[...]