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 
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 
39 static Atom formatAtom(unsigned Atom) { return {Atom}; }
40 
41 DWARFAcceleratorTable::~DWARFAcceleratorTable() = default;
42 
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 
81 uint32_t AppleAcceleratorTable::getNumBuckets() { return Hdr.BucketCount; }
82 uint32_t AppleAcceleratorTable::getNumHashes() { return Hdr.HashCount; }
83 uint32_t AppleAcceleratorTable::getSizeHdr() { return sizeof(Hdr); }
84 uint32_t AppleAcceleratorTable::getHeaderDataLength() {
85   return Hdr.HeaderDataLength;
86 }
87 
88 ArrayRef<std::pair<AppleAcceleratorTable::HeaderData::AtomType,
89                    AppleAcceleratorTable::HeaderData::Form>>
90 AppleAcceleratorTable::getAtomsDesc() {
91   return HdrData.Atoms;
92 }
93 
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>
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 
136 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 
146 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 
163 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 
202 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 
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 
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>
276 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>
287 AppleAcceleratorTable::Entry::getDIESectionOffset() const {
288   return HdrData->extractOffset(lookup(dwarf::DW_ATOM_die_offset));
289 }
290 
291 std::optional<uint64_t> AppleAcceleratorTable::Entry::getCUOffset() const {
292   return HdrData->extractOffset(lookup(dwarf::DW_ATOM_cu_offset));
293 }
294 
295 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 
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 
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>
329 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 
365 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 
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 
413 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 
421 static constexpr DWARFDebugNames::AttributeEncoding sentinelAttrEnc() {
422   return {dwarf::Index(0), dwarf::Form(0)};
423 }
424 
425 static bool isSentinel(const DWARFDebugNames::AttributeEncoding &AE) {
426   return AE == sentinelAttrEnc();
427 }
428 
429 static DWARFDebugNames::Abbrev sentinelAbbrev() {
430   return DWARFDebugNames::Abbrev(0, dwarf::Tag(0), {});
431 }
432 
433 static bool isSentinel(const DWARFDebugNames::Abbrev &Abbr) {
434   return Abbr.Code == 0;
435 }
436 
437 DWARFDebugNames::Abbrev DWARFDebugNames::AbbrevMapInfo::getEmptyKey() {
438   return sentinelAbbrev();
439 }
440 
441 DWARFDebugNames::Abbrev DWARFDebugNames::AbbrevMapInfo::getTombstoneKey() {
442   return DWARFDebugNames::Abbrev(~0, dwarf::Tag(0), {});
443 }
444 
445 Expected<DWARFDebugNames::AttributeEncoding>
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>>
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>
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 
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 
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>
539 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 
548 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 
554 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 
564 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 
571 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;
583 std::error_code DWARFDebugNames::SentinelError::convertToErrorCode() const {
584   return inconvertibleErrorCode();
585 }
586 
587 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 
594 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 
601 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>
611 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
637 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
654 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 
660 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).
670 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 
685 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 
700 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 
706 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 
716 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 
727 void DWARFDebugNames::NameIndex::dumpAbbreviations(ScopedPrinter &W) const {
728   ListScope AbbrevsScope(W, "Abbreviations");
729   for (const auto &Abbr : Abbrevs)
730     Abbr.dump(W);
731 }
732 
733 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 
755 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 
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>
787 DWARFDebugNames::NameIndex::equal_range(StringRef Key) const {
788   return make_range(ValueIterator(*this, Key), ValueIterator());
789 }
790 
791 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>
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 
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 
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 
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 
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 
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 
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>
890 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 *
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