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