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:
getEntries()46 const ListEntries &getEntries() const { return Entries; }
empty()47 bool empty() const { return Entries.empty(); }
clear()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:
DWARFListTableHeader(StringRef SectionName,StringRef ListTypeString)91 DWARFListTableHeader(StringRef SectionName, StringRef ListTypeString)
92 : SectionName(SectionName), ListTypeString(ListTypeString) {}
93
clear()94 void clear() {
95 HeaderData = {};
96 Offsets.clear();
97 }
getHeaderOffset()98 uint64_t getHeaderOffset() const { return HeaderOffset; }
getAddrSize()99 uint8_t getAddrSize() const { return HeaderData.AddrSize; }
getLength()100 uint64_t getLength() const { return HeaderData.Length; }
getVersion()101 uint16_t getVersion() const { return HeaderData.Version; }
getSectionName()102 StringRef getSectionName() const { return SectionName; }
getListTypeString()103 StringRef getListTypeString() const { return ListTypeString; }
getFormat()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.
getHeaderSize(dwarf::DwarfFormat Format)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;
getOffsetEntry(uint32_t Index)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:
DWARFListTableBase(StringRef SectionName,StringRef HeaderString,StringRef ListTypeString)149 DWARFListTableBase(StringRef SectionName, StringRef HeaderString,
150 StringRef ListTypeString)
151 : Header(SectionName, ListTypeString), HeaderString(HeaderString) {}
152
153 public:
clear()154 void clear() {
155 Header.clear();
156 ListMap.clear();
157 }
158 /// Extract the table header and the array of offsets.
extractHeaderAndOffsets(DWARFDataExtractor Data,uint64_t * OffsetPtr)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
getHeaderOffset()168 uint64_t getHeaderOffset() const { return Header.getHeaderOffset(); }
getAddrSize()169 uint8_t getAddrSize() const { return Header.getAddrSize(); }
getFormat()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.
getOffsetEntry(uint32_t 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.
getHeaderSize()184 uint8_t getHeaderSize() const {
185 return DWARFListTableHeader::getHeaderSize(getFormat());
186 }
187
length()188 uint64_t length() { return Header.length(); }
189 };
190
191 template <typename DWARFListType>
extract(DWARFDataExtractor Data,uint64_t * OffsetPtr)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>
extract(DWARFDataExtractor Data,uint64_t HeaderOffset,uint64_t End,uint64_t * OffsetPtr,StringRef SectionName,StringRef ListTypeString)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>
dump(raw_ostream & OS,llvm::function_ref<Optional<object::SectionedAddress> (uint32_t)> LookupPooledAddress,DIDumpOptions DumpOpts)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>
findList(DWARFDataExtractor Data,uint64_t Offset)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