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