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