blob: 2b047bcf42a4eb1c450c0283af9bea2676052836 [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)
Joakim Tjernlundaaca7352012-03-01 08:12:18 +000020 * before sending, make sure that is at least one STP tick.
Linus Torvalds1da177e2005-04-16 15:20:36 -070021 */
Joakim Tjernlundaaca7352012-03-01 08:12:18 +000022#define MESSAGE_AGE_INCR ((HZ / 256) + 1)
Linus Torvalds1da177e2005-04-16 15:20:36 -070023
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{
Paulius Zaleckasd9e179e2012-03-06 22:25:14 +000034 br_info(p->br, "port %u(%s) entered %s state\n",
Eric Dumazet95c96172012-04-15 05:58:06 +000035 (unsigned int) 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
Florian Fainelli775dd692014-09-30 16:13:19 -070039void br_set_state(struct net_bridge_port *p, unsigned int state)
40{
41 p->state = state;
42}
43
Linus Torvalds1da177e2005-04-16 15:20:36 -070044/* called under bridge lock */
45struct net_bridge_port *br_get_port(struct net_bridge *br, u16 port_no)
46{
47 struct net_bridge_port *p;
48
49 list_for_each_entry_rcu(p, &br->port_list, list) {
50 if (p->port_no == port_no)
51 return p;
52 }
53
54 return NULL;
55}
56
57/* called under bridge lock */
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +090058static int br_should_become_root_port(const struct net_bridge_port *p,
Linus Torvalds1da177e2005-04-16 15:20:36 -070059 u16 root_port)
60{
61 struct net_bridge *br;
62 struct net_bridge_port *rp;
63 int t;
64
65 br = p->br;
66 if (p->state == BR_STATE_DISABLED ||
67 br_is_designated_port(p))
68 return 0;
69
70 if (memcmp(&br->bridge_id, &p->designated_root, 8) <= 0)
71 return 0;
72
73 if (!root_port)
74 return 1;
75
76 rp = br_get_port(br, root_port);
77
78 t = memcmp(&p->designated_root, &rp->designated_root, 8);
79 if (t < 0)
80 return 1;
81 else if (t > 0)
82 return 0;
83
84 if (p->designated_cost + p->path_cost <
85 rp->designated_cost + rp->path_cost)
86 return 1;
87 else if (p->designated_cost + p->path_cost >
88 rp->designated_cost + rp->path_cost)
89 return 0;
90
91 t = memcmp(&p->designated_bridge, &rp->designated_bridge, 8);
92 if (t < 0)
93 return 1;
94 else if (t > 0)
95 return 0;
96
97 if (p->designated_port < rp->designated_port)
98 return 1;
99 else if (p->designated_port > rp->designated_port)
100 return 0;
101
102 if (p->port_id < rp->port_id)
103 return 1;
104
105 return 0;
106}
107
stephen hemminger1007dd12012-11-13 07:53:08 +0000108static void br_root_port_block(const struct net_bridge *br,
109 struct net_bridge_port *p)
110{
111
112 br_notice(br, "port %u(%s) tried to become root port (blocked)",
113 (unsigned int) p->port_no, p->dev->name);
114
Florian Fainelli775dd692014-09-30 16:13:19 -0700115 br_set_state(p, BR_STATE_LISTENING);
stephen hemminger1007dd12012-11-13 07:53:08 +0000116 br_log_state(p);
117 br_ifinfo_notify(RTM_NEWLINK, p);
118
119 if (br->forward_delay > 0)
120 mod_timer(&p->forward_delay_timer, jiffies + br->forward_delay);
121}
122
Linus Torvalds1da177e2005-04-16 15:20:36 -0700123/* called under bridge lock */
124static void br_root_selection(struct net_bridge *br)
125{
126 struct net_bridge_port *p;
127 u16 root_port = 0;
128
129 list_for_each_entry(p, &br->port_list, list) {
stephen hemminger1007dd12012-11-13 07:53:08 +0000130 if (!br_should_become_root_port(p, root_port))
131 continue;
132
133 if (p->flags & BR_ROOT_BLOCK)
134 br_root_port_block(br, p);
135 else
Linus Torvalds1da177e2005-04-16 15:20:36 -0700136 root_port = p->port_no;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700137 }
138
139 br->root_port = root_port;
140
141 if (!root_port) {
142 br->designated_root = br->bridge_id;
143 br->root_path_cost = 0;
144 } else {
145 p = br_get_port(br, root_port);
146 br->designated_root = p->designated_root;
147 br->root_path_cost = p->designated_cost + p->path_cost;
148 }
149}
150
151/* called under bridge lock */
152void br_become_root_bridge(struct net_bridge *br)
153{
154 br->max_age = br->bridge_max_age;
155 br->hello_time = br->bridge_hello_time;
156 br->forward_delay = br->bridge_forward_delay;
157 br_topology_change_detection(br);
158 del_timer(&br->tcn_timer);
159
160 if (br->dev->flags & IFF_UP) {
161 br_config_bpdu_generation(br);
162 mod_timer(&br->hello_timer, jiffies + br->hello_time);
163 }
164}
165
166/* called under bridge lock */
167void br_transmit_config(struct net_bridge_port *p)
168{
169 struct br_config_bpdu bpdu;
170 struct net_bridge *br;
171
Linus Torvalds1da177e2005-04-16 15:20:36 -0700172 if (timer_pending(&p->hold_timer)) {
173 p->config_pending = 1;
174 return;
175 }
176
177 br = p->br;
178
179 bpdu.topology_change = br->topology_change;
180 bpdu.topology_change_ack = p->topology_change_ack;
181 bpdu.root = br->designated_root;
182 bpdu.root_path_cost = br->root_path_cost;
183 bpdu.bridge_id = br->bridge_id;
184 bpdu.port_id = p->port_id;
185 if (br_is_root_bridge(br))
186 bpdu.message_age = 0;
187 else {
188 struct net_bridge_port *root
189 = br_get_port(br, br->root_port);
stephen hemminger0c031502011-07-22 07:47:06 +0000190 bpdu.message_age = (jiffies - root->designated_age)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700191 + MESSAGE_AGE_INCR;
192 }
193 bpdu.max_age = br->max_age;
194 bpdu.hello_time = br->hello_time;
195 bpdu.forward_delay = br->forward_delay;
196
197 if (bpdu.message_age < br->max_age) {
198 br_send_config_bpdu(p, &bpdu);
199 p->topology_change_ack = 0;
200 p->config_pending = 0;
Stephen Hemminger9a834b82007-05-31 01:21:39 -0700201 mod_timer(&p->hold_timer,
202 round_jiffies(jiffies + BR_HOLD_TIME));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700203 }
204}
205
206/* called under bridge lock */
stephen hemminger160d73b2011-07-22 07:47:10 +0000207static void br_record_config_information(struct net_bridge_port *p,
208 const struct br_config_bpdu *bpdu)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700209{
210 p->designated_root = bpdu->root;
211 p->designated_cost = bpdu->root_path_cost;
212 p->designated_bridge = bpdu->bridge_id;
213 p->designated_port = bpdu->port_id;
Joakim Tjernlund709e1b52012-03-01 08:12:19 +0000214 p->designated_age = jiffies - bpdu->message_age;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700215
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +0900216 mod_timer(&p->message_age_timer, jiffies
Chris Healy9a062012013-09-11 21:37:47 -0700217 + (bpdu->max_age - bpdu->message_age));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700218}
219
220/* called under bridge lock */
stephen hemminger160d73b2011-07-22 07:47:10 +0000221static void br_record_config_timeout_values(struct net_bridge *br,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700222 const struct br_config_bpdu *bpdu)
223{
224 br->max_age = bpdu->max_age;
225 br->hello_time = bpdu->hello_time;
226 br->forward_delay = bpdu->forward_delay;
227 br->topology_change = bpdu->topology_change;
228}
229
230/* called under bridge lock */
231void br_transmit_tcn(struct net_bridge *br)
232{
stephen hemminger91bc0332013-04-30 05:29:27 +0000233 struct net_bridge_port *p;
234
235 p = br_get_port(br, br->root_port);
236 if (p)
237 br_send_tcn_bpdu(p);
238 else
239 br_notice(br, "root port %u not found for topology notice\n",
240 br->root_port);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700241}
242
243/* called under bridge lock */
244static int br_should_become_designated_port(const struct net_bridge_port *p)
245{
246 struct net_bridge *br;
247 int t;
248
249 br = p->br;
250 if (br_is_designated_port(p))
251 return 1;
252
253 if (memcmp(&p->designated_root, &br->designated_root, 8))
254 return 1;
255
256 if (br->root_path_cost < p->designated_cost)
257 return 1;
258 else if (br->root_path_cost > p->designated_cost)
259 return 0;
260
261 t = memcmp(&br->bridge_id, &p->designated_bridge, 8);
262 if (t < 0)
263 return 1;
264 else if (t > 0)
265 return 0;
266
267 if (p->port_id < p->designated_port)
268 return 1;
269
270 return 0;
271}
272
273/* called under bridge lock */
274static void br_designated_port_selection(struct net_bridge *br)
275{
276 struct net_bridge_port *p;
277
278 list_for_each_entry(p, &br->port_list, list) {
279 if (p->state != BR_STATE_DISABLED &&
280 br_should_become_designated_port(p))
281 br_become_designated_port(p);
282
283 }
284}
285
286/* called under bridge lock */
stephen hemminger160d73b2011-07-22 07:47:10 +0000287static int br_supersedes_port_info(const struct net_bridge_port *p,
288 const struct br_config_bpdu *bpdu)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700289{
290 int t;
291
292 t = memcmp(&bpdu->root, &p->designated_root, 8);
293 if (t < 0)
294 return 1;
295 else if (t > 0)
296 return 0;
297
298 if (bpdu->root_path_cost < p->designated_cost)
299 return 1;
300 else if (bpdu->root_path_cost > p->designated_cost)
301 return 0;
302
303 t = memcmp(&bpdu->bridge_id, &p->designated_bridge, 8);
304 if (t < 0)
305 return 1;
306 else if (t > 0)
307 return 0;
308
309 if (memcmp(&bpdu->bridge_id, &p->br->bridge_id, 8))
310 return 1;
311
312 if (bpdu->port_id <= p->designated_port)
313 return 1;
314
315 return 0;
316}
317
318/* called under bridge lock */
stephen hemminger160d73b2011-07-22 07:47:10 +0000319static void br_topology_change_acknowledged(struct net_bridge *br)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700320{
321 br->topology_change_detected = 0;
322 del_timer(&br->tcn_timer);
323}
324
325/* called under bridge lock */
326void br_topology_change_detection(struct net_bridge *br)
327{
328 int isroot = br_is_root_bridge(br);
329
Stephen Hemminger4f0611a2009-05-15 06:11:58 +0000330 if (br->stp_enabled != BR_KERNEL_STP)
331 return;
332
stephen hemminger28a16c92010-05-10 09:31:09 +0000333 br_info(br, "topology change detected, %s\n",
Linus Torvalds1da177e2005-04-16 15:20:36 -0700334 isroot ? "propagating" : "sending tcn bpdu");
335
336 if (isroot) {
337 br->topology_change = 1;
338 mod_timer(&br->topology_change_timer, jiffies
339 + br->bridge_forward_delay + br->bridge_max_age);
340 } else if (!br->topology_change_detected) {
341 br_transmit_tcn(br);
342 mod_timer(&br->tcn_timer, jiffies + br->bridge_hello_time);
343 }
344
345 br->topology_change_detected = 1;
346}
347
348/* called under bridge lock */
349void br_config_bpdu_generation(struct net_bridge *br)
350{
351 struct net_bridge_port *p;
352
353 list_for_each_entry(p, &br->port_list, list) {
354 if (p->state != BR_STATE_DISABLED &&
355 br_is_designated_port(p))
356 br_transmit_config(p);
357 }
358}
359
360/* called under bridge lock */
stephen hemminger160d73b2011-07-22 07:47:10 +0000361static void br_reply(struct net_bridge_port *p)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700362{
363 br_transmit_config(p);
364}
365
366/* called under bridge lock */
367void br_configuration_update(struct net_bridge *br)
368{
369 br_root_selection(br);
370 br_designated_port_selection(br);
371}
372
373/* called under bridge lock */
374void br_become_designated_port(struct net_bridge_port *p)
375{
376 struct net_bridge *br;
377
378 br = p->br;
379 p->designated_root = br->designated_root;
380 p->designated_cost = br->root_path_cost;
381 p->designated_bridge = br->bridge_id;
382 p->designated_port = p->port_id;
383}
384
385
386/* called under bridge lock */
387static void br_make_blocking(struct net_bridge_port *p)
388{
389 if (p->state != BR_STATE_DISABLED &&
390 p->state != BR_STATE_BLOCKING) {
391 if (p->state == BR_STATE_FORWARDING ||
392 p->state == BR_STATE_LEARNING)
393 br_topology_change_detection(p->br);
394
Florian Fainelli775dd692014-09-30 16:13:19 -0700395 br_set_state(p, BR_STATE_BLOCKING);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700396 br_log_state(p);
stephen hemminger4ecb9612011-07-22 07:47:09 +0000397 br_ifinfo_notify(RTM_NEWLINK, p);
398
Linus Torvalds1da177e2005-04-16 15:20:36 -0700399 del_timer(&p->forward_delay_timer);
400 }
401}
402
403/* called under bridge lock */
404static void br_make_forwarding(struct net_bridge_port *p)
405{
Stephen Hemmingeref647f12008-08-05 18:42:51 -0700406 struct net_bridge *br = p->br;
Stephen Hemminger9cde0702007-03-21 14:22:44 -0700407
Stephen Hemmingeref647f12008-08-05 18:42:51 -0700408 if (p->state != BR_STATE_BLOCKING)
409 return;
410
stephen hemmingera461c022011-03-10 05:57:04 +0000411 if (br->stp_enabled == BR_NO_STP || br->forward_delay == 0) {
Florian Fainelli775dd692014-09-30 16:13:19 -0700412 br_set_state(p, BR_STATE_FORWARDING);
Stephen Hemmingeref647f12008-08-05 18:42:51 -0700413 br_topology_change_detection(br);
414 del_timer(&p->forward_delay_timer);
stephen hemminger160d73b2011-07-22 07:47:10 +0000415 } else if (br->stp_enabled == BR_KERNEL_STP)
Florian Fainelli775dd692014-09-30 16:13:19 -0700416 br_set_state(p, BR_STATE_LISTENING);
Stephen Hemmingeref647f12008-08-05 18:42:51 -0700417 else
Florian Fainelli775dd692014-09-30 16:13:19 -0700418 br_set_state(p, BR_STATE_LEARNING);
Stephen Hemmingeref647f12008-08-05 18:42:51 -0700419
Herbert Xu3fe2d7c2010-02-28 00:49:38 -0800420 br_multicast_enable_port(p);
Stephen Hemmingeref647f12008-08-05 18:42:51 -0700421 br_log_state(p);
stephen hemminger4ecb9612011-07-22 07:47:09 +0000422 br_ifinfo_notify(RTM_NEWLINK, p);
Stephen Hemmingeref647f12008-08-05 18:42:51 -0700423
424 if (br->forward_delay != 0)
425 mod_timer(&p->forward_delay_timer, jiffies + br->forward_delay);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700426}
427
428/* called under bridge lock */
429void br_port_state_selection(struct net_bridge *br)
430{
431 struct net_bridge_port *p;
stephen hemminger1faa4352011-03-07 08:34:06 +0000432 unsigned int liveports = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700433
434 list_for_each_entry(p, &br->port_list, list) {
stephen hemminger1faa4352011-03-07 08:34:06 +0000435 if (p->state == BR_STATE_DISABLED)
436 continue;
437
Vitalii Demianetsb03b6dd2011-11-25 00:16:37 +0000438 /* Don't change port states if userspace is handling STP */
439 if (br->stp_enabled != BR_USER_STP) {
440 if (p->port_no == br->root_port) {
441 p->config_pending = 0;
442 p->topology_change_ack = 0;
443 br_make_forwarding(p);
444 } else if (br_is_designated_port(p)) {
445 del_timer(&p->message_age_timer);
446 br_make_forwarding(p);
447 } else {
448 p->config_pending = 0;
449 p->topology_change_ack = 0;
450 br_make_blocking(p);
451 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700452 }
453
stephen hemminger1faa4352011-03-07 08:34:06 +0000454 if (p->state == BR_STATE_FORWARDING)
455 ++liveports;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700456 }
stephen hemminger1faa4352011-03-07 08:34:06 +0000457
458 if (liveports == 0)
459 netif_carrier_off(br->dev);
460 else
461 netif_carrier_on(br->dev);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700462}
463
464/* called under bridge lock */
stephen hemminger160d73b2011-07-22 07:47:10 +0000465static void br_topology_change_acknowledge(struct net_bridge_port *p)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700466{
467 p->topology_change_ack = 1;
468 br_transmit_config(p);
469}
470
471/* called under bridge lock */
stephen hemminger160d73b2011-07-22 07:47:10 +0000472void br_received_config_bpdu(struct net_bridge_port *p,
473 const struct br_config_bpdu *bpdu)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700474{
475 struct net_bridge *br;
476 int was_root;
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +0900477
Linus Torvalds1da177e2005-04-16 15:20:36 -0700478 br = p->br;
479 was_root = br_is_root_bridge(br);
480
481 if (br_supersedes_port_info(p, bpdu)) {
482 br_record_config_information(p, bpdu);
483 br_configuration_update(br);
484 br_port_state_selection(br);
485
486 if (!br_is_root_bridge(br) && was_root) {
487 del_timer(&br->hello_timer);
488 if (br->topology_change_detected) {
489 del_timer(&br->topology_change_timer);
490 br_transmit_tcn(br);
491
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +0900492 mod_timer(&br->tcn_timer,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700493 jiffies + br->bridge_hello_time);
494 }
495 }
496
497 if (p->port_no == br->root_port) {
498 br_record_config_timeout_values(br, bpdu);
499 br_config_bpdu_generation(br);
500 if (bpdu->topology_change_ack)
501 br_topology_change_acknowledged(br);
502 }
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +0900503 } else if (br_is_designated_port(p)) {
504 br_reply(p);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700505 }
506}
507
508/* called under bridge lock */
509void br_received_tcn_bpdu(struct net_bridge_port *p)
510{
511 if (br_is_designated_port(p)) {
stephen hemminger28a16c92010-05-10 09:31:09 +0000512 br_info(p->br, "port %u(%s) received tcn bpdu\n",
Eric Dumazet95c96172012-04-15 05:58:06 +0000513 (unsigned int) p->port_no, p->dev->name);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700514
515 br_topology_change_detection(p->br);
516 br_topology_change_acknowledge(p);
517 }
518}
stephen hemminger14f98f22011-04-04 14:03:33 +0000519
520/* Change bridge STP parameter */
521int br_set_hello_time(struct net_bridge *br, unsigned long val)
522{
523 unsigned long t = clock_t_to_jiffies(val);
524
525 if (t < BR_MIN_HELLO_TIME || t > BR_MAX_HELLO_TIME)
526 return -ERANGE;
527
528 spin_lock_bh(&br->lock);
529 br->bridge_hello_time = t;
530 if (br_is_root_bridge(br))
531 br->hello_time = br->bridge_hello_time;
532 spin_unlock_bh(&br->lock);
533 return 0;
534}
535
536int br_set_max_age(struct net_bridge *br, unsigned long val)
537{
538 unsigned long t = clock_t_to_jiffies(val);
539
540 if (t < BR_MIN_MAX_AGE || t > BR_MAX_MAX_AGE)
541 return -ERANGE;
542
543 spin_lock_bh(&br->lock);
544 br->bridge_max_age = t;
545 if (br_is_root_bridge(br))
546 br->max_age = br->bridge_max_age;
547 spin_unlock_bh(&br->lock);
548 return 0;
549
550}
551
Herbert Xube4f1542013-09-12 17:12:05 +1000552void __br_set_forward_delay(struct net_bridge *br, unsigned long t)
stephen hemminger14f98f22011-04-04 14:03:33 +0000553{
stephen hemminger14f98f22011-04-04 14:03:33 +0000554 br->bridge_forward_delay = t;
555 if (br_is_root_bridge(br))
556 br->forward_delay = br->bridge_forward_delay;
Herbert Xube4f1542013-09-12 17:12:05 +1000557}
558
559int br_set_forward_delay(struct net_bridge *br, unsigned long val)
560{
561 unsigned long t = clock_t_to_jiffies(val);
562 int err = -ERANGE;
563
564 spin_lock_bh(&br->lock);
565 if (br->stp_enabled != BR_NO_STP &&
566 (t < BR_MIN_FORWARD_DELAY || t > BR_MAX_FORWARD_DELAY))
567 goto unlock;
568
569 __br_set_forward_delay(br, t);
570 err = 0;
571
572unlock:
stephen hemminger14f98f22011-04-04 14:03:33 +0000573 spin_unlock_bh(&br->lock);
Herbert Xube4f1542013-09-12 17:12:05 +1000574 return err;
stephen hemminger14f98f22011-04-04 14:03:33 +0000575}