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

/*
 *	Spanning tree protocol; generic parts
 *	Linux ethernet bridge
 *
 *	Authors:
 *	Lennert Buytenhek		<[email protected]>
 *
 *	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]);
}

void br_set_state(struct net_bridge_port *p, unsigned int state)
{
	p->state = 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);

	br_set_state(p, 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
		  + (bpdu->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)
{
	struct net_bridge_port *p;

	p = br_get_port(br, br->root_port);
	if (p)
		br_send_tcn_bpdu(p);
	else
		br_notice(br, "root port %u not found for topology notice\n",
			  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);

		br_set_state(p, 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) {
		br_set_state(p, BR_STATE_FORWARDING);
		br_topology_change_detection(br);
		del_timer(&p->forward_delay_timer);
	} else if (br->stp_enabled == BR_KERNEL_STP)
		br_set_state(p, BR_STATE_LISTENING);
	else
		br_set_state(p, 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;

}

void __br_set_forward_delay(struct net_bridge *br, unsigned long t)
{
	br->bridge_forward_delay = t;
	if (br_is_root_bridge(br))
		br->forward_delay = br->bridge_forward_delay;
}

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

	spin_lock_bh(&br->lock);
	if (br->stp_enabled != BR_NO_STP &&
	    (t < BR_MIN_FORWARD_DELAY || t > BR_MAX_FORWARD_DELAY))
		goto unlock;

	__br_set_forward_delay(br, t);
	err = 0;

unlock:
	spin_unlock_bh(&br->lock);
	return err;
}
Commit	Line	Data
1da177e4 LT	1	/*
	2	* Spanning tree protocol; generic parts
	3	* Linux ethernet bridge
	4	*
	5	* Authors:
	6	* Lennert Buytenhek <[email protected]>
	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	}
1da177e4 LT	38
775dd692 FF	39	void br_set_state(struct net_bridge_port *p, unsigned int state)
	40	{
	41	p->state = state;
	42	}
	43
1da177e4 LT	44	/* called under bridge lock */
	45	struct 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 */
9d6f229f	58	static int br_should_become_root_port(const struct net_bridge_port *p,
1da177e4 LT	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
1007dd1a	108	static 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
775dd692	115	br_set_state(p, BR_STATE_LISTENING);
1007dd1a	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
1da177e4 LT	123	/* called under bridge lock */
	124	static 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) {
1007dd1a	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
1da177e4	136	root_port = p->port_no;
1da177e4 LT	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 */
	152	void 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 */
	167	void br_transmit_config(struct net_bridge_port *p)
	168	{
	169	struct br_config_bpdu bpdu;
	170	struct net_bridge *br;
	171
1da177e4 LT	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);
0c03150e	190	bpdu.message_age = (jiffies - root->designated_age)
1da177e4 LT	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;
9a834b87 SH	201	mod_timer(&p->hold_timer,
9a834b87 SH	202	round_jiffies(jiffies + BR_HOLD_TIME));
1da177e4 LT	203	}
	204	}
	205
	206	/* called under bridge lock */
160d73b8	207	static void br_record_config_information(struct net_bridge_port *p,
160d73b8	208	const struct br_config_bpdu *bpdu)
1da177e4 LT	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;
709e1b5c	214	p->designated_age = jiffies - bpdu->message_age;
1da177e4	215
9d6f229f	216	mod_timer(&p->message_age_timer, jiffies
9a062013	217	+ (bpdu->max_age - bpdu->message_age));
1da177e4 LT	218	}
	219
	220	/* called under bridge lock */
160d73b8	221	static void br_record_config_timeout_values(struct net_bridge *br,
1da177e4 LT	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 */
	231	void br_transmit_tcn(struct net_bridge *br)
	232	{
91bc033c	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);
1da177e4 LT	241	}
	242
	243	/* called under bridge lock */
	244	static 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 */
	274	static 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 */
