Root/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
24static 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
32void 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 */
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 */
53static 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 */
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;
179        mod_timer(&p->hold_timer,
180              round_jiffies(jiffies + BR_HOLD_TIME));
181    }
182}
183
184/* called under bridge lock */
185static 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 */
198static 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 */
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
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 */
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{
373    struct net_bridge *br = p->br;
374
375    if (p->state != BR_STATE_BLOCKING)
376        return;
377
378    if (br->stp_enabled == BR_NO_STP || 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 (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 */
397void br_port_state_selection(struct net_bridge *br)
398{
399    struct net_bridge_port *p;
400    unsigned int liveports = 0;
401
402    /* Don't change port states if userspace is handling STP */
403    if (br->stp_enabled == BR_USER_STP)
404        return;
405
406    list_for_each_entry(p, &br->port_list, list) {
407        if (p->state == BR_STATE_DISABLED)
408            continue;
409
410        if (p->port_no == br->root_port) {
411            p->config_pending = 0;
412            p->topology_change_ack = 0;
413            br_make_forwarding(p);
414        } else if (br_is_designated_port(p)) {
415            del_timer(&p->message_age_timer);
416            br_make_forwarding(p);
417        } else {
418            p->config_pending = 0;
419            p->topology_change_ack = 0;
420            br_make_blocking(p);
421        }
422
423        if (p->state == BR_STATE_FORWARDING)
424            ++liveports;
425    }
426
427    if (liveports == 0)
428        netif_carrier_off(br->dev);
429    else
430        netif_carrier_on(br->dev);
431}
432
433/* called under bridge lock */
434static inline void br_topology_change_acknowledge(struct net_bridge_port *p)
435{
436    p->topology_change_ack = 1;
437    br_transmit_config(p);
438}
439
440/* called under bridge lock */
441void br_received_config_bpdu(struct net_bridge_port *p, struct br_config_bpdu *bpdu)
442{
443    struct net_bridge *br;
444    int was_root;
445
446    br = p->br;
447    was_root = br_is_root_bridge(br);
448
449    if (br_supersedes_port_info(p, bpdu)) {
450        br_record_config_information(p, bpdu);
451        br_configuration_update(br);
452        br_port_state_selection(br);
453
454        if (!br_is_root_bridge(br) && was_root) {
455            del_timer(&br->hello_timer);
456            if (br->topology_change_detected) {
457                del_timer(&br->topology_change_timer);
458                br_transmit_tcn(br);
459
460                mod_timer(&br->tcn_timer,
461                      jiffies + br->bridge_hello_time);
462            }
463        }
464
465        if (p->port_no == br->root_port) {
466            br_record_config_timeout_values(br, bpdu);
467            br_config_bpdu_generation(br);
468            if (bpdu->topology_change_ack)
469                br_topology_change_acknowledged(br);
470        }
471    } else if (br_is_designated_port(p)) {
472        br_reply(p);
473    }
474}
475
476/* called under bridge lock */
477void br_received_tcn_bpdu(struct net_bridge_port *p)
478{
479    if (br_is_designated_port(p)) {
480        br_info(p->br, "port %u(%s) received tcn bpdu\n",
481            (unsigned) p->port_no, p->dev->name);
482
483        br_topology_change_detection(p->br);
484        br_topology_change_acknowledge(p);
485    }
486}
487

Archive Download this file

Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master

Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9



interactive