[DWARF] Change ambiguity resolution from smallest CUOffset to largest (LowPC, CUOffset)

[MaskRay]

Summary

When constructing debug aranges, if ranges overlap, we currently pick
the CU with the smallest CUOffset. This patch changes the rule to the
largest (LowPC, CUOffset).

--gc-sections and comdat may discard sections. The associated compile
units may be kept and have zero DW_AT_low_pc. If the DW_AT_high_pc is
sufficiently large, it may overlap with a good one.

llvm-symbolizer may resolve an address in the good CU to the discarded
CU. By giving priority to the largest (LowPC, CUOffset), the good one
will win. Some incorrect resolution will be fixed.

This patch also drops the Aranges.back().setHighPC(E.Address);
optimization because that is not very useful. N CUs can have at most
2*N-1 ranges.

In practice, overlapping only happens with such [0,high_pc) sections.
This optimization saves no more than M ranges where M is the number of
garbage collected CUs that overlap with a good CU.

[dblaikie]

What does addr2line (or any other symbolizers, not that I know of others) do in these cases?

How's this compare/contrast with the lld change that's being made to achieve similar results? (does this remove the need for the lld change?)

[MaskRay]

What does addr2line (or any other symbolizers, not that I know of others) do in these cases?

addr2line doesn't use binary search. It iterates all ELF sections, finds the first section containing the address, then iterates DWARF CUs and finds the associated line table. It has the same problem and is computationally more expensive:

% addr2line -e res.out 0x2010f0
/tmp/c/not_used.cpp:2

How's this compare/contrast with the lld change that's being made to achieve similar results? (does this remove the need for the lld change?)

This patch drops one minor space optimization, and changes the arbitrary *ValidCUs.begin() (prefer smallest CUOffset) to LiveCUs.rbegin() (prefer largest LowPC). It thus fixes an issue similar to D59553. After this patch, for an address in a non-discarded CU, it will not be incorrectly attributed to the discarded CU if the discarded CU also contains that address.

The D59553 lld change will resolve a relocation to a discarded DW_AT_low_pc to -2. It will make the DW_AT_low_pc=0 scenario not happen for lld-linked executables/DSOs (note, ld.bfd and gold still use zero DW_AT_low_pc). It won't affect other overlapping CU scenarios. We still need a rule defensively and I think (largest LowPC) is probably better than (smallest CUOffset).

[dblaikie]

In D60470#1460670, @MaskRay wrote:

What does addr2line (or any other symbolizers, not that I know of others) do in these cases?

addr2line doesn't use binary search. It iterates all ELF sections, finds the first section containing the address, then iterates DWARF CUs and finds the associated line table. It has the same problem

Any idea why this problem hasn't been much of an issue until now/recently (both your change here, and the LLD change being reviewed)?

and is computationally more expensive:

% addr2line -e res.out 0x2010f0
/tmp/c/not_used.cpp:2

How's this compare/contrast with the lld change that's being made to achieve similar results? (does this remove the need for the lld change?)

This patch drops one minor space optimization, and changes the arbitrary *ValidCUs.begin() (prefer smallest CUOffset) to LiveCUs.rbegin() (prefer largest LowPC). It thus fixes an issue similar to D54747. After this patch, for an address in a non-discarded CU, it will not be incorrectly attributed to the discarded CU if the discarded CU also contains that address.

The D54747 lld change will resolve a relocation to a discarded DW_AT_low_pc to -2. It will make the DW_AT_low_pc=0 scenario not happen for lld-linked executables/DSOs (note, ld.bfd and gold still use zero DW_AT_low_pc). It won't affect other overlapping CU scenarios. We still need a rule defensively and I think (largest LowPC) is probably better than (smallest CUOffset).

[MaskRay]

Any idea why this problem hasn't been much of an issue until now/recently (both your change here, and the LLD change being reviewed)?

