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