[DebugInfo] Prevent infinite recursion for malformed DWARF

[JDevlieghere]

Summary

This prevents infinite recursion in DWARFDie::findRecursively for
malformed DWARF where a DIE references itself.

https://bugs.llvm.org/PR36257

[JDevlieghere]

I plan on adding a verifier check for this in a follow up commit.

[aprantl]

llvm/lib/DebugInfo/DWARF/DWARFDie.cpp

299

Perhaps add a comment what this means?

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

18

Is there anything you could CHECK? Otherwise this will pass even if llvm-mc is returning empty output.

[JDevlieghere]

• Add comment
• Add CHECK clause

[dblaikie]

I'm guessing this is insufficient for catching indirect recursion (DIE A refers to DIE B and B back to A)?

Ideally/the original version of this, I think was non-recursive and only specifically looked for certain attributes in order and then stopped. I'd sort of rather than, because it's more constrained.

[JDevlieghere]

In D43092#1002598, @dblaikie wrote:

I'm guessing this is insufficient for catching indirect recursion (DIE A refers to DIE B and B back to A)?

That's true, unfortunately. Is it worth to convert this to a worklist and keep track of the already-seen DIEs?

Ideally/the original version of this, I think was non-recursive and only specifically looked for certain attributes in order and then stopped. I'd sort of rather than, because it's more constrained.

The original find() still exists, so I'd expect this variant only to be used where the recursive property is needed.

[dblaikie]

Ideally/the original version of this, I think was non-recursive and only specifically looked for certain attributes in order and then stopped. I'd sort of rather than, because it's more constrained.

The original find() still exists, so I'd expect this variant only to be used where the recursive property is needed.

'find()' only searches the current DIE. findRecursively is needed when looking through abstract or specification references - but these aren't, so far as I know, arbitrarily nested (you can't have an unlimited chain of abstract/specifications - really you can only have at most one of each, in a specific order (abstract then specification) - as far as I recall/know). So unlimited recursion is a bit overpowered here.

Could you check the revision history here? I'm pretty sure the first version of this I reviewed from Greg wasn't recursive - and then it became recursive at some point to handle something needed, but maybe those decisions need to be reexamined?

[JDevlieghere]

In D43092#1002677, @dblaikie wrote:

Could you check the revision history here? I'm pretty sure the first version of this I reviewed from Greg wasn't recursive - and then it became recursive at some point to handle something needed, but maybe those decisions need to be reexamined?

It was @clayborg himself that updated the implementation. (D40156 rL319104)

The previous implementation would only look 1 DW_AT_specification or DW_AT_abstract_origin deep. This means DWARFDie::getName() would fail in certain cases. I ran into such a case while creating a tool that used the LLVM DWARF parser to generate a symbolication format so I have seen this in the wild.

[JDevlieghere]

• Turn recursion into worklist.
• Keep track of already seen DIEs.

[JDevlieghere]

Use SmallSet<DWARFDie, 3> (running dsymutil over clang showed that there were never more than 3 elements in the set for valid DWARF).

[aprantl]

Thanks for checking!

llvm/lib/DebugInfo/DWARF/DWARFDie.cpp

300

Perhaps add a comment explaining that this avoids infinite recursion on malformed input and empirically we never have a depth>3 ?

[dblaikie]

Sorry - could we revisit this?

I think my concerns expressed still haven't been resolved:

"Could you check the revision history here? I'm pretty sure the first
version of this I reviewed from Greg wasn't recursive - and then it became
recursive at some point to handle something needed, but maybe those
decisions need to be reexamined?" (& related comments back there)

llvm/lib/DebugInfo/DWARF/DWARFDie.cpp

 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/WithColor.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
 #include <cinttypes>
 #include <cstdint>
