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   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 
92 uint32_t AppleAcceleratorTable::getNumBuckets() const {
93   return Hdr.BucketCount;
94 }
95 uint32_t AppleAcceleratorTable::getNumHashes() const { return Hdr.HashCount; }
96 uint32_t AppleAcceleratorTable::getSizeHdr() const { return sizeof(Hdr); }
97 uint32_t AppleAcceleratorTable::getHeaderDataLength() const {
98   return Hdr.HeaderDataLength;
99 }
100 
101 ArrayRef<std::pair<AppleAcceleratorTable::HeaderData::AtomType,
102                    AppleAcceleratorTable::HeaderData::Form>>
103 AppleAcceleratorTable::getAtomsDesc() {
104   return HdrData.Atoms;
105 }
106 
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>
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 
148 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 
158 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 
175 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 
213 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 
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 
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>
283 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>
291 AppleAcceleratorTable::Entry::getDIESectionOffset() const {
292   return Table.HdrData.extractOffset(lookup(dwarf::DW_ATOM_die_offset));
293 }
294 
295 std::optional<uint64_t> AppleAcceleratorTable::Entry::getCUOffset() const {
296   return Table.HdrData.extractOffset(lookup(dwarf::DW_ATOM_cu_offset));
297 }
298 
299 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 
308 AppleAcceleratorTable::SameNameIterator::SameNameIterator(
309     const AppleAcceleratorTable &AccelTable, uint64_t DataOffset)
310     : Current(AccelTable), Offset(DataOffset) {}
311 
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 
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 
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>
350 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>
390 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 
406 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>
418 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 
431 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 
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 
479 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 
487 static constexpr DWARFDebugNames::AttributeEncoding sentinelAttrEnc() {
488   return {dwarf::Index(0), dwarf::Form(0)};
489 }
490 
491 static bool isSentinel(const DWARFDebugNames::AttributeEncoding &AE) {
492   return AE == sentinelAttrEnc();
493 }
494 
495 static DWARFDebugNames::Abbrev sentinelAbbrev() {
496   return DWARFDebugNames::Abbrev(0, dwarf::Tag(0), {});
497 }
498 
499 static bool isSentinel(const DWARFDebugNames::Abbrev &Abbr) {
500   return Abbr.Code == 0;
501 }
502 
503 DWARFDebugNames::Abbrev DWARFDebugNames::AbbrevMapInfo::getEmptyKey() {
504   return sentinelAbbrev();
505 }
506 
507 DWARFDebugNames::Abbrev DWARFDebugNames::AbbrevMapInfo::getTombstoneKey() {
508   return DWARFDebugNames::Abbrev(~0, dwarf::Tag(0), {});
509 }
510 
511 Expected<DWARFDebugNames::AttributeEncoding>
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>>
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>
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 
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 
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>
605 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 
614 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 
620 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.
625   if (NameIdx->getCUCount() == 1)
626     return 0;
627   return std::nullopt;
628 }
629 
630 std::optional<uint64_t> DWARFDebugNames::Entry::getCUOffset() const {
631   std::optional<uint64_t> Index = getCUIndex();
632   if (!Index || *Index >= NameIdx->getCUCount())
633     return std::nullopt;
634   return NameIdx->getCUOffset(*Index);
635 }
636 
637 void DWARFDebugNames::Entry::dump(ScopedPrinter &W) const {
638   W.printHex("Abbrev", Abbr->Code);
639   W.startLine() << formatv("Tag: {0}\n", Abbr->Tag);
640   assert(Abbr->Attributes.size() == Values.size());
641   for (auto Tuple : zip_first(Abbr->Attributes, Values)) {
642     W.startLine() << formatv("{0}: ", std::get<0>(Tuple).Index);
643     std::get<1>(Tuple).dump(W.getOStream());
644     W.getOStream() << '\n';
645   }
646 }
647 
648 char DWARFDebugNames::SentinelError::ID;
649 std::error_code DWARFDebugNames::SentinelError::convertToErrorCode() const {
650   return inconvertibleErrorCode();
651 }
652 
653 uint64_t DWARFDebugNames::NameIndex::getCUOffset(uint32_t CU) const {
654   assert(CU < Hdr.CompUnitCount);
655   const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);
656   uint64_t Offset = CUsBase + SectionOffsetSize * CU;
657   return Section.AccelSection.getRelocatedValue(SectionOffsetSize, &Offset);
658 }
659 
660 uint64_t DWARFDebugNames::NameIndex::getLocalTUOffset(uint32_t TU) const {
661   assert(TU < Hdr.LocalTypeUnitCount);
662   const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);
663   uint64_t Offset = CUsBase + SectionOffsetSize * (Hdr.CompUnitCount + TU);
664   return Section.AccelSection.getRelocatedValue(SectionOffsetSize, &Offset);
665 }
666 
667 uint64_t DWARFDebugNames::NameIndex::getForeignTUSignature(uint32_t TU) const {
668   assert(TU < Hdr.ForeignTypeUnitCount);
669   const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);
670   uint64_t Offset =
671       CUsBase +
672       SectionOffsetSize * (Hdr.CompUnitCount + Hdr.LocalTypeUnitCount) + 8 * TU;
673   return Section.AccelSection.getU64(&Offset);
674 }
675 
676 Expected<DWARFDebugNames::Entry>
677 DWARFDebugNames::NameIndex::getEntry(uint64_t *Offset) const {
678   const DWARFDataExtractor &AS = Section.AccelSection;
679   if (!AS.isValidOffset(*Offset))
680     return createStringError(errc::illegal_byte_sequence,
681                              "Incorrectly terminated entry list.");
682 
683   uint32_t AbbrevCode = AS.getULEB128(Offset);
684   if (AbbrevCode == 0)
685     return make_error<SentinelError>();
686 
687   const auto AbbrevIt = Abbrevs.find_as(AbbrevCode);
688   if (AbbrevIt == Abbrevs.end())
689     return createStringError(errc::invalid_argument, "Invalid abbreviation.");
690 
691   Entry E(*this, *AbbrevIt);
692 
693   dwarf::FormParams FormParams = {Hdr.Version, 0, Hdr.Format};
694   for (auto &Value : E.Values) {
695     if (!Value.extractValue(AS, Offset, FormParams))
696       return createStringError(errc::io_error,
697                                "Error extracting index attribute values.");
698   }
699   return std::move(E);
700 }
701 
702 DWARFDebugNames::NameTableEntry
703 DWARFDebugNames::NameIndex::getNameTableEntry(uint32_t Index) const {
704   assert(0 < Index && Index <= Hdr.NameCount);
705   const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);
706   uint64_t StringOffsetOffset =
707       StringOffsetsBase + SectionOffsetSize * (Index - 1);
708   uint64_t EntryOffsetOffset =
709       EntryOffsetsBase + SectionOffsetSize * (Index - 1);
710   const DWARFDataExtractor &AS = Section.AccelSection;
711 
712   uint64_t StringOffset =
713       AS.getRelocatedValue(SectionOffsetSize, &StringOffsetOffset);
714   uint64_t EntryOffset = AS.getUnsigned(&EntryOffsetOffset, SectionOffsetSize);
715   EntryOffset += EntriesBase;
716   return {Section.StringSection, Index, StringOffset, EntryOffset};
717 }
718 
719 uint32_t
720 DWARFDebugNames::NameIndex::getBucketArrayEntry(uint32_t Bucket) const {
721   assert(Bucket < Hdr.BucketCount);
722   uint64_t BucketOffset = BucketsBase + 4 * Bucket;
723   return Section.AccelSection.getU32(&BucketOffset);
724 }
725 
726 uint32_t DWARFDebugNames::NameIndex::getHashArrayEntry(uint32_t Index) const {
727   assert(0 < Index && Index <= Hdr.NameCount);
728   uint64_t HashOffset = HashesBase + 4 * (Index - 1);
729   return Section.AccelSection.getU32(&HashOffset);
730 }
731 
732 // Returns true if we should continue scanning for entries, false if this is the
733 // last (sentinel) entry). In case of a parsing error we also return false, as
734 // it's not possible to recover this entry list (but the other lists may still
735 // parse OK).
736 bool DWARFDebugNames::NameIndex::dumpEntry(ScopedPrinter &W,
737                                            uint64_t *Offset) const {
738   uint64_t EntryId = *Offset;
739   auto EntryOr = getEntry(Offset);
740   if (!EntryOr) {
741     handleAllErrors(EntryOr.takeError(), [](const SentinelError &) {},
742                     [&W](const ErrorInfoBase &EI) { EI.log(W.startLine()); });
743     return false;
744   }
745 
746   DictScope EntryScope(W, ("Entry @ 0x" + Twine::utohexstr(EntryId)).str());
747   EntryOr->dump(W);
748   return true;
749 }
750 
751 void DWARFDebugNames::NameIndex::dumpName(ScopedPrinter &W,
752                                           const NameTableEntry &NTE,
753                                           std::optional<uint32_t> Hash) const {
754   DictScope NameScope(W, ("Name " + Twine(NTE.getIndex())).str());
755   if (Hash)
756     W.printHex("Hash", *Hash);
757 
758   W.startLine() << format("String: 0x%08" PRIx64, NTE.getStringOffset());
759   W.getOStream() << " \"" << NTE.getString() << "\"\n";
760 
761   uint64_t EntryOffset = NTE.getEntryOffset();
762   while (dumpEntry(W, &EntryOffset))
763     /*empty*/;
764 }
765 
766 void DWARFDebugNames::NameIndex::dumpCUs(ScopedPrinter &W) const {
767   ListScope CUScope(W, "Compilation Unit offsets");
768   for (uint32_t CU = 0; CU < Hdr.CompUnitCount; ++CU)
769     W.startLine() << format("CU[%u]: 0x%08" PRIx64 "\n", CU, getCUOffset(CU));
770 }
771 
772 void DWARFDebugNames::NameIndex::dumpLocalTUs(ScopedPrinter &W) const {
773   if (Hdr.LocalTypeUnitCount == 0)
774     return;
775 
776   ListScope TUScope(W, "Local Type Unit offsets");
777   for (uint32_t TU = 0; TU < Hdr.LocalTypeUnitCount; ++TU)
778     W.startLine() << format("LocalTU[%u]: 0x%08" PRIx64 "\n", TU,
779                             getLocalTUOffset(TU));
780 }
781 
782 void DWARFDebugNames::NameIndex::dumpForeignTUs(ScopedPrinter &W) const {
783   if (Hdr.ForeignTypeUnitCount == 0)
784     return;
785 
786   ListScope TUScope(W, "Foreign Type Unit signatures");
787   for (uint32_t TU = 0; TU < Hdr.ForeignTypeUnitCount; ++TU) {
788     W.startLine() << format("ForeignTU[%u]: 0x%016" PRIx64 "\n", TU,
789                             getForeignTUSignature(TU));
790   }
791 }
792 
793 void DWARFDebugNames::NameIndex::dumpAbbreviations(ScopedPrinter &W) const {
794   ListScope AbbrevsScope(W, "Abbreviations");
795   for (const auto &Abbr : Abbrevs)
796     Abbr.dump(W);
797 }
798 
799 void DWARFDebugNames::NameIndex::dumpBucket(ScopedPrinter &W,
800                                             uint32_t Bucket) const {
801   ListScope BucketScope(W, ("Bucket " + Twine(Bucket)).str());
802   uint32_t Index = getBucketArrayEntry(Bucket);
803   if (Index == 0) {
804     W.printString("EMPTY");
805     return;
806   }
807   if (Index > Hdr.NameCount) {
808     W.printString("Name index is invalid");
809     return;
810   }
811 
812   for (; Index <= Hdr.NameCount; ++Index) {
813     uint32_t Hash = getHashArrayEntry(Index);
814     if (Hash % Hdr.BucketCount != Bucket)
815       break;
816 
817     dumpName(W, getNameTableEntry(Index), Hash);
818   }
819 }
820 
821 LLVM_DUMP_METHOD void DWARFDebugNames::NameIndex::dump(ScopedPrinter &W) const {
822   DictScope UnitScope(W, ("Name Index @ 0x" + Twine::utohexstr(Base)).str());
823   Hdr.dump(W);
824   dumpCUs(W);
825   dumpLocalTUs(W);
826   dumpForeignTUs(W);
827   dumpAbbreviations(W);
828 
829   if (Hdr.BucketCount > 0) {
830     for (uint32_t Bucket = 0; Bucket < Hdr.BucketCount; ++Bucket)
831       dumpBucket(W, Bucket);
832     return;
833   }
834 
835   W.startLine() << "Hash table not present\n";
836   for (const NameTableEntry &NTE : *this)
837     dumpName(W, NTE, std::nullopt);
838 }
839 
840 Error DWARFDebugNames::extract() {
841   uint64_t Offset = 0;
842   while (AccelSection.isValidOffset(Offset)) {
843     NameIndex Next(*this, Offset);
844     if (Error E = Next.extract())
845       return E;
846     Offset = Next.getNextUnitOffset();
847     NameIndices.push_back(std::move(Next));
848   }
849   return Error::success();
850 }
851 
852 iterator_range<DWARFDebugNames::ValueIterator>
853 DWARFDebugNames::NameIndex::equal_range(StringRef Key) const {
854   return make_range(ValueIterator(*this, Key), ValueIterator());
855 }
856 
857 LLVM_DUMP_METHOD void DWARFDebugNames::dump(raw_ostream &OS) const {
858   ScopedPrinter W(OS);
859   for (const NameIndex &NI : NameIndices)
860     NI.dump(W);
861 }
862 
863 std::optional<uint64_t>
864 DWARFDebugNames::ValueIterator::findEntryOffsetInCurrentIndex() {
865   const Header &Hdr = CurrentIndex->Hdr;
866   if (Hdr.BucketCount == 0) {
867     // No Hash Table, We need to search through all names in the Name Index.
868     for (const NameTableEntry &NTE : *CurrentIndex) {
869       if (NTE.getString() == Key)
870         return NTE.getEntryOffset();
871     }
872     return std::nullopt;
873   }
874 
875   // The Name Index has a Hash Table, so use that to speed up the search.
876   // Compute the Key Hash, if it has not been done already.
877   if (!Hash)
878     Hash = caseFoldingDjbHash(Key);
879   uint32_t Bucket = *Hash % Hdr.BucketCount;
880   uint32_t Index = CurrentIndex->getBucketArrayEntry(Bucket);
881   if (Index == 0)
882     return std::nullopt; // Empty bucket
883 
884   for (; Index <= Hdr.NameCount; ++Index) {
885     uint32_t Hash = CurrentIndex->getHashArrayEntry(Index);
886     if (Hash % Hdr.BucketCount != Bucket)
887       return std::nullopt; // End of bucket
888 
889     NameTableEntry NTE = CurrentIndex->getNameTableEntry(Index);
890     if (NTE.getString() == Key)
891       return NTE.getEntryOffset();
892   }
893   return std::nullopt;
894 }
895 
896 bool DWARFDebugNames::ValueIterator::getEntryAtCurrentOffset() {
897   auto EntryOr = CurrentIndex->getEntry(&DataOffset);
898   if (!EntryOr) {
899     consumeError(EntryOr.takeError());
900     return false;
901   }
902   CurrentEntry = std::move(*EntryOr);
903   return true;
904 }
905 
906 bool DWARFDebugNames::ValueIterator::findInCurrentIndex() {
907   std::optional<uint64_t> Offset = findEntryOffsetInCurrentIndex();
908   if (!Offset)
909     return false;
910   DataOffset = *Offset;
911   return getEntryAtCurrentOffset();
912 }
913 
914 void DWARFDebugNames::ValueIterator::searchFromStartOfCurrentIndex() {
915   for (const NameIndex *End = CurrentIndex->Section.NameIndices.end();
916        CurrentIndex != End; ++CurrentIndex) {
917     if (findInCurrentIndex())
918       return;
919   }
920   setEnd();
921 }
922 
923 void DWARFDebugNames::ValueIterator::next() {
924   assert(CurrentIndex && "Incrementing an end() iterator?");
925 
926   // First try the next entry in the current Index.
927   if (getEntryAtCurrentOffset())
928     return;
929 
930   // If we're a local iterator or we have reached the last Index, we're done.
931   if (IsLocal || CurrentIndex == &CurrentIndex->Section.NameIndices.back()) {
932     setEnd();
933     return;
934   }
935 
936   // Otherwise, try the next index.
937   ++CurrentIndex;
938   searchFromStartOfCurrentIndex();
939 }
940 
941 DWARFDebugNames::ValueIterator::ValueIterator(const DWARFDebugNames &AccelTable,
942                                               StringRef Key)
943     : CurrentIndex(AccelTable.NameIndices.begin()), IsLocal(false),
944       Key(std::string(Key)) {
945   searchFromStartOfCurrentIndex();
946 }
947 
948 DWARFDebugNames::ValueIterator::ValueIterator(
949     const DWARFDebugNames::NameIndex &NI, StringRef Key)
950     : CurrentIndex(&NI), IsLocal(true), Key(std::string(Key)) {
951   if (!findInCurrentIndex())
952     setEnd();
953 }
954 
955 iterator_range<DWARFDebugNames::ValueIterator>
956 DWARFDebugNames::equal_range(StringRef Key) const {
957   if (NameIndices.empty())
958     return make_range(ValueIterator(), ValueIterator());
959   return make_range(ValueIterator(*this, Key), ValueIterator());
960 }
961 
962 const DWARFDebugNames::NameIndex *
963 DWARFDebugNames::getCUNameIndex(uint64_t CUOffset) {
964   if (CUToNameIndex.size() == 0 && NameIndices.size() > 0) {
965     for (const auto &NI : *this) {
966       for (uint32_t CU = 0; CU < NI.getCUCount(); ++CU)
967         CUToNameIndex.try_emplace(NI.getCUOffset(CU), &NI);
968     }
969   }
970   return CUToNameIndex.lookup(CUOffset);
971 }
972