llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp

   1 //===- DWARFAcceleratorTable.cpp ------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h"
  10
  11 #include "llvm/ADT/SmallVector.h"
  12 #include "llvm/BinaryFormat/Dwarf.h"
  13 #include "llvm/DebugInfo/DWARF/DWARFRelocMap.h"
  14 #include "llvm/Support/Compiler.h"
  15 #include "llvm/Support/DJB.h"
  16 #include "llvm/Support/Errc.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 Error AppleAcceleratorTable::extract() {
  45   uint64_t Offset = 0;
  46
  47   // Check that we can at least read the header.
  48   if (!AccelSection.isValidOffset(offsetof(Header, HeaderDataLength) + 4))
  49     return createStringError(errc::illegal_byte_sequence,
  50                              "Section too small: cannot read header.");
  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 createStringError(
  66         errc::illegal_byte_sequence,
  67         "Section too small: cannot read buckets and hashes.");
  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<uint64_t, dwarf::Tag>
 115 AppleAcceleratorTable::readAtoms(uint64_t *HashDataOffset) {
 116   uint64_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                                      uint64_t *DataOffset) const {
 167   dwarf::FormParams FormParams = {Hdr.Version, 0, dwarf::DwarfFormat::DWARF32};
 168   uint64_t NameOffset = *DataOffset;
 169   if (!AccelSection.isValidOffsetForDataOfSize(*DataOffset, 4)) {
 170     W.printString("Incorrectly terminated list.");
 171     return false;
 172   }
 173   uint64_t 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%08" PRIx64, 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   uint64_t Offset = sizeof(Hdr) + Hdr.HeaderDataLength;
 227   uint64_t HashesBase = Offset + Hdr.BucketCount * 4;
 228   uint64_t 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       uint64_t HashOffset = HashesBase + HashIdx*4;
 241       uint64_t OffsetsOffset = OffsetsBase + HashIdx*4;
 242       uint32_t Hash = AccelSection.getU32(&HashOffset);
 243
 244       if (Hash % Hdr.BucketCount != Bucket)
 245         break;
 246
 247       uint64_t 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, uint64_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 (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, uint64_t 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   uint64_t BucketBase = sizeof(Hdr) + Hdr.HeaderDataLength;
 337   uint64_t HashesBase = BucketBase + Hdr.BucketCount * 4;
 338   uint64_t OffsetsBase = HashesBase + Hdr.HashCount * 4;
 339
 340   uint64_t 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     uint64_t HashOffset = HashesBase + HashIdx * 4;
 346     uint64_t 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     uint64_t DataOffset = AccelSection.getU32(&OffsetsOffset);
 354     uint64_t 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.printString("Format", dwarf::FormatString(Format));
 369   W.printNumber("Version", Version);
 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 Error DWARFDebugNames::Header::extract(const DWARFDataExtractor &AS,
 380                                              uint64_t *Offset) {
 381   auto HeaderError = [Offset = *Offset](Error E) {
 382     return createStringError(errc::illegal_byte_sequence,
 383                              "parsing .debug_names header at 0x%" PRIx64 ": %s",
 384                              Offset, toString(std::move(E)).c_str());
 385   };
 386
 387   DataExtractor::Cursor C(*Offset);
 388   std::tie(UnitLength, Format) = AS.getInitialLength(C);
 389
 390   Version = AS.getU16(C);
 391   AS.skip(C, 2); // padding
 392   CompUnitCount = AS.getU32(C);
 393   LocalTypeUnitCount = AS.getU32(C);
 394   ForeignTypeUnitCount = AS.getU32(C);
 395   BucketCount = AS.getU32(C);
 396   NameCount = AS.getU32(C);
 397   AbbrevTableSize = AS.getU32(C);
 398   AugmentationStringSize = alignTo(AS.getU32(C), 4);
 399
 400   if (!C)
 401     return HeaderError(C.takeError());
 402
 403   if (!AS.isValidOffsetForDataOfSize(C.tell(), AugmentationStringSize))
 404     return HeaderError(createStringError(errc::illegal_byte_sequence,
 405                                          "cannot read header augmentation"));
 406   AugmentationString.resize(AugmentationStringSize);
 407   AS.getU8(C, reinterpret_cast<uint8_t *>(AugmentationString.data()),
 408            AugmentationStringSize);
 409   *Offset = C.tell();
 410   return C.takeError();
 411 }
 412
 413 void DWARFDebugNames::Abbrev::dump(ScopedPrinter &W) const {
 414   DictScope AbbrevScope(W, ("Abbreviation 0x" + Twine::utohexstr(Code)).str());
 415   W.startLine() << formatv("Tag: {0}\n", Tag);
 416
 417   for (const auto &Attr : Attributes)
 418     W.startLine() << formatv("{0}: {1}\n", Attr.Index, Attr.Form);
 419 }
 420
 421 static constexpr DWARFDebugNames::AttributeEncoding sentinelAttrEnc() {
 422   return {dwarf::Index(0), dwarf::Form(0)};
 423 }
 424
 425 static bool isSentinel(const DWARFDebugNames::AttributeEncoding &AE) {
 426   return AE == sentinelAttrEnc();
 427 }
 428
 429 static DWARFDebugNames::Abbrev sentinelAbbrev() {
 430   return DWARFDebugNames::Abbrev(0, dwarf::Tag(0), {});
 431 }
 432
 433 static bool isSentinel(const DWARFDebugNames::Abbrev &Abbr) {
 434   return Abbr.Code == 0;
 435 }
 436
 437 DWARFDebugNames::Abbrev DWARFDebugNames::AbbrevMapInfo::getEmptyKey() {
 438   return sentinelAbbrev();
 439 }
 440
 441 DWARFDebugNames::Abbrev DWARFDebugNames::AbbrevMapInfo::getTombstoneKey() {
 442   return DWARFDebugNames::Abbrev(~0, dwarf::Tag(0), {});
 443 }
 444
 445 Expected<DWARFDebugNames::AttributeEncoding>
 446 DWARFDebugNames::NameIndex::extractAttributeEncoding(uint64_t *Offset) {
 447   if (*Offset >= EntriesBase) {
 448     return createStringError(errc::illegal_byte_sequence,
 449                              "Incorrectly terminated abbreviation table.");
 450   }
 451
 452   uint32_t Index = Section.AccelSection.getULEB128(Offset);
 453   uint32_t Form = Section.AccelSection.getULEB128(Offset);
 454   return AttributeEncoding(dwarf::Index(Index), dwarf::Form(Form));
 455 }
 456
 457 Expected<std::vector<DWARFDebugNames::AttributeEncoding>>
 458 DWARFDebugNames::NameIndex::extractAttributeEncodings(uint64_t *Offset) {
 459   std::vector<AttributeEncoding> Result;
 460   for (;;) {
 461     auto AttrEncOr = extractAttributeEncoding(Offset);
 462     if (!AttrEncOr)
 463       return AttrEncOr.takeError();
 464     if (isSentinel(*AttrEncOr))
 465       return std::move(Result);
 466
 467     Result.emplace_back(*AttrEncOr);
 468   }
 469 }
 470
 471 Expected<DWARFDebugNames::Abbrev>
 472 DWARFDebugNames::NameIndex::extractAbbrev(uint64_t *Offset) {
 473   if (*Offset >= EntriesBase) {
 474     return createStringError(errc::illegal_byte_sequence,
 475                              "Incorrectly terminated abbreviation table.");
 476   }
 477
 478   uint32_t Code = Section.AccelSection.getULEB128(Offset);
 479   if (Code == 0)
 480     return sentinelAbbrev();
 481
 482   uint32_t Tag = Section.AccelSection.getULEB128(Offset);
 483   auto AttrEncOr = extractAttributeEncodings(Offset);
 484   if (!AttrEncOr)
 485     return AttrEncOr.takeError();
 486   return Abbrev(Code, dwarf::Tag(Tag), std::move(*AttrEncOr));
 487 }
 488
 489 Error DWARFDebugNames::NameIndex::extract() {
 490   const DWARFDataExtractor &AS = Section.AccelSection;
 491   uint64_t Offset = Base;
 492   if (Error E = Hdr.extract(AS, &Offset))
 493     return E;
 494
 495   const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);
 496   CUsBase = Offset;
 497   Offset += Hdr.CompUnitCount * SectionOffsetSize;
 498   Offset += Hdr.LocalTypeUnitCount * SectionOffsetSize;
 499   Offset += Hdr.ForeignTypeUnitCount * 8;
 500   BucketsBase = Offset;
 501   Offset += Hdr.BucketCount * 4;
 502   HashesBase = Offset;
 503   if (Hdr.BucketCount > 0)
 504     Offset += Hdr.NameCount * 4;
 505   StringOffsetsBase = Offset;
 506   Offset += Hdr.NameCount * SectionOffsetSize;
 507   EntryOffsetsBase = Offset;
 508   Offset += Hdr.NameCount * SectionOffsetSize;
 509
 510   if (!AS.isValidOffsetForDataOfSize(Offset, Hdr.AbbrevTableSize))
 511     return createStringError(errc::illegal_byte_sequence,
 512                              "Section too small: cannot read abbreviations.");
 513
 514   EntriesBase = Offset + Hdr.AbbrevTableSize;
 515
 516   for (;;) {
 517     auto AbbrevOr = extractAbbrev(&Offset);
 518     if (!AbbrevOr)
 519       return AbbrevOr.takeError();
 520     if (isSentinel(*AbbrevOr))
 521       return Error::success();
 522
 523     if (!Abbrevs.insert(std::move(*AbbrevOr)).second)
 524       return createStringError(errc::invalid_argument,
 525                                "Duplicate abbreviation code.");
 526   }
 527 }
 528
 529 DWARFDebugNames::Entry::Entry(const NameIndex &NameIdx, const Abbrev &Abbr)
 530     : NameIdx(&NameIdx), Abbr(&Abbr) {
 531   // This merely creates form values. It is up to the caller
 532   // (NameIndex::getEntry) to populate them.
 533   Values.reserve(Abbr.Attributes.size());
 534   for (const auto &Attr : Abbr.Attributes)
 535     Values.emplace_back(Attr.Form);
 536 }
 537
 538 Optional<DWARFFormValue>
 539 DWARFDebugNames::Entry::lookup(dwarf::Index Index) const {
 540   assert(Abbr->Attributes.size() == Values.size());
 541   for (auto Tuple : zip_first(Abbr->Attributes, Values)) {
 542     if (std::get<0>(Tuple).Index == Index)
 543       return std::get<1>(Tuple);
 544   }
 545   return None;
 546 }
 547
 548 Optional<uint64_t> DWARFDebugNames::Entry::getDIEUnitOffset() const {
 549   if (Optional<DWARFFormValue> Off = lookup(dwarf::DW_IDX_die_offset))
 550     return Off->getAsReferenceUVal();
 551   return None;
 552 }
 553
 554 Optional<uint64_t> DWARFDebugNames::Entry::getCUIndex() const {
 555   if (Optional<DWARFFormValue> Off = lookup(dwarf::DW_IDX_compile_unit))
 556     return Off->getAsUnsignedConstant();
 557   // In a per-CU index, the entries without a DW_IDX_compile_unit attribute
 558   // implicitly refer to the single CU.
 559   if (NameIdx->getCUCount() == 1)
 560     return 0;
 561   return None;
 562 }
 563
 564 Optional<uint64_t> DWARFDebugNames::Entry::getCUOffset() const {
 565   Optional<uint64_t> Index = getCUIndex();
 566   if (!Index || *Index >= NameIdx->getCUCount())
 567     return None;
 568   return NameIdx->getCUOffset(*Index);
 569 }
 570
 571 void DWARFDebugNames::Entry::dump(ScopedPrinter &W) const {
 572   W.printHex("Abbrev", Abbr->Code);
 573   W.startLine() << formatv("Tag: {0}\n", Abbr->Tag);
 574   assert(Abbr->Attributes.size() == Values.size());
 575   for (auto Tuple : zip_first(Abbr->Attributes, Values)) {
 576     W.startLine() << formatv("{0}: ", std::get<0>(Tuple).Index);
 577     std::get<1>(Tuple).dump(W.getOStream());
 578     W.getOStream() << '\n';
 579   }
 580 }
 581
 582 char DWARFDebugNames::SentinelError::ID;
 583 std::error_code DWARFDebugNames::SentinelError::convertToErrorCode() const {
 584   return inconvertibleErrorCode();
 585 }
 586
 587 uint64_t DWARFDebugNames::NameIndex::getCUOffset(uint32_t CU) const {
 588   assert(CU < Hdr.CompUnitCount);
 589   const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);
 590   uint64_t Offset = CUsBase + SectionOffsetSize * CU;
 591   return Section.AccelSection.getRelocatedValue(SectionOffsetSize, &Offset);
 592 }
 593
 594 uint64_t DWARFDebugNames::NameIndex::getLocalTUOffset(uint32_t TU) const {
 595   assert(TU < Hdr.LocalTypeUnitCount);
 596   const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);
 597   uint64_t Offset = CUsBase + SectionOffsetSize * (Hdr.CompUnitCount + TU);
 598   return Section.AccelSection.getRelocatedValue(SectionOffsetSize, &Offset);
 599 }
 600
 601 uint64_t DWARFDebugNames::NameIndex::getForeignTUSignature(uint32_t TU) const {
 602   assert(TU < Hdr.ForeignTypeUnitCount);
 603   const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);
 604   uint64_t Offset =
 605       CUsBase +
 606       SectionOffsetSize * (Hdr.CompUnitCount + Hdr.LocalTypeUnitCount) + 8 * TU;
 607   return Section.AccelSection.getU64(&Offset);
 608 }
 609
 610 Expected<DWARFDebugNames::Entry>
 611 DWARFDebugNames::NameIndex::getEntry(uint64_t *Offset) const {
 612   const DWARFDataExtractor &AS = Section.AccelSection;
 613   if (!AS.isValidOffset(*Offset))
 614     return createStringError(errc::illegal_byte_sequence,
 615                              "Incorrectly terminated entry list.");
 616
 617   uint32_t AbbrevCode = AS.getULEB128(Offset);
 618   if (AbbrevCode == 0)
 619     return make_error<SentinelError>();
 620
 621   const auto AbbrevIt = Abbrevs.find_as(AbbrevCode);
 622   if (AbbrevIt == Abbrevs.end())
 623     return createStringError(errc::invalid_argument, "Invalid abbreviation.");
 624
 625   Entry E(*this, *AbbrevIt);
 626
 627   dwarf::FormParams FormParams = {Hdr.Version, 0, Hdr.Format};
 628   for (auto &Value : E.Values) {
 629     if (!Value.extractValue(AS, Offset, FormParams))
 630       return createStringError(errc::io_error,
 631                                "Error extracting index attribute values.");
 632   }
 633   return std::move(E);
 634 }
 635
 636 DWARFDebugNames::NameTableEntry
 637 DWARFDebugNames::NameIndex::getNameTableEntry(uint32_t Index) const {
 638   assert(0 < Index && Index <= Hdr.NameCount);
 639   const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);
 640   uint64_t StringOffsetOffset =
 641       StringOffsetsBase + SectionOffsetSize * (Index - 1);
 642   uint64_t EntryOffsetOffset =
 643       EntryOffsetsBase + SectionOffsetSize * (Index - 1);
 644   const DWARFDataExtractor &AS = Section.AccelSection;
 645
 646   uint64_t StringOffset =
 647       AS.getRelocatedValue(SectionOffsetSize, &StringOffsetOffset);
 648   uint64_t EntryOffset = AS.getUnsigned(&EntryOffsetOffset, SectionOffsetSize);
 649   EntryOffset += EntriesBase;
 650   return {Section.StringSection, Index, StringOffset, EntryOffset};
 651 }
 652
 653 uint32_t
 654 DWARFDebugNames::NameIndex::getBucketArrayEntry(uint32_t Bucket) const {
 655   assert(Bucket < Hdr.BucketCount);
 656   uint64_t BucketOffset = BucketsBase + 4 * Bucket;
 657   return Section.AccelSection.getU32(&BucketOffset);
 658 }
 659
 660 uint32_t DWARFDebugNames::NameIndex::getHashArrayEntry(uint32_t Index) const {
 661   assert(0 < Index && Index <= Hdr.NameCount);
 662   uint64_t HashOffset = HashesBase + 4 * (Index - 1);
 663   return Section.AccelSection.getU32(&HashOffset);
 664 }
 665
 666 // Returns true if we should continue scanning for entries, false if this is the
 667 // last (sentinel) entry). In case of a parsing error we also return false, as
 668 // it's not possible to recover this entry list (but the other lists may still
 669 // parse OK).
 670 bool DWARFDebugNames::NameIndex::dumpEntry(ScopedPrinter &W,
 671                                            uint64_t *Offset) const {
 672   uint64_t EntryId = *Offset;
 673   auto EntryOr = getEntry(Offset);
 674   if (!EntryOr) {
 675     handleAllErrors(EntryOr.takeError(), [](const SentinelError &) {},
 676                     [&W](const ErrorInfoBase &EI) { EI.log(W.startLine()); });
 677     return false;
 678   }
 679
 680   DictScope EntryScope(W, ("Entry @ 0x" + Twine::utohexstr(EntryId)).str());
 681   EntryOr->dump(W);
 682   return true;
 683 }
 684
 685 void DWARFDebugNames::NameIndex::dumpName(ScopedPrinter &W,
 686                                           const NameTableEntry &NTE,
 687                                           Optional<uint32_t> Hash) const {
 688   DictScope NameScope(W, ("Name " + Twine(NTE.getIndex())).str());
 689   if (Hash)
 690     W.printHex("Hash", *Hash);
 691
 692   W.startLine() << format("String: 0x%08" PRIx64, NTE.getStringOffset());
 693   W.getOStream() << " \"" << NTE.getString() << "\"\n";
 694
 695   uint64_t EntryOffset = NTE.getEntryOffset();
 696   while (dumpEntry(W, &EntryOffset))
 697     /*empty*/;
 698 }
 699
 700 void DWARFDebugNames::NameIndex::dumpCUs(ScopedPrinter &W) const {
 701   ListScope CUScope(W, "Compilation Unit offsets");
 702   for (uint32_t CU = 0; CU < Hdr.CompUnitCount; ++CU)
 703     W.startLine() << format("CU[%u]: 0x%08" PRIx64 "\n", CU, getCUOffset(CU));
 704 }
 705
 706 void DWARFDebugNames::NameIndex::dumpLocalTUs(ScopedPrinter &W) const {
 707   if (Hdr.LocalTypeUnitCount == 0)
 708     return;
 709
 710   ListScope TUScope(W, "Local Type Unit offsets");
 711   for (uint32_t TU = 0; TU < Hdr.LocalTypeUnitCount; ++TU)
 712     W.startLine() << format("LocalTU[%u]: 0x%08" PRIx64 "\n", TU,
 713                             getLocalTUOffset(TU));
 714 }
 715
 716 void DWARFDebugNames::NameIndex::dumpForeignTUs(ScopedPrinter &W) const {
 717   if (Hdr.ForeignTypeUnitCount == 0)
 718     return;
 719
 720   ListScope TUScope(W, "Foreign Type Unit signatures");
 721   for (uint32_t TU = 0; TU < Hdr.ForeignTypeUnitCount; ++TU) {
 722     W.startLine() << format("ForeignTU[%u]: 0x%016" PRIx64 "\n", TU,
 723                             getForeignTUSignature(TU));
 724   }
 725 }
 726
 727 void DWARFDebugNames::NameIndex::dumpAbbreviations(ScopedPrinter &W) const {
 728   ListScope AbbrevsScope(W, "Abbreviations");
 729   for (const auto &Abbr : Abbrevs)
 730     Abbr.dump(W);
 731 }
 732
 733 void DWARFDebugNames::NameIndex::dumpBucket(ScopedPrinter &W,
 734                                             uint32_t Bucket) const {
 735   ListScope BucketScope(W, ("Bucket " + Twine(Bucket)).str());
 736   uint32_t Index = getBucketArrayEntry(Bucket);
 737   if (Index == 0) {
 738     W.printString("EMPTY");
 739     return;
 740   }
 741   if (Index > Hdr.NameCount) {
 742     W.printString("Name index is invalid");
 743     return;
 744   }
 745
 746   for (; Index <= Hdr.NameCount; ++Index) {
 747     uint32_t Hash = getHashArrayEntry(Index);
 748     if (Hash % Hdr.BucketCount != Bucket)
 749       break;
 750
 751     dumpName(W, getNameTableEntry(Index), Hash);
 752   }
 753 }
 754
 755 LLVM_DUMP_METHOD void DWARFDebugNames::NameIndex::dump(ScopedPrinter &W) const {
 756   DictScope UnitScope(W, ("Name Index @ 0x" + Twine::utohexstr(Base)).str());
 757   Hdr.dump(W);
 758   dumpCUs(W);
 759   dumpLocalTUs(W);
 760   dumpForeignTUs(W);
 761   dumpAbbreviations(W);
 762
 763   if (Hdr.BucketCount > 0) {
 764     for (uint32_t Bucket = 0; Bucket < Hdr.BucketCount; ++Bucket)
 765       dumpBucket(W, Bucket);
 766     return;
 767   }
 768
 769   W.startLine() << "Hash table not present\n";
 770   for (NameTableEntry NTE : *this)
 771     dumpName(W, NTE, None);
 772 }
 773
 774 Error DWARFDebugNames::extract() {
 775   uint64_t Offset = 0;
 776   while (AccelSection.isValidOffset(Offset)) {
 777     NameIndex Next(*this, Offset);
 778     if (Error E = Next.extract())
 779       return E;
 780     Offset = Next.getNextUnitOffset();
 781     NameIndices.push_back(std::move(Next));
 782   }
 783   return Error::success();
 784 }
 785
 786 iterator_range<DWARFDebugNames::ValueIterator>
 787 DWARFDebugNames::NameIndex::equal_range(StringRef Key) const {
 788   return make_range(ValueIterator(*this, Key), ValueIterator());
 789 }
 790
 791 LLVM_DUMP_METHOD void DWARFDebugNames::dump(raw_ostream &OS) const {
 792   ScopedPrinter W(OS);
 793   for (const NameIndex &NI : NameIndices)
 794     NI.dump(W);
 795 }
 796
 797 Optional<uint64_t>
 798 DWARFDebugNames::ValueIterator::findEntryOffsetInCurrentIndex() {
 799   const Header &Hdr = CurrentIndex->Hdr;
 800   if (Hdr.BucketCount == 0) {
 801     // No Hash Table, We need to search through all names in the Name Index.
 802     for (NameTableEntry NTE : *CurrentIndex) {
 803       if (NTE.getString() == Key)
 804         return NTE.getEntryOffset();
 805     }
 806     return None;
 807   }
 808
 809   // The Name Index has a Hash Table, so use that to speed up the search.
 810   // Compute the Key Hash, if it has not been done already.
 811   if (!Hash)
 812     Hash = caseFoldingDjbHash(Key);
 813   uint32_t Bucket = *Hash % Hdr.BucketCount;
 814   uint32_t Index = CurrentIndex->getBucketArrayEntry(Bucket);
 815   if (Index == 0)
 816     return None; // Empty bucket
 817
 818   for (; Index <= Hdr.NameCount; ++Index) {
 819     uint32_t Hash = CurrentIndex->getHashArrayEntry(Index);
 820     if (Hash % Hdr.BucketCount != Bucket)
 821       return None; // End of bucket
 822
 823     NameTableEntry NTE = CurrentIndex->getNameTableEntry(Index);
 824     if (NTE.getString() == Key)
 825       return NTE.getEntryOffset();
 826   }
 827   return None;
 828 }
 829
 830 bool DWARFDebugNames::ValueIterator::getEntryAtCurrentOffset() {
 831   auto EntryOr = CurrentIndex->getEntry(&DataOffset);
 832   if (!EntryOr) {
 833     consumeError(EntryOr.takeError());
 834     return false;
 835   }
 836   CurrentEntry = std::move(*EntryOr);
 837   return true;
 838 }
 839
 840 bool DWARFDebugNames::ValueIterator::findInCurrentIndex() {
 841   Optional<uint64_t> Offset = findEntryOffsetInCurrentIndex();
 842   if (!Offset)
 843     return false;
 844   DataOffset = *Offset;
 845   return getEntryAtCurrentOffset();
 846 }
 847
 848 void DWARFDebugNames::ValueIterator::searchFromStartOfCurrentIndex() {
 849   for (const NameIndex *End = CurrentIndex->Section.NameIndices.end();
 850        CurrentIndex != End; ++CurrentIndex) {
 851     if (findInCurrentIndex())
 852       return;
 853   }
 854   setEnd();
 855 }
 856
 857 void DWARFDebugNames::ValueIterator::next() {
 858   assert(CurrentIndex && "Incrementing an end() iterator?");
 859
 860   // First try the next entry in the current Index.
 861   if (getEntryAtCurrentOffset())
 862     return;
 863
 864   // If we're a local iterator or we have reached the last Index, we're done.
 865   if (IsLocal || CurrentIndex == &CurrentIndex->Section.NameIndices.back()) {
 866     setEnd();
 867     return;
 868   }
 869
 870   // Otherwise, try the next index.
 871   ++CurrentIndex;
 872   searchFromStartOfCurrentIndex();
 873 }
 874
 875 DWARFDebugNames::ValueIterator::ValueIterator(const DWARFDebugNames &AccelTable,
 876                                               StringRef Key)
 877     : CurrentIndex(AccelTable.NameIndices.begin()), IsLocal(false),
 878       Key(std::string(Key)) {
 879   searchFromStartOfCurrentIndex();
 880 }
 881
 882 DWARFDebugNames::ValueIterator::ValueIterator(
 883     const DWARFDebugNames::NameIndex &NI, StringRef Key)
 884     : CurrentIndex(&NI), IsLocal(true), Key(std::string(Key)) {
 885   if (!findInCurrentIndex())
 886     setEnd();
 887 }
 888
 889 iterator_range<DWARFDebugNames::ValueIterator>
 890 DWARFDebugNames::equal_range(StringRef Key) const {
 891   if (NameIndices.empty())
 892     return make_range(ValueIterator(), ValueIterator());
 893   return make_range(ValueIterator(*this, Key), ValueIterator());
 894 }
 895
 896 const DWARFDebugNames::NameIndex *
 897 DWARFDebugNames::getCUNameIndex(uint64_t CUOffset) {
 898   if (CUToNameIndex.size() == 0 && NameIndices.size() > 0) {
 899     for (const auto &NI : *this) {
 900       for (uint32_t CU = 0; CU < NI.getCUCount(); ++CU)
 901         CUToNameIndex.try_emplace(NI.getCUOffset(CU), &NI);
 902     }
 903   }
 904   return CUToNameIndex.lookup(CUOffset);
 905 }