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