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