This is an archive of the discontinued LLVM Phabricator instance.

[AppleAccelTable][NFC] Refactor equal_range code
ClosedPublic

Authored by fdeazeve on Jun 2 2023, 5:13 AM.

Details

Summary

The current implementation of AppleAcceleratorTable::equal_range has a couple of
drawbacks:

  1. Assumptions about how the hash table is structured are hard-coded throughout

the code. Unless you are familiar with the data layout of the table, it becomes
tricky to follow the code.

  1. We currently load strings from the string table even for hashes that don't

match our current search hash. This is wasteful.

  1. There is no error checking in most DataExtractor calls that can fail.

This patch cleans up (1) by making helper methods that hide the details of the
data layout from the algorithms relying on them. This should also help us in
future patches, where we want to expand the interface to allow iterating over
_all_ entries in the table, and potentially clean up the existing Iterator
class.

The changes above also fix (2), as the problem "just vanishes" when you have a
function called "idxOfHashInBucket(SearchHash)".

The changes above also fix (3), as having individual functions allow us to
expose the points in which reading data can fail. This is particularly important
as we would like to share this implementation with LLDB, which requires robust
error handling.

The changes above are also a step towards addressing a comment left by the
original author:

/// TODO: Generalize the rest of the AppleAcceleratorTable interface and move it
/// to this class.

I suspect a lot of these helper functions created also apply to DWARF 5's
accelerator table, so they could be moved to the base class.

The changes above also expose a bug in this implementation: the previous
algorithm looks at _one_ string inside the bucket, but never bothers checking
for collisions. When the main search loop is written as it is with this patch,
the problem becomes evident. We do not fix the issue in this patch, as it is
intended to be NFC.

Diff Detail

Event Timeline

fdeazeve created this revision.Jun 2 2023, 5:13 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 2 2023, 5:13 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
fdeazeve requested review of this revision.Jun 2 2023, 5:13 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 2 2023, 5:13 AM
fdeazeve updated this revision to Diff 527813.Jun 2 2023, 5:17 AM

Reorder functions in cpp file for a friendlier diff

fdeazeve updated this revision to Diff 528410.Jun 5 2023, 6:42 AM

Update some methods

fdeazeve updated this revision to Diff 528421.Jun 5 2023, 7:02 AM

Update base

aprantl added inline comments.Jun 5 2023, 9:29 AM
llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp
343

This isn't really a loop, is it?
Maybe just use an if () statement and convert this to another early exit?

374–379

Feel free to ignore this suggestion, but we could consider returning an error with the offset of the failure here?

aprantl added inline comments.Jun 5 2023, 9:30 AM
llvm/include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h
133

I hope the answer is no, but is there a 64-bit variant of the accelerator tables, too?

fdeazeve added inline comments.Jun 6 2023, 4:01 AM
llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp
343

That's right. It *should* be (if we were actually checking all hash collisions) but once we rewrite the algorithm this way it becomes obvious that there is a bug. I can replace the for with an if for now, but we will re-instate the for once the bug is fixed

374–379

You mean the failure we got from attempting to read the HashIdx-th hash? (i.e. the fact that MaybeHash was nullopt?)

I think if we were to try and expose extraction errors with an Error instead of an optional, this would propagate up to all functions of this file. So it's something we can consider but I'd advise to do it separately, as we already have quite a few cleanups being done in the stack

fdeazeve added inline comments.Jun 6 2023, 4:06 AM
llvm/include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h
133

From what I can tell of the specification, it's always 32

fdeazeve updated this revision to Diff 528784.Jun 6 2023, 4:22 AM

Address review comments

fdeazeve updated this revision to Diff 528829.Jun 6 2023, 6:33 AM

Fix mistake made while addressing review comment (I used the wrong condition
for the early exit suggested)

aprantl accepted this revision.Jun 6 2023, 8:22 AM
This revision is now accepted and ready to land.Jun 6 2023, 8:22 AM
JDevlieghere accepted this revision.Jun 6 2023, 9:15 AM
This revision was automatically updated to reflect the committed changes.