Skip to contentSkip to conversation

bpftool: improve btf c dump sorting stability

PATCH Superseded Mykyta Yatsenko 2 participants 3 messages Sep 5, 2024

Subsystems (2)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 bpftool: improve btf c dump sorting stability

From: Mykyta Yatsenko <[email protected]>

Existing algorithm for BTF C dump sorting uses only types and names of the structs and unions for ordering. As dump contains structs with the same names but different contents, relative to each other ordering of those structs will be accidental.
This patch addresses this problem by introducing a new sorting field that contains hash of the struct/union field names and types to disambiguate comparison of the non-unique named structs.

---
 tools/bpf/bpftool/btf.c | 93 ++++++++++++++++++++++++++++++++++-------
 1 file changed, 79 insertions(+), 14 deletions(-)
tools/bpf/bpftool/btf.c +79 -14
index 3b57ba095ab6..0e7151bfc3d5 100644
@@ -50,6 +50,7 @@ struct sort_datum {
 	int type_rank;
 	const char *sort_name;
 	const char *own_name;
+	__u64 disambig_hash;
 };
 
 static const char *btf_int_enc_str(__u8 encoding)
@@ -557,17 +558,6 @@ static const char *btf_type_sort_name(const struct btf *btf, __u32 index, bool f
 	const struct btf_type *t = btf__type_by_id(btf, index);
 
 	switch (btf_kind(t)) {
-	case BTF_KIND_ENUM:
-	case BTF_KIND_ENUM64: {
-		int name_off = t->name_off;
-
-		if (!from_ref && !name_off && btf_vlen(t))
-			name_off = btf_kind(t) == BTF_KIND_ENUM64 ?
-				btf_enum64(t)->name_off :
-				btf_enum(t)->name_off;
-
-		return btf__name_by_offset(btf, name_off);
-	}
 	case BTF_KIND_ARRAY:
 		return btf_type_sort_name(btf, btf_array(t)->type, true);
 	case BTF_KIND_TYPE_TAG:
@@ -584,20 +574,94 @@ static const char *btf_type_sort_name(const struct btf *btf, __u32 index, bool f
 	return NULL;
 }
 
+static __u64 hasher(__u64 hash, __u64 val)
+{
+	return hash * 31 + val;
+}
+
+static __u64 btf_name_hasher(__u64 hash, const struct btf *btf, __u32 name_off)
+{
+	if (!name_off)
+		return hash;
+
+	return hasher(hash, str_hash(btf__name_by_offset(btf, name_off)));
+}
+
+static __u64 btf_type_disambig_hash(const struct btf *btf, __u32 index, bool include_members)
+{
+	const struct btf_type *t = btf__type_by_id(btf, index);
+	int i;
+	size_t hash = 0;
+
+	hash = btf_name_hasher(hash, btf, t->name_off);
+
+	switch (btf_kind(t)) {
+	case BTF_KIND_ENUM:
+	case BTF_KIND_ENUM64:
+		for (i = 0; i < btf_vlen(t); i++) {
+			__u32 name_off = btf_is_enum(t) ?
+				btf_enum(t)[i].name_off :
+				btf_enum64(t)[i].name_off;
+
+			hash = btf_name_hasher(hash, btf, name_off);
+		}
+		break;
+	case BTF_KIND_STRUCT:
+	case BTF_KIND_UNION:
+		if (!include_members)
+			break;
+		for (i = 0; i < btf_vlen(t); i++) {
+			const struct btf_member *m = btf_members(t) + i;
+
+			hash = btf_name_hasher(hash, btf, m->name_off);
+			/* resolve field type's name and hash it as well */
+			hash = hasher(hash, btf_type_disambig_hash(btf, m->type, false));
+		}
+		break;
+	case BTF_KIND_TYPE_TAG:
+	case BTF_KIND_CONST:
+	case BTF_KIND_PTR:
+	case BTF_KIND_VOLATILE:
+	case BTF_KIND_RESTRICT:
+	case BTF_KIND_TYPEDEF:
+	case BTF_KIND_DECL_TAG:
+		hash = hasher(hash, btf_type_disambig_hash(btf, t->type, include_members));
+		break;
+	case BTF_KIND_ARRAY: {
+		struct btf_array *arr = btf_array(t);
+
+		hash = hasher(hash, arr->nelems);
+		hash = hasher(hash, btf_type_disambig_hash(btf, arr->type, include_members));
+		break;
+	}
+	default:
+		break;
+	}
+	return hash;
+}
+
 static int btf_type_compare(const void *left, const void *right)
 {
 	const struct sort_datum *d1 = (const struct sort_datum *)left;
 	const struct sort_datum *d2 = (const struct sort_datum *)right;
 	int r;
 
-	if (d1->type_rank != d2->type_rank)
-		return d1->type_rank < d2->type_rank ? -1 : 1;
+	r = d1->type_rank - d2->type_rank;
+	if (r)
+		return r;
 
 	r = strcmp(d1->sort_name, d2->sort_name);
 	if (r)
 		return r;
 
-	return strcmp(d1->own_name, d2->own_name);
+	r = strcmp(d1->own_name, d2->own_name);
+	if (r)
+		return r;
+
+	if (d1->disambig_hash != d2->disambig_hash)
+		return d1->disambig_hash < d2->disambig_hash ? -1 : 1;
+
+	return d1->index - d2->index;
 }
 
 static struct sort_datum *sort_btf_c(const struct btf *btf)
@@ -618,6 +682,7 @@ static struct sort_datum *sort_btf_c(const struct btf *btf)
 		d->type_rank = btf_type_rank(btf, i, false);
 		d->sort_name = btf_type_sort_name(btf, i, false);
 		d->own_name = btf__name_by_offset(btf, t->name_off);
+		d->disambig_hash = btf_type_disambig_hash(btf, i, true);
 	}
 
 	qsort(datums, n, sizeof(struct sort_datum), btf_type_compare);
Signature · 1 line
2.46.0
#1 lore raw
Quoted 11 lines · Mykyta Yatsenko

From: Mykyta Yatsenko <[email protected]>

Existing algorithm for BTF C dump sorting uses only types and names of the structs and unions for ordering. As dump contains structs with the same names but different contents, relative to each other ordering of those structs will be accidental.
This patch addresses this problem by introducing a new sorting field that contains hash of the struct/union field names and types to disambiguate comparison of the non-unique named structs.

Did you check how stable generated vmlinux.h now is when just rebuilding kernel with no actual changes? Does it still have some variation?

LGTM, but let's keep the btf_type_sort_name() as is? See below.

Quoted 22 lines
---
 tools/bpf/bpftool/btf.c | 93 ++++++++++++++++++++++++++++++++++-------
 1 file changed, 79 insertions(+), 14 deletions(-)
tools/bpf/bpftool/btf.c +1 -1
index 3b57ba095ab6..0e7151bfc3d5 100644
@@ -50,6 +50,7 @@ struct sort_datum {
        int type_rank;
        const char *sort_name;
        const char *own_name;
+       __u64 disambig_hash;
 };
 
 static const char *btf_int_enc_str(__u8 encoding)
@@ -557,17 +558,6 @@ static const char *btf_type_sort_name(const struct btf *btf, __u32 index, bool f
        const struct btf_type *t = btf__type_by_id(btf, index);
 
        switch (btf_kind(t)) {
-       case BTF_KIND_ENUM:

tools/bpf/bpftool/btf.c static const char *btf_type_sort_name(const struct btf *btf, __u32 index, bool f · line 570

Quoted 10 lines
tools/bpf/bpftool/btf.c +0 -10
-       case BTF_KIND_ENUM64: {
-               int name_off = t->name_off;
-
-               if (!from_ref && !name_off && btf_vlen(t))
-                       name_off = btf_kind(t) == BTF_KIND_ENUM64 ?
-                               btf_enum64(t)->name_off :
-                               btf_enum(t)->name_off;
-
-               return btf__name_by_offset(btf, name_off);
-       }

Why remove this? anonymous enums will usually still have some meaningful prefix for each enumerator value, and so sorting based on those prefixes (effective) still seems useful for more logical ordering

pw-bot: cr

Quoted 11 lines
tools/bpf/bpftool/btf.c +4 -0
        case BTF_KIND_ARRAY:
                return btf_type_sort_name(btf, btf_array(t)->type, true);
        case BTF_KIND_TYPE_TAG:
@@ -584,20 +574,94 @@ static const char *btf_type_sort_name(const struct btf *btf, __u32 index, bool f
        return NULL;
 }
 
+static __u64 hasher(__u64 hash, __u64 val)
+{
+       return hash * 31 + val;
+}

tools/bpf/bpftool/btf.c static const char *btf_type_sort_name(const struct btf *btf, __u32 index, bool f · line 590

Quoted 10 lines
tools/bpf/bpftool/btf.c +10 -0
+
+static __u64 btf_name_hasher(__u64 hash, const struct btf *btf, __u32 name_off)
+{
+       if (!name_off)
+               return hash;
+
+       return hasher(hash, str_hash(btf__name_by_offset(btf, name_off)));
+}
+
+static __u64 btf_type_disambig_hash(const struct btf *btf, __u32 index, bool include_members)

nit: s/index/id/ ?

Quoted 62 lines
tools/bpf/bpftool/btf.c +54 -2
+{
+       const struct btf_type *t = btf__type_by_id(btf, index);
+       int i;
+       size_t hash = 0;
+
+       hash = btf_name_hasher(hash, btf, t->name_off);
+
+       switch (btf_kind(t)) {
+       case BTF_KIND_ENUM:
+       case BTF_KIND_ENUM64:
+               for (i = 0; i < btf_vlen(t); i++) {
+                       __u32 name_off = btf_is_enum(t) ?
+                               btf_enum(t)[i].name_off :
+                               btf_enum64(t)[i].name_off;
+
+                       hash = btf_name_hasher(hash, btf, name_off);
+               }
+               break;
+       case BTF_KIND_STRUCT:
+       case BTF_KIND_UNION:
+               if (!include_members)
+                       break;
+               for (i = 0; i < btf_vlen(t); i++) {
+                       const struct btf_member *m = btf_members(t) + i;
+
+                       hash = btf_name_hasher(hash, btf, m->name_off);
+                       /* resolve field type's name and hash it as well */
+                       hash = hasher(hash, btf_type_disambig_hash(btf, m->type, false));
+               }
+               break;
+       case BTF_KIND_TYPE_TAG:
+       case BTF_KIND_CONST:
+       case BTF_KIND_PTR:
+       case BTF_KIND_VOLATILE:
+       case BTF_KIND_RESTRICT:
+       case BTF_KIND_TYPEDEF:
+       case BTF_KIND_DECL_TAG:
+               hash = hasher(hash, btf_type_disambig_hash(btf, t->type, include_members));
+               break;
+       case BTF_KIND_ARRAY: {
+               struct btf_array *arr = btf_array(t);
+
+               hash = hasher(hash, arr->nelems);
+               hash = hasher(hash, btf_type_disambig_hash(btf, arr->type, include_members));
+               break;
+       }
+       default:
+               break;
+       }
+       return hash;
+}
+
 static int btf_type_compare(const void *left, const void *right)
 {
        const struct sort_datum *d1 = (const struct sort_datum *)left;
        const struct sort_datum *d2 = (const struct sort_datum *)right;
        int r;
 
-       if (d1->type_rank != d2->type_rank)
-               return d1->type_rank < d2->type_rank ? -1 : 1;
+       r = d1->type_rank - d2->type_rank;
+       if (r)

tools/bpf/bpftool/btf.c static const char *btf_type_sort_name(const struct btf *btf, __u32 index, bool f · line 659

Quoted 10 lines
tools/bpf/bpftool/btf.c +4 -1
+               return r;
 
        r = strcmp(d1->sort_name, d2->sort_name);
        if (r)
                return r;
 
-       return strcmp(d1->own_name, d2->own_name);
+       r = strcmp(d1->own_name, d2->own_name);
+       if (r)
+               return r;

when I was playing with this code I had stong desire to do something like below to cut down on visual noise

r = d1->type_rank - d2->type_rank;
r = r ?: strcmp(d1->sort_name, d2->sort_name);
r = r ?: strcmp(d1->own_name, d2->own_name);
if (r)

    return r;

WDYT?

Quoted 19 lines
tools/bpf/bpftool/btf.c +6 -1
+
+       if (d1->disambig_hash != d2->disambig_hash)
+               return d1->disambig_hash < d2->disambig_hash ? -1 : 1;
+
+       return d1->index - d2->index;
 }
 
 static struct sort_datum *sort_btf_c(const struct btf *btf)
@@ -618,6 +682,7 @@ static struct sort_datum *sort_btf_c(const struct btf *btf)
                d->type_rank = btf_type_rank(btf, i, false);
                d->sort_name = btf_type_sort_name(btf, i, false);
                d->own_name = btf__name_by_offset(btf, t->name_off);
+               d->disambig_hash = btf_type_disambig_hash(btf, i, true);
        }
 
        qsort(datums, n, sizeof(struct sort_datum), btf_type_compare);
--

2.46.0

#2 lore raw
Quoted 12 lines · Andrii Nakryiko
Quoted 10 lines · Mykyta Yatsenko

From: Mykyta Yatsenko <[email protected]>

Existing algorithm for BTF C dump sorting uses only types and names of the structs and unions for ordering. As dump contains structs with the same names but different contents, relative to each other ordering of those structs will be accidental.
This patch addresses this problem by introducing a new sorting field that contains hash of the struct/union field names and types to disambiguate comparison of the non-unique named structs.

Quoted 3 lines

Did you check how stable generated vmlinux.h now is when just rebuilding kernel with no actual changes? Does it still have some variation?

It's stable with this change, no variation at all (I tested up to about 5 times in a row rebuilding kernel and generating vmlinux.h), though, I would not be surprised if some edge case for same-named structs is not covered. It may get triggered in future by some change in kernel structures.

Quoted 22 lines

LGTM, but let's keep the btf_type_sort_name() as is? See below.

Quoted 20 lines
---
  tools/bpf/bpftool/btf.c | 93 ++++++++++++++++++++++++++++++++++-------
  1 file changed, 79 insertions(+), 14 deletions(-)
tools/bpf/bpftool/btf.c +1 -0
index 3b57ba095ab6..0e7151bfc3d5 100644
@@ -50,6 +50,7 @@ struct sort_datum {
         int type_rank;
         const char *sort_name;
         const char *own_name;
+       __u64 disambig_hash;
  };
 
  static const char *btf_int_enc_str(__u8 encoding)
@@ -557,17 +558,6 @@ static const char *btf_type_sort_name(const struct btf *btf, __u32 index, bool f
         const struct btf_type *t = btf__type_by_id(btf, index);
 
Quoted 16 lines

tools/bpf/bpftool/btf.c static const char *btf_type_sort_name(const struct btf *btf, __u32 index, bool f · line 570

Quoted 12 lines
tools/bpf/bpftool/btf.c +0 -11
         switch (btf_kind(t)) {
-       case BTF_KIND_ENUM:
-       case BTF_KIND_ENUM64: {
-               int name_off = t->name_off;
-
-               if (!from_ref && !name_off && btf_vlen(t))
-                       name_off = btf_kind(t) == BTF_KIND_ENUM64 ?
-                               btf_enum64(t)->name_off :
-                               btf_enum(t)->name_off;
-
-               return btf__name_by_offset(btf, name_off);
-       }

Why remove this? anonymous enums will usually still have some meaningful prefix for each enumerator value, and so sorting based on those prefixes (effective) still seems useful for more logical ordering

Removed this just to simplify code a little bit. With the hash function we use for disambiguation same-named enums, enums with less number of elements would be pushed higher which is decent sorting as well. I see why we would prefer to cluster enums with similar prefixes together. I'll revert this removal in v2.

Quoted 10 lines

pw-bot: cr

Quoted 7 lines
tools/bpf/bpftool/btf.c +0 -0
         case BTF_KIND_ARRAY:
                 return btf_type_sort_name(btf, btf_array(t)->type, true);
         case BTF_KIND_TYPE_TAG:
@@ -584,20 +574,94 @@ static const char *btf_type_sort_name(const struct btf *btf, __u32 index, bool f
         return NULL;
  }
 
Quoted 15 lines
Quoted 4 lines
tools/bpf/bpftool/btf.c +4 -0
+static __u64 hasher(__u64 hash, __u64 val)
+{
+       return hash * 31 + val;
+}

tools/bpf/bpftool/btf.c static const char *btf_type_sort_name(const struct btf *btf, __u32 index, bool f · line 590

Quoted 10 lines
tools/bpf/bpftool/btf.c +10 -0
+
+static __u64 btf_name_hasher(__u64 hash, const struct btf *btf, __u32 name_off)
+{
+       if (!name_off)
+               return hash;
+
+       return hasher(hash, str_hash(btf__name_by_offset(btf, name_off)));
+}
+
+static __u64 btf_type_disambig_hash(const struct btf *btf, __u32 index, bool include_members)

nit: s/index/id/ ?

Ack

Quoted 76 lines
Quoted 63 lines
tools/bpf/bpftool/btf.c +54 -2
+{
+       const struct btf_type *t = btf__type_by_id(btf, index);
+       int i;
+       size_t hash = 0;
+
+       hash = btf_name_hasher(hash, btf, t->name_off);
+
+       switch (btf_kind(t)) {
+       case BTF_KIND_ENUM:
+       case BTF_KIND_ENUM64:
+               for (i = 0; i < btf_vlen(t); i++) {
+                       __u32 name_off = btf_is_enum(t) ?
+                               btf_enum(t)[i].name_off :
+                               btf_enum64(t)[i].name_off;
+
+                       hash = btf_name_hasher(hash, btf, name_off);
+               }
+               break;
+       case BTF_KIND_STRUCT:
+       case BTF_KIND_UNION:
+               if (!include_members)
+                       break;
+               for (i = 0; i < btf_vlen(t); i++) {
+                       const struct btf_member *m = btf_members(t) + i;
+
+                       hash = btf_name_hasher(hash, btf, m->name_off);
+                       /* resolve field type's name and hash it as well */
+                       hash = hasher(hash, btf_type_disambig_hash(btf, m->type, false));
+               }
+               break;
+       case BTF_KIND_TYPE_TAG:
+       case BTF_KIND_CONST:
+       case BTF_KIND_PTR:
+       case BTF_KIND_VOLATILE:
+       case BTF_KIND_RESTRICT:
+       case BTF_KIND_TYPEDEF:
+       case BTF_KIND_DECL_TAG:
+               hash = hasher(hash, btf_type_disambig_hash(btf, t->type, include_members));
+               break;
+       case BTF_KIND_ARRAY: {
+               struct btf_array *arr = btf_array(t);
+
+               hash = hasher(hash, arr->nelems);
+               hash = hasher(hash, btf_type_disambig_hash(btf, arr->type, include_members));
+               break;
+       }
+       default:
+               break;
+       }
+       return hash;
+}
+
  static int btf_type_compare(const void *left, const void *right)
  {
         const struct sort_datum *d1 = (const struct sort_datum *)left;
         const struct sort_datum *d2 = (const struct sort_datum *)right;
         int r;
 
-       if (d1->type_rank != d2->type_rank)
-               return d1->type_rank < d2->type_rank ? -1 : 1;
+       r = d1->type_rank - d2->type_rank;
+       if (r)

tools/bpf/bpftool/btf.c static const char *btf_type_sort_name(const struct btf *btf, __u32 index, bool f · line 659

Quoted 10 lines
tools/bpf/bpftool/btf.c +4 -1
+               return r;
 
         r = strcmp(d1->sort_name, d2->sort_name);
         if (r)
                 return r;
 
-       return strcmp(d1->own_name, d2->own_name);
+       r = strcmp(d1->own_name, d2->own_name);
+       if (r)
+               return r;

when I was playing with this code I had stong desire to do something like below to cut down on visual noise

Quoted 7 lines

r = d1->type_rank - d2->type_rank;
r = r ?: strcmp(d1->sort_name, d2->sort_name);
r = r ?: strcmp(d1->own_name, d2->own_name);
if (r)

     return r;

WDYT?

Looks a little hard to parse for me (maybe a skill issue). Early exits help to disregard context when reading the code (not sure if this makes sense), so I prefer them. Essentially this is the same thing as theexisting code, but more compact, makes sense, I'll include it in v2.

Quoted 19 lines
Quoted 19 lines
tools/bpf/bpftool/btf.c +6 -1
+
+       if (d1->disambig_hash != d2->disambig_hash)
+               return d1->disambig_hash < d2->disambig_hash ? -1 : 1;
+
+       return d1->index - d2->index;
  }
 
  static struct sort_datum *sort_btf_c(const struct btf *btf)
@@ -618,6 +682,7 @@ static struct sort_datum *sort_btf_c(const struct btf *btf)
                 d->type_rank = btf_type_rank(btf, i, false);
                 d->sort_name = btf_type_sort_name(btf, i, false);
                 d->own_name = btf__name_by_offset(btf, t->name_off);
+               d->disambig_hash = btf_type_disambig_hash(btf, i, true);
         }
 
         qsort(datums, n, sizeof(struct sort_datum), btf_type_compare);
--

2.46.0