Skip to content

Commit

Permalink
[dwarfdump] Add DWARF verifiers for address ranges
Browse files Browse the repository at this point in the history
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

llvm-svn: 313255
  • Loading branch information
JDevlieghere committed Sep 14, 2017
1 parent 28365b3 commit 5891060
Showing 5 changed files with 879 additions and 6 deletions.
30 changes: 30 additions & 0 deletions llvm/include/llvm/DebugInfo/DWARF/DWARFDebugRangeList.h
Original file line number Diff line number Diff line change
@@ -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<DWARFAddressRange>;

4 changes: 4 additions & 0 deletions llvm/include/llvm/DebugInfo/DWARF/DWARFDie.h
Original file line number Diff line number Diff line change
@@ -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<iterator,
std::forward_iterator_tag,
const DWARFDie> {
64 changes: 63 additions & 1 deletion llvm/include/llvm/DebugInfo/DWARF/DWARFVerifier.h
Original file line number Diff line number Diff line change
@@ -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 <cstdint>
#include <map>
@@ -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<DWARFAddressRange> Ranges;

/// Sorted DWARFAddressRangeInfo.
std::set<DieRangeInfo> Children;

DieRangeInfo() = default;
DieRangeInfo(DWARFDie Die) : Die(Die) {}

/// Used for unit testing.
DieRangeInfo(std::vector<DWARFAddressRange> Ranges)
: Ranges(std::move(Ranges)) {}

typedef std::vector<DWARFAddressRange>::const_iterator
address_range_iterator;
typedef std::set<DieRangeInfo>::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 {
auto Begin = Ranges.begin();
auto End = Ranges.end();
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 @@ class DWARFVerifier {
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
139 changes: 135 additions & 4 deletions llvm/lib/DebugInfo/DWARF/DWARFVerifier.cpp
Original file line number Diff line number Diff line change
@@ -24,6 +24,83 @@ using namespace llvm;
using namespace dwarf;
using namespace object;

DWARFVerifier::DieRangeInfo::address_range_iterator
DWARFVerifier::DieRangeInfo::insert(const DWARFAddressRange &R) {
auto Begin = Ranges.begin();
auto End = Ranges.end();
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.end();
}

DWARFVerifier::DieRangeInfo::die_range_info_iterator
DWARFVerifier::DieRangeInfo::insert(const DieRangeInfo &RI) {
auto End = Children.end();
auto Iter = Children.begin();
while (Iter != End) {
if (Iter->intersects(RI))
return Iter;
++Iter;
}
Children.insert(RI);
return Children.end();
}

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.
auto End = Ranges.end();
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;

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.end()) {
++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.end()) {
++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;
}

648 changes: 647 additions & 1 deletion llvm/unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

Large diffs are not rendered by default.

0 comments on commit 5891060

Please sign in to comment.