1 /* 2 * Copyright (c) 2000 Jason L. Wright (jason@thought.net) 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. All advertising materials mentioning features or use of this software 14 * must display the following acknowledgement: 15 * This product includes software developed by Jason L. Wright 16 * 4. The name of the author may not be used to endorse or promote products 17 * derived from this software without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 20 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 21 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 22 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, 23 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 24 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 25 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 27 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 28 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 * 31 * $OpenBSD: bridgestp.c,v 1.5 2001/03/22 03:48:29 jason Exp $ 32 * $NetBSD: bridgestp.c,v 1.5 2003/11/28 08:56:48 keihan Exp $ 33 * $FreeBSD: src/sys/net/bridgestp.c,v 1.7 2005/10/11 02:58:32 thompsa Exp $ 34 */ 35 36 /* 37 * Implementation of the spanning tree protocol as defined in 38 * ISO/IEC Final DIS 15802-3 (IEEE P802.1D/D17), May 25, 1998. 39 * (In English: IEEE 802.1D, Draft 17, 1998) 40 */ 41 42 #include <sys/param.h> 43 #include <sys/systm.h> 44 #include <sys/malloc.h> /* for M_NOWAIT */ 45 #include <sys/mbuf.h> 46 #include <sys/socket.h> 47 #include <sys/sockio.h> 48 #include <sys/kernel.h> 49 #include <sys/callout.h> 50 #include <sys/proc.h> 51 #include <sys/lock.h> 52 #include <sys/thread.h> 53 #include <sys/thread2.h> 54 #include <sys/msgport2.h> 55 56 #include <net/if.h> 57 #include <net/if_dl.h> 58 #include <net/if_types.h> 59 #include <net/if_llc.h> 60 #include <net/if_media.h> 61 62 #include <netinet/in.h> 63 #include <netinet/in_systm.h> 64 #include <netinet/in_var.h> 65 #include <netinet/if_ether.h> 66 #include <net/bridge/if_bridgevar.h> 67 68 /* BPDU message types */ 69 #define BSTP_MSGTYPE_CFG 0x00 /* Configuration */ 70 #define BSTP_MSGTYPE_TCN 0x80 /* Topology chg notification */ 71 72 /* BPDU flags */ 73 #define BSTP_FLAG_TC 0x01 /* Topology change */ 74 #define BSTP_FLAG_TCA 0x80 /* Topology change ack */ 75 76 #define BSTP_MESSAGE_AGE_INCR (1 * 256) /* in 256ths of a second */ 77 #define BSTP_TICK_VAL (1 * 256) /* in 256ths of a second */ 78 79 /* 80 * Because BPDU's do not make nicely aligned structures, two different 81 * declarations are used: bstp_?bpdu (wire representation, packed) and 82 * bstp_*_unit (internal, nicely aligned version). 83 */ 84 85 /* configuration bridge protocol data unit */ 86 struct bstp_cbpdu { 87 uint8_t cbu_dsap; /* LLC: destination sap */ 88 uint8_t cbu_ssap; /* LLC: source sap */ 89 uint8_t cbu_ctl; /* LLC: control */ 90 uint16_t cbu_protoid; /* protocol id */ 91 uint8_t cbu_protover; /* protocol version */ 92 uint8_t cbu_bpdutype; /* message type */ 93 uint8_t cbu_flags; /* flags (below) */ 94 95 /* root id */ 96 uint16_t cbu_rootpri; /* root priority */ 97 uint8_t cbu_rootaddr[6]; /* root address */ 98 99 uint32_t cbu_rootpathcost; /* root path cost */ 100 101 /* bridge id */ 102 uint16_t cbu_bridgepri; /* bridge priority */ 103 uint8_t cbu_bridgeaddr[6]; /* bridge address */ 104 105 uint16_t cbu_portid; /* port id */ 106 uint16_t cbu_messageage; /* current message age */ 107 uint16_t cbu_maxage; /* maximum age */ 108 uint16_t cbu_hellotime; /* hello time */ 109 uint16_t cbu_forwarddelay; /* forwarding delay */ 110 } __attribute__((__packed__)); 111 112 /* topology change notification bridge protocol data unit */ 113 struct bstp_tbpdu { 114 uint8_t tbu_dsap; /* LLC: destination sap */ 115 uint8_t tbu_ssap; /* LLC: source sap */ 116 uint8_t tbu_ctl; /* LLC: control */ 117 uint16_t tbu_protoid; /* protocol id */ 118 uint8_t tbu_protover; /* protocol version */ 119 uint8_t tbu_bpdutype; /* message type */ 120 } __attribute__((__packed__)); 121 122 const uint8_t bstp_etheraddr[] = { 0x01, 0x80, 0xc2, 0x00, 0x00, 0x00 }; 123 124 static void bstp_initialize_port(struct bridge_softc *, 125 struct bridge_iflist *); 126 static void bstp_ifupdstatus(struct bridge_softc *, struct bridge_iflist *); 127 static void bstp_enable_port(struct bridge_softc *, struct bridge_iflist *); 128 static void bstp_disable_port(struct bridge_softc *, 129 struct bridge_iflist *); 130 #ifdef notused 131 static void bstp_enable_change_detection(struct bridge_iflist *); 132 static void bstp_disable_change_detection(struct bridge_iflist *); 133 #endif /* notused */ 134 static int bstp_root_bridge(struct bridge_softc *sc); 135 static void bstp_transmit_config(struct bridge_softc *, 136 struct bridge_iflist *); 137 static void bstp_transmit_tcn(struct bridge_softc *); 138 static void bstp_received_config_bpdu(struct bridge_softc *, 139 struct bridge_iflist *, struct bstp_config_unit *); 140 static void bstp_received_tcn_bpdu(struct bridge_softc *, 141 struct bridge_iflist *, struct bstp_tcn_unit *); 142 static void bstp_record_config_information(struct bridge_softc *, 143 struct bridge_iflist *, struct bstp_config_unit *); 144 static void bstp_record_config_timeout_values(struct bridge_softc *, 145 struct bstp_config_unit *); 146 static void bstp_config_bpdu_generation(struct bridge_softc *); 147 static void bstp_send_config_bpdu(struct bridge_softc *, 148 struct bridge_iflist *, struct bstp_config_unit *); 149 static void bstp_configuration_update(struct bridge_softc *); 150 static void bstp_port_state_selection(struct bridge_softc *); 151 static void bstp_clear_peer_info(struct bridge_softc *, 152 struct bridge_iflist *); 153 static void bstp_make_forwarding(struct bridge_softc *, 154 struct bridge_iflist *); 155 static void bstp_make_blocking(struct bridge_softc *, 156 struct bridge_iflist *); 157 static void bstp_make_l1blocking(struct bridge_softc *sc, 158 struct bridge_iflist *bif); 159 static void bstp_adjust_bonded_states(struct bridge_softc *sc, 160 struct bridge_iflist *obif); 161 static void bstp_set_port_state(struct bridge_iflist *, uint8_t); 162 #ifdef notused 163 static void bstp_set_bridge_priority(struct bridge_softc *, uint64_t); 164 static void bstp_set_port_priority(struct bridge_softc *, 165 struct bridge_iflist *, uint16_t); 166 static void bstp_set_path_cost(struct bridge_softc *, 167 struct bridge_iflist *, uint32_t); 168 #endif /* notused */ 169 static void bstp_topology_change_detection(struct bridge_softc *); 170 static void bstp_topology_change_acknowledged(struct bridge_softc *); 171 static void bstp_acknowledge_topology_change(struct bridge_softc *, 172 struct bridge_iflist *); 173 174 static void bstp_tick(void *); 175 static void bstp_timer_start(struct bridge_timer *, uint16_t); 176 static void bstp_timer_stop(struct bridge_timer *); 177 static int bstp_timer_expired(struct bridge_timer *, uint16_t); 178 179 static void bstp_hold_timer_expiry(struct bridge_softc *, 180 struct bridge_iflist *); 181 static void bstp_message_age_timer_expiry(struct bridge_softc *, 182 struct bridge_iflist *); 183 static void bstp_forward_delay_timer_expiry(struct bridge_softc *, 184 struct bridge_iflist *); 185 static void bstp_topology_change_timer_expiry(struct bridge_softc *); 186 static void bstp_tcn_timer_expiry(struct bridge_softc *); 187 static void bstp_hello_timer_expiry(struct bridge_softc *); 188 static int bstp_addr_cmp(const uint8_t *, const uint8_t *); 189 190 /* 191 * When transmitting a config we tack on our path cost to 192 * our aggregated path-to-root cost. 193 * 194 * Note that sc_designated_cost is the lowest root path cost from all 195 * incoming links. When one is talking about two bridges with multiple 196 * links between them the root path cost the secondary bridge transmits 197 * will be the lowest root path cost it received across those three 198 * links and NOT necessarily the root path cost it received specifically 199 * on that particular link. The receiving end must still add its local 200 * link cost back in for differentiation purposes. 201 */ 202 static void 203 bstp_transmit_config(struct bridge_softc *sc, struct bridge_iflist *bif) 204 { 205 if (bif->bif_hold_timer.active) { 206 bif->bif_config_pending = 1; 207 return; 208 } 209 210 bif->bif_config_bpdu.cu_message_type = BSTP_MSGTYPE_CFG; 211 bif->bif_config_bpdu.cu_rootid = sc->sc_designated_root; 212 bif->bif_config_bpdu.cu_root_path_cost = sc->sc_designated_cost + 213 bif->bif_path_cost; 214 bif->bif_config_bpdu.cu_bridge_id = sc->sc_bridge_id; 215 bif->bif_config_bpdu.cu_port_id = bif->bif_port_id; 216 217 if (bstp_root_bridge(sc)) { 218 bif->bif_config_bpdu.cu_message_age = 0; 219 } else if (sc->sc_root_port) { 220 bif->bif_config_bpdu.cu_message_age = 221 sc->sc_root_port->bif_message_age_timer.value + 222 BSTP_MESSAGE_AGE_INCR; 223 } else { 224 bif->bif_config_bpdu.cu_message_age = BSTP_MESSAGE_AGE_INCR; 225 } 226 227 bif->bif_config_bpdu.cu_max_age = sc->sc_max_age; 228 bif->bif_config_bpdu.cu_hello_time = sc->sc_hello_time; 229 bif->bif_config_bpdu.cu_forward_delay = sc->sc_forward_delay; 230 bif->bif_config_bpdu.cu_topology_change_acknowledgment 231 = bif->bif_topology_change_acknowledge; 232 bif->bif_config_bpdu.cu_topology_change = sc->sc_topology_change; 233 234 if (bif->bif_config_bpdu.cu_message_age < sc->sc_max_age || 235 (sc->sc_ifp->if_flags & IFF_LINK1)) { 236 bif->bif_topology_change_acknowledge = 0; 237 bif->bif_config_pending = 0; 238 bstp_send_config_bpdu(sc, bif, &bif->bif_config_bpdu); 239 bstp_timer_start(&bif->bif_hold_timer, 0); 240 } 241 } 242 243 static void 244 bstp_send_config_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif, 245 struct bstp_config_unit *cu) 246 { 247 struct ifnet *ifp; 248 struct mbuf *m; 249 struct ether_header *eh; 250 struct bstp_cbpdu bpdu; 251 252 ifp = bif->bif_ifp; 253 254 if ((ifp->if_flags & IFF_RUNNING) == 0) 255 return; 256 257 MGETHDR(m, M_NOWAIT, MT_DATA); 258 if (m == NULL) 259 return; 260 261 eh = mtod(m, struct ether_header *); 262 263 m->m_pkthdr.rcvif = ifp; 264 m->m_pkthdr.len = sizeof(*eh) + sizeof(bpdu); 265 m->m_len = m->m_pkthdr.len; 266 267 bpdu.cbu_ssap = bpdu.cbu_dsap = LLC_8021D_LSAP; 268 bpdu.cbu_ctl = LLC_UI; 269 bpdu.cbu_protoid = htons(0); 270 bpdu.cbu_protover = 0; 271 bpdu.cbu_bpdutype = cu->cu_message_type; 272 bpdu.cbu_flags = (cu->cu_topology_change ? BSTP_FLAG_TC : 0) | 273 (cu->cu_topology_change_acknowledgment ? BSTP_FLAG_TCA : 0); 274 275 bpdu.cbu_rootpri = htons(cu->cu_rootid >> 48); 276 bpdu.cbu_rootaddr[0] = cu->cu_rootid >> 40; 277 bpdu.cbu_rootaddr[1] = cu->cu_rootid >> 32; 278 bpdu.cbu_rootaddr[2] = cu->cu_rootid >> 24; 279 bpdu.cbu_rootaddr[3] = cu->cu_rootid >> 16; 280 bpdu.cbu_rootaddr[4] = cu->cu_rootid >> 8; 281 bpdu.cbu_rootaddr[5] = cu->cu_rootid >> 0; 282 283 bpdu.cbu_rootpathcost = htonl(cu->cu_root_path_cost); 284 285 bpdu.cbu_bridgepri = htons(cu->cu_bridge_id >> 48); 286 bpdu.cbu_bridgeaddr[0] = cu->cu_bridge_id >> 40; 287 bpdu.cbu_bridgeaddr[1] = cu->cu_bridge_id >> 32; 288 bpdu.cbu_bridgeaddr[2] = cu->cu_bridge_id >> 24; 289 bpdu.cbu_bridgeaddr[3] = cu->cu_bridge_id >> 16; 290 bpdu.cbu_bridgeaddr[4] = cu->cu_bridge_id >> 8; 291 bpdu.cbu_bridgeaddr[5] = cu->cu_bridge_id >> 0; 292 293 bpdu.cbu_portid = htons(cu->cu_port_id); 294 bpdu.cbu_messageage = htons(cu->cu_message_age); 295 bpdu.cbu_maxage = htons(cu->cu_max_age); 296 bpdu.cbu_hellotime = htons(cu->cu_hello_time); 297 bpdu.cbu_forwarddelay = htons(cu->cu_forward_delay); 298 299 /* 300 * Packets sent from the bridge always use the bridge MAC 301 * as the source. 302 */ 303 memcpy(eh->ether_shost, IF_LLADDR(sc->sc_ifp), ETHER_ADDR_LEN); 304 memcpy(eh->ether_dhost, bstp_etheraddr, ETHER_ADDR_LEN); 305 eh->ether_type = htons(sizeof(bpdu)); 306 307 memcpy(mtod(m, caddr_t) + sizeof(*eh), &bpdu, sizeof(bpdu)); 308 309 bridge_enqueue(ifp, m); 310 } 311 312 static int 313 bstp_root_bridge(struct bridge_softc *sc) 314 { 315 return (sc->sc_designated_root == sc->sc_bridge_id); 316 } 317 318 /* 319 * Returns TRUE if the recorded information from our peer has a shorter 320 * graph distance than our current best. 321 */ 322 int 323 bstp_supersedes_port_info(struct bridge_softc *sc, struct bridge_iflist *bif) 324 { 325 if (bif->bif_peer_root < sc->sc_designated_root) 326 return (1); 327 if (bif->bif_peer_root > sc->sc_designated_root) 328 return (0); 329 330 /* 331 * bif_peer_cost and sc_designated_cost do not include the local 332 * bif_path_cost, otherwise we would not be able to make this 333 * comparison. 334 */ 335 if (bif->bif_peer_cost < sc->sc_designated_cost) 336 return (1); 337 if (bif->bif_peer_cost > sc->sc_designated_cost) 338 return (0); 339 340 /* 341 * When the peer costs match we have to check the local path 342 * cost against the selected root port. sc_designated_cost 343 * in an aggregation and cannot be used. 344 */ 345 if (sc->sc_root_port && 346 bif->bif_path_cost < sc->sc_root_port->bif_path_cost) 347 return (1); 348 if (sc->sc_root_port && 349 bif->bif_path_cost > sc->sc_root_port->bif_path_cost) 350 return (0); 351 352 /* 353 * If the path costs are identical the bridge with the lowest 354 * bridge_id wins. 355 */ 356 if (bif->bif_peer_bridge < sc->sc_designated_bridge) 357 return (1); 358 if (bif->bif_peer_bridge > sc->sc_designated_bridge) 359 return (0); 360 361 /* 362 * bridge_id or bridge+port collision w/peer returns TRUE. 363 * 364 * This case can also occur when two bridges are connected 365 * via multiple links whos path costs have not been set. 366 */ 367 if (bif->bif_peer_bridge != sc->sc_bridge_id) 368 return (1); 369 if (bif->bif_peer_port <= sc->sc_designated_port) 370 return (1); 371 return (0); 372 } 373 374 /* 375 * The shorter graph distance represented by cu (most of which is also 376 * already stored in our bif_peer_* fields) becomes the designated info. 377 * 378 * NOTE: sc_designated_cost does not include bif_path_cost, it is added 379 * in later on a port-by-port basis as needed. 380 */ 381 static void 382 bstp_record_config_information(struct bridge_softc *sc, 383 struct bridge_iflist *bif, 384 struct bstp_config_unit *cu) 385 { 386 sc->sc_designated_root = bif->bif_peer_root; 387 sc->sc_designated_cost = bif->bif_peer_cost; 388 sc->sc_designated_bridge = bif->bif_peer_bridge; 389 sc->sc_designated_port = bif->bif_peer_port; 390 bstp_timer_start(&bif->bif_message_age_timer, cu->cu_message_age); 391 } 392 393 static void 394 bstp_record_config_timeout_values(struct bridge_softc *sc, 395 struct bstp_config_unit *config) 396 { 397 sc->sc_max_age = config->cu_max_age; 398 sc->sc_hello_time = config->cu_hello_time; 399 sc->sc_forward_delay = config->cu_forward_delay; 400 sc->sc_topology_change = config->cu_topology_change; 401 } 402 403 static void 404 bstp_config_bpdu_generation(struct bridge_softc *sc) 405 { 406 struct bridge_iflist *bif, *nbif; 407 408 TAILQ_FOREACH_MUTABLE(bif, &sc->sc_iflists[mycpuid], bif_next, nbif) { 409 if ((bif->bif_flags & IFBIF_STP) == 0) 410 continue; 411 if (bif->bif_state != BSTP_IFSTATE_DISABLED && 412 ((sc->sc_ifp->if_flags & IFF_LINK1) || 413 (bif->bif_flags & IFBIF_DESIGNATED))) { 414 bstp_transmit_config(sc, bif); 415 } 416 417 if (nbif != NULL && !nbif->bif_onlist) { 418 KKASSERT(bif->bif_onlist); 419 nbif = TAILQ_NEXT(bif, bif_next); 420 } 421 } 422 } 423 424 static void 425 bstp_transmit_tcn(struct bridge_softc *sc) 426 { 427 struct bstp_tbpdu bpdu; 428 struct ifnet *ifp; 429 struct ether_header *eh; 430 struct mbuf *m; 431 432 if (sc->sc_root_port == NULL) /* all iterfaces disabled */ 433 return; 434 435 ifp = sc->sc_root_port->bif_ifp; 436 if ((ifp->if_flags & IFF_RUNNING) == 0) 437 return; 438 439 MGETHDR(m, M_NOWAIT, MT_DATA); 440 if (m == NULL) 441 return; 442 443 m->m_pkthdr.rcvif = ifp; 444 m->m_pkthdr.len = sizeof(*eh) + sizeof(bpdu); 445 m->m_len = m->m_pkthdr.len; 446 447 eh = mtod(m, struct ether_header *); 448 449 /* 450 * Packets sent from the bridge always use the bridge MAC 451 * as the source. 452 */ 453 memcpy(eh->ether_shost, IF_LLADDR(sc->sc_ifp), ETHER_ADDR_LEN); 454 memcpy(eh->ether_dhost, bstp_etheraddr, ETHER_ADDR_LEN); 455 eh->ether_type = htons(sizeof(bpdu)); 456 457 bpdu.tbu_ssap = bpdu.tbu_dsap = LLC_8021D_LSAP; 458 bpdu.tbu_ctl = LLC_UI; 459 bpdu.tbu_protoid = 0; 460 bpdu.tbu_protover = 0; 461 bpdu.tbu_bpdutype = BSTP_MSGTYPE_TCN; 462 463 memcpy(mtod(m, caddr_t) + sizeof(*eh), &bpdu, sizeof(bpdu)); 464 465 bridge_enqueue(ifp, m); 466 } 467 468 /* 469 * Recalculate sc->sc_designated* and sc->sc_root_port (if our bridge 470 * is calculated to be the root bridge). We do this by initializing 471 * the designated variables to point at us and then scan our peers. 472 * Any uninitialized peers will have a max-value root. 473 * 474 * Clear IFBIF_DESIGNATED on any ports which no longer match the criteria 475 * required to be a designated port. Only aged out ports and the root 476 * port can be designated. 477 * 478 * If we win we do a second scan to determine which port on our bridge 479 * is the best. 480 */ 481 static void 482 bstp_configuration_update(struct bridge_softc *sc) 483 { 484 uint64_t designated_root = sc->sc_bridge_id; 485 uint64_t designated_bridge = sc->sc_bridge_id; 486 uint32_t designated_cost = 0xFFFFFFFFU; 487 uint32_t designated_root_cost = 0xFFFFFFFFU; 488 uint16_t designated_port = 65535; 489 struct bridge_iflist *root_port = NULL; 490 struct bridge_iflist *bif; 491 492 /* 493 * Resolve information from our peers. Aged peers will have 494 * a maxed bif_peer_root and not come under consideration. 495 */ 496 TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) { 497 if ((bif->bif_flags & IFBIF_STP) == 0) 498 continue; 499 if (bif->bif_state == BSTP_IFSTATE_DISABLED || 500 bif->bif_state == BSTP_IFSTATE_L1BLOCKING) { 501 continue; 502 } 503 504 if (bif->bif_peer_root > designated_root) 505 continue; 506 if (bif->bif_peer_root < designated_root) 507 goto set_port; 508 509 /* 510 * NOTE: The designated_cost temporary variable already added 511 * in the path code of the related root port. 512 */ 513 if (bif->bif_peer_cost + bif->bif_path_cost > designated_cost) 514 continue; 515 if (bif->bif_peer_cost + bif->bif_path_cost < designated_cost) 516 goto set_port; 517 518 if (bif->bif_peer_bridge > designated_bridge) 519 continue; 520 if (bif->bif_peer_bridge < designated_bridge) 521 goto set_port; 522 523 if (bif->bif_peer_port > designated_port) 524 continue; 525 if (bif->bif_peer_port < designated_port) 526 goto set_port; 527 528 /* 529 * Same root, path cost, bridge, and port. Set the root 530 * only if we do not already have it. 531 */ 532 if (root_port) 533 continue; 534 535 /* 536 * New root port (from peers) 537 * 538 * NOTE: Temporarily add bif_path_cost into the designated 539 * cost to reduce complexity in the loop, it will be 540 * subtracted out when we are done. 541 */ 542 set_port: 543 designated_root = bif->bif_peer_root; 544 designated_cost = bif->bif_peer_cost + bif->bif_path_cost; 545 designated_root_cost = bif->bif_peer_cost; 546 designated_bridge = bif->bif_peer_bridge; 547 designated_port = bif->bif_peer_port; 548 root_port = bif; 549 } 550 551 /* 552 * root_port will be NULL at the start here if all of our 553 * peers are aged or are not as good a root as our bridge would 554 * be. It can also be NULL due to all related links being 555 * disabled. 556 * 557 * If the root winds up being our bridge scan again against local 558 * information. Unconditionally update IFBIF_DESIGNATED. 559 */ 560 TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) { 561 bif->bif_flags &= ~(IFBIF_DESIGNATED | IFBIF_ROOT); 562 if ((bif->bif_flags & IFBIF_STP) == 0) 563 continue; 564 if (bif->bif_state == BSTP_IFSTATE_DISABLED || 565 bif->bif_state == BSTP_IFSTATE_L1BLOCKING) { 566 continue; 567 } 568 569 /* 570 * Set DESIGNATED for an aged or unknown peer. 571 */ 572 if (bif->bif_peer_bridge == 0xFFFFFFFFFFFFFFFFLLU) 573 bif->bif_flags |= IFBIF_DESIGNATED; 574 if (designated_root != sc->sc_bridge_id) 575 continue; 576 577 /* 578 * This is only reached if our bridge is the root bridge, 579 * select the root port (IFBIF_DESIGNATED is set at the 580 * end). 581 * 582 * The peer cost will incorporate the peer bridge's best 583 * cost to the root bridge (us), which is NOT necessarily 584 * our path cost, plus the peer bridge's own path cost. 585 * Because of this we must still add in our path cost for 586 * further differentiation. Because the peer's 'best' cost 587 * is applied to all of its outgoing messages we should 588 * still come to the same conclusion as the peer. 589 */ 590 if (bif->bif_peer_cost + bif->bif_path_cost > designated_cost) 591 continue; 592 if (bif->bif_peer_cost + bif->bif_path_cost < designated_cost) 593 goto set_port2; 594 595 if (bif->bif_port_id > designated_port) 596 continue; 597 if (bif->bif_port_id < designated_port) 598 goto set_port2; 599 /* degenerate case (possible peer collision w/our key */ 600 601 /* 602 * New port. Since we are the root, the root cost is always 603 * 0. The peer's cu_root_path_cost does not necessarily 604 * incorporate our peer path cost, but instead incorporates 605 * the lowest path cost to root for the target bridge 606 * when multiple links are present between the two bridges. 607 * Thus for selection purposes we must still add in our 608 * local path cost. 609 */ 610 set_port2: 611 designated_cost = bif->bif_peer_cost + bif->bif_path_cost; 612 designated_root_cost = 0; 613 designated_bridge = sc->sc_bridge_id; 614 designated_port = bif->bif_port_id; 615 root_port = bif; 616 } 617 618 /* 619 * Update aggregate information. The selected root port always 620 * becomes a designated port (along with aged ports). This can 621 * either be the port whos peer is closest to the root or it 622 * can be one of our ports if our bridge is the root. 623 * 624 * The root cost we record in sc_designated_root does not include 625 * bif_path_cost of the root port, since we may transmit this 626 * out of any port we will add the cost back in later on on 627 * a per-port basis. 628 * 629 * root_port can be NULL here (if all links are disabled) 630 */ 631 if (root_port) { 632 sc->sc_designated_root = designated_root; 633 sc->sc_designated_cost = designated_root_cost; 634 sc->sc_designated_bridge = designated_bridge; 635 sc->sc_designated_port = designated_port; 636 root_port->bif_flags |= IFBIF_DESIGNATED | IFBIF_ROOT; 637 } else { 638 sc->sc_designated_root = designated_root; 639 sc->sc_designated_cost = designated_cost; 640 sc->sc_designated_bridge = designated_bridge; 641 sc->sc_designated_port = designated_port; 642 } 643 sc->sc_root_port = root_port; 644 } 645 646 /* 647 * Calculate the desired state for each interface link on our bridge. 648 * 649 * The best port will match against sc->sc_root_port (whether we are root 650 * or whether that port is the closest to the root). We push this port 651 * towards a FORWARDING state. 652 * 653 * Next come designated ports, either aged ports or ports with no peer info 654 * (yet), or the peer who is closest to the root. We push this port towards 655 * a FORWARDING state as well. 656 * 657 * Any remaining ports are pushed towards a BLOCKING state. Both sides of 658 * the port (us and our peer) should wind up placing the two ends in this 659 * state or bad things happen. 660 */ 661 static void 662 bstp_port_state_selection(struct bridge_softc *sc) 663 { 664 struct bridge_iflist *bif, *nbif; 665 666 TAILQ_FOREACH_MUTABLE(bif, &sc->sc_iflists[mycpuid], bif_next, nbif) { 667 if ((bif->bif_flags & IFBIF_STP) == 0) 668 continue; 669 if (sc->sc_root_port && 670 bif->bif_info == sc->sc_root_port->bif_info) { 671 bif->bif_config_pending = 0; 672 bif->bif_topology_change_acknowledge = 0; 673 bstp_make_forwarding(sc, bif); 674 } else if (bif->bif_flags & IFBIF_DESIGNATED) { 675 bstp_timer_stop(&bif->bif_message_age_timer); 676 bstp_make_forwarding(sc, bif); 677 } else { 678 bif->bif_config_pending = 0; 679 bif->bif_topology_change_acknowledge = 0; 680 bstp_make_blocking(sc, bif); 681 } 682 683 if (nbif != NULL && !nbif->bif_onlist) { 684 KKASSERT(bif->bif_onlist); 685 nbif = TAILQ_NEXT(bif, bif_next); 686 } 687 } 688 } 689 690 /* 691 * Clear peer info, effectively makes the port looked aged out. 692 * It becomes a designated go-to port. 693 */ 694 static void 695 bstp_clear_peer_info(struct bridge_softc *sc, struct bridge_iflist *bif) 696 { 697 bif->bif_peer_root = 0xFFFFFFFFFFFFFFFFLLU; 698 bif->bif_peer_cost = 0xFFFFFFFFU; 699 bif->bif_peer_bridge = 0xFFFFFFFFFFFFFFFFLLU; 700 bif->bif_peer_port = 0xFFFFU; 701 702 if (bif->bif_state != BSTP_IFSTATE_DISABLED && 703 bif->bif_state != BSTP_IFSTATE_L1BLOCKING) { 704 bif->bif_flags |= IFBIF_DESIGNATED; 705 } 706 } 707 708 static void 709 bstp_make_forwarding(struct bridge_softc *sc, struct bridge_iflist *bif) 710 { 711 if (bif->bif_state == BSTP_IFSTATE_BLOCKING || 712 bif->bif_state == BSTP_IFSTATE_BONDED) { 713 bstp_set_port_state(bif, BSTP_IFSTATE_LISTENING); 714 bstp_timer_start(&bif->bif_forward_delay_timer, 0); 715 } 716 } 717 718 static void 719 bstp_make_blocking(struct bridge_softc *sc, struct bridge_iflist *bif) 720 { 721 if (bif->bif_state != BSTP_IFSTATE_DISABLED && 722 bif->bif_state != BSTP_IFSTATE_BLOCKING && 723 bif->bif_state != BSTP_IFSTATE_BONDED && 724 bif->bif_state != BSTP_IFSTATE_L1BLOCKING) { 725 if ((bif->bif_state == BSTP_IFSTATE_FORWARDING) || 726 (bif->bif_state == BSTP_IFSTATE_LEARNING)) { 727 if (bif->bif_change_detection_enabled) { 728 bstp_topology_change_detection(sc); 729 } 730 } 731 bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING); 732 bridge_rtdelete(sc, bif->bif_ifp, IFBF_FLUSHDYN); 733 bstp_timer_stop(&bif->bif_forward_delay_timer); 734 if (sc->sc_ifp->if_flags & IFF_LINK2) 735 bstp_adjust_bonded_states(sc, bif); 736 } 737 } 738 739 static void 740 bstp_make_l1blocking(struct bridge_softc *sc, struct bridge_iflist *bif) 741 { 742 int was_forwarding = (bif->bif_state == BSTP_IFSTATE_FORWARDING); 743 744 switch(bif->bif_state) { 745 case BSTP_IFSTATE_LISTENING: 746 case BSTP_IFSTATE_LEARNING: 747 case BSTP_IFSTATE_FORWARDING: 748 case BSTP_IFSTATE_BLOCKING: 749 case BSTP_IFSTATE_BONDED: 750 bstp_set_port_state(bif, BSTP_IFSTATE_L1BLOCKING); 751 bridge_rtdelete(sc, bif->bif_ifp, IFBF_FLUSHDYN); 752 bstp_timer_stop(&bif->bif_forward_delay_timer); 753 bstp_timer_stop(&bif->bif_link1_timer); 754 if (bif->bif_flags & IFBIF_DESIGNATED) { 755 bif->bif_flags &= ~IFBIF_DESIGNATED; 756 bstp_configuration_update(sc); 757 bstp_port_state_selection(sc); 758 } 759 if (was_forwarding && (sc->sc_ifp->if_flags & IFF_LINK2)) 760 bstp_adjust_bonded_states(sc, bif); 761 break; 762 default: 763 break; 764 } 765 } 766 767 /* 768 * Member (bif) changes to or from a FORWARDING state. All members in the 769 * same bonding group which are in a BLOCKING or BONDED state must be set 770 * to either BLOCKING or BONDED based on whether any members in the bonding 771 * group remain in the FORWARDING state. 772 * 773 * Going between the BLOCKING and BONDED states does not require a 774 * configuration update. 775 */ 776 static void 777 bstp_adjust_bonded_states(struct bridge_softc *sc, struct bridge_iflist *obif) 778 { 779 struct bridge_iflist *bif; 780 int state = BSTP_IFSTATE_BLOCKING; 781 782 TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) { 783 if ((bif->bif_flags & IFBIF_STP) == 0) 784 continue; 785 if (bif->bif_state != BSTP_IFSTATE_FORWARDING) 786 continue; 787 if (memcmp(IF_LLADDR(bif->bif_ifp), IF_LLADDR(obif->bif_ifp), 788 ETHER_ADDR_LEN) != 0) { 789 continue; 790 } 791 state = BSTP_IFSTATE_BONDED; 792 break; 793 } 794 TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) { 795 if ((bif->bif_flags & IFBIF_STP) == 0) 796 continue; 797 if (bif->bif_state != BSTP_IFSTATE_BLOCKING && 798 bif->bif_state != BSTP_IFSTATE_BONDED) { 799 continue; 800 } 801 if (memcmp(IF_LLADDR(bif->bif_ifp), IF_LLADDR(obif->bif_ifp), 802 ETHER_ADDR_LEN) != 0) { 803 continue; 804 } 805 if (bif->bif_bond_weight == 0) 806 bif->bif_state = BSTP_IFSTATE_BLOCKING; 807 else 808 bif->bif_state = state; 809 } 810 } 811 812 static void 813 bstp_set_port_state(struct bridge_iflist *bif, uint8_t state) 814 { 815 bif->bif_state = state; 816 } 817 818 static void 819 bstp_topology_change_detection(struct bridge_softc *sc) 820 { 821 if (bstp_root_bridge(sc)) { 822 sc->sc_topology_change = 1; 823 bstp_timer_start(&sc->sc_topology_change_timer, 0); 824 } else if (!sc->sc_topology_change_detected) { 825 bstp_transmit_tcn(sc); 826 bstp_timer_start(&sc->sc_tcn_timer, 0); 827 } 828 sc->sc_topology_change_detected = 1; 829 } 830 831 static void 832 bstp_topology_change_acknowledged(struct bridge_softc *sc) 833 { 834 sc->sc_topology_change_detected = 0; 835 bstp_timer_stop(&sc->sc_tcn_timer); 836 } 837 838 static void 839 bstp_acknowledge_topology_change(struct bridge_softc *sc, 840 struct bridge_iflist *bif) 841 { 842 bif->bif_topology_change_acknowledge = 1; 843 bstp_transmit_config(sc, bif); 844 } 845 846 void 847 bstp_input(struct bridge_softc *sc, struct bridge_iflist *bif, struct mbuf *m) 848 { 849 struct ether_header *eh; 850 struct bstp_tbpdu tpdu; 851 struct bstp_cbpdu cpdu; 852 struct bstp_config_unit cu; 853 struct bstp_tcn_unit tu; 854 uint16_t len; 855 856 if ((bif->bif_flags & IFBIF_STP) == 0) 857 goto out; 858 859 /* 860 * The L1BLOCKING (ping pong failover) test needs to reset the 861 * timer if LINK1 is active. 862 */ 863 if (bif->bif_state == BSTP_IFSTATE_L1BLOCKING) { 864 bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING); 865 if (sc->sc_ifp->if_flags & IFF_LINK1) 866 bstp_timer_start(&bif->bif_link1_timer, 0); 867 bstp_make_forwarding(sc, bif); 868 } else if (sc->sc_ifp->if_flags & IFF_LINK1) { 869 bstp_timer_start(&bif->bif_link1_timer, 0); 870 } 871 872 eh = mtod(m, struct ether_header *); 873 874 len = ntohs(eh->ether_type); 875 if (len < sizeof(tpdu)) 876 goto out; 877 878 m_adj(m, ETHER_HDR_LEN); 879 880 if (m->m_pkthdr.len > len) 881 m_adj(m, len - m->m_pkthdr.len); 882 if (m->m_len < sizeof(tpdu) && 883 (m = m_pullup(m, sizeof(tpdu))) == NULL) 884 goto out; 885 886 memcpy(&tpdu, mtod(m, caddr_t), sizeof(tpdu)); 887 888 if (tpdu.tbu_dsap != LLC_8021D_LSAP || 889 tpdu.tbu_ssap != LLC_8021D_LSAP || 890 tpdu.tbu_ctl != LLC_UI) 891 goto out; 892 if (tpdu.tbu_protoid != 0 || tpdu.tbu_protover != 0) 893 goto out; 894 895 switch (tpdu.tbu_bpdutype) { 896 case BSTP_MSGTYPE_TCN: 897 tu.tu_message_type = tpdu.tbu_bpdutype; 898 bstp_received_tcn_bpdu(sc, bif, &tu); 899 break; 900 case BSTP_MSGTYPE_CFG: 901 if (m->m_len < sizeof(cpdu) && 902 (m = m_pullup(m, sizeof(cpdu))) == NULL) 903 goto out; 904 memcpy(&cpdu, mtod(m, caddr_t), sizeof(cpdu)); 905 906 cu.cu_rootid = 907 (((uint64_t)ntohs(cpdu.cbu_rootpri)) << 48) | 908 (((uint64_t)cpdu.cbu_rootaddr[0]) << 40) | 909 (((uint64_t)cpdu.cbu_rootaddr[1]) << 32) | 910 (((uint64_t)cpdu.cbu_rootaddr[2]) << 24) | 911 (((uint64_t)cpdu.cbu_rootaddr[3]) << 16) | 912 (((uint64_t)cpdu.cbu_rootaddr[4]) << 8) | 913 (((uint64_t)cpdu.cbu_rootaddr[5]) << 0); 914 915 cu.cu_bridge_id = 916 (((uint64_t)ntohs(cpdu.cbu_bridgepri)) << 48) | 917 (((uint64_t)cpdu.cbu_bridgeaddr[0]) << 40) | 918 (((uint64_t)cpdu.cbu_bridgeaddr[1]) << 32) | 919 (((uint64_t)cpdu.cbu_bridgeaddr[2]) << 24) | 920 (((uint64_t)cpdu.cbu_bridgeaddr[3]) << 16) | 921 (((uint64_t)cpdu.cbu_bridgeaddr[4]) << 8) | 922 (((uint64_t)cpdu.cbu_bridgeaddr[5]) << 0); 923 924 cu.cu_root_path_cost = ntohl(cpdu.cbu_rootpathcost); 925 cu.cu_message_age = ntohs(cpdu.cbu_messageage); 926 cu.cu_max_age = ntohs(cpdu.cbu_maxage); 927 cu.cu_hello_time = ntohs(cpdu.cbu_hellotime); 928 cu.cu_forward_delay = ntohs(cpdu.cbu_forwarddelay); 929 cu.cu_port_id = ntohs(cpdu.cbu_portid); 930 cu.cu_message_type = cpdu.cbu_bpdutype; 931 cu.cu_topology_change_acknowledgment = 932 (cpdu.cbu_flags & BSTP_FLAG_TCA) ? 1 : 0; 933 cu.cu_topology_change = 934 (cpdu.cbu_flags & BSTP_FLAG_TC) ? 1 : 0; 935 bstp_received_config_bpdu(sc, bif, &cu); 936 break; 937 default: 938 goto out; 939 } 940 out: 941 if (m) 942 m_freem(m); 943 } 944 945 static void 946 bstp_received_config_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif, 947 struct bstp_config_unit *cu) 948 { 949 int iamroot; 950 951 iamroot = bstp_root_bridge(sc); 952 953 if (bif->bif_state != BSTP_IFSTATE_DISABLED) { 954 /* 955 * Record information from peer. The peer_cost field 956 * does not include the local bif->bif_path_cost, it will 957 * be added in as needed (since it can be modified manually 958 * this way we don't have to worry about fixups). 959 */ 960 bif->bif_peer_root = cu->cu_rootid; 961 bif->bif_peer_cost = cu->cu_root_path_cost; 962 bif->bif_peer_bridge = cu->cu_bridge_id; 963 bif->bif_peer_port = cu->cu_port_id; 964 965 if (bstp_supersedes_port_info(sc, bif)) { 966 bstp_record_config_information(sc, bif, cu); 967 bstp_configuration_update(sc); 968 bstp_port_state_selection(sc); 969 970 /* 971 * If our bridge loses its root status (?) 972 * 973 * Hello's (unsolicited CFG packets) are generated 974 * every hello period of LINK1 is set, otherwise 975 * we are no longer the root bridge and must stop 976 * generating unsolicited CFG packets. 977 */ 978 if (iamroot && bstp_root_bridge(sc) == 0) { 979 if ((sc->sc_ifp->if_flags & IFF_LINK1) == 0) 980 bstp_timer_stop(&sc->sc_hello_timer); 981 982 if (sc->sc_topology_change_detected) { 983 bstp_timer_stop( 984 &sc->sc_topology_change_timer); 985 bstp_transmit_tcn(sc); 986 bstp_timer_start(&sc->sc_tcn_timer, 0); 987 } 988 } 989 990 if (sc->sc_root_port && 991 bif->bif_info == sc->sc_root_port->bif_info) { 992 bstp_record_config_timeout_values(sc, cu); 993 bstp_config_bpdu_generation(sc); 994 995 if (cu->cu_topology_change_acknowledgment) 996 bstp_topology_change_acknowledged(sc); 997 } 998 } else if (bif->bif_flags & IFBIF_DESIGNATED) { 999 /* 1000 * Update designated ports (aged out peers or 1001 * the port closest to the root) at a faster pace. 1002 * 1003 * Clear our designated flag if we aren't marked 1004 * as the root port. 1005 */ 1006 bstp_transmit_config(sc, bif); 1007 if ((bif->bif_flags & IFBIF_ROOT) == 0) { 1008 bif->bif_flags &= ~IFBIF_DESIGNATED; 1009 bstp_configuration_update(sc); 1010 bstp_port_state_selection(sc); 1011 } 1012 } 1013 } 1014 } 1015 1016 static void 1017 bstp_received_tcn_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif, 1018 struct bstp_tcn_unit *tcn) 1019 { 1020 if (bif->bif_state != BSTP_IFSTATE_DISABLED && 1021 (bif->bif_flags & IFBIF_DESIGNATED)) { 1022 bstp_topology_change_detection(sc); 1023 bstp_acknowledge_topology_change(sc, bif); 1024 } 1025 } 1026 1027 /* 1028 * link1 forces continuous hello's (the bridge interface must be cycled 1029 * to start them up), so keep the timer hot if that is the case, otherwise 1030 * only send HELLO's if we are the root. 1031 */ 1032 static void 1033 bstp_hello_timer_expiry(struct bridge_softc *sc) 1034 { 1035 bstp_config_bpdu_generation(sc); 1036 1037 if ((sc->sc_ifp->if_flags & IFF_LINK1) || bstp_root_bridge(sc)) 1038 bstp_timer_start(&sc->sc_hello_timer, 0); 1039 } 1040 1041 static void 1042 bstp_message_age_timer_expiry(struct bridge_softc *sc, 1043 struct bridge_iflist *bif) 1044 { 1045 int iamroot; 1046 1047 iamroot = bstp_root_bridge(sc); 1048 bstp_clear_peer_info(sc, bif); 1049 bstp_configuration_update(sc); 1050 bstp_port_state_selection(sc); 1051 1052 /* 1053 * If we've become the root and were not the root before 1054 * we have some cleanup to do. This also occurs if we 1055 * wind up being completely isolated. 1056 */ 1057 if (iamroot == 0 && bstp_root_bridge(sc)) { 1058 sc->sc_max_age = sc->sc_bridge_max_age; 1059 sc->sc_hello_time = sc->sc_bridge_hello_time; 1060 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 1061 1062 bstp_topology_change_detection(sc); 1063 bstp_timer_stop(&sc->sc_tcn_timer); 1064 bstp_config_bpdu_generation(sc); 1065 bstp_timer_start(&sc->sc_hello_timer, 0); 1066 } 1067 } 1068 1069 static void 1070 bstp_forward_delay_timer_expiry(struct bridge_softc *sc, 1071 struct bridge_iflist *bif) 1072 { 1073 if (bif->bif_state == BSTP_IFSTATE_LISTENING) { 1074 bstp_set_port_state(bif, BSTP_IFSTATE_LEARNING); 1075 bstp_timer_start(&bif->bif_forward_delay_timer, 0); 1076 } else if (bif->bif_state == BSTP_IFSTATE_LEARNING) { 1077 bstp_set_port_state(bif, BSTP_IFSTATE_FORWARDING); 1078 if (sc->sc_designated_bridge == sc->sc_bridge_id && 1079 bif->bif_change_detection_enabled) { 1080 bstp_topology_change_detection(sc); 1081 } 1082 bstp_configuration_update(sc); 1083 bstp_port_state_selection(sc); 1084 if (sc->sc_ifp->if_flags & IFF_LINK2) 1085 bstp_adjust_bonded_states(sc, bif); 1086 } 1087 } 1088 1089 static void 1090 bstp_tcn_timer_expiry(struct bridge_softc *sc) 1091 { 1092 bstp_transmit_tcn(sc); 1093 bstp_timer_start(&sc->sc_tcn_timer, 0); 1094 } 1095 1096 static void 1097 bstp_topology_change_timer_expiry(struct bridge_softc *sc) 1098 { 1099 sc->sc_topology_change_detected = 0; 1100 sc->sc_topology_change = 0; 1101 } 1102 1103 static void 1104 bstp_hold_timer_expiry(struct bridge_softc *sc, struct bridge_iflist *bif) 1105 { 1106 if (bif->bif_config_pending) 1107 bstp_transmit_config(sc, bif); 1108 } 1109 1110 /* 1111 * If no traffic received directly on this port for the specified 1112 * period with link1 set we go into a special blocking mode to 1113 * fail-over traffic to another port. 1114 */ 1115 static void 1116 bstp_link1_timer_expiry(struct bridge_softc *sc, struct bridge_iflist *bif) 1117 { 1118 if (sc->sc_ifp->if_flags & IFF_LINK1) 1119 bstp_make_l1blocking(sc, bif); 1120 } 1121 1122 static int 1123 bstp_addr_cmp(const uint8_t *a, const uint8_t *b) 1124 { 1125 int i, d; 1126 1127 for (i = 0, d = 0; i < ETHER_ADDR_LEN && d == 0; i++) { 1128 d = ((int)a[i]) - ((int)b[i]); 1129 } 1130 1131 return (d); 1132 } 1133 1134 void 1135 bstp_initialization(struct bridge_softc *sc) 1136 { 1137 struct bridge_iflist *bif, *mif, *nbif; 1138 u_char *e_addr; 1139 1140 KKASSERT(&curthread->td_msgport == BRIDGE_CFGPORT); 1141 1142 /* 1143 * Figure out our bridge ID, use the lowest-valued MAC. 1144 * Include the bridge's own random MAC in the calculation. 1145 */ 1146 mif = NULL; 1147 1148 TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) { 1149 if ((bif->bif_flags & IFBIF_STP) == 0) 1150 continue; 1151 if (bif->bif_ifp->if_type != IFT_ETHER) 1152 continue; 1153 if (mif == NULL) { 1154 mif = bif; 1155 continue; 1156 } 1157 1158 bif->bif_port_id = (bif->bif_priority << 8) | 1159 (bif->bif_ifp->if_index & 0xff); 1160 if (bstp_addr_cmp(IF_LLADDR(bif->bif_ifp), 1161 IF_LLADDR(mif->bif_ifp)) < 0) { 1162 mif = bif; 1163 continue; 1164 } 1165 } 1166 if (mif == NULL) { 1167 bstp_stop(sc); 1168 return; 1169 } 1170 1171 if (bstp_addr_cmp(IF_LLADDR(sc->sc_ifp), IF_LLADDR(mif->bif_ifp)) < 0) 1172 e_addr = IF_LLADDR(sc->sc_ifp); 1173 else 1174 e_addr = IF_LLADDR(mif->bif_ifp); 1175 1176 sc->sc_bridge_id = 1177 (((uint64_t)sc->sc_bridge_priority) << 48) | 1178 (((uint64_t)e_addr[0]) << 40) | 1179 (((uint64_t)e_addr[1]) << 32) | 1180 (((uint64_t)e_addr[2]) << 24) | 1181 (((uint64_t)e_addr[3]) << 16) | 1182 (((uint64_t)e_addr[4]) << 8) | 1183 (((uint64_t)e_addr[5])); 1184 1185 /* 1186 * Remainder of setup. 1187 */ 1188 1189 sc->sc_designated_root = sc->sc_bridge_id; 1190 sc->sc_designated_cost = 0; 1191 sc->sc_root_port = NULL; 1192 1193 sc->sc_max_age = sc->sc_bridge_max_age; 1194 sc->sc_hello_time = sc->sc_bridge_hello_time; 1195 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 1196 sc->sc_topology_change_detected = 0; 1197 sc->sc_topology_change = 0; 1198 bstp_timer_stop(&sc->sc_tcn_timer); 1199 bstp_timer_stop(&sc->sc_topology_change_timer); 1200 1201 if (callout_pending(&sc->sc_bstpcallout) == 0) 1202 callout_reset(&sc->sc_bstpcallout, hz, 1203 bstp_tick, sc); 1204 1205 TAILQ_FOREACH_MUTABLE(bif, &sc->sc_iflists[mycpuid], bif_next, nbif) { 1206 if (sc->sc_ifp->if_flags & IFF_LINK1) 1207 bstp_timer_start(&bif->bif_link1_timer, 0); 1208 if (bif->bif_flags & IFBIF_STP) 1209 bstp_ifupdstatus(sc, bif); 1210 else 1211 bstp_disable_port(sc, bif); 1212 1213 if (nbif != NULL && !nbif->bif_onlist) { 1214 KKASSERT(bif->bif_onlist); 1215 nbif = TAILQ_NEXT(bif, bif_next); 1216 } 1217 } 1218 1219 bstp_port_state_selection(sc); 1220 bstp_config_bpdu_generation(sc); 1221 bstp_timer_start(&sc->sc_hello_timer, 0); 1222 } 1223 1224 void 1225 bstp_stop(struct bridge_softc *sc) 1226 { 1227 struct bridge_iflist *bif; 1228 1229 KKASSERT(&curthread->td_msgport == BRIDGE_CFGPORT); 1230 1231 TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) { 1232 bstp_set_port_state(bif, BSTP_IFSTATE_DISABLED); 1233 bstp_timer_stop(&bif->bif_hold_timer); 1234 bstp_timer_stop(&bif->bif_message_age_timer); 1235 bstp_timer_stop(&bif->bif_forward_delay_timer); 1236 bstp_timer_stop(&bif->bif_link1_timer); 1237 } 1238 1239 callout_stop(&sc->sc_bstpcallout); 1240 1241 bstp_timer_stop(&sc->sc_topology_change_timer); 1242 bstp_timer_stop(&sc->sc_tcn_timer); 1243 bstp_timer_stop(&sc->sc_hello_timer); 1244 1245 crit_enter(); 1246 lwkt_dropmsg(&sc->sc_bstptimemsg.lmsg); 1247 crit_exit(); 1248 } 1249 1250 /* 1251 * [re]initialize a port. The port is initialized to a L1BLOCKING state 1252 * or a BLOCKING state. When link ping/pong is enabled (LINK1) we start 1253 * out in the L1BLOCKING state to prevent flapping from blowing up the 1254 * state of the other ports. 1255 * 1256 * Either way the first config packet received will knock the port into 1257 * the LISTENING state. 1258 */ 1259 static void 1260 bstp_initialize_port(struct bridge_softc *sc, struct bridge_iflist *bif) 1261 { 1262 int needs_adjust = (bif->bif_state == BSTP_IFSTATE_FORWARDING || 1263 bif->bif_state == BSTP_IFSTATE_BLOCKING || 1264 bif->bif_state == BSTP_IFSTATE_BONDED); 1265 1266 if (sc->sc_ifp->if_flags & IFF_LINK1) 1267 bstp_set_port_state(bif, BSTP_IFSTATE_L1BLOCKING); 1268 else 1269 bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING); 1270 bstp_clear_peer_info(sc, bif); 1271 bif->bif_topology_change_acknowledge = 0; 1272 bif->bif_config_pending = 0; 1273 bif->bif_change_detection_enabled = 1; 1274 bstp_timer_stop(&bif->bif_message_age_timer); 1275 bstp_timer_stop(&bif->bif_forward_delay_timer); 1276 bstp_timer_stop(&bif->bif_hold_timer); 1277 bstp_timer_stop(&bif->bif_link1_timer); 1278 if (needs_adjust && (sc->sc_ifp->if_flags & IFF_LINK2)) 1279 bstp_adjust_bonded_states(sc, bif); 1280 } 1281 1282 /* 1283 * When enabling a port that was previously disabled no configuration 1284 * update occurs, otherwise down/up or running/not-running flapping 1285 * (e.g. by openvpn on a TAP interface) will blow up the other ports. 1286 */ 1287 static void 1288 bstp_enable_port(struct bridge_softc *sc, struct bridge_iflist *bif) 1289 { 1290 int was_disabled = (bif->bif_state == BSTP_IFSTATE_DISABLED || 1291 bif->bif_state == BSTP_IFSTATE_L1BLOCKING); 1292 1293 bstp_initialize_port(sc, bif); 1294 if (sc->sc_ifp->if_flags & IFF_LINK1) 1295 bstp_timer_start(&bif->bif_link1_timer, 0); 1296 if (was_disabled == 0) { 1297 bstp_configuration_update(sc); 1298 bstp_port_state_selection(sc); 1299 } 1300 bstp_adjust_bonded_states(sc, bif); 1301 } 1302 1303 /* 1304 * When disabling a port that was previously in a non-forwarding or bonded 1305 * state no configuration update occurs, otherwise down/up or 1306 * running/not-running flapping (e.g. by openvpn on a TAP interface) will 1307 * blow up the other ports. 1308 */ 1309 static void 1310 bstp_disable_port(struct bridge_softc *sc, struct bridge_iflist *bif) 1311 { 1312 int was_forwarding = (bif->bif_state == BSTP_IFSTATE_FORWARDING); 1313 int was_bonded = (bif->bif_state == BSTP_IFSTATE_BONDED); 1314 int iamroot; 1315 1316 iamroot = bstp_root_bridge(sc); 1317 1318 bstp_clear_peer_info(sc, bif); 1319 bstp_set_port_state(bif, BSTP_IFSTATE_DISABLED); 1320 bif->bif_topology_change_acknowledge = 0; 1321 bif->bif_config_pending = 0; 1322 bstp_timer_stop(&bif->bif_message_age_timer); 1323 bstp_timer_stop(&bif->bif_forward_delay_timer); 1324 bstp_timer_stop(&bif->bif_link1_timer); 1325 if (was_forwarding || was_bonded) { 1326 bstp_configuration_update(sc); 1327 bstp_port_state_selection(sc); 1328 } 1329 bridge_rtdelete(sc, bif->bif_ifp, IFBF_FLUSHDYN); 1330 if (was_forwarding && (sc->sc_ifp->if_flags & IFF_LINK2)) 1331 bstp_adjust_bonded_states(sc, bif); 1332 1333 if (iamroot == 0 && bstp_root_bridge(sc)) { 1334 sc->sc_max_age = sc->sc_bridge_max_age; 1335 sc->sc_hello_time = sc->sc_bridge_hello_time; 1336 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 1337 1338 bstp_topology_change_detection(sc); 1339 bstp_timer_stop(&sc->sc_tcn_timer); 1340 bstp_config_bpdu_generation(sc); 1341 bstp_timer_start(&sc->sc_hello_timer, 0); 1342 } 1343 } 1344 1345 void 1346 bstp_linkstate(struct ifnet *ifp, int state) 1347 { 1348 struct bridge_softc *sc; 1349 struct bridge_iflist *bif; 1350 1351 sc = ifp->if_bridge; 1352 ifnet_serialize_all(sc->sc_ifp); 1353 1354 /* 1355 * bstp_ifupdstatus() may block, but it is the last 1356 * operation of the member iface iteration, so we 1357 * don't need to use LIST_FOREACH_MUTABLE()+bif_onlist 1358 * check here. 1359 */ 1360 TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) { 1361 if ((bif->bif_flags & IFBIF_STP) == 0) 1362 continue; 1363 1364 if (bif->bif_ifp == ifp) { 1365 bstp_ifupdstatus(sc, bif); 1366 break; 1367 } 1368 } 1369 ifnet_deserialize_all(sc->sc_ifp); 1370 } 1371 1372 static void 1373 bstp_ifupdstatus(struct bridge_softc *sc, struct bridge_iflist *bif) 1374 { 1375 struct ifnet *ifp = bif->bif_ifp; 1376 struct ifmediareq ifmr; 1377 int error = 0; 1378 1379 bzero((char *)&ifmr, sizeof(ifmr)); 1380 ifnet_serialize_all(ifp); 1381 error = (*ifp->if_ioctl)(ifp, SIOCGIFMEDIA, (caddr_t)&ifmr, NULL); 1382 ifnet_deserialize_all(ifp); 1383 1384 if ((error == 0) && (ifp->if_flags & IFF_UP)) { 1385 if (ifmr.ifm_status & IFM_ACTIVE) { 1386 if (bif->bif_state == BSTP_IFSTATE_DISABLED) 1387 bstp_enable_port(sc, bif); 1388 1389 } else { 1390 if (bif->bif_state != BSTP_IFSTATE_DISABLED) 1391 bstp_disable_port(sc, bif); 1392 } 1393 return; 1394 } 1395 1396 if (bif->bif_state != BSTP_IFSTATE_DISABLED) 1397 bstp_disable_port(sc, bif); 1398 } 1399 1400 static void 1401 bstp_tick(void *arg) 1402 { 1403 struct bridge_softc *sc = arg; 1404 struct lwkt_msg *lmsg; 1405 1406 KKASSERT(mycpuid == BRIDGE_CFGCPU); 1407 1408 crit_enter(); 1409 1410 if (callout_pending(&sc->sc_bstpcallout) || 1411 !callout_active(&sc->sc_bstpcallout)) { 1412 crit_exit(); 1413 return; 1414 } 1415 callout_deactivate(&sc->sc_bstpcallout); 1416 1417 lmsg = &sc->sc_bstptimemsg.lmsg; 1418 KKASSERT(lmsg->ms_flags & MSGF_DONE); 1419 lwkt_sendmsg_oncpu(BRIDGE_CFGPORT, lmsg); 1420 1421 crit_exit(); 1422 } 1423 1424 void 1425 bstp_tick_handler(netmsg_t msg) 1426 { 1427 struct bridge_softc *sc = msg->lmsg.u.ms_resultp; 1428 struct bridge_iflist *bif; 1429 1430 KKASSERT(&curthread->td_msgport == BRIDGE_CFGPORT); 1431 crit_enter(); 1432 /* Reply ASAP */ 1433 lwkt_replymsg(&msg->lmsg, 0); 1434 crit_exit(); 1435 1436 ifnet_serialize_all(sc->sc_ifp); 1437 1438 /* 1439 * NOTE: 1440 * We don't need to worry that member iface is ripped 1441 * from the per-cpu list during the blocking operation 1442 * in the loop body, since deletion is serialized by 1443 * BRIDGE_CFGPORT 1444 */ 1445 1446 TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) { 1447 if ((bif->bif_flags & IFBIF_STP) == 0) 1448 continue; 1449 /* 1450 * XXX This can cause a lag in "link does away" 1451 * XXX and "spanning tree gets updated". We need 1452 * XXX come sort of callback from the link state 1453 * XXX update code to kick spanning tree. 1454 * XXX --thorpej@NetBSD.org 1455 */ 1456 bstp_ifupdstatus(sc, bif); 1457 } 1458 1459 if (bstp_timer_expired(&sc->sc_hello_timer, sc->sc_hello_time)) 1460 bstp_hello_timer_expiry(sc); 1461 1462 if (bstp_timer_expired(&sc->sc_tcn_timer, sc->sc_bridge_hello_time)) 1463 bstp_tcn_timer_expiry(sc); 1464 1465 if (bstp_timer_expired(&sc->sc_topology_change_timer, 1466 sc->sc_topology_change_time)) 1467 bstp_topology_change_timer_expiry(sc); 1468 1469 TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) { 1470 if ((bif->bif_flags & IFBIF_STP) == 0) 1471 continue; 1472 if (bstp_timer_expired(&bif->bif_message_age_timer, 1473 sc->sc_max_age)) 1474 bstp_message_age_timer_expiry(sc, bif); 1475 } 1476 1477 TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) { 1478 if ((bif->bif_flags & IFBIF_STP) == 0) 1479 continue; 1480 if (bstp_timer_expired(&bif->bif_forward_delay_timer, 1481 sc->sc_forward_delay)) 1482 bstp_forward_delay_timer_expiry(sc, bif); 1483 1484 if (bstp_timer_expired(&bif->bif_hold_timer, 1485 sc->sc_hold_time)) 1486 bstp_hold_timer_expiry(sc, bif); 1487 1488 if (bstp_timer_expired(&bif->bif_link1_timer, 1489 sc->sc_hello_time * 10)) 1490 bstp_link1_timer_expiry(sc, bif); 1491 } 1492 1493 if (sc->sc_ifp->if_flags & IFF_RUNNING) 1494 callout_reset(&sc->sc_bstpcallout, hz, bstp_tick, sc); 1495 1496 ifnet_deserialize_all(sc->sc_ifp); 1497 } 1498 1499 static void 1500 bstp_timer_start(struct bridge_timer *t, uint16_t v) 1501 { 1502 t->value = v; 1503 t->active = 1; 1504 } 1505 1506 static void 1507 bstp_timer_stop(struct bridge_timer *t) 1508 { 1509 t->value = 0; 1510 t->active = 0; 1511 } 1512 1513 static int 1514 bstp_timer_expired(struct bridge_timer *t, uint16_t v) 1515 { 1516 if (t->active == 0) 1517 return (0); 1518 t->value += BSTP_TICK_VAL; 1519 if (t->value >= v) { 1520 bstp_timer_stop(t); 1521 return (1); 1522 } 1523 return (0); 1524 1525 } 1526