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

// SPDX-License-Identifier: GPL-2.0-or-later
/*
 *	Spanning tree protocol; generic parts
 *	Linux ethernet bridge
 *
 *	Authors:
 *	Lennert Buytenhek		<[email protected]>
 */
#include <linux/kernel.h>
#include <linux/rculist.h>
#include <net/switchdev.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_set_state(struct net_bridge_port *p, unsigned int state)
{
	struct switchdev_attr attr = {
		.orig_dev = p->dev,
		.id = SWITCHDEV_ATTR_ID_PORT_STP_STATE,
		.flags = SWITCHDEV_F_DEFER,
		.u.stp_state = state,
	};
	int err;

	/* Don't change the state of the ports if they are driven by a different
	 * protocol.
	 */
	if (p->flags & BR_MRP_AWARE)
		return;

	p->state = state;
	err = switchdev_port_attr_set(p->dev, &attr, NULL);
	if (err && err != -EOPNOTSUPP)
		br_warn(p->br, "error setting offload STP state on port %u(%s)\n",
				(unsigned int) p->port_no, p->dev->name);
	else
		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]);

	if (p->br->stp_enabled == BR_KERNEL_STP) {
		switch (p->state) {
		case BR_STATE_BLOCKING:
			p->stp_xstats.transition_blk++;
			break;
		case BR_STATE_FORWARDING:
			p->stp_xstats.transition_fwd++;
			break;
		}
	}
}

