From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1791) id AB620385AC0A; Mon, 6 Sep 2021 18:44:37 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org AB620385AC0A Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: Adhemerval Zanella To: glibc-cvs@sourceware.org Subject: [glibc/azanella/qsort-fixes] stdlib: Add more qsort{_r} coverage X-Act-Checkin: glibc X-Git-Author: Adhemerval Zanella X-Git-Refname: refs/heads/azanella/qsort-fixes X-Git-Oldrev: b8c6166b1b75036ab3e4127a1c0aacf52ca93651 X-Git-Newrev: de255ac5b5d1d0d63405d2fa47e7d364c6bcad61 Message-Id: <20210906184437.AB620385AC0A@sourceware.org> Date: Mon, 6 Sep 2021 18:44:37 +0000 (GMT) X-BeenThere: glibc-cvs@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Glibc-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 06 Sep 2021 18:44:37 -0000 https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=de255ac5b5d1d0d63405d2fa47e7d364c6bcad61 commit de255ac5b5d1d0d63405d2fa47e7d364c6bcad61 Author: Adhemerval Zanella Date: Mon Jan 15 09:20:30 2018 -0200 stdlib: Add more qsort{_r} coverage This patch adds a qsort and qsort_r (which glibc current lacks coverage). The test is done with random input (created using support random), different internal types (uint8_t, uint16_t, uint32_t, and uint64_t), and with different set of element numbers (from 0 to 262144). Checked on x86_64-linux-gnu. Diff: --- stdlib/Makefile | 2 +- stdlib/tst-qsort-common.c | 285 ++++++++++++++++++++++++++++++++++++++++++++++ stdlib/tst-qsort3.c | 138 ++++++++++++++++++++++ 3 files changed, 424 insertions(+), 1 deletion(-) diff --git a/stdlib/Makefile b/stdlib/Makefile index 7c15549caf..ef8a9007d8 100644 --- a/stdlib/Makefile +++ b/stdlib/Makefile @@ -88,7 +88,7 @@ tests := tst-strtol tst-strtod testmb testrand testsort testdiv \ tst-swapcontext1 tst-setcontext4 tst-setcontext5 \ tst-setcontext6 tst-setcontext7 tst-setcontext8 \ tst-setcontext9 tst-bz20544 tst-canon-bz26341 \ - tst-realpath + tst-realpath tst-qsort3 tests-internal := tst-strtod1i tst-strtod3 tst-strtod4 tst-strtod5i \ tst-tls-atexit tst-tls-atexit-nodelete diff --git a/stdlib/tst-qsort-common.c b/stdlib/tst-qsort-common.c new file mode 100644 index 0000000000..9ab8f91618 --- /dev/null +++ b/stdlib/tst-qsort-common.c @@ -0,0 +1,285 @@ +/* Common definition for qsort testing/benchmark. + Copyright (C) 2021 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +#include +#include +#include +#include +#include +#include + +/* Type of inputs arrays: + - SORTED: array already sorted in placed. + - MOSTLYSORTED: sorted array with 'MOSTLY_SORTED_RATIO * size' elements + in random positions set to random values. + - RANDOM: all elements in array set to random values. + - REPEATED: random array with 'RepeatedRation' elements in random + positions set to an unique value. + - BITONIC: strictly increasing to up middle then strictly + decreasing. */ +typedef enum +{ + SORTED, + MOSTLYSORTED, + RANDOM, + REPEATED, + BITONIC +} arraytype_t; + +struct array_t +{ + arraytype_t type; + const char *name; + }; +static const struct array_t arraytypes[] = +{ + { SORTED, "SORTED" }, + { MOSTLYSORTED, "MOSTLYSORTED" }, + { RANDOM, "RANDOM" }, + { REPEATED, "REPEATED" }, + { BITONIC, "BITONIC" }, +}; + +/* Ratio of total of elements which will randomized. */ +#define MOSTLY_SORTED_RATIO (0.2) + +/* Ratio of total of elements which will be repeated. */ +#define REPEATED_RATIO (0.2) + +/* Return the index of BASE as interpreted as an array of elements + of size SIZE. */ +static inline void * +arr (void *base, size_t idx, size_t size) +{ + return (void*)((uintptr_t)base + (idx * size)); +} + +/* Functions used to check qsort. */ +static int +uint8_t_cmp (const void *a, const void *b) +{ + uint8_t ia = *(uint8_t*)a; + uint8_t ib = *(uint8_t*)b; + return (ia > ib) - (ia < ib); +} + +static int +uint16_t_cmp (const void *a, const void *b) +{ + uint16_t ia = *(uint16_t*)a; + uint16_t ib = *(uint16_t*)b; + return (ia > ib) - (ia < ib); +} + +static int +uint32_t_cmp (const void *a, const void *b) +{ + uint32_t ia = *(uint32_t*)a; + uint32_t ib = *(uint32_t*)b; + return (ia > ib) - (ia < ib); +} + +static int +uint64_t_cmp (const void *a, const void *b) +{ + uint64_t ia = *(uint64_t*)a; + uint64_t ib = *(uint64_t*)b; + return (ia > ib) - (ia < ib); +} + +/* Function used to check qsort_r. */ +typedef enum +{ + UINT8_CMP_T, + UINT16_CMP_T, + UINT32_CMP_T, + UINT64_CMP_T +} type_cmp_t; + +static type_cmp_t +__attribute__((used)) +uint_t_cmp_type (size_t sz) +{ + switch (sz) + { + case sizeof (uint8_t): return UINT8_CMP_T; + case sizeof (uint16_t): return UINT16_CMP_T; + case sizeof (uint64_t): return UINT64_CMP_T; + case sizeof (uint32_t): + default: return UINT32_CMP_T; + } +} + +static int +__attribute__((used)) +uint_t_cmp (const void *a, const void *b, void *arg) +{ + type_cmp_t type = *(type_cmp_t*) arg; + switch (type) + { + case UINT8_CMP_T: return uint8_t_cmp (a, b); + case UINT16_CMP_T: return uint16_t_cmp (a, b); + case UINT64_CMP_T: return uint64_t_cmp (a, b); + case UINT32_CMP_T: + default: return uint32_t_cmp (a, b); + } +} + +static void +seq (void *elem, size_t type_size, uint64_t value) +{ + if (type_size == sizeof (uint8_t)) + { + uint8_t x = value; + memcpy (elem, &x, type_size); + } + else if (type_size == sizeof (uint16_t)) + { + uint16_t x = value; + memcpy (elem, &x, type_size); + } + else if (type_size == sizeof (uint32_t)) + { + uint32_t x = value; + memcpy (elem, &x, type_size); + } + else if (type_size == sizeof (uint64_t)) + memcpy (elem, &value, type_size); + else + memset (elem, value, type_size); +} + +static void +random_init (void) +{ + unsigned short seed16v[3]; + if (getrandom (seed16v, sizeof seed16v, 0) == -1) + srand (time (NULL)); + else + seed48 (seed16v); +} + +static uint32_t +random_uniform_distribution (uint32_t min, uint32_t max) +{ + uint32_t ret; + uint32_t range = max - min; + /* It assumes the input random number RANDOM range is as larger or equal + than the RANGE, so the result will either returned or downscaled. */ + if (range != UINT32_MAX) + { + uint32_t urange = range + 1; /* range can be 0. */ + uint32_t scaling = UINT32_MAX / urange; + uint32_t past = urange * scaling; + do + ret = lrand48 (); + while (ret >= past); + ret /= scaling; + } + else + ret = lrand48 (); + return ret + min; +} + +void +random_buf (void *buf, size_t nbytes) +{ + size_t nw = nbytes / sizeof (uint32_t); + for (size_t i = 0; i < nw; i++) + { + uint32_t r = lrand48 (); + memcpy (buf, &r, sizeof (uint32_t)); + buf = (void*)((uintptr_t)buf + sizeof (uint32_t)); + } + + size_t nb = nbytes % sizeof (uint32_t); + if (nb != 0) + { + uint32_t r = lrand48 (); + memcpy (buf, &r, nb); + } +} + +static void * +create_array (size_t nmemb, size_t type_size, arraytype_t type) +{ + size_t size = nmemb * type_size; + void *array = xmalloc (size); + + switch (type) + { + case SORTED: + for (uint64_t i = 0; i < nmemb; i++) + seq (arr (array, i, type_size), type_size, i); + break; + + case MOSTLYSORTED: + { + for (uint64_t i = 0; i < nmemb; i++) + seq (arr (array, i, type_size), type_size, i); + + /* Change UNSORTED elements (based on MostlySortedRatio ratio) + in the sorted array. */ + size_t unsorted = (size_t)(nmemb * MOSTLY_SORTED_RATIO); + for (size_t i = 0; i < unsorted; i++) + { + size_t pos = random_uniform_distribution (0, nmemb - 1); + random_buf (arr (array, pos, type_size), type_size); + } + } + break; + + case RANDOM: + random_buf (array, size); + break; + + case REPEATED: + { + random_buf (array, size); + + void *randelem = xmalloc (type_size); + random_buf (randelem, type_size); + + /* Repeat REPEATED elements (based on RepeatRatio ratio) in the random + array. */ + size_t repeated = (size_t)(nmemb * REPEATED_RATIO); + for (size_t i = 0; i < repeated; i++) + { + size_t pos = random_uniform_distribution (0, nmemb - 1); + memcpy (arr (array, pos, type_size), randelem, type_size); + } + + free (randelem); + } + break; + + case BITONIC: + { + uint64_t i; + for (i = 0; i < nmemb / 2; i++) + seq (arr (array, i, type_size), type_size, i); + for ( ; i < nmemb; i++) + seq (arr (array, i, type_size), type_size, (nmemb - 1) - i); + } + break; + } + + return array; +} + +typedef int (*cmpfunc_t)(const void *, const void *); diff --git a/stdlib/tst-qsort3.c b/stdlib/tst-qsort3.c new file mode 100644 index 0000000000..d946f37c9d --- /dev/null +++ b/stdlib/tst-qsort3.c @@ -0,0 +1,138 @@ +/* qsorte if (type_size == sizeof (uint32_t)) + _r) generic tests. + Copyright (C) 2021 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +#include +#include +#include +#include +#include +#include +#include +#include + +#include + +/* Check if ARRAY of total NMEMB element of size SIZE is sorted + based on CMPFUNC. */ +static void +check_array (void *array, size_t nmemb, size_t type_size, + cmpfunc_t cmpfunc) +{ + for (size_t i = 1; i < nmemb; i++) + { + int ret = cmpfunc (arr (array, i, type_size), + arr (array, i-1, type_size)); + TEST_VERIFY_EXIT (ret >= 0); + } +} + +static void +check_qsort (size_t nelem, size_t type_size, arraytype_t type, + cmpfunc_t cmpfunc) +{ + void *array = create_array (nelem, type_size, type); + + qsort (array, nelem, type_size, cmpfunc); + + check_array (array, nelem, type_size, cmpfunc); + + free (array); +} + +static void +check_qsort_r (size_t nelem, size_t type_size, arraytype_t type, + cmpfunc_t cmpfunc) +{ + void *array = create_array (nelem, type_size, type); + + type_cmp_t typecmp = uint_t_cmp_type (type_size); + qsort_r (array, nelem, type_size, uint_t_cmp, &typecmp); + + check_array (array, nelem, type_size, cmpfunc); + + free (array); +} + +static int +do_test (void) +{ + random_init (); + + struct test_t + { + size_t type_size; + cmpfunc_t cmpfunc; + }; + static const struct test_t tests[] = + { + { sizeof (uint8_t), uint8_t_cmp }, + { sizeof (uint16_t), uint16_t_cmp }, + { sizeof (uint32_t), uint32_t_cmp }, + { sizeof (uint64_t), uint64_t_cmp }, + /* Test swap with large elements. */ + { 32, uint32_t_cmp }, + }; + + struct array_t + { + arraytype_t type; + const char *name; + }; + static const struct array_t arraytypes[] = + { + { SORTED, "SORTED" }, + { MOSTLYSORTED, "MOSTLYSORTED" }, + { RANDOM, "RANDOM" }, + { REPEATED, "REPEATED" }, + { BITONIC, "BITONIC" }, + }; + + static const size_t nelems[] = + { 0, 1, 16, 32, 64, 128, 256, 4096, 16384, 262144 }; + + for (const struct test_t *test = tests; test < array_end (tests); ++test) + { + if (test_verbose > 0) + printf ("info: testing qsort with type_size=%zu\n", test->type_size); + for (const struct array_t *arraytype = arraytypes; + arraytype < array_end (arraytypes); + ++arraytype) + { + if (test_verbose > 0) + printf (" distribution=%s\n", arraytype->name); + for (const size_t *nelem = nelems; + nelem < array_end (nelems); + ++nelem) + { + if (test_verbose > 0) + printf (" i nelem=%zu, total size=%zu\n", *nelem, + *nelem * test->type_size); + + check_qsort (*nelem, test->type_size, arraytype->type, + test->cmpfunc); + check_qsort_r (*nelem, test->type_size, arraytype->type, + test->cmpfunc); + } + } + } + + return 0; +} + +#include