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

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

[Andrii Nakryiko]

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

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

[Andrii Nakryiko]

On Thu, May 1, 2025 at 4:52 PM Andrii Nakryiko <andrii@kernel.org> 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

Forgot to mention that vmlinux BTF size itself didn't change at all.

> 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>
> ---
>  tools/lib/bpf/btf.c | 137 ++++++++++++++++++++++++++++----------------
>  1 file changed, 89 insertions(+), 48 deletions(-)
>

[...]

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

[Alan Maguire]

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

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

[Alexei Starovoitov]

On Fri, May 2, 2025 at 2:32 AM Alan Maguire <alan.maguire@oracle.com> wrote:
>
> >
> > 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.

I'm curious what BTF sizes you'll see.

Sounds like dwarf has more cases of "same type but different id"
than we expected.
So existing workarounds are working only because we have very
few modules that rely on proper dedup of kernel types.
Beyond array/struct/ptrs, I wonder, what else is there.

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

[Andrii Nakryiko]

On Fri, May 2, 2025 at 11:09 AM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Fri, May 2, 2025 at 2:32 AM Alan Maguire <alan.maguire@oracle.com> wrote:
> >
> > >
> > > 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.
>
> I'm curious what BTF sizes you'll see.
>
> Sounds like dwarf has more cases of "same type but different id"
> than we expected.
> So existing workarounds are working only because we have very
> few modules that rely on proper dedup of kernel types.
> Beyond array/struct/ptrs, I wonder, what else is there.

Well, turns out I screwed up the measurements. I thought that I used
libbpf version with Alan's patch applied as a baseline, but it turned
out it was libbpf without his patch. So all the measurements (41MB ->
5MB) are actually due to Alan's identical pointers fix. My patches
have no effect on module BTF sizes (which is good and a bit more
sensible, I should have double checked before submitting). So, if we
are going to apply the patch, it's probably better to just drop that
paragraph. Or I can send v2 with an adjusted commit message, whatever
is better.

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

[Alexei Starovoitov]

On Mon, May 5, 2025 at 2:10 PM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Fri, May 2, 2025 at 11:09 AM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> >
> > On Fri, May 2, 2025 at 2:32 AM Alan Maguire <alan.maguire@oracle.com> wrote:
> > >
> > > >
> > > > 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.
> >
> > I'm curious what BTF sizes you'll see.
> >
> > Sounds like dwarf has more cases of "same type but different id"
> > than we expected.
> > So existing workarounds are working only because we have very
> > few modules that rely on proper dedup of kernel types.
> > Beyond array/struct/ptrs, I wonder, what else is there.
>
> Well, turns out I screwed up the measurements. I thought that I used
> libbpf version with Alan's patch applied as a baseline, but it turned
> out it was libbpf without his patch. So all the measurements (41MB ->
> 5MB) are actually due to Alan's identical pointers fix. My patches
> have no effect on module BTF sizes (which is good and a bit more
> sensible, I should have double checked before submitting). So, if we
> are going to apply the patch, it's probably better to just drop that
> paragraph. Or I can send v2 with an adjusted commit message, whatever
> is better.

Dropped the paragraph while applying.
Thanks for double checking.

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

[patchwork-bot+netdevbpf]

Hello:

This patch was applied to bpf/bpf-next.git (master)
by Alexei Starovoitov <ast@kernel.org>:

On Thu,  1 May 2025 16:52:31 -0700 you 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.
> 
> [...]

Here is the summary with links:
  - [bpf-next] libbpf: improve BTF dedup handling of "identical" BTF types
    https://git.kernel.org/bpf/bpf-next/c/62e23f183839

You are awesome, thank you!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html

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

[Alan Maguire]

On 05/05/2025 22:10, Andrii Nakryiko wrote:
> On Fri, May 2, 2025 at 11:09 AM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
>>
>> On Fri, May 2, 2025 at 2:32 AM Alan Maguire <alan.maguire@oracle.com> wrote:
>>>
>>>>
>>>> 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.
>>
>> I'm curious what BTF sizes you'll see.
>>
>> Sounds like dwarf has more cases of "same type but different id"
>> than we expected.
>> So existing workarounds are working only because we have very
>> few modules that rely on proper dedup of kernel types.
>> Beyond array/struct/ptrs, I wonder, what else is there.
> 
> Well, turns out I screwed up the measurements. I thought that I used
> libbpf version with Alan's patch applied as a baseline, but it turned
> out it was libbpf without his patch. So all the measurements (41MB ->
> 5MB) are actually due to Alan's identical pointers fix. My patches
> have no effect on module BTF sizes (which is good and a bit more
> sensible, I should have double checked before submitting). So, if we
> are going to apply the patch, it's probably better to just drop that
> paragraph. Or I can send v2 with an adjusted commit message, whatever
> is better.
> 

I did see some small changes, so the fact that you've added additional
cases here definitely helps; with ~3000 modules built I got ~50Mb of
module BTF in total both before and after the change, but comparing the
results using latest pahole (with the pointer-specific fix) and your
change (the more general fix) we do see some size reductions:

