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

[Jan Beulich]

On 08.04.2022 13:03, Steinar H. Gunderson wrote:
> 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).

Hmm, okay, that's not all that much of an increase. I withdraw my
respective request.

Jan