LCOV - code coverage report
Current view: top level - lib/DebugInfo/DWARF - DWARFAcceleratorTable.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 432 466 92.7 %
Date: 2018-06-17 00:07:59 Functions: 60 65 92.3 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13