1 /* 2 * Copyright (c) 2000 Jason L. Wright (jason@thought.net) 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. All advertising materials mentioning features or use of this software 14 * must display the following acknowledgement: 15 * This product includes software developed by Jason L. Wright 16 * 4. The name of the author may not be used to endorse or promote products 17 * derived from this software without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 20 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 21 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 22 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, 23 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 24 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 25 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 27 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 28 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 * 31 * $OpenBSD: bridgestp.c,v 1.5 2001/03/22 03:48:29 jason Exp $ 32 * $NetBSD: bridgestp.c,v 1.5 2003/11/28 08:56:48 keihan Exp $ 33 * $FreeBSD: src/sys/net/bridgestp.c,v 1.7 2005/10/11 02:58:32 thompsa Exp $ 34 * $DragonFly: src/sys/net/bridge/bridgestp.c,v 1.5 2008/06/14 07:58:46 sephe Exp $ 35 */ 36 37 /* 38 * Implementation of the spanning tree protocol as defined in 39 * ISO/IEC Final DIS 15802-3 (IEEE P802.1D/D17), May 25, 1998. 40 * (In English: IEEE 802.1D, Draft 17, 1998) 41 */ 42 43 #include <sys/cdefs.h> 44 45 #include <sys/param.h> 46 #include <sys/systm.h> 47 #include <sys/mbuf.h> 48 #include <sys/socket.h> 49 #include <sys/sockio.h> 50 #include <sys/kernel.h> 51 #include <sys/callout.h> 52 #include <sys/proc.h> 53 #include <sys/lock.h> 54 #include <sys/thread.h> 55 #include <sys/thread2.h> 56 57 #include <net/if.h> 58 #include <net/if_dl.h> 59 #include <net/if_types.h> 60 #include <net/if_llc.h> 61 #include <net/if_media.h> 62 63 #include <netinet/in.h> 64 #include <netinet/in_systm.h> 65 #include <netinet/in_var.h> 66 #include <netinet/if_ether.h> 67 #include <net/bridge/if_bridgevar.h> 68 69 /* BPDU message types */ 70 #define BSTP_MSGTYPE_CFG 0x00 /* Configuration */ 71 #define BSTP_MSGTYPE_TCN 0x80 /* Topology chg notification */ 72 73 /* BPDU flags */ 74 #define BSTP_FLAG_TC 0x01 /* Topology change */ 75 #define BSTP_FLAG_TCA 0x80 /* Topology change ack */ 76 77 #define BSTP_MESSAGE_AGE_INCR (1 * 256) /* in 256ths of a second */ 78 #define BSTP_TICK_VAL (1 * 256) /* in 256ths of a second */ 79 80 /* 81 * Because BPDU's do not make nicely aligned structures, two different 82 * declarations are used: bstp_?bpdu (wire representation, packed) and 83 * bstp_*_unit (internal, nicely aligned version). 84 */ 85 86 /* configuration bridge protocol data unit */ 87 struct bstp_cbpdu { 88 uint8_t cbu_dsap; /* LLC: destination sap */ 89 uint8_t cbu_ssap; /* LLC: source sap */ 90 uint8_t cbu_ctl; /* LLC: control */ 91 uint16_t cbu_protoid; /* protocol id */ 92 uint8_t cbu_protover; /* protocol version */ 93 uint8_t cbu_bpdutype; /* message type */ 94 uint8_t cbu_flags; /* flags (below) */ 95 96 /* root id */ 97 uint16_t cbu_rootpri; /* root priority */ 98 uint8_t cbu_rootaddr[6]; /* root address */ 99 100 uint32_t cbu_rootpathcost; /* root path cost */ 101 102 /* bridge id */ 103 uint16_t cbu_bridgepri; /* bridge priority */ 104 uint8_t cbu_bridgeaddr[6]; /* bridge address */ 105 106 uint16_t cbu_portid; /* port id */ 107 uint16_t cbu_messageage; /* current message age */ 108 uint16_t cbu_maxage; /* maximum age */ 109 uint16_t cbu_hellotime; /* hello time */ 110 uint16_t cbu_forwarddelay; /* forwarding delay */ 111 } __attribute__((__packed__)); 112 113 /* topology change notification bridge protocol data unit */ 114 struct bstp_tbpdu { 115 uint8_t tbu_dsap; /* LLC: destination sap */ 116 uint8_t tbu_ssap; /* LLC: source sap */ 117 uint8_t tbu_ctl; /* LLC: control */ 118 uint16_t tbu_protoid; /* protocol id */ 119 uint8_t tbu_protover; /* protocol version */ 120 uint8_t tbu_bpdutype; /* message type */ 121 } __attribute__((__packed__)); 122 123 const uint8_t bstp_etheraddr[] = { 0x01, 0x80, 0xc2, 0x00, 0x00, 0x00 }; 124 125 static void bstp_initialize_port(struct bridge_softc *, 126 struct bridge_iflist *); 127 static void bstp_ifupdstatus(struct bridge_softc *, struct bridge_iflist *); 128 static void bstp_enable_port(struct bridge_softc *, struct bridge_iflist *); 129 static void bstp_disable_port(struct bridge_softc *, 130 struct bridge_iflist *); 131 #ifdef notused 132 static void bstp_enable_change_detection(struct bridge_iflist *); 133 static void bstp_disable_change_detection(struct bridge_iflist *); 134 #endif /* notused */ 135 static int bstp_root_bridge(struct bridge_softc *sc); 136 static int bstp_supersedes_port_info(struct bridge_softc *, 137 struct bridge_iflist *, struct bstp_config_unit *); 138 static int bstp_designated_port(struct bridge_softc *, 139 struct bridge_iflist *); 140 static int bstp_designated_for_some_port(struct bridge_softc *); 141 static void bstp_transmit_config(struct bridge_softc *, 142 struct bridge_iflist *); 143 static void bstp_transmit_tcn(struct bridge_softc *); 144 static void bstp_received_config_bpdu(struct bridge_softc *, 145 struct bridge_iflist *, struct bstp_config_unit *); 146 static void bstp_received_tcn_bpdu(struct bridge_softc *, 147 struct bridge_iflist *, struct bstp_tcn_unit *); 148 static void bstp_record_config_information(struct bridge_softc *, 149 struct bridge_iflist *, struct bstp_config_unit *); 150 static void bstp_record_config_timeout_values(struct bridge_softc *, 151 struct bstp_config_unit *); 152 static void bstp_config_bpdu_generation(struct bridge_softc *); 153 static void bstp_send_config_bpdu(struct bridge_softc *, 154 struct bridge_iflist *, struct bstp_config_unit *); 155 static void bstp_configuration_update(struct bridge_softc *); 156 static void bstp_root_selection(struct bridge_softc *); 157 static void bstp_designated_port_selection(struct bridge_softc *); 158 static void bstp_become_designated_port(struct bridge_softc *, 159 struct bridge_iflist *); 160 static void bstp_port_state_selection(struct bridge_softc *); 161 static void bstp_make_forwarding(struct bridge_softc *, 162 struct bridge_iflist *); 163 static void bstp_make_blocking(struct bridge_softc *, 164 struct bridge_iflist *); 165 static void bstp_set_port_state(struct bridge_iflist *, uint8_t); 166 #ifdef notused 167 static void bstp_set_bridge_priority(struct bridge_softc *, uint64_t); 168 static void bstp_set_port_priority(struct bridge_softc *, 169 struct bridge_iflist *, uint16_t); 170 static void bstp_set_path_cost(struct bridge_softc *, 171 struct bridge_iflist *, uint32_t); 172 #endif /* notused */ 173 static void bstp_topology_change_detection(struct bridge_softc *); 174 static void bstp_topology_change_acknowledged(struct bridge_softc *); 175 static void bstp_acknowledge_topology_change(struct bridge_softc *, 176 struct bridge_iflist *); 177 178 static void bstp_tick(void *); 179 static void bstp_timer_start(struct bridge_timer *, uint16_t); 180 static void bstp_timer_stop(struct bridge_timer *); 181 static int bstp_timer_expired(struct bridge_timer *, uint16_t); 182 183 static void bstp_hold_timer_expiry(struct bridge_softc *, 184 struct bridge_iflist *); 185 static void bstp_message_age_timer_expiry(struct bridge_softc *, 186 struct bridge_iflist *); 187 static void bstp_forward_delay_timer_expiry(struct bridge_softc *, 188 struct bridge_iflist *); 189 static void bstp_topology_change_timer_expiry(struct bridge_softc *); 190 static void bstp_tcn_timer_expiry(struct bridge_softc *); 191 static void bstp_hello_timer_expiry(struct bridge_softc *); 192 static int bstp_addr_cmp(const uint8_t *, const uint8_t *); 193 194 static void 195 bstp_transmit_config(struct bridge_softc *sc, struct bridge_iflist *bif) 196 { 197 if (bif->bif_hold_timer.active) { 198 bif->bif_config_pending = 1; 199 return; 200 } 201 202 bif->bif_config_bpdu.cu_message_type = BSTP_MSGTYPE_CFG; 203 bif->bif_config_bpdu.cu_rootid = sc->sc_designated_root; 204 bif->bif_config_bpdu.cu_root_path_cost = sc->sc_root_path_cost; 205 bif->bif_config_bpdu.cu_bridge_id = sc->sc_bridge_id; 206 bif->bif_config_bpdu.cu_port_id = bif->bif_port_id; 207 208 if (bstp_root_bridge(sc)) 209 bif->bif_config_bpdu.cu_message_age = 0; 210 else 211 bif->bif_config_bpdu.cu_message_age = 212 sc->sc_root_port->bif_message_age_timer.value + 213 BSTP_MESSAGE_AGE_INCR; 214 215 bif->bif_config_bpdu.cu_max_age = sc->sc_max_age; 216 bif->bif_config_bpdu.cu_hello_time = sc->sc_hello_time; 217 bif->bif_config_bpdu.cu_forward_delay = sc->sc_forward_delay; 218 bif->bif_config_bpdu.cu_topology_change_acknowledgment 219 = bif->bif_topology_change_acknowledge; 220 bif->bif_config_bpdu.cu_topology_change = sc->sc_topology_change; 221 222 if (bif->bif_config_bpdu.cu_message_age < sc->sc_max_age) { 223 bif->bif_topology_change_acknowledge = 0; 224 bif->bif_config_pending = 0; 225 bstp_send_config_bpdu(sc, bif, &bif->bif_config_bpdu); 226 bstp_timer_start(&bif->bif_hold_timer, 0); 227 } 228 } 229 230 static void 231 bstp_send_config_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif, 232 struct bstp_config_unit *cu) 233 { 234 struct ifnet *ifp; 235 struct mbuf *m; 236 struct ether_header *eh; 237 struct bstp_cbpdu bpdu; 238 239 ifp = bif->bif_ifp; 240 241 if ((ifp->if_flags & IFF_RUNNING) == 0) 242 return; 243 244 MGETHDR(m, MB_DONTWAIT, MT_DATA); 245 if (m == NULL) 246 return; 247 248 eh = mtod(m, struct ether_header *); 249 250 m->m_pkthdr.rcvif = ifp; 251 m->m_pkthdr.len = sizeof(*eh) + sizeof(bpdu); 252 m->m_len = m->m_pkthdr.len; 253 254 bpdu.cbu_ssap = bpdu.cbu_dsap = LLC_8021D_LSAP; 255 bpdu.cbu_ctl = LLC_UI; 256 bpdu.cbu_protoid = htons(0); 257 bpdu.cbu_protover = 0; 258 bpdu.cbu_bpdutype = cu->cu_message_type; 259 bpdu.cbu_flags = (cu->cu_topology_change ? BSTP_FLAG_TC : 0) | 260 (cu->cu_topology_change_acknowledgment ? BSTP_FLAG_TCA : 0); 261 262 bpdu.cbu_rootpri = htons(cu->cu_rootid >> 48); 263 bpdu.cbu_rootaddr[0] = cu->cu_rootid >> 40; 264 bpdu.cbu_rootaddr[1] = cu->cu_rootid >> 32; 265 bpdu.cbu_rootaddr[2] = cu->cu_rootid >> 24; 266 bpdu.cbu_rootaddr[3] = cu->cu_rootid >> 16; 267 bpdu.cbu_rootaddr[4] = cu->cu_rootid >> 8; 268 bpdu.cbu_rootaddr[5] = cu->cu_rootid >> 0; 269 270 bpdu.cbu_rootpathcost = htonl(cu->cu_root_path_cost); 271 272 bpdu.cbu_bridgepri = htons(cu->cu_bridge_id >> 48); 273 bpdu.cbu_bridgeaddr[0] = cu->cu_bridge_id >> 40; 274 bpdu.cbu_bridgeaddr[1] = cu->cu_bridge_id >> 32; 275 bpdu.cbu_bridgeaddr[2] = cu->cu_bridge_id >> 24; 276 bpdu.cbu_bridgeaddr[3] = cu->cu_bridge_id >> 16; 277 bpdu.cbu_bridgeaddr[4] = cu->cu_bridge_id >> 8; 278 bpdu.cbu_bridgeaddr[5] = cu->cu_bridge_id >> 0; 279 280 bpdu.cbu_portid = htons(cu->cu_port_id); 281 bpdu.cbu_messageage = htons(cu->cu_message_age); 282 bpdu.cbu_maxage = htons(cu->cu_max_age); 283 bpdu.cbu_hellotime = htons(cu->cu_hello_time); 284 bpdu.cbu_forwarddelay = htons(cu->cu_forward_delay); 285 286 memcpy(eh->ether_shost, IF_LLADDR(ifp), ETHER_ADDR_LEN); 287 memcpy(eh->ether_dhost, bstp_etheraddr, ETHER_ADDR_LEN); 288 eh->ether_type = htons(sizeof(bpdu)); 289 290 memcpy(mtod(m, caddr_t) + sizeof(*eh), &bpdu, sizeof(bpdu)); 291 292 bridge_enqueue(ifp, m); 293 } 294 295 static int 296 bstp_root_bridge(struct bridge_softc *sc) 297 { 298 return (sc->sc_designated_root == sc->sc_bridge_id); 299 } 300 301 static int 302 bstp_supersedes_port_info(struct bridge_softc *sc, struct bridge_iflist *bif, 303 struct bstp_config_unit *cu) 304 { 305 if (cu->cu_rootid < bif->bif_designated_root) 306 return (1); 307 if (cu->cu_rootid > bif->bif_designated_root) 308 return (0); 309 310 if (cu->cu_root_path_cost < bif->bif_designated_cost) 311 return (1); 312 if (cu->cu_root_path_cost > bif->bif_designated_cost) 313 return (0); 314 315 if (cu->cu_bridge_id < bif->bif_designated_bridge) 316 return (1); 317 if (cu->cu_bridge_id > bif->bif_designated_bridge) 318 return (0); 319 320 if (sc->sc_bridge_id != cu->cu_bridge_id) 321 return (1); 322 if (cu->cu_port_id <= bif->bif_designated_port) 323 return (1); 324 return (0); 325 } 326 327 static void 328 bstp_record_config_information(struct bridge_softc *sc, 329 struct bridge_iflist *bif, struct bstp_config_unit *cu) 330 { 331 bif->bif_designated_root = cu->cu_rootid; 332 bif->bif_designated_cost = cu->cu_root_path_cost; 333 bif->bif_designated_bridge = cu->cu_bridge_id; 334 bif->bif_designated_port = cu->cu_port_id; 335 bstp_timer_start(&bif->bif_message_age_timer, cu->cu_message_age); 336 } 337 338 static void 339 bstp_record_config_timeout_values(struct bridge_softc *sc, 340 struct bstp_config_unit *config) 341 { 342 sc->sc_max_age = config->cu_max_age; 343 sc->sc_hello_time = config->cu_hello_time; 344 sc->sc_forward_delay = config->cu_forward_delay; 345 sc->sc_topology_change = config->cu_topology_change; 346 } 347 348 static void 349 bstp_config_bpdu_generation(struct bridge_softc *sc) 350 { 351 struct bridge_iflist *bif; 352 353 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 354 if ((bif->bif_flags & IFBIF_STP) == 0) 355 continue; 356 if (bstp_designated_port(sc, bif) && 357 (bif->bif_state != BSTP_IFSTATE_DISABLED)) 358 bstp_transmit_config(sc, bif); 359 } 360 } 361 362 static int 363 bstp_designated_port(struct bridge_softc *sc, struct bridge_iflist *bif) 364 { 365 return ((bif->bif_designated_bridge == sc->sc_bridge_id) 366 && (bif->bif_designated_port == bif->bif_port_id)); 367 } 368 369 static void 370 bstp_transmit_tcn(struct bridge_softc *sc) 371 { 372 struct bstp_tbpdu bpdu; 373 struct bridge_iflist *bif = sc->sc_root_port; 374 struct ifnet *ifp = bif->bif_ifp; 375 struct ether_header *eh; 376 struct mbuf *m; 377 378 if ((ifp->if_flags & IFF_RUNNING) == 0) 379 return; 380 381 MGETHDR(m, MB_DONTWAIT, MT_DATA); 382 if (m == NULL) 383 return; 384 385 m->m_pkthdr.rcvif = ifp; 386 m->m_pkthdr.len = sizeof(*eh) + sizeof(bpdu); 387 m->m_len = m->m_pkthdr.len; 388 389 eh = mtod(m, struct ether_header *); 390 391 memcpy(eh->ether_shost, IF_LLADDR(ifp), ETHER_ADDR_LEN); 392 memcpy(eh->ether_dhost, bstp_etheraddr, ETHER_ADDR_LEN); 393 eh->ether_type = htons(sizeof(bpdu)); 394 395 bpdu.tbu_ssap = bpdu.tbu_dsap = LLC_8021D_LSAP; 396 bpdu.tbu_ctl = LLC_UI; 397 bpdu.tbu_protoid = 0; 398 bpdu.tbu_protover = 0; 399 bpdu.tbu_bpdutype = BSTP_MSGTYPE_TCN; 400 401 memcpy(mtod(m, caddr_t) + sizeof(*eh), &bpdu, sizeof(bpdu)); 402 403 bridge_enqueue(ifp, m); 404 } 405 406 static void 407 bstp_configuration_update(struct bridge_softc *sc) 408 { 409 bstp_root_selection(sc); 410 bstp_designated_port_selection(sc); 411 } 412 413 static void 414 bstp_root_selection(struct bridge_softc *sc) 415 { 416 struct bridge_iflist *root_port = NULL, *bif; 417 418 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 419 if ((bif->bif_flags & IFBIF_STP) == 0) 420 continue; 421 if (bstp_designated_port(sc, bif)) 422 continue; 423 if (bif->bif_state == BSTP_IFSTATE_DISABLED) 424 continue; 425 if (bif->bif_designated_root >= sc->sc_bridge_id) 426 continue; 427 if (root_port == NULL) 428 goto set_port; 429 430 if (bif->bif_designated_root < root_port->bif_designated_root) 431 goto set_port; 432 if (bif->bif_designated_root > root_port->bif_designated_root) 433 continue; 434 435 if ((bif->bif_designated_cost + bif->bif_path_cost) < 436 (root_port->bif_designated_cost + root_port->bif_path_cost)) 437 goto set_port; 438 if ((bif->bif_designated_cost + bif->bif_path_cost) > 439 (root_port->bif_designated_cost + root_port->bif_path_cost)) 440 continue; 441 442 if (bif->bif_designated_bridge < 443 root_port->bif_designated_bridge) 444 goto set_port; 445 if (bif->bif_designated_bridge > 446 root_port->bif_designated_bridge) 447 continue; 448 449 if (bif->bif_designated_port < root_port->bif_designated_port) 450 goto set_port; 451 if (bif->bif_designated_port > root_port->bif_designated_port) 452 continue; 453 454 if (bif->bif_port_id >= root_port->bif_port_id) 455 continue; 456 set_port: 457 root_port = bif; 458 } 459 460 sc->sc_root_port = root_port; 461 if (root_port == NULL) { 462 sc->sc_designated_root = sc->sc_bridge_id; 463 sc->sc_root_path_cost = 0; 464 } else { 465 sc->sc_designated_root = root_port->bif_designated_root; 466 sc->sc_root_path_cost = root_port->bif_designated_cost + 467 root_port->bif_path_cost; 468 } 469 } 470 471 static void 472 bstp_designated_port_selection(struct bridge_softc *sc) 473 { 474 struct bridge_iflist *bif; 475 476 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 477 if ((bif->bif_flags & IFBIF_STP) == 0) 478 continue; 479 if (bstp_designated_port(sc, bif)) 480 goto designated; 481 if (bif->bif_designated_root != sc->sc_designated_root) 482 goto designated; 483 484 if (sc->sc_root_path_cost < bif->bif_designated_cost) 485 goto designated; 486 if (sc->sc_root_path_cost > bif->bif_designated_cost) 487 continue; 488 489 if (sc->sc_bridge_id < bif->bif_designated_bridge) 490 goto designated; 491 if (sc->sc_bridge_id > bif->bif_designated_bridge) 492 continue; 493 494 if (bif->bif_port_id > bif->bif_designated_port) 495 continue; 496 designated: 497 bstp_become_designated_port(sc, bif); 498 } 499 } 500 501 static void 502 bstp_become_designated_port(struct bridge_softc *sc, struct bridge_iflist *bif) 503 { 504 bif->bif_designated_root = sc->sc_designated_root; 505 bif->bif_designated_cost = sc->sc_root_path_cost; 506 bif->bif_designated_bridge = sc->sc_bridge_id; 507 bif->bif_designated_port = bif->bif_port_id; 508 } 509 510 static void 511 bstp_port_state_selection(struct bridge_softc *sc) 512 { 513 struct bridge_iflist *bif; 514 515 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 516 if ((bif->bif_flags & IFBIF_STP) == 0) 517 continue; 518 if (bif == sc->sc_root_port) { 519 bif->bif_config_pending = 0; 520 bif->bif_topology_change_acknowledge = 0; 521 bstp_make_forwarding(sc, bif); 522 } else if (bstp_designated_port(sc, bif)) { 523 bstp_timer_stop(&bif->bif_message_age_timer); 524 bstp_make_forwarding(sc, bif); 525 } else { 526 bif->bif_config_pending = 0; 527 bif->bif_topology_change_acknowledge = 0; 528 bstp_make_blocking(sc, bif); 529 } 530 } 531 } 532 533 static void 534 bstp_make_forwarding(struct bridge_softc *sc, struct bridge_iflist *bif) 535 { 536 if (bif->bif_state == BSTP_IFSTATE_BLOCKING) { 537 bstp_set_port_state(bif, BSTP_IFSTATE_LISTENING); 538 bstp_timer_start(&bif->bif_forward_delay_timer, 0); 539 } 540 } 541 542 static void 543 bstp_make_blocking(struct bridge_softc *sc, struct bridge_iflist *bif) 544 { 545 if ((bif->bif_state != BSTP_IFSTATE_DISABLED) && 546 (bif->bif_state != BSTP_IFSTATE_BLOCKING)) { 547 if ((bif->bif_state == BSTP_IFSTATE_FORWARDING) || 548 (bif->bif_state == BSTP_IFSTATE_LEARNING)) { 549 if (bif->bif_change_detection_enabled) { 550 bstp_topology_change_detection(sc); 551 } 552 } 553 bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING); 554 bridge_rtdelete(sc, bif->bif_ifp, IFBF_FLUSHDYN); 555 bstp_timer_stop(&bif->bif_forward_delay_timer); 556 } 557 } 558 559 static void 560 bstp_set_port_state(struct bridge_iflist *bif, uint8_t state) 561 { 562 bif->bif_state = state; 563 } 564 565 static void 566 bstp_topology_change_detection(struct bridge_softc *sc) 567 { 568 if (bstp_root_bridge(sc)) { 569 sc->sc_topology_change = 1; 570 bstp_timer_start(&sc->sc_topology_change_timer, 0); 571 } else if (!sc->sc_topology_change_detected) { 572 bstp_transmit_tcn(sc); 573 bstp_timer_start(&sc->sc_tcn_timer, 0); 574 } 575 sc->sc_topology_change_detected = 1; 576 } 577 578 static void 579 bstp_topology_change_acknowledged(struct bridge_softc *sc) 580 { 581 sc->sc_topology_change_detected = 0; 582 bstp_timer_stop(&sc->sc_tcn_timer); 583 } 584 585 static void 586 bstp_acknowledge_topology_change(struct bridge_softc *sc, 587 struct bridge_iflist *bif) 588 { 589 bif->bif_topology_change_acknowledge = 1; 590 bstp_transmit_config(sc, bif); 591 } 592 593 struct mbuf * 594 bstp_input(struct bridge_softc *sc, struct bridge_iflist *bif, struct mbuf *m) 595 { 596 struct ether_header *eh; 597 struct bstp_tbpdu tpdu; 598 struct bstp_cbpdu cpdu; 599 struct bstp_config_unit cu; 600 struct bstp_tcn_unit tu; 601 uint16_t len; 602 603 if ((bif->bif_flags & IFBIF_STP) == 0) 604 goto out; 605 606 eh = mtod(m, struct ether_header *); 607 608 len = ntohs(eh->ether_type); 609 if (len < sizeof(tpdu)) 610 goto out; 611 612 m_adj(m, ETHER_HDR_LEN); 613 614 if (m->m_pkthdr.len > len) 615 m_adj(m, len - m->m_pkthdr.len); 616 if (m->m_len < sizeof(tpdu) && 617 (m = m_pullup(m, sizeof(tpdu))) == NULL) 618 goto out; 619 620 memcpy(&tpdu, mtod(m, caddr_t), sizeof(tpdu)); 621 622 if (tpdu.tbu_dsap != LLC_8021D_LSAP || 623 tpdu.tbu_ssap != LLC_8021D_LSAP || 624 tpdu.tbu_ctl != LLC_UI) 625 goto out; 626 if (tpdu.tbu_protoid != 0 || tpdu.tbu_protover != 0) 627 goto out; 628 629 switch (tpdu.tbu_bpdutype) { 630 case BSTP_MSGTYPE_TCN: 631 tu.tu_message_type = tpdu.tbu_bpdutype; 632 bstp_received_tcn_bpdu(sc, bif, &tu); 633 break; 634 case BSTP_MSGTYPE_CFG: 635 if (m->m_len < sizeof(cpdu) && 636 (m = m_pullup(m, sizeof(cpdu))) == NULL) 637 goto out; 638 memcpy(&cpdu, mtod(m, caddr_t), sizeof(cpdu)); 639 640 cu.cu_rootid = 641 (((uint64_t)ntohs(cpdu.cbu_rootpri)) << 48) | 642 (((uint64_t)cpdu.cbu_rootaddr[0]) << 40) | 643 (((uint64_t)cpdu.cbu_rootaddr[1]) << 32) | 644 (((uint64_t)cpdu.cbu_rootaddr[2]) << 24) | 645 (((uint64_t)cpdu.cbu_rootaddr[3]) << 16) | 646 (((uint64_t)cpdu.cbu_rootaddr[4]) << 8) | 647 (((uint64_t)cpdu.cbu_rootaddr[5]) << 0); 648 649 cu.cu_bridge_id = 650 (((uint64_t)ntohs(cpdu.cbu_bridgepri)) << 48) | 651 (((uint64_t)cpdu.cbu_bridgeaddr[0]) << 40) | 652 (((uint64_t)cpdu.cbu_bridgeaddr[1]) << 32) | 653 (((uint64_t)cpdu.cbu_bridgeaddr[2]) << 24) | 654 (((uint64_t)cpdu.cbu_bridgeaddr[3]) << 16) | 655 (((uint64_t)cpdu.cbu_bridgeaddr[4]) << 8) | 656 (((uint64_t)cpdu.cbu_bridgeaddr[5]) << 0); 657 658 cu.cu_root_path_cost = ntohl(cpdu.cbu_rootpathcost); 659 cu.cu_message_age = ntohs(cpdu.cbu_messageage); 660 cu.cu_max_age = ntohs(cpdu.cbu_maxage); 661 cu.cu_hello_time = ntohs(cpdu.cbu_hellotime); 662 cu.cu_forward_delay = ntohs(cpdu.cbu_forwarddelay); 663 cu.cu_port_id = ntohs(cpdu.cbu_portid); 664 cu.cu_message_type = cpdu.cbu_bpdutype; 665 cu.cu_topology_change_acknowledgment = 666 (cpdu.cbu_flags & BSTP_FLAG_TCA) ? 1 : 0; 667 cu.cu_topology_change = 668 (cpdu.cbu_flags & BSTP_FLAG_TC) ? 1 : 0; 669 bstp_received_config_bpdu(sc, bif, &cu); 670 break; 671 default: 672 goto out; 673 } 674 675 out: 676 if (m) 677 m_freem(m); 678 return (NULL); 679 } 680 681 static void 682 bstp_received_config_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif, 683 struct bstp_config_unit *cu) 684 { 685 int root; 686 687 root = bstp_root_bridge(sc); 688 689 if (bif->bif_state != BSTP_IFSTATE_DISABLED) { 690 if (bstp_supersedes_port_info(sc, bif, cu)) { 691 bstp_record_config_information(sc, bif, cu); 692 bstp_configuration_update(sc); 693 bstp_port_state_selection(sc); 694 695 if ((bstp_root_bridge(sc) == 0) && root) { 696 bstp_timer_stop(&sc->sc_hello_timer); 697 698 if (sc->sc_topology_change_detected) { 699 bstp_timer_stop( 700 &sc->sc_topology_change_timer); 701 bstp_transmit_tcn(sc); 702 bstp_timer_start(&sc->sc_tcn_timer, 0); 703 } 704 } 705 706 if (bif == sc->sc_root_port) { 707 bstp_record_config_timeout_values(sc, cu); 708 bstp_config_bpdu_generation(sc); 709 710 if (cu->cu_topology_change_acknowledgment) 711 bstp_topology_change_acknowledged(sc); 712 } 713 } else if (bstp_designated_port(sc, bif)) 714 bstp_transmit_config(sc, bif); 715 } 716 } 717 718 static void 719 bstp_received_tcn_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif, 720 struct bstp_tcn_unit *tcn) 721 { 722 if (bif->bif_state != BSTP_IFSTATE_DISABLED && 723 bstp_designated_port(sc, bif)) { 724 bstp_topology_change_detection(sc); 725 bstp_acknowledge_topology_change(sc, bif); 726 } 727 } 728 729 static void 730 bstp_hello_timer_expiry(struct bridge_softc *sc) 731 { 732 bstp_config_bpdu_generation(sc); 733 bstp_timer_start(&sc->sc_hello_timer, 0); 734 } 735 736 static void 737 bstp_message_age_timer_expiry(struct bridge_softc *sc, 738 struct bridge_iflist *bif) 739 { 740 int root; 741 742 root = bstp_root_bridge(sc); 743 bstp_become_designated_port(sc, bif); 744 bstp_configuration_update(sc); 745 bstp_port_state_selection(sc); 746 747 if ((bstp_root_bridge(sc)) && (root == 0)) { 748 sc->sc_max_age = sc->sc_bridge_max_age; 749 sc->sc_hello_time = sc->sc_bridge_hello_time; 750 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 751 752 bstp_topology_change_detection(sc); 753 bstp_timer_stop(&sc->sc_tcn_timer); 754 bstp_config_bpdu_generation(sc); 755 bstp_timer_start(&sc->sc_hello_timer, 0); 756 } 757 } 758 759 static void 760 bstp_forward_delay_timer_expiry(struct bridge_softc *sc, 761 struct bridge_iflist *bif) 762 { 763 if (bif->bif_state == BSTP_IFSTATE_LISTENING) { 764 bstp_set_port_state(bif, BSTP_IFSTATE_LEARNING); 765 bstp_timer_start(&bif->bif_forward_delay_timer, 0); 766 } else if (bif->bif_state == BSTP_IFSTATE_LEARNING) { 767 bstp_set_port_state(bif, BSTP_IFSTATE_FORWARDING); 768 if (bstp_designated_for_some_port(sc) && 769 bif->bif_change_detection_enabled) 770 bstp_topology_change_detection(sc); 771 } 772 } 773 774 static int 775 bstp_designated_for_some_port(struct bridge_softc *sc) 776 { 777 778 struct bridge_iflist *bif; 779 780 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 781 if ((bif->bif_flags & IFBIF_STP) == 0) 782 continue; 783 if (bif->bif_designated_bridge == sc->sc_bridge_id) 784 return (1); 785 } 786 return (0); 787 } 788 789 static void 790 bstp_tcn_timer_expiry(struct bridge_softc *sc) 791 { 792 bstp_transmit_tcn(sc); 793 bstp_timer_start(&sc->sc_tcn_timer, 0); 794 } 795 796 static void 797 bstp_topology_change_timer_expiry(struct bridge_softc *sc) 798 { 799 sc->sc_topology_change_detected = 0; 800 sc->sc_topology_change = 0; 801 } 802 803 static void 804 bstp_hold_timer_expiry(struct bridge_softc *sc, struct bridge_iflist *bif) 805 { 806 if (bif->bif_config_pending) 807 bstp_transmit_config(sc, bif); 808 } 809 810 static int 811 bstp_addr_cmp(const uint8_t *a, const uint8_t *b) 812 { 813 int i, d; 814 815 for (i = 0, d = 0; i < ETHER_ADDR_LEN && d == 0; i++) { 816 d = ((int)a[i]) - ((int)b[i]); 817 } 818 819 return (d); 820 } 821 822 void 823 bstp_initialization(struct bridge_softc *sc) 824 { 825 struct bridge_iflist *bif, *mif; 826 u_char *e_addr; 827 828 mif = NULL; 829 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 830 if ((bif->bif_flags & IFBIF_STP) == 0) 831 continue; 832 if (bif->bif_ifp->if_type != IFT_ETHER) 833 continue; 834 bif->bif_port_id = (bif->bif_priority << 8) | 835 (bif->bif_ifp->if_index & 0xff); 836 837 if (mif == NULL) { 838 mif = bif; 839 continue; 840 } 841 if (bstp_addr_cmp(IF_LLADDR(bif->bif_ifp), 842 IF_LLADDR(mif->bif_ifp)) < 0) { 843 mif = bif; 844 continue; 845 } 846 } 847 if (mif == NULL) { 848 bstp_stop(sc); 849 return; 850 } 851 852 e_addr = IF_LLADDR(mif->bif_ifp); 853 sc->sc_bridge_id = 854 (((uint64_t)sc->sc_bridge_priority) << 48) | 855 (((uint64_t)e_addr[0]) << 40) | 856 (((uint64_t)e_addr[1]) << 32) | 857 (((uint64_t)e_addr[2]) << 24) | 858 (((uint64_t)e_addr[3]) << 16) | 859 (((uint64_t)e_addr[4]) << 8) | 860 (((uint64_t)e_addr[5])); 861 862 sc->sc_designated_root = sc->sc_bridge_id; 863 sc->sc_root_path_cost = 0; 864 sc->sc_root_port = NULL; 865 866 sc->sc_max_age = sc->sc_bridge_max_age; 867 sc->sc_hello_time = sc->sc_bridge_hello_time; 868 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 869 sc->sc_topology_change_detected = 0; 870 sc->sc_topology_change = 0; 871 bstp_timer_stop(&sc->sc_tcn_timer); 872 bstp_timer_stop(&sc->sc_topology_change_timer); 873 874 if (callout_pending(&sc->sc_bstpcallout) == 0) 875 callout_reset(&sc->sc_bstpcallout, hz, 876 bstp_tick, sc); 877 878 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 879 if (bif->bif_flags & IFBIF_STP) 880 bstp_ifupdstatus(sc, bif); 881 else 882 bstp_disable_port(sc, bif); 883 } 884 885 bstp_port_state_selection(sc); 886 bstp_config_bpdu_generation(sc); 887 bstp_timer_start(&sc->sc_hello_timer, 0); 888 } 889 890 void 891 bstp_stop(struct bridge_softc *sc) 892 { 893 struct bridge_iflist *bif; 894 895 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 896 bstp_set_port_state(bif, BSTP_IFSTATE_DISABLED); 897 bstp_timer_stop(&bif->bif_hold_timer); 898 bstp_timer_stop(&bif->bif_message_age_timer); 899 bstp_timer_stop(&bif->bif_forward_delay_timer); 900 } 901 902 callout_stop(&sc->sc_bstpcallout); 903 904 bstp_timer_stop(&sc->sc_topology_change_timer); 905 bstp_timer_stop(&sc->sc_tcn_timer); 906 bstp_timer_stop(&sc->sc_hello_timer); 907 908 } 909 910 static void 911 bstp_initialize_port(struct bridge_softc *sc, struct bridge_iflist *bif) 912 { 913 bstp_become_designated_port(sc, bif); 914 bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING); 915 bif->bif_topology_change_acknowledge = 0; 916 bif->bif_config_pending = 0; 917 bif->bif_change_detection_enabled = 1; 918 bstp_timer_stop(&bif->bif_message_age_timer); 919 bstp_timer_stop(&bif->bif_forward_delay_timer); 920 bstp_timer_stop(&bif->bif_hold_timer); 921 } 922 923 static void 924 bstp_enable_port(struct bridge_softc *sc, struct bridge_iflist *bif) 925 { 926 bstp_initialize_port(sc, bif); 927 bstp_port_state_selection(sc); 928 } 929 930 static void 931 bstp_disable_port(struct bridge_softc *sc, struct bridge_iflist *bif) 932 { 933 int root; 934 935 root = bstp_root_bridge(sc); 936 bstp_become_designated_port(sc, bif); 937 bstp_set_port_state(bif, BSTP_IFSTATE_DISABLED); 938 bif->bif_topology_change_acknowledge = 0; 939 bif->bif_config_pending = 0; 940 bstp_timer_stop(&bif->bif_message_age_timer); 941 bstp_timer_stop(&bif->bif_forward_delay_timer); 942 bstp_configuration_update(sc); 943 bstp_port_state_selection(sc); 944 bridge_rtdelete(sc, bif->bif_ifp, IFBF_FLUSHDYN); 945 946 if (bstp_root_bridge(sc) && (root == 0)) { 947 sc->sc_max_age = sc->sc_bridge_max_age; 948 sc->sc_hello_time = sc->sc_bridge_hello_time; 949 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 950 951 bstp_topology_change_detection(sc); 952 bstp_timer_stop(&sc->sc_tcn_timer); 953 bstp_config_bpdu_generation(sc); 954 bstp_timer_start(&sc->sc_hello_timer, 0); 955 } 956 } 957 958 #ifdef notused 959 static void 960 bstp_set_bridge_priority(struct bridge_softc *sc, uint64_t new_bridge_id) 961 { 962 struct bridge_iflist *bif; 963 int root; 964 965 root = bstp_root_bridge(sc); 966 967 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 968 if ((bif->bif_flags & IFBIF_STP) == 0) 969 continue; 970 if (bstp_designated_port(sc, bif)) 971 bif->bif_designated_bridge = new_bridge_id; 972 } 973 974 sc->sc_bridge_id = new_bridge_id; 975 976 bstp_configuration_update(sc); 977 bstp_port_state_selection(sc); 978 979 if (bstp_root_bridge(sc) && (root == 0)) { 980 sc->sc_max_age = sc->sc_bridge_max_age; 981 sc->sc_hello_time = sc->sc_bridge_hello_time; 982 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 983 984 bstp_topology_change_detection(sc); 985 bstp_timer_stop(&sc->sc_tcn_timer); 986 bstp_config_bpdu_generation(sc); 987 bstp_timer_start(&sc->sc_hello_timer, 0); 988 } 989 } 990 991 static void 992 bstp_set_port_priority(struct bridge_softc *sc, struct bridge_iflist *bif, 993 uint16_t new_port_id) 994 { 995 if (bstp_designated_port(sc, bif)) 996 bif->bif_designated_port = new_port_id; 997 998 bif->bif_port_id = new_port_id; 999 1000 if ((sc->sc_bridge_id == bif->bif_designated_bridge) && 1001 (bif->bif_port_id < bif->bif_designated_port)) { 1002 bstp_become_designated_port(sc, bif); 1003 bstp_port_state_selection(sc); 1004 } 1005 } 1006 1007 static void 1008 bstp_set_path_cost(struct bridge_softc *sc, struct bridge_iflist *bif, 1009 uint32_t path_cost) 1010 { 1011 bif->bif_path_cost = path_cost; 1012 bstp_configuration_update(sc); 1013 bstp_port_state_selection(sc); 1014 } 1015 1016 static void 1017 bstp_enable_change_detection(struct bridge_iflist *bif) 1018 { 1019 bif->bif_change_detection_enabled = 1; 1020 } 1021 1022 static void 1023 bstp_disable_change_detection(struct bridge_iflist *bif) 1024 { 1025 bif->bif_change_detection_enabled = 0; 1026 } 1027 #endif /* notused */ 1028 1029 void 1030 bstp_linkstate(struct ifnet *ifp, int state) 1031 { 1032 struct bridge_softc *sc; 1033 struct bridge_iflist *bif; 1034 1035 sc = ifp->if_bridge; 1036 lwkt_serialize_enter(sc->sc_ifp->if_serializer); 1037 1038 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 1039 if ((bif->bif_flags & IFBIF_STP) == 0) 1040 continue; 1041 1042 if (bif->bif_ifp == ifp) { 1043 bstp_ifupdstatus(sc, bif); 1044 break; 1045 } 1046 } 1047 lwkt_serialize_exit(sc->sc_ifp->if_serializer); 1048 } 1049 1050 static void 1051 bstp_ifupdstatus(struct bridge_softc *sc, struct bridge_iflist *bif) 1052 { 1053 struct ifnet *ifp = bif->bif_ifp; 1054 struct ifmediareq ifmr; 1055 int error = 0; 1056 1057 bzero((char *)&ifmr, sizeof(ifmr)); 1058 lwkt_serialize_enter(ifp->if_serializer); 1059 error = (*ifp->if_ioctl)(ifp, SIOCGIFMEDIA, (caddr_t)&ifmr, NULL); 1060 lwkt_serialize_exit(ifp->if_serializer); 1061 1062 if ((error == 0) && (ifp->if_flags & IFF_UP)) { 1063 if (ifmr.ifm_status & IFM_ACTIVE) { 1064 if (bif->bif_state == BSTP_IFSTATE_DISABLED) 1065 bstp_enable_port(sc, bif); 1066 1067 } else { 1068 if (bif->bif_state != BSTP_IFSTATE_DISABLED) 1069 bstp_disable_port(sc, bif); 1070 } 1071 return; 1072 } 1073 1074 if (bif->bif_state != BSTP_IFSTATE_DISABLED) 1075 bstp_disable_port(sc, bif); 1076 } 1077 1078 static void 1079 bstp_tick(void *arg) 1080 { 1081 struct bridge_softc *sc = arg; 1082 struct bridge_iflist *bif; 1083 1084 lwkt_serialize_enter(sc->sc_ifp->if_serializer); 1085 1086 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 1087 if ((bif->bif_flags & IFBIF_STP) == 0) 1088 continue; 1089 /* 1090 * XXX This can cause a lag in "link does away" 1091 * XXX and "spanning tree gets updated". We need 1092 * XXX come sort of callback from the link state 1093 * XXX update code to kick spanning tree. 1094 * XXX --thorpej@NetBSD.org 1095 */ 1096 bstp_ifupdstatus(sc, bif); 1097 } 1098 1099 if (bstp_timer_expired(&sc->sc_hello_timer, sc->sc_hello_time)) 1100 bstp_hello_timer_expiry(sc); 1101 1102 if (bstp_timer_expired(&sc->sc_tcn_timer, sc->sc_bridge_hello_time)) 1103 bstp_tcn_timer_expiry(sc); 1104 1105 if (bstp_timer_expired(&sc->sc_topology_change_timer, 1106 sc->sc_topology_change_time)) 1107 bstp_topology_change_timer_expiry(sc); 1108 1109 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 1110 if ((bif->bif_flags & IFBIF_STP) == 0) 1111 continue; 1112 if (bstp_timer_expired(&bif->bif_message_age_timer, 1113 sc->sc_max_age)) 1114 bstp_message_age_timer_expiry(sc, bif); 1115 } 1116 1117 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 1118 if ((bif->bif_flags & IFBIF_STP) == 0) 1119 continue; 1120 if (bstp_timer_expired(&bif->bif_forward_delay_timer, 1121 sc->sc_forward_delay)) 1122 bstp_forward_delay_timer_expiry(sc, bif); 1123 1124 if (bstp_timer_expired(&bif->bif_hold_timer, 1125 sc->sc_hold_time)) 1126 bstp_hold_timer_expiry(sc, bif); 1127 } 1128 1129 if (sc->sc_ifp->if_flags & IFF_RUNNING) 1130 callout_reset(&sc->sc_bstpcallout, hz, bstp_tick, sc); 1131 1132 lwkt_serialize_exit(sc->sc_ifp->if_serializer); 1133 } 1134 1135 static void 1136 bstp_timer_start(struct bridge_timer *t, uint16_t v) 1137 { 1138 t->value = v; 1139 t->active = 1; 1140 } 1141 1142 static void 1143 bstp_timer_stop(struct bridge_timer *t) 1144 { 1145 t->value = 0; 1146 t->active = 0; 1147 } 1148 1149 static int 1150 bstp_timer_expired(struct bridge_timer *t, uint16_t v) 1151 { 1152 if (t->active == 0) 1153 return (0); 1154 t->value += BSTP_TICK_VAL; 1155 if (t->value >= v) { 1156 bstp_timer_stop(t); 1157 return (1); 1158 } 1159 return (0); 1160 1161 } 1162