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