blob: 57186d84d2bd6497366d7d4d7cca7a694e0b5818 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
2 * Spanning tree protocol; generic parts
3 * Linux ethernet bridge
4 *
5 * Authors:
6 * Lennert Buytenhek <buytenh@gnu.org>
7 *
Linus Torvalds1da177e2005-04-16 15:20:36 -07008 * 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.
12 */
13#include <linux/kernel.h>
Franck Bui-Huu82524742008-05-12 21:21:05 +020014#include <linux/rculist.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070015
16#include "br_private.h"
17#include "br_private_stp.h"
18
19/* since time values in bpdu are in jiffies and then scaled (1/256)
20 * before sending, make sure that is at least one.
21 */
22#define MESSAGE_AGE_INCR ((HZ < 256) ? 1 : (HZ/256))
23
Jan Engelhardt36cbd3d2009-08-05 10:42:58 -070024static const char *const br_port_state_names[] = {
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +090025 [BR_STATE_DISABLED] = "disabled",
Linus Torvalds1da177e2005-04-16 15:20:36 -070026 [BR_STATE_LISTENING] = "listening",
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +090027 [BR_STATE_LEARNING] = "learning",
28 [BR_STATE_FORWARDING] = "forwarding",
Linus Torvalds1da177e2005-04-16 15:20:36 -070029 [BR_STATE_BLOCKING] = "blocking",
30};
31
32void br_log_state(const struct net_bridge_port *p)
33{
stephen hemminger28a16c92010-05-10 09:31:09 +000034 br_info(p->br, "port %u(%s) entering %s state\n",
35 (unsigned) p->port_no, p->dev->name,
Linus Torvalds1da177e2005-04-16 15:20:36 -070036 br_port_state_names[p->state]);
Linus Torvalds1da177e2005-04-16 15:20:36 -070037}
38
39/* called under bridge lock */
40struct net_bridge_port *br_get_port(struct net_bridge *br, u16 port_no)
41{
42 struct net_bridge_port *p;
43
44 list_for_each_entry_rcu(p, &br->port_list, list) {
45 if (p->port_no == port_no)
46 return p;
47 }
48
49 return NULL;
50}
51
52/* called under bridge lock */
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +090053static int br_should_become_root_port(const struct net_bridge_port *p,
Linus Torvalds1da177e2005-04-16 15:20:36 -070054 u16 root_port)
55{
56 struct net_bridge *br;
57 struct net_bridge_port *rp;
58 int t;
59
60 br = p->br;
61 if (p->state == BR_STATE_DISABLED ||
62 br_is_designated_port(p))
63 return 0;
64
65 if (memcmp(&br->bridge_id, &p->designated_root, 8) <= 0)
66 return 0;
67
68 if (!root_port)
69 return 1;
70
71 rp = br_get_port(br, root_port);
72
73 t = memcmp(&p->designated_root, &rp->designated_root, 8);
74 if (t < 0)
75 return 1;
76 else if (t > 0)
77 return 0;
78
79 if (p->designated_cost + p->path_cost <
80 rp->designated_cost + rp->path_cost)
81 return 1;
82 else if (p->designated_cost + p->path_cost >
83 rp->designated_cost + rp->path_cost)
84 return 0;
85
86 t = memcmp(&p->designated_bridge, &rp->designated_bridge, 8);
87 if (t < 0)
88 return 1;
89 else if (t > 0)
90 return 0;
91
92 if (p->designated_port < rp->designated_port)
93 return 1;
94 else if (p->designated_port > rp->designated_port)
95 return 0;
96
97 if (p->port_id < rp->port_id)
98 return 1;
99
100 return 0;
101}
102
103/* called under bridge lock */
104static void br_root_selection(struct net_bridge *br)
105{
106 struct net_bridge_port *p;
107 u16 root_port = 0;
108
109 list_for_each_entry(p, &br->port_list, list) {
110 if (br_should_become_root_port(p, root_port))
111 root_port = p->port_no;
112
113 }
114
115 br->root_port = root_port;
116
117 if (!root_port) {
118 br->designated_root = br->bridge_id;
119 br->root_path_cost = 0;
120 } else {
121 p = br_get_port(br, root_port);
122 br->designated_root = p->designated_root;
123 br->root_path_cost = p->designated_cost + p->path_cost;
124 }
125}
126
127/* called under bridge lock */
128void br_become_root_bridge(struct net_bridge *br)
129{
130 br->max_age = br->bridge_max_age;
131 br->hello_time = br->bridge_hello_time;
132 br->forward_delay = br->bridge_forward_delay;
133 br_topology_change_detection(br);
134 del_timer(&br->tcn_timer);
135
136 if (br->dev->flags & IFF_UP) {
137 br_config_bpdu_generation(br);
138 mod_timer(&br->hello_timer, jiffies + br->hello_time);
139 }
140}
141
142/* called under bridge lock */
143void br_transmit_config(struct net_bridge_port *p)
144{
145 struct br_config_bpdu bpdu;
146 struct net_bridge *br;
147
148
149 if (timer_pending(&p->hold_timer)) {
150 p->config_pending = 1;
151 return;
152 }
153
154 br = p->br;
155
156 bpdu.topology_change = br->topology_change;
157 bpdu.topology_change_ack = p->topology_change_ack;
158 bpdu.root = br->designated_root;
159 bpdu.root_path_cost = br->root_path_cost;
160 bpdu.bridge_id = br->bridge_id;
161 bpdu.port_id = p->port_id;
162 if (br_is_root_bridge(br))
163 bpdu.message_age = 0;
164 else {
165 struct net_bridge_port *root
166 = br_get_port(br, br->root_port);
167 bpdu.message_age = br->max_age
168 - (root->message_age_timer.expires - jiffies)
169 + MESSAGE_AGE_INCR;
170 }
171 bpdu.max_age = br->max_age;
172 bpdu.hello_time = br->hello_time;
173 bpdu.forward_delay = br->forward_delay;
174
175 if (bpdu.message_age < br->max_age) {
176 br_send_config_bpdu(p, &bpdu);
177 p->topology_change_ack = 0;
178 p->config_pending = 0;
Stephen Hemminger9a834b82007-05-31 01:21:39 -0700179 mod_timer(&p->hold_timer,
180 round_jiffies(jiffies + BR_HOLD_TIME));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700181 }
182}
183
184/* called under bridge lock */
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +0900185static inline void br_record_config_information(struct net_bridge_port *p,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700186 const struct br_config_bpdu *bpdu)
187{
188 p->designated_root = bpdu->root;
189 p->designated_cost = bpdu->root_path_cost;
190 p->designated_bridge = bpdu->bridge_id;
191 p->designated_port = bpdu->port_id;
192
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +0900193 mod_timer(&p->message_age_timer, jiffies
Linus Torvalds1da177e2005-04-16 15:20:36 -0700194 + (p->br->max_age - bpdu->message_age));
195}
196
197/* called under bridge lock */
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +0900198static inline void br_record_config_timeout_values(struct net_bridge *br,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700199 const struct br_config_bpdu *bpdu)
200{
201 br->max_age = bpdu->max_age;
202 br->hello_time = bpdu->hello_time;
203 br->forward_delay = bpdu->forward_delay;
204 br->topology_change = bpdu->topology_change;
205}
206
207/* called under bridge lock */
208void br_transmit_tcn(struct net_bridge *br)
209{
210 br_send_tcn_bpdu(br_get_port(br, br->root_port));
211}
212
213/* called under bridge lock */
214static int br_should_become_designated_port(const struct net_bridge_port *p)
215{
216 struct net_bridge *br;
217 int t;
218
219 br = p->br;
220 if (br_is_designated_port(p))
221 return 1;
222
223 if (memcmp(&p->designated_root, &br->designated_root, 8))
224 return 1;
225
226 if (br->root_path_cost < p->designated_cost)
227 return 1;
228 else if (br->root_path_cost > p->designated_cost)
229 return 0;
230
231 t = memcmp(&br->bridge_id, &p->designated_bridge, 8);
232 if (t < 0)
233 return 1;
234 else if (t > 0)
235 return 0;
236
237 if (p->port_id < p->designated_port)
238 return 1;
239
240 return 0;
241}
242
243/* called under bridge lock */
244static void br_designated_port_selection(struct net_bridge *br)
245{
246 struct net_bridge_port *p;
247
248 list_for_each_entry(p, &br->port_list, list) {
249 if (p->state != BR_STATE_DISABLED &&
250 br_should_become_designated_port(p))
251 br_become_designated_port(p);
252
253 }
254}
255
256/* called under bridge lock */
257static int br_supersedes_port_info(struct net_bridge_port *p, struct br_config_bpdu *bpdu)
258{
259 int t;
260
261 t = memcmp(&bpdu->root, &p->designated_root, 8);
262 if (t < 0)
263 return 1;
264 else if (t > 0)
265 return 0;
266
267 if (bpdu->root_path_cost < p->designated_cost)
268 return 1;
269 else if (bpdu->root_path_cost > p->designated_cost)
270 return 0;
271
272 t = memcmp(&bpdu->bridge_id, &p->designated_bridge, 8);
273 if (t < 0)
274 return 1;
275 else if (t > 0)
276 return 0;
277
278 if (memcmp(&bpdu->bridge_id, &p->br->bridge_id, 8))
279 return 1;
280
281 if (bpdu->port_id <= p->designated_port)
282 return 1;
283
284 return 0;
285}
286
287/* called under bridge lock */
288static inline void br_topology_change_acknowledged(struct net_bridge *br)
289{
290 br->topology_change_detected = 0;
291 del_timer(&br->tcn_timer);
292}
293
294/* called under bridge lock */
295void br_topology_change_detection(struct net_bridge *br)
296{
297 int isroot = br_is_root_bridge(br);
298
Stephen Hemminger4f0611a2009-05-15 06:11:58 +0000299 if (br->stp_enabled != BR_KERNEL_STP)
300 return;
301
stephen hemminger28a16c92010-05-10 09:31:09 +0000302 br_info(br, "topology change detected, %s\n",
Linus Torvalds1da177e2005-04-16 15:20:36 -0700303 isroot ? "propagating" : "sending tcn bpdu");
304
305 if (isroot) {
306 br->topology_change = 1;
307 mod_timer(&br->topology_change_timer, jiffies
308 + br->bridge_forward_delay + br->bridge_max_age);
309 } else if (!br->topology_change_detected) {
310 br_transmit_tcn(br);
311 mod_timer(&br->tcn_timer, jiffies + br->bridge_hello_time);
312 }
313
314 br->topology_change_detected = 1;
315}
316
317/* called under bridge lock */
318void br_config_bpdu_generation(struct net_bridge *br)
319{
320 struct net_bridge_port *p;
321
322 list_for_each_entry(p, &br->port_list, list) {
323 if (p->state != BR_STATE_DISABLED &&
324 br_is_designated_port(p))
325 br_transmit_config(p);
326 }
327}
328
329/* called under bridge lock */
330static inline void br_reply(struct net_bridge_port *p)
331{
332 br_transmit_config(p);
333}
334
335/* called under bridge lock */
336void br_configuration_update(struct net_bridge *br)
337{
338 br_root_selection(br);
339 br_designated_port_selection(br);
340}
341
342/* called under bridge lock */
343void br_become_designated_port(struct net_bridge_port *p)
344{
345 struct net_bridge *br;
346
347 br = p->br;
348 p->designated_root = br->designated_root;
349 p->designated_cost = br->root_path_cost;
350 p->designated_bridge = br->bridge_id;
351 p->designated_port = p->port_id;
352}
353
354
355/* called under bridge lock */
356static void br_make_blocking(struct net_bridge_port *p)
357{
358 if (p->state != BR_STATE_DISABLED &&
359 p->state != BR_STATE_BLOCKING) {
360 if (p->state == BR_STATE_FORWARDING ||
361 p->state == BR_STATE_LEARNING)
362 br_topology_change_detection(p->br);
363
364 p->state = BR_STATE_BLOCKING;
365 br_log_state(p);
366 del_timer(&p->forward_delay_timer);
367 }
368}
369
370/* called under bridge lock */
371static void br_make_forwarding(struct net_bridge_port *p)
372{
Stephen Hemmingeref647f12008-08-05 18:42:51 -0700373 struct net_bridge *br = p->br;
Stephen Hemminger9cde0702007-03-21 14:22:44 -0700374
Stephen Hemmingeref647f12008-08-05 18:42:51 -0700375 if (p->state != BR_STATE_BLOCKING)
376 return;
377
378 if (br->forward_delay == 0) {
379 p->state = BR_STATE_FORWARDING;
380 br_topology_change_detection(br);
381 del_timer(&p->forward_delay_timer);
382 }
383 else if (p->br->stp_enabled == BR_KERNEL_STP)
384 p->state = BR_STATE_LISTENING;
385 else
386 p->state = BR_STATE_LEARNING;
387
Herbert Xu3fe2d7c2010-02-28 00:49:38 -0800388 br_multicast_enable_port(p);
389
Stephen Hemmingeref647f12008-08-05 18:42:51 -0700390 br_log_state(p);
391
392 if (br->forward_delay != 0)
393 mod_timer(&p->forward_delay_timer, jiffies + br->forward_delay);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700394}
395
396/* called under bridge lock */
397void br_port_state_selection(struct net_bridge *br)
398{
399 struct net_bridge_port *p;
400
Stephen Hemminger9cde0702007-03-21 14:22:44 -0700401 /* Don't change port states if userspace is handling STP */
402 if (br->stp_enabled == BR_USER_STP)
403 return;
404
Linus Torvalds1da177e2005-04-16 15:20:36 -0700405 list_for_each_entry(p, &br->port_list, list) {
406 if (p->state != BR_STATE_DISABLED) {
407 if (p->port_no == br->root_port) {
408 p->config_pending = 0;
409 p->topology_change_ack = 0;
410 br_make_forwarding(p);
411 } else if (br_is_designated_port(p)) {
412 del_timer(&p->message_age_timer);
413 br_make_forwarding(p);
414 } else {
415 p->config_pending = 0;
416 p->topology_change_ack = 0;
417 br_make_blocking(p);
418 }
419 }
420
421 }
422}
423
424/* called under bridge lock */
425static inline void br_topology_change_acknowledge(struct net_bridge_port *p)
426{
427 p->topology_change_ack = 1;
428 br_transmit_config(p);
429}
430
431/* called under bridge lock */
432void br_received_config_bpdu(struct net_bridge_port *p, struct br_config_bpdu *bpdu)
433{
434 struct net_bridge *br;
435 int was_root;
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +0900436
Linus Torvalds1da177e2005-04-16 15:20:36 -0700437 br = p->br;
438 was_root = br_is_root_bridge(br);
439
440 if (br_supersedes_port_info(p, bpdu)) {
441 br_record_config_information(p, bpdu);
442 br_configuration_update(br);
443 br_port_state_selection(br);
444
445 if (!br_is_root_bridge(br) && was_root) {
446 del_timer(&br->hello_timer);
447 if (br->topology_change_detected) {
448 del_timer(&br->topology_change_timer);
449 br_transmit_tcn(br);
450
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +0900451 mod_timer(&br->tcn_timer,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700452 jiffies + br->bridge_hello_time);
453 }
454 }
455
456 if (p->port_no == br->root_port) {
457 br_record_config_timeout_values(br, bpdu);
458 br_config_bpdu_generation(br);
459 if (bpdu->topology_change_ack)
460 br_topology_change_acknowledged(br);
461 }
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +0900462 } else if (br_is_designated_port(p)) {
463 br_reply(p);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700464 }
465}
466
467/* called under bridge lock */
468void br_received_tcn_bpdu(struct net_bridge_port *p)
469{
470 if (br_is_designated_port(p)) {
stephen hemminger28a16c92010-05-10 09:31:09 +0000471 br_info(p->br, "port %u(%s) received tcn bpdu\n",
472 (unsigned) p->port_no, p->dev->name);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700473
474 br_topology_change_detection(p->br);
475 br_topology_change_acknowledge(p);
476 }
477}