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