libbacktrace patch: fix memory allocation buglet on DWARF line table with zero dirs

libbacktrace patch: fix memory allocation buglet on DWARF line table with zero dirs

[Than McIntosh via gcc-patches]

Hello,

The attached patch to libbacktrace is intended to fix a memory
allocation bug involving reading of line table information.

The scenario of interest takes place when libbacktrace reads a DWARF
line table whose directory count is zero (an unusual case). If the
memory allocator invocation triggers a call to mmap, this can cause
the size passed to mmap to be zero, resulting in an EINVAL error.  The
fix is to detect the zero-directory case and avoid invoking the
allocation helper with a zero size.

Questions + comments welcome.

Thanks, Than

---

diff --git a/libbacktrace/dwarf.c b/libbacktrace/dwarf.c
index 80c64034092..bcb2c0991ef 100644
--- a/libbacktrace/dwarf.c
+++ b/libbacktrace/dwarf.c
@@ -1563,16 +1563,15 @@ add_line (struct backtrace_state *state,
struct dwarf_data *ddata,
   return 1;
 }

-/* Free the line header information.  If FREE_FILENAMES is true we
-   free the file names themselves, otherwise we leave them, as there
-   may be line structures pointing to them.  */
+/* Free the line header information.  */

 static void
 free_line_header (struct backtrace_state *state, struct line_header *hdr,
   backtrace_error_callback error_callback, void *data)
 {
-  backtrace_free (state, hdr->dirs, hdr->dirs_count * sizeof (const char *),
-  error_callback, data);
+  if (hdr->dirs_count != 0)
+    backtrace_free (state, hdr->dirs, hdr->dirs_count * sizeof (const char *),
+                    error_callback, data);
   backtrace_free (state, hdr->filenames,
   hdr->filenames_count * sizeof (char *),
   error_callback, data);
@@ -1633,12 +1632,16 @@ read_line_header (struct backtrace_state
*state, struct unit *u,
       ++hdr->dirs_count;
     }

-  hdr->dirs = ((const char **)
-       backtrace_alloc (state,
- hdr->dirs_count * sizeof (const char *),
- line_buf->error_callback, line_buf->data));
-  if (hdr->dirs == NULL)
-    return 0;
+  hdr->dirs = NULL;
+  if (hdr->dirs_count != 0)
+    {
+      hdr->dirs = ((const char **)
+                   backtrace_alloc (state,
+                                    hdr->dirs_count * sizeof (const char *),
+                                    line_buf->error_callback, line_buf->data));
+      if (hdr->dirs == NULL)
+        return 0;
+    }

   i = 0;
   while (*hdr_buf.buf != '\0')

Re: libbacktrace patch: fix memory allocation buglet on DWARF line table with zero dirs

[Than McIntosh via gcc-patches]

Hi again,

I wrote:
== The attached patch to libbacktrace is intended to fix a memory
== allocation bug involving reading of line table information.

I've revised my previous patch to include a new test ("edtest") that
verifies the fix.

Thanks, Than

---

Patch (take 2):

diff --git a/Makefile.am b/Makefile.am
index ec494c4..d236261 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -96,6 +96,17 @@ stest_LDADD = libbacktrace.la

 check_PROGRAMS += stest

+edtest_SOURCES = edtest.c edtest2_build.c
+edtest_LDADD = libbacktrace.la
+
+check_PROGRAMS += edtest
+
+edtest2_build.c: gen_edtest2_build; @true
+gen_edtest2_build: $(srcdir)/edtest2.c
+ cat $(srcdir)/edtest2.c > tmp-edtest2_build.c
+ $(SHELL) $(srcdir)/mvifdiff.sh tmp-edtest2_build.c edtest2_build.c
+ echo timestamp > $@
+
 endif NATIVE

 # We can't use automake's automatic dependency tracking, because it
@@ -126,5 +137,6 @@ read.lo: config.h backtrace.h internal.h
 simple.lo: config.h backtrace.h internal.h
 sort.lo: config.h backtrace.h internal.h
 stest.lo: config.h backtrace.h internal.h
+edtest.lo: config.h backtrace.h internal.h
 state.lo: config.h backtrace.h backtrace-supported.h internal.h
 unknown.lo: config.h backtrace.h internal.h
diff --git a/Makefile.in b/Makefile.in
index f3a7a42..04c6689 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -85,7 +85,7 @@ build_triplet = @build@
 host_triplet = @host@
 target_triplet = @target@
 check_PROGRAMS = $(am__EXEEXT_1)
-@NATIVE_TRUE@am__append_1 = btest stest
+@NATIVE_TRUE@am__append_1 = btest stest edtest
 subdir = .
 DIST_COMMON = $(srcdir)/Makefile.in $(srcdir)/Makefile.am \
  $(top_srcdir)/configure $(am__configure_deps) \
@@ -135,13 +135,18 @@ am__DEPENDENCIES_1 =
 am_libbacktrace_la_OBJECTS = atomic.lo dwarf.lo fileline.lo posix.lo \
  print.lo sort.lo state.lo
 libbacktrace_la_OBJECTS = $(am_libbacktrace_la_OBJECTS)
-@NATIVE_TRUE@am__EXEEXT_1 = btest$(EXEEXT) stest$(EXEEXT)
+@NATIVE_TRUE@am__EXEEXT_1 = btest$(EXEEXT) stest$(EXEEXT) \
+@NATIVE_TRUE@ edtest$(EXEEXT)
 @NATIVE_TRUE@am_btest_OBJECTS = btest-btest.$(OBJEXT)
 btest_OBJECTS = $(am_btest_OBJECTS)
 @NATIVE_TRUE@btest_DEPENDENCIES = libbacktrace.la
 btest_LINK = $(LIBTOOL) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) \
  --mode=link $(CCLD) $(btest_CFLAGS) $(CFLAGS) $(AM_LDFLAGS) \
  $(LDFLAGS) -o $@
