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