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