2 * Spanning tree protocol; generic parts
3 * Linux ethernet bridge
6 * Lennert Buytenhek <buytenh@gnu.org>
8 * This program is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU General Public License
10 * as published by the Free Software Foundation; either version
11 * 2 of the License, or (at your option) any later version.
13 #include <linux/kernel.h>
14 #include <linux/rculist.h>
15 #include <net/switchdev.h>
17 #include "br_private.h"
18 #include "br_private_stp.h"
20 /* since time values in bpdu are in jiffies and then scaled (1/256)
21 * before sending, make sure that is at least one STP tick.
23 #define MESSAGE_AGE_INCR ((HZ / 256) + 1)
25 static const char *const br_port_state_names
[] = {
26 [BR_STATE_DISABLED
] = "disabled",
27 [BR_STATE_LISTENING
] = "listening",
28 [BR_STATE_LEARNING
] = "learning",
29 [BR_STATE_FORWARDING
] = "forwarding",
30 [BR_STATE_BLOCKING
] = "blocking",
33 void br_log_state(const struct net_bridge_port
*p
)
35 br_info(p
->br
, "port %u(%s) entered %s state\n",
36 (unsigned int) p
->port_no
, p
->dev
->name
,
37 br_port_state_names
[p
->state
]);
40 void br_set_state(struct net_bridge_port
*p
, unsigned int state
)
42 struct switchdev_attr attr
= {
44 .id
= SWITCHDEV_ATTR_ID_PORT_STP_STATE
,
45 .flags
= SWITCHDEV_F_DEFER
,
51 err
= switchdev_port_attr_set(p
->dev
, &attr
);
52 if (err
&& err
!= -EOPNOTSUPP
)
53 br_warn(p
->br
, "error setting offload STP state on port %u(%s)\n",
54 (unsigned int) p
->port_no
, p
->dev
->name
);
57 /* called under bridge lock */
58 struct net_bridge_port
*br_get_port(struct net_bridge
*br
, u16 port_no
)
60 struct net_bridge_port
*p
;
62 list_for_each_entry_rcu(p
, &br
->port_list
, list
) {
63 if (p
->port_no
== port_no
)
70 /* called under bridge lock */
71 static int br_should_become_root_port(const struct net_bridge_port
*p
,
74 struct net_bridge
*br
;
75 struct net_bridge_port
*rp
;
79 if (p
->state
== BR_STATE_DISABLED
||
80 br_is_designated_port(p
))
83 if (memcmp(&br
->bridge_id
, &p
->designated_root
, 8) <= 0)
89 rp
= br_get_port(br
, root_port
);
91 t
= memcmp(&p
->designated_root
, &rp
->designated_root
, 8);
97 if (p
->designated_cost
+ p
->path_cost
<
98 rp
->designated_cost
+ rp
->path_cost
)
100 else if (p
->designated_cost
+ p
->path_cost
>
101 rp
->designated_cost
+ rp
->path_cost
)
104 t
= memcmp(&p
->designated_bridge
, &rp
->designated_bridge
, 8);
110 if (p
->designated_port
< rp
->designated_port
)
112 else if (p
->designated_port
> rp
->designated_port
)
115 if (p
->port_id
< rp
->port_id
)
121 static void br_root_port_block(const struct net_bridge
*br
,
122 struct net_bridge_port
*p
)
125 br_notice(br
, "port %u(%s) tried to become root port (blocked)",
126 (unsigned int) p
->port_no
, p
->dev
->name
);
128 br_set_state(p
, BR_STATE_LISTENING
);
130 br_ifinfo_notify(RTM_NEWLINK
, p
);
132 if (br
->forward_delay
> 0)
133 mod_timer(&p
->forward_delay_timer
, jiffies
+ br
->forward_delay
);
136 /* called under bridge lock */
137 static void br_root_selection(struct net_bridge
*br
)
139 struct net_bridge_port
*p
;
142 list_for_each_entry(p
, &br
->port_list
, list
) {
143 if (!br_should_become_root_port(p
, root_port
))
146 if (p
->flags
& BR_ROOT_BLOCK
)
147 br_root_port_block(br
, p
);
149 root_port
= p
->port_no
;
152 br
->root_port
= root_port
;
155 br
->designated_root
= br
->bridge_id
;
156 br
->root_path_cost
= 0;
158 p
= br_get_port(br
, root_port
);
159 br
->designated_root
= p
->designated_root
;
160 br
->root_path_cost
= p
->designated_cost
+ p
->path_cost
;
164 /* called under bridge lock */
165 void br_become_root_bridge(struct net_bridge
*br
)
167 br
->max_age
= br
->bridge_max_age
;
168 br
->hello_time
= br
->bridge_hello_time
;
169 br
->forward_delay
= br
->bridge_forward_delay
;
170 br_topology_change_detection(br
);
171 del_timer(&br
->tcn_timer
);
173 if (br
->dev
->flags
& IFF_UP
) {
174 br_config_bpdu_generation(br
);
175 mod_timer(&br
->hello_timer
, jiffies
+ br
->hello_time
);
179 /* called under bridge lock */
180 void br_transmit_config(struct net_bridge_port
*p
)
182 struct br_config_bpdu bpdu
;
183 struct net_bridge
*br
;
185 if (timer_pending(&p
->hold_timer
)) {
186 p
->config_pending
= 1;
192 bpdu
.topology_change
= br
->topology_change
;
193 bpdu
.topology_change_ack
= p
->topology_change_ack
;
194 bpdu
.root
= br
->designated_root
;
195 bpdu
.root_path_cost
= br
->root_path_cost
;
196 bpdu
.bridge_id
= br
->bridge_id
;
197 bpdu
.port_id
= p
->port_id
;
198 if (br_is_root_bridge(br
))
199 bpdu
.message_age
= 0;
201 struct net_bridge_port
*root
202 = br_get_port(br
, br
->root_port
);
203 bpdu
.message_age
= (jiffies
- root
->designated_age
)
206 bpdu
.max_age
= br
->max_age
;
207 bpdu
.hello_time
= br
->hello_time
;
208 bpdu
.forward_delay
= br
->forward_delay
;
210 if (bpdu
.message_age
< br
->max_age
) {
211 br_send_config_bpdu(p
, &bpdu
);
212 p
->topology_change_ack
= 0;
213 p
->config_pending
= 0;
214 if (p
->br
->stp_enabled
== BR_KERNEL_STP
)
215 mod_timer(&p
->hold_timer
,
216 round_jiffies(jiffies
+ BR_HOLD_TIME
));
220 /* called under bridge lock */
221 static void br_record_config_information(struct net_bridge_port
*p
,
222 const struct br_config_bpdu
*bpdu
)
224 p
->designated_root
= bpdu
->root
;
225 p
->designated_cost
= bpdu
->root_path_cost
;
226 p
->designated_bridge
= bpdu
->bridge_id
;
227 p
->designated_port
= bpdu
->port_id
;
228 p
->designated_age
= jiffies
- bpdu
->message_age
;
230 mod_timer(&p
->message_age_timer
, jiffies
231 + (bpdu
->max_age
- bpdu
->message_age
));
234 /* called under bridge lock */
235 static void br_record_config_timeout_values(struct net_bridge
*br
,
236 const struct br_config_bpdu
*bpdu
)
238 br
->max_age
= bpdu
->max_age
;
239 br
->hello_time
= bpdu
->hello_time
;
240 br
->forward_delay
= bpdu
->forward_delay
;
241 br
->topology_change
= bpdu
->topology_change
;
244 /* called under bridge lock */
245 void br_transmit_tcn(struct net_bridge
*br
)
247 struct net_bridge_port
*p
;
249 p
= br_get_port(br
, br
->root_port
);
253 br_notice(br
, "root port %u not found for topology notice\n",
257 /* called under bridge lock */
258 static int br_should_become_designated_port(const struct net_bridge_port
*p
)
260 struct net_bridge
*br
;
264 if (br_is_designated_port(p
))
267 if (memcmp(&p
->designated_root
, &br
->designated_root
, 8))
270 if (br
->root_path_cost
< p
->designated_cost
)
272 else if (br
->root_path_cost
> p
->designated_cost
)
275 t
= memcmp(&br
->bridge_id
, &p
->designated_bridge
, 8);
281 if (p
->port_id
< p
->designated_port
)
287 /* called under bridge lock */
288 static void br_designated_port_selection(struct net_bridge
*br
)
290 struct net_bridge_port
*p
;
292 list_for_each_entry(p
, &br
->port_list
, list
) {
293 if (p
->state
!= BR_STATE_DISABLED
&&
294 br_should_become_designated_port(p
))
295 br_become_designated_port(p
);
300 /* called under bridge lock */
301 static int br_supersedes_port_info(const struct net_bridge_port
*p
,
302 const struct br_config_bpdu
*bpdu
)
306 t
= memcmp(&bpdu
->root
, &p
->designated_root
, 8);
312 if (bpdu
->root_path_cost
< p
->designated_cost
)
314 else if (bpdu
->root_path_cost
> p
->designated_cost
)
317 t
= memcmp(&bpdu
->bridge_id
, &p
->designated_bridge
, 8);
323 if (memcmp(&bpdu
->bridge_id
, &p
->br
->bridge_id
, 8))
326 if (bpdu
->port_id
<= p
->designated_port
)
332 /* called under bridge lock */
333 static void br_topology_change_acknowledged(struct net_bridge
*br
)
335 br
->topology_change_detected
= 0;
336 del_timer(&br
->tcn_timer
);
339 /* called under bridge lock */
340 void br_topology_change_detection(struct net_bridge
*br
)
342 int isroot
= br_is_root_bridge(br
);
344 if (br
->stp_enabled
!= BR_KERNEL_STP
)
347 br_info(br
, "topology change detected, %s\n",
348 isroot
? "propagating" : "sending tcn bpdu");
351 br
->topology_change
= 1;
352 mod_timer(&br
->topology_change_timer
, jiffies
353 + br
->bridge_forward_delay
+ br
->bridge_max_age
);
354 } else if (!br
->topology_change_detected
) {
356 mod_timer(&br
->tcn_timer
, jiffies
+ br
->bridge_hello_time
);
359 br
->topology_change_detected
= 1;
362 /* called under bridge lock */
363 void br_config_bpdu_generation(struct net_bridge
*br
)
365 struct net_bridge_port
*p
;
367 list_for_each_entry(p
, &br
->port_list
, list
) {
368 if (p
->state
!= BR_STATE_DISABLED
&&
369 br_is_designated_port(p
))
370 br_transmit_config(p
);
374 /* called under bridge lock */
375 static void br_reply(struct net_bridge_port
*p
)
377 br_transmit_config(p
);
380 /* called under bridge lock */
381 void br_configuration_update(struct net_bridge
*br
)
383 br_root_selection(br
);
384 br_designated_port_selection(br
);
387 /* called under bridge lock */
388 void br_become_designated_port(struct net_bridge_port
*p
)
390 struct net_bridge
*br
;
393 p
->designated_root
= br
->designated_root
;
394 p
->designated_cost
= br
->root_path_cost
;
395 p
->designated_bridge
= br
->bridge_id
;
396 p
->designated_port
= p
->port_id
;
400 /* called under bridge lock */
401 static void br_make_blocking(struct net_bridge_port
*p
)
403 if (p
->state
!= BR_STATE_DISABLED
&&
404 p
->state
!= BR_STATE_BLOCKING
) {
405 if (p
->state
== BR_STATE_FORWARDING
||
406 p
->state
== BR_STATE_LEARNING
)
407 br_topology_change_detection(p
->br
);
409 br_set_state(p
, BR_STATE_BLOCKING
);
411 br_ifinfo_notify(RTM_NEWLINK
, p
);
413 del_timer(&p
->forward_delay_timer
);
417 /* called under bridge lock */
418 static void br_make_forwarding(struct net_bridge_port
*p
)
420 struct net_bridge
*br
= p
->br
;
422 if (p
->state
!= BR_STATE_BLOCKING
)
425 if (br
->stp_enabled
== BR_NO_STP
|| br
->forward_delay
== 0) {
426 br_set_state(p
, BR_STATE_FORWARDING
);
427 br_topology_change_detection(br
);
428 del_timer(&p
->forward_delay_timer
);
429 } else if (br
->stp_enabled
== BR_KERNEL_STP
)
430 br_set_state(p
, BR_STATE_LISTENING
);
432 br_set_state(p
, BR_STATE_LEARNING
);
435 br_ifinfo_notify(RTM_NEWLINK
, p
);
437 if (br
->forward_delay
!= 0)
438 mod_timer(&p
->forward_delay_timer
, jiffies
+ br
->forward_delay
);
441 /* called under bridge lock */
442 void br_port_state_selection(struct net_bridge
*br
)
444 struct net_bridge_port
*p
;
445 unsigned int liveports
= 0;
447 list_for_each_entry(p
, &br
->port_list
, list
) {
448 if (p
->state
== BR_STATE_DISABLED
)
451 /* Don't change port states if userspace is handling STP */
452 if (br
->stp_enabled
!= BR_USER_STP
) {
453 if (p
->port_no
== br
->root_port
) {
454 p
->config_pending
= 0;
455 p
->topology_change_ack
= 0;
456 br_make_forwarding(p
);
457 } else if (br_is_designated_port(p
)) {
458 del_timer(&p
->message_age_timer
);
459 br_make_forwarding(p
);
461 p
->config_pending
= 0;
462 p
->topology_change_ack
= 0;
467 if (p
->state
!= BR_STATE_BLOCKING
)
468 br_multicast_enable_port(p
);
469 /* Multicast is not disabled for the port when it goes in
470 * blocking state because the timers will expire and stop by
471 * themselves without sending more queries.
473 if (p
->state
== BR_STATE_FORWARDING
)
478 netif_carrier_off(br
->dev
);
480 netif_carrier_on(br
->dev
);
483 /* called under bridge lock */
484 static void br_topology_change_acknowledge(struct net_bridge_port
*p
)
486 p
->topology_change_ack
= 1;
487 br_transmit_config(p
);
490 /* called under bridge lock */
491 void br_received_config_bpdu(struct net_bridge_port
*p
,
492 const struct br_config_bpdu
*bpdu
)
494 struct net_bridge
*br
;
498 was_root
= br_is_root_bridge(br
);
500 if (br_supersedes_port_info(p
, bpdu
)) {
501 br_record_config_information(p
, bpdu
);
502 br_configuration_update(br
);
503 br_port_state_selection(br
);
505 if (!br_is_root_bridge(br
) && was_root
) {
506 del_timer(&br
->hello_timer
);
507 if (br
->topology_change_detected
) {
508 del_timer(&br
->topology_change_timer
);
511 mod_timer(&br
->tcn_timer
,
512 jiffies
+ br
->bridge_hello_time
);
516 if (p
->port_no
== br
->root_port
) {
517 br_record_config_timeout_values(br
, bpdu
);
518 br_config_bpdu_generation(br
);
519 if (bpdu
->topology_change_ack
)
520 br_topology_change_acknowledged(br
);
522 } else if (br_is_designated_port(p
)) {
527 /* called under bridge lock */
528 void br_received_tcn_bpdu(struct net_bridge_port
*p
)
530 if (br_is_designated_port(p
)) {
531 br_info(p
->br
, "port %u(%s) received tcn bpdu\n",
532 (unsigned int) p
->port_no
, p
->dev
->name
);
534 br_topology_change_detection(p
->br
);
535 br_topology_change_acknowledge(p
);
539 /* Change bridge STP parameter */
540 int br_set_hello_time(struct net_bridge
*br
, unsigned long val
)
542 unsigned long t
= clock_t_to_jiffies(val
);
544 if (t
< BR_MIN_HELLO_TIME
|| t
> BR_MAX_HELLO_TIME
)
547 spin_lock_bh(&br
->lock
);
548 br
->bridge_hello_time
= t
;
549 if (br_is_root_bridge(br
))
550 br
->hello_time
= br
->bridge_hello_time
;
551 spin_unlock_bh(&br
->lock
);
555 int br_set_max_age(struct net_bridge
*br
, unsigned long val
)
557 unsigned long t
= clock_t_to_jiffies(val
);
559 if (t
< BR_MIN_MAX_AGE
|| t
> BR_MAX_MAX_AGE
)
562 spin_lock_bh(&br
->lock
);
563 br
->bridge_max_age
= t
;
564 if (br_is_root_bridge(br
))
565 br
->max_age
= br
->bridge_max_age
;
566 spin_unlock_bh(&br
->lock
);
571 int br_set_ageing_time(struct net_bridge
*br
, u32 ageing_time
)
573 struct switchdev_attr attr
= {
575 .id
= SWITCHDEV_ATTR_ID_BRIDGE_AGEING_TIME
,
576 .flags
= SWITCHDEV_F_SKIP_EOPNOTSUPP
,
577 .u
.ageing_time
= ageing_time
,
579 unsigned long t
= clock_t_to_jiffies(ageing_time
);
582 if (t
< BR_MIN_AGEING_TIME
|| t
> BR_MAX_AGEING_TIME
)
585 err
= switchdev_port_attr_set(br
->dev
, &attr
);
590 mod_timer(&br
->gc_timer
, jiffies
);
595 void __br_set_forward_delay(struct net_bridge
*br
, unsigned long t
)
597 br
->bridge_forward_delay
= t
;
598 if (br_is_root_bridge(br
))
599 br
->forward_delay
= br
->bridge_forward_delay
;
602 int br_set_forward_delay(struct net_bridge
*br
, unsigned long val
)
604 unsigned long t
= clock_t_to_jiffies(val
);
607 spin_lock_bh(&br
->lock
);
608 if (br
->stp_enabled
!= BR_NO_STP
&&
609 (t
< BR_MIN_FORWARD_DELAY
|| t
> BR_MAX_FORWARD_DELAY
))
612 __br_set_forward_delay(br
, t
);
616 spin_unlock_bh(&br
->lock
);