[WIP][DebugInfo] Lazily parse debug_loclist offsets

[dblaikie]

Summary

Parsing DWARFv5 debug_loclist offsets when a CU is parsed is weighing
down memory usage of symbolizers that don't need to parse this data at
all. There's not much benefit to caching these anyway - since they are
O(1) lookup and reading once you know where the offset list starts (and
can do bounds checking with the offset list size too).

In general, I think it might be time to start paying down some of the
technical debt of loc/loclist/range/rnglist parsing to try to unify it a
bit more.

eg:

• Currently DWARFUnit has: RangeSection, RangeSectionBase, LocSection, LocSectionBase, LocTable, RngListTable, LoclistTableHeader (be nice if these were all wrapped up in two variables - one for loclists, one for rnglists)

• rnglists and loclists are handled differently (see: LoclistTableHeader, but no RnglistTableHeader)

• maybe all these types could be less stateful - lazily parse what they need to, even reparsing rather than caching because it doesn't seem too expensive, for instance. (though admittedly so long as it's constantcost/overead per compilatiton that's probably adequate)

• Maybe implementing and using a DWARFDataExtractor that can be sub-ranged (so we could slice it up to just the single contribution) - though maybe that's not so useful because loc/ranges need to refer to it by absolute, not contribution-relative mechanisms

[labath]

This sounds perfectly reasonable to me. The offsets are present in memory already so there's no point in storing them in a vector as well.

[dblaikie]

In D86110#2223905, @labath wrote:

This sounds perfectly reasonable to me. The offsets are present in memory already so there's no point in storing them in a vector as well.

Thanks for taking a look! I'll take this as approval and commit soon.

[labath]

In D86110#2224163, @dblaikie wrote:

In D86110#2223905, @labath wrote:

This sounds perfectly reasonable to me. The offsets are present in memory already so there's no point in storing them in a vector as well.

Thanks for taking a look! I'll take this as approval and commit soon.

The patch had a WIP label, so I was only looking/commenting on the high-level idea. But after looking at the implementation more closely, I think that looks good too.

[dblaikie]

In D86110#2225970, @labath wrote:

In D86110#2224163, @dblaikie wrote:

In D86110#2223905, @labath wrote:

This sounds perfectly reasonable to me. The offsets are present in memory already so there's no point in storing them in a vector as well.

Thanks for taking a look! I'll take this as approval and commit soon.

The patch had a WIP label, so I was only looking/commenting on the high-level idea. But after looking at the implementation more closely, I think that looks good too.

Right right - sorry about that. Realized after I committed it it still had that tag & totally understand it gave the wrong impression. I think when I wrote the commit message I was still thinking about it, but by the time I sent it for review, tested more things, etc, I was more comfortable with it & didn't think to change the message.

[jankratochvil]

llvm/include/llvm/DebugInfo/DWARF/DWARFListTable.h

116

That is going to be addressed in D98289.

[dblaikie]

llvm/include/llvm/DebugInfo/DWARF/DWARFListTable.h

116

Ah, thanks for the catch!

lldb/source/Plugins/SymbolFile/DWARF/DWARFUnit.h

public:
   llvm::Expected<DWARFRangeList> FindRnglistFromIndex(uint32_t index);
 
   /// Return a rangelist's offset based on an index. The index designates
   /// an entry in the rangelist table's offset array and is supplied by
   /// DW_FORM_rnglistx.
   llvm::Optional<uint64_t> GetRnglistOffset(uint32_t Index) const {
     if (!m_rnglist_table)
       return llvm::None;
-    if (llvm::Optional<uint64_t> off = m_rnglist_table->getOffsetEntry(Index))
+    if (llvm::Optional<uint64_t> off = m_rnglist_table->getOffsetEntry(
+            m_dwarf.GetDWARFContext().getOrLoadRngListsData().GetAsLLVM(),
+            Index))
       return *off + m_ranges_base;
     return llvm::None;
   }
 
   llvm::Optional<uint64_t> GetLoclistOffset(uint32_t Index) {
     if (!m_loclist_table_header)
       return llvm::None;
 
-    llvm::Optional<uint64_t> Offset =  m_loclist_table_header->getOffsetEntry(Index);
+    llvm::Optional<uint64_t> Offset = m_loclist_table_header->getOffsetEntry(
+        m_dwarf.GetDWARFContext().getOrLoadLocListsData().GetAsLLVM(), Index);
     if (!Offset)
       return llvm::None;
     return *Offset + m_loclists_base;
   }
 
   /// Return the location table for parsing the given location list data. The
   /// format is chosen according to the unit type. Never returns null.
   std::unique_ptr<llvm::DWARFLocationTable>

