sys/netgraph7/netgraph/ng_base.c

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