Index: llvm/trunk/include/llvm/DebugInfo/DWARF/DWARFDebugRangeList.h =================================================================== --- llvm/trunk/include/llvm/DebugInfo/DWARF/DWARFDebugRangeList.h +++ llvm/trunk/include/llvm/DebugInfo/DWARF/DWARFDebugRangeList.h @@ -25,8 +25,38 @@ uint64_t LowPC; uint64_t HighPC; uint64_t SectionIndex; + + DWARFAddressRange() = default; + + /// Used for unit testing. + DWARFAddressRange(uint64_t LowPC, uint64_t HighPC, uint64_t SectionIndex = 0) + : LowPC(LowPC), HighPC(HighPC), SectionIndex(SectionIndex) {} + + /// Returns true if LowPC is smaller or equal to HighPC. This accounts for + /// dead-stripped ranges. + bool valid() const { return LowPC <= HighPC; } + + /// Returns true if [LowPC, HighPC) intersects with [RHS.LowPC, RHS.HighPC). + bool intersects(const DWARFAddressRange &RHS) const { + // Empty ranges can't intersect. + if (LowPC == HighPC || RHS.LowPC == RHS.HighPC) + return false; + return (LowPC < RHS.HighPC) && (HighPC > RHS.LowPC); + } + + /// Returns true if [LowPC, HighPC) fully contains [RHS.LowPC, RHS.HighPC). + bool contains(const DWARFAddressRange &RHS) const { + if (LowPC <= RHS.LowPC && RHS.LowPC <= HighPC) + return LowPC <= RHS.HighPC && RHS.HighPC <= HighPC; + return false; + } }; +static inline bool operator<(const DWARFAddressRange &LHS, + const DWARFAddressRange &RHS) { + return std::tie(LHS.LowPC, LHS.HighPC) < std::tie(RHS.LowPC, RHS.HighPC); +} + /// DWARFAddressRangesVector - represents a set of absolute address ranges. using DWARFAddressRangesVector = std::vector; Index: llvm/trunk/include/llvm/DebugInfo/DWARF/DWARFDie.h =================================================================== --- llvm/trunk/include/llvm/DebugInfo/DWARF/DWARFDie.h +++ llvm/trunk/include/llvm/DebugInfo/DWARF/DWARFDie.h @@ -308,6 +308,10 @@ return !(LHS == RHS); } +inline bool operator<(const DWARFDie &LHS, const DWARFDie &RHS) { + return LHS.getOffset() < RHS.getOffset(); +} + class DWARFDie::iterator : public iterator_facade_base { Index: llvm/trunk/include/llvm/DebugInfo/DWARF/DWARFVerifier.h =================================================================== --- llvm/trunk/include/llvm/DebugInfo/DWARF/DWARFVerifier.h +++ llvm/trunk/include/llvm/DebugInfo/DWARF/DWARFVerifier.h @@ -11,6 +11,8 @@ #define LLVM_DEBUGINFO_DWARF_DWARFVERIFIER_H #include "llvm/DebugInfo/DIContext.h" +#include "llvm/DebugInfo/DWARF/DWARFDebugRangeList.h" +#include "llvm/DebugInfo/DWARF/DWARFDie.h" #include #include @@ -30,6 +32,61 @@ /// A class that verifies DWARF debug information given a DWARF Context. class DWARFVerifier { +public: + /// A class that keeps the address range information for a single DIE. + struct DieRangeInfo { + DWARFDie Die; + + /// Sorted DWARFAddressRanges. + std::vector Ranges; + + /// Sorted DWARFAddressRangeInfo. + std::set Children; + + DieRangeInfo() = default; + DieRangeInfo(DWARFDie Die) : Die(Die) {} + + /// Used for unit testing. + DieRangeInfo(std::vector Ranges) + : Ranges(std::move(Ranges)) {} + + typedef std::vector::const_iterator + address_range_iterator; + typedef std::set::const_iterator die_range_info_iterator; + + /// Inserts the address range. If the range overlaps with an existing + /// range, the range is *not* added and an iterator to the overlapping + /// range is returned. + /// + /// This is used for finding overlapping ranges within the same DIE. + address_range_iterator insert(const DWARFAddressRange &R); + + /// Finds an address range in the sorted vector of ranges. + address_range_iterator findRange(const DWARFAddressRange &R) const { + const auto Begin = Ranges.cbegin(); + const auto End = Ranges.cend(); + auto Iter = std::upper_bound(Begin, End, R); + if (Iter != Begin) + --Iter; + return Iter; + } + + /// Inserts the address range info. If any of its ranges overlaps with a + /// range in an existing range info, the range info is *not* added and an + /// iterator to the overlapping range info. + /// + /// This is used for finding overlapping children of the same DIE. + die_range_info_iterator insert(const DieRangeInfo &RI); + + /// Return true if ranges in this object contains all ranges within RHS. + bool contains(const DieRangeInfo &RHS) const; + + /// Return true if any range in this object intersects with any range in + /// RHS. + bool intersects(const DieRangeInfo &RHS) const; + }; + +private: raw_ostream &OS; DWARFContext &DCtx; DIDumpOptions DumpOpts; @@ -84,7 +141,7 @@ /// - cases in which lowPC >= highPC /// /// \returns Number of errors that occured during verification. - unsigned verifyDieRanges(const DWARFDie &Die); + unsigned verifyDieRanges(const DWARFDie &Die, DieRangeInfo &ParentRI); /// Verifies the attribute's DWARF attribute and its value. /// @@ -196,6 +253,11 @@ bool handleAccelTables(); }; +static inline bool operator<(const DWARFVerifier::DieRangeInfo &LHS, + const DWARFVerifier::DieRangeInfo &RHS) { + return std::tie(LHS.Ranges, LHS.Die) < std::tie(RHS.Ranges, RHS.Die); +} + } // end namespace llvm #endif // LLVM_DEBUGINFO_DWARF_DWARFCONTEXT_H Index: llvm/trunk/lib/DebugInfo/DWARF/DWARFVerifier.cpp =================================================================== --- llvm/trunk/lib/DebugInfo/DWARF/DWARFVerifier.cpp +++ llvm/trunk/lib/DebugInfo/DWARF/DWARFVerifier.cpp @@ -24,6 +24,83 @@ using namespace dwarf; using namespace object; +DWARFVerifier::DieRangeInfo::address_range_iterator +DWARFVerifier::DieRangeInfo::insert(const DWARFAddressRange &R) { + const auto Begin = Ranges.cbegin(); + const auto End = Ranges.cend(); + auto Pos = std::lower_bound(Begin, End, R); + + if (Pos != End) { + if (Pos->intersects(R)) + return Pos; + if (Pos != Begin) { + auto Iter = Pos - 1; + if (Iter->intersects(R)) + return Iter; + } + } + + Ranges.insert(Pos, R); + return Ranges.cend(); +} + +DWARFVerifier::DieRangeInfo::die_range_info_iterator +DWARFVerifier::DieRangeInfo::insert(const DieRangeInfo &RI) { + const auto End = Children.end(); + auto Iter = Children.begin(); + while (Iter != End) { + if (Iter->intersects(RI)) + return Iter; + ++Iter; + } + Children.insert(RI); + return Children.cend(); +} + +bool DWARFVerifier::DieRangeInfo::contains(const DieRangeInfo &RHS) const { + // Both list of ranges are sorted so we can make this fast. + + if (Ranges.empty() || RHS.Ranges.empty()) + return false; + + // Since the ranges are sorted we can advance where we start searching with + // this object's ranges as we traverse RHS.Ranges. + const auto End = Ranges.cend(); + auto Iter = findRange(RHS.Ranges.front()); + + // Now linearly walk the ranges in this object and see if they contain each + // ranges from RHS.Ranges. + for (const auto &R : RHS.Ranges) { + while (Iter != End) { + if (Iter->contains(R)) + break; + ++Iter; + } + if (Iter == End) + return false; + } + return true; +} + +bool DWARFVerifier::DieRangeInfo::intersects(const DieRangeInfo &RHS) const { + if (Ranges.empty() || RHS.Ranges.empty()) + return false; + + const auto End = Ranges.end(); + auto Iter = findRange(RHS.Ranges.front()); + for (const auto &R : RHS.Ranges) { + if (R.HighPC <= Iter->LowPC) + continue; + while (Iter != End) { + if (Iter->intersects(R)) + return true; + ++Iter; + } + } + + return false; +} + bool DWARFVerifier::verifyUnitHeader(const DWARFDataExtractor DebugInfoData, uint32_t *Offset, unsigned UnitIndex, uint8_t &UnitType, bool &isUnitDWARF64) { @@ -94,12 +171,15 @@ auto Die = Unit.getDIEAtIndex(I); if (Die.getTag() == DW_TAG_null) continue; - NumUnitErrors += verifyDieRanges(Die); for (auto AttrValue : Die.attributes()) { NumUnitErrors += verifyDebugInfoAttribute(Die, AttrValue); NumUnitErrors += verifyDebugInfoForm(Die, AttrValue); } } + + DieRangeInfo RI; + DWARFDie Die = Unit.getUnitDIE(/* ExtractUnitDIEOnly = */ false); + NumUnitErrors += verifyDieRanges(Die, RI); return NumUnitErrors == 0; } @@ -210,16 +290,67 @@ return (isHeaderChainValid && NumDebugInfoErrors == 0); } -unsigned DWARFVerifier::verifyDieRanges(const DWARFDie &Die) { +unsigned DWARFVerifier::verifyDieRanges(const DWARFDie &Die, + DieRangeInfo &ParentRI) { unsigned NumErrors = 0; - for (auto Range : Die.getAddressRanges()) { - if (Range.LowPC >= Range.HighPC) { + + if (!Die.isValid()) + return NumErrors; + + DWARFAddressRangesVector Ranges = Die.getAddressRanges(); + + // Build RI for this DIE and check that ranges within this DIE do not + // overlap. + DieRangeInfo RI(Die); + for (auto Range : Ranges) { + if (!Range.valid()) { ++NumErrors; OS << format("error: Invalid address range [0x%08" PRIx64 " - 0x%08" PRIx64 "].\n", Range.LowPC, Range.HighPC); + continue; + } + + // Verify that ranges don't intersect. + const auto IntersectingRange = RI.insert(Range); + if (IntersectingRange != RI.Ranges.cend()) { + ++NumErrors; + OS << format("error: DIE has overlapping address ranges: [0x%08" PRIx64 + " - 0x%08" PRIx64 "] and [0x%08" PRIx64 " - 0x%08" PRIx64 + "].\n", + Range.LowPC, Range.HighPC, IntersectingRange->LowPC, + IntersectingRange->HighPC); + break; } } + + // Verify that children don't intersect. + const auto IntersectingChild = ParentRI.insert(RI); + if (IntersectingChild != ParentRI.Children.cend()) { + ++NumErrors; + OS << "error: DIEs have overlapping address ranges:"; + Die.dump(OS, 0); + IntersectingChild->Die.dump(OS, 0); + OS << "\n"; + } + + // Verify that ranges are contained within their parent. + bool ShouldBeContained = !Ranges.empty() && !ParentRI.Ranges.empty() && + !(Die.getTag() == DW_TAG_subprogram && + ParentRI.Die.getTag() == DW_TAG_subprogram); + if (ShouldBeContained && !ParentRI.contains(RI)) { + ++NumErrors; + OS << "error: DIE address ranges are not " + "contained in its parent's ranges:"; + Die.dump(OS, 0); + ParentRI.Die.dump(OS, 0); + OS << "\n"; + } + + // Recursively check children. + for (DWARFDie Child : Die) + NumErrors += verifyDieRanges(Child, RI); + return NumErrors; } Index: llvm/trunk/unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp =================================================================== --- llvm/trunk/unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp +++ llvm/trunk/unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp @@ -20,6 +20,7 @@ #include "llvm/DebugInfo/DWARF/DWARFContext.h" #include "llvm/DebugInfo/DWARF/DWARFDie.h" #include "llvm/DebugInfo/DWARF/DWARFFormValue.h" +#include "llvm/DebugInfo/DWARF/DWARFVerifier.h" #include "llvm/MC/MCContext.h" #include "llvm/MC/MCSectionELF.h" #include "llvm/MC/MCStreamer.h" @@ -1672,9 +1673,15 @@ EXPECT_TRUE(Str.str().contains(Error)); } +void VerifySuccess(DWARFContext &DwarfContext) { + SmallString<1024> Str; + raw_svector_ostream Strm(Str); + EXPECT_TRUE(DwarfContext.verify(Strm, DIDT_All)); +} + TEST(DWARFDebugInfo, TestDwarfVerifyInvalidCURef) { // Create a single compile unit with a single function that has a DW_AT_type - // that is CU relative. The CU offset is not valid becuase it is larger than + // that is CU relative. The CU offset is not valid because it is larger than // the compile unit itself. const char *yamldata = R"( @@ -2347,4 +2354,643 @@ EXPECT_TRUE(Errors == 1); } +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); + std::unique_ptr DwarfContext = + DWARFContext::create(*ErrOrSections, 8); + VerifyError(*DwarfContext, "error: DIE address ranges are not " + "contained in its parent's 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); + std::unique_ptr DwarfContext = + DWARFContext::create(*ErrOrSections, 8); + VerifyError(*DwarfContext, "error: DIE address ranges are not " + "contained in its parent's 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); + std::unique_ptr DwarfContext = + DWARFContext::create(*ErrOrSections, 8); + VerifyError(*DwarfContext, "error: DIEs have overlapping address ranges:"); +} + +TEST(DWARFDebugInfo, TestDwarfVerifyOverlappingLexicalBlockRanges) { + // Create a single compile unit with a one function that has two lexical + // blocks with 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); + std::unique_ptr DwarfContext = + DWARFContext::create(*ErrOrSections, 8); + VerifyError(*DwarfContext, "error: DIEs have overlapping address ranges:"); +} + +TEST(DWARFDebugInfo, TestDwarfVerifyInvalidDIERange) { + // Create a single compile unit with a single function that has an invalid + // address range where the high PC is smaller than the low PC. + 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_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: 34 + Version: 4 + AbbrOffset: 0 + AddrSize: 8 + Entries: + - AbbrCode: 0x00000001 + Values: + - Value: 0x0000000000000001 + - AbbrCode: 0x00000002 + Values: + - Value: 0x000000000000000D + - Value: 0x0000000000001000 + - Value: 0x0000000000000900 + - AbbrCode: 0x00000000 + Values: + )"; + auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata); + ASSERT_TRUE((bool)ErrOrSections); + std::unique_ptr DwarfContext = + DWARFContext::create(*ErrOrSections, 8); + VerifyError(*DwarfContext, "error: Invalid address range"); +} + +TEST(DWARFDebugInfo, TestDwarfVerifyElidedDoesntFail) { + // Create a single compile unit with two functions: one that has a valid range + // and one whose low and high PC are the same. When the low and high PC are + // the same, this indicates the function was dead code stripped. We want to + // ensure that verification succeeds. + StringRef yamldata = R"( + debug_str: + - '' + - /tmp/main.c + - main + - elided + 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_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: 71 + 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: 0x00000002 + Values: + - Value: 0x0000000000000012 + - Value: 0x0000000000002000 + - Value: 0x0000000000002000 + - AbbrCode: 0x00000000 + Values: + )"; + auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata); + ASSERT_TRUE((bool)ErrOrSections); + std::unique_ptr DwarfContext = + DWARFContext::create(*ErrOrSections, 8); + VerifySuccess(*DwarfContext); +} + +TEST(DWARFDebugInfo, TestDwarfVerifyNestedFunctions) { + // Create a single compile unit with a nested function which is not contained + // in its parent. Although LLVM doesn't generate this, it is valid accoridng + // to the DWARF standard. + StringRef yamldata = R"( + debug_str: + - '' + - /tmp/main.c + - main + - nested + 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 + debug_info: + - Length: + TotalLength: 73 + Version: 4 + AbbrOffset: 0 + AddrSize: 8 + Entries: + - AbbrCode: 0x00000001 + Values: + - Value: 0x0000000000001000 + - Value: 0x0000000000002000 + - Value: 0x0000000000000001 + - AbbrCode: 0x00000002 + Values: + - Value: 0x000000000000000D + - Value: 0x0000000000001000 + - Value: 0x0000000000001500 + - AbbrCode: 0x00000002 + Values: + - Value: 0x0000000000000012 + - Value: 0x0000000000001500 + - Value: 0x0000000000002000 + - AbbrCode: 0x00000000 + Values: + - AbbrCode: 0x00000000 + Values: + - AbbrCode: 0x00000000 + Values: + )"; + auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata); + ASSERT_TRUE((bool)ErrOrSections); + std::unique_ptr DwarfContext = + DWARFContext::create(*ErrOrSections, 8); + VerifySuccess(*DwarfContext); +} + +TEST(DWARFDebugInfo, TestDwarfRangesContains) { + DWARFAddressRange R(0x10, 0x20); + + //---------------------------------------------------------------------- + // Test ranges that start before R... + //---------------------------------------------------------------------- + // Other range ends before start of R + ASSERT_FALSE(R.contains({0x0f, 0x10})); + // Other range end address is start of a R + ASSERT_FALSE(R.contains({0x0f, 0x11})); + // Other range end address is at and of R + ASSERT_FALSE(R.contains({0x0f, 0x20})); + // Other range end address is past end of R + ASSERT_FALSE(R.contains({0x0f, 0x40})); + + //---------------------------------------------------------------------- + // Test ranges that start at R's start address + //---------------------------------------------------------------------- + // Ensure empty ranges matches + ASSERT_TRUE(R.contains({0x10, 0x10})); + // 1 byte of Range + ASSERT_TRUE(R.contains({0x10, 0x11})); + // same as Range + ASSERT_TRUE(R.contains({0x10, 0x20})); + // 1 byte past Range + ASSERT_FALSE(R.contains({0x10, 0x21})); + + //---------------------------------------------------------------------- + // Test ranges that start inside Range + //---------------------------------------------------------------------- + // empty in range + ASSERT_TRUE(R.contains({0x11, 0x11})); + // all in Range + ASSERT_TRUE(R.contains({0x11, 0x1f})); + // ends at end of Range + ASSERT_TRUE(R.contains({0x11, 0x20})); + // ends past Range + ASSERT_FALSE(R.contains({0x11, 0x21})); + + //---------------------------------------------------------------------- + // Test ranges that start at last bytes of Range + //---------------------------------------------------------------------- + // ends at end of Range + ASSERT_TRUE(R.contains({0x1f, 0x20})); + // ends past Range + ASSERT_FALSE(R.contains({0x1f, 0x21})); + + //---------------------------------------------------------------------- + // Test ranges that start after Range + //---------------------------------------------------------------------- + // empty considered in Range + ASSERT_TRUE(R.contains({0x20, 0x20})); + // valid past Range + ASSERT_FALSE(R.contains({0x20, 0x21})); +} + +TEST(DWARFDebugInfo, TestDWARFDieRangeInfoContains) { + DWARFVerifier::DieRangeInfo Ranges({{0x10, 0x20}, {0x30, 0x40}}); + + ASSERT_FALSE(Ranges.contains({{{0x0f, 0x10}}})); + ASSERT_FALSE(Ranges.contains({{{0x20, 0x30}}})); + ASSERT_FALSE(Ranges.contains({{{0x40, 0x41}}})); + ASSERT_TRUE(Ranges.contains({{{0x10, 0x20}}})); + ASSERT_TRUE(Ranges.contains({{{0x11, 0x12}}})); + ASSERT_TRUE(Ranges.contains({{{0x1f, 0x20}}})); + ASSERT_TRUE(Ranges.contains({{{0x30, 0x40}}})); + ASSERT_TRUE(Ranges.contains({{{0x31, 0x32}}})); + ASSERT_TRUE(Ranges.contains({{{0x3f, 0x40}}})); + ASSERT_TRUE(Ranges.contains({{{0x10, 0x20}, {0x30, 0x40}}})); + ASSERT_TRUE(Ranges.contains({{{0x11, 0x12}, {0x31, 0x32}}})); + ASSERT_TRUE(Ranges.contains( + {{{0x11, 0x12}, {0x12, 0x13}, {0x31, 0x32}, {0x32, 0x33}}})); + ASSERT_FALSE(Ranges.contains({{{0x11, 0x12}, + {0x12, 0x13}, + {0x20, 0x21}, + {0x31, 0x32}, + {0x32, 0x33}}})); + ASSERT_FALSE(Ranges.contains( + {{{0x11, 0x12}, {0x12, 0x13}, {0x31, 0x32}, {0x32, 0x41}}})); +} + +namespace { + +void AssertRangesIntersect(const DWARFAddressRange &LHS, + const DWARFAddressRange &RHS) { + ASSERT_TRUE(LHS.intersects(RHS)); + ASSERT_TRUE(RHS.intersects(LHS)); +} +void AssertRangesDontIntersect(const DWARFAddressRange &LHS, + const DWARFAddressRange &RHS) { + ASSERT_FALSE(LHS.intersects(RHS)); + ASSERT_FALSE(RHS.intersects(LHS)); +} + +void AssertRangesIntersect(const DWARFVerifier::DieRangeInfo &LHS, + const DWARFAddressRangesVector &Ranges) { + DWARFVerifier::DieRangeInfo RHS(Ranges); + ASSERT_TRUE(LHS.intersects(RHS)); + ASSERT_TRUE(RHS.intersects(LHS)); +} + +void AssertRangesDontIntersect(const DWARFVerifier::DieRangeInfo &LHS, + const DWARFAddressRangesVector &Ranges) { + DWARFVerifier::DieRangeInfo RHS(Ranges); + ASSERT_FALSE(LHS.intersects(RHS)); + ASSERT_FALSE(RHS.intersects(LHS)); +} + +} // namespace +TEST(DWARFDebugInfo, TestDwarfRangesIntersect) { + DWARFAddressRange R(0x10, 0x20); + + //---------------------------------------------------------------------- + // Test ranges that start before R... + //---------------------------------------------------------------------- + // Other range ends before start of R + AssertRangesDontIntersect(R, {0x00, 0x10}); + // Other range end address is start of a R + AssertRangesIntersect(R, {0x00, 0x11}); + // Other range end address is in R + AssertRangesIntersect(R, {0x00, 0x15}); + // Other range end address is at and of R + AssertRangesIntersect(R, {0x00, 0x20}); + // Other range end address is past end of R + AssertRangesIntersect(R, {0x00, 0x40}); + + //---------------------------------------------------------------------- + // Test ranges that start at R's start address + //---------------------------------------------------------------------- + // Ensure empty ranges doesn't match + AssertRangesDontIntersect(R, {0x10, 0x10}); + // 1 byte of Range + AssertRangesIntersect(R, {0x10, 0x11}); + // same as Range + AssertRangesIntersect(R, {0x10, 0x20}); + // 1 byte past Range + AssertRangesIntersect(R, {0x10, 0x21}); + + //---------------------------------------------------------------------- + // Test ranges that start inside Range + //---------------------------------------------------------------------- + // empty in range + AssertRangesDontIntersect(R, {0x11, 0x11}); + // all in Range + AssertRangesIntersect(R, {0x11, 0x1f}); + // ends at end of Range + AssertRangesIntersect(R, {0x11, 0x20}); + // ends past Range + AssertRangesIntersect(R, {0x11, 0x21}); + + //---------------------------------------------------------------------- + // Test ranges that start at last bytes of Range + //---------------------------------------------------------------------- + // ends at end of Range + AssertRangesIntersect(R, {0x1f, 0x20}); + // ends past Range + AssertRangesIntersect(R, {0x1f, 0x21}); + + //---------------------------------------------------------------------- + // Test ranges that start after Range + //---------------------------------------------------------------------- + // empty just past in Range + AssertRangesDontIntersect(R, {0x20, 0x20}); + // valid past Range + AssertRangesDontIntersect(R, {0x20, 0x21}); +} + +TEST(DWARFDebugInfo, TestDWARFDieRangeInfoIntersects) { + + DWARFVerifier::DieRangeInfo Ranges({{0x10, 0x20}, {0x30, 0x40}}); + + // Test empty range + AssertRangesDontIntersect(Ranges, {}); + // Test range that appears before all ranges in Ranges + AssertRangesDontIntersect(Ranges, {{0x00, 0x10}}); + // Test range that appears between ranges in Ranges + AssertRangesDontIntersect(Ranges, {{0x20, 0x30}}); + // Test range that appears after ranges in Ranges + AssertRangesDontIntersect(Ranges, {{0x40, 0x50}}); + + // Test range that start before first range + AssertRangesIntersect(Ranges, {{0x00, 0x11}}); + // Test range that start at first range + AssertRangesIntersect(Ranges, {{0x10, 0x11}}); + // Test range that start in first range + AssertRangesIntersect(Ranges, {{0x11, 0x12}}); + // Test range that start at end of first range + AssertRangesIntersect(Ranges, {{0x1f, 0x20}}); + // Test range that starts at end of first range + AssertRangesDontIntersect(Ranges, {{0x20, 0x21}}); + // Test range that starts at end of first range + AssertRangesIntersect(Ranges, {{0x20, 0x31}}); + + // Test range that start before second range and ends before second + AssertRangesDontIntersect(Ranges, {{0x2f, 0x30}}); + // Test range that start before second range and ends in second + AssertRangesIntersect(Ranges, {{0x2f, 0x31}}); + // Test range that start at second range + AssertRangesIntersect(Ranges, {{0x30, 0x31}}); + // Test range that start in second range + AssertRangesIntersect(Ranges, {{0x31, 0x32}}); + // Test range that start at end of second range + AssertRangesIntersect(Ranges, {{0x3f, 0x40}}); + // Test range that starts at end of second range + AssertRangesDontIntersect(Ranges, {{0x40, 0x41}}); +} + } // end anonymous namespace