From owner-svn-src-all@freebsd.org Wed Oct 16 09:20:10 2019 Return-Path: Delivered-To: svn-src-all@mailman.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.nyi.freebsd.org (Postfix) with ESMTP id 8859B160244; Wed, 16 Oct 2019 09:20:10 +0000 (UTC) (envelope-from avg@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) server-signature RSA-PSS (4096 bits) client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "Let's Encrypt Authority X3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 46tRbG35HNz4V4V; Wed, 16 Oct 2019 09:20:10 +0000 (UTC) (envelope-from avg@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 48CE14D8D; Wed, 16 Oct 2019 09:20:10 +0000 (UTC) (envelope-from avg@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id x9G9KAY2077464; Wed, 16 Oct 2019 09:20:10 GMT (envelope-from avg@FreeBSD.org) Received: (from avg@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id x9G9K8pt077452; Wed, 16 Oct 2019 09:20:08 GMT (envelope-from avg@FreeBSD.org) Message-Id: <201910160920.x9G9K8pt077452@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: avg set sender to avg@FreeBSD.org using -f From: Andriy Gapon Date: Wed, 16 Oct 2019 09:20:08 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r353636 - in head/sys/cddl/contrib/opensolaris/uts/common: fs/zfs sys X-SVN-Group: head X-SVN-Commit-Author: avg X-SVN-Commit-Paths: in head/sys/cddl/contrib/opensolaris/uts/common: fs/zfs sys X-SVN-Commit-Revision: 353636 X-SVN-Commit-Repository: base MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 16 Oct 2019 09:20:10 -0000 Author: avg Date: Wed Oct 16 09:20:08 2019 New Revision: 353636 URL: https://svnweb.freebsd.org/changeset/base/353636 Log: MFV r353630: 10809 Performance optimization of AVL tree comparator functions illumos/illumos-gate@c4ab0d3f46036e85ad0700125c5a83cc139f55a3 https://github.com/illumos/illumos-gate/commit/c4ab0d3f46036e85ad0700125c5a83cc139f55a3 https://www.illumos.org/issues/10809 Port ZoL ee36c709c3d Performance optimization of AVL tree comparator functions This is a followup to r337567 that imported the ZoL commit directly into FreeBSD. It seems that at the time we did not have some of the earlier changes, so some pieces of the ZoL change were not applicable. Also, the illumos version got a few style cleanups. Some changes were missed or incorrectly merged (e.g., vdev_cache_lastused_compare and metaslab_rangesize_compare). Obtained from: ZoL, illumos MFC after: 25 days X-MFC after: r353634 Modified: head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/ddt.c head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/lz4.c head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/metaslab.c head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/range_tree.c head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/vdev_cache.c head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/vdev_queue.c head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/zfs_rlock.c head/sys/cddl/contrib/opensolaris/uts/common/sys/avl.h Directory Properties: head/cddl/contrib/opensolaris/ (props changed) head/sys/cddl/contrib/opensolaris/ (props changed) Modified: head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/ddt.c ============================================================================== --- head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/ddt.c Wed Oct 16 09:11:49 2019 (r353635) +++ head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/ddt.c Wed Oct 16 09:20:08 2019 (r353636) @@ -768,22 +768,31 @@ ddt_prefetch(spa_t *spa, const blkptr_t *bp) } } +/* + * Opaque struct used for ddt_key comparison + */ +#define DDT_KEY_CMP_LEN (sizeof (ddt_key_t) / sizeof (uint16_t)) + +typedef struct ddt_key_cmp { + uint16_t u16[DDT_KEY_CMP_LEN]; +} ddt_key_cmp_t; + int ddt_entry_compare(const void *x1, const void *x2) { const ddt_entry_t *dde1 = x1; const ddt_entry_t *dde2 = x2; - const uint64_t *u1 = (const uint64_t *)&dde1->dde_key; - const uint64_t *u2 = (const uint64_t *)&dde2->dde_key; + const ddt_key_cmp_t *k1 = (const ddt_key_cmp_t *)&dde1->dde_key; + const ddt_key_cmp_t *k2 = (const ddt_key_cmp_t *)&dde2->dde_key; + int32_t cmp = 0; - for (int i = 0; i < DDT_KEY_WORDS; i++) { - if (u1[i] < u2[i]) - return (-1); - if (u1[i] > u2[i]) - return (1); + for (int i = 0; i < DDT_KEY_CMP_LEN; i++) { + cmp = (int32_t)k1->u16[i] - (int32_t)k2->u16[i]; + if (likely(cmp)) + break; } - return (0); + return (AVL_ISIGN(cmp)); } static ddt_t * Modified: head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/lz4.c ============================================================================== --- head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/lz4.c Wed Oct 16 09:11:49 2019 (r353635) +++ head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/lz4.c Wed Oct 16 09:20:08 2019 (r353636) @@ -259,8 +259,13 @@ lz4_decompress(void *s_start, void *d_start, size_t s_ #undef unlikely #endif +#ifndef likely #define likely(expr) expect((expr) != 0, 1) +#endif + +#ifndef unlikely #define unlikely(expr) expect((expr) != 0, 0) +#endif /* Basic types */ #define BYTE uint8_t Modified: head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/metaslab.c ============================================================================== --- head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/metaslab.c Wed Oct 16 09:11:49 2019 (r353635) +++ head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/metaslab.c Wed Oct 16 09:20:08 2019 (r353636) @@ -1203,9 +1203,6 @@ metaslab_rangesize_compare(const void *x1, const void if (likely(cmp)) return (cmp); - if (r1->rs_start < r2->rs_start) - return (-1); - return (AVL_CMP(r1->rs_start, r2->rs_start)); } Modified: head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/range_tree.c ============================================================================== --- head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/range_tree.c Wed Oct 16 09:11:49 2019 (r353635) +++ head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/range_tree.c Wed Oct 16 09:20:08 2019 (r353636) @@ -164,7 +164,7 @@ range_tree_seg_compare(const void *x1, const void *x2) ASSERT3U(r1->rs_start, <=, r1->rs_end); ASSERT3U(r2->rs_start, <=, r2->rs_end); - + return ((r1->rs_start >= r2->rs_end) - (r1->rs_end <= r2->rs_start)); } Modified: head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/vdev_cache.c ============================================================================== --- head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/vdev_cache.c Wed Oct 16 09:11:49 2019 (r353635) +++ head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/vdev_cache.c Wed Oct 16 09:20:08 2019 (r353636) @@ -114,29 +114,24 @@ static vdc_stats_t vdc_stats = { #define VDCSTAT_BUMP(stat) atomic_inc_64(&vdc_stats.stat.value.ui64); -static int +static inline int vdev_cache_offset_compare(const void *a1, const void *a2) { - const vdev_cache_entry_t *ve1 = a1; - const vdev_cache_entry_t *ve2 = a2; + const vdev_cache_entry_t *ve1 = (const vdev_cache_entry_t *)a1; + const vdev_cache_entry_t *ve2 = (const vdev_cache_entry_t *)a2; - if (ve1->ve_offset < ve2->ve_offset) - return (-1); - if (ve1->ve_offset > ve2->ve_offset) - return (1); - return (0); + return (AVL_CMP(ve1->ve_offset, ve2->ve_offset)); } static int vdev_cache_lastused_compare(const void *a1, const void *a2) { - const vdev_cache_entry_t *ve1 = a1; - const vdev_cache_entry_t *ve2 = a2; + const vdev_cache_entry_t *ve1 = (const vdev_cache_entry_t *)a1; + const vdev_cache_entry_t *ve2 = (const vdev_cache_entry_t *)a2; - if (ve1->ve_lastused < ve2->ve_lastused) - return (-1); - if (ve1->ve_lastused > ve2->ve_lastused) - return (1); + int cmp = AVL_CMP(ve1->ve_lastused, ve2->ve_lastused); + if (likely(cmp)) + return (cmp); /* * Among equally old entries, sort by offset to ensure uniqueness. Modified: head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/vdev_queue.c ============================================================================== --- head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/vdev_queue.c Wed Oct 16 09:11:49 2019 (r353635) +++ head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/vdev_queue.c Wed Oct 16 09:20:08 2019 (r353636) @@ -353,25 +353,15 @@ vdev_queue_type_tree(vdev_queue_t *vq, zio_type_t t) int vdev_queue_timestamp_compare(const void *x1, const void *x2) { - const zio_t *z1 = x1; - const zio_t *z2 = x2; + const zio_t *z1 = (const zio_t *)x1; + const zio_t *z2 = (const zio_t *)x2; - if (z1->io_timestamp < z2->io_timestamp) - return (-1); - if (z1->io_timestamp > z2->io_timestamp) - return (1); + int cmp = AVL_CMP(z1->io_timestamp, z2->io_timestamp); - if (z1->io_offset < z2->io_offset) - return (-1); - if (z1->io_offset > z2->io_offset) - return (1); + if (likely(cmp)) + return (cmp); - if (z1 < z2) - return (-1); - if (z1 > z2) - return (1); - - return (0); + return (AVL_PCMP(z1, z2)); } void Modified: head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/zfs_rlock.c ============================================================================== --- head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/zfs_rlock.c Wed Oct 16 09:11:49 2019 (r353635) +++ head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/zfs_rlock.c Wed Oct 16 09:20:08 2019 (r353636) @@ -107,14 +107,10 @@ static int rangelock_compare(const void *arg1, const void *arg2) { - const locked_range_t *rl1 = arg1; - const locked_range_t *rl2 = arg2; + const locked_range_t *rl1 = (const locked_range_t *)arg1; + const locked_range_t *rl2 = (const locked_range_t *)arg2; - if (rl1->lr_offset > rl2->lr_offset) - return (1); - if (rl1->lr_offset < rl2->lr_offset) - return (-1); - return (0); + return (AVL_CMP(rl1->lr_offset, rl2->lr_offset)); } /* Modified: head/sys/cddl/contrib/opensolaris/uts/common/sys/avl.h ============================================================================== --- head/sys/cddl/contrib/opensolaris/uts/common/sys/avl.h Wed Oct 16 09:11:49 2019 (r353635) +++ head/sys/cddl/contrib/opensolaris/uts/common/sys/avl.h Wed Oct 16 09:20:08 2019 (r353636) @@ -105,6 +105,13 @@ extern "C" { * as is needed for any linked list implementation. */ +/* + * AVL comparator helpers + */ +#define AVL_ISIGN(a) (((a) > 0) - ((a) < 0)) +#define AVL_CMP(a, b) (((a) > (b)) - ((a) < (b))) +#define AVL_PCMP(a, b) \ + (((uintptr_t)(a) > (uintptr_t)(b)) - ((uintptr_t)(a) < (uintptr_t)(b))) /* * AVL comparator helpers