Fix __apple_XXX iterator that iterates over all entries.

[clayborg]

The previous iterator for __apple_XXX sections was assuming that all entries in the table would be contiguous and it wasn't using the offsets table to access each chain of entries for a given name. This patch fixes it so the iterator does the right thing.

This issue became apparent after a modification to strip template names from DW_AT_name entries to allow adding both the template class base name as an entry and also include the name with template names. The commit hash is 2e7ee4d. The problem is if the name starts with a "<" it will try and split the name. So if the name is "<get-size>" it will return an empty string as the function name, and this empty string gets added to the __apple_names table and causes large delays when using the iterators.

[llvmbot]

@llvm/pr-subscribers-debuginfo

Author: Greg Clayton (clayborg)

Changes

The previous iterator for __apple_XXX sections was assuming that all entries in the table would be contiguous and it wasn't using the offsets table to access each chain of entries for a given name. This patch fixes it so the iterator does the right thing.

This issue became apparent after a modification to strip template names from DW_AT_name entries to allow adding both the template class base name as an entry and also include the name with template names. The commit hash is 2e7ee4d. The problem is if the name starts with a "<" it will try and split the name. So if the name is "<get-size>" it will return an empty string as the function name, and this empty string gets added to the __apple_names table and causes large delays when using the iterators.

---

Full diff: https://github.com/llvm/llvm-project/pull/157538.diff

2 Files Affected:

• (modified) llvm/include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h (+25-11)
• (modified) llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp (+16-8)