$ find . -name '*.ko' -print |sort|xargs objdump -h --section=".BTF" >
/tmp/modout.base
$ awk '/file format/ { printf $1" " } / .BTF/ { print strtonum("0x" $3)
}'  /tmp/modout.base > /tmp/modout.base.sizes
# rebuild pahole with Andrii's change
$ rm vmlinux
$ make -j$(nproc)
$ find . -name '*.ko' -print |sort|xargs objdump -h --section=".BTF" >
/tmp/modout.test
$ awk '/file format/ { printf $1" " } /tmp/modout.test / .BTF/ { print
strtonum("0x" $3) }' > /tmp/modout.test.sizes

$ diff /tmp/modout.base.sizes /tmp/modout.test.sizes
198c198
< ./drivers/char/ipmi/ipmi_si.ko: 11575
---
> ./drivers/char/ipmi/ipmi_si.ko: 11539
1810c1810
< ./drivers/platform/x86/ideapad-laptop.ko: 7122
---
> ./drivers/platform/x86/ideapad-laptop.ko: 7086
1952c1952
< ./drivers/scsi/mpi3mr/mpi3mr.ko: 52625
---
> ./drivers/scsi/mpi3mr/mpi3mr.ko: 52589

So while numerically it isn't huge, it definitely validates the
principle of making the identical type handling less specific to the
cases we had encountered. If you want to resync libbpf github again I
can update the submodule commit in pahole. Thanks!

Alan

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

[Andrii Nakryiko]

On Tue, May 6, 2025 at 3:15 AM Alan Maguire <alan.maguire@oracle.com> wrote:
>
> On 05/05/2025 22:10, Andrii Nakryiko wrote:
> > On Fri, May 2, 2025 at 11:09 AM Alexei Starovoitov
> > <alexei.starovoitov@gmail.com> wrote:
> >>
> >> On Fri, May 2, 2025 at 2:32 AM Alan Maguire <alan.maguire@oracle.com> wrote:
> >>>
> >>>>
> >>>> 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.
> >>
> >> I'm curious what BTF sizes you'll see.
> >>
> >> Sounds like dwarf has more cases of "same type but different id"
> >> than we expected.
> >> So existing workarounds are working only because we have very
> >> few modules that rely on proper dedup of kernel types.
> >> Beyond array/struct/ptrs, I wonder, what else is there.
> >
> > Well, turns out I screwed up the measurements. I thought that I used
> > libbpf version with Alan's patch applied as a baseline, but it turned
> > out it was libbpf without his patch. So all the measurements (41MB ->
> > 5MB) are actually due to Alan's identical pointers fix. My patches
> > have no effect on module BTF sizes (which is good and a bit more
> > sensible, I should have double checked before submitting). So, if we
> > are going to apply the patch, it's probably better to just drop that
> > paragraph. Or I can send v2 with an adjusted commit message, whatever
> > is better.
> >
>
> I did see some small changes, so the fact that you've added additional
> cases here definitely helps; with ~3000 modules built I got ~50Mb of
> module BTF in total both before and after the change, but comparing the
> results using latest pahole (with the pointer-specific fix) and your
> change (the more general fix) we do see some size reductions:
>
> $ find . -name '*.ko' -print |sort|xargs objdump -h --section=".BTF" >
> /tmp/modout.base
> $ awk '/file format/ { printf $1" " } / .BTF/ { print strtonum("0x" $3)
> }'  /tmp/modout.base > /tmp/modout.base.sizes
> # rebuild pahole with Andrii's change
> $ rm vmlinux
> $ make -j$(nproc)
> $ find . -name '*.ko' -print |sort|xargs objdump -h --section=".BTF" >
> /tmp/modout.test
> $ awk '/file format/ { printf $1" " } /tmp/modout.test / .BTF/ { print
> strtonum("0x" $3) }' > /tmp/modout.test.sizes
>
> $ diff /tmp/modout.base.sizes /tmp/modout.test.sizes
> 198c198
> < ./drivers/char/ipmi/ipmi_si.ko: 11575
> ---
> > ./drivers/char/ipmi/ipmi_si.ko: 11539
> 1810c1810
> < ./drivers/platform/x86/ideapad-laptop.ko: 7122
> ---
> > ./drivers/platform/x86/ideapad-laptop.ko: 7086
> 1952c1952
> < ./drivers/scsi/mpi3mr/mpi3mr.ko: 52625
> ---
> > ./drivers/scsi/mpi3mr/mpi3mr.ko: 52589
>
> So while numerically it isn't huge, it definitely validates the
> principle of making the identical type handling less specific to the
> cases we had encountered. If you want to resync libbpf github again I
> can update the submodule commit in pahole. Thanks!

given how small the change in size is, it's probably const/volatile
PTR cases or something similar. Well, good to know it does make a bit
of a difference in some situations, thanks for confirming!

>
> Alan