2 * Spanning tree protocol; generic parts
3 * Linux ethernet bridge
6 * Lennert Buytenhek <buytenh@gnu.org>
8 * $Id: br_stp.c,v 1.4 2000/06/19 10:13:35 davem Exp $
10 * This program is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU General Public License
12 * as published by the Free Software Foundation; either version
13 * 2 of the License, or (at your option) any later version.
15 #include <linux/kernel.h>
16 #include <linux/smp_lock.h>
18 #include "br_private.h"
19 #include "br_private_stp.h"
21 static const char *br_port_state_names[] = {
22 [BR_STATE_DISABLED] = "disabled",
23 [BR_STATE_LISTENING] = "listening",
24 [BR_STATE_LEARNING] = "learning",
25 [BR_STATE_FORWARDING] = "forwarding",
26 [BR_STATE_BLOCKING] = "blocking",
29 void br_log_state(const struct net_bridge_port *p)
31 pr_info("%s: port %d(%s) entering %s state\n",
32 p->br->dev->name, p->port_no, p->dev->name,
33 br_port_state_names[p->state]);
37 /* called under bridge lock */
38 struct net_bridge_port *br_get_port(struct net_bridge *br, u16 port_no)
40 struct net_bridge_port *p;
42 list_for_each_entry_rcu(p, &br->port_list, list) {
43 if (p->port_no == port_no)
50 /* called under bridge lock */
51 static int br_should_become_root_port(const struct net_bridge_port *p,
54 struct net_bridge *br;
55 struct net_bridge_port *rp;
59 if (p->state == BR_STATE_DISABLED ||
60 br_is_designated_port(p))
63 if (memcmp(&br->bridge_id, &p->designated_root, 8) <= 0)
69 rp = br_get_port(br, root_port);
71 t = memcmp(&p->designated_root, &rp->designated_root, 8);
77 if (p->designated_cost + p->path_cost <
78 rp->designated_cost + rp->path_cost)
80 else if (p->designated_cost + p->path_cost >
81 rp->designated_cost + rp->path_cost)
84 t = memcmp(&p->designated_bridge, &rp->designated_bridge, 8);
90 if (p->designated_port < rp->designated_port)
92 else if (p->designated_port > rp->designated_port)
95 if (p->port_id < rp->port_id)
101 /* called under bridge lock */
102 static void br_root_selection(struct net_bridge *br)
104 struct net_bridge_port *p;
107 list_for_each_entry(p, &br->port_list, list) {
108 if (br_should_become_root_port(p, root_port))
109 root_port = p->port_no;
113 br->root_port = root_port;
116 br->designated_root = br->bridge_id;
117 br->root_path_cost = 0;
119 p = br_get_port(br, root_port);
120 br->designated_root = p->designated_root;
121 br->root_path_cost = p->designated_cost + p->path_cost;
125 /* called under bridge lock */
126 void br_become_root_bridge(struct net_bridge *br)
128 br->max_age = br->bridge_max_age;
129 br->hello_time = br->bridge_hello_time;
130 br->forward_delay = br->bridge_forward_delay;
131 br_topology_change_detection(br);
132 del_timer(&br->tcn_timer);
134 if (br->dev->flags & IFF_UP) {
135 br_config_bpdu_generation(br);
136 mod_timer(&br->hello_timer, jiffies + br->hello_time);
140 /* called under bridge lock */
141 void br_transmit_config(struct net_bridge_port *p)
143 struct br_config_bpdu bpdu;
144 struct net_bridge *br;
147 if (timer_pending(&p->hold_timer)) {
148 p->config_pending = 1;
154 bpdu.topology_change = br->topology_change;
155 bpdu.topology_change_ack = p->topology_change_ack;
156 bpdu.root = br->designated_root;
157 bpdu.root_path_cost = br->root_path_cost;
158 bpdu.bridge_id = br->bridge_id;
159 bpdu.port_id = p->port_id;
160 bpdu.message_age = 0;
161 if (!br_is_root_bridge(br)) {
162 struct net_bridge_port *root
163 = br_get_port(br, br->root_port);
164 bpdu.max_age = root->message_age_timer.expires - jiffies;
166 if (bpdu.max_age <= 0) bpdu.max_age = 1;
168 bpdu.max_age = br->max_age;
169 bpdu.hello_time = br->hello_time;
170 bpdu.forward_delay = br->forward_delay;
172 br_send_config_bpdu(p, &bpdu);
174 p->topology_change_ack = 0;
175 p->config_pending = 0;
177 mod_timer(&p->hold_timer, jiffies + BR_HOLD_TIME);
180 /* called under bridge lock */
181 static inline void br_record_config_information(struct net_bridge_port *p,
182 const struct br_config_bpdu *bpdu)
184 p->designated_root = bpdu->root;
185 p->designated_cost = bpdu->root_path_cost;
186 p->designated_bridge = bpdu->bridge_id;
187 p->designated_port = bpdu->port_id;
189 mod_timer(&p->message_age_timer, jiffies
190 + (p->br->max_age - bpdu->message_age));
193 /* called under bridge lock */
194 static inline void br_record_config_timeout_values(struct net_bridge *br,
195 const struct br_config_bpdu *bpdu)
197 br->max_age = bpdu->max_age;
198 br->hello_time = bpdu->hello_time;
199 br->forward_delay = bpdu->forward_delay;
200 br->topology_change = bpdu->topology_change;
203 /* called under bridge lock */
204 void br_transmit_tcn(struct net_bridge *br)
206 br_send_tcn_bpdu(br_get_port(br, br->root_port));
209 /* called under bridge lock */
210 static int br_should_become_designated_port(const struct net_bridge_port *p)
212 struct net_bridge *br;
216 if (br_is_designated_port(p))
219 if (memcmp(&p->designated_root, &br->designated_root, 8))
222 if (br->root_path_cost < p->designated_cost)
224 else if (br->root_path_cost > p->designated_cost)
227 t = memcmp(&br->bridge_id, &p->designated_bridge, 8);
233 if (p->port_id < p->designated_port)
239 /* called under bridge lock */
240 static void br_designated_port_selection(struct net_bridge *br)
242 struct net_bridge_port *p;
244 list_for_each_entry(p, &br->port_list, list) {
245 if (p->state != BR_STATE_DISABLED &&
246 br_should_become_designated_port(p))
247 br_become_designated_port(p);
252 /* called under bridge lock */
253 static int br_supersedes_port_info(struct net_bridge_port *p, struct br_config_bpdu *bpdu)
257 t = memcmp(&bpdu->root, &p->designated_root, 8);
263 if (bpdu->root_path_cost < p->designated_cost)
265 else if (bpdu->root_path_cost > p->designated_cost)
268 t = memcmp(&bpdu->bridge_id, &p->designated_bridge, 8);
274 if (memcmp(&bpdu->bridge_id, &p->br->bridge_id, 8))
277 if (bpdu->port_id <= p->designated_port)
283 /* called under bridge lock */
284 static inline void br_topology_change_acknowledged(struct net_bridge *br)
286 br->topology_change_detected = 0;
287 del_timer(&br->tcn_timer);
290 /* called under bridge lock */
291 void br_topology_change_detection(struct net_bridge *br)
293 int isroot = br_is_root_bridge(br);
295 pr_info("%s: topology change detected, %s\n", br->dev->name,
296 isroot ? "propgating" : "sending tcn bpdu");
299 br->topology_change = 1;
300 mod_timer(&br->topology_change_timer, jiffies
301 + br->bridge_forward_delay + br->bridge_max_age);
302 } else if (!br->topology_change_detected) {
304 mod_timer(&br->tcn_timer, jiffies + br->bridge_hello_time);
307 br->topology_change_detected = 1;
310 /* called under bridge lock */
311 void br_config_bpdu_generation(struct net_bridge *br)
313 struct net_bridge_port *p;
315 list_for_each_entry(p, &br->port_list, list) {
316 if (p->state != BR_STATE_DISABLED &&
317 br_is_designated_port(p))
318 br_transmit_config(p);
322 /* called under bridge lock */
323 static inline void br_reply(struct net_bridge_port *p)
325 br_transmit_config(p);
328 /* called under bridge lock */
329 void br_configuration_update(struct net_bridge *br)
331 br_root_selection(br);
332 br_designated_port_selection(br);
335 /* called under bridge lock */
336 void br_become_designated_port(struct net_bridge_port *p)
338 struct net_bridge *br;
341 p->designated_root = br->designated_root;
342 p->designated_cost = br->root_path_cost;
343 p->designated_bridge = br->bridge_id;
344 p->designated_port = p->port_id;
348 /* called under bridge lock */
349 static void br_make_blocking(struct net_bridge_port *p)
351 if (p->state != BR_STATE_DISABLED &&
352 p->state != BR_STATE_BLOCKING) {
353 if (p->state == BR_STATE_FORWARDING ||
354 p->state == BR_STATE_LEARNING)
355 br_topology_change_detection(p->br);
357 p->state = BR_STATE_BLOCKING;
359 del_timer(&p->forward_delay_timer);
363 /* called under bridge lock */
364 static void br_make_forwarding(struct net_bridge_port *p)
366 if (p->state == BR_STATE_BLOCKING) {
367 if (p->br->stp_enabled) {
368 p->state = BR_STATE_LISTENING;
370 p->state = BR_STATE_LEARNING;
373 mod_timer(&p->forward_delay_timer, jiffies + p->br->forward_delay); }
376 /* called under bridge lock */
377 void br_port_state_selection(struct net_bridge *br)
379 struct net_bridge_port *p;
381 list_for_each_entry(p, &br->port_list, list) {
382 if (p->state != BR_STATE_DISABLED) {
383 if (p->port_no == br->root_port) {
384 p->config_pending = 0;
385 p->topology_change_ack = 0;
386 br_make_forwarding(p);
387 } else if (br_is_designated_port(p)) {
388 del_timer(&p->message_age_timer);
389 br_make_forwarding(p);
391 p->config_pending = 0;
392 p->topology_change_ack = 0;
400 /* called under bridge lock */
401 static inline void br_topology_change_acknowledge(struct net_bridge_port *p)
403 p->topology_change_ack = 1;
404 br_transmit_config(p);
407 /* called under bridge lock */
408 void br_received_config_bpdu(struct net_bridge_port *p, struct br_config_bpdu *bpdu)
410 struct net_bridge *br;
414 was_root = br_is_root_bridge(br);
416 if (br_supersedes_port_info(p, bpdu)) {
417 br_record_config_information(p, bpdu);
418 br_configuration_update(br);
419 br_port_state_selection(br);
421 if (!br_is_root_bridge(br) && was_root) {
422 del_timer(&br->hello_timer);
423 if (br->topology_change_detected) {
424 del_timer(&br->topology_change_timer);
427 mod_timer(&br->tcn_timer,
428 jiffies + br->bridge_hello_time);
432 if (p->port_no == br->root_port) {
433 br_record_config_timeout_values(br, bpdu);
434 br_config_bpdu_generation(br);
435 if (bpdu->topology_change_ack)
436 br_topology_change_acknowledged(br);
438 } else if (br_is_designated_port(p)) {
443 /* called under bridge lock */
444 void br_received_tcn_bpdu(struct net_bridge_port *p)
446 if (br_is_designated_port(p)) {
447 pr_info("%s: received tcn bpdu on port %i(%s)\n",
448 p->br->dev->name, p->port_no, p->dev->name);
450 br_topology_change_detection(p->br);
451 br_topology_change_acknowledge(p);