lldb/test/Shell/SymbolFile/DWARF/DW_AT_loclists_base.s

 # REQUIRES: x86
 
 # RUN: llvm-mc -triple=x86_64-pc-linux -filetype=obj %s > %t
 # RUN: %lldb %t -o "image lookup -v -s lookup_loclists" -o exit | FileCheck %s
 
 # CHECK-LABEL: image lookup -v -s lookup_loclists
 # CHECK: Variable: {{.*}}, name = "x0", type = "int", location = DW_OP_reg0 RAX,
-# CHECK: Variable: {{.*}}, name = "x1", type = "int", location = ,
+# CHECK-NOT: Variable:
 
 loclists:
         nop
 .Ltmp0:
         nop
 lookup_loclists:
 .Ltmp1:
         nop
 .Ltmp2:
         nop
 .Ltmp3:
         nop
 .Ltmp4:
         nop
 .Lloclists_end:
 
         .section        .debug_loclists,"",@progbits
         .long   .Ldebug_loclist_table_end0-.Ldebug_loclist_table_start0 # Length
 .Ldebug_loclist_table_start0:
         .short  5                       # Version
         .byte   8                       # Address size
         .byte   0                       # Segment selector size
-        .long   1                       # Offset entry count
+        .long   2                       # Offset entry count
 .Lloclists_table_base:
         .long   .Ldebug_loc0-.Lloclists_table_base
         .long   .Ldebug_loc1-.Lloclists_table_base
 .Ldebug_loc0:
         .byte   4                       # DW_LLE_offset_pair
         .uleb128 loclists-loclists
         .uleb128  .Ltmp2-loclists
         .uleb128 1                      # Expression size

llvm/include/llvm/DebugInfo/DWARF/DWARFDebugLoc.h

bool dumpLocationList(uint64_t *Offset, raw_ostream &OS,
                         DWARFUnit *U, DIDumpOptions DumpOpts,
                         unsigned Indent) const;
 
   Error visitAbsoluteLocationList(
       uint64_t Offset, Optional<object::SectionedAddress> BaseAddr,
       std::function<Optional<object::SectionedAddress>(uint32_t)> LookupAddr,
       function_ref<bool(Expected<DWARFLocationExpression>)> Callback) const;
 
+  const DWARFDataExtractor &getData() { return Data; }
+
 protected:
   DWARFDataExtractor Data;
 
   virtual void dumpRawEntry(const DWARFLocationEntry &Entry, raw_ostream &OS,
                             unsigned Indent, DIDumpOptions DumpOpts,
                             const DWARFObject &Obj) const = 0;
 };
 

llvm/include/llvm/DebugInfo/DWARF/DWARFListTable.h

struct Header {
     /// 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;
   };
 
   Header HeaderData;
