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