xref: /openbmc/linux/net/bridge/br_stp.c (revision e1f7c9ee) 
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 
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 
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 */
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 */
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 
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
361 static void br_reply(struct net_bridge_port *p)
362 {
363 	br_transmit_config(p);
364 }
365 
366 /* called under bridge lock */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 
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 
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 
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