1 //===- DWARFVerifier.cpp --------------------------------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "SyntaxHighlighting.h"
11 #include "llvm/DebugInfo/DWARF/DWARFVerifier.h"
12 #include "llvm/DebugInfo/DWARF/DWARFCompileUnit.h"
13 #include "llvm/DebugInfo/DWARF/DWARFContext.h"
14 #include "llvm/DebugInfo/DWARF/DWARFDebugLine.h"
15 #include "llvm/DebugInfo/DWARF/DWARFDie.h"
16 #include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
17 #include "llvm/DebugInfo/DWARF/DWARFSection.h"
18 #include "llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h"
19 #include "llvm/Support/raw_ostream.h"
20 #include <map>
21 #include <set>
22 #include <vector>
23 
24 using namespace llvm;
25 using namespace dwarf;
26 using namespace object;
27 using namespace syntax;
28 
29 DWARFVerifier::DieRangeInfo::address_range_iterator
30 DWARFVerifier::DieRangeInfo::insert(const DWARFAddressRange &R) {
31   auto Begin = Ranges.begin();
32   auto End = Ranges.end();
33   auto Pos = std::lower_bound(Begin, End, R);
34 
35   if (Pos != End) {
36     if (Pos->intersects(R))
37       return Pos;
38     if (Pos != Begin) {
39       auto Iter = Pos - 1;
40       if (Iter->intersects(R))
41         return Iter;
42     }
43   }
44 
45   Ranges.insert(Pos, R);
46   return Ranges.end();
47 }
48 
49 DWARFVerifier::DieRangeInfo::die_range_info_iterator
50 DWARFVerifier::DieRangeInfo::insert(const DieRangeInfo &RI) {
51   auto End = Children.end();
52   auto Iter = Children.begin();
53   while (Iter != End) {
54     if (Iter->intersects(RI))
55       return Iter;
56     ++Iter;
57   }
58   Children.insert(RI);
59   return Children.end();
60 }
61 
62 bool DWARFVerifier::DieRangeInfo::contains(const DieRangeInfo &RHS) const {
63   // Both list of ranges are sorted so we can make this fast.
64 
65   if (Ranges.empty() || RHS.Ranges.empty())
66     return false;
67 
68   // Since the ranges are sorted we can advance where we start searching with
69   // this object's ranges as we traverse RHS.Ranges.
70   auto End = Ranges.end();
71   auto Iter = findRange(RHS.Ranges.front());
72 
73   // Now linearly walk the ranges in this object and see if they contain each
74   // ranges from RHS.Ranges.
75   for (const auto &R : RHS.Ranges) {
76     while (Iter != End) {
77       if (Iter->contains(R))
78         break;
79       ++Iter;
80     }
81     if (Iter == End)
82       return false;
83   }
84   return true;
85 }
86 
87 bool DWARFVerifier::DieRangeInfo::intersects(const DieRangeInfo &RHS) const {
88   if (Ranges.empty() || RHS.Ranges.empty())
89     return false;
90 
91   auto End = Ranges.end();
92   auto Iter = findRange(RHS.Ranges.front());
93   for (const auto &R : RHS.Ranges) {
94     if(Iter == End)
95       return false;
96     if (R.HighPC <= Iter->LowPC)
97       continue;
98     while (Iter != End) {
99       if (Iter->intersects(R))
100         return true;
101       ++Iter;
102     }
103   }
104 
105   return false;
106 }
107 
108 bool DWARFVerifier::verifyUnitHeader(const DWARFDataExtractor DebugInfoData,
109                                      uint32_t *Offset, unsigned UnitIndex,
110                                      uint8_t &UnitType, bool &isUnitDWARF64) {
111   uint32_t AbbrOffset, Length;
112   uint8_t AddrSize = 0;
113   uint16_t Version;
114   bool Success = true;
115 
116   bool ValidLength = false;
117   bool ValidVersion = false;
118   bool ValidAddrSize = false;
119   bool ValidType = true;
120   bool ValidAbbrevOffset = true;
121 
122   uint32_t OffsetStart = *Offset;
123   Length = DebugInfoData.getU32(Offset);
124   if (Length == UINT32_MAX) {
125     isUnitDWARF64 = true;
126     OS << format(
127         "Unit[%d] is in 64-bit DWARF format; cannot verify from this point.\n",
128         UnitIndex);
129     return false;
130   }
131   Version = DebugInfoData.getU16(Offset);
132 
133   if (Version >= 5) {
134     UnitType = DebugInfoData.getU8(Offset);
135     AddrSize = DebugInfoData.getU8(Offset);
136     AbbrOffset = DebugInfoData.getU32(Offset);
137     ValidType = dwarf::isUnitType(UnitType);
138   } else {
139     UnitType = 0;
140     AbbrOffset = DebugInfoData.getU32(Offset);
141     AddrSize = DebugInfoData.getU8(Offset);
142   }
143 
144   if (!DCtx.getDebugAbbrev()->getAbbreviationDeclarationSet(AbbrOffset))
145     ValidAbbrevOffset = false;
146 
147   ValidLength = DebugInfoData.isValidOffset(OffsetStart + Length + 3);
148   ValidVersion = DWARFContext::isSupportedVersion(Version);
149   ValidAddrSize = AddrSize == 4 || AddrSize == 8;
150   if (!ValidLength || !ValidVersion || !ValidAddrSize || !ValidAbbrevOffset ||
151       !ValidType) {
152     Success = false;
153     error() << format("Units[%d] - start offset: 0x%08x \n", UnitIndex,
154                       OffsetStart);
155     if (!ValidLength)
156       note() << "The length for this unit is too "
157             "large for the .debug_info provided.\n";
158     if (!ValidVersion)
159       note() << "The 16 bit unit header version is not valid.\n";
160     if (!ValidType)
161       note() << "The unit type encoding is not valid.\n";
162     if (!ValidAbbrevOffset)
163       note() << "The offset into the .debug_abbrev section is "
164             "not valid.\n";
165     if (!ValidAddrSize)
166       note() << "The address size is unsupported.\n";
167   }
168   *Offset = OffsetStart + Length + 4;
169   return Success;
170 }
171 
172 bool DWARFVerifier::verifyUnitContents(DWARFUnit Unit, uint8_t UnitType) {
173   uint32_t NumUnitErrors = 0;
174   unsigned NumDies = Unit.getNumDIEs();
175   for (unsigned I = 0; I < NumDies; ++I) {
176     auto Die = Unit.getDIEAtIndex(I);
177     if (Die.getTag() == DW_TAG_null)
178       continue;
179     for (auto AttrValue : Die.attributes()) {
180       NumUnitErrors += verifyDebugInfoAttribute(Die, AttrValue);
181       NumUnitErrors += verifyDebugInfoForm(Die, AttrValue);
182     }
183   }
184 
185   DWARFDie Die = Unit.getUnitDIE(/* ExtractUnitDIEOnly = */ false);
186   if (!Die) {
187     error() << "Compilation unit without DIE.\n";
188     NumUnitErrors++;
189     return NumUnitErrors == 0;
190   }
191 
192   if (!dwarf::isUnitType(Die.getTag())) {
193     error() << "Compilation unit root DIE is not a unit DIE: "
194             << dwarf::TagString(Die.getTag()) << ".\n";
195     NumUnitErrors++;
196   }
197 
198   if (UnitType != 0 &&
199       !DWARFUnit::isMatchingUnitTypeAndTag(UnitType, Die.getTag())) {
200     error() << "Compilation unit type (" << dwarf::UnitTypeString(UnitType)
201             << ") and root DIE (" << dwarf::TagString(Die.getTag())
202             << ") do not match.\n";
203     NumUnitErrors++;
204   }
205 
206   DieRangeInfo RI;
207   NumUnitErrors += verifyDieRanges(Die, RI);
208 
209   return NumUnitErrors == 0;
210 }
211 
212 unsigned DWARFVerifier::verifyAbbrevSection(const DWARFDebugAbbrev *Abbrev) {
213   unsigned NumErrors = 0;
214   if (Abbrev) {
215     const DWARFAbbreviationDeclarationSet *AbbrDecls =
216         Abbrev->getAbbreviationDeclarationSet(0);
217     for (auto AbbrDecl : *AbbrDecls) {
218       SmallDenseSet<uint16_t> AttributeSet;
219       for (auto Attribute : AbbrDecl.attributes()) {
220         auto Result = AttributeSet.insert(Attribute.Attr);
221         if (!Result.second) {
222           error() << "Abbreviation declaration contains multiple "
223                   << AttributeString(Attribute.Attr) << " attributes.\n";
224           AbbrDecl.dump(OS);
225           ++NumErrors;
226         }
227       }
228     }
229   }
230   return NumErrors;
231 }
232 
233 bool DWARFVerifier::handleDebugAbbrev() {
234   OS << "Verifying .debug_abbrev...\n";
235 
236   const DWARFObject &DObj = DCtx.getDWARFObj();
237   bool noDebugAbbrev = DObj.getAbbrevSection().empty();
238   bool noDebugAbbrevDWO = DObj.getAbbrevDWOSection().empty();
239 
240   if (noDebugAbbrev && noDebugAbbrevDWO) {
241     return true;
242   }
243 
244   unsigned NumErrors = 0;
245   if (!noDebugAbbrev)
246     NumErrors += verifyAbbrevSection(DCtx.getDebugAbbrev());
247 
248   if (!noDebugAbbrevDWO)
249     NumErrors += verifyAbbrevSection(DCtx.getDebugAbbrevDWO());
250   return NumErrors == 0;
251 }
252 
253 bool DWARFVerifier::handleDebugInfo() {
254   OS << "Verifying .debug_info Unit Header Chain...\n";
255 
256   const DWARFObject &DObj = DCtx.getDWARFObj();
257   DWARFDataExtractor DebugInfoData(DObj, DObj.getInfoSection(),
258                                    DCtx.isLittleEndian(), 0);
259   uint32_t NumDebugInfoErrors = 0;
260   uint32_t OffsetStart = 0, Offset = 0, UnitIdx = 0;
261   uint8_t UnitType = 0;
262   bool isUnitDWARF64 = false;
263   bool isHeaderChainValid = true;
264   bool hasDIE = DebugInfoData.isValidOffset(Offset);
265   while (hasDIE) {
266     OffsetStart = Offset;
267     if (!verifyUnitHeader(DebugInfoData, &Offset, UnitIdx, UnitType,
268                           isUnitDWARF64)) {
269       isHeaderChainValid = false;
270       if (isUnitDWARF64)
271         break;
272     } else {
273       std::unique_ptr<DWARFUnit> Unit;
274       switch (UnitType) {
275       case dwarf::DW_UT_type:
276       case dwarf::DW_UT_split_type: {
277         DWARFUnitSection<DWARFTypeUnit> TUSection{};
278         Unit.reset(new DWARFTypeUnit(
279             DCtx, DObj.getInfoSection(), DCtx.getDebugAbbrev(),
280             &DObj.getRangeSection(), DObj.getStringSection(),
281             DObj.getStringOffsetSection(), &DObj.getAppleObjCSection(),
282             DObj.getLineSection(), DCtx.isLittleEndian(), false, TUSection,
283             nullptr));
284         break;
285       }
286       case dwarf::DW_UT_skeleton:
287       case dwarf::DW_UT_split_compile:
288       case dwarf::DW_UT_compile:
289       case dwarf::DW_UT_partial:
290       // UnitType = 0 means that we are
291       // verifying a compile unit in DWARF v4.
292       case 0: {
293         DWARFUnitSection<DWARFCompileUnit> CUSection{};
294         Unit.reset(new DWARFCompileUnit(
295             DCtx, DObj.getInfoSection(), DCtx.getDebugAbbrev(),
296             &DObj.getRangeSection(), DObj.getStringSection(),
297             DObj.getStringOffsetSection(), &DObj.getAppleObjCSection(),
298             DObj.getLineSection(), DCtx.isLittleEndian(), false, CUSection,
299             nullptr));
300         break;
301       }
302       default: { llvm_unreachable("Invalid UnitType."); }
303       }
304       Unit->extract(DebugInfoData, &OffsetStart);
305       if (!verifyUnitContents(*Unit, UnitType))
306         ++NumDebugInfoErrors;
307     }
308     hasDIE = DebugInfoData.isValidOffset(Offset);
309     ++UnitIdx;
310   }
311   if (UnitIdx == 0 && !hasDIE) {
312     warn() << ".debug_info is empty.\n";
313     isHeaderChainValid = true;
314   }
315   NumDebugInfoErrors += verifyDebugInfoReferences();
316   return (isHeaderChainValid && NumDebugInfoErrors == 0);
317 }
318 
319 unsigned DWARFVerifier::verifyDieRanges(const DWARFDie &Die,
320                                         DieRangeInfo &ParentRI) {
321   unsigned NumErrors = 0;
322 
323   if (!Die.isValid())
324     return NumErrors;
325 
326   DWARFAddressRangesVector Ranges = Die.getAddressRanges();
327 
328   // Build RI for this DIE and check that ranges within this DIE do not
329   // overlap.
330   DieRangeInfo RI(Die);
331   for (auto Range : Ranges) {
332     if (!Range.valid()) {
333       ++NumErrors;
334       error() << "Invalid address range " << Range << "\n";
335       continue;
336     }
337 
338     // Verify that ranges don't intersect.
339     const auto IntersectingRange = RI.insert(Range);
340     if (IntersectingRange != RI.Ranges.end()) {
341       ++NumErrors;
342       error() << "DIE has overlapping address ranges: " << Range << " and "
343               << *IntersectingRange << "\n";
344       break;
345     }
346   }
347 
348   // Verify that children don't intersect.
349   const auto IntersectingChild = ParentRI.insert(RI);
350   if (IntersectingChild != ParentRI.Children.end()) {
351     ++NumErrors;
352     error() << "DIEs have overlapping address ranges:";
353     Die.dump(OS, 0);
354     IntersectingChild->Die.dump(OS, 0);
355     OS << "\n";
356   }
357 
358   // Verify that ranges are contained within their parent.
359   bool ShouldBeContained = !Ranges.empty() && !ParentRI.Ranges.empty() &&
360                            !(Die.getTag() == DW_TAG_subprogram &&
361                              ParentRI.Die.getTag() == DW_TAG_subprogram);
362   if (ShouldBeContained && !ParentRI.contains(RI)) {
363     ++NumErrors;
364     error() << "DIE address ranges are not "
365                "contained in its parent's ranges:";
366     Die.dump(OS, 0);
367     ParentRI.Die.dump(OS, 0);
368     OS << "\n";
369   }
370 
371   // Recursively check children.
372   for (DWARFDie Child : Die)
373     NumErrors += verifyDieRanges(Child, RI);
374 
375   return NumErrors;
376 }
377 
378 unsigned DWARFVerifier::verifyDebugInfoAttribute(const DWARFDie &Die,
379                                                  DWARFAttribute &AttrValue) {
380   const DWARFObject &DObj = DCtx.getDWARFObj();
381   unsigned NumErrors = 0;
382   const auto Attr = AttrValue.Attr;
383   switch (Attr) {
384   case DW_AT_ranges:
385     // Make sure the offset in the DW_AT_ranges attribute is valid.
386     if (auto SectionOffset = AttrValue.Value.getAsSectionOffset()) {
387       if (*SectionOffset >= DObj.getRangeSection().Data.size()) {
388         ++NumErrors;
389         error() << "DW_AT_ranges offset is beyond .debug_ranges "
390                    "bounds:\n";
391         Die.dump(OS, 0, DumpOpts);
392         OS << "\n";
393       }
394     } else {
395       ++NumErrors;
396       error() << "DIE has invalid DW_AT_ranges encoding:\n";
397       Die.dump(OS, 0, DumpOpts);
398       OS << "\n";
399     }
400     break;
401   case DW_AT_stmt_list:
402     // Make sure the offset in the DW_AT_stmt_list attribute is valid.
403     if (auto SectionOffset = AttrValue.Value.getAsSectionOffset()) {
404       if (*SectionOffset >= DObj.getLineSection().Data.size()) {
405         ++NumErrors;
406         error() << "DW_AT_stmt_list offset is beyond .debug_line "
407                    "bounds: "
408                 << format("0x%08" PRIx64, *SectionOffset) << "\n";
409         Die.dump(OS, 0, DumpOpts);
410         OS << "\n";
411       }
412     } else {
413       ++NumErrors;
414       error() << "DIE has invalid DW_AT_stmt_list encoding:\n";
415       Die.dump(OS, 0, DumpOpts);
416       OS << "\n";
417     }
418     break;
419 
420   default:
421     break;
422   }
423   return NumErrors;
424 }
425 
426 unsigned DWARFVerifier::verifyDebugInfoForm(const DWARFDie &Die,
427                                             DWARFAttribute &AttrValue) {
428   const DWARFObject &DObj = DCtx.getDWARFObj();
429   unsigned NumErrors = 0;
430   const auto Form = AttrValue.Value.getForm();
431   switch (Form) {
432   case DW_FORM_ref1:
433   case DW_FORM_ref2:
434   case DW_FORM_ref4:
435   case DW_FORM_ref8:
436   case DW_FORM_ref_udata: {
437     // Verify all CU relative references are valid CU offsets.
438     Optional<uint64_t> RefVal = AttrValue.Value.getAsReference();
439     assert(RefVal);
440     if (RefVal) {
441       auto DieCU = Die.getDwarfUnit();
442       auto CUSize = DieCU->getNextUnitOffset() - DieCU->getOffset();
443       auto CUOffset = AttrValue.Value.getRawUValue();
444       if (CUOffset >= CUSize) {
445         ++NumErrors;
446         error() << FormEncodingString(Form) << " CU offset "
447                 << format("0x%08" PRIx64, CUOffset)
448                 << " is invalid (must be less than CU size of "
449                 << format("0x%08" PRIx32, CUSize) << "):\n";
450         Die.dump(OS, 0, DumpOpts);
451         OS << "\n";
452       } else {
453         // Valid reference, but we will verify it points to an actual
454         // DIE later.
455         ReferenceToDIEOffsets[*RefVal].insert(Die.getOffset());
456       }
457     }
458     break;
459   }
460   case DW_FORM_ref_addr: {
461     // Verify all absolute DIE references have valid offsets in the
462     // .debug_info section.
463     Optional<uint64_t> RefVal = AttrValue.Value.getAsReference();
464     assert(RefVal);
465     if (RefVal) {
466       if (*RefVal >= DObj.getInfoSection().Data.size()) {
467         ++NumErrors;
468         error() << "DW_FORM_ref_addr offset beyond .debug_info "
469                    "bounds:\n";
470         Die.dump(OS, 0, DumpOpts);
471         OS << "\n";
472       } else {
473         // Valid reference, but we will verify it points to an actual
474         // DIE later.
475         ReferenceToDIEOffsets[*RefVal].insert(Die.getOffset());
476       }
477     }
478     break;
479   }
480   case DW_FORM_strp: {
481     auto SecOffset = AttrValue.Value.getAsSectionOffset();
482     assert(SecOffset); // DW_FORM_strp is a section offset.
483     if (SecOffset && *SecOffset >= DObj.getStringSection().size()) {
484       ++NumErrors;
485       error() << "DW_FORM_strp offset beyond .debug_str bounds:\n";
486       Die.dump(OS, 0, DumpOpts);
487       OS << "\n";
488     }
489     break;
490   }
491   default:
492     break;
493   }
494   return NumErrors;
495 }
496 
497 unsigned DWARFVerifier::verifyDebugInfoReferences() {
498   // Take all references and make sure they point to an actual DIE by
499   // getting the DIE by offset and emitting an error
500   OS << "Verifying .debug_info references...\n";
501   unsigned NumErrors = 0;
502   for (auto Pair : ReferenceToDIEOffsets) {
503     auto Die = DCtx.getDIEForOffset(Pair.first);
504     if (Die)
505       continue;
506     ++NumErrors;
507     error() << "invalid DIE reference " << format("0x%08" PRIx64, Pair.first)
508             << ". Offset is in between DIEs:\n";
509     for (auto Offset : Pair.second) {
510       auto ReferencingDie = DCtx.getDIEForOffset(Offset);
511       ReferencingDie.dump(OS, 0, DumpOpts);
512       OS << "\n";
513     }
514     OS << "\n";
515   }
516   return NumErrors;
517 }
518 
519 void DWARFVerifier::verifyDebugLineStmtOffsets() {
520   std::map<uint64_t, DWARFDie> StmtListToDie;
521   for (const auto &CU : DCtx.compile_units()) {
522     auto Die = CU->getUnitDIE();
523     // Get the attribute value as a section offset. No need to produce an
524     // error here if the encoding isn't correct because we validate this in
525     // the .debug_info verifier.
526     auto StmtSectionOffset = toSectionOffset(Die.find(DW_AT_stmt_list));
527     if (!StmtSectionOffset)
528       continue;
529     const uint32_t LineTableOffset = *StmtSectionOffset;
530     auto LineTable = DCtx.getLineTableForUnit(CU.get());
531     if (LineTableOffset < DCtx.getDWARFObj().getLineSection().Data.size()) {
532       if (!LineTable) {
533         ++NumDebugLineErrors;
534         error() << ".debug_line[" << format("0x%08" PRIx32, LineTableOffset)
535                 << "] was not able to be parsed for CU:\n";
536         Die.dump(OS, 0, DumpOpts);
537         OS << '\n';
538         continue;
539       }
540     } else {
541       // Make sure we don't get a valid line table back if the offset is wrong.
542       assert(LineTable == nullptr);
543       // Skip this line table as it isn't valid. No need to create an error
544       // here because we validate this in the .debug_info verifier.
545       continue;
546     }
547     auto Iter = StmtListToDie.find(LineTableOffset);
548     if (Iter != StmtListToDie.end()) {
549       ++NumDebugLineErrors;
550       error() << "two compile unit DIEs, "
551               << format("0x%08" PRIx32, Iter->second.getOffset()) << " and "
552               << format("0x%08" PRIx32, Die.getOffset())
553               << ", have the same DW_AT_stmt_list section offset:\n";
554       Iter->second.dump(OS, 0, DumpOpts);
555       Die.dump(OS, 0, DumpOpts);
556       OS << '\n';
557       // Already verified this line table before, no need to do it again.
558       continue;
559     }
560     StmtListToDie[LineTableOffset] = Die;
561   }
562 }
563 
564 void DWARFVerifier::verifyDebugLineRows() {
565   for (const auto &CU : DCtx.compile_units()) {
566     auto Die = CU->getUnitDIE();
567     auto LineTable = DCtx.getLineTableForUnit(CU.get());
568     // If there is no line table we will have created an error in the
569     // .debug_info verifier or in verifyDebugLineStmtOffsets().
570     if (!LineTable)
571       continue;
572 
573     // Verify prologue.
574     uint32_t MaxFileIndex = LineTable->Prologue.FileNames.size();
575     uint32_t MaxDirIndex = LineTable->Prologue.IncludeDirectories.size();
576     uint32_t FileIndex = 1;
577     StringMap<uint16_t> FullPathMap;
578     for (const auto &FileName : LineTable->Prologue.FileNames) {
579       // Verify directory index.
580       if (FileName.DirIdx > MaxDirIndex) {
581         ++NumDebugLineErrors;
582         error() << ".debug_line["
583                 << format("0x%08" PRIx64,
584                           *toSectionOffset(Die.find(DW_AT_stmt_list)))
585                 << "].prologue.file_names[" << FileIndex
586                 << "].dir_idx contains an invalid index: " << FileName.DirIdx
587                 << "\n";
588       }
589 
590       // Check file paths for duplicates.
591       std::string FullPath;
592       const bool HasFullPath = LineTable->getFileNameByIndex(
593           FileIndex, CU->getCompilationDir(),
594           DILineInfoSpecifier::FileLineInfoKind::AbsoluteFilePath, FullPath);
595       assert(HasFullPath && "Invalid index?");
596       (void)HasFullPath;
597       auto It = FullPathMap.find(FullPath);
598       if (It == FullPathMap.end())
599         FullPathMap[FullPath] = FileIndex;
600       else if (It->second != FileIndex) {
601         warn() << ".debug_line["
602                << format("0x%08" PRIx64,
603                          *toSectionOffset(Die.find(DW_AT_stmt_list)))
604                << "].prologue.file_names[" << FileIndex
605                << "] is a duplicate of file_names[" << It->second << "]\n";
606       }
607 
608       FileIndex++;
609     }
610 
611     // Verify rows.
612     uint64_t PrevAddress = 0;
613     uint32_t RowIndex = 0;
614     for (const auto &Row : LineTable->Rows) {
615       // Verify row address.
616       if (Row.Address < PrevAddress) {
617         ++NumDebugLineErrors;
618         error() << ".debug_line["
619                 << format("0x%08" PRIx64,
620                           *toSectionOffset(Die.find(DW_AT_stmt_list)))
621                 << "] row[" << RowIndex
622                 << "] decreases in address from previous row:\n";
623 
624         DWARFDebugLine::Row::dumpTableHeader(OS);
625         if (RowIndex > 0)
626           LineTable->Rows[RowIndex - 1].dump(OS);
627         Row.dump(OS);
628         OS << '\n';
629       }
630 
631       // Verify file index.
632       if (Row.File > MaxFileIndex) {
633         ++NumDebugLineErrors;
634         error() << ".debug_line["
635                 << format("0x%08" PRIx64,
636                           *toSectionOffset(Die.find(DW_AT_stmt_list)))
637                 << "][" << RowIndex << "] has invalid file index " << Row.File
638                 << " (valid values are [1," << MaxFileIndex << "]):\n";
639         DWARFDebugLine::Row::dumpTableHeader(OS);
640         Row.dump(OS);
641         OS << '\n';
642       }
643       if (Row.EndSequence)
644         PrevAddress = 0;
645       else
646         PrevAddress = Row.Address;
647       ++RowIndex;
648     }
649   }
650 }
651 
652 bool DWARFVerifier::handleDebugLine() {
653   NumDebugLineErrors = 0;
654   OS << "Verifying .debug_line...\n";
655   verifyDebugLineStmtOffsets();
656   verifyDebugLineRows();
657   return NumDebugLineErrors == 0;
658 }
659 
660 unsigned DWARFVerifier::verifyAccelTable(const DWARFSection *AccelSection,
661                                          DataExtractor *StrData,
662                                          const char *SectionName) {
663   unsigned NumErrors = 0;
664   DWARFDataExtractor AccelSectionData(DCtx.getDWARFObj(), *AccelSection,
665                                       DCtx.isLittleEndian(), 0);
666   DWARFAcceleratorTable AccelTable(AccelSectionData, *StrData);
667 
668   OS << "Verifying " << SectionName << "...\n";
669 
670   // Verify that the fixed part of the header is not too short.
671   if (!AccelSectionData.isValidOffset(AccelTable.getSizeHdr())) {
672     error() << "Section is too small to fit a section header.\n";
673     return 1;
674   }
675 
676   // Verify that the section is not too short.
677   if (!AccelTable.extract()) {
678     error() << "Section is smaller than size described in section header.\n";
679     return 1;
680   }
681 
682   // Verify that all buckets have a valid hash index or are empty.
683   uint32_t NumBuckets = AccelTable.getNumBuckets();
684   uint32_t NumHashes = AccelTable.getNumHashes();
685 
686   uint32_t BucketsOffset =
687       AccelTable.getSizeHdr() + AccelTable.getHeaderDataLength();
688   uint32_t HashesBase = BucketsOffset + NumBuckets * 4;
689   uint32_t OffsetsBase = HashesBase + NumHashes * 4;
690   for (uint32_t BucketIdx = 0; BucketIdx < NumBuckets; ++BucketIdx) {
691     uint32_t HashIdx = AccelSectionData.getU32(&BucketsOffset);
692     if (HashIdx >= NumHashes && HashIdx != UINT32_MAX) {
693       error() << format("Bucket[%d] has invalid hash index: %u.\n", BucketIdx,
694                         HashIdx);
695       ++NumErrors;
696     }
697   }
698   uint32_t NumAtoms = AccelTable.getAtomsDesc().size();
699   if (NumAtoms == 0) {
700     error() << "No atoms: failed to read HashData.\n";
701     return 1;
702   }
703   if (!AccelTable.validateForms()) {
704     error() << "Unsupported form: failed to read HashData.\n";
705     return 1;
706   }
707 
708   for (uint32_t HashIdx = 0; HashIdx < NumHashes; ++HashIdx) {
709     uint32_t HashOffset = HashesBase + 4 * HashIdx;
710     uint32_t DataOffset = OffsetsBase + 4 * HashIdx;
711     uint32_t Hash = AccelSectionData.getU32(&HashOffset);
712     uint32_t HashDataOffset = AccelSectionData.getU32(&DataOffset);
713     if (!AccelSectionData.isValidOffsetForDataOfSize(HashDataOffset,
714                                                      sizeof(uint64_t))) {
715       error() << format("Hash[%d] has invalid HashData offset: 0x%08x.\n",
716                         HashIdx, HashDataOffset);
717       ++NumErrors;
718     }
719 
720     uint32_t StrpOffset;
721     uint32_t StringOffset;
722     uint32_t StringCount = 0;
723     unsigned Offset;
724     unsigned Tag;
725     while ((StrpOffset = AccelSectionData.getU32(&HashDataOffset)) != 0) {
726       const uint32_t NumHashDataObjects =
727           AccelSectionData.getU32(&HashDataOffset);
728       for (uint32_t HashDataIdx = 0; HashDataIdx < NumHashDataObjects;
729            ++HashDataIdx) {
730         std::tie(Offset, Tag) = AccelTable.readAtoms(HashDataOffset);
731         auto Die = DCtx.getDIEForOffset(Offset);
732         if (!Die) {
733           const uint32_t BucketIdx =
734               NumBuckets ? (Hash % NumBuckets) : UINT32_MAX;
735           StringOffset = StrpOffset;
736           const char *Name = StrData->getCStr(&StringOffset);
737           if (!Name)
738             Name = "<NULL>";
739 
740           error() << format(
741               "%s Bucket[%d] Hash[%d] = 0x%08x "
742               "Str[%u] = 0x%08x "
743               "DIE[%d] = 0x%08x is not a valid DIE offset for \"%s\".\n",
744               SectionName, BucketIdx, HashIdx, Hash, StringCount, StrpOffset,
745               HashDataIdx, Offset, Name);
746 
747           ++NumErrors;
748           continue;
749         }
750         if ((Tag != dwarf::DW_TAG_null) && (Die.getTag() != Tag)) {
751           error() << "Tag " << dwarf::TagString(Tag)
752                   << " in accelerator table does not match Tag "
753                   << dwarf::TagString(Die.getTag()) << " of DIE[" << HashDataIdx
754                   << "].\n";
755           ++NumErrors;
756         }
757       }
758       ++StringCount;
759     }
760   }
761   return NumErrors;
762 }
763 
764 bool DWARFVerifier::handleAccelTables() {
765   const DWARFObject &D = DCtx.getDWARFObj();
766   DataExtractor StrData(D.getStringSection(), DCtx.isLittleEndian(), 0);
767   unsigned NumErrors = 0;
768   if (!D.getAppleNamesSection().Data.empty())
769     NumErrors +=
770         verifyAccelTable(&D.getAppleNamesSection(), &StrData, ".apple_names");
771   if (!D.getAppleTypesSection().Data.empty())
772     NumErrors +=
773         verifyAccelTable(&D.getAppleTypesSection(), &StrData, ".apple_types");
774   if (!D.getAppleNamespacesSection().Data.empty())
775     NumErrors += verifyAccelTable(&D.getAppleNamespacesSection(), &StrData,
776                                   ".apple_namespaces");
777   if (!D.getAppleObjCSection().Data.empty())
778     NumErrors +=
779         verifyAccelTable(&D.getAppleObjCSection(), &StrData, ".apple_objc");
780   return NumErrors == 0;
781 }
782 
783 raw_ostream &DWARFVerifier::error() const {
784   return WithColor(OS, syntax::Error).get() << "error: ";
785 }
786 
787 raw_ostream &DWARFVerifier::warn() const {
788   return WithColor(OS, syntax::Warning).get() << "warning: ";
789 }
790 
791 raw_ostream &DWARFVerifier::note() const {
792   return WithColor(OS, syntax::Note).get() << "note: ";
793 }
794