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