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 uint32_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, uint32_t HeaderOffset, uint32_t End, 50 uint32_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 uint32_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<uint32_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 uint32_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 uint32_t getHeaderOffset() const { return HeaderOffset; } 99 uint8_t getAddrSize() const { return HeaderData.AddrSize; } 100 uint32_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 void dump(raw_ostream &OS, DIDumpOptions DumpOpts = {}) const; 107 Optional<uint32_t> getOffsetEntry(uint32_t Index) const { 108 if (Index < Offsets.size()) 109 return Offsets[Index]; 110 return None; 111 } 112 113 /// Extract the table header and the array of offsets. 114 Error extract(DWARFDataExtractor Data, uint32_t *OffsetPtr); 115 116 /// Returns the length of the table, including the length field, or 0 if the 117 /// length has not been determined (e.g. because the table has not yet been 118 /// parsed, or there was a problem in parsing). 119 uint32_t length() const; 120 }; 121 122 /// A class representing a table of lists as specified in the DWARF v5 123 /// standard for location lists and range lists. The table consists of a header 124 /// followed by an array of offsets into a DWARF section, followed by zero or 125 /// more list entries. The list entries are kept in a map where the keys are 126 /// the lists' section offsets. 127 template <typename DWARFListType> class DWARFListTableBase { 128 DWARFListTableHeader Header; 129 /// A mapping between file offsets and lists. It is used to find a particular 130 /// list based on an offset (obtained from DW_AT_ranges, for example). 131 std::map<uint32_t, DWARFListType> ListMap; 132 /// This string is displayed as a heading before the list is dumped 133 /// (e.g. "ranges:"). 134 StringRef HeaderString; 135 136 protected: 137 DWARFListTableBase(StringRef SectionName, StringRef HeaderString, 138 StringRef ListTypeString) 139 : Header(SectionName, ListTypeString), HeaderString(HeaderString) {} 140 141 public: 142 void clear() { 143 Header.clear(); 144 ListMap.clear(); 145 } 146 /// Extract the table header and the array of offsets. 147 Error extractHeaderAndOffsets(DWARFDataExtractor Data, uint32_t *OffsetPtr) { 148 return Header.extract(Data, OffsetPtr); 149 } 150 /// Extract an entire table, including all list entries. 151 Error extract(DWARFDataExtractor Data, uint32_t *OffsetPtr); 152 /// Look up a list based on a given offset. Extract it and enter it into the 153 /// list map if necessary. 154 Expected<DWARFListType> findList(DWARFDataExtractor Data, uint32_t Offset); 155 156 uint32_t getHeaderOffset() const { return Header.getHeaderOffset(); } 157 uint8_t getAddrSize() const { return Header.getAddrSize(); } 158 159 void dump(raw_ostream &OS, 160 llvm::function_ref<Optional<object::SectionedAddress>(uint32_t)> 161 LookupPooledAddress, 162 DIDumpOptions DumpOpts = {}) const; 163 164 /// Return the contents of the offset entry designated by a given index. 165 Optional<uint32_t> getOffsetEntry(uint32_t Index) const { 166 return Header.getOffsetEntry(Index); 167 } 168 /// Return the size of the table header including the length but not including 169 /// the offsets. This is dependent on the table format, which is unambiguously 170 /// derived from parsing the table. 171 uint8_t getHeaderSize() const { 172 switch (Header.getFormat()) { 173 case dwarf::DwarfFormat::DWARF32: 174 return 12; 175 case dwarf::DwarfFormat::DWARF64: 176 return 20; 177 } 178 llvm_unreachable("Invalid DWARF format (expected DWARF32 or DWARF64"); 179 } 180 181 uint32_t length() { return Header.length(); } 182 }; 183 184 template <typename DWARFListType> 185 Error DWARFListTableBase<DWARFListType>::extract(DWARFDataExtractor Data, 186 uint32_t *OffsetPtr) { 187 clear(); 188 if (Error E = extractHeaderAndOffsets(Data, OffsetPtr)) 189 return E; 190 191 Data.setAddressSize(Header.getAddrSize()); 192 uint32_t End = getHeaderOffset() + Header.length(); 193 while (*OffsetPtr < End) { 194 DWARFListType CurrentList; 195 uint32_t Off = *OffsetPtr; 196 if (Error E = CurrentList.extract(Data, getHeaderOffset(), End, OffsetPtr, 197 Header.getSectionName(), 198 Header.getListTypeString())) 199 return E; 200 ListMap[Off] = CurrentList; 201 } 202 203 assert(*OffsetPtr == End && 204 "mismatch between expected length of table and length " 205 "of extracted data"); 206 return Error::success(); 207 } 208 209 template <typename ListEntryType> 210 Error DWARFListType<ListEntryType>::extract(DWARFDataExtractor Data, 211 uint32_t HeaderOffset, uint32_t End, 212 uint32_t *OffsetPtr, 213 StringRef SectionName, 214 StringRef ListTypeString) { 215 if (*OffsetPtr < HeaderOffset || *OffsetPtr >= End) 216 return createStringError(errc::invalid_argument, 217 "invalid %s list offset 0x%" PRIx32, 218 ListTypeString.data(), *OffsetPtr); 219 Entries.clear(); 220 while (*OffsetPtr < End) { 221 ListEntryType Entry; 222 if (Error E = Entry.extract(Data, End, OffsetPtr)) 223 return E; 224 Entries.push_back(Entry); 225 if (Entry.isSentinel()) 226 return Error::success(); 227 } 228 return createStringError(errc::illegal_byte_sequence, 229 "no end of list marker detected at end of %s table " 230 "starting at offset 0x%" PRIx32, 231 SectionName.data(), HeaderOffset); 232 } 233 234 template <typename DWARFListType> 235 void DWARFListTableBase<DWARFListType>::dump( 236 raw_ostream &OS, 237 llvm::function_ref<Optional<object::SectionedAddress>(uint32_t)> 238 LookupPooledAddress, 239 DIDumpOptions DumpOpts) const { 240 Header.dump(OS, DumpOpts); 241 OS << HeaderString << "\n"; 242 243 // Determine the length of the longest encoding string we have in the table, 244 // so we can align the output properly. We only need this in verbose mode. 245 size_t MaxEncodingStringLength = 0; 246 if (DumpOpts.Verbose) { 247 for (const auto &List : ListMap) 248 for (const auto &Entry : List.second.getEntries()) 249 MaxEncodingStringLength = 250 std::max(MaxEncodingStringLength, 251 dwarf::RangeListEncodingString(Entry.EntryKind).size()); 252 } 253 254 uint64_t CurrentBase = 0; 255 for (const auto &List : ListMap) 256 for (const auto &Entry : List.second.getEntries()) 257 Entry.dump(OS, getAddrSize(), MaxEncodingStringLength, CurrentBase, 258 DumpOpts, LookupPooledAddress); 259 } 260 261 template <typename DWARFListType> 262 Expected<DWARFListType> 263 DWARFListTableBase<DWARFListType>::findList(DWARFDataExtractor Data, 264 uint32_t Offset) { 265 auto Entry = ListMap.find(Offset); 266 if (Entry != ListMap.end()) 267 return Entry->second; 268 269 // Extract the list from the section and enter it into the list map. 270 DWARFListType List; 271 uint32_t End = getHeaderOffset() + Header.length(); 272 uint32_t StartingOffset = Offset; 273 if (Error E = 274 List.extract(Data, getHeaderOffset(), End, &Offset, 275 Header.getSectionName(), Header.getListTypeString())) 276 return std::move(E); 277 ListMap[StartingOffset] = List; 278 return List; 279 } 280 281 } // end namespace llvm 282 283 #endif // LLVM_DEBUGINFO_DWARFLISTTABLE_H 284