llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp

   1 //===- DWARFUnit.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/DWARFUnit.h"
  10 #include "llvm/ADT/SmallString.h"
  11 #include "llvm/ADT/StringRef.h"
  12 #include "llvm/DebugInfo/DWARF/DWARFAbbreviationDeclaration.h"
  13 #include "llvm/DebugInfo/DWARF/DWARFCompileUnit.h"
  14 #include "llvm/DebugInfo/DWARF/DWARFContext.h"
  15 #include "llvm/DebugInfo/DWARF/DWARFDebugAbbrev.h"
  16 #include "llvm/DebugInfo/DWARF/DWARFDebugInfoEntry.h"
  17 #include "llvm/DebugInfo/DWARF/DWARFDebugRnglists.h"
  18 #include "llvm/DebugInfo/DWARF/DWARFDie.h"
  19 #include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
  20 #include "llvm/DebugInfo/DWARF/DWARFTypeUnit.h"
  21 #include "llvm/Support/DataExtractor.h"
  22 #include "llvm/Support/Errc.h"
  23 #include "llvm/Support/Path.h"
  24 #include <algorithm>
  25 #include <cassert>
  26 #include <cstddef>
  27 #include <cstdint>
  28 #include <cstdio>
  29 #include <utility>
  30 #include <vector>
  31
  32 using namespace llvm;
  33 using namespace dwarf;
  34
  35 void DWARFUnitVector::addUnitsForSection(DWARFContext &C,
  36                                          const DWARFSection &Section,
  37                                          DWARFSectionKind SectionKind) {
  38   const DWARFObject &D = C.getDWARFObj();
  39   addUnitsImpl(C, D, Section, C.getDebugAbbrev(), &D.getRangesSection(),
  40                &D.getLocSection(), D.getStrSection(),
  41                D.getStrOffsetsSection(), &D.getAddrSection(),
  42                D.getLineSection(), D.isLittleEndian(), false, false,
  43                SectionKind);
  44 }
  45
  46 void DWARFUnitVector::addUnitsForDWOSection(DWARFContext &C,
  47                                             const DWARFSection &DWOSection,
  48                                             DWARFSectionKind SectionKind,
  49                                             bool Lazy) {
  50   const DWARFObject &D = C.getDWARFObj();
  51   addUnitsImpl(C, D, DWOSection, C.getDebugAbbrevDWO(), &D.getRangesDWOSection(),
  52                &D.getLocDWOSection(), D.getStrDWOSection(),
  53                D.getStrOffsetsDWOSection(), &D.getAddrSection(),
  54                D.getLineDWOSection(), C.isLittleEndian(), true, Lazy,
  55                SectionKind);
  56 }
  57
  58 void DWARFUnitVector::addUnitsImpl(
  59     DWARFContext &Context, const DWARFObject &Obj, const DWARFSection &Section,
  60     const DWARFDebugAbbrev *DA, const DWARFSection *RS,
  61     const DWARFSection *LocSection, StringRef SS, const DWARFSection &SOS,
  62     const DWARFSection *AOS, const DWARFSection &LS, bool LE, bool IsDWO,
  63     bool Lazy, DWARFSectionKind SectionKind) {
  64   DWARFDataExtractor Data(Obj, Section, LE, 0);
  65   // Lazy initialization of Parser, now that we have all section info.
  66   if (!Parser) {
  67     Parser = [=, &Context, &Obj, &Section, &SOS,
  68               &LS](uint64_t Offset, DWARFSectionKind SectionKind,
  69                    const DWARFSection *CurSection,
  70                    const DWARFUnitIndex::Entry *IndexEntry)
  71         -> std::unique_ptr<DWARFUnit> {
  72       const DWARFSection &InfoSection = CurSection ? *CurSection : Section;
  73       DWARFDataExtractor Data(Obj, InfoSection, LE, 0);
  74       if (!Data.isValidOffset(Offset))
  75         return nullptr;
  76       DWARFUnitHeader Header;
  77       if (!Header.extract(Context, Data, &Offset, SectionKind))
  78         return nullptr;
  79       if (!IndexEntry && IsDWO) {
  80         const DWARFUnitIndex &Index = getDWARFUnitIndex(
  81             Context, Header.isTypeUnit() ? DW_SECT_EXT_TYPES : DW_SECT_INFO);
  82         IndexEntry = Index.getFromOffset(Header.getOffset());
  83       }
  84       if (IndexEntry && !Header.applyIndexEntry(IndexEntry))
  85         return nullptr;
  86       std::unique_ptr<DWARFUnit> U;
  87       if (Header.isTypeUnit())
  88         U = std::make_unique<DWARFTypeUnit>(Context, InfoSection, Header, DA,
  89                                              RS, LocSection, SS, SOS, AOS, LS,
  90                                              LE, IsDWO, *this);
  91       else
  92         U = std::make_unique<DWARFCompileUnit>(Context, InfoSection, Header,
  93                                                 DA, RS, LocSection, SS, SOS,
  94                                                 AOS, LS, LE, IsDWO, *this);
  95       return U;
  96     };
  97   }
  98   if (Lazy)
  99     return;
 100   // Find a reasonable insertion point within the vector.  We skip over
 101   // (a) units from a different section, (b) units from the same section
 102   // but with lower offset-within-section.  This keeps units in order
 103   // within a section, although not necessarily within the object file,
 104   // even if we do lazy parsing.
 105   auto I = this->begin();
 106   uint64_t Offset = 0;
 107   while (Data.isValidOffset(Offset)) {
 108     if (I != this->end() &&
 109         (&(*I)->getInfoSection() != &Section || (*I)->getOffset() == Offset)) {
 110       ++I;
 111       continue;
 112     }
 113     auto U = Parser(Offset, SectionKind, &Section, nullptr);
 114     // If parsing failed, we're done with this section.
 115     if (!U)
 116       break;
 117     Offset = U->getNextUnitOffset();
 118     I = std::next(this->insert(I, std::move(U)));
 119   }
 120 }
 121
 122 DWARFUnit *DWARFUnitVector::addUnit(std::unique_ptr<DWARFUnit> Unit) {
 123   auto I = std::upper_bound(begin(), end(), Unit,
 124                             [](const std::unique_ptr<DWARFUnit> &LHS,
 125                                const std::unique_ptr<DWARFUnit> &RHS) {
 126                               return LHS->getOffset() < RHS->getOffset();
 127                             });
 128   return this->insert(I, std::move(Unit))->get();
 129 }
 130
 131 DWARFUnit *DWARFUnitVector::getUnitForOffset(uint64_t Offset) const {
 132   auto end = begin() + getNumInfoUnits();
 133   auto *CU =
 134       std::upper_bound(begin(), end, Offset,
 135                        [](uint64_t LHS, const std::unique_ptr<DWARFUnit> &RHS) {
 136                          return LHS < RHS->getNextUnitOffset();
 137                        });
 138   if (CU != end && (*CU)->getOffset() <= Offset)
 139     return CU->get();
 140   return nullptr;
 141 }
 142
 143 DWARFUnit *
 144 DWARFUnitVector::getUnitForIndexEntry(const DWARFUnitIndex::Entry &E) {
 145   const auto *CUOff = E.getContribution(DW_SECT_INFO);
 146   if (!CUOff)
 147     return nullptr;
 148
 149   auto Offset = CUOff->Offset;
 150   auto end = begin() + getNumInfoUnits();
 151
 152   auto *CU =
 153       std::upper_bound(begin(), end, CUOff->Offset,
 154                        [](uint64_t LHS, const std::unique_ptr<DWARFUnit> &RHS) {
 155                          return LHS < RHS->getNextUnitOffset();
 156                        });
 157   if (CU != end && (*CU)->getOffset() <= Offset)
 158     return CU->get();
 159
 160   if (!Parser)
 161     return nullptr;
 162
 163   auto U = Parser(Offset, DW_SECT_INFO, nullptr, &E);
 164   if (!U)
 165     U = nullptr;
 166
 167   auto *NewCU = U.get();
 168   this->insert(CU, std::move(U));
 169   ++NumInfoUnits;
 170   return NewCU;
 171 }
 172
 173 DWARFUnit::DWARFUnit(DWARFContext &DC, const DWARFSection &Section,
 174                      const DWARFUnitHeader &Header, const DWARFDebugAbbrev *DA,
 175                      const DWARFSection *RS, const DWARFSection *LocSection,
 176                      StringRef SS, const DWARFSection &SOS,
 177                      const DWARFSection *AOS, const DWARFSection &LS, bool LE,
 178                      bool IsDWO, const DWARFUnitVector &UnitVector)
 179     : Context(DC), InfoSection(Section), Header(Header), Abbrev(DA),
 180       RangeSection(RS), LineSection(LS), StringSection(SS),
 181       StringOffsetSection(SOS), AddrOffsetSection(AOS), isLittleEndian(LE),
 182       IsDWO(IsDWO), UnitVector(UnitVector) {
 183   clear();
 184 }
 185
 186 DWARFUnit::~DWARFUnit() = default;
 187
 188 DWARFDataExtractor DWARFUnit::getDebugInfoExtractor() const {
 189   return DWARFDataExtractor(Context.getDWARFObj(), InfoSection, isLittleEndian,
 190                             getAddressByteSize());
 191 }
 192
 193 Optional<object::SectionedAddress>
 194 DWARFUnit::getAddrOffsetSectionItem(uint32_t Index) const {
 195   if (!AddrOffsetSectionBase) {
 196     auto R = Context.info_section_units();
 197     // Surprising if a DWO file has more than one skeleton unit in it - this
 198     // probably shouldn't be valid, but if a use case is found, here's where to
 199     // support it (probably have to linearly search for the matching skeleton CU
 200     // here)
 201     if (IsDWO && hasSingleElement(R))
 202       return (*R.begin())->getAddrOffsetSectionItem(Index);
 203
 204     return None;
 205   }
 206
 207   uint64_t Offset = *AddrOffsetSectionBase + Index * getAddressByteSize();
 208   if (AddrOffsetSection->Data.size() < Offset + getAddressByteSize())
 209     return None;
 210   DWARFDataExtractor DA(Context.getDWARFObj(), *AddrOffsetSection,
 211                         isLittleEndian, getAddressByteSize());
 212   uint64_t Section;
 213   uint64_t Address = DA.getRelocatedAddress(&Offset, &Section);
 214   return {{Address, Section}};
 215 }
 216
 217 Optional<uint64_t> DWARFUnit::getStringOffsetSectionItem(uint32_t Index) const {
 218   if (!StringOffsetsTableContribution)
 219     return None;
 220   unsigned ItemSize = getDwarfStringOffsetsByteSize();
 221   uint64_t Offset = getStringOffsetsBase() + Index * ItemSize;
 222   if (StringOffsetSection.Data.size() < Offset + ItemSize)
 223     return None;
 224   DWARFDataExtractor DA(Context.getDWARFObj(), StringOffsetSection,
 225                         isLittleEndian, 0);
 226   return DA.getRelocatedValue(ItemSize, &Offset);
 227 }
 228
 229 bool DWARFUnitHeader::extract(DWARFContext &Context,
 230                               const DWARFDataExtractor &debug_info,
 231                               uint64_t *offset_ptr,
 232                               DWARFSectionKind SectionKind) {
 233   Offset = *offset_ptr;
 234   Error Err = Error::success();
 235   IndexEntry = nullptr;
 236   std::tie(Length, FormParams.Format) =
 237       debug_info.getInitialLength(offset_ptr, &Err);
 238   FormParams.Version = debug_info.getU16(offset_ptr, &Err);
 239   if (FormParams.Version >= 5) {
 240     UnitType = debug_info.getU8(offset_ptr, &Err);
 241     FormParams.AddrSize = debug_info.getU8(offset_ptr, &Err);
 242     AbbrOffset = debug_info.getRelocatedValue(
 243         FormParams.getDwarfOffsetByteSize(), offset_ptr, nullptr, &Err);
 244   } else {
 245     AbbrOffset = debug_info.getRelocatedValue(
 246         FormParams.getDwarfOffsetByteSize(), offset_ptr, nullptr, &Err);
 247     FormParams.AddrSize = debug_info.getU8(offset_ptr, &Err);
 248     // Fake a unit type based on the section type.  This isn't perfect,
 249     // but distinguishing compile and type units is generally enough.
 250     if (SectionKind == DW_SECT_EXT_TYPES)
 251       UnitType = DW_UT_type;
 252     else
 253       UnitType = DW_UT_compile;
 254   }
 255   if (isTypeUnit()) {
 256     TypeHash = debug_info.getU64(offset_ptr, &Err);
 257     TypeOffset = debug_info.getUnsigned(
 258         offset_ptr, FormParams.getDwarfOffsetByteSize(), &Err);
 259   } else if (UnitType == DW_UT_split_compile || UnitType == DW_UT_skeleton)
 260     DWOId = debug_info.getU64(offset_ptr, &Err);
 261
 262   if (Err) {
 263     Context.getWarningHandler()(joinErrors(
 264         createStringError(
 265             errc::invalid_argument,
 266             "DWARF unit at 0x%8.8" PRIx64 " cannot be parsed:", Offset),
 267         std::move(Err)));
 268     return false;
 269   }
 270
 271   // Header fields all parsed, capture the size of this unit header.
 272   assert(*offset_ptr - Offset <= 255 && "unexpected header size");
 273   Size = uint8_t(*offset_ptr - Offset);
 274   uint64_t NextCUOffset = Offset + getUnitLengthFieldByteSize() + getLength();
 275
 276   if (!debug_info.isValidOffset(getNextUnitOffset() - 1)) {
 277     Context.getWarningHandler()(
 278         createStringError(errc::invalid_argument,
 279                           "DWARF unit from offset 0x%8.8" PRIx64 " incl. "
 280                           "to offset  0x%8.8" PRIx64 " excl. "
 281                           "extends past section size 0x%8.8zx",
 282                           Offset, NextCUOffset, debug_info.size()));
 283     return false;
 284   }
 285
 286   if (!DWARFContext::isSupportedVersion(getVersion())) {
 287     Context.getWarningHandler()(createStringError(
 288         errc::invalid_argument,
 289         "DWARF unit at offset 0x%8.8" PRIx64 " "
 290         "has unsupported version %" PRIu16 ", supported are 2-%u",
 291         Offset, getVersion(), DWARFContext::getMaxSupportedVersion()));
 292     return false;
 293   }
 294
 295   // Type offset is unit-relative; should be after the header and before
 296   // the end of the current unit.
 297   if (isTypeUnit() && TypeOffset < Size) {
 298     Context.getWarningHandler()(
 299         createStringError(errc::invalid_argument,
 300                           "DWARF type unit at offset "
 301                           "0x%8.8" PRIx64 " "
 302                           "has its relocated type_offset 0x%8.8" PRIx64 " "
 303                           "pointing inside the header",
 304                           Offset, Offset + TypeOffset));
 305     return false;
 306   }
 307   if (isTypeUnit() &&
 308       TypeOffset >= getUnitLengthFieldByteSize() + getLength()) {
 309     Context.getWarningHandler()(createStringError(
 310         errc::invalid_argument,
 311         "DWARF type unit from offset 0x%8.8" PRIx64 " incl. "
 312         "to offset 0x%8.8" PRIx64 " excl. has its "
 313         "relocated type_offset 0x%8.8" PRIx64 " pointing past the unit end",
 314         Offset, NextCUOffset, Offset + TypeOffset));
 315     return false;
 316   }
 317
 318   if (!DWARFContext::isAddressSizeSupported(getAddressByteSize())) {
 319     SmallVector<std::string, 3> Sizes;
 320     for (auto Size : DWARFContext::getSupportedAddressSizes())
 321       Sizes.push_back(std::to_string(Size));
 322     Context.getWarningHandler()(createStringError(
 323         errc::invalid_argument,
 324         "DWARF unit at offset 0x%8.8" PRIx64 " "
 325         "has unsupported address size %" PRIu8 ", supported are %s",
 326         Offset, getAddressByteSize(), llvm::join(Sizes, ", ").c_str()));
 327     return false;
 328   }
 329
 330   // Keep track of the highest DWARF version we encounter across all units.
 331   Context.setMaxVersionIfGreater(getVersion());
 332   return true;
 333 }
 334
 335 bool DWARFUnitHeader::applyIndexEntry(const DWARFUnitIndex::Entry *Entry) {
 336   assert(Entry);
 337   assert(!IndexEntry);
 338   IndexEntry = Entry;
 339   if (AbbrOffset)
 340     return false;
 341   auto *UnitContrib = IndexEntry->getContribution();
 342   if (!UnitContrib ||
 343       UnitContrib->Length != (getLength() + getUnitLengthFieldByteSize()))
 344     return false;
 345   auto *AbbrEntry = IndexEntry->getContribution(DW_SECT_ABBREV);
 346   if (!AbbrEntry)
 347     return false;
 348   AbbrOffset = AbbrEntry->Offset;
 349   return true;
 350 }
 351
 352 Error DWARFUnit::extractRangeList(uint64_t RangeListOffset,
 353                                   DWARFDebugRangeList &RangeList) const {
 354   // Require that compile unit is extracted.
 355   assert(!DieArray.empty());
 356   DWARFDataExtractor RangesData(Context.getDWARFObj(), *RangeSection,
 357                                 isLittleEndian, getAddressByteSize());
 358   uint64_t ActualRangeListOffset = RangeSectionBase + RangeListOffset;
 359   return RangeList.extract(RangesData, &ActualRangeListOffset);
 360 }
 361
 362 void DWARFUnit::clear() {
 363   Abbrevs = nullptr;
 364   BaseAddr.reset();
 365   RangeSectionBase = 0;
 366   LocSectionBase = 0;
 367   AddrOffsetSectionBase = None;
 368   SU = nullptr;
 369   clearDIEs(false);
 370   DWO.reset();
 371 }
 372
 373 const char *DWARFUnit::getCompilationDir() {
 374   return dwarf::toString(getUnitDIE().find(DW_AT_comp_dir), nullptr);
 375 }
 376
 377 void DWARFUnit::extractDIEsToVector(
 378     bool AppendCUDie, bool AppendNonCUDies,
 379     std::vector<DWARFDebugInfoEntry> &Dies) const {
 380   if (!AppendCUDie && !AppendNonCUDies)
 381     return;
 382
 383   // Set the offset to that of the first DIE and calculate the start of the
 384   // next compilation unit header.
 385   uint64_t DIEOffset = getOffset() + getHeaderSize();
 386   uint64_t NextCUOffset = getNextUnitOffset();
 387   DWARFDebugInfoEntry DIE;
 388   DWARFDataExtractor DebugInfoData = getDebugInfoExtractor();
 389   // The end offset has been already checked by DWARFUnitHeader::extract.
 390   assert(DebugInfoData.isValidOffset(NextCUOffset - 1));
 391   uint32_t Depth = 0;
 392   bool IsCUDie = true;
 393
 394   while (DIE.extractFast(*this, &DIEOffset, DebugInfoData, NextCUOffset,
 395                          Depth)) {
 396     if (IsCUDie) {
 397       if (AppendCUDie)
 398         Dies.push_back(DIE);
 399       if (!AppendNonCUDies)
 400         break;
 401       // The average bytes per DIE entry has been seen to be
 402       // around 14-20 so let's pre-reserve the needed memory for
 403       // our DIE entries accordingly.
 404       Dies.reserve(Dies.size() + getDebugInfoSize() / 14);
 405       IsCUDie = false;
 406     } else {
 407       Dies.push_back(DIE);
 408     }
 409
 410     if (const DWARFAbbreviationDeclaration *AbbrDecl =
 411             DIE.getAbbreviationDeclarationPtr()) {
 412       // Normal DIE
 413       if (AbbrDecl->hasChildren())
 414         ++Depth;
 415       else if (Depth == 0)
 416         break; // This unit has a single DIE with no children.
 417     } else {
 418       // NULL DIE.
 419       if (Depth > 0)
 420         --Depth;
 421       if (Depth == 0)
 422         break;  // We are done with this compile unit!
 423     }
 424   }
 425 }
 426
 427 void DWARFUnit::extractDIEsIfNeeded(bool CUDieOnly) {
 428   if (Error e = tryExtractDIEsIfNeeded(CUDieOnly))
 429     Context.getRecoverableErrorHandler()(std::move(e));
 430 }
 431
 432 Error DWARFUnit::tryExtractDIEsIfNeeded(bool CUDieOnly) {
 433   if ((CUDieOnly && !DieArray.empty()) ||
 434       DieArray.size() > 1)
 435     return Error::success(); // Already parsed.
 436
 437   bool HasCUDie = !DieArray.empty();
 438   extractDIEsToVector(!HasCUDie, !CUDieOnly, DieArray);
 439
 440   if (DieArray.empty())
 441     return Error::success();
 442
 443   // If CU DIE was just parsed, copy several attribute values from it.
 444   if (HasCUDie)
 445     return Error::success();
 446
 447   DWARFDie UnitDie(this, &DieArray[0]);
 448   if (Optional<uint64_t> DWOId = toUnsigned(UnitDie.find(DW_AT_GNU_dwo_id)))
 449     Header.setDWOId(*DWOId);
 450   if (!IsDWO) {
 451     assert(AddrOffsetSectionBase == None);
 452     assert(RangeSectionBase == 0);
 453     assert(LocSectionBase == 0);
 454     AddrOffsetSectionBase = toSectionOffset(UnitDie.find(DW_AT_addr_base));
 455     if (!AddrOffsetSectionBase)
 456       AddrOffsetSectionBase =
 457           toSectionOffset(UnitDie.find(DW_AT_GNU_addr_base));
 458     RangeSectionBase = toSectionOffset(UnitDie.find(DW_AT_rnglists_base), 0);
 459     LocSectionBase = toSectionOffset(UnitDie.find(DW_AT_loclists_base), 0);
 460   }
 461
 462   // In general, in DWARF v5 and beyond we derive the start of the unit's
 463   // contribution to the string offsets table from the unit DIE's
 464   // DW_AT_str_offsets_base attribute. Split DWARF units do not use this
 465   // attribute, so we assume that there is a contribution to the string
 466   // offsets table starting at offset 0 of the debug_str_offsets.dwo section.
 467   // In both cases we need to determine the format of the contribution,
 468   // which may differ from the unit's format.
 469   DWARFDataExtractor DA(Context.getDWARFObj(), StringOffsetSection,
 470                         isLittleEndian, 0);
 471   if (IsDWO || getVersion() >= 5) {
 472     auto StringOffsetOrError =
 473         IsDWO ? determineStringOffsetsTableContributionDWO(DA)
 474               : determineStringOffsetsTableContribution(DA);
 475     if (!StringOffsetOrError)
 476       return createStringError(errc::invalid_argument,
 477                                "invalid reference to or invalid content in "
 478                                ".debug_str_offsets[.dwo]: " +
 479                                    toString(StringOffsetOrError.takeError()));
 480
 481     StringOffsetsTableContribution = *StringOffsetOrError;
 482   }
 483
 484   // DWARF v5 uses the .debug_rnglists and .debug_rnglists.dwo sections to
 485   // describe address ranges.
 486   if (getVersion() >= 5) {
 487     // In case of DWP, the base offset from the index has to be added.
 488     if (IsDWO) {
 489       uint64_t ContributionBaseOffset = 0;
 490       if (auto *IndexEntry = Header.getIndexEntry())
 491         if (auto *Contrib = IndexEntry->getContribution(DW_SECT_RNGLISTS))
 492           ContributionBaseOffset = Contrib->Offset;
 493       setRangesSection(
 494           &Context.getDWARFObj().getRnglistsDWOSection(),
 495           ContributionBaseOffset +
 496               DWARFListTableHeader::getHeaderSize(Header.getFormat()));
 497     } else
 498       setRangesSection(&Context.getDWARFObj().getRnglistsSection(),
 499                        toSectionOffset(UnitDie.find(DW_AT_rnglists_base),
 500                                        DWARFListTableHeader::getHeaderSize(
 501                                            Header.getFormat())));
 502   }
 503
 504   if (IsDWO) {
 505     // If we are reading a package file, we need to adjust the location list
 506     // data based on the index entries.
 507     StringRef Data = Header.getVersion() >= 5
 508                          ? Context.getDWARFObj().getLoclistsDWOSection().Data
 509                          : Context.getDWARFObj().getLocDWOSection().Data;
 510     if (auto *IndexEntry = Header.getIndexEntry())
 511       if (const auto *C = IndexEntry->getContribution(
 512               Header.getVersion() >= 5 ? DW_SECT_LOCLISTS : DW_SECT_EXT_LOC))
 513         Data = Data.substr(C->Offset, C->Length);
 514
 515     DWARFDataExtractor DWARFData(Data, isLittleEndian, getAddressByteSize());
 516     LocTable =
 517         std::make_unique<DWARFDebugLoclists>(DWARFData, Header.getVersion());
 518     LocSectionBase = DWARFListTableHeader::getHeaderSize(Header.getFormat());
 519   } else if (getVersion() >= 5) {
 520     LocTable = std::make_unique<DWARFDebugLoclists>(
 521         DWARFDataExtractor(Context.getDWARFObj(),
 522                            Context.getDWARFObj().getLoclistsSection(),
 523                            isLittleEndian, getAddressByteSize()),
 524         getVersion());
 525   } else {
 526     LocTable = std::make_unique<DWARFDebugLoc>(DWARFDataExtractor(
 527         Context.getDWARFObj(), Context.getDWARFObj().getLocSection(),
 528         isLittleEndian, getAddressByteSize()));
 529   }
 530
 531   // Don't fall back to DW_AT_GNU_ranges_base: it should be ignored for
 532   // skeleton CU DIE, so that DWARF users not aware of it are not broken.
 533   return Error::success();
 534 }
 535
 536 bool DWARFUnit::parseDWO() {
 537   if (IsDWO)
 538     return false;
 539   if (DWO.get())
 540     return false;
 541   DWARFDie UnitDie = getUnitDIE();
 542   if (!UnitDie)
 543     return false;
 544   auto DWOFileName = getVersion() >= 5
 545                          ? dwarf::toString(UnitDie.find(DW_AT_dwo_name))
 546                          : dwarf::toString(UnitDie.find(DW_AT_GNU_dwo_name));
 547   if (!DWOFileName)
 548     return false;
 549   auto CompilationDir = dwarf::toString(UnitDie.find(DW_AT_comp_dir));
 550   SmallString<16> AbsolutePath;
 551   if (sys::path::is_relative(*DWOFileName) && CompilationDir &&
 552       *CompilationDir) {
 553     sys::path::append(AbsolutePath, *CompilationDir);
 554   }
 555   sys::path::append(AbsolutePath, *DWOFileName);
 556   auto DWOId = getDWOId();
 557   if (!DWOId)
 558     return false;
 559   auto DWOContext = Context.getDWOContext(AbsolutePath);
 560   if (!DWOContext)
 561     return false;
 562
 563   DWARFCompileUnit *DWOCU = DWOContext->getDWOCompileUnitForHash(*DWOId);
 564   if (!DWOCU)
 565     return false;
 566   DWO = std::shared_ptr<DWARFCompileUnit>(std::move(DWOContext), DWOCU);
 567   DWO->setSkeletonUnit(this);
 568   // Share .debug_addr and .debug_ranges section with compile unit in .dwo
 569   if (AddrOffsetSectionBase)
 570     DWO->setAddrOffsetSection(AddrOffsetSection, *AddrOffsetSectionBase);
 571   if (getVersion() == 4) {
 572     auto DWORangesBase = UnitDie.getRangesBaseAttribute();
 573     DWO->setRangesSection(RangeSection, DWORangesBase ? *DWORangesBase : 0);
 574   }
 575
 576   return true;
 577 }
 578
 579 void DWARFUnit::clearDIEs(bool KeepCUDie) {
 580   if (DieArray.size() > (unsigned)KeepCUDie) {
 581     DieArray.resize((unsigned)KeepCUDie);
 582     DieArray.shrink_to_fit();
 583   }
 584 }
 585
 586 Expected<DWARFAddressRangesVector>
 587 DWARFUnit::findRnglistFromOffset(uint64_t Offset) {
 588   if (getVersion() <= 4) {
 589     DWARFDebugRangeList RangeList;
 590     if (Error E = extractRangeList(Offset, RangeList))
 591       return std::move(E);
 592     return RangeList.getAbsoluteRanges(getBaseAddress());
 593   }
 594   DWARFDataExtractor RangesData(Context.getDWARFObj(), *RangeSection,
 595                                 isLittleEndian, Header.getAddressByteSize());
 596   DWARFDebugRnglistTable RnglistTable;
 597   auto RangeListOrError = RnglistTable.findList(RangesData, Offset);
 598   if (RangeListOrError)
 599     return RangeListOrError.get().getAbsoluteRanges(getBaseAddress(), *this);
 600   return RangeListOrError.takeError();
 601 }
 602
 603 Expected<DWARFAddressRangesVector>
 604 DWARFUnit::findRnglistFromIndex(uint32_t Index) {
 605   if (auto Offset = getRnglistOffset(Index))
 606     return findRnglistFromOffset(*Offset);
 607
 608   return createStringError(errc::invalid_argument,
 609                            "invalid range list table index %d (possibly "
 610                            "missing the entire range list table)",
 611                            Index);
 612 }
 613
 614 Expected<DWARFAddressRangesVector> DWARFUnit::collectAddressRanges() {
 615   DWARFDie UnitDie = getUnitDIE();
 616   if (!UnitDie)
 617     return createStringError(errc::invalid_argument, "No unit DIE");
 618
 619   // First, check if unit DIE describes address ranges for the whole unit.
 620   auto CUDIERangesOrError = UnitDie.getAddressRanges();
 621   if (!CUDIERangesOrError)
 622     return createStringError(errc::invalid_argument,
 623                              "decoding address ranges: %s",
 624                              toString(CUDIERangesOrError.takeError()).c_str());
 625   return *CUDIERangesOrError;
 626 }
 627
 628 Expected<DWARFLocationExpressionsVector>
 629 DWARFUnit::findLoclistFromOffset(uint64_t Offset) {
 630   DWARFLocationExpressionsVector Result;
 631
 632   Error InterpretationError = Error::success();
 633
 634   Error ParseError = getLocationTable().visitAbsoluteLocationList(
 635       Offset, getBaseAddress(),
 636       [this](uint32_t Index) { return getAddrOffsetSectionItem(Index); },
 637       [&](Expected<DWARFLocationExpression> L) {
 638         if (L)
 639           Result.push_back(std::move(*L));
 640         else
 641           InterpretationError =
 642               joinErrors(L.takeError(), std::move(InterpretationError));
 643         return !InterpretationError;
 644       });
 645
 646   if (ParseError || InterpretationError)
 647     return joinErrors(std::move(ParseError), std::move(InterpretationError));
 648
 649   return Result;
 650 }
 651
 652 void DWARFUnit::updateAddressDieMap(DWARFDie Die) {
 653   if (Die.isSubroutineDIE()) {
 654     auto DIERangesOrError = Die.getAddressRanges();
 655     if (DIERangesOrError) {
 656       for (const auto &R : DIERangesOrError.get()) {
 657         // Ignore 0-sized ranges.
 658         if (R.LowPC == R.HighPC)
 659           continue;
 660         auto B = AddrDieMap.upper_bound(R.LowPC);
 661         if (B != AddrDieMap.begin() && R.LowPC < (--B)->second.first) {
 662           // The range is a sub-range of existing ranges, we need to split the
 663           // existing range.
 664           if (R.HighPC < B->second.first)
 665             AddrDieMap[R.HighPC] = B->second;
 666           if (R.LowPC > B->first)
 667             AddrDieMap[B->first].first = R.LowPC;
 668         }
 669         AddrDieMap[R.LowPC] = std::make_pair(R.HighPC, Die);
 670       }
 671     } else
 672       llvm::consumeError(DIERangesOrError.takeError());
 673   }
 674   // Parent DIEs are added to the AddrDieMap prior to the Children DIEs to
 675   // simplify the logic to update AddrDieMap. The child's range will always
 676   // be equal or smaller than the parent's range. With this assumption, when
 677   // adding one range into the map, it will at most split a range into 3
 678   // sub-ranges.
 679   for (DWARFDie Child = Die.getFirstChild(); Child; Child = Child.getSibling())
 680     updateAddressDieMap(Child);
 681 }
 682
 683 DWARFDie DWARFUnit::getSubroutineForAddress(uint64_t Address) {
 684   extractDIEsIfNeeded(false);
 685   if (AddrDieMap.empty())
 686     updateAddressDieMap(getUnitDIE());
 687   auto R = AddrDieMap.upper_bound(Address);
 688   if (R == AddrDieMap.begin())
 689     return DWARFDie();
 690   // upper_bound's previous item contains Address.
 691   --R;
 692   if (Address >= R->second.first)
 693     return DWARFDie();
 694   return R->second.second;
 695 }
 696
 697 void
 698 DWARFUnit::getInlinedChainForAddress(uint64_t Address,
 699                                      SmallVectorImpl<DWARFDie> &InlinedChain) {
 700   assert(InlinedChain.empty());
 701   // Try to look for subprogram DIEs in the DWO file.
 702   parseDWO();
 703   // First, find the subroutine that contains the given address (the leaf
 704   // of inlined chain).
 705   DWARFDie SubroutineDIE =
 706       (DWO ? *DWO : *this).getSubroutineForAddress(Address);
 707
 708   while (SubroutineDIE) {
 709     if (SubroutineDIE.isSubprogramDIE()) {
 710       InlinedChain.push_back(SubroutineDIE);
 711       return;
 712     }
 713     if (SubroutineDIE.getTag() == DW_TAG_inlined_subroutine)
 714       InlinedChain.push_back(SubroutineDIE);
 715     SubroutineDIE  = SubroutineDIE.getParent();
 716   }
 717 }
 718
 719 const DWARFUnitIndex &llvm::getDWARFUnitIndex(DWARFContext &Context,
 720                                               DWARFSectionKind Kind) {
 721   if (Kind == DW_SECT_INFO)
 722     return Context.getCUIndex();
 723   assert(Kind == DW_SECT_EXT_TYPES);
 724   return Context.getTUIndex();
 725 }
 726
 727 DWARFDie DWARFUnit::getParent(const DWARFDebugInfoEntry *Die) {
 728   if (!Die)
 729     return DWARFDie();
 730   const uint32_t Depth = Die->getDepth();
 731   // Unit DIEs always have a depth of zero and never have parents.
 732   if (Depth == 0)
 733     return DWARFDie();
 734   // Depth of 1 always means parent is the compile/type unit.
 735   if (Depth == 1)
 736     return getUnitDIE();
 737   // Look for previous DIE with a depth that is one less than the Die's depth.
 738   const uint32_t ParentDepth = Depth - 1;
 739   for (uint32_t I = getDIEIndex(Die) - 1; I > 0; --I) {
 740     if (DieArray[I].getDepth() == ParentDepth)
 741       return DWARFDie(this, &DieArray[I]);
 742   }
 743   return DWARFDie();
 744 }
 745
 746 DWARFDie DWARFUnit::getSibling(const DWARFDebugInfoEntry *Die) {
 747   if (!Die)
 748     return DWARFDie();
 749   uint32_t Depth = Die->getDepth();
 750   // Unit DIEs always have a depth of zero and never have siblings.
 751   if (Depth == 0)
 752     return DWARFDie();
 753   // NULL DIEs don't have siblings.
 754   if (Die->getAbbreviationDeclarationPtr() == nullptr)
 755     return DWARFDie();
 756
 757   // Find the next DIE whose depth is the same as the Die's depth.
 758   for (size_t I = getDIEIndex(Die) + 1, EndIdx = DieArray.size(); I < EndIdx;
 759        ++I) {
 760     if (DieArray[I].getDepth() == Depth)
 761       return DWARFDie(this, &DieArray[I]);
 762   }
 763   return DWARFDie();
 764 }
 765
 766 DWARFDie DWARFUnit::getPreviousSibling(const DWARFDebugInfoEntry *Die) {
 767   if (!Die)
 768     return DWARFDie();
 769   uint32_t Depth = Die->getDepth();
 770   // Unit DIEs always have a depth of zero and never have siblings.
 771   if (Depth == 0)
 772     return DWARFDie();
 773
 774   // Find the previous DIE whose depth is the same as the Die's depth.
 775   for (size_t I = getDIEIndex(Die); I > 0;) {
 776     --I;
 777     if (DieArray[I].getDepth() == Depth - 1)
 778       return DWARFDie();
 779     if (DieArray[I].getDepth() == Depth)
 780       return DWARFDie(this, &DieArray[I]);
 781   }
 782   return DWARFDie();
 783 }
 784
 785 DWARFDie DWARFUnit::getFirstChild(const DWARFDebugInfoEntry *Die) {
 786   if (!Die->hasChildren())
 787     return DWARFDie();
 788
 789   // We do not want access out of bounds when parsing corrupted debug data.
 790   size_t I = getDIEIndex(Die) + 1;
 791   if (I >= DieArray.size())
 792     return DWARFDie();
 793   return DWARFDie(this, &DieArray[I]);
 794 }
 795
 796 DWARFDie DWARFUnit::getLastChild(const DWARFDebugInfoEntry *Die) {
 797   if (!Die->hasChildren())
 798     return DWARFDie();
 799
 800   uint32_t Depth = Die->getDepth();
 801   for (size_t I = getDIEIndex(Die) + 1, EndIdx = DieArray.size(); I < EndIdx;
 802        ++I) {
 803     if (DieArray[I].getDepth() == Depth + 1 &&
 804         DieArray[I].getTag() == dwarf::DW_TAG_null)
 805       return DWARFDie(this, &DieArray[I]);
 806     assert(DieArray[I].getDepth() > Depth && "Not processing children?");
 807   }
 808   return DWARFDie();
 809 }
 810
 811 const DWARFAbbreviationDeclarationSet *DWARFUnit::getAbbreviations() const {
 812   if (!Abbrevs)
 813     Abbrevs = Abbrev->getAbbreviationDeclarationSet(getAbbreviationsOffset());
 814   return Abbrevs;
 815 }
 816
 817 llvm::Optional<object::SectionedAddress> DWARFUnit::getBaseAddress() {
 818   if (BaseAddr)
 819     return BaseAddr;
 820
 821   DWARFDie UnitDie = getUnitDIE();
 822   Optional<DWARFFormValue> PC = UnitDie.find({DW_AT_low_pc, DW_AT_entry_pc});
 823   BaseAddr = toSectionedAddress(PC);
 824   return BaseAddr;
 825 }
 826
 827 Expected<StrOffsetsContributionDescriptor>
 828 StrOffsetsContributionDescriptor::validateContributionSize(
 829     DWARFDataExtractor &DA) {
 830   uint8_t EntrySize = getDwarfOffsetByteSize();
 831   // In order to ensure that we don't read a partial record at the end of
 832   // the section we validate for a multiple of the entry size.
 833   uint64_t ValidationSize = alignTo(Size, EntrySize);
 834   // Guard against overflow.
 835   if (ValidationSize >= Size)
 836     if (DA.isValidOffsetForDataOfSize((uint32_t)Base, ValidationSize))
 837       return *this;
 838   return createStringError(errc::invalid_argument, "length exceeds section size");
 839 }
 840
 841 // Look for a DWARF64-formatted contribution to the string offsets table
 842 // starting at a given offset and record it in a descriptor.
 843 static Expected<StrOffsetsContributionDescriptor>
 844 parseDWARF64StringOffsetsTableHeader(DWARFDataExtractor &DA, uint64_t Offset) {
 845   if (!DA.isValidOffsetForDataOfSize(Offset, 16))
 846     return createStringError(errc::invalid_argument, "section offset exceeds section size");
 847
 848   if (DA.getU32(&Offset) != dwarf::DW_LENGTH_DWARF64)
 849     return createStringError(errc::invalid_argument, "32 bit contribution referenced from a 64 bit unit");
 850
 851   uint64_t Size = DA.getU64(&Offset);
 852   uint8_t Version = DA.getU16(&Offset);
 853   (void)DA.getU16(&Offset); // padding
 854   // The encoded length includes the 2-byte version field and the 2-byte
 855   // padding, so we need to subtract them out when we populate the descriptor.
 856   return StrOffsetsContributionDescriptor(Offset, Size - 4, Version, DWARF64);
 857 }
 858
 859 // Look for a DWARF32-formatted contribution to the string offsets table
 860 // starting at a given offset and record it in a descriptor.
 861 static Expected<StrOffsetsContributionDescriptor>
 862 parseDWARF32StringOffsetsTableHeader(DWARFDataExtractor &DA, uint64_t Offset) {
 863   if (!DA.isValidOffsetForDataOfSize(Offset, 8))
 864     return createStringError(errc::invalid_argument, "section offset exceeds section size");
 865
 866   uint32_t ContributionSize = DA.getU32(&Offset);
 867   if (ContributionSize >= dwarf::DW_LENGTH_lo_reserved)
 868     return createStringError(errc::invalid_argument, "invalid length");
 869
 870   uint8_t Version = DA.getU16(&Offset);
 871   (void)DA.getU16(&Offset); // padding
 872   // The encoded length includes the 2-byte version field and the 2-byte
 873   // padding, so we need to subtract them out when we populate the descriptor.
 874   return StrOffsetsContributionDescriptor(Offset, ContributionSize - 4, Version,
 875                                           DWARF32);
 876 }
 877
 878 static Expected<StrOffsetsContributionDescriptor>
 879 parseDWARFStringOffsetsTableHeader(DWARFDataExtractor &DA,
 880                                    llvm::dwarf::DwarfFormat Format,
 881                                    uint64_t Offset) {
 882   StrOffsetsContributionDescriptor Desc;
 883   switch (Format) {
 884   case dwarf::DwarfFormat::DWARF64: {
 885     if (Offset < 16)
 886       return createStringError(errc::invalid_argument, "insufficient space for 64 bit header prefix");
 887     auto DescOrError = parseDWARF64StringOffsetsTableHeader(DA, Offset - 16);
 888     if (!DescOrError)
 889       return DescOrError.takeError();
 890     Desc = *DescOrError;
 891     break;
 892   }
 893   case dwarf::DwarfFormat::DWARF32: {
 894     if (Offset < 8)
 895       return createStringError(errc::invalid_argument, "insufficient space for 32 bit header prefix");
 896     auto DescOrError = parseDWARF32StringOffsetsTableHeader(DA, Offset - 8);
 897     if (!DescOrError)
 898       return DescOrError.takeError();
 899     Desc = *DescOrError;
 900     break;
 901   }
 902   }
 903   return Desc.validateContributionSize(DA);
 904 }
 905
 906 Expected<Optional<StrOffsetsContributionDescriptor>>
 907 DWARFUnit::determineStringOffsetsTableContribution(DWARFDataExtractor &DA) {
 908   assert(!IsDWO);
 909   auto OptOffset = toSectionOffset(getUnitDIE().find(DW_AT_str_offsets_base));
 910   if (!OptOffset)
 911     return None;
 912   auto DescOrError =
 913       parseDWARFStringOffsetsTableHeader(DA, Header.getFormat(), *OptOffset);
 914   if (!DescOrError)
 915     return DescOrError.takeError();
 916   return *DescOrError;
 917 }
 918
 919 Expected<Optional<StrOffsetsContributionDescriptor>>
 920 DWARFUnit::determineStringOffsetsTableContributionDWO(DWARFDataExtractor & DA) {
 921   assert(IsDWO);
 922   uint64_t Offset = 0;
 923   auto IndexEntry = Header.getIndexEntry();
 924   const auto *C =
 925       IndexEntry ? IndexEntry->getContribution(DW_SECT_STR_OFFSETS) : nullptr;
 926   if (C)
 927     Offset = C->Offset;
 928   if (getVersion() >= 5) {
 929     if (DA.getData().data() == nullptr)
 930       return None;
 931     Offset += Header.getFormat() == dwarf::DwarfFormat::DWARF32 ? 8 : 16;
 932     // Look for a valid contribution at the given offset.
 933     auto DescOrError = parseDWARFStringOffsetsTableHeader(DA, Header.getFormat(), Offset);
 934     if (!DescOrError)
 935       return DescOrError.takeError();
 936     return *DescOrError;
 937   }
 938   // Prior to DWARF v5, we derive the contribution size from the
 939   // index table (in a package file). In a .dwo file it is simply
 940   // the length of the string offsets section.
 941   StrOffsetsContributionDescriptor Desc;
 942   if (C)
 943     Desc = StrOffsetsContributionDescriptor(C->Offset, C->Length, 4,
 944                                             Header.getFormat());
 945   else if (!IndexEntry && !StringOffsetSection.Data.empty())
 946     Desc = StrOffsetsContributionDescriptor(0, StringOffsetSection.Data.size(),
 947                                             4, Header.getFormat());
 948   else
 949     return None;
 950   auto DescOrError = Desc.validateContributionSize(DA);
 951   if (!DescOrError)
 952     return DescOrError.takeError();
 953   return *DescOrError;
 954 }
 955
 956 Optional<uint64_t> DWARFUnit::getRnglistOffset(uint32_t Index) {
 957   DataExtractor RangesData(RangeSection->Data, isLittleEndian,
 958                            getAddressByteSize());
 959   DWARFDataExtractor RangesDA(Context.getDWARFObj(), *RangeSection,
 960                               isLittleEndian, 0);
 961   if (Optional<uint64_t> Off = llvm::DWARFListTableHeader::getOffsetEntry(
 962           RangesData, RangeSectionBase, getFormat(), Index))
 963     return *Off + RangeSectionBase;
 964   return None;
 965 }
 966
 967 Optional<uint64_t> DWARFUnit::getLoclistOffset(uint32_t Index) {
 968   if (Optional<uint64_t> Off = llvm::DWARFListTableHeader::getOffsetEntry(
 969           LocTable->getData(), LocSectionBase, getFormat(), Index))
 970     return *Off + LocSectionBase;
 971   return None;
 972 }