]> git.saurik.com Git - apple/xnu.git/blob - bsd/net/bridgestp.c
projects / apple / xnu.git / blob
? search:


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