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