Re: [PATCH bpf-next] libbpf: improve BTF dedup handling of "identical" BTF types

[Alan Maguire <alan.maguire@oracle.com>]

On 02/05/2025 00:52, Andrii Nakryiko wrote:
> BTF dedup has a strong assumption that compiler with deduplicate identical
> types within any given compilation unit (i.e., .c file). This property
> is used when establishing equilvalence of two subgraphs of types.
> 
> Unfortunately, this property doesn't always holds in practice. We've
> seen cases of having truly identical structs, unions, array definitions,
> and, most recently, even pointers to the same type being duplicated
> within CU.
> 
> Previously, we mitigated this on a case-by-case basis, adding a few
> simple heuristics for validating that two BTF types (having two
> different type IDs) are structurally the same. But this approach scales
> poorly, and we can have more weird cases come up in the future.
> 
> So let's take a half-step back, and implement a bit more generic
> structural equivalence check, recursively. We still limit it to
> reasonable depth to avoid long reference loops. Depth-wise limiting of
> potentially cyclical graph isn't great, but as I mentioned below doesn't
> seem to be detrimental performance-wise. We can always improve this in
> the future with per-type visited markers, if necessary.
> 
> Performance-wise this doesn't seem too affect vmlinux BTF dedup, which
> makes sense because this logic kicks in not so frequently and only if we
> already established a canonical candidate type match, but suddenly find
> a different (but probably identical) type.
> 
> On the other hand, this seems to help to reduce duplication across many
> kernel modules. In my local test, I had 639 kernel module built. Overall
> .BTF sections size goes down from 41MB bytes down to 5MB (!), which is
> pretty impressive for such a straightforward piece of logic added. But
> it would be nice to validate independently just in case my bash and
> Python-fu is broken.
> 
> Signed-off-by: Andrii Nakryiko <andrii@kernel.org>

Looks great!

Reviewed-by: Alan Maguire <alan.maguire@oracle.com>

Should have some numbers on the module size differences with this change
by Monday, had to dash before my build completed.

