xref: /openbmc/linux/net/bridge/br_stp.c (revision b34e08d5) 
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 /* 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 */
53 static int br_should_become_root_port(const struct net_bridge_port *p,
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 
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 
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) {
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
131 			root_port = p->port_no;
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 
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);
185 		bpdu.message_age = (jiffies - root->designated_age)
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;
196 		mod_timer(&p->hold_timer,
197 			  round_jiffies(jiffies + BR_HOLD_TIME));
198 	}
199 }
200 
201 /* called under bridge lock */
202 static void br_record_config_information(struct net_bridge_port *p,
203 					 const struct br_config_bpdu *bpdu)
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;
209 	p->designated_age = jiffies - bpdu->message_age;
210 
211 	mod_timer(&p->message_age_timer, jiffies
212 		  + (bpdu->max_age - bpdu->message_age));
213 }
214 
215 /* called under bridge lock */
216 static void br_record_config_timeout_values(struct net_bridge *br,
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 {
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);
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 */
282 static int br_supersedes_port_info(const struct net_bridge_port *p,
283 				   const struct br_config_bpdu *bpdu)
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 */
314 static void br_topology_change_acknowledged(struct net_bridge *br)
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 
325 	if (br->stp_enabled != BR_KERNEL_STP)
326 		return;
327 
328 	br_info(br, "topology change detected, %s\n",
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 */
356 static void br_reply(struct net_bridge_port *p)
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);
392 		br_ifinfo_notify(RTM_NEWLINK, p);
393 
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 {
401 	struct net_bridge *br = p->br;
402 
403 	if (p->state != BR_STATE_BLOCKING)
404 		return;
405 
406 	if (br->stp_enabled == BR_NO_STP || br->forward_delay == 0) {
407 		p->state = BR_STATE_FORWARDING;
408 		br_topology_change_detection(br);
409 		del_timer(&p->forward_delay_timer);
410 	} else if (br->stp_enabled == BR_KERNEL_STP)
411 		p->state = BR_STATE_LISTENING;
412 	else
413 		p->state = BR_STATE_LEARNING;
414 
415 	br_multicast_enable_port(p);
416 	br_log_state(p);
417 	br_ifinfo_notify(RTM_NEWLINK, p);
418 
419 	if (br->forward_delay != 0)
420 		mod_timer(&p->forward_delay_timer, jiffies + br->forward_delay);
421 }
422 
423 /* called under bridge lock */
424 void br_port_state_selection(struct net_bridge *br)
425 {
426 	struct net_bridge_port *p;
427 	unsigned int liveports = 0;
428 
429 	list_for_each_entry(p, &br->port_list, list) {
430 		if (p->state == BR_STATE_DISABLED)
431 			continue;
432 
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 			}
447 		}
448 
449 		if (p->state == BR_STATE_FORWARDING)
450 			++liveports;
451 	}
452 
453 	if (liveports == 0)
454 		netif_carrier_off(br->dev);
455 	else
456 		netif_carrier_on(br->dev);
457 }
458 
459 /* called under bridge lock */
460 static void br_topology_change_acknowledge(struct net_bridge_port *p)
461 {
462 	p->topology_change_ack = 1;
463 	br_transmit_config(p);
464 }
465 
466 /* called under bridge lock */
467 void br_received_config_bpdu(struct net_bridge_port *p,
468 			     const struct br_config_bpdu *bpdu)
469 {
470 	struct net_bridge *br;
471 	int was_root;
472 
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 
487 				mod_timer(&br->tcn_timer,
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 		}
498 	} else if (br_is_designated_port(p)) {
499 		br_reply(p);
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)) {
507 		br_info(p->br, "port %u(%s) received tcn bpdu\n",
508 			(unsigned int) p->port_no, p->dev->name);
509 
510 		br_topology_change_detection(p->br);
511 		br_topology_change_acknowledge(p);
512 	}
513 }
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 
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 
554 int br_set_forward_delay(struct net_bridge *br, unsigned long val)
555 {
556 	unsigned long t = clock_t_to_jiffies(val);
557 	int err = -ERANGE;
558 
559 	spin_lock_bh(&br->lock);
560 	if (br->stp_enabled != BR_NO_STP &&
561 	    (t < BR_MIN_FORWARD_DELAY || t > BR_MAX_FORWARD_DELAY))
562 		goto unlock;
563 
564 	__br_set_forward_delay(br, t);
565 	err = 0;
566 
567 unlock:
568 	spin_unlock_bh(&br->lock);
569 	return err;
570 }
571