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