include/llvm/DebugInfo/DWARF/DWARFListTable.h

   1 //===- DWARFListTable.h -----------------------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef LLVM_DEBUGINFO_DWARFLISTTABLE_H
  11 #define LLVM_DEBUGINFO_DWARFLISTTABLE_H
  12
  13 #include "llvm/BinaryFormat/Dwarf.h"
  14 #include "llvm/DebugInfo/DIContext.h"
  15 #include "llvm/DebugInfo/DWARF/DWARFDataExtractor.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   // FIXME: We need to consolidate the various verions of "createError"
  47   // that are used in the DWARF consumer. Until then, this is a workaround.
  48   Error createError(const char *, const char *, uint32_t);
  49
  50   const ListEntries &getEntries() const { return Entries; }
  51   bool empty() const { return Entries.empty(); }
  52   void clear() { Entries.clear(); }
  53   Error extract(DWARFDataExtractor Data, uint32_t HeaderOffset, uint32_t End,
  54                 uint32_t *OffsetPtr, StringRef SectionName,
  55                 StringRef ListStringName);
  56 };
  57
  58 /// A class representing the header of a list table such as the range list
  59 /// table in the .debug_rnglists section.
  60 class DWARFListTableHeader {
  61   struct Header {
  62     /// The total length of the entries for this table, not including the length
  63     /// field itself.
  64     uint32_t Length = 0;
  65     /// The DWARF version number.
  66     uint16_t Version;
  67     /// The size in bytes of an address on the target architecture. For
  68     /// segmented addressing, this is the size of the offset portion of the
  69     /// address.
  70     uint8_t AddrSize;
  71     /// The size in bytes of a segment selector on the target architecture.
  72     /// If the target system uses a flat address space, this value is 0.
  73     uint8_t SegSize;
  74     /// The number of offsets that follow the header before the range lists.
  75     uint32_t OffsetEntryCount;
  76   };
  77
  78   Header HeaderData;
  79   /// The offset table, which contains offsets to the individual list entries.
  80   /// It is used by forms such as DW_FORM_rnglistx.
  81   /// FIXME: Generate the table and use the appropriate forms.
  82   std::vector<uint32_t> Offsets;
  83   /// The table's format, either DWARF32 or DWARF64.
  84   dwarf::DwarfFormat Format;
  85   /// The offset at which the header (and hence the table) is located within
  86   /// its section.
  87   uint32_t HeaderOffset;
  88   /// The name of the section the list is located in.
  89   StringRef SectionName;
  90   /// A characterization of the list for dumping purposes, e.g. "range" or
  91   /// "location".
  92   StringRef ListTypeString;
  93
  94 public:
  95   DWARFListTableHeader(StringRef SectionName, StringRef ListTypeString)
  96       : SectionName(SectionName), ListTypeString(ListTypeString) {}
  97
  98   void clear() {
  99     HeaderData = {};
 100     Offsets.clear();
 101   }
 102   uint32_t getHeaderOffset() const { return HeaderOffset; }
 103   uint8_t getAddrSize() const { return HeaderData.AddrSize; }
 104   uint32_t getLength() const { return HeaderData.Length; }
 105   StringRef getSectionName() const { return SectionName; }
 106   StringRef getListTypeString() const { return ListTypeString; }
 107   dwarf::DwarfFormat getFormat() const { return Format; }
 108
 109   void dump(raw_ostream &OS, DIDumpOptions DumpOpts = {}) const;
 110   Optional<uint32_t> getOffsetEntry(uint32_t Index) const {
 111     if (Index < Offsets.size())
 112       return Offsets[Index];
 113     return None;
 114   }
 115
 116   /// Extract the table header and the array of offsets.
 117   Error extract(DWARFDataExtractor Data, uint32_t *OffsetPtr);
 118
 119   /// Returns the length of the table, including the length field, or 0 if the
 120   /// length has not been determined (e.g. because the table has not yet been
 121   /// parsed, or there was a problem in parsing).
 122   uint32_t length() const;
 123 };
 124
 125 /// A class representing a table of lists as specified in the DWARF v5
 126 /// standard for location lists and range lists. The table consists of a header
 127 /// followed by an array of offsets into a DWARF section, followed by zero or
 128 /// more list entries. The list entries are kept in a map where the keys are
 129 /// the lists' section offsets.
 130 template <typename DWARFListType> class DWARFListTableBase {
 131   DWARFListTableHeader Header;
 132   /// A mapping between file offsets and lists. It is used to find a particular
 133   /// list based on an offset (obtained from DW_AT_ranges, for example).
 134   std::map<uint32_t, DWARFListType> ListMap;
 135   /// This string is displayed as a heading before the list is dumped
 136   /// (e.g. "ranges:").
 137   StringRef HeaderString;
 138
 139 protected:
 140   DWARFListTableBase(StringRef SectionName, StringRef HeaderString,
 141                      StringRef ListTypeString)
 142       : Header(SectionName, ListTypeString), HeaderString(HeaderString) {}
 143
 144 public:
 145   void clear() {
 146     Header.clear();
 147     ListMap.clear();
 148   }
 149   /// Extract the table header and the array of offsets.
 150   Error extractHeaderAndOffsets(DWARFDataExtractor Data, uint32_t *OffsetPtr) {
 151     return Header.extract(Data, OffsetPtr);
 152   }
 153   /// Extract an entire table, including all list entries.
 154   Error extract(DWARFDataExtractor Data, uint32_t *OffsetPtr);
 155   /// Look up a list based on a given offset. Extract it and enter it into the
 156   /// list map if necessary.
 157   Expected<DWARFListType> findList(DWARFDataExtractor Data, uint32_t Offset);
 158
 159   uint32_t getHeaderOffset() const { return Header.getHeaderOffset(); }
 160   uint8_t getAddrSize() const { return Header.getAddrSize(); }
 161
 162   void dump(raw_ostream &OS, 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 createError("invalid %s list offset 0x%" PRIx32,
 217                        ListTypeString.data(), *OffsetPtr);
 218   Entries.clear();
 219   while (*OffsetPtr < End) {
 220     ListEntryType Entry;
 221     if (Error E = Entry.extract(Data, End, OffsetPtr))
 222       return E;
 223     Entries.push_back(Entry);
 224     if (Entry.isSentinel())
 225       return Error::success();
 226   }
 227   return createError("no end of list marker detected at end of %s table "
 228                      "starting at offset 0x%" PRIx32,
 229                      SectionName.data(), HeaderOffset);
 230 }
 231
 232 template <typename DWARFListType>
 233 void DWARFListTableBase<DWARFListType>::dump(raw_ostream &OS,
 234                                              DIDumpOptions DumpOpts) const {
 235   Header.dump(OS, DumpOpts);
 236   OS << HeaderString << "\n";
 237
 238   // Determine the length of the longest encoding string we have in the table,
 239   // so we can align the output properly. We only need this in verbose mode.
 240   size_t MaxEncodingStringLength = 0;
 241   if (DumpOpts.Verbose) {
 242     for (const auto &List : ListMap)
 243       for (const auto &Entry : List.second.getEntries())
 244         MaxEncodingStringLength =
 245             std::max(MaxEncodingStringLength,
 246                      dwarf::RangeListEncodingString(Entry.EntryKind).size());
 247   }
 248
 249   uint64_t CurrentBase = 0;
 250   for (const auto &List : ListMap)
 251     for (const auto &Entry : List.second.getEntries())
 252       Entry.dump(OS, getAddrSize(), MaxEncodingStringLength, CurrentBase,
 253                  DumpOpts);
 254 }
 255
 256 template <typename DWARFListType>
 257 Expected<DWARFListType>
 258 DWARFListTableBase<DWARFListType>::findList(DWARFDataExtractor Data,
 259                                             uint32_t Offset) {
 260   auto Entry = ListMap.find(Offset);
 261   if (Entry != ListMap.end())
 262     return Entry->second;
 263
 264   // Extract the list from the section and enter it into the list map.
 265   DWARFListType List;
 266   uint32_t End = getHeaderOffset() + Header.length();
 267   uint32_t StartingOffset = Offset;
 268   if (Error E =
 269           List.extract(Data, getHeaderOffset(), End, &Offset,
 270                        Header.getSectionName(), Header.getListTypeString()))
 271     return std::move(E);
 272   ListMap[StartingOffset] = List;
 273   return List;
 274 }
 275
 276 } // end namespace llvm
 277
 278 #endif // LLVM_DEBUGINFO_DWARFLISTTABLE_H