[PATCH v2] Add a trie to map quickly from address range to compilation unit.

[Jan Beulich]

On 04.04.2022 09:32, Steinar H. Gunderson via Binutils wrote:
> When using perf to profile large binaries, _bfd_dwarf2_find_nearest_line()
> becomes a hotspot, as perf wants to get line number information
> (for inline-detection purposes) for each and every sample. In Chromium
> in particular (the content_shell binary), this entails going through
> 475k address ranges, which takes a long time when done repeatedly.
> 
> Add a radix-256 trie over the address space to quickly map address to
> compilation unit spaces; for content_shell, which is 1.6 GB when some
> (but not full) debug information turned is on, we go from 6 ms to
> 0.006 ms (6 µs) for each lookup from address to compilation unit, a 1000x
> speedup.
> 
> There is a modest RAM increase of 180 MB in this binary (the existing
> linked list over ranges uses about 10 MB, and the entire perf job uses
> between 2–3 GB for a medium-size profile); for smaller binaries with few
> ranges, there should be hardly any extra RAM usage at all.

While the change looks okay to me in principle (a few comments further
down), I'm concerned of it being tailored to your use case: A long
running process surely will benefit from the speedup. To a short
running process (e.g. addr2line) this may be quite different, and the
increased memory demand and trie setup overhead may become dominant. I
guess there may want to be control over this by the application using
libbfd.

> +/* All trie_node pointers will really be trie_leaf or trie_interior,
> +   but they have this common head.  */
> +struct trie_node
> +{
> +  /* If zero, we are an interior node.
> +     Otherwise, how many ranges we have room for in this leaf.  */
> +  int num_room_in_leaf;

Here and in several more places further down, I think you would better
use "unsigned int". That's imo a general pattern to follow when values
can't go negative. But then again I'm still quite new as a general
maintainer, so I may not know of (unwritten?) rules saying otherwise.

> +};
> +
> +struct trie_leaf
> +{
> +  struct trie_node head;
> +  int num_stored_in_leaf;
> +  struct {
> +    const struct comp_unit *unit;
> +    bfd_vma low_pc, high_pc;
> +  } ranges[TRIE_LEAF_SIZE];
> +};
> +
> +struct trie_interior
> +{
> +  struct trie_node head;
> +  struct trie_node *children[256];
> +};
> +
> +static struct trie_node *alloc_trie_leaf (bfd *abfd)
> +{
> +  struct trie_leaf *leaf =
> +    (struct trie_leaf *) bfd_zalloc (abfd, sizeof (struct trie_leaf));

With C99 now being a requirement (and K&R long not having been supported)
I don't think you need a cast here (and elsewhere in similar cases).

> +  if (leaf != NULL)
> +    leaf->head.num_room_in_leaf = TRIE_LEAF_SIZE;
> +  return (struct trie_node *) leaf;

Furthermore, with casts being somewhat risky in general (and there not
being more fine-grained C++-like casts in C), I think it would be better
to use &leaf->head in such cases. For the opposite conversion Linux and
other projects have a container_of() construct - I couldn't find
anything similar in bfd or libiberty, but I wonder whether something
like that would be worthwhile introducing to increase type-safety.
There are several more casts throughout the patch, with one more flavor
to specifically call out:

> +      if (trie)
> +	{
> +	  const struct trie_leaf *leaf = (struct trie_leaf *) trie;
> +	  int i;
> +
> +	  for (i = 0; i < leaf->num_stored_in_leaf; ++i)
> +	    {
> +	      struct comp_unit *unit = (struct comp_unit *) leaf->ranges[i].unit;

Here you cast away constness. Imo such should only be done in very rare
cases. Avoiding such a cast is as simple as dropping the "const" from
the struct field declaration.

Finally one other concern: Recently a patch was contributed to make
libopcodes usable (for x86) from multi-threaded applications. I don't
know what the respective aims are with libbfd. If the library is meant
to be usable that way, then something would need to be done about races
in the trie accesses. I would hope e.g. Nick or Alan could help clarify
this.

Jan