Skip site navigation (1)Skip section navigation (2) 
Date:      Sun, 10 Jun 2018 17:54:44 +0000 (UTC)
From:      Konstantin Belousov <kib@FreeBSD.org>
To:        src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org
Subject:   svn commit: r334928 - head/lib/libc/stdlib
Message-ID:  <201806101754.w5AHsi4r061028@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help 
Author: kib
Date: Sun Jun 10 17:54:44 2018
New Revision: 334928
URL: https://svnweb.freebsd.org/changeset/base/334928

Log:
  libc qsort(3): stop aliasing.
  
  Qsort swap code aliases the sorted array elements to ints and longs in
  order to do swap by machine words.  Unfortunately this breaks with the
  full code optimization, e.g. LTO.
  
  See https://gcc.gnu.org/bugzilla/show_bug.cgi?id=83201 which seems to
  reference code directly copied from libc/stdlib/qsort.c.
  
  PR:	228780
  Reported by:	mliska@suse.cz
  Reviewed by:	brooks
  Sponsored by:	The FreeBSD Foundation
  MFC after:	2 weeks
  Differential revision:	https://reviews.freebsd.org/D15714

Modified:
  head/lib/libc/stdlib/qsort.c

Modified: head/lib/libc/stdlib/qsort.c
==============================================================================
--- head/lib/libc/stdlib/qsort.c	Sun Jun 10 16:44:18 2018	(r334927)
+++ head/lib/libc/stdlib/qsort.c	Sun Jun 10 17:54:44 2018	(r334928)
@@ -43,53 +43,27 @@ typedef int		 cmp_t(void *, const void *, const void *
 typedef int		 cmp_t(const void *, const void *);
 #endif
 static inline char	*med3(char *, char *, char *, cmp_t *, void *);
-static inline void	 swapfunc(char *, char *, size_t, int, int);
 
 #define	MIN(a, b)	((a) < (b) ? a : b)
 
 /*
  * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
  */
-#define	swapcode(TYPE, parmi, parmj, n) {		\
-	size_t i = (n) / sizeof (TYPE);			\
-	TYPE *pi = (TYPE *) (parmi);		\
-	TYPE *pj = (TYPE *) (parmj);		\
-	do { 						\
-		TYPE	t = *pi;		\
-		*pi++ = *pj;				\
-		*pj++ = t;				\
-	} while (--i > 0);				\
-}
 
-#define	SWAPINIT(TYPE, a, es) swaptype_ ## TYPE =	\
-	((char *)a - (char *)0) % sizeof(TYPE) ||	\
-	es % sizeof(TYPE) ? 2 : es == sizeof(TYPE) ? 0 : 1;
-
 static inline void
-swapfunc(char *a, char *b, size_t n, int swaptype_long, int swaptype_int)
+swapfunc(char *a, char *b, size_t es)
 {
-	if (swaptype_long <= 1)
-		swapcode(long, a, b, n)
-	else if (swaptype_int <= 1)
-		swapcode(int, a, b, n)
-	else
-		swapcode(char, a, b, n)
+	char t;
+
+	do {
+		t = *a;
+		*a++ = *b;
+		*b++ = t;
+	} while (--es > 0);
 }
 
-#define	swap(a, b)					\
-	if (swaptype_long == 0) {			\
-		long t = *(long *)(a);			\
-		*(long *)(a) = *(long *)(b);		\
-		*(long *)(b) = t;			\
-	} else if (swaptype_int == 0) {			\
-		int t = *(int *)(a);			\
-		*(int *)(a) = *(int *)(b);		\
-		*(int *)(b) = t;			\
-	} else						\
-		swapfunc(a, b, es, swaptype_long, swaptype_int)
-
 #define	vecswap(a, b, n)				\
-	if ((n) > 0) swapfunc(a, b, n, swaptype_long, swaptype_int)
+	if ((n) > 0) swapfunc(a, b, n)
 
 #ifdef I_AM_QSORT_R
 #define	CMP(t, x, y) (cmp((t), (x), (y)))
@@ -121,17 +95,16 @@ qsort(void *a, size_t n, size_t es, cmp_t *cmp)
 	char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
 	size_t d1, d2;
 	int cmp_result;
-	int swaptype_long, swaptype_int, swap_cnt;
+	int swap_cnt;
 
-loop:	SWAPINIT(long, a, es);
-	SWAPINIT(int, a, es);
+loop:
 	swap_cnt = 0;
 	if (n < 7) {
 		for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
 			for (pl = pm; 
 			     pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
 			     pl -= es)
-				swap(pl, pl - es);
+				swapfunc(pl, pl - es, es);
 		return;
 	}
 	pm = (char *)a + (n / 2) * es;
@@ -147,7 +120,7 @@ loop:	SWAPINIT(long, a, es);
 		}
 		pm = med3(pl, pm, pn, cmp, thunk);
 	}
-	swap(a, pm);
+	swapfunc(a, pm, es);
 	pa = pb = (char *)a + es;
 
 	pc = pd = (char *)a + (n - 1) * es;
@@ -155,7 +128,7 @@ loop:	SWAPINIT(long, a, es);
 		while (pb <= pc && (cmp_result = CMP(thunk, pb, a)) <= 0) {
 			if (cmp_result == 0) {
 				swap_cnt = 1;
-				swap(pa, pb);
+				swapfunc(pa, pb, es);
 				pa += es;
 			}
 			pb += es;
@@ -163,14 +136,14 @@ loop:	SWAPINIT(long, a, es);
 		while (pb <= pc && (cmp_result = CMP(thunk, pc, a)) >= 0) {
 			if (cmp_result == 0) {
 				swap_cnt = 1;
-				swap(pc, pd);
+				swapfunc(pc, pd, es);
 				pd -= es;
 			}
 			pc -= es;
 		}
 		if (pb > pc)
 			break;
-		swap(pb, pc);
+		swapfunc(pb, pc, es);
 		swap_cnt = 1;
 		pb += es;
 		pc -= es;
@@ -180,7 +153,7 @@ loop:	SWAPINIT(long, a, es);
 			for (pl = pm; 
 			     pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
 			     pl -= es)
-				swap(pl, pl - es);
+				swapfunc(pl, pl - es, es);
 		return;
 	}

Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201806101754.w5AHsi4r061028>