[lldb/DWARF] Add more line table validation

[labath]

Summary

The intention here is to prune out line sequences addresses referring
outside any known sections. Such line sequences are typically produced
by dead-stripped code, which leaves behind some debug info.

These line sequences were pretty much ignored already -- they would fail
at the LineTable::ConvertEntryAtIndexToLineEntry stage. However, they
still made it into the line table and into the "image dump line-table"
output, which was printing random nonsense as a result.

This avoids putting these sequences into the line table in the first
place, which makes them smaller (some files have a lot of dead line
sequences) and hopefully slightly speeds up code which iterates through
the line table linearly.

It also makes the "image dump line-table" output sane, which means I can
write my test for handling of different linker tombstoning behaviors.

Depends on D84401.

[labath]

lldb/test/Shell/SymbolFile/DWARF/debug_line-tombstone.s

35–36

The bogus output I'm talking about would end up looking like:

0x0000000000000000: :4294967295
0x0000000000000001: :4294967295
...

[dblaikie]

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

1044

Could you specifically look for/propagate tombstones here, to reduce the risk of large functions overlapping with the valid address range, even when they're tombstoned to zero? (because zero+large function size could still end up overlapping with valid code)

To do that well, I guess it'd have to be implemented at a lower-layer, inside the line table state machine - essentially dropping all lines derived from a "set address" operation that specifies a tombstone.

[clayborg]

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

1044

Just checking if the section lists contains an address doesn't help weed out addresses that were tombstoned to zero since our PT_LOAD[0] will almost always contain zero for shared libraries. It might be nice to make a list of addresses that come from sections with read + execute permissions and store that in SymbolFileDWARF one time at startup. Then these searches will be faster as we are looking in less ranges, and most likely will not contain address zero. This code will catch the -1 and -2 tombstones, but most linkers I have run into use zero and the tombstone.

If our algorithm only checks sections with no subsections and then makes a list of file addresses for and section ranges for those, we should have a great list. The entire PT_LOAD[0] will usually be mapped read + execute, so we can't just check top level sections for ELF. Mach-o also has this issue TEXT in mac is also mapped read + execute and usually contains zero for shared libraries, but since the sections must come after the mach-o header, the sections within the TEXT segment have correct permissions and would work, just like they would for ELF.

[clayborg]

If we do make a set of text ranges in SymbolFileDWARF, we should avoid producing function's whose address ranges are not within these bounds as well, so there are other uses for this text ranges list in SymbolFileDWARF.

[labath]

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

1044

You're right -- this would not handle shared libraries with base zero.

I am slightly uneasy about requiring executable permissions for all line tables. While it does not seem terribly useful to have line tables for non-executable code, if someone does have a line table for it for whatever reason (maybe he wants to make it executable at runtime?) it would be a shame not to display it. Also the choice of using section rather than segment permissions feels slightly arbitrary (although I could make a case for it), as it's the segment permissions which will actually define the runtime memory permissions.

Since this is really about filtering out (near) zero addresses, how about we make that explicit? Find the lowest executable (section) address and reject anything below that? Additionally, I'd also reject all addresses which are completely outside of the module range, as those not going to get used for anything, and they are generating bogus line-table dumps.

What do you think?

David: The -1 tombstones are already sort of handled in llvm (and in lldb since D83957). They are "handled" in the sense that the all sequences with and end PC lower than the start PC are rejected (and line sequences starting with (unsigned)-1 will definitely wrap). This is trying to do something about the zero tombstones.

[clayborg]

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

1044

Since this is really about filtering out (near) zero addresses, how about we make that explicit? Find the lowest executable (section) address and reject anything below that? Additionally, I'd also reject all addresses which are completely outside of the module range, as those not going to get used for anything, and they are generating bogus line-table dumps.

What do you think?

That will work for me. My main goal is to get anything that should have been dead stripped out from appearing in results for line lookups or function lookups. The quicker we can short circuit these cases the better for performance. We can also use this when we try to lookup functions and don't return any matches for functions whose start address falls below this value.

