On Thu, 2025-05-22 at 13:03 -0700, Andrii Nakryiko wrote:
> On Thu, May 22, 2025 at 10:56 AM Thierry Treyer <ttreyer@xxxxxxxx> 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?
[...]
