Re: [PATCH RFC 0/3] list inline expansions in .BTF.inline

[Eduard Zingerman <eddyz87@gmail.com>]

On Thu, 2025-05-22 at 13:03 -0700, Andrii Nakryiko wrote:
> On Thu, May 22, 2025 at 10:56 AM Thierry Treyer <ttreyer@meta.com> wrote:
> > 
> > Hello everyone,
> > 
> > Here are the estimates for the different encoding schemes we discussed:
> > - parameters' location takes ~1MB without de-duplication,
> > - parameters' location shrinks to ~14kB when de-duplicated,
> > - instead of de-duplicating the individual locations,
> >   de-duplicating functions' parameter lists yields 187kB of locations data.
> > 
> > We also need to take into account the size of the corresponding funcsec
> > table, which starts at 3.6MB. The full details follows:
> > 
> >   1) // params_offset points to the first parameter's location
> >      struct fn_info { u32 type_id, offset, params_offset; };
> >   2) // param_offsets point to each parameters' location
> >      struct fn_info { u32 type_id, offset; u16 param_offsets[proto.arglen]; };
> >   3) // locations are stored inline, in the funcsec table
> >      struct fn_info { u32 type_id, offset; loc inline_locs[proto.arglen]; };
> > 
> >   Params encoding             Locations Size   Funcsec Size   Total Size
> >   ======================================================================
> >   (1) param list, no dedup         1,017,654      5,467,824    6,485,478
> >   (1) param list, w/ dedup           187,379      5,467,824    5,655,203
> >   (2) param offsets, w/ dedup         14,526      4,808,838    4,823,364
> 
> This one is almost as good as (3) below, but fits better into the
> existing kind+vlen model where there is a variable number of fixed
> sized elements (but locations can still be variable-sized and keep
> evolving much more easily). I'd go with this one, unless I'm missing
> some important benefit of other representations.

Thierry, could you please provide some details for the representation
of both fn_info and parameters for this case?
I'm curious how far this version is from exhausting u16 limit.

> 
> >   (3) param list inline            1,017,654      3,645,216    4,662,870
> > 
> >   Estimated size in bytes of the new .BTF.func_aux section, from a
> >   production kernel v6.9. It includes both partially and fully inlined
> >   functions in the funcsec tables, with all their parameters, either inline
> >   or in their own sub-section. It does not include type information that
> >   would be required to handle fully inlined functions, functions with
> >   conflicting name, and functions with conflicting prototypes.
> > 
> >   The deduplicated locations in 2) are small enough to be indexed by a u16.
> > 
> > Storing the locations inline uses the least amount of space. Followed by
> > storing inline a list of offsets to the locations. Neither of these
> > approaches have fixed size records in funcsec. "param list, w/ dedup" is
> > ~1MB larger than inlined locations, but has fixed size records.
> > 
> > In all cases, the funcsec table uses the most space, compared to the
> > locations. The size of the `type` sub-section will also grow when we add
> > the missing type information for fully inlined functions, functions with
> > conflicting name, and functions with conflicting prototypes.
> > 
> > With fixed size records in the funcsec table, we'd get faster lookup by
> > sorting by `type_id` or `offset`.  bpftrace could efficiently search the
> > lower bound of a `type_id` to instrument all its inline instances.
> > Symbolication tools could efficiently search for inline functions at a
> > given offset.
> > 
> > However, it would rule out the most efficient encoding.
> > How do we want to approach this tradeoff?

[...]