2 * Copyright (c) 2000 Jason L. Wright (jason@thought.net)
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. All advertising materials mentioning features or use of this software
14 * must display the following acknowledgement:
15 * This product includes software developed by Jason L. Wright
16 * 4. The name of the author may not be used to endorse or promote products
17 * derived from this software without specific prior written permission.
19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
21 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
23 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
24 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
27 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
28 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
31 * $OpenBSD: bridgestp.c,v 1.5 2001/03/22 03:48:29 jason Exp $
32 * $NetBSD: bridgestp.c,v 1.5 2003/11/28 08:56:48 keihan Exp $
33 * $FreeBSD: src/sys/net/bridgestp.c,v 1.7 2005/10/11 02:58:32 thompsa Exp $
34 * $DragonFly: src/sys/net/bridge/bridgestp.c,v 1.10 2008/11/26 12:49:43 sephe Exp $
38 * Implementation of the spanning tree protocol as defined in
39 * ISO/IEC Final DIS 15802-3 (IEEE P802.1D/D17), May 25, 1998.
40 * (In English: IEEE 802.1D, Draft 17, 1998)
43 #include <sys/cdefs.h>
45 #include <sys/param.h>
46 #include <sys/systm.h>
48 #include <sys/socket.h>
49 #include <sys/sockio.h>
50 #include <sys/kernel.h>
51 #include <sys/callout.h>
54 #include <sys/thread.h>
55 #include <sys/thread2.h>
56 #include <sys/msgport2.h>
59 #include <net/if_dl.h>
60 #include <net/if_types.h>
61 #include <net/if_llc.h>
62 #include <net/if_media.h>
64 #include <netinet/in.h>
65 #include <netinet/in_systm.h>
66 #include <netinet/in_var.h>
67 #include <netinet/if_ether.h>
68 #include <net/bridge/if_bridgevar.h>
70 /* BPDU message types */
71 #define BSTP_MSGTYPE_CFG 0x00 /* Configuration */
72 #define BSTP_MSGTYPE_TCN 0x80 /* Topology chg notification */
75 #define BSTP_FLAG_TC 0x01 /* Topology change */
76 #define BSTP_FLAG_TCA 0x80 /* Topology change ack */
78 #define BSTP_MESSAGE_AGE_INCR (1 * 256) /* in 256ths of a second */
79 #define BSTP_TICK_VAL (1 * 256) /* in 256ths of a second */
82 * Because BPDU's do not make nicely aligned structures, two different
83 * declarations are used: bstp_?bpdu (wire representation, packed) and
84 * bstp_*_unit (internal, nicely aligned version).
87 /* configuration bridge protocol data unit */
89 uint8_t cbu_dsap
; /* LLC: destination sap */
90 uint8_t cbu_ssap
; /* LLC: source sap */
91 uint8_t cbu_ctl
; /* LLC: control */
92 uint16_t cbu_protoid
; /* protocol id */
93 uint8_t cbu_protover
; /* protocol version */
94 uint8_t cbu_bpdutype
; /* message type */
95 uint8_t cbu_flags
; /* flags (below) */
98 uint16_t cbu_rootpri
; /* root priority */
99 uint8_t cbu_rootaddr
[6]; /* root address */
101 uint32_t cbu_rootpathcost
; /* root path cost */
104 uint16_t cbu_bridgepri
; /* bridge priority */
105 uint8_t cbu_bridgeaddr
[6]; /* bridge address */
107 uint16_t cbu_portid
; /* port id */
108 uint16_t cbu_messageage
; /* current message age */
109 uint16_t cbu_maxage
; /* maximum age */
110 uint16_t cbu_hellotime
; /* hello time */
111 uint16_t cbu_forwarddelay
; /* forwarding delay */
112 } __attribute__((__packed__
));
114 /* topology change notification bridge protocol data unit */
116 uint8_t tbu_dsap
; /* LLC: destination sap */
117 uint8_t tbu_ssap
; /* LLC: source sap */
118 uint8_t tbu_ctl
; /* LLC: control */
119 uint16_t tbu_protoid
; /* protocol id */
120 uint8_t tbu_protover
; /* protocol version */
121 uint8_t tbu_bpdutype
; /* message type */
122 } __attribute__((__packed__
));
124 const uint8_t bstp_etheraddr
[] = { 0x01, 0x80, 0xc2, 0x00, 0x00, 0x00 };
126 static void bstp_initialize_port(struct bridge_softc
*,
127 struct bridge_iflist
*);
128 static void bstp_ifupdstatus(struct bridge_softc
*, struct bridge_iflist
*);
129 static void bstp_enable_port(struct bridge_softc
*, struct bridge_iflist
*);
130 static void bstp_disable_port(struct bridge_softc
*,
131 struct bridge_iflist
*);
133 static void bstp_enable_change_detection(struct bridge_iflist
*);
134 static void bstp_disable_change_detection(struct bridge_iflist
*);
136 static int bstp_root_bridge(struct bridge_softc
*sc
);
137 static int bstp_supersedes_port_info(struct bridge_softc
*,
138 struct bridge_iflist
*, struct bstp_config_unit
*);
139 static int bstp_designated_port(struct bridge_softc
*,
140 struct bridge_iflist
*);
141 static int bstp_designated_for_some_port(struct bridge_softc
*);
142 static void bstp_transmit_config(struct bridge_softc
*,
143 struct bridge_iflist
*);
144 static void bstp_transmit_tcn(struct bridge_softc
*);
145 static void bstp_received_config_bpdu(struct bridge_softc
*,
146 struct bridge_iflist
*, struct bstp_config_unit
*);
147 static void bstp_received_tcn_bpdu(struct bridge_softc
*,
148 struct bridge_iflist
*, struct bstp_tcn_unit
*);
149 static void bstp_record_config_information(struct bridge_softc
*,
150 struct bridge_iflist
*, struct bstp_config_unit
*);
151 static void bstp_record_config_timeout_values(struct bridge_softc
*,
152 struct bstp_config_unit
*);
153 static void bstp_config_bpdu_generation(struct bridge_softc
*);
154 static void bstp_send_config_bpdu(struct bridge_softc
*,
155 struct bridge_iflist
*, struct bstp_config_unit
*);
156 static void bstp_configuration_update(struct bridge_softc
*);
157 static void bstp_root_selection(struct bridge_softc
*);
158 static void bstp_designated_port_selection(struct bridge_softc
*);
159 static void bstp_become_designated_port(struct bridge_softc
*,
160 struct bridge_iflist
*);
161 static void bstp_port_state_selection(struct bridge_softc
*);
162 static void bstp_make_forwarding(struct bridge_softc
*,
163 struct bridge_iflist
*);
164 static void bstp_make_blocking(struct bridge_softc
*,
165 struct bridge_iflist
*);
166 static void bstp_set_port_state(struct bridge_iflist
*, uint8_t);
168 static void bstp_set_bridge_priority(struct bridge_softc
*, uint64_t);
169 static void bstp_set_port_priority(struct bridge_softc
*,
170 struct bridge_iflist
*, uint16_t);
171 static void bstp_set_path_cost(struct bridge_softc
*,
172 struct bridge_iflist
*, uint32_t);
174 static void bstp_topology_change_detection(struct bridge_softc
*);
175 static void bstp_topology_change_acknowledged(struct bridge_softc
*);
176 static void bstp_acknowledge_topology_change(struct bridge_softc
*,
177 struct bridge_iflist
*);
179 static void bstp_tick(void *);
180 static void bstp_timer_start(struct bridge_timer
*, uint16_t);
181 static void bstp_timer_stop(struct bridge_timer
*);
182 static int bstp_timer_expired(struct bridge_timer
*, uint16_t);
184 static void bstp_hold_timer_expiry(struct bridge_softc
*,
185 struct bridge_iflist
*);
186 static void bstp_message_age_timer_expiry(struct bridge_softc
*,
187 struct bridge_iflist
*);
188 static void bstp_forward_delay_timer_expiry(struct bridge_softc
*,
189 struct bridge_iflist
*);
190 static void bstp_topology_change_timer_expiry(struct bridge_softc
*);
191 static void bstp_tcn_timer_expiry(struct bridge_softc
*);
192 static void bstp_hello_timer_expiry(struct bridge_softc
*);
193 static int bstp_addr_cmp(const uint8_t *, const uint8_t *);
196 bstp_transmit_config(struct bridge_softc
*sc
, struct bridge_iflist
*bif
)
198 if (bif
->bif_hold_timer
.active
) {
199 bif
->bif_config_pending
= 1;
203 bif
->bif_config_bpdu
.cu_message_type
= BSTP_MSGTYPE_CFG
;
204 bif
->bif_config_bpdu
.cu_rootid
= sc
->sc_designated_root
;
205 bif
->bif_config_bpdu
.cu_root_path_cost
= sc
->sc_root_path_cost
;
206 bif
->bif_config_bpdu
.cu_bridge_id
= sc
->sc_bridge_id
;
207 bif
->bif_config_bpdu
.cu_port_id
= bif
->bif_port_id
;
209 if (bstp_root_bridge(sc
)) {
210 bif
->bif_config_bpdu
.cu_message_age
= 0;
212 bif
->bif_config_bpdu
.cu_message_age
=
213 sc
->sc_root_port
->bifi_message_age_timer
.value
+
214 BSTP_MESSAGE_AGE_INCR
;
217 bif
->bif_config_bpdu
.cu_max_age
= sc
->sc_max_age
;
218 bif
->bif_config_bpdu
.cu_hello_time
= sc
->sc_hello_time
;
219 bif
->bif_config_bpdu
.cu_forward_delay
= sc
->sc_forward_delay
;
220 bif
->bif_config_bpdu
.cu_topology_change_acknowledgment
221 = bif
->bif_topology_change_acknowledge
;
222 bif
->bif_config_bpdu
.cu_topology_change
= sc
->sc_topology_change
;
224 if (bif
->bif_config_bpdu
.cu_message_age
< sc
->sc_max_age
) {
225 bif
->bif_topology_change_acknowledge
= 0;
226 bif
->bif_config_pending
= 0;
227 bstp_send_config_bpdu(sc
, bif
, &bif
->bif_config_bpdu
);
228 bstp_timer_start(&bif
->bif_hold_timer
, 0);
233 bstp_send_config_bpdu(struct bridge_softc
*sc
, struct bridge_iflist
*bif
,
234 struct bstp_config_unit
*cu
)
238 struct ether_header
*eh
;
239 struct bstp_cbpdu bpdu
;
243 if ((ifp
->if_flags
& IFF_RUNNING
) == 0)
246 MGETHDR(m
, MB_DONTWAIT
, MT_DATA
);
250 eh
= mtod(m
, struct ether_header
*);
252 m
->m_pkthdr
.rcvif
= ifp
;
253 m
->m_pkthdr
.len
= sizeof(*eh
) + sizeof(bpdu
);
254 m
->m_len
= m
->m_pkthdr
.len
;
256 bpdu
.cbu_ssap
= bpdu
.cbu_dsap
= LLC_8021D_LSAP
;
257 bpdu
.cbu_ctl
= LLC_UI
;
258 bpdu
.cbu_protoid
= htons(0);
259 bpdu
.cbu_protover
= 0;
260 bpdu
.cbu_bpdutype
= cu
->cu_message_type
;
261 bpdu
.cbu_flags
= (cu
->cu_topology_change
? BSTP_FLAG_TC
: 0) |
262 (cu
->cu_topology_change_acknowledgment
? BSTP_FLAG_TCA
: 0);
264 bpdu
.cbu_rootpri
= htons(cu
->cu_rootid
>> 48);
265 bpdu
.cbu_rootaddr
[0] = cu
->cu_rootid
>> 40;
266 bpdu
.cbu_rootaddr
[1] = cu
->cu_rootid
>> 32;
267 bpdu
.cbu_rootaddr
[2] = cu
->cu_rootid
>> 24;
268 bpdu
.cbu_rootaddr
[3] = cu
->cu_rootid
>> 16;
269 bpdu
.cbu_rootaddr
[4] = cu
->cu_rootid
>> 8;
270 bpdu
.cbu_rootaddr
[5] = cu
->cu_rootid
>> 0;
272 bpdu
.cbu_rootpathcost
= htonl(cu
->cu_root_path_cost
);
274 bpdu
.cbu_bridgepri
= htons(cu
->cu_bridge_id
>> 48);
275 bpdu
.cbu_bridgeaddr
[0] = cu
->cu_bridge_id
>> 40;
276 bpdu
.cbu_bridgeaddr
[1] = cu
->cu_bridge_id
>> 32;
277 bpdu
.cbu_bridgeaddr
[2] = cu
->cu_bridge_id
>> 24;
278 bpdu
.cbu_bridgeaddr
[3] = cu
->cu_bridge_id
>> 16;
279 bpdu
.cbu_bridgeaddr
[4] = cu
->cu_bridge_id
>> 8;
280 bpdu
.cbu_bridgeaddr
[5] = cu
->cu_bridge_id
>> 0;
282 bpdu
.cbu_portid
= htons(cu
->cu_port_id
);
283 bpdu
.cbu_messageage
= htons(cu
->cu_message_age
);
284 bpdu
.cbu_maxage
= htons(cu
->cu_max_age
);
285 bpdu
.cbu_hellotime
= htons(cu
->cu_hello_time
);
286 bpdu
.cbu_forwarddelay
= htons(cu
->cu_forward_delay
);
288 memcpy(eh
->ether_shost
, IF_LLADDR(ifp
), ETHER_ADDR_LEN
);
289 memcpy(eh
->ether_dhost
, bstp_etheraddr
, ETHER_ADDR_LEN
);
290 eh
->ether_type
= htons(sizeof(bpdu
));
292 memcpy(mtod(m
, caddr_t
) + sizeof(*eh
), &bpdu
, sizeof(bpdu
));
294 bridge_enqueue(ifp
, m
);
298 bstp_root_bridge(struct bridge_softc
*sc
)
300 return (sc
->sc_designated_root
== sc
->sc_bridge_id
);
304 bstp_supersedes_port_info(struct bridge_softc
*sc
, struct bridge_iflist
*bif
,
305 struct bstp_config_unit
*cu
)
307 if (cu
->cu_rootid
< bif
->bif_designated_root
)
309 if (cu
->cu_rootid
> bif
->bif_designated_root
)
312 if (cu
->cu_root_path_cost
< bif
->bif_designated_cost
)
314 if (cu
->cu_root_path_cost
> bif
->bif_designated_cost
)
317 if (cu
->cu_bridge_id
< bif
->bif_designated_bridge
)
319 if (cu
->cu_bridge_id
> bif
->bif_designated_bridge
)
322 if (sc
->sc_bridge_id
!= cu
->cu_bridge_id
)
324 if (cu
->cu_port_id
<= bif
->bif_designated_port
)
330 bstp_record_config_information(struct bridge_softc
*sc
,
331 struct bridge_iflist
*bif
, struct bstp_config_unit
*cu
)
333 bif
->bif_designated_root
= cu
->cu_rootid
;
334 bif
->bif_designated_cost
= cu
->cu_root_path_cost
;
335 bif
->bif_designated_bridge
= cu
->cu_bridge_id
;
336 bif
->bif_designated_port
= cu
->cu_port_id
;
337 bstp_timer_start(&bif
->bif_message_age_timer
, cu
->cu_message_age
);
341 bstp_record_config_timeout_values(struct bridge_softc
*sc
,
342 struct bstp_config_unit
*config
)
344 sc
->sc_max_age
= config
->cu_max_age
;
345 sc
->sc_hello_time
= config
->cu_hello_time
;
346 sc
->sc_forward_delay
= config
->cu_forward_delay
;
347 sc
->sc_topology_change
= config
->cu_topology_change
;
351 bstp_config_bpdu_generation(struct bridge_softc
*sc
)
353 struct bridge_iflist
*bif
, *nbif
;
355 LIST_FOREACH_MUTABLE(bif
, &sc
->sc_iflists
[mycpuid
], bif_next
, nbif
) {
356 if ((bif
->bif_flags
& IFBIF_STP
) == 0)
358 if (bstp_designated_port(sc
, bif
) &&
359 (bif
->bif_state
!= BSTP_IFSTATE_DISABLED
))
360 bstp_transmit_config(sc
, bif
);
362 if (nbif
!= NULL
&& !nbif
->bif_onlist
) {
363 KKASSERT(bif
->bif_onlist
);
364 nbif
= LIST_NEXT(bif
, bif_next
);
370 bstp_designated_port(struct bridge_softc
*sc
, struct bridge_iflist
*bif
)
372 return ((bif
->bif_designated_bridge
== sc
->sc_bridge_id
)
373 && (bif
->bif_designated_port
== bif
->bif_port_id
));
377 bstp_transmit_tcn(struct bridge_softc
*sc
)
379 struct bstp_tbpdu bpdu
;
380 struct ifnet
*ifp
= sc
->sc_root_port
->bifi_ifp
;
381 struct ether_header
*eh
;
384 if ((ifp
->if_flags
& IFF_RUNNING
) == 0)
387 MGETHDR(m
, MB_DONTWAIT
, MT_DATA
);
391 m
->m_pkthdr
.rcvif
= ifp
;
392 m
->m_pkthdr
.len
= sizeof(*eh
) + sizeof(bpdu
);
393 m
->m_len
= m
->m_pkthdr
.len
;
395 eh
= mtod(m
, struct ether_header
*);
397 memcpy(eh
->ether_shost
, IF_LLADDR(ifp
), ETHER_ADDR_LEN
);
398 memcpy(eh
->ether_dhost
, bstp_etheraddr
, ETHER_ADDR_LEN
);
399 eh
->ether_type
= htons(sizeof(bpdu
));
401 bpdu
.tbu_ssap
= bpdu
.tbu_dsap
= LLC_8021D_LSAP
;
402 bpdu
.tbu_ctl
= LLC_UI
;
403 bpdu
.tbu_protoid
= 0;
404 bpdu
.tbu_protover
= 0;
405 bpdu
.tbu_bpdutype
= BSTP_MSGTYPE_TCN
;
407 memcpy(mtod(m
, caddr_t
) + sizeof(*eh
), &bpdu
, sizeof(bpdu
));
409 bridge_enqueue(ifp
, m
);
413 bstp_configuration_update(struct bridge_softc
*sc
)
415 bstp_root_selection(sc
);
416 bstp_designated_port_selection(sc
);
420 bstp_root_selection(struct bridge_softc
*sc
)
422 struct bridge_iflist
*root_port
= NULL
, *bif
;
424 LIST_FOREACH(bif
, &sc
->sc_iflists
[mycpuid
], bif_next
) {
425 if ((bif
->bif_flags
& IFBIF_STP
) == 0)
427 if (bstp_designated_port(sc
, bif
))
429 if (bif
->bif_state
== BSTP_IFSTATE_DISABLED
)
431 if (bif
->bif_designated_root
>= sc
->sc_bridge_id
)
433 if (root_port
== NULL
)
436 if (bif
->bif_designated_root
< root_port
->bif_designated_root
)
438 if (bif
->bif_designated_root
> root_port
->bif_designated_root
)
441 if ((bif
->bif_designated_cost
+ bif
->bif_path_cost
) <
442 (root_port
->bif_designated_cost
+ root_port
->bif_path_cost
))
444 if ((bif
->bif_designated_cost
+ bif
->bif_path_cost
) >
445 (root_port
->bif_designated_cost
+ root_port
->bif_path_cost
))
448 if (bif
->bif_designated_bridge
<
449 root_port
->bif_designated_bridge
)
451 if (bif
->bif_designated_bridge
>
452 root_port
->bif_designated_bridge
)
455 if (bif
->bif_designated_port
< root_port
->bif_designated_port
)
457 if (bif
->bif_designated_port
> root_port
->bif_designated_port
)
460 if (bif
->bif_port_id
>= root_port
->bif_port_id
)
466 if (root_port
== NULL
) {
467 sc
->sc_root_port
= NULL
;
468 sc
->sc_designated_root
= sc
->sc_bridge_id
;
469 sc
->sc_root_path_cost
= 0;
471 sc
->sc_root_port
= root_port
->bif_info
;
472 sc
->sc_designated_root
= root_port
->bif_designated_root
;
473 sc
->sc_root_path_cost
= root_port
->bif_designated_cost
+
474 root_port
->bif_path_cost
;
479 bstp_designated_port_selection(struct bridge_softc
*sc
)
481 struct bridge_iflist
*bif
;
483 LIST_FOREACH(bif
, &sc
->sc_iflists
[mycpuid
], bif_next
) {
484 if ((bif
->bif_flags
& IFBIF_STP
) == 0)
486 if (bstp_designated_port(sc
, bif
))
488 if (bif
->bif_designated_root
!= sc
->sc_designated_root
)
491 if (sc
->sc_root_path_cost
< bif
->bif_designated_cost
)
493 if (sc
->sc_root_path_cost
> bif
->bif_designated_cost
)
496 if (sc
->sc_bridge_id
< bif
->bif_designated_bridge
)
498 if (sc
->sc_bridge_id
> bif
->bif_designated_bridge
)
501 if (bif
->bif_port_id
> bif
->bif_designated_port
)
504 bstp_become_designated_port(sc
, bif
);
509 bstp_become_designated_port(struct bridge_softc
*sc
, struct bridge_iflist
*bif
)
511 bif
->bif_designated_root
= sc
->sc_designated_root
;
512 bif
->bif_designated_cost
= sc
->sc_root_path_cost
;
513 bif
->bif_designated_bridge
= sc
->sc_bridge_id
;
514 bif
->bif_designated_port
= bif
->bif_port_id
;
518 bstp_port_state_selection(struct bridge_softc
*sc
)
520 struct bridge_iflist
*bif
, *nbif
;
522 LIST_FOREACH_MUTABLE(bif
, &sc
->sc_iflists
[mycpuid
], bif_next
, nbif
) {
523 if ((bif
->bif_flags
& IFBIF_STP
) == 0)
525 if (bif
->bif_info
== sc
->sc_root_port
) {
526 bif
->bif_config_pending
= 0;
527 bif
->bif_topology_change_acknowledge
= 0;
528 bstp_make_forwarding(sc
, bif
);
529 } else if (bstp_designated_port(sc
, bif
)) {
530 bstp_timer_stop(&bif
->bif_message_age_timer
);
531 bstp_make_forwarding(sc
, bif
);
533 bif
->bif_config_pending
= 0;
534 bif
->bif_topology_change_acknowledge
= 0;
535 bstp_make_blocking(sc
, bif
);
538 if (nbif
!= NULL
&& !nbif
->bif_onlist
) {
539 KKASSERT(bif
->bif_onlist
);
540 nbif
= LIST_NEXT(bif
, bif_next
);
546 bstp_make_forwarding(struct bridge_softc
*sc
, struct bridge_iflist
*bif
)
548 if (bif
->bif_state
== BSTP_IFSTATE_BLOCKING
) {
549 bstp_set_port_state(bif
, BSTP_IFSTATE_LISTENING
);
550 bstp_timer_start(&bif
->bif_forward_delay_timer
, 0);
555 bstp_make_blocking(struct bridge_softc
*sc
, struct bridge_iflist
*bif
)
557 if ((bif
->bif_state
!= BSTP_IFSTATE_DISABLED
) &&
558 (bif
->bif_state
!= BSTP_IFSTATE_BLOCKING
)) {
559 if ((bif
->bif_state
== BSTP_IFSTATE_FORWARDING
) ||
560 (bif
->bif_state
== BSTP_IFSTATE_LEARNING
)) {
561 if (bif
->bif_change_detection_enabled
) {
562 bstp_topology_change_detection(sc
);
565 bstp_set_port_state(bif
, BSTP_IFSTATE_BLOCKING
);
566 bridge_rtdelete(sc
, bif
->bif_ifp
, IFBF_FLUSHDYN
);
567 bstp_timer_stop(&bif
->bif_forward_delay_timer
);
572 bstp_set_port_state(struct bridge_iflist
*bif
, uint8_t state
)
574 bif
->bif_state
= state
;
578 bstp_topology_change_detection(struct bridge_softc
*sc
)
580 if (bstp_root_bridge(sc
)) {
581 sc
->sc_topology_change
= 1;
582 bstp_timer_start(&sc
->sc_topology_change_timer
, 0);
583 } else if (!sc
->sc_topology_change_detected
) {
584 bstp_transmit_tcn(sc
);
585 bstp_timer_start(&sc
->sc_tcn_timer
, 0);
587 sc
->sc_topology_change_detected
= 1;
591 bstp_topology_change_acknowledged(struct bridge_softc
*sc
)
593 sc
->sc_topology_change_detected
= 0;
594 bstp_timer_stop(&sc
->sc_tcn_timer
);
598 bstp_acknowledge_topology_change(struct bridge_softc
*sc
,
599 struct bridge_iflist
*bif
)
601 bif
->bif_topology_change_acknowledge
= 1;
602 bstp_transmit_config(sc
, bif
);
606 bstp_input(struct bridge_softc
*sc
, struct bridge_iflist
*bif
, struct mbuf
*m
)
608 struct ether_header
*eh
;
609 struct bstp_tbpdu tpdu
;
610 struct bstp_cbpdu cpdu
;
611 struct bstp_config_unit cu
;
612 struct bstp_tcn_unit tu
;
615 if ((bif
->bif_flags
& IFBIF_STP
) == 0)
618 eh
= mtod(m
, struct ether_header
*);
620 len
= ntohs(eh
->ether_type
);
621 if (len
< sizeof(tpdu
))
624 m_adj(m
, ETHER_HDR_LEN
);
626 if (m
->m_pkthdr
.len
> len
)
627 m_adj(m
, len
- m
->m_pkthdr
.len
);
628 if (m
->m_len
< sizeof(tpdu
) &&
629 (m
= m_pullup(m
, sizeof(tpdu
))) == NULL
)
632 memcpy(&tpdu
, mtod(m
, caddr_t
), sizeof(tpdu
));
634 if (tpdu
.tbu_dsap
!= LLC_8021D_LSAP
||
635 tpdu
.tbu_ssap
!= LLC_8021D_LSAP
||
636 tpdu
.tbu_ctl
!= LLC_UI
)
638 if (tpdu
.tbu_protoid
!= 0 || tpdu
.tbu_protover
!= 0)
641 switch (tpdu
.tbu_bpdutype
) {
642 case BSTP_MSGTYPE_TCN
:
643 tu
.tu_message_type
= tpdu
.tbu_bpdutype
;
644 bstp_received_tcn_bpdu(sc
, bif
, &tu
);
646 case BSTP_MSGTYPE_CFG
:
647 if (m
->m_len
< sizeof(cpdu
) &&
648 (m
= m_pullup(m
, sizeof(cpdu
))) == NULL
)
650 memcpy(&cpdu
, mtod(m
, caddr_t
), sizeof(cpdu
));
653 (((uint64_t)ntohs(cpdu
.cbu_rootpri
)) << 48) |
654 (((uint64_t)cpdu
.cbu_rootaddr
[0]) << 40) |
655 (((uint64_t)cpdu
.cbu_rootaddr
[1]) << 32) |
656 (((uint64_t)cpdu
.cbu_rootaddr
[2]) << 24) |
657 (((uint64_t)cpdu
.cbu_rootaddr
[3]) << 16) |
658 (((uint64_t)cpdu
.cbu_rootaddr
[4]) << 8) |
659 (((uint64_t)cpdu
.cbu_rootaddr
[5]) << 0);
662 (((uint64_t)ntohs(cpdu
.cbu_bridgepri
)) << 48) |
663 (((uint64_t)cpdu
.cbu_bridgeaddr
[0]) << 40) |
664 (((uint64_t)cpdu
.cbu_bridgeaddr
[1]) << 32) |
665 (((uint64_t)cpdu
.cbu_bridgeaddr
[2]) << 24) |
666 (((uint64_t)cpdu
.cbu_bridgeaddr
[3]) << 16) |
667 (((uint64_t)cpdu
.cbu_bridgeaddr
[4]) << 8) |
668 (((uint64_t)cpdu
.cbu_bridgeaddr
[5]) << 0);
670 cu
.cu_root_path_cost
= ntohl(cpdu
.cbu_rootpathcost
);
671 cu
.cu_message_age
= ntohs(cpdu
.cbu_messageage
);
672 cu
.cu_max_age
= ntohs(cpdu
.cbu_maxage
);
673 cu
.cu_hello_time
= ntohs(cpdu
.cbu_hellotime
);
674 cu
.cu_forward_delay
= ntohs(cpdu
.cbu_forwarddelay
);
675 cu
.cu_port_id
= ntohs(cpdu
.cbu_portid
);
676 cu
.cu_message_type
= cpdu
.cbu_bpdutype
;
677 cu
.cu_topology_change_acknowledgment
=
678 (cpdu
.cbu_flags
& BSTP_FLAG_TCA
) ? 1 : 0;
679 cu
.cu_topology_change
=
680 (cpdu
.cbu_flags
& BSTP_FLAG_TC
) ? 1 : 0;
681 bstp_received_config_bpdu(sc
, bif
, &cu
);
692 bstp_received_config_bpdu(struct bridge_softc
*sc
, struct bridge_iflist
*bif
,
693 struct bstp_config_unit
*cu
)
697 root
= bstp_root_bridge(sc
);
699 if (bif
->bif_state
!= BSTP_IFSTATE_DISABLED
) {
700 if (bstp_supersedes_port_info(sc
, bif
, cu
)) {
701 bstp_record_config_information(sc
, bif
, cu
);
702 bstp_configuration_update(sc
);
703 bstp_port_state_selection(sc
);
705 if ((bstp_root_bridge(sc
) == 0) && root
) {
706 bstp_timer_stop(&sc
->sc_hello_timer
);
708 if (sc
->sc_topology_change_detected
) {
710 &sc
->sc_topology_change_timer
);
711 bstp_transmit_tcn(sc
);
712 bstp_timer_start(&sc
->sc_tcn_timer
, 0);
716 if (bif
->bif_info
== sc
->sc_root_port
) {
717 bstp_record_config_timeout_values(sc
, cu
);
718 bstp_config_bpdu_generation(sc
);
720 if (cu
->cu_topology_change_acknowledgment
)
721 bstp_topology_change_acknowledged(sc
);
723 } else if (bstp_designated_port(sc
, bif
))
724 bstp_transmit_config(sc
, bif
);
729 bstp_received_tcn_bpdu(struct bridge_softc
*sc
, struct bridge_iflist
*bif
,
730 struct bstp_tcn_unit
*tcn
)
732 if (bif
->bif_state
!= BSTP_IFSTATE_DISABLED
&&
733 bstp_designated_port(sc
, bif
)) {
734 bstp_topology_change_detection(sc
);
735 bstp_acknowledge_topology_change(sc
, bif
);
740 bstp_hello_timer_expiry(struct bridge_softc
*sc
)
742 bstp_config_bpdu_generation(sc
);
743 bstp_timer_start(&sc
->sc_hello_timer
, 0);
747 bstp_message_age_timer_expiry(struct bridge_softc
*sc
,
748 struct bridge_iflist
*bif
)
752 root
= bstp_root_bridge(sc
);
753 bstp_become_designated_port(sc
, bif
);
754 bstp_configuration_update(sc
);
755 bstp_port_state_selection(sc
);
757 if ((bstp_root_bridge(sc
)) && (root
== 0)) {
758 sc
->sc_max_age
= sc
->sc_bridge_max_age
;
759 sc
->sc_hello_time
= sc
->sc_bridge_hello_time
;
760 sc
->sc_forward_delay
= sc
->sc_bridge_forward_delay
;
762 bstp_topology_change_detection(sc
);
763 bstp_timer_stop(&sc
->sc_tcn_timer
);
764 bstp_config_bpdu_generation(sc
);
765 bstp_timer_start(&sc
->sc_hello_timer
, 0);
770 bstp_forward_delay_timer_expiry(struct bridge_softc
*sc
,
771 struct bridge_iflist
*bif
)
773 if (bif
->bif_state
== BSTP_IFSTATE_LISTENING
) {
774 bstp_set_port_state(bif
, BSTP_IFSTATE_LEARNING
);
775 bstp_timer_start(&bif
->bif_forward_delay_timer
, 0);
776 } else if (bif
->bif_state
== BSTP_IFSTATE_LEARNING
) {
777 bstp_set_port_state(bif
, BSTP_IFSTATE_FORWARDING
);
778 if (bstp_designated_for_some_port(sc
) &&
779 bif
->bif_change_detection_enabled
)
780 bstp_topology_change_detection(sc
);
785 bstp_designated_for_some_port(struct bridge_softc
*sc
)
788 struct bridge_iflist
*bif
;
790 LIST_FOREACH(bif
, &sc
->sc_iflists
[mycpuid
], bif_next
) {
791 if ((bif
->bif_flags
& IFBIF_STP
) == 0)
793 if (bif
->bif_designated_bridge
== sc
->sc_bridge_id
)
800 bstp_tcn_timer_expiry(struct bridge_softc
*sc
)
802 bstp_transmit_tcn(sc
);
803 bstp_timer_start(&sc
->sc_tcn_timer
, 0);
807 bstp_topology_change_timer_expiry(struct bridge_softc
*sc
)
809 sc
->sc_topology_change_detected
= 0;
810 sc
->sc_topology_change
= 0;
814 bstp_hold_timer_expiry(struct bridge_softc
*sc
, struct bridge_iflist
*bif
)
816 if (bif
->bif_config_pending
)
817 bstp_transmit_config(sc
, bif
);
821 bstp_addr_cmp(const uint8_t *a
, const uint8_t *b
)
825 for (i
= 0, d
= 0; i
< ETHER_ADDR_LEN
&& d
== 0; i
++) {
826 d
= ((int)a
[i
]) - ((int)b
[i
]);
833 bstp_initialization(struct bridge_softc
*sc
)
835 struct bridge_iflist
*bif
, *mif
, *nbif
;
838 KKASSERT(&curthread
->td_msgport
== BRIDGE_CFGPORT
);
841 LIST_FOREACH(bif
, &sc
->sc_iflists
[mycpuid
], bif_next
) {
842 if ((bif
->bif_flags
& IFBIF_STP
) == 0)
844 if (bif
->bif_ifp
->if_type
!= IFT_ETHER
)
846 bif
->bif_port_id
= (bif
->bif_priority
<< 8) |
847 (bif
->bif_ifp
->if_index
& 0xff);
853 if (bstp_addr_cmp(IF_LLADDR(bif
->bif_ifp
),
854 IF_LLADDR(mif
->bif_ifp
)) < 0) {
864 e_addr
= IF_LLADDR(mif
->bif_ifp
);
866 (((uint64_t)sc
->sc_bridge_priority
) << 48) |
867 (((uint64_t)e_addr
[0]) << 40) |
868 (((uint64_t)e_addr
[1]) << 32) |
869 (((uint64_t)e_addr
[2]) << 24) |
870 (((uint64_t)e_addr
[3]) << 16) |
871 (((uint64_t)e_addr
[4]) << 8) |
872 (((uint64_t)e_addr
[5]));
874 sc
->sc_designated_root
= sc
->sc_bridge_id
;
875 sc
->sc_root_path_cost
= 0;
876 sc
->sc_root_port
= NULL
;
878 sc
->sc_max_age
= sc
->sc_bridge_max_age
;
879 sc
->sc_hello_time
= sc
->sc_bridge_hello_time
;
880 sc
->sc_forward_delay
= sc
->sc_bridge_forward_delay
;
881 sc
->sc_topology_change_detected
= 0;
882 sc
->sc_topology_change
= 0;
883 bstp_timer_stop(&sc
->sc_tcn_timer
);
884 bstp_timer_stop(&sc
->sc_topology_change_timer
);
886 if (callout_pending(&sc
->sc_bstpcallout
) == 0)
887 callout_reset(&sc
->sc_bstpcallout
, hz
,
890 LIST_FOREACH_MUTABLE(bif
, &sc
->sc_iflists
[mycpuid
], bif_next
, nbif
) {
891 if (bif
->bif_flags
& IFBIF_STP
)
892 bstp_ifupdstatus(sc
, bif
);
894 bstp_disable_port(sc
, bif
);
896 if (nbif
!= NULL
&& !nbif
->bif_onlist
) {
897 KKASSERT(bif
->bif_onlist
);
898 nbif
= LIST_NEXT(bif
, bif_next
);
902 bstp_port_state_selection(sc
);
903 bstp_config_bpdu_generation(sc
);
904 bstp_timer_start(&sc
->sc_hello_timer
, 0);
908 bstp_stop(struct bridge_softc
*sc
)
910 struct bridge_iflist
*bif
;
911 struct lwkt_msg
*lmsg
;
913 KKASSERT(&curthread
->td_msgport
== BRIDGE_CFGPORT
);
915 LIST_FOREACH(bif
, &sc
->sc_iflists
[mycpuid
], bif_next
) {
916 bstp_set_port_state(bif
, BSTP_IFSTATE_DISABLED
);
917 bstp_timer_stop(&bif
->bif_hold_timer
);
918 bstp_timer_stop(&bif
->bif_message_age_timer
);
919 bstp_timer_stop(&bif
->bif_forward_delay_timer
);
922 callout_stop(&sc
->sc_bstpcallout
);
924 bstp_timer_stop(&sc
->sc_topology_change_timer
);
925 bstp_timer_stop(&sc
->sc_tcn_timer
);
926 bstp_timer_stop(&sc
->sc_hello_timer
);
929 lmsg
= &sc
->sc_bstptimemsg
.nm_lmsg
;
930 if ((lmsg
->ms_flags
& MSGF_DONE
) == 0) {
931 /* Pending to be processed; drop it */
938 bstp_initialize_port(struct bridge_softc
*sc
, struct bridge_iflist
*bif
)
940 bstp_become_designated_port(sc
, bif
);
941 bstp_set_port_state(bif
, BSTP_IFSTATE_BLOCKING
);
942 bif
->bif_topology_change_acknowledge
= 0;
943 bif
->bif_config_pending
= 0;
944 bif
->bif_change_detection_enabled
= 1;
945 bstp_timer_stop(&bif
->bif_message_age_timer
);
946 bstp_timer_stop(&bif
->bif_forward_delay_timer
);
947 bstp_timer_stop(&bif
->bif_hold_timer
);
951 bstp_enable_port(struct bridge_softc
*sc
, struct bridge_iflist
*bif
)
953 bstp_initialize_port(sc
, bif
);
954 bstp_port_state_selection(sc
);
958 bstp_disable_port(struct bridge_softc
*sc
, struct bridge_iflist
*bif
)
962 root
= bstp_root_bridge(sc
);
963 bstp_become_designated_port(sc
, bif
);
964 bstp_set_port_state(bif
, BSTP_IFSTATE_DISABLED
);
965 bif
->bif_topology_change_acknowledge
= 0;
966 bif
->bif_config_pending
= 0;
967 bstp_timer_stop(&bif
->bif_message_age_timer
);
968 bstp_timer_stop(&bif
->bif_forward_delay_timer
);
969 bstp_configuration_update(sc
);
970 bstp_port_state_selection(sc
);
971 bridge_rtdelete(sc
, bif
->bif_ifp
, IFBF_FLUSHDYN
);
973 if (bstp_root_bridge(sc
) && (root
== 0)) {
974 sc
->sc_max_age
= sc
->sc_bridge_max_age
;
975 sc
->sc_hello_time
= sc
->sc_bridge_hello_time
;
976 sc
->sc_forward_delay
= sc
->sc_bridge_forward_delay
;
978 bstp_topology_change_detection(sc
);
979 bstp_timer_stop(&sc
->sc_tcn_timer
);
980 bstp_config_bpdu_generation(sc
);
981 bstp_timer_start(&sc
->sc_hello_timer
, 0);
987 bstp_set_bridge_priority(struct bridge_softc
*sc
, uint64_t new_bridge_id
)
989 struct bridge_iflist
*bif
;
992 root
= bstp_root_bridge(sc
);
994 LIST_FOREACH(bif
, &sc
->sc_iflists
[mycpuid
], bif_next
) {
995 if ((bif
->bif_flags
& IFBIF_STP
) == 0)
997 if (bstp_designated_port(sc
, bif
))
998 bif
->bif_designated_bridge
= new_bridge_id
;
1001 sc
->sc_bridge_id
= new_bridge_id
;
1003 bstp_configuration_update(sc
);
1004 bstp_port_state_selection(sc
);
1006 if (bstp_root_bridge(sc
) && (root
== 0)) {
1007 sc
->sc_max_age
= sc
->sc_bridge_max_age
;
1008 sc
->sc_hello_time
= sc
->sc_bridge_hello_time
;
1009 sc
->sc_forward_delay
= sc
->sc_bridge_forward_delay
;
1011 bstp_topology_change_detection(sc
);
1012 bstp_timer_stop(&sc
->sc_tcn_timer
);
1013 bstp_config_bpdu_generation(sc
);
1014 bstp_timer_start(&sc
->sc_hello_timer
, 0);
1019 bstp_set_port_priority(struct bridge_softc
*sc
, struct bridge_iflist
*bif
,
1020 uint16_t new_port_id
)
1022 if (bstp_designated_port(sc
, bif
))
1023 bif
->bif_designated_port
= new_port_id
;
1025 bif
->bif_port_id
= new_port_id
;
1027 if ((sc
->sc_bridge_id
== bif
->bif_designated_bridge
) &&
1028 (bif
->bif_port_id
< bif
->bif_designated_port
)) {
1029 bstp_become_designated_port(sc
, bif
);
1030 bstp_port_state_selection(sc
);
1035 bstp_set_path_cost(struct bridge_softc
*sc
, struct bridge_iflist
*bif
,
1038 bif
->bif_path_cost
= path_cost
;
1039 bstp_configuration_update(sc
);
1040 bstp_port_state_selection(sc
);
1044 bstp_enable_change_detection(struct bridge_iflist
*bif
)
1046 bif
->bif_change_detection_enabled
= 1;
1050 bstp_disable_change_detection(struct bridge_iflist
*bif
)
1052 bif
->bif_change_detection_enabled
= 0;
1054 #endif /* notused */
1057 bstp_linkstate(struct ifnet
*ifp
, int state
)
1059 struct bridge_softc
*sc
;
1060 struct bridge_iflist
*bif
;
1062 sc
= ifp
->if_bridge
;
1063 ifnet_serialize_all(sc
->sc_ifp
);
1066 * bstp_ifupdstatus() may block, but it is the last
1067 * operation of the member iface iteration, so we
1068 * don't need to use LIST_FOREACH_MUTABLE()+bif_onlist
1071 LIST_FOREACH(bif
, &sc
->sc_iflists
[mycpuid
], bif_next
) {
1072 if ((bif
->bif_flags
& IFBIF_STP
) == 0)
1075 if (bif
->bif_ifp
== ifp
) {
1076 bstp_ifupdstatus(sc
, bif
);
1080 ifnet_deserialize_all(sc
->sc_ifp
);
1084 bstp_ifupdstatus(struct bridge_softc
*sc
, struct bridge_iflist
*bif
)
1086 struct ifnet
*ifp
= bif
->bif_ifp
;
1087 struct ifmediareq ifmr
;
1090 bzero((char *)&ifmr
, sizeof(ifmr
));
1091 ifnet_serialize_all(ifp
);
1092 error
= (*ifp
->if_ioctl
)(ifp
, SIOCGIFMEDIA
, (caddr_t
)&ifmr
, NULL
);
1093 ifnet_deserialize_all(ifp
);
1095 if ((error
== 0) && (ifp
->if_flags
& IFF_UP
)) {
1096 if (ifmr
.ifm_status
& IFM_ACTIVE
) {
1097 if (bif
->bif_state
== BSTP_IFSTATE_DISABLED
)
1098 bstp_enable_port(sc
, bif
);
1101 if (bif
->bif_state
!= BSTP_IFSTATE_DISABLED
)
1102 bstp_disable_port(sc
, bif
);
1107 if (bif
->bif_state
!= BSTP_IFSTATE_DISABLED
)
1108 bstp_disable_port(sc
, bif
);
1112 bstp_tick(void *arg
)
1114 struct bridge_softc
*sc
= arg
;
1115 struct lwkt_msg
*lmsg
;
1117 KKASSERT(mycpuid
== BRIDGE_CFGCPU
);
1121 if (callout_pending(&sc
->sc_bstpcallout
) ||
1122 !callout_active(&sc
->sc_bstpcallout
)) {
1126 callout_deactivate(&sc
->sc_bstpcallout
);
1128 lmsg
= &sc
->sc_bstptimemsg
.nm_lmsg
;
1129 KKASSERT(lmsg
->ms_flags
& MSGF_DONE
);
1130 lwkt_sendmsg(BRIDGE_CFGPORT
, lmsg
);
1136 bstp_tick_handler(struct netmsg
*nmsg
)
1138 struct bridge_softc
*sc
= nmsg
->nm_lmsg
.u
.ms_resultp
;
1139 struct bridge_iflist
*bif
;
1141 KKASSERT(&curthread
->td_msgport
== BRIDGE_CFGPORT
);
1144 lwkt_replymsg(&nmsg
->nm_lmsg
, 0);
1147 ifnet_serialize_all(sc
->sc_ifp
);
1151 * We don't need to worry that member iface is ripped
1152 * from the per-cpu list during the blocking operation
1153 * in the loop body, since deletion is serialized by
1157 LIST_FOREACH(bif
, &sc
->sc_iflists
[mycpuid
], bif_next
) {
1158 if ((bif
->bif_flags
& IFBIF_STP
) == 0)
1161 * XXX This can cause a lag in "link does away"
1162 * XXX and "spanning tree gets updated". We need
1163 * XXX come sort of callback from the link state
1164 * XXX update code to kick spanning tree.
1165 * XXX --thorpej@NetBSD.org
1167 bstp_ifupdstatus(sc
, bif
);
1170 if (bstp_timer_expired(&sc
->sc_hello_timer
, sc
->sc_hello_time
))
1171 bstp_hello_timer_expiry(sc
);
1173 if (bstp_timer_expired(&sc
->sc_tcn_timer
, sc
->sc_bridge_hello_time
))
1174 bstp_tcn_timer_expiry(sc
);
1176 if (bstp_timer_expired(&sc
->sc_topology_change_timer
,
1177 sc
->sc_topology_change_time
))
1178 bstp_topology_change_timer_expiry(sc
);
1180 LIST_FOREACH(bif
, &sc
->sc_iflists
[mycpuid
], bif_next
) {
1181 if ((bif
->bif_flags
& IFBIF_STP
) == 0)
1183 if (bstp_timer_expired(&bif
->bif_message_age_timer
,
1185 bstp_message_age_timer_expiry(sc
, bif
);
1188 LIST_FOREACH(bif
, &sc
->sc_iflists
[mycpuid
], bif_next
) {
1189 if ((bif
->bif_flags
& IFBIF_STP
) == 0)
1191 if (bstp_timer_expired(&bif
->bif_forward_delay_timer
,
1192 sc
->sc_forward_delay
))
1193 bstp_forward_delay_timer_expiry(sc
, bif
);
1195 if (bstp_timer_expired(&bif
->bif_hold_timer
,
1197 bstp_hold_timer_expiry(sc
, bif
);
1200 if (sc
->sc_ifp
->if_flags
& IFF_RUNNING
)
1201 callout_reset(&sc
->sc_bstpcallout
, hz
, bstp_tick
, sc
);
1203 ifnet_deserialize_all(sc
->sc_ifp
);
1207 bstp_timer_start(struct bridge_timer
*t
, uint16_t v
)
1214 bstp_timer_stop(struct bridge_timer
*t
)
1221 bstp_timer_expired(struct bridge_timer
*t
, uint16_t v
)
1225 t
->value
+= BSTP_TICK_VAL
;
1226 if (t
->value
>= v
) {