Index: include/llvm/DebugInfo/DWARF/DWARFDie.h =================================================================== --- include/llvm/DebugInfo/DWARF/DWARFDie.h +++ include/llvm/DebugInfo/DWARF/DWARFDie.h @@ -302,6 +302,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: 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,100 @@ /// A class that verifies DWARF debug information given a DWARF Context. class DWARFVerifier { +public: + struct DWARFRange { + uint64_t Start; + uint64_t End; + DWARFRange(uint64_t S, uint64_t E) : Start(S), End(E) {} + /// Returns true if [Start, End) intersects with [RHS.Start, RHS.End). + bool intersects(const DWARFRange &RHS) const { + // Empty ranges can't intersect. + if (Start == End || RHS.Start == RHS.End) + return false; + return (Start < RHS.End) && (End > RHS.Start); + } + /// Returns true if [Start, End) fully contains [RHS.Start, RHS.End). + bool contains(const DWARFRange &RHS) const { + if (Start <= RHS.Start && RHS.Start < End) + return Start < RHS.End && RHS.End <= End; + return false; + } + }; + + /// A class that keeps the address range information for a single DIE. + struct DieRangeInfo { + DWARFDie Die; + /// Sorted address ranges. + std::vector Ranges; + DieRangeInfo() = default; + /// Constructor used for unit testing. + DieRangeInfo(const DWARFAddressRangesVector &R) { insert(R); } + /// Return true if ranges in this object contains all ranges within RHS. + bool contains(const DieRangeInfo &RHS) const; + /// Return true if any ranges in RHS overlap with ranges in this object. + bool intersects(const DieRangeInfo &RHS) const; + void dump(raw_ostream &OS) const; + /// Extract address ranges from the Die in this object and return true if + /// there are errors in the ranges. + bool extractRangesAndReportErrors(raw_ostream &OS); + /// Return true if this object doesn't fully contain the ranges in RI + /// and report errors to the stream. + bool reportErrorIfNotContained(raw_ostream &OS, const DieRangeInfo &RI, + const char *Error) const; + /// Inserts the unsorted ranges and returns true if errors were found + /// during insertion + bool insert(const DWARFAddressRangesVector &UnsortedRanges); + }; + + /// A class that ensures that no two DieRangeInfo's overlap. + struct NonOverlappingRanges { + std::set RangeSet; + + /// Returns true if the sibling ranges + Optional GetOverlappingRangeInfo(const DieRangeInfo &RI) const; + + bool insertAndReportErrors(raw_ostream &OS, const DieRangeInfo &RI); + }; + + /// A class the keeps information for a DIE that contains child DIEs whose + /// address ranges must be contained within its ranges and whose direct + /// children that have address ranges must not overlap. + struct DieInfo { + DieRangeInfo RI; + NonOverlappingRanges NOR; + /// Returns true if an error was found when inserting Die. + bool addContainedDieAndReportErrors(raw_ostream &OS, DieRangeInfo &DieRI); + }; + +private: raw_ostream &OS; DWARFContext &DCtx; + DieInfo UnitDI; /// 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; + 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 + /// \param ParantDI The parent DIE's range and overlap information. + void verifyDie(const DWARFDie &Die, DieInfo &ParentDI); + /// Verifies the attribute's DWARF attribute and its value. /// /// This function currently checks for: @@ -93,6 +182,16 @@ bool handleDebugLine(); }; +static inline bool operator<(const DWARFVerifier::DWARFRange &LHS, + const DWARFVerifier::DWARFRange &RHS) { + return std::tie(LHS.Start, LHS.End) < std::tie(RHS.Start, RHS.End); +} + +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: lib/DebugInfo/DWARF/DWARFContext.cpp =================================================================== --- lib/DebugInfo/DWARF/DWARFContext.cpp +++ lib/DebugInfo/DWARF/DWARFContext.cpp @@ -294,248 +294,6 @@ return DWARFDie(); } -namespace { - -class Verifier { - raw_ostream &OS; - DWARFContext &DCtx; -public: - Verifier(raw_ostream &S, DWARFContext &D) : OS(S), DCtx(D) {} - - bool HandleDebugInfo() { - bool Success = true; - // 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; - - OS << "Verifying .debug_info...\n"; - for (const auto &CU : DCtx.compile_units()) { - unsigned NumDies = CU->getNumDIEs(); - for (unsigned I = 0; I < NumDies; ++I) { - auto Die = CU->getDIEAtIndex(I); - const auto Tag = Die.getTag(); - if (Tag == DW_TAG_null) - continue; - for (auto AttrValue : Die.attributes()) { - const auto Attr = AttrValue.Attr; - const auto Form = AttrValue.Value.getForm(); - switch (Attr) { - case DW_AT_ranges: - // Make sure the offset in the DW_AT_ranges attribute is valid. - if (auto SectionOffset = AttrValue.Value.getAsSectionOffset()) { - if (*SectionOffset >= DCtx.getRangeSection().Data.size()) { - Success = false; - OS << "error: DW_AT_ranges offset is beyond .debug_ranges " - "bounds:\n"; - Die.dump(OS, 0); - OS << "\n"; - } - } else { - Success = false; - OS << "error: DIE has invalid DW_AT_ranges encoding:\n"; - Die.dump(OS, 0); - OS << "\n"; - } - break; - case DW_AT_stmt_list: - // Make sure the offset in the DW_AT_stmt_list attribute is valid. - if (auto SectionOffset = AttrValue.Value.getAsSectionOffset()) { - if (*SectionOffset >= DCtx.getLineSection().Data.size()) { - Success = false; - OS << "error: DW_AT_stmt_list offset is beyond .debug_line " - "bounds: " - << format("0x%08" PRIx32, *SectionOffset) << "\n"; - CU->getUnitDIE().dump(OS, 0); - OS << "\n"; - } - } else { - Success = false; - OS << "error: DIE has invalid DW_AT_stmt_list encoding:\n"; - Die.dump(OS, 0); - OS << "\n"; - } - break; - - default: - break; - } - switch (Form) { - case DW_FORM_ref1: - case DW_FORM_ref2: - case DW_FORM_ref4: - case DW_FORM_ref8: - case DW_FORM_ref_udata: { - // Verify all CU relative references are valid CU offsets. - Optional RefVal = AttrValue.Value.getAsReference(); - assert(RefVal); - if (RefVal) { - auto DieCU = Die.getDwarfUnit(); - auto CUSize = DieCU->getNextUnitOffset() - DieCU->getOffset(); - auto CUOffset = AttrValue.Value.getRawUValue(); - if (CUOffset >= CUSize) { - Success = false; - OS << "error: " << FormEncodingString(Form) << " CU offset " - << format("0x%08" PRIx32, CUOffset) - << " is invalid (must be less than CU size of " - << format("0x%08" PRIx32, CUSize) << "):\n"; - Die.dump(OS, 0); - OS << "\n"; - } else { - // Valid reference, but we will verify it points to an actual - // DIE later. - ReferenceToDIEOffsets[*RefVal].insert(Die.getOffset()); - } - } - break; - } - case DW_FORM_ref_addr: { - // Verify all absolute DIE references have valid offsets in the - // .debug_info section. - Optional RefVal = AttrValue.Value.getAsReference(); - assert(RefVal); - if (RefVal) { - if(*RefVal >= DCtx.getInfoSection().Data.size()) { - Success = false; - OS << "error: DW_FORM_ref_addr offset beyond .debug_info " - "bounds:\n"; - Die.dump(OS, 0); - OS << "\n"; - } else { - // Valid reference, but we will verify it points to an actual - // DIE later. - ReferenceToDIEOffsets[*RefVal].insert(Die.getOffset()); - } - } - break; - } - case DW_FORM_strp: { - auto SecOffset = AttrValue.Value.getAsSectionOffset(); - assert(SecOffset); // DW_FORM_strp is a section offset. - if (SecOffset && *SecOffset >= DCtx.getStringSection().size()) { - Success = false; - OS << "error: DW_FORM_strp offset beyond .debug_str bounds:\n"; - Die.dump(OS, 0); - OS << "\n"; - } - break; - } - default: - break; - } - } - } - } - - // Take all references and make sure they point to an actual DIE by - // getting the DIE by offset and emitting an error - OS << "Verifying .debug_info references...\n"; - for (auto Pair: ReferenceToDIEOffsets) { - auto Die = DCtx.getDIEForOffset(Pair.first); - if (Die) - continue; - Success = false; - OS << "error: invalid DIE reference " << format("0x%08" PRIx64, Pair.first) - << ". Offset is in between DIEs:\n"; - for (auto Offset: Pair.second) { - auto ReferencingDie = DCtx.getDIEForOffset(Offset); - ReferencingDie.dump(OS, 0); - OS << "\n"; - } - OS << "\n"; - } - return Success; - } - - bool HandleDebugLine() { - std::map StmtListToDie; - bool Success = true; - OS << "Verifying .debug_line...\n"; - for (const auto &CU : DCtx.compile_units()) { - uint32_t LineTableOffset = 0; - auto CUDie = CU->getUnitDIE(); - auto StmtFormValue = CUDie.find(DW_AT_stmt_list); - if (!StmtFormValue) { - // No line table for this compile unit. - continue; - } - // Get the attribute value as a section offset. No need to produce an - // error here if the encoding isn't correct because we validate this in - // the .debug_info verifier. - if (auto StmtSectionOffset = toSectionOffset(StmtFormValue)) { - LineTableOffset = *StmtSectionOffset; - if (LineTableOffset >= DCtx.getLineSection().Data.size()) { - // Make sure we don't get a valid line table back if the offset - // is wrong. - assert(DCtx.getLineTableForUnit(CU.get()) == nullptr); - // Skip this line table as it isn't valid. No need to create an error - // here because we validate this in the .debug_info verifier. - continue; - } else { - auto Iter = StmtListToDie.find(LineTableOffset); - if (Iter != StmtListToDie.end()) { - Success = false; - OS << "error: two compile unit DIEs, " - << format("0x%08" PRIx32, Iter->second.getOffset()) << " and " - << format("0x%08" PRIx32, CUDie.getOffset()) - << ", have the same DW_AT_stmt_list section offset:\n"; - Iter->second.dump(OS, 0); - CUDie.dump(OS, 0); - OS << '\n'; - // Already verified this line table before, no need to do it again. - continue; - } - StmtListToDie[LineTableOffset] = CUDie; - } - } - auto LineTable = DCtx.getLineTableForUnit(CU.get()); - if (!LineTable) { - Success = false; - OS << "error: .debug_line[" << format("0x%08" PRIx32, LineTableOffset) - << "] was not able to be parsed for CU:\n"; - CUDie.dump(OS, 0); - OS << '\n'; - continue; - } - uint32_t MaxFileIndex = LineTable->Prologue.FileNames.size(); - uint64_t PrevAddress = 0; - uint32_t RowIndex = 0; - for (const auto &Row : LineTable->Rows) { - if (Row.Address < PrevAddress) { - Success = false; - OS << "error: .debug_line[" << format("0x%08" PRIx32, LineTableOffset) - << "] row[" << RowIndex - << "] decreases in address from previous row:\n"; - - DWARFDebugLine::Row::dumpTableHeader(OS); - if (RowIndex > 0) - LineTable->Rows[RowIndex - 1].dump(OS); - Row.dump(OS); - OS << '\n'; - } - - if (Row.File > MaxFileIndex) { - Success = false; - OS << "error: .debug_line[" << format("0x%08" PRIx32, LineTableOffset) - << "][" << RowIndex << "] has invalid file index " << Row.File - << " (valid values are [1," << MaxFileIndex << "]):\n"; - DWARFDebugLine::Row::dumpTableHeader(OS); - Row.dump(OS); - OS << '\n'; - } - if (Row.EndSequence) - PrevAddress = 0; - else - PrevAddress = Row.Address; - ++RowIndex; - } - } - return Success; - } -}; - -} // anonymous namespace - bool DWARFContext::verify(raw_ostream &OS, DIDumpType DumpType) { bool Success = true; DWARFVerifier verifier(OS, *this); Index: lib/DebugInfo/DWARF/DWARFVerifier.cpp =================================================================== --- lib/DebugInfo/DWARF/DWARFVerifier.cpp +++ lib/DebugInfo/DWARF/DWARFVerifier.cpp @@ -8,6 +8,7 @@ //===----------------------------------------------------------------------===// #include "llvm/DebugInfo/DWARF/DWARFVerifier.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/DebugInfo/DWARF/DWARFCompileUnit.h" #include "llvm/DebugInfo/DWARF/DWARFContext.h" #include "llvm/DebugInfo/DWARF/DWARFDebugLine.h" @@ -23,6 +24,220 @@ using namespace dwarf; using namespace object; +bool DWARFVerifier::DieRangeInfo::insert( + const DWARFAddressRangesVector &UnsortedRanges) { + bool Error = false; + for (const auto &UR : UnsortedRanges) { + DWARFRange R(UR.first, UR.second); + if (R.Start >= R.End) + continue; + auto Begin = Ranges.begin(); + auto End = Ranges.end(); + auto InsertPos = std::lower_bound(Begin, End, R); + if (!Error) { + bool RangeOverlaps = false; + if (InsertPos != End) { + if (InsertPos->intersects(R)) + RangeOverlaps = true; + else if (InsertPos != Begin) { + auto Iter = InsertPos - 1; + if (Iter->intersects(R)) + RangeOverlaps = true; + } + if (RangeOverlaps) { + Error = true; + } + } + // Insert the range into our sorted list + Ranges.insert(InsertPos, R); + } + } + return Error; +} + +bool DWARFVerifier::DieRangeInfo::extractRangesAndReportErrors( + raw_ostream &OS) { + Ranges.clear(); + auto UnsortedRanges = Die.getAddressRanges(); + bool HasErrors = false; + + auto ErasePos = + remove_if(UnsortedRanges, [&](const std::pair &R) { + if (R.first < R.second) + return false; + if (R.first > R.second) + HasErrors = true; + return false; + }); + UnsortedRanges.erase(ErasePos, UnsortedRanges.end()); + + if (HasErrors) + OS << "error: invalid range in DIE:\n"; + + if (insert(UnsortedRanges)) { + OS << "error: ranges in DIE overlap:\n"; + HasErrors = true; + } + if (HasErrors) { + Die.dump(OS, 0); + OS << "\n"; + } + 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%" PRIx64, R.Start) << "-" + << format("0x%" PRIx64, R.End) << ")"; + OS << "\n"; +} + +bool DWARFVerifier::DieRangeInfo::contains(const DieRangeInfo &RHS) const { + // Both list of ranges are sorted so we can make this fasts + auto Begin = Ranges.begin(); + auto End = Ranges.end(); + // Since the ranges are sorted we can advance where we start searching with + // this object's ranges as we traverse RHS.Ranges. + auto SearchBegin = Begin; + for (const auto &R : RHS.Ranges) { + auto Iter = std::lower_bound(SearchBegin, End, R); + if (Iter == Begin) + SearchBegin = Iter; + else { + SearchBegin = Iter - 1; + if (SearchBegin->contains(R)) + continue; + } + if (Iter != End && Iter->contains(R)) + continue; + return false; + } + return true; +} + +bool DWARFVerifier::DieRangeInfo::intersects(const DieRangeInfo &RHS) const { + auto Begin = Ranges.begin(); + auto End = Ranges.end(); + auto SearchBegin = Begin; + for (const auto &R : RHS.Ranges) { + auto Iter = std::lower_bound(SearchBegin, End, R); + if (Iter != End && Iter->intersects(R)) + return true; + if (Iter != Begin) { + auto Prev = Iter - 1; + if (Prev->intersects(R)) + return true; + } + SearchBegin = Iter; + } + return false; +} + +bool DWARFVerifier::DieRangeInfo::reportErrorIfNotContained( + raw_ostream &OS, const DieRangeInfo &RI, const char *Error) const { + if (contains(RI)) + return false; + OS << Error; + Die.dump(OS, 0); + RI.Die.dump(OS, 0); + OS << "\n"; + return true; +} + +bool DWARFVerifier::DieInfo::addContainedDieAndReportErrors( + raw_ostream &OS, DieRangeInfo &DieRI) { + bool HasErrors = DieRI.extractRangesAndReportErrors(OS); + + // If this DIE has not valid ranges to check then we are done. + if (DieRI.Ranges.empty()) + return HasErrors; + + // Die has address ranges so we need to check that its address ranges are + // contained in this DieInfo's address ranges except if this is a compile + // unit that doesn't have address range(s). + bool IsCompileUnit = RI.Die.getTag() == DW_TAG_compile_unit; + bool CheckContains = !IsCompileUnit || !RI.Ranges.empty(); + + const char *Error = "error: DIE has a child DIE whose address ranges are not " + "contained in its ranges:"; + if (CheckContains && RI.reportErrorIfNotContained(OS, DieRI, Error)) + HasErrors = true; + + // Check if this range overlaps with any previous sibling ranges and make an + // error if needed. + if (NOR.insertAndReportErrors(OS, DieRI)) + HasErrors = true; + return HasErrors; +} + +Optional DWARFVerifier::NonOverlappingRanges::GetOverlappingRangeInfo( + const DieRangeInfo &RI) const { + if (RangeSet.empty()) + return None; + auto Iter = RangeSet.lower_bound(RI); + // Since we are searching using lower_bound, Iter might the address range + // that follows RI, so we need to check it in case RI overlaps with the next + // range. + if (Iter != RangeSet.end() && Iter->intersects(RI)) + return Iter->Die; + // We also need to check the previous range to ensure it doesn't overlap with + // this range. + if (Iter != RangeSet.begin() && (--Iter)->intersects(RI)) + return Iter->Die; + return None; +} + +bool DWARFVerifier::NonOverlappingRanges::insertAndReportErrors( + raw_ostream &OS, const DieRangeInfo &RI) { + bool Error = false; + if (auto OverlappingDie = GetOverlappingRangeInfo(RI)) { + OS << "error: DIEs have overlapping address ranges:\n"; + OverlappingDie->dump(OS, 0); + RI.Die.dump(OS, 0); + OS << "\n"; + Error = true; + } + RangeSet.insert(RI); + return Error; +} + +void DWARFVerifier::verifyDie(const DWARFDie &Die, DieInfo &ParentDI) { + const auto Tag = Die.getTag(); + + DieInfo DI; + DI.RI.Die = Die; + switch (Tag) { + case DW_TAG_null: + return; + case DW_TAG_compile_unit: + // Set the Unit DIE info. + UnitDI.RI.Die = Die; + if (UnitDI.RI.extractRangesAndReportErrors(OS)) + ++NumDebugInfoErrors; + break; + case DW_TAG_subprogram: + // Add the subprogram to the unit DIE and make it is contained. + if (UnitDI.addContainedDieAndReportErrors(OS, DI.RI)) + ++NumDebugInfoErrors; + break; + case DW_TAG_lexical_block: + case DW_TAG_inlined_subroutine: { + if (ParentDI.addContainedDieAndReportErrors(OS, DI.RI)) + ++NumDebugInfoErrors; + } 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, DI); +} void DWARFVerifier::verifyDebugInfoAttribute(const DWARFDie &Die, DWARFAttribute &AttrValue) { const auto Attr = AttrValue.Attr; @@ -160,17 +375,9 @@ NumDebugInfoErrors = 0; OS << "Verifying .debug_info...\n"; 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); - } - } + DieInfo DI; + DWARFDie Die = CU->getUnitDIE(/* ExtractUnitDIEOnly = */ false); + verifyDie(Die, DI); } verifyDebugInfoReferences(); return NumDebugInfoErrors == 0; Index: unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp =================================================================== --- unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp +++ unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp @@ -18,6 +18,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/Object/ObjectFile.h" #include "llvm/ObjectYAML/DWARFEmitter.h" #include "llvm/ObjectYAML/DWARFYAML.h" @@ -2142,4 +2143,504 @@ "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: DIE has a child DIE whose address ranges " + "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 DIE whose address ranges " + "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 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); + DWARFContextInMemory DwarfContext(*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); + DWARFContextInMemory DwarfContext(*ErrOrSections, 8); + VerifyError(DwarfContext, "error: invalid range in DIE:"); +} + +TEST(DWARFDebugInfo, TestDwarfRangesContains) { + DWARFVerifier::DWARFRange 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 doesn't match + ASSERT_FALSE(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 just past in Range + ASSERT_FALSE(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 DWARFVerifier::DWARFRange &LHS, + const DWARFVerifier::DWARFRange &RHS) { + ASSERT_TRUE(LHS.intersects(RHS)); + ASSERT_TRUE(RHS.intersects(LHS)); +} +void AssertRangesDontIntersect(const DWARFVerifier::DWARFRange &LHS, + const DWARFVerifier::DWARFRange &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) { + DWARFVerifier::DWARFRange 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