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.
21  */
22 #define MESSAGE_AGE_INCR	((HZ < 256) ? 1 : (HZ/256))
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) entering %s state\n",
35 		(unsigned) p->port_no, p->dev->name,
36 		br_port_state_names[p->state]);
37 }
38 
39 /* called under bridge lock */
br_get_port(struct net_bridge * br,u16 port_no)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 */
br_should_become_root_port(const struct net_bridge_port * p,u16 root_port)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 /* called under bridge lock */
br_root_selection(struct net_bridge * br)104 static void br_root_selection(struct net_bridge *br)
105 {
106 	struct net_bridge_port *p;
107 	u16 root_port = 0;
108 
109 	list_for_each_entry(p, &br->port_list, list) {
110 		if (br_should_become_root_port(p, root_port))
111 			root_port = p->port_no;
112 
113 	}
114 
115 	br->root_port = root_port;
116 
117 	if (!root_port) {
118 		br->designated_root = br->bridge_id;
119 		br->root_path_cost = 0;
120 	} else {
121 		p = br_get_port(br, root_port);
122 		br->designated_root = p->designated_root;
123 		br->root_path_cost = p->designated_cost + p->path_cost;
124 	}
125 }
126 
127 /* called under bridge lock */
br_become_root_bridge(struct net_bridge * br)128 void br_become_root_bridge(struct net_bridge *br)
129 {
130 	br->max_age = br->bridge_max_age;
131 	br->hello_time = br->bridge_hello_time;
132 	br->forward_delay = br->bridge_forward_delay;
133 	br_topology_change_detection(br);
134 	del_timer(&br->tcn_timer);
135 
136 	if (br->dev->flags & IFF_UP) {
137 		br_config_bpdu_generation(br);
138 		mod_timer(&br->hello_timer, jiffies + br->hello_time);
139 	}
140 }
141 
142 /* called under bridge lock */
br_transmit_config(struct net_bridge_port * p)143 void br_transmit_config(struct net_bridge_port *p)
144 {
145 	struct br_config_bpdu bpdu;
146 	struct net_bridge *br;
147 
148 
149 	if (timer_pending(&p->hold_timer)) {
150 		p->config_pending = 1;
151 		return;
152 	}
153 
154 	br = p->br;
155 
156 	bpdu.topology_change = br->topology_change;
157 	bpdu.topology_change_ack = p->topology_change_ack;
158 	bpdu.root = br->designated_root;
159 	bpdu.root_path_cost = br->root_path_cost;
160 	bpdu.bridge_id = br->bridge_id;
161 	bpdu.port_id = p->port_id;
162 	if (br_is_root_bridge(br))
163 		bpdu.message_age = 0;
164 	else {
165 		struct net_bridge_port *root
166 			= br_get_port(br, br->root_port);
167 		bpdu.message_age = br->max_age
168 			- (root->message_age_timer.expires - jiffies)
169 			+ MESSAGE_AGE_INCR;
170 	}
171 	bpdu.max_age = br->max_age;
172 	bpdu.hello_time = br->hello_time;
173 	bpdu.forward_delay = br->forward_delay;
174 
175 	if (bpdu.message_age < br->max_age) {
176 		br_send_config_bpdu(p, &bpdu);
177 		p->topology_change_ack = 0;
178 		p->config_pending = 0;
179 		mod_timer(&p->hold_timer,
180 			  round_jiffies(jiffies + BR_HOLD_TIME));
181 	}
182 }
183 
184 /* called under bridge lock */
br_record_config_information(struct net_bridge_port * p,const struct br_config_bpdu * bpdu)185 static inline void br_record_config_information(struct net_bridge_port *p,
186 						const struct br_config_bpdu *bpdu)
187 {
188 	p->designated_root = bpdu->root;
189 	p->designated_cost = bpdu->root_path_cost;
190 	p->designated_bridge = bpdu->bridge_id;
191 	p->designated_port = bpdu->port_id;
192 
193 	mod_timer(&p->message_age_timer, jiffies
194 		  + (p->br->max_age - bpdu->message_age));
195 }
196 
197 /* called under bridge lock */
br_record_config_timeout_values(struct net_bridge * br,const struct br_config_bpdu * bpdu)198 static inline void br_record_config_timeout_values(struct net_bridge *br,
199 					    const struct br_config_bpdu *bpdu)
200 {
201 	br->max_age = bpdu->max_age;
202 	br->hello_time = bpdu->hello_time;
203 	br->forward_delay = bpdu->forward_delay;
204 	br->topology_change = bpdu->topology_change;
205 }
206 
207 /* called under bridge lock */
br_transmit_tcn(struct net_bridge * br)208 void br_transmit_tcn(struct net_bridge *br)
209 {
210 	br_send_tcn_bpdu(br_get_port(br, br->root_port));
211 }
212 
213 /* called under bridge lock */
br_should_become_designated_port(const struct net_bridge_port * p)214 static int br_should_become_designated_port(const struct net_bridge_port *p)
215 {
216 	struct net_bridge *br;
217 	int t;
218 
219 	br = p->br;
220 	if (br_is_designated_port(p))
221 		return 1;
222 
223 	if (memcmp(&p->designated_root, &br->designated_root, 8))
224 		return 1;
225 
226 	if (br->root_path_cost < p->designated_cost)
227 		return 1;
228 	else if (br->root_path_cost > p->designated_cost)
229 		return 0;
230 
231 	t = memcmp(&br->bridge_id, &p->designated_bridge, 8);
232 	if (t < 0)
233 		return 1;
234 	else if (t > 0)
235 		return 0;
236 
237 	if (p->port_id < p->designated_port)
238 		return 1;
239 
240 	return 0;
241 }
242 
243 /* called under bridge lock */
br_designated_port_selection(struct net_bridge * br)244 static void br_designated_port_selection(struct net_bridge *br)
245 {
246 	struct net_bridge_port *p;
247 
248 	list_for_each_entry(p, &br->port_list, list) {
249 		if (p->state != BR_STATE_DISABLED &&
250 		    br_should_become_designated_port(p))
251 			br_become_designated_port(p);
252 
253 	}
254 }
255 
256 /* called under bridge lock */
br_supersedes_port_info(struct net_bridge_port * p,struct br_config_bpdu * bpdu)257 static int br_supersedes_port_info(struct net_bridge_port *p, struct br_config_bpdu *bpdu)
258 {
259 	int t;
260 
261 	t = memcmp(&bpdu->root, &p->designated_root, 8);
262 	if (t < 0)
263 		return 1;
264 	else if (t > 0)
265 		return 0;
266 
267 	if (bpdu->root_path_cost < p->designated_cost)
268 		return 1;
269 	else if (bpdu->root_path_cost > p->designated_cost)
270 		return 0;
271 
272 	t = memcmp(&bpdu->bridge_id, &p->designated_bridge, 8);
273 	if (t < 0)
274 		return 1;
275 	else if (t > 0)
276 		return 0;
277 
278 	if (memcmp(&bpdu->bridge_id, &p->br->bridge_id, 8))
279 		return 1;
280 
281 	if (bpdu->port_id <= p->designated_port)
282 		return 1;
283 
284 	return 0;
285 }
286 
287 /* called under bridge lock */
br_topology_change_acknowledged(struct net_bridge * br)288 static inline void br_topology_change_acknowledged(struct net_bridge *br)
289 {
290 	br->topology_change_detected = 0;
291 	del_timer(&br->tcn_timer);
292 }
293 
294 /* called under bridge lock */
br_topology_change_detection(struct net_bridge * br)295 void br_topology_change_detection(struct net_bridge *br)
296 {
297 	int isroot = br_is_root_bridge(br);
298 
299 	if (br->stp_enabled != BR_KERNEL_STP)
300 		return;
301 
302 	br_info(br, "topology change detected, %s\n",
303 		isroot ? "propagating" : "sending tcn bpdu");
304 
305 	if (isroot) {
306 		br->topology_change = 1;
307 		mod_timer(&br->topology_change_timer, jiffies
308 			  + br->bridge_forward_delay + br->bridge_max_age);
309 	} else if (!br->topology_change_detected) {
310 		br_transmit_tcn(br);
311 		mod_timer(&br->tcn_timer, jiffies + br->bridge_hello_time);
312 	}
313 
314 	br->topology_change_detected = 1;
315 }
316 
317 /* called under bridge lock */
br_config_bpdu_generation(struct net_bridge * br)318 void br_config_bpdu_generation(struct net_bridge *br)
319 {
320 	struct net_bridge_port *p;
321 
322 	list_for_each_entry(p, &br->port_list, list) {
323 		if (p->state != BR_STATE_DISABLED &&
324 		    br_is_designated_port(p))
325 			br_transmit_config(p);
326 	}
327 }
328 
329 /* called under bridge lock */
br_reply(struct net_bridge_port * p)330 static inline void br_reply(struct net_bridge_port *p)
331 {
332 	br_transmit_config(p);
333 }
334 
335 /* called under bridge lock */
br_configuration_update(struct net_bridge * br)336 void br_configuration_update(struct net_bridge *br)
337 {
338 	br_root_selection(br);
339 	br_designated_port_selection(br);
340 }
341 
342 /* called under bridge lock */
br_become_designated_port(struct net_bridge_port * p)343 void br_become_designated_port(struct net_bridge_port *p)
344 {
345 	struct net_bridge *br;
346 
347 	br = p->br;
348 	p->designated_root = br->designated_root;
349 	p->designated_cost = br->root_path_cost;
350 	p->designated_bridge = br->bridge_id;
351 	p->designated_port = p->port_id;
352 }
353 
354 
355 /* called under bridge lock */
br_make_blocking(struct net_bridge_port * p)356 static void br_make_blocking(struct net_bridge_port *p)
357 {
358 	if (p->state != BR_STATE_DISABLED &&
359 	    p->state != BR_STATE_BLOCKING) {
360 		if (p->state == BR_STATE_FORWARDING ||
361 		    p->state == BR_STATE_LEARNING)
362 			br_topology_change_detection(p->br);
363 
364 		p->state = BR_STATE_BLOCKING;
365 		br_log_state(p);
366 		del_timer(&p->forward_delay_timer);
367 	}
368 }
369 
370 /* called under bridge lock */
br_make_forwarding(struct net_bridge_port * p)371 static void br_make_forwarding(struct net_bridge_port *p)
372 {
373 	struct net_bridge *br = p->br;
374 
375 	if (p->state != BR_STATE_BLOCKING)
376 		return;
377 
378 	if (br->stp_enabled == BR_NO_STP || br->forward_delay == 0) {
379 		p->state = BR_STATE_FORWARDING;
380 		br_topology_change_detection(br);
381 		del_timer(&p->forward_delay_timer);
382 	}
383 	else if (br->stp_enabled == BR_KERNEL_STP)
384 		p->state = BR_STATE_LISTENING;
385 	else
386 		p->state = BR_STATE_LEARNING;
387 
388 	br_multicast_enable_port(p);
389 
390 	br_log_state(p);
391 
392 	if (br->forward_delay != 0)
393 		mod_timer(&p->forward_delay_timer, jiffies + br->forward_delay);
394 }
395 
396 /* called under bridge lock */
br_port_state_selection(struct net_bridge * br)397 void br_port_state_selection(struct net_bridge *br)
398 {
399 	struct net_bridge_port *p;
400 	unsigned int liveports = 0;
401 
402 	/* Don't change port states if userspace is handling STP */
403 	if (br->stp_enabled == BR_USER_STP)
404 		return;
405 
406 	list_for_each_entry(p, &br->port_list, list) {
407 		if (p->state == BR_STATE_DISABLED)
408 			continue;
409 
410 		if (p->port_no == br->root_port) {
411 			p->config_pending = 0;
412 			p->topology_change_ack = 0;
413 			br_make_forwarding(p);
414 		} else if (br_is_designated_port(p)) {
415 			del_timer(&p->message_age_timer);
416 			br_make_forwarding(p);
417 		} else {
418 			p->config_pending = 0;
419 			p->topology_change_ack = 0;
420 			br_make_blocking(p);
421 		}
422 
423 		if (p->state == BR_STATE_FORWARDING)
424 			++liveports;
425 	}
426 
427 	if (liveports == 0)
428 		netif_carrier_off(br->dev);
429 	else
430 		netif_carrier_on(br->dev);
431 }
432 
433 /* called under bridge lock */
br_topology_change_acknowledge(struct net_bridge_port * p)434 static inline void br_topology_change_acknowledge(struct net_bridge_port *p)
435 {
436 	p->topology_change_ack = 1;
437 	br_transmit_config(p);
438 }
439 
440 /* called under bridge lock */
br_received_config_bpdu(struct net_bridge_port * p,struct br_config_bpdu * bpdu)441 void br_received_config_bpdu(struct net_bridge_port *p, struct br_config_bpdu *bpdu)
442 {
443 	struct net_bridge *br;
444 	int was_root;
445 
446 	br = p->br;
447 	was_root = br_is_root_bridge(br);
448 
449 	if (br_supersedes_port_info(p, bpdu)) {
450 		br_record_config_information(p, bpdu);
451 		br_configuration_update(br);
452 		br_port_state_selection(br);
453 
454 		if (!br_is_root_bridge(br) && was_root) {
455 			del_timer(&br->hello_timer);
456 			if (br->topology_change_detected) {
457 				del_timer(&br->topology_change_timer);
458 				br_transmit_tcn(br);
459 
460 				mod_timer(&br->tcn_timer,
461 					  jiffies + br->bridge_hello_time);
462 			}
463 		}
464 
465 		if (p->port_no == br->root_port) {
466 			br_record_config_timeout_values(br, bpdu);
467 			br_config_bpdu_generation(br);
468 			if (bpdu->topology_change_ack)
469 				br_topology_change_acknowledged(br);
470 		}
471 	} else if (br_is_designated_port(p)) {
472 		br_reply(p);
473 	}
474 }
475 
476 /* called under bridge lock */
br_received_tcn_bpdu(struct net_bridge_port * p)477 void br_received_tcn_bpdu(struct net_bridge_port *p)
478 {
479 	if (br_is_designated_port(p)) {
480 		br_info(p->br, "port %u(%s) received tcn bpdu\n",
481 			(unsigned) p->port_no, p->dev->name);
482 
483 		br_topology_change_detection(p->br);
484 		br_topology_change_acknowledge(p);
485 	}
486 }
487