1/* $NetBSD: bridgestp.c,v 1.5 2003/11/28 08:56:48 keihan Exp $ */ 2 3/* 4 * Copyright (c) 2009-2010 Apple Inc. All rights reserved. 5 * 6 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ 7 * 8 * This file contains Original Code and/or Modifications of Original Code 9 * as defined in and that are subject to the Apple Public Source License 10 * Version 2.0 (the 'License'). You may not use this file except in 11 * compliance with the License. The rights granted to you under the License 12 * may not be used to create, or enable the creation or redistribution of, 13 * unlawful or unlicensed copies of an Apple operating system, or to 14 * circumvent, violate, or enable the circumvention or violation of, any 15 * terms of an Apple operating system software license agreement. 16 * 17 * Please obtain a copy of the License at 18 * http://www.opensource.apple.com/apsl/ and read it before using this file. 19 * 20 * The Original Code and all software distributed under the License are 21 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 22 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 23 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 24 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 25 * Please see the License for the specific language governing rights and 26 * limitations under the License. 27 * 28 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ 29 */ 30 31/* 32 * Copyright (c) 2000 Jason L. Wright (jason@thought.net) 33 * Copyright (c) 2006 Andrew Thompson (thompsa@FreeBSD.org) 34 * All rights reserved. 35 * 36 * Redistribution and use in source and binary forms, with or without 37 * modification, are permitted provided that the following conditions 38 * are met: 39 * 1. Redistributions of source code must retain the above copyright 40 * notice, this list of conditions and the following disclaimer. 41 * 2. Redistributions in binary form must reproduce the above copyright 42 * notice, this list of conditions and the following disclaimer in the 43 * documentation and/or other materials provided with the distribution. 44 * 45 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 46 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 47 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 48 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, 49 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 50 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 51 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 52 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 53 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 54 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 55 * POSSIBILITY OF SUCH DAMAGE. 56 * 57 * OpenBSD: bridgestp.c,v 1.5 2001/03/22 03:48:29 jason Exp 58 */ 59 60/* 61 * Implementation of the spanning tree protocol as defined in 62 * ISO/IEC 802.1D-2004, June 9, 2004. 63 */ 64 65#include <sys/cdefs.h> 66//__FBSDID("$FreeBSD$"); 67 68#include <sys/param.h> 69#include <sys/systm.h> 70#include <sys/mbuf.h> 71#include <sys/socket.h> 72#include <sys/sockio.h> 73#include <sys/kernel.h> 74//#include <sys/callout.h> 75//#include <sys/module.h> 76#include <sys/proc.h> 77#include <sys/lock.h> 78//#include <sys/mutex.h> 79//#include <sys/taskqueue.h> 80 81#include <net/if.h> 82#include <net/if_dl.h> 83#include <net/if_types.h> 84#include <net/if_llc.h> 85#include <net/if_media.h> 86 87#include <net/kpi_interface.h> 88 89#include <netinet/in.h> 90#include <netinet/in_systm.h> 91#include <netinet/in_var.h> 92#include <netinet/if_ether.h> 93#include <net/bridgestp.h> 94 95#include <kern/thread.h> 96 97decl_lck_mtx_data(static, bstp_task_mtx_data); 98static lck_mtx_t *bstp_task_mtx = &bstp_task_mtx_data; 99static lck_grp_t *bstp_task_grp = NULL; 100static lck_attr_t *bstp_task_attr = NULL; 101static thread_t bstp_task_thread; 102static TAILQ_HEAD(bstp_task_queue, bstp_task) 103 bstp_task_queue = TAILQ_HEAD_INITIALIZER(bstp_task_queue); 104static struct bstp_task *bstp_task_queue_running = NULL; 105 106static void bstp_create_task_thread(void); 107static void bstp_task_thread_func(void); 108 109static void bstp_task_enqueue(struct bstp_task *); 110static void bstp_task_drain(struct bstp_task *); 111 112#define BSTP_TASK_INIT(bt, func, context) do { \ 113 (bt)->bt_count = 0; \ 114 (bt)->bt_func = func; \ 115 (bt)->bt_context = context; \ 116} while(0) 117 118 119 120#define BSTP_LOCK_INIT(_bs) (_bs)->bs_mtx = lck_mtx_alloc_init(bstp_lock_grp, bstp_lock_attr) 121#define BSTP_LOCK_DESTROY(_bs) lck_mtx_free((_bs)->bs_mtx, bstp_lock_grp) 122#define BSTP_LOCK(_bs) lck_mtx_lock((_bs)->bs_mtx) 123#define BSTP_UNLOCK(_bs) lck_mtx_unlock((_bs)->bs_mtx) 124#define BSTP_LOCK_ASSERT(_bs) lck_mtx_assert((_bs)->bs_mtx, LCK_MTX_ASSERT_OWNED) 125 126 127#ifdef BRIDGESTP_DEBUG 128#define DPRINTF(fmt, arg...) printf("bstp: " fmt, ##arg) 129#else 130#define DPRINTF(fmt, arg...) 131#endif 132 133#define PV2ADDR(pv, eaddr) do { \ 134 eaddr[0] = pv >> 40; \ 135 eaddr[1] = pv >> 32; \ 136 eaddr[2] = pv >> 24; \ 137 eaddr[3] = pv >> 16; \ 138 eaddr[4] = pv >> 8; \ 139 eaddr[5] = pv >> 0; \ 140} while (0) 141 142#define INFO_BETTER 1 143#define INFO_SAME 0 144#define INFO_WORSE -1 145 146LIST_HEAD(, bstp_state) bstp_list; 147decl_lck_mtx_data(static, bstp_list_mtx_data); 148static lck_mtx_t *bstp_list_mtx = &bstp_list_mtx_data; 149static lck_grp_t *bstp_lock_grp = NULL; 150static lck_attr_t *bstp_lock_attr = NULL; 151 152static void bstp_transmit(struct bstp_state *, struct bstp_port *); 153static void bstp_transmit_bpdu(struct bstp_state *, struct bstp_port *); 154static void bstp_transmit_tcn(struct bstp_state *, struct bstp_port *); 155static void bstp_decode_bpdu(struct bstp_port *, struct bstp_cbpdu *, 156 struct bstp_config_unit *); 157static void bstp_send_bpdu(struct bstp_state *, struct bstp_port *, 158 struct bstp_cbpdu *); 159static void bstp_enqueue(struct ifnet *, struct mbuf *); 160static int bstp_pdu_flags(struct bstp_port *); 161static void bstp_received_stp(struct bstp_state *, struct bstp_port *, 162 struct mbuf **, struct bstp_tbpdu *); 163static void bstp_received_rstp(struct bstp_state *, struct bstp_port *, 164 struct mbuf **, struct bstp_tbpdu *); 165static void bstp_received_tcn(struct bstp_state *, struct bstp_port *, 166 struct bstp_tcn_unit *); 167static void bstp_received_bpdu(struct bstp_state *, struct bstp_port *, 168 struct bstp_config_unit *); 169static int bstp_pdu_rcvtype(struct bstp_port *, struct bstp_config_unit *); 170static int bstp_pdu_bettersame(struct bstp_port *, int); 171static int bstp_info_cmp(struct bstp_pri_vector *, 172 struct bstp_pri_vector *); 173static int bstp_info_superior(struct bstp_pri_vector *, 174 struct bstp_pri_vector *); 175static void bstp_assign_roles(struct bstp_state *); 176static void bstp_update_roles(struct bstp_state *, struct bstp_port *); 177static void bstp_update_state(struct bstp_state *, struct bstp_port *); 178static void bstp_update_tc(struct bstp_port *); 179static void bstp_update_info(struct bstp_port *); 180static void bstp_set_other_tcprop(struct bstp_port *); 181static void bstp_set_all_reroot(struct bstp_state *); 182static void bstp_set_all_sync(struct bstp_state *); 183static void bstp_set_port_state(struct bstp_port *, int); 184static void bstp_set_port_role(struct bstp_port *, int); 185static void bstp_set_port_proto(struct bstp_port *, int); 186static void bstp_set_port_tc(struct bstp_port *, int); 187static void bstp_set_timer_tc(struct bstp_port *); 188static void bstp_set_timer_msgage(struct bstp_port *); 189static int bstp_rerooted(struct bstp_state *, struct bstp_port *); 190static uint32_t bstp_calc_path_cost(struct bstp_port *); 191static void bstp_notify_state(void *, int); 192static void bstp_notify_rtage(void *, int); 193static void bstp_ifupdstatus(struct bstp_state *, struct bstp_port *); 194static void bstp_enable_port(struct bstp_state *, struct bstp_port *); 195static void bstp_disable_port(struct bstp_state *, struct bstp_port *); 196static void bstp_tick(void *); 197static void bstp_timer_start(struct bstp_timer *, uint16_t); 198static void bstp_timer_stop(struct bstp_timer *); 199static void bstp_timer_latch(struct bstp_timer *); 200static int bstp_timer_expired(struct bstp_timer *); 201static void bstp_hello_timer_expiry(struct bstp_state *, 202 struct bstp_port *); 203static void bstp_message_age_expiry(struct bstp_state *, 204 struct bstp_port *); 205static void bstp_migrate_delay_expiry(struct bstp_state *, 206 struct bstp_port *); 207static void bstp_edge_delay_expiry(struct bstp_state *, 208 struct bstp_port *); 209static int bstp_addr_cmp(const uint8_t *, const uint8_t *); 210static int bstp_same_bridgeid(uint64_t, uint64_t); 211static void bstp_reinit(struct bstp_state *); 212 213static void 214bstp_transmit(struct bstp_state *bs, struct bstp_port *bp) 215{ 216 if (bs->bs_running == 0) 217 return; 218 219 /* 220 * a PDU can only be sent if we have tx quota left and the 221 * hello timer is running. 222 */ 223 if (bp->bp_hello_timer.active == 0) { 224 /* Test if it needs to be reset */ 225 bstp_hello_timer_expiry(bs, bp); 226 return; 227 } 228 if (bp->bp_txcount > bs->bs_txholdcount) 229 /* Ran out of karma */ 230 return; 231 232 if (bp->bp_protover == BSTP_PROTO_RSTP) { 233 bstp_transmit_bpdu(bs, bp); 234 bp->bp_tc_ack = 0; 235 } else { /* STP */ 236 switch (bp->bp_role) { 237 case BSTP_ROLE_DESIGNATED: 238 bstp_transmit_bpdu(bs, bp); 239 bp->bp_tc_ack = 0; 240 break; 241 242 case BSTP_ROLE_ROOT: 243 bstp_transmit_tcn(bs, bp); 244 break; 245 } 246 } 247 bstp_timer_start(&bp->bp_hello_timer, bp->bp_desg_htime); 248 bp->bp_flags &= ~BSTP_PORT_NEWINFO; 249} 250 251static void 252bstp_transmit_bpdu(struct bstp_state *bs, struct bstp_port *bp) 253{ 254 struct bstp_cbpdu bpdu; 255 256 BSTP_LOCK_ASSERT(bs); 257 258 bpdu.cbu_rootpri = htons(bp->bp_desg_pv.pv_root_id >> 48); 259 PV2ADDR(bp->bp_desg_pv.pv_root_id, bpdu.cbu_rootaddr); 260 261 bpdu.cbu_rootpathcost = htonl(bp->bp_desg_pv.pv_cost); 262 263 bpdu.cbu_bridgepri = htons(bp->bp_desg_pv.pv_dbridge_id >> 48); 264 PV2ADDR(bp->bp_desg_pv.pv_dbridge_id, bpdu.cbu_bridgeaddr); 265 266 bpdu.cbu_portid = htons(bp->bp_port_id); 267 bpdu.cbu_messageage = htons(bp->bp_desg_msg_age); 268 bpdu.cbu_maxage = htons(bp->bp_desg_max_age); 269 bpdu.cbu_hellotime = htons(bp->bp_desg_htime); 270 bpdu.cbu_forwarddelay = htons(bp->bp_desg_fdelay); 271 272 bpdu.cbu_flags = bstp_pdu_flags(bp); 273 274 switch (bp->bp_protover) { 275 case BSTP_PROTO_STP: 276 bpdu.cbu_bpdutype = BSTP_MSGTYPE_CFG; 277 break; 278 279 case BSTP_PROTO_RSTP: 280 bpdu.cbu_bpdutype = BSTP_MSGTYPE_RSTP; 281 break; 282 } 283 284 bstp_send_bpdu(bs, bp, &bpdu); 285} 286 287static void 288bstp_transmit_tcn(struct bstp_state *bs, struct bstp_port *bp) 289{ 290 struct bstp_tbpdu bpdu; 291 struct ifnet *ifp = bp->bp_ifp; 292 struct ether_header *eh; 293 struct mbuf *m; 294 int touched = bs ? 1 : 0; 295 296 touched++; 297 298 KASSERT(bp == bs->bs_root_port, ("%s: bad root port\n", __func__)); 299 300 if ((ifp->if_flags & IFF_RUNNING) == 0) 301 return; 302 303 MGETHDR(m, M_DONTWAIT, MT_DATA); 304 if (m == NULL) 305 return; 306 307 m->m_pkthdr.rcvif = ifp; 308 m->m_pkthdr.len = sizeof(*eh) + sizeof(bpdu); 309 m->m_len = m->m_pkthdr.len; 310 311 eh = mtod(m, struct ether_header *); 312 313 memcpy(eh->ether_shost, ifnet_lladdr(ifp), ETHER_ADDR_LEN); 314 memcpy(eh->ether_dhost, bstp_etheraddr, ETHER_ADDR_LEN); 315 eh->ether_type = htons(sizeof(bpdu)); 316 317 bpdu.tbu_ssap = bpdu.tbu_dsap = LLC_8021D_LSAP; 318 bpdu.tbu_ctl = LLC_UI; 319 bpdu.tbu_protoid = 0; 320 bpdu.tbu_protover = 0; 321 bpdu.tbu_bpdutype = BSTP_MSGTYPE_TCN; 322 323 memcpy(mtod(m, caddr_t) + sizeof(*eh), &bpdu, sizeof(bpdu)); 324 325 bp->bp_txcount++; 326 bstp_enqueue(ifp, m); 327} 328 329static void 330bstp_decode_bpdu(struct bstp_port *bp, struct bstp_cbpdu *cpdu, 331 struct bstp_config_unit *cu) 332{ 333 int flags; 334 335 cu->cu_pv.pv_root_id = 336 (((uint64_t)ntohs(cpdu->cbu_rootpri)) << 48) | 337 (((uint64_t)cpdu->cbu_rootaddr[0]) << 40) | 338 (((uint64_t)cpdu->cbu_rootaddr[1]) << 32) | 339 (((uint64_t)cpdu->cbu_rootaddr[2]) << 24) | 340 (((uint64_t)cpdu->cbu_rootaddr[3]) << 16) | 341 (((uint64_t)cpdu->cbu_rootaddr[4]) << 8) | 342 (((uint64_t)cpdu->cbu_rootaddr[5]) << 0); 343 344 cu->cu_pv.pv_dbridge_id = 345 (((uint64_t)ntohs(cpdu->cbu_bridgepri)) << 48) | 346 (((uint64_t)cpdu->cbu_bridgeaddr[0]) << 40) | 347 (((uint64_t)cpdu->cbu_bridgeaddr[1]) << 32) | 348 (((uint64_t)cpdu->cbu_bridgeaddr[2]) << 24) | 349 (((uint64_t)cpdu->cbu_bridgeaddr[3]) << 16) | 350 (((uint64_t)cpdu->cbu_bridgeaddr[4]) << 8) | 351 (((uint64_t)cpdu->cbu_bridgeaddr[5]) << 0); 352 353 cu->cu_pv.pv_cost = ntohl(cpdu->cbu_rootpathcost); 354 cu->cu_message_age = ntohs(cpdu->cbu_messageage); 355 cu->cu_max_age = ntohs(cpdu->cbu_maxage); 356 cu->cu_hello_time = ntohs(cpdu->cbu_hellotime); 357 cu->cu_forward_delay = ntohs(cpdu->cbu_forwarddelay); 358 cu->cu_pv.pv_dport_id = ntohs(cpdu->cbu_portid); 359 cu->cu_pv.pv_port_id = bp->bp_port_id; 360 cu->cu_message_type = cpdu->cbu_bpdutype; 361 362 /* Strip off unused flags in STP mode */ 363 flags = cpdu->cbu_flags; 364 switch (cpdu->cbu_protover) { 365 case BSTP_PROTO_STP: 366 flags &= BSTP_PDU_STPMASK; 367 /* A STP BPDU explicitly conveys a Designated Port */ 368 cu->cu_role = BSTP_ROLE_DESIGNATED; 369 break; 370 371 case BSTP_PROTO_RSTP: 372 flags &= BSTP_PDU_RSTPMASK; 373 break; 374 } 375 376 cu->cu_topology_change_ack = 377 (flags & BSTP_PDU_F_TCA) ? 1 : 0; 378 cu->cu_proposal = 379 (flags & BSTP_PDU_F_P) ? 1 : 0; 380 cu->cu_agree = 381 (flags & BSTP_PDU_F_A) ? 1 : 0; 382 cu->cu_learning = 383 (flags & BSTP_PDU_F_L) ? 1 : 0; 384 cu->cu_forwarding = 385 (flags & BSTP_PDU_F_F) ? 1 : 0; 386 cu->cu_topology_change = 387 (flags & BSTP_PDU_F_TC) ? 1 : 0; 388 389 switch ((flags & BSTP_PDU_PRMASK) >> BSTP_PDU_PRSHIFT) { 390 case BSTP_PDU_F_ROOT: 391 cu->cu_role = BSTP_ROLE_ROOT; 392 break; 393 case BSTP_PDU_F_ALT: 394 cu->cu_role = BSTP_ROLE_ALTERNATE; 395 break; 396 case BSTP_PDU_F_DESG: 397 cu->cu_role = BSTP_ROLE_DESIGNATED; 398 break; 399 } 400} 401 402static void 403bstp_send_bpdu(struct bstp_state *bs, struct bstp_port *bp, 404 struct bstp_cbpdu *bpdu) 405{ 406 struct ifnet *ifp; 407 struct mbuf *m; 408 struct ether_header *eh; 409 410 BSTP_LOCK_ASSERT(bs); 411 412 ifp = bp->bp_ifp; 413 414 if ((ifp->if_flags & IFF_RUNNING) == 0) 415 return; 416 417 MGETHDR(m, M_DONTWAIT, MT_DATA); 418 if (m == NULL) 419 return; 420 421 eh = mtod(m, struct ether_header *); 422 423 bpdu->cbu_ssap = bpdu->cbu_dsap = LLC_8021D_LSAP; 424 bpdu->cbu_ctl = LLC_UI; 425 bpdu->cbu_protoid = htons(BSTP_PROTO_ID); 426 427 memcpy(eh->ether_shost, ifnet_lladdr(ifp), ETHER_ADDR_LEN); 428 memcpy(eh->ether_dhost, bstp_etheraddr, ETHER_ADDR_LEN); 429 430 switch (bpdu->cbu_bpdutype) { 431 case BSTP_MSGTYPE_CFG: 432 bpdu->cbu_protover = BSTP_PROTO_STP; 433 m->m_pkthdr.len = sizeof(*eh) + BSTP_BPDU_STP_LEN; 434 eh->ether_type = htons(BSTP_BPDU_STP_LEN); 435 memcpy(mtod(m, caddr_t) + sizeof(*eh), bpdu, 436 BSTP_BPDU_STP_LEN); 437 break; 438 439 case BSTP_MSGTYPE_RSTP: 440 bpdu->cbu_protover = BSTP_PROTO_RSTP; 441 bpdu->cbu_versionlen = htons(0); 442 m->m_pkthdr.len = sizeof(*eh) + BSTP_BPDU_RSTP_LEN; 443 eh->ether_type = htons(BSTP_BPDU_RSTP_LEN); 444 memcpy(mtod(m, caddr_t) + sizeof(*eh), bpdu, 445 BSTP_BPDU_RSTP_LEN); 446 break; 447 448 default: 449 panic("not implemented"); 450 } 451 m->m_pkthdr.rcvif = ifp; 452 m->m_len = m->m_pkthdr.len; 453 454 bp->bp_txcount++; 455 bstp_enqueue(ifp, m); 456} 457 458static void 459bstp_enqueue(struct ifnet *dst_ifp, struct mbuf *m) 460{ 461 errno_t error = 0; 462 u_int32_t len = m->m_pkthdr.len; 463 464 m->m_flags |= M_PROTO1; //set to avoid loops 465 466 error = ifnet_output_raw(dst_ifp, 0, m); 467 if (error == 0) { 468 (void) ifnet_stat_increment_out(dst_ifp, 1, len, 0); 469 } else { 470 (void) ifnet_stat_increment_out(dst_ifp, 0, 0, 1); 471 } 472} 473 474static int 475bstp_pdu_flags(struct bstp_port *bp) 476{ 477 int flags = 0; 478 479 if (bp->bp_proposing && bp->bp_state != BSTP_IFSTATE_FORWARDING) 480 flags |= BSTP_PDU_F_P; 481 482 if (bp->bp_agree) 483 flags |= BSTP_PDU_F_A; 484 485 if (bp->bp_tc_timer.active) 486 flags |= BSTP_PDU_F_TC; 487 488 if (bp->bp_tc_ack) 489 flags |= BSTP_PDU_F_TCA; 490 491 switch (bp->bp_state) { 492 case BSTP_IFSTATE_LEARNING: 493 flags |= BSTP_PDU_F_L; 494 break; 495 496 case BSTP_IFSTATE_FORWARDING: 497 flags |= (BSTP_PDU_F_L | BSTP_PDU_F_F); 498 break; 499 } 500 501 switch (bp->bp_role) { 502 case BSTP_ROLE_ROOT: 503 flags |= 504 (BSTP_PDU_F_ROOT << BSTP_PDU_PRSHIFT); 505 break; 506 507 case BSTP_ROLE_ALTERNATE: 508 case BSTP_ROLE_BACKUP: /* fall through */ 509 flags |= 510 (BSTP_PDU_F_ALT << BSTP_PDU_PRSHIFT); 511 break; 512 513 case BSTP_ROLE_DESIGNATED: 514 flags |= 515 (BSTP_PDU_F_DESG << BSTP_PDU_PRSHIFT); 516 break; 517 } 518 519 /* Strip off unused flags in either mode */ 520 switch (bp->bp_protover) { 521 case BSTP_PROTO_STP: 522 flags &= BSTP_PDU_STPMASK; 523 break; 524 case BSTP_PROTO_RSTP: 525 flags &= BSTP_PDU_RSTPMASK; 526 break; 527 } 528 return (flags); 529} 530 531struct mbuf * 532bstp_input(struct bstp_port *bp, __unused struct ifnet *ifp, struct mbuf *m) 533{ 534 struct bstp_state *bs = bp->bp_bs; 535 struct ether_header *eh; 536 struct bstp_tbpdu tpdu; 537 uint16_t len; 538 539 if (bp->bp_active == 0) { 540 m_freem(m); 541 return (NULL); 542 } 543 544 BSTP_LOCK(bs); 545 546 eh = mtod(m, struct ether_header *); 547 548 len = ntohs(eh->ether_type); 549 if (len < sizeof(tpdu)) 550 goto out; 551 552 m_adj(m, ETHER_HDR_LEN); 553 554 if (m->m_pkthdr.len > len) 555 m_adj(m, len - m->m_pkthdr.len); 556 if ((unsigned int)m->m_len < sizeof(tpdu) && 557 (m = m_pullup(m, sizeof(tpdu))) == NULL) 558 goto out; 559 560 memcpy(&tpdu, mtod(m, caddr_t), sizeof(tpdu)); 561 562 /* basic packet checks */ 563 if (tpdu.tbu_dsap != LLC_8021D_LSAP || 564 tpdu.tbu_ssap != LLC_8021D_LSAP || 565 tpdu.tbu_ctl != LLC_UI) 566 goto out; 567 if (tpdu.tbu_protoid != BSTP_PROTO_ID) 568 goto out; 569 570 /* 571 * We can treat later versions of the PDU as the same as the maximum 572 * version we implement. All additional parameters/flags are ignored. 573 */ 574 if (tpdu.tbu_protover > BSTP_PROTO_MAX) 575 tpdu.tbu_protover = BSTP_PROTO_MAX; 576 577 if (tpdu.tbu_protover != bp->bp_protover) { 578 /* 579 * Wait for the migration delay timer to expire before changing 580 * protocol version to avoid flip-flops. 581 */ 582 if (bp->bp_flags & BSTP_PORT_CANMIGRATE) 583 bstp_set_port_proto(bp, tpdu.tbu_protover); 584 else 585 goto out; 586 } 587 588 /* Clear operedge upon receiving a PDU on the port */ 589 bp->bp_operedge = 0; 590 bstp_timer_start(&bp->bp_edge_delay_timer, 591 BSTP_DEFAULT_MIGRATE_DELAY); 592 593 switch (tpdu.tbu_protover) { 594 case BSTP_PROTO_STP: 595 bstp_received_stp(bs, bp, &m, &tpdu); 596 break; 597 598 case BSTP_PROTO_RSTP: 599 bstp_received_rstp(bs, bp, &m, &tpdu); 600 break; 601 } 602out: 603 BSTP_UNLOCK(bs); 604 if (m) 605 m_freem(m); 606 return (NULL); 607} 608 609static void 610bstp_received_stp(struct bstp_state *bs, struct bstp_port *bp, 611 struct mbuf **mp, struct bstp_tbpdu *tpdu) 612{ 613 struct bstp_cbpdu cpdu; 614 struct bstp_config_unit *cu = &bp->bp_msg_cu; 615 struct bstp_tcn_unit tu; 616 617 switch (tpdu->tbu_bpdutype) { 618 case BSTP_MSGTYPE_TCN: 619 tu.tu_message_type = tpdu->tbu_bpdutype; 620 bstp_received_tcn(bs, bp, &tu); 621 break; 622 case BSTP_MSGTYPE_CFG: 623 if ((*mp)->m_len < BSTP_BPDU_STP_LEN && 624 (*mp = m_pullup(*mp, BSTP_BPDU_STP_LEN)) == NULL) 625 return; 626 memcpy(&cpdu, mtod(*mp, caddr_t), BSTP_BPDU_STP_LEN); 627 628 bstp_decode_bpdu(bp, &cpdu, cu); 629 bstp_received_bpdu(bs, bp, cu); 630 break; 631 } 632} 633 634static void 635bstp_received_rstp(struct bstp_state *bs, struct bstp_port *bp, 636 struct mbuf **mp, struct bstp_tbpdu *tpdu) 637{ 638 struct bstp_cbpdu cpdu; 639 struct bstp_config_unit *cu = &bp->bp_msg_cu; 640 641 if (tpdu->tbu_bpdutype != BSTP_MSGTYPE_RSTP) 642 return; 643 644 if ((*mp)->m_len < BSTP_BPDU_RSTP_LEN && 645 (*mp = m_pullup(*mp, BSTP_BPDU_RSTP_LEN)) == NULL) 646 return; 647 memcpy(&cpdu, mtod(*mp, caddr_t), BSTP_BPDU_RSTP_LEN); 648 649 bstp_decode_bpdu(bp, &cpdu, cu); 650 bstp_received_bpdu(bs, bp, cu); 651} 652 653static void 654bstp_received_tcn(__unused struct bstp_state *bs, struct bstp_port *bp, 655 __unused struct bstp_tcn_unit *tcn) 656{ 657 bp->bp_rcvdtcn = 1; 658 bstp_update_tc(bp); 659} 660 661static void 662bstp_received_bpdu(struct bstp_state *bs, struct bstp_port *bp, 663 struct bstp_config_unit *cu) 664{ 665 int type; 666 667 BSTP_LOCK_ASSERT(bs); 668 669 /* We need to have transitioned to INFO_MINE before proceeding */ 670 switch (bp->bp_infois) { 671 case BSTP_INFO_DISABLED: 672 case BSTP_INFO_AGED: 673 return; 674 } 675 676 type = bstp_pdu_rcvtype(bp, cu); 677 678 switch (type) { 679 case BSTP_PDU_SUPERIOR: 680 bs->bs_allsynced = 0; 681 bp->bp_agreed = 0; 682 bp->bp_proposing = 0; 683 684 if (cu->cu_proposal && cu->cu_forwarding == 0) 685 bp->bp_proposed = 1; 686 if (cu->cu_topology_change) 687 bp->bp_rcvdtc = 1; 688 if (cu->cu_topology_change_ack) 689 bp->bp_rcvdtca = 1; 690 691 if (bp->bp_agree && 692 !bstp_pdu_bettersame(bp, BSTP_INFO_RECEIVED)) 693 bp->bp_agree = 0; 694 695 /* copy the received priority and timers to the port */ 696 bp->bp_port_pv = cu->cu_pv; 697 bp->bp_port_msg_age = cu->cu_message_age; 698 bp->bp_port_max_age = cu->cu_max_age; 699 bp->bp_port_fdelay = cu->cu_forward_delay; 700 bp->bp_port_htime = 701 (cu->cu_hello_time > BSTP_MIN_HELLO_TIME ? 702 cu->cu_hello_time : BSTP_MIN_HELLO_TIME); 703 704 /* set expiry for the new info */ 705 bstp_set_timer_msgage(bp); 706 707 bp->bp_infois = BSTP_INFO_RECEIVED; 708 bstp_assign_roles(bs); 709 break; 710 711 case BSTP_PDU_REPEATED: 712 if (cu->cu_proposal && cu->cu_forwarding == 0) 713 bp->bp_proposed = 1; 714 if (cu->cu_topology_change) 715 bp->bp_rcvdtc = 1; 716 if (cu->cu_topology_change_ack) 717 bp->bp_rcvdtca = 1; 718 719 /* rearm the age timer */ 720 bstp_set_timer_msgage(bp); 721 break; 722 723 case BSTP_PDU_INFERIOR: 724 if (cu->cu_learning) { 725 bp->bp_agreed = 1; 726 bp->bp_proposing = 0; 727 } 728 break; 729 730 case BSTP_PDU_INFERIORALT: 731 /* 732 * only point to point links are allowed fast 733 * transitions to forwarding. 734 */ 735 if (cu->cu_agree && bp->bp_ptp_link) { 736 bp->bp_agreed = 1; 737 bp->bp_proposing = 0; 738 } else 739 bp->bp_agreed = 0; 740 741 if (cu->cu_topology_change) 742 bp->bp_rcvdtc = 1; 743 if (cu->cu_topology_change_ack) 744 bp->bp_rcvdtca = 1; 745 break; 746 747 case BSTP_PDU_OTHER: 748 return; /* do nothing */ 749 } 750 /* update the state machines with the new data */ 751 bstp_update_state(bs, bp); 752} 753 754static int 755bstp_pdu_rcvtype(struct bstp_port *bp, struct bstp_config_unit *cu) 756{ 757 int type; 758 759 /* default return type */ 760 type = BSTP_PDU_OTHER; 761 762 switch (cu->cu_role) { 763 case BSTP_ROLE_DESIGNATED: 764 if (bstp_info_superior(&bp->bp_port_pv, &cu->cu_pv)) 765 /* bpdu priority is superior */ 766 type = BSTP_PDU_SUPERIOR; 767 else if (bstp_info_cmp(&bp->bp_port_pv, &cu->cu_pv) == 768 INFO_SAME) { 769 if (bp->bp_port_msg_age != cu->cu_message_age || 770 bp->bp_port_max_age != cu->cu_max_age || 771 bp->bp_port_fdelay != cu->cu_forward_delay || 772 bp->bp_port_htime != cu->cu_hello_time) 773 /* bpdu priority is equal and timers differ */ 774 type = BSTP_PDU_SUPERIOR; 775 else 776 /* bpdu is equal */ 777 type = BSTP_PDU_REPEATED; 778 } else 779 /* bpdu priority is worse */ 780 type = BSTP_PDU_INFERIOR; 781 782 break; 783 784 case BSTP_ROLE_ROOT: 785 case BSTP_ROLE_ALTERNATE: 786 case BSTP_ROLE_BACKUP: 787 if (bstp_info_cmp(&bp->bp_port_pv, &cu->cu_pv) <= INFO_SAME) 788 /* 789 * not a designated port and priority is the same or 790 * worse 791 */ 792 type = BSTP_PDU_INFERIORALT; 793 break; 794 } 795 796 return (type); 797} 798 799static int 800bstp_pdu_bettersame(struct bstp_port *bp, int newinfo) 801{ 802 if (newinfo == BSTP_INFO_RECEIVED && 803 bp->bp_infois == BSTP_INFO_RECEIVED && 804 bstp_info_cmp(&bp->bp_port_pv, &bp->bp_msg_cu.cu_pv) >= INFO_SAME) 805 return (1); 806 807 if (newinfo == BSTP_INFO_MINE && 808 bp->bp_infois == BSTP_INFO_MINE && 809 bstp_info_cmp(&bp->bp_port_pv, &bp->bp_desg_pv) >= INFO_SAME) 810 return (1); 811 812 return (0); 813} 814 815static int 816bstp_info_cmp(struct bstp_pri_vector *pv, 817 struct bstp_pri_vector *cpv) 818{ 819 if (cpv->pv_root_id < pv->pv_root_id) 820 return (INFO_BETTER); 821 if (cpv->pv_root_id > pv->pv_root_id) 822 return (INFO_WORSE); 823 824 if (cpv->pv_cost < pv->pv_cost) 825 return (INFO_BETTER); 826 if (cpv->pv_cost > pv->pv_cost) 827 return (INFO_WORSE); 828 829 if (cpv->pv_dbridge_id < pv->pv_dbridge_id) 830 return (INFO_BETTER); 831 if (cpv->pv_dbridge_id > pv->pv_dbridge_id) 832 return (INFO_WORSE); 833 834 if (cpv->pv_dport_id < pv->pv_dport_id) 835 return (INFO_BETTER); 836 if (cpv->pv_dport_id > pv->pv_dport_id) 837 return (INFO_WORSE); 838 839 return (INFO_SAME); 840} 841 842/* 843 * This message priority vector is superior to the port priority vector and 844 * will replace it if, and only if, the message priority vector is better than 845 * the port priority vector, or the message has been transmitted from the same 846 * designated bridge and designated port as the port priority vector. 847 */ 848static int 849bstp_info_superior(struct bstp_pri_vector *pv, 850 struct bstp_pri_vector *cpv) 851{ 852 if (bstp_info_cmp(pv, cpv) == INFO_BETTER || 853 (bstp_same_bridgeid(pv->pv_dbridge_id, cpv->pv_dbridge_id) && 854 (cpv->pv_dport_id & 0xfff) == (pv->pv_dport_id & 0xfff))) 855 return (1); 856 return (0); 857} 858 859static void 860bstp_assign_roles(struct bstp_state *bs) 861{ 862 struct bstp_port *bp, *rbp = NULL; 863 struct bstp_pri_vector pv; 864 865 /* default to our priority vector */ 866 bs->bs_root_pv = bs->bs_bridge_pv; 867 bs->bs_root_msg_age = 0; 868 bs->bs_root_max_age = bs->bs_bridge_max_age; 869 bs->bs_root_fdelay = bs->bs_bridge_fdelay; 870 bs->bs_root_htime = bs->bs_bridge_htime; 871 bs->bs_root_port = NULL; 872 873 /* check if any recieved info supersedes us */ 874 LIST_FOREACH(bp, &bs->bs_bplist, bp_next) { 875 if (bp->bp_infois != BSTP_INFO_RECEIVED) 876 continue; 877 878 pv = bp->bp_port_pv; 879 pv.pv_cost += bp->bp_path_cost; 880 881 /* 882 * The root priority vector is the best of the set comprising 883 * the bridge priority vector plus all root path priority 884 * vectors whose bridge address is not equal to us. 885 */ 886 if (bstp_same_bridgeid(pv.pv_dbridge_id, 887 bs->bs_bridge_pv.pv_dbridge_id) == 0 && 888 bstp_info_cmp(&bs->bs_root_pv, &pv) == INFO_BETTER) { 889 /* the port vector replaces the root */ 890 bs->bs_root_pv = pv; 891 bs->bs_root_msg_age = bp->bp_port_msg_age + 892 BSTP_MESSAGE_AGE_INCR; 893 bs->bs_root_max_age = bp->bp_port_max_age; 894 bs->bs_root_fdelay = bp->bp_port_fdelay; 895 bs->bs_root_htime = bp->bp_port_htime; 896 rbp = bp; 897 } 898 } 899 900 LIST_FOREACH(bp, &bs->bs_bplist, bp_next) { 901 /* calculate the port designated vector */ 902 bp->bp_desg_pv.pv_root_id = bs->bs_root_pv.pv_root_id; 903 bp->bp_desg_pv.pv_cost = bs->bs_root_pv.pv_cost; 904 bp->bp_desg_pv.pv_dbridge_id = bs->bs_bridge_pv.pv_dbridge_id; 905 bp->bp_desg_pv.pv_dport_id = bp->bp_port_id; 906 bp->bp_desg_pv.pv_port_id = bp->bp_port_id; 907 908 /* calculate designated times */ 909 bp->bp_desg_msg_age = bs->bs_root_msg_age; 910 bp->bp_desg_max_age = bs->bs_root_max_age; 911 bp->bp_desg_fdelay = bs->bs_root_fdelay; 912 bp->bp_desg_htime = bs->bs_bridge_htime; 913 914 915 switch (bp->bp_infois) { 916 case BSTP_INFO_DISABLED: 917 bstp_set_port_role(bp, BSTP_ROLE_DISABLED); 918 break; 919 920 case BSTP_INFO_AGED: 921 bstp_set_port_role(bp, BSTP_ROLE_DESIGNATED); 922 bstp_update_info(bp); 923 break; 924 925 case BSTP_INFO_MINE: 926 bstp_set_port_role(bp, BSTP_ROLE_DESIGNATED); 927 /* update the port info if stale */ 928 if (bstp_info_cmp(&bp->bp_port_pv, 929 &bp->bp_desg_pv) != INFO_SAME || 930 (rbp != NULL && 931 (bp->bp_port_msg_age != rbp->bp_port_msg_age || 932 bp->bp_port_max_age != rbp->bp_port_max_age || 933 bp->bp_port_fdelay != rbp->bp_port_fdelay || 934 bp->bp_port_htime != rbp->bp_port_htime))) 935 bstp_update_info(bp); 936 break; 937 938 case BSTP_INFO_RECEIVED: 939 if (bp == rbp) { 940 /* 941 * root priority is derived from this 942 * port, make it the root port. 943 */ 944 bstp_set_port_role(bp, BSTP_ROLE_ROOT); 945 bs->bs_root_port = bp; 946 } else if (bstp_info_cmp(&bp->bp_port_pv, 947 &bp->bp_desg_pv) == INFO_BETTER) { 948 /* 949 * the port priority is lower than the root 950 * port. 951 */ 952 bstp_set_port_role(bp, BSTP_ROLE_DESIGNATED); 953 bstp_update_info(bp); 954 } else { 955 if (bstp_same_bridgeid( 956 bp->bp_port_pv.pv_dbridge_id, 957 bs->bs_bridge_pv.pv_dbridge_id)) { 958 /* 959 * the designated bridge refers to 960 * another port on this bridge. 961 */ 962 bstp_set_port_role(bp, 963 BSTP_ROLE_BACKUP); 964 } else { 965 /* 966 * the port is an inferior path to the 967 * root bridge. 968 */ 969 bstp_set_port_role(bp, 970 BSTP_ROLE_ALTERNATE); 971 } 972 } 973 break; 974 } 975 } 976} 977 978static void 979bstp_update_state(struct bstp_state *bs, struct bstp_port *bp) 980{ 981 struct bstp_port *bp2; 982 int synced; 983 984 BSTP_LOCK_ASSERT(bs); 985 986 /* check if all the ports have syncronised again */ 987 if (!bs->bs_allsynced) { 988 synced = 1; 989 LIST_FOREACH(bp2, &bs->bs_bplist, bp_next) { 990 if (!(bp2->bp_synced || 991 bp2->bp_role == BSTP_ROLE_ROOT)) { 992 synced = 0; 993 break; 994 } 995 } 996 bs->bs_allsynced = synced; 997 } 998 999 bstp_update_roles(bs, bp); 1000 bstp_update_tc(bp); 1001} 1002 1003static void 1004bstp_update_roles(struct bstp_state *bs, struct bstp_port *bp) 1005{ 1006 switch (bp->bp_role) { 1007 case BSTP_ROLE_DISABLED: 1008 /* Clear any flags if set */ 1009 if (bp->bp_sync || !bp->bp_synced || bp->bp_reroot) { 1010 bp->bp_sync = 0; 1011 bp->bp_synced = 1; 1012 bp->bp_reroot = 0; 1013 } 1014 break; 1015 1016 case BSTP_ROLE_ALTERNATE: 1017 case BSTP_ROLE_BACKUP: 1018 if ((bs->bs_allsynced && !bp->bp_agree) || 1019 (bp->bp_proposed && bp->bp_agree)) { 1020 bp->bp_proposed = 0; 1021 bp->bp_agree = 1; 1022 bp->bp_flags |= BSTP_PORT_NEWINFO; 1023 DPRINTF("%s -> ALTERNATE_AGREED\n", 1024 bp->bp_ifp->if_xname); 1025 } 1026 1027 if (bp->bp_proposed && !bp->bp_agree) { 1028 bstp_set_all_sync(bs); 1029 bp->bp_proposed = 0; 1030 DPRINTF("%s -> ALTERNATE_PROPOSED\n", 1031 bp->bp_ifp->if_xname); 1032 } 1033 1034 /* Clear any flags if set */ 1035 if (bp->bp_sync || !bp->bp_synced || bp->bp_reroot) { 1036 bp->bp_sync = 0; 1037 bp->bp_synced = 1; 1038 bp->bp_reroot = 0; 1039 DPRINTF("%s -> ALTERNATE_PORT\n", bp->bp_ifp->if_xname); 1040 } 1041 break; 1042 1043 case BSTP_ROLE_ROOT: 1044 if (bp->bp_state != BSTP_IFSTATE_FORWARDING && !bp->bp_reroot) { 1045 bstp_set_all_reroot(bs); 1046 DPRINTF("%s -> ROOT_REROOT\n", bp->bp_ifp->if_xname); 1047 } 1048 1049 if ((bs->bs_allsynced && !bp->bp_agree) || 1050 (bp->bp_proposed && bp->bp_agree)) { 1051 bp->bp_proposed = 0; 1052 bp->bp_sync = 0; 1053 bp->bp_agree = 1; 1054 bp->bp_flags |= BSTP_PORT_NEWINFO; 1055 DPRINTF("%s -> ROOT_AGREED\n", bp->bp_ifp->if_xname); 1056 } 1057 1058 if (bp->bp_proposed && !bp->bp_agree) { 1059 bstp_set_all_sync(bs); 1060 bp->bp_proposed = 0; 1061 DPRINTF("%s -> ROOT_PROPOSED\n", bp->bp_ifp->if_xname); 1062 } 1063 1064 if (bp->bp_state != BSTP_IFSTATE_FORWARDING && 1065 (bp->bp_forward_delay_timer.active == 0 || 1066 (bstp_rerooted(bs, bp) && 1067 bp->bp_recent_backup_timer.active == 0 && 1068 bp->bp_protover == BSTP_PROTO_RSTP))) { 1069 switch (bp->bp_state) { 1070 case BSTP_IFSTATE_DISCARDING: 1071 bstp_set_port_state(bp, BSTP_IFSTATE_LEARNING); 1072 break; 1073 case BSTP_IFSTATE_LEARNING: 1074 bstp_set_port_state(bp, 1075 BSTP_IFSTATE_FORWARDING); 1076 break; 1077 } 1078 } 1079 1080 if (bp->bp_state == BSTP_IFSTATE_FORWARDING && bp->bp_reroot) { 1081 bp->bp_reroot = 0; 1082 DPRINTF("%s -> ROOT_REROOTED\n", bp->bp_ifp->if_xname); 1083 } 1084 break; 1085 1086 case BSTP_ROLE_DESIGNATED: 1087 if (bp->bp_recent_root_timer.active == 0 && bp->bp_reroot) { 1088 bp->bp_reroot = 0; 1089 DPRINTF("%s -> DESIGNATED_RETIRED\n", 1090 bp->bp_ifp->if_xname); 1091 } 1092 1093 if ((bp->bp_state == BSTP_IFSTATE_DISCARDING && 1094 !bp->bp_synced) || (bp->bp_agreed && !bp->bp_synced) || 1095 (bp->bp_operedge && !bp->bp_synced) || 1096 (bp->bp_sync && bp->bp_synced)) { 1097 bstp_timer_stop(&bp->bp_recent_root_timer); 1098 bp->bp_synced = 1; 1099 bp->bp_sync = 0; 1100 DPRINTF("%s -> DESIGNATED_SYNCED\n", 1101 bp->bp_ifp->if_xname); 1102 } 1103 1104 if (bp->bp_state != BSTP_IFSTATE_FORWARDING && 1105 !bp->bp_agreed && !bp->bp_proposing && 1106 !bp->bp_operedge) { 1107 bp->bp_proposing = 1; 1108 bp->bp_flags |= BSTP_PORT_NEWINFO; 1109 bstp_timer_start(&bp->bp_edge_delay_timer, 1110 (bp->bp_ptp_link ? BSTP_DEFAULT_MIGRATE_DELAY : 1111 bp->bp_desg_max_age)); 1112 DPRINTF("%s -> DESIGNATED_PROPOSE\n", 1113 bp->bp_ifp->if_xname); 1114 } 1115 1116 if (bp->bp_state != BSTP_IFSTATE_FORWARDING && 1117 (bp->bp_forward_delay_timer.active == 0 || bp->bp_agreed || 1118 bp->bp_operedge) && 1119 (bp->bp_recent_root_timer.active == 0 || !bp->bp_reroot) && 1120 !bp->bp_sync) { 1121#ifdef BRIDGESTP_DEBUG 1122 if (bp->bp_agreed) 1123 DPRINTF("%s -> AGREED\n", bp->bp_ifp->if_xname); 1124#endif /* BRIDGESTP_DEBUG */ 1125 /* 1126 * If agreed|operedge then go straight to forwarding, 1127 * otherwise follow discard -> learn -> forward. 1128 */ 1129 if (bp->bp_agreed || bp->bp_operedge || 1130 bp->bp_state == BSTP_IFSTATE_LEARNING) { 1131 bstp_set_port_state(bp, 1132 BSTP_IFSTATE_FORWARDING); 1133 bp->bp_agreed = bp->bp_protover; 1134 } else if (bp->bp_state == BSTP_IFSTATE_DISCARDING) 1135 bstp_set_port_state(bp, BSTP_IFSTATE_LEARNING); 1136 } 1137 1138 if (((bp->bp_sync && !bp->bp_synced) || 1139 (bp->bp_reroot && bp->bp_recent_root_timer.active) || 1140 (bp->bp_flags & BSTP_PORT_DISPUTED)) && !bp->bp_operedge && 1141 bp->bp_state != BSTP_IFSTATE_DISCARDING) { 1142 bstp_set_port_state(bp, BSTP_IFSTATE_DISCARDING); 1143 bp->bp_flags &= ~BSTP_PORT_DISPUTED; 1144 bstp_timer_start(&bp->bp_forward_delay_timer, 1145 bp->bp_protover == BSTP_PROTO_RSTP ? 1146 bp->bp_desg_htime : bp->bp_desg_fdelay); 1147 DPRINTF("%s -> DESIGNATED_DISCARD\n", 1148 bp->bp_ifp->if_xname); 1149 } 1150 break; 1151 } 1152 1153 if (bp->bp_flags & BSTP_PORT_NEWINFO) 1154 bstp_transmit(bs, bp); 1155} 1156 1157static void 1158bstp_update_tc(struct bstp_port *bp) 1159{ 1160 switch (bp->bp_tcstate) { 1161 case BSTP_TCSTATE_ACTIVE: 1162 if ((bp->bp_role != BSTP_ROLE_DESIGNATED && 1163 bp->bp_role != BSTP_ROLE_ROOT) || bp->bp_operedge) 1164 bstp_set_port_tc(bp, BSTP_TCSTATE_LEARNING); 1165 1166 if (bp->bp_rcvdtcn) 1167 bstp_set_port_tc(bp, BSTP_TCSTATE_TCN); 1168 if (bp->bp_rcvdtc) 1169 bstp_set_port_tc(bp, BSTP_TCSTATE_TC); 1170 1171 if (bp->bp_tc_prop && !bp->bp_operedge) 1172 bstp_set_port_tc(bp, BSTP_TCSTATE_PROPAG); 1173 1174 if (bp->bp_rcvdtca) 1175 bstp_set_port_tc(bp, BSTP_TCSTATE_ACK); 1176 break; 1177 1178 case BSTP_TCSTATE_INACTIVE: 1179 if ((bp->bp_state == BSTP_IFSTATE_LEARNING || 1180 bp->bp_state == BSTP_IFSTATE_FORWARDING) && 1181 bp->bp_fdbflush == 0) 1182 bstp_set_port_tc(bp, BSTP_TCSTATE_LEARNING); 1183 break; 1184 1185 case BSTP_TCSTATE_LEARNING: 1186 if (bp->bp_rcvdtc || bp->bp_rcvdtcn || bp->bp_rcvdtca || 1187 bp->bp_tc_prop) 1188 bstp_set_port_tc(bp, BSTP_TCSTATE_LEARNING); 1189 else if (bp->bp_role != BSTP_ROLE_DESIGNATED && 1190 bp->bp_role != BSTP_ROLE_ROOT && 1191 bp->bp_state == BSTP_IFSTATE_DISCARDING) 1192 bstp_set_port_tc(bp, BSTP_TCSTATE_INACTIVE); 1193 1194 if ((bp->bp_role == BSTP_ROLE_DESIGNATED || 1195 bp->bp_role == BSTP_ROLE_ROOT) && 1196 bp->bp_state == BSTP_IFSTATE_FORWARDING && 1197 !bp->bp_operedge) 1198 bstp_set_port_tc(bp, BSTP_TCSTATE_DETECTED); 1199 break; 1200 1201 /* these are transient states and go straight back to ACTIVE */ 1202 case BSTP_TCSTATE_DETECTED: 1203 case BSTP_TCSTATE_TCN: 1204 case BSTP_TCSTATE_TC: 1205 case BSTP_TCSTATE_PROPAG: 1206 case BSTP_TCSTATE_ACK: 1207 DPRINTF("Invalid TC state for %s\n", 1208 bp->bp_ifp->if_xname); 1209 break; 1210 } 1211 1212} 1213 1214static void 1215bstp_update_info(struct bstp_port *bp) 1216{ 1217 struct bstp_state *bs = bp->bp_bs; 1218 1219 bp->bp_proposing = 0; 1220 bp->bp_proposed = 0; 1221 1222 if (bp->bp_agreed && !bstp_pdu_bettersame(bp, BSTP_INFO_MINE)) 1223 bp->bp_agreed = 0; 1224 1225 if (bp->bp_synced && !bp->bp_agreed) { 1226 bp->bp_synced = 0; 1227 bs->bs_allsynced = 0; 1228 } 1229 1230 /* copy the designated pv to the port */ 1231 bp->bp_port_pv = bp->bp_desg_pv; 1232 bp->bp_port_msg_age = bp->bp_desg_msg_age; 1233 bp->bp_port_max_age = bp->bp_desg_max_age; 1234 bp->bp_port_fdelay = bp->bp_desg_fdelay; 1235 bp->bp_port_htime = bp->bp_desg_htime; 1236 bp->bp_infois = BSTP_INFO_MINE; 1237 1238 /* Set transmit flag but do not immediately send */ 1239 bp->bp_flags |= BSTP_PORT_NEWINFO; 1240} 1241 1242/* set tcprop on every port other than the caller */ 1243static void 1244bstp_set_other_tcprop(struct bstp_port *bp) 1245{ 1246 struct bstp_state *bs = bp->bp_bs; 1247 struct bstp_port *bp2; 1248 1249 BSTP_LOCK_ASSERT(bs); 1250 1251 LIST_FOREACH(bp2, &bs->bs_bplist, bp_next) { 1252 if (bp2 == bp) 1253 continue; 1254 bp2->bp_tc_prop = 1; 1255 } 1256} 1257 1258static void 1259bstp_set_all_reroot(struct bstp_state *bs) 1260{ 1261 struct bstp_port *bp; 1262 1263 BSTP_LOCK_ASSERT(bs); 1264 1265 LIST_FOREACH(bp, &bs->bs_bplist, bp_next) 1266 bp->bp_reroot = 1; 1267} 1268 1269static void 1270bstp_set_all_sync(struct bstp_state *bs) 1271{ 1272 struct bstp_port *bp; 1273 1274 BSTP_LOCK_ASSERT(bs); 1275 1276 LIST_FOREACH(bp, &bs->bs_bplist, bp_next) { 1277 bp->bp_sync = 1; 1278 bp->bp_synced = 0; /* Not explicit in spec */ 1279 } 1280 1281 bs->bs_allsynced = 0; 1282} 1283 1284static void 1285bstp_set_port_state(struct bstp_port *bp, int state) 1286{ 1287 if (bp->bp_state == state) 1288 return; 1289 1290 bp->bp_state = state; 1291 1292 switch (bp->bp_state) { 1293 case BSTP_IFSTATE_DISCARDING: 1294 DPRINTF("state changed to DISCARDING on %s\n", 1295 bp->bp_ifp->if_xname); 1296 break; 1297 1298 case BSTP_IFSTATE_LEARNING: 1299 DPRINTF("state changed to LEARNING on %s\n", 1300 bp->bp_ifp->if_xname); 1301 1302 bstp_timer_start(&bp->bp_forward_delay_timer, 1303 bp->bp_protover == BSTP_PROTO_RSTP ? 1304 bp->bp_desg_htime : bp->bp_desg_fdelay); 1305 break; 1306 1307 case BSTP_IFSTATE_FORWARDING: 1308 DPRINTF("state changed to FORWARDING on %s\n", 1309 bp->bp_ifp->if_xname); 1310 1311 bstp_timer_stop(&bp->bp_forward_delay_timer); 1312 /* Record that we enabled forwarding */ 1313 bp->bp_forward_transitions++; 1314 break; 1315 } 1316 1317 /* notify the parent bridge */ 1318 bstp_task_enqueue(&bp->bp_statetask); 1319} 1320 1321static void 1322bstp_set_port_role(struct bstp_port *bp, int role) 1323{ 1324 struct bstp_state *bs = bp->bp_bs; 1325 1326 if (bp->bp_role == role) 1327 return; 1328 1329 /* perform pre-change tasks */ 1330 switch (bp->bp_role) { 1331 case BSTP_ROLE_DISABLED: 1332 bstp_timer_start(&bp->bp_forward_delay_timer, 1333 bp->bp_desg_max_age); 1334 break; 1335 1336 case BSTP_ROLE_BACKUP: 1337 bstp_timer_start(&bp->bp_recent_backup_timer, 1338 bp->bp_desg_htime * 2); 1339 /* fall through */ 1340 case BSTP_ROLE_ALTERNATE: 1341 bstp_timer_start(&bp->bp_forward_delay_timer, 1342 bp->bp_desg_fdelay); 1343 bp->bp_sync = 0; 1344 bp->bp_synced = 1; 1345 bp->bp_reroot = 0; 1346 break; 1347 1348 case BSTP_ROLE_ROOT: 1349 bstp_timer_start(&bp->bp_recent_root_timer, 1350 BSTP_DEFAULT_FORWARD_DELAY); 1351 break; 1352 } 1353 1354 bp->bp_role = role; 1355 /* clear values not carried between roles */ 1356 bp->bp_proposing = 0; 1357 bs->bs_allsynced = 0; 1358 1359 /* initialise the new role */ 1360 switch (bp->bp_role) { 1361 case BSTP_ROLE_DISABLED: 1362 case BSTP_ROLE_ALTERNATE: 1363 case BSTP_ROLE_BACKUP: 1364 DPRINTF("%s role -> ALT/BACK/DISABLED\n", 1365 bp->bp_ifp->if_xname); 1366 bstp_set_port_state(bp, BSTP_IFSTATE_DISCARDING); 1367 bstp_timer_stop(&bp->bp_recent_root_timer); 1368 bstp_timer_latch(&bp->bp_forward_delay_timer); 1369 bp->bp_sync = 0; 1370 bp->bp_synced = 1; 1371 bp->bp_reroot = 0; 1372 break; 1373 1374 case BSTP_ROLE_ROOT: 1375 DPRINTF("%s role -> ROOT\n", 1376 bp->bp_ifp->if_xname); 1377 bstp_set_port_state(bp, BSTP_IFSTATE_DISCARDING); 1378 bstp_timer_latch(&bp->bp_recent_root_timer); 1379 bp->bp_proposing = 0; 1380 break; 1381 1382 case BSTP_ROLE_DESIGNATED: 1383 DPRINTF("%s role -> DESIGNATED\n", 1384 bp->bp_ifp->if_xname); 1385 bstp_timer_start(&bp->bp_hello_timer, 1386 bp->bp_desg_htime); 1387 bp->bp_agree = 0; 1388 break; 1389 } 1390 1391 /* let the TC state know that the role changed */ 1392 bstp_update_tc(bp); 1393} 1394 1395static void 1396bstp_set_port_proto(struct bstp_port *bp, int proto) 1397{ 1398 struct bstp_state *bs = bp->bp_bs; 1399 1400 /* supported protocol versions */ 1401 switch (proto) { 1402 case BSTP_PROTO_STP: 1403 /* we can downgrade protocols only */ 1404 bstp_timer_stop(&bp->bp_migrate_delay_timer); 1405 /* clear unsupported features */ 1406 bp->bp_operedge = 0; 1407 /* STP compat mode only uses 16 bits of the 32 */ 1408 if (bp->bp_path_cost > 65535) 1409 bp->bp_path_cost = 65535; 1410 break; 1411 1412 case BSTP_PROTO_RSTP: 1413 bstp_timer_start(&bp->bp_migrate_delay_timer, 1414 bs->bs_migration_delay); 1415 break; 1416 1417 default: 1418 DPRINTF("Unsupported STP version %d\n", proto); 1419 return; 1420 } 1421 1422 bp->bp_protover = proto; 1423 bp->bp_flags &= ~BSTP_PORT_CANMIGRATE; 1424} 1425 1426static void 1427bstp_set_port_tc(struct bstp_port *bp, int state) 1428{ 1429 struct bstp_state *bs = bp->bp_bs; 1430 1431 bp->bp_tcstate = state; 1432 1433 /* initialise the new state */ 1434 switch (bp->bp_tcstate) { 1435 case BSTP_TCSTATE_ACTIVE: 1436 DPRINTF("%s -> TC_ACTIVE\n", bp->bp_ifp->if_xname); 1437 /* nothing to do */ 1438 break; 1439 1440 case BSTP_TCSTATE_INACTIVE: 1441 bstp_timer_stop(&bp->bp_tc_timer); 1442 /* flush routes on the parent bridge */ 1443 bp->bp_fdbflush = 1; 1444 bstp_task_enqueue(&bp->bp_rtagetask); 1445 bp->bp_tc_ack = 0; 1446 DPRINTF("%s -> TC_INACTIVE\n", bp->bp_ifp->if_xname); 1447 break; 1448 1449 case BSTP_TCSTATE_LEARNING: 1450 bp->bp_rcvdtc = 0; 1451 bp->bp_rcvdtcn = 0; 1452 bp->bp_rcvdtca = 0; 1453 bp->bp_tc_prop = 0; 1454 DPRINTF("%s -> TC_LEARNING\n", bp->bp_ifp->if_xname); 1455 break; 1456 1457 case BSTP_TCSTATE_DETECTED: 1458 bstp_set_timer_tc(bp); 1459 bstp_set_other_tcprop(bp); 1460 /* send out notification */ 1461 bp->bp_flags |= BSTP_PORT_NEWINFO; 1462 bstp_transmit(bs, bp); 1463 /* reviewed for getmicrotime usage */ 1464 getmicrotime(&bs->bs_last_tc_time); 1465 DPRINTF("%s -> TC_DETECTED\n", bp->bp_ifp->if_xname); 1466 bp->bp_tcstate = BSTP_TCSTATE_ACTIVE; /* UCT */ 1467 break; 1468 1469 case BSTP_TCSTATE_TCN: 1470 bstp_set_timer_tc(bp); 1471 DPRINTF("%s -> TC_TCN\n", bp->bp_ifp->if_xname); 1472 /* fall through */ 1473 case BSTP_TCSTATE_TC: 1474 bp->bp_rcvdtc = 0; 1475 bp->bp_rcvdtcn = 0; 1476 if (bp->bp_role == BSTP_ROLE_DESIGNATED) 1477 bp->bp_tc_ack = 1; 1478 1479 bstp_set_other_tcprop(bp); 1480 DPRINTF("%s -> TC_TC\n", bp->bp_ifp->if_xname); 1481 bp->bp_tcstate = BSTP_TCSTATE_ACTIVE; /* UCT */ 1482 break; 1483 1484 case BSTP_TCSTATE_PROPAG: 1485 /* flush routes on the parent bridge */ 1486 bp->bp_fdbflush = 1; 1487 bstp_task_enqueue(&bp->bp_rtagetask); 1488 bp->bp_tc_prop = 0; 1489 bstp_set_timer_tc(bp); 1490 DPRINTF("%s -> TC_PROPAG\n", bp->bp_ifp->if_xname); 1491 bp->bp_tcstate = BSTP_TCSTATE_ACTIVE; /* UCT */ 1492 break; 1493 1494 case BSTP_TCSTATE_ACK: 1495 bstp_timer_stop(&bp->bp_tc_timer); 1496 bp->bp_rcvdtca = 0; 1497 DPRINTF("%s -> TC_ACK\n", bp->bp_ifp->if_xname); 1498 bp->bp_tcstate = BSTP_TCSTATE_ACTIVE; /* UCT */ 1499 break; 1500 } 1501} 1502 1503static void 1504bstp_set_timer_tc(struct bstp_port *bp) 1505{ 1506 struct bstp_state *bs = bp->bp_bs; 1507 1508 if (bp->bp_tc_timer.active) 1509 return; 1510 1511 switch (bp->bp_protover) { 1512 case BSTP_PROTO_RSTP: 1513 bstp_timer_start(&bp->bp_tc_timer, 1514 bp->bp_desg_htime + BSTP_TICK_VAL); 1515 bp->bp_flags |= BSTP_PORT_NEWINFO; 1516 break; 1517 1518 case BSTP_PROTO_STP: 1519 bstp_timer_start(&bp->bp_tc_timer, 1520 bs->bs_root_max_age + bs->bs_root_fdelay); 1521 break; 1522 } 1523} 1524 1525static void 1526bstp_set_timer_msgage(struct bstp_port *bp) 1527{ 1528 if (bp->bp_port_msg_age + BSTP_MESSAGE_AGE_INCR <= 1529 bp->bp_port_max_age) { 1530 bstp_timer_start(&bp->bp_message_age_timer, 1531 bp->bp_port_htime * 3); 1532 } else 1533 /* expires immediately */ 1534 bstp_timer_start(&bp->bp_message_age_timer, 0); 1535} 1536 1537static int 1538bstp_rerooted(struct bstp_state *bs, struct bstp_port *bp) 1539{ 1540 struct bstp_port *bp2; 1541 int rr_set = 0; 1542 1543 LIST_FOREACH(bp2, &bs->bs_bplist, bp_next) { 1544 if (bp2 == bp) 1545 continue; 1546 if (bp2->bp_recent_root_timer.active) { 1547 rr_set = 1; 1548 break; 1549 } 1550 } 1551 return (!rr_set); 1552} 1553 1554int 1555bstp_set_htime(struct bstp_state *bs, int t) 1556{ 1557 /* convert seconds to ticks */ 1558 t *= BSTP_TICK_VAL; 1559 1560 /* value can only be changed in leagacy stp mode */ 1561 if (bs->bs_protover != BSTP_PROTO_STP) 1562 return (EPERM); 1563 1564 if (t < BSTP_MIN_HELLO_TIME || t > BSTP_MAX_HELLO_TIME) 1565 return (EINVAL); 1566 1567 BSTP_LOCK(bs); 1568 bs->bs_bridge_htime = t; 1569 bstp_reinit(bs); 1570 BSTP_UNLOCK(bs); 1571 return (0); 1572} 1573 1574int 1575bstp_set_fdelay(struct bstp_state *bs, int t) 1576{ 1577 /* convert seconds to ticks */ 1578 t *= BSTP_TICK_VAL; 1579 1580 if (t < BSTP_MIN_FORWARD_DELAY || t > BSTP_MAX_FORWARD_DELAY) 1581 return (EINVAL); 1582 1583 BSTP_LOCK(bs); 1584 bs->bs_bridge_fdelay = t; 1585 bstp_reinit(bs); 1586 BSTP_UNLOCK(bs); 1587 return (0); 1588} 1589 1590int 1591bstp_set_maxage(struct bstp_state *bs, int t) 1592{ 1593 /* convert seconds to ticks */ 1594 t *= BSTP_TICK_VAL; 1595 1596 if (t < BSTP_MIN_MAX_AGE || t > BSTP_MAX_MAX_AGE) 1597 return (EINVAL); 1598 1599 BSTP_LOCK(bs); 1600 bs->bs_bridge_max_age = t; 1601 bstp_reinit(bs); 1602 BSTP_UNLOCK(bs); 1603 return (0); 1604} 1605 1606int 1607bstp_set_holdcount(struct bstp_state *bs, int count) 1608{ 1609 struct bstp_port *bp; 1610 1611 if (count < BSTP_MIN_HOLD_COUNT || 1612 count > BSTP_MAX_HOLD_COUNT) 1613 return (EINVAL); 1614 1615 BSTP_LOCK(bs); 1616 bs->bs_txholdcount = count; 1617 LIST_FOREACH(bp, &bs->bs_bplist, bp_next) 1618 bp->bp_txcount = 0; 1619 BSTP_UNLOCK(bs); 1620 return (0); 1621} 1622 1623int 1624bstp_set_protocol(struct bstp_state *bs, int proto) 1625{ 1626 struct bstp_port *bp; 1627 1628 switch (proto) { 1629 /* Supported protocol versions */ 1630 case BSTP_PROTO_STP: 1631 case BSTP_PROTO_RSTP: 1632 break; 1633 1634 default: 1635 return (EINVAL); 1636 } 1637 1638 BSTP_LOCK(bs); 1639 bs->bs_protover = proto; 1640 bs->bs_bridge_htime = BSTP_DEFAULT_HELLO_TIME; 1641 LIST_FOREACH(bp, &bs->bs_bplist, bp_next) { 1642 /* reinit state */ 1643 bp->bp_infois = BSTP_INFO_DISABLED; 1644 bp->bp_txcount = 0; 1645 bstp_set_port_proto(bp, bs->bs_protover); 1646 bstp_set_port_role(bp, BSTP_ROLE_DISABLED); 1647 bstp_set_port_tc(bp, BSTP_TCSTATE_INACTIVE); 1648 bstp_timer_stop(&bp->bp_recent_backup_timer); 1649 } 1650 bstp_reinit(bs); 1651 BSTP_UNLOCK(bs); 1652 return (0); 1653} 1654 1655int 1656bstp_set_priority(struct bstp_state *bs, int pri) 1657{ 1658 if (pri < 0 || pri > BSTP_MAX_PRIORITY) 1659 return (EINVAL); 1660 1661 /* Limit to steps of 4096 */ 1662 pri -= pri % 4096; 1663 1664 BSTP_LOCK(bs); 1665 bs->bs_bridge_priority = pri; 1666 bstp_reinit(bs); 1667 BSTP_UNLOCK(bs); 1668 return (0); 1669} 1670 1671int 1672bstp_set_port_priority(struct bstp_port *bp, int pri) 1673{ 1674 struct bstp_state *bs = bp->bp_bs; 1675 1676 if (pri < 0 || pri > BSTP_MAX_PORT_PRIORITY) 1677 return (EINVAL); 1678 1679 /* Limit to steps of 16 */ 1680 pri -= pri % 16; 1681 1682 BSTP_LOCK(bs); 1683 bp->bp_priority = pri; 1684 bstp_reinit(bs); 1685 BSTP_UNLOCK(bs); 1686 return (0); 1687} 1688 1689int 1690bstp_set_path_cost(struct bstp_port *bp, uint32_t path_cost) 1691{ 1692 struct bstp_state *bs = bp->bp_bs; 1693 1694 if (path_cost > BSTP_MAX_PATH_COST) 1695 return (EINVAL); 1696 1697 /* STP compat mode only uses 16 bits of the 32 */ 1698 if (bp->bp_protover == BSTP_PROTO_STP && path_cost > 65535) 1699 path_cost = 65535; 1700 1701 BSTP_LOCK(bs); 1702 1703 if (path_cost == 0) { /* use auto */ 1704 bp->bp_flags &= ~BSTP_PORT_ADMCOST; 1705 bp->bp_path_cost = bstp_calc_path_cost(bp); 1706 } else { 1707 bp->bp_path_cost = path_cost; 1708 bp->bp_flags |= BSTP_PORT_ADMCOST; 1709 } 1710 bstp_reinit(bs); 1711 BSTP_UNLOCK(bs); 1712 return (0); 1713} 1714 1715int 1716bstp_set_edge(struct bstp_port *bp, int set) 1717{ 1718 struct bstp_state *bs = bp->bp_bs; 1719 1720 BSTP_LOCK(bs); 1721 if ((bp->bp_operedge = set) == 0) 1722 bp->bp_flags &= ~BSTP_PORT_ADMEDGE; 1723 else 1724 bp->bp_flags |= BSTP_PORT_ADMEDGE; 1725 BSTP_UNLOCK(bs); 1726 return (0); 1727} 1728 1729int 1730bstp_set_autoedge(struct bstp_port *bp, int set) 1731{ 1732 struct bstp_state *bs = bp->bp_bs; 1733 1734 BSTP_LOCK(bs); 1735 if (set) { 1736 bp->bp_flags |= BSTP_PORT_AUTOEDGE; 1737 /* we may be able to transition straight to edge */ 1738 if (bp->bp_edge_delay_timer.active == 0) 1739 bstp_edge_delay_expiry(bs, bp); 1740 } else 1741 bp->bp_flags &= ~BSTP_PORT_AUTOEDGE; 1742 BSTP_UNLOCK(bs); 1743 return (0); 1744} 1745 1746int 1747bstp_set_ptp(struct bstp_port *bp, int set) 1748{ 1749 struct bstp_state *bs = bp->bp_bs; 1750 1751 BSTP_LOCK(bs); 1752 bp->bp_ptp_link = set; 1753 BSTP_UNLOCK(bs); 1754 return (0); 1755} 1756 1757int 1758bstp_set_autoptp(struct bstp_port *bp, int set) 1759{ 1760 struct bstp_state *bs = bp->bp_bs; 1761 1762 BSTP_LOCK(bs); 1763 if (set) { 1764 bp->bp_flags |= BSTP_PORT_AUTOPTP; 1765 if (bp->bp_role != BSTP_ROLE_DISABLED) 1766 bstp_ifupdstatus(bs, bp); 1767 } else 1768 bp->bp_flags &= ~BSTP_PORT_AUTOPTP; 1769 BSTP_UNLOCK(bs); 1770 return (0); 1771} 1772 1773/* 1774 * Calculate the path cost according to the link speed. 1775 */ 1776static uint32_t 1777bstp_calc_path_cost(struct bstp_port *bp) 1778{ 1779 struct ifnet *ifp = bp->bp_ifp; 1780 uint32_t path_cost; 1781 1782 /* If the priority has been manually set then retain the value */ 1783 if (bp->bp_flags & BSTP_PORT_ADMCOST) 1784 return bp->bp_path_cost; 1785 1786 if (bp->bp_if_link_state == LINK_STATE_DOWN) { 1787 /* Recalc when the link comes up again */ 1788 bp->bp_flags |= BSTP_PORT_PNDCOST; 1789 return (BSTP_DEFAULT_PATH_COST); 1790 } 1791 1792 if (ifp->if_baudrate < 1000) 1793 return (BSTP_DEFAULT_PATH_COST); 1794 1795 /* formula from section 17.14, IEEE Std 802.1D-2004 */ 1796 path_cost = 20000000000ULL / (ifp->if_baudrate / 1000); 1797 1798 if (path_cost > BSTP_MAX_PATH_COST) 1799 path_cost = BSTP_MAX_PATH_COST; 1800 1801 /* STP compat mode only uses 16 bits of the 32 */ 1802 if (bp->bp_protover == BSTP_PROTO_STP && path_cost > 65535) 1803 path_cost = 65535; 1804 1805 return (path_cost); 1806} 1807 1808/* 1809 * Notify the bridge that a port state has changed, we need to do this from a 1810 * taskqueue to avoid a LOR. 1811 */ 1812static void 1813bstp_notify_state(void *arg, __unused int pending) 1814{ 1815 struct bstp_port *bp = (struct bstp_port *)arg; 1816 struct bstp_state *bs = bp->bp_bs; 1817 1818 if (bp->bp_active == 1 && bs->bs_state_cb != NULL) 1819 (*bs->bs_state_cb)(bp->bp_ifp, bp->bp_state); 1820} 1821 1822/* 1823 * Flush the routes on the bridge port, we need to do this from a 1824 * taskqueue to avoid a LOR. 1825 */ 1826static void 1827bstp_notify_rtage(void *arg, __unused int pending) 1828{ 1829 struct bstp_port *bp = (struct bstp_port *)arg; 1830 struct bstp_state *bs = bp->bp_bs; 1831 int age = 0; 1832 1833 BSTP_LOCK(bs); 1834 switch (bp->bp_protover) { 1835 case BSTP_PROTO_STP: 1836 /* convert to seconds */ 1837 age = bp->bp_desg_fdelay / BSTP_TICK_VAL; 1838 break; 1839 1840 case BSTP_PROTO_RSTP: 1841 age = 0; 1842 break; 1843 } 1844 BSTP_UNLOCK(bs); 1845 1846 if (bp->bp_active == 1 && bs->bs_rtage_cb != NULL) 1847 (*bs->bs_rtage_cb)(bp->bp_ifp, age); 1848 1849 /* flush is complete */ 1850 BSTP_LOCK(bs); 1851 bp->bp_fdbflush = 0; 1852 BSTP_UNLOCK(bs); 1853} 1854 1855void 1856bstp_linkstate(struct ifnet *ifp, __unused int state) 1857{ 1858 struct bstp_state *bs; 1859 struct bstp_port *bp; 1860 1861 /* search for the stp port */ 1862 lck_mtx_lock(bstp_list_mtx); 1863 LIST_FOREACH(bs, &bstp_list, bs_list) { 1864 BSTP_LOCK(bs); 1865 LIST_FOREACH(bp, &bs->bs_bplist, bp_next) { 1866 if (bp->bp_ifp == ifp) { 1867 bstp_ifupdstatus(bs, bp); 1868 bstp_update_state(bs, bp); 1869 /* it only exists once so return */ 1870 BSTP_UNLOCK(bs); 1871 lck_mtx_unlock(bstp_list_mtx); 1872 return; 1873 } 1874 } 1875 BSTP_UNLOCK(bs); 1876 } 1877 lck_mtx_unlock(bstp_list_mtx); 1878} 1879 1880static void 1881bstp_ifupdstatus(struct bstp_state *bs, struct bstp_port *bp) 1882{ 1883 struct ifnet *ifp = bp->bp_ifp; 1884 struct ifmediareq ifmr; 1885 int error = 0; 1886 1887 BSTP_LOCK_ASSERT(bs); 1888 1889 bzero((char *)&ifmr, sizeof(ifmr)); 1890 error = (*ifp->if_ioctl)(ifp, SIOCGIFMEDIA, (caddr_t)&ifmr); 1891 1892 if ((error == 0) && (ifp->if_flags & IFF_UP)) { 1893 if (ifmr.ifm_status & IFM_ACTIVE) { 1894 /* A full-duplex link is assumed to be point to point */ 1895 if (bp->bp_flags & BSTP_PORT_AUTOPTP) { 1896 bp->bp_ptp_link = 1897 ifmr.ifm_active & IFM_FDX ? 1 : 0; 1898 } 1899 1900 /* Calc the cost if the link was down previously */ 1901 if (bp->bp_flags & BSTP_PORT_PNDCOST) { 1902 bp->bp_path_cost = bstp_calc_path_cost(bp); 1903 bp->bp_flags &= ~BSTP_PORT_PNDCOST; 1904 } 1905 1906 if (bp->bp_role == BSTP_ROLE_DISABLED) 1907 bstp_enable_port(bs, bp); 1908 } else { 1909 if (bp->bp_role != BSTP_ROLE_DISABLED) { 1910 bstp_disable_port(bs, bp); 1911 if ((bp->bp_flags & BSTP_PORT_ADMEDGE) && 1912 bp->bp_protover == BSTP_PROTO_RSTP) 1913 bp->bp_operedge = 1; 1914 } 1915 } 1916 return; 1917 } 1918 1919 if (bp->bp_infois != BSTP_INFO_DISABLED) 1920 bstp_disable_port(bs, bp); 1921} 1922 1923static void 1924bstp_enable_port(struct bstp_state *bs, struct bstp_port *bp) 1925{ 1926 bp->bp_infois = BSTP_INFO_AGED; 1927 bstp_assign_roles(bs); 1928} 1929 1930static void 1931bstp_disable_port(struct bstp_state *bs, struct bstp_port *bp) 1932{ 1933 bp->bp_infois = BSTP_INFO_DISABLED; 1934 bstp_assign_roles(bs); 1935} 1936 1937static void 1938bstp_tick(void *arg) 1939{ 1940 struct bstp_state *bs = arg; 1941 struct bstp_port *bp; 1942 struct timespec ts; 1943 1944 BSTP_LOCK(bs); 1945 1946 if (bs->bs_running == 0) 1947 return; 1948 1949 /* slow timer to catch missed link events */ 1950 if (bstp_timer_expired(&bs->bs_link_timer)) { 1951 LIST_FOREACH(bp, &bs->bs_bplist, bp_next) 1952 bstp_ifupdstatus(bs, bp); 1953 bstp_timer_start(&bs->bs_link_timer, BSTP_LINK_TIMER); 1954 } 1955 1956 LIST_FOREACH(bp, &bs->bs_bplist, bp_next) { 1957 /* no events need to happen for these */ 1958 bstp_timer_expired(&bp->bp_tc_timer); 1959 bstp_timer_expired(&bp->bp_recent_root_timer); 1960 bstp_timer_expired(&bp->bp_forward_delay_timer); 1961 bstp_timer_expired(&bp->bp_recent_backup_timer); 1962 1963 if (bstp_timer_expired(&bp->bp_hello_timer)) 1964 bstp_hello_timer_expiry(bs, bp); 1965 1966 if (bstp_timer_expired(&bp->bp_message_age_timer)) 1967 bstp_message_age_expiry(bs, bp); 1968 1969 if (bstp_timer_expired(&bp->bp_migrate_delay_timer)) 1970 bstp_migrate_delay_expiry(bs, bp); 1971 1972 if (bstp_timer_expired(&bp->bp_edge_delay_timer)) 1973 bstp_edge_delay_expiry(bs, bp); 1974 1975 /* update the various state machines for the port */ 1976 bstp_update_state(bs, bp); 1977 1978 if (bp->bp_txcount > 0) 1979 bp->bp_txcount--; 1980 } 1981 1982 BSTP_UNLOCK(bs); 1983 1984 ts.tv_sec = 1; 1985 ts.tv_nsec = 0; 1986 bsd_timeout(bstp_tick, bs, &ts); 1987} 1988 1989static void 1990bstp_timer_start(struct bstp_timer *t, uint16_t v) 1991{ 1992 t->value = v; 1993 t->active = 1; 1994 t->latched = 0; 1995} 1996 1997static void 1998bstp_timer_stop(struct bstp_timer *t) 1999{ 2000 t->value = 0; 2001 t->active = 0; 2002 t->latched = 0; 2003} 2004 2005static void 2006bstp_timer_latch(struct bstp_timer *t) 2007{ 2008 t->latched = 1; 2009 t->active = 1; 2010} 2011 2012static int 2013bstp_timer_expired(struct bstp_timer *t) 2014{ 2015 if (t->active == 0 || t->latched) 2016 return (0); 2017 t->value -= BSTP_TICK_VAL; 2018 if (t->value <= 0) { 2019 bstp_timer_stop(t); 2020 return (1); 2021 } 2022 return (0); 2023} 2024 2025static void 2026bstp_hello_timer_expiry(struct bstp_state *bs, struct bstp_port *bp) 2027{ 2028 if ((bp->bp_flags & BSTP_PORT_NEWINFO) || 2029 bp->bp_role == BSTP_ROLE_DESIGNATED || 2030 (bp->bp_role == BSTP_ROLE_ROOT && 2031 bp->bp_tc_timer.active == 1)) { 2032 bstp_timer_start(&bp->bp_hello_timer, bp->bp_desg_htime); 2033 bp->bp_flags |= BSTP_PORT_NEWINFO; 2034 bstp_transmit(bs, bp); 2035 } 2036} 2037 2038static void 2039bstp_message_age_expiry(struct bstp_state *bs, struct bstp_port *bp) 2040{ 2041 if (bp->bp_infois == BSTP_INFO_RECEIVED) { 2042 bp->bp_infois = BSTP_INFO_AGED; 2043 bstp_assign_roles(bs); 2044 DPRINTF("aged info on %s\n", bp->bp_ifp->if_xname); 2045 } 2046} 2047 2048static void 2049bstp_migrate_delay_expiry(__unused struct bstp_state *bs, struct bstp_port *bp) 2050{ 2051 bp->bp_flags |= BSTP_PORT_CANMIGRATE; 2052} 2053 2054static void 2055bstp_edge_delay_expiry(__unused struct bstp_state *bs, struct bstp_port *bp) 2056{ 2057 if ((bp->bp_flags & BSTP_PORT_AUTOEDGE) && 2058 bp->bp_protover == BSTP_PROTO_RSTP && bp->bp_proposing && 2059 bp->bp_role == BSTP_ROLE_DESIGNATED) { 2060 bp->bp_operedge = 1; 2061 DPRINTF("%s -> edge port\n", bp->bp_ifp->if_xname); 2062 } 2063} 2064 2065static int 2066bstp_addr_cmp(const uint8_t *a, const uint8_t *b) 2067{ 2068 int i, d; 2069 2070 for (i = 0, d = 0; i < ETHER_ADDR_LEN && d == 0; i++) { 2071 d = ((int)a[i]) - ((int)b[i]); 2072 } 2073 2074 return (d); 2075} 2076 2077/* 2078 * compare the bridge address component of the bridgeid 2079 */ 2080static int 2081bstp_same_bridgeid(uint64_t id1, uint64_t id2) 2082{ 2083 u_char addr1[ETHER_ADDR_LEN]; 2084 u_char addr2[ETHER_ADDR_LEN]; 2085 2086 PV2ADDR(id1, addr1); 2087 PV2ADDR(id2, addr2); 2088 2089 if (bstp_addr_cmp(addr1, addr2) == 0) 2090 return (1); 2091 2092 return (0); 2093} 2094 2095void 2096bstp_reinit(struct bstp_state *bs) 2097{ 2098 struct bstp_port *bp; 2099 struct ifnet *ifp, *mif; 2100 u_char *e_addr; 2101 static const u_char llzero[ETHER_ADDR_LEN]; /* 00:00:00:00:00:00 */ 2102 2103 BSTP_LOCK_ASSERT(bs); 2104 2105 mif = NULL; 2106 /* 2107 * Search through the Ethernet adapters and find the one with the 2108 * lowest value. The adapter which we take the MAC address from does 2109 * not need to be part of the bridge, it just needs to be a unique 2110 * value. 2111 */ 2112 ifnet_head_lock_shared(); 2113 TAILQ_FOREACH(ifp, &ifnet_head, if_link) { 2114 if (ifp->if_type != IFT_ETHER) 2115 continue; 2116 2117 if (bstp_addr_cmp(ifnet_lladdr(ifp), llzero) == 0) 2118 continue; 2119 2120 if (mif == NULL) { 2121 mif = ifp; 2122 continue; 2123 } 2124 if (bstp_addr_cmp(ifnet_lladdr(ifp), ifnet_lladdr(mif)) < 0) { 2125 mif = ifp; 2126 continue; 2127 } 2128 } 2129 ifnet_head_done(); 2130 2131 if (LIST_EMPTY(&bs->bs_bplist) || mif == NULL) { 2132 /* Set the bridge and root id (lower bits) to zero */ 2133 bs->bs_bridge_pv.pv_dbridge_id = 2134 ((uint64_t)bs->bs_bridge_priority) << 48; 2135 bs->bs_bridge_pv.pv_root_id = bs->bs_bridge_pv.pv_dbridge_id; 2136 bs->bs_root_pv = bs->bs_bridge_pv; 2137 /* Disable any remaining ports, they will have no MAC address */ 2138 LIST_FOREACH(bp, &bs->bs_bplist, bp_next) { 2139 bp->bp_infois = BSTP_INFO_DISABLED; 2140 bstp_set_port_role(bp, BSTP_ROLE_DISABLED); 2141 } 2142 bsd_untimeout(bstp_tick, bs); 2143 return; 2144 } 2145 2146 e_addr = ifnet_lladdr(mif); 2147 bs->bs_bridge_pv.pv_dbridge_id = 2148 (((uint64_t)bs->bs_bridge_priority) << 48) | 2149 (((uint64_t)e_addr[0]) << 40) | 2150 (((uint64_t)e_addr[1]) << 32) | 2151 (((uint64_t)e_addr[2]) << 24) | 2152 (((uint64_t)e_addr[3]) << 16) | 2153 (((uint64_t)e_addr[4]) << 8) | 2154 (((uint64_t)e_addr[5])); 2155 2156 bs->bs_bridge_pv.pv_root_id = bs->bs_bridge_pv.pv_dbridge_id; 2157 bs->bs_bridge_pv.pv_cost = 0; 2158 bs->bs_bridge_pv.pv_dport_id = 0; 2159 bs->bs_bridge_pv.pv_port_id = 0; 2160 2161 if (bs->bs_running) 2162 bsd_untimeout(bstp_tick, bs); 2163 2164 LIST_FOREACH(bp, &bs->bs_bplist, bp_next) { 2165 bp->bp_port_id = (bp->bp_priority << 8) | 2166 (bp->bp_ifp->if_index & 0xfff); 2167 bstp_ifupdstatus(bs, bp); 2168 } 2169 2170 bstp_assign_roles(bs); 2171 bstp_timer_start(&bs->bs_link_timer, BSTP_LINK_TIMER); 2172} 2173 2174void 2175bstp_attach(struct bstp_state *bs, struct bstp_cb_ops *cb) 2176{ 2177 BSTP_LOCK_INIT(bs); 2178 LIST_INIT(&bs->bs_bplist); 2179 2180 bs->bs_bridge_max_age = BSTP_DEFAULT_MAX_AGE; 2181 bs->bs_bridge_htime = BSTP_DEFAULT_HELLO_TIME; 2182 bs->bs_bridge_fdelay = BSTP_DEFAULT_FORWARD_DELAY; 2183 bs->bs_bridge_priority = BSTP_DEFAULT_BRIDGE_PRIORITY; 2184 bs->bs_hold_time = BSTP_DEFAULT_HOLD_TIME; 2185 bs->bs_migration_delay = BSTP_DEFAULT_MIGRATE_DELAY; 2186 bs->bs_txholdcount = BSTP_DEFAULT_HOLD_COUNT; 2187 bs->bs_protover = BSTP_PROTO_RSTP; 2188 bs->bs_state_cb = cb->bcb_state; 2189 bs->bs_rtage_cb = cb->bcb_rtage; 2190 2191 /* reviewed for getmicrotime usage */ 2192 getmicrotime(&bs->bs_last_tc_time); 2193 2194 lck_mtx_lock(bstp_list_mtx); 2195 LIST_INSERT_HEAD(&bstp_list, bs, bs_list); 2196 lck_mtx_unlock(bstp_list_mtx); 2197} 2198 2199void 2200bstp_detach(struct bstp_state *bs) 2201{ 2202 KASSERT(LIST_EMPTY(&bs->bs_bplist), ("bstp still active")); 2203 2204 lck_mtx_lock(bstp_list_mtx); 2205 LIST_REMOVE(bs, bs_list); 2206 lck_mtx_unlock(bstp_list_mtx); 2207 bsd_untimeout(bstp_tick, bs); 2208 BSTP_LOCK_DESTROY(bs); 2209} 2210 2211void 2212bstp_init(struct bstp_state *bs) 2213{ 2214 struct timespec ts; 2215 2216 ts.tv_sec = 1; 2217 ts.tv_nsec = 0; 2218 2219 BSTP_LOCK(bs); 2220 bsd_timeout(bstp_tick, bs, &ts); 2221 bs->bs_running = 1; 2222 bstp_reinit(bs); 2223 BSTP_UNLOCK(bs); 2224} 2225 2226void 2227bstp_stop(struct bstp_state *bs) 2228{ 2229 struct bstp_port *bp; 2230 2231 BSTP_LOCK(bs); 2232 2233 LIST_FOREACH(bp, &bs->bs_bplist, bp_next) 2234 bstp_set_port_state(bp, BSTP_IFSTATE_DISCARDING); 2235 2236 bs->bs_running = 0; 2237 bsd_untimeout(bstp_tick, bs); 2238 BSTP_UNLOCK(bs); 2239} 2240 2241int 2242bstp_create(struct bstp_state *bs, struct bstp_port *bp, struct ifnet *ifp) 2243{ 2244 bzero(bp, sizeof(struct bstp_port)); 2245 2246 BSTP_LOCK(bs); 2247 bp->bp_ifp = ifp; 2248 bp->bp_bs = bs; 2249 bp->bp_priority = BSTP_DEFAULT_PORT_PRIORITY; 2250 BSTP_TASK_INIT(&bp->bp_statetask, bstp_notify_state, bp); 2251 BSTP_TASK_INIT(&bp->bp_rtagetask, bstp_notify_rtage, bp); 2252 2253 /* Init state */ 2254 bp->bp_infois = BSTP_INFO_DISABLED; 2255 bp->bp_flags = BSTP_PORT_AUTOEDGE|BSTP_PORT_AUTOPTP; 2256 bstp_set_port_state(bp, BSTP_IFSTATE_DISCARDING); 2257 bstp_set_port_proto(bp, bs->bs_protover); 2258 bstp_set_port_role(bp, BSTP_ROLE_DISABLED); 2259 bstp_set_port_tc(bp, BSTP_TCSTATE_INACTIVE); 2260 bp->bp_path_cost = bstp_calc_path_cost(bp); 2261 BSTP_UNLOCK(bs); 2262 return (0); 2263} 2264 2265int 2266bstp_enable(struct bstp_port *bp) 2267{ 2268 struct bstp_state *bs = bp->bp_bs; 2269 struct ifnet *ifp = bp->bp_ifp; 2270 2271 KASSERT(bp->bp_active == 0, ("already a bstp member")); 2272 2273 switch (ifp->if_type) { 2274 case IFT_ETHER: /* These can do spanning tree. */ 2275 break; 2276 default: 2277 /* Nothing else can. */ 2278 return (EINVAL); 2279 } 2280 2281 BSTP_LOCK(bs); 2282 LIST_INSERT_HEAD(&bs->bs_bplist, bp, bp_next); 2283 bp->bp_active = 1; 2284 bp->bp_flags |= BSTP_PORT_NEWINFO; 2285 bstp_reinit(bs); 2286 bstp_update_roles(bs, bp); 2287 BSTP_UNLOCK(bs); 2288 return (0); 2289} 2290 2291void 2292bstp_disable(struct bstp_port *bp) 2293{ 2294 struct bstp_state *bs = bp->bp_bs; 2295 2296 KASSERT(bp->bp_active == 1, ("not a bstp member")); 2297 2298 BSTP_LOCK(bs); 2299 bstp_disable_port(bs, bp); 2300 LIST_REMOVE(bp, bp_next); 2301 bp->bp_active = 0; 2302 bstp_reinit(bs); 2303 BSTP_UNLOCK(bs); 2304} 2305 2306/* 2307 * The bstp_port structure is about to be freed by the parent bridge. 2308 */ 2309void 2310bstp_destroy(struct bstp_port *bp) 2311{ 2312 KASSERT(bp->bp_active == 0, ("port is still attached")); 2313 bstp_task_drain(&bp->bp_statetask); 2314 bstp_task_drain(&bp->bp_rtagetask); 2315} 2316 2317 2318__private_extern__ void 2319bstp_sys_init(void) 2320{ 2321 lck_grp_attr_t *lck_grp_attr = NULL; 2322 2323 lck_grp_attr = lck_grp_attr_alloc_init(); 2324 bstp_lock_grp = lck_grp_alloc_init("bstp", lck_grp_attr); 2325 bstp_lock_attr = lck_attr_alloc_init(); 2326#if BRIDGE_DEBUG 2327 lck_attr_setdebug(bstp_lock_attr); 2328#endif 2329 lck_mtx_init(bstp_list_mtx, bstp_lock_grp, bstp_lock_attr); 2330 lck_grp_attr_free(lck_grp_attr); 2331 2332 LIST_INIT(&bstp_list); 2333 2334 bstp_create_task_thread(); 2335} 2336 2337 2338 2339static void 2340bstp_create_task_thread(void) 2341{ 2342 kern_return_t error; 2343 2344 lck_grp_attr_t *lck_grp_attr = NULL; 2345 2346 lck_grp_attr = lck_grp_attr_alloc_init(); 2347 bstp_task_grp = lck_grp_alloc_init("bstp_task", lck_grp_attr); 2348 bstp_task_attr = lck_attr_alloc_init(); 2349#if BRIDGE_DEBUG 2350 lck_attr_setdebug(bstp_task_attr); 2351#endif 2352 lck_mtx_init(bstp_task_mtx, bstp_lock_grp, bstp_lock_attr); 2353 lck_grp_attr_free(lck_grp_attr); 2354 2355 error = kernel_thread_start((thread_continue_t)bstp_task_thread_func, NULL, &bstp_task_thread); 2356} 2357 2358 2359static void 2360bstp_task_thread_func(void) 2361{ 2362 struct bstp_task *bt, *tvar; 2363 2364 lck_mtx_lock(bstp_task_mtx); 2365 2366 do { 2367 while(TAILQ_EMPTY(&bstp_task_queue)) { 2368 wakeup(&bstp_task_queue_running); 2369 msleep(&bstp_task_queue, bstp_task_mtx, PZERO, "bstp_task_queue", NULL); 2370 } 2371 2372 TAILQ_FOREACH_SAFE(bt, &bstp_task_queue, bt_next, tvar) { 2373 int count = bt->bt_count; 2374 2375 bt->bt_count = 0; 2376 2377 bstp_task_queue_running = bt; 2378 lck_mtx_unlock(bstp_task_mtx); 2379 2380 (*bt->bt_func)(bt->bt_context, count); 2381 2382 lck_mtx_lock(bstp_task_mtx); 2383 bstp_task_queue_running = NULL; 2384 2385 if (bt->bt_count == 0) 2386 TAILQ_REMOVE(&bstp_task_queue, bt, bt_next); 2387 } 2388 } while (1); 2389 2390 /* UNREACHED */ 2391} 2392 2393static void 2394bstp_task_enqueue(struct bstp_task *bt) 2395{ 2396 lck_mtx_lock(bstp_task_mtx); 2397 2398 if (bt->bt_count) { 2399 bt->bt_count++; 2400 lck_mtx_unlock(bstp_task_mtx); 2401 wakeup(&bstp_task_queue); 2402 return; 2403 } 2404 2405 bt->bt_count = 1; 2406 TAILQ_INSERT_TAIL(&bstp_task_queue, bt, bt_next); 2407 2408 lck_mtx_unlock(bstp_task_mtx); 2409 2410 wakeup(&bstp_task_queue); 2411} 2412 2413static void 2414bstp_task_drain(struct bstp_task *bt) 2415{ 2416 lck_mtx_lock(bstp_task_mtx); 2417 2418 while (bt->bt_count != 0 || bstp_task_queue_running == bt) { 2419 wakeup(&bstp_task_queue); 2420 msleep(&bstp_task_queue_running, bstp_task_mtx, PZERO, "bstp_task_queue", NULL); 2421 } 2422 lck_mtx_unlock(bstp_task_mtx); 2423} 2424 2425 2426