1 //===- DWARFUnit.h ----------------------------------------------*- C++ -*-===//
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 #ifndef LLVM_DEBUGINFO_DWARF_DWARFUNIT_H
10 #define LLVM_DEBUGINFO_DWARF_DWARFUNIT_H
11 
12 #include "llvm/ADT/Optional.h"
13 #include "llvm/ADT/STLExtras.h"
14 #include "llvm/ADT/SmallVector.h"
15 #include "llvm/ADT/StringRef.h"
16 #include "llvm/ADT/iterator_range.h"
17 #include "llvm/BinaryFormat/Dwarf.h"
18 #include "llvm/DebugInfo/DWARF/DWARFDebugInfoEntry.h"
19 #include "llvm/DebugInfo/DWARF/DWARFDebugLoc.h"
20 #include "llvm/DebugInfo/DWARF/DWARFDebugRangeList.h"
21 #include "llvm/DebugInfo/DWARF/DWARFDebugRnglists.h"
22 #include "llvm/DebugInfo/DWARF/DWARFDie.h"
23 #include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
24 #include "llvm/DebugInfo/DWARF/DWARFRelocMap.h"
25 #include "llvm/DebugInfo/DWARF/DWARFSection.h"
26 #include "llvm/DebugInfo/DWARF/DWARFUnitIndex.h"
27 #include "llvm/Support/DataExtractor.h"
28 #include <algorithm>
29 #include <cassert>
30 #include <cstddef>
31 #include <cstdint>
32 #include <map>
33 #include <memory>
34 #include <utility>
35 #include <vector>
36 
37 namespace llvm {
38 
39 class DWARFAbbreviationDeclarationSet;
40 class DWARFContext;
41 class DWARFDebugAbbrev;
42 class DWARFUnit;
43 
44 /// Base class describing the header of any kind of "unit."  Some information
45 /// is specific to certain unit types.  We separate this class out so we can
46 /// parse the header before deciding what specific kind of unit to construct.
47 class DWARFUnitHeader {
48   // Offset within section.
49   uint64_t Offset = 0;
50   // Version, address size, and DWARF format.
51   dwarf::FormParams FormParams;
52   uint64_t Length = 0;
53   uint64_t AbbrOffset = 0;
54 
55   // For DWO units only.
56   const DWARFUnitIndex::Entry *IndexEntry = nullptr;
57 
58   // For type units only.
59   uint64_t TypeHash = 0;
60   uint64_t TypeOffset = 0;
61 
62   // For v5 split or skeleton compile units only.
63   Optional<uint64_t> DWOId;
64 
65   // Unit type as parsed, or derived from the section kind.
66   uint8_t UnitType = 0;
67 
68   // Size as parsed. uint8_t for compactness.
69   uint8_t Size = 0;
70 
71 public:
72   /// Parse a unit header from \p debug_info starting at \p offset_ptr.
73   /// Note that \p SectionKind is used as a hint to guess the unit type
74   /// for DWARF formats prior to DWARFv5. In DWARFv5 the unit type is
75   /// explicitly defined in the header and the hint is ignored.
76   bool extract(DWARFContext &Context, const DWARFDataExtractor &debug_info,
77                uint64_t *offset_ptr, DWARFSectionKind SectionKind);
78   // For units in DWARF Package File, remember the index entry and update
79   // the abbreviation offset read by extract().
80   bool applyIndexEntry(const DWARFUnitIndex::Entry *Entry);
81   uint64_t getOffset() const { return Offset; }
82   const dwarf::FormParams &getFormParams() const { return FormParams; }
83   uint16_t getVersion() const { return FormParams.Version; }
84   dwarf::DwarfFormat getFormat() const { return FormParams.Format; }
85   uint8_t getAddressByteSize() const { return FormParams.AddrSize; }
86   uint8_t getRefAddrByteSize() const { return FormParams.getRefAddrByteSize(); }
87   uint8_t getDwarfOffsetByteSize() const {
88     return FormParams.getDwarfOffsetByteSize();
89   }
90   uint64_t getLength() const { return Length; }
91   uint64_t getAbbrOffset() const { return AbbrOffset; }
92   Optional<uint64_t> getDWOId() const { return DWOId; }
93   void setDWOId(uint64_t Id) {
94     assert((!DWOId || *DWOId == Id) && "setting DWOId to a different value");
95     DWOId = Id;
96   }
97   const DWARFUnitIndex::Entry *getIndexEntry() const { return IndexEntry; }
98   uint64_t getTypeHash() const { return TypeHash; }
99   uint64_t getTypeOffset() const { return TypeOffset; }
100   uint8_t getUnitType() const { return UnitType; }
101   bool isTypeUnit() const {
102     return UnitType == dwarf::DW_UT_type || UnitType == dwarf::DW_UT_split_type;
103   }
104   uint8_t getSize() const { return Size; }
105   uint8_t getUnitLengthFieldByteSize() const {
106     return dwarf::getUnitLengthFieldByteSize(FormParams.Format);
107   }
108   uint64_t getNextUnitOffset() const {
109     return Offset + Length + getUnitLengthFieldByteSize();
110   }
111 };
112 
113 const DWARFUnitIndex &getDWARFUnitIndex(DWARFContext &Context,
114                                         DWARFSectionKind Kind);
115 
116 bool isCompileUnit(const std::unique_ptr<DWARFUnit> &U);
117 
118 /// Describe a collection of units. Intended to hold all units either from
119 /// .debug_info and .debug_types, or from .debug_info.dwo and .debug_types.dwo.
120 class DWARFUnitVector final : public SmallVector<std::unique_ptr<DWARFUnit>, 1> {
121   std::function<std::unique_ptr<DWARFUnit>(uint64_t, DWARFSectionKind,
122                                            const DWARFSection *,
123                                            const DWARFUnitIndex::Entry *)>
124       Parser;
125   int NumInfoUnits = -1;
126 
127 public:
128   using UnitVector = SmallVectorImpl<std::unique_ptr<DWARFUnit>>;
129   using iterator = typename UnitVector::iterator;
130   using iterator_range = llvm::iterator_range<typename UnitVector::iterator>;
131 
132   using compile_unit_range =
133       decltype(make_filter_range(std::declval<iterator_range>(), isCompileUnit));
134 
135   DWARFUnit *getUnitForOffset(uint64_t Offset) const;
136   DWARFUnit *getUnitForIndexEntry(const DWARFUnitIndex::Entry &E);
137 
138   /// Read units from a .debug_info or .debug_types section.  Calls made
139   /// before finishedInfoUnits() are assumed to be for .debug_info sections,
140   /// calls after finishedInfoUnits() are for .debug_types sections.  Caller
141   /// must not mix calls to addUnitsForSection and addUnitsForDWOSection.
142   void addUnitsForSection(DWARFContext &C, const DWARFSection &Section,
143                           DWARFSectionKind SectionKind);
144   /// Read units from a .debug_info.dwo or .debug_types.dwo section.  Calls
145   /// made before finishedInfoUnits() are assumed to be for .debug_info.dwo
146   /// sections, calls after finishedInfoUnits() are for .debug_types.dwo
147   /// sections.  Caller must not mix calls to addUnitsForSection and
148   /// addUnitsForDWOSection.
149   void addUnitsForDWOSection(DWARFContext &C, const DWARFSection &DWOSection,
150                              DWARFSectionKind SectionKind, bool Lazy = false);
151 
152   /// Add an existing DWARFUnit to this UnitVector. This is used by the DWARF
153   /// verifier to process unit separately.
154   DWARFUnit *addUnit(std::unique_ptr<DWARFUnit> Unit);
155 
156   /// Returns number of all units held by this instance.
157   unsigned getNumUnits() const { return size(); }
158   /// Returns number of units from all .debug_info[.dwo] sections.
159   unsigned getNumInfoUnits() const {
160     return NumInfoUnits == -1 ? size() : NumInfoUnits;
161   }
162   /// Returns number of units from all .debug_types[.dwo] sections.
163   unsigned getNumTypesUnits() const { return size() - NumInfoUnits; }
164   /// Indicate that parsing .debug_info[.dwo] is done, and remaining units
165   /// will be from .debug_types[.dwo].
166   void finishedInfoUnits() { NumInfoUnits = size(); }
167 
168 private:
169   void addUnitsImpl(DWARFContext &Context, const DWARFObject &Obj,
170                     const DWARFSection &Section, const DWARFDebugAbbrev *DA,
171                     const DWARFSection *RS, const DWARFSection *LocSection,
172                     StringRef SS, const DWARFSection &SOS,
173                     const DWARFSection *AOS, const DWARFSection &LS, bool LE,
174                     bool IsDWO, bool Lazy, DWARFSectionKind SectionKind);
175 };
176 
177 /// Represents base address of the CU.
178 /// Represents a unit's contribution to the string offsets table.
179 struct StrOffsetsContributionDescriptor {
180   uint64_t Base = 0;
181   /// The contribution size not including the header.
182   uint64_t Size = 0;
183   /// Format and version.
184   dwarf::FormParams FormParams = {0, 0, dwarf::DwarfFormat::DWARF32};
185 
186   StrOffsetsContributionDescriptor(uint64_t Base, uint64_t Size,
187                                    uint8_t Version, dwarf::DwarfFormat Format)
188       : Base(Base), Size(Size), FormParams({Version, 0, Format}) {}
189   StrOffsetsContributionDescriptor() = default;
190 
191   uint8_t getVersion() const { return FormParams.Version; }
192   dwarf::DwarfFormat getFormat() const { return FormParams.Format; }
193   uint8_t getDwarfOffsetByteSize() const {
194     return FormParams.getDwarfOffsetByteSize();
195   }
196   /// Determine whether a contribution to the string offsets table is
197   /// consistent with the relevant section size and that its length is
198   /// a multiple of the size of one of its entries.
199   Expected<StrOffsetsContributionDescriptor>
200   validateContributionSize(DWARFDataExtractor &DA);
201 };
202 
203 class DWARFUnit {
204   DWARFContext &Context;
205   /// Section containing this DWARFUnit.
206   const DWARFSection &InfoSection;
207 
208   DWARFUnitHeader Header;
209   const DWARFDebugAbbrev *Abbrev;
210   const DWARFSection *RangeSection;
211   uint64_t RangeSectionBase;
212   uint64_t LocSectionBase;
213 
214   /// Location table of this unit.
215   std::unique_ptr<DWARFLocationTable> LocTable;
216 
217   const DWARFSection &LineSection;
218   StringRef StringSection;
219   const DWARFSection &StringOffsetSection;
220   const DWARFSection *AddrOffsetSection;
221   Optional<uint64_t> AddrOffsetSectionBase;
222   bool isLittleEndian;
223   bool IsDWO;
224   const DWARFUnitVector &UnitVector;
225 
226   /// Start, length, and DWARF format of the unit's contribution to the string
227   /// offsets table (DWARF v5).
228   Optional<StrOffsetsContributionDescriptor> StringOffsetsTableContribution;
229 
230   mutable const DWARFAbbreviationDeclarationSet *Abbrevs;
231   llvm::Optional<object::SectionedAddress> BaseAddr;
232   /// The compile unit debug information entry items.
233   std::vector<DWARFDebugInfoEntry> DieArray;
234 
235   /// Map from range's start address to end address and corresponding DIE.
236   /// IntervalMap does not support range removal, as a result, we use the
237   /// std::map::upper_bound for address range lookup.
238   std::map<uint64_t, std::pair<uint64_t, DWARFDie>> AddrDieMap;
239 
240   using die_iterator_range =
241       iterator_range<std::vector<DWARFDebugInfoEntry>::iterator>;
242 
243   std::shared_ptr<DWARFUnit> DWO;
244 
245   uint32_t getDIEIndex(const DWARFDebugInfoEntry *Die) {
246     auto First = DieArray.data();
247     assert(Die >= First && Die < First + DieArray.size());
248     return Die - First;
249   }
250 
251 protected:
252   const DWARFUnitHeader &getHeader() const { return Header; }
253 
254   /// Size in bytes of the parsed unit header.
255   uint32_t getHeaderSize() const { return Header.getSize(); }
256 
257   /// Find the unit's contribution to the string offsets table and determine its
258   /// length and form. The given offset is expected to be derived from the unit
259   /// DIE's DW_AT_str_offsets_base attribute.
260   Expected<Optional<StrOffsetsContributionDescriptor>>
261   determineStringOffsetsTableContribution(DWARFDataExtractor &DA);
262 
263   /// Find the unit's contribution to the string offsets table and determine its
264   /// length and form. The given offset is expected to be 0 in a dwo file or,
265   /// in a dwp file, the start of the unit's contribution to the string offsets
266   /// table section (as determined by the index table).
267   Expected<Optional<StrOffsetsContributionDescriptor>>
268   determineStringOffsetsTableContributionDWO(DWARFDataExtractor &DA);
269 
270 public:
271   DWARFUnit(DWARFContext &Context, const DWARFSection &Section,
272             const DWARFUnitHeader &Header, const DWARFDebugAbbrev *DA,
273             const DWARFSection *RS, const DWARFSection *LocSection,
274             StringRef SS, const DWARFSection &SOS, const DWARFSection *AOS,
275             const DWARFSection &LS, bool LE, bool IsDWO,
276             const DWARFUnitVector &UnitVector);
277 
278   virtual ~DWARFUnit();
279 
280   bool isDWOUnit() const { return IsDWO; }
281   DWARFContext& getContext() const { return Context; }
282   const DWARFSection &getInfoSection() const { return InfoSection; }
283   uint64_t getOffset() const { return Header.getOffset(); }
284   const dwarf::FormParams &getFormParams() const {
285     return Header.getFormParams();
286   }
287   uint16_t getVersion() const { return Header.getVersion(); }
288   uint8_t getAddressByteSize() const { return Header.getAddressByteSize(); }
289   uint8_t getRefAddrByteSize() const { return Header.getRefAddrByteSize(); }
290   uint8_t getDwarfOffsetByteSize() const {
291     return Header.getDwarfOffsetByteSize();
292   }
293   uint64_t getLength() const { return Header.getLength(); }
294   dwarf::DwarfFormat getFormat() const { return Header.getFormat(); }
295   uint8_t getUnitType() const { return Header.getUnitType(); }
296   bool isTypeUnit() const { return Header.isTypeUnit(); }
297   uint64_t getAbbrOffset() const { return Header.getAbbrOffset(); }
298   uint64_t getNextUnitOffset() const { return Header.getNextUnitOffset(); }
299   const DWARFSection &getLineSection() const { return LineSection; }
300   StringRef getStringSection() const { return StringSection; }
301   const DWARFSection &getStringOffsetSection() const {
302     return StringOffsetSection;
303   }
304 
305   void setAddrOffsetSection(const DWARFSection *AOS, uint64_t Base) {
306     AddrOffsetSection = AOS;
307     AddrOffsetSectionBase = Base;
308   }
309 
310   /// Recursively update address to Die map.
311   void updateAddressDieMap(DWARFDie Die);
312 
313   void setRangesSection(const DWARFSection *RS, uint64_t Base) {
314     RangeSection = RS;
315     RangeSectionBase = Base;
316   }
317 
318   uint64_t getLocSectionBase() const {
319     return LocSectionBase;
320   }
321 
322   Optional<object::SectionedAddress>
323   getAddrOffsetSectionItem(uint32_t Index) const;
324   Optional<uint64_t> getStringOffsetSectionItem(uint32_t Index) const;
325 
326   DWARFDataExtractor getDebugInfoExtractor() const;
327 
328   DataExtractor getStringExtractor() const {
329     return DataExtractor(StringSection, false, 0);
330   }
331 
332   const DWARFLocationTable &getLocationTable() { return *LocTable; }
333 
334   /// Extract the range list referenced by this compile unit from the
335   /// .debug_ranges section. If the extraction is unsuccessful, an error
336   /// is returned. Successful extraction requires that the compile unit
337   /// has already been extracted.
338   Error extractRangeList(uint64_t RangeListOffset,
339                          DWARFDebugRangeList &RangeList) const;
340   void clear();
341 
342   const Optional<StrOffsetsContributionDescriptor> &
343   getStringOffsetsTableContribution() const {
344     return StringOffsetsTableContribution;
345   }
346 
347   uint8_t getDwarfStringOffsetsByteSize() const {
348     assert(StringOffsetsTableContribution);
349     return StringOffsetsTableContribution->getDwarfOffsetByteSize();
350   }
351 
352   uint64_t getStringOffsetsBase() const {
353     assert(StringOffsetsTableContribution);
354     return StringOffsetsTableContribution->Base;
355   }
356 
357   const DWARFAbbreviationDeclarationSet *getAbbreviations() const;
358 
359   static bool isMatchingUnitTypeAndTag(uint8_t UnitType, dwarf::Tag Tag) {
360     switch (UnitType) {
361     case dwarf::DW_UT_compile:
362       return Tag == dwarf::DW_TAG_compile_unit;
363     case dwarf::DW_UT_type:
364       return Tag == dwarf::DW_TAG_type_unit;
365     case dwarf::DW_UT_partial:
366       return Tag == dwarf::DW_TAG_partial_unit;
367     case dwarf::DW_UT_skeleton:
368       return Tag == dwarf::DW_TAG_skeleton_unit;
369     case dwarf::DW_UT_split_compile:
370     case dwarf::DW_UT_split_type:
371       return dwarf::isUnitType(Tag);
372     }
373     return false;
374   }
375 
376   llvm::Optional<object::SectionedAddress> getBaseAddress();
377 
378   DWARFDie getUnitDIE(bool ExtractUnitDIEOnly = true) {
379     extractDIEsIfNeeded(ExtractUnitDIEOnly);
380     if (DieArray.empty())
381       return DWARFDie();
382     return DWARFDie(this, &DieArray[0]);
383   }
384 
385   DWARFDie getNonSkeletonUnitDIE(bool ExtractUnitDIEOnly = true) {
386     parseDWO();
387     if (DWO)
388       return DWO->getUnitDIE(ExtractUnitDIEOnly);
389     return getUnitDIE(ExtractUnitDIEOnly);
390   }
391 
392   const char *getCompilationDir();
393   Optional<uint64_t> getDWOId() {
394     extractDIEsIfNeeded(/*CUDieOnly*/ true);
395     return getHeader().getDWOId();
396   }
397   void setDWOId(uint64_t NewID) { Header.setDWOId(NewID); }
398 
399   /// Return a vector of address ranges resulting from a (possibly encoded)
400   /// range list starting at a given offset in the appropriate ranges section.
401   Expected<DWARFAddressRangesVector> findRnglistFromOffset(uint64_t Offset);
402 
403   /// Return a vector of address ranges retrieved from an encoded range
404   /// list whose offset is found via a table lookup given an index (DWARF v5
405   /// and later).
406   Expected<DWARFAddressRangesVector> findRnglistFromIndex(uint32_t Index);
407 
408   /// Return a rangelist's offset based on an index. The index designates
409   /// an entry in the rangelist table's offset array and is supplied by
410   /// DW_FORM_rnglistx.
411   Optional<uint64_t> getRnglistOffset(uint32_t Index);
412 
413   Optional<uint64_t> getLoclistOffset(uint32_t Index);
414 
415   Expected<DWARFAddressRangesVector> collectAddressRanges();
416 
417   Expected<DWARFLocationExpressionsVector>
418   findLoclistFromOffset(uint64_t Offset);
419 
420   /// Returns subprogram DIE with address range encompassing the provided
421   /// address. The pointer is alive as long as parsed compile unit DIEs are not
422   /// cleared.
423   DWARFDie getSubroutineForAddress(uint64_t Address);
424 
425   /// getInlinedChainForAddress - fetches inlined chain for a given address.
426   /// Returns empty chain if there is no subprogram containing address. The
427   /// chain is valid as long as parsed compile unit DIEs are not cleared.
428   void getInlinedChainForAddress(uint64_t Address,
429                                  SmallVectorImpl<DWARFDie> &InlinedChain);
430 
431   /// Return the DWARFUnitVector containing this unit.
432   const DWARFUnitVector &getUnitVector() const { return UnitVector; }
433 
434   /// Returns the number of DIEs in the unit. Parses the unit
435   /// if necessary.
436   unsigned getNumDIEs() {
437     extractDIEsIfNeeded(false);
438     return DieArray.size();
439   }
440 
441   /// Return the index of a DIE inside the unit's DIE vector.
442   ///
443   /// It is illegal to call this method with a DIE that hasn't be
444   /// created by this unit. In other word, it's illegal to call this
445   /// method on a DIE that isn't accessible by following
446   /// children/sibling links starting from this unit's getUnitDIE().
447   uint32_t getDIEIndex(const DWARFDie &D) {
448     return getDIEIndex(D.getDebugInfoEntry());
449   }
450 
451   /// Return the DIE object at the given index.
452   DWARFDie getDIEAtIndex(unsigned Index) {
453     assert(Index < DieArray.size());
454     return DWARFDie(this, &DieArray[Index]);
455   }
456 
457   DWARFDie getParent(const DWARFDebugInfoEntry *Die);
458   DWARFDie getSibling(const DWARFDebugInfoEntry *Die);
459   DWARFDie getPreviousSibling(const DWARFDebugInfoEntry *Die);
460   DWARFDie getFirstChild(const DWARFDebugInfoEntry *Die);
461   DWARFDie getLastChild(const DWARFDebugInfoEntry *Die);
462 
463   /// Return the DIE object for a given offset inside the
464   /// unit's DIE vector.
465   ///
466   /// The unit needs to have its DIEs extracted for this method to work.
467   DWARFDie getDIEForOffset(uint64_t Offset) {
468     extractDIEsIfNeeded(false);
469     auto It =
470         llvm::partition_point(DieArray, [=](const DWARFDebugInfoEntry &DIE) {
471           return DIE.getOffset() < Offset;
472         });
473     if (It != DieArray.end() && It->getOffset() == Offset)
474       return DWARFDie(this, &*It);
475     return DWARFDie();
476   }
477 
478   uint32_t getLineTableOffset() const {
479     if (auto IndexEntry = Header.getIndexEntry())
480       if (const auto *Contrib = IndexEntry->getContribution(DW_SECT_LINE))
481         return Contrib->Offset;
482     return 0;
483   }
484 
485   die_iterator_range dies() {
486     extractDIEsIfNeeded(false);
487     return die_iterator_range(DieArray.begin(), DieArray.end());
488   }
489 
490   virtual void dump(raw_ostream &OS, DIDumpOptions DumpOpts) = 0;
491 
492   Error tryExtractDIEsIfNeeded(bool CUDieOnly);
493 
494 private:
495   /// Size in bytes of the .debug_info data associated with this compile unit.
496   size_t getDebugInfoSize() const {
497     return Header.getLength() + Header.getUnitLengthFieldByteSize() -
498            getHeaderSize();
499   }
500 
501   /// extractDIEsIfNeeded - Parses a compile unit and indexes its DIEs if it
502   /// hasn't already been done
503   void extractDIEsIfNeeded(bool CUDieOnly);
504 
505   /// extractDIEsToVector - Appends all parsed DIEs to a vector.
506   void extractDIEsToVector(bool AppendCUDie, bool AppendNonCUDIEs,
507                            std::vector<DWARFDebugInfoEntry> &DIEs) const;
508 
509   /// clearDIEs - Clear parsed DIEs to keep memory usage low.
510   void clearDIEs(bool KeepCUDie);
511 
512   /// parseDWO - Parses .dwo file for current compile unit. Returns true if
513   /// it was actually constructed.
514   bool parseDWO();
515 };
516 
517 inline bool isCompileUnit(const std::unique_ptr<DWARFUnit> &U) {
518   return !U->isTypeUnit();
519 }
520 
521 } // end namespace llvm
522 
523 #endif // LLVM_DEBUGINFO_DWARF_DWARFUNIT_H
524