• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
10 #include "llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h"
11 
12 #include "llvm/ADT/SmallVector.h"
13 #include "llvm/BinaryFormat/Dwarf.h"
14 #include "llvm/DebugInfo/DWARF/DWARFRelocMap.h"
15 #include "llvm/Support/Compiler.h"
16 #include "llvm/Support/DJB.h"
17 #include "llvm/Support/Format.h"
18 #include "llvm/Support/FormatVariadic.h"
19 #include "llvm/Support/ScopedPrinter.h"
20 #include "llvm/Support/raw_ostream.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 
operator <<(raw_ostream & OS,const Atom & A)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 
formatAtom(unsigned Atom)40 static Atom formatAtom(unsigned Atom) { return {Atom}; }
41 
42 DWARFAcceleratorTable::~DWARFAcceleratorTable() = default;
43 
extract()44 llvm::Error AppleAcceleratorTable::extract() {
45   uint32_t Offset = 0;
46 
47   // Check that we can at least read the header.
48   if (!AccelSection.isValidOffset(offsetof(Header, HeaderDataLength)+4))
49     return make_error<StringError>("Section too small: cannot read header.",
50                                    inconvertibleErrorCode());
51 
52   Hdr.Magic = AccelSection.getU32(&Offset);
53   Hdr.Version = AccelSection.getU16(&Offset);
54   Hdr.HashFunction = AccelSection.getU16(&Offset);
55   Hdr.BucketCount = AccelSection.getU32(&Offset);
56   Hdr.HashCount = AccelSection.getU32(&Offset);
57   Hdr.HeaderDataLength = AccelSection.getU32(&Offset);
58 
59   // Check that we can read all the hashes and offsets from the
60   // section (see SourceLevelDebugging.rst for the structure of the index).
61   // We need to substract one because we're checking for an *offset* which is
62   // equal to the size for an empty table and hence pointer after the section.
63   if (!AccelSection.isValidOffset(sizeof(Hdr) + Hdr.HeaderDataLength +
64                                   Hdr.BucketCount * 4 + Hdr.HashCount * 8 - 1))
65     return make_error<StringError>(
66         "Section too small: cannot read buckets and hashes.",
67         inconvertibleErrorCode());
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 
getNumBuckets()82 uint32_t AppleAcceleratorTable::getNumBuckets() { return Hdr.BucketCount; }
getNumHashes()83 uint32_t AppleAcceleratorTable::getNumHashes() { return Hdr.HashCount; }
getSizeHdr()84 uint32_t AppleAcceleratorTable::getSizeHdr() { return sizeof(Hdr); }
getHeaderDataLength()85 uint32_t AppleAcceleratorTable::getHeaderDataLength() {
86   return Hdr.HeaderDataLength;
87 }
88 
89 ArrayRef<std::pair<AppleAcceleratorTable::HeaderData::AtomType,
90                    AppleAcceleratorTable::HeaderData::Form>>
getAtomsDesc()91 AppleAcceleratorTable::getAtomsDesc() {
92   return HdrData.Atoms;
93 }
94 
validateForms()95 bool AppleAcceleratorTable::validateForms() {
96   for (auto Atom : getAtomsDesc()) {
97     DWARFFormValue FormValue(Atom.second);
98     switch (Atom.first) {
99     case dwarf::DW_ATOM_die_offset:
100     case dwarf::DW_ATOM_die_tag:
101     case dwarf::DW_ATOM_type_flags:
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>
readAtoms(uint32_t & HashDataOffset)115 AppleAcceleratorTable::readAtoms(uint32_t &HashDataOffset) {
116   uint32_t DieOffset = dwarf::DW_INVALID_OFFSET;
117   dwarf::Tag DieTag = dwarf::DW_TAG_null;
118   dwarf::FormParams FormParams = {Hdr.Version, 0, dwarf::DwarfFormat::DWARF32};
119 
120   for (auto Atom : getAtomsDesc()) {
121     DWARFFormValue FormValue(Atom.second);
122     FormValue.extractValue(AccelSection, &HashDataOffset, FormParams);
123     switch (Atom.first) {
124     case dwarf::DW_ATOM_die_offset:
125       DieOffset = *FormValue.getAsUnsignedConstant();
126       break;
127     case dwarf::DW_ATOM_die_tag:
128       DieTag = (dwarf::Tag)*FormValue.getAsUnsignedConstant();
129       break;
130     default:
131       break;
132     }
133   }
134   return {DieOffset, DieTag};
135 }
136 
dump(ScopedPrinter & W) const137 void AppleAcceleratorTable::Header::dump(ScopedPrinter &W) const {
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 
extractOffset(Optional<DWARFFormValue> Value) const147 Optional<uint64_t> AppleAcceleratorTable::HeaderData::extractOffset(
148     Optional<DWARFFormValue> Value) const {
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 
dumpName(ScopedPrinter & W,SmallVectorImpl<DWARFFormValue> & AtomForms,uint32_t * DataOffset) const164 bool AppleAcceleratorTable::dumpName(ScopedPrinter &W,
165                                      SmallVectorImpl<DWARFFormValue> &AtomForms,
166                                      uint32_t *DataOffset) const {
167   dwarf::FormParams FormParams = {Hdr.Version, 0, dwarf::DwarfFormat::DWARF32};
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 
dump(raw_ostream & OS) const203 LLVM_DUMP_METHOD void AppleAcceleratorTable::dump(raw_ostream &OS) const {
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()));
213   SmallVector<DWARFFormValue, 3> AtomForms;
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 
Entry(const AppleAcceleratorTable::HeaderData & HdrData)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 
extract(const AppleAcceleratorTable & AccelTable,uint32_t * Offset)267 void AppleAcceleratorTable::Entry::extract(
268     const AppleAcceleratorTable &AccelTable, uint32_t *Offset) {
269 
270   dwarf::FormParams FormParams = {AccelTable.Hdr.Version, 0,
271                                   dwarf::DwarfFormat::DWARF32};
272   for (auto &Atom : Values)
273     Atom.extractValue(AccelTable.AccelSection, Offset, FormParams);
274 }
275 
276 Optional<DWARFFormValue>
lookup(HeaderData::AtomType Atom) const277 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 
getDIESectionOffset() const287 Optional<uint64_t> AppleAcceleratorTable::Entry::getDIESectionOffset() const {
288   return HdrData->extractOffset(lookup(dwarf::DW_ATOM_die_offset));
289 }
290 
getCUOffset() const291 Optional<uint64_t> AppleAcceleratorTable::Entry::getCUOffset() const {
292   return HdrData->extractOffset(lookup(dwarf::DW_ATOM_cu_offset));
293 }
294 
getTag() const295 Optional<dwarf::Tag> AppleAcceleratorTable::Entry::getTag() const {
296   Optional<DWARFFormValue> Tag = lookup(dwarf::DW_ATOM_die_tag);
297   if (!Tag)
298     return None;
299   if (Optional<uint64_t> Value = Tag->getAsUnsignedConstant())
300     return dwarf::Tag(*Value);
301   return None;
302 }
303 
ValueIterator(const AppleAcceleratorTable & AccelTable,unsigned Offset)304 AppleAcceleratorTable::ValueIterator::ValueIterator(
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 
Next()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 
328 iterator_range<AppleAcceleratorTable::ValueIterator>
equal_range(StringRef Key) const329 AppleAcceleratorTable::equal_range(StringRef Key) const {
330   if (!IsValid)
331     return make_range(ValueIterator(), ValueIterator());
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   }
362   return make_range(ValueIterator(), ValueIterator());
363 }
364 
dump(ScopedPrinter & W) const365 void DWARFDebugNames::Header::dump(ScopedPrinter &W) const {
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 
extract(const DWARFDataExtractor & AS,uint32_t * Offset)379 llvm::Error DWARFDebugNames::Header::extract(const DWARFDataExtractor &AS,
380                                              uint32_t *Offset) {
381   // Check that we can read the fixed-size part.
382   if (!AS.isValidOffset(*Offset + sizeof(HeaderPOD) - 1))
383     return make_error<StringError>("Section too small: cannot read header.",
384                                    inconvertibleErrorCode());
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 make_error<StringError>(
399         "Section too small: cannot read header augmentation.",
400         inconvertibleErrorCode());
401   AugmentationString.resize(AugmentationStringSize);
402   AS.getU8(Offset, reinterpret_cast<uint8_t *>(AugmentationString.data()),
403            AugmentationStringSize);
404   return Error::success();
405 }
406 
dump(ScopedPrinter & W) const407 void DWARFDebugNames::Abbrev::dump(ScopedPrinter &W) const {
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 
sentinelAttrEnc()415 static constexpr DWARFDebugNames::AttributeEncoding sentinelAttrEnc() {
416   return {dwarf::Index(0), dwarf::Form(0)};
417 }
418 
isSentinel(const DWARFDebugNames::AttributeEncoding & AE)419 static bool isSentinel(const DWARFDebugNames::AttributeEncoding &AE) {
420   return AE == sentinelAttrEnc();
421 }
422 
sentinelAbbrev()423 static DWARFDebugNames::Abbrev sentinelAbbrev() {
424   return DWARFDebugNames::Abbrev(0, dwarf::Tag(0), {});
425 }
426 
isSentinel(const DWARFDebugNames::Abbrev & Abbr)427 static bool isSentinel(const DWARFDebugNames::Abbrev &Abbr) {
428   return Abbr.Code == 0;
429 }
430 
getEmptyKey()431 DWARFDebugNames::Abbrev DWARFDebugNames::AbbrevMapInfo::getEmptyKey() {
432   return sentinelAbbrev();
433 }
434 
getTombstoneKey()435 DWARFDebugNames::Abbrev DWARFDebugNames::AbbrevMapInfo::getTombstoneKey() {
436   return DWARFDebugNames::Abbrev(~0, dwarf::Tag(0), {});
437 }
438 
439 Expected<DWARFDebugNames::AttributeEncoding>
extractAttributeEncoding(uint32_t * Offset)440 DWARFDebugNames::NameIndex::extractAttributeEncoding(uint32_t *Offset) {
441   if (*Offset >= EntriesBase) {
442     return make_error<StringError>("Incorrectly terminated abbreviation table.",
443                                    inconvertibleErrorCode());
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 
451 Expected<std::vector<DWARFDebugNames::AttributeEncoding>>
extractAttributeEncodings(uint32_t * Offset)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 
465 Expected<DWARFDebugNames::Abbrev>
extractAbbrev(uint32_t * Offset)466 DWARFDebugNames::NameIndex::extractAbbrev(uint32_t *Offset) {
467   if (*Offset >= EntriesBase) {
468     return make_error<StringError>("Incorrectly terminated abbreviation table.",
469                                    inconvertibleErrorCode());
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 
extract()483 Error DWARFDebugNames::NameIndex::extract() {
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))
504     return make_error<StringError>(
505         "Section too small: cannot read abbreviations.",
506         inconvertibleErrorCode());
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) {
518       return make_error<StringError>("Duplicate abbreviation code.",
519                                      inconvertibleErrorCode());
520     }
521   }
522 }
Entry(const NameIndex & NameIdx,const Abbrev & Abbr)523 DWARFDebugNames::Entry::Entry(const NameIndex &NameIdx, const Abbrev &Abbr)
524     : NameIdx(&NameIdx), Abbr(&Abbr) {
525   // This merely creates form values. It is up to the caller
526   // (NameIndex::getEntry) to populate them.
527   Values.reserve(Abbr.Attributes.size());
528   for (const auto &Attr : Abbr.Attributes)
529     Values.emplace_back(Attr.Form);
530 }
531 
532 Optional<DWARFFormValue>
lookup(dwarf::Index Index) const533 DWARFDebugNames::Entry::lookup(dwarf::Index Index) const {
534   assert(Abbr->Attributes.size() == Values.size());
535   for (const auto &Tuple : zip_first(Abbr->Attributes, Values)) {
536     if (std::get<0>(Tuple).Index == Index)
537       return std::get<1>(Tuple);
538   }
539   return None;
540 }
541 
getDIEUnitOffset() const542 Optional<uint64_t> DWARFDebugNames::Entry::getDIEUnitOffset() const {
543   if (Optional<DWARFFormValue> Off = lookup(dwarf::DW_IDX_die_offset))
544     return Off->getAsReferenceUVal();
545   return None;
546 }
547 
getCUIndex() const548 Optional<uint64_t> DWARFDebugNames::Entry::getCUIndex() const {
549   if (Optional<DWARFFormValue> Off = lookup(dwarf::DW_IDX_compile_unit))
550     return Off->getAsUnsignedConstant();
551   // In a per-CU index, the entries without a DW_IDX_compile_unit attribute
552   // implicitly refer to the single CU.
553   if (NameIdx->getCUCount() == 1)
554     return 0;
555   return None;
556 }
557 
getCUOffset() const558 Optional<uint64_t> DWARFDebugNames::Entry::getCUOffset() const {
559   Optional<uint64_t> Index = getCUIndex();
560   if (!Index || *Index >= NameIdx->getCUCount())
561     return None;
562   return NameIdx->getCUOffset(*Index);
563 }
564 
dump(ScopedPrinter & W) const565 void DWARFDebugNames::Entry::dump(ScopedPrinter &W) const {
566   W.printHex("Abbrev", Abbr->Code);
567   W.startLine() << formatv("Tag: {0}\n", Abbr->Tag);
568   assert(Abbr->Attributes.size() == Values.size());
569   for (const auto &Tuple : zip_first(Abbr->Attributes, Values)) {
570     W.startLine() << formatv("{0}: ", std::get<0>(Tuple).Index);
571     std::get<1>(Tuple).dump(W.getOStream());
572     W.getOStream() << '\n';
573   }
574 }
575 
576 char DWARFDebugNames::SentinelError::ID;
convertToErrorCode() const577 std::error_code DWARFDebugNames::SentinelError::convertToErrorCode() const {
578   return inconvertibleErrorCode();
579 }
580 
getCUOffset(uint32_t CU) const581 uint32_t DWARFDebugNames::NameIndex::getCUOffset(uint32_t CU) const {
582   assert(CU < Hdr.CompUnitCount);
583   uint32_t Offset = CUsBase + 4 * CU;
584   return Section.AccelSection.getRelocatedValue(4, &Offset);
585 }
586 
getLocalTUOffset(uint32_t TU) const587 uint32_t DWARFDebugNames::NameIndex::getLocalTUOffset(uint32_t TU) const {
588   assert(TU < Hdr.LocalTypeUnitCount);
589   uint32_t Offset = CUsBase + Hdr.CompUnitCount * 4;
590   return Section.AccelSection.getRelocatedValue(4, &Offset);
591 }
592 
getForeignTUSignature(uint32_t TU) const593 uint64_t DWARFDebugNames::NameIndex::getForeignTUSignature(uint32_t TU) const {
594   assert(TU < Hdr.ForeignTypeUnitCount);
595   uint32_t Offset = CUsBase + (Hdr.CompUnitCount + Hdr.LocalTypeUnitCount) * 4;
596   return Section.AccelSection.getU64(&Offset);
597 }
598 
599 Expected<DWARFDebugNames::Entry>
getEntry(uint32_t * Offset) const600 DWARFDebugNames::NameIndex::getEntry(uint32_t *Offset) const {
601   const DWARFDataExtractor &AS = Section.AccelSection;
602   if (!AS.isValidOffset(*Offset))
603     return make_error<StringError>("Incorrectly terminated entry list.",
604                                    inconvertibleErrorCode());
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 make_error<StringError>("Invalid abbreviation.",
613                                    inconvertibleErrorCode());
614 
615   Entry E(*this, *AbbrevIt);
616 
617   dwarf::FormParams FormParams = {Hdr.Version, 0, dwarf::DwarfFormat::DWARF32};
618   for (auto &Value : E.Values) {
619     if (!Value.extractValue(AS, Offset, FormParams))
620       return make_error<StringError>("Error extracting index attribute values.",
621                                      inconvertibleErrorCode());
622   }
623   return std::move(E);
624 }
625 
626 DWARFDebugNames::NameTableEntry
getNameTableEntry(uint32_t Index) const627 DWARFDebugNames::NameIndex::getNameTableEntry(uint32_t Index) const {
628   assert(0 < Index && Index <= Hdr.NameCount);
629   uint32_t StringOffsetOffset = StringOffsetsBase + 4 * (Index - 1);
630   uint32_t EntryOffsetOffset = EntryOffsetsBase + 4 * (Index - 1);
631   const DWARFDataExtractor &AS = Section.AccelSection;
632 
633   uint32_t StringOffset = AS.getRelocatedValue(4, &StringOffsetOffset);
634   uint32_t EntryOffset = AS.getU32(&EntryOffsetOffset);
635   EntryOffset += EntriesBase;
636   return {Section.StringSection, Index, StringOffset, EntryOffset};
637 }
638 
639 uint32_t
getBucketArrayEntry(uint32_t Bucket) const640 DWARFDebugNames::NameIndex::getBucketArrayEntry(uint32_t Bucket) const {
641   assert(Bucket < Hdr.BucketCount);
642   uint32_t BucketOffset = BucketsBase + 4 * Bucket;
643   return Section.AccelSection.getU32(&BucketOffset);
644 }
645 
getHashArrayEntry(uint32_t Index) const646 uint32_t DWARFDebugNames::NameIndex::getHashArrayEntry(uint32_t Index) const {
647   assert(0 < Index && Index <= Hdr.NameCount);
648   uint32_t HashOffset = HashesBase + 4 * (Index - 1);
649   return Section.AccelSection.getU32(&HashOffset);
650 }
651 
652 // Returns true if we should continue scanning for entries, false if this is the
653 // last (sentinel) entry). In case of a parsing error we also return false, as
654 // it's not possible to recover this entry list (but the other lists may still
655 // parse OK).
dumpEntry(ScopedPrinter & W,uint32_t * Offset) const656 bool DWARFDebugNames::NameIndex::dumpEntry(ScopedPrinter &W,
657                                            uint32_t *Offset) const {
658   uint32_t EntryId = *Offset;
659   auto EntryOr = getEntry(Offset);
660   if (!EntryOr) {
661     handleAllErrors(EntryOr.takeError(), [](const SentinelError &) {},
662                     [&W](const ErrorInfoBase &EI) { EI.log(W.startLine()); });
663     return false;
664   }
665 
666   DictScope EntryScope(W, ("Entry @ 0x" + Twine::utohexstr(EntryId)).str());
667   EntryOr->dump(W);
668   return true;
669 }
670 
dumpName(ScopedPrinter & W,const NameTableEntry & NTE,Optional<uint32_t> Hash) const671 void DWARFDebugNames::NameIndex::dumpName(ScopedPrinter &W,
672                                           const NameTableEntry &NTE,
673                                           Optional<uint32_t> Hash) const {
674   DictScope NameScope(W, ("Name " + Twine(NTE.getIndex())).str());
675   if (Hash)
676     W.printHex("Hash", *Hash);
677 
678   W.startLine() << format("String: 0x%08x", NTE.getStringOffset());
679   W.getOStream() << " \"" << NTE.getString() << "\"\n";
680 
681   uint32_t EntryOffset = NTE.getEntryOffset();
682   while (dumpEntry(W, &EntryOffset))
683     /*empty*/;
684 }
685 
dumpCUs(ScopedPrinter & W) const686 void DWARFDebugNames::NameIndex::dumpCUs(ScopedPrinter &W) const {
687   ListScope CUScope(W, "Compilation Unit offsets");
688   for (uint32_t CU = 0; CU < Hdr.CompUnitCount; ++CU)
689     W.startLine() << format("CU[%u]: 0x%08x\n", CU, getCUOffset(CU));
690 }
691 
dumpLocalTUs(ScopedPrinter & W) const692 void DWARFDebugNames::NameIndex::dumpLocalTUs(ScopedPrinter &W) const {
693   if (Hdr.LocalTypeUnitCount == 0)
694     return;
695 
696   ListScope TUScope(W, "Local Type Unit offsets");
697   for (uint32_t TU = 0; TU < Hdr.LocalTypeUnitCount; ++TU)
698     W.startLine() << format("LocalTU[%u]: 0x%08x\n", TU, getLocalTUOffset(TU));
699 }
700 
dumpForeignTUs(ScopedPrinter & W) const701 void DWARFDebugNames::NameIndex::dumpForeignTUs(ScopedPrinter &W) const {
702   if (Hdr.ForeignTypeUnitCount == 0)
703     return;
704 
705   ListScope TUScope(W, "Foreign Type Unit signatures");
706   for (uint32_t TU = 0; TU < Hdr.ForeignTypeUnitCount; ++TU) {
707     W.startLine() << format("ForeignTU[%u]: 0x%016" PRIx64 "\n", TU,
708                             getForeignTUSignature(TU));
709   }
710 }
711 
dumpAbbreviations(ScopedPrinter & W) const712 void DWARFDebugNames::NameIndex::dumpAbbreviations(ScopedPrinter &W) const {
713   ListScope AbbrevsScope(W, "Abbreviations");
714   for (const auto &Abbr : Abbrevs)
715     Abbr.dump(W);
716 }
717 
dumpBucket(ScopedPrinter & W,uint32_t Bucket) const718 void DWARFDebugNames::NameIndex::dumpBucket(ScopedPrinter &W,
719                                             uint32_t Bucket) const {
720   ListScope BucketScope(W, ("Bucket " + Twine(Bucket)).str());
721   uint32_t Index = getBucketArrayEntry(Bucket);
722   if (Index == 0) {
723     W.printString("EMPTY");
724     return;
725   }
726   if (Index > Hdr.NameCount) {
727     W.printString("Name index is invalid");
728     return;
729   }
730 
731   for (; Index <= Hdr.NameCount; ++Index) {
732     uint32_t Hash = getHashArrayEntry(Index);
733     if (Hash % Hdr.BucketCount != Bucket)
734       break;
735 
736     dumpName(W, getNameTableEntry(Index), Hash);
737   }
738 }
739 
dump(ScopedPrinter & W) const740 LLVM_DUMP_METHOD void DWARFDebugNames::NameIndex::dump(ScopedPrinter &W) const {
741   DictScope UnitScope(W, ("Name Index @ 0x" + Twine::utohexstr(Base)).str());
742   Hdr.dump(W);
743   dumpCUs(W);
744   dumpLocalTUs(W);
745   dumpForeignTUs(W);
746   dumpAbbreviations(W);
747 
748   if (Hdr.BucketCount > 0) {
749     for (uint32_t Bucket = 0; Bucket < Hdr.BucketCount; ++Bucket)
750       dumpBucket(W, Bucket);
751     return;
752   }
753 
754   W.startLine() << "Hash table not present\n";
755   for (NameTableEntry NTE : *this)
756     dumpName(W, NTE, None);
757 }
758 
extract()759 llvm::Error DWARFDebugNames::extract() {
760   uint32_t Offset = 0;
761   while (AccelSection.isValidOffset(Offset)) {
762     NameIndex Next(*this, Offset);
763     if (llvm::Error E = Next.extract())
764       return E;
765     Offset = Next.getNextUnitOffset();
766     NameIndices.push_back(std::move(Next));
767   }
768   return Error::success();
769 }
770 
771 iterator_range<DWARFDebugNames::ValueIterator>
equal_range(StringRef Key) const772 DWARFDebugNames::NameIndex::equal_range(StringRef Key) const {
773   return make_range(ValueIterator(*this, Key), ValueIterator());
774 }
775 
dump(raw_ostream & OS) const776 LLVM_DUMP_METHOD void DWARFDebugNames::dump(raw_ostream &OS) const {
777   ScopedPrinter W(OS);
778   for (const NameIndex &NI : NameIndices)
779     NI.dump(W);
780 }
781 
782 Optional<uint32_t>
findEntryOffsetInCurrentIndex()783 DWARFDebugNames::ValueIterator::findEntryOffsetInCurrentIndex() {
784   const Header &Hdr = CurrentIndex->Hdr;
785   if (Hdr.BucketCount == 0) {
786     // No Hash Table, We need to search through all names in the Name Index.
787     for (NameTableEntry NTE : *CurrentIndex) {
788       if (NTE.getString() == Key)
789         return NTE.getEntryOffset();
790     }
791     return None;
792   }
793 
794   // The Name Index has a Hash Table, so use that to speed up the search.
795   // Compute the Key Hash, if it has not been done already.
796   if (!Hash)
797     Hash = caseFoldingDjbHash(Key);
798   uint32_t Bucket = *Hash % Hdr.BucketCount;
799   uint32_t Index = CurrentIndex->getBucketArrayEntry(Bucket);
800   if (Index == 0)
801     return None; // Empty bucket
802 
803   for (; Index <= Hdr.NameCount; ++Index) {
804     uint32_t Hash = CurrentIndex->getHashArrayEntry(Index);
805     if (Hash % Hdr.BucketCount != Bucket)
806       return None; // End of bucket
807 
808     NameTableEntry NTE = CurrentIndex->getNameTableEntry(Index);
809     if (NTE.getString() == Key)
810       return NTE.getEntryOffset();
811   }
812   return None;
813 }
814 
getEntryAtCurrentOffset()815 bool DWARFDebugNames::ValueIterator::getEntryAtCurrentOffset() {
816   auto EntryOr = CurrentIndex->getEntry(&DataOffset);
817   if (!EntryOr) {
818     consumeError(EntryOr.takeError());
819     return false;
820   }
821   CurrentEntry = std::move(*EntryOr);
822   return true;
823 }
824 
findInCurrentIndex()825 bool DWARFDebugNames::ValueIterator::findInCurrentIndex() {
826   Optional<uint32_t> Offset = findEntryOffsetInCurrentIndex();
827   if (!Offset)
828     return false;
829   DataOffset = *Offset;
830   return getEntryAtCurrentOffset();
831 }
832 
searchFromStartOfCurrentIndex()833 void DWARFDebugNames::ValueIterator::searchFromStartOfCurrentIndex() {
834   for (const NameIndex *End = CurrentIndex->Section.NameIndices.end();
835        CurrentIndex != End; ++CurrentIndex) {
836     if (findInCurrentIndex())
837       return;
838   }
839   setEnd();
840 }
841 
next()842 void DWARFDebugNames::ValueIterator::next() {
843   assert(CurrentIndex && "Incrementing an end() iterator?");
844 
845   // First try the next entry in the current Index.
846   if (getEntryAtCurrentOffset())
847     return;
848 
849   // If we're a local iterator or we have reached the last Index, we're done.
850   if (IsLocal || CurrentIndex == &CurrentIndex->Section.NameIndices.back()) {
851     setEnd();
852     return;
853   }
854 
855   // Otherwise, try the next index.
856   ++CurrentIndex;
857   searchFromStartOfCurrentIndex();
858 }
859 
ValueIterator(const DWARFDebugNames & AccelTable,StringRef Key)860 DWARFDebugNames::ValueIterator::ValueIterator(const DWARFDebugNames &AccelTable,
861                                               StringRef Key)
862     : CurrentIndex(AccelTable.NameIndices.begin()), IsLocal(false), Key(Key) {
863   searchFromStartOfCurrentIndex();
864 }
865 
ValueIterator(const DWARFDebugNames::NameIndex & NI,StringRef Key)866 DWARFDebugNames::ValueIterator::ValueIterator(
867     const DWARFDebugNames::NameIndex &NI, StringRef Key)
868     : CurrentIndex(&NI), IsLocal(true), Key(Key) {
869   if (!findInCurrentIndex())
870     setEnd();
871 }
872 
873 iterator_range<DWARFDebugNames::ValueIterator>
equal_range(StringRef Key) const874 DWARFDebugNames::equal_range(StringRef Key) const {
875   if (NameIndices.empty())
876     return make_range(ValueIterator(), ValueIterator());
877   return make_range(ValueIterator(*this, Key), ValueIterator());
878 }
879 
880 const DWARFDebugNames::NameIndex *
getCUNameIndex(uint32_t CUOffset)881 DWARFDebugNames::getCUNameIndex(uint32_t CUOffset) {
882   if (CUToNameIndex.size() == 0 && NameIndices.size() > 0) {
883     for (const auto &NI : *this) {
884       for (uint32_t CU = 0; CU < NI.getCUCount(); ++CU)
885         CUToNameIndex.try_emplace(NI.getCUOffset(CU), &NI);
886     }
887   }
888   return CUToNameIndex.lookup(CUOffset);
889 }
890