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.
22 #define MESSAGE_AGE_INCR ((HZ < 256) ? 1 : (HZ/256))
24 static const char *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 pr_info("%s: port %d(%s) entering %s state\n",
35 p
->br
->dev
->name
, p
->port_no
, p
->dev
->name
,
36 br_port_state_names
[p
->state
]);
40 /* called under bridge lock */
41 struct net_bridge_port
*br_get_port(struct net_bridge
*br
, u16 port_no
)
43 struct net_bridge_port
*p
;
45 list_for_each_entry_rcu(p
, &br
->port_list
, list
) {
46 if (p
->port_no
== port_no
)
53 /* called under bridge lock */
54 static int br_should_become_root_port(const struct net_bridge_port
*p
,
57 struct net_bridge
*br
;
58 struct net_bridge_port
*rp
;
62 if (p
->state
== BR_STATE_DISABLED
||
63 br_is_designated_port(p
))
66 if (memcmp(&br
->bridge_id
, &p
->designated_root
, 8) <= 0)
72 rp
= br_get_port(br
, root_port
);
74 t
= memcmp(&p
->designated_root
, &rp
->designated_root
, 8);
80 if (p
->designated_cost
+ p
->path_cost
<
81 rp
->designated_cost
+ rp
->path_cost
)
83 else if (p
->designated_cost
+ p
->path_cost
>
84 rp
->designated_cost
+ rp
->path_cost
)
87 t
= memcmp(&p
->designated_bridge
, &rp
->designated_bridge
, 8);
93 if (p
->designated_port
< rp
->designated_port
)
95 else if (p
->designated_port
> rp
->designated_port
)
98 if (p
->port_id
< rp
->port_id
)
104 /* called under bridge lock */
105 static void br_root_selection(struct net_bridge
*br
)
107 struct net_bridge_port
*p
;
110 list_for_each_entry(p
, &br
->port_list
, list
) {
111 if (br_should_become_root_port(p
, root_port
))
112 root_port
= p
->port_no
;
116 br
->root_port
= root_port
;
119 br
->designated_root
= br
->bridge_id
;
120 br
->root_path_cost
= 0;
122 p
= br_get_port(br
, root_port
);
123 br
->designated_root
= p
->designated_root
;
124 br
->root_path_cost
= p
->designated_cost
+ p
->path_cost
;
128 /* called under bridge lock */
129 void br_become_root_bridge(struct net_bridge
*br
)
131 br
->max_age
= br
->bridge_max_age
;
132 br
->hello_time
= br
->bridge_hello_time
;
133 br
->forward_delay
= br
->bridge_forward_delay
;
134 br_topology_change_detection(br
);
135 del_timer(&br
->tcn_timer
);
137 if (br
->dev
->flags
& IFF_UP
) {
138 br_config_bpdu_generation(br
);
139 mod_timer(&br
->hello_timer
, jiffies
+ br
->hello_time
);
143 /* called under bridge lock */
144 void br_transmit_config(struct net_bridge_port
*p
)
146 struct br_config_bpdu bpdu
;
147 struct net_bridge
*br
;
150 if (timer_pending(&p
->hold_timer
)) {
151 p
->config_pending
= 1;
157 bpdu
.topology_change
= br
->topology_change
;
158 bpdu
.topology_change_ack
= p
->topology_change_ack
;
159 bpdu
.root
= br
->designated_root
;
160 bpdu
.root_path_cost
= br
->root_path_cost
;
161 bpdu
.bridge_id
= br
->bridge_id
;
162 bpdu
.port_id
= p
->port_id
;
163 if (br_is_root_bridge(br
))
164 bpdu
.message_age
= 0;
166 struct net_bridge_port
*root
167 = br_get_port(br
, br
->root_port
);
168 bpdu
.message_age
= br
->max_age
169 - (root
->message_age_timer
.expires
- jiffies
)
172 bpdu
.max_age
= br
->max_age
;
173 bpdu
.hello_time
= br
->hello_time
;
174 bpdu
.forward_delay
= br
->forward_delay
;
176 if (bpdu
.message_age
< br
->max_age
) {
177 br_send_config_bpdu(p
, &bpdu
);
178 p
->topology_change_ack
= 0;
179 p
->config_pending
= 0;
180 mod_timer(&p
->hold_timer
,
181 round_jiffies(jiffies
+ BR_HOLD_TIME
));
185 /* called under bridge lock */
186 static inline void br_record_config_information(struct net_bridge_port
*p
,
187 const struct br_config_bpdu
*bpdu
)
189 p
->designated_root
= bpdu
->root
;
190 p
->designated_cost
= bpdu
->root_path_cost
;
191 p
->designated_bridge
= bpdu
->bridge_id
;
192 p
->designated_port
= bpdu
->port_id
;
194 mod_timer(&p
->message_age_timer
, jiffies
195 + (p
->br
->max_age
- bpdu
->message_age
));
198 /* called under bridge lock */
199 static inline void br_record_config_timeout_values(struct net_bridge
*br
,
200 const struct br_config_bpdu
*bpdu
)
202 br
->max_age
= bpdu
->max_age
;
203 br
->hello_time
= bpdu
->hello_time
;
204 br
->forward_delay
= bpdu
->forward_delay
;
205 br
->topology_change
= bpdu
->topology_change
;
208 /* called under bridge lock */
209 void br_transmit_tcn(struct net_bridge
*br
)
211 br_send_tcn_bpdu(br_get_port(br
, br
->root_port
));
214 /* called under bridge lock */
215 static int br_should_become_designated_port(const struct net_bridge_port
*p
)
217 struct net_bridge
*br
;
221 if (br_is_designated_port(p
))
224 if (memcmp(&p
->designated_root
, &br
->designated_root
, 8))
227 if (br
->root_path_cost
< p
->designated_cost
)
229 else if (br
->root_path_cost
> p
->designated_cost
)
232 t
= memcmp(&br
->bridge_id
, &p
->designated_bridge
, 8);
238 if (p
->port_id
< p
->designated_port
)
244 /* called under bridge lock */
245 static void br_designated_port_selection(struct net_bridge
*br
)
247 struct net_bridge_port
*p
;
249 list_for_each_entry(p
, &br
->port_list
, list
) {
250 if (p
->state
!= BR_STATE_DISABLED
&&
251 br_should_become_designated_port(p
))
252 br_become_designated_port(p
);
257 /* called under bridge lock */
258 static int br_supersedes_port_info(struct net_bridge_port
*p
, struct br_config_bpdu
*bpdu
)
262 t
= memcmp(&bpdu
->root
, &p
->designated_root
, 8);
268 if (bpdu
->root_path_cost
< p
->designated_cost
)
270 else if (bpdu
->root_path_cost
> p
->designated_cost
)
273 t
= memcmp(&bpdu
->bridge_id
, &p
->designated_bridge
, 8);
279 if (memcmp(&bpdu
->bridge_id
, &p
->br
->bridge_id
, 8))
282 if (bpdu
->port_id
<= p
->designated_port
)
288 /* called under bridge lock */
289 static inline void br_topology_change_acknowledged(struct net_bridge
*br
)
291 br
->topology_change_detected
= 0;
292 del_timer(&br
->tcn_timer
);
295 /* called under bridge lock */
296 void br_topology_change_detection(struct net_bridge
*br
)
298 int isroot
= br_is_root_bridge(br
);
300 pr_info("%s: topology change detected, %s\n", br
->dev
->name
,
301 isroot
? "propagating" : "sending tcn bpdu");
304 br
->topology_change
= 1;
305 mod_timer(&br
->topology_change_timer
, jiffies
306 + br
->bridge_forward_delay
+ br
->bridge_max_age
);
307 } else if (!br
->topology_change_detected
) {
309 mod_timer(&br
->tcn_timer
, jiffies
+ br
->bridge_hello_time
);
312 br
->topology_change_detected
= 1;
315 /* called under bridge lock */
316 void br_config_bpdu_generation(struct net_bridge
*br
)
318 struct net_bridge_port
*p
;
320 list_for_each_entry(p
, &br
->port_list
, list
) {
321 if (p
->state
!= BR_STATE_DISABLED
&&
322 br_is_designated_port(p
))
323 br_transmit_config(p
);
327 /* called under bridge lock */
328 static inline void br_reply(struct net_bridge_port
*p
)
330 br_transmit_config(p
);
333 /* called under bridge lock */
334 void br_configuration_update(struct net_bridge
*br
)
336 br_root_selection(br
);
337 br_designated_port_selection(br
);
340 /* called under bridge lock */
341 void br_become_designated_port(struct net_bridge_port
*p
)
343 struct net_bridge
*br
;
346 p
->designated_root
= br
->designated_root
;
347 p
->designated_cost
= br
->root_path_cost
;
348 p
->designated_bridge
= br
->bridge_id
;
349 p
->designated_port
= p
->port_id
;
353 /* called under bridge lock */
354 static void br_make_blocking(struct net_bridge_port
*p
)
356 if (p
->state
!= BR_STATE_DISABLED
&&
357 p
->state
!= BR_STATE_BLOCKING
) {
358 if (p
->state
== BR_STATE_FORWARDING
||
359 p
->state
== BR_STATE_LEARNING
)
360 br_topology_change_detection(p
->br
);
362 p
->state
= BR_STATE_BLOCKING
;
364 del_timer(&p
->forward_delay_timer
);
368 /* called under bridge lock */
369 static void br_make_forwarding(struct net_bridge_port
*p
)
371 struct net_bridge
*br
= p
->br
;
373 if (p
->state
!= BR_STATE_BLOCKING
)
376 if (br
->forward_delay
== 0) {
377 p
->state
= BR_STATE_FORWARDING
;
378 br_topology_change_detection(br
);
379 del_timer(&p
->forward_delay_timer
);
381 else if (p
->br
->stp_enabled
== BR_KERNEL_STP
)
382 p
->state
= BR_STATE_LISTENING
;
384 p
->state
= BR_STATE_LEARNING
;
388 if (br
->forward_delay
!= 0)
389 mod_timer(&p
->forward_delay_timer
, jiffies
+ br
->forward_delay
);
392 /* called under bridge lock */
393 void br_port_state_selection(struct net_bridge
*br
)
395 struct net_bridge_port
*p
;
397 /* Don't change port states if userspace is handling STP */
398 if (br
->stp_enabled
== BR_USER_STP
)
401 list_for_each_entry(p
, &br
->port_list
, list
) {
402 if (p
->state
!= BR_STATE_DISABLED
) {
403 if (p
->port_no
== br
->root_port
) {
404 p
->config_pending
= 0;
405 p
->topology_change_ack
= 0;
406 br_make_forwarding(p
);
407 } else if (br_is_designated_port(p
)) {
408 del_timer(&p
->message_age_timer
);
409 br_make_forwarding(p
);
411 p
->config_pending
= 0;
412 p
->topology_change_ack
= 0;
420 /* called under bridge lock */
421 static inline void br_topology_change_acknowledge(struct net_bridge_port
*p
)
423 p
->topology_change_ack
= 1;
424 br_transmit_config(p
);
427 /* called under bridge lock */
428 void br_received_config_bpdu(struct net_bridge_port
*p
, struct br_config_bpdu
*bpdu
)
430 struct net_bridge
*br
;
434 was_root
= br_is_root_bridge(br
);
436 if (br_supersedes_port_info(p
, bpdu
)) {
437 br_record_config_information(p
, bpdu
);
438 br_configuration_update(br
);
439 br_port_state_selection(br
);
441 if (!br_is_root_bridge(br
) && was_root
) {
442 del_timer(&br
->hello_timer
);
443 if (br
->topology_change_detected
) {
444 del_timer(&br
->topology_change_timer
);
447 mod_timer(&br
->tcn_timer
,
448 jiffies
+ br
->bridge_hello_time
);
452 if (p
->port_no
== br
->root_port
) {
453 br_record_config_timeout_values(br
, bpdu
);
454 br_config_bpdu_generation(br
);
455 if (bpdu
->topology_change_ack
)
456 br_topology_change_acknowledged(br
);
458 } else if (br_is_designated_port(p
)) {
463 /* called under bridge lock */
464 void br_received_tcn_bpdu(struct net_bridge_port
*p
)
466 if (br_is_designated_port(p
)) {
467 pr_info("%s: received tcn bpdu on port %i(%s)\n",
468 p
->br
->dev
->name
, p
->port_no
, p
->dev
->name
);
470 br_topology_change_detection(p
->br
);
471 br_topology_change_acknowledge(p
);
This page took 0.039201 seconds and 5 git commands to generate.