From 2e42fb210e0c9ef819b242617b20df42b2083213 Mon Sep 17 00:00:00 2001 From: Jonas Devlieghere Date: Thu, 14 Sep 2017 10:38:18 +0000 Subject: [PATCH] [dwarfdump] Add DWARF verifiers for address ranges This patch started as an attempt to rebase Greg's differential (D32821). The result is both quite similar and different at the same time. It adds the following checks: - Verify that all address ranges in a DIE are valid. - Verify that no ranges within the DIE overlap. - Verify that no ranges overlap with the ranges of a sibling. - Verify that children are completely contained in its (direct) parent's address range. (unless both are subprograms) Differential revision: https://reviews.llvm.org/D37696 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@313250 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../DebugInfo/DWARF/DWARFDebugRangeList.h | 30 + include/llvm/DebugInfo/DWARF/DWARFDie.h | 4 + include/llvm/DebugInfo/DWARF/DWARFVerifier.h | 64 +- lib/DebugInfo/DWARF/DWARFVerifier.cpp | 139 +++- .../DebugInfo/DWARF/DWARFDebugInfoTest.cpp | 648 +++++++++++++++++- 5 files changed, 879 insertions(+), 6 deletions(-) diff --git a/include/llvm/DebugInfo/DWARF/DWARFDebugRangeList.h b/include/llvm/DebugInfo/DWARF/DWARFDebugRangeList.h index 421b6a4b561..0d97c2169e8 100644 --- a/include/llvm/DebugInfo/DWARF/DWARFDebugRangeList.h +++ b/include/llvm/DebugInfo/DWARF/DWARFDebugRangeList.h @@ -25,8 +25,38 @@ struct DWARFAddressRange { 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; diff --git a/include/llvm/DebugInfo/DWARF/DWARFDie.h b/include/llvm/DebugInfo/DWARF/DWARFDie.h index e28cc6c1785..9ae43958c89 100644 --- a/include/llvm/DebugInfo/DWARF/DWARFDie.h +++ b/include/llvm/DebugInfo/DWARF/DWARFDie.h @@ -308,6 +308,10 @@ inline bool operator!=(const DWARFDie &LHS, const DWARFDie &RHS) { return !(LHS == RHS); } +inline bool operator<(const DWARFDie &LHS, const DWARFDie &RHS) { + return LHS.getOffset() < RHS.getOffset(); +} + class DWARFDie::iterator : public iterator_facade_base { diff --git a/include/llvm/DebugInfo/DWARF/DWARFVerifier.h b/include/llvm/DebugInfo/DWARF/DWARFVerifier.h index 8dc7905ff92..3067def18cc 100644 --- a/include/llvm/DebugInfo/DWARF/DWARFVerifier.h +++ b/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 @@ struct DWARFSection; /// 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 @@ class DWARFVerifier { /// - 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 @@ public: 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 diff --git a/lib/DebugInfo/DWARF/DWARFVerifier.cpp b/lib/DebugInfo/DWARF/DWARFVerifier.cpp index 87b7be1eb84..9fd6463ba46 100644 --- a/lib/DebugInfo/DWARF/DWARFVerifier.cpp +++ b/lib/DebugInfo/DWARF/DWARFVerifier.cpp @@ -24,6 +24,83 @@ using namespace llvm; 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 @@ bool DWARFVerifier::verifyUnitContents(DWARFUnit Unit) { 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 @@ bool DWARFVerifier::handleDebugInfo() { 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; } diff --git a/unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp b/unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp index f687fc07417..57a61f73d83 100644 --- a/unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp +++ b/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 @@ void VerifyError(DWARFContext &DwarfContext, StringRef Error) { 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 @@ TEST(DWARFDebugInfo, TestErrorReportingPolicy) { 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 -- 2.40.0