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 = 0;
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     auto BaseAddr = toAddress(UnitDie.find({DW_AT_low_pc, DW_AT_entry_pc}));
246     if (BaseAddr)
247       setBaseAddress(*BaseAddr);
248     if (!isDWO) {
249       assert(AddrOffsetSectionBase == 0);
250       assert(RangeSectionBase == 0);
251       AddrOffsetSectionBase =
252           toSectionOffset(UnitDie.find(DW_AT_GNU_addr_base), 0);
253       RangeSectionBase = toSectionOffset(UnitDie.find(DW_AT_rnglists_base), 0);
254     }
255 
256     // In general, we derive the offset of the unit's contibution to the
257     // debug_str_offsets{.dwo} section from the unit DIE's
258     // DW_AT_str_offsets_base attribute. In dwp files we add to it the offset
259     // we get from the index table.
260     StringOffsetSectionBase =
261         toSectionOffset(UnitDie.find(DW_AT_str_offsets_base), 0);
262     if (IndexEntry)
263       if (const auto *C = IndexEntry->getOffset(DW_SECT_STR_OFFSETS))
264         StringOffsetSectionBase += C->Offset;
265 
266     // Don't fall back to DW_AT_GNU_ranges_base: it should be ignored for
267     // skeleton CU DIE, so that DWARF users not aware of it are not broken.
268   }
269 
270   return DieArray.size();
271 }
272 
273 bool DWARFUnit::parseDWO() {
274   if (isDWO)
275     return false;
276   if (DWO.get())
277     return false;
278   DWARFDie UnitDie = getUnitDIE();
279   if (!UnitDie)
280     return false;
281   auto DWOFileName = dwarf::toString(UnitDie.find(DW_AT_GNU_dwo_name));
282   if (!DWOFileName)
283     return false;
284   auto CompilationDir = dwarf::toString(UnitDie.find(DW_AT_comp_dir));
285   SmallString<16> AbsolutePath;
286   if (sys::path::is_relative(*DWOFileName) && CompilationDir &&
287       *CompilationDir) {
288     sys::path::append(AbsolutePath, *CompilationDir);
289   }
290   sys::path::append(AbsolutePath, *DWOFileName);
291   auto DWOId = getDWOId();
292   if (!DWOId)
293     return false;
294   auto DWOContext = Context.getDWOContext(AbsolutePath);
295   if (!DWOContext)
296     return false;
297 
298   DWARFCompileUnit *DWOCU = DWOContext->getDWOCompileUnitForHash(*DWOId);
299   if (!DWOCU)
300     return false;
301   DWO = std::shared_ptr<DWARFCompileUnit>(std::move(DWOContext), DWOCU);
302   // Share .debug_addr and .debug_ranges section with compile unit in .dwo
303   DWO->setAddrOffsetSection(AddrOffsetSection, AddrOffsetSectionBase);
304   auto DWORangesBase = UnitDie.getRangesBaseAttribute();
305   DWO->setRangesSection(RangeSection, DWORangesBase ? *DWORangesBase : 0);
306   return true;
307 }
308 
309 void DWARFUnit::clearDIEs(bool KeepCUDie) {
310   if (DieArray.size() > (unsigned)KeepCUDie) {
311     DieArray.resize((unsigned)KeepCUDie);
312     DieArray.shrink_to_fit();
313   }
314 }
315 
316 void DWARFUnit::collectAddressRanges(DWARFAddressRangesVector &CURanges) {
317   DWARFDie UnitDie = getUnitDIE();
318   if (!UnitDie)
319     return;
320   // First, check if unit DIE describes address ranges for the whole unit.
321   const auto &CUDIERanges = UnitDie.getAddressRanges();
322   if (!CUDIERanges.empty()) {
323     CURanges.insert(CURanges.end(), CUDIERanges.begin(), CUDIERanges.end());
324     return;
325   }
326 
327   // This function is usually called if there in no .debug_aranges section
328   // in order to produce a compile unit level set of address ranges that
329   // is accurate. If the DIEs weren't parsed, then we don't want all dies for
330   // all compile units to stay loaded when they weren't needed. So we can end
331   // up parsing the DWARF and then throwing them all away to keep memory usage
332   // down.
333   const bool ClearDIEs = extractDIEsIfNeeded(false) > 1;
334   getUnitDIE().collectChildrenAddressRanges(CURanges);
335 
336   // Collect address ranges from DIEs in .dwo if necessary.
337   bool DWOCreated = parseDWO();
338   if (DWO)
339     DWO->collectAddressRanges(CURanges);
340   if (DWOCreated)
341     DWO.reset();
342 
343   // Keep memory down by clearing DIEs if this generate function
344   // caused them to be parsed.
345   if (ClearDIEs)
346     clearDIEs(true);
347 }
348 
349 void DWARFUnit::updateAddressDieMap(DWARFDie Die) {
350   if (Die.isSubroutineDIE()) {
351     for (const auto &R : Die.getAddressRanges()) {
352       // Ignore 0-sized ranges.
353       if (R.LowPC == R.HighPC)
354         continue;
355       auto B = AddrDieMap.upper_bound(R.LowPC);
356       if (B != AddrDieMap.begin() && R.LowPC < (--B)->second.first) {
357         // The range is a sub-range of existing ranges, we need to split the
358         // existing range.
359         if (R.HighPC < B->second.first)
360           AddrDieMap[R.HighPC] = B->second;
361         if (R.LowPC > B->first)
362           AddrDieMap[B->first].first = R.LowPC;
363       }
364       AddrDieMap[R.LowPC] = std::make_pair(R.HighPC, Die);
365     }
366   }
367   // Parent DIEs are added to the AddrDieMap prior to the Children DIEs to
368   // simplify the logic to update AddrDieMap. The child's range will always
369   // be equal or smaller than the parent's range. With this assumption, when
370   // adding one range into the map, it will at most split a range into 3
371   // sub-ranges.
372   for (DWARFDie Child = Die.getFirstChild(); Child; Child = Child.getSibling())
373     updateAddressDieMap(Child);
374 }
375 
376 DWARFDie DWARFUnit::getSubroutineForAddress(uint64_t Address) {
377   extractDIEsIfNeeded(false);
378   if (AddrDieMap.empty())
379     updateAddressDieMap(getUnitDIE());
380   auto R = AddrDieMap.upper_bound(Address);
381   if (R == AddrDieMap.begin())
382     return DWARFDie();
383   // upper_bound's previous item contains Address.
384   --R;
385   if (Address >= R->second.first)
386     return DWARFDie();
387   return R->second.second;
388 }
389 
390 void
391 DWARFUnit::getInlinedChainForAddress(uint64_t Address,
392                                      SmallVectorImpl<DWARFDie> &InlinedChain) {
393   assert(InlinedChain.empty());
394   // Try to look for subprogram DIEs in the DWO file.
395   parseDWO();
396   // First, find the subroutine that contains the given address (the leaf
397   // of inlined chain).
398   DWARFDie SubroutineDIE =
399       (DWO ? DWO.get() : this)->getSubroutineForAddress(Address);
400 
401   while (SubroutineDIE) {
402     if (SubroutineDIE.isSubroutineDIE())
403       InlinedChain.push_back(SubroutineDIE);
404     SubroutineDIE  = SubroutineDIE.getParent();
405   }
406 }
407 
408 const DWARFUnitIndex &llvm::getDWARFUnitIndex(DWARFContext &Context,
409                                               DWARFSectionKind Kind) {
410   if (Kind == DW_SECT_INFO)
411     return Context.getCUIndex();
412   assert(Kind == DW_SECT_TYPES);
413   return Context.getTUIndex();
414 }
415 
416 DWARFDie DWARFUnit::getParent(const DWARFDebugInfoEntry *Die) {
417   if (!Die)
418     return DWARFDie();
419   const uint32_t Depth = Die->getDepth();
420   // Unit DIEs always have a depth of zero and never have parents.
421   if (Depth == 0)
422     return DWARFDie();
423   // Depth of 1 always means parent is the compile/type unit.
424   if (Depth == 1)
425     return getUnitDIE();
426   // Look for previous DIE with a depth that is one less than the Die's depth.
427   const uint32_t ParentDepth = Depth - 1;
428   for (uint32_t I = getDIEIndex(Die) - 1; I > 0; --I) {
429     if (DieArray[I].getDepth() == ParentDepth)
430       return DWARFDie(this, &DieArray[I]);
431   }
432   return DWARFDie();
433 }
434 
435 DWARFDie DWARFUnit::getSibling(const DWARFDebugInfoEntry *Die) {
436   if (!Die)
437     return DWARFDie();
438   uint32_t Depth = Die->getDepth();
439   // Unit DIEs always have a depth of zero and never have siblings.
440   if (Depth == 0)
441     return DWARFDie();
442   // NULL DIEs don't have siblings.
443   if (Die->getAbbreviationDeclarationPtr() == nullptr)
444     return DWARFDie();
445 
446   // Find the next DIE whose depth is the same as the Die's depth.
447   for (size_t I = getDIEIndex(Die) + 1, EndIdx = DieArray.size(); I < EndIdx;
448        ++I) {
449     if (DieArray[I].getDepth() == Depth)
450       return DWARFDie(this, &DieArray[I]);
451   }
452   return DWARFDie();
453 }
454