1 /* $NetBSD: bridgestp.c,v 1.14 2009/01/18 10:28:55 mrg 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.14 2009/01/18 10:28:55 mrg Exp $"); 44 45 #include <sys/param.h> 46 #include <sys/systm.h> 47 #include <sys/mbuf.h> 48 #include <sys/socket.h> 49 #include <sys/ioctl.h> 50 #include <sys/device.h> 51 #include <sys/kernel.h> 52 #include <sys/callout.h> 53 54 #include <net/if.h> 55 #include <net/if_dl.h> 56 #include <net/if_types.h> 57 #include <net/if_llc.h> 58 59 #include <net/if_ether.h> 60 #include <net/if_bridgevar.h> 61 62 /* BPDU message types */ 63 #define BSTP_MSGTYPE_CFG 0x00 /* Configuration */ 64 #define BSTP_MSGTYPE_TCN 0x80 /* Topology chg notification */ 65 66 /* BPDU flags */ 67 #define BSTP_FLAG_TC 0x01 /* Topology change */ 68 #define BSTP_FLAG_TCA 0x80 /* Topology change ack */ 69 70 #define BSTP_MESSAGE_AGE_INCR (1 * 256) /* in 256ths of a second */ 71 #define BSTP_TICK_VAL (1 * 256) /* in 256ths of a second */ 72 73 /* 74 * Because BPDU's do not make nicely aligned structures, two different 75 * declarations are used: bstp_?bpdu (wire representation, packed) and 76 * bstp_*_unit (internal, nicely aligned version). 77 */ 78 79 /* configuration bridge protocol data unit */ 80 struct bstp_cbpdu { 81 uint8_t cbu_dsap; /* LLC: destination sap */ 82 uint8_t cbu_ssap; /* LLC: source sap */ 83 uint8_t cbu_ctl; /* LLC: control */ 84 uint16_t cbu_protoid; /* protocol id */ 85 uint8_t cbu_protover; /* protocol version */ 86 uint8_t cbu_bpdutype; /* message type */ 87 uint8_t cbu_flags; /* flags (below) */ 88 89 /* root id */ 90 uint16_t cbu_rootpri; /* root priority */ 91 uint8_t cbu_rootaddr[6]; /* root address */ 92 93 uint32_t cbu_rootpathcost; /* root path cost */ 94 95 /* bridge id */ 96 uint16_t cbu_bridgepri; /* bridge priority */ 97 uint8_t cbu_bridgeaddr[6]; /* bridge address */ 98 99 uint16_t cbu_portid; /* port id */ 100 uint16_t cbu_messageage; /* current message age */ 101 uint16_t cbu_maxage; /* maximum age */ 102 uint16_t cbu_hellotime; /* hello time */ 103 uint16_t cbu_forwarddelay; /* forwarding delay */ 104 } __packed; 105 106 /* topology change notification bridge protocol data unit */ 107 struct bstp_tbpdu { 108 uint8_t tbu_dsap; /* LLC: destination sap */ 109 uint8_t tbu_ssap; /* LLC: source sap */ 110 uint8_t tbu_ctl; /* LLC: control */ 111 uint16_t tbu_protoid; /* protocol id */ 112 uint8_t tbu_protover; /* protocol version */ 113 uint8_t tbu_bpdutype; /* message type */ 114 } __packed; 115 116 const uint8_t bstp_etheraddr[] = { 0x01, 0x80, 0xc2, 0x00, 0x00, 0x00 }; 117 118 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, CLLADDR(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, char *) + sizeof(*eh), &bpdu, sizeof(bpdu)); 273 274 s = splnet(); 275 bridge_enqueue(sc, ifp, m, 0); 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; 359 struct ether_header *eh; 360 struct mbuf *m; 361 int s; 362 363 KASSERT(bif != NULL); 364 ifp = bif->bif_ifp; 365 if ((ifp->if_flags & IFF_RUNNING) == 0) 366 return; 367 368 MGETHDR(m, M_DONTWAIT, MT_DATA); 369 if (m == NULL) 370 return; 371 372 m->m_pkthdr.rcvif = ifp; 373 m->m_pkthdr.len = sizeof(*eh) + sizeof(bpdu); 374 m->m_len = m->m_pkthdr.len; 375 376 eh = mtod(m, struct ether_header *); 377 378 memcpy(eh->ether_shost, CLLADDR(ifp->if_sadl), ETHER_ADDR_LEN); 379 memcpy(eh->ether_dhost, bstp_etheraddr, ETHER_ADDR_LEN); 380 eh->ether_type = htons(sizeof(bpdu)); 381 382 bpdu.tbu_ssap = bpdu.tbu_dsap = LLC_8021D_LSAP; 383 bpdu.tbu_ctl = LLC_UI; 384 bpdu.tbu_protoid = 0; 385 bpdu.tbu_protover = 0; 386 bpdu.tbu_bpdutype = BSTP_MSGTYPE_TCN; 387 388 memcpy(mtod(m, char *) + sizeof(*eh), &bpdu, sizeof(bpdu)); 389 390 s = splnet(); 391 bridge_enqueue(sc, ifp, m, 0); 392 splx(s); 393 } 394 395 void 396 bstp_configuration_update(struct bridge_softc *sc) 397 { 398 bstp_root_selection(sc); 399 bstp_designated_port_selection(sc); 400 } 401 402 void 403 bstp_root_selection(struct bridge_softc *sc) 404 { 405 struct bridge_iflist *root_port = NULL, *bif; 406 407 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 408 if ((bif->bif_flags & IFBIF_STP) == 0) 409 continue; 410 if (bstp_designated_port(sc, bif)) 411 continue; 412 if (bif->bif_state == BSTP_IFSTATE_DISABLED) 413 continue; 414 if (bif->bif_designated_root >= sc->sc_bridge_id) 415 continue; 416 if (root_port == NULL) 417 goto set_port; 418 419 if (bif->bif_designated_root < root_port->bif_designated_root) 420 goto set_port; 421 if (bif->bif_designated_root > root_port->bif_designated_root) 422 continue; 423 424 if ((bif->bif_designated_cost + bif->bif_path_cost) < 425 (root_port->bif_designated_cost + root_port->bif_path_cost)) 426 goto set_port; 427 if ((bif->bif_designated_cost + bif->bif_path_cost) > 428 (root_port->bif_designated_cost + root_port->bif_path_cost)) 429 continue; 430 431 if (bif->bif_designated_bridge < 432 root_port->bif_designated_bridge) 433 goto set_port; 434 if (bif->bif_designated_bridge > 435 root_port->bif_designated_bridge) 436 continue; 437 438 if (bif->bif_designated_port < root_port->bif_designated_port) 439 goto set_port; 440 if (bif->bif_designated_port > root_port->bif_designated_port) 441 continue; 442 443 if (bif->bif_port_id >= root_port->bif_port_id) 444 continue; 445 set_port: 446 root_port = bif; 447 } 448 449 sc->sc_root_port = root_port; 450 if (root_port == NULL) { 451 sc->sc_designated_root = sc->sc_bridge_id; 452 sc->sc_root_path_cost = 0; 453 } else { 454 sc->sc_designated_root = root_port->bif_designated_root; 455 sc->sc_root_path_cost = root_port->bif_designated_cost + 456 root_port->bif_path_cost; 457 } 458 } 459 460 void 461 bstp_designated_port_selection(struct bridge_softc *sc) 462 { 463 struct bridge_iflist *bif; 464 465 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 466 if ((bif->bif_flags & IFBIF_STP) == 0) 467 continue; 468 if (bstp_designated_port(sc, bif)) 469 goto designated; 470 if (bif->bif_designated_root != sc->sc_designated_root) 471 goto designated; 472 473 if (sc->sc_root_path_cost < bif->bif_designated_cost) 474 goto designated; 475 if (sc->sc_root_path_cost > bif->bif_designated_cost) 476 continue; 477 478 if (sc->sc_bridge_id < bif->bif_designated_bridge) 479 goto designated; 480 if (sc->sc_bridge_id > bif->bif_designated_bridge) 481 continue; 482 483 if (bif->bif_port_id > bif->bif_designated_port) 484 continue; 485 designated: 486 bstp_become_designated_port(sc, bif); 487 } 488 } 489 490 void 491 bstp_become_designated_port(struct bridge_softc *sc, struct bridge_iflist *bif) 492 { 493 bif->bif_designated_root = sc->sc_designated_root; 494 bif->bif_designated_cost = sc->sc_root_path_cost; 495 bif->bif_designated_bridge = sc->sc_bridge_id; 496 bif->bif_designated_port = bif->bif_port_id; 497 } 498 499 void 500 bstp_port_state_selection(struct bridge_softc *sc) 501 { 502 struct bridge_iflist *bif; 503 504 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 505 if ((bif->bif_flags & IFBIF_STP) == 0) 506 continue; 507 if (bif == sc->sc_root_port) { 508 bif->bif_config_pending = 0; 509 bif->bif_topology_change_acknowledge = 0; 510 bstp_make_forwarding(sc, bif); 511 } else if (bstp_designated_port(sc, bif)) { 512 bstp_timer_stop(&bif->bif_message_age_timer); 513 bstp_make_forwarding(sc, bif); 514 } else { 515 bif->bif_config_pending = 0; 516 bif->bif_topology_change_acknowledge = 0; 517 bstp_make_blocking(sc, bif); 518 } 519 } 520 } 521 522 void 523 bstp_make_forwarding(struct bridge_softc *sc, 524 struct bridge_iflist *bif) 525 { 526 if (bif->bif_state == BSTP_IFSTATE_BLOCKING) { 527 bstp_set_port_state(bif, BSTP_IFSTATE_LISTENING); 528 bstp_timer_start(&bif->bif_forward_delay_timer, 0); 529 } 530 } 531 532 void 533 bstp_make_blocking(struct bridge_softc *sc, struct bridge_iflist *bif) 534 { 535 if ((bif->bif_state != BSTP_IFSTATE_DISABLED) && 536 (bif->bif_state != BSTP_IFSTATE_BLOCKING)) { 537 if ((bif->bif_state == BSTP_IFSTATE_FORWARDING) || 538 (bif->bif_state == BSTP_IFSTATE_LEARNING)) { 539 if (bif->bif_change_detection_enabled) { 540 bstp_topology_change_detection(sc); 541 } 542 } 543 bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING); 544 bstp_timer_stop(&bif->bif_forward_delay_timer); 545 } 546 } 547 548 void 549 bstp_set_port_state(struct bridge_iflist *bif, uint8_t state) 550 { 551 bif->bif_state = state; 552 } 553 554 void 555 bstp_topology_change_detection(struct bridge_softc *sc) 556 { 557 if (bstp_root_bridge(sc)) { 558 sc->sc_topology_change = 1; 559 bstp_timer_start(&sc->sc_topology_change_timer, 0); 560 } else if (!sc->sc_topology_change_detected) { 561 bstp_transmit_tcn(sc); 562 bstp_timer_start(&sc->sc_tcn_timer, 0); 563 } 564 sc->sc_topology_change_detected = 1; 565 } 566 567 void 568 bstp_topology_change_acknowledged(struct bridge_softc *sc) 569 { 570 sc->sc_topology_change_detected = 0; 571 bstp_timer_stop(&sc->sc_tcn_timer); 572 } 573 574 void 575 bstp_acknowledge_topology_change(struct bridge_softc *sc, 576 struct bridge_iflist *bif) 577 { 578 bif->bif_topology_change_acknowledge = 1; 579 bstp_transmit_config(sc, bif); 580 } 581 582 struct mbuf * 583 bstp_input(struct bridge_softc *sc, struct bridge_iflist *bif, struct mbuf *m) 584 { 585 struct ether_header *eh; 586 struct bstp_tbpdu tpdu; 587 struct bstp_cbpdu cpdu; 588 struct bstp_config_unit cu; 589 struct bstp_tcn_unit tu; 590 uint16_t len; 591 592 eh = mtod(m, struct ether_header *); 593 594 if ((bif->bif_flags & IFBIF_STP) == 0) 595 return (m); 596 597 len = ntohs(eh->ether_type); 598 if (len < sizeof(tpdu)) 599 goto out; 600 601 m_adj(m, ETHER_HDR_LEN); 602 603 if (m->m_pkthdr.len > len) 604 m_adj(m, len - m->m_pkthdr.len); 605 if (m->m_len < sizeof(tpdu) && 606 (m = m_pullup(m, sizeof(tpdu))) == NULL) 607 goto out; 608 609 memcpy(&tpdu, mtod(m, void *), sizeof(tpdu)); 610 611 if (tpdu.tbu_dsap != LLC_8021D_LSAP || 612 tpdu.tbu_ssap != LLC_8021D_LSAP || 613 tpdu.tbu_ctl != LLC_UI) 614 goto out; 615 if (tpdu.tbu_protoid != 0 || tpdu.tbu_protover != 0) 616 goto out; 617 618 switch (tpdu.tbu_bpdutype) { 619 case BSTP_MSGTYPE_TCN: 620 tu.tu_message_type = tpdu.tbu_bpdutype; 621 bstp_received_tcn_bpdu(sc, bif, &tu); 622 break; 623 case BSTP_MSGTYPE_CFG: 624 if (m->m_len < sizeof(cpdu) && 625 (m = m_pullup(m, sizeof(cpdu))) == NULL) 626 goto out; 627 memcpy(&cpdu, mtod(m, void *), sizeof(cpdu)); 628 629 cu.cu_rootid = 630 (((uint64_t)ntohs(cpdu.cbu_rootpri)) << 48) | 631 (((uint64_t)cpdu.cbu_rootaddr[0]) << 40) | 632 (((uint64_t)cpdu.cbu_rootaddr[1]) << 32) | 633 (((uint64_t)cpdu.cbu_rootaddr[2]) << 24) | 634 (((uint64_t)cpdu.cbu_rootaddr[3]) << 16) | 635 (((uint64_t)cpdu.cbu_rootaddr[4]) << 8) | 636 (((uint64_t)cpdu.cbu_rootaddr[5]) << 0); 637 638 cu.cu_bridge_id = 639 (((uint64_t)ntohs(cpdu.cbu_bridgepri)) << 48) | 640 (((uint64_t)cpdu.cbu_bridgeaddr[0]) << 40) | 641 (((uint64_t)cpdu.cbu_bridgeaddr[1]) << 32) | 642 (((uint64_t)cpdu.cbu_bridgeaddr[2]) << 24) | 643 (((uint64_t)cpdu.cbu_bridgeaddr[3]) << 16) | 644 (((uint64_t)cpdu.cbu_bridgeaddr[4]) << 8) | 645 (((uint64_t)cpdu.cbu_bridgeaddr[5]) << 0); 646 647 cu.cu_root_path_cost = ntohl(cpdu.cbu_rootpathcost); 648 cu.cu_message_age = ntohs(cpdu.cbu_messageage); 649 cu.cu_max_age = ntohs(cpdu.cbu_maxage); 650 cu.cu_hello_time = ntohs(cpdu.cbu_hellotime); 651 cu.cu_forward_delay = ntohs(cpdu.cbu_forwarddelay); 652 cu.cu_port_id = ntohs(cpdu.cbu_portid); 653 cu.cu_message_type = cpdu.cbu_bpdutype; 654 cu.cu_topology_change_acknowledgment = 655 (cpdu.cbu_flags & BSTP_FLAG_TCA) ? 1 : 0; 656 cu.cu_topology_change = 657 (cpdu.cbu_flags & BSTP_FLAG_TC) ? 1 : 0; 658 bstp_received_config_bpdu(sc, bif, &cu); 659 break; 660 default: 661 goto out; 662 } 663 664 out: 665 if (m) 666 m_freem(m); 667 return (NULL); 668 } 669 670 void 671 bstp_received_config_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif, 672 struct bstp_config_unit *cu) 673 { 674 int root; 675 676 root = bstp_root_bridge(sc); 677 678 if (bif->bif_state != BSTP_IFSTATE_DISABLED) { 679 if (bstp_supersedes_port_info(sc, bif, cu)) { 680 bstp_record_config_information(sc, bif, cu); 681 bstp_configuration_update(sc); 682 bstp_port_state_selection(sc); 683 684 if ((bstp_root_bridge(sc) == 0) && root) { 685 bstp_timer_stop(&sc->sc_hello_timer); 686 687 if (sc->sc_topology_change_detected) { 688 bstp_timer_stop( 689 &sc->sc_topology_change_timer); 690 bstp_transmit_tcn(sc); 691 bstp_timer_start(&sc->sc_tcn_timer, 0); 692 } 693 } 694 695 if (bif == sc->sc_root_port) { 696 bstp_record_config_timeout_values(sc, cu); 697 bstp_config_bpdu_generation(sc); 698 699 if (cu->cu_topology_change_acknowledgment) 700 bstp_topology_change_acknowledged(sc); 701 } 702 } else if (bstp_designated_port(sc, bif)) 703 bstp_transmit_config(sc, bif); 704 } 705 } 706 707 void 708 bstp_received_tcn_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif, 709 struct bstp_tcn_unit *tcn) 710 { 711 if (bif->bif_state != BSTP_IFSTATE_DISABLED && 712 bstp_designated_port(sc, bif)) { 713 bstp_topology_change_detection(sc); 714 bstp_acknowledge_topology_change(sc, bif); 715 } 716 } 717 718 void 719 bstp_hello_timer_expiry(struct bridge_softc *sc) 720 { 721 bstp_config_bpdu_generation(sc); 722 bstp_timer_start(&sc->sc_hello_timer, 0); 723 } 724 725 void 726 bstp_message_age_timer_expiry(struct bridge_softc *sc, 727 struct bridge_iflist *bif) 728 { 729 int root; 730 731 root = bstp_root_bridge(sc); 732 bstp_become_designated_port(sc, bif); 733 bstp_configuration_update(sc); 734 bstp_port_state_selection(sc); 735 736 if ((bstp_root_bridge(sc)) && (root == 0)) { 737 sc->sc_max_age = sc->sc_bridge_max_age; 738 sc->sc_hello_time = sc->sc_bridge_hello_time; 739 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 740 741 bstp_topology_change_detection(sc); 742 bstp_timer_stop(&sc->sc_tcn_timer); 743 bstp_config_bpdu_generation(sc); 744 bstp_timer_start(&sc->sc_hello_timer, 0); 745 } 746 } 747 748 void 749 bstp_forward_delay_timer_expiry(struct bridge_softc *sc, 750 struct bridge_iflist *bif) 751 { 752 if (bif->bif_state == BSTP_IFSTATE_LISTENING) { 753 bstp_set_port_state(bif, BSTP_IFSTATE_LEARNING); 754 bstp_timer_start(&bif->bif_forward_delay_timer, 0); 755 } else if (bif->bif_state == BSTP_IFSTATE_LEARNING) { 756 bstp_set_port_state(bif, BSTP_IFSTATE_FORWARDING); 757 if (bstp_designated_for_some_port(sc) && 758 bif->bif_change_detection_enabled) 759 bstp_topology_change_detection(sc); 760 } 761 } 762 763 int 764 bstp_designated_for_some_port(struct bridge_softc *sc) 765 { 766 767 struct bridge_iflist *bif; 768 769 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 770 if ((bif->bif_flags & IFBIF_STP) == 0) 771 continue; 772 if (bif->bif_designated_bridge == sc->sc_bridge_id) 773 return (1); 774 } 775 return (0); 776 } 777 778 void 779 bstp_tcn_timer_expiry(struct bridge_softc *sc) 780 { 781 bstp_transmit_tcn(sc); 782 bstp_timer_start(&sc->sc_tcn_timer, 0); 783 } 784 785 void 786 bstp_topology_change_timer_expiry(struct bridge_softc *sc) 787 { 788 sc->sc_topology_change_detected = 0; 789 sc->sc_topology_change = 0; 790 } 791 792 void 793 bstp_hold_timer_expiry(struct bridge_softc *sc, struct bridge_iflist *bif) 794 { 795 if (bif->bif_config_pending) 796 bstp_transmit_config(sc, bif); 797 } 798 799 void 800 bstp_initialization(struct bridge_softc *sc) 801 { 802 struct bridge_iflist *bif, *mif; 803 804 mif = NULL; 805 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 806 if ((bif->bif_flags & IFBIF_STP) == 0) 807 continue; 808 if (bif->bif_ifp->if_type != IFT_ETHER) 809 continue; 810 bif->bif_port_id = (bif->bif_priority << 8) | 811 (bif->bif_ifp->if_index & 0xff); 812 813 if (mif == NULL) { 814 mif = bif; 815 continue; 816 } 817 if (memcmp(CLLADDR(bif->bif_ifp->if_sadl), 818 CLLADDR(mif->bif_ifp->if_sadl), ETHER_ADDR_LEN) < 0) { 819 mif = bif; 820 continue; 821 } 822 } 823 if (mif == NULL) { 824 bstp_stop(sc); 825 return; 826 } 827 828 sc->sc_bridge_id = 829 (((uint64_t)sc->sc_bridge_priority) << 48) | 830 (((uint64_t)(uint8_t)CLLADDR(mif->bif_ifp->if_sadl)[0]) << 40) | 831 (((uint64_t)(uint8_t)CLLADDR(mif->bif_ifp->if_sadl)[1]) << 32) | 832 (((uint64_t)(uint8_t)CLLADDR(mif->bif_ifp->if_sadl)[2]) << 24) | 833 (((uint64_t)(uint8_t)CLLADDR(mif->bif_ifp->if_sadl)[3]) << 16) | 834 (((uint64_t)(uint8_t)CLLADDR(mif->bif_ifp->if_sadl)[4]) << 8) | 835 (((uint64_t)(uint8_t)CLLADDR(mif->bif_ifp->if_sadl)[5]) << 0); 836 837 sc->sc_designated_root = sc->sc_bridge_id; 838 sc->sc_root_path_cost = 0; 839 sc->sc_root_port = NULL; 840 841 sc->sc_max_age = sc->sc_bridge_max_age; 842 sc->sc_hello_time = sc->sc_bridge_hello_time; 843 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 844 sc->sc_topology_change_detected = 0; 845 sc->sc_topology_change = 0; 846 bstp_timer_stop(&sc->sc_tcn_timer); 847 bstp_timer_stop(&sc->sc_topology_change_timer); 848 849 if (callout_pending(&sc->sc_bstpcallout) == 0) 850 callout_reset(&sc->sc_bstpcallout, hz, 851 bstp_tick, sc); 852 853 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 854 if (bif->bif_flags & IFBIF_STP) 855 bstp_enable_port(sc, bif); 856 else 857 bstp_disable_port(sc, bif); 858 } 859 860 bstp_port_state_selection(sc); 861 bstp_config_bpdu_generation(sc); 862 bstp_timer_start(&sc->sc_hello_timer, 0); 863 } 864 865 void 866 bstp_stop(struct bridge_softc *sc) 867 { 868 struct bridge_iflist *bif; 869 870 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 871 bstp_set_port_state(bif, BSTP_IFSTATE_DISABLED); 872 bstp_timer_stop(&bif->bif_hold_timer); 873 bstp_timer_stop(&bif->bif_message_age_timer); 874 bstp_timer_stop(&bif->bif_forward_delay_timer); 875 } 876 877 callout_stop(&sc->sc_bstpcallout); 878 879 bstp_timer_stop(&sc->sc_topology_change_timer); 880 bstp_timer_stop(&sc->sc_tcn_timer); 881 bstp_timer_stop(&sc->sc_hello_timer); 882 883 } 884 885 void 886 bstp_initialize_port(struct bridge_softc *sc, struct bridge_iflist *bif) 887 { 888 bstp_become_designated_port(sc, bif); 889 bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING); 890 bif->bif_topology_change_acknowledge = 0; 891 bif->bif_config_pending = 0; 892 bif->bif_change_detection_enabled = 1; 893 bstp_timer_stop(&bif->bif_message_age_timer); 894 bstp_timer_stop(&bif->bif_forward_delay_timer); 895 bstp_timer_stop(&bif->bif_hold_timer); 896 } 897 898 void 899 bstp_enable_port(struct bridge_softc *sc, struct bridge_iflist *bif) 900 { 901 bstp_initialize_port(sc, bif); 902 bstp_port_state_selection(sc); 903 } 904 905 void 906 bstp_disable_port(struct bridge_softc *sc, struct bridge_iflist *bif) 907 { 908 int root; 909 910 root = bstp_root_bridge(sc); 911 bstp_become_designated_port(sc, bif); 912 bstp_set_port_state(bif, BSTP_IFSTATE_DISABLED); 913 bif->bif_topology_change_acknowledge = 0; 914 bif->bif_config_pending = 0; 915 bstp_timer_stop(&bif->bif_message_age_timer); 916 bstp_timer_stop(&bif->bif_forward_delay_timer); 917 bstp_configuration_update(sc); 918 bstp_port_state_selection(sc); 919 920 if (bstp_root_bridge(sc) && (root == 0)) { 921 sc->sc_max_age = sc->sc_bridge_max_age; 922 sc->sc_hello_time = sc->sc_bridge_hello_time; 923 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 924 925 bstp_topology_change_detection(sc); 926 bstp_timer_stop(&sc->sc_tcn_timer); 927 bstp_config_bpdu_generation(sc); 928 bstp_timer_start(&sc->sc_hello_timer, 0); 929 } 930 } 931 932 void 933 bstp_set_bridge_priority(struct bridge_softc *sc, uint64_t new_bridge_id) 934 { 935 struct bridge_iflist *bif; 936 int root; 937 938 root = bstp_root_bridge(sc); 939 940 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 941 if ((bif->bif_flags & IFBIF_STP) == 0) 942 continue; 943 if (bstp_designated_port(sc, bif)) 944 bif->bif_designated_bridge = new_bridge_id; 945 } 946 947 sc->sc_bridge_id = new_bridge_id; 948 949 bstp_configuration_update(sc); 950 bstp_port_state_selection(sc); 951 952 if (bstp_root_bridge(sc) && (root == 0)) { 953 sc->sc_max_age = sc->sc_bridge_max_age; 954 sc->sc_hello_time = sc->sc_bridge_hello_time; 955 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 956 957 bstp_topology_change_detection(sc); 958 bstp_timer_stop(&sc->sc_tcn_timer); 959 bstp_config_bpdu_generation(sc); 960 bstp_timer_start(&sc->sc_hello_timer, 0); 961 } 962 } 963 964 void 965 bstp_set_port_priority(struct bridge_softc *sc, struct bridge_iflist *bif, 966 uint16_t new_port_id) 967 { 968 if (bstp_designated_port(sc, bif)) 969 bif->bif_designated_port = new_port_id; 970 971 bif->bif_port_id = new_port_id; 972 973 if ((sc->sc_bridge_id == bif->bif_designated_bridge) && 974 (bif->bif_port_id < bif->bif_designated_port)) { 975 bstp_become_designated_port(sc, bif); 976 bstp_port_state_selection(sc); 977 } 978 } 979 980 void 981 bstp_set_path_cost(struct bridge_softc *sc, struct bridge_iflist *bif, 982 uint32_t path_cost) 983 { 984 bif->bif_path_cost = path_cost; 985 bstp_configuration_update(sc); 986 bstp_port_state_selection(sc); 987 } 988 989 void 990 bstp_enable_change_detection(struct bridge_iflist *bif) 991 { 992 bif->bif_change_detection_enabled = 1; 993 } 994 995 void 996 bstp_disable_change_detection(struct bridge_iflist *bif) 997 { 998 bif->bif_change_detection_enabled = 0; 999 } 1000 1001 void 1002 bstp_ifupdstatus(struct bridge_softc *sc, struct bridge_iflist *bif) 1003 { 1004 struct ifnet *ifp = bif->bif_ifp; 1005 1006 if (ifp->if_flags & IFF_UP) { 1007 switch (ifp->if_link_state) { 1008 case LINK_STATE_UNKNOWN: 1009 /* 1010 * Just enable the port if the link state is 1011 * unknown. 1012 */ 1013 if (bif->bif_state == BSTP_IFSTATE_DISABLED) 1014 bstp_enable_port(sc, bif); 1015 break; 1016 1017 case LINK_STATE_UP: 1018 if (bif->bif_state == BSTP_IFSTATE_DISABLED) 1019 bstp_enable_port(sc, bif); 1020 break; 1021 1022 case LINK_STATE_DOWN: 1023 if (bif->bif_state != BSTP_IFSTATE_DISABLED) 1024 bstp_disable_port(sc, bif); 1025 break; 1026 } 1027 return; 1028 } 1029 1030 if (bif->bif_state != BSTP_IFSTATE_DISABLED) 1031 bstp_disable_port(sc, bif); 1032 } 1033 1034 void 1035 bstp_tick(void *arg) 1036 { 1037 struct bridge_softc *sc = arg; 1038 struct bridge_iflist *bif; 1039 int s; 1040 1041 s = splnet(); 1042 1043 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 1044 if ((bif->bif_flags & IFBIF_STP) == 0) 1045 continue; 1046 /* 1047 * XXX This can cause a lag in "link does away" 1048 * XXX and "spanning tree gets updated". We need 1049 * XXX come sort of callback from the link state 1050 * XXX update code to kick spanning tree. 1051 * XXX --thorpej@NetBSD.org 1052 */ 1053 bstp_ifupdstatus(sc, bif); 1054 } 1055 1056 if (bstp_timer_expired(&sc->sc_hello_timer, sc->sc_hello_time)) 1057 bstp_hello_timer_expiry(sc); 1058 1059 if (bstp_timer_expired(&sc->sc_tcn_timer, sc->sc_bridge_hello_time)) 1060 bstp_tcn_timer_expiry(sc); 1061 1062 if (bstp_timer_expired(&sc->sc_topology_change_timer, 1063 sc->sc_topology_change_time)) 1064 bstp_topology_change_timer_expiry(sc); 1065 1066 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 1067 if ((bif->bif_flags & IFBIF_STP) == 0) 1068 continue; 1069 if (bstp_timer_expired(&bif->bif_message_age_timer, 1070 sc->sc_max_age)) 1071 bstp_message_age_timer_expiry(sc, bif); 1072 } 1073 1074 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 1075 if ((bif->bif_flags & IFBIF_STP) == 0) 1076 continue; 1077 if (bstp_timer_expired(&bif->bif_forward_delay_timer, 1078 sc->sc_forward_delay)) 1079 bstp_forward_delay_timer_expiry(sc, bif); 1080 1081 if (bstp_timer_expired(&bif->bif_hold_timer, 1082 sc->sc_hold_time)) 1083 bstp_hold_timer_expiry(sc, bif); 1084 } 1085 1086 if (sc->sc_if.if_flags & IFF_RUNNING) 1087 callout_reset(&sc->sc_bstpcallout, hz, bstp_tick, sc); 1088 1089 splx(s); 1090 } 1091 1092 void 1093 bstp_timer_start(struct bridge_timer *t, uint16_t v) 1094 { 1095 t->value = v; 1096 t->active = 1; 1097 } 1098 1099 void 1100 bstp_timer_stop(struct bridge_timer *t) 1101 { 1102 t->value = 0; 1103 t->active = 0; 1104 } 1105 1106 int 1107 bstp_timer_expired(struct bridge_timer *t, uint16_t v) 1108 { 1109 if (t->active == 0) 1110 return (0); 1111 t->value += BSTP_TICK_VAL; 1112 if (t->value >= v) { 1113 bstp_timer_stop(t); 1114 return (1); 1115 } 1116 return (0); 1117 1118 } 1119