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