[linux-block.git] / net / bridge / br_stp.c

/*
 *	Spanning tree protocol; generic parts
 *	Linux ethernet bridge
 *
 *	Authors:
 *	Lennert Buytenhek		<buytenh@gnu.org>
 *
 *	This program is free software; you can redistribute it and/or
 *	modify it under the terms of the GNU General Public License
 *	as published by the Free Software Foundation; either version
 *	2 of the License, or (at your option) any later version.
 */
#include <linux/kernel.h>
#include <linux/rculist.h>

#include "br_private.h"
#include "br_private_stp.h"

/* since time values in bpdu are in jiffies and then scaled (1/256)
 * before sending, make sure that is at least one STP tick.
 */
#define MESSAGE_AGE_INCR	((HZ / 256) + 1)

static const char *const br_port_state_names[] = {
	[BR_STATE_DISABLED] = "disabled",
	[BR_STATE_LISTENING] = "listening",
	[BR_STATE_LEARNING] = "learning",
	[BR_STATE_FORWARDING] = "forwarding",
	[BR_STATE_BLOCKING] = "blocking",
};

void br_log_state(const struct net_bridge_port *p)
{
	br_info(p->br, "port %u(%s) entered %s state\n",
		(unsigned int) p->port_no, p->dev->name,
		br_port_state_names[p->state]);
}

/* called under bridge lock */
struct net_bridge_port *br_get_port(struct net_bridge *br, u16 port_no)
{
	struct net_bridge_port *p;

	list_for_each_entry_rcu(p, &br->port_list, list) {
		if (p->port_no == port_no)
			return p;
	}

	return NULL;
}

/* called under bridge lock */
static int br_should_become_root_port(const struct net_bridge_port *p,
				      u16 root_port)
{
	struct net_bridge *br;
	struct net_bridge_port *rp;
	int t;

	br = p->br;
	if (p->state == BR_STATE_DISABLED ||
	    br_is_designated_port(p))
		return 0;

	if (memcmp(&br->bridge_id, &p->designated_root, 8) <= 0)
		return 0;

	if (!root_port)
		return 1;

	rp = br_get_port(br, root_port);

	t = memcmp(&p->designated_root, &rp->designated_root, 8);
	if (t < 0)
		return 1;
	else if (t > 0)
		return 0;

	if (p->designated_cost + p->path_cost <
	    rp->designated_cost + rp->path_cost)
		return 1;
	else if (p->designated_cost + p->path_cost >
		 rp->designated_cost + rp->path_cost)
		return 0;

	t = memcmp(&p->designated_bridge, &rp->designated_bridge, 8);
	if (t < 0)
		return 1;
	else if (t > 0)
		return 0;

	if (p->designated_port < rp->designated_port)
		return 1;
	else if (p->designated_port > rp->designated_port)
		return 0;

	if (p->port_id < rp->port_id)
		return 1;

	return 0;
}

static void br_root_port_block(const struct net_bridge *br,
			       struct net_bridge_port *p)
{

	br_notice(br, "port %u(%s) tried to become root port (blocked)",
		  (unsigned int) p->port_no, p->dev->name);

	p->state = BR_STATE_LISTENING;
	br_log_state(p);
	br_ifinfo_notify(RTM_NEWLINK, p);

	if (br->forward_delay > 0)
		mod_timer(&p->forward_delay_timer, jiffies + br->forward_delay);
}

/* called under bridge lock */
static void br_root_selection(struct net_bridge *br)
{
	struct net_bridge_port *p;
	u16 root_port = 0;

	list_for_each_entry(p, &br->port_list, list) {
		if (!br_should_become_root_port(p, root_port))
			continue;

		if (p->flags & BR_ROOT_BLOCK)
			br_root_port_block(br, p);
		else
			root_port = p->port_no;
	}

	br->root_port = root_port;

	if (!root_port) {
		br->designated_root = br->bridge_id;
		br->root_path_cost = 0;
	} else {
		p = br_get_port(br, root_port);
		br->designated_root = p->designated_root;
		br->root_path_cost = p->designated_cost + p->path_cost;
	}
}

/* called under bridge lock */
void br_become_root_bridge(struct net_bridge *br)
{
	br->max_age = br->bridge_max_age;
	br->hello_time = br->bridge_hello_time;
	br->forward_delay = br->bridge_forward_delay;
	br_topology_change_detection(br);
	del_timer(&br->tcn_timer);

	if (br->dev->flags & IFF_UP) {
		br_config_bpdu_generation(br);
		mod_timer(&br->hello_timer, jiffies + br->hello_time);
	}
}

