Merge branch 'x86/mm' into core/percpu
[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         pr_info("%s: topology change detected, %s\n", br->dev->name,
301                 isroot ? "propagating" : "sending tcn bpdu");
302
303         if (isroot) {
304                 br->topology_change = 1;
305                 mod_timer(&br->topology_change_timer, jiffies
306                           + br->bridge_forward_delay + br->bridge_max_age);
307         } else if (!br->topology_change_detected) {
308                 br_transmit_tcn(br);
309                 mod_timer(&br->tcn_timer, jiffies + br->bridge_hello_time);
310         }
311
312         br->topology_change_detected = 1;
313 }
314
315 /* called under bridge lock */
316 void br_config_bpdu_generation(struct net_bridge *br)
317 {
318         struct net_bridge_port *p;
319
320         list_for_each_entry(p, &br->port_list, list) {
321                 if (p->state != BR_STATE_DISABLED &&
322                     br_is_designated_port(p))
323                         br_transmit_config(p);
324         }
325 }
326
327 /* called under bridge lock */
328 static inline void br_reply(struct net_bridge_port *p)
329 {
330         br_transmit_config(p);
331 }
332
333 /* called under bridge lock */
334 void br_configuration_update(struct net_bridge *br)
335 {
336         br_root_selection(br);
337         br_designated_port_selection(br);
338 }
339
340 /* called under bridge lock */
341 void br_become_designated_port(struct net_bridge_port *p)
342 {
343         struct net_bridge *br;
344
345         br = p->br;
346         p->designated_root = br->designated_root;
347         p->designated_cost = br->root_path_cost;
348         p->designated_bridge = br->bridge_id;
349         p->designated_port = p->port_id;
350 }
351
352
353 /* called under bridge lock */
354 static void br_make_blocking(struct net_bridge_port *p)
355 {
356         if (p->state != BR_STATE_DISABLED &&
357             p->state != BR_STATE_BLOCKING) {
358                 if (p->state == BR_STATE_FORWARDING ||
359                     p->state == BR_STATE_LEARNING)
360                         br_topology_change_detection(p->br);
361
362                 p->state = BR_STATE_BLOCKING;
363                 br_log_state(p);
364                 del_timer(&p->forward_delay_timer);
365         }
366 }
367
368 /* called under bridge lock */
369 static void br_make_forwarding(struct net_bridge_port *p)
370 {
371         struct net_bridge *br = p->br;
372
373         if (p->state != BR_STATE_BLOCKING)
374                 return;
375
376         if (br->forward_delay == 0) {
377                 p->state = BR_STATE_FORWARDING;
378                 br_topology_change_detection(br);
379                 del_timer(&p->forward_delay_timer);
380         }
381         else if (p->br->stp_enabled == BR_KERNEL_STP)
382                 p->state = BR_STATE_LISTENING;
383         else
384                 p->state = BR_STATE_LEARNING;
385
386         br_log_state(p);
387
388         if (br->forward_delay != 0)
389                 mod_timer(&p->forward_delay_timer, jiffies + br->forward_delay);
390 }
391
392 /* called under bridge lock */
393 void br_port_state_selection(struct net_bridge *br)
394 {
395         struct net_bridge_port *p;
396
397         /* Don't change port states if userspace is handling STP */
398         if (br->stp_enabled == BR_USER_STP)
399                 return;
400
401         list_for_each_entry(p, &br->port_list, list) {
402                 if (p->state != BR_STATE_DISABLED) {
403                         if (p->port_no == br->root_port) {
404                                 p->config_pending = 0;
405                                 p->topology_change_ack = 0;
406                                 br_make_forwarding(p);
407                         } else if (br_is_designated_port(p)) {
408                                 del_timer(&p->message_age_timer);
409                                 br_make_forwarding(p);
410                         } else {
411                                 p->config_pending = 0;
412                                 p->topology_change_ack = 0;
413                                 br_make_blocking(p);
414                         }
415                 }
416
417         }
418 }
419
420 /* called under bridge lock */
421 static inline void br_topology_change_acknowledge(struct net_bridge_port *p)
422 {
423         p->topology_change_ack = 1;
424         br_transmit_config(p);
425 }
426
427 /* called under bridge lock */
428 void br_received_config_bpdu(struct net_bridge_port *p, struct br_config_bpdu *bpdu)
429 {
430         struct net_bridge *br;
431         int was_root;
432
433         br = p->br;
434         was_root = br_is_root_bridge(br);
435
436         if (br_supersedes_port_info(p, bpdu)) {
437                 br_record_config_information(p, bpdu);
438                 br_configuration_update(br);
439                 br_port_state_selection(br);
440
441                 if (!br_is_root_bridge(br) && was_root) {
442                         del_timer(&br->hello_timer);
443                         if (br->topology_change_detected) {
444                                 del_timer(&br->topology_change_timer);
445                                 br_transmit_tcn(br);
446
447                                 mod_timer(&br->tcn_timer,
448                                           jiffies + br->bridge_hello_time);
449                         }
450                 }
451
452                 if (p->port_no == br->root_port) {
453                         br_record_config_timeout_values(br, bpdu);
454                         br_config_bpdu_generation(br);
455                         if (bpdu->topology_change_ack)
456                                 br_topology_change_acknowledged(br);
457                 }
458         } else if (br_is_designated_port(p)) {
459                 br_reply(p);
460         }
461 }
462
463 /* called under bridge lock */
464 void br_received_tcn_bpdu(struct net_bridge_port *p)
465 {
466         if (br_is_designated_port(p)) {
467                 pr_info("%s: received tcn bpdu on port %i(%s)\n",
468                        p->br->dev->name, p->port_no, p->dev->name);
469
470                 br_topology_change_detection(p->br);
471                 br_topology_change_acknowledge(p);
472         }
473 }