[MaskRay]

For ELF, there are non-pic cases (i.e. -no-pie) and pic cases (-pie or -shared). I think it is sufficient just testing -pie (image base is zero). If filtering for -pie works, filter for -no-pie or -shared should work as well.

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

1044

There is a concern about ContainsFileAddressRange's performance.

FindSectionContainingFileAddress iterates all sections and can be slow when the number of sections is large.

if someone does have a line table for it for whatever reason (maybe he wants to make it executable at runtime?) it would be a shame not to display it.

+1

Instead of a [lowpc,highpc) range check, I wonder whether we should just filter out lowpc. We don't seem to benefit much from a range check. A data point is that gdb filters with the CU address range and only checks lowpc (https://sourceware.org/git/?p=binutils-gdb.git;a=blobdiff;f=gdb/dwarf2/read.c;h=405b5fb3348c94aad10e3bb40f393137ddb0759c;hp=4622d14a05c6819b482c9c97c14a14755876aa72;hb=a8caed5d7faa639a1e6769eba551d15d8ddd9510;hpb=33d1369f183f1c276e3f0f52b5573fb2f5843b1c )
If the CU's lowpc is 0, it will allow a line sequence at address 0, otherwise disallow it. There is some bare metal usage with zero address.

[labath]

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

1044

There is a concern about ContainsFileAddressRange's performance.
FindSectionContainingFileAddress iterates all sections and can be slow when the number of sections is large.

Yeah, that function isn't very optimized, but OTOH, it is used in pretty much every address translation in lldb (Address class internally represents things as section+offset), and it hasn't been a problem so far. (can't say we run many benchmarks, but we do run _some_). My thinking was that if it ever becomes a problem, it could be solved at the source so that all users benefit.

If the CU's lowpc is 0, it will allow a line sequence at address 0, otherwise disallow it.

Hmm.... are you sure that code actually works? Because using DW_AT_low_pc=0 in combination with DW_AT_ranges is a common practice for describing code from multiple sections (which is pretty much all code in c++). It relies on the fact that when DW_AT_ranges is used, the only purpose of DW_AT_low_pc is to set a base address for range and location lists. An absolute base of zero allows those entries to have relocations applied to them. I'm not sure this practice is still useful/needed for dwarf 5, but clang does it nonetheless.

$ clang -gdwarf-5 -x c -o - -c -g - <<<"void f(){} void g(){}" -ffunction-sections | llvm-dwarfdump - | grep -C 1 -e DW_AT_ranges
              DW_AT_low_pc	(0x0000000000000000)
              DW_AT_ranges	(indexed (0x0) rangelist = 0x00000010
                 [0x0000000000000000, 0x0000000000000006)

[clayborg]

I really like the idea of coming up with a low PC that is the first valid .text address. This will filter out many of the zeroed out dead stripped DWARF and will make a cheap way for us to check addresses when parsing debug info and line tables. Checking for -1 and -2 of course is great to do as well.

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

1044

If the CU's lowpc is 0, it will allow a line sequence at address 0, otherwise disallow it.

I agree with Pavel here, DW_AT_low_pc is often specified as zero just for DW_AT_ranges. The whole relying on the low PC of a compile unit as a base address creates a lot of ways for the debug info to be messed up with LTO and dead stripping.

I really like the idea of coming up with a minimum PC that makes sense and filter everything else out below that.

if someone does have a line table for it for whatever reason (maybe he wants to make it executable at runtime?) it would be a shame not to display it.

I don't agree here. In reality how many times will this happen? Almost zero. And every day in anything that isn't macOS (since both DWARF in .o files and dSYM files _do_ link debug info correctly), we deal with linkers that only can concatenate and relocate and we often have many functions mapped to zero due to dead stripping. So I think we will be doing our users a disservice by not fixing this huge flaw in debug info that is generated by many linkers and is _very_ prevalent in all flavors of linux. I would be fine adding a setting for the DWARF plug-in if we really care about this issue, but I would rather wait until we see a real case of this issue before we try and proactively fix this.

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

if (!line_table)
     return false;
 
   // FIXME: Rather than parsing the whole line table and then copying it over
   // into LLDB, we should explore using a callback to populate the line table
   // while we parse to reduce memory usage.
   std::vector<std::unique_ptr<LineSequence>> sequences;
   // The Sequences view contains only valid line sequences. Don't iterate over
   // the Rows directly.
+  SectionList &list = *GetObjectFile()->GetModule()->GetSectionList();
   for (const llvm::DWARFDebugLine::Sequence &seq : line_table->Sequences) {
+    if (!list.ContainsFileAddressRange(seq.LowPC, seq.HighPC - seq.LowPC))
+      continue;
     std::unique_ptr<LineSequence> sequence =
         LineTable::CreateLineSequenceContainer();
     for (unsigned idx = seq.FirstRowIndex; idx < seq.LastRowIndex; ++idx) {
       const llvm::DWARFDebugLine::Row &row = line_table->Rows[idx];
       LineTable::AppendLineEntryToSequence(
           sequence.get(), row.Address.Address, row.Line, row.Column, row.File,
           row.IsStmt, row.BasicBlock, row.PrologueEnd, row.EpilogueBegin,
           row.EndSequence);

lldb/test/Shell/SymbolFile/DWARF/debug_line-tombstone.s

-# This test that we don't get confused by line tables containing a tombstone
-# (-1) value, as produced by recent lld's. Line sequences with the tombstone
-# value should be completely ignored. The tombstone sequence is deliberately
-# longer so that any attempt at an address binary search will likely land inside
-# the sequence.
-
-# RUN: llvm-mc --filetype=obj --triple=x86_64-pc-linux %s -o %t
-# RUN: %lldb -o "image lookup -n main -v" -o "image dump line-table main.cpp" \
-# RUN:   -o exit %t | FileCheck %s
+# Test handling of line table tombstone strategies by various linkers. When a
+# section not added to the final binary (either due to --gc-sections or comdats)
+# (elf) linkers still need to resolve debug info relocations to it. This test
+# simulates tombstoning behavior of bfd gold and lld linkers.
+# - ld.bfd will resolve all relocations to zero
+# - ld.gold (and lld before D81784) could also resolve the relocations to a
+#    small value (zero+relocation addend), although this is not likely to happen
+#    in line tables.
+# - ld.lld since D81784, resolves the relocations to -1
+# These line tables should be ignored. bfd and gold tombstones can be ambiguous
+# if the binary has sections in the low addresses, but we should definitely
+# ignore them if they fall outside of any section.
+
+# REQUIRES: x86, lld
+
+# RUN: llvm-mc --filetype=obj --triple=x86_64-pc-linux %s -o %t.lld.o --defsym TOMBSTONE=-1
+# RUN: ld.lld -o %t.lld %t.lld.o --image-base=0x10000
+# RUN: %lldb -o "image lookup -n _start -v" -o "image dump line-table main.cpp" \
+# RUN:   -o exit %t.lld | FileCheck %s
+
+# RUN: llvm-mc --filetype=obj --triple=x86_64-pc-linux %s -o %t.bfd.o --defsym TOMBSTONE=0
+# RUN: ld.lld -o %t.bfd %t.bfd.o --image-base=0x10000
+# RUN: %lldb -o "image lookup -n _start -v" -o "image dump line-table main.cpp" \
+# RUN:   -o exit %t.bfd | FileCheck %s
+
+# RUN: llvm-mc --filetype=obj --triple=x86_64-pc-linux %s -o %t.gold.o --defsym TOMBSTONE=47
+# RUN: ld.lld -o %t.gold %t.gold.o --image-base=0x10000
+# RUN: %lldb -o "image lookup -n _start -v" -o "image dump line-table main.cpp" \
+# RUN:   -o exit %t.gold | FileCheck %s
 
-# CHECK-LABEL: image lookup -n main -v
-# CHECK: LineEntry: [0x0000000000001000-0x0000000000001001): main.cpp:1
+# CHECK-LABEL: image lookup -n _start -v
+# CHECK: LineEntry: [0x0000000000020000-0x0000000000020001): main.cpp:1
 # CHECK-LABEL: image dump line-table main.cpp
 # CHECK-NEXT: Line table for main.cpp
-# CHECK-NEXT: 0x0000000000001000: main.cpp:1
-# CHECK-NEXT: 0x0000000000001001: main.cpp:1
+# CHECK-NEXT: 0x0000000000020000: main.cpp:1
+# CHECK-NEXT: 0x0000000000020001: main.cpp:1
 # CHECK-EMPTY:
 # CHECK-NEXT: exit
 
+        .globl _start
         .text
-.space 0x1000
-main:
+        .p2align 16
+_start:
   nop
-.Lmain_end:
+.L_start_end:
 
         .section        .debug_abbrev,"",@progbits
         .byte   1                               # Abbreviation Code
         .byte   17                              # DW_TAG_compile_unit
         .byte   0                               # DW_CHILDREN_no
         .byte   37                              # DW_AT_producer
         .byte   8                               # DW_FORM_string
         .byte   3                               # DW_AT_name

 .Ldebug_info_start0:
         .short  4                               # DWARF version number
         .long   0                               # Offset Into Abbrev. Section
         .byte   8                               # Address Size (in bytes)
         .byte   1                               # Abbrev [1] 0xb:0xc4 DW_TAG_compile_unit
         .asciz  "Hand-written DWARF"            # DW_AT_producer
         .asciz  "main.cpp"                      # DW_AT_name
         .long   0                               # DW_AT_stmt_list
-        .quad   main-.text                      # DW_AT_low_pc
-        .long   .Lmain_end-main                 # DW_AT_high_pc
+        .quad   _start                          # DW_AT_low_pc
+        .long   .L_start_end-_start             # DW_AT_high_pc
 .Ldebug_info_end0:
 
 .section .debug_line,"",@progbits
         .long   .Llt1_end - .Llt1_start # Length of Unit (DWARF-32 format)
 .Llt1_start:
         .short  4               # DWARF version number
         .long   .Lprologue1_end-.Lprologue1_start # Length of Prologue
 .Lprologue1_start:
         .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
         .byte   0
         .asciz "main.cpp"          # File table
         .byte   0, 0, 0
         .byte   0
 .Lprologue1_end:
         .byte   0, 9, 2         # DW_LNE_set_address
-        .quad   -1
+        .quad   TOMBSTONE
         .byte   1               # DW_LNS_copy
         .byte   33              # address += 1,  line += 1
         .byte   33              # address += 1,  line += 1
         .byte   33              # address += 1,  line += 1
         .byte   33              # address += 1,  line += 1
         .byte   33              # address += 1,  line += 1
         .byte   33              # address += 1,  line += 1
         .byte   33              # address += 1,  line += 1
         .byte   33              # address += 1,  line += 1
         .byte   33              # address += 1,  line += 1
         .byte   33              # address += 1,  line += 1
         .byte   33              # address += 1,  line += 1
         .byte   33              # address += 1,  line += 1
         .byte   33              # address += 1,  line += 1
         .byte   33              # address += 1,  line += 1
         .byte   33              # address += 1,  line += 1
         .byte   2               # DW_LNS_advance_pc
         .uleb128 1
         .byte   0, 1, 1         # DW_LNE_end_sequence
 
         .byte   0, 9, 2         # DW_LNE_set_address
-        .quad   main-.text
+        .quad   _start
         .byte   18              # address += 0,  line += 0
         .byte   2               # DW_LNS_advance_pc
         .uleb128 1
         .byte   0, 1, 1         # DW_LNE_end_sequence
 .Llt1_end: