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	/*
1584	 * drop the references we were holding on the two hooks.
1585	 */
1586	if (error) {
1587		ng_destroy_hook(hook2);	/* also zaps hook1 */
1588		ng_rmnode(node2, NULL, NULL, 0);
1589	} else {
1590		/* As a last act, allow the hooks to be used */
1591		hook1->hk_flags &= ~HK_INVALID;
1592		hook2->hk_flags &= ~HK_INVALID;
1593	}
1594	NG_HOOK_UNREF(hook1);
1595	NG_HOOK_UNREF(hook2);
1596	return (error);
1597}
1598
1599/************************************************************************
1600		Utility routines to send self messages
1601************************************************************************/
1602
1603/* Shut this node down as soon as everyone is clear of it */
1604/* Should add arg "immediately" to jump the queue */
1605int
1606ng_rmnode_self(node_p node)
1607{
1608	int		error;
1609
1610	if (node == &ng_deadnode)
1611		return (0);
1612	node->nd_flags |= NGF_INVALID;
1613	if (node->nd_flags & NGF_CLOSING)
1614		return (0);
1615
1616	error = ng_send_fn(node, NULL, &ng_rmnode, NULL, 0);
1617	return (error);
1618}
1619
1620static void
1621ng_rmhook_part2(node_p node, hook_p hook, void *arg1, int arg2)
1622{
1623	ng_destroy_hook(hook);
1624	return ;
1625}
1626
1627int
1628ng_rmhook_self(hook_p hook)
1629{
1630	int		error;
1631	node_p node = NG_HOOK_NODE(hook);
1632
1633	if (node == &ng_deadnode)
1634		return (0);
1635
1636	error = ng_send_fn(node, hook, &ng_rmhook_part2, NULL, 0);
1637	return (error);
1638}
1639
1640/***********************************************************************
1641 * Parse and verify a string of the form:  <NODE:><PATH>
1642 *
1643 * Such a string can refer to a specific node or a specific hook
1644 * on a specific node, depending on how you look at it. In the
1645 * latter case, the PATH component must not end in a dot.
1646 *
1647 * Both <NODE:> and <PATH> are optional. The <PATH> is a string
1648 * of hook names separated by dots. This breaks out the original
1649 * string, setting *nodep to "NODE" (or NULL if none) and *pathp
1650 * to "PATH" (or NULL if degenerate). Also, *hookp will point to
1651 * the final hook component of <PATH>, if any, otherwise NULL.
1652 *
1653 * This returns -1 if the path is malformed. The char ** are optional.
1654 ***********************************************************************/
1655int
1656ng_path_parse(char *addr, char **nodep, char **pathp, char **hookp)
1657{
1658	char	*node, *path, *hook;
1659	int	k;
1660
1661	/*
1662	 * Extract absolute NODE, if any
1663	 */
1664	for (path = addr; *path && *path != ':'; path++);
1665	if (*path) {
1666		node = addr;	/* Here's the NODE */
1667		*path++ = '\0';	/* Here's the PATH */
1668
1669		/* Node name must not be empty */
1670		if (!*node)
1671			return -1;
1672
1673		/* A name of "." is OK; otherwise '.' not allowed */
1674		if (strcmp(node, ".") != 0) {
1675			for (k = 0; node[k]; k++)
1676				if (node[k] == '.')
1677					return -1;
1678		}
1679	} else {
1680		node = NULL;	/* No absolute NODE */
1681		path = addr;	/* Here's the PATH */
1682	}
1683
1684	/* Snoop for illegal characters in PATH */
1685	for (k = 0; path[k]; k++)
1686		if (path[k] == ':')
1687			return -1;
1688
1689	/* Check for no repeated dots in PATH */
1690	for (k = 0; path[k]; k++)
1691		if (path[k] == '.' && path[k + 1] == '.')
1692			return -1;
1693
1694	/* Remove extra (degenerate) dots from beginning or end of PATH */
1695	if (path[0] == '.')
1696		path++;
1697	if (*path && path[strlen(path) - 1] == '.')
1698		path[strlen(path) - 1] = 0;
1699
1700	/* If PATH has a dot, then we're not talking about a hook */
1701	if (*path) {
1702		for (hook = path, k = 0; path[k]; k++)
1703			if (path[k] == '.') {
1704				hook = NULL;
1705				break;
1706			}
1707	} else
1708		path = hook = NULL;
1709
1710	/* Done */
1711	if (nodep)
1712		*nodep = node;
1713	if (pathp)
1714		*pathp = path;
1715	if (hookp)
1716		*hookp = hook;
1717	return (0);
1718}
1719
1720/*
1721 * Given a path, which may be absolute or relative, and a starting node,
1722 * return the destination node.
1723 */
1724int
1725ng_path2noderef(node_p here, const char *address, node_p *destp,
1726    hook_p *lasthook)
1727{
1728	char    fullpath[NG_PATHSIZ];
1729	char   *nodename, *path;
1730	node_p  node, oldnode;
1731
1732	/* Initialize */
1733	if (destp == NULL) {
1734		TRAP_ERROR();
1735		return EINVAL;
1736	}
1737	*destp = NULL;
1738
1739	/* Make a writable copy of address for ng_path_parse() */
1740	strncpy(fullpath, address, sizeof(fullpath) - 1);
1741	fullpath[sizeof(fullpath) - 1] = '\0';
1742
1743	/* Parse out node and sequence of hooks */
1744	if (ng_path_parse(fullpath, &nodename, &path, NULL) < 0) {
1745		TRAP_ERROR();
1746		return EINVAL;
1747	}
1748
1749	/*
1750	 * For an absolute address, jump to the starting node.
1751	 * Note that this holds a reference on the node for us.
1752	 * Don't forget to drop the reference if we don't need it.
1753	 */
1754	if (nodename) {
1755		node = ng_name2noderef(here, nodename);
1756		if (node == NULL) {
1757			TRAP_ERROR();
1758			return (ENOENT);
1759		}
1760	} else {
1761		if (here == NULL) {
1762			TRAP_ERROR();
1763			return (EINVAL);
1764		}
1765		node = here;
1766		NG_NODE_REF(node);
1767	}
1768
1769	if (path == NULL) {
1770		if (lasthook != NULL)
1771			*lasthook = NULL;
1772		*destp = node;
1773		return (0);
1774	}
1775
1776	/*
1777	 * Now follow the sequence of hooks
1778	 *
1779	 * XXXGL: The path may demolish as we go the sequence, but if
1780	 * we hold the topology mutex at critical places, then, I hope,
1781	 * we would always have valid pointers in hand, although the
1782	 * path behind us may no longer exist.
1783	 */
1784	for (;;) {
1785		hook_p hook;
1786		char *segment;
1787
1788		/*
1789		 * Break out the next path segment. Replace the dot we just
1790		 * found with a NUL; "path" points to the next segment (or the
1791		 * NUL at the end).
1792		 */
1793		for (segment = path; *path != '\0'; path++) {
1794			if (*path == '.') {
1795				*path++ = '\0';
1796				break;
1797			}
1798		}
1799
1800		/* We have a segment, so look for a hook by that name */
1801		hook = ng_findhook(node, segment);
1802
1803		TOPOLOGY_WLOCK();
1804		/* Can't get there from here... */
1805		if (hook == NULL || NG_HOOK_PEER(hook) == NULL ||
1806		    NG_HOOK_NOT_VALID(hook) ||
1807		    NG_HOOK_NOT_VALID(NG_HOOK_PEER(hook))) {
1808			TRAP_ERROR();
1809			NG_NODE_UNREF(node);
1810			TOPOLOGY_WUNLOCK();
1811			return (ENOENT);
1812		}
1813
1814		/*
1815		 * Hop on over to the next node
1816		 * XXX
1817		 * Big race conditions here as hooks and nodes go away
1818		 * *** Idea.. store an ng_ID_t in each hook and use that
1819		 * instead of the direct hook in this crawl?
1820		 */
1821		oldnode = node;
1822		if ((node = NG_PEER_NODE(hook)))
1823			NG_NODE_REF(node);	/* XXX RACE */
1824		NG_NODE_UNREF(oldnode);	/* XXX another race */
1825		if (NG_NODE_NOT_VALID(node)) {
1826			NG_NODE_UNREF(node);	/* XXX more races */
1827			TOPOLOGY_WUNLOCK();
1828			TRAP_ERROR();
1829			return (ENXIO);
1830		}
1831
1832		if (*path == '\0') {
1833			if (lasthook != NULL) {
1834				if (hook != NULL) {
1835					*lasthook = NG_HOOK_PEER(hook);
1836					NG_HOOK_REF(*lasthook);
1837				} else
1838					*lasthook = NULL;
1839			}
1840			TOPOLOGY_WUNLOCK();
1841			*destp = node;
1842			return (0);
1843		}
1844		TOPOLOGY_WUNLOCK();
1845	}
1846}
1847
1848/***************************************************************\
1849* Input queue handling.
1850* All activities are submitted to the node via the input queue
1851* which implements a multiple-reader/single-writer gate.
1852* Items which cannot be handled immediately are queued.
1853*
1854* read-write queue locking inline functions			*
1855\***************************************************************/
1856
1857static __inline void	ng_queue_rw(node_p node, item_p  item, int rw);
1858static __inline item_p	ng_dequeue(node_p node, int *rw);
1859static __inline item_p	ng_acquire_read(node_p node, item_p  item);
1860static __inline item_p	ng_acquire_write(node_p node, item_p  item);
1861static __inline void	ng_leave_read(node_p node);
1862static __inline void	ng_leave_write(node_p node);
1863
1864/*
1865 * Definition of the bits fields in the ng_queue flag word.
1866 * Defined here rather than in netgraph.h because no-one should fiddle
1867 * with them.
1868 *
1869 * The ordering here may be important! don't shuffle these.
1870 */
1871/*-
1872 Safety Barrier--------+ (adjustable to suit taste) (not used yet)
1873                       |
1874                       V
1875+-------+-------+-------+-------+-------+-------+-------+-------+
1876  | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
1877  | |A|c|t|i|v|e| |R|e|a|d|e|r| |C|o|u|n|t| | | | | | | | | |P|A|
1878  | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |O|W|
1879+-------+-------+-------+-------+-------+-------+-------+-------+
1880  \___________________________ ____________________________/ | |
1881                            V                                | |
1882                  [active reader count]                      | |
1883                                                             | |
1884            Operation Pending -------------------------------+ |
1885                                                               |
1886          Active Writer ---------------------------------------+
1887
1888Node queue has such semantics:
1889- All flags modifications are atomic.
1890- Reader count can be incremented only if there is no writer or pending flags.
1891  As soon as this can't be done with single operation, it is implemented with
1892  spin loop and atomic_cmpset().
1893- Writer flag can be set only if there is no any bits set.
1894  It is implemented with atomic_cmpset().
1895- Pending flag can be set any time, but to avoid collision on queue processing
1896  all queue fields are protected by the mutex.
1897- Queue processing thread reads queue holding the mutex, but releases it while
1898  processing. When queue is empty pending flag is removed.
1899*/
1900
1901#define WRITER_ACTIVE	0x00000001
1902#define OP_PENDING	0x00000002
1903#define READER_INCREMENT 0x00000004
1904#define READER_MASK	0xfffffffc	/* Not valid if WRITER_ACTIVE is set */
1905#define SAFETY_BARRIER	0x00100000	/* 128K items queued should be enough */
1906
1907/* Defines of more elaborate states on the queue */
1908/* Mask of bits a new read cares about */
1909#define NGQ_RMASK	(WRITER_ACTIVE|OP_PENDING)
1910
1911/* Mask of bits a new write cares about */
1912#define NGQ_WMASK	(NGQ_RMASK|READER_MASK)
1913
1914/* Test to decide if there is something on the queue. */
1915#define QUEUE_ACTIVE(QP) ((QP)->q_flags & OP_PENDING)
1916
1917/* How to decide what the next queued item is. */
1918#define HEAD_IS_READER(QP)  NGI_QUEUED_READER(STAILQ_FIRST(&(QP)->queue))
1919#define HEAD_IS_WRITER(QP)  NGI_QUEUED_WRITER(STAILQ_FIRST(&(QP)->queue)) /* notused */
1920
1921/* Read the status to decide if the next item on the queue can now run. */
1922#define QUEUED_READER_CAN_PROCEED(QP)			\
1923		(((QP)->q_flags & (NGQ_RMASK & ~OP_PENDING)) == 0)
1924#define QUEUED_WRITER_CAN_PROCEED(QP)			\
1925		(((QP)->q_flags & (NGQ_WMASK & ~OP_PENDING)) == 0)
1926
1927/* Is there a chance of getting ANY work off the queue? */
1928#define NEXT_QUEUED_ITEM_CAN_PROCEED(QP)				\
1929	((HEAD_IS_READER(QP)) ? QUEUED_READER_CAN_PROCEED(QP) :		\
1930				QUEUED_WRITER_CAN_PROCEED(QP))
1931
1932#define NGQRW_R 0
1933#define NGQRW_W 1
1934
1935#define NGQ2_WORKQ	0x00000001
1936
1937/*
1938 * Taking into account the current state of the queue and node, possibly take
1939 * the next entry off the queue and return it. Return NULL if there was
1940 * nothing we could return, either because there really was nothing there, or
1941 * because the node was in a state where it cannot yet process the next item
1942 * on the queue.
1943 */
1944static __inline item_p
1945ng_dequeue(node_p node, int *rw)
1946{
1947	item_p item;
1948	struct ng_queue *ngq = &node->nd_input_queue;
1949
1950	/* This MUST be called with the mutex held. */
1951	mtx_assert(&ngq->q_mtx, MA_OWNED);
1952
1953	/* If there is nothing queued, then just return. */
1954	if (!QUEUE_ACTIVE(ngq)) {
1955		CTR4(KTR_NET, "%20s: node [%x] (%p) queue empty; "
1956		    "queue flags 0x%lx", __func__,
1957		    node->nd_ID, node, ngq->q_flags);
1958		return (NULL);
1959	}
1960
1961	/*
1962	 * From here, we can assume there is a head item.
1963	 * We need to find out what it is and if it can be dequeued, given
1964	 * the current state of the node.
1965	 */
1966	if (HEAD_IS_READER(ngq)) {
1967		while (1) {
1968			long t = ngq->q_flags;
1969			if (t & WRITER_ACTIVE) {
1970				/* There is writer, reader can't proceed. */
1971				CTR4(KTR_NET, "%20s: node [%x] (%p) queued "
1972				    "reader can't proceed; queue flags 0x%lx",
1973				    __func__, node->nd_ID, node, t);
1974				return (NULL);
1975			}
1976			if (atomic_cmpset_acq_int(&ngq->q_flags, t,
1977			    t + READER_INCREMENT))
1978				break;
1979			cpu_spinwait();
1980		}
1981		/* We have got reader lock for the node. */
1982		*rw = NGQRW_R;
1983	} else if (atomic_cmpset_acq_int(&ngq->q_flags, OP_PENDING,
1984	    OP_PENDING + WRITER_ACTIVE)) {
1985		/* We have got writer lock for the node. */
1986		*rw = NGQRW_W;
1987	} else {
1988		/* There is somebody other, writer can't proceed. */
1989		CTR4(KTR_NET, "%20s: node [%x] (%p) queued writer can't "
1990		    "proceed; queue flags 0x%lx", __func__, node->nd_ID, node,
1991		    ngq->q_flags);
1992		return (NULL);
1993	}
1994
1995	/*
1996	 * Now we dequeue the request (whatever it may be) and correct the
1997	 * pending flags and the next and last pointers.
1998	 */
1999	item = STAILQ_FIRST(&ngq->queue);
2000	STAILQ_REMOVE_HEAD(&ngq->queue, el_next);
2001	if (STAILQ_EMPTY(&ngq->queue))
2002		atomic_clear_int(&ngq->q_flags, OP_PENDING);
2003	CTR6(KTR_NET, "%20s: node [%x] (%p) returning item %p as %s; queue "
2004	    "flags 0x%lx", __func__, node->nd_ID, node, item, *rw ? "WRITER" :
2005	    "READER", ngq->q_flags);
2006	return (item);
2007}
2008
2009/*
2010 * Queue a packet to be picked up later by someone else.
2011 * If the queue could be run now, add node to the queue handler's worklist.
2012 */
2013static __inline void
2014ng_queue_rw(node_p node, item_p  item, int rw)
2015{
2016	struct ng_queue *ngq = &node->nd_input_queue;
2017	if (rw == NGQRW_W)
2018		NGI_SET_WRITER(item);
2019	else
2020		NGI_SET_READER(item);
2021	item->depth = 1;
2022
2023	NG_QUEUE_LOCK(ngq);
2024	/* Set OP_PENDING flag and enqueue the item. */
2025	atomic_set_int(&ngq->q_flags, OP_PENDING);
2026	STAILQ_INSERT_TAIL(&ngq->queue, item, el_next);
2027
2028	CTR5(KTR_NET, "%20s: node [%x] (%p) queued item %p as %s", __func__,
2029	    node->nd_ID, node, item, rw ? "WRITER" : "READER" );
2030
2031	/*
2032	 * We can take the worklist lock with the node locked
2033	 * BUT NOT THE REVERSE!
2034	 */
2035	if (NEXT_QUEUED_ITEM_CAN_PROCEED(ngq))
2036		ng_worklist_add(node);
2037	NG_QUEUE_UNLOCK(ngq);
2038}
2039
2040/* Acquire reader lock on node. If node is busy, queue the packet. */
2041static __inline item_p
2042ng_acquire_read(node_p node, item_p item)
2043{
2044	KASSERT(node != &ng_deadnode,
2045	    ("%s: working on deadnode", __func__));
2046
2047	/* Reader needs node without writer and pending items. */
2048	for (;;) {
2049		long t = node->nd_input_queue.q_flags;
2050		if (t & NGQ_RMASK)
2051			break; /* Node is not ready for reader. */
2052		if (atomic_cmpset_acq_int(&node->nd_input_queue.q_flags, t,
2053		    t + READER_INCREMENT)) {
2054	    		/* Successfully grabbed node */
2055			CTR4(KTR_NET, "%20s: node [%x] (%p) acquired item %p",
2056			    __func__, node->nd_ID, node, item);
2057			return (item);
2058		}
2059		cpu_spinwait();
2060	}
2061
2062	/* Queue the request for later. */
2063	ng_queue_rw(node, item, NGQRW_R);
2064
2065	return (NULL);
2066}
2067
2068/* Acquire writer lock on node. If node is busy, queue the packet. */
2069static __inline item_p
2070ng_acquire_write(node_p node, item_p item)
2071{
2072	KASSERT(node != &ng_deadnode,
2073	    ("%s: working on deadnode", __func__));
2074
2075	/* Writer needs completely idle node. */
2076	if (atomic_cmpset_acq_int(&node->nd_input_queue.q_flags, 0,
2077	    WRITER_ACTIVE)) {
2078	    	/* Successfully grabbed node */
2079		CTR4(KTR_NET, "%20s: node [%x] (%p) acquired item %p",
2080		    __func__, node->nd_ID, node, item);
2081		return (item);
2082	}
2083
2084	/* Queue the request for later. */
2085	ng_queue_rw(node, item, NGQRW_W);
2086
2087	return (NULL);
2088}
2089
2090#if 0
2091static __inline item_p
2092ng_upgrade_write(node_p node, item_p item)
2093{
2094	struct ng_queue *ngq = &node->nd_input_queue;
2095	KASSERT(node != &ng_deadnode,
2096	    ("%s: working on deadnode", __func__));
2097
2098	NGI_SET_WRITER(item);
2099
2100	NG_QUEUE_LOCK(ngq);
2101
2102	/*
2103	 * There will never be no readers as we are there ourselves.
2104	 * Set the WRITER_ACTIVE flags ASAP to block out fast track readers.
2105	 * The caller we are running from will call ng_leave_read()
2106	 * soon, so we must account for that. We must leave again with the
2107	 * READER lock. If we find other readers, then
2108	 * queue the request for later. However "later" may be rignt now
2109	 * if there are no readers. We don't really care if there are queued
2110	 * items as we will bypass them anyhow.
2111	 */
2112	atomic_add_int(&ngq->q_flags, WRITER_ACTIVE - READER_INCREMENT);
2113	if ((ngq->q_flags & (NGQ_WMASK & ~OP_PENDING)) == WRITER_ACTIVE) {
2114		NG_QUEUE_UNLOCK(ngq);
2115
2116		/* It's just us, act on the item. */
2117		/* will NOT drop writer lock when done */
2118		ng_apply_item(node, item, 0);
2119
2120		/*
2121		 * Having acted on the item, atomically
2122		 * downgrade back to READER and finish up.
2123	 	 */
2124		atomic_add_int(&ngq->q_flags, READER_INCREMENT - WRITER_ACTIVE);
2125
2126		/* Our caller will call ng_leave_read() */
2127		return;
2128	}
2129	/*
2130	 * It's not just us active, so queue us AT THE HEAD.
2131	 * "Why?" I hear you ask.
2132	 * Put us at the head of the queue as we've already been
2133	 * through it once. If there is nothing else waiting,
2134	 * set the correct flags.
2135	 */
2136	if (STAILQ_EMPTY(&ngq->queue)) {
2137		/* We've gone from, 0 to 1 item in the queue */
2138		atomic_set_int(&ngq->q_flags, OP_PENDING);
2139
2140		CTR3(KTR_NET, "%20s: node [%x] (%p) set OP_PENDING", __func__,
2141		    node->nd_ID, node);
2142	};
2143	STAILQ_INSERT_HEAD(&ngq->queue, item, el_next);
2144	CTR4(KTR_NET, "%20s: node [%x] (%p) requeued item %p as WRITER",
2145	    __func__, node->nd_ID, node, item );
2146
2147	/* Reverse what we did above. That downgrades us back to reader */
2148	atomic_add_int(&ngq->q_flags, READER_INCREMENT - WRITER_ACTIVE);
2149	if (QUEUE_ACTIVE(ngq) && NEXT_QUEUED_ITEM_CAN_PROCEED(ngq))
2150		ng_worklist_add(node);
2151	NG_QUEUE_UNLOCK(ngq);
2152
2153	return;
2154}
2155#endif
2156
2157/* Release reader lock. */
2158static __inline void
2159ng_leave_read(node_p node)
2160{
2161	atomic_subtract_rel_int(&node->nd_input_queue.q_flags, READER_INCREMENT);
2162}
2163
2164/* Release writer lock. */
2165static __inline void
2166ng_leave_write(node_p node)
2167{
2168	atomic_clear_rel_int(&node->nd_input_queue.q_flags, WRITER_ACTIVE);
2169}
2170
2171/* Purge node queue. Called on node shutdown. */
2172static void
2173ng_flush_input_queue(node_p node)
2174{
2175	struct ng_queue *ngq = &node->nd_input_queue;
2176	item_p item;
2177
2178	NG_QUEUE_LOCK(ngq);
2179	while ((item = STAILQ_FIRST(&ngq->queue)) != NULL) {
2180		STAILQ_REMOVE_HEAD(&ngq->queue, el_next);
2181		if (STAILQ_EMPTY(&ngq->queue))
2182			atomic_clear_int(&ngq->q_flags, OP_PENDING);
2183		NG_QUEUE_UNLOCK(ngq);
2184
2185		/* If the item is supplying a callback, call it with an error */
2186		if (item->apply != NULL) {
2187			if (item->depth == 1)
2188				item->apply->error = ENOENT;
2189			if (refcount_release(&item->apply->refs)) {
2190				(*item->apply->apply)(item->apply->context,
2191				    item->apply->error);
2192			}
2193		}
2194		NG_FREE_ITEM(item);
2195		NG_QUEUE_LOCK(ngq);
2196	}
2197	NG_QUEUE_UNLOCK(ngq);
2198}
2199
2200/***********************************************************************
2201* Externally visible method for sending or queueing messages or data.
2202***********************************************************************/
2203
2204/*
2205 * The module code should have filled out the item correctly by this stage:
2206 * Common:
2207 *    reference to destination node.
2208 *    Reference to destination rcv hook if relevant.
2209 *    apply pointer must be or NULL or reference valid struct ng_apply_info.
2210 * Data:
2211 *    pointer to mbuf
2212 * Control_Message:
2213 *    pointer to msg.
2214 *    ID of original sender node. (return address)
2215 * Function:
2216 *    Function pointer
2217 *    void * argument
2218 *    integer argument
2219 *
2220 * The nodes have several routines and macros to help with this task:
2221 */
2222
2223int
2224ng_snd_item(item_p item, int flags)
2225{
2226	hook_p hook;
2227	node_p node;
2228	int queue, rw;
2229	struct ng_queue *ngq;
2230	int error = 0;
2231
2232	/* We are sending item, so it must be present! */
2233	KASSERT(item != NULL, ("ng_snd_item: item is NULL"));
2234
2235#ifdef	NETGRAPH_DEBUG
2236	_ngi_check(item, __FILE__, __LINE__);
2237#endif
2238
2239	/* Item was sent once more, postpone apply() call. */
2240	if (item->apply)
2241		refcount_acquire(&item->apply->refs);
2242
2243	node = NGI_NODE(item);
2244	/* Node is never optional. */
2245	KASSERT(node != NULL, ("ng_snd_item: node is NULL"));
2246
2247	hook = NGI_HOOK(item);
2248	/* Valid hook and mbuf are mandatory for data. */
2249	if ((item->el_flags & NGQF_TYPE) == NGQF_DATA) {
2250		KASSERT(hook != NULL, ("ng_snd_item: hook for data is NULL"));
2251		if (NGI_M(item) == NULL)
2252			ERROUT(EINVAL);
2253		CHECK_DATA_MBUF(NGI_M(item));
2254	}
2255
2256	/*
2257	 * If the item or the node specifies single threading, force
2258	 * writer semantics. Similarly, the node may say one hook always
2259	 * produces writers. These are overrides.
2260	 */
2261	if (((item->el_flags & NGQF_RW) == NGQF_WRITER) ||
2262	    (node->nd_flags & NGF_FORCE_WRITER) ||
2263	    (hook && (hook->hk_flags & HK_FORCE_WRITER))) {
2264		rw = NGQRW_W;
2265	} else {
2266		rw = NGQRW_R;
2267	}
2268
2269	/*
2270	 * If sender or receiver requests queued delivery, or call graph
2271	 * loops back from outbound to inbound path, or stack usage
2272	 * level is dangerous - enqueue message.
2273	 */
2274	if ((flags & NG_QUEUE) || (hook && (hook->hk_flags & HK_QUEUE))) {
2275		queue = 1;
2276	} else if (hook && (hook->hk_flags & HK_TO_INBOUND) &&
2277	    curthread->td_ng_outbound) {
2278		queue = 1;
2279	} else {
2280		queue = 0;
2281#ifdef GET_STACK_USAGE
2282		/*
2283		 * Most of netgraph nodes have small stack consumption and
2284		 * for them 25% of free stack space is more than enough.
2285		 * Nodes/hooks with higher stack usage should be marked as
2286		 * HI_STACK. For them 50% of stack will be guaranteed then.
2287		 * XXX: Values 25% and 50% are completely empirical.
2288		 */
2289		size_t	st, su, sl;
2290		GET_STACK_USAGE(st, su);
2291		sl = st - su;
2292		if ((sl * 4 < st) || ((sl * 2 < st) &&
2293		    ((node->nd_flags & NGF_HI_STACK) || (hook &&
2294		    (hook->hk_flags & HK_HI_STACK)))))
2295			queue = 1;
2296#endif
2297	}
2298
2299	if (queue) {
2300		/* Put it on the queue for that node*/
2301		ng_queue_rw(node, item, rw);
2302		return ((flags & NG_PROGRESS) ? EINPROGRESS : 0);
2303	}
2304
2305	/*
2306	 * We already decided how we will be queueud or treated.
2307	 * Try get the appropriate operating permission.
2308	 */
2309 	if (rw == NGQRW_R)
2310		item = ng_acquire_read(node, item);
2311	else
2312		item = ng_acquire_write(node, item);
2313
2314	/* Item was queued while trying to get permission. */
2315	if (item == NULL)
2316		return ((flags & NG_PROGRESS) ? EINPROGRESS : 0);
2317
2318	NGI_GET_NODE(item, node); /* zaps stored node */
2319
2320	item->depth++;
2321	error = ng_apply_item(node, item, rw); /* drops r/w lock when done */
2322
2323	/* If something is waiting on queue and ready, schedule it. */
2324	ngq = &node->nd_input_queue;
2325	if (QUEUE_ACTIVE(ngq)) {
2326		NG_QUEUE_LOCK(ngq);
2327		if (QUEUE_ACTIVE(ngq) && NEXT_QUEUED_ITEM_CAN_PROCEED(ngq))
2328			ng_worklist_add(node);
2329		NG_QUEUE_UNLOCK(ngq);
2330	}
2331
2332	/*
2333	 * Node may go away as soon as we remove the reference.
2334	 * Whatever we do, DO NOT access the node again!
2335	 */
2336	NG_NODE_UNREF(node);
2337
2338	return (error);
2339
2340done:
2341	/* If was not sent, apply callback here. */
2342	if (item->apply != NULL) {
2343		if (item->depth == 0 && error != 0)
2344			item->apply->error = error;
2345		if (refcount_release(&item->apply->refs)) {
2346			(*item->apply->apply)(item->apply->context,
2347			    item->apply->error);
2348		}
2349	}
2350
2351	NG_FREE_ITEM(item);
2352	return (error);
2353}
2354
2355/*
2356 * We have an item that was possibly queued somewhere.
2357 * It should contain all the information needed
2358 * to run it on the appropriate node/hook.
2359 * If there is apply pointer and we own the last reference, call apply().
2360 */
2361static int
2362ng_apply_item(node_p node, item_p item, int rw)
2363{
2364	hook_p  hook;
2365	ng_rcvdata_t *rcvdata;
2366	ng_rcvmsg_t *rcvmsg;
2367	struct ng_apply_info *apply;
2368	int	error = 0, depth;
2369
2370	/* Node and item are never optional. */
2371	KASSERT(node != NULL, ("ng_apply_item: node is NULL"));
2372	KASSERT(item != NULL, ("ng_apply_item: item is NULL"));
2373
2374	NGI_GET_HOOK(item, hook); /* clears stored hook */
2375#ifdef	NETGRAPH_DEBUG
2376	_ngi_check(item, __FILE__, __LINE__);
2377#endif
2378
2379	apply = item->apply;
2380	depth = item->depth;
2381
2382	switch (item->el_flags & NGQF_TYPE) {
2383	case NGQF_DATA:
2384		/*
2385		 * Check things are still ok as when we were queued.
2386		 */
2387		KASSERT(hook != NULL, ("ng_apply_item: hook for data is NULL"));
2388		if (NG_HOOK_NOT_VALID(hook) ||
2389		    NG_NODE_NOT_VALID(node)) {
2390			error = EIO;
2391			NG_FREE_ITEM(item);
2392			break;
2393		}
2394		/*
2395		 * If no receive method, just silently drop it.
2396		 * Give preference to the hook over-ride method.
2397		 */
2398		if ((!(rcvdata = hook->hk_rcvdata)) &&
2399		    (!(rcvdata = NG_HOOK_NODE(hook)->nd_type->rcvdata))) {
2400			error = 0;
2401			NG_FREE_ITEM(item);
2402			break;
2403		}
2404		error = (*rcvdata)(hook, item);
2405		break;
2406	case NGQF_MESG:
2407		if (hook && NG_HOOK_NOT_VALID(hook)) {
2408			/*
2409			 * The hook has been zapped then we can't use it.
2410			 * Immediately drop its reference.
2411			 * The message may not need it.
2412			 */
2413			NG_HOOK_UNREF(hook);
2414			hook = NULL;
2415		}
2416		/*
2417		 * Similarly, if the node is a zombie there is
2418		 * nothing we can do with it, drop everything.
2419		 */
2420		if (NG_NODE_NOT_VALID(node)) {
2421			TRAP_ERROR();
2422			error = EINVAL;
2423			NG_FREE_ITEM(item);
2424			break;
2425		}
2426		/*
2427		 * Call the appropriate message handler for the object.
2428		 * It is up to the message handler to free the message.
2429		 * If it's a generic message, handle it generically,
2430		 * otherwise call the type's message handler (if it exists).
2431		 * XXX (race). Remember that a queued message may
2432		 * reference a node or hook that has just been
2433		 * invalidated. It will exist as the queue code
2434		 * is holding a reference, but..
2435		 */
2436		if ((NGI_MSG(item)->header.typecookie == NGM_GENERIC_COOKIE) &&
2437		    ((NGI_MSG(item)->header.flags & NGF_RESP) == 0)) {
2438			error = ng_generic_msg(node, item, hook);
2439			break;
2440		}
2441		if (((!hook) || (!(rcvmsg = hook->hk_rcvmsg))) &&
2442		    (!(rcvmsg = node->nd_type->rcvmsg))) {
2443			TRAP_ERROR();
2444			error = 0;
2445			NG_FREE_ITEM(item);
2446			break;
2447		}
2448		error = (*rcvmsg)(node, item, hook);
2449		break;
2450	case NGQF_FN:
2451	case NGQF_FN2:
2452		/*
2453		 * In the case of the shutdown message we allow it to hit
2454		 * even if the node is invalid.
2455		 */
2456		if (NG_NODE_NOT_VALID(node) &&
2457		    NGI_FN(item) != &ng_rmnode) {
2458			TRAP_ERROR();
2459			error = EINVAL;
2460			NG_FREE_ITEM(item);
2461			break;
2462		}
2463		/* Same is about some internal functions and invalid hook. */
2464		if (hook && NG_HOOK_NOT_VALID(hook) &&
2465		    NGI_FN2(item) != &ng_con_part2 &&
2466		    NGI_FN2(item) != &ng_con_part3 &&
2467		    NGI_FN(item) != &ng_rmhook_part2) {
2468			TRAP_ERROR();
2469			error = EINVAL;
2470			NG_FREE_ITEM(item);
2471			break;
2472		}
2473
2474		if ((item->el_flags & NGQF_TYPE) == NGQF_FN) {
2475			(*NGI_FN(item))(node, hook, NGI_ARG1(item),
2476			    NGI_ARG2(item));
2477			NG_FREE_ITEM(item);
2478		} else	/* it is NGQF_FN2 */
2479			error = (*NGI_FN2(item))(node, item, hook);
2480		break;
2481	}
2482	/*
2483	 * We held references on some of the resources
2484	 * that we took from the item. Now that we have
2485	 * finished doing everything, drop those references.
2486	 */
2487	if (hook)
2488		NG_HOOK_UNREF(hook);
2489
2490 	if (rw == NGQRW_R)
2491		ng_leave_read(node);
2492	else
2493		ng_leave_write(node);
2494
2495	/* Apply callback. */
2496	if (apply != NULL) {
2497		if (depth == 1 && error != 0)
2498			apply->error = error;
2499		if (refcount_release(&apply->refs))
2500			(*apply->apply)(apply->context, apply->error);
2501	}
2502
2503	return (error);
2504}
2505
2506/***********************************************************************
2507 * Implement the 'generic' control messages
2508 ***********************************************************************/
2509static int
2510ng_generic_msg(node_p here, item_p item, hook_p lasthook)
2511{
2512	int error = 0;
2513	struct ng_mesg *msg;
2514	struct ng_mesg *resp = NULL;
2515
2516	NGI_GET_MSG(item, msg);
2517	if (msg->header.typecookie != NGM_GENERIC_COOKIE) {
2518		TRAP_ERROR();
2519		error = EINVAL;
2520		goto out;
2521	}
2522	switch (msg->header.cmd) {
2523	case NGM_SHUTDOWN:
2524		ng_rmnode(here, NULL, NULL, 0);
2525		break;
2526	case NGM_MKPEER:
2527	    {
2528		struct ngm_mkpeer *const mkp = (struct ngm_mkpeer *) msg->data;
2529
2530		if (msg->header.arglen != sizeof(*mkp)) {
2531			TRAP_ERROR();
2532			error = EINVAL;
2533			break;
2534		}
2535		mkp->type[sizeof(mkp->type) - 1] = '\0';
2536		mkp->ourhook[sizeof(mkp->ourhook) - 1] = '\0';
2537		mkp->peerhook[sizeof(mkp->peerhook) - 1] = '\0';
2538		error = ng_mkpeer(here, mkp->ourhook, mkp->peerhook, mkp->type);
2539		break;
2540	    }
2541	case NGM_CONNECT:
2542	    {
2543		struct ngm_connect *const con =
2544			(struct ngm_connect *) msg->data;
2545		node_p node2;
2546
2547		if (msg->header.arglen != sizeof(*con)) {
2548			TRAP_ERROR();
2549			error = EINVAL;
2550			break;
2551		}
2552		con->path[sizeof(con->path) - 1] = '\0';
2553		con->ourhook[sizeof(con->ourhook) - 1] = '\0';
2554		con->peerhook[sizeof(con->peerhook) - 1] = '\0';
2555		/* Don't forget we get a reference.. */
2556		error = ng_path2noderef(here, con->path, &node2, NULL);
2557		if (error)
2558			break;
2559		error = ng_con_nodes(item, here, con->ourhook,
2560		    node2, con->peerhook);
2561		NG_NODE_UNREF(node2);
2562		break;
2563	    }
2564	case NGM_NAME:
2565	    {
2566		struct ngm_name *const nam = (struct ngm_name *) msg->data;
2567
2568		if (msg->header.arglen != sizeof(*nam)) {
2569			TRAP_ERROR();
2570			error = EINVAL;
2571			break;
2572		}
2573		nam->name[sizeof(nam->name) - 1] = '\0';
2574		error = ng_name_node(here, nam->name);
2575		break;
2576	    }
2577	case NGM_RMHOOK:
2578	    {
2579		struct ngm_rmhook *const rmh = (struct ngm_rmhook *) msg->data;
2580		hook_p hook;
2581
2582		if (msg->header.arglen != sizeof(*rmh)) {
2583			TRAP_ERROR();
2584			error = EINVAL;
2585			break;
2586		}
2587		rmh->ourhook[sizeof(rmh->ourhook) - 1] = '\0';
2588		if ((hook = ng_findhook(here, rmh->ourhook)) != NULL)
2589			ng_destroy_hook(hook);
2590		break;
2591	    }
2592	case NGM_NODEINFO:
2593	    {
2594		struct nodeinfo *ni;
2595
2596		NG_MKRESPONSE(resp, msg, sizeof(*ni), M_NOWAIT);
2597		if (resp == NULL) {
2598			error = ENOMEM;
2599			break;
2600		}
2601
2602		/* Fill in node info */
2603		ni = (struct nodeinfo *) resp->data;
2604		if (NG_NODE_HAS_NAME(here))
2605			strcpy(ni->name, NG_NODE_NAME(here));
2606		strcpy(ni->type, here->nd_type->name);
2607		ni->id = ng_node2ID(here);
2608		ni->hooks = here->nd_numhooks;
2609		break;
2610	    }
2611	case NGM_LISTHOOKS:
2612	    {
2613		const int nhooks = here->nd_numhooks;
2614		struct hooklist *hl;
2615		struct nodeinfo *ni;
2616		hook_p hook;
2617
2618		/* Get response struct */
2619		NG_MKRESPONSE(resp, msg, sizeof(*hl) +
2620		    (nhooks * sizeof(struct linkinfo)), M_NOWAIT);
2621		if (resp == NULL) {
2622			error = ENOMEM;
2623			break;
2624		}
2625		hl = (struct hooklist *) resp->data;
2626		ni = &hl->nodeinfo;
2627
2628		/* Fill in node info */
2629		if (NG_NODE_HAS_NAME(here))
2630			strcpy(ni->name, NG_NODE_NAME(here));
2631		strcpy(ni->type, here->nd_type->name);
2632		ni->id = ng_node2ID(here);
2633
2634		/* Cycle through the linked list of hooks */
2635		ni->hooks = 0;
2636		LIST_FOREACH(hook, &here->nd_hooks, hk_hooks) {
2637			struct linkinfo *const link = &hl->link[ni->hooks];
2638
2639			if (ni->hooks >= nhooks) {
2640				log(LOG_ERR, "%s: number of %s changed\n",
2641				    __func__, "hooks");
2642				break;
2643			}
2644			if (NG_HOOK_NOT_VALID(hook))
2645				continue;
2646			strcpy(link->ourhook, NG_HOOK_NAME(hook));
2647			strcpy(link->peerhook, NG_PEER_HOOK_NAME(hook));
2648			if (NG_PEER_NODE_NAME(hook)[0] != '\0')
2649				strcpy(link->nodeinfo.name,
2650				    NG_PEER_NODE_NAME(hook));
2651			strcpy(link->nodeinfo.type,
2652			   NG_PEER_NODE(hook)->nd_type->name);
2653			link->nodeinfo.id = ng_node2ID(NG_PEER_NODE(hook));
2654			link->nodeinfo.hooks = NG_PEER_NODE(hook)->nd_numhooks;
2655			ni->hooks++;
2656		}
2657		break;
2658	    }
2659
2660	case NGM_LISTNODES:
2661	    {
2662		struct namelist *nl;
2663		node_p node;
2664		int i;
2665
2666		IDHASH_RLOCK();
2667		/* Get response struct. */
2668		NG_MKRESPONSE(resp, msg, sizeof(*nl) +
2669		    (V_ng_nodes * sizeof(struct nodeinfo)), M_NOWAIT);
2670		if (resp == NULL) {
2671			IDHASH_RUNLOCK();
2672			error = ENOMEM;
2673			break;
2674		}
2675		nl = (struct namelist *) resp->data;
2676
2677		/* Cycle through the lists of nodes. */
2678		nl->numnames = 0;
2679		for (i = 0; i <= V_ng_ID_hmask; i++) {
2680			LIST_FOREACH(node, &V_ng_ID_hash[i], nd_idnodes) {
2681				struct nodeinfo *const np =
2682				    &nl->nodeinfo[nl->numnames];
2683
2684				if (NG_NODE_NOT_VALID(node))
2685					continue;
2686				if (NG_NODE_HAS_NAME(node))
2687					strcpy(np->name, NG_NODE_NAME(node));
2688				strcpy(np->type, node->nd_type->name);
2689				np->id = ng_node2ID(node);
2690				np->hooks = node->nd_numhooks;
2691				KASSERT(nl->numnames < V_ng_nodes,
2692				    ("%s: no space", __func__));
2693				nl->numnames++;
2694			}
2695		}
2696		IDHASH_RUNLOCK();
2697		break;
2698	    }
2699	case NGM_LISTNAMES:
2700	    {
2701		struct namelist *nl;
2702		node_p node;
2703		int i;
2704
2705		NAMEHASH_RLOCK();
2706		/* Get response struct. */
2707		NG_MKRESPONSE(resp, msg, sizeof(*nl) +
2708		    (V_ng_named_nodes * sizeof(struct nodeinfo)), M_NOWAIT);
2709		if (resp == NULL) {
2710			NAMEHASH_RUNLOCK();
2711			error = ENOMEM;
2712			break;
2713		}
2714		nl = (struct namelist *) resp->data;
2715
2716		/* Cycle through the lists of nodes. */
2717		nl->numnames = 0;
2718		for (i = 0; i <= V_ng_name_hmask; i++) {
2719			LIST_FOREACH(node, &V_ng_name_hash[i], nd_nodes) {
2720				struct nodeinfo *const np =
2721				    &nl->nodeinfo[nl->numnames];
2722
2723				if (NG_NODE_NOT_VALID(node))
2724					continue;
2725				strcpy(np->name, NG_NODE_NAME(node));
2726				strcpy(np->type, node->nd_type->name);
2727				np->id = ng_node2ID(node);
2728				np->hooks = node->nd_numhooks;
2729				KASSERT(nl->numnames < V_ng_named_nodes,
2730				    ("%s: no space", __func__));
2731				nl->numnames++;
2732			}
2733		}
2734		NAMEHASH_RUNLOCK();
2735		break;
2736	    }
2737
2738	case NGM_LISTTYPES:
2739	    {
2740		struct typelist *tl;
2741		struct ng_type *type;
2742		int num = 0;
2743
2744		TYPELIST_RLOCK();
2745		/* Count number of types */
2746		LIST_FOREACH(type, &ng_typelist, types)
2747			num++;
2748
2749		/* Get response struct */
2750		NG_MKRESPONSE(resp, msg, sizeof(*tl) +
2751		    (num * sizeof(struct typeinfo)), M_NOWAIT);
2752		if (resp == NULL) {
2753			TYPELIST_RUNLOCK();
2754			error = ENOMEM;
2755			break;
2756		}
2757		tl = (struct typelist *) resp->data;
2758
2759		/* Cycle through the linked list of types */
2760		tl->numtypes = 0;
2761		LIST_FOREACH(type, &ng_typelist, types) {
2762			struct typeinfo *const tp = &tl->typeinfo[tl->numtypes];
2763
2764			strcpy(tp->type_name, type->name);
2765			tp->numnodes = type->refs - 1; /* don't count list */
2766			KASSERT(tl->numtypes < num, ("%s: no space", __func__));
2767			tl->numtypes++;
2768		}
2769		TYPELIST_RUNLOCK();
2770		break;
2771	    }
2772
2773	case NGM_BINARY2ASCII:
2774	    {
2775		int bufSize = 20 * 1024;	/* XXX hard coded constant */
2776		const struct ng_parse_type *argstype;
2777		const struct ng_cmdlist *c;
2778		struct ng_mesg *binary, *ascii;
2779
2780		/* Data area must contain a valid netgraph message */
2781		binary = (struct ng_mesg *)msg->data;
2782		if (msg->header.arglen < sizeof(struct ng_mesg) ||
2783		    (msg->header.arglen - sizeof(struct ng_mesg) <
2784		    binary->header.arglen)) {
2785			TRAP_ERROR();
2786			error = EINVAL;
2787			break;
2788		}
2789
2790		/* Get a response message with lots of room */
2791		NG_MKRESPONSE(resp, msg, sizeof(*ascii) + bufSize, M_NOWAIT);
2792		if (resp == NULL) {
2793			error = ENOMEM;
2794			break;
2795		}
2796		ascii = (struct ng_mesg *)resp->data;
2797
2798		/* Copy binary message header to response message payload */
2799		bcopy(binary, ascii, sizeof(*binary));
2800
2801		/* Find command by matching typecookie and command number */
2802		for (c = here->nd_type->cmdlist; c != NULL && c->name != NULL;
2803		    c++) {
2804			if (binary->header.typecookie == c->cookie &&
2805			    binary->header.cmd == c->cmd)
2806				break;
2807		}
2808		if (c == NULL || c->name == NULL) {
2809			for (c = ng_generic_cmds; c->name != NULL; c++) {
2810				if (binary->header.typecookie == c->cookie &&
2811				    binary->header.cmd == c->cmd)
2812					break;
2813			}
2814			if (c->name == NULL) {
2815				NG_FREE_MSG(resp);
2816				error = ENOSYS;
2817				break;
2818			}
2819		}
2820
2821		/* Convert command name to ASCII */
2822		snprintf(ascii->header.cmdstr, sizeof(ascii->header.cmdstr),
2823		    "%s", c->name);
2824
2825		/* Convert command arguments to ASCII */
2826		argstype = (binary->header.flags & NGF_RESP) ?
2827		    c->respType : c->mesgType;
2828		if (argstype == NULL) {
2829			*ascii->data = '\0';
2830		} else {
2831			if ((error = ng_unparse(argstype,
2832			    (u_char *)binary->data,
2833			    ascii->data, bufSize)) != 0) {
2834				NG_FREE_MSG(resp);
2835				break;
2836			}
2837		}
2838
2839		/* Return the result as struct ng_mesg plus ASCII string */
2840		bufSize = strlen(ascii->data) + 1;
2841		ascii->header.arglen = bufSize;
2842		resp->header.arglen = sizeof(*ascii) + bufSize;
2843		break;
2844	    }
2845
2846	case NGM_ASCII2BINARY:
2847	    {
2848		int bufSize = 20 * 1024;	/* XXX hard coded constant */
2849		const struct ng_cmdlist *c;
2850		const struct ng_parse_type *argstype;
2851		struct ng_mesg *ascii, *binary;
2852		int off = 0;
2853
2854		/* Data area must contain at least a struct ng_mesg + '\0' */
2855		ascii = (struct ng_mesg *)msg->data;
2856		if ((msg->header.arglen < sizeof(*ascii) + 1) ||
2857		    (ascii->header.arglen < 1) ||
2858		    (msg->header.arglen < sizeof(*ascii) +
2859		    ascii->header.arglen)) {
2860			TRAP_ERROR();
2861			error = EINVAL;
2862			break;
2863		}
2864		ascii->data[ascii->header.arglen - 1] = '\0';
2865
2866		/* Get a response message with lots of room */
2867		NG_MKRESPONSE(resp, msg, sizeof(*binary) + bufSize, M_NOWAIT);
2868		if (resp == NULL) {
2869			error = ENOMEM;
2870			break;
2871		}
2872		binary = (struct ng_mesg *)resp->data;
2873
2874		/* Copy ASCII message header to response message payload */
2875		bcopy(ascii, binary, sizeof(*ascii));
2876
2877		/* Find command by matching ASCII command string */
2878		for (c = here->nd_type->cmdlist;
2879		    c != NULL && c->name != NULL; c++) {
2880			if (strcmp(ascii->header.cmdstr, c->name) == 0)
2881				break;
2882		}
2883		if (c == NULL || c->name == NULL) {
2884			for (c = ng_generic_cmds; c->name != NULL; c++) {
2885				if (strcmp(ascii->header.cmdstr, c->name) == 0)
2886					break;
2887			}
2888			if (c->name == NULL) {
2889				NG_FREE_MSG(resp);
2890				error = ENOSYS;
2891				break;
2892			}
2893		}
2894
2895		/* Convert command name to binary */
2896		binary->header.cmd = c->cmd;
2897		binary->header.typecookie = c->cookie;
2898
2899		/* Convert command arguments to binary */
2900		argstype = (binary->header.flags & NGF_RESP) ?
2901		    c->respType : c->mesgType;
2902		if (argstype == NULL) {
2903			bufSize = 0;
2904		} else {
2905			if ((error = ng_parse(argstype, ascii->data, &off,
2906			    (u_char *)binary->data, &bufSize)) != 0) {
2907				NG_FREE_MSG(resp);
2908				break;
2909			}
2910		}
2911
2912		/* Return the result */
2913		binary->header.arglen = bufSize;
2914		resp->header.arglen = sizeof(*binary) + bufSize;
2915		break;
2916	    }
2917
2918	case NGM_TEXT_CONFIG:
2919	case NGM_TEXT_STATUS:
2920		/*
2921		 * This one is tricky as it passes the command down to the
2922		 * actual node, even though it is a generic type command.
2923		 * This means we must assume that the item/msg is already freed
2924		 * when control passes back to us.
2925		 */
2926		if (here->nd_type->rcvmsg != NULL) {
2927			NGI_MSG(item) = msg; /* put it back as we found it */
2928			return((*here->nd_type->rcvmsg)(here, item, lasthook));
2929		}
2930		/* Fall through if rcvmsg not supported */
2931	default:
2932		TRAP_ERROR();
2933		error = EINVAL;
2934	}
2935	/*
2936	 * Sometimes a generic message may be statically allocated
2937	 * to avoid problems with allocating when in tight memory situations.
2938	 * Don't free it if it is so.
2939	 * I break them apart here, because erros may cause a free if the item
2940	 * in which case we'd be doing it twice.
2941	 * they are kept together above, to simplify freeing.
2942	 */
2943out:
2944	NG_RESPOND_MSG(error, here, item, resp);
2945	NG_FREE_MSG(msg);
2946	return (error);
2947}
2948
2949/************************************************************************
2950			Queue element get/free routines
2951************************************************************************/
2952
2953uma_zone_t			ng_qzone;
2954uma_zone_t			ng_qdzone;
2955static int			numthreads = 0; /* number of queue threads */
2956static int			maxalloc = 4096;/* limit the damage of a leak */
2957static int			maxdata = 4096;	/* limit the damage of a DoS */
2958
2959SYSCTL_INT(_net_graph, OID_AUTO, threads, CTLFLAG_RDTUN, &numthreads,
2960    0, "Number of queue processing threads");
2961SYSCTL_INT(_net_graph, OID_AUTO, maxalloc, CTLFLAG_RDTUN, &maxalloc,
2962    0, "Maximum number of non-data queue items to allocate");
2963SYSCTL_INT(_net_graph, OID_AUTO, maxdata, CTLFLAG_RDTUN, &maxdata,
2964    0, "Maximum number of data queue items to allocate");
2965
2966#ifdef	NETGRAPH_DEBUG
2967static TAILQ_HEAD(, ng_item) ng_itemlist = TAILQ_HEAD_INITIALIZER(ng_itemlist);
2968static int allocated;	/* number of items malloc'd */
2969#endif
2970
2971/*
2972 * Get a queue entry.
2973 * This is usually called when a packet first enters netgraph.
2974 * By definition, this is usually from an interrupt, or from a user.
2975 * Users are not so important, but try be quick for the times that it's
2976 * an interrupt.
2977 */
2978static __inline item_p
2979ng_alloc_item(int type, int flags)
2980{
2981	item_p item;
2982
2983	KASSERT(((type & ~NGQF_TYPE) == 0),
2984	    ("%s: incorrect item type: %d", __func__, type));
2985
2986	item = uma_zalloc((type == NGQF_DATA) ? ng_qdzone : ng_qzone,
2987	    ((flags & NG_WAITOK) ? M_WAITOK : M_NOWAIT) | M_ZERO);
2988
2989	if (item) {
2990		item->el_flags = type;
2991#ifdef	NETGRAPH_DEBUG
2992		mtx_lock(&ngq_mtx);
2993		TAILQ_INSERT_TAIL(&ng_itemlist, item, all);
2994		allocated++;
2995		mtx_unlock(&ngq_mtx);
2996#endif
2997	}
2998
2999	return (item);
3000}
3001
3002/*
3003 * Release a queue entry
3004 */
3005void
3006ng_free_item(item_p item)
3007{
3008	/*
3009	 * The item may hold resources on its own. We need to free
3010	 * these before we can free the item. What they are depends upon
3011	 * what kind of item it is. it is important that nodes zero
3012	 * out pointers to resources that they remove from the item
3013	 * or we release them again here.
3014	 */
3015	switch (item->el_flags & NGQF_TYPE) {
3016	case NGQF_DATA:
3017		/* If we have an mbuf still attached.. */
3018		NG_FREE_M(_NGI_M(item));
3019		break;
3020	case NGQF_MESG:
3021		_NGI_RETADDR(item) = 0;
3022		NG_FREE_MSG(_NGI_MSG(item));
3023		break;
3024	case NGQF_FN:
3025	case NGQF_FN2:
3026		/* nothing to free really, */
3027		_NGI_FN(item) = NULL;
3028		_NGI_ARG1(item) = NULL;
3029		_NGI_ARG2(item) = 0;
3030		break;
3031	}
3032	/* If we still have a node or hook referenced... */
3033	_NGI_CLR_NODE(item);
3034	_NGI_CLR_HOOK(item);
3035
3036#ifdef	NETGRAPH_DEBUG
3037	mtx_lock(&ngq_mtx);
3038	TAILQ_REMOVE(&ng_itemlist, item, all);
3039	allocated--;
3040	mtx_unlock(&ngq_mtx);
3041#endif
3042	uma_zfree(((item->el_flags & NGQF_TYPE) == NGQF_DATA) ?
3043	    ng_qdzone : ng_qzone, item);
3044}
3045
3046/*
3047 * Change type of the queue entry.
3048 * Possibly reallocates it from another UMA zone.
3049 */
3050static __inline item_p
3051ng_realloc_item(item_p pitem, int type, int flags)
3052{
3053	item_p item;
3054	int from, to;
3055
3056	KASSERT((pitem != NULL), ("%s: can't reallocate NULL", __func__));
3057	KASSERT(((type & ~NGQF_TYPE) == 0),
3058	    ("%s: incorrect item type: %d", __func__, type));
3059
3060	from = ((pitem->el_flags & NGQF_TYPE) == NGQF_DATA);
3061	to = (type == NGQF_DATA);
3062	if (from != to) {
3063		/* If reallocation is required do it and copy item. */
3064		if ((item = ng_alloc_item(type, flags)) == NULL) {
3065			ng_free_item(pitem);
3066			return (NULL);
3067		}
3068		*item = *pitem;
3069		ng_free_item(pitem);
3070	} else
3071		item = pitem;
3072	item->el_flags = (item->el_flags & ~NGQF_TYPE) | type;
3073
3074	return (item);
3075}
3076
3077/************************************************************************
3078			Module routines
3079************************************************************************/
3080
3081/*
3082 * Handle the loading/unloading of a netgraph node type module
3083 */
3084int
3085ng_mod_event(module_t mod, int event, void *data)
3086{
3087	struct ng_type *const type = data;
3088	int error = 0;
3089
3090	switch (event) {
3091	case MOD_LOAD:
3092
3093		/* Register new netgraph node type */
3094		if ((error = ng_newtype(type)) != 0)
3095			break;
3096
3097		/* Call type specific code */
3098		if (type->mod_event != NULL)
3099			if ((error = (*type->mod_event)(mod, event, data))) {
3100				TYPELIST_WLOCK();
3101				type->refs--;	/* undo it */
3102				LIST_REMOVE(type, types);
3103				TYPELIST_WUNLOCK();
3104			}
3105		break;
3106
3107	case MOD_UNLOAD:
3108		if (type->refs > 1) {		/* make sure no nodes exist! */
3109			error = EBUSY;
3110		} else {
3111			if (type->refs == 0) /* failed load, nothing to undo */
3112				break;
3113			if (type->mod_event != NULL) {	/* check with type */
3114				error = (*type->mod_event)(mod, event, data);
3115				if (error != 0)	/* type refuses.. */
3116					break;
3117			}
3118			TYPELIST_WLOCK();
3119			LIST_REMOVE(type, types);
3120			TYPELIST_WUNLOCK();
3121		}
3122		break;
3123
3124	default:
3125		if (type->mod_event != NULL)
3126			error = (*type->mod_event)(mod, event, data);
3127		else
3128			error = EOPNOTSUPP;		/* XXX ? */
3129		break;
3130	}
3131	return (error);
3132}
3133
3134static void
3135vnet_netgraph_init(const void *unused __unused)
3136{
3137
3138	/* We start with small hashes, but they can grow. */
3139	V_ng_ID_hash = hashinit(16, M_NETGRAPH_NODE, &V_ng_ID_hmask);
3140	V_ng_name_hash = hashinit(16, M_NETGRAPH_NODE, &V_ng_name_hmask);
3141}
3142VNET_SYSINIT(vnet_netgraph_init, SI_SUB_NETGRAPH, SI_ORDER_FIRST,
3143    vnet_netgraph_init, NULL);
3144
3145#ifdef VIMAGE
3146static void
3147vnet_netgraph_uninit(const void *unused __unused)
3148{
3149	node_p node = NULL, last_killed = NULL;
3150	int i;
3151
3152	do {
3153		/* Find a node to kill */
3154		IDHASH_RLOCK();
3155		for (i = 0; i <= V_ng_ID_hmask; i++) {
3156			LIST_FOREACH(node, &V_ng_ID_hash[i], nd_idnodes) {
3157				if (node != &ng_deadnode) {
3158					NG_NODE_REF(node);
3159					break;
3160				}
3161			}
3162			if (node != NULL)
3163				break;
3164		}
3165		IDHASH_RUNLOCK();
3166
3167		/* Attempt to kill it only if it is a regular node */
3168		if (node != NULL) {
3169			if (node == last_killed) {
3170				/* This should never happen */
3171				printf("ng node %s needs NGF_REALLY_DIE\n",
3172				    node->nd_name);
3173				if (node->nd_flags & NGF_REALLY_DIE)
3174					panic("ng node %s won't die",
3175					    node->nd_name);
3176				node->nd_flags |= NGF_REALLY_DIE;
3177			}
3178			ng_rmnode(node, NULL, NULL, 0);
3179			NG_NODE_UNREF(node);
3180			last_killed = node;
3181		}
3182	} while (node != NULL);
3183
3184	hashdestroy(V_ng_name_hash, M_NETGRAPH_NODE, V_ng_name_hmask);
3185	hashdestroy(V_ng_ID_hash, M_NETGRAPH_NODE, V_ng_ID_hmask);
3186}
3187VNET_SYSUNINIT(vnet_netgraph_uninit, SI_SUB_NETGRAPH, SI_ORDER_FIRST,
3188    vnet_netgraph_uninit, NULL);
3189#endif /* VIMAGE */
3190
3191/*
3192 * Handle loading and unloading for this code.
3193 * The only thing we need to link into is the NETISR strucure.
3194 */
3195static int
3196ngb_mod_event(module_t mod, int event, void *data)
3197{
3198	struct proc *p;
3199	struct thread *td;
3200	int i, error = 0;
3201
3202	switch (event) {
3203	case MOD_LOAD:
3204		/* Initialize everything. */
3205		NG_WORKLIST_LOCK_INIT();
3206		rw_init(&ng_typelist_lock, "netgraph types");
3207		rw_init(&ng_idhash_lock, "netgraph idhash");
3208		rw_init(&ng_namehash_lock, "netgraph namehash");
3209		rw_init(&ng_topo_lock, "netgraph topology mutex");
3210#ifdef	NETGRAPH_DEBUG
3211		mtx_init(&ng_nodelist_mtx, "netgraph nodelist mutex", NULL,
3212		    MTX_DEF);
3213		mtx_init(&ngq_mtx, "netgraph item list mutex", NULL,
3214		    MTX_DEF);
3215#endif
3216		ng_qzone = uma_zcreate("NetGraph items", sizeof(struct ng_item),
3217		    NULL, NULL, NULL, NULL, UMA_ALIGN_CACHE, 0);
3218		uma_zone_set_max(ng_qzone, maxalloc);
3219		ng_qdzone = uma_zcreate("NetGraph data items",
3220		    sizeof(struct ng_item), NULL, NULL, NULL, NULL,
3221		    UMA_ALIGN_CACHE, 0);
3222		uma_zone_set_max(ng_qdzone, maxdata);
3223		/* Autoconfigure number of threads. */
3224		if (numthreads <= 0)
3225			numthreads = mp_ncpus;
3226		/* Create threads. */
3227    		p = NULL; /* start with no process */
3228		for (i = 0; i < numthreads; i++) {
3229			if (kproc_kthread_add(ngthread, NULL, &p, &td,
3230			    RFHIGHPID, 0, "ng_queue", "ng_queue%d", i)) {
3231				numthreads = i;
3232				break;
3233			}
3234		}
3235		break;
3236	case MOD_UNLOAD:
3237		/* You can't unload it because an interface may be using it. */
3238		error = EBUSY;
3239		break;
3240	default:
3241		error = EOPNOTSUPP;
3242		break;
3243	}
3244	return (error);
3245}
3246
3247static moduledata_t netgraph_mod = {
3248	"netgraph",
3249	ngb_mod_event,
3250	(NULL)
3251};
3252DECLARE_MODULE(netgraph, netgraph_mod, SI_SUB_NETGRAPH, SI_ORDER_FIRST);
3253SYSCTL_NODE(_net, OID_AUTO, graph, CTLFLAG_RW | CTLFLAG_MPSAFE, 0,
3254    "netgraph Family");
3255SYSCTL_INT(_net_graph, OID_AUTO, abi_version, CTLFLAG_RD, SYSCTL_NULL_INT_PTR, NG_ABI_VERSION,"");
3256SYSCTL_INT(_net_graph, OID_AUTO, msg_version, CTLFLAG_RD, SYSCTL_NULL_INT_PTR, NG_VERSION, "");
3257
3258#ifdef	NETGRAPH_DEBUG
3259void
3260dumphook (hook_p hook, char *file, int line)
3261{
3262	printf("hook: name %s, %d refs, Last touched:\n",
3263		_NG_HOOK_NAME(hook), hook->hk_refs);
3264	printf("	Last active @ %s, line %d\n",
3265		hook->lastfile, hook->lastline);
3266	if (line) {
3267		printf(" problem discovered at file %s, line %d\n", file, line);
3268#ifdef KDB
3269		kdb_backtrace();
3270#endif
3271	}
3272}
3273
3274void
3275dumpnode(node_p node, char *file, int line)
3276{
3277	printf("node: ID [%x]: type '%s', %d hooks, flags 0x%x, %d refs, %s:\n",
3278		_NG_NODE_ID(node), node->nd_type->name,
3279		node->nd_numhooks, node->nd_flags,
3280		node->nd_refs, node->nd_name);
3281	printf("	Last active @ %s, line %d\n",
3282		node->lastfile, node->lastline);
3283	if (line) {
3284		printf(" problem discovered at file %s, line %d\n", file, line);
3285#ifdef KDB
3286		kdb_backtrace();
3287#endif
3288	}
3289}
3290
3291void
3292dumpitem(item_p item, char *file, int line)
3293{
3294	printf(" ACTIVE item, last used at %s, line %d",
3295		item->lastfile, item->lastline);
3296	switch(item->el_flags & NGQF_TYPE) {
3297	case NGQF_DATA:
3298		printf(" - [data]\n");
3299		break;
3300	case NGQF_MESG:
3301		printf(" - retaddr[%d]:\n", _NGI_RETADDR(item));
3302		break;
3303	case NGQF_FN:
3304		printf(" - fn@%p (%p, %p, %p, %d (%x))\n",
3305			_NGI_FN(item),
3306			_NGI_NODE(item),
3307			_NGI_HOOK(item),
3308			item->body.fn.fn_arg1,
3309			item->body.fn.fn_arg2,
3310			item->body.fn.fn_arg2);
3311		break;
3312	case NGQF_FN2:
3313		printf(" - fn2@%p (%p, %p, %p, %d (%x))\n",
3314			_NGI_FN2(item),
3315			_NGI_NODE(item),
3316			_NGI_HOOK(item),
3317			item->body.fn.fn_arg1,
3318			item->body.fn.fn_arg2,
3319			item->body.fn.fn_arg2);
3320		break;
3321	}
3322	if (line) {
3323		printf(" problem discovered at file %s, line %d\n", file, line);
3324		if (_NGI_NODE(item)) {
3325			printf("node %p ([%x])\n",
3326				_NGI_NODE(item), ng_node2ID(_NGI_NODE(item)));
3327		}
3328	}
3329}
3330
3331static void
3332ng_dumpitems(void)
3333{
3334	item_p item;
3335	int i = 1;
3336	TAILQ_FOREACH(item, &ng_itemlist, all) {
3337		printf("[%d] ", i++);
3338		dumpitem(item, NULL, 0);
3339	}
3340}
3341
3342static void
3343ng_dumpnodes(void)
3344{
3345	node_p node;
3346	int i = 1;
3347	mtx_lock(&ng_nodelist_mtx);
3348	SLIST_FOREACH(node, &ng_allnodes, nd_all) {
3349		printf("[%d] ", i++);
3350		dumpnode(node, NULL, 0);
3351	}
3352	mtx_unlock(&ng_nodelist_mtx);
3353}
3354
3355static void
3356ng_dumphooks(void)
3357{
3358	hook_p hook;
3359	int i = 1;
3360	mtx_lock(&ng_nodelist_mtx);
3361	SLIST_FOREACH(hook, &ng_allhooks, hk_all) {
3362		printf("[%d] ", i++);
3363		dumphook(hook, NULL, 0);
3364	}
3365	mtx_unlock(&ng_nodelist_mtx);
3366}
3367
3368static int
3369sysctl_debug_ng_dump_items(SYSCTL_HANDLER_ARGS)
3370{
3371	int error;
3372	int val;
3373	int i;
3374
3375	val = allocated;
3376	i = 1;
3377	error = sysctl_handle_int(oidp, &val, 0, req);
3378	if (error != 0 || req->newptr == NULL)
3379		return (error);
3380	if (val == 42) {
3381		ng_dumpitems();
3382		ng_dumpnodes();
3383		ng_dumphooks();
3384	}
3385	return (0);
3386}
3387
3388SYSCTL_PROC(_debug, OID_AUTO, ng_dump_items,
3389    CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_NEEDGIANT, 0, sizeof(int),
3390    sysctl_debug_ng_dump_items, "I",
3391    "Number of allocated items");
3392#endif	/* NETGRAPH_DEBUG */
3393
3394/***********************************************************************
3395* Worklist routines
3396**********************************************************************/
3397/*
3398 * Pick a node off the list of nodes with work,
3399 * try get an item to process off it. Remove the node from the list.
3400 */
3401static void
3402ngthread(void *arg)
3403{
3404	for (;;) {
3405		struct epoch_tracker et;
3406		node_p  node;
3407
3408		/* Get node from the worklist. */
3409		NG_WORKLIST_LOCK();
3410		while ((node = STAILQ_FIRST(&ng_worklist)) == NULL)
3411			NG_WORKLIST_SLEEP();
3412		STAILQ_REMOVE_HEAD(&ng_worklist, nd_input_queue.q_work);
3413		NG_WORKLIST_UNLOCK();
3414		CURVNET_SET(node->nd_vnet);
3415		CTR3(KTR_NET, "%20s: node [%x] (%p) taken off worklist",
3416		    __func__, node->nd_ID, node);
3417		/*
3418		 * We have the node. We also take over the reference
3419		 * that the list had on it.
3420		 * Now process as much as you can, until it won't
3421		 * let you have another item off the queue.
3422		 * All this time, keep the reference
3423		 * that lets us be sure that the node still exists.
3424		 * Let the reference go at the last minute.
3425		 */
3426		NET_EPOCH_ENTER(et);
3427		for (;;) {
3428			item_p item;
3429			int rw;
3430
3431			NG_QUEUE_LOCK(&node->nd_input_queue);
3432			item = ng_dequeue(node, &rw);
3433			if (item == NULL) {
3434				node->nd_input_queue.q_flags2 &= ~NGQ2_WORKQ;
3435				NG_QUEUE_UNLOCK(&node->nd_input_queue);
3436				break; /* go look for another node */
3437			} else {
3438				NG_QUEUE_UNLOCK(&node->nd_input_queue);
3439				NGI_GET_NODE(item, node); /* zaps stored node */
3440				ng_apply_item(node, item, rw);
3441				NG_NODE_UNREF(node);
3442			}
3443		}
3444		NET_EPOCH_EXIT(et);
3445		NG_NODE_UNREF(node);
3446		CURVNET_RESTORE();
3447	}
3448}
3449
3450/*
3451 * XXX
3452 * It's posible that a debugging NG_NODE_REF may need
3453 * to be outside the mutex zone
3454 */
3455static void
3456ng_worklist_add(node_p node)
3457{
3458
3459	mtx_assert(&node->nd_input_queue.q_mtx, MA_OWNED);
3460
3461	if ((node->nd_input_queue.q_flags2 & NGQ2_WORKQ) == 0) {
3462		/*
3463		 * If we are not already on the work queue,
3464		 * then put us on.
3465		 */
3466		node->nd_input_queue.q_flags2 |= NGQ2_WORKQ;
3467		NG_NODE_REF(node); /* XXX safe in mutex? */
3468		NG_WORKLIST_LOCK();
3469		STAILQ_INSERT_TAIL(&ng_worklist, node, nd_input_queue.q_work);
3470		NG_WORKLIST_UNLOCK();
3471		CTR3(KTR_NET, "%20s: node [%x] (%p) put on worklist", __func__,
3472		    node->nd_ID, node);
3473		NG_WORKLIST_WAKEUP();
3474	} else {
3475		CTR3(KTR_NET, "%20s: node [%x] (%p) already on worklist",
3476		    __func__, node->nd_ID, node);
3477	}
3478}
3479
3480/***********************************************************************
3481* Externally useable functions to set up a queue item ready for sending
3482***********************************************************************/
3483
3484#ifdef	NETGRAPH_DEBUG
3485#define	ITEM_DEBUG_CHECKS						\
3486	do {								\
3487		if (NGI_NODE(item) ) {					\
3488			printf("item already has node");		\
3489			kdb_enter(KDB_WHY_NETGRAPH, "has node");	\
3490			NGI_CLR_NODE(item);				\
3491		}							\
3492		if (NGI_HOOK(item) ) {					\
3493			printf("item already has hook");		\
3494			kdb_enter(KDB_WHY_NETGRAPH, "has hook");	\
3495			NGI_CLR_HOOK(item);				\
3496		}							\
3497	} while (0)
3498#else
3499#define ITEM_DEBUG_CHECKS
3500#endif
3501
3502/*
3503 * Put mbuf into the item.
3504 * Hook and node references will be removed when the item is dequeued.
3505 * (or equivalent)
3506 * (XXX) Unsafe because no reference held by peer on remote node.
3507 * remote node might go away in this timescale.
3508 * We know the hooks can't go away because that would require getting
3509 * a writer item on both nodes and we must have at least a  reader
3510 * here to be able to do this.
3511 * Note that the hook loaded is the REMOTE hook.
3512 *
3513 * This is possibly in the critical path for new data.
3514 */
3515item_p
3516ng_package_data(struct mbuf *m, int flags)
3517{
3518	item_p item;
3519
3520	if ((item = ng_alloc_item(NGQF_DATA, flags)) == NULL) {
3521		NG_FREE_M(m);
3522		return (NULL);
3523	}
3524	ITEM_DEBUG_CHECKS;
3525	item->el_flags |= NGQF_READER;
3526	NGI_M(item) = m;
3527	return (item);
3528}
3529
3530/*
3531 * Allocate a queue item and put items into it..
3532 * Evaluate the address as this will be needed to queue it and
3533 * to work out what some of the fields should be.
3534 * Hook and node references will be removed when the item is dequeued.
3535 * (or equivalent)
3536 */
3537item_p
3538ng_package_msg(struct ng_mesg *msg, int flags)
3539{
3540	item_p item;
3541
3542	if ((item = ng_alloc_item(NGQF_MESG, flags)) == NULL) {
3543		NG_FREE_MSG(msg);
3544		return (NULL);
3545	}
3546	ITEM_DEBUG_CHECKS;
3547	/* Messages items count as writers unless explicitly exempted. */
3548	if (msg->header.cmd & NGM_READONLY)
3549		item->el_flags |= NGQF_READER;
3550	else
3551		item->el_flags |= NGQF_WRITER;
3552	/*
3553	 * Set the current lasthook into the queue item
3554	 */
3555	NGI_MSG(item) = msg;
3556	NGI_RETADDR(item) = 0;
3557	return (item);
3558}
3559
3560#define SET_RETADDR(item, here, retaddr)				\
3561	do {	/* Data or fn items don't have retaddrs */		\
3562		if ((item->el_flags & NGQF_TYPE) == NGQF_MESG) {	\
3563			if (retaddr) {					\
3564				NGI_RETADDR(item) = retaddr;		\
3565			} else {					\
3566				/*					\
3567				 * The old return address should be ok.	\
3568				 * If there isn't one, use the address	\
3569				 * here.				\
3570				 */					\
3571				if (NGI_RETADDR(item) == 0) {		\
3572					NGI_RETADDR(item)		\
3573						= ng_node2ID(here);	\
3574				}					\
3575			}						\
3576		}							\
3577	} while (0)
3578
3579int
3580ng_address_hook(node_p here, item_p item, hook_p hook, ng_ID_t retaddr)
3581{
3582	hook_p peer;
3583	node_p peernode;
3584	ITEM_DEBUG_CHECKS;
3585	/*
3586	 * Quick sanity check..
3587	 * Since a hook holds a reference on its node, once we know
3588	 * that the peer is still connected (even if invalid,) we know
3589	 * that the peer node is present, though maybe invalid.
3590	 */
3591	TOPOLOGY_RLOCK();
3592	if ((hook == NULL) || NG_HOOK_NOT_VALID(hook) ||
3593	    NG_HOOK_NOT_VALID(peer = NG_HOOK_PEER(hook)) ||
3594	    NG_NODE_NOT_VALID(peernode = NG_PEER_NODE(hook))) {
3595		NG_FREE_ITEM(item);
3596		TRAP_ERROR();
3597		TOPOLOGY_RUNLOCK();
3598		return (ENETDOWN);
3599	}
3600
3601	/*
3602	 * Transfer our interest to the other (peer) end.
3603	 */
3604	NG_HOOK_REF(peer);
3605	NG_NODE_REF(peernode);
3606	NGI_SET_HOOK(item, peer);
3607	NGI_SET_NODE(item, peernode);
3608	SET_RETADDR(item, here, retaddr);
3609
3610	TOPOLOGY_RUNLOCK();
3611
3612	return (0);
3613}
3614
3615int
3616ng_address_path(node_p here, item_p item, const char *address, ng_ID_t retaddr)
3617{
3618	node_p	dest = NULL;
3619	hook_p	hook = NULL;
3620	int	error;
3621
3622	ITEM_DEBUG_CHECKS;
3623	/*
3624	 * Note that ng_path2noderef increments the reference count
3625	 * on the node for us if it finds one. So we don't have to.
3626	 */
3627	error = ng_path2noderef(here, address, &dest, &hook);
3628	if (error) {
3629		NG_FREE_ITEM(item);
3630		return (error);
3631	}
3632	NGI_SET_NODE(item, dest);
3633	if (hook)
3634		NGI_SET_HOOK(item, hook);
3635
3636	SET_RETADDR(item, here, retaddr);
3637	return (0);
3638}
3639
3640int
3641ng_address_ID(node_p here, item_p item, ng_ID_t ID, ng_ID_t retaddr)
3642{
3643	node_p dest;
3644
3645	ITEM_DEBUG_CHECKS;
3646	/*
3647	 * Find the target node.
3648	 */
3649	dest = ng_ID2noderef(ID); /* GETS REFERENCE! */
3650	if (dest == NULL) {
3651		NG_FREE_ITEM(item);
3652		TRAP_ERROR();
3653		return(EINVAL);
3654	}
3655	/* Fill out the contents */
3656	NGI_SET_NODE(item, dest);
3657	NGI_CLR_HOOK(item);
3658	SET_RETADDR(item, here, retaddr);
3659	return (0);
3660}
3661
3662/*
3663 * special case to send a message to self (e.g. destroy node)
3664 * Possibly indicate an arrival hook too.
3665 * Useful for removing that hook :-)
3666 */
3667item_p
3668ng_package_msg_self(node_p here, hook_p hook, struct ng_mesg *msg)
3669{
3670	item_p item;
3671
3672	/*
3673	 * Find the target node.
3674	 * If there is a HOOK argument, then use that in preference
3675	 * to the address.
3676	 */
3677	if ((item = ng_alloc_item(NGQF_MESG, NG_NOFLAGS)) == NULL) {
3678		NG_FREE_MSG(msg);
3679		return (NULL);
3680	}
3681
3682	/* Fill out the contents */
3683	item->el_flags |= NGQF_WRITER;
3684	NG_NODE_REF(here);
3685	NGI_SET_NODE(item, here);
3686	if (hook) {
3687		NG_HOOK_REF(hook);
3688		NGI_SET_HOOK(item, hook);
3689	}
3690	NGI_MSG(item) = msg;
3691	NGI_RETADDR(item) = ng_node2ID(here);
3692	return (item);
3693}
3694
3695/*
3696 * Send ng_item_fn function call to the specified node.
3697 */
3698
3699int
3700ng_send_fn(node_p node, hook_p hook, ng_item_fn *fn, void * arg1, int arg2)
3701{
3702
3703	return ng_send_fn1(node, hook, fn, arg1, arg2, NG_NOFLAGS);
3704}
3705
3706int
3707ng_send_fn1(node_p node, hook_p hook, ng_item_fn *fn, void * arg1, int arg2,
3708	int flags)
3709{
3710	item_p item;
3711
3712	if ((item = ng_alloc_item(NGQF_FN, flags)) == NULL) {
3713		return (ENOMEM);
3714	}
3715	item->el_flags |= NGQF_WRITER;
3716	NG_NODE_REF(node); /* and one for the item */
3717	NGI_SET_NODE(item, node);
3718	if (hook) {
3719		NG_HOOK_REF(hook);
3720		NGI_SET_HOOK(item, hook);
3721	}
3722	NGI_FN(item) = fn;
3723	NGI_ARG1(item) = arg1;
3724	NGI_ARG2(item) = arg2;
3725	return(ng_snd_item(item, flags));
3726}
3727
3728/*
3729 * Send ng_item_fn2 function call to the specified node.
3730 *
3731 * If an optional pitem parameter is supplied, its apply
3732 * callback will be copied to the new item. If also NG_REUSE_ITEM
3733 * flag is set, no new item will be allocated, but pitem will
3734 * be used.
3735 */
3736int
3737ng_send_fn2(node_p node, hook_p hook, item_p pitem, ng_item_fn2 *fn, void *arg1,
3738	int arg2, int flags)
3739{
3740	item_p item;
3741
3742	KASSERT((pitem != NULL || (flags & NG_REUSE_ITEM) == 0),
3743	    ("%s: NG_REUSE_ITEM but no pitem", __func__));
3744
3745	/*
3746	 * Allocate a new item if no supplied or
3747	 * if we can't use supplied one.
3748	 */
3749	if (pitem == NULL || (flags & NG_REUSE_ITEM) == 0) {
3750		if ((item = ng_alloc_item(NGQF_FN2, flags)) == NULL)
3751			return (ENOMEM);
3752		if (pitem != NULL)
3753			item->apply = pitem->apply;
3754	} else {
3755		if ((item = ng_realloc_item(pitem, NGQF_FN2, flags)) == NULL)
3756			return (ENOMEM);
3757	}
3758
3759	item->el_flags = (item->el_flags & ~NGQF_RW) | NGQF_WRITER;
3760	NG_NODE_REF(node); /* and one for the item */
3761	NGI_SET_NODE(item, node);
3762	if (hook) {
3763		NG_HOOK_REF(hook);
3764		NGI_SET_HOOK(item, hook);
3765	}
3766	NGI_FN2(item) = fn;
3767	NGI_ARG1(item) = arg1;
3768	NGI_ARG2(item) = arg2;
3769	return(ng_snd_item(item, flags));
3770}
3771
3772/*
3773 * Official timeout routines for Netgraph nodes.
3774 */
3775static void
3776ng_callout_trampoline(void *arg)
3777{
3778	struct epoch_tracker et;
3779	item_p item = arg;
3780
3781	NET_EPOCH_ENTER(et);
3782	CURVNET_SET(NGI_NODE(item)->nd_vnet);
3783	ng_snd_item(item, 0);
3784	CURVNET_RESTORE();
3785	NET_EPOCH_EXIT(et);
3786}
3787
3788int
3789ng_callout(struct callout *c, node_p node, hook_p hook, int ticks,
3790    ng_item_fn *fn, void * arg1, int arg2)
3791{
3792	item_p item, oitem;
3793
3794	if ((item = ng_alloc_item(NGQF_FN, NG_NOFLAGS)) == NULL)
3795		return (ENOMEM);
3796
3797	item->el_flags |= NGQF_WRITER;
3798	NG_NODE_REF(node);		/* and one for the item */
3799	NGI_SET_NODE(item, node);
3800	if (hook) {
3801		NG_HOOK_REF(hook);
3802		NGI_SET_HOOK(item, hook);
3803	}
3804	NGI_FN(item) = fn;
3805	NGI_ARG1(item) = arg1;
3806	NGI_ARG2(item) = arg2;
3807	oitem = c->c_arg;
3808	if (callout_reset(c, ticks, &ng_callout_trampoline, item) == 1 &&
3809	    oitem != NULL)
3810		NG_FREE_ITEM(oitem);
3811	return (0);
3812}
3813
3814/* A special modified version of callout_stop() */
3815int
3816ng_uncallout(struct callout *c, node_p node)
3817{
3818	item_p item;
3819	int rval;
3820
3821	KASSERT(c != NULL, ("ng_uncallout: NULL callout"));
3822	KASSERT(node != NULL, ("ng_uncallout: NULL node"));
3823
3824	rval = callout_stop(c);
3825	item = c->c_arg;
3826	/* Do an extra check */
3827	if ((rval > 0) && (c->c_func == &ng_callout_trampoline) &&
3828	    (item != NULL) && (NGI_NODE(item) == node)) {
3829		/*
3830		 * We successfully removed it from the queue before it ran
3831		 * So now we need to unreference everything that was
3832		 * given extra references. (NG_FREE_ITEM does this).
3833		 */
3834		NG_FREE_ITEM(item);
3835	}
3836	c->c_arg = NULL;
3837
3838	/*
3839	 * Callers only want to know if the callout was cancelled and
3840	 * not draining or stopped.
3841	 */
3842	return (rval > 0);
3843}
3844
3845/*
3846 * Set the address, if none given, give the node here.
3847 */
3848void
3849ng_replace_retaddr(node_p here, item_p item, ng_ID_t retaddr)
3850{
3851	if (retaddr) {
3852		NGI_RETADDR(item) = retaddr;
3853	} else {
3854		/*
3855		 * The old return address should be ok.
3856		 * If there isn't one, use the address here.
3857		 */
3858		NGI_RETADDR(item) = ng_node2ID(here);
3859	}
3860}
3861