Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | /* |
2 | * Spanning tree protocol; generic parts | |
3 | * Linux ethernet bridge | |
4 | * | |
5 | * Authors: | |
6 | * Lennert Buytenhek <buytenh@gnu.org> | |
7 | * | |
1da177e4 LT |
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. | |
12 | */ | |
13 | #include <linux/kernel.h> | |
82524746 | 14 | #include <linux/rculist.h> |
1da177e4 LT |
15 | |
16 | #include "br_private.h" | |
17 | #include "br_private_stp.h" | |
18 | ||
19 | /* since time values in bpdu are in jiffies and then scaled (1/256) | |
aaca735f | 20 | * before sending, make sure that is at least one STP tick. |
1da177e4 | 21 | */ |
aaca735f | 22 | #define MESSAGE_AGE_INCR ((HZ / 256) + 1) |
1da177e4 | 23 | |
36cbd3dc | 24 | static const char *const br_port_state_names[] = { |
9d6f229f | 25 | [BR_STATE_DISABLED] = "disabled", |
1da177e4 | 26 | [BR_STATE_LISTENING] = "listening", |
9d6f229f YH |
27 | [BR_STATE_LEARNING] = "learning", |
28 | [BR_STATE_FORWARDING] = "forwarding", | |
1da177e4 LT |
29 | [BR_STATE_BLOCKING] = "blocking", |
30 | }; | |
31 | ||
32 | void br_log_state(const struct net_bridge_port *p) | |
33 | { | |
d9e179ec | 34 | br_info(p->br, "port %u(%s) entered %s state\n", |
95c96174 | 35 | (unsigned int) p->port_no, p->dev->name, |
1da177e4 | 36 | br_port_state_names[p->state]); |
1da177e4 LT |
37 | } |
38 | ||
39 | /* called under bridge lock */ | |
40 | struct net_bridge_port *br_get_port(struct net_bridge *br, u16 port_no) | |
41 | { | |
42 | struct net_bridge_port *p; | |
43 | ||
44 | list_for_each_entry_rcu(p, &br->port_list, list) { | |
45 | if (p->port_no == port_no) | |
46 | return p; | |
47 | } | |
48 | ||
49 | return NULL; | |
50 | } | |
51 | ||
52 | /* called under bridge lock */ | |
9d6f229f | 53 | static int br_should_become_root_port(const struct net_bridge_port *p, |
1da177e4 LT |
54 | u16 root_port) |
55 | { | |
56 | struct net_bridge *br; | |
57 | struct net_bridge_port *rp; | |
58 | int t; | |
59 | ||
60 | br = p->br; | |
61 | if (p->state == BR_STATE_DISABLED || | |
62 | br_is_designated_port(p)) | |
63 | return 0; | |
64 | ||
65 | if (memcmp(&br->bridge_id, &p->designated_root, 8) <= 0) | |
66 | return 0; | |
67 | ||
68 | if (!root_port) | |
69 | return 1; | |
70 | ||
71 | rp = br_get_port(br, root_port); | |
72 | ||
73 | t = memcmp(&p->designated_root, &rp->designated_root, 8); | |
74 | if (t < 0) | |
75 | return 1; | |
76 | else if (t > 0) | |
77 | return 0; | |
78 | ||
79 | if (p->designated_cost + p->path_cost < | |
80 | rp->designated_cost + rp->path_cost) | |
81 | return 1; | |
82 | else if (p->designated_cost + p->path_cost > | |
83 | rp->designated_cost + rp->path_cost) | |
84 | return 0; | |
85 | ||
86 | t = memcmp(&p->designated_bridge, &rp->designated_bridge, 8); | |
87 | if (t < 0) | |
88 | return 1; | |
89 | else if (t > 0) | |
90 | return 0; | |
91 | ||
92 | if (p->designated_port < rp->designated_port) | |
93 | return 1; | |
94 | else if (p->designated_port > rp->designated_port) | |
95 | return 0; | |
96 | ||
97 | if (p->port_id < rp->port_id) | |
98 | return 1; | |
99 | ||
100 | return 0; | |
101 | } | |
102 | ||
1007dd1a | 103 | static void br_root_port_block(const struct net_bridge *br, |
104 | struct net_bridge_port *p) | |
105 | { | |
106 | ||
107 | br_notice(br, "port %u(%s) tried to become root port (blocked)", | |
108 | (unsigned int) p->port_no, p->dev->name); | |
109 | ||
110 | p->state = BR_STATE_LISTENING; | |
111 | br_log_state(p); | |
112 | br_ifinfo_notify(RTM_NEWLINK, p); | |
113 | ||
114 | if (br->forward_delay > 0) | |
115 | mod_timer(&p->forward_delay_timer, jiffies + br->forward_delay); | |
116 | } | |
117 | ||
1da177e4 LT |
118 | /* called under bridge lock */ |
119 | static void br_root_selection(struct net_bridge *br) | |
120 | { | |
121 | struct net_bridge_port *p; | |
122 | u16 root_port = 0; | |
123 | ||
124 | list_for_each_entry(p, &br->port_list, list) { | |
1007dd1a | 125 | if (!br_should_become_root_port(p, root_port)) |
126 | continue; | |
127 | ||
128 | if (p->flags & BR_ROOT_BLOCK) | |
129 | br_root_port_block(br, p); | |
130 | else | |
1da177e4 | 131 | root_port = p->port_no; |
1da177e4 LT |
132 | } |
133 | ||
134 | br->root_port = root_port; | |
135 | ||
136 | if (!root_port) { | |
137 | br->designated_root = br->bridge_id; | |
138 | br->root_path_cost = 0; | |
139 | } else { | |
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; | |
143 | } | |
144 | } | |
145 | ||
146 | /* called under bridge lock */ | |
147 | void br_become_root_bridge(struct net_bridge *br) | |
148 | { | |
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); | |
154 | ||
155 | if (br->dev->flags & IFF_UP) { | |
156 | br_config_bpdu_generation(br); | |
157 | mod_timer(&br->hello_timer, jiffies + br->hello_time); | |
158 | } | |
159 | } | |
160 | ||
161 | /* called under bridge lock */ | |
162 | void br_transmit_config(struct net_bridge_port *p) | |
163 | { | |
164 | struct br_config_bpdu bpdu; | |
165 | struct net_bridge *br; | |
166 | ||
1da177e4 LT |
167 | if (timer_pending(&p->hold_timer)) { |
168 | p->config_pending = 1; | |
169 | return; | |
170 | } | |
171 | ||
172 | br = p->br; | |
173 | ||
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; | |
182 | else { | |
183 | struct net_bridge_port *root | |
184 | = br_get_port(br, br->root_port); | |
0c03150e | 185 | bpdu.message_age = (jiffies - root->designated_age) |
1da177e4 LT |
186 | + MESSAGE_AGE_INCR; |
187 | } | |
188 | bpdu.max_age = br->max_age; | |
189 | bpdu.hello_time = br->hello_time; | |
190 | bpdu.forward_delay = br->forward_delay; | |
191 | ||
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; | |
9a834b87 SH |
196 | mod_timer(&p->hold_timer, |
197 | round_jiffies(jiffies + BR_HOLD_TIME)); | |
1da177e4 LT |
198 | } |
199 | } | |
200 | ||
201 | /* called under bridge lock */ | |
160d73b8 | 202 | static void br_record_config_information(struct net_bridge_port *p, |
203 | const struct br_config_bpdu *bpdu) | |
1da177e4 LT |
204 | { |
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; | |
709e1b5c | 209 | p->designated_age = jiffies - bpdu->message_age; |
1da177e4 | 210 | |
9d6f229f | 211 | mod_timer(&p->message_age_timer, jiffies |
9a062013 | 212 | + (bpdu->max_age - bpdu->message_age)); |
1da177e4 LT |
213 | } |
214 | ||
215 | /* called under bridge lock */ | |
160d73b8 | 216 | static void br_record_config_timeout_values(struct net_bridge *br, |
1da177e4 LT |
217 | const struct br_config_bpdu *bpdu) |
218 | { | |
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; | |
223 | } | |
224 | ||
225 | /* called under bridge lock */ | |
226 | void br_transmit_tcn(struct net_bridge *br) | |
227 | { | |
91bc033c | 228 | struct net_bridge_port *p; |
229 | ||
230 | p = br_get_port(br, br->root_port); | |
231 | if (p) | |
232 | br_send_tcn_bpdu(p); | |
233 | else | |
234 | br_notice(br, "root port %u not found for topology notice\n", | |
235 | br->root_port); | |
1da177e4 LT |
236 | } |
237 | ||
238 | /* called under bridge lock */ | |
239 | static int br_should_become_designated_port(const struct net_bridge_port *p) | |
240 | { | |
241 | struct net_bridge *br; | |
242 | int t; | |
243 | ||
244 | br = p->br; | |
245 | if (br_is_designated_port(p)) | |
246 | return 1; | |
247 | ||
248 | if (memcmp(&p->designated_root, &br->designated_root, 8)) | |
249 | return 1; | |
250 | ||
251 | if (br->root_path_cost < p->designated_cost) | |
252 | return 1; | |
253 | else if (br->root_path_cost > p->designated_cost) | |
254 | return 0; | |
255 | ||
256 | t = memcmp(&br->bridge_id, &p->designated_bridge, 8); | |
257 | if (t < 0) | |
258 | return 1; | |
259 | else if (t > 0) | |
260 | return 0; | |
261 | ||
262 | if (p->port_id < p->designated_port) | |
263 | return 1; | |
264 | ||
265 | return 0; | |
266 | } | |
267 | ||
268 | /* called under bridge lock */ | |
269 | static void br_designated_port_selection(struct net_bridge *br) | |
270 | { | |
271 | struct net_bridge_port *p; | |
272 | ||
273 | list_for_each_entry(p, &br->port_list, list) { | |
274 | if (p->state != BR_STATE_DISABLED && | |
275 | br_should_become_designated_port(p)) | |
276 | br_become_designated_port(p); | |
277 | ||
278 | } | |
279 | } | |
280 | ||
281 | /* called under bridge lock */ | |
160d73b8 | 282 | static int br_supersedes_port_info(const struct net_bridge_port *p, |
283 | const struct br_config_bpdu *bpdu) | |
1da177e4 LT |
284 | { |
285 | int t; | |
286 | ||
287 | t = memcmp(&bpdu->root, &p->designated_root, 8); | |
288 | if (t < 0) | |
289 | return 1; | |
290 | else if (t > 0) | |
291 | return 0; | |
292 | ||
293 | if (bpdu->root_path_cost < p->designated_cost) | |
294 | return 1; | |
295 | else if (bpdu->root_path_cost > p->designated_cost) | |
296 | return 0; | |
297 | ||
298 | t = memcmp(&bpdu->bridge_id, &p->designated_bridge, 8); | |
299 | if (t < 0) | |
300 | return 1; | |
301 | else if (t > 0) | |
302 | return 0; | |
303 | ||
304 | if (memcmp(&bpdu->bridge_id, &p->br->bridge_id, 8)) | |
305 | return 1; | |
306 | ||
307 | if (bpdu->port_id <= p->designated_port) | |
308 | return 1; | |
309 | ||
310 | return 0; | |
311 | } | |
312 | ||
313 | /* called under bridge lock */ | |
160d73b8 | 314 | static void br_topology_change_acknowledged(struct net_bridge *br) |
1da177e4 LT |
315 | { |
316 | br->topology_change_detected = 0; | |
317 | del_timer(&br->tcn_timer); | |
318 | } | |
319 | ||
320 | /* called under bridge lock */ | |
321 | void br_topology_change_detection(struct net_bridge *br) | |
322 | { | |
323 | int isroot = br_is_root_bridge(br); | |
324 | ||
4f0611af SH |
325 | if (br->stp_enabled != BR_KERNEL_STP) |
326 | return; | |
327 | ||
28a16c97 | 328 | br_info(br, "topology change detected, %s\n", |
1da177e4 LT |
329 | isroot ? "propagating" : "sending tcn bpdu"); |
330 | ||
331 | if (isroot) { | |
332 | br->topology_change = 1; | |
333 | mod_timer(&br->topology_change_timer, jiffies | |
334 | + br->bridge_forward_delay + br->bridge_max_age); | |
335 | } else if (!br->topology_change_detected) { | |
336 | br_transmit_tcn(br); | |
337 | mod_timer(&br->tcn_timer, jiffies + br->bridge_hello_time); | |
338 | } | |
339 | ||
340 | br->topology_change_detected = 1; | |
341 | } | |
342 | ||
343 | /* called under bridge lock */ | |
344 | void br_config_bpdu_generation(struct net_bridge *br) | |
345 | { | |
346 | struct net_bridge_port *p; | |
347 | ||
348 | list_for_each_entry(p, &br->port_list, list) { | |
349 | if (p->state != BR_STATE_DISABLED && | |
350 | br_is_designated_port(p)) | |
351 | br_transmit_config(p); | |
352 | } | |
353 | } | |
354 | ||
355 | /* called under bridge lock */ | |
160d73b8 | 356 | static void br_reply(struct net_bridge_port *p) |
1da177e4 LT |
357 | { |
358 | br_transmit_config(p); | |
359 | } | |
360 | ||
361 | /* called under bridge lock */ | |
362 | void br_configuration_update(struct net_bridge *br) | |
363 | { | |
364 | br_root_selection(br); | |
365 | br_designated_port_selection(br); | |
366 | } | |
367 | ||
368 | /* called under bridge lock */ | |
369 | void br_become_designated_port(struct net_bridge_port *p) | |
370 | { | |
371 | struct net_bridge *br; | |
372 | ||
373 | br = p->br; | |
374 | p->designated_root = br->designated_root; | |
375 | p->designated_cost = br->root_path_cost; | |
376 | p->designated_bridge = br->bridge_id; | |
377 | p->designated_port = p->port_id; | |
378 | } | |
379 | ||
380 | ||
381 | /* called under bridge lock */ | |
382 | static void br_make_blocking(struct net_bridge_port *p) | |
383 | { | |
384 | if (p->state != BR_STATE_DISABLED && | |
385 | p->state != BR_STATE_BLOCKING) { | |
386 | if (p->state == BR_STATE_FORWARDING || | |
387 | p->state == BR_STATE_LEARNING) | |
388 | br_topology_change_detection(p->br); | |
389 | ||
390 | p->state = BR_STATE_BLOCKING; | |
391 | br_log_state(p); | |
4ecb961c | 392 | br_ifinfo_notify(RTM_NEWLINK, p); |
393 | ||
1da177e4 LT |
394 | del_timer(&p->forward_delay_timer); |
395 | } | |
396 | } | |
397 | ||
398 | /* called under bridge lock */ | |
399 | static void br_make_forwarding(struct net_bridge_port *p) | |
400 | { | |
ef647f13 | 401 | struct net_bridge *br = p->br; |
9cde0708 | 402 | |
ef647f13 SH |
403 | if (p->state != BR_STATE_BLOCKING) |
404 | return; | |
405 | ||
a461c029 | 406 | if (br->stp_enabled == BR_NO_STP || br->forward_delay == 0) { |
ef647f13 SH |
407 | p->state = BR_STATE_FORWARDING; |
408 | br_topology_change_detection(br); | |
409 | del_timer(&p->forward_delay_timer); | |
160d73b8 | 410 | } else if (br->stp_enabled == BR_KERNEL_STP) |
ef647f13 SH |
411 | p->state = BR_STATE_LISTENING; |
412 | else | |
413 | p->state = BR_STATE_LEARNING; | |
414 | ||
3fe2d7c7 | 415 | br_multicast_enable_port(p); |
ef647f13 | 416 | br_log_state(p); |
4ecb961c | 417 | br_ifinfo_notify(RTM_NEWLINK, p); |
ef647f13 SH |
418 | |
419 | if (br->forward_delay != 0) | |
420 | mod_timer(&p->forward_delay_timer, jiffies + br->forward_delay); | |
1da177e4 LT |
421 | } |
422 | ||
423 | /* called under bridge lock */ | |
424 | void br_port_state_selection(struct net_bridge *br) | |
425 | { | |
426 | struct net_bridge_port *p; | |
1faa4356 | 427 | unsigned int liveports = 0; |
1da177e4 LT |
428 | |
429 | list_for_each_entry(p, &br->port_list, list) { | |
1faa4356 | 430 | if (p->state == BR_STATE_DISABLED) |
431 | continue; | |
432 | ||
b03b6dd5 VD |
433 | /* Don't change port states if userspace is handling STP */ |
434 | if (br->stp_enabled != BR_USER_STP) { | |
435 | if (p->port_no == br->root_port) { | |
436 | p->config_pending = 0; | |
437 | p->topology_change_ack = 0; | |
438 | br_make_forwarding(p); | |
439 | } else if (br_is_designated_port(p)) { | |
440 | del_timer(&p->message_age_timer); | |
441 | br_make_forwarding(p); | |
442 | } else { | |
443 | p->config_pending = 0; | |
444 | p->topology_change_ack = 0; | |
445 | br_make_blocking(p); | |
446 | } | |
1da177e4 LT |
447 | } |
448 | ||
1faa4356 | 449 | if (p->state == BR_STATE_FORWARDING) |
450 | ++liveports; | |
1da177e4 | 451 | } |
1faa4356 | 452 | |
453 | if (liveports == 0) | |
454 | netif_carrier_off(br->dev); | |
455 | else | |
456 | netif_carrier_on(br->dev); | |
1da177e4 LT |
457 | } |
458 | ||
459 | /* called under bridge lock */ | |
160d73b8 | 460 | static void br_topology_change_acknowledge(struct net_bridge_port *p) |
1da177e4 LT |
461 | { |
462 | p->topology_change_ack = 1; | |
463 | br_transmit_config(p); | |
464 | } | |
465 | ||
466 | /* called under bridge lock */ | |
160d73b8 | 467 | void br_received_config_bpdu(struct net_bridge_port *p, |
468 | const struct br_config_bpdu *bpdu) | |
1da177e4 LT |
469 | { |
470 | struct net_bridge *br; | |
471 | int was_root; | |
9d6f229f | 472 | |
1da177e4 LT |
473 | br = p->br; |
474 | was_root = br_is_root_bridge(br); | |
475 | ||
476 | if (br_supersedes_port_info(p, bpdu)) { | |
477 | br_record_config_information(p, bpdu); | |
478 | br_configuration_update(br); | |
479 | br_port_state_selection(br); | |
480 | ||
481 | if (!br_is_root_bridge(br) && was_root) { | |
482 | del_timer(&br->hello_timer); | |
483 | if (br->topology_change_detected) { | |
484 | del_timer(&br->topology_change_timer); | |
485 | br_transmit_tcn(br); | |
486 | ||
9d6f229f | 487 | mod_timer(&br->tcn_timer, |
1da177e4 LT |
488 | jiffies + br->bridge_hello_time); |
489 | } | |
490 | } | |
491 | ||
492 | if (p->port_no == br->root_port) { | |
493 | br_record_config_timeout_values(br, bpdu); | |
494 | br_config_bpdu_generation(br); | |
495 | if (bpdu->topology_change_ack) | |
496 | br_topology_change_acknowledged(br); | |
497 | } | |
9d6f229f YH |
498 | } else if (br_is_designated_port(p)) { |
499 | br_reply(p); | |
1da177e4 LT |
500 | } |
501 | } | |
502 | ||
503 | /* called under bridge lock */ | |
504 | void br_received_tcn_bpdu(struct net_bridge_port *p) | |
505 | { | |
506 | if (br_is_designated_port(p)) { | |
28a16c97 | 507 | br_info(p->br, "port %u(%s) received tcn bpdu\n", |
95c96174 | 508 | (unsigned int) p->port_no, p->dev->name); |
1da177e4 LT |
509 | |
510 | br_topology_change_detection(p->br); | |
511 | br_topology_change_acknowledge(p); | |
512 | } | |
513 | } | |
14f98f25 | 514 | |
515 | /* Change bridge STP parameter */ | |
516 | int br_set_hello_time(struct net_bridge *br, unsigned long val) | |
517 | { | |
518 | unsigned long t = clock_t_to_jiffies(val); | |
519 | ||
520 | if (t < BR_MIN_HELLO_TIME || t > BR_MAX_HELLO_TIME) | |
521 | return -ERANGE; | |
522 | ||
523 | spin_lock_bh(&br->lock); | |
524 | br->bridge_hello_time = t; | |
525 | if (br_is_root_bridge(br)) | |
526 | br->hello_time = br->bridge_hello_time; | |
527 | spin_unlock_bh(&br->lock); | |
528 | return 0; | |
529 | } | |
530 | ||
531 | int br_set_max_age(struct net_bridge *br, unsigned long val) | |
532 | { | |
533 | unsigned long t = clock_t_to_jiffies(val); | |
534 | ||
535 | if (t < BR_MIN_MAX_AGE || t > BR_MAX_MAX_AGE) | |
536 | return -ERANGE; | |
537 | ||
538 | spin_lock_bh(&br->lock); | |
539 | br->bridge_max_age = t; | |
540 | if (br_is_root_bridge(br)) | |
541 | br->max_age = br->bridge_max_age; | |
542 | spin_unlock_bh(&br->lock); | |
543 | return 0; | |
544 | ||
545 | } | |
546 | ||
be4f154d HX |
547 | void __br_set_forward_delay(struct net_bridge *br, unsigned long t) |
548 | { | |
549 | br->bridge_forward_delay = t; | |
550 | if (br_is_root_bridge(br)) | |
551 | br->forward_delay = br->bridge_forward_delay; | |
552 | } | |
553 | ||
14f98f25 | 554 | int br_set_forward_delay(struct net_bridge *br, unsigned long val) |
555 | { | |
556 | unsigned long t = clock_t_to_jiffies(val); | |
be4f154d | 557 | int err = -ERANGE; |
14f98f25 | 558 | |
be4f154d | 559 | spin_lock_bh(&br->lock); |
14f98f25 | 560 | if (br->stp_enabled != BR_NO_STP && |
561 | (t < BR_MIN_FORWARD_DELAY || t > BR_MAX_FORWARD_DELAY)) | |
be4f154d | 562 | goto unlock; |
14f98f25 | 563 | |
be4f154d HX |
564 | __br_set_forward_delay(br, t); |
565 | err = 0; | |
566 | ||
567 | unlock: | |
14f98f25 | 568 | spin_unlock_bh(&br->lock); |
be4f154d | 569 | return err; |
14f98f25 | 570 | } |