[AppleAccelTable] Keep track of the size of each hash data entry

[fdeazeve]

Summary

In a future patch, it will be desirable to skip over all hash data entries for a
particular string. In order to do so, we must know how many bytes each of those
entries have.

In its full specification, Apple tables allow for variable length entries, which
would make the above impossible without reading the data of each entry. However,
this is largely unsupported today (as a FIXME in the code indicates, there is a
bug with hash collisions exactly because we don't know how to skip over data),
and the documentation[1] states that:

For the current implementations of the “.apple_names” (all functions +
globals), the “.apple_types” (names of all types that are defined), and the
“.apple_namespaces” (all namespaces), we currently set the Atom array to be:
[...]
This defines the contents to be the DIE offset (eAtomTypeDIEOffset) that is
encoded as a 32 bit value (DW_FORM_data4).

In other words, we only produce fixed sized entries.

A few tests containing invalid dwarf had to be updated, as the error is now
detected earlier (when the accelerator table is being parsed, instead of inside
the explicit call to "verify").

[1]: https://llvm.org/docs/SourceLevelDebugging.html#fixed-lookup

Depends on D152156

[fdeazeve]

Update base

[aprantl]

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

109

should this be default-initialized?

[dblaikie]

Is this parsing code used for the standardized .debug_names too, and do we (LLVM itself, and maybe GCC too) generally produce fixed size records there? (not that I'm suggesting you should be the one to add support for variable sized records, but just to know if we should add a FIXME or other note about potential incompatibility/necessary improvement)

[fdeazeve]

In D152157#4396561, @dblaikie wrote:

Is this parsing code used for the standardized .debug_names too

, and do we (LLVM itself, and maybe GCC too) generally produce fixed size records there?

Nope, this code is for apple tables only; the two kinds of tables only share a pure virtual class, but not any real implementation.

I want to look into how the debug_names work as well, but for now my goal is to bring LLVM to feature parity with the duplicate code found inside LLDB for apple tables, so that we can delete the (IMO) not as-good-looking code in LLDB :)

[fdeazeve]

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

109

I believe the design of this class is that it should not be used until IsValid is set to true, and IsValid is only set to true after all of its members are initialized.

We could clean this up by moving away from the declare(ctor)-then-initialize (extract) anti-pattern, instead making sure the constructor does all the way

[fdeazeve]

Rebased

[JDevlieghere]

LGTM

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

109

+1: moving away from that would be great.

[fdeazeve]

Rebased

[fdeazeve]

Fix clang format issue

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

struct HeaderData {
 
     std::optional<uint64_t>
     extractOffset(std::optional<DWARFFormValue> Value) const;
   };
 
   Header Hdr;
   HeaderData HdrData;
   dwarf::FormParams FormParams;
+  uint32_t HashDataEntryLength;
   bool IsValid = false;
 
   /// Returns true if we should continue scanning for entries or false if we've
   /// reached the last (sentinel) entry of encountered a parsing error.
   bool dumpName(ScopedPrinter &W, SmallVectorImpl<DWARFFormValue> &AtomForms,
                 uint64_t *DataOffset) const;
 
   /// Reads an uint32_t from the accelerator table at Offset, which is
AppleAcceleratorTable(const DWARFDataExtractor &AccelSection,
       : DWARFAcceleratorTable(AccelSection, StringSection) {}
 
   Error extract() override;
   uint32_t getNumBuckets() const;
   uint32_t getNumHashes() const;
   uint32_t getSizeHdr() const;
   uint32_t getHeaderDataLength() const;
 
+  /// Returns the size of one HashData entry.
+  uint32_t getHashDataEntryLength() const { return HashDataEntryLength; }
+
   /// Return the Atom description, which can be used to interpret the raw values
   /// of the Accelerator Entries in this table.
   ArrayRef<std::pair<HeaderData::AtomType, HeaderData::Form>> getAtomsDesc();
   bool validateForms();
 
   /// Return information related to the DWARF DIE we're looking for when
   /// performing a lookup by name.
   ///

llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp

Error AppleAcceleratorTable::extract() {
   if (!AccelSection.isValidOffset(getIthBucketBase(Hdr.BucketCount - 1)))
     return createStringError(
         errc::illegal_byte_sequence,
         "Section too small: cannot read buckets and hashes.");
 
   HdrData.DIEOffsetBase = AccelSection.getU32(&Offset);
   uint32_t NumAtoms = AccelSection.getU32(&Offset);
 
+  HashDataEntryLength = 0;
+  auto MakeUnsupportedFormError = [](dwarf::Form Form) {
+    return createStringError(errc::not_supported,
+                             "Unsupported form:" +
+                                 dwarf::FormEncodingString(Form));
+  };
+
   for (unsigned i = 0; i < NumAtoms; ++i) {
     uint16_t AtomType = AccelSection.getU16(&Offset);
     auto AtomForm = static_cast<dwarf::Form>(AccelSection.getU16(&Offset));
     HdrData.Atoms.push_back(std::make_pair(AtomType, AtomForm));
+
+    std::optional<uint8_t> FormSize =
+        dwarf::getFixedFormByteSize(AtomForm, FormParams);
+    if (!FormSize)
+      return MakeUnsupportedFormError(AtomForm);
+    HashDataEntryLength += *FormSize;
   }
 
   IsValid = true;
   return Error::success();
 }
 
 uint32_t AppleAcceleratorTable::getNumBuckets() const {
   return Hdr.BucketCount;
if (!IsValid)
     return;
 
   ScopedPrinter W(OS);
 
   Hdr.dump(W);
 
   W.printNumber("DIE offset base", HdrData.DIEOffsetBase);
   W.printNumber("Number of atoms", uint64_t(HdrData.Atoms.size()));
+  W.printNumber("Size of each hash data entry", getHashDataEntryLength());
   SmallVector<DWARFFormValue, 3> AtomForms;
   {
     ListScope AtomsScope(W, "Atoms");
     unsigned i = 0;
     for (const auto &Atom : HdrData.Atoms) {
       DictScope AtomScope(W, ("Atom " + Twine(i++)).str());
       W.startLine() << "Type: " << formatAtom(Atom.first) << '\n';
       W.startLine() << "Form: " << formatv("{0}", Atom.second) << '\n';

llvm/test/tools/dsymutil/X86/basic-lto-dw4-linking-x86.test

 CHECK-NEXT:   Version: 0x1
 CHECK-NEXT:   Hash function: 0x0
 CHECK-NEXT:   Bucket count: 7
 CHECK-NEXT:   Hashes count: 7
 CHECK-NEXT:   HeaderData length: 12
 CHECK-NEXT: }
 CHECK-NEXT: DIE offset base: 0
 CHECK-NEXT: Number of atoms: 1
+CHECK-NEXT: Size of each hash data entry: 4
 CHECK-NEXT: Atoms [
 CHECK-NEXT:   Atom 0 {
 CHECK-NEXT:     Type: DW_ATOM_die_offset
 CHECK-NEXT:     Form: DW_FORM_data4
 CHECK-NEXT:   }
 CHECK-NEXT: ]
 CHECK-NEXT: Bucket 0 [
 CHECK-NEXT:   Hash 0xb8860c2 [

 CHECK-NEXT:   Version: 0x1
 CHECK-NEXT:   Hash function: 0x0
 CHECK-NEXT:   Bucket count: 2
 CHECK-NEXT:   Hashes count: 2
 CHECK-NEXT:   HeaderData length: 24
 CHECK-NEXT: }
 CHECK-NEXT: DIE offset base: 0
 CHECK-NEXT: Number of atoms: 4
+CHECK-NEXT: Size of each hash data entry: 11
 CHECK-NEXT: Atoms [
 CHECK-NEXT:   Atom 0 {
 CHECK-NEXT:     Type: DW_ATOM_die_offset
 CHECK-NEXT:     Form: DW_FORM_data4
 CHECK-NEXT:   }
 CHECK-NEXT:   Atom 1 {
 CHECK-NEXT:     Type: DW_ATOM_die_tag
 CHECK-NEXT:     Form: DW_FORM_data2

 CHECK-NEXT:   Version: 0x1
 CHECK-NEXT:   Hash function: 0x0
 CHECK-NEXT:   Bucket count: 1
 CHECK-NEXT:   Hashes count: 0
 CHECK-NEXT:   HeaderData length: 12
 CHECK-NEXT: }
 CHECK-NEXT: DIE offset base: 0
 CHECK-NEXT: Number of atoms: 1
+CHECK-NEXT: Size of each hash data entry: 4
 CHECK-NEXT: Atoms [
 CHECK-NEXT:   Atom 0 {
 CHECK-NEXT:     Type: DW_ATOM_die_offset
 CHECK-NEXT:     Form: DW_FORM_data4
 CHECK-NEXT:   }
 CHECK-NEXT: ]
 CHECK-NEXT: Bucket 0 [
 CHECK-NEXT:   EMPTY
 CHECK-NEXT: ]
 
 CHECK: .apple_objc contents:
 CHECK-NEXT: Header {
 CHECK-NEXT:   Magic: 0x48415348
 CHECK-NEXT:   Version: 0x1
 CHECK-NEXT:   Hash function: 0x0
 CHECK-NEXT:   Bucket count: 1
 CHECK-NEXT:   Hashes count: 0
 CHECK-NEXT:   HeaderData length: 12
 CHECK-NEXT: }
 CHECK-NEXT: DIE offset base: 0
 CHECK-NEXT: Number of atoms: 1
+CHECK-NEXT: Size of each hash data entry: 4
 CHECK-NEXT: Atoms [
 CHECK-NEXT:   Atom 0 {
 CHECK-NEXT:     Type: DW_ATOM_die_offset
 CHECK-NEXT:     Form: DW_FORM_data4
 CHECK-NEXT:   }
 CHECK-NEXT: ]
 CHECK-NEXT: Bucket 0 [
 CHECK-NEXT:   EMPTY
 CHECK-NEXT: ]

llvm/test/tools/dsymutil/X86/basic-lto-linking-x86.test

 CHECK-NEXT:   Version: 0x1
 CHECK-NEXT:   Hash function: 0x0
 CHECK-NEXT:   Bucket count: 7
 CHECK-NEXT:   Hashes count: 7
 CHECK-NEXT:   HeaderData length: 12
 CHECK-NEXT: }
 CHECK-NEXT: DIE offset base: 0
 CHECK-NEXT: Number of atoms: 1
+CHECK-NEXT: Size of each hash data entry: 4
 CHECK-NEXT: Atoms [
 CHECK-NEXT:   Atom 0 {
 CHECK-NEXT:     Type: DW_ATOM_die_offset
 CHECK-NEXT:     Form: DW_FORM_data4
 CHECK-NEXT:   }
 CHECK-NEXT: ]
 CHECK-NEXT: Bucket 0 [
 CHECK-NEXT:   Hash 0xb8860c2 [

 CHECK-NEXT:   Version: 0x1
 CHECK-NEXT:   Hash function: 0x0
 CHECK-NEXT:   Bucket count: 2
 CHECK-NEXT:   Hashes count: 2
 CHECK-NEXT:   HeaderData length: 24
 CHECK-NEXT: }
 CHECK-NEXT: DIE offset base: 0
 CHECK-NEXT: Number of atoms: 4
+CHECK-NEXT: Size of each hash data entry: 11
 CHECK-NEXT: Atoms [
 CHECK-NEXT:   Atom 0 {
 CHECK-NEXT:     Type: DW_ATOM_die_offset
 CHECK-NEXT:     Form: DW_FORM_data4
 CHECK-NEXT:   }
 CHECK-NEXT:   Atom 1 {
 CHECK-NEXT:     Type: DW_ATOM_die_tag
 CHECK-NEXT:     Form: DW_FORM_data2

 CHECK-NEXT:   Version: 0x1
 CHECK-NEXT:   Hash function: 0x0
 CHECK-NEXT:   Bucket count: 1
 CHECK-NEXT:   Hashes count: 0
 CHECK-NEXT:   HeaderData length: 12
 CHECK-NEXT: }
 CHECK-NEXT: DIE offset base: 0
 CHECK-NEXT: Number of atoms: 1
+CHECK-NEXT: Size of each hash data entry: 4
 CHECK-NEXT: Atoms [
 CHECK-NEXT:   Atom 0 {
 CHECK-NEXT:     Type: DW_ATOM_die_offset
 CHECK-NEXT:     Form: DW_FORM_data4
 CHECK-NEXT:   }
 CHECK-NEXT: ]
 CHECK-NEXT: Bucket 0 [
 CHECK-NEXT:   EMPTY
 CHECK-NEXT: ]
 
 CHECK: .apple_objc contents:
 CHECK-NEXT: Header {
 CHECK-NEXT:   Magic: 0x48415348
 CHECK-NEXT:   Version: 0x1
 CHECK-NEXT:   Hash function: 0x0
 CHECK-NEXT:   Bucket count: 1
 CHECK-NEXT:   Hashes count: 0
 CHECK-NEXT:   HeaderData length: 12
 CHECK-NEXT: }
 CHECK-NEXT: DIE offset base: 0
 CHECK-NEXT: Number of atoms: 1
+CHECK-NEXT: Size of each hash data entry: 4
 CHECK-NEXT: Atoms [
 CHECK-NEXT:   Atom 0 {
 CHECK-NEXT:     Type: DW_ATOM_die_offset
 CHECK-NEXT:     Form: DW_FORM_data4
 CHECK-NEXT:   }
 CHECK-NEXT: ]
 CHECK-NEXT: Bucket 0 [
 CHECK-NEXT:   EMPTY
 CHECK-NEXT: ]

llvm/test/tools/dsymutil/X86/objc.test

 CHECK-NEXT:   Version: 0x1
 CHECK-NEXT:   Hash function: 0x0
 CHECK-NEXT:   Bucket count: 2
 CHECK-NEXT:   Hashes count: 2
 CHECK-NEXT:   HeaderData length: 12
 CHECK-NEXT: }
 CHECK-NEXT: DIE offset base: 0
 CHECK-NEXT: Number of atoms: 1
+CHECK-NEXT: Size of each hash data entry: 4
 CHECK-NEXT: Atoms [
 CHECK-NEXT:   Atom 0 {
 CHECK-NEXT:     Type: DW_ATOM_die_offset
 CHECK-NEXT:     Form: DW_FORM_data4
 CHECK-NEXT:   }
 CHECK-NEXT: ]
 CHECK-NEXT: Bucket 0 [
 CHECK-NEXT:   Hash 0x2b5e6 [

llvm/test/tools/llvm-dwarfdump/X86/apple_names_verify_form.s

 # RUN: llvm-mc %s -filetype obj -triple x86_64-apple-darwin -o - \
 # RUN: | not llvm-dwarfdump -verify - \
 # RUN: | FileCheck %s
 
 # CHECK: Verifying .apple_names...
-# CHECK-NEXT: error: Unsupported form: failed to read HashData.
+# CHECK-NEXT: error: Unsupported form:
 
 # This test is meant to verify that the -verify option
 # in llvm-dwarfdump, correctly identifies that Atom[0].form is unsupported.
 # As a result, the hashdata cannot be read.
 
   .section  __TEXT,__text,regular,pure_instructions
   .file 1 "basic.c"
   .comm _i,4,2                  ## @i
Lnames_begin:
   .short  1                       ## Header Version
   .short  0                       ## Header Hash Function
   .long 2                       ## Header Bucket Count
   .long 2                       ## Header Hash Count
   .long 12                      ## Header Data Length
   .long 0                       ## HeaderData Die Offset Base
   .long 1                       ## HeaderData Atom Count
   .short  1                       ## DW_ATOM_die_offset
-  .short  400                     ## DW_FORM_data4 -- error: unsupported form; failed to read HashData.
+  .short  400                     ## not a valid form -- error: unsupported form; failed to read HashData.
   .long 0                       ## Bucket 0
   .long 1                       ## Bucket 1
   .long 177678                  ## Hash in Bucket 0
   .long 177679                  ## Hash in Bucket 1
   .long LNames0-Lnames_begin    ## Offset in Bucket 0
   .long LNames1-Lnames_begin    ## Offset in Bucket 1
 LNames0:
   .long 84                      ## i