1 /* $NetBSD: bridgestp.c,v 1.5 2003/11/28 08:56:48 keihan Exp $ */ 2 3 /* 4 * Copyright (c) 2000 Jason L. Wright (jason@thought.net) 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. All advertising materials mentioning features or use of this software 16 * must display the following acknowledgement: 17 * This product includes software developed by Jason L. Wright 18 * 4. The name of the author may not be used to endorse or promote products 19 * derived from this software without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 22 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 23 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 24 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, 25 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 26 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 27 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 29 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 30 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 31 * POSSIBILITY OF SUCH DAMAGE. 32 * 33 * OpenBSD: bridgestp.c,v 1.5 2001/03/22 03:48:29 jason Exp 34 */ 35 36 /* 37 * Implementation of the spanning tree protocol as defined in 38 * ISO/IEC Final DIS 15802-3 (IEEE P802.1D/D17), May 25, 1998. 39 * (In English: IEEE 802.1D, Draft 17, 1998) 40 */ 41 42 #include <sys/cdefs.h> 43 __FBSDID("$FreeBSD$"); 44 45 #include <sys/param.h> 46 #include <sys/systm.h> 47 #include <sys/mbuf.h> 48 #include <sys/socket.h> 49 #include <sys/sockio.h> 50 #include <sys/kernel.h> 51 #include <sys/callout.h> 52 #include <sys/proc.h> 53 #include <sys/lock.h> 54 #include <sys/mutex.h> 55 56 #include <net/if.h> 57 #include <net/if_dl.h> 58 #include <net/if_types.h> 59 #include <net/if_llc.h> 60 #include <net/if_media.h> 61 62 #include <netinet/in.h> 63 #include <netinet/in_systm.h> 64 #include <netinet/in_var.h> 65 #include <netinet/if_ether.h> 66 #include <net/if_bridgevar.h> 67 68 /* BPDU message types */ 69 #define BSTP_MSGTYPE_CFG 0x00 /* Configuration */ 70 #define BSTP_MSGTYPE_TCN 0x80 /* Topology chg notification */ 71 72 /* BPDU flags */ 73 #define BSTP_FLAG_TC 0x01 /* Topology change */ 74 #define BSTP_FLAG_TCA 0x80 /* Topology change ack */ 75 76 #define BSTP_MESSAGE_AGE_INCR (1 * 256) /* in 256ths of a second */ 77 #define BSTP_TICK_VAL (1 * 256) /* in 256ths of a second */ 78 79 /* 80 * Because BPDU's do not make nicely aligned structures, two different 81 * declarations are used: bstp_?bpdu (wire representation, packed) and 82 * bstp_*_unit (internal, nicely aligned version). 83 */ 84 85 /* configuration bridge protocol data unit */ 86 struct bstp_cbpdu { 87 uint8_t cbu_dsap; /* LLC: destination sap */ 88 uint8_t cbu_ssap; /* LLC: source sap */ 89 uint8_t cbu_ctl; /* LLC: control */ 90 uint16_t cbu_protoid; /* protocol id */ 91 uint8_t cbu_protover; /* protocol version */ 92 uint8_t cbu_bpdutype; /* message type */ 93 uint8_t cbu_flags; /* flags (below) */ 94 95 /* root id */ 96 uint16_t cbu_rootpri; /* root priority */ 97 uint8_t cbu_rootaddr[6]; /* root address */ 98 99 uint32_t cbu_rootpathcost; /* root path cost */ 100 101 /* bridge id */ 102 uint16_t cbu_bridgepri; /* bridge priority */ 103 uint8_t cbu_bridgeaddr[6]; /* bridge address */ 104 105 uint16_t cbu_portid; /* port id */ 106 uint16_t cbu_messageage; /* current message age */ 107 uint16_t cbu_maxage; /* maximum age */ 108 uint16_t cbu_hellotime; /* hello time */ 109 uint16_t cbu_forwarddelay; /* forwarding delay */ 110 } __attribute__((__packed__)); 111 112 /* topology change notification bridge protocol data unit */ 113 struct bstp_tbpdu { 114 uint8_t tbu_dsap; /* LLC: destination sap */ 115 uint8_t tbu_ssap; /* LLC: source sap */ 116 uint8_t tbu_ctl; /* LLC: control */ 117 uint16_t tbu_protoid; /* protocol id */ 118 uint8_t tbu_protover; /* protocol version */ 119 uint8_t tbu_bpdutype; /* message type */ 120 } __attribute__((__packed__)); 121 122 const uint8_t bstp_etheraddr[] = { 0x01, 0x80, 0xc2, 0x00, 0x00, 0x00 }; 123 124 static void bstp_initialize_port(struct bridge_softc *, 125 struct bridge_iflist *); 126 static void bstp_ifupdstatus(struct bridge_softc *, struct bridge_iflist *); 127 static void bstp_enable_port(struct bridge_softc *, struct bridge_iflist *); 128 static void bstp_disable_port(struct bridge_softc *, 129 struct bridge_iflist *); 130 #ifdef notused 131 static void bstp_enable_change_detection(struct bridge_iflist *); 132 static void bstp_disable_change_detection(struct bridge_iflist *); 133 #endif /* notused */ 134 static int bstp_root_bridge(struct bridge_softc *sc); 135 static int bstp_supersedes_port_info(struct bridge_softc *, 136 struct bridge_iflist *, struct bstp_config_unit *); 137 static int bstp_designated_port(struct bridge_softc *, 138 struct bridge_iflist *); 139 static int bstp_designated_for_some_port(struct bridge_softc *); 140 static void bstp_transmit_config(struct bridge_softc *, 141 struct bridge_iflist *); 142 static void bstp_transmit_tcn(struct bridge_softc *); 143 static void bstp_received_config_bpdu(struct bridge_softc *, 144 struct bridge_iflist *, struct bstp_config_unit *); 145 static void bstp_received_tcn_bpdu(struct bridge_softc *, 146 struct bridge_iflist *, struct bstp_tcn_unit *); 147 static void bstp_record_config_information(struct bridge_softc *, 148 struct bridge_iflist *, struct bstp_config_unit *); 149 static void bstp_record_config_timeout_values(struct bridge_softc *, 150 struct bstp_config_unit *); 151 static void bstp_config_bpdu_generation(struct bridge_softc *); 152 static void bstp_send_config_bpdu(struct bridge_softc *, 153 struct bridge_iflist *, struct bstp_config_unit *); 154 static void bstp_configuration_update(struct bridge_softc *); 155 static void bstp_root_selection(struct bridge_softc *); 156 static void bstp_designated_port_selection(struct bridge_softc *); 157 static void bstp_become_designated_port(struct bridge_softc *, 158 struct bridge_iflist *); 159 static void bstp_port_state_selection(struct bridge_softc *); 160 static void bstp_make_forwarding(struct bridge_softc *, 161 struct bridge_iflist *); 162 static void bstp_make_blocking(struct bridge_softc *, 163 struct bridge_iflist *); 164 static void bstp_set_port_state(struct bridge_iflist *, uint8_t); 165 #ifdef notused 166 static void bstp_set_bridge_priority(struct bridge_softc *, uint64_t); 167 static void bstp_set_port_priority(struct bridge_softc *, 168 struct bridge_iflist *, uint16_t); 169 static void bstp_set_path_cost(struct bridge_softc *, 170 struct bridge_iflist *, uint32_t); 171 #endif /* notused */ 172 static void bstp_topology_change_detection(struct bridge_softc *); 173 static void bstp_topology_change_acknowledged(struct bridge_softc *); 174 static void bstp_acknowledge_topology_change(struct bridge_softc *, 175 struct bridge_iflist *); 176 177 static void bstp_tick(void *); 178 static void bstp_timer_start(struct bridge_timer *, uint16_t); 179 static void bstp_timer_stop(struct bridge_timer *); 180 static int bstp_timer_expired(struct bridge_timer *, uint16_t); 181 182 static void bstp_hold_timer_expiry(struct bridge_softc *, 183 struct bridge_iflist *); 184 static void bstp_message_age_timer_expiry(struct bridge_softc *, 185 struct bridge_iflist *); 186 static void bstp_forward_delay_timer_expiry(struct bridge_softc *, 187 struct bridge_iflist *); 188 static void bstp_topology_change_timer_expiry(struct bridge_softc *); 189 static void bstp_tcn_timer_expiry(struct bridge_softc *); 190 static void bstp_hello_timer_expiry(struct bridge_softc *); 191 192 static void 193 bstp_transmit_config(struct bridge_softc *sc, struct bridge_iflist *bif) 194 { 195 if (bif->bif_hold_timer.active) { 196 bif->bif_config_pending = 1; 197 return; 198 } 199 200 bif->bif_config_bpdu.cu_message_type = BSTP_MSGTYPE_CFG; 201 bif->bif_config_bpdu.cu_rootid = sc->sc_designated_root; 202 bif->bif_config_bpdu.cu_root_path_cost = sc->sc_root_path_cost; 203 bif->bif_config_bpdu.cu_bridge_id = sc->sc_bridge_id; 204 bif->bif_config_bpdu.cu_port_id = bif->bif_port_id; 205 206 if (bstp_root_bridge(sc)) 207 bif->bif_config_bpdu.cu_message_age = 0; 208 else 209 bif->bif_config_bpdu.cu_message_age = 210 sc->sc_root_port->bif_message_age_timer.value + 211 BSTP_MESSAGE_AGE_INCR; 212 213 bif->bif_config_bpdu.cu_max_age = sc->sc_max_age; 214 bif->bif_config_bpdu.cu_hello_time = sc->sc_hello_time; 215 bif->bif_config_bpdu.cu_forward_delay = sc->sc_forward_delay; 216 bif->bif_config_bpdu.cu_topology_change_acknowledgment 217 = bif->bif_topology_change_acknowledge; 218 bif->bif_config_bpdu.cu_topology_change = sc->sc_topology_change; 219 220 if (bif->bif_config_bpdu.cu_message_age < sc->sc_max_age) { 221 bif->bif_topology_change_acknowledge = 0; 222 bif->bif_config_pending = 0; 223 bstp_send_config_bpdu(sc, bif, &bif->bif_config_bpdu); 224 bstp_timer_start(&bif->bif_hold_timer, 0); 225 } 226 } 227 228 static void 229 bstp_send_config_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif, 230 struct bstp_config_unit *cu) 231 { 232 struct ifnet *ifp; 233 struct mbuf *m; 234 struct ether_header *eh; 235 struct bstp_cbpdu bpdu; 236 237 BRIDGE_LOCK_ASSERT(sc); 238 239 ifp = bif->bif_ifp; 240 241 if ((ifp->if_drv_flags & IFF_DRV_RUNNING) == 0) 242 return; 243 244 MGETHDR(m, M_DONTWAIT, MT_DATA); 245 if (m == NULL) 246 return; 247 248 eh = mtod(m, struct ether_header *); 249 250 m->m_pkthdr.rcvif = ifp; 251 m->m_pkthdr.len = sizeof(*eh) + sizeof(bpdu); 252 m->m_len = m->m_pkthdr.len; 253 254 bpdu.cbu_ssap = bpdu.cbu_dsap = LLC_8021D_LSAP; 255 bpdu.cbu_ctl = LLC_UI; 256 bpdu.cbu_protoid = htons(0); 257 bpdu.cbu_protover = 0; 258 bpdu.cbu_bpdutype = cu->cu_message_type; 259 bpdu.cbu_flags = (cu->cu_topology_change ? BSTP_FLAG_TC : 0) | 260 (cu->cu_topology_change_acknowledgment ? BSTP_FLAG_TCA : 0); 261 262 bpdu.cbu_rootpri = htons(cu->cu_rootid >> 48); 263 bpdu.cbu_rootaddr[0] = cu->cu_rootid >> 40; 264 bpdu.cbu_rootaddr[1] = cu->cu_rootid >> 32; 265 bpdu.cbu_rootaddr[2] = cu->cu_rootid >> 24; 266 bpdu.cbu_rootaddr[3] = cu->cu_rootid >> 16; 267 bpdu.cbu_rootaddr[4] = cu->cu_rootid >> 8; 268 bpdu.cbu_rootaddr[5] = cu->cu_rootid >> 0; 269 270 bpdu.cbu_rootpathcost = htonl(cu->cu_root_path_cost); 271 272 bpdu.cbu_bridgepri = htons(cu->cu_rootid >> 48); 273 bpdu.cbu_bridgeaddr[0] = cu->cu_rootid >> 40; 274 bpdu.cbu_bridgeaddr[1] = cu->cu_rootid >> 32; 275 bpdu.cbu_bridgeaddr[2] = cu->cu_rootid >> 24; 276 bpdu.cbu_bridgeaddr[3] = cu->cu_rootid >> 16; 277 bpdu.cbu_bridgeaddr[4] = cu->cu_rootid >> 8; 278 bpdu.cbu_bridgeaddr[5] = cu->cu_rootid >> 0; 279 280 bpdu.cbu_portid = htons(cu->cu_port_id); 281 bpdu.cbu_messageage = htons(cu->cu_message_age); 282 bpdu.cbu_maxage = htons(cu->cu_max_age); 283 bpdu.cbu_hellotime = htons(cu->cu_hello_time); 284 bpdu.cbu_forwarddelay = htons(cu->cu_forward_delay); 285 286 memcpy(eh->ether_shost, IF_LLADDR(ifp), ETHER_ADDR_LEN); 287 memcpy(eh->ether_dhost, bstp_etheraddr, ETHER_ADDR_LEN); 288 eh->ether_type = htons(sizeof(bpdu)); 289 290 memcpy(mtod(m, caddr_t) + sizeof(*eh), &bpdu, sizeof(bpdu)); 291 292 /* XXX: safe here?!? */ 293 BRIDGE_UNLOCK(sc); 294 bridge_enqueue(sc, ifp, m); 295 BRIDGE_LOCK(sc); 296 } 297 298 static int 299 bstp_root_bridge(struct bridge_softc *sc) 300 { 301 return (sc->sc_designated_root == sc->sc_bridge_id); 302 } 303 304 static int 305 bstp_supersedes_port_info(struct bridge_softc *sc, struct bridge_iflist *bif, 306 struct bstp_config_unit *cu) 307 { 308 if (cu->cu_rootid < bif->bif_designated_root) 309 return (1); 310 if (cu->cu_rootid > bif->bif_designated_root) 311 return (0); 312 313 if (cu->cu_root_path_cost < bif->bif_designated_cost) 314 return (1); 315 if (cu->cu_root_path_cost > bif->bif_designated_cost) 316 return (0); 317 318 if (cu->cu_bridge_id < bif->bif_designated_bridge) 319 return (1); 320 if (cu->cu_bridge_id > bif->bif_designated_bridge) 321 return (0); 322 323 if (sc->sc_bridge_id != cu->cu_bridge_id) 324 return (1); 325 if (cu->cu_port_id <= bif->bif_designated_port) 326 return (1); 327 return (0); 328 } 329 330 static void 331 bstp_record_config_information(struct bridge_softc *sc, 332 struct bridge_iflist *bif, struct bstp_config_unit *cu) 333 { 334 bif->bif_designated_root = cu->cu_rootid; 335 bif->bif_designated_cost = cu->cu_root_path_cost; 336 bif->bif_designated_bridge = cu->cu_bridge_id; 337 bif->bif_designated_port = cu->cu_port_id; 338 bstp_timer_start(&bif->bif_message_age_timer, cu->cu_message_age); 339 } 340 341 static void 342 bstp_record_config_timeout_values(struct bridge_softc *sc, 343 struct bstp_config_unit *config) 344 { 345 sc->sc_max_age = config->cu_max_age; 346 sc->sc_hello_time = config->cu_hello_time; 347 sc->sc_forward_delay = config->cu_forward_delay; 348 sc->sc_topology_change = config->cu_topology_change; 349 } 350 351 static void 352 bstp_config_bpdu_generation(struct bridge_softc *sc) 353 { 354 struct bridge_iflist *bif; 355 356 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 357 if ((bif->bif_flags & IFBIF_STP) == 0) 358 continue; 359 if (bstp_designated_port(sc, bif) && 360 (bif->bif_state != BSTP_IFSTATE_DISABLED)) 361 bstp_transmit_config(sc, bif); 362 } 363 } 364 365 static int 366 bstp_designated_port(struct bridge_softc *sc, struct bridge_iflist *bif) 367 { 368 return ((bif->bif_designated_bridge == sc->sc_bridge_id) 369 && (bif->bif_designated_port == bif->bif_port_id)); 370 } 371 372 static void 373 bstp_transmit_tcn(struct bridge_softc *sc) 374 { 375 struct bstp_tbpdu bpdu; 376 struct bridge_iflist *bif = sc->sc_root_port; 377 struct ifnet *ifp = bif->bif_ifp; 378 struct ether_header *eh; 379 struct mbuf *m; 380 381 BRIDGE_LOCK_ASSERT(sc); 382 383 if ((ifp->if_drv_flags & IFF_DRV_RUNNING) == 0) 384 return; 385 386 MGETHDR(m, M_DONTWAIT, MT_DATA); 387 if (m == NULL) 388 return; 389 390 m->m_pkthdr.rcvif = ifp; 391 m->m_pkthdr.len = sizeof(*eh) + sizeof(bpdu); 392 m->m_len = m->m_pkthdr.len; 393 394 eh = mtod(m, struct ether_header *); 395 396 memcpy(eh->ether_shost, IF_LLADDR(ifp), ETHER_ADDR_LEN); 397 memcpy(eh->ether_dhost, bstp_etheraddr, ETHER_ADDR_LEN); 398 eh->ether_type = htons(sizeof(bpdu)); 399 400 bpdu.tbu_ssap = bpdu.tbu_dsap = LLC_8021D_LSAP; 401 bpdu.tbu_ctl = LLC_UI; 402 bpdu.tbu_protoid = 0; 403 bpdu.tbu_protover = 0; 404 bpdu.tbu_bpdutype = BSTP_MSGTYPE_TCN; 405 406 memcpy(mtod(m, caddr_t) + sizeof(*eh), &bpdu, sizeof(bpdu)); 407 408 /* XXX: safe here?!? */ 409 BRIDGE_UNLOCK(sc); 410 bridge_enqueue(sc, ifp, m); 411 BRIDGE_LOCK(sc); 412 } 413 414 static void 415 bstp_configuration_update(struct bridge_softc *sc) 416 { 417 BRIDGE_LOCK_ASSERT(sc); 418 419 bstp_root_selection(sc); 420 bstp_designated_port_selection(sc); 421 } 422 423 static void 424 bstp_root_selection(struct bridge_softc *sc) 425 { 426 struct bridge_iflist *root_port = NULL, *bif; 427 428 BRIDGE_LOCK_ASSERT(sc); 429 430 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 431 if ((bif->bif_flags & IFBIF_STP) == 0) 432 continue; 433 if (bstp_designated_port(sc, bif)) 434 continue; 435 if (bif->bif_state == BSTP_IFSTATE_DISABLED) 436 continue; 437 if (bif->bif_designated_root >= sc->sc_bridge_id) 438 continue; 439 if (root_port == NULL) 440 goto set_port; 441 442 if (bif->bif_designated_root < root_port->bif_designated_root) 443 goto set_port; 444 if (bif->bif_designated_root > root_port->bif_designated_root) 445 continue; 446 447 if ((bif->bif_designated_cost + bif->bif_path_cost) < 448 (root_port->bif_designated_cost + root_port->bif_path_cost)) 449 goto set_port; 450 if ((bif->bif_designated_cost + bif->bif_path_cost) > 451 (root_port->bif_designated_cost + root_port->bif_path_cost)) 452 continue; 453 454 if (bif->bif_designated_bridge < 455 root_port->bif_designated_bridge) 456 goto set_port; 457 if (bif->bif_designated_bridge > 458 root_port->bif_designated_bridge) 459 continue; 460 461 if (bif->bif_designated_port < root_port->bif_designated_port) 462 goto set_port; 463 if (bif->bif_designated_port > root_port->bif_designated_port) 464 continue; 465 466 if (bif->bif_port_id >= root_port->bif_port_id) 467 continue; 468 set_port: 469 root_port = bif; 470 } 471 472 sc->sc_root_port = root_port; 473 if (root_port == NULL) { 474 sc->sc_designated_root = sc->sc_bridge_id; 475 sc->sc_root_path_cost = 0; 476 } else { 477 sc->sc_designated_root = root_port->bif_designated_root; 478 sc->sc_root_path_cost = root_port->bif_designated_cost + 479 root_port->bif_path_cost; 480 } 481 } 482 483 static void 484 bstp_designated_port_selection(struct bridge_softc *sc) 485 { 486 struct bridge_iflist *bif; 487 488 BRIDGE_LOCK_ASSERT(sc); 489 490 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 491 if ((bif->bif_flags & IFBIF_STP) == 0) 492 continue; 493 if (bstp_designated_port(sc, bif)) 494 goto designated; 495 if (bif->bif_designated_root != sc->sc_designated_root) 496 goto designated; 497 498 if (sc->sc_root_path_cost < bif->bif_designated_cost) 499 goto designated; 500 if (sc->sc_root_path_cost > bif->bif_designated_cost) 501 continue; 502 503 if (sc->sc_bridge_id < bif->bif_designated_bridge) 504 goto designated; 505 if (sc->sc_bridge_id > bif->bif_designated_bridge) 506 continue; 507 508 if (bif->bif_port_id > bif->bif_designated_port) 509 continue; 510 designated: 511 bstp_become_designated_port(sc, bif); 512 } 513 } 514 515 static void 516 bstp_become_designated_port(struct bridge_softc *sc, struct bridge_iflist *bif) 517 { 518 bif->bif_designated_root = sc->sc_designated_root; 519 bif->bif_designated_cost = sc->sc_root_path_cost; 520 bif->bif_designated_bridge = sc->sc_bridge_id; 521 bif->bif_designated_port = bif->bif_port_id; 522 } 523 524 static void 525 bstp_port_state_selection(struct bridge_softc *sc) 526 { 527 struct bridge_iflist *bif; 528 529 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 530 if ((bif->bif_flags & IFBIF_STP) == 0) 531 continue; 532 if (bif == sc->sc_root_port) { 533 bif->bif_config_pending = 0; 534 bif->bif_topology_change_acknowledge = 0; 535 bstp_make_forwarding(sc, bif); 536 } else if (bstp_designated_port(sc, bif)) { 537 bstp_timer_stop(&bif->bif_message_age_timer); 538 bstp_make_forwarding(sc, bif); 539 } else { 540 bif->bif_config_pending = 0; 541 bif->bif_topology_change_acknowledge = 0; 542 bstp_make_blocking(sc, bif); 543 } 544 } 545 } 546 547 static void 548 bstp_make_forwarding(struct bridge_softc *sc, struct bridge_iflist *bif) 549 { 550 if (bif->bif_state == BSTP_IFSTATE_BLOCKING) { 551 bstp_set_port_state(bif, BSTP_IFSTATE_LISTENING); 552 bstp_timer_start(&bif->bif_forward_delay_timer, 0); 553 } 554 } 555 556 static void 557 bstp_make_blocking(struct bridge_softc *sc, struct bridge_iflist *bif) 558 { 559 BRIDGE_LOCK_ASSERT(sc); 560 561 if ((bif->bif_state != BSTP_IFSTATE_DISABLED) && 562 (bif->bif_state != BSTP_IFSTATE_BLOCKING)) { 563 if ((bif->bif_state == BSTP_IFSTATE_FORWARDING) || 564 (bif->bif_state == BSTP_IFSTATE_LEARNING)) { 565 if (bif->bif_change_detection_enabled) { 566 bstp_topology_change_detection(sc); 567 } 568 } 569 bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING); 570 bridge_rtdelete(sc, bif->bif_ifp, IFBF_FLUSHDYN); 571 bstp_timer_stop(&bif->bif_forward_delay_timer); 572 } 573 } 574 575 static void 576 bstp_set_port_state(struct bridge_iflist *bif, uint8_t state) 577 { 578 bif->bif_state = state; 579 } 580 581 static void 582 bstp_topology_change_detection(struct bridge_softc *sc) 583 { 584 if (bstp_root_bridge(sc)) { 585 sc->sc_topology_change = 1; 586 bstp_timer_start(&sc->sc_topology_change_timer, 0); 587 } else if (!sc->sc_topology_change_detected) { 588 bstp_transmit_tcn(sc); 589 bstp_timer_start(&sc->sc_tcn_timer, 0); 590 } 591 sc->sc_topology_change_detected = 1; 592 } 593 594 static void 595 bstp_topology_change_acknowledged(struct bridge_softc *sc) 596 { 597 sc->sc_topology_change_detected = 0; 598 bstp_timer_stop(&sc->sc_tcn_timer); 599 } 600 601 static void 602 bstp_acknowledge_topology_change(struct bridge_softc *sc, 603 struct bridge_iflist *bif) 604 { 605 bif->bif_topology_change_acknowledge = 1; 606 bstp_transmit_config(sc, bif); 607 } 608 609 struct mbuf * 610 bstp_input(struct ifnet *ifp, struct mbuf *m) 611 { 612 struct bridge_softc *sc = ifp->if_bridge; 613 struct bridge_iflist *bif = NULL; 614 struct ether_header *eh; 615 struct bstp_tbpdu tpdu; 616 struct bstp_cbpdu cpdu; 617 struct bstp_config_unit cu; 618 struct bstp_tcn_unit tu; 619 uint16_t len; 620 621 BRIDGE_LOCK_ASSERT(sc); 622 623 eh = mtod(m, struct ether_header *); 624 625 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 626 if ((bif->bif_flags & IFBIF_STP) == 0) 627 continue; 628 if (bif->bif_ifp == ifp) 629 break; 630 } 631 if (bif == NULL) 632 goto out; 633 634 len = ntohs(eh->ether_type); 635 if (len < sizeof(tpdu)) 636 goto out; 637 638 m_adj(m, ETHER_HDR_LEN); 639 640 if (m->m_pkthdr.len > len) 641 m_adj(m, len - m->m_pkthdr.len); 642 if (m->m_len < sizeof(tpdu) && 643 (m = m_pullup(m, sizeof(tpdu))) == NULL) 644 goto out; 645 646 memcpy(&tpdu, mtod(m, caddr_t), sizeof(tpdu)); 647 648 if (tpdu.tbu_dsap != LLC_8021D_LSAP || 649 tpdu.tbu_ssap != LLC_8021D_LSAP || 650 tpdu.tbu_ctl != LLC_UI) 651 goto out; 652 if (tpdu.tbu_protoid != 0 || tpdu.tbu_protover != 0) 653 goto out; 654 655 switch (tpdu.tbu_bpdutype) { 656 case BSTP_MSGTYPE_TCN: 657 tu.tu_message_type = tpdu.tbu_bpdutype; 658 bstp_received_tcn_bpdu(sc, bif, &tu); 659 break; 660 case BSTP_MSGTYPE_CFG: 661 if (m->m_len < sizeof(cpdu) && 662 (m = m_pullup(m, sizeof(cpdu))) == NULL) 663 goto out; 664 memcpy(&cpdu, mtod(m, caddr_t), sizeof(cpdu)); 665 666 cu.cu_rootid = 667 (((uint64_t)ntohs(cpdu.cbu_rootpri)) << 48) | 668 (((uint64_t)cpdu.cbu_rootaddr[0]) << 40) | 669 (((uint64_t)cpdu.cbu_rootaddr[1]) << 32) | 670 (((uint64_t)cpdu.cbu_rootaddr[2]) << 24) | 671 (((uint64_t)cpdu.cbu_rootaddr[3]) << 16) | 672 (((uint64_t)cpdu.cbu_rootaddr[4]) << 8) | 673 (((uint64_t)cpdu.cbu_rootaddr[5]) << 0); 674 675 cu.cu_bridge_id = 676 (((uint64_t)ntohs(cpdu.cbu_bridgepri)) << 48) | 677 (((uint64_t)cpdu.cbu_bridgeaddr[0]) << 40) | 678 (((uint64_t)cpdu.cbu_bridgeaddr[1]) << 32) | 679 (((uint64_t)cpdu.cbu_bridgeaddr[2]) << 24) | 680 (((uint64_t)cpdu.cbu_bridgeaddr[3]) << 16) | 681 (((uint64_t)cpdu.cbu_bridgeaddr[4]) << 8) | 682 (((uint64_t)cpdu.cbu_bridgeaddr[5]) << 0); 683 684 cu.cu_root_path_cost = ntohl(cpdu.cbu_rootpathcost); 685 cu.cu_message_age = ntohs(cpdu.cbu_messageage); 686 cu.cu_max_age = ntohs(cpdu.cbu_maxage); 687 cu.cu_hello_time = ntohs(cpdu.cbu_hellotime); 688 cu.cu_forward_delay = ntohs(cpdu.cbu_forwarddelay); 689 cu.cu_port_id = ntohs(cpdu.cbu_portid); 690 cu.cu_message_type = cpdu.cbu_bpdutype; 691 cu.cu_topology_change_acknowledgment = 692 (cpdu.cbu_flags & BSTP_FLAG_TCA) ? 1 : 0; 693 cu.cu_topology_change = 694 (cpdu.cbu_flags & BSTP_FLAG_TC) ? 1 : 0; 695 bstp_received_config_bpdu(sc, bif, &cu); 696 break; 697 default: 698 goto out; 699 } 700 701 out: 702 if (m) 703 m_freem(m); 704 return (NULL); 705 } 706 707 static void 708 bstp_received_config_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif, 709 struct bstp_config_unit *cu) 710 { 711 int root; 712 713 BRIDGE_LOCK_ASSERT(sc); 714 715 root = bstp_root_bridge(sc); 716 717 if (bif->bif_state != BSTP_IFSTATE_DISABLED) { 718 if (bstp_supersedes_port_info(sc, bif, cu)) { 719 bstp_record_config_information(sc, bif, cu); 720 bstp_configuration_update(sc); 721 bstp_port_state_selection(sc); 722 723 if ((bstp_root_bridge(sc) == 0) && root) { 724 bstp_timer_stop(&sc->sc_hello_timer); 725 726 if (sc->sc_topology_change_detected) { 727 bstp_timer_stop( 728 &sc->sc_topology_change_timer); 729 bstp_transmit_tcn(sc); 730 bstp_timer_start(&sc->sc_tcn_timer, 0); 731 } 732 } 733 734 if (bif == sc->sc_root_port) { 735 bstp_record_config_timeout_values(sc, cu); 736 bstp_config_bpdu_generation(sc); 737 738 if (cu->cu_topology_change_acknowledgment) 739 bstp_topology_change_acknowledged(sc); 740 } 741 } else if (bstp_designated_port(sc, bif)) 742 bstp_transmit_config(sc, bif); 743 } 744 } 745 746 static void 747 bstp_received_tcn_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif, 748 struct bstp_tcn_unit *tcn) 749 { 750 if (bif->bif_state != BSTP_IFSTATE_DISABLED && 751 bstp_designated_port(sc, bif)) { 752 bstp_topology_change_detection(sc); 753 bstp_acknowledge_topology_change(sc, bif); 754 } 755 } 756 757 static void 758 bstp_hello_timer_expiry(struct bridge_softc *sc) 759 { 760 bstp_config_bpdu_generation(sc); 761 bstp_timer_start(&sc->sc_hello_timer, 0); 762 } 763 764 static void 765 bstp_message_age_timer_expiry(struct bridge_softc *sc, 766 struct bridge_iflist *bif) 767 { 768 int root; 769 770 root = bstp_root_bridge(sc); 771 bstp_become_designated_port(sc, bif); 772 bstp_configuration_update(sc); 773 bstp_port_state_selection(sc); 774 775 if ((bstp_root_bridge(sc)) && (root == 0)) { 776 sc->sc_max_age = sc->sc_bridge_max_age; 777 sc->sc_hello_time = sc->sc_bridge_hello_time; 778 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 779 780 bstp_topology_change_detection(sc); 781 bstp_timer_stop(&sc->sc_tcn_timer); 782 bstp_config_bpdu_generation(sc); 783 bstp_timer_start(&sc->sc_hello_timer, 0); 784 } 785 } 786 787 static void 788 bstp_forward_delay_timer_expiry(struct bridge_softc *sc, 789 struct bridge_iflist *bif) 790 { 791 if (bif->bif_state == BSTP_IFSTATE_LISTENING) { 792 bstp_set_port_state(bif, BSTP_IFSTATE_LEARNING); 793 bstp_timer_start(&bif->bif_forward_delay_timer, 0); 794 } else if (bif->bif_state == BSTP_IFSTATE_LEARNING) { 795 bstp_set_port_state(bif, BSTP_IFSTATE_FORWARDING); 796 if (bstp_designated_for_some_port(sc) && 797 bif->bif_change_detection_enabled) 798 bstp_topology_change_detection(sc); 799 } 800 } 801 802 static int 803 bstp_designated_for_some_port(struct bridge_softc *sc) 804 { 805 806 struct bridge_iflist *bif; 807 808 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 809 if ((bif->bif_flags & IFBIF_STP) == 0) 810 continue; 811 if (bif->bif_designated_bridge == sc->sc_bridge_id) 812 return (1); 813 } 814 return (0); 815 } 816 817 static void 818 bstp_tcn_timer_expiry(struct bridge_softc *sc) 819 { 820 bstp_transmit_tcn(sc); 821 bstp_timer_start(&sc->sc_tcn_timer, 0); 822 } 823 824 static void 825 bstp_topology_change_timer_expiry(struct bridge_softc *sc) 826 { 827 sc->sc_topology_change_detected = 0; 828 sc->sc_topology_change = 0; 829 } 830 831 static void 832 bstp_hold_timer_expiry(struct bridge_softc *sc, struct bridge_iflist *bif) 833 { 834 if (bif->bif_config_pending) 835 bstp_transmit_config(sc, bif); 836 } 837 838 void 839 bstp_initialization(struct bridge_softc *sc) 840 { 841 struct bridge_iflist *bif, *mif; 842 843 BRIDGE_LOCK_ASSERT(sc); 844 845 mif = NULL; 846 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 847 if ((bif->bif_flags & IFBIF_STP) == 0) 848 continue; 849 if (bif->bif_ifp->if_type != IFT_ETHER) 850 continue; 851 bif->bif_port_id = (bif->bif_priority << 8) | 852 (bif->bif_ifp->if_index & 0xff); 853 854 if (mif == NULL) { 855 mif = bif; 856 continue; 857 } 858 if (memcmp(IF_LLADDR(bif->bif_ifp), 859 IF_LLADDR(mif->bif_ifp), ETHER_ADDR_LEN) < 0) { 860 mif = bif; 861 continue; 862 } 863 } 864 if (mif == NULL) { 865 bstp_stop(sc); 866 return; 867 } 868 869 sc->sc_bridge_id = 870 (((uint64_t)sc->sc_bridge_priority) << 48) | 871 (((uint64_t)IF_LLADDR(mif->bif_ifp)[0]) << 40) | 872 (((uint64_t)IF_LLADDR(mif->bif_ifp)[1]) << 32) | 873 (IF_LLADDR(mif->bif_ifp)[2] << 24) | 874 (IF_LLADDR(mif->bif_ifp)[3] << 16) | 875 (IF_LLADDR(mif->bif_ifp)[4] << 8) | 876 (IF_LLADDR(mif->bif_ifp)[5]); 877 878 sc->sc_designated_root = sc->sc_bridge_id; 879 sc->sc_root_path_cost = 0; 880 sc->sc_root_port = NULL; 881 882 sc->sc_max_age = sc->sc_bridge_max_age; 883 sc->sc_hello_time = sc->sc_bridge_hello_time; 884 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 885 sc->sc_topology_change_detected = 0; 886 sc->sc_topology_change = 0; 887 bstp_timer_stop(&sc->sc_tcn_timer); 888 bstp_timer_stop(&sc->sc_topology_change_timer); 889 890 if (callout_pending(&sc->sc_bstpcallout) == 0) 891 callout_reset(&sc->sc_bstpcallout, hz, 892 bstp_tick, sc); 893 894 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 895 if (bif->bif_flags & IFBIF_STP) 896 bstp_ifupdstatus(sc, bif); 897 else 898 bstp_disable_port(sc, bif); 899 } 900 901 bstp_port_state_selection(sc); 902 bstp_config_bpdu_generation(sc); 903 bstp_timer_start(&sc->sc_hello_timer, 0); 904 } 905 906 void 907 bstp_stop(struct bridge_softc *sc) 908 { 909 struct bridge_iflist *bif; 910 911 BRIDGE_LOCK_ASSERT(sc); 912 913 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 914 bstp_set_port_state(bif, BSTP_IFSTATE_DISABLED); 915 bstp_timer_stop(&bif->bif_hold_timer); 916 bstp_timer_stop(&bif->bif_message_age_timer); 917 bstp_timer_stop(&bif->bif_forward_delay_timer); 918 } 919 920 callout_stop(&sc->sc_bstpcallout); 921 922 bstp_timer_stop(&sc->sc_topology_change_timer); 923 bstp_timer_stop(&sc->sc_tcn_timer); 924 bstp_timer_stop(&sc->sc_hello_timer); 925 926 } 927 928 static void 929 bstp_initialize_port(struct bridge_softc *sc, struct bridge_iflist *bif) 930 { 931 bstp_become_designated_port(sc, bif); 932 bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING); 933 bif->bif_topology_change_acknowledge = 0; 934 bif->bif_config_pending = 0; 935 bif->bif_change_detection_enabled = 1; 936 bstp_timer_stop(&bif->bif_message_age_timer); 937 bstp_timer_stop(&bif->bif_forward_delay_timer); 938 bstp_timer_stop(&bif->bif_hold_timer); 939 } 940 941 static void 942 bstp_enable_port(struct bridge_softc *sc, struct bridge_iflist *bif) 943 { 944 bstp_initialize_port(sc, bif); 945 bstp_port_state_selection(sc); 946 } 947 948 static void 949 bstp_disable_port(struct bridge_softc *sc, struct bridge_iflist *bif) 950 { 951 int root; 952 953 BRIDGE_LOCK_ASSERT(sc); 954 955 root = bstp_root_bridge(sc); 956 bstp_become_designated_port(sc, bif); 957 bstp_set_port_state(bif, BSTP_IFSTATE_DISABLED); 958 bif->bif_topology_change_acknowledge = 0; 959 bif->bif_config_pending = 0; 960 bstp_timer_stop(&bif->bif_message_age_timer); 961 bstp_timer_stop(&bif->bif_forward_delay_timer); 962 bstp_configuration_update(sc); 963 bstp_port_state_selection(sc); 964 bridge_rtdelete(sc, bif->bif_ifp, IFBF_FLUSHDYN); 965 966 if (bstp_root_bridge(sc) && (root == 0)) { 967 sc->sc_max_age = sc->sc_bridge_max_age; 968 sc->sc_hello_time = sc->sc_bridge_hello_time; 969 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 970 971 bstp_topology_change_detection(sc); 972 bstp_timer_stop(&sc->sc_tcn_timer); 973 bstp_config_bpdu_generation(sc); 974 bstp_timer_start(&sc->sc_hello_timer, 0); 975 } 976 } 977 978 #ifdef notused 979 static void 980 bstp_set_bridge_priority(struct bridge_softc *sc, uint64_t new_bridge_id) 981 { 982 struct bridge_iflist *bif; 983 int root; 984 985 BRIDGE_LOCK_ASSERT(sc); 986 987 root = bstp_root_bridge(sc); 988 989 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 990 if ((bif->bif_flags & IFBIF_STP) == 0) 991 continue; 992 if (bstp_designated_port(sc, bif)) 993 bif->bif_designated_bridge = new_bridge_id; 994 } 995 996 sc->sc_bridge_id = new_bridge_id; 997 998 bstp_configuration_update(sc); 999 bstp_port_state_selection(sc); 1000 1001 if (bstp_root_bridge(sc) && (root == 0)) { 1002 sc->sc_max_age = sc->sc_bridge_max_age; 1003 sc->sc_hello_time = sc->sc_bridge_hello_time; 1004 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 1005 1006 bstp_topology_change_detection(sc); 1007 bstp_timer_stop(&sc->sc_tcn_timer); 1008 bstp_config_bpdu_generation(sc); 1009 bstp_timer_start(&sc->sc_hello_timer, 0); 1010 } 1011 } 1012 1013 static void 1014 bstp_set_port_priority(struct bridge_softc *sc, struct bridge_iflist *bif, 1015 uint16_t new_port_id) 1016 { 1017 if (bstp_designated_port(sc, bif)) 1018 bif->bif_designated_port = new_port_id; 1019 1020 bif->bif_port_id = new_port_id; 1021 1022 if ((sc->sc_bridge_id == bif->bif_designated_bridge) && 1023 (bif->bif_port_id < bif->bif_designated_port)) { 1024 bstp_become_designated_port(sc, bif); 1025 bstp_port_state_selection(sc); 1026 } 1027 } 1028 1029 static void 1030 bstp_set_path_cost(struct bridge_softc *sc, struct bridge_iflist *bif, 1031 uint32_t path_cost) 1032 { 1033 bif->bif_path_cost = path_cost; 1034 bstp_configuration_update(sc); 1035 bstp_port_state_selection(sc); 1036 } 1037 1038 static void 1039 bstp_enable_change_detection(struct bridge_iflist *bif) 1040 { 1041 bif->bif_change_detection_enabled = 1; 1042 } 1043 1044 static void 1045 bstp_disable_change_detection(struct bridge_iflist *bif) 1046 { 1047 bif->bif_change_detection_enabled = 0; 1048 } 1049 #endif /* notused */ 1050 1051 void 1052 bstp_linkstate(struct ifnet *ifp, int state) 1053 { 1054 struct bridge_softc *sc; 1055 struct bridge_iflist *bif; 1056 1057 sc = ifp->if_bridge; 1058 BRIDGE_LOCK(sc); 1059 1060 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 1061 if ((bif->bif_flags & IFBIF_STP) == 0) 1062 continue; 1063 1064 if (bif->bif_ifp == ifp) { 1065 bstp_ifupdstatus(sc, bif); 1066 break; 1067 } 1068 } 1069 1070 BRIDGE_UNLOCK(sc); 1071 } 1072 1073 static void 1074 bstp_ifupdstatus(struct bridge_softc *sc, struct bridge_iflist *bif) 1075 { 1076 struct ifnet *ifp = bif->bif_ifp; 1077 struct ifmediareq ifmr; 1078 int error = 0; 1079 1080 BRIDGE_LOCK_ASSERT(sc); 1081 1082 bzero((char *)&ifmr, sizeof(ifmr)); 1083 error = (*ifp->if_ioctl)(ifp, SIOCGIFMEDIA, (caddr_t)&ifmr); 1084 1085 if ((error == 0) && (ifp->if_flags & IFF_UP)) { 1086 if (ifmr.ifm_status & IFM_ACTIVE) { 1087 if (bif->bif_state == BSTP_IFSTATE_DISABLED) 1088 bstp_enable_port(sc, bif); 1089 1090 } else { 1091 if (bif->bif_state != BSTP_IFSTATE_DISABLED) 1092 bstp_disable_port(sc, bif); 1093 } 1094 return; 1095 } 1096 1097 if (bif->bif_state != BSTP_IFSTATE_DISABLED) 1098 bstp_disable_port(sc, bif); 1099 } 1100 1101 static void 1102 bstp_tick(void *arg) 1103 { 1104 struct bridge_softc *sc = arg; 1105 struct bridge_iflist *bif; 1106 1107 BRIDGE_LOCK_ASSERT(sc); 1108 1109 #if 0 1110 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 1111 if ((bif->bif_flags & IFBIF_STP) == 0) 1112 continue; 1113 /* 1114 * XXX This can cause a lag in "link does away" 1115 * XXX and "spanning tree gets updated". We need 1116 * XXX come sort of callback from the link state 1117 * XXX update code to kick spanning tree. 1118 * XXX --thorpej@NetBSD.org 1119 */ 1120 bstp_ifupdstatus(sc, bif); 1121 } 1122 #endif 1123 1124 if (bstp_timer_expired(&sc->sc_hello_timer, sc->sc_hello_time)) 1125 bstp_hello_timer_expiry(sc); 1126 1127 if (bstp_timer_expired(&sc->sc_tcn_timer, sc->sc_bridge_hello_time)) 1128 bstp_tcn_timer_expiry(sc); 1129 1130 if (bstp_timer_expired(&sc->sc_topology_change_timer, 1131 sc->sc_topology_change_time)) 1132 bstp_topology_change_timer_expiry(sc); 1133 1134 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 1135 if ((bif->bif_flags & IFBIF_STP) == 0) 1136 continue; 1137 if (bstp_timer_expired(&bif->bif_message_age_timer, 1138 sc->sc_max_age)) 1139 bstp_message_age_timer_expiry(sc, bif); 1140 } 1141 1142 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 1143 if ((bif->bif_flags & IFBIF_STP) == 0) 1144 continue; 1145 if (bstp_timer_expired(&bif->bif_forward_delay_timer, 1146 sc->sc_forward_delay)) 1147 bstp_forward_delay_timer_expiry(sc, bif); 1148 1149 if (bstp_timer_expired(&bif->bif_hold_timer, 1150 sc->sc_hold_time)) 1151 bstp_hold_timer_expiry(sc, bif); 1152 } 1153 1154 if (sc->sc_ifp->if_drv_flags & IFF_DRV_RUNNING) 1155 callout_reset(&sc->sc_bstpcallout, hz, bstp_tick, sc); 1156 } 1157 1158 static void 1159 bstp_timer_start(struct bridge_timer *t, uint16_t v) 1160 { 1161 t->value = v; 1162 t->active = 1; 1163 } 1164 1165 static void 1166 bstp_timer_stop(struct bridge_timer *t) 1167 { 1168 t->value = 0; 1169 t->active = 0; 1170 } 1171 1172 static int 1173 bstp_timer_expired(struct bridge_timer *t, uint16_t v) 1174 { 1175 if (t->active == 0) 1176 return (0); 1177 t->value += BSTP_TICK_VAL; 1178 if (t->value >= v) { 1179 bstp_timer_stop(t); 1180 return (1); 1181 } 1182 return (0); 1183 1184 } 1185