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