1 //===- DWARFVerifier.h ----------------------------------------------------===//
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_DWARFVERIFIER_H
10 #define LLVM_DEBUGINFO_DWARF_DWARFVERIFIER_H
11 
12 #include "llvm/DebugInfo/DIContext.h"
13 #include "llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h"
14 #include "llvm/DebugInfo/DWARF/DWARFAddressRange.h"
15 #include "llvm/DebugInfo/DWARF/DWARFDie.h"
16 #include "llvm/DebugInfo/DWARF/DWARFUnitIndex.h"
17 
18 #include <cstdint>
19 #include <map>
20 #include <set>
21 
22 namespace llvm {
23 class raw_ostream;
24 struct DWARFAttribute;
25 class DWARFContext;
26 class DWARFDie;
27 class DWARFUnit;
28 class DWARFCompileUnit;
29 class DWARFDataExtractor;
30 class DWARFDebugAbbrev;
31 class DataExtractor;
32 struct DWARFSection;
33 
34 /// A class that verifies DWARF debug information given a DWARF Context.
35 class DWARFVerifier {
36 public:
37   /// A class that keeps the address range information for a single DIE.
38   struct DieRangeInfo {
39     DWARFDie Die;
40 
41     /// Sorted DWARFAddressRanges.
42     std::vector<DWARFAddressRange> Ranges;
43 
44     /// Sorted DWARFAddressRangeInfo.
45     std::set<DieRangeInfo> Children;
46 
47     DieRangeInfo() = default;
48     DieRangeInfo(DWARFDie Die) : Die(Die) {}
49 
50     /// Used for unit testing.
51     DieRangeInfo(std::vector<DWARFAddressRange> Ranges)
52         : Ranges(std::move(Ranges)) {}
53 
54     typedef std::vector<DWARFAddressRange>::const_iterator
55         address_range_iterator;
56     typedef std::set<DieRangeInfo>::const_iterator die_range_info_iterator;
57 
58     /// Inserts the address range. If the range overlaps with an existing
59     /// range, the range is *not* added and an iterator to the overlapping
60     /// range is returned.
61     ///
62     /// This is used for finding overlapping ranges within the same DIE.
63     address_range_iterator insert(const DWARFAddressRange &R);
64 
65     /// Finds an address range in the sorted vector of ranges.
66     address_range_iterator findRange(const DWARFAddressRange &R) const {
67       auto Begin = Ranges.begin();
68       auto End = Ranges.end();
69       auto Iter = std::upper_bound(Begin, End, R);
70       if (Iter != Begin)
71         --Iter;
72       return Iter;
73     }
74 
75     /// Inserts the address range info. If any of its ranges overlaps with a
76     /// range in an existing range info, the range info is *not* added and an
77     /// iterator to the overlapping range info.
78     ///
79     /// This is used for finding overlapping children of the same DIE.
80     die_range_info_iterator insert(const DieRangeInfo &RI);
81 
82     /// Return true if ranges in this object contains all ranges within RHS.
83     bool contains(const DieRangeInfo &RHS) const;
84 
85     /// Return true if any range in this object intersects with any range in
86     /// RHS.
87     bool intersects(const DieRangeInfo &RHS) const;
88   };
89 
90 private:
91   raw_ostream &OS;
92   DWARFContext &DCtx;
93   DIDumpOptions DumpOpts;
94   /// A map that tracks all references (converted absolute references) so we
95   /// can verify each reference points to a valid DIE and not an offset that
96   /// lies between to valid DIEs.
97   std::map<uint64_t, std::set<uint64_t>> ReferenceToDIEOffsets;
98   uint32_t NumDebugLineErrors = 0;
99   // Used to relax some checks that do not currently work portably
100   bool IsObjectFile;
101   bool IsMachOObject;
102 
103   raw_ostream &error() const;
104   raw_ostream &warn() const;
105   raw_ostream &note() const;
106   raw_ostream &dump(const DWARFDie &Die, unsigned indent = 0) const;
107 
108   /// Verifies the abbreviations section.
109   ///
110   /// This function currently checks that:
111   /// --No abbreviation declaration has more than one attributes with the same
112   /// name.
113   ///
114   /// \param Abbrev Pointer to the abbreviations section we are verifying
115   /// Abbrev can be a pointer to either .debug_abbrev or debug_abbrev.dwo.
116   ///
117   /// \returns The number of errors that occurred during verification.
118   unsigned verifyAbbrevSection(const DWARFDebugAbbrev *Abbrev);
119 
120   /// Verifies the header of a unit in a .debug_info or .debug_types section.
121   ///
122   /// This function currently checks for:
123   /// - Unit is in 32-bit DWARF format. The function can be modified to
124   /// support 64-bit format.
125   /// - The DWARF version is valid
126   /// - The unit type is valid (if unit is in version >=5)
127   /// - The unit doesn't extend beyond the containing section
128   /// - The address size is valid
129   /// - The offset in the .debug_abbrev section is valid
130   ///
131   /// \param DebugInfoData The section data
132   /// \param Offset A reference to the offset start of the unit. The offset will
133   /// be updated to point to the next unit in the section
134   /// \param UnitIndex The index of the unit to be verified
135   /// \param UnitType A reference to the type of the unit
136   /// \param isUnitDWARF64 A reference to a flag that shows whether the unit is
137   /// in 64-bit format.
138   ///
139   /// \returns true if the header is verified successfully, false otherwise.
140   bool verifyUnitHeader(const DWARFDataExtractor DebugInfoData,
141                         uint64_t *Offset, unsigned UnitIndex, uint8_t &UnitType,
142                         bool &isUnitDWARF64);
143 
144   /// Verifies the header of a unit in a .debug_info or .debug_types section.
145   ///
146   /// This function currently verifies:
147   ///  - The debug info attributes.
148   ///  - The debug info form=s.
149   ///  - The presence of a root DIE.
150   ///  - That the root DIE is a unit DIE.
151   ///  - If a unit type is provided, that the unit DIE matches the unit type.
152   ///  - The DIE ranges.
153   ///  - That call site entries are only nested within subprograms with a
154   ///    DW_AT_call attribute.
155   ///
156   /// \param Unit      The DWARF Unit to verify.
157   ///
158   /// \returns The number of errors that occurred during verification.
159   unsigned verifyUnitContents(DWARFUnit &Unit);
160 
161   /// Verifies the unit headers and contents in a .debug_info or .debug_types
162   /// section.
163   ///
164   /// \param S           The DWARF Section to verify.
165   /// \param SectionKind The object-file section kind that S comes from.
166   ///
167   /// \returns The number of errors that occurred during verification.
168   unsigned verifyUnitSection(const DWARFSection &S,
169                              DWARFSectionKind SectionKind);
170 
171   /// Verifies that a call site entry is nested within a subprogram with a
172   /// DW_AT_call attribute.
173   ///
174   /// \returns Number of errors that occurred during verification.
175   unsigned verifyDebugInfoCallSite(const DWARFDie &Die);
176 
177   /// Verify that all Die ranges are valid.
178   ///
179   /// This function currently checks for:
180   /// - cases in which lowPC >= highPC
181   ///
182   /// \returns Number of errors that occurred during verification.
183   unsigned verifyDieRanges(const DWARFDie &Die, DieRangeInfo &ParentRI);
184 
185   /// Verifies the attribute's DWARF attribute and its value.
186   ///
187   /// This function currently checks for:
188   /// - DW_AT_ranges values is a valid .debug_ranges offset
189   /// - DW_AT_stmt_list is a valid .debug_line offset
190   ///
191   /// \param Die          The DWARF DIE that owns the attribute value
192   /// \param AttrValue    The DWARF attribute value to check
193   ///
194   /// \returns NumErrors The number of errors occurred during verification of
195   /// attributes' values in a unit
196   unsigned verifyDebugInfoAttribute(const DWARFDie &Die,
197                                     DWARFAttribute &AttrValue);
198 
199   /// Verifies the attribute's DWARF form.
200   ///
201   /// This function currently checks for:
202   /// - All DW_FORM_ref values that are CU relative have valid CU offsets
203   /// - All DW_FORM_ref_addr values have valid section offsets
204   /// - All DW_FORM_strp values have valid .debug_str offsets
205   ///
206   /// \param Die          The DWARF DIE that owns the attribute value
207   /// \param AttrValue    The DWARF attribute value to check
208   ///
209   /// \returns NumErrors The number of errors occurred during verification of
210   /// attributes' forms in a unit
211   unsigned verifyDebugInfoForm(const DWARFDie &Die, DWARFAttribute &AttrValue);
212 
213   /// Verifies the all valid references that were found when iterating through
214   /// all of the DIE attributes.
215   ///
216   /// This function will verify that all references point to DIEs whose DIE
217   /// offset matches. This helps to ensure if a DWARF link phase moved things
218   /// around, that it doesn't create invalid references by failing to relocate
219   /// CU relative and absolute references.
220   ///
221   /// \returns NumErrors The number of errors occurred during verification of
222   /// references for the .debug_info and .debug_types sections
223   unsigned verifyDebugInfoReferences();
224 
225   /// Verify the DW_AT_stmt_list encoding and value and ensure that no
226   /// compile units that have the same DW_AT_stmt_list value.
227   void verifyDebugLineStmtOffsets();
228 
229   /// Verify that all of the rows in the line table are valid.
230   ///
231   /// This function currently checks for:
232   /// - addresses within a sequence that decrease in value
233   /// - invalid file indexes
234   void verifyDebugLineRows();
235 
236   /// Verify that an Apple-style accelerator table is valid.
237   ///
238   /// This function currently checks that:
239   /// - The fixed part of the header fits in the section
240   /// - The size of the section is as large as what the header describes
241   /// - There is at least one atom
242   /// - The form for each atom is valid
243   /// - The tag for each DIE in the table is valid
244   /// - The buckets have a valid index, or they are empty
245   /// - Each hashdata offset is valid
246   /// - Each DIE is valid
247   ///
248   /// \param AccelSection pointer to the section containing the acceleration table
249   /// \param StrData pointer to the string section
250   /// \param SectionName the name of the table we're verifying
251   ///
252   /// \returns The number of errors occurred during verification
253   unsigned verifyAppleAccelTable(const DWARFSection *AccelSection,
254                                  DataExtractor *StrData,
255                                  const char *SectionName);
256 
257   unsigned verifyDebugNamesCULists(const DWARFDebugNames &AccelTable);
258   unsigned verifyNameIndexBuckets(const DWARFDebugNames::NameIndex &NI,
259                                   const DataExtractor &StrData);
260   unsigned verifyNameIndexAbbrevs(const DWARFDebugNames::NameIndex &NI);
261   unsigned verifyNameIndexAttribute(const DWARFDebugNames::NameIndex &NI,
262                                     const DWARFDebugNames::Abbrev &Abbr,
263                                     DWARFDebugNames::AttributeEncoding AttrEnc);
264   unsigned verifyNameIndexEntries(const DWARFDebugNames::NameIndex &NI,
265                                   const DWARFDebugNames::NameTableEntry &NTE);
266   unsigned verifyNameIndexCompleteness(const DWARFDie &Die,
267                                        const DWARFDebugNames::NameIndex &NI);
268 
269   /// Verify that the DWARF v5 accelerator table is valid.
270   ///
271   /// This function currently checks that:
272   /// - Headers individual Name Indices fit into the section and can be parsed.
273   /// - Abbreviation tables can be parsed and contain valid index attributes
274   ///   with correct form encodings.
275   /// - The CU lists reference existing compile units.
276   /// - The buckets have a valid index, or they are empty.
277   /// - All names are reachable via the hash table (they have the correct hash,
278   ///   and the hash is in the correct bucket).
279   /// - Information in the index entries is complete (all required entries are
280   ///   present) and consistent with the debug_info section DIEs.
281   ///
282   /// \param AccelSection section containing the acceleration table
283   /// \param StrData string section
284   ///
285   /// \returns The number of errors occurred during verification
286   unsigned verifyDebugNames(const DWARFSection &AccelSection,
287                             const DataExtractor &StrData);
288 
289 public:
290   DWARFVerifier(raw_ostream &S, DWARFContext &D,
291                 DIDumpOptions DumpOpts = DIDumpOptions::getForSingleDIE());
292 
293   /// Verify the information in any of the following sections, if available:
294   /// .debug_abbrev, debug_abbrev.dwo
295   ///
296   /// Any errors are reported to the stream that was this object was
297   /// constructed with.
298   ///
299   /// \returns true if .debug_abbrev and .debug_abbrev.dwo verify successfully,
300   /// false otherwise.
301   bool handleDebugAbbrev();
302 
303   /// Verify the information in the .debug_info and .debug_types sections.
304   ///
305   /// Any errors are reported to the stream that this object was
306   /// constructed with.
307   ///
308   /// \returns true if all sections verify successfully, false otherwise.
309   bool handleDebugInfo();
310 
311   /// Verify the information in the .debug_line section.
312   ///
313   /// Any errors are reported to the stream that was this object was
314   /// constructed with.
315   ///
316   /// \returns true if the .debug_line verifies successfully, false otherwise.
317   bool handleDebugLine();
318 
319   /// Verify the information in accelerator tables, if they exist.
320   ///
321   /// Any errors are reported to the stream that was this object was
322   /// constructed with.
323   ///
324   /// \returns true if the existing Apple-style accelerator tables verify
325   /// successfully, false otherwise.
326   bool handleAccelTables();
327 };
328 
329 static inline bool operator<(const DWARFVerifier::DieRangeInfo &LHS,
330                              const DWARFVerifier::DieRangeInfo &RHS) {
331   return std::tie(LHS.Ranges, LHS.Die) < std::tie(RHS.Ranges, RHS.Die);
332 }
333 
334 } // end namespace llvm
335 
336 #endif // LLVM_DEBUGINFO_DWARF_DWARFCONTEXT_H
337