Author: trasz Date: Mon Jan 20 11:40:07 2020 New Revision: 356909 URL: https://svnweb.freebsd.org/changeset/base/356909
Log: Add qsort_s(3). Apart from the constraints, it also makes it easier to port software written for Linux variant of qsort_r(3). Reviewed by: kib, arichardson MFC after: 2 weeks Relnotes: yes Sponsored by: DARPA Differential Revision: https://reviews.freebsd.org/D23174 Added: head/lib/libc/stdlib/qsort_s.c (contents, props changed) head/lib/libc/tests/stdlib/qsort_s_test.c (contents, props changed) Modified: head/include/stdlib.h head/lib/libc/stdlib/Makefile.inc head/lib/libc/stdlib/Symbol.map head/lib/libc/stdlib/qsort.3 head/lib/libc/stdlib/qsort.c head/lib/libc/tests/stdlib/Makefile Modified: head/include/stdlib.h ============================================================================== --- head/include/stdlib.h Mon Jan 20 11:19:55 2020 (r356908) +++ head/include/stdlib.h Mon Jan 20 11:40:07 2020 (r356909) @@ -324,6 +324,11 @@ extern char *suboptarg; /* getsubopt(3) external var #if __EXT1_VISIBLE +#ifndef _RSIZE_T_DEFINED +#define _RSIZE_T_DEFINED +typedef size_t rsize_t; +#endif + #ifndef _ERRNO_T_DEFINED #define _ERRNO_T_DEFINED typedef int errno_t; @@ -339,6 +344,9 @@ _Noreturn void abort_handler_s(const char * __restrict errno_t); /* K3.6.1.3 */ void ignore_handler_s(const char * __restrict, void * __restrict, errno_t); +/* K.3.6.3.2 */ +errno_t qsort_s(void *, rsize_t, rsize_t, + int (*)(const void *, const void *, void *), void *); #endif /* __EXT1_VISIBLE */ __END_DECLS Modified: head/lib/libc/stdlib/Makefile.inc ============================================================================== --- head/lib/libc/stdlib/Makefile.inc Mon Jan 20 11:19:55 2020 (r356908) +++ head/lib/libc/stdlib/Makefile.inc Mon Jan 20 11:40:07 2020 (r356909) @@ -11,8 +11,8 @@ MISRCS+=C99_Exit.c a64l.c abort.c abs.c atexit.c atof. getsubopt.c hcreate.c hcreate_r.c hdestroy_r.c heapsort.c heapsort_b.c \ hsearch_r.c imaxabs.c imaxdiv.c \ insque.c l64a.c labs.c ldiv.c llabs.c lldiv.c lsearch.c \ - merge.c mergesort_b.c ptsname.c qsort.c qsort_r.c quick_exit.c \ - radixsort.c rand.c \ + merge.c mergesort_b.c ptsname.c qsort.c qsort_r.c qsort_s.c \ + quick_exit.c radixsort.c rand.c \ random.c reallocarray.c reallocf.c realpath.c remque.c \ set_constraint_handler_s.c strfmon.c strtoimax.c \ strtol.c strtold.c strtoll.c strtoq.c strtoul.c strtonum.c strtoull.c \ @@ -51,7 +51,8 @@ MLINKS+=hcreate.3 hcreate_r.3 hcreate.3 hdestroy_r.3 h MLINKS+=insque.3 remque.3 MLINKS+=lsearch.3 lfind.3 MLINKS+=ptsname.3 grantpt.3 ptsname.3 unlockpt.3 -MLINKS+=qsort.3 heapsort.3 qsort.3 mergesort.3 qsort.3 qsort_r.3 +MLINKS+=qsort.3 heapsort.3 qsort.3 mergesort.3 qsort.3 qsort_r.3 \ + qsort.3 qsort_s.3 MLINKS+=rand.3 rand_r.3 rand.3 srand.3 MLINKS+=random.3 initstate.3 random.3 setstate.3 random.3 srandom.3 \ random.3 srandomdev.3 Modified: head/lib/libc/stdlib/Symbol.map ============================================================================== --- head/lib/libc/stdlib/Symbol.map Mon Jan 20 11:19:55 2020 (r356908) +++ head/lib/libc/stdlib/Symbol.map Mon Jan 20 11:40:07 2020 (r356909) @@ -123,6 +123,10 @@ FBSD_1.5 { set_constraint_handler_s; }; +FBSD_1.6 { + qsort_s; +}; + FBSDprivate_1.0 { __system; _system; Modified: head/lib/libc/stdlib/qsort.3 ============================================================================== --- head/lib/libc/stdlib/qsort.3 Mon Jan 20 11:19:55 2020 (r356908) +++ head/lib/libc/stdlib/qsort.3 Mon Jan 20 11:40:07 2020 (r356909) @@ -32,7 +32,7 @@ .\" @(#)qsort.3 8.1 (Berkeley) 6/4/93 .\" $FreeBSD$ .\" -.Dd February 20, 2013 +.Dd January 14, 2020 .Dt QSORT 3 .Os .Sh NAME @@ -98,6 +98,15 @@ .Fa "size_t size" .Fa "int \*[lp]^compar\*[rp]\*[lp]const void *, const void *\*[rp]" .Fc +.Fd #define __STDC_WANT_LIB_EXT1__ 1 +.Ft errno_t +.Fo qsort_s +.Fa "void *base" +.Fa "rsize_t nmemb" +.Fa "rsize_t size" +.Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *, void *\*[rp]" +.Fa "void *thunk" +.Fc .Sh DESCRIPTION The .Fn qsort @@ -238,6 +247,36 @@ is faster than .Fn heapsort . Memory availability and pre-existing order in the data can make this untrue. +.Pp +The +.Fn qsort_s +function behaves the same as +.Fn qsort_r , except that: +.Bl -dash +.It +The order of arguments is different +.It +The order of arguments to +.Fa compar +is different +.It +if +.Fa nmemb +or +.Fa size +are greater than +.Dv RSIZE_MAX , +or +.Fa nmemb +is not zero and +.Fa compar +is NULL, then the runtime-constraint handler is called, and +.Fn qsort_s +returns an error. +Note that the handler is called before +.Fn qsort_s +returns the error, and the handler function might not return. +.El .Sh RETURN VALUES The .Fn qsort @@ -245,6 +284,9 @@ and .Fn qsort_r functions return no value. +The +.Fn qsort_s +function returns zero on success, non-zero on error. .Pp .Rv -std heapsort mergesort .Sh EXAMPLES @@ -288,6 +330,19 @@ main(void) } .Ed .Sh COMPATIBILITY +The order of arguments for the comparison function used with +.Fn qsort_r +is different from the one used by +.Fn qsort_s , +and the GNU libc implementation of +.Fn qsort_r . +When porting software written for GNU libc, it is usually possible +to replace +.Fn qsort_r +with +.Fn qsort_s +to work around this problem. +.Pp Previous versions of .Fn qsort did not permit the comparison routine itself to call @@ -366,6 +421,10 @@ The function conforms to .St -isoC . +.Fn qsort_s +conforms to +.St -isoC-2011 +K.3.6.3.2. .Sh HISTORY The variants of these functions that take blocks as arguments first appeared in Mac OS X. Modified: head/lib/libc/stdlib/qsort.c ============================================================================== --- head/lib/libc/stdlib/qsort.c Mon Jan 20 11:19:55 2020 (r356908) +++ head/lib/libc/stdlib/qsort.c Mon Jan 20 11:40:07 2020 (r356909) @@ -35,10 +35,16 @@ static char sccsid[] = "@(#)qsort.c 8.1 (Berkeley) 6/4 #include <sys/cdefs.h> __FBSDID("$FreeBSD$"); +#include <errno.h> +#include <stdint.h> #include <stdlib.h> +#include <string.h> +#include "libc_private.h" -#ifdef I_AM_QSORT_R +#if defined(I_AM_QSORT_R) typedef int cmp_t(void *, const void *, const void *); +#elif defined(I_AM_QSORT_S) +typedef int cmp_t(const void *, const void *, void *); #else typedef int cmp_t(const void *, const void *); #endif @@ -65,15 +71,17 @@ swapfunc(char *a, char *b, size_t es) #define vecswap(a, b, n) \ if ((n) > 0) swapfunc(a, b, n) -#ifdef I_AM_QSORT_R +#if defined(I_AM_QSORT_R) #define CMP(t, x, y) (cmp((t), (x), (y))) +#elif defined(I_AM_QSORT_S) +#define CMP(t, x, y) (cmp((x), (y), (t))) #else #define CMP(t, x, y) (cmp((x), (y))) #endif static inline char * med3(char *a, char *b, char *c, cmp_t *cmp, void *thunk -#ifndef I_AM_QSORT_R +#if !defined(I_AM_QSORT_R) && !defined(I_AM_QSORT_S) __unused #endif ) @@ -83,9 +91,12 @@ __unused :(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c )); } -#ifdef I_AM_QSORT_R +#if defined(I_AM_QSORT_R) void qsort_r(void *a, size_t n, size_t es, void *thunk, cmp_t *cmp) +#elif defined(I_AM_QSORT_S) +errno_t +qsort_s(void *a, rsize_t n, rsize_t es, cmp_t *cmp, void *thunk) #else #define thunk NULL void @@ -97,6 +108,24 @@ qsort(void *a, size_t n, size_t es, cmp_t *cmp) int cmp_result; int swap_cnt; +#ifdef I_AM_QSORT_S + if (n > RSIZE_MAX) { + __throw_constraint_handler_s("qsort_s : n > RSIZE_MAX", EINVAL); + return (EINVAL); + } else if (es > RSIZE_MAX) { + __throw_constraint_handler_s("qsort_s : es > RSIZE_MAX", EINVAL); + return (EINVAL); + } else if (n != 0) { + if (a == NULL) { + __throw_constraint_handler_s("qsort_s : a == NULL", EINVAL); + return (EINVAL); + } else if (cmp == NULL) { + __throw_constraint_handler_s("qsort_s : cmp == NULL", EINVAL); + return (EINVAL); + } + } +#endif + loop: swap_cnt = 0; if (n < 7) { @@ -105,7 +134,11 @@ loop: pl > (char *)a && CMP(thunk, pl - es, pl) > 0; pl -= es) swapfunc(pl, pl - es, es); +#ifdef I_AM_QSORT_S + return (0); +#else return; +#endif } pm = (char *)a + (n / 2) * es; if (n > 7) { @@ -154,7 +187,11 @@ loop: pl > (char *)a && CMP(thunk, pl - es, pl) > 0; pl -= es) swapfunc(pl, pl - es, es); +#ifdef I_AM_QSORT_S + return (0); +#else return; +#endif } pn = (char *)a + n * es; @@ -168,8 +205,10 @@ loop: if (d1 <= d2) { /* Recurse on left partition, then iterate on right partition */ if (d1 > es) { -#ifdef I_AM_QSORT_R +#if defined(I_AM_QSORT_R) qsort_r(a, d1 / es, es, thunk, cmp); +#elif defined(I_AM_QSORT_S) + qsort_s(a, d1 / es, es, cmp, thunk); #else qsort(a, d1 / es, es, cmp); #endif @@ -184,8 +223,10 @@ loop: } else { /* Recurse on right partition, then iterate on left partition */ if (d2 > es) { -#ifdef I_AM_QSORT_R +#if defined(I_AM_QSORT_R) qsort_r(pn - d2, d2 / es, es, thunk, cmp); +#elif defined(I_AM_QSORT_S) + qsort_s(pn - d2, d2 / es, es, cmp, thunk); #else qsort(pn - d2, d2 / es, es, cmp); #endif @@ -197,4 +238,8 @@ loop: goto loop; } } + +#ifdef I_AM_QSORT_S + return (0); +#endif } Added: head/lib/libc/stdlib/qsort_s.c ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ head/lib/libc/stdlib/qsort_s.c Mon Jan 20 11:40:07 2020 (r356909) @@ -0,0 +1,8 @@ +/* + * This file is in the public domain. Originally written by Garrett + * A. Wollman. + * + * $FreeBSD$ + */ +#define I_AM_QSORT_S +#include "qsort.c" Modified: head/lib/libc/tests/stdlib/Makefile ============================================================================== --- head/lib/libc/tests/stdlib/Makefile Mon Jan 20 11:19:55 2020 (r356908) +++ head/lib/libc/tests/stdlib/Makefile Mon Jan 20 11:40:07 2020 (r356909) @@ -6,6 +6,7 @@ ATF_TESTS_C+= dynthr_test ATF_TESTS_C+= heapsort_test ATF_TESTS_C+= mergesort_test ATF_TESTS_C+= qsort_test +ATF_TESTS_C+= qsort_s_test ATF_TESTS_C+= set_constraint_handler_s_test ATF_TESTS_C+= strfmon_test ATF_TESTS_C+= tsearch_test Added: head/lib/libc/tests/stdlib/qsort_s_test.c ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ head/lib/libc/tests/stdlib/qsort_s_test.c Mon Jan 20 11:40:07 2020 (r356909) @@ -0,0 +1,257 @@ +/*- + * Copyright (C) 2020 Edward Tomasz Napierala <tr...@freebsd.org> + * Copyright (c) 2017 Juniper Networks. All rights reserved. + * Copyright (C) 2004 Maxim Sobolev <sobo...@freebsd.org> + * All rights reserved. + * + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``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 OR CONTRIBUTORS 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. + */ + +/* + * Test for qsort_s(3) routine. + */ + +#include <sys/cdefs.h> +__FBSDID("$FreeBSD$"); + +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> + +#define THUNK 42 + +#include "test-sort.h" + +static errno_t e; + +static int +sorthelp_s(const void *a, const void *b, void *thunk) +{ + const int *oa, *ob; + + ATF_REQUIRE_EQ(*(int *)thunk, THUNK); + + oa = a; + ob = b; + /* Don't use "return *oa - *ob" since it's easy to cause overflow! */ + if (*oa > *ob) + return (1); + if (*oa < *ob) + return (-1); + return (0); +} + +void +h(const char * restrict msg __unused, void * restrict ptr __unused, errno_t error) +{ + e = error; +} + +/* nmemb < 0 */ +ATF_TC_WITHOUT_HEAD(qsort_s_nmemb_lt_zero); +ATF_TC_BODY(qsort_s_nmemb_lt_zero, tc) +{ + int thunk = THUNK; + int b; + + ATF_CHECK(qsort_s(&b, -1, sizeof(int), sorthelp_s, &thunk) != 0); +} + +/* nmemb > rmax */ +ATF_TC_WITHOUT_HEAD(qsort_s_nmemb_gt_rmax); +ATF_TC_BODY(qsort_s_nmemb_gt_rmax, tc) +{ + int thunk = THUNK; + int b; + + ATF_CHECK(qsort_s(&b, RSIZE_MAX + 1, sizeof(int), sorthelp_s, &thunk) != 0); +} + +/* size < 0 */ +ATF_TC_WITHOUT_HEAD(qsort_s_size_lt_zero); +ATF_TC_BODY(qsort_s_size_lt_zero, tc) +{ + int thunk = THUNK; + int b; + + ATF_CHECK(qsort_s(&b, 1, -1, sorthelp_s, &thunk) != 0); +} + +/* size > rmax */ +ATF_TC_WITHOUT_HEAD(qsort_s_size_gt_rmax); +ATF_TC_BODY(qsort_s_size_gt_rmax, tc) +{ + int thunk = THUNK; + int b; + + ATF_CHECK(qsort_s(&b, 1, RSIZE_MAX + 1, sorthelp_s, &thunk) != 0); +} + +/* NULL compar */ +ATF_TC_WITHOUT_HEAD(qsort_s_null_compar); +ATF_TC_BODY(qsort_s_null_compar, tc) +{ + int thunk = THUNK; + int b; + + ATF_CHECK(qsort_s(&b, 1, sizeof(int), NULL, &thunk) != 0); +} + +/* nmemb < 0, handler */ +ATF_TC_WITHOUT_HEAD(qsort_s_nmemb_lt_zero_h); +ATF_TC_BODY(qsort_s_nmemb_lt_zero_h, tc) +{ + int thunk = THUNK; + int b[] = {81, 4, 7}; + + e = 0; + set_constraint_handler_s(h); + ATF_CHECK(qsort_s(&b, -1, sizeof(int), sorthelp_s, &thunk) != 0); + ATF_CHECK(e > 0); + ATF_CHECK_EQ(b[0], 81); + ATF_CHECK_EQ(b[1], 4); + ATF_CHECK_EQ(b[2], 7); +} + +/* nmemb > rmax, handler */ +ATF_TC_WITHOUT_HEAD(qsort_s_nmemb_gt_rmax_h); +ATF_TC_BODY(qsort_s_nmemb_gt_rmax_h, tc) +{ + int thunk = THUNK; + int b[] = {81, 4, 7}; + + e = 0; + set_constraint_handler_s(h); + ATF_CHECK(qsort_s(&b, RSIZE_MAX + 1, sizeof(int), sorthelp_s, &thunk) != 0); + ATF_CHECK(e > 0); + ATF_CHECK_EQ(b[0], 81); + ATF_CHECK_EQ(b[1], 4); + ATF_CHECK_EQ(b[2], 7); +} + +/* size < 0, handler */ +ATF_TC_WITHOUT_HEAD(qsort_s_size_lt_zero_h); +ATF_TC_BODY(qsort_s_size_lt_zero_h, tc) +{ + int thunk = THUNK; + int b[] = {81, 4, 7}; + + e = 0; + set_constraint_handler_s(h); + ATF_CHECK(qsort_s(&b, nitems(b), -1, sorthelp_s, &thunk) != 0); + ATF_CHECK(e > 0); + ATF_CHECK_EQ(b[0], 81); + ATF_CHECK_EQ(b[1], 4); + ATF_CHECK_EQ(b[2], 7); +} + +/* size > rmax, handler */ +ATF_TC_WITHOUT_HEAD(qsort_s_size_gt_rmax_h); +ATF_TC_BODY(qsort_s_size_gt_rmax_h, tc) +{ + int thunk = THUNK; + int b[] = {81, 4, 7}; + + e = 0; + set_constraint_handler_s(h); + ATF_CHECK(qsort_s(&b, nitems(b), RSIZE_MAX + 1, sorthelp_s, &thunk) != 0); + ATF_CHECK(e > 0); + ATF_CHECK_EQ(b[0], 81); + ATF_CHECK_EQ(b[1], 4); + ATF_CHECK_EQ(b[2], 7); +} + +/* NULL compar, handler */ +ATF_TC_WITHOUT_HEAD(qsort_s_null_compar_h); +ATF_TC_BODY(qsort_s_null_compar_h, tc) +{ + int thunk = THUNK; + int b[] = {81, 4, 7}; + + e = 0; + set_constraint_handler_s(h); + ATF_CHECK(qsort_s(&b, nitems(b), sizeof(int), NULL, &thunk) != 0); + ATF_CHECK(e > 0); + ATF_CHECK_EQ(b[0], 81); + ATF_CHECK_EQ(b[1], 4); + ATF_CHECK_EQ(b[2], 7); +} + +ATF_TC_WITHOUT_HEAD(qsort_s_h); +ATF_TC_BODY(qsort_s_h, tc) +{ + int thunk = THUNK; + int b[] = {81, 4, 7}; + + e = 0; + set_constraint_handler_s(h); + ATF_CHECK(qsort_s(&b, nitems(b), sizeof(int), sorthelp_s, &thunk) == 0); + ATF_CHECK(e == 0); + ATF_CHECK_EQ(b[0], 4); + ATF_CHECK_EQ(b[1], 7); + ATF_CHECK_EQ(b[2], 81); +} + +ATF_TC_WITHOUT_HEAD(qsort_s_test); +ATF_TC_BODY(qsort_s_test, tc) +{ + int testvector[IVEC_LEN]; + int sresvector[IVEC_LEN]; + int i, j; + int thunk = THUNK; + + for (j = 2; j < IVEC_LEN; j++) { + /* Populate test vectors */ + for (i = 0; i < j; i++) + testvector[i] = sresvector[i] = initvector[i]; + + /* Sort using qsort_s(3) */ + qsort_s(testvector, j, sizeof(testvector[0]), + sorthelp_s, &thunk); + /* Sort using reference slow sorting routine */ + ssort(sresvector, j); + + /* Compare results */ + for (i = 0; i < j; i++) + ATF_CHECK_MSG(testvector[i] == sresvector[i], + "item at index %d didn't match: %d != %d", + i, testvector[i], sresvector[i]); + } +} + +ATF_TP_ADD_TCS(tp) +{ + ATF_TP_ADD_TC(tp, qsort_s_nmemb_lt_zero); + ATF_TP_ADD_TC(tp, qsort_s_nmemb_gt_rmax); + ATF_TP_ADD_TC(tp, qsort_s_size_lt_zero); + ATF_TP_ADD_TC(tp, qsort_s_size_gt_rmax); + ATF_TP_ADD_TC(tp, qsort_s_null_compar); + ATF_TP_ADD_TC(tp, qsort_s_nmemb_lt_zero_h); + ATF_TP_ADD_TC(tp, qsort_s_nmemb_gt_rmax_h); + ATF_TP_ADD_TC(tp, qsort_s_size_lt_zero_h); + ATF_TP_ADD_TC(tp, qsort_s_size_gt_rmax_h); + ATF_TP_ADD_TC(tp, qsort_s_null_compar_h); + ATF_TP_ADD_TC(tp, qsort_s_h); + ATF_TP_ADD_TC(tp, qsort_s_test); + + return (atf_no_error()); +} _______________________________________________ svn-src-all@freebsd.org mailing list https://lists.freebsd.org/mailman/listinfo/svn-src-all To unsubscribe, send any mail to "svn-src-all-unsubscr...@freebsd.org"
