[AppleAccelTable][NFC] Refactor iterator class

[fdeazeve]

Summary

The current implementation of the AppleAcceleratorTable::Entry is problematic
for a few reasons:

1. It is heavyweight. Iterators should be cheap, but the current implementation

tracks 3 different integer values, one "Entry" object, and one pointer to the
actual accelerator table. Most of this information is redundant and can be
removed.

2. It performs "memory reads" outside of the dereference operation. This

violates the usual expectations of iterators, whereby we don't access anything
so long as we don't dereference the iterator.

3. It doesn't commit to tracking _one_ thing only. It tries to track both an

"index" into a list of HashData entries and a pointer in a blob of data. For
this reason, it allows for multiple "invalid" states, keeps redundant
information around and is difficult to understand.

4. It couples the interpretation of the data with the iterator increment. As

such, if the *interpretation* fails, the iterator will keep on producing garbage
values without ever indicating so to consumers.

The problem this iterator is trying to solve is simple: we have a blob of data
containing many "HashData" entries and we want to iterate over them. As such,
this commit makes the iterator only track a pointer over that data, and it
decouples the iterator increments from the interpretation of this blob of data.

We maintain the already existing assumption that failures never happen, but now
make it explicit with an assert.

Depends on D152158

[fdeazeve]

Update base

[fdeazeve]

Add NFC tag.

[aprantl]

llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp

283

What does it mean for ExtractWorked to be false?
If this can be triggered by malformed input, even an asserts-enabled parser needs to handle it gracefully. Asserts should only be used for internal consistency checks that may never fail.

[fdeazeve]

llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp

283

If this can be triggered by malformed input, even an asserts-enabled parser needs to handle it gracefully.

That's what I mean in the commit message with:

We maintain the already existing assumption that failures never happen, but now
make it explicit with an assert.

Today, if we fail to extract, we're going to start producing completely incorrect data and be silent about it. Imagine one of the iteration fails: the offset doesn't get updated and the next iteration is going to re-use the offset of the previous iteration.

IMO we're not handling it gracefully today, that's why I added the assert. But I don't feel strongly about this (just a bit :) )

I think the only way to fix this correctly is to remove the iterator abstraction and use callbacks instead. Non-end iterators should never fail the dereference operator, but data extracts are inherently a "fail-able" abstraction.

[dblaikie]

llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp

283

I believe @lhames and I spoke about fallible iterators previously & he's used some iterator abstractions with fallibility (which can be nicer than a callback - for instance, allowing early exit or other novel iteration sequences that a callback API might not provide in a general way) - by having the iterator terminate early (when it hits an error, it becomes == end) and having a member you have to inspect after the fact to query for the error state/if it's failed.

[fdeazeve]

llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp

283

and having a member you have to inspect after the fact to query for the error state/if it's failed.

That's an interesting idea, but how would that work with range-based for loops, as they don't expose the iterator itself to the programmer?

Are you aware of examples of such iterators inside LLVM?

having the iterator terminate early

Note how this also forces the iterator to know how to set itself to the end iterator, which is ok but requires more bookkeeping.

One other possibility we could try is to have the iterator's operator * return an optional. However, the current implementation of these iterators (both before and after this patch) avoid memory operations by keeping an Entry inside the iterator; the optional would inevitably have copy that. Unless we use pointers as optionals? (i.e. operator* returns an Entry*)

While what I'm saying applies only for apple_names, the standardized debug_names implementation seems to follow a similar pattern, though the code there is even more complex and I haven't yet been able to digest it.

Another thing we could do is to eagerly read all the data (except maybe for the strings) from the section and build a proper data structure with the FormValues and hashes and offsets already parsed. So we never have a chance to error again after the constructor is finished. That said, I suspect the original implementors didn't do this for performance / memory reasons? It's interesting to consider how some queries from LLDB force us to search/materialize all of the table anyway. For example, by search by regex (gotta read all the strings) or by DIE whose offset is inside a given range (gotta read all the HashData to find the DIE offset)

[dblaikie]

llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp

283

