Re: [PATCH v2 bpf-next] bpftool: introduce btf c dump sorting

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

On 09/05/2024 16:17, Mykyta@web.codeaurora.org wrote:
> From: Mykyta Yatsenko <yatsenko@meta.com>
> 
> 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@meta.com>

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@oracle.com>

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