Skip to contentSkip to conversation

libbpf: accommodate DWARF/compiler bug with duplicated structs

PATCH Applied Andrii Nakryiko 4 participants 11 messages Nov 17, 2021 – Nov 24, 2021

Subsystems (4)
lore
Share & tools
lore

Andrii Nakryiko

author maintainer
#0 lore raw

PATCH 1/2 libbpf: accommodate DWARF/compiler bug with duplicated structs

According to [0], compilers sometimes might produce duplicate DWARF definitions for exactly the same struct/union within the same compilation unit (CU). We've had similar issues with identical arrays and handled them with a similar workaround in 6b6e6b1d09aa ("libbpf:
Accomodate DWARF/compiler bug with duplicated identical arrays"). Do the same for struct/union by ensuring that two structs/unions are exactly the same, down to the integer values of field referenced type IDs.

Solving this more generically (allowing referenced types to be equivalent, but using different type IDs, all within a single CU) requires a huge complexity increase to handle many-to-many mappings between canonidal and candidate type graphs. Before we invest in that, let's see if this approach handles all the instances of this issue in practice. Thankfully it's pretty rare, it seems.

[0] https://lore.kernel.org/bpf/YXr2NFlJTAhHdZqq@krava/

---
 tools/lib/bpf/btf.c | 45 +++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 41 insertions(+), 4 deletions(-)
tools/lib/bpf/btf.c +41 -4
index b6be579e0dc6..e97217a77196 100644
@@ -3477,8 +3477,8 @@ static long btf_hash_struct(struct btf_type *t)
 }
 
 /*
- * Check structural compatibility of two FUNC_PROTOs, ignoring referenced type
- * IDs. This check is performed during type graph equivalence check and
+ * Check structural compatibility of two STRUCTs/UNIONs, ignoring referenced
+ * type IDs. This check is performed during type graph equivalence check and
  * referenced types equivalence is checked separately.
  */
 static bool btf_shallow_equal_struct(struct btf_type *t1, struct btf_type *t2)
@@ -3851,6 +3851,31 @@ static int btf_dedup_identical_arrays(struct btf_dedup *d, __u32 id1, __u32 id2)
 	return btf_equal_array(t1, t2);
 }
 
+/* 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;
+
+	t1 = btf_type_by_id(d->btf, id1);
+	t2 = btf_type_by_id(d->btf, id2);
+
+	if (!btf_is_composite(t1) || btf_kind(t1) != btf_kind(t2))
+		return false;
+
+	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)
+			return false;
+	}
+	return true;
+}
+
 /*
  * 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
@@ -3962,6 +3987,8 @@ static int btf_dedup_is_equiv(struct btf_dedup *d, __u32 cand_id,
 
 	hypot_type_id = d->hypot_map[canon_id];
 	if (hypot_type_id <= BTF_MAX_NR_TYPES) {
+		if (hypot_type_id == cand_id)
+			return 1;
 		/* In some cases compiler will generate different DWARF types
 		 * for *identical* array type definitions and use them for
 		 * different fields within the *same* struct. This breaks type
@@ -3970,8 +3997,18 @@ static int btf_dedup_is_equiv(struct btf_dedup *d, __u32 cand_id,
 		 * types within a single CU. So work around that by explicitly
 		 * allowing identical array types here.
 		 */
-		return hypot_type_id == cand_id ||
-		       btf_dedup_identical_arrays(d, hypot_type_id, cand_id);
+		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;
+		return 0;
 	}
 
 	if (btf_dedup_hypot_map_add(d, canon_id, cand_id))
Signature · 1 line
2.30.2
author maintainer
#1 lore raw

PATCH 2/2 selftests/bpf: add btf_dedup case with duplicated structs within CU

From: Jiri Olsa <[email protected]>

Add an artificial minimal example simulating compilers producing two different types within a single CU that correspond to identical struct definitions.

---
 .../bpf/prog_tests/btf_dedup_split.c          | 113 ++++++++++++++++++
 1 file changed, 113 insertions(+)
tools/testing/selftests/bpf/prog_tests/btf_dedup_split.c +113 -0
index 9d3b8d7a1537..94ff9757557a 100644
@@ -314,6 +314,117 @@ static void test_split_struct_duped() {
 	btf__free(btf1);
 }
 
