addr2line: add label checks when DW_AT_range and DW_AT_low_pc cannot be used

[tig_freebsdfoundation.org]

Summary

Check label's ranges for address we want to translate if a CU doesn't have usable DW_AT_range or DW_AT_low_pc.
Use more appropriate names: "struct CU" -> "struct range"
PR: https://sourceforge.net/p/elftoolchain/tickets/552/

Test Plan

Passing my test with random addresses, sequential addresses, DW_AT_range tests, and label tests.
While testing, I found some small/trivial discrepancy between GNU and elftoolchain output. If you give the program the low_pc of a function(subprogram), GNU will output first line of function's c code that's not a macro. Elftoolchain will output the line that has the opening bracket "{" of the function.

[tig_freebsdfoundation.org]

Check labels seems to be using a lot of memory (20 Mb). There might be a bug somewhere. I'm looking into it.

[tig_freebsdfoundation.org]

It looks like it's just the allocated memory for labels, as most of the memory used by check_labels are given back (freed) according to the picture.
Kernel probably has a lot of assembly files with a lot of labels. Is memory usage a problem?

[markj]

In D23782#522571, @tig_freebsdfoundation.org wrote:

It looks like it's just the allocated memory for labels, as most of the memory used by check_labels are given back (freed) according to the picture.
Kernel probably has a lot of assembly files with a lot of labels. Is memory usage a problem?

Yes, I can imagine that e.g., exception.S generates quite a few labels.

How does the memory usage compare to GNU addr2line? Maybe we can redesign the cache so that it consumes less memory.

[markj]

contrib/elftoolchain/addr2line/addr2line.c

987

There is no harm in calling dwarf_get_aranges() each time you need to use it. libdwarf's implementation first checks to see if it has already initialized the arange array for this particular dbg handle, and simply returns it if so. The first call does the initialization. So this caching that you're doing doesn't really help with anything, I believe.

I also don't think it makes sense to print a warning if dwarf_get_aranges() returns DW_DLV_NO_ENTRY. If you get anything other than DW_DLV_OK or DW_DLV_NO_ENTRY it should probably be a fatal error.

[tig_freebsdfoundation.org]

contrib/elftoolchain/addr2line/addr2line.c

987

I see. Moved dwarf_get_aranges to check_labels and when to print warning.

[markj]

I still have to read check_labels() carefully, but overall I think this is ok.

contrib/elftoolchain/addr2line/addr2line.c

261–263

I think this comment could be a bit more descriptive. :)

265–275

I think this block can be written without a goto:

if (tag != DW_TAG_label) {
   <something>
        goto cont_search;
}

Also, what happens when we have a label without a low_pc attribute?

426

I think a high-level description of what this function is doing would be useful.

[tig_freebsdfoundation.org]

contrib/elftoolchain/addr2line/addr2line.c

265–275

If we have a label without a low_pc attribute, we should goto cont_search since we can't use the current label. I made it more explicit in this revision.

[tig_freebsdfoundation.org]

I think all the comments are addressed. Is there anything else that needs to be fixed? Thanks

[markj]

contrib/elftoolchain/addr2line/addr2line.c

267

Style: indentation should be by four spaces here.

427

"die" should be written "DIE".

485

There's no need to cast the return value of calloc() in C.

500

Indentation by four spaces.

553

I think these comments ("free memory", "return status", "add to cache", etc.) which describe *what* the code is doing are not useful. It's better to ensure that the high-level algorithm is documented, and to write comments that explain *why* the code is doing something when it's not clear.

[tig_freebsdfoundation.org]

Addressed the comments.

[emaste]

contrib/elftoolchain/addr2line/addr2line.c

60

This s/CU/range/ is just for clarity? I'm curious about reordering so die and dbg are at the top now. (Sorry if I missed something in the earlier discussion.)

[markj]

contrib/elftoolchain/addr2line/addr2line.c

60

Yes, I think I asked for the rename since we no longer really assume that a CU can be represented by a single address range. I'm not sure about the purpose of reordering the fields.

[tig_freebsdfoundation.org]

contrib/elftoolchain/addr2line/addr2line.c

60

I don't remember why I reordered the fields. I will revert it.

[emaste]

Looks like this needs to be rebased?

