From c5604b48f91fa510171faf5a6e9d4138799186f1 Mon Sep 17 00:00:00 2001 From: Ian Lance Taylor Date: Fri, 7 Mar 2014 05:07:56 +0000 Subject: [PATCH] sort.c: New file. * 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. From-SVN: r208392 --- libbacktrace/ChangeLog | 13 ++++ libbacktrace/Makefile.am | 6 ++ libbacktrace/Makefile.in | 17 +++-- libbacktrace/dwarf.c | 19 +++--- libbacktrace/elf.c | 4 +- libbacktrace/internal.h | 5 ++ libbacktrace/sort.c | 102 +++++++++++++++++++++++++++++ libbacktrace/stest.c | 137 +++++++++++++++++++++++++++++++++++++++ 8 files changed, 288 insertions(+), 15 deletions(-) create mode 100644 libbacktrace/sort.c create mode 100644 libbacktrace/stest.c 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 + + * 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 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 +#include + +#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 +#include +#include +#include + +#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); +} -- 2.43.0