Oh, actually - maybe we settled on a different idiom - an out parameter from the range accessor, that's compatible with range-for loops, it's even documented: https://llvm.org/docs/ProgrammersManual.html#building-fallible-iterators-and-iterator-ranges

& yeah, certainly one of Lang's goals with libObject was to make it as lazy as possible so as not to do any extra work/hurt performance but also to be as usable as possible on potentially invalid object files - be able to parse all the parts that can be parsed, without tripping over on the first failure and being unable to continue.

The LLVM libDebugInfoDWARF code would probably benefit from similar goals - same idea that it might be used to investigate invalid inputs, and being able to keep going as much as possible/not trip over unrelated errors would be a valuable feature.

[fdeazeve]

Rebased

[fdeazeve]

llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp

283

Oh very interesting, I think we can make this work on top of the cleanups of this patch, so I will give it a try as a follow-up patch. Thank you for the references!

one of Lang's goals with libObject was to make it as lazy as possible so as not to do any extra work/hurt performance

Maybe I'm being naive here, but it's not clear to me whether being lazy (for the bucket/hash/offset/string relocation resolving) is the right call, since we don't cache anything for future use. Granted, if we do <= 1 queries that visit the entire table, then it is a win. But the moment we do the second query, it would have been faster to rely on a pre-processed data structure, as these data extractors are heavy-weight.

[aprantl]

llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp

283

With LLDB as the consumer in mind there are two scenarios we want to optimize for:

1. debugging with a Mach-O debug map: Traversing through thousands of .o files when looking up a DIE by name, most of the time getting a "no" result

2. lookups in a single, very large accelerator table (.dSYMs, ELF binaries, ...)

[dblaikie]

llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp

283

Sorry I'm not following this in detail, so feel free to ignore this if it's not worth the hassle to explain.

You mention these are heavyweight structures - that makes me concerned - in theory the accelerator tables were/are meant to be cheap to use from-disk. So I would expect we shouldn't have to/shouldn't be building heavyweight data structures to use these?

[fdeazeve]

llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp

283

Full disclosure, I have not looked at what an optimized code for the final "equal_ranges" function looks like, but my claim boils down to the following:

