1 //===- DWARFUnit.cpp ------------------------------------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "llvm/DebugInfo/DWARF/DWARFUnit.h"
11 #include "llvm/ADT/SmallString.h"
12 #include "llvm/ADT/StringRef.h"
13 #include "llvm/DebugInfo/DWARF/DWARFAbbreviationDeclaration.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/DWARFDie.h"
18 #include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
19 #include "llvm/Support/DataExtractor.h"
20 #include "llvm/Support/Path.h"
21 #include <algorithm>
22 #include <cassert>
23 #include <cstddef>
24 #include <cstdint>
25 #include <cstdio>
26 #include <utility>
27 #include <vector>
28 
29 using namespace llvm;
30 using namespace dwarf;
31 
32 void DWARFUnitSectionBase::parse(DWARFContext &C, const DWARFSection &Section) {
33   const DWARFObject &D = C.getDWARFObj();
34   parseImpl(C, Section, C.getDebugAbbrev(), &D.getRangeSection(),
35             D.getStringSection(), D.getStringOffsetSection(),
36             &D.getAddrSection(), D.getLineSection(), D.isLittleEndian(), false);
37 }
38 
39 void DWARFUnitSectionBase::parseDWO(DWARFContext &C,
40                                     const DWARFSection &DWOSection,
41                                     DWARFUnitIndex *Index) {
42   const DWARFObject &D = C.getDWARFObj();
43   parseImpl(C, DWOSection, C.getDebugAbbrevDWO(), &D.getRangeDWOSection(),
44             D.getStringDWOSection(), D.getStringOffsetDWOSection(),
45             &D.getAddrSection(), D.getLineDWOSection(), C.isLittleEndian(),
46             true);
47 }
48 
49 DWARFUnit::DWARFUnit(DWARFContext &DC, const DWARFSection &Section,
50                      const DWARFDebugAbbrev *DA, const DWARFSection *RS,
51                      StringRef SS, const DWARFSection &SOS,
52                      const DWARFSection *AOS, const DWARFSection &LS, bool LE,
53                      bool IsDWO, const DWARFUnitSectionBase &UnitSection,
54                      const DWARFUnitIndex::Entry *IndexEntry)
55     : Context(DC), InfoSection(Section), Abbrev(DA), RangeSection(RS),
56       LineSection(LS), StringSection(SS), StringOffsetSection(SOS),
57       AddrOffsetSection(AOS), isLittleEndian(LE), isDWO(IsDWO),
58       UnitSection(UnitSection), IndexEntry(IndexEntry) {
59   clear();
60 }
61 
62 DWARFUnit::~DWARFUnit() = default;
63 
64 DWARFDataExtractor DWARFUnit::getDebugInfoExtractor() const {
65   return DWARFDataExtractor(Context.getDWARFObj(), InfoSection, isLittleEndian,
66                             getAddressByteSize());
67 }
68 
69 bool DWARFUnit::getAddrOffsetSectionItem(uint32_t Index,
70                                                 uint64_t &Result) const {
71   uint32_t Offset = AddrOffsetSectionBase + Index * getAddressByteSize();
72   if (AddrOffsetSection->Data.size() < Offset + getAddressByteSize())
73     return false;
74   DWARFDataExtractor DA(Context.getDWARFObj(), *AddrOffsetSection,
75                         isLittleEndian, getAddressByteSize());
76   Result = DA.getRelocatedAddress(&Offset);
77   return true;
78 }
79 
80 bool DWARFUnit::getStringOffsetSectionItem(uint32_t Index,
81                                            uint64_t &Result) const {
82   unsigned ItemSize = getDwarfOffsetByteSize();
83   uint32_t Offset = StringOffsetSectionBase + Index * ItemSize;
84   if (StringOffsetSection.Data.size() < Offset + ItemSize)
85     return false;
86   DWARFDataExtractor DA(Context.getDWARFObj(), StringOffsetSection,
87                         isLittleEndian, 0);
88   Result = DA.getRelocatedValue(ItemSize, &Offset);
89   return true;
90 }
91 
92 bool DWARFUnit::extractImpl(DataExtractor debug_info, uint32_t *offset_ptr) {
93   Length = debug_info.getU32(offset_ptr);
94   // FIXME: Support DWARF64.
95   FormParams.Format = DWARF32;
96   FormParams.Version = debug_info.getU16(offset_ptr);
97   uint64_t AbbrOffset;
98   if (FormParams.Version >= 5) {
99     UnitType = debug_info.getU8(offset_ptr);
100     FormParams.AddrSize = debug_info.getU8(offset_ptr);
101     AbbrOffset = debug_info.getU32(offset_ptr);
102   } else {
103     AbbrOffset = debug_info.getU32(offset_ptr);
104     FormParams.AddrSize = debug_info.getU8(offset_ptr);
105   }
106   if (IndexEntry) {
107     if (AbbrOffset)
108       return false;
109     auto *UnitContrib = IndexEntry->getOffset();
110     if (!UnitContrib || UnitContrib->Length != (Length + 4))
111       return false;
112     auto *AbbrEntry = IndexEntry->getOffset(DW_SECT_ABBREV);
113     if (!AbbrEntry)
114       return false;
115     AbbrOffset = AbbrEntry->Offset;
116   }
117 
118   bool LengthOK = debug_info.isValidOffset(getNextUnitOffset() - 1);
119   bool VersionOK = DWARFContext::isSupportedVersion(getVersion());
120   bool AddrSizeOK = getAddressByteSize() == 4 || getAddressByteSize() == 8;
121 
122   if (!LengthOK || !VersionOK || !AddrSizeOK)
123     return false;
124 
125   // Keep track of the highest DWARF version we encounter across all units.
126   Context.setMaxVersionIfGreater(getVersion());
127 
128   Abbrevs = Abbrev->getAbbreviationDeclarationSet(AbbrOffset);
129   return Abbrevs != nullptr;
130 }
131 
132 bool DWARFUnit::extract(DataExtractor debug_info, uint32_t *offset_ptr) {
133   clear();
134 
135   Offset = *offset_ptr;
136 
137   if (debug_info.isValidOffset(*offset_ptr)) {
138     if (extractImpl(debug_info, offset_ptr))
139       return true;
140 
141     // reset the offset to where we tried to parse from if anything went wrong
142     *offset_ptr = Offset;
143   }
144 
145   return false;
146 }
147 
148 bool DWARFUnit::extractRangeList(uint32_t RangeListOffset,
149                                  DWARFDebugRangeList &RangeList) const {
150   // Require that compile unit is extracted.
151   assert(!DieArray.empty());
152   DWARFDataExtractor RangesData(Context.getDWARFObj(), *RangeSection,
153                                 isLittleEndian, getAddressByteSize());
154   uint32_t ActualRangeListOffset = RangeSectionBase + RangeListOffset;
155   return RangeList.extract(RangesData, &ActualRangeListOffset);
156 }
157 
158 void DWARFUnit::clear() {
159   Offset = 0;
160   Length = 0;
161   Abbrevs = nullptr;
162   FormParams = DWARFFormParams({0, 0, DWARF32});
163   BaseAddr.reset();
164   RangeSectionBase = 0;
165   AddrOffsetSectionBase = 0;
166   clearDIEs(false);
167   DWO.reset();
168 }
169 
170 const char *DWARFUnit::getCompilationDir() {
171   return dwarf::toString(getUnitDIE().find(DW_AT_comp_dir), nullptr);
172 }
173 
174 Optional<uint64_t> DWARFUnit::getDWOId() {
175   return toUnsigned(getUnitDIE().find(DW_AT_GNU_dwo_id));
176 }
177 
178 void DWARFUnit::extractDIEsToVector(
179     bool AppendCUDie, bool AppendNonCUDies,
180     std::vector<DWARFDebugInfoEntry> &Dies) const {
181   if (!AppendCUDie && !AppendNonCUDies)
182     return;
183 
184   // Set the offset to that of the first DIE and calculate the start of the
185   // next compilation unit header.
186   uint32_t DIEOffset = Offset + getHeaderSize();
187   uint32_t NextCUOffset = getNextUnitOffset();
188   DWARFDebugInfoEntry DIE;
189   DWARFDataExtractor DebugInfoData = getDebugInfoExtractor();
190   uint32_t Depth = 0;
191   bool IsCUDie = true;
192 
193   while (DIE.extractFast(*this, &DIEOffset, DebugInfoData, NextCUOffset,
194                          Depth)) {
195     if (IsCUDie) {
196       if (AppendCUDie)
197         Dies.push_back(DIE);
198       if (!AppendNonCUDies)
199         break;
200       // The average bytes per DIE entry has been seen to be
201       // around 14-20 so let's pre-reserve the needed memory for
202       // our DIE entries accordingly.
203       Dies.reserve(Dies.size() + getDebugInfoSize() / 14);
204       IsCUDie = false;
205     } else {
206       Dies.push_back(DIE);
207     }
208 
209     if (const DWARFAbbreviationDeclaration *AbbrDecl =
210             DIE.getAbbreviationDeclarationPtr()) {
211       // Normal DIE
212       if (AbbrDecl->hasChildren())
213         ++Depth;
214     } else {
215       // NULL DIE.
216       if (Depth > 0)
217         --Depth;
218       if (Depth == 0)
219         break;  // We are done with this compile unit!
220     }
221   }
222 
223   // Give a little bit of info if we encounter corrupt DWARF (our offset
224   // should always terminate at or before the start of the next compilation
225   // unit header).
226   if (DIEOffset > NextCUOffset)
227     fprintf(stderr, "warning: DWARF compile unit extends beyond its "
228                     "bounds cu 0x%8.8x at 0x%8.8x'\n", getOffset(), DIEOffset);
229 }
230 
231 size_t DWARFUnit::extractDIEsIfNeeded(bool CUDieOnly) {
232   if ((CUDieOnly && !DieArray.empty()) ||
233       DieArray.size() > 1)
234     return 0; // Already parsed.
235 
236   bool HasCUDie = !DieArray.empty();
237   extractDIEsToVector(!HasCUDie, !CUDieOnly, DieArray);
238 
239   if (DieArray.empty())
240     return 0;
241 
242   // If CU DIE was just parsed, copy several attribute values from it.
243   if (!HasCUDie) {
244     DWARFDie UnitDie = getUnitDIE();
245     Optional<DWARFFormValue> PC = UnitDie.find({DW_AT_low_pc, DW_AT_entry_pc});
246     if (Optional<uint64_t> Addr = toAddress(PC))
247         setBaseAddress({*Addr, PC->getSectionIndex()});
248 
249     if (!isDWO) {
250       assert(AddrOffsetSectionBase == 0);
251       assert(RangeSectionBase == 0);
252       AddrOffsetSectionBase =
253           toSectionOffset(UnitDie.find(DW_AT_GNU_addr_base), 0);
254       RangeSectionBase = toSectionOffset(UnitDie.find(DW_AT_rnglists_base), 0);
255     }
256 
257     // In general, we derive the offset of the unit's contibution to the
258     // debug_str_offsets{.dwo} section from the unit DIE's
259     // DW_AT_str_offsets_base attribute. In dwp files we add to it the offset
260     // we get from the index table.
261     StringOffsetSectionBase =
262         toSectionOffset(UnitDie.find(DW_AT_str_offsets_base), 0);
263     if (IndexEntry)
264       if (const auto *C = IndexEntry->getOffset(DW_SECT_STR_OFFSETS))
265         StringOffsetSectionBase += C->Offset;
266 
267     // Don't fall back to DW_AT_GNU_ranges_base: it should be ignored for
268     // skeleton CU DIE, so that DWARF users not aware of it are not broken.
269   }
270 
271   return DieArray.size();
272 }
273 
274 bool DWARFUnit::parseDWO() {
275   if (isDWO)
276     return false;
277   if (DWO.get())
278     return false;
279   DWARFDie UnitDie = getUnitDIE();
280   if (!UnitDie)
281     return false;
282   auto DWOFileName = dwarf::toString(UnitDie.find(DW_AT_GNU_dwo_name));
283   if (!DWOFileName)
284     return false;
285   auto CompilationDir = dwarf::toString(UnitDie.find(DW_AT_comp_dir));
286   SmallString<16> AbsolutePath;
287   if (sys::path::is_relative(*DWOFileName) && CompilationDir &&
288       *CompilationDir) {
289     sys::path::append(AbsolutePath, *CompilationDir);
290   }
291   sys::path::append(AbsolutePath, *DWOFileName);
292   auto DWOId = getDWOId();
293   if (!DWOId)
294     return false;
295   auto DWOContext = Context.getDWOContext(AbsolutePath);
296   if (!DWOContext)
297     return false;
298 
299   DWARFCompileUnit *DWOCU = DWOContext->getDWOCompileUnitForHash(*DWOId);
300   if (!DWOCU)
301     return false;
302   DWO = std::shared_ptr<DWARFCompileUnit>(std::move(DWOContext), DWOCU);
303   // Share .debug_addr and .debug_ranges section with compile unit in .dwo
304   DWO->setAddrOffsetSection(AddrOffsetSection, AddrOffsetSectionBase);
305   auto DWORangesBase = UnitDie.getRangesBaseAttribute();
306   DWO->setRangesSection(RangeSection, DWORangesBase ? *DWORangesBase : 0);
307   return true;
308 }
309 
310 void DWARFUnit::clearDIEs(bool KeepCUDie) {
311   if (DieArray.size() > (unsigned)KeepCUDie) {
312     DieArray.resize((unsigned)KeepCUDie);
313     DieArray.shrink_to_fit();
314   }
315 }
316 
317 void DWARFUnit::collectAddressRanges(DWARFAddressRangesVector &CURanges) {
318   DWARFDie UnitDie = getUnitDIE();
319   if (!UnitDie)
320     return;
321   // First, check if unit DIE describes address ranges for the whole unit.
322   const auto &CUDIERanges = UnitDie.getAddressRanges();
323   if (!CUDIERanges.empty()) {
324     CURanges.insert(CURanges.end(), CUDIERanges.begin(), CUDIERanges.end());
325     return;
326   }
327 
328   // This function is usually called if there in no .debug_aranges section
329   // in order to produce a compile unit level set of address ranges that
330   // is accurate. If the DIEs weren't parsed, then we don't want all dies for
331   // all compile units to stay loaded when they weren't needed. So we can end
332   // up parsing the DWARF and then throwing them all away to keep memory usage
333   // down.
334   const bool ClearDIEs = extractDIEsIfNeeded(false) > 1;
335   getUnitDIE().collectChildrenAddressRanges(CURanges);
336 
337   // Collect address ranges from DIEs in .dwo if necessary.
338   bool DWOCreated = parseDWO();
339   if (DWO)
340     DWO->collectAddressRanges(CURanges);
341   if (DWOCreated)
342     DWO.reset();
343 
344   // Keep memory down by clearing DIEs if this generate function
345   // caused them to be parsed.
346   if (ClearDIEs)
347     clearDIEs(true);
348 }
349 
350 void DWARFUnit::updateAddressDieMap(DWARFDie Die) {
351   if (Die.isSubroutineDIE()) {
352     for (const auto &R : Die.getAddressRanges()) {
353       // Ignore 0-sized ranges.
354       if (R.LowPC == R.HighPC)
355         continue;
356       auto B = AddrDieMap.upper_bound(R.LowPC);
357       if (B != AddrDieMap.begin() && R.LowPC < (--B)->second.first) {
358         // The range is a sub-range of existing ranges, we need to split the
359         // existing range.
360         if (R.HighPC < B->second.first)
361           AddrDieMap[R.HighPC] = B->second;
362         if (R.LowPC > B->first)
363           AddrDieMap[B->first].first = R.LowPC;
364       }
365       AddrDieMap[R.LowPC] = std::make_pair(R.HighPC, Die);
366     }
367   }
368   // Parent DIEs are added to the AddrDieMap prior to the Children DIEs to
369   // simplify the logic to update AddrDieMap. The child's range will always
370   // be equal or smaller than the parent's range. With this assumption, when
371   // adding one range into the map, it will at most split a range into 3
372   // sub-ranges.
373   for (DWARFDie Child = Die.getFirstChild(); Child; Child = Child.getSibling())
374     updateAddressDieMap(Child);
375 }
376 
377 DWARFDie DWARFUnit::getSubroutineForAddress(uint64_t Address) {
378   extractDIEsIfNeeded(false);
379   if (AddrDieMap.empty())
380     updateAddressDieMap(getUnitDIE());
381   auto R = AddrDieMap.upper_bound(Address);
382   if (R == AddrDieMap.begin())
383     return DWARFDie();
384   // upper_bound's previous item contains Address.
385   --R;
386   if (Address >= R->second.first)
387     return DWARFDie();
388   return R->second.second;
389 }
390 
391 void
392 DWARFUnit::getInlinedChainForAddress(uint64_t Address,
393                                      SmallVectorImpl<DWARFDie> &InlinedChain) {
394   assert(InlinedChain.empty());
395   // Try to look for subprogram DIEs in the DWO file.
396   parseDWO();
397   // First, find the subroutine that contains the given address (the leaf
398   // of inlined chain).
399   DWARFDie SubroutineDIE =
400       (DWO ? DWO.get() : this)->getSubroutineForAddress(Address);
401 
402   while (SubroutineDIE) {
403     if (SubroutineDIE.isSubroutineDIE())
404       InlinedChain.push_back(SubroutineDIE);
405     SubroutineDIE  = SubroutineDIE.getParent();
406   }
407 }
408 
409 const DWARFUnitIndex &llvm::getDWARFUnitIndex(DWARFContext &Context,
410                                               DWARFSectionKind Kind) {
411   if (Kind == DW_SECT_INFO)
412     return Context.getCUIndex();
413   assert(Kind == DW_SECT_TYPES);
414   return Context.getTUIndex();
415 }
416 
417 DWARFDie DWARFUnit::getParent(const DWARFDebugInfoEntry *Die) {
418   if (!Die)
419     return DWARFDie();
420   const uint32_t Depth = Die->getDepth();
421   // Unit DIEs always have a depth of zero and never have parents.
422   if (Depth == 0)
423     return DWARFDie();
424   // Depth of 1 always means parent is the compile/type unit.
425   if (Depth == 1)
426     return getUnitDIE();
427   // Look for previous DIE with a depth that is one less than the Die's depth.
428   const uint32_t ParentDepth = Depth - 1;
429   for (uint32_t I = getDIEIndex(Die) - 1; I > 0; --I) {
430     if (DieArray[I].getDepth() == ParentDepth)
431       return DWARFDie(this, &DieArray[I]);
432   }
433   return DWARFDie();
434 }
435 
436 DWARFDie DWARFUnit::getSibling(const DWARFDebugInfoEntry *Die) {
437   if (!Die)
438     return DWARFDie();
439   uint32_t Depth = Die->getDepth();
440   // Unit DIEs always have a depth of zero and never have siblings.
441   if (Depth == 0)
442     return DWARFDie();
443   // NULL DIEs don't have siblings.
444   if (Die->getAbbreviationDeclarationPtr() == nullptr)
445     return DWARFDie();
446 
447   // Find the next DIE whose depth is the same as the Die's depth.
448   for (size_t I = getDIEIndex(Die) + 1, EndIdx = DieArray.size(); I < EndIdx;
449        ++I) {
450     if (DieArray[I].getDepth() == Depth)
451       return DWARFDie(this, &DieArray[I]);
452   }
453   return DWARFDie();
454 }
455