+static void btf_add_dup_struct_in_cu(struct btf *btf, int start_id)
+{
+#define ID(n) (start_id + n)
+	btf__set_pointer_size(btf, 8); /* enforce 64-bit arch */
+
+	btf__add_int(btf, "int", 4, BTF_INT_SIGNED);    /* [1] int */
+
+	btf__add_struct(btf, "s", 8);                   /* [2] struct s { */
+	btf__add_field(btf, "a", ID(3), 0, 0);          /*      struct anon a; */
+	btf__add_field(btf, "b", ID(4), 0, 0);          /*      struct anon b; */
+							/* } */
+
+	btf__add_struct(btf, "(anon)", 8);              /* [3] struct anon { */
+	btf__add_field(btf, "f1", ID(1), 0, 0);         /*      int f1; */
+	btf__add_field(btf, "f2", ID(1), 32, 0);        /*      int f2; */
+							/* } */
+
+	btf__add_struct(btf, "(anon)", 8);              /* [4] struct anon { */
+	btf__add_field(btf, "f1", ID(1), 0, 0);         /*      int f1; */
+	btf__add_field(btf, "f2", ID(1), 32, 0);        /*      int f2; */
+							/* } */
+#undef ID
+}
+
+static void test_split_dup_struct_in_cu()
+{
+	struct btf *btf1, *btf2;
+	int err;
+
+	/* generate the base data.. */
+	btf1 = btf__new_empty();
+	if (!ASSERT_OK_PTR(btf1, "empty_main_btf"))
+		return;
+
+	btf_add_dup_struct_in_cu(btf1, 0);
+
+	VALIDATE_RAW_BTF(
+			btf1,
+			"[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
+			"[2] STRUCT 's' size=8 vlen=2\n"
+			"\t'a' type_id=3 bits_offset=0\n"
+			"\t'b' type_id=4 bits_offset=0",
+			"[3] STRUCT '(anon)' size=8 vlen=2\n"
+			"\t'f1' type_id=1 bits_offset=0\n"
+			"\t'f2' type_id=1 bits_offset=32",
+			"[4] STRUCT '(anon)' size=8 vlen=2\n"
+			"\t'f1' type_id=1 bits_offset=0\n"
+			"\t'f2' type_id=1 bits_offset=32");
+
+	/* ..dedup them... */
+	err = btf__dedup(btf1, NULL, NULL);
+	if (!ASSERT_OK(err, "btf_dedup"))
+		goto cleanup;
+
+	VALIDATE_RAW_BTF(
+			btf1,
+			"[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
+			"[2] STRUCT 's' size=8 vlen=2\n"
+			"\t'a' type_id=3 bits_offset=0\n"
+			"\t'b' type_id=3 bits_offset=0",
+			"[3] STRUCT '(anon)' size=8 vlen=2\n"
+			"\t'f1' type_id=1 bits_offset=0\n"
+			"\t'f2' type_id=1 bits_offset=32");
+
+	/* and add the same data on top of it */
+	btf2 = btf__new_empty_split(btf1);
+	if (!ASSERT_OK_PTR(btf2, "empty_split_btf"))
+		goto cleanup;
+
+	btf_add_dup_struct_in_cu(btf2, 3);
+
+	VALIDATE_RAW_BTF(
+			btf2,
+			"[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
+			"[2] STRUCT 's' size=8 vlen=2\n"
+			"\t'a' type_id=3 bits_offset=0\n"
+			"\t'b' type_id=3 bits_offset=0",
+			"[3] STRUCT '(anon)' size=8 vlen=2\n"
+			"\t'f1' type_id=1 bits_offset=0\n"
+			"\t'f2' type_id=1 bits_offset=32",
+			"[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
+			"[5] STRUCT 's' size=8 vlen=2\n"
+			"\t'a' type_id=6 bits_offset=0\n"
+			"\t'b' type_id=7 bits_offset=0",
+			"[6] STRUCT '(anon)' size=8 vlen=2\n"
+			"\t'f1' type_id=4 bits_offset=0\n"
+			"\t'f2' type_id=4 bits_offset=32",
+			"[7] STRUCT '(anon)' size=8 vlen=2\n"
+			"\t'f1' type_id=4 bits_offset=0\n"
+			"\t'f2' type_id=4 bits_offset=32");
+
+	err = btf__dedup(btf2, NULL, NULL);
+	if (!ASSERT_OK(err, "btf_dedup"))
+		goto cleanup;
+
+	/* after dedup it should match the original data */
+	VALIDATE_RAW_BTF(
+			btf2,
+			"[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
+			"[2] STRUCT 's' size=8 vlen=2\n"
+			"\t'a' type_id=3 bits_offset=0\n"
+			"\t'b' type_id=3 bits_offset=0",
+			"[3] STRUCT '(anon)' size=8 vlen=2\n"
+			"\t'f1' type_id=1 bits_offset=0\n"
+			"\t'f2' type_id=1 bits_offset=32");
+
+cleanup:
+	btf__free(btf2);
+	btf__free(btf1);
+}
+
 void test_btf_dedup_split()
 {
 	if (test__start_subtest("split_simple"))
@@ -322,4 +433,6 @@ void test_btf_dedup_split()
 		test_split_struct_duped();
 	if (test__start_subtest("split_fwd_resolve"))
 		test_split_fwd_resolve();
+	if (test__start_subtest("split_dup_struct_in_cu"))
+		test_split_dup_struct_in_cu();
 }
Signature · 1 line
2.30.2
#2 lore raw
In reply to Andrii Nakryiko
Quoted 8 lines · Andrii Nakryiko

