sys/netgraph/ng_bridge.c

   1 /*-
   2  * Copyright (c) 2000 Whistle Communications, Inc.
   3  * All rights reserved.
   4  *
   5  * Subject to the following obligations and disclaimer of warranty, use and
   6  * redistribution of this software, in source or object code forms, with or
   7  * without modifications are expressly permitted by Whistle Communications;
   8  * provided, however, that:
   9  * 1. Any and all reproductions of the source or object code must include the
  10  *    copyright notice above and the following disclaimer of warranties; and
  11  * 2. No rights are granted, in any manner or form, to use Whistle
  12  *    Communications, Inc. trademarks, including the mark "WHISTLE
  13  *    COMMUNICATIONS" on advertising, endorsements, or otherwise except as
  14  *    such appears in the above copyright notice or in the software.
  15  *
  16  * THIS SOFTWARE IS BEING PROVIDED BY WHISTLE COMMUNICATIONS "AS IS", AND
  17  * TO THE MAXIMUM EXTENT PERMITTED BY LAW, WHISTLE COMMUNICATIONS MAKES NO
  18  * REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED, REGARDING THIS SOFTWARE,
  19  * INCLUDING WITHOUT LIMITATION, ANY AND ALL IMPLIED WARRANTIES OF
  20  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, OR NON-INFRINGEMENT.
  21  * WHISTLE COMMUNICATIONS DOES NOT WARRANT, GUARANTEE, OR MAKE ANY
  22  * REPRESENTATIONS REGARDING THE USE OF, OR THE RESULTS OF THE USE OF THIS
  23  * SOFTWARE IN TERMS OF ITS CORRECTNESS, ACCURACY, RELIABILITY OR OTHERWISE.
  24  * IN NO EVENT SHALL WHISTLE COMMUNICATIONS BE LIABLE FOR ANY DAMAGES
  25  * RESULTING FROM OR ARISING OUT OF ANY USE OF THIS SOFTWARE, INCLUDING
  26  * WITHOUT LIMITATION, ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
  27  * PUNITIVE, OR CONSEQUENTIAL DAMAGES, PROCUREMENT OF SUBSTITUTE GOODS OR
  28  * SERVICES, LOSS OF USE, DATA OR PROFITS, HOWEVER CAUSED AND UNDER ANY
  29  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  30  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  31  * THIS SOFTWARE, EVEN IF WHISTLE COMMUNICATIONS IS ADVISED OF THE POSSIBILITY
  32  * OF SUCH DAMAGE.
  33  *
  34  * Author: Archie Cobbs <archie@freebsd.org>
  35  *
  36  * $FreeBSD$
  37  */
  38
  39 /*
  40  * ng_bridge(4) netgraph node type
  41  *
  42  * The node performs standard intelligent Ethernet bridging over
  43  * each of its connected hooks, or links.  A simple loop detection
  44  * algorithm is included which disables a link for priv->conf.loopTimeout
  45  * seconds when a host is seen to have jumped from one link to
  46  * another within priv->conf.minStableAge seconds.
  47  *
  48  * We keep a hashtable that maps Ethernet addresses to host info,
  49  * which is contained in struct ng_bridge_host's. These structures
  50  * tell us on which link the host may be found. A host's entry will
  51  * expire after priv->conf.maxStaleness seconds.
  52  *
  53  * This node is optimzed for stable networks, where machines jump
  54  * from one port to the other only rarely.
  55  */
  56
  57 #include <sys/param.h>
  58 #include <sys/systm.h>
  59 #include <sys/kernel.h>
  60 #include <sys/lock.h>
  61 #include <sys/malloc.h>
  62 #include <sys/mbuf.h>
  63 #include <sys/errno.h>
  64 #include <sys/rwlock.h>
  65 #include <sys/syslog.h>
  66 #include <sys/socket.h>
  67 #include <sys/ctype.h>
  68
  69 #include <net/if.h>
  70 #include <net/if_var.h>
  71 #include <net/ethernet.h>
  72 #include <net/vnet.h>
  73
  74 #include <netinet/in.h>
  75 #if 0   /* not used yet */
  76 #include <netinet/ip_fw.h>
  77 #endif
  78 #include <netgraph/ng_message.h>
  79 #include <netgraph/netgraph.h>
  80 #include <netgraph/ng_parse.h>
  81 #include <netgraph/ng_bridge.h>
  82
  83 #ifdef NG_SEPARATE_MALLOC
  84 static MALLOC_DEFINE(M_NETGRAPH_BRIDGE, "netgraph_bridge",
  85     "netgraph bridge node");
  86 #else
  87 #define M_NETGRAPH_BRIDGE M_NETGRAPH
  88 #endif
  89
  90 /* Per-link private data */
  91 struct ng_bridge_link {
  92         hook_p                          hook;           /* netgraph hook */
  93         u_int16_t                       loopCount;      /* loop ignore timer */
  94         unsigned int                    learnMac : 1,   /* autolearn macs */
  95                                         sendUnknown : 1;/* send unknown macs out */
  96         struct ng_bridge_link_stats     stats;          /* link stats */
  97 };
  98
  99 /* Per-node private data */
 100 struct ng_bridge_private {
 101         struct ng_bridge_bucket *tab;           /* hash table bucket array */
 102         struct ng_bridge_config conf;           /* node configuration */
 103         node_p                  node;           /* netgraph node */
 104         u_int                   numHosts;       /* num entries in table */
 105         u_int                   numBuckets;     /* num buckets in table */
 106         u_int                   hashMask;       /* numBuckets - 1 */
 107         int                     numLinks;       /* num connected links */
 108         unsigned int            persistent : 1, /* can exist w/o hooks */
 109                                 sendUnknown : 1;/* links receive unknowns by default */
 110         struct callout          timer;          /* one second periodic timer */
 111 };
 112 typedef struct ng_bridge_private *priv_p;
 113
 114 /* Information about a host, stored in a hash table entry */
 115 struct ng_bridge_hent {
 116         struct ng_bridge_host           host;   /* actual host info */
 117         SLIST_ENTRY(ng_bridge_hent)     next;   /* next entry in bucket */
 118 };
 119
 120 /* Hash table bucket declaration */
 121 SLIST_HEAD(ng_bridge_bucket, ng_bridge_hent);
 122
 123 /* Netgraph node methods */
 124 static ng_constructor_t ng_bridge_constructor;
 125 static ng_rcvmsg_t      ng_bridge_rcvmsg;
 126 static ng_shutdown_t    ng_bridge_shutdown;
 127 static ng_newhook_t     ng_bridge_newhook;
 128 static ng_rcvdata_t     ng_bridge_rcvdata;
 129 static ng_disconnect_t  ng_bridge_disconnect;
 130
 131 /* Other internal functions */
 132 static struct   ng_bridge_host *ng_bridge_get(priv_p priv, const u_char *addr);
 133 static int      ng_bridge_put(priv_p priv, const u_char *addr, link_p link);
 134 static void     ng_bridge_rehash(priv_p priv);
 135 static void     ng_bridge_remove_hosts(priv_p priv, link_p link);
 136 static void     ng_bridge_timeout(node_p node, hook_p hook, void *arg1, int arg2);
 137 static const    char *ng_bridge_nodename(node_p node);
 138
 139 /* Ethernet broadcast */
 140 static const u_char ng_bridge_bcast_addr[ETHER_ADDR_LEN] =
 141     { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff };
 142
 143 /* Compare Ethernet addresses using 32 and 16 bit words instead of bytewise */
 144 #define ETHER_EQUAL(a,b)        (((const u_int32_t *)(a))[0] \
 145                                         == ((const u_int32_t *)(b))[0] \
 146                                     && ((const u_int16_t *)(a))[2] \
 147                                         == ((const u_int16_t *)(b))[2])
 148
 149 /* Minimum and maximum number of hash buckets. Must be a power of two. */
 150 #define MIN_BUCKETS             (1 << 5)        /* 32 */
 151 #define MAX_BUCKETS             (1 << 14)       /* 16384 */
 152
 153 /* Configuration default values */
 154 #define DEFAULT_LOOP_TIMEOUT    60
 155 #define DEFAULT_MAX_STALENESS   (15 * 60)       /* same as ARP timeout */
 156 #define DEFAULT_MIN_STABLE_AGE  1
 157
 158 /******************************************************************
 159                     NETGRAPH PARSE TYPES
 160 ******************************************************************/
 161
 162 /*
 163  * How to determine the length of the table returned by NGM_BRIDGE_GET_TABLE
 164  */
 165 static int
 166 ng_bridge_getTableLength(const struct ng_parse_type *type,
 167         const u_char *start, const u_char *buf)
 168 {
 169         const struct ng_bridge_host_ary *const hary
 170             = (const struct ng_bridge_host_ary *)(buf - sizeof(u_int32_t));
 171
 172         return hary->numHosts;
 173 }
 174
 175 /* Parse type for struct ng_bridge_host_ary */
 176 static const struct ng_parse_struct_field ng_bridge_host_type_fields[]
 177         = NG_BRIDGE_HOST_TYPE_INFO(&ng_parse_enaddr_type);
 178 static const struct ng_parse_type ng_bridge_host_type = {
 179         &ng_parse_struct_type,
 180         &ng_bridge_host_type_fields
 181 };
 182 static const struct ng_parse_array_info ng_bridge_hary_type_info = {
 183         &ng_bridge_host_type,
 184         ng_bridge_getTableLength
 185 };
 186 static const struct ng_parse_type ng_bridge_hary_type = {
 187         &ng_parse_array_type,
 188         &ng_bridge_hary_type_info
 189 };
 190 static const struct ng_parse_struct_field ng_bridge_host_ary_type_fields[]
 191         = NG_BRIDGE_HOST_ARY_TYPE_INFO(&ng_bridge_hary_type);
 192 static const struct ng_parse_type ng_bridge_host_ary_type = {
 193         &ng_parse_struct_type,
 194         &ng_bridge_host_ary_type_fields
 195 };
 196
 197 /* Parse type for struct ng_bridge_config */
 198 static const struct ng_parse_struct_field ng_bridge_config_type_fields[]
 199         = NG_BRIDGE_CONFIG_TYPE_INFO;
 200 static const struct ng_parse_type ng_bridge_config_type = {
 201         &ng_parse_struct_type,
 202         &ng_bridge_config_type_fields
 203 };
 204
 205 /* Parse type for struct ng_bridge_link_stat */
 206 static const struct ng_parse_struct_field ng_bridge_stats_type_fields[]
 207         = NG_BRIDGE_STATS_TYPE_INFO;
 208 static const struct ng_parse_type ng_bridge_stats_type = {
 209         &ng_parse_struct_type,
 210         &ng_bridge_stats_type_fields
 211 };
 212
 213 /* List of commands and how to convert arguments to/from ASCII */
 214 static const struct ng_cmdlist ng_bridge_cmdlist[] = {
 215         {
 216           NGM_BRIDGE_COOKIE,
 217           NGM_BRIDGE_SET_CONFIG,
 218           "setconfig",
 219           &ng_bridge_config_type,
 220           NULL
 221         },
 222         {
 223           NGM_BRIDGE_COOKIE,
 224           NGM_BRIDGE_GET_CONFIG,
 225           "getconfig",
 226           NULL,
 227           &ng_bridge_config_type
 228         },
 229         {
 230           NGM_BRIDGE_COOKIE,
 231           NGM_BRIDGE_RESET,
 232           "reset",
 233           NULL,
 234           NULL
 235         },
 236         {
 237           NGM_BRIDGE_COOKIE,
 238           NGM_BRIDGE_GET_STATS,
 239           "getstats",
 240           &ng_parse_uint32_type,
 241           &ng_bridge_stats_type
 242         },
 243         {
 244           NGM_BRIDGE_COOKIE,
 245           NGM_BRIDGE_CLR_STATS,
 246           "clrstats",
 247           &ng_parse_uint32_type,
 248           NULL
 249         },
 250         {
 251           NGM_BRIDGE_COOKIE,
 252           NGM_BRIDGE_GETCLR_STATS,
 253           "getclrstats",
 254           &ng_parse_uint32_type,
 255           &ng_bridge_stats_type
 256         },
 257         {
 258           NGM_BRIDGE_COOKIE,
 259           NGM_BRIDGE_GET_TABLE,
 260           "gettable",
 261           NULL,
 262           &ng_bridge_host_ary_type
 263         },
 264         {
 265           NGM_BRIDGE_COOKIE,
 266           NGM_BRIDGE_SET_PERSISTENT,
 267           "setpersistent",
 268           NULL,
 269           NULL
 270         },
 271         { 0 }
 272 };
 273
 274 /* Node type descriptor */
 275 static struct ng_type ng_bridge_typestruct = {
 276         .version =      NG_ABI_VERSION,
 277         .name =         NG_BRIDGE_NODE_TYPE,
 278         .constructor =  ng_bridge_constructor,
 279         .rcvmsg =       ng_bridge_rcvmsg,
 280         .shutdown =     ng_bridge_shutdown,
 281         .newhook =      ng_bridge_newhook,
 282         .rcvdata =      ng_bridge_rcvdata,
 283         .disconnect =   ng_bridge_disconnect,
 284         .cmdlist =      ng_bridge_cmdlist,
 285 };
 286 NETGRAPH_INIT(bridge, &ng_bridge_typestruct);
 287
 288 /******************************************************************
 289                     NETGRAPH NODE METHODS
 290 ******************************************************************/
 291
 292 /*
 293  * Node constructor
 294  */
 295 static int
 296 ng_bridge_constructor(node_p node)
 297 {
 298         priv_p priv;
 299
 300         /* Allocate and initialize private info */
 301         priv = malloc(sizeof(*priv), M_NETGRAPH_BRIDGE, M_WAITOK | M_ZERO);
 302         ng_callout_init(&priv->timer);
 303
 304         /* Allocate and initialize hash table, etc. */
 305         priv->tab = malloc(MIN_BUCKETS * sizeof(*priv->tab),
 306             M_NETGRAPH_BRIDGE, M_WAITOK | M_ZERO);
 307         priv->numBuckets = MIN_BUCKETS;
 308         priv->hashMask = MIN_BUCKETS - 1;
 309         priv->conf.debugLevel = 1;
 310         priv->conf.loopTimeout = DEFAULT_LOOP_TIMEOUT;
 311         priv->conf.maxStaleness = DEFAULT_MAX_STALENESS;
 312         priv->conf.minStableAge = DEFAULT_MIN_STABLE_AGE;
 313         priv->sendUnknown = 1;         /* classic bridge */
 314
 315         /*
 316          * This node has all kinds of stuff that could be screwed by SMP.
 317          * Until it gets it's own internal protection, we go through in
 318          * single file. This could hurt a machine bridging between two
 319          * GB ethernets so it should be fixed.
 320          * When it's fixed the process SHOULD NOT SLEEP, spinlocks please!
 321          * (and atomic ops )
 322          */
 323         NG_NODE_FORCE_WRITER(node);
 324         NG_NODE_SET_PRIVATE(node, priv);
 325         priv->node = node;
 326
 327         /* Start timer; timer is always running while node is alive */
 328         ng_callout(&priv->timer, node, NULL, hz, ng_bridge_timeout, NULL, 0);
 329
 330         /* Done */
 331         return (0);
 332 }
 333
 334 /*
 335  * Method for attaching a new hook
 336  */
 337 static  int
 338 ng_bridge_newhook(node_p node, hook_p hook, const char *name)
 339 {
 340         const priv_p priv = NG_NODE_PRIVATE(node);
 341         char linkName[NG_HOOKSIZ];
 342         u_int32_t linkNum;
 343         link_p link;
 344         const char *prefix = NG_BRIDGE_HOOK_LINK_PREFIX;
 345         bool isUplink;
 346
 347         /* Check for a link hook */
 348         if (strlen(name) <= strlen(prefix))
 349                 return (EINVAL);       /* Unknown hook name */
 350
 351         isUplink = (name[0] == 'u');
 352         if (isUplink)
 353                 prefix = NG_BRIDGE_HOOK_UPLINK_PREFIX;
 354
 355         /* primitive parsing */
 356         linkNum = strtoul(name + strlen(prefix), NULL, 10);
 357         /* validation by comparing against the reconstucted name  */
 358         snprintf(linkName, sizeof(linkName), "%s%u", prefix, linkNum);
 359         if (strcmp(linkName, name) != 0)
 360                 return (EINVAL);
 361
 362         if (linkNum == 0 && isUplink)
 363                 return (EINVAL);
 364
 365         if(NG_PEER_NODE(hook) == node)
 366                 return (ELOOP);
 367
 368         link = malloc(sizeof(*link), M_NETGRAPH_BRIDGE, M_ZERO);
 369         if (link == NULL)
 370                 return (ENOMEM);
 371
 372         link->hook = hook;
 373         if (isUplink) {
 374                 link->learnMac = 0;
 375                 link->sendUnknown = 1;
 376                 if (priv->numLinks == 0)        /* if the first link is an uplink */
 377                     priv->sendUnknown = 0;      /* switch to restrictive mode */
 378         } else {
 379                 link->learnMac = 1;
 380                 link->sendUnknown = priv->sendUnknown;
 381         }
 382
 383         NG_HOOK_SET_PRIVATE(hook, link);
 384         priv->numLinks++;
 385         return (0);
 386 }
 387
 388 /*
 389  * Receive a control message
 390  */
 391 static int
 392 ng_bridge_reset_link(hook_p hook, void *arg __unused)
 393 {
 394         link_p priv = NG_HOOK_PRIVATE(hook);
 395
 396         priv->loopCount = 0;
 397         bzero(&priv->stats, sizeof(priv->stats));
 398
 399         return (1);
 400 }
 401
 402
 403 static int
 404 ng_bridge_rcvmsg(node_p node, item_p item, hook_p lasthook)
 405 {
 406         const priv_p priv = NG_NODE_PRIVATE(node);
 407         struct ng_mesg *resp = NULL;
 408         int error = 0;
 409         struct ng_mesg *msg;
 410
 411         NGI_GET_MSG(item, msg);
 412         switch (msg->header.typecookie) {
 413 #ifdef NGM_BRIDGE_TABLE_ABI
 414         case NGM_BRIDGE_COOKIE_TBL:
 415                 switch (msg->header.cmd) {
 416                 case NGM_BRIDGE_GET_CONFIG:
 417                     {
 418                         struct ng_bridge_config_tbl *conf;
 419
 420                         NG_MKRESPONSE(resp, msg, sizeof(*conf),
 421                             M_NOWAIT|M_ZERO);
 422                         if (resp == NULL) {
 423                                 error = ENOMEM;
 424                                 break;
 425                         }
 426                         conf = (struct ng_bridge_config_tbl *)resp->data;
 427                         conf->cfg = priv->conf;
 428                         break;
 429                     }
 430                 case NGM_BRIDGE_SET_CONFIG:
 431                     {
 432                         struct ng_bridge_config_tbl *conf;
 433
 434                         if (msg->header.arglen != sizeof(*conf)) {
 435                                 error = EINVAL;
 436                                 break;
 437                         }
 438                         conf = (struct ng_bridge_config_tbl *)msg->data;
 439                         priv->conf = conf->cfg;
 440                         break;
 441                     }
 442                 case NGM_BRIDGE_GET_TABLE:
 443                     {
 444                         struct ng_bridge_host_tbl_ary *ary;
 445                         struct ng_bridge_hent *hent;
 446                         int i, bucket;
 447
 448                         NG_MKRESPONSE(resp, msg, sizeof(*ary) +
 449                             (priv->numHosts * sizeof(*ary->hosts)), M_NOWAIT);
 450                         if (resp == NULL) {
 451                                 error = ENOMEM;
 452                                 break;
 453                         }
 454                         ary = (struct ng_bridge_host_tbl_ary *)resp->data;
 455                         ary->numHosts = priv->numHosts;
 456                         i = 0;
 457                         for (bucket = 0; bucket < priv->numBuckets; bucket++) {
 458                                 SLIST_FOREACH(hent, &priv->tab[bucket], next) {
 459                                         const char *name = NG_HOOK_NAME(hent->host.link->hook);
 460                                         const char *prefix = name[0] == 'u' ?
 461                                             NG_BRIDGE_HOOK_UPLINK_PREFIX :
 462                                             NG_BRIDGE_HOOK_LINK_PREFIX;
 463
 464                                         memcpy(ary->hosts[i].addr,
 465                                             hent->host.addr,
 466                                             sizeof(ary->hosts[i].addr));
 467                                         ary->hosts[i].age = hent->host.age;
 468                                         ary->hosts[i].staleness =
 469                                              hent->host.staleness;
 470                                         ary->hosts[i].linkNum = strtol(
 471                                             name + strlen(prefix), NULL, 10);
 472                                         i++;
 473                                 }
 474                         }
 475                         break;
 476                     }
 477                 }
 478                 /* If already handled break, otherwise use new ABI. */
 479                 if (resp != NULL || error != 0)
 480                     break;
 481 #endif /* NGM_BRIDGE_TABLE_ABI */
 482         case NGM_BRIDGE_COOKIE:
 483                 switch (msg->header.cmd) {
 484                 case NGM_BRIDGE_GET_CONFIG:
 485                     {
 486                         struct ng_bridge_config *conf;
 487
 488                         NG_MKRESPONSE(resp, msg,
 489                             sizeof(struct ng_bridge_config), M_NOWAIT);
 490                         if (resp == NULL) {
 491                                 error = ENOMEM;
 492                                 break;
 493                         }
 494                         conf = (struct ng_bridge_config *)resp->data;
 495                         *conf = priv->conf;     /* no sanity checking needed */
 496                         break;
 497                     }
 498                 case NGM_BRIDGE_SET_CONFIG:
 499                     {
 500                         struct ng_bridge_config *conf;
 501
 502                         if (msg->header.arglen
 503                             != sizeof(struct ng_bridge_config)) {
 504                                 error = EINVAL;
 505                                 break;
 506                         }
 507                         conf = (struct ng_bridge_config *)msg->data;
 508                         priv->conf = *conf;
 509                         break;
 510                     }
 511                 case NGM_BRIDGE_RESET:
 512                     {
 513                         hook_p rethook;
 514
 515                         /* Flush all entries in the hash table */
 516                         ng_bridge_remove_hosts(priv, NULL);
 517
 518                         /* Reset all loop detection counters and stats */
 519                         NG_NODE_FOREACH_HOOK(node, ng_bridge_reset_link, NULL,
 520                             rethook);
 521                         break;
 522                     }
 523                 case NGM_BRIDGE_GET_STATS:
 524                 case NGM_BRIDGE_CLR_STATS:
 525                 case NGM_BRIDGE_GETCLR_STATS:
 526                     {
 527                         hook_p hook;
 528                         link_p link;
 529                         char linkName[NG_HOOKSIZ];
 530                         int linkNum;
 531
 532                         /* Get link number */
 533                         if (msg->header.arglen != sizeof(u_int32_t)) {
 534                                 error = EINVAL;
 535                                 break;
 536                         }
 537                         linkNum = *((int32_t *)msg->data);
 538                         if (linkNum < 0)
 539                                 snprintf(linkName, sizeof(linkName),
 540                                     "%s%u", NG_BRIDGE_HOOK_UPLINK_PREFIX, -linkNum);
 541                         else
 542                                 snprintf(linkName, sizeof(linkName),
 543                                     "%s%u", NG_BRIDGE_HOOK_LINK_PREFIX, linkNum);
 544
 545                         if ((hook = ng_findhook(node, linkName)) == NULL) {
 546                                 error = ENOTCONN;
 547                                 break;
 548                         }
 549                         link = NG_HOOK_PRIVATE(hook);
 550
 551                         /* Get/clear stats */
 552                         if (msg->header.cmd != NGM_BRIDGE_CLR_STATS) {
 553                                 NG_MKRESPONSE(resp, msg,
 554                                     sizeof(link->stats), M_NOWAIT);
 555                                 if (resp == NULL) {
 556                                         error = ENOMEM;
 557                                         break;
 558                                 }
 559                                 bcopy(&link->stats,
 560                                     resp->data, sizeof(link->stats));
 561                         }
 562                         if (msg->header.cmd != NGM_BRIDGE_GET_STATS)
 563                                 bzero(&link->stats, sizeof(link->stats));
 564                         break;
 565                     }
 566                 case NGM_BRIDGE_GET_TABLE:
 567                     {
 568                         struct ng_bridge_host_ary *ary;
 569                         struct ng_bridge_hent *hent;
 570                         int i = 0, bucket;
 571
 572                         NG_MKRESPONSE(resp, msg, sizeof(*ary)
 573                             + (priv->numHosts * sizeof(*ary->hosts)), M_NOWAIT);
 574                         if (resp == NULL) {
 575                                 error = ENOMEM;
 576                                 break;
 577                         }
 578                         ary = (struct ng_bridge_host_ary *)resp->data;
 579                         ary->numHosts = priv->numHosts;
 580                         for (bucket = 0; bucket < priv->numBuckets; bucket++) {
 581                                 SLIST_FOREACH(hent, &priv->tab[bucket], next) {
 582                                         memcpy(ary->hosts[i].addr,
 583                                                hent->host.addr,
 584                                                sizeof(ary->hosts[i].addr));
 585                                         ary->hosts[i].age       = hent->host.age;
 586                                         ary->hosts[i].staleness = hent->host.staleness;
 587                                         strncpy(ary->hosts[i].hook,
 588                                                 NG_HOOK_NAME(hent->host.link->hook),
 589                                                 sizeof(ary->hosts[i].hook));
 590                                         i++;
 591                                 }
 592                         }
 593                         break;
 594                     }
 595                 case NGM_BRIDGE_SET_PERSISTENT:
 596                     {
 597                         priv->persistent = 1;
 598                         break;
 599                     }
 600                 default:
 601                         error = EINVAL;
 602                         break;
 603                 }
 604                 break;
 605         default:
 606                 error = EINVAL;
 607                 break;
 608         }
 609
 610         /* Done */
 611         NG_RESPOND_MSG(error, node, item, resp);
 612         NG_FREE_MSG(msg);
 613         return (error);
 614 }
 615
 616 /*
 617  * Receive data on a hook
 618  */
 619 struct ng_bridge_send_ctx {
 620         link_p foundFirst, incoming;
 621         struct mbuf * m;
 622         int manycast, error;
 623 };
 624
 625 static int
 626 ng_bridge_send_ctx(hook_p dst, void *arg)
 627 {
 628         struct ng_bridge_send_ctx *ctx = arg;
 629         link_p destLink = NG_HOOK_PRIVATE(dst);
 630         struct mbuf *m2 = NULL;
 631         int error = 0;
 632
 633         /* Skip incoming link */
 634         if (destLink == ctx->incoming) {
 635                 return (1);
 636         }
 637
 638         /* Skip sending unknowns to undesired links  */
 639         if (!ctx->manycast && !destLink->sendUnknown)
 640                 return (1);
 641
 642         if (ctx->foundFirst == NULL) {
 643                 /*
 644                  * This is the first usable link we have found.
 645                  * Reserve it for the originals.
 646                  * If we never find another we save a copy.
 647                  */
 648                 ctx->foundFirst = destLink;
 649                 return (1);
 650         }
 651
 652         /*
 653          * It's usable link but not the reserved (first) one.
 654          * Copy mbuf info for sending.
 655          */
 656         m2 = m_dup(ctx->m, M_NOWAIT);   /* XXX m_copypacket() */
 657         if (m2 == NULL) {
 658                 ctx->incoming->stats.memoryFailures++;
 659                 ctx->error = ENOBUFS;
 660                 return (0);            /* abort loop */
 661         }
 662
 663
 664         /* Update stats */
 665         destLink->stats.xmitPackets++;
 666         destLink->stats.xmitOctets += m2->m_pkthdr.len;
 667         switch (ctx->manycast) {
 668          default:                                       /* unknown unicast */
 669                 break;
 670          case 1:                                        /* multicast */
 671                 destLink->stats.xmitMulticasts++;
 672                 break;
 673          case 2:                                        /* broadcast */
 674                 destLink->stats.xmitBroadcasts++;
 675                 break;
 676         }
 677
 678         /* Send packet */
 679         NG_SEND_DATA_ONLY(error, destLink->hook, m2);
 680         if(error)
 681           ctx->error = error;
 682         return (1);
 683 }
 684
 685 static int
 686 ng_bridge_rcvdata(hook_p hook, item_p item)
 687 {
 688         const node_p node = NG_HOOK_NODE(hook);
 689         const priv_p priv = NG_NODE_PRIVATE(node);
 690         struct ng_bridge_host *host;
 691         struct ether_header *eh;
 692         struct ng_bridge_send_ctx ctx = { 0 };
 693         hook_p ret;
 694
 695         NGI_GET_M(item, ctx.m);
 696
 697         ctx.incoming = NG_HOOK_PRIVATE(hook);
 698         /* Sanity check packet and pull up header */
 699         if (ctx.m->m_pkthdr.len < ETHER_HDR_LEN) {
 700                 ctx.incoming->stats.recvRunts++;
 701                 NG_FREE_ITEM(item);
 702                 NG_FREE_M(ctx.m);
 703                 return (EINVAL);
 704         }
 705         if (ctx.m->m_len < ETHER_HDR_LEN && !(ctx.m = m_pullup(ctx.m, ETHER_HDR_LEN))) {
 706                 ctx.incoming->stats.memoryFailures++;
 707                 NG_FREE_ITEM(item);
 708                 return (ENOBUFS);
 709         }
 710         eh = mtod(ctx.m, struct ether_header *);
 711         if ((eh->ether_shost[0] & 1) != 0) {
 712                 ctx.incoming->stats.recvInvalid++;
 713                 NG_FREE_ITEM(item);
 714                 NG_FREE_M(ctx.m);
 715                 return (EINVAL);
 716         }
 717
 718         /* Is link disabled due to a loopback condition? */
 719         if (ctx.incoming->loopCount != 0) {
 720                 ctx.incoming->stats.loopDrops++;
 721                 NG_FREE_ITEM(item);
 722                 NG_FREE_M(ctx.m);
 723                 return (ELOOP);         /* XXX is this an appropriate error? */
 724         }
 725
 726         /* Update stats */
 727         ctx.incoming->stats.recvPackets++;
 728         ctx.incoming->stats.recvOctets += ctx.m->m_pkthdr.len;
 729         if ((ctx.manycast = (eh->ether_dhost[0] & 1)) != 0) {
 730                 if (ETHER_EQUAL(eh->ether_dhost, ng_bridge_bcast_addr)) {
 731                         ctx.incoming->stats.recvBroadcasts++;
 732                         ctx.manycast = 2;
 733                 } else
 734                         ctx.incoming->stats.recvMulticasts++;
 735         }
 736
 737         /* Look up packet's source Ethernet address in hashtable */
 738         if ((host = ng_bridge_get(priv, eh->ether_shost)) != NULL) {
 739
 740                 /* Update time since last heard from this host */
 741                 host->staleness = 0;
 742
 743                 /* Did host jump to a different link? */
 744                 if (host->link != ctx.incoming) {
 745
 746                         /*
 747                          * If the host's old link was recently established
 748                          * on the old link and it's already jumped to a new
 749                          * link, declare a loopback condition.
 750                          */
 751                         if (host->age < priv->conf.minStableAge) {
 752
 753                                 /* Log the problem */
 754                                 if (priv->conf.debugLevel >= 2) {
 755                                         struct ifnet *ifp = ctx.m->m_pkthdr.rcvif;
 756                                         char suffix[32];
 757
 758                                         if (ifp != NULL)
 759                                                 snprintf(suffix, sizeof(suffix),
 760                                                     " (%s)", ifp->if_xname);
 761                                         else
 762                                                 *suffix = '\0';
 763                                         log(LOG_WARNING, "ng_bridge: %s:"
 764                                             " loopback detected on %s%s\n",
 765                                             ng_bridge_nodename(node),
 766                                             NG_HOOK_NAME(hook), suffix);
 767                                 }
 768
 769                                 /* Mark link as linka non grata */
 770                                 ctx.incoming->loopCount = priv->conf.loopTimeout;
 771                                 ctx.incoming->stats.loopDetects++;
 772
 773                                 /* Forget all hosts on this link */
 774                                 ng_bridge_remove_hosts(priv, ctx.incoming);
 775
 776                                 /* Drop packet */
 777                                 ctx.incoming->stats.loopDrops++;
 778                                 NG_FREE_ITEM(item);
 779                                 NG_FREE_M(ctx.m);
 780                                 return (ELOOP);         /* XXX appropriate? */
 781                         }
 782
 783                         /* Move host over to new link */
 784                         host->link = ctx.incoming;
 785                         host->age = 0;
 786                 }
 787         } else if (ctx.incoming->learnMac) {
 788                 if (!ng_bridge_put(priv, eh->ether_shost, ctx.incoming)) {
 789                         ctx.incoming->stats.memoryFailures++;
 790                         NG_FREE_ITEM(item);
 791                         NG_FREE_M(ctx.m);
 792                         return (ENOMEM);
 793                 }
 794         }
 795
 796         /* Run packet through ipfw processing, if enabled */
 797 #if 0
 798         if (priv->conf.ipfw[linkNum] && V_fw_enable && V_ip_fw_chk_ptr != NULL) {
 799                 /* XXX not implemented yet */
 800         }
 801 #endif
 802
 803         /*
 804          * If unicast and destination host known, deliver to host's link,
 805          * unless it is the same link as the packet came in on.
 806          */
 807         if (!ctx.manycast) {
 808
 809                 /* Determine packet destination link */
 810                 if ((host = ng_bridge_get(priv, eh->ether_dhost)) != NULL) {
 811                         link_p destLink = host->link;
 812
 813                         /* If destination same as incoming link, do nothing */
 814                         if (destLink == ctx.incoming) {
 815                                 NG_FREE_ITEM(item);
 816                                 NG_FREE_M(ctx.m);
 817                                 return (0);
 818                         }
 819
 820                         /* Deliver packet out the destination link */
 821                         destLink->stats.xmitPackets++;
 822                         destLink->stats.xmitOctets += ctx.m->m_pkthdr.len;
 823                         NG_FWD_NEW_DATA(ctx.error, item, destLink->hook, ctx.m);
 824                         return (ctx.error);
 825                 }
 826
 827                 /* Destination host is not known */
 828                 ctx.incoming->stats.recvUnknown++;
 829         }
 830
 831         /* Distribute unknown, multicast, broadcast pkts to all other links */
 832         NG_NODE_FOREACH_HOOK(node, ng_bridge_send_ctx, &ctx, ret);
 833
 834         /* If we never saw a good link, leave. */
 835         if (ctx.foundFirst == NULL || ctx.error != 0) {
 836                 NG_FREE_ITEM(item);
 837                 NG_FREE_M(ctx.m);
 838                 return (ctx.error);
 839         }
 840
 841         /*
 842          * If we've sent all the others, send the original
 843          * on the first link we found.
 844          */
 845         NG_FWD_NEW_DATA(ctx.error, item, ctx.foundFirst->hook, ctx.m);
 846         return (ctx.error);
 847 }
 848
 849 /*
 850  * Shutdown node
 851  */
 852 static int
 853 ng_bridge_shutdown(node_p node)
 854 {
 855         const priv_p priv = NG_NODE_PRIVATE(node);
 856
 857         /*
 858          * Shut down everything including the timer.  Even if the
 859          * callout has already been dequeued and is about to be
 860          * run, ng_bridge_timeout() won't be fired as the node
 861          * is already marked NGF_INVALID, so we're safe to free
 862          * the node now.
 863          */
 864         KASSERT(priv->numLinks == 0 && priv->numHosts == 0,
 865             ("%s: numLinks=%d numHosts=%d",
 866             __func__, priv->numLinks, priv->numHosts));
 867         ng_uncallout(&priv->timer, node);
 868         NG_NODE_SET_PRIVATE(node, NULL);
 869         NG_NODE_UNREF(node);
 870         free(priv->tab, M_NETGRAPH_BRIDGE);
 871         free(priv, M_NETGRAPH_BRIDGE);
 872         return (0);
 873 }
 874
 875 /*
 876  * Hook disconnection.
 877  */
 878 static int
 879 ng_bridge_disconnect(hook_p hook)
 880 {
 881         const priv_p priv = NG_NODE_PRIVATE(NG_HOOK_NODE(hook));
 882         link_p link = NG_HOOK_PRIVATE(hook);
 883
 884         /* Remove all hosts associated with this link */
 885         ng_bridge_remove_hosts(priv, link);
 886
 887         /* Free associated link information */
 888         free(link, M_NETGRAPH_BRIDGE);
 889         priv->numLinks--;
 890
 891         /* If no more hooks, go away */
 892         if ((NG_NODE_NUMHOOKS(NG_HOOK_NODE(hook)) == 0)
 893             && (NG_NODE_IS_VALID(NG_HOOK_NODE(hook)))
 894             && !priv->persistent) {
 895                 ng_rmnode_self(NG_HOOK_NODE(hook));
 896         }
 897         return (0);
 898 }
 899
 900 /******************************************************************
 901                     HASH TABLE FUNCTIONS
 902 ******************************************************************/
 903
 904 /*
 905  * Hash algorithm
 906  */
 907 #define HASH(addr,mask)         ( (((const u_int16_t *)(addr))[0]       \
 908                                  ^ ((const u_int16_t *)(addr))[1]       \
 909                                  ^ ((const u_int16_t *)(addr))[2]) & (mask) )
 910
 911 /*
 912  * Find a host entry in the table.
 913  */
 914 static struct ng_bridge_host *
 915 ng_bridge_get(priv_p priv, const u_char *addr)
 916 {
 917         const int bucket = HASH(addr, priv->hashMask);
 918         struct ng_bridge_hent *hent;
 919
 920         SLIST_FOREACH(hent, &priv->tab[bucket], next) {
 921                 if (ETHER_EQUAL(hent->host.addr, addr))
 922                         return (&hent->host);
 923         }
 924         return (NULL);
 925 }
 926
 927 /*
 928  * Add a new host entry to the table. This assumes the host doesn't
 929  * already exist in the table. Returns 1 on success, 0 if there
 930  * was a memory allocation failure.
 931  */
 932 static int
 933 ng_bridge_put(priv_p priv, const u_char *addr, link_p link)
 934 {
 935         const int bucket = HASH(addr, priv->hashMask);
 936         struct ng_bridge_hent *hent;
 937
 938 #ifdef INVARIANTS
 939         /* Assert that entry does not already exist in hashtable */
 940         SLIST_FOREACH(hent, &priv->tab[bucket], next) {
 941                 KASSERT(!ETHER_EQUAL(hent->host.addr, addr),
 942                     ("%s: entry %6D exists in table", __func__, addr, ":"));
 943         }
 944 #endif
 945
 946         /* Allocate and initialize new hashtable entry */
 947         hent = malloc(sizeof(*hent), M_NETGRAPH_BRIDGE, M_NOWAIT);
 948         if (hent == NULL)
 949                 return (0);
 950         bcopy(addr, hent->host.addr, ETHER_ADDR_LEN);
 951         hent->host.link = link;
 952         hent->host.staleness = 0;
 953         hent->host.age = 0;
 954
 955         /* Add new element to hash bucket */
 956         SLIST_INSERT_HEAD(&priv->tab[bucket], hent, next);
 957         priv->numHosts++;
 958
 959         /* Resize table if necessary */
 960         ng_bridge_rehash(priv);
 961         return (1);
 962 }
 963
 964 /*
 965  * Resize the hash table. We try to maintain the number of buckets
 966  * such that the load factor is in the range 0.25 to 1.0.
 967  *
 968  * If we can't get the new memory then we silently fail. This is OK
 969  * because things will still work and we'll try again soon anyway.
 970  */
 971 static void
 972 ng_bridge_rehash(priv_p priv)
 973 {
 974         struct ng_bridge_bucket *newTab;
 975         int oldBucket, newBucket;
 976         int newNumBuckets;
 977         u_int newMask;
 978
 979         /* Is table too full or too empty? */
 980         if (priv->numHosts > priv->numBuckets
 981             && (priv->numBuckets << 1) <= MAX_BUCKETS)
 982                 newNumBuckets = priv->numBuckets << 1;
 983         else if (priv->numHosts < (priv->numBuckets >> 2)
 984             && (priv->numBuckets >> 2) >= MIN_BUCKETS)
 985                 newNumBuckets = priv->numBuckets >> 2;
 986         else
 987                 return;
 988         newMask = newNumBuckets - 1;
 989
 990         /* Allocate and initialize new table */
 991         newTab = malloc(newNumBuckets * sizeof(*newTab),
 992             M_NETGRAPH_BRIDGE, M_NOWAIT | M_ZERO);
 993         if (newTab == NULL)
 994                 return;
 995
 996         /* Move all entries from old table to new table */
 997         for (oldBucket = 0; oldBucket < priv->numBuckets; oldBucket++) {
 998                 struct ng_bridge_bucket *const oldList = &priv->tab[oldBucket];
 999
1000                 while (!SLIST_EMPTY(oldList)) {
1001                         struct ng_bridge_hent *const hent
1002                             = SLIST_FIRST(oldList);
1003
1004                         SLIST_REMOVE_HEAD(oldList, next);
1005                         newBucket = HASH(hent->host.addr, newMask);
1006                         SLIST_INSERT_HEAD(&newTab[newBucket], hent, next);
1007                 }
1008         }
1009
1010         /* Replace old table with new one */
1011         if (priv->conf.debugLevel >= 3) {
1012                 log(LOG_INFO, "ng_bridge: %s: table size %d -> %d\n",
1013                     ng_bridge_nodename(priv->node),
1014                     priv->numBuckets, newNumBuckets);
1015         }
1016         free(priv->tab, M_NETGRAPH_BRIDGE);
1017         priv->numBuckets = newNumBuckets;
1018         priv->hashMask = newMask;
1019         priv->tab = newTab;
1020         return;
1021 }
1022
1023 /******************************************************************
1024                     MISC FUNCTIONS
1025 ******************************************************************/
1026
1027
1028 /*
1029  * Remove all hosts associated with a specific link from the hashtable.
1030  * If linkNum == -1, then remove all hosts in the table.
1031  */
1032 static void
1033 ng_bridge_remove_hosts(priv_p priv, link_p link)
1034 {
1035         int bucket;
1036
1037         for (bucket = 0; bucket < priv->numBuckets; bucket++) {
1038                 struct ng_bridge_hent **hptr = &SLIST_FIRST(&priv->tab[bucket]);
1039
1040                 while (*hptr != NULL) {
1041                         struct ng_bridge_hent *const hent = *hptr;
1042
1043                         if (link == NULL || hent->host.link == link) {
1044                                 *hptr = SLIST_NEXT(hent, next);
1045                                 free(hent, M_NETGRAPH_BRIDGE);
1046                                 priv->numHosts--;
1047                         } else
1048                                 hptr = &SLIST_NEXT(hent, next);
1049                 }
1050         }
1051 }
1052
1053 /*
1054  * Handle our once-per-second timeout event. We do two things:
1055  * we decrement link->loopCount for those links being muted due to
1056  * a detected loopback condition, and we remove any hosts from
1057  * the hashtable whom we haven't heard from in a long while.
1058  */
1059 static int
1060 ng_bridge_unmute(hook_p hook, void *arg)
1061 {
1062         link_p link = NG_HOOK_PRIVATE(hook);
1063         node_p node = NG_HOOK_NODE(hook);
1064         priv_p priv = NG_NODE_PRIVATE(node);
1065         int *counter = arg;
1066
1067         if (link->loopCount != 0) {
1068                 link->loopCount--;
1069                 if (link->loopCount == 0 && priv->conf.debugLevel >= 2) {
1070                         log(LOG_INFO, "ng_bridge: %s:"
1071                             " restoring looped back %s\n",
1072                             ng_bridge_nodename(node), NG_HOOK_NAME(hook));
1073                 }
1074         }
1075         (*counter)++;
1076         return (1);
1077 }
1078
1079 static void
1080 ng_bridge_timeout(node_p node, hook_p hook, void *arg1, int arg2)
1081 {
1082         const priv_p priv = NG_NODE_PRIVATE(node);
1083         int bucket;
1084         int counter = 0;
1085         hook_p ret;
1086
1087         /* Update host time counters and remove stale entries */
1088         for (bucket = 0; bucket < priv->numBuckets; bucket++) {
1089                 struct ng_bridge_hent **hptr = &SLIST_FIRST(&priv->tab[bucket]);
1090
1091                 while (*hptr != NULL) {
1092                         struct ng_bridge_hent *const hent = *hptr;
1093
1094                         /* Remove hosts we haven't heard from in a while */
1095                         if (++hent->host.staleness >= priv->conf.maxStaleness) {
1096                                 *hptr = SLIST_NEXT(hent, next);
1097                                 free(hent, M_NETGRAPH_BRIDGE);
1098                                 priv->numHosts--;
1099                         } else {
1100                                 if (hent->host.age < 0xffff)
1101                                         hent->host.age++;
1102                                 hptr = &SLIST_NEXT(hent, next);
1103                                 counter++;
1104                         }
1105                 }
1106         }
1107         KASSERT(priv->numHosts == counter,
1108             ("%s: hosts: %d != %d", __func__, priv->numHosts, counter));
1109
1110         /* Decrease table size if necessary */
1111         ng_bridge_rehash(priv);
1112
1113         /* Decrease loop counter on muted looped back links */
1114         counter = 0;
1115         NG_NODE_FOREACH_HOOK(node, ng_bridge_unmute, &counter, ret);
1116         KASSERT(priv->numLinks == counter,
1117             ("%s: links: %d != %d", __func__, priv->numLinks, counter));
1118
1119         /* Register a new timeout, keeping the existing node reference */
1120         ng_callout(&priv->timer, node, NULL, hz, ng_bridge_timeout, NULL, 0);
1121 }
1122
1123 /*
1124  * Return node's "name", even if it doesn't have one.
1125  */
1126 static const char *
1127 ng_bridge_nodename(node_p node)
1128 {
1129         static char name[NG_NODESIZ];
1130
1131         if (NG_NODE_HAS_NAME(node))
1132                 snprintf(name, sizeof(name), "%s", NG_NODE_NAME(node));
1133         else
1134                 snprintf(name, sizeof(name), "[%x]", ng_node2ID(node));
1135         return name;
1136 }
1137