[DWARF] Partial verification for .apple_names accelerator table in llvm-dwarfdump output.

[sgravani]

Summary

This patch adds code which verifies that each bucket in the .apple_names
accelerator table is either empty or has a valid hash index.

[probinson]

Please subscribe 'llvm-commits' when you create a review, so the whole community can see the proposed patch.
(If you add llvm-commits later, we recommend that you paste the original description into a comment, because otherwise the mailing list never sees the original description.)

I understand that DWARFAcceleratorTable already exists and you are building on that, but I have to wonder how much (if any) of this can be leveraged for the actual DWARF v5 standard's .debug_names section. (I haven't looked at any of this stuff yet; the accelerator table is pretty far down my list of v5 features to look at.) If the answer is "not much" then maybe it ought to be renamed DWARFAppleNamesTable instead.

[aprantl]

In D34177#779664, @probinson wrote:

Please subscribe 'llvm-commits' when you create a review, so the whole community can see the proposed patch.
(If you add llvm-commits later, we recommend that you paste the original description into a comment, because otherwise the mailing list never sees the original description.)

I understand that DWARFAcceleratorTable already exists and you are building on that, but I have to wonder how much (if any) of this can be leveraged for the actual DWARF v5 standard's .debug_names section. (I haven't looked at any of this stuff yet; the accelerator table is pretty far down my list of v5 features to look at.) If the answer is "not much" then maybe it ought to be renamed DWARFAppleNamesTable instead.

The DWARF v5 accelerator table is a direct evolution of the Apple accelerator table, so it is quite possible that we can share some of the implementation. Form a cursory glance it looks like at least the accessors for the hash table (bucket count, ...) are similar enough that they can share a common interface. We probably can't make that call until someone actually sits down and comes up with a design for how to implement the DWARF 5 accelerator tables, though. How about we revisit this question then? Hopefully this won't be too far out into the future.

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

6 ↗

(On Diff #102436)

Could you check for the actual error message and move the # CHECK: line right next to the injected error?

[probinson]

In D34177#779712, @aprantl wrote:

In D34177#779664, @probinson wrote:

I understand that DWARFAcceleratorTable already exists and you are building on that, but I have to wonder how much (if any) of this can be leveraged for the actual DWARF v5 standard's .debug_names section. (I haven't looked at any of this stuff yet; the accelerator table is pretty far down my list of v5 features to look at.) If the answer is "not much" then maybe it ought to be renamed DWARFAppleNamesTable instead.

The DWARF v5 accelerator table is a direct evolution of the Apple accelerator table, so it is quite possible that we can share some of the implementation. Form a cursory glance it looks like at least the accessors for the hash table (bucket count, ...) are similar enough that they can share a common interface. We probably can't make that call until someone actually sits down and comes up with a design for how to implement the DWARF 5 accelerator tables, though. How about we revisit this question then? Hopefully this won't be too far out into the future.

Thanks for the info, if there's a reasonable chance to make it reasonably common then I'm happy to leave the naming as is for now.

[sgravani]

Adding llvm-commits.

Summary:
This patch adds code which verifies that each bucket in the .apple_names
accelerator table is either empty or has a valid hash index.

[aprantl]

In D34177#779723, @probinson wrote:

In D34177#779712, @aprantl wrote:

In D34177#779664, @probinson wrote:

I understand that DWARFAcceleratorTable already exists and you are building on that, but I have to wonder how much (if any) of this can be leveraged for the actual DWARF v5 standard's .debug_names section. (I haven't looked at any of this stuff yet; the accelerator table is pretty far down my list of v5 features to look at.) If the answer is "not much" then maybe it ought to be renamed DWARFAppleNamesTable instead.

The DWARF v5 accelerator table is a direct evolution of the Apple accelerator table, so it is quite possible that we can share some of the implementation. Form a cursory glance it looks like at least the accessors for the hash table (bucket count, ...) are similar enough that they can share a common interface. We probably can't make that call until someone actually sits down and comes up with a design for how to implement the DWARF 5 accelerator tables, though. How about we revisit this question then? Hopefully this won't be too far out into the future.

Thanks for the info, if there's a reasonable chance to make it reasonably common then I'm happy to leave the naming as is for now.

And it is totally possible that

include/llvm/DebugInfo/DWARF/DWARFVerifier.h

103 ↗