diff --git a/llvm/include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h b/llvm/include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h
index 87586eda90682..1fda6b8664283 100644
--- a/llvm/include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h
+++ b/llvm/include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h
@@ -50,7 +50,6 @@ class LLVM_ABI DWARFAcceleratorTable {
     Entry &operator=(Entry &&) = default;
     ~Entry() = default;
 
-
   public:
     /// Returns the Offset of the Compilation Unit associated with this
     /// Accelerator Entry or std::nullopt if the Compilation Unit offset is not
@@ -153,7 +152,11 @@ class LLVM_ABI AppleAcceleratorTable : public DWARFAcceleratorTable {
   uint64_t getHashBase() const { return getBucketBase() + getNumBuckets() * 4; }
 
   /// Return the offset into the section where the I-th hash is.
-  uint64_t getIthHashBase(uint32_t I) const { return getHashBase() + I * 4; }
+  std::optional<uint64_t> getIthHashBase(uint32_t I) const {
+    if (I < Hdr.HashCount)
+      return getHashBase() + I * 4;
+    return std::nullopt;
+  }
 
   /// Return the offset into the section where the offset list begins.
   uint64_t getOffsetBase() const { return getHashBase() + getNumHashes() * 4; }
@@ -164,8 +167,10 @@ class LLVM_ABI AppleAcceleratorTable : public DWARFAcceleratorTable {
   }
 
   /// Return the offset into the section where the I-th offset is.
-  uint64_t getIthOffsetBase(uint32_t I) const {
-    return getOffsetBase() + I * 4;
+  std::optional<uint64_t> getIthOffsetBase(uint32_t I) const {
+    if (I < Hdr.HashCount)
+      return getOffsetBase() + I * 4;
+    return std::nullopt;
   }
 
   /// Returns the index of the bucket where a hypothetical Hash would be.
@@ -188,14 +193,22 @@ class LLVM_ABI AppleAcceleratorTable : public DWARFAcceleratorTable {
 
   /// Reads the I-th hash in the hash list.
   std::optional<uint32_t> readIthHash(uint32_t I) const {
-    uint64_t Offset = getIthHashBase(I);
-    return readU32FromAccel(Offset);
+    std::optional<uint64_t> OptOffset = getIthHashBase(I);
+    if (OptOffset) {
+      uint64_t Offset = *OptOffset;
+      return readU32FromAccel(Offset);
+    }
+    return std::nullopt;
   }
 
   /// Reads the I-th offset in the offset list.
   std::optional<uint32_t> readIthOffset(uint32_t I) const {
-    uint64_t Offset = getIthOffsetBase(I);
-    return readU32FromAccel(Offset);
+    std::optional<uint64_t> OptOffset = getIthOffsetBase(I);
+    if (OptOffset) {
+      uint64_t Offset = *OptOffset;
+      return readU32FromAccel(Offset);
+    }
+    return std::nullopt;
   }
 
   /// Reads a string offset from the accelerator table at Offset, which is
@@ -282,6 +295,7 @@ class LLVM_ABI AppleAcceleratorTable : public DWARFAcceleratorTable {
     constexpr static auto EndMarker = std::numeric_limits<uint64_t>::max();
 
     EntryWithName Current;
+    uint32_t OffsetIdx = 0;
     uint64_t Offset = EndMarker;
     uint32_t NumEntriesToCome = 0;
 
@@ -423,7 +437,7 @@ class LLVM_ABI DWARFDebugNames : public DWARFAcceleratorTable {
   struct Abbrev {
     uint64_t AbbrevOffset; /// < Abbreviation offset in the .debug_names section
     uint32_t Code;         ///< Abbreviation code
-    dwarf::Tag Tag; ///< Dwarf Tag of the described entity.
+    dwarf::Tag Tag;        ///< Dwarf Tag of the described entity.
     std::vector<AttributeEncoding> Attributes; ///< List of index attributes.
 
     Abbrev(uint32_t Code, dwarf::Tag Tag, uint64_t AbbrevOffset,
@@ -712,8 +726,8 @@ class LLVM_ABI DWARFDebugNames : public DWARFAcceleratorTable {
     bool IsLocal;
 
     std::optional<Entry> CurrentEntry;
-    uint64_t DataOffset = 0; ///< Offset into the section.
-    std::string Key;         ///< The Key we are searching for.
+    uint64_t DataOffset = 0;      ///< Offset into the section.
+    std::string Key;              ///< The Key we are searching for.
     std::optional<uint32_t> Hash; ///< Hash of Key, if it has been computed.
 
     bool getEntryAtCurrentOffset();
diff --git a/llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp b/llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp
index ea336378bebb3..463455b5d344b 100644
--- a/llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp
+++ b/llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp
@@ -248,8 +248,8 @@ LLVM_DUMP_METHOD void AppleAcceleratorTable::dump(raw_ostream &OS) const {
     }
 
     for (unsigned HashIdx = Index; HashIdx < Hdr.HashCount; ++HashIdx) {
-      uint64_t HashOffset = HashesBase + HashIdx*4;
-      uint64_t OffsetsOffset = OffsetsBase + HashIdx*4;
+      uint64_t HashOffset = HashesBase + HashIdx * 4;
+      uint64_t OffsetsOffset = OffsetsBase + HashIdx * 4;
       uint32_t Hash = AccelSection.getU32(&HashOffset);
 
       if (Hash % Hdr.BucketCount != Bucket)
@@ -321,7 +321,14 @@ void AppleAcceleratorTable::Iterator::prepareNextEntryOrEnd() {
 }
 
 void AppleAcceleratorTable::Iterator::prepareNextStringOrEnd() {
-  std::optional<uint32_t> StrOffset = getTable().readStringOffsetAt(Offset);
+  const AppleAcceleratorTable &Table = getTable();
+  // Always start looking for strings using a valid offset from the Offsets
+  // table. Entries are not always consecutive.
+  std::optional<uint64_t> OptOffset = Table.readIthOffset(OffsetIdx++);
+  if (!OptOffset)
+    return setToEnd();
+  Offset = *OptOffset;
+  std::optional<uint32_t> StrOffset = Table.readStringOffsetAt(Offset);
   if (!StrOffset)
     return setToEnd();
 
@@ -331,7 +338,7 @@ void AppleAcceleratorTable::Iterator::prepareNextStringOrEnd() {
     return prepareNextStringOrEnd();
   Current.StrOffset = *StrOffset;
 
-  std::optional<uint32_t> MaybeNumEntries = getTable().readU32FromAccel(Offset);
+  std::optional<uint32_t> MaybeNumEntries = Table.readU32FromAccel(Offset);
   if (!MaybeNumEntries || *MaybeNumEntries == 0)
     return setToEnd();
   NumEntriesToCome = *MaybeNumEntries;
@@ -339,7 +346,7 @@ void AppleAcceleratorTable::Iterator::prepareNextStringOrEnd() {
 
 AppleAcceleratorTable::Iterator::Iterator(const AppleAcceleratorTable &Table,
                                           bool SetEnd)
-    : Current(Table), Offset(Table.getEntriesBase()), NumEntriesToCome(0) {
+    : Current(Table), Offset(0), NumEntriesToCome(0) {
   if (SetEnd)
     setToEnd();
   else
@@ -443,7 +450,7 @@ void DWARFDebugNames::Header::dump(ScopedPrinter &W) const {
 }
 
 Error DWARFDebugNames::Header::extract(const DWARFDataExtractor &AS,
-                                             uint64_t *Offset) {
+                                       uint64_t *Offset) {
   auto HeaderError = [Offset = *Offset](Error E) {
     return createStringError(errc::illegal_byte_sequence,
                              "parsing .debug_names header at 0x%" PRIx64 ": %s",
@@ -830,8 +837,9 @@ bool DWARFDebugNames::NameIndex::dumpEntry(ScopedPrinter &W,
   uint64_t EntryId = *Offset;
   auto EntryOr = getEntry(Offset);
   if (!EntryOr) {
-    handleAllErrors(EntryOr.takeError(), [](const SentinelError &) {},
-                    [&W](const ErrorInfoBase &EI) { EI.log(W.startLine()); });
+    handleAllErrors(
+        EntryOr.takeError(), [](const SentinelError &) {},
+        [&W](const ErrorInfoBase &EI) { EI.log(W.startLine()); });
     return false;
   }
 

[Michael137]

Seems reasonable to me. I'll defer approval to @JDevlieghere or @felipepiovezan

[Michael137]

Suggested change

	if (OptOffset) {
	uint64_t Offset = *OptOffset;
	return readU32FromAccel(Offset);
	}
	if (OptOffset)
	return readU32FromAccel(*OptOffset);

[Michael137]

Suggested change

	if (OptOffset) {
	uint64_t Offset = *OptOffset;
	return readU32FromAccel(Offset);
	}
	if (OptOffset)
	return readU32FromAccel(*OptOffset);

[Michael137]

Is this comment about Offset pointing to a valid string reference still accurate after this patch?

    /// Reads the next string pointer and the entry count for that string,
    /// populating `NumEntriesToCome`.
    /// If not possible (e.g. end of the section), becomes the end iterator.
    /// Assumes `Offset` points to a string reference.
    void prepareNextStringOrEnd();