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