> ---
>  tools/lib/bpf/btf.c | 137 ++++++++++++++++++++++++++++----------------
>  1 file changed, 89 insertions(+), 48 deletions(-)
> 
> diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> index b7513d4cce55..f18d7e6a453c 100644
> --- a/tools/lib/bpf/btf.c
> +++ b/tools/lib/bpf/btf.c
> @@ -4356,59 +4356,109 @@ static inline __u16 btf_fwd_kind(struct btf_type *t)
>  	return btf_kflag(t) ? BTF_KIND_UNION : BTF_KIND_STRUCT;
>  }
>  
> -/* Check if given two types are identical ARRAY definitions */
> -static bool btf_dedup_identical_arrays(struct btf_dedup *d, __u32 id1, __u32 id2)
> +static bool btf_dedup_identical_types(struct btf_dedup *d, __u32 id1, __u32 id2, int depth)
>  {
>  	struct btf_type *t1, *t2;
> +	int k1, k2;
> +recur:
> +	if (depth <= 0)
> +		return false;
>  
>  	t1 = btf_type_by_id(d->btf, id1);
>  	t2 = btf_type_by_id(d->btf, id2);
> -	if (!btf_is_array(t1) || !btf_is_array(t2))
> +
> +	k1 = btf_kind(t1);
> +	k2 = btf_kind(t2);
> +	if (k1 != k2)
>  		return false;
>  
> -	return btf_equal_array(t1, t2);
> -}
> +	switch (k1) {
> +	case BTF_KIND_UNKN: /* VOID */
> +		return true;
> +	case BTF_KIND_INT:
> +		return btf_equal_int_tag(t1, t2);
> +	case BTF_KIND_ENUM:
> +	case BTF_KIND_ENUM64:
> +		return btf_compat_enum(t1, t2);
> +	case BTF_KIND_FWD:
> +	case BTF_KIND_FLOAT:
> +		return btf_equal_common(t1, t2);
> +	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_TYPE_TAG:
> +		if (t1->info != t2->info || t1->name_off != t2->name_off)
> +			return false;
> +		id1 = t1->type;> +		id2 = t2->type;
> +		goto recur;
> +	case BTF_KIND_ARRAY: {
> +		struct btf_array *a1, *a2;
>  
> -/* Check if given two types are identical STRUCT/UNION definitions */
> -static bool btf_dedup_identical_structs(struct btf_dedup *d, __u32 id1, __u32 id2)
> -{
> -	const struct btf_member *m1, *m2;
> -	struct btf_type *t1, *t2;
> -	int n, i;
> +		if (!btf_compat_array(t1, t2))
> +			return false;
>  
> -	t1 = btf_type_by_id(d->btf, id1);
> -	t2 = btf_type_by_id(d->btf, id2);
> +		a1 = btf_array(t1);
> +		a2 = btf_array(t1);
>  
> -	if (!btf_is_composite(t1) || btf_kind(t1) != btf_kind(t2))
> -		return false;
> +		if (a1->index_type != a2->index_type &&
> +		    !btf_dedup_identical_types(d, a1->index_type, a2->index_type, depth - 1))
> +			return false;
>  
> -	if (!btf_shallow_equal_struct(t1, t2))
> -		return false;
> +		if (a1->type != a2->type &&
> +		    !btf_dedup_identical_types(d, a1->type, a2->type, depth - 1))
> +			return false;
>  
> -	m1 = btf_members(t1);
> -	m2 = btf_members(t2);
> -	for (i = 0, n = btf_vlen(t1); i < n; i++, m1++, m2++) {
> -		if (m1->type != m2->type &&
> -		    !btf_dedup_identical_arrays(d, m1->type, m2->type) &&
> -		    !btf_dedup_identical_structs(d, m1->type, m2->type))
> +		return true;
> +	}
> +	case BTF_KIND_STRUCT:
> +	case BTF_KIND_UNION: {
> +		const struct btf_member *m1, *m2;
> +		int i, n;
> +
> +		if (!btf_shallow_equal_struct(t1, t2))
>  			return false;
> +
> +		m1 = btf_members(t1);
> +		m2 = btf_members(t2);
> +		for (i = 0, n = btf_vlen(t1); i < n; i++, m1++, m2++) {
> +			if (m1->type == m2->type)
> +				continue;
> +			if (!btf_dedup_identical_types(d, m1->type, m2->type, depth - 1))
> +				return false;
> +		}
> +		return true;
>  	}
> -	return true;
> -}
> +	case BTF_KIND_FUNC_PROTO: {
> +		const struct btf_param *p1, *p2;
> +		int i, n;
>  
> -static bool btf_dedup_identical_ptrs(struct btf_dedup *d, __u32 id1, __u32 id2)
> -{
> -	struct btf_type *t1, *t2;
> +		if (!btf_compat_fnproto(t1, t2))
> +			return false;
>  
> -	t1 = btf_type_by_id(d->btf, id1);
> -	t2 = btf_type_by_id(d->btf, id2);
> +		if (t1->type != t2->type &&
> +		    !btf_dedup_identical_types(d, t1->type, t2->type, depth - 1))
> +			return false;
>  
> -	if (!btf_is_ptr(t1) || !btf_is_ptr(t2))
> +		p1 = btf_params(t1);
> +		p2 = btf_params(t2);
> +		for (i = 0, n = btf_vlen(t1); i < n; i++, p1++, p2++) {
> +			if (p1->type == p2->type)
> +				continue;
> +			if (!btf_dedup_identical_types(d, p1->type, p2->type, depth - 1))
> +				return false;
> +		}
> +		return true;
> +	}
> +	default:
>  		return false;
> -
> -	return t1->type == t2->type;
> +	}
>  }
>  
> +
>  /*
>   * Check equivalence of BTF type graph formed by candidate struct/union (we'll
>   * call it "candidate graph" in this description for brevity) to a type graph
> @@ -4527,22 +4577,13 @@ static int btf_dedup_is_equiv(struct btf_dedup *d, __u32 cand_id,
>  		 * different fields within the *same* struct. This breaks type
>  		 * equivalence check, which makes an assumption that candidate
>  		 * types sub-graph has a consistent and deduped-by-compiler
> -		 * types within a single CU. So work around that by explicitly
> -		 * allowing identical array types here.
> +		 * types within a single CU. And similar situation can happen
> +		 * with struct/union sometimes, and event with pointers.
> +		 * So accommodate cases like this doing a structural
> +		 * comparison recursively, but avoiding being stuck in endless
> +		 * loops by limiting the depth up to which we check.
>  		 */
> -		if (btf_dedup_identical_arrays(d, hypot_type_id, cand_id))
> -			return 1;
> -		/* It turns out that similar situation can happen with
> -		 * struct/union sometimes, sigh... Handle the case where
> -		 * structs/unions are exactly the same, down to the referenced
> -		 * type IDs. Anything more complicated (e.g., if referenced
> -		 * types are different, but equivalent) is *way more*
> -		 * complicated and requires a many-to-many equivalence mapping.
> -		 */
> -		if (btf_dedup_identical_structs(d, hypot_type_id, cand_id))
> -			return 1;
> -		/* A similar case is again observed for PTRs. */
> -		if (btf_dedup_identical_ptrs(d, hypot_type_id, cand_id))
> +		if (btf_dedup_identical_types(d, hypot_type_id, cand_id, 16))
>  			return 1;
>  		return 0;
>  	}