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>
16 #include "br_private.h"
17 #include "br_private_stp.h"
19 /* since time values in bpdu are in jiffies and then scaled (1/256)
20 * before sending, make sure that is at least one STP tick.
22 #define MESSAGE_AGE_INCR ((HZ / 256) + 1)
24 static const char *const br_port_state_names
[] = {
25 [BR_STATE_DISABLED
] = "disabled",
26 [BR_STATE_LISTENING
] = "listening",
27 [BR_STATE_LEARNING
] = "learning",
28 [BR_STATE_FORWARDING
] = "forwarding",
29 [BR_STATE_BLOCKING
] = "blocking",
32 void br_log_state(const struct net_bridge_port
*p
)
34 br_info(p
->br
, "port %u(%s) entered %s state\n",
35 (unsigned int) p
->port_no
, p
->dev
->name
,
36 br_port_state_names
[p
->state
]);
39 void br_set_state(struct net_bridge_port
*p
, unsigned int state
)
44 /* called under bridge lock */
45 struct net_bridge_port
*br_get_port(struct net_bridge
*br
, u16 port_no
)
47 struct net_bridge_port
*p
;
49 list_for_each_entry_rcu(p
, &br
->port_list
, list
) {
50 if (p
->port_no
== port_no
)
57 /* called under bridge lock */
58 static int br_should_become_root_port(const struct net_bridge_port
*p
,
61 struct net_bridge
*br
;
62 struct net_bridge_port
*rp
;
66 if (p
->state
== BR_STATE_DISABLED
||
67 br_is_designated_port(p
))
70 if (memcmp(&br
->bridge_id
, &p
->designated_root
, 8) <= 0)
76 rp
= br_get_port(br
, root_port
);
78 t
= memcmp(&p
->designated_root
, &rp
->designated_root
, 8);
84 if (p
->designated_cost
+ p
->path_cost
<
85 rp
->designated_cost
+ rp
->path_cost
)
87 else if (p
->designated_cost
+ p
->path_cost
>
88 rp
->designated_cost
+ rp
->path_cost
)
91 t
= memcmp(&p
->designated_bridge
, &rp
->designated_bridge
, 8);
97 if (p
->designated_port
< rp
->designated_port
)
99 else if (p
->designated_port
> rp
->designated_port
)
102 if (p
->port_id
< rp
->port_id
)
108 static void br_root_port_block(const struct net_bridge
*br
,
109 struct net_bridge_port
*p
)
112 br_notice(br
, "port %u(%s) tried to become root port (blocked)",
113 (unsigned int) p
->port_no
, p
->dev
->name
);
115 br_set_state(p
, BR_STATE_LISTENING
);
117 br_ifinfo_notify(RTM_NEWLINK
, p
);
119 if (br
->forward_delay
> 0)
120 mod_timer(&p
->forward_delay_timer
, jiffies
+ br
->forward_delay
);
123 /* called under bridge lock */
124 static void br_root_selection(struct net_bridge
*br
)
126 struct net_bridge_port
*p
;
129 list_for_each_entry(p
, &br
->port_list
, list
) {
130 if (!br_should_become_root_port(p
, root_port
))
133 if (p
->flags
& BR_ROOT_BLOCK
)
134 br_root_port_block(br
, p
);
136 root_port
= p
->port_no
;
139 br
->root_port
= root_port
;
142 br
->designated_root
= br
->bridge_id
;
143 br
->root_path_cost
= 0;
145 p
= br_get_port(br
, root_port
);
146 br
->designated_root
= p
->designated_root
;
147 br
->root_path_cost
= p
->designated_cost
+ p
->path_cost
;
151 /* called under bridge lock */
152 void br_become_root_bridge(struct net_bridge
*br
)
154 br
->max_age
= br
->bridge_max_age
;
155 br
->hello_time
= br
->bridge_hello_time
;
156 br
->forward_delay
= br
->bridge_forward_delay
;
157 br_topology_change_detection(br
);
158 del_timer(&br
->tcn_timer
);
160 if (br
->dev
->flags
& IFF_UP
) {
161 br_config_bpdu_generation(br
);
162 mod_timer(&br
->hello_timer
, jiffies
+ br
->hello_time
);
166 /* called under bridge lock */
167 void br_transmit_config(struct net_bridge_port
*p
)
169 struct br_config_bpdu bpdu
;
170 struct net_bridge
*br
;
172 if (timer_pending(&p
->hold_timer
)) {
173 p
->config_pending
= 1;
179 bpdu
.topology_change
= br
->topology_change
;
180 bpdu
.topology_change_ack
= p
->topology_change_ack
;
181 bpdu
.root
= br
->designated_root
;
182 bpdu
.root_path_cost
= br
->root_path_cost
;
183 bpdu
.bridge_id
= br
->bridge_id
;
184 bpdu
.port_id
= p
->port_id
;
185 if (br_is_root_bridge(br
))
186 bpdu
.message_age
= 0;
188 struct net_bridge_port
*root
189 = br_get_port(br
, br
->root_port
);
190 bpdu
.message_age
= (jiffies
- root
->designated_age
)
193 bpdu
.max_age
= br
->max_age
;
194 bpdu
.hello_time
= br
->hello_time
;
195 bpdu
.forward_delay
= br
->forward_delay
;
197 if (bpdu
.message_age
< br
->max_age
) {
198 br_send_config_bpdu(p
, &bpdu
);
199 p
->topology_change_ack
= 0;
200 p
->config_pending
= 0;
201 mod_timer(&p
->hold_timer
,
202 round_jiffies(jiffies
+ BR_HOLD_TIME
));
206 /* called under bridge lock */
207 static void br_record_config_information(struct net_bridge_port
*p
,
208 const struct br_config_bpdu
*bpdu
)
210 p
->designated_root
= bpdu
->root
;
211 p
->designated_cost
= bpdu
->root_path_cost
;
212 p
->designated_bridge
= bpdu
->bridge_id
;
213 p
->designated_port
= bpdu
->port_id
;
214 p
->designated_age
= jiffies
- bpdu
->message_age
;
216 mod_timer(&p
->message_age_timer
, jiffies
217 + (bpdu
->max_age
- bpdu
->message_age
));
220 /* called under bridge lock */
221 static void br_record_config_timeout_values(struct net_bridge
*br
,
222 const struct br_config_bpdu
*bpdu
)
224 br
->max_age
= bpdu
->max_age
;
225 br
->hello_time
= bpdu
->hello_time
;
226 br
->forward_delay
= bpdu
->forward_delay
;
227 br
->topology_change
= bpdu
->topology_change
;
230 /* called under bridge lock */
231 void br_transmit_tcn(struct net_bridge
*br
)
233 struct net_bridge_port
*p
;
235 p
= br_get_port(br
, br
->root_port
);
239 br_notice(br
, "root port %u not found for topology notice\n",
243 /* called under bridge lock */
244 static int br_should_become_designated_port(const struct net_bridge_port
*p
)
246 struct net_bridge
*br
;
250 if (br_is_designated_port(p
))
253 if (memcmp(&p
->designated_root
, &br
->designated_root
, 8))
256 if (br
->root_path_cost
< p
->designated_cost
)
258 else if (br
->root_path_cost
> p
->designated_cost
)
261 t
= memcmp(&br
->bridge_id
, &p
->designated_bridge
, 8);
267 if (p
->port_id
< p
->designated_port
)
273 /* called under bridge lock */
274 static void br_designated_port_selection(struct net_bridge
*br
)
276 struct net_bridge_port
*p
;
278 list_for_each_entry(p
, &br
->port_list
, list
) {
279 if (p
->state
!= BR_STATE_DISABLED
&&
280 br_should_become_designated_port(p
))
281 br_become_designated_port(p
);
286 /* called under bridge lock */
287 static int br_supersedes_port_info(const struct net_bridge_port
*p
,
288 const struct br_config_bpdu
*bpdu
)
292 t
= memcmp(&bpdu
->root
, &p
->designated_root
, 8);
298 if (bpdu
->root_path_cost
< p
->designated_cost
)
300 else if (bpdu
->root_path_cost
> p
->designated_cost
)
303 t
= memcmp(&bpdu
->bridge_id
, &p
->designated_bridge
, 8);
309 if (memcmp(&bpdu
->bridge_id
, &p
->br
->bridge_id
, 8))
312 if (bpdu
->port_id
<= p
->designated_port
)
318 /* called under bridge lock */
319 static void br_topology_change_acknowledged(struct net_bridge
*br
)
321 br
->topology_change_detected
= 0;
322 del_timer(&br
->tcn_timer
);
325 /* called under bridge lock */
326 void br_topology_change_detection(struct net_bridge
*br
)
328 int isroot
= br_is_root_bridge(br
);
330 if (br
->stp_enabled
!= BR_KERNEL_STP
)
333 br_info(br
, "topology change detected, %s\n",
334 isroot
? "propagating" : "sending tcn bpdu");
337 br
->topology_change
= 1;
338 mod_timer(&br
->topology_change_timer
, jiffies
339 + br
->bridge_forward_delay
+ br
->bridge_max_age
);
340 } else if (!br
->topology_change_detected
) {
342 mod_timer(&br
->tcn_timer
, jiffies
+ br
->bridge_hello_time
);
345 br
->topology_change_detected
= 1;
348 /* called under bridge lock */
349 void br_config_bpdu_generation(struct net_bridge
*br
)
351 struct net_bridge_port
*p
;
353 list_for_each_entry(p
, &br
->port_list
, list
) {
354 if (p
->state
!= BR_STATE_DISABLED
&&
355 br_is_designated_port(p
))
356 br_transmit_config(p
);
360 /* called under bridge lock */
361 static void br_reply(struct net_bridge_port
*p
)
363 br_transmit_config(p
);
366 /* called under bridge lock */
367 void br_configuration_update(struct net_bridge
*br
)
369 br_root_selection(br
);
370 br_designated_port_selection(br
);
373 /* called under bridge lock */
374 void br_become_designated_port(struct net_bridge_port
*p
)
376 struct net_bridge
*br
;
379 p
->designated_root
= br
->designated_root
;
380 p
->designated_cost
= br
->root_path_cost
;
381 p
->designated_bridge
= br
->bridge_id
;
382 p
->designated_port
= p
->port_id
;
386 /* called under bridge lock */
387 static void br_make_blocking(struct net_bridge_port
*p
)
389 if (p
->state
!= BR_STATE_DISABLED
&&
390 p
->state
!= BR_STATE_BLOCKING
) {
391 if (p
->state
== BR_STATE_FORWARDING
||
392 p
->state
== BR_STATE_LEARNING
)
393 br_topology_change_detection(p
->br
);
395 br_set_state(p
, BR_STATE_BLOCKING
);
397 br_ifinfo_notify(RTM_NEWLINK
, p
);
399 del_timer(&p
->forward_delay_timer
);
403 /* called under bridge lock */
404 static void br_make_forwarding(struct net_bridge_port
*p
)
406 struct net_bridge
*br
= p
->br
;
408 if (p
->state
!= BR_STATE_BLOCKING
)
411 if (br
->stp_enabled
== BR_NO_STP
|| br
->forward_delay
== 0) {
412 br_set_state(p
, BR_STATE_FORWARDING
);
413 br_topology_change_detection(br
);
414 del_timer(&p
->forward_delay_timer
);
415 } else if (br
->stp_enabled
== BR_KERNEL_STP
)
416 br_set_state(p
, BR_STATE_LISTENING
);
418 br_set_state(p
, BR_STATE_LEARNING
);
420 br_multicast_enable_port(p
);
422 br_ifinfo_notify(RTM_NEWLINK
, p
);
424 if (br
->forward_delay
!= 0)
425 mod_timer(&p
->forward_delay_timer
, jiffies
+ br
->forward_delay
);
428 /* called under bridge lock */
429 void br_port_state_selection(struct net_bridge
*br
)
431 struct net_bridge_port
*p
;
432 unsigned int liveports
= 0;
434 list_for_each_entry(p
, &br
->port_list
, list
) {
435 if (p
->state
== BR_STATE_DISABLED
)
438 /* Don't change port states if userspace is handling STP */
439 if (br
->stp_enabled
!= BR_USER_STP
) {
440 if (p
->port_no
== br
->root_port
) {
441 p
->config_pending
= 0;
442 p
->topology_change_ack
= 0;
443 br_make_forwarding(p
);
444 } else if (br_is_designated_port(p
)) {
445 del_timer(&p
->message_age_timer
);
446 br_make_forwarding(p
);
448 p
->config_pending
= 0;
449 p
->topology_change_ack
= 0;
454 if (p
->state
== BR_STATE_FORWARDING
)
459 netif_carrier_off(br
->dev
);
461 netif_carrier_on(br
->dev
);
464 /* called under bridge lock */
465 static void br_topology_change_acknowledge(struct net_bridge_port
*p
)
467 p
->topology_change_ack
= 1;
468 br_transmit_config(p
);
471 /* called under bridge lock */
472 void br_received_config_bpdu(struct net_bridge_port
*p
,
473 const struct br_config_bpdu
*bpdu
)
475 struct net_bridge
*br
;
479 was_root
= br_is_root_bridge(br
);
481 if (br_supersedes_port_info(p
, bpdu
)) {
482 br_record_config_information(p
, bpdu
);
483 br_configuration_update(br
);
484 br_port_state_selection(br
);
486 if (!br_is_root_bridge(br
) && was_root
) {
487 del_timer(&br
->hello_timer
);
488 if (br
->topology_change_detected
) {
489 del_timer(&br
->topology_change_timer
);
492 mod_timer(&br
->tcn_timer
,
493 jiffies
+ br
->bridge_hello_time
);
497 if (p
->port_no
== br
->root_port
) {
498 br_record_config_timeout_values(br
, bpdu
);
499 br_config_bpdu_generation(br
);
500 if (bpdu
->topology_change_ack
)
501 br_topology_change_acknowledged(br
);
503 } else if (br_is_designated_port(p
)) {
508 /* called under bridge lock */
509 void br_received_tcn_bpdu(struct net_bridge_port
*p
)
511 if (br_is_designated_port(p
)) {
512 br_info(p
->br
, "port %u(%s) received tcn bpdu\n",
513 (unsigned int) p
->port_no
, p
->dev
->name
);
515 br_topology_change_detection(p
->br
);
516 br_topology_change_acknowledge(p
);
520 /* Change bridge STP parameter */
521 int br_set_hello_time(struct net_bridge
*br
, unsigned long val
)
523 unsigned long t
= clock_t_to_jiffies(val
);
525 if (t
< BR_MIN_HELLO_TIME
|| t
> BR_MAX_HELLO_TIME
)
528 spin_lock_bh(&br
->lock
);
529 br
->bridge_hello_time
= t
;
530 if (br_is_root_bridge(br
))
531 br
->hello_time
= br
->bridge_hello_time
;
532 spin_unlock_bh(&br
->lock
);
536 int br_set_max_age(struct net_bridge
*br
, unsigned long val
)
538 unsigned long t
= clock_t_to_jiffies(val
);
540 if (t
< BR_MIN_MAX_AGE
|| t
> BR_MAX_MAX_AGE
)
543 spin_lock_bh(&br
->lock
);
544 br
->bridge_max_age
= t
;
545 if (br_is_root_bridge(br
))
546 br
->max_age
= br
->bridge_max_age
;
547 spin_unlock_bh(&br
->lock
);
552 void __br_set_forward_delay(struct net_bridge
*br
, unsigned long t
)
554 br
->bridge_forward_delay
= t
;
555 if (br_is_root_bridge(br
))
556 br
->forward_delay
= br
->bridge_forward_delay
;
559 int br_set_forward_delay(struct net_bridge
*br
, unsigned long val
)
561 unsigned long t
= clock_t_to_jiffies(val
);
564 spin_lock_bh(&br
->lock
);
565 if (br
->stp_enabled
!= BR_NO_STP
&&
566 (t
< BR_MIN_FORWARD_DELAY
|| t
> BR_MAX_FORWARD_DELAY
))
569 __br_set_forward_delay(br
, t
);
573 spin_unlock_bh(&br
->lock
);
This page took 0.071369 seconds and 5 git commands to generate.