According to [0], compilers sometimes might produce duplicate DWARF definitions for exactly the same struct/union within the same compilation unit (CU). We've had similar issues with identical arrays and handled them with a similar workaround in 6b6e6b1d09aa ("libbpf:
Accomodate DWARF/compiler bug with duplicated identical arrays"). Do the same for struct/union by ensuring that two structs/unions are exactly the same, down to the integer values of field referenced type IDs.

Jiri, can you please try this in your setup and see if that handles all situations or there are more complicated ones still. We'll need a test for more complicated ones in that case :( Thanks.

Quoted 96 lines

Solving this more generically (allowing referenced types to be equivalent, but using different type IDs, all within a single CU) requires a huge complexity increase to handle many-to-many mappings between canonidal and candidate type graphs. Before we invest in that, let's see if this approach handles all the instances of this issue in practice. Thankfully it's pretty rare, it seems.

[0] https://lore.kernel.org/bpf/YXr2NFlJTAhHdZqq@krava/

---
 tools/lib/bpf/btf.c | 45 +++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 41 insertions(+), 4 deletions(-)
tools/lib/bpf/btf.c +41 -5
index b6be579e0dc6..e97217a77196 100644
@@ -3477,8 +3477,8 @@ static long btf_hash_struct(struct btf_type *t)
 }
 
 /*
- * Check structural compatibility of two FUNC_PROTOs, ignoring referenced type
- * IDs. This check is performed during type graph equivalence check and
+ * Check structural compatibility of two STRUCTs/UNIONs, ignoring referenced
+ * type IDs. This check is performed during type graph equivalence check and
  * referenced types equivalence is checked separately.
  */
 static bool btf_shallow_equal_struct(struct btf_type *t1, struct btf_type *t2)
@@ -3851,6 +3851,31 @@ static int btf_dedup_identical_arrays(struct btf_dedup *d, __u32 id1, __u32 id2)
        return btf_equal_array(t1, t2);
 }
 
+/* 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;
+
+       t1 = btf_type_by_id(d->btf, id1);
+       t2 = btf_type_by_id(d->btf, id2);
+
+       if (!btf_is_composite(t1) || btf_kind(t1) != btf_kind(t2))
+               return false;
+
+       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)
+                       return false;
+       }
+       return true;
+}
+
 /*
  * 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
@@ -3962,6 +3987,8 @@ static int btf_dedup_is_equiv(struct btf_dedup *d, __u32 cand_id,
 
        hypot_type_id = d->hypot_map[canon_id];
        if (hypot_type_id <= BTF_MAX_NR_TYPES) {
+               if (hypot_type_id == cand_id)
+                       return 1;
                /* In some cases compiler will generate different DWARF types
                 * for *identical* array type definitions and use them for
                 * different fields within the *same* struct. This breaks type
@@ -3970,8 +3997,18 @@ static int btf_dedup_is_equiv(struct btf_dedup *d, __u32 cand_id,
                 * types within a single CU. So work around that by explicitly
                 * allowing identical array types here.
                 */
-               return hypot_type_id == cand_id ||
-                      btf_dedup_identical_arrays(d, hypot_type_id, cand_id);
+               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;
+               return 0;
        }
 
        if (btf_dedup_hypot_map_add(d, canon_id, cand_id))
--

2.30.2

#3 lore raw
Quoted 10 lines · Andrii Nakryiko
Quoted 8 lines · Andrii Nakryiko

According to [0], compilers sometimes might produce duplicate DWARF definitions for exactly the same struct/union within the same compilation unit (CU). We've had similar issues with identical arrays and handled them with a similar workaround in 6b6e6b1d09aa ("libbpf:
Accomodate DWARF/compiler bug with duplicated identical arrays"). Do the same for struct/union by ensuring that two structs/unions are exactly the same, down to the integer values of field referenced type IDs.

Quoted 3 lines

Jiri, can you please try this in your setup and see if that handles all situations or there are more complicated ones still. We'll need a test for more complicated ones in that case :( Thanks.

it seems to help largely, but I still see few modules (67 out of 780) that keep 'struct module' for some reason.. their struct module looks completely the same as is in vmlinux

I uploaded one of the module with vmlinux in here:
http://people.redhat.com/~jolsa/kmodbtf/2/

I will do some debugging and find out why it did not work in this module and try to come up with another test

thanks,
jirka

Quoted 98 lines
Quoted 97 lines

Solving this more generically (allowing referenced types to be equivalent, but using different type IDs, all within a single CU) requires a huge complexity increase to handle many-to-many mappings between canonidal and candidate type graphs. Before we invest in that, let's see if this approach handles all the instances of this issue in practice. Thankfully it's pretty rare, it seems.

[0] https://lore.kernel.org/bpf/YXr2NFlJTAhHdZqq@krava/

---
 tools/lib/bpf/btf.c | 45 +++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 41 insertions(+), 4 deletions(-)
