From owner-svn-src-head@freebsd.org Sun Jun 10 17:54:45 2018 Return-Path: Delivered-To: svn-src-head@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 3E2AC100B0C6; Sun, 10 Jun 2018 17:54:45 +0000 (UTC) (envelope-from kib@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client CN "mxrelay.nyi.freebsd.org", Issuer "Let's Encrypt Authority X3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id E73346EA88; Sun, 10 Jun 2018 17:54:44 +0000 (UTC) (envelope-from kib@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id C8729102F4; Sun, 10 Jun 2018 17:54:44 +0000 (UTC) (envelope-from kib@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id w5AHsit5061029; Sun, 10 Jun 2018 17:54:44 GMT (envelope-from kib@FreeBSD.org) Received: (from kib@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id w5AHsi4r061028; Sun, 10 Jun 2018 17:54:44 GMT (envelope-from kib@FreeBSD.org) Message-Id: <201806101754.w5AHsi4r061028@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: kib set sender to kib@FreeBSD.org using -f From: Konstantin Belousov Date: Sun, 10 Jun 2018 17:54:44 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r334928 - head/lib/libc/stdlib X-SVN-Group: head X-SVN-Commit-Author: kib X-SVN-Commit-Paths: head/lib/libc/stdlib X-SVN-Commit-Revision: 334928 X-SVN-Commit-Repository: base MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-head@freebsd.org X-Mailman-Version: 2.1.26 Precedence: list List-Id: SVN commit messages for the src tree for head/-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 10 Jun 2018 17:54:45 -0000 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; }