LLVM  7.0.0svn
DWARFAcceleratorTable.cpp
Go to the documentation of this file.
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 
11 
12 #include "llvm/ADT/SmallVector.h"
15 #include "llvm/Support/Compiler.h"
16 #include "llvm/Support/DJB.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  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.",
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.",
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<uint32_t, dwarf::Tag>
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  uint32_t *DataOffset) const {
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 
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()));
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(
263 
264  dwarf::FormParams FormParams = {AccelTable.Hdr.Version, 0,
266  for (auto &Atom : Values)
267  Atom.extractValue(AccelTable.AccelSection, Offset, FormParams);
268 }
269 
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 
282  return HdrData->extractOffset(lookup(dwarf::DW_ATOM_die_offset));
283 }
284 
286  return HdrData->extractOffset(lookup(dwarf::DW_ATOM_cu_offset));
287 }
288 
291  if (!Tag)
292  return None;
293  if (Optional<uint64_t> Value = Tag->getAsUnsignedConstant())
294  return dwarf::Tag(*Value);
295  return None;
296 }
297 
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  DataOffset = 0;
316  return;
317  }
318  Current.extract(*AccelTable, &DataOffset);
319  ++Data;
320 }
321 
324  if (!IsValid)
326 
327  // Find the bucket.
328  unsigned HashValue = djbHash(Key);
329  unsigned Bucket = HashValue % Hdr.BucketCount;
330  unsigned BucketBase = sizeof(Hdr) + Hdr.HeaderDataLength;
331  unsigned HashesBase = BucketBase + Hdr.BucketCount * 4;
332  unsigned OffsetsBase = HashesBase + Hdr.HashCount * 4;
333 
334  unsigned BucketOffset = BucketBase + Bucket * 4;
335  unsigned Index = AccelSection.getU32(&BucketOffset);
336 
337  // Search through all hashes in the bucket.
338  for (unsigned HashIdx = Index; HashIdx < Hdr.HashCount; ++HashIdx) {
339  unsigned HashOffset = HashesBase + HashIdx * 4;
340  unsigned OffsetsOffset = OffsetsBase + HashIdx * 4;
341  uint32_t Hash = AccelSection.getU32(&HashOffset);
342 
343  if (Hash % Hdr.BucketCount != Bucket)
344  // We are already in the next bucket.
345  break;
346 
347  unsigned DataOffset = AccelSection.getU32(&OffsetsOffset);
348  unsigned StringOffset = AccelSection.getRelocatedValue(4, &DataOffset);
349  if (!StringOffset)
350  break;
351 
352  // Finally, compare the key.
353  if (Key == StringSection.getCStr(&StringOffset))
354  return make_range({*this, DataOffset}, ValueIterator());
355  }
357 }
358 
360  DictScope HeaderScope(W, "Header");
361  W.printHex("Length", UnitLength);
362  W.printNumber("Version", Version);
363  W.printHex("Padding", Padding);
364  W.printNumber("CU count", CompUnitCount);
365  W.printNumber("Local TU count", LocalTypeUnitCount);
366  W.printNumber("Foreign TU count", ForeignTypeUnitCount);
367  W.printNumber("Bucket count", BucketCount);
368  W.printNumber("Name count", NameCount);
369  W.printHex("Abbreviations table size", AbbrevTableSize);
370  W.startLine() << "Augmentation: '" << AugmentationString << "'\n";
371 }
372 
374  uint32_t *Offset) {
375  // Check that we can read the fixed-size part.
376  if (!AS.isValidOffset(*Offset + sizeof(HeaderPOD) - 1))
377  return make_error<StringError>("Section too small: cannot read header.",
379 
380  UnitLength = AS.getU32(Offset);
381  Version = AS.getU16(Offset);
382  Padding = AS.getU16(Offset);
383  CompUnitCount = AS.getU32(Offset);
384  LocalTypeUnitCount = AS.getU32(Offset);
385  ForeignTypeUnitCount = AS.getU32(Offset);
386  BucketCount = AS.getU32(Offset);
387  NameCount = AS.getU32(Offset);
388  AbbrevTableSize = AS.getU32(Offset);
389  AugmentationStringSize = alignTo(AS.getU32(Offset), 4);
390 
391  if (!AS.isValidOffsetForDataOfSize(*Offset, AugmentationStringSize))
392  return make_error<StringError>(
393  "Section too small: cannot read header augmentation.",
395  AugmentationString.resize(AugmentationStringSize);
396  AS.getU8(Offset, reinterpret_cast<uint8_t *>(AugmentationString.data()),
397  AugmentationStringSize);
398  return Error::success();
399 }
400 
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 
410  return {dwarf::Index(0), dwarf::Form(0)};
411 }
412 
414  return AE == sentinelAttrEnc();
415 }
416 
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 
434 DWARFDebugNames::NameIndex::extractAttributeEncoding(uint32_t *Offset) {
435  if (*Offset >= EntriesBase) {
436  return make_error<StringError>("Incorrectly terminated abbreviation table.",
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 
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 
460 DWARFDebugNames::NameIndex::extractAbbrev(uint32_t *Offset) {
461  if (*Offset >= EntriesBase) {
462  return make_error<StringError>("Incorrectly terminated abbreviation table.",
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 
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.",
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.",
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 
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 
537  if (Optional<DWARFFormValue> Off = lookup(dwarf::DW_IDX_die_offset))
538  return Off->getAsReferenceUVal();
539  return None;
540 }
541 
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 
553  Optional<uint64_t> Index = getCUIndex();
554  if (!Index || *Index >= NameIdx->getCUCount())
555  return None;
556  return NameIdx->getCUOffset(*Index);
557 }
558 
560  W.printHex("Abbrev", Abbr->Code);
561  W.startLine() << formatv("Tag: {0}\n", Abbr->Tag);
562  assert(Abbr->Attributes.size() == Values.size());
563  for (const auto &Tuple : zip_first(Abbr->Attributes, Values)) {
564  W.startLine() << formatv("{0}: ", std::get<0>(Tuple).Index);
565  std::get<1>(Tuple).dump(W.getOStream());
566  W.getOStream() << '\n';
567  }
568 }
569 
572  return inconvertibleErrorCode();
573 }
574 
576  assert(CU < Hdr.CompUnitCount);
577  uint32_t Offset = CUsBase + 4 * CU;
578  return Section.AccelSection.getRelocatedValue(4, &Offset);
579 }
580 
582  assert(TU < Hdr.LocalTypeUnitCount);
583  uint32_t Offset = CUsBase + Hdr.CompUnitCount * 4;
584  return Section.AccelSection.getRelocatedValue(4, &Offset);
585 }
586 
588  assert(TU < Hdr.ForeignTypeUnitCount);
589  uint32_t Offset = CUsBase + (Hdr.CompUnitCount + Hdr.LocalTypeUnitCount) * 4;
590  return Section.AccelSection.getU64(&Offset);
591 }
592 
595  const DWARFDataExtractor &AS = Section.AccelSection;
596  if (!AS.isValidOffset(*Offset))
597  return make_error<StringError>("Incorrectly terminated entry list.",
599 
600  uint32_t AbbrevCode = AS.getULEB128(Offset);
601  if (AbbrevCode == 0)
602  return make_error<SentinelError>();
603 
604  const auto AbbrevIt = Abbrevs.find_as(AbbrevCode);
605  if (AbbrevIt == Abbrevs.end())
606  return make_error<StringError>("Invalid abbreviation.",
608 
609  Entry E(*this, *AbbrevIt);
610 
612  for (auto &Value : E.Values) {
613  if (!Value.extractValue(AS, Offset, FormParams))
614  return make_error<StringError>("Error extracting index attribute values.",
616  }
617  return std::move(E);
618 }
619 
622  assert(0 < Index && Index <= Hdr.NameCount);
623  uint32_t StringOffsetOffset = StringOffsetsBase + 4 * (Index - 1);
624  uint32_t EntryOffsetOffset = EntryOffsetsBase + 4 * (Index - 1);
625  const DWARFDataExtractor &AS = Section.AccelSection;
626 
627  uint32_t StringOffset = AS.getRelocatedValue(4, &StringOffsetOffset);
628  uint32_t EntryOffset = AS.getU32(&EntryOffsetOffset);
629  EntryOffset += EntriesBase;
630  return {Section.StringSection, Index, StringOffset, EntryOffset};
631 }
632 
633 uint32_t
635  assert(Bucket < Hdr.BucketCount);
636  uint32_t BucketOffset = BucketsBase + 4 * Bucket;
637  return Section.AccelSection.getU32(&BucketOffset);
638 }
639 
641  assert(0 < Index && Index <= Hdr.NameCount);
642  uint32_t HashOffset = HashesBase + 4 * (Index - 1);
643  return Section.AccelSection.getU32(&HashOffset);
644 }
645 
646 // Returns true if we should continue scanning for entries, false if this is the
647 // last (sentinel) entry). In case of a parsing error we also return false, as
648 // it's not possible to recover this entry list (but the other lists may still
649 // parse OK).
650 bool DWARFDebugNames::NameIndex::dumpEntry(ScopedPrinter &W,
651  uint32_t *Offset) const {
652  uint32_t EntryId = *Offset;
653  auto EntryOr = getEntry(Offset);
654  if (!EntryOr) {
655  handleAllErrors(EntryOr.takeError(), [](const SentinelError &) {},
656  [&W](const ErrorInfoBase &EI) { EI.log(W.startLine()); });
657  return false;
658  }
659 
660  DictScope EntryScope(W, ("Entry @ 0x" + Twine::utohexstr(EntryId)).str());
661  EntryOr->dump(W);
662  return true;
663 }
664 
665 void DWARFDebugNames::NameIndex::dumpName(ScopedPrinter &W,
666  const NameTableEntry &NTE,
667  Optional<uint32_t> Hash) const {
668  DictScope NameScope(W, ("Name " + Twine(NTE.getIndex())).str());
669  if (Hash)
670  W.printHex("Hash", *Hash);
671 
672  W.startLine() << format("String: 0x%08x", NTE.getStringOffset());
673  W.getOStream() << " \"" << NTE.getString() << "\"\n";
674 
675  uint32_t EntryOffset = NTE.getEntryOffset();
676  while (dumpEntry(W, &EntryOffset))
677  /*empty*/;
678 }
679 
680 void DWARFDebugNames::NameIndex::dumpCUs(ScopedPrinter &W) const {
681  ListScope CUScope(W, "Compilation Unit offsets");
682  for (uint32_t CU = 0; CU < Hdr.CompUnitCount; ++CU)
683  W.startLine() << format("CU[%u]: 0x%08x\n", CU, getCUOffset(CU));
684 }
685 
686 void DWARFDebugNames::NameIndex::dumpLocalTUs(ScopedPrinter &W) const {
687  if (Hdr.LocalTypeUnitCount == 0)
688  return;
689 
690  ListScope TUScope(W, "Local Type Unit offsets");
691  for (uint32_t TU = 0; TU < Hdr.LocalTypeUnitCount; ++TU)
692  W.startLine() << format("LocalTU[%u]: 0x%08x\n", TU, getLocalTUOffset(TU));
693 }
694 
695 void DWARFDebugNames::NameIndex::dumpForeignTUs(ScopedPrinter &W) const {
696  if (Hdr.ForeignTypeUnitCount == 0)
697  return;
698 
699  ListScope TUScope(W, "Foreign Type Unit signatures");
700  for (uint32_t TU = 0; TU < Hdr.ForeignTypeUnitCount; ++TU) {
701  W.startLine() << format("ForeignTU[%u]: 0x%016" PRIx64 "\n", TU,
702  getForeignTUSignature(TU));
703  }
704 }
705 
706 void DWARFDebugNames::NameIndex::dumpAbbreviations(ScopedPrinter &W) const {
707  ListScope AbbrevsScope(W, "Abbreviations");
708  for (const auto &Abbr : Abbrevs)
709  Abbr.dump(W);
710 }
711 
712 void DWARFDebugNames::NameIndex::dumpBucket(ScopedPrinter &W,
713  uint32_t Bucket) const {
714  ListScope BucketScope(W, ("Bucket " + Twine(Bucket)).str());
715  uint32_t Index = getBucketArrayEntry(Bucket);
716  if (Index == 0) {
717  W.printString("EMPTY");
718  return;
719  }
720  if (Index > Hdr.NameCount) {
721  W.printString("Name index is invalid");
722  return;
723  }
724 
725  for (; Index <= Hdr.NameCount; ++Index) {
726  uint32_t Hash = getHashArrayEntry(Index);
727  if (Hash % Hdr.BucketCount != Bucket)
728  break;
729 
730  dumpName(W, getNameTableEntry(Index), Hash);
731  }
732 }
733 
735  DictScope UnitScope(W, ("Name Index @ 0x" + Twine::utohexstr(Base)).str());
736  Hdr.dump(W);
737  dumpCUs(W);
738  dumpLocalTUs(W);
739  dumpForeignTUs(W);
740  dumpAbbreviations(W);
741 
742  if (Hdr.BucketCount > 0) {
743  for (uint32_t Bucket = 0; Bucket < Hdr.BucketCount; ++Bucket)
744  dumpBucket(W, Bucket);
745  return;
746  }
747 
748  W.startLine() << "Hash table not present\n";
749  for (NameTableEntry NTE : *this)
750  dumpName(W, NTE, None);
751 }
752 
754  uint32_t Offset = 0;
755  while (AccelSection.isValidOffset(Offset)) {
756  NameIndex Next(*this, Offset);
757  if (llvm::Error E = Next.extract())
758  return E;
759  Offset = Next.getNextUnitOffset();
760  NameIndices.push_back(std::move(Next));
761  }
762  return Error::success();
763 }
764 
767  return make_range(ValueIterator(*this, Key), ValueIterator());
768 }
769 
771  ScopedPrinter W(OS);
772  for (const NameIndex &NI : NameIndices)
773  NI.dump(W);
774 }
775 
777 DWARFDebugNames::ValueIterator::findEntryOffsetInCurrentIndex() {
778  const Header &Hdr = CurrentIndex->Hdr;
779  if (Hdr.BucketCount == 0) {
780  // No Hash Table, We need to search through all names in the Name Index.
781  for (NameTableEntry NTE : *CurrentIndex) {
782  if (NTE.getString() == Key)
783  return NTE.getEntryOffset();
784  }
785  return None;
786  }
787 
788  // The Name Index has a Hash Table, so use that to speed up the search.
789  // Compute the Key Hash, if it has not been done already.
790  if (!Hash)
791  Hash = caseFoldingDjbHash(Key);
792  uint32_t Bucket = *Hash % Hdr.BucketCount;
793  uint32_t Index = CurrentIndex->getBucketArrayEntry(Bucket);
794  if (Index == 0)
795  return None; // Empty bucket
796 
797  for (; Index <= Hdr.NameCount; ++Index) {
798  uint32_t Hash = CurrentIndex->getHashArrayEntry(Index);
799  if (Hash % Hdr.BucketCount != Bucket)
800  return None; // End of bucket
801 
802  NameTableEntry NTE = CurrentIndex->getNameTableEntry(Index);
803  if (NTE.getString() == Key)
804  return NTE.getEntryOffset();
805  }
806  return None;
807 }
808 
809 bool DWARFDebugNames::ValueIterator::getEntryAtCurrentOffset() {
810  auto EntryOr = CurrentIndex->getEntry(&DataOffset);
811  if (!EntryOr) {
812  consumeError(EntryOr.takeError());
813  return false;
814  }
815  CurrentEntry = std::move(*EntryOr);
816  return true;
817 }
818 
819 bool DWARFDebugNames::ValueIterator::findInCurrentIndex() {
820  Optional<uint32_t> Offset = findEntryOffsetInCurrentIndex();
821  if (!Offset)
822  return false;
823  DataOffset = *Offset;
824  return getEntryAtCurrentOffset();
825 }
826 
827 void DWARFDebugNames::ValueIterator::searchFromStartOfCurrentIndex() {
828  for (const NameIndex *End = CurrentIndex->Section.NameIndices.end();
829  CurrentIndex != End; ++CurrentIndex) {
830  if (findInCurrentIndex())
831  return;
832  }
833  setEnd();
834 }
835 
836 void DWARFDebugNames::ValueIterator::next() {
837  assert(CurrentIndex && "Incrementing an end() iterator?");
838 
839  // First try the next entry in the current Index.
840  if (getEntryAtCurrentOffset())
841  return;
842 
843  // If we're a local iterator or we have reached the last Index, we're done.
844  if (IsLocal || CurrentIndex == &CurrentIndex->Section.NameIndices.back()) {
845  setEnd();
846  return;
847  }
848 
849  // Otherwise, try the next index.
850  ++CurrentIndex;
851  searchFromStartOfCurrentIndex();
852 }
853 
855  StringRef Key)
856  : CurrentIndex(AccelTable.NameIndices.begin()), IsLocal(false), Key(Key) {
857  searchFromStartOfCurrentIndex();
858 }
859 
861  const DWARFDebugNames::NameIndex &NI, StringRef Key)
862  : CurrentIndex(&NI), IsLocal(true), Key(Key) {
863  if (!findInCurrentIndex())
864  setEnd();
865 }
866 
869  if (NameIndices.empty())
871  return make_range(ValueIterator(*this, Key), ValueIterator());
872 }
873 
876  if (CUToNameIndex.size() == 0 && NameIndices.size() > 0) {
877  for (const auto &NI : *this) {
878  for (uint32_t CU = 0; CU < NI.getCUCount(); ++CU)
879  CUToNameIndex.try_emplace(NI.getCUOffset(CU), &NI);
880  }
881  }
882  return CUToNameIndex.lookup(CUOffset);
883 }
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:495
uint32_t getEntryOffset() const
Returns the offset of the first Entry in the list.
void dump(ScopedPrinter &W) const
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:241
uint64_t getULEB128(uint32_t *offset_ptr) const
Extract a unsigned LEB128 value from *offset_ptr.
iterator_range< ValueIterator > equal_range(StringRef Key) const
Look up all entries in the accelerator table matching Key.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
StringRef AtomTypeString(unsigned Atom)
Definition: Dwarf.cpp:491
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:449
std::vector< AttributeEncoding > Attributes
List of index attributes.
void dump(ScopedPrinter &W) const
SmallVector< DWARFFormValue, 3 > Values
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()
This class holds an abstract representation of an Accelerator Table, consisting of a sequence of buck...
Definition: AccelTable.h:199
uint32_t getStringOffset() const
Returns the offset of the name of the described entities.
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition: Format.h:124
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:299
uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew=0)
Returns the next integer (mod 2**64) that is greater than or equal to Value and is a multiple of Alig...
Definition: MathExtras.h:685
std::error_code convertToErrorCode() const override
Convert this error to a std::error_code.
Optional< DWARFFormValue > lookup(HeaderData::AtomType Atom) const
Returns the value of the Atom in this Accelerator Entry, if the Entry contains such Atom...
uint16_t getU16(uint32_t *offset_ptr) const
Extract a uint16_t value from *offset_ptr.
bool isFormClass(FormClass FC) const
Base class for error info classes.
Definition: Error.h:47
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.
dwarf::Form getForm() const
const NameIndex * getCUNameIndex(uint32_t CUOffset)
Return the Name Index covering the compile unit at CUOffset, or nullptr if there is no Name Index cov...
uint32_t getU32(uint32_t *offset_ptr) const
Extract a uint32_t value from *offset_ptr.
Error extract(const DWARFDataExtractor &AS, uint32_t *Offset)
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
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:42
llvm::Error extract() override
Tagged union holding either a T or a Error.
Definition: CachePruning.h:23
Index attribute and its encoding.
static const uint16_t * lookup(unsigned opcode, unsigned domain, ArrayRef< uint16_t[3]> Table)
dwarf::Tag Tag
Dwarf Tag of the described entity.
Key
PAL metadata keys.
raw_ostream & getOStream()
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE bool empty() const
empty - Check if the string is empty.
Definition: StringRef.h:133
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
Represents a single accelerator table within the Dwarf 5 .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)
bool isValidOffsetForDataOfSize(uint32_t offset, uint32_t length) const
Test the availability of length bytes of data from offset.
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:75
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.
static const unsigned End
uint8_t getU8(uint32_t *offset_ptr) const
Extract a uint8_t value from *offset_ptr.
Optional< uint64_t > getAsUnsignedConstant() const
void printHex(StringRef Label, T Value)
Dwarf 5 Name Index header.
Expected< Entry > getEntry(uint32_t *Offset) const
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:555
const AMDGPUAS & AS
void consumeError(Error Err)
Consume a Error without doing anything.
Definition: Error.h:962
uint32_t djbHash(StringRef Buffer, uint32_t H=5381)
The Bernstein hash function used by the DWARF accelerator tables.
Definition: DJB.h:22
uint32_t getLocalTUOffset(uint32_t TU) const
Reads offset of local type unit TU, TU is 0-based.
uint64_t getRelocatedValue(uint32_t Size, uint32_t *Off, uint64_t *SectionIndex=nullptr) const
Extracts a value and applies a relocation to the result if one exists for the given offset...
static const char *const Magic
Definition: Archive.cpp:42
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:889
static ErrorSuccess success()
Create a success value.
Definition: Error.h:313
void printNumber(StringRef Label, uint64_t Value)
void dump(ScopedPrinter &W) const
A single entry in the Name Table (Dwarf 5 sect.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:861
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:385
uint32_t getIndex() const
Return the index of this name in the parent Name Index.
A range adaptor for a pair of iterators.
This file contains constants used for implementing Dwarf debug support.
std::pair< uint32_t, dwarf::Tag > readAtoms(uint32_t &HashDataOffset)
Return information related to the DWARF DIE we&#39;re looking for when performing a lookup by name...
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...
bool extractValue(const DWARFDataExtractor &Data, uint32_t *OffsetPtr, dwarf::FormParams FormParams, const DWARFContext *Context=nullptr, const DWARFUnit *Unit=nullptr)
Extracts a value in Data at offset *OffsetPtr.
Basic Alias true
Optional< uint64_t > getCUOffset() const override
Returns the Offset of the Compilation Unit associated with this Accelerator Entry or None if the Comp...
void dump(ScopedPrinter &W) const
const char * getCStr(uint32_t *offset_ptr) const
Extract a C string from *offset_ptr.
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2023
bool isValidOffset(uint32_t offset) const
Test the validity of offset.
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:156
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
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:49
Marker as the end of a list of atoms.
Definition: Dwarf.h:372
for(unsigned i=Desc.getNumOperands(), e=OldMI.getNumOperands();i !=e;++i)
uint32_t getCUOffset(uint32_t CU) const
Reads offset of compilation unit CU. CU is 0-based.
iterator_range< ValueIterator > equal_range(StringRef Key) const
Look up all entries in this Name Index matching Key.
Optional< uint64_t > getAsSectionOffset() const
const uint64_t Version
Definition: InstrProf.h:895
std::error_code inconvertibleErrorCode()
The value returned by this function can be returned from convertToErrorCode for Error values where no...
Definition: Error.cpp:73