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