sys/netgraph/ng_base.c

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