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