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