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

[Steinar H. Gunderson]

On Fri, Apr 08, 2022 at 10:50:37AM +0200, Jan Beulich wrote:
>> 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?
> If we were talking of just a few kb, I think it wouldn't matter. But
> for large binaries I think the peak could be quite a bit higher with
> your change in place.

Let's try to quantify it a bit. Here's content_shell from chromium,
running addr2line over a single address and then immediately exiting.
Before this change:

  calls to allocation functions: 172864 (406738/s)
  temporary memory allocations: 62124 (146174/s)
  peak heap memory consumption: 1.46G
  peak RSS (including heaptrack overhead): 1.47G
  total memory leaked: 5.60K

After:

  calls to allocation functions: 193686 (412097/s)
  temporary memory allocations: 62124 (132178/s)
  peak heap memory consumption: 1.54G
  peak RSS (including heaptrack overhead): 1.55G
  total memory leaked: 5.60K

So it's up about 5% in terms of RSS (this doesn't count the OS cache
needed to read in the binary, if any). Let's look at the case where I
give in an address that doesn't correspond to a source line at all, ie.,
it has to consume the entire binary. Before:

  calls to allocation functions: 38786514 (1640368/s)
  temporary memory allocations: 6312506 (266970/s)
  peak heap memory consumption: 7.68G
  peak RSS (including heaptrack overhead): 8.18G
  total memory leaked: 8.53M

After:

  calls to allocation functions: 38835333 (1516886/s)
  temporary memory allocations: 6311800 (246535/s)
  peak heap memory consumption: 7.88G
  peak RSS (including heaptrack overhead): 8.37G
  total memory leaked: 8.53M

So that's a bit over 2% in terms of RSS. And this is memory that goes
away immediately after addr2line exits, ie. number of byte-seconds is
going to be low. (And you could argue many other things are more
wasteful; e.g. we spend 1.5 GB of that RSS holding tons and tons of
copies of the exact same filenames, from concat_filename().)

For a smaller binary like /bin/ls, we go from 5.43 MB to 5.46 MB
(for reading all of it).

>> 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.
> Some heuristic like this may also do, yes. Nevertheless I think it
> would be better for the application to provide an indication. After
> all, if addr2line was called with dozens of addresses, it might
> benefit as well (so such a heuristic would better live there than
> in the library).

I'm not too sold on moving the heuristics into the caller, for the
simple reason that there are a lot of potential callers. This means we'd
first need to define a new API, get a new binutils version out, go hunt
all relevant callers that could be ever interested in looking up debug
lines, and convince each of their maintainers to add a check for the new
binutils version to call that API (plus heuristics). All to get behavior
of “reasonable performance for large binaries”, which I believe is
something most of them already expected. :-)

If you put the heuristic in the library, addr2line would automatically
benefit without changing it. There's already precedent for this kind of
heuristic in libbfd as far as I can see, pretty much in the same area of
code:

   /* Number of times find_line is called.  This is used in
     the heuristic for enabling the info hash tables.  */
  int info_hash_count;
  
  #define STASH_INFO_HASH_TRIGGER    100

> They haven't changed in C99, but apparently there were very old
> compilers (hence my reference to K&R) which issued diagnostics for
> such conversions.

GCC has an optional warning for it, FWIW.

/* Steinar */