Patch RFC: Use internal qsort function in libbacktrace

[Ian Lance Taylor <iant at google dot com>]

The GNU glibc qsort function will call malloc in some cases.  That makes
it unsuitable for libbacktrace, which is intended to work when called
from a signal handler.  This patch changes libbacktrace to use an
internal qsort function.

I'm posting this for comments in case anybody sees anything wrong with
the implementation.  I'll commit it in a day or two if I don't hear
anything.

Bootstrapped and ran libbacktrace and Go tests on
x86_64-unknown-linux-gnu.

Ian


2014-03-04  Ian Lance Taylor  <iant@google.com>

	* sort.c: New file.
	* stest.c: New file.
	* internal.h (backtrace_qsort): Declare.
	* dwarf.c (read_abbrevs): Call backtrace_qsort instead of qsort.
	(read_line_info, read_function_entry): Likewise.
	(read_function_info, build_dwarf_data): Likewise.
	* elf.c (elf_initialize_syminfo): Likewise.
	* Makefile.am (libbacktrace_la_SOURCES): Add sort.c.
	(stest_SOURCES, stest_LDADD): Define.
	(check_PROGRAMS): Add stest.


Index: dwarf.c
===================================================================
--- dwarf.c	(revision 208327)
+++ dwarf.c	(working copy)
@@ -1134,8 +1134,8 @@ read_abbrevs (struct backtrace_state *st
       ++num_abbrevs;
     }
 
-  qsort (abbrevs->abbrevs, abbrevs->num_abbrevs, sizeof (struct abbrev),
-	 abbrev_compare);
+  backtrace_qsort (abbrevs->abbrevs, abbrevs->num_abbrevs,
+		   sizeof (struct abbrev), abbrev_compare);
 
   return 1;
 
@@ -2016,7 +2016,7 @@ read_line_info (struct backtrace_state *
     goto fail;
 
   ln = (struct line *) vec.vec.base;
-  qsort (ln, vec.count, sizeof (struct line), line_compare);
+  backtrace_qsort (ln, vec.count, sizeof (struct line), line_compare);
 
   *lines = ln;
   *lines_count = vec.count;
@@ -2476,9 +2476,9 @@ read_function_entry (struct backtrace_st
 		    return 0;
 
 		  faddrs = (struct function_addrs *) fvec.vec.base;
-		  qsort (faddrs, fvec.count,
-			 sizeof (struct function_addrs),
-			 function_addrs_compare);
+		  backtrace_qsort (faddrs, fvec.count,
+				   sizeof (struct function_addrs),
+				   function_addrs_compare);
 
 		  function->function_addrs = faddrs;
 		  function->function_addrs_count = fvec.count;
@@ -2555,8 +2555,8 @@ read_function_info (struct backtrace_sta
       fvec->count = 0;
     }
 
-  qsort (addrs, addrs_count, sizeof (struct function_addrs),
-	 function_addrs_compare);
+  backtrace_qsort (addrs, addrs_count, sizeof (struct function_addrs),
+		   function_addrs_compare);
 
   *ret_addrs = addrs;
   *ret_addrs_count = addrs_count;
@@ -2923,7 +2923,8 @@ build_dwarf_data (struct backtrace_state
     return NULL;
   addrs = (struct unit_addrs *) addrs_vec.vec.base;
   addrs_count = addrs_vec.count;
-  qsort (addrs, addrs_count, sizeof (struct unit_addrs), unit_addrs_compare);
+  backtrace_qsort (addrs, addrs_count, sizeof (struct unit_addrs),
+		   unit_addrs_compare);
 
   fdata = ((struct dwarf_data *)
 	   backtrace_alloc (state, sizeof (struct dwarf_data),
Index: elf.c
===================================================================
--- elf.c	(revision 208327)
+++ elf.c	(working copy)
@@ -407,8 +407,8 @@ elf_initialize_syminfo (struct backtrace
       ++j;
     }
 
-  qsort (elf_symbols, elf_symbol_count, sizeof (struct elf_symbol),
-	 elf_symbol_compare);
+  backtrace_qsort (elf_symbols, elf_symbol_count, sizeof (struct elf_symbol),
+		   elf_symbol_compare);
 
   sdata->next = NULL;
   sdata->symbols = elf_symbols;
Index: internal.h
===================================================================
--- internal.h	(revision 208327)
+++ internal.h	(working copy)
@@ -196,6 +196,11 @@ extern int backtrace_close (int descript
 			    backtrace_error_callback error_callback,
 			    void *data);
 
+/* Sort without using memory.  */
+
+extern void backtrace_qsort (void *base, size_t count, size_t size,
+			     int (*compar) (const void *, const void *));
+
 /* Allocate memory.  This is like malloc.  */
 
 extern void *backtrace_alloc (struct backtrace_state *state, size_t size,
Index: sort.c
===================================================================
--- sort.c	(revision 0)
+++ sort.c	(revision 0)
@@ -0,0 +1,87 @@
+/* sort.c -- Sort without allocating memory
+   Copyright (C) 2012-2014 Free Software Foundation, Inc.
+   Written by Ian Lance Taylor, Google.
+
+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 <stddef.h>
+#include <sys/types.h>
+
+#include "backtrace.h"
+#include "internal.h"
+
+/* The GNU glibc version of qsort allocates memory, which we must not
+   do if we are invoked by a signal handler.  So provide our own
+   sort.  */
+
+static void
+swap (char *a, char *b, size_t size)
+{
+  size_t i;
+
+  for (i = 0; i < size; i++, a++, b++)
+    {
+      char t;
+
+      t = *a;
+      *a = *b;
+      *b = t;
+    }
+}
+
+void
+backtrace_qsort (void *basearg, size_t count, size_t size,
+		 int (*compar) (const void *, const void *))
+{
+  char *base = (char *) basearg;
+  size_t i;
+  size_t mid;
+
+  if (count < 2)
+    return;
+
+  mid = 0;
+  for (i = 1; i < count; i++)
+    {
+      if ((*compar) (base, base + i * size) > 0)
+	{
+	  ++mid;
+	  if (i != mid)
+	    swap (base + mid * size, base + i * size, size);
+	}
+    }
+
+  if (mid > 0)
+    swap (base, base + mid * size, size);
+
+  backtrace_qsort (base, mid, size, compar);
+  backtrace_qsort (base + (mid + 1) * size, count - (mid + 1), size, compar);
+}
Index: Makefile.am
===================================================================
--- Makefile.am	(revision 208327)
+++ Makefile.am	(working copy)
@@ -46,6 +46,7 @@ libbacktrace_la_SOURCES = \
 	internal.h \
 	posix.c \
 	print.c \
+	sort.c \
 	state.c
 
 BACKTRACE_FILES = \
@@ -93,6 +94,11 @@ btest_LDADD = libbacktrace.la
 
 check_PROGRAMS += btest
 
+stest_SOURCES = stest.c
+stest_LDADD = libbacktrace.la
+
+check_PROGRAMS += stest
+
 endif NATIVE
 
 # We can't use automake's automatic dependency tracking, because it
Index: stest.c
===================================================================
--- stest.c	(revision 0)
+++ stest.c	(revision 0)
@@ -0,0 +1,137 @@
+/* btest.c -- Test for libbacktrace library
+   Copyright (C) 2012-2014 Free Software Foundation, Inc.
+   Written by Ian Lance Taylor, Google.
+
+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 <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/types.h>
+
+#include "backtrace.h"
+#include "internal.h"
+
+/* Test the local qsort implementation.  */
+
+#define MAX 10
+
+struct test
+{
+  size_t count;
+  int input[MAX];
+  int output[MAX];
+};
+
+static struct test tests[] =
+  {
+    {
+      10,
+      { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 },
+      { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
+    },
+    {
+      9,
+      { 1, 2, 3, 4, 5, 6, 7, 8, 9 },
+      { 1, 2, 3, 4, 5, 6, 7, 8, 9 }
+    },
+    {
+      10,
+      { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 },
+      { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 },
+    },
+    {
+      9,
+      { 9, 8, 7, 6, 5, 4, 3, 2, 1 },
+      { 1, 2, 3, 4, 5, 6, 7, 8, 9 },
+    },
+    {
+      10,
+      { 2, 4, 6, 8, 10, 1, 3, 5, 7, 9 },
+      { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 },
+    },
+    {
+      5,
+      { 4, 5, 3, 1, 2 },
+      { 1, 2, 3, 4, 5 },
+    },
+    {
+      5,
+      { 1, 1, 1, 1, 1 },
+      { 1, 1, 1, 1, 1 },
+    },
+    {
+      5,
+      { 1, 1, 2, 1, 1 },
+      { 1, 1, 1, 1, 2 },
+    },
+    {
+      5,
+      { 2, 1, 1, 1, 1 },
+      { 1, 1, 1, 1, 2 },
+    },
+  };
+
+static int
+compare (const void *a, const void *b)
+{
+  const int *ai = (const int *) a;
+  const int *bi = (const int *) b;
+
+  return *ai - *bi;
+}
+
+int
+main (int argc ATTRIBUTE_UNUSED, char **argv ATTRIBUTE_UNUSED)
+{
+  int failures;
+  size_t i;
+  int a[MAX];
+
+  failures = 0;
+  for (i = 0; i < sizeof tests / sizeof tests[0]; i++)
+    {
+      memcpy (a, tests[i].input, tests[i].count * sizeof (int));
+      backtrace_qsort (a, tests[i].count, sizeof (int), compare);
+      if (memcmp (a, tests[i].output, tests[i].count * sizeof (int)) != 0)
+	{
+	  size_t j;
+
+	  fprintf (stderr, "test %d failed:", (int) i);
+	  for (j = 0; j < tests[i].count; j++)
+	    fprintf (stderr, " %d", a[j]);
+	  fprintf (stderr, "\n");
+	  ++failures;
+	}
+    }
+
+  exit (failures > 0 ? EXIT_FAILURE : EXIT_SUCCESS);
+}