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