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