1 /* 2 * Copyright (c) 2000 Jason L. Wright (jason@thought.net) 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. All advertising materials mentioning features or use of this software 14 * must display the following acknowledgement: 15 * This product includes software developed by Jason L. Wright 16 * 4. The name of the author may not be used to endorse or promote products 17 * derived from this software without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 20 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 21 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 22 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, 23 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 24 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 25 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 27 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 28 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 * 31 * $OpenBSD: bridgestp.c,v 1.5 2001/03/22 03:48:29 jason Exp $ 32 * $NetBSD: bridgestp.c,v 1.5 2003/11/28 08:56:48 keihan Exp $ 33 * $FreeBSD: src/sys/net/bridgestp.c,v 1.7 2005/10/11 02:58:32 thompsa Exp $ 34 * $DragonFly: src/sys/net/bridge/bridgestp.c,v 1.2 2005/12/22 15:16:13 corecode Exp $ 35 */ 36 37 /* 38 * Implementation of the spanning tree protocol as defined in 39 * ISO/IEC Final DIS 15802-3 (IEEE P802.1D/D17), May 25, 1998. 40 * (In English: IEEE 802.1D, Draft 17, 1998) 41 */ 42 43 #include <sys/cdefs.h> 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/thread.h> 55 #include <sys/thread2.h> 56 57 #include <net/if.h> 58 #include <net/if_dl.h> 59 #include <net/if_types.h> 60 #include <net/if_llc.h> 61 #include <net/if_media.h> 62 63 #include <netinet/in.h> 64 #include <netinet/in_systm.h> 65 #include <netinet/in_var.h> 66 #include <netinet/if_ether.h> 67 #include <net/bridge/if_bridgevar.h> 68 69 /* BPDU message types */ 70 #define BSTP_MSGTYPE_CFG 0x00 /* Configuration */ 71 #define BSTP_MSGTYPE_TCN 0x80 /* Topology chg notification */ 72 73 /* BPDU flags */ 74 #define BSTP_FLAG_TC 0x01 /* Topology change */ 75 #define BSTP_FLAG_TCA 0x80 /* Topology change ack */ 76 77 #define BSTP_MESSAGE_AGE_INCR (1 * 256) /* in 256ths of a second */ 78 #define BSTP_TICK_VAL (1 * 256) /* in 256ths of a second */ 79 80 /* 81 * Because BPDU's do not make nicely aligned structures, two different 82 * declarations are used: bstp_?bpdu (wire representation, packed) and 83 * bstp_*_unit (internal, nicely aligned version). 84 */ 85 86 /* configuration bridge protocol data unit */ 87 struct bstp_cbpdu { 88 uint8_t cbu_dsap; /* LLC: destination sap */ 89 uint8_t cbu_ssap; /* LLC: source sap */ 90 uint8_t cbu_ctl; /* LLC: control */ 91 uint16_t cbu_protoid; /* protocol id */ 92 uint8_t cbu_protover; /* protocol version */ 93 uint8_t cbu_bpdutype; /* message type */ 94 uint8_t cbu_flags; /* flags (below) */ 95 96 /* root id */ 97 uint16_t cbu_rootpri; /* root priority */ 98 uint8_t cbu_rootaddr[6]; /* root address */ 99 100 uint32_t cbu_rootpathcost; /* root path cost */ 101 102 /* bridge id */ 103 uint16_t cbu_bridgepri; /* bridge priority */ 104 uint8_t cbu_bridgeaddr[6]; /* bridge address */ 105 106 uint16_t cbu_portid; /* port id */ 107 uint16_t cbu_messageage; /* current message age */ 108 uint16_t cbu_maxage; /* maximum age */ 109 uint16_t cbu_hellotime; /* hello time */ 110 uint16_t cbu_forwarddelay; /* forwarding delay */ 111 } __attribute__((__packed__)); 112 113 /* topology change notification bridge protocol data unit */ 114 struct bstp_tbpdu { 115 uint8_t tbu_dsap; /* LLC: destination sap */ 116 uint8_t tbu_ssap; /* LLC: source sap */ 117 uint8_t tbu_ctl; /* LLC: control */ 118 uint16_t tbu_protoid; /* protocol id */ 119 uint8_t tbu_protover; /* protocol version */ 120 uint8_t tbu_bpdutype; /* message type */ 121 } __attribute__((__packed__)); 122 123 const uint8_t bstp_etheraddr[] = { 0x01, 0x80, 0xc2, 0x00, 0x00, 0x00 }; 124 125 void bstp_initialize_port(struct bridge_softc *, struct bridge_iflist *); 126 void bstp_ifupdstatus(struct bridge_softc *, struct bridge_iflist *); 127 void bstp_enable_port(struct bridge_softc *, struct bridge_iflist *); 128 void bstp_disable_port(struct bridge_softc *, struct bridge_iflist *); 129 void bstp_enable_change_detection(struct bridge_iflist *); 130 void bstp_disable_change_detection(struct bridge_iflist *); 131 int bstp_root_bridge(struct bridge_softc *sc); 132 int bstp_supersedes_port_info(struct bridge_softc *, 133 struct bridge_iflist *, struct bstp_config_unit *); 134 int bstp_designated_port(struct bridge_softc *, struct bridge_iflist *); 135 int bstp_designated_for_some_port(struct bridge_softc *); 136 void bstp_transmit_config(struct bridge_softc *, struct bridge_iflist *); 137 void bstp_transmit_tcn(struct bridge_softc *); 138 void bstp_received_config_bpdu(struct bridge_softc *, 139 struct bridge_iflist *, struct bstp_config_unit *); 140 void bstp_received_tcn_bpdu(struct bridge_softc *, struct bridge_iflist *, 141 struct bstp_tcn_unit *); 142 void bstp_record_config_information(struct bridge_softc *, 143 struct bridge_iflist *, struct bstp_config_unit *); 144 void bstp_record_config_timeout_values(struct bridge_softc *, 145 struct bstp_config_unit *); 146 void bstp_config_bpdu_generation(struct bridge_softc *); 147 void bstp_send_config_bpdu(struct bridge_softc *, struct bridge_iflist *, 148 struct bstp_config_unit *); 149 void bstp_configuration_update(struct bridge_softc *); 150 void bstp_root_selection(struct bridge_softc *); 151 void bstp_designated_port_selection(struct bridge_softc *); 152 void bstp_become_designated_port(struct bridge_softc *, 153 struct bridge_iflist *); 154 void bstp_port_state_selection(struct bridge_softc *); 155 void bstp_make_forwarding(struct bridge_softc *, struct bridge_iflist *); 156 void bstp_make_blocking(struct bridge_softc *, struct bridge_iflist *); 157 void bstp_set_port_state(struct bridge_iflist *, uint8_t); 158 void bstp_set_bridge_priority(struct bridge_softc *, uint64_t); 159 void bstp_set_port_priority(struct bridge_softc *, struct bridge_iflist *, 160 uint16_t); 161 void bstp_set_path_cost(struct bridge_softc *, struct bridge_iflist *, 162 uint32_t); 163 void bstp_topology_change_detection(struct bridge_softc *); 164 void bstp_topology_change_acknowledged(struct bridge_softc *); 165 void bstp_acknowledge_topology_change(struct bridge_softc *, 166 struct bridge_iflist *); 167 168 void bstp_tick(void *); 169 void bstp_timer_start(struct bridge_timer *, uint16_t); 170 void bstp_timer_stop(struct bridge_timer *); 171 int bstp_timer_expired(struct bridge_timer *, uint16_t); 172 173 void bstp_hold_timer_expiry(struct bridge_softc *, struct bridge_iflist *); 174 void bstp_message_age_timer_expiry(struct bridge_softc *, 175 struct bridge_iflist *); 176 void bstp_forward_delay_timer_expiry(struct bridge_softc *, 177 struct bridge_iflist *); 178 void bstp_topology_change_timer_expiry(struct bridge_softc *); 179 void bstp_tcn_timer_expiry(struct bridge_softc *); 180 void bstp_hello_timer_expiry(struct bridge_softc *); 181 182 void 183 bstp_transmit_config(struct bridge_softc *sc, struct bridge_iflist *bif) 184 { 185 if (bif->bif_hold_timer.active) { 186 bif->bif_config_pending = 1; 187 return; 188 } 189 190 bif->bif_config_bpdu.cu_message_type = BSTP_MSGTYPE_CFG; 191 bif->bif_config_bpdu.cu_rootid = sc->sc_designated_root; 192 bif->bif_config_bpdu.cu_root_path_cost = sc->sc_root_path_cost; 193 bif->bif_config_bpdu.cu_bridge_id = sc->sc_bridge_id; 194 bif->bif_config_bpdu.cu_port_id = bif->bif_port_id; 195 196 if (bstp_root_bridge(sc)) 197 bif->bif_config_bpdu.cu_message_age = 0; 198 else 199 bif->bif_config_bpdu.cu_message_age = 200 sc->sc_root_port->bif_message_age_timer.value + 201 BSTP_MESSAGE_AGE_INCR; 202 203 bif->bif_config_bpdu.cu_max_age = sc->sc_max_age; 204 bif->bif_config_bpdu.cu_hello_time = sc->sc_hello_time; 205 bif->bif_config_bpdu.cu_forward_delay = sc->sc_forward_delay; 206 bif->bif_config_bpdu.cu_topology_change_acknowledgment 207 = bif->bif_topology_change_acknowledge; 208 bif->bif_config_bpdu.cu_topology_change = sc->sc_topology_change; 209 210 if (bif->bif_config_bpdu.cu_message_age < sc->sc_max_age) { 211 bif->bif_topology_change_acknowledge = 0; 212 bif->bif_config_pending = 0; 213 bstp_send_config_bpdu(sc, bif, &bif->bif_config_bpdu); 214 bstp_timer_start(&bif->bif_hold_timer, 0); 215 } 216 } 217 218 void 219 bstp_send_config_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif, 220 struct bstp_config_unit *cu) 221 { 222 struct ifnet *ifp; 223 struct mbuf *m; 224 struct ether_header *eh; 225 struct bstp_cbpdu bpdu; 226 227 ifp = bif->bif_ifp; 228 229 if ((ifp->if_flags & IFF_RUNNING) == 0) 230 return; 231 232 MGETHDR(m, MB_DONTWAIT, MT_DATA); 233 if (m == NULL) 234 return; 235 236 eh = mtod(m, struct ether_header *); 237 238 m->m_pkthdr.rcvif = ifp; 239 m->m_pkthdr.len = sizeof(*eh) + sizeof(bpdu); 240 m->m_len = m->m_pkthdr.len; 241 242 bpdu.cbu_ssap = bpdu.cbu_dsap = LLC_8021D_LSAP; 243 bpdu.cbu_ctl = LLC_UI; 244 bpdu.cbu_protoid = htons(0); 245 bpdu.cbu_protover = 0; 246 bpdu.cbu_bpdutype = cu->cu_message_type; 247 bpdu.cbu_flags = (cu->cu_topology_change ? BSTP_FLAG_TC : 0) | 248 (cu->cu_topology_change_acknowledgment ? BSTP_FLAG_TCA : 0); 249 250 bpdu.cbu_rootpri = htons(cu->cu_rootid >> 48); 251 bpdu.cbu_rootaddr[0] = cu->cu_rootid >> 40; 252 bpdu.cbu_rootaddr[1] = cu->cu_rootid >> 32; 253 bpdu.cbu_rootaddr[2] = cu->cu_rootid >> 24; 254 bpdu.cbu_rootaddr[3] = cu->cu_rootid >> 16; 255 bpdu.cbu_rootaddr[4] = cu->cu_rootid >> 8; 256 bpdu.cbu_rootaddr[5] = cu->cu_rootid >> 0; 257 258 bpdu.cbu_rootpathcost = htonl(cu->cu_root_path_cost); 259 260 bpdu.cbu_bridgepri = htons(cu->cu_rootid >> 48); 261 bpdu.cbu_bridgeaddr[0] = cu->cu_rootid >> 40; 262 bpdu.cbu_bridgeaddr[1] = cu->cu_rootid >> 32; 263 bpdu.cbu_bridgeaddr[2] = cu->cu_rootid >> 24; 264 bpdu.cbu_bridgeaddr[3] = cu->cu_rootid >> 16; 265 bpdu.cbu_bridgeaddr[4] = cu->cu_rootid >> 8; 266 bpdu.cbu_bridgeaddr[5] = cu->cu_rootid >> 0; 267 268 bpdu.cbu_portid = htons(cu->cu_port_id); 269 bpdu.cbu_messageage = htons(cu->cu_message_age); 270 bpdu.cbu_maxage = htons(cu->cu_max_age); 271 bpdu.cbu_hellotime = htons(cu->cu_hello_time); 272 bpdu.cbu_forwarddelay = htons(cu->cu_forward_delay); 273 274 memcpy(eh->ether_shost, IF_LLADDR(ifp), ETHER_ADDR_LEN); 275 memcpy(eh->ether_dhost, bstp_etheraddr, ETHER_ADDR_LEN); 276 eh->ether_type = htons(sizeof(bpdu)); 277 278 memcpy(mtod(m, caddr_t) + sizeof(*eh), &bpdu, sizeof(bpdu)); 279 280 bridge_enqueue(sc, ifp, m); 281 } 282 283 int 284 bstp_root_bridge(struct bridge_softc *sc) 285 { 286 return (sc->sc_designated_root == sc->sc_bridge_id); 287 } 288 289 int 290 bstp_supersedes_port_info(struct bridge_softc *sc, struct bridge_iflist *bif, 291 struct bstp_config_unit *cu) 292 { 293 if (cu->cu_rootid < bif->bif_designated_root) 294 return (1); 295 if (cu->cu_rootid > bif->bif_designated_root) 296 return (0); 297 298 if (cu->cu_root_path_cost < bif->bif_designated_cost) 299 return (1); 300 if (cu->cu_root_path_cost > bif->bif_designated_cost) 301 return (0); 302 303 if (cu->cu_bridge_id < bif->bif_designated_bridge) 304 return (1); 305 if (cu->cu_bridge_id > bif->bif_designated_bridge) 306 return (0); 307 308 if (sc->sc_bridge_id != cu->cu_bridge_id) 309 return (1); 310 if (cu->cu_port_id <= bif->bif_designated_port) 311 return (1); 312 return (0); 313 } 314 315 void 316 bstp_record_config_information(struct bridge_softc *sc, 317 struct bridge_iflist *bif, struct bstp_config_unit *cu) 318 { 319 bif->bif_designated_root = cu->cu_rootid; 320 bif->bif_designated_cost = cu->cu_root_path_cost; 321 bif->bif_designated_bridge = cu->cu_bridge_id; 322 bif->bif_designated_port = cu->cu_port_id; 323 bstp_timer_start(&bif->bif_message_age_timer, cu->cu_message_age); 324 } 325 326 void 327 bstp_record_config_timeout_values(struct bridge_softc *sc, 328 struct bstp_config_unit *config) 329 { 330 sc->sc_max_age = config->cu_max_age; 331 sc->sc_hello_time = config->cu_hello_time; 332 sc->sc_forward_delay = config->cu_forward_delay; 333 sc->sc_topology_change = config->cu_topology_change; 334 } 335 336 void 337 bstp_config_bpdu_generation(struct bridge_softc *sc) 338 { 339 struct bridge_iflist *bif; 340 341 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 342 if ((bif->bif_flags & IFBIF_STP) == 0) 343 continue; 344 if (bstp_designated_port(sc, bif) && 345 (bif->bif_state != BSTP_IFSTATE_DISABLED)) 346 bstp_transmit_config(sc, bif); 347 } 348 } 349 350 int 351 bstp_designated_port(struct bridge_softc *sc, struct bridge_iflist *bif) 352 { 353 return ((bif->bif_designated_bridge == sc->sc_bridge_id) 354 && (bif->bif_designated_port == bif->bif_port_id)); 355 } 356 357 void 358 bstp_transmit_tcn(struct bridge_softc *sc) 359 { 360 struct bstp_tbpdu bpdu; 361 struct bridge_iflist *bif = sc->sc_root_port; 362 struct ifnet *ifp = bif->bif_ifp; 363 struct ether_header *eh; 364 struct mbuf *m; 365 366 if ((ifp->if_flags & IFF_RUNNING) == 0) 367 return; 368 369 MGETHDR(m, MB_DONTWAIT, MT_DATA); 370 if (m == NULL) 371 return; 372 373 m->m_pkthdr.rcvif = ifp; 374 m->m_pkthdr.len = sizeof(*eh) + sizeof(bpdu); 375 m->m_len = m->m_pkthdr.len; 376 377 eh = mtod(m, struct ether_header *); 378 379 memcpy(eh->ether_shost, IF_LLADDR(ifp), ETHER_ADDR_LEN); 380 memcpy(eh->ether_dhost, bstp_etheraddr, ETHER_ADDR_LEN); 381 eh->ether_type = htons(sizeof(bpdu)); 382 383 bpdu.tbu_ssap = bpdu.tbu_dsap = LLC_8021D_LSAP; 384 bpdu.tbu_ctl = LLC_UI; 385 bpdu.tbu_protoid = 0; 386 bpdu.tbu_protover = 0; 387 bpdu.tbu_bpdutype = BSTP_MSGTYPE_TCN; 388 389 memcpy(mtod(m, caddr_t) + sizeof(*eh), &bpdu, sizeof(bpdu)); 390 391 bridge_enqueue(sc, ifp, m); 392 } 393 394 void 395 bstp_configuration_update(struct bridge_softc *sc) 396 { 397 bstp_root_selection(sc); 398 bstp_designated_port_selection(sc); 399 } 400 401 void 402 bstp_root_selection(struct bridge_softc *sc) 403 { 404 struct bridge_iflist *root_port = NULL, *bif; 405 406 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 407 if ((bif->bif_flags & IFBIF_STP) == 0) 408 continue; 409 if (bstp_designated_port(sc, bif)) 410 continue; 411 if (bif->bif_state == BSTP_IFSTATE_DISABLED) 412 continue; 413 if (bif->bif_designated_root >= sc->sc_bridge_id) 414 continue; 415 if (root_port == NULL) 416 goto set_port; 417 418 if (bif->bif_designated_root < root_port->bif_designated_root) 419 goto set_port; 420 if (bif->bif_designated_root > root_port->bif_designated_root) 421 continue; 422 423 if ((bif->bif_designated_cost + bif->bif_path_cost) < 424 (root_port->bif_designated_cost + root_port->bif_path_cost)) 425 goto set_port; 426 if ((bif->bif_designated_cost + bif->bif_path_cost) > 427 (root_port->bif_designated_cost + root_port->bif_path_cost)) 428 continue; 429 430 if (bif->bif_designated_bridge < 431 root_port->bif_designated_bridge) 432 goto set_port; 433 if (bif->bif_designated_bridge > 434 root_port->bif_designated_bridge) 435 continue; 436 437 if (bif->bif_designated_port < root_port->bif_designated_port) 438 goto set_port; 439 if (bif->bif_designated_port > root_port->bif_designated_port) 440 continue; 441 442 if (bif->bif_port_id >= root_port->bif_port_id) 443 continue; 444 set_port: 445 root_port = bif; 446 } 447 448 sc->sc_root_port = root_port; 449 if (root_port == NULL) { 450 sc->sc_designated_root = sc->sc_bridge_id; 451 sc->sc_root_path_cost = 0; 452 } else { 453 sc->sc_designated_root = root_port->bif_designated_root; 454 sc->sc_root_path_cost = root_port->bif_designated_cost + 455 root_port->bif_path_cost; 456 } 457 } 458 459 void 460 bstp_designated_port_selection(struct bridge_softc *sc) 461 { 462 struct bridge_iflist *bif; 463 464 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 465 if ((bif->bif_flags & IFBIF_STP) == 0) 466 continue; 467 if (bstp_designated_port(sc, bif)) 468 goto designated; 469 if (bif->bif_designated_root != sc->sc_designated_root) 470 goto designated; 471 472 if (sc->sc_root_path_cost < bif->bif_designated_cost) 473 goto designated; 474 if (sc->sc_root_path_cost > bif->bif_designated_cost) 475 continue; 476 477 if (sc->sc_bridge_id < bif->bif_designated_bridge) 478 goto designated; 479 if (sc->sc_bridge_id > bif->bif_designated_bridge) 480 continue; 481 482 if (bif->bif_port_id > bif->bif_designated_port) 483 continue; 484 designated: 485 bstp_become_designated_port(sc, bif); 486 } 487 } 488 489 void 490 bstp_become_designated_port(struct bridge_softc *sc, struct bridge_iflist *bif) 491 { 492 bif->bif_designated_root = sc->sc_designated_root; 493 bif->bif_designated_cost = sc->sc_root_path_cost; 494 bif->bif_designated_bridge = sc->sc_bridge_id; 495 bif->bif_designated_port = bif->bif_port_id; 496 } 497 498 void 499 bstp_port_state_selection(struct bridge_softc *sc) 500 { 501 struct bridge_iflist *bif; 502 503 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 504 if ((bif->bif_flags & IFBIF_STP) == 0) 505 continue; 506 if (bif == sc->sc_root_port) { 507 bif->bif_config_pending = 0; 508 bif->bif_topology_change_acknowledge = 0; 509 bstp_make_forwarding(sc, bif); 510 } else if (bstp_designated_port(sc, bif)) { 511 bstp_timer_stop(&bif->bif_message_age_timer); 512 bstp_make_forwarding(sc, bif); 513 } else { 514 bif->bif_config_pending = 0; 515 bif->bif_topology_change_acknowledge = 0; 516 bstp_make_blocking(sc, bif); 517 } 518 } 519 } 520 521 void 522 bstp_make_forwarding(struct bridge_softc *sc, struct bridge_iflist *bif) 523 { 524 if (bif->bif_state == BSTP_IFSTATE_BLOCKING) { 525 bstp_set_port_state(bif, BSTP_IFSTATE_LISTENING); 526 bstp_timer_start(&bif->bif_forward_delay_timer, 0); 527 } 528 } 529 530 void 531 bstp_make_blocking(struct bridge_softc *sc, struct bridge_iflist *bif) 532 { 533 if ((bif->bif_state != BSTP_IFSTATE_DISABLED) && 534 (bif->bif_state != BSTP_IFSTATE_BLOCKING)) { 535 if ((bif->bif_state == BSTP_IFSTATE_FORWARDING) || 536 (bif->bif_state == BSTP_IFSTATE_LEARNING)) { 537 if (bif->bif_change_detection_enabled) { 538 bstp_topology_change_detection(sc); 539 } 540 } 541 bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING); 542 bridge_rtdelete(sc, bif->bif_ifp, IFBF_FLUSHDYN); 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(IF_LLADDR(bif->bif_ifp), 825 IF_LLADDR(mif->bif_ifp), 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)IF_LLADDR(mif->bif_ifp)[0]) << 40) | 838 (((uint64_t)IF_LLADDR(mif->bif_ifp)[1]) << 32) | 839 (IF_LLADDR(mif->bif_ifp)[2] << 24) | 840 (IF_LLADDR(mif->bif_ifp)[3] << 16) | 841 (IF_LLADDR(mif->bif_ifp)[4] << 8) | 842 (IF_LLADDR(mif->bif_ifp)[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_ifupdstatus(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 bridge_rtdelete(sc, bif->bif_ifp, IFBF_FLUSHDYN); 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_linkstate(struct ifnet *ifp, int state) 1011 { 1012 struct bridge_softc *sc; 1013 struct bridge_iflist *bif; 1014 1015 sc = ifp->if_bridge; 1016 lwkt_serialize_enter(sc->sc_ifp->if_serializer); 1017 1018 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 1019 if ((bif->bif_flags & IFBIF_STP) == 0) 1020 continue; 1021 1022 if (bif->bif_ifp == ifp) { 1023 bstp_ifupdstatus(sc, bif); 1024 break; 1025 } 1026 } 1027 lwkt_serialize_exit(sc->sc_ifp->if_serializer); 1028 } 1029 1030 void 1031 bstp_ifupdstatus(struct bridge_softc *sc, struct bridge_iflist *bif) 1032 { 1033 struct ifnet *ifp = bif->bif_ifp; 1034 struct ifmediareq ifmr; 1035 int error = 0; 1036 1037 bzero((char *)&ifmr, sizeof(ifmr)); 1038 lwkt_serialize_enter(ifp->if_serializer); 1039 error = (*ifp->if_ioctl)(ifp, SIOCGIFMEDIA, (caddr_t)&ifmr, curthread->td_proc->p_ucred); 1040 lwkt_serialize_exit(ifp->if_serializer); 1041 1042 if ((error == 0) && (ifp->if_flags & IFF_UP)) { 1043 if (ifmr.ifm_status & IFM_ACTIVE) { 1044 if (bif->bif_state == BSTP_IFSTATE_DISABLED) 1045 bstp_enable_port(sc, bif); 1046 1047 } else { 1048 if (bif->bif_state != BSTP_IFSTATE_DISABLED) 1049 bstp_disable_port(sc, bif); 1050 } 1051 return; 1052 } 1053 1054 if (bif->bif_state != BSTP_IFSTATE_DISABLED) 1055 bstp_disable_port(sc, bif); 1056 } 1057 1058 void 1059 bstp_tick(void *arg) 1060 { 1061 struct bridge_softc *sc = arg; 1062 struct bridge_iflist *bif; 1063 1064 lwkt_serialize_enter(sc->sc_ifp->if_serializer); 1065 1066 #if 0 1067 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 1068 if ((bif->bif_flags & IFBIF_STP) == 0) 1069 continue; 1070 /* 1071 * XXX This can cause a lag in "link does away" 1072 * XXX and "spanning tree gets updated". We need 1073 * XXX come sort of callback from the link state 1074 * XXX update code to kick spanning tree. 1075 * XXX --thorpej@NetBSD.org 1076 */ 1077 bstp_ifupdstatus(sc, bif); 1078 } 1079 #endif 1080 1081 if (bstp_timer_expired(&sc->sc_hello_timer, sc->sc_hello_time)) 1082 bstp_hello_timer_expiry(sc); 1083 1084 if (bstp_timer_expired(&sc->sc_tcn_timer, sc->sc_bridge_hello_time)) 1085 bstp_tcn_timer_expiry(sc); 1086 1087 if (bstp_timer_expired(&sc->sc_topology_change_timer, 1088 sc->sc_topology_change_time)) 1089 bstp_topology_change_timer_expiry(sc); 1090 1091 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 1092 if ((bif->bif_flags & IFBIF_STP) == 0) 1093 continue; 1094 if (bstp_timer_expired(&bif->bif_message_age_timer, 1095 sc->sc_max_age)) 1096 bstp_message_age_timer_expiry(sc, bif); 1097 } 1098 1099 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 1100 if ((bif->bif_flags & IFBIF_STP) == 0) 1101 continue; 1102 if (bstp_timer_expired(&bif->bif_forward_delay_timer, 1103 sc->sc_forward_delay)) 1104 bstp_forward_delay_timer_expiry(sc, bif); 1105 1106 if (bstp_timer_expired(&bif->bif_hold_timer, 1107 sc->sc_hold_time)) 1108 bstp_hold_timer_expiry(sc, bif); 1109 } 1110 1111 if (sc->sc_ifp->if_flags & IFF_RUNNING) 1112 callout_reset(&sc->sc_bstpcallout, hz, bstp_tick, sc); 1113 1114 lwkt_serialize_exit(sc->sc_ifp->if_serializer); 1115 } 1116 1117 void 1118 bstp_timer_start(struct bridge_timer *t, uint16_t v) 1119 { 1120 t->value = v; 1121 t->active = 1; 1122 } 1123 1124 void 1125 bstp_timer_stop(struct bridge_timer *t) 1126 { 1127 t->value = 0; 1128 t->active = 0; 1129 } 1130 1131 int 1132 bstp_timer_expired(struct bridge_timer *t, uint16_t v) 1133 { 1134 if (t->active == 0) 1135 return (0); 1136 t->value += BSTP_TICK_VAL; 1137 if (t->value >= v) { 1138 bstp_timer_stop(t); 1139 return (1); 1140 } 1141 return (0); 1142 1143 } 1144