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/epoch.h>
59#include <sys/queue.h>
60#include <sys/refcount.h>
61#include <sys/rwlock.h>
62#include <sys/smp.h>
63#include <sys/sysctl.h>
64#include <sys/syslog.h>
65#include <sys/unistd.h>
66#include <machine/cpu.h>
67#include <vm/uma.h>
68
69#include <net/netisr.h>
70#include <net/vnet.h>
71
72#include <netgraph/ng_message.h>
73#include <netgraph/netgraph.h>
74#include <netgraph/ng_parse.h>
75
76MODULE_VERSION(netgraph, NG_ABI_VERSION);
77
78/* Mutex to protect topology events. */
79static struct rwlock	ng_topo_lock;
80#define	TOPOLOGY_RLOCK()	rw_rlock(&ng_topo_lock)
81#define	TOPOLOGY_RUNLOCK()	rw_runlock(&ng_topo_lock)
82#define	TOPOLOGY_WLOCK()	rw_wlock(&ng_topo_lock)
83#define	TOPOLOGY_WUNLOCK()	rw_wunlock(&ng_topo_lock)
84#define	TOPOLOGY_NOTOWNED()	rw_assert(&ng_topo_lock, RA_UNLOCKED)
85
86#ifdef	NETGRAPH_DEBUG
87static struct mtx	ng_nodelist_mtx; /* protects global node/hook lists */
88static struct mtx	ngq_mtx;	/* protects the queue item list */
89
90static SLIST_HEAD(, ng_node) ng_allnodes;
91static LIST_HEAD(, ng_node) ng_freenodes; /* in debug, we never free() them */
92static SLIST_HEAD(, ng_hook) ng_allhooks;
93static LIST_HEAD(, ng_hook) ng_freehooks; /* in debug, we never free() them */
94
95static void ng_dumpitems(void);
96static void ng_dumpnodes(void);
97static void ng_dumphooks(void);
98
99#endif	/* NETGRAPH_DEBUG */
100/*
101 * DEAD versions of the structures.
102 * In order to avoid races, it is sometimes necessary to point
103 * at SOMETHING even though theoretically, the current entity is
104 * INVALID. Use these to avoid these races.
105 */
106struct ng_type ng_deadtype = {
107	NG_ABI_VERSION,
108	"dead",
109	NULL,	/* modevent */
110	NULL,	/* constructor */
111	NULL,	/* rcvmsg */
112	NULL,	/* shutdown */
113	NULL,	/* newhook */
114	NULL,	/* findhook */
115	NULL,	/* connect */
116	NULL,	/* rcvdata */
117	NULL,	/* disconnect */
118	NULL, 	/* cmdlist */
119};
120
121struct ng_node ng_deadnode = {
122	"dead",
123	&ng_deadtype,
124	NGF_INVALID,
125	0,	/* numhooks */
126	NULL,	/* private */
127	0,	/* ID */
128	LIST_HEAD_INITIALIZER(ng_deadnode.nd_hooks),
129	{},	/* all_nodes list entry */
130	{},	/* id hashtable list entry */
131	{	0,
132		0,
133		{}, /* should never use! (should hang) */
134		{}, /* workqueue entry */
135		STAILQ_HEAD_INITIALIZER(ng_deadnode.nd_input_queue.queue),
136	},
137	1,	/* refs */
138	NULL,	/* vnet */
139#ifdef	NETGRAPH_DEBUG
140	ND_MAGIC,
141	__FILE__,
142	__LINE__,
143	{NULL}
144#endif	/* NETGRAPH_DEBUG */
145};
146
147struct ng_hook ng_deadhook = {
148	"dead",
149	NULL,		/* private */
150	HK_INVALID | HK_DEAD,
151	0,		/* undefined data link type */
152	&ng_deadhook,	/* Peer is self */
153	&ng_deadnode,	/* attached to deadnode */
154	{},		/* hooks list */
155	NULL,		/* override rcvmsg() */
156	NULL,		/* override rcvdata() */
157	1,		/* refs always >= 1 */
158#ifdef	NETGRAPH_DEBUG
159	HK_MAGIC,
160	__FILE__,
161	__LINE__,
162	{NULL}
163#endif	/* NETGRAPH_DEBUG */
164};
165
166/*
167 * END DEAD STRUCTURES
168 */
169/* List nodes with unallocated work */
170static STAILQ_HEAD(, ng_node) ng_worklist = STAILQ_HEAD_INITIALIZER(ng_worklist);
171static struct mtx	ng_worklist_mtx;   /* MUST LOCK NODE FIRST */
172
173/* List of installed types */
174static LIST_HEAD(, ng_type) ng_typelist;
175static struct rwlock	ng_typelist_lock;
176#define	TYPELIST_RLOCK()	rw_rlock(&ng_typelist_lock)
177#define	TYPELIST_RUNLOCK()	rw_runlock(&ng_typelist_lock)
178#define	TYPELIST_WLOCK()	rw_wlock(&ng_typelist_lock)
179#define	TYPELIST_WUNLOCK()	rw_wunlock(&ng_typelist_lock)
180
181/* Hash related definitions. */
182LIST_HEAD(nodehash, ng_node);
183VNET_DEFINE_STATIC(struct nodehash *, ng_ID_hash);
184VNET_DEFINE_STATIC(u_long, ng_ID_hmask);
185VNET_DEFINE_STATIC(u_long, ng_nodes);
186VNET_DEFINE_STATIC(struct nodehash *, ng_name_hash);
187VNET_DEFINE_STATIC(u_long, ng_name_hmask);
188VNET_DEFINE_STATIC(u_long, ng_named_nodes);
189#define	V_ng_ID_hash		VNET(ng_ID_hash)
190#define	V_ng_ID_hmask		VNET(ng_ID_hmask)
191#define	V_ng_nodes		VNET(ng_nodes)
192#define	V_ng_name_hash		VNET(ng_name_hash)
193#define	V_ng_name_hmask		VNET(ng_name_hmask)
194#define	V_ng_named_nodes	VNET(ng_named_nodes)
195
196static struct rwlock	ng_idhash_lock;
197#define	IDHASH_RLOCK()		rw_rlock(&ng_idhash_lock)
198#define	IDHASH_RUNLOCK()	rw_runlock(&ng_idhash_lock)
199#define	IDHASH_WLOCK()		rw_wlock(&ng_idhash_lock)
200#define	IDHASH_WUNLOCK()	rw_wunlock(&ng_idhash_lock)
201
202/* Method to find a node.. used twice so do it here */
203#define NG_IDHASH_FN(ID) ((ID) % (V_ng_ID_hmask + 1))
204#define NG_IDHASH_FIND(ID, node)					\
205	do { 								\
206		rw_assert(&ng_idhash_lock, RA_LOCKED);			\
207		LIST_FOREACH(node, &V_ng_ID_hash[NG_IDHASH_FN(ID)],	\
208						nd_idnodes) {		\
209			if (NG_NODE_IS_VALID(node)			\
210			&& (NG_NODE_ID(node) == ID)) {			\
211				break;					\
212			}						\
213		}							\
214	} while (0)
215
216static struct rwlock	ng_namehash_lock;
217#define	NAMEHASH_RLOCK()	rw_rlock(&ng_namehash_lock)
218#define	NAMEHASH_RUNLOCK()	rw_runlock(&ng_namehash_lock)
219#define	NAMEHASH_WLOCK()	rw_wlock(&ng_namehash_lock)
220#define	NAMEHASH_WUNLOCK()	rw_wunlock(&ng_namehash_lock)
221
222/* Internal functions */
223static int	ng_add_hook(node_p node, const char *name, hook_p * hookp);
224static int	ng_generic_msg(node_p here, item_p item, hook_p lasthook);
225static ng_ID_t	ng_decodeidname(const char *name);
226static int	ngb_mod_event(module_t mod, int event, void *data);
227static void	ng_worklist_add(node_p node);
228static void	ngthread(void *);
229static int	ng_apply_item(node_p node, item_p item, int rw);
230static void	ng_flush_input_queue(node_p node);
231static node_p	ng_ID2noderef(ng_ID_t ID);
232static int	ng_con_nodes(item_p item, node_p node, const char *name,
233		    node_p node2, const char *name2);
234static int	ng_con_part2(node_p node, item_p item, hook_p hook);
235static int	ng_con_part3(node_p node, item_p item, hook_p hook);
236static int	ng_mkpeer(node_p node, const char *name, const char *name2,
237		    char *type);
238static void	ng_name_rehash(void);
239static void	ng_ID_rehash(void);
240
241/* Imported, these used to be externally visible, some may go back. */
242void	ng_destroy_hook(hook_p hook);
243int	ng_path2noderef(node_p here, const char *path,
244	node_p *dest, hook_p *lasthook);
245int	ng_make_node(const char *type, node_p *nodepp);
246int	ng_path_parse(char *addr, char **node, char **path, char **hook);
247void	ng_rmnode(node_p node, hook_p dummy1, void *dummy2, int dummy3);
248void	ng_unname(node_p node);
249
250/* Our own netgraph malloc type */
251MALLOC_DEFINE(M_NETGRAPH, "netgraph", "netgraph structures and ctrl messages");
252MALLOC_DEFINE(M_NETGRAPH_MSG, "netgraph_msg", "netgraph name storage");
253static MALLOC_DEFINE(M_NETGRAPH_HOOK, "netgraph_hook",
254    "netgraph hook structures");
255static MALLOC_DEFINE(M_NETGRAPH_NODE, "netgraph_node",
256    "netgraph node structures");
257static MALLOC_DEFINE(M_NETGRAPH_ITEM, "netgraph_item",
258    "netgraph item structures");
259
260/* Should not be visible outside this file */
261
262#define _NG_ALLOC_HOOK(hook) \
263	hook = malloc(sizeof(*hook), M_NETGRAPH_HOOK, M_NOWAIT | M_ZERO)
264#define _NG_ALLOC_NODE(node) \
265	node = malloc(sizeof(*node), M_NETGRAPH_NODE, M_NOWAIT | M_ZERO)
266
267#define	NG_QUEUE_LOCK_INIT(n)			\
268	mtx_init(&(n)->q_mtx, "ng_node", NULL, MTX_DEF)
269#define	NG_QUEUE_LOCK(n)			\
270	mtx_lock(&(n)->q_mtx)
271#define	NG_QUEUE_UNLOCK(n)			\
272	mtx_unlock(&(n)->q_mtx)
273#define	NG_WORKLIST_LOCK_INIT()			\
274	mtx_init(&ng_worklist_mtx, "ng_worklist", NULL, MTX_DEF)
275#define	NG_WORKLIST_LOCK()			\
276	mtx_lock(&ng_worklist_mtx)
277#define	NG_WORKLIST_UNLOCK()			\
278	mtx_unlock(&ng_worklist_mtx)
279#define	NG_WORKLIST_SLEEP()			\
280	mtx_sleep(&ng_worklist, &ng_worklist_mtx, PI_NET, "sleep", 0)
281#define	NG_WORKLIST_WAKEUP()			\
282	wakeup_one(&ng_worklist)
283
284#ifdef NETGRAPH_DEBUG /*----------------------------------------------*/
285/*
286 * In debug mode:
287 * In an attempt to help track reference count screwups
288 * we do not free objects back to the malloc system, but keep them
289 * in a local cache where we can examine them and keep information safely
290 * after they have been freed.
291 * We use this scheme for nodes and hooks, and to some extent for items.
292 */
293static __inline hook_p
294ng_alloc_hook(void)
295{
296	hook_p hook;
297	SLIST_ENTRY(ng_hook) temp;
298	mtx_lock(&ng_nodelist_mtx);
299	hook = LIST_FIRST(&ng_freehooks);
300	if (hook) {
301		LIST_REMOVE(hook, hk_hooks);
302		bcopy(&hook->hk_all, &temp, sizeof(temp));
303		bzero(hook, sizeof(struct ng_hook));
304		bcopy(&temp, &hook->hk_all, sizeof(temp));
305		mtx_unlock(&ng_nodelist_mtx);
306		hook->hk_magic = HK_MAGIC;
307	} else {
308		mtx_unlock(&ng_nodelist_mtx);
309		_NG_ALLOC_HOOK(hook);
310		if (hook) {
311			hook->hk_magic = HK_MAGIC;
312			mtx_lock(&ng_nodelist_mtx);
313			SLIST_INSERT_HEAD(&ng_allhooks, hook, hk_all);
314			mtx_unlock(&ng_nodelist_mtx);
315		}
316	}
317	return (hook);
318}
319
320static __inline node_p
321ng_alloc_node(void)
322{
323	node_p node;
324	SLIST_ENTRY(ng_node) temp;
325	mtx_lock(&ng_nodelist_mtx);
326	node = LIST_FIRST(&ng_freenodes);
327	if (node) {
328		LIST_REMOVE(node, nd_nodes);
329		bcopy(&node->nd_all, &temp, sizeof(temp));
330		bzero(node, sizeof(struct ng_node));
331		bcopy(&temp, &node->nd_all, sizeof(temp));
332		mtx_unlock(&ng_nodelist_mtx);
333		node->nd_magic = ND_MAGIC;
334	} else {
335		mtx_unlock(&ng_nodelist_mtx);
336		_NG_ALLOC_NODE(node);
337		if (node) {
338			node->nd_magic = ND_MAGIC;
339			mtx_lock(&ng_nodelist_mtx);
340			SLIST_INSERT_HEAD(&ng_allnodes, node, nd_all);
341			mtx_unlock(&ng_nodelist_mtx);
342		}
343	}
344	return (node);
345}
346
347#define NG_ALLOC_HOOK(hook) do { (hook) = ng_alloc_hook(); } while (0)
348#define NG_ALLOC_NODE(node) do { (node) = ng_alloc_node(); } while (0)
349
350#define NG_FREE_HOOK(hook)						\
351	do {								\
352		mtx_lock(&ng_nodelist_mtx);				\
353		LIST_INSERT_HEAD(&ng_freehooks, hook, hk_hooks);	\
354		hook->hk_magic = 0;					\
355		mtx_unlock(&ng_nodelist_mtx);				\
356	} while (0)
357
358#define NG_FREE_NODE(node)						\
359	do {								\
360		mtx_lock(&ng_nodelist_mtx);				\
361		LIST_INSERT_HEAD(&ng_freenodes, node, nd_nodes);	\
362		node->nd_magic = 0;					\
363		mtx_unlock(&ng_nodelist_mtx);				\
364	} while (0)
365
366#else /* NETGRAPH_DEBUG */ /*----------------------------------------------*/
367
368#define NG_ALLOC_HOOK(hook) _NG_ALLOC_HOOK(hook)
369#define NG_ALLOC_NODE(node) _NG_ALLOC_NODE(node)
370
371#define NG_FREE_HOOK(hook) do { free((hook), M_NETGRAPH_HOOK); } while (0)
372#define NG_FREE_NODE(node) do { free((node), M_NETGRAPH_NODE); } while (0)
373
374#endif /* NETGRAPH_DEBUG */ /*----------------------------------------------*/
375
376/* Set this to kdb_enter("X") to catch all errors as they occur */
377#ifndef TRAP_ERROR
378#define TRAP_ERROR()
379#endif
380
381VNET_DEFINE_STATIC(ng_ID_t, nextID) = 1;
382#define	V_nextID			VNET(nextID)
383
384#ifdef INVARIANTS
385#define CHECK_DATA_MBUF(m)	do {					\
386		struct mbuf *n;						\
387		int total;						\
388									\
389		M_ASSERTPKTHDR(m);					\
390		for (total = 0, n = (m); n != NULL; n = n->m_next) {	\
391			total += n->m_len;				\
392			if (n->m_nextpkt != NULL)			\
393				panic("%s: m_nextpkt", __func__);	\
394		}							\
395									\
396		if ((m)->m_pkthdr.len != total) {			\
397			panic("%s: %d != %d",				\
398			    __func__, (m)->m_pkthdr.len, total);	\
399		}							\
400	} while (0)
401#else
402#define CHECK_DATA_MBUF(m)
403#endif
404
405#define ERROUT(x)	do { error = (x); goto done; } while (0)
406
407/************************************************************************
408	Parse type definitions for generic messages
409************************************************************************/
410
411/* Handy structure parse type defining macro */
412#define DEFINE_PARSE_STRUCT_TYPE(lo, up, args)				\
413static const struct ng_parse_struct_field				\
414	ng_ ## lo ## _type_fields[] = NG_GENERIC_ ## up ## _INFO args;	\
415static const struct ng_parse_type ng_generic_ ## lo ## _type = {	\
416	&ng_parse_struct_type,						\
417	&ng_ ## lo ## _type_fields					\
418}
419
420DEFINE_PARSE_STRUCT_TYPE(mkpeer, MKPEER, ());
421DEFINE_PARSE_STRUCT_TYPE(connect, CONNECT, ());
422DEFINE_PARSE_STRUCT_TYPE(name, NAME, ());
423DEFINE_PARSE_STRUCT_TYPE(rmhook, RMHOOK, ());
424DEFINE_PARSE_STRUCT_TYPE(nodeinfo, NODEINFO, ());
425DEFINE_PARSE_STRUCT_TYPE(typeinfo, TYPEINFO, ());
426DEFINE_PARSE_STRUCT_TYPE(linkinfo, LINKINFO, (&ng_generic_nodeinfo_type));
427
428/* Get length of an array when the length is stored as a 32 bit
429   value immediately preceding the array -- as with struct namelist
430   and struct typelist. */
431static int
432ng_generic_list_getLength(const struct ng_parse_type *type,
433	const u_char *start, const u_char *buf)
434{
435	return *((const u_int32_t *)(buf - 4));
436}
437
438/* Get length of the array of struct linkinfo inside a struct hooklist */
439static int
440ng_generic_linkinfo_getLength(const struct ng_parse_type *type,
441	const u_char *start, const u_char *buf)
442{
443	const struct hooklist *hl = (const struct hooklist *)start;
444
445	return hl->nodeinfo.hooks;
446}
447
448/* Array type for a variable length array of struct namelist */
449static const struct ng_parse_array_info ng_nodeinfoarray_type_info = {
450	&ng_generic_nodeinfo_type,
451	&ng_generic_list_getLength
452};
453static const struct ng_parse_type ng_generic_nodeinfoarray_type = {
454	&ng_parse_array_type,
455	&ng_nodeinfoarray_type_info
456};
457
458/* Array type for a variable length array of struct typelist */
459static const struct ng_parse_array_info ng_typeinfoarray_type_info = {
460	&ng_generic_typeinfo_type,
461	&ng_generic_list_getLength
462};
463static const struct ng_parse_type ng_generic_typeinfoarray_type = {
464	&ng_parse_array_type,
465	&ng_typeinfoarray_type_info
466};
467
468/* Array type for array of struct linkinfo in struct hooklist */
469static const struct ng_parse_array_info ng_generic_linkinfo_array_type_info = {
470	&ng_generic_linkinfo_type,
471	&ng_generic_linkinfo_getLength
472};
473static const struct ng_parse_type ng_generic_linkinfo_array_type = {
474	&ng_parse_array_type,
475	&ng_generic_linkinfo_array_type_info
476};
477
478DEFINE_PARSE_STRUCT_TYPE(typelist, TYPELIST, (&ng_generic_typeinfoarray_type));
479DEFINE_PARSE_STRUCT_TYPE(hooklist, HOOKLIST,
480	(&ng_generic_nodeinfo_type, &ng_generic_linkinfo_array_type));
481DEFINE_PARSE_STRUCT_TYPE(listnodes, LISTNODES,
482	(&ng_generic_nodeinfoarray_type));
483
484/* List of commands and how to convert arguments to/from ASCII */
485static const struct ng_cmdlist ng_generic_cmds[] = {
486	{
487	  NGM_GENERIC_COOKIE,
488	  NGM_SHUTDOWN,
489	  "shutdown",
490	  NULL,
491	  NULL
492	},
493	{
494	  NGM_GENERIC_COOKIE,
495	  NGM_MKPEER,
496	  "mkpeer",
497	  &ng_generic_mkpeer_type,
498	  NULL
499	},
500	{
501	  NGM_GENERIC_COOKIE,
502	  NGM_CONNECT,
503	  "connect",
504	  &ng_generic_connect_type,
505	  NULL
506	},
507	{
508	  NGM_GENERIC_COOKIE,
509	  NGM_NAME,
510	  "name",
511	  &ng_generic_name_type,
512	  NULL
513	},
514	{
515	  NGM_GENERIC_COOKIE,
516	  NGM_RMHOOK,
517	  "rmhook",
518	  &ng_generic_rmhook_type,
519	  NULL
520	},
521	{
522	  NGM_GENERIC_COOKIE,
523	  NGM_NODEINFO,
524	  "nodeinfo",
525	  NULL,
526	  &ng_generic_nodeinfo_type
527	},
528	{
529	  NGM_GENERIC_COOKIE,
530	  NGM_LISTHOOKS,
531	  "listhooks",
532	  NULL,
533	  &ng_generic_hooklist_type
534	},
535	{
536	  NGM_GENERIC_COOKIE,
537	  NGM_LISTNAMES,
538	  "listnames",
539	  NULL,
540	  &ng_generic_listnodes_type	/* same as NGM_LISTNODES */
541	},
542	{
543	  NGM_GENERIC_COOKIE,
544	  NGM_LISTNODES,
545	  "listnodes",
546	  NULL,
547	  &ng_generic_listnodes_type
548	},
549	{
550	  NGM_GENERIC_COOKIE,
551	  NGM_LISTTYPES,
552	  "listtypes",
553	  NULL,
554	  &ng_generic_typelist_type
555	},
556	{
557	  NGM_GENERIC_COOKIE,
558	  NGM_TEXT_CONFIG,
559	  "textconfig",
560	  NULL,
561	  &ng_parse_string_type
562	},
563	{
564	  NGM_GENERIC_COOKIE,
565	  NGM_TEXT_STATUS,
566	  "textstatus",
567	  NULL,
568	  &ng_parse_string_type
569	},
570	{
571	  NGM_GENERIC_COOKIE,
572	  NGM_ASCII2BINARY,
573	  "ascii2binary",
574	  &ng_parse_ng_mesg_type,
575	  &ng_parse_ng_mesg_type
576	},
577	{
578	  NGM_GENERIC_COOKIE,
579	  NGM_BINARY2ASCII,
580	  "binary2ascii",
581	  &ng_parse_ng_mesg_type,
582	  &ng_parse_ng_mesg_type
583	},
584	{ 0 }
585};
586
587/************************************************************************
588			Node routines
589************************************************************************/
590
591/*
592 * Instantiate a node of the requested type
593 */
594int
595ng_make_node(const char *typename, node_p *nodepp)
596{
597	struct ng_type *type;
598	int	error;
599
600	/* Check that the type makes sense */
601	if (typename == NULL) {
602		TRAP_ERROR();
603		return (EINVAL);
604	}
605
606	/* Locate the node type. If we fail we return. Do not try to load
607	 * module.
608	 */
609	if ((type = ng_findtype(typename)) == NULL)
610		return (ENXIO);
611
612	/*
613	 * If we have a constructor, then make the node and
614	 * call the constructor to do type specific initialisation.
615	 */
616	if (type->constructor != NULL) {
617		if ((error = ng_make_node_common(type, nodepp)) == 0) {
618			if ((error = ((*type->constructor)(*nodepp))) != 0) {
619				NG_NODE_UNREF(*nodepp);
620			}
621		}
622	} else {
623		/*
624		 * Node has no constructor. We cannot ask for one
625		 * to be made. It must be brought into existence by
626		 * some external agency. The external agency should
627		 * call ng_make_node_common() directly to get the
628		 * netgraph part initialised.
629		 */
630		TRAP_ERROR();
631		error = EINVAL;
632	}
633	return (error);
634}
635
636/*
637 * Generic node creation. Called by node initialisation for externally
638 * instantiated nodes (e.g. hardware, sockets, etc ).
639 * The returned node has a reference count of 1.
640 */
641int
642ng_make_node_common(struct ng_type *type, node_p *nodepp)
643{
644	node_p node;
645
646	/* Require the node type to have been already installed */
647	if (ng_findtype(type->name) == NULL) {
648		TRAP_ERROR();
649		return (EINVAL);
650	}
651
652	/* Make a node and try attach it to the type */
653	NG_ALLOC_NODE(node);
654	if (node == NULL) {
655		TRAP_ERROR();
656		return (ENOMEM);
657	}
658	node->nd_type = type;
659#ifdef VIMAGE
660	node->nd_vnet = curvnet;
661#endif
662	NG_NODE_REF(node);				/* note reference */
663	type->refs++;
664
665	NG_QUEUE_LOCK_INIT(&node->nd_input_queue);
666	STAILQ_INIT(&node->nd_input_queue.queue);
667	node->nd_input_queue.q_flags = 0;
668
669	/* Initialize hook list for new node */
670	LIST_INIT(&node->nd_hooks);
671
672	/* Get an ID and put us in the hash chain. */
673	IDHASH_WLOCK();
674	for (;;) { /* wrap protection, even if silly */
675		node_p node2 = NULL;
676		node->nd_ID = V_nextID++; /* 137/sec for 1 year before wrap */
677
678		/* Is there a problem with the new number? */
679		NG_IDHASH_FIND(node->nd_ID, node2); /* already taken? */
680		if ((node->nd_ID != 0) && (node2 == NULL)) {
681			break;
682		}
683	}
684	V_ng_nodes++;
685	if (V_ng_nodes * 2 > V_ng_ID_hmask)
686		ng_ID_rehash();
687	LIST_INSERT_HEAD(&V_ng_ID_hash[NG_IDHASH_FN(node->nd_ID)], node,
688	    nd_idnodes);
689	IDHASH_WUNLOCK();
690
691	/* Done */
692	*nodepp = node;
693	return (0);
694}
695
696/*
697 * Forceably start the shutdown process on a node. Either call
698 * its shutdown method, or do the default shutdown if there is
699 * no type-specific method.
700 *
701 * We can only be called from a shutdown message, so we know we have
702 * a writer lock, and therefore exclusive access. It also means
703 * that we should not be on the work queue, but we check anyhow.
704 *
705 * Persistent node types must have a type-specific method which
706 * allocates a new node in which case, this one is irretrievably going away,
707 * or cleans up anything it needs, and just makes the node valid again,
708 * in which case we allow the node to survive.
709 *
710 * XXX We need to think of how to tell a persistent node that we
711 * REALLY need to go away because the hardware has gone or we
712 * are rebooting.... etc.
713 */
714void
715ng_rmnode(node_p node, hook_p dummy1, void *dummy2, int dummy3)
716{
717	hook_p hook;
718
719	/* Check if it's already shutting down */
720	if ((node->nd_flags & NGF_CLOSING) != 0)
721		return;
722
723	if (node == &ng_deadnode) {
724		printf ("shutdown called on deadnode\n");
725		return;
726	}
727
728	/* Add an extra reference so it doesn't go away during this */
729	NG_NODE_REF(node);
730
731	/*
732	 * Mark it invalid so any newcomers know not to try use it
733	 * Also add our own mark so we can't recurse
734	 * note that NGF_INVALID does not do this as it's also set during
735	 * creation
736	 */
737	node->nd_flags |= NGF_INVALID|NGF_CLOSING;
738
739	/* If node has its pre-shutdown method, then call it first*/
740	if (node->nd_type && node->nd_type->close)
741		(*node->nd_type->close)(node);
742
743	/* Notify all remaining connected nodes to disconnect */
744	while ((hook = LIST_FIRST(&node->nd_hooks)) != NULL)
745		ng_destroy_hook(hook);
746
747	/*
748	 * Drain the input queue forceably.
749	 * it has no hooks so what's it going to do, bleed on someone?
750	 * Theoretically we came here from a queue entry that was added
751	 * Just before the queue was closed, so it should be empty anyway.
752	 * Also removes us from worklist if needed.
753	 */
754	ng_flush_input_queue(node);
755
756	/* Ask the type if it has anything to do in this case */
757	if (node->nd_type && node->nd_type->shutdown) {
758		(*node->nd_type->shutdown)(node);
759		if (NG_NODE_IS_VALID(node)) {
760			/*
761			 * Well, blow me down if the node code hasn't declared
762			 * that it doesn't want to die.
763			 * Presumably it is a persistent node.
764			 * If we REALLY want it to go away,
765			 *  e.g. hardware going away,
766			 * Our caller should set NGF_REALLY_DIE in nd_flags.
767			 */
768			node->nd_flags &= ~(NGF_INVALID|NGF_CLOSING);
769			NG_NODE_UNREF(node); /* Assume they still have theirs */
770			return;
771		}
772	} else {				/* do the default thing */
773		NG_NODE_UNREF(node);
774	}
775
776	ng_unname(node); /* basically a NOP these days */
777
778	/*
779	 * Remove extra reference, possibly the last
780	 * Possible other holders of references may include
781	 * timeout callouts, but theoretically the node's supposed to
782	 * have cancelled them. Possibly hardware dependencies may
783	 * force a driver to 'linger' with a reference.
784	 */
785	NG_NODE_UNREF(node);
786}
787
788/*
789 * Remove a reference to the node, possibly the last.
790 * deadnode always acts as it it were the last.
791 */
792void
793ng_unref_node(node_p node)
794{
795
796	if (node == &ng_deadnode)
797		return;
798
799	CURVNET_SET(node->nd_vnet);
800
801	if (refcount_release(&node->nd_refs)) { /* we were the last */
802
803		node->nd_type->refs--; /* XXX maybe should get types lock? */
804		NAMEHASH_WLOCK();
805		if (NG_NODE_HAS_NAME(node)) {
806			V_ng_named_nodes--;
807			LIST_REMOVE(node, nd_nodes);
808		}
809		NAMEHASH_WUNLOCK();
810
811		IDHASH_WLOCK();
812		V_ng_nodes--;
813		LIST_REMOVE(node, nd_idnodes);
814		IDHASH_WUNLOCK();
815
816		mtx_destroy(&node->nd_input_queue.q_mtx);
817		NG_FREE_NODE(node);
818	}
819	CURVNET_RESTORE();
820}
821
822/************************************************************************
823			Node ID handling
824************************************************************************/
825static node_p
826ng_ID2noderef(ng_ID_t ID)
827{
828	node_p node;
829
830	IDHASH_RLOCK();
831	NG_IDHASH_FIND(ID, node);
832	if (node)
833		NG_NODE_REF(node);
834	IDHASH_RUNLOCK();
835	return(node);
836}
837
838ng_ID_t
839ng_node2ID(node_p node)
840{
841	return (node ? NG_NODE_ID(node) : 0);
842}
843
844/************************************************************************
845			Node name handling
846************************************************************************/
847
848/*
849 * Assign a node a name.
850 */
851int
852ng_name_node(node_p node, const char *name)
853{
854	uint32_t hash;
855	node_p node2;
856	int i;
857
858	/* Check the name is valid */
859	for (i = 0; i < NG_NODESIZ; i++) {
860		if (name[i] == '\0' || name[i] == '.' || name[i] == ':')
861			break;
862	}
863	if (i == 0 || name[i] != '\0') {
864		TRAP_ERROR();
865		return (EINVAL);
866	}
867	if (ng_decodeidname(name) != 0) { /* valid IDs not allowed here */
868		TRAP_ERROR();
869		return (EINVAL);
870	}
871
872	NAMEHASH_WLOCK();
873	if (V_ng_named_nodes * 2 > V_ng_name_hmask)
874		ng_name_rehash();
875
876	hash = hash32_str(name, HASHINIT) & V_ng_name_hmask;
877	/* Check the name isn't already being used. */
878	LIST_FOREACH(node2, &V_ng_name_hash[hash], nd_nodes)
879		if (NG_NODE_IS_VALID(node2) &&
880		    (strcmp(NG_NODE_NAME(node2), name) == 0)) {
881			NAMEHASH_WUNLOCK();
882			return (EADDRINUSE);
883		}
884
885	if (NG_NODE_HAS_NAME(node))
886		LIST_REMOVE(node, nd_nodes);
887	else
888		V_ng_named_nodes++;
889	/* Copy it. */
890	strlcpy(NG_NODE_NAME(node), name, NG_NODESIZ);
891	/* Update name hash. */
892	LIST_INSERT_HEAD(&V_ng_name_hash[hash], node, nd_nodes);
893	NAMEHASH_WUNLOCK();
894
895	return (0);
896}
897
898/*
899 * Find a node by absolute name. The name should NOT end with ':'
900 * The name "." means "this node" and "[xxx]" means "the node
901 * with ID (ie, at address) xxx".
902 *
903 * Returns the node if found, else NULL.
904 * Eventually should add something faster than a sequential search.
905 * Note it acquires a reference on the node so you can be sure it's still
906 * there.
907 */
908node_p
909ng_name2noderef(node_p here, const char *name)
910{
911	node_p node;
912	ng_ID_t temp;
913	int	hash;
914
915	/* "." means "this node" */
916	if (strcmp(name, ".") == 0) {
917		NG_NODE_REF(here);
918		return(here);
919	}
920
921	/* Check for name-by-ID */
922	if ((temp = ng_decodeidname(name)) != 0) {
923		return (ng_ID2noderef(temp));
924	}
925
926	/* Find node by name. */
927	hash = hash32_str(name, HASHINIT) & V_ng_name_hmask;
928	NAMEHASH_RLOCK();
929	LIST_FOREACH(node, &V_ng_name_hash[hash], nd_nodes)
930		if (NG_NODE_IS_VALID(node) &&
931		    (strcmp(NG_NODE_NAME(node), name) == 0)) {
932			NG_NODE_REF(node);
933			break;
934		}
935	NAMEHASH_RUNLOCK();
936
937	return (node);
938}
939
940/*
941 * Decode an ID name, eg. "[f03034de]". Returns 0 if the
942 * string is not valid, otherwise returns the value.
943 */
944static ng_ID_t
945ng_decodeidname(const char *name)
946{
947	const int len = strlen(name);
948	char *eptr;
949	u_long val;
950
951	/* Check for proper length, brackets, no leading junk */
952	if ((len < 3) || (name[0] != '[') || (name[len - 1] != ']') ||
953	    (!isxdigit(name[1])))
954		return ((ng_ID_t)0);
955
956	/* Decode number */
957	val = strtoul(name + 1, &eptr, 16);
958	if ((eptr - name != len - 1) || (val == ULONG_MAX) || (val == 0))
959		return ((ng_ID_t)0);
960
961	return ((ng_ID_t)val);
962}
963
964/*
965 * Remove a name from a node. This should only be called
966 * when shutting down and removing the node.
967 */
968void
969ng_unname(node_p node)
970{
971}
972
973/*
974 * Allocate a bigger name hash.
975 */
976static void
977ng_name_rehash()
978{
979	struct nodehash *new;
980	uint32_t hash;
981	u_long hmask;
982	node_p node, node2;
983	int i;
984
985	new = hashinit_flags((V_ng_name_hmask + 1) * 2, M_NETGRAPH_NODE, &hmask,
986	    HASH_NOWAIT);
987	if (new == NULL)
988		return;
989
990	for (i = 0; i <= V_ng_name_hmask; i++)
991		LIST_FOREACH_SAFE(node, &V_ng_name_hash[i], nd_nodes, node2) {
992#ifdef INVARIANTS
993			LIST_REMOVE(node, nd_nodes);
994#endif
995			hash = hash32_str(NG_NODE_NAME(node), HASHINIT) & hmask;
996			LIST_INSERT_HEAD(&new[hash], node, nd_nodes);
997		}
998
999	hashdestroy(V_ng_name_hash, M_NETGRAPH_NODE, V_ng_name_hmask);
1000	V_ng_name_hash = new;
1001	V_ng_name_hmask = hmask;
1002}
1003
1004/*
1005 * Allocate a bigger ID hash.
1006 */
1007static void
1008ng_ID_rehash()
1009{
1010	struct nodehash *new;
1011	uint32_t hash;
1012	u_long hmask;
1013	node_p node, node2;
1014	int i;
1015
1016	new = hashinit_flags((V_ng_ID_hmask + 1) * 2, M_NETGRAPH_NODE, &hmask,
1017	    HASH_NOWAIT);
1018	if (new == NULL)
1019		return;
1020
1021	for (i = 0; i <= V_ng_ID_hmask; i++)
1022		LIST_FOREACH_SAFE(node, &V_ng_ID_hash[i], nd_idnodes, node2) {
1023#ifdef INVARIANTS
1024			LIST_REMOVE(node, nd_idnodes);
1025#endif
1026			hash = (node->nd_ID % (hmask + 1));
1027			LIST_INSERT_HEAD(&new[hash], node, nd_idnodes);
1028		}
1029
1030	hashdestroy(V_ng_ID_hash, M_NETGRAPH_NODE, V_ng_name_hmask);
1031	V_ng_ID_hash = new;
1032	V_ng_ID_hmask = hmask;
1033}
1034
1035/************************************************************************
1036			Hook routines
1037 Names are not optional. Hooks are always connected, except for a
1038 brief moment within these routines. On invalidation or during creation
1039 they are connected to the 'dead' hook.
1040************************************************************************/
1041
1042/*
1043 * Remove a hook reference
1044 */
1045void
1046ng_unref_hook(hook_p hook)
1047{
1048
1049	if (hook == &ng_deadhook)
1050		return;
1051
1052	if (refcount_release(&hook->hk_refs)) { /* we were the last */
1053		if (_NG_HOOK_NODE(hook)) /* it'll probably be ng_deadnode */
1054			_NG_NODE_UNREF((_NG_HOOK_NODE(hook)));
1055		NG_FREE_HOOK(hook);
1056	}
1057}
1058
1059/*
1060 * Add an unconnected hook to a node. Only used internally.
1061 * Assumes node is locked. (XXX not yet true )
1062 */
1063static int
1064ng_add_hook(node_p node, const char *name, hook_p *hookp)
1065{
1066	hook_p hook;
1067	int error = 0;
1068
1069	/* Check that the given name is good */
1070	if (name == NULL) {
1071		TRAP_ERROR();
1072		return (EINVAL);
1073	}
1074	if (ng_findhook(node, name) != NULL) {
1075		TRAP_ERROR();
1076		return (EEXIST);
1077	}
1078
1079	/* Allocate the hook and link it up */
1080	NG_ALLOC_HOOK(hook);
1081	if (hook == NULL) {
1082		TRAP_ERROR();
1083		return (ENOMEM);
1084	}
1085	hook->hk_refs = 1;		/* add a reference for us to return */
1086	hook->hk_flags = HK_INVALID;
1087	hook->hk_peer = &ng_deadhook;	/* start off this way */
1088	hook->hk_node = node;
1089	NG_NODE_REF(node);		/* each hook counts as a reference */
1090
1091	/* Set hook name */
1092	strlcpy(NG_HOOK_NAME(hook), name, NG_HOOKSIZ);
1093
1094	/*
1095	 * Check if the node type code has something to say about it
1096	 * If it fails, the unref of the hook will also unref the node.
1097	 */
1098	if (node->nd_type->newhook != NULL) {
1099		if ((error = (*node->nd_type->newhook)(node, hook, name))) {
1100			NG_HOOK_UNREF(hook);	/* this frees the hook */
1101			return (error);
1102		}
1103	}
1104	/*
1105	 * The 'type' agrees so far, so go ahead and link it in.
1106	 * We'll ask again later when we actually connect the hooks.
1107	 */
1108	LIST_INSERT_HEAD(&node->nd_hooks, hook, hk_hooks);
1109	node->nd_numhooks++;
1110	NG_HOOK_REF(hook);	/* one for the node */
1111
1112	if (hookp)
1113		*hookp = hook;
1114	return (0);
1115}
1116
1117/*
1118 * Find a hook
1119 *
1120 * Node types may supply their own optimized routines for finding
1121 * hooks.  If none is supplied, we just do a linear search.
1122 * XXX Possibly we should add a reference to the hook?
1123 */
1124hook_p
1125ng_findhook(node_p node, const char *name)
1126{
1127	hook_p hook;
1128
1129	if (node->nd_type->findhook != NULL)
1130		return (*node->nd_type->findhook)(node, name);
1131	LIST_FOREACH(hook, &node->nd_hooks, hk_hooks) {
1132		if (NG_HOOK_IS_VALID(hook) &&
1133		    (strcmp(NG_HOOK_NAME(hook), name) == 0))
1134			return (hook);
1135	}
1136	return (NULL);
1137}
1138
1139/*
1140 * Destroy a hook
1141 *
1142 * As hooks are always attached, this really destroys two hooks.
1143 * The one given, and the one attached to it. Disconnect the hooks
1144 * from each other first. We reconnect the peer hook to the 'dead'
1145 * hook so that it can still exist after we depart. We then
1146 * send the peer its own destroy message. This ensures that we only
1147 * interact with the peer's structures when it is locked processing that
1148 * message. We hold a reference to the peer hook so we are guaranteed that
1149 * the peer hook and node are still going to exist until
1150 * we are finished there as the hook holds a ref on the node.
1151 * We run this same code again on the peer hook, but that time it is already
1152 * attached to the 'dead' hook.
1153 *
1154 * This routine is called at all stages of hook creation
1155 * on error detection and must be able to handle any such stage.
1156 */
1157void
1158ng_destroy_hook(hook_p hook)
1159{
1160	hook_p peer;
1161	node_p node;
1162
1163	if (hook == &ng_deadhook) {	/* better safe than sorry */
1164		printf("ng_destroy_hook called on deadhook\n");
1165		return;
1166	}
1167
1168	/*
1169	 * Protect divorce process with mutex, to avoid races on
1170	 * simultaneous disconnect.
1171	 */
1172	TOPOLOGY_WLOCK();
1173
1174	hook->hk_flags |= HK_INVALID;
1175
1176	peer = NG_HOOK_PEER(hook);
1177	node = NG_HOOK_NODE(hook);
1178
1179	if (peer && (peer != &ng_deadhook)) {
1180		/*
1181		 * Set the peer to point to ng_deadhook
1182		 * from this moment on we are effectively independent it.
1183		 * send it an rmhook message of its own.
1184		 */
1185		peer->hk_peer = &ng_deadhook;	/* They no longer know us */
1186		hook->hk_peer = &ng_deadhook;	/* Nor us, them */
1187		if (NG_HOOK_NODE(peer) == &ng_deadnode) {
1188			/*
1189			 * If it's already divorced from a node,
1190			 * just free it.
1191			 */
1192			TOPOLOGY_WUNLOCK();
1193		} else {
1194			TOPOLOGY_WUNLOCK();
1195			ng_rmhook_self(peer); 	/* Send it a surprise */
1196		}
1197		NG_HOOK_UNREF(peer);		/* account for peer link */
1198		NG_HOOK_UNREF(hook);		/* account for peer link */
1199	} else
1200		TOPOLOGY_WUNLOCK();
1201
1202	TOPOLOGY_NOTOWNED();
1203
1204	/*
1205	 * Remove the hook from the node's list to avoid possible recursion
1206	 * in case the disconnection results in node shutdown.
1207	 */
1208	if (node == &ng_deadnode) { /* happens if called from ng_con_nodes() */
1209		return;
1210	}
1211	LIST_REMOVE(hook, hk_hooks);
1212	node->nd_numhooks--;
1213	if (node->nd_type->disconnect) {
1214		/*
1215		 * The type handler may elect to destroy the node so don't
1216		 * trust its existence after this point. (except
1217		 * that we still hold a reference on it. (which we
1218		 * inherrited from the hook we are destroying)
1219		 */
1220		(*node->nd_type->disconnect) (hook);
1221	}
1222
1223	/*
1224	 * Note that because we will point to ng_deadnode, the original node
1225	 * is not decremented automatically so we do that manually.
1226	 */
1227	_NG_HOOK_NODE(hook) = &ng_deadnode;
1228	NG_NODE_UNREF(node);	/* We no longer point to it so adjust count */
1229	NG_HOOK_UNREF(hook);	/* Account for linkage (in list) to node */
1230}
1231
1232/*
1233 * Take two hooks on a node and merge the connection so that the given node
1234 * is effectively bypassed.
1235 */
1236int
1237ng_bypass(hook_p hook1, hook_p hook2)
1238{
1239	if (hook1->hk_node != hook2->hk_node) {
1240		TRAP_ERROR();
1241		return (EINVAL);
1242	}
1243	TOPOLOGY_WLOCK();
1244	if (NG_HOOK_NOT_VALID(hook1) || NG_HOOK_NOT_VALID(hook2)) {
1245		TOPOLOGY_WUNLOCK();
1246		return (EINVAL);
1247	}
1248	hook1->hk_peer->hk_peer = hook2->hk_peer;
1249	hook2->hk_peer->hk_peer = hook1->hk_peer;
1250
1251	hook1->hk_peer = &ng_deadhook;
1252	hook2->hk_peer = &ng_deadhook;
1253	TOPOLOGY_WUNLOCK();
1254
1255	NG_HOOK_UNREF(hook1);
1256	NG_HOOK_UNREF(hook2);
1257
1258	/* XXX If we ever cache methods on hooks update them as well */
1259	ng_destroy_hook(hook1);
1260	ng_destroy_hook(hook2);
1261	return (0);
1262}
1263
1264/*
1265 * Install a new netgraph type
1266 */
1267int
1268ng_newtype(struct ng_type *tp)
1269{
1270	const size_t namelen = strlen(tp->name);
1271
1272	/* Check version and type name fields */
1273	if ((tp->version != NG_ABI_VERSION) || (namelen == 0) ||
1274	    (namelen >= NG_TYPESIZ)) {
1275		TRAP_ERROR();
1276		if (tp->version != NG_ABI_VERSION) {
1277			printf("Netgraph: Node type rejected. ABI mismatch. "
1278			    "Suggest recompile\n");
1279		}
1280		return (EINVAL);
1281	}
1282
1283	/* Check for name collision */
1284	if (ng_findtype(tp->name) != NULL) {
1285		TRAP_ERROR();
1286		return (EEXIST);
1287	}
1288
1289	/* Link in new type */
1290	TYPELIST_WLOCK();
1291	LIST_INSERT_HEAD(&ng_typelist, tp, types);
1292	tp->refs = 1;	/* first ref is linked list */
1293	TYPELIST_WUNLOCK();
1294	return (0);
1295}
1296
1297/*
1298 * unlink a netgraph type
1299 * If no examples exist
1300 */
1301int
1302ng_rmtype(struct ng_type *tp)
1303{
1304	/* Check for name collision */
1305	if (tp->refs != 1) {
1306		TRAP_ERROR();
1307		return (EBUSY);
1308	}
1309
1310	/* Unlink type */
1311	TYPELIST_WLOCK();
1312	LIST_REMOVE(tp, types);
1313	TYPELIST_WUNLOCK();
1314	return (0);
1315}
1316
1317/*
1318 * Look for a type of the name given
1319 */
1320struct ng_type *
1321ng_findtype(const char *typename)
1322{
1323	struct ng_type *type;
1324
1325	TYPELIST_RLOCK();
1326	LIST_FOREACH(type, &ng_typelist, types) {
1327		if (strcmp(type->name, typename) == 0)
1328			break;
1329	}
1330	TYPELIST_RUNLOCK();
1331	return (type);
1332}
1333
1334/************************************************************************
1335			Composite routines
1336************************************************************************/
1337/*
1338 * Connect two nodes using the specified hooks, using queued functions.
1339 */
1340static int
1341ng_con_part3(node_p node, item_p item, hook_p hook)
1342{
1343	int	error = 0;
1344
1345	/*
1346	 * When we run, we know that the node 'node' is locked for us.
1347	 * Our caller has a reference on the hook.
1348	 * Our caller has a reference on the node.
1349	 * (In this case our caller is ng_apply_item() ).
1350	 * The peer hook has a reference on the hook.
1351	 * We are all set up except for the final call to the node, and
1352	 * the clearing of the INVALID flag.
1353	 */
1354	if (NG_HOOK_NODE(hook) == &ng_deadnode) {
1355		/*
1356		 * The node must have been freed again since we last visited
1357		 * here. ng_destry_hook() has this effect but nothing else does.
1358		 * We should just release our references and
1359		 * free anything we can think of.
1360		 * Since we know it's been destroyed, and it's our caller
1361		 * that holds the references, just return.
1362		 */
1363		ERROUT(ENOENT);
1364	}
1365	if (hook->hk_node->nd_type->connect) {
1366		if ((error = (*hook->hk_node->nd_type->connect) (hook))) {
1367			ng_destroy_hook(hook);	/* also zaps peer */
1368			printf("failed in ng_con_part3()\n");
1369			ERROUT(error);
1370		}
1371	}
1372	/*
1373	 *  XXX this is wrong for SMP. Possibly we need
1374	 * to separate out 'create' and 'invalid' flags.
1375	 * should only set flags on hooks we have locked under our node.
1376	 */
1377	hook->hk_flags &= ~HK_INVALID;
1378done:
1379	NG_FREE_ITEM(item);
1380	return (error);
1381}
1382
1383static int
1384ng_con_part2(node_p node, item_p item, hook_p hook)
1385{
1386	hook_p	peer;
1387	int	error = 0;
1388
1389	/*
1390	 * When we run, we know that the node 'node' is locked for us.
1391	 * Our caller has a reference on the hook.
1392	 * Our caller has a reference on the node.
1393	 * (In this case our caller is ng_apply_item() ).
1394	 * The peer hook has a reference on the hook.
1395	 * our node pointer points to the 'dead' node.
1396	 * First check the hook name is unique.
1397	 * Should not happen because we checked before queueing this.
1398	 */
1399	if (ng_findhook(node, NG_HOOK_NAME(hook)) != NULL) {
1400		TRAP_ERROR();
1401		ng_destroy_hook(hook); /* should destroy peer too */
1402		printf("failed in ng_con_part2()\n");
1403		ERROUT(EEXIST);
1404	}
1405	/*
1406	 * Check if the node type code has something to say about it
1407	 * If it fails, the unref of the hook will also unref the attached node,
1408	 * however since that node is 'ng_deadnode' this will do nothing.
1409	 * The peer hook will also be destroyed.
1410	 */
1411	if (node->nd_type->newhook != NULL) {
1412		if ((error = (*node->nd_type->newhook)(node, hook,
1413		    hook->hk_name))) {
1414			ng_destroy_hook(hook); /* should destroy peer too */
1415			printf("failed in ng_con_part2()\n");
1416			ERROUT(error);
1417		}
1418	}
1419
1420	/*
1421	 * The 'type' agrees so far, so go ahead and link it in.
1422	 * We'll ask again later when we actually connect the hooks.
1423	 */
1424	hook->hk_node = node;		/* just overwrite ng_deadnode */
1425	NG_NODE_REF(node);		/* each hook counts as a reference */
1426	LIST_INSERT_HEAD(&node->nd_hooks, hook, hk_hooks);
1427	node->nd_numhooks++;
1428	NG_HOOK_REF(hook);	/* one for the node */
1429
1430	/*
1431	 * We now have a symmetrical situation, where both hooks have been
1432	 * linked to their nodes, the newhook methods have been called
1433	 * And the references are all correct. The hooks are still marked
1434	 * as invalid, as we have not called the 'connect' methods
1435	 * yet.
1436	 * We can call the local one immediately as we have the
1437	 * node locked, but we need to queue the remote one.
1438	 */
1439	if (hook->hk_node->nd_type->connect) {
1440		if ((error = (*hook->hk_node->nd_type->connect) (hook))) {
1441			ng_destroy_hook(hook);	/* also zaps peer */
1442			printf("failed in ng_con_part2(A)\n");
1443			ERROUT(error);
1444		}
1445	}
1446
1447	/*
1448	 * Acquire topo mutex to avoid race with ng_destroy_hook().
1449	 */
1450	TOPOLOGY_RLOCK();
1451	peer = hook->hk_peer;
1452	if (peer == &ng_deadhook) {
1453		TOPOLOGY_RUNLOCK();
1454		printf("failed in ng_con_part2(B)\n");
1455		ng_destroy_hook(hook);
1456		ERROUT(ENOENT);
1457	}
1458	TOPOLOGY_RUNLOCK();
1459
1460	if ((error = ng_send_fn2(peer->hk_node, peer, item, &ng_con_part3,
1461	    NULL, 0, NG_REUSE_ITEM))) {
1462		printf("failed in ng_con_part2(C)\n");
1463		ng_destroy_hook(hook);	/* also zaps peer */
1464		return (error);		/* item was consumed. */
1465	}
1466	hook->hk_flags &= ~HK_INVALID; /* need both to be able to work */
1467	return (0);			/* item was consumed. */
1468done:
1469	NG_FREE_ITEM(item);
1470	return (error);
1471}
1472
1473/*
1474 * Connect this node with another node. We assume that this node is
1475 * currently locked, as we are only called from an NGM_CONNECT message.
1476 */
1477static int
1478ng_con_nodes(item_p item, node_p node, const char *name,
1479    node_p node2, const char *name2)
1480{
1481	int	error;
1482	hook_p	hook;
1483	hook_p	hook2;
1484
1485	if (ng_findhook(node2, name2) != NULL) {
1486		return(EEXIST);
1487	}
1488	if ((error = ng_add_hook(node, name, &hook)))  /* gives us a ref */
1489		return (error);
1490	/* Allocate the other hook and link it up */
1491	NG_ALLOC_HOOK(hook2);
1492	if (hook2 == NULL) {
1493		TRAP_ERROR();
1494		ng_destroy_hook(hook);	/* XXX check ref counts so far */
1495		NG_HOOK_UNREF(hook);	/* including our ref */
1496		return (ENOMEM);
1497	}
1498	hook2->hk_refs = 1;		/* start with a reference for us. */
1499	hook2->hk_flags = HK_INVALID;
1500	hook2->hk_peer = hook;		/* Link the two together */
1501	hook->hk_peer = hook2;
1502	NG_HOOK_REF(hook);		/* Add a ref for the peer to each*/
1503	NG_HOOK_REF(hook2);
1504	hook2->hk_node = &ng_deadnode;
1505	strlcpy(NG_HOOK_NAME(hook2), name2, NG_HOOKSIZ);
1506
1507	/*
1508	 * Queue the function above.
1509	 * Procesing continues in that function in the lock context of
1510	 * the other node.
1511	 */
1512	if ((error = ng_send_fn2(node2, hook2, item, &ng_con_part2, NULL, 0,
1513	    NG_NOFLAGS))) {
1514		printf("failed in ng_con_nodes(): %d\n", error);
1515		ng_destroy_hook(hook);	/* also zaps peer */
1516	}
1517
1518	NG_HOOK_UNREF(hook);		/* Let each hook go if it wants to */
1519	NG_HOOK_UNREF(hook2);
1520	return (error);
1521}
1522
1523/*
1524 * Make a peer and connect.
1525 * We assume that the local node is locked.
1526 * The new node probably doesn't need a lock until
1527 * it has a hook, because it cannot really have any work until then,
1528 * but we should think about it a bit more.
1529 *
1530 * The problem may come if the other node also fires up
1531 * some hardware or a timer or some other source of activation,
1532 * also it may already get a command msg via it's ID.
1533 *
1534 * We could use the same method as ng_con_nodes() but we'd have
1535 * to add ability to remove the node when failing. (Not hard, just
1536 * make arg1 point to the node to remove).
1537 * Unless of course we just ignore failure to connect and leave
1538 * an unconnected node?
1539 */
1540static int
1541ng_mkpeer(node_p node, const char *name, const char *name2, char *type)
1542{
1543	node_p	node2;
1544	hook_p	hook1, hook2;
1545	int	error;
1546
1547	if ((error = ng_make_node(type, &node2))) {
1548		return (error);
1549	}
1550
1551	if ((error = ng_add_hook(node, name, &hook1))) { /* gives us a ref */
1552		ng_rmnode(node2, NULL, NULL, 0);
1553		return (error);
1554	}
1555
1556	if ((error = ng_add_hook(node2, name2, &hook2))) {
1557		ng_rmnode(node2, NULL, NULL, 0);
1558		ng_destroy_hook(hook1);
1559		NG_HOOK_UNREF(hook1);
1560		return (error);
1561	}
1562
1563	/*
1564	 * Actually link the two hooks together.
1565	 */
1566	hook1->hk_peer = hook2;
1567	hook2->hk_peer = hook1;
1568
1569	/* Each hook is referenced by the other */
1570	NG_HOOK_REF(hook1);
1571	NG_HOOK_REF(hook2);
1572
1573	/* Give each node the opportunity to veto the pending connection */
1574	if (hook1->hk_node->nd_type->connect) {
1575		error = (*hook1->hk_node->nd_type->connect) (hook1);
1576	}
1577
1578	if ((error == 0) && hook2->hk_node->nd_type->connect) {
1579		error = (*hook2->hk_node->nd_type->connect) (hook2);
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 | CTLFLAG_MPSAFE, 0,
3253    "netgraph Family");
3254SYSCTL_INT(_net_graph, OID_AUTO, abi_version, CTLFLAG_RD, SYSCTL_NULL_INT_PTR, NG_ABI_VERSION,"");
3255SYSCTL_INT(_net_graph, OID_AUTO, msg_version, CTLFLAG_RD, SYSCTL_NULL_INT_PTR, NG_VERSION, "");
3256
3257#ifdef	NETGRAPH_DEBUG
3258void
3259dumphook (hook_p hook, char *file, int line)
3260{
3261	printf("hook: name %s, %d refs, Last touched:\n",
3262		_NG_HOOK_NAME(hook), hook->hk_refs);
3263	printf("	Last active @ %s, line %d\n",
3264		hook->lastfile, hook->lastline);
3265	if (line) {
3266		printf(" problem discovered at file %s, line %d\n", file, line);
3267#ifdef KDB
3268		kdb_backtrace();
3269#endif
3270	}
3271}
3272
3273void
3274dumpnode(node_p node, char *file, int line)
3275{
3276	printf("node: ID [%x]: type '%s', %d hooks, flags 0x%x, %d refs, %s:\n",
3277		_NG_NODE_ID(node), node->nd_type->name,
3278		node->nd_numhooks, node->nd_flags,
3279		node->nd_refs, node->nd_name);
3280	printf("	Last active @ %s, line %d\n",
3281		node->lastfile, node->lastline);
3282	if (line) {
3283		printf(" problem discovered at file %s, line %d\n", file, line);
3284#ifdef KDB
3285		kdb_backtrace();
3286#endif
3287	}
3288}
3289
3290void
3291dumpitem(item_p item, char *file, int line)
3292{
3293	printf(" ACTIVE item, last used at %s, line %d",
3294		item->lastfile, item->lastline);
3295	switch(item->el_flags & NGQF_TYPE) {
3296	case NGQF_DATA:
3297		printf(" - [data]\n");
3298		break;
3299	case NGQF_MESG:
3300		printf(" - retaddr[%d]:\n", _NGI_RETADDR(item));
3301		break;
3302	case NGQF_FN:
3303		printf(" - fn@%p (%p, %p, %p, %d (%x))\n",
3304			_NGI_FN(item),
3305			_NGI_NODE(item),
3306			_NGI_HOOK(item),
3307			item->body.fn.fn_arg1,
3308			item->body.fn.fn_arg2,
3309			item->body.fn.fn_arg2);
3310		break;
3311	case NGQF_FN2:
3312		printf(" - fn2@%p (%p, %p, %p, %d (%x))\n",
3313			_NGI_FN2(item),
3314			_NGI_NODE(item),
3315			_NGI_HOOK(item),
3316			item->body.fn.fn_arg1,
3317			item->body.fn.fn_arg2,
3318			item->body.fn.fn_arg2);
3319		break;
3320	}
3321	if (line) {
3322		printf(" problem discovered at file %s, line %d\n", file, line);
3323		if (_NGI_NODE(item)) {
3324			printf("node %p ([%x])\n",
3325				_NGI_NODE(item), ng_node2ID(_NGI_NODE(item)));
3326		}
3327	}
3328}
3329
3330static void
3331ng_dumpitems(void)
3332{
3333	item_p item;
3334	int i = 1;
3335	TAILQ_FOREACH(item, &ng_itemlist, all) {
3336		printf("[%d] ", i++);
3337		dumpitem(item, NULL, 0);
3338	}
3339}
3340
3341static void
3342ng_dumpnodes(void)
3343{
3344	node_p node;
3345	int i = 1;
3346	mtx_lock(&ng_nodelist_mtx);
3347	SLIST_FOREACH(node, &ng_allnodes, nd_all) {
3348		printf("[%d] ", i++);
3349		dumpnode(node, NULL, 0);
3350	}
3351	mtx_unlock(&ng_nodelist_mtx);
3352}
3353
3354static void
3355ng_dumphooks(void)
3356{
3357	hook_p hook;
3358	int i = 1;
3359	mtx_lock(&ng_nodelist_mtx);
3360	SLIST_FOREACH(hook, &ng_allhooks, hk_all) {
3361		printf("[%d] ", i++);
3362		dumphook(hook, NULL, 0);
3363	}
3364	mtx_unlock(&ng_nodelist_mtx);
3365}
3366
3367static int
3368sysctl_debug_ng_dump_items(SYSCTL_HANDLER_ARGS)
3369{
3370	int error;
3371	int val;
3372	int i;
3373
3374	val = allocated;
3375	i = 1;
3376	error = sysctl_handle_int(oidp, &val, 0, req);
3377	if (error != 0 || req->newptr == NULL)
3378		return (error);
3379	if (val == 42) {
3380		ng_dumpitems();
3381		ng_dumpnodes();
3382		ng_dumphooks();
3383	}
3384	return (0);
3385}
3386
3387SYSCTL_PROC(_debug, OID_AUTO, ng_dump_items,
3388    CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_NEEDGIANT, 0, sizeof(int),
3389    sysctl_debug_ng_dump_items, "I",
3390    "Number of allocated items");
3391#endif	/* NETGRAPH_DEBUG */
3392
3393/***********************************************************************
3394* Worklist routines
3395**********************************************************************/
3396/*
3397 * Pick a node off the list of nodes with work,
3398 * try get an item to process off it. Remove the node from the list.
3399 */
3400static void
3401ngthread(void *arg)
3402{
3403	for (;;) {
3404		struct epoch_tracker et;
3405		node_p  node;
3406
3407		/* Get node from the worklist. */
3408		NG_WORKLIST_LOCK();
3409		while ((node = STAILQ_FIRST(&ng_worklist)) == NULL)
3410			NG_WORKLIST_SLEEP();
3411		STAILQ_REMOVE_HEAD(&ng_worklist, nd_input_queue.q_work);
3412		NG_WORKLIST_UNLOCK();
3413		CURVNET_SET(node->nd_vnet);
3414		CTR3(KTR_NET, "%20s: node [%x] (%p) taken off worklist",
3415		    __func__, node->nd_ID, node);
3416		/*
3417		 * We have the node. We also take over the reference
3418		 * that the list had on it.
3419		 * Now process as much as you can, until it won't
3420		 * let you have another item off the queue.
3421		 * All this time, keep the reference
3422		 * that lets us be sure that the node still exists.
3423		 * Let the reference go at the last minute.
3424		 */
3425		NET_EPOCH_ENTER(et);
3426		for (;;) {
3427			item_p item;
3428			int rw;
3429
3430			NG_QUEUE_LOCK(&node->nd_input_queue);
3431			item = ng_dequeue(node, &rw);
3432			if (item == NULL) {
3433				node->nd_input_queue.q_flags2 &= ~NGQ2_WORKQ;
3434				NG_QUEUE_UNLOCK(&node->nd_input_queue);
3435				break; /* go look for another node */
3436			} else {
3437				NG_QUEUE_UNLOCK(&node->nd_input_queue);
3438				NGI_GET_NODE(item, node); /* zaps stored node */
3439				ng_apply_item(node, item, rw);
3440				NG_NODE_UNREF(node);
3441			}
3442		}
3443		NET_EPOCH_EXIT(et);
3444		NG_NODE_UNREF(node);
3445		CURVNET_RESTORE();
3446	}
3447}
3448
3449/*
3450 * XXX
3451 * It's posible that a debugging NG_NODE_REF may need
3452 * to be outside the mutex zone
3453 */
3454static void
3455ng_worklist_add(node_p node)
3456{
3457
3458	mtx_assert(&node->nd_input_queue.q_mtx, MA_OWNED);
3459
3460	if ((node->nd_input_queue.q_flags2 & NGQ2_WORKQ) == 0) {
3461		/*
3462		 * If we are not already on the work queue,
3463		 * then put us on.
3464		 */
3465		node->nd_input_queue.q_flags2 |= NGQ2_WORKQ;
3466		NG_NODE_REF(node); /* XXX safe in mutex? */
3467		NG_WORKLIST_LOCK();
3468		STAILQ_INSERT_TAIL(&ng_worklist, node, nd_input_queue.q_work);
3469		NG_WORKLIST_UNLOCK();
3470		CTR3(KTR_NET, "%20s: node [%x] (%p) put on worklist", __func__,
3471		    node->nd_ID, node);
3472		NG_WORKLIST_WAKEUP();
3473	} else {
3474		CTR3(KTR_NET, "%20s: node [%x] (%p) already on worklist",
3475		    __func__, node->nd_ID, node);
3476	}
3477}
3478
3479/***********************************************************************
3480* Externally useable functions to set up a queue item ready for sending
3481***********************************************************************/
3482
3483#ifdef	NETGRAPH_DEBUG
3484#define	ITEM_DEBUG_CHECKS						\
3485	do {								\
3486		if (NGI_NODE(item) ) {					\
3487			printf("item already has node");		\
3488			kdb_enter(KDB_WHY_NETGRAPH, "has node");	\
3489			NGI_CLR_NODE(item);				\
3490		}							\
3491		if (NGI_HOOK(item) ) {					\
3492			printf("item already has hook");		\
3493			kdb_enter(KDB_WHY_NETGRAPH, "has hook");	\
3494			NGI_CLR_HOOK(item);				\
3495		}							\
3496	} while (0)
3497#else
3498#define ITEM_DEBUG_CHECKS
3499#endif
3500
3501/*
3502 * Put mbuf into the item.
3503 * Hook and node references will be removed when the item is dequeued.
3504 * (or equivalent)
3505 * (XXX) Unsafe because no reference held by peer on remote node.
3506 * remote node might go away in this timescale.
3507 * We know the hooks can't go away because that would require getting
3508 * a writer item on both nodes and we must have at least a  reader
3509 * here to be able to do this.
3510 * Note that the hook loaded is the REMOTE hook.
3511 *
3512 * This is possibly in the critical path for new data.
3513 */
3514item_p
3515ng_package_data(struct mbuf *m, int flags)
3516{
3517	item_p item;
3518
3519	if ((item = ng_alloc_item(NGQF_DATA, flags)) == NULL) {
3520		NG_FREE_M(m);
3521		return (NULL);
3522	}
3523	ITEM_DEBUG_CHECKS;
3524	item->el_flags |= NGQF_READER;
3525	NGI_M(item) = m;
3526	return (item);
3527}
3528
3529/*
3530 * Allocate a queue item and put items into it..
3531 * Evaluate the address as this will be needed to queue it and
3532 * to work out what some of the fields should be.
3533 * Hook and node references will be removed when the item is dequeued.
3534 * (or equivalent)
3535 */
3536item_p
3537ng_package_msg(struct ng_mesg *msg, int flags)
3538{
3539	item_p item;
3540
3541	if ((item = ng_alloc_item(NGQF_MESG, flags)) == NULL) {
3542		NG_FREE_MSG(msg);
3543		return (NULL);
3544	}
3545	ITEM_DEBUG_CHECKS;
3546	/* Messages items count as writers unless explicitly exempted. */
3547	if (msg->header.cmd & NGM_READONLY)
3548		item->el_flags |= NGQF_READER;
3549	else
3550		item->el_flags |= NGQF_WRITER;
3551	/*
3552	 * Set the current lasthook into the queue item
3553	 */
3554	NGI_MSG(item) = msg;
3555	NGI_RETADDR(item) = 0;
3556	return (item);
3557}
3558
3559#define SET_RETADDR(item, here, retaddr)				\
3560	do {	/* Data or fn items don't have retaddrs */		\
3561		if ((item->el_flags & NGQF_TYPE) == NGQF_MESG) {	\
3562			if (retaddr) {					\
3563				NGI_RETADDR(item) = retaddr;		\
3564			} else {					\
3565				/*					\
3566				 * The old return address should be ok.	\
3567				 * If there isn't one, use the address	\
3568				 * here.				\
3569				 */					\
3570				if (NGI_RETADDR(item) == 0) {		\
3571					NGI_RETADDR(item)		\
3572						= ng_node2ID(here);	\
3573				}					\
3574			}						\
3575		}							\
3576	} while (0)
3577
3578int
3579ng_address_hook(node_p here, item_p item, hook_p hook, ng_ID_t retaddr)
3580{
3581	hook_p peer;
3582	node_p peernode;
3583	ITEM_DEBUG_CHECKS;
3584	/*
3585	 * Quick sanity check..
3586	 * Since a hook holds a reference on its node, once we know
3587	 * that the peer is still connected (even if invalid,) we know
3588	 * that the peer node is present, though maybe invalid.
3589	 */
3590	TOPOLOGY_RLOCK();
3591	if ((hook == NULL) || NG_HOOK_NOT_VALID(hook) ||
3592	    NG_HOOK_NOT_VALID(peer = NG_HOOK_PEER(hook)) ||
3593	    NG_NODE_NOT_VALID(peernode = NG_PEER_NODE(hook))) {
3594		NG_FREE_ITEM(item);
3595		TRAP_ERROR();
3596		TOPOLOGY_RUNLOCK();
3597		return (ENETDOWN);
3598	}
3599
3600	/*
3601	 * Transfer our interest to the other (peer) end.
3602	 */
3603	NG_HOOK_REF(peer);
3604	NG_NODE_REF(peernode);
3605	NGI_SET_HOOK(item, peer);
3606	NGI_SET_NODE(item, peernode);
3607	SET_RETADDR(item, here, retaddr);
3608
3609	TOPOLOGY_RUNLOCK();
3610
3611	return (0);
3612}
3613
3614int
3615ng_address_path(node_p here, item_p item, const char *address, ng_ID_t retaddr)
3616{
3617	node_p	dest = NULL;
3618	hook_p	hook = NULL;
3619	int	error;
3620
3621	ITEM_DEBUG_CHECKS;
3622	/*
3623	 * Note that ng_path2noderef increments the reference count
3624	 * on the node for us if it finds one. So we don't have to.
3625	 */
3626	error = ng_path2noderef(here, address, &dest, &hook);
3627	if (error) {
3628		NG_FREE_ITEM(item);
3629		return (error);
3630	}
3631	NGI_SET_NODE(item, dest);
3632	if (hook)
3633		NGI_SET_HOOK(item, hook);
3634
3635	SET_RETADDR(item, here, retaddr);
3636	return (0);
3637}
3638
3639int
3640ng_address_ID(node_p here, item_p item, ng_ID_t ID, ng_ID_t retaddr)
3641{
3642	node_p dest;
3643
3644	ITEM_DEBUG_CHECKS;
3645	/*
3646	 * Find the target node.
3647	 */
3648	dest = ng_ID2noderef(ID); /* GETS REFERENCE! */
3649	if (dest == NULL) {
3650		NG_FREE_ITEM(item);
3651		TRAP_ERROR();
3652		return(EINVAL);
3653	}
3654	/* Fill out the contents */
3655	NGI_SET_NODE(item, dest);
3656	NGI_CLR_HOOK(item);
3657	SET_RETADDR(item, here, retaddr);
3658	return (0);
3659}
3660
3661/*
3662 * special case to send a message to self (e.g. destroy node)
3663 * Possibly indicate an arrival hook too.
3664 * Useful for removing that hook :-)
3665 */
3666item_p
3667ng_package_msg_self(node_p here, hook_p hook, struct ng_mesg *msg)
3668{
3669	item_p item;
3670
3671	/*
3672	 * Find the target node.
3673	 * If there is a HOOK argument, then use that in preference
3674	 * to the address.
3675	 */
3676	if ((item = ng_alloc_item(NGQF_MESG, NG_NOFLAGS)) == NULL) {
3677		NG_FREE_MSG(msg);
3678		return (NULL);
3679	}
3680
3681	/* Fill out the contents */
3682	item->el_flags |= NGQF_WRITER;
3683	NG_NODE_REF(here);
3684	NGI_SET_NODE(item, here);
3685	if (hook) {
3686		NG_HOOK_REF(hook);
3687		NGI_SET_HOOK(item, hook);
3688	}
3689	NGI_MSG(item) = msg;
3690	NGI_RETADDR(item) = ng_node2ID(here);
3691	return (item);
3692}
3693
3694/*
3695 * Send ng_item_fn function call to the specified node.
3696 */
3697
3698int
3699ng_send_fn(node_p node, hook_p hook, ng_item_fn *fn, void * arg1, int arg2)
3700{
3701
3702	return ng_send_fn1(node, hook, fn, arg1, arg2, NG_NOFLAGS);
3703}
3704
3705int
3706ng_send_fn1(node_p node, hook_p hook, ng_item_fn *fn, void * arg1, int arg2,
3707	int flags)
3708{
3709	item_p item;
3710
3711	if ((item = ng_alloc_item(NGQF_FN, flags)) == NULL) {
3712		return (ENOMEM);
3713	}
3714	item->el_flags |= NGQF_WRITER;
3715	NG_NODE_REF(node); /* and one for the item */
3716	NGI_SET_NODE(item, node);
3717	if (hook) {
3718		NG_HOOK_REF(hook);
3719		NGI_SET_HOOK(item, hook);
3720	}
3721	NGI_FN(item) = fn;
3722	NGI_ARG1(item) = arg1;
3723	NGI_ARG2(item) = arg2;
3724	return(ng_snd_item(item, flags));
3725}
3726
3727/*
3728 * Send ng_item_fn2 function call to the specified node.
3729 *
3730 * If an optional pitem parameter is supplied, its apply
3731 * callback will be copied to the new item. If also NG_REUSE_ITEM
3732 * flag is set, no new item will be allocated, but pitem will
3733 * be used.
3734 */
3735int
3736ng_send_fn2(node_p node, hook_p hook, item_p pitem, ng_item_fn2 *fn, void *arg1,
3737	int arg2, int flags)
3738{
3739	item_p item;
3740
3741	KASSERT((pitem != NULL || (flags & NG_REUSE_ITEM) == 0),
3742	    ("%s: NG_REUSE_ITEM but no pitem", __func__));
3743
3744	/*
3745	 * Allocate a new item if no supplied or
3746	 * if we can't use supplied one.
3747	 */
3748	if (pitem == NULL || (flags & NG_REUSE_ITEM) == 0) {
3749		if ((item = ng_alloc_item(NGQF_FN2, flags)) == NULL)
3750			return (ENOMEM);
3751		if (pitem != NULL)
3752			item->apply = pitem->apply;
3753	} else {
3754		if ((item = ng_realloc_item(pitem, NGQF_FN2, flags)) == NULL)
3755			return (ENOMEM);
3756	}
3757
3758	item->el_flags = (item->el_flags & ~NGQF_RW) | NGQF_WRITER;
3759	NG_NODE_REF(node); /* and one for the item */
3760	NGI_SET_NODE(item, node);
3761	if (hook) {
3762		NG_HOOK_REF(hook);
3763		NGI_SET_HOOK(item, hook);
3764	}
3765	NGI_FN2(item) = fn;
3766	NGI_ARG1(item) = arg1;
3767	NGI_ARG2(item) = arg2;
3768	return(ng_snd_item(item, flags));
3769}
3770
3771/*
3772 * Official timeout routines for Netgraph nodes.
3773 */
3774static void
3775ng_callout_trampoline(void *arg)
3776{
3777	struct epoch_tracker et;
3778	item_p item = arg;
3779
3780	NET_EPOCH_ENTER(et);
3781	CURVNET_SET(NGI_NODE(item)->nd_vnet);
3782	ng_snd_item(item, 0);
3783	CURVNET_RESTORE();
3784	NET_EPOCH_EXIT(et);
3785}
3786
3787int
3788ng_callout(struct callout *c, node_p node, hook_p hook, int ticks,
3789    ng_item_fn *fn, void * arg1, int arg2)
3790{
3791	item_p item, oitem;
3792
3793	if ((item = ng_alloc_item(NGQF_FN, NG_NOFLAGS)) == NULL)
3794		return (ENOMEM);
3795
3796	item->el_flags |= NGQF_WRITER;
3797	NG_NODE_REF(node);		/* and one for the item */
3798	NGI_SET_NODE(item, node);
3799	if (hook) {
3800		NG_HOOK_REF(hook);
3801		NGI_SET_HOOK(item, hook);
3802	}
3803	NGI_FN(item) = fn;
3804	NGI_ARG1(item) = arg1;
3805	NGI_ARG2(item) = arg2;
3806	oitem = c->c_arg;
3807	if (callout_reset(c, ticks, &ng_callout_trampoline, item) == 1 &&
3808	    oitem != NULL)
3809		NG_FREE_ITEM(oitem);
3810	return (0);
3811}
3812
3813/* A special modified version of callout_stop() */
3814int
3815ng_uncallout(struct callout *c, node_p node)
3816{
3817	item_p item;
3818	int rval;
3819
3820	KASSERT(c != NULL, ("ng_uncallout: NULL callout"));
3821	KASSERT(node != NULL, ("ng_uncallout: NULL node"));
3822
3823	rval = callout_stop(c);
3824	item = c->c_arg;
3825	/* Do an extra check */
3826	if ((rval > 0) && (c->c_func == &ng_callout_trampoline) &&
3827	    (item != NULL) && (NGI_NODE(item) == node)) {
3828		/*
3829		 * We successfully removed it from the queue before it ran
3830		 * So now we need to unreference everything that was
3831		 * given extra references. (NG_FREE_ITEM does this).
3832		 */
3833		NG_FREE_ITEM(item);
3834	}
3835	c->c_arg = NULL;
3836
3837	/*
3838	 * Callers only want to know if the callout was cancelled and
3839	 * not draining or stopped.
3840	 */
3841	return (rval > 0);
3842}
3843
3844/*
3845 * Set the address, if none given, give the node here.
3846 */
3847void
3848ng_replace_retaddr(node_p here, item_p item, ng_ID_t retaddr)
3849{
3850	if (retaddr) {
3851		NGI_RETADDR(item) = retaddr;
3852	} else {
3853		/*
3854		 * The old return address should be ok.
3855		 * If there isn't one, use the address here.
3856		 */
3857		NGI_RETADDR(item) = ng_node2ID(here);
3858	}
3859}
3860