DWARFListTable.h revision 360784 
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
23namespace llvm {
24
25/// A base class for DWARF list entries, such as range or location list
26/// entries.
27struct 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.
38template <typename ListEntryType> class DWARFListType {
39  using EntryType = ListEntryType;
40  using ListEntries = std::vector<EntryType>;
41
42protected:
43  ListEntries Entries;
44
45public:
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.
56class 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
90public:
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.
139template <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
148protected:
149  DWARFListTableBase(StringRef SectionName, StringRef HeaderString,
150                     StringRef ListTypeString)
151      : Header(SectionName, ListTypeString), HeaderString(HeaderString) {}
152
153public:
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
191template <typename DWARFListType>
192Error 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
216template <typename ListEntryType>
217Error 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
241template <typename DWARFListType>
242void 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
268template <typename DWARFListType>
269Expected<DWARFListType>
270DWARFListTableBase<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