Verify that all references point to actual DIEs in "llvm-dwarfdump --verify"

[clayborg]

Summary

LTO and other fancy linking previously led to DWARF that contained invalid references. We already validate that CU relative references fall into the CU, and the DW_FORM_ref_addr references fall inside the .debug_info section, but we didn't validate that the references pointed to correct DIE offsets. This new verification will ensure that all references refer to actual DIEs and not an offset in between.

This caught a bug in DWARFUnit::getDIEForOffset() where if you gave it any offset, it would match the DIE that mathes the offset _or_ the next DIE. This has been fixed.

[clayborg]

I also moved the verification code over into a Verifier class to prepare for future extra verification steps where we will need to persist data between two steps.

[clayborg]

Ping

[aprantl]

lib/DebugInfo/DWARF/DWARFContext.cpp

309

Do we need a sorted container here or would an llvm::DenseMap be sufficient (and faster)?

[clayborg]

lib/DebugInfo/DWARF/DWARFContext.cpp

309

We can change this if needed. std::unordered_set would work as well.

include/llvm/DebugInfo/DWARF/DWARFContext.h

public:
   }
 
   /// Get the compile unit at the specified index for the DWO compile units.
   DWARFCompileUnit *getDWOCompileUnitAtIndex(unsigned index) {
     parseDWOCompileUnits();
     return DWOCUs[index].get();
   }
 
+  /// Get a DIE given an exact offset.
+  DWARFDie getDIEForOffset(uint32_t Offset);
+
   const DWARFUnitIndex &getCUIndex();
   DWARFGdbIndex &getGdbIndex();
   const DWARFUnitIndex &getTUIndex();
 
   /// Get a pointer to the parsed DebugAbbrev object.
   const DWARFDebugAbbrev *getDebugAbbrev();
 
   /// Get a pointer to the parsed DebugLoc object.

include/llvm/DebugInfo/DWARF/DWARFUnit.h

public:
   DWARFDie getDIEForOffset(uint32_t Offset) {
     extractDIEsIfNeeded(false);
     assert(!DieArray.empty());
     auto it = std::lower_bound(
         DieArray.begin(), DieArray.end(), Offset,
         [](const DWARFDebugInfoEntry &LHS, uint32_t Offset) {
           return LHS.getOffset() < Offset;
         });
-    if (it == DieArray.end())
-      return DWARFDie();
+    if (it != DieArray.end() && it->getOffset() == Offset)
       return DWARFDie(this, &*it);
+    return DWARFDie();
   }
 
   uint32_t getLineTableOffset() const {
     if (IndexEntry)
       if (const auto *Contrib = IndexEntry->getOffset(DW_SECT_LINE))
         return Contrib->Offset;
     return 0;
   }

lib/DebugInfo/DWARF/DWARFContext.cpp

 #include "llvm/Support/DataExtractor.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cstdint>
+#include <map>
+#include <set>
 #include <string>
 #include <utility>
 #include <vector>
 
 using namespace llvm;
 using namespace dwarf;
 using namespace object;
 
if (DumpType == DIDT_All || DumpType == DIDT_AppleNamespaces)
     dumpAccelSection(OS, "apple_namespaces", getAppleNamespacesSection(),
                      getStringSection(), isLittleEndian());
 
   if (DumpType == DIDT_All || DumpType == DIDT_AppleObjC)
     dumpAccelSection(OS, "apple_objc", getAppleObjCSection(),
                      getStringSection(), isLittleEndian());
 }
 