tools/lib/bpf/btf.c +41 -5
index b6be579e0dc6..e97217a77196 100644
@@ -3477,8 +3477,8 @@ static long btf_hash_struct(struct btf_type *t)
 }
 
 /*
- * Check structural compatibility of two FUNC_PROTOs, ignoring referenced type
- * IDs. This check is performed during type graph equivalence check and
+ * Check structural compatibility of two STRUCTs/UNIONs, ignoring referenced
+ * type IDs. This check is performed during type graph equivalence check and
  * referenced types equivalence is checked separately.
  */
 static bool btf_shallow_equal_struct(struct btf_type *t1, struct btf_type *t2)
@@ -3851,6 +3851,31 @@ static int btf_dedup_identical_arrays(struct btf_dedup *d, __u32 id1, __u32 id2)
        return btf_equal_array(t1, t2);
 }
 
+/* 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;
+
+       t1 = btf_type_by_id(d->btf, id1);
+       t2 = btf_type_by_id(d->btf, id2);
+
+       if (!btf_is_composite(t1) || btf_kind(t1) != btf_kind(t2))
+               return false;
+
+       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)
+                       return false;
+       }
+       return true;
+}
+
 /*
  * 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
@@ -3962,6 +3987,8 @@ static int btf_dedup_is_equiv(struct btf_dedup *d, __u32 cand_id,
 
        hypot_type_id = d->hypot_map[canon_id];
        if (hypot_type_id <= BTF_MAX_NR_TYPES) {
+               if (hypot_type_id == cand_id)
+                       return 1;
                /* In some cases compiler will generate different DWARF types
                 * for *identical* array type definitions and use them for
                 * different fields within the *same* struct. This breaks type
@@ -3970,8 +3997,18 @@ static int btf_dedup_is_equiv(struct btf_dedup *d, __u32 cand_id,
                 * types within a single CU. So work around that by explicitly
                 * allowing identical array types here.
                 */
-               return hypot_type_id == cand_id ||
-                      btf_dedup_identical_arrays(d, hypot_type_id, cand_id);
+               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;
+               return 0;
        }
 
        if (btf_dedup_hypot_map_add(d, canon_id, cand_id))
--

2.30.2

#4 lore raw
Quoted 12 lines · Jiri Olsa
Quoted 10 lines · Andrii Nakryiko
Quoted 8 lines · Andrii Nakryiko

According to [0], compilers sometimes might produce duplicate DWARF definitions for exactly the same struct/union within the same compilation unit (CU). We've had similar issues with identical arrays and handled them with a similar workaround in 6b6e6b1d09aa ("libbpf:
Accomodate DWARF/compiler bug with duplicated identical arrays"). Do the same for struct/union by ensuring that two structs/unions are exactly the same, down to the integer values of field referenced type IDs.

Quoted 7 lines
Quoted 3 lines

Jiri, can you please try this in your setup and see if that handles all situations or there are more complicated ones still. We'll need a test for more complicated ones in that case :( Thanks.

it seems to help largely, but I still see few modules (67 out of 780) that keep 'struct module' for some reason.. their struct module looks completely the same as is in vmlinux

Curious, what's the size of all the module BTFs now? And yes, please try to narrow down what is causing the bloat this time. I think this change can go in anyways, it's conceptually the same as a workaround for duplicate arrays produced by the compiler.

Quoted 109 lines

I uploaded one of the module with vmlinux in here:
http://people.redhat.com/~jolsa/kmodbtf/2/

I will do some debugging and find out why it did not work in this module and try to come up with another test

thanks,
jirka

Quoted 98 lines
Quoted 97 lines

Solving this more generically (allowing referenced types to be equivalent, but using different type IDs, all within a single CU) requires a huge complexity increase to handle many-to-many mappings between canonidal and candidate type graphs. Before we invest in that, let's see if this approach handles all the instances of this issue in practice. Thankfully it's pretty rare, it seems.

[0] https://lore.kernel.org/bpf/YXr2NFlJTAhHdZqq@krava/

---
 tools/lib/bpf/btf.c | 45 +++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 41 insertions(+), 4 deletions(-)
tools/lib/bpf/btf.c +41 -5
index b6be579e0dc6..e97217a77196 100644
@@ -3477,8 +3477,8 @@ static long btf_hash_struct(struct btf_type *t)
 }
 
 /*
- * Check structural compatibility of two FUNC_PROTOs, ignoring referenced type
- * IDs. This check is performed during type graph equivalence check and
+ * Check structural compatibility of two STRUCTs/UNIONs, ignoring referenced
+ * type IDs. This check is performed during type graph equivalence check and
  * referenced types equivalence is checked separately.
  */
 static bool btf_shallow_equal_struct(struct btf_type *t1, struct btf_type *t2)
@@ -3851,6 +3851,31 @@ static int btf_dedup_identical_arrays(struct btf_dedup *d, __u32 id1, __u32 id2)
        return btf_equal_array(t1, t2);
 }
 
