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