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