Rewrite of netgraph to start getting ready for SMP.

This version is functional and is aproaching solid..
notice I said APROACHING. There are many node types I cannot test
I have tested: echo hole ppp socket vjc iface tee bpf async tty
The rest compile and "Look" right.  More changes to follow.
DEBUGGING is enabled in this code to help if people have problems.

1 files changed, 1580 insertions, 604 deletions

diff --git a/sys/netgraph/ng_base.c b/sys/netgraph/ng_base.c
index d9b26f4..0cbd63d 100644
--- a/sys/netgraph/ng_base.c
+++ b/sys/netgraph/ng_base.c
@@ -1,10 +1,9 @@
-
 /*
  * ng_base.c
  *
  * Copyright (c) 1996-1999 Whistle Communications, Inc.
  * All rights reserved.
- * 
+ *
  * Subject to the following obligations and disclaimer of warranty, use and
  * redistribution of this software, in source or object code forms, with or
  * without modifications are expressly permitted by Whistle Communications;
@@ -15,7 +14,7 @@
  *    Communications, Inc. trademarks, including the mark "WHISTLE
  *    COMMUNICATIONS" on advertising, endorsements, or otherwise except as
  *    such appears in the above copyright notice or in the software.
- * 
+ *
  * THIS SOFTWARE IS BEING PROVIDED BY WHISTLE COMMUNICATIONS "AS IS", AND
  * TO THE MAXIMUM EXTENT PERMITTED BY LAW, WHISTLE COMMUNICATIONS MAKES NO
  * REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED, REGARDING THIS SOFTWARE,
@@ -51,6 +50,7 @@
 #include <sys/kernel.h>
 #include <sys/malloc.h>
 #include <sys/syslog.h>
+#include <sys/sysctl.h>
 #include <sys/linker.h>
 #include <sys/queue.h>
 #include <sys/mbuf.h>
@@ -66,32 +66,73 @@
 MODULE_VERSION(netgraph, 1);
 
 /* List of all nodes */
-static LIST_HEAD(, ng_node) nodelist;
+static LIST_HEAD(, ng_node) ng_nodelist;
+static struct mtx	ng_nodelist_mtx;
+
+/* NETISR queue */
+/* List nodes with unallocated work */
+static TAILQ_HEAD(, ng_node) ng_worklist = TAILQ_HEAD_INITIALIZER(ng_worklist);
+static struct mtx	ng_worklist_mtx;
 
 /* List of installed types */
-static LIST_HEAD(, ng_type) typelist;
+static LIST_HEAD(, ng_type) ng_typelist;
+static struct mtx	ng_typelist_mtx;
 
-/* Hash releted definitions */
-#define ID_HASH_SIZE 32 /* most systems wont need even this many */
-static LIST_HEAD(, ng_node) ID_hash[ID_HASH_SIZE];
+/* Hash related definitions */
 /* Don't nead to initialise them because it's a LIST */
+#define ID_HASH_SIZE 32 /* most systems wont need even this many */
+static LIST_HEAD(, ng_node) ng_ID_hash[ID_HASH_SIZE];
+static struct mtx	ng_idhash_mtx;
+
+/* Mutex that protects the free queue item list */
+static volatile item_p		ngqfree;	/* free ones */
+static struct mtx	ngq_mtx;
 
 /* Internal functions */
 static int	ng_add_hook(node_p node, const char *name, hook_p * hookp);
 static int	ng_connect(hook_p hook1, hook_p hook2);
 static void	ng_disconnect_hook(hook_p hook);
-static int	ng_generic_msg(node_p here, struct ng_mesg *msg,
-			const char *retaddr, struct ng_mesg ** resp,
-			hook_p hook);
+static int	ng_generic_msg(node_p here, item_p item, hook_p lasthook);
 static ng_ID_t	ng_decodeidname(const char *name);
 static int	ngb_mod_event(module_t mod, int event, void *data);
-static int	ng_send_data_dont_queue(hook_p hook, struct mbuf *m,
-		meta_p meta, struct mbuf **ret_m, meta_p *ret_meta,
-		struct ng_mesg **resp);
+static void	ng_worklist_remove(node_p node);
 static void	ngintr(void);
+static int	ng_apply_item(node_p node, item_p item);
+static void	ng_flush_input_queue(struct ng_queue * ngq);
+static void	ng_setisr(node_p node);
+static node_p	ng_ID2noderef(ng_ID_t ID);
+
+/* imported */
+int	ng_bypass(hook_p hook1, hook_p hook2);
+void	ng_cutlinks(node_p node);
+int	ng_con_nodes(node_p node, const char *name, node_p node2,
+	const char *name2);
+void	ng_destroy_hook(hook_p hook);
+node_p	ng_name2noderef(node_p node, const char *name);
+int	ng_path2noderef(node_p here, const char *path,
+	node_p *dest, hook_p *lasthook);
+struct	ng_type *ng_findtype(const char *type);
+int	ng_make_node(const char *type, node_p *nodepp);
+int	ng_mkpeer(node_p node, const char *name, const char *name2, char *type);
+int	ng_path_parse(char *addr, char **node, char **path, char **hook);
+void	ng_rmnode(node_p node);
+
 
 /* Our own netgraph malloc type */
 MALLOC_DEFINE(M_NETGRAPH, "netgraph", "netgraph structures and ctrl messages");
+MALLOC_DEFINE(M_NETGRAPH_HOOK, "netgraph_hook", "netgraph hook structures");
+MALLOC_DEFINE(M_NETGRAPH_NODE, "netgraph_node", "netgraph node structures");
+MALLOC_DEFINE(M_NETGRAPH_ITEM, "netgraph_item", "netgraph item structures");
+MALLOC_DEFINE(M_NETGRAPH_META, "netgraph_meta", "netgraph name storage");
+MALLOC_DEFINE(M_NETGRAPH_MSG, "netgraph_msg", "netgraph name storage");
+
+/* Should not be visible outside this file */
+#define NG_FREE_HOOK(hook) do { FREE((hook), M_NETGRAPH_HOOK); } while (0)
+#define NG_FREE_NODE(node) do { FREE((node), M_NETGRAPH_NODE); } while (0)
+#define NG_FREE_NAME(name) do { FREE((name), M_NETGRAPH_NAME); } while (0)
+/* Warning: Generally use NG_FREE_ITEM() instead */
+#define NG_FREE_ITEM_REAL(item) do { FREE((item), M_NETGRAPH_ITEM); } while (0)
+
 
 /* Set this to Debugger("X") to catch all errors as they occur */
 #ifndef TRAP_ERROR
@@ -310,6 +351,7 @@ int
 ng_make_node(const char *typename, node_p *nodepp)
 {
 	struct ng_type *type;
+	int	error;
 
 	/* Check that the type makes sense */
 	if (typename == NULL) {
@@ -335,15 +377,32 @@ ng_make_node(const char *typename, node_p *nodepp)
 			return (ENXIO);
 	}
 
-	/* Call the constructor */
-	if (type->constructor != NULL)
-		return ((*type->constructor)(nodepp));
-	else
-		return (ng_make_node_common(type, nodepp));
+	/*
+	 * If we have a constructor, then make the node and
+	 * call the constructor to do type specific initialisation.
+	 */
+	if (type->constructor != NULL) {
+		if ((error = ng_make_node_common(type, nodepp)) == 0) {
+			if ((error = ((*type->constructor)(*nodepp)) != 0)) {
+				ng_unref(*nodepp);
+			}
+		}
+	} else {
+		/*
+		 * Node has no constructor. We cannot ask for one
+		 * to be made. It must be brought into existance by
+		 * some external agency. The external acency should
+		 * call ng_make_node_common() directly to get the
+		 * netgraph part initialised.
+		 */
+		error = EINVAL;
+	}
+	return (error);
 }
 
 /*
- * Generic node creation. Called by node constructors.
+ * Generic node creation. Called by node initialisation for externally
+ * instantiated nodes (e.g. hardware, sockets, etc ).
  * The returned node has a reference count of 1.
  */
 int
@@ -358,7 +417,7 @@ ng_make_node_common(struct ng_type *type, node_p *nodepp)
 	}
 
 	/* Make a node and try attach it to the type */
