LLVM  8.0.0svn
DWARFVerifier.cpp
Go to the documentation of this file.
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 
11 #include "llvm/ADT/SmallSet.h"
19 #include "llvm/Support/DJB.h"
21 #include "llvm/Support/WithColor.h"
23 #include <map>
24 #include <set>
25 #include <vector>
26 
27 using namespace llvm;
28 using namespace dwarf;
29 using namespace object;
30 
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 
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 
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 
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 unsigned DWARFVerifier::verifyUnitContents(DWARFUnit &Unit) {
175  unsigned 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;
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  uint8_t UnitType = Unit.getUnitType();
201  if (!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;
212 }
213 
214 unsigned DWARFVerifier::verifyAbbrevSection(const DWARFDebugAbbrev *Abbrev) {
215  unsigned NumErrors = 0;
216  if (Abbrev) {
217  const DWARFAbbreviationDeclarationSet *AbbrDecls =
219  for (auto AbbrDecl : *AbbrDecls) {
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 
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 unsigned DWARFVerifier::verifyUnitSection(const DWARFSection &S,
257  const DWARFObject &DObj = DCtx.getDWARFObj();
258  DWARFDataExtractor DebugInfoData(DObj, S, DCtx.isLittleEndian(), 0);
259  unsigned 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  DWARFUnitVector UnitVector{};
266  while (hasDIE) {
267  OffsetStart = Offset;
268  if (!verifyUnitHeader(DebugInfoData, &Offset, UnitIdx, UnitType,
269  isUnitDWARF64)) {
270  isHeaderChainValid = false;
271  if (isUnitDWARF64)
272  break;
273  } else {
274  DWARFUnitHeader Header;
275  Header.extract(DCtx, DebugInfoData, &OffsetStart, SectionKind);
276  std::unique_ptr<DWARFUnit> Unit;
277  switch (UnitType) {
278  case dwarf::DW_UT_type:
279  case dwarf::DW_UT_split_type: {
280  Unit.reset(new DWARFTypeUnit(
281  DCtx, S, Header, DCtx.getDebugAbbrev(), &DObj.getRangeSection(),
283  &DObj.getAppleObjCSection(), DObj.getLineSection(),
284  DCtx.isLittleEndian(), false, UnitVector));
285  break;
286  }
287  case dwarf::DW_UT_skeleton:
288  case dwarf::DW_UT_split_compile:
289  case dwarf::DW_UT_compile:
290  case dwarf::DW_UT_partial:
291  // UnitType = 0 means that we are verifying a compile unit in DWARF v4.
292  case 0: {
293  Unit.reset(new DWARFCompileUnit(
294  DCtx, S, Header, DCtx.getDebugAbbrev(), &DObj.getRangeSection(),
296  &DObj.getAppleObjCSection(), DObj.getLineSection(),
297  DCtx.isLittleEndian(), false, UnitVector));
298  break;
299  }
300  default: { llvm_unreachable("Invalid UnitType."); }
301  }
302  NumDebugInfoErrors += verifyUnitContents(*Unit);
303  }
304  hasDIE = DebugInfoData.isValidOffset(Offset);
305  ++UnitIdx;
306  }
307  if (UnitIdx == 0 && !hasDIE) {
308  warn() << "Section is empty.\n";
309  isHeaderChainValid = true;
310  }
311  if (!isHeaderChainValid)
312  ++NumDebugInfoErrors;
313  NumDebugInfoErrors += verifyDebugInfoReferences();
314  return NumDebugInfoErrors;
315 }
316 
318  const DWARFObject &DObj = DCtx.getDWARFObj();
319 
320  OS << "Verifying .debug_info Unit Header Chain...\n";
321  unsigned result = verifyUnitSection(DObj.getInfoSection(), DW_SECT_INFO);
322 
323  OS << "Verifying .debug_types Unit Header Chain...\n";
324  DObj.forEachTypesSections([&](const DWARFSection &S) {
325  result += verifyUnitSection(S, DW_SECT_TYPES);
326  });
327  return result == 0;
328 }
329 
330 unsigned DWARFVerifier::verifyDieRanges(const DWARFDie &Die,
331  DieRangeInfo &ParentRI) {
332  unsigned NumErrors = 0;
333 
334  if (!Die.isValid())
335  return NumErrors;
336 
337  auto RangesOrError = Die.getAddressRanges();
338  if (!RangesOrError) {
339  // FIXME: Report the error.
340  ++NumErrors;
341  llvm::consumeError(RangesOrError.takeError());
342  return NumErrors;
343  }
344 
345  DWARFAddressRangesVector Ranges = RangesOrError.get();
346  // Build RI for this DIE and check that ranges within this DIE do not
347  // overlap.
348  DieRangeInfo RI(Die);
349  for (auto Range : Ranges) {
350  if (!Range.valid()) {
351  ++NumErrors;
352  error() << "Invalid address range " << Range << "\n";
353  continue;
354  }
355 
356  // Verify that ranges don't intersect.
357  const auto IntersectingRange = RI.insert(Range);
358  if (IntersectingRange != RI.Ranges.end()) {
359  ++NumErrors;
360  error() << "DIE has overlapping address ranges: " << Range << " and "
361  << *IntersectingRange << "\n";
362  break;
363  }
364  }
365 
366  // Verify that children don't intersect.
367  const auto IntersectingChild = ParentRI.insert(RI);
368  if (IntersectingChild != ParentRI.Children.end()) {
369  ++NumErrors;
370  error() << "DIEs have overlapping address ranges:";
371  Die.dump(OS, 0);
372  IntersectingChild->Die.dump(OS, 0);
373  OS << "\n";
374  }
375 
376  // Verify that ranges are contained within their parent.
377  bool ShouldBeContained = !Ranges.empty() && !ParentRI.Ranges.empty() &&
378  !(Die.getTag() == DW_TAG_subprogram &&
379  ParentRI.Die.getTag() == DW_TAG_subprogram);
380  if (ShouldBeContained && !ParentRI.contains(RI)) {
381  ++NumErrors;
382  error() << "DIE address ranges are not contained in its parent's ranges:";
383  ParentRI.Die.dump(OS, 0);
384  Die.dump(OS, 2);
385  OS << "\n";
386  }
387 
388  // Recursively check children.
389  for (DWARFDie Child : Die)
390  NumErrors += verifyDieRanges(Child, RI);
391 
392  return NumErrors;
393 }
394 
395 unsigned DWARFVerifier::verifyDebugInfoAttribute(const DWARFDie &Die,
396  DWARFAttribute &AttrValue) {
397  unsigned NumErrors = 0;
398  auto ReportError = [&](const Twine &TitleMsg) {
399  ++NumErrors;
400  error() << TitleMsg << '\n';
401  Die.dump(OS, 0, DumpOpts);
402  OS << "\n";
403  };
404 
405  const DWARFObject &DObj = DCtx.getDWARFObj();
406  const auto Attr = AttrValue.Attr;
407  switch (Attr) {
408  case DW_AT_ranges:
409  // Make sure the offset in the DW_AT_ranges attribute is valid.
410  if (auto SectionOffset = AttrValue.Value.getAsSectionOffset()) {
411  if (*SectionOffset >= DObj.getRangeSection().Data.size())
412  ReportError("DW_AT_ranges offset is beyond .debug_ranges bounds:");
413  break;
414  }
415  ReportError("DIE has invalid DW_AT_ranges encoding:");
416  break;
417  case DW_AT_stmt_list:
418  // Make sure the offset in the DW_AT_stmt_list attribute is valid.
419  if (auto SectionOffset = AttrValue.Value.getAsSectionOffset()) {
420  if (*SectionOffset >= DObj.getLineSection().Data.size())
421  ReportError("DW_AT_stmt_list offset is beyond .debug_line bounds: " +
422  llvm::formatv("{0:x8}", *SectionOffset));
423  break;
424  }
425  ReportError("DIE has invalid DW_AT_stmt_list encoding:");
426  break;
427  case DW_AT_location: {
428  auto VerifyLocationExpr = [&](StringRef D) {
429  DWARFUnit *U = Die.getDwarfUnit();
430  DataExtractor Data(D, DCtx.isLittleEndian(), 0);
431  DWARFExpression Expression(Data, U->getVersion(),
432  U->getAddressByteSize());
433  bool Error = llvm::any_of(Expression, [](DWARFExpression::Operation &Op) {
434  return Op.isError();
435  });
436  if (Error)
437  ReportError("DIE contains invalid DWARF expression:");
438  };
439  if (Optional<ArrayRef<uint8_t>> Expr = AttrValue.Value.getAsBlock()) {
440  // Verify inlined location.
441  VerifyLocationExpr(llvm::toStringRef(*Expr));
442  } else if (auto LocOffset = AttrValue.Value.getAsSectionOffset()) {
443  // Verify location list.
444  if (auto DebugLoc = DCtx.getDebugLoc())
445  if (auto LocList = DebugLoc->getLocationListAtOffset(*LocOffset))
446  for (const auto &Entry : LocList->Entries)
447  VerifyLocationExpr({Entry.Loc.data(), Entry.Loc.size()});
448  }
449  break;
450  }
451 
452  default:
453  break;
454  }
455  return NumErrors;
456 }
457 
458 unsigned DWARFVerifier::verifyDebugInfoForm(const DWARFDie &Die,
459  DWARFAttribute &AttrValue) {
460  const DWARFObject &DObj = DCtx.getDWARFObj();
461  unsigned NumErrors = 0;
462  const auto Form = AttrValue.Value.getForm();
463  switch (Form) {
464  case DW_FORM_ref1:
465  case DW_FORM_ref2:
466  case DW_FORM_ref4:
467  case DW_FORM_ref8:
468  case DW_FORM_ref_udata: {
469  // Verify all CU relative references are valid CU offsets.
470  Optional<uint64_t> RefVal = AttrValue.Value.getAsReference();
471  assert(RefVal);
472  if (RefVal) {
473  auto DieCU = Die.getDwarfUnit();
474  auto CUSize = DieCU->getNextUnitOffset() - DieCU->getOffset();
475  auto CUOffset = AttrValue.Value.getRawUValue();
476  if (CUOffset >= CUSize) {
477  ++NumErrors;
478  error() << FormEncodingString(Form) << " CU offset "
479  << format("0x%08" PRIx64, CUOffset)
480  << " is invalid (must be less than CU size of "
481  << format("0x%08" PRIx32, CUSize) << "):\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_ref_addr: {
493  // Verify all absolute DIE references have valid offsets in the
494  // .debug_info section.
495  Optional<uint64_t> RefVal = AttrValue.Value.getAsReference();
496  assert(RefVal);
497  if (RefVal) {
498  if (*RefVal >= DObj.getInfoSection().Data.size()) {
499  ++NumErrors;
500  error() << "DW_FORM_ref_addr offset beyond .debug_info "
501  "bounds:\n";
502  Die.dump(OS, 0, DumpOpts);
503  OS << "\n";
504  } else {
505  // Valid reference, but we will verify it points to an actual
506  // DIE later.
507  ReferenceToDIEOffsets[*RefVal].insert(Die.getOffset());
508  }
509  }
510  break;
511  }
512  case DW_FORM_strp: {
513  auto SecOffset = AttrValue.Value.getAsSectionOffset();
514  assert(SecOffset); // DW_FORM_strp is a section offset.
515  if (SecOffset && *SecOffset >= DObj.getStringSection().size()) {
516  ++NumErrors;
517  error() << "DW_FORM_strp offset beyond .debug_str bounds:\n";
518  Die.dump(OS, 0, DumpOpts);
519  OS << "\n";
520  }
521  break;
522  }
523  default:
524  break;
525  }
526  return NumErrors;
527 }
528 
529 unsigned DWARFVerifier::verifyDebugInfoReferences() {
530  // Take all references and make sure they point to an actual DIE by
531  // getting the DIE by offset and emitting an error
532  OS << "Verifying .debug_info references...\n";
533  unsigned NumErrors = 0;
534  for (auto Pair : ReferenceToDIEOffsets) {
535  auto Die = DCtx.getDIEForOffset(Pair.first);
536  if (Die)
537  continue;
538  ++NumErrors;
539  error() << "invalid DIE reference " << format("0x%08" PRIx64, Pair.first)
540  << ". Offset is in between DIEs:\n";
541  for (auto Offset : Pair.second) {
542  auto ReferencingDie = DCtx.getDIEForOffset(Offset);
543  ReferencingDie.dump(OS, 0, DumpOpts);
544  OS << "\n";
545  }
546  OS << "\n";
547  }
548  return NumErrors;
549 }
550 
551 void DWARFVerifier::verifyDebugLineStmtOffsets() {
552  std::map<uint64_t, DWARFDie> StmtListToDie;
553  for (const auto &CU : DCtx.compile_units()) {
554  auto Die = CU->getUnitDIE();
555  // Get the attribute value as a section offset. No need to produce an
556  // error here if the encoding isn't correct because we validate this in
557  // the .debug_info verifier.
558  auto StmtSectionOffset = toSectionOffset(Die.find(DW_AT_stmt_list));
559  if (!StmtSectionOffset)
560  continue;
561  const uint32_t LineTableOffset = *StmtSectionOffset;
562  auto LineTable = DCtx.getLineTableForUnit(CU.get());
563  if (LineTableOffset < DCtx.getDWARFObj().getLineSection().Data.size()) {
564  if (!LineTable) {
565  ++NumDebugLineErrors;
566  error() << ".debug_line[" << format("0x%08" PRIx32, LineTableOffset)
567  << "] was not able to be parsed for CU:\n";
568  Die.dump(OS, 0, DumpOpts);
569  OS << '\n';
570  continue;
571  }
572  } else {
573  // Make sure we don't get a valid line table back if the offset is wrong.
574  assert(LineTable == nullptr);
575  // Skip this line table as it isn't valid. No need to create an error
576  // here because we validate this in the .debug_info verifier.
577  continue;
578  }
579  auto Iter = StmtListToDie.find(LineTableOffset);
580  if (Iter != StmtListToDie.end()) {
581  ++NumDebugLineErrors;
582  error() << "two compile unit DIEs, "
583  << format("0x%08" PRIx32, Iter->second.getOffset()) << " and "
584  << format("0x%08" PRIx32, Die.getOffset())
585  << ", have the same DW_AT_stmt_list section offset:\n";
586  Iter->second.dump(OS, 0, DumpOpts);
587  Die.dump(OS, 0, DumpOpts);
588  OS << '\n';
589  // Already verified this line table before, no need to do it again.
590  continue;
591  }
592  StmtListToDie[LineTableOffset] = Die;
593  }
594 }
595 
596 void DWARFVerifier::verifyDebugLineRows() {
597  for (const auto &CU : DCtx.compile_units()) {
598  auto Die = CU->getUnitDIE();
599  auto LineTable = DCtx.getLineTableForUnit(CU.get());
600  // If there is no line table we will have created an error in the
601  // .debug_info verifier or in verifyDebugLineStmtOffsets().
602  if (!LineTable)
603  continue;
604 
605  // Verify prologue.
606  uint32_t MaxFileIndex = LineTable->Prologue.FileNames.size();
607  uint32_t MaxDirIndex = LineTable->Prologue.IncludeDirectories.size();
608  uint32_t FileIndex = 1;
609  StringMap<uint16_t> FullPathMap;
610  for (const auto &FileName : LineTable->Prologue.FileNames) {
611  // Verify directory index.
612  if (FileName.DirIdx > MaxDirIndex) {
613  ++NumDebugLineErrors;
614  error() << ".debug_line["
615  << format("0x%08" PRIx64,
616  *toSectionOffset(Die.find(DW_AT_stmt_list)))
617  << "].prologue.file_names[" << FileIndex
618  << "].dir_idx contains an invalid index: " << FileName.DirIdx
619  << "\n";
620  }
621 
622  // Check file paths for duplicates.
623  std::string FullPath;
624  const bool HasFullPath = LineTable->getFileNameByIndex(
625  FileIndex, CU->getCompilationDir(),
627  assert(HasFullPath && "Invalid index?");
628  (void)HasFullPath;
629  auto It = FullPathMap.find(FullPath);
630  if (It == FullPathMap.end())
631  FullPathMap[FullPath] = FileIndex;
632  else if (It->second != FileIndex) {
633  warn() << ".debug_line["
634  << format("0x%08" PRIx64,
635  *toSectionOffset(Die.find(DW_AT_stmt_list)))
636  << "].prologue.file_names[" << FileIndex
637  << "] is a duplicate of file_names[" << It->second << "]\n";
638  }
639 
640  FileIndex++;
641  }
642 
643  // Verify rows.
644  uint64_t PrevAddress = 0;
645  uint32_t RowIndex = 0;
646  for (const auto &Row : LineTable->Rows) {
647  // Verify row address.
648  if (Row.Address < PrevAddress) {
649  ++NumDebugLineErrors;
650  error() << ".debug_line["
651  << format("0x%08" PRIx64,
652  *toSectionOffset(Die.find(DW_AT_stmt_list)))
653  << "] row[" << RowIndex
654  << "] decreases in address from previous row:\n";
655 
657  if (RowIndex > 0)
658  LineTable->Rows[RowIndex - 1].dump(OS);
659  Row.dump(OS);
660  OS << '\n';
661  }
662 
663  // Verify file index.
664  if (Row.File > MaxFileIndex) {
665  ++NumDebugLineErrors;
666  error() << ".debug_line["
667  << format("0x%08" PRIx64,
668  *toSectionOffset(Die.find(DW_AT_stmt_list)))
669  << "][" << RowIndex << "] has invalid file index " << Row.File
670  << " (valid values are [1," << MaxFileIndex << "]):\n";
672  Row.dump(OS);
673  OS << '\n';
674  }
675  if (Row.EndSequence)
676  PrevAddress = 0;
677  else
678  PrevAddress = Row.Address;
679  ++RowIndex;
680  }
681  }
682 }
683 
685  NumDebugLineErrors = 0;
686  OS << "Verifying .debug_line...\n";
687  verifyDebugLineStmtOffsets();
688  verifyDebugLineRows();
689  return NumDebugLineErrors == 0;
690 }
691 
692 unsigned DWARFVerifier::verifyAppleAccelTable(const DWARFSection *AccelSection,
693  DataExtractor *StrData,
694  const char *SectionName) {
695  unsigned NumErrors = 0;
696  DWARFDataExtractor AccelSectionData(DCtx.getDWARFObj(), *AccelSection,
697  DCtx.isLittleEndian(), 0);
698  AppleAcceleratorTable AccelTable(AccelSectionData, *StrData);
699 
700  OS << "Verifying " << SectionName << "...\n";
701 
702  // Verify that the fixed part of the header is not too short.
703  if (!AccelSectionData.isValidOffset(AccelTable.getSizeHdr())) {
704  error() << "Section is too small to fit a section header.\n";
705  return 1;
706  }
707 
708  // Verify that the section is not too short.
709  if (Error E = AccelTable.extract()) {
710  error() << toString(std::move(E)) << '\n';
711  return 1;
712  }
713 
714  // Verify that all buckets have a valid hash index or are empty.
715  uint32_t NumBuckets = AccelTable.getNumBuckets();
716  uint32_t NumHashes = AccelTable.getNumHashes();
717 
718  uint32_t BucketsOffset =
719  AccelTable.getSizeHdr() + AccelTable.getHeaderDataLength();
720  uint32_t HashesBase = BucketsOffset + NumBuckets * 4;
721  uint32_t OffsetsBase = HashesBase + NumHashes * 4;
722  for (uint32_t BucketIdx = 0; BucketIdx < NumBuckets; ++BucketIdx) {
723  uint32_t HashIdx = AccelSectionData.getU32(&BucketsOffset);
724  if (HashIdx >= NumHashes && HashIdx != UINT32_MAX) {
725  error() << format("Bucket[%d] has invalid hash index: %u.\n", BucketIdx,
726  HashIdx);
727  ++NumErrors;
728  }
729  }
730  uint32_t NumAtoms = AccelTable.getAtomsDesc().size();
731  if (NumAtoms == 0) {
732  error() << "No atoms: failed to read HashData.\n";
733  return 1;
734  }
735  if (!AccelTable.validateForms()) {
736  error() << "Unsupported form: failed to read HashData.\n";
737  return 1;
738  }
739 
740  for (uint32_t HashIdx = 0; HashIdx < NumHashes; ++HashIdx) {
741  uint32_t HashOffset = HashesBase + 4 * HashIdx;
742  uint32_t DataOffset = OffsetsBase + 4 * HashIdx;
743  uint32_t Hash = AccelSectionData.getU32(&HashOffset);
744  uint32_t HashDataOffset = AccelSectionData.getU32(&DataOffset);
745  if (!AccelSectionData.isValidOffsetForDataOfSize(HashDataOffset,
746  sizeof(uint64_t))) {
747  error() << format("Hash[%d] has invalid HashData offset: 0x%08x.\n",
748  HashIdx, HashDataOffset);
749  ++NumErrors;
750  }
751 
752  uint32_t StrpOffset;
753  uint32_t StringOffset;
754  uint32_t StringCount = 0;
755  unsigned Offset;
756  unsigned Tag;
757  while ((StrpOffset = AccelSectionData.getU32(&HashDataOffset)) != 0) {
758  const uint32_t NumHashDataObjects =
759  AccelSectionData.getU32(&HashDataOffset);
760  for (uint32_t HashDataIdx = 0; HashDataIdx < NumHashDataObjects;
761  ++HashDataIdx) {
762  std::tie(Offset, Tag) = AccelTable.readAtoms(HashDataOffset);
763  auto Die = DCtx.getDIEForOffset(Offset);
764  if (!Die) {
765  const uint32_t BucketIdx =
766  NumBuckets ? (Hash % NumBuckets) : UINT32_MAX;
767  StringOffset = StrpOffset;
768  const char *Name = StrData->getCStr(&StringOffset);
769  if (!Name)
770  Name = "<NULL>";
771 
772  error() << format(
773  "%s Bucket[%d] Hash[%d] = 0x%08x "
774  "Str[%u] = 0x%08x "
775  "DIE[%d] = 0x%08x is not a valid DIE offset for \"%s\".\n",
776  SectionName, BucketIdx, HashIdx, Hash, StringCount, StrpOffset,
777  HashDataIdx, Offset, Name);
778 
779  ++NumErrors;
780  continue;
781  }
782  if ((Tag != dwarf::DW_TAG_null) && (Die.getTag() != Tag)) {
783  error() << "Tag " << dwarf::TagString(Tag)
784  << " in accelerator table does not match Tag "
785  << dwarf::TagString(Die.getTag()) << " of DIE[" << HashDataIdx
786  << "].\n";
787  ++NumErrors;
788  }
789  }
790  ++StringCount;
791  }
792  }
793  return NumErrors;
794 }
795 
796 unsigned
797 DWARFVerifier::verifyDebugNamesCULists(const DWARFDebugNames &AccelTable) {
798  // A map from CU offset to the (first) Name Index offset which claims to index
799  // this CU.
801  const uint32_t NotIndexed = std::numeric_limits<uint32_t>::max();
802 
803  CUMap.reserve(DCtx.getNumCompileUnits());
804  for (const auto &CU : DCtx.compile_units())
805  CUMap[CU->getOffset()] = NotIndexed;
806 
807  unsigned NumErrors = 0;
808  for (const DWARFDebugNames::NameIndex &NI : AccelTable) {
809  if (NI.getCUCount() == 0) {
810  error() << formatv("Name Index @ {0:x} does not index any CU\n",
811  NI.getUnitOffset());
812  ++NumErrors;
813  continue;
814  }
815  for (uint32_t CU = 0, End = NI.getCUCount(); CU < End; ++CU) {
816  uint32_t Offset = NI.getCUOffset(CU);
817  auto Iter = CUMap.find(Offset);
818 
819  if (Iter == CUMap.end()) {
820  error() << formatv(
821  "Name Index @ {0:x} references a non-existing CU @ {1:x}\n",
822  NI.getUnitOffset(), Offset);
823  ++NumErrors;
824  continue;
825  }
826 
827  if (Iter->second != NotIndexed) {
828  error() << formatv("Name Index @ {0:x} references a CU @ {1:x}, but "
829  "this CU is already indexed by Name Index @ {2:x}\n",
830  NI.getUnitOffset(), Offset, Iter->second);
831  continue;
832  }
833  Iter->second = NI.getUnitOffset();
834  }
835  }
836 
837  for (const auto &KV : CUMap) {
838  if (KV.second == NotIndexed)
839  warn() << formatv("CU @ {0:x} not covered by any Name Index\n", KV.first);
840  }
841 
842  return NumErrors;
843 }
844 
845 unsigned
846 DWARFVerifier::verifyNameIndexBuckets(const DWARFDebugNames::NameIndex &NI,
847  const DataExtractor &StrData) {
848  struct BucketInfo {
849  uint32_t Bucket;
850  uint32_t Index;
851 
852  constexpr BucketInfo(uint32_t Bucket, uint32_t Index)
853  : Bucket(Bucket), Index(Index) {}
854  bool operator<(const BucketInfo &RHS) const { return Index < RHS.Index; };
855  };
856 
857  uint32_t NumErrors = 0;
858  if (NI.getBucketCount() == 0) {
859  warn() << formatv("Name Index @ {0:x} does not contain a hash table.\n",
860  NI.getUnitOffset());
861  return NumErrors;
862  }
863 
864  // Build up a list of (Bucket, Index) pairs. We use this later to verify that
865  // each Name is reachable from the appropriate bucket.
866  std::vector<BucketInfo> BucketStarts;
867  BucketStarts.reserve(NI.getBucketCount() + 1);
868  for (uint32_t Bucket = 0, End = NI.getBucketCount(); Bucket < End; ++Bucket) {
869  uint32_t Index = NI.getBucketArrayEntry(Bucket);
870  if (Index > NI.getNameCount()) {
871  error() << formatv("Bucket {0} of Name Index @ {1:x} contains invalid "
872  "value {2}. Valid range is [0, {3}].\n",
873  Bucket, NI.getUnitOffset(), Index, NI.getNameCount());
874  ++NumErrors;
875  continue;
876  }
877  if (Index > 0)
878  BucketStarts.emplace_back(Bucket, Index);
879  }
880 
881  // If there were any buckets with invalid values, skip further checks as they
882  // will likely produce many errors which will only confuse the actual root
883  // problem.
884  if (NumErrors > 0)
885  return NumErrors;
886 
887  // Sort the list in the order of increasing "Index" entries.
888  array_pod_sort(BucketStarts.begin(), BucketStarts.end());
889 
890  // Insert a sentinel entry at the end, so we can check that the end of the
891  // table is covered in the loop below.
892  BucketStarts.emplace_back(NI.getBucketCount(), NI.getNameCount() + 1);
893 
894  // Loop invariant: NextUncovered is the (1-based) index of the first Name
895  // which is not reachable by any of the buckets we processed so far (and
896  // hasn't been reported as uncovered).
897  uint32_t NextUncovered = 1;
898  for (const BucketInfo &B : BucketStarts) {
899  // Under normal circumstances B.Index be equal to NextUncovered, but it can
900  // be less if a bucket points to names which are already known to be in some
901  // bucket we processed earlier. In that case, we won't trigger this error,
902  // but report the mismatched hash value error instead. (We know the hash
903  // will not match because we have already verified that the name's hash
904  // puts it into the previous bucket.)
905  if (B.Index > NextUncovered) {
906  error() << formatv("Name Index @ {0:x}: Name table entries [{1}, {2}] "
907  "are not covered by the hash table.\n",
908  NI.getUnitOffset(), NextUncovered, B.Index - 1);
909  ++NumErrors;
910  }
911  uint32_t Idx = B.Index;
912 
913  // The rest of the checks apply only to non-sentinel entries.
914  if (B.Bucket == NI.getBucketCount())
915  break;
916 
917  // This triggers if a non-empty bucket points to a name with a mismatched
918  // hash. Clients are likely to interpret this as an empty bucket, because a
919  // mismatched hash signals the end of a bucket, but if this is indeed an
920  // empty bucket, the producer should have signalled this by marking the
921  // bucket as empty.
922  uint32_t FirstHash = NI.getHashArrayEntry(Idx);
923  if (FirstHash % NI.getBucketCount() != B.Bucket) {
924  error() << formatv(
925  "Name Index @ {0:x}: Bucket {1} is not empty but points to a "
926  "mismatched hash value {2:x} (belonging to bucket {3}).\n",
927  NI.getUnitOffset(), B.Bucket, FirstHash,
928  FirstHash % NI.getBucketCount());
929  ++NumErrors;
930  }
931 
932  // This find the end of this bucket and also verifies that all the hashes in
933  // this bucket are correct by comparing the stored hashes to the ones we
934  // compute ourselves.
935  while (Idx <= NI.getNameCount()) {
936  uint32_t Hash = NI.getHashArrayEntry(Idx);
937  if (Hash % NI.getBucketCount() != B.Bucket)
938  break;
939 
940  const char *Str = NI.getNameTableEntry(Idx).getString();
941  if (caseFoldingDjbHash(Str) != Hash) {
942  error() << formatv("Name Index @ {0:x}: String ({1}) at index {2} "
943  "hashes to {3:x}, but "
944  "the Name Index hash is {4:x}\n",
945  NI.getUnitOffset(), Str, Idx,
946  caseFoldingDjbHash(Str), Hash);
947  ++NumErrors;
948  }
949 
950  ++Idx;
951  }
952  NextUncovered = std::max(NextUncovered, Idx);
953  }
954  return NumErrors;
955 }
956 
957 unsigned DWARFVerifier::verifyNameIndexAttribute(
960  StringRef FormName = dwarf::FormEncodingString(AttrEnc.Form);
961  if (FormName.empty()) {
962  error() << formatv("NameIndex @ {0:x}: Abbreviation {1:x}: {2} uses an "
963  "unknown form: {3}.\n",
964  NI.getUnitOffset(), Abbr.Code, AttrEnc.Index,
965  AttrEnc.Form);
966  return 1;
967  }
968 
969  if (AttrEnc.Index == DW_IDX_type_hash) {
970  if (AttrEnc.Form != dwarf::DW_FORM_data8) {
971  error() << formatv(
972  "NameIndex @ {0:x}: Abbreviation {1:x}: DW_IDX_type_hash "
973  "uses an unexpected form {2} (should be {3}).\n",
974  NI.getUnitOffset(), Abbr.Code, AttrEnc.Form, dwarf::DW_FORM_data8);
975  return 1;
976  }
977  }
978 
979  // A list of known index attributes and their expected form classes.
980  // DW_IDX_type_hash is handled specially in the check above, as it has a
981  // specific form (not just a form class) we should expect.
982  struct FormClassTable {
985  StringLiteral ClassName;
986  };
987  static constexpr FormClassTable Table[] = {
988  {dwarf::DW_IDX_compile_unit, DWARFFormValue::FC_Constant, {"constant"}},
989  {dwarf::DW_IDX_type_unit, DWARFFormValue::FC_Constant, {"constant"}},
990  {dwarf::DW_IDX_die_offset, DWARFFormValue::FC_Reference, {"reference"}},
991  {dwarf::DW_IDX_parent, DWARFFormValue::FC_Constant, {"constant"}},
992  };
993 
995  auto Iter = find_if(TableRef, [AttrEnc](const FormClassTable &T) {
996  return T.Index == AttrEnc.Index;
997  });
998  if (Iter == TableRef.end()) {
999  warn() << formatv("NameIndex @ {0:x}: Abbreviation {1:x} contains an "
1000  "unknown index attribute: {2}.\n",
1001  NI.getUnitOffset(), Abbr.Code, AttrEnc.Index);
1002  return 0;
1003  }
1004 
1005  if (!DWARFFormValue(AttrEnc.Form).isFormClass(Iter->Class)) {
1006  error() << formatv("NameIndex @ {0:x}: Abbreviation {1:x}: {2} uses an "
1007  "unexpected form {3} (expected form class {4}).\n",
1008  NI.getUnitOffset(), Abbr.Code, AttrEnc.Index,
1009  AttrEnc.Form, Iter->ClassName);
1010  return 1;
1011  }
1012  return 0;
1013 }
1014 
1015 unsigned
1016 DWARFVerifier::verifyNameIndexAbbrevs(const DWARFDebugNames::NameIndex &NI) {
1017  if (NI.getLocalTUCount() + NI.getForeignTUCount() > 0) {
1018  warn() << formatv("Name Index @ {0:x}: Verifying indexes of type units is "
1019  "not currently supported.\n",
1020  NI.getUnitOffset());
1021  return 0;
1022  }
1023 
1024  unsigned NumErrors = 0;
1025  for (const auto &Abbrev : NI.getAbbrevs()) {
1026  StringRef TagName = dwarf::TagString(Abbrev.Tag);
1027  if (TagName.empty()) {
1028  warn() << formatv("NameIndex @ {0:x}: Abbreviation {1:x} references an "
1029  "unknown tag: {2}.\n",
1030  NI.getUnitOffset(), Abbrev.Code, Abbrev.Tag);
1031  }
1032  SmallSet<unsigned, 5> Attributes;
1033  for (const auto &AttrEnc : Abbrev.Attributes) {
1034  if (!Attributes.insert(AttrEnc.Index).second) {
1035  error() << formatv("NameIndex @ {0:x}: Abbreviation {1:x} contains "
1036  "multiple {2} attributes.\n",
1037  NI.getUnitOffset(), Abbrev.Code, AttrEnc.Index);
1038  ++NumErrors;
1039  continue;
1040  }
1041  NumErrors += verifyNameIndexAttribute(NI, Abbrev, AttrEnc);
1042  }
1043 
1044  if (NI.getCUCount() > 1 && !Attributes.count(dwarf::DW_IDX_compile_unit)) {
1045  error() << formatv("NameIndex @ {0:x}: Indexing multiple compile units "
1046  "and abbreviation {1:x} has no {2} attribute.\n",
1047  NI.getUnitOffset(), Abbrev.Code,
1048  dwarf::DW_IDX_compile_unit);
1049  ++NumErrors;
1050  }
1051  if (!Attributes.count(dwarf::DW_IDX_die_offset)) {
1052  error() << formatv(
1053  "NameIndex @ {0:x}: Abbreviation {1:x} has no {2} attribute.\n",
1054  NI.getUnitOffset(), Abbrev.Code, dwarf::DW_IDX_die_offset);
1055  ++NumErrors;
1056  }
1057  }
1058  return NumErrors;
1059 }
1060 
1062  bool IncludeLinkageName = true) {
1064  if (const char *Str = DIE.getName(DINameKind::ShortName))
1065  Result.emplace_back(Str);
1066  else if (DIE.getTag() == dwarf::DW_TAG_namespace)
1067  Result.emplace_back("(anonymous namespace)");
1068 
1069  if (IncludeLinkageName) {
1070  if (const char *Str = DIE.getName(DINameKind::LinkageName)) {
1071  if (Result.empty() || Result[0] != Str)
1072  Result.emplace_back(Str);
1073  }
1074  }
1075 
1076  return Result;
1077 }
1078 
1079 unsigned DWARFVerifier::verifyNameIndexEntries(
1080  const DWARFDebugNames::NameIndex &NI,
1081  const DWARFDebugNames::NameTableEntry &NTE) {
1082  // Verifying type unit indexes not supported.
1083  if (NI.getLocalTUCount() + NI.getForeignTUCount() > 0)
1084  return 0;
1085 
1086  const char *CStr = NTE.getString();
1087  if (!CStr) {
1088  error() << formatv(
1089  "Name Index @ {0:x}: Unable to get string associated with name {1}.\n",
1090  NI.getUnitOffset(), NTE.getIndex());
1091  return 1;
1092  }
1093  StringRef Str(CStr);
1094 
1095  unsigned NumErrors = 0;
1096  unsigned NumEntries = 0;
1097  uint32_t EntryID = NTE.getEntryOffset();
1098  uint32_t NextEntryID = EntryID;
1099  Expected<DWARFDebugNames::Entry> EntryOr = NI.getEntry(&NextEntryID);
1100  for (; EntryOr; ++NumEntries, EntryID = NextEntryID,
1101  EntryOr = NI.getEntry(&NextEntryID)) {
1102  uint32_t CUIndex = *EntryOr->getCUIndex();
1103  if (CUIndex > NI.getCUCount()) {
1104  error() << formatv("Name Index @ {0:x}: Entry @ {1:x} contains an "
1105  "invalid CU index ({2}).\n",
1106  NI.getUnitOffset(), EntryID, CUIndex);
1107  ++NumErrors;
1108  continue;
1109  }
1110  uint32_t CUOffset = NI.getCUOffset(CUIndex);
1111  uint64_t DIEOffset = CUOffset + *EntryOr->getDIEUnitOffset();
1112  DWARFDie DIE = DCtx.getDIEForOffset(DIEOffset);
1113  if (!DIE) {
1114  error() << formatv("Name Index @ {0:x}: Entry @ {1:x} references a "
1115  "non-existing DIE @ {2:x}.\n",
1116  NI.getUnitOffset(), EntryID, DIEOffset);
1117  ++NumErrors;
1118  continue;
1119  }
1120  if (DIE.getDwarfUnit()->getOffset() != CUOffset) {
1121  error() << formatv("Name Index @ {0:x}: Entry @ {1:x}: mismatched CU of "
1122  "DIE @ {2:x}: index - {3:x}; debug_info - {4:x}.\n",
1123  NI.getUnitOffset(), EntryID, DIEOffset, CUOffset,
1124  DIE.getDwarfUnit()->getOffset());
1125  ++NumErrors;
1126  }
1127  if (DIE.getTag() != EntryOr->tag()) {
1128  error() << formatv("Name Index @ {0:x}: Entry @ {1:x}: mismatched Tag of "
1129  "DIE @ {2:x}: index - {3}; debug_info - {4}.\n",
1130  NI.getUnitOffset(), EntryID, DIEOffset, EntryOr->tag(),
1131  DIE.getTag());
1132  ++NumErrors;
1133  }
1134 
1135  auto EntryNames = getNames(DIE);
1136  if (!is_contained(EntryNames, Str)) {
1137  error() << formatv("Name Index @ {0:x}: Entry @ {1:x}: mismatched Name "
1138  "of DIE @ {2:x}: index - {3}; debug_info - {4}.\n",
1139  NI.getUnitOffset(), EntryID, DIEOffset, Str,
1140  make_range(EntryNames.begin(), EntryNames.end()));
1141  ++NumErrors;
1142  }
1143  }
1144  handleAllErrors(EntryOr.takeError(),
1145  [&](const DWARFDebugNames::SentinelError &) {
1146  if (NumEntries > 0)
1147  return;
1148  error() << formatv("Name Index @ {0:x}: Name {1} ({2}) is "
1149  "not associated with any entries.\n",
1150  NI.getUnitOffset(), NTE.getIndex(), Str);
1151  ++NumErrors;
1152  },
1153  [&](const ErrorInfoBase &Info) {
1154  error()
1155  << formatv("Name Index @ {0:x}: Name {1} ({2}): {3}\n",
1156  NI.getUnitOffset(), NTE.getIndex(), Str,
1157  Info.message());
1158  ++NumErrors;
1159  });
1160  return NumErrors;
1161 }
1162 
1163 static bool isVariableIndexable(const DWARFDie &Die, DWARFContext &DCtx) {
1164  Optional<DWARFFormValue> Location = Die.findRecursively(DW_AT_location);
1165  if (!Location)
1166  return false;
1167 
1168  auto ContainsInterestingOperators = [&](StringRef D) {
1169  DWARFUnit *U = Die.getDwarfUnit();
1171  DWARFExpression Expression(Data, U->getVersion(), U->getAddressByteSize());
1172  return any_of(Expression, [](DWARFExpression::Operation &Op) {
1173  return !Op.isError() && (Op.getCode() == DW_OP_addr ||
1174  Op.getCode() == DW_OP_form_tls_address ||
1175  Op.getCode() == DW_OP_GNU_push_tls_address);
1176  });
1177  };
1178 
1179  if (Optional<ArrayRef<uint8_t>> Expr = Location->getAsBlock()) {
1180  // Inlined location.
1181  if (ContainsInterestingOperators(toStringRef(*Expr)))
1182  return true;
1183  } else if (Optional<uint64_t> Offset = Location->getAsSectionOffset()) {
1184  // Location list.
1185  if (const DWARFDebugLoc *DebugLoc = DCtx.getDebugLoc()) {
1186  if (const DWARFDebugLoc::LocationList *LocList =
1187  DebugLoc->getLocationListAtOffset(*Offset)) {
1188  if (any_of(LocList->Entries, [&](const DWARFDebugLoc::Entry &E) {
1189  return ContainsInterestingOperators({E.Loc.data(), E.Loc.size()});
1190  }))
1191  return true;
1192  }
1193  }
1194  }
1195  return false;
1196 }
1197 
1198 unsigned DWARFVerifier::verifyNameIndexCompleteness(
1199  const DWARFDie &Die, const DWARFDebugNames::NameIndex &NI) {
1200 
1201  // First check, if the Die should be indexed. The code follows the DWARF v5
1202  // wording as closely as possible.
1203 
1204  // "All non-defining declarations (that is, debugging information entries
1205  // with a DW_AT_declaration attribute) are excluded."
1206  if (Die.find(DW_AT_declaration))
1207  return 0;
1208 
1209  // "DW_TAG_namespace debugging information entries without a DW_AT_name
1210  // attribute are included with the name “(anonymous namespace)”.
1211  // All other debugging information entries without a DW_AT_name attribute
1212  // are excluded."
1213  // "If a subprogram or inlined subroutine is included, and has a
1214  // DW_AT_linkage_name attribute, there will be an additional index entry for
1215  // the linkage name."
1216  auto IncludeLinkageName = Die.getTag() == DW_TAG_subprogram ||
1217  Die.getTag() == DW_TAG_inlined_subroutine;
1218  auto EntryNames = getNames(Die, IncludeLinkageName);
1219  if (EntryNames.empty())
1220  return 0;
1221 
1222  // We deviate from the specification here, which says:
1223  // "The name index must contain an entry for each debugging information entry
1224  // that defines a named subprogram, label, variable, type, or namespace,
1225  // subject to ..."
1226  // Instead whitelisting all TAGs representing a "type" or a "subprogram", to
1227  // make sure we catch any missing items, we instead blacklist all TAGs that we
1228  // know shouldn't be indexed.
1229  switch (Die.getTag()) {
1230  // Compile units and modules have names but shouldn't be indexed.
1231  case DW_TAG_compile_unit:
1232  case DW_TAG_module:
1233  return 0;
1234 
1235  // Function and template parameters are not globally visible, so we shouldn't
1236  // index them.
1237  case DW_TAG_formal_parameter:
1238  case DW_TAG_template_value_parameter:
1239  case DW_TAG_template_type_parameter:
1240  case DW_TAG_GNU_template_parameter_pack:
1241  case DW_TAG_GNU_template_template_param:
1242  return 0;
1243 
1244  // Object members aren't globally visible.
1245  case DW_TAG_member:
1246  return 0;
1247 
1248  // According to a strict reading of the specification, enumerators should not
1249  // be indexed (and LLVM currently does not do that). However, this causes
1250  // problems for the debuggers, so we may need to reconsider this.
1251  case DW_TAG_enumerator:
1252  return 0;
1253 
1254  // Imported declarations should not be indexed according to the specification
1255  // and LLVM currently does not do that.
1256  case DW_TAG_imported_declaration:
1257  return 0;
1258 
1259  // "DW_TAG_subprogram, DW_TAG_inlined_subroutine, and DW_TAG_label debugging
1260  // information entries without an address attribute (DW_AT_low_pc,
1261  // DW_AT_high_pc, DW_AT_ranges, or DW_AT_entry_pc) are excluded."
1262  case DW_TAG_subprogram:
1263  case DW_TAG_inlined_subroutine:
1264  case DW_TAG_label:
1265  if (Die.findRecursively(
1266  {DW_AT_low_pc, DW_AT_high_pc, DW_AT_ranges, DW_AT_entry_pc}))
1267  break;
1268  return 0;
1269 
1270  // "DW_TAG_variable debugging information entries with a DW_AT_location
1271  // attribute that includes a DW_OP_addr or DW_OP_form_tls_address operator are
1272  // included; otherwise, they are excluded."
1273  //
1274  // LLVM extension: We also add DW_OP_GNU_push_tls_address to this list.
1275  case DW_TAG_variable:
1276  if (isVariableIndexable(Die, DCtx))
1277  break;
1278  return 0;
1279 
1280  default:
1281  break;
1282  }
1283 
1284  // Now we know that our Die should be present in the Index. Let's check if
1285  // that's the case.
1286  unsigned NumErrors = 0;
1287  uint64_t DieUnitOffset = Die.getOffset() - Die.getDwarfUnit()->getOffset();
1288  for (StringRef Name : EntryNames) {
1289  if (none_of(NI.equal_range(Name), [&](const DWARFDebugNames::Entry &E) {
1290  return E.getDIEUnitOffset() == DieUnitOffset;
1291  })) {
1292  error() << formatv("Name Index @ {0:x}: Entry for DIE @ {1:x} ({2}) with "
1293  "name {3} missing.\n",
1294  NI.getUnitOffset(), Die.getOffset(), Die.getTag(),
1295  Name);
1296  ++NumErrors;
1297  }
1298  }
1299  return NumErrors;
1300 }
1301 
1302 unsigned DWARFVerifier::verifyDebugNames(const DWARFSection &AccelSection,
1303  const DataExtractor &StrData) {
1304  unsigned NumErrors = 0;
1305  DWARFDataExtractor AccelSectionData(DCtx.getDWARFObj(), AccelSection,
1306  DCtx.isLittleEndian(), 0);
1307  DWARFDebugNames AccelTable(AccelSectionData, StrData);
1308 
1309  OS << "Verifying .debug_names...\n";
1310 
1311  // This verifies that we can read individual name indices and their
1312  // abbreviation tables.
1313  if (Error E = AccelTable.extract()) {
1314  error() << toString(std::move(E)) << '\n';
1315  return 1;
1316  }
1317 
1318  NumErrors += verifyDebugNamesCULists(AccelTable);
1319  for (const auto &NI : AccelTable)
1320  NumErrors += verifyNameIndexBuckets(NI, StrData);
1321  for (const auto &NI : AccelTable)
1322  NumErrors += verifyNameIndexAbbrevs(NI);
1323 
1324  // Don't attempt Entry validation if any of the previous checks found errors
1325  if (NumErrors > 0)
1326  return NumErrors;
1327  for (const auto &NI : AccelTable)
1328  for (DWARFDebugNames::NameTableEntry NTE : NI)
1329  NumErrors += verifyNameIndexEntries(NI, NTE);
1330 
1331  if (NumErrors > 0)
1332  return NumErrors;
1333 
1334  for (const std::unique_ptr<DWARFUnit> &U : DCtx.compile_units()) {
1335  if (const DWARFDebugNames::NameIndex *NI =
1336  AccelTable.getCUNameIndex(U->getOffset())) {
1337  auto *CU = cast<DWARFCompileUnit>(U.get());
1338  for (const DWARFDebugInfoEntry &Die : CU->dies())
1339  NumErrors += verifyNameIndexCompleteness(DWARFDie(CU, &Die), *NI);
1340  }
1341  }
1342  return NumErrors;
1343 }
1344 
1346  const DWARFObject &D = DCtx.getDWARFObj();
1347  DataExtractor StrData(D.getStringSection(), DCtx.isLittleEndian(), 0);
1348  unsigned NumErrors = 0;
1349  if (!D.getAppleNamesSection().Data.empty())
1350  NumErrors += verifyAppleAccelTable(&D.getAppleNamesSection(), &StrData,
1351  ".apple_names");
1352  if (!D.getAppleTypesSection().Data.empty())
1353  NumErrors += verifyAppleAccelTable(&D.getAppleTypesSection(), &StrData,
1354  ".apple_types");
1356  NumErrors += verifyAppleAccelTable(&D.getAppleNamespacesSection(), &StrData,
1357  ".apple_namespaces");
1358  if (!D.getAppleObjCSection().Data.empty())
1359  NumErrors += verifyAppleAccelTable(&D.getAppleObjCSection(), &StrData,
1360  ".apple_objc");
1361 
1362  if (!D.getDebugNamesSection().Data.empty())
1363  NumErrors += verifyDebugNames(D.getDebugNamesSection(), StrData);
1364  return NumErrors == 0;
1365 }
1366 
1367 raw_ostream &DWARFVerifier::error() const { return WithColor::error(OS); }
1368 
1369 raw_ostream &DWARFVerifier::warn() const { return WithColor::warning(OS); }
1370 
1371 raw_ostream &DWARFVerifier::note() const { return WithColor::note(OS); }
A list of locations that contain one variable.
Definition: DWARFDebugLoc.h:37
static bool isMatchingUnitTypeAndTag(uint8_t UnitType, dwarf::Tag Tag)
Definition: DWARFUnit.h:334
DWARFUnit * getDwarfUnit() const
Definition: DWARFDie.h:54
uint32_t getEntryOffset() const
Returns the offset of the first Entry in the list.
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
bool isValid() const
Definition: DWARFDie.h:51
virtual void forEachTypesSections(function_ref< void(const DWARFSection &)> F) const
Definition: DWARFObject.h:38
dwarf::Attribute Attr
The attribute enumeration of this attribute.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
const DWARFDebugLoc * getDebugLoc()
Get a pointer to the parsed DebugLoc object.
virtual StringRef getAbbrevSection() const
Definition: DWARFObject.h:39
bool isUnitType(uint8_t UnitType)
Definition: Dwarf.h:341
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE size_t size() const
size - Get the string size.
Definition: StringRef.h:138
static raw_ostream & error()
Convenience method for printing "error: " to stderr.
Definition: WithColor.cpp:63
This class holds an abstract representation of an Accelerator Table, consisting of a sequence of buck...
Definition: AccelTable.h:199
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition: Format.h:124
bool handleDebugLine()
Verify the information in the .debug_line section.
iterator find(StringRef Key)
Definition: StringMap.h:333
auto formatv(const char *Fmt, Ts &&... Vals) -> formatv_object< decltype(std::make_tuple(detail::build_format_adapter(std::forward< Ts >(Vals))...))>
static raw_ostream & warning()
Convenience method for printing "warning: " to stderr.
Definition: WithColor.cpp:65
#define error(X)
A debug info location.
Definition: DebugLoc.h:34
static SmallVector< StringRef, 2 > getNames(const DWARFDie &DIE, bool IncludeLinkageName=true)
This class represents an Operation in the Expression.
uint16_t getU16(uint32_t *offset_ptr) const
Extract a uint16_t value from *offset_ptr.
bool isFormClass(FormClass FC) const
Base class for error info classes.
Definition: Error.h:49
void dump(raw_ostream &OS, unsigned indent=0, DIDumpOptions DumpOpts=DIDumpOptions()) const
Dump the DIE and all of its attributes to the supplied stream.
Definition: DWARFDie.cpp:484
virtual StringRef getAbbrevDWOSection() const
Definition: DWARFObject.h:58
Abbreviation describing the encoding of Name Index entries.
virtual const DWARFSection & getAppleTypesSection() const
Definition: DWARFObject.h:69
bool handleDebugInfo()
Verify the information in the .debug_info and .debug_types sections.
dwarf::Form getForm() const
DWARFFormValue Value
The form and value for this attribute.
uint32_t getNextUnitOffset() const
Definition: DWARFUnit.h:280
Optional< uint64_t > getAsReference() const
getAsFoo functions below return the extracted value as Foo if only DWARFFormValue has form class is s...
uint32_t getU32(uint32_t *offset_ptr) const
Extract a uint32_t value from *offset_ptr.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
uint64_t getRawUValue() const
Optional< ArrayRef< uint8_t > > getAsBlock() const
StringRef FormEncodingString(unsigned Encoding)
Definition: Dwarf.cpp:105
static bool isVariableIndexable(const DWARFDie &Die, DWARFContext &DCtx)
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1056
A single location within a location list.
Definition: DWARFDebugLoc.h:27
static raw_ostream & note()
Convenience method for printing "note: " to stderr.
Definition: WithColor.cpp:67
Tagged union holding either a T or a Error.
Definition: CachePruning.h:23
Index attribute and its encoding.
uint32_t getOffset() const
Get the absolute offset into the debug info or types section.
Definition: DWARFDie.h:67
uint8_t getAddressByteSize() const
Definition: DWARFUnit.h:272
std::set< DieRangeInfo > Children
Sorted DWARFAddressRangeInfo.
Definition: DWARFVerifier.h:46
unsigned getNumDIEs()
Returns the number of DIEs in the unit.
Definition: DWARFUnit.h:423
std::vector< DWARFAddressRange > Ranges
Sorted DWARFAddressRanges.
Definition: DWARFVerifier.h:43
Encapsulates a DWARF attribute value and all of the data required to describe the attribute value...
StringRef AttributeString(unsigned Attribute)
Definition: Dwarf.cpp:72
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE bool empty() const
empty - Check if the string is empty.
Definition: StringRef.h:133
const DenseSet< Abbrev, AbbrevMapInfo > & getAbbrevs() const
auto lower_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range))
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1138
Represents a single accelerator table within the Dwarf 5 .debug_names section.
uint32_t getBucketArrayEntry(uint32_t Bucket) const
Reads an entry in the Bucket Array for the given Bucket.
uint16_t getVersion() const
Definition: DWARFUnit.h:271
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:146
Optional< uint64_t > toSectionOffset(const Optional< DWARFFormValue > &V)
Take an optional DWARFFormValue and try to extract an section offset.
virtual const DWARFSection & getAppleObjCSection() const
Definition: DWARFObject.h:74
A wrapper around a string literal that serves as a proxy for constructing global tables of StringRefs...
Definition: StringRef.h:869
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
Definition: STLExtras.h:939
Utility class that carries the DWARF compile/type unit and the debug info entry in an object...
Definition: DWARFDie.h:43
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
DWARF v5-specific implementation of an Accelerator Entry.
This implements the Apple accelerator table format, a precursor of the DWARF 5 accelerator table form...
virtual const DWARFSection & getStringOffsetSection() const
Definition: DWARFObject.h:54
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
DWARFSectionKind
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
A structured debug information entry.
Definition: DIE.h:662
Optional< DWARFFormValue > findRecursively(ArrayRef< dwarf::Attribute > Attrs) const
Extract the first value of any attribute in Attrs from this DIE and recurse into any DW_AT_specificat...
Definition: DWARFDie.cpp:317
bool handleDebugAbbrev()
Verify the information in any of the following sections, if available: .debug_abbrev, debug_abbrev.dwo.
NameTableEntry getNameTableEntry(uint32_t Index) const
Reads an entry in the Name Table for the given Index.
A class that keeps the address range information for a single DIE.
Definition: DWARFVerifier.h:39
const DWARFAbbreviationDeclarationSet * getAbbreviationDeclarationSet(uint64_t CUAbbrOffset) const
bool any_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1049
uint32_t getHashArrayEntry(uint32_t Index) const
Reads an entry in the Hash Array for the given Index.
bool contains(const DieRangeInfo &RHS) const
Return true if ranges in this object contains all ranges within RHS.
uint8_t getU8(uint32_t *offset_ptr) const
Extract a uint8_t value from *offset_ptr.
SectionKind - This is a simple POD value that classifies the properties of a section.
Definition: SectionKind.h:23
virtual StringRef getStringSection() const
Definition: DWARFObject.h:46
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again...
Definition: DenseMap.h:100
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1070
bool extract(DWARFContext &Context, const DWARFDataExtractor &debug_info, uint32_t *offset_ptr, DWARFSectionKind Kind=DW_SECT_INFO, const DWARFUnitIndex *Index=nullptr)
Parse a unit header from debug_info starting at offset_ptr.
Definition: DWARFUnit.cpp:202
Expected< Entry > getEntry(uint32_t *Offset) const
std::vector< DWARFAddressRange >::const_iterator address_range_iterator
Definition: DWARFVerifier.h:56
StringRef toStringRef(bool B)
Construct a string ref from a boolean.
Definition: StringExtras.h:53
void consumeError(Error Err)
Consume a Error without doing anything.
Definition: Error.h:978
Base class describing the header of any kind of "unit." Some information is specific to certain unit ...
Definition: DWARFUnit.h:47
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
UnitType
Constants for unit types in DWARF v5.
Definition: Dwarf.h:327
A DataExtractor (typically for an in-memory copy of an object-file section) plus a relocation map for...
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
const char * getString() const
Return the string referenced by this name table entry or nullptr if the string offset is not valid...
.debug_names section consists of one or more units.
void handleAllErrors(Error E, HandlerTs &&... Handlers)
Behaves the same as handleErrors, except that by contract all errors must be handled by the given han...
Definition: Error.h:905
DWARFDie getUnitDIE(bool ExtractUnitDIEOnly=true)
Definition: DWARFUnit.h:373
const char * getName(DINameKind Kind) const
Return the DIE name resolving DW_AT_sepcification or DW_AT_abstract_origin references if necessary...
Definition: DWARFDie.cpp:446
A single entry in the Name Table (Dwarf 5 sect.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
uint32_t caseFoldingDjbHash(StringRef Buffer, uint32_t H=5381)
Computes the Bernstein hash after folding the input according to the Dwarf 5 standard case folding ru...
Definition: DJB.cpp:71
address_range_iterator insert(const DWARFAddressRange &R)
Inserts the address range.
iterator end() const
Definition: ArrayRef.h:138
DWARFContext This data structure is the top level entity that deals with dwarf debug information pars...
Definition: DWARFContext.h:59
uint32_t getIndex() const
Return the index of this name in the parent Name Index.
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static void dumpTableHeader(raw_ostream &OS)
Describe a collection of units.
Definition: DWARFUnit.h:109
Optional< const char * > toString(const Optional< DWARFFormValue > &V)
Take an optional DWARFFormValue and try to extract a string value from it.
Implements a dense probed hash-table based set with some number of buckets stored inline...
Definition: DenseSet.h:239
StringMap - This is an unconventional map that is specialized for handling keys that are "strings"...
Definition: StringMap.h:220
StringRef UnitTypeString(unsigned)
Definition: Dwarf.cpp:480
Error returned by NameIndex::getEntry to report it has reached the end of the entry list...
virtual const DWARFSection & getAppleNamespacesSection() const
Definition: DWARFObject.h:70
#define Success
virtual const DWARFSection & getInfoSection() const
Definition: DWARFObject.h:36
virtual const DWARFSection & getLineSection() const
Definition: DWARFObject.h:44
bool intersects(const DieRangeInfo &RHS) const
Return true if any range in this object intersects with any range in RHS.
StringRef TagString(unsigned Tag)
Definition: Dwarf.cpp:21
virtual const DWARFSection & getDebugNamesSection() const
Definition: DWARFObject.h:73
static bool isSupportedVersion(unsigned version)
Definition: DWARFContext.h:321
DWARFDie getDIEAtIndex(unsigned Index)
Return the DIE object at the given index.
Definition: DWARFUnit.h:439
void emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:652
dwarf::Tag getTag() const
Definition: DWARFDie.h:72
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
bool handleAccelTables()
Verify the information in accelerator tables, if they exist.
#define I(x, y, z)
Definition: MD5.cpp:58
virtual const DWARFSection & getAppleNamesSection() const
Definition: DWARFObject.h:68
const char * getCStr(uint32_t *offset_ptr) const
Extract a C string from *offset_ptr.
iterator end()
Definition: DenseMap.h:79
uint32_t getOffset() const
Definition: DWARFUnit.h:267
Expected< DWARFAddressRangesVector > getAddressRanges() const
Get the address ranges for this DIE.
Definition: DWARFDie.cpp:394
std::set< DieRangeInfo >::const_iterator die_range_info_iterator
Definition: DWARFVerifier.h:57
bool isLittleEndian() const
Definition: DWARFContext.h:320
bool isValidOffset(uint32_t offset) const
Test the validity of offset.
virtual const DWARFSection & getRangeSection() const
Definition: DWARFObject.h:47
uint8_t getUnitType() const
Definition: DWARFUnit.h:278
uint32_t Code
Abbreviation code.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:326
Optional< DWARFFormValue > find(dwarf::Attribute Attr) const
Extract the specified attribute from this DIE.
Definition: DWARFDie.cpp:293
std::vector< DWARFAddressRange > DWARFAddressRangesVector
DWARFAddressRangesVector - represents a set of absolute address ranges.
DWARFDebugInfoEntry - A DIE with only the minimum required data.
Lightweight error class with error context and mandatory checking.
Definition: Error.h:158
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
static void LLVM_ATTRIBUTE_NORETURN ReportError(uint32_t StartOffset, const char *ErrorMsg)
uint32_t getCUOffset(uint32_t CU) const
Reads offset of compilation unit CU. CU is 0-based.
iterator_range< ValueIterator > equal_range(StringRef Key) const
Look up all entries in this Name Index matching Key.
Optional< uint64_t > getAsSectionOffset() const
const uint64_t Version
Definition: InstrProf.h:895
iterator end()
Definition: StringMap.h:318
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1101