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.

1 files changed, 1 insertions, 5 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