LCOV - code coverage report
Current view: top level - lib/DebugInfo/DWARF - DWARFAcceleratorTable.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 438 474 92.4 %
Date: 2018-10-20 13:21:21 Functions: 60 66 90.9 %
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/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             : }

Generated by: LCOV version 1.13