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