+@NATIVE_TRUE@am_edtest_OBJECTS = edtest.$(OBJEXT) \
+@NATIVE_TRUE@ edtest2_build.$(OBJEXT)
+edtest_OBJECTS = $(am_edtest_OBJECTS)
+@NATIVE_TRUE@edtest_DEPENDENCIES = libbacktrace.la
 @NATIVE_TRUE@am_stest_OBJECTS = stest.$(OBJEXT)
 stest_OBJECTS = $(am_stest_OBJECTS)
 @NATIVE_TRUE@stest_DEPENDENCIES = libbacktrace.la
@@ -158,7 +163,7 @@ LINK = $(LIBTOOL) --tag=CC $(AM_LIBTOOLFLAGS)
$(LIBTOOLFLAGS) \
  --mode=link $(CCLD) $(AM_CFLAGS) $(CFLAGS) $(AM_LDFLAGS) \
  $(LDFLAGS) -o $@
 SOURCES = $(libbacktrace_la_SOURCES) $(EXTRA_libbacktrace_la_SOURCES) \
- $(btest_SOURCES) $(stest_SOURCES)
+ $(btest_SOURCES) $(edtest_SOURCES) $(stest_SOURCES)
 MULTISRCTOP =
 MULTIBUILDTOP =
 MULTIDIRS =
@@ -350,6 +355,8 @@ TESTS = $(check_PROGRAMS)
 @NATIVE_TRUE@btest_LDADD = libbacktrace.la
 @NATIVE_TRUE@stest_SOURCES = stest.c
 @NATIVE_TRUE@stest_LDADD = libbacktrace.la
+@NATIVE_TRUE@edtest_SOURCES = edtest.c edtest2_build.c
+@NATIVE_TRUE@edtest_LDADD = libbacktrace.la
 all: config.h
  $(MAKE) $(AM_MAKEFLAGS) all-am

@@ -452,6 +459,9 @@ clean-checkPROGRAMS:
 btest$(EXEEXT): $(btest_OBJECTS) $(btest_DEPENDENCIES)
$(EXTRA_btest_DEPENDENCIES)
  @rm -f btest$(EXEEXT)
  $(btest_LINK) $(btest_OBJECTS) $(btest_LDADD) $(LIBS)
+edtest$(EXEEXT): $(edtest_OBJECTS) $(edtest_DEPENDENCIES)
$(EXTRA_edtest_DEPENDENCIES)
+ @rm -f edtest$(EXEEXT)
+ $(LINK) $(edtest_OBJECTS) $(edtest_LDADD) $(LIBS)
 stest$(EXEEXT): $(stest_OBJECTS) $(stest_DEPENDENCIES)
$(EXTRA_stest_DEPENDENCIES)
  @rm -f stest$(EXEEXT)
  $(LINK) $(stest_OBJECTS) $(stest_LDADD) $(LIBS)
@@ -801,6 +811,12 @@ uninstall-am: uninstall-includeHEADERS
uninstall-libLTLIBRARIES
  uninstall-am uninstall-includeHEADERS uninstall-libLTLIBRARIES