+/* 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;
+
+       t1 = btf_type_by_id(d->btf, id1);
+       t2 = btf_type_by_id(d->btf, id2);
+
+       if (!btf_is_composite(t1) || btf_kind(t1) != btf_kind(t2))
+               return false;
+
+       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)
+                       return false;
+       }
+       return true;
+}
+
 /*
  * 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
@@ -3962,6 +3987,8 @@ static int btf_dedup_is_equiv(struct btf_dedup *d, __u32 cand_id,
 
        hypot_type_id = d->hypot_map[canon_id];
        if (hypot_type_id <= BTF_MAX_NR_TYPES) {
+               if (hypot_type_id == cand_id)
+                       return 1;
                /* In some cases compiler will generate different DWARF types
                 * for *identical* array type definitions and use them for
                 * different fields within the *same* struct. This breaks type
@@ -3970,8 +3997,18 @@ static int btf_dedup_is_equiv(struct btf_dedup *d, __u32 cand_id,
                 * types within a single CU. So work around that by explicitly
                 * allowing identical array types here.
                 */
-               return hypot_type_id == cand_id ||
-                      btf_dedup_identical_arrays(d, hypot_type_id, cand_id);
+               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;
+               return 0;
        }
 
        if (btf_dedup_hypot_map_add(d, canon_id, cand_id))
--

2.30.2

#5 lore raw
Quoted 17 lines · Andrii Nakryiko
Quoted 16 lines · Jiri Olsa
Quoted 13 lines · Andrii Nakryiko
Quoted 8 lines · Andrii Nakryiko

According to [0], compilers sometimes might produce duplicate DWARF definitions for exactly the same struct/union within the same compilation unit (CU). We've had similar issues with identical arrays and handled them with a similar workaround in 6b6e6b1d09aa ("libbpf:
Accomodate DWARF/compiler bug with duplicated identical arrays"). Do the same for struct/union by ensuring that two structs/unions are exactly the same, down to the integer values of field referenced type IDs.

Jiri, can you please try this in your setup and see if that handles all situations or there are more complicated ones still. We'll need a test for more complicated ones in that case :( Thanks.

Quoted 5 lines
Quoted 3 lines

it seems to help largely, but I still see few modules (67 out of 780) that keep 'struct module' for some reason.. their struct module looks completely the same as is in vmlinux

Curious, what's the size of all the module BTFs now?

sorry for delay, I was waiting for s390x server

so with 'current' fedora kernel rawhide I'm getting slightly different total size number than before, so something has changed after the merge window..

however the increase with BTF enabled in modules is now from 16M to 18M, so the BTF data adds just about 2M, which I think we can live with

Quoted 2 lines

And yes, please
try to narrow down what is causing the bloat this time. I think this

I'm on it

Quoted 2 lines

change can go in anyways, it's conceptually the same as a workaround for duplicate arrays produced by the compiler.

yes, thanks
jirka

Quoted 111 lines
Quoted 110 lines

I uploaded one of the module with vmlinux in here:
http://people.redhat.com/~jolsa/kmodbtf/2/

I will do some debugging and find out why it did not work in this module and try to come up with another test

thanks,
jirka

Quoted 98 lines
Quoted 97 lines

Solving this more generically (allowing referenced types to be equivalent, but using different type IDs, all within a single CU) requires a huge complexity increase to handle many-to-many mappings between canonidal and candidate type graphs. Before we invest in that, let's see if this approach handles all the instances of this issue in practice. Thankfully it's pretty rare, it seems.

[0] https://lore.kernel.org/bpf/YXr2NFlJTAhHdZqq@krava/

---
 tools/lib/bpf/btf.c | 45 +++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 41 insertions(+), 4 deletions(-)
tools/lib/bpf/btf.c +41 -5
index b6be579e0dc6..e97217a77196 100644
@@ -3477,8 +3477,8 @@ static long btf_hash_struct(struct btf_type *t)
 }
 
 /*
- * Check structural compatibility of two FUNC_PROTOs, ignoring referenced type
- * IDs. This check is performed during type graph equivalence check and
+ * Check structural compatibility of two STRUCTs/UNIONs, ignoring referenced
+ * type IDs. This check is performed during type graph equivalence check and
  * referenced types equivalence is checked separately.
  */
 static bool btf_shallow_equal_struct(struct btf_type *t1, struct btf_type *t2)
@@ -3851,6 +3851,31 @@ static int btf_dedup_identical_arrays(struct btf_dedup *d, __u32 id1, __u32 id2)
        return btf_equal_array(t1, t2);
 }
 
+/* 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;
+
+       t1 = btf_type_by_id(d->btf, id1);
+       t2 = btf_type_by_id(d->btf, id2);
+
+       if (!btf_is_composite(t1) || btf_kind(t1) != btf_kind(t2))
+               return false;
+
+       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)
+                       return false;
+       }
+       return true;
+}
+
 /*
  * 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
@@ -3962,6 +3987,8 @@ static int btf_dedup_is_equiv(struct btf_dedup *d, __u32 cand_id,
 
        hypot_type_id = d->hypot_map[canon_id];
        if (hypot_type_id <= BTF_MAX_NR_TYPES) {
+               if (hypot_type_id == cand_id)
+                       return 1;
                /* In some cases compiler will generate different DWARF types
                 * for *identical* array type definitions and use them for
                 * different fields within the *same* struct. This breaks type
@@ -3970,8 +3997,18 @@ static int btf_dedup_is_equiv(struct btf_dedup *d, __u32 cand_id,
                 * types within a single CU. So work around that by explicitly
                 * allowing identical array types here.
                 */
-               return hypot_type_id == cand_id ||
-                      btf_dedup_identical_arrays(d, hypot_type_id, cand_id);
+               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;
+               return 0;
        }
 
        if (btf_dedup_hypot_map_add(d, canon_id, cand_id))
--

2.30.2

#6 lore raw
Quoted 30 lines · Jiri Olsa
Quoted 17 lines · Andrii Nakryiko
Quoted 16 lines · Jiri Olsa
Quoted 13 lines · Andrii Nakryiko
Quoted 8 lines · Andrii Nakryiko

According to [0], compilers sometimes might produce duplicate DWARF definitions for exactly the same struct/union within the same compilation unit (CU). We've had similar issues with identical arrays and handled them with a similar workaround in 6b6e6b1d09aa ("libbpf:
Accomodate DWARF/compiler bug with duplicated identical arrays"). Do the same for struct/union by ensuring that two structs/unions are exactly the same, down to the integer values of field referenced type IDs.

Jiri, can you please try this in your setup and see if that handles all situations or there are more complicated ones still. We'll need a test for more complicated ones in that case :( Thanks.

Quoted 5 lines
Quoted 3 lines

it seems to help largely, but I still see few modules (67 out of 780) that keep 'struct module' for some reason.. their struct module looks completely the same as is in vmlinux

Curious, what's the size of all the module BTFs now?

sorry for delay, I was waiting for s390x server

so with 'current' fedora kernel rawhide I'm getting slightly different total size number than before, so something has changed after the merge window..

Quoted 7 lines

however the increase with BTF enabled in modules is now from 16M to 18M, so the BTF data adds just about 2M, which I think we can live with

Quoted 2 lines

And yes, please
try to narrow down what is causing the bloat this time. I think this

I'm on it

I'm seeing vmlinux BTF having just FWD record for sctp_mib struct, while the kernel module has the full definition

kernel:

        [2798] STRUCT 'netns_sctp' size=296 vlen=46
                'sctp_statistics' type_id=2800 bits_offset=0

        [2799] FWD 'sctp_mib' fwd_kind=struct
        [2800] PTR '(anon)' type_id=2799

module before dedup:

        [78928] STRUCT 'netns_sctp' size=296 vlen=46
                'sctp_statistics' type_id=78930 bits_offset=0

        [78929] STRUCT 'sctp_mib' size=272 vlen=1
                'mibs' type_id=80518 bits_offset=0
        [78930] PTR '(anon)' type_id=78929

this field is referenced from within 'struct module' so it won't match its kernel version and as a result extra 'struct module' stays in the module's BTF

I'll need to check debuginfo/pahole if that FWD is correct, but I guess it's normal that some structs might end up unwinded only in modules and not necessarily in vmlinux

jirka

#7 lore raw
Quoted 28 lines · Jiri Olsa
Quoted 26 lines · Jiri Olsa
Quoted 17 lines · Andrii Nakryiko
Quoted 16 lines · Jiri Olsa
Quoted 13 lines · Andrii Nakryiko
Quoted 8 lines · Andrii Nakryiko

According to [0], compilers sometimes might produce duplicate DWARF definitions for exactly the same struct/union within the same compilation unit (CU). We've had similar issues with identical arrays and handled them with a similar workaround in 6b6e6b1d09aa ("libbpf:
Accomodate DWARF/compiler bug with duplicated identical arrays"). Do the same for struct/union by ensuring that two structs/unions are exactly the same, down to the integer values of field referenced type IDs.

Jiri, can you please try this in your setup and see if that handles all situations or there are more complicated ones still. We'll need a test for more complicated ones in that case :( Thanks.

Quoted 5 lines
Quoted 3 lines

it seems to help largely, but I still see few modules (67 out of 780) that keep 'struct module' for some reason.. their struct module looks completely the same as is in vmlinux

Curious, what's the size of all the module BTFs now?

sorry for delay, I was waiting for s390x server

Quoted 7 lines
Quoted 7 lines

so with 'current' fedora kernel rawhide I'm getting slightly different total size number than before, so something has changed after the merge window..

however the increase with BTF enabled in modules is now from 16M to 18M, so the BTF data adds just about 2M, which I think we can live with

16MB for vmlinux BTF is quite a lot. Is it a allmodyesconfig or something?

Quoted 27 lines
Quoted 4 lines
Quoted 2 lines

And yes, please
try to narrow down what is causing the bloat this time. I think this

I'm on it

I'm seeing vmlinux BTF having just FWD record for sctp_mib struct, while the kernel module has the full definition

kernel:

        [2798] STRUCT 'netns_sctp' size=296 vlen=46
                'sctp_statistics' type_id=2800 bits_offset=0

        [2799] FWD 'sctp_mib' fwd_kind=struct
        [2800] PTR '(anon)' type_id=2799

