Re: [PATCH] libdw. Don't blow up stack in dwarf_getsrclines with lots of lines.

[Mark Wielaard <mjw at redhat dot com>]

On Wed, 2013-07-03 at 12:44 +0200, Petr Machata wrote:
> We tend to use stack allocation a fair deal in elfutils (61 alloca's
> vs. 112 [cm]alloc's; not counting VLA's, as they are hard to grep for).
> I'm afraid more of those places might blow up in face of malformed, or
> simply huge data.
> 
> In glibc, there are macros for handling malloc/alloca splits (alloca if
> small, malloc otherwise).  In this case, we don't know the line count in
> advance, and would have to use LINEENDP-LINEP as a hint.  But maybe it
> would be worth it to port those over, as other places might benefit from
> this more directly.  I'll look into it.

Most other locations (I found less than you, so maybe I missed some)
seem to be somewhat constrained and used for smaller data structures.
But there are a couple of other places (going over the dirlist, parsing
everything in an expression block, etc.) that could potentially contain
many items and surprise us. If there is a way to automatically keep
track of the stack depth and switch to other allocation techniques when
detecting a large amount of stack allocations that would be nice.

> For now, your patch makes
> sense, except:
> 
> > +	if (unlikely (add_new_line (ll, end_seq)))			\
> >  	  goto invalid_data;						\
> 
> Wouldn't this leak the malloc'd blocks?

Indeed it would, as would some other failure paths. Thanks for spotting
that. I tweaked the patch a little to initialize everything slightly
earlier and do the deallocation at the very end (all success and failure
paths end up at out:). New patch attached. Also tested with valgrind to
make sure there are no leaks or erroneous frees.

Cheers,

Mark

commit 5debaf87c033a60a9a704741b9e2b9c60ad08ceb
Author: Mark Wielaard <mjw@redhat.com>
Date:   Tue Jul 2 16:36:16 2013 +0200

    libdw. Don't blow up stack in dwarf_getsrclines with lots of lines.
    
    When a CU has a really large number of lines dwarf_getsrclines could blow
    up the stack because it uses alloca for temporary storage. Use malloc and
    free if the number of lines gets too big.

diff --git a/libdw/ChangeLog b/libdw/ChangeLog
index 59b6c63..c595891 100644
--- a/libdw/ChangeLog
+++ b/libdw/ChangeLog
@@ -1,3 +1,9 @@
+2013-07-02  Mark Wielaard  <mjw@redhat.com>
+
+	* dwarf_getsrclines.c (dwarf_getsrclines): Add new stack allocation
+	limit MAX_STACK_ALLOC.  After MAX_STACK_ALLOC lines use malloc in
+	NEW_LINE macro.  Free malloced line records if any at the end.
+
 2013-05-03  Mark Wielaard  <mjw@redhat.com>
 
 	* dwarf_getsrclines.c (dwarf_getsrclines): Only set end_sequence
diff --git a/libdw/dwarf_getsrclines.c b/libdw/dwarf_getsrclines.c
index fa4dd18..7b174cf 100644
--- a/libdw/dwarf_getsrclines.c
+++ b/libdw/dwarf_getsrclines.c
@@ -75,6 +75,15 @@ dwarf_getsrclines (Dwarf_Die *cudie, Dwarf_Lines **lines, size_t *nlines)
 
   int res = -1;
 
+  struct linelist *linelist = NULL;
+  unsigned int nlinelist = 0;
+
+  /* If there are a large number of lines don't blow up the stack.
+     Keep track of the last malloced linelist record and free them
+     through the next pointer at the end.  */
+#define MAX_STACK_ALLOC 4096
+  struct linelist *malloc_linelist = NULL;
+
   /* Get the information if it is not already known.  */
   struct Dwarf_CU *const cu = cudie->cu;
   if (cu->lines == NULL)
@@ -325,20 +334,26 @@ dwarf_getsrclines (Dwarf_Die *cudie, Dwarf_Lines **lines, size_t *nlines)
       }
 
       /* Process the instructions.  */
-      struct linelist *linelist = NULL;
-      unsigned int nlinelist = 0;
 
       /* Adds a new line to the matrix.
 	 We cannot simply define a function because we want to use alloca.  */
 #define NEW_LINE(end_seq)						\
       do {								\
-	if (unlikely (add_new_line (alloca (sizeof (struct linelist)),	\
-				    end_seq)))				\
+	struct linelist *ll = (nlinelist < MAX_STACK_ALLOC		\
+			       ? alloca (sizeof (struct linelist))	\
+			       : malloc (sizeof (struct linelist)));	\
+	if (nlinelist >= MAX_STACK_ALLOC)				\
+	  malloc_linelist = ll;						\
+	if (unlikely (add_new_line (ll, end_seq)))			\
 	  goto invalid_data;						\
       } while (0)
 
       inline bool add_new_line (struct linelist *new_line, bool end_sequence)
       {
+	new_line->next = linelist;
+	linelist = new_line;
+	++nlinelist;
+
 	/* Set the line information.  For some fields we use bitfields,
 	   so we would lose information if the encoded values are too large.
 	   Check just for paranoia, and call the data "invalid" if it
@@ -365,10 +380,6 @@ dwarf_getsrclines (Dwarf_Die *cudie, Dwarf_Lines **lines, size_t *nlines)
 
 #undef SET
 
-	new_line->next = linelist;
-	linelist = new_line;
-	++nlinelist;
-
 	return false;
       }
 
@@ -732,6 +743,14 @@ dwarf_getsrclines (Dwarf_Die *cudie, Dwarf_Lines **lines, size_t *nlines)
     }
  out:
 
+  /* Free malloced line records, if any.  */
+  for (unsigned int i = MAX_STACK_ALLOC; i < nlinelist; i++)
+    {
+      struct linelist *ll = malloc_linelist->next;
+      free (malloc_linelist);
+      malloc_linelist = ll;
+    }
+
   // XXX Eventually: unlocking here.
 
   return res;