Add line table verification to lldb-dwarfdump --verify.

[clayborg]

Summary

This patch verifies the .debug_line:

• verify all addresses in a line table sequence have ascending addresses
• verify that all line table file indexes are valid

Unit tests added for both cases.

[dblaikie]

lib/DebugInfo/DWARF/DWARFContext.cpp

404

FIXME to handle this as a verification failure too? (if stmt_list isn't usable as a section offset)

406

another verification failure possibility?

414–415

probably invert this to reduce indentation:

auto StmtFormValue = CU->getUnitDIE().find(DW_AT_stmt_list);
if (!StmtFormValue)
  continue;
...

449–450

maybe use set notation to be clear about open/closed range, etc: "[1,MaxFileIndex]"

453

Probably use '\n' rather than "\n" - so there's no need to go hunting for a null terminator, etc.

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

1914

Declare as StringRef?

1984

Probably make this a StringRef

1992

StringRef?

2064–2065

Perhaps it's worthwhile to mention what the file index was? (doesn't look like it's in this error message)

[clayborg]

Updates:

• reflow code around StmtFormValue
• comment that we don't need to create an error where things are already checked in the .debug_info to make things clear
• Use StringRef where needed
• clang-format
• include bad file index in error message and update unit test
• use '\n' instead of "\n"

[clayborg]

Marked things as done and commented where things weren't changed.

lib/DebugInfo/DWARF/DWARFContext.cpp

404

This is handled when verifying the .debug_info section. No need to duplicate this here.

406

This is handled when verifying the .debug_info section. No need to duplicate this here.

415

Yeah, I thought of that but have been asked to do the "if (auto StmtFormValue" way many times. The way you did it above is the way I wanted to do it. I will change it.

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

1984

We search the std::string named "str" for this below and use must be a C string as part of the EXPECT_TRUE. No need for the StringRef here? Unless I wrap "str" into a StringRef. Let me know your preference here.

[dblaikie]

lib/DebugInfo/DWARF/DWARFContext.cpp

404

Should it be an assertion here, then? (is this verification still run, even if the debug_info section verification fails?)

415

Yeah, it depends - both are certainly used a lot.

Exactly how much code is unindented by inverting the condition makes it worthwhile is a bit subjective. All good.

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

1914

Prefer copy-init over direct init where possible. ie:

T v = u;

rather than

T v(u);

(so 'StringRef yamldata = R"(... ' here)

1984

Could use SmallString instead of std::string (with raw_svector_ostream (SmallString is a StringVector)) & then SmallString's got a find(StringRef).

2056

can this be 'const auto &'? (or skip the variable and pass '*ErrOrSections' to the DWARFContextInMemory ctor directly)

[probinson]

Can you verify that each CU (that has DW_AT_stmt_list) points to a different place in .debug_line?

[probinson]

lib/DebugInfo/DWARF/DWARFContext.cpp

460

Can you verify that the address is in-range for the CU?
(which might be sufficient for my comment about each CU having a unique contribution to the line table.)

[clayborg]

In D32754#743899, @probinson wrote:

Can you verify that each CU (that has DW_AT_stmt_list) points to a different place in .debug_line?

That is a good idea. Maybe we emit a warning? I say that because it seems like a good way to save space for type unique style DWARF to share line tables since they only use the line tables for DW_AT_decl_file and DW_AT_call_file. Is it against the DWARF spec to share a line table? Let me know if you think this should be a warning or error.

lib/DebugInfo/DWARF/DWARFContext.cpp

404

No assertion. It will be handled by the .debug_info and reported there. We just want to get around it here.

[clayborg]

Lines have changed too much and a previous patch for llvm-dwarfdump --verify changed where verification happens. I will fix all requested items and make a new diff

include/llvm/DebugInfo/DWARF/DWARFDebugLine.h

public:
   /// Standard .debug_line state machine structure.
   struct Row {
     explicit Row(bool DefaultIsStmt = false);
 
     /// Called after a row is appended to the matrix.
     void postAppend();
     void reset(bool DefaultIsStmt);
     void dump(raw_ostream &OS) const;
-
+    static void dumpTableHeader(raw_ostream &OS);
     static bool orderByAddress(const Row &LHS, const Row &RHS) {
       return LHS.Address < RHS.Address;
     }
 
     /// The program-counter value corresponding to a machine instruction
     /// generated by the compiler.
     uint64_t Address;
     /// An unsigned integer indicating a source line number. Lines are numbered

lib/DebugInfo/DWARF/DWARFContext.cpp

for (const auto &CU : compile_units()) {
           }
           default:
             break;
           }
         }
       }
     }
   }
+
+  if (DumpType == DIDT_All || DumpType == DIDT_Line) {
+    OS << "Verifying .debug_line...\n";
+    for (const auto &CU : compile_units()) {
+      uint32_t LineTableOffset = 0;
+      auto StmtFormValue = CU->getUnitDIE().find(DW_AT_stmt_list);
+      if (!StmtFormValue) {
+        // No line table for this compile unit.
+        continue;
+      }
+      // Get the attribute value as a section offset. No need to produce an
+      // error here if the encoding isn't correct because we validate this in
+      // the .debug_info verifier.
+      if (auto StmtSectionOffset = toSectionOffset(StmtFormValue)) {
+        LineTableOffset = *StmtSectionOffset;
+        if (LineTableOffset >= getLineSection().Data.size()) {
+          // Make sure we don't get a valid line table back if the offset
+          // is wrong.
+          assert(getLineTableForUnit(CU.get()) == nullptr);
+          // Skip this line table as it isn't valid. No need to create an error
+          // here because we validate this in the .debug_info verifier.
+          continue;
+        }
+      }
+      auto LineTable = getLineTableForUnit(CU.get());
+      if (!LineTable) {
+        Success = false;
+        OS << "error: .debug_line[" << format("0x%08" PRIx32, LineTableOffset)
+           << "] was not able to be parsed for CU:\n";
+        CU->getUnitDIE().dump(OS, 0);
+        OS << '\n';
+        continue;
+      }
+      uint32_t MaxFileIndex = LineTable->Prologue.FileNames.size();
+      uint64_t PrevAddress = 0;
+      uint32_t RowIndex = 0;
+      for (const auto &Row : LineTable->Rows) {
+        if (Row.Address < PrevAddress) {
+          Success = false;
+          OS << "error: .debug_line[" << format("0x%08" PRIx32, LineTableOffset)
+             << "] row[" << RowIndex
+             << "] decreases in address from previous row:\n";
+
+          DWARFDebugLine::Row::dumpTableHeader(OS);
+          if (RowIndex > 0)
+            LineTable->Rows[RowIndex - 1].dump(OS);
+          Row.dump(OS);
+          OS << '\n';
+        }
+
+        if (Row.File > MaxFileIndex) {
+          Success = false;
+          OS << "error: .debug_line[" << format("0x%08" PRIx32, LineTableOffset)
+             << "][" << RowIndex << "] has invalid file index " << Row.File
+             << " (valid values are [1," << MaxFileIndex << "]):\n";
+          DWARFDebugLine::Row::dumpTableHeader(OS);
+          Row.dump(OS);
+          OS << '\n';
+        }
+        if (Row.EndSequence)
+          PrevAddress = 0;
+        else
+          PrevAddress = Row.Address;
+        ++RowIndex;
+      }
+    }
+  }
+
   return Success;
 }
 const DWARFUnitIndex &DWARFContext::getCUIndex() {
   if (CUIndex)
     return *CUIndex;
 
   DataExtractor CUIndexData(getCUIndexSection(), isLittleEndian(), 0);
 

lib/DebugInfo/DWARF/DWARFDebugLine.cpp

void DWARFDebugLine::Row::reset(bool DefaultIsStmt) {
   Discriminator = 0;
   IsStmt = DefaultIsStmt;
   BasicBlock = false;
   EndSequence = false;
   PrologueEnd = false;
   EpilogueBegin = false;
 }
 
+void DWARFDebugLine::Row::dumpTableHeader(raw_ostream &OS) {
+  OS << "Address            Line   Column File   ISA Discriminator Flags\n"
+     << "------------------ ------ ------ ------ --- ------------- "
+        "-------------\n";
+}
+
 void DWARFDebugLine::Row::dump(raw_ostream &OS) const {
   OS << format("0x%16.16" PRIx64 " %6u %6u", Address, Line, Column)
      << format(" %6u %3u %13u ", File, Isa, Discriminator)
      << (IsStmt ? " is_stmt" : "") << (BasicBlock ? " basic_block" : "")
      << (PrologueEnd ? " prologue_end" : "")
      << (EpilogueBegin ? " epilogue_begin" : "")
      << (EndSequence ? " end_sequence" : "") << '\n';
 }

 
 DWARFDebugLine::LineTable::LineTable() { clear(); }
 
 void DWARFDebugLine::LineTable::dump(raw_ostream &OS) const {
   Prologue.dump(OS);
   OS << '\n';
 
   if (!Rows.empty()) {
-    OS << "Address            Line   Column File   ISA Discriminator Flags\n"
-       << "------------------ ------ ------ ------ --- ------------- "
-          "-------------\n";
+    Row::dumpTableHeader(OS);
     for (const Row &R : Rows) {
       R.dump(OS);
     }
   }
 }
 
 void DWARFDebugLine::LineTable::clear() {
   Prologue.clear();

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

TEST(DWARFDebugInfo, TestDwarfVerifyInvalidStrp) {
   std::string str;
   raw_string_ostream strm(str);
   EXPECT_FALSE(DwarfContext.verify(strm, DIDT_All));
   strm.flush();
   const char *err = "error: DW_FORM_strp offset beyond .debug_str bounds:";
   EXPECT_TRUE(strm.str().find(err) != std::string::npos);
 }
 
+TEST(DWARFDebugInfo, TestDwarfVerifyInvalidLineSequence) {
+  // Create a single compile unit whose line table has a sequence in it where
+  // the address decreases.
+  StringRef yamldata(R"(
+    debug_str:
+      - ''
+      - /tmp/main.c
+    debug_abbrev:
+      - Code:            0x00000001
+        Tag:             DW_TAG_compile_unit
+        Children:        DW_CHILDREN_no
+        Attributes:
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+          - Attribute:       DW_AT_stmt_list
+            Form:            DW_FORM_sec_offset
+    debug_info:
+      - Length:
+          TotalLength:     16
+        Version:         4
+        AbbrOffset:      0
+        AddrSize:        8
+        Entries:
+          - AbbrCode:        0x00000001
+            Values:
+              - Value:           0x0000000000000001
+              - Value:           0x0000000000000000
+    debug_line:
+      - Length:
+          TotalLength:     68
+        Version:         2
+        PrologueLength:  34
+        MinInstLength:   1
+        DefaultIsStmt:   1
+        LineBase:        251
+        LineRange:       14
+        OpcodeBase:      13
+        StandardOpcodeLengths: [ 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1 ]
+        IncludeDirs:
+          - /tmp
+        Files:
+          - Name:            main.c
+            DirIdx:          1
+            ModTime:         0
+            Length:          0
+        Opcodes:
+          - Opcode:          DW_LNS_extended_op
+            ExtLen:          9
+            SubOpcode:       DW_LNE_set_address
+            Data:            4112
+          - Opcode:          DW_LNS_advance_line
+            SData:           9
+            Data:            4112
+          - Opcode:          DW_LNS_copy
+            Data:            4112
+          - Opcode:          DW_LNS_advance_pc
+            Data:            18446744073709551600
+          - Opcode:          DW_LNS_extended_op
+            ExtLen:          1
+            SubOpcode:       DW_LNE_end_sequence
+            Data:            18446744073709551600
+  )");
+  auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata);
+  ASSERT_TRUE((bool)ErrOrSections);
+
+  auto &DebugSections = *ErrOrSections;
+
+  DWARFContextInMemory DwarfContext(DebugSections, 8);
+
+  std::string str;
+  raw_string_ostream strm(str);
+  EXPECT_FALSE(DwarfContext.verify(strm, DIDT_All));
+  strm.flush();
+  const char *err = "error: .debug_line[0x00000000] row[1] decreases in "
+                    "address from previous row:";
+  EXPECT_TRUE(strm.str().find(err) != std::string::npos);
+}
+
+TEST(DWARFDebugInfo, TestDwarfVerifyInvalidLineFileIndex) {
+  // Create a single compile unit whose line table has a line table row with
+  // an invalid file index.
+  StringRef yamldata(R"(
+    debug_str:
+      - ''
+      - /tmp/main.c
+    debug_abbrev:
+      - Code:            0x00000001
+        Tag:             DW_TAG_compile_unit
+        Children:        DW_CHILDREN_no
+        Attributes:
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+          - Attribute:       DW_AT_stmt_list
+            Form:            DW_FORM_sec_offset
+    debug_info:
+      - Length:
+          TotalLength:     16
+        Version:         4
+        AbbrOffset:      0
+        AddrSize:        8
+        Entries:
+          - AbbrCode:        0x00000001
+            Values:
+              - Value:           0x0000000000000001
+              - Value:           0x0000000000000000
+    debug_line:
+      - Length:
+          TotalLength:     61
+        Version:         2
+        PrologueLength:  34
+        MinInstLength:   1
+        DefaultIsStmt:   1
+        LineBase:        251
+        LineRange:       14
+        OpcodeBase:      13
+        StandardOpcodeLengths: [ 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1 ]
+        IncludeDirs:
+          - /tmp
+        Files:
+          - Name:            main.c
+            DirIdx:          1
+            ModTime:         0
+            Length:          0
+        Opcodes:
+          - Opcode:          DW_LNS_extended_op
+            ExtLen:          9
+            SubOpcode:       DW_LNE_set_address
+            Data:            4096
+          - Opcode:          DW_LNS_advance_line
+            SData:           9
+            Data:            4096
+          - Opcode:          DW_LNS_copy
+            Data:            4096
+          - Opcode:          DW_LNS_advance_pc
+            Data:            16
+          - Opcode:          DW_LNS_set_file
+            Data:            5
+          - Opcode:          DW_LNS_extended_op
+            ExtLen:          1
+            SubOpcode:       DW_LNE_end_sequence
+            Data:            5
+  )");
+  auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata);
+  ASSERT_TRUE((bool)ErrOrSections);
+
+  auto &DebugSections = *ErrOrSections;
+
+  DWARFContextInMemory DwarfContext(DebugSections, 8);
+
+  std::string str;
+  raw_string_ostream strm(str);
+  EXPECT_FALSE(DwarfContext.verify(strm, DIDT_All));
+  strm.flush();
+  const char *err = "error: .debug_line[0x00000000][1] has invalid file index "
+                    "5 (valid values are [1,1]):";
+  EXPECT_TRUE(strm.str().find(err) != std::string::npos);
+}
+
 } // end anonymous namespace