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