1 /* $NetBSD: bridgestp.c,v 1.23 2016/06/10 13:27:15 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.23 2016/06/10 13:27:15 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 int s; 223 224 KASSERT(BRIDGE_LOCKED(sc)); 225 226 ifp = bif->bif_ifp; 227 228 if ((ifp->if_flags & IFF_RUNNING) == 0) 229 return; 230 231 MGETHDR(m, M_DONTWAIT, MT_DATA); 232 if (m == NULL) 233 return; 234 235 eh = mtod(m, struct ether_header *); 236 237 m_set_rcvif(m, ifp); 238 m->m_pkthdr.len = sizeof(*eh) + sizeof(bpdu); 239 m->m_len = m->m_pkthdr.len; 240 241 bpdu.cbu_ssap = bpdu.cbu_dsap = LLC_8021D_LSAP; 242 bpdu.cbu_ctl = LLC_UI; 243 bpdu.cbu_protoid = htons(0); 244 bpdu.cbu_protover = 0; 245 bpdu.cbu_bpdutype = cu->cu_message_type; 246 bpdu.cbu_flags = (cu->cu_topology_change ? BSTP_FLAG_TC : 0) | 247 (cu->cu_topology_change_acknowledgment ? BSTP_FLAG_TCA : 0); 248 249 bpdu.cbu_rootpri = htons(cu->cu_rootid >> 48); 250 bpdu.cbu_rootaddr[0] = cu->cu_rootid >> 40; 251 bpdu.cbu_rootaddr[1] = cu->cu_rootid >> 32; 252 bpdu.cbu_rootaddr[2] = cu->cu_rootid >> 24; 253 bpdu.cbu_rootaddr[3] = cu->cu_rootid >> 16; 254 bpdu.cbu_rootaddr[4] = cu->cu_rootid >> 8; 255 bpdu.cbu_rootaddr[5] = cu->cu_rootid >> 0; 256 257 bpdu.cbu_rootpathcost = htonl(cu->cu_root_path_cost); 258 259 bpdu.cbu_bridgepri = htons(cu->cu_rootid >> 48); 260 bpdu.cbu_bridgeaddr[0] = cu->cu_rootid >> 40; 261 bpdu.cbu_bridgeaddr[1] = cu->cu_rootid >> 32; 262 bpdu.cbu_bridgeaddr[2] = cu->cu_rootid >> 24; 263 bpdu.cbu_bridgeaddr[3] = cu->cu_rootid >> 16; 264 bpdu.cbu_bridgeaddr[4] = cu->cu_rootid >> 8; 265 bpdu.cbu_bridgeaddr[5] = cu->cu_rootid >> 0; 266 267 bpdu.cbu_portid = htons(cu->cu_port_id); 268 bpdu.cbu_messageage = htons(cu->cu_message_age); 269 bpdu.cbu_maxage = htons(cu->cu_max_age); 270 bpdu.cbu_hellotime = htons(cu->cu_hello_time); 271 bpdu.cbu_forwarddelay = htons(cu->cu_forward_delay); 272 273 memcpy(eh->ether_shost, CLLADDR(ifp->if_sadl), ETHER_ADDR_LEN); 274 memcpy(eh->ether_dhost, bstp_etheraddr, ETHER_ADDR_LEN); 275 eh->ether_type = htons(sizeof(bpdu)); 276 277 memcpy(mtod(m, char *) + sizeof(*eh), &bpdu, sizeof(bpdu)); 278 279 BRIDGE_UNLOCK(sc); 280 s = splnet(); 281 bridge_enqueue(sc, ifp, m, 0); 282 splx(s); 283 BRIDGE_LOCK(sc); 284 } 285 286 static int 287 bstp_root_bridge(struct bridge_softc *sc) 288 { 289 return (sc->sc_designated_root == sc->sc_bridge_id); 290 } 291 292 static int 293 bstp_supersedes_port_info(struct bridge_softc *sc, struct bridge_iflist *bif, 294 struct bstp_config_unit *cu) 295 { 296 if (cu->cu_rootid < bif->bif_designated_root) 297 return (1); 298 if (cu->cu_rootid > bif->bif_designated_root) 299 return (0); 300 301 if (cu->cu_root_path_cost < bif->bif_designated_cost) 302 return (1); 303 if (cu->cu_root_path_cost > bif->bif_designated_cost) 304 return (0); 305 306 if (cu->cu_bridge_id < bif->bif_designated_bridge) 307 return (1); 308 if (cu->cu_bridge_id > bif->bif_designated_bridge) 309 return (0); 310 311 if (sc->sc_bridge_id != cu->cu_bridge_id) 312 return (1); 313 if (cu->cu_port_id <= bif->bif_designated_port) 314 return (1); 315 return (0); 316 } 317 318 static void 319 bstp_record_config_information(struct bridge_softc *sc, 320 struct bridge_iflist *bif, struct bstp_config_unit *cu) 321 { 322 bif->bif_designated_root = cu->cu_rootid; 323 bif->bif_designated_cost = cu->cu_root_path_cost; 324 bif->bif_designated_bridge = cu->cu_bridge_id; 325 bif->bif_designated_port = cu->cu_port_id; 326 bstp_timer_start(&bif->bif_message_age_timer, cu->cu_message_age); 327 } 328 329 static void 330 bstp_record_config_timeout_values(struct bridge_softc *sc, 331 struct bstp_config_unit *config) 332 { 333 sc->sc_max_age = config->cu_max_age; 334 sc->sc_hello_time = config->cu_hello_time; 335 sc->sc_forward_delay = config->cu_forward_delay; 336 sc->sc_topology_change = config->cu_topology_change; 337 } 338 339 static void 340 bstp_config_bpdu_generation(struct bridge_softc *sc) 341 { 342 struct bridge_iflist *bif; 343 344 BRIDGE_IFLIST_WRITER_FOREACH(bif, sc) { 345 if ((bif->bif_flags & IFBIF_STP) == 0) 346 continue; 347 if (bstp_designated_port(sc, bif) && 348 (bif->bif_state != BSTP_IFSTATE_DISABLED)) 349 bstp_transmit_config(sc, bif); 350 } 351 } 352 353 static int 354 bstp_designated_port(struct bridge_softc *sc, struct bridge_iflist *bif) 355 { 356 return ((bif->bif_designated_bridge == sc->sc_bridge_id) 357 && (bif->bif_designated_port == bif->bif_port_id)); 358 } 359 360 static void 361 bstp_transmit_tcn(struct bridge_softc *sc) 362 { 363 struct bstp_tbpdu bpdu; 364 struct bridge_iflist *bif = sc->sc_root_port; 365 struct ifnet *ifp; 366 struct ether_header *eh; 367 struct mbuf *m; 368 int s; 369 370 KASSERT(BRIDGE_LOCKED(sc)); 371 372 KASSERT(bif != NULL); 373 ifp = bif->bif_ifp; 374 if ((ifp->if_flags & IFF_RUNNING) == 0) 375 return; 376 377 MGETHDR(m, M_DONTWAIT, MT_DATA); 378 if (m == NULL) 379 return; 380 381 m_set_rcvif(m, ifp); 382 m->m_pkthdr.len = sizeof(*eh) + sizeof(bpdu); 383 m->m_len = m->m_pkthdr.len; 384 385 eh = mtod(m, struct ether_header *); 386 387 memcpy(eh->ether_shost, CLLADDR(ifp->if_sadl), ETHER_ADDR_LEN); 388 memcpy(eh->ether_dhost, bstp_etheraddr, ETHER_ADDR_LEN); 389 eh->ether_type = htons(sizeof(bpdu)); 390 391 bpdu.tbu_ssap = bpdu.tbu_dsap = LLC_8021D_LSAP; 392 bpdu.tbu_ctl = LLC_UI; 393 bpdu.tbu_protoid = 0; 394 bpdu.tbu_protover = 0; 395 bpdu.tbu_bpdutype = BSTP_MSGTYPE_TCN; 396 397 memcpy(mtod(m, char *) + sizeof(*eh), &bpdu, sizeof(bpdu)); 398 399 BRIDGE_UNLOCK(sc); 400 s = splnet(); 401 bridge_enqueue(sc, ifp, m, 0); 402 splx(s); 403 BRIDGE_LOCK(sc); 404 } 405 406 static void 407 bstp_configuration_update(struct bridge_softc *sc) 408 { 409 bstp_root_selection(sc); 410 bstp_designated_port_selection(sc); 411 } 412 413 static void 414 bstp_root_selection(struct bridge_softc *sc) 415 { 416 struct bridge_iflist *root_port = NULL, *bif; 417 418 BRIDGE_IFLIST_WRITER_FOREACH(bif, sc) { 419 if ((bif->bif_flags & IFBIF_STP) == 0) 420 continue; 421 if (bstp_designated_port(sc, bif)) 422 continue; 423 if (bif->bif_state == BSTP_IFSTATE_DISABLED) 424 continue; 425 if (bif->bif_designated_root >= sc->sc_bridge_id) 426 continue; 427 if (root_port == NULL) 428 goto set_port; 429 430 if (bif->bif_designated_root < root_port->bif_designated_root) 431 goto set_port; 432 if (bif->bif_designated_root > root_port->bif_designated_root) 433 continue; 434 435 if ((bif->bif_designated_cost + bif->bif_path_cost) < 436 (root_port->bif_designated_cost + root_port->bif_path_cost)) 437 goto set_port; 438 if ((bif->bif_designated_cost + bif->bif_path_cost) > 439 (root_port->bif_designated_cost + root_port->bif_path_cost)) 440 continue; 441 442 if (bif->bif_designated_bridge < 443 root_port->bif_designated_bridge) 444 goto set_port; 445 if (bif->bif_designated_bridge > 446 root_port->bif_designated_bridge) 447 continue; 448 449 if (bif->bif_designated_port < root_port->bif_designated_port) 450 goto set_port; 451 if (bif->bif_designated_port > root_port->bif_designated_port) 452 continue; 453 454 if (bif->bif_port_id >= root_port->bif_port_id) 455 continue; 456 set_port: 457 root_port = bif; 458 } 459 460 sc->sc_root_port = root_port; 461 if (root_port == NULL) { 462 sc->sc_designated_root = sc->sc_bridge_id; 463 sc->sc_root_path_cost = 0; 464 } else { 465 sc->sc_designated_root = root_port->bif_designated_root; 466 sc->sc_root_path_cost = root_port->bif_designated_cost + 467 root_port->bif_path_cost; 468 } 469 } 470 471 static void 472 bstp_designated_port_selection(struct bridge_softc *sc) 473 { 474 struct bridge_iflist *bif; 475 476 BRIDGE_IFLIST_WRITER_FOREACH(bif, sc) { 477 if ((bif->bif_flags & IFBIF_STP) == 0) 478 continue; 479 if (bstp_designated_port(sc, bif)) 480 goto designated; 481 if (bif->bif_designated_root != sc->sc_designated_root) 482 goto designated; 483 484 if (sc->sc_root_path_cost < bif->bif_designated_cost) 485 goto designated; 486 if (sc->sc_root_path_cost > bif->bif_designated_cost) 487 continue; 488 489 if (sc->sc_bridge_id < bif->bif_designated_bridge) 490 goto designated; 491 if (sc->sc_bridge_id > bif->bif_designated_bridge) 492 continue; 493 494 if (bif->bif_port_id > bif->bif_designated_port) 495 continue; 496 designated: 497 bstp_become_designated_port(sc, bif); 498 } 499 } 500 501 static void 502 bstp_become_designated_port(struct bridge_softc *sc, struct bridge_iflist *bif) 503 { 504 bif->bif_designated_root = sc->sc_designated_root; 505 bif->bif_designated_cost = sc->sc_root_path_cost; 506 bif->bif_designated_bridge = sc->sc_bridge_id; 507 bif->bif_designated_port = bif->bif_port_id; 508 } 509 510 static void 511 bstp_port_state_selection(struct bridge_softc *sc) 512 { 513 struct bridge_iflist *bif; 514 515 BRIDGE_IFLIST_WRITER_FOREACH(bif, sc) { 516 if ((bif->bif_flags & IFBIF_STP) == 0) 517 continue; 518 if (bif == sc->sc_root_port) { 519 bif->bif_config_pending = 0; 520 bif->bif_topology_change_acknowledge = 0; 521 bstp_make_forwarding(sc, bif); 522 } else if (bstp_designated_port(sc, bif)) { 523 bstp_timer_stop(&bif->bif_message_age_timer); 524 bstp_make_forwarding(sc, bif); 525 } else { 526 bif->bif_config_pending = 0; 527 bif->bif_topology_change_acknowledge = 0; 528 bstp_make_blocking(sc, bif); 529 } 530 } 531 } 532 533 static void 534 bstp_make_forwarding(struct bridge_softc *sc, 535 struct bridge_iflist *bif) 536 { 537 if (bif->bif_state == BSTP_IFSTATE_BLOCKING) { 538 bstp_set_port_state(bif, BSTP_IFSTATE_LISTENING); 539 bstp_timer_start(&bif->bif_forward_delay_timer, 0); 540 } 541 } 542 543 static void 544 bstp_make_blocking(struct bridge_softc *sc, struct bridge_iflist *bif) 545 { 546 if ((bif->bif_state != BSTP_IFSTATE_DISABLED) && 547 (bif->bif_state != BSTP_IFSTATE_BLOCKING)) { 548 if ((bif->bif_state == BSTP_IFSTATE_FORWARDING) || 549 (bif->bif_state == BSTP_IFSTATE_LEARNING)) { 550 if (bif->bif_change_detection_enabled) { 551 bstp_topology_change_detection(sc); 552 } 553 } 554 bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING); 555 bstp_timer_stop(&bif->bif_forward_delay_timer); 556 } 557 } 558 559 static void 560 bstp_set_port_state(struct bridge_iflist *bif, uint8_t state) 561 { 562 bif->bif_state = state; 563 } 564 565 static void 566 bstp_topology_change_detection(struct bridge_softc *sc) 567 { 568 if (bstp_root_bridge(sc)) { 569 sc->sc_topology_change = 1; 570 bstp_timer_start(&sc->sc_topology_change_timer, 0); 571 } else if (!sc->sc_topology_change_detected) { 572 bstp_transmit_tcn(sc); 573 bstp_timer_start(&sc->sc_tcn_timer, 0); 574 } 575 sc->sc_topology_change_detected = 1; 576 } 577 578 static void 579 bstp_topology_change_acknowledged(struct bridge_softc *sc) 580 { 581 sc->sc_topology_change_detected = 0; 582 bstp_timer_stop(&sc->sc_tcn_timer); 583 } 584 585 static void 586 bstp_acknowledge_topology_change(struct bridge_softc *sc, 587 struct bridge_iflist *bif) 588 { 589 bif->bif_topology_change_acknowledge = 1; 590 bstp_transmit_config(sc, bif); 591 } 592 593 void 594 bstp_input(struct bridge_softc *sc, struct bridge_iflist *bif, struct mbuf *m) 595 { 596 struct ether_header *eh; 597 struct bstp_tbpdu tpdu; 598 struct bstp_cbpdu cpdu; 599 struct bstp_config_unit cu; 600 struct bstp_tcn_unit tu; 601 uint16_t len; 602 603 #ifdef BRIDGE_MPSAFE 604 KASSERT(bif->bif_refs > 0); 605 #endif 606 607 eh = mtod(m, struct ether_header *); 608 609 if ((bif->bif_flags & IFBIF_STP) == 0) 610 goto out; 611 612 len = ntohs(eh->ether_type); 613 if (len < sizeof(tpdu)) 614 goto out; 615 616 m_adj(m, ETHER_HDR_LEN); 617 618 if (m->m_pkthdr.len > len) 619 m_adj(m, len - m->m_pkthdr.len); 620 if (m->m_len < sizeof(tpdu) && 621 (m = m_pullup(m, sizeof(tpdu))) == NULL) 622 goto out; 623 624 memcpy(&tpdu, mtod(m, void *), sizeof(tpdu)); 625 626 if (tpdu.tbu_dsap != LLC_8021D_LSAP || 627 tpdu.tbu_ssap != LLC_8021D_LSAP || 628 tpdu.tbu_ctl != LLC_UI) 629 goto out; 630 if (tpdu.tbu_protoid != 0 || tpdu.tbu_protover != 0) 631 goto out; 632 633 switch (tpdu.tbu_bpdutype) { 634 case BSTP_MSGTYPE_TCN: 635 tu.tu_message_type = tpdu.tbu_bpdutype; 636 637 BRIDGE_LOCK(sc); 638 bstp_received_tcn_bpdu(sc, bif, &tu); 639 BRIDGE_UNLOCK(sc); 640 641 break; 642 case BSTP_MSGTYPE_CFG: 643 if (m->m_len < sizeof(cpdu) && 644 (m = m_pullup(m, sizeof(cpdu))) == NULL) 645 goto out; 646 memcpy(&cpdu, mtod(m, void *), sizeof(cpdu)); 647 648 cu.cu_rootid = 649 (((uint64_t)ntohs(cpdu.cbu_rootpri)) << 48) | 650 (((uint64_t)cpdu.cbu_rootaddr[0]) << 40) | 651 (((uint64_t)cpdu.cbu_rootaddr[1]) << 32) | 652 (((uint64_t)cpdu.cbu_rootaddr[2]) << 24) | 653 (((uint64_t)cpdu.cbu_rootaddr[3]) << 16) | 654 (((uint64_t)cpdu.cbu_rootaddr[4]) << 8) | 655 (((uint64_t)cpdu.cbu_rootaddr[5]) << 0); 656 657 cu.cu_bridge_id = 658 (((uint64_t)ntohs(cpdu.cbu_bridgepri)) << 48) | 659 (((uint64_t)cpdu.cbu_bridgeaddr[0]) << 40) | 660 (((uint64_t)cpdu.cbu_bridgeaddr[1]) << 32) | 661 (((uint64_t)cpdu.cbu_bridgeaddr[2]) << 24) | 662 (((uint64_t)cpdu.cbu_bridgeaddr[3]) << 16) | 663 (((uint64_t)cpdu.cbu_bridgeaddr[4]) << 8) | 664 (((uint64_t)cpdu.cbu_bridgeaddr[5]) << 0); 665 666 cu.cu_root_path_cost = ntohl(cpdu.cbu_rootpathcost); 667 cu.cu_message_age = ntohs(cpdu.cbu_messageage); 668 cu.cu_max_age = ntohs(cpdu.cbu_maxage); 669 cu.cu_hello_time = ntohs(cpdu.cbu_hellotime); 670 cu.cu_forward_delay = ntohs(cpdu.cbu_forwarddelay); 671 cu.cu_port_id = ntohs(cpdu.cbu_portid); 672 cu.cu_message_type = cpdu.cbu_bpdutype; 673 cu.cu_topology_change_acknowledgment = 674 (cpdu.cbu_flags & BSTP_FLAG_TCA) ? 1 : 0; 675 cu.cu_topology_change = 676 (cpdu.cbu_flags & BSTP_FLAG_TC) ? 1 : 0; 677 678 BRIDGE_LOCK(sc); 679 bstp_received_config_bpdu(sc, bif, &cu); 680 BRIDGE_UNLOCK(sc); 681 682 break; 683 default: 684 goto out; 685 } 686 687 out: 688 if (m) 689 m_freem(m); 690 return; 691 } 692 693 static void 694 bstp_received_config_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif, 695 struct bstp_config_unit *cu) 696 { 697 int root; 698 699 root = bstp_root_bridge(sc); 700 701 if (bif->bif_state != BSTP_IFSTATE_DISABLED) { 702 if (bstp_supersedes_port_info(sc, bif, cu)) { 703 bstp_record_config_information(sc, bif, cu); 704 bstp_configuration_update(sc); 705 bstp_port_state_selection(sc); 706 707 if ((bstp_root_bridge(sc) == 0) && root) { 708 bstp_timer_stop(&sc->sc_hello_timer); 709 710 if (sc->sc_topology_change_detected) { 711 bstp_timer_stop( 712 &sc->sc_topology_change_timer); 713 bstp_transmit_tcn(sc); 714 bstp_timer_start(&sc->sc_tcn_timer, 0); 715 } 716 } 717 718 if (bif == sc->sc_root_port) { 719 bstp_record_config_timeout_values(sc, cu); 720 bstp_config_bpdu_generation(sc); 721 722 if (cu->cu_topology_change_acknowledgment) 723 bstp_topology_change_acknowledged(sc); 724 } 725 } else if (bstp_designated_port(sc, bif)) 726 bstp_transmit_config(sc, bif); 727 } 728 } 729 730 static void 731 bstp_received_tcn_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif, 732 struct bstp_tcn_unit *tcn) 733 { 734 if (bif->bif_state != BSTP_IFSTATE_DISABLED && 735 bstp_designated_port(sc, bif)) { 736 bstp_topology_change_detection(sc); 737 bstp_acknowledge_topology_change(sc, bif); 738 } 739 } 740 741 static void 742 bstp_hello_timer_expiry(struct bridge_softc *sc) 743 { 744 bstp_config_bpdu_generation(sc); 745 bstp_timer_start(&sc->sc_hello_timer, 0); 746 } 747 748 static void 749 bstp_message_age_timer_expiry(struct bridge_softc *sc, 750 struct bridge_iflist *bif) 751 { 752 int root; 753 754 root = bstp_root_bridge(sc); 755 bstp_become_designated_port(sc, bif); 756 bstp_configuration_update(sc); 757 bstp_port_state_selection(sc); 758 759 if ((bstp_root_bridge(sc)) && (root == 0)) { 760 sc->sc_max_age = sc->sc_bridge_max_age; 761 sc->sc_hello_time = sc->sc_bridge_hello_time; 762 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 763 764 bstp_topology_change_detection(sc); 765 bstp_timer_stop(&sc->sc_tcn_timer); 766 bstp_config_bpdu_generation(sc); 767 bstp_timer_start(&sc->sc_hello_timer, 0); 768 } 769 } 770 771 static void 772 bstp_forward_delay_timer_expiry(struct bridge_softc *sc, 773 struct bridge_iflist *bif) 774 { 775 if (bif->bif_state == BSTP_IFSTATE_LISTENING) { 776 bstp_set_port_state(bif, BSTP_IFSTATE_LEARNING); 777 bstp_timer_start(&bif->bif_forward_delay_timer, 0); 778 } else if (bif->bif_state == BSTP_IFSTATE_LEARNING) { 779 bstp_set_port_state(bif, BSTP_IFSTATE_FORWARDING); 780 if (bstp_designated_for_some_port(sc) && 781 bif->bif_change_detection_enabled) 782 bstp_topology_change_detection(sc); 783 } 784 } 785 786 static int 787 bstp_designated_for_some_port(struct bridge_softc *sc) 788 { 789 790 struct bridge_iflist *bif; 791 792 BRIDGE_IFLIST_WRITER_FOREACH(bif, sc) { 793 if ((bif->bif_flags & IFBIF_STP) == 0) 794 continue; 795 if (bif->bif_designated_bridge == sc->sc_bridge_id) 796 return (1); 797 } 798 return (0); 799 } 800 801 static void 802 bstp_tcn_timer_expiry(struct bridge_softc *sc) 803 { 804 bstp_transmit_tcn(sc); 805 bstp_timer_start(&sc->sc_tcn_timer, 0); 806 } 807 808 static void 809 bstp_topology_change_timer_expiry(struct bridge_softc *sc) 810 { 811 sc->sc_topology_change_detected = 0; 812 sc->sc_topology_change = 0; 813 } 814 815 static void 816 bstp_hold_timer_expiry(struct bridge_softc *sc, struct bridge_iflist *bif) 817 { 818 if (bif->bif_config_pending) 819 bstp_transmit_config(sc, bif); 820 } 821 822 void 823 bstp_initialization(struct bridge_softc *sc) 824 { 825 struct bridge_iflist *bif, *mif; 826 827 mif = NULL; 828 829 BRIDGE_LOCK(sc); 830 831 BRIDGE_IFLIST_WRITER_FOREACH(bif, sc) { 832 if ((bif->bif_flags & IFBIF_STP) == 0) 833 continue; 834 if (bif->bif_ifp->if_type != IFT_ETHER) 835 continue; 836 bif->bif_port_id = (bif->bif_priority << 8) | 837 (bif->bif_ifp->if_index & 0xff); 838 839 if (mif == NULL) { 840 mif = bif; 841 continue; 842 } 843 if (memcmp(CLLADDR(bif->bif_ifp->if_sadl), 844 CLLADDR(mif->bif_ifp->if_sadl), ETHER_ADDR_LEN) < 0) { 845 mif = bif; 846 continue; 847 } 848 } 849 850 if (mif == NULL) { 851 BRIDGE_UNLOCK(sc); 852 bstp_stop(sc); 853 return; 854 } 855 856 sc->sc_bridge_id = 857 (((uint64_t)sc->sc_bridge_priority) << 48) | 858 (((uint64_t)(uint8_t)CLLADDR(mif->bif_ifp->if_sadl)[0]) << 40) | 859 (((uint64_t)(uint8_t)CLLADDR(mif->bif_ifp->if_sadl)[1]) << 32) | 860 (((uint64_t)(uint8_t)CLLADDR(mif->bif_ifp->if_sadl)[2]) << 24) | 861 (((uint64_t)(uint8_t)CLLADDR(mif->bif_ifp->if_sadl)[3]) << 16) | 862 (((uint64_t)(uint8_t)CLLADDR(mif->bif_ifp->if_sadl)[4]) << 8) | 863 (((uint64_t)(uint8_t)CLLADDR(mif->bif_ifp->if_sadl)[5]) << 0); 864 865 BRIDGE_UNLOCK(sc); 866 867 sc->sc_designated_root = sc->sc_bridge_id; 868 sc->sc_root_path_cost = 0; 869 sc->sc_root_port = NULL; 870 871 sc->sc_max_age = sc->sc_bridge_max_age; 872 sc->sc_hello_time = sc->sc_bridge_hello_time; 873 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 874 sc->sc_topology_change_detected = 0; 875 sc->sc_topology_change = 0; 876 bstp_timer_stop(&sc->sc_tcn_timer); 877 bstp_timer_stop(&sc->sc_topology_change_timer); 878 879 if (callout_pending(&sc->sc_bstpcallout) == 0) 880 callout_reset(&sc->sc_bstpcallout, hz, 881 bstp_tick, sc); 882 883 BRIDGE_LOCK(sc); 884 885 BRIDGE_IFLIST_WRITER_FOREACH(bif, sc) { 886 if (bif->bif_flags & IFBIF_STP) 887 bstp_enable_port(sc, bif); 888 else 889 bstp_disable_port(sc, bif); 890 } 891 892 bstp_port_state_selection(sc); 893 bstp_config_bpdu_generation(sc); 894 bstp_timer_start(&sc->sc_hello_timer, 0); 895 896 BRIDGE_UNLOCK(sc); 897 } 898 899 void 900 bstp_stop(struct bridge_softc *sc) 901 { 902 struct bridge_iflist *bif; 903 904 BRIDGE_LOCK(sc); 905 BRIDGE_IFLIST_WRITER_FOREACH(bif, sc) { 906 bstp_set_port_state(bif, BSTP_IFSTATE_DISABLED); 907 bstp_timer_stop(&bif->bif_hold_timer); 908 bstp_timer_stop(&bif->bif_message_age_timer); 909 bstp_timer_stop(&bif->bif_forward_delay_timer); 910 } 911 BRIDGE_UNLOCK(sc); 912 913 callout_stop(&sc->sc_bstpcallout); 914 915 bstp_timer_stop(&sc->sc_topology_change_timer); 916 bstp_timer_stop(&sc->sc_tcn_timer); 917 bstp_timer_stop(&sc->sc_hello_timer); 918 919 } 920 921 static void 922 bstp_initialize_port(struct bridge_softc *sc, struct bridge_iflist *bif) 923 { 924 bstp_become_designated_port(sc, bif); 925 bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING); 926 bif->bif_topology_change_acknowledge = 0; 927 bif->bif_config_pending = 0; 928 bif->bif_change_detection_enabled = 1; 929 bstp_timer_stop(&bif->bif_message_age_timer); 930 bstp_timer_stop(&bif->bif_forward_delay_timer); 931 bstp_timer_stop(&bif->bif_hold_timer); 932 } 933 934 static void 935 bstp_enable_port(struct bridge_softc *sc, struct bridge_iflist *bif) 936 { 937 bstp_initialize_port(sc, bif); 938 bstp_port_state_selection(sc); 939 } 940 941 static void 942 bstp_disable_port(struct bridge_softc *sc, struct bridge_iflist *bif) 943 { 944 int root; 945 946 root = bstp_root_bridge(sc); 947 bstp_become_designated_port(sc, bif); 948 bstp_set_port_state(bif, BSTP_IFSTATE_DISABLED); 949 bif->bif_topology_change_acknowledge = 0; 950 bif->bif_config_pending = 0; 951 bstp_timer_stop(&bif->bif_message_age_timer); 952 bstp_timer_stop(&bif->bif_forward_delay_timer); 953 bstp_configuration_update(sc); 954 bstp_port_state_selection(sc); 955 956 if (bstp_root_bridge(sc) && (root == 0)) { 957 sc->sc_max_age = sc->sc_bridge_max_age; 958 sc->sc_hello_time = sc->sc_bridge_hello_time; 959 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 960 961 bstp_topology_change_detection(sc); 962 bstp_timer_stop(&sc->sc_tcn_timer); 963 bstp_config_bpdu_generation(sc); 964 bstp_timer_start(&sc->sc_hello_timer, 0); 965 } 966 } 967 968 #if notused 969 static void 970 bstp_set_bridge_priority(struct bridge_softc *sc, uint64_t new_bridge_id) 971 { 972 struct bridge_iflist *bif; 973 int root; 974 975 root = bstp_root_bridge(sc); 976 977 BRIDGE_IFLIST_WRITER_FOREACH(bif, sc) { 978 if ((bif->bif_flags & IFBIF_STP) == 0) 979 continue; 980 if (bstp_designated_port(sc, bif)) 981 bif->bif_designated_bridge = new_bridge_id; 982 } 983 984 sc->sc_bridge_id = new_bridge_id; 985 986 bstp_configuration_update(sc); 987 bstp_port_state_selection(sc); 988 989 if (bstp_root_bridge(sc) && (root == 0)) { 990 sc->sc_max_age = sc->sc_bridge_max_age; 991 sc->sc_hello_time = sc->sc_bridge_hello_time; 992 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 993 994 bstp_topology_change_detection(sc); 995 bstp_timer_stop(&sc->sc_tcn_timer); 996 bstp_config_bpdu_generation(sc); 997 bstp_timer_start(&sc->sc_hello_timer, 0); 998 } 999 } 1000 1001 static void 1002 bstp_set_port_priority(struct bridge_softc *sc, struct bridge_iflist *bif, 1003 uint16_t new_port_id) 1004 { 1005 if (bstp_designated_port(sc, bif)) 1006 bif->bif_designated_port = new_port_id; 1007 1008 bif->bif_port_id = new_port_id; 1009 1010 if ((sc->sc_bridge_id == bif->bif_designated_bridge) && 1011 (bif->bif_port_id < bif->bif_designated_port)) { 1012 bstp_become_designated_port(sc, bif); 1013 bstp_port_state_selection(sc); 1014 } 1015 } 1016 1017 static void 1018 bstp_set_path_cost(struct bridge_softc *sc, struct bridge_iflist *bif, 1019 uint32_t path_cost) 1020 { 1021 bif->bif_path_cost = path_cost; 1022 bstp_configuration_update(sc); 1023 bstp_port_state_selection(sc); 1024 } 1025 #endif 1026 1027 static void 1028 bstp_ifupdstatus(struct bridge_softc *sc, struct bridge_iflist *bif) 1029 { 1030 struct ifnet *ifp = bif->bif_ifp; 1031 1032 if (ifp->if_flags & IFF_UP) { 1033 switch (ifp->if_link_state) { 1034 case LINK_STATE_UNKNOWN: 1035 /* 1036 * Just enable the port if the link state is 1037 * unknown. 1038 */ 1039 if (bif->bif_state == BSTP_IFSTATE_DISABLED) 1040 bstp_enable_port(sc, bif); 1041 break; 1042 1043 case LINK_STATE_UP: 1044 if (bif->bif_state == BSTP_IFSTATE_DISABLED) 1045 bstp_enable_port(sc, bif); 1046 break; 1047 1048 case LINK_STATE_DOWN: 1049 if (bif->bif_state != BSTP_IFSTATE_DISABLED) 1050 bstp_disable_port(sc, bif); 1051 break; 1052 } 1053 return; 1054 } 1055 1056 if (bif->bif_state != BSTP_IFSTATE_DISABLED) 1057 bstp_disable_port(sc, bif); 1058 } 1059 1060 static void 1061 bstp_tick(void *arg) 1062 { 1063 struct bridge_softc *sc = arg; 1064 struct bridge_iflist *bif; 1065 int s; 1066 1067 s = splnet(); 1068 BRIDGE_LOCK(sc); 1069 1070 BRIDGE_IFLIST_WRITER_FOREACH(bif, sc) { 1071 if ((bif->bif_flags & IFBIF_STP) == 0) 1072 continue; 1073 /* 1074 * XXX This can cause a lag in "link does away" 1075 * XXX and "spanning tree gets updated". We need 1076 * XXX come sort of callback from the link state 1077 * XXX update code to kick spanning tree. 1078 * XXX --thorpej@NetBSD.org 1079 */ 1080 bstp_ifupdstatus(sc, bif); 1081 } 1082 1083 if (bstp_timer_expired(&sc->sc_hello_timer, sc->sc_hello_time)) 1084 bstp_hello_timer_expiry(sc); 1085 1086 if (bstp_timer_expired(&sc->sc_tcn_timer, sc->sc_bridge_hello_time)) 1087 bstp_tcn_timer_expiry(sc); 1088 1089 if (bstp_timer_expired(&sc->sc_topology_change_timer, 1090 sc->sc_topology_change_time)) 1091 bstp_topology_change_timer_expiry(sc); 1092 1093 BRIDGE_IFLIST_WRITER_FOREACH(bif, sc) { 1094 if ((bif->bif_flags & IFBIF_STP) == 0) 1095 continue; 1096 if (bstp_timer_expired(&bif->bif_message_age_timer, 1097 sc->sc_max_age)) 1098 bstp_message_age_timer_expiry(sc, bif); 1099 } 1100 1101 BRIDGE_IFLIST_WRITER_FOREACH(bif, sc) { 1102 if ((bif->bif_flags & IFBIF_STP) == 0) 1103 continue; 1104 if (bstp_timer_expired(&bif->bif_forward_delay_timer, 1105 sc->sc_forward_delay)) 1106 bstp_forward_delay_timer_expiry(sc, bif); 1107 1108 if (bstp_timer_expired(&bif->bif_hold_timer, 1109 sc->sc_hold_time)) 1110 bstp_hold_timer_expiry(sc, bif); 1111 } 1112 1113 if (sc->sc_if.if_flags & IFF_RUNNING) 1114 callout_reset(&sc->sc_bstpcallout, hz, bstp_tick, sc); 1115 1116 BRIDGE_UNLOCK(sc); 1117 splx(s); 1118 } 1119 1120 static void 1121 bstp_timer_start(struct bridge_timer *t, uint16_t v) 1122 { 1123 t->value = v; 1124 t->active = 1; 1125 } 1126 1127 static void 1128 bstp_timer_stop(struct bridge_timer *t) 1129 { 1130 t->value = 0; 1131 t->active = 0; 1132 } 1133 1134 static int 1135 bstp_timer_expired(struct bridge_timer *t, uint16_t v) 1136 { 1137 if (t->active == 0) 1138 return (0); 1139 t->value += BSTP_TICK_VAL; 1140 if (t->value >= v) { 1141 bstp_timer_stop(t); 1142 return (1); 1143 } 1144 return (0); 1145 1146 } 1147