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 FormParams = {Hdr.Version, 0, dwarf::DwarfFormat::DWARF32};
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 if (!AccelSection.isValidOffset(getIthBucketBase(Hdr.BucketCount - 1)))
62 return createStringError(
63 errc::illegal_byte_sequence,
64 "Section too small: cannot read buckets and hashes.");
65
66 HdrData.DIEOffsetBase = AccelSection.getU32(&Offset);
67 uint32_t NumAtoms = AccelSection.getU32(&Offset);
68
69 HashDataEntryLength = 0;
70 auto MakeUnsupportedFormError = [](dwarf::Form Form) {
71 return createStringError(errc::not_supported,
72 "Unsupported form:" +
73 dwarf::FormEncodingString(Form));
74 };
75
76 for (unsigned i = 0; i < NumAtoms; ++i) {
77 uint16_t AtomType = AccelSection.getU16(&Offset);
78 auto AtomForm = static_cast<dwarf::Form>(AccelSection.getU16(&Offset));
79 HdrData.Atoms.push_back(std::make_pair(AtomType, AtomForm));
80
81 std::optional<uint8_t> FormSize =
82 dwarf::getFixedFormByteSize(AtomForm, FormParams);
83 if (!FormSize)
84 return MakeUnsupportedFormError(AtomForm);
85 HashDataEntryLength += *FormSize;
86 }
87
88 IsValid = true;
89 return Error::success();
90 }
91
getNumBuckets() const92 uint32_t AppleAcceleratorTable::getNumBuckets() const {
93 return Hdr.BucketCount;
94 }
getNumHashes() const95 uint32_t AppleAcceleratorTable::getNumHashes() const { return Hdr.HashCount; }
getSizeHdr() const96 uint32_t AppleAcceleratorTable::getSizeHdr() const { return sizeof(Hdr); }
getHeaderDataLength() const97 uint32_t AppleAcceleratorTable::getHeaderDataLength() const {
98 return Hdr.HeaderDataLength;
99 }
100
101 ArrayRef<std::pair<AppleAcceleratorTable::HeaderData::AtomType,
102 AppleAcceleratorTable::HeaderData::Form>>
getAtomsDesc()103 AppleAcceleratorTable::getAtomsDesc() {
104 return HdrData.Atoms;
105 }
106
validateForms()107 bool AppleAcceleratorTable::validateForms() {
108 for (auto Atom : getAtomsDesc()) {
109 DWARFFormValue FormValue(Atom.second);
110 switch (Atom.first) {
111 case dwarf::DW_ATOM_die_offset:
112 case dwarf::DW_ATOM_die_tag:
113 case dwarf::DW_ATOM_type_flags:
114 if ((!FormValue.isFormClass(DWARFFormValue::FC_Constant) &&
115 !FormValue.isFormClass(DWARFFormValue::FC_Flag)) ||
116 FormValue.getForm() == dwarf::DW_FORM_sdata)
117 return false;
118 break;
119 default:
120 break;
121 }
122 }
123 return true;
124 }
125
126 std::pair<uint64_t, dwarf::Tag>
readAtoms(uint64_t * HashDataOffset)127 AppleAcceleratorTable::readAtoms(uint64_t *HashDataOffset) {
128 uint64_t DieOffset = dwarf::DW_INVALID_OFFSET;
129 dwarf::Tag DieTag = dwarf::DW_TAG_null;
130
131 for (auto Atom : getAtomsDesc()) {
132 DWARFFormValue FormValue(Atom.second);
133 FormValue.extractValue(AccelSection, HashDataOffset, FormParams);
134 switch (Atom.first) {
135 case dwarf::DW_ATOM_die_offset:
136 DieOffset = *FormValue.getAsUnsignedConstant();
137 break;
138 case dwarf::DW_ATOM_die_tag:
139 DieTag = (dwarf::Tag)*FormValue.getAsUnsignedConstant();
140 break;
141 default:
142 break;
143 }
144 }
145 return {DieOffset, DieTag};
146 }
147
dump(ScopedPrinter & W) const148 void AppleAcceleratorTable::Header::dump(ScopedPrinter &W) const {
149 DictScope HeaderScope(W, "Header");
150 W.printHex("Magic", Magic);
151 W.printHex("Version", Version);
152 W.printHex("Hash function", HashFunction);
153 W.printNumber("Bucket count", BucketCount);
154 W.printNumber("Hashes count", HashCount);
155 W.printNumber("HeaderData length", HeaderDataLength);
156 }
157
extractOffset(std::optional<DWARFFormValue> Value) const158 std::optional<uint64_t> AppleAcceleratorTable::HeaderData::extractOffset(
159 std::optional<DWARFFormValue> Value) const {
160 if (!Value)
161 return std::nullopt;
162
163 switch (Value->getForm()) {
164 case dwarf::DW_FORM_ref1:
165 case dwarf::DW_FORM_ref2:
166 case dwarf::DW_FORM_ref4:
167 case dwarf::DW_FORM_ref8:
168 case dwarf::DW_FORM_ref_udata:
169 return Value->getRawUValue() + DIEOffsetBase;
170 default:
171 return Value->getAsSectionOffset();
172 }
173 }
174
dumpName(ScopedPrinter & W,SmallVectorImpl<DWARFFormValue> & AtomForms,uint64_t * DataOffset) const175 bool AppleAcceleratorTable::dumpName(ScopedPrinter &W,
176 SmallVectorImpl<DWARFFormValue> &AtomForms,
177 uint64_t *DataOffset) const {
178 uint64_t NameOffset = *DataOffset;
179 if (!AccelSection.isValidOffsetForDataOfSize(*DataOffset, 4)) {
180 W.printString("Incorrectly terminated list.");
181 return false;
182 }
183 uint64_t StringOffset = AccelSection.getRelocatedValue(4, DataOffset);
184 if (!StringOffset)
185 return false; // End of list
186
187 DictScope NameScope(W, ("Name@0x" + Twine::utohexstr(NameOffset)).str());
188 W.startLine() << format("String: 0x%08" PRIx64, StringOffset);
189 W.getOStream() << " \"" << StringSection.getCStr(&StringOffset) << "\"\n";
190
191 unsigned NumData = AccelSection.getU32(DataOffset);
192 for (unsigned Data = 0; Data < NumData; ++Data) {
193 ListScope DataScope(W, ("Data " + Twine(Data)).str());
194 unsigned i = 0;
195 for (auto &Atom : AtomForms) {
196 W.startLine() << format("Atom[%d]: ", i);
197 if (Atom.extractValue(AccelSection, DataOffset, FormParams)) {
198 Atom.dump(W.getOStream());
199 if (std::optional<uint64_t> Val = Atom.getAsUnsignedConstant()) {
200 StringRef Str = dwarf::AtomValueString(HdrData.Atoms[i].first, *Val);
201 if (!Str.empty())
202 W.getOStream() << " (" << Str << ")";
203 }
204 } else
205 W.getOStream() << "Error extracting the value";
206 W.getOStream() << "\n";
207 i++;
208 }
209 }
210 return true; // more entries follow
211 }
212
dump(raw_ostream & OS) const213 LLVM_DUMP_METHOD void AppleAcceleratorTable::dump(raw_ostream &OS) const {
214 if (!IsValid)
215 return;
216
217 ScopedPrinter W(OS);
218
219 Hdr.dump(W);
220
221 W.printNumber("DIE offset base", HdrData.DIEOffsetBase);
222 W.printNumber("Number of atoms", uint64_t(HdrData.Atoms.size()));
223 W.printNumber("Size of each hash data entry", getHashDataEntryLength());
224 SmallVector<DWARFFormValue, 3> AtomForms;
225 {
226 ListScope AtomsScope(W, "Atoms");
227 unsigned i = 0;
228 for (const auto &Atom : HdrData.Atoms) {
229 DictScope AtomScope(W, ("Atom " + Twine(i++)).str());
230 W.startLine() << "Type: " << formatAtom(Atom.first) << '\n';
231 W.startLine() << "Form: " << formatv("{0}", Atom.second) << '\n';
232 AtomForms.push_back(DWARFFormValue(Atom.second));
233 }
234 }
235
236 // Now go through the actual tables and dump them.
237 uint64_t Offset = sizeof(Hdr) + Hdr.HeaderDataLength;
238 uint64_t HashesBase = Offset + Hdr.BucketCount * 4;
239 uint64_t OffsetsBase = HashesBase + Hdr.HashCount * 4;
240
241 for (unsigned Bucket = 0; Bucket < Hdr.BucketCount; ++Bucket) {
242 unsigned Index = AccelSection.getU32(&Offset);
243
244 ListScope BucketScope(W, ("Bucket " + Twine(Bucket)).str());
245 if (Index == UINT32_MAX) {
246 W.printString("EMPTY");
247 continue;
248 }
249
250 for (unsigned HashIdx = Index; HashIdx < Hdr.HashCount; ++HashIdx) {
251 uint64_t HashOffset = HashesBase + HashIdx*4;
252 uint64_t OffsetsOffset = OffsetsBase + HashIdx*4;
253 uint32_t Hash = AccelSection.getU32(&HashOffset);
254
255 if (Hash % Hdr.BucketCount != Bucket)
256 break;
257
258 uint64_t DataOffset = AccelSection.getU32(&OffsetsOffset);
259 ListScope HashScope(W, ("Hash 0x" + Twine::utohexstr(Hash)).str());
260 if (!AccelSection.isValidOffset(DataOffset)) {
261 W.printString("Invalid section offset");
262 continue;
263 }
264 while (dumpName(W, AtomForms, &DataOffset))
265 /*empty*/;
266 }
267 }
268 }
269
Entry(const AppleAcceleratorTable & Table)270 AppleAcceleratorTable::Entry::Entry(const AppleAcceleratorTable &Table)
271 : Table(Table) {
272 Values.reserve(Table.HdrData.Atoms.size());
273 for (const auto &Atom : Table.HdrData.Atoms)
274 Values.push_back(DWARFFormValue(Atom.second));
275 }
276
extract(uint64_t * Offset)277 void AppleAcceleratorTable::Entry::extract(uint64_t *Offset) {
278 for (auto &FormValue : Values)
279 FormValue.extractValue(Table.AccelSection, Offset, Table.FormParams);
280 }
281
282 std::optional<DWARFFormValue>
lookup(HeaderData::AtomType AtomToFind) const283 AppleAcceleratorTable::Entry::lookup(HeaderData::AtomType AtomToFind) const {
284 for (auto [Atom, FormValue] : zip_equal(Table.HdrData.Atoms, Values))
285 if (Atom.first == AtomToFind)
286 return FormValue;
287 return std::nullopt;
288 }
289
290 std::optional<uint64_t>
getDIESectionOffset() const291 AppleAcceleratorTable::Entry::getDIESectionOffset() const {
292 return Table.HdrData.extractOffset(lookup(dwarf::DW_ATOM_die_offset));
293 }
294
getCUOffset() const295 std::optional<uint64_t> AppleAcceleratorTable::Entry::getCUOffset() const {
296 return Table.HdrData.extractOffset(lookup(dwarf::DW_ATOM_cu_offset));
297 }
298
getTag() const299 std::optional<dwarf::Tag> AppleAcceleratorTable::Entry::getTag() const {
300 std::optional<DWARFFormValue> Tag = lookup(dwarf::DW_ATOM_die_tag);
301 if (!Tag)
302 return std::nullopt;
303 if (std::optional<uint64_t> Value = Tag->getAsUnsignedConstant())
304 return dwarf::Tag(*Value);
305 return std::nullopt;
306 }
307
SameNameIterator(const AppleAcceleratorTable & AccelTable,uint64_t DataOffset)308 AppleAcceleratorTable::SameNameIterator::SameNameIterator(
309 const AppleAcceleratorTable &AccelTable, uint64_t DataOffset)
310 : Current(AccelTable), Offset(DataOffset) {}
311
prepareNextEntryOrEnd()312 void AppleAcceleratorTable::Iterator::prepareNextEntryOrEnd() {
313 if (NumEntriesToCome == 0)
314 prepareNextStringOrEnd();
315 if (isEnd())
316 return;
317 uint64_t OffsetCopy = Offset;
318 Current.BaseEntry.extract(&OffsetCopy);
319 NumEntriesToCome--;
320 Offset += getTable().getHashDataEntryLength();
321 }
322
prepareNextStringOrEnd()323 void AppleAcceleratorTable::Iterator::prepareNextStringOrEnd() {
324 std::optional<uint32_t> StrOffset = getTable().readStringOffsetAt(Offset);
325 if (!StrOffset)
326 return setToEnd();
327
328 // A zero denotes the end of the collision list. Read the next string
329 // again.
330 if (*StrOffset == 0)
331 return prepareNextStringOrEnd();
332 Current.StrOffset = *StrOffset;
333
334 std::optional<uint32_t> MaybeNumEntries = getTable().readU32FromAccel(Offset);
335 if (!MaybeNumEntries || *MaybeNumEntries == 0)
336 return setToEnd();
337 NumEntriesToCome = *MaybeNumEntries;
338 }
339
Iterator(const AppleAcceleratorTable & Table,bool SetEnd)340 AppleAcceleratorTable::Iterator::Iterator(const AppleAcceleratorTable &Table,
341 bool SetEnd)
342 : Current(Table), Offset(Table.getEntriesBase()), NumEntriesToCome(0) {
343 if (SetEnd)
344 setToEnd();
345 else
346 prepareNextEntryOrEnd();
347 }
348
349 iterator_range<AppleAcceleratorTable::SameNameIterator>
equal_range(StringRef Key) const350 AppleAcceleratorTable::equal_range(StringRef Key) const {
351 const auto EmptyRange =
352 make_range(SameNameIterator(*this, 0), SameNameIterator(*this, 0));
353 if (!IsValid)
354 return EmptyRange;
355
356 // Find the bucket.
357 uint32_t SearchHash = djbHash(Key);
358 uint32_t BucketIdx = hashToBucketIdx(SearchHash);
359 std::optional<uint32_t> HashIdx = idxOfHashInBucket(SearchHash, BucketIdx);
360 if (!HashIdx)
361 return EmptyRange;
362
363 std::optional<uint64_t> MaybeDataOffset = readIthOffset(*HashIdx);
364 if (!MaybeDataOffset)
365 return EmptyRange;
366
367 uint64_t DataOffset = *MaybeDataOffset;
368 if (DataOffset >= AccelSection.size())
369 return EmptyRange;
370
371 std::optional<uint32_t> StrOffset = readStringOffsetAt(DataOffset);
372 // Valid input and still have strings in this hash.
373 while (StrOffset && *StrOffset) {
374 std::optional<StringRef> MaybeStr = readStringFromStrSection(*StrOffset);
375 std::optional<uint32_t> NumEntries = this->readU32FromAccel(DataOffset);
376 if (!MaybeStr || !NumEntries)
377 return EmptyRange;
378 uint64_t EndOffset = DataOffset + *NumEntries * getHashDataEntryLength();
379 if (Key == *MaybeStr)
380 return make_range({*this, DataOffset},
381 SameNameIterator{*this, EndOffset});
382 DataOffset = EndOffset;
383 StrOffset = readStringOffsetAt(DataOffset);
384 }
385
386 return EmptyRange;
387 }
388
389 std::optional<uint32_t>
idxOfHashInBucket(uint32_t HashToFind,uint32_t BucketIdx) const390 AppleAcceleratorTable::idxOfHashInBucket(uint32_t HashToFind,
391 uint32_t BucketIdx) const {
392 std::optional<uint32_t> HashStartIdx = readIthBucket(BucketIdx);
393 if (!HashStartIdx)
394 return std::nullopt;
395
396 for (uint32_t HashIdx = *HashStartIdx; HashIdx < getNumHashes(); HashIdx++) {
397 std::optional<uint32_t> MaybeHash = readIthHash(HashIdx);
398 if (!MaybeHash || !wouldHashBeInBucket(*MaybeHash, BucketIdx))
399 break;
400 if (*MaybeHash == HashToFind)
401 return HashIdx;
402 }
403 return std::nullopt;
404 }
405
readStringFromStrSection(uint64_t StringSectionOffset) const406 std::optional<StringRef> AppleAcceleratorTable::readStringFromStrSection(
407 uint64_t StringSectionOffset) const {
408 Error E = Error::success();
409 StringRef Str = StringSection.getCStrRef(&StringSectionOffset, &E);
410 if (E) {
411 consumeError(std::move(E));
412 return std::nullopt;
413 }
414 return Str;
415 }
416
417 std::optional<uint32_t>
readU32FromAccel(uint64_t & Offset,bool UseRelocation) const418 AppleAcceleratorTable::readU32FromAccel(uint64_t &Offset,
419 bool UseRelocation) const {
420 Error E = Error::success();
421 uint32_t Data = UseRelocation
422 ? AccelSection.getRelocatedValue(4, &Offset, nullptr, &E)
423 : AccelSection.getU32(&Offset, &E);
424 if (E) {
425 consumeError(std::move(E));
426 return std::nullopt;
427 }
428 return Data;
429 }
430
dump(ScopedPrinter & W) const431 void DWARFDebugNames::Header::dump(ScopedPrinter &W) const {
432 DictScope HeaderScope(W, "Header");
433 W.printHex("Length", UnitLength);
434 W.printString("Format", dwarf::FormatString(Format));
435 W.printNumber("Version", Version);
436 W.printNumber("CU count", CompUnitCount);
437 W.printNumber("Local TU count", LocalTypeUnitCount);
438 W.printNumber("Foreign TU count", ForeignTypeUnitCount);
439 W.printNumber("Bucket count", BucketCount);
440 W.printNumber("Name count", NameCount);
441 W.printHex("Abbreviations table size", AbbrevTableSize);
442 W.startLine() << "Augmentation: '" << AugmentationString << "'\n";
443 }
444
extract(const DWARFDataExtractor & AS,uint64_t * Offset)445 Error DWARFDebugNames::Header::extract(const DWARFDataExtractor &AS,
446 uint64_t *Offset) {
447 auto HeaderError = [Offset = *Offset](Error E) {
448 return createStringError(errc::illegal_byte_sequence,
449 "parsing .debug_names header at 0x%" PRIx64 ": %s",
450 Offset, toString(std::move(E)).c_str());
451 };
452
453 DataExtractor::Cursor C(*Offset);
454 std::tie(UnitLength, Format) = AS.getInitialLength(C);
455
456 Version = AS.getU16(C);
457 AS.skip(C, 2); // padding
458 CompUnitCount = AS.getU32(C);
459 LocalTypeUnitCount = AS.getU32(C);
460 ForeignTypeUnitCount = AS.getU32(C);
461 BucketCount = AS.getU32(C);
462 NameCount = AS.getU32(C);
463 AbbrevTableSize = AS.getU32(C);
464 AugmentationStringSize = alignTo(AS.getU32(C), 4);
465
466 if (!C)
467 return HeaderError(C.takeError());
468
469 if (!AS.isValidOffsetForDataOfSize(C.tell(), AugmentationStringSize))
470 return HeaderError(createStringError(errc::illegal_byte_sequence,
471 "cannot read header augmentation"));
472 AugmentationString.resize(AugmentationStringSize);
473 AS.getU8(C, reinterpret_cast<uint8_t *>(AugmentationString.data()),
474 AugmentationStringSize);
475 *Offset = C.tell();
476 return C.takeError();
477 }
478
dump(ScopedPrinter & W) const479 void DWARFDebugNames::Abbrev::dump(ScopedPrinter &W) const {
480 DictScope AbbrevScope(W, ("Abbreviation 0x" + Twine::utohexstr(Code)).str());
481 W.startLine() << formatv("Tag: {0}\n", Tag);
482
483 for (const auto &Attr : Attributes)
484 W.startLine() << formatv("{0}: {1}\n", Attr.Index, Attr.Form);
485 }
486
sentinelAttrEnc()487 static constexpr DWARFDebugNames::AttributeEncoding sentinelAttrEnc() {
488 return {dwarf::Index(0), dwarf::Form(0)};
489 }
490
isSentinel(const DWARFDebugNames::AttributeEncoding & AE)491 static bool isSentinel(const DWARFDebugNames::AttributeEncoding &AE) {
492 return AE == sentinelAttrEnc();
493 }
494
sentinelAbbrev()495 static DWARFDebugNames::Abbrev sentinelAbbrev() {
496 return DWARFDebugNames::Abbrev(0, dwarf::Tag(0), {});
497 }
498
isSentinel(const DWARFDebugNames::Abbrev & Abbr)499 static bool isSentinel(const DWARFDebugNames::Abbrev &Abbr) {
500 return Abbr.Code == 0;
501 }
502
getEmptyKey()503 DWARFDebugNames::Abbrev DWARFDebugNames::AbbrevMapInfo::getEmptyKey() {
504 return sentinelAbbrev();
505 }
506
getTombstoneKey()507 DWARFDebugNames::Abbrev DWARFDebugNames::AbbrevMapInfo::getTombstoneKey() {
508 return DWARFDebugNames::Abbrev(~0, dwarf::Tag(0), {});
509 }
510
511 Expected<DWARFDebugNames::AttributeEncoding>
extractAttributeEncoding(uint64_t * Offset)512 DWARFDebugNames::NameIndex::extractAttributeEncoding(uint64_t *Offset) {
513 if (*Offset >= EntriesBase) {
514 return createStringError(errc::illegal_byte_sequence,
515 "Incorrectly terminated abbreviation table.");
516 }
517
518 uint32_t Index = Section.AccelSection.getULEB128(Offset);
519 uint32_t Form = Section.AccelSection.getULEB128(Offset);
520 return AttributeEncoding(dwarf::Index(Index), dwarf::Form(Form));
521 }
522
523 Expected<std::vector<DWARFDebugNames::AttributeEncoding>>
extractAttributeEncodings(uint64_t * Offset)524 DWARFDebugNames::NameIndex::extractAttributeEncodings(uint64_t *Offset) {
525 std::vector<AttributeEncoding> Result;
526 for (;;) {
527 auto AttrEncOr = extractAttributeEncoding(Offset);
528 if (!AttrEncOr)
529 return AttrEncOr.takeError();
530 if (isSentinel(*AttrEncOr))
531 return std::move(Result);
532
533 Result.emplace_back(*AttrEncOr);
534 }
535 }
536
537 Expected<DWARFDebugNames::Abbrev>
extractAbbrev(uint64_t * Offset)538 DWARFDebugNames::NameIndex::extractAbbrev(uint64_t *Offset) {
539 if (*Offset >= EntriesBase) {
540 return createStringError(errc::illegal_byte_sequence,
541 "Incorrectly terminated abbreviation table.");
542 }
543
544 uint32_t Code = Section.AccelSection.getULEB128(Offset);
545 if (Code == 0)
546 return sentinelAbbrev();
547
548 uint32_t Tag = Section.AccelSection.getULEB128(Offset);
549 auto AttrEncOr = extractAttributeEncodings(Offset);
550 if (!AttrEncOr)
551 return AttrEncOr.takeError();
552 return Abbrev(Code, dwarf::Tag(Tag), std::move(*AttrEncOr));
553 }
554
extract()555 Error DWARFDebugNames::NameIndex::extract() {
556 const DWARFDataExtractor &AS = Section.AccelSection;
557 uint64_t Offset = Base;
558 if (Error E = Hdr.extract(AS, &Offset))
559 return E;
560
561 const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);
562 CUsBase = Offset;
563 Offset += Hdr.CompUnitCount * SectionOffsetSize;
564 Offset += Hdr.LocalTypeUnitCount * SectionOffsetSize;
565 Offset += Hdr.ForeignTypeUnitCount * 8;
566 BucketsBase = Offset;
567 Offset += Hdr.BucketCount * 4;
568 HashesBase = Offset;
569 if (Hdr.BucketCount > 0)
570 Offset += Hdr.NameCount * 4;
571 StringOffsetsBase = Offset;
572 Offset += Hdr.NameCount * SectionOffsetSize;
573 EntryOffsetsBase = Offset;
574 Offset += Hdr.NameCount * SectionOffsetSize;
575
576 if (!AS.isValidOffsetForDataOfSize(Offset, Hdr.AbbrevTableSize))
577 return createStringError(errc::illegal_byte_sequence,
578 "Section too small: cannot read abbreviations.");
579
580 EntriesBase = Offset + Hdr.AbbrevTableSize;
581
582 for (;;) {
583 auto AbbrevOr = extractAbbrev(&Offset);
584 if (!AbbrevOr)
585 return AbbrevOr.takeError();
586 if (isSentinel(*AbbrevOr))
587 return Error::success();
588
589 if (!Abbrevs.insert(std::move(*AbbrevOr)).second)
590 return createStringError(errc::invalid_argument,
591 "Duplicate abbreviation code.");
592 }
593 }
594
Entry(const NameIndex & NameIdx,const Abbrev & Abbr)595 DWARFDebugNames::Entry::Entry(const NameIndex &NameIdx, const Abbrev &Abbr)
596 : NameIdx(&NameIdx), Abbr(&Abbr) {
597 // This merely creates form values. It is up to the caller
598 // (NameIndex::getEntry) to populate them.
599 Values.reserve(Abbr.Attributes.size());
600 for (const auto &Attr : Abbr.Attributes)
601 Values.emplace_back(Attr.Form);
602 }
603
604 std::optional<DWARFFormValue>
lookup(dwarf::Index Index) const605 DWARFDebugNames::Entry::lookup(dwarf::Index Index) const {
606 assert(Abbr->Attributes.size() == Values.size());
607 for (auto Tuple : zip_first(Abbr->Attributes, Values)) {
608 if (std::get<0>(Tuple).Index == Index)
609 return std::get<1>(Tuple);
610 }
611 return std::nullopt;
612 }
613
getDIEUnitOffset() const614 std::optional<uint64_t> DWARFDebugNames::Entry::getDIEUnitOffset() const {
615 if (std::optional<DWARFFormValue> Off = lookup(dwarf::DW_IDX_die_offset))
616 return Off->getAsReferenceUVal();
617 return std::nullopt;
618 }
619
getCUIndex() const620 std::optional<uint64_t> DWARFDebugNames::Entry::getCUIndex() const {
621 if (std::optional<DWARFFormValue> Off = lookup(dwarf::DW_IDX_compile_unit))
622 return Off->getAsUnsignedConstant();
623 // In a per-CU index, the entries without a DW_IDX_compile_unit attribute
624 // implicitly refer to the single CU, but only if we don't have a
625 // DW_IDX_type_unit.
626 if (lookup(dwarf::DW_IDX_type_unit).has_value())
627 return std::nullopt;
628 if (NameIdx->getCUCount() == 1)
629 return 0;
630 return std::nullopt;
631 }
632
getCUOffset() const633 std::optional<uint64_t> DWARFDebugNames::Entry::getCUOffset() const {
634 std::optional<uint64_t> Index = getCUIndex();
635 if (!Index || *Index >= NameIdx->getCUCount())
636 return std::nullopt;
637 return NameIdx->getCUOffset(*Index);
638 }
639
getLocalTUOffset() const640 std::optional<uint64_t> DWARFDebugNames::Entry::getLocalTUOffset() const {
641 std::optional<uint64_t> Index = getLocalTUIndex();
642 if (!Index || *Index >= NameIdx->getLocalTUCount())
643 return std::nullopt;
644 return NameIdx->getLocalTUOffset(*Index);
645 }
646
getLocalTUIndex() const647 std::optional<uint64_t> DWARFDebugNames::Entry::getLocalTUIndex() const {
648 if (std::optional<DWARFFormValue> Off = lookup(dwarf::DW_IDX_type_unit))
649 return Off->getAsUnsignedConstant();
650 return std::nullopt;
651 }
652
dump(ScopedPrinter & W) const653 void DWARFDebugNames::Entry::dump(ScopedPrinter &W) const {
654 W.startLine() << formatv("Abbrev: {0:x}\n", Abbr->Code);
655 W.startLine() << formatv("Tag: {0}\n", Abbr->Tag);
656 assert(Abbr->Attributes.size() == Values.size());
657 for (auto Tuple : zip_first(Abbr->Attributes, Values)) {
658 W.startLine() << formatv("{0}: ", std::get<0>(Tuple).Index);
659 std::get<1>(Tuple).dump(W.getOStream());
660 W.getOStream() << '\n';
661 }
662 }
663
664 char DWARFDebugNames::SentinelError::ID;
convertToErrorCode() const665 std::error_code DWARFDebugNames::SentinelError::convertToErrorCode() const {
666 return inconvertibleErrorCode();
667 }
668
getCUOffset(uint32_t CU) const669 uint64_t DWARFDebugNames::NameIndex::getCUOffset(uint32_t CU) const {
670 assert(CU < Hdr.CompUnitCount);
671 const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);
672 uint64_t Offset = CUsBase + SectionOffsetSize * CU;
673 return Section.AccelSection.getRelocatedValue(SectionOffsetSize, &Offset);
674 }
675
getLocalTUOffset(uint32_t TU) const676 uint64_t DWARFDebugNames::NameIndex::getLocalTUOffset(uint32_t TU) const {
677 assert(TU < Hdr.LocalTypeUnitCount);
678 const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);
679 uint64_t Offset = CUsBase + SectionOffsetSize * (Hdr.CompUnitCount + TU);
680 return Section.AccelSection.getRelocatedValue(SectionOffsetSize, &Offset);
681 }
682
getForeignTUSignature(uint32_t TU) const683 uint64_t DWARFDebugNames::NameIndex::getForeignTUSignature(uint32_t TU) const {
684 assert(TU < Hdr.ForeignTypeUnitCount);
685 const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);
686 uint64_t Offset =
687 CUsBase +
688 SectionOffsetSize * (Hdr.CompUnitCount + Hdr.LocalTypeUnitCount) + 8 * TU;
689 return Section.AccelSection.getU64(&Offset);
690 }
691
692 Expected<DWARFDebugNames::Entry>
getEntry(uint64_t * Offset) const693 DWARFDebugNames::NameIndex::getEntry(uint64_t *Offset) const {
694 const DWARFDataExtractor &AS = Section.AccelSection;
695 if (!AS.isValidOffset(*Offset))
696 return createStringError(errc::illegal_byte_sequence,
697 "Incorrectly terminated entry list.");
698
699 uint32_t AbbrevCode = AS.getULEB128(Offset);
700 if (AbbrevCode == 0)
701 return make_error<SentinelError>();
702
703 const auto AbbrevIt = Abbrevs.find_as(AbbrevCode);
704 if (AbbrevIt == Abbrevs.end())
705 return createStringError(errc::invalid_argument, "Invalid abbreviation.");
706
707 Entry E(*this, *AbbrevIt);
708
709 dwarf::FormParams FormParams = {Hdr.Version, 0, Hdr.Format};
710 for (auto &Value : E.Values) {
711 if (!Value.extractValue(AS, Offset, FormParams))
712 return createStringError(errc::io_error,
713 "Error extracting index attribute values.");
714 }
715 return std::move(E);
716 }
717
718 DWARFDebugNames::NameTableEntry
getNameTableEntry(uint32_t Index) const719 DWARFDebugNames::NameIndex::getNameTableEntry(uint32_t Index) const {
720 assert(0 < Index && Index <= Hdr.NameCount);
721 const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);
722 uint64_t StringOffsetOffset =
723 StringOffsetsBase + SectionOffsetSize * (Index - 1);
724 uint64_t EntryOffsetOffset =
725 EntryOffsetsBase + SectionOffsetSize * (Index - 1);
726 const DWARFDataExtractor &AS = Section.AccelSection;
727
728 uint64_t StringOffset =
729 AS.getRelocatedValue(SectionOffsetSize, &StringOffsetOffset);
730 uint64_t EntryOffset = AS.getUnsigned(&EntryOffsetOffset, SectionOffsetSize);
731 EntryOffset += EntriesBase;
732 return {Section.StringSection, Index, StringOffset, EntryOffset};
733 }
734
735 uint32_t
getBucketArrayEntry(uint32_t Bucket) const736 DWARFDebugNames::NameIndex::getBucketArrayEntry(uint32_t Bucket) const {
737 assert(Bucket < Hdr.BucketCount);
738 uint64_t BucketOffset = BucketsBase + 4 * Bucket;
739 return Section.AccelSection.getU32(&BucketOffset);
740 }
741
getHashArrayEntry(uint32_t Index) const742 uint32_t DWARFDebugNames::NameIndex::getHashArrayEntry(uint32_t Index) const {
743 assert(0 < Index && Index <= Hdr.NameCount);
744 uint64_t HashOffset = HashesBase + 4 * (Index - 1);
745 return Section.AccelSection.getU32(&HashOffset);
746 }
747
748 // Returns true if we should continue scanning for entries, false if this is the
749 // last (sentinel) entry). In case of a parsing error we also return false, as
750 // it's not possible to recover this entry list (but the other lists may still
751 // parse OK).
dumpEntry(ScopedPrinter & W,uint64_t * Offset) const752 bool DWARFDebugNames::NameIndex::dumpEntry(ScopedPrinter &W,
753 uint64_t *Offset) const {
754 uint64_t EntryId = *Offset;
755 auto EntryOr = getEntry(Offset);
756 if (!EntryOr) {
757 handleAllErrors(EntryOr.takeError(), [](const SentinelError &) {},
758 [&W](const ErrorInfoBase &EI) { EI.log(W.startLine()); });
759 return false;
760 }
761
762 DictScope EntryScope(W, ("Entry @ 0x" + Twine::utohexstr(EntryId)).str());
763 EntryOr->dump(W);
764 return true;
765 }
766
dumpName(ScopedPrinter & W,const NameTableEntry & NTE,std::optional<uint32_t> Hash) const767 void DWARFDebugNames::NameIndex::dumpName(ScopedPrinter &W,
768 const NameTableEntry &NTE,
769 std::optional<uint32_t> Hash) const {
770 DictScope NameScope(W, ("Name " + Twine(NTE.getIndex())).str());
771 if (Hash)
772 W.printHex("Hash", *Hash);
773
774 W.startLine() << format("String: 0x%08" PRIx64, NTE.getStringOffset());
775 W.getOStream() << " \"" << NTE.getString() << "\"\n";
776
777 uint64_t EntryOffset = NTE.getEntryOffset();
778 while (dumpEntry(W, &EntryOffset))
779 /*empty*/;
780 }
781
dumpCUs(ScopedPrinter & W) const782 void DWARFDebugNames::NameIndex::dumpCUs(ScopedPrinter &W) const {
783 ListScope CUScope(W, "Compilation Unit offsets");
784 for (uint32_t CU = 0; CU < Hdr.CompUnitCount; ++CU)
785 W.startLine() << format("CU[%u]: 0x%08" PRIx64 "\n", CU, getCUOffset(CU));
786 }
787
dumpLocalTUs(ScopedPrinter & W) const788 void DWARFDebugNames::NameIndex::dumpLocalTUs(ScopedPrinter &W) const {
789 if (Hdr.LocalTypeUnitCount == 0)
790 return;
791
792 ListScope TUScope(W, "Local Type Unit offsets");
793 for (uint32_t TU = 0; TU < Hdr.LocalTypeUnitCount; ++TU)
794 W.startLine() << format("LocalTU[%u]: 0x%08" PRIx64 "\n", TU,
795 getLocalTUOffset(TU));
796 }
797
dumpForeignTUs(ScopedPrinter & W) const798 void DWARFDebugNames::NameIndex::dumpForeignTUs(ScopedPrinter &W) const {
799 if (Hdr.ForeignTypeUnitCount == 0)
800 return;
801
802 ListScope TUScope(W, "Foreign Type Unit signatures");
803 for (uint32_t TU = 0; TU < Hdr.ForeignTypeUnitCount; ++TU) {
804 W.startLine() << format("ForeignTU[%u]: 0x%016" PRIx64 "\n", TU,
805 getForeignTUSignature(TU));
806 }
807 }
808
dumpAbbreviations(ScopedPrinter & W) const809 void DWARFDebugNames::NameIndex::dumpAbbreviations(ScopedPrinter &W) const {
810 ListScope AbbrevsScope(W, "Abbreviations");
811 for (const auto &Abbr : Abbrevs)
812 Abbr.dump(W);
813 }
814
dumpBucket(ScopedPrinter & W,uint32_t Bucket) const815 void DWARFDebugNames::NameIndex::dumpBucket(ScopedPrinter &W,
816 uint32_t Bucket) const {
817 ListScope BucketScope(W, ("Bucket " + Twine(Bucket)).str());
818 uint32_t Index = getBucketArrayEntry(Bucket);
819 if (Index == 0) {
820 W.printString("EMPTY");
821 return;
822 }
823 if (Index > Hdr.NameCount) {
824 W.printString("Name index is invalid");
825 return;
826 }
827
828 for (; Index <= Hdr.NameCount; ++Index) {
829 uint32_t Hash = getHashArrayEntry(Index);
830 if (Hash % Hdr.BucketCount != Bucket)
831 break;
832
833 dumpName(W, getNameTableEntry(Index), Hash);
834 }
835 }
836
dump(ScopedPrinter & W) const837 LLVM_DUMP_METHOD void DWARFDebugNames::NameIndex::dump(ScopedPrinter &W) const {
838 DictScope UnitScope(W, ("Name Index @ 0x" + Twine::utohexstr(Base)).str());
839 Hdr.dump(W);
840 dumpCUs(W);
841 dumpLocalTUs(W);
842 dumpForeignTUs(W);
843 dumpAbbreviations(W);
844
845 if (Hdr.BucketCount > 0) {
846 for (uint32_t Bucket = 0; Bucket < Hdr.BucketCount; ++Bucket)
847 dumpBucket(W, Bucket);
848 return;
849 }
850
851 W.startLine() << "Hash table not present\n";
852 for (const NameTableEntry &NTE : *this)
853 dumpName(W, NTE, std::nullopt);
854 }
855
extract()856 Error DWARFDebugNames::extract() {
857 uint64_t Offset = 0;
858 while (AccelSection.isValidOffset(Offset)) {
859 NameIndex Next(*this, Offset);
860 if (Error E = Next.extract())
861 return E;
862 Offset = Next.getNextUnitOffset();
863 NameIndices.push_back(std::move(Next));
864 }
865 return Error::success();
866 }
867
868 iterator_range<DWARFDebugNames::ValueIterator>
equal_range(StringRef Key) const869 DWARFDebugNames::NameIndex::equal_range(StringRef Key) const {
870 return make_range(ValueIterator(*this, Key), ValueIterator());
871 }
872
dump(raw_ostream & OS) const873 LLVM_DUMP_METHOD void DWARFDebugNames::dump(raw_ostream &OS) const {
874 ScopedPrinter W(OS);
875 for (const NameIndex &NI : NameIndices)
876 NI.dump(W);
877 }
878
879 std::optional<uint64_t>
findEntryOffsetInCurrentIndex()880 DWARFDebugNames::ValueIterator::findEntryOffsetInCurrentIndex() {
881 const Header &Hdr = CurrentIndex->Hdr;
882 if (Hdr.BucketCount == 0) {
883 // No Hash Table, We need to search through all names in the Name Index.
884 for (const NameTableEntry &NTE : *CurrentIndex) {
885 if (NTE.getString() == Key)
886 return NTE.getEntryOffset();
887 }
888 return std::nullopt;
889 }
890
891 // The Name Index has a Hash Table, so use that to speed up the search.
892 // Compute the Key Hash, if it has not been done already.
893 if (!Hash)
894 Hash = caseFoldingDjbHash(Key);
895 uint32_t Bucket = *Hash % Hdr.BucketCount;
896 uint32_t Index = CurrentIndex->getBucketArrayEntry(Bucket);
897 if (Index == 0)
898 return std::nullopt; // Empty bucket
899
900 for (; Index <= Hdr.NameCount; ++Index) {
901 uint32_t Hash = CurrentIndex->getHashArrayEntry(Index);
902 if (Hash % Hdr.BucketCount != Bucket)
903 return std::nullopt; // End of bucket
904
905 NameTableEntry NTE = CurrentIndex->getNameTableEntry(Index);
906 if (NTE.getString() == Key)
907 return NTE.getEntryOffset();
908 }
909 return std::nullopt;
910 }
911
getEntryAtCurrentOffset()912 bool DWARFDebugNames::ValueIterator::getEntryAtCurrentOffset() {
913 auto EntryOr = CurrentIndex->getEntry(&DataOffset);
914 if (!EntryOr) {
915 consumeError(EntryOr.takeError());
916 return false;
917 }
918 CurrentEntry = std::move(*EntryOr);
919 return true;
920 }
921
findInCurrentIndex()922 bool DWARFDebugNames::ValueIterator::findInCurrentIndex() {
923 std::optional<uint64_t> Offset = findEntryOffsetInCurrentIndex();
924 if (!Offset)
925 return false;
926 DataOffset = *Offset;
927 return getEntryAtCurrentOffset();
928 }
929
searchFromStartOfCurrentIndex()930 void DWARFDebugNames::ValueIterator::searchFromStartOfCurrentIndex() {
931 for (const NameIndex *End = CurrentIndex->Section.NameIndices.end();
932 CurrentIndex != End; ++CurrentIndex) {
933 if (findInCurrentIndex())
934 return;
935 }
936 setEnd();
937 }
938
next()939 void DWARFDebugNames::ValueIterator::next() {
940 assert(CurrentIndex && "Incrementing an end() iterator?");
941
942 // First try the next entry in the current Index.
943 if (getEntryAtCurrentOffset())
944 return;
945
946 // If we're a local iterator or we have reached the last Index, we're done.
947 if (IsLocal || CurrentIndex == &CurrentIndex->Section.NameIndices.back()) {
948 setEnd();
949 return;
950 }
951
952 // Otherwise, try the next index.
953 ++CurrentIndex;
954 searchFromStartOfCurrentIndex();
955 }
956
ValueIterator(const DWARFDebugNames & AccelTable,StringRef Key)957 DWARFDebugNames::ValueIterator::ValueIterator(const DWARFDebugNames &AccelTable,
958 StringRef Key)
959 : CurrentIndex(AccelTable.NameIndices.begin()), IsLocal(false),
960 Key(std::string(Key)) {
961 searchFromStartOfCurrentIndex();
962 }
963
ValueIterator(const DWARFDebugNames::NameIndex & NI,StringRef Key)964 DWARFDebugNames::ValueIterator::ValueIterator(
965 const DWARFDebugNames::NameIndex &NI, StringRef Key)
966 : CurrentIndex(&NI), IsLocal(true), Key(std::string(Key)) {
967 if (!findInCurrentIndex())
968 setEnd();
969 }
970
971 iterator_range<DWARFDebugNames::ValueIterator>
equal_range(StringRef Key) const972 DWARFDebugNames::equal_range(StringRef Key) const {
973 if (NameIndices.empty())
974 return make_range(ValueIterator(), ValueIterator());
975 return make_range(ValueIterator(*this, Key), ValueIterator());
976 }
977
978 const DWARFDebugNames::NameIndex *
getCUNameIndex(uint64_t CUOffset)979 DWARFDebugNames::getCUNameIndex(uint64_t CUOffset) {
980 if (CUToNameIndex.size() == 0 && NameIndices.size() > 0) {
981 for (const auto &NI : *this) {
982 for (uint32_t CU = 0; CU < NI.getCUCount(); ++CU)
983 CUToNameIndex.try_emplace(NI.getCUOffset(CU), &NI);
984 }
985 }
986 return CUToNameIndex.lookup(CUOffset);
987 }
988
isObjCSelector(StringRef Name)989 static bool isObjCSelector(StringRef Name) {
990 return Name.size() > 2 && (Name[0] == '-' || Name[0] == '+') &&
991 (Name[1] == '[');
992 }
993
getObjCNamesIfSelector(StringRef Name)994 std::optional<ObjCSelectorNames> llvm::getObjCNamesIfSelector(StringRef Name) {
995 if (!isObjCSelector(Name))
996 return std::nullopt;
997 // "-[Atom setMass:]"
998 StringRef ClassNameStart(Name.drop_front(2));
999 size_t FirstSpace = ClassNameStart.find(' ');
1000 if (FirstSpace == StringRef::npos)
1001 return std::nullopt;
1002
1003 StringRef SelectorStart = ClassNameStart.drop_front(FirstSpace + 1);
1004 if (!SelectorStart.size())
1005 return std::nullopt;
1006
1007 ObjCSelectorNames Ans;
1008 Ans.ClassName = ClassNameStart.take_front(FirstSpace);
1009 Ans.Selector = SelectorStart.drop_back(); // drop ']';
1010
1011 // "-[Class(Category) selector :withArg ...]"
1012 if (Ans.ClassName.back() == ')') {
1013 size_t OpenParens = Ans.ClassName.find('(');
1014 if (OpenParens != StringRef::npos) {
1015 Ans.ClassNameNoCategory = Ans.ClassName.take_front(OpenParens);
1016
1017 Ans.MethodNameNoCategory = Name.take_front(OpenParens + 2);
1018 // FIXME: The missing space here may be a bug, but dsymutil-classic also
1019 // does it this way.
1020 append_range(*Ans.MethodNameNoCategory, SelectorStart);
1021 }
1022 }
1023 return Ans;
1024 }
1025
StripTemplateParameters(StringRef Name)1026 std::optional<StringRef> llvm::StripTemplateParameters(StringRef Name) {
1027 // We are looking for template parameters to strip from Name. e.g.
1028 //
1029 // operator<<B>
1030 //
1031 // We look for > at the end but if it does not contain any < then we
1032 // have something like operator>>. We check for the operator<=> case.
1033 if (!Name.ends_with(">") || Name.count("<") == 0 || Name.ends_with("<=>"))
1034 return {};
1035
1036 // How many < until we have the start of the template parameters.
1037 size_t NumLeftAnglesToSkip = 1;
1038
1039 // If we have operator<=> then we need to skip its < as well.
1040 NumLeftAnglesToSkip += Name.count("<=>");
1041
1042 size_t RightAngleCount = Name.count('>');
1043 size_t LeftAngleCount = Name.count('<');
1044
1045 // If we have more < than > we have operator< or operator<<
1046 // we to account for their < as well.
1047 if (LeftAngleCount > RightAngleCount)
1048 NumLeftAnglesToSkip += LeftAngleCount - RightAngleCount;
1049
1050 size_t StartOfTemplate = 0;
1051 while (NumLeftAnglesToSkip--)
1052 StartOfTemplate = Name.find('<', StartOfTemplate) + 1;
1053
1054 return Name.substr(0, StartOfTemplate - 1);
1055 }
1056