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 #define sc_if ifb_ac.ac_if 70 71 /* BPDU message types */ 72 #define BSTP_MSGTYPE_CFG 0x00 /* Configuration */ 73 #define BSTP_MSGTYPE_TCN 0x80 /* Topology chg notification */ 74 75 /* BPDU flags */ 76 #define BSTP_FLAG_TC 0x01 /* Topology change */ 77 #define BSTP_FLAG_TCA 0x80 /* Topology change ack */ 78 79 #define BSTP_MESSAGE_AGE_INCR (1 * 256) /* in 256ths of a second */ 80 #define BSTP_TICK_VAL (1 * 256) /* in 256ths of a second */ 81 82 /* 83 * Because BPDU's do not make nicely aligned structures, two different 84 * declarations are used: bstp_?bpdu (wire representation, packed) and 85 * bstp_*_unit (internal, nicely aligned version). 86 */ 87 88 /* configuration bridge protocol data unit */ 89 struct bstp_cbpdu { 90 uint8_t cbu_dsap; /* LLC: destination sap */ 91 uint8_t cbu_ssap; /* LLC: source sap */ 92 uint8_t cbu_ctl; /* LLC: control */ 93 uint16_t cbu_protoid; /* protocol id */ 94 uint8_t cbu_protover; /* protocol version */ 95 uint8_t cbu_bpdutype; /* message type */ 96 uint8_t cbu_flags; /* flags (below) */ 97 98 /* root id */ 99 uint16_t cbu_rootpri; /* root priority */ 100 uint8_t cbu_rootaddr[6]; /* root address */ 101 102 uint32_t cbu_rootpathcost; /* root path cost */ 103 104 /* bridge id */ 105 uint16_t cbu_bridgepri; /* bridge priority */ 106 uint8_t cbu_bridgeaddr[6]; /* bridge address */ 107 108 uint16_t cbu_portid; /* port id */ 109 uint16_t cbu_messageage; /* current message age */ 110 uint16_t cbu_maxage; /* maximum age */ 111 uint16_t cbu_hellotime; /* hello time */ 112 uint16_t cbu_forwarddelay; /* forwarding delay */ 113 } __attribute__((__packed__)); 114 115 /* topology change notification bridge protocol data unit */ 116 struct bstp_tbpdu { 117 uint8_t tbu_dsap; /* LLC: destination sap */ 118 uint8_t tbu_ssap; /* LLC: source sap */ 119 uint8_t tbu_ctl; /* LLC: control */ 120 uint16_t tbu_protoid; /* protocol id */ 121 uint8_t tbu_protover; /* protocol version */ 122 uint8_t tbu_bpdutype; /* message type */ 123 } __attribute__((__packed__)); 124 125 const uint8_t bstp_etheraddr[] = { 0x01, 0x80, 0xc2, 0x00, 0x00, 0x00 }; 126 127 void bstp_initialize_port(struct bridge_softc *, struct bridge_iflist *); 128 void bstp_ifupdstatus(struct bridge_softc *, struct bridge_iflist *); 129 void bstp_enable_port(struct bridge_softc *, struct bridge_iflist *); 130 void bstp_disable_port(struct bridge_softc *, struct bridge_iflist *); 131 void bstp_enable_change_detection(struct bridge_iflist *); 132 void bstp_disable_change_detection(struct bridge_iflist *); 133 int bstp_root_bridge(struct bridge_softc *sc); 134 int bstp_supersedes_port_info(struct bridge_softc *, 135 struct bridge_iflist *, struct bstp_config_unit *); 136 int bstp_designated_port(struct bridge_softc *, struct bridge_iflist *); 137 int bstp_designated_for_some_port(struct bridge_softc *); 138 void bstp_transmit_config(struct bridge_softc *, struct bridge_iflist *); 139 void bstp_transmit_tcn(struct bridge_softc *); 140 void bstp_received_config_bpdu(struct bridge_softc *, 141 struct bridge_iflist *, struct bstp_config_unit *); 142 void bstp_received_tcn_bpdu(struct bridge_softc *, struct bridge_iflist *, 143 struct bstp_tcn_unit *); 144 void bstp_record_config_information(struct bridge_softc *, 145 struct bridge_iflist *, struct bstp_config_unit *); 146 void bstp_record_config_timeout_values(struct bridge_softc *, 147 struct bstp_config_unit *); 148 void bstp_config_bpdu_generation(struct bridge_softc *); 149 void bstp_send_config_bpdu(struct bridge_softc *, struct bridge_iflist *, 150 struct bstp_config_unit *); 151 void bstp_configuration_update(struct bridge_softc *); 152 void bstp_root_selection(struct bridge_softc *); 153 void bstp_designated_port_selection(struct bridge_softc *); 154 void bstp_become_designated_port(struct bridge_softc *, 155 struct bridge_iflist *); 156 void bstp_port_state_selection(struct bridge_softc *); 157 void bstp_make_forwarding(struct bridge_softc *, struct bridge_iflist *); 158 void bstp_make_blocking(struct bridge_softc *, struct bridge_iflist *); 159 void bstp_set_port_state(struct bridge_iflist *, uint8_t); 160 void bstp_set_bridge_priority(struct bridge_softc *, uint64_t); 161 void bstp_set_port_priority(struct bridge_softc *, struct bridge_iflist *, 162 uint16_t); 163 void bstp_set_path_cost(struct bridge_softc *, struct bridge_iflist *, 164 uint32_t); 165 void bstp_topology_change_detection(struct bridge_softc *); 166 void bstp_topology_change_acknowledged(struct bridge_softc *); 167 void bstp_acknowledge_topology_change(struct bridge_softc *, 168 struct bridge_iflist *); 169 170 void bstp_tick(void *); 171 void bstp_timer_start(struct bridge_timer *, uint16_t); 172 void bstp_timer_stop(struct bridge_timer *); 173 int bstp_timer_expired(struct bridge_timer *, uint16_t); 174 175 void bstp_hold_timer_expiry(struct bridge_softc *, struct bridge_iflist *); 176 void bstp_message_age_timer_expiry(struct bridge_softc *, 177 struct bridge_iflist *); 178 void bstp_forward_delay_timer_expiry(struct bridge_softc *, 179 struct bridge_iflist *); 180 void bstp_topology_change_timer_expiry(struct bridge_softc *); 181 void bstp_tcn_timer_expiry(struct bridge_softc *); 182 void bstp_hello_timer_expiry(struct bridge_softc *); 183 184 void 185 bstp_transmit_config(struct bridge_softc *sc, struct bridge_iflist *bif) 186 { 187 if (bif->bif_hold_timer.active) { 188 bif->bif_config_pending = 1; 189 return; 190 } 191 192 bif->bif_config_bpdu.cu_message_type = BSTP_MSGTYPE_CFG; 193 bif->bif_config_bpdu.cu_rootid = sc->sc_designated_root; 194 bif->bif_config_bpdu.cu_root_path_cost = sc->sc_root_path_cost; 195 bif->bif_config_bpdu.cu_bridge_id = sc->sc_bridge_id; 196 bif->bif_config_bpdu.cu_port_id = bif->bif_port_id; 197 198 if (bstp_root_bridge(sc)) 199 bif->bif_config_bpdu.cu_message_age = 0; 200 else 201 bif->bif_config_bpdu.cu_message_age = 202 sc->sc_root_port->bif_message_age_timer.value + 203 BSTP_MESSAGE_AGE_INCR; 204 205 bif->bif_config_bpdu.cu_max_age = sc->sc_max_age; 206 bif->bif_config_bpdu.cu_hello_time = sc->sc_hello_time; 207 bif->bif_config_bpdu.cu_forward_delay = sc->sc_forward_delay; 208 bif->bif_config_bpdu.cu_topology_change_acknowledgment 209 = bif->bif_topology_change_acknowledge; 210 bif->bif_config_bpdu.cu_topology_change = sc->sc_topology_change; 211 212 if (bif->bif_config_bpdu.cu_message_age < sc->sc_max_age) { 213 bif->bif_topology_change_acknowledge = 0; 214 bif->bif_config_pending = 0; 215 bstp_send_config_bpdu(sc, bif, &bif->bif_config_bpdu); 216 bstp_timer_start(&bif->bif_hold_timer, 0); 217 } 218 } 219 220 void 221 bstp_send_config_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif, 222 struct bstp_config_unit *cu) 223 { 224 struct ifnet *ifp; 225 struct mbuf *m; 226 struct ether_header *eh; 227 struct bstp_cbpdu bpdu; 228 229 BRIDGE_LOCK_ASSERT(sc); 230 231 ifp = bif->bif_ifp; 232 233 if ((ifp->if_flags & IFF_RUNNING) == 0) 234 return; 235 236 MGETHDR(m, M_DONTWAIT, MT_DATA); 237 if (m == NULL) 238 return; 239 240 eh = mtod(m, struct ether_header *); 241 242 m->m_pkthdr.rcvif = ifp; 243 m->m_pkthdr.len = sizeof(*eh) + sizeof(bpdu); 244 m->m_len = m->m_pkthdr.len; 245 246 bpdu.cbu_ssap = bpdu.cbu_dsap = LLC_8021D_LSAP; 247 bpdu.cbu_ctl = LLC_UI; 248 bpdu.cbu_protoid = htons(0); 249 bpdu.cbu_protover = 0; 250 bpdu.cbu_bpdutype = cu->cu_message_type; 251 bpdu.cbu_flags = (cu->cu_topology_change ? BSTP_FLAG_TC : 0) | 252 (cu->cu_topology_change_acknowledgment ? BSTP_FLAG_TCA : 0); 253 254 bpdu.cbu_rootpri = htons(cu->cu_rootid >> 48); 255 bpdu.cbu_rootaddr[0] = cu->cu_rootid >> 40; 256 bpdu.cbu_rootaddr[1] = cu->cu_rootid >> 32; 257 bpdu.cbu_rootaddr[2] = cu->cu_rootid >> 24; 258 bpdu.cbu_rootaddr[3] = cu->cu_rootid >> 16; 259 bpdu.cbu_rootaddr[4] = cu->cu_rootid >> 8; 260 bpdu.cbu_rootaddr[5] = cu->cu_rootid >> 0; 261 262 bpdu.cbu_rootpathcost = htonl(cu->cu_root_path_cost); 263 264 bpdu.cbu_bridgepri = htons(cu->cu_rootid >> 48); 265 bpdu.cbu_bridgeaddr[0] = cu->cu_rootid >> 40; 266 bpdu.cbu_bridgeaddr[1] = cu->cu_rootid >> 32; 267 bpdu.cbu_bridgeaddr[2] = cu->cu_rootid >> 24; 268 bpdu.cbu_bridgeaddr[3] = cu->cu_rootid >> 16; 269 bpdu.cbu_bridgeaddr[4] = cu->cu_rootid >> 8; 270 bpdu.cbu_bridgeaddr[5] = cu->cu_rootid >> 0; 271 272 bpdu.cbu_portid = htons(cu->cu_port_id); 273 bpdu.cbu_messageage = htons(cu->cu_message_age); 274 bpdu.cbu_maxage = htons(cu->cu_max_age); 275 bpdu.cbu_hellotime = htons(cu->cu_hello_time); 276 bpdu.cbu_forwarddelay = htons(cu->cu_forward_delay); 277 278 memcpy(eh->ether_shost, IF_LLADDR(ifp), ETHER_ADDR_LEN); 279 memcpy(eh->ether_dhost, bstp_etheraddr, ETHER_ADDR_LEN); 280 eh->ether_type = htons(sizeof(bpdu)); 281 282 memcpy(mtod(m, caddr_t) + sizeof(*eh), &bpdu, sizeof(bpdu)); 283 284 /* XXX: safe here?!? */ 285 BRIDGE_UNLOCK(sc); 286 bridge_enqueue(sc, ifp, m, 0); 287 BRIDGE_LOCK(sc); 288 } 289 290 int 291 bstp_root_bridge(struct bridge_softc *sc) 292 { 293 return (sc->sc_designated_root == sc->sc_bridge_id); 294 } 295 296 int 297 bstp_supersedes_port_info(struct bridge_softc *sc, struct bridge_iflist *bif, 298 struct bstp_config_unit *cu) 299 { 300 if (cu->cu_rootid < bif->bif_designated_root) 301 return (1); 302 if (cu->cu_rootid > bif->bif_designated_root) 303 return (0); 304 305 if (cu->cu_root_path_cost < bif->bif_designated_cost) 306 return (1); 307 if (cu->cu_root_path_cost > bif->bif_designated_cost) 308 return (0); 309 310 if (cu->cu_bridge_id < bif->bif_designated_bridge) 311 return (1); 312 if (cu->cu_bridge_id > bif->bif_designated_bridge) 313 return (0); 314 315 if (sc->sc_bridge_id != cu->cu_bridge_id) 316 return (1); 317 if (cu->cu_port_id <= bif->bif_designated_port) 318 return (1); 319 return (0); 320 } 321 322 void 323 bstp_record_config_information(struct bridge_softc *sc, 324 struct bridge_iflist *bif, struct bstp_config_unit *cu) 325 { 326 bif->bif_designated_root = cu->cu_rootid; 327 bif->bif_designated_cost = cu->cu_root_path_cost; 328 bif->bif_designated_bridge = cu->cu_bridge_id; 329 bif->bif_designated_port = cu->cu_port_id; 330 bstp_timer_start(&bif->bif_message_age_timer, cu->cu_message_age); 331 } 332 333 void 334 bstp_record_config_timeout_values(struct bridge_softc *sc, 335 struct bstp_config_unit *config) 336 { 337 sc->sc_max_age = config->cu_max_age; 338 sc->sc_hello_time = config->cu_hello_time; 339 sc->sc_forward_delay = config->cu_forward_delay; 340 sc->sc_topology_change = config->cu_topology_change; 341 } 342 343 void 344 bstp_config_bpdu_generation(struct bridge_softc *sc) 345 { 346 struct bridge_iflist *bif; 347 348 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 349 if ((bif->bif_flags & IFBIF_STP) == 0) 350 continue; 351 if (bstp_designated_port(sc, bif) && 352 (bif->bif_state != BSTP_IFSTATE_DISABLED)) 353 bstp_transmit_config(sc, bif); 354 } 355 } 356 357 int 358 bstp_designated_port(struct bridge_softc *sc, struct bridge_iflist *bif) 359 { 360 return ((bif->bif_designated_bridge == sc->sc_bridge_id) 361 && (bif->bif_designated_port == bif->bif_port_id)); 362 } 363 364 void 365 bstp_transmit_tcn(struct bridge_softc *sc) 366 { 367 struct bstp_tbpdu bpdu; 368 struct bridge_iflist *bif = sc->sc_root_port; 369 struct ifnet *ifp = bif->bif_ifp; 370 struct ether_header *eh; 371 struct mbuf *m; 372 373 BRIDGE_LOCK_ASSERT(sc); 374 375 if ((ifp->if_flags & IFF_RUNNING) == 0) 376 return; 377 378 MGETHDR(m, M_DONTWAIT, MT_DATA); 379 if (m == NULL) 380 return; 381 382 m->m_pkthdr.rcvif = ifp; 383 m->m_pkthdr.len = sizeof(*eh) + sizeof(bpdu); 384 m->m_len = m->m_pkthdr.len; 385 386 eh = mtod(m, struct ether_header *); 387 388 memcpy(eh->ether_shost, IF_LLADDR(ifp), ETHER_ADDR_LEN); 389 memcpy(eh->ether_dhost, bstp_etheraddr, ETHER_ADDR_LEN); 390 eh->ether_type = htons(sizeof(bpdu)); 391 392 bpdu.tbu_ssap = bpdu.tbu_dsap = LLC_8021D_LSAP; 393 bpdu.tbu_ctl = LLC_UI; 394 bpdu.tbu_protoid = 0; 395 bpdu.tbu_protover = 0; 396 bpdu.tbu_bpdutype = BSTP_MSGTYPE_TCN; 397 398 memcpy(mtod(m, caddr_t) + sizeof(*eh), &bpdu, sizeof(bpdu)); 399 400 /* XXX: safe here?!? */ 401 BRIDGE_UNLOCK(sc); 402 bridge_enqueue(sc, ifp, m, 0); 403 BRIDGE_LOCK(sc); 404 } 405 406 void 407 bstp_configuration_update(struct bridge_softc *sc) 408 { 409 BRIDGE_LOCK_ASSERT(sc); 410 411 bstp_root_selection(sc); 412 bstp_designated_port_selection(sc); 413 } 414 415 void 416 bstp_root_selection(struct bridge_softc *sc) 417 { 418 struct bridge_iflist *root_port = NULL, *bif; 419 420 BRIDGE_LOCK_ASSERT(sc); 421 422 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 423 if ((bif->bif_flags & IFBIF_STP) == 0) 424 continue; 425 if (bstp_designated_port(sc, bif)) 426 continue; 427 if (bif->bif_state == BSTP_IFSTATE_DISABLED) 428 continue; 429 if (bif->bif_designated_root >= sc->sc_bridge_id) 430 continue; 431 if (root_port == NULL) 432 goto set_port; 433 434 if (bif->bif_designated_root < root_port->bif_designated_root) 435 goto set_port; 436 if (bif->bif_designated_root > root_port->bif_designated_root) 437 continue; 438 439 if ((bif->bif_designated_cost + bif->bif_path_cost) < 440 (root_port->bif_designated_cost + root_port->bif_path_cost)) 441 goto set_port; 442 if ((bif->bif_designated_cost + bif->bif_path_cost) > 443 (root_port->bif_designated_cost + root_port->bif_path_cost)) 444 continue; 445 446 if (bif->bif_designated_bridge < 447 root_port->bif_designated_bridge) 448 goto set_port; 449 if (bif->bif_designated_bridge > 450 root_port->bif_designated_bridge) 451 continue; 452 453 if (bif->bif_designated_port < root_port->bif_designated_port) 454 goto set_port; 455 if (bif->bif_designated_port > root_port->bif_designated_port) 456 continue; 457 458 if (bif->bif_port_id >= root_port->bif_port_id) 459 continue; 460 set_port: 461 root_port = bif; 462 } 463 464 sc->sc_root_port = root_port; 465 if (root_port == NULL) { 466 sc->sc_designated_root = sc->sc_bridge_id; 467 sc->sc_root_path_cost = 0; 468 } else { 469 sc->sc_designated_root = root_port->bif_designated_root; 470 sc->sc_root_path_cost = root_port->bif_designated_cost + 471 root_port->bif_path_cost; 472 } 473 } 474 475 void 476 bstp_designated_port_selection(struct bridge_softc *sc) 477 { 478 struct bridge_iflist *bif; 479 480 BRIDGE_LOCK_ASSERT(sc); 481 482 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 483 if ((bif->bif_flags & IFBIF_STP) == 0) 484 continue; 485 if (bstp_designated_port(sc, bif)) 486 goto designated; 487 if (bif->bif_designated_root != sc->sc_designated_root) 488 goto designated; 489 490 if (sc->sc_root_path_cost < bif->bif_designated_cost) 491 goto designated; 492 if (sc->sc_root_path_cost > bif->bif_designated_cost) 493 continue; 494 495 if (sc->sc_bridge_id < bif->bif_designated_bridge) 496 goto designated; 497 if (sc->sc_bridge_id > bif->bif_designated_bridge) 498 continue; 499 500 if (bif->bif_port_id > bif->bif_designated_port) 501 continue; 502 designated: 503 bstp_become_designated_port(sc, bif); 504 } 505 } 506 507 void 508 bstp_become_designated_port(struct bridge_softc *sc, struct bridge_iflist *bif) 509 { 510 bif->bif_designated_root = sc->sc_designated_root; 511 bif->bif_designated_cost = sc->sc_root_path_cost; 512 bif->bif_designated_bridge = sc->sc_bridge_id; 513 bif->bif_designated_port = bif->bif_port_id; 514 } 515 516 void 517 bstp_port_state_selection(struct bridge_softc *sc) 518 { 519 struct bridge_iflist *bif; 520 521 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 522 if ((bif->bif_flags & IFBIF_STP) == 0) 523 continue; 524 if (bif == sc->sc_root_port) { 525 bif->bif_config_pending = 0; 526 bif->bif_topology_change_acknowledge = 0; 527 bstp_make_forwarding(sc, bif); 528 } else if (bstp_designated_port(sc, bif)) { 529 bstp_timer_stop(&bif->bif_message_age_timer); 530 bstp_make_forwarding(sc, bif); 531 } else { 532 bif->bif_config_pending = 0; 533 bif->bif_topology_change_acknowledge = 0; 534 bstp_make_blocking(sc, bif); 535 } 536 } 537 } 538 539 void 540 bstp_make_forwarding(struct bridge_softc *sc, struct bridge_iflist *bif) 541 { 542 if (bif->bif_state == BSTP_IFSTATE_BLOCKING) { 543 bstp_set_port_state(bif, BSTP_IFSTATE_LISTENING); 544 bstp_timer_start(&bif->bif_forward_delay_timer, 0); 545 } 546 } 547 548 void 549 bstp_make_blocking(struct bridge_softc *sc, struct bridge_iflist *bif) 550 { 551 BRIDGE_LOCK_ASSERT(sc); 552 553 if ((bif->bif_state != BSTP_IFSTATE_DISABLED) && 554 (bif->bif_state != BSTP_IFSTATE_BLOCKING)) { 555 if ((bif->bif_state == BSTP_IFSTATE_FORWARDING) || 556 (bif->bif_state == BSTP_IFSTATE_LEARNING)) { 557 if (bif->bif_change_detection_enabled) { 558 bstp_topology_change_detection(sc); 559 } 560 } 561 bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING); 562 bridge_rtdelete(sc, bif->bif_ifp, IFBF_FLUSHDYN); 563 bstp_timer_stop(&bif->bif_forward_delay_timer); 564 } 565 } 566 567 void 568 bstp_set_port_state(struct bridge_iflist *bif, uint8_t state) 569 { 570 bif->bif_state = state; 571 } 572 573 void 574 bstp_topology_change_detection(struct bridge_softc *sc) 575 { 576 if (bstp_root_bridge(sc)) { 577 sc->sc_topology_change = 1; 578 bstp_timer_start(&sc->sc_topology_change_timer, 0); 579 } else if (!sc->sc_topology_change_detected) { 580 bstp_transmit_tcn(sc); 581 bstp_timer_start(&sc->sc_tcn_timer, 0); 582 } 583 sc->sc_topology_change_detected = 1; 584 } 585 586 void 587 bstp_topology_change_acknowledged(struct bridge_softc *sc) 588 { 589 sc->sc_topology_change_detected = 0; 590 bstp_timer_stop(&sc->sc_tcn_timer); 591 } 592 593 void 594 bstp_acknowledge_topology_change(struct bridge_softc *sc, 595 struct bridge_iflist *bif) 596 { 597 bif->bif_topology_change_acknowledge = 1; 598 bstp_transmit_config(sc, bif); 599 } 600 601 struct mbuf * 602 bstp_input(struct ifnet *ifp, struct mbuf *m) 603 { 604 struct bridge_softc *sc = ifp->if_bridge; 605 struct bridge_iflist *bif = NULL; 606 struct ether_header *eh; 607 struct bstp_tbpdu tpdu; 608 struct bstp_cbpdu cpdu; 609 struct bstp_config_unit cu; 610 struct bstp_tcn_unit tu; 611 uint16_t len; 612 613 BRIDGE_LOCK_ASSERT(sc); 614 615 eh = mtod(m, struct ether_header *); 616 617 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 618 if ((bif->bif_flags & IFBIF_STP) == 0) 619 continue; 620 if (bif->bif_ifp == ifp) 621 break; 622 } 623 if (bif == NULL) 624 goto out; 625 626 len = ntohs(eh->ether_type); 627 if (len < sizeof(tpdu)) 628 goto out; 629 630 m_adj(m, ETHER_HDR_LEN); 631 632 if (m->m_pkthdr.len > len) 633 m_adj(m, len - m->m_pkthdr.len); 634 if (m->m_len < sizeof(tpdu) && 635 (m = m_pullup(m, sizeof(tpdu))) == NULL) 636 goto out; 637 638 memcpy(&tpdu, mtod(m, caddr_t), sizeof(tpdu)); 639 640 if (tpdu.tbu_dsap != LLC_8021D_LSAP || 641 tpdu.tbu_ssap != LLC_8021D_LSAP || 642 tpdu.tbu_ctl != LLC_UI) 643 goto out; 644 if (tpdu.tbu_protoid != 0 || tpdu.tbu_protover != 0) 645 goto out; 646 647 switch (tpdu.tbu_bpdutype) { 648 case BSTP_MSGTYPE_TCN: 649 tu.tu_message_type = tpdu.tbu_bpdutype; 650 bstp_received_tcn_bpdu(sc, bif, &tu); 651 break; 652 case BSTP_MSGTYPE_CFG: 653 if (m->m_len < sizeof(cpdu) && 654 (m = m_pullup(m, sizeof(cpdu))) == NULL) 655 goto out; 656 memcpy(&cpdu, mtod(m, caddr_t), sizeof(cpdu)); 657 658 cu.cu_rootid = 659 (((uint64_t)ntohs(cpdu.cbu_rootpri)) << 48) | 660 (((uint64_t)cpdu.cbu_rootaddr[0]) << 40) | 661 (((uint64_t)cpdu.cbu_rootaddr[1]) << 32) | 662 (((uint64_t)cpdu.cbu_rootaddr[2]) << 24) | 663 (((uint64_t)cpdu.cbu_rootaddr[3]) << 16) | 664 (((uint64_t)cpdu.cbu_rootaddr[4]) << 8) | 665 (((uint64_t)cpdu.cbu_rootaddr[5]) << 0); 666 667 cu.cu_bridge_id = 668 (((uint64_t)ntohs(cpdu.cbu_bridgepri)) << 48) | 669 (((uint64_t)cpdu.cbu_bridgeaddr[0]) << 40) | 670 (((uint64_t)cpdu.cbu_bridgeaddr[1]) << 32) | 671 (((uint64_t)cpdu.cbu_bridgeaddr[2]) << 24) | 672 (((uint64_t)cpdu.cbu_bridgeaddr[3]) << 16) | 673 (((uint64_t)cpdu.cbu_bridgeaddr[4]) << 8) | 674 (((uint64_t)cpdu.cbu_bridgeaddr[5]) << 0); 675 676 cu.cu_root_path_cost = ntohl(cpdu.cbu_rootpathcost); 677 cu.cu_message_age = ntohs(cpdu.cbu_messageage); 678 cu.cu_max_age = ntohs(cpdu.cbu_maxage); 679 cu.cu_hello_time = ntohs(cpdu.cbu_hellotime); 680 cu.cu_forward_delay = ntohs(cpdu.cbu_forwarddelay); 681 cu.cu_port_id = ntohs(cpdu.cbu_portid); 682 cu.cu_message_type = cpdu.cbu_bpdutype; 683 cu.cu_topology_change_acknowledgment = 684 (cpdu.cbu_flags & BSTP_FLAG_TCA) ? 1 : 0; 685 cu.cu_topology_change = 686 (cpdu.cbu_flags & BSTP_FLAG_TC) ? 1 : 0; 687 bstp_received_config_bpdu(sc, bif, &cu); 688 break; 689 default: 690 goto out; 691 } 692 693 out: 694 if (m) 695 m_freem(m); 696 return (NULL); 697 } 698 699 void 700 bstp_received_config_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif, 701 struct bstp_config_unit *cu) 702 { 703 int root; 704 705 BRIDGE_LOCK_ASSERT(sc); 706 707 root = bstp_root_bridge(sc); 708 709 if (bif->bif_state != BSTP_IFSTATE_DISABLED) { 710 if (bstp_supersedes_port_info(sc, bif, cu)) { 711 bstp_record_config_information(sc, bif, cu); 712 bstp_configuration_update(sc); 713 bstp_port_state_selection(sc); 714 715 if ((bstp_root_bridge(sc) == 0) && root) { 716 bstp_timer_stop(&sc->sc_hello_timer); 717 718 if (sc->sc_topology_change_detected) { 719 bstp_timer_stop( 720 &sc->sc_topology_change_timer); 721 bstp_transmit_tcn(sc); 722 bstp_timer_start(&sc->sc_tcn_timer, 0); 723 } 724 } 725 726 if (bif == sc->sc_root_port) { 727 bstp_record_config_timeout_values(sc, cu); 728 bstp_config_bpdu_generation(sc); 729 730 if (cu->cu_topology_change_acknowledgment) 731 bstp_topology_change_acknowledged(sc); 732 } 733 } else if (bstp_designated_port(sc, bif)) 734 bstp_transmit_config(sc, bif); 735 } 736 } 737 738 void 739 bstp_received_tcn_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif, 740 struct bstp_tcn_unit *tcn) 741 { 742 if (bif->bif_state != BSTP_IFSTATE_DISABLED && 743 bstp_designated_port(sc, bif)) { 744 bstp_topology_change_detection(sc); 745 bstp_acknowledge_topology_change(sc, bif); 746 } 747 } 748 749 void 750 bstp_hello_timer_expiry(struct bridge_softc *sc) 751 { 752 bstp_config_bpdu_generation(sc); 753 bstp_timer_start(&sc->sc_hello_timer, 0); 754 } 755 756 void 757 bstp_message_age_timer_expiry(struct bridge_softc *sc, 758 struct bridge_iflist *bif) 759 { 760 int root; 761 762 root = bstp_root_bridge(sc); 763 bstp_become_designated_port(sc, bif); 764 bstp_configuration_update(sc); 765 bstp_port_state_selection(sc); 766 767 if ((bstp_root_bridge(sc)) && (root == 0)) { 768 sc->sc_max_age = sc->sc_bridge_max_age; 769 sc->sc_hello_time = sc->sc_bridge_hello_time; 770 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 771 772 bstp_topology_change_detection(sc); 773 bstp_timer_stop(&sc->sc_tcn_timer); 774 bstp_config_bpdu_generation(sc); 775 bstp_timer_start(&sc->sc_hello_timer, 0); 776 } 777 } 778 779 void 780 bstp_forward_delay_timer_expiry(struct bridge_softc *sc, 781 struct bridge_iflist *bif) 782 { 783 if (bif->bif_state == BSTP_IFSTATE_LISTENING) { 784 bstp_set_port_state(bif, BSTP_IFSTATE_LEARNING); 785 bstp_timer_start(&bif->bif_forward_delay_timer, 0); 786 } else if (bif->bif_state == BSTP_IFSTATE_LEARNING) { 787 bstp_set_port_state(bif, BSTP_IFSTATE_FORWARDING); 788 if (bstp_designated_for_some_port(sc) && 789 bif->bif_change_detection_enabled) 790 bstp_topology_change_detection(sc); 791 } 792 } 793 794 int 795 bstp_designated_for_some_port(struct bridge_softc *sc) 796 { 797 798 struct bridge_iflist *bif; 799 800 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 801 if ((bif->bif_flags & IFBIF_STP) == 0) 802 continue; 803 if (bif->bif_designated_bridge == sc->sc_bridge_id) 804 return (1); 805 } 806 return (0); 807 } 808 809 void 810 bstp_tcn_timer_expiry(struct bridge_softc *sc) 811 { 812 bstp_transmit_tcn(sc); 813 bstp_timer_start(&sc->sc_tcn_timer, 0); 814 } 815 816 void 817 bstp_topology_change_timer_expiry(struct bridge_softc *sc) 818 { 819 sc->sc_topology_change_detected = 0; 820 sc->sc_topology_change = 0; 821 } 822 823 void 824 bstp_hold_timer_expiry(struct bridge_softc *sc, struct bridge_iflist *bif) 825 { 826 if (bif->bif_config_pending) 827 bstp_transmit_config(sc, bif); 828 } 829 830 void 831 bstp_initialization(struct bridge_softc *sc) 832 { 833 struct bridge_iflist *bif, *mif; 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(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_if.if_flags & IFF_RUNNING) 1143 callout_reset(&sc->sc_bstpcallout, hz, bstp_tick, sc); 1144 1145 BRIDGE_UNLOCK(sc); 1146 } 1147 1148 void 1149 bstp_timer_start(struct bridge_timer *t, uint16_t v) 1150 { 1151 t->value = v; 1152 t->active = 1; 1153 } 1154 1155 void 1156 bstp_timer_stop(struct bridge_timer *t) 1157 { 1158 t->value = 0; 1159 t->active = 0; 1160 } 1161 1162 int 1163 bstp_timer_expired(struct bridge_timer *t, uint16_t v) 1164 { 1165 if (t->active == 0) 1166 return (0); 1167 t->value += BSTP_TICK_VAL; 1168 if (t->value >= v) { 1169 bstp_timer_stop(t); 1170 return (1); 1171 } 1172 return (0); 1173 1174 } 1175