160d73b8	287	static int br_supersedes_port_info(const struct net_bridge_port *p,
160d73b8	288	const struct br_config_bpdu *bpdu)
1da177e4 LT	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 */
160d73b8	319	static void br_topology_change_acknowledged(struct net_bridge *br)
1da177e4 LT	320	{
	321	br->topology_change_detected = 0;
	322	del_timer(&br->tcn_timer);
	323	}
	324
	325	/* called under bridge lock */
	326	void br_topology_change_detection(struct net_bridge *br)
	327	{
	328	int isroot = br_is_root_bridge(br);
	329
4f0611af SH	330	if (br->stp_enabled != BR_KERNEL_STP)
	331	return;
	332
28a16c97	333	br_info(br, "topology change detected, %s\n",
1da177e4 LT	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 */
	349	void 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 */
160d73b8	361	static void br_reply(struct net_bridge_port *p)
1da177e4 LT	362	{
	363	br_transmit_config(p);
	364	}
	365
	366	/* called under bridge lock */
	367	void 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 */
	374	void 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 */
	387	static 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
775dd692	395	br_set_state(p, BR_STATE_BLOCKING);
1da177e4	396	br_log_state(p);
4ecb961c	397	br_ifinfo_notify(RTM_NEWLINK, p);
4ecb961c	398
1da177e4 LT	399	del_timer(&p->forward_delay_timer);
	400	}
	401	}
	402
	403	/* called under bridge lock */
	404	static void br_make_forwarding(struct net_bridge_port *p)
	405	{
ef647f13	406	struct net_bridge *br = p->br;
9cde0708	407
ef647f13 SH	408	if (p->state != BR_STATE_BLOCKING)
	409	return;
	410
a461c029	411	if (br->stp_enabled == BR_NO_STP \|\| br->forward_delay == 0) {
775dd692	412	br_set_state(p, BR_STATE_FORWARDING);
ef647f13 SH	413	br_topology_change_detection(br);
ef647f13 SH	414	del_timer(&p->forward_delay_timer);
160d73b8	415	} else if (br->stp_enabled == BR_KERNEL_STP)
775dd692	416	br_set_state(p, BR_STATE_LISTENING);
ef647f13	417	else
775dd692	418	br_set_state(p, BR_STATE_LEARNING);
ef647f13	419
3fe2d7c7	420	br_multicast_enable_port(p);
ef647f13	421	br_log_state(p);
4ecb961c	422	br_ifinfo_notify(RTM_NEWLINK, p);
ef647f13 SH	423
	424	if (br->forward_delay != 0)
	425	mod_timer(&p->forward_delay_timer, jiffies + br->forward_delay);
1da177e4 LT	426	}
	427
	428	/* called under bridge lock */
	429	void br_port_state_selection(struct net_bridge *br)
	430	{
	431	struct net_bridge_port *p;
1faa4356	432	unsigned int liveports = 0;
1da177e4 LT	433
1da177e4 LT	434	list_for_each_entry(p, &br->port_list, list) {
1faa4356	435	if (p->state == BR_STATE_DISABLED)
	436	continue;
	437
b03b6dd5 VD	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	}
1da177e4 LT	452	}
1da177e4 LT	453
1faa4356	454	if (p->state == BR_STATE_FORWARDING)
1faa4356	455	++liveports;
1da177e4	456	}
1faa4356	457
	458	if (liveports == 0)
	459	netif_carrier_off(br->dev);
	460	else
	461	netif_carrier_on(br->dev);
1da177e4 LT	462	}
	463
	464	/* called under bridge lock */
160d73b8	465	static void br_topology_change_acknowledge(struct net_bridge_port *p)
1da177e4 LT	466	{
	467	p->topology_change_ack = 1;
	468	br_transmit_config(p);
	469	}
	470
	471	/* called under bridge lock */
160d73b8	472	void br_received_config_bpdu(struct net_bridge_port *p,
160d73b8	473	const struct br_config_bpdu *bpdu)
1da177e4 LT	474	{
	475	struct net_bridge *br;
	476	int was_root;
9d6f229f	477
1da177e4 LT	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
9d6f229f	492	mod_timer(&br->tcn_timer,
1da177e4 LT	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	}
9d6f229f YH	503	} else if (br_is_designated_port(p)) {
9d6f229f YH	504	br_reply(p);
1da177e4 LT	505	}
	506	}
	507
	508	/* called under bridge lock */
	509	void br_received_tcn_bpdu(struct net_bridge_port *p)
	510	{
	511	if (br_is_designated_port(p)) {
28a16c97	512	br_info(p->br, "port %u(%s) received tcn bpdu\n",
95c96174	513	(unsigned int) p->port_no, p->dev->name);
1da177e4 LT	514
	515	br_topology_change_detection(p->br);
	516	br_topology_change_acknowledge(p);
	517	}
	518	}
14f98f25	519
	520	/* Change bridge STP parameter */
	521	int 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
	536	int 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
be4f154d HX	552	void __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
14f98f25	559	int br_set_forward_delay(struct net_bridge *br, unsigned long val)
	560	{
	561	unsigned long t = clock_t_to_jiffies(val);
be4f154d	562	int err = -ERANGE;
14f98f25	563
be4f154d	564	spin_lock_bh(&br->lock);
14f98f25	565	if (br->stp_enabled != BR_NO_STP &&
14f98f25	566	(t < BR_MIN_FORWARD_DELAY \|\| t > BR_MAX_FORWARD_DELAY))
be4f154d	567	goto unlock;
14f98f25	568
be4f154d HX	569	__br_set_forward_delay(br, t);
	570	err = 0;
	571
	572	unlock:
14f98f25	573	spin_unlock_bh(&br->lock);
be4f154d	574	return err;
14f98f25	575	}