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