LLVM  10.0.0svn
DWARFAcceleratorTable.cpp
Go to the documentation of this file.
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 
10 
11 #include "llvm/ADT/SmallVector.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"
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 
43 
45  uint64_t Offset = 0;
46 
47  // Check that we can at least read the header.
48  if (!AccelSection.isValidOffset(offsetof(Header, HeaderDataLength) + 4))
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(
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 
82 uint32_t AppleAcceleratorTable::getNumBuckets() { return Hdr.BucketCount; }
83 uint32_t AppleAcceleratorTable::getNumHashes() { return Hdr.HashCount; }
86  return Hdr.HeaderDataLength;
87 }
88 
89 ArrayRef<std::pair<AppleAcceleratorTable::HeaderData::AtomType,
92  return HdrData.Atoms;
93 }
94 
96  for (auto Atom : getAtomsDesc()) {
97  DWARFFormValue FormValue(Atom.second);
98  switch (Atom.first) {
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<uint64_t, dwarf::Tag>
115 AppleAcceleratorTable::readAtoms(uint64_t *HashDataOffset) {
116  uint64_t DieOffset = dwarf::DW_INVALID_OFFSET;
117  dwarf::Tag DieTag = dwarf::DW_TAG_null;
119 
120  for (auto Atom : getAtomsDesc()) {
121  DWARFFormValue FormValue(Atom.second);
122  FormValue.extractValue(AccelSection, HashDataOffset, FormParams);
123  switch (Atom.first) {
125  DieOffset = *FormValue.getAsUnsignedConstant();
126  break;
128  DieTag = (dwarf::Tag)*FormValue.getAsUnsignedConstant();
129  break;
130  default:
131  break;
132  }
133  }
134  return {DieOffset, DieTag};
135 }
136 
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(
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,
166  uint64_t *DataOffset) const {
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 
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()));
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 
259 AppleAcceleratorTable::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 
267 void AppleAcceleratorTable::Entry::extract(
268  const AppleAcceleratorTable &AccelTable, uint64_t *Offset) {
269 
270  dwarf::FormParams FormParams = {AccelTable.Hdr.Version, 0,
272  for (auto &Atom : Values)
273  Atom.extractValue(AccelTable.AccelSection, Offset, FormParams);
274 }
275 
277 AppleAcceleratorTable::Entry::lookup(HeaderData::AtomType Atom) const {
278  assert(HdrData && "Dereferencing end iterator?");
279  assert(HdrData->Atoms.size() == Values.size());
280  for (const 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 
288  return HdrData->extractOffset(lookup(dwarf::DW_ATOM_die_offset));
289 }
290 
292  return HdrData->extractOffset(lookup(dwarf::DW_ATOM_cu_offset));
293 }
294 
297  if (!Tag)
298  return None;
299  if (Optional<uint64_t> Value = Tag->getAsUnsignedConstant())
300  return dwarf::Tag(*Value);
301  return None;
302 }
303 
305  const AppleAcceleratorTable &AccelTable, uint64_t Offset)
306  : AccelTable(&AccelTable), Current(AccelTable.HdrData), DataOffset(Offset) {
307  if (!AccelTable.AccelSection.isValidOffsetForDataOfSize(DataOffset, 4))
308  return;
309 
310  // Read the first entry.
311  NumData = AccelTable.AccelSection.getU32(&DataOffset);
312  Next();
313 }
314 
315 void AppleAcceleratorTable::ValueIterator::Next() {
316  assert(NumData > 0 && "attempted to increment iterator past the end");
317  auto &AccelSection = AccelTable->AccelSection;
318  if (Data >= NumData ||
319  !AccelSection.isValidOffsetForDataOfSize(DataOffset, 4)) {
320  NumData = 0;
321  DataOffset = 0;
322  return;
323  }
324  Current.extract(*AccelTable, &DataOffset);
325  ++Data;
326 }
327 
330  if (!IsValid)
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  }
363 }
364 
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 
380  uint64_t *Offset) {
381  // Check that we can read the fixed-size part.
382  if (!AS.isValidOffset(*Offset + sizeof(HeaderPOD) - 1))
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(
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 
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 
416  return {dwarf::Index(0), dwarf::Form(0)};
417 }
418 
420  return AE == sentinelAttrEnc();
421 }
422 
424  return DWARFDebugNames::Abbrev(0, dwarf::Tag(0), {});
425 }
426 
427 static bool isSentinel(const DWARFDebugNames::Abbrev &Abbr) {
428  return Abbr.Code == 0;
429 }
430 
431 DWARFDebugNames::Abbrev DWARFDebugNames::AbbrevMapInfo::getEmptyKey() {
432  return sentinelAbbrev();
433 }
434 
435 DWARFDebugNames::Abbrev DWARFDebugNames::AbbrevMapInfo::getTombstoneKey() {
436  return DWARFDebugNames::Abbrev(~0, dwarf::Tag(0), {});
437 }
438 
440 DWARFDebugNames::NameIndex::extractAttributeEncoding(uint64_t *Offset) {
441  if (*Offset >= EntriesBase) {
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 
452 DWARFDebugNames::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 
466 DWARFDebugNames::NameIndex::extractAbbrev(uint64_t *Offset) {
467  if (*Offset >= EntriesBase) {
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 
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))
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)
518  "Duplicate abbreviation code.");
519  }
520 }
521 
522 DWARFDebugNames::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 
533  assert(Abbr->Attributes.size() == Values.size());
534  for (const 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 
542  if (Optional<DWARFFormValue> Off = lookup(dwarf::DW_IDX_die_offset))
543  return Off->getAsReferenceUVal();
544  return None;
545 }
546 
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 
558  Optional<uint64_t> Index = getCUIndex();
559  if (!Index || *Index >= NameIdx->getCUCount())
560  return None;
561  return NameIdx->getCUOffset(*Index);
562 }
563 
565  W.printHex("Abbrev", Abbr->Code);
566  W.startLine() << formatv("Tag: {0}\n", Abbr->Tag);
567  assert(Abbr->Attributes.size() == Values.size());
568  for (const 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 
577  return inconvertibleErrorCode();
578 }
579 
581  assert(CU < Hdr.CompUnitCount);
582  uint64_t Offset = CUsBase + 4 * CU;
583  return Section.AccelSection.getRelocatedValue(4, &Offset);
584 }
585 
587  assert(TU < Hdr.LocalTypeUnitCount);
588  uint64_t Offset = CUsBase + 4 * (Hdr.CompUnitCount + TU);
589  return Section.AccelSection.getRelocatedValue(4, &Offset);
590 }
591 
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 
600 DWARFDebugNames::NameIndex::getEntry(uint64_t *Offset) const {
601  const DWARFDataExtractor &AS = Section.AccelSection;
602  if (!AS.isValidOffset(*Offset))
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 
617  for (auto &Value : E.Values) {
618  if (!Value.extractValue(AS, Offset, FormParams))
620  "Error extracting index attribute values.");
621  }
622  return std::move(E);
623 }
624 
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 
638 uint32_t
640  assert(Bucket < Hdr.BucketCount);
641  uint64_t BucketOffset = BucketsBase + 4 * Bucket;
642  return Section.AccelSection.getU32(&BucketOffset);
643 }
644 
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).
655 bool 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 
670 void 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 
685 void 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 
691 void 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 
701 void 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 
712 void DWARFDebugNames::NameIndex::dumpAbbreviations(ScopedPrinter &W) const {
713  ListScope AbbrevsScope(W, "Abbreviations");
714  for (const auto &Abbr : Abbrevs)
715  Abbr.dump(W);
716 }
717 
718 void 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 
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 
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 
773  return make_range(ValueIterator(*this, Key), ValueIterator());
774 }
775 
777  ScopedPrinter W(OS);
778  for (const NameIndex &NI : NameIndices)
779  NI.dump(W);
780 }
781 
783 DWARFDebugNames::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 
815 bool 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 
825 bool DWARFDebugNames::ValueIterator::findInCurrentIndex() {
826  Optional<uint64_t> Offset = findEntryOffsetInCurrentIndex();
827  if (!Offset)
828  return false;
829  DataOffset = *Offset;
830  return getEntryAtCurrentOffset();
831 }
832 
833 void 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 
842 void 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 
861  StringRef Key)
862  : CurrentIndex(AccelTable.NameIndices.begin()), IsLocal(false), Key(Key) {
863  searchFromStartOfCurrentIndex();
864 }
865 
867  const DWARFDebugNames::NameIndex &NI, StringRef Key)
868  : CurrentIndex(&NI), IsLocal(true), Key(Key) {
869  if (!findInCurrentIndex())
870  setEnd();
871 }
872 
875  if (NameIndices.empty())
877  return make_range(ValueIterator(*this, Key), ValueIterator());
878 }
879 
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 }
iterator_range< ValueIterator > equal_range(StringRef Key) const
Look up all entries in the accelerator table matching Key.
A helper struct providing information about the byte size of DW_FORM values that vary in size dependi...
Definition: Dwarf.h:488
void dump(ScopedPrinter &W) const
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
iterator_range< ValueIterator > equal_range(StringRef Key) const
Look up all entries in the accelerator table matching Key.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
StringRef AtomTypeString(unsigned Atom)
Definition: Dwarf.cpp:526
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:473
Error extract(const DWARFDataExtractor &AS, uint64_t *Offset)
uint64_t getULEB128(uint64_t *offset_ptr) const
Extract a unsigned LEB128 value from *offset_ptr.
std::vector< AttributeEncoding > Attributes
List of index attributes.
void dump(ScopedPrinter &W) const
SmallVector< DWARFFormValue, 3 > Values
uint32_t getU32(uint64_t *offset_ptr) const
Extract a uint32_t value from *offset_ptr.
Optional< DWARFFormValue > lookup(dwarf::Index Index) const
Returns the value of the Index Attribute in this Accelerator Entry, if the Entry contains such Attrib...
static constexpr DWARFDebugNames::AttributeEncoding sentinelAttrEnc()
const char * getCStr(uint64_t *offset_ptr) const
Extract a C string from *offset_ptr.
This class holds an abstract representation of an Accelerator Table, consisting of a sequence of buck...
Definition: AccelTable.h:198
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition: Format.h:124
uint64_t getCUOffset(uint32_t CU) const
Reads offset of compilation unit CU. CU is 0-based.
auto formatv(const char *Fmt, Ts &&... Vals) -> formatv_object< decltype(std::make_tuple(detail::build_format_adapter(std::forward< Ts >(Vals))...))>
static void dump(StringRef Title, SpillInfo const &Spills)
Definition: CoroFrame.cpp:322
block Block Frequency true
std::error_code convertToErrorCode() const override
Convert this error to a std::error_code.
bool extractValue(const DWARFDataExtractor &Data, uint64_t *OffsetPtr, dwarf::FormParams FormParams, const DWARFContext *Context=nullptr, const DWARFUnit *Unit=nullptr)
Extracts a value in Data at offset *OffsetPtr.
Optional< DWARFFormValue > lookup(HeaderData::AtomType Atom) const
Returns the value of the Atom in this Accelerator Entry, if the Entry contains such Atom...
bool isFormClass(FormClass FC) const
Base class for error info classes.
Definition: Error.h:48
Abbreviation describing the encoding of Name Index entries.
uint64_t getForeignTUSignature(uint32_t TU) const
Reads signature of foreign type unit TU. TU is 0-based.
uint64_t getRelocatedValue(uint32_t Size, uint64_t *Off, uint64_t *SectionIndex=nullptr) const
Extracts a value and applies a relocation to the result if one exists for the given offset...
dwarf::Form getForm() const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
uint64_t getRawUValue() const
ArrayRef< std::pair< HeaderData::AtomType, HeaderData::Form > > getAtomsDesc()
Return the Atom description, which can be used to interpret the raw values of the Accelerator Entries...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
Tagged union holding either a T or a Error.
Definition: yaml2obj.h:21
Index attribute and its encoding.
static const uint16_t * lookup(unsigned opcode, unsigned domain, ArrayRef< uint16_t[3]> Table)
LLVM_NODISCARD bool empty() const
empty - Check if the string is empty.
Definition: StringRef.h:126
dwarf::Tag Tag
Dwarf Tag of the described entity.
Key
PAL metadata keys.
raw_ostream & getOStream()
uint64_t getLocalTUOffset(uint32_t TU) const
Reads offset of local type unit TU, TU is 0-based.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
Represents a single accelerator table within the DWARF v5 .debug_names section.
Optional< uint64_t > getCUOffset() const override
Returns the Offset of the Compilation Unit associated with this Accelerator Entry or None if the Comp...
uint32_t getBucketArrayEntry(uint32_t Bucket) const
Reads an entry in the Bucket Array for the given Bucket.
Optional< uint64_t > getCUIndex() const
Returns the Index into the Compilation Unit list of the owning Name Index or None if this Accelerator...
static DWARFDebugNames::Abbrev sentinelAbbrev()
static Atom formatAtom(unsigned Atom)
Expected< Entry > getEntry(uint64_t *Offset) const
std::pair< uint64_t, dwarf::Tag > readAtoms(uint64_t *HashDataOffset)
Return information related to the DWARF DIE we&#39;re looking for when performing a lookup by name...
DWARF v5-specific implementation of an Accelerator Entry.
This implements the Apple accelerator table format, a precursor of the DWARF 5 accelerator table form...
const uint32_t DW_INVALID_OFFSET
Identifier of an invalid DIE offset in the .debug_info section.
Definition: Dwarf.h:80
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
raw_ostream & startLine()
Optional< uint64_t > getDIEUnitOffset() const
Returns the Offset of the DIE within the containing CU or TU.
#define offsetof(TYPE, MEMBER)
NameTableEntry getNameTableEntry(uint32_t Index) const
Reads an entry in the Name Table for the given Index.
uint32_t getHashArrayEntry(uint32_t Index) const
Reads an entry in the Hash Array for the given Index.
Optional< uint64_t > getAsUnsignedConstant() const
void printHex(StringRef Label, T Value)
DWARF v5 Name Index header.
uint8_t getU8(uint64_t *offset_ptr) const
Extract a uint8_t value from *offset_ptr.
detail::zippy< detail::zip_first, T, U, Args... > zip_first(T &&t, U &&u, Args &&... args)
zip iterator that, for the sake of efficiency, assumes the first iteratee to be the shortest...
Definition: STLExtras.h:676
void consumeError(Error Err)
Consume a Error without doing anything.
Definition: Error.h:981
uint32_t djbHash(StringRef Buffer, uint32_t H=5381)
The Bernstein hash function used by the DWARF accelerator tables.
Definition: DJB.h:21
static const char *const Magic
Definition: Archive.cpp:41
A DataExtractor (typically for an in-memory copy of an object-file section) plus a relocation map for...
void printString(StringRef Value)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
const char * getString() const
Return the string referenced by this name table entry or nullptr if the string offset is not valid...
.debug_names section consists of one or more units.
void handleAllErrors(Error E, HandlerTs &&... Handlers)
Behaves the same as handleErrors, except that by contract all errors must be handled by the given han...
Definition: Error.h:904
static ErrorSuccess success()
Create a success value.
Definition: Error.h:326
void printNumber(StringRef Label, uint64_t Value)
bool isValidOffsetForDataOfSize(uint64_t offset, uint64_t length) const
Test the availability of length bytes of data from offset.
void dump(ScopedPrinter &W) const
A single entry in the Name Table (DWARF v5 sect.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
uint32_t caseFoldingDjbHash(StringRef Buffer, uint32_t H=5381)
Computes the Bernstein hash after folding the input according to the Dwarf 5 standard case folding ru...
Definition: DJB.cpp:71
void dump(raw_ostream &OS) const override
static Twine utohexstr(const uint64_t &Val)
Definition: Twine.h:387
uint32_t getIndex() const
Return the index of this name in the parent Name Index.
bool isValidOffset(uint64_t offset) const
Test the validity of offset.
A range adaptor for a pair of iterators.
This file contains constants used for implementing Dwarf debug support.
Optional< uint64_t > getDIESectionOffset() const
Returns the Section Offset of the Debug Info Entry associated with this Accelerator Entry or None if ...
Error returned by NameIndex::getEntry to report it has reached the end of the entry list...
StringRef AtomValueString(uint16_t Atom, unsigned Val)
Returns the symbolic string representing Val when used as a value for atom Atom.
Definition: Dwarf.cpp:609
Optional< uint64_t > getCUOffset() const override
Returns the Offset of the Compilation Unit associated with this Accelerator Entry or None if the Comp...
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:126
const NameIndex * getCUNameIndex(uint64_t CUOffset)
Return the Name Index covering the compile unit at CUOffset, or nullptr if there is no Name Index cov...
void dump(ScopedPrinter &W) const
uint64_t getEntryOffset() const
Returns the offset of the first Entry in the list.
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2045
ValueIterator()=default
End marker.
void dump(raw_ostream &OS) const override
uint32_t Code
Abbreviation code.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool isSentinel(const DWARFDebugNames::AttributeEncoding &AE)
LLVM Value Representation.
Definition: Value.h:73
Lightweight error class with error context and mandatory checking.
Definition: Error.h:157
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
Optional< dwarf::Tag > getTag() const override
Returns the Tag of the Debug Info Entry associated with this Accelerator Entry or None if the Tag is ...
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
Marker as the end of a list of atoms.
Definition: Dwarf.h:363
for(unsigned i=Desc.getNumOperands(), e=OldMI.getNumOperands();i !=e;++i)
uint16_t getU16(uint64_t *offset_ptr) const
Extract a uint16_t value from *offset_ptr.
iterator_range< ValueIterator > equal_range(StringRef Key) const
Look up all entries in this Name Index matching Key.
Optional< uint64_t > getAsSectionOffset() const
uint64_t getStringOffset() const
Returns the offset of the name of the described entities.
const uint64_t Version
Definition: InstrProf.h:984
Error createStringError(std::error_code EC, char const *Fmt, const Ts &... Vals)
Create formatted StringError object.
Definition: Error.h:1163
std::error_code inconvertibleErrorCode()
The value returned by this function can be returned from convertToErrorCode for Error values where no...
Definition: Error.cpp:77