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