-  /// The offset table, which contains offsets to the individual list entries.
-  /// It is used by forms such as DW_FORM_rnglistx.
-  /// FIXME: Generate the table and use the appropriate forms.
-  std::vector<uint64_t> Offsets;
   /// The table's format, either DWARF32 or DWARF64.
   dwarf::DwarfFormat Format;
   /// The offset at which the header (and hence the table) is located within
   /// its section.
   uint64_t HeaderOffset;
   /// The name of the section the list is located in.
   StringRef SectionName;
   /// A characterization of the list for dumping purposes, e.g. "range" or
   /// "location".
   StringRef ListTypeString;
 
 public:
   DWARFListTableHeader(StringRef SectionName, StringRef ListTypeString)
       : SectionName(SectionName), ListTypeString(ListTypeString) {}
 
   void clear() {
     HeaderData = {};
-    Offsets.clear();
   }
   uint64_t getHeaderOffset() const { return HeaderOffset; }
   uint8_t getAddrSize() const { return HeaderData.AddrSize; }
   uint64_t getLength() const { return HeaderData.Length; }
   uint16_t getVersion() const { return HeaderData.Version; }
   StringRef getSectionName() const { return SectionName; }
   StringRef getListTypeString() const { return ListTypeString; }
   dwarf::DwarfFormat getFormat() const { return Format; }
 
   /// Return the size of the table header including the length but not including
   /// the offsets.
   static uint8_t getHeaderSize(dwarf::DwarfFormat Format) {
     switch (Format) {
     case dwarf::DwarfFormat::DWARF32:
       return 12;
     case dwarf::DwarfFormat::DWARF64:
       return 20;
     }
     llvm_unreachable("Invalid DWARF format (expected DWARF32 or DWARF64");
   }
 
