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