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>
16 #include "br_private.h"
17 #include "br_private_stp.h"
19 /* since time values in bpdu are in jiffies and then scaled (1/256)
20 * before sending, make sure that is at least one.
22 #define MESSAGE_AGE_INCR ((HZ < 256) ? 1 : (HZ/256))
24 static const char *br_port_state_names[] = {
25 [BR_STATE_DISABLED] = "disabled",
26 [BR_STATE_LISTENING] = "listening",
27 [BR_STATE_LEARNING] = "learning",
28 [BR_STATE_FORWARDING] = "forwarding",
29 [BR_STATE_BLOCKING] = "blocking",
32 void br_log_state(const struct net_bridge_port *p)
34 pr_info("%s: port %d(%s) entering %s state\n",
35 p->br->dev->name, p->port_no, p->dev->name,
36 br_port_state_names[p->state]);
40 /* called under bridge lock */
41 struct net_bridge_port *br_get_port(struct net_bridge *br, u16 port_no)
43 struct net_bridge_port *p;
45 list_for_each_entry_rcu(p, &br->port_list, list) {
46 if (p->port_no == port_no)
53 /* called under bridge lock */
54 static int br_should_become_root_port(const struct net_bridge_port *p,
57 struct net_bridge *br;
58 struct net_bridge_port *rp;
62 if (p->state == BR_STATE_DISABLED ||
63 br_is_designated_port(p))
66 if (memcmp(&br->bridge_id, &p->designated_root, 8) <= 0)
72 rp = br_get_port(br, root_port);
74 t = memcmp(&p->designated_root, &rp->designated_root, 8);
80 if (p->designated_cost + p->path_cost <
81 rp->designated_cost + rp->path_cost)
83 else if (p->designated_cost + p->path_cost >
84 rp->designated_cost + rp->path_cost)
87 t = memcmp(&p->designated_bridge, &rp->designated_bridge, 8);
93 if (p->designated_port < rp->designated_port)
95 else if (p->designated_port > rp->designated_port)
98 if (p->port_id < rp->port_id)
104 /* called under bridge lock */
105 static void br_root_selection(struct net_bridge *br)
107 struct net_bridge_port *p;
110 list_for_each_entry(p, &br->port_list, list) {
111 if (br_should_become_root_port(p, root_port))
112 root_port = p->port_no;
116 br->root_port = root_port;
119 br->designated_root = br->bridge_id;
120 br->root_path_cost = 0;
122 p = br_get_port(br, root_port);
123 br->designated_root = p->designated_root;
124 br->root_path_cost = p->designated_cost + p->path_cost;
128 /* called under bridge lock */
129 void br_become_root_bridge(struct net_bridge *br)
131 br->max_age = br->bridge_max_age;
132 br->hello_time = br->bridge_hello_time;
133 br->forward_delay = br->bridge_forward_delay;
134 br_topology_change_detection(br);
135 del_timer(&br->tcn_timer);
137 if (br->dev->flags & IFF_UP) {
138 br_config_bpdu_generation(br);
139 mod_timer(&br->hello_timer, jiffies + br->hello_time);
143 /* called under bridge lock */
144 void br_transmit_config(struct net_bridge_port *p)
146 struct br_config_bpdu bpdu;
147 struct net_bridge *br;
150 if (timer_pending(&p->hold_timer)) {
151 p->config_pending = 1;
157 bpdu.topology_change = br->topology_change;
158 bpdu.topology_change_ack = p->topology_change_ack;
159 bpdu.root = br->designated_root;
160 bpdu.root_path_cost = br->root_path_cost;
161 bpdu.bridge_id = br->bridge_id;
162 bpdu.port_id = p->port_id;
163 if (br_is_root_bridge(br))
164 bpdu.message_age = 0;
166 struct net_bridge_port *root
167 = br_get_port(br, br->root_port);
168 bpdu.message_age = br->max_age
169 - (root->message_age_timer.expires - jiffies)
172 bpdu.max_age = br->max_age;
173 bpdu.hello_time = br->hello_time;
174 bpdu.forward_delay = br->forward_delay;
176 if (bpdu.message_age < br->max_age) {
177 br_send_config_bpdu(p, &bpdu);
178 p->topology_change_ack = 0;
179 p->config_pending = 0;
180 mod_timer(&p->hold_timer,
181 round_jiffies(jiffies + BR_HOLD_TIME));
185 /* called under bridge lock */
186 static inline void br_record_config_information(struct net_bridge_port *p,
187 const struct br_config_bpdu *bpdu)
189 p->designated_root = bpdu->root;
190 p->designated_cost = bpdu->root_path_cost;
191 p->designated_bridge = bpdu->bridge_id;
192 p->designated_port = bpdu->port_id;
194 mod_timer(&p->message_age_timer, jiffies
195 + (p->br->max_age - bpdu->message_age));
198 /* called under bridge lock */
199 static inline void br_record_config_timeout_values(struct net_bridge *br,
200 const struct br_config_bpdu *bpdu)
202 br->max_age = bpdu->max_age;
203 br->hello_time = bpdu->hello_time;
204 br->forward_delay = bpdu->forward_delay;
205 br->topology_change = bpdu->topology_change;
208 /* called under bridge lock */
209 void br_transmit_tcn(struct net_bridge *br)
211 br_send_tcn_bpdu(br_get_port(br, br->root_port));
214 /* called under bridge lock */
215 static int br_should_become_designated_port(const struct net_bridge_port *p)
217 struct net_bridge *br;
221 if (br_is_designated_port(p))
224 if (memcmp(&p->designated_root, &br->designated_root, 8))
227 if (br->root_path_cost < p->designated_cost)
229 else if (br->root_path_cost > p->designated_cost)
232 t = memcmp(&br->bridge_id, &p->designated_bridge, 8);
238 if (p->port_id < p->designated_port)
244 /* called under bridge lock */
245 static void br_designated_port_selection(struct net_bridge *br)
247 struct net_bridge_port *p;
249 list_for_each_entry(p, &br->port_list, list) {
250 if (p->state != BR_STATE_DISABLED &&
251 br_should_become_designated_port(p))
252 br_become_designated_port(p);
257 /* called under bridge lock */
258 static int br_supersedes_port_info(struct net_bridge_port *p, struct br_config_bpdu *bpdu)
262 t = memcmp(&bpdu->root, &p->designated_root, 8);
268 if (bpdu->root_path_cost < p->designated_cost)
270 else if (bpdu->root_path_cost > p->designated_cost)
273 t = memcmp(&bpdu->bridge_id, &p->designated_bridge, 8);
279 if (memcmp(&bpdu->bridge_id, &p->br->bridge_id, 8))
282 if (bpdu->port_id <= p->designated_port)
288 /* called under bridge lock */
289 static inline void br_topology_change_acknowledged(struct net_bridge *br)
291 br->topology_change_detected = 0;
292 del_timer(&br->tcn_timer);
295 /* called under bridge lock */
296 void br_topology_change_detection(struct net_bridge *br)
298 int isroot = br_is_root_bridge(br);
300 pr_info("%s: topology change detected, %s\n", br->dev->name,
301 isroot ? "propagating" : "sending tcn bpdu");
304 br->topology_change = 1;
305 mod_timer(&br->topology_change_timer, jiffies
306 + br->bridge_forward_delay + br->bridge_max_age);
307 } else if (!br->topology_change_detected) {
309 mod_timer(&br->tcn_timer, jiffies + br->bridge_hello_time);
312 br->topology_change_detected = 1;
315 /* called under bridge lock */
316 void br_config_bpdu_generation(struct net_bridge *br)
318 struct net_bridge_port *p;
320 list_for_each_entry(p, &br->port_list, list) {
321 if (p->state != BR_STATE_DISABLED &&
322 br_is_designated_port(p))
323 br_transmit_config(p);
327 /* called under bridge lock */
328 static inline void br_reply(struct net_bridge_port *p)
330 br_transmit_config(p);
333 /* called under bridge lock */
334 void br_configuration_update(struct net_bridge *br)
336 br_root_selection(br);
337 br_designated_port_selection(br);
340 /* called under bridge lock */
341 void br_become_designated_port(struct net_bridge_port *p)
343 struct net_bridge *br;
346 p->designated_root = br->designated_root;
347 p->designated_cost = br->root_path_cost;
348 p->designated_bridge = br->bridge_id;
349 p->designated_port = p->port_id;
353 /* called under bridge lock */
354 static void br_make_blocking(struct net_bridge_port *p)
356 if (p->state != BR_STATE_DISABLED &&
357 p->state != BR_STATE_BLOCKING) {
358 if (p->state == BR_STATE_FORWARDING ||
359 p->state == BR_STATE_LEARNING)
360 br_topology_change_detection(p->br);
362 p->state = BR_STATE_BLOCKING;
364 del_timer(&p->forward_delay_timer);
368 /* called under bridge lock */
369 static void br_make_forwarding(struct net_bridge_port *p)
371 struct net_bridge *br = p->br;
373 if (p->state != BR_STATE_BLOCKING)
376 if (br->forward_delay == 0) {
377 p->state = BR_STATE_FORWARDING;
378 br_topology_change_detection(br);
379 del_timer(&p->forward_delay_timer);
381 else if (p->br->stp_enabled == BR_KERNEL_STP)
382 p->state = BR_STATE_LISTENING;
384 p->state = BR_STATE_LEARNING;
388 if (br->forward_delay != 0)
389 mod_timer(&p->forward_delay_timer, jiffies + br->forward_delay);
392 /* called under bridge lock */
393 void br_port_state_selection(struct net_bridge *br)
395 struct net_bridge_port *p;
397 /* Don't change port states if userspace is handling STP */
398 if (br->stp_enabled == BR_USER_STP)
401 list_for_each_entry(p, &br->port_list, list) {
402 if (p->state != BR_STATE_DISABLED) {
403 if (p->port_no == br->root_port) {
404 p->config_pending = 0;
405 p->topology_change_ack = 0;
406 br_make_forwarding(p);
407 } else if (br_is_designated_port(p)) {
408 del_timer(&p->message_age_timer);
409 br_make_forwarding(p);
411 p->config_pending = 0;
412 p->topology_change_ack = 0;
420 /* called under bridge lock */
421 static inline void br_topology_change_acknowledge(struct net_bridge_port *p)
423 p->topology_change_ack = 1;
424 br_transmit_config(p);
427 /* called under bridge lock */
428 void br_received_config_bpdu(struct net_bridge_port *p, struct br_config_bpdu *bpdu)
430 struct net_bridge *br;
434 was_root = br_is_root_bridge(br);
436 if (br_supersedes_port_info(p, bpdu)) {
437 br_record_config_information(p, bpdu);
438 br_configuration_update(br);
439 br_port_state_selection(br);
441 if (!br_is_root_bridge(br) && was_root) {
442 del_timer(&br->hello_timer);
443 if (br->topology_change_detected) {
444 del_timer(&br->topology_change_timer);
447 mod_timer(&br->tcn_timer,
448 jiffies + br->bridge_hello_time);
452 if (p->port_no == br->root_port) {
453 br_record_config_timeout_values(br, bpdu);
454 br_config_bpdu_generation(br);
455 if (bpdu->topology_change_ack)
456 br_topology_change_acknowledged(br);
458 } else if (br_is_designated_port(p)) {
463 /* called under bridge lock */
464 void br_received_tcn_bpdu(struct net_bridge_port *p)
466 if (br_is_designated_port(p)) {
467 pr_info("%s: received tcn bpdu on port %i(%s)\n",
468 p->br->dev->name, p->port_no, p->dev->name);
470 br_topology_change_detection(p->br);
471 br_topology_change_acknowledge(p);