include/llvm/DebugInfo/DWARF/DWARFListTable.h

   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