+@NATIVE_TRUE@edtest2_build.c: gen_edtest2_build; @true
+@NATIVE_TRUE@gen_edtest2_build: $(srcdir)/edtest2.c
+@NATIVE_TRUE@ cat $(srcdir)/edtest2.c > tmp-edtest2_build.c
+@NATIVE_TRUE@ $(SHELL) $(srcdir)/mvifdiff.sh tmp-edtest2_build.c
edtest2_build.c
+@NATIVE_TRUE@ echo timestamp > $@
+
 # We can't use automake's automatic dependency tracking, because it
 # breaks when using bootstrap-lean.  Automatic dependency tracking
 # with GCC bootstrap will cause some of the objects to depend on
@@ -829,6 +845,7 @@ read.lo: config.h backtrace.h internal.h
 simple.lo: config.h backtrace.h internal.h
 sort.lo: config.h backtrace.h internal.h
 stest.lo: config.h backtrace.h internal.h
+edtest.lo: config.h backtrace.h internal.h
 state.lo: config.h backtrace.h backtrace-supported.h internal.h
 unknown.lo: config.h backtrace.h internal.h

diff --git a/dwarf.c b/dwarf.c
index b182567..c1bfbf5 100644
--- a/dwarf.c
+++ b/dwarf.c
@@ -1648,16 +1648,15 @@ add_line (struct backtrace_state *state,
struct dwarf_data *ddata,
   return 1;
 }

