From owner-svn-src-all@freebsd.org Fri Aug 3 01:52:27 2018 Return-Path: Delivered-To: svn-src-all@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 E3B651058B7E; Fri, 3 Aug 2018 01:52:26 +0000 (UTC) (envelope-from mav@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 97F0D8AC15; Fri, 3 Aug 2018 01:52:26 +0000 (UTC) (envelope-from mav@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 78CEE19FF1; Fri, 3 Aug 2018 01:52:26 +0000 (UTC) (envelope-from mav@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id w731qQDE091271; Fri, 3 Aug 2018 01:52:26 GMT (envelope-from mav@FreeBSD.org) Received: (from mav@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id w731qPpL091267; Fri, 3 Aug 2018 01:52:25 GMT (envelope-from mav@FreeBSD.org) Message-Id: <201808030152.w731qPpL091267@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: mav set sender to mav@FreeBSD.org using -f From: Alexander Motin Date: Fri, 3 Aug 2018 01:52:25 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r337227 - in head: cddl/contrib/opensolaris/lib/libnvpair sys/cddl/contrib/opensolaris/common/nvpair sys/cddl/contrib/opensolaris/uts/common/sys X-SVN-Group: head X-SVN-Commit-Author: mav X-SVN-Commit-Paths: in head: cddl/contrib/opensolaris/lib/libnvpair sys/cddl/contrib/opensolaris/common/nvpair sys/cddl/contrib/opensolaris/uts/common/sys X-SVN-Commit-Revision: 337227 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.27 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: Fri, 03 Aug 2018 01:52:27 -0000 Author: mav Date: Fri Aug 3 01:52:25 2018 New Revision: 337227 URL: https://svnweb.freebsd.org/changeset/base/337227 Log: MFV r337223: 9580 Add a hash-table on top of nvlist to speed-up operations illumos/illumos-gate@2ec7644aab2a726a64681fa66c6db8731b160de1 Reviewed by: Matt Ahrens Reviewed by: Sebastien Roy Approved by: Robert Mustacchi Author: Serapheim Dimitropoulos Modified: head/cddl/contrib/opensolaris/lib/libnvpair/nvpair_json.c head/sys/cddl/contrib/opensolaris/common/nvpair/opensolaris_nvpair.c head/sys/cddl/contrib/opensolaris/uts/common/sys/nvpair.h head/sys/cddl/contrib/opensolaris/uts/common/sys/nvpair_impl.h Directory Properties: head/cddl/contrib/opensolaris/ (props changed) head/sys/cddl/contrib/opensolaris/ (props changed) Modified: head/cddl/contrib/opensolaris/lib/libnvpair/nvpair_json.c ============================================================================== --- head/cddl/contrib/opensolaris/lib/libnvpair/nvpair_json.c Fri Aug 3 01:51:44 2018 (r337226) +++ head/cddl/contrib/opensolaris/lib/libnvpair/nvpair_json.c Fri Aug 3 01:52:25 2018 (r337227) @@ -10,6 +10,7 @@ */ /* * Copyright (c) 2014, Joyent, Inc. + * Copyright (c) 2017 by Delphix. All rights reserved. */ #include @@ -394,8 +395,10 @@ nvlist_print_json(FILE *fp, nvlist_t *nvl) } case DATA_TYPE_UNKNOWN: + case DATA_TYPE_DONTCARE: return (-1); } + } FPRINTF(fp, "}"); Modified: head/sys/cddl/contrib/opensolaris/common/nvpair/opensolaris_nvpair.c ============================================================================== --- head/sys/cddl/contrib/opensolaris/common/nvpair/opensolaris_nvpair.c Fri Aug 3 01:51:44 2018 (r337226) +++ head/sys/cddl/contrib/opensolaris/common/nvpair/opensolaris_nvpair.c Fri Aug 3 01:52:25 2018 (r337227) @@ -149,6 +149,8 @@ int nvpair_max_recursion = 20; int nvpair_max_recursion = 100; #endif +uint64_t nvlist_hashtable_init_size = (1 << 4); + int nv_alloc_init(nv_alloc_t *nva, const nv_alloc_ops_t *nvo, /* args */ ...) { @@ -256,7 +258,292 @@ nv_priv_alloc_embedded(nvpriv_t *priv) return (emb_priv); } +static int +nvt_tab_alloc(nvpriv_t *priv, uint64_t buckets) +{ + ASSERT3P(priv->nvp_hashtable, ==, NULL); + ASSERT0(priv->nvp_nbuckets); + ASSERT0(priv->nvp_nentries); + + i_nvp_t **tab = nv_mem_zalloc(priv, buckets * sizeof (i_nvp_t *)); + if (tab == NULL) + return (ENOMEM); + + priv->nvp_hashtable = tab; + priv->nvp_nbuckets = buckets; + return (0); +} + static void +nvt_tab_free(nvpriv_t *priv) +{ + i_nvp_t **tab = priv->nvp_hashtable; + if (tab == NULL) { + ASSERT0(priv->nvp_nbuckets); + ASSERT0(priv->nvp_nentries); + return; + } + + nv_mem_free(priv, tab, priv->nvp_nbuckets * sizeof (i_nvp_t *)); + + priv->nvp_hashtable = NULL; + priv->nvp_nbuckets = 0; + priv->nvp_nentries = 0; +} + +static uint32_t +nvt_hash(const char *p) +{ + uint32_t g, hval = 0; + + while (*p) { + hval = (hval << 4) + *p++; + if ((g = (hval & 0xf0000000)) != 0) + hval ^= g >> 24; + hval &= ~g; + } + return (hval); +} + +static boolean_t +nvt_nvpair_match(nvpair_t *nvp1, nvpair_t *nvp2, uint32_t nvflag) +{ + boolean_t match = B_FALSE; + if (nvflag & NV_UNIQUE_NAME_TYPE) { + if (strcmp(NVP_NAME(nvp1), NVP_NAME(nvp2)) == 0 && + NVP_TYPE(nvp1) == NVP_TYPE(nvp2)) + match = B_TRUE; + } else { + ASSERT(nvflag == 0 || nvflag & NV_UNIQUE_NAME); + if (strcmp(NVP_NAME(nvp1), NVP_NAME(nvp2)) == 0) + match = B_TRUE; + } + return (match); +} + +static nvpair_t * +nvt_lookup_name_type(nvlist_t *nvl, const char *name, data_type_t type) +{ + nvpriv_t *priv = (nvpriv_t *)(uintptr_t)nvl->nvl_priv; + ASSERT(priv != NULL); + + i_nvp_t **tab = priv->nvp_hashtable; + + if (tab == NULL) { + ASSERT3P(priv->nvp_list, ==, NULL); + ASSERT0(priv->nvp_nbuckets); + ASSERT0(priv->nvp_nentries); + return (NULL); + } else { + ASSERT(priv->nvp_nbuckets != 0); + } + + uint64_t hash = nvt_hash(name); + uint64_t index = hash & (priv->nvp_nbuckets - 1); + + ASSERT3U(index, <, priv->nvp_nbuckets); + i_nvp_t *entry = tab[index]; + + for (i_nvp_t *e = entry; e != NULL; e = e->nvi_hashtable_next) { + if (strcmp(NVP_NAME(&e->nvi_nvp), name) == 0 && + (type == DATA_TYPE_DONTCARE || + NVP_TYPE(&e->nvi_nvp) == type)) + return (&e->nvi_nvp); + } + return (NULL); +} + +static nvpair_t * +nvt_lookup_name(nvlist_t *nvl, const char *name) +{ + return (nvt_lookup_name_type(nvl, name, DATA_TYPE_DONTCARE)); +} + +static int +nvt_resize(nvpriv_t *priv, uint32_t new_size) +{ + i_nvp_t **tab = priv->nvp_hashtable; + + /* + * Migrate all the entries from the current table + * to a newly-allocated table with the new size by + * re-adjusting the pointers of their entries. + */ + uint32_t size = priv->nvp_nbuckets; + uint32_t new_mask = new_size - 1; + ASSERT(((new_size) & ((new_size) - 1)) == 0); + + i_nvp_t **new_tab = nv_mem_zalloc(priv, new_size * sizeof (i_nvp_t *)); + if (new_tab == NULL) + return (ENOMEM); + + uint32_t nentries = 0; + for (uint32_t i = 0; i < size; i++) { + i_nvp_t *next, *e = tab[i]; + + while (e != NULL) { + next = e->nvi_hashtable_next; + + uint32_t hash = nvt_hash(NVP_NAME(&e->nvi_nvp)); + uint32_t index = hash & new_mask; + + e->nvi_hashtable_next = new_tab[index]; + new_tab[index] = e; + nentries++; + + e = next; + } + tab[i] = NULL; + } + ASSERT3U(nentries, ==, priv->nvp_nentries); + + nvt_tab_free(priv); + + priv->nvp_hashtable = new_tab; + priv->nvp_nbuckets = new_size; + priv->nvp_nentries = nentries; + + return (0); +} + +static boolean_t +nvt_needs_togrow(nvpriv_t *priv) +{ + /* + * Grow only when we have more elements than buckets + * and the # of buckets doesn't overflow. + */ + return (priv->nvp_nentries > priv->nvp_nbuckets && + (UINT32_MAX >> 1) >= priv->nvp_nbuckets); +} + +/* + * Allocate a new table that's twice the size of the old one, + * and migrate all the entries from the old one to the new + * one by re-adjusting their pointers. + */ +static int +nvt_grow(nvpriv_t *priv) +{ + uint32_t current_size = priv->nvp_nbuckets; + /* ensure we won't overflow */ + ASSERT3U(UINT32_MAX >> 1, >=, current_size); + return (nvt_resize(priv, current_size << 1)); +} + +static boolean_t +nvt_needs_toshrink(nvpriv_t *priv) +{ + /* + * Shrink only when the # of elements is less than or + * equal to 1/4 the # of buckets. Never shrink less than + * nvlist_hashtable_init_size. + */ + ASSERT3U(priv->nvp_nbuckets, >=, nvlist_hashtable_init_size); + if (priv->nvp_nbuckets == nvlist_hashtable_init_size) + return (B_FALSE); + return (priv->nvp_nentries <= (priv->nvp_nbuckets >> 2)); +} + +/* + * Allocate a new table that's half the size of the old one, + * and migrate all the entries from the old one to the new + * one by re-adjusting their pointers. + */ +static int +nvt_shrink(nvpriv_t *priv) +{ + uint32_t current_size = priv->nvp_nbuckets; + /* ensure we won't overflow */ + ASSERT3U(current_size, >=, nvlist_hashtable_init_size); + return (nvt_resize(priv, current_size >> 1)); +} + +static int +nvt_remove_nvpair(nvlist_t *nvl, nvpair_t *nvp) +{ + nvpriv_t *priv = (nvpriv_t *)(uintptr_t)nvl->nvl_priv; + + if (nvt_needs_toshrink(priv)) { + int err = nvt_shrink(priv); + if (err != 0) + return (err); + } + i_nvp_t **tab = priv->nvp_hashtable; + + char *name = NVP_NAME(nvp); + uint64_t hash = nvt_hash(name); + uint64_t index = hash & (priv->nvp_nbuckets - 1); + + ASSERT3U(index, <, priv->nvp_nbuckets); + i_nvp_t *bucket = tab[index]; + + for (i_nvp_t *prev = NULL, *e = bucket; + e != NULL; prev = e, e = e->nvi_hashtable_next) { + if (nvt_nvpair_match(&e->nvi_nvp, nvp, nvl->nvl_flag)) { + if (prev != NULL) { + prev->nvi_hashtable_next = + e->nvi_hashtable_next; + } else { + ASSERT3P(e, ==, bucket); + tab[index] = e->nvi_hashtable_next; + } + e->nvi_hashtable_next = NULL; + priv->nvp_nentries--; + break; + } + } + + return (0); +} + +static int +nvt_add_nvpair(nvlist_t *nvl, nvpair_t *nvp) +{ + nvpriv_t *priv = (nvpriv_t *)(uintptr_t)nvl->nvl_priv; + + /* initialize nvpair table now if it doesn't exist. */ + if (priv->nvp_hashtable == NULL) { + int err = nvt_tab_alloc(priv, nvlist_hashtable_init_size); + if (err != 0) + return (err); + } + + /* + * if we don't allow duplicate entries, make sure to + * unlink any existing entries from the table. + */ + if (nvl->nvl_nvflag != 0) { + int err = nvt_remove_nvpair(nvl, nvp); + if (err != 0) + return (err); + } + + if (nvt_needs_togrow(priv)) { + int err = nvt_grow(priv); + if (err != 0) + return (err); + } + i_nvp_t **tab = priv->nvp_hashtable; + + char *name = NVP_NAME(nvp); + uint64_t hash = nvt_hash(name); + uint64_t index = hash & (priv->nvp_nbuckets - 1); + + ASSERT3U(index, <, priv->nvp_nbuckets); + i_nvp_t *bucket = tab[index]; + + /* insert link at the beginning of the bucket */ + i_nvp_t *new_entry = NVPAIR2I_NVP(nvp); + ASSERT3P(new_entry->nvi_hashtable_next, ==, NULL); + new_entry->nvi_hashtable_next = bucket; + tab[index] = new_entry; + + priv->nvp_nentries++; + return (0); +} + +static void nvlist_init(nvlist_t *nvl, uint32_t nvflag, nvpriv_t *priv) { nvl->nvl_version = NV_VERSION; @@ -588,6 +875,7 @@ nvlist_free(nvlist_t *nvl) else nvl->nvl_priv = 0; + nvt_tab_free(priv); nv_mem_free(priv, priv, sizeof (nvpriv_t)); } @@ -648,26 +936,14 @@ nvlist_xdup(nvlist_t *nvl, nvlist_t **nvlp, nv_alloc_t int nvlist_remove_all(nvlist_t *nvl, const char *name) { - nvpriv_t *priv; - i_nvp_t *curr; int error = ENOENT; - if (nvl == NULL || name == NULL || - (priv = (nvpriv_t *)(uintptr_t)nvl->nvl_priv) == NULL) + if (nvl == NULL || name == NULL || nvl->nvl_priv == 0) return (EINVAL); - curr = priv->nvp_list; - while (curr != NULL) { - nvpair_t *nvp = &curr->nvi_nvp; - - curr = curr->nvi_next; - if (strcmp(name, NVP_NAME(nvp)) != 0) - continue; - - nvp_buf_unlink(nvl, nvp); - nvpair_free(nvp); - nvp_buf_free(nvl, nvp); - + nvpair_t *nvp; + while ((nvp = nvt_lookup_name(nvl, name)) != NULL) { + VERIFY0(nvlist_remove_nvpair(nvl, nvp)); error = 0; } @@ -680,28 +956,14 @@ nvlist_remove_all(nvlist_t *nvl, const char *name) int nvlist_remove(nvlist_t *nvl, const char *name, data_type_t type) { - nvpriv_t *priv; - i_nvp_t *curr; - - if (nvl == NULL || name == NULL || - (priv = (nvpriv_t *)(uintptr_t)nvl->nvl_priv) == NULL) + if (nvl == NULL || name == NULL || nvl->nvl_priv == 0) return (EINVAL); - curr = priv->nvp_list; - while (curr != NULL) { - nvpair_t *nvp = &curr->nvi_nvp; + nvpair_t *nvp = nvt_lookup_name_type(nvl, name, type); + if (nvp == NULL) + return (ENOENT); - if (strcmp(name, NVP_NAME(nvp)) == 0 && NVP_TYPE(nvp) == type) { - nvp_buf_unlink(nvl, nvp); - nvpair_free(nvp); - nvp_buf_free(nvl, nvp); - - return (0); - } - curr = curr->nvi_next; - } - - return (ENOENT); + return (nvlist_remove_nvpair(nvl, nvp)); } int @@ -710,6 +972,10 @@ nvlist_remove_nvpair(nvlist_t *nvl, nvpair_t *nvp) if (nvl == NULL || nvp == NULL) return (EINVAL); + int err = nvt_remove_nvpair(nvl, nvp); + if (err != 0) + return (err); + nvp_buf_unlink(nvl, nvp); nvpair_free(nvp); nvp_buf_free(nvl, nvp); @@ -987,6 +1253,12 @@ nvlist_add_common(nvlist_t *nvl, const char *name, else if (nvl->nvl_nvflag & NV_UNIQUE_NAME_TYPE) (void) nvlist_remove(nvl, name, type); + err = nvt_add_nvpair(nvl, nvp); + if (err != 0) { + nvpair_free(nvp); + nvp_buf_free(nvl, nvp); + return (err); + } nvp_buf_link(nvl, nvp); return (0); @@ -1336,25 +1608,17 @@ static int nvlist_lookup_common(nvlist_t *nvl, const char *name, data_type_t type, uint_t *nelem, void *data) { - nvpriv_t *priv; - nvpair_t *nvp; - i_nvp_t *curr; - - if (name == NULL || nvl == NULL || - (priv = (nvpriv_t *)(uintptr_t)nvl->nvl_priv) == NULL) + if (name == NULL || nvl == NULL || nvl->nvl_priv == 0) return (EINVAL); if (!(nvl->nvl_nvflag & (NV_UNIQUE_NAME | NV_UNIQUE_NAME_TYPE))) return (ENOTSUP); - for (curr = priv->nvp_list; curr != NULL; curr = curr->nvi_next) { - nvp = &curr->nvi_nvp; + nvpair_t *nvp = nvt_lookup_name_type(nvl, name, type); + if (nvp == NULL) + return (ENOENT); - if (strcmp(name, NVP_NAME(nvp)) == 0 && NVP_TYPE(nvp) == type) - return (nvpair_value_common(nvp, type, nelem, data)); - } - - return (ENOENT); + return (nvpair_value_common(nvp, type, nelem, data)); } int @@ -2112,6 +2376,12 @@ nvs_decode_pairs(nvstream_t *nvs, nvlist_t *nvl) return (EFAULT); } + err = nvt_add_nvpair(nvl, nvp); + if (err != 0) { + nvpair_free(nvp); + nvp_buf_free(nvl, nvp); + return (err); + } nvp_buf_link(nvl, nvp); } return (err); Modified: head/sys/cddl/contrib/opensolaris/uts/common/sys/nvpair.h ============================================================================== --- head/sys/cddl/contrib/opensolaris/uts/common/sys/nvpair.h Fri Aug 3 01:51:44 2018 (r337226) +++ head/sys/cddl/contrib/opensolaris/uts/common/sys/nvpair.h Fri Aug 3 01:52:25 2018 (r337227) @@ -20,7 +20,7 @@ */ /* * Copyright (c) 2000, 2010, Oracle and/or its affiliates. All rights reserved. - * Copyright (c) 2012 by Delphix. All rights reserved. + * Copyright (c) 2012, 2017 by Delphix. All rights reserved. */ #ifndef _SYS_NVPAIR_H @@ -39,6 +39,7 @@ extern "C" { #endif typedef enum { + DATA_TYPE_DONTCARE = -1, DATA_TYPE_UNKNOWN = 0, DATA_TYPE_BOOLEAN, DATA_TYPE_BYTE, Modified: head/sys/cddl/contrib/opensolaris/uts/common/sys/nvpair_impl.h ============================================================================== --- head/sys/cddl/contrib/opensolaris/uts/common/sys/nvpair_impl.h Fri Aug 3 01:51:44 2018 (r337226) +++ head/sys/cddl/contrib/opensolaris/uts/common/sys/nvpair_impl.h Fri Aug 3 01:52:25 2018 (r337227) @@ -24,11 +24,13 @@ * Use is subject to license terms. */ +/* + * Copyright (c) 2017 by Delphix. All rights reserved. + */ + #ifndef _NVPAIR_IMPL_H #define _NVPAIR_IMPL_H -#pragma ident "%Z%%M% %I% %E% SMI" - #ifdef __cplusplus extern "C" { #endif @@ -47,16 +49,27 @@ typedef struct i_nvp i_nvp_t; struct i_nvp { union { - uint64_t _nvi_align; /* ensure alignment */ + /* ensure alignment */ + uint64_t _nvi_align; + struct { - i_nvp_t *_nvi_next; /* pointer to next nvpair */ - i_nvp_t *_nvi_prev; /* pointer to prev nvpair */ + /* pointer to next nvpair */ + i_nvp_t *_nvi_next; + + /* pointer to prev nvpair */ + i_nvp_t *_nvi_prev; + + /* next pair in table bucket */ + i_nvp_t *_nvi_hashtable_next; } _nvi; } _nvi_un; - nvpair_t nvi_nvp; /* nvpair */ + + /* nvpair */ + nvpair_t nvi_nvp; }; #define nvi_next _nvi_un._nvi._nvi_next #define nvi_prev _nvi_un._nvi._nvi_prev +#define nvi_hashtable_next _nvi_un._nvi._nvi_hashtable_next typedef struct { i_nvp_t *nvp_list; /* linked list of nvpairs */ @@ -64,6 +77,10 @@ typedef struct { i_nvp_t *nvp_curr; /* current walker nvpair */ nv_alloc_t *nvp_nva; /* pluggable allocator */ uint32_t nvp_stat; /* internal state */ + + i_nvp_t **nvp_hashtable; /* table of entries used for lookup */ + uint32_t nvp_nbuckets; /* # of buckets in hash table */ + uint32_t nvp_nentries; /* # of entries in hash table */ } nvpriv_t; #ifdef __cplusplus