sys/netgraph/ng_base.c

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