-	MALLOC(node, node_p, sizeof(*node), M_NETGRAPH, M_NOWAIT | M_ZERO);
+	MALLOC(node, node_p, sizeof(*node), M_NETGRAPH_NODE, M_NOWAIT | M_ZERO);
 	if (node == NULL) {
 		TRAP_ERROR;
 		return (ENOMEM);
@@ -367,15 +426,36 @@ ng_make_node_common(struct ng_type *type, node_p *nodepp)
 	node->refs++;				/* note reference */
 	type->refs++;
 
-	/* Link us into the node linked list */
-	LIST_INSERT_HEAD(&nodelist, node, nodes);
+	mtx_init(&node->input_queue.q_mtx, "netgraph node mutex", 0);
+	node->input_queue.queue = NULL;
+	node->input_queue.last = &node->input_queue.queue;
+	node->input_queue.q_flags = 0;
+	node->input_queue.q_node = node;
 
 	/* Initialize hook list for new node */
 	LIST_INIT(&node->hooks);
 
+	/* Link us into the node linked list */
+	mtx_enter(&ng_nodelist_mtx, MTX_DEF);
+	LIST_INSERT_HEAD(&ng_nodelist, node, nodes);
+	mtx_exit(&ng_nodelist_mtx, MTX_DEF);
+
+
 	/* get an ID and put us in the hash chain */
-	node->ID = nextID++; /* 137 per second for 1 year before wrap */
-	LIST_INSERT_HEAD(&ID_hash[node->ID % ID_HASH_SIZE], node, idnodes);
+	mtx_enter(&ng_idhash_mtx, MTX_DEF);
+	do { /* wrap protection, even if silly */
+		node_p node2 = NULL;
+		node->ID = nextID++; /* 137 per second for 1 year before wrap */
+		if ((node->ID == 0) || (node2 = ng_ID2noderef(node->ID))) {
+			if (node2) {
+				ng_unref(node2);
+				node2 = NULL;
+			}
+			continue;	/* try again */
+		}
+	} while (0);
+	LIST_INSERT_HEAD(&ng_ID_hash[node->ID % ID_HASH_SIZE], node, idnodes);
+	mtx_exit(&ng_idhash_mtx, MTX_DEF);
 
 	/* Done */
 	*nodepp = node;
@@ -387,29 +467,43 @@ ng_make_node_common(struct ng_type *type, node_p *nodepp)
  * it's shutdown method, or do the default shutdown if there is
  * no type-specific method.
  *
- * Persistent nodes must have a type-specific method which
- * resets the NG_INVALID flag.
+ * We can only be called form a shutdown message, so we know we have
+ * a writer lock, and therefore exclusive access.
+ *
+ * Persistent node types must have a type-specific method which
+ * Allocates a new node. This one is irretrievably going away.
  */
 void
 ng_rmnode(node_p node)
 {
 	/* Check if it's already shutting down */
-	if ((node->flags & NG_INVALID) != 0)
+	if ((node->flags & NG_CLOSING) != 0)
 		return;
 
 	/* Add an extra reference so it doesn't go away during this */
 	node->refs++;
 
 	/* Mark it invalid so any newcomers know not to try use it */
-	node->flags |= NG_INVALID;
+	node->flags |= NG_INVALID|NG_CLOSING;
+
+	ng_unname(node);
+	ng_cutlinks(node);
+	/*
+	 * Drain the input queue forceably.
+	 */
+	ng_flush_input_queue(&node->input_queue);
+
+	/*
+	 * Take us off the work queue if we are there.
+	 */
+	ng_worklist_remove(node);
+
 
 	/* Ask the type if it has anything to do in this case */
-	if (node->type && node->type->shutdown)
+	if (node->type && node->type->shutdown) {
 		(*node->type->shutdown)(node);
-	else {				/* do the default thing */
-		ng_unname(node);
-		ng_cutlinks(node);
-		ng_unref(node);
+	} else {				/* do the default thing */
+		ng_unref(node); /* XXX hmmmmm check this */
 	}
 
 	/* Remove extra reference, possibly the last */
@@ -427,9 +521,12 @@ ng_cutlinks(node_p node)
 	/* Make sure that this is set to stop infinite loops */
 	node->flags |= NG_INVALID;
 
-	/* If we have sleepers, wake them up; they'll see NG_INVALID */
-	if (node->sleepers)
-		wakeup(node);
+	/*
+	 * Drain the input queue forceably.
+	 * We also do this in ng_rmnode
+	 * to make sure we get all code paths.
+	 */
+	ng_flush_input_queue(&node->input_queue);
 
 	/* Notify all remaining connected nodes to disconnect */
 	while ((hook = LIST_FIRST(&node->hooks)) != NULL)
@@ -445,83 +542,45 @@ ng_unref(node_p node)
 	int	s;
 
 	s = splhigh();
+/* XXX not atomic.. fix */
 	if (--node->refs <= 0) {
-		node->type->refs--;
+
+		mtx_enter(&ng_nodelist_mtx, MTX_DEF);
+		node->type->refs--; /* XXX maybe should get types lock? */
 		LIST_REMOVE(node, nodes);
-		LIST_REMOVE(node, idnodes);
-		FREE(node, M_NETGRAPH);
-	}
-	splx(s);
-}
+		mtx_exit(&ng_nodelist_mtx, MTX_DEF);
 
-/*
- * Wait for a node to come ready. Returns a node with a reference count;
- * don't forget to drop it when we are done with it using ng_release_node().
- */
-int
-ng_wait_node(node_p node, char *msg)
-{
-	int s, error = 0;
+		mtx_enter(&ng_idhash_mtx, MTX_DEF);
+		LIST_REMOVE(node, idnodes);
+		mtx_exit(&ng_idhash_mtx, MTX_DEF);
 
-	if (msg == NULL)
-		msg = "netgraph";
-	s = splnet();
-	node->sleepers++;
-	node->refs++;		/* the sleeping process counts as a reference */
-	while ((node->flags & (NG_BUSY | NG_INVALID)) == NG_BUSY)
-		error = tsleep(node, (PZERO + 1) | PCATCH, msg, 0);
-	node->sleepers--;
-	if (node->flags & NG_INVALID) {
-		TRAP_ERROR;
-		error = ENXIO;
-	} else {
-		KASSERT(node->refs > 1,
-		    ("%s: refs=%d", __FUNCTION__, node->refs));
-		node->flags |= NG_BUSY;
+		NG_FREE_NODE(node);
 	}
 	splx(s);
-
-	/* Release the reference we had on it */
-	if (error != 0)
-		ng_unref(node);
-	return error;
-}
-
-/*
- * Release a node acquired via ng_wait_node()
- */
-void
-ng_release_node(node_p node)
-{
-	/* Declare that we don't want it */
-	node->flags &= ~NG_BUSY;
-
-	/* If we have sleepers, then wake them up */
-	if (node->sleepers)
-		wakeup(node);
-
-	/* We also have a reference.. drop it too */
-	ng_unref(node);
 }
 
 /************************************************************************
 			Node ID handling
 ************************************************************************/
 static node_p
-ng_ID2node(ng_ID_t ID)
+ng_ID2noderef(ng_ID_t ID)
 {
 	node_p np;
-	LIST_FOREACH(np, &ID_hash[ID % ID_HASH_SIZE], idnodes) {
+	mtx_enter(&ng_idhash_mtx, MTX_DEF);
+	LIST_FOREACH(np, &ng_ID_hash[ID % ID_HASH_SIZE], idnodes) {
 		if (np->ID == ID)
 			break;
 	}
+	if(np)
+		np->refs++;
+	mtx_exit(&ng_idhash_mtx, MTX_DEF);
 	return(np);
 }
 
 ng_ID_t
 ng_node2ID(node_p node)
 {
-	return (node->ID);
+	return (node?node->ID:0);
 }
 
 /************************************************************************
@@ -535,6 +594,7 @@ int
 ng_name_node(node_p node, const char *name)
 {
 	int i;
+	node_p node2;
 
 	/* Check the name is valid */
 	for (i = 0; i < NG_NODELEN + 1; i++) {
@@ -550,28 +610,16 @@ ng_name_node(node_p node, const char *name)
 		return (EINVAL);
 	}
 
-	/* Check the node isn't already named */
-	if (node->name != NULL) {
-		TRAP_ERROR;
-		return (EISCONN);
-	}
-
 	/* Check the name isn't already being used */
-	if (ng_findname(node, name) != NULL) {
+	if ((node2 = ng_name2noderef(node, name)) != NULL) {
+		ng_unref(node2);
 		TRAP_ERROR;
 		return (EADDRINUSE);
 	}
 
-	/* Allocate space and copy it */
-	MALLOC(node->name, char *, strlen(name) + 1, M_NETGRAPH, M_NOWAIT);
-	if (node->name == NULL) {
-		TRAP_ERROR;
-		return (ENOMEM);
-	}
+	/* copy it */
 	strcpy(node->name, name);
 
-	/* The name counts as a reference */
-	node->refs++;
 	return (0);
 }
 
@@ -581,27 +629,35 @@ ng_name_node(node_p node, const char *name)
  * with ID (ie, at address) xxx".
  *
  * Returns the node if found, else NULL.
+ * Eventually should add something faster than a sequential search.
+ * Note it holds a reference on the node so you an be sure it's still there.
  */
 node_p
-ng_findname(node_p this, const char *name)
+ng_name2noderef(node_p here, const char *name)
 {
 	node_p node;
 	ng_ID_t temp;
 
 	/* "." means "this node" */
-	if (strcmp(name, ".") == 0)
-		return(this);
+	if (strcmp(name, ".") == 0) {
+		here->refs++;
+		return(here);
+	}
 
 	/* Check for name-by-ID */
 	if ((temp = ng_decodeidname(name)) != 0) {
-		return (ng_ID2node(temp));
+		return (ng_ID2noderef(temp));
 	}
 
 	/* Find node by name */
-	LIST_FOREACH(node, &nodelist, nodes) {
-		if (node->name != NULL && strcmp(node->name, name) == 0)
+	mtx_enter(&ng_nodelist_mtx, MTX_DEF);
+	LIST_FOREACH(node, &ng_nodelist, nodes) {
+		if (node->name[0] != '\0' && strcmp(node->name, name) == 0)
 			break;
 	}
+	if (node)
+		node->refs++;
+	mtx_exit(&ng_nodelist_mtx, MTX_DEF);
 	return (node);
 }
 
@@ -635,19 +691,13 @@ ng_decodeidname(const char *name)
 void
 ng_unname(node_p node)
 {
-	if (node->name) {
-		FREE(node->name, M_NETGRAPH);
-		node->name = NULL;
-		ng_unref(node);
-	}
+	bzero(node->name, NG_NODELEN);
 }
 
 /************************************************************************
 			Hook routines
-
  Names are not optional. Hooks are always connected, except for a
  brief moment within these routines.
-
 ************************************************************************/
 
 /*
@@ -659,8 +709,14 @@ ng_unref_hook(hook_p hook)
 	int	s;
 
 	s = splhigh();
-	if (--hook->refs == 0)
-		FREE(hook, M_NETGRAPH);
+/* XXX not atomic.. fix */
+	if (--hook->refs == 0) {
+		if (hook->node) {
+			ng_unref(hook->node);
+			hook->node = NULL;
+		}
+		NG_FREE_HOOK(hook);
+	}
 	splx(s);
 }
 
@@ -684,7 +740,7 @@ ng_add_hook(node_p node, const char *name, hook_p *hookp)
 	}
 
 	/* Allocate the hook and link it up */
-	MALLOC(hook, hook_p, sizeof(*hook), M_NETGRAPH, M_NOWAIT | M_ZERO);
+	MALLOC(hook, hook_p, sizeof(*hook), M_NETGRAPH_HOOK, M_NOWAIT | M_ZERO);
 	if (hook == NULL) {
 		TRAP_ERROR;
 		return (ENOMEM);
@@ -696,28 +752,20 @@ ng_add_hook(node_p node, const char *name, hook_p *hookp)
 
 	/* Check if the node type code has something to say about it */
 	if (node->type->newhook != NULL)
-		if ((error = (*node->type->newhook)(node, hook, name)) != 0)
-			goto fail;
+		if ((error = (*node->type->newhook)(node, hook, name)) != 0) {
+			ng_unref_hook(hook);	/* this frees the hook */
+			return (error);
+		}
 
 	/*
 	 * The 'type' agrees so far, so go ahead and link it in.
 	 * We'll ask again later when we actually connect the hooks.
+	 * The reference we have is for this linkage.
 	 */
 	LIST_INSERT_HEAD(&node->hooks, hook, hooks);
 	node->numhooks++;
 
 	/* Set hook name */
-	MALLOC(hook->name, char *, strlen(name) + 1, M_NETGRAPH, M_NOWAIT);
-	if (hook->name == NULL) {
-		error = ENOMEM;
-		LIST_REMOVE(hook, hooks);
-		node->numhooks--;
-fail:
-		hook->node = NULL;
-		ng_unref(node);
-		ng_unref_hook(hook);	/* this frees the hook */
-		return (error);
-	}
 	strcpy(hook->name, name);
 	if (hookp)
 		*hookp = hook;
@@ -767,7 +815,7 @@ ng_findhook(node_p node, const char *name)
 	if (node->type->findhook != NULL)
 		return (*node->type->findhook)(node, name);
 	LIST_FOREACH(hook, &node->hooks, hooks) {
-		if (hook->name != NULL && strcmp(hook->name, name) == 0)
+		if (strcmp(hook->name, name) == 0)
 			return (hook);
 	}
 	return (NULL);
@@ -820,10 +868,6 @@ ng_disconnect_hook(hook_p hook)
 		 */
 		(*node->type->disconnect) (hook);
 	}
-	ng_unref(node);		/* might be the last reference */
-	if (hook->name)
-		FREE(hook->name, M_NETGRAPH);
-	hook->node = NULL;	/* may still be referenced elsewhere */
 	ng_unref_hook(hook);
 }
 
@@ -869,9 +913,12 @@ ng_newtype(struct ng_type *tp)
 		return (EEXIST);
 	}
 
-	/* Link in new type */
-	LIST_INSERT_HEAD(&typelist, tp, types);
 	tp->refs = 0;
+
+	/* Link in new type */
+	mtx_enter(&ng_typelist_mtx, MTX_DEF);
+	LIST_INSERT_HEAD(&ng_typelist, tp, types);
+	mtx_exit(&ng_typelist_mtx, MTX_DEF);
 	return (0);
 }
 
@@ -883,14 +930,15 @@ ng_findtype(const char *typename)
 {
 	struct ng_type *type;
 
-	LIST_FOREACH(type, &typelist, types) {
+	mtx_enter(&ng_typelist_mtx, MTX_DEF);
+	LIST_FOREACH(type, &ng_typelist, types) {
 		if (strcmp(type->name, typename) == 0)
 			break;
 	}
+	mtx_exit(&ng_typelist_mtx, MTX_DEF);
 	return (type);
 }
 
-
 /************************************************************************
 			Composite routines
 ************************************************************************/
@@ -946,8 +994,64 @@ ng_con_nodes(node_p node, const char *name, node_p node2, const char *name2)
 	}
 	return (ng_connect(hook, hook2));
 }
-
+/************************************************************************
+		Utility routines to send self messages
+************************************************************************/
 /*
+ * Static version of shutdown message. we don't want to need resources
+ * to shut down (we may be doing it to release resources because we ran out.
+ */
+static struct	ng_mesg  ng_msg_shutdown = {
+	{NG_VERSION,		/* u_char */
+	0,			/* u_char spare */
+	0,			/* u_int16_t arglen */
+	NGF_STATIC,		/* u_int32_t flags */
+	0,			/* u_int32_t token */
+	NGM_GENERIC_COOKIE,	/* u_int32_t */
+	NGM_SHUTDOWN,		/* u_int32_t */
+	"shutdown"}		/* u_char[16] */
+};
+	
+int
+ng_rmnode_self(node_p here)
+{
+	item_p	item;
+	struct	ng_mesg	*msg;
+
+	/*
+	 * Use the static version to avoid needing
+	 * memory allocation to succeed.
+	 * The message is never written to and always the same.
+	 */
+	msg = &ng_msg_shutdown;
+
+	/*
+	 * Try get a queue item to send it with.
+	 * Hopefully since it has a reserve, we can get one.
+	 * If we can't we are screwed anyhow.
+	 * Increase the chances by flushing our queue first.
+	 * We may free an item, (if we were the hog).
+	 * Work in progress is allowed to complete.
+	 * We also pretty much ensure that we come straight
+	 * back in to do the shutdown. It may be a good idea
+	 * to hold a reference actually to stop it from all
+	 * going up in smoke.
+	 */
+/*	ng_flush_input_queue(&here->input_queue); will mask problem  */
+	item = ng_package_msg_self(here, NULL, msg);
+	if (item == NULL) { /* it would have freed the msg except static */
+		/* try again after flushing our queue */
+		ng_flush_input_queue(&here->input_queue);
+		item = ng_package_msg_self(here, NULL, msg);
+		if (item == NULL) {
+			printf("failed to free node 0x%x\n", ng_node2ID(here));
+			return (ENOMEM);
+		}
+	}
+	return (ng_snd_item(item, 0));
+}
+
+/***********************************************************************
  * Parse and verify a string of the form:  <NODE:><PATH>
  *
  * Such a string can refer to a specific node or a specific hook
@@ -961,8 +1065,7 @@ ng_con_nodes(node_p node, const char *name, node_p node2, const char *name2)
  * the final hook component of <PATH>, if any, otherwise NULL.
  *
  * This returns -1 if the path is malformed. The char ** are optional.
- */
-
+ ***********************************************************************/
 int
 ng_path_parse(char *addr, char **nodep, char **pathp, char **hookp)
 {
@@ -1030,14 +1133,15 @@ ng_path_parse(char *addr, char **nodep, char **pathp, char **hookp)
 
 /*
  * Given a path, which may be absolute or relative, and a starting node,
- * return the destination node. Compute the "return address" if desired.
+ * return the destination node.
  */
 int
-ng_path2node(node_p here, const char *address, node_p *destp, hook_p *lasthook)
+ng_path2noderef(node_p here, const char *address,
+				node_p *destp, hook_p *lasthook)
 {
 	char    fullpath[NG_PATHLEN + 1];
 	char   *nodename, *path, pbuf[2];
-	node_p  node;
+	node_p  node, oldnode;
 	char   *cp;
 	hook_p hook = NULL;
 
@@ -1061,17 +1165,39 @@ ng_path2node(node_p here, const char *address, node_p *destp, hook_p *lasthook)
 		path = pbuf;
 	}
 
-	/* For an absolute address, jump to the starting node */
+	/*
+	 * For an absolute address, jump to the starting node.
+	 * Note that this holds a reference on the node for us.
+	 * Don't forget to drop the reference if we don't need it.
+	 */
 	if (nodename) {
-		node = ng_findname(here, nodename);
+		node = ng_name2noderef(here, nodename);
 		if (node == NULL) {
 			TRAP_ERROR;
 			return (ENOENT);
 		}
-	} else
+	} else {
+		if (here == NULL) {
+			TRAP_ERROR
+			return (EINVAL);
+		}
 		node = here;
+		node->refs++;
+	}
 
