1 //===- DWARFAcceleratorTable.cpp ------------------------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h"
11 
12 #include "llvm/ADT/SmallVector.h"
13 #include "llvm/BinaryFormat/Dwarf.h"
14 #include "llvm/DebugInfo/DWARF/DWARFRelocMap.h"
15 #include "llvm/Support/Compiler.h"
16 #include "llvm/Support/DJB.h"
17 #include "llvm/Support/Format.h"
18 #include "llvm/Support/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 DwarfConstant {
28   StringRef (*StringFn)(unsigned);
29   StringRef Type;
30   unsigned Value;
31 };
32 
33 static raw_ostream &operator<<(raw_ostream &OS, const DwarfConstant &C) {
34   StringRef Str = C.StringFn(C.Value);
35   if (!Str.empty())
36     return OS << Str;
37   return OS << "DW_" << C.Type << "_Unknown_0x" << format("%x", C.Value);
38 }
39 } // namespace
40 
41 static DwarfConstant formatTag(unsigned Tag) {
42   return {dwarf::TagString, "TAG", Tag};
43 }
44 
45 static DwarfConstant formatForm(unsigned Form) {
46   return {dwarf::FormEncodingString, "FORM", Form};
47 }
48 
49 static DwarfConstant formatIndex(unsigned Idx) {
50   return {dwarf::IndexString, "IDX", Idx};
51 }
52 
53 static DwarfConstant formatAtom(unsigned Atom) {
54   return {dwarf::AtomTypeString, "ATOM", Atom};
55 }
56 
57 DWARFAcceleratorTable::~DWARFAcceleratorTable() = default;
58 
59 llvm::Error AppleAcceleratorTable::extract() {
60   uint32_t Offset = 0;
61 
62   // Check that we can at least read the header.
63   if (!AccelSection.isValidOffset(offsetof(Header, HeaderDataLength)+4))
64     return make_error<StringError>("Section too small: cannot read header.",
65                                    inconvertibleErrorCode());
66 
67   Hdr.Magic = AccelSection.getU32(&Offset);
68   Hdr.Version = AccelSection.getU16(&Offset);
69   Hdr.HashFunction = AccelSection.getU16(&Offset);
70   Hdr.BucketCount = AccelSection.getU32(&Offset);
71   Hdr.HashCount = AccelSection.getU32(&Offset);
72   Hdr.HeaderDataLength = AccelSection.getU32(&Offset);
73 
74   // Check that we can read all the hashes and offsets from the
75   // section (see SourceLevelDebugging.rst for the structure of the index).
76   // We need to substract one because we're checking for an *offset* which is
77   // equal to the size for an empty table and hence pointer after the section.
78   if (!AccelSection.isValidOffset(sizeof(Hdr) + Hdr.HeaderDataLength +
79                                   Hdr.BucketCount * 4 + Hdr.HashCount * 8 - 1))
80     return make_error<StringError>(
81         "Section too small: cannot read buckets and hashes.",
82         inconvertibleErrorCode());
83 
84   HdrData.DIEOffsetBase = AccelSection.getU32(&Offset);
85   uint32_t NumAtoms = AccelSection.getU32(&Offset);
86 
87   for (unsigned i = 0; i < NumAtoms; ++i) {
88     uint16_t AtomType = AccelSection.getU16(&Offset);
89     auto AtomForm = static_cast<dwarf::Form>(AccelSection.getU16(&Offset));
90     HdrData.Atoms.push_back(std::make_pair(AtomType, AtomForm));
91   }
92 
93   IsValid = true;
94   return Error::success();
95 }
96 
97 uint32_t AppleAcceleratorTable::getNumBuckets() { return Hdr.BucketCount; }
98 uint32_t AppleAcceleratorTable::getNumHashes() { return Hdr.HashCount; }
99 uint32_t AppleAcceleratorTable::getSizeHdr() { return sizeof(Hdr); }
100 uint32_t AppleAcceleratorTable::getHeaderDataLength() {
101   return Hdr.HeaderDataLength;
102 }
103 
104 ArrayRef<std::pair<AppleAcceleratorTable::HeaderData::AtomType,
105                    AppleAcceleratorTable::HeaderData::Form>>
106 AppleAcceleratorTable::getAtomsDesc() {
107   return HdrData.Atoms;
108 }
109 
110 bool AppleAcceleratorTable::validateForms() {
111   for (auto Atom : getAtomsDesc()) {
112     DWARFFormValue FormValue(Atom.second);
113     switch (Atom.first) {
114     case dwarf::DW_ATOM_die_offset:
115     case dwarf::DW_ATOM_die_tag:
116     case dwarf::DW_ATOM_type_flags:
117       if ((!FormValue.isFormClass(DWARFFormValue::FC_Constant) &&
118            !FormValue.isFormClass(DWARFFormValue::FC_Flag)) ||
119           FormValue.getForm() == dwarf::DW_FORM_sdata)
120         return false;
121       break;
122     default:
123       break;
124     }
125   }
126   return true;
127 }
128 
129 std::pair<uint32_t, dwarf::Tag>
130 AppleAcceleratorTable::readAtoms(uint32_t &HashDataOffset) {
131   uint32_t DieOffset = dwarf::DW_INVALID_OFFSET;
132   dwarf::Tag DieTag = dwarf::DW_TAG_null;
133   DWARFFormParams FormParams = {Hdr.Version, 0, dwarf::DwarfFormat::DWARF32};
134 
135   for (auto Atom : getAtomsDesc()) {
136     DWARFFormValue FormValue(Atom.second);
137     FormValue.extractValue(AccelSection, &HashDataOffset, FormParams);
138     switch (Atom.first) {
139     case dwarf::DW_ATOM_die_offset:
140       DieOffset = *FormValue.getAsUnsignedConstant();
141       break;
142     case dwarf::DW_ATOM_die_tag:
143       DieTag = (dwarf::Tag)*FormValue.getAsUnsignedConstant();
144       break;
145     default:
146       break;
147     }
148   }
149   return {DieOffset, DieTag};
150 }
151 
152 void AppleAcceleratorTable::Header::dump(ScopedPrinter &W) const {
153   DictScope HeaderScope(W, "Header");
154   W.printHex("Magic", Magic);
155   W.printHex("Version", Version);
156   W.printHex("Hash function", HashFunction);
157   W.printNumber("Bucket count", BucketCount);
158   W.printNumber("Hashes count", HashCount);
159   W.printNumber("HeaderData length", HeaderDataLength);
160 }
161 
162 bool AppleAcceleratorTable::dumpName(ScopedPrinter &W,
163                                      SmallVectorImpl<DWARFFormValue> &AtomForms,
164                                      uint32_t *DataOffset) const {
165   DWARFFormParams FormParams = {Hdr.Version, 0, dwarf::DwarfFormat::DWARF32};
166   uint32_t NameOffset = *DataOffset;
167   if (!AccelSection.isValidOffsetForDataOfSize(*DataOffset, 4)) {
168     W.printString("Incorrectly terminated list.");
169     return false;
170   }
171   unsigned StringOffset = AccelSection.getRelocatedValue(4, DataOffset);
172   if (!StringOffset)
173     return false; // End of list
174 
175   DictScope NameScope(W, ("Name@0x" + Twine::utohexstr(NameOffset)).str());
176   W.startLine() << format("String: 0x%08x", StringOffset);
177   W.getOStream() << " \"" << StringSection.getCStr(&StringOffset) << "\"\n";
178 
179   unsigned NumData = AccelSection.getU32(DataOffset);
180   for (unsigned Data = 0; Data < NumData; ++Data) {
181     ListScope DataScope(W, ("Data " + Twine(Data)).str());
182     unsigned i = 0;
183     for (auto &Atom : AtomForms) {
184       W.startLine() << format("Atom[%d]: ", i++);
185       if (Atom.extractValue(AccelSection, DataOffset, FormParams))
186         Atom.dump(W.getOStream());
187       else
188         W.getOStream() << "Error extracting the value";
189       W.getOStream() << "\n";
190     }
191   }
192   return true; // more entries follow
193 }
194 
195 LLVM_DUMP_METHOD void AppleAcceleratorTable::dump(raw_ostream &OS) const {
196   if (!IsValid)
197     return;
198 
199   ScopedPrinter W(OS);
200 
201   Hdr.dump(W);
202 
203   W.printNumber("DIE offset base", HdrData.DIEOffsetBase);
204   W.printNumber("Number of atoms", uint64_t(HdrData.Atoms.size()));
205   SmallVector<DWARFFormValue, 3> AtomForms;
206   {
207     ListScope AtomsScope(W, "Atoms");
208     unsigned i = 0;
209     for (const auto &Atom : HdrData.Atoms) {
210       DictScope AtomScope(W, ("Atom " + Twine(i++)).str());
211       W.startLine() << "Type: " << formatAtom(Atom.first) << '\n';
212       W.startLine() << "Form: " << formatForm(Atom.second) << '\n';
213       AtomForms.push_back(DWARFFormValue(Atom.second));
214     }
215   }
216 
217   // Now go through the actual tables and dump them.
218   uint32_t Offset = sizeof(Hdr) + Hdr.HeaderDataLength;
219   unsigned HashesBase = Offset + Hdr.BucketCount * 4;
220   unsigned OffsetsBase = HashesBase + Hdr.HashCount * 4;
221 
222   for (unsigned Bucket = 0; Bucket < Hdr.BucketCount; ++Bucket) {
223     unsigned Index = AccelSection.getU32(&Offset);
224 
225     ListScope BucketScope(W, ("Bucket " + Twine(Bucket)).str());
226     if (Index == UINT32_MAX) {
227       W.printString("EMPTY");
228       continue;
229     }
230 
231     for (unsigned HashIdx = Index; HashIdx < Hdr.HashCount; ++HashIdx) {
232       unsigned HashOffset = HashesBase + HashIdx*4;
233       unsigned OffsetsOffset = OffsetsBase + HashIdx*4;
234       uint32_t Hash = AccelSection.getU32(&HashOffset);
235 
236       if (Hash % Hdr.BucketCount != Bucket)
237         break;
238 
239       unsigned DataOffset = AccelSection.getU32(&OffsetsOffset);
240       ListScope HashScope(W, ("Hash 0x" + Twine::utohexstr(Hash)).str());
241       if (!AccelSection.isValidOffset(DataOffset)) {
242         W.printString("Invalid section offset");
243         continue;
244       }
245       while (dumpName(W, AtomForms, &DataOffset))
246         /*empty*/;
247     }
248   }
249 }
250 
251 AppleAcceleratorTable::ValueIterator::ValueIterator(
252     const AppleAcceleratorTable &AccelTable, unsigned Offset)
253     : AccelTable(&AccelTable), DataOffset(Offset) {
254   if (!AccelTable.AccelSection.isValidOffsetForDataOfSize(DataOffset, 4))
255     return;
256 
257   for (const auto &Atom : AccelTable.HdrData.Atoms)
258     AtomForms.push_back(DWARFFormValue(Atom.second));
259 
260   // Read the first entry.
261   NumData = AccelTable.AccelSection.getU32(&DataOffset);
262   Next();
263 }
264 
265 void AppleAcceleratorTable::ValueIterator::Next() {
266   assert(NumData > 0 && "attempted to increment iterator past the end");
267   auto &AccelSection = AccelTable->AccelSection;
268   if (Data >= NumData ||
269       !AccelSection.isValidOffsetForDataOfSize(DataOffset, 4)) {
270     NumData = 0;
271     return;
272   }
273   DWARFFormParams FormParams = {AccelTable->Hdr.Version, 0,
274                                 dwarf::DwarfFormat::DWARF32};
275   for (auto &Atom : AtomForms)
276     Atom.extractValue(AccelSection, &DataOffset, FormParams);
277   ++Data;
278 }
279 
280 iterator_range<AppleAcceleratorTable::ValueIterator>
281 AppleAcceleratorTable::equal_range(StringRef Key) const {
282   if (!IsValid)
283     return make_range(ValueIterator(), ValueIterator());
284 
285   // Find the bucket.
286   unsigned HashValue = djbHash(Key);
287   unsigned Bucket = HashValue % Hdr.BucketCount;
288   unsigned BucketBase = sizeof(Hdr) + Hdr.HeaderDataLength;
289   unsigned HashesBase = BucketBase + Hdr.BucketCount * 4;
290   unsigned OffsetsBase = HashesBase + Hdr.HashCount * 4;
291 
292   unsigned BucketOffset = BucketBase + Bucket * 4;
293   unsigned Index = AccelSection.getU32(&BucketOffset);
294 
295   // Search through all hashes in the bucket.
296   for (unsigned HashIdx = Index; HashIdx < Hdr.HashCount; ++HashIdx) {
297     unsigned HashOffset = HashesBase + HashIdx * 4;
298     unsigned OffsetsOffset = OffsetsBase + HashIdx * 4;
299     uint32_t Hash = AccelSection.getU32(&HashOffset);
300 
301     if (Hash % Hdr.BucketCount != Bucket)
302       // We are already in the next bucket.
303       break;
304 
305     unsigned DataOffset = AccelSection.getU32(&OffsetsOffset);
306     unsigned StringOffset = AccelSection.getRelocatedValue(4, &DataOffset);
307     if (!StringOffset)
308       break;
309 
310     // Finally, compare the key.
311     if (Key == StringSection.getCStr(&StringOffset))
312       return make_range({*this, DataOffset}, ValueIterator());
313   }
314   return make_range(ValueIterator(), ValueIterator());
315 }
316 
317 void DWARFDebugNames::Header::dump(ScopedPrinter &W) const {
318   DictScope HeaderScope(W, "Header");
319   W.printHex("Length", UnitLength);
320   W.printNumber("Version", Version);
321   W.printHex("Padding", Padding);
322   W.printNumber("CU count", CompUnitCount);
323   W.printNumber("Local TU count", LocalTypeUnitCount);
324   W.printNumber("Foreign TU count", ForeignTypeUnitCount);
325   W.printNumber("Bucket count", BucketCount);
326   W.printNumber("Name count", NameCount);
327   W.printHex("Abbreviations table size", AbbrevTableSize);
328   W.startLine() << "Augmentation: '" << AugmentationString << "'\n";
329 }
330 
331 llvm::Error DWARFDebugNames::Header::extract(const DWARFDataExtractor &AS,
332                                              uint32_t *Offset) {
333   // Check that we can read the fixed-size part.
334   if (!AS.isValidOffset(*Offset + sizeof(HeaderPOD) - 1))
335     return make_error<StringError>("Section too small: cannot read header.",
336                                    inconvertibleErrorCode());
337 
338   UnitLength = AS.getU32(Offset);
339   Version = AS.getU16(Offset);
340   Padding = AS.getU16(Offset);
341   CompUnitCount = AS.getU32(Offset);
342   LocalTypeUnitCount = AS.getU32(Offset);
343   ForeignTypeUnitCount = AS.getU32(Offset);
344   BucketCount = AS.getU32(Offset);
345   NameCount = AS.getU32(Offset);
346   AbbrevTableSize = AS.getU32(Offset);
347   AugmentationStringSize = AS.getU32(Offset);
348 
349   if (!AS.isValidOffsetForDataOfSize(*Offset, AugmentationStringSize))
350     return make_error<StringError>(
351         "Section too small: cannot read header augmentation.",
352         inconvertibleErrorCode());
353   AugmentationString.resize(AugmentationStringSize);
354   AS.getU8(Offset, reinterpret_cast<uint8_t *>(AugmentationString.data()),
355            AugmentationStringSize);
356   *Offset = alignTo(*Offset, 4);
357   return Error::success();
358 }
359 
360 void DWARFDebugNames::Abbrev::dump(ScopedPrinter &W) const {
361   DictScope AbbrevScope(W, ("Abbreviation 0x" + Twine::utohexstr(Code)).str());
362   W.startLine() << "Tag: " << formatTag(Tag) << '\n';
363 
364   for (const auto &Attr : Attributes) {
365     W.startLine() << formatIndex(Attr.Index) << ": " << formatForm(Attr.Form)
366                   << '\n';
367   }
368 }
369 
370 static constexpr DWARFDebugNames::AttributeEncoding sentinelAttrEnc() {
371   return {dwarf::Index(0), dwarf::Form(0)};
372 }
373 
374 static bool isSentinel(const DWARFDebugNames::AttributeEncoding &AE) {
375   return AE == sentinelAttrEnc();
376 }
377 
378 static DWARFDebugNames::Abbrev sentinelAbbrev() {
379   return DWARFDebugNames::Abbrev(0, dwarf::Tag(0), {});
380 }
381 
382 static bool isSentinel(const DWARFDebugNames::Abbrev &Abbr) {
383   return Abbr.Code == 0;
384 }
385 
386 DWARFDebugNames::Abbrev DWARFDebugNames::AbbrevMapInfo::getEmptyKey() {
387   return sentinelAbbrev();
388 }
389 
390 DWARFDebugNames::Abbrev DWARFDebugNames::AbbrevMapInfo::getTombstoneKey() {
391   return DWARFDebugNames::Abbrev(~0, dwarf::Tag(0), {});
392 }
393 
394 Expected<DWARFDebugNames::AttributeEncoding>
395 DWARFDebugNames::NameIndex::extractAttributeEncoding(uint32_t *Offset) {
396   if (*Offset >= EntriesBase) {
397     return make_error<StringError>("Incorrectly terminated abbreviation table.",
398                                    inconvertibleErrorCode());
399   }
400 
401   uint32_t Index = Section.AccelSection.getULEB128(Offset);
402   uint32_t Form = Section.AccelSection.getULEB128(Offset);
403   return AttributeEncoding(dwarf::Index(Index), dwarf::Form(Form));
404 }
405 
406 Expected<std::vector<DWARFDebugNames::AttributeEncoding>>
407 DWARFDebugNames::NameIndex::extractAttributeEncodings(uint32_t *Offset) {
408   std::vector<AttributeEncoding> Result;
409   for (;;) {
410     auto AttrEncOr = extractAttributeEncoding(Offset);
411     if (!AttrEncOr)
412       return AttrEncOr.takeError();
413     if (isSentinel(*AttrEncOr))
414       return std::move(Result);
415 
416     Result.emplace_back(*AttrEncOr);
417   }
418 }
419 
420 Expected<DWARFDebugNames::Abbrev>
421 DWARFDebugNames::NameIndex::extractAbbrev(uint32_t *Offset) {
422   if (*Offset >= EntriesBase) {
423     return make_error<StringError>("Incorrectly terminated abbreviation table.",
424                                    inconvertibleErrorCode());
425   }
426 
427   uint32_t Code = Section.AccelSection.getULEB128(Offset);
428   if (Code == 0)
429     return sentinelAbbrev();
430 
431   uint32_t Tag = Section.AccelSection.getULEB128(Offset);
432   auto AttrEncOr = extractAttributeEncodings(Offset);
433   if (!AttrEncOr)
434     return AttrEncOr.takeError();
435   return Abbrev(Code, dwarf::Tag(Tag), std::move(*AttrEncOr));
436 }
437 
438 Error DWARFDebugNames::NameIndex::extract() {
439   const DWARFDataExtractor &AS = Section.AccelSection;
440   uint32_t Offset = Base;
441   if (Error E = Hdr.extract(AS, &Offset))
442     return E;
443 
444   CUsBase = Offset;
445   Offset += Hdr.CompUnitCount * 4;
446   Offset += Hdr.LocalTypeUnitCount * 4;
447   Offset += Hdr.ForeignTypeUnitCount * 8;
448   BucketsBase = Offset;
449   Offset += Hdr.BucketCount * 4;
450   HashesBase = Offset;
451   if (Hdr.BucketCount > 0)
452     Offset += Hdr.NameCount * 4;
453   StringOffsetsBase = Offset;
454   Offset += Hdr.NameCount * 4;
455   EntryOffsetsBase = Offset;
456   Offset += Hdr.NameCount * 4;
457 
458   if (!AS.isValidOffsetForDataOfSize(Offset, Hdr.AbbrevTableSize))
459     return make_error<StringError>(
460         "Section too small: cannot read abbreviations.",
461         inconvertibleErrorCode());
462 
463   EntriesBase = Offset + Hdr.AbbrevTableSize;
464 
465   for (;;) {
466     auto AbbrevOr = extractAbbrev(&Offset);
467     if (!AbbrevOr)
468       return AbbrevOr.takeError();
469     if (isSentinel(*AbbrevOr))
470       return Error::success();
471 
472     if (!Abbrevs.insert(std::move(*AbbrevOr)).second) {
473       return make_error<StringError>("Duplicate abbreviation code.",
474                                      inconvertibleErrorCode());
475     }
476   }
477 }
478 
479 DWARFDebugNames::Entry::Entry(const Abbrev &Abbr) : Abbr(Abbr) {
480   // This merely creates form values. It is up to the caller
481   // (NameIndex::getEntry) to populate them.
482   Values.reserve(Abbr.Attributes.size());
483   for (const auto &Attr : Abbr.Attributes)
484     Values.emplace_back(Attr.Form);
485 }
486 
487 void DWARFDebugNames::Entry::dump(ScopedPrinter &W) const {
488   W.printHex("Abbrev", Abbr.Code);
489   W.startLine() << "Tag: " << formatTag(Abbr.Tag) << "\n";
490 
491   assert(Abbr.Attributes.size() == Values.size());
492   for (uint32_t I = 0, E = Values.size(); I < E; ++I) {
493     W.startLine() << formatIndex(Abbr.Attributes[I].Index) << ": ";
494     Values[I].dump(W.getOStream());
495     W.getOStream() << '\n';
496   }
497 }
498 
499 char DWARFDebugNames::SentinelError::ID;
500 std::error_code DWARFDebugNames::SentinelError::convertToErrorCode() const {
501   return inconvertibleErrorCode();
502 }
503 
504 uint32_t DWARFDebugNames::NameIndex::getCUOffset(uint32_t CU) const {
505   assert(CU < Hdr.CompUnitCount);
506   uint32_t Offset = CUsBase + 4 * CU;
507   return Section.AccelSection.getRelocatedValue(4, &Offset);
508 }
509 
510 uint32_t DWARFDebugNames::NameIndex::getLocalTUOffset(uint32_t TU) const {
511   assert(TU < Hdr.LocalTypeUnitCount);
512   uint32_t Offset = CUsBase + Hdr.CompUnitCount * 4;
513   return Section.AccelSection.getRelocatedValue(4, &Offset);
514 }
515 
516 uint64_t DWARFDebugNames::NameIndex::getForeignTUOffset(uint32_t TU) const {
517   assert(TU < Hdr.ForeignTypeUnitCount);
518   uint32_t Offset = CUsBase + (Hdr.CompUnitCount + Hdr.LocalTypeUnitCount) * 4;
519   return Section.AccelSection.getU64(&Offset);
520 }
521 
522 Expected<DWARFDebugNames::Entry>
523 DWARFDebugNames::NameIndex::getEntry(uint32_t *Offset) const {
524   const DWARFDataExtractor &AS = Section.AccelSection;
525   if (!AS.isValidOffset(*Offset))
526     return make_error<StringError>("Incorrectly terminated entry list",
527                                    inconvertibleErrorCode());
528 
529   uint32_t AbbrevCode = AS.getULEB128(Offset);
530   if (AbbrevCode == 0)
531     return make_error<SentinelError>();
532 
533   const auto AbbrevIt = Abbrevs.find_as(AbbrevCode);
534   if (AbbrevIt == Abbrevs.end())
535     return make_error<StringError>("Invalid abbreviation",
536                                    inconvertibleErrorCode());
537 
538   Entry E(*AbbrevIt);
539 
540   DWARFFormParams FormParams = {Hdr.Version, 0, dwarf::DwarfFormat::DWARF32};
541   for (auto &Value : E.Values) {
542     if (!Value.extractValue(AS, Offset, FormParams))
543       return make_error<StringError>("Error extracting index attribute values",
544                                      inconvertibleErrorCode());
545   }
546   return std::move(E);
547 }
548 
549 DWARFDebugNames::NameTableEntry
550 DWARFDebugNames::NameIndex::getNameTableEntry(uint32_t Index) const {
551   assert(0 < Index && Index <= Hdr.NameCount);
552   uint32_t StringOffsetOffset = StringOffsetsBase + 4 * (Index - 1);
553   uint32_t EntryOffsetOffset = EntryOffsetsBase + 4 * (Index - 1);
554   const DWARFDataExtractor &AS = Section.AccelSection;
555 
556   uint32_t StringOffset = AS.getRelocatedValue(4, &StringOffsetOffset);
557   uint32_t EntryOffset = AS.getU32(&EntryOffsetOffset);
558   EntryOffset += EntriesBase;
559   return {StringOffset, EntryOffset};
560 }
561 
562 uint32_t
563 DWARFDebugNames::NameIndex::getBucketArrayEntry(uint32_t Bucket) const {
564   assert(Bucket < Hdr.BucketCount);
565   uint32_t BucketOffset = BucketsBase + 4 * Bucket;
566   return Section.AccelSection.getU32(&BucketOffset);
567 }
568 
569 uint32_t DWARFDebugNames::NameIndex::getHashArrayEntry(uint32_t Index) const {
570   assert(0 < Index && Index <= Hdr.NameCount);
571   uint32_t HashOffset = HashesBase + 4 * (Index - 1);
572   return Section.AccelSection.getU32(&HashOffset);
573 }
574 
575 // Returns true if we should continue scanning for entries, false if this is the
576 // last (sentinel) entry). In case of a parsing error we also return false, as
577 // it's not possible to recover this entry list (but the other lists may still
578 // parse OK).
579 bool DWARFDebugNames::NameIndex::dumpEntry(ScopedPrinter &W,
580                                            uint32_t *Offset) const {
581   uint32_t EntryId = *Offset;
582   auto EntryOr = getEntry(Offset);
583   if (!EntryOr) {
584     handleAllErrors(EntryOr.takeError(), [](const SentinelError &) {},
585                     [&W](const ErrorInfoBase &EI) { EI.log(W.startLine()); });
586     return false;
587   }
588 
589   DictScope EntryScope(W, ("Entry @ 0x" + Twine::utohexstr(EntryId)).str());
590   EntryOr->dump(W);
591   return true;
592 }
593 
594 void DWARFDebugNames::NameIndex::dumpName(ScopedPrinter &W, uint32_t Index,
595                                           Optional<uint32_t> Hash) const {
596   const DataExtractor &SS = Section.StringSection;
597   NameTableEntry NTE = getNameTableEntry(Index);
598 
599   DictScope NameScope(W, ("Name " + Twine(Index)).str());
600   if (Hash)
601     W.printHex("Hash", *Hash);
602 
603   W.startLine() << format("String: 0x%08x", NTE.StringOffset);
604   W.getOStream() << " \"" << SS.getCStr(&NTE.StringOffset) << "\"\n";
605 
606   while (dumpEntry(W, &NTE.EntryOffset))
607     /*empty*/;
608 }
609 
610 void DWARFDebugNames::NameIndex::dumpCUs(ScopedPrinter &W) const {
611   ListScope CUScope(W, "Compilation Unit offsets");
612   for (uint32_t CU = 0; CU < Hdr.CompUnitCount; ++CU)
613     W.startLine() << format("CU[%u]: 0x%08x\n", CU, getCUOffset(CU));
614 }
615 
616 void DWARFDebugNames::NameIndex::dumpLocalTUs(ScopedPrinter &W) const {
617   if (Hdr.LocalTypeUnitCount == 0)
618     return;
619 
620   ListScope TUScope(W, "Local Type Unit offsets");
621   for (uint32_t TU = 0; TU < Hdr.LocalTypeUnitCount; ++TU)
622     W.startLine() << format("LocalTU[%u]: 0x%08x\n", TU, getLocalTUOffset(TU));
623 }
624 
625 void DWARFDebugNames::NameIndex::dumpForeignTUs(ScopedPrinter &W) const {
626   if (Hdr.ForeignTypeUnitCount == 0)
627     return;
628 
629   ListScope TUScope(W, "Foreign Type Unit signatures");
630   for (uint32_t TU = 0; TU < Hdr.ForeignTypeUnitCount; ++TU) {
631     W.startLine() << format("ForeignTU[%u]: 0x%016" PRIx64 "\n", TU,
632                             getForeignTUOffset(TU));
633   }
634 }
635 
636 void DWARFDebugNames::NameIndex::dumpAbbreviations(ScopedPrinter &W) const {
637   ListScope AbbrevsScope(W, "Abbreviations");
638   for (const auto &Abbr : Abbrevs)
639     Abbr.dump(W);
640 }
641 
642 void DWARFDebugNames::NameIndex::dumpBucket(ScopedPrinter &W,
643                                             uint32_t Bucket) const {
644   ListScope BucketScope(W, ("Bucket " + Twine(Bucket)).str());
645   uint32_t Index = getBucketArrayEntry(Bucket);
646   if (Index == 0) {
647     W.printString("EMPTY");
648     return;
649   }
650   if (Index > Hdr.NameCount) {
651     W.printString("Name index is invalid");
652     return;
653   }
654 
655   for (; Index <= Hdr.NameCount; ++Index) {
656     uint32_t Hash = getHashArrayEntry(Index);
657     if (Hash % Hdr.BucketCount != Bucket)
658       break;
659 
660     dumpName(W, Index, Hash);
661   }
662 }
663 
664 LLVM_DUMP_METHOD void DWARFDebugNames::NameIndex::dump(ScopedPrinter &W) const {
665   DictScope UnitScope(W, ("Name Index @ 0x" + Twine::utohexstr(Base)).str());
666   Hdr.dump(W);
667   dumpCUs(W);
668   dumpLocalTUs(W);
669   dumpForeignTUs(W);
670   dumpAbbreviations(W);
671 
672   if (Hdr.BucketCount > 0) {
673     for (uint32_t Bucket = 0; Bucket < Hdr.BucketCount; ++Bucket)
674       dumpBucket(W, Bucket);
675     return;
676   }
677 
678   W.startLine() << "Hash table not present\n";
679   for (uint32_t Index = 1; Index <= Hdr.NameCount; ++Index)
680     dumpName(W, Index, None);
681 }
682 
683 llvm::Error DWARFDebugNames::extract() {
684   uint32_t Offset = 0;
685   while (AccelSection.isValidOffset(Offset)) {
686     NameIndex Next(*this, Offset);
687     if (llvm::Error E = Next.extract())
688       return E;
689     Offset = Next.getNextUnitOffset();
690     NameIndices.push_back(std::move(Next));
691   }
692   return Error::success();
693 }
694 
695 LLVM_DUMP_METHOD void DWARFDebugNames::dump(raw_ostream &OS) const {
696   ScopedPrinter W(OS);
697   for (const NameIndex &NI : NameIndices)
698     NI.dump(W);
699 }
700