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 if (p->br->stp_enabled == BR_KERNEL_STP) 213 mod_timer(&p->hold_timer, 214 round_jiffies(jiffies + BR_HOLD_TIME)); 215 } 216 } 217 218 /* called under bridge lock */ 219 static void br_record_config_information(struct net_bridge_port *p, 220 const struct br_config_bpdu *bpdu) 221 { 222 p->designated_root = bpdu->root; 223 p->designated_cost = bpdu->root_path_cost; 224 p->designated_bridge = bpdu->bridge_id; 225 p->designated_port = bpdu->port_id; 226 p->designated_age = jiffies - bpdu->message_age; 227 228 mod_timer(&p->message_age_timer, jiffies 229 + (bpdu->max_age - bpdu->message_age)); 230 } 231 232 /* called under bridge lock */ 233 static void br_record_config_timeout_values(struct net_bridge *br, 234 const struct br_config_bpdu *bpdu) 235 { 236 br->max_age = bpdu->max_age; 237 br->hello_time = bpdu->hello_time; 238 br->forward_delay = bpdu->forward_delay; 239 br->topology_change = bpdu->topology_change; 240 } 241 242 /* called under bridge lock */ 243 void br_transmit_tcn(struct net_bridge *br) 244 { 245 struct net_bridge_port *p; 246 247 p = br_get_port(br, br->root_port); 248 if (p) 249 br_send_tcn_bpdu(p); 250 else 251 br_notice(br, "root port %u not found for topology notice\n", 252 br->root_port); 253 } 254 255 /* called under bridge lock */ 256 static int br_should_become_designated_port(const struct net_bridge_port *p) 257 { 258 struct net_bridge *br; 259 int t; 260 261 br = p->br; 262 if (br_is_designated_port(p)) 263 return 1; 264 265 if (memcmp(&p->designated_root, &br->designated_root, 8)) 266 return 1; 267 268 if (br->root_path_cost < p->designated_cost) 269 return 1; 270 else if (br->root_path_cost > p->designated_cost) 271 return 0; 272 273 t = memcmp(&br->bridge_id, &p->designated_bridge, 8); 274 if (t < 0) 275 return 1; 276 else if (t > 0) 277 return 0; 278 279 if (p->port_id < p->designated_port) 280 return 1; 281 282 return 0; 283 } 284 285 /* called under bridge lock */ 286 static void br_designated_port_selection(struct net_bridge *br) 287 { 288 struct net_bridge_port *p; 289 290 list_for_each_entry(p, &br->port_list, list) { 291 if (p->state != BR_STATE_DISABLED && 292 br_should_become_designated_port(p)) 293 br_become_designated_port(p); 294 295 } 296 } 297 298 /* called under bridge lock */ 299 static int br_supersedes_port_info(const struct net_bridge_port *p, 300 const struct br_config_bpdu *bpdu) 301 { 302 int t; 303 304 t = memcmp(&bpdu->root, &p->designated_root, 8); 305 if (t < 0) 306 return 1; 307 else if (t > 0) 308 return 0; 309 310 if (bpdu->root_path_cost < p->designated_cost) 311 return 1; 312 else if (bpdu->root_path_cost > p->designated_cost) 313 return 0; 314 315 t = memcmp(&bpdu->bridge_id, &p->designated_bridge, 8); 316 if (t < 0) 317 return 1; 318 else if (t > 0) 319 return 0; 320 321 if (memcmp(&bpdu->bridge_id, &p->br->bridge_id, 8)) 322 return 1; 323 324 if (bpdu->port_id <= p->designated_port) 325 return 1; 326 327 return 0; 328 } 329 330 /* called under bridge lock */ 331 static void br_topology_change_acknowledged(struct net_bridge *br) 332 { 333 br->topology_change_detected = 0; 334 del_timer(&br->tcn_timer); 335 } 336 337 /* called under bridge lock */ 338 void br_topology_change_detection(struct net_bridge *br) 339 { 340 int isroot = br_is_root_bridge(br); 341 342 if (br->stp_enabled != BR_KERNEL_STP) 343 return; 344 345 br_info(br, "topology change detected, %s\n", 346 isroot ? "propagating" : "sending tcn bpdu"); 347 348 if (isroot) { 349 br->topology_change = 1; 350 mod_timer(&br->topology_change_timer, jiffies 351 + br->bridge_forward_delay + br->bridge_max_age); 352 } else if (!br->topology_change_detected) { 353 br_transmit_tcn(br); 354 mod_timer(&br->tcn_timer, jiffies + br->bridge_hello_time); 355 } 356 357 br->topology_change_detected = 1; 358 } 359 360 /* called under bridge lock */ 361 void br_config_bpdu_generation(struct net_bridge *br) 362 { 363 struct net_bridge_port *p; 364 365 list_for_each_entry(p, &br->port_list, list) { 366 if (p->state != BR_STATE_DISABLED && 367 br_is_designated_port(p)) 368 br_transmit_config(p); 369 } 370 } 371 372 /* called under bridge lock */ 373 static void br_reply(struct net_bridge_port *p) 374 { 375 br_transmit_config(p); 376 } 377 378 /* called under bridge lock */ 379 void br_configuration_update(struct net_bridge *br) 380 { 381 br_root_selection(br); 382 br_designated_port_selection(br); 383 } 384 385 /* called under bridge lock */ 386 void br_become_designated_port(struct net_bridge_port *p) 387 { 388 struct net_bridge *br; 389 390 br = p->br; 391 p->designated_root = br->designated_root; 392 p->designated_cost = br->root_path_cost; 393 p->designated_bridge = br->bridge_id; 394 p->designated_port = p->port_id; 395 } 396 397 398 /* called under bridge lock */ 399 static void br_make_blocking(struct net_bridge_port *p) 400 { 401 if (p->state != BR_STATE_DISABLED && 402 p->state != BR_STATE_BLOCKING) { 403 if (p->state == BR_STATE_FORWARDING || 404 p->state == BR_STATE_LEARNING) 405 br_topology_change_detection(p->br); 406 407 br_set_state(p, BR_STATE_BLOCKING); 408 br_log_state(p); 409 br_ifinfo_notify(RTM_NEWLINK, p); 410 411 del_timer(&p->forward_delay_timer); 412 } 413 } 414 415 /* called under bridge lock */ 416 static void br_make_forwarding(struct net_bridge_port *p) 417 { 418 struct net_bridge *br = p->br; 419 420 if (p->state != BR_STATE_BLOCKING) 421 return; 422 423 if (br->stp_enabled == BR_NO_STP || br->forward_delay == 0) { 424 br_set_state(p, BR_STATE_FORWARDING); 425 br_topology_change_detection(br); 426 del_timer(&p->forward_delay_timer); 427 } else if (br->stp_enabled == BR_KERNEL_STP) 428 br_set_state(p, BR_STATE_LISTENING); 429 else 430 br_set_state(p, BR_STATE_LEARNING); 431 432 br_log_state(p); 433 br_ifinfo_notify(RTM_NEWLINK, p); 434 435 if (br->forward_delay != 0) 436 mod_timer(&p->forward_delay_timer, jiffies + br->forward_delay); 437 } 438 439 /* called under bridge lock */ 440 void br_port_state_selection(struct net_bridge *br) 441 { 442 struct net_bridge_port *p; 443 unsigned int liveports = 0; 444 445 list_for_each_entry(p, &br->port_list, list) { 446 if (p->state == BR_STATE_DISABLED) 447 continue; 448 449 /* Don't change port states if userspace is handling STP */ 450 if (br->stp_enabled != BR_USER_STP) { 451 if (p->port_no == br->root_port) { 452 p->config_pending = 0; 453 p->topology_change_ack = 0; 454 br_make_forwarding(p); 455 } else if (br_is_designated_port(p)) { 456 del_timer(&p->message_age_timer); 457 br_make_forwarding(p); 458 } else { 459 p->config_pending = 0; 460 p->topology_change_ack = 0; 461 br_make_blocking(p); 462 } 463 } 464 465 if (p->state != BR_STATE_BLOCKING) 466 br_multicast_enable_port(p); 467 /* Multicast is not disabled for the port when it goes in 468 * blocking state because the timers will expire and stop by 469 * themselves without sending more queries. 470 */ 471 if (p->state == BR_STATE_FORWARDING) 472 ++liveports; 473 } 474 475 if (liveports == 0) 476 netif_carrier_off(br->dev); 477 else 478 netif_carrier_on(br->dev); 479 } 480 481 /* called under bridge lock */ 482 static void br_topology_change_acknowledge(struct net_bridge_port *p) 483 { 484 p->topology_change_ack = 1; 485 br_transmit_config(p); 486 } 487 488 /* called under bridge lock */ 489 void br_received_config_bpdu(struct net_bridge_port *p, 490 const struct br_config_bpdu *bpdu) 491 { 492 struct net_bridge *br; 493 int was_root; 494 495 br = p->br; 496 was_root = br_is_root_bridge(br); 497 498 if (br_supersedes_port_info(p, bpdu)) { 499 br_record_config_information(p, bpdu); 500 br_configuration_update(br); 501 br_port_state_selection(br); 502 503 if (!br_is_root_bridge(br) && was_root) { 504 del_timer(&br->hello_timer); 505 if (br->topology_change_detected) { 506 del_timer(&br->topology_change_timer); 507 br_transmit_tcn(br); 508 509 mod_timer(&br->tcn_timer, 510 jiffies + br->bridge_hello_time); 511 } 512 } 513 514 if (p->port_no == br->root_port) { 515 br_record_config_timeout_values(br, bpdu); 516 br_config_bpdu_generation(br); 517 if (bpdu->topology_change_ack) 518 br_topology_change_acknowledged(br); 519 } 520 } else if (br_is_designated_port(p)) { 521 br_reply(p); 522 } 523 } 524 525 /* called under bridge lock */ 526 void br_received_tcn_bpdu(struct net_bridge_port *p) 527 { 528 if (br_is_designated_port(p)) { 529 br_info(p->br, "port %u(%s) received tcn bpdu\n", 530 (unsigned int) p->port_no, p->dev->name); 531 532 br_topology_change_detection(p->br); 533 br_topology_change_acknowledge(p); 534 } 535 } 536 537 /* Change bridge STP parameter */ 538 int br_set_hello_time(struct net_bridge *br, unsigned long val) 539 { 540 unsigned long t = clock_t_to_jiffies(val); 541 542 if (t < BR_MIN_HELLO_TIME || t > BR_MAX_HELLO_TIME) 543 return -ERANGE; 544 545 spin_lock_bh(&br->lock); 546 br->bridge_hello_time = t; 547 if (br_is_root_bridge(br)) 548 br->hello_time = br->bridge_hello_time; 549 spin_unlock_bh(&br->lock); 550 return 0; 551 } 552 553 int br_set_max_age(struct net_bridge *br, unsigned long val) 554 { 555 unsigned long t = clock_t_to_jiffies(val); 556 557 if (t < BR_MIN_MAX_AGE || t > BR_MAX_MAX_AGE) 558 return -ERANGE; 559 560 spin_lock_bh(&br->lock); 561 br->bridge_max_age = t; 562 if (br_is_root_bridge(br)) 563 br->max_age = br->bridge_max_age; 564 spin_unlock_bh(&br->lock); 565 return 0; 566 567 } 568 569 void __br_set_forward_delay(struct net_bridge *br, unsigned long t) 570 { 571 br->bridge_forward_delay = t; 572 if (br_is_root_bridge(br)) 573 br->forward_delay = br->bridge_forward_delay; 574 } 575 576 int br_set_forward_delay(struct net_bridge *br, unsigned long val) 577 { 578 unsigned long t = clock_t_to_jiffies(val); 579 int err = -ERANGE; 580 581 spin_lock_bh(&br->lock); 582 if (br->stp_enabled != BR_NO_STP && 583 (t < BR_MIN_FORWARD_DELAY || t > BR_MAX_FORWARD_DELAY)) 584 goto unlock; 585 586 __br_set_forward_delay(br, t); 587 err = 0; 588 589 unlock: 590 spin_unlock_bh(&br->lock); 591 return err; 592 } 593