3763 Implement qsort_r(3C)

Reviewed by: Toomas Soome <tsoome@me.com>
Reviewed by: Andy Fiddaman <andy@omniosce.org>
Approved by: Dan McDonald <danmcd@joyent.com>

18 files changed, 1456 insertions, 113 deletions

diff --git a/exception_lists/cstyle b/exception_lists/cstyle
index d347bc3eea..5218f53f45 100644
--- a/exception_lists/cstyle
+++ b/exception_lists/cstyle
@@ -1405,6 +1405,7 @@ usr/src/cmd/bhyvectl/bhyvectl.c
 usr/src/compat/bhyve/*
 usr/src/contrib/bhyve/*
 usr/src/lib/libvmmapi/common/vmmapi.[ch]
+usr/src/test/libc-tests/tests/qsort/*.c
 usr/src/uts/i86pc/io/vmm/amd/*.[ch]
 usr/src/uts/i86pc/io/vmm/intel/*.[chs]
 usr/src/uts/i86pc/io/vmm/io/*.[ch]
diff --git a/exception_lists/wscheck b/exception_lists/wscheck
index 48893a7a1b..cea72a1e0a 100644
--- a/exception_lists/wscheck
+++ b/exception_lists/wscheck
@@ -20,6 +20,7 @@ usr/src/data/hwdata/usb.ids
 usr/src/data/perfmon/readme.txt
 usr/src/test/crypto-tests/tests/digest/data/*.rsp
 usr/src/test/util-tests/tests/dis/i386/*.out
+usr/src/test/libc-tests/tests/qsort/*.c
 usr/src/tools/smatch/src/*
 usr/src/uts/common/io/cxgbe/*
 usr/src/uts/common/io/e1000api/*
diff --git a/usr/src/common/util/qsort.c b/usr/src/common/util/qsort.c
index ce2a596554..78967c0ac6 100644
--- a/usr/src/common/util/qsort.c
+++ b/usr/src/common/util/qsort.c
@@ -22,10 +22,9 @@
 /*
  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
  * Use is subject to license terms.
+ * Copyright 2020 Oxide Computer Company
  */
 
-#pragma ident	"%Z%%M%	%I%	%E% SMI"
-
 #if !defined(_KERNEL) && !defined(_KMDB)
 #include "lint.h"
 #endif /* !_KERNEL && !_KMDB */
@@ -44,15 +43,32 @@ static void swapp64(uint64_t *r1, uint64_t *r2, size_t cnt);
 static void swapi(uint32_t *r1, uint32_t *r2, size_t cnt);
 static void swapb(char *r1, char *r2, size_t cnt);
 
+typedef int (*cmp_f)(const void *, const void *, void *);
+
 /*
  * choose a median of 3 values
- *
- * note: cstyle specifically prohibits nested conditional operators
- * but this is the only way to do the median of 3 function in-line
  */
-#define	med3(a, b, c) (cmp((a), (b)) < 0) \
-	? ((cmp((b), (c)) < 0) ? (b) : (cmp((a), (c)) < 0) ? (c) : (a)) \
-	: ((cmp((b), (c)) > 0) ? (b) : (cmp((a), (c)) > 0) ? (c) : (a))
+static __GNU_INLINE char *
+med3(char *a, char *b, char *c, cmp_f cmp, void *arg)
+{
+	if (cmp(a, b, arg) < 0) {
+		if (cmp(b, c, arg) < 0) {
+			return (b);
+		} else if (cmp(a, c, arg) < 0) {
+			return (c);
+		} else {
+			return (a);
+		}
+	} else {
+		if (cmp(b, c, arg) > 0) {
+			return (b);
+		} else if (cmp(a, c, arg) > 0) {
+			return (c);
+		} else {
+			return (a);
+		}
+	}
+}
 
 #define	THRESH_L	5	/* threshold for insertion sort */
 #define	THRESH_M3	20	/* threshold for median of 3 */
@@ -104,12 +120,17 @@ typedef struct {
  *   9) The user compare function modifies the data records
  */
 
+static int
+qsort_r_wrapper(const void *a, const void *b, void *arg)
+{
+	int (*cmp)(const void *, const void *) =
+	    (int(*)(const void *, const void *))(uintptr_t)arg;
+	return (cmp(a, b));
+}
+
 void
