contrib/llvm-project/llvm/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   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