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/IntervalMap.h"
10#include "llvm/ADT/STLExtras.h"
11#include "llvm/ADT/SmallSet.h"
12#include "llvm/BinaryFormat/Dwarf.h"
13#include "llvm/DebugInfo/DWARF/DWARFAbbreviationDeclaration.h"
14#include "llvm/DebugInfo/DWARF/DWARFAttribute.h"
15#include "llvm/DebugInfo/DWARF/DWARFCompileUnit.h"
16#include "llvm/DebugInfo/DWARF/DWARFContext.h"
17#include "llvm/DebugInfo/DWARF/DWARFDataExtractor.h"
18#include "llvm/DebugInfo/DWARF/DWARFDebugAbbrev.h"
19#include "llvm/DebugInfo/DWARF/DWARFDebugLine.h"
20#include "llvm/DebugInfo/DWARF/DWARFDebugLoc.h"
21#include "llvm/DebugInfo/DWARF/DWARFDie.h"
22#include "llvm/DebugInfo/DWARF/DWARFExpression.h"
23#include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
24#include "llvm/DebugInfo/DWARF/DWARFLocationExpression.h"
25#include "llvm/DebugInfo/DWARF/DWARFObject.h"
26#include "llvm/DebugInfo/DWARF/DWARFSection.h"
27#include "llvm/DebugInfo/DWARF/DWARFUnit.h"
28#include "llvm/Object/Error.h"
29#include "llvm/Support/DJB.h"
30#include "llvm/Support/Error.h"
31#include "llvm/Support/ErrorHandling.h"
32#include "llvm/Support/FormatVariadic.h"
33#include "llvm/Support/WithColor.h"
34#include "llvm/Support/raw_ostream.h"
35#include <map>
36#include <set>
37#include <vector>
38
39using namespace llvm;
40using namespace dwarf;
41using namespace object;
42
43namespace llvm {
44class DWARFDebugInfoEntry;
45}
46
47std::optional<DWARFAddressRange>
48DWARFVerifier::DieRangeInfo::insert(const DWARFAddressRange &R) {
49  auto Begin = Ranges.begin();
50  auto End = Ranges.end();
51  auto Pos = std::lower_bound(Begin, End, R);
52
53  if (Pos != End) {
54    DWARFAddressRange Range(*Pos);
55    if (Pos->merge(R))
56      return Range;
57  }
58  if (Pos != Begin) {
59    auto Iter = Pos - 1;
60    DWARFAddressRange Range(*Iter);
61    if (Iter->merge(R))
62      return Range;
63  }
64
65  Ranges.insert(Pos, R);
66  return std::nullopt;
67}
68
69DWARFVerifier::DieRangeInfo::die_range_info_iterator
70DWARFVerifier::DieRangeInfo::insert(const DieRangeInfo &RI) {
71  if (RI.Ranges.empty())
72    return Children.end();
73
74  auto End = Children.end();
75  auto Iter = Children.begin();
76  while (Iter != End) {
77    if (Iter->intersects(RI))
78      return Iter;
79    ++Iter;
80  }
81  Children.insert(RI);
82  return Children.end();
83}
84
85bool DWARFVerifier::DieRangeInfo::contains(const DieRangeInfo &RHS) const {
86  auto I1 = Ranges.begin(), E1 = Ranges.end();
87  auto I2 = RHS.Ranges.begin(), E2 = RHS.Ranges.end();
88  if (I2 == E2)
89    return true;
90
91  DWARFAddressRange R = *I2;
92  while (I1 != E1) {
93    bool Covered = I1->LowPC <= R.LowPC;
94    if (R.LowPC == R.HighPC || (Covered && R.HighPC <= I1->HighPC)) {
95      if (++I2 == E2)
96        return true;
97      R = *I2;
98      continue;
99    }
100    if (!Covered)
101      return false;
102    if (R.LowPC < I1->HighPC)
103      R.LowPC = I1->HighPC;
104    ++I1;
105  }
106  return false;
107}
108
109bool DWARFVerifier::DieRangeInfo::intersects(const DieRangeInfo &RHS) const {
110  auto I1 = Ranges.begin(), E1 = Ranges.end();
111  auto I2 = RHS.Ranges.begin(), E2 = RHS.Ranges.end();
112  while (I1 != E1 && I2 != E2) {
113    if (I1->intersects(*I2))
114      return true;
115    if (I1->LowPC < I2->LowPC)
116      ++I1;
117    else
118      ++I2;
119  }
120  return false;
121}
122
123bool DWARFVerifier::verifyUnitHeader(const DWARFDataExtractor DebugInfoData,
124                                     uint64_t *Offset, unsigned UnitIndex,
125                                     uint8_t &UnitType, bool &isUnitDWARF64) {
126  uint64_t AbbrOffset, Length;
127  uint8_t AddrSize = 0;
128  uint16_t Version;
129  bool Success = true;
130
131  bool ValidLength = false;
132  bool ValidVersion = false;
133  bool ValidAddrSize = false;
134  bool ValidType = true;
135  bool ValidAbbrevOffset = true;
136
137  uint64_t OffsetStart = *Offset;
138  DwarfFormat Format;
139  std::tie(Length, Format) = DebugInfoData.getInitialLength(Offset);
140  isUnitDWARF64 = Format == DWARF64;
141  Version = DebugInfoData.getU16(Offset);
142
143  if (Version >= 5) {
144    UnitType = DebugInfoData.getU8(Offset);
145    AddrSize = DebugInfoData.getU8(Offset);
146    AbbrOffset = isUnitDWARF64 ? DebugInfoData.getU64(Offset) : DebugInfoData.getU32(Offset);
147    ValidType = dwarf::isUnitType(UnitType);
148  } else {
149    UnitType = 0;
150    AbbrOffset = isUnitDWARF64 ? DebugInfoData.getU64(Offset) : DebugInfoData.getU32(Offset);
151    AddrSize = DebugInfoData.getU8(Offset);
152  }
153
154  Expected<const DWARFAbbreviationDeclarationSet *> AbbrevSetOrErr =
155      DCtx.getDebugAbbrev()->getAbbreviationDeclarationSet(AbbrOffset);
156  if (!AbbrevSetOrErr) {
157    ValidAbbrevOffset = false;
158    // FIXME: A problematic debug_abbrev section is reported below in the form
159    // of a `note:`. We should propagate this error there (or elsewhere) to
160    // avoid losing the specific problem with the debug_abbrev section.
161    consumeError(AbbrevSetOrErr.takeError());
162  }
163
164  ValidLength = DebugInfoData.isValidOffset(OffsetStart + Length + 3);
165  ValidVersion = DWARFContext::isSupportedVersion(Version);
166  ValidAddrSize = DWARFContext::isAddressSizeSupported(AddrSize);
167  if (!ValidLength || !ValidVersion || !ValidAddrSize || !ValidAbbrevOffset ||
168      !ValidType) {
169    Success = false;
170    error() << format("Units[%d] - start offset: 0x%08" PRIx64 " \n", UnitIndex,
171                      OffsetStart);
172    if (!ValidLength)
173      note() << "The length for this unit is too "
174                "large for the .debug_info provided.\n";
175    if (!ValidVersion)
176      note() << "The 16 bit unit header version is not valid.\n";
177    if (!ValidType)
178      note() << "The unit type encoding is not valid.\n";
179    if (!ValidAbbrevOffset)
180      note() << "The offset into the .debug_abbrev section is "
181                "not valid.\n";
182    if (!ValidAddrSize)
183      note() << "The address size is unsupported.\n";
184  }
185  *Offset = OffsetStart + Length + (isUnitDWARF64 ? 12 : 4);
186  return Success;
187}
188
189bool DWARFVerifier::verifyName(const DWARFDie &Die) {
190  // FIXME Add some kind of record of which DIE names have already failed and
191  // don't bother checking a DIE that uses an already failed DIE.
192
193  std::string ReconstructedName;
194  raw_string_ostream OS(ReconstructedName);
195  std::string OriginalFullName;
196  Die.getFullName(OS, &OriginalFullName);
197  OS.flush();
198  if (OriginalFullName.empty() || OriginalFullName == ReconstructedName)
199    return false;
200
201  error() << "Simplified template DW_AT_name could not be reconstituted:\n"
202          << formatv("         original: {0}\n"
203                     "    reconstituted: {1}\n",
204                     OriginalFullName, ReconstructedName);
205  dump(Die) << '\n';
206  dump(Die.getDwarfUnit()->getUnitDIE()) << '\n';
207  return true;
208}
209
210unsigned DWARFVerifier::verifyUnitContents(DWARFUnit &Unit,
211                                           ReferenceMap &UnitLocalReferences,
212                                           ReferenceMap &CrossUnitReferences) {
213  unsigned NumUnitErrors = 0;
214  unsigned NumDies = Unit.getNumDIEs();
215  for (unsigned I = 0; I < NumDies; ++I) {
216    auto Die = Unit.getDIEAtIndex(I);
217
218    if (Die.getTag() == DW_TAG_null)
219      continue;
220
221    for (auto AttrValue : Die.attributes()) {
222      NumUnitErrors += verifyDebugInfoAttribute(Die, AttrValue);
223      NumUnitErrors += verifyDebugInfoForm(Die, AttrValue, UnitLocalReferences,
224                                           CrossUnitReferences);
225    }
226
227    NumUnitErrors += verifyName(Die);
228
229    if (Die.hasChildren()) {
230      if (Die.getFirstChild().isValid() &&
231          Die.getFirstChild().getTag() == DW_TAG_null) {
232        warn() << dwarf::TagString(Die.getTag())
233               << " has DW_CHILDREN_yes but DIE has no children: ";
234        Die.dump(OS);
235      }
236    }
237
238    NumUnitErrors += verifyDebugInfoCallSite(Die);
239  }
240
241  DWARFDie Die = Unit.getUnitDIE(/* ExtractUnitDIEOnly = */ false);
242  if (!Die) {
243    error() << "Compilation unit without DIE.\n";
244    NumUnitErrors++;
245    return NumUnitErrors;
246  }
247
248  if (!dwarf::isUnitType(Die.getTag())) {
249    error() << "Compilation unit root DIE is not a unit DIE: "
250            << dwarf::TagString(Die.getTag()) << ".\n";
251    NumUnitErrors++;
252  }
253
254  uint8_t UnitType = Unit.getUnitType();
255  if (!DWARFUnit::isMatchingUnitTypeAndTag(UnitType, Die.getTag())) {
256    error() << "Compilation unit type (" << dwarf::UnitTypeString(UnitType)
257            << ") and root DIE (" << dwarf::TagString(Die.getTag())
258            << ") do not match.\n";
259    NumUnitErrors++;
260  }
261
262  //  According to DWARF Debugging Information Format Version 5,
263  //  3.1.2 Skeleton Compilation Unit Entries:
264  //  "A skeleton compilation unit has no children."
265  if (Die.getTag() == dwarf::DW_TAG_skeleton_unit && Die.hasChildren()) {
266    error() << "Skeleton compilation unit has children.\n";
267    NumUnitErrors++;
268  }
269
270  DieRangeInfo RI;
271  NumUnitErrors += verifyDieRanges(Die, RI);
272
273  return NumUnitErrors;
274}
275
276unsigned DWARFVerifier::verifyDebugInfoCallSite(const DWARFDie &Die) {
277  if (Die.getTag() != DW_TAG_call_site && Die.getTag() != DW_TAG_GNU_call_site)
278    return 0;
279
280  DWARFDie Curr = Die.getParent();
281  for (; Curr.isValid() && !Curr.isSubprogramDIE(); Curr = Die.getParent()) {
282    if (Curr.getTag() == DW_TAG_inlined_subroutine) {
283      error() << "Call site entry nested within inlined subroutine:";
284      Curr.dump(OS);
285      return 1;
286    }
287  }
288
289  if (!Curr.isValid()) {
290    error() << "Call site entry not nested within a valid subprogram:";
291    Die.dump(OS);
292    return 1;
293  }
294
295  std::optional<DWARFFormValue> CallAttr = Curr.find(
296      {DW_AT_call_all_calls, DW_AT_call_all_source_calls,
297       DW_AT_call_all_tail_calls, DW_AT_GNU_all_call_sites,
298       DW_AT_GNU_all_source_call_sites, DW_AT_GNU_all_tail_call_sites});
299  if (!CallAttr) {
300    error() << "Subprogram with call site entry has no DW_AT_call attribute:";
301    Curr.dump(OS);
302    Die.dump(OS, /*indent*/ 1);
303    return 1;
304  }
305
306  return 0;
307}
308
309unsigned DWARFVerifier::verifyAbbrevSection(const DWARFDebugAbbrev *Abbrev) {
310  if (!Abbrev)
311    return 0;
312
313  Expected<const DWARFAbbreviationDeclarationSet *> AbbrDeclsOrErr =
314      Abbrev->getAbbreviationDeclarationSet(0);
315  if (!AbbrDeclsOrErr) {
316    error() << toString(AbbrDeclsOrErr.takeError()) << "\n";
317    return 1;
318  }
319
320  const auto *AbbrDecls = *AbbrDeclsOrErr;
321  unsigned NumErrors = 0;
322  for (auto AbbrDecl : *AbbrDecls) {
323    SmallDenseSet<uint16_t> AttributeSet;
324    for (auto Attribute : AbbrDecl.attributes()) {
325      auto Result = AttributeSet.insert(Attribute.Attr);
326      if (!Result.second) {
327        error() << "Abbreviation declaration contains multiple "
328                << AttributeString(Attribute.Attr) << " attributes.\n";
329        AbbrDecl.dump(OS);
330        ++NumErrors;
331      }
332    }
333  }
334  return NumErrors;
335}
336
337bool DWARFVerifier::handleDebugAbbrev() {
338  OS << "Verifying .debug_abbrev...\n";
339
340  const DWARFObject &DObj = DCtx.getDWARFObj();
341  unsigned NumErrors = 0;
342  if (!DObj.getAbbrevSection().empty())
343    NumErrors += verifyAbbrevSection(DCtx.getDebugAbbrev());
344  if (!DObj.getAbbrevDWOSection().empty())
345    NumErrors += verifyAbbrevSection(DCtx.getDebugAbbrevDWO());
346
347  return NumErrors == 0;
348}
349
350unsigned DWARFVerifier::verifyUnits(const DWARFUnitVector &Units) {
351  unsigned NumDebugInfoErrors = 0;
352  ReferenceMap CrossUnitReferences;
353
354  unsigned Index = 1;
355  for (const auto &Unit : Units) {
356    OS << "Verifying unit: " << Index << " / " << Units.getNumUnits();
357    if (const char* Name = Unit->getUnitDIE(true).getShortName())
358      OS << ", \"" << Name << '\"';
359    OS << '\n';
360    OS.flush();
361    ReferenceMap UnitLocalReferences;
362    NumDebugInfoErrors +=
363        verifyUnitContents(*Unit, UnitLocalReferences, CrossUnitReferences);
364    NumDebugInfoErrors += verifyDebugInfoReferences(
365        UnitLocalReferences, [&](uint64_t Offset) { return Unit.get(); });
366    ++Index;
367  }
368
369  NumDebugInfoErrors += verifyDebugInfoReferences(
370      CrossUnitReferences, [&](uint64_t Offset) -> DWARFUnit * {
371        if (DWARFUnit *U = Units.getUnitForOffset(Offset))
372          return U;
373        return nullptr;
374      });
375
376  return NumDebugInfoErrors;
377}
378
379unsigned DWARFVerifier::verifyUnitSection(const DWARFSection &S) {
380  const DWARFObject &DObj = DCtx.getDWARFObj();
381  DWARFDataExtractor DebugInfoData(DObj, S, DCtx.isLittleEndian(), 0);
382  unsigned NumDebugInfoErrors = 0;
383  uint64_t Offset = 0, UnitIdx = 0;
384  uint8_t UnitType = 0;
385  bool isUnitDWARF64 = false;
386  bool isHeaderChainValid = true;
387  bool hasDIE = DebugInfoData.isValidOffset(Offset);
388  DWARFUnitVector TypeUnitVector;
389  DWARFUnitVector CompileUnitVector;
390  /// A map that tracks all references (converted absolute references) so we
391  /// can verify each reference points to a valid DIE and not an offset that
392  /// lies between to valid DIEs.
393  ReferenceMap CrossUnitReferences;
394  while (hasDIE) {
395    if (!verifyUnitHeader(DebugInfoData, &Offset, UnitIdx, UnitType,
396                          isUnitDWARF64)) {
397      isHeaderChainValid = false;
398      if (isUnitDWARF64)
399        break;
400    }
401    hasDIE = DebugInfoData.isValidOffset(Offset);
402    ++UnitIdx;
403  }
404  if (UnitIdx == 0 && !hasDIE) {
405    warn() << "Section is empty.\n";
406    isHeaderChainValid = true;
407  }
408  if (!isHeaderChainValid)
409    ++NumDebugInfoErrors;
410  return NumDebugInfoErrors;
411}
412
413unsigned DWARFVerifier::verifyIndex(StringRef Name,
414                                    DWARFSectionKind InfoColumnKind,
415                                    StringRef IndexStr) {
416  if (IndexStr.empty())
417    return 0;
418  OS << "Verifying " << Name << "...\n";
419  DWARFUnitIndex Index(InfoColumnKind);
420  DataExtractor D(IndexStr, DCtx.isLittleEndian(), 0);
421  if (!Index.parse(D))
422    return 1;
423  using MapType = IntervalMap<uint64_t, uint64_t>;
424  MapType::Allocator Alloc;
425  std::vector<std::unique_ptr<MapType>> Sections(Index.getColumnKinds().size());
426  for (const DWARFUnitIndex::Entry &E : Index.getRows()) {
427    uint64_t Sig = E.getSignature();
428    if (!E.getContributions())
429      continue;
430    for (auto E : enumerate(
431             InfoColumnKind == DW_SECT_INFO
432                 ? ArrayRef(E.getContributions(), Index.getColumnKinds().size())
433                 : ArrayRef(E.getContribution(), 1))) {
434      const DWARFUnitIndex::Entry::SectionContribution &SC = E.value();
435      int Col = E.index();
436      if (SC.getLength() == 0)
437        continue;
438      if (!Sections[Col])
439        Sections[Col] = std::make_unique<MapType>(Alloc);
440      auto &M = *Sections[Col];
441      auto I = M.find(SC.getOffset());
442      if (I != M.end() && I.start() < (SC.getOffset() + SC.getLength())) {
443        error() << llvm::formatv(
444            "overlapping index entries for entries {0:x16} "
445            "and {1:x16} for column {2}\n",
446            *I, Sig, toString(Index.getColumnKinds()[Col]));
447        return 1;
448      }
449      M.insert(SC.getOffset(), SC.getOffset() + SC.getLength() - 1, Sig);
450    }
451  }
452
453  return 0;
454}
455
456bool DWARFVerifier::handleDebugCUIndex() {
457  return verifyIndex(".debug_cu_index", DWARFSectionKind::DW_SECT_INFO,
458                     DCtx.getDWARFObj().getCUIndexSection()) == 0;
459}
460
461bool DWARFVerifier::handleDebugTUIndex() {
462  return verifyIndex(".debug_tu_index", DWARFSectionKind::DW_SECT_EXT_TYPES,
463                     DCtx.getDWARFObj().getTUIndexSection()) == 0;
464}
465
466bool DWARFVerifier::handleDebugInfo() {
467  const DWARFObject &DObj = DCtx.getDWARFObj();
468  unsigned NumErrors = 0;
469
470  OS << "Verifying .debug_info Unit Header Chain...\n";
471  DObj.forEachInfoSections([&](const DWARFSection &S) {
472    NumErrors += verifyUnitSection(S);
473  });
474
475  OS << "Verifying .debug_types Unit Header Chain...\n";
476  DObj.forEachTypesSections([&](const DWARFSection &S) {
477    NumErrors += verifyUnitSection(S);
478  });
479
480  OS << "Verifying non-dwo Units...\n";
481  NumErrors += verifyUnits(DCtx.getNormalUnitsVector());
482
483  OS << "Verifying dwo Units...\n";
484  NumErrors += verifyUnits(DCtx.getDWOUnitsVector());
485  return NumErrors == 0;
486}
487
488unsigned DWARFVerifier::verifyDieRanges(const DWARFDie &Die,
489                                        DieRangeInfo &ParentRI) {
490  unsigned NumErrors = 0;
491
492  if (!Die.isValid())
493    return NumErrors;
494
495  DWARFUnit *Unit = Die.getDwarfUnit();
496
497  auto RangesOrError = Die.getAddressRanges();
498  if (!RangesOrError) {
499    // FIXME: Report the error.
500    if (!Unit->isDWOUnit())
501      ++NumErrors;
502    llvm::consumeError(RangesOrError.takeError());
503    return NumErrors;
504  }
505
506  const DWARFAddressRangesVector &Ranges = RangesOrError.get();
507  // Build RI for this DIE and check that ranges within this DIE do not
508  // overlap.
509  DieRangeInfo RI(Die);
510
511  // TODO support object files better
512  //
513  // Some object file formats (i.e. non-MachO) support COMDAT.  ELF in
514  // particular does so by placing each function into a section.  The DWARF data
515  // for the function at that point uses a section relative DW_FORM_addrp for
516  // the DW_AT_low_pc and a DW_FORM_data4 for the offset as the DW_AT_high_pc.
517  // In such a case, when the Die is the CU, the ranges will overlap, and we
518  // will flag valid conflicting ranges as invalid.
519  //
520  // For such targets, we should read the ranges from the CU and partition them
521  // by the section id.  The ranges within a particular section should be
522  // disjoint, although the ranges across sections may overlap.  We would map
523  // the child die to the entity that it references and the section with which
524  // it is associated.  The child would then be checked against the range
525  // information for the associated section.
526  //
527  // For now, simply elide the range verification for the CU DIEs if we are
528  // processing an object file.
529
530  if (!IsObjectFile || IsMachOObject || Die.getTag() != DW_TAG_compile_unit) {
531    bool DumpDieAfterError = false;
532    for (const auto &Range : Ranges) {
533      if (!Range.valid()) {
534        ++NumErrors;
535        error() << "Invalid address range " << Range << "\n";
536        DumpDieAfterError = true;
537        continue;
538      }
539
540      // Verify that ranges don't intersect and also build up the DieRangeInfo
541      // address ranges. Don't break out of the loop below early, or we will
542      // think this DIE doesn't have all of the address ranges it is supposed
543      // to have. Compile units often have DW_AT_ranges that can contain one or
544      // more dead stripped address ranges which tend to all be at the same
545      // address: 0 or -1.
546      if (auto PrevRange = RI.insert(Range)) {
547        ++NumErrors;
548        error() << "DIE has overlapping ranges in DW_AT_ranges attribute: "
549                << *PrevRange << " and " << Range << '\n';
550        DumpDieAfterError = true;
551      }
552    }
553    if (DumpDieAfterError)
554      dump(Die, 2) << '\n';
555  }
556
557  // Verify that children don't intersect.
558  const auto IntersectingChild = ParentRI.insert(RI);
559  if (IntersectingChild != ParentRI.Children.end()) {
560    ++NumErrors;
561    error() << "DIEs have overlapping address ranges:";
562    dump(Die);
563    dump(IntersectingChild->Die) << '\n';
564  }
565
566  // Verify that ranges are contained within their parent.
567  bool ShouldBeContained = !RI.Ranges.empty() && !ParentRI.Ranges.empty() &&
568                           !(Die.getTag() == DW_TAG_subprogram &&
569                             ParentRI.Die.getTag() == DW_TAG_subprogram);
570  if (ShouldBeContained && !ParentRI.contains(RI)) {
571    ++NumErrors;
572    error() << "DIE address ranges are not contained in its parent's ranges:";
573    dump(ParentRI.Die);
574    dump(Die, 2) << '\n';
575  }
576
577  // Recursively check children.
578  for (DWARFDie Child : Die)
579    NumErrors += verifyDieRanges(Child, RI);
580
581  return NumErrors;
582}
583
584unsigned DWARFVerifier::verifyDebugInfoAttribute(const DWARFDie &Die,
585                                                 DWARFAttribute &AttrValue) {
586  unsigned NumErrors = 0;
587  auto ReportError = [&](const Twine &TitleMsg) {
588    ++NumErrors;
589    error() << TitleMsg << '\n';
590    dump(Die) << '\n';
591  };
592
593  const DWARFObject &DObj = DCtx.getDWARFObj();
594  DWARFUnit *U = Die.getDwarfUnit();
595  const auto Attr = AttrValue.Attr;
596  switch (Attr) {
597  case DW_AT_ranges:
598    // Make sure the offset in the DW_AT_ranges attribute is valid.
599    if (auto SectionOffset = AttrValue.Value.getAsSectionOffset()) {
600      unsigned DwarfVersion = U->getVersion();
601      const DWARFSection &RangeSection = DwarfVersion < 5
602                                             ? DObj.getRangesSection()
603                                             : DObj.getRnglistsSection();
604      if (U->isDWOUnit() && RangeSection.Data.empty())
605        break;
606      if (*SectionOffset >= RangeSection.Data.size())
607        ReportError(
608            "DW_AT_ranges offset is beyond " +
609            StringRef(DwarfVersion < 5 ? ".debug_ranges" : ".debug_rnglists") +
610            " bounds: " + llvm::formatv("{0:x8}", *SectionOffset));
611      break;
612    }
613    ReportError("DIE has invalid DW_AT_ranges encoding:");
614    break;
615  case DW_AT_stmt_list:
616    // Make sure the offset in the DW_AT_stmt_list attribute is valid.
617    if (auto SectionOffset = AttrValue.Value.getAsSectionOffset()) {
618      if (*SectionOffset >= U->getLineSection().Data.size())
619        ReportError("DW_AT_stmt_list offset is beyond .debug_line bounds: " +
620                    llvm::formatv("{0:x8}", *SectionOffset));
621      break;
622    }
623    ReportError("DIE has invalid DW_AT_stmt_list encoding:");
624    break;
625  case DW_AT_location: {
626    // FIXME: It might be nice if there's a way to walk location expressions
627    // without trying to resolve the address ranges - it'd be a more efficient
628    // API (since the API is currently unnecessarily resolving addresses for
629    // this use case which only wants to validate the expressions themselves) &
630    // then the expressions could be validated even if the addresses can't be
631    // resolved.
632    // That sort of API would probably look like a callback "for each
633    // expression" with some way to lazily resolve the address ranges when
634    // needed (& then the existing API used here could be built on top of that -
635    // using the callback API to build the data structure and return it).
636    if (Expected<std::vector<DWARFLocationExpression>> Loc =
637            Die.getLocations(DW_AT_location)) {
638      for (const auto &Entry : *Loc) {
639        DataExtractor Data(toStringRef(Entry.Expr), DCtx.isLittleEndian(), 0);
640        DWARFExpression Expression(Data, U->getAddressByteSize(),
641                                   U->getFormParams().Format);
642        bool Error =
643            any_of(Expression, [](const DWARFExpression::Operation &Op) {
644              return Op.isError();
645            });
646        if (Error || !Expression.verify(U))
647          ReportError("DIE contains invalid DWARF expression:");
648      }
649    } else if (Error Err = handleErrors(
650                   Loc.takeError(), [&](std::unique_ptr<ResolverError> E) {
651                     return U->isDWOUnit() ? Error::success()
652                                           : Error(std::move(E));
653                   }))
654      ReportError(toString(std::move(Err)));
655    break;
656  }
657  case DW_AT_specification:
658  case DW_AT_abstract_origin: {
659    if (auto ReferencedDie = Die.getAttributeValueAsReferencedDie(Attr)) {
660      auto DieTag = Die.getTag();
661      auto RefTag = ReferencedDie.getTag();
662      if (DieTag == RefTag)
663        break;
664      if (DieTag == DW_TAG_inlined_subroutine && RefTag == DW_TAG_subprogram)
665        break;
666      if (DieTag == DW_TAG_variable && RefTag == DW_TAG_member)
667        break;
668      // This might be reference to a function declaration.
669      if (DieTag == DW_TAG_GNU_call_site && RefTag == DW_TAG_subprogram)
670        break;
671      ReportError("DIE with tag " + TagString(DieTag) + " has " +
672                  AttributeString(Attr) +
673                  " that points to DIE with "
674                  "incompatible tag " +
675                  TagString(RefTag));
676    }
677    break;
678  }
679  case DW_AT_type: {
680    DWARFDie TypeDie = Die.getAttributeValueAsReferencedDie(DW_AT_type);
681    if (TypeDie && !isType(TypeDie.getTag())) {
682      ReportError("DIE has " + AttributeString(Attr) +
683                  " with incompatible tag " + TagString(TypeDie.getTag()));
684    }
685    break;
686  }
687  case DW_AT_call_file:
688  case DW_AT_decl_file: {
689    if (auto FileIdx = AttrValue.Value.getAsUnsignedConstant()) {
690      if (U->isDWOUnit() && !U->isTypeUnit())
691        break;
692      const auto *LT = U->getContext().getLineTableForUnit(U);
693      if (LT) {
694        if (!LT->hasFileAtIndex(*FileIdx)) {
695          bool IsZeroIndexed = LT->Prologue.getVersion() >= 5;
696          if (std::optional<uint64_t> LastFileIdx =
697                  LT->getLastValidFileIndex()) {
698            ReportError("DIE has " + AttributeString(Attr) +
699                        " with an invalid file index " +
700                        llvm::formatv("{0}", *FileIdx) +
701                        " (valid values are [" + (IsZeroIndexed ? "0-" : "1-") +
702                        llvm::formatv("{0}", *LastFileIdx) + "])");
703          } else {
704            ReportError("DIE has " + AttributeString(Attr) +
705                        " with an invalid file index " +
706                        llvm::formatv("{0}", *FileIdx) +
707                        " (the file table in the prologue is empty)");
708          }
709        }
710      } else {
711        ReportError("DIE has " + AttributeString(Attr) +
712                    " that references a file with index " +
713                    llvm::formatv("{0}", *FileIdx) +
714                    " and the compile unit has no line table");
715      }
716    } else {
717      ReportError("DIE has " + AttributeString(Attr) +
718                  " with invalid encoding");
719    }
720    break;
721  }
722  case DW_AT_call_line:
723  case DW_AT_decl_line: {
724    if (!AttrValue.Value.getAsUnsignedConstant()) {
725      ReportError("DIE has " + AttributeString(Attr) +
726                  " with invalid encoding");
727    }
728    break;
729  }
730  default:
731    break;
732  }
733  return NumErrors;
734}
735
736unsigned DWARFVerifier::verifyDebugInfoForm(const DWARFDie &Die,
737                                            DWARFAttribute &AttrValue,
738                                            ReferenceMap &LocalReferences,
739                                            ReferenceMap &CrossUnitReferences) {
740  auto DieCU = Die.getDwarfUnit();
741  unsigned NumErrors = 0;
742  const auto Form = AttrValue.Value.getForm();
743  switch (Form) {
744  case DW_FORM_ref1:
745  case DW_FORM_ref2:
746  case DW_FORM_ref4:
747  case DW_FORM_ref8:
748  case DW_FORM_ref_udata: {
749    // Verify all CU relative references are valid CU offsets.
750    std::optional<uint64_t> RefVal = AttrValue.Value.getAsReference();
751    assert(RefVal);
752    if (RefVal) {
753      auto CUSize = DieCU->getNextUnitOffset() - DieCU->getOffset();
754      auto CUOffset = AttrValue.Value.getRawUValue();
755      if (CUOffset >= CUSize) {
756        ++NumErrors;
757        error() << FormEncodingString(Form) << " CU offset "
758                << format("0x%08" PRIx64, CUOffset)
759                << " is invalid (must be less than CU size of "
760                << format("0x%08" PRIx64, CUSize) << "):\n";
761        Die.dump(OS, 0, DumpOpts);
762        dump(Die) << '\n';
763      } else {
764        // Valid reference, but we will verify it points to an actual
765        // DIE later.
766        LocalReferences[*RefVal].insert(Die.getOffset());
767      }
768    }
769    break;
770  }
771  case DW_FORM_ref_addr: {
772    // Verify all absolute DIE references have valid offsets in the
773    // .debug_info section.
774    std::optional<uint64_t> RefVal = AttrValue.Value.getAsReference();
775    assert(RefVal);
776    if (RefVal) {
777      if (*RefVal >= DieCU->getInfoSection().Data.size()) {
778        ++NumErrors;
779        error() << "DW_FORM_ref_addr offset beyond .debug_info "
780                   "bounds:\n";
781        dump(Die) << '\n';
782      } else {
783        // Valid reference, but we will verify it points to an actual
784        // DIE later.
785        CrossUnitReferences[*RefVal].insert(Die.getOffset());
786      }
787    }
788    break;
789  }
790  case DW_FORM_strp:
791  case DW_FORM_strx:
792  case DW_FORM_strx1:
793  case DW_FORM_strx2:
794  case DW_FORM_strx3:
795  case DW_FORM_strx4:
796  case DW_FORM_line_strp: {
797    if (Error E = AttrValue.Value.getAsCString().takeError()) {
798      ++NumErrors;
799      error() << toString(std::move(E)) << ":\n";
800      dump(Die) << '\n';
801    }
802    break;
803  }
804  default:
805    break;
806  }
807  return NumErrors;
808}
809
810unsigned DWARFVerifier::verifyDebugInfoReferences(
811    const ReferenceMap &References,
812    llvm::function_ref<DWARFUnit *(uint64_t)> GetUnitForOffset) {
813  auto GetDIEForOffset = [&](uint64_t Offset) {
814    if (DWARFUnit *U = GetUnitForOffset(Offset))
815      return U->getDIEForOffset(Offset);
816    return DWARFDie();
817  };
818  unsigned NumErrors = 0;
819  for (const std::pair<const uint64_t, std::set<uint64_t>> &Pair :
820       References) {
821    if (GetDIEForOffset(Pair.first))
822      continue;
823    ++NumErrors;
824    error() << "invalid DIE reference " << format("0x%08" PRIx64, Pair.first)
825            << ". Offset is in between DIEs:\n";
826    for (auto Offset : Pair.second)
827      dump(GetDIEForOffset(Offset)) << '\n';
828    OS << "\n";
829  }
830  return NumErrors;
831}
832
833void DWARFVerifier::verifyDebugLineStmtOffsets() {
834  std::map<uint64_t, DWARFDie> StmtListToDie;
835  for (const auto &CU : DCtx.compile_units()) {
836    auto Die = CU->getUnitDIE();
837    // Get the attribute value as a section offset. No need to produce an
838    // error here if the encoding isn't correct because we validate this in
839    // the .debug_info verifier.
840    auto StmtSectionOffset = toSectionOffset(Die.find(DW_AT_stmt_list));
841    if (!StmtSectionOffset)
842      continue;
843    const uint64_t LineTableOffset = *StmtSectionOffset;
844    auto LineTable = DCtx.getLineTableForUnit(CU.get());
845    if (LineTableOffset < DCtx.getDWARFObj().getLineSection().Data.size()) {
846      if (!LineTable) {
847        ++NumDebugLineErrors;
848        error() << ".debug_line[" << format("0x%08" PRIx64, LineTableOffset)
849                << "] was not able to be parsed for CU:\n";
850        dump(Die) << '\n';
851        continue;
852      }
853    } else {
854      // Make sure we don't get a valid line table back if the offset is wrong.
855      assert(LineTable == nullptr);
856      // Skip this line table as it isn't valid. No need to create an error
857      // here because we validate this in the .debug_info verifier.
858      continue;
859    }
860    auto Iter = StmtListToDie.find(LineTableOffset);
861    if (Iter != StmtListToDie.end()) {
862      ++NumDebugLineErrors;
863      error() << "two compile unit DIEs, "
864              << format("0x%08" PRIx64, Iter->second.getOffset()) << " and "
865              << format("0x%08" PRIx64, Die.getOffset())
866              << ", have the same DW_AT_stmt_list section offset:\n";
867      dump(Iter->second);
868      dump(Die) << '\n';
869      // Already verified this line table before, no need to do it again.
870      continue;
871    }
872    StmtListToDie[LineTableOffset] = Die;
873  }
874}
875
876void DWARFVerifier::verifyDebugLineRows() {
877  for (const auto &CU : DCtx.compile_units()) {
878    auto Die = CU->getUnitDIE();
879    auto LineTable = DCtx.getLineTableForUnit(CU.get());
880    // If there is no line table we will have created an error in the
881    // .debug_info verifier or in verifyDebugLineStmtOffsets().
882    if (!LineTable)
883      continue;
884
885    // Verify prologue.
886    bool isDWARF5 = LineTable->Prologue.getVersion() >= 5;
887    uint32_t MaxDirIndex = LineTable->Prologue.IncludeDirectories.size();
888    uint32_t MinFileIndex = isDWARF5 ? 0 : 1;
889    uint32_t FileIndex = MinFileIndex;
890    StringMap<uint16_t> FullPathMap;
891    for (const auto &FileName : LineTable->Prologue.FileNames) {
892      // Verify directory index.
893      if (FileName.DirIdx > MaxDirIndex) {
894        ++NumDebugLineErrors;
895        error() << ".debug_line["
896                << format("0x%08" PRIx64,
897                          *toSectionOffset(Die.find(DW_AT_stmt_list)))
898                << "].prologue.file_names[" << FileIndex
899                << "].dir_idx contains an invalid index: " << FileName.DirIdx
900                << "\n";
901      }
902
903      // Check file paths for duplicates.
904      std::string FullPath;
905      const bool HasFullPath = LineTable->getFileNameByIndex(
906          FileIndex, CU->getCompilationDir(),
907          DILineInfoSpecifier::FileLineInfoKind::AbsoluteFilePath, FullPath);
908      assert(HasFullPath && "Invalid index?");
909      (void)HasFullPath;
910      auto It = FullPathMap.find(FullPath);
911      if (It == FullPathMap.end())
912        FullPathMap[FullPath] = FileIndex;
913      else if (It->second != FileIndex) {
914        warn() << ".debug_line["
915               << format("0x%08" PRIx64,
916                         *toSectionOffset(Die.find(DW_AT_stmt_list)))
917               << "].prologue.file_names[" << FileIndex
918               << "] is a duplicate of file_names[" << It->second << "]\n";
919      }
920
921      FileIndex++;
922    }
923
924    // Verify rows.
925    uint64_t PrevAddress = 0;
926    uint32_t RowIndex = 0;
927    for (const auto &Row : LineTable->Rows) {
928      // Verify row address.
929      if (Row.Address.Address < PrevAddress) {
930        ++NumDebugLineErrors;
931        error() << ".debug_line["
932                << format("0x%08" PRIx64,
933                          *toSectionOffset(Die.find(DW_AT_stmt_list)))
934                << "] row[" << RowIndex
935                << "] decreases in address from previous row:\n";
936
937        DWARFDebugLine::Row::dumpTableHeader(OS, 0);
938        if (RowIndex > 0)
939          LineTable->Rows[RowIndex - 1].dump(OS);
940        Row.dump(OS);
941        OS << '\n';
942      }
943
944      // If the prologue contains no file names and the line table has only one
945      // row, do not verify the file index, this is a line table of an empty
946      // file with an end_sequence, but the DWARF standard sets the file number
947      // to 1 by default, otherwise verify file index.
948      if ((LineTable->Prologue.FileNames.size() ||
949           LineTable->Rows.size() != 1) &&
950          !LineTable->hasFileAtIndex(Row.File)) {
951        ++NumDebugLineErrors;
952        error() << ".debug_line["
953                << format("0x%08" PRIx64,
954                          *toSectionOffset(Die.find(DW_AT_stmt_list)))
955                << "][" << RowIndex << "] has invalid file index " << Row.File
956                << " (valid values are [" << MinFileIndex << ','
957                << LineTable->Prologue.FileNames.size()
958                << (isDWARF5 ? ")" : "]") << "):\n";
959        DWARFDebugLine::Row::dumpTableHeader(OS, 0);
960        Row.dump(OS);
961        OS << '\n';
962      }
963      if (Row.EndSequence)
964        PrevAddress = 0;
965      else
966        PrevAddress = Row.Address.Address;
967      ++RowIndex;
968    }
969  }
970}
971
972DWARFVerifier::DWARFVerifier(raw_ostream &S, DWARFContext &D,
973                             DIDumpOptions DumpOpts)
974    : OS(S), DCtx(D), DumpOpts(std::move(DumpOpts)), IsObjectFile(false),
975      IsMachOObject(false) {
976  if (const auto *F = DCtx.getDWARFObj().getFile()) {
977    IsObjectFile = F->isRelocatableObject();
978    IsMachOObject = F->isMachO();
979  }
980}
981
982bool DWARFVerifier::handleDebugLine() {
983  NumDebugLineErrors = 0;
984  OS << "Verifying .debug_line...\n";
985  verifyDebugLineStmtOffsets();
986  verifyDebugLineRows();
987  return NumDebugLineErrors == 0;
988}
989
990unsigned DWARFVerifier::verifyAppleAccelTable(const DWARFSection *AccelSection,
991                                              DataExtractor *StrData,
992                                              const char *SectionName) {
993  unsigned NumErrors = 0;
994  DWARFDataExtractor AccelSectionData(DCtx.getDWARFObj(), *AccelSection,
995                                      DCtx.isLittleEndian(), 0);
996  AppleAcceleratorTable AccelTable(AccelSectionData, *StrData);
997
998  OS << "Verifying " << SectionName << "...\n";
999
1000  // Verify that the fixed part of the header is not too short.
1001  if (!AccelSectionData.isValidOffset(AccelTable.getSizeHdr())) {
1002    error() << "Section is too small to fit a section header.\n";
1003    return 1;
1004  }
1005
1006  // Verify that the section is not too short.
1007  if (Error E = AccelTable.extract()) {
1008    error() << toString(std::move(E)) << '\n';
1009    return 1;
1010  }
1011
1012  // Verify that all buckets have a valid hash index or are empty.
1013  uint32_t NumBuckets = AccelTable.getNumBuckets();
1014  uint32_t NumHashes = AccelTable.getNumHashes();
1015
1016  uint64_t BucketsOffset =
1017      AccelTable.getSizeHdr() + AccelTable.getHeaderDataLength();
1018  uint64_t HashesBase = BucketsOffset + NumBuckets * 4;
1019  uint64_t OffsetsBase = HashesBase + NumHashes * 4;
1020  for (uint32_t BucketIdx = 0; BucketIdx < NumBuckets; ++BucketIdx) {
1021    uint32_t HashIdx = AccelSectionData.getU32(&BucketsOffset);
1022    if (HashIdx >= NumHashes && HashIdx != UINT32_MAX) {
1023      error() << format("Bucket[%d] has invalid hash index: %u.\n", BucketIdx,
1024                        HashIdx);
1025      ++NumErrors;
1026    }
1027  }
1028  uint32_t NumAtoms = AccelTable.getAtomsDesc().size();
1029  if (NumAtoms == 0) {
1030    error() << "No atoms: failed to read HashData.\n";
1031    return 1;
1032  }
1033  if (!AccelTable.validateForms()) {
1034    error() << "Unsupported form: failed to read HashData.\n";
1035    return 1;
1036  }
1037
1038  for (uint32_t HashIdx = 0; HashIdx < NumHashes; ++HashIdx) {
1039    uint64_t HashOffset = HashesBase + 4 * HashIdx;
1040    uint64_t DataOffset = OffsetsBase + 4 * HashIdx;
1041    uint32_t Hash = AccelSectionData.getU32(&HashOffset);
1042    uint64_t HashDataOffset = AccelSectionData.getU32(&DataOffset);
1043    if (!AccelSectionData.isValidOffsetForDataOfSize(HashDataOffset,
1044                                                     sizeof(uint64_t))) {
1045      error() << format("Hash[%d] has invalid HashData offset: "
1046                        "0x%08" PRIx64 ".\n",
1047                        HashIdx, HashDataOffset);
1048      ++NumErrors;
1049    }
1050
1051    uint64_t StrpOffset;
1052    uint64_t StringOffset;
1053    uint32_t StringCount = 0;
1054    uint64_t Offset;
1055    unsigned Tag;
1056    while ((StrpOffset = AccelSectionData.getU32(&HashDataOffset)) != 0) {
1057      const uint32_t NumHashDataObjects =
1058          AccelSectionData.getU32(&HashDataOffset);
1059      for (uint32_t HashDataIdx = 0; HashDataIdx < NumHashDataObjects;
1060           ++HashDataIdx) {
1061        std::tie(Offset, Tag) = AccelTable.readAtoms(&HashDataOffset);
1062        auto Die = DCtx.getDIEForOffset(Offset);
1063        if (!Die) {
1064          const uint32_t BucketIdx =
1065              NumBuckets ? (Hash % NumBuckets) : UINT32_MAX;
1066          StringOffset = StrpOffset;
1067          const char *Name = StrData->getCStr(&StringOffset);
1068          if (!Name)
1069            Name = "<NULL>";
1070
1071          error() << format(
1072              "%s Bucket[%d] Hash[%d] = 0x%08x "
1073              "Str[%u] = 0x%08" PRIx64 " DIE[%d] = 0x%08" PRIx64 " "
1074              "is not a valid DIE offset for \"%s\".\n",
1075              SectionName, BucketIdx, HashIdx, Hash, StringCount, StrpOffset,
1076              HashDataIdx, Offset, Name);
1077
1078          ++NumErrors;
1079          continue;
1080        }
1081        if ((Tag != dwarf::DW_TAG_null) && (Die.getTag() != Tag)) {
1082          error() << "Tag " << dwarf::TagString(Tag)
1083                  << " in accelerator table does not match Tag "
1084                  << dwarf::TagString(Die.getTag()) << " of DIE[" << HashDataIdx
1085                  << "].\n";
1086          ++NumErrors;
1087        }
1088      }
1089      ++StringCount;
1090    }
1091  }
1092  return NumErrors;
1093}
1094
1095unsigned
1096DWARFVerifier::verifyDebugNamesCULists(const DWARFDebugNames &AccelTable) {
1097  // A map from CU offset to the (first) Name Index offset which claims to index
1098  // this CU.
1099  DenseMap<uint64_t, uint64_t> CUMap;
1100  const uint64_t NotIndexed = std::numeric_limits<uint64_t>::max();
1101
1102  CUMap.reserve(DCtx.getNumCompileUnits());
1103  for (const auto &CU : DCtx.compile_units())
1104    CUMap[CU->getOffset()] = NotIndexed;
1105
1106  unsigned NumErrors = 0;
1107  for (const DWARFDebugNames::NameIndex &NI : AccelTable) {
1108    if (NI.getCUCount() == 0) {
1109      error() << formatv("Name Index @ {0:x} does not index any CU\n",
1110                         NI.getUnitOffset());
1111      ++NumErrors;
1112      continue;
1113    }
1114    for (uint32_t CU = 0, End = NI.getCUCount(); CU < End; ++CU) {
1115      uint64_t Offset = NI.getCUOffset(CU);
1116      auto Iter = CUMap.find(Offset);
1117
1118      if (Iter == CUMap.end()) {
1119        error() << formatv(
1120            "Name Index @ {0:x} references a non-existing CU @ {1:x}\n",
1121            NI.getUnitOffset(), Offset);
1122        ++NumErrors;
1123        continue;
1124      }
1125
1126      if (Iter->second != NotIndexed) {
1127        error() << formatv("Name Index @ {0:x} references a CU @ {1:x}, but "
1128                           "this CU is already indexed by Name Index @ {2:x}\n",
1129                           NI.getUnitOffset(), Offset, Iter->second);
1130        continue;
1131      }
1132      Iter->second = NI.getUnitOffset();
1133    }
1134  }
1135
1136  for (const auto &KV : CUMap) {
1137    if (KV.second == NotIndexed)
1138      warn() << formatv("CU @ {0:x} not covered by any Name Index\n", KV.first);
1139  }
1140
1141  return NumErrors;
1142}
1143
1144unsigned
1145DWARFVerifier::verifyNameIndexBuckets(const DWARFDebugNames::NameIndex &NI,
1146                                      const DataExtractor &StrData) {
1147  struct BucketInfo {
1148    uint32_t Bucket;
1149    uint32_t Index;
1150
1151    constexpr BucketInfo(uint32_t Bucket, uint32_t Index)
1152        : Bucket(Bucket), Index(Index) {}
1153    bool operator<(const BucketInfo &RHS) const { return Index < RHS.Index; }
1154  };
1155
1156  uint32_t NumErrors = 0;
1157  if (NI.getBucketCount() == 0) {
1158    warn() << formatv("Name Index @ {0:x} does not contain a hash table.\n",
1159                      NI.getUnitOffset());
1160    return NumErrors;
1161  }
1162
1163  // Build up a list of (Bucket, Index) pairs. We use this later to verify that
1164  // each Name is reachable from the appropriate bucket.
1165  std::vector<BucketInfo> BucketStarts;
1166  BucketStarts.reserve(NI.getBucketCount() + 1);
1167  for (uint32_t Bucket = 0, End = NI.getBucketCount(); Bucket < End; ++Bucket) {
1168    uint32_t Index = NI.getBucketArrayEntry(Bucket);
1169    if (Index > NI.getNameCount()) {
1170      error() << formatv("Bucket {0} of Name Index @ {1:x} contains invalid "
1171                         "value {2}. Valid range is [0, {3}].\n",
1172                         Bucket, NI.getUnitOffset(), Index, NI.getNameCount());
1173      ++NumErrors;
1174      continue;
1175    }
1176    if (Index > 0)
1177      BucketStarts.emplace_back(Bucket, Index);
1178  }
1179
1180  // If there were any buckets with invalid values, skip further checks as they
1181  // will likely produce many errors which will only confuse the actual root
1182  // problem.
1183  if (NumErrors > 0)
1184    return NumErrors;
1185
1186  // Sort the list in the order of increasing "Index" entries.
1187  array_pod_sort(BucketStarts.begin(), BucketStarts.end());
1188
1189  // Insert a sentinel entry at the end, so we can check that the end of the
1190  // table is covered in the loop below.
1191  BucketStarts.emplace_back(NI.getBucketCount(), NI.getNameCount() + 1);
1192
1193  // Loop invariant: NextUncovered is the (1-based) index of the first Name
1194  // which is not reachable by any of the buckets we processed so far (and
1195  // hasn't been reported as uncovered).
1196  uint32_t NextUncovered = 1;
1197  for (const BucketInfo &B : BucketStarts) {
1198    // Under normal circumstances B.Index be equal to NextUncovered, but it can
1199    // be less if a bucket points to names which are already known to be in some
1200    // bucket we processed earlier. In that case, we won't trigger this error,
1201    // but report the mismatched hash value error instead. (We know the hash
1202    // will not match because we have already verified that the name's hash
1203    // puts it into the previous bucket.)
1204    if (B.Index > NextUncovered) {
1205      error() << formatv("Name Index @ {0:x}: Name table entries [{1}, {2}] "
1206                         "are not covered by the hash table.\n",
1207                         NI.getUnitOffset(), NextUncovered, B.Index - 1);
1208      ++NumErrors;
1209    }
1210    uint32_t Idx = B.Index;
1211
1212    // The rest of the checks apply only to non-sentinel entries.
1213    if (B.Bucket == NI.getBucketCount())
1214      break;
1215
1216    // This triggers if a non-empty bucket points to a name with a mismatched
1217    // hash. Clients are likely to interpret this as an empty bucket, because a
1218    // mismatched hash signals the end of a bucket, but if this is indeed an
1219    // empty bucket, the producer should have signalled this by marking the
1220    // bucket as empty.
1221    uint32_t FirstHash = NI.getHashArrayEntry(Idx);
1222    if (FirstHash % NI.getBucketCount() != B.Bucket) {
1223      error() << formatv(
1224          "Name Index @ {0:x}: Bucket {1} is not empty but points to a "
1225          "mismatched hash value {2:x} (belonging to bucket {3}).\n",
1226          NI.getUnitOffset(), B.Bucket, FirstHash,
1227          FirstHash % NI.getBucketCount());
1228      ++NumErrors;
1229    }
1230
1231    // This find the end of this bucket and also verifies that all the hashes in
1232    // this bucket are correct by comparing the stored hashes to the ones we
1233    // compute ourselves.
1234    while (Idx <= NI.getNameCount()) {
1235      uint32_t Hash = NI.getHashArrayEntry(Idx);
1236      if (Hash % NI.getBucketCount() != B.Bucket)
1237        break;
1238
1239      const char *Str = NI.getNameTableEntry(Idx).getString();
1240      if (caseFoldingDjbHash(Str) != Hash) {
1241        error() << formatv("Name Index @ {0:x}: String ({1}) at index {2} "
1242                           "hashes to {3:x}, but "
1243                           "the Name Index hash is {4:x}\n",
1244                           NI.getUnitOffset(), Str, Idx,
1245                           caseFoldingDjbHash(Str), Hash);
1246        ++NumErrors;
1247      }
1248
1249      ++Idx;
1250    }
1251    NextUncovered = std::max(NextUncovered, Idx);
1252  }
1253  return NumErrors;
1254}
1255
1256unsigned DWARFVerifier::verifyNameIndexAttribute(
1257    const DWARFDebugNames::NameIndex &NI, const DWARFDebugNames::Abbrev &Abbr,
1258    DWARFDebugNames::AttributeEncoding AttrEnc) {
1259  StringRef FormName = dwarf::FormEncodingString(AttrEnc.Form);
1260  if (FormName.empty()) {
1261    error() << formatv("NameIndex @ {0:x}: Abbreviation {1:x}: {2} uses an "
1262                       "unknown form: {3}.\n",
1263                       NI.getUnitOffset(), Abbr.Code, AttrEnc.Index,
1264                       AttrEnc.Form);
1265    return 1;
1266  }
1267
1268  if (AttrEnc.Index == DW_IDX_type_hash) {
1269    if (AttrEnc.Form != dwarf::DW_FORM_data8) {
1270      error() << formatv(
1271          "NameIndex @ {0:x}: Abbreviation {1:x}: DW_IDX_type_hash "
1272          "uses an unexpected form {2} (should be {3}).\n",
1273          NI.getUnitOffset(), Abbr.Code, AttrEnc.Form, dwarf::DW_FORM_data8);
1274      return 1;
1275    }
1276    return 0;
1277  }
1278
1279  if (AttrEnc.Index == dwarf::DW_IDX_parent) {
1280    constexpr static auto AllowedForms = {dwarf::Form::DW_FORM_flag_present,
1281                                          dwarf::Form::DW_FORM_ref4};
1282    if (!is_contained(AllowedForms, AttrEnc.Form)) {
1283      error() << formatv("NameIndex @ {0:x}: Abbreviation {1:x}: DW_IDX_parent "
1284                         "uses an unexpected form {2} (should be "
1285                         "DW_FORM_ref4 or DW_FORM_flag_present).\n",
1286                         NI.getUnitOffset(), Abbr.Code, AttrEnc.Form);
1287      return 1;
1288    }
1289    return 0;
1290  }
1291
1292  // A list of known index attributes and their expected form classes.
1293  // DW_IDX_type_hash is handled specially in the check above, as it has a
1294  // specific form (not just a form class) we should expect.
1295  struct FormClassTable {
1296    dwarf::Index Index;
1297    DWARFFormValue::FormClass Class;
1298    StringLiteral ClassName;
1299  };
1300  static constexpr FormClassTable Table[] = {
1301      {dwarf::DW_IDX_compile_unit, DWARFFormValue::FC_Constant, {"constant"}},
1302      {dwarf::DW_IDX_type_unit, DWARFFormValue::FC_Constant, {"constant"}},
1303      {dwarf::DW_IDX_die_offset, DWARFFormValue::FC_Reference, {"reference"}},
1304  };
1305
1306  ArrayRef<FormClassTable> TableRef(Table);
1307  auto Iter = find_if(TableRef, [AttrEnc](const FormClassTable &T) {
1308    return T.Index == AttrEnc.Index;
1309  });
1310  if (Iter == TableRef.end()) {
1311    warn() << formatv("NameIndex @ {0:x}: Abbreviation {1:x} contains an "
1312                      "unknown index attribute: {2}.\n",
1313                      NI.getUnitOffset(), Abbr.Code, AttrEnc.Index);
1314    return 0;
1315  }
1316
1317  if (!DWARFFormValue(AttrEnc.Form).isFormClass(Iter->Class)) {
1318    error() << formatv("NameIndex @ {0:x}: Abbreviation {1:x}: {2} uses an "
1319                       "unexpected form {3} (expected form class {4}).\n",
1320                       NI.getUnitOffset(), Abbr.Code, AttrEnc.Index,
1321                       AttrEnc.Form, Iter->ClassName);
1322    return 1;
1323  }
1324  return 0;
1325}
1326
1327unsigned
1328DWARFVerifier::verifyNameIndexAbbrevs(const DWARFDebugNames::NameIndex &NI) {
1329  if (NI.getLocalTUCount() + NI.getForeignTUCount() > 0) {
1330    warn() << formatv("Name Index @ {0:x}: Verifying indexes of type units is "
1331                      "not currently supported.\n",
1332                      NI.getUnitOffset());
1333    return 0;
1334  }
1335
1336  unsigned NumErrors = 0;
1337  for (const auto &Abbrev : NI.getAbbrevs()) {
1338    StringRef TagName = dwarf::TagString(Abbrev.Tag);
1339    if (TagName.empty()) {
1340      warn() << formatv("NameIndex @ {0:x}: Abbreviation {1:x} references an "
1341                        "unknown tag: {2}.\n",
1342                        NI.getUnitOffset(), Abbrev.Code, Abbrev.Tag);
1343    }
1344    SmallSet<unsigned, 5> Attributes;
1345    for (const auto &AttrEnc : Abbrev.Attributes) {
1346      if (!Attributes.insert(AttrEnc.Index).second) {
1347        error() << formatv("NameIndex @ {0:x}: Abbreviation {1:x} contains "
1348                           "multiple {2} attributes.\n",
1349                           NI.getUnitOffset(), Abbrev.Code, AttrEnc.Index);
1350        ++NumErrors;
1351        continue;
1352      }
1353      NumErrors += verifyNameIndexAttribute(NI, Abbrev, AttrEnc);
1354    }
1355
1356    if (NI.getCUCount() > 1 && !Attributes.count(dwarf::DW_IDX_compile_unit)) {
1357      error() << formatv("NameIndex @ {0:x}: Indexing multiple compile units "
1358                         "and abbreviation {1:x} has no {2} attribute.\n",
1359                         NI.getUnitOffset(), Abbrev.Code,
1360                         dwarf::DW_IDX_compile_unit);
1361      ++NumErrors;
1362    }
1363    if (!Attributes.count(dwarf::DW_IDX_die_offset)) {
1364      error() << formatv(
1365          "NameIndex @ {0:x}: Abbreviation {1:x} has no {2} attribute.\n",
1366          NI.getUnitOffset(), Abbrev.Code, dwarf::DW_IDX_die_offset);
1367      ++NumErrors;
1368    }
1369  }
1370  return NumErrors;
1371}
1372
1373static SmallVector<std::string, 3> getNames(const DWARFDie &DIE,
1374                                            bool IncludeStrippedTemplateNames,
1375                                            bool IncludeObjCNames = true,
1376                                            bool IncludeLinkageName = true) {
1377  SmallVector<std::string, 3> Result;
1378  if (const char *Str = DIE.getShortName()) {
1379    StringRef Name(Str);
1380    Result.emplace_back(Name);
1381    if (IncludeStrippedTemplateNames) {
1382      if (std::optional<StringRef> StrippedName =
1383              StripTemplateParameters(Result.back()))
1384        // Convert to std::string and push; emplacing the StringRef may trigger
1385        // a vector resize which may destroy the StringRef memory.
1386        Result.push_back(StrippedName->str());
1387    }
1388
1389    if (IncludeObjCNames) {
1390      if (std::optional<ObjCSelectorNames> ObjCNames =
1391              getObjCNamesIfSelector(Name)) {
1392        Result.emplace_back(ObjCNames->ClassName);
1393        Result.emplace_back(ObjCNames->Selector);
1394        if (ObjCNames->ClassNameNoCategory)
1395          Result.emplace_back(*ObjCNames->ClassNameNoCategory);
1396        if (ObjCNames->MethodNameNoCategory)
1397          Result.push_back(std::move(*ObjCNames->MethodNameNoCategory));
1398      }
1399    }
1400  } else if (DIE.getTag() == dwarf::DW_TAG_namespace)
1401    Result.emplace_back("(anonymous namespace)");
1402
1403  if (IncludeLinkageName) {
1404    if (const char *Str = DIE.getLinkageName())
1405      Result.emplace_back(Str);
1406  }
1407
1408  return Result;
1409}
1410
1411unsigned DWARFVerifier::verifyNameIndexEntries(
1412    const DWARFDebugNames::NameIndex &NI,
1413    const DWARFDebugNames::NameTableEntry &NTE) {
1414  // Verifying type unit indexes not supported.
1415  if (NI.getLocalTUCount() + NI.getForeignTUCount() > 0)
1416    return 0;
1417
1418  const char *CStr = NTE.getString();
1419  if (!CStr) {
1420    error() << formatv(
1421        "Name Index @ {0:x}: Unable to get string associated with name {1}.\n",
1422        NI.getUnitOffset(), NTE.getIndex());
1423    return 1;
1424  }
1425  StringRef Str(CStr);
1426
1427  unsigned NumErrors = 0;
1428  unsigned NumEntries = 0;
1429  uint64_t EntryID = NTE.getEntryOffset();
1430  uint64_t NextEntryID = EntryID;
1431  Expected<DWARFDebugNames::Entry> EntryOr = NI.getEntry(&NextEntryID);
1432  for (; EntryOr; ++NumEntries, EntryID = NextEntryID,
1433                                EntryOr = NI.getEntry(&NextEntryID)) {
1434    uint32_t CUIndex = *EntryOr->getCUIndex();
1435    if (CUIndex > NI.getCUCount()) {
1436      error() << formatv("Name Index @ {0:x}: Entry @ {1:x} contains an "
1437                         "invalid CU index ({2}).\n",
1438                         NI.getUnitOffset(), EntryID, CUIndex);
1439      ++NumErrors;
1440      continue;
1441    }
1442    uint64_t CUOffset = NI.getCUOffset(CUIndex);
1443    uint64_t DIEOffset = CUOffset + *EntryOr->getDIEUnitOffset();
1444    DWARFDie DIE = DCtx.getDIEForOffset(DIEOffset);
1445    if (!DIE) {
1446      error() << formatv("Name Index @ {0:x}: Entry @ {1:x} references a "
1447                         "non-existing DIE @ {2:x}.\n",
1448                         NI.getUnitOffset(), EntryID, DIEOffset);
1449      ++NumErrors;
1450      continue;
1451    }
1452    if (DIE.getDwarfUnit()->getOffset() != CUOffset) {
1453      error() << formatv("Name Index @ {0:x}: Entry @ {1:x}: mismatched CU of "
1454                         "DIE @ {2:x}: index - {3:x}; debug_info - {4:x}.\n",
1455                         NI.getUnitOffset(), EntryID, DIEOffset, CUOffset,
1456                         DIE.getDwarfUnit()->getOffset());
1457      ++NumErrors;
1458    }
1459    if (DIE.getTag() != EntryOr->tag()) {
1460      error() << formatv("Name Index @ {0:x}: Entry @ {1:x}: mismatched Tag of "
1461                         "DIE @ {2:x}: index - {3}; debug_info - {4}.\n",
1462                         NI.getUnitOffset(), EntryID, DIEOffset, EntryOr->tag(),
1463                         DIE.getTag());
1464      ++NumErrors;
1465    }
1466
1467    // We allow an extra name for functions: their name without any template
1468    // parameters.
1469    auto IncludeStrippedTemplateNames =
1470        DIE.getTag() == DW_TAG_subprogram ||
1471        DIE.getTag() == DW_TAG_inlined_subroutine;
1472    auto EntryNames = getNames(DIE, IncludeStrippedTemplateNames);
1473    if (!is_contained(EntryNames, Str)) {
1474      error() << formatv("Name Index @ {0:x}: Entry @ {1:x}: mismatched Name "
1475                         "of DIE @ {2:x}: index - {3}; debug_info - {4}.\n",
1476                         NI.getUnitOffset(), EntryID, DIEOffset, Str,
1477                         make_range(EntryNames.begin(), EntryNames.end()));
1478      ++NumErrors;
1479    }
1480  }
1481  handleAllErrors(EntryOr.takeError(),
1482                  [&](const DWARFDebugNames::SentinelError &) {
1483                    if (NumEntries > 0)
1484                      return;
1485                    error() << formatv("Name Index @ {0:x}: Name {1} ({2}) is "
1486                                       "not associated with any entries.\n",
1487                                       NI.getUnitOffset(), NTE.getIndex(), Str);
1488                    ++NumErrors;
1489                  },
1490                  [&](const ErrorInfoBase &Info) {
1491                    error()
1492                        << formatv("Name Index @ {0:x}: Name {1} ({2}): {3}\n",
1493                                   NI.getUnitOffset(), NTE.getIndex(), Str,
1494                                   Info.message());
1495                    ++NumErrors;
1496                  });
1497  return NumErrors;
1498}
1499
1500static bool isVariableIndexable(const DWARFDie &Die, DWARFContext &DCtx) {
1501  Expected<std::vector<DWARFLocationExpression>> Loc =
1502      Die.getLocations(DW_AT_location);
1503  if (!Loc) {
1504    consumeError(Loc.takeError());
1505    return false;
1506  }
1507  DWARFUnit *U = Die.getDwarfUnit();
1508  for (const auto &Entry : *Loc) {
1509    DataExtractor Data(toStringRef(Entry.Expr), DCtx.isLittleEndian(),
1510                       U->getAddressByteSize());
1511    DWARFExpression Expression(Data, U->getAddressByteSize(),
1512                               U->getFormParams().Format);
1513    bool IsInteresting =
1514        any_of(Expression, [](const DWARFExpression::Operation &Op) {
1515          return !Op.isError() && (Op.getCode() == DW_OP_addr ||
1516                                   Op.getCode() == DW_OP_form_tls_address ||
1517                                   Op.getCode() == DW_OP_GNU_push_tls_address);
1518        });
1519    if (IsInteresting)
1520      return true;
1521  }
1522  return false;
1523}
1524
1525unsigned DWARFVerifier::verifyNameIndexCompleteness(
1526    const DWARFDie &Die, const DWARFDebugNames::NameIndex &NI) {
1527
1528  // First check, if the Die should be indexed. The code follows the DWARF v5
1529  // wording as closely as possible.
1530
1531  // "All non-defining declarations (that is, debugging information entries
1532  // with a DW_AT_declaration attribute) are excluded."
1533  if (Die.find(DW_AT_declaration))
1534    return 0;
1535
1536  // "DW_TAG_namespace debugging information entries without a DW_AT_name
1537  // attribute are included with the name ���(anonymous namespace)���.
1538  // All other debugging information entries without a DW_AT_name attribute
1539  // are excluded."
1540  // "If a subprogram or inlined subroutine is included, and has a
1541  // DW_AT_linkage_name attribute, there will be an additional index entry for
1542  // the linkage name."
1543  auto IncludeLinkageName = Die.getTag() == DW_TAG_subprogram ||
1544                            Die.getTag() == DW_TAG_inlined_subroutine;
1545  // We *allow* stripped template names / ObjectiveC names as extra entries into
1546  // the table, but we don't *require* them to pass the completeness test.
1547  auto IncludeStrippedTemplateNames = false;
1548  auto IncludeObjCNames = false;
1549  auto EntryNames = getNames(Die, IncludeStrippedTemplateNames,
1550                             IncludeObjCNames, IncludeLinkageName);
1551  if (EntryNames.empty())
1552    return 0;
1553
1554  // We deviate from the specification here, which says:
1555  // "The name index must contain an entry for each debugging information entry
1556  // that defines a named subprogram, label, variable, type, or namespace,
1557  // subject to ..."
1558  // Explicitly exclude all TAGs that we know shouldn't be indexed.
1559  switch (Die.getTag()) {
1560  // Compile units and modules have names but shouldn't be indexed.
1561  case DW_TAG_compile_unit:
1562  case DW_TAG_module:
1563    return 0;
1564
1565  // Function and template parameters are not globally visible, so we shouldn't
1566  // index them.
1567  case DW_TAG_formal_parameter:
1568  case DW_TAG_template_value_parameter:
1569  case DW_TAG_template_type_parameter:
1570  case DW_TAG_GNU_template_parameter_pack:
1571  case DW_TAG_GNU_template_template_param:
1572    return 0;
1573
1574  // Object members aren't globally visible.
1575  case DW_TAG_member:
1576    return 0;
1577
1578  // According to a strict reading of the specification, enumerators should not
1579  // be indexed (and LLVM currently does not do that). However, this causes
1580  // problems for the debuggers, so we may need to reconsider this.
1581  case DW_TAG_enumerator:
1582    return 0;
1583
1584  // Imported declarations should not be indexed according to the specification
1585  // and LLVM currently does not do that.
1586  case DW_TAG_imported_declaration:
1587    return 0;
1588
1589  // "DW_TAG_subprogram, DW_TAG_inlined_subroutine, and DW_TAG_label debugging
1590  // information entries without an address attribute (DW_AT_low_pc,
1591  // DW_AT_high_pc, DW_AT_ranges, or DW_AT_entry_pc) are excluded."
1592  case DW_TAG_subprogram:
1593  case DW_TAG_inlined_subroutine:
1594  case DW_TAG_label:
1595    if (Die.findRecursively(
1596            {DW_AT_low_pc, DW_AT_high_pc, DW_AT_ranges, DW_AT_entry_pc}))
1597      break;
1598    return 0;
1599
1600  // "DW_TAG_variable debugging information entries with a DW_AT_location
1601  // attribute that includes a DW_OP_addr or DW_OP_form_tls_address operator are
1602  // included; otherwise, they are excluded."
1603  //
1604  // LLVM extension: We also add DW_OP_GNU_push_tls_address to this list.
1605  case DW_TAG_variable:
1606    if (isVariableIndexable(Die, DCtx))
1607      break;
1608    return 0;
1609
1610  default:
1611    break;
1612  }
1613
1614  // Now we know that our Die should be present in the Index. Let's check if
1615  // that's the case.
1616  unsigned NumErrors = 0;
1617  uint64_t DieUnitOffset = Die.getOffset() - Die.getDwarfUnit()->getOffset();
1618  for (StringRef Name : EntryNames) {
1619    if (none_of(NI.equal_range(Name), [&](const DWARFDebugNames::Entry &E) {
1620          return E.getDIEUnitOffset() == DieUnitOffset;
1621        })) {
1622      error() << formatv("Name Index @ {0:x}: Entry for DIE @ {1:x} ({2}) with "
1623                         "name {3} missing.\n",
1624                         NI.getUnitOffset(), Die.getOffset(), Die.getTag(),
1625                         Name);
1626      ++NumErrors;
1627    }
1628  }
1629  return NumErrors;
1630}
1631
1632unsigned DWARFVerifier::verifyDebugNames(const DWARFSection &AccelSection,
1633                                         const DataExtractor &StrData) {
1634  unsigned NumErrors = 0;
1635  DWARFDataExtractor AccelSectionData(DCtx.getDWARFObj(), AccelSection,
1636                                      DCtx.isLittleEndian(), 0);
1637  DWARFDebugNames AccelTable(AccelSectionData, StrData);
1638
1639  OS << "Verifying .debug_names...\n";
1640
1641  // This verifies that we can read individual name indices and their
1642  // abbreviation tables.
1643  if (Error E = AccelTable.extract()) {
1644    error() << toString(std::move(E)) << '\n';
1645    return 1;
1646  }
1647
1648  NumErrors += verifyDebugNamesCULists(AccelTable);
1649  for (const auto &NI : AccelTable)
1650    NumErrors += verifyNameIndexBuckets(NI, StrData);
1651  for (const auto &NI : AccelTable)
1652    NumErrors += verifyNameIndexAbbrevs(NI);
1653
1654  // Don't attempt Entry validation if any of the previous checks found errors
1655  if (NumErrors > 0)
1656    return NumErrors;
1657  for (const auto &NI : AccelTable)
1658    for (const DWARFDebugNames::NameTableEntry &NTE : NI)
1659      NumErrors += verifyNameIndexEntries(NI, NTE);
1660
1661  if (NumErrors > 0)
1662    return NumErrors;
1663
1664  for (const std::unique_ptr<DWARFUnit> &U : DCtx.compile_units()) {
1665    if (const DWARFDebugNames::NameIndex *NI =
1666            AccelTable.getCUNameIndex(U->getOffset())) {
1667      auto *CU = cast<DWARFCompileUnit>(U.get());
1668      for (const DWARFDebugInfoEntry &Die : CU->dies())
1669        NumErrors += verifyNameIndexCompleteness(DWARFDie(CU, &Die), *NI);
1670    }
1671  }
1672  return NumErrors;
1673}
1674
1675bool DWARFVerifier::handleAccelTables() {
1676  const DWARFObject &D = DCtx.getDWARFObj();
1677  DataExtractor StrData(D.getStrSection(), DCtx.isLittleEndian(), 0);
1678  unsigned NumErrors = 0;
1679  if (!D.getAppleNamesSection().Data.empty())
1680    NumErrors += verifyAppleAccelTable(&D.getAppleNamesSection(), &StrData,
1681                                       ".apple_names");
1682  if (!D.getAppleTypesSection().Data.empty())
1683    NumErrors += verifyAppleAccelTable(&D.getAppleTypesSection(), &StrData,
1684                                       ".apple_types");
1685  if (!D.getAppleNamespacesSection().Data.empty())
1686    NumErrors += verifyAppleAccelTable(&D.getAppleNamespacesSection(), &StrData,
1687                                       ".apple_namespaces");
1688  if (!D.getAppleObjCSection().Data.empty())
1689    NumErrors += verifyAppleAccelTable(&D.getAppleObjCSection(), &StrData,
1690                                       ".apple_objc");
1691
1692  if (!D.getNamesSection().Data.empty())
1693    NumErrors += verifyDebugNames(D.getNamesSection(), StrData);
1694  return NumErrors == 0;
1695}
1696
1697bool DWARFVerifier::handleDebugStrOffsets() {
1698  OS << "Verifying .debug_str_offsets...\n";
1699  const DWARFObject &DObj = DCtx.getDWARFObj();
1700  bool Success = true;
1701  Success &= verifyDebugStrOffsets(
1702      ".debug_str_offsets.dwo", DObj.getStrOffsetsDWOSection(),
1703      DObj.getStrDWOSection(), &DWARFObject::forEachInfoDWOSections);
1704  Success &= verifyDebugStrOffsets(
1705      ".debug_str_offsets", DObj.getStrOffsetsSection(), DObj.getStrSection(),
1706      &DWARFObject::forEachInfoSections);
1707  return Success;
1708}
1709
1710bool DWARFVerifier::verifyDebugStrOffsets(
1711    StringRef SectionName, const DWARFSection &Section, StringRef StrData,
1712    void (DWARFObject::*VisitInfoSections)(
1713        function_ref<void(const DWARFSection &)>) const) {
1714  const DWARFObject &DObj = DCtx.getDWARFObj();
1715  uint16_t InfoVersion = 0;
1716  DwarfFormat InfoFormat = DwarfFormat::DWARF32;
1717  (DObj.*VisitInfoSections)([&](const DWARFSection &S) {
1718    if (InfoVersion)
1719      return;
1720    DWARFDataExtractor DebugInfoData(DObj, S, DCtx.isLittleEndian(), 0);
1721    uint64_t Offset = 0;
1722    InfoFormat = DebugInfoData.getInitialLength(&Offset).second;
1723    InfoVersion = DebugInfoData.getU16(&Offset);
1724  });
1725
1726  DWARFDataExtractor DA(DObj, Section, DCtx.isLittleEndian(), 0);
1727
1728  DataExtractor::Cursor C(0);
1729  uint64_t NextUnit = 0;
1730  bool Success = true;
1731  while (C.seek(NextUnit), C.tell() < DA.getData().size()) {
1732    DwarfFormat Format;
1733    uint64_t Length;
1734    uint64_t StartOffset = C.tell();
1735    if (InfoVersion == 4) {
1736      Format = InfoFormat;
1737      Length = DA.getData().size();
1738      NextUnit = C.tell() + Length;
1739    } else {
1740      std::tie(Length, Format) = DA.getInitialLength(C);
1741      if (!C)
1742        break;
1743      if (C.tell() + Length > DA.getData().size()) {
1744        error() << formatv(
1745            "{0}: contribution {1:X}: length exceeds available space "
1746            "(contribution "
1747            "offset ({1:X}) + length field space ({2:X}) + length ({3:X}) == "
1748            "{4:X} > section size {5:X})\n",
1749            SectionName, StartOffset, C.tell() - StartOffset, Length,
1750            C.tell() + Length, DA.getData().size());
1751        Success = false;
1752        // Nothing more to do - no other contributions to try.
1753        break;
1754      }
1755      NextUnit = C.tell() + Length;
1756      uint8_t Version = DA.getU16(C);
1757      if (C && Version != 5) {
1758        error() << formatv("{0}: contribution {1:X}: invalid version {2}\n",
1759                           SectionName, StartOffset, Version);
1760        Success = false;
1761        // Can't parse the rest of this contribution, since we don't know the
1762        // version, but we can pick up with the next contribution.
1763        continue;
1764      }
1765      (void)DA.getU16(C); // padding
1766    }
1767    uint64_t OffsetByteSize = getDwarfOffsetByteSize(Format);
1768    DA.setAddressSize(OffsetByteSize);
1769    uint64_t Remainder = (Length - 4) % OffsetByteSize;
1770    if (Remainder != 0) {
1771      error() << formatv(
1772          "{0}: contribution {1:X}: invalid length ((length ({2:X}) "
1773          "- header (0x4)) % offset size {3:X} == {4:X} != 0)\n",
1774          SectionName, StartOffset, Length, OffsetByteSize, Remainder);
1775      Success = false;
1776    }
1777    for (uint64_t Index = 0; C && C.tell() + OffsetByteSize <= NextUnit; ++Index) {
1778      uint64_t OffOff = C.tell();
1779      uint64_t StrOff = DA.getAddress(C);
1780      // check StrOff refers to the start of a string
1781      if (StrOff == 0)
1782        continue;
1783      if (StrData.size() <= StrOff) {
1784        error() << formatv(
1785            "{0}: contribution {1:X}: index {2:X}: invalid string "
1786            "offset *{3:X} == {4:X}, is beyond the bounds of the string section of length {5:X}\n",
1787            SectionName, StartOffset, Index, OffOff, StrOff, StrData.size());
1788        continue;
1789      }
1790      if (StrData[StrOff - 1] == '\0')
1791        continue;
1792      error() << formatv("{0}: contribution {1:X}: index {2:X}: invalid string "
1793                         "offset *{3:X} == {4:X}, is neither zero nor "
1794                         "immediately following a null character\n",
1795                         SectionName, StartOffset, Index, OffOff, StrOff);
1796      Success = false;
1797    }
1798  }
1799
1800  if (Error E = C.takeError()) {
1801    error() << SectionName << ": " << toString(std::move(E)) << '\n';
1802    return false;
1803  }
1804  return Success;
1805}
1806
1807raw_ostream &DWARFVerifier::error() const { return WithColor::error(OS); }
1808
1809raw_ostream &DWARFVerifier::warn() const { return WithColor::warning(OS); }
1810
1811raw_ostream &DWARFVerifier::note() const { return WithColor::note(OS); }
1812
1813raw_ostream &DWARFVerifier::dump(const DWARFDie &Die, unsigned indent) const {
1814  Die.dump(OS, indent, DumpOpts);
1815  return OS;
1816}
1817