Merge branch 'topic/misc' into for-linus
[linux-2.6] / 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 *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         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]);
37
38 }
39
40 /* called under bridge lock */
41 struct net_bridge_port *br_get_port(struct net_bridge *br, u16 port_no)
42 {
43         struct net_bridge_port *p;
44
45         list_for_each_entry_rcu(p, &br->port_list, list) {
46                 if (p->port_no == port_no)
47                         return p;
48         }
49
50         return NULL;
51 }
52
53 /* called under bridge lock */
54 static int br_should_become_root_port(const struct net_bridge_port *p,
55                                       u16 root_port)
56 {
57         struct net_bridge *br;
58         struct net_bridge_port *rp;
59         int t;
60
61         br = p->br;
62         if (p->state == BR_STATE_DISABLED ||
63             br_is_designated_port(p))
64                 return 0;
65
66         if (memcmp(&br->bridge_id, &p->designated_root, 8) <= 0)
67                 return 0;
68
69         if (!root_port)
70                 return 1;
71
72         rp = br_get_port(br, root_port);
73
74         t = memcmp(&p->designated_root, &rp->designated_root, 8);
75         if (t < 0)
76                 return 1;
77         else if (t > 0)
78                 return 0;
79
80         if (p->designated_cost + p->path_cost <
81             rp->designated_cost + rp->path_cost)
82                 return 1;
83         else if (p->designated_cost + p->path_cost >
84                  rp->designated_cost + rp->path_cost)
85                 return 0;
86
87         t = memcmp(&p->designated_bridge, &rp->designated_bridge, 8);
88         if (t < 0)
89                 return 1;
90         else if (t > 0)
91                 return 0;
92
93         if (p->designated_port < rp->designated_port)
94                 return 1;
95         else if (p->designated_port > rp->designated_port)
96                 return 0;
97
98         if (p->port_id < rp->port_id)
99                 return 1;
100
101         return 0;
102 }
103
104 /* called under bridge lock */
105 static void br_root_selection(struct net_bridge *br)
106 {
107         struct net_bridge_port *p;
108         u16 root_port = 0;
109
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;
113
114         }
115
116         br->root_port = root_port;
117
118         if (!root_port) {
119                 br->designated_root = br->bridge_id;
120                 br->root_path_cost = 0;
121         } else {
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;
125         }
126 }
127
128 /* called under bridge lock */
129 void br_become_root_bridge(struct net_bridge *br)
130 {
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);
136
137         if (br->dev->flags & IFF_UP) {
138                 br_config_bpdu_generation(br);
139                 mod_timer(&br->hello_timer, jiffies + br->hello_time);
140         }
141 }
142
143 /* called under bridge lock */
144 void br_transmit_config(struct net_bridge_port *p)
145 {
146         struct br_config_bpdu bpdu;
147         struct net_bridge *br;
148
149
150         if (timer_pending(&p->hold_timer)) {
151                 p->config_pending = 1;
152                 return;
153         }
154
155         br = p->br;
156
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;
165         else {
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)
170                         + MESSAGE_AGE_INCR;
171         }
172         bpdu.max_age = br->max_age;
173         bpdu.hello_time = br->hello_time;
174         bpdu.forward_delay = br->forward_delay;
175
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));
182         }
183 }
184
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)
188 {
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;
193
194         mod_timer(&p->message_age_timer, jiffies
195                   + (p->br->max_age - bpdu->message_age));
196 }
197
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)
201 {
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;
206 }
207
208 /* called under bridge lock */
209 void br_transmit_tcn(struct net_bridge *br)
210 {
211         br_send_tcn_bpdu(br_get_port(br, br->root_port));
212 }
213
214 /* called under bridge lock */
215 static int br_should_become_designated_port(const struct net_bridge_port *p)
216 {
217         struct net_bridge *br;
218         int t;
219
220         br = p->br;
221         if (br_is_designated_port(p))
222                 return 1;
223
224         if (memcmp(&p->designated_root, &br->designated_root, 8))
225                 return 1;
226
227         if (br->root_path_cost < p->designated_cost)
228                 return 1;
229         else if (br->root_path_cost > p->designated_cost)
230                 return 0;
231
232         t = memcmp(&br->bridge_id, &p->designated_bridge, 8);
233         if (t < 0)
234                 return 1;
235         else if (t > 0)
236                 return 0;
237
238         if (p->port_id < p->designated_port)
239                 return 1;
240
241         return 0;
242 }
243
244 /* called under bridge lock */
245 static void br_designated_port_selection(struct net_bridge *br)
246 {
247         struct net_bridge_port *p;
248
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);
253
254         }
255 }
256
257 /* called under bridge lock */
258 static int br_supersedes_port_info(struct net_bridge_port *p, struct br_config_bpdu *bpdu)
259 {
260         int t;
261
262         t = memcmp(&bpdu->root, &p->designated_root, 8);
263         if (t < 0)
264                 return 1;
265         else if (t > 0)
266                 return 0;
267
268         if (bpdu->root_path_cost < p->designated_cost)
269                 return 1;
270         else if (bpdu->root_path_cost > p->designated_cost)
271                 return 0;
272
273         t = memcmp(&bpdu->bridge_id, &p->designated_bridge, 8);
274         if (t < 0)
275                 return 1;
276         else if (t > 0)
277                 return 0;
278
279         if (memcmp(&bpdu->bridge_id, &p->br->bridge_id, 8))
280                 return 1;
281
282         if (bpdu->port_id <= p->designated_port)
283                 return 1;
284
285         return 0;
286 }
287
288 /* called under bridge lock */
289 static inline void br_topology_change_acknowledged(struct net_bridge *br)
290 {
291         br->topology_change_detected = 0;
292         del_timer(&br->tcn_timer);
293 }
294
295 /* called under bridge lock */
296 void br_topology_change_detection(struct net_bridge *br)
297 {
298         int isroot = br_is_root_bridge(br);
299
300         if (br->stp_enabled != BR_KERNEL_STP)
301                 return;
302
303         pr_info("%s: topology change detected, %s\n", br->dev->name,
304                 isroot ? "propagating" : "sending tcn bpdu");
305
306         if (isroot) {
307                 br->topology_change = 1;
308                 mod_timer(&br->topology_change_timer, jiffies
309                           + br->bridge_forward_delay + br->bridge_max_age);
310         } else if (!br->topology_change_detected) {
311                 br_transmit_tcn(br);
312                 mod_timer(&br->tcn_timer, jiffies + br->bridge_hello_time);
313         }
314
315         br->topology_change_detected = 1;
316 }
317
318 /* called under bridge lock */
319 void br_config_bpdu_generation(struct net_bridge *br)
320 {
321         struct net_bridge_port *p;
322
323         list_for_each_entry(p, &br->port_list, list) {
324                 if (p->state != BR_STATE_DISABLED &&
325                     br_is_designated_port(p))
326                         br_transmit_config(p);
327         }
328 }
329
330 /* called under bridge lock */
331 static inline void br_reply(struct net_bridge_port *p)
332 {
333         br_transmit_config(p);
334 }
335
336 /* called under bridge lock */
337 void br_configuration_update(struct net_bridge *br)
338 {
339         br_root_selection(br);
340         br_designated_port_selection(br);
341 }
342
343 /* called under bridge lock */
344 void br_become_designated_port(struct net_bridge_port *p)
345 {
346         struct net_bridge *br;
347
348         br = p->br;
349         p->designated_root = br->designated_root;
350         p->designated_cost = br->root_path_cost;
351         p->designated_bridge = br->bridge_id;
352         p->designated_port = p->port_id;
353 }
354
355
356 /* called under bridge lock */
357 static void br_make_blocking(struct net_bridge_port *p)
358 {
359         if (p->state != BR_STATE_DISABLED &&
360             p->state != BR_STATE_BLOCKING) {
361                 if (p->state == BR_STATE_FORWARDING ||
362                     p->state == BR_STATE_LEARNING)
363                         br_topology_change_detection(p->br);
364
365                 p->state = BR_STATE_BLOCKING;
366                 br_log_state(p);
367                 del_timer(&p->forward_delay_timer);
368         }
369 }
370
371 /* called under bridge lock */
372 static void br_make_forwarding(struct net_bridge_port *p)
373 {
374         struct net_bridge *br = p->br;
375
376         if (p->state != BR_STATE_BLOCKING)
377                 return;
378
379         if (br->forward_delay == 0) {
380                 p->state = BR_STATE_FORWARDING;
381                 br_topology_change_detection(br);
382                 del_timer(&p->forward_delay_timer);
383         }
384         else if (p->br->stp_enabled == BR_KERNEL_STP)
385                 p->state = BR_STATE_LISTENING;
386         else
387                 p->state = BR_STATE_LEARNING;
388
389         br_log_state(p);
390
391         if (br->forward_delay != 0)
392                 mod_timer(&p->forward_delay_timer, jiffies + br->forward_delay);
393 }
394
395 /* called under bridge lock */
396 void br_port_state_selection(struct net_bridge *br)
397 {
398         struct net_bridge_port *p;
399
400         /* Don't change port states if userspace is handling STP */
401         if (br->stp_enabled == BR_USER_STP)
402                 return;
403
404         list_for_each_entry(p, &br->port_list, list) {
405                 if (p->state != BR_STATE_DISABLED) {
406                         if (p->port_no == br->root_port) {
407                                 p->config_pending = 0;
408                                 p->topology_change_ack = 0;
409                                 br_make_forwarding(p);
410                         } else if (br_is_designated_port(p)) {
411                                 del_timer(&p->message_age_timer);
412                                 br_make_forwarding(p);
413                         } else {
414                                 p->config_pending = 0;
415                                 p->topology_change_ack = 0;
416                                 br_make_blocking(p);
417                         }
418                 }
419
420         }
421 }
422
423 /* called under bridge lock */
424 static inline void br_topology_change_acknowledge(struct net_bridge_port *p)
425 {
426         p->topology_change_ack = 1;
427         br_transmit_config(p);
428 }
429
430 /* called under bridge lock */
431 void br_received_config_bpdu(struct net_bridge_port *p, struct br_config_bpdu *bpdu)
432 {
433         struct net_bridge *br;
434         int was_root;
435
436         br = p->br;
437         was_root = br_is_root_bridge(br);
438
439         if (br_supersedes_port_info(p, bpdu)) {
440                 br_record_config_information(p, bpdu);
441                 br_configuration_update(br);
442                 br_port_state_selection(br);
443
444                 if (!br_is_root_bridge(br) && was_root) {
445                         del_timer(&br->hello_timer);
446                         if (br->topology_change_detected) {
447                                 del_timer(&br->topology_change_timer);
448                                 br_transmit_tcn(br);
449
450                                 mod_timer(&br->tcn_timer,
451                                           jiffies + br->bridge_hello_time);
452                         }
453                 }
454
455                 if (p->port_no == br->root_port) {
456                         br_record_config_timeout_values(br, bpdu);
457                         br_config_bpdu_generation(br);
458                         if (bpdu->topology_change_ack)
459                                 br_topology_change_acknowledged(br);
460                 }
461         } else if (br_is_designated_port(p)) {
462                 br_reply(p);
463         }
464 }
465
466 /* called under bridge lock */
467 void br_received_tcn_bpdu(struct net_bridge_port *p)
468 {
469         if (br_is_designated_port(p)) {
470                 pr_info("%s: received tcn bpdu on port %i(%s)\n",
471                        p->br->dev->name, p->port_no, p->dev->name);
472
473                 br_topology_change_detection(p->br);
474                 br_topology_change_acknowledge(p);
475         }
476 }