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
24static 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
32void 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
39void br_set_state(struct net_bridge_port *p, unsigned int state)
40{
41	p->state = state;
42}
43
44/* called under bridge lock */
45struct 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 */
58static 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
108static 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 */
124static 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 */
152void 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 */
167void 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 */
207static 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 */
221static 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 */
231void 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 */
244static 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 */
274static 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 */
287static 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 */
319static 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 */
326void 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 */
349void 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 */
361static void br_reply(struct net_bridge_port *p)
362{
363	br_transmit_config(p);
364}
365
366/* called under bridge lock */
367void 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 */
374void 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 */
387static 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 */
404static 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 */
429void 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 */
465static 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 */
472void 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 */
509void 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 */
521int 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
536int 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
552void __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
559int 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
572unlock:
573	spin_unlock_bh(&br->lock);
574	return err;
575}
576