LCOV - code coverage report
Current view: top level - lib/DebugInfo/DWARF - DWARFVerifier.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 637 670 95.1 %
Date: 2018-06-17 00:07:59 Functions: 35 35 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- DWARFVerifier.cpp --------------------------------------------------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : 
      10             : #include "llvm/DebugInfo/DWARF/DWARFVerifier.h"
      11             : #include "llvm/ADT/SmallSet.h"
      12             : #include "llvm/DebugInfo/DWARF/DWARFCompileUnit.h"
      13             : #include "llvm/DebugInfo/DWARF/DWARFContext.h"
      14             : #include "llvm/DebugInfo/DWARF/DWARFDebugLine.h"
      15             : #include "llvm/DebugInfo/DWARF/DWARFDie.h"
      16             : #include "llvm/DebugInfo/DWARF/DWARFExpression.h"
      17             : #include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
      18             : #include "llvm/DebugInfo/DWARF/DWARFSection.h"
      19             : #include "llvm/Support/DJB.h"
      20             : #include "llvm/Support/FormatVariadic.h"
      21             : #include "llvm/Support/WithColor.h"
      22             : #include "llvm/Support/raw_ostream.h"
      23             : #include <map>
      24             : #include <set>
      25             : #include <vector>
      26             : 
      27             : using namespace llvm;
      28             : using namespace dwarf;
      29             : using namespace object;
      30             : 
      31             : DWARFVerifier::DieRangeInfo::address_range_iterator
      32         101 : DWARFVerifier::DieRangeInfo::insert(const DWARFAddressRange &R) {
      33             :   auto Begin = Ranges.begin();
      34             :   auto End = Ranges.end();
      35             :   auto Pos = std::lower_bound(Begin, End, R);
      36             : 
      37         101 :   if (Pos != End) {
      38           0 :     if (Pos->intersects(R))
      39           0 :       return Pos;
      40           0 :     if (Pos != Begin) {
      41             :       auto Iter = Pos - 1;
      42           0 :       if (Iter->intersects(R))
      43           0 :         return Iter;
      44             :     }
      45             :   }
      46             : 
      47         202 :   Ranges.insert(Pos, R);
      48         101 :   return Ranges.end();
      49             : }
      50             : 
      51             : DWARFVerifier::DieRangeInfo::die_range_info_iterator
      52         401 : DWARFVerifier::DieRangeInfo::insert(const DieRangeInfo &RI) {
      53             :   auto End = Children.end();
      54             :   auto Iter = Children.begin();
      55        1555 :   while (Iter != End) {
      56        1156 :     if (Iter->intersects(RI))
      57           2 :       return Iter;
      58             :     ++Iter;
      59             :   }
      60             :   Children.insert(RI);
      61             :   return Children.end();
      62             : }
      63             : 
      64          62 : bool DWARFVerifier::DieRangeInfo::contains(const DieRangeInfo &RHS) const {
      65             :   // Both list of ranges are sorted so we can make this fast.
      66             : 
      67         124 :   if (Ranges.empty() || RHS.Ranges.empty())
      68             :     return false;
      69             : 
      70             :   // Since the ranges are sorted we can advance where we start searching with
      71             :   // this object's ranges as we traverse RHS.Ranges.
      72             :   auto End = Ranges.end();
      73          62 :   auto Iter = findRange(RHS.Ranges.front());
      74             : 
      75             :   // Now linearly walk the ranges in this object and see if they contain each
      76             :   // ranges from RHS.Ranges.
      77          62 :   for (const auto &R : RHS.Ranges) {
      78          90 :     while (Iter != End) {
      79          83 :       if (Iter->contains(R))
      80             :         break;
      81             :       ++Iter;
      82             :     }
      83          76 :     if (Iter == End)
      84             :       return false;
      85             :   }
      86             :   return true;
      87             : }
      88             : 
      89        1188 : bool DWARFVerifier::DieRangeInfo::intersects(const DieRangeInfo &RHS) const {
      90        1579 :   if (Ranges.empty() || RHS.Ranges.empty())
      91             :     return false;
      92             : 
      93             :   auto End = Ranges.end();
      94         254 :   auto Iter = findRange(RHS.Ranges.front());
      95         254 :   for (const auto &R : RHS.Ranges) {
      96         265 :     if(Iter == End)
      97             :       return false;
      98         264 :     if (R.HighPC <= Iter->LowPC)
      99          13 :       continue;
     100         488 :     while (Iter != End) {
     101         257 :       if (Iter->intersects(R))
     102             :         return true;
     103             :       ++Iter;
     104             :     }
     105             :   }
     106             : 
     107             :   return false;
     108             : }
     109             : 
     110          79 : bool DWARFVerifier::verifyUnitHeader(const DWARFDataExtractor DebugInfoData,
     111             :                                      uint32_t *Offset, unsigned UnitIndex,
     112             :                                      uint8_t &UnitType, bool &isUnitDWARF64) {
     113             :   uint32_t AbbrOffset, Length;
     114             :   uint8_t AddrSize = 0;
     115             :   uint16_t Version;
     116             :   bool Success = true;
     117             : 
     118             :   bool ValidLength = false;
     119             :   bool ValidVersion = false;
     120             :   bool ValidAddrSize = false;
     121             :   bool ValidType = true;
     122             :   bool ValidAbbrevOffset = true;
     123             : 
     124          79 :   uint32_t OffsetStart = *Offset;
     125          79 :   Length = DebugInfoData.getU32(Offset);
     126          79 :   if (Length == UINT32_MAX) {
     127           0 :     isUnitDWARF64 = true;
     128           0 :     OS << format(
     129             :         "Unit[%d] is in 64-bit DWARF format; cannot verify from this point.\n",
     130             :         UnitIndex);
     131           0 :     return false;
     132             :   }
     133          79 :   Version = DebugInfoData.getU16(Offset);
     134             : 
     135          79 :   if (Version >= 5) {
     136           8 :     UnitType = DebugInfoData.getU8(Offset);
     137           8 :     AddrSize = DebugInfoData.getU8(Offset);
     138           8 :     AbbrOffset = DebugInfoData.getU32(Offset);
     139           8 :     ValidType = dwarf::isUnitType(UnitType);
     140             :   } else {
     141          71 :     UnitType = 0;
     142          71 :     AbbrOffset = DebugInfoData.getU32(Offset);
     143          71 :     AddrSize = DebugInfoData.getU8(Offset);
     144             :   }
     145             : 
     146          79 :   if (!DCtx.getDebugAbbrev()->getAbbreviationDeclarationSet(AbbrOffset))
     147             :     ValidAbbrevOffset = false;
     148             : 
     149          79 :   ValidLength = DebugInfoData.isValidOffset(OffsetStart + Length + 3);
     150          79 :   ValidVersion = DWARFContext::isSupportedVersion(Version);
     151          79 :   ValidAddrSize = AddrSize == 4 || AddrSize == 8;
     152          79 :   if (!ValidLength || !ValidVersion || !ValidAddrSize || !ValidAbbrevOffset ||
     153             :       !ValidType) {
     154             :     Success = false;
     155          10 :     error() << format("Units[%d] - start offset: 0x%08x \n", UnitIndex,
     156             :                       OffsetStart);
     157           5 :     if (!ValidLength)
     158           3 :       note() << "The length for this unit is too "
     159             :             "large for the .debug_info provided.\n";
     160           5 :     if (!ValidVersion)
     161           2 :       note() << "The 16 bit unit header version is not valid.\n";
     162           5 :     if (!ValidType)
     163           2 :       note() << "The unit type encoding is not valid.\n";
     164           5 :     if (!ValidAbbrevOffset)
     165           1 :       note() << "The offset into the .debug_abbrev section is "
     166             :             "not valid.\n";
     167           5 :     if (!ValidAddrSize)
     168           2 :       note() << "The address size is unsupported.\n";
     169             :   }
     170          79 :   *Offset = OffsetStart + Length + 4;
     171          79 :   return Success;
     172             : }
     173             : 
     174          74 : bool DWARFVerifier::verifyUnitContents(DWARFUnit Unit, uint8_t UnitType) {
     175             :   uint32_t NumUnitErrors = 0;
     176             :   unsigned NumDies = Unit.getNumDIEs();
     177        1114 :   for (unsigned I = 0; I < NumDies; ++I) {
     178         520 :     auto Die = Unit.getDIEAtIndex(I);
     179         399 :     if (Die.getTag() == DW_TAG_null)
     180         121 :       continue;
     181        4368 :     for (auto AttrValue : Die.attributes()) {
     182        1785 :       NumUnitErrors += verifyDebugInfoAttribute(Die, AttrValue);
     183        1785 :       NumUnitErrors += verifyDebugInfoForm(Die, AttrValue);
     184             :     }
     185             :   }
     186             : 
     187          74 :   DWARFDie Die = Unit.getUnitDIE(/* ExtractUnitDIEOnly = */ false);
     188             :   if (!Die) {
     189           1 :     error() << "Compilation unit without DIE.\n";
     190             :     NumUnitErrors++;
     191           1 :     return NumUnitErrors == 0;
     192             :   }
     193             : 
     194             :   if (!dwarf::isUnitType(Die.getTag())) {
     195           2 :     error() << "Compilation unit root DIE is not a unit DIE: "
     196           2 :             << dwarf::TagString(Die.getTag()) << ".\n";
     197           2 :     NumUnitErrors++;
     198             :   }
     199             : 
     200          77 :   if (UnitType != 0 &&
     201           4 :       !DWARFUnit::isMatchingUnitTypeAndTag(UnitType, Die.getTag())) {
     202           2 :     error() << "Compilation unit type (" << dwarf::UnitTypeString(UnitType)
     203           4 :             << ") and root DIE (" << dwarf::TagString(Die.getTag())
     204           2 :             << ") do not match.\n";
     205           2 :     NumUnitErrors++;
     206             :   }
     207             : 
     208          73 :   DieRangeInfo RI;
     209          73 :   NumUnitErrors += verifyDieRanges(Die, RI);
     210             : 
     211          73 :   return NumUnitErrors == 0;
     212             : }
     213             : 
     214          61 : unsigned DWARFVerifier::verifyAbbrevSection(const DWARFDebugAbbrev *Abbrev) {
     215             :   unsigned NumErrors = 0;
     216          61 :   if (Abbrev) {
     217             :     const DWARFAbbreviationDeclarationSet *AbbrDecls =
     218          61 :         Abbrev->getAbbreviationDeclarationSet(0);
     219         313 :     for (auto AbbrDecl : *AbbrDecls) {
     220             :       SmallDenseSet<uint16_t> AttributeSet;
     221        2300 :       for (auto Attribute : AbbrDecl.attributes()) {
     222        2048 :         auto Result = AttributeSet.insert(Attribute.Attr);
     223        1024 :         if (!Result.second) {
     224           4 :           error() << "Abbreviation declaration contains multiple "
     225           4 :                   << AttributeString(Attribute.Attr) << " attributes.\n";
     226           4 :           AbbrDecl.dump(OS);
     227           4 :           ++NumErrors;
     228             :         }
     229             :       }
     230             :     }
     231             :   }
     232          61 :   return NumErrors;
     233             : }
     234             : 
     235          65 : bool DWARFVerifier::handleDebugAbbrev() {
     236          65 :   OS << "Verifying .debug_abbrev...\n";
     237             : 
     238          65 :   const DWARFObject &DObj = DCtx.getDWARFObj();
     239         130 :   bool noDebugAbbrev = DObj.getAbbrevSection().empty();
     240         130 :   bool noDebugAbbrevDWO = DObj.getAbbrevDWOSection().empty();
     241             : 
     242          65 :   if (noDebugAbbrev && noDebugAbbrevDWO) {
     243             :     return true;
     244             :   }
     245             : 
     246             :   unsigned NumErrors = 0;
     247          60 :   if (!noDebugAbbrev)
     248          60 :     NumErrors += verifyAbbrevSection(DCtx.getDebugAbbrev());
     249             : 
     250          60 :   if (!noDebugAbbrevDWO)
     251           1 :     NumErrors += verifyAbbrevSection(DCtx.getDebugAbbrevDWO());
     252          60 :   return NumErrors == 0;
     253             : }
     254             : 
     255          55 : bool DWARFVerifier::handleDebugInfo() {
     256          55 :   OS << "Verifying .debug_info Unit Header Chain...\n";
     257             : 
     258          55 :   const DWARFObject &DObj = DCtx.getDWARFObj();
     259          55 :   DWARFDataExtractor DebugInfoData(DObj, DObj.getInfoSection(),
     260          55 :                                    DCtx.isLittleEndian(), 0);
     261             :   uint32_t NumDebugInfoErrors = 0;
     262          55 :   uint32_t OffsetStart = 0, Offset = 0, UnitIdx = 0;
     263          55 :   uint8_t UnitType = 0;
     264          55 :   bool isUnitDWARF64 = false;
     265             :   bool isHeaderChainValid = true;
     266             :   bool hasDIE = DebugInfoData.isValidOffset(Offset);
     267         110 :   DWARFUnitSection<DWARFTypeUnit> TUSection{};
     268         110 :   DWARFUnitSection<DWARFCompileUnit> CUSection{};
     269         213 :   while (hasDIE) {
     270          79 :     OffsetStart = Offset;
     271          79 :     if (!verifyUnitHeader(DebugInfoData, &Offset, UnitIdx, UnitType,
     272             :                           isUnitDWARF64)) {
     273             :       isHeaderChainValid = false;
     274           5 :       if (isUnitDWARF64)
     275             :         break;
     276             :     } else {
     277             :       DWARFUnitHeader Header;
     278          74 :       Header.extract(DCtx, DebugInfoData, &OffsetStart);
     279             :       std::unique_ptr<DWARFUnit> Unit;
     280          74 :       switch (UnitType) {
     281           0 :       case dwarf::DW_UT_type:
     282             :       case dwarf::DW_UT_split_type: {
     283           0 :         Unit.reset(new DWARFTypeUnit(
     284           0 :             DCtx, DObj.getInfoSection(), Header, DCtx.getDebugAbbrev(),
     285           0 :             &DObj.getRangeSection(), DObj.getStringSection(),
     286           0 :             DObj.getStringOffsetSection(), &DObj.getAppleObjCSection(),
     287           0 :             DObj.getLineSection(), DCtx.isLittleEndian(), false, TUSection));
     288           0 :         break;
     289             :       }
     290          74 :       case dwarf::DW_UT_skeleton:
     291             :       case dwarf::DW_UT_split_compile:
     292             :       case dwarf::DW_UT_compile:
     293             :       case dwarf::DW_UT_partial:
     294             :       // UnitType = 0 means that we are
     295             :       // verifying a compile unit in DWARF v4.
     296             :       case 0: {
     297         222 :         Unit.reset(new DWARFCompileUnit(
     298         148 :             DCtx, DObj.getInfoSection(), Header, DCtx.getDebugAbbrev(),
     299         148 :             &DObj.getRangeSection(), DObj.getStringSection(),
     300         148 :             DObj.getStringOffsetSection(), &DObj.getAppleObjCSection(),
     301         222 :             DObj.getLineSection(), DCtx.isLittleEndian(), false, CUSection));
     302          74 :         break;
     303             :       }
     304           0 :       default: { llvm_unreachable("Invalid UnitType."); }
     305             :       }
     306          74 :       if (!verifyUnitContents(*Unit, UnitType))
     307          16 :         ++NumDebugInfoErrors;
     308             :     }
     309          79 :     hasDIE = DebugInfoData.isValidOffset(Offset);
     310          79 :     ++UnitIdx;
     311             :   }
     312          55 :   if (UnitIdx == 0 && !hasDIE) {
     313           5 :     warn() << ".debug_info is empty.\n";
     314             :     isHeaderChainValid = true;
     315             :   }
     316          55 :   NumDebugInfoErrors += verifyDebugInfoReferences();
     317         110 :   return (isHeaderChainValid && NumDebugInfoErrors == 0);
     318             : }
     319             : 
     320         401 : unsigned DWARFVerifier::verifyDieRanges(const DWARFDie &Die,
     321             :                                         DieRangeInfo &ParentRI) {
     322             :   unsigned NumErrors = 0;
     323             : 
     324             :   if (!Die.isValid())
     325             :     return NumErrors;
     326             : 
     327         401 :   DWARFAddressRangesVector Ranges = Die.getAddressRanges();
     328             : 
     329             :   // Build RI for this DIE and check that ranges within this DIE do not
     330             :   // overlap.
     331         401 :   DieRangeInfo RI(Die);
     332         504 :   for (auto Range : Ranges) {
     333         105 :     if (!Range.valid()) {
     334           2 :       ++NumErrors;
     335           2 :       error() << "Invalid address range " << Range << "\n";
     336             :       continue;
     337             :     }
     338             : 
     339             :     // Verify that ranges don't intersect.
     340         101 :     const auto IntersectingRange = RI.insert(Range);
     341         101 :     if (IntersectingRange != RI.Ranges.end()) {
     342           0 :       ++NumErrors;
     343           0 :       error() << "DIE has overlapping address ranges: " << Range << " and "
     344           0 :               << *IntersectingRange << "\n";
     345             :       break;
     346             :     }
     347             :   }
     348             : 
     349             :   // Verify that children don't intersect.
     350         401 :   const auto IntersectingChild = ParentRI.insert(RI);
     351         401 :   if (IntersectingChild != ParentRI.Children.end()) {
     352           2 :     ++NumErrors;
     353           2 :     error() << "DIEs have overlapping address ranges:";
     354           4 :     Die.dump(OS, 0);
     355           4 :     IntersectingChild->Die.dump(OS, 0);
     356           2 :     OS << "\n";
     357             :   }
     358             : 
     359             :   // Verify that ranges are contained within their parent.
     360         549 :   bool ShouldBeContained = !Ranges.empty() && !ParentRI.Ranges.empty() &&
     361          36 :                            !(Die.getTag() == DW_TAG_subprogram &&
     362             :                              ParentRI.Die.getTag() == DW_TAG_subprogram);
     363          48 :   if (ShouldBeContained && !ParentRI.contains(RI)) {
     364           2 :     ++NumErrors;
     365           2 :     error() << "DIE address ranges are not contained in its parent's ranges:";
     366           4 :     ParentRI.Die.dump(OS, 0);
     367           4 :     Die.dump(OS, 2);
     368           2 :     OS << "\n";
     369             :   }
     370             : 
     371             :   // Recursively check children.
     372        1057 :   for (DWARFDie Child : Die)
     373         328 :     NumErrors += verifyDieRanges(Child, RI);
     374             : 
     375             :   return NumErrors;
     376             : }
     377             : 
     378        1785 : unsigned DWARFVerifier::verifyDebugInfoAttribute(const DWARFDie &Die,
     379             :                                                  DWARFAttribute &AttrValue) {
     380        1785 :   unsigned NumErrors = 0;
     381           4 :   auto ReportError = [&](const Twine &TitleMsg) {
     382           4 :     ++NumErrors;
     383          12 :     error() << TitleMsg << '\n';
     384           8 :     Die.dump(OS, 0, DumpOpts);
     385           4 :     OS << "\n";
     386        1789 :   };
     387             : 
     388        1785 :   const DWARFObject &DObj = DCtx.getDWARFObj();
     389        1785 :   const auto Attr = AttrValue.Attr;
     390        1785 :   switch (Attr) {
     391           5 :   case DW_AT_ranges:
     392             :     // Make sure the offset in the DW_AT_ranges attribute is valid.
     393           5 :     if (auto SectionOffset = AttrValue.Value.getAsSectionOffset()) {
     394          10 :       if (*SectionOffset >= DObj.getRangeSection().Data.size())
     395           1 :         ReportError("DW_AT_ranges offset is beyond .debug_ranges bounds:");
     396             :       break;
     397           5 :     }
     398           0 :     ReportError("DIE has invalid DW_AT_ranges encoding:");
     399           0 :     break;
     400          38 :   case DW_AT_stmt_list:
     401             :     // Make sure the offset in the DW_AT_stmt_list attribute is valid.
     402          38 :     if (auto SectionOffset = AttrValue.Value.getAsSectionOffset()) {
     403          74 :       if (*SectionOffset >= DObj.getLineSection().Data.size())
     404           1 :         ReportError("DW_AT_stmt_list offset is beyond .debug_line bounds: " +
     405           2 :                     llvm::formatv("{0:x8}", *SectionOffset));
     406             :       break;
     407          38 :     }
     408           1 :     ReportError("DIE has invalid DW_AT_stmt_list encoding:");
     409           1 :     break;
     410         117 :   case DW_AT_location: {
     411         123 :     auto VerifyLocationExpr = [&](StringRef D) {
     412         123 :       DWARFUnit *U = Die.getDwarfUnit();
     413         123 :       DataExtractor Data(D, DCtx.isLittleEndian(), 0);
     414             :       DWARFExpression Expression(Data, U->getVersion(),
     415             :                                  U->getAddressByteSize());
     416             :       bool Error = llvm::any_of(Expression, [](DWARFExpression::Operation &Op) {
     417             :         return Op.isError();
     418         123 :       });
     419         123 :       if (Error)
     420           2 :         ReportError("DIE contains invalid DWARF expression:");
     421         240 :     };
     422         117 :     if (Optional<ArrayRef<uint8_t>> Expr = AttrValue.Value.getAsBlock()) {
     423             :       // Verify inlined location.
     424         106 :       VerifyLocationExpr(llvm::toStringRef(*Expr));
     425          11 :     } else if (auto LocOffset = AttrValue.Value.getAsSectionOffset()) {
     426             :       // Verify location list.
     427          11 :       if (auto DebugLoc = DCtx.getDebugLoc())
     428          11 :         if (auto LocList = DebugLoc->getLocationListAtOffset(*LocOffset))
     429          45 :           for (const auto &Entry : LocList->Entries)
     430          34 :             VerifyLocationExpr({Entry.Loc.data(), Entry.Loc.size()});
     431             :     }
     432             :     break;
     433             :   }
     434             : 
     435             :   default:
     436             :     break;
     437             :   }
     438        1785 :   return NumErrors;
     439             : }
     440             : 
     441        1785 : unsigned DWARFVerifier::verifyDebugInfoForm(const DWARFDie &Die,
     442             :                                             DWARFAttribute &AttrValue) {
     443        1785 :   const DWARFObject &DObj = DCtx.getDWARFObj();
     444             :   unsigned NumErrors = 0;
     445        1785 :   const auto Form = AttrValue.Value.getForm();
     446        1785 :   switch (Form) {
     447         232 :   case DW_FORM_ref1:
     448             :   case DW_FORM_ref2:
     449             :   case DW_FORM_ref4:
     450             :   case DW_FORM_ref8:
     451             :   case DW_FORM_ref_udata: {
     452             :     // Verify all CU relative references are valid CU offsets.
     453         232 :     Optional<uint64_t> RefVal = AttrValue.Value.getAsReference();
     454             :     assert(RefVal);
     455         232 :     if (RefVal) {
     456         232 :       auto DieCU = Die.getDwarfUnit();
     457         232 :       auto CUSize = DieCU->getNextUnitOffset() - DieCU->getOffset();
     458         232 :       auto CUOffset = AttrValue.Value.getRawUValue();
     459         232 :       if (CUOffset >= CUSize) {
     460             :         ++NumErrors;
     461           1 :         error() << FormEncodingString(Form) << " CU offset "
     462           2 :                 << format("0x%08" PRIx64, CUOffset)
     463           1 :                 << " is invalid (must be less than CU size of "
     464           1 :                 << format("0x%08" PRIx32, CUSize) << "):\n";
     465           1 :         Die.dump(OS, 0, DumpOpts);
     466           1 :         OS << "\n";
     467             :       } else {
     468             :         // Valid reference, but we will verify it points to an actual
     469             :         // DIE later.
     470         693 :         ReferenceToDIEOffsets[*RefVal].insert(Die.getOffset());
     471             :       }
     472             :     }
     473             :     break;
     474             :   }
     475          32 :   case DW_FORM_ref_addr: {
     476             :     // Verify all absolute DIE references have valid offsets in the
     477             :     // .debug_info section.
     478          32 :     Optional<uint64_t> RefVal = AttrValue.Value.getAsReference();
     479             :     assert(RefVal);
     480          32 :     if (RefVal) {
     481          64 :       if (*RefVal >= DObj.getInfoSection().Data.size()) {
     482             :         ++NumErrors;
     483           1 :         error() << "DW_FORM_ref_addr offset beyond .debug_info "
     484             :                    "bounds:\n";
     485           1 :         Die.dump(OS, 0, DumpOpts);
     486           1 :         OS << "\n";
     487             :       } else {
     488             :         // Valid reference, but we will verify it points to an actual
     489             :         // DIE later.
     490          93 :         ReferenceToDIEOffsets[*RefVal].insert(Die.getOffset());
     491             :       }
     492             :     }
     493             :     break;
     494             :   }
     495         408 :   case DW_FORM_strp: {
     496         408 :     auto SecOffset = AttrValue.Value.getAsSectionOffset();
     497             :     assert(SecOffset); // DW_FORM_strp is a section offset.
     498        1223 :     if (SecOffset && *SecOffset >= DObj.getStringSection().size()) {
     499             :       ++NumErrors;
     500           1 :       error() << "DW_FORM_strp offset beyond .debug_str bounds:\n";
     501           1 :       Die.dump(OS, 0, DumpOpts);
     502           1 :       OS << "\n";
     503             :     }
     504             :     break;
     505             :   }
     506             :   default:
     507             :     break;
     508             :   }
     509        1785 :   return NumErrors;
     510             : }
     511             : 
     512          55 : unsigned DWARFVerifier::verifyDebugInfoReferences() {
     513             :   // Take all references and make sure they point to an actual DIE by
     514             :   // getting the DIE by offset and emitting an error
     515          55 :   OS << "Verifying .debug_info references...\n";
     516             :   unsigned NumErrors = 0;
     517         160 :   for (auto Pair : ReferenceToDIEOffsets) {
     518         105 :     auto Die = DCtx.getDIEForOffset(Pair.first);
     519         104 :     if (Die)
     520             :       continue;
     521           1 :     ++NumErrors;
     522           3 :     error() << "invalid DIE reference " << format("0x%08" PRIx64, Pair.first)
     523           1 :             << ". Offset is in between DIEs:\n";
     524           2 :     for (auto Offset : Pair.second) {
     525           1 :       auto ReferencingDie = DCtx.getDIEForOffset(Offset);
     526           1 :       ReferencingDie.dump(OS, 0, DumpOpts);
     527           1 :       OS << "\n";
     528             :     }
     529           1 :     OS << "\n";
     530             :   }
     531          55 :   return NumErrors;
     532             : }
     533             : 
     534          30 : void DWARFVerifier::verifyDebugLineStmtOffsets() {
     535             :   std::map<uint64_t, DWARFDie> StmtListToDie;
     536         156 :   for (const auto &CU : DCtx.compile_units()) {
     537          96 :     auto Die = CU->getUnitDIE();
     538             :     // Get the attribute value as a section offset. No need to produce an
     539             :     // error here if the encoding isn't correct because we validate this in
     540             :     // the .debug_info verifier.
     541          96 :     auto StmtSectionOffset = toSectionOffset(Die.find(DW_AT_stmt_list));
     542          48 :     if (!StmtSectionOffset)
     543          15 :       continue;
     544          33 :     const uint32_t LineTableOffset = *StmtSectionOffset;
     545          66 :     auto LineTable = DCtx.getLineTableForUnit(CU.get());
     546         100 :     if (LineTableOffset < DCtx.getDWARFObj().getLineSection().Data.size()) {
     547          32 :       if (!LineTable) {
     548           0 :         ++NumDebugLineErrors;
     549           0 :         error() << ".debug_line[" << format("0x%08" PRIx32, LineTableOffset)
     550           0 :                 << "] was not able to be parsed for CU:\n";
     551           0 :         Die.dump(OS, 0, DumpOpts);
     552           0 :         OS << '\n';
     553           0 :         continue;
     554             :       }
     555             :     } else {
     556             :       // Make sure we don't get a valid line table back if the offset is wrong.
     557             :       assert(LineTable == nullptr);
     558             :       // Skip this line table as it isn't valid. No need to create an error
     559             :       // here because we validate this in the .debug_info verifier.
     560           1 :       continue;
     561             :     }
     562             :     auto Iter = StmtListToDie.find(LineTableOffset);
     563          33 :     if (Iter != StmtListToDie.end()) {
     564           1 :       ++NumDebugLineErrors;
     565           1 :       error() << "two compile unit DIEs, "
     566           3 :               << format("0x%08" PRIx32, Iter->second.getOffset()) << " and "
     567           3 :               << format("0x%08" PRIx32, Die.getOffset())
     568           1 :               << ", have the same DW_AT_stmt_list section offset:\n";
     569           1 :       Iter->second.dump(OS, 0, DumpOpts);
     570           1 :       Die.dump(OS, 0, DumpOpts);
     571           1 :       OS << '\n';
     572             :       // Already verified this line table before, no need to do it again.
     573           1 :       continue;
     574             :     }
     575          31 :     StmtListToDie[LineTableOffset] = Die;
     576             :   }
     577          30 : }
     578             : 
     579          30 : void DWARFVerifier::verifyDebugLineRows() {
     580         156 :   for (const auto &CU : DCtx.compile_units()) {
     581          96 :     auto Die = CU->getUnitDIE();
     582          96 :     auto LineTable = DCtx.getLineTableForUnit(CU.get());
     583             :     // If there is no line table we will have created an error in the
     584             :     // .debug_info verifier or in verifyDebugLineStmtOffsets().
     585          48 :     if (!LineTable)
     586          16 :       continue;
     587             : 
     588             :     // Verify prologue.
     589          64 :     uint32_t MaxFileIndex = LineTable->Prologue.FileNames.size();
     590          32 :     uint32_t MaxDirIndex = LineTable->Prologue.IncludeDirectories.size();
     591             :     uint32_t FileIndex = 1;
     592          32 :     StringMap<uint16_t> FullPathMap;
     593          65 :     for (const auto &FileName : LineTable->Prologue.FileNames) {
     594             :       // Verify directory index.
     595          33 :       if (FileName.DirIdx > MaxDirIndex) {
     596           1 :         ++NumDebugLineErrors;
     597           1 :         error() << ".debug_line["
     598           2 :                 << format("0x%08" PRIx64,
     599           3 :                           *toSectionOffset(Die.find(DW_AT_stmt_list)))
     600           1 :                 << "].prologue.file_names[" << FileIndex
     601           1 :                 << "].dir_idx contains an invalid index: " << FileName.DirIdx
     602           1 :                 << "\n";
     603             :       }
     604             : 
     605             :       // Check file paths for duplicates.
     606             :       std::string FullPath;
     607          33 :       const bool HasFullPath = LineTable->getFileNameByIndex(
     608             :           FileIndex, CU->getCompilationDir(),
     609          33 :           DILineInfoSpecifier::FileLineInfoKind::AbsoluteFilePath, FullPath);
     610             :       assert(HasFullPath && "Invalid index?");
     611             :       (void)HasFullPath;
     612          33 :       auto It = FullPathMap.find(FullPath);
     613          66 :       if (It == FullPathMap.end())
     614          32 :         FullPathMap[FullPath] = FileIndex;
     615           1 :       else if (It->second != FileIndex) {
     616           1 :         warn() << ".debug_line["
     617           2 :                << format("0x%08" PRIx64,
     618           3 :                          *toSectionOffset(Die.find(DW_AT_stmt_list)))
     619           1 :                << "].prologue.file_names[" << FileIndex
     620           3 :                << "] is a duplicate of file_names[" << It->second << "]\n";
     621             :       }
     622             : 
     623          33 :       FileIndex++;
     624             :     }
     625             : 
     626             :     // Verify rows.
     627             :     uint64_t PrevAddress = 0;
     628             :     uint32_t RowIndex = 0;
     629          32 :     for (const auto &Row : LineTable->Rows) {
     630             :       // Verify row address.
     631         174 :       if (Row.Address < PrevAddress) {
     632           1 :         ++NumDebugLineErrors;
     633           1 :         error() << ".debug_line["
     634           2 :                 << format("0x%08" PRIx64,
     635           3 :                           *toSectionOffset(Die.find(DW_AT_stmt_list)))
     636           1 :                 << "] row[" << RowIndex
     637           1 :                 << "] decreases in address from previous row:\n";
     638             : 
     639           1 :         DWARFDebugLine::Row::dumpTableHeader(OS);
     640           1 :         if (RowIndex > 0)
     641           2 :           LineTable->Rows[RowIndex - 1].dump(OS);
     642           1 :         Row.dump(OS);
     643           1 :         OS << '\n';
     644             :       }
     645             : 
     646             :       // Verify file index.
     647         174 :       if (Row.File > MaxFileIndex) {
     648           1 :         ++NumDebugLineErrors;
     649           1 :         error() << ".debug_line["
     650           2 :                 << format("0x%08" PRIx64,
     651           3 :                           *toSectionOffset(Die.find(DW_AT_stmt_list)))
     652           2 :                 << "][" << RowIndex << "] has invalid file index " << Row.File
     653           2 :                 << " (valid values are [1," << MaxFileIndex << "]):\n";
     654           1 :         DWARFDebugLine::Row::dumpTableHeader(OS);
     655           1 :         Row.dump(OS);
     656           1 :         OS << '\n';
     657             :       }
     658         174 :       if (Row.EndSequence)
     659             :         PrevAddress = 0;
     660             :       else
     661         132 :         PrevAddress = Row.Address;
     662         174 :       ++RowIndex;
     663             :     }
     664             :   }
     665          30 : }
     666             : 
     667          30 : bool DWARFVerifier::handleDebugLine() {
     668          30 :   NumDebugLineErrors = 0;
     669          30 :   OS << "Verifying .debug_line...\n";
     670          30 :   verifyDebugLineStmtOffsets();
     671          30 :   verifyDebugLineRows();
     672          30 :   return NumDebugLineErrors == 0;
     673             : }
     674             : 
     675          48 : unsigned DWARFVerifier::verifyAppleAccelTable(const DWARFSection *AccelSection,
     676             :                                               DataExtractor *StrData,
     677             :                                               const char *SectionName) {
     678             :   unsigned NumErrors = 0;
     679          48 :   DWARFDataExtractor AccelSectionData(DCtx.getDWARFObj(), *AccelSection,
     680          48 :                                       DCtx.isLittleEndian(), 0);
     681          48 :   AppleAcceleratorTable AccelTable(AccelSectionData, *StrData);
     682             : 
     683          48 :   OS << "Verifying " << SectionName << "...\n";
     684             : 
     685             :   // Verify that the fixed part of the header is not too short.
     686          96 :   if (!AccelSectionData.isValidOffset(AccelTable.getSizeHdr())) {
     687           0 :     error() << "Section is too small to fit a section header.\n";
     688           0 :     return 1;
     689             :   }
     690             : 
     691             :   // Verify that the section is not too short.
     692          96 :   if (Error E = AccelTable.extract()) {
     693           4 :     error() << toString(std::move(E)) << '\n';
     694             :     return 1;
     695             :   }
     696             : 
     697             :   // Verify that all buckets have a valid hash index or are empty.
     698          47 :   uint32_t NumBuckets = AccelTable.getNumBuckets();
     699          47 :   uint32_t NumHashes = AccelTable.getNumHashes();
     700             : 
     701             :   uint32_t BucketsOffset =
     702          47 :       AccelTable.getSizeHdr() + AccelTable.getHeaderDataLength();
     703          47 :   uint32_t HashesBase = BucketsOffset + NumBuckets * 4;
     704          47 :   uint32_t OffsetsBase = HashesBase + NumHashes * 4;
     705         313 :   for (uint32_t BucketIdx = 0; BucketIdx < NumBuckets; ++BucketIdx) {
     706         133 :     uint32_t HashIdx = AccelSectionData.getU32(&BucketsOffset);
     707         133 :     if (HashIdx >= NumHashes && HashIdx != UINT32_MAX) {
     708           2 :       error() << format("Bucket[%d] has invalid hash index: %u.\n", BucketIdx,
     709             :                         HashIdx);
     710           1 :       ++NumErrors;
     711             :     }
     712             :   }
     713          47 :   uint32_t NumAtoms = AccelTable.getAtomsDesc().size();
     714          47 :   if (NumAtoms == 0) {
     715           1 :     error() << "No atoms: failed to read HashData.\n";
     716           1 :     return 1;
     717             :   }
     718          46 :   if (!AccelTable.validateForms()) {
     719           1 :     error() << "Unsupported form: failed to read HashData.\n";
     720           1 :     return 1;
     721             :   }
     722             : 
     723         305 :   for (uint32_t HashIdx = 0; HashIdx < NumHashes; ++HashIdx) {
     724         130 :     uint32_t HashOffset = HashesBase + 4 * HashIdx;
     725         130 :     uint32_t DataOffset = OffsetsBase + 4 * HashIdx;
     726         130 :     uint32_t Hash = AccelSectionData.getU32(&HashOffset);
     727         130 :     uint32_t HashDataOffset = AccelSectionData.getU32(&DataOffset);
     728             :     if (!AccelSectionData.isValidOffsetForDataOfSize(HashDataOffset,
     729             :                                                      sizeof(uint64_t))) {
     730           2 :       error() << format("Hash[%d] has invalid HashData offset: 0x%08x.\n",
     731             :                         HashIdx, HashDataOffset);
     732           1 :       ++NumErrors;
     733             :     }
     734             : 
     735             :     uint32_t StrpOffset;
     736             :     uint32_t StringOffset;
     737             :     uint32_t StringCount = 0;
     738             :     unsigned Offset;
     739             :     unsigned Tag;
     740         390 :     while ((StrpOffset = AccelSectionData.getU32(&HashDataOffset)) != 0) {
     741             :       const uint32_t NumHashDataObjects =
     742         130 :           AccelSectionData.getU32(&HashDataOffset);
     743         460 :       for (uint32_t HashDataIdx = 0; HashDataIdx < NumHashDataObjects;
     744             :            ++HashDataIdx) {
     745         330 :         std::tie(Offset, Tag) = AccelTable.readAtoms(HashDataOffset);
     746         165 :         auto Die = DCtx.getDIEForOffset(Offset);
     747             :         if (!Die) {
     748             :           const uint32_t BucketIdx =
     749           2 :               NumBuckets ? (Hash % NumBuckets) : UINT32_MAX;
     750           1 :           StringOffset = StrpOffset;
     751           1 :           const char *Name = StrData->getCStr(&StringOffset);
     752           1 :           if (!Name)
     753             :             Name = "<NULL>";
     754             : 
     755           2 :           error() << format(
     756             :               "%s Bucket[%d] Hash[%d] = 0x%08x "
     757             :               "Str[%u] = 0x%08x "
     758             :               "DIE[%d] = 0x%08x is not a valid DIE offset for \"%s\".\n",
     759             :               SectionName, BucketIdx, HashIdx, Hash, StringCount, StrpOffset,
     760             :               HashDataIdx, Offset, Name);
     761             : 
     762           1 :           ++NumErrors;
     763           1 :           continue;
     764             :         }
     765         197 :         if ((Tag != dwarf::DW_TAG_null) && (Die.getTag() != Tag)) {
     766           1 :           error() << "Tag " << dwarf::TagString(Tag)
     767           1 :                   << " in accelerator table does not match Tag "
     768           1 :                   << dwarf::TagString(Die.getTag()) << " of DIE[" << HashDataIdx
     769           1 :                   << "].\n";
     770           1 :           ++NumErrors;
     771             :         }
     772             :       }
     773         130 :       ++StringCount;
     774             :     }
     775             :   }
     776             :   return NumErrors;
     777             : }
     778             : 
     779             : unsigned
     780          17 : DWARFVerifier::verifyDebugNamesCULists(const DWARFDebugNames &AccelTable) {
     781             :   // A map from CU offset to the (first) Name Index offset which claims to index
     782             :   // this CU.
     783             :   DenseMap<uint32_t, uint32_t> CUMap;
     784             :   const uint32_t NotIndexed = std::numeric_limits<uint32_t>::max();
     785             : 
     786          34 :   CUMap.reserve(DCtx.getNumCompileUnits());
     787         590 :   for (const auto &CU : DCtx.compile_units())
     788         556 :     CUMap[CU->getOffset()] = NotIndexed;
     789             : 
     790             :   unsigned NumErrors = 0;
     791          57 :   for (const DWARFDebugNames::NameIndex &NI : AccelTable) {
     792          21 :     if (NI.getCUCount() == 0) {
     793           3 :       error() << formatv("Name Index @ {0:x} does not index any CU\n",
     794           1 :                          NI.getUnitOffset());
     795           1 :       ++NumErrors;
     796           1 :       continue;
     797             :     }
     798         577 :     for (uint32_t CU = 0, End = NI.getCUCount(); CU < End; ++CU) {
     799         279 :       uint32_t Offset = NI.getCUOffset(CU);
     800         279 :       auto Iter = CUMap.find(Offset);
     801             : 
     802         280 :       if (Iter == CUMap.end()) {
     803           3 :         error() << formatv(
     804             :             "Name Index @ {0:x} references a non-existing CU @ {1:x}\n",
     805           1 :             NI.getUnitOffset(), Offset);
     806           1 :         ++NumErrors;
     807           3 :         continue;
     808             :       }
     809             : 
     810         279 :       if (Iter->second != NotIndexed) {
     811           3 :         error() << formatv("Name Index @ {0:x} references a CU @ {1:x}, but "
     812             :                           "this CU is already indexed by Name Index @ {2:x}\n",
     813           1 :                           NI.getUnitOffset(), Offset, Iter->second);
     814           1 :         continue;
     815             :       }
     816         277 :       Iter->second = NI.getUnitOffset();
     817             :     }
     818             :   }
     819             : 
     820         312 :   for (const auto &KV : CUMap) {
     821         278 :     if (KV.second == NotIndexed)
     822           3 :       warn() << formatv("CU @ {0:x} not covered by any Name Index\n", KV.first);
     823             :   }
     824             : 
     825          17 :   return NumErrors;
     826             : }
     827             : 
     828             : unsigned
     829          20 : DWARFVerifier::verifyNameIndexBuckets(const DWARFDebugNames::NameIndex &NI,
     830             :                                       const DataExtractor &StrData) {
     831             :   struct BucketInfo {
     832             :     uint32_t Bucket;
     833             :     uint32_t Index;
     834             : 
     835             :     constexpr BucketInfo(uint32_t Bucket, uint32_t Index)
     836         161 :         : Bucket(Bucket), Index(Index) {}
     837             :     bool operator<(const BucketInfo &RHS) const { return Index < RHS.Index; };
     838             :   };
     839             : 
     840             :   uint32_t NumErrors = 0;
     841          20 :   if (NI.getBucketCount() == 0) {
     842          24 :     warn() << formatv("Name Index @ {0:x} does not contain a hash table.\n",
     843           8 :                       NI.getUnitOffset());
     844           8 :     return NumErrors;
     845             :   }
     846             : 
     847             :   // Build up a list of (Bucket, Index) pairs. We use this later to verify that
     848             :   // each Name is reachable from the appropriate bucket.
     849             :   std::vector<BucketInfo> BucketStarts;
     850          12 :   BucketStarts.reserve(NI.getBucketCount() + 1);
     851         178 :   for (uint32_t Bucket = 0, End = NI.getBucketCount(); Bucket < End; ++Bucket) {
     852         166 :     uint32_t Index = NI.getBucketArrayEntry(Bucket);
     853         167 :     if (Index > NI.getNameCount()) {
     854           3 :       error() << formatv("Bucket {0} of Name Index @ {1:x} contains invalid "
     855             :                          "value {2}. Valid range is [0, {3}].\n",
     856           1 :                          Bucket, NI.getUnitOffset(), Index, NI.getNameCount());
     857           1 :       ++NumErrors;
     858           1 :       continue;
     859             :     }
     860         165 :     if (Index > 0)
     861         150 :       BucketStarts.emplace_back(Bucket, Index);
     862             :   }
     863             : 
     864             :   // If there were any buckets with invalid values, skip further checks as they
     865             :   // will likely produce many errors which will only confuse the actual root
     866             :   // problem.
     867          12 :   if (NumErrors > 0)
     868             :     return NumErrors;
     869             : 
     870             :   // Sort the list in the order of increasing "Index" entries.
     871             :   array_pod_sort(BucketStarts.begin(), BucketStarts.end());
     872             : 
     873             :   // Insert a sentinel entry at the end, so we can check that the end of the
     874             :   // table is covered in the loop below.
     875          11 :   BucketStarts.emplace_back(NI.getBucketCount(), NI.getNameCount() + 1);
     876             : 
     877             :   // Loop invariant: NextUncovered is the (1-based) index of the first Name
     878             :   // which is not reachable by any of the buckets we processed so far (and
     879             :   // hasn't been reported as uncovered).
     880          11 :   uint32_t NextUncovered = 1;
     881         160 :   for (const BucketInfo &B : BucketStarts) {
     882             :     // Under normal circumstances B.Index be equal to NextUncovered, but it can
     883             :     // be less if a bucket points to names which are already known to be in some
     884             :     // bucket we processed earlier. In that case, we won't trigger this error,
     885             :     // but report the mismatched hash value error instead. (We know the hash
     886             :     // will not match because we have already verified that the name's hash
     887             :     // puts it into the previous bucket.)
     888         160 :     if (B.Index > NextUncovered) {
     889           6 :       error() << formatv("Name Index @ {0:x}: Name table entries [{1}, {2}] "
     890             :                          "are not covered by the hash table.\n",
     891           2 :                          NI.getUnitOffset(), NextUncovered, B.Index - 1);
     892           2 :       ++NumErrors;
     893             :     }
     894         160 :     uint32_t Idx = B.Index;
     895             : 
     896             :     // The rest of the checks apply only to non-sentinel entries.
     897         160 :     if (B.Bucket == NI.getBucketCount())
     898             :       break;
     899             : 
     900             :     // This triggers if a non-empty bucket points to a name with a mismatched
     901             :     // hash. Clients are likely to interpret this as an empty bucket, because a
     902             :     // mismatched hash signals the end of a bucket, but if this is indeed an
     903             :     // empty bucket, the producer should have signalled this by marking the
     904             :     // bucket as empty.
     905         149 :     uint32_t FirstHash = NI.getHashArrayEntry(Idx);
     906         149 :     if (FirstHash % NI.getBucketCount() != B.Bucket) {
     907           4 :       error() << formatv(
     908             :           "Name Index @ {0:x}: Bucket {1} is not empty but points to a "
     909             :           "mismatched hash value {2:x} (belonging to bucket {3}).\n",
     910           1 :           NI.getUnitOffset(), B.Bucket, FirstHash,
     911           1 :           FirstHash % NI.getBucketCount());
     912           1 :       ++NumErrors;
     913             :     }
     914             : 
     915             :     // This find the end of this bucket and also verifies that all the hashes in
     916             :     // this bucket are correct by comparing the stored hashes to the ones we
     917             :     // compute ourselves.
     918         745 :     while (Idx <= NI.getNameCount()) {
     919         437 :       uint32_t Hash = NI.getHashArrayEntry(Idx);
     920         437 :       if (Hash % NI.getBucketCount() != B.Bucket)
     921             :         break;
     922             : 
     923         596 :       const char *Str = NI.getNameTableEntry(Idx).getString();
     924         298 :       if (caseFoldingDjbHash(Str) != Hash) {
     925           3 :         error() << formatv("Name Index @ {0:x}: String ({1}) at index {2} "
     926             :                            "hashes to {3:x}, but "
     927             :                            "the Name Index hash is {4:x}\n",
     928           1 :                            NI.getUnitOffset(), Str, Idx,
     929           3 :                            caseFoldingDjbHash(Str), Hash);
     930           1 :         ++NumErrors;
     931             :       }
     932             : 
     933         298 :       ++Idx;
     934             :     }
     935         149 :     NextUncovered = std::max(NextUncovered, Idx);
     936             :   }
     937             :   return NumErrors;
     938             : }
     939             : 
     940          42 : unsigned DWARFVerifier::verifyNameIndexAttribute(
     941             :     const DWARFDebugNames::NameIndex &NI, const DWARFDebugNames::Abbrev &Abbr,
     942             :     DWARFDebugNames::AttributeEncoding AttrEnc) {
     943          42 :   StringRef FormName = dwarf::FormEncodingString(AttrEnc.Form);
     944          42 :   if (FormName.empty()) {
     945           3 :     error() << formatv("NameIndex @ {0:x}: Abbreviation {1:x}: {2} uses an "
     946             :                        "unknown form: {3}.\n",
     947           1 :                        NI.getUnitOffset(), Abbr.Code, AttrEnc.Index,
     948             :                        AttrEnc.Form);
     949           1 :     return 1;
     950             :   }
     951             : 
     952          41 :   if (AttrEnc.Index == DW_IDX_type_hash) {
     953           1 :     if (AttrEnc.Form != dwarf::DW_FORM_data8) {
     954           3 :       error() << formatv(
     955             :           "NameIndex @ {0:x}: Abbreviation {1:x}: DW_IDX_type_hash "
     956             :           "uses an unexpected form {2} (should be {3}).\n",
     957           1 :           NI.getUnitOffset(), Abbr.Code, AttrEnc.Form, dwarf::DW_FORM_data8);
     958           1 :       return 1;
     959             :     }
     960             :   }
     961             : 
     962             :   // A list of known index attributes and their expected form classes.
     963             :   // DW_IDX_type_hash is handled specially in the check above, as it has a
     964             :   // specific form (not just a form class) we should expect.
     965             :   struct FormClassTable {
     966             :     dwarf::Index Index;
     967             :     DWARFFormValue::FormClass Class;
     968             :     StringLiteral ClassName;
     969             :   };
     970             :   static constexpr FormClassTable Table[] = {
     971             :       {dwarf::DW_IDX_compile_unit, DWARFFormValue::FC_Constant, {"constant"}},
     972             :       {dwarf::DW_IDX_type_unit, DWARFFormValue::FC_Constant, {"constant"}},
     973             :       {dwarf::DW_IDX_die_offset, DWARFFormValue::FC_Reference, {"reference"}},
     974             :       {dwarf::DW_IDX_parent, DWARFFormValue::FC_Constant, {"constant"}},
     975             :   };
     976             : 
     977             :   ArrayRef<FormClassTable> TableRef(Table);
     978             :   auto Iter = find_if(TableRef, [AttrEnc](const FormClassTable &T) {
     979             :     return T.Index == AttrEnc.Index;
     980             :   });
     981          40 :   if (Iter == TableRef.end()) {
     982           3 :     warn() << formatv("NameIndex @ {0:x}: Abbreviation {1:x} contains an "
     983             :                       "unknown index attribute: {2}.\n",
     984           1 :                       NI.getUnitOffset(), Abbr.Code, AttrEnc.Index);
     985           1 :     return 0;
     986             :   }
     987             : 
     988          78 :   if (!DWARFFormValue(AttrEnc.Form).isFormClass(Iter->Class)) {
     989           6 :     error() << formatv("NameIndex @ {0:x}: Abbreviation {1:x}: {2} uses an "
     990             :                        "unexpected form {3} (expected form class {4}).\n",
     991           2 :                        NI.getUnitOffset(), Abbr.Code, AttrEnc.Index,
     992             :                        AttrEnc.Form, Iter->ClassName);
     993           2 :     return 1;
     994             :   }
     995             :   return 0;
     996             : }
     997             : 
     998             : unsigned
     999          20 : DWARFVerifier::verifyNameIndexAbbrevs(const DWARFDebugNames::NameIndex &NI) {
    1000          20 :   if (NI.getLocalTUCount() + NI.getForeignTUCount() > 0) {
    1001           0 :     warn() << formatv("Name Index @ {0:x}: Verifying indexes of type units is "
    1002             :                       "not currently supported.\n",
    1003           0 :                       NI.getUnitOffset());
    1004           0 :     return 0;
    1005             :   }
    1006             : 
    1007             :   unsigned NumErrors = 0;
    1008          74 :   for (const auto &Abbrev : NI.getAbbrevs()) {
    1009          34 :     StringRef TagName = dwarf::TagString(Abbrev.Tag);
    1010          34 :     if (TagName.empty()) {
    1011           3 :       warn() << formatv("NameIndex @ {0:x}: Abbreviation {1:x} references an "
    1012             :                         "unknown tag: {2}.\n",
    1013           1 :                         NI.getUnitOffset(), Abbrev.Code, Abbrev.Tag);
    1014             :     }
    1015          34 :     SmallSet<unsigned, 5> Attributes;
    1016          34 :     for (const auto &AttrEnc : Abbrev.Attributes) {
    1017          46 :       if (!Attributes.insert(AttrEnc.Index).second) {
    1018           6 :         error() << formatv("NameIndex @ {0:x}: Abbreviation {1:x} contains "
    1019             :                            "multiple {2} attributes.\n",
    1020           2 :                            NI.getUnitOffset(), Abbrev.Code, AttrEnc.Index);
    1021           2 :         ++NumErrors;
    1022           2 :         continue;
    1023             :       }
    1024          42 :       NumErrors += verifyNameIndexAttribute(NI, Abbrev, AttrEnc);
    1025             :     }
    1026             : 
    1027          67 :     if (NI.getCUCount() > 1 && !Attributes.count(dwarf::DW_IDX_compile_unit)) {
    1028           3 :       error() << formatv("NameIndex @ {0:x}: Indexing multiple compile units "
    1029             :                          "and abbreviation {1:x} has no {2} attribute.\n",
    1030           1 :                          NI.getUnitOffset(), Abbrev.Code,
    1031             :                          dwarf::DW_IDX_compile_unit);
    1032           1 :       ++NumErrors;
    1033             :     }
    1034          34 :     if (!Attributes.count(dwarf::DW_IDX_die_offset)) {
    1035           6 :       error() << formatv(
    1036             :           "NameIndex @ {0:x}: Abbreviation {1:x} has no {2} attribute.\n",
    1037           2 :           NI.getUnitOffset(), Abbrev.Code, dwarf::DW_IDX_die_offset);
    1038           2 :       ++NumErrors;
    1039             :     }
    1040             :   }
    1041          20 :   return NumErrors;
    1042             : }
    1043             : 
    1044        1174 : static SmallVector<StringRef, 2> getNames(const DWARFDie &DIE) {
    1045             :   SmallVector<StringRef, 2> Result;
    1046        1174 :   if (const char *Str = DIE.getName(DINameKind::ShortName))
    1047         879 :     Result.emplace_back(Str);
    1048          12 :   else if (DIE.getTag() == dwarf::DW_TAG_namespace)
    1049           2 :     Result.emplace_back("(anonymous namespace)");
    1050             : 
    1051        1174 :   if (const char *Str = DIE.getName(DINameKind::LinkageName)) {
    1052         881 :     if (Result.empty() || Result[0] != Str)
    1053          27 :       Result.emplace_back(Str);
    1054             :   }
    1055             : 
    1056        1174 :   return Result;
    1057             : }
    1058             : 
    1059         299 : unsigned DWARFVerifier::verifyNameIndexEntries(
    1060             :     const DWARFDebugNames::NameIndex &NI,
    1061             :     const DWARFDebugNames::NameTableEntry &NTE) {
    1062             :   // Verifying type unit indexes not supported.
    1063         299 :   if (NI.getLocalTUCount() + NI.getForeignTUCount() > 0)
    1064             :     return 0;
    1065             : 
    1066             :   const char *CStr = NTE.getString();
    1067         299 :   if (!CStr) {
    1068           3 :     error() << formatv(
    1069             :         "Name Index @ {0:x}: Unable to get string associated with name {1}.\n",
    1070           1 :         NI.getUnitOffset(), NTE.getIndex());
    1071           1 :     return 1;
    1072             :   }
    1073             :   StringRef Str(CStr);
    1074             : 
    1075         298 :   unsigned NumErrors = 0;
    1076         298 :   unsigned NumEntries = 0;
    1077         298 :   uint32_t EntryID = NTE.getEntryOffset();
    1078         298 :   uint32_t NextEntryID = EntryID;
    1079         596 :   Expected<DWARFDebugNames::Entry> EntryOr = NI.getEntry(&NextEntryID);
    1080        1222 :   for (; EntryOr; ++NumEntries, EntryID = NextEntryID,
    1081         616 :                                 EntryOr = NI.getEntry(&NextEntryID)) {
    1082         308 :     uint32_t CUIndex = *EntryOr->getCUIndex();
    1083         309 :     if (CUIndex > NI.getCUCount()) {
    1084           3 :       error() << formatv("Name Index @ {0:x}: Entry @ {1:x} contains an "
    1085             :                          "invalid CU index ({2}).\n",
    1086           1 :                          NI.getUnitOffset(), EntryID, CUIndex);
    1087           1 :       ++NumErrors;
    1088           3 :       continue;
    1089             :     }
    1090         307 :     uint32_t CUOffset = NI.getCUOffset(CUIndex);
    1091         307 :     uint64_t DIEOffset = CUOffset + *EntryOr->getDIEUnitOffset();
    1092         307 :     DWARFDie DIE = DCtx.getDIEForOffset(DIEOffset);
    1093           1 :     if (!DIE) {
    1094           3 :       error() << formatv("Name Index @ {0:x}: Entry @ {1:x} references a "
    1095             :                          "non-existing DIE @ {2:x}.\n",
    1096           1 :                          NI.getUnitOffset(), EntryID, DIEOffset);
    1097           1 :       ++NumErrors;
    1098           1 :       continue;
    1099             :     }
    1100         306 :     if (DIE.getDwarfUnit()->getOffset() != CUOffset) {
    1101           3 :       error() << formatv("Name Index @ {0:x}: Entry @ {1:x}: mismatched CU of "
    1102             :                          "DIE @ {2:x}: index - {3:x}; debug_info - {4:x}.\n",
    1103           1 :                          NI.getUnitOffset(), EntryID, DIEOffset, CUOffset,
    1104           1 :                          DIE.getDwarfUnit()->getOffset());
    1105           1 :       ++NumErrors;
    1106             :     }
    1107         612 :     if (DIE.getTag() != EntryOr->tag()) {
    1108           3 :       error() << formatv("Name Index @ {0:x}: Entry @ {1:x}: mismatched Tag of "
    1109             :                          "DIE @ {2:x}: index - {3}; debug_info - {4}.\n",
    1110           2 :                          NI.getUnitOffset(), EntryID, DIEOffset, EntryOr->tag(),
    1111             :                          DIE.getTag());
    1112           1 :       ++NumErrors;
    1113             :     }
    1114             : 
    1115         306 :     auto EntryNames = getNames(DIE);
    1116         306 :     if (!is_contained(EntryNames, Str)) {
    1117           6 :       error() << formatv("Name Index @ {0:x}: Entry @ {1:x}: mismatched Name "
    1118             :                          "of DIE @ {2:x}: index - {3}; debug_info - {4}.\n",
    1119           2 :                          NI.getUnitOffset(), EntryID, DIEOffset, Str,
    1120           4 :                          make_range(EntryNames.begin(), EntryNames.end()));
    1121           2 :       ++NumErrors;
    1122             :     }
    1123             :   }
    1124         894 :   handleAllErrors(EntryOr.takeError(),
    1125         297 :                   [&](const DWARFDebugNames::SentinelError &) {
    1126         297 :                     if (NumEntries > 0)
    1127             :                       return;
    1128           3 :                     error() << formatv("Name Index @ {0:x}: Name {1} ({2}) is "
    1129             :                                        "not associated with any entries.\n",
    1130           1 :                                        NI.getUnitOffset(), NTE.getIndex(), Str);
    1131           1 :                     ++NumErrors;
    1132             :                   },
    1133           1 :                   [&](const ErrorInfoBase &Info) {
    1134           1 :                     error()
    1135           1 :                         << formatv("Name Index @ {0:x}: Name {1} ({2}): {3}\n",
    1136           2 :                                    NI.getUnitOffset(), NTE.getIndex(), Str,
    1137           2 :                                    Info.message());
    1138           1 :                     ++NumErrors;
    1139           1 :                   });
    1140         298 :   return NumErrors;
    1141             : }
    1142             : 
    1143         275 : static bool isVariableIndexable(const DWARFDie &Die, DWARFContext &DCtx) {
    1144         550 :   Optional<DWARFFormValue> Location = Die.findRecursively(DW_AT_location);
    1145         275 :   if (!Location)
    1146             :     return false;
    1147             : 
    1148         275 :   auto ContainsInterestingOperators = [&](StringRef D) {
    1149         275 :     DWARFUnit *U = Die.getDwarfUnit();
    1150         275 :     DataExtractor Data(D, DCtx.isLittleEndian(), U->getAddressByteSize());
    1151             :     DWARFExpression Expression(Data, U->getVersion(), U->getAddressByteSize());
    1152             :     return any_of(Expression, [](DWARFExpression::Operation &Op) {
    1153         275 :       return !Op.isError() && (Op.getCode() == DW_OP_addr ||
    1154           1 :                                Op.getCode() == DW_OP_form_tls_address ||
    1155             :                                Op.getCode() == DW_OP_GNU_push_tls_address);
    1156         275 :     });
    1157         275 :   };
    1158             : 
    1159         275 :   if (Optional<ArrayRef<uint8_t>> Expr = Location->getAsBlock()) {
    1160             :     // Inlined location.
    1161         274 :     if (ContainsInterestingOperators(toStringRef(*Expr)))
    1162             :       return true;
    1163           1 :   } else if (Optional<uint64_t> Offset = Location->getAsSectionOffset()) {
    1164             :     // Location list.
    1165           1 :     if (const DWARFDebugLoc *DebugLoc = DCtx.getDebugLoc()) {
    1166           1 :       if (const DWARFDebugLoc::LocationList *LocList =
    1167           1 :               DebugLoc->getLocationListAtOffset(*Offset)) {
    1168           1 :         if (any_of(LocList->Entries, [&](const DWARFDebugLoc::Entry &E) {
    1169           2 :               return ContainsInterestingOperators({E.Loc.data(), E.Loc.size()});
    1170           1 :             }))
    1171             :           return true;
    1172             :       }
    1173             :     }
    1174             :   }
    1175           0 :   return false;
    1176             : }
    1177             : 
    1178         868 : unsigned DWARFVerifier::verifyNameIndexCompleteness(
    1179             :     const DWARFDie &Die, const DWARFDebugNames::NameIndex &NI) {
    1180             : 
    1181             :   // First check, if the Die should be indexed. The code follows the DWARF v5
    1182             :   // wording as closely as possible.
    1183             : 
    1184             :   // "All non-defining declarations (that is, debugging information entries
    1185             :   // with a DW_AT_declaration attribute) are excluded."
    1186         868 :   if (Die.find(DW_AT_declaration))
    1187             :     return 0;
    1188             : 
    1189             :   // "DW_TAG_namespace debugging information entries without a DW_AT_name
    1190             :   // attribute are included with the name “(anonymous namespace)”.
    1191             :   // All other debugging information entries without a DW_AT_name attribute
    1192             :   // are excluded."
    1193             :   // "If a subprogram or inlined subroutine is included, and has a
    1194             :   // DW_AT_linkage_name attribute, there will be an additional index entry for
    1195             :   // the linkage name."
    1196         868 :   auto EntryNames = getNames(Die);
    1197         868 :   if (EntryNames.empty())
    1198             :     return 0;
    1199             : 
    1200             :   // We deviate from the specification here, which says:
    1201             :   // "The name index must contain an entry for each debugging information entry
    1202             :   // that defines a named subprogram, label, variable, type, or namespace,
    1203             :   // subject to ..."
    1204             :   // Instead whitelisting all TAGs representing a "type" or a "subprogram", to
    1205             :   // make sure we catch any missing items, we instead blacklist all TAGs that we
    1206             :   // know shouldn't be indexed.
    1207         577 :   switch (Die.getTag()) {
    1208             :   // Compile unit has a name but it shouldn't be indexed.
    1209             :   case DW_TAG_compile_unit:
    1210             :     return 0;
    1211             : 
    1212             :   // Function and template parameters are not globally visible, so we shouldn't
    1213             :   // index them.
    1214             :   case DW_TAG_formal_parameter:
    1215             :   case DW_TAG_template_value_parameter:
    1216             :   case DW_TAG_template_type_parameter:
    1217             :   case DW_TAG_GNU_template_parameter_pack:
    1218             :   case DW_TAG_GNU_template_template_param:
    1219             :     return 0;
    1220             : 
    1221             :   // Object members aren't globally visible.
    1222             :   case DW_TAG_member:
    1223             :     return 0;
    1224             : 
    1225             :   // According to a strict reading of the specification, enumerators should not
    1226             :   // be indexed (and LLVM currently does not do that). However, this causes
    1227             :   // problems for the debuggers, so we may need to reconsider this.
    1228             :   case DW_TAG_enumerator:
    1229             :     return 0;
    1230             : 
    1231             :   // Imported declarations should not be indexed according to the specification
    1232             :   // and LLVM currently does not do that.
    1233             :   case DW_TAG_imported_declaration:
    1234             :     return 0;
    1235             : 
    1236             :   // "DW_TAG_subprogram, DW_TAG_inlined_subroutine, and DW_TAG_label debugging
    1237             :   // information entries without an address attribute (DW_AT_low_pc,
    1238             :   // DW_AT_high_pc, DW_AT_ranges, or DW_AT_entry_pc) are excluded."
    1239          11 :   case DW_TAG_subprogram:
    1240             :   case DW_TAG_inlined_subroutine:
    1241             :   case DW_TAG_label:
    1242          22 :     if (Die.findRecursively(
    1243          11 :             {DW_AT_low_pc, DW_AT_high_pc, DW_AT_ranges, DW_AT_entry_pc}))
    1244             :       break;
    1245             :     return 0;
    1246             : 
    1247             :   // "DW_TAG_variable debugging information entries with a DW_AT_location
    1248             :   // attribute that includes a DW_OP_addr or DW_OP_form_tls_address operator are
    1249             :   // included; otherwise, they are excluded."
    1250             :   //
    1251             :   // LLVM extension: We also add DW_OP_GNU_push_tls_address to this list.
    1252         275 :   case DW_TAG_variable:
    1253         275 :     if (isVariableIndexable(Die, DCtx))
    1254             :       break;
    1255             :     return 0;
    1256             : 
    1257             :   default:
    1258             :     break;
    1259             :   }
    1260             : 
    1261             :   // Now we know that our Die should be present in the Index. Let's check if
    1262             :   // that's the case.
    1263             :   unsigned NumErrors = 0;
    1264         906 :   uint64_t DieUnitOffset = Die.getOffset() - Die.getDwarfUnit()->getOffset();
    1265         922 :   for (StringRef Name : EntryNames) {
    1266         620 :     if (none_of(NI.equal_range(Name), [&](const DWARFDebugNames::Entry &E) {
    1267         318 :           return E.getDIEUnitOffset() == DieUnitOffset;
    1268             :         })) {
    1269          30 :       error() << formatv("Name Index @ {0:x}: Entry for DIE @ {1:x} ({2}) with "
    1270             :                          "name {3} missing.\n",
    1271          10 :                          NI.getUnitOffset(), Die.getOffset(), Die.getTag(),
    1272             :                          Name);
    1273          10 :       ++NumErrors;
    1274             :     }
    1275             :   }
    1276         302 :   return NumErrors;
    1277             : }
    1278             : 
    1279          22 : unsigned DWARFVerifier::verifyDebugNames(const DWARFSection &AccelSection,
    1280             :                                          const DataExtractor &StrData) {
    1281             :   unsigned NumErrors = 0;
    1282          22 :   DWARFDataExtractor AccelSectionData(DCtx.getDWARFObj(), AccelSection,
    1283          22 :                                       DCtx.isLittleEndian(), 0);
    1284          22 :   DWARFDebugNames AccelTable(AccelSectionData, StrData);
    1285             : 
    1286          22 :   OS << "Verifying .debug_names...\n";
    1287             : 
    1288             :   // This verifies that we can read individual name indices and their
    1289             :   // abbreviation tables.
    1290          44 :   if (Error E = AccelTable.extract()) {
    1291          20 :     error() << toString(std::move(E)) << '\n';
    1292             :     return 1;
    1293             :   }
    1294             : 
    1295          17 :   NumErrors += verifyDebugNamesCULists(AccelTable);
    1296          57 :   for (const auto &NI : AccelTable)
    1297          20 :     NumErrors += verifyNameIndexBuckets(NI, StrData);
    1298          57 :   for (const auto &NI : AccelTable)
    1299          20 :     NumErrors += verifyNameIndexAbbrevs(NI);
    1300             : 
    1301             :   // Don't attempt Entry validation if any of the previous checks found errors
    1302          17 :   if (NumErrors > 0)
    1303             :     return NumErrors;
    1304          36 :   for (const auto &NI : AccelTable)
    1305             :     for (DWARFDebugNames::NameTableEntry NTE : NI)
    1306         299 :       NumErrors += verifyNameIndexEntries(NI, NTE);
    1307             : 
    1308          12 :   if (NumErrors > 0)
    1309             :     return NumErrors;
    1310             : 
    1311         558 :   for (const std::unique_ptr<DWARFCompileUnit> &CU : DCtx.compile_units()) {
    1312         268 :     if (const DWARFDebugNames::NameIndex *NI =
    1313         268 :             AccelTable.getCUNameIndex(CU->getOffset())) {
    1314        1404 :       for (const DWARFDebugInfoEntry &Die : CU->dies())
    1315         868 :         NumErrors += verifyNameIndexCompleteness(DWARFDie(CU.get(), &Die), *NI);
    1316             :     }
    1317             :   }
    1318             :   return NumErrors;
    1319             : }
    1320             : 
    1321          65 : bool DWARFVerifier::handleAccelTables() {
    1322          65 :   const DWARFObject &D = DCtx.getDWARFObj();
    1323          65 :   DataExtractor StrData(D.getStringSection(), DCtx.isLittleEndian(), 0);
    1324             :   unsigned NumErrors = 0;
    1325         130 :   if (!D.getAppleNamesSection().Data.empty())
    1326             :     NumErrors +=
    1327          14 :         verifyAppleAccelTable(&D.getAppleNamesSection(), &StrData, ".apple_names");
    1328         130 :   if (!D.getAppleTypesSection().Data.empty())
    1329          12 :     NumErrors +=
    1330          12 :         verifyAppleAccelTable(&D.getAppleTypesSection(), &StrData, ".apple_types");
    1331         130 :   if (!D.getAppleNamespacesSection().Data.empty())
    1332          11 :     NumErrors += verifyAppleAccelTable(&D.getAppleNamespacesSection(), &StrData,
    1333             :                                   ".apple_namespaces");
    1334         130 :   if (!D.getAppleObjCSection().Data.empty())
    1335          11 :     NumErrors +=
    1336          11 :         verifyAppleAccelTable(&D.getAppleObjCSection(), &StrData, ".apple_objc");
    1337             : 
    1338         130 :   if (!D.getDebugNamesSection().Data.empty())
    1339          22 :     NumErrors += verifyDebugNames(D.getDebugNamesSection(), StrData);
    1340          65 :   return NumErrors == 0;
    1341             : }
    1342             : 
    1343         160 : raw_ostream &DWARFVerifier::error() const { return WithColor::error(OS); }
    1344             : 
    1345          34 : raw_ostream &DWARFVerifier::warn() const { return WithColor::warning(OS); }
    1346             : 
    1347          20 : raw_ostream &DWARFVerifier::note() const { return WithColor::note(OS); }

Generated by: LCOV version 1.13