-bool DWARFContext::verify(raw_ostream &OS, DIDumpType DumpType) {
+DWARFDie DWARFContext::getDIEForOffset(uint32_t Offset) {
+  parseCompileUnits();
+  if (auto *CU = CUs.getUnitForOffset(Offset))
+    return CU->getDIEForOffset(Offset);
+  return DWARFDie();
+}
+
+namespace {
+  
+class Verifier {
+  raw_ostream &OS;
+  DWARFContext &DCtx;
+public:
+  Verifier(raw_ostream &S, DWARFContext &D) : OS(S), DCtx(D) {}
+  
+  bool HandleDebugInfo() {
     bool Success = true;
-  if (DumpType == DIDT_All || DumpType == DIDT_Info) {
+    // A map that tracks all references (converted absolute references) so we
+    // can verify each reference points to a valid DIE and not an offset that
+    // lies between to valid DIEs.
+    std::map<uint64_t, std::set<uint32_t>> ReferenceToDIEOffsets;
+
     OS << "Verifying .debug_info...\n";
-    for (const auto &CU : compile_units()) {
+    for (const auto &CU : DCtx.compile_units()) {
       unsigned NumDies = CU->getNumDIEs();
       for (unsigned I = 0; I < NumDies; ++I) {
         auto Die = CU->getDIEAtIndex(I);
         const auto Tag = Die.getTag();
         if (Tag == DW_TAG_null)
           continue;
         for (auto AttrValue : Die.attributes()) {
           const auto Attr = AttrValue.Attr;
           const auto Form = AttrValue.Value.getForm();
           switch (Attr) {
             case DW_AT_ranges:
               // Make sure the offset in the DW_AT_ranges attribute is valid.
               if (auto SectionOffset = AttrValue.Value.getAsSectionOffset()) {
-              if (*SectionOffset >= getRangeSection().Data.size()) {
+                if (*SectionOffset >= DCtx.getRangeSection().Data.size()) {
                   Success = false;
                   OS << "error: DW_AT_ranges offset is beyond .debug_ranges "
-                      "bounds:\n";
                   Die.dump(OS, 0);
                   OS << "\n";
                 }
               } else {
                 Success = false;
                 OS << "error: DIE has invalid DW_AT_ranges encoding:\n";
                 Die.dump(OS, 0);
                 OS << "\n";
               }
               break;
             case DW_AT_stmt_list:
               // Make sure the offset in the DW_AT_stmt_list attribute is valid.
               if (auto SectionOffset = AttrValue.Value.getAsSectionOffset()) {
-              if (*SectionOffset >= getLineSection().Data.size()) {
+                if (*SectionOffset >= DCtx.getLineSection().Data.size()) {
                   Success = false;
                   OS << "error: DW_AT_stmt_list offset is beyond .debug_line "
-                      "bounds: "
-                   << format("0x%08" PRIx32, *SectionOffset) << "\n";
                   CU->getUnitDIE().dump(OS, 0);
                   OS << "\n";
                 }
               } else {
                 Success = false;
                 OS << "error: DIE has invalid DW_AT_stmt_list encoding:\n";
                 Die.dump(OS, 0);
                 OS << "\n";
               }
               break;
               
             default:
               break;
           }
           switch (Form) {
             case DW_FORM_ref1:
             case DW_FORM_ref2:
             case DW_FORM_ref4:
             case DW_FORM_ref8:
             case DW_FORM_ref_udata: {
               // Verify all CU relative references are valid CU offsets.
               Optional<uint64_t> RefVal = AttrValue.Value.getAsReference();
               assert(RefVal);
               if (RefVal) {
                 auto DieCU = Die.getDwarfUnit();
                 auto CUSize = DieCU->getNextUnitOffset() - DieCU->getOffset();
                 auto CUOffset = AttrValue.Value.getRawUValue();
                 if (CUOffset >= CUSize) {
                   Success = false;
                   OS << "error: " << FormEncodingString(Form) << " CU offset "
-                   << format("0x%08" PRIx32, CUOffset)
-                   << " is invalid (must be less than CU size of "
-                   << format("0x%08" PRIx32, CUSize) << "):\n";
                   Die.dump(OS, 0);
                   OS << "\n";
+                } else {
+                  // Valid reference, but we will verify it points to an actual
+                  // DIE later.
+                  ReferenceToDIEOffsets[*RefVal].insert(Die.getOffset());
                 }
               }
               break;
             }
             case DW_FORM_ref_addr: {
               // Verify all absolute DIE references have valid offsets in the
               // .debug_info section.
               Optional<uint64_t> RefVal = AttrValue.Value.getAsReference();
               assert(RefVal);
-            if (RefVal && *RefVal >= getInfoSection().Data.size()) {
+              if (RefVal) {
+                if(*RefVal >= DCtx.getInfoSection().Data.size()) {
                   Success = false;
                   OS << "error: DW_FORM_ref_addr offset beyond .debug_info "
                         "bounds:\n";
                   Die.dump(OS, 0);
                   OS << "\n";
+                } else {
+                  // Valid reference, but we will verify it points to an actual
+                  // DIE later.
+                  ReferenceToDIEOffsets[*RefVal].insert(Die.getOffset());
+                }
               }
               break;
             }
             case DW_FORM_strp: {
               auto SecOffset = AttrValue.Value.getAsSectionOffset();
               assert(SecOffset); // DW_FORM_strp is a section offset.
-            if (SecOffset && *SecOffset >= getStringSection().size()) {
+              if (SecOffset && *SecOffset >= DCtx.getStringSection().size()) {
                 Success = false;
                 OS << "error: DW_FORM_strp offset beyond .debug_str bounds:\n";
                 Die.dump(OS, 0);
                 OS << "\n";
               }
               break;
             }
             default:
               break;
           }
         }
       }
     }
+
+    // Take all references and make sure they point to an actual DIE by
+    // getting the DIE by offset and emitting an error
+    OS << "Verifying .debug_info references...\n";
+    for (auto Pair: ReferenceToDIEOffsets) {
+      auto Die = DCtx.getDIEForOffset(Pair.first);
+      if (Die)
+        continue;
+      Success = false;
+      OS << "error: invalid DIE reference " << format("0x%08" PRIx64, Pair.first)
+         << ". Offset is in between DIEs:\n";
+      for (auto Offset: Pair.second) {
+        auto ReferencingDie = DCtx.getDIEForOffset(Offset);
+        ReferencingDie.dump(OS, 0);
+        OS << "\n";
+      }
+      OS << "\n";
+    }
+    return Success;
+  }
+};
+  
+} // anonymous namespace
+
+bool DWARFContext::verify(raw_ostream &OS, DIDumpType DumpType) {
+  bool Success = true;
+  Verifier verifier(OS, *this);
+  if (DumpType == DIDT_All || DumpType == DIDT_Info) {
+    if (!verifier.HandleDebugInfo())
+      Success = false;
   }
   return Success;
 }
 const DWARFUnitIndex &DWARFContext::getCUIndex() {
   if (CUIndex)
     return *CUIndex;
 
   DataExtractor CUIndexData(getCUIndexSection(), isLittleEndian(), 0);

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, TestDwarfVerifyInvalidRefAddrBetween) {
+  // Create a single compile unit with a single function that has a DW_AT_type
+  // with a valid .debug_info offset, but the offset is between two DIEs.
+  const char *yamldata = R"(
+    debug_str:
+      - ''
+      - /tmp/main.c
+      - main
+    debug_abbrev:
+      - Code:            0x00000001
+        Tag:             DW_TAG_compile_unit
+        Children:        DW_CHILDREN_yes
+        Attributes:
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+      - Code:            0x00000002
+        Tag:             DW_TAG_subprogram
+        Children:        DW_CHILDREN_no
+        Attributes:
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+          - Attribute:       DW_AT_type
+            Form:            DW_FORM_ref_addr
+    debug_info:
+      - Length:
+          TotalLength:     22
+        Version:         4
+        AbbrOffset:      0
+        AddrSize:        8
+        Entries:
+          - AbbrCode:        0x00000001
+            Values:
+              - Value:           0x0000000000000001
+          - AbbrCode:        0x00000002
+            Values:
+              - Value:           0x000000000000000D
+              - Value:           0x0000000000000011
+          - AbbrCode:        0x00000000
+            Values:
+  )";
+  auto ErrOrSections = DWARFYAML::EmitDebugSections(StringRef(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: invalid DIE reference 0x00000011. Offset is in "
+      "between DIEs:";
+  EXPECT_TRUE(strm.str().find(err) != std::string::npos);
+}
+  
 } // end anonymous namespace