1 /* $NetBSD: bridgestp.c,v 1.13 2007/12/25 18:33:44 perry 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.13 2007/12/25 18:33:44 perry 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 ifnet *ifp, struct mbuf *m) 584 { 585 struct bridge_softc *sc = ifp->if_bridge; 586 struct bridge_iflist *bif = NULL; 587 struct ether_header *eh; 588 struct bstp_tbpdu tpdu; 589 struct bstp_cbpdu cpdu; 590 struct bstp_config_unit cu; 591 struct bstp_tcn_unit tu; 592 uint16_t len; 593 594 eh = mtod(m, struct ether_header *); 595 596 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 597 if ((bif->bif_flags & IFBIF_STP) == 0) 598 continue; 599 if (bif->bif_ifp == ifp) 600 break; 601 } 602 if (bif == NULL) 603 goto out; 604 605 len = ntohs(eh->ether_type); 606 if (len < sizeof(tpdu)) 607 goto out; 608 609 m_adj(m, ETHER_HDR_LEN); 610 611 if (m->m_pkthdr.len > len) 612 m_adj(m, len - m->m_pkthdr.len); 613 if (m->m_len < sizeof(tpdu) && 614 (m = m_pullup(m, sizeof(tpdu))) == NULL) 615 goto out; 616 617 memcpy(&tpdu, mtod(m, void *), sizeof(tpdu)); 618 619 if (tpdu.tbu_dsap != LLC_8021D_LSAP || 620 tpdu.tbu_ssap != LLC_8021D_LSAP || 621 tpdu.tbu_ctl != LLC_UI) 622 goto out; 623 if (tpdu.tbu_protoid != 0 || tpdu.tbu_protover != 0) 624 goto out; 625 626 switch (tpdu.tbu_bpdutype) { 627 case BSTP_MSGTYPE_TCN: 628 tu.tu_message_type = tpdu.tbu_bpdutype; 629 bstp_received_tcn_bpdu(sc, bif, &tu); 630 break; 631 case BSTP_MSGTYPE_CFG: 632 if (m->m_len < sizeof(cpdu) && 633 (m = m_pullup(m, sizeof(cpdu))) == NULL) 634 goto out; 635 memcpy(&cpdu, mtod(m, void *), sizeof(cpdu)); 636 637 cu.cu_rootid = 638 (((uint64_t)ntohs(cpdu.cbu_rootpri)) << 48) | 639 (((uint64_t)cpdu.cbu_rootaddr[0]) << 40) | 640 (((uint64_t)cpdu.cbu_rootaddr[1]) << 32) | 641 (((uint64_t)cpdu.cbu_rootaddr[2]) << 24) | 642 (((uint64_t)cpdu.cbu_rootaddr[3]) << 16) | 643 (((uint64_t)cpdu.cbu_rootaddr[4]) << 8) | 644 (((uint64_t)cpdu.cbu_rootaddr[5]) << 0); 645 646 cu.cu_bridge_id = 647 (((uint64_t)ntohs(cpdu.cbu_bridgepri)) << 48) | 648 (((uint64_t)cpdu.cbu_bridgeaddr[0]) << 40) | 649 (((uint64_t)cpdu.cbu_bridgeaddr[1]) << 32) | 650 (((uint64_t)cpdu.cbu_bridgeaddr[2]) << 24) | 651 (((uint64_t)cpdu.cbu_bridgeaddr[3]) << 16) | 652 (((uint64_t)cpdu.cbu_bridgeaddr[4]) << 8) | 653 (((uint64_t)cpdu.cbu_bridgeaddr[5]) << 0); 654 655 cu.cu_root_path_cost = ntohl(cpdu.cbu_rootpathcost); 656 cu.cu_message_age = ntohs(cpdu.cbu_messageage); 657 cu.cu_max_age = ntohs(cpdu.cbu_maxage); 658 cu.cu_hello_time = ntohs(cpdu.cbu_hellotime); 659 cu.cu_forward_delay = ntohs(cpdu.cbu_forwarddelay); 660 cu.cu_port_id = ntohs(cpdu.cbu_portid); 661 cu.cu_message_type = cpdu.cbu_bpdutype; 662 cu.cu_topology_change_acknowledgment = 663 (cpdu.cbu_flags & BSTP_FLAG_TCA) ? 1 : 0; 664 cu.cu_topology_change = 665 (cpdu.cbu_flags & BSTP_FLAG_TC) ? 1 : 0; 666 bstp_received_config_bpdu(sc, bif, &cu); 667 break; 668 default: 669 goto out; 670 } 671 672 out: 673 if (m) 674 m_freem(m); 675 return (NULL); 676 } 677 678 void 679 bstp_received_config_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif, 680 struct bstp_config_unit *cu) 681 { 682 int root; 683 684 root = bstp_root_bridge(sc); 685 686 if (bif->bif_state != BSTP_IFSTATE_DISABLED) { 687 if (bstp_supersedes_port_info(sc, bif, cu)) { 688 bstp_record_config_information(sc, bif, cu); 689 bstp_configuration_update(sc); 690 bstp_port_state_selection(sc); 691 692 if ((bstp_root_bridge(sc) == 0) && root) { 693 bstp_timer_stop(&sc->sc_hello_timer); 694 695 if (sc->sc_topology_change_detected) { 696 bstp_timer_stop( 697 &sc->sc_topology_change_timer); 698 bstp_transmit_tcn(sc); 699 bstp_timer_start(&sc->sc_tcn_timer, 0); 700 } 701 } 702 703 if (bif == sc->sc_root_port) { 704 bstp_record_config_timeout_values(sc, cu); 705 bstp_config_bpdu_generation(sc); 706 707 if (cu->cu_topology_change_acknowledgment) 708 bstp_topology_change_acknowledged(sc); 709 } 710 } else if (bstp_designated_port(sc, bif)) 711 bstp_transmit_config(sc, bif); 712 } 713 } 714 715 void 716 bstp_received_tcn_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif, 717 struct bstp_tcn_unit *tcn) 718 { 719 if (bif->bif_state != BSTP_IFSTATE_DISABLED && 720 bstp_designated_port(sc, bif)) { 721 bstp_topology_change_detection(sc); 722 bstp_acknowledge_topology_change(sc, bif); 723 } 724 } 725 726 void 727 bstp_hello_timer_expiry(struct bridge_softc *sc) 728 { 729 bstp_config_bpdu_generation(sc); 730 bstp_timer_start(&sc->sc_hello_timer, 0); 731 } 732 733 void 734 bstp_message_age_timer_expiry(struct bridge_softc *sc, 735 struct bridge_iflist *bif) 736 { 737 int root; 738 739 root = bstp_root_bridge(sc); 740 bstp_become_designated_port(sc, bif); 741 bstp_configuration_update(sc); 742 bstp_port_state_selection(sc); 743 744 if ((bstp_root_bridge(sc)) && (root == 0)) { 745 sc->sc_max_age = sc->sc_bridge_max_age; 746 sc->sc_hello_time = sc->sc_bridge_hello_time; 747 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 748 749 bstp_topology_change_detection(sc); 750 bstp_timer_stop(&sc->sc_tcn_timer); 751 bstp_config_bpdu_generation(sc); 752 bstp_timer_start(&sc->sc_hello_timer, 0); 753 } 754 } 755 756 void 757 bstp_forward_delay_timer_expiry(struct bridge_softc *sc, 758 struct bridge_iflist *bif) 759 { 760 if (bif->bif_state == BSTP_IFSTATE_LISTENING) { 761 bstp_set_port_state(bif, BSTP_IFSTATE_LEARNING); 762 bstp_timer_start(&bif->bif_forward_delay_timer, 0); 763 } else if (bif->bif_state == BSTP_IFSTATE_LEARNING) { 764 bstp_set_port_state(bif, BSTP_IFSTATE_FORWARDING); 765 if (bstp_designated_for_some_port(sc) && 766 bif->bif_change_detection_enabled) 767 bstp_topology_change_detection(sc); 768 } 769 } 770 771 int 772 bstp_designated_for_some_port(struct bridge_softc *sc) 773 { 774 775 struct bridge_iflist *bif; 776 777 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 778 if ((bif->bif_flags & IFBIF_STP) == 0) 779 continue; 780 if (bif->bif_designated_bridge == sc->sc_bridge_id) 781 return (1); 782 } 783 return (0); 784 } 785 786 void 787 bstp_tcn_timer_expiry(struct bridge_softc *sc) 788 { 789 bstp_transmit_tcn(sc); 790 bstp_timer_start(&sc->sc_tcn_timer, 0); 791 } 792 793 void 794 bstp_topology_change_timer_expiry(struct bridge_softc *sc) 795 { 796 sc->sc_topology_change_detected = 0; 797 sc->sc_topology_change = 0; 798 } 799 800 void 801 bstp_hold_timer_expiry(struct bridge_softc *sc, struct bridge_iflist *bif) 802 { 803 if (bif->bif_config_pending) 804 bstp_transmit_config(sc, bif); 805 } 806 807 void 808 bstp_initialization(struct bridge_softc *sc) 809 { 810 struct bridge_iflist *bif, *mif; 811 812 mif = NULL; 813 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 814 if ((bif->bif_flags & IFBIF_STP) == 0) 815 continue; 816 if (bif->bif_ifp->if_type != IFT_ETHER) 817 continue; 818 bif->bif_port_id = (bif->bif_priority << 8) | 819 (bif->bif_ifp->if_index & 0xff); 820 821 if (mif == NULL) { 822 mif = bif; 823 continue; 824 } 825 if (memcmp(CLLADDR(bif->bif_ifp->if_sadl), 826 CLLADDR(mif->bif_ifp->if_sadl), ETHER_ADDR_LEN) < 0) { 827 mif = bif; 828 continue; 829 } 830 } 831 if (mif == NULL) { 832 bstp_stop(sc); 833 return; 834 } 835 836 sc->sc_bridge_id = 837 (((uint64_t)sc->sc_bridge_priority) << 48) | 838 (((uint64_t)CLLADDR(mif->bif_ifp->if_sadl)[0]) << 40) | 839 (((uint64_t)CLLADDR(mif->bif_ifp->if_sadl)[1]) << 32) | 840 (CLLADDR(mif->bif_ifp->if_sadl)[2] << 24) | 841 (CLLADDR(mif->bif_ifp->if_sadl)[3] << 16) | 842 (CLLADDR(mif->bif_ifp->if_sadl)[4] << 8) | 843 (CLLADDR(mif->bif_ifp->if_sadl)[5]); 844 845 sc->sc_designated_root = sc->sc_bridge_id; 846 sc->sc_root_path_cost = 0; 847 sc->sc_root_port = NULL; 848 849 sc->sc_max_age = sc->sc_bridge_max_age; 850 sc->sc_hello_time = sc->sc_bridge_hello_time; 851 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 852 sc->sc_topology_change_detected = 0; 853 sc->sc_topology_change = 0; 854 bstp_timer_stop(&sc->sc_tcn_timer); 855 bstp_timer_stop(&sc->sc_topology_change_timer); 856 857 if (callout_pending(&sc->sc_bstpcallout) == 0) 858 callout_reset(&sc->sc_bstpcallout, hz, 859 bstp_tick, sc); 860 861 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 862 if (bif->bif_flags & IFBIF_STP) 863 bstp_enable_port(sc, bif); 864 else 865 bstp_disable_port(sc, bif); 866 } 867 868 bstp_port_state_selection(sc); 869 bstp_config_bpdu_generation(sc); 870 bstp_timer_start(&sc->sc_hello_timer, 0); 871 } 872 873 void 874 bstp_stop(struct bridge_softc *sc) 875 { 876 struct bridge_iflist *bif; 877 878 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 879 bstp_set_port_state(bif, BSTP_IFSTATE_DISABLED); 880 bstp_timer_stop(&bif->bif_hold_timer); 881 bstp_timer_stop(&bif->bif_message_age_timer); 882 bstp_timer_stop(&bif->bif_forward_delay_timer); 883 } 884 885 callout_stop(&sc->sc_bstpcallout); 886 887 bstp_timer_stop(&sc->sc_topology_change_timer); 888 bstp_timer_stop(&sc->sc_tcn_timer); 889 bstp_timer_stop(&sc->sc_hello_timer); 890 891 } 892 893 void 894 bstp_initialize_port(struct bridge_softc *sc, struct bridge_iflist *bif) 895 { 896 bstp_become_designated_port(sc, bif); 897 bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING); 898 bif->bif_topology_change_acknowledge = 0; 899 bif->bif_config_pending = 0; 900 bif->bif_change_detection_enabled = 1; 901 bstp_timer_stop(&bif->bif_message_age_timer); 902 bstp_timer_stop(&bif->bif_forward_delay_timer); 903 bstp_timer_stop(&bif->bif_hold_timer); 904 } 905 906 void 907 bstp_enable_port(struct bridge_softc *sc, struct bridge_iflist *bif) 908 { 909 bstp_initialize_port(sc, bif); 910 bstp_port_state_selection(sc); 911 } 912 913 void 914 bstp_disable_port(struct bridge_softc *sc, struct bridge_iflist *bif) 915 { 916 int root; 917 918 root = bstp_root_bridge(sc); 919 bstp_become_designated_port(sc, bif); 920 bstp_set_port_state(bif, BSTP_IFSTATE_DISABLED); 921 bif->bif_topology_change_acknowledge = 0; 922 bif->bif_config_pending = 0; 923 bstp_timer_stop(&bif->bif_message_age_timer); 924 bstp_timer_stop(&bif->bif_forward_delay_timer); 925 bstp_configuration_update(sc); 926 bstp_port_state_selection(sc); 927 928 if (bstp_root_bridge(sc) && (root == 0)) { 929 sc->sc_max_age = sc->sc_bridge_max_age; 930 sc->sc_hello_time = sc->sc_bridge_hello_time; 931 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 932 933 bstp_topology_change_detection(sc); 934 bstp_timer_stop(&sc->sc_tcn_timer); 935 bstp_config_bpdu_generation(sc); 936 bstp_timer_start(&sc->sc_hello_timer, 0); 937 } 938 } 939 940 void 941 bstp_set_bridge_priority(struct bridge_softc *sc, uint64_t new_bridge_id) 942 { 943 struct bridge_iflist *bif; 944 int root; 945 946 root = bstp_root_bridge(sc); 947 948 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 949 if ((bif->bif_flags & IFBIF_STP) == 0) 950 continue; 951 if (bstp_designated_port(sc, bif)) 952 bif->bif_designated_bridge = new_bridge_id; 953 } 954 955 sc->sc_bridge_id = new_bridge_id; 956 957 bstp_configuration_update(sc); 958 bstp_port_state_selection(sc); 959 960 if (bstp_root_bridge(sc) && (root == 0)) { 961 sc->sc_max_age = sc->sc_bridge_max_age; 962 sc->sc_hello_time = sc->sc_bridge_hello_time; 963 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 964 965 bstp_topology_change_detection(sc); 966 bstp_timer_stop(&sc->sc_tcn_timer); 967 bstp_config_bpdu_generation(sc); 968 bstp_timer_start(&sc->sc_hello_timer, 0); 969 } 970 } 971 972 void 973 bstp_set_port_priority(struct bridge_softc *sc, struct bridge_iflist *bif, 974 uint16_t new_port_id) 975 { 976 if (bstp_designated_port(sc, bif)) 977 bif->bif_designated_port = new_port_id; 978 979 bif->bif_port_id = new_port_id; 980 981 if ((sc->sc_bridge_id == bif->bif_designated_bridge) && 982 (bif->bif_port_id < bif->bif_designated_port)) { 983 bstp_become_designated_port(sc, bif); 984 bstp_port_state_selection(sc); 985 } 986 } 987 988 void 989 bstp_set_path_cost(struct bridge_softc *sc, struct bridge_iflist *bif, 990 uint32_t path_cost) 991 { 992 bif->bif_path_cost = path_cost; 993 bstp_configuration_update(sc); 994 bstp_port_state_selection(sc); 995 } 996 997 void 998 bstp_enable_change_detection(struct bridge_iflist *bif) 999 { 1000 bif->bif_change_detection_enabled = 1; 1001 } 1002 1003 void 1004 bstp_disable_change_detection(struct bridge_iflist *bif) 1005 { 1006 bif->bif_change_detection_enabled = 0; 1007 } 1008 1009 void 1010 bstp_ifupdstatus(struct bridge_softc *sc, struct bridge_iflist *bif) 1011 { 1012 struct ifnet *ifp = bif->bif_ifp; 1013 1014 if (ifp->if_flags & IFF_UP) { 1015 switch (ifp->if_link_state) { 1016 case LINK_STATE_UNKNOWN: 1017 /* 1018 * Just enable the port if the link state is 1019 * unknown. 1020 */ 1021 if (bif->bif_state == BSTP_IFSTATE_DISABLED) 1022 bstp_enable_port(sc, bif); 1023 break; 1024 1025 case LINK_STATE_UP: 1026 if (bif->bif_state == BSTP_IFSTATE_DISABLED) 1027 bstp_enable_port(sc, bif); 1028 break; 1029 1030 case LINK_STATE_DOWN: 1031 if (bif->bif_state != BSTP_IFSTATE_DISABLED) 1032 bstp_disable_port(sc, bif); 1033 break; 1034 } 1035 return; 1036 } 1037 1038 if (bif->bif_state != BSTP_IFSTATE_DISABLED) 1039 bstp_disable_port(sc, bif); 1040 } 1041 1042 void 1043 bstp_tick(void *arg) 1044 { 1045 struct bridge_softc *sc = arg; 1046 struct bridge_iflist *bif; 1047 int s; 1048 1049 s = splnet(); 1050 1051 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 1052 if ((bif->bif_flags & IFBIF_STP) == 0) 1053 continue; 1054 /* 1055 * XXX This can cause a lag in "link does away" 1056 * XXX and "spanning tree gets updated". We need 1057 * XXX come sort of callback from the link state 1058 * XXX update code to kick spanning tree. 1059 * XXX --thorpej@NetBSD.org 1060 */ 1061 bstp_ifupdstatus(sc, bif); 1062 } 1063 1064 if (bstp_timer_expired(&sc->sc_hello_timer, sc->sc_hello_time)) 1065 bstp_hello_timer_expiry(sc); 1066 1067 if (bstp_timer_expired(&sc->sc_tcn_timer, sc->sc_bridge_hello_time)) 1068 bstp_tcn_timer_expiry(sc); 1069 1070 if (bstp_timer_expired(&sc->sc_topology_change_timer, 1071 sc->sc_topology_change_time)) 1072 bstp_topology_change_timer_expiry(sc); 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_message_age_timer, 1078 sc->sc_max_age)) 1079 bstp_message_age_timer_expiry(sc, bif); 1080 } 1081 1082 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 1083 if ((bif->bif_flags & IFBIF_STP) == 0) 1084 continue; 1085 if (bstp_timer_expired(&bif->bif_forward_delay_timer, 1086 sc->sc_forward_delay)) 1087 bstp_forward_delay_timer_expiry(sc, bif); 1088 1089 if (bstp_timer_expired(&bif->bif_hold_timer, 1090 sc->sc_hold_time)) 1091 bstp_hold_timer_expiry(sc, bif); 1092 } 1093 1094 if (sc->sc_if.if_flags & IFF_RUNNING) 1095 callout_reset(&sc->sc_bstpcallout, hz, bstp_tick, sc); 1096 1097 splx(s); 1098 } 1099 1100 void 1101 bstp_timer_start(struct bridge_timer *t, uint16_t v) 1102 { 1103 t->value = v; 1104 t->active = 1; 1105 } 1106 1107 void 1108 bstp_timer_stop(struct bridge_timer *t) 1109 { 1110 t->value = 0; 1111 t->active = 0; 1112 } 1113 1114 int 1115 bstp_timer_expired(struct bridge_timer *t, uint16_t v) 1116 { 1117 if (t->active == 0) 1118 return (0); 1119 t->value += BSTP_TICK_VAL; 1120 if (t->value >= v) { 1121 bstp_timer_stop(t); 1122 return (1); 1123 } 1124 return (0); 1125 1126 } 1127