Handle overlapping ranges

[philipc]

This assert triggers for some binaries.

May also need better validation of ranges in general. May also want to ignore ranges that begin at 0. Also see #49 for some changes that may be required.

[main--]

Hm. I did run across some invalid ranges like the 1..1 you mention in #49, which is why I'm trying to filter those out with the start != end check. Perhaps there is a way to identify the other invalid ranges as well?

If there really is no other way, we could use an interval tree here as well, but I'd really like to avoid dropping unit ranges entirely. Is there any legitimate reason for multiple compilation units to describe the same address ranges?

[philipc]

My memory of #49 is that we failed to return a result for some addresses. The line table had entries for the addresses, but the unit ranges were missing. I'll try to reproduce this again.

I don't think there's any legitimate reason for multiple CUs to cover the same range. I've seen many invalid ranges starting at 0 though, which should be easy to filter out if needed.

In theory, the unit ranges and the line ranges should be identical, so the only advantage of the unit ranges is they are faster to parse, but if they do match the address then we need to parse the line ranges anyway. Also, it's the line ranges that have the information we want, so they should always be more accurate. There's also .debug_aranges which should be an even faster map of address to unit, but I think it's often broken (this is what eu-addr2line uses, and I think that's why it doesn't work).

[main--]

AFAIK .debug_aranges is optional and many compilers just don't generate it at all (I think clang does but rustc doesn't).

Unit ranges allow lazy parsing of units (don't look at the line number program until you need it), I think that may be a nice optimization.

[sfackler]

I'm seeing this on nightly build (https://circleci.com/gh/sfackler/rstack/23), but not a stable build of the same commit (https://circleci.com/gh/sfackler/rstack/22). Might be caused by rust-lang/rust#45511?

[philipc]

Using a nightly older than nightly-2017-10-24 didn't fix the problem for rstack, so it's not rust-lang/rust#45511.

[philipc]

For rstack, the issue is a couple of compilation units that use low_pc/high_pc to specify the range, but the low_pc is 0. Both units contain a single subprogram that also has a low_pc of 0. I suspect this is similar to the 1..1 ranges that occur elsewhere, but it gets handled wrongly because there's only one subprogram in the unit.

For the other binaries I've tested on, there are subprograms that have debuginfo in multiple units, and this is a relatively common occurrence. These seem to all be C++ constructors/destructors, so I suspect this is the compiler generating multiple copies and combining them when linking.

[philipc]

Investigating #49 again, I was mistaken about what was happening there. Here's the problem cases I have found.

1. A unit may specify DW_AT_low_pc = 0, and have no DW_AT_high_pc or DW_AT_ranges, but still have valid line sequences. I've seen this with clang 3.4. I don't care too much about this one, but other tools handle it, and if we can get it for free then we should.

2. A unit may contain a single subprogram, and both the unit and subprogram specify DW_AT_low_pc = 0, and .debug_lines has a sequence starting at 0. This was seen for rstack.

3. A function may have DW_AT_low_pc = 0, and a corresponding line sequence starting at 0. Inlined subroutines within that function are relative to that, so they are also invalid addresses, but they may not start at 0. This is a more general case of (2), and doesn't trigger the assert because it's not in the unit ranges.

4. A function may appear in multiple units. Usually the address range for the function will be identical in every unit, but not always, and I don't know how to determine which one is valid in that case. I think this occurs for automatically generated code in C++ (eg destructors).

5. For rust, if LTO inlines into main or __rust_oom then there are line sequences for the inlined functions, but nothing in .debug_info. This could probably be fixed in rust by specifying debug metadata for main and __rust_oom, but I'm not sure if this can happen in more instances.

6. libxul.so from firefox 56.0+build6-0ubuntu0.16.04.2 has some weirdness in one unit generated by rustc 1.17.0. Some functions are missing from .debug_info, and the line sequences only cover the tail end of the functions. Not a problem for firefox 57.0, so probably can ignore this one.

So I think 3 changes are possible:

• remove the assert, to allow for (4). This happens for functions that are actually the same, so I don't think this affects correctness.
• stop using unit ranges, and use only line sequences, to allow for (1) and (5). Neither are high priority to fix, but I don't see any downside to doing this.
• ignore line sequences and functions with address 0, to allow for (2) and (3). Ignoring inlined subroutines in this case may be tricky. This change isn't really necessary if you only ever look up valid addresses, but with the currently algorithm, looking up an address such as 0 or 1 can give you a very long call trace, since it thinks there are many functions at that address.

[philipc]

Unit ranges allow lazy parsing of units (don't look at the line number program until you need it), I think that may be a nice optimization.

This is true for the first lookup of an address that isn't in that unit. But lookups of addresses in that unit will be slower both for the first and subsequent lookups since you need to do a binary search for both the unit ranges and the line sequences (unless you discard the unit ranges once you have parsed sequences).