-	/* Now follow the sequence of hooks */
+	/*
+	 * Now follow the sequence of hooks 
+	 * XXX
+	 * We actually cannot guarantee that the sequence
+	 * is not being demolished as we crawl along it
+	 * without extra-ordinary locking etc.
+	 * So this is a bit dodgy to say the least.
+	 * We can probably hold up some things by holding
+	 * the nodelist mutex for the time of this
+	 * crawl if we wanted.. At least that way we wouldn't have to
+	 * worry about the nodes dissappearing, but the hooks would still
+	 * be a problem.
+	 */
 	for (cp = path; node != NULL && *cp != '\0'; ) {
 		char *segment;
 
@@ -1097,13 +1223,28 @@ ng_path2node(node_p here, const char *address, node_p *destp, hook_p *lasthook)
 		/* Can't get there from here... */
 		if (hook == NULL
 		    || hook->peer == NULL
-		    || (hook->flags & HK_INVALID) != 0) {
+		    || (hook->flags & HK_INVALID) != 0
+		    || (hook->peer->flags & HK_INVALID) != 0) {
 			TRAP_ERROR;
+			ng_unref(node);
 			return (ENOENT);
 		}
 
-		/* Hop on over to the next node */
-		node = hook->peer->node;
+		/*
+		 * Hop on over to the next node 
+		 * XXX
+		 * Big race conditions here as hooks and nodes go away 
+		 * *** Idea.. store an ng_ID_t in each hook and use that
+		 * instead of the direct hook in this crawl?
+		 */
+		oldnode = node;
+		if ((node = hook->peer->node))
+			node->refs++;	/* XXX RACE */
+		ng_unref(oldnode);	/* XXX another race */
+		if (node->flags & NG_INVALID) {
+			ng_unref(node);	/* XXX more races */
+			node = NULL;
+		}
 	}
 
 	/* If node somehow missing, fail here (probably this is not needed) */
@@ -1115,116 +1256,740 @@ ng_path2node(node_p here, const char *address, node_p *destp, hook_p *lasthook)
 	/* Done */
 	*destp = node;
 	if (lasthook != NULL)
-		*lasthook = hook ? hook->peer : NULL;
+		*lasthook = (hook ? hook->peer : NULL);
 	return (0);
 }
 
+/***************************************************************\
+* Input queue handling.
+* All activities are submitted to the node via the input queue
+* which implements a multiple-reader/single-writer gate.
+* Items which cannot be handled immeditly are queued.
+*
+* read-write queue locking inline functions			*
+\***************************************************************/
+
+static __inline item_p ng_dequeue(struct ng_queue * ngq);
+static __inline item_p ng_acquire_read(struct ng_queue * ngq,
+					item_p  item);
+static __inline item_p ng_acquire_write(struct ng_queue * ngq,
+					item_p  item);
+static __inline void	ng_leave_read(struct ng_queue * ngq);
+static __inline void	ng_leave_write(struct ng_queue * ngq);
+static __inline void	ng_queue_rw(struct ng_queue * ngq,
+					item_p  item, int rw);
+
 /*
- * Call the appropriate message handler for the object.
- * It is up to the message handler to free the message.
- * If it's a generic message, handle it generically, otherwise
- * call the type's message handler (if it exists)
- * XXX (race). Remember that a queued message may reference a node
- * or hook that has just been invalidated. It will exist
- * as the queue code is holding a reference, but..
+ * Definition of the bits fields in the ng_queue flag word.
+ * Defined here rather than in netgraph.h because no-one should fiddle
+ * with them.
+ *
+ * The ordering here is important! don't shuffle these. If you add
+ * READ_PENDING to the word when it has READ_PENDING already set, you
+ * generate a carry into the reader count, this you atomically add a reader,
+ * and remove the pending reader count! Similarly for the pending writer
+ * flag, adding WRITE_PENDING generates a carry and sets the WRITER_ACTIVE
+ * flag, while clearing WRITE_PENDING. When 'SINGLE_THREAD_ONLY' is set, then
+ * it is only permitted to do WRITER operations. Reader operations will
+ * result in errors.
+ * But that "hack" is unnecessary: "cpp" can do the math for us!
  */
+/*-
+ Safety Barrier--------+ (adjustable to suit taste) (not used yet)
+                       |
+                       V
++-------+-------+-------+-------+-------+-------+-------+-------+
+| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
+|A|c|t|i|v|e| |R|e|a|d|e|r| |C|o|u|n|t| | | | | | | | | |R|A|W|S|
+| | | | | | | | | | | | | | | | | | | | | | | | | | | | |P|W|P|T|
++-------+-------+-------+-------+-------+-------+-------+-------+
+\_________________________ ____________________________/ | | | |
+                          V                              | | | |
+                [active reader count]                    | | | |
+                                                         | | | |
+        Read Pending ------------------------------------+ | | |
+                                                           | | |
+        Active Writer -------------------------------------+ | |
+                                                             | |
+        Write Pending ---------------------------------------+ |
+                                                               |
+        Single Threading Only ---------------------------------+
+*/
+#define	SINGLE_THREAD_ONLY 0x00000001	/* if set, even reads single thread */
+#define WRITE_PENDING	0x00000002
+#define	WRITER_ACTIVE	0x00000004
+#define READ_PENDING	0x00000008
+#define	READER_INCREMENT 0x00000010
+#define	READER_MASK	0xfffffff0	/* Not valid if WRITER_ACTIVE is set */
+#define SAFETY_BARRIER	0x00100000	/* 64K items queued should be enough */
+/*
+ * Taking into account the current state of the queue and node, possibly take
+ * the next entry off the queue and return it. Return NULL if there was
+ * nothing we could return, either because there really was nothing there, or
+ * because the node was in a state where it cannot yet process the next item
+ * on the queue.
+ *
+ * This MUST MUST MUST be called with the mutex held.
+ */
+static __inline item_p
+ng_dequeue(struct ng_queue *ngq)
+{
+	item_p item;
+	u_int		add_arg;
+	/*
+	 * If there is a writer, then the answer is "no". Everything else
+	 * stops when there is a WRITER.
+	 */
+	if (ngq->q_flags & WRITER_ACTIVE) {
+		return (NULL);
+	}
+	/* Now take a look at what's on the queue and what's running */
+	if ((ngq->q_flags & ~(READER_MASK | SINGLE_THREAD_ONLY)) == READ_PENDING) {
+		/*
+		 * It was a reader and we have no write active. We don't care
+		 * how many readers are already active. Adjust the count for
+		 * the item we are about to dequeue. Adding READ_PENDING to
+		 * the exisiting READ_PENDING clears it and generates a carry
+		 * into the reader count.
+		 */
+		add_arg = READ_PENDING;
+	} else if ((ngq->q_flags & ~SINGLE_THREAD_ONLY) == WRITE_PENDING) {
+		/*
+		 * There is a pending write, no readers and no active writer.
+		 * This means we can go ahead with the pending writer. Note
+		 * the fact that we now have a writer, ready for when we take
+		 * it off the queue.
+		 *
+		 * We don't need to worry about a possible collision with the
+		 * fasttrack reader.
+		 *
+		 * The fasttrack thread may take a long time to discover that we
+		 * are running so we would have an inconsistent state in the
+		 * flags for a while. Since we ignore the reader count
+		 * entirely when the WRITER_ACTIVE flag is set, this should
+		 * not matter (in fact it is defined that way). If it tests
+		 * the flag before this operation, the WRITE_PENDING flag
+		 * will make it fail, and if it tests it later, the
+		 * ACTIVE_WRITER flag will do the same. If it is SO slow that
+		 * we have actually completed the operation, and neither flag
+		 * is set (nor the READ_PENDING) by the time that it tests
+		 * the flags, then it is actually ok for it to continue. If
+		 * it completes and we've finished and the read pending is
+		 * set it still fails.
+		 *
+		 * So we can just ignore it,  as long as we can ensure that the
+		 * transition from WRITE_PENDING state to the WRITER_ACTIVE
+		 * state is atomic.
+		 *
+		 * After failing, first it will be held back by the mutex, then
+		 * when it can proceed, it will queue its request, then it
+		 * would arrive at this function. Usually it will have to
+		 * leave empty handed because the ACTIVE WRITER bit wil be
+		 * set.
+		 */
+		/*
+		 * Adjust the flags for the item we are about to dequeue.
+		 * Adding WRITE_PENDING to the exisiting WRITE_PENDING clears
+		 * it and generates a carry into the WRITER_ACTIVE flag, all
+		 * atomically.
+		 */
+		add_arg = WRITE_PENDING;
+		/*
+		 * We want to write "active writer, no readers " Now go make
+		 * it true. In fact there may be a number in the readers
+		 * count but we know it is not true and will be fixed soon.
+		 * We will fix the flags for the next pending entry in a
+		 * moment.
+		 */
+	} else {
+		/*
+		 * We can't dequeue anything.. return and say so. Probably we
+		 * have a write pending and the readers count is non zero. If
+		 * we got here because a reader hit us just at the wrong
+		 * moment with the fasttrack code, and put us in a strange
+		 * state, then it will be through in just a moment, (as soon
+		 * as we release the mutex) and keep things moving.
+		 */
+		return (0);
+	}
 
-#define CALL_MSG_HANDLER(error, node, msg, retaddr, resp, hook)		\
-do {									\
-	if((msg)->header.typecookie == NGM_GENERIC_COOKIE) {		\
-		(error) = ng_generic_msg((node), (msg),			\
-			(retaddr), (resp), (hook));			\
-	} else {							\
-		if ((node)->type->rcvmsg != NULL) {			\
-			(error) = (*(node)->type->rcvmsg)((node),	\
-				(msg), (retaddr), (resp), (hook));	\
-		} else {						\
-			TRAP_ERROR;					\
-			FREE((msg), M_NETGRAPH);			\
-			(error) = EINVAL;				\
-		}							\
-	}								\
-} while (0)
+	/*
+	 * Now we dequeue the request (whatever it may be) and correct the
+	 * pending flags and the next and last pointers.
+	 */
+	item = ngq->queue;
+	ngq->queue = item->el_next;
+	if (ngq->last == &(item->el_next)) {
+		/*
+		 * that was the last entry in the queue so set the 'last
+		 * pointer up correctly and make sure the pending flags are
+		 * clear.
+		 */
+		ngq->last = &(ngq->queue);
+		/*
+		 * Whatever flag was set is cleared and the carry sets the
+		 * correct new active state/count. So we don't need to change
+		 * add_arg.
+		 */
+	} else {
+		if ((ngq->queue->el_flags & NGQF_TYPE) == NGQF_READER) {
+			/*
+			 * If we had a READ_PENDING and have another one, we
+			 * just want to add READ_PENDING twice (the same as
+			 * adding READER_INCREMENT). If we had WRITE_PENDING,
+			 * we want to add READ_PENDING + WRITE_PENDING to
+			 * clear the old WRITE_PENDING, set ACTIVE_WRITER,
+			 * and set READ_PENDING. Either way we just add
+			 * READ_PENDING to whatever we already had.
+			 */
+			add_arg += READ_PENDING;
+		} else {
+			/*
+			 * If we had a WRITE_PENDING and have another one, we
+			 * just want to add WRITE_PENDING twice (the same as
+			 * adding ACTIVE_WRITER). If we had READ_PENDING, we
+			 * want to add READ_PENDING + WRITE_PENDING to clear
+			 * the old READ_PENDING, increment the readers, and
+			 * set WRITE_PENDING. Either way we just add
+			 * WRITE_PENDING to whatever we already had.
+			 */
+			add_arg += WRITE_PENDING;
+		}
+	}
+	atomic_add_long(&ngq->q_flags, add_arg);
+	/*
+	 * We have successfully cleared the old pending flag, set the new one
+	 * if it is needed, and incremented the appropriate active field.
+	 * (all in one atomic addition.. wow)
+	 */
+	return (item);
+}
+
+/*
+ * Queue a packet to be picked up by someone else.
+ * We really don't care who, but we can't or don't want to hang around
+ * to process it ourselves. We are probably an interrupt routine..
+ * 1 = writer, 0 = reader
+ * We should set something to indicate NETISR requested
+ * If it's the first item queued.
+ */
+#define NGQRW_R 0
+#define NGQRW_W 1
+static __inline void
+ng_queue_rw(struct ng_queue * ngq, item_p  item, int rw)
+{
+	item->el_next = NULL;	/* maybe not needed */
+	*ngq->last = item;
+	/*
+	 * If it was the first item in the queue then we need to
+	 * set the last pointer and the type flags.
+	 */
+	if (ngq->last == &(ngq->queue)) {
+		/*
+		 * When called with constants for rw, the optimiser will
+		 * remove the unneeded branch below.
+		 */
+		if (rw == NGQRW_W) {
+			atomic_add_long(&ngq->q_flags, WRITE_PENDING);
+		} else {
+			atomic_add_long(&ngq->q_flags, READ_PENDING);
+		}
+	}
+	ngq->last = &(item->el_next);
+}
 
 
 /*
- * Send a control message to a node.
- * If hook is supplied, use it in preference to the address.
- * If the return address is not supplied it will be set to this node.
+ * This function 'cheats' in that it first tries to 'grab' the use of the
+ * node, without going through the mutex. We can do this becasue of the
+ * semantics of the lock. The semantics include a clause that says that the
+ * value of the readers count is invalid if the WRITER_ACTIVE flag is set. It
+ * also says that the WRITER_ACTIVE flag cannot be set if the readers count
+ * is not zero. Note that this talks about what is valid to SET the
+ * WRITER_ACTIVE flag, because from the moment it is set, the value if the
+ * reader count is immaterial, and not valid. The two 'pending' flags have a
+ * similar effect, in that If they are orthogonal to the two active fields in
+ * how they are set, but if either is set, the attempted 'grab' need to be
+ * backed out because there is earlier work, and we maintain ordering in the
+ * queue. The result of this is that the reader request can try obtain use of
+ * the node with only a single atomic addition, and without any of the mutex
+ * overhead. If this fails the operation degenerates to the same as for other
+ * cases.
+ *
  */
