1155 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h"10 11#include "llvm/ADT/SmallVector.h"12#include "llvm/BinaryFormat/Dwarf.h"13#include "llvm/Support/Compiler.h"14#include "llvm/Support/DJB.h"15#include "llvm/Support/Errc.h"16#include "llvm/Support/Format.h"17#include "llvm/Support/FormatVariadic.h"18#include "llvm/Support/ScopedPrinter.h"19#include "llvm/Support/raw_ostream.h"20#include <cstddef>21#include <cstdint>22#include <utility>23 24using namespace llvm;25 26namespace {27struct Atom {28 unsigned Value;29};30 31static raw_ostream &operator<<(raw_ostream &OS, const Atom &A) {32 StringRef Str = dwarf::AtomTypeString(A.Value);33 if (!Str.empty())34 return OS << Str;35 return OS << "DW_ATOM_unknown_" << format("%x", A.Value);36}37} // namespace38 39static Atom formatAtom(unsigned Atom) { return {Atom}; }40 41DWARFAcceleratorTable::~DWARFAcceleratorTable() = default;42 43Error AppleAcceleratorTable::extract() {44 uint64_t Offset = 0;45 46 // Check that we can at least read the header.47 if (!AccelSection.isValidOffset(offsetof(Header, HeaderDataLength) + 4))48 return createStringError(errc::illegal_byte_sequence,49 "Section too small: cannot read header.");50 51 Hdr.Magic = AccelSection.getU32(&Offset);52 Hdr.Version = AccelSection.getU16(&Offset);53 Hdr.HashFunction = AccelSection.getU16(&Offset);54 Hdr.BucketCount = AccelSection.getU32(&Offset);55 Hdr.HashCount = AccelSection.getU32(&Offset);56 Hdr.HeaderDataLength = AccelSection.getU32(&Offset);57 FormParams = {Hdr.Version, 0, dwarf::DwarfFormat::DWARF32};58 59 // Check that we can read all the hashes and offsets from the60 // section (see SourceLevelDebugging.rst for the structure of the index).61 if (!AccelSection.isValidOffset(getIthBucketBase(Hdr.BucketCount - 1)))62 return createStringError(63 errc::illegal_byte_sequence,64 "Section too small: cannot read buckets and hashes.");65 66 HdrData.DIEOffsetBase = AccelSection.getU32(&Offset);67 uint32_t NumAtoms = AccelSection.getU32(&Offset);68 69 HashDataEntryLength = 0;70 auto MakeUnsupportedFormError = [](dwarf::Form Form) {71 return createStringError(errc::not_supported,72 "Unsupported form:" +73 dwarf::FormEncodingString(Form));74 };75 76 for (unsigned i = 0; i < NumAtoms; ++i) {77 uint16_t AtomType = AccelSection.getU16(&Offset);78 auto AtomForm = static_cast<dwarf::Form>(AccelSection.getU16(&Offset));79 HdrData.Atoms.push_back(std::make_pair(AtomType, AtomForm));80 81 std::optional<uint8_t> FormSize =82 dwarf::getFixedFormByteSize(AtomForm, FormParams);83 if (!FormSize)84 return MakeUnsupportedFormError(AtomForm);85 HashDataEntryLength += *FormSize;86 }87 88 IsValid = true;89 return Error::success();90}91 92uint32_t AppleAcceleratorTable::getNumBuckets() const {93 return Hdr.BucketCount;94}95uint32_t AppleAcceleratorTable::getNumHashes() const { return Hdr.HashCount; }96uint32_t AppleAcceleratorTable::getSizeHdr() const { return sizeof(Hdr); }97uint32_t AppleAcceleratorTable::getHeaderDataLength() const {98 return Hdr.HeaderDataLength;99}100 101ArrayRef<std::pair<AppleAcceleratorTable::HeaderData::AtomType,102 AppleAcceleratorTable::HeaderData::Form>>103AppleAcceleratorTable::getAtomsDesc() {104 return HdrData.Atoms;105}106 107bool AppleAcceleratorTable::validateForms() {108 for (auto Atom : getAtomsDesc()) {109 DWARFFormValue FormValue(Atom.second);110 switch (Atom.first) {111 case dwarf::DW_ATOM_die_offset:112 case dwarf::DW_ATOM_die_tag:113 case dwarf::DW_ATOM_type_flags:114 if ((!FormValue.isFormClass(DWARFFormValue::FC_Constant) &&115 !FormValue.isFormClass(DWARFFormValue::FC_Flag)) ||116 FormValue.getForm() == dwarf::DW_FORM_sdata)117 return false;118 break;119 default:120 break;121 }122 }123 return true;124}125 126std::pair<uint64_t, dwarf::Tag>127AppleAcceleratorTable::readAtoms(uint64_t *HashDataOffset) {128 uint64_t DieOffset = dwarf::DW_INVALID_OFFSET;129 dwarf::Tag DieTag = dwarf::DW_TAG_null;130 131 for (auto Atom : getAtomsDesc()) {132 DWARFFormValue FormValue(Atom.second);133 FormValue.extractValue(AccelSection, HashDataOffset, FormParams);134 switch (Atom.first) {135 case dwarf::DW_ATOM_die_offset:136 DieOffset = *FormValue.getAsUnsignedConstant();137 break;138 case dwarf::DW_ATOM_die_tag:139 DieTag = (dwarf::Tag)*FormValue.getAsUnsignedConstant();140 break;141 default:142 break;143 }144 }145 return {DieOffset, DieTag};146}147 148void AppleAcceleratorTable::Header::dump(ScopedPrinter &W) const {149 DictScope HeaderScope(W, "Header");150 W.printHex("Magic", Magic);151 W.printHex("Version", Version);152 W.printHex("Hash function", HashFunction);153 W.printNumber("Bucket count", BucketCount);154 W.printNumber("Hashes count", HashCount);155 W.printNumber("HeaderData length", HeaderDataLength);156}157 158std::optional<uint64_t> AppleAcceleratorTable::HeaderData::extractOffset(159 std::optional<DWARFFormValue> Value) const {160 if (!Value)161 return std::nullopt;162 163 switch (Value->getForm()) {164 case dwarf::DW_FORM_ref1:165 case dwarf::DW_FORM_ref2:166 case dwarf::DW_FORM_ref4:167 case dwarf::DW_FORM_ref8:168 case dwarf::DW_FORM_ref_udata:169 return Value->getRawUValue() + DIEOffsetBase;170 default:171 return Value->getAsSectionOffset();172 }173}174 175bool AppleAcceleratorTable::dumpName(ScopedPrinter &W,176 SmallVectorImpl<DWARFFormValue> &AtomForms,177 uint64_t *DataOffset) const {178 uint64_t NameOffset = *DataOffset;179 if (!AccelSection.isValidOffsetForDataOfSize(*DataOffset, 4)) {180 W.printString("Incorrectly terminated list.");181 return false;182 }183 uint64_t StringOffset = AccelSection.getRelocatedValue(4, DataOffset);184 if (!StringOffset)185 return false; // End of list186 187 DictScope NameScope(W, ("Name@0x" + Twine::utohexstr(NameOffset)).str());188 W.startLine() << format("String: 0x%08" PRIx64, StringOffset);189 W.getOStream() << " \"" << StringSection.getCStr(&StringOffset) << "\"\n";190 191 unsigned NumData = AccelSection.getU32(DataOffset);192 for (unsigned Data = 0; Data < NumData; ++Data) {193 ListScope DataScope(W, ("Data " + Twine(Data)).str());194 unsigned i = 0;195 for (auto &Atom : AtomForms) {196 W.startLine() << format("Atom[%d]: ", i);197 if (Atom.extractValue(AccelSection, DataOffset, FormParams)) {198 Atom.dump(W.getOStream());199 if (std::optional<uint64_t> Val = Atom.getAsUnsignedConstant()) {200 StringRef Str = dwarf::AtomValueString(HdrData.Atoms[i].first, *Val);201 if (!Str.empty())202 W.getOStream() << " (" << Str << ")";203 }204 } else205 W.getOStream() << "Error extracting the value";206 W.getOStream() << "\n";207 i++;208 }209 }210 return true; // more entries follow211}212 213LLVM_DUMP_METHOD void AppleAcceleratorTable::dump(raw_ostream &OS) const {214 if (!IsValid)215 return;216 217 ScopedPrinter W(OS);218 219 Hdr.dump(W);220 221 W.printNumber("DIE offset base", HdrData.DIEOffsetBase);222 W.printNumber("Number of atoms", uint64_t(HdrData.Atoms.size()));223 W.printNumber("Size of each hash data entry", getHashDataEntryLength());224 SmallVector<DWARFFormValue, 3> AtomForms;225 {226 ListScope AtomsScope(W, "Atoms");227 unsigned i = 0;228 for (const auto &Atom : HdrData.Atoms) {229 DictScope AtomScope(W, ("Atom " + Twine(i++)).str());230 W.startLine() << "Type: " << formatAtom(Atom.first) << '\n';231 W.startLine() << "Form: " << formatv("{0}", Atom.second) << '\n';232 AtomForms.push_back(DWARFFormValue(Atom.second));233 }234 }235 236 // Now go through the actual tables and dump them.237 uint64_t Offset = sizeof(Hdr) + Hdr.HeaderDataLength;238 uint64_t HashesBase = Offset + Hdr.BucketCount * 4;239 uint64_t OffsetsBase = HashesBase + Hdr.HashCount * 4;240 241 for (unsigned Bucket = 0; Bucket < Hdr.BucketCount; ++Bucket) {242 unsigned Index = AccelSection.getU32(&Offset);243 244 ListScope BucketScope(W, ("Bucket " + Twine(Bucket)).str());245 if (Index == UINT32_MAX) {246 W.printString("EMPTY");247 continue;248 }249 250 for (unsigned HashIdx = Index; HashIdx < Hdr.HashCount; ++HashIdx) {251 uint64_t HashOffset = HashesBase + HashIdx*4;252 uint64_t OffsetsOffset = OffsetsBase + HashIdx*4;253 uint32_t Hash = AccelSection.getU32(&HashOffset);254 255 if (Hash % Hdr.BucketCount != Bucket)256 break;257 258 uint64_t DataOffset = AccelSection.getU32(&OffsetsOffset);259 ListScope HashScope(W, ("Hash 0x" + Twine::utohexstr(Hash)).str());260 if (!AccelSection.isValidOffset(DataOffset)) {261 W.printString("Invalid section offset");262 continue;263 }264 while (dumpName(W, AtomForms, &DataOffset))265 /*empty*/;266 }267 }268}269 270AppleAcceleratorTable::Entry::Entry(const AppleAcceleratorTable &Table)271 : Table(Table) {272 Values.reserve(Table.HdrData.Atoms.size());273 for (const auto &Atom : Table.HdrData.Atoms)274 Values.push_back(DWARFFormValue(Atom.second));275}276 277void AppleAcceleratorTable::Entry::extract(uint64_t *Offset) {278 for (auto &FormValue : Values)279 FormValue.extractValue(Table.AccelSection, Offset, Table.FormParams);280}281 282std::optional<DWARFFormValue>283AppleAcceleratorTable::Entry::lookup(HeaderData::AtomType AtomToFind) const {284 for (auto [Atom, FormValue] : zip_equal(Table.HdrData.Atoms, Values))285 if (Atom.first == AtomToFind)286 return FormValue;287 return std::nullopt;288}289 290std::optional<uint64_t>291AppleAcceleratorTable::Entry::getDIESectionOffset() const {292 return Table.HdrData.extractOffset(lookup(dwarf::DW_ATOM_die_offset));293}294 295std::optional<uint64_t> AppleAcceleratorTable::Entry::getCUOffset() const {296 return Table.HdrData.extractOffset(lookup(dwarf::DW_ATOM_cu_offset));297}298 299std::optional<dwarf::Tag> AppleAcceleratorTable::Entry::getTag() const {300 std::optional<DWARFFormValue> Tag = lookup(dwarf::DW_ATOM_die_tag);301 if (!Tag)302 return std::nullopt;303 if (std::optional<uint64_t> Value = Tag->getAsUnsignedConstant())304 return dwarf::Tag(*Value);305 return std::nullopt;306}307 308AppleAcceleratorTable::SameNameIterator::SameNameIterator(309 const AppleAcceleratorTable &AccelTable, uint64_t DataOffset)310 : Current(AccelTable), Offset(DataOffset) {}311 312void AppleAcceleratorTable::Iterator::prepareNextEntryOrEnd() {313 if (NumEntriesToCome == 0)314 prepareNextStringOrEnd();315 if (isEnd())316 return;317 uint64_t OffsetCopy = Offset;318 Current.BaseEntry.extract(&OffsetCopy);319 NumEntriesToCome--;320 Offset += getTable().getHashDataEntryLength();321}322 323void AppleAcceleratorTable::Iterator::prepareNextStringOrEnd() {324 const AppleAcceleratorTable &Table = getTable();325 if (Offset == 0) {326 // Always start looking for strings using a valid offset from the Offsets327 // table. Entries are not always consecutive.328 std::optional<uint64_t> OptOffset = Table.readIthOffset(OffsetIdx++);329 if (!OptOffset)330 return setToEnd();331 Offset = *OptOffset;332 }333 std::optional<uint32_t> StrOffset = Table.readStringOffsetAt(Offset);334 if (!StrOffset)335 return setToEnd();336 337 // A zero denotes the end of the collision list. Skip to the next offset338 // in the offsets table by setting the Offset to zero so we will grab the339 // next offset from the offsets table.340 if (*StrOffset == 0) {341 Offset = 0;342 return prepareNextStringOrEnd();343 }344 Current.StrOffset = *StrOffset;345 346 std::optional<uint32_t> MaybeNumEntries = Table.readU32FromAccel(Offset);347 if (!MaybeNumEntries || *MaybeNumEntries == 0)348 return setToEnd();349 NumEntriesToCome = *MaybeNumEntries;350}351 352AppleAcceleratorTable::Iterator::Iterator(const AppleAcceleratorTable &Table,353 bool SetEnd)354 : Current(Table), Offset(0), NumEntriesToCome(0) {355 if (SetEnd)356 setToEnd();357 else358 prepareNextEntryOrEnd();359}360 361iterator_range<AppleAcceleratorTable::SameNameIterator>362AppleAcceleratorTable::equal_range(StringRef Key) const {363 const auto EmptyRange =364 make_range(SameNameIterator(*this, 0), SameNameIterator(*this, 0));365 if (!IsValid)366 return EmptyRange;367 368 // Find the bucket.369 uint32_t SearchHash = djbHash(Key);370 uint32_t BucketIdx = hashToBucketIdx(SearchHash);371 std::optional<uint32_t> HashIdx = idxOfHashInBucket(SearchHash, BucketIdx);372 if (!HashIdx)373 return EmptyRange;374 375 std::optional<uint64_t> MaybeDataOffset = readIthOffset(*HashIdx);376 if (!MaybeDataOffset)377 return EmptyRange;378 379 uint64_t DataOffset = *MaybeDataOffset;380 if (DataOffset >= AccelSection.size())381 return EmptyRange;382 383 std::optional<uint32_t> StrOffset = readStringOffsetAt(DataOffset);384 // Valid input and still have strings in this hash.385 while (StrOffset && *StrOffset) {386 std::optional<StringRef> MaybeStr = readStringFromStrSection(*StrOffset);387 std::optional<uint32_t> NumEntries = this->readU32FromAccel(DataOffset);388 if (!MaybeStr || !NumEntries)389 return EmptyRange;390 uint64_t EndOffset = DataOffset + *NumEntries * getHashDataEntryLength();391 if (Key == *MaybeStr)392 return make_range({*this, DataOffset},393 SameNameIterator{*this, EndOffset});394 DataOffset = EndOffset;395 StrOffset = readStringOffsetAt(DataOffset);396 }397 398 return EmptyRange;399}400 401std::optional<uint32_t>402AppleAcceleratorTable::idxOfHashInBucket(uint32_t HashToFind,403 uint32_t BucketIdx) const {404 std::optional<uint32_t> HashStartIdx = readIthBucket(BucketIdx);405 if (!HashStartIdx)406 return std::nullopt;407 408 for (uint32_t HashIdx = *HashStartIdx; HashIdx < getNumHashes(); HashIdx++) {409 std::optional<uint32_t> MaybeHash = readIthHash(HashIdx);410 if (!MaybeHash || !wouldHashBeInBucket(*MaybeHash, BucketIdx))411 break;412 if (*MaybeHash == HashToFind)413 return HashIdx;414 }415 return std::nullopt;416}417 418std::optional<StringRef> AppleAcceleratorTable::readStringFromStrSection(419 uint64_t StringSectionOffset) const {420 Error E = Error::success();421 StringRef Str = StringSection.getCStrRef(&StringSectionOffset, &E);422 if (E) {423 consumeError(std::move(E));424 return std::nullopt;425 }426 return Str;427}428 429std::optional<uint32_t>430AppleAcceleratorTable::readU32FromAccel(uint64_t &Offset,431 bool UseRelocation) const {432 Error E = Error::success();433 uint32_t Data = UseRelocation434 ? AccelSection.getRelocatedValue(4, &Offset, nullptr, &E)435 : AccelSection.getU32(&Offset, &E);436 if (E) {437 consumeError(std::move(E));438 return std::nullopt;439 }440 return Data;441}442 443void DWARFDebugNames::Header::dump(ScopedPrinter &W) const {444 DictScope HeaderScope(W, "Header");445 W.printHex("Length", UnitLength);446 W.printString("Format", dwarf::FormatString(Format));447 W.printNumber("Version", Version);448 W.printNumber("CU count", CompUnitCount);449 W.printNumber("Local TU count", LocalTypeUnitCount);450 W.printNumber("Foreign TU count", ForeignTypeUnitCount);451 W.printNumber("Bucket count", BucketCount);452 W.printNumber("Name count", NameCount);453 W.printHex("Abbreviations table size", AbbrevTableSize);454 W.startLine() << "Augmentation: '" << AugmentationString << "'\n";455}456 457Error DWARFDebugNames::Header::extract(const DWARFDataExtractor &AS,458 uint64_t *Offset) {459 auto HeaderError = [Offset = *Offset](Error E) {460 return createStringError(errc::illegal_byte_sequence,461 "parsing .debug_names header at 0x%" PRIx64 ": %s",462 Offset, toString(std::move(E)).c_str());463 };464 465 DataExtractor::Cursor C(*Offset);466 std::tie(UnitLength, Format) = AS.getInitialLength(C);467 468 Version = AS.getU16(C);469 AS.skip(C, 2); // padding470 CompUnitCount = AS.getU32(C);471 LocalTypeUnitCount = AS.getU32(C);472 ForeignTypeUnitCount = AS.getU32(C);473 BucketCount = AS.getU32(C);474 NameCount = AS.getU32(C);475 AbbrevTableSize = AS.getU32(C);476 AugmentationStringSize = alignTo(AS.getU32(C), 4);477 478 if (!C)479 return HeaderError(C.takeError());480 481 if (!AS.isValidOffsetForDataOfSize(C.tell(), AugmentationStringSize))482 return HeaderError(createStringError(errc::illegal_byte_sequence,483 "cannot read header augmentation"));484 AugmentationString.resize(AugmentationStringSize);485 AS.getU8(C, reinterpret_cast<uint8_t *>(AugmentationString.data()),486 AugmentationStringSize);487 *Offset = C.tell();488 return C.takeError();489}490 491void DWARFDebugNames::Abbrev::dump(ScopedPrinter &W) const {492 DictScope AbbrevScope(W, ("Abbreviation 0x" + Twine::utohexstr(Code)).str());493 W.startLine() << formatv("Tag: {0}\n", Tag);494 495 for (const auto &Attr : Attributes)496 W.startLine() << formatv("{0}: {1}\n", Attr.Index, Attr.Form);497}498 499static constexpr DWARFDebugNames::AttributeEncoding sentinelAttrEnc() {500 return {dwarf::Index(0), dwarf::Form(0)};501}502 503static bool isSentinel(const DWARFDebugNames::AttributeEncoding &AE) {504 return AE == sentinelAttrEnc();505}506 507static DWARFDebugNames::Abbrev sentinelAbbrev() {508 return DWARFDebugNames::Abbrev(0, dwarf::Tag(0), 0, {});509}510 511static bool isSentinel(const DWARFDebugNames::Abbrev &Abbr) {512 return Abbr.Code == 0;513}514 515DWARFDebugNames::Abbrev DWARFDebugNames::AbbrevMapInfo::getEmptyKey() {516 return sentinelAbbrev();517}518 519DWARFDebugNames::Abbrev DWARFDebugNames::AbbrevMapInfo::getTombstoneKey() {520 return DWARFDebugNames::Abbrev(~0, dwarf::Tag(0), 0, {});521}522 523Expected<DWARFDebugNames::AttributeEncoding>524DWARFDebugNames::NameIndex::extractAttributeEncoding(uint64_t *Offset) {525 if (*Offset >= Offsets.EntriesBase) {526 return createStringError(errc::illegal_byte_sequence,527 "Incorrectly terminated abbreviation table.");528 }529 530 uint32_t Index = Section.AccelSection.getULEB128(Offset);531 uint32_t Form = Section.AccelSection.getULEB128(Offset);532 return AttributeEncoding(dwarf::Index(Index), dwarf::Form(Form));533}534 535Expected<std::vector<DWARFDebugNames::AttributeEncoding>>536DWARFDebugNames::NameIndex::extractAttributeEncodings(uint64_t *Offset) {537 std::vector<AttributeEncoding> Result;538 for (;;) {539 auto AttrEncOr = extractAttributeEncoding(Offset);540 if (!AttrEncOr)541 return AttrEncOr.takeError();542 if (isSentinel(*AttrEncOr))543 return std::move(Result);544 545 Result.emplace_back(*AttrEncOr);546 }547}548 549Expected<DWARFDebugNames::Abbrev>550DWARFDebugNames::NameIndex::extractAbbrev(uint64_t *Offset) {551 if (*Offset >= Offsets.EntriesBase) {552 return createStringError(errc::illegal_byte_sequence,553 "Incorrectly terminated abbreviation table.");554 }555 const uint64_t AbbrevOffset = *Offset;556 uint32_t Code = Section.AccelSection.getULEB128(Offset);557 if (Code == 0)558 return sentinelAbbrev();559 560 uint32_t Tag = Section.AccelSection.getULEB128(Offset);561 auto AttrEncOr = extractAttributeEncodings(Offset);562 if (!AttrEncOr)563 return AttrEncOr.takeError();564 return Abbrev(Code, dwarf::Tag(Tag), AbbrevOffset, std::move(*AttrEncOr));565}566 567DWARFDebugNames::DWARFDebugNamesOffsets568dwarf::findDebugNamesOffsets(uint64_t EndOfHeaderOffset,569 const DWARFDebugNames::Header &Hdr) {570 uint64_t DwarfSize = getDwarfOffsetByteSize(Hdr.Format);571 DWARFDebugNames::DWARFDebugNamesOffsets Ret;572 Ret.CUsBase = EndOfHeaderOffset;573 Ret.BucketsBase = Ret.CUsBase + Hdr.CompUnitCount * DwarfSize +574 Hdr.LocalTypeUnitCount * DwarfSize +575 Hdr.ForeignTypeUnitCount * 8;576 Ret.HashesBase = Ret.BucketsBase + Hdr.BucketCount * 4;577 Ret.StringOffsetsBase =578 Ret.HashesBase + (Hdr.BucketCount > 0 ? Hdr.NameCount * 4 : 0);579 Ret.EntryOffsetsBase = Ret.StringOffsetsBase + Hdr.NameCount * DwarfSize;580 Ret.EntriesBase =581 Ret.EntryOffsetsBase + Hdr.NameCount * DwarfSize + Hdr.AbbrevTableSize;582 return Ret;583}584 585Error DWARFDebugNames::NameIndex::extract() {586 const DWARFDataExtractor &AS = Section.AccelSection;587 uint64_t EndOfHeaderOffset = Base;588 if (Error E = Hdr.extract(AS, &EndOfHeaderOffset))589 return E;590 591 const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);592 Offsets = dwarf::findDebugNamesOffsets(EndOfHeaderOffset, Hdr);593 594 uint64_t Offset =595 Offsets.EntryOffsetsBase + (Hdr.NameCount * SectionOffsetSize);596 597 if (!AS.isValidOffsetForDataOfSize(Offset, Hdr.AbbrevTableSize))598 return createStringError(errc::illegal_byte_sequence,599 "Section too small: cannot read abbreviations.");600 601 Offsets.EntriesBase = Offset + Hdr.AbbrevTableSize;602 603 for (;;) {604 auto AbbrevOr = extractAbbrev(&Offset);605 if (!AbbrevOr)606 return AbbrevOr.takeError();607 if (isSentinel(*AbbrevOr))608 return Error::success();609 610 if (!Abbrevs.insert(std::move(*AbbrevOr)).second)611 return createStringError(errc::invalid_argument,612 "Duplicate abbreviation code.");613 }614}615 616DWARFDebugNames::Entry::Entry(const NameIndex &NameIdx, const Abbrev &Abbr)617 : NameIdx(&NameIdx), Abbr(&Abbr) {618 // This merely creates form values. It is up to the caller619 // (NameIndex::getEntry) to populate them.620 Values.reserve(Abbr.Attributes.size());621 for (const auto &Attr : Abbr.Attributes)622 Values.emplace_back(Attr.Form);623}624 625std::optional<DWARFFormValue>626DWARFDebugNames::Entry::lookup(dwarf::Index Index) const {627 assert(Abbr->Attributes.size() == Values.size());628 for (auto Tuple : zip_first(Abbr->Attributes, Values)) {629 if (std::get<0>(Tuple).Index == Index)630 return std::get<1>(Tuple);631 }632 return std::nullopt;633}634 635bool DWARFDebugNames::Entry::hasParentInformation() const {636 return lookup(dwarf::DW_IDX_parent).has_value();637}638 639std::optional<uint64_t> DWARFDebugNames::Entry::getDIEUnitOffset() const {640 if (std::optional<DWARFFormValue> Off = lookup(dwarf::DW_IDX_die_offset))641 return Off->getAsReferenceUVal();642 return std::nullopt;643}644 645std::optional<uint64_t> DWARFDebugNames::Entry::getRelatedCUIndex() const {646 // Return the DW_IDX_compile_unit attribute value if it is specified.647 if (std::optional<DWARFFormValue> Off = lookup(dwarf::DW_IDX_compile_unit))648 return Off->getAsUnsignedConstant();649 // In a per-CU index, the entries without a DW_IDX_compile_unit attribute650 // implicitly refer to the single CU.651 if (NameIdx->getCUCount() == 1)652 return 0;653 return std::nullopt;654}655 656std::optional<uint64_t> DWARFDebugNames::Entry::getCUIndex() const {657 // Return the DW_IDX_compile_unit attribute value but only if we don't have a658 // DW_IDX_type_unit attribute. Use Entry::getRelatedCUIndex() to get the659 // associated CU index if this behaviour is not desired.660 if (lookup(dwarf::DW_IDX_type_unit).has_value())661 return std::nullopt;662 return getRelatedCUIndex();663}664 665std::optional<uint64_t> DWARFDebugNames::Entry::getCUOffset() const {666 std::optional<uint64_t> Index = getCUIndex();667 if (!Index || *Index >= NameIdx->getCUCount())668 return std::nullopt;669 return NameIdx->getCUOffset(*Index);670}671 672std::optional<uint64_t> DWARFDebugNames::Entry::getRelatedCUOffset() const {673 std::optional<uint64_t> Index = getRelatedCUIndex();674 if (!Index || *Index >= NameIdx->getCUCount())675 return std::nullopt;676 return NameIdx->getCUOffset(*Index);677}678 679std::optional<uint64_t> DWARFDebugNames::Entry::getLocalTUOffset() const {680 std::optional<uint64_t> Index = getTUIndex();681 if (!Index || *Index >= NameIdx->getLocalTUCount())682 return std::nullopt;683 return NameIdx->getLocalTUOffset(*Index);684}685 686std::optional<uint64_t>687DWARFDebugNames::Entry::getForeignTUTypeSignature() const {688 std::optional<uint64_t> Index = getTUIndex();689 const uint32_t NumLocalTUs = NameIdx->getLocalTUCount();690 if (!Index || *Index < NumLocalTUs)691 return std::nullopt; // Invalid TU index or TU index is for a local TU692 // The foreign TU index is the TU index minus the number of local TUs.693 const uint64_t ForeignTUIndex = *Index - NumLocalTUs;694 if (ForeignTUIndex >= NameIdx->getForeignTUCount())695 return std::nullopt; // Invalid foreign TU index.696 return NameIdx->getForeignTUSignature(ForeignTUIndex);697}698 699std::optional<uint64_t> DWARFDebugNames::Entry::getTUIndex() const {700 if (std::optional<DWARFFormValue> Off = lookup(dwarf::DW_IDX_type_unit))701 return Off->getAsUnsignedConstant();702 return std::nullopt;703}704 705Expected<std::optional<DWARFDebugNames::Entry>>706DWARFDebugNames::Entry::getParentDIEEntry() const {707 // The offset of the accelerator table entry for the parent.708 std::optional<DWARFFormValue> ParentEntryOff = lookup(dwarf::DW_IDX_parent);709 assert(ParentEntryOff.has_value() && "hasParentInformation() must be called");710 711 if (ParentEntryOff->getForm() == dwarf::Form::DW_FORM_flag_present)712 return std::nullopt;713 return NameIdx->getEntryAtRelativeOffset(ParentEntryOff->getRawUValue());714}715 716void DWARFDebugNames::Entry::dumpParentIdx(717 ScopedPrinter &W, const DWARFFormValue &FormValue) const {718 Expected<std::optional<Entry>> ParentEntry = getParentDIEEntry();719 if (!ParentEntry) {720 W.getOStream() << "<invalid offset data>";721 consumeError(ParentEntry.takeError());722 return;723 }724 725 if (!ParentEntry->has_value()) {726 W.getOStream() << "<parent not indexed>";727 return;728 }729 730 auto AbsoluteOffset = NameIdx->Offsets.EntriesBase + FormValue.getRawUValue();731 W.getOStream() << "Entry @ 0x" + Twine::utohexstr(AbsoluteOffset);732}733 734void DWARFDebugNames::Entry::dump(ScopedPrinter &W) const {735 W.startLine() << formatv("Abbrev: {0:x}\n", Abbr->Code);736 W.startLine() << formatv("Tag: {0}\n", Abbr->Tag);737 assert(Abbr->Attributes.size() == Values.size());738 for (auto Tuple : zip_first(Abbr->Attributes, Values)) {739 auto Index = std::get<0>(Tuple).Index;740 W.startLine() << formatv("{0}: ", Index);741 742 auto FormValue = std::get<1>(Tuple);743 if (Index == dwarf::Index::DW_IDX_parent)744 dumpParentIdx(W, FormValue);745 else746 FormValue.dump(W.getOStream());747 W.getOStream() << '\n';748 }749}750 751char DWARFDebugNames::SentinelError::ID;752std::error_code DWARFDebugNames::SentinelError::convertToErrorCode() const {753 return inconvertibleErrorCode();754}755 756uint64_t DWARFDebugNames::NameIndex::getCUOffset(uint32_t CU) const {757 assert(CU < Hdr.CompUnitCount);758 const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);759 uint64_t Offset = Offsets.CUsBase + SectionOffsetSize * CU;760 return Section.AccelSection.getRelocatedValue(SectionOffsetSize, &Offset);761}762 763uint64_t DWARFDebugNames::NameIndex::getLocalTUOffset(uint32_t TU) const {764 assert(TU < Hdr.LocalTypeUnitCount);765 const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);766 uint64_t Offset =767 Offsets.CUsBase + SectionOffsetSize * (Hdr.CompUnitCount + TU);768 return Section.AccelSection.getRelocatedValue(SectionOffsetSize, &Offset);769}770 771uint64_t DWARFDebugNames::NameIndex::getForeignTUSignature(uint32_t TU) const {772 assert(TU < Hdr.ForeignTypeUnitCount);773 const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);774 uint64_t Offset =775 Offsets.CUsBase +776 SectionOffsetSize * (Hdr.CompUnitCount + Hdr.LocalTypeUnitCount) + 8 * TU;777 return Section.AccelSection.getU64(&Offset);778}779 780Expected<DWARFDebugNames::Entry>781DWARFDebugNames::NameIndex::getEntry(uint64_t *Offset) const {782 const DWARFDataExtractor &AS = Section.AccelSection;783 if (!AS.isValidOffset(*Offset))784 return createStringError(errc::illegal_byte_sequence,785 "Incorrectly terminated entry list.");786 787 uint32_t AbbrevCode = AS.getULEB128(Offset);788 if (AbbrevCode == 0)789 return make_error<SentinelError>();790 791 const auto AbbrevIt = Abbrevs.find_as(AbbrevCode);792 if (AbbrevIt == Abbrevs.end())793 return createStringError(errc::invalid_argument, "Invalid abbreviation.");794 795 Entry E(*this, *AbbrevIt);796 797 dwarf::FormParams FormParams = {Hdr.Version, 0, Hdr.Format};798 for (auto &Value : E.Values) {799 if (!Value.extractValue(AS, Offset, FormParams))800 return createStringError(errc::io_error,801 "Error extracting index attribute values.");802 }803 return std::move(E);804}805 806DWARFDebugNames::NameTableEntry807DWARFDebugNames::NameIndex::getNameTableEntry(uint32_t Index) const {808 assert(0 < Index && Index <= Hdr.NameCount);809 const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);810 uint64_t StringOffsetOffset =811 Offsets.StringOffsetsBase + SectionOffsetSize * (Index - 1);812 uint64_t EntryOffsetOffset =813 Offsets.EntryOffsetsBase + SectionOffsetSize * (Index - 1);814 const DWARFDataExtractor &AS = Section.AccelSection;815 816 uint64_t StringOffset =817 AS.getRelocatedValue(SectionOffsetSize, &StringOffsetOffset);818 uint64_t EntryOffset = AS.getUnsigned(&EntryOffsetOffset, SectionOffsetSize);819 EntryOffset += Offsets.EntriesBase;820 return {Section.StringSection, Index, StringOffset, EntryOffset};821}822 823uint32_t824DWARFDebugNames::NameIndex::getBucketArrayEntry(uint32_t Bucket) const {825 assert(Bucket < Hdr.BucketCount);826 uint64_t BucketOffset = Offsets.BucketsBase + 4 * Bucket;827 return Section.AccelSection.getU32(&BucketOffset);828}829 830uint32_t DWARFDebugNames::NameIndex::getHashArrayEntry(uint32_t Index) const {831 assert(0 < Index && Index <= Hdr.NameCount);832 uint64_t HashOffset = Offsets.HashesBase + 4 * (Index - 1);833 return Section.AccelSection.getU32(&HashOffset);834}835 836// Returns true if we should continue scanning for entries, false if this is the837// last (sentinel) entry). In case of a parsing error we also return false, as838// it's not possible to recover this entry list (but the other lists may still839// parse OK).840bool DWARFDebugNames::NameIndex::dumpEntry(ScopedPrinter &W,841 uint64_t *Offset) const {842 uint64_t EntryId = *Offset;843 auto EntryOr = getEntry(Offset);844 if (!EntryOr) {845 handleAllErrors(EntryOr.takeError(), [](const SentinelError &) {},846 [&W](const ErrorInfoBase &EI) { EI.log(W.startLine()); });847 return false;848 }849 850 DictScope EntryScope(W, ("Entry @ 0x" + Twine::utohexstr(EntryId)).str());851 EntryOr->dump(W);852 return true;853}854 855void DWARFDebugNames::NameIndex::dumpName(ScopedPrinter &W,856 const NameTableEntry &NTE,857 std::optional<uint32_t> Hash) const {858 DictScope NameScope(W, ("Name " + Twine(NTE.getIndex())).str());859 if (Hash)860 W.printHex("Hash", *Hash);861 862 W.startLine() << format("String: 0x%08" PRIx64, NTE.getStringOffset());863 W.getOStream() << " \"" << NTE.getString() << "\"\n";864 865 uint64_t EntryOffset = NTE.getEntryOffset();866 while (dumpEntry(W, &EntryOffset))867 /*empty*/;868}869 870void DWARFDebugNames::NameIndex::dumpCUs(ScopedPrinter &W) const {871 ListScope CUScope(W, "Compilation Unit offsets");872 for (uint32_t CU = 0; CU < Hdr.CompUnitCount; ++CU)873 W.startLine() << format("CU[%u]: 0x%08" PRIx64 "\n", CU, getCUOffset(CU));874}875 876void DWARFDebugNames::NameIndex::dumpLocalTUs(ScopedPrinter &W) const {877 if (Hdr.LocalTypeUnitCount == 0)878 return;879 880 ListScope TUScope(W, "Local Type Unit offsets");881 for (uint32_t TU = 0; TU < Hdr.LocalTypeUnitCount; ++TU)882 W.startLine() << format("LocalTU[%u]: 0x%08" PRIx64 "\n", TU,883 getLocalTUOffset(TU));884}885 886void DWARFDebugNames::NameIndex::dumpForeignTUs(ScopedPrinter &W) const {887 if (Hdr.ForeignTypeUnitCount == 0)888 return;889 890 ListScope TUScope(W, "Foreign Type Unit signatures");891 for (uint32_t TU = 0; TU < Hdr.ForeignTypeUnitCount; ++TU) {892 W.startLine() << format("ForeignTU[%u]: 0x%016" PRIx64 "\n", TU,893 getForeignTUSignature(TU));894 }895}896 897void DWARFDebugNames::NameIndex::dumpAbbreviations(ScopedPrinter &W) const {898 ListScope AbbrevsScope(W, "Abbreviations");899 std::vector<const Abbrev *> AbbrevsVect;900 for (const DWARFDebugNames::Abbrev &Abbr : Abbrevs)901 AbbrevsVect.push_back(&Abbr);902 llvm::sort(AbbrevsVect, [](const Abbrev *LHS, const Abbrev *RHS) {903 return LHS->AbbrevOffset < RHS->AbbrevOffset;904 });905 for (const DWARFDebugNames::Abbrev *Abbr : AbbrevsVect)906 Abbr->dump(W);907}908 909void DWARFDebugNames::NameIndex::dumpBucket(ScopedPrinter &W,910 uint32_t Bucket) const {911 ListScope BucketScope(W, ("Bucket " + Twine(Bucket)).str());912 uint32_t Index = getBucketArrayEntry(Bucket);913 if (Index == 0) {914 W.printString("EMPTY");915 return;916 }917 if (Index > Hdr.NameCount) {918 W.printString("Name index is invalid");919 return;920 }921 922 for (; Index <= Hdr.NameCount; ++Index) {923 uint32_t Hash = getHashArrayEntry(Index);924 if (Hash % Hdr.BucketCount != Bucket)925 break;926 927 dumpName(W, getNameTableEntry(Index), Hash);928 }929}930 931LLVM_DUMP_METHOD void DWARFDebugNames::NameIndex::dump(ScopedPrinter &W) const {932 DictScope UnitScope(W, ("Name Index @ 0x" + Twine::utohexstr(Base)).str());933 Hdr.dump(W);934 dumpCUs(W);935 dumpLocalTUs(W);936 dumpForeignTUs(W);937 dumpAbbreviations(W);938 939 if (Hdr.BucketCount > 0) {940 for (uint32_t Bucket = 0; Bucket < Hdr.BucketCount; ++Bucket)941 dumpBucket(W, Bucket);942 return;943 }944 945 W.startLine() << "Hash table not present\n";946 for (const NameTableEntry &NTE : *this)947 dumpName(W, NTE, std::nullopt);948}949 950Error DWARFDebugNames::extract() {951 uint64_t Offset = 0;952 while (AccelSection.isValidOffset(Offset)) {953 NameIndex Next(*this, Offset);954 if (Error E = Next.extract())955 return E;956 Offset = Next.getNextUnitOffset();957 NameIndices.push_back(std::move(Next));958 }959 return Error::success();960}961 962iterator_range<DWARFDebugNames::ValueIterator>963DWARFDebugNames::NameIndex::equal_range(StringRef Key) const {964 return make_range(ValueIterator(*this, Key), ValueIterator());965}966 967LLVM_DUMP_METHOD void DWARFDebugNames::dump(raw_ostream &OS) const {968 ScopedPrinter W(OS);969 for (const NameIndex &NI : NameIndices)970 NI.dump(W);971}972 973std::optional<uint64_t>974DWARFDebugNames::ValueIterator::findEntryOffsetInCurrentIndex() {975 const Header &Hdr = CurrentIndex->Hdr;976 if (Hdr.BucketCount == 0) {977 // No Hash Table, We need to search through all names in the Name Index.978 for (const NameTableEntry &NTE : *CurrentIndex) {979 if (NTE.sameNameAs(Key))980 return NTE.getEntryOffset();981 }982 return std::nullopt;983 }984 985 // The Name Index has a Hash Table, so use that to speed up the search.986 // Compute the Key Hash, if it has not been done already.987 if (!Hash)988 Hash = caseFoldingDjbHash(Key);989 uint32_t Bucket = *Hash % Hdr.BucketCount;990 uint32_t Index = CurrentIndex->getBucketArrayEntry(Bucket);991 if (Index == 0)992 return std::nullopt; // Empty bucket993 994 for (; Index <= Hdr.NameCount; ++Index) {995 uint32_t HashAtIndex = CurrentIndex->getHashArrayEntry(Index);996 if (HashAtIndex % Hdr.BucketCount != Bucket)997 return std::nullopt; // End of bucket998 // Only compare names if the hashes match.999 if (HashAtIndex != Hash)1000 continue;1001 1002 NameTableEntry NTE = CurrentIndex->getNameTableEntry(Index);1003 if (NTE.sameNameAs(Key))1004 return NTE.getEntryOffset();1005 }1006 return std::nullopt;1007}1008 1009bool DWARFDebugNames::ValueIterator::getEntryAtCurrentOffset() {1010 auto EntryOr = CurrentIndex->getEntry(&DataOffset);1011 if (!EntryOr) {1012 consumeError(EntryOr.takeError());1013 return false;1014 }1015 CurrentEntry = std::move(*EntryOr);1016 return true;1017}1018 1019bool DWARFDebugNames::ValueIterator::findInCurrentIndex() {1020 std::optional<uint64_t> Offset = findEntryOffsetInCurrentIndex();1021 if (!Offset)1022 return false;1023 DataOffset = *Offset;1024 return getEntryAtCurrentOffset();1025}1026 1027void DWARFDebugNames::ValueIterator::searchFromStartOfCurrentIndex() {1028 for (const NameIndex *End = CurrentIndex->Section.NameIndices.end();1029 CurrentIndex != End; ++CurrentIndex) {1030 if (findInCurrentIndex())1031 return;1032 }1033 setEnd();1034}1035 1036void DWARFDebugNames::ValueIterator::next() {1037 assert(CurrentIndex && "Incrementing an end() iterator?");1038 1039 // First try the next entry in the current Index.1040 if (getEntryAtCurrentOffset())1041 return;1042 1043 // If we're a local iterator or we have reached the last Index, we're done.1044 if (IsLocal || CurrentIndex == &CurrentIndex->Section.NameIndices.back()) {1045 setEnd();1046 return;1047 }1048 1049 // Otherwise, try the next index.1050 ++CurrentIndex;1051 searchFromStartOfCurrentIndex();1052}1053 1054DWARFDebugNames::ValueIterator::ValueIterator(const DWARFDebugNames &AccelTable,1055 StringRef Key)1056 : CurrentIndex(AccelTable.NameIndices.begin()), IsLocal(false),1057 Key(std::string(Key)) {1058 searchFromStartOfCurrentIndex();1059}1060 1061DWARFDebugNames::ValueIterator::ValueIterator(1062 const DWARFDebugNames::NameIndex &NI, StringRef Key)1063 : CurrentIndex(&NI), IsLocal(true), Key(std::string(Key)) {1064 if (!findInCurrentIndex())1065 setEnd();1066}1067 1068iterator_range<DWARFDebugNames::ValueIterator>1069DWARFDebugNames::equal_range(StringRef Key) const {1070 if (NameIndices.empty())1071 return make_range(ValueIterator(), ValueIterator());1072 return make_range(ValueIterator(*this, Key), ValueIterator());1073}1074 1075const DWARFDebugNames::NameIndex *1076DWARFDebugNames::getCUOrTUNameIndex(uint64_t UnitOffset) {1077 if (UnitOffsetToNameIndex.size() == 0 && NameIndices.size() > 0) {1078 for (const auto &NI : *this) {1079 for (uint32_t CU = 0; CU < NI.getCUCount(); ++CU)1080 UnitOffsetToNameIndex.try_emplace(NI.getCUOffset(CU), &NI);1081 for (uint32_t TU = 0; TU < NI.getLocalTUCount(); ++TU)1082 UnitOffsetToNameIndex.try_emplace(NI.getLocalTUOffset(TU), &NI);1083 }1084 }1085 return UnitOffsetToNameIndex.lookup(UnitOffset);1086}1087 1088static bool isObjCSelector(StringRef Name) {1089 return Name.size() > 2 && (Name[0] == '-' || Name[0] == '+') &&1090 (Name[1] == '[');1091}1092 1093std::optional<ObjCSelectorNames> llvm::getObjCNamesIfSelector(StringRef Name) {1094 if (!isObjCSelector(Name))1095 return std::nullopt;1096 // "-[Atom setMass:]"1097 StringRef ClassNameStart(Name.drop_front(2));1098 size_t FirstSpace = ClassNameStart.find(' ');1099 if (FirstSpace == StringRef::npos)1100 return std::nullopt;1101 1102 StringRef SelectorStart = ClassNameStart.drop_front(FirstSpace + 1);1103 if (!SelectorStart.size())1104 return std::nullopt;1105 1106 ObjCSelectorNames Ans;1107 Ans.ClassName = ClassNameStart.take_front(FirstSpace);1108 Ans.Selector = SelectorStart.drop_back(); // drop ']';1109 1110 // "-[Class(Category) selector :withArg ...]"1111 if (Ans.ClassName.back() == ')') {1112 size_t OpenParens = Ans.ClassName.find('(');1113 if (OpenParens != StringRef::npos) {1114 Ans.ClassNameNoCategory = Ans.ClassName.take_front(OpenParens);1115 1116 Ans.MethodNameNoCategory = Name.take_front(OpenParens + 2);1117 // FIXME: The missing space here may be a bug, but dsymutil-classic also1118 // does it this way.1119 append_range(*Ans.MethodNameNoCategory, SelectorStart);1120 }1121 }1122 return Ans;1123}1124 1125std::optional<StringRef> llvm::StripTemplateParameters(StringRef Name) {1126 // We are looking for template parameters to strip from Name. e.g.1127 //1128 // operator<<B>1129 //1130 // We look for > at the end but if it does not contain any < then we1131 // have something like operator>>. We check for the operator<=> case.1132 if (!Name.ends_with(">") || Name.count("<") == 0 || Name.ends_with("<=>"))1133 return {};1134 1135 // How many < until we have the start of the template parameters.1136 size_t NumLeftAnglesToSkip = 1;1137 1138 // If we have operator<=> then we need to skip its < as well.1139 NumLeftAnglesToSkip += Name.count("<=>");1140 1141 size_t RightAngleCount = Name.count('>');1142 size_t LeftAngleCount = Name.count('<');1143 1144 // If we have more < than > we have operator< or operator<<1145 // we to account for their < as well.1146 if (LeftAngleCount > RightAngleCount)1147 NumLeftAnglesToSkip += LeftAngleCount - RightAngleCount;1148 1149 size_t StartOfTemplate = 0;1150 while (NumLeftAnglesToSkip--)1151 StartOfTemplate = Name.find('<', StartOfTemplate) + 1;1152 1153 return Name.substr(0, StartOfTemplate - 1);1154}1155