(On Diff #102436)

side-note: We generally use \return over @return. You might want to update this in the entire file in a separate commit.

lib/DebugInfo/DWARF/DWARFVerifier.cpp

291 ↗

(On Diff #102436)

General question: Should error messages be printed to errs() (or rather a separate error stream passed to DWARFVerifier)?
This is a pre-existing problem with the other checks, too, so it doesn't need to be fixed in this patch.

[probinson]

A couple of minor comments inline. I'm okay with this, assuming Adrian is.

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

1 ↗

(On Diff #102436)

Is the "env" necessary? I don't recall seeing other tests that do that.

10 ↗

(On Diff #102436)

s/the there/there/

[sgravani]

Removed the env from test case.
Fixed the description in test case.
Added the error message next to the line in the .s file that triggers the error in verify.

[sgravani]

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

1 ↗

(On Diff #102436)

It wasn't, good catch.

10 ↗

(On Diff #102436)

Not sure I addressed your comment, I fixed the text a bit.

[sgravani]

include/llvm/DebugInfo/DWARF/DWARFVerifier.h

103 ↗

(On Diff #102436)

Ok, I'll do that.

[aprantl]

This is good to go now. Thanks!

[probinson]

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

10 ↗

(On Diff #102436)

New comment looks fine thanks!

[dblaikie]

llvm/trunk/include/llvm/DebugInfo/DWARF/DWARFVerifier.h

81

Maybe use a non-static data member initializer here (& move the other members over to using that syntax too (in a separate pre-commit, doesn't need review))

llvm/trunk/lib/DebugInfo/DWARF/DWARFVerifier.cpp

290–293

Is this error produced when the section is not present? Is that the right behavior/does this need an error in that case?

310

Probably use a boolean flag if that's the only thing that matters? ("HasErrors"?)

llvm/trunk/test/tools/llvm-dwarfdump/X86/apple_names_verify_buckets.s

1–10

Provide some detail about what this test case was built from (source code, command line, etc)?

5–6

This seems pretty vague/non-specific for a test case. The error message should be tested.

Also, add a test case with an object with no apple names, to demonstrate what happens there. (be it an error, or silence, depending on the resolution of my other comment).

[sgravani]

llvm/trunk/lib/DebugInfo/DWARF/DWARFVerifier.cpp

290–293

In such a case, we should not have any output message.
Thanks for noticing! fixed it in new commit.

310

I prefer to stay consistent with the naming in the other handle[section] functions in the class.

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

class DWARFAcceleratorTable {
   const RelocAddrMap& Relocs;
 
 public:
   DWARFAcceleratorTable(DataExtractor AccelSection, DataExtractor StringSection,
                         const RelocAddrMap &Relocs)
     : AccelSection(AccelSection), StringSection(StringSection), Relocs(Relocs) {}
 
   bool extract();
+  uint32_t getNumBuckets();
+  uint32_t getNumHashes();
+  uint32_t getSizeHdr();
+  uint32_t getHeaderDataLength();
   void dump(raw_ostream &OS) const;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_DWARFACCELERATORTABLE_H

llvm/trunk/include/llvm/DebugInfo/DWARF/DWARFVerifier.h

 #include <set>
 
 namespace llvm {
 class raw_ostream;
 struct DWARFAttribute;
 class DWARFContext;
 class DWARFDie;
 class DWARFUnit;
+class DWARFAcceleratorTable;
 
 /// A class that verifies DWARF debug information given a DWARF Context.
 class DWARFVerifier {
   raw_ostream &OS;
   DWARFContext &DCtx;
   /// A map that tracks all references (converted absolute references) so we
   /// can verify each reference points to a valid DIE and not an offset that
   /// lies between to valid DIEs.
   std::map<uint64_t, std::set<uint32_t>> ReferenceToDIEOffsets;
   uint32_t NumDebugInfoErrors;
   uint32_t NumDebugLineErrors;
+  uint32_t NumAppleNamesErrors;
 
   /// Verifies the attribute's DWARF attribute and its value.
   ///
   /// This function currently checks for:
   /// - DW_AT_ranges values is a valid .debug_ranges offset
   /// - DW_AT_stmt_list is a valid .debug_line offset
   ///
   /// @param Die          The DWARF DIE that owns the attribute value
class DWARFVerifier {
   ///
   /// This function currently checks for:
   /// - addresses within a sequence that decrease in value
   /// - invalid file indexes
   void verifyDebugLineRows();
 
 public:
   DWARFVerifier(raw_ostream &S, DWARFContext &D)
-      : OS(S), DCtx(D), NumDebugInfoErrors(0), NumDebugLineErrors(0) {}
+      : OS(S), DCtx(D), NumDebugInfoErrors(0), NumDebugLineErrors(0),
+        NumAppleNamesErrors(0) {}
   /// Verify the information in the .debug_info section.
   ///
   /// Any errors are reported to the stream that was this object was
   /// constructed with.
   ///
   /// @return True if the .debug_info verifies successfully, false otherwise.
   bool handleDebugInfo();
 
   /// Verify the information in the .debug_line section.
   ///
   /// Any errors are reported to the stream that was this object was
   /// constructed with.
   ///
   /// @return True if the .debug_line verifies successfully, false otherwise.
   bool handleDebugLine();
+
+  /// Verify the information in the .apple_names accelerator table.
+  ///
+  /// Any errors are reported to the stream that was this object was
+  /// constructed with.
+  ///
+  /// @return True if the .apple_names verifies successfully, false otherwise.
+  bool handleAppleNames();
 };
 
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_DWARF_DWARFCONTEXT_H

llvm/trunk/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp

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));
   }
 
   return true;
 }
 
+uint32_t DWARFAcceleratorTable::getNumBuckets() { return Hdr.NumBuckets; }
+uint32_t DWARFAcceleratorTable::getNumHashes() { return Hdr.NumHashes; }
+uint32_t DWARFAcceleratorTable::getSizeHdr() { return sizeof(Hdr); }
+uint32_t DWARFAcceleratorTable::getHeaderDataLength() {
+  return Hdr.HeaderDataLength;
+}
+
 LLVM_DUMP_METHOD void DWARFAcceleratorTable::dump(raw_ostream &OS) const {
   // Dump the header.
   OS << "Magic = " << format("0x%08x", Hdr.Magic) << '\n'
      << "Version = " << format("0x%04x", Hdr.Version) << '\n'
      << "Hash function = " << format("0x%08x", Hdr.HashFunction) << '\n'
      << "Bucket count = " << Hdr.NumBuckets << '\n'
      << "Hashes count = " << Hdr.NumHashes << '\n'
      << "HeaderData length = " << Hdr.HeaderDataLength << '\n'

llvm/trunk/lib/DebugInfo/DWARF/DWARFContext.cpp

bool DWARFContext::verify(raw_ostream &OS, DIDumpType DumpType) {
   if (DumpType == DIDT_All || DumpType == DIDT_Info) {
     if (!verifier.handleDebugInfo())
       Success = false;
   }
   if (DumpType == DIDT_All || DumpType == DIDT_Line) {
     if (!verifier.handleDebugLine())
       Success = false;
   }
+  if (DumpType == DIDT_All || DumpType == DIDT_AppleNames) {
+    if (!verifier.handleAppleNames())
+      Success = false;
+  }
   return Success;
 }
+
 const DWARFUnitIndex &DWARFContext::getCUIndex() {
   if (CUIndex)
     return *CUIndex;
 
   DataExtractor CUIndexData(getCUIndexSection(), isLittleEndian(), 0);
 
   CUIndex = llvm::make_unique<DWARFUnitIndex>(DW_SECT_INFO);
   CUIndex->parse(CUIndexData);

llvm/trunk/lib/DebugInfo/DWARF/DWARFVerifier.cpp

 //===- DWARFVerifier.cpp --------------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/DebugInfo/DWARF/DWARFVerifier.h"
 #include "llvm/DebugInfo/DWARF/DWARFCompileUnit.h"
 #include "llvm/DebugInfo/DWARF/DWARFContext.h"
 #include "llvm/DebugInfo/DWARF/DWARFDebugLine.h"
 #include "llvm/DebugInfo/DWARF/DWARFDie.h"
 #include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
 #include "llvm/DebugInfo/DWARF/DWARFSection.h"
+#include "llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h"
 #include "llvm/Support/raw_ostream.h"
 #include <map>
 #include <set>
 #include <vector>
 
 using namespace llvm;
 using namespace dwarf;
 using namespace object;

 
 bool DWARFVerifier::handleDebugLine() {
   NumDebugLineErrors = 0;
   OS << "Verifying .debug_line...\n";
   verifyDebugLineStmtOffsets();
   verifyDebugLineRows();
   return NumDebugLineErrors == 0;
 }
+
+bool DWARFVerifier::handleAppleNames() {
+  NumAppleNamesErrors = 0;
+  OS << "Verifying .apple_names...\n";
+
+  DataExtractor AppleNamesSection(DCtx.getAppleNamesSection().Data,
+                                  DCtx.isLittleEndian(), 0);
+  DataExtractor StrData(DCtx.getStringSection(), DCtx.isLittleEndian(), 0);
+  DWARFAcceleratorTable AppleNames(AppleNamesSection, StrData,
+                                   DCtx.getAppleNamesSection().Relocs);
+
+  if (!AppleNames.extract()) {
+    OS << "error: cannot extract .apple_names accelerator table\n";
+    return false;
+  }
+
+  // Verify that all buckets have a valid hash index or are empty
+  uint32_t NumBuckets = AppleNames.getNumBuckets();
+  uint32_t NumHashes = AppleNames.getNumHashes();
+
+  uint32_t BucketsOffset =
+      AppleNames.getSizeHdr() + AppleNames.getHeaderDataLength();
+
+  for (uint32_t BucketIdx = 0; BucketIdx < NumBuckets; ++BucketIdx) {
+    uint32_t HashIdx = AppleNamesSection.getU32(&BucketsOffset);
+    if (HashIdx >= NumHashes && HashIdx != UINT32_MAX) {
+      OS << format("error: Bucket[%d] has invalid hash index: [%d]\n",
+                   BucketIdx, HashIdx);
+      ++NumAppleNamesErrors;
+    }
+  }
+  return NumAppleNamesErrors == 0;
+}

llvm/trunk/test/tools/llvm-dwarfdump/X86/apple_names_verify_buckets.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:
+
+# This test is meant to verify that the -verify option 
+# in llvm-dwarfdump, correctly identifies
+# an invalid hash index for bucket[0] in the .apple_names section. 
+
+  .section  __TEXT,__text,regular,pure_instructions
+  .file 1 "basic.c"
+  .comm _i,4,2                  ## @i
+  .section  __DWARF,__debug_str,regular,debug
+Linfo_string:
+  .asciz  "basic.c"               ## string offset=42
+  .asciz  "i"                     ## string offset=84
+  .asciz  "int"                   ## string offset=86
+  .section  __DWARF,__debug_loc,regular,debug
+Lsection_debug_loc:
+  .section  __DWARF,__debug_abbrev,regular,debug
+Lsection_abbrev:
+  .byte 1                       ## Abbreviation Code
+  .byte 17                      ## DW_TAG_compile_unit
+  .byte 1                       ## DW_CHILDREN_yes
+  .byte 37                      ## DW_AT_producer
+  .byte 14                      ## DW_FORM_strp
+  .byte 19                      ## DW_AT_language
+  .byte 5                       ## DW_FORM_data2
+  .byte 3                       ## DW_AT_name
+  .byte 14                      ## DW_FORM_strp
+  .byte 16                      ## DW_AT_stmt_list
+  .byte 23                      ## DW_FORM_sec_offset
+  .byte 27                      ## DW_AT_comp_dir
+  .byte 14                      ## DW_FORM_strp
+  .byte 0                       ## EOM(1)
+  .byte 0                       ## EOM(2)
+  .byte 2                       ## Abbreviation Code
+  .byte 52                      ## DW_TAG_variable
+  .byte 0                       ## DW_CHILDREN_no
+  .byte 3                       ## DW_AT_name
+  .byte 14                      ## DW_FORM_strp
+  .byte 73                      ## DW_AT_type
+  .byte 19                      ## DW_FORM_ref4
+  .byte 63                      ## DW_AT_external
+  .byte 25                      ## DW_FORM_flag_present
+  .byte 58                      ## DW_AT_decl_file
+  .byte 11                      ## DW_FORM_data1
+  .byte 59                      ## DW_AT_decl_line
+  .byte 11                      ## DW_FORM_data1
+  .byte 2                       ## DW_AT_location
+  .byte 24                      ## DW_FORM_exprloc
+  .byte 0                       ## EOM(1)
+  .byte 0                       ## EOM(2)
+  .byte 3                       ## Abbreviation Code
+  .byte 36                      ## DW_TAG_base_type
+  .byte 0                       ## DW_CHILDREN_no
+  .byte 3                       ## DW_AT_name
+  .byte 14                      ## DW_FORM_strp
+  .byte 62                      ## DW_AT_encoding
+  .byte 11                      ## DW_FORM_data1
+  .byte 11                      ## DW_AT_byte_size
+  .byte 11                      ## DW_FORM_data1
+  .byte 0                       ## EOM(1)
+  .byte 0                       ## EOM(2)
+  .byte 0                       ## EOM(3)
+  .section  __DWARF,__debug_info,regular,debug
+Lsection_info:
+Lcu_begin0:
+  .long 55                      ## Length of Unit
+  .short  4                       ## DWARF version number
+Lset0 = Lsection_abbrev-Lsection_abbrev ## Offset Into Abbrev. Section
+  .long Lset0
+  .byte 8                       ## Address Size (in bytes)
+  .byte 1                       ## Abbrev [1] 0xb:0x30 DW_TAG_compile_unit
+  .long 0                       ## DW_AT_producer
+  .short  12                      ## DW_AT_language
+  .long 42                      ## DW_AT_name
+Lset1 = Lline_table_start0-Lsection_line ## DW_AT_stmt_list
+  .long Lset1
+  .long 50                      ## DW_AT_comp_dir
+  .byte 2                       ## Abbrev [2] 0x1e:0x15 DW_TAG_variable
+  .long 84                      ## DW_AT_name
+  .long 51                      ## DW_AT_type
+                                        ## DW_AT_external
+  .byte 1                       ## DW_AT_decl_file
+  .byte 1                       ## DW_AT_decl_line
+  .byte 9                       ## DW_AT_location
+  .byte 3
+  .quad _i
+  .byte 3                       ## Abbrev [3] 0x33:0x7 DW_TAG_base_type
+  .long 86                      ## DW_AT_name
+  .byte 5                       ## DW_AT_encoding
+  .byte 4                       ## DW_AT_byte_size
+  .byte 0                       ## End Of Children Mark
+  .section  __DWARF,__debug_ranges,regular,debug
+Ldebug_range:
+  .section  __DWARF,__debug_macinfo,regular,debug
+Ldebug_macinfo:
+Lcu_macro_begin0:
+  .byte 0                       ## End Of Macro List Mark
+  .section  __DWARF,__apple_names,regular,debug
+Lnames_begin:
+  .long 1212240712              ## Header Magic
+  .short  1                       ## Header Version
+  .short  0                       ## Header Hash Function
+  .long 1                       ## Header Bucket Count
+  .long 1                       ## 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  6                       ## DW_FORM_data4
+  .long -2                      ## Bucket 0 -- error: Bucket[0] has invalid hash index: [-2]
+  .long 177678                  ## Hash in Bucket 0
+  .long LNames0-Lnames_begin    ## Offset in Bucket 0
+LNames0:
+  .long 84                      ## i
+  .long 1                       ## Num DIEs
+  .long 30
+  .long 0
+  .section  __DWARF,__apple_objc,regular,debug
+Lobjc_begin:
+  .long 1212240712              ## Header Magic
+  .short  1                       ## Header Version
+  .short  0                       ## Header Hash Function
+  .long 1                       ## Header Bucket Count
+  .long 0                       ## 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  6                       ## DW_FORM_data4
+  .long -1                      ## Bucket 0
+  .section  __DWARF,__apple_namespac,regular,debug
+Lnamespac_begin:
+  .long 1212240712              ## Header Magic
+  .short  1                       ## Header Version
+  .short  0                       ## Header Hash Function
+  .long 1                       ## Header Bucket Count
+  .long 0                       ## 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  6                       ## DW_FORM_data4
+  .long -1                      ## Bucket 0
+  .section  __DWARF,__apple_types,regular,debug
+Ltypes_begin:
+  .long 1212240712              ## Header Magic
+  .short  1                       ## Header Version
+  .short  0                       ## Header Hash Function
+  .long 1                       ## Header Bucket Count
+  .long 1                       ## Header Hash Count
+  .long 20                      ## Header Data Length
+  .long 0                       ## HeaderData Die Offset Base
+  .long 3                       ## HeaderData Atom Count
+  .short  1                       ## DW_ATOM_die_offset
+  .short  6                       ## DW_FORM_data4
+  .short  3                       ## DW_ATOM_die_tag
+  .short  5                       ## DW_FORM_data2
+  .short  4                       ## DW_ATOM_type_flags
+  .short  11                      ## DW_FORM_data1
+  .long 0                       ## Bucket 0
+  .long 193495088               ## Hash in Bucket 0
+  .long Ltypes0-Ltypes_begin    ## Offset in Bucket 0
+Ltypes0:
+  .long 86                      ## int
+  .long 1                       ## Num DIEs
+  .long 51
+  .short  36
+  .byte 0
+  .long 0
+  .section  __DWARF,__apple_exttypes,regular,debug
+Lexttypes_begin:
+  .long 1212240712              ## Header Magic
+  .short  1                       ## Header Version
+  .short  0                       ## Header Hash Function
+  .long 1                       ## Header Bucket Count
+  .long 0                       ## Header Hash Count
+  .long 12                      ## Header Data Length
+  .long 0                       ## HeaderData Die Offset Base
+  .long 1                       ## HeaderData Atom Count
+  .short  7                       ## DW_ATOM_ext_types
+  .short  6                       ## DW_FORM_data4
+  .long -1                      ## Bucket 0
+
+.subsections_via_symbols
+  .section  __DWARF,__debug_line,regular,debug
+Lsection_line:
+Lline_table_start0: