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