1 //===- DWARFAcceleratorTable.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
9 #include "llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h"
10
11 #include "llvm/ADT/SmallVector.h"
12 #include "llvm/BinaryFormat/Dwarf.h"
13 #include "llvm/Support/Compiler.h"
14 #include "llvm/Support/DJB.h"
15 #include "llvm/Support/Errc.h"
16 #include "llvm/Support/Format.h"
17 #include "llvm/Support/FormatVariadic.h"
18 #include "llvm/Support/ScopedPrinter.h"
19 #include "llvm/Support/raw_ostream.h"
20 #include <cstddef>
21 #include <cstdint>
22 #include <utility>
23
24 using namespace llvm;
25
26 namespace {
27 struct Atom {
28 unsigned Value;
29 };
30
operator <<(raw_ostream & OS,const Atom & A)31 static raw_ostream &operator<<(raw_ostream &OS, const Atom &A) {
32 StringRef Str = dwarf::AtomTypeString(A.Value);
33 if (!Str.empty())
34 return OS << Str;
35 return OS << "DW_ATOM_unknown_" << format("%x", A.Value);
36 }
37 } // namespace
38
formatAtom(unsigned Atom)39 static Atom formatAtom(unsigned Atom) { return {Atom}; }
40
41 DWARFAcceleratorTable::~DWARFAcceleratorTable() = default;
42
extract()43 Error AppleAcceleratorTable::extract() {
44 uint64_t Offset = 0;
45
46 // Check that we can at least read the header.
47 if (!AccelSection.isValidOffset(offsetof(Header, HeaderDataLength) + 4))
48 return createStringError(errc::illegal_byte_sequence,
49 "Section too small: cannot read header.");
50
51 Hdr.Magic = AccelSection.getU32(&Offset);
52 Hdr.Version = AccelSection.getU16(&Offset);
53 Hdr.HashFunction = AccelSection.getU16(&Offset);
54 Hdr.BucketCount = AccelSection.getU32(&Offset);
55 Hdr.HashCount = AccelSection.getU32(&Offset);
56 Hdr.HeaderDataLength = AccelSection.getU32(&Offset);
57
58 // Check that we can read all the hashes and offsets from the
59 // section (see SourceLevelDebugging.rst for the structure of the index).
60 // We need to substract one because we're checking for an *offset* which is
61 // equal to the size for an empty table and hence pointer after the section.
62 if (!AccelSection.isValidOffset(sizeof(Hdr) + Hdr.HeaderDataLength +
63 Hdr.BucketCount * 4 + Hdr.HashCount * 8 - 1))
64 return createStringError(
65 errc::illegal_byte_sequence,
66 "Section too small: cannot read buckets and hashes.");
67
68 HdrData.DIEOffsetBase = AccelSection.getU32(&Offset);
69 uint32_t NumAtoms = AccelSection.getU32(&Offset);
70
71 for (unsigned i = 0; i < NumAtoms; ++i) {
72 uint16_t AtomType = AccelSection.getU16(&Offset);
73 auto AtomForm = static_cast<dwarf::Form>(AccelSection.getU16(&Offset));
74 HdrData.Atoms.push_back(std::make_pair(AtomType, AtomForm));
75 }
76
77 IsValid = true;
78 return Error::success();
79 }
80
getNumBuckets()81 uint32_t AppleAcceleratorTable::getNumBuckets() { return Hdr.BucketCount; }
getNumHashes()82 uint32_t AppleAcceleratorTable::getNumHashes() { return Hdr.HashCount; }
getSizeHdr()83 uint32_t AppleAcceleratorTable::getSizeHdr() { return sizeof(Hdr); }
getHeaderDataLength()84 uint32_t AppleAcceleratorTable::getHeaderDataLength() {
85 return Hdr.HeaderDataLength;
86 }
87
88 ArrayRef<std::pair<AppleAcceleratorTable::HeaderData::AtomType,
89 AppleAcceleratorTable::HeaderData::Form>>
getAtomsDesc()90 AppleAcceleratorTable::getAtomsDesc() {
91 return HdrData.Atoms;
92 }
93
validateForms()94 bool AppleAcceleratorTable::validateForms() {
95 for (auto Atom : getAtomsDesc()) {
96 DWARFFormValue FormValue(Atom.second);
97 switch (Atom.first) {
98 case dwarf::DW_ATOM_die_offset:
99 case dwarf::DW_ATOM_die_tag:
100 case dwarf::DW_ATOM_type_flags:
101 if ((!FormValue.isFormClass(DWARFFormValue::FC_Constant) &&
102 !FormValue.isFormClass(DWARFFormValue::FC_Flag)) ||
103 FormValue.getForm() == dwarf::DW_FORM_sdata)
104 return false;
105 break;
106 default:
107 break;
108 }
109 }
110 return true;
111 }
112
113 std::pair<uint64_t, dwarf::Tag>
readAtoms(uint64_t * HashDataOffset)114 AppleAcceleratorTable::readAtoms(uint64_t *HashDataOffset) {
115 uint64_t DieOffset = dwarf::DW_INVALID_OFFSET;
116 dwarf::Tag DieTag = dwarf::DW_TAG_null;
117 dwarf::FormParams FormParams = {Hdr.Version, 0, dwarf::DwarfFormat::DWARF32};
118
119 for (auto Atom : getAtomsDesc()) {
120 DWARFFormValue FormValue(Atom.second);
121 FormValue.extractValue(AccelSection, HashDataOffset, FormParams);
122 switch (Atom.first) {
123 case dwarf::DW_ATOM_die_offset:
124 DieOffset = *FormValue.getAsUnsignedConstant();
125 break;
126 case dwarf::DW_ATOM_die_tag:
127 DieTag = (dwarf::Tag)*FormValue.getAsUnsignedConstant();
128 break;
129 default:
130 break;
131 }
132 }
133 return {DieOffset, DieTag};
134 }
135
dump(ScopedPrinter & W) const136 void AppleAcceleratorTable::Header::dump(ScopedPrinter &W) const {
137 DictScope HeaderScope(W, "Header");
138 W.printHex("Magic", Magic);
139 W.printHex("Version", Version);
140 W.printHex("Hash function", HashFunction);
141 W.printNumber("Bucket count", BucketCount);
142 W.printNumber("Hashes count", HashCount);
143 W.printNumber("HeaderData length", HeaderDataLength);
144 }
145
extractOffset(std::optional<DWARFFormValue> Value) const146 std::optional<uint64_t> AppleAcceleratorTable::HeaderData::extractOffset(
147 std::optional<DWARFFormValue> Value) const {
148 if (!Value)
149 return std::nullopt;
150
151 switch (Value->getForm()) {
152 case dwarf::DW_FORM_ref1:
153 case dwarf::DW_FORM_ref2:
154 case dwarf::DW_FORM_ref4:
155 case dwarf::DW_FORM_ref8:
156 case dwarf::DW_FORM_ref_udata:
157 return Value->getRawUValue() + DIEOffsetBase;
158 default:
159 return Value->getAsSectionOffset();
160 }
161 }
162
dumpName(ScopedPrinter & W,SmallVectorImpl<DWARFFormValue> & AtomForms,uint64_t * DataOffset) const163 bool AppleAcceleratorTable::dumpName(ScopedPrinter &W,
164 SmallVectorImpl<DWARFFormValue> &AtomForms,
165 uint64_t *DataOffset) const {
166 dwarf::FormParams FormParams = {Hdr.Version, 0, dwarf::DwarfFormat::DWARF32};
167 uint64_t NameOffset = *DataOffset;
168 if (!AccelSection.isValidOffsetForDataOfSize(*DataOffset, 4)) {
169 W.printString("Incorrectly terminated list.");
170 return false;
171 }
172 uint64_t StringOffset = AccelSection.getRelocatedValue(4, DataOffset);
173 if (!StringOffset)
174 return false; // End of list
175
176 DictScope NameScope(W, ("Name@0x" + Twine::utohexstr(NameOffset)).str());
177 W.startLine() << format("String: 0x%08" PRIx64, StringOffset);
178 W.getOStream() << " \"" << StringSection.getCStr(&StringOffset) << "\"\n";
179
180 unsigned NumData = AccelSection.getU32(DataOffset);
181 for (unsigned Data = 0; Data < NumData; ++Data) {
182 ListScope DataScope(W, ("Data " + Twine(Data)).str());
183 unsigned i = 0;
184 for (auto &Atom : AtomForms) {
185 W.startLine() << format("Atom[%d]: ", i);
186 if (Atom.extractValue(AccelSection, DataOffset, FormParams)) {
187 Atom.dump(W.getOStream());
188 if (std::optional<uint64_t> Val = Atom.getAsUnsignedConstant()) {
189 StringRef Str = dwarf::AtomValueString(HdrData.Atoms[i].first, *Val);
190 if (!Str.empty())
191 W.getOStream() << " (" << Str << ")";
192 }
193 } else
194 W.getOStream() << "Error extracting the value";
195 W.getOStream() << "\n";
196 i++;
197 }
198 }
199 return true; // more entries follow
200 }
201
dump(raw_ostream & OS) const202 LLVM_DUMP_METHOD void AppleAcceleratorTable::dump(raw_ostream &OS) const {
203 if (!IsValid)
204 return;
205
206 ScopedPrinter W(OS);
207
208 Hdr.dump(W);
209
210 W.printNumber("DIE offset base", HdrData.DIEOffsetBase);
211 W.printNumber("Number of atoms", uint64_t(HdrData.Atoms.size()));
212 SmallVector<DWARFFormValue, 3> AtomForms;
213 {
214 ListScope AtomsScope(W, "Atoms");
215 unsigned i = 0;
216 for (const auto &Atom : HdrData.Atoms) {
217 DictScope AtomScope(W, ("Atom " + Twine(i++)).str());
218 W.startLine() << "Type: " << formatAtom(Atom.first) << '\n';
219 W.startLine() << "Form: " << formatv("{0}", Atom.second) << '\n';
220 AtomForms.push_back(DWARFFormValue(Atom.second));
221 }
222 }
223
224 // Now go through the actual tables and dump them.
225 uint64_t Offset = sizeof(Hdr) + Hdr.HeaderDataLength;
226 uint64_t HashesBase = Offset + Hdr.BucketCount * 4;
227 uint64_t OffsetsBase = HashesBase + Hdr.HashCount * 4;
228
229 for (unsigned Bucket = 0; Bucket < Hdr.BucketCount; ++Bucket) {
230 unsigned Index = AccelSection.getU32(&Offset);
231
232 ListScope BucketScope(W, ("Bucket " + Twine(Bucket)).str());
233 if (Index == UINT32_MAX) {
234 W.printString("EMPTY");
235 continue;
236 }
237
238 for (unsigned HashIdx = Index; HashIdx < Hdr.HashCount; ++HashIdx) {
239 uint64_t HashOffset = HashesBase + HashIdx*4;
240 uint64_t OffsetsOffset = OffsetsBase + HashIdx*4;
241 uint32_t Hash = AccelSection.getU32(&HashOffset);
242
243 if (Hash % Hdr.BucketCount != Bucket)
244 break;
245
246 uint64_t DataOffset = AccelSection.getU32(&OffsetsOffset);
247 ListScope HashScope(W, ("Hash 0x" + Twine::utohexstr(Hash)).str());
248 if (!AccelSection.isValidOffset(DataOffset)) {
249 W.printString("Invalid section offset");
250 continue;
251 }
252 while (dumpName(W, AtomForms, &DataOffset))
253 /*empty*/;
254 }
255 }
256 }
257
Entry(const AppleAcceleratorTable::HeaderData & HdrData)258 AppleAcceleratorTable::Entry::Entry(
259 const AppleAcceleratorTable::HeaderData &HdrData)
260 : HdrData(&HdrData) {
261 Values.reserve(HdrData.Atoms.size());
262 for (const auto &Atom : HdrData.Atoms)
263 Values.push_back(DWARFFormValue(Atom.second));
264 }
265
extract(const AppleAcceleratorTable & AccelTable,uint64_t * Offset)266 void AppleAcceleratorTable::Entry::extract(
267 const AppleAcceleratorTable &AccelTable, uint64_t *Offset) {
268
269 dwarf::FormParams FormParams = {AccelTable.Hdr.Version, 0,
270 dwarf::DwarfFormat::DWARF32};
271 for (auto &Atom : Values)
272 Atom.extractValue(AccelTable.AccelSection, Offset, FormParams);
273 }
274
275 std::optional<DWARFFormValue>
lookup(HeaderData::AtomType Atom) const276 AppleAcceleratorTable::Entry::lookup(HeaderData::AtomType Atom) const {
277 assert(HdrData && "Dereferencing end iterator?");
278 assert(HdrData->Atoms.size() == Values.size());
279 for (auto Tuple : zip_first(HdrData->Atoms, Values)) {
280 if (std::get<0>(Tuple).first == Atom)
281 return std::get<1>(Tuple);
282 }
283 return std::nullopt;
284 }
285
286 std::optional<uint64_t>
getDIESectionOffset() const287 AppleAcceleratorTable::Entry::getDIESectionOffset() const {
288 return HdrData->extractOffset(lookup(dwarf::DW_ATOM_die_offset));
289 }
290
getCUOffset() const291 std::optional<uint64_t> AppleAcceleratorTable::Entry::getCUOffset() const {
292 return HdrData->extractOffset(lookup(dwarf::DW_ATOM_cu_offset));
293 }
294
getTag() const295 std::optional<dwarf::Tag> AppleAcceleratorTable::Entry::getTag() const {
296 std::optional<DWARFFormValue> Tag = lookup(dwarf::DW_ATOM_die_tag);
297 if (!Tag)
298 return std::nullopt;
299 if (std::optional<uint64_t> Value = Tag->getAsUnsignedConstant())
300 return dwarf::Tag(*Value);
301 return std::nullopt;
302 }
303
ValueIterator(const AppleAcceleratorTable & AccelTable,uint64_t Offset)304 AppleAcceleratorTable::ValueIterator::ValueIterator(
305 const AppleAcceleratorTable &AccelTable, uint64_t Offset)
306 : AccelTable(&AccelTable), Current(AccelTable.HdrData), DataOffset(Offset) {
307 if (!AccelTable.AccelSection.isValidOffsetForDataOfSize(DataOffset, 4))
308 return;
309
310 // Read the first entry.
311 NumData = AccelTable.AccelSection.getU32(&DataOffset);
312 Next();
313 }
314
Next()315 void AppleAcceleratorTable::ValueIterator::Next() {
316 assert(NumData > 0 && "attempted to increment iterator past the end");
317 auto &AccelSection = AccelTable->AccelSection;
318 if (Data >= NumData ||
319 !AccelSection.isValidOffsetForDataOfSize(DataOffset, 4)) {
320 NumData = 0;
321 DataOffset = 0;
322 return;
323 }
324 Current.extract(*AccelTable, &DataOffset);
325 ++Data;
326 }
327
328 iterator_range<AppleAcceleratorTable::ValueIterator>
equal_range(StringRef Key) const329 AppleAcceleratorTable::equal_range(StringRef Key) const {
330 if (!IsValid)
331 return make_range(ValueIterator(), ValueIterator());
332
333 // Find the bucket.
334 unsigned HashValue = djbHash(Key);
335 unsigned Bucket = HashValue % Hdr.BucketCount;
336 uint64_t BucketBase = sizeof(Hdr) + Hdr.HeaderDataLength;
337 uint64_t HashesBase = BucketBase + Hdr.BucketCount * 4;
338 uint64_t OffsetsBase = HashesBase + Hdr.HashCount * 4;
339
340 uint64_t BucketOffset = BucketBase + Bucket * 4;
341 unsigned Index = AccelSection.getU32(&BucketOffset);
342
343 // Search through all hashes in the bucket.
344 for (unsigned HashIdx = Index; HashIdx < Hdr.HashCount; ++HashIdx) {
345 uint64_t HashOffset = HashesBase + HashIdx * 4;
346 uint64_t OffsetsOffset = OffsetsBase + HashIdx * 4;
347 uint32_t Hash = AccelSection.getU32(&HashOffset);
348
349 if (Hash % Hdr.BucketCount != Bucket)
350 // We are already in the next bucket.
351 break;
352
353 uint64_t DataOffset = AccelSection.getU32(&OffsetsOffset);
354 uint64_t StringOffset = AccelSection.getRelocatedValue(4, &DataOffset);
355 if (!StringOffset)
356 break;
357
358 // Finally, compare the key.
359 if (Key == StringSection.getCStr(&StringOffset))
360 return make_range({*this, DataOffset}, ValueIterator());
361 }
362 return make_range(ValueIterator(), ValueIterator());
363 }
364
dump(ScopedPrinter & W) const365 void DWARFDebugNames::Header::dump(ScopedPrinter &W) const {
366 DictScope HeaderScope(W, "Header");
367 W.printHex("Length", UnitLength);
368 W.printString("Format", dwarf::FormatString(Format));
369 W.printNumber("Version", Version);
370 W.printNumber("CU count", CompUnitCount);
371 W.printNumber("Local TU count", LocalTypeUnitCount);
372 W.printNumber("Foreign TU count", ForeignTypeUnitCount);
373 W.printNumber("Bucket count", BucketCount);
374 W.printNumber("Name count", NameCount);
375 W.printHex("Abbreviations table size", AbbrevTableSize);
376 W.startLine() << "Augmentation: '" << AugmentationString << "'\n";
377 }
378
extract(const DWARFDataExtractor & AS,uint64_t * Offset)379 Error DWARFDebugNames::Header::extract(const DWARFDataExtractor &AS,
380 uint64_t *Offset) {
381 auto HeaderError = [Offset = *Offset](Error E) {
382 return createStringError(errc::illegal_byte_sequence,
383 "parsing .debug_names header at 0x%" PRIx64 ": %s",
384 Offset, toString(std::move(E)).c_str());
385 };
386
387 DataExtractor::Cursor C(*Offset);
388 std::tie(UnitLength, Format) = AS.getInitialLength(C);
389
390 Version = AS.getU16(C);
391 AS.skip(C, 2); // padding
392 CompUnitCount = AS.getU32(C);
393 LocalTypeUnitCount = AS.getU32(C);
394 ForeignTypeUnitCount = AS.getU32(C);
395 BucketCount = AS.getU32(C);
396 NameCount = AS.getU32(C);
397 AbbrevTableSize = AS.getU32(C);
398 AugmentationStringSize = alignTo(AS.getU32(C), 4);
399
400 if (!C)
401 return HeaderError(C.takeError());
402
403 if (!AS.isValidOffsetForDataOfSize(C.tell(), AugmentationStringSize))
404 return HeaderError(createStringError(errc::illegal_byte_sequence,
405 "cannot read header augmentation"));
406 AugmentationString.resize(AugmentationStringSize);
407 AS.getU8(C, reinterpret_cast<uint8_t *>(AugmentationString.data()),
408 AugmentationStringSize);
409 *Offset = C.tell();
410 return C.takeError();
411 }
412
dump(ScopedPrinter & W) const413 void DWARFDebugNames::Abbrev::dump(ScopedPrinter &W) const {
414 DictScope AbbrevScope(W, ("Abbreviation 0x" + Twine::utohexstr(Code)).str());
415 W.startLine() << formatv("Tag: {0}\n", Tag);
416
417 for (const auto &Attr : Attributes)
418 W.startLine() << formatv("{0}: {1}\n", Attr.Index, Attr.Form);
419 }
420
sentinelAttrEnc()421 static constexpr DWARFDebugNames::AttributeEncoding sentinelAttrEnc() {
422 return {dwarf::Index(0), dwarf::Form(0)};
423 }
424
isSentinel(const DWARFDebugNames::AttributeEncoding & AE)425 static bool isSentinel(const DWARFDebugNames::AttributeEncoding &AE) {
426 return AE == sentinelAttrEnc();
427 }
428
sentinelAbbrev()429 static DWARFDebugNames::Abbrev sentinelAbbrev() {
430 return DWARFDebugNames::Abbrev(0, dwarf::Tag(0), {});
431 }
432
isSentinel(const DWARFDebugNames::Abbrev & Abbr)433 static bool isSentinel(const DWARFDebugNames::Abbrev &Abbr) {
434 return Abbr.Code == 0;
435 }
436
getEmptyKey()437 DWARFDebugNames::Abbrev DWARFDebugNames::AbbrevMapInfo::getEmptyKey() {
438 return sentinelAbbrev();
439 }
440
getTombstoneKey()441 DWARFDebugNames::Abbrev DWARFDebugNames::AbbrevMapInfo::getTombstoneKey() {
442 return DWARFDebugNames::Abbrev(~0, dwarf::Tag(0), {});
443 }
444
445 Expected<DWARFDebugNames::AttributeEncoding>
extractAttributeEncoding(uint64_t * Offset)446 DWARFDebugNames::NameIndex::extractAttributeEncoding(uint64_t *Offset) {
447 if (*Offset >= EntriesBase) {
448 return createStringError(errc::illegal_byte_sequence,
449 "Incorrectly terminated abbreviation table.");
450 }
451
452 uint32_t Index = Section.AccelSection.getULEB128(Offset);
453 uint32_t Form = Section.AccelSection.getULEB128(Offset);
454 return AttributeEncoding(dwarf::Index(Index), dwarf::Form(Form));
455 }
456
457 Expected<std::vector<DWARFDebugNames::AttributeEncoding>>
extractAttributeEncodings(uint64_t * Offset)458 DWARFDebugNames::NameIndex::extractAttributeEncodings(uint64_t *Offset) {
459 std::vector<AttributeEncoding> Result;
460 for (;;) {
461 auto AttrEncOr = extractAttributeEncoding(Offset);
462 if (!AttrEncOr)
463 return AttrEncOr.takeError();
464 if (isSentinel(*AttrEncOr))
465 return std::move(Result);
466
467 Result.emplace_back(*AttrEncOr);
468 }
469 }
470
471 Expected<DWARFDebugNames::Abbrev>
extractAbbrev(uint64_t * Offset)472 DWARFDebugNames::NameIndex::extractAbbrev(uint64_t *Offset) {
473 if (*Offset >= EntriesBase) {
474 return createStringError(errc::illegal_byte_sequence,
475 "Incorrectly terminated abbreviation table.");
476 }
477
478 uint32_t Code = Section.AccelSection.getULEB128(Offset);
479 if (Code == 0)
480 return sentinelAbbrev();
481
482 uint32_t Tag = Section.AccelSection.getULEB128(Offset);
483 auto AttrEncOr = extractAttributeEncodings(Offset);
484 if (!AttrEncOr)
485 return AttrEncOr.takeError();
486 return Abbrev(Code, dwarf::Tag(Tag), std::move(*AttrEncOr));
487 }
488
extract()489 Error DWARFDebugNames::NameIndex::extract() {
490 const DWARFDataExtractor &AS = Section.AccelSection;
491 uint64_t Offset = Base;
492 if (Error E = Hdr.extract(AS, &Offset))
493 return E;
494
495 const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);
496 CUsBase = Offset;
497 Offset += Hdr.CompUnitCount * SectionOffsetSize;
498 Offset += Hdr.LocalTypeUnitCount * SectionOffsetSize;
499 Offset += Hdr.ForeignTypeUnitCount * 8;
500 BucketsBase = Offset;
501 Offset += Hdr.BucketCount * 4;
502 HashesBase = Offset;
503 if (Hdr.BucketCount > 0)
504 Offset += Hdr.NameCount * 4;
505 StringOffsetsBase = Offset;
506 Offset += Hdr.NameCount * SectionOffsetSize;
507 EntryOffsetsBase = Offset;
508 Offset += Hdr.NameCount * SectionOffsetSize;
509
510 if (!AS.isValidOffsetForDataOfSize(Offset, Hdr.AbbrevTableSize))
511 return createStringError(errc::illegal_byte_sequence,
512 "Section too small: cannot read abbreviations.");
513
514 EntriesBase = Offset + Hdr.AbbrevTableSize;
515
516 for (;;) {
517 auto AbbrevOr = extractAbbrev(&Offset);
518 if (!AbbrevOr)
519 return AbbrevOr.takeError();
520 if (isSentinel(*AbbrevOr))
521 return Error::success();
522
523 if (!Abbrevs.insert(std::move(*AbbrevOr)).second)
524 return createStringError(errc::invalid_argument,
525 "Duplicate abbreviation code.");
526 }
527 }
528
Entry(const NameIndex & NameIdx,const Abbrev & Abbr)529 DWARFDebugNames::Entry::Entry(const NameIndex &NameIdx, const Abbrev &Abbr)
530 : NameIdx(&NameIdx), Abbr(&Abbr) {
531 // This merely creates form values. It is up to the caller
532 // (NameIndex::getEntry) to populate them.
533 Values.reserve(Abbr.Attributes.size());
534 for (const auto &Attr : Abbr.Attributes)
535 Values.emplace_back(Attr.Form);
536 }
537
538 std::optional<DWARFFormValue>
lookup(dwarf::Index Index) const539 DWARFDebugNames::Entry::lookup(dwarf::Index Index) const {
540 assert(Abbr->Attributes.size() == Values.size());
541 for (auto Tuple : zip_first(Abbr->Attributes, Values)) {
542 if (std::get<0>(Tuple).Index == Index)
543 return std::get<1>(Tuple);
544 }
545 return std::nullopt;
546 }
547
getDIEUnitOffset() const548 std::optional<uint64_t> DWARFDebugNames::Entry::getDIEUnitOffset() const {
549 if (std::optional<DWARFFormValue> Off = lookup(dwarf::DW_IDX_die_offset))
550 return Off->getAsReferenceUVal();
551 return std::nullopt;
552 }
553
getCUIndex() const554 std::optional<uint64_t> DWARFDebugNames::Entry::getCUIndex() const {
555 if (std::optional<DWARFFormValue> Off = lookup(dwarf::DW_IDX_compile_unit))
556 return Off->getAsUnsignedConstant();
557 // In a per-CU index, the entries without a DW_IDX_compile_unit attribute
558 // implicitly refer to the single CU.
559 if (NameIdx->getCUCount() == 1)
560 return 0;
561 return std::nullopt;
562 }
563
getCUOffset() const564 std::optional<uint64_t> DWARFDebugNames::Entry::getCUOffset() const {
565 std::optional<uint64_t> Index = getCUIndex();
566 if (!Index || *Index >= NameIdx->getCUCount())
567 return std::nullopt;
568 return NameIdx->getCUOffset(*Index);
569 }
570
dump(ScopedPrinter & W) const571 void DWARFDebugNames::Entry::dump(ScopedPrinter &W) const {
572 W.printHex("Abbrev", Abbr->Code);
573 W.startLine() << formatv("Tag: {0}\n", Abbr->Tag);
574 assert(Abbr->Attributes.size() == Values.size());
575 for (auto Tuple : zip_first(Abbr->Attributes, Values)) {
576 W.startLine() << formatv("{0}: ", std::get<0>(Tuple).Index);
577 std::get<1>(Tuple).dump(W.getOStream());
578 W.getOStream() << '\n';
579 }
580 }
581
582 char DWARFDebugNames::SentinelError::ID;
convertToErrorCode() const583 std::error_code DWARFDebugNames::SentinelError::convertToErrorCode() const {
584 return inconvertibleErrorCode();
585 }
586
getCUOffset(uint32_t CU) const587 uint64_t DWARFDebugNames::NameIndex::getCUOffset(uint32_t CU) const {
588 assert(CU < Hdr.CompUnitCount);
589 const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);
590 uint64_t Offset = CUsBase + SectionOffsetSize * CU;
591 return Section.AccelSection.getRelocatedValue(SectionOffsetSize, &Offset);
592 }
593
getLocalTUOffset(uint32_t TU) const594 uint64_t DWARFDebugNames::NameIndex::getLocalTUOffset(uint32_t TU) const {
595 assert(TU < Hdr.LocalTypeUnitCount);
596 const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);
597 uint64_t Offset = CUsBase + SectionOffsetSize * (Hdr.CompUnitCount + TU);
598 return Section.AccelSection.getRelocatedValue(SectionOffsetSize, &Offset);
599 }
600
getForeignTUSignature(uint32_t TU) const601 uint64_t DWARFDebugNames::NameIndex::getForeignTUSignature(uint32_t TU) const {
602 assert(TU < Hdr.ForeignTypeUnitCount);
603 const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);
604 uint64_t Offset =
605 CUsBase +
606 SectionOffsetSize * (Hdr.CompUnitCount + Hdr.LocalTypeUnitCount) + 8 * TU;
607 return Section.AccelSection.getU64(&Offset);
608 }
609
610 Expected<DWARFDebugNames::Entry>
getEntry(uint64_t * Offset) const611 DWARFDebugNames::NameIndex::getEntry(uint64_t *Offset) const {
612 const DWARFDataExtractor &AS = Section.AccelSection;
613 if (!AS.isValidOffset(*Offset))
614 return createStringError(errc::illegal_byte_sequence,
615 "Incorrectly terminated entry list.");
616
617 uint32_t AbbrevCode = AS.getULEB128(Offset);
618 if (AbbrevCode == 0)
619 return make_error<SentinelError>();
620
621 const auto AbbrevIt = Abbrevs.find_as(AbbrevCode);
622 if (AbbrevIt == Abbrevs.end())
623 return createStringError(errc::invalid_argument, "Invalid abbreviation.");
624
625 Entry E(*this, *AbbrevIt);
626
627 dwarf::FormParams FormParams = {Hdr.Version, 0, Hdr.Format};
628 for (auto &Value : E.Values) {
629 if (!Value.extractValue(AS, Offset, FormParams))
630 return createStringError(errc::io_error,
631 "Error extracting index attribute values.");
632 }
633 return std::move(E);
634 }
635
636 DWARFDebugNames::NameTableEntry
getNameTableEntry(uint32_t Index) const637 DWARFDebugNames::NameIndex::getNameTableEntry(uint32_t Index) const {
638 assert(0 < Index && Index <= Hdr.NameCount);
639 const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);
640 uint64_t StringOffsetOffset =
641 StringOffsetsBase + SectionOffsetSize * (Index - 1);
642 uint64_t EntryOffsetOffset =
643 EntryOffsetsBase + SectionOffsetSize * (Index - 1);
644 const DWARFDataExtractor &AS = Section.AccelSection;
645
646 uint64_t StringOffset =
647 AS.getRelocatedValue(SectionOffsetSize, &StringOffsetOffset);
648 uint64_t EntryOffset = AS.getUnsigned(&EntryOffsetOffset, SectionOffsetSize);
649 EntryOffset += EntriesBase;
650 return {Section.StringSection, Index, StringOffset, EntryOffset};
651 }
652
653 uint32_t
getBucketArrayEntry(uint32_t Bucket) const654 DWARFDebugNames::NameIndex::getBucketArrayEntry(uint32_t Bucket) const {
655 assert(Bucket < Hdr.BucketCount);
656 uint64_t BucketOffset = BucketsBase + 4 * Bucket;
657 return Section.AccelSection.getU32(&BucketOffset);
658 }
659
getHashArrayEntry(uint32_t Index) const660 uint32_t DWARFDebugNames::NameIndex::getHashArrayEntry(uint32_t Index) const {
661 assert(0 < Index && Index <= Hdr.NameCount);
662 uint64_t HashOffset = HashesBase + 4 * (Index - 1);
663 return Section.AccelSection.getU32(&HashOffset);
664 }
665
666 // Returns true if we should continue scanning for entries, false if this is the
667 // last (sentinel) entry). In case of a parsing error we also return false, as
668 // it's not possible to recover this entry list (but the other lists may still
669 // parse OK).
dumpEntry(ScopedPrinter & W,uint64_t * Offset) const670 bool DWARFDebugNames::NameIndex::dumpEntry(ScopedPrinter &W,
671 uint64_t *Offset) const {
672 uint64_t EntryId = *Offset;
673 auto EntryOr = getEntry(Offset);
674 if (!EntryOr) {
675 handleAllErrors(EntryOr.takeError(), [](const SentinelError &) {},
676 [&W](const ErrorInfoBase &EI) { EI.log(W.startLine()); });
677 return false;
678 }
679
680 DictScope EntryScope(W, ("Entry @ 0x" + Twine::utohexstr(EntryId)).str());
681 EntryOr->dump(W);
682 return true;
683 }
684
dumpName(ScopedPrinter & W,const NameTableEntry & NTE,std::optional<uint32_t> Hash) const685 void DWARFDebugNames::NameIndex::dumpName(ScopedPrinter &W,
686 const NameTableEntry &NTE,
687 std::optional<uint32_t> Hash) const {
688 DictScope NameScope(W, ("Name " + Twine(NTE.getIndex())).str());
689 if (Hash)
690 W.printHex("Hash", *Hash);
691
692 W.startLine() << format("String: 0x%08" PRIx64, NTE.getStringOffset());
693 W.getOStream() << " \"" << NTE.getString() << "\"\n";
694
695 uint64_t EntryOffset = NTE.getEntryOffset();
696 while (dumpEntry(W, &EntryOffset))
697 /*empty*/;
698 }
699
dumpCUs(ScopedPrinter & W) const700 void DWARFDebugNames::NameIndex::dumpCUs(ScopedPrinter &W) const {
701 ListScope CUScope(W, "Compilation Unit offsets");
702 for (uint32_t CU = 0; CU < Hdr.CompUnitCount; ++CU)
703 W.startLine() << format("CU[%u]: 0x%08" PRIx64 "\n", CU, getCUOffset(CU));
704 }
705
dumpLocalTUs(ScopedPrinter & W) const706 void DWARFDebugNames::NameIndex::dumpLocalTUs(ScopedPrinter &W) const {
707 if (Hdr.LocalTypeUnitCount == 0)
708 return;
709
710 ListScope TUScope(W, "Local Type Unit offsets");
711 for (uint32_t TU = 0; TU < Hdr.LocalTypeUnitCount; ++TU)
712 W.startLine() << format("LocalTU[%u]: 0x%08" PRIx64 "\n", TU,
713 getLocalTUOffset(TU));
714 }
715
dumpForeignTUs(ScopedPrinter & W) const716 void DWARFDebugNames::NameIndex::dumpForeignTUs(ScopedPrinter &W) const {
717 if (Hdr.ForeignTypeUnitCount == 0)
718 return;
719
720 ListScope TUScope(W, "Foreign Type Unit signatures");
721 for (uint32_t TU = 0; TU < Hdr.ForeignTypeUnitCount; ++TU) {
722 W.startLine() << format("ForeignTU[%u]: 0x%016" PRIx64 "\n", TU,
723 getForeignTUSignature(TU));
724 }
725 }
726
dumpAbbreviations(ScopedPrinter & W) const727 void DWARFDebugNames::NameIndex::dumpAbbreviations(ScopedPrinter &W) const {
728 ListScope AbbrevsScope(W, "Abbreviations");
729 for (const auto &Abbr : Abbrevs)
730 Abbr.dump(W);
731 }
732
dumpBucket(ScopedPrinter & W,uint32_t Bucket) const733 void DWARFDebugNames::NameIndex::dumpBucket(ScopedPrinter &W,
734 uint32_t Bucket) const {
735 ListScope BucketScope(W, ("Bucket " + Twine(Bucket)).str());
736 uint32_t Index = getBucketArrayEntry(Bucket);
737 if (Index == 0) {
738 W.printString("EMPTY");
739 return;
740 }
741 if (Index > Hdr.NameCount) {
742 W.printString("Name index is invalid");
743 return;
744 }
745
746 for (; Index <= Hdr.NameCount; ++Index) {
747 uint32_t Hash = getHashArrayEntry(Index);
748 if (Hash % Hdr.BucketCount != Bucket)
749 break;
750
751 dumpName(W, getNameTableEntry(Index), Hash);
752 }
753 }
754
dump(ScopedPrinter & W) const755 LLVM_DUMP_METHOD void DWARFDebugNames::NameIndex::dump(ScopedPrinter &W) const {
756 DictScope UnitScope(W, ("Name Index @ 0x" + Twine::utohexstr(Base)).str());
757 Hdr.dump(W);
758 dumpCUs(W);
759 dumpLocalTUs(W);
760 dumpForeignTUs(W);
761 dumpAbbreviations(W);
762
763 if (Hdr.BucketCount > 0) {
764 for (uint32_t Bucket = 0; Bucket < Hdr.BucketCount; ++Bucket)
765 dumpBucket(W, Bucket);
766 return;
767 }
768
769 W.startLine() << "Hash table not present\n";
770 for (const NameTableEntry &NTE : *this)
771 dumpName(W, NTE, std::nullopt);
772 }
773
extract()774 Error DWARFDebugNames::extract() {
775 uint64_t Offset = 0;
776 while (AccelSection.isValidOffset(Offset)) {
777 NameIndex Next(*this, Offset);
778 if (Error E = Next.extract())
779 return E;
780 Offset = Next.getNextUnitOffset();
781 NameIndices.push_back(std::move(Next));
782 }
783 return Error::success();
784 }
785
786 iterator_range<DWARFDebugNames::ValueIterator>
equal_range(StringRef Key) const787 DWARFDebugNames::NameIndex::equal_range(StringRef Key) const {
788 return make_range(ValueIterator(*this, Key), ValueIterator());
789 }
790
dump(raw_ostream & OS) const791 LLVM_DUMP_METHOD void DWARFDebugNames::dump(raw_ostream &OS) const {
792 ScopedPrinter W(OS);
793 for (const NameIndex &NI : NameIndices)
794 NI.dump(W);
795 }
796
797 std::optional<uint64_t>
findEntryOffsetInCurrentIndex()798 DWARFDebugNames::ValueIterator::findEntryOffsetInCurrentIndex() {
799 const Header &Hdr = CurrentIndex->Hdr;
800 if (Hdr.BucketCount == 0) {
801 // No Hash Table, We need to search through all names in the Name Index.
802 for (const NameTableEntry &NTE : *CurrentIndex) {
803 if (NTE.getString() == Key)
804 return NTE.getEntryOffset();
805 }
806 return std::nullopt;
807 }
808
809 // The Name Index has a Hash Table, so use that to speed up the search.
810 // Compute the Key Hash, if it has not been done already.
811 if (!Hash)
812 Hash = caseFoldingDjbHash(Key);
813 uint32_t Bucket = *Hash % Hdr.BucketCount;
814 uint32_t Index = CurrentIndex->getBucketArrayEntry(Bucket);
815 if (Index == 0)
816 return std::nullopt; // Empty bucket
817
818 for (; Index <= Hdr.NameCount; ++Index) {
819 uint32_t Hash = CurrentIndex->getHashArrayEntry(Index);
820 if (Hash % Hdr.BucketCount != Bucket)
821 return std::nullopt; // End of bucket
822
823 NameTableEntry NTE = CurrentIndex->getNameTableEntry(Index);
824 if (NTE.getString() == Key)
825 return NTE.getEntryOffset();
826 }
827 return std::nullopt;
828 }
829
getEntryAtCurrentOffset()830 bool DWARFDebugNames::ValueIterator::getEntryAtCurrentOffset() {
831 auto EntryOr = CurrentIndex->getEntry(&DataOffset);
832 if (!EntryOr) {
833 consumeError(EntryOr.takeError());
834 return false;
835 }
836 CurrentEntry = std::move(*EntryOr);
837 return true;
838 }
839
findInCurrentIndex()840 bool DWARFDebugNames::ValueIterator::findInCurrentIndex() {
841 std::optional<uint64_t> Offset = findEntryOffsetInCurrentIndex();
842 if (!Offset)
843 return false;
844 DataOffset = *Offset;
845 return getEntryAtCurrentOffset();
846 }
847
searchFromStartOfCurrentIndex()848 void DWARFDebugNames::ValueIterator::searchFromStartOfCurrentIndex() {
849 for (const NameIndex *End = CurrentIndex->Section.NameIndices.end();
850 CurrentIndex != End; ++CurrentIndex) {
851 if (findInCurrentIndex())
852 return;
853 }
854 setEnd();
855 }
856
next()857 void DWARFDebugNames::ValueIterator::next() {
858 assert(CurrentIndex && "Incrementing an end() iterator?");
859
860 // First try the next entry in the current Index.
861 if (getEntryAtCurrentOffset())
862 return;
863
864 // If we're a local iterator or we have reached the last Index, we're done.
865 if (IsLocal || CurrentIndex == &CurrentIndex->Section.NameIndices.back()) {
866 setEnd();
867 return;
868 }
869
870 // Otherwise, try the next index.
871 ++CurrentIndex;
872 searchFromStartOfCurrentIndex();
873 }
874
ValueIterator(const DWARFDebugNames & AccelTable,StringRef Key)875 DWARFDebugNames::ValueIterator::ValueIterator(const DWARFDebugNames &AccelTable,
876 StringRef Key)
877 : CurrentIndex(AccelTable.NameIndices.begin()), IsLocal(false),
878 Key(std::string(Key)) {
879 searchFromStartOfCurrentIndex();
880 }
881
ValueIterator(const DWARFDebugNames::NameIndex & NI,StringRef Key)882 DWARFDebugNames::ValueIterator::ValueIterator(
883 const DWARFDebugNames::NameIndex &NI, StringRef Key)
884 : CurrentIndex(&NI), IsLocal(true), Key(std::string(Key)) {
885 if (!findInCurrentIndex())
886 setEnd();
887 }
888
889 iterator_range<DWARFDebugNames::ValueIterator>
equal_range(StringRef Key) const890 DWARFDebugNames::equal_range(StringRef Key) const {
891 if (NameIndices.empty())
892 return make_range(ValueIterator(), ValueIterator());
893 return make_range(ValueIterator(*this, Key), ValueIterator());
894 }
895
896 const DWARFDebugNames::NameIndex *
getCUNameIndex(uint64_t CUOffset)897 DWARFDebugNames::getCUNameIndex(uint64_t CUOffset) {
898 if (CUToNameIndex.size() == 0 && NameIndices.size() > 0) {
899 for (const auto &NI : *this) {
900 for (uint32_t CU = 0; CU < NI.getCUCount(); ++CU)
901 CUToNameIndex.try_emplace(NI.getCUOffset(CU), &NI);
902 }
903 }
904 return CUToNameIndex.lookup(CUOffset);
905 }
906