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