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