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 /* called under bridge lock */
40 struct net_bridge_port
*br_get_port(struct net_bridge
*br
, u16 port_no
)
42 struct net_bridge_port
*p
;
44 list_for_each_entry_rcu(p
, &br
->port_list
, list
) {
45 if (p
->port_no
== port_no
)
52 /* called under bridge lock */
53 static int br_should_become_root_port(const struct net_bridge_port
*p
,
56 struct net_bridge
*br
;
57 struct net_bridge_port
*rp
;
61 if (p
->state
== BR_STATE_DISABLED
||
62 br_is_designated_port(p
))
65 if (memcmp(&br
->bridge_id
, &p
->designated_root
, 8) <= 0)
71 rp
= br_get_port(br
, root_port
);
73 t
= memcmp(&p
->designated_root
, &rp
->designated_root
, 8);
79 if (p
->designated_cost
+ p
->path_cost
<
80 rp
->designated_cost
+ rp
->path_cost
)
82 else if (p
->designated_cost
+ p
->path_cost
>
83 rp
->designated_cost
+ rp
->path_cost
)
86 t
= memcmp(&p
->designated_bridge
, &rp
->designated_bridge
, 8);
92 if (p
->designated_port
< rp
->designated_port
)
94 else if (p
->designated_port
> rp
->designated_port
)
97 if (p
->port_id
< rp
->port_id
)
103 static void br_root_port_block(const struct net_bridge
*br
,
104 struct net_bridge_port
*p
)
107 br_notice(br
, "port %u(%s) tried to become root port (blocked)",
108 (unsigned int) p
->port_no
, p
->dev
->name
);
110 p
->state
= BR_STATE_LISTENING
;
112 br_ifinfo_notify(RTM_NEWLINK
, p
);
114 if (br
->forward_delay
> 0)
115 mod_timer(&p
->forward_delay_timer
, jiffies
+ br
->forward_delay
);
118 /* called under bridge lock */
119 static void br_root_selection(struct net_bridge
*br
)
121 struct net_bridge_port
*p
;
124 list_for_each_entry(p
, &br
->port_list
, list
) {
125 if (!br_should_become_root_port(p
, root_port
))
128 if (p
->flags
& BR_ROOT_BLOCK
)
129 br_root_port_block(br
, p
);
131 root_port
= p
->port_no
;
134 br
->root_port
= root_port
;
137 br
->designated_root
= br
->bridge_id
;
138 br
->root_path_cost
= 0;
140 p
= br_get_port(br
, root_port
);
141 br
->designated_root
= p
->designated_root
;
142 br
->root_path_cost
= p
->designated_cost
+ p
->path_cost
;
146 /* called under bridge lock */
147 void br_become_root_bridge(struct net_bridge
*br
)
149 br
->max_age
= br
->bridge_max_age
;
150 br
->hello_time
= br
->bridge_hello_time
;
151 br
->forward_delay
= br
->bridge_forward_delay
;
152 br_topology_change_detection(br
);
153 del_timer(&br
->tcn_timer
);
155 if (br
->dev
->flags
& IFF_UP
) {
156 br_config_bpdu_generation(br
);
157 mod_timer(&br
->hello_timer
, jiffies
+ br
->hello_time
);
161 /* called under bridge lock */
162 void br_transmit_config(struct net_bridge_port
*p
)
164 struct br_config_bpdu bpdu
;
165 struct net_bridge
*br
;
167 if (timer_pending(&p
->hold_timer
)) {
168 p
->config_pending
= 1;
174 bpdu
.topology_change
= br
->topology_change
;
175 bpdu
.topology_change_ack
= p
->topology_change_ack
;
176 bpdu
.root
= br
->designated_root
;
177 bpdu
.root_path_cost
= br
->root_path_cost
;
178 bpdu
.bridge_id
= br
->bridge_id
;
179 bpdu
.port_id
= p
->port_id
;
180 if (br_is_root_bridge(br
))
181 bpdu
.message_age
= 0;
183 struct net_bridge_port
*root
184 = br_get_port(br
, br
->root_port
);
185 bpdu
.message_age
= (jiffies
- root
->designated_age
)
188 bpdu
.max_age
= br
->max_age
;
189 bpdu
.hello_time
= br
->hello_time
;
190 bpdu
.forward_delay
= br
->forward_delay
;
192 if (bpdu
.message_age
< br
->max_age
) {
193 br_send_config_bpdu(p
, &bpdu
);
194 p
->topology_change_ack
= 0;
195 p
->config_pending
= 0;
196 mod_timer(&p
->hold_timer
,
197 round_jiffies(jiffies
+ BR_HOLD_TIME
));
201 /* called under bridge lock */
202 static void br_record_config_information(struct net_bridge_port
*p
,
203 const struct br_config_bpdu
*bpdu
)
205 p
->designated_root
= bpdu
->root
;
206 p
->designated_cost
= bpdu
->root_path_cost
;
207 p
->designated_bridge
= bpdu
->bridge_id
;
208 p
->designated_port
= bpdu
->port_id
;
209 p
->designated_age
= jiffies
- bpdu
->message_age
;
211 mod_timer(&p
->message_age_timer
, jiffies
212 + (p
->br
->max_age
- bpdu
->message_age
));
215 /* called under bridge lock */
216 static void br_record_config_timeout_values(struct net_bridge
*br
,
217 const struct br_config_bpdu
*bpdu
)
219 br
->max_age
= bpdu
->max_age
;
220 br
->hello_time
= bpdu
->hello_time
;
221 br
->forward_delay
= bpdu
->forward_delay
;
222 br
->topology_change
= bpdu
->topology_change
;
225 /* called under bridge lock */
226 void br_transmit_tcn(struct net_bridge
*br
)
228 br_send_tcn_bpdu(br_get_port(br
, br
->root_port
));
231 /* called under bridge lock */
232 static int br_should_become_designated_port(const struct net_bridge_port
*p
)
234 struct net_bridge
*br
;
238 if (br_is_designated_port(p
))
241 if (memcmp(&p
->designated_root
, &br
->designated_root
, 8))
244 if (br
->root_path_cost
< p
->designated_cost
)
246 else if (br
->root_path_cost
> p
->designated_cost
)
249 t
= memcmp(&br
->bridge_id
, &p
->designated_bridge
, 8);
255 if (p
->port_id
< p
->designated_port
)
261 /* called under bridge lock */
262 static void br_designated_port_selection(struct net_bridge
*br
)
264 struct net_bridge_port
*p
;
266 list_for_each_entry(p
, &br
->port_list
, list
) {
267 if (p
->state
!= BR_STATE_DISABLED
&&
268 br_should_become_designated_port(p
))
269 br_become_designated_port(p
);
274 /* called under bridge lock */
275 static int br_supersedes_port_info(const struct net_bridge_port
*p
,
276 const struct br_config_bpdu
*bpdu
)
280 t
= memcmp(&bpdu
->root
, &p
->designated_root
, 8);
286 if (bpdu
->root_path_cost
< p
->designated_cost
)
288 else if (bpdu
->root_path_cost
> p
->designated_cost
)
291 t
= memcmp(&bpdu
->bridge_id
, &p
->designated_bridge
, 8);
297 if (memcmp(&bpdu
->bridge_id
, &p
->br
->bridge_id
, 8))
300 if (bpdu
->port_id
<= p
->designated_port
)
306 /* called under bridge lock */
307 static void br_topology_change_acknowledged(struct net_bridge
*br
)
309 br
->topology_change_detected
= 0;
310 del_timer(&br
->tcn_timer
);
313 /* called under bridge lock */
314 void br_topology_change_detection(struct net_bridge
*br
)
316 int isroot
= br_is_root_bridge(br
);
318 if (br
->stp_enabled
!= BR_KERNEL_STP
)
321 br_info(br
, "topology change detected, %s\n",
322 isroot
? "propagating" : "sending tcn bpdu");
325 br
->topology_change
= 1;
326 mod_timer(&br
->topology_change_timer
, jiffies
327 + br
->bridge_forward_delay
+ br
->bridge_max_age
);
328 } else if (!br
->topology_change_detected
) {
330 mod_timer(&br
->tcn_timer
, jiffies
+ br
->bridge_hello_time
);
333 br
->topology_change_detected
= 1;
336 /* called under bridge lock */
337 void br_config_bpdu_generation(struct net_bridge
*br
)
339 struct net_bridge_port
*p
;
341 list_for_each_entry(p
, &br
->port_list
, list
) {
342 if (p
->state
!= BR_STATE_DISABLED
&&
343 br_is_designated_port(p
))
344 br_transmit_config(p
);
348 /* called under bridge lock */
349 static void br_reply(struct net_bridge_port
*p
)
351 br_transmit_config(p
);
354 /* called under bridge lock */
355 void br_configuration_update(struct net_bridge
*br
)
357 br_root_selection(br
);
358 br_designated_port_selection(br
);
361 /* called under bridge lock */
362 void br_become_designated_port(struct net_bridge_port
*p
)
364 struct net_bridge
*br
;
367 p
->designated_root
= br
->designated_root
;
368 p
->designated_cost
= br
->root_path_cost
;
369 p
->designated_bridge
= br
->bridge_id
;
370 p
->designated_port
= p
->port_id
;
374 /* called under bridge lock */
375 static void br_make_blocking(struct net_bridge_port
*p
)
377 if (p
->state
!= BR_STATE_DISABLED
&&
378 p
->state
!= BR_STATE_BLOCKING
) {
379 if (p
->state
== BR_STATE_FORWARDING
||
380 p
->state
== BR_STATE_LEARNING
)
381 br_topology_change_detection(p
->br
);
383 p
->state
= BR_STATE_BLOCKING
;
385 br_ifinfo_notify(RTM_NEWLINK
, p
);
387 del_timer(&p
->forward_delay_timer
);
391 /* called under bridge lock */
392 static void br_make_forwarding(struct net_bridge_port
*p
)
394 struct net_bridge
*br
= p
->br
;
396 if (p
->state
!= BR_STATE_BLOCKING
)
399 if (br
->stp_enabled
== BR_NO_STP
|| br
->forward_delay
== 0) {
400 p
->state
= BR_STATE_FORWARDING
;
401 br_topology_change_detection(br
);
402 del_timer(&p
->forward_delay_timer
);
403 } else if (br
->stp_enabled
== BR_KERNEL_STP
)
404 p
->state
= BR_STATE_LISTENING
;
406 p
->state
= BR_STATE_LEARNING
;
408 br_multicast_enable_port(p
);
410 br_ifinfo_notify(RTM_NEWLINK
, p
);
412 if (br
->forward_delay
!= 0)
413 mod_timer(&p
->forward_delay_timer
, jiffies
+ br
->forward_delay
);
416 /* called under bridge lock */
417 void br_port_state_selection(struct net_bridge
*br
)
419 struct net_bridge_port
*p
;
420 unsigned int liveports
= 0;
422 list_for_each_entry(p
, &br
->port_list
, list
) {
423 if (p
->state
== BR_STATE_DISABLED
)
426 /* Don't change port states if userspace is handling STP */
427 if (br
->stp_enabled
!= BR_USER_STP
) {
428 if (p
->port_no
== br
->root_port
) {
429 p
->config_pending
= 0;
430 p
->topology_change_ack
= 0;
431 br_make_forwarding(p
);
432 } else if (br_is_designated_port(p
)) {
433 del_timer(&p
->message_age_timer
);
434 br_make_forwarding(p
);
436 p
->config_pending
= 0;
437 p
->topology_change_ack
= 0;
442 if (p
->state
== BR_STATE_FORWARDING
)
447 netif_carrier_off(br
->dev
);
449 netif_carrier_on(br
->dev
);
452 /* called under bridge lock */
453 static void br_topology_change_acknowledge(struct net_bridge_port
*p
)
455 p
->topology_change_ack
= 1;
456 br_transmit_config(p
);
459 /* called under bridge lock */
460 void br_received_config_bpdu(struct net_bridge_port
*p
,
461 const struct br_config_bpdu
*bpdu
)
463 struct net_bridge
*br
;
467 was_root
= br_is_root_bridge(br
);
469 if (br_supersedes_port_info(p
, bpdu
)) {
470 br_record_config_information(p
, bpdu
);
471 br_configuration_update(br
);
472 br_port_state_selection(br
);
474 if (!br_is_root_bridge(br
) && was_root
) {
475 del_timer(&br
->hello_timer
);
476 if (br
->topology_change_detected
) {
477 del_timer(&br
->topology_change_timer
);
480 mod_timer(&br
->tcn_timer
,
481 jiffies
+ br
->bridge_hello_time
);
485 if (p
->port_no
== br
->root_port
) {
486 br_record_config_timeout_values(br
, bpdu
);
487 br_config_bpdu_generation(br
);
488 if (bpdu
->topology_change_ack
)
489 br_topology_change_acknowledged(br
);
491 } else if (br_is_designated_port(p
)) {
496 /* called under bridge lock */
497 void br_received_tcn_bpdu(struct net_bridge_port
*p
)
499 if (br_is_designated_port(p
)) {
500 br_info(p
->br
, "port %u(%s) received tcn bpdu\n",
501 (unsigned int) p
->port_no
, p
->dev
->name
);
503 br_topology_change_detection(p
->br
);
504 br_topology_change_acknowledge(p
);
508 /* Change bridge STP parameter */
509 int br_set_hello_time(struct net_bridge
*br
, unsigned long val
)
511 unsigned long t
= clock_t_to_jiffies(val
);
513 if (t
< BR_MIN_HELLO_TIME
|| t
> BR_MAX_HELLO_TIME
)
516 spin_lock_bh(&br
->lock
);
517 br
->bridge_hello_time
= t
;
518 if (br_is_root_bridge(br
))
519 br
->hello_time
= br
->bridge_hello_time
;
520 spin_unlock_bh(&br
->lock
);
524 int br_set_max_age(struct net_bridge
*br
, unsigned long val
)
526 unsigned long t
= clock_t_to_jiffies(val
);
528 if (t
< BR_MIN_MAX_AGE
|| t
> BR_MAX_MAX_AGE
)
531 spin_lock_bh(&br
->lock
);
532 br
->bridge_max_age
= t
;
533 if (br_is_root_bridge(br
))
534 br
->max_age
= br
->bridge_max_age
;
535 spin_unlock_bh(&br
->lock
);
540 int br_set_forward_delay(struct net_bridge
*br
, unsigned long val
)
542 unsigned long t
= clock_t_to_jiffies(val
);
544 if (br
->stp_enabled
!= BR_NO_STP
&&
545 (t
< BR_MIN_FORWARD_DELAY
|| t
> BR_MAX_FORWARD_DELAY
))
548 spin_lock_bh(&br
->lock
);
549 br
->bridge_forward_delay
= t
;
550 if (br_is_root_bridge(br
))
551 br
->forward_delay
= br
->bridge_forward_delay
;
552 spin_unlock_bh(&br
->lock
);
This page took 0.046509 seconds and 5 git commands to generate.