These .debug_info sections associated with garbage collected sections have low_pc/high_pc pairs in this form: [0, high_pc) (their DW_AT_low_pc relocations resolve to zero).

ld.bfd sets default image base to 0x400000 for x86_64, thus the first good CU will have DW_AT_low_pc slightly larger than 0x400000. That bad CU needs to have DW_AT_high_pc larger than 0x400000 (4MiB) to overlap with a good CU. I think it is not common to have a >4MiB text section with -ffunction-sections -fdata-sections -Wl,--gc-sections.

lld has a different section layout. Its default image base is 0x200000 (2MiB) but it places potentially large sections .dynsym .rodata .eh_frame before .text. If the application is complex enough to have >2MiB .text.*, I'm fairly confident it should have sufficient large .rodata to move .text far away from the bad CU.

[12] .rodata           PROGBITS        000000000020b950 00b950 006118 00 AMS  0   0 16                       
...
[15] .eh_frame         PROGBITS        0000000000222330 022330 01a494 00   A  0   0  8                       
[16] .text             PROGBITS        000000000023d000 03d000 0f6339 00  AX  0   0 16

So the llvm-symbolizer fix is probably most useful for ld.bfd/gold linked executables.

[jhenderson]

In D60470#1462002, @dblaikie wrote:

In D60470#1460670, @MaskRay wrote:

What does addr2line (or any other symbolizers, not that I know of others) do in these cases?

addr2line doesn't use binary search. It iterates all ELF sections, finds the first section containing the address, then iterates DWARF CUs and finds the associated line table. It has the same problem

Any idea why this problem hasn't been much of an issue until now/recently (both your change here, and the LLD change being reviewed)?

It's not even a new issue. We've had this problem for years in the PlayStation proprietary linker, because ASLR-enabled executables have a 0 base address. We have special handling of discarded functions to work around this in the linker.

[MaskRay]

It's not even a new issue. We've had this problem for years in the PlayStation proprietary linker, because ASLR-enabled executables have a 0 base address.

Ah, right! I forgot about the PIE case.

if (Config->ImageBase) // --image-base= option
  return *Config->ImageBase;
return Config->Pic ? 0 : DefaultImageBase; // otherwise, image base is 0 if -shared or -pie

-static makes it easier to run into this problem as there is no huge .dynsym .dynstr. lld's different section layout alleviates the problem due to its placement of .rodata .eh_frame before .text.

[MaskRay]

Ping :)

[dblaikie]

What happens if a program is linked from some objects with debug info and some objects without it?

It sounds like this solution might not address that case (in this case, there might be no ambiguity - only one CU would have an address range covering the instruction address - but that instruction address would have no real debug info).

Should we use a different solution? Is GNU addr2line's solution robust, if slow? Or does it still fail in these sort of cases? & if it isn't complete, should we settle for fixing the linker & not try to partially support this in the symbolizer if it necessarily can't be complete in general?

[t.p.northover]

Have you run make check on this patch?

[MaskRay]

In D60470#1467587, @t.p.northover wrote:

Have you run make check on this patch?

If you meant llvm-objdump -exports-trie. It was my problem and I apologize for the llvm-objdump test failure I caused. Or https://reviews.llvm.org/D60376 where I didn't notice BSD sed's escape character support for y command is different from GNU sed on Linux. ("The meaning of a <backslash> followed by any character that is not 'n', a <backslash>, or the delimiter character is undefined."). Thank you for telling that there is ninja check beside check-all check-llvm ..., but those discussions are unrelated to this revision.

[smeenai]

In D60470#1467862, @MaskRay wrote:

In D60470#1467587, @t.p.northover wrote:

Have you run make check on this patch?

If you meant llvm-objdump -exports-trie. It was my problem and I apologize for the llvm-objdump test failure I caused. Or https://reviews.llvm.org/D60376 where I didn't notice BSD sed's escape character support for y command is different from GNU sed on Linux. ("The meaning of a <backslash> followed by any character that is not 'n', a <backslash>, or the delimiter character is undefined."). Thank you for telling that there is ninja check beside check-all check-llvm ..., but those discussions are unrelated to this revision.