-qsort(
-	void		*basep,
-	size_t		nrec,
-	size_t		rsiz,
-	int		(*cmp)(const void *, const void *))
+qsort_r(void *basep, size_t nrec, size_t rsiz,
+    cmp_f cmp, void *arg)
 {
 	size_t		i;		/* temporary variable */
 
@@ -209,7 +230,8 @@ qsort(
 				b_par = t_par;
 				while (b_par > b_lim) {
 					b_par -= rsiz;
-					if ((*cmp)(b_par, b_par + rsiz) <= 0) {
+					if ((*cmp)(b_par, b_par + rsiz, arg) <=
+					    0) {
 						break;
 					}
 					(*swapf)(b_par, b_par + rsiz, loops);
@@ -264,14 +286,16 @@ qsort(
 		} else if (nrec < THRESH_M9) {
 			/* use median of 3 */
 			i = ((nrec - 1) / 2) * rsiz;
-			m2 = med3(b_lim, b_lim + i, b_lim + 2 * i);
+			m2 = med3(b_lim, b_lim + i, b_lim + 2 * i, cmp, arg);
 		} else {
 			/* approx median of 9 */
 			i = ((nrec - 1) / 8) * rsiz;
-			m1 = med3(b_lim, b_lim +  i, b_lim + 2 * i);
-			m2 = med3(b_lim + 3 * i, b_lim + 4 * i, b_lim + 5 * i);
-			m3 = med3(b_lim + 6 * i, b_lim + 7 * i, b_lim + 8 * i);
-			m2 = med3(m1, m2, m3);
+			m1 = med3(b_lim, b_lim +  i, b_lim + 2 * i, cmp, arg);
+			m2 = med3(b_lim + 3 * i, b_lim + 4 * i, b_lim + 5 * i,
+			    cmp, arg);
+			m3 = med3(b_lim + 6 * i, b_lim + 7 * i, b_lim + 8 * i,
+			    cmp, arg);
+			m2 = med3(m1, m2, m3, cmp, arg);
 		}
 
 		/*
@@ -323,7 +347,7 @@ qsort(
 				if (b_par == m2) {
 					continue;
 				}
-				cv = cmp(b_par, m2);
+				cv = cmp(b_par, m2, arg);
 				if (cv > 0) {
 					break;
 				}
@@ -342,7 +366,7 @@ qsort(
 				if (t_par == m2) {
 					continue;
 				}
-				cv = cmp(t_par, m2);
+				cv = cmp(t_par, m2, arg);
 				if (cv < 0) {
 					break;
 				}
@@ -467,6 +491,14 @@ qsort(
 	}
 }
 
+void
+qsort(void *basep, size_t nrec, size_t rsiz,
+    int (*cmp)(const void *, const void *))
+{
+	return (qsort_r(basep, nrec, rsiz, qsort_r_wrapper,
+	    (void *)(uintptr_t)cmp));
+}
+
 /*
  * The following swap functions should not create a stack frame
  * the SPARC call / return instruction will be executed
diff --git a/usr/src/head/stdlib.h b/usr/src/head/stdlib.h
index 337311a978..37dfbe6a3e 100644
--- a/usr/src/head/stdlib.h
+++ b/usr/src/head/stdlib.h
@@ -311,7 +311,7 @@ extern char *ulltostr(unsigned long long, char *);
 
 #endif /* defined(__EXTENSIONS__) || !defined(_STRICT_STDC) ... */
 
-/* OpenBSD compatibility functions */
+/* OpenBSD and misc. compatibility functions */
 #if !defined(_STRICT_SYMBOLS)
 
 #include <inttypes.h>
@@ -324,6 +324,8 @@ extern void *recallocarray(void *, size_t, size_t, size_t);
 extern long long strtonum(const char *, long long, long long, const char **);
 extern void *reallocf(void *, size_t);
 
+extern void qsort_r(void *, size_t, size_t,
+    int (*)(const void *, const void *, void *), void *);
 #endif	/* !_STRICT_SYBMOLS */
 
 
diff --git a/usr/src/lib/libc/port/mapfile-vers b/usr/src/lib/libc/port/mapfile-vers
index be5b7e73bf..0be36d5e6b 100644
--- a/usr/src/lib/libc/port/mapfile-vers
+++ b/usr/src/lib/libc/port/mapfile-vers
@@ -78,6 +78,11 @@ $if _x86 && _ELF64
 $add amd64
 $endif
 
+SYMBOL_VERSION ILLUMOS_0.35 {
+    protected:
+	qsort_r;
+} ILLUMOS_0.34;
+
 SYMBOL_VERSION ILLUMOS_0.34 {
     protected:
 	futimes;
diff --git a/usr/src/man/man3c/Makefile b/usr/src/man/man3c/Makefile
index 1728df06e3..d2ed27f4d7 100644
--- a/usr/src/man/man3c/Makefile
+++ b/usr/src/man/man3c/Makefile
@@ -1157,6 +1157,7 @@ MANLINKS=	FD_CLR.3c				\
 		qeconvert.3c				\
 		qfconvert.3c				\
 		qgconvert.3c				\
+		qsort_r.3c				\
 		quadruple_to_decimal.3c			\
 		rand_r.3c				\
 		rctlblk_get_enforced_value.3c		\
@@ -2249,6 +2250,8 @@ pthread_spin_trylock.3c			:= LINKSRC = pthread_spin_lock.3c
 
 fputs.3c				:= LINKSRC = puts.3c
 
+qsort_r.3c				:= LINKSRC = qsort.3c
+
 rand_r.3c				:= LINKSRC = rand.3c
 srand.3c				:= LINKSRC = rand.3c
 
diff --git a/usr/src/man/man3c/qsort.3c b/usr/src/man/man3c/qsort.3c
index 133f654330..7bfaf50a5d 100644
--- a/usr/src/man/man3c/qsort.3c
+++ b/usr/src/man/man3c/qsort.3c
@@ -1,57 +1,106 @@
-'\" te
-.\"  Copyright 1989 AT&T  Copyright (c) 2002, Sun Microsystems, Inc.  All Rights Reserved
-.\" The contents of this file are subject to the terms of the Common Development and Distribution License (the "License").  You may not use this file except in compliance with the License.
-.\" You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE or http://www.opensolaris.org/os/licensing.  See the License for the specific language governing permissions and limitations under the License.
-.\" When distributing Covered Code, include this CDDL HEADER in each file and include the License file at usr/src/OPENSOLARIS.LICENSE.  If applicable, add the following below this CDDL HEADER, with the fields enclosed by brackets "[]" replaced with your own identifying information: Portions Copyright [yyyy] [name of copyright owner]
-.TH QSORT 3C "Dec 6, 2004"
-.SH NAME
-qsort \- quick sort
-.SH SYNOPSIS
-.LP
-.nf
-#include <stdlib.h>
-
-\fBvoid\fR \fBqsort\fR(\fBvoid *\fR\fIbase\fR, \fBsize_t\fR \fInel\fR, \fBsize_t\fR \fIwidth\fR,
-     \fBint (*\fR\fIcompar\fR)(const void *, const void *));
-.fi
-
-.SH DESCRIPTION
-.sp
-.LP
-The \fBqsort()\fR function is an implementation of the quick-sort algorithm. It
-sorts a table of data in place. The contents of the table are sorted in
-ascending order according to the  user-supplied comparison function.
-.sp
-.LP
-The \fIbase\fR argument points to the element at the base of the table.  The
-\fInel\fR argument is the number of elements in the table.  The \fIwidth\fR
-argument specifies the size of each element in bytes.  The \fIcompar\fR
-argument is the name of the comparison function, which is called with two
+.\"
+.\" The contents of this file are subject to the terms of the
+.\" Common Development and Distribution License (the "License").
+.\" You may not use this file except in compliance with the License.
+.\"
+.\" You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
+.\" or http://www.opensolaris.org/os/licensing.
+.\" See the License for the specific language governing permissions
+.\" and limitations under the License.
+.\"
+.\" When distributing Covered Code, include this CDDL HEADER in each
+.\" file and include the License file at usr/src/OPENSOLARIS.LICENSE.
+.\" If applicable, add the following below this CDDL HEADER, with the
+.\" fields enclosed by brackets "[]" replaced with your own identifying
+.\" information: Portions Copyright [yyyy] [name of copyright owner]
+.\"
+.\"
+.\" Copyright 1989 AT&T
+.\" Copyright (c) 2002, Sun Microsystems, Inc.  All Rights Reserved
+.\" Copyright 2020 Oxide Computer Company
+.\"
+.Dd September 11, 2020
+.Dt QSORT 3C
+.Os
+.Sh NAME
+.Nm qsort ,
+.Nm qsort_r
+.Nd quick sort
+.Sh SYNOPSIS
+.In stdlib.h
+.Ft void
+.Fo qsort
+.Fa "void *base"
+.Fa "size_t nel"
+.Fa "size_t width"
+.Fa "int (*compar)(const void *, const void *)"
+.Fc
+.Fo qsort
+.Fa "void *base"
+.Fa "size_t nel"
+.Fa "size_t width"
+.Fa "int (*compar_arg)(const void *, const void *, void *)"
+.Fa "void *arg"
+.Fc
+.Sh DESCRIPTION
+The
+.Fn qsort
+function is an implementation of the quick-sort algorithm.
+It sorts a table of data in place.
+The contents of the table are sorted in ascending order according to the
+user-supplied comparison function.
+.Pp
+The
+.Fa Ibase
+argument points to the element at the base of the table.
+The
+.Fa nel
+argument is the number of elements in the table.
+The
+.Fa width
+argument specifies the size of each element in bytes.
+The
+.Fa compar
 arguments that point to the elements being compared.
-.sp
-.LP
+The comparison function need not compare every byte, so arbitrary data may be
+contained in the elements in addition to the values being compared.
+.Pp
 The function must return an integer less than, equal to, or greater than zero
 to indicate if the first argument is to be considered less than, equal to, or
 greater than the second argument.
-.sp
-.LP
+.Pp
 The contents of the table are sorted in ascending order according to the user
 supplied comparison function.
-.SH USAGE
-.sp
-.LP
-The \fBqsort()\fR function safely allows concurrent access by  multiple threads
+The relative order in the output of two items that compare as equal is
+unpredictable.
+.Pp
+The
+.Fn qsort_r
+function behaves similarly to the
+.Fn qsort
+function, except that its comparison function,
+.Fn compar_arg ,
+takes an extra argument which is the
+.Fn qsort_r
+argument
+.Fa arg .
+This allows one to avoid global data in the comparison function, unlike
+with the
+.Fn qsort
+function.
+.Pp
+The
+.Fn qsort
+and
+.Fn qsort_r
+function safely allows concurrent access by multiple threads
 to disjoint data, such as overlapping subtrees or tables.
-.SH EXAMPLES
-.LP
-\fBExample 1 \fRProgram sorts.
-.sp
-.LP
+.Sh EXAMPLES
+.Sy Example 1
+Program sorts.
+.Pp
 The following program sorts a simple array:
-
-.sp
-.in +2
-.nf
+.Bd -literal
 #include <stdlib.h>
 #include <stdio.h>
 
@@ -84,38 +133,15 @@ main()
     (void) printf("\en");
     return (0);
 }
-.fi
-.in -2
-
-.SH ATTRIBUTES
-.sp
-.LP
-See \fBattributes\fR(5) for descriptions of the following attributes:
-.sp
-
-.sp
-.TS
-box;
-c | c
-l | l .
-ATTRIBUTE TYPE	ATTRIBUTE VALUE
-_
-Interface Stability	Standard
-_
-MT-Level	MT-Safe
-.TE
-
-.SH SEE ALSO
-.sp
-.LP
-\fBsort\fR(1), \fBbsearch\fR(3C), \fBlsearch\fR(3C), \fBstring\fR(3C),
-\fBattributes\fR(5), \fBstandards\fR(5)
-.SH NOTES
-.sp
-.LP
-The comparison function need not compare every byte, so arbitrary data may be
-contained in the elements in addition to the values being compared.
-.sp
-.LP
-The relative order in the output of two items that compare as equal is
-unpredictable.
+.Ed
+.Sh INTERFACE STABILITY
+.Sy Standard
+.Sh MT-LEVEL
+.Sy MT-Safe
+.Sh SEE ALSO
+.Xr sort 1 ,
+.Xr bsearch 3C ,
+.Xr lsearch 3C ,
+.Xr string 3C ,
+.Xr attributes 5 ,
+.Xr standards 5
diff --git a/usr/src/pkg/manifests/system-library.man3c.inc b/usr/src/pkg/manifests/system-library.man3c.inc
index ce6056ce82..100b5db173 100644
--- a/usr/src/pkg/manifests/system-library.man3c.inc
+++ b/usr/src/pkg/manifests/system-library.man3c.inc
@@ -1216,6 +1216,7 @@ link path=usr/share/man/man3c/putwchar.3c target=fputwc.3c
 link path=usr/share/man/man3c/qeconvert.3c target=econvert.3c
 link path=usr/share/man/man3c/qfconvert.3c target=econvert.3c
 link path=usr/share/man/man3c/qgconvert.3c target=econvert.3c
+link path=usr/share/man/man3c/qsort_r.3c target=qsort.3c
 link path=usr/share/man/man3c/quadruple_to_decimal.3c \
     target=floating_to_decimal.3c
 link path=usr/share/man/man3c/rand_r.3c target=rand.3c
diff --git a/usr/src/pkg/manifests/system-test-libctest.mf b/usr/src/pkg/manifests/system-test-libctest.mf
index 3145beeadc..adb232e2ef 100644
--- a/usr/src/pkg/manifests/system-test-libctest.mf
+++ b/usr/src/pkg/manifests/system-test-libctest.mf
@@ -30,6 +30,7 @@ dir path=opt/libc-tests/cfg/symbols
 dir path=opt/libc-tests/runfiles
 dir path=opt/libc-tests/tests
 dir path=opt/libc-tests/tests/i18n
+dir path=opt/libc-tests/tests/qsort
 dir path=opt/libc-tests/tests/random
 dir path=opt/libc-tests/tests/regex
 dir path=opt/libc-tests/tests/regex/data
@@ -116,6 +117,9 @@ file path=opt/libc-tests/tests/psignal mode=0555
 file path=opt/libc-tests/tests/psignal-5097.32 mode=0555
 file path=opt/libc-tests/tests/psignal-5097.64 mode=0555
 file path=opt/libc-tests/tests/pthread_attr_get_np mode=0555
+file path=opt/libc-tests/tests/qsort/qsort_test mode=0555
+file path=opt/libc-tests/tests/qsort/qsort_test.$(ARCH) mode=0555
+file path=opt/libc-tests/tests/qsort/qsort_test.$(ARCH64) mode=0555
 file path=opt/libc-tests/tests/quick_exit mode=0555
 file path=opt/libc-tests/tests/quick_exit_order.32 mode=0555
 file path=opt/libc-tests/tests/quick_exit_order.64 mode=0555
diff --git a/usr/src/test/libc-tests/cfg/symbols/stdlib_h.cfg b/usr/src/test/libc-tests/cfg/symbols/stdlib_h.cfg
index 745575068d..37d6ab9376 100644
--- a/usr/src/test/libc-tests/cfg/symbols/stdlib_h.cfg
+++ b/usr/src/test/libc-tests/cfg/symbols/stdlib_h.cfg
@@ -35,7 +35,7 @@ value |	NULL		| void *	| stdlib.h | ALL
 # Functions
 #
 func |	aligned_alloc							|\
-	void * 								|\
+	void *								|\
 	size_t; size_t							|\
 	stdlib.h							|\
 	-ALL C11
@@ -47,55 +47,55 @@ func |	at_quick_exit							|\
 	-ALL C11
 
 func |	calloc								|\
-	void * 								|\
+	void *								|\
 	size_t; size_t							|\
 	stdlib.h							|\
 	ALL
 
 func |	exit								|\
-	void 								|\
+	void								|\
 	int								|\
 	stdlib.h							|\
 	ALL
 
 func |	free								|\
-	void 								|\
+	void								|\
 	void *								|\
 	stdlib.h							|\
 	ALL
 
 func |	malloc								|\
-	void * 								|\
+	void *								|\
 	size_t								|\
 	stdlib.h							|\
 	ALL
 
 func |	mkstemp								|\
-	int 								|\
+	int								|\
 	char *								|\
 	stdlib.h							|\
 	C90 C99 SUSv1+
 
 func |	mkostemp							|\
-	int 								|\
+	int								|\
 	char *; int							|\
 	stdlib.h							|\
 	-ALL
 
 func |	mkstemps							|\
-	int 								|\
+	int								|\
 	char *; int							|\
 	stdlib.h							|\
 	C90 C99
 
 func |	mkostemps							|\
-	int 								|\
+	int								|\
 	char *; int; int						|\
 	stdlib.h							|\
 	-ALL
 
 func |	mkdtemp								|\
-	char * 								|\
+	char *								|\
 	char *								|\
 	stdlib.h							|\
 	-ALL SUSv4+
@@ -105,3 +105,15 @@ func |	quick_exit							|\
 	int								|\
 	stdlib.h							|\
 	-ALL C11
+
+func |	qsort								|\
+	void								|\
+	void *; size_t; size_t; int (*)(const void *, const void *)	|\
+	stdlib.h							|\
+	ALL
+
+func |	qsort_r										|\
+	void										|\
+	void *; size_t; size_t; int (*)(const void *, const void *, void *), void *	|\
+	stdlib.h									|\
+	-ALL
diff --git a/usr/src/test/libc-tests/runfiles/default.run b/usr/src/test/libc-tests/runfiles/default.run
index bada7ea85b..72846a3a46 100644
--- a/usr/src/test/libc-tests/runfiles/default.run
+++ b/usr/src/test/libc-tests/runfiles/default.run
@@ -40,6 +40,7 @@ outputdir = /var/tmp/test_results
 [/opt/libc-tests/tests/wcsncasecmp-7350.64]
 
 [/opt/libc-tests/tests/i18n/bindtextdomain_test]
+[/opt/libc-tests/tests/qsort/qsort_test]
 
 [/opt/libc-tests/tests/random/getrandom]
 [/opt/libc-tests/tests/random/getentropy]
diff --git a/usr/src/test/libc-tests/tests/Makefile b/usr/src/test/libc-tests/tests/Makefile
index 54a9a23572..c15aeba252 100644
--- a/usr/src/test/libc-tests/tests/Makefile
+++ b/usr/src/test/libc-tests/tests/Makefile
@@ -23,6 +23,7 @@ SUBDIRS = \
 	newlocale \
 	nl_langinfo \
 	priv_gettext \
+	qsort \
 	random \
 	regex \
 	select \
diff --git a/usr/src/test/libc-tests/tests/qsort/Makefile b/usr/src/test/libc-tests/tests/qsort/Makefile
new file mode 100644
index 0000000000..0fcc2d2aba
--- /dev/null
+++ b/usr/src/test/libc-tests/tests/qsort/Makefile
@@ -0,0 +1,22 @@
+#
+# This file and its contents are supplied under the terms of the
+# Common Development and Distribution License ("CDDL"), version 1.0.
+# You may only use this file in accordance with the terms of version
+# 1.0 of the CDDL.
+#
+# A full copy of the text of the CDDL should have accompanied this
+# source.  A copy of the CDDL is also available via the Internet at
+# http://www.illumos.org/license/CDDL.
+#
+
+#
+# Copyright 2020 Oxide Computer Company
+#
+
+TESTSUBDIR = qsort
+PROG = qsort_test
+ARCHPROG = qsort_test
+OBJS_OVERRIDE=1
+OBJS = qsort_test.o merge.o antiqsort.o
+
+include ../Makefile.com
diff --git a/usr/src/test/libc-tests/tests/qsort/THIRDPARTYLICENSE b/usr/src/test/libc-tests/tests/qsort/THIRDPARTYLICENSE
new file mode 100644
index 0000000000..fed2d8bb0b
--- /dev/null
+++ b/usr/src/test/libc-tests/tests/qsort/THIRDPARTYLICENSE
@@ -0,0 +1,47 @@
+/*
+ * Copyright (c) 2017 Todd C. Miller <millert@openbsd.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+/*-
+ * Copyright (c) 1992, 1993
+ *	The Regents of the University of California.  All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Peter McIlroy.
+ *
+ * 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. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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.
+ */
diff --git a/usr/src/test/libc-tests/tests/qsort/THIRDPARTYLICENSE.descrip b/usr/src/test/libc-tests/tests/qsort/THIRDPARTYLICENSE.descrip
new file mode 100644
index 0000000000..3d6d2ccd52
--- /dev/null
+++ b/usr/src/test/libc-tests/tests/qsort/THIRDPARTYLICENSE.descrip
@@ -0,0 +1 @@
+QUICKSORT TEST SUITE
diff --git a/usr/src/test/libc-tests/tests/qsort/antiqsort.c b/usr/src/test/libc-tests/tests/qsort/antiqsort.c
new file mode 100644
index 0000000000..cb3b7b2525
--- /dev/null
+++ b/usr/src/test/libc-tests/tests/qsort/antiqsort.c
@@ -0,0 +1,58 @@
+/*
+ * A Killer Adversary for Quicksort
+ * M. D. MCILROY
+ * http://www.cs.dartmouth.edu/~doug/mdmspe.pdf
+ *
+ * For comparison:
+ *  Bentley & McIlroy: 4096 items, 1645585 compares
+ *  random pivot:      4096 items, 8388649 compares
+ *  introsort:         4096 items, 151580 compares
+ *  heapsort:          4096 items, 48233 compares
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+
+static int *val;				/* item values */
+static int ncmp;				/* number of comparisons */
+static int nsolid;				/* number of solid items */
+static int candidate;				/* pivot candidate */
+static int gas;					/* gas value */
+
+#define freeze(x)	(val[(x)] = nsolid++)
+
+static int
+cmp(const void *px, const void *py)
+{
+	const int x = *(const int *)px;
+	const int y = *(const int *)py;
+
+	ncmp++;
+	if (val[x] == gas && val[y] == gas) {
+		if (x == candidate)
+			freeze(x);
+		else
+			freeze(y);
+	}
+	if (val[x] == gas)
+		candidate = x;
+	else if (val[y] == gas)
+		candidate = y;
+	return val[x] > val[y] ? 1 : val[x] < val[y] ? -1 : 0;
+}
+
+int
+antiqsort(int n, int *a, int *ptr)
+{
+	int i;
+
+	val = a;
+	gas = n - 1;
+	nsolid = ncmp = candidate = 0;
+	for (i = 0; i < n; i++) {
+		ptr[i] = i;
+		val[i] = gas;
+	}
+	qsort(ptr, n, sizeof(*ptr), cmp);
+	return ncmp;
+}
diff --git a/usr/src/test/libc-tests/tests/qsort/merge.c b/usr/src/test/libc-tests/tests/qsort/merge.c
new file mode 100644
index 0000000000..d60317ce08
--- /dev/null
+++ b/usr/src/test/libc-tests/tests/qsort/merge.c
@@ -0,0 +1,336 @@
+/*	$OpenBSD: merge.c,v 1.10 2015/06/21 03:20:56 millert Exp $ */
+/*-
+ * Copyright (c) 1992, 1993
+ *	The Regents of the University of California.  All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Peter McIlroy.
+ *
+ * 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. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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.
+ */
+
+/*
+ * Hybrid exponential search/linear search merge sort with hybrid
+ * natural/pairwise first pass.  Requires about .3% more comparisons
+ * for random data than LSMS with pairwise first pass alone.
+ * It works for objects as small as two bytes.
+ */
+
+#define NATURAL
+#define THRESHOLD 16	/* Best choice for natural merge cut-off. */
+
+/* #define NATURAL to get hybrid natural merge.
+ * (The default is pairwise merging.)
+ */
+
+#include <sys/types.h>
+
+#include <errno.h>
+#include <stdlib.h>
+#include <string.h>
+
+static void setup(u_char *, u_char *, size_t, size_t, int (*)());
+static void insertionsort(u_char *, size_t, size_t, int (*)());
+
+#define ISIZE sizeof(int)
+#define PSIZE sizeof(u_char *)
+#define ICOPY_LIST(src, dst, last)				\
+	do							\
+	*(int*)dst = *(int*)src, src += ISIZE, dst += ISIZE;	\
+	while(src < last)
+#define ICOPY_ELT(src, dst, i)					\
+	do							\
+	*(int*) dst = *(int*) src, src += ISIZE, dst += ISIZE;	\
+	while (i -= ISIZE)
+
+#define CCOPY_LIST(src, dst, last)		\
+	do					\
+		*dst++ = *src++;		\
+	while (src < last)
+#define CCOPY_ELT(src, dst, i)			\
+	do					\
+		*dst++ = *src++;		\
+	while (i -= 1)
+		
+/*
+ * Find the next possible pointer head.  (Trickery for forcing an array
+ * to do double duty as a linked list when objects do not align with word
+ * boundaries.
+ */
+/* Assumption: PSIZE is a power of 2. */
+#define EVAL(p) (u_char **)						\
+	((u_char *)0 +							\
+	    (((u_char *)p + PSIZE - 1 - (u_char *) 0) & ~(PSIZE - 1)))
+
+/*
+ * Arguments are as for qsort.
+ */
+int
+mergesort(void *base, size_t nmemb, size_t size,
+    int (*cmp)(const void *, const void *))
+{
+	int i, sense;
+	int big, iflag;
+	u_char *f1, *f2, *t, *b, *tp2, *q, *l1, *l2;
+	u_char *list2, *list1, *p2, *p, *last, **p1;
+
+	if (size < PSIZE / 2) {		/* Pointers must fit into 2 * size. */
+		errno = EINVAL;
+		return (-1);
+	}
+
+	if (nmemb == 0)
+		return (0);
+
+	/*
+	 * XXX
+	 * Stupid subtraction for the Cray.
+	 */
+	iflag = 0;
+	if (!(size % ISIZE) && !(((char *)base - (char *)0) % ISIZE))
+		iflag = 1;
+
+	if ((list2 = malloc(nmemb * size + PSIZE)) == NULL)
+		return (-1);
+
+	list1 = base;
+	setup(list1, list2, nmemb, size, cmp);
+	last = list2 + nmemb * size;
+	i = big = 0;
+	while (*EVAL(list2) != last) {
+	    l2 = list1;
+	    p1 = EVAL(list1);
+	    for (tp2 = p2 = list2; p2 != last; p1 = EVAL(l2)) {
+	    	p2 = *EVAL(p2);
+	    	f1 = l2;
+	    	f2 = l1 = list1 + (p2 - list2);
+	    	if (p2 != last)
+	    		p2 = *EVAL(p2);
+	    	l2 = list1 + (p2 - list2);
+	    	while (f1 < l1 && f2 < l2) {
+	    		if ((*cmp)(f1, f2) <= 0) {
+	    			q = f2;
+	    			b = f1, t = l1;
+	    			sense = -1;
+	    		} else {
+	    			q = f1;
+	    			b = f2, t = l2;
+	    			sense = 0;
+	    		}
+	    		if (!big) {	/* here i = 0 */
+	    			while ((b += size) < t && cmp(q, b) >sense)
+	    				if (++i == 6) {
+	    					big = 1;
+	    					goto EXPONENTIAL;
+	    				}
+	    		} else {
+EXPONENTIAL:	    		for (i = size; ; i <<= 1)
+	    				if ((p = (b + i)) >= t) {
+	    					if ((p = t - size) > b &&
+						    (*cmp)(q, p) <= sense)
+	    						t = p;
+	    					else
+	    						b = p;
+	    					break;
+	    				} else if ((*cmp)(q, p) <= sense) {
+	    					t = p;
+	    					if (i == size)
+	    						big = 0; 
+	    					goto FASTCASE;
+	    				} else
+	    					b = p;
+		    		while (t > b+size) {
+	    				i = (((t - b) / size) >> 1) * size;
+	    				if ((*cmp)(q, p = b + i) <= sense)
+	    					t = p;
+	    				else
+	    					b = p;
+	    			}
+	    			goto COPY;
+FASTCASE:	    		while (i > size)
+	    				if ((*cmp)(q,
+	    					p = b + (i >>= 1)) <= sense)
+	    					t = p;
+	    				else
+	    					b = p;
+COPY:	    			b = t;
+	    		}
+	    		i = size;
+	    		if (q == f1) {
+	    			if (iflag) {
+	    				ICOPY_LIST(f2, tp2, b);
+	    				ICOPY_ELT(f1, tp2, i);
+	    			} else {
+	    				CCOPY_LIST(f2, tp2, b);
+	    				CCOPY_ELT(f1, tp2, i);
+	    			}
+	    		} else {
+	    			if (iflag) {
+	    				ICOPY_LIST(f1, tp2, b);
+	    				ICOPY_ELT(f2, tp2, i);
+	    			} else {
+	    				CCOPY_LIST(f1, tp2, b);
+	    				CCOPY_ELT(f2, tp2, i);
+	    			}
+	    		}
+	    	}
+	    	if (f2 < l2) {
+	    		if (iflag)
+	    			ICOPY_LIST(f2, tp2, l2);
+	    		else
+	    			CCOPY_LIST(f2, tp2, l2);
+	    	} else if (f1 < l1) {
+	    		if (iflag)
+	    			ICOPY_LIST(f1, tp2, l1);
+	    		else
+	    			CCOPY_LIST(f1, tp2, l1);
+	    	}
+	    	*p1 = l2;
+	    }
+	    tp2 = list1;	/* swap list1, list2 */
+	    list1 = list2;
+	    list2 = tp2;
+	    last = list2 + nmemb*size;
+	}
+	if (base == list2) {
+		memmove(list2, list1, nmemb*size);
+		list2 = list1;
+	}
+	free(list2);
+	return (0);
+}
+
+#define	swap(a, b) {					\
+		s = b;					\
+		i = size;				\
+		do {					\
+			tmp = *a; *a++ = *s; *s++ = tmp; \
+		} while (--i);				\
+		a -= size;				\
+	}
+#define reverse(bot, top) {				\
+	s = top;					\
+	do {						\
+		i = size;				\
+		do {					\
+			tmp = *bot; *bot++ = *s; *s++ = tmp; \
+		} while (--i);				\
+		s -= size2;				\
+	} while(bot < s);				\
+}
+
+/*
+ * Optional hybrid natural/pairwise first pass.  Eats up list1 in runs of
+ * increasing order, list2 in a corresponding linked list.  Checks for runs
+ * when THRESHOLD/2 pairs compare with same sense.  (Only used when NATURAL
+ * is defined.  Otherwise simple pairwise merging is used.)
+ */
+void
+setup(u_char *list1, u_char *list2, size_t n, size_t size,
+    int (*cmp)(const void *, const void *))
+{
+	int i, length, size2, sense;
+	u_char tmp, *f1, *f2, *s, *l2, *last, *p2;
+
+	size2 = size*2;
+	if (n <= 5) {
+		insertionsort(list1, n, size, cmp);
+		*EVAL(list2) = (u_char*) list2 + n*size;
+		return;
+	}
+	/*
+	 * Avoid running pointers out of bounds; limit n to evens
+	 * for simplicity.
+	 */
+	i = 4 + (n & 1);
+	insertionsort(list1 + (n - i) * size, i, size, cmp);
+	last = list1 + size * (n - i);
+	*EVAL(list2 + (last - list1)) = list2 + n * size;
+
+#ifdef NATURAL
+	p2 = list2;
+	f1 = list1;
+	sense = (cmp(f1, f1 + size) > 0);
+	for (; f1 < last; sense = !sense) {
+		length = 2;
+					/* Find pairs with same sense. */
+		for (f2 = f1 + size2; f2 < last; f2 += size2) {
+			if ((cmp(f2, f2+ size) > 0) != sense)
+				break;
+			length += 2;
+		}
+		if (length < THRESHOLD) {		/* Pairwise merge */
+			do {
+				p2 = *EVAL(p2) = f1 + size2 - list1 + list2;
+				if (sense > 0)
+					swap (f1, f1 + size);
+			} while ((f1 += size2) < f2);
+		} else {				/* Natural merge */
+			l2 = f2;
+			for (f2 = f1 + size2; f2 < l2; f2 += size2) {
+				if ((cmp(f2-size, f2) > 0) != sense) {
+					p2 = *EVAL(p2) = f2 - list1 + list2;
+					if (sense > 0)
+						reverse(f1, f2-size);
+					f1 = f2;
+				}
+			}
+			if (sense > 0)
+				reverse (f1, f2-size);
+			f1 = f2;
+			if (f2 < last || cmp(f2 - size, f2) > 0)
+				p2 = *EVAL(p2) = f2 - list1 + list2;
+			else
+				p2 = *EVAL(p2) = list2 + n*size;
+		}
+	}
+#else		/* pairwise merge only. */
+	for (f1 = list1, p2 = list2; f1 < last; f1 += size2) {
+		p2 = *EVAL(p2) = p2 + size2;
+		if (cmp (f1, f1 + size) > 0)
+			swap(f1, f1 + size);
+	}
+#endif /* NATURAL */
+}
+
+/*
+ * This is to avoid out-of-bounds addresses in sorting the
+ * last 4 elements.
+ */
+static void
+insertionsort(u_char *a, size_t n, size_t size,
+    int (*cmp)(const void *, const void *))
+{
+	u_char *ai, *s, *t, *u, tmp;
+	int i;
+
+	for (ai = a+size; --n >= 1; ai += size)
+		for (t = ai; t > a; t -= size) {
+			u = t - size;
+			if (cmp(u, t) <= 0)
+				break;
+			swap(u, t);
+		}
+}
diff --git a/usr/src/test/libc-tests/tests/qsort/qsort_test.c b/usr/src/test/libc-tests/tests/qsort/qsort_test.c
new file mode 100644
index 0000000000..fb0f5f8e08
--- /dev/null
+++ b/usr/src/test/libc-tests/tests/qsort/qsort_test.c
@@ -0,0 +1,790 @@
+/*
+ * Copyright (c) 2017 Todd C. Miller <millert@openbsd.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <sys/time.h>
+
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <setjmp.h>
+#include <time.h>
+#include <unistd.h>
+#include <err.h>
+
+/*
+ * Test program based on Bentley & McIlroy's "Engineering a Sort Function".
+ * Uses mergesort(3) to check the results.
+ *
+ * Additional "killer" input taken from:
+ *  David R. Musser's "Introspective Sorting and Selection Algorithms"
+ *  http://calmerthanyouare.org/2014/06/11/algorithmic-complexity-attacks-and-libc-qsort.html
+ *  M. D. McIlroy's "A Killer Adversary for Quicksort"
+ */
+
+#define timespecsub(tsp, usp, vsp)					\
+	do {								\
+		(vsp)->tv_sec = (tsp)->tv_sec - (usp)->tv_sec;		\
+		(vsp)->tv_nsec = (tsp)->tv_nsec - (usp)->tv_nsec;	\
+		if ((vsp)->tv_nsec < 0) {				\
+			(vsp)->tv_sec--;				\
+			(vsp)->tv_nsec += 1000000000L;			\
+		}							\
+	} while (0)
+
+extern int mergesort(void *, size_t, size_t,
+    int (*)(const void *, const void *));
+
+/*
+ * TODO:
+ *	test with unaligned elements (char[]?)
+ */
+struct test_distribution {
+	const char *name;
+	void (*fill)(void *x, int n, int m);
+	int (*test)(struct test_distribution *d, int n, void *x, void *y, void *z);
+	int (*cmp)(const void *v1, const void *v2);
+	int (*cmp_checked)(const void *v1, const void *v2);
+};
+
+#define MINIMUM(a, b)	(((a) < (b)) ? (a) : (b))
+#define MAXIMUM(a, b)	(((a) > (b)) ? (a) : (b))
+
+static size_t compares;
+static size_t max_compares;
+static size_t abrt_compares;
+static sigjmp_buf cmpjmp;
+static bool dump_table, timing, verbose;
+
+extern int antiqsort(int n, int *a, int *ptr);
+
+static int
+cmp_i(const void *v1, const void *v2)
+{
+	const int a = *(const int *)v1;
+	const int b = *(const int *)v2;
+
+	return a > b ? 1 : a < b ? -1 : 0;
+}
+
+static int
+cmp_checked_i(const void *v1, const void *v2)
+{
+	const int a = *(const int *)v1;
+	const int b = *(const int *)v2;
+
+	compares++;
+	if (compares > abrt_compares)
+		siglongjmp(cmpjmp, 1);
+	return a > b ? 1 : a < b ? -1 : 0;
+}
+
+static int
+cmp_ll(const void *v1, const void *v2)
+{
+	const long long a = *(const long long *)v1;
+	const long long b = *(const long long *)v2;
+
+	return a > b ? 1 : a < b ? -1 : 0;
+}
+
+static int
+cmp_checked_ll(const void *v1, const void *v2)
+{
+	const long long a = *(const long long *)v1;
+	const long long b = *(const long long *)v2;
+
+	compares++;
+	if (compares > abrt_compares)
+		siglongjmp(cmpjmp, 1);
+	return a > b ? 1 : a < b ? -1 : 0;
+}
+
+static int
+cmp_d(const void *v1, const void *v2)
+{
+	const double a = *(const double *)v1;
+	const double b = *(const double *)v2;
+
+	return a > b ? 1 : a < b ? -1 : 0;
+}
+
+static int
+cmp_checked_d(const void *v1, const void *v2)
+{
+	const double a = *(const double *)v1;
+	const double b = *(const double *)v2;
+
+	compares++;
+	if (compares > abrt_compares)
+		siglongjmp(cmpjmp, 1);
+	return a > b ? 1 : a < b ? -1 : 0;
+}
+
+static int
+check_result(char *sub, size_t es, char *got, char *expected, struct test_distribution *d,
+    int m, int n)
+{
+	int i;
+
+	if (verbose || compares > max_compares) {
+		if (sub != NULL) {
+			if (m != 0) {
+				warnx("%s (%s): m: %d, n: %d, %zu compares, "
+				    "max %zu(%zu)", d->name, sub, m, n,
+				    compares, max_compares, abrt_compares);
+			} else {
+				warnx("%s (%s): n: %d, %zu compares, "
+				    "max %zu(%zu)", d->name, sub, n,
+				    compares, max_compares, abrt_compares);
+			}
+		} else {
+			if (m != 0) {
+				warnx("%s: m: %d, n: %d, %zu compares, "
+				    "max %zu(%zu)", d->name, m, n,
+				    compares, max_compares, abrt_compares);
+			} else {
+				warnx("%s: n: %d, %zu compares, "
+				    "max %zu(%zu)", d->name, n,
+				    compares, max_compares, abrt_compares);
+			}
+		}
+	}
+
+	for (i = 0; i < n; i++) {
+		if (memcmp(got, expected, es) != 0)
+			break;
+		got += es;
+		expected += es;
+	}
+	if (i == n)
+		return 0;
+
+	if (sub != NULL) {
+		warnx("%s (%s): failure at %d, m: %d, n: %d",
+		    d->name, sub, i, m, n);
+	} else {
+		warnx("%s: failure at %d, m: %d, n: %d",
+		    d->name, i, m, n);
+	}
+	return 1;
+}
+
+#define FILL_SAWTOOTH(x, n, m)	do {					\
+	int i;								\
+									\
+	for (i = 0; i < n; i++)						\
+		x[i] = i % m;						\
+} while (0)
+
+static void
+fill_sawtooth_i(void *v, int n, int m)
+{
+	int *x = v;
+	FILL_SAWTOOTH(x, n, m);
+}
+
+static void
+fill_sawtooth_ll(void *v, int n, int m)
+{
+	long long *x = v;
+	FILL_SAWTOOTH(x, n, m);
+}
+
+static void
+fill_sawtooth_double(void *v, int n, int m)
+{
+	double *x = v;
+	FILL_SAWTOOTH(x, n, m);
+}
+
+#define FILL_RANDOM(x, n, m)	do {					\
+	int i;								\
+									\
+	for (i = 0; i < n; i++)						\
+		x[i] = arc4random_uniform(m);				\
+} while (0)
+
+
+static void
+fill_random_i(void *v, int n, int m)
+{
+	int *x = v;
+	FILL_RANDOM(x, n, m);
+}
+
+static void
+fill_random_ll(void *v, int n, int m)
+{
+	long long *x = v;
+	FILL_RANDOM(x, n, m);
+}
+
+static void
+fill_random_double(void *v, int n, int m)
+{
+	double *x = v;
+	FILL_RANDOM(x, n, m);
+}
+
+#define FILL_STAGGER(x, n, m)	do {					\
+	int i;								\
+									\
+	for (i = 0; i < n; i++)						\
+		x[i] = (i * m + i) % n;					\
+} while (0)
+
+
+static void
+fill_stagger_i(void *v, int n, int m)
+{
+	int *x = v;
+	FILL_STAGGER(x, n, m);
+}
+
+static void
+fill_stagger_ll(void *v, int n, int m)
+{
+	long long *x = v;
+	FILL_STAGGER(x, n, m);
+}
+
+static void
+fill_stagger_double(void *v, int n, int m)
+{
+	double *x = v;
+	FILL_STAGGER(x, n, m);
+}
+
+#define FILL_PLATEAU(x, n, m)	do {					\
+	int i;								\
+									\
+	for (i = 0; i < n; i++)						\
+		x[i] = MINIMUM(i, m);					\
+} while (0)
+
+static void
+fill_plateau_i(void *v, int n, int m)
+{
+	int *x = v;
+	FILL_PLATEAU(x, n, m);
+}
+
+static void
+fill_plateau_ll(void *v, int n, int m)
+{
+	long long *x = v;
+	FILL_PLATEAU(x, n, m);
+}
+
+static void
+fill_plateau_double(void *v, int n, int m)
+{
+	double *x = v;
+	FILL_PLATEAU(x, n, m);
+}
+
+#define FILL_SHUFFLE(x, n, m)	do {					\
+	int i, j, k;							\
+									\
+	for (i = 0, j = 0, k = 1; i < n; i++)				\
+		x[i] = arc4random_uniform(m) ? (j += 2) : (k += 2);	\
+} while (0)
+
+static void
+fill_shuffle_i(void *v, int n, int m)
+{
+	int *x = v;
+	FILL_SHUFFLE(x, n, m);
+}
+
+static void
+fill_shuffle_ll(void *v, int n, int m)
+{
+	long long *x = v;
+	FILL_SHUFFLE(x, n, m);
+}
+
+static void
+fill_shuffle_double(void *v, int n, int m)
+{
+	double *x = v;
+	FILL_SHUFFLE(x, n, m);
+}
+
+#define FILL_BSD_KILLER(x, n, m)	do {				\
+	int i, k;							\
+									\
+	/* 4.4BSD insertion sort optimization killer, Mats Linander */	\
+	k = n / 2;							\
+	for (i = 0; i < n; i++) {					\
+		if (i < k)						\
+			x[i] = k - i;					\
+		else if (i > k)						\
+			x[i] = n + k + 1 - i;				\
+		else							\
+			x[i] = k + 1;					\
+	}								\
+} while (0)
+
+static void
+fill_bsd_killer_i(void *v, int n, int m)
+{
+	int *x = v;
+	FILL_BSD_KILLER(x, n, m);
+
+}
+
+static void
+fill_bsd_killer_ll(void *v, int n, int m)
+{
+	long long *x = v;
+	FILL_BSD_KILLER(x, n, m);
+
+}
+
+static void
+fill_bsd_killer_double(void *v, int n, int m)
+{
+	double *x = v;
+	FILL_BSD_KILLER(x, n, m);
+
+}
+
+#define FILL_MED3_KILLER(x, n, m)	do {				\
+	int i, k;							\
+									\
+	/*								\
+	 * Median of 3 killer, as seen in David R Musser's		\
+	 * "Introspective Sorting and Selection Algorithms"		\
+	 */								\
+	if (n & 1) {							\
+		/* odd size, store last at end and make even. */	\
+		x[n - 1] = n;						\
+		n--;							\
+	}								\
+	k = n / 2;							\
+	for (i = 0; i < n; i++) {					\
+		if (i & 1) {						\
+			x[i] = k + x[i - 1];				\
+		} else {						\
+			x[i] = i + 1;					\
+		}							\
+	}								\
+} while (0)
+
+static void
+fill_med3_killer_i(void *v, int n, int m)
+{
+	int *x = v;
+	FILL_MED3_KILLER(x, n, m);
+}
+
+static void
+fill_med3_killer_ll(void *v, int n, int m)
+{
+	long long *x = v;
+	FILL_MED3_KILLER(x, n, m);
+}
+
+static void
+fill_med3_killer_double(void *v, int n, int m)
+{
+	double *x = v;
+	FILL_MED3_KILLER(x, n, m);
+}
+
+static void
+print_timing(struct test_distribution *d, char *sub, int m, int n, double elapsed)
+{
+	if (sub != NULL) {
+		if (m != 0) {
+			warnx("%s (%s): m: %d, n: %d, %f seconds",
+			    d->name, sub, m, n, elapsed);
+		} else {
+			warnx("%s (%s): n: %d, %f seconds",
+			    d->name, sub, n, elapsed);
+		}
+	} else {
+		if (m != 0) {
+			warnx("%s: m: %d, n: %d, %f seconds",
+			    d->name, m, n, elapsed);
+		} else {
+			warnx("%s: n: %d, %f seconds",
+			    d->name, n, elapsed);
+		}
+	}
+}
+
+static int
+do_test(struct test_distribution *d, char *sub, int m, int n, size_t es, void *y, void *z)
+{
+	int ret = 0;
+	struct timespec before, after;
+
+	compares = 0;
+	if (sigsetjmp(cmpjmp, 1) != 0) {
+		if (sub != NULL) {
+			warnx("%s (%s): qsort aborted after %zu compares, m: %d, n: %d",
+			    d->name, sub, compares, m, n);
+		} else {
+			warnx("%s: qsort aborted after %zu compares, m: %d, n: %d",
+			    d->name, compares, m, n);
+		}
+		ret = 1;
+	} else {
+		if (timing)
+			(void) clock_gettime(CLOCK_MONOTONIC, &before);
+		qsort(y, n, es, d->cmp_checked);
+		if (timing) {
+			double elapsed;
+			(void) clock_gettime(CLOCK_MONOTONIC, &after);
+			timespecsub(&after, &before, &after);
+			elapsed = after.tv_sec + after.tv_nsec / 1000000000.0;
+			print_timing(d, sub, m, n, elapsed);
+		}
+		if (check_result(sub, es, y, z, d, m, n) != 0)
+			ret = 1;
+	}
+	return ret;
+}
+
+#define TEST_PERTURBED(d, n, x, y, z)	do {				\
+	int i, j, m;							\
+	const int es = sizeof(x[0]);					\
+									\
+	for (m = 1; m < 2 * n; m *= 2) {				\
+		/* Fill in x[n] modified by m */			\
+		d->fill(x, n, m);					\
+									\
+		/* Test on copy of x[] */				\
+		for (i = 0; i < n; i++)					\
+			y[i] = z[i] = x[i];				\
+		if (mergesort(z, n, es, d->cmp) != 0)			\
+			err(1, NULL);					\
+		if (do_test(d, "copy", m, n, es, y, z) != 0)		\
+			ret = 1;					\
+									\
+		/* Test on reversed copy of x[] */			\
+		for (i = 0, j = n - 1; i < n; i++, j--)			\
+			y[i] = z[i] = x[j];				\
+		if (mergesort(z, n, es, d->cmp) != 0)			\
+			err(1, NULL);					\
+		if (do_test(d, "reversed", m, n, es, y, z) != 0)	\
+			ret = 1;					\
+									\
+		/* Test with front half of x[] reversed */		\
+		for (i = 0, j = (n / 2) - 1; i < n / 2; i++, j--)	\
+			y[i] = z[i] = x[j];				\
+		for (; i < n; i++)					\
+			y[i] = z[i] = x[i];				\
+		if (mergesort(z, n, es, d->cmp) != 0)			\
+			err(1, NULL);					\
+		if (do_test(d, "front reversed", m, n, es, y, z) != 0)	\
+			ret = 1;					\
+									\
+		/* Test with back half of x[] reversed */		\
+		for (i = 0; i < n / 2; i++)				\
+			y[i] = z[i] = x[i];				\
+		for (j = n - 1; i < n; i++, j--)			\
+			y[i] = z[i] = x[j];				\
+		if (mergesort(z, n, es, d->cmp) != 0)			\
+			err(1, NULL);					\
+		if (do_test(d, "back reversed", m, n, es, y, z) != 0)	\
+			ret = 1;					\
+									\
+		/* Test on sorted copy of x[] */			\
+		if (mergesort(x, n, es, d->cmp) != 0)			\
+			err(1, NULL);					\
+		for (i = 0; i < n; i++)					\
+			y[i] = x[i];					\
+		if (do_test(d, "sorted", m, n, es, y, x) != 0)		\
+			ret = 1;					\
+									\
+		/* Test with i%5 added to x[i] (dither) */		\
+		for (i = 0, j = n - 1; i < n; i++, j--)			\
+			y[i] = z[i] = x[j] + (i % 5);			\
+		if (mergesort(z, n, es, d->cmp) != 0)			\
+			err(1, NULL);					\
+		if (do_test(d, "dithered", m, n, es, y, z) != 0)	\
+			ret = 1;					\
+	}								\
+} while (0)
+
+static int
+test_perturbed_i(struct test_distribution *d, int n, void *vx, void *vy, void *vz)
+{
+	int *x = vx;
+	int *y = vx;
+	int *z = vz;
+	int ret = 0;
+
+	TEST_PERTURBED(d, n, x, y, z);
+	return ret;
+}
+
+static int
+test_perturbed_ll(struct test_distribution *d, int n, void *vx, void *vy, void *vz)
+{
+	long long *x = vx;
+	long long *y = vx;
+	long long *z = vz;
+	int ret = 0;
+
+	TEST_PERTURBED(d, n, x, y, z);
+	return ret;
+}
+
+static int
+test_perturbed_double(struct test_distribution *d, int n, void *vx, void *vy, void *vz)
+{
+	double *x = vx;
+	double *y = vx;
+	double *z = vz;
+	int ret = 0;
+
+	TEST_PERTURBED(d, n, x, y, z);
+	return ret;
+}
+
+/*
+ * Like TEST_PERTURBED but because the input is tailored to cause
+ * quicksort to go quadratic we don't perturb the input.
+ */
+#define TEST_SIMPLE(d, n, x, y, z)	do {				\
+	int i;								\
+									\
+	/* Fill in x[n] */						\
+	d->fill(x, n, 0);						\
+									\
+	/* Make a copy of x[] */					\
+	for (i = 0; i < n; i++)						\
+		y[i] = z[i] = x[i];					\
+	if (mergesort(z, n, sizeof(z[0]), d->cmp) != 0)			\
+		err(1, NULL);						\
+	if (do_test(d, NULL, 0, n, sizeof(x[0]), y, z) != 0)		\
+		ret = 1;						\
+} while (0)
+
+static int
+test_simple_i(struct test_distribution *d, int n, void *vx, void *vy, void *vz)
+{
+	int *x = vx;
+	int *y = vx;
+	int *z = vz;
+	int ret = 0;
+
+	TEST_SIMPLE(d, n, x, y, z);
+	return ret;
+}
+
+static int
+test_simple_ll(struct test_distribution *d, int n, void *vx, void *vy, void *vz)
+{
+	long long *x = vx;
+	long long *y = vx;
+	long long *z = vz;
+	int ret = 0;
+
+	TEST_SIMPLE(d, n, x, y, z);
+	return ret;
+}
+
+static int
+test_simple_double(struct test_distribution *d, int n, void *vx, void *vy, void *vz)
+{
+	double *x = vx;
+	double *y = vx;
+	double *z = vz;
+	int ret = 0;
+
+	TEST_SIMPLE(d, n, x, y, z);
+	return ret;
+}
+
+/*
+ * Use D. McIlroy's "Killer Adversary for Quicksort"
+ * We don't compare the results in this case.
+ */
+static int
+test_antiqsort(struct test_distribution *d, int n, void *vx, void *vy, void *vz)
+{
+	struct timespec before, after;
+	int *x = vx;
+	int *y = vx;
+	int i, ret = 0;
+
+	/*
+	 * We expect antiqsort to generate > 1.5 * nlgn compares.
+	 * If introspection is not used, it will be > 10 * nlgn compares.
+	 */
+	if (timing)
+		(void) clock_gettime(CLOCK_MONOTONIC, &before);
+	i = antiqsort(n, x, y);
+	if (timing)
+		(void) clock_gettime(CLOCK_MONOTONIC, &after);
+	if (i > abrt_compares)
+		ret = 1;
+	if (dump_table) {
+		printf("/* %d items, %d compares */\n", n, i);
+		printf("static const int table_%d[] = {", n);
+		for (i = 0; i < n - 1; i++) {
+			if ((i % 12) == 0)
+				printf("\n\t");
+			printf("%4d, ", x[i]);
+		}
+		printf("%4d\n};\n", x[i]);
+	} else {
+		if (timing) {
+			double elapsed;
+			timespecsub(&after, &before, &after);
+			elapsed = after.tv_sec + after.tv_nsec / 1000000000.0;
+			print_timing(d, NULL, 0, n, elapsed);
+		}
+		if (verbose || ret != 0) {
+			warnx("%s: n: %d, %d compares, max %zu(%zu)",
+			    d->name, n, i, max_compares, abrt_compares);
+		}
+	}
+
+	return ret;
+}
+
+static struct test_distribution distributions[] = {
+	{ "sawtooth_i", fill_sawtooth_i, test_perturbed_i, cmp_i, cmp_checked_i },
+	{ "sawtooth_ll", fill_sawtooth_ll, test_perturbed_ll, cmp_ll, cmp_checked_ll },
+	{ "sawtooth_d", fill_sawtooth_double, test_perturbed_double, cmp_d, cmp_checked_d },
+	{ "random_i", fill_random_i, test_perturbed_i, cmp_i, cmp_checked_i },
+	{ "random_ll", fill_random_ll, test_perturbed_ll, cmp_ll, cmp_checked_ll },
+	{ "random_d", fill_random_double, test_perturbed_double, cmp_d, cmp_checked_d },
+	{ "stagger_i", fill_stagger_i, test_perturbed_i, cmp_i, cmp_checked_i },
+	{ "stagger_ll", fill_stagger_ll, test_perturbed_ll, cmp_ll, cmp_checked_ll },
+	{ "stagger_d", fill_stagger_double, test_perturbed_double, cmp_d, cmp_checked_d },
+	{ "plateau_i", fill_plateau_i, test_perturbed_i, cmp_i, cmp_checked_i },
+	{ "plateau_ll", fill_plateau_ll, test_perturbed_ll, cmp_ll, cmp_checked_ll },
+	{ "plateau_d", fill_plateau_double, test_perturbed_double, cmp_d, cmp_checked_d },
+	{ "shuffle_i", fill_shuffle_i, test_perturbed_i, cmp_i, cmp_checked_i },
+	{ "shuffle_ll", fill_shuffle_ll, test_perturbed_ll, cmp_ll, cmp_checked_ll },
+	{ "shuffle_d", fill_shuffle_double, test_perturbed_double, cmp_d, cmp_checked_d },
+	{ "bsd_killer_i", fill_bsd_killer_i, test_simple_i, cmp_i, cmp_checked_i },
+	{ "bsd_killer_ll", fill_bsd_killer_ll, test_simple_ll, cmp_ll, cmp_checked_ll },
+	{ "bsd_killer_d", fill_bsd_killer_double, test_simple_double, cmp_d, cmp_checked_d },
+	{ "med3_killer_i", fill_med3_killer_i, test_simple_i, cmp_i, cmp_checked_i },
+	{ "med3_killer_ll", fill_med3_killer_ll, test_simple_ll, cmp_ll, cmp_checked_ll },
+	{ "med3_killer_d", fill_med3_killer_double, test_simple_double, cmp_d, cmp_checked_d },
+	{ "antiqsort", NULL, test_antiqsort, cmp_i, cmp_checked_i },
+	{ NULL }
+};
+
+static int
+run_tests(int n, const char *name)
+{
+	void *x, *y, *z;
+	int i, nlgn = 0;
+	int ret = 0;
+	size_t es;
+	struct test_distribution *d;
+
+	/*
+	 * We expect A*n*lg(n) compares where A is between 1 and 2.
+	 * For A > 1.5, print a warning.
+	 * For A > 10 abort the test since qsort has probably gone quadratic.
+	 */
+	for (i = n - 1; i > 0; i >>= 1)
+	    nlgn++;
+	nlgn *= n;
+	max_compares = nlgn * 1.5;
+	abrt_compares = nlgn * 10;
+
+	/* Allocate enough space to store ints or doubles. */
+	es = MAXIMUM(sizeof(int), sizeof(double));
+	x = reallocarray(NULL, n, es);
+	y = reallocarray(NULL, n, es);
+	z = reallocarray(NULL, n, es);
+	if (x == NULL || y == NULL || z == NULL)
+		err(1, NULL);
+
+	for (d = distributions; d->name != NULL; d++) {
+		if (name != NULL && strncmp(name, d->name, strlen(name)) != 0)
+			continue;
+		if (d->test(d, n, x, y, z) != 0)
+			ret = 1;
+	}
+
+	free(x);
+	free(y);
+	free(z);
+	return ret;
+}
+
+void
+usage(void)
+{
+        fprintf(stderr, "usage: qsort_test [-dvt] [-n test_name] [num ...]\n");
+	exit(1);
+}
+
+int
+main(int argc, char *argv[])
+{
+	char *nums[] = { "100", "1023", "1024", "1025", "4095", "4096", "4097" };
+	struct test_distribution *d;
+	int ch, n, ret = 0;
+	char *name = NULL;
+
+        while ((ch = getopt(argc, argv, "dn:tv")) != -1) {
+                switch (ch) {
+                case 'd':
+                        dump_table = true;
+                        break;
+                case 'n':
+			for (d = distributions; d->name != NULL; d++) {
+				if (strncmp(optarg, d->name, strlen(optarg)) == 0)
+					break;
+			}
+			if (d->name == NULL)
+				errx(1, "unknown test %s", optarg);
+                        name = optarg;
+                        break;
+                case 't':
+                        timing = true;
+                        break;
+                case 'v':
+                        verbose = true;
+                        break;
+                default:
+                        usage();
+                        break;
+                }
+        }
+        argc -= optind;
+        argv += optind;
+
+	if (argc == 0) {
+		argv = nums;
+		argc = sizeof(nums) / sizeof(nums[0]);
+	}
+
+	while (argc > 0) {
+		n = atoi(*argv);
+		if (run_tests(n, name) != 0)
+			ret = 1;
+		argc--;
+		argv++;
+	}
+
+	return ret;
+}