-/* Free the line header information.  If FREE_FILENAMES is true we
-   free the file names themselves, otherwise we leave them, as there
-   may be line structures pointing to them.  */
+/* Free the line header information.  */

 static void
 free_line_header (struct backtrace_state *state, struct line_header *hdr,
   backtrace_error_callback error_callback, void *data)
 {
-  backtrace_free (state, hdr->dirs, hdr->dirs_count * sizeof (const char *),
-  error_callback, data);
+  if (hdr->dirs_count != 0)
+    backtrace_free (state, hdr->dirs, hdr->dirs_count * sizeof (const char *),
+                    error_callback, data);
   backtrace_free (state, hdr->filenames,
   hdr->filenames_count * sizeof (char *),
   error_callback, data);
@@ -1718,12 +1717,16 @@ read_line_header (struct backtrace_state
*state, struct unit *u,
       ++hdr->dirs_count;
     }

-  hdr->dirs = ((const char **)
-       backtrace_alloc (state,
- hdr->dirs_count * sizeof (const char *),
- line_buf->error_callback, line_buf->data));
-  if (hdr->dirs == NULL)
-    return 0;
+  hdr->dirs = NULL;
+  if (hdr->dirs_count != 0)
+    {
+      hdr->dirs = ((const char **)
+                   backtrace_alloc (state,
+                                    hdr->dirs_count * sizeof (const char *),
+                                    line_buf->error_callback, line_buf->data));
+      if (hdr->dirs == NULL)
+        return 0;
+    }

   i = 0;
   while (*hdr_buf.buf != '\0')
diff --git a/edtest.c b/edtest.c
new file mode 100644
index 0000000..daf4dd9
--- /dev/null
+++ b/edtest.c
@@ -0,0 +1,266 @@
+/* edtest.c -- Test for libbacktrace storage allocation stress handling
+   Copyright (C) 2017 Free Software Foundation, Inc.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are
+met:
+
+    (1) Redistributions of source code must retain the above copyright
+    notice, this list of conditions and the following disclaimer.
+
+    (2) Redistributions in binary form must reproduce the above copyright
+    notice, this list of conditions and the following disclaimer in
+    the documentation and/or other materials provided with the
+    distribution.
+
+    (3) The name of the author may not be used to
+    endorse or promote products derived from this software without
+    specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
+INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
+IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+POSSIBILITY OF SUCH DAMAGE.  */
+
+#include "config.h"
+
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/types.h>
+
+#include "backtrace.h"
+#include "backtrace-supported.h"
+#include "internal.h"
+
+#if defined(__MSDOS__) || defined(_WIN32) || defined(__OS2__) ||
defined (__CYGWIN__)
+# define IS_DIR_SEPARATOR(c) ((c) == '/' || (c) == '\\')
+#else
+# define IS_DIR_SEPARATOR(c) ((c) == '/')
+#endif
+
+/* The backtrace state.  */
+
+static void *state;
+
+/* The number of failures.  */
+
+int failures = 0;
+
+static int test1 (void) __attribute__ ((noinline, unused));
+static int test1 (void) __attribute__ ((noinline, unused));
+extern int f2 (int);
+extern int f3 (int, int);
+
+static int
+test1 (void)
+{
+  /* Returning a value here and elsewhere avoids a tailcall which
+     would mess up the backtrace.  */
+  return f2 (__LINE__) + 1;
+}
+
+/* Used to collect backtrace info.  */
+
+struct info
+{
+  char *filename;
+  int lineno;
+  char *function;
+};
+
+/* Return the base name in a path.  */
+
+static const char *
+base (const char *p)
+{
+  const char *last;
+  const char *s;
+
+  last = NULL;
+  for (s = p; *s != '\0'; ++s)
+    {
+      if (IS_DIR_SEPARATOR (*s))
+        last = s + 1;
+    }
+  return last != NULL ? last : p;
+}
+
+/* Check an entry in a struct info array.  */
+
+static void
+check (const char *name, int index, const struct info *all, int want_lineno,
+       const char *want_function, const char *want_file, int *failed)
+{
+  if (*failed)
+    return;
+  if (all[index].filename == NULL || all[index].function == NULL)
+    {
+      fprintf (stderr, "%s: [%d]: missing file name or function name\n",
+               name, index);
+      *failed = 1;
+      return;
+    }
+  if (strcmp (base (all[index].filename), want_file) != 0)
+    {
+      fprintf (stderr, "%s: [%d]: got %s expected %s\n", name, index,
+               all[index].filename, want_file);
+      *failed = 1;
+    }
+  if (all[index].lineno != want_lineno)
+    {
+      fprintf (stderr, "%s: [%d]: got %d expected %d\n", name, index,
+               all[index].lineno, want_lineno);
+      *failed = 1;
+    }
+  if (strcmp (all[index].function, want_function) != 0)
+    {
+      fprintf (stderr, "%s: [%d]: got %s expected %s\n", name, index,
+               all[index].function, want_function);
+      *failed = 1;
+    }
+}
+
+/* Passed to backtrace callback function.  */
+
+struct bdata
+{
+  struct info *all;
+  size_t index;
+  size_t max;
+  int failed;
+};
+
+/* An error callback passed to backtrace.  */
+
+static void
+error_callback_one (void *vdata, const char *msg, int errnum)
+{
+  struct bdata *data = (struct bdata *) vdata;
+
+  fprintf (stderr, "%s", msg);
+  if (errnum > 0)
+    fprintf (stderr, ": %s", strerror (errnum));
+  fprintf (stderr, "\n");
+  data->failed = 1;
+}
+
+/* The backtrace callback function.  */
+
+static int
+callback_one (void *vdata, uintptr_t pc ATTRIBUTE_UNUSED,
+              const char *filename, int lineno, const char *function)
+{
+  struct bdata *data = (struct bdata *) vdata;
+  struct info *p;
+
+  if (data->index >= data->max)
+    {
+      fprintf (stderr, "callback_one: callback called too many times\n");
+      data->failed = 1;
+      return 1;
+    }
+
+  p = &data->all[data->index];
+  if (filename == NULL)
+    p->filename = NULL;
+  else
+    {
+      p->filename = strdup (filename);
+      assert (p->filename != NULL);
+    }
+  p->lineno = lineno;
+  if (function == NULL)
+    p->function = NULL;
+  else
+    {
+      p->function = strdup (function);
+      assert (p->function != NULL);
+    }
+  ++data->index;
+
+  return 0;
+}
+
+int
+f3 (int f1line, int f2line)
+{
+  struct info all[20];
+  struct bdata data;
+  int f3line;
+  int i;
+
+  data.all = &all[0];
+  data.index = 0;
+  data.max = 20;
+  data.failed = 0;
+
+  f3line = __LINE__ + 1;
+  i = backtrace_full (state, 0, callback_one, error_callback_one, &data);
+
+  if (i != 0)
+    {
+      fprintf (stderr, "test1: unexpected return value %d\n", i);
+      data.failed = 1;
+    }
+
+  if (data.index < 3)
+    {
+      fprintf (stderr,
+               "test1: not enough frames; got %zu, expected at least 3\n",
+               data.index);
+      data.failed = 1;
+    }
+
+  check ("test1", 0, all, f3line, "f3", "edtest.c", &data.failed);
+  check ("test1", 1, all, f2line, "f2", "edtest2_build.c", &data.failed);
+  check ("test1", 2, all, f1line, "test1", "edtest.c", &data.failed);
+
+  printf ("%s: backtrace_full alloc stress\n", data.failed ? "FAIL" : "PASS");
+
+  if (data.failed)
+    ++failures;
+
+  return failures;
+}
+
+static void
+error_callback_create (void *data ATTRIBUTE_UNUSED, const char *msg,
+                       int errnum)
+{
+  fprintf (stderr, "%s", msg);
+  if (errnum > 0)
+    fprintf (stderr, ": %s", strerror (errnum));
+  fprintf (stderr, "\n");
+  exit (EXIT_FAILURE);
+}
+
+int
+main (int argc ATTRIBUTE_UNUSED, char **argv ATTRIBUTE_UNUSED)
+{
+  state = backtrace_create_state (argv[0], BACKTRACE_SUPPORTS_THREADS,
+                                  error_callback_create, NULL);
+
+  // Grab the storage allocation lock prior to doing anything interesting.
+  // The intent here is to insure that the backtrace_alloc code is forced
+  // to always call mmap() for new memory as opposed to reusing previously
+  // allocated memory from the free list. Doing things this way helps
+  // simulate what you might see in a multithreaded program in which there
+  // are racing calls to the allocator.
+  struct backtrace_state *state_internal =
+      (struct backtrace_state *) state;
+  state_internal->lock_alloc = 1;
+
+  // Kick off the test
+  test1();
+
+  exit (failures > 0 ? EXIT_FAILURE : EXIT_SUCCESS);
+}
diff --git a/edtest2.c b/edtest2.c
new file mode 100644
index 0000000..1ab78ee
--- /dev/null
+++ b/edtest2.c
@@ -0,0 +1,43 @@
+/* edtest2.c -- Test for libbacktrace storage allocation stress handling (p2)
+   Copyright (C) 2017 Free Software Foundation, Inc.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are
+met:
+
+    (1) Redistributions of source code must retain the above copyright
+    notice, this list of conditions and the following disclaimer.
+
+    (2) Redistributions in binary form must reproduce the above copyright
+    notice, this list of conditions and the following disclaimer in
+    the documentation and/or other materials provided with the
+    distribution.
+
+    (3) The name of the author may not be used to
+    endorse or promote products derived from this software without
+    specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
+INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
+IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+POSSIBILITY OF SUCH DAMAGE.  */
+
+/* This file intentionally written without any #include's
+ */
+
+extern int f3(int, int);
+extern int f2(int);
+
+int f2(int x)
+{
+  /* Returning a value here and elsewhere avoids a tailcall which
+     would mess up the backtrace.  */
+  return f3(x, __LINE__) + 3;
+}
diff --git a/mvifdiff.sh b/mvifdiff.sh
new file mode 100755
index 0000000..976f282
--- /dev/null
+++ b/mvifdiff.sh
@@ -0,0 +1,15 @@
+#!/bin/sh
+
+# Copyright (C) 2017 Free Software Foundation, Inc. All rights reserved.
+# Use of this source code is governed by a
+# license that can be found in the LICENSE file.
+
+# The mvifdiff.sh script works like the mv(1) command, except
+# that it does not touch the destination file if its contents
+# are the same as the source file.
+
+if cmp -s "$1" "$2" ; then
+  rm "$1"
+else
+  mv "$1" "$2"
+fi


On Fri, May 12, 2017 at 9:30 AM, Than McIntosh <thanm@google.com> wrote:
> Hello,
>
> The attached patch to libbacktrace is intended to fix a memory
> allocation bug involving reading of line table information.
>
> The scenario of interest takes place when libbacktrace reads a DWARF
> line table whose directory count is zero (an unusual case). If the
> memory allocator invocation triggers a call to mmap, this can cause
> the size passed to mmap to be zero, resulting in an EINVAL error.  The
> fix is to detect the zero-directory case and avoid invoking the
> allocation helper with a zero size.
>
> Questions + comments welcome.
>
> Thanks, Than
>

Re: libbacktrace patch: fix memory allocation buglet on DWARF line table with zero dirs

[Ian Lance Taylor via gcc-patches]

On Fri, May 19, 2017 at 6:18 AM, Than McIntosh <thanm@google.com> wrote:
>
> I wrote:
> == The attached patch to libbacktrace is intended to fix a memory
> == allocation bug involving reading of line table information.
>
> I've revised my previous patch to include a new test ("edtest") that
> verifies the fix.

Thanks.

I changed the use of mvifdiff to use ../move-if-change.  (We use
mvifdiff in libgo to make it less dependent on GCC infrastructure.)

Committed to mainline.

Ian