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 DWARFDebugNames::Entry::Entry(const NameIndex &NameIdx, const Abbrev &Abbr)
522  : NameIdx(&NameIdx), Abbr(&Abbr) {
523  // This merely creates form values. It is up to the caller
524  // (NameIndex::getEntry) to populate them.
525  Values.reserve(Abbr.Attributes.size());
526  for (const auto &Attr : Abbr.Attributes)
527  Values.emplace_back(Attr.Form);
528 }
529 
532  assert(Abbr->Attributes.size() == Values.size());
533  for (const auto &Tuple : zip_first(Abbr->Attributes, Values)) {
534  if (std::get<0>(Tuple).Index == Index)
535  return std::get<1>(Tuple);
536  }
537  return None;
538 }
539 
541  if (Optional<DWARFFormValue> Off = lookup(dwarf::DW_IDX_die_offset))
542  return Off->getAsReferenceUVal();
543  return None;
544 }
545 
547  if (Optional<DWARFFormValue> Off = lookup(dwarf::DW_IDX_compile_unit))
548  return Off->getAsUnsignedConstant();
549  // In a per-CU index, the entries without a DW_IDX_compile_unit attribute
550  // implicitly refer to the single CU.
551  if (NameIdx->getCUCount() == 1)
552  return 0;
553  return None;
554 }
555 
557  Optional<uint64_t> Index = getCUIndex();
558  if (!Index || *Index >= NameIdx->getCUCount())
559  return None;
560  return NameIdx->getCUOffset(*Index);
561 }
562 
564  W.printHex("Abbrev", Abbr->Code);
565  W.startLine() << formatv("Tag: {0}\n", Abbr->Tag);
566  assert(Abbr->Attributes.size() == Values.size());
567  for (const auto &Tuple : zip_first(Abbr->Attributes, Values)) {
568  W.startLine() << formatv("{0}: ", std::get<0>(Tuple).Index);
569  std::get<1>(Tuple).dump(W.getOStream());
570  W.getOStream() << '\n';
571  }
572 }
573 
576  return inconvertibleErrorCode();
577 }
578 
580  assert(CU < Hdr.CompUnitCount);
581  uint32_t Offset = CUsBase + 4 * CU;
582  return Section.AccelSection.getRelocatedValue(4, &Offset);
583 }
584 
586  assert(TU < Hdr.LocalTypeUnitCount);
587  uint32_t Offset = CUsBase + Hdr.CompUnitCount * 4;
588  return Section.AccelSection.getRelocatedValue(4, &Offset);
589 }
590 
592  assert(TU < Hdr.ForeignTypeUnitCount);
593  uint32_t Offset = CUsBase + (Hdr.CompUnitCount + Hdr.LocalTypeUnitCount) * 4;
594  return Section.AccelSection.getU64(&Offset);
595 }
596 
599  const DWARFDataExtractor &AS = Section.AccelSection;
600  if (!AS.isValidOffset(*Offset))
602  "Incorrectly terminated entry list.");
603 
604  uint32_t AbbrevCode = AS.getULEB128(Offset);
605  if (AbbrevCode == 0)
606  return make_error<SentinelError>();
607 
608  const auto AbbrevIt = Abbrevs.find_as(AbbrevCode);
609  if (AbbrevIt == Abbrevs.end())
610  return createStringError(errc::invalid_argument, "Invalid abbreviation.");
611 
612  Entry E(*this, *AbbrevIt);
613 
615  for (auto &Value : E.Values) {
616  if (!Value.extractValue(AS, Offset, FormParams))
618  "Error extracting index attribute values.");
619  }
620  return std::move(E);
621 }
622 
625  assert(0 < Index && Index <= Hdr.NameCount);
626  uint32_t StringOffsetOffset = StringOffsetsBase + 4 * (Index - 1);
627  uint32_t EntryOffsetOffset = EntryOffsetsBase + 4 * (Index - 1);
628  const DWARFDataExtractor &AS = Section.AccelSection;
629 
630  uint32_t StringOffset = AS.getRelocatedValue(4, &StringOffsetOffset);
631  uint32_t EntryOffset = AS.getU32(&EntryOffsetOffset);
632  EntryOffset += EntriesBase;
633  return {Section.StringSection, Index, StringOffset, EntryOffset};
634 }
635 
636 uint32_t
638  assert(Bucket < Hdr.BucketCount);
639  uint32_t BucketOffset = BucketsBase + 4 * Bucket;
640  return Section.AccelSection.getU32(&BucketOffset);
641 }
642 
644  assert(0 < Index && Index <= Hdr.NameCount);
645  uint32_t HashOffset = HashesBase + 4 * (Index - 1);
646  return Section.AccelSection.getU32(&HashOffset);
647 }
648 
649 // Returns true if we should continue scanning for entries, false if this is the
650 // last (sentinel) entry). In case of a parsing error we also return false, as
651 // it's not possible to recover this entry list (but the other lists may still
652 // parse OK).
653 bool DWARFDebugNames::NameIndex::dumpEntry(ScopedPrinter &W,
654  uint32_t *Offset) const {
655  uint32_t EntryId = *Offset;
656  auto EntryOr = getEntry(Offset);
657  if (!EntryOr) {
658  handleAllErrors(EntryOr.takeError(), [](const SentinelError &) {},
659  [&W](const ErrorInfoBase &EI) { EI.log(W.startLine()); });
660  return false;
661  }
662 
663  DictScope EntryScope(W, ("Entry @ 0x" + Twine::utohexstr(EntryId)).str());
664  EntryOr->dump(W);
665  return true;
666 }
667 
668 void DWARFDebugNames::NameIndex::dumpName(ScopedPrinter &W,
669  const NameTableEntry &NTE,
670  Optional<uint32_t> Hash) const {
671  DictScope NameScope(W, ("Name " + Twine(NTE.getIndex())).str());
672  if (Hash)
673  W.printHex("Hash", *Hash);
674 
675  W.startLine() << format("String: 0x%08x", NTE.getStringOffset());
676  W.getOStream() << " \"" << NTE.getString() << "\"\n";
677 
678  uint32_t EntryOffset = NTE.getEntryOffset();
679  while (dumpEntry(W, &EntryOffset))
680  /*empty*/;
681 }
682 
683 void DWARFDebugNames::NameIndex::dumpCUs(ScopedPrinter &W) const {
684  ListScope CUScope(W, "Compilation Unit offsets");
685  for (uint32_t CU = 0; CU < Hdr.CompUnitCount; ++CU)
686  W.startLine() << format("CU[%u]: 0x%08x\n", CU, getCUOffset(CU));
687 }
688 
689 void DWARFDebugNames::NameIndex::dumpLocalTUs(ScopedPrinter &W) const {
690  if (Hdr.LocalTypeUnitCount == 0)
691  return;
692 
693  ListScope TUScope(W, "Local Type Unit offsets");
694  for (uint32_t TU = 0; TU < Hdr.LocalTypeUnitCount; ++TU)
695  W.startLine() << format("LocalTU[%u]: 0x%08x\n", TU, getLocalTUOffset(TU));
696 }
697 
698 void DWARFDebugNames::NameIndex::dumpForeignTUs(ScopedPrinter &W) const {
699  if (Hdr.ForeignTypeUnitCount == 0)
700  return;
701 
702  ListScope TUScope(W, "Foreign Type Unit signatures");
703  for (uint32_t TU = 0; TU < Hdr.ForeignTypeUnitCount; ++TU) {
704  W.startLine() << format("ForeignTU[%u]: 0x%016" PRIx64 "\n", TU,
705  getForeignTUSignature(TU));
706  }
707 }
708 
709 void DWARFDebugNames::NameIndex::dumpAbbreviations(ScopedPrinter &W) const {
710  ListScope AbbrevsScope(W, "Abbreviations");
711  for (const auto &Abbr : Abbrevs)
712  Abbr.dump(W);
713 }
714 
715 void DWARFDebugNames::NameIndex::dumpBucket(ScopedPrinter &W,
716  uint32_t Bucket) const {
717  ListScope BucketScope(W, ("Bucket " + Twine(Bucket)).str());
718  uint32_t Index = getBucketArrayEntry(Bucket);
719  if (Index == 0) {
720  W.printString("EMPTY");
721  return;
722  }
723  if (Index > Hdr.NameCount) {
724  W.printString("Name index is invalid");
725  return;
726  }
727 
728  for (; Index <= Hdr.NameCount; ++Index) {
729  uint32_t Hash = getHashArrayEntry(Index);
730  if (Hash % Hdr.BucketCount != Bucket)
731  break;
732 
733  dumpName(W, getNameTableEntry(Index), Hash);
734  }
735 }
736 
738  DictScope UnitScope(W, ("Name Index @ 0x" + Twine::utohexstr(Base)).str());
739  Hdr.dump(W);
740  dumpCUs(W);
741  dumpLocalTUs(W);
742  dumpForeignTUs(W);
743  dumpAbbreviations(W);
744 
745  if (Hdr.BucketCount > 0) {
746  for (uint32_t Bucket = 0; Bucket < Hdr.BucketCount; ++Bucket)
747  dumpBucket(W, Bucket);
748  return;
749  }
750 
751  W.startLine() << "Hash table not present\n";
752  for (NameTableEntry NTE : *this)
753  dumpName(W, NTE, None);
754 }
755 
757  uint32_t Offset = 0;
758  while (AccelSection.isValidOffset(Offset)) {
759  NameIndex Next(*this, Offset);
760  if (llvm::Error E = Next.extract())
761  return E;
762  Offset = Next.getNextUnitOffset();
763  NameIndices.push_back(std::move(Next));
764  }
765  return Error::success();
766 }
767 
770  return make_range(ValueIterator(*this, Key), ValueIterator());
771 }
772 
774  ScopedPrinter W(OS);
775  for (const NameIndex &NI : NameIndices)
776  NI.dump(W);
777 }
778 
780 DWARFDebugNames::ValueIterator::findEntryOffsetInCurrentIndex() {
781  const Header &Hdr = CurrentIndex->Hdr;
782  if (Hdr.BucketCount == 0) {
783  // No Hash Table, We need to search through all names in the Name Index.
784  for (NameTableEntry NTE : *CurrentIndex) {
785  if (NTE.getString() == Key)
786  return NTE.getEntryOffset();
787  }
788  return None;
789  }
790 
791  // The Name Index has a Hash Table, so use that to speed up the search.
792  // Compute the Key Hash, if it has not been done already.
793  if (!Hash)
794  Hash = caseFoldingDjbHash(Key);
795  uint32_t Bucket = *Hash % Hdr.BucketCount;
796  uint32_t Index = CurrentIndex->getBucketArrayEntry(Bucket);
797  if (Index == 0)
798  return None; // Empty bucket
799 
800  for (; Index <= Hdr.NameCount; ++Index) {
801  uint32_t Hash = CurrentIndex->getHashArrayEntry(Index);
802  if (Hash % Hdr.BucketCount != Bucket)
803  return None; // End of bucket
804 
805  NameTableEntry NTE = CurrentIndex->getNameTableEntry(Index);
806  if (NTE.getString() == Key)
807  return NTE.getEntryOffset();
808  }
809  return None;
810 }
811 
812 bool DWARFDebugNames::ValueIterator::getEntryAtCurrentOffset() {
813  auto EntryOr = CurrentIndex->getEntry(&DataOffset);
814  if (!EntryOr) {
815  consumeError(EntryOr.takeError());
816  return false;
817  }
818  CurrentEntry = std::move(*EntryOr);
819  return true;
820 }
821 
822 bool DWARFDebugNames::ValueIterator::findInCurrentIndex() {
823  Optional<uint32_t> Offset = findEntryOffsetInCurrentIndex();
824  if (!Offset)
825  return false;
826  DataOffset = *Offset;
827  return getEntryAtCurrentOffset();
828 }
829 
830 void DWARFDebugNames::ValueIterator::searchFromStartOfCurrentIndex() {
831  for (const NameIndex *End = CurrentIndex->Section.NameIndices.end();
832  CurrentIndex != End; ++CurrentIndex) {
833  if (findInCurrentIndex())
834  return;
835  }
836  setEnd();
837 }
838 
839 void DWARFDebugNames::ValueIterator::next() {
840  assert(CurrentIndex && "Incrementing an end() iterator?");
841 
842  // First try the next entry in the current Index.
843  if (getEntryAtCurrentOffset())
844  return;
845 
846  // If we're a local iterator or we have reached the last Index, we're done.
847  if (IsLocal || CurrentIndex == &CurrentIndex->Section.NameIndices.back()) {
848  setEnd();
849  return;
850  }
851 
852  // Otherwise, try the next index.
853  ++CurrentIndex;
854  searchFromStartOfCurrentIndex();
855 }
856 
858  StringRef Key)
859  : CurrentIndex(AccelTable.NameIndices.begin()), IsLocal(false), Key(Key) {
860  searchFromStartOfCurrentIndex();
861 }
862 
864  const DWARFDebugNames::NameIndex &NI, StringRef Key)
865  : CurrentIndex(&NI), IsLocal(true), Key(Key) {
866  if (!findInCurrentIndex())
867  setEnd();
868 }
869 
872  if (NameIndices.empty())
874  return make_range(ValueIterator(*this, Key), ValueIterator());
875 }
876 
879  if (CUToNameIndex.size() == 0 && NameIndices.size() > 0) {
880  for (const auto &NI : *this) {
881  for (uint32_t CU = 0; CU < NI.getCUCount(); ++CU)
882  CUToNameIndex.try_emplace(NI.getCUOffset(CU), &NI);
883  }
884  }
885  return CUToNameIndex.lookup(CUOffset);
886 }
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:498
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:520
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:464
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.
Error extract(const DWARFDataExtractor &AS, uint32_t *Offset)
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
llvm::Error extract() override
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 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: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)
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: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:70
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:603
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:373
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:904
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