module before dedup:

        [78928] STRUCT 'netns_sctp' size=296 vlen=46
                'sctp_statistics' type_id=78930 bits_offset=0

        [78929] STRUCT 'sctp_mib' size=272 vlen=1
                'mibs' type_id=80518 bits_offset=0
        [78930] PTR '(anon)' type_id=78929
Quoted 4 lines

this field is referenced from within 'struct module' so it won't match its kernel version and as a result extra 'struct module' stays in the module's BTF

Yeah, not much we could do about that short of just blindly matching FWD to STRUCT/UNION/ENUM by name, which sounds bad to me, I avoided doing that in BTF dedup algorithm. We only resolve FWD to STRUCT/UNION/ENUM when we have some containing struct with a field that points to FWD and (in another instance of the containing struct) to STRUCT/UNION/ENUM. That way we have sort of a proof that we are resolving the right FWD. While in this case it would be a blind guess based on name alone.

Quoted 3 lines

I'll need to check debuginfo/pahole if that FWD is correct, but I guess it's normal that some structs might end up unwinded only in modules and not necessarily in vmlinux

It can happen, yes. If that's a very common case, ideally we should make sure that modules keep FWD or that vmlinux BTF does have a full struct instead of FWD.

Quoted 3 lines

jirka

#8 lore raw
Quoted 33 lines · Andrii Nakryiko
Quoted 32 lines · Jiri Olsa
Quoted 30 lines · Jiri Olsa
Quoted 17 lines · Andrii Nakryiko
Quoted 16 lines · Jiri Olsa
Quoted 13 lines · Andrii Nakryiko
Quoted 8 lines · Andrii Nakryiko

According to [0], compilers sometimes might produce duplicate DWARF definitions for exactly the same struct/union within the same compilation unit (CU). We've had similar issues with identical arrays and handled them with a similar workaround in 6b6e6b1d09aa ("libbpf:
Accomodate DWARF/compiler bug with duplicated identical arrays"). Do the same for struct/union by ensuring that two structs/unions are exactly the same, down to the integer values of field referenced type IDs.

Jiri, can you please try this in your setup and see if that handles all situations or there are more complicated ones still. We'll need a test for more complicated ones in that case :( Thanks.

Quoted 5 lines
Quoted 3 lines

it seems to help largely, but I still see few modules (67 out of 780) that keep 'struct module' for some reason.. their struct module looks completely the same as is in vmlinux

Curious, what's the size of all the module BTFs now?

sorry for delay, I was waiting for s390x server

so with 'current' fedora kernel rawhide I'm getting slightly different total size number than before, so something has changed after the merge window..

Quoted 5 lines
Quoted 3 lines
Quoted 3 lines

however the increase with BTF enabled in modules is now from 16M to 18M, so the BTF data adds just about 2M, which I think we can live with

16MB for vmlinux BTF is quite a lot. Is it a allmodyesconfig or something?

looks like my english betrayed me again.. sry ;-)

size of all modules without BTF is 16M,
size of all modules with BTF is 18M,

so it's overall 2M increase

also note that each module is compressed with xz

jirka

Quoted 55 lines
Quoted 28 lines
Quoted 5 lines
Quoted 3 lines

And yes, please
try to narrow down what is causing the bloat this time. I think this

I'm on it

I'm seeing vmlinux BTF having just FWD record for sctp_mib struct, while the kernel module has the full definition

kernel:

        [2798] STRUCT 'netns_sctp' size=296 vlen=46
                'sctp_statistics' type_id=2800 bits_offset=0

        [2799] FWD 'sctp_mib' fwd_kind=struct
        [2800] PTR '(anon)' type_id=2799

module before dedup:

        [78928] STRUCT 'netns_sctp' size=296 vlen=46
                'sctp_statistics' type_id=78930 bits_offset=0

        [78929] STRUCT 'sctp_mib' size=272 vlen=1
                'mibs' type_id=80518 bits_offset=0
        [78930] PTR '(anon)' type_id=78929
Quoted 4 lines

this field is referenced from within 'struct module' so it won't match its kernel version and as a result extra 'struct module' stays in the module's BTF

Yeah, not much we could do about that short of just blindly matching FWD to STRUCT/UNION/ENUM by name, which sounds bad to me, I avoided doing that in BTF dedup algorithm. We only resolve FWD to STRUCT/UNION/ENUM when we have some containing struct with a field that points to FWD and (in another instance of the containing struct) to STRUCT/UNION/ENUM. That way we have sort of a proof that we are resolving the right FWD. While in this case it would be a blind guess based on name alone.

Quoted 3 lines

I'll need to check debuginfo/pahole if that FWD is correct, but I guess it's normal that some structs might end up unwinded only in modules and not necessarily in vmlinux

It can happen, yes. If that's a very common case, ideally we should make sure that modules keep FWD or that vmlinux BTF does have a full struct instead of FWD.

Quoted 3 lines

jirka

