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