-int
-ng_send_msg(node_p here, struct ng_mesg *msg, const char *address,
-		hook_p hook, char *retaddr, struct ng_mesg **rptr)
+static __inline item_p
+ng_acquire_read(struct ng_queue *ngq, item_p item)
 {
-	node_p  dest = NULL;
-	int     error;
-	hook_p	lasthook;
 
+	/* ######### Hack alert ######### */
+	atomic_add_long(&ngq->q_flags, READER_INCREMENT);
+	if ((ngq->q_flags & (~READER_MASK)) == 0) {
+		/* Successfully grabbed node */
+		return (item);
+	}
+	/* undo the damage if we didn't succeed */
+	atomic_subtract_long(&ngq->q_flags, READER_INCREMENT);
+
+	/* ######### End Hack alert ######### */
+	mtx_enter((&ngq->q_mtx), MTX_SPIN);
 	/*
-	 * Find the target node.
-	 * If there is a HOOK argument, then use that in preference
-	 * to the address.
+	 * Try again. Another processor (or interrupt for that matter) may
+	 * have removed the last queued item that was stopping us from
+	 * running, between the previous test, and the moment that we took
+	 * the mutex. (Or maybe a writer completed.)
 	 */
-	if (hook) {
-		lasthook = hook->peer;
-		dest = lasthook->node;
-	} else {
-		error = ng_path2node(here, address, &dest, &lasthook);
-		if (error) {
-			FREE(msg, M_NETGRAPH);
-			return (error);
+	if ((ngq->q_flags & (~READER_MASK)) == 0) {
+		atomic_add_long(&ngq->q_flags, READER_INCREMENT);
+		mtx_exit((&ngq->q_mtx), MTX_SPIN);
+		return (item);
+	}
+
+	/*
+	 * Quick check that we are doing things right.
+	 */
+	if (ngq->q_flags & SINGLE_THREAD_ONLY) {
+		panic("Calling single treaded queue incorrectly");
+	}
+
+	/*
+	 * and queue the request for later.
+	 */
+	item->el_flags |= NGQF_TYPE;
+	ng_queue_rw(ngq, item, NGQRW_R);
+
+	/*
+	 * Ok, so that's the item successfully queued for later. So now we
+	 * see if we can dequeue something to run instead.
+	 */
+	item = ng_dequeue(ngq);
+	mtx_exit(&(ngq->q_mtx), MTX_SPIN);
+	return (item);
+}
+
+static __inline item_p
+ng_acquire_write(struct ng_queue *ngq, item_p item)
+{
+restart:
+	mtx_enter(&(ngq->q_mtx), MTX_SPIN);
+	/*
+	 * If there are no readers, no writer, and no pending packets, then
+	 * we can just go ahead. In all other situations we need to queue the
+	 * request
+	 */
+	if ((ngq->q_flags & (~SINGLE_THREAD_ONLY)) == 0) {
+		atomic_add_long(&ngq->q_flags, WRITER_ACTIVE);
+		mtx_exit((&ngq->q_mtx), MTX_SPIN);
+		if (ngq->q_flags & READER_MASK) {
+			/* Collision with fast-track reader */
+			atomic_add_long(&ngq->q_flags, -WRITER_ACTIVE);
+			goto restart;
+		}
+
+		return (item);
+	}
+
+	/*
+	 * and queue the request for later.
+	 */
+	item->el_flags &= ~NGQF_TYPE;
+	ng_queue_rw(ngq, item, NGQRW_W);
+
+	/*
+	 * Ok, so that's the item successfully queued for later. So now we
+	 * see if we can dequeue something to run instead.
+	 */
+	item = ng_dequeue(ngq);
+	mtx_exit(&(ngq->q_mtx), MTX_SPIN);
+	return (item);
+}
+
+static __inline void
+ng_leave_read(struct ng_queue *ngq)
+{
+	atomic_subtract_long(&ngq->q_flags, READER_INCREMENT);
+}
+
+static __inline void
+ng_leave_write(struct ng_queue *ngq)
+{
+	atomic_subtract_long(&ngq->q_flags, WRITER_ACTIVE);
+}
+
+static void
+ng_flush_input_queue(struct ng_queue * ngq)
+{
+	item_p item;
+	u_int		add_arg;
+	mtx_enter(&ngq->q_mtx, MTX_SPIN);
+	for (;;) {
+		/* Now take a look at what's on the queue */
+		if (ngq->q_flags & READ_PENDING) {
+			add_arg = -READ_PENDING;
+		} else if (ngq->q_flags & WRITE_PENDING) {
+			add_arg = -WRITE_PENDING;
+		} else {
+			break;
+		}
+
+		item = ngq->queue;
+		ngq->queue = item->el_next;
+		if (ngq->last == &(item->el_next)) {
+			ngq->last = &(ngq->queue);
+		} else {
+			if ((ngq->queue->el_flags & NGQF_TYPE) == NGQF_READER) {
+				add_arg += READ_PENDING;
+			} else {
+				add_arg += WRITE_PENDING;
+			}
 		}
+		atomic_add_long(&ngq->q_flags, add_arg);
+
+		mtx_exit(&ngq->q_mtx, MTX_SPIN);
+		NG_FREE_ITEM(item);
+		mtx_enter(&ngq->q_mtx, MTX_SPIN);
 	}
+	mtx_exit(&ngq->q_mtx, MTX_SPIN);
+}
+
+/***********************************************************************
+* Externally visible method for sending or queueing messages or data.
+***********************************************************************/
+
+/*
+ * MACRO WILL DO THE JOB OF CALLING ng_package_msg IN CALLER
+ * before we are called. The user code should have filled out the item
+ * correctly by this stage:
+ * Common:
+ *    reference to destination node.
+ *    Reference to destination rcv hook if relevant.
+ * Data:
+ *    pointer to mbuf
+ *    pointer to metadata
+ * Control_Message:
+ *    pointer to msg.
+ *    ID of original sender node. (return address)
+ *
+ * The nodes have several routines and macros to help with this task:
+ * ng_package_msg()
+ * ng_package_data() do much of the work.
+ * ng_retarget_msg
+ * ng_retarget_data
+ */
+
+int
+ng_snd_item(item_p item, int queue)
+{
+	hook_p hook = item->el_hook;
+	node_p dest = item->el_dest;
+	int rw;
+	int error = 0, ierror;
+	item_p	oitem;
+	struct ng_queue * ngq = &dest->input_queue;
+
+#ifdef	ITEM_DEBUG
+        _ngi_check(item, __FILE__, __LINE__);
+#endif
 
-	/* If the user didn't supply a return addres, assume it's "here". */
-	if (retaddr == NULL) {
+	if (item == NULL) {
+		return (EINVAL);	/* failed to get queue element */
+	}
+	if (dest == NULL) {
+		NG_FREE_ITEM(item);
+		return (EINVAL);	/* No address */
+	}
+	if ((item->el_flags & NGQF_D_M) == NGQF_DATA) {
 		/*
-		 * Now fill out the return address,
-		 * i.e. the name/ID of the sender. (If we didn't get one)
+		 * DATA MESSAGE
+		 * Delivered to a node via a non-optional hook.
+		 * Both should be present in the item even though
+		 * the node is derivable from the hook.
+		 * References are held on both by the item.
 		 */
-		MALLOC(retaddr, char *, NG_NODELEN + 2, M_NETGRAPH, M_NOWAIT);
-		if (retaddr == NULL) {
+#ifdef	ITEM_DEBUG
+        _ngi_check(item, __FILE__, __LINE__);
+#endif
+		CHECK_DATA_MBUF(NGI_M(item));
+		if (hook == NULL) {
+			NG_FREE_ITEM(item);
+			return(EINVAL);
+		}
+		if (((hook->flags & HK_INVALID) != 0)
+		|| ((hook->node->flags & NG_INVALID) != 0)) {
 			TRAP_ERROR;
-			return (ENOMEM);
+			NG_FREE_ITEM(item);
+			return (ENOTCONN);
 		}
-		if (here->name != NULL)
-			sprintf(retaddr, "%s:", here->name);
-		else
-			sprintf(retaddr, "[%x]:", ng_node2ID(here));
+		if ((hook->flags & HK_QUEUE)) {
+			queue = 1;
+		}
+		/* By default data is a reader in the locking scheme */
+		item->el_flags |= NGQF_READER;
+		rw = NGQRW_R;
+	} else {
+		/*
+		 * CONTROL MESSAGE
+		 * Delivered to a node.
+		 * Hook is optional.
+		 * References are held by the item on the node and
+		 * the hook if it is present.
+		 */
+		if (hook && (hook->flags & HK_QUEUE)) {
+			queue = 1;
+		}
+		/* Data messages count as writers unles explicitly exempted */
+		if (NGI_MSG(item)->header.cmd & NGM_READONLY) {
+			item->el_flags |= NGQF_READER;
+			rw = NGQRW_R;
+		} else {
+			item->el_flags &= ~NGQF_TYPE;
+			rw = NGQRW_W;
+		}
+	}
+	/*
+	 * If the node specifies single threading, force writer semantics
+	 * Similarly the node may say one hook always produces writers.
+	 * These are over-rides.
+	 */
+	if ((ngq->q_flags & SINGLE_THREAD_ONLY)
+	|| (dest->flags & NG_FORCE_WRITER)
+	|| (hook && (hook->flags & HK_FORCE_WRITER))) {
+			rw = NGQRW_W;
+			item->el_flags &= ~NGQF_TYPE;
+	}
+	if (queue) {
+		/* Put it on the queue for that node*/
+#ifdef	ITEM_DEBUG
+        _ngi_check(item, __FILE__, __LINE__);
+#endif
+		mtx_enter(&(ngq->q_mtx), MTX_SPIN);
+		ng_queue_rw(ngq, item, rw);
+		mtx_exit(&(ngq->q_mtx), MTX_SPIN);
+		/*
+		 * If there are active elements then we can rely on
+		 * them. if not we should not rely on another packet
+		 * coming here by another path,
+		 * so it is best to put us in the netisr list.
+		 */
+		if ((ngq->q_flags & (READER_MASK|WRITER_ACTIVE)) == 0) {
+			ng_setisr(ngq->q_node);
+		}
+		return (0);
 	}
+	/*
+	 * Take a queue item and a node and see if we can apply the item to
+	 * the node. We may end up getting a different item to apply instead.
+	 * Will allow for a piggyback reply only in the case where
+	 * there is no queueing.
+	 */
 
-	/* Make sure the resp field is null before we start */
-	if (rptr != NULL)
-		*rptr = NULL;
+	oitem = item;
+	/*
+	 * We already decided how we will be queueud or treated.
+	 * Try get the appropriate operating permission.
+	 */
+ 	if (rw == NGQRW_R) {
+		item = ng_acquire_read(ngq, item);
+	} else {
+		item = ng_acquire_write(ngq, item);
+	}
 
-	CALL_MSG_HANDLER(error, dest, msg, retaddr, rptr, lasthook);
+	/*
+	 * May have come back with a different item.
+	 * or maybe none at all. The one we started with will
+	 * have been queued in thises cases.
+	 */
+	if (item == NULL) {
+		return (0);
+	}
 
-	/* Make sure that if there is a response, it has the RESP bit set */
-	if ((error == 0) && rptr && *rptr)
-		(*rptr)->header.flags |= NGF_RESP;
+#ifdef	ITEM_DEBUG
+        _ngi_check(item, __FILE__, __LINE__);
+#endif
+	ierror = ng_apply_item(dest, item); /* drops r/w lock when done */
+
+	/* only return an error if it was our initial item.. (compat hack) */
+	if (oitem == item) {
+		error = ierror;
+	}
 
 	/*
-	 * If we had a return address it is up to us to free it. They should
-	 * have taken a copy if they needed to make a delayed response.
+	 * Now we've handled the packet we brought, (or a friend of it) let's
+	 * look for any other packets that may have been queued up. We hold
+	 * no locks, so if someone puts something in the queue after
+	 * we check that it is empty, it is their problem
+	 * to ensure it is processed. If we have the netisr thread cme in here
+	 * while we still say we have stuff to do, we may get a boost
+	 * in SMP systems. :-)
 	 */
-	if (retaddr)
-		FREE(retaddr, M_NETGRAPH);
-	return (error);
+	for (;;) {
+		/* quick hack to save all that mutex stuff */
+		if ((ngq->q_flags & (WRITE_PENDING | READ_PENDING)) == 0) {
+			if (dest->flags & NG_WORKQ)
+				ng_worklist_remove(dest);
+			return (0);
+		}
+		/*
+		 * dequeue acquires and adjusts the input_queue as it dequeues
+		 * packets. It acquires the rw lock as needed.
+		 */
+		mtx_enter(&ngq->q_mtx, MTX_SPIN);
+		item = ng_dequeue(ngq);
+		mtx_exit(&ngq->q_mtx, MTX_SPIN);
+		if (!item) {
+			/*
+			 * If we have no work to do
+			 * then we certainly don't need to be
+			 * on the worklist.
+			 */
+			if (dest->flags & NG_WORKQ)
+				ng_worklist_remove(dest);
+			return (0);
+		}
+#ifdef	ITEM_DEBUG
+        _ngi_check(item, __FILE__, __LINE__);
+#endif
+
+		/*
+		 * We have the appropriate lock, so run the item.
+		 * When finished it will drop the lock accordingly
+		 */
+
+		ierror = ng_apply_item(dest, item);
+		/*
+		 * only return an error if it was our initial
+		 * item.. (compat hack)
+		 */
+		if (oitem == item) {
+			error = ierror;
+		}
+	}
+	return (0);
 }
 
 /*
- * Implement the 'generic' control messages
+ * We have an item that was possibly queued somewhere.
+ * It should contain all the information needed
+ * to run it on the appropriate node/hook.
  */
 static int
-ng_generic_msg(node_p here, struct ng_mesg *msg, const char *retaddr,
-	       struct ng_mesg **resp, hook_p lasthook)
+ng_apply_item(node_p node, item_p item)
+{
+	hook_p  hook;
+	int was_reader = ((item->el_flags & NGQF_TYPE));
+	int error = 0;
+	ng_rcvdata_t *rcvdata;
+
+	hook = item->el_hook;
+	item->el_hook = NULL;	/* so NG_FREE_ITEM doesn't ng_unref_hook() */
+	/* We already have the node.. assume responsibility */
+	/* And the reference */
+	/* node = item->el_dest; */
+	item->el_dest = NULL;	/* same as for the hook above */
+#ifdef	ITEM_DEBUG
+        _ngi_check(item, __FILE__, __LINE__);
+#endif
+
+	switch (item->el_flags & NGQF_D_M) {
+	case NGQF_DATA:
+		/*
+		 * Check things are still ok as when we were queued.
+		 */
+
+		if ((hook == NULL)
+		|| ((hook->flags & HK_INVALID) != 0)
+		|| ((hook->node->flags & NG_INVALID) != 0)
+		|| ((rcvdata = hook->node->type->rcvdata) == NULL)) {
+			error = EIO;
+			NG_FREE_ITEM(item);
+		} else {
+			error = (*rcvdata)(hook, item);
+		}
+		break;
+	case NGQF_MESG:
+
+		if (hook) {
+			item->el_hook = NULL;
+			if ((hook->flags & HK_INVALID) != 0) {
+			/*
+			 * If the hook has been zapped then we can't use it.
+			 * Immediatly drop its reference.
+			 * The message may not need it.
+			 */
+				ng_unref_hook(hook);
+				hook = NULL;
+			}
+		}
+		/*
+		 * Similarly, if the node is a zombie there is
+		 * nothing we can do with it, drop everything.
+		 */
+		if (node->flags & NG_INVALID) {
+			error = EINVAL;
+			NG_FREE_ITEM(item);
+		} else {
+			/*
+			 * Call the appropriate message handler for the object.
+			 * It is up to the message handler to free the message.
+			 * If it's a generic message, handle it generically,
+			 * otherwise call the type's message handler
+			 * (if it exists)
+			 * XXX (race). Remember that a queued message may
+			 * reference a node or hook that has just been
+			 * invalidated. It will exist as the queue code
+			 * is holding a reference, but..
+			 */
+
+			struct ng_mesg *msg = NGI_MSG(item);
+
+			if ((msg->header.typecookie == NGM_GENERIC_COOKIE)
+			&& ((msg->header.flags & NGF_RESP) == 0)) {
+				error = ng_generic_msg(node, item, hook);
+			} else {
+				if ((node)->type->rcvmsg != NULL) {
+					error = (*(node)->type->rcvmsg)((node),
+						(item), (hook));
+				} else {
+					TRAP_ERROR;
+					error = EINVAL; /* XXX */
+					NG_FREE_ITEM(item);
+				}
+			}
+			/* item is now invalid */
+		}
+		break;
+	}
+	/*
+	 * We held references on some of the resources
+	 * that we took from the item. Now that we have
+	 * finished doing everything, drop those references.
+	 */
+	if (hook) {
+		ng_unref_hook(hook);
+	}
+
+	if (was_reader) {
+		ng_leave_read(&node->input_queue);
+	} else {
+		ng_leave_write(&node->input_queue);
+	}
+	ng_unref(node);
+	return (error);
+}
+
+/***********************************************************************
+ * Implement the 'generic' control messages
+ ***********************************************************************/
+static int
+ng_generic_msg(node_p here, item_p item, hook_p lasthook)
 {
 	int error = 0;
+	struct ng_mesg *msg;
+	struct ng_mesg *resp = NULL;
 
+	NGI_GET_MSG(item, msg);
 	if (msg->header.typecookie != NGM_GENERIC_COOKIE) {
-		TRAP_ERROR;
-		FREE(msg, M_NETGRAPH);
-		return (EINVAL);
+		error = EINVAL;
+		goto out;
 	}
 	switch (msg->header.cmd) {
 	case NGM_SHUTDOWN:
@@ -1235,8 +2000,8 @@ ng_generic_msg(node_p here, struct ng_mesg *msg, const char *retaddr,
 		struct ngm_mkpeer *const mkp = (struct ngm_mkpeer *) msg->data;
 
 		if (msg->header.arglen != sizeof(*mkp)) {
-			TRAP_ERROR;
-			return (EINVAL);
+			error = EINVAL;
+			break;
 		}
 		mkp->type[sizeof(mkp->type) - 1] = '\0';
 		mkp->ourhook[sizeof(mkp->ourhook) - 1] = '\0';
@@ -1251,16 +2016,18 @@ ng_generic_msg(node_p here, struct ng_mesg *msg, const char *retaddr,
 		node_p node2;
 
 		if (msg->header.arglen != sizeof(*con)) {
-			TRAP_ERROR;
-			return (EINVAL);
+			error = EINVAL;
+			break;
 		}
 		con->path[sizeof(con->path) - 1] = '\0';
 		con->ourhook[sizeof(con->ourhook) - 1] = '\0';
 		con->peerhook[sizeof(con->peerhook) - 1] = '\0';
-		error = ng_path2node(here, con->path, &node2, NULL);
+		/* Don't forget we get a reference.. */
+		error = ng_path2noderef(here, con->path, &node2, NULL);
 		if (error)
 			break;
 		error = ng_con_nodes(here, con->ourhook, node2, con->peerhook);
+		ng_unref(node2);
 		break;
 	    }
 	case NGM_NAME:
@@ -1268,8 +2035,8 @@ ng_generic_msg(node_p here, struct ng_mesg *msg, const char *retaddr,
 		struct ngm_name *const nam = (struct ngm_name *) msg->data;
 
 		if (msg->header.arglen != sizeof(*nam)) {
-			TRAP_ERROR;
-			return (EINVAL);
+			error = EINVAL;
+			break;
 		}
 		nam->name[sizeof(nam->name) - 1] = '\0';
 		error = ng_name_node(here, nam->name);
@@ -1281,8 +2048,8 @@ ng_generic_msg(node_p here, struct ng_mesg *msg, const char *retaddr,
 		hook_p hook;
 
 		if (msg->header.arglen != sizeof(*rmh)) {
-			TRAP_ERROR;
-			return (EINVAL);
+			error = EINVAL;
+			break;
 		}
 		rmh->ourhook[sizeof(rmh->ourhook) - 1] = '\0';
 		if ((hook = ng_findhook(here, rmh->ourhook)) != NULL)
@@ -1292,27 +2059,20 @@ ng_generic_msg(node_p here, struct ng_mesg *msg, const char *retaddr,
 	case NGM_NODEINFO:
 	    {
 		struct nodeinfo *ni;
-		struct ng_mesg *rp;
 
-		/* Get response struct */
+		NG_MKRESPONSE(resp, msg, sizeof(*ni), M_NOWAIT);
 		if (resp == NULL) {
-			error = EINVAL;
-			break;
-		}
-		NG_MKRESPONSE(rp, msg, sizeof(*ni), M_NOWAIT);
-		if (rp == NULL) {
 			error = ENOMEM;
 			break;
 		}
 
 		/* Fill in node info */
-		ni = (struct nodeinfo *) rp->data;
+		ni = (struct nodeinfo *) resp->data;
 		if (here->name != NULL)
 			strncpy(ni->name, here->name, NG_NODELEN);
 		strncpy(ni->type, here->type->name, NG_TYPELEN);
 		ni->id = ng_node2ID(here);
 		ni->hooks = here->numhooks;
-		*resp = rp;
 		break;
 	    }
 	case NGM_LISTHOOKS:
@@ -1320,21 +2080,16 @@ ng_generic_msg(node_p here, struct ng_mesg *msg, const char *retaddr,
 		const int nhooks = here->numhooks;
 		struct hooklist *hl;
 		struct nodeinfo *ni;
-		struct ng_mesg *rp;
 		hook_p hook;
 
 		/* Get response struct */
-		if (resp == NULL) {
-			error = EINVAL;
-			break;
-		}
-		NG_MKRESPONSE(rp, msg, sizeof(*hl)
+		NG_MKRESPONSE(resp, msg, sizeof(*hl)
 		    + (nhooks * sizeof(struct linkinfo)), M_NOWAIT);
-		if (rp == NULL) {
+		if (resp == NULL) {
 			error = ENOMEM;
 			break;
 		}
-		hl = (struct hooklist *) rp->data;
+		hl = (struct hooklist *) resp->data;
 		ni = &hl->nodeinfo;
 
 		/* Fill in node info */
@@ -1357,7 +2112,7 @@ ng_generic_msg(node_p here, struct ng_mesg *msg, const char *retaddr,
 				continue;
 			strncpy(link->ourhook, hook->name, NG_HOOKLEN);
 			strncpy(link->peerhook, hook->peer->name, NG_HOOKLEN);
-			if (hook->peer->node->name != NULL)
+			if (hook->peer->node->name[0] != '\0')
 				strncpy(link->nodeinfo.name,
 				    hook->peer->node->name, NG_NODELEN);
 			strncpy(link->nodeinfo.type,
@@ -1366,7 +2121,6 @@ ng_generic_msg(node_p here, struct ng_mesg *msg, const char *retaddr,
 			link->nodeinfo.hooks = hook->peer->node->numhooks;
 			ni->hooks++;
 		}
-		*resp = rp;
 		break;
 	    }
 
@@ -1375,37 +2129,30 @@ ng_generic_msg(node_p here, struct ng_mesg *msg, const char *retaddr,
 	    {
 		const int unnamed = (msg->header.cmd == NGM_LISTNODES);
 		struct namelist *nl;
-		struct ng_mesg *rp;
 		node_p node;
 		int num = 0;
 
-		if (resp == NULL) {
-			error = EINVAL;
-			break;
-		}
-
+		mtx_enter(&ng_nodelist_mtx, MTX_DEF);
 		/* Count number of nodes */
-		LIST_FOREACH(node, &nodelist, nodes) {
-			if (unnamed || node->name != NULL)
+		LIST_FOREACH(node, &ng_nodelist, nodes) {
+			if (unnamed || node->name[0] != '\0')
 				num++;
 		}
+		mtx_exit(&ng_nodelist_mtx, MTX_DEF);
 
 		/* Get response struct */
-		if (resp == NULL) {
-			error = EINVAL;
-			break;
-		}
-		NG_MKRESPONSE(rp, msg, sizeof(*nl)
+		NG_MKRESPONSE(resp, msg, sizeof(*nl)
 		    + (num * sizeof(struct nodeinfo)), M_NOWAIT);
-		if (rp == NULL) {
+		if (resp == NULL) {
 			error = ENOMEM;
 			break;
 		}
-		nl = (struct namelist *) rp->data;
+		nl = (struct namelist *) resp->data;
 
 		/* Cycle through the linked list of nodes */
 		nl->numnames = 0;
-		LIST_FOREACH(node, &nodelist, nodes) {
+		mtx_enter(&ng_nodelist_mtx, MTX_DEF);
+		LIST_FOREACH(node, &ng_nodelist, nodes) {
 			struct nodeinfo *const np = &nl->nodeinfo[nl->numnames];
 
 			if (nl->numnames >= num) {
@@ -1415,51 +2162,44 @@ ng_generic_msg(node_p here, struct ng_mesg *msg, const char *retaddr,
 			}
 			if ((node->flags & NG_INVALID) != 0)
 				continue;
-			if (!unnamed && node->name == NULL)
+			if (!unnamed && node->name[0] == '\0')
 				continue;
-			if (node->name != NULL)
+			if (node->name[0] != '\0')
 				strncpy(np->name, node->name, NG_NODELEN);
 			strncpy(np->type, node->type->name, NG_TYPELEN);
 			np->id = ng_node2ID(node);
 			np->hooks = node->numhooks;
 			nl->numnames++;
 		}
-		*resp = rp;
+		mtx_exit(&ng_nodelist_mtx, MTX_DEF);
 		break;
 	    }
 
 	case NGM_LISTTYPES:
 	    {
 		struct typelist *tl;
-		struct ng_mesg *rp;
 		struct ng_type *type;
 		int num = 0;
 
-		if (resp == NULL) {
-			error = EINVAL;
-			break;
-		}
-
+		mtx_enter(&ng_typelist_mtx, MTX_DEF);
 		/* Count number of types */
-		LIST_FOREACH(type, &typelist, types)
+		LIST_FOREACH(type, &ng_typelist, types)
 			num++;
+		mtx_exit(&ng_typelist_mtx, MTX_DEF);
 
 		/* Get response struct */
-		if (resp == NULL) {
-			error = EINVAL;
-			break;
-		}
-		NG_MKRESPONSE(rp, msg, sizeof(*tl)
+		NG_MKRESPONSE(resp, msg, sizeof(*tl)
 		    + (num * sizeof(struct typeinfo)), M_NOWAIT);
-		if (rp == NULL) {
+		if (resp == NULL) {
 			error = ENOMEM;
 			break;
 		}
-		tl = (struct typelist *) rp->data;
+		tl = (struct typelist *) resp->data;
 
 		/* Cycle through the linked list of types */
 		tl->numtypes = 0;
-		LIST_FOREACH(type, &typelist, types) {
+		mtx_enter(&ng_typelist_mtx, MTX_DEF);
+		LIST_FOREACH(type, &ng_typelist, types) {
 			struct typeinfo *const tp = &tl->typeinfo[tl->numtypes];
 
 			if (tl->numtypes >= num) {
@@ -1471,7 +2211,7 @@ ng_generic_msg(node_p here, struct ng_mesg *msg, const char *retaddr,
 			tp->numnodes = type->refs;
 			tl->numtypes++;
 		}
-		*resp = rp;
+		mtx_exit(&ng_typelist_mtx, MTX_DEF);
 		break;
 	    }
 
@@ -1480,30 +2220,24 @@ ng_generic_msg(node_p here, struct ng_mesg *msg, const char *retaddr,
 		int bufSize = 20 * 1024;	/* XXX hard coded constant */
 		const struct ng_parse_type *argstype;
 		const struct ng_cmdlist *c;
-		struct ng_mesg *rp, *binary, *ascii;
+		struct ng_mesg *binary, *ascii;
 
 		/* Data area must contain a valid netgraph message */
 		binary = (struct ng_mesg *)msg->data;
 		if (msg->header.arglen < sizeof(struct ng_mesg)
-		    || msg->header.arglen - sizeof(struct ng_mesg) 
+		    || msg->header.arglen - sizeof(struct ng_mesg)
 		      < binary->header.arglen) {
 			error = EINVAL;
 			break;
 		}
 
-		/* Check response pointer */
-		if (resp == NULL) {
-			error = EINVAL;
-			break;
-		}
-
 		/* Get a response message with lots of room */
-		NG_MKRESPONSE(rp, msg, sizeof(*ascii) + bufSize, M_NOWAIT);
-		if (rp == NULL) {
+		NG_MKRESPONSE(resp, msg, sizeof(*ascii) + bufSize, M_NOWAIT);
+		if (resp == NULL) {
 			error = ENOMEM;
 			break;
 		}
-		ascii = (struct ng_mesg *)rp->data;
+		ascii = (struct ng_mesg *)resp->data;
 
 		/* Copy binary message header to response message payload */
 		bcopy(binary, ascii, sizeof(*binary));
@@ -1522,7 +2256,7 @@ ng_generic_msg(node_p here, struct ng_mesg *msg, const char *retaddr,
 					break;
 			}
 			if (c->name == NULL) {
-				FREE(rp, M_NETGRAPH);
+				NG_FREE_MSG(resp);
 				error = ENOSYS;
 				break;
 			}
@@ -1541,7 +2275,7 @@ ng_generic_msg(node_p here, struct ng_mesg *msg, const char *retaddr,
 			if ((error = ng_unparse(argstype,
 			    (u_char *)binary->data,
 			    ascii->data, bufSize)) != 0) {
-				FREE(rp, M_NETGRAPH);
+				NG_FREE_MSG(resp);
 				break;
 			}
 		}
@@ -1549,8 +2283,7 @@ ng_generic_msg(node_p here, struct ng_mesg *msg, const char *retaddr,
 		/* Return the result as struct ng_mesg plus ASCII string */
 		bufSize = strlen(ascii->data) + 1;
 		ascii->header.arglen = bufSize;
-		rp->header.arglen = sizeof(*ascii) + bufSize;
-		*resp = rp;
+		resp->header.arglen = sizeof(*ascii) + bufSize;
 		break;
 	    }
 
@@ -1559,7 +2292,7 @@ ng_generic_msg(node_p here, struct ng_mesg *msg, const char *retaddr,
 		int bufSize = 2000;	/* XXX hard coded constant */
 		const struct ng_cmdlist *c;
 		const struct ng_parse_type *argstype;
-		struct ng_mesg *rp, *ascii, *binary;
+		struct ng_mesg *ascii, *binary;
 		int off = 0;
 
 		/* Data area must contain at least a struct ng_mesg + '\0' */
@@ -1573,19 +2306,13 @@ ng_generic_msg(node_p here, struct ng_mesg *msg, const char *retaddr,
 		}
 		ascii->data[ascii->header.arglen - 1] = '\0';
 
-		/* Check response pointer */
-		if (resp == NULL) {
-			error = EINVAL;
-			break;
-		}
-
 		/* Get a response message with lots of room */
-		NG_MKRESPONSE(rp, msg, sizeof(*binary) + bufSize, M_NOWAIT);
-		if (rp == NULL) {
+		NG_MKRESPONSE(resp, msg, sizeof(*binary) + bufSize, M_NOWAIT);
+		if (resp == NULL) {
 			error = ENOMEM;
 			break;
 		}
-		binary = (struct ng_mesg *)rp->data;
+		binary = (struct ng_mesg *)resp->data;
 
 		/* Copy ASCII message header to response message payload */
 		bcopy(ascii, binary, sizeof(*ascii));
@@ -1602,7 +2329,7 @@ ng_generic_msg(node_p here, struct ng_mesg *msg, const char *retaddr,
 					break;
 			}
 			if (c->name == NULL) {
-				FREE(rp, M_NETGRAPH);
+				NG_FREE_MSG(resp);
 				error = ENOSYS;
 				break;
 			}
@@ -1620,15 +2347,14 @@ ng_generic_msg(node_p here, struct ng_mesg *msg, const char *retaddr,
 		else {
 			if ((error = ng_parse(argstype, ascii->data,
 			    &off, (u_char *)binary->data, &bufSize)) != 0) {
-				FREE(rp, M_NETGRAPH);
+				NG_FREE_MSG(resp);
 				break;
 			}
 		}
 
 		/* Return the result */
 		binary->header.arglen = bufSize;
-		rp->header.arglen = sizeof(*binary) + bufSize;
-		*resp = rp;
+		resp->header.arglen = sizeof(*binary) + bufSize;
 		break;
 	    }
 
@@ -1637,79 +2363,34 @@ ng_generic_msg(node_p here, struct ng_mesg *msg, const char *retaddr,
 		/*
 		 * This one is tricky as it passes the command down to the
 		 * actual node, even though it is a generic type command.
-		 * This means we must assume that the msg is already freed
+		 * This means we must assume that the item/msg is already freed
 		 * when control passes back to us.
 		 */
-		if (resp == NULL) {
-			error = EINVAL;
-			break;
+		if (here->type->rcvmsg != NULL) {
+			NGI_MSG(item) = msg; /* put it back as we found it */
+			return((*here->type->rcvmsg)(here, item, lasthook));
 		}
-		if (here->type->rcvmsg != NULL)
-			return((*here->type->rcvmsg)(here, msg, retaddr,
-			resp, lasthook));
 		/* Fall through if rcvmsg not supported */
 	default:
 		TRAP_ERROR;
 		error = EINVAL;
 	}
-	FREE(msg, M_NETGRAPH);
+	/*
+	 * Sometimes a generic message may be statically allocated
+	 * to avoid problems with allocating when in tight memeory situations.
+	 * Don't free it if it is so.
+	 * I break them appart here, because erros may cause a free if the item
+	 * in which case we'd be doing it twice.
+	 * they are kept together above, to simplify freeing.
+	 */
+out:
+	NG_RESPOND_MSG(error, here, item, resp);
+	if ( msg && ((msg->header.flags & NGF_STATIC) == 0))
+		NG_FREE_MSG(msg);
 	return (error);
 }
 
 /*
- * Send a data packet to a node. If the recipient has no
- * 'receive data' method, then silently discard the packet.
- * The receiving node may elect to put the data onto the netgraph
- * NETISR queue for later delivery. It may do this because it knows there
- * is some recursion and wishes to unwind the stack, or because it has
- * some suspicion that it is being called at (say) splimp instead of
- * splnet.
- */
-int 
-ng_send_data(hook_p hook, struct mbuf *m, meta_p meta,
-	struct mbuf **ret_m, meta_p *ret_meta, struct ng_mesg **resp)
-{
-	ng_rcvdata_t *rcvdata;
-
-	CHECK_DATA_MBUF(m);
-	if ((hook == NULL)
-	|| ((hook->flags & HK_INVALID) != 0)
-	|| ((rcvdata = hook->peer->node->type->rcvdata) == NULL)) {
-		TRAP_ERROR;
-		NG_FREE_DATA(m, meta);
-		return (ENOTCONN);
-	}
-	if (hook->peer->flags & HK_QUEUE) {
-		return (ng_queue_data(hook, m, meta));
-	}
-	return ( (*rcvdata)(hook->peer, m, meta, ret_m, ret_meta, resp));
-}
-
-/*
- * Send a queued data packet to a node. 
- *
- * This is meant for data that is being dequeued and should therefore NOT
- * be queued again. It ignores the queue flag and should NOT be called
- * outside of this file. (thus it is static)
- */
-static int 
-ng_send_data_dont_queue(hook_p hook, struct mbuf *m, meta_p meta,
-	struct mbuf **ret_m, meta_p *ret_meta, struct ng_mesg **resp)
-{
-	ng_rcvdata_t *rcvdata;
-
-	CHECK_DATA_MBUF(m);
-	if ((hook == NULL)
-	|| ((hook->flags & HK_INVALID) != 0)
-	|| ((rcvdata = hook->peer->node->type->rcvdata) == NULL)) {
-		TRAP_ERROR;
-		NG_FREE_DATA(m, meta);
-		return (ENOTCONN);
-	} 
-	return ((*rcvdata)(hook->peer, m, meta, ret_m, ret_meta, resp));
-}
-
-/*
  * Copy a 'meta'.
  *
  * Returns new meta, or NULL if original meta is NULL or ENOMEM.
@@ -1721,7 +2402,7 @@ ng_copy_meta(meta_p meta)
 
 	if (meta == NULL)
 		return (NULL);
-	MALLOC(meta2, meta_p, meta->used_len, M_NETGRAPH, M_NOWAIT);
+	MALLOC(meta2, meta_p, meta->used_len, M_NETGRAPH_META, M_NOWAIT);
 	if (meta2 == NULL)
 		return (NULL);
 	meta2->allocated_len = meta->used_len;
@@ -1754,8 +2435,11 @@ ng_mod_event(module_t mod, int event, void *data)
 
 		/* Call type specific code */
 		if (type->mod_event != NULL)
-			if ((error = (*type->mod_event)(mod, event, data)) != 0)
+			if ((error = (*type->mod_event)(mod, event, data))) {
+				mtx_enter(&ng_typelist_mtx, MTX_DEF);
 				LIST_REMOVE(type, types);
+				mtx_exit(&ng_typelist_mtx, MTX_DEF);
+			}
 		splx(s);
 		break;
 
@@ -1771,7 +2455,9 @@ ng_mod_event(module_t mod, int event, void *data)
 					break;
 				}
 			}
+			mtx_enter(&ng_typelist_mtx, MTX_DEF);
 			LIST_REMOVE(type, types);
+			mtx_exit(&ng_typelist_mtx, MTX_DEF);
 		}
 		splx(s);
 		break;
@@ -1798,6 +2484,11 @@ ngb_mod_event(module_t mod, int event, void *data)
 	switch (event) {
 	case MOD_LOAD:
 		/* Register line discipline */
+		mtx_init(&ng_worklist_mtx, "netgraph worklist mutex", 0);
+		mtx_init(&ng_typelist_mtx, "netgraph types mutex", 0);
+		mtx_init(&ng_nodelist_mtx, "netgraph nodelist mutex", 0);
+		mtx_init(&ng_idhash_mtx, "netgraph idhash mutex", 0);
+		mtx_init(&ngq_mtx, "netgraph netisr mutex", 0);
 		s = splimp();
 		error = register_netisr(NETISR_NETGRAPH, ngintr);
 		splx(s);
@@ -1821,276 +2512,561 @@ static moduledata_t netgraph_mod = {
 DECLARE_MODULE(netgraph, netgraph_mod, SI_SUB_DRIVERS, SI_ORDER_MIDDLE);
 
 /************************************************************************
-			Queueing routines
+			Queue element get/free routines
 ************************************************************************/
 
-/* The structure for queueing across ISR switches */
-struct ng_queue_entry {
-	u_long	flags;
-	struct ng_queue_entry *next;
-	union {
-		struct {
-			hook_p		da_hook;	/*  target hook */
-			struct mbuf	*da_m;
-			meta_p		da_meta;
-		} data;
-		struct {
-			struct ng_mesg	*msg_msg;
-			node_p		msg_node;
-			hook_p		msg_lasthook;
-			char		*msg_retaddr;
-		} msg;
-	} body;
-};
-#define NGQF_DATA	0x01		/* the queue element is data */
-#define NGQF_MESG	0x02		/* the queue element is a message */
-
-static struct ng_queue_entry   *ngqbase;	/* items to be unqueued */
-static struct ng_queue_entry   *ngqlast;	/* last item queued */
-static const int		ngqroom = 64;	/* max items to queue */
-static int			ngqsize;	/* number of items in queue */
-
-static struct ng_queue_entry   *ngqfree;	/* free ones */
-static const int		ngqfreemax = 16;/* cache at most this many */
-static int			ngqfreesize;	/* number of cached entries */
 
+static int			allocated;	/* number of items malloc'd */
+static int			maxalloc = 128;	/* limit the damage of a leak */
+static const int		ngqfreemax = 64;/* cache at most this many */
+static const int		ngqfreelow = 4; /* try malloc if free < this */
+static volatile int		ngqfreesize;	/* number of cached entries */
+#ifdef	ITEM_DEBUG
+static TAILQ_HEAD(, ng_item) ng_itemlist = TAILQ_HEAD_INITIALIZER(ng_itemlist);
+#endif
 /*
  * Get a queue entry
+ * This is usually called when a packet first enters netgraph.
+ * By definition, this is usually from an interrupt, or from a user.
+ * Users are not so important, but try be quick for the times that it's
+ * an interrupt. Use atomic operations to cope with collisions
+ * with interrupts and other processors. Assumes MALLOC is SMP safe.
+ * XXX If reserve is low, we should try to get 2 from malloc as this
+ * would indicate it often fails.
  */
-static struct ng_queue_entry *
+static item_p
 ng_getqblk(void)
 {
-	register struct ng_queue_entry *q;
-	int s;
+	item_p item = NULL;
 
-	/* Could be guarding against tty ints or whatever */
-	s = splhigh();
+	/*
+	 * Try get a cached queue block, or else allocate a new one
+	 * If we are less than our reserve, try malloc. If malloc
+	 * fails, then that's what the reserve is for...
+	 * Don't completely trust ngqfreesize, as it is subject
+	 * to races.. (it'll eventually catch up but may be out by one or two
+	 * for brief moments(under SMP or interrupts).
+	 * ngqfree is the final arbiter. We have our little reserve
+	 * because we use M_NOWAIT for malloc. This just helps us
+	 * avoid dropping packets while not increasing the time
+	 * we take to service the interrupt (on average) (we hope).
+	 */
+	for (;;) {
+		if ((ngqfreesize < ngqfreelow) || (ngqfree == NULL)) {
+			if (allocated < maxalloc) {  /* don't leak forever */
+				MALLOC(item, item_p ,
+				    sizeof(*item), M_NETGRAPH_ITEM,
+				    (M_NOWAIT | M_ZERO));
+				if (item) {
+#ifdef	ITEM_DEBUG
+					TAILQ_INSERT_TAIL(&ng_itemlist,
+								item, all);
+#endif	/* ITEM_DEBUG */
+					atomic_add_int(&allocated, 1);
+					break;
+				}
+			}
+		}
 
-	/* Try get a cached queue block, or else allocate a new one */
-	if ((q = ngqfree) == NULL) {
-		splx(s);
-		if (ngqsize < ngqroom) {	/* don't worry about races */
-			MALLOC(q, struct ng_queue_entry *,
-			    sizeof(*q), M_NETGRAPH, M_NOWAIT);
+		/*
+		 * We didn't or couldn't malloc.
+		 * try get one from our cache.
+		 * item must be NULL to get here.
+		 */
+		if ((item = ngqfree) != NULL) {
+			/*
+			 * Atomically try grab the first item
+			 * and put it's successor in its place.
+			 * If we fail, just try again.. someone else
+			 * beat us to this one or freed one.
+			 * Don't worry about races with ngqfreesize.
+			 * Close enough is good enough..
+			 */
+			if (atomic_cmpset_ptr(&ngqfree, item, item->el_next)) {
+				atomic_subtract_int(&ngqfreesize, 1);
+				break;
+			}
+			item = NULL;
+		} else {
+			/* We really ran out */
+			break;
 		}
-	} else {
-		ngqfree = q->next;
-		ngqfreesize--;
-		splx(s);
 	}
-	return (q);
+	item->el_flags &= ~NGQF_FREE;
+	return (item);
 }
 
 /*
  * Release a queue entry
  */
-#define RETURN_QBLK(q)							\
-do {									\
-	int s;								\
-	if (ngqfreesize < ngqfreemax) { /* don't worry about races */ 	\
-		s = splhigh();						\
-		(q)->next = ngqfree;					\
-		ngqfree = (q);						\
-		ngqfreesize++;						\
-		splx(s);						\
-	} else {							\
-		FREE((q), M_NETGRAPH);					\
-	}								\
-} while (0)
-
-/*
- * Running at a raised (but we don't know which) processor priority level,
- * put the data onto a queue to be picked up by another PPL (probably splnet)
- */
-int
-ng_queue_data(hook_p hook, struct mbuf *m, meta_p meta)
+void
+ng_free_item(item_p item)
 {
-	struct ng_queue_entry *q;
-	int s;
 
-	if (hook == NULL) {
-		NG_FREE_DATA(m, meta);
-		return (0);
+	/*
+	 * The item may hold resources on it's own. We need to free
+	 * these before we can free the item. What they are depends upon
+	 * what kind of item it is. it is important that nodes zero
+	 * out pointers to resources that they remove from the item
+	 * or we release them again here.
+	 */
+	if (item->el_flags & NGQF_FREE) {
+		panic(" Freeing free queue item");
+	}
+	switch (item->el_flags & NGQF_D_M) {
+	case NGQF_DATA:
+		/* If we have an mbuf and metadata still attached.. */
+		NG_FREE_M(_NGI_M(item));
+		NG_FREE_META(_NGI_META(item));
+		break;
+	case NGQF_MESG:
+		_NGI_RETADDR(item) = NULL;
+		NG_FREE_MSG(_NGI_MSG(item));
+		break;
 	}
-	if ((q = ng_getqblk()) == NULL) {
-		NG_FREE_DATA(m, meta);
-		return (ENOBUFS);
+		/* If we still have a node or hook referenced... */
+	if (item->el_dest) {
+		ng_unref(item->el_dest);
+		item->el_dest = NULL;
 	}
+	if (item->el_hook) {
+		ng_unref_hook(item->el_hook);
+		item->el_hook = NULL;
+	}
+	item->el_flags |= NGQF_FREE;
 
-	/* Fill out the contents */
-	q->flags = NGQF_DATA;
-	q->next = NULL;
-	q->body.data.da_hook = hook;
-	q->body.data.da_m = m;
-	q->body.data.da_meta = meta;
-	s = splhigh();		/* protect refs and queue */
-	hook->refs++;		/* don't let it go away while on the queue */
-
-	/* Put it on the queue */
-	if (ngqbase) {
-		ngqlast->next = q;
+	/*
+	 * We have freed any resources held by the item.
+	 * now we can free the item itself.
+	 */
+	if (ngqfreesize < ngqfreemax) { /* don't worry about races */
+		for (;;) {
+			item->el_next = ngqfree;
+			if (atomic_cmpset_ptr(&ngqfree, item->el_next, item)) {
+				break;
+			}
+		}
+		atomic_add_int(&ngqfreesize, 1);
 	} else {
-		ngqbase = q;
+		/* This is the only place that should use this Macro */
+#ifdef	ITEM_DEBUG
+		TAILQ_REMOVE(&ng_itemlist, item, all);
+#endif	/* ITEM_DEBUG */
+		NG_FREE_ITEM_REAL(item);
+		atomic_subtract_int(&allocated, 1);
 	}
-	ngqlast = q;
-	ngqsize++;
-	splx(s);
+}
 
-	/* Schedule software interrupt to handle it later */
-	schednetisr(NETISR_NETGRAPH);
-	return (0);
+#ifdef	ITEM_DEBUG
+void
+dumpitem(item_p item, char *file, int line)
+{
+	if (item->el_flags & NGQF_FREE) {
+		printf(" Free item, freed at %s, line %d\n",
+			item->lastfile, item->lastline);
+	} else {
+		printf(" ACTIVE item, last used at %s, line %d",
+			item->lastfile, item->lastline);
+		if ((item->el_flags & NGQF_D_M) == NGQF_MESG) {
+			printf(" - retaddr[%d]:\n", _NGI_RETADDR(item));
+		} else {
+			printf(" - [data]\n");
+		}
+	}
+	printf(" problem discovered at file %s, line %d\n", file, line);
+	if (item->el_dest)
+		printf("node %X ([%x])\n",
+			item->el_dest, ng_node2ID(item->el_dest));
 }
 
+static int
+sysctl_debug_ng_dump_items(SYSCTL_HANDLER_ARGS)
+{
+	int error;
+	int val;
+	item_p item;
+	int i;
+
+	val = allocated;
+	i = 1;
+	error = sysctl_handle_int(oidp, &val, sizeof(int), req);
+	TAILQ_FOREACH(item, &ng_itemlist, all) {
+		if (item->el_flags & NGQF_FREE) {
+			printf("[%d] free item, freed at %s, line %d\n",
+				i++, item->lastfile, item->lastline);
+		} else {
+			printf("[%d] ACTIVE item, last used at %s, line %d",
+				i++, item->lastfile, item->lastline);
+			if ((item->el_flags & NGQF_D_M) == NGQF_MESG) {
+				printf(" - retaddr[%d]:\n", _NGI_RETADDR(item));
+			} else {
+				printf(" - [data]\n");
+			}
+		}
+		if (item->el_dest) {
+			printf("node %X ([%x])",
+				item->el_dest, ng_node2ID(item->el_dest));
+			printf("<%X>\n",item->el_dest->input_queue.q_flags);
+		} 
+	}
+	return error;
+}
+
+SYSCTL_PROC(_debug, OID_AUTO, ng_dump_items, CTLTYPE_INT | CTLFLAG_RD,
+    0, 0, sysctl_debug_ng_dump_items, "I", "Number of allocated items");
+#endif	/* ITEM_DEBUG */
+
+
+/***********************************************************************
+* Worklist routines
+**********************************************************************/
+/* NETISR thread enters here */
 /*
- * Running at a raised (but we don't know which) processor priority level,
- * put the msg onto a queue to be picked up by another PPL (probably splnet)
- * Either specify an address, or a hook to traverse.
- * The return address can be specified, or it will be pointed at this node.
+ * Pick a node off the list of nodes with work,
+ * try get an item to process off it.
+ * If there are no more, remove the node from the list.
  */
-int
-ng_queue_msg(node_p here, struct ng_mesg *msg, const char *address, hook_p hook,char *retaddr)
+static void
+ngintr(void)
 {
-	register struct ng_queue_entry *q;
-	int     s;
-	node_p  dest = NULL;
-	int     error;
-	hook_p	lasthook = NULL;
-
-	/*
-	 * Find the target node.
-	 * If there is a HOOK argument, then use that in preference
-	 * to the address.
-	 */
-	if (hook) {
-		lasthook = hook->peer;
-		dest = lasthook->node;
-	} else {
-		error = ng_path2node(here, address, &dest, &lasthook);
-		if (error) {
-			FREE(msg, M_NETGRAPH);
-			return (error);
+	item_p item;
+	node_p  node = NULL;
+
+	for (;;) {
+		mtx_enter(&ng_worklist_mtx, MTX_SPIN);
+		node = TAILQ_FIRST(&ng_worklist);
+		if (!node) {
+			mtx_exit(&ng_worklist_mtx, MTX_SPIN);
+			break;
+		}
+		TAILQ_REMOVE(&ng_worklist, node, work);
+		mtx_exit(&ng_worklist_mtx, MTX_SPIN);
+		/*
+		 * We have the node. We also take over the reference
+		 * that the list had on it.
+		 * Now process as much as you can, until it won't
+		 * let you have another item off the queue.
+		 * All this time, keep the reference
+		 * that lets us be sure that the node still exists.
+		 * Let the reference go at the last minute.
+		 */
+		for (;;) {
+			mtx_enter(&node->input_queue.q_mtx, MTX_SPIN);
+			item = ng_dequeue(&node->input_queue);
+			if (item == NULL) {
+				/*
+				 * Say we are on the queue as long as
+				 * we are processing it here.
+				 * it probably wouldn't come here while we
+				 * are processing anyhow.
+				 */
+				node->flags &= ~NG_WORKQ;	
+				mtx_exit(&node->input_queue.q_mtx, MTX_SPIN);
+				ng_unref(node);
+				break; /* go look for another node */
+			} else {
+				mtx_exit(&node->input_queue.q_mtx, MTX_SPIN);
+#ifdef	ITEM_DEBUG
+        _ngi_check(item, __FILE__, __LINE__);
+#endif
+				ng_apply_item(node, item);
+			}
 		}
 	}
+}
+
+static void
+ng_worklist_remove(node_p node)
+{
+	mtx_enter(&ng_worklist_mtx, MTX_SPIN);
+	if (node->flags & NG_WORKQ) {
+		TAILQ_REMOVE(&ng_worklist, node, work);
+		ng_unref(node);
+	}
+	node->flags &= ~NG_WORKQ;
+	mtx_exit(&ng_worklist_mtx, MTX_SPIN);
+}
 
-	if (retaddr == NULL) {
+static void
+ng_setisr(node_p node)
+{
+	mtx_enter(&ng_worklist_mtx, MTX_SPIN);
+	if ((node->flags & NG_WORKQ) == 0) {
 		/*
-		 * Now fill out the return address,
-		 * i.e. the name/ID of the sender. (If we didn't get one)
+		 * If we are not already on the work queue,
+		 * then put us on.
 		 */
-		MALLOC(retaddr, char *, NG_NODELEN + 2, M_NETGRAPH, M_NOWAIT);
-		if (retaddr == NULL) {
-			TRAP_ERROR;
-			return (ENOMEM);
+		node->flags |= NG_WORKQ;
+		TAILQ_INSERT_TAIL(&ng_worklist, node, work);
+		node->refs++;
+	}
+	mtx_exit(&ng_worklist_mtx, MTX_SPIN);
+	schednetisr(NETISR_NETGRAPH);
+}
+
+
+/***********************************************************************
+* Externally useable functions to set up a queue item ready for sending
+***********************************************************************/
+
+#ifdef	ITEM_DEBUG
+#define	DEBUG_CHECKS							\
+	do {								\
+		if (item->el_dest ) {					\
+			printf("item already has node");		\
+			Debugger("has node");				\
+			ng_unref(item->el_dest);			\
+			item->el_dest = NULL;				\
+		}							\
+		if (item->el_hook ) {					\
+			printf("item already has hook");		\
+			Debugger("has hook");				\
+			ng_unref_hook(item->el_hook);			\
+			item->el_hook = NULL;				\
+		}							\
+	} while (0)
+#else
+#define DEBUG_CHECKS
+#endif
+
+/*
+ * Put elements into the item.
+ * Hook and node references will be removed when the item is dequeued.
+ * (or equivalent)
+ * (XXX) Unsafe because no reference held by peer on remote node.
+ * remote node might go away in this timescale.
+ * We know the hooks can't go away because that would require getting
+ * a writer item on both nodes and we must have at least a  reader
+ * here to eb able to do this.
+ * Note that the hook loaded is the REMOTE hook.
+ *
+ * This is possibly in the critical path for new data.
+ */
+item_p
+ng_package_data(struct mbuf *m, meta_p meta)
+{
+	item_p item;
+
+	if ((item = ng_getqblk()) == NULL) {
+		NG_FREE_M(m);
+		NG_FREE_META(meta);
+		return (NULL);
+	}
+	DEBUG_CHECKS;
+	item->el_flags = NGQF_DATA;
+	item->el_next = NULL;
+	NGI_M(item) = m;
+	NGI_META(item) = meta;
+	return (item);
+}
+
+/*
+ * Allocate a queue item and put items into it..
+ * Evaluate the address as this will be needed to queue it and
+ * to work out what some of the fields should be.
+ * Hook and node references will be removed when the item is dequeued.
+ * (or equivalent)
+ */
+item_p
+ng_package_msg(struct ng_mesg *msg)
+{
+	item_p item;
+
+	if ((item = ng_getqblk()) == NULL) {
+		if ((msg->header.flags & NGF_STATIC) == 0) {
+			NG_FREE_MSG(msg);
 		}
-		if (here->name != NULL)
-			sprintf(retaddr, "%s:", here->name);
-		else
-			sprintf(retaddr, "[%x]:", ng_node2ID(here));
+		return (NULL);
 	}
+	DEBUG_CHECKS;
+	item->el_flags = NGQF_MESG;
+	item->el_next = NULL;
+	/*
+	 * Set the current lasthook into the queue item
+	 */
+	NGI_MSG(item) = msg;
+	NGI_RETADDR(item) = NULL;
+	return (item);
+}
+
+
+
+#define SET_RETADDR							\
+	do {	/* Data items don't have retaddrs */			\
+		if ((item->el_flags & NGQF_D_M) == NGQF_MESG) {		\
+			if (retaddr) {					\
+				NGI_RETADDR(item) = retaddr;		\
+			} else {					\
+				/*					\
+				 * The old return address should be ok.	\
+				 * If there isn't one, use the address	\
+				 * here.				\
+				 */					\
+				if (NGI_RETADDR(item) == 0) {		\
+					NGI_RETADDR(item)		\
+						= ng_node2ID(here);	\
+				}					\
+			}						\
+		}							\
+	} while (0)
 
-	if ((q = ng_getqblk()) == NULL) {
-		FREE(msg, M_NETGRAPH);
-		if (retaddr)
-			FREE(retaddr, M_NETGRAPH);
-		return (ENOBUFS);
+int
+ng_address_hook(node_p here, item_p item, hook_p hook, ng_ID_t retaddr)
+{
+	DEBUG_CHECKS;
+	/*
+	 * Quick sanity check..
+	 */
+	if ((hook == NULL)
+	|| ((hook->flags & HK_INVALID) != 0)
+	|| (hook->peer == NULL)
+	|| ((hook->peer->flags & HK_INVALID) != 0)
+	|| ((hook->peer->node->flags & NG_INVALID) != 0)) {
+		NG_FREE_ITEM(item);
+		return (EINVAL);
 	}
 
-	/* Fill out the contents */
-	q->flags = NGQF_MESG;
-	q->next = NULL;
-	q->body.msg.msg_node = dest;
-	q->body.msg.msg_msg = msg;
-	q->body.msg.msg_retaddr = retaddr; /* XXX malloc'd, give it away */
-	q->body.msg.msg_lasthook = lasthook; /* XXX needs reference */
-	s = splhigh();		/* protect refs and queue */
-	dest->refs++;		/* don't let it go away while on the queue */
-	if (lasthook)
-		lasthook->refs++; /* same for the hook */
-
-	/* Put it on the queue */
-	if (ngqbase) {
-		ngqlast->next = q;
-	} else {
-		ngqbase = q;
+	/*
+	 * Transfer our interest to the other (peer) end.
+	 * note sleazy use of 'hook'.
+	 */
+	item->el_hook = hook->peer;
+	item->el_hook->refs++;	/* don't let it go away while on the queue */
+	item->el_dest = hook->peer->node; /* sleaze */
+	item->el_dest->refs++; /* XXX dangerous, not atomic */
+	SET_RETADDR;
+	return (0);
+}
+
+int
+ng_address_path(node_p here, item_p item, char *address, ng_ID_t retaddr) 
+{
+	node_p  dest = NULL;
+	hook_p	hook = NULL;
+	int     error;
+
+	DEBUG_CHECKS;
+	/*
+	 * Note that ng_path2noderef increments the reference count
+	 * on the node for us if it finds one. So we don't have to.
+	 */
+	error = ng_path2noderef(here, address, &dest, &hook);
+	if (error) {
+		NG_FREE_ITEM(item);
+		return (EINVAL);
 	}
-	ngqlast = q;
-	ngqsize++;
-	splx(s);
+	item->el_dest = dest;
+	if (( item->el_hook = hook))
+		hook->refs++;	/* don't let it go away while on the queue */
+	SET_RETADDR;
+	return (0);
+}
 
-	/* Schedule software interrupt to handle it later */
-	schednetisr(NETISR_NETGRAPH);
+int
+ng_address_ID(node_p here, item_p item, ng_ID_t ID, ng_ID_t retaddr)
+{
+	node_p dest;
+
+	DEBUG_CHECKS;
+	/*
+	 * Find the target node.
+	 */
+	dest = ng_ID2noderef(ID); /* GETS REFERENCE! */
+	if (dest == NULL) {
+		NG_FREE_ITEM(item);
+		return(EINVAL);
+	}
+	/* Fill out the contents */
+	item->el_flags = NGQF_MESG;
+	item->el_next = NULL;
+	item->el_dest = dest;
+	item->el_hook = NULL;
+	/* NGI_RETADDR(item) = ng_node2ID(here); not sure why its here XXX */
+	SET_RETADDR;
 	return (0);
 }
 
 /*
- * Pick an item off the queue, process it, and dispose of the queue entry.
- * Should be running at splnet.
+ * special case to send a message to self (e.g. destroy node)
+ * Possibly indicate an arrival hook too.
+ * Useful for removing that hook :-)
  */
-static void
-ngintr(void)
+item_p
+ng_package_msg_self(node_p here, hook_p hook, struct ng_mesg *msg)
 {
-	hook_p  hook;
-	struct ng_queue_entry *ngq;
-	struct mbuf *m;
-	meta_p  meta;
-	void   *retaddr;
-	struct ng_mesg *msg;
-	node_p  node;
-	int     error = 0;
-	int     s;
+	item_p item;
 
-	while (1) {
-		s = splhigh();
-		if ((ngq = ngqbase)) {
-			ngqbase = ngq->next;
-			ngqsize--;
-		}
-		splx(s);
-		if (ngq == NULL)
-			return;
-		switch (ngq->flags) {
-		case NGQF_DATA:
-			hook = ngq->body.data.da_hook;
-			m = ngq->body.data.da_m;
-			meta = ngq->body.data.da_meta;
-			RETURN_QBLK(ngq);
-			ng_send_data_dont_queue(hook, m, meta,
-				NULL, NULL, NULL);
-			m = NULL;
-			meta = NULL;
-			ng_unref_hook(hook);
-			break;
-		case NGQF_MESG:
-			node = ngq->body.msg.msg_node;
-			msg = ngq->body.msg.msg_msg;
-			retaddr = ngq->body.msg.msg_retaddr;
-			hook = ngq->body.msg.msg_lasthook;
-			RETURN_QBLK(ngq);
-			if (hook) {
-				if ((hook->flags & HK_INVALID) != 0) {
-				/* If the hook has been zapped
-					then we can't use it */
-					ng_unref_hook(hook);
-					hook = NULL;
-				}
-			}
-			/* similarly, if the node is a zombie.. */
-			if (node->flags & NG_INVALID) {
-				FREE(msg, M_NETGRAPH);
-			} else {
-				CALL_MSG_HANDLER(error, node, msg,
-						 retaddr, NULL, hook);
-			}
-			if (hook)
-				ng_unref_hook(hook);
-			ng_unref(node);
-			if (retaddr)
-				FREE(retaddr, M_NETGRAPH);
-			break;
-		default:
-			RETURN_QBLK(ngq);
+	/*
+	 * Find the target node.
+	 * If there is a HOOK argument, then use that in preference
+	 * to the address.
+	 */
+	if ((item = ng_getqblk()) == NULL) {
+		if ((msg->header.flags & NGF_STATIC) == 0) {
+			NG_FREE_MSG(msg);
 		}
+		return (NULL);
 	}
+
+	/* Fill out the contents */
+	item->el_flags = NGQF_MESG;
+	item->el_next = NULL;
+	item->el_dest = here;
+	here->refs++; /* XXX  not atomic, + May have other races */
+	item->el_hook = hook;
+	if (hook)
+		hook->refs++;
+	NGI_MSG(item) = msg;
+	NGI_RETADDR(item) = ng_node2ID(here);
+	return (item);
 }
 
+/*
+ * Set the address, if none given, give the node here.
+ */
+void
+ng_replace_retaddr(node_p here, item_p item, ng_ID_t retaddr)
+{
+	if (retaddr) {
+		NGI_RETADDR(item) = retaddr;
+	} else {
+		/*
+		 * The old return address should be ok.
+		 * If there isn't one, use the address here.
+		 */
+		NGI_RETADDR(item) = ng_node2ID(here);
+	}
+}
+
+#define TESTING
+#ifdef TESTING
+/* just test all the macros */
+void
+ng_macro_test(item_p item);
+void
+ng_macro_test(item_p item)
+{
+	node_p node = NULL;
+	hook_p hook = NULL;
+	struct mbuf *m;
+	meta_p meta;
+	struct ng_mesg *msg;
+	ng_ID_t retaddr;
+	int	error;
+
+	NGI_GET_M(item, m);
+	NGI_GET_META(item, meta);
+	NGI_GET_MSG(item, msg);
+	retaddr = NGI_RETADDR(item);
+	NG_SEND_DATA(error, hook, m, meta);
+	NG_SEND_DATA_ONLY(error, hook, m);
+	NG_FWD_NEW_DATA(error, item, hook, m);
+	NG_FWD_DATA(error, item, hook);
+	NG_SEND_MSG_HOOK(error, node, msg, hook, retaddr);
+	NG_SEND_MSG_ID(error, node, msg, retaddr, retaddr);
+	NG_SEND_MSG_PATH(error, node, msg, ".:", retaddr);
+	NG_QUEUE_MSG(error, node, msg, ".:", retaddr);
+	NG_FWD_MSG_HOOK(error, node, item, hook, retaddr);
+}
+#endif /* TESTING */