[DebugInfo] Prevent infinite recursion for malformed DWARF

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

This fixes PR36257.

Differential revision: https://reviews.llvm.org/D43092

llvm-svn: 331200

2 files changed, 326 insertions, 10 deletions

diff --git a/llvm/lib/DebugInfo/DWARF/DWARFDie.cpp b/llvm/lib/DebugInfo/DWARF/DWARFDie.cpp
index 7ae38e6e053..0d045c5d4bc 100644
--- a/llvm/lib/DebugInfo/DWARF/DWARFDie.cpp
+++ b/llvm/lib/DebugInfo/DWARF/DWARFDie.cpp
@@ -10,6 +10,7 @@
 #include "llvm/DebugInfo/DWARF/DWARFDie.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/DebugInfo/DWARF/DWARFAbbreviationDeclaration.h"
@@ -295,18 +296,37 @@ DWARFDie::find(ArrayRef<dwarf::Attribute> Attrs) const {
 
 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;
+  Worklist.push_back(*this);
+
+  // Keep track if DIEs already seen to prevent infinite recursion.
+  // Empirically we rarely see a depth of more than 3 when dealing with valid
+  // DWARF. This corresponds to following the DW_AT_abstract_origin and
+  // DW_AT_specification just once.
+  SmallSet<DWARFDie, 3> Seen;
+
+  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;
 }
 
diff --git a/llvm/test/tools/llvm-dwarfdump/X86/invalid_abstract_origin.s b/llvm/test/tools/llvm-dwarfdump/X86/invalid_abstract_origin.s
new file mode 100644
index 00000000000..49eb3177e48
--- /dev/null
+++ b/llvm/test/tools/llvm-dwarfdump/X86/invalid_abstract_origin.s
@@ -0,0 +1,296 @@
+# 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: