* 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.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@208392 138bc75d-0d04-0410-961f-82ee72b054a4

8 files changed, 288 insertions, 15 deletions

diff --git a/libbacktrace/ChangeLog b/libbacktrace/ChangeLog
index 5ad616228e49..abbea3ed6e8b 100644
--- a/libbacktrace/ChangeLog
+++ b/libbacktrace/ChangeLog
@@ -1,3 +1,16 @@
+2014-03-06  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.
+
 2014-02-07  Misty De Meo  <misty@brew.sh>
 
 	PR target/58710
diff --git a/libbacktrace/Makefile.am b/libbacktrace/Makefile.am
index 6add85d73415..ab1a6b32b5e0 100644
--- a/libbacktrace/Makefile.am
+++ b/libbacktrace/Makefile.am
@@ -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
diff --git a/libbacktrace/Makefile.in b/libbacktrace/Makefile.in
index 18c1ecaca545..f2821fc15262 100644
--- a/libbacktrace/Makefile.in
+++ b/libbacktrace/Makefile.in
@@ -67,7 +67,7 @@ build_triplet = @build@
 host_triplet = @host@
 target_triplet = @target@
 check_PROGRAMS = $(am__EXEEXT_1)
-@NATIVE_TRUE@am__append_1 = btest
+@NATIVE_TRUE@am__append_1 = btest stest
 subdir = .
 DIST_COMMON = README ChangeLog $(srcdir)/Makefile.in \
 	$(srcdir)/Makefile.am $(top_srcdir)/configure \
@@ -94,15 +94,18 @@ CONFIG_CLEAN_VPATH_FILES =
 LTLIBRARIES = $(noinst_LTLIBRARIES)
 am__DEPENDENCIES_1 =
 am_libbacktrace_la_OBJECTS = atomic.lo dwarf.lo fileline.lo posix.lo \
-	print.lo state.lo
+	print.lo sort.lo state.lo
 libbacktrace_la_OBJECTS = $(am_libbacktrace_la_OBJECTS)
-@NATIVE_TRUE@am__EXEEXT_1 = btest$(EXEEXT)
+@NATIVE_TRUE@am__EXEEXT_1 = btest$(EXEEXT) stest$(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_stest_OBJECTS = stest.$(OBJEXT)
+stest_OBJECTS = $(am_stest_OBJECTS)
+@NATIVE_TRUE@stest_DEPENDENCIES = libbacktrace.la
 DEFAULT_INCLUDES = -I.@am__isrc@
 depcomp =
 am__depfiles_maybe =
@@ -116,7 +119,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)
+	$(btest_SOURCES) $(stest_SOURCES)
 MULTISRCTOP = 
 MULTIBUILDTOP = 
 MULTIDIRS = 
@@ -264,6 +267,7 @@ libbacktrace_la_SOURCES = \
 	internal.h \
 	posix.c \
 	print.c \
+	sort.c \
 	state.c
 
 BACKTRACE_FILES = \
@@ -300,6 +304,8 @@ TESTS = $(check_PROGRAMS)
 @NATIVE_TRUE@btest_SOURCES = btest.c
 @NATIVE_TRUE@btest_CFLAGS = $(AM_CFLAGS) -g -O
 @NATIVE_TRUE@btest_LDADD = libbacktrace.la
+@NATIVE_TRUE@stest_SOURCES = stest.c
+@NATIVE_TRUE@stest_LDADD = libbacktrace.la
 
 # We can't use automake's automatic dependency tracking, because it
 # breaks when using bootstrap-lean.  Automatic dependency tracking
@@ -394,6 +400,9 @@ clean-checkPROGRAMS:
 btest$(EXEEXT): $(btest_OBJECTS) $(btest_DEPENDENCIES) 
 	@rm -f btest$(EXEEXT)
 	$(btest_LINK) $(btest_OBJECTS) $(btest_LDADD) $(LIBS)
+stest$(EXEEXT): $(stest_OBJECTS) $(stest_DEPENDENCIES) 
+	@rm -f stest$(EXEEXT)
+	$(LINK) $(stest_OBJECTS) $(stest_LDADD) $(LIBS)
 
 mostlyclean-compile:
 	-rm -f *.$(OBJEXT)
diff --git a/libbacktrace/dwarf.c b/libbacktrace/dwarf.c
index ad52d73b752e..143bb280f5f8 100644
--- a/libbacktrace/dwarf.c
+++ b/libbacktrace/dwarf.c
@@ -1134,8 +1134,8 @@ read_abbrevs (struct backtrace_state *state, uint64_t abbrev_offset,
       ++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 *state, struct dwarf_data *ddata,
     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_state *state, struct dwarf_data *ddata,
 		    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_state *state, struct dwarf_data *ddata,
       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 *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),
diff --git a/libbacktrace/elf.c b/libbacktrace/elf.c
index 6c5b179e90d0..e63aaf5dbdfe 100644
--- a/libbacktrace/elf.c
+++ b/libbacktrace/elf.c
@@ -407,8 +407,8 @@ elf_initialize_syminfo (struct backtrace_state *state,
       ++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;
diff --git a/libbacktrace/internal.h b/libbacktrace/internal.h
index dd109db24aed..1ae43177f380 100644
--- a/libbacktrace/internal.h
+++ b/libbacktrace/internal.h
@@ -196,6 +196,11 @@ extern int backtrace_close (int descriptor,
 			    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,
diff --git a/libbacktrace/sort.c b/libbacktrace/sort.c
new file mode 100644
index 000000000000..88f923142247
--- /dev/null
+++ b/libbacktrace/sort.c
@@ -0,0 +1,102 @@
+/* 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;
+
+ tail_recurse:
+  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);
+
+  /* Recurse with the smaller array, loop with the larger one.  That
+     ensures that our maximum stack depth is log count.  */
+  if (2 * mid < count)
+    {
+      backtrace_qsort (base, mid, size, compar);
+      base += (mid + 1) * size;
+      count -= mid + 1;
+      goto tail_recurse;
+    }
+  else
+    {
+      backtrace_qsort (base + (mid + 1) * size, count - (mid + 1),
+		       size, compar);
+      count = mid;
+      goto tail_recurse;
+    }
+}
diff --git a/libbacktrace/stest.c b/libbacktrace/stest.c
new file mode 100644
index 000000000000..5676745547d8
--- /dev/null
+++ b/libbacktrace/stest.c
@@ -0,0 +1,137 @@
+/* stest.c -- Test for libbacktrace internal sort function
+   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);
+}