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
= {
43 .id
= SWITCHDEV_ATTR_PORT_STP_STATE
,
49 err
= switchdev_port_attr_set(p
->dev
, &attr
);
50 if (err
&& err
!= -EOPNOTSUPP
)
51 br_warn(p
->br
, "error setting offload STP state on port %u(%s)\n",
52 (unsigned int) p
->port_no
, p
->dev
->name
);
55 /* called under bridge lock */
56 struct net_bridge_port
*br_get_port(struct net_bridge
*br
, u16 port_no
)
58 struct net_bridge_port
*p
;
60 list_for_each_entry_rcu(p
, &br
->port_list
, list
) {
61 if (p
->port_no
== port_no
)
68 /* called under bridge lock */
69 static int br_should_become_root_port(const struct net_bridge_port
*p
,
72 struct net_bridge
*br
;
73 struct net_bridge_port
*rp
;
77 if (p
->state
== BR_STATE_DISABLED
||
78 br_is_designated_port(p
))
81 if (memcmp(&br
->bridge_id
, &p
->designated_root
, 8) <= 0)
87 rp
= br_get_port(br
, root_port
);
89 t
= memcmp(&p
->designated_root
, &rp
->designated_root
, 8);
95 if (p
->designated_cost
+ p
->path_cost
<
96 rp
->designated_cost
+ rp
->path_cost
)
98 else if (p
->designated_cost
+ p
->path_cost
>
99 rp
->designated_cost
+ rp
->path_cost
)
102 t
= memcmp(&p
->designated_bridge
, &rp
->designated_bridge
, 8);
108 if (p
->designated_port
< rp
->designated_port
)
110 else if (p
->designated_port
> rp
->designated_port
)
113 if (p
->port_id
< rp
->port_id
)
119 static void br_root_port_block(const struct net_bridge
*br
,
120 struct net_bridge_port
*p
)
123 br_notice(br
, "port %u(%s) tried to become root port (blocked)",
124 (unsigned int) p
->port_no
, p
->dev
->name
);
126 br_set_state(p
, BR_STATE_LISTENING
);
128 br_ifinfo_notify(RTM_NEWLINK
, p
);
130 if (br
->forward_delay
> 0)
131 mod_timer(&p
->forward_delay_timer
, jiffies
+ br
->forward_delay
);
134 /* called under bridge lock */
135 static void br_root_selection(struct net_bridge
*br
)
137 struct net_bridge_port
*p
;
140 list_for_each_entry(p
, &br
->port_list
, list
) {
141 if (!br_should_become_root_port(p
, root_port
))
144 if (p
->flags
& BR_ROOT_BLOCK
)
145 br_root_port_block(br
, p
);
147 root_port
= p
->port_no
;
150 br
->root_port
= root_port
;
153 br
->designated_root
= br
->bridge_id
;
154 br
->root_path_cost
= 0;
156 p
= br_get_port(br
, root_port
);
157 br
->designated_root
= p
->designated_root
;
158 br
->root_path_cost
= p
->designated_cost
+ p
->path_cost
;
162 /* called under bridge lock */
163 void br_become_root_bridge(struct net_bridge
*br
)
165 br
->max_age
= br
->bridge_max_age
;
166 br
->hello_time
= br
->bridge_hello_time
;
167 br
->forward_delay
= br
->bridge_forward_delay
;
168 br_topology_change_detection(br
);
169 del_timer(&br
->tcn_timer
);
171 if (br
->dev
->flags
& IFF_UP
) {
172 br_config_bpdu_generation(br
);
173 mod_timer(&br
->hello_timer
, jiffies
+ br
->hello_time
);
177 /* called under bridge lock */
178 void br_transmit_config(struct net_bridge_port
*p
)
180 struct br_config_bpdu bpdu
;
181 struct net_bridge
*br
;
183 if (timer_pending(&p
->hold_timer
)) {
184 p
->config_pending
= 1;
190 bpdu
.topology_change
= br
->topology_change
;
191 bpdu
.topology_change_ack
= p
->topology_change_ack
;
192 bpdu
.root
= br
->designated_root
;
193 bpdu
.root_path_cost
= br
->root_path_cost
;
194 bpdu
.bridge_id
= br
->bridge_id
;
195 bpdu
.port_id
= p
->port_id
;
196 if (br_is_root_bridge(br
))
197 bpdu
.message_age
= 0;
199 struct net_bridge_port
*root
200 = br_get_port(br
, br
->root_port
);
201 bpdu
.message_age
= (jiffies
- root
->designated_age
)
204 bpdu
.max_age
= br
->max_age
;
205 bpdu
.hello_time
= br
->hello_time
;
206 bpdu
.forward_delay
= br
->forward_delay
;
208 if (bpdu
.message_age
< br
->max_age
) {
209 br_send_config_bpdu(p
, &bpdu
);
210 p
->topology_change_ack
= 0;
211 p
->config_pending
= 0;
212 mod_timer(&p
->hold_timer
,
213 round_jiffies(jiffies
+ BR_HOLD_TIME
));
217 /* called under bridge lock */
218 static void br_record_config_information(struct net_bridge_port
*p
,
219 const struct br_config_bpdu
*bpdu
)
221 p
->designated_root
= bpdu
->root
;
222 p
->designated_cost
= bpdu
->root_path_cost
;
223 p
->designated_bridge
= bpdu
->bridge_id
;
224 p
->designated_port
= bpdu
->port_id
;
225 p
->designated_age
= jiffies
- bpdu
->message_age
;
227 mod_timer(&p
->message_age_timer
, jiffies
228 + (bpdu
->max_age
- bpdu
->message_age
));
231 /* called under bridge lock */
232 static void br_record_config_timeout_values(struct net_bridge
*br
,
233 const struct br_config_bpdu
*bpdu
)
235 br
->max_age
= bpdu
->max_age
;
236 br
->hello_time
= bpdu
->hello_time
;
237 br
->forward_delay
= bpdu
->forward_delay
;
238 br
->topology_change
= bpdu
->topology_change
;
241 /* called under bridge lock */
242 void br_transmit_tcn(struct net_bridge
*br
)
244 struct net_bridge_port
*p
;
246 p
= br_get_port(br
, br
->root_port
);
250 br_notice(br
, "root port %u not found for topology notice\n",
254 /* called under bridge lock */
255 static int br_should_become_designated_port(const struct net_bridge_port
*p
)
257 struct net_bridge
*br
;
261 if (br_is_designated_port(p
))
264 if (memcmp(&p
->designated_root
, &br
->designated_root
, 8))
267 if (br
->root_path_cost
< p
->designated_cost
)
269 else if (br
->root_path_cost
> p
->designated_cost
)
272 t
= memcmp(&br
->bridge_id
, &p
->designated_bridge
, 8);
278 if (p
->port_id
< p
->designated_port
)
284 /* called under bridge lock */
285 static void br_designated_port_selection(struct net_bridge
*br
)
287 struct net_bridge_port
*p
;
289 list_for_each_entry(p
, &br
->port_list
, list
) {
290 if (p
->state
!= BR_STATE_DISABLED
&&
291 br_should_become_designated_port(p
))
292 br_become_designated_port(p
);
297 /* called under bridge lock */
298 static int br_supersedes_port_info(const struct net_bridge_port
*p
,
299 const struct br_config_bpdu
*bpdu
)
303 t
= memcmp(&bpdu
->root
, &p
->designated_root
, 8);
309 if (bpdu
->root_path_cost
< p
->designated_cost
)
311 else if (bpdu
->root_path_cost
> p
->designated_cost
)
314 t
= memcmp(&bpdu
->bridge_id
, &p
->designated_bridge
, 8);
320 if (memcmp(&bpdu
->bridge_id
, &p
->br
->bridge_id
, 8))
323 if (bpdu
->port_id
<= p
->designated_port
)
329 /* called under bridge lock */
330 static void br_topology_change_acknowledged(struct net_bridge
*br
)
332 br
->topology_change_detected
= 0;
333 del_timer(&br
->tcn_timer
);
336 /* called under bridge lock */
337 void br_topology_change_detection(struct net_bridge
*br
)
339 int isroot
= br_is_root_bridge(br
);
341 if (br
->stp_enabled
!= BR_KERNEL_STP
)
344 br_info(br
, "topology change detected, %s\n",
345 isroot
? "propagating" : "sending tcn bpdu");
348 br
->topology_change
= 1;
349 mod_timer(&br
->topology_change_timer
, jiffies
350 + br
->bridge_forward_delay
+ br
->bridge_max_age
);
351 } else if (!br
->topology_change_detected
) {
353 mod_timer(&br
->tcn_timer
, jiffies
+ br
->bridge_hello_time
);
356 br
->topology_change_detected
= 1;
359 /* called under bridge lock */
360 void br_config_bpdu_generation(struct net_bridge
*br
)
362 struct net_bridge_port
*p
;
364 list_for_each_entry(p
, &br
->port_list
, list
) {
365 if (p
->state
!= BR_STATE_DISABLED
&&
366 br_is_designated_port(p
))
367 br_transmit_config(p
);
371 /* called under bridge lock */
372 static void br_reply(struct net_bridge_port
*p
)
374 br_transmit_config(p
);
377 /* called under bridge lock */
378 void br_configuration_update(struct net_bridge
*br
)
380 br_root_selection(br
);
381 br_designated_port_selection(br
);
384 /* called under bridge lock */
385 void br_become_designated_port(struct net_bridge_port
*p
)
387 struct net_bridge
*br
;
390 p
->designated_root
= br
->designated_root
;
391 p
->designated_cost
= br
->root_path_cost
;
392 p
->designated_bridge
= br
->bridge_id
;
393 p
->designated_port
= p
->port_id
;
397 /* called under bridge lock */
398 static void br_make_blocking(struct net_bridge_port
*p
)
400 if (p
->state
!= BR_STATE_DISABLED
&&
401 p
->state
!= BR_STATE_BLOCKING
) {
402 if (p
->state
== BR_STATE_FORWARDING
||
403 p
->state
== BR_STATE_LEARNING
)
404 br_topology_change_detection(p
->br
);
406 br_set_state(p
, BR_STATE_BLOCKING
);
408 br_ifinfo_notify(RTM_NEWLINK
, p
);
410 del_timer(&p
->forward_delay_timer
);
414 /* called under bridge lock */
415 static void br_make_forwarding(struct net_bridge_port
*p
)
417 struct net_bridge
*br
= p
->br
;
419 if (p
->state
!= BR_STATE_BLOCKING
)
422 if (br
->stp_enabled
== BR_NO_STP
|| br
->forward_delay
== 0) {
423 br_set_state(p
, BR_STATE_FORWARDING
);
424 br_topology_change_detection(br
);
425 del_timer(&p
->forward_delay_timer
);
426 } else if (br
->stp_enabled
== BR_KERNEL_STP
)
427 br_set_state(p
, BR_STATE_LISTENING
);
429 br_set_state(p
, BR_STATE_LEARNING
);
432 br_ifinfo_notify(RTM_NEWLINK
, p
);
434 if (br
->forward_delay
!= 0)
435 mod_timer(&p
->forward_delay_timer
, jiffies
+ br
->forward_delay
);
438 /* called under bridge lock */
439 void br_port_state_selection(struct net_bridge
*br
)
441 struct net_bridge_port
*p
;
442 unsigned int liveports
= 0;
444 list_for_each_entry(p
, &br
->port_list
, list
) {
445 if (p
->state
== BR_STATE_DISABLED
)
448 /* Don't change port states if userspace is handling STP */
449 if (br
->stp_enabled
!= BR_USER_STP
) {
450 if (p
->port_no
== br
->root_port
) {
451 p
->config_pending
= 0;
452 p
->topology_change_ack
= 0;
453 br_make_forwarding(p
);
454 } else if (br_is_designated_port(p
)) {
455 del_timer(&p
->message_age_timer
);
456 br_make_forwarding(p
);
458 p
->config_pending
= 0;
459 p
->topology_change_ack
= 0;
464 if (p
->state
!= BR_STATE_BLOCKING
)
465 br_multicast_enable_port(p
);
466 /* Multicast is not disabled for the port when it goes in
467 * blocking state because the timers will expire and stop by
468 * themselves without sending more queries.
470 if (p
->state
== BR_STATE_FORWARDING
)
475 netif_carrier_off(br
->dev
);
477 netif_carrier_on(br
->dev
);
480 /* called under bridge lock */
481 static void br_topology_change_acknowledge(struct net_bridge_port
*p
)
483 p
->topology_change_ack
= 1;
484 br_transmit_config(p
);
487 /* called under bridge lock */
488 void br_received_config_bpdu(struct net_bridge_port
*p
,
489 const struct br_config_bpdu
*bpdu
)
491 struct net_bridge
*br
;
495 was_root
= br_is_root_bridge(br
);
497 if (br_supersedes_port_info(p
, bpdu
)) {
498 br_record_config_information(p
, bpdu
);
499 br_configuration_update(br
);
500 br_port_state_selection(br
);
502 if (!br_is_root_bridge(br
) && was_root
) {
503 del_timer(&br
->hello_timer
);
504 if (br
->topology_change_detected
) {
505 del_timer(&br
->topology_change_timer
);
508 mod_timer(&br
->tcn_timer
,
509 jiffies
+ br
->bridge_hello_time
);
513 if (p
->port_no
== br
->root_port
) {
514 br_record_config_timeout_values(br
, bpdu
);
515 br_config_bpdu_generation(br
);
516 if (bpdu
->topology_change_ack
)
517 br_topology_change_acknowledged(br
);
519 } else if (br_is_designated_port(p
)) {
524 /* called under bridge lock */
525 void br_received_tcn_bpdu(struct net_bridge_port
*p
)
527 if (br_is_designated_port(p
)) {
528 br_info(p
->br
, "port %u(%s) received tcn bpdu\n",
529 (unsigned int) p
->port_no
, p
->dev
->name
);
531 br_topology_change_detection(p
->br
);
532 br_topology_change_acknowledge(p
);
536 /* Change bridge STP parameter */
537 int br_set_hello_time(struct net_bridge
*br
, unsigned long val
)
539 unsigned long t
= clock_t_to_jiffies(val
);
541 if (t
< BR_MIN_HELLO_TIME
|| t
> BR_MAX_HELLO_TIME
)
544 spin_lock_bh(&br
->lock
);
545 br
->bridge_hello_time
= t
;
546 if (br_is_root_bridge(br
))
547 br
->hello_time
= br
->bridge_hello_time
;
548 spin_unlock_bh(&br
->lock
);
552 int br_set_max_age(struct net_bridge
*br
, unsigned long val
)
554 unsigned long t
= clock_t_to_jiffies(val
);
556 if (t
< BR_MIN_MAX_AGE
|| t
> BR_MAX_MAX_AGE
)
559 spin_lock_bh(&br
->lock
);
560 br
->bridge_max_age
= t
;
561 if (br_is_root_bridge(br
))
562 br
->max_age
= br
->bridge_max_age
;
563 spin_unlock_bh(&br
->lock
);
568 void __br_set_forward_delay(struct net_bridge
*br
, unsigned long t
)
570 br
->bridge_forward_delay
= t
;
571 if (br_is_root_bridge(br
))
572 br
->forward_delay
= br
->bridge_forward_delay
;
575 int br_set_forward_delay(struct net_bridge
*br
, unsigned long val
)
577 unsigned long t
= clock_t_to_jiffies(val
);
580 spin_lock_bh(&br
->lock
);
581 if (br
->stp_enabled
!= BR_NO_STP
&&
582 (t
< BR_MIN_FORWARD_DELAY
|| t
> BR_MAX_FORWARD_DELAY
))
585 __br_set_forward_delay(br
, t
);
589 spin_unlock_bh(&br
->lock
);