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. 21 */ 22 #define MESSAGE_AGE_INCR ((HZ < 256) ? 1 : (HZ/256)) 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) entering %s state\n", 35 (unsigned) 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 /* called under bridge lock */ 104 static void br_root_selection(struct net_bridge *br) 105 { 106 struct net_bridge_port *p; 107 u16 root_port = 0; 108 109 list_for_each_entry(p, &br->port_list, list) { 110 if (br_should_become_root_port(p, root_port)) 111 root_port = p->port_no; 112 113 } 114 115 br->root_port = root_port; 116 117 if (!root_port) { 118 br->designated_root = br->bridge_id; 119 br->root_path_cost = 0; 120 } else { 121 p = br_get_port(br, root_port); 122 br->designated_root = p->designated_root; 123 br->root_path_cost = p->designated_cost + p->path_cost; 124 } 125 } 126 127 /* called under bridge lock */ 128 void br_become_root_bridge(struct net_bridge *br) 129 { 130 br->max_age = br->bridge_max_age; 131 br->hello_time = br->bridge_hello_time; 132 br->forward_delay = br->bridge_forward_delay; 133 br_topology_change_detection(br); 134 del_timer(&br->tcn_timer); 135 136 if (br->dev->flags & IFF_UP) { 137 br_config_bpdu_generation(br); 138 mod_timer(&br->hello_timer, jiffies + br->hello_time); 139 } 140 } 141 142 /* called under bridge lock */ 143 void br_transmit_config(struct net_bridge_port *p) 144 { 145 struct br_config_bpdu bpdu; 146 struct net_bridge *br; 147 148 149 if (timer_pending(&p->hold_timer)) { 150 p->config_pending = 1; 151 return; 152 } 153 154 br = p->br; 155 156 bpdu.topology_change = br->topology_change; 157 bpdu.topology_change_ack = p->topology_change_ack; 158 bpdu.root = br->designated_root; 159 bpdu.root_path_cost = br->root_path_cost; 160 bpdu.bridge_id = br->bridge_id; 161 bpdu.port_id = p->port_id; 162 if (br_is_root_bridge(br)) 163 bpdu.message_age = 0; 164 else { 165 struct net_bridge_port *root 166 = br_get_port(br, br->root_port); 167 bpdu.message_age = br->max_age 168 - (root->message_age_timer.expires - jiffies) 169 + MESSAGE_AGE_INCR; 170 } 171 bpdu.max_age = br->max_age; 172 bpdu.hello_time = br->hello_time; 173 bpdu.forward_delay = br->forward_delay; 174 175 if (bpdu.message_age < br->max_age) { 176 br_send_config_bpdu(p, &bpdu); 177 p->topology_change_ack = 0; 178 p->config_pending = 0; 179 mod_timer(&p->hold_timer, 180 round_jiffies(jiffies + BR_HOLD_TIME)); 181 } 182 } 183 184 /* called under bridge lock */ 185 static inline void br_record_config_information(struct net_bridge_port *p, 186 const struct br_config_bpdu *bpdu) 187 { 188 p->designated_root = bpdu->root; 189 p->designated_cost = bpdu->root_path_cost; 190 p->designated_bridge = bpdu->bridge_id; 191 p->designated_port = bpdu->port_id; 192 193 mod_timer(&p->message_age_timer, jiffies 194 + (p->br->max_age - bpdu->message_age)); 195 } 196 197 /* called under bridge lock */ 198 static inline void br_record_config_timeout_values(struct net_bridge *br, 199 const struct br_config_bpdu *bpdu) 200 { 201 br->max_age = bpdu->max_age; 202 br->hello_time = bpdu->hello_time; 203 br->forward_delay = bpdu->forward_delay; 204 br->topology_change = bpdu->topology_change; 205 } 206 207 /* called under bridge lock */ 208 void br_transmit_tcn(struct net_bridge *br) 209 { 210 br_send_tcn_bpdu(br_get_port(br, br->root_port)); 211 } 212 213 /* called under bridge lock */ 214 static int br_should_become_designated_port(const struct net_bridge_port *p) 215 { 216 struct net_bridge *br; 217 int t; 218 219 br = p->br; 220 if (br_is_designated_port(p)) 221 return 1; 222 223 if (memcmp(&p->designated_root, &br->designated_root, 8)) 224 return 1; 225 226 if (br->root_path_cost < p->designated_cost) 227 return 1; 228 else if (br->root_path_cost > p->designated_cost) 229 return 0; 230 231 t = memcmp(&br->bridge_id, &p->designated_bridge, 8); 232 if (t < 0) 233 return 1; 234 else if (t > 0) 235 return 0; 236 237 if (p->port_id < p->designated_port) 238 return 1; 239 240 return 0; 241 } 242 243 /* called under bridge lock */ 244 static void br_designated_port_selection(struct net_bridge *br) 245 { 246 struct net_bridge_port *p; 247 248 list_for_each_entry(p, &br->port_list, list) { 249 if (p->state != BR_STATE_DISABLED && 250 br_should_become_designated_port(p)) 251 br_become_designated_port(p); 252 253 } 254 } 255 256 /* called under bridge lock */ 257 static int br_supersedes_port_info(struct net_bridge_port *p, struct br_config_bpdu *bpdu) 258 { 259 int t; 260 261 t = memcmp(&bpdu->root, &p->designated_root, 8); 262 if (t < 0) 263 return 1; 264 else if (t > 0) 265 return 0; 266 267 if (bpdu->root_path_cost < p->designated_cost) 268 return 1; 269 else if (bpdu->root_path_cost > p->designated_cost) 270 return 0; 271 272 t = memcmp(&bpdu->bridge_id, &p->designated_bridge, 8); 273 if (t < 0) 274 return 1; 275 else if (t > 0) 276 return 0; 277 278 if (memcmp(&bpdu->bridge_id, &p->br->bridge_id, 8)) 279 return 1; 280 281 if (bpdu->port_id <= p->designated_port) 282 return 1; 283 284 return 0; 285 } 286 287 /* called under bridge lock */ 288 static inline void br_topology_change_acknowledged(struct net_bridge *br) 289 { 290 br->topology_change_detected = 0; 291 del_timer(&br->tcn_timer); 292 } 293 294 /* called under bridge lock */ 295 void br_topology_change_detection(struct net_bridge *br) 296 { 297 int isroot = br_is_root_bridge(br); 298 299 if (br->stp_enabled != BR_KERNEL_STP) 300 return; 301 302 br_info(br, "topology change detected, %s\n", 303 isroot ? "propagating" : "sending tcn bpdu"); 304 305 if (isroot) { 306 br->topology_change = 1; 307 mod_timer(&br->topology_change_timer, jiffies 308 + br->bridge_forward_delay + br->bridge_max_age); 309 } else if (!br->topology_change_detected) { 310 br_transmit_tcn(br); 311 mod_timer(&br->tcn_timer, jiffies + br->bridge_hello_time); 312 } 313 314 br->topology_change_detected = 1; 315 } 316 317 /* called under bridge lock */ 318 void br_config_bpdu_generation(struct net_bridge *br) 319 { 320 struct net_bridge_port *p; 321 322 list_for_each_entry(p, &br->port_list, list) { 323 if (p->state != BR_STATE_DISABLED && 324 br_is_designated_port(p)) 325 br_transmit_config(p); 326 } 327 } 328 329 /* called under bridge lock */ 330 static inline void br_reply(struct net_bridge_port *p) 331 { 332 br_transmit_config(p); 333 } 334 335 /* called under bridge lock */ 336 void br_configuration_update(struct net_bridge *br) 337 { 338 br_root_selection(br); 339 br_designated_port_selection(br); 340 } 341 342 /* called under bridge lock */ 343 void br_become_designated_port(struct net_bridge_port *p) 344 { 345 struct net_bridge *br; 346 347 br = p->br; 348 p->designated_root = br->designated_root; 349 p->designated_cost = br->root_path_cost; 350 p->designated_bridge = br->bridge_id; 351 p->designated_port = p->port_id; 352 } 353 354 355 /* called under bridge lock */ 356 static void br_make_blocking(struct net_bridge_port *p) 357 { 358 if (p->state != BR_STATE_DISABLED && 359 p->state != BR_STATE_BLOCKING) { 360 if (p->state == BR_STATE_FORWARDING || 361 p->state == BR_STATE_LEARNING) 362 br_topology_change_detection(p->br); 363 364 p->state = BR_STATE_BLOCKING; 365 br_log_state(p); 366 del_timer(&p->forward_delay_timer); 367 } 368 } 369 370 /* called under bridge lock */ 371 static void br_make_forwarding(struct net_bridge_port *p) 372 { 373 struct net_bridge *br = p->br; 374 375 if (p->state != BR_STATE_BLOCKING) 376 return; 377 378 if (br->stp_enabled == BR_NO_STP || br->forward_delay == 0) { 379 p->state = BR_STATE_FORWARDING; 380 br_topology_change_detection(br); 381 del_timer(&p->forward_delay_timer); 382 } 383 else if (br->stp_enabled == BR_KERNEL_STP) 384 p->state = BR_STATE_LISTENING; 385 else 386 p->state = BR_STATE_LEARNING; 387 388 br_multicast_enable_port(p); 389 390 br_log_state(p); 391 392 if (br->forward_delay != 0) 393 mod_timer(&p->forward_delay_timer, jiffies + br->forward_delay); 394 } 395 396 /* called under bridge lock */ 397 void br_port_state_selection(struct net_bridge *br) 398 { 399 struct net_bridge_port *p; 400 unsigned int liveports = 0; 401 402 /* Don't change port states if userspace is handling STP */ 403 if (br->stp_enabled == BR_USER_STP) 404 return; 405 406 list_for_each_entry(p, &br->port_list, list) { 407 if (p->state == BR_STATE_DISABLED) 408 continue; 409 410 if (p->port_no == br->root_port) { 411 p->config_pending = 0; 412 p->topology_change_ack = 0; 413 br_make_forwarding(p); 414 } else if (br_is_designated_port(p)) { 415 del_timer(&p->message_age_timer); 416 br_make_forwarding(p); 417 } else { 418 p->config_pending = 0; 419 p->topology_change_ack = 0; 420 br_make_blocking(p); 421 } 422 423 if (p->state == BR_STATE_FORWARDING) 424 ++liveports; 425 } 426 427 if (liveports == 0) 428 netif_carrier_off(br->dev); 429 else 430 netif_carrier_on(br->dev); 431 } 432 433 /* called under bridge lock */ 434 static inline void br_topology_change_acknowledge(struct net_bridge_port *p) 435 { 436 p->topology_change_ack = 1; 437 br_transmit_config(p); 438 } 439 440 /* called under bridge lock */ 441 void br_received_config_bpdu(struct net_bridge_port *p, struct br_config_bpdu *bpdu) 442 { 443 struct net_bridge *br; 444 int was_root; 445 446 br = p->br; 447 was_root = br_is_root_bridge(br); 448 449 if (br_supersedes_port_info(p, bpdu)) { 450 br_record_config_information(p, bpdu); 451 br_configuration_update(br); 452 br_port_state_selection(br); 453 454 if (!br_is_root_bridge(br) && was_root) { 455 del_timer(&br->hello_timer); 456 if (br->topology_change_detected) { 457 del_timer(&br->topology_change_timer); 458 br_transmit_tcn(br); 459 460 mod_timer(&br->tcn_timer, 461 jiffies + br->bridge_hello_time); 462 } 463 } 464 465 if (p->port_no == br->root_port) { 466 br_record_config_timeout_values(br, bpdu); 467 br_config_bpdu_generation(br); 468 if (bpdu->topology_change_ack) 469 br_topology_change_acknowledged(br); 470 } 471 } else if (br_is_designated_port(p)) { 472 br_reply(p); 473 } 474 } 475 476 /* called under bridge lock */ 477 void br_received_tcn_bpdu(struct net_bridge_port *p) 478 { 479 if (br_is_designated_port(p)) { 480 br_info(p->br, "port %u(%s) received tcn bpdu\n", 481 (unsigned) p->port_no, p->dev->name); 482 483 br_topology_change_detection(p->br); 484 br_topology_change_acknowledge(p); 485 } 486 } 487