On 09/05/2024 16:17, Mykyta@xxxxxxxxxxxxxxxxxx wrote:
> From: Mykyta Yatsenko <yatsenko@xxxxxxxx>
>
> Sort bpftool c dump output; aiming to simplify vmlinux.h diffing and
> forcing more natural type definitions ordering.
>
> Definitions are sorted first by their BTF kind ranks, then by their base
> type name and by their own name.
>
> Type ranks
>
> Assign ranks to btf kinds (defined in function btf_type_rank) to set
> next order:
> 1. Anonymous enums/enums64
> 2. Named enums/enums64
> 3. Trivial types typedefs (ints, then floats)
> 4. Structs/Unions
> 5. Function prototypes
> 6. Forward declarations
>
> Type rank is set to maximum for unnamed reference types, structs and
> unions to avoid emitting those types early. They will be emitted as
> part of the type chain starting with named type.
>
> Lexicographical ordering
>
> Each type is assigned a sort_name and own_name.
> sort_name is the resolved name of the final base type for reference
> types (typedef, pointer, array etc). Sorting by sort_name allows to
> group typedefs of the same base type. sort_name for non-reference type
> is the same as own_name. own_name is a direct name of particular type,
> is used as final sorting step.
>
> Signed-off-by: Mykyta Yatsenko <yatsenko@xxxxxxxx>
This looks great! Not sure if you experimented with sorting for the
split BTF case (dumping /sys/kernel/btf/tun say); are there any
additional issues in doing that? From what I can see below the sort
would just be applied across base and split BTF and should just work, is
that right? A few suggestions below, but
Reviewed-by: Alan Maguire <alan.maguire@xxxxxxxxxx>
> ---
> tools/bpf/bpftool/btf.c | 125 +++++++++++++++++++++++++++++++++++++++-
> 1 file changed, 122 insertions(+), 3 deletions(-)
>
> diff --git a/tools/bpf/bpftool/btf.c b/tools/bpf/bpftool/btf.c
> index 91fcb75babe3..09ecd2abf066 100644
> --- a/tools/bpf/bpftool/btf.c
> +++ b/tools/bpf/bpftool/btf.c
> @@ -43,6 +43,13 @@ static const char * const btf_kind_str[NR_BTF_KINDS] = {
> [BTF_KIND_ENUM64] = "ENUM64",
> };
>
> +struct sort_datum {
> + int index;
> + int type_rank;
> + const char *sort_name;
> + const char *own_name;
> +};
> +
> static const char *btf_int_enc_str(__u8 encoding)
> {
> switch (encoding) {
> @@ -460,11 +467,114 @@ static void __printf(2, 0) btf_dump_printf(void *ctx,
> vfprintf(stdout, fmt, args);
> }
>
> +static bool is_reference_type(const struct btf_type *t)
> +{
> + int kind = btf_kind(t);
> +
> + return kind == BTF_KIND_CONST || kind == BTF_KIND_PTR || kind == BTF_KIND_VOLATILE ||
> + kind == BTF_KIND_RESTRICT || kind == BTF_KIND_ARRAY || kind == BTF_KIND_TYPEDEF ||
> + kind == BTF_KIND_DECL_TAG;
> +}
> +
> +static int btf_type_rank(const struct btf *btf, __u32 index, bool has_name)
> +{
> + const struct btf_type *t = btf__type_by_id(btf, index);
> + const int max_rank = 10;
> + const int kind = btf_kind(t);
> +
> + if (t->name_off)
> + has_name = true;
> +
> + switch (kind) {
> + case BTF_KIND_ENUM:
> + case BTF_KIND_ENUM64:
> + return has_name ? 1 : 0;
> + case BTF_KIND_INT:
> + case BTF_KIND_FLOAT:
> + return 2;
> + case BTF_KIND_STRUCT:
> + case BTF_KIND_UNION:
> + return has_name ? 3 : max_rank;
> + case BTF_KIND_FUNC_PROTO:
> + return has_name ? 4 : max_rank;
> +
Don't think a FUNC_PROTO will ever have a name, so has_name check
probably not needed here.
> + default: {
> + if (has_name && is_reference_type(t)) {
> + const int parent = kind == BTF_KIND_ARRAY ? btf_array(t)->type : t->type;
> +
> + return btf_type_rank(btf, parent, has_name);
> + }
> + return max_rank;
> + }
> + }
> +}
> +
> +static const char *btf_type_sort_name(const struct btf *btf, __u32 index)
> +{
> + const struct btf_type *t = btf__type_by_id(btf, index);
> + int kind = btf_kind(t);
> +
> + /* Use name of the first element for anonymous enums */
> + if (!t->name_off && (kind == BTF_KIND_ENUM || kind == BTF_KIND_ENUM64) &&
> + BTF_INFO_VLEN(t->info))
> + return btf__name_by_offset(btf, btf_enum(t)->name_off);
> +
> + /* Return base type name for reference types */
> + while (is_reference_type(t)) {
The two times is_reference_type() is used, we use this conditional to
get the array type; worth rolling this into a get_reference_type(t)
function that returns t->type for reference types, btf_array(t)->type
for arrays and -1 otherwise perhaps?
> + index = btf_kind(t) == BTF_KIND_ARRAY ? btf_array(t)->type : t->type;
> + t = btf__type_by_id(btf, index);
> + }
> +
> + return btf__name_by_offset(btf, t->name_off);
> +}
> +
> +static int btf_type_compare(const void *left, const void *right)
> +{
> + const struct sort_datum *datum1 = (const struct sort_datum *)left;
> + const struct sort_datum *datum2 = (const struct sort_datum *)right;
> + int sort_name_cmp;
> +
> + if (datum1->type_rank != datum2->type_rank)
> + return datum1->type_rank < datum2->type_rank ? -1 : 1;
> +
> + sort_name_cmp = strcmp(datum1->sort_name, datum2->sort_name);
> + if (sort_name_cmp)
> + return sort_name_cmp;
> +
> + return strcmp(datum1->own_name, datum2->own_name);
> +}
> +
> +static struct sort_datum *sort_btf_c(const struct btf *btf)
> +{
> + int total_root_types;
> + struct sort_datum *datums;
> +
> + total_root_types = btf__type_cnt(btf);
> + datums = malloc(sizeof(struct sort_datum) * total_root_types);
calloc(total_root_types, sizeof(*datums)) will get you a
zero-initialized array, which may be useful below...
> + if (!datums)
> + return NULL;
> +
> + for (int i = 0; i < total_root_types; ++i) {
you're starting from zero here so you'll get &btf_void below; if you
zero-initialize above I think you can just start from 1.
> + struct sort_datum *current_datum = datums + i;
> + const struct btf_type *t = btf__type_by_id(btf, i);
> +
> + current_datum->index = i;
> + current_datum->type_rank = btf_type_rank(btf, i, false);
> + current_datum->sort_name = btf_type_sort_name(btf, i);
> + current_datum->own_name = btf__name_by_offset(btf, t->name_off);
> + }
> +
> + qsort(datums, total_root_types, sizeof(struct sort_datum), btf_type_compare);
> +
> + return datums;
> +}
> +
> static int dump_btf_c(const struct btf *btf,
> - __u32 *root_type_ids, int root_type_cnt)
> + __u32 *root_type_ids, int root_type_cnt, bool sort_dump)
> {
> struct btf_dump *d;
> int err = 0, i;
> + struct sort_datum *datums = NULL;
>
> d = btf_dump__new(btf, btf_dump_printf, NULL, NULL);
> if (!d)
> @@ -486,8 +596,12 @@ static int dump_btf_c(const struct btf *btf,
> } else {
> int cnt = btf__type_cnt(btf);
>
> + if (sort_dump)
> + datums = sort_btf_c(btf);
> for (i = 1; i < cnt; i++) {
> - err = btf_dump__dump_type(d, i);
> + int idx = datums ? datums[i].index : i;
> +
> + err = btf_dump__dump_type(d, idx);
> if (err)
> goto done;
> }
> @@ -501,6 +615,7 @@ static int dump_btf_c(const struct btf *btf,
>
> done:
> btf_dump__free(d);
> + free(datums);
> return err;
> }
>
> @@ -553,6 +668,7 @@ static int do_dump(int argc, char **argv)
> __u32 root_type_ids[2];
> int root_type_cnt = 0;
> bool dump_c = false;
> + bool sort_dump_c = true;
> __u32 btf_id = -1;
> const char *src;
> int fd = -1;
> @@ -663,6 +779,9 @@ static int do_dump(int argc, char **argv)
> goto done;
> }
> NEXT_ARG();
> + } else if (is_prefix(*argv, "unordered")) {
you'll need to update the man page and add to the bash completion for
this new argument I think.
> + sort_dump_c = false;
> + NEXT_ARG();
> } else {
> p_err("unrecognized option: '%s'", *argv);
> err = -EINVAL;
> @@ -691,7 +810,7 @@ static int do_dump(int argc, char **argv)
> err = -ENOTSUP;
> goto done;
> }
> - err = dump_btf_c(btf, root_type_ids, root_type_cnt);
> + err = dump_btf_c(btf, root_type_ids, root_type_cnt, sort_dump_c);
> } else {
> err = dump_btf_raw(btf, root_type_ids, root_type_cnt);
> }
