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