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>
15 #include "br_private.h"
16 #include "br_private_stp.h"
18 /* since time values in bpdu are in jiffies and then scaled (1/256)
19 * before sending, make sure that is at least one.
21 #define MESSAGE_AGE_INCR ((HZ < 256) ? 1 : (HZ/256))
23 static const char *br_port_state_names
[] = {
24 [BR_STATE_DISABLED
] = "disabled",
25 [BR_STATE_LISTENING
] = "listening",
26 [BR_STATE_LEARNING
] = "learning",
27 [BR_STATE_FORWARDING
] = "forwarding",
28 [BR_STATE_BLOCKING
] = "blocking",
31 void br_log_state(const struct net_bridge_port
*p
)
33 pr_info("%s: port %d(%s) entering %s state\n",
34 p
->br
->dev
->name
, p
->port_no
, p
->dev
->name
,
35 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 /* called under bridge lock */
104 static void br_root_selection(struct net_bridge
*br
)
106 struct net_bridge_port
*p
;
109 list_for_each_entry(p
, &br
->port_list
, list
) {
110 if (br_should_become_root_port(p
, root_port
))
111 root_port
= p
->port_no
;
115 br
->root_port
= root_port
;
118 br
->designated_root
= br
->bridge_id
;
119 br
->root_path_cost
= 0;
121 p
= br_get_port(br
, root_port
);
122 br
->designated_root
= p
->designated_root
;
123 br
->root_path_cost
= p
->designated_cost
+ p
->path_cost
;
127 /* called under bridge lock */
128 void br_become_root_bridge(struct net_bridge
*br
)
130 br
->max_age
= br
->bridge_max_age
;
131 br
->hello_time
= br
->bridge_hello_time
;
132 br
->forward_delay
= br
->bridge_forward_delay
;
133 br_topology_change_detection(br
);
134 del_timer(&br
->tcn_timer
);
136 if (br
->dev
->flags
& IFF_UP
) {
137 br_config_bpdu_generation(br
);
138 mod_timer(&br
->hello_timer
, jiffies
+ br
->hello_time
);
142 /* called under bridge lock */
143 void br_transmit_config(struct net_bridge_port
*p
)
145 struct br_config_bpdu bpdu
;
146 struct net_bridge
*br
;
149 if (timer_pending(&p
->hold_timer
)) {
150 p
->config_pending
= 1;
156 bpdu
.topology_change
= br
->topology_change
;
157 bpdu
.topology_change_ack
= p
->topology_change_ack
;
158 bpdu
.root
= br
->designated_root
;
159 bpdu
.root_path_cost
= br
->root_path_cost
;
160 bpdu
.bridge_id
= br
->bridge_id
;
161 bpdu
.port_id
= p
->port_id
;
162 if (br_is_root_bridge(br
))
163 bpdu
.message_age
= 0;
165 struct net_bridge_port
*root
166 = br_get_port(br
, br
->root_port
);
167 bpdu
.message_age
= br
->max_age
168 - (root
->message_age_timer
.expires
- jiffies
)
171 bpdu
.max_age
= br
->max_age
;
172 bpdu
.hello_time
= br
->hello_time
;
173 bpdu
.forward_delay
= br
->forward_delay
;
175 if (bpdu
.message_age
< br
->max_age
) {
176 br_send_config_bpdu(p
, &bpdu
);
177 p
->topology_change_ack
= 0;
178 p
->config_pending
= 0;
179 mod_timer(&p
->hold_timer
,
180 round_jiffies(jiffies
+ BR_HOLD_TIME
));
184 /* called under bridge lock */
185 static inline void br_record_config_information(struct net_bridge_port
*p
,
186 const struct br_config_bpdu
*bpdu
)
188 p
->designated_root
= bpdu
->root
;
189 p
->designated_cost
= bpdu
->root_path_cost
;
190 p
->designated_bridge
= bpdu
->bridge_id
;
191 p
->designated_port
= bpdu
->port_id
;
193 mod_timer(&p
->message_age_timer
, jiffies
194 + (p
->br
->max_age
- bpdu
->message_age
));
197 /* called under bridge lock */
198 static inline void br_record_config_timeout_values(struct net_bridge
*br
,
199 const struct br_config_bpdu
*bpdu
)
201 br
->max_age
= bpdu
->max_age
;
202 br
->hello_time
= bpdu
->hello_time
;
203 br
->forward_delay
= bpdu
->forward_delay
;
204 br
->topology_change
= bpdu
->topology_change
;
207 /* called under bridge lock */
208 void br_transmit_tcn(struct net_bridge
*br
)
210 br_send_tcn_bpdu(br_get_port(br
, br
->root_port
));
213 /* called under bridge lock */
214 static int br_should_become_designated_port(const struct net_bridge_port
*p
)
216 struct net_bridge
*br
;
220 if (br_is_designated_port(p
))
223 if (memcmp(&p
->designated_root
, &br
->designated_root
, 8))
226 if (br
->root_path_cost
< p
->designated_cost
)
228 else if (br
->root_path_cost
> p
->designated_cost
)
231 t
= memcmp(&br
->bridge_id
, &p
->designated_bridge
, 8);
237 if (p
->port_id
< p
->designated_port
)
243 /* called under bridge lock */
244 static void br_designated_port_selection(struct net_bridge
*br
)
246 struct net_bridge_port
*p
;
248 list_for_each_entry(p
, &br
->port_list
, list
) {
249 if (p
->state
!= BR_STATE_DISABLED
&&
250 br_should_become_designated_port(p
))
251 br_become_designated_port(p
);
256 /* called under bridge lock */
257 static int br_supersedes_port_info(struct net_bridge_port
*p
, struct br_config_bpdu
*bpdu
)
261 t
= memcmp(&bpdu
->root
, &p
->designated_root
, 8);
267 if (bpdu
->root_path_cost
< p
->designated_cost
)
269 else if (bpdu
->root_path_cost
> p
->designated_cost
)
272 t
= memcmp(&bpdu
->bridge_id
, &p
->designated_bridge
, 8);
278 if (memcmp(&bpdu
->bridge_id
, &p
->br
->bridge_id
, 8))
281 if (bpdu
->port_id
<= p
->designated_port
)
287 /* called under bridge lock */
288 static inline void br_topology_change_acknowledged(struct net_bridge
*br
)
290 br
->topology_change_detected
= 0;
291 del_timer(&br
->tcn_timer
);
294 /* called under bridge lock */
295 void br_topology_change_detection(struct net_bridge
*br
)
297 int isroot
= br_is_root_bridge(br
);
299 pr_info("%s: topology change detected, %s\n", br
->dev
->name
,
300 isroot
? "propagating" : "sending tcn bpdu");
303 br
->topology_change
= 1;
304 mod_timer(&br
->topology_change_timer
, jiffies
305 + br
->bridge_forward_delay
+ br
->bridge_max_age
);
306 } else if (!br
->topology_change_detected
) {
308 mod_timer(&br
->tcn_timer
, jiffies
+ br
->bridge_hello_time
);
311 br
->topology_change_detected
= 1;
314 /* called under bridge lock */
315 void br_config_bpdu_generation(struct net_bridge
*br
)
317 struct net_bridge_port
*p
;
319 list_for_each_entry(p
, &br
->port_list
, list
) {
320 if (p
->state
!= BR_STATE_DISABLED
&&
321 br_is_designated_port(p
))
322 br_transmit_config(p
);
326 /* called under bridge lock */
327 static inline void br_reply(struct net_bridge_port
*p
)
329 br_transmit_config(p
);
332 /* called under bridge lock */
333 void br_configuration_update(struct net_bridge
*br
)
335 br_root_selection(br
);
336 br_designated_port_selection(br
);
339 /* called under bridge lock */
340 void br_become_designated_port(struct net_bridge_port
*p
)
342 struct net_bridge
*br
;
345 p
->designated_root
= br
->designated_root
;
346 p
->designated_cost
= br
->root_path_cost
;
347 p
->designated_bridge
= br
->bridge_id
;
348 p
->designated_port
= p
->port_id
;
352 /* called under bridge lock */
353 static void br_make_blocking(struct net_bridge_port
*p
)
355 if (p
->state
!= BR_STATE_DISABLED
&&
356 p
->state
!= BR_STATE_BLOCKING
) {
357 if (p
->state
== BR_STATE_FORWARDING
||
358 p
->state
== BR_STATE_LEARNING
)
359 br_topology_change_detection(p
->br
);
361 p
->state
= BR_STATE_BLOCKING
;
363 del_timer(&p
->forward_delay_timer
);
367 /* called under bridge lock */
368 static void br_make_forwarding(struct net_bridge_port
*p
)
370 if (p
->state
== BR_STATE_BLOCKING
) {
371 if (p
->br
->stp_enabled
== BR_KERNEL_STP
)
372 p
->state
= BR_STATE_LISTENING
;
374 p
->state
= BR_STATE_LEARNING
;
377 mod_timer(&p
->forward_delay_timer
, jiffies
+ p
->br
->forward_delay
); }
380 /* called under bridge lock */
381 void br_port_state_selection(struct net_bridge
*br
)
383 struct net_bridge_port
*p
;
385 /* Don't change port states if userspace is handling STP */
386 if (br
->stp_enabled
== BR_USER_STP
)
389 list_for_each_entry(p
, &br
->port_list
, list
) {
390 if (p
->state
!= BR_STATE_DISABLED
) {
391 if (p
->port_no
== br
->root_port
) {
392 p
->config_pending
= 0;
393 p
->topology_change_ack
= 0;
394 br_make_forwarding(p
);
395 } else if (br_is_designated_port(p
)) {
396 del_timer(&p
->message_age_timer
);
397 br_make_forwarding(p
);
399 p
->config_pending
= 0;
400 p
->topology_change_ack
= 0;
408 /* called under bridge lock */
409 static inline void br_topology_change_acknowledge(struct net_bridge_port
*p
)
411 p
->topology_change_ack
= 1;
412 br_transmit_config(p
);
415 /* called under bridge lock */
416 void br_received_config_bpdu(struct net_bridge_port
*p
, struct br_config_bpdu
*bpdu
)
418 struct net_bridge
*br
;
422 was_root
= br_is_root_bridge(br
);
424 if (br_supersedes_port_info(p
, bpdu
)) {
425 br_record_config_information(p
, bpdu
);
426 br_configuration_update(br
);
427 br_port_state_selection(br
);
429 if (!br_is_root_bridge(br
) && was_root
) {
430 del_timer(&br
->hello_timer
);
431 if (br
->topology_change_detected
) {
432 del_timer(&br
->topology_change_timer
);
435 mod_timer(&br
->tcn_timer
,
436 jiffies
+ br
->bridge_hello_time
);
440 if (p
->port_no
== br
->root_port
) {
441 br_record_config_timeout_values(br
, bpdu
);
442 br_config_bpdu_generation(br
);
443 if (bpdu
->topology_change_ack
)
444 br_topology_change_acknowledged(br
);
446 } else if (br_is_designated_port(p
)) {
451 /* called under bridge lock */
452 void br_received_tcn_bpdu(struct net_bridge_port
*p
)
454 if (br_is_designated_port(p
)) {
455 pr_info("%s: received tcn bpdu on port %i(%s)\n",
456 p
->br
->dev
->name
, p
->port_no
, p
->dev
->name
);
458 br_topology_change_detection(p
->br
);
459 br_topology_change_acknowledge(p
);
This page took 0.144109 seconds and 5 git commands to generate.