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 25static 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 33void 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 40void 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 */ 57struct 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 */ 70static 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 120static 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 */ 136static 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 */ 164void 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 */ 179void 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 */ 220static 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 */ 234static 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 */ 244void 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 */ 257static 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 */ 287static 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 */ 300static 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 */ 332static 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 */ 339void 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 */ 362void 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 */ 374static void br_reply(struct net_bridge_port *p) 375{ 376 br_transmit_config(p); 377} 378 379/* called under bridge lock */ 380void 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 */ 387void 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 */ 400static 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 */ 417static 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 */ 441void 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 */ 483static 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 */ 490void 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 */ 527void 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 */ 539int 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 554int 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/* Set time interval that dynamic forwarding entries live 571 * For pure software bridge, allow values outside the 802.1 572 * standard specification for special cases: 573 * 0 - entry never ages (all permanant) 574 * 1 - entry disappears (no persistance) 575 * 576 * Offloaded switch entries maybe more restrictive 577 */ 578int br_set_ageing_time(struct net_bridge *br, u32 ageing_time) 579{ 580 struct switchdev_attr attr = { 581 .id = SWITCHDEV_ATTR_ID_BRIDGE_AGEING_TIME, 582 .flags = SWITCHDEV_F_SKIP_EOPNOTSUPP, 583 .u.ageing_time = ageing_time, 584 }; 585 unsigned long t = clock_t_to_jiffies(ageing_time); 586 int err; 587 588 err = switchdev_port_attr_set(br->dev, &attr); 589 if (err && err != -EOPNOTSUPP) 590 return err; 591 592 br->ageing_time = t; 593 mod_timer(&br->gc_timer, jiffies); 594 595 return 0; 596} 597 598void __br_set_forward_delay(struct net_bridge *br, unsigned long t) 599{ 600 br->bridge_forward_delay = t; 601 if (br_is_root_bridge(br)) 602 br->forward_delay = br->bridge_forward_delay; 603} 604 605int br_set_forward_delay(struct net_bridge *br, unsigned long val) 606{ 607 unsigned long t = clock_t_to_jiffies(val); 608 int err = -ERANGE; 609 610 spin_lock_bh(&br->lock); 611 if (br->stp_enabled != BR_NO_STP && 612 (t < BR_MIN_FORWARD_DELAY || t > BR_MAX_FORWARD_DELAY)) 613 goto unlock; 614 615 __br_set_forward_delay(br, t); 616 err = 0; 617 618unlock: 619 spin_unlock_bh(&br->lock); 620 return err; 621} 622