-  void dump(raw_ostream &OS, DIDumpOptions DumpOpts = {}) const;
-  Optional<uint64_t> getOffsetEntry(uint32_t Index) const {
-    if (Index < Offsets.size())
-      return Offsets[Index];
+  void dump(DataExtractor Data, raw_ostream &OS,
+            DIDumpOptions DumpOpts = {}) const;
+  Optional<uint64_t> getOffsetEntry(DataExtractor Data, uint32_t Index) const {
+    if (Index > HeaderData.OffsetEntryCount)
       return None;
+
+    uint8_t OffsetByteSize = Format == dwarf::DWARF64 ? 8 : 4;
+    uint64_t Offset =
+        getHeaderOffset() + getHeaderSize(Format) + OffsetByteSize * Index;
+    auto R = Data.getUnsigned(&Offset, OffsetByteSize);
+    return R;
   }
 
   /// Extract the table header and the array of offsets.
   Error extract(DWARFDataExtractor Data, uint64_t *OffsetPtr);
 
   /// Returns the length of the 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).
public:
   /// Look up a list based on a given offset. Extract it and enter it into the
   /// list map if necessary.
   Expected<DWARFListType> findList(DWARFDataExtractor Data, uint64_t Offset);
 
   uint64_t getHeaderOffset() const { return Header.getHeaderOffset(); }
   uint8_t getAddrSize() const { return Header.getAddrSize(); }
   dwarf::DwarfFormat getFormat() const { return Header.getFormat(); }
 
-  void dump(raw_ostream &OS,
+  void dump(DWARFDataExtractor Data, raw_ostream &OS,
             llvm::function_ref<Optional<object::SectionedAddress>(uint32_t)>
                 LookupPooledAddress,
             DIDumpOptions DumpOpts = {}) const;
 
   /// Return the contents of the offset entry designated by a given index.
-  Optional<uint64_t> getOffsetEntry(uint32_t Index) const {
-    return Header.getOffsetEntry(Index);
+  Optional<uint64_t> getOffsetEntry(DataExtractor Data, uint32_t Index) const {
+    return Header.getOffsetEntry(Data, Index);
   }
   /// Return the size of the table header including the length but not including
   /// the offsets. This is dependent on the table format, which is unambiguously
   /// derived from parsing the table.
   uint8_t getHeaderSize() const {
     return DWARFListTableHeader::getHeaderSize(getFormat());
   }
 
Error DWARFListType<ListEntryType>::extract(DWARFDataExtractor Data,
   return createStringError(errc::illegal_byte_sequence,
                      "no end of list marker detected at end of %s table "
                      "starting at offset 0x%" PRIx64,
                      SectionName.data(), HeaderOffset);
 }
 
 template <typename DWARFListType>
 void DWARFListTableBase<DWARFListType>::dump(
-    raw_ostream &OS,
+    DWARFDataExtractor Data, raw_ostream &OS,
     llvm::function_ref<Optional<object::SectionedAddress>(uint32_t)>
         LookupPooledAddress,
     DIDumpOptions DumpOpts) const {
-  Header.dump(OS, DumpOpts);
+  Header.dump(Data, OS, DumpOpts);
   OS << HeaderString << "\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 : ListMap)
       for (const auto &Entry : List.second.getEntries())

llvm/include/llvm/DebugInfo/DWARF/DWARFUnit.h

public:
   /// Return a vector of address ranges retrieved from an encoded range
   /// list whose offset is found via a table lookup given an index (DWARF v5
   /// and later).
   Expected<DWARFAddressRangesVector> findRnglistFromIndex(uint32_t Index);
 
   /// Return a rangelist's offset based on an index. The index designates
   /// an entry in the rangelist table's offset array and is supplied by
   /// DW_FORM_rnglistx.
-  Optional<uint64_t> getRnglistOffset(uint32_t Index) {
-    if (!RngListTable)
-      return None;
-    if (Optional<uint64_t> Off = RngListTable->getOffsetEntry(Index))
-      return *Off + RangeSectionBase;
-    return None;
-  }
+  Optional<uint64_t> getRnglistOffset(uint32_t Index);
 
   Optional<uint64_t> getLoclistOffset(uint32_t Index) {
     if (!LoclistTableHeader)
       return None;
-    if (Optional<uint64_t> Off = LoclistTableHeader->getOffsetEntry(Index))
+    if (Optional<uint64_t> Off =
+            LoclistTableHeader->getOffsetEntry(LocTable->getData(), Index))
       return *Off + getLocSectionBase();
     return None;
   }
   Expected<DWARFAddressRangesVector> collectAddressRanges();
 
   Expected<DWARFLocationExpressionsVector>
   findLoclistFromOffset(uint64_t Offset);
 

llvm/lib/DebugInfo/DWARF/DWARFContext.cpp

if (Error Err = Rnglists.extract(rnglistData, &Offset)) {
       DumpOpts.RecoverableErrorHandler(std::move(Err));
       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;
       Offset = TableOffset + Length;
     } else {
-      Rnglists.dump(OS, LookupPooledAddress, DumpOpts);
+      Rnglists.dump(rnglistData, OS, LookupPooledAddress, DumpOpts);
     }
   }
 }
 
 std::unique_ptr<DWARFDebugMacro>
 DWARFContext::parseMacroOrMacinfo(MacroSecType SectionType) {
   auto Macro = std::make_unique<DWARFDebugMacro>();
   auto ParseAndDump = [&](DWARFDataExtractor &Data, bool IsMacro) {
static void dumpLoclistsSection(raw_ostream &OS, DIDumpOptions DumpOpts,
 
   while (Data.isValidOffset(Offset)) {
     DWARFListTableHeader Header(".debug_loclists", "locations");
     if (Error E = Header.extract(Data, &Offset)) {
       DumpOpts.RecoverableErrorHandler(std::move(E));
       return;
     }
 
-    Header.dump(OS, DumpOpts);
+    Header.dump(Data, OS, DumpOpts);
 
     uint64_t EndOffset = Header.length() + Header.getHeaderOffset();
     Data.setAddressSize(Header.getAddrSize());
     DWARFDebugLoclists Loc(Data, Header.getVersion());
     if (DumpOffset) {
       if (DumpOffset >= Offset && DumpOffset < EndOffset) {
         Offset = *DumpOffset;
         Loc.dumpLocationList(&Offset, OS, /*BaseAddr=*/None, MRI, Obj, nullptr,

llvm/lib/DebugInfo/DWARF/DWARFListTable.cpp

return createStringError(errc::not_supported,
                        SectionName.data(), HeaderOffset, HeaderData.SegSize);
   if (End < HeaderOffset + getHeaderSize(Format) +
                 HeaderData.OffsetEntryCount * OffsetByteSize)
     return createStringError(errc::invalid_argument,
         "%s table at offset 0x%" PRIx64 " has more offset entries (%" PRIu32
         ") than there is space for",
         SectionName.data(), HeaderOffset, HeaderData.OffsetEntryCount);
   Data.setAddressSize(HeaderData.AddrSize);
-  for (uint32_t I = 0; I < HeaderData.OffsetEntryCount; ++I)
-    Offsets.push_back(Data.getRelocatedValue(OffsetByteSize, OffsetPtr));
+  *OffsetPtr += HeaderData.OffsetEntryCount * OffsetByteSize;
   return Error::success();
 }
 
-void DWARFListTableHeader::dump(raw_ostream &OS, DIDumpOptions DumpOpts) const {
+void DWARFListTableHeader::dump(DataExtractor Data, raw_ostream &OS,
+                                DIDumpOptions DumpOpts) const {
   if (DumpOpts.Verbose)
     OS << format("0x%8.8" PRIx64 ": ", HeaderOffset);
   int OffsetDumpWidth = 2 * dwarf::getDwarfOffsetByteSize(Format);
   OS << format("%s list header: length = 0x%0*" PRIx64, ListTypeString.data(),
                OffsetDumpWidth, HeaderData.Length)
      << ", format = " << dwarf::FormatString(Format)
      << format(", 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.Version, HeaderData.AddrSize, HeaderData.SegSize,
                HeaderData.OffsetEntryCount);
 
   if (HeaderData.OffsetEntryCount > 0) {
     OS << "offsets: [";
-    for (const auto &Off : Offsets) {
+    for (uint32_t I = 0; I < HeaderData.OffsetEntryCount; ++I) {
+      auto Off = *getOffsetEntry(Data, I);
       OS << format("\n0x%0*" PRIx64, OffsetDumpWidth, Off);
       if (DumpOpts.Verbose)
         OS << format(" => 0x%08" PRIx64,
                      Off + HeaderOffset + getHeaderSize(Format));
     }
     OS << "\n]\n";
   }
 }
 
 uint64_t DWARFListTableHeader::length() const {
   if (HeaderData.Length == 0)
     return 0;
   return HeaderData.Length + dwarf::getUnitLengthFieldByteSize(Format);
 }

llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp

if (getVersion() >= 5) {
     if (LocSection) {
       if (IsDWO)
         LoclistTableHeader.emplace(".debug_loclists.dwo", "locations");
       else
         LoclistTableHeader.emplace(".debug_loclists", "locations");
 
       uint64_t HeaderSize = DWARFListTableHeader::getHeaderSize(Header.getFormat());
       uint64_t Offset = getLocSectionBase();
-      DWARFDataExtractor Data(Context.getDWARFObj(), *LocSection,
-                              isLittleEndian, getAddressByteSize());
+      const DWARFDataExtractor &Data = LocTable->getData();
       if (Offset < HeaderSize)
         return createStringError(errc::invalid_argument,
                                  "did not detect a valid"
                                  " list table with base = 0x%" PRIx64 "\n",
                                  Offset);
       Offset -= HeaderSize;
-      if (auto *IndexEntry = Header.getIndexEntry())
-        if (const auto *Contrib = IndexEntry->getContribution(DW_SECT_LOCLISTS))
-          Offset += Contrib->Offset;
       if (Error E = LoclistTableHeader->extract(Data, &Offset))
         return createStringError(errc::invalid_argument,
                                  "parsing a loclist table: " +
                                      toString(std::move(E)));
     }
   }
 
   // Don't fall back to DW_AT_GNU_ranges_base: it should be ignored for
Desc = StrOffsetsContributionDescriptor(0, StringOffsetSection.Data.size(),
                                             4, Header.getFormat());
   else
     return None;
   auto DescOrError = Desc.validateContributionSize(DA);
   if (!DescOrError)
     return DescOrError.takeError();
   return *DescOrError;
 }
+
+Optional<uint64_t> DWARFUnit::getRnglistOffset(uint32_t Index) {
+  if (!RngListTable)
+    return None;
+  DataExtractor RangesData(RangeSection->Data, isLittleEndian,
+                           getAddressByteSize());
+  if (Optional<uint64_t> Off = RngListTable->getOffsetEntry(RangesData, Index))
+    return *Off + RangeSectionBase;
+  return None;
+}