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