~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/net/bridge/br_stp.c

Version: ~ [ linux-5.12-rc1 ] ~ [ linux-5.11.2 ] ~ [ linux-5.10.19 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.101 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.177 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.222 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.258 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.258 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.18.140 ] ~ [ linux-3.16.85 ] ~ [ linux-3.14.79 ] ~ [ linux-3.12.74 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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 #include <net/switchdev.h>
 16 
 17 #include "br_private.h"
 18 #include "br_private_stp.h"
 19 
 20 /* since time values in bpdu are in jiffies and then scaled (1/256)
 21  * before sending, make sure that is at least one STP tick.
 22  */
 23 #define MESSAGE_AGE_INCR        ((HZ / 256) + 1)
 24 
 25 static const char *const br_port_state_names[] = {
 26         [BR_STATE_DISABLED] = "disabled",
 27         [BR_STATE_LISTENING] = "listening",
 28         [BR_STATE_LEARNING] = "learning",
 29         [BR_STATE_FORWARDING] = "forwarding",
 30         [BR_STATE_BLOCKING] = "blocking",
 31 };
 32 
 33 void br_set_state(struct net_bridge_port *p, unsigned int state)
 34 {
 35         struct switchdev_attr attr = {
 36                 .orig_dev = p->dev,
 37                 .id = SWITCHDEV_ATTR_ID_PORT_STP_STATE,
 38                 .flags = SWITCHDEV_F_DEFER,
 39                 .u.stp_state = state,
 40         };
 41         int err;
 42 
 43         p->state = state;
 44         err = switchdev_port_attr_set(p->dev, &attr);
 45         if (err && err != -EOPNOTSUPP)
 46                 br_warn(p->br, "error setting offload STP state on port %u(%s)\n",
 47                                 (unsigned int) p->port_no, p->dev->name);
 48         else
 49                 br_info(p->br, "port %u(%s) entered %s state\n",
 50                                 (unsigned int) p->port_no, p->dev->name,
 51                                 br_port_state_names[p->state]);
 52 }
 53 
 54 /* called under bridge lock */
 55 struct net_bridge_port *br_get_port(struct net_bridge *br, u16 port_no)
 56 {
 57         struct net_bridge_port *p;
 58 
 59         list_for_each_entry_rcu(p, &br->port_list, list) {
 60                 if (p->port_no == port_no)
 61                         return p;
 62         }
 63 
 64         return NULL;
 65 }
 66 
 67 /* called under bridge lock */
 68 static int br_should_become_root_port(const struct net_bridge_port *p,
 69                                       u16 root_port)
 70 {
 71         struct net_bridge *br;
 72         struct net_bridge_port *rp;
 73         int t;
 74 
 75         br = p->br;
 76         if (p->state == BR_STATE_DISABLED ||
 77             br_is_designated_port(p))
 78                 return 0;
 79 
 80         if (memcmp(&br->bridge_id, &p->designated_root, 8) <= 0)
 81                 return 0;
 82 
 83         if (!root_port)
 84                 return 1;
 85 
 86         rp = br_get_port(br, root_port);
 87 
 88         t = memcmp(&p->designated_root, &rp->designated_root, 8);
 89         if (t < 0)
 90                 return 1;
 91         else if (t > 0)
 92                 return 0;
 93 
 94         if (p->designated_cost + p->path_cost <
 95             rp->designated_cost + rp->path_cost)
 96                 return 1;
 97         else if (p->designated_cost + p->path_cost >
 98                  rp->designated_cost + rp->path_cost)
 99                 return 0;
100 
101         t = memcmp(&p->designated_bridge, &rp->designated_bridge, 8);
102         if (t < 0)
103                 return 1;
104         else if (t > 0)
105                 return 0;
106 
107         if (p->designated_port < rp->designated_port)
108                 return 1;
109         else if (p->designated_port > rp->designated_port)
110                 return 0;
111 
112         if (p->port_id < rp->port_id)
113                 return 1;
114 
115         return 0;
116 }
117 
118 static void br_root_port_block(const struct net_bridge *br,
119                                struct net_bridge_port *p)
120 {
121 
122         br_notice(br, "port %u(%s) tried to become root port (blocked)",
123                   (unsigned int) p->port_no, p->dev->name);
124 
125         br_set_state(p, BR_STATE_LISTENING);
126         br_ifinfo_notify(RTM_NEWLINK, NULL, p);
127 
128         if (br->forward_delay > 0)
129                 mod_timer(&p->forward_delay_timer, jiffies + br->forward_delay);
130 }
131 
132 /* called under bridge lock */
133 static void br_root_selection(struct net_bridge *br)
134 {
135         struct net_bridge_port *p;
136         u16 root_port = 0;
137 
138         list_for_each_entry(p, &br->port_list, list) {
139                 if (!br_should_become_root_port(p, root_port))
140                         continue;
141 
142                 if (p->flags & BR_ROOT_BLOCK)
143                         br_root_port_block(br, p);
144                 else
145                         root_port = p->port_no;
146         }
147 
148         br->root_port = root_port;
149 
150         if (!root_port) {
151                 br->designated_root = br->bridge_id;
152                 br->root_path_cost = 0;
153         } else {
154                 p = br_get_port(br, root_port);
155                 br->designated_root = p->designated_root;
156                 br->root_path_cost = p->designated_cost + p->path_cost;
157         }
158 }
159 
160 /* called under bridge lock */
161 void br_become_root_bridge(struct net_bridge *br)
162 {
163         br->max_age = br->bridge_max_age;
164         br->hello_time = br->bridge_hello_time;
165         br->forward_delay = br->bridge_forward_delay;
166         br_topology_change_detection(br);
167         del_timer(&br->tcn_timer);
168 
169         if (br->dev->flags & IFF_UP) {
170                 br_config_bpdu_generation(br);
171                 mod_timer(&br->hello_timer, jiffies + br->hello_time);
172         }
173 }
174 
175 /* called under bridge lock */
176 void br_transmit_config(struct net_bridge_port *p)
177 {
178         struct br_config_bpdu bpdu;
179         struct net_bridge *br;
180 
181         if (timer_pending(&p->hold_timer)) {
182                 p->config_pending = 1;
183                 return;
184         }
185 
186         br = p->br;
187 
188         bpdu.topology_change = br->topology_change;
189         bpdu.topology_change_ack = p->topology_change_ack;
190         bpdu.root = br->designated_root;
191         bpdu.root_path_cost = br->root_path_cost;
192         bpdu.bridge_id = br->bridge_id;
193         bpdu.port_id = p->port_id;
194         if (br_is_root_bridge(br))
195                 bpdu.message_age = 0;
196         else {
197                 struct net_bridge_port *root
198                         = br_get_port(br, br->root_port);
199                 bpdu.message_age = (jiffies - root->designated_age)
200                         + MESSAGE_AGE_INCR;
201         }
202         bpdu.max_age = br->max_age;
203         bpdu.hello_time = br->hello_time;
204         bpdu.forward_delay = br->forward_delay;
205 
206         if (bpdu.message_age < br->max_age) {
207                 br_send_config_bpdu(p, &bpdu);
208                 p->topology_change_ack = 0;
209                 p->config_pending = 0;
210                 if (p->br->stp_enabled == BR_KERNEL_STP)
211                         mod_timer(&p->hold_timer,
212                                   round_jiffies(jiffies + BR_HOLD_TIME));
213         }
214 }
215 
216 /* called under bridge lock */
217 static void br_record_config_information(struct net_bridge_port *p,
218                                          const struct br_config_bpdu *bpdu)
219 {
220         p->designated_root = bpdu->root;
221         p->designated_cost = bpdu->root_path_cost;
222         p->designated_bridge = bpdu->bridge_id;
223         p->designated_port = bpdu->port_id;
224         p->designated_age = jiffies - bpdu->message_age;
225 
226         mod_timer(&p->message_age_timer, jiffies
227                   + (bpdu->max_age - bpdu->message_age));
228 }
229 
230 /* called under bridge lock */
231 static void br_record_config_timeout_values(struct net_bridge *br,
232                                             const struct br_config_bpdu *bpdu)
233 {
234         br->max_age = bpdu->max_age;
235         br->hello_time = bpdu->hello_time;
236         br->forward_delay = bpdu->forward_delay;
237         __br_set_topology_change(br, bpdu->topology_change);
238 }
239 
240 /* called under bridge lock */
241 void br_transmit_tcn(struct net_bridge *br)
242 {
243         struct net_bridge_port *p;
244 
245         p = br_get_port(br, br->root_port);
246         if (p)
247                 br_send_tcn_bpdu(p);
248         else
249                 br_notice(br, "root port %u not found for topology notice\n",
250                           br->root_port);
251 }
252 
253 /* called under bridge lock */
254 static int br_should_become_designated_port(const struct net_bridge_port *p)
255 {
256         struct net_bridge *br;
257         int t;
258 
259         br = p->br;
260         if (br_is_designated_port(p))
261                 return 1;
262 
263         if (memcmp(&p->designated_root, &br->designated_root, 8))
264                 return 1;
265 
266         if (br->root_path_cost < p->designated_cost)
267                 return 1;
268         else if (br->root_path_cost > p->designated_cost)
269                 return 0;
270 
271         t = memcmp(&br->bridge_id, &p->designated_bridge, 8);
272         if (t < 0)
273                 return 1;
274         else if (t > 0)
275                 return 0;
276 
277         if (p->port_id < p->designated_port)
278                 return 1;
279 
280         return 0;
281 }
282 
283 /* called under bridge lock */
284 static void br_designated_port_selection(struct net_bridge *br)
285 {
286         struct net_bridge_port *p;
287 
288         list_for_each_entry(p, &br->port_list, list) {
289                 if (p->state != BR_STATE_DISABLED &&
290                     br_should_become_designated_port(p))
291                         br_become_designated_port(p);
292 
293         }
294 }
295 
296 /* called under bridge lock */
297 static int br_supersedes_port_info(const struct net_bridge_port *p,
298                                    const struct br_config_bpdu *bpdu)
299 {
300         int t;
301 
302         t = memcmp(&bpdu->root, &p->designated_root, 8);
303         if (t < 0)
304                 return 1;
305         else if (t > 0)
306                 return 0;
307 
308         if (bpdu->root_path_cost < p->designated_cost)
309                 return 1;
310         else if (bpdu->root_path_cost > p->designated_cost)
311                 return 0;
312 
313         t = memcmp(&bpdu->bridge_id, &p->designated_bridge, 8);
314         if (t < 0)
315                 return 1;
316         else if (t > 0)
317                 return 0;
318 
319         if (memcmp(&bpdu->bridge_id, &p->br->bridge_id, 8))
320                 return 1;
321 
322         if (bpdu->port_id <= p->designated_port)
323                 return 1;
324 
325         return 0;
326 }
327 
328 /* called under bridge lock */
329 static void br_topology_change_acknowledged(struct net_bridge *br)
330 {
331         br->topology_change_detected = 0;
332         del_timer(&br->tcn_timer);
333 }
334 
335 /* called under bridge lock */
336 void br_topology_change_detection(struct net_bridge *br)
337 {
338         int isroot = br_is_root_bridge(br);
339 
340         if (br->stp_enabled != BR_KERNEL_STP)
341                 return;
342 
343         br_info(br, "topology change detected, %s\n",
344                 isroot ? "propagating" : "sending tcn bpdu");
345 
346         if (isroot) {
347                 __br_set_topology_change(br, 1);
348                 mod_timer(&br->topology_change_timer, jiffies
349                           + br->bridge_forward_delay + br->bridge_max_age);
350         } else if (!br->topology_change_detected) {
351                 br_transmit_tcn(br);
352                 mod_timer(&br->tcn_timer, jiffies + br->bridge_hello_time);
353         }
354 
355         br->topology_change_detected = 1;
356 }
357 
358 /* called under bridge lock */
359 void br_config_bpdu_generation(struct net_bridge *br)
360 {
361         struct net_bridge_port *p;
362 
363         list_for_each_entry(p, &br->port_list, list) {
364                 if (p->state != BR_STATE_DISABLED &&
365                     br_is_designated_port(p))
366                         br_transmit_config(p);
367         }
368 }
369 
370 /* called under bridge lock */
371 static void br_reply(struct net_bridge_port *p)
372 {
373         br_transmit_config(p);
374 }
375 
376 /* called under bridge lock */
377 void br_configuration_update(struct net_bridge *br)
378 {
379         br_root_selection(br);
380         br_designated_port_selection(br);
381 }
382 
383 /* called under bridge lock */
384 void br_become_designated_port(struct net_bridge_port *p)
385 {
386         struct net_bridge *br;
387 
388         br = p->br;
389         p->designated_root = br->designated_root;
390         p->designated_cost = br->root_path_cost;
391         p->designated_bridge = br->bridge_id;
392         p->designated_port = p->port_id;
393 }
394 
395 
396 /* called under bridge lock */
397 static void br_make_blocking(struct net_bridge_port *p)
398 {
399         if (p->state != BR_STATE_DISABLED &&
400             p->state != BR_STATE_BLOCKING) {
401                 if (p->state == BR_STATE_FORWARDING ||
402                     p->state == BR_STATE_LEARNING)
403                         br_topology_change_detection(p->br);
404 
405                 br_set_state(p, BR_STATE_BLOCKING);
406                 br_ifinfo_notify(RTM_NEWLINK, NULL, p);
407 
408                 del_timer(&p->forward_delay_timer);
409         }
410 }
411 
412 /* called under bridge lock */
413 static void br_make_forwarding(struct net_bridge_port *p)
414 {
415         struct net_bridge *br = p->br;
416 
417         if (p->state != BR_STATE_BLOCKING)
418                 return;
419 
420         if (br->stp_enabled == BR_NO_STP || br->forward_delay == 0) {
421                 br_set_state(p, BR_STATE_FORWARDING);
422                 br_topology_change_detection(br);
423                 del_timer(&p->forward_delay_timer);
424         } else if (br->stp_enabled == BR_KERNEL_STP)
425                 br_set_state(p, BR_STATE_LISTENING);
426         else
427                 br_set_state(p, BR_STATE_LEARNING);
428 
429         br_ifinfo_notify(RTM_NEWLINK, NULL, p);
430 
431         if (br->forward_delay != 0)
432                 mod_timer(&p->forward_delay_timer, jiffies + br->forward_delay);
433 }
434 
435 /* called under bridge lock */
436 void br_port_state_selection(struct net_bridge *br)
437 {
438         struct net_bridge_port *p;
439         unsigned int liveports = 0;
440 
441         list_for_each_entry(p, &br->port_list, list) {
442                 if (p->state == BR_STATE_DISABLED)
443                         continue;
444 
445                 /* Don't change port states if userspace is handling STP */
446                 if (br->stp_enabled != BR_USER_STP) {
447                         if (p->port_no == br->root_port) {
448                                 p->config_pending = 0;
449                                 p->topology_change_ack = 0;
450                                 br_make_forwarding(p);
451                         } else if (br_is_designated_port(p)) {
452                                 del_timer(&p->message_age_timer);
453                                 br_make_forwarding(p);
454                         } else {
455                                 p->config_pending = 0;
456                                 p->topology_change_ack = 0;
457                                 br_make_blocking(p);
458                         }
459                 }
460 
461                 if (p->state != BR_STATE_BLOCKING)
462                         br_multicast_enable_port(p);
463                 /* Multicast is not disabled for the port when it goes in
464                  * blocking state because the timers will expire and stop by
465                  * themselves without sending more queries.
466                  */
467                 if (p->state == BR_STATE_FORWARDING)
468                         ++liveports;
469         }
470 
471         if (liveports == 0)
472                 netif_carrier_off(br->dev);
473         else
474                 netif_carrier_on(br->dev);
475 }
476 
477 /* called under bridge lock */
478 static void br_topology_change_acknowledge(struct net_bridge_port *p)
479 {
480         p->topology_change_ack = 1;
481         br_transmit_config(p);
482 }
483 
484 /* called under bridge lock */
485 void br_received_config_bpdu(struct net_bridge_port *p,
486                              const struct br_config_bpdu *bpdu)
487 {
488         struct net_bridge *br;
489         int was_root;
490 
491         br = p->br;
492         was_root = br_is_root_bridge(br);
493 
494         if (br_supersedes_port_info(p, bpdu)) {
495                 br_record_config_information(p, bpdu);
496                 br_configuration_update(br);
497                 br_port_state_selection(br);
498 
499                 if (!br_is_root_bridge(br) && was_root) {
500                         del_timer(&br->hello_timer);
501                         if (br->topology_change_detected) {
502                                 del_timer(&br->topology_change_timer);
503                                 br_transmit_tcn(br);
504 
505                                 mod_timer(&br->tcn_timer,
506                                           jiffies + br->bridge_hello_time);
507                         }
508                 }
509 
510                 if (p->port_no == br->root_port) {
511                         br_record_config_timeout_values(br, bpdu);
512                         br_config_bpdu_generation(br);
513                         if (bpdu->topology_change_ack)
514                                 br_topology_change_acknowledged(br);
515                 }
516         } else if (br_is_designated_port(p)) {
517                 br_reply(p);
518         }
519 }
520 
521 /* called under bridge lock */
522 void br_received_tcn_bpdu(struct net_bridge_port *p)
523 {
524         if (br_is_designated_port(p)) {
525                 br_info(p->br, "port %u(%s) received tcn bpdu\n",
526                         (unsigned int) p->port_no, p->dev->name);
527 
528                 br_topology_change_detection(p->br);
529                 br_topology_change_acknowledge(p);
530         }
531 }
532 
533 /* Change bridge STP parameter */
534 int br_set_hello_time(struct net_bridge *br, unsigned long val)
535 {
536         unsigned long t = clock_t_to_jiffies(val);
537 
538         if (t < BR_MIN_HELLO_TIME || t > BR_MAX_HELLO_TIME)
539                 return -ERANGE;
540 
541         spin_lock_bh(&br->lock);
542         br->bridge_hello_time = t;
543         if (br_is_root_bridge(br))
544                 br->hello_time = br->bridge_hello_time;
545         spin_unlock_bh(&br->lock);
546         return 0;
547 }
548 
549 int br_set_max_age(struct net_bridge *br, unsigned long val)
550 {
551         unsigned long t = clock_t_to_jiffies(val);
552 
553         if (t < BR_MIN_MAX_AGE || t > BR_MAX_MAX_AGE)
554                 return -ERANGE;
555 
556         spin_lock_bh(&br->lock);
557         br->bridge_max_age = t;
558         if (br_is_root_bridge(br))
559                 br->max_age = br->bridge_max_age;
560         spin_unlock_bh(&br->lock);
561         return 0;
562 
563 }
564 
565 /* called under bridge lock */
566 int __set_ageing_time(struct net_device *dev, unsigned long t)
567 {
568         struct switchdev_attr attr = {
569                 .orig_dev = dev,
570                 .id = SWITCHDEV_ATTR_ID_BRIDGE_AGEING_TIME,
571                 .flags = SWITCHDEV_F_SKIP_EOPNOTSUPP | SWITCHDEV_F_DEFER,
572                 .u.ageing_time = jiffies_to_clock_t(t),
573         };
574         int err;
575 
576         err = switchdev_port_attr_set(dev, &attr);
577         if (err && err != -EOPNOTSUPP)
578                 return err;
579 
580         return 0;
581 }
582 
583 /* Set time interval that dynamic forwarding entries live
584  * For pure software bridge, allow values outside the 802.1
585  * standard specification for special cases:
586  *  0 - entry never ages (all permanant)
587  *  1 - entry disappears (no persistance)
588  *
589  * Offloaded switch entries maybe more restrictive
590  */
591 int br_set_ageing_time(struct net_bridge *br, clock_t ageing_time)
592 {
593         unsigned long t = clock_t_to_jiffies(ageing_time);
594         int err;
595 
596         err = __set_ageing_time(br->dev, t);
597         if (err)
598                 return err;
599 
600         spin_lock_bh(&br->lock);
601         br->bridge_ageing_time = t;
602         br->ageing_time = t;
603         spin_unlock_bh(&br->lock);
604 
605         mod_delayed_work(system_long_wq, &br->gc_work, 0);
606 
607         return 0;
608 }
609 
610 /* called under bridge lock */
611 void __br_set_topology_change(struct net_bridge *br, unsigned char val)
612 {
613         unsigned long t;
614         int err;
615 
616         if (br->stp_enabled == BR_KERNEL_STP && br->topology_change != val) {
617                 /* On topology change, set the bridge ageing time to twice the
618                  * forward delay. Otherwise, restore its default ageing time.
619                  */
620 
621                 if (val) {
622                         t = 2 * br->forward_delay;
623                         br_debug(br, "decreasing ageing time to %lu\n", t);
624                 } else {
625                         t = br->bridge_ageing_time;
626                         br_debug(br, "restoring ageing time to %lu\n", t);
627                 }
628 
629                 err = __set_ageing_time(br->dev, t);
630                 if (err)
631                         br_warn(br, "error offloading ageing time\n");
632                 else
633                         br->ageing_time = t;
634         }
635 
636         br->topology_change = val;
637 }
638 
639 void __br_set_forward_delay(struct net_bridge *br, unsigned long t)
640 {
641         br->bridge_forward_delay = t;
642         if (br_is_root_bridge(br))
643                 br->forward_delay = br->bridge_forward_delay;
644 }
645 
646 int br_set_forward_delay(struct net_bridge *br, unsigned long val)
647 {
648         unsigned long t = clock_t_to_jiffies(val);
649         int err = -ERANGE;
650 
651         spin_lock_bh(&br->lock);
652         if (br->stp_enabled != BR_NO_STP &&
653             (t < BR_MIN_FORWARD_DELAY || t > BR_MAX_FORWARD_DELAY))
654                 goto unlock;
655 
656         __br_set_forward_delay(br, t);
657         err = 0;
658 
659 unlock:
660         spin_unlock_bh(&br->lock);
661         return err;
662 }
663 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp