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