On Tue, Mar 4, 2014 at 7:34 PM, Ian Lance Taylor <i...@google.com> wrote:
> 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.
I've committed this patch as follows. It's pretty much the same but I
tweaked the sort to use explicit tail recursion, and to do the
non-tail recursion for the smaller part of the array. This limits the
function call depth to the log of the size of the array.
Ian
2014-03-06 Ian Lance Taylor <i...@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: stest.c
===================================================================
--- stest.c (revision 0)
+++ stest.c (revision 0)
@@ -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);
+}
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: ChangeLog
===================================================================
--- ChangeLog (revision 208327)
+++ ChangeLog (working copy)
@@ -1,3 +1,16 @@
+2014-03-04 Ian Lance Taylor <i...@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 <mi...@brew.sh>
PR target/58710
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,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;
+ }
+}
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
