2 * Spanning tree protocol; generic parts
3 * Linux ethernet bridge
6 * Lennert Buytenhek <buytenh@gnu.org>
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.
13 #include <linux/kernel.h>
14 #include <linux/rculist.h>
15 #include <net/switchdev.h>
17 #include "br_private.h"
18 #include "br_private_stp.h"
20 /* since time values in bpdu are in jiffies and then scaled (1/256)
21 * before sending, make sure that is at least one STP tick.
23 #define MESSAGE_AGE_INCR ((HZ / 256) + 1)
25 static const char *const br_port_state_names[] = {
26 [BR_STATE_DISABLED] = "disabled",
27 [BR_STATE_LISTENING] = "listening",
28 [BR_STATE_LEARNING] = "learning",
29 [BR_STATE_FORWARDING] = "forwarding",
30 [BR_STATE_BLOCKING] = "blocking",
33 void br_log_state(const struct net_bridge_port *p)
35 br_info(p->br, "port %u(%s) entered %s state\n",
36 (unsigned int) p->port_no, p->dev->name,
37 br_port_state_names[p->state]);
40 void br_set_state(struct net_bridge_port *p, unsigned int state)
42 struct switchdev_attr attr = {
44 .id = SWITCHDEV_ATTR_ID_PORT_STP_STATE,
45 .flags = SWITCHDEV_F_DEFER,
51 err = switchdev_port_attr_set(p->dev, &attr);
52 if (err && err != -EOPNOTSUPP)
53 br_warn(p->br, "error setting offload STP state on port %u(%s)\n",
54 (unsigned int) p->port_no, p->dev->name);
57 /* called under bridge lock */
58 struct net_bridge_port *br_get_port(struct net_bridge *br, u16 port_no)
60 struct net_bridge_port *p;
62 list_for_each_entry_rcu(p, &br->port_list, list) {
63 if (p->port_no == port_no)
70 /* called under bridge lock */
71 static int br_should_become_root_port(const struct net_bridge_port *p,
74 struct net_bridge *br;
75 struct net_bridge_port *rp;
79 if (p->state == BR_STATE_DISABLED ||
80 br_is_designated_port(p))
83 if (memcmp(&br->bridge_id, &p->designated_root, 8) <= 0)
89 rp = br_get_port(br, root_port);
91 t = memcmp(&p->designated_root, &rp->designated_root, 8);
97 if (p->designated_cost + p->path_cost <
98 rp->designated_cost + rp->path_cost)
100 else if (p->designated_cost + p->path_cost >
101 rp->designated_cost + rp->path_cost)
104 t = memcmp(&p->designated_bridge, &rp->designated_bridge, 8);
110 if (p->designated_port < rp->designated_port)
112 else if (p->designated_port > rp->designated_port)
115 if (p->port_id < rp->port_id)
121 static void br_root_port_block(const struct net_bridge *br,
122 struct net_bridge_port *p)
125 br_notice(br, "port %u(%s) tried to become root port (blocked)",
126 (unsigned int) p->port_no, p->dev->name);
128 br_set_state(p, BR_STATE_LISTENING);
130 br_ifinfo_notify(RTM_NEWLINK, p);
132 if (br->forward_delay > 0)
133 mod_timer(&p->forward_delay_timer, jiffies + br->forward_delay);
136 /* called under bridge lock */
137 static void br_root_selection(struct net_bridge *br)
139 struct net_bridge_port *p;
142 list_for_each_entry(p, &br->port_list, list) {
143 if (!br_should_become_root_port(p, root_port))
146 if (p->flags & BR_ROOT_BLOCK)
147 br_root_port_block(br, p);
149 root_port = p->port_no;
152 br->root_port = root_port;
155 br->designated_root = br->bridge_id;
156 br->root_path_cost = 0;
158 p = br_get_port(br, root_port);
159 br->designated_root = p->designated_root;
160 br->root_path_cost = p->designated_cost + p->path_cost;
164 /* called under bridge lock */
165 void br_become_root_bridge(struct net_bridge *br)
167 br->max_age = br->bridge_max_age;
168 br->hello_time = br->bridge_hello_time;
169 br->forward_delay = br->bridge_forward_delay;
170 br_topology_change_detection(br);
171 del_timer(&br->tcn_timer);
173 if (br->dev->flags & IFF_UP) {
174 br_config_bpdu_generation(br);
175 mod_timer(&br->hello_timer, jiffies + br->hello_time);
179 /* called under bridge lock */
180 void br_transmit_config(struct net_bridge_port *p)
182 struct br_config_bpdu bpdu;
183 struct net_bridge *br;
185 if (timer_pending(&p->hold_timer)) {
186 p->config_pending = 1;
192 bpdu.topology_change = br->topology_change;
193 bpdu.topology_change_ack = p->topology_change_ack;
194 bpdu.root = br->designated_root;
195 bpdu.root_path_cost = br->root_path_cost;
196 bpdu.bridge_id = br->bridge_id;
197 bpdu.port_id = p->port_id;
198 if (br_is_root_bridge(br))
199 bpdu.message_age = 0;
201 struct net_bridge_port *root
202 = br_get_port(br, br->root_port);
203 bpdu.message_age = (jiffies - root->designated_age)
206 bpdu.max_age = br->max_age;
207 bpdu.hello_time = br->hello_time;
208 bpdu.forward_delay = br->forward_delay;
210 if (bpdu.message_age < br->max_age) {
211 br_send_config_bpdu(p, &bpdu);
212 p->topology_change_ack = 0;
213 p->config_pending = 0;
214 if (p->br->stp_enabled == BR_KERNEL_STP)
215 mod_timer(&p->hold_timer,
216 round_jiffies(jiffies + BR_HOLD_TIME));
220 /* called under bridge lock */
221 static void br_record_config_information(struct net_bridge_port *p,
222 const struct br_config_bpdu *bpdu)
224 p->designated_root = bpdu->root;
225 p->designated_cost = bpdu->root_path_cost;
226 p->designated_bridge = bpdu->bridge_id;
227 p->designated_port = bpdu->port_id;
228 p->designated_age = jiffies - bpdu->message_age;
230 mod_timer(&p->message_age_timer, jiffies
231 + (bpdu->max_age - bpdu->message_age));
234 /* called under bridge lock */
235 static void br_record_config_timeout_values(struct net_bridge *br,
236 const struct br_config_bpdu *bpdu)
238 br->max_age = bpdu->max_age;
239 br->hello_time = bpdu->hello_time;
240 br->forward_delay = bpdu->forward_delay;
241 br->topology_change = bpdu->topology_change;
244 /* called under bridge lock */
245 void br_transmit_tcn(struct net_bridge *br)
247 struct net_bridge_port *p;
249 p = br_get_port(br, br->root_port);
253 br_notice(br, "root port %u not found for topology notice\n",
257 /* called under bridge lock */
258 static int br_should_become_designated_port(const struct net_bridge_port *p)
260 struct net_bridge *br;
264 if (br_is_designated_port(p))
267 if (memcmp(&p->designated_root, &br->designated_root, 8))
270 if (br->root_path_cost < p->designated_cost)
272 else if (br->root_path_cost > p->designated_cost)
275 t = memcmp(&br->bridge_id, &p->designated_bridge, 8);
281 if (p->port_id < p->designated_port)
287 /* called under bridge lock */
288 static void br_designated_port_selection(struct net_bridge *br)
290 struct net_bridge_port *p;
292 list_for_each_entry(p, &br->port_list, list) {
293 if (p->state != BR_STATE_DISABLED &&
294 br_should_become_designated_port(p))
295 br_become_designated_port(p);
300 /* called under bridge lock */
301 static int br_supersedes_port_info(const struct net_bridge_port *p,
302 const struct br_config_bpdu *bpdu)
306 t = memcmp(&bpdu->root, &p->designated_root, 8);
312 if (bpdu->root_path_cost < p->designated_cost)
314 else if (bpdu->root_path_cost > p->designated_cost)
317 t = memcmp(&bpdu->bridge_id, &p->designated_bridge, 8);
323 if (memcmp(&bpdu->bridge_id, &p->br->bridge_id, 8))
326 if (bpdu->port_id <= p->designated_port)
332 /* called under bridge lock */
333 static void br_topology_change_acknowledged(struct net_bridge *br)
335 br->topology_change_detected = 0;
336 del_timer(&br->tcn_timer);
339 /* called under bridge lock */
340 void br_topology_change_detection(struct net_bridge *br)
342 int isroot = br_is_root_bridge(br);
344 if (br->stp_enabled != BR_KERNEL_STP)
347 br_info(br, "topology change detected, %s\n",
348 isroot ? "propagating" : "sending tcn bpdu");
351 br->topology_change = 1;
352 mod_timer(&br->topology_change_timer, jiffies
353 + br->bridge_forward_delay + br->bridge_max_age);
354 } else if (!br->topology_change_detected) {
356 mod_timer(&br->tcn_timer, jiffies + br->bridge_hello_time);
359 br->topology_change_detected = 1;
362 /* called under bridge lock */
363 void br_config_bpdu_generation(struct net_bridge *br)
365 struct net_bridge_port *p;
367 list_for_each_entry(p, &br->port_list, list) {
368 if (p->state != BR_STATE_DISABLED &&
369 br_is_designated_port(p))
370 br_transmit_config(p);
374 /* called under bridge lock */
375 static void br_reply(struct net_bridge_port *p)
377 br_transmit_config(p);
380 /* called under bridge lock */
381 void br_configuration_update(struct net_bridge *br)
383 br_root_selection(br);
384 br_designated_port_selection(br);
387 /* called under bridge lock */
388 void br_become_designated_port(struct net_bridge_port *p)
390 struct net_bridge *br;
393 p->designated_root = br->designated_root;
394 p->designated_cost = br->root_path_cost;
395 p->designated_bridge = br->bridge_id;
396 p->designated_port = p->port_id;
400 /* called under bridge lock */
401 static void br_make_blocking(struct net_bridge_port *p)
403 if (p->state != BR_STATE_DISABLED &&
404 p->state != BR_STATE_BLOCKING) {
405 if (p->state == BR_STATE_FORWARDING ||
406 p->state == BR_STATE_LEARNING)
407 br_topology_change_detection(p->br);
409 br_set_state(p, BR_STATE_BLOCKING);
411 br_ifinfo_notify(RTM_NEWLINK, p);
413 del_timer(&p->forward_delay_timer);
417 /* called under bridge lock */
418 static void br_make_forwarding(struct net_bridge_port *p)
420 struct net_bridge *br = p->br;
422 if (p->state != BR_STATE_BLOCKING)
425 if (br->stp_enabled == BR_NO_STP || br->forward_delay == 0) {
426 br_set_state(p, BR_STATE_FORWARDING);
427 br_topology_change_detection(br);
428 del_timer(&p->forward_delay_timer);
429 } else if (br->stp_enabled == BR_KERNEL_STP)
430 br_set_state(p, BR_STATE_LISTENING);
432 br_set_state(p, BR_STATE_LEARNING);
435 br_ifinfo_notify(RTM_NEWLINK, p);
437 if (br->forward_delay != 0)
438 mod_timer(&p->forward_delay_timer, jiffies + br->forward_delay);
441 /* called under bridge lock */
442 void br_port_state_selection(struct net_bridge *br)
444 struct net_bridge_port *p;
445 unsigned int liveports = 0;
447 list_for_each_entry(p, &br->port_list, list) {
448 if (p->state == BR_STATE_DISABLED)
451 /* Don't change port states if userspace is handling STP */
452 if (br->stp_enabled != BR_USER_STP) {
453 if (p->port_no == br->root_port) {
454 p->config_pending = 0;
455 p->topology_change_ack = 0;
456 br_make_forwarding(p);
457 } else if (br_is_designated_port(p)) {
458 del_timer(&p->message_age_timer);
459 br_make_forwarding(p);
461 p->config_pending = 0;
462 p->topology_change_ack = 0;
467 if (p->state != BR_STATE_BLOCKING)
468 br_multicast_enable_port(p);
469 /* Multicast is not disabled for the port when it goes in
470 * blocking state because the timers will expire and stop by
471 * themselves without sending more queries.
473 if (p->state == BR_STATE_FORWARDING)
478 netif_carrier_off(br->dev);
480 netif_carrier_on(br->dev);
483 /* called under bridge lock */
484 static void br_topology_change_acknowledge(struct net_bridge_port *p)
486 p->topology_change_ack = 1;
487 br_transmit_config(p);
490 /* called under bridge lock */
491 void br_received_config_bpdu(struct net_bridge_port *p,
492 const struct br_config_bpdu *bpdu)
494 struct net_bridge *br;
498 was_root = br_is_root_bridge(br);
500 if (br_supersedes_port_info(p, bpdu)) {
501 br_record_config_information(p, bpdu);
502 br_configuration_update(br);
503 br_port_state_selection(br);
505 if (!br_is_root_bridge(br) && was_root) {
506 del_timer(&br->hello_timer);
507 if (br->topology_change_detected) {
508 del_timer(&br->topology_change_timer);
511 mod_timer(&br->tcn_timer,
512 jiffies + br->bridge_hello_time);
516 if (p->port_no == br->root_port) {
517 br_record_config_timeout_values(br, bpdu);
518 br_config_bpdu_generation(br);
519 if (bpdu->topology_change_ack)
520 br_topology_change_acknowledged(br);
522 } else if (br_is_designated_port(p)) {
527 /* called under bridge lock */
528 void br_received_tcn_bpdu(struct net_bridge_port *p)
530 if (br_is_designated_port(p)) {
531 br_info(p->br, "port %u(%s) received tcn bpdu\n",
532 (unsigned int) p->port_no, p->dev->name);
534 br_topology_change_detection(p->br);
535 br_topology_change_acknowledge(p);
539 /* Change bridge STP parameter */
540 int br_set_hello_time(struct net_bridge *br, unsigned long val)
542 unsigned long t = clock_t_to_jiffies(val);
544 if (t < BR_MIN_HELLO_TIME || t > BR_MAX_HELLO_TIME)
547 spin_lock_bh(&br->lock);
548 br->bridge_hello_time = t;
549 if (br_is_root_bridge(br))
550 br->hello_time = br->bridge_hello_time;
551 spin_unlock_bh(&br->lock);
555 int br_set_max_age(struct net_bridge *br, unsigned long val)
557 unsigned long t = clock_t_to_jiffies(val);
559 if (t < BR_MIN_MAX_AGE || t > BR_MAX_MAX_AGE)
562 spin_lock_bh(&br->lock);
563 br->bridge_max_age = t;
564 if (br_is_root_bridge(br))
565 br->max_age = br->bridge_max_age;
566 spin_unlock_bh(&br->lock);
571 int br_set_ageing_time(struct net_bridge *br, u32 ageing_time)
573 struct switchdev_attr attr = {
575 .id = SWITCHDEV_ATTR_ID_BRIDGE_AGEING_TIME,
576 .flags = SWITCHDEV_F_SKIP_EOPNOTSUPP,
577 .u.ageing_time = ageing_time,
579 unsigned long t = clock_t_to_jiffies(ageing_time);
582 if (t < BR_MIN_AGEING_TIME || t > BR_MAX_AGEING_TIME)
585 err = switchdev_port_attr_set(br->dev, &attr);
590 mod_timer(&br->gc_timer, jiffies);
595 void __br_set_forward_delay(struct net_bridge *br, unsigned long t)
597 br->bridge_forward_delay = t;
598 if (br_is_root_bridge(br))
599 br->forward_delay = br->bridge_forward_delay;
602 int br_set_forward_delay(struct net_bridge *br, unsigned long val)
604 unsigned long t = clock_t_to_jiffies(val);
607 spin_lock_bh(&br->lock);
608 if (br->stp_enabled != BR_NO_STP &&
609 (t < BR_MIN_FORWARD_DELAY || t > BR_MAX_FORWARD_DELAY))
612 __br_set_forward_delay(br, t);
616 spin_unlock_bh(&br->lock);