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