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