+#include <set>
 #include <string>
 #include <utility>
 
 using namespace llvm;
 using namespace dwarf;
 using namespace object;
 
 static void dumpApplePropertyAttribute(raw_ostream &OS, uint64_t Val) {
for (auto Attr : Attrs) {
         return Value;
     }
   }
   return None;
 }
 
 Optional<DWARFFormValue>
 DWARFDie::findRecursively(ArrayRef<dwarf::Attribute> Attrs) const {
-  if (!isValid())
-    return None;
-  if (auto Value = find(Attrs))
-    return Value;
-  if (auto Die = getAttributeValueAsReferencedDie(DW_AT_abstract_origin)) {
-    if (auto Value = Die.findRecursively(Attrs))
-      return Value;
-  }
-  if (auto Die = getAttributeValueAsReferencedDie(DW_AT_specification)) {
-    if (auto Value = Die.findRecursively(Attrs))
+  std::vector<DWARFDie> Worklist;
+  std::set<DWARFDie> Seen;
+  Worklist.push_back(*this);
+
+  while (!Worklist.empty()) {
+    DWARFDie Die = Worklist.back();
+    Worklist.pop_back();
+
+    if (!Die.isValid())
+      continue;
+
+    if (Seen.count(Die))
+      continue;
+
+    Seen.insert(Die);
+
+    if (auto Value = Die.find(Attrs))
       return Value;
+
+    if (auto D = Die.getAttributeValueAsReferencedDie(DW_AT_abstract_origin))
+      Worklist.push_back(D);
+
+    if (auto D = Die.getAttributeValueAsReferencedDie(DW_AT_specification))
+      Worklist.push_back(D);
   }
+
   return None;
 }
 
 DWARFDie
 DWARFDie::getAttributeValueAsReferencedDie(dwarf::Attribute Attr) const {
   if (auto SpecRef = toReference(find(Attr))) {
     if (auto SpecUnit = U->getUnitSection().getUnitForOffset(*SpecRef))
       return SpecUnit->getDIEForOffset(*SpecRef);

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

+# This test ensures that dwarfdump doesn't crash for malformed DWARF where a
+# DIE references itself.
+#
+# Source:
+#   void f();
+#   __attribute__((always_inline)) void g() {
+#     f();
+#   }
+#   void h() {
+#     g();
+#   };
+#
+# Compile with:
+#   clang inlined.c -S -g -o inlined.s
+#
+# RUN: llvm-mc %s -filetype obj -triple x86_64-apple-darwin -o - \
+# RUN:   | llvm-dwarfdump -debug-info - \
+# RUN:   | FileCheck %s
+
+# CHECK: 0x0000005a:     DW_TAG_inlined_subroutine
+# CHECK-NEXT: DW_AT_abstract_origin (0x0000005a)
+
+  .section  __TEXT,__text,regular,pure_instructions
+  .macosx_version_min 10, 13
+  .globl  _g                      ## -- Begin function g
+  .p2align  4, 0x90
+_g:                                     ## @g
+Lfunc_begin0:
+  .file 1 "inlined.c"
+  .loc  1 2 0                   ## inlined.c:2:0
+  .cfi_startproc
+## %bb.0:                               ## %entry
+  pushq %rbp
+  .cfi_def_cfa_offset 16
+  .cfi_offset %rbp, -16
+  movq  %rsp, %rbp
+  .cfi_def_cfa_register %rbp
+Ltmp0:
+  .loc  1 3 3 prologue_end      ## inlined.c:3:3
+  movb  $0, %al
+  callq _f
+  .loc  1 4 1                   ## inlined.c:4:1
+  popq  %rbp
+  retq
+Ltmp1:
+Lfunc_end0:
+  .cfi_endproc
+                                        ## -- End function
+  .globl  _h                      ## -- Begin function h
+  .p2align  4, 0x90
+_h:                                     ## @h
+Lfunc_begin1:
+  .loc  1 5 0                   ## inlined.c:5:0
+  .cfi_startproc
+## %bb.0:                               ## %entry
+  pushq %rbp
+  .cfi_def_cfa_offset 16
+  .cfi_offset %rbp, -16
+  movq  %rsp, %rbp
+  .cfi_def_cfa_register %rbp
+Ltmp2:
+  .loc  1 3 3 prologue_end      ## inlined.c:3:3
+  movb  $0, %al
+  callq _f
+Ltmp3:
+  .loc  1 7 1                   ## inlined.c:7:1
+  popq  %rbp
+  retq
+Ltmp4:
+Lfunc_end1:
+  .cfi_endproc
+                                        ## -- End function
+  .section  __DWARF,__debug_str,regular,debug
+Linfo_string:
+  .asciz  "clang version 7.0.0 "  ## string offset=0
+  .asciz  "inlined.c"             ## string offset=21
+  .asciz  "/private/tmp"          ## string offset=31
+  .asciz  "g"                     ## string offset=44
+  .asciz  "h"                     ## string offset=46
+  .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 17                      ## DW_AT_low_pc
+  .byte 1                       ## DW_FORM_addr
+  .byte 18                      ## DW_AT_high_pc
+  .byte 6                       ## DW_FORM_data4
+  .byte 0                       ## EOM(1)
+  .byte 0                       ## EOM(2)
+  .byte 2                       ## Abbreviation Code
+  .byte 46                      ## DW_TAG_subprogram
+  .byte 0                       ## DW_CHILDREN_no
+  .byte 17                      ## DW_AT_low_pc
+  .byte 1                       ## DW_FORM_addr
+  .byte 18                      ## DW_AT_high_pc
+  .byte 6                       ## DW_FORM_data4
+  .byte 64                      ## DW_AT_frame_base
+  .byte 24                      ## DW_FORM_exprloc
+  .byte 49                      ## DW_AT_abstract_origin
+  .byte 19                      ## DW_FORM_ref4
+  .byte 0                       ## EOM(1)
+  .byte 0                       ## EOM(2)
+  .byte 3                       ## Abbreviation Code
+  .byte 46                      ## DW_TAG_subprogram
+  .byte 0                       ## DW_CHILDREN_no
+  .byte 3                       ## DW_AT_name
+  .byte 14                      ## DW_FORM_strp
+  .byte 58                      ## DW_AT_decl_file
+  .byte 11                      ## DW_FORM_data1
+  .byte 59                      ## DW_AT_decl_line
+  .byte 11                      ## DW_FORM_data1
+  .byte 63                      ## DW_AT_external
+  .byte 25                      ## DW_FORM_flag_present
+  .byte 32                      ## DW_AT_inline
+  .byte 11                      ## DW_FORM_data1
+  .byte 0                       ## EOM(1)
+  .byte 0                       ## EOM(2)
+  .byte 4                       ## Abbreviation Code
+  .byte 46                      ## DW_TAG_subprogram
+  .byte 1                       ## DW_CHILDREN_yes
+  .byte 17                      ## DW_AT_low_pc
+  .byte 1                       ## DW_FORM_addr
+  .byte 18                      ## DW_AT_high_pc
+  .byte 6                       ## DW_FORM_data4
+  .byte 64                      ## DW_AT_frame_base
+  .byte 24                      ## DW_FORM_exprloc
+  .byte 3                       ## DW_AT_name
+  .byte 14                      ## DW_FORM_strp
+  .byte 58                      ## DW_AT_decl_file
+  .byte 11                      ## DW_FORM_data1
+  .byte 59                      ## DW_AT_decl_line
+  .byte 11                      ## DW_FORM_data1
+  .byte 63                      ## DW_AT_external
+  .byte 25                      ## DW_FORM_flag_present
+  .byte 0                       ## EOM(1)
+  .byte 0                       ## EOM(2)
+  .byte 5                       ## Abbreviation Code
+  .byte 29                      ## DW_TAG_inlined_subroutine
+  .byte 0                       ## DW_CHILDREN_no
+  .byte 49                      ## DW_AT_abstract_origin
+  .byte 19                      ## DW_FORM_ref4
+  .byte 17                      ## DW_AT_low_pc
+  .byte 1                       ## DW_FORM_addr
+  .byte 18                      ## DW_AT_high_pc
+  .byte 6                       ## DW_FORM_data4
+  .byte 88                      ## DW_AT_call_file
+  .byte 11                      ## DW_FORM_data1
+  .byte 89                      ## DW_AT_call_line
+  .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 107                     ## 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:0x64 DW_TAG_compile_unit
+  .long 0                       ## DW_AT_producer
+  .short  12                      ## DW_AT_language
+  .long 21                      ## DW_AT_name
+Lset1 = Lline_table_start0-Lsection_line ## DW_AT_stmt_list
+  .long Lset1
+  .long 31                      ## DW_AT_comp_dir
+  .quad Lfunc_begin0            ## DW_AT_low_pc
+Lset2 = Lfunc_end1-Lfunc_begin0         ## DW_AT_high_pc
+  .long Lset2
+  .byte 2                       ## Abbrev [2] 0x2a:0x13 DW_TAG_subprogram
+  .quad Lfunc_begin0            ## DW_AT_low_pc
+Lset3 = Lfunc_end0-Lfunc_begin0         ## DW_AT_high_pc
+  .long Lset3
+  .byte 1                       ## DW_AT_frame_base
+  .byte 86
+  .long 61                      ## DW_AT_abstract_origin
+  .byte 3                       ## Abbrev [3] 0x3d:0x8 DW_TAG_subprogram
+  .long 44                      ## DW_AT_name
+  .byte 1                       ## DW_AT_decl_file
+  .byte 2                       ## DW_AT_decl_line
+                                        ## DW_AT_external
+  .byte 1                       ## DW_AT_inline
+  .byte 4                       ## Abbrev [4] 0x45:0x29 DW_TAG_subprogram
+  .quad Lfunc_begin1            ## DW_AT_low_pc
+Lset4 = Lfunc_end1-Lfunc_begin1         ## DW_AT_high_pc
+  .long Lset4
+  .byte 1                       ## DW_AT_frame_base
+  .byte 86
+  .long 46                      ## DW_AT_name
+  .byte 1                       ## DW_AT_decl_file
+  .byte 5                       ## DW_AT_decl_line
+                                        ## DW_AT_external
+  .byte 5                       ## Abbrev [5] 0x5a:0x13 DW_TAG_inlined_subroutine
+  .long 90                      ## DW_AT_abstract_origin <- We modified the value so the DIE references itself.
+  .quad Ltmp2                   ## DW_AT_low_pc
+Lset5 = Ltmp3-Ltmp2                     ## DW_AT_high_pc
+  .long Lset5
+  .byte 1                       ## DW_AT_call_file
+  .byte 6                       ## DW_AT_call_line
+  .byte 0                       ## End Of Children Mark
+  .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 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  6                       ## DW_FORM_data4
+  .long 0                       ## Bucket 0
+  .long 1                       ## Bucket 1
+  .long 177676                  ## Hash in Bucket 0
+  .long 177677                  ## Hash in Bucket 1
+  .long LNames0-Lnames_begin    ## Offset in Bucket 0
+  .long LNames1-Lnames_begin    ## Offset in Bucket 1
+LNames0:
+  .long 44                      ## g
+  .long 2                       ## Num DIEs
+  .long 42
+  .long 90
+  .long 0
+LNames1:
+  .long 46                      ## h
+  .long 1                       ## Num DIEs
+  .long 69
+  .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 0                       ## 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 -1                      ## Bucket 0
+
+.subsections_via_symbols
+  .section  __DWARF,__debug_line,regular,debug
+Lsection_line:
+Lline_table_start0: