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