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 <m...@delphix.com>
Reviewed by: Sebastien Roy <sebastien....@delphix.com>
Approved by: Robert Mustacchi <r...@joyent.com>
Author: Serapheim Dimitropoulos <seraph...@delphix.com>
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 <stdio.h>
@@ -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
_______________________________________________
svn-src-head@freebsd.org mailing list
https://lists.freebsd.org/mailman/listinfo/svn-src-head
To unsubscribe, send any mail to "svn-src-head-unsubscr...@freebsd.org"
