LLVM  9.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  uint32_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<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  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  uint32_t Offset = sizeof(Hdr) + Hdr.HeaderDataLength;
227  unsigned HashesBase = Offset + Hdr.BucketCount * 4;
228  unsigned 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  unsigned HashOffset = HashesBase + HashIdx*4;
241  unsigned OffsetsOffset = OffsetsBase + HashIdx*4;
242  uint32_t Hash = AccelSection.getU32(&HashOffset);
243 
244  if (Hash % Hdr.BucketCount != Bucket)
245  break;
246 
247  unsigned 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(
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, unsigned 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  unsigned BucketBase = sizeof(Hdr) + Hdr.HeaderDataLength;
337  unsigned HashesBase = BucketBase + Hdr.BucketCount * 4;
338  unsigned OffsetsBase = HashesBase + Hdr.HashCount * 4;
339 
340  unsigned 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  unsigned HashOffset = HashesBase + HashIdx * 4;
346  unsigned 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  unsigned DataOffset = AccelSection.getU32(&OffsetsOffset);
354  unsigned 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  uint32_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(uint32_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(uint32_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(uint32_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  uint32_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  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 + 4 * (Hdr.CompUnitCount + TU);
589  return Section.AccelSection.getRelocatedValue(4, &Offset);
590 }
591 
593  assert(TU < Hdr.ForeignTypeUnitCount);
594  uint32_t Offset =
595  CUsBase + 4 * (Hdr.CompUnitCount + Hdr.LocalTypeUnitCount) + 8 * TU;
596  return Section.AccelSection.getU64(&Offset);
597 }
598 
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  uint32_t StringOffsetOffset = StringOffsetsBase + 4 * (Index - 1);
629  uint32_t EntryOffsetOffset = EntryOffsetsBase + 4 * (Index - 1);
630  const DWARFDataExtractor &AS = Section.AccelSection;
631 
632  uint32_t StringOffset = AS.getRelocatedValue(4, &StringOffsetOffset);
633  uint32_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  uint32_t BucketOffset = BucketsBase + 4 * Bucket;
642  return Section.AccelSection.getU32(&BucketOffset);
643 }
644 
646  assert(0 < Index && Index <= Hdr.NameCount);
647  uint32_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  uint32_t *Offset) const {
657  uint32_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%08x", NTE.getStringOffset());
678  W.getOStream() << " \"" << NTE.getString() << "\"\n";
679 
680  uint32_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%08x\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%08x\n", TU, getLocalTUOffset(TU));
698 }
699 
700 void DWARFDebugNames::NameIndex::dumpForeignTUs(ScopedPrinter &W) const {
701  if (Hdr.ForeignTypeUnitCount == 0)
702  return;
703 
704  ListScope TUScope(W, "Foreign Type Unit signatures");
705  for (uint32_t TU = 0; TU < Hdr.ForeignTypeUnitCount; ++TU) {
706  W.startLine() << format("ForeignTU[%u]: 0x%016" PRIx64 "\n", TU,
707  getForeignTUSignature(TU));
708  }
709 }
710 
711 void DWARFDebugNames::NameIndex::dumpAbbreviations(ScopedPrinter &W) const {
712  ListScope AbbrevsScope(W, "Abbreviations");
713  for (const auto &Abbr : Abbrevs)
714  Abbr.dump(W);
715 }
716 
717 void DWARFDebugNames::NameIndex::dumpBucket(ScopedPrinter &W,
718  uint32_t Bucket) const {
719  ListScope BucketScope(W, ("Bucket " + Twine(Bucket)).str());
720  uint32_t Index = getBucketArrayEntry(Bucket);
721  if (Index == 0) {
722  W.printString("EMPTY");
723  return;
724  }
725  if (Index > Hdr.NameCount) {
726  W.printString("Name index is invalid");
727  return;
728  }
729 
730  for (; Index <= Hdr.NameCount; ++Index) {
731  uint32_t Hash = getHashArrayEntry(Index);
732  if (Hash % Hdr.BucketCount != Bucket)
733  break;
734 
735  dumpName(W, getNameTableEntry(Index), Hash);
736  }
737 }
738 
740  DictScope UnitScope(W, ("Name Index @ 0x" + Twine::utohexstr(Base)).str());
741  Hdr.dump(W);
742  dumpCUs(W);
743  dumpLocalTUs(W);
744  dumpForeignTUs(W);
745  dumpAbbreviations(W);
746 
747  if (Hdr.BucketCount > 0) {
748  for (uint32_t Bucket = 0; Bucket < Hdr.BucketCount; ++Bucket)
749  dumpBucket(W, Bucket);
750  return;
751  }
752 
753  W.startLine() << "Hash table not present\n";
754  for (NameTableEntry NTE : *this)
755  dumpName(W, NTE, None);
756 }
757 
759  uint32_t Offset = 0;
760  while (AccelSection.isValidOffset(Offset)) {
761  NameIndex Next(*this, Offset);
762  if (Error E = Next.extract())
763  return E;
764  Offset = Next.getNextUnitOffset();
765  NameIndices.push_back(std::move(Next));
766  }
767  return Error::success();
768 }
769 
772  return make_range(ValueIterator(*this, Key), ValueIterator());
773 }
774 
776  ScopedPrinter W(OS);
777  for (const NameIndex &NI : NameIndices)
778  NI.dump(W);
779 }
780 
782 DWARFDebugNames::ValueIterator::findEntryOffsetInCurrentIndex() {
783  const Header &Hdr = CurrentIndex->Hdr;
784  if (Hdr.BucketCount == 0) {
785  // No Hash Table, We need to search through all names in the Name Index.
786  for (NameTableEntry NTE : *CurrentIndex) {
787  if (NTE.getString() == Key)
788  return NTE.getEntryOffset();
789  }
790  return None;
791  }
792 
793  // The Name Index has a Hash Table, so use that to speed up the search.
794  // Compute the Key Hash, if it has not been done already.
795  if (!Hash)
796  Hash = caseFoldingDjbHash(Key);
797  uint32_t Bucket = *Hash % Hdr.BucketCount;
798  uint32_t Index = CurrentIndex->getBucketArrayEntry(Bucket);
799  if (Index == 0)
800  return None; // Empty bucket
801 
802  for (; Index <= Hdr.NameCount; ++Index) {
803  uint32_t Hash = CurrentIndex->getHashArrayEntry(Index);
804  if (Hash % Hdr.BucketCount != Bucket)
805  return None; // End of bucket
806 
807  NameTableEntry NTE = CurrentIndex->getNameTableEntry(Index);
808  if (NTE.getString() == Key)
809  return NTE.getEntryOffset();
810  }
811  return None;
812 }
813 
814 bool DWARFDebugNames::ValueIterator::getEntryAtCurrentOffset() {
815  auto EntryOr = CurrentIndex->getEntry(&DataOffset);
816  if (!EntryOr) {
817  consumeError(EntryOr.takeError());
818  return false;
819  }
820  CurrentEntry = std::move(*EntryOr);
821  return true;
822 }
823 
824 bool DWARFDebugNames::ValueIterator::findInCurrentIndex() {
825  Optional<uint32_t> Offset = findEntryOffsetInCurrentIndex();
826  if (!Offset)
827  return false;
828  DataOffset = *Offset;
829  return getEntryAtCurrentOffset();
830 }
831 
832 void DWARFDebugNames::ValueIterator::searchFromStartOfCurrentIndex() {
833  for (const NameIndex *End = CurrentIndex->Section.NameIndices.end();
834  CurrentIndex != End; ++CurrentIndex) {
835  if (findInCurrentIndex())
836  return;
837  }
838  setEnd();
839 }
840 
841 void DWARFDebugNames::ValueIterator::next() {
842  assert(CurrentIndex && "Incrementing an end() iterator?");
843 
844  // First try the next entry in the current Index.
845  if (getEntryAtCurrentOffset())
846  return;
847 
848  // If we're a local iterator or we have reached the last Index, we're done.
849  if (IsLocal || CurrentIndex == &CurrentIndex->Section.NameIndices.back()) {
850  setEnd();
851  return;
852  }
853 
854  // Otherwise, try the next index.
855  ++CurrentIndex;
856  searchFromStartOfCurrentIndex();
857 }
858 
860  StringRef Key)
861  : CurrentIndex(AccelTable.NameIndices.begin()), IsLocal(false), Key(Key) {
862  searchFromStartOfCurrentIndex();
863 }
864 
866  const DWARFDebugNames::NameIndex &NI, StringRef Key)
867  : CurrentIndex(&NI), IsLocal(true), Key(Key) {
868  if (!findInCurrentIndex())
869  setEnd();
870 }
871 
874  if (NameIndices.empty())
876  return make_range(ValueIterator(*this, Key), ValueIterator());
877 }
878 
881  if (CUToNameIndex.size() == 0 && NameIndices.size() > 0) {
882  for (const auto &NI : *this) {
883  for (uint32_t CU = 0; CU < NI.getCUCount(); ++CU)
884  CUToNameIndex.try_emplace(NI.getCUOffset(CU), &NI);
885  }
886  }
887  return CUToNameIndex.lookup(CUOffset);
888 }
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:499
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:224
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.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
StringRef AtomTypeString(unsigned Atom)
Definition: Dwarf.cpp:523
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:473
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:198
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:123
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:298
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:684
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: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.
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.
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: CachePruning.h:22
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()
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)
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 v5 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:669
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
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: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)
Error extract(const DWARFDataExtractor &AS, uint32_t *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:841
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.
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:606
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:2038
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:72
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:374
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: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