xref: /freebsd/sys/netgraph/ng_base.c (revision 6780ab54325a71e7e70112b11657973edde8655e)
1 /*
2  * ng_base.c
3  *
4  * Copyright (c) 1996-1999 Whistle Communications, Inc.
5  * All rights reserved.
6  *
7  * Subject to the following obligations and disclaimer of warranty, use and
8  * redistribution of this software, in source or object code forms, with or
9  * without modifications are expressly permitted by Whistle Communications;
10  * provided, however, that:
11  * 1. Any and all reproductions of the source or object code must include the
12  *    copyright notice above and the following disclaimer of warranties; and
13  * 2. No rights are granted, in any manner or form, to use Whistle
14  *    Communications, Inc. trademarks, including the mark "WHISTLE
15  *    COMMUNICATIONS" on advertising, endorsements, or otherwise except as
16  *    such appears in the above copyright notice or in the software.
17  *
18  * THIS SOFTWARE IS BEING PROVIDED BY WHISTLE COMMUNICATIONS "AS IS", AND
19  * TO THE MAXIMUM EXTENT PERMITTED BY LAW, WHISTLE COMMUNICATIONS MAKES NO
20  * REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED, REGARDING THIS SOFTWARE,
21  * INCLUDING WITHOUT LIMITATION, ANY AND ALL IMPLIED WARRANTIES OF
22  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, OR NON-INFRINGEMENT.
23  * WHISTLE COMMUNICATIONS DOES NOT WARRANT, GUARANTEE, OR MAKE ANY
24  * REPRESENTATIONS REGARDING THE USE OF, OR THE RESULTS OF THE USE OF THIS
25  * SOFTWARE IN TERMS OF ITS CORRECTNESS, ACCURACY, RELIABILITY OR OTHERWISE.
26  * IN NO EVENT SHALL WHISTLE COMMUNICATIONS BE LIABLE FOR ANY DAMAGES
27  * RESULTING FROM OR ARISING OUT OF ANY USE OF THIS SOFTWARE, INCLUDING
28  * WITHOUT LIMITATION, ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
29  * PUNITIVE, OR CONSEQUENTIAL DAMAGES, PROCUREMENT OF SUBSTITUTE GOODS OR
30  * SERVICES, LOSS OF USE, DATA OR PROFITS, HOWEVER CAUSED AND UNDER ANY
31  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
32  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
33  * THIS SOFTWARE, EVEN IF WHISTLE COMMUNICATIONS IS ADVISED OF THE POSSIBILITY
34  * OF SUCH DAMAGE.
35  *
36  * Authors: Julian Elischer <julian@freebsd.org>
37  *          Archie Cobbs <archie@freebsd.org>
38  *
39  * $FreeBSD$
40  * $Whistle: ng_base.c,v 1.39 1999/01/28 23:54:53 julian Exp $
41  */
42 
43 /*
44  * This file implements the base netgraph code.
45  */
46 
47 #include <sys/param.h>
48 #include <sys/systm.h>
49 #include <sys/errno.h>
50 #include <sys/kernel.h>
51 #include <sys/malloc.h>
52 #include <sys/syslog.h>
53 #include <sys/sysctl.h>
54 #include <sys/linker.h>
55 #include <sys/queue.h>
56 #include <sys/mbuf.h>
57 #include <sys/ctype.h>
58 #include <sys/sysctl.h>
59 #include <machine/limits.h>
60 
61 #include <net/netisr.h>
62 
63 #include <netgraph/ng_message.h>
64 #include <netgraph/netgraph.h>
65 #include <netgraph/ng_parse.h>
66 
67 MODULE_VERSION(netgraph, NG_ABI_VERSION);
68 
69 /* List of all active nodes */
70 static LIST_HEAD(, ng_node) ng_nodelist;
71 static struct mtx	ng_nodelist_mtx;
72 
73 #ifdef	NETGRAPH_DEBUG
74 
75 static SLIST_HEAD(, ng_node) ng_allnodes;
76 static LIST_HEAD(, ng_node) ng_freenodes; /* in debug, we never free() them */
77 static SLIST_HEAD(, ng_hook) ng_allhooks;
78 static LIST_HEAD(, ng_hook) ng_freehooks; /* in debug, we never free() them */
79 
80 static void ng_dumpitems(void);
81 static void ng_dumpnodes(void);
82 static void ng_dumphooks(void);
83 
84 #endif	/* NETGRAPH_DEBUG */
85 /*
86  * DEAD versions of the structures.
87  * In order to avoid races, it is sometimes neccesary to point
88  * at SOMETHING even though theoretically, the current entity is
89  * INVALID. Use these to avoid these races.
90  */
91 struct ng_type ng_deadtype = {
92 	NG_ABI_VERSION,
93 	"dead",
94 	NULL,	/* modevent */
95 	NULL,	/* constructor */
96 	NULL,	/* rcvmsg */
97 	NULL,	/* shutdown */
98 	NULL,	/* newhook */
99 	NULL,	/* findhook */
100 	NULL,	/* connect */
101 	NULL,	/* rcvdata */
102 	NULL,	/* disconnect */
103 	NULL, 	/* cmdlist */
104 };
105 
106 struct ng_node ng_deadnode = {
107 	"dead",
108 	&ng_deadtype,
109 	NG_INVALID,
110 	1,	/* refs */
111 	0,	/* numhooks */
112 	NULL,	/* private */
113 	0,	/* ID */
114 	LIST_HEAD_INITIALIZER(ng_deadnode.hooks),
115 	{},	/* all_nodes list entry */
116 	{},	/* id hashtable list entry */
117 	{},	/* workqueue entry */
118 	{	0,
119 		{}, /* should never use! (should hang) */
120 		NULL,
121 		&ng_deadnode.nd_input_queue.queue,
122 		&ng_deadnode
123 	},
124 #ifdef	NETGRAPH_DEBUG
125 	ND_MAGIC,
126 	__FILE__,
127 	__LINE__,
128 	{NULL}
129 #endif	/* NETGRAPH_DEBUG */
130 };
131 
132 struct ng_hook ng_deadhook = {
133 	"dead",
134 	NULL,		/* private */
135 	HK_INVALID | HK_DEAD,
136 	1,		/* refs always >= 1 */
137 	&ng_deadhook,	/* Peer is self */
138 	&ng_deadnode,	/* attached to deadnode */
139 	{},		/* hooks list */
140 	NULL,		/* override rcvmsg() */
141 	NULL,		/* override rcvdata() */
142 #ifdef	NETGRAPH_DEBUG
143 	HK_MAGIC,
144 	__FILE__,
145 	__LINE__,
146 	{NULL}
147 #endif	/* NETGRAPH_DEBUG */
148 };
149 
150 /*
151  * END DEAD STRUCTURES
152  */
153 /* List nodes with unallocated work */
154 static TAILQ_HEAD(, ng_node) ng_worklist = TAILQ_HEAD_INITIALIZER(ng_worklist);
155 static struct mtx	ng_worklist_mtx;   /* MUST LOCK NODE FIRST */
156 
157 /* List of installed types */
158 static LIST_HEAD(, ng_type) ng_typelist;
159 static struct mtx	ng_typelist_mtx;
160 
161 /* Hash related definitions */
162 /* XXX Don't need to initialise them because it's a LIST */
163 #define NG_ID_HASH_SIZE 32 /* most systems wont need even this many */
164 static LIST_HEAD(, ng_node) ng_ID_hash[NG_ID_HASH_SIZE];
165 static struct mtx	ng_idhash_mtx;
166 /* Method to find a node.. used twice so do it here */
167 #define NG_IDHASH_FN(ID) ((ID) % (NG_ID_HASH_SIZE))
168 #define NG_IDHASH_FIND(ID, node)					\
169 	do { 								\
170 		LIST_FOREACH(node, &ng_ID_hash[NG_IDHASH_FN(ID)],	\
171 						nd_idnodes) {		\
172 			if (NG_NODE_IS_VALID(node)			\
173 			&& (NG_NODE_ID(node) == ID)) {			\
174 				break;					\
175 			}						\
176 		}							\
177 	} while (0)
178 
179 /* Mutex that protects the free queue item list */
180 static volatile item_p		ngqfree;	/* free ones */
181 static struct mtx	ngq_mtx;
182 
183 /* Internal functions */
184 static int	ng_add_hook(node_p node, const char *name, hook_p * hookp);
185 static int	ng_generic_msg(node_p here, item_p item, hook_p lasthook);
186 static ng_ID_t	ng_decodeidname(const char *name);
187 static int	ngb_mod_event(module_t mod, int event, void *data);
188 static void	ng_worklist_remove(node_p node);
189 static void	ngintr(void);
190 static int	ng_apply_item(node_p node, item_p item);
191 static void	ng_flush_input_queue(struct ng_queue * ngq);
192 static void	ng_setisr(node_p node);
193 static node_p	ng_ID2noderef(ng_ID_t ID);
194 static int	ng_con_nodes(node_p node, const char *name, node_p node2,
195 							const char *name2);
196 static void	ng_con_part2(node_p node, hook_p hook, void *arg1, int arg2);
197 static void	ng_con_part3(node_p node, hook_p hook, void *arg1, int arg2);
198 static int	ng_mkpeer(node_p node, const char *name,
199 						const char *name2, char *type);
200 
201 /* imported , these used to be externally visible, some may go back */
202 int	ng_bypass(hook_p hook1, hook_p hook2);
203 void	ng_destroy_hook(hook_p hook);
204 node_p	ng_name2noderef(node_p node, const char *name);
205 int	ng_path2noderef(node_p here, const char *path,
206 	node_p *dest, hook_p *lasthook);
207 struct	ng_type *ng_findtype(const char *type);
208 int	ng_make_node(const char *type, node_p *nodepp);
209 int	ng_path_parse(char *addr, char **node, char **path, char **hook);
210 void	ng_rmnode(node_p node, hook_p dummy1, void *dummy2, int dummy3);
211 void	ng_unname(node_p node);
212 
213 
214 /* Our own netgraph malloc type */
215 MALLOC_DEFINE(M_NETGRAPH, "netgraph", "netgraph structures and ctrl messages");
216 MALLOC_DEFINE(M_NETGRAPH_HOOK, "netgraph_hook", "netgraph hook structures");
217 MALLOC_DEFINE(M_NETGRAPH_NODE, "netgraph_node", "netgraph node structures");
218 MALLOC_DEFINE(M_NETGRAPH_ITEM, "netgraph_item", "netgraph item structures");
219 MALLOC_DEFINE(M_NETGRAPH_META, "netgraph_meta", "netgraph name storage");
220 MALLOC_DEFINE(M_NETGRAPH_MSG, "netgraph_msg", "netgraph name storage");
221 
222 /* Should not be visible outside this file */
223 
224 #define _NG_ALLOC_HOOK(hook) \
225 	MALLOC(hook, hook_p, sizeof(*hook), M_NETGRAPH_HOOK, M_NOWAIT | M_ZERO)
226 #define _NG_ALLOC_NODE(node) \
227 	MALLOC(node, node_p, sizeof(*node), M_NETGRAPH_NODE, M_NOWAIT | M_ZERO)
228 
229 #ifdef NETGRAPH_DEBUG /*----------------------------------------------*/
230 /*
231  * In debug mode:
232  * In an attempt to help track reference count screwups
233  * we do not free objects back to the malloc system, but keep them
234  * in a local cache where we can examine them and keep information safely
235  * after they have been freed.
236  * We use this scheme for nodes and hooks, and to some extent for items.
237  */
238 static __inline hook_p
239 ng_alloc_hook(void)
240 {
241 	hook_p hook;
242 	SLIST_ENTRY(ng_hook) temp;
243 	mtx_lock(&ng_nodelist_mtx);
244 	hook = LIST_FIRST(&ng_freehooks);
245 	if (hook) {
246 		LIST_REMOVE(hook, hk_hooks);
247 		bcopy(&hook->hk_all, &temp, sizeof(temp));
248 		bzero(hook, sizeof(struct ng_hook));
249 		bcopy(&temp, &hook->hk_all, sizeof(temp));
250 		mtx_unlock(&ng_nodelist_mtx);
251 		hook->hk_magic = HK_MAGIC;
252 	} else {
253 		mtx_unlock(&ng_nodelist_mtx);
254 		_NG_ALLOC_HOOK(hook);
255 		if (hook) {
256 			hook->hk_magic = HK_MAGIC;
257 			mtx_lock(&ng_nodelist_mtx);
258 			SLIST_INSERT_HEAD(&ng_allhooks, hook, hk_all);
259 			mtx_unlock(&ng_nodelist_mtx);
260 		}
261 	}
262 	return (hook);
263 }
264 
265 static __inline node_p
266 ng_alloc_node(void)
267 {
268 	node_p node;
269 	SLIST_ENTRY(ng_node) temp;
270 	mtx_lock(&ng_nodelist_mtx);
271 	node = LIST_FIRST(&ng_freenodes);
272 	if (node) {
273 		LIST_REMOVE(node, nd_nodes);
274 		bcopy(&node->nd_all, &temp, sizeof(temp));
275 		bzero(node, sizeof(struct ng_node));
276 		bcopy(&temp, &node->nd_all, sizeof(temp));
277 		mtx_unlock(&ng_nodelist_mtx);
278 		node->nd_magic = ND_MAGIC;
279 	} else {
280 		mtx_unlock(&ng_nodelist_mtx);
281 		_NG_ALLOC_NODE(node);
282 		if (node) {
283 			node->nd_magic = ND_MAGIC;
284 			mtx_lock(&ng_nodelist_mtx);
285 			SLIST_INSERT_HEAD(&ng_allnodes, node, nd_all);
286 			mtx_unlock(&ng_nodelist_mtx);
287 		}
288 	}
289 	return (node);
290 }
291 
292 #define NG_ALLOC_HOOK(hook) do { (hook) = ng_alloc_hook(); } while (0)
293 #define NG_ALLOC_NODE(node) do { (node) = ng_alloc_node(); } while (0)
294 
295 
296 #define NG_FREE_HOOK(hook)						\
297 	do {								\
298 		mtx_lock(&ng_nodelist_mtx);			\
299 		LIST_INSERT_HEAD(&ng_freehooks, hook, hk_hooks);	\
300 		hook->hk_magic = 0;					\
301 		mtx_unlock(&ng_nodelist_mtx);			\
302 	} while (0)
303 
304 #define NG_FREE_NODE(node)						\
305 	do {								\
306 		mtx_lock(&ng_nodelist_mtx);			\
307 		LIST_INSERT_HEAD(&ng_freenodes, node, nd_nodes);	\
308 		node->nd_magic = 0;					\
309 		mtx_unlock(&ng_nodelist_mtx);			\
310 	} while (0)
311 
312 #else /* NETGRAPH_DEBUG */ /*----------------------------------------------*/
313 
314 #define NG_ALLOC_HOOK(hook) _NG_ALLOC_HOOK(hook)
315 #define NG_ALLOC_NODE(node) _NG_ALLOC_NODE(node)
316 
317 #define NG_FREE_HOOK(hook) do { FREE((hook), M_NETGRAPH_HOOK); } while (0)
318 #define NG_FREE_NODE(node) do { FREE((node), M_NETGRAPH_NODE); } while (0)
319 
320 #endif /* NETGRAPH_DEBUG */ /*----------------------------------------------*/
321 
322 /* Warning: Generally use NG_FREE_ITEM() instead */
323 #define NG_FREE_ITEM_REAL(item) do { FREE((item), M_NETGRAPH_ITEM); } while (0)
324 
325 
326 /* Set this to Debugger("X") to catch all errors as they occur */
327 #ifndef TRAP_ERROR
328 #define TRAP_ERROR()
329 #endif
330 
331 static	ng_ID_t nextID = 1;
332 
333 #ifdef INVARIANTS
334 #define CHECK_DATA_MBUF(m)	do {					\
335 		struct mbuf *n;						\
336 		int total;						\
337 									\
338 		if (((m)->m_flags & M_PKTHDR) == 0)			\
339 			panic("%s: !PKTHDR", __func__);		\
340 		for (total = 0, n = (m); n != NULL; n = n->m_next)	\
341 			total += n->m_len;				\
342 		if ((m)->m_pkthdr.len != total) {			\
343 			panic("%s: %d != %d",				\
344 			    __func__, (m)->m_pkthdr.len, total);	\
345 		}							\
346 	} while (0)
347 #else
348 #define CHECK_DATA_MBUF(m)
349 #endif
350 
351 
352 /************************************************************************
353 	Parse type definitions for generic messages
354 ************************************************************************/
355 
356 /* Handy structure parse type defining macro */
357 #define DEFINE_PARSE_STRUCT_TYPE(lo, up, args)				\
358 static const struct ng_parse_struct_field				\
359 	ng_ ## lo ## _type_fields[] = NG_GENERIC_ ## up ## _INFO args;	\
360 static const struct ng_parse_type ng_generic_ ## lo ## _type = {	\
361 	&ng_parse_struct_type,						\
362 	&ng_ ## lo ## _type_fields					\
363 }
364 
365 DEFINE_PARSE_STRUCT_TYPE(mkpeer, MKPEER, ());
366 DEFINE_PARSE_STRUCT_TYPE(connect, CONNECT, ());
367 DEFINE_PARSE_STRUCT_TYPE(name, NAME, ());
368 DEFINE_PARSE_STRUCT_TYPE(rmhook, RMHOOK, ());
369 DEFINE_PARSE_STRUCT_TYPE(nodeinfo, NODEINFO, ());
370 DEFINE_PARSE_STRUCT_TYPE(typeinfo, TYPEINFO, ());
371 DEFINE_PARSE_STRUCT_TYPE(linkinfo, LINKINFO, (&ng_generic_nodeinfo_type));
372 
373 /* Get length of an array when the length is stored as a 32 bit
374    value immediately preceding the array -- as with struct namelist
375    and struct typelist. */
376 static int
377 ng_generic_list_getLength(const struct ng_parse_type *type,
378 	const u_char *start, const u_char *buf)
379 {
380 	return *((const u_int32_t *)(buf - 4));
381 }
382 
383 /* Get length of the array of struct linkinfo inside a struct hooklist */
384 static int
385 ng_generic_linkinfo_getLength(const struct ng_parse_type *type,
386 	const u_char *start, const u_char *buf)
387 {
388 	const struct hooklist *hl = (const struct hooklist *)start;
389 
390 	return hl->nodeinfo.hooks;
391 }
392 
393 /* Array type for a variable length array of struct namelist */
394 static const struct ng_parse_array_info ng_nodeinfoarray_type_info = {
395 	&ng_generic_nodeinfo_type,
396 	&ng_generic_list_getLength
397 };
398 static const struct ng_parse_type ng_generic_nodeinfoarray_type = {
399 	&ng_parse_array_type,
400 	&ng_nodeinfoarray_type_info
401 };
402 
403 /* Array type for a variable length array of struct typelist */
404 static const struct ng_parse_array_info ng_typeinfoarray_type_info = {
405 	&ng_generic_typeinfo_type,
406 	&ng_generic_list_getLength
407 };
408 static const struct ng_parse_type ng_generic_typeinfoarray_type = {
409 	&ng_parse_array_type,
410 	&ng_typeinfoarray_type_info
411 };
412 
413 /* Array type for array of struct linkinfo in struct hooklist */
414 static const struct ng_parse_array_info ng_generic_linkinfo_array_type_info = {
415 	&ng_generic_linkinfo_type,
416 	&ng_generic_linkinfo_getLength
417 };
418 static const struct ng_parse_type ng_generic_linkinfo_array_type = {
419 	&ng_parse_array_type,
420 	&ng_generic_linkinfo_array_type_info
421 };
422 
423 DEFINE_PARSE_STRUCT_TYPE(typelist, TYPELIST, (&ng_generic_nodeinfoarray_type));
424 DEFINE_PARSE_STRUCT_TYPE(hooklist, HOOKLIST,
425 	(&ng_generic_nodeinfo_type, &ng_generic_linkinfo_array_type));
426 DEFINE_PARSE_STRUCT_TYPE(listnodes, LISTNODES,
427 	(&ng_generic_nodeinfoarray_type));
428 
429 /* List of commands and how to convert arguments to/from ASCII */
430 static const struct ng_cmdlist ng_generic_cmds[] = {
431 	{
432 	  NGM_GENERIC_COOKIE,
433 	  NGM_SHUTDOWN,
434 	  "shutdown",
435 	  NULL,
436 	  NULL
437 	},
438 	{
439 	  NGM_GENERIC_COOKIE,
440 	  NGM_MKPEER,
441 	  "mkpeer",
442 	  &ng_generic_mkpeer_type,
443 	  NULL
444 	},
445 	{
446 	  NGM_GENERIC_COOKIE,
447 	  NGM_CONNECT,
448 	  "connect",
449 	  &ng_generic_connect_type,
450 	  NULL
451 	},
452 	{
453 	  NGM_GENERIC_COOKIE,
454 	  NGM_NAME,
455 	  "name",
456 	  &ng_generic_name_type,
457 	  NULL
458 	},
459 	{
460 	  NGM_GENERIC_COOKIE,
461 	  NGM_RMHOOK,
462 	  "rmhook",
463 	  &ng_generic_rmhook_type,
464 	  NULL
465 	},
466 	{
467 	  NGM_GENERIC_COOKIE,
468 	  NGM_NODEINFO,
469 	  "nodeinfo",
470 	  NULL,
471 	  &ng_generic_nodeinfo_type
472 	},
473 	{
474 	  NGM_GENERIC_COOKIE,
475 	  NGM_LISTHOOKS,
476 	  "listhooks",
477 	  NULL,
478 	  &ng_generic_hooklist_type
479 	},
480 	{
481 	  NGM_GENERIC_COOKIE,
482 	  NGM_LISTNAMES,
483 	  "listnames",
484 	  NULL,
485 	  &ng_generic_listnodes_type	/* same as NGM_LISTNODES */
486 	},
487 	{
488 	  NGM_GENERIC_COOKIE,
489 	  NGM_LISTNODES,
490 	  "listnodes",
491 	  NULL,
492 	  &ng_generic_listnodes_type
493 	},
494 	{
495 	  NGM_GENERIC_COOKIE,
496 	  NGM_LISTTYPES,
497 	  "listtypes",
498 	  NULL,
499 	  &ng_generic_typeinfo_type
500 	},
501 	{
502 	  NGM_GENERIC_COOKIE,
503 	  NGM_TEXT_CONFIG,
504 	  "textconfig",
505 	  NULL,
506 	  &ng_parse_string_type
507 	},
508 	{
509 	  NGM_GENERIC_COOKIE,
510 	  NGM_TEXT_STATUS,
511 	  "textstatus",
512 	  NULL,
513 	  &ng_parse_string_type
514 	},
515 	{
516 	  NGM_GENERIC_COOKIE,
517 	  NGM_ASCII2BINARY,
518 	  "ascii2binary",
519 	  &ng_parse_ng_mesg_type,
520 	  &ng_parse_ng_mesg_type
521 	},
522 	{
523 	  NGM_GENERIC_COOKIE,
524 	  NGM_BINARY2ASCII,
525 	  "binary2ascii",
526 	  &ng_parse_ng_mesg_type,
527 	  &ng_parse_ng_mesg_type
528 	},
529 	{ 0 }
530 };
531 
532 /************************************************************************
533 			Node routines
534 ************************************************************************/
535 
536 /*
537  * Instantiate a node of the requested type
538  */
539 int
540 ng_make_node(const char *typename, node_p *nodepp)
541 {
542 	struct ng_type *type;
543 	int	error;
544 
545 	/* Check that the type makes sense */
546 	if (typename == NULL) {
547 		TRAP_ERROR();
548 		return (EINVAL);
549 	}
550 
551 	/* Locate the node type */
552 	if ((type = ng_findtype(typename)) == NULL) {
553 		char filename[NG_TYPELEN + 4];
554 		linker_file_t lf;
555 		int error;
556 
557 		/* Not found, try to load it as a loadable module */
558 		snprintf(filename, sizeof(filename), "ng_%s", typename);
559 		error = linker_load_module(NULL, filename, NULL, NULL, &lf);
560 		if (error != 0)
561 			return (error);
562 		lf->userrefs++;		/* pretend loaded by the syscall */
563 
564 		/* Try again, as now the type should have linked itself in */
565 		if ((type = ng_findtype(typename)) == NULL)
566 			return (ENXIO);
567 	}
568 
569 	/*
570 	 * If we have a constructor, then make the node and
571 	 * call the constructor to do type specific initialisation.
572 	 */
573 	if (type->constructor != NULL) {
574 		if ((error = ng_make_node_common(type, nodepp)) == 0) {
575 			if ((error = ((*type->constructor)(*nodepp)) != 0)) {
576 				NG_NODE_UNREF(*nodepp);
577 			}
578 		}
579 	} else {
580 		/*
581 		 * Node has no constructor. We cannot ask for one
582 		 * to be made. It must be brought into existance by
583 		 * some external agency. The external agency should
584 		 * call ng_make_node_common() directly to get the
585 		 * netgraph part initialised.
586 		 */
587 		TRAP_ERROR();
588 		error = EINVAL;
589 	}
590 	return (error);
591 }
592 
593 /*
594  * Generic node creation. Called by node initialisation for externally
595  * instantiated nodes (e.g. hardware, sockets, etc ).
596  * The returned node has a reference count of 1.
597  */
598 int
599 ng_make_node_common(struct ng_type *type, node_p *nodepp)
600 {
601 	node_p node;
602 
603 	/* Require the node type to have been already installed */
604 	if (ng_findtype(type->name) == NULL) {
605 		TRAP_ERROR();
606 		return (EINVAL);
607 	}
608 
609 	/* Make a node and try attach it to the type */
610 	NG_ALLOC_NODE(node);
611 	if (node == NULL) {
612 		TRAP_ERROR();
613 		return (ENOMEM);
614 	}
615 	node->nd_type = type;
616 	NG_NODE_REF(node);				/* note reference */
617 	type->refs++;
618 
619 	mtx_init(&node->nd_input_queue.q_mtx, "ng_node", NULL, MTX_SPIN);
620 	node->nd_input_queue.queue = NULL;
621 	node->nd_input_queue.last = &node->nd_input_queue.queue;
622 	node->nd_input_queue.q_flags = 0;
623 	node->nd_input_queue.q_node = node;
624 
625 	/* Initialize hook list for new node */
626 	LIST_INIT(&node->nd_hooks);
627 
628 	/* Link us into the node linked list */
629 	mtx_lock(&ng_nodelist_mtx);
630 	LIST_INSERT_HEAD(&ng_nodelist, node, nd_nodes);
631 	mtx_unlock(&ng_nodelist_mtx);
632 
633 
634 	/* get an ID and put us in the hash chain */
635 	mtx_lock(&ng_idhash_mtx);
636 	for (;;) { /* wrap protection, even if silly */
637 		node_p node2 = NULL;
638 		node->nd_ID = nextID++; /* 137/second for 1 year before wrap */
639 
640 		/* Is there a problem with the new number? */
641 		NG_IDHASH_FIND(node->nd_ID, node2); /* already taken? */
642 		if ((node->nd_ID != 0) && (node2 == NULL)) {
643 			break;
644 		}
645 	}
646 	LIST_INSERT_HEAD(&ng_ID_hash[NG_IDHASH_FN(node->nd_ID)],
647 							node, nd_idnodes);
648 	mtx_unlock(&ng_idhash_mtx);
649 
650 	/* Done */
651 	*nodepp = node;
652 	return (0);
653 }
654 
655 /*
656  * Forceably start the shutdown process on a node. Either call
657  * it's shutdown method, or do the default shutdown if there is
658  * no type-specific method.
659  *
660  * We can only be called form a shutdown message, so we know we have
661  * a writer lock, and therefore exclusive access. It also means
662  * that we should not be on the work queue, but we check anyhow.
663  *
664  * Persistent node types must have a type-specific method which
665  * Allocates a new node in which case, this one is irretrievably going away,
666  * or cleans up anything it needs, and just makes the node valid again,
667  * in which case we allow the node to survive.
668  *
669  * XXX We need to think of how to tell a persistant node that we
670  * REALLY need to go away because the hardware has gone or we
671  * are rebooting.... etc.
672  */
673 void
674 ng_rmnode(node_p node, hook_p dummy1, void *dummy2, int dummy3)
675 {
676 	hook_p hook;
677 
678 	/* Check if it's already shutting down */
679 	if ((node->nd_flags & NG_CLOSING) != 0)
680 		return;
681 
682 	if (node == &ng_deadnode) {
683 		printf ("shutdown called on deadnode\n");
684 		return;
685 	}
686 
687 	/* Add an extra reference so it doesn't go away during this */
688 	NG_NODE_REF(node);
689 
690 	/*
691 	 * Mark it invalid so any newcomers know not to try use it
692 	 * Also add our own mark so we can't recurse
693 	 * note that NG_INVALID does not do this as it's also set during
694 	 * creation
695 	 */
696 	node->nd_flags |= NG_INVALID|NG_CLOSING;
697 
698 	/* Notify all remaining connected nodes to disconnect */
699 	while ((hook = LIST_FIRST(&node->nd_hooks)) != NULL)
700 		ng_destroy_hook(hook);
701 
702 	/*
703 	 * Drain the input queue forceably.
704 	 * it has no hooks so what's it going to do, bleed on someone?
705 	 * Theoretically we came here from a queue entry that was added
706 	 * Just before the queue was closed, so it should be empty anyway.
707 	 * Also removes us from worklist if needed.
708 	 */
709 	ng_flush_input_queue(&node->nd_input_queue);
710 
711 	/* Ask the type if it has anything to do in this case */
712 	if (node->nd_type && node->nd_type->shutdown) {
713 		(*node->nd_type->shutdown)(node);
714 		if (NG_NODE_IS_VALID(node)) {
715 			/*
716 			 * Well, blow me down if the node code hasn't declared
717 			 * that it doesn't want to die.
718 			 * Presumably it is a persistant node.
719 			 * If we REALLY want it to go away,
720 			 *  e.g. hardware going away,
721 			 * Our caller should set NG_REALLY_DIE in nd_flags.
722 			 */
723 			node->nd_flags &= ~(NG_INVALID|NG_CLOSING);
724 			NG_NODE_UNREF(node); /* Assume they still have theirs */
725 			return;
726 		}
727 	} else {				/* do the default thing */
728 		NG_NODE_UNREF(node);
729 	}
730 
731 	ng_unname(node); /* basically a NOP these days */
732 
733 	/*
734 	 * Remove extra reference, possibly the last
735 	 * Possible other holders of references may include
736 	 * timeout callouts, but theoretically the node's supposed to
737 	 * have cancelled them. Possibly hardware dependencies may
738 	 * force a driver to 'linger' with a reference.
739 	 */
740 	NG_NODE_UNREF(node);
741 }
742 
743 #ifdef	NETGRAPH_DEBUG
744 void
745 ng_ref_node(node_p node)
746 {
747 	_NG_NODE_REF(node);
748 }
749 #endif
750 
751 /*
752  * Remove a reference to the node, possibly the last.
753  * deadnode always acts as it it were the last.
754  */
755 int
756 ng_unref_node(node_p node)
757 {
758 	int     v;
759 
760 	if (node == &ng_deadnode) {
761 		return (0);
762 	}
763 
764 	do {
765 		v = node->nd_refs - 1;
766 	} while (! atomic_cmpset_int(&node->nd_refs, v + 1, v));
767 
768 	if (v == 0) { /* we were the last */
769 
770 		mtx_lock(&ng_nodelist_mtx);
771 		node->nd_type->refs--; /* XXX maybe should get types lock? */
772 		LIST_REMOVE(node, nd_nodes);
773 		mtx_unlock(&ng_nodelist_mtx);
774 
775 		mtx_lock(&ng_idhash_mtx);
776 		LIST_REMOVE(node, nd_idnodes);
777 		mtx_unlock(&ng_idhash_mtx);
778 
779 		mtx_destroy(&node->nd_input_queue.q_mtx);
780 		NG_FREE_NODE(node);
781 	}
782 	return (v);
783 }
784 
785 /************************************************************************
786 			Node ID handling
787 ************************************************************************/
788 static node_p
789 ng_ID2noderef(ng_ID_t ID)
790 {
791 	node_p node;
792 	mtx_lock(&ng_idhash_mtx);
793 	NG_IDHASH_FIND(ID, node);
794 	if(node)
795 		NG_NODE_REF(node);
796 	mtx_unlock(&ng_idhash_mtx);
797 	return(node);
798 }
799 
800 ng_ID_t
801 ng_node2ID(node_p node)
802 {
803 	return (node ? NG_NODE_ID(node) : 0);
804 }
805 
806 /************************************************************************
807 			Node name handling
808 ************************************************************************/
809 
810 /*
811  * Assign a node a name. Once assigned, the name cannot be changed.
812  */
813 int
814 ng_name_node(node_p node, const char *name)
815 {
816 	int i;
817 	node_p node2;
818 
819 	/* Check the name is valid */
820 	for (i = 0; i < NG_NODELEN + 1; i++) {
821 		if (name[i] == '\0' || name[i] == '.' || name[i] == ':')
822 			break;
823 	}
824 	if (i == 0 || name[i] != '\0') {
825 		TRAP_ERROR();
826 		return (EINVAL);
827 	}
828 	if (ng_decodeidname(name) != 0) { /* valid IDs not allowed here */
829 		TRAP_ERROR();
830 		return (EINVAL);
831 	}
832 
833 	/* Check the name isn't already being used */
834 	if ((node2 = ng_name2noderef(node, name)) != NULL) {
835 		NG_NODE_UNREF(node2);
836 		TRAP_ERROR();
837 		return (EADDRINUSE);
838 	}
839 
840 	/* copy it */
841 	strncpy(NG_NODE_NAME(node), name, NG_NODELEN);
842 
843 	return (0);
844 }
845 
846 /*
847  * Find a node by absolute name. The name should NOT end with ':'
848  * The name "." means "this node" and "[xxx]" means "the node
849  * with ID (ie, at address) xxx".
850  *
851  * Returns the node if found, else NULL.
852  * Eventually should add something faster than a sequential search.
853  * Note it aquires a reference on the node so you can be sure it's still there.
854  */
855 node_p
856 ng_name2noderef(node_p here, const char *name)
857 {
858 	node_p node;
859 	ng_ID_t temp;
860 
861 	/* "." means "this node" */
862 	if (strcmp(name, ".") == 0) {
863 		NG_NODE_REF(here);
864 		return(here);
865 	}
866 
867 	/* Check for name-by-ID */
868 	if ((temp = ng_decodeidname(name)) != 0) {
869 		return (ng_ID2noderef(temp));
870 	}
871 
872 	/* Find node by name */
873 	mtx_lock(&ng_nodelist_mtx);
874 	LIST_FOREACH(node, &ng_nodelist, nd_nodes) {
875 		if (NG_NODE_IS_VALID(node)
876 		&& NG_NODE_HAS_NAME(node)
877 		&& (strcmp(NG_NODE_NAME(node), name) == 0)) {
878 			break;
879 		}
880 	}
881 	if (node)
882 		NG_NODE_REF(node);
883 	mtx_unlock(&ng_nodelist_mtx);
884 	return (node);
885 }
886 
887 /*
888  * Decode an ID name, eg. "[f03034de]". Returns 0 if the
889  * string is not valid, otherwise returns the value.
890  */
891 static ng_ID_t
892 ng_decodeidname(const char *name)
893 {
894 	const int len = strlen(name);
895 	char *eptr;
896 	u_long val;
897 
898 	/* Check for proper length, brackets, no leading junk */
899 	if ((len < 3)
900 	|| (name[0] != '[')
901 	|| (name[len - 1] != ']')
902 	|| (!isxdigit(name[1]))) {
903 		return ((ng_ID_t)0);
904 	}
905 
906 	/* Decode number */
907 	val = strtoul(name + 1, &eptr, 16);
908 	if ((eptr - name != len - 1)
909 	|| (val == ULONG_MAX)
910 	|| (val == 0)) {
911 		return ((ng_ID_t)0);
912 	}
913 	return (ng_ID_t)val;
914 }
915 
916 /*
917  * Remove a name from a node. This should only be called
918  * when shutting down and removing the node.
919  * IF we allow name changing this may be more resurected.
920  */
921 void
922 ng_unname(node_p node)
923 {
924 }
925 
926 /************************************************************************
927 			Hook routines
928  Names are not optional. Hooks are always connected, except for a
929  brief moment within these routines. On invalidation or during creation
930  they are connected to the 'dead' hook.
931 ************************************************************************/
932 
933 /*
934  * Remove a hook reference
935  */
936 void
937 ng_unref_hook(hook_p hook)
938 {
939 	int     v;
940 
941 	if (hook == &ng_deadhook) {
942 		return;
943 	}
944 	do {
945 		v = hook->hk_refs;
946 	} while (! atomic_cmpset_int(&hook->hk_refs, v, v - 1));
947 
948 	if (v == 1) { /* we were the last */
949 		if (_NG_HOOK_NODE(hook)) { /* it'll probably be ng_deadnode */
950 			_NG_NODE_UNREF((_NG_HOOK_NODE(hook)));
951 			hook->hk_node = NULL;
952 		}
953 		NG_FREE_HOOK(hook);
954 	}
955 }
956 
957 /*
958  * Add an unconnected hook to a node. Only used internally.
959  * Assumes node is locked. (XXX not yet true )
960  */
961 static int
962 ng_add_hook(node_p node, const char *name, hook_p *hookp)
963 {
964 	hook_p hook;
965 	int error = 0;
966 
967 	/* Check that the given name is good */
968 	if (name == NULL) {
969 		TRAP_ERROR();
970 		return (EINVAL);
971 	}
972 	if (ng_findhook(node, name) != NULL) {
973 		TRAP_ERROR();
974 		return (EEXIST);
975 	}
976 
977 	/* Allocate the hook and link it up */
978 	NG_ALLOC_HOOK(hook);
979 	if (hook == NULL) {
980 		TRAP_ERROR();
981 		return (ENOMEM);
982 	}
983 	hook->hk_refs = 1;		/* add a reference for us to return */
984 	hook->hk_flags = HK_INVALID;
985 	hook->hk_peer = &ng_deadhook;	/* start off this way */
986 	hook->hk_node = node;
987 	NG_NODE_REF(node);		/* each hook counts as a reference */
988 
989 	/* Set hook name */
990 	strncpy(NG_HOOK_NAME(hook), name, NG_HOOKLEN);
991 
992 	/*
993 	 * Check if the node type code has something to say about it
994 	 * If it fails, the unref of the hook will also unref the node.
995 	 */
996 	if (node->nd_type->newhook != NULL) {
997 		if ((error = (*node->nd_type->newhook)(node, hook, name))) {
998 			NG_HOOK_UNREF(hook);	/* this frees the hook */
999 			return (error);
1000 		}
1001 	}
1002 	/*
1003 	 * The 'type' agrees so far, so go ahead and link it in.
1004 	 * We'll ask again later when we actually connect the hooks.
1005 	 */
1006 	LIST_INSERT_HEAD(&node->nd_hooks, hook, hk_hooks);
1007 	node->nd_numhooks++;
1008 	NG_HOOK_REF(hook);	/* one for the node */
1009 
1010 	if (hookp)
1011 		*hookp = hook;
1012 	return (0);
1013 }
1014 
1015 /*
1016  * Find a hook
1017  *
1018  * Node types may supply their own optimized routines for finding
1019  * hooks.  If none is supplied, we just do a linear search.
1020  * XXX Possibly we should add a reference to the hook?
1021  */
1022 hook_p
1023 ng_findhook(node_p node, const char *name)
1024 {
1025 	hook_p hook;
1026 
1027 	if (node->nd_type->findhook != NULL)
1028 		return (*node->nd_type->findhook)(node, name);
1029 	LIST_FOREACH(hook, &node->nd_hooks, hk_hooks) {
1030 		if (NG_HOOK_IS_VALID(hook)
1031 		&& (strcmp(NG_HOOK_NAME(hook), name) == 0))
1032 			return (hook);
1033 	}
1034 	return (NULL);
1035 }
1036 
1037 /*
1038  * Destroy a hook
1039  *
1040  * As hooks are always attached, this really destroys two hooks.
1041  * The one given, and the one attached to it. Disconnect the hooks
1042  * from each other first. We reconnect the peer hook to the 'dead'
1043  * hook so that it can still exist after we depart. We then
1044  * send the peer its own destroy message. This ensures that we only
1045  * interact with the peer's structures when it is locked processing that
1046  * message. We hold a reference to the peer hook so we are guaranteed that
1047  * the peer hook and node are still going to exist until
1048  * we are finished there as the hook holds a ref on the node.
1049  * We run this same code again on the peer hook, but that time it is already
1050  * attached to the 'dead' hook.
1051  *
1052  * This routine is called at all stages of hook creation
1053  * on error detection and must be able to handle any such stage.
1054  */
1055 void
1056 ng_destroy_hook(hook_p hook)
1057 {
1058 	hook_p peer = NG_HOOK_PEER(hook);
1059 	node_p node = NG_HOOK_NODE(hook);
1060 
1061 	if (hook == &ng_deadhook) {	/* better safe than sorry */
1062 		printf("ng_destroy_hook called on deadhook\n");
1063 		return;
1064 	}
1065 	hook->hk_flags |= HK_INVALID;		/* as soon as possible */
1066 	if (peer && (peer != &ng_deadhook)) {
1067 		/*
1068 		 * Set the peer to point to ng_deadhook
1069 		 * from this moment on we are effectively independent it.
1070 		 * send it an rmhook message of it's own.
1071 		 */
1072 		peer->hk_peer = &ng_deadhook;	/* They no longer know us */
1073 		hook->hk_peer = &ng_deadhook;	/* Nor us, them */
1074 		if (NG_HOOK_NODE(peer) == &ng_deadnode) {
1075 			/*
1076 			 * If it's already divorced from a node,
1077 			 * just free it.
1078 			 */
1079 			/* nothing */
1080 		} else {
1081 			ng_rmhook_self(peer); 	/* Send it a surprise */
1082 		}
1083 		NG_HOOK_UNREF(peer);		/* account for peer link */
1084 		NG_HOOK_UNREF(hook);		/* account for peer link */
1085 	}
1086 
1087 	/*
1088 	 * Remove the hook from the node's list to avoid possible recursion
1089 	 * in case the disconnection results in node shutdown.
1090 	 */
1091 	if (node == &ng_deadnode) { /* happens if called from ng_con_nodes() */
1092 		return;
1093 	}
1094 	LIST_REMOVE(hook, hk_hooks);
1095 	node->nd_numhooks--;
1096 	if (node->nd_type->disconnect) {
1097 		/*
1098 		 * The type handler may elect to destroy the node so don't
1099 		 * trust its existance after this point. (except
1100 		 * that we still hold a reference on it. (which we
1101 		 * inherrited from the hook we are destroying)
1102 		 */
1103 		(*node->nd_type->disconnect) (hook);
1104 	}
1105 
1106 	/*
1107 	 * Note that because we will point to ng_deadnode, the original node
1108 	 * is not decremented automatically so we do that manually.
1109 	 */
1110 	_NG_HOOK_NODE(hook) = &ng_deadnode;
1111 	NG_NODE_UNREF(node);	/* We no longer point to it so adjust count */
1112 	NG_HOOK_UNREF(hook);	/* Account for linkage (in list) to node */
1113 }
1114 
1115 /*
1116  * Take two hooks on a node and merge the connection so that the given node
1117  * is effectively bypassed.
1118  */
1119 int
1120 ng_bypass(hook_p hook1, hook_p hook2)
1121 {
1122 	if (hook1->hk_node != hook2->hk_node) {
1123 		TRAP_ERROR();
1124 		return (EINVAL);
1125 	}
1126 	hook1->hk_peer->hk_peer = hook2->hk_peer;
1127 	hook2->hk_peer->hk_peer = hook1->hk_peer;
1128 
1129 	hook1->hk_peer = &ng_deadhook;
1130 	hook2->hk_peer = &ng_deadhook;
1131 
1132 	/* XXX If we ever cache methods on hooks update them as well */
1133 	ng_destroy_hook(hook1);
1134 	ng_destroy_hook(hook2);
1135 	return (0);
1136 }
1137 
1138 /*
1139  * Install a new netgraph type
1140  */
1141 int
1142 ng_newtype(struct ng_type *tp)
1143 {
1144 	const size_t namelen = strlen(tp->name);
1145 
1146 	/* Check version and type name fields */
1147 	if ((tp->version != NG_ABI_VERSION)
1148 	|| (namelen == 0)
1149 	|| (namelen > NG_TYPELEN)) {
1150 		TRAP_ERROR();
1151 		return (EINVAL);
1152 	}
1153 
1154 	/* Check for name collision */
1155 	if (ng_findtype(tp->name) != NULL) {
1156 		TRAP_ERROR();
1157 		return (EEXIST);
1158 	}
1159 
1160 
1161 	/* Link in new type */
1162 	mtx_lock(&ng_typelist_mtx);
1163 	LIST_INSERT_HEAD(&ng_typelist, tp, types);
1164 	tp->refs = 1;	/* first ref is linked list */
1165 	mtx_unlock(&ng_typelist_mtx);
1166 	return (0);
1167 }
1168 
1169 /*
1170  * unlink a netgraph type
1171  * If no examples exist
1172  */
1173 int
1174 ng_rmtype(struct ng_type *tp)
1175 {
1176 	/* Check for name collision */
1177 	if (tp->refs != 1) {
1178 		TRAP_ERROR();
1179 		return (EBUSY);
1180 	}
1181 
1182 	/* Unlink type */
1183 	mtx_lock(&ng_typelist_mtx);
1184 	LIST_REMOVE(tp, types);
1185 	mtx_unlock(&ng_typelist_mtx);
1186 	return (0);
1187 }
1188 
1189 /*
1190  * Look for a type of the name given
1191  */
1192 struct ng_type *
1193 ng_findtype(const char *typename)
1194 {
1195 	struct ng_type *type;
1196 
1197 	mtx_lock(&ng_typelist_mtx);
1198 	LIST_FOREACH(type, &ng_typelist, types) {
1199 		if (strcmp(type->name, typename) == 0)
1200 			break;
1201 	}
1202 	mtx_unlock(&ng_typelist_mtx);
1203 	return (type);
1204 }
1205 
1206 /************************************************************************
1207 			Composite routines
1208 ************************************************************************/
1209 /*
1210  * Connect two nodes using the specified hooks, using queued functions.
1211  */
1212 static void
1213 ng_con_part3(node_p node, hook_p hook, void *arg1, int arg2)
1214 {
1215 
1216 	/*
1217 	 * When we run, we know that the node 'node' is locked for us.
1218 	 * Our caller has a reference on the hook.
1219 	 * Our caller has a reference on the node.
1220 	 * (In this case our caller is ng_apply_item() ).
1221 	 * The peer hook has a reference on the hook.
1222 	 * We are all set up except for the final call to the node, and
1223 	 * the clearing of the INVALID flag.
1224 	 */
1225 	if (NG_HOOK_NODE(hook) == &ng_deadnode) {
1226 		/*
1227 		 * The node must have been freed again since we last visited
1228 		 * here. ng_destry_hook() has this effect but nothing else does.
1229 		 * We should just release our references and
1230 		 * free anything we can think of.
1231 		 * Since we know it's been destroyed, and it's our caller
1232 		 * that holds the references, just return.
1233 		 */
1234 		return ;
1235 	}
1236 	if (hook->hk_node->nd_type->connect) {
1237 		if ((*hook->hk_node->nd_type->connect) (hook)) {
1238 			ng_destroy_hook(hook);	/* also zaps peer */
1239 			printf("failed in ng_con_part3()\n");
1240 			return ;
1241 		}
1242 	}
1243 	/*
1244 	 *  XXX this is wrong for SMP. Possibly we need
1245 	 * to separate out 'create' and 'invalid' flags.
1246 	 * should only set flags on hooks we have locked under our node.
1247 	 */
1248 	hook->hk_flags &= ~HK_INVALID;
1249 	return ;
1250 }
1251 
1252 static void
1253 ng_con_part2(node_p node, hook_p hook, void *arg1, int arg2)
1254 {
1255 
1256 	/*
1257 	 * When we run, we know that the node 'node' is locked for us.
1258 	 * Our caller has a reference on the hook.
1259 	 * Our caller has a reference on the node.
1260 	 * (In this case our caller is ng_apply_item() ).
1261 	 * The peer hook has a reference on the hook.
1262 	 * our node pointer points to the 'dead' node.
1263 	 * First check the hook name is unique.
1264 	 * Should not happen because we checked before queueing this.
1265 	 */
1266 	if (ng_findhook(node, NG_HOOK_NAME(hook)) != NULL) {
1267 		TRAP_ERROR();
1268 		ng_destroy_hook(hook); /* should destroy peer too */
1269 		printf("failed in ng_con_part2()\n");
1270 		return ;
1271 	}
1272 	/*
1273 	 * Check if the node type code has something to say about it
1274 	 * If it fails, the unref of the hook will also unref the attached node,
1275 	 * however since that node is 'ng_deadnode' this will do nothing.
1276 	 * The peer hook will also be destroyed.
1277 	 */
1278 	if (node->nd_type->newhook != NULL) {
1279 		if ((*node->nd_type->newhook)(node, hook, hook->hk_name)) {
1280 			ng_destroy_hook(hook); /* should destroy peer too */
1281 			printf("failed in ng_con_part2()\n");
1282 			return ;
1283 		}
1284 	}
1285 
1286 	/*
1287 	 * The 'type' agrees so far, so go ahead and link it in.
1288 	 * We'll ask again later when we actually connect the hooks.
1289 	 */
1290 	hook->hk_node = node;		/* just overwrite ng_deadnode */
1291 	NG_NODE_REF(node);		/* each hook counts as a reference */
1292 	LIST_INSERT_HEAD(&node->nd_hooks, hook, hk_hooks);
1293 	node->nd_numhooks++;
1294 	NG_HOOK_REF(hook);	/* one for the node */
1295 
1296 	/*
1297 	 * We now have a symetrical situation, where both hooks have been
1298 	 * linked to their nodes, the newhook methods have been called
1299 	 * And the references are all correct. The hooks are still marked
1300 	 * as invalid, as we have not called the 'connect' methods
1301 	 * yet.
1302 	 * We can call the local one immediatly as we have the
1303 	 * node locked, but we need to queue the remote one.
1304 	 */
1305 	if (hook->hk_node->nd_type->connect) {
1306 		if ((*hook->hk_node->nd_type->connect) (hook)) {
1307 			ng_destroy_hook(hook);	/* also zaps peer */
1308 			printf("failed in ng_con_part2(A)\n");
1309 			return ;
1310 		}
1311 	}
1312 	if (ng_send_fn(hook->hk_peer->hk_node, hook->hk_peer,
1313 			&ng_con_part3, arg1, arg2)) {
1314 		printf("failed in ng_con_part2(B)");
1315 		ng_destroy_hook(hook);	/* also zaps peer */
1316 		return ;
1317 	}
1318 	hook->hk_flags &= ~HK_INVALID; /* need both to be able to work */
1319 	return ;
1320 }
1321 
1322 /*
1323  * Connect this node with another node. We assume that this node is
1324  * currently locked, as we are only called from an NGM_CONNECT message.
1325  */
1326 static int
1327 ng_con_nodes(node_p node, const char *name, node_p node2, const char *name2)
1328 {
1329 	int     error;
1330 	hook_p  hook;
1331 	hook_p  hook2;
1332 
1333 	if (ng_findhook(node2, name2) != NULL) {
1334 		return(EEXIST);
1335 	}
1336 	if ((error = ng_add_hook(node, name, &hook)))  /* gives us a ref */
1337 		return (error);
1338 	/* Allocate the other hook and link it up */
1339 	NG_ALLOC_HOOK(hook2);
1340 	if (hook == NULL) {
1341 		TRAP_ERROR();
1342 		ng_destroy_hook(hook);	/* XXX check ref counts so far */
1343 		NG_HOOK_UNREF(hook);	/* including our ref */
1344 		return (ENOMEM);
1345 	}
1346 	hook2->hk_refs = 1;		/* start with a reference for us. */
1347 	hook2->hk_flags = HK_INVALID;
1348 	hook2->hk_peer = hook;		/* Link the two together */
1349 	hook->hk_peer = hook2;
1350 	NG_HOOK_REF(hook);		/* Add a ref for the peer to each*/
1351 	NG_HOOK_REF(hook2);
1352 	hook2->hk_node = &ng_deadnode;
1353 	strncpy(NG_HOOK_NAME(hook2), name2, NG_HOOKLEN);
1354 
1355 	/*
1356 	 * Queue the function above.
1357 	 * Procesing continues in that function in the lock context of
1358 	 * the other node.
1359 	 */
1360 	ng_send_fn(node2, hook2, &ng_con_part2, NULL, 0);
1361 
1362 	NG_HOOK_UNREF(hook);		/* Let each hook go if it wants to */
1363 	NG_HOOK_UNREF(hook2);
1364 	return (0);
1365 }
1366 
1367 /*
1368  * Make a peer and connect.
1369  * We assume that the local node is locked.
1370  * The new node probably doesn't need a lock until
1371  * it has a hook, because it cannot really have any work until then,
1372  * but we should think about it a bit more.
1373  *
1374  * The problem may come if the other node also fires up
1375  * some hardware or a timer or some other source of activation,
1376  * also it may already get a command msg via it's ID.
1377  *
1378  * We could use the same method as ng_con_nodes() but we'd have
1379  * to add ability to remove the node when failing. (Not hard, just
1380  * make arg1 point to the node to remove).
1381  * Unless of course we just ignore failure to connect and leave
1382  * an unconnected node?
1383  */
1384 static int
1385 ng_mkpeer(node_p node, const char *name, const char *name2, char *type)
1386 {
1387 	node_p  node2;
1388 	hook_p  hook1;
1389 	hook_p  hook2;
1390 	int     error;
1391 
1392 	if ((error = ng_make_node(type, &node2))) {
1393 		return (error);
1394 	}
1395 
1396 	if ((error = ng_add_hook(node, name, &hook1))) { /* gives us a ref */
1397 		ng_rmnode(node2, NULL, NULL, 0);
1398 		return (error);
1399 	}
1400 
1401 	if ((error = ng_add_hook(node2, name2, &hook2))) {
1402 		ng_rmnode(node2, NULL, NULL, 0);
1403 		ng_destroy_hook(hook1);
1404 		NG_HOOK_UNREF(hook1);
1405 		return (error);
1406 	}
1407 
1408 	/*
1409 	 * Actually link the two hooks together.
1410 	 */
1411 	hook1->hk_peer = hook2;
1412 	hook2->hk_peer = hook1;
1413 
1414 	/* Each hook is referenced by the other */
1415 	NG_HOOK_REF(hook1);
1416 	NG_HOOK_REF(hook2);
1417 
1418 	/* Give each node the opportunity to veto the pending connection */
1419 	if (hook1->hk_node->nd_type->connect) {
1420 		error = (*hook1->hk_node->nd_type->connect) (hook1);
1421 	}
1422 
1423 	if ((error == 0) && hook2->hk_node->nd_type->connect) {
1424 		error = (*hook2->hk_node->nd_type->connect) (hook2);
1425 
1426 	}
1427 
1428 	/*
1429 	 * drop the references we were holding on the two hooks.
1430 	 */
1431 	if (error) {
1432 		ng_destroy_hook(hook2);	/* also zaps hook1 */
1433 		ng_rmnode(node2, NULL, NULL, 0);
1434 	} else {
1435 		/* As a last act, allow the hooks to be used */
1436 		hook1->hk_flags &= ~HK_INVALID;
1437 		hook2->hk_flags &= ~HK_INVALID;
1438 	}
1439 	NG_HOOK_UNREF(hook1);
1440 	NG_HOOK_UNREF(hook2);
1441 	return (error);
1442 }
1443 
1444 /************************************************************************
1445 		Utility routines to send self messages
1446 ************************************************************************/
1447 
1448 /* Shut this node down as soon as everyone is clear of it */
1449 /* Should add arg "immediatly" to jump the queue */
1450 int
1451 ng_rmnode_self(node_p node)
1452 {
1453 	int		error;
1454 
1455 	if (node == &ng_deadnode)
1456 		return (0);
1457 	node->nd_flags |= NG_INVALID;
1458 	if (node->nd_flags & NG_CLOSING)
1459 		return (0);
1460 
1461 	error = ng_send_fn(node, NULL, &ng_rmnode, NULL, 0);
1462 	return (error);
1463 }
1464 
1465 static void
1466 ng_rmhook_part2(node_p node, hook_p hook, void *arg1, int arg2)
1467 {
1468 	ng_destroy_hook(hook);
1469 	return ;
1470 }
1471 
1472 int
1473 ng_rmhook_self(hook_p hook)
1474 {
1475 	int		error;
1476 	node_p node = NG_HOOK_NODE(hook);
1477 
1478 	if (node == &ng_deadnode)
1479 		return (0);
1480 
1481 	error = ng_send_fn(node, hook, &ng_rmhook_part2, NULL, 0);
1482 	return (error);
1483 }
1484 
1485 /***********************************************************************
1486  * Parse and verify a string of the form:  <NODE:><PATH>
1487  *
1488  * Such a string can refer to a specific node or a specific hook
1489  * on a specific node, depending on how you look at it. In the
1490  * latter case, the PATH component must not end in a dot.
1491  *
1492  * Both <NODE:> and <PATH> are optional. The <PATH> is a string
1493  * of hook names separated by dots. This breaks out the original
1494  * string, setting *nodep to "NODE" (or NULL if none) and *pathp
1495  * to "PATH" (or NULL if degenerate). Also, *hookp will point to
1496  * the final hook component of <PATH>, if any, otherwise NULL.
1497  *
1498  * This returns -1 if the path is malformed. The char ** are optional.
1499  ***********************************************************************/
1500 int
1501 ng_path_parse(char *addr, char **nodep, char **pathp, char **hookp)
1502 {
1503 	char   *node, *path, *hook;
1504 	int     k;
1505 
1506 	/*
1507 	 * Extract absolute NODE, if any
1508 	 */
1509 	for (path = addr; *path && *path != ':'; path++);
1510 	if (*path) {
1511 		node = addr;	/* Here's the NODE */
1512 		*path++ = '\0';	/* Here's the PATH */
1513 
1514 		/* Node name must not be empty */
1515 		if (!*node)
1516 			return -1;
1517 
1518 		/* A name of "." is OK; otherwise '.' not allowed */
1519 		if (strcmp(node, ".") != 0) {
1520 			for (k = 0; node[k]; k++)
1521 				if (node[k] == '.')
1522 					return -1;
1523 		}
1524 	} else {
1525 		node = NULL;	/* No absolute NODE */
1526 		path = addr;	/* Here's the PATH */
1527 	}
1528 
1529 	/* Snoop for illegal characters in PATH */
1530 	for (k = 0; path[k]; k++)
1531 		if (path[k] == ':')
1532 			return -1;
1533 
1534 	/* Check for no repeated dots in PATH */
1535 	for (k = 0; path[k]; k++)
1536 		if (path[k] == '.' && path[k + 1] == '.')
1537 			return -1;
1538 
1539 	/* Remove extra (degenerate) dots from beginning or end of PATH */
1540 	if (path[0] == '.')
1541 		path++;
1542 	if (*path && path[strlen(path) - 1] == '.')
1543 		path[strlen(path) - 1] = 0;
1544 
1545 	/* If PATH has a dot, then we're not talking about a hook */
1546 	if (*path) {
1547 		for (hook = path, k = 0; path[k]; k++)
1548 			if (path[k] == '.') {
1549 				hook = NULL;
1550 				break;
1551 			}
1552 	} else
1553 		path = hook = NULL;
1554 
1555 	/* Done */
1556 	if (nodep)
1557 		*nodep = node;
1558 	if (pathp)
1559 		*pathp = path;
1560 	if (hookp)
1561 		*hookp = hook;
1562 	return (0);
1563 }
1564 
1565 /*
1566  * Given a path, which may be absolute or relative, and a starting node,
1567  * return the destination node.
1568  */
1569 int
1570 ng_path2noderef(node_p here, const char *address,
1571 				node_p *destp, hook_p *lasthook)
1572 {
1573 	char    fullpath[NG_PATHLEN + 1];
1574 	char   *nodename, *path, pbuf[2];
1575 	node_p  node, oldnode;
1576 	char   *cp;
1577 	hook_p hook = NULL;
1578 
1579 	/* Initialize */
1580 	if (destp == NULL) {
1581 		TRAP_ERROR();
1582 		return EINVAL;
1583 	}
1584 	*destp = NULL;
1585 
1586 	/* Make a writable copy of address for ng_path_parse() */
1587 	strncpy(fullpath, address, sizeof(fullpath) - 1);
1588 	fullpath[sizeof(fullpath) - 1] = '\0';
1589 
1590 	/* Parse out node and sequence of hooks */
1591 	if (ng_path_parse(fullpath, &nodename, &path, NULL) < 0) {
1592 		TRAP_ERROR();
1593 		return EINVAL;
1594 	}
1595 	if (path == NULL) {
1596 		pbuf[0] = '.';	/* Needs to be writable */
1597 		pbuf[1] = '\0';
1598 		path = pbuf;
1599 	}
1600 
1601 	/*
1602 	 * For an absolute address, jump to the starting node.
1603 	 * Note that this holds a reference on the node for us.
1604 	 * Don't forget to drop the reference if we don't need it.
1605 	 */
1606 	if (nodename) {
1607 		node = ng_name2noderef(here, nodename);
1608 		if (node == NULL) {
1609 			TRAP_ERROR();
1610 			return (ENOENT);
1611 		}
1612 	} else {
1613 		if (here == NULL) {
1614 			TRAP_ERROR();
1615 			return (EINVAL);
1616 		}
1617 		node = here;
1618 		NG_NODE_REF(node);
1619 	}
1620 
1621 	/*
1622 	 * Now follow the sequence of hooks
1623 	 * XXX
1624 	 * We actually cannot guarantee that the sequence
1625 	 * is not being demolished as we crawl along it
1626 	 * without extra-ordinary locking etc.
1627 	 * So this is a bit dodgy to say the least.
1628 	 * We can probably hold up some things by holding
1629 	 * the nodelist mutex for the time of this
1630 	 * crawl if we wanted.. At least that way we wouldn't have to
1631 	 * worry about the nodes dissappearing, but the hooks would still
1632 	 * be a problem.
1633 	 */
1634 	for (cp = path; node != NULL && *cp != '\0'; ) {
1635 		char *segment;
1636 
1637 		/*
1638 		 * Break out the next path segment. Replace the dot we just
1639 		 * found with a NUL; "cp" points to the next segment (or the
1640 		 * NUL at the end).
1641 		 */
1642 		for (segment = cp; *cp != '\0'; cp++) {
1643 			if (*cp == '.') {
1644 				*cp++ = '\0';
1645 				break;
1646 			}
1647 		}
1648 
1649 		/* Empty segment */
1650 		if (*segment == '\0')
1651 			continue;
1652 
1653 		/* We have a segment, so look for a hook by that name */
1654 		hook = ng_findhook(node, segment);
1655 
1656 		/* Can't get there from here... */
1657 		if (hook == NULL
1658 		    || NG_HOOK_PEER(hook) == NULL
1659 		    || NG_HOOK_NOT_VALID(hook)
1660 		    || NG_HOOK_NOT_VALID(NG_HOOK_PEER(hook))) {
1661 			TRAP_ERROR();
1662 			NG_NODE_UNREF(node);
1663 #if 0
1664 			printf("hooknotvalid %s %s %d %d %d %d ",
1665 					path,
1666 					segment,
1667 					hook == NULL,
1668 		     			NG_HOOK_PEER(hook) == NULL,
1669 		     			NG_HOOK_NOT_VALID(hook),
1670 		     			NG_HOOK_NOT_VALID(NG_HOOK_PEER(hook)));
1671 #endif
1672 			return (ENOENT);
1673 		}
1674 
1675 		/*
1676 		 * Hop on over to the next node
1677 		 * XXX
1678 		 * Big race conditions here as hooks and nodes go away
1679 		 * *** Idea.. store an ng_ID_t in each hook and use that
1680 		 * instead of the direct hook in this crawl?
1681 		 */
1682 		oldnode = node;
1683 		if ((node = NG_PEER_NODE(hook)))
1684 			NG_NODE_REF(node);	/* XXX RACE */
1685 		NG_NODE_UNREF(oldnode);	/* XXX another race */
1686 		if (NG_NODE_NOT_VALID(node)) {
1687 			NG_NODE_UNREF(node);	/* XXX more races */
1688 			node = NULL;
1689 		}
1690 	}
1691 
1692 	/* If node somehow missing, fail here (probably this is not needed) */
1693 	if (node == NULL) {
1694 		TRAP_ERROR();
1695 		return (ENXIO);
1696 	}
1697 
1698 	/* Done */
1699 	*destp = node;
1700 	if (lasthook != NULL)
1701 		*lasthook = (hook ? NG_HOOK_PEER(hook) : NULL);
1702 	return (0);
1703 }
1704 
1705 /***************************************************************\
1706 * Input queue handling.
1707 * All activities are submitted to the node via the input queue
1708 * which implements a multiple-reader/single-writer gate.
1709 * Items which cannot be handled immeditly are queued.
1710 *
1711 * read-write queue locking inline functions			*
1712 \***************************************************************/
1713 
1714 static __inline item_p ng_dequeue(struct ng_queue * ngq);
1715 static __inline item_p ng_acquire_read(struct ng_queue * ngq,
1716 					item_p  item);
1717 static __inline item_p ng_acquire_write(struct ng_queue * ngq,
1718 					item_p  item);
1719 static __inline void	ng_leave_read(struct ng_queue * ngq);
1720 static __inline void	ng_leave_write(struct ng_queue * ngq);
1721 static __inline void	ng_queue_rw(struct ng_queue * ngq,
1722 					item_p  item, int rw);
1723 
1724 /*
1725  * Definition of the bits fields in the ng_queue flag word.
1726  * Defined here rather than in netgraph.h because no-one should fiddle
1727  * with them.
1728  *
1729  * The ordering here may be important! don't shuffle these.
1730  */
1731 /*-
1732  Safety Barrier--------+ (adjustable to suit taste) (not used yet)
1733                        |
1734                        V
1735 +-------+-------+-------+-------+-------+-------+-------+-------+
1736 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
1737 | |A|c|t|i|v|e| |R|e|a|d|e|r| |C|o|u|n|t| | | | | | | | | |R|A|W|
1738 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |P|W|P|
1739 +-------+-------+-------+-------+-------+-------+-------+-------+
1740 \___________________________ ____________________________/ | | |
1741                             V                              | | |
1742                   [active reader count]                    | | |
1743                                                            | | |
1744           Read Pending ------------------------------------+ | |
1745                                                              | |
1746           Active Writer -------------------------------------+ |
1747                                                                |
1748           Write Pending ---------------------------------------+
1749 
1750 
1751 */
1752 #define WRITE_PENDING	0x00000001
1753 #define WRITER_ACTIVE	0x00000002
1754 #define READ_PENDING	0x00000004
1755 #define READER_INCREMENT 0x00000008
1756 #define READER_MASK	0xfffffff0	/* Not valid if WRITER_ACTIVE is set */
1757 #define SAFETY_BARRIER	0x00100000	/* 64K items queued should be enough */
1758 
1759 /* Defines of more elaborate states on the queue */
1760 /* Mask of bits a read cares about */
1761 #define NGQ_RMASK	(WRITE_PENDING|WRITER_ACTIVE|READ_PENDING)
1762 
1763 /* Mask of bits a write cares about */
1764 #define NGQ_WMASK	(NGQ_RMASK|READER_MASK)
1765 
1766 /* tests to decide if we could get a read or write off the queue */
1767 #define CAN_GET_READ(flag)	((flag & NGQ_RMASK) == READ_PENDING)
1768 #define CAN_GET_WRITE(flag)	((flag & NGQ_WMASK) == WRITE_PENDING)
1769 
1770 /* Is there a chance of getting ANY work off the queue? */
1771 #define CAN_GET_WORK(flag)	(CAN_GET_READ(flag) || CAN_GET_WRITE(flag))
1772 
1773 /*
1774  * Taking into account the current state of the queue and node, possibly take
1775  * the next entry off the queue and return it. Return NULL if there was
1776  * nothing we could return, either because there really was nothing there, or
1777  * because the node was in a state where it cannot yet process the next item
1778  * on the queue.
1779  *
1780  * This MUST MUST MUST be called with the mutex held.
1781  */
1782 static __inline item_p
1783 ng_dequeue(struct ng_queue *ngq)
1784 {
1785 	item_p item;
1786 	u_int		add_arg;
1787 
1788 	if (CAN_GET_READ(ngq->q_flags)) {
1789 		/*
1790 		 * Head of queue is a reader and we have no write active.
1791 		 * We don't care how many readers are already active.
1792 		 * Adjust the flags for the item we are about to dequeue.
1793 		 * Add the correct increment for the reader count as well.
1794 		 */
1795 		add_arg = (READER_INCREMENT - READ_PENDING);
1796 	} else if (CAN_GET_WRITE(ngq->q_flags)) {
1797 		/*
1798 		 * There is a pending write, no readers and no active writer.
1799 		 * This means we can go ahead with the pending writer. Note
1800 		 * the fact that we now have a writer, ready for when we take
1801 		 * it off the queue.
1802 		 *
1803 		 * We don't need to worry about a possible collision with the
1804 		 * fasttrack reader.
1805 		 *
1806 		 * The fasttrack thread may take a long time to discover that we
1807 		 * are running so we would have an inconsistent state in the
1808 		 * flags for a while. Since we ignore the reader count
1809 		 * entirely when the WRITER_ACTIVE flag is set, this should
1810 		 * not matter (in fact it is defined that way). If it tests
1811 		 * the flag before this operation, the WRITE_PENDING flag
1812 		 * will make it fail, and if it tests it later, the
1813 		 * WRITER_ACTIVE flag will do the same. If it is SO slow that
1814 		 * we have actually completed the operation, and neither flag
1815 		 * is set (nor the READ_PENDING) by the time that it tests
1816 		 * the flags, then it is actually ok for it to continue. If
1817 		 * it completes and we've finished and the read pending is
1818 		 * set it still fails.
1819 		 *
1820 		 * So we can just ignore it,  as long as we can ensure that the
1821 		 * transition from WRITE_PENDING state to the WRITER_ACTIVE
1822 		 * state is atomic.
1823 		 *
1824 		 * After failing, first it will be held back by the mutex, then
1825 		 * when it can proceed, it will queue its request, then it
1826 		 * would arrive at this function. Usually it will have to
1827 		 * leave empty handed because the ACTIVE WRITER bit will be
1828 		 * set.
1829 		 *
1830 		 * Adjust the flags for the item we are about to dequeue
1831 		 * and for the new active writer.
1832 		 */
1833 		add_arg = (WRITER_ACTIVE - WRITE_PENDING);
1834 		/*
1835 		 * We want to write "active writer, no readers " Now go make
1836 		 * it true. In fact there may be a number in the readers
1837 		 * count but we know it is not true and will be fixed soon.
1838 		 * We will fix the flags for the next pending entry in a
1839 		 * moment.
1840 		 */
1841 	} else {
1842 		/*
1843 		 * We can't dequeue anything.. return and say so. Probably we
1844 		 * have a write pending and the readers count is non zero. If
1845 		 * we got here because a reader hit us just at the wrong
1846 		 * moment with the fasttrack code, and put us in a strange
1847 		 * state, then it will be through in just a moment, (as soon
1848 		 * as we release the mutex) and keep things moving.
1849 		 * Make sure we remove ourselves from the work queue.
1850 		 */
1851 		ng_worklist_remove(ngq->q_node);
1852 		return (0);
1853 	}
1854 
1855 	/*
1856 	 * Now we dequeue the request (whatever it may be) and correct the
1857 	 * pending flags and the next and last pointers.
1858 	 */
1859 	item = ngq->queue;
1860 	ngq->queue = item->el_next;
1861 	if (ngq->last == &(item->el_next)) {
1862 		/*
1863 		 * that was the last entry in the queue so set the 'last
1864 		 * pointer up correctly and make sure the pending flags are
1865 		 * clear.
1866 		 */
1867 		ngq->last = &(ngq->queue);
1868 		/*
1869 		 * Whatever flag was set will be cleared and
1870 		 * the new acive field will be set by the add as well,
1871 		 * so we don't need to change add_arg.
1872 		 * But we know we don't need to be on the work list.
1873 		 */
1874 		atomic_add_long(&ngq->q_flags, add_arg);
1875 		ng_worklist_remove(ngq->q_node);
1876 	} else {
1877 		/*
1878 		 * Since there is something on the queue, note what it is
1879 		 * in the flags word.
1880 		 */
1881 		if ((ngq->queue->el_flags & NGQF_RW) == NGQF_READER) {
1882 			add_arg += READ_PENDING;
1883 		} else {
1884 			add_arg += WRITE_PENDING;
1885 		}
1886 		atomic_add_long(&ngq->q_flags, add_arg);
1887 		/*
1888 		 * If we see more doable work, make sure we are
1889 		 * on the work queue.
1890 		 */
1891 		if (CAN_GET_WORK(ngq->q_flags)) {
1892 			ng_setisr(ngq->q_node);
1893 		}
1894 	}
1895 	/*
1896 	 * We have successfully cleared the old pending flag, set the new one
1897 	 * if it is needed, and incremented the appropriate active field.
1898 	 * (all in one atomic addition.. )
1899 	 */
1900 	return (item);
1901 }
1902 
1903 /*
1904  * Queue a packet to be picked up by someone else.
1905  * We really don't care who, but we can't or don't want to hang around
1906  * to process it ourselves. We are probably an interrupt routine..
1907  * 1 = writer, 0 = reader
1908  */
1909 #define NGQRW_R 0
1910 #define NGQRW_W 1
1911 static __inline void
1912 ng_queue_rw(struct ng_queue * ngq, item_p  item, int rw)
1913 {
1914 	item->el_next = NULL;	/* maybe not needed */
1915 	*ngq->last = item;
1916 	/*
1917 	 * If it was the first item in the queue then we need to
1918 	 * set the last pointer and the type flags.
1919 	 */
1920 	if (ngq->last == &(ngq->queue)) {
1921 		/*
1922 		 * When called with constants for rw, the optimiser will
1923 		 * remove the unneeded branch below.
1924 		 */
1925 		if (rw == NGQRW_W) {
1926 			atomic_add_long(&ngq->q_flags, WRITE_PENDING);
1927 		} else {
1928 			atomic_add_long(&ngq->q_flags, READ_PENDING);
1929 		}
1930 	}
1931 	ngq->last = &(item->el_next);
1932 }
1933 
1934 
1935 /*
1936  * This function 'cheats' in that it first tries to 'grab' the use of the
1937  * node, without going through the mutex. We can do this becasue of the
1938  * semantics of the lock. The semantics include a clause that says that the
1939  * value of the readers count is invalid if the WRITER_ACTIVE flag is set. It
1940  * also says that the WRITER_ACTIVE flag cannot be set if the readers count
1941  * is not zero. Note that this talks about what is valid to SET the
1942  * WRITER_ACTIVE flag, because from the moment it is set, the value if the
1943  * reader count is immaterial, and not valid. The two 'pending' flags have a
1944  * similar effect, in that If they are orthogonal to the two active fields in
1945  * how they are set, but if either is set, the attempted 'grab' need to be
1946  * backed out because there is earlier work, and we maintain ordering in the
1947  * queue. The result of this is that the reader request can try obtain use of
1948  * the node with only a single atomic addition, and without any of the mutex
1949  * overhead. If this fails the operation degenerates to the same as for other
1950  * cases.
1951  *
1952  */
1953 static __inline item_p
1954 ng_acquire_read(struct ng_queue *ngq, item_p item)
1955 {
1956 
1957 	/* ######### Hack alert ######### */
1958 	atomic_add_long(&ngq->q_flags, READER_INCREMENT);
1959 	if ((ngq->q_flags & NGQ_RMASK) == 0) {
1960 		/* Successfully grabbed node */
1961 		return (item);
1962 	}
1963 	/* undo the damage if we didn't succeed */
1964 	atomic_subtract_long(&ngq->q_flags, READER_INCREMENT);
1965 
1966 	/* ######### End Hack alert ######### */
1967 	mtx_lock_spin((&ngq->q_mtx));
1968 	/*
1969 	 * Try again. Another processor (or interrupt for that matter) may
1970 	 * have removed the last queued item that was stopping us from
1971 	 * running, between the previous test, and the moment that we took
1972 	 * the mutex. (Or maybe a writer completed.)
1973 	 */
1974 	if ((ngq->q_flags & NGQ_RMASK) == 0) {
1975 		atomic_add_long(&ngq->q_flags, READER_INCREMENT);
1976 		mtx_unlock_spin((&ngq->q_mtx));
1977 		return (item);
1978 	}
1979 
1980 	/*
1981 	 * and queue the request for later.
1982 	 */
1983 	item->el_flags |= NGQF_READER;
1984 	ng_queue_rw(ngq, item, NGQRW_R);
1985 
1986 	/*
1987 	 * Ok, so that's the item successfully queued for later. So now we
1988 	 * see if we can dequeue something to run instead.
1989 	 */
1990 	item = ng_dequeue(ngq);
1991 	mtx_unlock_spin(&(ngq->q_mtx));
1992 	return (item);
1993 }
1994 
1995 static __inline item_p
1996 ng_acquire_write(struct ng_queue *ngq, item_p item)
1997 {
1998 restart:
1999 	mtx_lock_spin(&(ngq->q_mtx));
2000 	/*
2001 	 * If there are no readers, no writer, and no pending packets, then
2002 	 * we can just go ahead. In all other situations we need to queue the
2003 	 * request
2004 	 */
2005 	if ((ngq->q_flags & NGQ_WMASK) == 0) {
2006 		atomic_add_long(&ngq->q_flags, WRITER_ACTIVE);
2007 		mtx_unlock_spin((&ngq->q_mtx));
2008 		if (ngq->q_flags & READER_MASK) {
2009 			/* Collision with fast-track reader */
2010 			atomic_subtract_long(&ngq->q_flags, WRITER_ACTIVE);
2011 			goto restart;
2012 		}
2013 		return (item);
2014 	}
2015 
2016 	/*
2017 	 * and queue the request for later.
2018 	 */
2019 	item->el_flags &= ~NGQF_RW;
2020 	ng_queue_rw(ngq, item, NGQRW_W);
2021 
2022 	/*
2023 	 * Ok, so that's the item successfully queued for later. So now we
2024 	 * see if we can dequeue something to run instead.
2025 	 */
2026 	item = ng_dequeue(ngq);
2027 	mtx_unlock_spin(&(ngq->q_mtx));
2028 	return (item);
2029 }
2030 
2031 static __inline void
2032 ng_leave_read(struct ng_queue *ngq)
2033 {
2034 	atomic_subtract_long(&ngq->q_flags, READER_INCREMENT);
2035 }
2036 
2037 static __inline void
2038 ng_leave_write(struct ng_queue *ngq)
2039 {
2040 	atomic_subtract_long(&ngq->q_flags, WRITER_ACTIVE);
2041 }
2042 
2043 static void
2044 ng_flush_input_queue(struct ng_queue * ngq)
2045 {
2046 	item_p item;
2047 	u_int		add_arg;
2048 	mtx_lock_spin(&ngq->q_mtx);
2049 	for (;;) {
2050 		/* Now take a look at what's on the queue */
2051 		if (ngq->q_flags & READ_PENDING) {
2052 			add_arg = -READ_PENDING;
2053 		} else if (ngq->q_flags & WRITE_PENDING) {
2054 			add_arg = -WRITE_PENDING;
2055 		} else {
2056 			break;
2057 		}
2058 
2059 		item = ngq->queue;
2060 		ngq->queue = item->el_next;
2061 		if (ngq->last == &(item->el_next)) {
2062 			ngq->last = &(ngq->queue);
2063 		} else {
2064 			if ((ngq->queue->el_flags & NGQF_RW) == NGQF_READER) {
2065 				add_arg += READ_PENDING;
2066 			} else {
2067 				add_arg += WRITE_PENDING;
2068 			}
2069 		}
2070 		atomic_add_long(&ngq->q_flags, add_arg);
2071 
2072 		mtx_lock_spin(&ngq->q_mtx);
2073 		NG_FREE_ITEM(item);
2074 		mtx_unlock_spin(&ngq->q_mtx);
2075 	}
2076 	/*
2077 	 * Take us off the work queue if we are there.
2078 	 * We definatly have no work to be done.
2079 	 */
2080 	ng_worklist_remove(ngq->q_node);
2081 	mtx_unlock_spin(&ngq->q_mtx);
2082 }
2083 
2084 /***********************************************************************
2085 * Externally visible method for sending or queueing messages or data.
2086 ***********************************************************************/
2087 
2088 /*
2089  * The module code should have filled out the item correctly by this stage:
2090  * Common:
2091  *    reference to destination node.
2092  *    Reference to destination rcv hook if relevant.
2093  * Data:
2094  *    pointer to mbuf
2095  *    pointer to metadata
2096  * Control_Message:
2097  *    pointer to msg.
2098  *    ID of original sender node. (return address)
2099  * Function:
2100  *    Function pointer
2101  *    void * argument
2102  *    integer argument
2103  *
2104  * The nodes have several routines and macros to help with this task:
2105  */
2106 
2107 int
2108 ng_snd_item(item_p item, int queue)
2109 {
2110 	hook_p hook = NGI_HOOK(item);
2111 	node_p node = NGI_NODE(item);
2112 	int rw;
2113 	int error = 0, ierror;
2114 	item_p	oitem;
2115 	struct ng_queue * ngq = &node->nd_input_queue;
2116 
2117 #ifdef	NETGRAPH_DEBUG
2118         _ngi_check(item, __FILE__, __LINE__);
2119 #endif
2120 
2121 	if (item == NULL) {
2122 		TRAP_ERROR();
2123 		return (EINVAL);	/* failed to get queue element */
2124 	}
2125 	if (node == NULL) {
2126 		NG_FREE_ITEM(item);
2127 		TRAP_ERROR();
2128 		return (EINVAL);	/* No address */
2129 	}
2130 	switch(item->el_flags & NGQF_TYPE) {
2131 	case NGQF_DATA:
2132 		/*
2133 		 * DATA MESSAGE
2134 		 * Delivered to a node via a non-optional hook.
2135 		 * Both should be present in the item even though
2136 		 * the node is derivable from the hook.
2137 		 * References are held on both by the item.
2138 		 */
2139 		CHECK_DATA_MBUF(NGI_M(item));
2140 		if (hook == NULL) {
2141 			NG_FREE_ITEM(item);
2142 			TRAP_ERROR();
2143 			return(EINVAL);
2144 		}
2145 		if ((NG_HOOK_NOT_VALID(hook))
2146 		|| (NG_NODE_NOT_VALID(NG_HOOK_NODE(hook)))) {
2147 			NG_FREE_ITEM(item);
2148 			return (ENOTCONN);
2149 		}
2150 		if ((hook->hk_flags & HK_QUEUE)) {
2151 			queue = 1;
2152 		}
2153 		/* By default data is a reader in the locking scheme */
2154 		item->el_flags |= NGQF_READER;
2155 		rw = NGQRW_R;
2156 		break;
2157 	case NGQF_MESG:
2158 		/*
2159 		 * CONTROL MESSAGE
2160 		 * Delivered to a node.
2161 		 * Hook is optional.
2162 		 * References are held by the item on the node and
2163 		 * the hook if it is present.
2164 		 */
2165 		if (hook && (hook->hk_flags & HK_QUEUE)) {
2166 			queue = 1;
2167 		}
2168 		/* Data messages count as writers unles explicitly exempted */
2169 		if (NGI_MSG(item)->header.cmd & NGM_READONLY) {
2170 			item->el_flags |= NGQF_READER;
2171 			rw = NGQRW_R;
2172 		} else {
2173 			item->el_flags &= ~NGQF_RW;
2174 			rw = NGQRW_W;
2175 		}
2176 		break;
2177 	case NGQF_FN:
2178 		item->el_flags &= ~NGQF_RW;
2179 		rw = NGQRW_W;
2180 		break;
2181 	default:
2182 		NG_FREE_ITEM(item);
2183 		TRAP_ERROR();
2184 		return (EINVAL);
2185 	}
2186 	/*
2187 	 * If the node specifies single threading, force writer semantics
2188 	 * Similarly the node may say one hook always produces writers.
2189 	 * These are over-rides.
2190 	 */
2191 	if ((node->nd_flags & NG_FORCE_WRITER)
2192 	|| (hook && (hook->hk_flags & HK_FORCE_WRITER))) {
2193 			rw = NGQRW_W;
2194 			item->el_flags &= ~NGQF_READER;
2195 	}
2196 	if (queue) {
2197 		/* Put it on the queue for that node*/
2198 #ifdef	NETGRAPH_DEBUG
2199         _ngi_check(item, __FILE__, __LINE__);
2200 #endif
2201 		mtx_lock_spin(&(ngq->q_mtx));
2202 		ng_queue_rw(ngq, item, rw);
2203 		/*
2204 		 * If there are active elements then we can rely on
2205 		 * them. if not we should not rely on another packet
2206 		 * coming here by another path,
2207 		 * so it is best to put us in the netisr list.
2208 		 * We can take the worklist lock with the node locked
2209 		 * BUT NOT THE REVERSE!
2210 		 */
2211 		if (CAN_GET_WORK(ngq->q_flags)) {
2212 			ng_setisr(node);
2213 		}
2214 		mtx_unlock_spin(&(ngq->q_mtx));
2215 		return (0);
2216 	}
2217 	/*
2218 	 * Take a queue item and a node and see if we can apply the item to
2219 	 * the node. We may end up getting a different item to apply instead.
2220 	 * Will allow for a piggyback reply only in the case where
2221 	 * there is no queueing.
2222 	 */
2223 
2224 	oitem = item;
2225 	/*
2226 	 * We already decided how we will be queueud or treated.
2227 	 * Try get the appropriate operating permission.
2228 	 */
2229  	if (rw == NGQRW_R) {
2230 		item = ng_acquire_read(ngq, item);
2231 	} else {
2232 		item = ng_acquire_write(ngq, item);
2233 	}
2234 
2235 	/*
2236 	 * May have come back with a different item.
2237 	 * or maybe none at all. The one we started with will
2238 	 * have been queued in thises cases.
2239 	 */
2240 	if (item == NULL) {
2241 		return (0);
2242 	}
2243 
2244 #ifdef	NETGRAPH_DEBUG
2245         _ngi_check(item, __FILE__, __LINE__);
2246 #endif
2247 	/*
2248 	 * Take over the reference frm the item.
2249 	 * Hold it until the called function returns.
2250 	 */
2251 	NGI_GET_NODE(item, node); /* zaps stored node */
2252 
2253 	ierror = ng_apply_item(node, item); /* drops r/w lock when done */
2254 
2255 	/* only return an error if it was our initial item.. (compat hack) */
2256 	if (oitem == item) {
2257 		error = ierror;
2258 	}
2259 
2260 	/*
2261 	 * If the node goes away when we remove the reference,
2262 	 * whatever we just did caused it.. whatever we do, DO NOT
2263 	 * access the node again!
2264 	 */
2265 	if (NG_NODE_UNREF(node) == 0) {
2266 		return (error);
2267 	}
2268 
2269 	/*
2270 	 * Now we've handled the packet we brought, (or a friend of it) let's
2271 	 * look for any other packets that may have been queued up. We hold
2272 	 * no locks, so if someone puts something in the queue after
2273 	 * we check that it is empty, it is their problem
2274 	 * to ensure it is processed. If we have the netisr thread cme in here
2275 	 * while we still say we have stuff to do, we may get a boost
2276 	 * in SMP systems. :-)
2277 	 */
2278 	for (;;) {
2279 		/*
2280 		 * dequeue acquires and adjusts the input_queue as it dequeues
2281 		 * packets. It acquires the rw lock as needed.
2282 		 */
2283 		mtx_lock_spin(&ngq->q_mtx);
2284 		item = ng_dequeue(ngq); /* fixes worklist too*/
2285 		if (!item) {
2286 			mtx_unlock_spin(&ngq->q_mtx);
2287 			return (error);
2288 		}
2289 		mtx_unlock_spin(&ngq->q_mtx);
2290 
2291 		/*
2292 		 * Take over the reference frm the item.
2293 		 * Hold it until the called function returns.
2294 		 */
2295 
2296 		NGI_GET_NODE(item, node); /* zaps stored node */
2297 
2298 		/*
2299 		 * We have the appropriate lock, so run the item.
2300 		 * When finished it will drop the lock accordingly
2301 		 */
2302 		ierror = ng_apply_item(node, item);
2303 
2304 		/*
2305 		 * only return an error if it was our initial
2306 		 * item.. (compat hack)
2307 		 */
2308 		if (oitem == item) {
2309 			error = ierror;
2310 		}
2311 
2312 		/*
2313 		 * If the node goes away when we remove the reference,
2314 		 * whatever we just did caused it.. whatever we do, DO NOT
2315 		 * access the node again!
2316 		 */
2317 		if (NG_NODE_UNREF(node) == 0) {
2318 			break;
2319 		}
2320 	}
2321 	return (error);
2322 }
2323 
2324 /*
2325  * We have an item that was possibly queued somewhere.
2326  * It should contain all the information needed
2327  * to run it on the appropriate node/hook.
2328  */
2329 static int
2330 ng_apply_item(node_p node, item_p item)
2331 {
2332 	hook_p  hook;
2333 	int	was_reader = ((item->el_flags & NGQF_RW));
2334 	int	error = 0;
2335 	ng_rcvdata_t *rcvdata;
2336 	ng_rcvmsg_t *rcvmsg;
2337 
2338 	NGI_GET_HOOK(item, hook); /* clears stored hook */
2339 #ifdef	NETGRAPH_DEBUG
2340         _ngi_check(item, __FILE__, __LINE__);
2341 #endif
2342 	switch (item->el_flags & NGQF_TYPE) {
2343 	case NGQF_DATA:
2344 		/*
2345 		 * Check things are still ok as when we were queued.
2346 		 */
2347 		if ((hook == NULL)
2348 		|| NG_HOOK_NOT_VALID(hook)
2349 		|| NG_NODE_NOT_VALID(node) ) {
2350 			error = EIO;
2351 			NG_FREE_ITEM(item);
2352 			break;
2353 		}
2354 		/*
2355 		 * If no receive method, just silently drop it.
2356 		 * Give preference to the hook over-ride method
2357 		 */
2358 		if ((!(rcvdata = hook->hk_rcvdata))
2359 		&& (!(rcvdata = NG_HOOK_NODE(hook)->nd_type->rcvdata))) {
2360 			error = 0;
2361 			NG_FREE_ITEM(item);
2362 			break;
2363 		}
2364 		error = (*rcvdata)(hook, item);
2365 		break;
2366 	case NGQF_MESG:
2367 		if (hook) {
2368 			if (NG_HOOK_NOT_VALID(hook)) {
2369 				/*
2370 				 * The hook has been zapped then we can't
2371 				 * use it. Immediatly drop its reference.
2372 				 * The message may not need it.
2373 				 */
2374 				NG_HOOK_UNREF(hook);
2375 				hook = NULL;
2376 			}
2377 		}
2378 		/*
2379 		 * Similarly, if the node is a zombie there is
2380 		 * nothing we can do with it, drop everything.
2381 		 */
2382 		if (NG_NODE_NOT_VALID(node)) {
2383 			TRAP_ERROR();
2384 			error = EINVAL;
2385 			NG_FREE_ITEM(item);
2386 		} else {
2387 			/*
2388 			 * Call the appropriate message handler for the object.
2389 			 * It is up to the message handler to free the message.
2390 			 * If it's a generic message, handle it generically,
2391 			 * otherwise call the type's message handler
2392 			 * (if it exists)
2393 			 * XXX (race). Remember that a queued message may
2394 			 * reference a node or hook that has just been
2395 			 * invalidated. It will exist as the queue code
2396 			 * is holding a reference, but..
2397 			 */
2398 
2399 			struct ng_mesg *msg = NGI_MSG(item);
2400 
2401 			/*
2402 			 * check if the generic handler owns it.
2403 			 */
2404 			if ((msg->header.typecookie == NGM_GENERIC_COOKIE)
2405 			&& ((msg->header.flags & NGF_RESP) == 0)) {
2406 				error = ng_generic_msg(node, item, hook);
2407 				break;
2408 			}
2409 			/*
2410 			 * Now see if there is a handler (hook or node specific)
2411 			 * in the target node. If none, silently discard.
2412 			 */
2413 			if (((!hook) || (!(rcvmsg = hook->hk_rcvmsg)))
2414 			&& (!(rcvmsg = node->nd_type->rcvmsg))) {
2415 				TRAP_ERROR();
2416 				error = 0;
2417 				NG_FREE_ITEM(item);
2418 				break;
2419 			}
2420 			error = (*rcvmsg)(node, item, hook);
2421 		}
2422 		break;
2423 	case NGQF_FN:
2424 		/*
2425 		 *  We have to implicitly trust the hook,
2426 		 * as some of these are used for system purposes
2427 		 * where the hook is invalid. In the case of
2428 		 * the shutdown message we allow it to hit
2429 		 * even if the node is invalid.
2430 		 */
2431 		if ((NG_NODE_NOT_VALID(node))
2432 		&& (NGI_FN(item) != &ng_rmnode)) {
2433 			TRAP_ERROR();
2434 			error = EINVAL;
2435 			break;
2436 		}
2437 		(*NGI_FN(item))(node, hook, NGI_ARG1(item), NGI_ARG2(item));
2438 		NG_FREE_ITEM(item);
2439 		break;
2440 
2441 	}
2442 	/*
2443 	 * We held references on some of the resources
2444 	 * that we took from the item. Now that we have
2445 	 * finished doing everything, drop those references.
2446 	 */
2447 	if (hook) {
2448 		NG_HOOK_UNREF(hook);
2449 	}
2450 
2451 	if (was_reader) {
2452 		ng_leave_read(&node->nd_input_queue);
2453 	} else {
2454 		ng_leave_write(&node->nd_input_queue);
2455 	}
2456 	return (error);
2457 }
2458 
2459 /***********************************************************************
2460  * Implement the 'generic' control messages
2461  ***********************************************************************/
2462 static int
2463 ng_generic_msg(node_p here, item_p item, hook_p lasthook)
2464 {
2465 	int error = 0;
2466 	struct ng_mesg *msg;
2467 	struct ng_mesg *resp = NULL;
2468 
2469 	NGI_GET_MSG(item, msg);
2470 	if (msg->header.typecookie != NGM_GENERIC_COOKIE) {
2471 		TRAP_ERROR();
2472 		error = EINVAL;
2473 		goto out;
2474 	}
2475 	switch (msg->header.cmd) {
2476 	case NGM_SHUTDOWN:
2477 		ng_rmnode(here, NULL, NULL, 0);
2478 		break;
2479 	case NGM_MKPEER:
2480 	    {
2481 		struct ngm_mkpeer *const mkp = (struct ngm_mkpeer *) msg->data;
2482 
2483 		if (msg->header.arglen != sizeof(*mkp)) {
2484 			TRAP_ERROR();
2485 			error = EINVAL;
2486 			break;
2487 		}
2488 		mkp->type[sizeof(mkp->type) - 1] = '\0';
2489 		mkp->ourhook[sizeof(mkp->ourhook) - 1] = '\0';
2490 		mkp->peerhook[sizeof(mkp->peerhook) - 1] = '\0';
2491 		error = ng_mkpeer(here, mkp->ourhook, mkp->peerhook, mkp->type);
2492 		break;
2493 	    }
2494 	case NGM_CONNECT:
2495 	    {
2496 		struct ngm_connect *const con =
2497 			(struct ngm_connect *) msg->data;
2498 		node_p node2;
2499 
2500 		if (msg->header.arglen != sizeof(*con)) {
2501 			TRAP_ERROR();
2502 			error = EINVAL;
2503 			break;
2504 		}
2505 		con->path[sizeof(con->path) - 1] = '\0';
2506 		con->ourhook[sizeof(con->ourhook) - 1] = '\0';
2507 		con->peerhook[sizeof(con->peerhook) - 1] = '\0';
2508 		/* Don't forget we get a reference.. */
2509 		error = ng_path2noderef(here, con->path, &node2, NULL);
2510 		if (error)
2511 			break;
2512 		error = ng_con_nodes(here, con->ourhook, node2, con->peerhook);
2513 		NG_NODE_UNREF(node2);
2514 		break;
2515 	    }
2516 	case NGM_NAME:
2517 	    {
2518 		struct ngm_name *const nam = (struct ngm_name *) msg->data;
2519 
2520 		if (msg->header.arglen != sizeof(*nam)) {
2521 			TRAP_ERROR();
2522 			error = EINVAL;
2523 			break;
2524 		}
2525 		nam->name[sizeof(nam->name) - 1] = '\0';
2526 		error = ng_name_node(here, nam->name);
2527 		break;
2528 	    }
2529 	case NGM_RMHOOK:
2530 	    {
2531 		struct ngm_rmhook *const rmh = (struct ngm_rmhook *) msg->data;
2532 		hook_p hook;
2533 
2534 		if (msg->header.arglen != sizeof(*rmh)) {
2535 			TRAP_ERROR();
2536 			error = EINVAL;
2537 			break;
2538 		}
2539 		rmh->ourhook[sizeof(rmh->ourhook) - 1] = '\0';
2540 		if ((hook = ng_findhook(here, rmh->ourhook)) != NULL)
2541 			ng_destroy_hook(hook);
2542 		break;
2543 	    }
2544 	case NGM_NODEINFO:
2545 	    {
2546 		struct nodeinfo *ni;
2547 
2548 		NG_MKRESPONSE(resp, msg, sizeof(*ni), M_NOWAIT);
2549 		if (resp == NULL) {
2550 			error = ENOMEM;
2551 			break;
2552 		}
2553 
2554 		/* Fill in node info */
2555 		ni = (struct nodeinfo *) resp->data;
2556 		if (NG_NODE_HAS_NAME(here))
2557 			strncpy(ni->name, NG_NODE_NAME(here), NG_NODELEN);
2558 		strncpy(ni->type, here->nd_type->name, NG_TYPELEN);
2559 		ni->id = ng_node2ID(here);
2560 		ni->hooks = here->nd_numhooks;
2561 		break;
2562 	    }
2563 	case NGM_LISTHOOKS:
2564 	    {
2565 		const int nhooks = here->nd_numhooks;
2566 		struct hooklist *hl;
2567 		struct nodeinfo *ni;
2568 		hook_p hook;
2569 
2570 		/* Get response struct */
2571 		NG_MKRESPONSE(resp, msg, sizeof(*hl)
2572 		    + (nhooks * sizeof(struct linkinfo)), M_NOWAIT);
2573 		if (resp == NULL) {
2574 			error = ENOMEM;
2575 			break;
2576 		}
2577 		hl = (struct hooklist *) resp->data;
2578 		ni = &hl->nodeinfo;
2579 
2580 		/* Fill in node info */
2581 		if (NG_NODE_HAS_NAME(here))
2582 			strncpy(ni->name, NG_NODE_NAME(here), NG_NODELEN);
2583 		strncpy(ni->type, here->nd_type->name, NG_TYPELEN);
2584 		ni->id = ng_node2ID(here);
2585 
2586 		/* Cycle through the linked list of hooks */
2587 		ni->hooks = 0;
2588 		LIST_FOREACH(hook, &here->nd_hooks, hk_hooks) {
2589 			struct linkinfo *const link = &hl->link[ni->hooks];
2590 
2591 			if (ni->hooks >= nhooks) {
2592 				log(LOG_ERR, "%s: number of %s changed\n",
2593 				    __func__, "hooks");
2594 				break;
2595 			}
2596 			if (NG_HOOK_NOT_VALID(hook))
2597 				continue;
2598 			strncpy(link->ourhook, NG_HOOK_NAME(hook), NG_HOOKLEN);
2599 			strncpy(link->peerhook,
2600 				NG_PEER_HOOK_NAME(hook), NG_HOOKLEN);
2601 			if (NG_PEER_NODE_NAME(hook)[0] != '\0')
2602 				strncpy(link->nodeinfo.name,
2603 				    NG_PEER_NODE_NAME(hook), NG_NODELEN);
2604 			strncpy(link->nodeinfo.type,
2605 			   NG_PEER_NODE(hook)->nd_type->name, NG_TYPELEN);
2606 			link->nodeinfo.id = ng_node2ID(NG_PEER_NODE(hook));
2607 			link->nodeinfo.hooks = NG_PEER_NODE(hook)->nd_numhooks;
2608 			ni->hooks++;
2609 		}
2610 		break;
2611 	    }
2612 
2613 	case NGM_LISTNAMES:
2614 	case NGM_LISTNODES:
2615 	    {
2616 		const int unnamed = (msg->header.cmd == NGM_LISTNODES);
2617 		struct namelist *nl;
2618 		node_p node;
2619 		int num = 0;
2620 
2621 		mtx_lock(&ng_nodelist_mtx);
2622 		/* Count number of nodes */
2623 		LIST_FOREACH(node, &ng_nodelist, nd_nodes) {
2624 			if (NG_NODE_IS_VALID(node)
2625 			&& (unnamed || NG_NODE_HAS_NAME(node))) {
2626 				num++;
2627 			}
2628 		}
2629 		mtx_unlock(&ng_nodelist_mtx);
2630 
2631 		/* Get response struct */
2632 		NG_MKRESPONSE(resp, msg, sizeof(*nl)
2633 		    + (num * sizeof(struct nodeinfo)), M_NOWAIT);
2634 		if (resp == NULL) {
2635 			error = ENOMEM;
2636 			break;
2637 		}
2638 		nl = (struct namelist *) resp->data;
2639 
2640 		/* Cycle through the linked list of nodes */
2641 		nl->numnames = 0;
2642 		mtx_lock(&ng_nodelist_mtx);
2643 		LIST_FOREACH(node, &ng_nodelist, nd_nodes) {
2644 			struct nodeinfo *const np = &nl->nodeinfo[nl->numnames];
2645 
2646 			if (nl->numnames >= num) {
2647 				log(LOG_ERR, "%s: number of %s changed\n",
2648 				    __func__, "nodes");
2649 				break;
2650 			}
2651 			if (NG_NODE_NOT_VALID(node))
2652 				continue;
2653 			if (!unnamed && (! NG_NODE_HAS_NAME(node)))
2654 				continue;
2655 			if (NG_NODE_HAS_NAME(node))
2656 				strncpy(np->name, NG_NODE_NAME(node), NG_NODELEN);
2657 			strncpy(np->type, node->nd_type->name, NG_TYPELEN);
2658 			np->id = ng_node2ID(node);
2659 			np->hooks = node->nd_numhooks;
2660 			nl->numnames++;
2661 		}
2662 		mtx_unlock(&ng_nodelist_mtx);
2663 		break;
2664 	    }
2665 
2666 	case NGM_LISTTYPES:
2667 	    {
2668 		struct typelist *tl;
2669 		struct ng_type *type;
2670 		int num = 0;
2671 
2672 		mtx_lock(&ng_typelist_mtx);
2673 		/* Count number of types */
2674 		LIST_FOREACH(type, &ng_typelist, types) {
2675 			num++;
2676 		}
2677 		mtx_unlock(&ng_typelist_mtx);
2678 
2679 		/* Get response struct */
2680 		NG_MKRESPONSE(resp, msg, sizeof(*tl)
2681 		    + (num * sizeof(struct typeinfo)), M_NOWAIT);
2682 		if (resp == NULL) {
2683 			error = ENOMEM;
2684 			break;
2685 		}
2686 		tl = (struct typelist *) resp->data;
2687 
2688 		/* Cycle through the linked list of types */
2689 		tl->numtypes = 0;
2690 		mtx_lock(&ng_typelist_mtx);
2691 		LIST_FOREACH(type, &ng_typelist, types) {
2692 			struct typeinfo *const tp = &tl->typeinfo[tl->numtypes];
2693 
2694 			if (tl->numtypes >= num) {
2695 				log(LOG_ERR, "%s: number of %s changed\n",
2696 				    __func__, "types");
2697 				break;
2698 			}
2699 			strncpy(tp->type_name, type->name, NG_TYPELEN);
2700 			tp->numnodes = type->refs - 1; /* don't count list */
2701 			tl->numtypes++;
2702 		}
2703 		mtx_unlock(&ng_typelist_mtx);
2704 		break;
2705 	    }
2706 
2707 	case NGM_BINARY2ASCII:
2708 	    {
2709 		int bufSize = 20 * 1024;	/* XXX hard coded constant */
2710 		const struct ng_parse_type *argstype;
2711 		const struct ng_cmdlist *c;
2712 		struct ng_mesg *binary, *ascii;
2713 
2714 		/* Data area must contain a valid netgraph message */
2715 		binary = (struct ng_mesg *)msg->data;
2716 		if (msg->header.arglen < sizeof(struct ng_mesg)
2717 		    || (msg->header.arglen - sizeof(struct ng_mesg)
2718 		      < binary->header.arglen)) {
2719 			TRAP_ERROR();
2720 			error = EINVAL;
2721 			break;
2722 		}
2723 
2724 		/* Get a response message with lots of room */
2725 		NG_MKRESPONSE(resp, msg, sizeof(*ascii) + bufSize, M_NOWAIT);
2726 		if (resp == NULL) {
2727 			error = ENOMEM;
2728 			break;
2729 		}
2730 		ascii = (struct ng_mesg *)resp->data;
2731 
2732 		/* Copy binary message header to response message payload */
2733 		bcopy(binary, ascii, sizeof(*binary));
2734 
2735 		/* Find command by matching typecookie and command number */
2736 		for (c = here->nd_type->cmdlist;
2737 		    c != NULL && c->name != NULL; c++) {
2738 			if (binary->header.typecookie == c->cookie
2739 			    && binary->header.cmd == c->cmd)
2740 				break;
2741 		}
2742 		if (c == NULL || c->name == NULL) {
2743 			for (c = ng_generic_cmds; c->name != NULL; c++) {
2744 				if (binary->header.typecookie == c->cookie
2745 				    && binary->header.cmd == c->cmd)
2746 					break;
2747 			}
2748 			if (c->name == NULL) {
2749 				NG_FREE_MSG(resp);
2750 				error = ENOSYS;
2751 				break;
2752 			}
2753 		}
2754 
2755 		/* Convert command name to ASCII */
2756 		snprintf(ascii->header.cmdstr, sizeof(ascii->header.cmdstr),
2757 		    "%s", c->name);
2758 
2759 		/* Convert command arguments to ASCII */
2760 		argstype = (binary->header.flags & NGF_RESP) ?
2761 		    c->respType : c->mesgType;
2762 		if (argstype == NULL) {
2763 			*ascii->data = '\0';
2764 		} else {
2765 			if ((error = ng_unparse(argstype,
2766 			    (u_char *)binary->data,
2767 			    ascii->data, bufSize)) != 0) {
2768 				NG_FREE_MSG(resp);
2769 				break;
2770 			}
2771 		}
2772 
2773 		/* Return the result as struct ng_mesg plus ASCII string */
2774 		bufSize = strlen(ascii->data) + 1;
2775 		ascii->header.arglen = bufSize;
2776 		resp->header.arglen = sizeof(*ascii) + bufSize;
2777 		break;
2778 	    }
2779 
2780 	case NGM_ASCII2BINARY:
2781 	    {
2782 		int bufSize = 2000;	/* XXX hard coded constant */
2783 		const struct ng_cmdlist *c;
2784 		const struct ng_parse_type *argstype;
2785 		struct ng_mesg *ascii, *binary;
2786 		int off = 0;
2787 
2788 		/* Data area must contain at least a struct ng_mesg + '\0' */
2789 		ascii = (struct ng_mesg *)msg->data;
2790 		if ((msg->header.arglen < sizeof(*ascii) + 1)
2791 		    || (ascii->header.arglen < 1)
2792 		    || (msg->header.arglen
2793 		      < sizeof(*ascii) + ascii->header.arglen)) {
2794 			TRAP_ERROR();
2795 			error = EINVAL;
2796 			break;
2797 		}
2798 		ascii->data[ascii->header.arglen - 1] = '\0';
2799 
2800 		/* Get a response message with lots of room */
2801 		NG_MKRESPONSE(resp, msg, sizeof(*binary) + bufSize, M_NOWAIT);
2802 		if (resp == NULL) {
2803 			error = ENOMEM;
2804 			break;
2805 		}
2806 		binary = (struct ng_mesg *)resp->data;
2807 
2808 		/* Copy ASCII message header to response message payload */
2809 		bcopy(ascii, binary, sizeof(*ascii));
2810 
2811 		/* Find command by matching ASCII command string */
2812 		for (c = here->nd_type->cmdlist;
2813 		    c != NULL && c->name != NULL; c++) {
2814 			if (strcmp(ascii->header.cmdstr, c->name) == 0)
2815 				break;
2816 		}
2817 		if (c == NULL || c->name == NULL) {
2818 			for (c = ng_generic_cmds; c->name != NULL; c++) {
2819 				if (strcmp(ascii->header.cmdstr, c->name) == 0)
2820 					break;
2821 			}
2822 			if (c->name == NULL) {
2823 				NG_FREE_MSG(resp);
2824 				error = ENOSYS;
2825 				break;
2826 			}
2827 		}
2828 
2829 		/* Convert command name to binary */
2830 		binary->header.cmd = c->cmd;
2831 		binary->header.typecookie = c->cookie;
2832 
2833 		/* Convert command arguments to binary */
2834 		argstype = (binary->header.flags & NGF_RESP) ?
2835 		    c->respType : c->mesgType;
2836 		if (argstype == NULL) {
2837 			bufSize = 0;
2838 		} else {
2839 			if ((error = ng_parse(argstype, ascii->data,
2840 			    &off, (u_char *)binary->data, &bufSize)) != 0) {
2841 				NG_FREE_MSG(resp);
2842 				break;
2843 			}
2844 		}
2845 
2846 		/* Return the result */
2847 		binary->header.arglen = bufSize;
2848 		resp->header.arglen = sizeof(*binary) + bufSize;
2849 		break;
2850 	    }
2851 
2852 	case NGM_TEXT_CONFIG:
2853 	case NGM_TEXT_STATUS:
2854 		/*
2855 		 * This one is tricky as it passes the command down to the
2856 		 * actual node, even though it is a generic type command.
2857 		 * This means we must assume that the item/msg is already freed
2858 		 * when control passes back to us.
2859 		 */
2860 		if (here->nd_type->rcvmsg != NULL) {
2861 			NGI_MSG(item) = msg; /* put it back as we found it */
2862 			return((*here->nd_type->rcvmsg)(here, item, lasthook));
2863 		}
2864 		/* Fall through if rcvmsg not supported */
2865 	default:
2866 		TRAP_ERROR();
2867 		error = EINVAL;
2868 	}
2869 	/*
2870 	 * Sometimes a generic message may be statically allocated
2871 	 * to avoid problems with allocating when in tight memeory situations.
2872 	 * Don't free it if it is so.
2873 	 * I break them appart here, because erros may cause a free if the item
2874 	 * in which case we'd be doing it twice.
2875 	 * they are kept together above, to simplify freeing.
2876 	 */
2877 out:
2878 	NG_RESPOND_MSG(error, here, item, resp);
2879 	if (msg)
2880 		NG_FREE_MSG(msg);
2881 	return (error);
2882 }
2883 
2884 /*
2885  * Copy a 'meta'.
2886  *
2887  * Returns new meta, or NULL if original meta is NULL or ENOMEM.
2888  */
2889 meta_p
2890 ng_copy_meta(meta_p meta)
2891 {
2892 	meta_p meta2;
2893 
2894 	if (meta == NULL)
2895 		return (NULL);
2896 	MALLOC(meta2, meta_p, meta->used_len, M_NETGRAPH_META, M_NOWAIT);
2897 	if (meta2 == NULL)
2898 		return (NULL);
2899 	meta2->allocated_len = meta->used_len;
2900 	bcopy(meta, meta2, meta->used_len);
2901 	return (meta2);
2902 }
2903 
2904 /************************************************************************
2905 			Module routines
2906 ************************************************************************/
2907 
2908 /*
2909  * Handle the loading/unloading of a netgraph node type module
2910  */
2911 int
2912 ng_mod_event(module_t mod, int event, void *data)
2913 {
2914 	struct ng_type *const type = data;
2915 	int s, error = 0;
2916 
2917 	switch (event) {
2918 	case MOD_LOAD:
2919 
2920 		/* Register new netgraph node type */
2921 		s = splnet();
2922 		if ((error = ng_newtype(type)) != 0) {
2923 			splx(s);
2924 			break;
2925 		}
2926 
2927 		/* Call type specific code */
2928 		if (type->mod_event != NULL)
2929 			if ((error = (*type->mod_event)(mod, event, data))) {
2930 				mtx_lock(&ng_typelist_mtx);
2931 				type->refs--;	/* undo it */
2932 				LIST_REMOVE(type, types);
2933 				mtx_unlock(&ng_typelist_mtx);
2934 			}
2935 		splx(s);
2936 		break;
2937 
2938 	case MOD_UNLOAD:
2939 		s = splnet();
2940 		if (type->refs > 1) {		/* make sure no nodes exist! */
2941 			error = EBUSY;
2942 		} else {
2943 			if (type->refs == 0) {
2944 				/* failed load, nothing to undo */
2945 				splx(s);
2946 				break;
2947 			}
2948 			if (type->mod_event != NULL) {	/* check with type */
2949 				error = (*type->mod_event)(mod, event, data);
2950 				if (error != 0) {	/* type refuses.. */
2951 					splx(s);
2952 					break;
2953 				}
2954 			}
2955 			mtx_lock(&ng_typelist_mtx);
2956 			LIST_REMOVE(type, types);
2957 			mtx_unlock(&ng_typelist_mtx);
2958 		}
2959 		splx(s);
2960 		break;
2961 
2962 	default:
2963 		if (type->mod_event != NULL)
2964 			error = (*type->mod_event)(mod, event, data);
2965 		else
2966 			error = 0;		/* XXX ? */
2967 		break;
2968 	}
2969 	return (error);
2970 }
2971 
2972 /*
2973  * Handle loading and unloading for this code.
2974  * The only thing we need to link into is the NETISR strucure.
2975  */
2976 static int
2977 ngb_mod_event(module_t mod, int event, void *data)
2978 {
2979 	int s, error = 0;
2980 
2981 	switch (event) {
2982 	case MOD_LOAD:
2983 		/* Register line discipline */
2984 		mtx_init(&ng_worklist_mtx, "ng_worklist", NULL, MTX_SPIN);
2985 		mtx_init(&ng_typelist_mtx, "netgraph types mutex", NULL, 0);
2986 		mtx_init(&ng_nodelist_mtx, "netgraph nodelist mutex", NULL, 0);
2987 		mtx_init(&ng_idhash_mtx, "netgraph idhash mutex", NULL, 0);
2988 		mtx_init(&ngq_mtx, "netgraph netisr mutex", NULL, 0);
2989 		s = splimp();
2990 		error = register_netisr(NETISR_NETGRAPH, ngintr);
2991 		splx(s);
2992 		break;
2993 	case MOD_UNLOAD:
2994 		/* You cant unload it because an interface may be using it.  */
2995 		error = EBUSY;
2996 		break;
2997 	default:
2998 		error = EOPNOTSUPP;
2999 		break;
3000 	}
3001 	return (error);
3002 }
3003 
3004 static moduledata_t netgraph_mod = {
3005 	"netgraph",
3006 	ngb_mod_event,
3007 	(NULL)
3008 };
3009 DECLARE_MODULE(netgraph, netgraph_mod, SI_SUB_DRIVERS, SI_ORDER_MIDDLE);
3010 SYSCTL_NODE(_net, OID_AUTO, graph, CTLFLAG_RW, 0, "netgraph Family");
3011 SYSCTL_INT(_net_graph, OID_AUTO, abi_version, CTLFLAG_RD, 0, NG_ABI_VERSION,"");
3012 SYSCTL_INT(_net_graph, OID_AUTO, msg_version, CTLFLAG_RD, 0, NG_VERSION, "");
3013 
3014 /************************************************************************
3015 			Queue element get/free routines
3016 ************************************************************************/
3017 
3018 
3019 static int			allocated;	/* number of items malloc'd */
3020 static int			maxalloc = 128;	/* limit the damage of a leak */
3021 static const int		ngqfreemax = 64;/* cache at most this many */
3022 static const int		ngqfreelow = 4; /* try malloc if free < this */
3023 static volatile int		ngqfreesize;	/* number of cached entries */
3024 #ifdef	NETGRAPH_DEBUG
3025 static TAILQ_HEAD(, ng_item) ng_itemlist = TAILQ_HEAD_INITIALIZER(ng_itemlist);
3026 #endif
3027 /*
3028  * Get a queue entry
3029  * This is usually called when a packet first enters netgraph.
3030  * By definition, this is usually from an interrupt, or from a user.
3031  * Users are not so important, but try be quick for the times that it's
3032  * an interrupt. Use atomic operations to cope with collisions
3033  * with interrupts and other processors. Assumes MALLOC is SMP safe.
3034  * XXX If reserve is low, we should try to get 2 from malloc as this
3035  * would indicate it often fails.
3036  */
3037 static item_p
3038 ng_getqblk(void)
3039 {
3040 	item_p item = NULL;
3041 
3042 	/*
3043 	 * Try get a cached queue block, or else allocate a new one
3044 	 * If we are less than our reserve, try malloc. If malloc
3045 	 * fails, then that's what the reserve is for...
3046 	 * Don't completely trust ngqfreesize, as it is subject
3047 	 * to races.. (it'll eventually catch up but may be out by one or two
3048 	 * for brief moments(under SMP or interrupts).
3049 	 * ngqfree is the final arbiter. We have our little reserve
3050 	 * because we use M_NOWAIT for malloc. This just helps us
3051 	 * avoid dropping packets while not increasing the time
3052 	 * we take to service the interrupt (on average) (I hope).
3053 	 */
3054 	for (;;) {
3055 		if ((ngqfreesize < ngqfreelow) || (ngqfree == NULL)) {
3056 			if (allocated < maxalloc) {  /* don't leak forever */
3057 				MALLOC(item, item_p ,
3058 				    sizeof(*item), M_NETGRAPH_ITEM,
3059 				    (M_NOWAIT | M_ZERO));
3060 				if (item) {
3061 #ifdef	NETGRAPH_DEBUG
3062 					TAILQ_INSERT_TAIL(&ng_itemlist,
3063 								item, all);
3064 #endif	/* NETGRAPH_DEBUG */
3065 					atomic_add_int(&allocated, 1);
3066 					break;
3067 				}
3068 			}
3069 		}
3070 
3071 		/*
3072 		 * We didn't or couldn't malloc.
3073 		 * try get one from our cache.
3074 		 * item must be NULL to get here.
3075 		 */
3076 		if ((item = ngqfree) != NULL) {
3077 			/*
3078 			 * Atomically try grab the first item
3079 			 * and put it's successor in its place.
3080 			 * If we fail, just try again.. someone else
3081 			 * beat us to this one or freed one.
3082 			 * Don't worry about races with ngqfreesize.
3083 			 * Close enough is good enough..
3084 			 */
3085 			if (atomic_cmpset_ptr(&ngqfree, item, item->el_next)) {
3086 				atomic_subtract_int(&ngqfreesize, 1);
3087 				item->el_flags &= ~NGQF_FREE;
3088 				break;
3089 			}
3090 			/*
3091 			 * something got there before we did.. try again
3092 			 * (go around the loop again)
3093 			 */
3094 			item = NULL;
3095 		} else {
3096 			/* We really ran out */
3097 			break;
3098 		}
3099 	}
3100 	return (item);
3101 }
3102 
3103 /*
3104  * Release a queue entry
3105  */
3106 void
3107 ng_free_item(item_p item)
3108 {
3109 
3110 	/*
3111 	 * The item may hold resources on it's own. We need to free
3112 	 * these before we can free the item. What they are depends upon
3113 	 * what kind of item it is. it is important that nodes zero
3114 	 * out pointers to resources that they remove from the item
3115 	 * or we release them again here.
3116 	 */
3117 	if (item->el_flags & NGQF_FREE) {
3118 		panic(" Freeing free queue item");
3119 	}
3120 	switch (item->el_flags & NGQF_TYPE) {
3121 	case NGQF_DATA:
3122 		/* If we have an mbuf and metadata still attached.. */
3123 		NG_FREE_M(_NGI_M(item));
3124 		NG_FREE_META(_NGI_META(item));
3125 		break;
3126 	case NGQF_MESG:
3127 		_NGI_RETADDR(item) = 0;
3128 		NG_FREE_MSG(_NGI_MSG(item));
3129 		break;
3130 	case NGQF_FN:
3131 		/* nothing to free really, */
3132 		_NGI_FN(item) = NULL;
3133 		_NGI_ARG1(item) = NULL;
3134 		_NGI_ARG2(item) = 0;
3135 	case NGQF_UNDEF:
3136 		break;
3137 	}
3138 	/* If we still have a node or hook referenced... */
3139 	_NGI_CLR_NODE(item);
3140 	_NGI_CLR_HOOK(item);
3141 	item->el_flags |= NGQF_FREE;
3142 
3143 	/*
3144 	 * We have freed any resources held by the item.
3145 	 * now we can free the item itself.
3146 	 */
3147 	if (ngqfreesize < ngqfreemax) { /* don't worry about races */
3148 		for (;;) {
3149 			item->el_next = ngqfree;
3150 			if (atomic_cmpset_ptr(&ngqfree, item->el_next, item)) {
3151 				break;
3152 			}
3153 		}
3154 		atomic_add_int(&ngqfreesize, 1);
3155 	} else {
3156 		/* This is the only place that should use this Macro */
3157 #ifdef	NETGRAPH_DEBUG
3158 		TAILQ_REMOVE(&ng_itemlist, item, all);
3159 #endif	/* NETGRAPH_DEBUG */
3160 		NG_FREE_ITEM_REAL(item);
3161 		atomic_subtract_int(&allocated, 1);
3162 	}
3163 }
3164 
3165 #ifdef	NETGRAPH_DEBUG
3166 void
3167 dumphook (hook_p hook, char *file, int line)
3168 {
3169 	printf("hook: name %s, %d refs, Last touched:\n",
3170 		_NG_HOOK_NAME(hook), hook->hk_refs);
3171 	printf("	Last active @ %s, line %d\n",
3172 		hook->lastfile, hook->lastline);
3173 	if (line) {
3174 		printf(" problem discovered at file %s, line %d\n", file, line);
3175 	}
3176 }
3177 
3178 void
3179 dumpnode(node_p node, char *file, int line)
3180 {
3181 	printf("node: ID [%x]: type '%s', %d hooks, flags 0x%x, %d refs, %s:\n",
3182 		_NG_NODE_ID(node), node->nd_type->name,
3183 		node->nd_numhooks, node->nd_flags,
3184 		node->nd_refs, node->nd_name);
3185 	printf("	Last active @ %s, line %d\n",
3186 		node->lastfile, node->lastline);
3187 	if (line) {
3188 		printf(" problem discovered at file %s, line %d\n", file, line);
3189 	}
3190 }
3191 
3192 void
3193 dumpitem(item_p item, char *file, int line)
3194 {
3195 	if (item->el_flags & NGQF_FREE) {
3196 		printf(" Free item, freed at %s, line %d\n",
3197 			item->lastfile, item->lastline);
3198 	} else {
3199 		printf(" ACTIVE item, last used at %s, line %d",
3200 			item->lastfile, item->lastline);
3201 		switch(item->el_flags & NGQF_TYPE) {
3202 		case NGQF_DATA:
3203 			printf(" - [data]\n");
3204 			break;
3205 		case NGQF_MESG:
3206 			printf(" - retaddr[%d]:\n", _NGI_RETADDR(item));
3207 			break;
3208 		case NGQF_FN:
3209 			printf(" - fn@%p (%p, %p, %p, %d (%x))\n",
3210 				item->body.fn.fn_fn,
3211 				NGI_NODE(item),
3212 				NGI_HOOK(item),
3213 				item->body.fn.fn_arg1,
3214 				item->body.fn.fn_arg2,
3215 				item->body.fn.fn_arg2);
3216 			break;
3217 		case NGQF_UNDEF:
3218 			printf(" - UNDEFINED!\n");
3219 		}
3220 	}
3221 	if (line) {
3222 		printf(" problem discovered at file %s, line %d\n", file, line);
3223 		if (NGI_NODE(item)) {
3224 			printf("node %p ([%x])\n",
3225 				NGI_NODE(item), ng_node2ID(NGI_NODE(item)));
3226 		}
3227 	}
3228 }
3229 
3230 static void
3231 ng_dumpitems(void)
3232 {
3233 	item_p item;
3234 	int i = 1;
3235 	TAILQ_FOREACH(item, &ng_itemlist, all) {
3236 		printf("[%d] ", i++);
3237 		dumpitem(item, NULL, 0);
3238 	}
3239 }
3240 
3241 static void
3242 ng_dumpnodes(void)
3243 {
3244 	node_p node;
3245 	int i = 1;
3246 	SLIST_FOREACH(node, &ng_allnodes, nd_all) {
3247 		printf("[%d] ", i++);
3248 		dumpnode(node, NULL, 0);
3249 	}
3250 }
3251 
3252 static void
3253 ng_dumphooks(void)
3254 {
3255 	hook_p hook;
3256 	int i = 1;
3257 	SLIST_FOREACH(hook, &ng_allhooks, hk_all) {
3258 		printf("[%d] ", i++);
3259 		dumphook(hook, NULL, 0);
3260 	}
3261 }
3262 
3263 static int
3264 sysctl_debug_ng_dump_items(SYSCTL_HANDLER_ARGS)
3265 {
3266 	int error;
3267 	int val;
3268 	int i;
3269 
3270 	val = allocated;
3271 	i = 1;
3272 	error = sysctl_handle_int(oidp, &val, sizeof(int), req);
3273 	if (error != 0 || req->newptr == NULL)
3274 		return (error);
3275 	if (val == 42) {
3276 		ng_dumpitems();
3277 		ng_dumpnodes();
3278 		ng_dumphooks();
3279 	}
3280 	return (0);
3281 }
3282 
3283 SYSCTL_PROC(_debug, OID_AUTO, ng_dump_items, CTLTYPE_INT | CTLFLAG_RW,
3284     0, sizeof(int), sysctl_debug_ng_dump_items, "I", "Number of allocated items");
3285 #endif	/* NETGRAPH_DEBUG */
3286 
3287 
3288 /***********************************************************************
3289 * Worklist routines
3290 **********************************************************************/
3291 /* NETISR thread enters here */
3292 /*
3293  * Pick a node off the list of nodes with work,
3294  * try get an item to process off it.
3295  * If there are no more, remove the node from the list.
3296  */
3297 static void
3298 ngintr(void)
3299 {
3300 	item_p item;
3301 	node_p  node = NULL;
3302 
3303 	for (;;) {
3304 		mtx_lock_spin(&ng_worklist_mtx);
3305 		node = TAILQ_FIRST(&ng_worklist);
3306 		if (!node) {
3307 			mtx_unlock_spin(&ng_worklist_mtx);
3308 			break;
3309 		}
3310 		node->nd_flags &= ~NG_WORKQ;
3311 		TAILQ_REMOVE(&ng_worklist, node, nd_work);
3312 		mtx_unlock_spin(&ng_worklist_mtx);
3313 		/*
3314 		 * We have the node. We also take over the reference
3315 		 * that the list had on it.
3316 		 * Now process as much as you can, until it won't
3317 		 * let you have another item off the queue.
3318 		 * All this time, keep the reference
3319 		 * that lets us be sure that the node still exists.
3320 		 * Let the reference go at the last minute.
3321 		 * ng_dequeue will put us back on the worklist
3322 		 * if there is more too do. This may be of use if there
3323 		 * are Multiple Processors and multiple Net threads in the
3324 		 * future.
3325 		 */
3326 		for (;;) {
3327 			mtx_lock_spin(&node->nd_input_queue.q_mtx);
3328 			item = ng_dequeue(&node->nd_input_queue);
3329 			if (item == NULL) {
3330 				mtx_unlock_spin(&node->nd_input_queue.q_mtx);
3331 				break; /* go look for another node */
3332 			} else {
3333 				mtx_unlock_spin(&node->nd_input_queue.q_mtx);
3334 				NGI_GET_NODE(item, node); /* zaps stored node */
3335 				ng_apply_item(node, item);
3336 				NG_NODE_UNREF(node);
3337 			}
3338 		}
3339 		NG_NODE_UNREF(node);
3340 	}
3341 }
3342 
3343 static void
3344 ng_worklist_remove(node_p node)
3345 {
3346 	mtx_lock_spin(&ng_worklist_mtx);
3347 	if (node->nd_flags & NG_WORKQ) {
3348 		node->nd_flags &= ~NG_WORKQ;
3349 		TAILQ_REMOVE(&ng_worklist, node, nd_work);
3350 		mtx_unlock_spin(&ng_worklist_mtx);
3351 		NG_NODE_UNREF(node);
3352 	} else {
3353 		mtx_unlock_spin(&ng_worklist_mtx);
3354 	}
3355 }
3356 
3357 /*
3358  * XXX
3359  * It's posible that a debugging NG_NODE_REF may need
3360  * to be outside the mutex zone
3361  */
3362 static void
3363 ng_setisr(node_p node)
3364 {
3365 	mtx_lock_spin(&ng_worklist_mtx);
3366 	if ((node->nd_flags & NG_WORKQ) == 0) {
3367 		/*
3368 		 * If we are not already on the work queue,
3369 		 * then put us on.
3370 		 */
3371 		node->nd_flags |= NG_WORKQ;
3372 		TAILQ_INSERT_TAIL(&ng_worklist, node, nd_work);
3373 		NG_NODE_REF(node); /* XXX fafe in mutex? */
3374 	}
3375 	mtx_unlock_spin(&ng_worklist_mtx);
3376 	schednetisr(NETISR_NETGRAPH);
3377 }
3378 
3379 
3380 /***********************************************************************
3381 * Externally useable functions to set up a queue item ready for sending
3382 ***********************************************************************/
3383 
3384 #ifdef	NETGRAPH_DEBUG
3385 #define	ITEM_DEBUG_CHECKS						\
3386 	do {								\
3387 		if (NGI_NODE(item) ) {					\
3388 			printf("item already has node");		\
3389 			Debugger("has node");				\
3390 			NGI_CLR_NODE(item);				\
3391 		}							\
3392 		if (NGI_HOOK(item) ) {					\
3393 			printf("item already has hook");		\
3394 			Debugger("has hook");				\
3395 			NGI_CLR_HOOK(item);				\
3396 		}							\
3397 	} while (0)
3398 #else
3399 #define ITEM_DEBUG_CHECKS
3400 #endif
3401 
3402 /*
3403  * Put elements into the item.
3404  * Hook and node references will be removed when the item is dequeued.
3405  * (or equivalent)
3406  * (XXX) Unsafe because no reference held by peer on remote node.
3407  * remote node might go away in this timescale.
3408  * We know the hooks can't go away because that would require getting
3409  * a writer item on both nodes and we must have at least a  reader
3410  * here to eb able to do this.
3411  * Note that the hook loaded is the REMOTE hook.
3412  *
3413  * This is possibly in the critical path for new data.
3414  */
3415 item_p
3416 ng_package_data(struct mbuf *m, meta_p meta)
3417 {
3418 	item_p item;
3419 
3420 	if ((item = ng_getqblk()) == NULL) {
3421 		NG_FREE_M(m);
3422 		NG_FREE_META(meta);
3423 		return (NULL);
3424 	}
3425 	ITEM_DEBUG_CHECKS;
3426 	item->el_flags = NGQF_DATA;
3427 	item->el_next = NULL;
3428 	NGI_M(item) = m;
3429 	NGI_META(item) = meta;
3430 	return (item);
3431 }
3432 
3433 /*
3434  * Allocate a queue item and put items into it..
3435  * Evaluate the address as this will be needed to queue it and
3436  * to work out what some of the fields should be.
3437  * Hook and node references will be removed when the item is dequeued.
3438  * (or equivalent)
3439  */
3440 item_p
3441 ng_package_msg(struct ng_mesg *msg)
3442 {
3443 	item_p item;
3444 
3445 	if ((item = ng_getqblk()) == NULL) {
3446 		NG_FREE_MSG(msg);
3447 		return (NULL);
3448 	}
3449 	ITEM_DEBUG_CHECKS;
3450 	item->el_flags = NGQF_MESG;
3451 	item->el_next = NULL;
3452 	/*
3453 	 * Set the current lasthook into the queue item
3454 	 */
3455 	NGI_MSG(item) = msg;
3456 	NGI_RETADDR(item) = 0;
3457 	return (item);
3458 }
3459 
3460 
3461 
3462 #define SET_RETADDR(item, here, retaddr)				\
3463 	do {	/* Data or fn items don't have retaddrs */		\
3464 		if ((item->el_flags & NGQF_TYPE) == NGQF_MESG) {	\
3465 			if (retaddr) {					\
3466 				NGI_RETADDR(item) = retaddr;		\
3467 			} else {					\
3468 				/*					\
3469 				 * The old return address should be ok.	\
3470 				 * If there isn't one, use the address	\
3471 				 * here.				\
3472 				 */					\
3473 				if (NGI_RETADDR(item) == 0) {		\
3474 					NGI_RETADDR(item)		\
3475 						= ng_node2ID(here);	\
3476 				}					\
3477 			}						\
3478 		}							\
3479 	} while (0)
3480 
3481 int
3482 ng_address_hook(node_p here, item_p item, hook_p hook, ng_ID_t retaddr)
3483 {
3484 	hook_p peer;
3485 	node_p peernode;
3486 	ITEM_DEBUG_CHECKS;
3487 	/*
3488 	 * Quick sanity check..
3489 	 * Since a hook holds a reference on it's node, once we know
3490 	 * that the peer is still connected (even if invalid,) we know
3491 	 * that the peer node is present, though maybe invalid.
3492 	 */
3493 	if ((hook == NULL)
3494 	|| NG_HOOK_NOT_VALID(hook)
3495 	|| (NG_HOOK_PEER(hook) == NULL)
3496 	|| NG_HOOK_NOT_VALID(NG_HOOK_PEER(hook))
3497 	|| NG_NODE_NOT_VALID(NG_PEER_NODE(hook))) {
3498 		NG_FREE_ITEM(item);
3499 		TRAP_ERROR();
3500 		return (ENETDOWN);
3501 	}
3502 
3503 	/*
3504 	 * Transfer our interest to the other (peer) end.
3505 	 */
3506 	peer = NG_HOOK_PEER(hook);
3507 	NG_HOOK_REF(peer);
3508 	NGI_SET_HOOK(item, peer);
3509 	peernode = NG_PEER_NODE(hook);
3510 	NG_NODE_REF(peernode);
3511 	NGI_SET_NODE(item, peernode);
3512 	SET_RETADDR(item, here, retaddr);
3513 	return (0);
3514 }
3515 
3516 int
3517 ng_address_path(node_p here, item_p item, char *address, ng_ID_t retaddr)
3518 {
3519 	node_p  dest = NULL;
3520 	hook_p	hook = NULL;
3521 	int     error;
3522 
3523 	ITEM_DEBUG_CHECKS;
3524 	/*
3525 	 * Note that ng_path2noderef increments the reference count
3526 	 * on the node for us if it finds one. So we don't have to.
3527 	 */
3528 	error = ng_path2noderef(here, address, &dest, &hook);
3529 	if (error) {
3530 		NG_FREE_ITEM(item);
3531 		return (error);
3532 	}
3533 	NGI_SET_NODE(item, dest);
3534 	if ( hook) {
3535 		NG_HOOK_REF(hook);	/* don't let it go while on the queue */
3536 		NGI_SET_HOOK(item, hook);
3537 	}
3538 	SET_RETADDR(item, here, retaddr);
3539 	return (0);
3540 }
3541 
3542 int
3543 ng_address_ID(node_p here, item_p item, ng_ID_t ID, ng_ID_t retaddr)
3544 {
3545 	node_p dest;
3546 
3547 	ITEM_DEBUG_CHECKS;
3548 	/*
3549 	 * Find the target node.
3550 	 */
3551 	dest = ng_ID2noderef(ID); /* GETS REFERENCE! */
3552 	if (dest == NULL) {
3553 		NG_FREE_ITEM(item);
3554 		TRAP_ERROR();
3555 		return(EINVAL);
3556 	}
3557 	/* Fill out the contents */
3558 	item->el_flags = NGQF_MESG;
3559 	item->el_next = NULL;
3560 	NGI_SET_NODE(item, dest);
3561 	NGI_CLR_HOOK(item);
3562 	SET_RETADDR(item, here, retaddr);
3563 	return (0);
3564 }
3565 
3566 /*
3567  * special case to send a message to self (e.g. destroy node)
3568  * Possibly indicate an arrival hook too.
3569  * Useful for removing that hook :-)
3570  */
3571 item_p
3572 ng_package_msg_self(node_p here, hook_p hook, struct ng_mesg *msg)
3573 {
3574 	item_p item;
3575 
3576 	/*
3577 	 * Find the target node.
3578 	 * If there is a HOOK argument, then use that in preference
3579 	 * to the address.
3580 	 */
3581 	if ((item = ng_getqblk()) == NULL) {
3582 		NG_FREE_MSG(msg);
3583 		return (NULL);
3584 	}
3585 
3586 	/* Fill out the contents */
3587 	item->el_flags = NGQF_MESG;
3588 	item->el_next = NULL;
3589 	NG_NODE_REF(here);
3590 	NGI_SET_NODE(item, here);
3591 	if (hook) {
3592 		NG_HOOK_REF(hook);
3593 		NGI_SET_HOOK(item, hook);
3594 	}
3595 	NGI_MSG(item) = msg;
3596 	NGI_RETADDR(item) = ng_node2ID(here);
3597 	return (item);
3598 }
3599 
3600 int
3601 ng_send_fn(node_p node, hook_p hook, ng_item_fn *fn, void * arg1, int arg2)
3602 {
3603 	item_p item;
3604 
3605 	if ((item = ng_getqblk()) == NULL) {
3606 		return (ENOMEM);
3607 	}
3608 	item->el_flags = NGQF_FN | NGQF_WRITER;
3609 	NG_NODE_REF(node); /* and one for the item */
3610 	NGI_SET_NODE(item, node);
3611 	if (hook) {
3612 		NG_HOOK_REF(hook);
3613 		NGI_SET_HOOK(item, hook);
3614 	}
3615 	NGI_FN(item) = fn;
3616 	NGI_ARG1(item) = arg1;
3617 	NGI_ARG2(item) = arg2;
3618 	return(ng_snd_item(item, 0));
3619 }
3620 
3621 /*
3622  * Official timeout routines for Netgraph nodes.
3623  */
3624 static void
3625 ng_timeout_trapoline(void *arg)
3626 {
3627 	item_p item = arg;
3628 
3629 	ng_snd_item(item, 0);
3630 }
3631 
3632 
3633 struct callout_handle
3634 ng_timeout(node_p node, hook_p hook, int ticks,
3635     ng_item_fn *fn, void * arg1, int arg2)
3636 {
3637 	item_p item;
3638 
3639 	if ((item = ng_getqblk()) == NULL) {
3640 		struct callout_handle handle;
3641 		handle.callout = NULL;
3642 		return (handle);
3643 	}
3644 	item->el_flags = NGQF_FN | NGQF_WRITER;
3645 	NG_NODE_REF(node);		/* and one for the item */
3646 	NGI_SET_NODE(item, node);
3647 	if (hook) {
3648 		NG_HOOK_REF(hook);
3649 		NGI_SET_HOOK(item, hook);
3650 	}
3651 	NGI_FN(item) = fn;
3652 	NGI_ARG1(item) = arg1;
3653 	NGI_ARG2(item) = arg2;
3654 	return (timeout(&ng_timeout_trapoline, item, ticks));
3655 }
3656 
3657 /* A special modified version of untimeout() */
3658 int
3659 ng_untimeout(struct callout_handle handle, node_p node)
3660 {
3661 	item_p item;
3662 
3663 	if (handle.callout == NULL)
3664 		return (0);
3665 	mtx_lock_spin(&callout_lock);
3666 	item = handle.callout->c_arg; /* should be an official way to do this */
3667 	if ((handle.callout->c_func == &ng_timeout_trapoline) &&
3668 	    (NGI_NODE(item) == node) &&
3669 	    (callout_stop(handle.callout))) {
3670 		/*
3671 		 * We successfully removed it from the queue before it ran
3672 		 * So now we need to unreference everything that was
3673 		 * given extra references. (NG_FREE_ITEM does this).
3674 		 */
3675 		mtx_unlock_spin(&callout_lock);
3676 		NG_FREE_ITEM(item);
3677 		return (1);
3678 	}
3679 	mtx_unlock_spin(&callout_lock);
3680 	return (0);
3681 }
3682 
3683 /*
3684  * Set the address, if none given, give the node here.
3685  */
3686 void
3687 ng_replace_retaddr(node_p here, item_p item, ng_ID_t retaddr)
3688 {
3689 	if (retaddr) {
3690 		NGI_RETADDR(item) = retaddr;
3691 	} else {
3692 		/*
3693 		 * The old return address should be ok.
3694 		 * If there isn't one, use the address here.
3695 		 */
3696 		NGI_RETADDR(item) = ng_node2ID(here);
3697 	}
3698 }
3699 
3700 #define TESTING
3701 #ifdef TESTING
3702 /* just test all the macros */
3703 void
3704 ng_macro_test(item_p item);
3705 void
3706 ng_macro_test(item_p item)
3707 {
3708 	node_p node = NULL;
3709 	hook_p hook = NULL;
3710 	struct mbuf *m;
3711 	meta_p meta;
3712 	struct ng_mesg *msg;
3713 	ng_ID_t retaddr;
3714 	int	error;
3715 
3716 	NGI_GET_M(item, m);
3717 	NGI_GET_META(item, meta);
3718 	NGI_GET_MSG(item, msg);
3719 	retaddr = NGI_RETADDR(item);
3720 	NG_SEND_DATA(error, hook, m, meta);
3721 	NG_SEND_DATA_ONLY(error, hook, m);
3722 	NG_FWD_NEW_DATA(error, item, hook, m);
3723 	NG_FWD_ITEM_HOOK(error, item, hook);
3724 	NG_SEND_MSG_HOOK(error, node, msg, hook, retaddr);
3725 	NG_SEND_MSG_ID(error, node, msg, retaddr, retaddr);
3726 	NG_SEND_MSG_PATH(error, node, msg, ".:", retaddr);
3727 	NG_FWD_MSG_HOOK(error, node, item, hook, retaddr);
3728 }
3729 #endif /* TESTING */
3730 
3731