To perform the most basic lookup ("is this string in the table"), we have to call DataExtractor::getU32 at least 4 times (more if the hash we're looking for is not the first hash in the bucket). That function boils down to a call to DataExtractor::getU: https://llvm.org/doxygen/DataExtractor_8cpp_source.html#l00040
That code is not exactly simple.

If we were working with a pre-processed data structure for the hashes/buckets, this would be simple 4 integer accesses in memory (after we paid all the cost in advance once). All the design decisions from the accelerator tables indicate that the intent was that queries should always be these simple memory accesses, but there is an inherent cost in having to convert from the "object file" representation (i.e. all the boilerplate in getU)

(Just to make sure we're on the same page, these patches are not changing anything about that in either direction)

[aprantl]

llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp

283

I'm not actually sure if I've ever seen the accelerator table parsing show up as being a major time sink in a trace of LLDB before.

[fdeazeve]

Removed assert that I added to make this patch _really_ NFC.
Will add error handling in a future patch using David's suggestion.

llvm/include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h

class AppleAcceleratorTable : public DWARFAcceleratorTable {
   /// Scans through all Hashes in the BucketIdx-th bucket, attempting to find
   /// HashToFind. If it is found, its index in the list of hashes is returned.
   std::optional<uint32_t> idxOfHashInBucket(uint32_t HashToFind,
                                             uint32_t BucketIdx) const;
 
 public:
   /// Apple-specific implementation of an Accelerator Entry.
   class Entry final : public DWARFAcceleratorTable::Entry {
-    const HeaderData *HdrData = nullptr;
+    const AppleAcceleratorTable &Table;
 
-    Entry(const HeaderData &Data);
-    Entry() = default;
-
-    void extract(const AppleAcceleratorTable &AccelTable, uint64_t *Offset);
+    Entry(const AppleAcceleratorTable &Table);
+    void extract(uint64_t *Offset);
 
   public:
     std::optional<uint64_t> getCUOffset() const override;
 
     /// Returns the Section Offset of the Debug Info Entry associated with this
     /// Accelerator Entry or std::nullopt if the DIE offset is not recorded in
     /// this Accelerator Entry. The returned offset is relative to the start of
     /// the Section containing the DIE.
     std::optional<uint64_t> getDIESectionOffset() const;
 
     std::optional<dwarf::Tag> getTag() const override;
 
     /// Returns the value of the Atom in this Accelerator Entry, if the Entry
     /// contains such Atom.
     std::optional<DWARFFormValue> lookup(HeaderData::AtomType Atom) const;
 
     friend class AppleAcceleratorTable;
     friend class ValueIterator;
   };
 
+  /// An iterator for Entries all having the same string as key.
   class ValueIterator {
-    const AppleAcceleratorTable *AccelTable = nullptr;
-    Entry Current;           ///< The current entry.
-    uint64_t DataOffset = 0; ///< Offset into the section.
-    unsigned Data = 0; ///< Current data entry.
-    unsigned NumData = 0; ///< Number of data entries.
+    Entry Current;
+    uint64_t Offset = 0;
 
-    /// Advance the iterator.
-    void Next();
+    void Next() { Offset += Current.Table.getHashDataEntryLength(); }
 
   public:
     using iterator_category = std::input_iterator_tag;
     using value_type = Entry;
     using difference_type = std::ptrdiff_t;
     using pointer = value_type *;
     using reference = value_type &;
 
     /// Construct a new iterator for the entries at \p DataOffset.
     ValueIterator(const AppleAcceleratorTable &AccelTable, uint64_t DataOffset);
-    /// End marker.
-    ValueIterator() = default;
 
-    const Entry &operator*() const { return Current; }
+    const Entry &operator*() {
+      uint64_t OffsetCopy = Offset;
+      Current.extract(&OffsetCopy);
+      return Current;
+    }
     ValueIterator &operator++() { Next(); return *this; }
     ValueIterator operator++(int) {
       ValueIterator I = *this;
       Next();
       return I;
     }
     friend bool operator==(const ValueIterator &A, const ValueIterator &B) {
-      return A.NumData == B.NumData && A.DataOffset == B.DataOffset;
+      return A.Offset == B.Offset;
     }
     friend bool operator!=(const ValueIterator &A, const ValueIterator &B) {
       return !(A == B);
     }
   };
 
   AppleAcceleratorTable(const DWARFDataExtractor &AccelSection,
                         DataExtractor StringSection)

llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp

for (unsigned HashIdx = Index; HashIdx < Hdr.HashCount; ++HashIdx) {
         continue;
       }
       while (dumpName(W, AtomForms, &DataOffset))
         /*empty*/;
     }
   }
 }
 
