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 = {
43 .id = SWITCHDEV_ATTR_PORT_STP_STATE,
49 err = switchdev_port_attr_set(p->dev, &attr);
50 if (err && err != -EOPNOTSUPP)
51 br_warn(p->br, "error setting offload STP state on port %u(%s)\n",
52 (unsigned int) p->port_no, p->dev->name);
55 /* called under bridge lock */
56 struct net_bridge_port *br_get_port(struct net_bridge *br, u16 port_no)
58 struct net_bridge_port *p;
60 list_for_each_entry_rcu(p, &br->port_list, list) {
61 if (p->port_no == port_no)
68 /* called under bridge lock */
69 static int br_should_become_root_port(const struct net_bridge_port *p,
72 struct net_bridge *br;
73 struct net_bridge_port *rp;
77 if (p->state == BR_STATE_DISABLED ||
78 br_is_designated_port(p))
81 if (memcmp(&br->bridge_id, &p->designated_root, 8) <= 0)
87 rp = br_get_port(br, root_port);
89 t = memcmp(&p->designated_root, &rp->designated_root, 8);
95 if (p->designated_cost + p->path_cost <
96 rp->designated_cost + rp->path_cost)
98 else if (p->designated_cost + p->path_cost >
99 rp->designated_cost + rp->path_cost)
102 t = memcmp(&p->designated_bridge, &rp->designated_bridge, 8);
108 if (p->designated_port < rp->designated_port)
110 else if (p->designated_port > rp->designated_port)
113 if (p->port_id < rp->port_id)
119 static void br_root_port_block(const struct net_bridge *br,
120 struct net_bridge_port *p)
123 br_notice(br, "port %u(%s) tried to become root port (blocked)",
124 (unsigned int) p->port_no, p->dev->name);
126 br_set_state(p, BR_STATE_LISTENING);
128 br_ifinfo_notify(RTM_NEWLINK, p);
130 if (br->forward_delay > 0)
131 mod_timer(&p->forward_delay_timer, jiffies + br->forward_delay);
134 /* called under bridge lock */
135 static void br_root_selection(struct net_bridge *br)
137 struct net_bridge_port *p;
140 list_for_each_entry(p, &br->port_list, list) {
141 if (!br_should_become_root_port(p, root_port))
144 if (p->flags & BR_ROOT_BLOCK)
145 br_root_port_block(br, p);
147 root_port = p->port_no;
150 br->root_port = root_port;
153 br->designated_root = br->bridge_id;
154 br->root_path_cost = 0;
156 p = br_get_port(br, root_port);
157 br->designated_root = p->designated_root;
158 br->root_path_cost = p->designated_cost + p->path_cost;
162 /* called under bridge lock */
163 void br_become_root_bridge(struct net_bridge *br)
165 br->max_age = br->bridge_max_age;
166 br->hello_time = br->bridge_hello_time;
167 br->forward_delay = br->bridge_forward_delay;
168 br_topology_change_detection(br);
169 del_timer(&br->tcn_timer);
171 if (br->dev->flags & IFF_UP) {
172 br_config_bpdu_generation(br);
173 mod_timer(&br->hello_timer, jiffies + br->hello_time);
177 /* called under bridge lock */
178 void br_transmit_config(struct net_bridge_port *p)
180 struct br_config_bpdu bpdu;
181 struct net_bridge *br;
183 if (timer_pending(&p->hold_timer)) {
184 p->config_pending = 1;
190 bpdu.topology_change = br->topology_change;
191 bpdu.topology_change_ack = p->topology_change_ack;
192 bpdu.root = br->designated_root;
193 bpdu.root_path_cost = br->root_path_cost;
194 bpdu.bridge_id = br->bridge_id;
195 bpdu.port_id = p->port_id;
196 if (br_is_root_bridge(br))
197 bpdu.message_age = 0;
199 struct net_bridge_port *root
200 = br_get_port(br, br->root_port);
201 bpdu.message_age = (jiffies - root->designated_age)
204 bpdu.max_age = br->max_age;
205 bpdu.hello_time = br->hello_time;
206 bpdu.forward_delay = br->forward_delay;
208 if (bpdu.message_age < br->max_age) {
209 br_send_config_bpdu(p, &bpdu);
210 p->topology_change_ack = 0;
211 p->config_pending = 0;
212 mod_timer(&p->hold_timer,
213 round_jiffies(jiffies + BR_HOLD_TIME));
217 /* called under bridge lock */
218 static void br_record_config_information(struct net_bridge_port *p,
219 const struct br_config_bpdu *bpdu)
221 p->designated_root = bpdu->root;
222 p->designated_cost = bpdu->root_path_cost;
223 p->designated_bridge = bpdu->bridge_id;
224 p->designated_port = bpdu->port_id;
225 p->designated_age = jiffies - bpdu->message_age;
227 mod_timer(&p->message_age_timer, jiffies
228 + (bpdu->max_age - bpdu->message_age));
231 /* called under bridge lock */
232 static void br_record_config_timeout_values(struct net_bridge *br,
233 const struct br_config_bpdu *bpdu)
235 br->max_age = bpdu->max_age;
236 br->hello_time = bpdu->hello_time;
237 br->forward_delay = bpdu->forward_delay;
238 br->topology_change = bpdu->topology_change;
241 /* called under bridge lock */
242 void br_transmit_tcn(struct net_bridge *br)
244 struct net_bridge_port *p;
246 p = br_get_port(br, br->root_port);
250 br_notice(br, "root port %u not found for topology notice\n",
254 /* called under bridge lock */
255 static int br_should_become_designated_port(const struct net_bridge_port *p)
257 struct net_bridge *br;
261 if (br_is_designated_port(p))
264 if (memcmp(&p->designated_root, &br->designated_root, 8))
267 if (br->root_path_cost < p->designated_cost)
269 else if (br->root_path_cost > p->designated_cost)
272 t = memcmp(&br->bridge_id, &p->designated_bridge, 8);
278 if (p->port_id < p->designated_port)
284 /* called under bridge lock */
285 static void br_designated_port_selection(struct net_bridge *br)
287 struct net_bridge_port *p;
289 list_for_each_entry(p, &br->port_list, list) {
290 if (p->state != BR_STATE_DISABLED &&
291 br_should_become_designated_port(p))
292 br_become_designated_port(p);
297 /* called under bridge lock */
298 static int br_supersedes_port_info(const struct net_bridge_port *p,
299 const struct br_config_bpdu *bpdu)
303 t = memcmp(&bpdu->root, &p->designated_root, 8);
309 if (bpdu->root_path_cost < p->designated_cost)
311 else if (bpdu->root_path_cost > p->designated_cost)
314 t = memcmp(&bpdu->bridge_id, &p->designated_bridge, 8);
320 if (memcmp(&bpdu->bridge_id, &p->br->bridge_id, 8))
323 if (bpdu->port_id <= p->designated_port)
329 /* called under bridge lock */
330 static void br_topology_change_acknowledged(struct net_bridge *br)
332 br->topology_change_detected = 0;
333 del_timer(&br->tcn_timer);
336 /* called under bridge lock */
337 void br_topology_change_detection(struct net_bridge *br)
339 int isroot = br_is_root_bridge(br);
341 if (br->stp_enabled != BR_KERNEL_STP)
344 br_info(br, "topology change detected, %s\n",
345 isroot ? "propagating" : "sending tcn bpdu");
348 br->topology_change = 1;
349 mod_timer(&br->topology_change_timer, jiffies
350 + br->bridge_forward_delay + br->bridge_max_age);
351 } else if (!br->topology_change_detected) {
353 mod_timer(&br->tcn_timer, jiffies + br->bridge_hello_time);
356 br->topology_change_detected = 1;
359 /* called under bridge lock */
360 void br_config_bpdu_generation(struct net_bridge *br)
362 struct net_bridge_port *p;
364 list_for_each_entry(p, &br->port_list, list) {
365 if (p->state != BR_STATE_DISABLED &&
366 br_is_designated_port(p))
367 br_transmit_config(p);
371 /* called under bridge lock */
372 static void br_reply(struct net_bridge_port *p)
374 br_transmit_config(p);
377 /* called under bridge lock */
378 void br_configuration_update(struct net_bridge *br)
380 br_root_selection(br);
381 br_designated_port_selection(br);
384 /* called under bridge lock */
385 void br_become_designated_port(struct net_bridge_port *p)
387 struct net_bridge *br;
390 p->designated_root = br->designated_root;
391 p->designated_cost = br->root_path_cost;
392 p->designated_bridge = br->bridge_id;
393 p->designated_port = p->port_id;
397 /* called under bridge lock */
398 static void br_make_blocking(struct net_bridge_port *p)
400 if (p->state != BR_STATE_DISABLED &&
401 p->state != BR_STATE_BLOCKING) {
402 if (p->state == BR_STATE_FORWARDING ||
403 p->state == BR_STATE_LEARNING)
404 br_topology_change_detection(p->br);
406 br_set_state(p, BR_STATE_BLOCKING);
408 br_ifinfo_notify(RTM_NEWLINK, p);
410 del_timer(&p->forward_delay_timer);
414 /* called under bridge lock */
415 static void br_make_forwarding(struct net_bridge_port *p)
417 struct net_bridge *br = p->br;
419 if (p->state != BR_STATE_BLOCKING)
422 if (br->stp_enabled == BR_NO_STP || br->forward_delay == 0) {
423 br_set_state(p, BR_STATE_FORWARDING);
424 br_topology_change_detection(br);
425 del_timer(&p->forward_delay_timer);
426 } else if (br->stp_enabled == BR_KERNEL_STP)
427 br_set_state(p, BR_STATE_LISTENING);
429 br_set_state(p, BR_STATE_LEARNING);
432 br_ifinfo_notify(RTM_NEWLINK, p);
434 if (br->forward_delay != 0)
435 mod_timer(&p->forward_delay_timer, jiffies + br->forward_delay);
438 /* called under bridge lock */
439 void br_port_state_selection(struct net_bridge *br)
441 struct net_bridge_port *p;
442 unsigned int liveports = 0;
444 list_for_each_entry(p, &br->port_list, list) {
445 if (p->state == BR_STATE_DISABLED)
448 /* Don't change port states if userspace is handling STP */
449 if (br->stp_enabled != BR_USER_STP) {
450 if (p->port_no == br->root_port) {
451 p->config_pending = 0;
452 p->topology_change_ack = 0;
453 br_make_forwarding(p);
454 } else if (br_is_designated_port(p)) {
455 del_timer(&p->message_age_timer);
456 br_make_forwarding(p);
458 p->config_pending = 0;
459 p->topology_change_ack = 0;
464 if (p->state != BR_STATE_BLOCKING)
465 br_multicast_enable_port(p);
466 /* Multicast is not disabled for the port when it goes in
467 * blocking state because the timers will expire and stop by
468 * themselves without sending more queries.
470 if (p->state == BR_STATE_FORWARDING)
475 netif_carrier_off(br->dev);
477 netif_carrier_on(br->dev);
480 /* called under bridge lock */
481 static void br_topology_change_acknowledge(struct net_bridge_port *p)
483 p->topology_change_ack = 1;
484 br_transmit_config(p);
487 /* called under bridge lock */
488 void br_received_config_bpdu(struct net_bridge_port *p,
489 const struct br_config_bpdu *bpdu)
491 struct net_bridge *br;
495 was_root = br_is_root_bridge(br);
497 if (br_supersedes_port_info(p, bpdu)) {
498 br_record_config_information(p, bpdu);
499 br_configuration_update(br);
500 br_port_state_selection(br);
502 if (!br_is_root_bridge(br) && was_root) {
503 del_timer(&br->hello_timer);
504 if (br->topology_change_detected) {
505 del_timer(&br->topology_change_timer);
508 mod_timer(&br->tcn_timer,
509 jiffies + br->bridge_hello_time);
513 if (p->port_no == br->root_port) {
514 br_record_config_timeout_values(br, bpdu);
515 br_config_bpdu_generation(br);
516 if (bpdu->topology_change_ack)
517 br_topology_change_acknowledged(br);
519 } else if (br_is_designated_port(p)) {
524 /* called under bridge lock */
525 void br_received_tcn_bpdu(struct net_bridge_port *p)
527 if (br_is_designated_port(p)) {
528 br_info(p->br, "port %u(%s) received tcn bpdu\n",
529 (unsigned int) p->port_no, p->dev->name);
531 br_topology_change_detection(p->br);
532 br_topology_change_acknowledge(p);
536 /* Change bridge STP parameter */
537 int br_set_hello_time(struct net_bridge *br, unsigned long val)
539 unsigned long t = clock_t_to_jiffies(val);
541 if (t < BR_MIN_HELLO_TIME || t > BR_MAX_HELLO_TIME)
544 spin_lock_bh(&br->lock);
545 br->bridge_hello_time = t;
546 if (br_is_root_bridge(br))
547 br->hello_time = br->bridge_hello_time;
548 spin_unlock_bh(&br->lock);
552 int br_set_max_age(struct net_bridge *br, unsigned long val)
554 unsigned long t = clock_t_to_jiffies(val);
556 if (t < BR_MIN_MAX_AGE || t > BR_MAX_MAX_AGE)
559 spin_lock_bh(&br->lock);
560 br->bridge_max_age = t;
561 if (br_is_root_bridge(br))
562 br->max_age = br->bridge_max_age;
563 spin_unlock_bh(&br->lock);
568 void __br_set_forward_delay(struct net_bridge *br, unsigned long t)
570 br->bridge_forward_delay = t;
571 if (br_is_root_bridge(br))
572 br->forward_delay = br->bridge_forward_delay;
575 int br_set_forward_delay(struct net_bridge *br, unsigned long val)
577 unsigned long t = clock_t_to_jiffies(val);
580 spin_lock_bh(&br->lock);
581 if (br->stp_enabled != BR_NO_STP &&
582 (t < BR_MIN_FORWARD_DELAY || t > BR_MAX_FORWARD_DELAY))
585 __br_set_forward_delay(br, t);
589 spin_unlock_bh(&br->lock);