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), LocSection(LocSection), LineSection(LS),
 179       StringSection(SS), StringOffsetSection(SOS), AddrOffsetSection(AOS),
 180       isLittleEndian(LE), IsDWO(IsDWO), UnitVector(UnitVector) {
 181   clear();
 182   // For split DWARF we only need to keep track of the location list section's
 183   // data (no relocations), and if we are reading a package file, we need to
 184   // adjust the location list data based on the index entries.
 185   if (IsDWO) {
 186     LocSectionData = LocSection->Data;
 187     if (auto *IndexEntry = Header.getIndexEntry())
 188       if (const auto *C = IndexEntry->getOffset(DW_SECT_LOC))
 189         LocSectionData = LocSectionData.substr(C->Offset, C->Length);
 190   }
 191 }
 192
 193 DWARFUnit::~DWARFUnit() = default;
 194
 195 DWARFDataExtractor DWARFUnit::getDebugInfoExtractor() const {
 196   return DWARFDataExtractor(Context.getDWARFObj(), InfoSection, isLittleEndian,
 197                             getAddressByteSize());
 198 }
 199
 200 Optional<object::SectionedAddress>
 201 DWARFUnit::getAddrOffsetSectionItem(uint32_t Index) const {
 202   if (IsDWO) {
 203     auto R = Context.info_section_units();
 204     auto I = R.begin();
 205     // Surprising if a DWO file has more than one skeleton unit in it - this
 206     // probably shouldn't be valid, but if a use case is found, here's where to
 207     // support it (probably have to linearly search for the matching skeleton CU
 208     // here)
 209     if (I != R.end() && std::next(I) == R.end())
 210       return (*I)->getAddrOffsetSectionItem(Index);
 211   }
 212   uint64_t Offset = AddrOffsetSectionBase + Index * getAddressByteSize();
 213   if (AddrOffsetSection->Data.size() < Offset + getAddressByteSize())
 214     return None;
 215   DWARFDataExtractor DA(Context.getDWARFObj(), *AddrOffsetSection,
 216                         isLittleEndian, getAddressByteSize());
 217   uint64_t Section;
 218   uint64_t Address = DA.getRelocatedAddress(&Offset, &Section);
 219   return {{Address, Section}};
 220 }
 221
 222 Optional<uint64_t> DWARFUnit::getStringOffsetSectionItem(uint32_t Index) const {
 223   if (!StringOffsetsTableContribution)
 224     return None;
 225   unsigned ItemSize = getDwarfStringOffsetsByteSize();
 226   uint64_t Offset = getStringOffsetsBase() + Index * ItemSize;
 227   if (StringOffsetSection.Data.size() < Offset + ItemSize)
 228     return None;
 229   DWARFDataExtractor DA(Context.getDWARFObj(), StringOffsetSection,
 230                         isLittleEndian, 0);
 231   return DA.getRelocatedValue(ItemSize, &Offset);
 232 }
 233
 234 bool DWARFUnitHeader::extract(DWARFContext &Context,
 235                               const DWARFDataExtractor &debug_info,
 236                               uint64_t *offset_ptr,
 237                               DWARFSectionKind SectionKind,
 238                               const DWARFUnitIndex *Index,
 239                               const DWARFUnitIndex::Entry *Entry) {
 240   Offset = *offset_ptr;
 241   IndexEntry = Entry;
 242   if (!IndexEntry && Index)
 243     IndexEntry = Index->getFromOffset(*offset_ptr);
 244   Length = debug_info.getRelocatedValue(4, offset_ptr);
 245   FormParams.Format = DWARF32;
 246   if (Length == dwarf::DW_LENGTH_DWARF64) {
 247     Length = debug_info.getU64(offset_ptr);
 248     FormParams.Format = DWARF64;
 249   }
 250   FormParams.Version = debug_info.getU16(offset_ptr);
 251   if (FormParams.Version >= 5) {
 252     UnitType = debug_info.getU8(offset_ptr);
 253     FormParams.AddrSize = debug_info.getU8(offset_ptr);
 254     AbbrOffset = debug_info.getRelocatedValue(FormParams.getDwarfOffsetByteSize(), offset_ptr);
 255   } else {
 256     AbbrOffset = debug_info.getRelocatedValue(FormParams.getDwarfOffsetByteSize(), offset_ptr);
 257     FormParams.AddrSize = debug_info.getU8(offset_ptr);
 258     // Fake a unit type based on the section type.  This isn't perfect,
 259     // but distinguishing compile and type units is generally enough.
 260     if (SectionKind == DW_SECT_TYPES)
 261       UnitType = DW_UT_type;
 262     else
 263       UnitType = DW_UT_compile;
 264   }
 265   if (IndexEntry) {
 266     if (AbbrOffset)
 267       return false;
 268     auto *UnitContrib = IndexEntry->getOffset();
 269     if (!UnitContrib || UnitContrib->Length != (Length + 4))
 270       return false;
 271     auto *AbbrEntry = IndexEntry->getOffset(DW_SECT_ABBREV);
 272     if (!AbbrEntry)
 273       return false;
 274     AbbrOffset = AbbrEntry->Offset;
 275   }
 276   if (isTypeUnit()) {
 277     TypeHash = debug_info.getU64(offset_ptr);
 278     TypeOffset =
 279         debug_info.getUnsigned(offset_ptr, FormParams.getDwarfOffsetByteSize());
 280   } else if (UnitType == DW_UT_split_compile || UnitType == DW_UT_skeleton)
 281     DWOId = debug_info.getU64(offset_ptr);
 282
 283   // Header fields all parsed, capture the size of this unit header.
 284   assert(*offset_ptr - Offset <= 255 && "unexpected header size");
 285   Size = uint8_t(*offset_ptr - Offset);
 286
 287   // Type offset is unit-relative; should be after the header and before
 288   // the end of the current unit.
 289   bool TypeOffsetOK =
 290       !isTypeUnit()
 291           ? true
 292           : TypeOffset >= Size &&
 293                 TypeOffset < getLength() + getUnitLengthFieldByteSize();
 294   bool LengthOK = debug_info.isValidOffset(getNextUnitOffset() - 1);
 295   bool VersionOK = DWARFContext::isSupportedVersion(getVersion());
 296   bool AddrSizeOK = getAddressByteSize() == 4 || getAddressByteSize() == 8;
 297
 298   if (!LengthOK || !VersionOK || !AddrSizeOK || !TypeOffsetOK)
 299     return false;
 300
 301   // Keep track of the highest DWARF version we encounter across all units.
 302   Context.setMaxVersionIfGreater(getVersion());
 303   return true;
 304 }
 305
 306 // Parse the rangelist table header, including the optional array of offsets
 307 // following it (DWARF v5 and later).
 308 static Expected<DWARFDebugRnglistTable>
 309 parseRngListTableHeader(DWARFDataExtractor &DA, uint64_t Offset) {
 310   // TODO: Support DWARF64
 311   // We are expected to be called with Offset 0 or pointing just past the table
 312   // header, which is 12 bytes long for DWARF32.
 313   if (Offset > 0) {
 314     if (Offset < 12U)
 315       return createStringError(errc::invalid_argument, "Did not detect a valid"
 316                                " range list table with base = 0x%" PRIx64,
 317                                Offset);
 318     Offset -= 12U;
 319   }
 320   llvm::DWARFDebugRnglistTable Table;
 321   if (Error E = Table.extractHeaderAndOffsets(DA, &Offset))
 322     return std::move(E);
 323   return Table;
 324 }
 325
 326 Error DWARFUnit::extractRangeList(uint64_t RangeListOffset,
 327                                   DWARFDebugRangeList &RangeList) const {
 328   // Require that compile unit is extracted.
 329   assert(!DieArray.empty());
 330   DWARFDataExtractor RangesData(Context.getDWARFObj(), *RangeSection,
 331                                 isLittleEndian, getAddressByteSize());
 332   uint64_t ActualRangeListOffset = RangeSectionBase + RangeListOffset;
 333   return RangeList.extract(RangesData, &ActualRangeListOffset);
 334 }
 335
 336 void DWARFUnit::clear() {
 337   Abbrevs = nullptr;
 338   BaseAddr.reset();
 339   RangeSectionBase = 0;
 340   AddrOffsetSectionBase = 0;
 341   clearDIEs(false);
 342   DWO.reset();
 343 }
 344
 345 const char *DWARFUnit::getCompilationDir() {
 346   return dwarf::toString(getUnitDIE().find(DW_AT_comp_dir), nullptr);
 347 }
 348
 349 void DWARFUnit::extractDIEsToVector(
 350     bool AppendCUDie, bool AppendNonCUDies,
 351     std::vector<DWARFDebugInfoEntry> &Dies) const {
 352   if (!AppendCUDie && !AppendNonCUDies)
 353     return;
 354
 355   // Set the offset to that of the first DIE and calculate the start of the
 356   // next compilation unit header.
 357   uint64_t DIEOffset = getOffset() + getHeaderSize();
 358   uint64_t NextCUOffset = getNextUnitOffset();
 359   DWARFDebugInfoEntry DIE;
 360   DWARFDataExtractor DebugInfoData = getDebugInfoExtractor();
 361   uint32_t Depth = 0;
 362   bool IsCUDie = true;
 363
 364   while (DIE.extractFast(*this, &DIEOffset, DebugInfoData, NextCUOffset,
 365                          Depth)) {
 366     if (IsCUDie) {
 367       if (AppendCUDie)
 368         Dies.push_back(DIE);
 369       if (!AppendNonCUDies)
 370         break;
 371       // The average bytes per DIE entry has been seen to be
 372       // around 14-20 so let's pre-reserve the needed memory for
 373       // our DIE entries accordingly.
 374       Dies.reserve(Dies.size() + getDebugInfoSize() / 14);
 375       IsCUDie = false;
 376     } else {
 377       Dies.push_back(DIE);
 378     }
 379
 380     if (const DWARFAbbreviationDeclaration *AbbrDecl =
 381             DIE.getAbbreviationDeclarationPtr()) {
 382       // Normal DIE
 383       if (AbbrDecl->hasChildren())
 384         ++Depth;
 385     } else {
 386       // NULL DIE.
 387       if (Depth > 0)
 388         --Depth;
 389       if (Depth == 0)
 390         break;  // We are done with this compile unit!
 391     }
 392   }
 393
 394   // Give a little bit of info if we encounter corrupt DWARF (our offset
 395   // should always terminate at or before the start of the next compilation
 396   // unit header).
 397   if (DIEOffset > NextCUOffset)
 398     WithColor::warning() << format("DWARF compile unit extends beyond its "
 399                                    "bounds cu 0x%8.8" PRIx64 " "
 400                                    "at 0x%8.8" PRIx64 "\n",
 401                                    getOffset(), DIEOffset);
 402 }
 403
 404 void DWARFUnit::extractDIEsIfNeeded(bool CUDieOnly) {
 405   if (Error e = tryExtractDIEsIfNeeded(CUDieOnly))
 406     WithColor::error() << toString(std::move(e));
 407 }
 408
 409 Error DWARFUnit::tryExtractDIEsIfNeeded(bool CUDieOnly) {
 410   if ((CUDieOnly && !DieArray.empty()) ||
 411       DieArray.size() > 1)
 412     return Error::success(); // Already parsed.
 413
 414   bool HasCUDie = !DieArray.empty();
 415   extractDIEsToVector(!HasCUDie, !CUDieOnly, DieArray);
 416
 417   if (DieArray.empty())
 418     return Error::success();
 419
 420   // If CU DIE was just parsed, copy several attribute values from it.
 421   if (HasCUDie)
 422     return Error::success();
 423
 424   DWARFDie UnitDie(this, &DieArray[0]);
 425   if (Optional<uint64_t> DWOId = toUnsigned(UnitDie.find(DW_AT_GNU_dwo_id)))
 426     Header.setDWOId(*DWOId);
 427   if (!IsDWO) {
 428     assert(AddrOffsetSectionBase == 0);
 429     assert(RangeSectionBase == 0);
 430     AddrOffsetSectionBase = toSectionOffset(UnitDie.find(DW_AT_addr_base), 0);
 431     if (!AddrOffsetSectionBase)
 432       AddrOffsetSectionBase =
 433           toSectionOffset(UnitDie.find(DW_AT_GNU_addr_base), 0);
 434     RangeSectionBase = toSectionOffset(UnitDie.find(DW_AT_rnglists_base), 0);
 435   }
 436
 437   // In general, in DWARF v5 and beyond we derive the start of the unit's
 438   // contribution to the string offsets table from the unit DIE's
 439   // DW_AT_str_offsets_base attribute. Split DWARF units do not use this
 440   // attribute, so we assume that there is a contribution to the string
 441   // offsets table starting at offset 0 of the debug_str_offsets.dwo section.
 442   // In both cases we need to determine the format of the contribution,
 443   // which may differ from the unit's format.
 444   DWARFDataExtractor DA(Context.getDWARFObj(), StringOffsetSection,
 445                         isLittleEndian, 0);
 446   if (IsDWO || getVersion() >= 5) {
 447     auto StringOffsetOrError =
 448         IsDWO ? determineStringOffsetsTableContributionDWO(DA)
 449               : determineStringOffsetsTableContribution(DA);
 450     if (!StringOffsetOrError)
 451       return createStringError(errc::invalid_argument,
 452                                "invalid reference to or invalid content in "
 453                                ".debug_str_offsets[.dwo]: " +
 454                                    toString(StringOffsetOrError.takeError()));
 455
 456     StringOffsetsTableContribution = *StringOffsetOrError;
 457   }
 458
 459   // DWARF v5 uses the .debug_rnglists and .debug_rnglists.dwo sections to
 460   // describe address ranges.
 461   if (getVersion() >= 5) {
 462     if (IsDWO)
 463       setRangesSection(&Context.getDWARFObj().getRnglistsDWOSection(), 0);
 464     else
 465       setRangesSection(&Context.getDWARFObj().getRnglistsSection(),
 466                        toSectionOffset(UnitDie.find(DW_AT_rnglists_base), 0));
 467     if (RangeSection->Data.size()) {
 468       // Parse the range list table header. Individual range lists are
 469       // extracted lazily.
 470       DWARFDataExtractor RangesDA(Context.getDWARFObj(), *RangeSection,
 471                                   isLittleEndian, 0);
 472       auto TableOrError =
 473               parseRngListTableHeader(RangesDA, RangeSectionBase);
 474       if (!TableOrError)
 475         return createStringError(errc::invalid_argument,
 476                                  "parsing a range list table: " +
 477                                      toString(TableOrError.takeError()));
 478
 479       RngListTable = TableOrError.get();
 480
 481       // In a split dwarf unit, there is no DW_AT_rnglists_base attribute.
 482       // Adjust RangeSectionBase to point past the table header.
 483       if (IsDWO && RngListTable)
 484         RangeSectionBase = RngListTable->getHeaderSize();
 485     }
 486   }
 487
 488   // Don't fall back to DW_AT_GNU_ranges_base: it should be ignored for
 489   // skeleton CU DIE, so that DWARF users not aware of it are not broken.
 490   return Error::success();
 491 }
 492
 493 bool DWARFUnit::parseDWO() {
 494   if (IsDWO)
 495     return false;
 496   if (DWO.get())
 497     return false;
 498   DWARFDie UnitDie = getUnitDIE();
 499   if (!UnitDie)
 500     return false;
 501   auto DWOFileName = dwarf::toString(UnitDie.find(DW_AT_GNU_dwo_name));
 502   if (!DWOFileName)
 503     return false;
 504   auto CompilationDir = dwarf::toString(UnitDie.find(DW_AT_comp_dir));
 505   SmallString<16> AbsolutePath;
 506   if (sys::path::is_relative(*DWOFileName) && CompilationDir &&
 507       *CompilationDir) {
 508     sys::path::append(AbsolutePath, *CompilationDir);
 509   }
 510   sys::path::append(AbsolutePath, *DWOFileName);
 511   auto DWOId = getDWOId();
 512   if (!DWOId)
 513     return false;
 514   auto DWOContext = Context.getDWOContext(AbsolutePath);
 515   if (!DWOContext)
 516     return false;
 517
 518   DWARFCompileUnit *DWOCU = DWOContext->getDWOCompileUnitForHash(*DWOId);
 519   if (!DWOCU)
 520     return false;
 521   DWO = std::shared_ptr<DWARFCompileUnit>(std::move(DWOContext), DWOCU);
 522   // Share .debug_addr and .debug_ranges section with compile unit in .dwo
 523   DWO->setAddrOffsetSection(AddrOffsetSection, AddrOffsetSectionBase);
 524   if (getVersion() >= 5) {
 525     DWO->setRangesSection(&Context.getDWARFObj().getRnglistsDWOSection(), 0);
 526     DWARFDataExtractor RangesDA(Context.getDWARFObj(), *RangeSection,
 527                                 isLittleEndian, 0);
 528     if (auto TableOrError = parseRngListTableHeader(RangesDA, RangeSectionBase))
 529       DWO->RngListTable = TableOrError.get();
 530     else
 531       WithColor::error() << "parsing a range list table: "
 532                          << toString(TableOrError.takeError())
 533                          << '\n';
 534     if (DWO->RngListTable)
 535       DWO->RangeSectionBase = DWO->RngListTable->getHeaderSize();
 536   } else {
 537     auto DWORangesBase = UnitDie.getRangesBaseAttribute();
 538     DWO->setRangesSection(RangeSection, DWORangesBase ? *DWORangesBase : 0);
 539   }
 540
 541   return true;
 542 }
 543
 544 void DWARFUnit::clearDIEs(bool KeepCUDie) {
 545   if (DieArray.size() > (unsigned)KeepCUDie) {
 546     DieArray.resize((unsigned)KeepCUDie);
 547     DieArray.shrink_to_fit();
 548   }
 549 }
 550
 551 Expected<DWARFAddressRangesVector>
 552 DWARFUnit::findRnglistFromOffset(uint64_t Offset) {
 553   if (getVersion() <= 4) {
 554     DWARFDebugRangeList RangeList;
 555     if (Error E = extractRangeList(Offset, RangeList))
 556       return std::move(E);
 557     return RangeList.getAbsoluteRanges(getBaseAddress());
 558   }
 559   if (RngListTable) {
 560     DWARFDataExtractor RangesData(Context.getDWARFObj(), *RangeSection,
 561                                   isLittleEndian, RngListTable->getAddrSize());
 562     auto RangeListOrError = RngListTable->findList(RangesData, Offset);
 563     if (RangeListOrError)
 564       return RangeListOrError.get().getAbsoluteRanges(getBaseAddress(), *this);
 565     return RangeListOrError.takeError();
 566   }
 567
 568   return createStringError(errc::invalid_argument,
 569                            "missing or invalid range list table");
 570 }
 571
 572 Expected<DWARFAddressRangesVector>
 573 DWARFUnit::findRnglistFromIndex(uint32_t Index) {
 574   if (auto Offset = getRnglistOffset(Index))
 575     return findRnglistFromOffset(*Offset + RangeSectionBase);
 576
 577   if (RngListTable)
 578     return createStringError(errc::invalid_argument,
 579                              "invalid range list table index %d", Index);
 580
 581   return createStringError(errc::invalid_argument,
 582                            "missing or invalid range list table");
 583 }
 584
 585 Expected<DWARFAddressRangesVector> DWARFUnit::collectAddressRanges() {
 586   DWARFDie UnitDie = getUnitDIE();
 587   if (!UnitDie)
 588     return createStringError(errc::invalid_argument, "No unit DIE");
 589
 590   // First, check if unit DIE describes address ranges for the whole unit.
 591   auto CUDIERangesOrError = UnitDie.getAddressRanges();
 592   if (!CUDIERangesOrError)
 593     return createStringError(errc::invalid_argument,
 594                              "decoding address ranges: %s",
 595                              toString(CUDIERangesOrError.takeError()).c_str());
 596   return *CUDIERangesOrError;
 597 }
 598
 599 void DWARFUnit::updateAddressDieMap(DWARFDie Die) {
 600   if (Die.isSubroutineDIE()) {
 601     auto DIERangesOrError = Die.getAddressRanges();
 602     if (DIERangesOrError) {
 603       for (const auto &R : DIERangesOrError.get()) {
 604         // Ignore 0-sized ranges.
 605         if (R.LowPC == R.HighPC)
 606           continue;
 607         auto B = AddrDieMap.upper_bound(R.LowPC);
 608         if (B != AddrDieMap.begin() && R.LowPC < (--B)->second.first) {
 609           // The range is a sub-range of existing ranges, we need to split the
 610           // existing range.
 611           if (R.HighPC < B->second.first)
 612             AddrDieMap[R.HighPC] = B->second;
 613           if (R.LowPC > B->first)
 614             AddrDieMap[B->first].first = R.LowPC;
 615         }
 616         AddrDieMap[R.LowPC] = std::make_pair(R.HighPC, Die);
 617       }
 618     } else
 619       llvm::consumeError(DIERangesOrError.takeError());
 620   }
 621   // Parent DIEs are added to the AddrDieMap prior to the Children DIEs to
 622   // simplify the logic to update AddrDieMap. The child's range will always
 623   // be equal or smaller than the parent's range. With this assumption, when
 624   // adding one range into the map, it will at most split a range into 3
 625   // sub-ranges.
 626   for (DWARFDie Child = Die.getFirstChild(); Child; Child = Child.getSibling())
 627     updateAddressDieMap(Child);
 628 }
 629
 630 DWARFDie DWARFUnit::getSubroutineForAddress(uint64_t Address) {
 631   extractDIEsIfNeeded(false);
 632   if (AddrDieMap.empty())
 633     updateAddressDieMap(getUnitDIE());
 634   auto R = AddrDieMap.upper_bound(Address);
 635   if (R == AddrDieMap.begin())
 636     return DWARFDie();
 637   // upper_bound's previous item contains Address.
 638   --R;
 639   if (Address >= R->second.first)
 640     return DWARFDie();
 641   return R->second.second;
 642 }
 643
 644 void
 645 DWARFUnit::getInlinedChainForAddress(uint64_t Address,
 646                                      SmallVectorImpl<DWARFDie> &InlinedChain) {
 647   assert(InlinedChain.empty());
 648   // Try to look for subprogram DIEs in the DWO file.
 649   parseDWO();
 650   // First, find the subroutine that contains the given address (the leaf
 651   // of inlined chain).
 652   DWARFDie SubroutineDIE =
 653       (DWO ? *DWO : *this).getSubroutineForAddress(Address);
 654
 655   if (!SubroutineDIE)
 656     return;
 657
 658   while (!SubroutineDIE.isSubprogramDIE()) {
 659     if (SubroutineDIE.getTag() == DW_TAG_inlined_subroutine)
 660       InlinedChain.push_back(SubroutineDIE);
 661     SubroutineDIE  = SubroutineDIE.getParent();
 662   }
 663   InlinedChain.push_back(SubroutineDIE);
 664 }
 665
 666 const DWARFUnitIndex &llvm::getDWARFUnitIndex(DWARFContext &Context,
 667                                               DWARFSectionKind Kind) {
 668   if (Kind == DW_SECT_INFO)
 669     return Context.getCUIndex();
 670   assert(Kind == DW_SECT_TYPES);
 671   return Context.getTUIndex();
 672 }
 673
 674 DWARFDie DWARFUnit::getParent(const DWARFDebugInfoEntry *Die) {
 675   if (!Die)
 676     return DWARFDie();
 677   const uint32_t Depth = Die->getDepth();
 678   // Unit DIEs always have a depth of zero and never have parents.
 679   if (Depth == 0)
 680     return DWARFDie();
 681   // Depth of 1 always means parent is the compile/type unit.
 682   if (Depth == 1)
 683     return getUnitDIE();
 684   // Look for previous DIE with a depth that is one less than the Die's depth.
 685   const uint32_t ParentDepth = Depth - 1;
 686   for (uint32_t I = getDIEIndex(Die) - 1; I > 0; --I) {
 687     if (DieArray[I].getDepth() == ParentDepth)
 688       return DWARFDie(this, &DieArray[I]);
 689   }
 690   return DWARFDie();
 691 }
 692
 693 DWARFDie DWARFUnit::getSibling(const DWARFDebugInfoEntry *Die) {
 694   if (!Die)
 695     return DWARFDie();
 696   uint32_t Depth = Die->getDepth();
 697   // Unit DIEs always have a depth of zero and never have siblings.
 698   if (Depth == 0)
 699     return DWARFDie();
 700   // NULL DIEs don't have siblings.
 701   if (Die->getAbbreviationDeclarationPtr() == nullptr)
 702     return DWARFDie();
 703
 704   // Find the next DIE whose depth is the same as the Die's depth.
 705   for (size_t I = getDIEIndex(Die) + 1, EndIdx = DieArray.size(); I < EndIdx;
 706        ++I) {
 707     if (DieArray[I].getDepth() == Depth)
 708       return DWARFDie(this, &DieArray[I]);
 709   }
 710   return DWARFDie();
 711 }
 712
 713 DWARFDie DWARFUnit::getPreviousSibling(const DWARFDebugInfoEntry *Die) {
 714   if (!Die)
 715     return DWARFDie();
 716   uint32_t Depth = Die->getDepth();
 717   // Unit DIEs always have a depth of zero and never have siblings.
 718   if (Depth == 0)
 719     return DWARFDie();
 720
 721   // Find the previous DIE whose depth is the same as the Die's depth.
 722   for (size_t I = getDIEIndex(Die); I > 0;) {
 723     --I;
 724     if (DieArray[I].getDepth() == Depth - 1)
 725       return DWARFDie();
 726     if (DieArray[I].getDepth() == Depth)
 727       return DWARFDie(this, &DieArray[I]);
 728   }
 729   return DWARFDie();
 730 }
 731
 732 DWARFDie DWARFUnit::getFirstChild(const DWARFDebugInfoEntry *Die) {
 733   if (!Die->hasChildren())
 734     return DWARFDie();
 735
 736   // We do not want access out of bounds when parsing corrupted debug data.
 737   size_t I = getDIEIndex(Die) + 1;
 738   if (I >= DieArray.size())
 739     return DWARFDie();
 740   return DWARFDie(this, &DieArray[I]);
 741 }
 742
 743 DWARFDie DWARFUnit::getLastChild(const DWARFDebugInfoEntry *Die) {
 744   if (!Die->hasChildren())
 745     return DWARFDie();
 746
 747   uint32_t Depth = Die->getDepth();
 748   for (size_t I = getDIEIndex(Die) + 1, EndIdx = DieArray.size(); I < EndIdx;
 749        ++I) {
 750     if (DieArray[I].getDepth() == Depth + 1 &&
 751         DieArray[I].getTag() == dwarf::DW_TAG_null)
 752       return DWARFDie(this, &DieArray[I]);
 753     assert(DieArray[I].getDepth() > Depth && "Not processing children?");
 754   }
 755   return DWARFDie();
 756 }
 757
 758 const DWARFAbbreviationDeclarationSet *DWARFUnit::getAbbreviations() const {
 759   if (!Abbrevs)
 760     Abbrevs = Abbrev->getAbbreviationDeclarationSet(Header.getAbbrOffset());
 761   return Abbrevs;
 762 }
 763
 764 llvm::Optional<object::SectionedAddress> DWARFUnit::getBaseAddress() {
 765   if (BaseAddr)
 766     return BaseAddr;
 767
 768   DWARFDie UnitDie = getUnitDIE();
 769   Optional<DWARFFormValue> PC = UnitDie.find({DW_AT_low_pc, DW_AT_entry_pc});
 770   BaseAddr = toSectionedAddress(PC);
 771   return BaseAddr;
 772 }
 773
 774 Expected<StrOffsetsContributionDescriptor>
 775 StrOffsetsContributionDescriptor::validateContributionSize(
 776     DWARFDataExtractor &DA) {
 777   uint8_t EntrySize = getDwarfOffsetByteSize();
 778   // In order to ensure that we don't read a partial record at the end of
 779   // the section we validate for a multiple of the entry size.
 780   uint64_t ValidationSize = alignTo(Size, EntrySize);
 781   // Guard against overflow.
 782   if (ValidationSize >= Size)
 783     if (DA.isValidOffsetForDataOfSize((uint32_t)Base, ValidationSize))
 784       return *this;
 785   return createStringError(errc::invalid_argument, "length exceeds section size");
 786 }
 787
 788 // Look for a DWARF64-formatted contribution to the string offsets table
 789 // starting at a given offset and record it in a descriptor.
 790 static Expected<StrOffsetsContributionDescriptor>
 791 parseDWARF64StringOffsetsTableHeader(DWARFDataExtractor &DA, uint64_t Offset) {
 792   if (!DA.isValidOffsetForDataOfSize(Offset, 16))
 793     return createStringError(errc::invalid_argument, "section offset exceeds section size");
 794
 795   if (DA.getU32(&Offset) != dwarf::DW_LENGTH_DWARF64)
 796     return createStringError(errc::invalid_argument, "32 bit contribution referenced from a 64 bit unit");
 797
 798   uint64_t Size = DA.getU64(&Offset);
 799   uint8_t Version = DA.getU16(&Offset);
 800   (void)DA.getU16(&Offset); // padding
 801   // The encoded length includes the 2-byte version field and the 2-byte
 802   // padding, so we need to subtract them out when we populate the descriptor.
 803   return StrOffsetsContributionDescriptor(Offset, Size - 4, Version, DWARF64);
 804 }
 805
 806 // Look for a DWARF32-formatted contribution to the string offsets table
 807 // starting at a given offset and record it in a descriptor.
 808 static Expected<StrOffsetsContributionDescriptor>
 809 parseDWARF32StringOffsetsTableHeader(DWARFDataExtractor &DA, uint64_t Offset) {
 810   if (!DA.isValidOffsetForDataOfSize(Offset, 8))
 811     return createStringError(errc::invalid_argument, "section offset exceeds section size");
 812
 813   uint32_t ContributionSize = DA.getU32(&Offset);
 814   if (ContributionSize >= dwarf::DW_LENGTH_lo_reserved)
 815     return createStringError(errc::invalid_argument, "invalid length");
 816
 817   uint8_t Version = DA.getU16(&Offset);
 818   (void)DA.getU16(&Offset); // padding
 819   // The encoded length includes the 2-byte version field and the 2-byte
 820   // padding, so we need to subtract them out when we populate the descriptor.
 821   return StrOffsetsContributionDescriptor(Offset, ContributionSize - 4, Version,
 822                                           DWARF32);
 823 }
 824
 825 static Expected<StrOffsetsContributionDescriptor>
 826 parseDWARFStringOffsetsTableHeader(DWARFDataExtractor &DA,
 827                                    llvm::dwarf::DwarfFormat Format,
 828                                    uint64_t Offset) {
 829   StrOffsetsContributionDescriptor Desc;
 830   switch (Format) {
 831   case dwarf::DwarfFormat::DWARF64: {
 832     if (Offset < 16)
 833       return createStringError(errc::invalid_argument, "insufficient space for 64 bit header prefix");
 834     auto DescOrError = parseDWARF64StringOffsetsTableHeader(DA, Offset - 16);
 835     if (!DescOrError)
 836       return DescOrError.takeError();
 837     Desc = *DescOrError;
 838     break;
 839   }
 840   case dwarf::DwarfFormat::DWARF32: {
 841     if (Offset < 8)
 842       return createStringError(errc::invalid_argument, "insufficient space for 32 bit header prefix");
 843     auto DescOrError = parseDWARF32StringOffsetsTableHeader(DA, Offset - 8);
 844     if (!DescOrError)
 845       return DescOrError.takeError();
 846     Desc = *DescOrError;
 847     break;
 848   }
 849   }
 850   return Desc.validateContributionSize(DA);
 851 }
 852
 853 Expected<Optional<StrOffsetsContributionDescriptor>>
 854 DWARFUnit::determineStringOffsetsTableContribution(DWARFDataExtractor &DA) {
 855   uint64_t Offset;
 856   if (IsDWO) {
 857     Offset = 0;
 858     if (DA.getData().data() == nullptr)
 859       return None;
 860   } else {
 861     auto OptOffset = toSectionOffset(getUnitDIE().find(DW_AT_str_offsets_base));
 862     if (!OptOffset)
 863       return None;
 864     Offset = *OptOffset;
 865   }
 866   auto DescOrError = parseDWARFStringOffsetsTableHeader(DA, Header.getFormat(), Offset);
 867   if (!DescOrError)
 868     return DescOrError.takeError();
 869   return *DescOrError;
 870 }
 871
 872 Expected<Optional<StrOffsetsContributionDescriptor>>
 873 DWARFUnit::determineStringOffsetsTableContributionDWO(DWARFDataExtractor & DA) {
 874   uint64_t Offset = 0;
 875   auto IndexEntry = Header.getIndexEntry();
 876   const auto *C =
 877       IndexEntry ? IndexEntry->getOffset(DW_SECT_STR_OFFSETS) : nullptr;
 878   if (C)
 879     Offset = C->Offset;
 880   if (getVersion() >= 5) {
 881     if (DA.getData().data() == nullptr)
 882       return None;
 883     Offset += Header.getFormat() == dwarf::DwarfFormat::DWARF32 ? 8 : 16;
 884     // Look for a valid contribution at the given offset.
 885     auto DescOrError = parseDWARFStringOffsetsTableHeader(DA, Header.getFormat(), Offset);
 886     if (!DescOrError)
 887       return DescOrError.takeError();
 888     return *DescOrError;
 889   }
 890   // Prior to DWARF v5, we derive the contribution size from the
 891   // index table (in a package file). In a .dwo file it is simply
 892   // the length of the string offsets section.
 893   if (!IndexEntry)
 894     return {
 895         Optional<StrOffsetsContributionDescriptor>(
 896             {0, StringOffsetSection.Data.size(), 4, DWARF32})};
 897   if (C)
 898     return {Optional<StrOffsetsContributionDescriptor>(
 899         {C->Offset, C->Length, 4, DWARF32})};
 900   return None;
 901 }