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