lib/DebugInfo/DWARF/DWARFVerifier.cpp

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