#9 lore raw
Quoted 41 lines · Jiri Olsa
Quoted 33 lines · Andrii Nakryiko
Quoted 32 lines · Jiri Olsa
Quoted 30 lines · Jiri Olsa
Quoted 17 lines · Andrii Nakryiko
Quoted 16 lines · Jiri Olsa
Quoted 13 lines · Andrii Nakryiko
Quoted 8 lines · Andrii Nakryiko

According to [0], compilers sometimes might produce duplicate DWARF definitions for exactly the same struct/union within the same compilation unit (CU). We've had similar issues with identical arrays and handled them with a similar workaround in 6b6e6b1d09aa ("libbpf:
Accomodate DWARF/compiler bug with duplicated identical arrays"). Do the same for struct/union by ensuring that two structs/unions are exactly the same, down to the integer values of field referenced type IDs.

Jiri, can you please try this in your setup and see if that handles all situations or there are more complicated ones still. We'll need a test for more complicated ones in that case :( Thanks.

Quoted 5 lines
Quoted 3 lines

it seems to help largely, but I still see few modules (67 out of 780) that keep 'struct module' for some reason.. their struct module looks completely the same as is in vmlinux

Curious, what's the size of all the module BTFs now?

sorry for delay, I was waiting for s390x server

so with 'current' fedora kernel rawhide I'm getting slightly different total size number than before, so something has changed after the merge window..

Quoted 5 lines
Quoted 3 lines
Quoted 3 lines

however the increase with BTF enabled in modules is now from 16M to 18M, so the BTF data adds just about 2M, which I think we can live with

16MB for vmlinux BTF is quite a lot. Is it a allmodyesconfig or something?

Quoted 8 lines

looks like my english betrayed me again.. sry ;-)

size of all modules without BTF is 16M,
size of all modules with BTF is 18M,

so it's overall 2M increase

also note that each module is compressed with xz

Oh, so those 16MB are binaries of modules, not just BTF. Would be nice to do just .BTF ELF section comparisons, but up to you, just my curiosity.

Quoted 59 lines

jirka

Quoted 55 lines
Quoted 28 lines
Quoted 5 lines
Quoted 3 lines

And yes, please
try to narrow down what is causing the bloat this time. I think this

I'm on it

I'm seeing vmlinux BTF having just FWD record for sctp_mib struct, while the kernel module has the full definition

kernel:

        [2798] STRUCT 'netns_sctp' size=296 vlen=46
                'sctp_statistics' type_id=2800 bits_offset=0

        [2799] FWD 'sctp_mib' fwd_kind=struct
        [2800] PTR '(anon)' type_id=2799

module before dedup:

        [78928] STRUCT 'netns_sctp' size=296 vlen=46
                'sctp_statistics' type_id=78930 bits_offset=0

        [78929] STRUCT 'sctp_mib' size=272 vlen=1
                'mibs' type_id=80518 bits_offset=0
        [78930] PTR '(anon)' type_id=78929
Quoted 4 lines

this field is referenced from within 'struct module' so it won't match its kernel version and as a result extra 'struct module' stays in the module's BTF

Yeah, not much we could do about that short of just blindly matching FWD to STRUCT/UNION/ENUM by name, which sounds bad to me, I avoided doing that in BTF dedup algorithm. We only resolve FWD to STRUCT/UNION/ENUM when we have some containing struct with a field that points to FWD and (in another instance of the containing struct) to STRUCT/UNION/ENUM. That way we have sort of a proof that we are resolving the right FWD. While in this case it would be a blind guess based on name alone.

Quoted 3 lines

I'll need to check debuginfo/pahole if that FWD is correct, but I guess it's normal that some structs might end up unwinded only in modules and not necessarily in vmlinux

It can happen, yes. If that's a very common case, ideally we should make sure that modules keep FWD or that vmlinux BTF does have a full struct instead of FWD.

Quoted 3 lines

jirka

#10 lore raw
In reply to Andrii Nakryiko
This series was applied to bpf/bpf-next.git (master) by Daniel Borkmann <[email protected]>:

Hello:

This series was applied to bpf/bpf-next.git (master) by Daniel Borkmann <[email protected]>:

Quoted 9 lines · On Wed, 17 Nov 2021 11:41:13 -0800 you wrote:

According to [0], compilers sometimes might produce duplicate DWARF definitions for exactly the same struct/union within the same compilation unit (CU). We've had similar issues with identical arrays and handled them with a similar workaround in 6b6e6b1d09aa ("libbpf:
Accomodate DWARF/compiler bug with duplicated identical arrays"). Do the same for struct/union by ensuring that two structs/unions are exactly the same, down to the integer values of field referenced type IDs.

[...]

Here is the summary with links:
- [bpf-next,1/2] libbpf: accommodate DWARF/compiler bug with duplicated structs

    https://git.kernel.org/bpf/bpf-next/c/efdd3eb8015e
  - [bpf-next,2/2] selftests/bpf: add btf_dedup case with duplicated structs within CU
    https://git.kernel.org/bpf/bpf-next/c/9a49afe6f5a5

You are awesome, thank you!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html