[DWARF v5][NFC] Refactor the implementation of DebugRnglists

[wolfgangp]

Summary

The current implementation of DebugRnglists (essentially the handling of the DWARF v5 .debug_rnglists and .debug_rnglists.dwo sections) is geared towards dumping the section. To handle references from DIEs via the DW_AT_ranges attribute we need more flexibility, which is what this refactor is trying to do.

The following changes are in this patch:

1. Parsing of rnglist tables is separated into parsing of headers/offsets and parsing (extracting) of individual rangelists. The previously monolithic extract() routine is broken into 3 parts: a) extraction of an individual rnglist entry, b) extraction of a rnglist (made up of multiple entries) and c) extraction of the entire table.

The idea is that the table headers and offsets are parsed when we first encounter the DW_AT_rnglist_base attribute in the CU DIE (or when we parse the CU DIE in split units). As we see DW_AT_ranges attributes in DIEs, we parse the rnglists referenced by them and enter them into a map (with section offsets as keys), where they can be looked up. The code for this will follow. This is just prep.

2. We calculate the maximum encoding string length for dumping before we dump the table and not during parsing of the range lists. Only the dumper cares about this.

Not in this patch is an interface to extract a range list from a section offset and a way to convert a range list into a DWARFAddressRangesVector, which is what DWARFDie::getAddressRanges returns. These will be part of the next patch, which will implement the full functionality with tests.

[JDevlieghere]

LGTM

lib/DebugInfo/DWARF/DWARFDebugRnglists.cpp

168 ↗

