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