Patching file contrib/elftoolchain/addr2line/addr2line.c using Plan A...
Hunk #1 succeeded at 57 (offset 1 line).
Hunk #2 succeeded at 89 (offset 1 line).
Hunk #3 succeeded at 171 (offset 1 line).
Hunk #4 succeeded at 179 (offset 1 line).
Hunk #5 succeeded at 216 (offset 1 line).
Hunk #6 succeeded at 238 (offset 1 line).
Hunk #7 succeeded at 258 (offset 1 line).
Hunk #8 succeeded at 330 (offset 1 line).
Hunk #9 succeeded at 341 (offset 1 line).
Hunk #10 succeeded at 351 (offset 1 line).
Hunk #11 succeeded at 365 (offset 1 line).
Hunk #12 succeeded at 397 (offset 1 line).
Hunk #13 failed at 421.
Hunk #14 succeeded at 575 (offset 2 lines).
Hunk #15 succeeded at 609 (offset 1 line).
Hunk #16 succeeded at 669 (offset 2 lines).
Hunk #17 succeeded at 682 (offset 1 line).
Hunk #18 succeeded at 725 (offset 2 lines).
Hunk #19 succeeded at 782 (offset 1 line).
Hunk #20 succeeded at 835 (offset 2 lines).
1 out of 20 hunks failed--saving rejects to contrib/elftoolchain/addr2line/addr2line.c.rej
done

[emaste]

contrib/elftoolchain/addr2line/addr2line.c

792

Is this die -> range->die an incidental fix?

[tig_freebsdfoundation.org]

contrib/elftoolchain/addr2line/addr2line.c

792

It would seem so. I don't remember exactly the reason for this change but when translating an address and at label out, range->die will be set to the correct die to use either from a cache lookup or a linear scan. I believe either die and range->die are both ok.

[emaste]

Still not handling the test case from https://sourceforge.net/p/elftoolchain/tickets/552/

with this patch

$ usr.bin/addr2line/obj/addr2line -f -e ~/src/elftoolchain/test/elfdump/ts/dso2/test.so 0xa88
addr2line: dwarf_tag failed: Invalid argument [dwarf_tag(242)]
??
??:0

binutils:

$ /usr/local/bin/addr2line -f -e ~/src/elftoolchain/test/elfdump/ts/dso2/test.so 0xa88
_fini
/home/aurel32/debian/co-packages/glibc/etch/glibc-2.3.6.ds1/build-tree/amd64-libc/csu/crti.S:37

llvm

$ ~/src/llvm-project/build/bin/llvm-addr2line -f -e ~/src/elftoolchain/test/elfdump/ts/dso2/test.so 0xa88
_fini
/home/aurel32/debian/co-packages/glibc/etch/glibc-2.3.6.ds1/build-tree/amd64-libc/csu/crti.S:37

[tig_freebsdfoundation.org]

Initially, I thought _fini is a label in the test case. However, I found, using readelf, that _fini isn't a label in the test case ~/src/elftoolchain/test/elfdump/ts/dso2/test.so. I found it in the symbol table (symtab) instead. Currently, symtab is not checked by addr2line so in order to pass this test a new feature to check symtab is needed.
This patch does help resolve labels addr. For example, when _init is in a DW_TAG_label:

[tig@tiger /usr/home/tig/freebsd-1/lib]$ /usr/local/bin/addr2line -f -e /usr/lib/debug/usr/lib/libdwarf.so.4.debug 0x2edec
_init
/usr/src/lib/csu/amd64/crti.S:34
[tig@tiger /usr/home/tig/freebsd-1/lib]$ /usr/bin/addr2line -f -e /usr/lib/debug/usr/lib/libdwarf.so.4.debug 0x2edec
init
/usr/src/lib/csu/amd64/crti.S:34

Maybe we should commit this patch first and have the symtab support as future work?

[emaste]

Maybe we should commit this patch first and have the symtab support as future work?

Yes, I'll commit it soon. I had a few style/whitespace fixes that I rolled in to my WIP (e.g. function signatures over 80 cols).

contrib/elftoolchain/addr2line/addr2line.c

586

Swapped these around in FreeBSD in rS367853

[emaste]

contrib/elftoolchain/addr2line/addr2line.c

617

could we actualy return anything other than DW_DLV_OK or DW_DLV_NO_ENTERY before?

[tig_freebsdfoundation.org]

contrib/elftoolchain/addr2line/addr2line.c

617

I believe this function has always been returning either DW_DLV_OK or DW_DLV_NO_ENTRY