57186d84d2bd6497366d7d4d7cca7a694e0b5818
[linux-2.6.git] / net / bridge / br_stp.c
1 /*
2  *      Spanning tree protocol; generic parts
3  *      Linux ethernet bridge
4  *
5  *      Authors:
6  *      Lennert Buytenhek               <buytenh@gnu.org>
7  *
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.
12  */
13 #include <linux/kernel.h>
14 #include <linux/rculist.h>
15
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
24 static const char *const 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",
30 };
31
32 void br_log_state(const struct net_bridge_port *p)
33 {
34         br_info(p->br, "port %u(%s) entering %s state\n",
35                 (unsigned) p->port_no, p->dev->name,
36                 br_port_state_names[p->state]);
37 }
38
39 /* called under bridge lock */
40 struct 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 */
53 static int br_should_become_root_port(const struct net_bridge_port *p,
54                                       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 */
104 static 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 */
128 void 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 */
143 void 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;
179                 mod_timer(&p->hold_timer,
180                           round_jiffies(jiffies + BR_HOLD_TIME));
181         }
182 }
183
184 /* called under bridge lock */
185 static inline void br_record_config_information(struct net_bridge_port *p,
186                                                 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
193         mod_timer(&p->message_age_timer, jiffies
194                   + (p->br->max_age - bpdu->message_age));
195 }
196
197 /* called under bridge lock */
198 static inline void br_record_config_timeout_values(struct net_bridge *br,
199                                             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 */
208 void 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 */
214 static 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 */
244 static 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 */
257 static 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 */
288 static 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 */
295 void br_topology_change_detection(struct net_bridge *br)
296 {
297         int isroot = br_is_root_bridge(br);
298
299         if (br->stp_enabled != BR_KERNEL_STP)
300                 return;
301
302         br_info(br, "topology change detected, %s\n",
303                 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 */
318 void 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 */
330 static inline void br_reply(struct net_bridge_port *p)
331 {
332         br_transmit_config(p);
333 }
334
335 /* called under bridge lock */
336 void 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 */
343 void 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 */
356 static 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 */
371 static void br_make_forwarding(struct net_bridge_port *p)
372 {
373         struct net_bridge *br = p->br;
374
375         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
388         br_multicast_enable_port(p);
389
390         br_log_state(p);
391
392         if (br->forward_delay != 0)
393                 mod_timer(&p->forward_delay_timer, jiffies + br->forward_delay);
394 }
395
396 /* called under bridge lock */
397 void br_port_state_selection(struct net_bridge *br)
398 {
399         struct net_bridge_port *p;
400
401         /* Don't change port states if userspace is handling STP */
402         if (br->stp_enabled == BR_USER_STP)
403                 return;
404
405         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 */
425 static 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 */
432 void br_received_config_bpdu(struct net_bridge_port *p, struct br_config_bpdu *bpdu)
433 {
434         struct net_bridge *br;
435         int was_root;
436
437         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
451                                 mod_timer(&br->tcn_timer,
452                                           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                 }
462         } else if (br_is_designated_port(p)) {
463                 br_reply(p);
464         }
465 }
466
467 /* called under bridge lock */
468 void br_received_tcn_bpdu(struct net_bridge_port *p)
469 {
470         if (br_is_designated_port(p)) {
471                 br_info(p->br, "port %u(%s) received tcn bpdu\n",
472                         (unsigned) p->port_no, p->dev->name);
473
474                 br_topology_change_detection(p->br);
475                 br_topology_change_acknowledge(p);
476         }
477 }