(On Diff #141095)

Maybe we should have a constructor for this?

[wolfgangp]

lib/DebugInfo/DWARF/DWARFDebugRnglists.cpp

168 ↗

(On Diff #141095)

I had a constructor in an earlier version (before this patch), but Dave suggested to get rid of it in favor of simple braced initializers. I don't have a strong opinion on this but it does seem to me that a constructor would add little value, given that it's really a very simple type, and the braced initializer does the same thing. I also don't anticipate this data structure to be created in lots of other places, where a constructor would provide more safety.

If you don't mind I'd like to keep it that way unless you feel strongly about it.

[dblaikie]

include/llvm/DebugInfo/DWARF/DWARFDebugRnglists.h

40 ↗

(On Diff #141095)

Maybe this (& DWARFDebugRngList::extract) should be a factory function (either static member or free function) returning ErrorOr<RangeListEntry> (and ErrorOr<DWARFDebugRngList>) - encapsulation doesn't seem to important here - a vector of structs seems like a pretty fine data structure for this purpose/no need to wrap it up in public/private things, etc?

llvm/trunk/include/llvm/DebugInfo/DWARF/DWARFDebugRnglists.h

 //===- DWARFDebugRnglists.h -------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_DEBUGINFO_DWARFDEBUGRNGLISTS_H
 #define LLVM_DEBUGINFO_DWARFDEBUGRNGLISTS_H
 
 #include "llvm/DebugInfo/DIContext.h"
 #include "llvm/DebugInfo/DWARF/DWARFDataExtractor.h"
 #include "llvm/DebugInfo/DWARF/DWARFDebugRangeList.h"
 #include <cstdint>
+#include <map>
 #include <vector>
 
 namespace llvm {
 
 class Error;
 class raw_ostream;
 
-class DWARFDebugRnglists {
+/// A class representing a single rangelist.
+class DWARFDebugRnglist {
+public:
+  struct RangeListEntry {
+    /// The offset at which the entry is located in the section.
+    uint32_t Offset;
+    /// The DWARF encoding (DW_RLE_*).
+    uint8_t EntryKind;
+    /// The values making up the range list entry. Most represent a range with
+    /// a start and end address or a start address and a length. Others are
+    /// single value base addresses or end-of-list with no values. The unneeded
+    /// values are semantically undefined, but initialized to 0.
+    uint64_t Value0;
+    uint64_t Value1;
+
+    Error extract(DWARFDataExtractor Data, uint32_t End, uint32_t *OffsetPtr);
+  };
+
+  using RngListEntries = std::vector<RangeListEntry>;
+
 private:
+  RngListEntries Entries;
+
+public:
+  const RngListEntries &getEntries() const { return Entries; }
+  bool empty() const { return Entries.empty(); }
+  void clear() { Entries.clear(); }
+  Error extract(DWARFDataExtractor Data, uint32_t HeaderOffset, uint32_t End,
+                uint32_t *OffsetPtr);
+};
+
+/// A class representing a table of range lists as specified in DWARF v5.
+/// The table consists of a header followed by an array of offsets into the
+/// .debug_rnglists section, followed by one or more rangelists. The rangelists
+/// are kept in a map where the keys are the lists' section offsets.
+class DWARFDebugRnglistTable {
+public:
   struct Header {
     /// The total length of the entries for this table, not including the length
     /// field itself.
     uint32_t Length = 0;
     /// The DWARF version number.
     uint16_t Version;
     /// The size in bytes of an address on the target architecture. For
     /// segmented addressing, this is the size of the offset portion of the
     /// address.
     uint8_t AddrSize;
     /// The size in bytes of a segment selector on the target architecture.
     /// If the target system uses a flat address space, this value is 0.
     uint8_t SegSize;
     /// The number of offsets that follow the header before the range lists.
     uint32_t OffsetEntryCount;
   };
 
-public:
-  struct RangeListEntry {
-    /// The offset at which the entry is located in the section.
-    const uint32_t Offset;
-    /// The DWARF encoding (DW_RLE_*).
-    const uint8_t EntryKind;
-    /// The values making up the range list entry. Most represent a range with
-    /// a start and end address or a start address and a length. Others are
-    /// single value base addresses or end-of-list with no values. The unneeded
-    /// values are semantically undefined, but initialized to 0.
-    const uint64_t Value0;
-    const uint64_t Value1;
-  };
-
-  using DWARFRangeList = std::vector<RangeListEntry>;
-
 private:
   uint32_t HeaderOffset;
   Header HeaderData;
   std::vector<uint32_t> Offsets;
-  std::vector<DWARFRangeList> Ranges;
-  // The length of the longest encoding string we encountered during parsing.
-  uint8_t MaxEncodingStringLength = 0;
+  std::map<uint32_t, DWARFDebugRnglist> Ranges;
 
 public:
   void clear();
+  /// Extract the table header and the array of offsets.
+  Error extractHeaderAndOffsets(DWARFDataExtractor Data, uint32_t *OffsetPtr);
+  /// Extract an entire table, including all rangelists.
   Error extract(DWARFDataExtractor Data, uint32_t *OffsetPtr);
   uint32_t getHeaderOffset() const { return HeaderOffset; }
   void dump(raw_ostream &OS, DIDumpOptions DumpOpts) const;
 
   /// Returns the length of this table, including the length field, or 0 if the
   /// length has not been determined (e.g. because the table has not yet been
   /// parsed, or there was a problem in parsing).
   uint32_t length() const;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_DWARFDEBUGRNGLISTS_H

llvm/trunk/lib/DebugInfo/DWARF/DWARFContext.cpp

void DWARFContext::dump(
   }
 
   if (shouldDump(Explicit, ".debug_rnglists", DIDT_ID_DebugRnglists,
                  DObj->getRnglistsSection().Data)) {
     DWARFDataExtractor rnglistData(*DObj, DObj->getRnglistsSection(),
                                    isLittleEndian(), 0);
     uint32_t Offset = 0;
     while (rnglistData.isValidOffset(Offset)) {
-      DWARFDebugRnglists Rnglists;
+      DWARFDebugRnglistTable Rnglists;
       uint32_t TableOffset = Offset;
       if (Error Err = Rnglists.extract(rnglistData, &Offset)) {
         errs() << "error: " + toString(std::move(Err)) << '\n';
         uint64_t Length = Rnglists.length();
         // Keep going after an error, if we can, assuming that the length field
         // could be read. If it couldn't, stop reading the section.
         if (Length == 0)
           break;

llvm/trunk/lib/DebugInfo/DWARF/DWARFDebugRnglists.cpp

 
 #include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 
-void DWARFDebugRnglists::clear() {
+void DWARFDebugRnglistTable::clear() {
   HeaderData = {};
   Offsets.clear();
   Ranges.clear();
 }
 
 template <typename... Ts>
 static Error createError(char const *Fmt, const Ts &... Vals) {
   std::string Buffer;
   raw_string_ostream Stream(Buffer);
   Stream << format(Fmt, Vals...);
   return make_error<StringError>(Stream.str(), inconvertibleErrorCode());
 }
 
-Error DWARFDebugRnglists::extract(DWARFDataExtractor Data,
+Error DWARFDebugRnglistTable::extractHeaderAndOffsets(DWARFDataExtractor Data,
                                                       uint32_t *OffsetPtr) {
-  clear();
   HeaderOffset = *OffsetPtr;
-
   // Read and verify the length field.
   if (!Data.isValidOffsetForDataOfSize(*OffsetPtr, sizeof(uint32_t)))
     return createError("section is not large enough to contain a "
                        ".debug_rnglists table length at offset 0x%" PRIx32,
                        *OffsetPtr);
   // TODO: Add support for DWARF64.
   HeaderData.Length = Data.getU32(OffsetPtr);
   if (HeaderData.Length == 0xffffffffu)
return createError(".debug_rnglists table at offset 0x%" PRIx32
                        " has unsupported segment selector size %" PRIu8,
                        HeaderOffset, HeaderData.SegSize);
   if (End < HeaderOffset + sizeof(HeaderData) +
                 HeaderData.OffsetEntryCount * sizeof(uint32_t))
     return createError(".debug_rnglists table at offset 0x%" PRIx32
                        " has more offset entries (%" PRIu32
                        ") than there is space for",
                        HeaderOffset, HeaderData.OffsetEntryCount);
-
   Data.setAddressSize(HeaderData.AddrSize);
-
   for (uint32_t I = 0; I < HeaderData.OffsetEntryCount; ++I)
     Offsets.push_back(Data.getU32(OffsetPtr));
+  return Error::success();
+}
 
-  DWARFRangeList CurrentRanges;
-  while (*OffsetPtr < End) {
-    uint32_t EntryOffset = *OffsetPtr;
-    uint8_t Encoding = Data.getU8(OffsetPtr);
-    MaxEncodingStringLength =
-        std::max(MaxEncodingStringLength,
-                 (uint8_t)dwarf::RangeListEncodingString(Encoding).size());
-    switch (Encoding) {
-    case dwarf::DW_RLE_end_of_list:
-      CurrentRanges.push_back(RangeListEntry{ EntryOffset, Encoding, 0, 0 });
-      Ranges.insert(Ranges.end(), std::move(CurrentRanges));
-      CurrentRanges.clear();
-      break;
-    // TODO: Support other encodings.
-    case dwarf::DW_RLE_base_addressx:
-      return createError("unsupported rnglists encoding DW_RLE_base_addressx "
-                         "at offset 0x%" PRIx32,
-                         *OffsetPtr - 1);
-    case dwarf::DW_RLE_startx_endx:
-      return createError("unsupported rnglists encoding DW_RLE_startx_endx at "
-                         "offset 0x%" PRIx32,
-                         *OffsetPtr - 1);
-    case dwarf::DW_RLE_startx_length:
-      return createError("unsupported rnglists encoding DW_RLE_startx_length "
-                         "at offset 0x%" PRIx32,
-                         *OffsetPtr - 1);
-    case dwarf::DW_RLE_offset_pair: {
-      uint32_t PreviousOffset = *OffsetPtr - 1;
-      uint64_t StartingOffset = Data.getULEB128(OffsetPtr);
-      uint64_t EndingOffset = Data.getULEB128(OffsetPtr);
-      if (End < *OffsetPtr)
-        return createError("read past end of table when reading "
-                           "DW_RLE_offset_pair encoding at offset 0x%" PRIx32,
-                           PreviousOffset);
-      CurrentRanges.push_back(
-          RangeListEntry{EntryOffset, Encoding, StartingOffset, EndingOffset});
-      break;
-    }
-    case dwarf::DW_RLE_base_address: {
-      if ((End - *OffsetPtr) < HeaderData.AddrSize)
-        return createError("insufficient space remaining in table for "
-                           "DW_RLE_base_address encoding at offset 0x%" PRIx32,
-                           *OffsetPtr - 1);
-      uint64_t Base = Data.getAddress(OffsetPtr);
-      CurrentRanges.push_back(RangeListEntry{EntryOffset, Encoding, Base, 0});
-      break;
-    }
-    case dwarf::DW_RLE_start_end: {
-      if ((End - *OffsetPtr) < unsigned(HeaderData.AddrSize * 2))
-        return createError("insufficient space remaining in table for "
-                           "DW_RLE_start_end encoding "
-                           "at offset 0x%" PRIx32,
-                           *OffsetPtr - 1);
-      uint64_t Start = Data.getAddress(OffsetPtr);
-      uint64_t End = Data.getAddress(OffsetPtr);
-      CurrentRanges.push_back(
-          RangeListEntry{EntryOffset, Encoding, Start, End});
-      break;
-    }
-    case dwarf::DW_RLE_start_length: {
-      uint32_t PreviousOffset = *OffsetPtr - 1;
-      uint64_t Start = Data.getAddress(OffsetPtr);
-      uint64_t Length = Data.getULEB128(OffsetPtr);
-      if (End < *OffsetPtr)
-        return createError("read past end of table when reading "
-                           "DW_RLE_start_length encoding at offset 0x%" PRIx32,
-                           PreviousOffset);
-      CurrentRanges.push_back(
-          RangeListEntry{EntryOffset, Encoding, Start, Length});
-      break;
-    }
-    default:
-      Ranges.insert(Ranges.end(), std::move(CurrentRanges));
-      return createError("unknown rnglists encoding 0x%" PRIx32
-                         " at offset 0x%" PRIx32,
-                         uint32_t(Encoding), *OffsetPtr - 1);
-    }
-  }
+Error DWARFDebugRnglist::RangeListEntry::extract(DWARFDataExtractor Data,
+                                                 uint32_t End,
+                                                 uint32_t *OffsetPtr) {
+  Offset = *OffsetPtr;
+  // The caller should guarantee that we have at least 1 byte available, so
+  // we just assert instead of revalidate.
+  assert(*OffsetPtr < End &&
+         "not enough space to extract a rangelist encoding");
+
+    Value0 = Value1 = 0;
+    Value0 = Data.getULEB128(OffsetPtr);
+    Value1 = Data.getULEB128(OffsetPtr);
+    if ((End - *OffsetPtr) < Data.getAddressSize())
+    Value0 = Data.getAddress(OffsetPtr);
+    if ((End - *OffsetPtr) < unsigned(Data.getAddressSize() * 2))
+    Value0 = Data.getAddress(OffsetPtr);
+    Value1 = Data.getAddress(OffsetPtr);
+    Value0 = Data.getAddress(OffsetPtr);
+    Value1 = Data.getULEB128(OffsetPtr);
 
-  // If OffsetPtr does not indicate the End offset, then either the above loop
-  // terminated prematurely, or we encountered a malformed encoding, but did not
-  // report an error when we should have done.
-  assert(*OffsetPtr == End &&
-         "did not detect malformed data or loop ended unexpectedly");
+  EntryKind = Encoding;
+  return Error::success();
+}
 
-  // If CurrentRanges is not empty, we have a malformed section, because we did
-  // not find a DW_RLE_end_of_list marker at the end of the last list.
-  if (!CurrentRanges.empty())
-    return createError(
-        "no end of list marker detected at end of .debug_rnglists table "
-        "starting at offset 0x%" PRIx32,
-        HeaderOffset);
+Error DWARFDebugRnglist::extract(DWARFDataExtractor Data, uint32_t HeaderOffset,
+                                 uint32_t End, uint32_t *OffsetPtr) {
+  Entries.clear();
+  while (*OffsetPtr < End) {
+    RangeListEntry Entry{0, 0, 0, 0};
+    if (Error E = Entry.extract(Data, End, OffsetPtr))
+      return E;
+    Entries.push_back(Entry);
+    if (Entry.EntryKind == dwarf::DW_RLE_end_of_list)
+      return Error::success();
+  }
+}
+
+Error DWARFDebugRnglistTable::extract(DWARFDataExtractor Data,
+                                      uint32_t *OffsetPtr) {
+  clear();
+  if (Error E = extractHeaderAndOffsets(Data, OffsetPtr))
+    return E;
+
+  Data.setAddressSize(HeaderData.AddrSize);
+  uint32_t End = HeaderOffset + length();
+  while (*OffsetPtr < End) {
+    DWARFDebugRnglist CurrentRangeList;
+    uint32_t Off = *OffsetPtr;
+    if (Error E = CurrentRangeList.extract(Data, HeaderOffset, End, OffsetPtr))
+      return E;
+    Ranges[Off] = CurrentRangeList;
+  }
+
+  assert(*OffsetPtr == End &&
+         "mismatch between expected length of .debug_rnglists table and length "
+         "of extracted data");
   return Error::success();
 }
 
 static void dumpRangeEntry(raw_ostream &OS,
-                           DWARFDebugRnglists::RangeListEntry Entry,
+                           DWARFDebugRnglist::RangeListEntry Entry,
                            uint8_t AddrSize, uint8_t MaxEncodingStringLength,
                            uint64_t &CurrentBase, DIDumpOptions DumpOpts) {
   auto PrintRawEntry = [](raw_ostream &OS,
-                          DWARFDebugRnglists::RangeListEntry Entry,
+                          DWARFDebugRnglist::RangeListEntry Entry,
                           uint8_t AddrSize, DIDumpOptions DumpOpts) {
     if (DumpOpts.Verbose) {
       DumpOpts.DisplayRawContents = true;
       DWARFAddressRange(Entry.Value0, Entry.Value1)
           .dump(OS, AddrSize, DumpOpts);
       OS << " => ";
     }
   };
case dwarf::DW_RLE_start_end:
     DWARFAddressRange(Entry.Value0, Entry.Value1).dump(OS, AddrSize, DumpOpts);
     break;
   default:
     llvm_unreachable("Unsupported range list encoding");
   }
   OS << "\n";
 }
 
-void DWARFDebugRnglists::dump(raw_ostream &OS, DIDumpOptions DumpOpts) const {
+void DWARFDebugRnglistTable::dump(raw_ostream &OS,
+                                  DIDumpOptions DumpOpts) const {
   if (DumpOpts.Verbose)
     OS << format("0x%8.8" PRIx32 ": ", HeaderOffset);
   OS << format("Range List Header: length = 0x%8.8" PRIx32
                ", version = 0x%4.4" PRIx16 ", "
                "addr_size = 0x%2.2" PRIx8 ", seg_size = 0x%2.2" PRIx8
                ", offset_entry_count = "
                "0x%8.8" PRIx32 "\n",
                HeaderData.Length, HeaderData.Version, HeaderData.AddrSize,
                HeaderData.SegSize, HeaderData.OffsetEntryCount);
 
   if (HeaderData.OffsetEntryCount > 0) {
     OS << "Offsets: [";
     for (const auto &Off : Offsets) {
       OS << format("\n0x%8.8" PRIx32, Off);
       if (DumpOpts.Verbose)
         OS << format(" => 0x%8.8" PRIx32,
                      Off + HeaderOffset + sizeof(HeaderData));
     }
     OS << "\n]\n";
   }
   OS << "Ranges:\n";
 
+  // Determine the length of the longest encoding string we have in the table,
+  // so we can align the output properly. We only need this in verbose mode.
+  size_t MaxEncodingStringLength = 0;
+  if (DumpOpts.Verbose) {
+    for (const auto &List : Ranges)
+      for (const auto &Entry : List.second.getEntries())
+        MaxEncodingStringLength =
+            std::max(MaxEncodingStringLength,
+                     dwarf::RangeListEncodingString(Entry.EntryKind).size());
+  }
+
   uint64_t CurrentBase = 0;
   for (const auto &List : Ranges)
-    for (const auto &Entry : List)
+    for (const auto &Entry : List.second.getEntries())
       dumpRangeEntry(OS, Entry, HeaderData.AddrSize, MaxEncodingStringLength,
                      CurrentBase, DumpOpts);
 }
 
-uint32_t DWARFDebugRnglists::length() const {
+uint32_t DWARFDebugRnglistTable::length() const {
   if (HeaderData.Length == 0)
     return 0;
   // TODO: DWARF64 support.
   return HeaderData.Length + sizeof(uint32_t);
 }