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.5 2008/06/14 07:58:46 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>
58 #include <net/if_dl.h>
59 #include <net/if_types.h>
60 #include <net/if_llc.h>
61 #include <net/if_media.h>
63 #include <netinet/in.h>
64 #include <netinet/in_systm.h>
65 #include <netinet/in_var.h>
66 #include <netinet/if_ether.h>
67 #include <net/bridge/if_bridgevar.h>
69 /* BPDU message types */
70 #define BSTP_MSGTYPE_CFG 0x00 /* Configuration */
71 #define BSTP_MSGTYPE_TCN 0x80 /* Topology chg notification */
74 #define BSTP_FLAG_TC 0x01 /* Topology change */
75 #define BSTP_FLAG_TCA 0x80 /* Topology change ack */
77 #define BSTP_MESSAGE_AGE_INCR (1 * 256) /* in 256ths of a second */
78 #define BSTP_TICK_VAL (1 * 256) /* in 256ths of a second */
81 * Because BPDU's do not make nicely aligned structures, two different
82 * declarations are used: bstp_?bpdu (wire representation, packed) and
83 * bstp_*_unit (internal, nicely aligned version).
86 /* configuration bridge protocol data unit */
88 uint8_t cbu_dsap
; /* LLC: destination sap */
89 uint8_t cbu_ssap
; /* LLC: source sap */
90 uint8_t cbu_ctl
; /* LLC: control */
91 uint16_t cbu_protoid
; /* protocol id */
92 uint8_t cbu_protover
; /* protocol version */
93 uint8_t cbu_bpdutype
; /* message type */
94 uint8_t cbu_flags
; /* flags (below) */
97 uint16_t cbu_rootpri
; /* root priority */
98 uint8_t cbu_rootaddr
[6]; /* root address */
100 uint32_t cbu_rootpathcost
; /* root path cost */
103 uint16_t cbu_bridgepri
; /* bridge priority */
104 uint8_t cbu_bridgeaddr
[6]; /* bridge address */
106 uint16_t cbu_portid
; /* port id */
107 uint16_t cbu_messageage
; /* current message age */
108 uint16_t cbu_maxage
; /* maximum age */
109 uint16_t cbu_hellotime
; /* hello time */
110 uint16_t cbu_forwarddelay
; /* forwarding delay */
111 } __attribute__((__packed__
));
113 /* topology change notification bridge protocol data unit */
115 uint8_t tbu_dsap
; /* LLC: destination sap */
116 uint8_t tbu_ssap
; /* LLC: source sap */
117 uint8_t tbu_ctl
; /* LLC: control */
118 uint16_t tbu_protoid
; /* protocol id */
119 uint8_t tbu_protover
; /* protocol version */
120 uint8_t tbu_bpdutype
; /* message type */
121 } __attribute__((__packed__
));
123 const uint8_t bstp_etheraddr
[] = { 0x01, 0x80, 0xc2, 0x00, 0x00, 0x00 };
125 static void bstp_initialize_port(struct bridge_softc
*,
126 struct bridge_iflist
*);
127 static void bstp_ifupdstatus(struct bridge_softc
*, struct bridge_iflist
*);
128 static void bstp_enable_port(struct bridge_softc
*, struct bridge_iflist
*);
129 static void bstp_disable_port(struct bridge_softc
*,
130 struct bridge_iflist
*);
132 static void bstp_enable_change_detection(struct bridge_iflist
*);
133 static void bstp_disable_change_detection(struct bridge_iflist
*);
135 static int bstp_root_bridge(struct bridge_softc
*sc
);
136 static int bstp_supersedes_port_info(struct bridge_softc
*,
137 struct bridge_iflist
*, struct bstp_config_unit
*);
138 static int bstp_designated_port(struct bridge_softc
*,
139 struct bridge_iflist
*);
140 static int bstp_designated_for_some_port(struct bridge_softc
*);
141 static void bstp_transmit_config(struct bridge_softc
*,
142 struct bridge_iflist
*);
143 static void bstp_transmit_tcn(struct bridge_softc
*);
144 static void bstp_received_config_bpdu(struct bridge_softc
*,
145 struct bridge_iflist
*, struct bstp_config_unit
*);
146 static void bstp_received_tcn_bpdu(struct bridge_softc
*,
147 struct bridge_iflist
*, struct bstp_tcn_unit
*);
148 static void bstp_record_config_information(struct bridge_softc
*,
149 struct bridge_iflist
*, struct bstp_config_unit
*);
150 static void bstp_record_config_timeout_values(struct bridge_softc
*,
151 struct bstp_config_unit
*);
152 static void bstp_config_bpdu_generation(struct bridge_softc
*);
153 static void bstp_send_config_bpdu(struct bridge_softc
*,
154 struct bridge_iflist
*, struct bstp_config_unit
*);
155 static void bstp_configuration_update(struct bridge_softc
*);
156 static void bstp_root_selection(struct bridge_softc
*);
157 static void bstp_designated_port_selection(struct bridge_softc
*);
158 static void bstp_become_designated_port(struct bridge_softc
*,
159 struct bridge_iflist
*);
160 static void bstp_port_state_selection(struct bridge_softc
*);
161 static void bstp_make_forwarding(struct bridge_softc
*,
162 struct bridge_iflist
*);
163 static void bstp_make_blocking(struct bridge_softc
*,
164 struct bridge_iflist
*);
165 static void bstp_set_port_state(struct bridge_iflist
*, uint8_t);
167 static void bstp_set_bridge_priority(struct bridge_softc
*, uint64_t);
168 static void bstp_set_port_priority(struct bridge_softc
*,
169 struct bridge_iflist
*, uint16_t);
170 static void bstp_set_path_cost(struct bridge_softc
*,
171 struct bridge_iflist
*, uint32_t);
173 static void bstp_topology_change_detection(struct bridge_softc
*);
174 static void bstp_topology_change_acknowledged(struct bridge_softc
*);
175 static void bstp_acknowledge_topology_change(struct bridge_softc
*,
176 struct bridge_iflist
*);
178 static void bstp_tick(void *);
179 static void bstp_timer_start(struct bridge_timer
*, uint16_t);
180 static void bstp_timer_stop(struct bridge_timer
*);
181 static int bstp_timer_expired(struct bridge_timer
*, uint16_t);
183 static void bstp_hold_timer_expiry(struct bridge_softc
*,
184 struct bridge_iflist
*);
185 static void bstp_message_age_timer_expiry(struct bridge_softc
*,
186 struct bridge_iflist
*);
187 static void bstp_forward_delay_timer_expiry(struct bridge_softc
*,
188 struct bridge_iflist
*);
189 static void bstp_topology_change_timer_expiry(struct bridge_softc
*);
190 static void bstp_tcn_timer_expiry(struct bridge_softc
*);
191 static void bstp_hello_timer_expiry(struct bridge_softc
*);
192 static int bstp_addr_cmp(const uint8_t *, const uint8_t *);
195 bstp_transmit_config(struct bridge_softc
*sc
, struct bridge_iflist
*bif
)
197 if (bif
->bif_hold_timer
.active
) {
198 bif
->bif_config_pending
= 1;
202 bif
->bif_config_bpdu
.cu_message_type
= BSTP_MSGTYPE_CFG
;
203 bif
->bif_config_bpdu
.cu_rootid
= sc
->sc_designated_root
;
204 bif
->bif_config_bpdu
.cu_root_path_cost
= sc
->sc_root_path_cost
;
205 bif
->bif_config_bpdu
.cu_bridge_id
= sc
->sc_bridge_id
;
206 bif
->bif_config_bpdu
.cu_port_id
= bif
->bif_port_id
;
208 if (bstp_root_bridge(sc
))
209 bif
->bif_config_bpdu
.cu_message_age
= 0;
211 bif
->bif_config_bpdu
.cu_message_age
=
212 sc
->sc_root_port
->bif_message_age_timer
.value
+
213 BSTP_MESSAGE_AGE_INCR
;
215 bif
->bif_config_bpdu
.cu_max_age
= sc
->sc_max_age
;
216 bif
->bif_config_bpdu
.cu_hello_time
= sc
->sc_hello_time
;
217 bif
->bif_config_bpdu
.cu_forward_delay
= sc
->sc_forward_delay
;
218 bif
->bif_config_bpdu
.cu_topology_change_acknowledgment
219 = bif
->bif_topology_change_acknowledge
;
220 bif
->bif_config_bpdu
.cu_topology_change
= sc
->sc_topology_change
;
222 if (bif
->bif_config_bpdu
.cu_message_age
< sc
->sc_max_age
) {
223 bif
->bif_topology_change_acknowledge
= 0;
224 bif
->bif_config_pending
= 0;
225 bstp_send_config_bpdu(sc
, bif
, &bif
->bif_config_bpdu
);
226 bstp_timer_start(&bif
->bif_hold_timer
, 0);
231 bstp_send_config_bpdu(struct bridge_softc
*sc
, struct bridge_iflist
*bif
,
232 struct bstp_config_unit
*cu
)
236 struct ether_header
*eh
;
237 struct bstp_cbpdu bpdu
;
241 if ((ifp
->if_flags
& IFF_RUNNING
) == 0)
244 MGETHDR(m
, MB_DONTWAIT
, MT_DATA
);
248 eh
= mtod(m
, struct ether_header
*);
250 m
->m_pkthdr
.rcvif
= ifp
;
251 m
->m_pkthdr
.len
= sizeof(*eh
) + sizeof(bpdu
);
252 m
->m_len
= m
->m_pkthdr
.len
;
254 bpdu
.cbu_ssap
= bpdu
.cbu_dsap
= LLC_8021D_LSAP
;
255 bpdu
.cbu_ctl
= LLC_UI
;
256 bpdu
.cbu_protoid
= htons(0);
257 bpdu
.cbu_protover
= 0;
258 bpdu
.cbu_bpdutype
= cu
->cu_message_type
;
259 bpdu
.cbu_flags
= (cu
->cu_topology_change
? BSTP_FLAG_TC
: 0) |
260 (cu
->cu_topology_change_acknowledgment
? BSTP_FLAG_TCA
: 0);
262 bpdu
.cbu_rootpri
= htons(cu
->cu_rootid
>> 48);
263 bpdu
.cbu_rootaddr
[0] = cu
->cu_rootid
>> 40;
264 bpdu
.cbu_rootaddr
[1] = cu
->cu_rootid
>> 32;
265 bpdu
.cbu_rootaddr
[2] = cu
->cu_rootid
>> 24;
266 bpdu
.cbu_rootaddr
[3] = cu
->cu_rootid
>> 16;
267 bpdu
.cbu_rootaddr
[4] = cu
->cu_rootid
>> 8;
268 bpdu
.cbu_rootaddr
[5] = cu
->cu_rootid
>> 0;
270 bpdu
.cbu_rootpathcost
= htonl(cu
->cu_root_path_cost
);
272 bpdu
.cbu_bridgepri
= htons(cu
->cu_bridge_id
>> 48);
273 bpdu
.cbu_bridgeaddr
[0] = cu
->cu_bridge_id
>> 40;
274 bpdu
.cbu_bridgeaddr
[1] = cu
->cu_bridge_id
>> 32;
275 bpdu
.cbu_bridgeaddr
[2] = cu
->cu_bridge_id
>> 24;
276 bpdu
.cbu_bridgeaddr
[3] = cu
->cu_bridge_id
>> 16;
277 bpdu
.cbu_bridgeaddr
[4] = cu
->cu_bridge_id
>> 8;
278 bpdu
.cbu_bridgeaddr
[5] = cu
->cu_bridge_id
>> 0;
280 bpdu
.cbu_portid
= htons(cu
->cu_port_id
);
281 bpdu
.cbu_messageage
= htons(cu
->cu_message_age
);
282 bpdu
.cbu_maxage
= htons(cu
->cu_max_age
);
283 bpdu
.cbu_hellotime
= htons(cu
->cu_hello_time
);
284 bpdu
.cbu_forwarddelay
= htons(cu
->cu_forward_delay
);
286 memcpy(eh
->ether_shost
, IF_LLADDR(ifp
), ETHER_ADDR_LEN
);
287 memcpy(eh
->ether_dhost
, bstp_etheraddr
, ETHER_ADDR_LEN
);
288 eh
->ether_type
= htons(sizeof(bpdu
));
290 memcpy(mtod(m
, caddr_t
) + sizeof(*eh
), &bpdu
, sizeof(bpdu
));
292 bridge_enqueue(ifp
, m
);
296 bstp_root_bridge(struct bridge_softc
*sc
)
298 return (sc
->sc_designated_root
== sc
->sc_bridge_id
);
302 bstp_supersedes_port_info(struct bridge_softc
*sc
, struct bridge_iflist
*bif
,
303 struct bstp_config_unit
*cu
)
305 if (cu
->cu_rootid
< bif
->bif_designated_root
)
307 if (cu
->cu_rootid
> bif
->bif_designated_root
)
310 if (cu
->cu_root_path_cost
< bif
->bif_designated_cost
)
312 if (cu
->cu_root_path_cost
> bif
->bif_designated_cost
)
315 if (cu
->cu_bridge_id
< bif
->bif_designated_bridge
)
317 if (cu
->cu_bridge_id
> bif
->bif_designated_bridge
)
320 if (sc
->sc_bridge_id
!= cu
->cu_bridge_id
)
322 if (cu
->cu_port_id
<= bif
->bif_designated_port
)
328 bstp_record_config_information(struct bridge_softc
*sc
,
329 struct bridge_iflist
*bif
, struct bstp_config_unit
*cu
)
331 bif
->bif_designated_root
= cu
->cu_rootid
;
332 bif
->bif_designated_cost
= cu
->cu_root_path_cost
;
333 bif
->bif_designated_bridge
= cu
->cu_bridge_id
;
334 bif
->bif_designated_port
= cu
->cu_port_id
;
335 bstp_timer_start(&bif
->bif_message_age_timer
, cu
->cu_message_age
);
339 bstp_record_config_timeout_values(struct bridge_softc
*sc
,
340 struct bstp_config_unit
*config
)
342 sc
->sc_max_age
= config
->cu_max_age
;
343 sc
->sc_hello_time
= config
->cu_hello_time
;
344 sc
->sc_forward_delay
= config
->cu_forward_delay
;
345 sc
->sc_topology_change
= config
->cu_topology_change
;
349 bstp_config_bpdu_generation(struct bridge_softc
*sc
)
351 struct bridge_iflist
*bif
;
353 LIST_FOREACH(bif
, &sc
->sc_iflist
, bif_next
) {
354 if ((bif
->bif_flags
& IFBIF_STP
) == 0)
356 if (bstp_designated_port(sc
, bif
) &&
357 (bif
->bif_state
!= BSTP_IFSTATE_DISABLED
))
358 bstp_transmit_config(sc
, bif
);
363 bstp_designated_port(struct bridge_softc
*sc
, struct bridge_iflist
*bif
)
365 return ((bif
->bif_designated_bridge
== sc
->sc_bridge_id
)
366 && (bif
->bif_designated_port
== bif
->bif_port_id
));
370 bstp_transmit_tcn(struct bridge_softc
*sc
)
372 struct bstp_tbpdu bpdu
;
373 struct bridge_iflist
*bif
= sc
->sc_root_port
;
374 struct ifnet
*ifp
= bif
->bif_ifp
;
375 struct ether_header
*eh
;
378 if ((ifp
->if_flags
& IFF_RUNNING
) == 0)
381 MGETHDR(m
, MB_DONTWAIT
, MT_DATA
);
385 m
->m_pkthdr
.rcvif
= ifp
;
386 m
->m_pkthdr
.len
= sizeof(*eh
) + sizeof(bpdu
);
387 m
->m_len
= m
->m_pkthdr
.len
;
389 eh
= mtod(m
, struct ether_header
*);
391 memcpy(eh
->ether_shost
, IF_LLADDR(ifp
), ETHER_ADDR_LEN
);
392 memcpy(eh
->ether_dhost
, bstp_etheraddr
, ETHER_ADDR_LEN
);
393 eh
->ether_type
= htons(sizeof(bpdu
));
395 bpdu
.tbu_ssap
= bpdu
.tbu_dsap
= LLC_8021D_LSAP
;
396 bpdu
.tbu_ctl
= LLC_UI
;
397 bpdu
.tbu_protoid
= 0;
398 bpdu
.tbu_protover
= 0;
399 bpdu
.tbu_bpdutype
= BSTP_MSGTYPE_TCN
;
401 memcpy(mtod(m
, caddr_t
) + sizeof(*eh
), &bpdu
, sizeof(bpdu
));
403 bridge_enqueue(ifp
, m
);
407 bstp_configuration_update(struct bridge_softc
*sc
)
409 bstp_root_selection(sc
);
410 bstp_designated_port_selection(sc
);
414 bstp_root_selection(struct bridge_softc
*sc
)
416 struct bridge_iflist
*root_port
= NULL
, *bif
;
418 LIST_FOREACH(bif
, &sc
->sc_iflist
, bif_next
) {
419 if ((bif
->bif_flags
& IFBIF_STP
) == 0)
421 if (bstp_designated_port(sc
, bif
))
423 if (bif
->bif_state
== BSTP_IFSTATE_DISABLED
)
425 if (bif
->bif_designated_root
>= sc
->sc_bridge_id
)
427 if (root_port
== NULL
)
430 if (bif
->bif_designated_root
< root_port
->bif_designated_root
)
432 if (bif
->bif_designated_root
> root_port
->bif_designated_root
)
435 if ((bif
->bif_designated_cost
+ bif
->bif_path_cost
) <
436 (root_port
->bif_designated_cost
+ root_port
->bif_path_cost
))
438 if ((bif
->bif_designated_cost
+ bif
->bif_path_cost
) >
439 (root_port
->bif_designated_cost
+ root_port
->bif_path_cost
))
442 if (bif
->bif_designated_bridge
<
443 root_port
->bif_designated_bridge
)
445 if (bif
->bif_designated_bridge
>
446 root_port
->bif_designated_bridge
)
449 if (bif
->bif_designated_port
< root_port
->bif_designated_port
)
451 if (bif
->bif_designated_port
> root_port
->bif_designated_port
)
454 if (bif
->bif_port_id
>= root_port
->bif_port_id
)
460 sc
->sc_root_port
= root_port
;
461 if (root_port
== NULL
) {
462 sc
->sc_designated_root
= sc
->sc_bridge_id
;
463 sc
->sc_root_path_cost
= 0;
465 sc
->sc_designated_root
= root_port
->bif_designated_root
;
466 sc
->sc_root_path_cost
= root_port
->bif_designated_cost
+
467 root_port
->bif_path_cost
;
472 bstp_designated_port_selection(struct bridge_softc
*sc
)
474 struct bridge_iflist
*bif
;
476 LIST_FOREACH(bif
, &sc
->sc_iflist
, bif_next
) {
477 if ((bif
->bif_flags
& IFBIF_STP
) == 0)
479 if (bstp_designated_port(sc
, bif
))
481 if (bif
->bif_designated_root
!= sc
->sc_designated_root
)
484 if (sc
->sc_root_path_cost
< bif
->bif_designated_cost
)
486 if (sc
->sc_root_path_cost
> bif
->bif_designated_cost
)
489 if (sc
->sc_bridge_id
< bif
->bif_designated_bridge
)
491 if (sc
->sc_bridge_id
> bif
->bif_designated_bridge
)
494 if (bif
->bif_port_id
> bif
->bif_designated_port
)
497 bstp_become_designated_port(sc
, bif
);
502 bstp_become_designated_port(struct bridge_softc
*sc
, struct bridge_iflist
*bif
)
504 bif
->bif_designated_root
= sc
->sc_designated_root
;
505 bif
->bif_designated_cost
= sc
->sc_root_path_cost
;
506 bif
->bif_designated_bridge
= sc
->sc_bridge_id
;
507 bif
->bif_designated_port
= bif
->bif_port_id
;
511 bstp_port_state_selection(struct bridge_softc
*sc
)
513 struct bridge_iflist
*bif
;
515 LIST_FOREACH(bif
, &sc
->sc_iflist
, bif_next
) {
516 if ((bif
->bif_flags
& IFBIF_STP
) == 0)
518 if (bif
== sc
->sc_root_port
) {
519 bif
->bif_config_pending
= 0;
520 bif
->bif_topology_change_acknowledge
= 0;
521 bstp_make_forwarding(sc
, bif
);
522 } else if (bstp_designated_port(sc
, bif
)) {
523 bstp_timer_stop(&bif
->bif_message_age_timer
);
524 bstp_make_forwarding(sc
, bif
);
526 bif
->bif_config_pending
= 0;
527 bif
->bif_topology_change_acknowledge
= 0;
528 bstp_make_blocking(sc
, bif
);
534 bstp_make_forwarding(struct bridge_softc
*sc
, struct bridge_iflist
*bif
)
536 if (bif
->bif_state
== BSTP_IFSTATE_BLOCKING
) {
537 bstp_set_port_state(bif
, BSTP_IFSTATE_LISTENING
);
538 bstp_timer_start(&bif
->bif_forward_delay_timer
, 0);
543 bstp_make_blocking(struct bridge_softc
*sc
, struct bridge_iflist
*bif
)
545 if ((bif
->bif_state
!= BSTP_IFSTATE_DISABLED
) &&
546 (bif
->bif_state
!= BSTP_IFSTATE_BLOCKING
)) {
547 if ((bif
->bif_state
== BSTP_IFSTATE_FORWARDING
) ||
548 (bif
->bif_state
== BSTP_IFSTATE_LEARNING
)) {
549 if (bif
->bif_change_detection_enabled
) {
550 bstp_topology_change_detection(sc
);
553 bstp_set_port_state(bif
, BSTP_IFSTATE_BLOCKING
);
554 bridge_rtdelete(sc
, bif
->bif_ifp
, IFBF_FLUSHDYN
);
555 bstp_timer_stop(&bif
->bif_forward_delay_timer
);
560 bstp_set_port_state(struct bridge_iflist
*bif
, uint8_t state
)
562 bif
->bif_state
= state
;
566 bstp_topology_change_detection(struct bridge_softc
*sc
)
568 if (bstp_root_bridge(sc
)) {
569 sc
->sc_topology_change
= 1;
570 bstp_timer_start(&sc
->sc_topology_change_timer
, 0);
571 } else if (!sc
->sc_topology_change_detected
) {
572 bstp_transmit_tcn(sc
);
573 bstp_timer_start(&sc
->sc_tcn_timer
, 0);
575 sc
->sc_topology_change_detected
= 1;
579 bstp_topology_change_acknowledged(struct bridge_softc
*sc
)
581 sc
->sc_topology_change_detected
= 0;
582 bstp_timer_stop(&sc
->sc_tcn_timer
);
586 bstp_acknowledge_topology_change(struct bridge_softc
*sc
,
587 struct bridge_iflist
*bif
)
589 bif
->bif_topology_change_acknowledge
= 1;
590 bstp_transmit_config(sc
, bif
);
594 bstp_input(struct bridge_softc
*sc
, struct bridge_iflist
*bif
, struct mbuf
*m
)
596 struct ether_header
*eh
;
597 struct bstp_tbpdu tpdu
;
598 struct bstp_cbpdu cpdu
;
599 struct bstp_config_unit cu
;
600 struct bstp_tcn_unit tu
;
603 if ((bif
->bif_flags
& IFBIF_STP
) == 0)
606 eh
= mtod(m
, struct ether_header
*);
608 len
= ntohs(eh
->ether_type
);
609 if (len
< sizeof(tpdu
))
612 m_adj(m
, ETHER_HDR_LEN
);
614 if (m
->m_pkthdr
.len
> len
)
615 m_adj(m
, len
- m
->m_pkthdr
.len
);
616 if (m
->m_len
< sizeof(tpdu
) &&
617 (m
= m_pullup(m
, sizeof(tpdu
))) == NULL
)
620 memcpy(&tpdu
, mtod(m
, caddr_t
), sizeof(tpdu
));
622 if (tpdu
.tbu_dsap
!= LLC_8021D_LSAP
||
623 tpdu
.tbu_ssap
!= LLC_8021D_LSAP
||
624 tpdu
.tbu_ctl
!= LLC_UI
)
626 if (tpdu
.tbu_protoid
!= 0 || tpdu
.tbu_protover
!= 0)
629 switch (tpdu
.tbu_bpdutype
) {
630 case BSTP_MSGTYPE_TCN
:
631 tu
.tu_message_type
= tpdu
.tbu_bpdutype
;
632 bstp_received_tcn_bpdu(sc
, bif
, &tu
);
634 case BSTP_MSGTYPE_CFG
:
635 if (m
->m_len
< sizeof(cpdu
) &&
636 (m
= m_pullup(m
, sizeof(cpdu
))) == NULL
)
638 memcpy(&cpdu
, mtod(m
, caddr_t
), sizeof(cpdu
));
641 (((uint64_t)ntohs(cpdu
.cbu_rootpri
)) << 48) |
642 (((uint64_t)cpdu
.cbu_rootaddr
[0]) << 40) |
643 (((uint64_t)cpdu
.cbu_rootaddr
[1]) << 32) |
644 (((uint64_t)cpdu
.cbu_rootaddr
[2]) << 24) |
645 (((uint64_t)cpdu
.cbu_rootaddr
[3]) << 16) |
646 (((uint64_t)cpdu
.cbu_rootaddr
[4]) << 8) |
647 (((uint64_t)cpdu
.cbu_rootaddr
[5]) << 0);
650 (((uint64_t)ntohs(cpdu
.cbu_bridgepri
)) << 48) |
651 (((uint64_t)cpdu
.cbu_bridgeaddr
[0]) << 40) |
652 (((uint64_t)cpdu
.cbu_bridgeaddr
[1]) << 32) |
653 (((uint64_t)cpdu
.cbu_bridgeaddr
[2]) << 24) |
654 (((uint64_t)cpdu
.cbu_bridgeaddr
[3]) << 16) |
655 (((uint64_t)cpdu
.cbu_bridgeaddr
[4]) << 8) |
656 (((uint64_t)cpdu
.cbu_bridgeaddr
[5]) << 0);
658 cu
.cu_root_path_cost
= ntohl(cpdu
.cbu_rootpathcost
);
659 cu
.cu_message_age
= ntohs(cpdu
.cbu_messageage
);
660 cu
.cu_max_age
= ntohs(cpdu
.cbu_maxage
);
661 cu
.cu_hello_time
= ntohs(cpdu
.cbu_hellotime
);
662 cu
.cu_forward_delay
= ntohs(cpdu
.cbu_forwarddelay
);
663 cu
.cu_port_id
= ntohs(cpdu
.cbu_portid
);
664 cu
.cu_message_type
= cpdu
.cbu_bpdutype
;
665 cu
.cu_topology_change_acknowledgment
=
666 (cpdu
.cbu_flags
& BSTP_FLAG_TCA
) ? 1 : 0;
667 cu
.cu_topology_change
=
668 (cpdu
.cbu_flags
& BSTP_FLAG_TC
) ? 1 : 0;
669 bstp_received_config_bpdu(sc
, bif
, &cu
);
682 bstp_received_config_bpdu(struct bridge_softc
*sc
, struct bridge_iflist
*bif
,
683 struct bstp_config_unit
*cu
)
687 root
= bstp_root_bridge(sc
);
689 if (bif
->bif_state
!= BSTP_IFSTATE_DISABLED
) {
690 if (bstp_supersedes_port_info(sc
, bif
, cu
)) {
691 bstp_record_config_information(sc
, bif
, cu
);
692 bstp_configuration_update(sc
);
693 bstp_port_state_selection(sc
);
695 if ((bstp_root_bridge(sc
) == 0) && root
) {
696 bstp_timer_stop(&sc
->sc_hello_timer
);
698 if (sc
->sc_topology_change_detected
) {
700 &sc
->sc_topology_change_timer
);
701 bstp_transmit_tcn(sc
);
702 bstp_timer_start(&sc
->sc_tcn_timer
, 0);
706 if (bif
== sc
->sc_root_port
) {
707 bstp_record_config_timeout_values(sc
, cu
);
708 bstp_config_bpdu_generation(sc
);
710 if (cu
->cu_topology_change_acknowledgment
)
711 bstp_topology_change_acknowledged(sc
);
713 } else if (bstp_designated_port(sc
, bif
))
714 bstp_transmit_config(sc
, bif
);
719 bstp_received_tcn_bpdu(struct bridge_softc
*sc
, struct bridge_iflist
*bif
,
720 struct bstp_tcn_unit
*tcn
)
722 if (bif
->bif_state
!= BSTP_IFSTATE_DISABLED
&&
723 bstp_designated_port(sc
, bif
)) {
724 bstp_topology_change_detection(sc
);
725 bstp_acknowledge_topology_change(sc
, bif
);
730 bstp_hello_timer_expiry(struct bridge_softc
*sc
)
732 bstp_config_bpdu_generation(sc
);
733 bstp_timer_start(&sc
->sc_hello_timer
, 0);
737 bstp_message_age_timer_expiry(struct bridge_softc
*sc
,
738 struct bridge_iflist
*bif
)
742 root
= bstp_root_bridge(sc
);
743 bstp_become_designated_port(sc
, bif
);
744 bstp_configuration_update(sc
);
745 bstp_port_state_selection(sc
);
747 if ((bstp_root_bridge(sc
)) && (root
== 0)) {
748 sc
->sc_max_age
= sc
->sc_bridge_max_age
;
749 sc
->sc_hello_time
= sc
->sc_bridge_hello_time
;
750 sc
->sc_forward_delay
= sc
->sc_bridge_forward_delay
;
752 bstp_topology_change_detection(sc
);
753 bstp_timer_stop(&sc
->sc_tcn_timer
);
754 bstp_config_bpdu_generation(sc
);
755 bstp_timer_start(&sc
->sc_hello_timer
, 0);
760 bstp_forward_delay_timer_expiry(struct bridge_softc
*sc
,
761 struct bridge_iflist
*bif
)
763 if (bif
->bif_state
== BSTP_IFSTATE_LISTENING
) {
764 bstp_set_port_state(bif
, BSTP_IFSTATE_LEARNING
);
765 bstp_timer_start(&bif
->bif_forward_delay_timer
, 0);
766 } else if (bif
->bif_state
== BSTP_IFSTATE_LEARNING
) {
767 bstp_set_port_state(bif
, BSTP_IFSTATE_FORWARDING
);
768 if (bstp_designated_for_some_port(sc
) &&
769 bif
->bif_change_detection_enabled
)
770 bstp_topology_change_detection(sc
);
775 bstp_designated_for_some_port(struct bridge_softc
*sc
)
778 struct bridge_iflist
*bif
;
780 LIST_FOREACH(bif
, &sc
->sc_iflist
, bif_next
) {
781 if ((bif
->bif_flags
& IFBIF_STP
) == 0)
783 if (bif
->bif_designated_bridge
== sc
->sc_bridge_id
)
790 bstp_tcn_timer_expiry(struct bridge_softc
*sc
)
792 bstp_transmit_tcn(sc
);
793 bstp_timer_start(&sc
->sc_tcn_timer
, 0);
797 bstp_topology_change_timer_expiry(struct bridge_softc
*sc
)
799 sc
->sc_topology_change_detected
= 0;
800 sc
->sc_topology_change
= 0;
804 bstp_hold_timer_expiry(struct bridge_softc
*sc
, struct bridge_iflist
*bif
)
806 if (bif
->bif_config_pending
)
807 bstp_transmit_config(sc
, bif
);
811 bstp_addr_cmp(const uint8_t *a
, const uint8_t *b
)
815 for (i
= 0, d
= 0; i
< ETHER_ADDR_LEN
&& d
== 0; i
++) {
816 d
= ((int)a
[i
]) - ((int)b
[i
]);
823 bstp_initialization(struct bridge_softc
*sc
)
825 struct bridge_iflist
*bif
, *mif
;
829 LIST_FOREACH(bif
, &sc
->sc_iflist
, bif_next
) {
830 if ((bif
->bif_flags
& IFBIF_STP
) == 0)
832 if (bif
->bif_ifp
->if_type
!= IFT_ETHER
)
834 bif
->bif_port_id
= (bif
->bif_priority
<< 8) |
835 (bif
->bif_ifp
->if_index
& 0xff);
841 if (bstp_addr_cmp(IF_LLADDR(bif
->bif_ifp
),
842 IF_LLADDR(mif
->bif_ifp
)) < 0) {
852 e_addr
= IF_LLADDR(mif
->bif_ifp
);
854 (((uint64_t)sc
->sc_bridge_priority
) << 48) |
855 (((uint64_t)e_addr
[0]) << 40) |
856 (((uint64_t)e_addr
[1]) << 32) |
857 (((uint64_t)e_addr
[2]) << 24) |
858 (((uint64_t)e_addr
[3]) << 16) |
859 (((uint64_t)e_addr
[4]) << 8) |
860 (((uint64_t)e_addr
[5]));
862 sc
->sc_designated_root
= sc
->sc_bridge_id
;
863 sc
->sc_root_path_cost
= 0;
864 sc
->sc_root_port
= NULL
;
866 sc
->sc_max_age
= sc
->sc_bridge_max_age
;
867 sc
->sc_hello_time
= sc
->sc_bridge_hello_time
;
868 sc
->sc_forward_delay
= sc
->sc_bridge_forward_delay
;
869 sc
->sc_topology_change_detected
= 0;
870 sc
->sc_topology_change
= 0;
871 bstp_timer_stop(&sc
->sc_tcn_timer
);
872 bstp_timer_stop(&sc
->sc_topology_change_timer
);
874 if (callout_pending(&sc
->sc_bstpcallout
) == 0)
875 callout_reset(&sc
->sc_bstpcallout
, hz
,
878 LIST_FOREACH(bif
, &sc
->sc_iflist
, bif_next
) {
879 if (bif
->bif_flags
& IFBIF_STP
)
880 bstp_ifupdstatus(sc
, bif
);
882 bstp_disable_port(sc
, bif
);
885 bstp_port_state_selection(sc
);
886 bstp_config_bpdu_generation(sc
);
887 bstp_timer_start(&sc
->sc_hello_timer
, 0);
891 bstp_stop(struct bridge_softc
*sc
)
893 struct bridge_iflist
*bif
;
895 LIST_FOREACH(bif
, &sc
->sc_iflist
, bif_next
) {
896 bstp_set_port_state(bif
, BSTP_IFSTATE_DISABLED
);
897 bstp_timer_stop(&bif
->bif_hold_timer
);
898 bstp_timer_stop(&bif
->bif_message_age_timer
);
899 bstp_timer_stop(&bif
->bif_forward_delay_timer
);
902 callout_stop(&sc
->sc_bstpcallout
);
904 bstp_timer_stop(&sc
->sc_topology_change_timer
);
905 bstp_timer_stop(&sc
->sc_tcn_timer
);
906 bstp_timer_stop(&sc
->sc_hello_timer
);
911 bstp_initialize_port(struct bridge_softc
*sc
, struct bridge_iflist
*bif
)
913 bstp_become_designated_port(sc
, bif
);
914 bstp_set_port_state(bif
, BSTP_IFSTATE_BLOCKING
);
915 bif
->bif_topology_change_acknowledge
= 0;
916 bif
->bif_config_pending
= 0;
917 bif
->bif_change_detection_enabled
= 1;
918 bstp_timer_stop(&bif
->bif_message_age_timer
);
919 bstp_timer_stop(&bif
->bif_forward_delay_timer
);
920 bstp_timer_stop(&bif
->bif_hold_timer
);
924 bstp_enable_port(struct bridge_softc
*sc
, struct bridge_iflist
*bif
)
926 bstp_initialize_port(sc
, bif
);
927 bstp_port_state_selection(sc
);
931 bstp_disable_port(struct bridge_softc
*sc
, struct bridge_iflist
*bif
)
935 root
= bstp_root_bridge(sc
);
936 bstp_become_designated_port(sc
, bif
);
937 bstp_set_port_state(bif
, BSTP_IFSTATE_DISABLED
);
938 bif
->bif_topology_change_acknowledge
= 0;
939 bif
->bif_config_pending
= 0;
940 bstp_timer_stop(&bif
->bif_message_age_timer
);
941 bstp_timer_stop(&bif
->bif_forward_delay_timer
);
942 bstp_configuration_update(sc
);
943 bstp_port_state_selection(sc
);
944 bridge_rtdelete(sc
, bif
->bif_ifp
, IFBF_FLUSHDYN
);
946 if (bstp_root_bridge(sc
) && (root
== 0)) {
947 sc
->sc_max_age
= sc
->sc_bridge_max_age
;
948 sc
->sc_hello_time
= sc
->sc_bridge_hello_time
;
949 sc
->sc_forward_delay
= sc
->sc_bridge_forward_delay
;
951 bstp_topology_change_detection(sc
);
952 bstp_timer_stop(&sc
->sc_tcn_timer
);
953 bstp_config_bpdu_generation(sc
);
954 bstp_timer_start(&sc
->sc_hello_timer
, 0);
960 bstp_set_bridge_priority(struct bridge_softc
*sc
, uint64_t new_bridge_id
)
962 struct bridge_iflist
*bif
;
965 root
= bstp_root_bridge(sc
);
967 LIST_FOREACH(bif
, &sc
->sc_iflist
, bif_next
) {
968 if ((bif
->bif_flags
& IFBIF_STP
) == 0)
970 if (bstp_designated_port(sc
, bif
))
971 bif
->bif_designated_bridge
= new_bridge_id
;
974 sc
->sc_bridge_id
= new_bridge_id
;
976 bstp_configuration_update(sc
);
977 bstp_port_state_selection(sc
);
979 if (bstp_root_bridge(sc
) && (root
== 0)) {
980 sc
->sc_max_age
= sc
->sc_bridge_max_age
;
981 sc
->sc_hello_time
= sc
->sc_bridge_hello_time
;
982 sc
->sc_forward_delay
= sc
->sc_bridge_forward_delay
;
984 bstp_topology_change_detection(sc
);
985 bstp_timer_stop(&sc
->sc_tcn_timer
);
986 bstp_config_bpdu_generation(sc
);
987 bstp_timer_start(&sc
->sc_hello_timer
, 0);
992 bstp_set_port_priority(struct bridge_softc
*sc
, struct bridge_iflist
*bif
,
993 uint16_t new_port_id
)
995 if (bstp_designated_port(sc
, bif
))
996 bif
->bif_designated_port
= new_port_id
;
998 bif
->bif_port_id
= new_port_id
;
1000 if ((sc
->sc_bridge_id
== bif
->bif_designated_bridge
) &&
1001 (bif
->bif_port_id
< bif
->bif_designated_port
)) {
1002 bstp_become_designated_port(sc
, bif
);
1003 bstp_port_state_selection(sc
);
1008 bstp_set_path_cost(struct bridge_softc
*sc
, struct bridge_iflist
*bif
,
1011 bif
->bif_path_cost
= path_cost
;
1012 bstp_configuration_update(sc
);
1013 bstp_port_state_selection(sc
);
1017 bstp_enable_change_detection(struct bridge_iflist
*bif
)
1019 bif
->bif_change_detection_enabled
= 1;
1023 bstp_disable_change_detection(struct bridge_iflist
*bif
)
1025 bif
->bif_change_detection_enabled
= 0;
1027 #endif /* notused */
1030 bstp_linkstate(struct ifnet
*ifp
, int state
)
1032 struct bridge_softc
*sc
;
1033 struct bridge_iflist
*bif
;
1035 sc
= ifp
->if_bridge
;
1036 lwkt_serialize_enter(sc
->sc_ifp
->if_serializer
);
1038 LIST_FOREACH(bif
, &sc
->sc_iflist
, bif_next
) {
1039 if ((bif
->bif_flags
& IFBIF_STP
) == 0)
1042 if (bif
->bif_ifp
== ifp
) {
1043 bstp_ifupdstatus(sc
, bif
);
1047 lwkt_serialize_exit(sc
->sc_ifp
->if_serializer
);
1051 bstp_ifupdstatus(struct bridge_softc
*sc
, struct bridge_iflist
*bif
)
1053 struct ifnet
*ifp
= bif
->bif_ifp
;
1054 struct ifmediareq ifmr
;
1057 bzero((char *)&ifmr
, sizeof(ifmr
));
1058 lwkt_serialize_enter(ifp
->if_serializer
);
1059 error
= (*ifp
->if_ioctl
)(ifp
, SIOCGIFMEDIA
, (caddr_t
)&ifmr
, NULL
);
1060 lwkt_serialize_exit(ifp
->if_serializer
);
1062 if ((error
== 0) && (ifp
->if_flags
& IFF_UP
)) {
1063 if (ifmr
.ifm_status
& IFM_ACTIVE
) {
1064 if (bif
->bif_state
== BSTP_IFSTATE_DISABLED
)
1065 bstp_enable_port(sc
, bif
);
1068 if (bif
->bif_state
!= BSTP_IFSTATE_DISABLED
)
1069 bstp_disable_port(sc
, bif
);
1074 if (bif
->bif_state
!= BSTP_IFSTATE_DISABLED
)
1075 bstp_disable_port(sc
, bif
);
1079 bstp_tick(void *arg
)
1081 struct bridge_softc
*sc
= arg
;
1082 struct bridge_iflist
*bif
;
1084 lwkt_serialize_enter(sc
->sc_ifp
->if_serializer
);
1086 LIST_FOREACH(bif
, &sc
->sc_iflist
, bif_next
) {
1087 if ((bif
->bif_flags
& IFBIF_STP
) == 0)
1090 * XXX This can cause a lag in "link does away"
1091 * XXX and "spanning tree gets updated". We need
1092 * XXX come sort of callback from the link state
1093 * XXX update code to kick spanning tree.
1094 * XXX --thorpej@NetBSD.org
1096 bstp_ifupdstatus(sc
, bif
);
1099 if (bstp_timer_expired(&sc
->sc_hello_timer
, sc
->sc_hello_time
))
1100 bstp_hello_timer_expiry(sc
);
1102 if (bstp_timer_expired(&sc
->sc_tcn_timer
, sc
->sc_bridge_hello_time
))
1103 bstp_tcn_timer_expiry(sc
);
1105 if (bstp_timer_expired(&sc
->sc_topology_change_timer
,
1106 sc
->sc_topology_change_time
))
1107 bstp_topology_change_timer_expiry(sc
);
1109 LIST_FOREACH(bif
, &sc
->sc_iflist
, bif_next
) {
1110 if ((bif
->bif_flags
& IFBIF_STP
) == 0)
1112 if (bstp_timer_expired(&bif
->bif_message_age_timer
,
1114 bstp_message_age_timer_expiry(sc
, bif
);
1117 LIST_FOREACH(bif
, &sc
->sc_iflist
, bif_next
) {
1118 if ((bif
->bif_flags
& IFBIF_STP
) == 0)
1120 if (bstp_timer_expired(&bif
->bif_forward_delay_timer
,
1121 sc
->sc_forward_delay
))
1122 bstp_forward_delay_timer_expiry(sc
, bif
);
1124 if (bstp_timer_expired(&bif
->bif_hold_timer
,
1126 bstp_hold_timer_expiry(sc
, bif
);
1129 if (sc
->sc_ifp
->if_flags
& IFF_RUNNING
)
1130 callout_reset(&sc
->sc_bstpcallout
, hz
, bstp_tick
, sc
);
1132 lwkt_serialize_exit(sc
->sc_ifp
->if_serializer
);
1136 bstp_timer_start(struct bridge_timer
*t
, uint16_t v
)
1143 bstp_timer_stop(struct bridge_timer
*t
)
1150 bstp_timer_expired(struct bridge_timer
*t
, uint16_t v
)
1154 t
->value
+= BSTP_TICK_VAL
;
1155 if (t
->value
>= v
) {