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