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