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,60 @@ /// A class that verifies DWARF debug information given a DWARF Context. class DWARFVerifier { + struct RangeInfoType { + DWARFDie Die; + DWARFAddressRangesVector Ranges; + + RangeInfoType() : Die(), Ranges() {} + RangeInfoType(DWARFDie D, const DWARFAddressRangesVector &R); + /// Return true if this object contains all ranges within RHS. + bool Contains(const RangeInfoType &RHS); + bool DoesIntersect(const RangeInfoType &RHS) const; + void Dump(raw_ostream &OS) const; + bool operator<(const RangeInfoType &RHS) const; + static bool CheckForRangeErrors(raw_ostream &OS, + DWARFAddressRangesVector &Ranges); + }; + 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 AllFunctionRangeInfos; + /// A vector of range infos for all DIEs where the index is the depth of the + /// DIE. This helps to verify address ranges so we can tell if a child's + /// address ranges are fully contained in a parent's address ranges. + std::vector DieRangeInfos; + 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 AllFunctionRangeInfos 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 verifyDebugInfoTag(DWARFDie &Die); + + /// 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: @@ -60,7 +109,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,6 +23,144 @@ using namespace dwarf; using namespace object; +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::RangeInfoType::CheckForRangeErrors( + raw_ostream &OS, DWARFAddressRangesVector &Ranges) { + 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::RangeInfoType::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"; +} + +bool DWARFVerifier::RangeInfoType::Contains(const RangeInfoType &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::RangeInfoType::DoesIntersect( + const RangeInfoType &RHS) const { + for (const auto &R : RHS.Ranges) + for (const auto &L : Ranges) + if (RangesIntersect(R, L)) + return true; + return false; +} + +bool DWARFVerifier::RangeInfoType::operator<(const RangeInfoType &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::verifyDebugInfoTag(DWARFDie &Die) { + const auto Tag = Die.getTag(); + const uint32_t Depth = Die.getDebugInfoEntry()->getDepth(); + if (Depth >= DieRangeInfos.size()) + DieRangeInfos.resize(Depth + 1); + DieRangeInfos[Depth].Die = Die; + DieRangeInfos[Depth].Ranges.clear(); + switch (Tag) { + case DW_TAG_compile_unit: { + DieRangeInfos[Depth].Ranges = Die.getAddressRanges(); + if (RangeInfoType::CheckForRangeErrors(OS, DieRangeInfos[Depth].Ranges)) { + ++NumDebugInfoErrors; + Die.dump(OS, 0); + OS << "\n"; + } + } break; + case DW_TAG_subprogram: + case DW_TAG_lexical_block: + case DW_TAG_inlined_subroutine: { + DieRangeInfos[Depth].Ranges = Die.getAddressRanges(); + if (RangeInfoType::CheckForRangeErrors(OS, DieRangeInfos[Depth].Ranges)) { + ++NumDebugInfoErrors; + Die.dump(OS, 0); + OS << "\n"; + } + if (DieRangeInfos[Depth].Ranges.empty()) + break; + if (Tag == DW_TAG_subprogram) { + // We need to keep track of all function ranges for + // .debug_aranges and .debug_info verifiers + AllFunctionRangeInfos.insert(DieRangeInfos[Depth]); + + // Check the if the compile unit has valid ranges + if (!DieRangeInfos[0].Ranges.empty()) { + if (!DieRangeInfos[0].Contains(DieRangeInfos[Depth])) { + ++NumDebugInfoErrors; + OS << "error: CU DIE has child with address ranges " + "that are not contained in its ranges:\n"; + DieRangeInfos[0].Die.dump(OS, 0); + Die.dump(OS, 0); + OS << "\n"; + } + } + } else { + if (!DieRangeInfos[Depth - 1].Contains(DieRangeInfos[Depth])) { + ++NumDebugInfoErrors; + OS << "error: DIE has a child " << TagString(Tag) + << " DIE whose address ranges that are not contained " + "in its ranges:\n"; + DieRangeInfos[Depth - 1].Die.dump(OS, 0); + Die.dump(OS, 0); + } + } + } break; + default: + break; + } +} void DWARFVerifier::verifyDebugInfoAttribute(DWARFDie &Die, DWARFAttribute &AttrValue) { const auto Attr = AttrValue.Attr; @@ -136,7 +274,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,6 +294,28 @@ } } +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"; + + auto End = AllFunctionRangeInfos.end(); + auto Prev = End; + for (auto Curr = AllFunctionRangeInfos.begin(); Curr != End; ++Curr) { + if (Prev != End) { + if (Prev->DoesIntersect(*Curr)) { + ++NumDebugInfoErrors; + OS << "error: two function DIEs have overlapping address ranges:\n"; + Prev->Die.dump(OS, 0); + Curr->Die.dump(OS, 0); + OS << "\n"; + } + } + Prev = Curr; + } +} + bool DWARFVerifier::handleDebugInfo() { NumDebugInfoErrors = 0; OS << "Verifying .debug_info...\n"; @@ -166,13 +326,15 @@ const auto Tag = Die.getTag(); if (Tag == DW_TAG_null) continue; + verifyDebugInfoTag(Die); for (auto AttrValue : Die.attributes()) { verifyDebugInfoAttribute(Die, AttrValue); verifyDebugInfoForm(Die, AttrValue); } } } - 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,180 @@ "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: two function DIEs have overlapping address ranges:"); +} + } // end anonymous namespace