Index: include/llvm/DebugInfo/DWARF/DWARFVerifier.h =================================================================== --- include/llvm/DebugInfo/DWARF/DWARFVerifier.h +++ include/llvm/DebugInfo/DWARF/DWARFVerifier.h @@ -10,9 +10,13 @@ #ifndef LLVM_DEBUGINFO_DWARF_DWARFVERIFIER_H #define LLVM_DEBUGINFO_DWARF_DWARFVERIFIER_H +#include "llvm/DebugInfo/DWARF/DWARFDebugRangeList.h" +#include "llvm/DebugInfo/DWARF/DWARFDie.h" + #include #include #include +#include namespace llvm { class raw_ostream; @@ -23,15 +27,64 @@ /// A class that verifies DWARF debug information given a DWARF Context. class DWARFVerifier { + struct DieRangeInfo { + DWARFDie Die; + DWARFAddressRangesVector Ranges; + + DieRangeInfo() : Die(), Ranges() {} + DieRangeInfo(DWARFDie D, const DWARFAddressRangesVector &R); + /// Return true if this object contains all ranges within RHS. + bool Contains(const DieRangeInfo &RHS); + bool DoesIntersect(const DieRangeInfo &RHS) const; + void Dump(raw_ostream &OS) const; + bool operator<(const DieRangeInfo &RHS) const; + /// Return true if there are errors in the ranges R. + bool SortAndCheckRangesHasErrors(raw_ostream &OS); + }; + + struct VerifyDieInfo { + DieRangeInfo RI; + std::set ChildRangesCantOverlap; + }; + raw_ostream &OS; DWARFContext &DCtx; /// 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> ReferenceToDIEOffsets; + + /// Keep a set of all DW_TAG_subprogram range infos across all compile + /// units so we can look for overlapping function ranges after we go through + /// all of the DIEs. + std::set AllFunctionDieRangeInfos; + uint32_t NumDebugInfoErrors; uint32_t NumDebugLineErrors; + /// Verifies the a DIE's tag and gathers information about all DIEs. + /// + /// This function currently checks for: + /// - Checks DW_TAG_compile_unit address range(s) + /// - Checks DW_TAG_subprogram address range(s) and if the compile unit + /// has ranges, verifies that its address range is fully contained in + /// the compile unit ranges. Also adds the functions address range info + /// to AllFunctionDieRangeInfos to look for functions with overlapping + /// ranges after all DIEs have been processed. + /// - Checks that DW_TAG_lexical_block and DW_TAG_inlined_subroutine DIEs + /// have address range(s) that are fully contained in their parent DIEs + /// address range(s). + /// + /// @param Die The DWARF DIE to check + void verifyDie(const DWARFDie &Die, DieRangeInfo &UnitRI, VerifyDieInfo &ParentVRI); + + /// Verify that no DIE ranges overlap. + void verifyNoRangesOverlap(const std::set &DieRangeInfos); + + /// Verifies that we have no overlapping function address ranges within all + /// of the DWARF. + void verifyDebugInfoOverlappingFunctionRanges(); + /// Verifies the attribute's DWARF attribute and its value. /// /// This function currently checks for: @@ -40,7 +93,7 @@ /// /// @param Die The DWARF DIE that owns the attribute value /// @param AttrValue The DWARF attribute value to check - void verifyDebugInfoAttribute(DWARFDie &Die, DWARFAttribute &AttrValue); + void verifyDebugInfoAttribute(const DWARFDie &Die, DWARFAttribute &AttrValue); /// Verifies the attribute's DWARF form. /// @@ -51,7 +104,7 @@ /// /// @param Die The DWARF DIE that owns the attribute value /// @param AttrValue The DWARF attribute value to check - void verifyDebugInfoForm(DWARFDie &Die, DWARFAttribute &AttrValue); + void verifyDebugInfoForm(const DWARFDie &Die, DWARFAttribute &AttrValue); /// Verifies the all valid references that were found when iterating through /// all of the DIE attributes. @@ -60,7 +113,7 @@ /// offset matches. This helps to ensure if a DWARF link phase moved things /// around, that it doesn't create invalid references by failing to relocate /// CU relative and absolute references. - void veifyDebugInfoReferences(); + void verifyDebugInfoReferences(); /// Verify the the DW_AT_stmt_list encoding and value and ensure that no /// compile units that have the same DW_AT_stmt_list value. Index: lib/DebugInfo/DWARF/DWARFVerifier.cpp =================================================================== --- lib/DebugInfo/DWARF/DWARFVerifier.cpp +++ lib/DebugInfo/DWARF/DWARFVerifier.cpp @@ -23,7 +23,182 @@ using namespace dwarf; using namespace object; -void DWARFVerifier::verifyDebugInfoAttribute(DWARFDie &Die, +namespace { +/// Returns true if the two ranges [a.first, a.second) and [b.first, b.second) +/// intersect. +bool RangesIntersect(const std::pair &a, + const std::pair &b) { + if (a.first == a.second || b.first == b.second) + return false; // Empty ranges can't intersect. + return (a.first < b.second) && (a.second > b.first); +} + +} // anonymous namespace + +bool DWARFVerifier::DieRangeInfo::SortAndCheckRangesHasErrors(raw_ostream &OS) { + bool HasErrors = false; + size_t I = 0; + while (I < Ranges.size()) { + if (Ranges[I].first >= Ranges[I].second) { + if (Ranges[I].first > Ranges[I].second) { + OS << "error: invalid range in DIE\n"; + HasErrors = true; + } + // Remove empty or invalid ranges. + Ranges.erase(Ranges.begin() + I); + continue; + } else { + ++I; // Only increment if we didn't remove the range. + } + } + std::sort(Ranges.begin(), Ranges.end()); + return HasErrors; +} + +void DWARFVerifier::DieRangeInfo::Dump(raw_ostream &OS) const { + OS << format("0x%08" PRIx32, Die.getOffset()) << ":"; + for (const auto &R : Ranges) + OS << " [" << format("0x%" PRIx32, R.first) << "-" + << format("0x%" PRIx32, R.second) << ")"; + OS << "\n"; +} + +void DWARFVerifier::verifyNoRangesOverlap(const std::set &DieRangeInfos) { + auto End = DieRangeInfos.end(); + auto Prev = End; + for (auto Curr = DieRangeInfos.begin(); Curr != End; ++Curr) { + if (Prev != End) { + if (Prev->DoesIntersect(*Curr)) { + ++NumDebugInfoErrors; + OS << "error: DIEs have overlapping address ranges:\n"; + Prev->Die.dump(OS, 0); + Curr->Die.dump(OS, 0); + OS << "\n"; + } + } + Prev = Curr; + } +} + +bool DWARFVerifier::DieRangeInfo::Contains(const DieRangeInfo &RHS) { + for (const auto &S : RHS.Ranges) + for (const auto &R : Ranges) + if (R.first <= S.first && S.first < R.second) + return R.first < S.second && S.second <= R.second; + return false; +} + +bool DWARFVerifier::DieRangeInfo::DoesIntersect( + const DieRangeInfo &RHS) const { + for (const auto &R : RHS.Ranges) + for (const auto &L : Ranges) + if (RangesIntersect(R, L)) + return true; + return false; +} + +bool DWARFVerifier::DieRangeInfo::operator<(const DieRangeInfo &RHS) const { + if (Ranges.empty()) { + if (RHS.Ranges.empty()) + return Die.getOffset() < RHS.Die.getOffset(); + else + return true; + } + if (RHS.Ranges.empty()) + return false; + size_t LeftSize = Ranges.size(); + size_t RightSize = RHS.Ranges.size(); + for (size_t I = 0; I < LeftSize; ++I) { + if (I >= RightSize) + return false; + if (Ranges[I].first != RHS.Ranges[I].first) + return Ranges[I].first < RHS.Ranges[I].first; + if (Ranges[I].second != RHS.Ranges[I].second) + return Ranges[I].second < RHS.Ranges[I].second; + } + return false; +} + +void DWARFVerifier::verifyDie(const DWARFDie &Die, DieRangeInfo &UnitRI, VerifyDieInfo &ParentVRI) { + const auto Tag = Die.getTag(); + + VerifyDieInfo VRI; + VRI.RI.Die = Die; + switch (Tag) { + case DW_TAG_null: + return; + case DW_TAG_compile_unit: { + UnitRI.Die = Die; + UnitRI.Ranges = Die.getAddressRanges(); + if (UnitRI.SortAndCheckRangesHasErrors(OS)) { + ++NumDebugInfoErrors; + Die.dump(OS, 0); + OS << "\n"; + } + } break; + case DW_TAG_subprogram: { + VRI.RI.Ranges = Die.getAddressRanges(); + if (VRI.RI.SortAndCheckRangesHasErrors(OS)) { + ++NumDebugInfoErrors; + Die.dump(OS, 0); + OS << "\n"; + } + if (VRI.RI.Ranges.empty()) + break; + // We need to keep track of all function ranges for + // .debug_aranges and .debug_info verifiers + AllFunctionDieRangeInfos.insert(VRI.RI); + + if (!UnitRI.Ranges.empty() &&!UnitRI.Contains(VRI.RI)) { + ++NumDebugInfoErrors; + OS << "error: CU DIE has child with address ranges " + "that are not contained in its ranges:\n"; + UnitRI.Die.dump(OS, 0); + Die.dump(OS, 0); + OS << "\n"; + } + } break; + case DW_TAG_lexical_block: + case DW_TAG_inlined_subroutine: { + VRI.RI.Ranges = Die.getAddressRanges(); + if (VRI.RI.SortAndCheckRangesHasErrors(OS)) { + ++NumDebugInfoErrors; + Die.dump(OS, 0); + OS << "\n"; + } + if (VRI.RI.Ranges.empty()) + break; + // Add any lexical block and inlined funtions to the parent's VerifyDieInfo + // so it can verify that none of these ranges overlap. + ParentVRI.ChildRangesCantOverlap.insert(VRI.RI); + // Check to make sure our parent contains all ranges for this Die. + if (!ParentVRI.RI.Contains(VRI.RI)) { + ++NumDebugInfoErrors; + OS << "error: DIE has a child " << TagString(Tag) + << " DIE whose address ranges that are not contained " + "in its ranges:\n"; + ParentVRI.RI.Die.dump(OS, 0); + Die.dump(OS, 0); + } + } break; + default: + break; + } + // Verify the attributes and forms + for (auto AttrValue : Die.attributes()) { + verifyDebugInfoAttribute(Die, AttrValue); + verifyDebugInfoForm(Die, AttrValue); + } + + for (DWARFDie Child : Die) + verifyDie(Child, UnitRI, VRI); + + // Verify that any address ranges from this DIE's children don't overlap. + if (!VRI.ChildRangesCantOverlap.empty()) { + verifyNoRangesOverlap(VRI.ChildRangesCantOverlap); + } +} +void DWARFVerifier::verifyDebugInfoAttribute(const DWARFDie &Die, DWARFAttribute &AttrValue) { const auto Attr = AttrValue.Attr; switch (Attr) { @@ -68,7 +243,7 @@ } } -void DWARFVerifier::verifyDebugInfoForm(DWARFDie &Die, +void DWARFVerifier::verifyDebugInfoForm(const DWARFDie &Die, DWARFAttribute &AttrValue) { const auto Form = AttrValue.Value.getForm(); switch (Form) { @@ -136,7 +311,7 @@ } } -void DWARFVerifier::veifyDebugInfoReferences() { +void DWARFVerifier::verifyDebugInfoReferences() { // 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"; @@ -156,23 +331,25 @@ } } +void DWARFVerifier::verifyDebugInfoOverlappingFunctionRanges() { + // Now go through all function address ranges and check for any that + // overlap. All function range infos were added to a std::set that we can + // traverse in order and do the checking for overlaps. + OS << "Verifying .debug_info function address ranges for overlap...\n"; + verifyNoRangesOverlap(AllFunctionDieRangeInfos); +} + bool DWARFVerifier::handleDebugInfo() { NumDebugInfoErrors = 0; OS << "Verifying .debug_info...\n"; + bool ExtractUnitDIEOnly = false; 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()) { - verifyDebugInfoAttribute(Die, AttrValue); - verifyDebugInfoForm(Die, AttrValue); - } - } + DieRangeInfo UnitRI; + VerifyDieInfo ParentVRI; + verifyDie(CU->getUnitDIE(ExtractUnitDIEOnly), UnitRI, ParentVRI); } - veifyDebugInfoReferences(); + verifyDebugInfoReferences(); + verifyDebugInfoOverlappingFunctionRanges(); return NumDebugInfoErrors == 0; } Index: unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp =================================================================== --- unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp +++ unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp @@ -2142,4 +2142,252 @@ "offset:"); } +TEST(DWARFDebugInfo, TestDwarfVerifyCURangesIncomplete) { + // Create a single compile unit with a single function. The compile + // unit has a DW_AT_ranges attribute that doesn't fully contain the + // address range of the function. The verification should fail due to + // the CU ranges not containing all of the address ranges of all of the + // functions. + StringRef yamldata = R"( + debug_str: + - '' + - /tmp/main.c + debug_abbrev: + - Code: 0x00000001 + Tag: DW_TAG_compile_unit + Children: DW_CHILDREN_yes + Attributes: + - Attribute: DW_AT_low_pc + Form: DW_FORM_addr + - Attribute: DW_AT_high_pc + Form: DW_FORM_addr + - Attribute: DW_AT_name + Form: DW_FORM_strp + - Code: 0x00000002 + Tag: DW_TAG_subprogram + Children: DW_CHILDREN_no + Attributes: + - Attribute: DW_AT_low_pc + Form: DW_FORM_addr + - Attribute: DW_AT_high_pc + Form: DW_FORM_addr + debug_info: + - Length: + TotalLength: 46 + Version: 4 + AbbrOffset: 0 + AddrSize: 8 + Entries: + - AbbrCode: 0x00000001 + Values: + - Value: 0x0000000000001000 + - Value: 0x0000000000001500 + - Value: 0x0000000000000001 + - AbbrCode: 0x00000002 + Values: + - Value: 0x0000000000001000 + - Value: 0x0000000000002000 + - AbbrCode: 0x00000000 + Values: + )"; + auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata); + ASSERT_TRUE((bool)ErrOrSections); + DWARFContextInMemory DwarfContext(*ErrOrSections, 8); + VerifyError(DwarfContext, "error: CU DIE has child with address ranges that " + "are not contained in its ranges:"); +} + +TEST(DWARFDebugInfo, TestDwarfVerifyLexicalBlockRanges) { + // Create a single compile unit with a single function that has a lexical + // block whose address range is not contained in the function address range. + StringRef 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_yes + Attributes: + - Attribute: DW_AT_name + Form: DW_FORM_strp + - Attribute: DW_AT_low_pc + Form: DW_FORM_addr + - Attribute: DW_AT_high_pc + Form: DW_FORM_addr + - Code: 0x00000003 + Tag: DW_TAG_lexical_block + Children: DW_CHILDREN_no + Attributes: + - Attribute: DW_AT_low_pc + Form: DW_FORM_addr + - Attribute: DW_AT_high_pc + Form: DW_FORM_addr + debug_info: + - Length: + TotalLength: 52 + Version: 4 + AbbrOffset: 0 + AddrSize: 8 + Entries: + - AbbrCode: 0x00000001 + Values: + - Value: 0x0000000000000001 + - AbbrCode: 0x00000002 + Values: + - Value: 0x000000000000000D + - Value: 0x0000000000001000 + - Value: 0x0000000000002000 + - AbbrCode: 0x00000003 + Values: + - Value: 0x0000000000001000 + - Value: 0x0000000000002001 + - AbbrCode: 0x00000000 + Values: + - AbbrCode: 0x00000000 + Values: + )"; + auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata); + ASSERT_TRUE((bool)ErrOrSections); + DWARFContextInMemory DwarfContext(*ErrOrSections, 8); + VerifyError(DwarfContext, "error: DIE has a child DW_TAG_lexical_block DIE " + "whose address ranges that are not contained in " + "its ranges:"); +} + +TEST(DWARFDebugInfo, TestDwarfVerifyOverlappingFunctionRanges) { + // Create a single compile unit with a two functions that have overlapping + // address ranges. + StringRef yamldata = R"( + debug_str: + - '' + - /tmp/main.c + - main + - foo + 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_low_pc + Form: DW_FORM_addr + - Attribute: DW_AT_high_pc + Form: DW_FORM_addr + debug_info: + - Length: + TotalLength: 55 + Version: 4 + AbbrOffset: 0 + AddrSize: 8 + Entries: + - AbbrCode: 0x00000001 + Values: + - Value: 0x0000000000000001 + - AbbrCode: 0x00000002 + Values: + - Value: 0x000000000000000D + - Value: 0x0000000000001000 + - Value: 0x0000000000002000 + - AbbrCode: 0x00000002 + Values: + - Value: 0x0000000000000012 + - Value: 0x0000000000001FFF + - Value: 0x0000000000002000 + - AbbrCode: 0x00000000 + Values: + )"; + auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata); + ASSERT_TRUE((bool)ErrOrSections); + DWARFContextInMemory DwarfContext(*ErrOrSections, 8); + VerifyError(DwarfContext, "error: DIEs have overlapping address ranges:"); +} + +TEST(DWARFDebugInfo, TestDwarfVerifyOverlappingLexicalBlockRanges) { + // Create a single compile unit with a two functions that have overlapping + // address ranges. + StringRef 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_low_pc + Form: DW_FORM_addr + - Attribute: DW_AT_high_pc + Form: DW_FORM_addr + - Attribute: DW_AT_name + Form: DW_FORM_strp + - Code: 0x00000002 + Tag: DW_TAG_subprogram + Children: DW_CHILDREN_yes + Attributes: + - Attribute: DW_AT_name + Form: DW_FORM_strp + - Attribute: DW_AT_low_pc + Form: DW_FORM_addr + - Attribute: DW_AT_high_pc + Form: DW_FORM_addr + - Code: 0x00000003 + Tag: DW_TAG_lexical_block + Children: DW_CHILDREN_no + Attributes: + - Attribute: DW_AT_low_pc + Form: DW_FORM_addr + - Attribute: DW_AT_high_pc + Form: DW_FORM_addr + debug_info: + - Length: + TotalLength: 85 + Version: 4 + AbbrOffset: 0 + AddrSize: 8 + Entries: + - AbbrCode: 0x00000001 + Values: + - Value: 0x0000000000001000 + - Value: 0x0000000000002000 + - Value: 0x0000000000000001 + - AbbrCode: 0x00000002 + Values: + - Value: 0x000000000000000D + - Value: 0x0000000000001000 + - Value: 0x0000000000002000 + - AbbrCode: 0x00000003 + Values: + - Value: 0x0000000000001100 + - Value: 0x0000000000001300 + - AbbrCode: 0x00000003 + Values: + - Value: 0x00000000000012FF + - Value: 0x0000000000001300 + - AbbrCode: 0x00000000 + Values: + - AbbrCode: 0x00000000 + Values: + )"; + auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata); + ASSERT_TRUE((bool)ErrOrSections); + DWARFContextInMemory DwarfContext(*ErrOrSections, 8); + VerifyError(DwarfContext, "error: DIEs have overlapping address ranges:"); +} + } // end anonymous namespace