1 /* $NetBSD: bridgestp.c,v 1.27 2024/07/05 04:31:53 rin Exp $ */ 2 3 /* 4 * Copyright (c) 2000 Jason L. Wright (jason@thought.net) 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. All advertising materials mentioning features or use of this software 16 * must display the following acknowledgement: 17 * This product includes software developed by Jason L. Wright 18 * 4. The name of the author may not be used to endorse or promote products 19 * derived from this software without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 22 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 23 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 24 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, 25 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 26 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 27 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 29 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 30 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 31 * POSSIBILITY OF SUCH DAMAGE. 32 * 33 * OpenBSD: bridgestp.c,v 1.5 2001/03/22 03:48:29 jason 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/cdefs.h> 43 __KERNEL_RCSID(0, "$NetBSD: bridgestp.c,v 1.27 2024/07/05 04:31:53 rin Exp $"); 44 45 #include <sys/param.h> 46 #include <sys/systm.h> 47 #include <sys/mbuf.h> 48 #include <sys/socket.h> 49 #include <sys/ioctl.h> 50 #include <sys/device.h> 51 #include <sys/kernel.h> 52 #include <sys/callout.h> 53 54 #include <net/if.h> 55 #include <net/if_dl.h> 56 #include <net/if_types.h> 57 #include <net/if_llc.h> 58 59 #include <net/if_ether.h> 60 #include <net/if_bridgevar.h> 61 62 /* BPDU message types */ 63 #define BSTP_MSGTYPE_CFG 0x00 /* Configuration */ 64 #define BSTP_MSGTYPE_TCN 0x80 /* Topology chg notification */ 65 66 /* BPDU flags */ 67 #define BSTP_FLAG_TC 0x01 /* Topology change */ 68 #define BSTP_FLAG_TCA 0x80 /* Topology change ack */ 69 70 #define BSTP_MESSAGE_AGE_INCR (1 * 256) /* in 256ths of a second */ 71 #define BSTP_TICK_VAL (1 * 256) /* in 256ths of a second */ 72 73 /* 74 * Because BPDU's do not make nicely aligned structures, two different 75 * declarations are used: bstp_?bpdu (wire representation, packed) and 76 * bstp_*_unit (internal, nicely aligned version). 77 */ 78 79 /* configuration bridge protocol data unit */ 80 struct bstp_cbpdu { 81 uint8_t cbu_dsap; /* LLC: destination sap */ 82 uint8_t cbu_ssap; /* LLC: source sap */ 83 uint8_t cbu_ctl; /* LLC: control */ 84 uint16_t cbu_protoid; /* protocol id */ 85 uint8_t cbu_protover; /* protocol version */ 86 uint8_t cbu_bpdutype; /* message type */ 87 uint8_t cbu_flags; /* flags (below) */ 88 89 /* root id */ 90 uint16_t cbu_rootpri; /* root priority */ 91 uint8_t cbu_rootaddr[6]; /* root address */ 92 93 uint32_t cbu_rootpathcost; /* root path cost */ 94 95 /* bridge id */ 96 uint16_t cbu_bridgepri; /* bridge priority */ 97 uint8_t cbu_bridgeaddr[6]; /* bridge address */ 98 99 uint16_t cbu_portid; /* port id */ 100 uint16_t cbu_messageage; /* current message age */ 101 uint16_t cbu_maxage; /* maximum age */ 102 uint16_t cbu_hellotime; /* hello time */ 103 uint16_t cbu_forwarddelay; /* forwarding delay */ 104 } __packed; 105 106 /* topology change notification bridge protocol data unit */ 107 struct bstp_tbpdu { 108 uint8_t tbu_dsap; /* LLC: destination sap */ 109 uint8_t tbu_ssap; /* LLC: source sap */ 110 uint8_t tbu_ctl; /* LLC: control */ 111 uint16_t tbu_protoid; /* protocol id */ 112 uint8_t tbu_protover; /* protocol version */ 113 uint8_t tbu_bpdutype; /* message type */ 114 } __packed; 115 116 const uint8_t bstp_etheraddr[] = { 0x01, 0x80, 0xc2, 0x00, 0x00, 0x00 }; 117 118 static void bstp_initialize_port(struct bridge_softc *, struct bridge_iflist *); 119 static void bstp_ifupdstatus(struct bridge_softc *, struct bridge_iflist *); 120 static void bstp_enable_port(struct bridge_softc *, struct bridge_iflist *); 121 static void bstp_disable_port(struct bridge_softc *, struct bridge_iflist *); 122 static int bstp_root_bridge(struct bridge_softc *sc); 123 static int bstp_supersedes_port_info(struct bridge_softc *, 124 struct bridge_iflist *, 125 struct bstp_config_unit *); 126 static int bstp_designated_port(struct bridge_softc *, struct bridge_iflist *); 127 static int bstp_designated_for_some_port(struct bridge_softc *); 128 static void bstp_transmit_config(struct bridge_softc *, struct bridge_iflist *); 129 static void bstp_transmit_tcn(struct bridge_softc *); 130 static void bstp_received_config_bpdu(struct bridge_softc *, 131 struct bridge_iflist *, 132 struct bstp_config_unit *); 133 static void bstp_received_tcn_bpdu(struct bridge_softc *, struct bridge_iflist *, 134 struct bstp_tcn_unit *); 135 static void bstp_record_config_information(struct bridge_softc *, 136 struct bridge_iflist *, 137 struct bstp_config_unit *); 138 static void bstp_record_config_timeout_values(struct bridge_softc *, 139 struct bstp_config_unit *); 140 static void bstp_config_bpdu_generation(struct bridge_softc *); 141 static void bstp_send_config_bpdu(struct bridge_softc *, struct bridge_iflist *, 142 struct bstp_config_unit *); 143 static void bstp_configuration_update(struct bridge_softc *); 144 static void bstp_root_selection(struct bridge_softc *); 145 static void bstp_designated_port_selection(struct bridge_softc *); 146 static void bstp_become_designated_port(struct bridge_softc *, 147 struct bridge_iflist *); 148 static void bstp_port_state_selection(struct bridge_softc *); 149 static void bstp_make_forwarding(struct bridge_softc *, struct bridge_iflist *); 150 static void bstp_make_blocking(struct bridge_softc *, struct bridge_iflist *); 151 static void bstp_set_port_state(struct bridge_iflist *, uint8_t); 152 #if notused 153 static void bstp_set_bridge_priority(struct bridge_softc *, uint64_t); 154 static void bstp_set_port_priority(struct bridge_softc *, struct bridge_iflist *, 155 uint16_t); 156 static void bstp_set_path_cost(struct bridge_softc *, struct bridge_iflist *, 157 uint32_t); 158 #endif 159 static void bstp_topology_change_detection(struct bridge_softc *); 160 static void bstp_topology_change_acknowledged(struct bridge_softc *); 161 static void bstp_acknowledge_topology_change(struct bridge_softc *, 162 struct bridge_iflist *); 163 164 static void bstp_tick(void *); 165 static void bstp_timer_start(struct bridge_timer *, uint16_t); 166 static void bstp_timer_stop(struct bridge_timer *); 167 static int bstp_timer_expired(struct bridge_timer *, uint16_t); 168 169 static void bstp_hold_timer_expiry(struct bridge_softc *, struct bridge_iflist *); 170 static void bstp_message_age_timer_expiry(struct bridge_softc *, 171 struct bridge_iflist *); 172 static void bstp_forward_delay_timer_expiry(struct bridge_softc *, 173 struct bridge_iflist *); 174 static void bstp_topology_change_timer_expiry(struct bridge_softc *); 175 static void bstp_tcn_timer_expiry(struct bridge_softc *); 176 static void bstp_hello_timer_expiry(struct bridge_softc *); 177 178 static void 179 bstp_transmit_config(struct bridge_softc *sc, struct bridge_iflist *bif) 180 { 181 if (bif->bif_hold_timer.active) { 182 bif->bif_config_pending = 1; 183 return; 184 } 185 186 bif->bif_config_bpdu.cu_message_type = BSTP_MSGTYPE_CFG; 187 bif->bif_config_bpdu.cu_rootid = sc->sc_designated_root; 188 bif->bif_config_bpdu.cu_root_path_cost = sc->sc_root_path_cost; 189 bif->bif_config_bpdu.cu_bridge_id = sc->sc_bridge_id; 190 bif->bif_config_bpdu.cu_port_id = bif->bif_port_id; 191 192 if (bstp_root_bridge(sc)) 193 bif->bif_config_bpdu.cu_message_age = 0; 194 else 195 bif->bif_config_bpdu.cu_message_age = 196 sc->sc_root_port->bif_message_age_timer.value + 197 BSTP_MESSAGE_AGE_INCR; 198 199 bif->bif_config_bpdu.cu_max_age = sc->sc_max_age; 200 bif->bif_config_bpdu.cu_hello_time = sc->sc_hello_time; 201 bif->bif_config_bpdu.cu_forward_delay = sc->sc_forward_delay; 202 bif->bif_config_bpdu.cu_topology_change_acknowledgment 203 = bif->bif_topology_change_acknowledge; 204 bif->bif_config_bpdu.cu_topology_change = sc->sc_topology_change; 205 206 if (bif->bif_config_bpdu.cu_message_age < sc->sc_max_age) { 207 bif->bif_topology_change_acknowledge = 0; 208 bif->bif_config_pending = 0; 209 bstp_send_config_bpdu(sc, bif, &bif->bif_config_bpdu); 210 bstp_timer_start(&bif->bif_hold_timer, 0); 211 } 212 } 213 214 static void 215 bstp_send_config_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif, 216 struct bstp_config_unit *cu) 217 { 218 struct ifnet *ifp; 219 struct mbuf *m; 220 struct ether_header *eh; 221 struct bstp_cbpdu bpdu; 222 223 KASSERT(BRIDGE_LOCKED(sc)); 224 225 ifp = bif->bif_ifp; 226 227 if ((ifp->if_flags & IFF_RUNNING) == 0) 228 return; 229 230 MGETHDR(m, M_DONTWAIT, MT_DATA); 231 if (m == NULL) 232 return; 233 234 eh = mtod(m, struct ether_header *); 235 236 m_set_rcvif(m, ifp); 237 m->m_pkthdr.len = sizeof(*eh) + sizeof(bpdu); 238 m->m_len = m->m_pkthdr.len; 239 240 bpdu.cbu_ssap = bpdu.cbu_dsap = LLC_8021D_LSAP; 241 bpdu.cbu_ctl = LLC_UI; 242 bpdu.cbu_protoid = htons(0); 243 bpdu.cbu_protover = 0; 244 bpdu.cbu_bpdutype = cu->cu_message_type; 245 bpdu.cbu_flags = (cu->cu_topology_change ? BSTP_FLAG_TC : 0) | 246 (cu->cu_topology_change_acknowledgment ? BSTP_FLAG_TCA : 0); 247 248 bpdu.cbu_rootpri = htons(cu->cu_rootid >> 48); 249 bpdu.cbu_rootaddr[0] = cu->cu_rootid >> 40; 250 bpdu.cbu_rootaddr[1] = cu->cu_rootid >> 32; 251 bpdu.cbu_rootaddr[2] = cu->cu_rootid >> 24; 252 bpdu.cbu_rootaddr[3] = cu->cu_rootid >> 16; 253 bpdu.cbu_rootaddr[4] = cu->cu_rootid >> 8; 254 bpdu.cbu_rootaddr[5] = cu->cu_rootid >> 0; 255 256 bpdu.cbu_rootpathcost = htonl(cu->cu_root_path_cost); 257 258 bpdu.cbu_bridgepri = htons(cu->cu_rootid >> 48); 259 bpdu.cbu_bridgeaddr[0] = cu->cu_rootid >> 40; 260 bpdu.cbu_bridgeaddr[1] = cu->cu_rootid >> 32; 261 bpdu.cbu_bridgeaddr[2] = cu->cu_rootid >> 24; 262 bpdu.cbu_bridgeaddr[3] = cu->cu_rootid >> 16; 263 bpdu.cbu_bridgeaddr[4] = cu->cu_rootid >> 8; 264 bpdu.cbu_bridgeaddr[5] = cu->cu_rootid >> 0; 265 266 bpdu.cbu_portid = htons(cu->cu_port_id); 267 bpdu.cbu_messageage = htons(cu->cu_message_age); 268 bpdu.cbu_maxage = htons(cu->cu_max_age); 269 bpdu.cbu_hellotime = htons(cu->cu_hello_time); 270 bpdu.cbu_forwarddelay = htons(cu->cu_forward_delay); 271 272 memcpy(eh->ether_shost, CLLADDR(ifp->if_sadl), ETHER_ADDR_LEN); 273 memcpy(eh->ether_dhost, bstp_etheraddr, ETHER_ADDR_LEN); 274 eh->ether_type = htons(sizeof(bpdu)); 275 276 memcpy(mtod(m, char *) + sizeof(*eh), &bpdu, sizeof(bpdu)); 277 278 BRIDGE_UNLOCK(sc); 279 bridge_enqueue(sc, ifp, m, 0); 280 BRIDGE_LOCK(sc); 281 } 282 283 static int 284 bstp_root_bridge(struct bridge_softc *sc) 285 { 286 return (sc->sc_designated_root == sc->sc_bridge_id); 287 } 288 289 static int 290 bstp_supersedes_port_info(struct bridge_softc *sc, struct bridge_iflist *bif, 291 struct bstp_config_unit *cu) 292 { 293 if (cu->cu_rootid < bif->bif_designated_root) 294 return (1); 295 if (cu->cu_rootid > bif->bif_designated_root) 296 return (0); 297 298 if (cu->cu_root_path_cost < bif->bif_designated_cost) 299 return (1); 300 if (cu->cu_root_path_cost > bif->bif_designated_cost) 301 return (0); 302 303 if (cu->cu_bridge_id < bif->bif_designated_bridge) 304 return (1); 305 if (cu->cu_bridge_id > bif->bif_designated_bridge) 306 return (0); 307 308 if (sc->sc_bridge_id != cu->cu_bridge_id) 309 return (1); 310 if (cu->cu_port_id <= bif->bif_designated_port) 311 return (1); 312 return (0); 313 } 314 315 static void 316 bstp_record_config_information(struct bridge_softc *sc, 317 struct bridge_iflist *bif, struct bstp_config_unit *cu) 318 { 319 bif->bif_designated_root = cu->cu_rootid; 320 bif->bif_designated_cost = cu->cu_root_path_cost; 321 bif->bif_designated_bridge = cu->cu_bridge_id; 322 bif->bif_designated_port = cu->cu_port_id; 323 bstp_timer_start(&bif->bif_message_age_timer, cu->cu_message_age); 324 } 325 326 static void 327 bstp_record_config_timeout_values(struct bridge_softc *sc, 328 struct bstp_config_unit *config) 329 { 330 sc->sc_max_age = config->cu_max_age; 331 sc->sc_hello_time = config->cu_hello_time; 332 sc->sc_forward_delay = config->cu_forward_delay; 333 sc->sc_topology_change = config->cu_topology_change; 334 } 335 336 static void 337 bstp_config_bpdu_generation(struct bridge_softc *sc) 338 { 339 struct bridge_iflist *bif; 340 341 BRIDGE_IFLIST_WRITER_FOREACH(bif, sc) { 342 if ((bif->bif_flags & IFBIF_STP) == 0) 343 continue; 344 if (bstp_designated_port(sc, bif) && 345 (bif->bif_state != BSTP_IFSTATE_DISABLED)) 346 bstp_transmit_config(sc, bif); 347 } 348 } 349 350 static int 351 bstp_designated_port(struct bridge_softc *sc, struct bridge_iflist *bif) 352 { 353 return ((bif->bif_designated_bridge == sc->sc_bridge_id) 354 && (bif->bif_designated_port == bif->bif_port_id)); 355 } 356 357 static void 358 bstp_transmit_tcn(struct bridge_softc *sc) 359 { 360 struct bstp_tbpdu bpdu; 361 struct bridge_iflist *bif = sc->sc_root_port; 362 struct ifnet *ifp; 363 struct ether_header *eh; 364 struct mbuf *m; 365 366 KASSERT(BRIDGE_LOCKED(sc)); 367 368 KASSERT(bif != NULL); 369 ifp = bif->bif_ifp; 370 if ((ifp->if_flags & IFF_RUNNING) == 0) 371 return; 372 373 MGETHDR(m, M_DONTWAIT, MT_DATA); 374 if (m == NULL) 375 return; 376 377 m_set_rcvif(m, ifp); 378 m->m_pkthdr.len = sizeof(*eh) + sizeof(bpdu); 379 m->m_len = m->m_pkthdr.len; 380 381 eh = mtod(m, struct ether_header *); 382 383 memcpy(eh->ether_shost, CLLADDR(ifp->if_sadl), ETHER_ADDR_LEN); 384 memcpy(eh->ether_dhost, bstp_etheraddr, ETHER_ADDR_LEN); 385 eh->ether_type = htons(sizeof(bpdu)); 386 387 bpdu.tbu_ssap = bpdu.tbu_dsap = LLC_8021D_LSAP; 388 bpdu.tbu_ctl = LLC_UI; 389 bpdu.tbu_protoid = 0; 390 bpdu.tbu_protover = 0; 391 bpdu.tbu_bpdutype = BSTP_MSGTYPE_TCN; 392 393 memcpy(mtod(m, char *) + sizeof(*eh), &bpdu, sizeof(bpdu)); 394 395 BRIDGE_UNLOCK(sc); 396 bridge_enqueue(sc, ifp, m, 0); 397 BRIDGE_LOCK(sc); 398 } 399 400 static void 401 bstp_configuration_update(struct bridge_softc *sc) 402 { 403 bstp_root_selection(sc); 404 bstp_designated_port_selection(sc); 405 } 406 407 static void 408 bstp_root_selection(struct bridge_softc *sc) 409 { 410 struct bridge_iflist *root_port = NULL, *bif; 411 412 BRIDGE_IFLIST_WRITER_FOREACH(bif, sc) { 413 if ((bif->bif_flags & IFBIF_STP) == 0) 414 continue; 415 if (bstp_designated_port(sc, bif)) 416 continue; 417 if (bif->bif_state == BSTP_IFSTATE_DISABLED) 418 continue; 419 if (bif->bif_designated_root >= sc->sc_bridge_id) 420 continue; 421 if (root_port == NULL) 422 goto set_port; 423 424 if (bif->bif_designated_root < root_port->bif_designated_root) 425 goto set_port; 426 if (bif->bif_designated_root > root_port->bif_designated_root) 427 continue; 428 429 if ((bif->bif_designated_cost + bif->bif_path_cost) < 430 (root_port->bif_designated_cost + root_port->bif_path_cost)) 431 goto set_port; 432 if ((bif->bif_designated_cost + bif->bif_path_cost) > 433 (root_port->bif_designated_cost + root_port->bif_path_cost)) 434 continue; 435 436 if (bif->bif_designated_bridge < 437 root_port->bif_designated_bridge) 438 goto set_port; 439 if (bif->bif_designated_bridge > 440 root_port->bif_designated_bridge) 441 continue; 442 443 if (bif->bif_designated_port < root_port->bif_designated_port) 444 goto set_port; 445 if (bif->bif_designated_port > root_port->bif_designated_port) 446 continue; 447 448 if (bif->bif_port_id >= root_port->bif_port_id) 449 continue; 450 set_port: 451 root_port = bif; 452 } 453 454 sc->sc_root_port = root_port; 455 if (root_port == NULL) { 456 sc->sc_designated_root = sc->sc_bridge_id; 457 sc->sc_root_path_cost = 0; 458 } else { 459 sc->sc_designated_root = root_port->bif_designated_root; 460 sc->sc_root_path_cost = root_port->bif_designated_cost + 461 root_port->bif_path_cost; 462 } 463 } 464 465 static void 466 bstp_designated_port_selection(struct bridge_softc *sc) 467 { 468 struct bridge_iflist *bif; 469 470 BRIDGE_IFLIST_WRITER_FOREACH(bif, sc) { 471 if ((bif->bif_flags & IFBIF_STP) == 0) 472 continue; 473 if (bstp_designated_port(sc, bif)) 474 goto designated; 475 if (bif->bif_designated_root != sc->sc_designated_root) 476 goto designated; 477 478 if (sc->sc_root_path_cost < bif->bif_designated_cost) 479 goto designated; 480 if (sc->sc_root_path_cost > bif->bif_designated_cost) 481 continue; 482 483 if (sc->sc_bridge_id < bif->bif_designated_bridge) 484 goto designated; 485 if (sc->sc_bridge_id > bif->bif_designated_bridge) 486 continue; 487 488 if (bif->bif_port_id > bif->bif_designated_port) 489 continue; 490 designated: 491 bstp_become_designated_port(sc, bif); 492 } 493 } 494 495 static void 496 bstp_become_designated_port(struct bridge_softc *sc, struct bridge_iflist *bif) 497 { 498 bif->bif_designated_root = sc->sc_designated_root; 499 bif->bif_designated_cost = sc->sc_root_path_cost; 500 bif->bif_designated_bridge = sc->sc_bridge_id; 501 bif->bif_designated_port = bif->bif_port_id; 502 } 503 504 static void 505 bstp_port_state_selection(struct bridge_softc *sc) 506 { 507 struct bridge_iflist *bif; 508 509 BRIDGE_IFLIST_WRITER_FOREACH(bif, sc) { 510 if ((bif->bif_flags & IFBIF_STP) == 0) 511 continue; 512 if (bif == sc->sc_root_port) { 513 bif->bif_config_pending = 0; 514 bif->bif_topology_change_acknowledge = 0; 515 bstp_make_forwarding(sc, bif); 516 } else if (bstp_designated_port(sc, bif)) { 517 bstp_timer_stop(&bif->bif_message_age_timer); 518 bstp_make_forwarding(sc, bif); 519 } else { 520 bif->bif_config_pending = 0; 521 bif->bif_topology_change_acknowledge = 0; 522 bstp_make_blocking(sc, bif); 523 } 524 } 525 } 526 527 static void 528 bstp_make_forwarding(struct bridge_softc *sc, 529 struct bridge_iflist *bif) 530 { 531 if (bif->bif_state == BSTP_IFSTATE_BLOCKING) { 532 bstp_set_port_state(bif, BSTP_IFSTATE_LISTENING); 533 bstp_timer_start(&bif->bif_forward_delay_timer, 0); 534 } 535 } 536 537 static void 538 bstp_make_blocking(struct bridge_softc *sc, struct bridge_iflist *bif) 539 { 540 if ((bif->bif_state != BSTP_IFSTATE_DISABLED) && 541 (bif->bif_state != BSTP_IFSTATE_BLOCKING)) { 542 if ((bif->bif_state == BSTP_IFSTATE_FORWARDING) || 543 (bif->bif_state == BSTP_IFSTATE_LEARNING)) { 544 if (bif->bif_change_detection_enabled) { 545 bstp_topology_change_detection(sc); 546 } 547 } 548 bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING); 549 bstp_timer_stop(&bif->bif_forward_delay_timer); 550 } 551 } 552 553 static void 554 bstp_set_port_state(struct bridge_iflist *bif, uint8_t state) 555 { 556 bif->bif_state = state; 557 } 558 559 static void 560 bstp_topology_change_detection(struct bridge_softc *sc) 561 { 562 if (bstp_root_bridge(sc)) { 563 sc->sc_topology_change = 1; 564 bstp_timer_start(&sc->sc_topology_change_timer, 0); 565 } else if (!sc->sc_topology_change_detected) { 566 bstp_transmit_tcn(sc); 567 bstp_timer_start(&sc->sc_tcn_timer, 0); 568 } 569 sc->sc_topology_change_detected = 1; 570 } 571 572 static void 573 bstp_topology_change_acknowledged(struct bridge_softc *sc) 574 { 575 sc->sc_topology_change_detected = 0; 576 bstp_timer_stop(&sc->sc_tcn_timer); 577 } 578 579 static void 580 bstp_acknowledge_topology_change(struct bridge_softc *sc, 581 struct bridge_iflist *bif) 582 { 583 bif->bif_topology_change_acknowledge = 1; 584 bstp_transmit_config(sc, bif); 585 } 586 587 void 588 bstp_input(struct bridge_softc *sc, struct bridge_iflist *bif, struct mbuf *m) 589 { 590 struct ether_header *eh; 591 struct bstp_tbpdu tpdu; 592 struct bstp_cbpdu cpdu; 593 struct bstp_config_unit cu; 594 struct bstp_tcn_unit tu; 595 uint16_t len; 596 597 eh = mtod(m, struct ether_header *); 598 599 if ((bif->bif_flags & IFBIF_STP) == 0) 600 goto out; 601 602 len = ntohs(eh->ether_type); 603 if (len < sizeof(tpdu)) 604 goto out; 605 606 m_adj(m, ETHER_HDR_LEN); 607 608 if (m->m_pkthdr.len > len) 609 m_adj(m, len - m->m_pkthdr.len); 610 if (m->m_len < sizeof(tpdu) && 611 (m = m_pullup(m, sizeof(tpdu))) == NULL) 612 goto out; 613 614 memcpy(&tpdu, mtod(m, void *), sizeof(tpdu)); 615 616 if (tpdu.tbu_dsap != LLC_8021D_LSAP || 617 tpdu.tbu_ssap != LLC_8021D_LSAP || 618 tpdu.tbu_ctl != LLC_UI) 619 goto out; 620 if (tpdu.tbu_protoid != 0 || tpdu.tbu_protover != 0) 621 goto out; 622 623 switch (tpdu.tbu_bpdutype) { 624 case BSTP_MSGTYPE_TCN: 625 tu.tu_message_type = tpdu.tbu_bpdutype; 626 627 BRIDGE_LOCK(sc); 628 bstp_received_tcn_bpdu(sc, bif, &tu); 629 BRIDGE_UNLOCK(sc); 630 631 break; 632 case BSTP_MSGTYPE_CFG: 633 if (m->m_len < sizeof(cpdu) && 634 (m = m_pullup(m, sizeof(cpdu))) == NULL) 635 goto out; 636 memcpy(&cpdu, mtod(m, void *), sizeof(cpdu)); 637 638 cu.cu_rootid = 639 (((uint64_t)ntohs(cpdu.cbu_rootpri)) << 48) | 640 (((uint64_t)cpdu.cbu_rootaddr[0]) << 40) | 641 (((uint64_t)cpdu.cbu_rootaddr[1]) << 32) | 642 (((uint64_t)cpdu.cbu_rootaddr[2]) << 24) | 643 (((uint64_t)cpdu.cbu_rootaddr[3]) << 16) | 644 (((uint64_t)cpdu.cbu_rootaddr[4]) << 8) | 645 (((uint64_t)cpdu.cbu_rootaddr[5]) << 0); 646 647 cu.cu_bridge_id = 648 (((uint64_t)ntohs(cpdu.cbu_bridgepri)) << 48) | 649 (((uint64_t)cpdu.cbu_bridgeaddr[0]) << 40) | 650 (((uint64_t)cpdu.cbu_bridgeaddr[1]) << 32) | 651 (((uint64_t)cpdu.cbu_bridgeaddr[2]) << 24) | 652 (((uint64_t)cpdu.cbu_bridgeaddr[3]) << 16) | 653 (((uint64_t)cpdu.cbu_bridgeaddr[4]) << 8) | 654 (((uint64_t)cpdu.cbu_bridgeaddr[5]) << 0); 655 656 cu.cu_root_path_cost = ntohl(cpdu.cbu_rootpathcost); 657 cu.cu_message_age = ntohs(cpdu.cbu_messageage); 658 cu.cu_max_age = ntohs(cpdu.cbu_maxage); 659 cu.cu_hello_time = ntohs(cpdu.cbu_hellotime); 660 cu.cu_forward_delay = ntohs(cpdu.cbu_forwarddelay); 661 cu.cu_port_id = ntohs(cpdu.cbu_portid); 662 cu.cu_message_type = cpdu.cbu_bpdutype; 663 cu.cu_topology_change_acknowledgment = 664 (cpdu.cbu_flags & BSTP_FLAG_TCA) ? 1 : 0; 665 cu.cu_topology_change = 666 (cpdu.cbu_flags & BSTP_FLAG_TC) ? 1 : 0; 667 668 BRIDGE_LOCK(sc); 669 bstp_received_config_bpdu(sc, bif, &cu); 670 BRIDGE_UNLOCK(sc); 671 672 break; 673 default: 674 goto out; 675 } 676 677 out: 678 m_freem(m); 679 return; 680 } 681 682 static void 683 bstp_received_config_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif, 684 struct bstp_config_unit *cu) 685 { 686 int root; 687 688 root = bstp_root_bridge(sc); 689 690 if (bif->bif_state != BSTP_IFSTATE_DISABLED) { 691 if (bstp_supersedes_port_info(sc, bif, cu)) { 692 bstp_record_config_information(sc, bif, cu); 693 bstp_configuration_update(sc); 694 bstp_port_state_selection(sc); 695 696 if ((bstp_root_bridge(sc) == 0) && root) { 697 bstp_timer_stop(&sc->sc_hello_timer); 698 699 if (sc->sc_topology_change_detected) { 700 bstp_timer_stop( 701 &sc->sc_topology_change_timer); 702 bstp_transmit_tcn(sc); 703 bstp_timer_start(&sc->sc_tcn_timer, 0); 704 } 705 } 706 707 if (bif == sc->sc_root_port) { 708 bstp_record_config_timeout_values(sc, cu); 709 bstp_config_bpdu_generation(sc); 710 711 if (cu->cu_topology_change_acknowledgment) 712 bstp_topology_change_acknowledged(sc); 713 } 714 } else if (bstp_designated_port(sc, bif)) 715 bstp_transmit_config(sc, bif); 716 } 717 } 718 719 static void 720 bstp_received_tcn_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif, 721 struct bstp_tcn_unit *tcn) 722 { 723 if (bif->bif_state != BSTP_IFSTATE_DISABLED && 724 bstp_designated_port(sc, bif)) { 725 bstp_topology_change_detection(sc); 726 bstp_acknowledge_topology_change(sc, bif); 727 } 728 } 729 730 static void 731 bstp_hello_timer_expiry(struct bridge_softc *sc) 732 { 733 bstp_config_bpdu_generation(sc); 734 bstp_timer_start(&sc->sc_hello_timer, 0); 735 } 736 737 static void 738 bstp_message_age_timer_expiry(struct bridge_softc *sc, 739 struct bridge_iflist *bif) 740 { 741 int root; 742 743 root = bstp_root_bridge(sc); 744 bstp_become_designated_port(sc, bif); 745 bstp_configuration_update(sc); 746 bstp_port_state_selection(sc); 747 748 if ((bstp_root_bridge(sc)) && (root == 0)) { 749 sc->sc_max_age = sc->sc_bridge_max_age; 750 sc->sc_hello_time = sc->sc_bridge_hello_time; 751 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 752 753 bstp_topology_change_detection(sc); 754 bstp_timer_stop(&sc->sc_tcn_timer); 755 bstp_config_bpdu_generation(sc); 756 bstp_timer_start(&sc->sc_hello_timer, 0); 757 } 758 } 759 760 static void 761 bstp_forward_delay_timer_expiry(struct bridge_softc *sc, 762 struct bridge_iflist *bif) 763 { 764 if (bif->bif_state == BSTP_IFSTATE_LISTENING) { 765 bstp_set_port_state(bif, BSTP_IFSTATE_LEARNING); 766 bstp_timer_start(&bif->bif_forward_delay_timer, 0); 767 } else if (bif->bif_state == BSTP_IFSTATE_LEARNING) { 768 bstp_set_port_state(bif, BSTP_IFSTATE_FORWARDING); 769 if (bstp_designated_for_some_port(sc) && 770 bif->bif_change_detection_enabled) 771 bstp_topology_change_detection(sc); 772 } 773 } 774 775 static int 776 bstp_designated_for_some_port(struct bridge_softc *sc) 777 { 778 779 struct bridge_iflist *bif; 780 781 BRIDGE_IFLIST_WRITER_FOREACH(bif, sc) { 782 if ((bif->bif_flags & IFBIF_STP) == 0) 783 continue; 784 if (bif->bif_designated_bridge == sc->sc_bridge_id) 785 return (1); 786 } 787 return (0); 788 } 789 790 static void 791 bstp_tcn_timer_expiry(struct bridge_softc *sc) 792 { 793 bstp_transmit_tcn(sc); 794 bstp_timer_start(&sc->sc_tcn_timer, 0); 795 } 796 797 static void 798 bstp_topology_change_timer_expiry(struct bridge_softc *sc) 799 { 800 sc->sc_topology_change_detected = 0; 801 sc->sc_topology_change = 0; 802 } 803 804 static void 805 bstp_hold_timer_expiry(struct bridge_softc *sc, struct bridge_iflist *bif) 806 { 807 if (bif->bif_config_pending) 808 bstp_transmit_config(sc, bif); 809 } 810 811 void 812 bstp_initialization(struct bridge_softc *sc) 813 { 814 struct bridge_iflist *bif, *mif; 815 816 mif = NULL; 817 818 BRIDGE_LOCK(sc); 819 820 BRIDGE_IFLIST_WRITER_FOREACH(bif, sc) { 821 if ((bif->bif_flags & IFBIF_STP) == 0) 822 continue; 823 if (bif->bif_ifp->if_type != IFT_ETHER) 824 continue; 825 bif->bif_port_id = (bif->bif_priority << 8) | 826 (bif->bif_ifp->if_index & 0xff); 827 828 if (mif == NULL) { 829 mif = bif; 830 continue; 831 } 832 if (memcmp(CLLADDR(bif->bif_ifp->if_sadl), 833 CLLADDR(mif->bif_ifp->if_sadl), ETHER_ADDR_LEN) < 0) { 834 mif = bif; 835 continue; 836 } 837 } 838 839 if (mif == NULL) { 840 BRIDGE_UNLOCK(sc); 841 bstp_stop(sc); 842 return; 843 } 844 845 sc->sc_bridge_id = 846 (((uint64_t)sc->sc_bridge_priority) << 48) | 847 (((uint64_t)(uint8_t)CLLADDR(mif->bif_ifp->if_sadl)[0]) << 40) | 848 (((uint64_t)(uint8_t)CLLADDR(mif->bif_ifp->if_sadl)[1]) << 32) | 849 (((uint64_t)(uint8_t)CLLADDR(mif->bif_ifp->if_sadl)[2]) << 24) | 850 (((uint64_t)(uint8_t)CLLADDR(mif->bif_ifp->if_sadl)[3]) << 16) | 851 (((uint64_t)(uint8_t)CLLADDR(mif->bif_ifp->if_sadl)[4]) << 8) | 852 (((uint64_t)(uint8_t)CLLADDR(mif->bif_ifp->if_sadl)[5]) << 0); 853 854 BRIDGE_UNLOCK(sc); 855 856 sc->sc_designated_root = sc->sc_bridge_id; 857 sc->sc_root_path_cost = 0; 858 sc->sc_root_port = NULL; 859 860 sc->sc_max_age = sc->sc_bridge_max_age; 861 sc->sc_hello_time = sc->sc_bridge_hello_time; 862 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 863 sc->sc_topology_change_detected = 0; 864 sc->sc_topology_change = 0; 865 bstp_timer_stop(&sc->sc_tcn_timer); 866 bstp_timer_stop(&sc->sc_topology_change_timer); 867 868 if (callout_pending(&sc->sc_bstpcallout) == 0) 869 callout_reset(&sc->sc_bstpcallout, hz, 870 bstp_tick, sc); 871 872 BRIDGE_LOCK(sc); 873 874 BRIDGE_IFLIST_WRITER_FOREACH(bif, sc) { 875 if (bif->bif_flags & IFBIF_STP) 876 bstp_enable_port(sc, bif); 877 else 878 bstp_disable_port(sc, bif); 879 } 880 881 bstp_port_state_selection(sc); 882 bstp_config_bpdu_generation(sc); 883 bstp_timer_start(&sc->sc_hello_timer, 0); 884 885 BRIDGE_UNLOCK(sc); 886 } 887 888 void 889 bstp_stop(struct bridge_softc *sc) 890 { 891 struct bridge_iflist *bif; 892 893 BRIDGE_LOCK(sc); 894 BRIDGE_IFLIST_WRITER_FOREACH(bif, sc) { 895 bstp_set_port_state(bif, BSTP_IFSTATE_DISABLED); 896 bstp_timer_stop(&bif->bif_hold_timer); 897 bstp_timer_stop(&bif->bif_message_age_timer); 898 bstp_timer_stop(&bif->bif_forward_delay_timer); 899 } 900 BRIDGE_UNLOCK(sc); 901 902 callout_stop(&sc->sc_bstpcallout); 903 904 bstp_timer_stop(&sc->sc_topology_change_timer); 905 bstp_timer_stop(&sc->sc_tcn_timer); 906 bstp_timer_stop(&sc->sc_hello_timer); 907 908 } 909 910 static void 911 bstp_initialize_port(struct bridge_softc *sc, struct bridge_iflist *bif) 912 { 913 bstp_become_designated_port(sc, bif); 914 bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING); 915 bif->bif_topology_change_acknowledge = 0; 916 bif->bif_config_pending = 0; 917 bif->bif_change_detection_enabled = 1; 918 bstp_timer_stop(&bif->bif_message_age_timer); 919 bstp_timer_stop(&bif->bif_forward_delay_timer); 920 bstp_timer_stop(&bif->bif_hold_timer); 921 } 922 923 static void 924 bstp_enable_port(struct bridge_softc *sc, struct bridge_iflist *bif) 925 { 926 bstp_initialize_port(sc, bif); 927 bstp_port_state_selection(sc); 928 } 929 930 static void 931 bstp_disable_port(struct bridge_softc *sc, struct bridge_iflist *bif) 932 { 933 int root; 934 935 root = bstp_root_bridge(sc); 936 bstp_become_designated_port(sc, bif); 937 bstp_set_port_state(bif, BSTP_IFSTATE_DISABLED); 938 bif->bif_topology_change_acknowledge = 0; 939 bif->bif_config_pending = 0; 940 bstp_timer_stop(&bif->bif_message_age_timer); 941 bstp_timer_stop(&bif->bif_forward_delay_timer); 942 bstp_configuration_update(sc); 943 bstp_port_state_selection(sc); 944 945 if (bstp_root_bridge(sc) && (root == 0)) { 946 sc->sc_max_age = sc->sc_bridge_max_age; 947 sc->sc_hello_time = sc->sc_bridge_hello_time; 948 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 949 950 bstp_topology_change_detection(sc); 951 bstp_timer_stop(&sc->sc_tcn_timer); 952 bstp_config_bpdu_generation(sc); 953 bstp_timer_start(&sc->sc_hello_timer, 0); 954 } 955 } 956 957 #if notused 958 static void 959 bstp_set_bridge_priority(struct bridge_softc *sc, uint64_t new_bridge_id) 960 { 961 struct bridge_iflist *bif; 962 int root; 963 964 root = bstp_root_bridge(sc); 965 966 BRIDGE_IFLIST_WRITER_FOREACH(bif, sc) { 967 if ((bif->bif_flags & IFBIF_STP) == 0) 968 continue; 969 if (bstp_designated_port(sc, bif)) 970 bif->bif_designated_bridge = new_bridge_id; 971 } 972 973 sc->sc_bridge_id = new_bridge_id; 974 975 bstp_configuration_update(sc); 976 bstp_port_state_selection(sc); 977 978 if (bstp_root_bridge(sc) && (root == 0)) { 979 sc->sc_max_age = sc->sc_bridge_max_age; 980 sc->sc_hello_time = sc->sc_bridge_hello_time; 981 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 982 983 bstp_topology_change_detection(sc); 984 bstp_timer_stop(&sc->sc_tcn_timer); 985 bstp_config_bpdu_generation(sc); 986 bstp_timer_start(&sc->sc_hello_timer, 0); 987 } 988 } 989 990 static void 991 bstp_set_port_priority(struct bridge_softc *sc, struct bridge_iflist *bif, 992 uint16_t new_port_id) 993 { 994 if (bstp_designated_port(sc, bif)) 995 bif->bif_designated_port = new_port_id; 996 997 bif->bif_port_id = new_port_id; 998 999 if ((sc->sc_bridge_id == bif->bif_designated_bridge) && 1000 (bif->bif_port_id < bif->bif_designated_port)) { 1001 bstp_become_designated_port(sc, bif); 1002 bstp_port_state_selection(sc); 1003 } 1004 } 1005 1006 static void 1007 bstp_set_path_cost(struct bridge_softc *sc, struct bridge_iflist *bif, 1008 uint32_t path_cost) 1009 { 1010 bif->bif_path_cost = path_cost; 1011 bstp_configuration_update(sc); 1012 bstp_port_state_selection(sc); 1013 } 1014 #endif 1015 1016 static void 1017 bstp_ifupdstatus(struct bridge_softc *sc, struct bridge_iflist *bif) 1018 { 1019 struct ifnet *ifp = bif->bif_ifp; 1020 1021 if (ifp->if_flags & IFF_UP) { 1022 switch (ifp->if_link_state) { 1023 case LINK_STATE_UNKNOWN: 1024 /* 1025 * Just enable the port if the link state is 1026 * unknown. 1027 */ 1028 if (bif->bif_state == BSTP_IFSTATE_DISABLED) 1029 bstp_enable_port(sc, bif); 1030 break; 1031 1032 case LINK_STATE_UP: 1033 if (bif->bif_state == BSTP_IFSTATE_DISABLED) 1034 bstp_enable_port(sc, bif); 1035 break; 1036 1037 case LINK_STATE_DOWN: 1038 if (bif->bif_state != BSTP_IFSTATE_DISABLED) 1039 bstp_disable_port(sc, bif); 1040 break; 1041 } 1042 return; 1043 } 1044 1045 if (bif->bif_state != BSTP_IFSTATE_DISABLED) 1046 bstp_disable_port(sc, bif); 1047 } 1048 1049 static void 1050 bstp_tick(void *arg) 1051 { 1052 struct bridge_softc *sc = arg; 1053 struct bridge_iflist *bif; 1054 1055 BRIDGE_LOCK(sc); 1056 1057 BRIDGE_IFLIST_WRITER_FOREACH(bif, sc) { 1058 if ((bif->bif_flags & IFBIF_STP) == 0) 1059 continue; 1060 /* 1061 * XXX This can cause a lag in "link does away" 1062 * XXX and "spanning tree gets updated". We need 1063 * XXX come sort of callback from the link state 1064 * XXX update code to kick spanning tree. 1065 * XXX --thorpej@NetBSD.org 1066 */ 1067 bstp_ifupdstatus(sc, bif); 1068 } 1069 1070 if (bstp_timer_expired(&sc->sc_hello_timer, sc->sc_hello_time)) 1071 bstp_hello_timer_expiry(sc); 1072 1073 if (bstp_timer_expired(&sc->sc_tcn_timer, sc->sc_bridge_hello_time)) 1074 bstp_tcn_timer_expiry(sc); 1075 1076 if (bstp_timer_expired(&sc->sc_topology_change_timer, 1077 sc->sc_topology_change_time)) 1078 bstp_topology_change_timer_expiry(sc); 1079 1080 BRIDGE_IFLIST_WRITER_FOREACH(bif, sc) { 1081 if ((bif->bif_flags & IFBIF_STP) == 0) 1082 continue; 1083 if (bstp_timer_expired(&bif->bif_message_age_timer, 1084 sc->sc_max_age)) 1085 bstp_message_age_timer_expiry(sc, bif); 1086 } 1087 1088 BRIDGE_IFLIST_WRITER_FOREACH(bif, sc) { 1089 if ((bif->bif_flags & IFBIF_STP) == 0) 1090 continue; 1091 if (bstp_timer_expired(&bif->bif_forward_delay_timer, 1092 sc->sc_forward_delay)) 1093 bstp_forward_delay_timer_expiry(sc, bif); 1094 1095 if (bstp_timer_expired(&bif->bif_hold_timer, 1096 sc->sc_hold_time)) 1097 bstp_hold_timer_expiry(sc, bif); 1098 } 1099 1100 if (sc->sc_if.if_flags & IFF_RUNNING) 1101 callout_reset(&sc->sc_bstpcallout, hz, bstp_tick, sc); 1102 1103 BRIDGE_UNLOCK(sc); 1104 } 1105 1106 static void 1107 bstp_timer_start(struct bridge_timer *t, uint16_t v) 1108 { 1109 t->value = v; 1110 t->active = 1; 1111 } 1112 1113 static void 1114 bstp_timer_stop(struct bridge_timer *t) 1115 { 1116 t->value = 0; 1117 t->active = 0; 1118 } 1119 1120 static int 1121 bstp_timer_expired(struct bridge_timer *t, uint16_t v) 1122 { 1123 if (t->active == 0) 1124 return (0); 1125 t->value += BSTP_TICK_VAL; 1126 if (t->value >= v) { 1127 bstp_timer_stop(t); 1128 return (1); 1129 } 1130 return (0); 1131 1132 } 1133