The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/netgraph/ng_base.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

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

Cache object: 4d909f86d5c89c690f8bf979d2c338a3


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.