-AppleAcceleratorTable::Entry::Entry(
-    const AppleAcceleratorTable::HeaderData &HdrData)
-    : HdrData(&HdrData) {
-  Values.reserve(HdrData.Atoms.size());
-  for (const auto &Atom : HdrData.Atoms)
+AppleAcceleratorTable::Entry::Entry(const AppleAcceleratorTable &Table)
+    : Table(Table) {
+  Values.reserve(Table.HdrData.Atoms.size());
+  for (const auto &Atom : Table.HdrData.Atoms)
     Values.push_back(DWARFFormValue(Atom.second));
 }
 
-void AppleAcceleratorTable::Entry::extract(
-    const AppleAcceleratorTable &AccelTable, uint64_t *Offset) {
+void AppleAcceleratorTable::Entry::extract(uint64_t *Offset) {
   for (auto &FormValue : Values)
-    FormValue.extractValue(AccelTable.AccelSection, Offset,
-                           AccelTable.FormParams);
+    FormValue.extractValue(Table.AccelSection, Offset, Table.FormParams);
 }
 
 std::optional<DWARFFormValue>
 AppleAcceleratorTable::Entry::lookup(HeaderData::AtomType AtomToFind) const {
-  assert(HdrData && "Dereferencing end iterator?");
-  assert(HdrData->Atoms.size() == Values.size());
-  for (auto [Atom, FormValue] : zip_equal(HdrData->Atoms, Values))
+  for (auto [Atom, FormValue] : zip_equal(Table.HdrData.Atoms, Values))
     if (Atom.first == AtomToFind)
       return FormValue;
   return std::nullopt;
 }
 
 std::optional<uint64_t>
 AppleAcceleratorTable::Entry::getDIESectionOffset() const {
-  return HdrData->extractOffset(lookup(dwarf::DW_ATOM_die_offset));
+  return Table.HdrData.extractOffset(lookup(dwarf::DW_ATOM_die_offset));
 }
 
 std::optional<uint64_t> AppleAcceleratorTable::Entry::getCUOffset() const {
-  return HdrData->extractOffset(lookup(dwarf::DW_ATOM_cu_offset));
+  return Table.HdrData.extractOffset(lookup(dwarf::DW_ATOM_cu_offset));
 }
 
 std::optional<dwarf::Tag> AppleAcceleratorTable::Entry::getTag() const {
   std::optional<DWARFFormValue> Tag = lookup(dwarf::DW_ATOM_die_tag);
   if (!Tag)
     return std::nullopt;
   if (std::optional<uint64_t> Value = Tag->getAsUnsignedConstant())
     return dwarf::Tag(*Value);
   return std::nullopt;
 }
 
 AppleAcceleratorTable::ValueIterator::ValueIterator(
-    const AppleAcceleratorTable &AccelTable, uint64_t Offset)
-    : AccelTable(&AccelTable), Current(AccelTable.HdrData), DataOffset(Offset) {
-  if (!AccelTable.AccelSection.isValidOffsetForDataOfSize(DataOffset, 4))
-    return;
-
-  // Read the first entry.
-  NumData = AccelTable.AccelSection.getU32(&DataOffset);
-  Next();
-}
-
-void AppleAcceleratorTable::ValueIterator::Next() {
-  assert(NumData > 0 && "attempted to increment iterator past the end");
-  auto &AccelSection = AccelTable->AccelSection;
-  if (Data >= NumData ||
-      !AccelSection.isValidOffsetForDataOfSize(DataOffset, 4)) {
-    NumData = 0;
-    DataOffset = 0;
-    return;
-  }
-  Current.extract(*AccelTable, &DataOffset);
-  ++Data;
+    const AppleAcceleratorTable &AccelTable, uint64_t DataOffset)
+    : Current(AccelTable), Offset(DataOffset) {
 }
 
 iterator_range<AppleAcceleratorTable::ValueIterator>
 AppleAcceleratorTable::equal_range(StringRef Key) const {
-  const auto EmptyRange = make_range(ValueIterator(), ValueIterator());
+  const auto EmptyRange =
+      make_range(ValueIterator(*this, 0), ValueIterator(*this, 0));
   if (!IsValid)
     return EmptyRange;
 
   // Find the bucket.
   uint32_t SearchHash = djbHash(Key);
   uint32_t BucketIdx = hashToBucketIdx(SearchHash);
   std::optional<uint32_t> HashIdx = idxOfHashInBucket(SearchHash, BucketIdx);
   if (!HashIdx)
AppleAcceleratorTable::equal_range(StringRef Key) const {
 
   std::optional<uint32_t> StrOffset = readStringOffsetAt(DataOffset);
 
   // Invalid input or no more strings in this hash.
   if (!StrOffset || *StrOffset == 0)
     return EmptyRange;
 
   std::optional<StringRef> MaybeStr = readStringFromStrSection(*StrOffset);
-  if (!MaybeStr)
+  std::optional<uint32_t> NumEntries = this->readU32FromAccel(DataOffset);
+  if (!MaybeStr || !NumEntries)
     return EmptyRange;
-  if (Key == *MaybeStr)
-    return make_range({*this, DataOffset}, ValueIterator());
+  if (Key == *MaybeStr) {
+    uint64_t EndOffset = DataOffset + *NumEntries * getHashDataEntryLength();
+    return make_range({*this, DataOffset}, ValueIterator{*this, EndOffset});
+  }
 
   // FIXME: this shouldn't return, we haven't checked all the colliding strings
   // in the bucket!
   return EmptyRange;
 }
 
 std::optional<uint32_t>
 AppleAcceleratorTable::idxOfHashInBucket(uint32_t HashToFind,