check is just an alias for check-llvm.

[MaskRay]

What happens if a program is linked from some objects with debug info and some objects without it?

This revision doesn't change the behavior. For the address ranges with no debug info, the results remain ??:0:0 (unknown).

It sounds like this solution might not address that case (in this case, there might be no ambiguity - only one CU would have an address range covering the instruction address - but that instruction address would have no real debug info).

The motivation was to mitigate some issues of lld-linked modules => my approach is general and doesn't discuss anything specific as zero addresses, etc => this patch seems a bit useful for ld.bfd/gold linked modules (reasons at https://reviews.llvm.org/D60470#1462246)

Should we use a different solution? Is GNU addr2line's solution robust, if slow? Or does it still fail in these sort of cases? &

I mentioned before (https://reviews.llvm.org/D60470#1460670) that addr2line's linear search can be faulty, as demonstrated by the following command:

% addr2line -e res.out 0x2010f0
/tmp/c/not_used.cpp:2

Linear search doesn't look more robust, but it is assuredly slow.

if it isn't complete, should we settle for fixing the linker & not try to partially support this in the symbolizer if it necessarily can't be complete in general?

This revision doesn't do any "involved" logic. It changes the rule about which range prevails when several ranges overlap. I even deleted a not useful "optimization"(trade-off) that (I think) cluttered the code.

[dblaikie]

In D60470#1467875, @MaskRay wrote:

What happens if a program is linked from some objects with debug info and some objects without it?

This revision doesn't change the behavior. For the address ranges with no debug info, the results remain ??:0:0 (unknown).

Ah, sorry, that's not the case I was interested in. I meant a case where two object files are linked together - one has debug info, one does not. They both have a comdat function. The non-debug info version is chosen (creating the [0, X) address range in the debug info from the other object).

If I understand it, this change is to the prioritization/resolution of ambiguities - but similar situations/bugs can arise when there is no ambiguity (because some code has no debug info - so it's not there to create an ambiguity). if I'm understanding/explaining correctly.

[MaskRay]

Ah, sorry, that's not the case I was interested in. I meant a case where two object files are linked together - one has debug info, one does not. They both have a comdat function. The non-debug info version is chosen (creating the [0, X) address range in the debug info from the other object).

If the linker makes the comdat function without debug info (assuming the debug info is not in a comdat) prevailing, the one with debug info is discarded while its debug info is kept. This is essentially the same as the --gc-sections case.

The compile unit with 0 DW_AT_low_pc is actually invalid because the addresses are incorrect. It should be ignored if it overlaps with a valid range when constructing aranges. This patch will do so.

If I understand it, this change is to the prioritization/resolution of ambiguities - but similar situations/bugs can arise when there is no ambiguity (because some code has no debug info - so it's not there to create an ambiguity). if I'm understanding/explaining correctly.

Yes, it is related to the resolution of ambiguities. The old rule is to pick the CU with the smallest E.CUOffset; the new rule is to pick the CU with the largest (E.LowPC, E.CUOffset) pair.

[MaskRay]

Update description

[dblaikie]

In D60470#1469679, @MaskRay wrote:

Ah, sorry, that's not the case I was interested in. I meant a case where two object files are linked together - one has debug info, one does not. They both have a comdat function. The non-debug info version is chosen (creating the [0, X) address range in the debug info from the other object).

If the linker makes the comdat function without debug info (assuming the debug info is not in a comdat) prevailing, the one with debug info is discarded while its debug info is kept. This is essentially the same as the --gc-sections case.

The compile unit with 0 DW_AT_low_pc is actually invalid because the addresses are incorrect. It should be ignored if it overlaps with a valid range when constructing aranges. This patch will do so.

If I understand it, this change is to the prioritization/resolution of ambiguities - but similar situations/bugs can arise when there is no ambiguity (because some code has no debug info - so it's not there to create an ambiguity). if I'm understanding/explaining correctly.

Yes, it is related to the resolution of ambiguities. The old rule is to pick the CU with the smallest E.CUOffset; the new rule is to pick the CU with the largest (E.LowPC, E.CUOffset) pair.

What I'm trying to ask is - it sounds like this is about resolution of an ambiguity between the wrong answer (the zero-based entry due to a comdat function not being chosen, or a gc-section being GC'd - but where the address range, even zero based, overlaps with executable code) and the right one (the one with a non-zero low pc).

So what I'm asking is: what happens if the right one isn't there (because that code wasn't built with debug info) - would we still get the wrong answer?

[MaskRay]

So what I'm asking is: what happens if the right one isn't there (because that code wasn't built with debug info) - would we still get the wrong answer?

We still get the wrong answer. Say there is an invalid [0, 0x201000). [0x200100, 0x220000) is part of the .text section but it isn't associated with a compile unit. When you resolve any address in [0x200100, 0x201000) (valid address ranges), it resolves to the invalid [0, 0x201000). This is the status quo and this patch doesn't change it.

This is because the code doesn't know if a compile unit should be ignored or not. This patch just changes priority.

[MaskRay]

Ping :) Whatever the lld resolution of D59553 is, this is at least useful for ld.bfd/gold linked modules. And this patch simplifies the logic.

[MaskRay]

Ping 😊

[dblaikie]

Fair point about this still being useful, even if we figure out a longer term/broader/more complete fix.

Does this fix work if the overlapping ranges come from the same CU, though? (if a CU had debug_ranges (or no CU level ranges and two subprograms one at [0, 10) and the other at [5, 15), for example?)

include/llvm/DebugInfo/DWARF/DWARFDebugAranges.h

struct Range {
 
     uint64_t LowPC; /// Start of address range.
     uint32_t Length; /// End of address range (not including this address).
     uint32_t CUOffset; /// Offset of the compile unit or die.
   };
 
   struct RangeEndpoint {
     uint64_t Address;
+    uint64_t LowPC;
     uint32_t CUOffset;
-    bool IsRangeStart;
 
-    RangeEndpoint(uint64_t Address, uint32_t CUOffset, bool IsRangeStart)
-        : Address(Address), CUOffset(CUOffset), IsRangeStart(IsRangeStart) {}
+    RangeEndpoint(uint64_t Address, uint64_t LowPC, uint32_t CUOffset)
+        : Address(Address), LowPC(LowPC), CUOffset(CUOffset) {}
 
     bool operator<(const RangeEndpoint &Other) const {
       return Address < Other.Address;
     }
   };
 
   using RangeColl = std::vector<Range>;
   using RangeCollIterator = RangeColl::const_iterator;

lib/DebugInfo/DWARF/DWARFDebugAranges.cpp

void DWARFDebugAranges::clear() {
   Aranges.clear();
   ParsedCUOffsets.clear();
 }
 
 void DWARFDebugAranges::appendRange(uint32_t CUOffset, uint64_t LowPC,
                                     uint64_t HighPC) {
   if (LowPC >= HighPC)
     return;
-  Endpoints.emplace_back(LowPC, CUOffset, true);
-  Endpoints.emplace_back(HighPC, CUOffset, false);
+  Endpoints.emplace_back(LowPC, LowPC, CUOffset);
+  Endpoints.emplace_back(HighPC, LowPC, CUOffset);
 }
 
 void DWARFDebugAranges::construct() {
-  std::multiset<uint32_t> ValidCUs;  // Maintain the set of CUs describing
-                                     // a current address range.
+  // Maintain the set of CUs that cross the sweep line.
+  std::multiset<std::pair<uint64_t, uint32_t>> LiveCUs;
   llvm::sort(Endpoints);
   uint64_t PrevAddress = -1ULL;
   for (const auto &E : Endpoints) {
-    if (PrevAddress < E.Address && !ValidCUs.empty()) {
-      // If the address range between two endpoints is described by some
-      // CU, first try to extend the last range in Aranges. If we can't
-      // do it, start a new range.
-      if (!Aranges.empty() && Aranges.back().HighPC() == PrevAddress &&
-          ValidCUs.find(Aranges.back().CUOffset) != ValidCUs.end()) {
-        Aranges.back().setHighPC(E.Address);
-      } else {
-        Aranges.emplace_back(PrevAddress, E.Address, *ValidCUs.begin());
-      }
-    }
-    // Update the set of valid CUs.
-    if (E.IsRangeStart) {
-      ValidCUs.insert(E.CUOffset);
-    } else {
-      auto CUPos = ValidCUs.find(E.CUOffset);
-      assert(CUPos != ValidCUs.end());
-      ValidCUs.erase(CUPos);
-    }
+    // Add a new range. If there are multiple live CUs, pick the one with the
+    // largest LowPC.
+    //
+    // In a --gc-sections link, a .debug_info associated with a discarded section
+    // may not be discarded and has zero DW_AT_low_pc. If its DW_AT_high_pc is
+    // sufficiently large, it may overlap with a good one. Use this heuristic to
+    // let the good one prevail.
+    if (PrevAddress < E.Address && !LiveCUs.empty())
+      Aranges.emplace_back(PrevAddress, E.Address, LiveCUs.rbegin()->second);
+    // For a LowPC event, add a CU; for a HighPC event, remove a CU.
+    if (E.Address == E.LowPC)
+      LiveCUs.emplace(E.LowPC, E.CUOffset);
+    else
+      LiveCUs.erase(LiveCUs.find({E.LowPC, E.CUOffset}));
     PrevAddress = E.Address;
   }
-  assert(ValidCUs.empty());
+  assert(LiveCUs.empty());
 
   // Endpoints are not needed now.
   Endpoints.clear();
   Endpoints.shrink_to_fit();
 }
 
 uint32_t DWARFDebugAranges::findAddress(uint64_t Address) const {
   RangeCollIterator It =
       llvm::upper_bound(Aranges, Address, [](uint64_t LHS, Range RHS) {
         return LHS < RHS.HighPC();
       });
   if (It != Aranges.end() && It->LowPC <= Address)
     return It->CUOffset;
   return -1U;
 }

test/tools/llvm-symbolizer/gc-sections-zero-low-pc.s

+# RUN: llvm-mc -filetype=obj -triple x86_64-pc-linux %s -o %t
+# RUN: llvm-symbolizer --obj=%t 0x1fffff 0x200000 0x200003 0x200004 | FileCheck %s
+
+# 0.c spans [0x0, 0x200010). Zero DW_AT_low_pc due to discarded relocation.
+# 1.c spans [0x200000, 0x200004)
+# 0.c's code is garbage collected but its debug info is left in %t.
+# We want [0x200000, 0x200004) to symbolize to 1.c
+# Ideally other addresses don't symbolize to 0.c since it is garbage collected,
+# but we currently fail to do so.
+
+# CHECK: 0.c:1:0
+# CHECK: 1.c:1:0
+# CHECK: 1.c:1:0
+# CHECK: 0.c:1:0
+
+.section .debug_abbrev,"",@progbits
+  .byte 1     # Abbreviation Code
+  .byte 17    # DW_TAG_compile_unit
+  .byte 1     # DW_children_yes
+  .byte 16    # DW_AT_stmt_list
+  .byte 23    # DW_FROM_sec_offset
+  .byte 17    # DW_AT_low_pc
+  .byte 1     # DW_FORM_addr
+  .byte 18    # DW_AT_high_pc
+  .byte 6     # DW_FORM_data4
+  .byte 0     # EOM(1)
+  .byte 0     # EOM(2)
+  .byte 2     # Abbreviation Code
+  .byte 46    # DW_TAG_subprogram
+  .byte 0     # DW_children_no
+  .byte 3     # DW_AT_name
+  .byte 8     # DW_FORM_string
+  .byte 17    # DW_AT_low_pc
+  .byte 1     # DW_FORM_addr
+  .byte 18    # DW_AT_high_pc
+  .byte 6     # DW_FORM_data4
+  .byte 0     # EOM(1)
+  .byte 0     # EOM(2)
+  .byte 0     # EOM(3)
+
+.section .debug_info,"",@progbits
+.macro define_cu i, low_pc, high_pc
+.Lcu_begin\i:
+  .long .Lcu_end\i - .Lcu_begin\i - 4 # Length of Unit
+  .short 5                            # DWARF version number
+  .byte 1                             # DWARF Unit Type
+  .byte 8                             # Address Size (in bytes)
+  .long .debug_abbrev                 # Offset Into Abbrev.
+  .byte 1                             # Abbrev [1]
+  .long .Lline_table_start\i          # DW_AT_stmt_list
+  .quad \low_pc                       # DW_AT_low_pc
+  .long \high_pc                      # DW_AT_high_pc
+    .byte 2                           # Abbrev [2] DW_TAG_subprogram
+    .if \i
+    .asciz "1.c"                      # DW_AT_name
+    .else
+    .asciz "0.c"                      # DW_AT_name
+    .endif
+    .quad \low_pc                     # DW_AT_low_pc
+    .long \high_pc                    # DW_AT_high_pc
+    .byte 0
+.Lcu_end\i:
+.endm
+
+define_cu 0, 0x0, 0x200010
+define_cu 1, 0x200000, 0x4
+
+.section .debug_line,"",@progbits
+
+# Define line tables for 0.c and 1.c. They differ in the name and addresses.
+.irp i, 0, 1
+.Lline_table_start\i:
+  .long   .Lline_table_end\i - .Lline_table_start\i - 4 # Length of Unit
+  .short  5               # DWARF version number
+  .byte   8               # Address Size
+  .byte   0               # Segment Selector Size
+  .long   .Lline_table_header_end\i - .Lline_table_params\i # Length of Prologue
+.Lline_table_params\i:
+  .byte   1               # Minimum Instruction Length
+  .byte   1               # Maximum Operations per Instruction
+  .byte   1               # Default is_stmt
+  .byte   -5              # Line Base
+  .byte   14              # Line Range
+  .byte   13              # Opcode Base
+  .byte   0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1 # Standard Opcode Lengths
+  # Directory table format
+  .byte   1               # One element per directory entry
+  .byte   1               # DW_LNCT_path
+  .byte   0x08            # DW_FORM_string
+  # Directory table entries
+  .byte   1               # 1 directory
+  .asciz  "/tmp"
+  # File table format
+  .byte   2               # 2 elements per file entry
+  .byte   1               # DW_LNCT_path
+  .byte   0x08            # DW_FORM_string
+  .byte   2               # DW_LNCT_directory_index
+  .byte   0x0b            # DW_FORM_data1
+  # File table entries
+  .byte   1               # 1 file
+  .if \i
+  .asciz "1.c"
+  .else
+  .asciz "0.c"
+  .endif
+  .byte   0
+.Lline_table_header_end\i:
+.if \i
+  .byte   0,9,2                # DW_LNE_set_address
+  .quad   0x200000
+  .byte   1                    # DW_LNS_copy
+  .byte   75                   # Addr += 4, Line += 1
+  .byte   0,1,1                # DW_LNE_end_sequence
+.else
+  .byte   1                    # DW_LNS_copy
+  .byte   2,0x90,0x80,0x80,0x1 # DW_LNS_advance_pc 0x200010
+  .byte   0,1,1                # DW_LNE_end_sequence
+.endif
+.Lline_table_end\i:
+.endr