Author: glebius
Date: Sat Apr 14 10:13:36 2012
New Revision: 234277
URL: http://svn.freebsd.org/changeset/base/234277
Log:
Merge 231831:
Refactor the name hash and the ID hash, that are used to address nodes:
- Make hash sizes growable, to satisfy users running large mpd
installations, having thousands of nodes.
- NG_NAMEHASH() proved to give a very bad distribution in real life
name sets, while generic hash32_str(name, HASHINIT) proved to give
an even one, so use the latter for name hash.
- Do not store unnamed nodes in slot 0 of name hash, no reason for that.
- Use the ID hash in cases when we need to run through all nodes: the
NGM_LISTNODES command and in the vnet_netgraph_uninit().
- Implement NGM_LISTNODES and NGM_LISTNAMES as separate code, the former
iterates through the ID hash, and the latter through the name hash.
- Keep count of all nodes and of named nodes, so that we don't need
to count nodes in NGM_LISTNODES and NGM_LISTNAMES. The counters are
also used to estimate whether we need to grow hashes.
- Close a race between two threads running ng_name_node() assigning same
name to different nodes.
Modified:
stable/9/sys/netgraph/netgraph.h
stable/9/sys/netgraph/ng_base.c
Directory Properties:
stable/9/sys/ (props changed)
Modified: stable/9/sys/netgraph/netgraph.h
==============================================================================
--- stable/9/sys/netgraph/netgraph.h Sat Apr 14 10:08:07 2012
(r234276)
+++ stable/9/sys/netgraph/netgraph.h Sat Apr 14 10:13:36 2012
(r234277)
@@ -365,7 +365,7 @@ struct ng_node {
void *nd_private; /* node type dependant node ID */
ng_ID_t nd_ID; /* Unique per node */
LIST_HEAD(hooks, ng_hook) nd_hooks; /* linked list of node hooks */
- LIST_ENTRY(ng_node) nd_nodes; /* linked list of all nodes */
+ LIST_ENTRY(ng_node) nd_nodes; /* name hash collision list */
LIST_ENTRY(ng_node) nd_idnodes; /* ID hash collision list */
struct ng_queue nd_input_queue; /* input queue for locking */
int nd_refs; /* # of references to this node */
@@ -1202,10 +1202,6 @@ typedef void *meta_p;
#define NGI_GET_META(i,m)
#define ng_copy_meta(meta) NULL
-/* Hash related definitions */
-#define NG_ID_HASH_SIZE 128 /* most systems wont need even this many */
-#define NG_NAME_HASH_SIZE 128 /* most systems wont need even this many
*/
-
/*
* Mark the current thread when called from the outbound path of the
* network stack, in order to enforce queuing on ng nodes calling into
Modified: stable/9/sys/netgraph/ng_base.c
==============================================================================
--- stable/9/sys/netgraph/ng_base.c Sat Apr 14 10:08:07 2012
(r234276)
+++ stable/9/sys/netgraph/ng_base.c Sat Apr 14 10:13:36 2012
(r234277)
@@ -45,6 +45,7 @@
#include <sys/param.h>
#include <sys/systm.h>
#include <sys/ctype.h>
+#include <sys/hash.h>
#include <sys/kdb.h>
#include <sys/kernel.h>
#include <sys/kthread.h>
@@ -170,10 +171,20 @@ static struct rwlock ng_typelist_lock;
#define TYPELIST_WLOCK() rw_wlock(&ng_typelist_lock)
#define TYPELIST_WUNLOCK() rw_wunlock(&ng_typelist_lock)
-/* Hash related definitions */
-/* XXX Don't need to initialise them because it's a LIST */
-static VNET_DEFINE(LIST_HEAD(, ng_node), ng_ID_hash[NG_ID_HASH_SIZE]);
-#define V_ng_ID_hash VNET(ng_ID_hash)
+/* Hash related definitions. */
+LIST_HEAD(nodehash, ng_node);
+static VNET_DEFINE(struct nodehash *, ng_ID_hash);
+static VNET_DEFINE(u_long, ng_ID_hmask);
+static VNET_DEFINE(u_long, ng_nodes);
+static VNET_DEFINE(struct nodehash *, ng_name_hash);
+static VNET_DEFINE(u_long, ng_name_hmask);
+static VNET_DEFINE(u_long, ng_named_nodes);
+#define V_ng_ID_hash VNET(ng_ID_hash)
+#define V_ng_ID_hmask VNET(ng_ID_hmask)
+#define V_ng_nodes VNET(ng_nodes)
+#define V_ng_name_hash VNET(ng_name_hash)
+#define V_ng_name_hmask VNET(ng_name_hmask)
+#define V_ng_named_nodes VNET(ng_named_nodes)
static struct rwlock ng_idhash_lock;
#define IDHASH_RLOCK() rw_rlock(&ng_idhash_lock)
@@ -182,7 +193,7 @@ static struct rwlock ng_idhash_lock;
#define IDHASH_WUNLOCK() rw_wunlock(&ng_idhash_lock)
/* Method to find a node.. used twice so do it here */
-#define NG_IDHASH_FN(ID) ((ID) % (NG_ID_HASH_SIZE))
+#define NG_IDHASH_FN(ID) ((ID) % (V_ng_ID_hmask + 1))
#define NG_IDHASH_FIND(ID, node) \
do { \
rw_assert(&ng_idhash_lock, RA_LOCKED); \
@@ -195,18 +206,6 @@ static struct rwlock ng_idhash_lock;
} \
} while (0)
-static VNET_DEFINE(LIST_HEAD(, ng_node), ng_name_hash[NG_NAME_HASH_SIZE]);
-#define V_ng_name_hash VNET(ng_name_hash)
-
-#define NG_NAMEHASH(NAME, HASH) \
- do { \
- u_char h = 0; \
- const u_char *c; \
- for (c = (const u_char*)(NAME); *c; c++)\
- h += *c; \
- (HASH) = h % (NG_NAME_HASH_SIZE); \
- } while (0)
-
static struct rwlock ng_namehash_lock;
#define NAMEHASH_RLOCK() rw_rlock(&ng_namehash_lock)
#define NAMEHASH_RUNLOCK() rw_runlock(&ng_namehash_lock)
@@ -227,8 +226,10 @@ static int ng_con_nodes(item_p item, nod
node_p node2, const char *name2);
static int ng_con_part2(node_p node, item_p item, hook_p hook);
static int ng_con_part3(node_p node, item_p item, hook_p hook);
-static int ng_mkpeer(node_p node, const char *name,
- const char *name2, char *type);
+static int ng_mkpeer(node_p node, const char *name, const char *name2,
+ char *type);
+static void ng_name_rehash(void);
+static void ng_ID_rehash(void);
/* Imported, these used to be externally visible, some may go back. */
void ng_destroy_hook(hook_p hook);
@@ -658,12 +659,7 @@ ng_make_node_common(struct ng_type *type
/* Initialize hook list for new node */
LIST_INIT(&node->nd_hooks);
- /* Link us into the name hash. */
- NAMEHASH_WLOCK();
- LIST_INSERT_HEAD(&V_ng_name_hash[0], node, nd_nodes);
- NAMEHASH_WUNLOCK();
-
- /* get an ID and put us in the hash chain */
+ /* Get an ID and put us in the hash chain. */
IDHASH_WLOCK();
for (;;) { /* wrap protection, even if silly */
node_p node2 = NULL;
@@ -675,6 +671,9 @@ ng_make_node_common(struct ng_type *type
break;
}
}
+ V_ng_nodes++;
+ if (V_ng_nodes * 2 > V_ng_ID_hmask)
+ ng_ID_rehash();
LIST_INSERT_HEAD(&V_ng_ID_hash[NG_IDHASH_FN(node->nd_ID)], node,
nd_idnodes);
IDHASH_WUNLOCK();
@@ -791,10 +790,14 @@ ng_unref_node(node_p node)
node->nd_type->refs--; /* XXX maybe should get types lock? */
NAMEHASH_WLOCK();
- LIST_REMOVE(node, nd_nodes);
+ if (NG_NODE_HAS_NAME(node)) {
+ V_ng_named_nodes--;
+ LIST_REMOVE(node, nd_nodes);
+ }
NAMEHASH_WUNLOCK();
IDHASH_WLOCK();
+ V_ng_nodes--;
LIST_REMOVE(node, nd_idnodes);
IDHASH_WUNLOCK();
@@ -810,9 +813,10 @@ static node_p
ng_ID2noderef(ng_ID_t ID)
{
node_p node;
+
IDHASH_RLOCK();
NG_IDHASH_FIND(ID, node);
- if(node)
+ if (node)
NG_NODE_REF(node);
IDHASH_RUNLOCK();
return(node);
@@ -834,8 +838,9 @@ ng_node2ID(node_p node)
int
ng_name_node(node_p node, const char *name)
{
- int i, hash;
+ uint32_t hash;
node_p node2;
+ int i;
/* Check the name is valid */
for (i = 0; i < NG_NODESIZ; i++) {
@@ -851,20 +856,26 @@ ng_name_node(node_p node, const char *na
return (EINVAL);
}
- /* Check the name isn't already being used */
- if ((node2 = ng_name2noderef(node, name)) != NULL) {
- NG_NODE_UNREF(node2);
- TRAP_ERROR();
- return (EADDRINUSE);
- }
+ NAMEHASH_WLOCK();
+ if (V_ng_named_nodes * 2 > V_ng_name_hmask)
+ ng_name_rehash();
- /* copy it */
- strlcpy(NG_NODE_NAME(node), name, NG_NODESIZ);
+ hash = hash32_str(name, HASHINIT) & V_ng_name_hmask;
+ /* Check the name isn't already being used. */
+ LIST_FOREACH(node2, &V_ng_name_hash[hash], nd_nodes)
+ if (NG_NODE_IS_VALID(node2) &&
+ (strcmp(NG_NODE_NAME(node2), name) == 0)) {
+ NAMEHASH_WUNLOCK();
+ return (EADDRINUSE);
+ }
+ if (NG_NODE_HAS_NAME(node))
+ LIST_REMOVE(node, nd_nodes);
+ else
+ V_ng_named_nodes++;
+ /* Copy it. */
+ strlcpy(NG_NODE_NAME(node), name, NG_NODESIZ);
/* Update name hash. */
- NG_NAMEHASH(name, hash);
- NAMEHASH_WLOCK();
- LIST_REMOVE(node, nd_nodes);
LIST_INSERT_HEAD(&V_ng_name_hash[hash], node, nd_nodes);
NAMEHASH_WUNLOCK();
@@ -899,8 +910,8 @@ ng_name2noderef(node_p here, const char
return (ng_ID2noderef(temp));
}
- /* Find node by name */
- NG_NAMEHASH(name, hash);
+ /* Find node by name. */
+ hash = hash32_str(name, HASHINIT) & V_ng_name_hmask;
NAMEHASH_RLOCK();
LIST_FOREACH(node, &V_ng_name_hash[hash], nd_nodes)
if (NG_NODE_IS_VALID(node) &&
@@ -946,6 +957,68 @@ ng_unname(node_p node)
{
}
+/*
+ * Allocate a bigger name hash.
+ */
+static void
+ng_name_rehash()
+{
+ struct nodehash *new;
+ uint32_t hash;
+ u_long hmask;
+ node_p node, node2;
+ int i;
+
+ new = hashinit_flags((V_ng_name_hmask + 1) * 2, M_NETGRAPH_NODE, &hmask,
+ HASH_NOWAIT);
+ if (new == NULL)
+ return;
+
+ for (i = 0; i <= V_ng_name_hmask; i++)
+ LIST_FOREACH_SAFE(node, &V_ng_name_hash[i], nd_nodes, node2) {
+#ifdef INVARIANTS
+ LIST_REMOVE(node, nd_nodes);
+#endif
+ hash = hash32_str(NG_NODE_NAME(node), HASHINIT) & hmask;
+ LIST_INSERT_HEAD(&new[hash], node, nd_nodes);
+ }
+
+ hashdestroy(V_ng_name_hash, M_NETGRAPH_NODE, V_ng_name_hmask);
+ V_ng_name_hash = new;
+ V_ng_name_hmask = hmask;
+}
+
+/*
+ * Allocate a bigger ID hash.
+ */
+static void
+ng_ID_rehash()
+{
+ struct nodehash *new;
+ uint32_t hash;
+ u_long hmask;
+ node_p node, node2;
+ int i;
+
+ new = hashinit_flags((V_ng_ID_hmask + 1) * 2, M_NETGRAPH_NODE, &hmask,
+ HASH_NOWAIT);
+ if (new == NULL)
+ return;
+
+ for (i = 0; i <= V_ng_ID_hmask; i++)
+ LIST_FOREACH_SAFE(node, &V_ng_ID_hash[i], nd_idnodes, node2) {
+#ifdef INVARIANTS
+ LIST_REMOVE(node, nd_idnodes);
+#endif
+ hash = (node->nd_ID % (hmask + 1));
+ LIST_INSERT_HEAD(&new[hash], node, nd_idnodes);
+ }
+
+ hashdestroy(V_ng_ID_hash, M_NETGRAPH_NODE, V_ng_name_hmask);
+ V_ng_ID_hash = new;
+ V_ng_ID_hmask = hmask;
+}
+
/************************************************************************
Hook routines
Names are not optional. Hooks are always connected, except for a
@@ -2571,28 +2644,55 @@ ng_generic_msg(node_p here, item_p item,
break;
}
- case NGM_LISTNAMES:
case NGM_LISTNODES:
{
- const int unnamed = (msg->header.cmd == NGM_LISTNODES);
struct namelist *nl;
node_p node;
- int num = 0, i;
+ int i;
- NAMEHASH_RLOCK();
- /* Count number of nodes */
- for (i = 0; i < NG_NAME_HASH_SIZE; i++) {
- LIST_FOREACH(node, &V_ng_name_hash[i], nd_nodes) {
- if (NG_NODE_IS_VALID(node) &&
- (unnamed || NG_NODE_HAS_NAME(node))) {
- num++;
- }
+ IDHASH_RLOCK();
+ /* Get response struct. */
+ NG_MKRESPONSE(resp, msg, sizeof(*nl) +
+ (V_ng_nodes * sizeof(struct nodeinfo)), M_NOWAIT | M_ZERO);
+ if (resp == NULL) {
+ IDHASH_RUNLOCK();
+ error = ENOMEM;
+ break;
+ }
+ nl = (struct namelist *) resp->data;
+
+ /* Cycle through the lists of nodes. */
+ nl->numnames = 0;
+ for (i = 0; i <= V_ng_ID_hmask; i++) {
+ LIST_FOREACH(node, &V_ng_ID_hash[i], nd_idnodes) {
+ struct nodeinfo *const np =
+ &nl->nodeinfo[nl->numnames];
+
+ if (NG_NODE_NOT_VALID(node))
+ continue;
+ if (NG_NODE_HAS_NAME(node))
+ strcpy(np->name, NG_NODE_NAME(node));
+ strcpy(np->type, node->nd_type->name);
+ np->id = ng_node2ID(node);
+ np->hooks = node->nd_numhooks;
+ KASSERT(nl->numnames < V_ng_nodes,
+ ("%s: no space", __func__));
+ nl->numnames++;
}
}
+ IDHASH_RUNLOCK();
+ break;
+ }
+ case NGM_LISTNAMES:
+ {
+ struct namelist *nl;
+ node_p node;
+ int i;
- /* Get response struct */
+ NAMEHASH_RLOCK();
+ /* Get response struct. */
NG_MKRESPONSE(resp, msg, sizeof(*nl) +
- (num * sizeof(struct nodeinfo)), M_NOWAIT);
+ (V_ng_named_nodes * sizeof(struct nodeinfo)), M_NOWAIT);
if (resp == NULL) {
NAMEHASH_RUNLOCK();
error = ENOMEM;
@@ -2600,24 +2700,21 @@ ng_generic_msg(node_p here, item_p item,
}
nl = (struct namelist *) resp->data;
- /* Cycle through the linked list of nodes */
+ /* Cycle through the lists of nodes. */
nl->numnames = 0;
- for (i = 0; i < NG_NAME_HASH_SIZE; i++) {
+ for (i = 0; i <= V_ng_name_hmask; i++) {
LIST_FOREACH(node, &V_ng_name_hash[i], nd_nodes) {
struct nodeinfo *const np =
&nl->nodeinfo[nl->numnames];
if (NG_NODE_NOT_VALID(node))
continue;
- if (!unnamed && (! NG_NODE_HAS_NAME(node)))
- continue;
- if (NG_NODE_HAS_NAME(node))
- strcpy(np->name, NG_NODE_NAME(node));
+ strcpy(np->name, NG_NODE_NAME(node));
strcpy(np->type, node->nd_type->name);
np->id = ng_node2ID(node);
np->hooks = node->nd_numhooks;
- KASSERT(nl->numnames < num, ("%s: no space",
- __func__));
+ KASSERT(nl->numnames < V_ng_named_nodes,
+ ("%s: no space", __func__));
nl->numnames++;
}
}
@@ -3024,6 +3121,17 @@ ng_mod_event(module_t mod, int event, vo
return (error);
}
+static void
+vnet_netgraph_init(const void *unused __unused)
+{
+
+ /* We start with small hashes, but they can grow. */
+ V_ng_ID_hash = hashinit(16, M_NETGRAPH_NODE, &V_ng_ID_hmask);
+ V_ng_name_hash = hashinit(16, M_NETGRAPH_NODE, &V_ng_name_hmask);
+}
+VNET_SYSINIT(vnet_netgraph_init, SI_SUB_NETGRAPH, SI_ORDER_FIRST,
+ vnet_netgraph_init, NULL);
+
#ifdef VIMAGE
static void
vnet_netgraph_uninit(const void *unused __unused)
@@ -3033,9 +3141,9 @@ vnet_netgraph_uninit(const void *unused
do {
/* Find a node to kill */
- NAMEHASH_RLOCK();
- for (i = 0; i < NG_NAME_HASH_SIZE; i++) {
- LIST_FOREACH(node, &V_ng_name_hash[i], nd_nodes) {
+ IDHASH_RLOCK();
+ for (i = 0; i <= V_ng_ID_hmask; i++) {
+ LIST_FOREACH(node, &V_ng_ID_hash[i], nd_idnodes) {
if (node != &ng_deadnode) {
NG_NODE_REF(node);
break;
@@ -3044,7 +3152,7 @@ vnet_netgraph_uninit(const void *unused
if (node != NULL)
break;
}
- NAMEHASH_RUNLOCK();
+ IDHASH_RUNLOCK();
/* Attempt to kill it only if it is a regular node */
if (node != NULL) {
@@ -3062,6 +3170,9 @@ vnet_netgraph_uninit(const void *unused
last_killed = node;
}
} while (node != NULL);
+
+ hashdestroy(V_ng_name_hash, M_NETGRAPH_NODE, V_ng_name_hmask);
+ hashdestroy(V_ng_ID_hash, M_NETGRAPH_NODE, V_ng_ID_hmask);
}
VNET_SYSUNINIT(vnet_netgraph_uninit, SI_SUB_NETGRAPH, SI_ORDER_FIRST,
vnet_netgraph_uninit, NULL);
_______________________________________________
svn-src-stable-9@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/svn-src-stable-9
To unsubscribe, send any mail to "svn-src-stable-9-unsubscr...@freebsd.org"
