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.3 2006/06/30 16:50:01 geekgod 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(sc, 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(sc, 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 ifnet *ifp, struct mbuf *m) 595 { 596 struct bridge_softc *sc = ifp->if_bridge; 597 struct bridge_iflist *bif = NULL; 598 struct ether_header *eh; 599 struct bstp_tbpdu tpdu; 600 struct bstp_cbpdu cpdu; 601 struct bstp_config_unit cu; 602 struct bstp_tcn_unit tu; 603 uint16_t len; 604 605 eh = mtod(m, struct ether_header *); 606 607 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 608 if ((bif->bif_flags & IFBIF_STP) == 0) 609 continue; 610 if (bif->bif_ifp == ifp) 611 break; 612 } 613 if (bif == NULL) 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, caddr_t), 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 bstp_received_tcn_bpdu(sc, bif, &tu); 641 break; 642 case BSTP_MSGTYPE_CFG: 643 if (m->m_len < sizeof(cpdu) && 644 (m = m_pullup(m, sizeof(cpdu))) == NULL) 645 goto out; 646 memcpy(&cpdu, mtod(m, caddr_t), sizeof(cpdu)); 647 648 cu.cu_rootid = 649 (((uint64_t)ntohs(cpdu.cbu_rootpri)) << 48) | 650 (((uint64_t)cpdu.cbu_rootaddr[0]) << 40) | 651 (((uint64_t)cpdu.cbu_rootaddr[1]) << 32) | 652 (((uint64_t)cpdu.cbu_rootaddr[2]) << 24) | 653 (((uint64_t)cpdu.cbu_rootaddr[3]) << 16) | 654 (((uint64_t)cpdu.cbu_rootaddr[4]) << 8) | 655 (((uint64_t)cpdu.cbu_rootaddr[5]) << 0); 656 657 cu.cu_bridge_id = 658 (((uint64_t)ntohs(cpdu.cbu_bridgepri)) << 48) | 659 (((uint64_t)cpdu.cbu_bridgeaddr[0]) << 40) | 660 (((uint64_t)cpdu.cbu_bridgeaddr[1]) << 32) | 661 (((uint64_t)cpdu.cbu_bridgeaddr[2]) << 24) | 662 (((uint64_t)cpdu.cbu_bridgeaddr[3]) << 16) | 663 (((uint64_t)cpdu.cbu_bridgeaddr[4]) << 8) | 664 (((uint64_t)cpdu.cbu_bridgeaddr[5]) << 0); 665 666 cu.cu_root_path_cost = ntohl(cpdu.cbu_rootpathcost); 667 cu.cu_message_age = ntohs(cpdu.cbu_messageage); 668 cu.cu_max_age = ntohs(cpdu.cbu_maxage); 669 cu.cu_hello_time = ntohs(cpdu.cbu_hellotime); 670 cu.cu_forward_delay = ntohs(cpdu.cbu_forwarddelay); 671 cu.cu_port_id = ntohs(cpdu.cbu_portid); 672 cu.cu_message_type = cpdu.cbu_bpdutype; 673 cu.cu_topology_change_acknowledgment = 674 (cpdu.cbu_flags & BSTP_FLAG_TCA) ? 1 : 0; 675 cu.cu_topology_change = 676 (cpdu.cbu_flags & BSTP_FLAG_TC) ? 1 : 0; 677 bstp_received_config_bpdu(sc, bif, &cu); 678 break; 679 default: 680 goto out; 681 } 682 683 out: 684 if (m) 685 m_freem(m); 686 return (NULL); 687 } 688 689 static void 690 bstp_received_config_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif, 691 struct bstp_config_unit *cu) 692 { 693 int root; 694 695 root = bstp_root_bridge(sc); 696 697 if (bif->bif_state != BSTP_IFSTATE_DISABLED) { 698 if (bstp_supersedes_port_info(sc, bif, cu)) { 699 bstp_record_config_information(sc, bif, cu); 700 bstp_configuration_update(sc); 701 bstp_port_state_selection(sc); 702 703 if ((bstp_root_bridge(sc) == 0) && root) { 704 bstp_timer_stop(&sc->sc_hello_timer); 705 706 if (sc->sc_topology_change_detected) { 707 bstp_timer_stop( 708 &sc->sc_topology_change_timer); 709 bstp_transmit_tcn(sc); 710 bstp_timer_start(&sc->sc_tcn_timer, 0); 711 } 712 } 713 714 if (bif == sc->sc_root_port) { 715 bstp_record_config_timeout_values(sc, cu); 716 bstp_config_bpdu_generation(sc); 717 718 if (cu->cu_topology_change_acknowledgment) 719 bstp_topology_change_acknowledged(sc); 720 } 721 } else if (bstp_designated_port(sc, bif)) 722 bstp_transmit_config(sc, bif); 723 } 724 } 725 726 static void 727 bstp_received_tcn_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif, 728 struct bstp_tcn_unit *tcn) 729 { 730 if (bif->bif_state != BSTP_IFSTATE_DISABLED && 731 bstp_designated_port(sc, bif)) { 732 bstp_topology_change_detection(sc); 733 bstp_acknowledge_topology_change(sc, bif); 734 } 735 } 736 737 static void 738 bstp_hello_timer_expiry(struct bridge_softc *sc) 739 { 740 bstp_config_bpdu_generation(sc); 741 bstp_timer_start(&sc->sc_hello_timer, 0); 742 } 743 744 static void 745 bstp_message_age_timer_expiry(struct bridge_softc *sc, 746 struct bridge_iflist *bif) 747 { 748 int root; 749 750 root = bstp_root_bridge(sc); 751 bstp_become_designated_port(sc, bif); 752 bstp_configuration_update(sc); 753 bstp_port_state_selection(sc); 754 755 if ((bstp_root_bridge(sc)) && (root == 0)) { 756 sc->sc_max_age = sc->sc_bridge_max_age; 757 sc->sc_hello_time = sc->sc_bridge_hello_time; 758 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 759 760 bstp_topology_change_detection(sc); 761 bstp_timer_stop(&sc->sc_tcn_timer); 762 bstp_config_bpdu_generation(sc); 763 bstp_timer_start(&sc->sc_hello_timer, 0); 764 } 765 } 766 767 static void 768 bstp_forward_delay_timer_expiry(struct bridge_softc *sc, 769 struct bridge_iflist *bif) 770 { 771 if (bif->bif_state == BSTP_IFSTATE_LISTENING) { 772 bstp_set_port_state(bif, BSTP_IFSTATE_LEARNING); 773 bstp_timer_start(&bif->bif_forward_delay_timer, 0); 774 } else if (bif->bif_state == BSTP_IFSTATE_LEARNING) { 775 bstp_set_port_state(bif, BSTP_IFSTATE_FORWARDING); 776 if (bstp_designated_for_some_port(sc) && 777 bif->bif_change_detection_enabled) 778 bstp_topology_change_detection(sc); 779 } 780 } 781 782 static int 783 bstp_designated_for_some_port(struct bridge_softc *sc) 784 { 785 786 struct bridge_iflist *bif; 787 788 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 789 if ((bif->bif_flags & IFBIF_STP) == 0) 790 continue; 791 if (bif->bif_designated_bridge == sc->sc_bridge_id) 792 return (1); 793 } 794 return (0); 795 } 796 797 static void 798 bstp_tcn_timer_expiry(struct bridge_softc *sc) 799 { 800 bstp_transmit_tcn(sc); 801 bstp_timer_start(&sc->sc_tcn_timer, 0); 802 } 803 804 static void 805 bstp_topology_change_timer_expiry(struct bridge_softc *sc) 806 { 807 sc->sc_topology_change_detected = 0; 808 sc->sc_topology_change = 0; 809 } 810 811 static void 812 bstp_hold_timer_expiry(struct bridge_softc *sc, struct bridge_iflist *bif) 813 { 814 if (bif->bif_config_pending) 815 bstp_transmit_config(sc, bif); 816 } 817 818 static int 819 bstp_addr_cmp(const uint8_t *a, const uint8_t *b) 820 { 821 int i, d; 822 823 for (i = 0, d = 0; i < ETHER_ADDR_LEN && d == 0; i++) { 824 d = ((int)a[i]) - ((int)b[i]); 825 } 826 827 return (d); 828 } 829 830 void 831 bstp_initialization(struct bridge_softc *sc) 832 { 833 struct bridge_iflist *bif, *mif; 834 u_char *e_addr; 835 836 mif = NULL; 837 LIST_FOREACH(bif, &sc->sc_iflist, 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 (bstp_addr_cmp(IF_LLADDR(bif->bif_ifp), 850 IF_LLADDR(mif->bif_ifp)) < 0) { 851 mif = bif; 852 continue; 853 } 854 } 855 if (mif == NULL) { 856 bstp_stop(sc); 857 return; 858 } 859 860 e_addr = IF_LLADDR(mif->bif_ifp); 861 sc->sc_bridge_id = 862 (((uint64_t)sc->sc_bridge_priority) << 48) | 863 (((uint64_t)e_addr[0]) << 40) | 864 (((uint64_t)e_addr[1]) << 32) | 865 (((uint64_t)e_addr[2]) << 24) | 866 (((uint64_t)e_addr[3]) << 16) | 867 (((uint64_t)e_addr[4]) << 8) | 868 (((uint64_t)e_addr[5])); 869 870 sc->sc_designated_root = sc->sc_bridge_id; 871 sc->sc_root_path_cost = 0; 872 sc->sc_root_port = NULL; 873 874 sc->sc_max_age = sc->sc_bridge_max_age; 875 sc->sc_hello_time = sc->sc_bridge_hello_time; 876 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 877 sc->sc_topology_change_detected = 0; 878 sc->sc_topology_change = 0; 879 bstp_timer_stop(&sc->sc_tcn_timer); 880 bstp_timer_stop(&sc->sc_topology_change_timer); 881 882 if (callout_pending(&sc->sc_bstpcallout) == 0) 883 callout_reset(&sc->sc_bstpcallout, hz, 884 bstp_tick, sc); 885 886 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 887 if (bif->bif_flags & IFBIF_STP) 888 bstp_ifupdstatus(sc, bif); 889 else 890 bstp_disable_port(sc, bif); 891 } 892 893 bstp_port_state_selection(sc); 894 bstp_config_bpdu_generation(sc); 895 bstp_timer_start(&sc->sc_hello_timer, 0); 896 } 897 898 void 899 bstp_stop(struct bridge_softc *sc) 900 { 901 struct bridge_iflist *bif; 902 903 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 904 bstp_set_port_state(bif, BSTP_IFSTATE_DISABLED); 905 bstp_timer_stop(&bif->bif_hold_timer); 906 bstp_timer_stop(&bif->bif_message_age_timer); 907 bstp_timer_stop(&bif->bif_forward_delay_timer); 908 } 909 910 callout_stop(&sc->sc_bstpcallout); 911 912 bstp_timer_stop(&sc->sc_topology_change_timer); 913 bstp_timer_stop(&sc->sc_tcn_timer); 914 bstp_timer_stop(&sc->sc_hello_timer); 915 916 } 917 918 static void 919 bstp_initialize_port(struct bridge_softc *sc, struct bridge_iflist *bif) 920 { 921 bstp_become_designated_port(sc, bif); 922 bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING); 923 bif->bif_topology_change_acknowledge = 0; 924 bif->bif_config_pending = 0; 925 bif->bif_change_detection_enabled = 1; 926 bstp_timer_stop(&bif->bif_message_age_timer); 927 bstp_timer_stop(&bif->bif_forward_delay_timer); 928 bstp_timer_stop(&bif->bif_hold_timer); 929 } 930 931 static void 932 bstp_enable_port(struct bridge_softc *sc, struct bridge_iflist *bif) 933 { 934 bstp_initialize_port(sc, bif); 935 bstp_port_state_selection(sc); 936 } 937 938 static void 939 bstp_disable_port(struct bridge_softc *sc, struct bridge_iflist *bif) 940 { 941 int root; 942 943 root = bstp_root_bridge(sc); 944 bstp_become_designated_port(sc, bif); 945 bstp_set_port_state(bif, BSTP_IFSTATE_DISABLED); 946 bif->bif_topology_change_acknowledge = 0; 947 bif->bif_config_pending = 0; 948 bstp_timer_stop(&bif->bif_message_age_timer); 949 bstp_timer_stop(&bif->bif_forward_delay_timer); 950 bstp_configuration_update(sc); 951 bstp_port_state_selection(sc); 952 bridge_rtdelete(sc, bif->bif_ifp, IFBF_FLUSHDYN); 953 954 if (bstp_root_bridge(sc) && (root == 0)) { 955 sc->sc_max_age = sc->sc_bridge_max_age; 956 sc->sc_hello_time = sc->sc_bridge_hello_time; 957 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 958 959 bstp_topology_change_detection(sc); 960 bstp_timer_stop(&sc->sc_tcn_timer); 961 bstp_config_bpdu_generation(sc); 962 bstp_timer_start(&sc->sc_hello_timer, 0); 963 } 964 } 965 966 #ifdef notused 967 static void 968 bstp_set_bridge_priority(struct bridge_softc *sc, uint64_t new_bridge_id) 969 { 970 struct bridge_iflist *bif; 971 int root; 972 973 root = bstp_root_bridge(sc); 974 975 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 976 if ((bif->bif_flags & IFBIF_STP) == 0) 977 continue; 978 if (bstp_designated_port(sc, bif)) 979 bif->bif_designated_bridge = new_bridge_id; 980 } 981 982 sc->sc_bridge_id = new_bridge_id; 983 984 bstp_configuration_update(sc); 985 bstp_port_state_selection(sc); 986 987 if (bstp_root_bridge(sc) && (root == 0)) { 988 sc->sc_max_age = sc->sc_bridge_max_age; 989 sc->sc_hello_time = sc->sc_bridge_hello_time; 990 sc->sc_forward_delay = sc->sc_bridge_forward_delay; 991 992 bstp_topology_change_detection(sc); 993 bstp_timer_stop(&sc->sc_tcn_timer); 994 bstp_config_bpdu_generation(sc); 995 bstp_timer_start(&sc->sc_hello_timer, 0); 996 } 997 } 998 999 static void 1000 bstp_set_port_priority(struct bridge_softc *sc, struct bridge_iflist *bif, 1001 uint16_t new_port_id) 1002 { 1003 if (bstp_designated_port(sc, bif)) 1004 bif->bif_designated_port = new_port_id; 1005 1006 bif->bif_port_id = new_port_id; 1007 1008 if ((sc->sc_bridge_id == bif->bif_designated_bridge) && 1009 (bif->bif_port_id < bif->bif_designated_port)) { 1010 bstp_become_designated_port(sc, bif); 1011 bstp_port_state_selection(sc); 1012 } 1013 } 1014 1015 static void 1016 bstp_set_path_cost(struct bridge_softc *sc, struct bridge_iflist *bif, 1017 uint32_t path_cost) 1018 { 1019 bif->bif_path_cost = path_cost; 1020 bstp_configuration_update(sc); 1021 bstp_port_state_selection(sc); 1022 } 1023 1024 static void 1025 bstp_enable_change_detection(struct bridge_iflist *bif) 1026 { 1027 bif->bif_change_detection_enabled = 1; 1028 } 1029 1030 static void 1031 bstp_disable_change_detection(struct bridge_iflist *bif) 1032 { 1033 bif->bif_change_detection_enabled = 0; 1034 } 1035 #endif /* notused */ 1036 1037 void 1038 bstp_linkstate(struct ifnet *ifp, int state) 1039 { 1040 struct bridge_softc *sc; 1041 struct bridge_iflist *bif; 1042 1043 sc = ifp->if_bridge; 1044 lwkt_serialize_enter(sc->sc_ifp->if_serializer); 1045 1046 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 1047 if ((bif->bif_flags & IFBIF_STP) == 0) 1048 continue; 1049 1050 if (bif->bif_ifp == ifp) { 1051 bstp_ifupdstatus(sc, bif); 1052 break; 1053 } 1054 } 1055 lwkt_serialize_exit(sc->sc_ifp->if_serializer); 1056 } 1057 1058 static void 1059 bstp_ifupdstatus(struct bridge_softc *sc, struct bridge_iflist *bif) 1060 { 1061 struct ifnet *ifp = bif->bif_ifp; 1062 struct ifmediareq ifmr; 1063 int error = 0; 1064 1065 bzero((char *)&ifmr, sizeof(ifmr)); 1066 lwkt_serialize_enter(ifp->if_serializer); 1067 error = (*ifp->if_ioctl)(ifp, SIOCGIFMEDIA, (caddr_t)&ifmr, NULL); 1068 lwkt_serialize_exit(ifp->if_serializer); 1069 1070 if ((error == 0) && (ifp->if_flags & IFF_UP)) { 1071 if (ifmr.ifm_status & IFM_ACTIVE) { 1072 if (bif->bif_state == BSTP_IFSTATE_DISABLED) 1073 bstp_enable_port(sc, bif); 1074 1075 } else { 1076 if (bif->bif_state != BSTP_IFSTATE_DISABLED) 1077 bstp_disable_port(sc, bif); 1078 } 1079 return; 1080 } 1081 1082 if (bif->bif_state != BSTP_IFSTATE_DISABLED) 1083 bstp_disable_port(sc, bif); 1084 } 1085 1086 static void 1087 bstp_tick(void *arg) 1088 { 1089 struct bridge_softc *sc = arg; 1090 struct bridge_iflist *bif; 1091 1092 lwkt_serialize_enter(sc->sc_ifp->if_serializer); 1093 1094 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 1095 if ((bif->bif_flags & IFBIF_STP) == 0) 1096 continue; 1097 /* 1098 * XXX This can cause a lag in "link does away" 1099 * XXX and "spanning tree gets updated". We need 1100 * XXX come sort of callback from the link state 1101 * XXX update code to kick spanning tree. 1102 * XXX --thorpej@NetBSD.org 1103 */ 1104 bstp_ifupdstatus(sc, bif); 1105 } 1106 1107 if (bstp_timer_expired(&sc->sc_hello_timer, sc->sc_hello_time)) 1108 bstp_hello_timer_expiry(sc); 1109 1110 if (bstp_timer_expired(&sc->sc_tcn_timer, sc->sc_bridge_hello_time)) 1111 bstp_tcn_timer_expiry(sc); 1112 1113 if (bstp_timer_expired(&sc->sc_topology_change_timer, 1114 sc->sc_topology_change_time)) 1115 bstp_topology_change_timer_expiry(sc); 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_message_age_timer, 1121 sc->sc_max_age)) 1122 bstp_message_age_timer_expiry(sc, bif); 1123 } 1124 1125 LIST_FOREACH(bif, &sc->sc_iflist, bif_next) { 1126 if ((bif->bif_flags & IFBIF_STP) == 0) 1127 continue; 1128 if (bstp_timer_expired(&bif->bif_forward_delay_timer, 1129 sc->sc_forward_delay)) 1130 bstp_forward_delay_timer_expiry(sc, bif); 1131 1132 if (bstp_timer_expired(&bif->bif_hold_timer, 1133 sc->sc_hold_time)) 1134 bstp_hold_timer_expiry(sc, bif); 1135 } 1136 1137 if (sc->sc_ifp->if_flags & IFF_RUNNING) 1138 callout_reset(&sc->sc_bstpcallout, hz, bstp_tick, sc); 1139 1140 lwkt_serialize_exit(sc->sc_ifp->if_serializer); 1141 } 1142 1143 static void 1144 bstp_timer_start(struct bridge_timer *t, uint16_t v) 1145 { 1146 t->value = v; 1147 t->active = 1; 1148 } 1149 1150 static void 1151 bstp_timer_stop(struct bridge_timer *t) 1152 { 1153 t->value = 0; 1154 t->active = 0; 1155 } 1156 1157 static int 1158 bstp_timer_expired(struct bridge_timer *t, uint16_t v) 1159 { 1160 if (t->active == 0) 1161 return (0); 1162 t->value += BSTP_TICK_VAL; 1163 if (t->value >= v) { 1164 bstp_timer_stop(t); 1165 return (1); 1166 } 1167 return (0); 1168 1169 } 1170