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

[Steinar H. Gunderson]

On Fri, Apr 08, 2022 at 10:05:55AM +0200, Jan Beulich wrote:
> 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.

Well, if you only run it once, the memory usage won't really be that
high either, as it stops as soon as it finds an appropriate compilation
unit (it inserts incrementally into the tree). So it scales pretty well
downwards as well, just like the existing code does. But that aside,
is it a goal to have a non-long-running addr2line use as little peak
memory as possible?

An alternative would be something like only building the trie after the
first 100 lookups or similar. It should be fairly non-intrusive, but it
would require us to keep more of the old paths around.

> 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.

I'm fine with anything as long as there is some rule. :-) The rest of
the file appeared to me to use mostly int, so I was trying to follow that.

>> +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).

Again, this is just following the rest of the style (and implicit casts
from void* have not changed in C99, from what I know?). Do you want me
to diverge? Change the existing calls?

> 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.

Sure, I can change that.

>> +      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.

The problem is that when we assign it to that struct field, we have it
only as a const. So we need to either const-cast here, at that point,
or all the way up to arange_add().

> 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.

The code already isn't thread-safe, though. It liberally reads in new
debug information from compilation units and inserts into various lists
as it goes. My patch does not really change anything here.

/* Steinar */