]>
git.proxmox.com Git - mirror_ubuntu-eoan-kernel.git/blob - net/bridge/br_stp.c
2 * Spanning tree protocol; generic parts
3 * Linux ethernet bridge
6 * Lennert Buytenhek <buytenh@gnu.org>
8 * $Id: br_stp.c,v 1.4 2000/06/19 10:13:35 davem Exp $
10 * This program is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU General Public License
12 * as published by the Free Software Foundation; either version
13 * 2 of the License, or (at your option) any later version.
15 #include <linux/kernel.h>
16 #include <linux/smp_lock.h>
18 #include "br_private.h"
19 #include "br_private_stp.h"
21 /* since time values in bpdu are in jiffies and then scaled (1/256)
22 * before sending, make sure that is at least one.
24 #define MESSAGE_AGE_INCR ((HZ < 256) ? 1 : (HZ/256))
26 static const char *br_port_state_names
[] = {
27 [BR_STATE_DISABLED
] = "disabled",
28 [BR_STATE_LISTENING
] = "listening",
29 [BR_STATE_LEARNING
] = "learning",
30 [BR_STATE_FORWARDING
] = "forwarding",
31 [BR_STATE_BLOCKING
] = "blocking",
34 void br_log_state(const struct net_bridge_port
*p
)
36 pr_info("%s: port %d(%s) entering %s state\n",
37 p
->br
->dev
->name
, p
->port_no
, p
->dev
->name
,
38 br_port_state_names
[p
->state
]);
42 /* called under bridge lock */
43 struct net_bridge_port
*br_get_port(struct net_bridge
*br
, u16 port_no
)
45 struct net_bridge_port
*p
;
47 list_for_each_entry_rcu(p
, &br
->port_list
, list
) {
48 if (p
->port_no
== port_no
)
55 /* called under bridge lock */
56 static int br_should_become_root_port(const struct net_bridge_port
*p
,
59 struct net_bridge
*br
;
60 struct net_bridge_port
*rp
;
64 if (p
->state
== BR_STATE_DISABLED
||
65 br_is_designated_port(p
))
68 if (memcmp(&br
->bridge_id
, &p
->designated_root
, 8) <= 0)
74 rp
= br_get_port(br
, root_port
);
76 t
= memcmp(&p
->designated_root
, &rp
->designated_root
, 8);
82 if (p
->designated_cost
+ p
->path_cost
<
83 rp
->designated_cost
+ rp
->path_cost
)
85 else if (p
->designated_cost
+ p
->path_cost
>
86 rp
->designated_cost
+ rp
->path_cost
)
89 t
= memcmp(&p
->designated_bridge
, &rp
->designated_bridge
, 8);
95 if (p
->designated_port
< rp
->designated_port
)
97 else if (p
->designated_port
> rp
->designated_port
)
100 if (p
->port_id
< rp
->port_id
)
106 /* called under bridge lock */
107 static void br_root_selection(struct net_bridge
*br
)
109 struct net_bridge_port
*p
;
112 list_for_each_entry(p
, &br
->port_list
, list
) {
113 if (br_should_become_root_port(p
, root_port
))
114 root_port
= p
->port_no
;
118 br
->root_port
= root_port
;
121 br
->designated_root
= br
->bridge_id
;
122 br
->root_path_cost
= 0;
124 p
= br_get_port(br
, root_port
);
125 br
->designated_root
= p
->designated_root
;
126 br
->root_path_cost
= p
->designated_cost
+ p
->path_cost
;
130 /* called under bridge lock */
131 void br_become_root_bridge(struct net_bridge
*br
)
133 br
->max_age
= br
->bridge_max_age
;
134 br
->hello_time
= br
->bridge_hello_time
;
135 br
->forward_delay
= br
->bridge_forward_delay
;
136 br_topology_change_detection(br
);
137 del_timer(&br
->tcn_timer
);
139 if (br
->dev
->flags
& IFF_UP
) {
140 br_config_bpdu_generation(br
);
141 mod_timer(&br
->hello_timer
, jiffies
+ br
->hello_time
);
145 /* called under bridge lock */
146 void br_transmit_config(struct net_bridge_port
*p
)
148 struct br_config_bpdu bpdu
;
149 struct net_bridge
*br
;
152 if (timer_pending(&p
->hold_timer
)) {
153 p
->config_pending
= 1;
159 bpdu
.topology_change
= br
->topology_change
;
160 bpdu
.topology_change_ack
= p
->topology_change_ack
;
161 bpdu
.root
= br
->designated_root
;
162 bpdu
.root_path_cost
= br
->root_path_cost
;
163 bpdu
.bridge_id
= br
->bridge_id
;
164 bpdu
.port_id
= p
->port_id
;
165 if (br_is_root_bridge(br
))
166 bpdu
.message_age
= 0;
168 struct net_bridge_port
*root
169 = br_get_port(br
, br
->root_port
);
170 bpdu
.message_age
= br
->max_age
171 - (root
->message_age_timer
.expires
- jiffies
)
174 bpdu
.max_age
= br
->max_age
;
175 bpdu
.hello_time
= br
->hello_time
;
176 bpdu
.forward_delay
= br
->forward_delay
;
178 if (bpdu
.message_age
< br
->max_age
) {
179 br_send_config_bpdu(p
, &bpdu
);
180 p
->topology_change_ack
= 0;
181 p
->config_pending
= 0;
182 mod_timer(&p
->hold_timer
, jiffies
+ BR_HOLD_TIME
);
186 /* called under bridge lock */
187 static inline void br_record_config_information(struct net_bridge_port
*p
,
188 const struct br_config_bpdu
*bpdu
)
190 p
->designated_root
= bpdu
->root
;
191 p
->designated_cost
= bpdu
->root_path_cost
;
192 p
->designated_bridge
= bpdu
->bridge_id
;
193 p
->designated_port
= bpdu
->port_id
;
195 mod_timer(&p
->message_age_timer
, jiffies
196 + (p
->br
->max_age
- bpdu
->message_age
));
199 /* called under bridge lock */
200 static inline void br_record_config_timeout_values(struct net_bridge
*br
,
201 const struct br_config_bpdu
*bpdu
)
203 br
->max_age
= bpdu
->max_age
;
204 br
->hello_time
= bpdu
->hello_time
;
205 br
->forward_delay
= bpdu
->forward_delay
;
206 br
->topology_change
= bpdu
->topology_change
;
209 /* called under bridge lock */
210 void br_transmit_tcn(struct net_bridge
*br
)
212 br_send_tcn_bpdu(br_get_port(br
, br
->root_port
));
215 /* called under bridge lock */
216 static int br_should_become_designated_port(const struct net_bridge_port
*p
)
218 struct net_bridge
*br
;
222 if (br_is_designated_port(p
))
225 if (memcmp(&p
->designated_root
, &br
->designated_root
, 8))
228 if (br
->root_path_cost
< p
->designated_cost
)
230 else if (br
->root_path_cost
> p
->designated_cost
)
233 t
= memcmp(&br
->bridge_id
, &p
->designated_bridge
, 8);
239 if (p
->port_id
< p
->designated_port
)
245 /* called under bridge lock */
246 static void br_designated_port_selection(struct net_bridge
*br
)
248 struct net_bridge_port
*p
;
250 list_for_each_entry(p
, &br
->port_list
, list
) {
251 if (p
->state
!= BR_STATE_DISABLED
&&
252 br_should_become_designated_port(p
))
253 br_become_designated_port(p
);
258 /* called under bridge lock */
259 static int br_supersedes_port_info(struct net_bridge_port
*p
, struct br_config_bpdu
*bpdu
)
263 t
= memcmp(&bpdu
->root
, &p
->designated_root
, 8);
269 if (bpdu
->root_path_cost
< p
->designated_cost
)
271 else if (bpdu
->root_path_cost
> p
->designated_cost
)
274 t
= memcmp(&bpdu
->bridge_id
, &p
->designated_bridge
, 8);
280 if (memcmp(&bpdu
->bridge_id
, &p
->br
->bridge_id
, 8))
283 if (bpdu
->port_id
<= p
->designated_port
)
289 /* called under bridge lock */
290 static inline void br_topology_change_acknowledged(struct net_bridge
*br
)
292 br
->topology_change_detected
= 0;
293 del_timer(&br
->tcn_timer
);
296 /* called under bridge lock */
297 void br_topology_change_detection(struct net_bridge
*br
)
299 int isroot
= br_is_root_bridge(br
);
301 pr_info("%s: topology change detected, %s\n", br
->dev
->name
,
302 isroot
? "propagating" : "sending tcn bpdu");
305 br
->topology_change
= 1;
306 mod_timer(&br
->topology_change_timer
, jiffies
307 + br
->bridge_forward_delay
+ br
->bridge_max_age
);
308 } else if (!br
->topology_change_detected
) {
310 mod_timer(&br
->tcn_timer
, jiffies
+ br
->bridge_hello_time
);
313 br
->topology_change_detected
= 1;
316 /* called under bridge lock */
317 void br_config_bpdu_generation(struct net_bridge
*br
)
319 struct net_bridge_port
*p
;
321 list_for_each_entry(p
, &br
->port_list
, list
) {
322 if (p
->state
!= BR_STATE_DISABLED
&&
323 br_is_designated_port(p
))
324 br_transmit_config(p
);
328 /* called under bridge lock */
329 static inline void br_reply(struct net_bridge_port
*p
)
331 br_transmit_config(p
);
334 /* called under bridge lock */
335 void br_configuration_update(struct net_bridge
*br
)
337 br_root_selection(br
);
338 br_designated_port_selection(br
);
341 /* called under bridge lock */
342 void br_become_designated_port(struct net_bridge_port
*p
)
344 struct net_bridge
*br
;
347 p
->designated_root
= br
->designated_root
;
348 p
->designated_cost
= br
->root_path_cost
;
349 p
->designated_bridge
= br
->bridge_id
;
350 p
->designated_port
= p
->port_id
;
354 /* called under bridge lock */
355 static void br_make_blocking(struct net_bridge_port
*p
)
357 if (p
->state
!= BR_STATE_DISABLED
&&
358 p
->state
!= BR_STATE_BLOCKING
) {
359 if (p
->state
== BR_STATE_FORWARDING
||
360 p
->state
== BR_STATE_LEARNING
)
361 br_topology_change_detection(p
->br
);
363 p
->state
= BR_STATE_BLOCKING
;
365 del_timer(&p
->forward_delay_timer
);
369 /* called under bridge lock */
370 static void br_make_forwarding(struct net_bridge_port
*p
)
372 if (p
->state
== BR_STATE_BLOCKING
) {
373 if (p
->br
->stp_enabled
) {
374 p
->state
= BR_STATE_LISTENING
;
376 p
->state
= BR_STATE_LEARNING
;
379 mod_timer(&p
->forward_delay_timer
, jiffies
+ p
->br
->forward_delay
); }
382 /* called under bridge lock */
383 void br_port_state_selection(struct net_bridge
*br
)
385 struct net_bridge_port
*p
;
387 list_for_each_entry(p
, &br
->port_list
, list
) {
388 if (p
->state
!= BR_STATE_DISABLED
) {
389 if (p
->port_no
== br
->root_port
) {
390 p
->config_pending
= 0;
391 p
->topology_change_ack
= 0;
392 br_make_forwarding(p
);
393 } else if (br_is_designated_port(p
)) {
394 del_timer(&p
->message_age_timer
);
395 br_make_forwarding(p
);
397 p
->config_pending
= 0;
398 p
->topology_change_ack
= 0;
406 /* called under bridge lock */
407 static inline void br_topology_change_acknowledge(struct net_bridge_port
*p
)
409 p
->topology_change_ack
= 1;
410 br_transmit_config(p
);
413 /* called under bridge lock */
414 void br_received_config_bpdu(struct net_bridge_port
*p
, struct br_config_bpdu
*bpdu
)
416 struct net_bridge
*br
;
420 was_root
= br_is_root_bridge(br
);
422 if (br_supersedes_port_info(p
, bpdu
)) {
423 br_record_config_information(p
, bpdu
);
424 br_configuration_update(br
);
425 br_port_state_selection(br
);
427 if (!br_is_root_bridge(br
) && was_root
) {
428 del_timer(&br
->hello_timer
);
429 if (br
->topology_change_detected
) {
430 del_timer(&br
->topology_change_timer
);
433 mod_timer(&br
->tcn_timer
,
434 jiffies
+ br
->bridge_hello_time
);
438 if (p
->port_no
== br
->root_port
) {
439 br_record_config_timeout_values(br
, bpdu
);
440 br_config_bpdu_generation(br
);
441 if (bpdu
->topology_change_ack
)
442 br_topology_change_acknowledged(br
);
444 } else if (br_is_designated_port(p
)) {
449 /* called under bridge lock */
450 void br_received_tcn_bpdu(struct net_bridge_port
*p
)
452 if (br_is_designated_port(p
)) {
453 pr_info("%s: received tcn bpdu on port %i(%s)\n",
454 p
->br
->dev
->name
, p
->port_no
, p
->dev
->name
);
456 br_topology_change_detection(p
->br
);
457 br_topology_change_acknowledge(p
);