1 //===- DWARFListTable.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_DWARFLISTTABLE_H
10 #define LLVM_DEBUGINFO_DWARF_DWARFLISTTABLE_H
11 
12 #include "llvm/BinaryFormat/Dwarf.h"
13 #include "llvm/DebugInfo/DIContext.h"
14 #include "llvm/DebugInfo/DWARF/DWARFDataExtractor.h"
15 #include "llvm/Support/Errc.h"
16 #include "llvm/Support/Error.h"
17 #include "llvm/Support/raw_ostream.h"
18 #include <cstdint>
19 #include <map>
20 #include <vector>
21 
22 namespace llvm {
23 
24 /// A base class for DWARF list entries, such as range or location list
25 /// entries.
26 struct DWARFListEntryBase {
27   /// The offset at which the entry is located in the section.
28   uint64_t Offset;
29   /// The DWARF encoding (DW_RLE_* or DW_LLE_*).
30   uint8_t EntryKind;
31   /// The index of the section this entry belongs to.
32   uint64_t SectionIndex;
33 };
34 
35 /// A base class for lists of entries that are extracted from a particular
36 /// section, such as range lists or location lists.
37 template <typename ListEntryType> class DWARFListType {
38   using EntryType = ListEntryType;
39   using ListEntries = std::vector<EntryType>;
40 
41 protected:
42   ListEntries Entries;
43 
44 public:
45   const ListEntries &getEntries() const { return Entries; }
46   bool empty() const { return Entries.empty(); }
47   void clear() { Entries.clear(); }
48   Error extract(DWARFDataExtractor Data, uint64_t HeaderOffset,
49                 uint64_t *OffsetPtr, StringRef SectionName,
50                 StringRef ListStringName);
51 };
52 
53 /// A class representing the header of a list table such as the range list
54 /// table in the .debug_rnglists section.
55 class DWARFListTableHeader {
56   struct Header {
57     /// The total length of the entries for this table, not including the length
58     /// field itself.
59     uint64_t Length = 0;
60     /// The DWARF version number.
61     uint16_t Version;
62     /// The size in bytes of an address on the target architecture. For
63     /// segmented addressing, this is the size of the offset portion of the
64     /// address.
65     uint8_t AddrSize;
66     /// The size in bytes of a segment selector on the target architecture.
67     /// If the target system uses a flat address space, this value is 0.
68     uint8_t SegSize;
69     /// The number of offsets that follow the header before the range lists.
70     uint32_t OffsetEntryCount;
71   };
72 
73   Header HeaderData;
74   /// The table's format, either DWARF32 or DWARF64.
75   dwarf::DwarfFormat Format;
76   /// The offset at which the header (and hence the table) is located within
77   /// its section.
78   uint64_t HeaderOffset;
79   /// The name of the section the list is located in.
80   StringRef SectionName;
81   /// A characterization of the list for dumping purposes, e.g. "range" or
82   /// "location".
83   StringRef ListTypeString;
84 
85 public:
86   DWARFListTableHeader(StringRef SectionName, StringRef ListTypeString)
87       : SectionName(SectionName), ListTypeString(ListTypeString) {}
88 
89   void clear() {
90     HeaderData = {};
91   }
92   uint64_t getHeaderOffset() const { return HeaderOffset; }
93   uint8_t getAddrSize() const { return HeaderData.AddrSize; }
94   uint64_t getLength() const { return HeaderData.Length; }
95   uint16_t getVersion() const { return HeaderData.Version; }
96   uint32_t getOffsetEntryCount() const { return HeaderData.OffsetEntryCount; }
97   StringRef getSectionName() const { return SectionName; }
98   StringRef getListTypeString() const { return ListTypeString; }
99   dwarf::DwarfFormat getFormat() const { return Format; }
100 
101   /// Return the size of the table header including the length but not including
102   /// the offsets.
103   static uint8_t getHeaderSize(dwarf::DwarfFormat Format) {
104     switch (Format) {
105     case dwarf::DwarfFormat::DWARF32:
106       return 12;
107     case dwarf::DwarfFormat::DWARF64:
108       return 20;
109     }
110     llvm_unreachable("Invalid DWARF format (expected DWARF32 or DWARF64");
111   }
112 
113   void dump(DataExtractor Data, raw_ostream &OS,
114             DIDumpOptions DumpOpts = {}) const;
115   Optional<uint64_t> getOffsetEntry(DataExtractor Data, uint32_t Index) const {
116     if (Index >= HeaderData.OffsetEntryCount)
117       return None;
118 
119     return getOffsetEntry(Data, getHeaderOffset() + getHeaderSize(Format), Format, Index);
120   }
121 
122   static Optional<uint64_t> getOffsetEntry(DataExtractor Data,
123                                            uint64_t OffsetTableOffset,
124                                            dwarf::DwarfFormat Format,
125                                            uint32_t Index) {
126     uint8_t OffsetByteSize = Format == dwarf::DWARF64 ? 8 : 4;
127     uint64_t Offset = OffsetTableOffset + OffsetByteSize * Index;
128     auto R = Data.getUnsigned(&Offset, OffsetByteSize);
129     return R;
130   }
131 
132   /// Extract the table header and the array of offsets.
133   Error extract(DWARFDataExtractor Data, uint64_t *OffsetPtr);
134 
135   /// Returns the length of the table, including the length field, or 0 if the
136   /// length has not been determined (e.g. because the table has not yet been
137   /// parsed, or there was a problem in parsing).
138   uint64_t length() const;
139 };
140 
141 /// A class representing a table of lists as specified in the DWARF v5
142 /// standard for location lists and range lists. The table consists of a header
143 /// followed by an array of offsets into a DWARF section, followed by zero or
144 /// more list entries. The list entries are kept in a map where the keys are
145 /// the lists' section offsets.
146 template <typename DWARFListType> class DWARFListTableBase {
147   DWARFListTableHeader Header;
148   /// A mapping between file offsets and lists. It is used to find a particular
149   /// list based on an offset (obtained from DW_AT_ranges, for example).
150   std::map<uint64_t, DWARFListType> ListMap;
151   /// This string is displayed as a heading before the list is dumped
152   /// (e.g. "ranges:").
153   StringRef HeaderString;
154 
155 protected:
156   DWARFListTableBase(StringRef SectionName, StringRef HeaderString,
157                      StringRef ListTypeString)
158       : Header(SectionName, ListTypeString), HeaderString(HeaderString) {}
159 
160 public:
161   void clear() {
162     Header.clear();
163     ListMap.clear();
164   }
165   /// Extract the table header and the array of offsets.
166   Error extractHeaderAndOffsets(DWARFDataExtractor Data, uint64_t *OffsetPtr) {
167     return Header.extract(Data, OffsetPtr);
168   }
169   /// Extract an entire table, including all list entries.
170   Error extract(DWARFDataExtractor Data, uint64_t *OffsetPtr);
171   /// Look up a list based on a given offset. Extract it and enter it into the
172   /// list map if necessary.
173   Expected<DWARFListType> findList(DWARFDataExtractor Data,
174                                    uint64_t Offset) const;
175 
176   uint64_t getHeaderOffset() const { return Header.getHeaderOffset(); }
177   uint8_t getAddrSize() const { return Header.getAddrSize(); }
178   uint32_t getOffsetEntryCount() const { return Header.getOffsetEntryCount(); }
179   dwarf::DwarfFormat getFormat() const { return Header.getFormat(); }
180 
181   void dump(DWARFDataExtractor Data, raw_ostream &OS,
182             llvm::function_ref<Optional<object::SectionedAddress>(uint32_t)>
183                 LookupPooledAddress,
184             DIDumpOptions DumpOpts = {}) const;
185 
186   /// Return the contents of the offset entry designated by a given index.
187   Optional<uint64_t> getOffsetEntry(DataExtractor Data, uint32_t Index) const {
188     return Header.getOffsetEntry(Data, Index);
189   }
190   /// Return the size of the table header including the length but not including
191   /// the offsets. This is dependent on the table format, which is unambiguously
192   /// derived from parsing the table.
193   uint8_t getHeaderSize() const {
194     return DWARFListTableHeader::getHeaderSize(getFormat());
195   }
196 
197   uint64_t length() { return Header.length(); }
198 };
199 
200 template <typename DWARFListType>
201 Error DWARFListTableBase<DWARFListType>::extract(DWARFDataExtractor Data,
202                                                  uint64_t *OffsetPtr) {
203   clear();
204   if (Error E = extractHeaderAndOffsets(Data, OffsetPtr))
205     return E;
206 
207   Data.setAddressSize(Header.getAddrSize());
208   Data = DWARFDataExtractor(Data, getHeaderOffset() + Header.length());
209   while (Data.isValidOffset(*OffsetPtr)) {
210     DWARFListType CurrentList;
211     uint64_t Off = *OffsetPtr;
212     if (Error E = CurrentList.extract(Data, getHeaderOffset(), OffsetPtr,
213                                       Header.getSectionName(),
214                                       Header.getListTypeString()))
215       return E;
216     ListMap[Off] = CurrentList;
217   }
218 
219   assert(*OffsetPtr == Data.size() &&
220          "mismatch between expected length of table and length "
221          "of extracted data");
222   return Error::success();
223 }
224 
225 template <typename ListEntryType>
226 Error DWARFListType<ListEntryType>::extract(DWARFDataExtractor Data,
227                                             uint64_t HeaderOffset,
228                                             uint64_t *OffsetPtr,
229                                             StringRef SectionName,
230                                             StringRef ListTypeString) {
231   if (*OffsetPtr < HeaderOffset || *OffsetPtr >= Data.size())
232     return createStringError(errc::invalid_argument,
233                        "invalid %s list offset 0x%" PRIx64,
234                        ListTypeString.data(), *OffsetPtr);
235   Entries.clear();
236   while (Data.isValidOffset(*OffsetPtr)) {
237     ListEntryType Entry;
238     if (Error E = Entry.extract(Data, OffsetPtr))
239       return E;
240     Entries.push_back(Entry);
241     if (Entry.isSentinel())
242       return Error::success();
243   }
244   return createStringError(errc::illegal_byte_sequence,
245                      "no end of list marker detected at end of %s table "
246                      "starting at offset 0x%" PRIx64,
247                      SectionName.data(), HeaderOffset);
248 }
249 
250 template <typename DWARFListType>
251 void DWARFListTableBase<DWARFListType>::dump(
252     DWARFDataExtractor Data, raw_ostream &OS,
253     llvm::function_ref<Optional<object::SectionedAddress>(uint32_t)>
254         LookupPooledAddress,
255     DIDumpOptions DumpOpts) const {
256   Header.dump(Data, OS, DumpOpts);
257   OS << HeaderString << "\n";
258 
259   // Determine the length of the longest encoding string we have in the table,
260   // so we can align the output properly. We only need this in verbose mode.
261   size_t MaxEncodingStringLength = 0;
262   if (DumpOpts.Verbose) {
263     for (const auto &List : ListMap)
264       for (const auto &Entry : List.second.getEntries())
265         MaxEncodingStringLength =
266             std::max(MaxEncodingStringLength,
267                      dwarf::RangeListEncodingString(Entry.EntryKind).size());
268   }
269 
270   uint64_t CurrentBase = 0;
271   for (const auto &List : ListMap)
272     for (const auto &Entry : List.second.getEntries())
273       Entry.dump(OS, getAddrSize(), MaxEncodingStringLength, CurrentBase,
274                  DumpOpts, LookupPooledAddress);
275 }
276 
277 template <typename DWARFListType>
278 Expected<DWARFListType>
279 DWARFListTableBase<DWARFListType>::findList(DWARFDataExtractor Data,
280                                             uint64_t Offset) const {
281   // Extract the list from the section and enter it into the list map.
282   DWARFListType List;
283   if (Header.length())
284     Data = DWARFDataExtractor(Data, getHeaderOffset() + Header.length());
285   if (Error E =
286           List.extract(Data, Header.length() ? getHeaderOffset() : 0, &Offset,
287                        Header.getSectionName(), Header.getListTypeString()))
288     return std::move(E);
289   return List;
290 }
291 
292 } // end namespace llvm
293 
294 #endif // LLVM_DEBUGINFO_DWARF_DWARFLISTTABLE_H
295