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