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