DebugInfo/DWARF/DWARFListTable.h

0001 //===- DWARFListTable.h -----------------------------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef LLVM_DEBUGINFO_DWARF_DWARFLISTTABLE_H
0010 #define LLVM_DEBUGINFO_DWARF_DWARFLISTTABLE_H
0011
0012 #include "llvm/BinaryFormat/Dwarf.h"
0013 #include "llvm/DebugInfo/DIContext.h"
0014 #include "llvm/DebugInfo/DWARF/DWARFDataExtractor.h"
0015 #include "llvm/Support/Errc.h"
0016 #include "llvm/Support/Error.h"
0017 #include "llvm/Support/raw_ostream.h"
0018 #include <cstdint>
0019 #include <map>
0020 #include <vector>
0021
0022 namespace llvm {
0023
0024 /// A base class for DWARF list entries, such as range or location list
0025 /// entries.
0026 struct DWARFListEntryBase {
0027   /// The offset at which the entry is located in the section.
0028   uint64_t Offset;
0029   /// The DWARF encoding (DW_RLE_* or DW_LLE_*).
0030   uint8_t EntryKind;
0031   /// The index of the section this entry belongs to.
0032   uint64_t SectionIndex;
0033 };
0034
0035 /// A base class for lists of entries that are extracted from a particular
0036 /// section, such as range lists or location lists.
0037 template <typename ListEntryType> class DWARFListType {
0038   using EntryType = ListEntryType;
0039   using ListEntries = std::vector<EntryType>;
0040
0041 protected:
0042   ListEntries Entries;
0043
0044 public:
0045   const ListEntries &getEntries() const { return Entries; }
0046   bool empty() const { return Entries.empty(); }
0047   void clear() { Entries.clear(); }
0048   Error extract(DWARFDataExtractor Data, uint64_t HeaderOffset,
0049                 uint64_t *OffsetPtr, StringRef SectionName,
0050                 StringRef ListStringName);
0051 };
0052
0053 /// A class representing the header of a list table such as the range list
0054 /// table in the .debug_rnglists section.
0055 class DWARFListTableHeader {
0056   struct Header {
0057     /// The total length of the entries for this table, not including the length
0058     /// field itself.
0059     uint64_t Length = 0;
0060     /// The DWARF version number.
0061     uint16_t Version;
0062     /// The size in bytes of an address on the target architecture. For
0063     /// segmented addressing, this is the size of the offset portion of the
0064     /// address.
0065     uint8_t AddrSize;
0066     /// The size in bytes of a segment selector on the target architecture.
0067     /// If the target system uses a flat address space, this value is 0.
0068     uint8_t SegSize;
0069     /// The number of offsets that follow the header before the range lists.
0070     uint32_t OffsetEntryCount;
0071   };
0072
0073   Header HeaderData;
0074   /// The table's format, either DWARF32 or DWARF64.
0075   dwarf::DwarfFormat Format;
0076   /// The offset at which the header (and hence the table) is located within
0077   /// its section.
0078   uint64_t HeaderOffset;
0079   /// The name of the section the list is located in.
0080   StringRef SectionName;
0081   /// A characterization of the list for dumping purposes, e.g. "range" or
0082   /// "location".
0083   StringRef ListTypeString;
0084
0085 public:
0086   DWARFListTableHeader(StringRef SectionName, StringRef ListTypeString)
0087       : SectionName(SectionName), ListTypeString(ListTypeString) {}
0088
0089   void clear() {
0090     HeaderData = {};
0091   }
0092   uint64_t getHeaderOffset() const { return HeaderOffset; }
0093   uint8_t getAddrSize() const { return HeaderData.AddrSize; }
0094   uint64_t getLength() const { return HeaderData.Length; }
0095   uint16_t getVersion() const { return HeaderData.Version; }
0096   uint32_t getOffsetEntryCount() const { return HeaderData.OffsetEntryCount; }
0097   StringRef getSectionName() const { return SectionName; }
0098   StringRef getListTypeString() const { return ListTypeString; }
0099   dwarf::DwarfFormat getFormat() const { return Format; }
0100
0101   /// Return the size of the table header including the length but not including
0102   /// the offsets.
0103   static uint8_t getHeaderSize(dwarf::DwarfFormat Format) {
0104     switch (Format) {
0105     case dwarf::DwarfFormat::DWARF32:
0106       return 12;
0107     case dwarf::DwarfFormat::DWARF64:
0108       return 20;
0109     }
0110     llvm_unreachable("Invalid DWARF format (expected DWARF32 or DWARF64");
0111   }
0112
0113   void dump(DataExtractor Data, raw_ostream &OS,
0114             DIDumpOptions DumpOpts = {}) const;
0115   std::optional<uint64_t> getOffsetEntry(DataExtractor Data,
0116                                          uint32_t Index) const {
0117     if (Index >= HeaderData.OffsetEntryCount)
0118       return std::nullopt;
0119
0120     return getOffsetEntry(Data, getHeaderOffset() + getHeaderSize(Format), Format, Index);
0121   }
0122
0123   static std::optional<uint64_t> getOffsetEntry(DataExtractor Data,
0124                                                 uint64_t OffsetTableOffset,
0125                                                 dwarf::DwarfFormat Format,
0126                                                 uint32_t Index) {
0127     uint8_t OffsetByteSize = Format == dwarf::DWARF64 ? 8 : 4;
0128     uint64_t Offset = OffsetTableOffset + OffsetByteSize * Index;
0129     auto R = Data.getUnsigned(&Offset, OffsetByteSize);
0130     return R;
0131   }
0132
0133   /// Extract the table header and the array of offsets.
0134   Error extract(DWARFDataExtractor Data, uint64_t *OffsetPtr);
0135
0136   /// Returns the length of the table, including the length field, or 0 if the
0137   /// length has not been determined (e.g. because the table has not yet been
0138   /// parsed, or there was a problem in parsing).
0139   uint64_t length() const;
0140 };
0141
0142 /// A class representing a table of lists as specified in the DWARF v5
0143 /// standard for location lists and range lists. The table consists of a header
0144 /// followed by an array of offsets into a DWARF section, followed by zero or
0145 /// more list entries. The list entries are kept in a map where the keys are
0146 /// the lists' section offsets.
0147 template <typename DWARFListType> class DWARFListTableBase {
0148   DWARFListTableHeader Header;
0149   /// A mapping between file offsets and lists. It is used to find a particular
0150   /// list based on an offset (obtained from DW_AT_ranges, for example).
0151   std::map<uint64_t, DWARFListType> ListMap;
0152   /// This string is displayed as a heading before the list is dumped
0153   /// (e.g. "ranges:").
0154   StringRef HeaderString;
0155
0156 protected:
0157   DWARFListTableBase(StringRef SectionName, StringRef HeaderString,
0158                      StringRef ListTypeString)
0159       : Header(SectionName, ListTypeString), HeaderString(HeaderString) {}
0160
0161 public:
0162   void clear() {
0163     Header.clear();
0164     ListMap.clear();
0165   }
0166   /// Extract the table header and the array of offsets.
0167   Error extractHeaderAndOffsets(DWARFDataExtractor Data, uint64_t *OffsetPtr) {
0168     return Header.extract(Data, OffsetPtr);
0169   }
0170   /// Extract an entire table, including all list entries.
0171   Error extract(DWARFDataExtractor Data, uint64_t *OffsetPtr);
0172   /// Look up a list based on a given offset. Extract it and enter it into the
0173   /// list map if necessary.
0174   Expected<DWARFListType> findList(DWARFDataExtractor Data,
0175                                    uint64_t Offset) const;
0176
0177   uint64_t getHeaderOffset() const { return Header.getHeaderOffset(); }
0178   uint8_t getAddrSize() const { return Header.getAddrSize(); }
0179   uint32_t getOffsetEntryCount() const { return Header.getOffsetEntryCount(); }
0180   dwarf::DwarfFormat getFormat() const { return Header.getFormat(); }
0181
0182   void
0183   dump(DWARFDataExtractor Data, raw_ostream &OS,
0184        llvm::function_ref<std::optional<object::SectionedAddress>(uint32_t)>
0185            LookupPooledAddress,
0186        DIDumpOptions DumpOpts = {}) const;
0187
0188   /// Return the contents of the offset entry designated by a given index.
0189   std::optional<uint64_t> getOffsetEntry(DataExtractor Data,
0190                                          uint32_t Index) const {
0191     return Header.getOffsetEntry(Data, Index);
0192   }
0193   /// Return the size of the table header including the length but not including
0194   /// the offsets. This is dependent on the table format, which is unambiguously
0195   /// derived from parsing the table.
0196   uint8_t getHeaderSize() const {
0197     return DWARFListTableHeader::getHeaderSize(getFormat());
0198   }
0199
0200   uint64_t length() { return Header.length(); }
0201 };
0202
0203 template <typename DWARFListType>
0204 Error DWARFListTableBase<DWARFListType>::extract(DWARFDataExtractor Data,
0205                                                  uint64_t *OffsetPtr) {
0206   clear();
0207   if (Error E = extractHeaderAndOffsets(Data, OffsetPtr))
0208     return E;
0209
0210   Data.setAddressSize(Header.getAddrSize());
0211   Data = DWARFDataExtractor(Data, getHeaderOffset() + Header.length());
0212   while (Data.isValidOffset(*OffsetPtr)) {
0213     DWARFListType CurrentList;
0214     uint64_t Off = *OffsetPtr;
0215     if (Error E = CurrentList.extract(Data, getHeaderOffset(), OffsetPtr,
0216                                       Header.getSectionName(),
0217                                       Header.getListTypeString()))
0218       return E;
0219     ListMap[Off] = CurrentList;
0220   }
0221
0222   assert(*OffsetPtr == Data.size() &&
0223          "mismatch between expected length of table and length "
0224          "of extracted data");
0225   return Error::success();
0226 }
0227
0228 template <typename ListEntryType>
0229 Error DWARFListType<ListEntryType>::extract(DWARFDataExtractor Data,
0230                                             uint64_t HeaderOffset,
0231                                             uint64_t *OffsetPtr,
0232                                             StringRef SectionName,
0233                                             StringRef ListTypeString) {
0234   if (*OffsetPtr < HeaderOffset || *OffsetPtr >= Data.size())
0235     return createStringError(errc::invalid_argument,
0236                        "invalid %s list offset 0x%" PRIx64,
0237                        ListTypeString.data(), *OffsetPtr);
0238   Entries.clear();
0239   while (Data.isValidOffset(*OffsetPtr)) {
0240     ListEntryType Entry;
0241     if (Error E = Entry.extract(Data, OffsetPtr))
0242       return E;
0243     Entries.push_back(Entry);
0244     if (Entry.isSentinel())
0245       return Error::success();
0246   }
0247   return createStringError(errc::illegal_byte_sequence,
0248                      "no end of list marker detected at end of %s table "
0249                      "starting at offset 0x%" PRIx64,
0250                      SectionName.data(), HeaderOffset);
0251 }
0252
0253 template <typename DWARFListType>
0254 void DWARFListTableBase<DWARFListType>::dump(
0255     DWARFDataExtractor Data, raw_ostream &OS,
0256     llvm::function_ref<std::optional<object::SectionedAddress>(uint32_t)>
0257         LookupPooledAddress,
0258     DIDumpOptions DumpOpts) const {
0259   Header.dump(Data, OS, DumpOpts);
0260   OS << HeaderString << "\n";
0261
0262   // Determine the length of the longest encoding string we have in the table,
0263   // so we can align the output properly. We only need this in verbose mode.
0264   size_t MaxEncodingStringLength = 0;
0265   if (DumpOpts.Verbose) {
0266     for (const auto &List : ListMap)
0267       for (const auto &Entry : List.second.getEntries())
0268         MaxEncodingStringLength =
0269             std::max(MaxEncodingStringLength,
0270                      dwarf::RangeListEncodingString(Entry.EntryKind).size());
0271   }
0272
0273   uint64_t CurrentBase = 0;
0274   for (const auto &List : ListMap)
0275     for (const auto &Entry : List.second.getEntries())
0276       Entry.dump(OS, getAddrSize(), MaxEncodingStringLength, CurrentBase,
0277                  DumpOpts, LookupPooledAddress);
0278 }
0279
0280 template <typename DWARFListType>
0281 Expected<DWARFListType>
0282 DWARFListTableBase<DWARFListType>::findList(DWARFDataExtractor Data,
0283                                             uint64_t Offset) const {
0284   // Extract the list from the section and enter it into the list map.
0285   DWARFListType List;
0286   if (Header.length())
0287     Data = DWARFDataExtractor(Data, getHeaderOffset() + Header.length());
0288   if (Error E =
0289           List.extract(Data, Header.length() ? getHeaderOffset() : 0, &Offset,
0290                        Header.getSectionName(), Header.getListTypeString()))
0291     return std::move(E);
0292   return List;
0293 }
0294
0295 } // end namespace llvm
0296
0297 #endif // LLVM_DEBUGINFO_DWARF_DWARFLISTTABLE_H