On Wed, May 8, 2024 at 4:07 PM Mykyta Yatsenko
<mykyta.yatsenko5@xxxxxxxxx> wrote:
>
> On 5/7/24 22:02, Andrii Nakryiko wrote:
> > On Mon, May 6, 2024 at 6:45 AM Mykyta Yatsenko
> > <mykyta.yatsenko5@xxxxxxxxx> wrote:
> >> From: Mykyta Yatsenko <yatsenko@xxxxxxxx>
> >>
> >> Provide a way to sort bpftool c dump output, to simplify vmlinux.h
> >> diffing and forcing more natural definitions ordering.
> >>
> >> Use `normalized` argument in bpftool CLI after `format c` for example:
> >> ```
> >> bpftool btf dump file /sys/kernel/btf/fuse format c normalized
> >> ```
> >>
> >> Definitions are sorted by their BTF kind ranks, lexicographically and
> >> typedefs are forced to go right after their base type.
> >>
> >> Type ranks
> >>
> >> Assign ranks to btf kinds (defined in function btf_type_rank) to set
> >> next order:
> >> 1. Anonymous enums
> >> 2. Anonymous enums64
> >> 3. Named enums
> >> 4. Named enums64
> >> 5. Trivial types typedefs (ints, then floats)
> >> 6. Structs
> >> 7. Unions
> >> 8. Function prototypes
> >> 9. Forward declarations
> >>
> >> Lexicographical ordering
> >>
> >> Definitions within the same BTF kind are ordered by their names.
> >> Anonymous enums are ordered by their first element.
> >>
> >> Forcing typedefs to go right after their base type
> >>
> >> To make sure that typedefs are emitted right after their base type,
> >> we build a list of type's typedefs (struct typedef_ref) and after
> >> emitting type, its typedefs are emitted as well (lexicographically)
> >>
> >> There is a small flaw in this implementation:
> >> Type dependencies are resolved by bpf lib, so when type is dumped
> >> because it is a dependency, its typedefs are not output right after it,
> >> as bpflib does not have the list of typedefs for a given type.
> >>
> >> Signed-off-by: Mykyta Yatsenko <yatsenko@xxxxxxxx>
> >> ---
> >> tools/bpf/bpftool/btf.c | 264 +++++++++++++++++++++++++++++++++++++++-
> >> 1 file changed, 259 insertions(+), 5 deletions(-)
> >>
[...]
> > can we avoid all this complexity with TYPEDEFs if we just rank them
> > just like the type they are pointing to? I.e., TYPEDEF -> STRUCT is
> > just a struct, TYPEDEF -> TYPEDEF -> INT is just an INT. Emitting the
> > TYPEDEF type will force all the dependent types to be emitted, which
> > is good.
> >
> > If we also use this "pointee type"'s name as TYPEDEF's sort name, it
> > will also put it in the position where it should be, right? There
> > might be some insignificant deviations, but I think it would keep the
> > code much simpler (and either way we are striving for something that
> > more-or-less works as expected in practice, not designing some API
> > that's set in stone).
> >
> > WDYT?
> >
> I don't think this will guarantee for each type all typedefs follow
> immediately.
> For example:
>
> With this patch next output is generated:
> typedef s64 aaa; /* aaa is the smallest first level child of s64 */
> typedef aaa ccc; /* ccc immediately follows aaa as child */
> typedef s64 bbb; /* bbb is first level child of s64 following aaa */
> typedef s32 xxx; /* xxx follows bbb lexicographically */
>
> Option 2: I we apply flat sorting by rank and then name, we'll get next
> order:
> typedef s64 aaa;
> typedef s64 bbb;
> typedef aaa ccc;
> typedef s32 xxx;
>
> Here order just follows aaa - bbb - ccc - xxx. Type ccc does not immediately
> follow its parent aaa.
>
> Option3: If we use pointee name as sort name, next output is expected:
> typedef s64 aaa; /* dependency of the next line */
> typedef aaa ccc; /* sort name aaa */
> typedef s32 xxx; /* sort name s32 */
> typedef s64 bbb; /* sort name s64 */
>
> I think Option 2 will have the simplest implementation, but we are
> getting BFS
> ordering instead of DFS. I'm not entirely sure, but it looks to me, that we
> can't achieve DFS ordering with sort-based simple implementation, let me
> know if
> I'm missing anything here.
> If DFS ordering is not required, I'm happy to scrap it.
I'd go with Option3, but I'd resolve ccc -> aaa -> s64 as sort name
(so all the way to non-reference type), and use INT as rank for that
typedef. We'd have ordering ambiguity between `ccc -> aaa -> s64`
chain and `bbb -> s64`, to resolve that we'd need to be able to
compare entire chains, but that would require more bookkeeping. So
maybe let's remember both resolved name and "original" name (i.e., for
ccc resolved would be "s64", original is "ccc"), and if the resolved
name is the same, then compare original name. That will give the
ordering more stability. And it's just an extra u32 to keep track per
type in this extra sort_datum thingy. WDYT?
I think simple trumps whatever ideal ordering we come up with. In any
case it's going to be pretty stable and easy to diff, so I'd go with
that.
> >> +static int *sort_btf_c(const struct btf *btf)
> >> +{
> >> + int total_root_types;
> >> + struct sort_datum *datums;
> >> + int *sorted_indexes = NULL;
> >> + int *type_index_to_datum_index;
> > nit: most of these names are unnecessarily verbose. It's one
> > relatively straightforward function, just use shorter names "n",
> > "idxs", "idx_to_datum", stuff like this. Cooler and shorter C names
> > :))
> >
> >> +
> >> + if (!btf)
> >> + return sorted_indexes;
> > this would be a horrible bug if this happens, don't guard against it here
> >
> >> +
> >> + total_root_types = btf__type_cnt(btf);
> >> + datums = malloc(sizeof(struct sort_datum) * total_root_types);
> >> +
> >> + for (int i = 1; i < total_root_types; ++i) {
> >> + struct sort_datum *current_datum = datums + i;
> >> +
> >> + current_datum->index = i;
> >> + current_datum->name = btf_type_sort_name(btf, i);
> >> + current_datum->type_rank = btf_type_rank(btf, i, false);
> >> + current_datum->emitted = false;
> > btf_dump__dump_type() keeps track of which types are already emitted,
> > you probably don't need to do this explicitly?
> I use `emitted` to indicate whether type index has been copied into output
> `sorted_indexes` array. This is needed because type (if it is a typedef)
> can be put into output out of order by its parent base type, if base has
> been processed earlier. It helps to avoid putting the same type twice in
> the output array preventing buffer overrun.
Would this still be needed if we do this sorting only approach?
[...]
