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