sys/netgraph7/ng_base.c

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