linux/net/bridge/br_stp.c
<<
>>
Prefs
   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 STP tick.
  21 */
  22#define MESSAGE_AGE_INCR        ((HZ / 256) + 1)
  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) entered %s state\n",
  35                (unsigned int) 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        br->root_port = root_port;
 115
 116        if (!root_port) {
 117                br->designated_root = br->bridge_id;
 118                br->root_path_cost = 0;
 119        } else {
 120                p = br_get_port(br, root_port);
 121                br->designated_root = p->designated_root;
 122                br->root_path_cost = p->designated_cost + p->path_cost;
 123        }
 124}
 125
 126/* called under bridge lock */
 127void br_become_root_bridge(struct net_bridge *br)
 128{
 129        br->max_age = br->bridge_max_age;
 130        br->hello_time = br->bridge_hello_time;
 131        br->forward_delay = br->bridge_forward_delay;
 132        br_topology_change_detection(br);
 133        del_timer(&br->tcn_timer);
 134
 135        if (br->dev->flags & IFF_UP) {
 136                br_config_bpdu_generation(br);
 137                mod_timer(&br->hello_timer, jiffies + br->hello_time);
 138        }
 139}
 140
 141/* called under bridge lock */
 142void br_transmit_config(struct net_bridge_port *p)
 143{
 144        struct br_config_bpdu bpdu;
 145        struct net_bridge *br;
 146
 147        if (timer_pending(&p->hold_timer)) {
 148                p->config_pending = 1;
 149                return;
 150        }
 151
 152        br = p->br;
 153
 154        bpdu.topology_change = br->topology_change;
 155        bpdu.topology_change_ack = p->topology_change_ack;
 156        bpdu.root = br->designated_root;
 157        bpdu.root_path_cost = br->root_path_cost;
 158        bpdu.bridge_id = br->bridge_id;
 159        bpdu.port_id = p->port_id;
 160        if (br_is_root_bridge(br))
 161                bpdu.message_age = 0;
 162        else {
 163                struct net_bridge_port *root
 164                        = br_get_port(br, br->root_port);
 165                bpdu.message_age = (jiffies - root->designated_age)
 166                        + MESSAGE_AGE_INCR;
 167        }
 168        bpdu.max_age = br->max_age;
 169        bpdu.hello_time = br->hello_time;
 170        bpdu.forward_delay = br->forward_delay;
 171
 172        if (bpdu.message_age < br->max_age) {
 173                br_send_config_bpdu(p, &bpdu);
 174                p->topology_change_ack = 0;
 175                p->config_pending = 0;
 176                mod_timer(&p->hold_timer,
 177                          round_jiffies(jiffies + BR_HOLD_TIME));
 178        }
 179}
 180
 181/* called under bridge lock */
 182static void br_record_config_information(struct net_bridge_port *p,
 183                                         const struct br_config_bpdu *bpdu)
 184{
 185        p->designated_root = bpdu->root;
 186        p->designated_cost = bpdu->root_path_cost;
 187        p->designated_bridge = bpdu->bridge_id;
 188        p->designated_port = bpdu->port_id;
 189        p->designated_age = jiffies - bpdu->message_age;
 190
 191        mod_timer(&p->message_age_timer, jiffies
 192                  + (p->br->max_age - bpdu->message_age));
 193}
 194
 195/* called under bridge lock */
 196static void br_record_config_timeout_values(struct net_bridge *br,
 197                                            const struct br_config_bpdu *bpdu)
 198{
 199        br->max_age = bpdu->max_age;
 200        br->hello_time = bpdu->hello_time;
 201        br->forward_delay = bpdu->forward_delay;
 202        br->topology_change = bpdu->topology_change;
 203}
 204
 205/* called under bridge lock */
 206void br_transmit_tcn(struct net_bridge *br)
 207{
 208        br_send_tcn_bpdu(br_get_port(br, br->root_port));
 209}
 210
 211/* called under bridge lock */
 212static int br_should_become_designated_port(const struct net_bridge_port *p)
 213{
 214        struct net_bridge *br;
 215        int t;
 216
 217        br = p->br;
 218        if (br_is_designated_port(p))
 219                return 1;
 220
 221        if (memcmp(&p->designated_root, &br->designated_root, 8))
 222                return 1;
 223
 224        if (br->root_path_cost < p->designated_cost)
 225                return 1;
 226        else if (br->root_path_cost > p->designated_cost)
 227                return 0;
 228
 229        t = memcmp(&br->bridge_id, &p->designated_bridge, 8);
 230        if (t < 0)
 231                return 1;
 232        else if (t > 0)
 233                return 0;
 234
 235        if (p->port_id < p->designated_port)
 236                return 1;
 237
 238        return 0;
 239}
 240
 241/* called under bridge lock */
 242static void br_designated_port_selection(struct net_bridge *br)
 243{
 244        struct net_bridge_port *p;
 245
 246        list_for_each_entry(p, &br->port_list, list) {
 247                if (p->state != BR_STATE_DISABLED &&
 248                    br_should_become_designated_port(p))
 249                        br_become_designated_port(p);
 250
 251        }
 252}
 253
 254/* called under bridge lock */
 255static int br_supersedes_port_info(const struct net_bridge_port *p,
 256                                   const struct br_config_bpdu *bpdu)
 257{
 258        int t;
 259
 260        t = memcmp(&bpdu->root, &p->designated_root, 8);
 261        if (t < 0)
 262                return 1;
 263        else if (t > 0)
 264                return 0;
 265
 266        if (bpdu->root_path_cost < p->designated_cost)
 267                return 1;
 268        else if (bpdu->root_path_cost > p->designated_cost)
 269                return 0;
 270
 271        t = memcmp(&bpdu->bridge_id, &p->designated_bridge, 8);
 272        if (t < 0)
 273                return 1;
 274        else if (t > 0)
 275                return 0;
 276
 277        if (memcmp(&bpdu->bridge_id, &p->br->bridge_id, 8))
 278                return 1;
 279
 280        if (bpdu->port_id <= p->designated_port)
 281                return 1;
 282
 283        return 0;
 284}
 285
 286/* called under bridge lock */
 287static void br_topology_change_acknowledged(struct net_bridge *br)
 288{
 289        br->topology_change_detected = 0;
 290        del_timer(&br->tcn_timer);
 291}
 292
 293/* called under bridge lock */
 294void br_topology_change_detection(struct net_bridge *br)
 295{
 296        int isroot = br_is_root_bridge(br);
 297
 298        if (br->stp_enabled != BR_KERNEL_STP)
 299                return;
 300
 301        br_info(br, "topology change detected, %s\n",
 302                isroot ? "propagating" : "sending tcn bpdu");
 303
 304        if (isroot) {
 305                br->topology_change = 1;
 306                mod_timer(&br->topology_change_timer, jiffies
 307                          + br->bridge_forward_delay + br->bridge_max_age);
 308        } else if (!br->topology_change_detected) {
 309                br_transmit_tcn(br);
 310                mod_timer(&br->tcn_timer, jiffies + br->bridge_hello_time);
 311        }
 312
 313        br->topology_change_detected = 1;
 314}
 315
 316/* called under bridge lock */
 317void br_config_bpdu_generation(struct net_bridge *br)
 318{
 319        struct net_bridge_port *p;
 320
 321        list_for_each_entry(p, &br->port_list, list) {
 322                if (p->state != BR_STATE_DISABLED &&
 323                    br_is_designated_port(p))
 324                        br_transmit_config(p);
 325        }
 326}
 327
 328/* called under bridge lock */
 329static void br_reply(struct net_bridge_port *p)
 330{
 331        br_transmit_config(p);
 332}
 333
 334/* called under bridge lock */
 335void br_configuration_update(struct net_bridge *br)
 336{
 337        br_root_selection(br);
 338        br_designated_port_selection(br);
 339}
 340
 341/* called under bridge lock */
 342void br_become_designated_port(struct net_bridge_port *p)
 343{
 344        struct net_bridge *br;
 345
 346        br = p->br;
 347        p->designated_root = br->designated_root;
 348        p->designated_cost = br->root_path_cost;
 349        p->designated_bridge = br->bridge_id;
 350        p->designated_port = p->port_id;
 351}
 352
 353
 354/* called under bridge lock */
 355static void br_make_blocking(struct net_bridge_port *p)
 356{
 357        if (p->state != BR_STATE_DISABLED &&
 358            p->state != BR_STATE_BLOCKING) {
 359                if (p->state == BR_STATE_FORWARDING ||
 360                    p->state == BR_STATE_LEARNING)
 361                        br_topology_change_detection(p->br);
 362
 363                p->state = BR_STATE_BLOCKING;
 364                br_log_state(p);
 365                br_ifinfo_notify(RTM_NEWLINK, p);
 366
 367                del_timer(&p->forward_delay_timer);
 368        }
 369}
 370
 371/* called under bridge lock */
 372static 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->stp_enabled == BR_NO_STP || br->forward_delay == 0) {
 380                p->state = BR_STATE_FORWARDING;
 381                br_topology_change_detection(br);
 382                del_timer(&p->forward_delay_timer);
 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        br_log_state(p);
 390        br_ifinfo_notify(RTM_NEWLINK, 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        list_for_each_entry(p, &br->port_list, list) {
 403                if (p->state == BR_STATE_DISABLED)
 404                        continue;
 405
 406                /* Don't change port states if userspace is handling STP */
 407                if (br->stp_enabled != BR_USER_STP) {
 408                        if (p->port_no == br->root_port) {
 409                                p->config_pending = 0;
 410                                p->topology_change_ack = 0;
 411                                br_make_forwarding(p);
 412                        } else if (br_is_designated_port(p)) {
 413                                del_timer(&p->message_age_timer);
 414                                br_make_forwarding(p);
 415                        } else {
 416                                p->config_pending = 0;
 417                                p->topology_change_ack = 0;
 418                                br_make_blocking(p);
 419                        }
 420                }
 421
 422                if (p->state == BR_STATE_FORWARDING)
 423                        ++liveports;
 424        }
 425
 426        if (liveports == 0)
 427                netif_carrier_off(br->dev);
 428        else
 429                netif_carrier_on(br->dev);
 430}
 431
 432/* called under bridge lock */
 433static void br_topology_change_acknowledge(struct net_bridge_port *p)
 434{
 435        p->topology_change_ack = 1;
 436        br_transmit_config(p);
 437}
 438
 439/* called under bridge lock */
 440void br_received_config_bpdu(struct net_bridge_port *p,
 441                             const 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 int) p->port_no, p->dev->name);
 482
 483                br_topology_change_detection(p->br);
 484                br_topology_change_acknowledge(p);
 485        }
 486}
 487
 488/* Change bridge STP parameter */
 489int br_set_hello_time(struct net_bridge *br, unsigned long val)
 490{
 491        unsigned long t = clock_t_to_jiffies(val);
 492
 493        if (t < BR_MIN_HELLO_TIME || t > BR_MAX_HELLO_TIME)
 494                return -ERANGE;
 495
 496        spin_lock_bh(&br->lock);
 497        br->bridge_hello_time = t;
 498        if (br_is_root_bridge(br))
 499                br->hello_time = br->bridge_hello_time;
 500        spin_unlock_bh(&br->lock);
 501        return 0;
 502}
 503
 504int br_set_max_age(struct net_bridge *br, unsigned long val)
 505{
 506        unsigned long t = clock_t_to_jiffies(val);
 507
 508        if (t < BR_MIN_MAX_AGE || t > BR_MAX_MAX_AGE)
 509                return -ERANGE;
 510
 511        spin_lock_bh(&br->lock);
 512        br->bridge_max_age = t;
 513        if (br_is_root_bridge(br))
 514                br->max_age = br->bridge_max_age;
 515        spin_unlock_bh(&br->lock);
 516        return 0;
 517
 518}
 519
 520int br_set_forward_delay(struct net_bridge *br, unsigned long val)
 521{
 522        unsigned long t = clock_t_to_jiffies(val);
 523
 524        if (br->stp_enabled != BR_NO_STP &&
 525            (t < BR_MIN_FORWARD_DELAY || t > BR_MAX_FORWARD_DELAY))
 526                return -ERANGE;
 527
 528        spin_lock_bh(&br->lock);
 529        br->bridge_forward_delay = t;
 530        if (br_is_root_bridge(br))
 531                br->forward_delay = br->bridge_forward_delay;
 532        spin_unlock_bh(&br->lock);
 533        return 0;
 534}
 535
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.