u8 br_port_get_stp_state(const struct net_device *dev)
{
	struct net_bridge_port *p;

	ASSERT_RTNL();

	p = br_port_get_rtnl(dev);
	if (!p)
		return BR_STATE_DISABLED;

	return p->state;
}
EXPORT_SYMBOL_GPL(br_port_get_stp_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,
				lockdep_is_held(&br->lock)) {
		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_ifinfo_notify(RTM_NEWLINK, NULL, 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;
		if (p->br->stp_enabled == BR_KERNEL_STP)
			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_set_topology_change(br, 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_set_topology_change(br, 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_ifinfo_notify(RTM_NEWLINK, NULL, 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_ifinfo_notify(RTM_NEWLINK, NULL, 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_BLOCKING)
			br_multicast_enable_port(p);
		/* Multicast is not disabled for the port when it goes in
		 * blocking state because the timers will expire and stop by
		 * themselves without sending more queries.
		 */
		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;

	p->stp_xstats.rx_bpdu++;

	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)
{
	p->stp_xstats.rx_tcn++;

	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;

}

/* called under bridge lock */
int __set_ageing_time(struct net_device *dev, unsigned long t)
{
	struct switchdev_attr attr = {
		.orig_dev = dev,
		.id = SWITCHDEV_ATTR_ID_BRIDGE_AGEING_TIME,
		.flags = SWITCHDEV_F_SKIP_EOPNOTSUPP | SWITCHDEV_F_DEFER,
		.u.ageing_time = jiffies_to_clock_t(t),
	};
	int err;

	err = switchdev_port_attr_set(dev, &attr, NULL);
	if (err && err != -EOPNOTSUPP)
		return err;

	return 0;
}

/* Set time interval that dynamic forwarding entries live
 * For pure software bridge, allow values outside the 802.1
 * standard specification for special cases:
 *  0 - entry never ages (all permanent)
 *  1 - entry disappears (no persistence)
 *
 * Offloaded switch entries maybe more restrictive
 */
int br_set_ageing_time(struct net_bridge *br, clock_t ageing_time)
{
	unsigned long t = clock_t_to_jiffies(ageing_time);
	int err;

	err = __set_ageing_time(br->dev, t);
	if (err)
		return err;

	spin_lock_bh(&br->lock);
	br->bridge_ageing_time = t;
	br->ageing_time = t;
	spin_unlock_bh(&br->lock);

	mod_delayed_work(system_long_wq, &br->gc_work, 0);

	return 0;
}

clock_t br_get_ageing_time(const struct net_device *br_dev)
{
	const struct net_bridge *br;

	if (!netif_is_bridge_master(br_dev))
		return 0;

	br = netdev_priv(br_dev);

	return jiffies_to_clock_t(br->ageing_time);
}
EXPORT_SYMBOL_GPL(br_get_ageing_time);

/* called under bridge lock */
void __br_set_topology_change(struct net_bridge *br, unsigned char val)
{
	unsigned long t;
	int err;

	if (br->stp_enabled == BR_KERNEL_STP && br->topology_change != val) {
		/* On topology change, set the bridge ageing time to twice the
		 * forward delay. Otherwise, restore its default ageing time.
		 */

		if (val) {
			t = 2 * br->forward_delay;
			br_debug(br, "decreasing ageing time to %lu\n", t);
		} else {
			t = br->bridge_ageing_time;
			br_debug(br, "restoring ageing time to %lu\n", t);
		}

		err = __set_ageing_time(br->dev, t);
		if (err)
			br_warn(br, "error offloading ageing time\n");
		else
			br->ageing_time = t;
	}

	br->topology_change = val;
}

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
2874c5fd	1	// SPDX-License-Identifier: GPL-2.0-or-later
1da177e4 LT	2	/*
	3	* Spanning tree protocol; generic parts
	4	* Linux ethernet bridge
	5	*
	6	* Authors:
	7	* Lennert Buytenhek <[email protected]>
1da177e4 LT	8	*/
1da177e4 LT	9	#include <linux/kernel.h>
82524746	10	#include <linux/rculist.h>
38dcf357	11	#include <net/switchdev.h>
1da177e4 LT	12
	13	#include "br_private.h"
	14	#include "br_private_stp.h"
	15
	16	/* since time values in bpdu are in jiffies and then scaled (1/256)
aaca735f	17	* before sending, make sure that is at least one STP tick.
1da177e4	18	*/
aaca735f	19	#define MESSAGE_AGE_INCR ((HZ / 256) + 1)
1da177e4	20
36cbd3dc	21	static const char *const br_port_state_names[] = {
9d6f229f	22	[BR_STATE_DISABLED] = "disabled",
1da177e4	23	[BR_STATE_LISTENING] = "listening",
9d6f229f YH	24	[BR_STATE_LEARNING] = "learning",
9d6f229f YH	25	[BR_STATE_FORWARDING] = "forwarding",
1da177e4 LT	26	[BR_STATE_BLOCKING] = "blocking",
	27	};
	28
775dd692 FF	29	void br_set_state(struct net_bridge_port *p, unsigned int state)
775dd692 FF	30	{
35636062	31	struct switchdev_attr attr = {
6ff64f6f	32	.orig_dev = p->dev,
1f868398	33	.id = SWITCHDEV_ATTR_ID_PORT_STP_STATE,
0bc05d58	34	.flags = SWITCHDEV_F_DEFER,
42275bd8	35	.u.stp_state = state,
35636062	36	};
38dcf357 SF	37	int err;
38dcf357 SF	38
419dba8a HV	39	/* Don't change the state of the ports if they are driven by a different
	40	* protocol.
	41	*/
	42	if (p->flags & BR_MRP_AWARE)
	43	return;
	44
775dd692	45	p->state = state;
dcbdf135	46	err = switchdev_port_attr_set(p->dev, &attr, NULL);
bbe14f54	47	if (err && err != -EOPNOTSUPP)
38dcf357 SF	48	br_warn(p->br, "error setting offload STP state on port %u(%s)\n",
38dcf357 SF	49	(unsigned int) p->port_no, p->dev->name);
7c25b16d VD	50	else
	51	br_info(p->br, "port %u(%s) entered %s state\n",
	52	(unsigned int) p->port_no, p->dev->name,
	53	br_port_state_names[p->state]);
de179966 VD	54
	55	if (p->br->stp_enabled == BR_KERNEL_STP) {
	56	switch (p->state) {
	57	case BR_STATE_BLOCKING:
	58	p->stp_xstats.transition_blk++;
	59	break;
	60	case BR_STATE_FORWARDING:
	61	p->stp_xstats.transition_fwd++;
	62	break;
	63	}
	64	}
775dd692 FF	65	}
775dd692 FF	66
c0e715bb VO	67	u8 br_port_get_stp_state(const struct net_device *dev)
	68	{
	69	struct net_bridge_port *p;
	70
	71	ASSERT_RTNL();
	72
	73	p = br_port_get_rtnl(dev);
	74	if (!p)
	75	return BR_STATE_DISABLED;
	76
	77	return p->state;
	78	}
	79	EXPORT_SYMBOL_GPL(br_port_get_stp_state);
	80
1da177e4 LT	81	/* called under bridge lock */
	82	struct net_bridge_port br_get_port(struct net_bridge br, u16 port_no)
	83	{
	84	struct net_bridge_port *p;
	85
33c4acbe MB	86	list_for_each_entry_rcu(p, &br->port_list, list,
33c4acbe MB	87	lockdep_is_held(&br->lock)) {
1da177e4 LT	88	if (p->port_no == port_no)
	89	return p;
	90	}
	91
	92	return NULL;
	93	}
	94
	95	/* called under bridge lock */
9d6f229f	96	static int br_should_become_root_port(const struct net_bridge_port *p,
1da177e4 LT	97	u16 root_port)
	98	{
	99	struct net_bridge *br;
	100	struct net_bridge_port *rp;
	101	int t;
	102
	103	br = p->br;
	104	if (p->state == BR_STATE_DISABLED \|\|
	105	br_is_designated_port(p))
	106	return 0;
	107
	108	if (memcmp(&br->bridge_id, &p->designated_root, 8) <= 0)
	109	return 0;
	110
	111	if (!root_port)
	112	return 1;
	113
	114	rp = br_get_port(br, root_port);
	115
	116	t = memcmp(&p->designated_root, &rp->designated_root, 8);
	117	if (t < 0)
	118	return 1;
	119	else if (t > 0)
	120	return 0;
	121
	122	if (p->designated_cost + p->path_cost <
	123	rp->designated_cost + rp->path_cost)
	124	return 1;
	125	else if (p->designated_cost + p->path_cost >
	126	rp->designated_cost + rp->path_cost)
	127	return 0;
	128
	129	t = memcmp(&p->designated_bridge, &rp->designated_bridge, 8);
	130	if (t < 0)
	131	return 1;
	132	else if (t > 0)
	133	return 0;
	134
	135	if (p->designated_port < rp->designated_port)
	136	return 1;
	137	else if (p->designated_port > rp->designated_port)
	138	return 0;
	139
	140	if (p->port_id < rp->port_id)
	141	return 1;
	142
	143	return 0;
	144	}
	145
1007dd1a	146	static void br_root_port_block(const struct net_bridge *br,
	147	struct net_bridge_port *p)
	148	{
	149
	150	br_notice(br, "port %u(%s) tried to become root port (blocked)",
	151	(unsigned int) p->port_no, p->dev->name);
	152
775dd692	153	br_set_state(p, BR_STATE_LISTENING);
92899063	154	br_ifinfo_notify(RTM_NEWLINK, NULL, p);
1007dd1a	155
	156	if (br->forward_delay > 0)
	157	mod_timer(&p->forward_delay_timer, jiffies + br->forward_delay);
	158	}
	159
1da177e4 LT	160	/* called under bridge lock */
	161	static void br_root_selection(struct net_bridge *br)
	162	{
	163	struct net_bridge_port *p;
	164	u16 root_port = 0;
	165
	166	list_for_each_entry(p, &br->port_list, list) {
1007dd1a	167	if (!br_should_become_root_port(p, root_port))
	168	continue;
	169
	170	if (p->flags & BR_ROOT_BLOCK)
	171	br_root_port_block(br, p);
	172	else
1da177e4	173	root_port = p->port_no;
1da177e4 LT	174	}
	175
	176	br->root_port = root_port;
	177
	178	if (!root_port) {
	179	br->designated_root = br->bridge_id;
	180	br->root_path_cost = 0;
	181	} else {
	182	p = br_get_port(br, root_port);
	183	br->designated_root = p->designated_root;
	184	br->root_path_cost = p->designated_cost + p->path_cost;
	185	}
	186	}
	187
	188	/* called under bridge lock */
	189	void br_become_root_bridge(struct net_bridge *br)
	190	{
	191	br->max_age = br->bridge_max_age;
	192	br->hello_time = br->bridge_hello_time;
	193	br->forward_delay = br->bridge_forward_delay;
	194	br_topology_change_detection(br);
	195	del_timer(&br->tcn_timer);
	196
	197	if (br->dev->flags & IFF_UP) {
	198	br_config_bpdu_generation(br);
	199	mod_timer(&br->hello_timer, jiffies + br->hello_time);
	200	}
	201	}
	202
	203	/* called under bridge lock */
	204	void br_transmit_config(struct net_bridge_port *p)
	205	{
	206	struct br_config_bpdu bpdu;
	207	struct net_bridge *br;
	208
1da177e4 LT	209	if (timer_pending(&p->hold_timer)) {
	210	p->config_pending = 1;
	211	return;
	212	}
	213
	214	br = p->br;
	215
	216	bpdu.topology_change = br->topology_change;
	217	bpdu.topology_change_ack = p->topology_change_ack;
	218	bpdu.root = br->designated_root;
	219	bpdu.root_path_cost = br->root_path_cost;
	220	bpdu.bridge_id = br->bridge_id;
	221	bpdu.port_id = p->port_id;
	222	if (br_is_root_bridge(br))
	223	bpdu.message_age = 0;
	224	else {
	225	struct net_bridge_port *root
	226	= br_get_port(br, br->root_port);
0c03150e	227	bpdu.message_age = (jiffies - root->designated_age)
1da177e4 LT	228	+ MESSAGE_AGE_INCR;
	229	}
	230	bpdu.max_age = br->max_age;
	231	bpdu.hello_time = br->hello_time;
	232	bpdu.forward_delay = br->forward_delay;
	233
	234	if (bpdu.message_age < br->max_age) {
	235	br_send_config_bpdu(p, &bpdu);
	236	p->topology_change_ack = 0;
	237	p->config_pending = 0;
76b91c32 NA	238	if (p->br->stp_enabled == BR_KERNEL_STP)
	239	mod_timer(&p->hold_timer,
	240	round_jiffies(jiffies + BR_HOLD_TIME));
1da177e4 LT	241	}
	242	}
	243
	244	/* called under bridge lock */
160d73b8	245	static void br_record_config_information(struct net_bridge_port *p,
160d73b8	246	const struct br_config_bpdu *bpdu)
1da177e4 LT	247	{
	248	p->designated_root = bpdu->root;
	249	p->designated_cost = bpdu->root_path_cost;
	250	p->designated_bridge = bpdu->bridge_id;
	251	p->designated_port = bpdu->port_id;
709e1b5c	252	p->designated_age = jiffies - bpdu->message_age;
1da177e4	253
9d6f229f	254	mod_timer(&p->message_age_timer, jiffies
9a062013	255	+ (bpdu->max_age - bpdu->message_age));
1da177e4 LT	256	}
	257
	258	/* called under bridge lock */
160d73b8	259	static void br_record_config_timeout_values(struct net_bridge *br,
1da177e4 LT	260	const struct br_config_bpdu *bpdu)
	261	{
	262	br->max_age = bpdu->max_age;
	263	br->hello_time = bpdu->hello_time;
	264	br->forward_delay = bpdu->forward_delay;
8384b5f5	265	__br_set_topology_change(br, bpdu->topology_change);
1da177e4 LT	266	}
	267
	268	/* called under bridge lock */
	269	void br_transmit_tcn(struct net_bridge *br)
	270	{
91bc033c	271	struct net_bridge_port *p;
	272
	273	p = br_get_port(br, br->root_port);
	274	if (p)
	275	br_send_tcn_bpdu(p);
	276	else
	277	br_notice(br, "root port %u not found for topology notice\n",
	278	br->root_port);
1da177e4 LT	279	}
	280
	281	/* called under bridge lock */
	282	static int br_should_become_designated_port(const struct net_bridge_port *p)
	283	{
	284	struct net_bridge *br;
	285	int t;
	286
	287	br = p->br;
	288	if (br_is_designated_port(p))
	289	return 1;
	290
	291	if (memcmp(&p->designated_root, &br->designated_root, 8))
	292	return 1;
	293
	294	if (br->root_path_cost < p->designated_cost)
	295	return 1;
	296	else if (br->root_path_cost > p->designated_cost)
	297	return 0;
	298
	299	t = memcmp(&br->bridge_id, &p->designated_bridge, 8);
	300	if (t < 0)
	301	return 1;
	302	else if (t > 0)
	303	return 0;
	304
	305	if (p->port_id < p->designated_port)
	306	return 1;
	307
	308	return 0;
	309	}
	310
	311	/* called under bridge lock */
	312	static void br_designated_port_selection(struct net_bridge *br)
	313	{
	314	struct net_bridge_port *p;
	315
	316	list_for_each_entry(p, &br->port_list, list) {
	317	if (p->state != BR_STATE_DISABLED &&
	318	br_should_become_designated_port(p))
	319	br_become_designated_port(p);
	320
	321	}
	322	}
	323
	324	/* called under bridge lock */
160d73b8	325	static int br_supersedes_port_info(const struct net_bridge_port *p,
160d73b8	326	const struct br_config_bpdu *bpdu)
1da177e4 LT	327	{
	328	int t;
	329
	330	t = memcmp(&bpdu->root, &p->designated_root, 8);
	331	if (t < 0)
	332	return 1;
	333	else if (t > 0)
	334	return 0;
	335
	336	if (bpdu->root_path_cost < p->designated_cost)
	337	return 1;
	338	else if (bpdu->root_path_cost > p->designated_cost)
	339	return 0;
	340
	341	t = memcmp(&bpdu->bridge_id, &p->designated_bridge, 8);
	342	if (t < 0)
	343	return 1;
	344	else if (t > 0)
	345	return 0;
	346
	347	if (memcmp(&bpdu->bridge_id, &p->br->bridge_id, 8))
	348	return 1;
	349
	350	if (bpdu->port_id <= p->designated_port)
	351	return 1;
	352
	353	return 0;
	354	}
	355
	356	/* called under bridge lock */
160d73b8	357	static void br_topology_change_acknowledged(struct net_bridge *br)
1da177e4 LT	358	{
	359	br->topology_change_detected = 0;
	360	del_timer(&br->tcn_timer);
	361	}
	362
	363	/* called under bridge lock */
	364	void br_topology_change_detection(struct net_bridge *br)
	365	{
	366	int isroot = br_is_root_bridge(br);
	367
4f0611af SH	368	if (br->stp_enabled != BR_KERNEL_STP)
	369	return;
	370
28a16c97	371	br_info(br, "topology change detected, %s\n",
1da177e4 LT	372	isroot ? "propagating" : "sending tcn bpdu");
	373
	374	if (isroot) {
8384b5f5	375	__br_set_topology_change(br, 1);
1da177e4 LT	376	mod_timer(&br->topology_change_timer, jiffies
	377	+ br->bridge_forward_delay + br->bridge_max_age);
	378	} else if (!br->topology_change_detected) {
	379	br_transmit_tcn(br);
	380	mod_timer(&br->tcn_timer, jiffies + br->bridge_hello_time);
	381	}
	382
	383	br->topology_change_detected = 1;
	384	}
	385
	386	/* called under bridge lock */
	387	void br_config_bpdu_generation(struct net_bridge *br)
	388	{
	389	struct net_bridge_port *p;
	390
	391	list_for_each_entry(p, &br->port_list, list) {
	392	if (p->state != BR_STATE_DISABLED &&
	393	br_is_designated_port(p))
	394	br_transmit_config(p);
	395	}
	396	}
	397
	398	/* called under bridge lock */
160d73b8	399	static void br_reply(struct net_bridge_port *p)
1da177e4 LT	400	{
	401	br_transmit_config(p);
	402	}
	403
	404	/* called under bridge lock */
	405	void br_configuration_update(struct net_bridge *br)
	406	{
	407	br_root_selection(br);
	408	br_designated_port_selection(br);
	409	}
	410
	411	/* called under bridge lock */
	412	void br_become_designated_port(struct net_bridge_port *p)
	413	{
	414	struct net_bridge *br;
	415
	416	br = p->br;
	417	p->designated_root = br->designated_root;
	418	p->designated_cost = br->root_path_cost;
	419	p->designated_bridge = br->bridge_id;
	420	p->designated_port = p->port_id;
	421	}
	422
	423
	424	/* called under bridge lock */
	425	static void br_make_blocking(struct net_bridge_port *p)
	426	{
	427	if (p->state != BR_STATE_DISABLED &&
	428	p->state != BR_STATE_BLOCKING) {
	429	if (p->state == BR_STATE_FORWARDING \|\|
	430	p->state == BR_STATE_LEARNING)
	431	br_topology_change_detection(p->br);
	432
775dd692	433	br_set_state(p, BR_STATE_BLOCKING);
92899063	434	br_ifinfo_notify(RTM_NEWLINK, NULL, p);
4ecb961c	435
1da177e4 LT	436	del_timer(&p->forward_delay_timer);
	437	}
	438	}
	439
	440	/* called under bridge lock */
	441	static void br_make_forwarding(struct net_bridge_port *p)
	442	{
ef647f13	443	struct net_bridge *br = p->br;
9cde0708	444
ef647f13 SH	445	if (p->state != BR_STATE_BLOCKING)
	446	return;
	447
a461c029	448	if (br->stp_enabled == BR_NO_STP \|\| br->forward_delay == 0) {
775dd692	449	br_set_state(p, BR_STATE_FORWARDING);
ef647f13 SH	450	br_topology_change_detection(br);
ef647f13 SH	451	del_timer(&p->forward_delay_timer);
160d73b8	452	} else if (br->stp_enabled == BR_KERNEL_STP)
775dd692	453	br_set_state(p, BR_STATE_LISTENING);
ef647f13	454	else
775dd692	455	br_set_state(p, BR_STATE_LEARNING);
ef647f13	456
92899063	457	br_ifinfo_notify(RTM_NEWLINK, NULL, p);
ef647f13 SH	458
	459	if (br->forward_delay != 0)
	460	mod_timer(&p->forward_delay_timer, jiffies + br->forward_delay);
1da177e4 LT	461	}
	462
	463	/* called under bridge lock */
	464	void br_port_state_selection(struct net_bridge *br)
	465	{
	466	struct net_bridge_port *p;
1faa4356	467	unsigned int liveports = 0;
1da177e4 LT	468
1da177e4 LT	469	list_for_each_entry(p, &br->port_list, list) {
1faa4356	470	if (p->state == BR_STATE_DISABLED)
	471	continue;
	472
b03b6dd5 VD	473	/* Don't change port states if userspace is handling STP */
	474	if (br->stp_enabled != BR_USER_STP) {
	475	if (p->port_no == br->root_port) {
	476	p->config_pending = 0;
	477	p->topology_change_ack = 0;
	478	br_make_forwarding(p);
	479	} else if (br_is_designated_port(p)) {
	480	del_timer(&p->message_age_timer);
	481	br_make_forwarding(p);
	482	} else {
	483	p->config_pending = 0;
	484	p->topology_change_ack = 0;
	485	br_make_blocking(p);
	486	}
1da177e4 LT	487	}
1da177e4 LT	488
7ce42de1 NA	489	if (p->state != BR_STATE_BLOCKING)
7ce42de1 NA	490	br_multicast_enable_port(p);
9aa66382 NA	491	/* Multicast is not disabled for the port when it goes in
	492	* blocking state because the timers will expire and stop by
	493	* themselves without sending more queries.
	494	*/
1faa4356	495	if (p->state == BR_STATE_FORWARDING)
1faa4356	496	++liveports;
1da177e4	497	}
1faa4356	498
	499	if (liveports == 0)
	500	netif_carrier_off(br->dev);
	501	else
	502	netif_carrier_on(br->dev);
1da177e4 LT	503	}
	504
	505	/* called under bridge lock */
160d73b8	506	static void br_topology_change_acknowledge(struct net_bridge_port *p)
1da177e4 LT	507	{
	508	p->topology_change_ack = 1;
	509	br_transmit_config(p);
	510	}
	511
	512	/* called under bridge lock */
160d73b8	513	void br_received_config_bpdu(struct net_bridge_port *p,
160d73b8	514	const struct br_config_bpdu *bpdu)
1da177e4 LT	515	{
	516	struct net_bridge *br;
	517	int was_root;
9d6f229f	518
de179966 VD	519	p->stp_xstats.rx_bpdu++;
de179966 VD	520
1da177e4 LT	521	br = p->br;
	522	was_root = br_is_root_bridge(br);
	523
	524	if (br_supersedes_port_info(p, bpdu)) {
	525	br_record_config_information(p, bpdu);
	526	br_configuration_update(br);
	527	br_port_state_selection(br);
	528
	529	if (!br_is_root_bridge(br) && was_root) {
	530	del_timer(&br->hello_timer);
	531	if (br->topology_change_detected) {
	532	del_timer(&br->topology_change_timer);
	533	br_transmit_tcn(br);
	534
9d6f229f	535	mod_timer(&br->tcn_timer,
1da177e4 LT	536	jiffies + br->bridge_hello_time);
	537	}
	538	}
	539
	540	if (p->port_no == br->root_port) {
	541	br_record_config_timeout_values(br, bpdu);
	542	br_config_bpdu_generation(br);
	543	if (bpdu->topology_change_ack)
	544	br_topology_change_acknowledged(br);
	545	}
9d6f229f YH	546	} else if (br_is_designated_port(p)) {
9d6f229f YH	547	br_reply(p);
1da177e4 LT	548	}
	549	}
	550
	551	/* called under bridge lock */
	552	void br_received_tcn_bpdu(struct net_bridge_port *p)
	553	{
de179966 VD	554	p->stp_xstats.rx_tcn++;
de179966 VD	555
1da177e4	556	if (br_is_designated_port(p)) {
28a16c97	557	br_info(p->br, "port %u(%s) received tcn bpdu\n",
95c96174	558	(unsigned int) p->port_no, p->dev->name);
1da177e4 LT	559
	560	br_topology_change_detection(p->br);
	561	br_topology_change_acknowledge(p);
	562	}
	563	}
14f98f25	564
	565	/* Change bridge STP parameter */
	566	int br_set_hello_time(struct net_bridge *br, unsigned long val)
	567	{
	568	unsigned long t = clock_t_to_jiffies(val);
	569
	570	if (t < BR_MIN_HELLO_TIME \|\| t > BR_MAX_HELLO_TIME)
	571	return -ERANGE;
	572
	573	spin_lock_bh(&br->lock);
	574	br->bridge_hello_time = t;
	575	if (br_is_root_bridge(br))
	576	br->hello_time = br->bridge_hello_time;
	577	spin_unlock_bh(&br->lock);
	578	return 0;
	579	}
	580
	581	int br_set_max_age(struct net_bridge *br, unsigned long val)
	582	{
	583	unsigned long t = clock_t_to_jiffies(val);
	584
	585	if (t < BR_MIN_MAX_AGE \|\| t > BR_MAX_MAX_AGE)
	586	return -ERANGE;
	587
	588	spin_lock_bh(&br->lock);
	589	br->bridge_max_age = t;
	590	if (br_is_root_bridge(br))
	591	br->max_age = br->bridge_max_age;
	592	spin_unlock_bh(&br->lock);
	593	return 0;
	594
	595	}
	596
82dd4332 VD	597	/* called under bridge lock */
	598	int __set_ageing_time(struct net_device *dev, unsigned long t)
	599	{
	600	struct switchdev_attr attr = {
	601	.orig_dev = dev,
	602	.id = SWITCHDEV_ATTR_ID_BRIDGE_AGEING_TIME,
	603	.flags = SWITCHDEV_F_SKIP_EOPNOTSUPP \| SWITCHDEV_F_DEFER,
	604	.u.ageing_time = jiffies_to_clock_t(t),
	605	};
	606	int err;
	607
dcbdf135	608	err = switchdev_port_attr_set(dev, &attr, NULL);
82dd4332 VD	609	if (err && err != -EOPNOTSUPP)
	610	return err;
	611
	612	return 0;
	613	}
	614
4c656c13 SH	615	/* Set time interval that dynamic forwarding entries live
	616	* For pure software bridge, allow values outside the 802.1
	617	* standard specification for special cases:
efb5b338 MD	618	* 0 - entry never ages (all permanent)
efb5b338 MD	619	* 1 - entry disappears (no persistence)
4c656c13 SH	620	*
	621	* Offloaded switch entries maybe more restrictive
	622	*/
9e0b27fe	623	int br_set_ageing_time(struct net_bridge *br, clock_t ageing_time)
c62987bb	624	{
c62987bb SF	625	unsigned long t = clock_t_to_jiffies(ageing_time);
	626	int err;
	627
82dd4332 VD	628	err = __set_ageing_time(br->dev, t);
82dd4332 VD	629	if (err)
c62987bb SF	630	return err;
c62987bb SF	631
34d8acd8 VD	632	spin_lock_bh(&br->lock);
34d8acd8 VD	633	br->bridge_ageing_time = t;
c62987bb	634	br->ageing_time = t;
34d8acd8 VD	635	spin_unlock_bh(&br->lock);
34d8acd8 VD	636
f7cdee8a	637	mod_delayed_work(system_long_wq, &br->gc_work, 0);
c62987bb SF	638
	639	return 0;
	640	}
	641
bdf123b4	642	clock_t br_get_ageing_time(const struct net_device *br_dev)
f1d42ea1	643	{
bdf123b4	644	const struct net_bridge *br;
f1d42ea1 VO	645
	646	if (!netif_is_bridge_master(br_dev))
	647	return 0;
	648
	649	br = netdev_priv(br_dev);
	650
	651	return jiffies_to_clock_t(br->ageing_time);
	652	}
	653	EXPORT_SYMBOL_GPL(br_get_ageing_time);
	654
8384b5f5 VD	655	/* called under bridge lock */
	656	void __br_set_topology_change(struct net_bridge *br, unsigned char val)
	657	{
34d8acd8 VD	658	unsigned long t;
	659	int err;
	660
	661	if (br->stp_enabled == BR_KERNEL_STP && br->topology_change != val) {
	662	/* On topology change, set the bridge ageing time to twice the
	663	* forward delay. Otherwise, restore its default ageing time.
	664	*/
	665
	666	if (val) {
	667	t = 2 * br->forward_delay;
	668	br_debug(br, "decreasing ageing time to %lu\n", t);
	669	} else {
	670	t = br->bridge_ageing_time;
	671	br_debug(br, "restoring ageing time to %lu\n", t);
	672	}
	673
	674	err = __set_ageing_time(br->dev, t);
	675	if (err)
	676	br_warn(br, "error offloading ageing time\n");
	677	else
	678	br->ageing_time = t;
	679	}
	680
8384b5f5 VD	681	br->topology_change = val;
	682	}
	683
be4f154d HX	684	void __br_set_forward_delay(struct net_bridge *br, unsigned long t)
	685	{
	686	br->bridge_forward_delay = t;
	687	if (br_is_root_bridge(br))
	688	br->forward_delay = br->bridge_forward_delay;
	689	}
	690
14f98f25	691	int br_set_forward_delay(struct net_bridge *br, unsigned long val)
	692	{
	693	unsigned long t = clock_t_to_jiffies(val);
8a921265	694	int err = -ERANGE;
14f98f25	695
34c2d9fb	696	spin_lock_bh(&br->lock);
8a921265 VY	697	if (br->stp_enabled != BR_NO_STP &&
	698	(t < BR_MIN_FORWARD_DELAY \|\| t > BR_MAX_FORWARD_DELAY))
	699	goto unlock;
	700
be4f154d	701	__br_set_forward_delay(br, t);
8a921265 VY	702	err = 0;
	703
	704	unlock:
14f98f25	705	spin_unlock_bh(&br->lock);
8a921265	706	return err;
14f98f25	707	}