Added Single Entry Cache to addr2line

[tig_freebsdfoundation.org]

Summary

Added single entry cache that stores last low and high addresses of last DIE(dwarf information entry) as well as last DIE. In translate(), first check if it is a cache hit, if so skip the lookup. Otherwise loop from the current CU -> last CU -> CU before current CU to find which DIE contains the address and save the DIE to cache.
Edit: added random access support.

Test Plan

compare output and performance on kernel addresses with gnu addr2line's output.
Tested against random addresses and sequential addresses. Seems to work.

[emaste]

Looks like the diff is the wrong way around and also the context is missing - https://wiki.freebsd.org/Phabricator has example commands you can copy and use

[tig_freebsdfoundation.org]

Updated.

[tig_freebsdfoundation.org]

I realized I need to change a small piece of code to support random access. Will update once done.

[tig_freebsdfoundation.org]

Added random support in. The revision is ready for review now.

[markj]

Let's focus on code correctness and clarity first, but I'd also encourage you to read our C style man page: "man style". The same style is used by ELFToolchain. In particular, wrapped lines should be indented by four spaces. For example:

ret = long_function_name_with_many_arguments(foo1, foo2, ...
    bar);

We also only use C-style comments, delimited by /* */. C++ one-line comments, using //, are discouraged.

contrib/elftoolchain/addr2line/addr2line.c

412

How do we know that last_die is valid here? Suppose addr2line is given two addresses as input. The first address is valid, and results in last_die being set. The second address is invalid (i.e., doesn't match any CU). When we process the first address, we will cache the DIE for its CU. When processing the second address, we will free last_die and set it to NULL, but locache and hicache are still left with their old values. So, when processing a third address, we may goto status_ok even though last_die is NULL.

424

As I understand it, this means that on a cache miss, we will resume the CU scan from the last place where we found a match. Is there any specific reason to do it that way? Why not always restart the search from the beginning on a cache miss.

500

Why not replace all instances of "goto not_found" with "goto out"?

504

I think it would be clearer if cache invalidation and cache insertion were done in the same place. That is, it is kind of confusing that last_die is freed above. Instead, you could keep last_die valid in the cache until a new match is found, instead of invalidating as soon as there is a cache miss. I think this should result in fewer gotos and make the control flow easier to follow.

[markj]

This is looking better.

contrib/elftoolchain/addr2line/addr2line.c

421

The indentation here is still wrong.

424

I still can't see the reason for this.

453

Can you explain this check? I don't quite see why it's there.

609–610

Is it possible to have die != last_die here?

[tig_freebsdfoundation.org]

contrib/elftoolchain/addr2line/addr2line.c

424

Because when we have 2 sequential addresses, and the second one is of the next CU, it is faster to just go to the next CU instead of starting from the beginning.

424

From My understanding:
CU1: ffff0000-ffff0100
...
CU10: ffff1000 - ffff1100
CU11: ffff1100 - ffff1200
We give the program:
ffff1098
ffff1105
If we scan from the last place we found a match (CU10), we call dwarf_next_cu_header once.
If we scan from the beginning, we call dwarf_next_cu_header 11 times and go through the loop 11 times.
Not sure if I'm correct though.

453

This is if we scanned across all the CU's and get back to where we started, we want to go to out because we cannot translate this address.

609–610

I guess DIE always equals last_die

[markj]

contrib/elftoolchain/addr2line/addr2line.c

409

Shouldn't it be last_die != NULL?

424

Got it. You might consider adding a short comment above the goto next_cu to explain this.

453

I see. But if the cache is invalid, this check will fail.

[tig_freebsdfoundation.org]

contrib/elftoolchain/addr2line/addr2line.c

453

But I think we will only get here when cache is valid. If the cache is invalid it will keep looping until it finds the die addr lies in.

[tig_freebsdfoundation.org]

contrib/elftoolchain/addr2line/addr2line.c

453

Only need this check**

[tig_freebsdfoundation.org]

contrib/elftoolchain/addr2line/addr2line.c

453

Only need this check on a cache miss.

[markj]

contrib/elftoolchain/addr2line/addr2line.c

453

Sorry, I was not specific enough. If the cache is invalid *and* the address is invalid, we will never exit the loop.

[tig_freebsdfoundation.org]

contrib/elftoolchain/addr2line/addr2line.c

453

I think initializing locache and checking locache is not initial value after we scan all CU's should fix it.

[tig_freebsdfoundation.org]

contrib/elftoolchain/addr2line/addr2line.c

412

I think we can remove the "else if" case since we changed next_cu to not invalidate cache until cache insertion. Next_cu now frees die if die is not NULL but die is always NULL in the "else if" case.

[markj]

This looks good to me.

[emaste]

Tree-based cache added in rS357450 instead