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