/* called under bridge lock */
void br_transmit_config(struct net_bridge_port *p)
{
	struct br_config_bpdu bpdu;
	struct net_bridge *br;

	if (timer_pending(&p->hold_timer)) {
		p->config_pending = 1;
		return;
	}

	br = p->br;

	bpdu.topology_change = br->topology_change;
	bpdu.topology_change_ack = p->topology_change_ack;
	bpdu.root = br->designated_root;
	bpdu.root_path_cost = br->root_path_cost;
	bpdu.bridge_id = br->bridge_id;
	bpdu.port_id = p->port_id;
	if (br_is_root_bridge(br))
		bpdu.message_age = 0;
	else {
		struct net_bridge_port *root
			= br_get_port(br, br->root_port);
		bpdu.message_age = (jiffies - root->designated_age)
			+ MESSAGE_AGE_INCR;
	}
	bpdu.max_age = br->max_age;
	bpdu.hello_time = br->hello_time;
	bpdu.forward_delay = br->forward_delay;

	if (bpdu.message_age < br->max_age) {
		br_send_config_bpdu(p, &bpdu);
		p->topology_change_ack = 0;
		p->config_pending = 0;
		mod_timer(&p->hold_timer,
			  round_jiffies(jiffies + BR_HOLD_TIME));
	}
}

/* called under bridge lock */
static void br_record_config_information(struct net_bridge_port *p,
					 const struct br_config_bpdu *bpdu)
{
	p->designated_root = bpdu->root;
	p->designated_cost = bpdu->root_path_cost;
	p->designated_bridge = bpdu->bridge_id;
	p->designated_port = bpdu->port_id;
	p->designated_age = jiffies - bpdu->message_age;

	mod_timer(&p->message_age_timer, jiffies
		  + (p->br->max_age - bpdu->message_age));
}

/* called under bridge lock */
static void br_record_config_timeout_values(struct net_bridge *br,
					    const struct br_config_bpdu *bpdu)
{
	br->max_age = bpdu->max_age;
	br->hello_time = bpdu->hello_time;
	br->forward_delay = bpdu->forward_delay;
	br->topology_change = bpdu->topology_change;
}

/* called under bridge lock */
void br_transmit_tcn(struct net_bridge *br)
{
	br_send_tcn_bpdu(br_get_port(br, br->root_port));
}

/* called under bridge lock */
static int br_should_become_designated_port(const struct net_bridge_port *p)
{
	struct net_bridge *br;
	int t;

	br = p->br;
	if (br_is_designated_port(p))
		return 1;

	if (memcmp(&p->designated_root, &br->designated_root, 8))
		return 1;

	if (br->root_path_cost < p->designated_cost)
		return 1;
	else if (br->root_path_cost > p->designated_cost)
		return 0;

	t = memcmp(&br->bridge_id, &p->designated_bridge, 8);
	if (t < 0)
		return 1;
	else if (t > 0)
		return 0;

	if (p->port_id < p->designated_port)
		return 1;

	return 0;
}

/* called under bridge lock */
static void br_designated_port_selection(struct net_bridge *br)
{
	struct net_bridge_port *p;

	list_for_each_entry(p, &br->port_list, list) {
		if (p->state != BR_STATE_DISABLED &&
		    br_should_become_designated_port(p))
			br_become_designated_port(p);

	}
}

/* called under bridge lock */
static int br_supersedes_port_info(const struct net_bridge_port *p,
				   const struct br_config_bpdu *bpdu)
{
	int t;

	t = memcmp(&bpdu->root, &p->designated_root, 8);
	if (t < 0)
		return 1;
	else if (t > 0)
		return 0;

	if (bpdu->root_path_cost < p->designated_cost)
		return 1;
	else if (bpdu->root_path_cost > p->designated_cost)
		return 0;

	t = memcmp(&bpdu->bridge_id, &p->designated_bridge, 8);
	if (t < 0)
		return 1;
	else if (t > 0)
		return 0;

	if (memcmp(&bpdu->bridge_id, &p->br->bridge_id, 8))
		return 1;

	if (bpdu->port_id <= p->designated_port)
		return 1;

	return 0;
}

/* called under bridge lock */
static void br_topology_change_acknowledged(struct net_bridge *br)
{
	br->topology_change_detected = 0;
	del_timer(&br->tcn_timer);
}

/* called under bridge lock */
void br_topology_change_detection(struct net_bridge *br)
{
	int isroot = br_is_root_bridge(br);

	if (br->stp_enabled != BR_KERNEL_STP)
		return;

	br_info(br, "topology change detected, %s\n",
		isroot ? "propagating" : "sending tcn bpdu");

	if (isroot) {
		br->topology_change = 1;
		mod_timer(&br->topology_change_timer, jiffies
			  + br->bridge_forward_delay + br->bridge_max_age);
	} else if (!br->topology_change_detected) {
		br_transmit_tcn(br);
		mod_timer(&br->tcn_timer, jiffies + br->bridge_hello_time);
	}

	br->topology_change_detected = 1;
}

/* called under bridge lock */
void br_config_bpdu_generation(struct net_bridge *br)
{
	struct net_bridge_port *p;

	list_for_each_entry(p, &br->port_list, list) {
		if (p->state != BR_STATE_DISABLED &&
		    br_is_designated_port(p))
			br_transmit_config(p);
	}
}

/* called under bridge lock */
static void br_reply(struct net_bridge_port *p)
{
	br_transmit_config(p);
}

/* called under bridge lock */
void br_configuration_update(struct net_bridge *br)
{
	br_root_selection(br);
	br_designated_port_selection(br);
}

/* called under bridge lock */
void br_become_designated_port(struct net_bridge_port *p)
{
	struct net_bridge *br;

	br = p->br;
	p->designated_root = br->designated_root;
	p->designated_cost = br->root_path_cost;
	p->designated_bridge = br->bridge_id;
	p->designated_port = p->port_id;
}


/* called under bridge lock */
static void br_make_blocking(struct net_bridge_port *p)
{
	if (p->state != BR_STATE_DISABLED &&
	    p->state != BR_STATE_BLOCKING) {
		if (p->state == BR_STATE_FORWARDING ||
		    p->state == BR_STATE_LEARNING)
			br_topology_change_detection(p->br);

		p->state = BR_STATE_BLOCKING;
		br_log_state(p);
		br_ifinfo_notify(RTM_NEWLINK, p);

		del_timer(&p->forward_delay_timer);
	}
}

/* called under bridge lock */
static void br_make_forwarding(struct net_bridge_port *p)
{
	struct net_bridge *br = p->br;

	if (p->state != BR_STATE_BLOCKING)
		return;

	if (br->stp_enabled == BR_NO_STP || br->forward_delay == 0) {
		p->state = BR_STATE_FORWARDING;
		br_topology_change_detection(br);
		del_timer(&p->forward_delay_timer);
	} else if (br->stp_enabled == BR_KERNEL_STP)
		p->state = BR_STATE_LISTENING;
	else
		p->state = BR_STATE_LEARNING;

	br_multicast_enable_port(p);
	br_log_state(p);
	br_ifinfo_notify(RTM_NEWLINK, p);

	if (br->forward_delay != 0)
		mod_timer(&p->forward_delay_timer, jiffies + br->forward_delay);
}

/* called under bridge lock */
void br_port_state_selection(struct net_bridge *br)
{
	struct net_bridge_port *p;
	unsigned int liveports = 0;

	list_for_each_entry(p, &br->port_list, list) {
		if (p->state == BR_STATE_DISABLED)
			continue;

		/* Don't change port states if userspace is handling STP */
		if (br->stp_enabled != BR_USER_STP) {
			if (p->port_no == br->root_port) {
				p->config_pending = 0;
				p->topology_change_ack = 0;
				br_make_forwarding(p);
			} else if (br_is_designated_port(p)) {
				del_timer(&p->message_age_timer);
				br_make_forwarding(p);
			} else {
				p->config_pending = 0;
				p->topology_change_ack = 0;
				br_make_blocking(p);
			}
		}

		if (p->state == BR_STATE_FORWARDING)
			++liveports;
	}

	if (liveports == 0)
		netif_carrier_off(br->dev);
	else
		netif_carrier_on(br->dev);
}

/* called under bridge lock */
static void br_topology_change_acknowledge(struct net_bridge_port *p)
{
	p->topology_change_ack = 1;
	br_transmit_config(p);
}

