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