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 you 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.

2 files changed, 178 insertions, 71 deletions

diff --git a/sys/netgraph/netgraph.h b/sys/netgraph/netgraph.h
index d649c6c..dc008f4 100644
--- a/sys/netgraph/netgraph.h
+++ b/sys/netgraph/netgraph.h
@@ -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
diff --git a/sys/netgraph/ng_base.c b/sys/netgraph/ng_base.c
index 59fcd42..6a9b08f 100644
--- a/sys/netgraph/ng_base.c
+++ b/sys/netgraph/ng_base.c
@@ -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, node_p node, const char *name,
 		    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);
@@ -661,12 +662,7 @@ ng_make_node_common(struct ng_type *type, node_p *nodepp)
 	/* 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;
@@ -678,6 +674,9 @@ ng_make_node_common(struct ng_type *type, node_p *nodepp)
 			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();
@@ -794,10 +793,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();
 
@@ -813,9 +816,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);
@@ -837,8 +841,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++) {
@@ -854,20 +859,26 @@ ng_name_node(node_p node, const char *name)
 		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();
+
+	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);
+		}
 
-	/* copy it */
+	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();
 
@@ -902,8 +913,8 @@ ng_name2noderef(node_p here, const char *name)
 		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) &&
@@ -949,6 +960,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
@@ -2574,28 +2647,55 @@ ng_generic_msg(node_p here, item_p item, hook_p lasthook)
 		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;
@@ -2603,24 +2703,21 @@ ng_generic_msg(node_p here, item_p item, hook_p lasthook)
 		}
 		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++;
 			}
 		}
@@ -3027,6 +3124,17 @@ ng_mod_event(module_t mod, int event, void *data)
 	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)
@@ -3036,9 +3144,9 @@ vnet_netgraph_uninit(const void *unused __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;
@@ -3047,7 +3155,7 @@ vnet_netgraph_uninit(const void *unused __unused)
 			if (node != NULL)
 				break;
 		}
-		NAMEHASH_RUNLOCK();
+		IDHASH_RUNLOCK();
 
 		/* Attempt to kill it only if it is a regular node */
 		if (node != NULL) {
@@ -3065,6 +3173,9 @@ vnet_netgraph_uninit(const void *unused __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);