/* called under bridge lock */
void br_received_config_bpdu(struct net_bridge_port *p,
			     const struct br_config_bpdu *bpdu)
{
	struct net_bridge *br;
	int was_root;

	br = p->br;
	was_root = br_is_root_bridge(br);

	if (br_supersedes_port_info(p, bpdu)) {
		br_record_config_information(p, bpdu);
		br_configuration_update(br);
		br_port_state_selection(br);

		if (!br_is_root_bridge(br) && was_root) {
			del_timer(&br->hello_timer);
			if (br->topology_change_detected) {
				del_timer(&br->topology_change_timer);
				br_transmit_tcn(br);

				mod_timer(&br->tcn_timer,
					  jiffies + br->bridge_hello_time);
			}
		}

		if (p->port_no == br->root_port) {
			br_record_config_timeout_values(br, bpdu);
			br_config_bpdu_generation(br);
			if (bpdu->topology_change_ack)
				br_topology_change_acknowledged(br);
		}
	} else if (br_is_designated_port(p)) {
		br_reply(p);
	}
}

/* called under bridge lock */
void br_received_tcn_bpdu(struct net_bridge_port *p)
{
	if (br_is_designated_port(p)) {
		br_info(p->br, "port %u(%s) received tcn bpdu\n",
			(unsigned int) p->port_no, p->dev->name);

		br_topology_change_detection(p->br);
		br_topology_change_acknowledge(p);
	}
}

/* Change bridge STP parameter */
int br_set_hello_time(struct net_bridge *br, unsigned long val)
{
	unsigned long t = clock_t_to_jiffies(val);

	if (t < BR_MIN_HELLO_TIME || t > BR_MAX_HELLO_TIME)
		return -ERANGE;

	spin_lock_bh(&br->lock);
	br->bridge_hello_time = t;
	if (br_is_root_bridge(br))
		br->hello_time = br->bridge_hello_time;
	spin_unlock_bh(&br->lock);
	return 0;
}

int br_set_max_age(struct net_bridge *br, unsigned long val)
{
	unsigned long t = clock_t_to_jiffies(val);

	if (t < BR_MIN_MAX_AGE || t > BR_MAX_MAX_AGE)
		return -ERANGE;

	spin_lock_bh(&br->lock);
	br->bridge_max_age = t;
	if (br_is_root_bridge(br))
		br->max_age = br->bridge_max_age;
	spin_unlock_bh(&br->lock);
	return 0;

}

int br_set_forward_delay(struct net_bridge *br, unsigned long val)
{
	unsigned long t = clock_t_to_jiffies(val);

	if (br->stp_enabled != BR_NO_STP &&
	    (t < BR_MIN_FORWARD_DELAY || t > BR_MAX_FORWARD_DELAY))
		return -ERANGE;

	spin_lock_bh(&br->lock);
	br->bridge_forward_delay = t;
	if (br_is_root_bridge(br))
		br->forward_delay = br->bridge_forward_delay;
	spin_unlock_bh(&br->lock);
	return 0;
}
Commit	Line	Data
1da177e4 LT	1	/*
	2	* Spanning tree protocol; generic parts
	3	* Linux ethernet bridge
	4	*
	5	* Authors:
	6	* Lennert Buytenhek <buytenh@gnu.org>
	7	*
1da177e4 LT	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>
82524746	14	#include <linux/rculist.h>
1da177e4 LT	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)
aaca735f	20	* before sending, make sure that is at least one STP tick.
1da177e4	21	*/
aaca735f	22	#define MESSAGE_AGE_INCR ((HZ / 256) + 1)
1da177e4	23
36cbd3dc	24	static const char *const br_port_state_names[] = {
9d6f229f	25	[BR_STATE_DISABLED] = "disabled",
1da177e4	26	[BR_STATE_LISTENING] = "listening",
9d6f229f YH	27	[BR_STATE_LEARNING] = "learning",
9d6f229f YH	28	[BR_STATE_FORWARDING] = "forwarding",
1da177e4 LT	29	[BR_STATE_BLOCKING] = "blocking",
	30	};
	31
	32	void br_log_state(const struct net_bridge_port *p)
	33	{
d9e179ec	34	br_info(p->br, "port %u(%s) entered %s state\n",
95c96174	35	(unsigned int) p->port_no, p->dev->name,
1da177e4	36	br_port_state_names[p->state]);
1da177e4 LT	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 */
9d6f229f	53	static int br_should_become_root_port(const struct net_bridge_port *p,
1da177e4 LT	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
1007dd1a	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
1da177e4 LT	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) {
1007dd1a	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
1da177e4	131	root_port = p->port_no;
1da177e4 LT	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
1da177e4 LT	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);
0c03150e	185	bpdu.message_age = (jiffies - root->designated_age)
1da177e4 LT	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;
9a834b87 SH	196	mod_timer(&p->hold_timer,
9a834b87 SH	197	round_jiffies(jiffies + BR_HOLD_TIME));
1da177e4 LT	198	}
	199	}
	200
	201	/* called under bridge lock */
