From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ot1-x329.google.com (mail-ot1-x329.google.com [IPv6:2607:f8b0:4864:20::329]) by sourceware.org (Postfix) with ESMTPS id D75CE3858C78 for ; Mon, 30 Oct 2023 19:05:03 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org D75CE3858C78 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org D75CE3858C78 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::329 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1698692706; cv=none; b=xMVXpvflkkwcpaa0UJy/yDwNfFRq64MQsLUCS+l5FKfIcilH2olHoJL0WAl4pS8Jn50bkUvjPtzqTGbduOFGW3mEMC4qXhbdQ5BNoo6S7v4WrriFr1RWcm62peNsIrEO2aCSWXRL9bPweu/tepvbBZQ2c1Bclf87rXmILQc81IE= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1698692706; c=relaxed/simple; bh=CL26WtYaZ8+bD+3bSxcsGWGqrWSoRDRMd30h949M2n8=; h=DKIM-Signature:MIME-Version:From:Date:Message-ID:Subject:To; b=CHfkwTDWjE+8fN7mEgOgPMSu9H/i/OtqK+Zu86jMzbEodqfxu9nFhGeUxI72uWZb3qVZjIX2f3NurWKlS+WKhHyUfiwzI5xouDbL8pfR1lLWUtghwPL2xwlGye1f3Zvtc2eOhQnt8lKGQr83TSGBNZC9wOkkeOYZzcX3YxB584w= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-ot1-x329.google.com with SMTP id 46e09a7af769-6cd09663b1cso2855584a34.3 for ; Mon, 30 Oct 2023 12:05:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1698692703; x=1699297503; darn=sourceware.org; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=FHJ/EOm3OAwy2P5dmyoBqt1OlweW7Vj7bScdY36+T10=; b=CdN74/hhcNSqlFjE0wdRxiTmJfeWzn2xhQrOG+AJQPBl1nBcNljknI0wahlfwdywHP qPUjPqQIbjn4V7JI9/XDvdS7TCnT3cJlc3HtmJhHabBYXRvvQ2IG0SY3VMH3Fl3C3dnp bUBpgC3PxhZMyFjivOWafJYOWv0MmDXPxEefTZOG8MTWDi8r6oG7Fm7n7lgnTdHRZvUJ I5GfpUXBA2R3YWGEO/oQWS6hSYwaBFkeesB7/wqkmwwOpqCCqtpwjcWrwviVgOFWWAMo zoOyMWsb5Zh/vDqe9eOdX+A2zFfS6qy64YCO16YUrHSzRIwOS97P1QbXpk514bFXYrs8 9OjQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698692703; x=1699297503; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=FHJ/EOm3OAwy2P5dmyoBqt1OlweW7Vj7bScdY36+T10=; b=fK79rwQQ+ft1dw+rq12pehlmDny79/ebiKW+mBQVYsQydM1UDI1WUpiB6dWaiwXOxN DPcwyjjjyxSKxZdkyKCslQ7TnJaN3OupyLncYX9OMkLU7Eu/1g4nYuZR+6OkCmCBpCgp Iq1GFwOkeikFsHV4fhgNg5vjKLcCrwOwVETXJMWBNeNAICQ3dwddK2t6kA4iNfNWCso7 e/SX/hU0ehSQrPkQ9eXuQULmQJhHa0+UMGMC8x7UutFBLDzikTjTOFV116zFVJToZyTA fXXhi5P6gdIiJ3G+h+DnmWt0Nul36oYkC1iPdkky8PKnLB8AXKaPsJ3VtijnYoPnYOee K5VQ== X-Gm-Message-State: AOJu0YwRInnXfA0t+5dKZFDRK2ov7iB+ueZFVNcxlAx8S+C44HYmHIzD G60mR0GeOCNEcIftuAjOqFsSV+X5+tahtudsYtwto+LjTck= X-Google-Smtp-Source: AGHT+IFC8ziEnME9zjN+YXlIXGdk4qsfgZn98Bn0v5U1R4RCQxLElks84qTpAUXFzQxlCHx34/1StiQuuTS2f+Nc+qY= X-Received: by 2002:a05:6871:a509:b0:1e9:bd5c:ae38 with SMTP id wc9-20020a056871a50900b001e9bd5cae38mr11367267oab.2.1698692703005; Mon, 30 Oct 2023 12:05:03 -0700 (PDT) MIME-Version: 1.0 References: <20231003122251.3325435-1-adhemerval.zanella@linaro.org> <20231003122251.3325435-8-adhemerval.zanella@linaro.org> In-Reply-To: <20231003122251.3325435-8-adhemerval.zanella@linaro.org> From: Noah Goldstein Date: Mon, 30 Oct 2023 14:04:51 -0500 Message-ID: Subject: Re: [PATCH v8 7/7] stdlib: Add more qsort{_r} coverage To: Adhemerval Zanella Cc: libc-alpha@sourceware.org, Paul Eggert , Florian Weimer Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-9.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,GIT_PATCH_0,KAM_SHORT,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On Tue, Oct 3, 2023 at 7:23=E2=80=AFAM Adhemerval Zanella wrote: > > This patch adds a qsort and qsort_r to trigger the worst case > scenario for the quicksort (which glibc current lacks coverage). > The test is done with random input, dfferent internal types (uint8_t, > uint16_t, uint32_t, uint64_t, large size), and with > different set of element numbers. > > Checked on x86_64-linux-gnu and i686-linux-gnu. > --- > stdlib/Makefile | 1 + > stdlib/tst-qsort3.c | 366 ++++++++++++++++++++++++++++++++++++++++++++ > 2 files changed, 367 insertions(+) > create mode 100644 stdlib/tst-qsort3.c > > diff --git a/stdlib/Makefile b/stdlib/Makefile > index 095518eef4..6af606136e 100644 > --- a/stdlib/Makefile > +++ b/stdlib/Makefile > @@ -214,6 +214,7 @@ tests :=3D \ > tst-on_exit \ > tst-qsort \ > tst-qsort2 \ > + tst-qsort3 \ > tst-quick_exit \ > tst-rand48 \ > tst-rand48-2 \ > diff --git a/stdlib/tst-qsort3.c b/stdlib/tst-qsort3.c > new file mode 100644 > index 0000000000..421560d744 > --- /dev/null > +++ b/stdlib/tst-qsort3.c > @@ -0,0 +1,366 @@ > +/* qsort(_r) tests to trigger worst case for quicksort. > + Copyright (C) 2023 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 > +#include > +#include > + > +typedef enum > +{ > + Sorted, > + Random, > + Repeated, > + Bitonic, > + Duplicated, > +} arraytype_t; > + > +/* Ratio of total of elements which will be repeated. */ > +static const double RepeatedRatio =3D 0.2; > + > +/* Ratio of duplicated element . */ > +static const double DuplicatedRatio =3D 0.4; > + > +struct array_t > +{ > + arraytype_t type; > + const char *name; > +} static const arraytypes[] =3D > +{ > + { Sorted, "Sorted" }, > + { Random, "Random" }, > + { Repeated, "Repeated" }, > + { Bitonic, "Bitonic" }, > + { Duplicated, "Duplicated" }, > +}; > + > +/* 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 =3D *(uint8_t*)a; > + uint8_t ib =3D *(uint8_t*)b; > + return (ia > ib) - (ia < ib); > +} > + > +static int > +uint16_t_cmp (const void *a, const void *b) > +{ > + uint16_t ia =3D *(uint16_t*)a; > + uint16_t ib =3D *(uint16_t*)b; > + return (ia > ib) - (ia < ib); > +} > + > +static int > +uint32_t_cmp (const void *a, const void *b) > +{ > + uint32_t ia =3D *(uint32_t*)a; > + uint32_t ib =3D *(uint32_t*)b; > + return (ia > ib) - (ia < ib); > +} > + > +static int > +uint64_t_cmp (const void *a, const void *b) > +{ > + uint64_t ia =3D *(uint64_t*)a; > + uint64_t ib =3D *(uint64_t*)b; > + return (ia > ib) - (ia < ib); > +} > + > +#define LARGE_SIZE 47 > + > +static int > +large_cmp (const void *a, const void *b) > +{ > + return memcmp (a, b, LARGE_SIZE); > +} > + > +/* Function used to check qsort_r. */ > +typedef enum > +{ > + UINT8_CMP_T, > + UINT16_CMP_T, > + UINT32_CMP_T, > + UINT64_CMP_T, > + LARGE_CMP_T > +} type_cmp_t; > + > +static type_cmp_t > +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): return UINT32_CMP_T; > + default: return LARGE_CMP_T; > + } > +} > + > +static int > +uint_t_cmp (const void *a, const void *b, void *arg) > +{ > + type_cmp_t type =3D *(type_cmp_t*) arg; > + switch (type) > + { > + case UINT8_CMP_T: return uint8_t_cmp (a, b); > + case UINT32_CMP_T: return uint32_t_cmp (a, b); > + case UINT16_CMP_T: return uint16_t_cmp (a, b); > + case UINT64_CMP_T: return uint64_t_cmp (a, b); > + default: return large_cmp (a, b); > + } > +} > + > +static void > +seq (void *elem, size_t type_size, int value) > +{ > + if (type_size =3D=3D sizeof (uint8_t)) > + *(uint8_t*)elem =3D value; > + else if (type_size =3D=3D sizeof (uint16_t)) > + *(uint16_t*)elem =3D value; > + else if (type_size =3D=3D sizeof (uint32_t)) > + *(uint32_t*)elem =3D value; > + else if (type_size =3D=3D sizeof (uint64_t)) > + *(uint64_t*)elem =3D value; > + else > + memset (elem, value, type_size); > +} > + > +static void > +fill_array (void *array, void *refarray, size_t nmemb, size_t type_size, > + arraytype_t type) > +{ > + size_t size =3D nmemb * type_size; > + > + switch (type) > + { > + case Sorted: > + for (size_t i =3D 0; i < nmemb; i++) > + seq (arr (array, i, type_size), type_size, i); > + break; > + > + case Random: > + arc4random_buf (array, size); > + break; > + > + case Repeated: > + { > + arc4random_buf (array, size); > + > + void *randelem =3D xmalloc (type_size); > + arc4random_buf (randelem, type_size); > + > + /* Repeat REPEATED elements (based on RepeatRatio ratio) in the r= andom > + array. */ > + size_t repeated =3D (size_t)(nmemb * RepeatedRatio); > + for (size_t i =3D 0; i < repeated; i++) > + { > + size_t pos =3D arc4random_uniform (nmemb - 1); > + memcpy (arr (array, pos, type_size), randelem, type_size); > + } > + free (randelem); > + } > + break; > + > + case Bitonic: > + { > + size_t i; > + for (i =3D 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; > + > + case Duplicated: > + { > + int randelem1 =3D arc4random (); > + for (size_t i =3D 0; i < nmemb; i++) > + seq (arr (array, i, type_size), type_size, randelem1); > + > + size_t duplicates =3D (size_t)(nmemb * DuplicatedRatio); > + int randelem2 =3D arc4random (); > + for (size_t i =3D 0; i < duplicates; i++) > + { > + size_t pos =3D arc4random_uniform (nmemb - 1); > + seq (arr (array, pos, type_size), type_size, randelem2); > + } > + } > + break; > + } > + > + memcpy (refarray, array, size); > +} > + > +typedef int (*cmpfunc_t)(const void *, const void *); > + > +/* Simple insertion sort to use as reference sort. */ > +static void > +qsort_r_ref (void *p, size_t n, size_t s, __compar_d_fn_t cmp, void *arg= ) > +{ > + if (n <=3D 1) > + return; > + > + int i =3D 1; > + char tmp[s]; > + while (i < n) > + { > + memcpy (tmp, arr (p, i, s), s); > + int j =3D i - 1; > + while (j >=3D 0 && cmp (arr (p, j, s), tmp, arg) > 0) > + { > + memcpy (arr (p, j + 1, s), arr (p, j, s), s); > + j =3D j - 1; > + } > + memcpy (arr (p, j + 1, s), tmp, s); > + i =3D i + 1; > + } > +} > + > +static void > +qsort_ref (void *b, size_t n, size_t s, __compar_fn_t cmp) > +{ > + return qsort_r_ref (b, n, s, (__compar_d_fn_t) cmp, NULL); > +} > + > +/* Check if ARRAY of total NMEMB element of size SIZE is sorted > + based on CMPFUNC. */ > +static void > +check_array (void *array, void *refarray, size_t nmemb, size_t type_size= , > + cmpfunc_t cmpfunc) > +{ > + for (size_t i =3D 1; i < nmemb; i++) > + { > + int ret =3D cmpfunc (arr (array, i, type_size), > + arr (array, i-1, type_size)); > + TEST_VERIFY_EXIT (ret >=3D 0); > + } > + > + size_t size =3D nmemb * type_size; > + TEST_COMPARE_BLOB (array, size, refarray, size); > +} > + > +static void > +check_qsort (void *buf, void *refbuf, size_t nelem, size_t type_size, > + arraytype_t type, cmpfunc_t cmpfunc) > +{ > + fill_array (buf, refbuf, nelem, type_size, type); > + > + qsort (buf, nelem, type_size, cmpfunc); > + qsort_ref (refbuf, nelem, type_size, cmpfunc); > + > + check_array (buf, refbuf, nelem, type_size, cmpfunc); > +} > + > +static void > +check_qsort_r (void *buf, void *refbuf, size_t nelem, size_t type_size, > + arraytype_t type, cmpfunc_t cmpfunc) > +{ > + fill_array (buf, refbuf, nelem, type_size, type); > + > + type_cmp_t typecmp =3D uint_t_cmp_type (type_size); > + > + qsort_r (buf, nelem, type_size, uint_t_cmp, &typecmp); > + qsort_r_ref (refbuf, nelem, type_size, uint_t_cmp, &typecmp); > + > + check_array (buf, refbuf, nelem, type_size, cmpfunc); > +} > + > +static int > +do_test (void) > +{ > + /* Some random sizes. */ > + static const size_t nelems[] =3D { 0, 1, 7, 20, 32, 100, 256, 1024, 42= 56 }; > + size_t max_nelems =3D 0; > + for (int i =3D 0; i < array_length (nelems); i++) > + if (nelems[i] > max_nelems) > + max_nelems =3D nelems[i]; > + > + static const struct test_t > + { > + size_t type_size; > + cmpfunc_t cmpfunc; > + } > + tests[] =3D > + { > + { 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. */ > + { LARGE_SIZE, large_cmp }, > + }; > + size_t max_type_size =3D 0; > + for (int i =3D 0; i < array_length (tests); i++) > + if (tests[i].type_size > max_type_size) > + max_type_size =3D tests[i].type_size; > + > + void *buf =3D reallocarray (NULL, max_nelems, max_type_size); > + TEST_VERIFY_EXIT (buf !=3D NULL); > + void *refbuf =3D reallocarray (NULL, max_nelems, max_type_size); > + TEST_VERIFY_EXIT (refbuf !=3D NULL); > + > + for (const struct test_t *test =3D tests; test < array_end (tests); ++= test) > + { > + if (test_verbose > 0) > + printf ("info: testing qsort with type_size=3D%zu\n", test->type_= size); > + for (const struct array_t *arraytype =3D arraytypes; > + arraytype < array_end (arraytypes); > + ++arraytype) > + { > + if (test_verbose > 0) > + printf (" distribution=3D%s\n", arraytype->name); > + for (const size_t *nelem =3D nelems; > + nelem < array_end (nelems); > + ++nelem) > + { > + if (test_verbose > 0) > + printf (" nelem=3D%zu, total size=3D%zu\n", *nelem, > + *nelem * test->type_size); > + > + check_qsort (buf, refbuf, *nelem, test->type_size, > + arraytype->type, test->cmpfunc); > + check_qsort_r (buf, refbuf, *nelem, test->type_size, > + arraytype->type, test->cmpfunc); > + } > + } > + } > + > + free (buf); > + free (refbuf); > + > + return 0; > +} > + > +#include > -- > 2.34.1 > LGTM Reviewed-by: Noah Goldstein