sys/netgraph7/ng_base.c

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