160d73b8	202	static void br_record_config_information(struct net_bridge_port *p,
160d73b8	203	const struct br_config_bpdu *bpdu)
1da177e4 LT	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;
709e1b5c	209	p->designated_age = jiffies - bpdu->message_age;
1da177e4	210
9d6f229f	211	mod_timer(&p->message_age_timer, jiffies
1da177e4 LT	212	+ (p->br->max_age - bpdu->message_age));
	213	}
	214
	215	/* called under bridge lock */
160d73b8	216	static void br_record_config_timeout_values(struct net_bridge *br,
1da177e4 LT	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	br_send_tcn_bpdu(br_get_port(br, br->root_port));
	229	}
	230
	231	/* called under bridge lock */
	232	static int br_should_become_designated_port(const struct net_bridge_port *p)
	233	{
	234	struct net_bridge *br;
	235	int t;
	236
	237	br = p->br;
	238	if (br_is_designated_port(p))
	239	return 1;
	240
	241	if (memcmp(&p->designated_root, &br->designated_root, 8))
	242	return 1;
	243
	244	if (br->root_path_cost < p->designated_cost)
	245	return 1;
	246	else if (br->root_path_cost > p->designated_cost)
	247	return 0;
	248
	249	t = memcmp(&br->bridge_id, &p->designated_bridge, 8);
	250	if (t < 0)
	251	return 1;
	252	else if (t > 0)
	253	return 0;
	254
	255	if (p->port_id < p->designated_port)
	256	return 1;
	257
	258	return 0;
	259	}
	260
	261	/* called under bridge lock */
	262	static void br_designated_port_selection(struct net_bridge *br)
	263	{
	264	struct net_bridge_port *p;
	265
	266	list_for_each_entry(p, &br->port_list, list) {
	267	if (p->state != BR_STATE_DISABLED &&
	268	br_should_become_designated_port(p))
	269	br_become_designated_port(p);
	270
	271	}
	272	}
	273
	274	/* called under bridge lock */
160d73b8	275	static int br_supersedes_port_info(const struct net_bridge_port *p,
160d73b8	276	const struct br_config_bpdu *bpdu)
1da177e4 LT	277	{
	278	int t;
	279
	280	t = memcmp(&bpdu->root, &p->designated_root, 8);
	281	if (t < 0)
	282	return 1;
	283	else if (t > 0)
	284	return 0;
	285
	286	if (bpdu->root_path_cost < p->designated_cost)
	287	return 1;
	288	else if (bpdu->root_path_cost > p->designated_cost)
	289	return 0;
	290
	291	t = memcmp(&bpdu->bridge_id, &p->designated_bridge, 8);
	292	if (t < 0)
	293	return 1;
	294	else if (t > 0)
	295	return 0;
	296
	297	if (memcmp(&bpdu->bridge_id, &p->br->bridge_id, 8))
	298	return 1;
	299
	300	if (bpdu->port_id <= p->designated_port)
	301	return 1;
	302
	303	return 0;
	304	}
	305
	306	/* called under bridge lock */
160d73b8	307	static void br_topology_change_acknowledged(struct net_bridge *br)
1da177e4 LT	308	{
	309	br->topology_change_detected = 0;
	310	del_timer(&br->tcn_timer);
	311	}
	312
	313	/* called under bridge lock */
	314	void br_topology_change_detection(struct net_bridge *br)
	315	{
	316	int isroot = br_is_root_bridge(br);
	317
4f0611af SH	318	if (br->stp_enabled != BR_KERNEL_STP)
	319	return;
	320
28a16c97	321	br_info(br, "topology change detected, %s\n",
1da177e4 LT	322	isroot ? "propagating" : "sending tcn bpdu");
	323
	324	if (isroot) {
	325	br->topology_change = 1;
	326	mod_timer(&br->topology_change_timer, jiffies
	327	+ br->bridge_forward_delay + br->bridge_max_age);
	328	} else if (!br->topology_change_detected) {
	329	br_transmit_tcn(br);
	330	mod_timer(&br->tcn_timer, jiffies + br->bridge_hello_time);
	331	}
	332
	333	br->topology_change_detected = 1;
	334	}
	335
	336	/* called under bridge lock */
	337	void br_config_bpdu_generation(struct net_bridge *br)
	338	{
	339	struct net_bridge_port *p;
	340
	341	list_for_each_entry(p, &br->port_list, list) {
	342	if (p->state != BR_STATE_DISABLED &&
	343	br_is_designated_port(p))
	344	br_transmit_config(p);
	345	}
	346	}
	347
	348	/* called under bridge lock */
160d73b8	349	static void br_reply(struct net_bridge_port *p)
1da177e4 LT	350	{
	351	br_transmit_config(p);
	352	}
	353
	354	/* called under bridge lock */
	355	void br_configuration_update(struct net_bridge *br)
	356	{
	357	br_root_selection(br);
	358	br_designated_port_selection(br);
	359	}
	360
	361	/* called under bridge lock */
	362	void br_become_designated_port(struct net_bridge_port *p)
	363	{
	364	struct net_bridge *br;
	365
	366	br = p->br;
	367	p->designated_root = br->designated_root;
	368	p->designated_cost = br->root_path_cost;
	369	p->designated_bridge = br->bridge_id;
	370	p->designated_port = p->port_id;
	371	}
	372
	373
	374	/* called under bridge lock */
	375	static void br_make_blocking(struct net_bridge_port *p)
	376	{
	377	if (p->state != BR_STATE_DISABLED &&
	378	p->state != BR_STATE_BLOCKING) {
	379	if (p->state == BR_STATE_FORWARDING \|\|
	380	p->state == BR_STATE_LEARNING)
	381	br_topology_change_detection(p->br);
	382
	383	p->state = BR_STATE_BLOCKING;
	384	br_log_state(p);
4ecb961c	385	br_ifinfo_notify(RTM_NEWLINK, p);
4ecb961c	386
1da177e4 LT	387	del_timer(&p->forward_delay_timer);
	388	}
	389	}
	390
	391	/* called under bridge lock */
	392	static void br_make_forwarding(struct net_bridge_port *p)
	393	{
ef647f13	394	struct net_bridge *br = p->br;
9cde0708	395
ef647f13 SH	396	if (p->state != BR_STATE_BLOCKING)
	397	return;
	398
a461c029	399	if (br->stp_enabled == BR_NO_STP \|\| br->forward_delay == 0) {
ef647f13 SH	400	p->state = BR_STATE_FORWARDING;
	401	br_topology_change_detection(br);
	402	del_timer(&p->forward_delay_timer);
160d73b8	403	} else if (br->stp_enabled == BR_KERNEL_STP)
ef647f13 SH	404	p->state = BR_STATE_LISTENING;
	405	else
	406	p->state = BR_STATE_LEARNING;
	407
3fe2d7c7	408	br_multicast_enable_port(p);
ef647f13	409	br_log_state(p);
4ecb961c	410	br_ifinfo_notify(RTM_NEWLINK, p);
ef647f13 SH	411
	412	if (br->forward_delay != 0)
	413	mod_timer(&p->forward_delay_timer, jiffies + br->forward_delay);
1da177e4 LT	414	}
	415
	416	/* called under bridge lock */
	417	void br_port_state_selection(struct net_bridge *br)
	418	{
	419	struct net_bridge_port *p;
1faa4356	420	unsigned int liveports = 0;
1da177e4 LT	421
1da177e4 LT	422	list_for_each_entry(p, &br->port_list, list) {
1faa4356	423	if (p->state == BR_STATE_DISABLED)
	424	continue;
	425
b03b6dd5 VD	426	/* Don't change port states if userspace is handling STP */
	427	if (br->stp_enabled != BR_USER_STP) {
	428	if (p->port_no == br->root_port) {
	429	p->config_pending = 0;
	430	p->topology_change_ack = 0;
	431	br_make_forwarding(p);
	432	} else if (br_is_designated_port(p)) {
	433	del_timer(&p->message_age_timer);
	434	br_make_forwarding(p);
	435	} else {
	436	p->config_pending = 0;
	437	p->topology_change_ack = 0;
	438	br_make_blocking(p);
	439	}
1da177e4 LT	440	}
1da177e4 LT	441
1faa4356	442	if (p->state == BR_STATE_FORWARDING)
1faa4356	443	++liveports;
1da177e4	444	}
1faa4356	445
	446	if (liveports == 0)
	447	netif_carrier_off(br->dev);
	448	else
	449	netif_carrier_on(br->dev);
1da177e4 LT	450	}
	451
	452	/* called under bridge lock */
