sys/netgraph/ng_base.c

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