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