160d73b8	453	static void br_topology_change_acknowledge(struct net_bridge_port *p)
1da177e4 LT	454	{
	455	p->topology_change_ack = 1;
	456	br_transmit_config(p);
	457	}
	458
	459	/* called under bridge lock */
160d73b8	460	void br_received_config_bpdu(struct net_bridge_port *p,
160d73b8	461	const struct br_config_bpdu *bpdu)
1da177e4 LT	462	{
	463	struct net_bridge *br;
	464	int was_root;
9d6f229f	465
1da177e4 LT	466	br = p->br;
	467	was_root = br_is_root_bridge(br);
	468
	469	if (br_supersedes_port_info(p, bpdu)) {
	470	br_record_config_information(p, bpdu);
	471	br_configuration_update(br);
	472	br_port_state_selection(br);
	473
	474	if (!br_is_root_bridge(br) && was_root) {
	475	del_timer(&br->hello_timer);
	476	if (br->topology_change_detected) {
	477	del_timer(&br->topology_change_timer);
	478	br_transmit_tcn(br);
	479
9d6f229f	480	mod_timer(&br->tcn_timer,
1da177e4 LT	481	jiffies + br->bridge_hello_time);
	482	}
	483	}
	484
	485	if (p->port_no == br->root_port) {
	486	br_record_config_timeout_values(br, bpdu);
	487	br_config_bpdu_generation(br);
	488	if (bpdu->topology_change_ack)
	489	br_topology_change_acknowledged(br);
	490	}
9d6f229f YH	491	} else if (br_is_designated_port(p)) {
9d6f229f YH	492	br_reply(p);
1da177e4 LT	493	}
	494	}
	495
	496	/* called under bridge lock */
	497	void br_received_tcn_bpdu(struct net_bridge_port *p)
	498	{
	499	if (br_is_designated_port(p)) {
28a16c97	500	br_info(p->br, "port %u(%s) received tcn bpdu\n",
95c96174	501	(unsigned int) p->port_no, p->dev->name);
1da177e4 LT	502
	503	br_topology_change_detection(p->br);
	504	br_topology_change_acknowledge(p);
	505	}
	506	}
14f98f25	507
	508	/* Change bridge STP parameter */
	509	int br_set_hello_time(struct net_bridge *br, unsigned long val)
	510	{
	511	unsigned long t = clock_t_to_jiffies(val);
	512
	513	if (t < BR_MIN_HELLO_TIME \|\| t > BR_MAX_HELLO_TIME)
	514	return -ERANGE;
	515
	516	spin_lock_bh(&br->lock);
	517	br->bridge_hello_time = t;
	518	if (br_is_root_bridge(br))
	519	br->hello_time = br->bridge_hello_time;
	520	spin_unlock_bh(&br->lock);
	521	return 0;
	522	}
	523
	524	int br_set_max_age(struct net_bridge *br, unsigned long val)
	525	{
	526	unsigned long t = clock_t_to_jiffies(val);
	527
	528	if (t < BR_MIN_MAX_AGE \|\| t > BR_MAX_MAX_AGE)
	529	return -ERANGE;
	530
	531	spin_lock_bh(&br->lock);
	532	br->bridge_max_age = t;
	533	if (br_is_root_bridge(br))
	534	br->max_age = br->bridge_max_age;
	535	spin_unlock_bh(&br->lock);
	536	return 0;
	537
	538	}
	539
	540	int br_set_forward_delay(struct net_bridge *br, unsigned long val)
	541	{
	542	unsigned long t = clock_t_to_jiffies(val);
	543
	544	if (br->stp_enabled != BR_NO_STP &&
	545	(t < BR_MIN_FORWARD_DELAY \|\| t > BR_MAX_FORWARD_DELAY))
	546	return -ERANGE;
	547
	548	spin_lock_bh(&br->lock);
	549	br->bridge_forward_delay = t;
	550	if (br_is_root_bridge(br))
	551	br->forward_delay = br->bridge_forward_delay;
	552	spin_unlock_bh(&br->lock);
	553	return 0;
	554	}