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