//===- DWARFVerifier.cpp --------------------------------------------------===// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// #include "llvm/DebugInfo/DWARF/DWARFVerifier.h" #include "llvm/ADT/SmallSet.h" #include "llvm/DebugInfo/DWARF/DWARFCompileUnit.h" #include "llvm/DebugInfo/DWARF/DWARFContext.h" #include "llvm/DebugInfo/DWARF/DWARFDebugLine.h" #include "llvm/DebugInfo/DWARF/DWARFDie.h" #include "llvm/DebugInfo/DWARF/DWARFExpression.h" #include "llvm/DebugInfo/DWARF/DWARFFormValue.h" #include "llvm/DebugInfo/DWARF/DWARFSection.h" #include "llvm/Support/DJB.h" #include "llvm/Support/FormatVariadic.h" #include "llvm/Support/WithColor.h" #include "llvm/Support/raw_ostream.h" #include <map> #include <set> #include <vector> 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(Iter == End) return false; 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) { uint32_t AbbrOffset, Length; uint8_t AddrSize = 0; uint16_t Version; bool Success = true; bool ValidLength = false; bool ValidVersion = false; bool ValidAddrSize = false; bool ValidType = true; bool ValidAbbrevOffset = true; uint32_t OffsetStart = *Offset; Length = DebugInfoData.getU32(Offset); if (Length == UINT32_MAX) { isUnitDWARF64 = true; OS << format( "Unit[%d] is in 64-bit DWARF format; cannot verify from this point.\n", UnitIndex); return false; } Version = DebugInfoData.getU16(Offset); if (Version >= 5) { UnitType = DebugInfoData.getU8(Offset); AddrSize = DebugInfoData.getU8(Offset); AbbrOffset = DebugInfoData.getU32(Offset); ValidType = dwarf::isUnitType(UnitType); } else { UnitType = 0; AbbrOffset = DebugInfoData.getU32(Offset); AddrSize = DebugInfoData.getU8(Offset); } if (!DCtx.getDebugAbbrev()->getAbbreviationDeclarationSet(AbbrOffset)) ValidAbbrevOffset = false; ValidLength = DebugInfoData.isValidOffset(OffsetStart + Length + 3); ValidVersion = DWARFContext::isSupportedVersion(Version); ValidAddrSize = AddrSize == 4 || AddrSize == 8; if (!ValidLength || !ValidVersion || !ValidAddrSize || !ValidAbbrevOffset || !ValidType) { Success = false; error() << format("Units[%d] - start offset: 0x%08x \n", UnitIndex, OffsetStart); if (!ValidLength) note() << "The length for this unit is too " "large for the .debug_info provided.\n"; if (!ValidVersion) note() << "The 16 bit unit header version is not valid.\n"; if (!ValidType) note() << "The unit type encoding is not valid.\n"; if (!ValidAbbrevOffset) note() << "The offset into the .debug_abbrev section is " "not valid.\n"; if (!ValidAddrSize) note() << "The address size is unsupported.\n"; } *Offset = OffsetStart + Length + 4; return Success; } bool DWARFVerifier::verifyUnitContents(DWARFUnit &Unit, uint8_t UnitType) { uint32_t NumUnitErrors = 0; unsigned NumDies = Unit.getNumDIEs(); for (unsigned I = 0; I < NumDies; ++I) { auto Die = Unit.getDIEAtIndex(I); if (Die.getTag() == DW_TAG_null) continue; for (auto AttrValue : Die.attributes()) { NumUnitErrors += verifyDebugInfoAttribute(Die, AttrValue); NumUnitErrors += verifyDebugInfoForm(Die, AttrValue); } } DWARFDie Die = Unit.getUnitDIE(/* ExtractUnitDIEOnly = */ false); if (!Die) { error() << "Compilation unit without DIE.\n"; NumUnitErrors++; return NumUnitErrors == 0; } if (!dwarf::isUnitType(Die.getTag())) { error() << "Compilation unit root DIE is not a unit DIE: " << dwarf::TagString(Die.getTag()) << ".\n"; NumUnitErrors++; } if (UnitType != 0 && !DWARFUnit::isMatchingUnitTypeAndTag(UnitType, Die.getTag())) { error() << "Compilation unit type (" << dwarf::UnitTypeString(UnitType) << ") and root DIE (" << dwarf::TagString(Die.getTag()) << ") do not match.\n"; NumUnitErrors++; } DieRangeInfo RI; NumUnitErrors += verifyDieRanges(Die, RI); return NumUnitErrors == 0; } unsigned DWARFVerifier::verifyAbbrevSection(const DWARFDebugAbbrev *Abbrev) { unsigned NumErrors = 0; if (Abbrev) { const DWARFAbbreviationDeclarationSet *AbbrDecls = Abbrev->getAbbreviationDeclarationSet(0); for (auto AbbrDecl : *AbbrDecls) { SmallDenseSet<uint16_t> AttributeSet; for (auto Attribute : AbbrDecl.attributes()) { auto Result = AttributeSet.insert(Attribute.Attr); if (!Result.second) { error() << "Abbreviation declaration contains multiple " << AttributeString(Attribute.Attr) << " attributes.\n"; AbbrDecl.dump(OS); ++NumErrors; } } } } return NumErrors; } bool DWARFVerifier::handleDebugAbbrev() { OS << "Verifying .debug_abbrev...\n"; const DWARFObject &DObj = DCtx.getDWARFObj(); bool noDebugAbbrev = DObj.getAbbrevSection().empty(); bool noDebugAbbrevDWO = DObj.getAbbrevDWOSection().empty(); if (noDebugAbbrev && noDebugAbbrevDWO) { return true; } unsigned NumErrors = 0; if (!noDebugAbbrev) NumErrors += verifyAbbrevSection(DCtx.getDebugAbbrev()); if (!noDebugAbbrevDWO) NumErrors += verifyAbbrevSection(DCtx.getDebugAbbrevDWO()); return NumErrors == 0; } bool DWARFVerifier::handleDebugInfo() { OS << "Verifying .debug_info Unit Header Chain...\n"; const DWARFObject &DObj = DCtx.getDWARFObj(); DWARFDataExtractor DebugInfoData(DObj, DObj.getInfoSection(), DCtx.isLittleEndian(), 0); uint32_t NumDebugInfoErrors = 0; uint32_t OffsetStart = 0, Offset = 0, UnitIdx = 0; uint8_t UnitType = 0; bool isUnitDWARF64 = false; bool isHeaderChainValid = true; bool hasDIE = DebugInfoData.isValidOffset(Offset); DWARFUnitSection<DWARFTypeUnit> TUSection{}; DWARFUnitSection<DWARFCompileUnit> CUSection{}; while (hasDIE) { OffsetStart = Offset; if (!verifyUnitHeader(DebugInfoData, &Offset, UnitIdx, UnitType, isUnitDWARF64)) { isHeaderChainValid = false; if (isUnitDWARF64) break; } else { DWARFUnitHeader Header; Header.extract(DCtx, DebugInfoData, &OffsetStart); std::unique_ptr<DWARFUnit> Unit; switch (UnitType) { case dwarf::DW_UT_type: case dwarf::DW_UT_split_type: { Unit.reset(new DWARFTypeUnit( DCtx, DObj.getInfoSection(), Header, DCtx.getDebugAbbrev(), &DObj.getRangeSection(), DObj.getStringSection(), DObj.getStringOffsetSection(), &DObj.getAppleObjCSection(), DObj.getLineSection(), DCtx.isLittleEndian(), false, TUSection)); break; } case dwarf::DW_UT_skeleton: case dwarf::DW_UT_split_compile: case dwarf::DW_UT_compile: case dwarf::DW_UT_partial: // UnitType = 0 means that we are // verifying a compile unit in DWARF v4. case 0: { Unit.reset(new DWARFCompileUnit( DCtx, DObj.getInfoSection(), Header, DCtx.getDebugAbbrev(), &DObj.getRangeSection(), DObj.getStringSection(), DObj.getStringOffsetSection(), &DObj.getAppleObjCSection(), DObj.getLineSection(), DCtx.isLittleEndian(), false, CUSection)); break; } default: { llvm_unreachable("Invalid UnitType."); } } if (!verifyUnitContents(*Unit, UnitType)) ++NumDebugInfoErrors; } hasDIE = DebugInfoData.isValidOffset(Offset); ++UnitIdx; } if (UnitIdx == 0 && !hasDIE) { warn() << ".debug_info is empty.\n"; isHeaderChainValid = true; } NumDebugInfoErrors += verifyDebugInfoReferences(); return (isHeaderChainValid && NumDebugInfoErrors == 0); } unsigned DWARFVerifier::verifyDieRanges(const DWARFDie &Die, DieRangeInfo &ParentRI) { unsigned NumErrors = 0; if (!Die.isValid()) return NumErrors; auto RangesOrError = Die.getAddressRanges(); if (!RangesOrError) { // FIXME: Report the error. ++NumErrors; llvm::consumeError(RangesOrError.takeError()); return NumErrors; } DWARFAddressRangesVector Ranges = RangesOrError.get(); // 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; error() << "Invalid address range " << Range << "\n"; continue; } // Verify that ranges don't intersect. const auto IntersectingRange = RI.insert(Range); if (IntersectingRange != RI.Ranges.end()) { ++NumErrors; error() << "DIE has overlapping address ranges: " << Range << " and " << *IntersectingRange << "\n"; break; } } // Verify that children don't intersect. const auto IntersectingChild = ParentRI.insert(RI); if (IntersectingChild != ParentRI.Children.end()) { ++NumErrors; 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; error() << "DIE address ranges are not contained in its parent's ranges:"; ParentRI.Die.dump(OS, 0); Die.dump(OS, 2); OS << "\n"; } // Recursively check children. for (DWARFDie Child : Die) NumErrors += verifyDieRanges(Child, RI); return NumErrors; } unsigned DWARFVerifier::verifyDebugInfoAttribute(const DWARFDie &Die, DWARFAttribute &AttrValue) { unsigned NumErrors = 0; auto ReportError = [&](const Twine &TitleMsg) { ++NumErrors; error() << TitleMsg << '\n'; Die.dump(OS, 0, DumpOpts); OS << "\n"; }; const DWARFObject &DObj = DCtx.getDWARFObj(); const auto Attr = AttrValue.Attr; 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 >= DObj.getRangeSection().Data.size()) ReportError("DW_AT_ranges offset is beyond .debug_ranges bounds:"); break; } ReportError("DIE has invalid DW_AT_ranges encoding:"); 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 >= DObj.getLineSection().Data.size()) ReportError("DW_AT_stmt_list offset is beyond .debug_line bounds: " + llvm::formatv("{0:x8}", *SectionOffset)); break; } ReportError("DIE has invalid DW_AT_stmt_list encoding:"); break; case DW_AT_location: { auto VerifyLocationExpr = [&](StringRef D) { DWARFUnit *U = Die.getDwarfUnit(); DataExtractor Data(D, DCtx.isLittleEndian(), 0); DWARFExpression Expression(Data, U->getVersion(), U->getAddressByteSize()); bool Error = llvm::any_of(Expression, [](DWARFExpression::Operation &Op) { return Op.isError(); }); if (Error) ReportError("DIE contains invalid DWARF expression:"); }; if (Optional<ArrayRef<uint8_t>> Expr = AttrValue.Value.getAsBlock()) { // Verify inlined location. VerifyLocationExpr(llvm::toStringRef(*Expr)); } else if (auto LocOffset = AttrValue.Value.getAsSectionOffset()) { // Verify location list. if (auto DebugLoc = DCtx.getDebugLoc()) if (auto LocList = DebugLoc->getLocationListAtOffset(*LocOffset)) for (const auto &Entry : LocList->Entries) VerifyLocationExpr({Entry.Loc.data(), Entry.Loc.size()}); } break; } default: break; } return NumErrors; } unsigned DWARFVerifier::verifyDebugInfoForm(const DWARFDie &Die, DWARFAttribute &AttrValue) { const DWARFObject &DObj = DCtx.getDWARFObj(); unsigned NumErrors = 0; const auto Form = AttrValue.Value.getForm(); 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<uint64_t> 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) { ++NumErrors; error() << FormEncodingString(Form) << " CU offset " << format("0x%08" PRIx64, CUOffset) << " is invalid (must be less than CU size of " << format("0x%08" PRIx32, CUSize) << "):\n"; Die.dump(OS, 0, DumpOpts); 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<uint64_t> RefVal = AttrValue.Value.getAsReference(); assert(RefVal); if (RefVal) { if (*RefVal >= DObj.getInfoSection().Data.size()) { ++NumErrors; error() << "DW_FORM_ref_addr offset beyond .debug_info " "bounds:\n"; Die.dump(OS, 0, DumpOpts); 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 >= DObj.getStringSection().size()) { ++NumErrors; error() << "DW_FORM_strp offset beyond .debug_str bounds:\n"; Die.dump(OS, 0, DumpOpts); OS << "\n"; } break; } default: break; } return NumErrors; } unsigned DWARFVerifier::verifyDebugInfoReferences() { // Take all references and make sure they point to an actual DIE by // getting the DIE by offset and emitting an error OS << "Verifying .debug_info references...\n"; unsigned NumErrors = 0; for (auto Pair : ReferenceToDIEOffsets) { auto Die = DCtx.getDIEForOffset(Pair.first); if (Die) continue; ++NumErrors; 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, DumpOpts); OS << "\n"; } OS << "\n"; } return NumErrors; } void DWARFVerifier::verifyDebugLineStmtOffsets() { std::map<uint64_t, DWARFDie> StmtListToDie; for (const auto &CU : DCtx.compile_units()) { auto Die = CU->getUnitDIE(); // 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. auto StmtSectionOffset = toSectionOffset(Die.find(DW_AT_stmt_list)); if (!StmtSectionOffset) continue; const uint32_t LineTableOffset = *StmtSectionOffset; auto LineTable = DCtx.getLineTableForUnit(CU.get()); if (LineTableOffset < DCtx.getDWARFObj().getLineSection().Data.size()) { if (!LineTable) { ++NumDebugLineErrors; error() << ".debug_line[" << format("0x%08" PRIx32, LineTableOffset) << "] was not able to be parsed for CU:\n"; Die.dump(OS, 0, DumpOpts); OS << '\n'; continue; } } else { // Make sure we don't get a valid line table back if the offset is wrong. assert(LineTable == 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; } auto Iter = StmtListToDie.find(LineTableOffset); if (Iter != StmtListToDie.end()) { ++NumDebugLineErrors; error() << "two compile unit DIEs, " << format("0x%08" PRIx32, Iter->second.getOffset()) << " and " << format("0x%08" PRIx32, Die.getOffset()) << ", have the same DW_AT_stmt_list section offset:\n"; Iter->second.dump(OS, 0, DumpOpts); Die.dump(OS, 0, DumpOpts); OS << '\n'; // Already verified this line table before, no need to do it again. continue; } StmtListToDie[LineTableOffset] = Die; } } void DWARFVerifier::verifyDebugLineRows() { for (const auto &CU : DCtx.compile_units()) { auto Die = CU->getUnitDIE(); auto LineTable = DCtx.getLineTableForUnit(CU.get()); // If there is no line table we will have created an error in the // .debug_info verifier or in verifyDebugLineStmtOffsets(). if (!LineTable) continue; // Verify prologue. uint32_t MaxFileIndex = LineTable->Prologue.FileNames.size(); uint32_t MaxDirIndex = LineTable->Prologue.IncludeDirectories.size(); uint32_t FileIndex = 1; StringMap<uint16_t> FullPathMap; for (const auto &FileName : LineTable->Prologue.FileNames) { // Verify directory index. if (FileName.DirIdx > MaxDirIndex) { ++NumDebugLineErrors; error() << ".debug_line[" << format("0x%08" PRIx64, *toSectionOffset(Die.find(DW_AT_stmt_list))) << "].prologue.file_names[" << FileIndex << "].dir_idx contains an invalid index: " << FileName.DirIdx << "\n"; } // Check file paths for duplicates. std::string FullPath; const bool HasFullPath = LineTable->getFileNameByIndex( FileIndex, CU->getCompilationDir(), DILineInfoSpecifier::FileLineInfoKind::AbsoluteFilePath, FullPath); assert(HasFullPath && "Invalid index?"); (void)HasFullPath; auto It = FullPathMap.find(FullPath); if (It == FullPathMap.end()) FullPathMap[FullPath] = FileIndex; else if (It->second != FileIndex) { warn() << ".debug_line[" << format("0x%08" PRIx64, *toSectionOffset(Die.find(DW_AT_stmt_list))) << "].prologue.file_names[" << FileIndex << "] is a duplicate of file_names[" << It->second << "]\n"; } FileIndex++; } // Verify rows. uint64_t PrevAddress = 0; uint32_t RowIndex = 0; for (const auto &Row : LineTable->Rows) { // Verify row address. if (Row.Address < PrevAddress) { ++NumDebugLineErrors; error() << ".debug_line[" << format("0x%08" PRIx64, *toSectionOffset(Die.find(DW_AT_stmt_list))) << "] 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'; } // Verify file index. if (Row.File > MaxFileIndex) { ++NumDebugLineErrors; error() << ".debug_line[" << format("0x%08" PRIx64, *toSectionOffset(Die.find(DW_AT_stmt_list))) << "][" << 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; } } } bool DWARFVerifier::handleDebugLine() { NumDebugLineErrors = 0; OS << "Verifying .debug_line...\n"; verifyDebugLineStmtOffsets(); verifyDebugLineRows(); return NumDebugLineErrors == 0; } unsigned DWARFVerifier::verifyAppleAccelTable(const DWARFSection *AccelSection, DataExtractor *StrData, const char *SectionName) { unsigned NumErrors = 0; DWARFDataExtractor AccelSectionData(DCtx.getDWARFObj(), *AccelSection, DCtx.isLittleEndian(), 0); AppleAcceleratorTable AccelTable(AccelSectionData, *StrData); OS << "Verifying " << SectionName << "...\n"; // Verify that the fixed part of the header is not too short. if (!AccelSectionData.isValidOffset(AccelTable.getSizeHdr())) { error() << "Section is too small to fit a section header.\n"; return 1; } // Verify that the section is not too short. if (Error E = AccelTable.extract()) { error() << toString(std::move(E)) << '\n'; return 1; } // Verify that all buckets have a valid hash index or are empty. uint32_t NumBuckets = AccelTable.getNumBuckets(); uint32_t NumHashes = AccelTable.getNumHashes(); uint32_t BucketsOffset = AccelTable.getSizeHdr() + AccelTable.getHeaderDataLength(); uint32_t HashesBase = BucketsOffset + NumBuckets * 4; uint32_t OffsetsBase = HashesBase + NumHashes * 4; for (uint32_t BucketIdx = 0; BucketIdx < NumBuckets; ++BucketIdx) { uint32_t HashIdx = AccelSectionData.getU32(&BucketsOffset); if (HashIdx >= NumHashes && HashIdx != UINT32_MAX) { error() << format("Bucket[%d] has invalid hash index: %u.\n", BucketIdx, HashIdx); ++NumErrors; } } uint32_t NumAtoms = AccelTable.getAtomsDesc().size(); if (NumAtoms == 0) { error() << "No atoms: failed to read HashData.\n"; return 1; } if (!AccelTable.validateForms()) { error() << "Unsupported form: failed to read HashData.\n"; return 1; } for (uint32_t HashIdx = 0; HashIdx < NumHashes; ++HashIdx) { uint32_t HashOffset = HashesBase + 4 * HashIdx; uint32_t DataOffset = OffsetsBase + 4 * HashIdx; uint32_t Hash = AccelSectionData.getU32(&HashOffset); uint32_t HashDataOffset = AccelSectionData.getU32(&DataOffset); if (!AccelSectionData.isValidOffsetForDataOfSize(HashDataOffset, sizeof(uint64_t))) { error() << format("Hash[%d] has invalid HashData offset: 0x%08x.\n", HashIdx, HashDataOffset); ++NumErrors; } uint32_t StrpOffset; uint32_t StringOffset; uint32_t StringCount = 0; unsigned Offset; unsigned Tag; while ((StrpOffset = AccelSectionData.getU32(&HashDataOffset)) != 0) { const uint32_t NumHashDataObjects = AccelSectionData.getU32(&HashDataOffset); for (uint32_t HashDataIdx = 0; HashDataIdx < NumHashDataObjects; ++HashDataIdx) { std::tie(Offset, Tag) = AccelTable.readAtoms(HashDataOffset); auto Die = DCtx.getDIEForOffset(Offset); if (!Die) { const uint32_t BucketIdx = NumBuckets ? (Hash % NumBuckets) : UINT32_MAX; StringOffset = StrpOffset; const char *Name = StrData->getCStr(&StringOffset); if (!Name) Name = "<NULL>"; error() << format( "%s Bucket[%d] Hash[%d] = 0x%08x " "Str[%u] = 0x%08x " "DIE[%d] = 0x%08x is not a valid DIE offset for \"%s\".\n", SectionName, BucketIdx, HashIdx, Hash, StringCount, StrpOffset, HashDataIdx, Offset, Name); ++NumErrors; continue; } if ((Tag != dwarf::DW_TAG_null) && (Die.getTag() != Tag)) { error() << "Tag " << dwarf::TagString(Tag) << " in accelerator table does not match Tag " << dwarf::TagString(Die.getTag()) << " of DIE[" << HashDataIdx << "].\n"; ++NumErrors; } } ++StringCount; } } return NumErrors; } unsigned DWARFVerifier::verifyDebugNamesCULists(const DWARFDebugNames &AccelTable) { // A map from CU offset to the (first) Name Index offset which claims to index // this CU. DenseMap<uint32_t, uint32_t> CUMap; const uint32_t NotIndexed = std::numeric_limits<uint32_t>::max(); CUMap.reserve(DCtx.getNumCompileUnits()); for (const auto &CU : DCtx.compile_units()) CUMap[CU->getOffset()] = NotIndexed; unsigned NumErrors = 0; for (const DWARFDebugNames::NameIndex &NI : AccelTable) { if (NI.getCUCount() == 0) { error() << formatv("Name Index @ {0:x} does not index any CU\n", NI.getUnitOffset()); ++NumErrors; continue; } for (uint32_t CU = 0, End = NI.getCUCount(); CU < End; ++CU) { uint32_t Offset = NI.getCUOffset(CU); auto Iter = CUMap.find(Offset); if (Iter == CUMap.end()) { error() << formatv( "Name Index @ {0:x} references a non-existing CU @ {1:x}\n", NI.getUnitOffset(), Offset); ++NumErrors; continue; } if (Iter->second != NotIndexed) { error() << formatv("Name Index @ {0:x} references a CU @ {1:x}, but " "this CU is already indexed by Name Index @ {2:x}\n", NI.getUnitOffset(), Offset, Iter->second); continue; } Iter->second = NI.getUnitOffset(); } } for (const auto &KV : CUMap) { if (KV.second == NotIndexed) warn() << formatv("CU @ {0:x} not covered by any Name Index\n", KV.first); } return NumErrors; } unsigned DWARFVerifier::verifyNameIndexBuckets(const DWARFDebugNames::NameIndex &NI, const DataExtractor &StrData) { struct BucketInfo { uint32_t Bucket; uint32_t Index; constexpr BucketInfo(uint32_t Bucket, uint32_t Index) : Bucket(Bucket), Index(Index) {} bool operator<(const BucketInfo &RHS) const { return Index < RHS.Index; }; }; uint32_t NumErrors = 0; if (NI.getBucketCount() == 0) { warn() << formatv("Name Index @ {0:x} does not contain a hash table.\n", NI.getUnitOffset()); return NumErrors; } // Build up a list of (Bucket, Index) pairs. We use this later to verify that // each Name is reachable from the appropriate bucket. std::vector<BucketInfo> BucketStarts; BucketStarts.reserve(NI.getBucketCount() + 1); for (uint32_t Bucket = 0, End = NI.getBucketCount(); Bucket < End; ++Bucket) { uint32_t Index = NI.getBucketArrayEntry(Bucket); if (Index > NI.getNameCount()) { error() << formatv("Bucket {0} of Name Index @ {1:x} contains invalid " "value {2}. Valid range is [0, {3}].\n", Bucket, NI.getUnitOffset(), Index, NI.getNameCount()); ++NumErrors; continue; } if (Index > 0) BucketStarts.emplace_back(Bucket, Index); } // If there were any buckets with invalid values, skip further checks as they // will likely produce many errors which will only confuse the actual root // problem. if (NumErrors > 0) return NumErrors; // Sort the list in the order of increasing "Index" entries. array_pod_sort(BucketStarts.begin(), BucketStarts.end()); // Insert a sentinel entry at the end, so we can check that the end of the // table is covered in the loop below. BucketStarts.emplace_back(NI.getBucketCount(), NI.getNameCount() + 1); // Loop invariant: NextUncovered is the (1-based) index of the first Name // which is not reachable by any of the buckets we processed so far (and // hasn't been reported as uncovered). uint32_t NextUncovered = 1; for (const BucketInfo &B : BucketStarts) { // Under normal circumstances B.Index be equal to NextUncovered, but it can // be less if a bucket points to names which are already known to be in some // bucket we processed earlier. In that case, we won't trigger this error, // but report the mismatched hash value error instead. (We know the hash // will not match because we have already verified that the name's hash // puts it into the previous bucket.) if (B.Index > NextUncovered) { error() << formatv("Name Index @ {0:x}: Name table entries [{1}, {2}] " "are not covered by the hash table.\n", NI.getUnitOffset(), NextUncovered, B.Index - 1); ++NumErrors; } uint32_t Idx = B.Index; // The rest of the checks apply only to non-sentinel entries. if (B.Bucket == NI.getBucketCount()) break; // This triggers if a non-empty bucket points to a name with a mismatched // hash. Clients are likely to interpret this as an empty bucket, because a // mismatched hash signals the end of a bucket, but if this is indeed an // empty bucket, the producer should have signalled this by marking the // bucket as empty. uint32_t FirstHash = NI.getHashArrayEntry(Idx); if (FirstHash % NI.getBucketCount() != B.Bucket) { error() << formatv( "Name Index @ {0:x}: Bucket {1} is not empty but points to a " "mismatched hash value {2:x} (belonging to bucket {3}).\n", NI.getUnitOffset(), B.Bucket, FirstHash, FirstHash % NI.getBucketCount()); ++NumErrors; } // This find the end of this bucket and also verifies that all the hashes in // this bucket are correct by comparing the stored hashes to the ones we // compute ourselves. while (Idx <= NI.getNameCount()) { uint32_t Hash = NI.getHashArrayEntry(Idx); if (Hash % NI.getBucketCount() != B.Bucket) break; const char *Str = NI.getNameTableEntry(Idx).getString(); if (caseFoldingDjbHash(Str) != Hash) { error() << formatv("Name Index @ {0:x}: String ({1}) at index {2} " "hashes to {3:x}, but " "the Name Index hash is {4:x}\n", NI.getUnitOffset(), Str, Idx, caseFoldingDjbHash(Str), Hash); ++NumErrors; } ++Idx; } NextUncovered = std::max(NextUncovered, Idx); } return NumErrors; } unsigned DWARFVerifier::verifyNameIndexAttribute( const DWARFDebugNames::NameIndex &NI, const DWARFDebugNames::Abbrev &Abbr, DWARFDebugNames::AttributeEncoding AttrEnc) { StringRef FormName = dwarf::FormEncodingString(AttrEnc.Form); if (FormName.empty()) { error() << formatv("NameIndex @ {0:x}: Abbreviation {1:x}: {2} uses an " "unknown form: {3}.\n", NI.getUnitOffset(), Abbr.Code, AttrEnc.Index, AttrEnc.Form); return 1; } if (AttrEnc.Index == DW_IDX_type_hash) { if (AttrEnc.Form != dwarf::DW_FORM_data8) { error() << formatv( "NameIndex @ {0:x}: Abbreviation {1:x}: DW_IDX_type_hash " "uses an unexpected form {2} (should be {3}).\n", NI.getUnitOffset(), Abbr.Code, AttrEnc.Form, dwarf::DW_FORM_data8); return 1; } } // A list of known index attributes and their expected form classes. // DW_IDX_type_hash is handled specially in the check above, as it has a // specific form (not just a form class) we should expect. struct FormClassTable { dwarf::Index Index; DWARFFormValue::FormClass Class; StringLiteral ClassName; }; static constexpr FormClassTable Table[] = { {dwarf::DW_IDX_compile_unit, DWARFFormValue::FC_Constant, {"constant"}}, {dwarf::DW_IDX_type_unit, DWARFFormValue::FC_Constant, {"constant"}}, {dwarf::DW_IDX_die_offset, DWARFFormValue::FC_Reference, {"reference"}}, {dwarf::DW_IDX_parent, DWARFFormValue::FC_Constant, {"constant"}}, }; ArrayRef<FormClassTable> TableRef(Table); auto Iter = find_if(TableRef, [AttrEnc](const FormClassTable &T) { return T.Index == AttrEnc.Index; }); if (Iter == TableRef.end()) { warn() << formatv("NameIndex @ {0:x}: Abbreviation {1:x} contains an " "unknown index attribute: {2}.\n", NI.getUnitOffset(), Abbr.Code, AttrEnc.Index); return 0; } if (!DWARFFormValue(AttrEnc.Form).isFormClass(Iter->Class)) { error() << formatv("NameIndex @ {0:x}: Abbreviation {1:x}: {2} uses an " "unexpected form {3} (expected form class {4}).\n", NI.getUnitOffset(), Abbr.Code, AttrEnc.Index, AttrEnc.Form, Iter->ClassName); return 1; } return 0; } unsigned DWARFVerifier::verifyNameIndexAbbrevs(const DWARFDebugNames::NameIndex &NI) { if (NI.getLocalTUCount() + NI.getForeignTUCount() > 0) { warn() << formatv("Name Index @ {0:x}: Verifying indexes of type units is " "not currently supported.\n", NI.getUnitOffset()); return 0; } unsigned NumErrors = 0; for (const auto &Abbrev : NI.getAbbrevs()) { StringRef TagName = dwarf::TagString(Abbrev.Tag); if (TagName.empty()) { warn() << formatv("NameIndex @ {0:x}: Abbreviation {1:x} references an " "unknown tag: {2}.\n", NI.getUnitOffset(), Abbrev.Code, Abbrev.Tag); } SmallSet<unsigned, 5> Attributes; for (const auto &AttrEnc : Abbrev.Attributes) { if (!Attributes.insert(AttrEnc.Index).second) { error() << formatv("NameIndex @ {0:x}: Abbreviation {1:x} contains " "multiple {2} attributes.\n", NI.getUnitOffset(), Abbrev.Code, AttrEnc.Index); ++NumErrors; continue; } NumErrors += verifyNameIndexAttribute(NI, Abbrev, AttrEnc); } if (NI.getCUCount() > 1 && !Attributes.count(dwarf::DW_IDX_compile_unit)) { error() << formatv("NameIndex @ {0:x}: Indexing multiple compile units " "and abbreviation {1:x} has no {2} attribute.\n", NI.getUnitOffset(), Abbrev.Code, dwarf::DW_IDX_compile_unit); ++NumErrors; } if (!Attributes.count(dwarf::DW_IDX_die_offset)) { error() << formatv( "NameIndex @ {0:x}: Abbreviation {1:x} has no {2} attribute.\n", NI.getUnitOffset(), Abbrev.Code, dwarf::DW_IDX_die_offset); ++NumErrors; } } return NumErrors; } static SmallVector<StringRef, 2> getNames(const DWARFDie &DIE) { SmallVector<StringRef, 2> Result; if (const char *Str = DIE.getName(DINameKind::ShortName)) Result.emplace_back(Str); else if (DIE.getTag() == dwarf::DW_TAG_namespace) Result.emplace_back("(anonymous namespace)"); if (const char *Str = DIE.getName(DINameKind::LinkageName)) { if (Result.empty() || Result[0] != Str) Result.emplace_back(Str); } return Result; } unsigned DWARFVerifier::verifyNameIndexEntries( const DWARFDebugNames::NameIndex &NI, const DWARFDebugNames::NameTableEntry &NTE) { // Verifying type unit indexes not supported. if (NI.getLocalTUCount() + NI.getForeignTUCount() > 0) return 0; const char *CStr = NTE.getString(); if (!CStr) { error() << formatv( "Name Index @ {0:x}: Unable to get string associated with name {1}.\n", NI.getUnitOffset(), NTE.getIndex()); return 1; } StringRef Str(CStr); unsigned NumErrors = 0; unsigned NumEntries = 0; uint32_t EntryID = NTE.getEntryOffset(); uint32_t NextEntryID = EntryID; Expected<DWARFDebugNames::Entry> EntryOr = NI.getEntry(&NextEntryID); for (; EntryOr; ++NumEntries, EntryID = NextEntryID, EntryOr = NI.getEntry(&NextEntryID)) { uint32_t CUIndex = *EntryOr->getCUIndex(); if (CUIndex > NI.getCUCount()) { error() << formatv("Name Index @ {0:x}: Entry @ {1:x} contains an " "invalid CU index ({2}).\n", NI.getUnitOffset(), EntryID, CUIndex); ++NumErrors; continue; } uint32_t CUOffset = NI.getCUOffset(CUIndex); uint64_t DIEOffset = CUOffset + *EntryOr->getDIEUnitOffset(); DWARFDie DIE = DCtx.getDIEForOffset(DIEOffset); if (!DIE) { error() << formatv("Name Index @ {0:x}: Entry @ {1:x} references a " "non-existing DIE @ {2:x}.\n", NI.getUnitOffset(), EntryID, DIEOffset); ++NumErrors; continue; } if (DIE.getDwarfUnit()->getOffset() != CUOffset) { error() << formatv("Name Index @ {0:x}: Entry @ {1:x}: mismatched CU of " "DIE @ {2:x}: index - {3:x}; debug_info - {4:x}.\n", NI.getUnitOffset(), EntryID, DIEOffset, CUOffset, DIE.getDwarfUnit()->getOffset()); ++NumErrors; } if (DIE.getTag() != EntryOr->tag()) { error() << formatv("Name Index @ {0:x}: Entry @ {1:x}: mismatched Tag of " "DIE @ {2:x}: index - {3}; debug_info - {4}.\n", NI.getUnitOffset(), EntryID, DIEOffset, EntryOr->tag(), DIE.getTag()); ++NumErrors; } auto EntryNames = getNames(DIE); if (!is_contained(EntryNames, Str)) { error() << formatv("Name Index @ {0:x}: Entry @ {1:x}: mismatched Name " "of DIE @ {2:x}: index - {3}; debug_info - {4}.\n", NI.getUnitOffset(), EntryID, DIEOffset, Str, make_range(EntryNames.begin(), EntryNames.end())); ++NumErrors; } } handleAllErrors(EntryOr.takeError(), [&](const DWARFDebugNames::SentinelError &) { if (NumEntries > 0) return; error() << formatv("Name Index @ {0:x}: Name {1} ({2}) is " "not associated with any entries.\n", NI.getUnitOffset(), NTE.getIndex(), Str); ++NumErrors; }, [&](const ErrorInfoBase &Info) { error() << formatv("Name Index @ {0:x}: Name {1} ({2}): {3}\n", NI.getUnitOffset(), NTE.getIndex(), Str, Info.message()); ++NumErrors; }); return NumErrors; } static bool isVariableIndexable(const DWARFDie &Die, DWARFContext &DCtx) { Optional<DWARFFormValue> Location = Die.findRecursively(DW_AT_location); if (!Location) return false; auto ContainsInterestingOperators = [&](StringRef D) { DWARFUnit *U = Die.getDwarfUnit(); DataExtractor Data(D, DCtx.isLittleEndian(), U->getAddressByteSize()); DWARFExpression Expression(Data, U->getVersion(), U->getAddressByteSize()); return any_of(Expression, [](DWARFExpression::Operation &Op) { return !Op.isError() && (Op.getCode() == DW_OP_addr || Op.getCode() == DW_OP_form_tls_address || Op.getCode() == DW_OP_GNU_push_tls_address); }); }; if (Optional<ArrayRef<uint8_t>> Expr = Location->getAsBlock()) { // Inlined location. if (ContainsInterestingOperators(toStringRef(*Expr))) return true; } else if (Optional<uint64_t> Offset = Location->getAsSectionOffset()) { // Location list. if (const DWARFDebugLoc *DebugLoc = DCtx.getDebugLoc()) { if (const DWARFDebugLoc::LocationList *LocList = DebugLoc->getLocationListAtOffset(*Offset)) { if (any_of(LocList->Entries, [&](const DWARFDebugLoc::Entry &E) { return ContainsInterestingOperators({E.Loc.data(), E.Loc.size()}); })) return true; } } } return false; } unsigned DWARFVerifier::verifyNameIndexCompleteness( const DWARFDie &Die, const DWARFDebugNames::NameIndex &NI) { // First check, if the Die should be indexed. The code follows the DWARF v5 // wording as closely as possible. // "All non-defining declarations (that is, debugging information entries // with a DW_AT_declaration attribute) are excluded." if (Die.find(DW_AT_declaration)) return 0; // "DW_TAG_namespace debugging information entries without a DW_AT_name // attribute are included with the name “(anonymous namespace)”. // All other debugging information entries without a DW_AT_name attribute // are excluded." // "If a subprogram or inlined subroutine is included, and has a // DW_AT_linkage_name attribute, there will be an additional index entry for // the linkage name." auto EntryNames = getNames(Die); if (EntryNames.empty()) return 0; // We deviate from the specification here, which says: // "The name index must contain an entry for each debugging information entry // that defines a named subprogram, label, variable, type, or namespace, // subject to ..." // Instead whitelisting all TAGs representing a "type" or a "subprogram", to // make sure we catch any missing items, we instead blacklist all TAGs that we // know shouldn't be indexed. switch (Die.getTag()) { // Compile unit has a name but it shouldn't be indexed. case DW_TAG_compile_unit: return 0; // Function and template parameters are not globally visible, so we shouldn't // index them. case DW_TAG_formal_parameter: case DW_TAG_template_value_parameter: case DW_TAG_template_type_parameter: case DW_TAG_GNU_template_parameter_pack: case DW_TAG_GNU_template_template_param: return 0; // Object members aren't globally visible. case DW_TAG_member: return 0; // According to a strict reading of the specification, enumerators should not // be indexed (and LLVM currently does not do that). However, this causes // problems for the debuggers, so we may need to reconsider this. case DW_TAG_enumerator: return 0; // Imported declarations should not be indexed according to the specification // and LLVM currently does not do that. case DW_TAG_imported_declaration: return 0; // "DW_TAG_subprogram, DW_TAG_inlined_subroutine, and DW_TAG_label debugging // information entries without an address attribute (DW_AT_low_pc, // DW_AT_high_pc, DW_AT_ranges, or DW_AT_entry_pc) are excluded." case DW_TAG_subprogram: case DW_TAG_inlined_subroutine: case DW_TAG_label: if (Die.findRecursively( {DW_AT_low_pc, DW_AT_high_pc, DW_AT_ranges, DW_AT_entry_pc})) break; return 0; // "DW_TAG_variable debugging information entries with a DW_AT_location // attribute that includes a DW_OP_addr or DW_OP_form_tls_address operator are // included; otherwise, they are excluded." // // LLVM extension: We also add DW_OP_GNU_push_tls_address to this list. case DW_TAG_variable: if (isVariableIndexable(Die, DCtx)) break; return 0; default: break; } // Now we know that our Die should be present in the Index. Let's check if // that's the case. unsigned NumErrors = 0; uint64_t DieUnitOffset = Die.getOffset() - Die.getDwarfUnit()->getOffset(); for (StringRef Name : EntryNames) { if (none_of(NI.equal_range(Name), [&](const DWARFDebugNames::Entry &E) { return E.getDIEUnitOffset() == DieUnitOffset; })) { error() << formatv("Name Index @ {0:x}: Entry for DIE @ {1:x} ({2}) with " "name {3} missing.\n", NI.getUnitOffset(), Die.getOffset(), Die.getTag(), Name); ++NumErrors; } } return NumErrors; } unsigned DWARFVerifier::verifyDebugNames(const DWARFSection &AccelSection, const DataExtractor &StrData) { unsigned NumErrors = 0; DWARFDataExtractor AccelSectionData(DCtx.getDWARFObj(), AccelSection, DCtx.isLittleEndian(), 0); DWARFDebugNames AccelTable(AccelSectionData, StrData); OS << "Verifying .debug_names...\n"; // This verifies that we can read individual name indices and their // abbreviation tables. if (Error E = AccelTable.extract()) { error() << toString(std::move(E)) << '\n'; return 1; } NumErrors += verifyDebugNamesCULists(AccelTable); for (const auto &NI : AccelTable) NumErrors += verifyNameIndexBuckets(NI, StrData); for (const auto &NI : AccelTable) NumErrors += verifyNameIndexAbbrevs(NI); // Don't attempt Entry validation if any of the previous checks found errors if (NumErrors > 0) return NumErrors; for (const auto &NI : AccelTable) for (DWARFDebugNames::NameTableEntry NTE : NI) NumErrors += verifyNameIndexEntries(NI, NTE); if (NumErrors > 0) return NumErrors; for (const std::unique_ptr<DWARFCompileUnit> &CU : DCtx.compile_units()) { if (const DWARFDebugNames::NameIndex *NI = AccelTable.getCUNameIndex(CU->getOffset())) { for (const DWARFDebugInfoEntry &Die : CU->dies()) NumErrors += verifyNameIndexCompleteness(DWARFDie(CU.get(), &Die), *NI); } } return NumErrors; } bool DWARFVerifier::handleAccelTables() { const DWARFObject &D = DCtx.getDWARFObj(); DataExtractor StrData(D.getStringSection(), DCtx.isLittleEndian(), 0); unsigned NumErrors = 0; if (!D.getAppleNamesSection().Data.empty()) NumErrors += verifyAppleAccelTable(&D.getAppleNamesSection(), &StrData, ".apple_names"); if (!D.getAppleTypesSection().Data.empty()) NumErrors += verifyAppleAccelTable(&D.getAppleTypesSection(), &StrData, ".apple_types"); if (!D.getAppleNamespacesSection().Data.empty()) NumErrors += verifyAppleAccelTable(&D.getAppleNamespacesSection(), &StrData, ".apple_namespaces"); if (!D.getAppleObjCSection().Data.empty()) NumErrors += verifyAppleAccelTable(&D.getAppleObjCSection(), &StrData, ".apple_objc"); if (!D.getDebugNamesSection().Data.empty()) NumErrors += verifyDebugNames(D.getDebugNamesSection(), StrData); return NumErrors == 0; } raw_ostream &DWARFVerifier::error() const { return WithColor::error(OS); } raw_ostream &DWARFVerifier::warn() const { return WithColor::warning(OS); } raw_ostream &DWARFVerifier::note() const { return WithColor::note(OS); }