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 24static 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 32void 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 */ 40struct 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 */ 53static 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 */ 104static 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 */ 128void 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 */ 143void 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 */ 185static 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 */ 198static 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 */ 208void 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 */ 214static 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 */ 244static 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 */ 257static 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 */ 288static 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 */ 295void 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 u32 ratio = HZ/10; 307 br->topology_change = 1; 308 mod_timer(&br->topology_change_timer, jiffies 309 + (br->bridge_forward_delay + br->bridge_max_age)/ratio); 310 } else if (!br->topology_change_detected) { 311 br_transmit_tcn(br); 312 mod_timer(&br->tcn_timer, jiffies + br->bridge_hello_time); 313 } 314 315 br->topology_change_detected = 1; 316} 317 318/* called under bridge lock */ 319void br_config_bpdu_generation(struct net_bridge *br) 320{ 321 struct net_bridge_port *p; 322 323 list_for_each_entry(p, &br->port_list, list) { 324 if (p->state != BR_STATE_DISABLED && 325 br_is_designated_port(p)) 326 br_transmit_config(p); 327 } 328} 329 330/* called under bridge lock */ 331static inline void br_reply(struct net_bridge_port *p) 332{ 333 br_transmit_config(p); 334} 335 336/* called under bridge lock */ 337void br_configuration_update(struct net_bridge *br) 338{ 339 br_root_selection(br); 340 br_designated_port_selection(br); 341} 342 343/* called under bridge lock */ 344void br_become_designated_port(struct net_bridge_port *p) 345{ 346 struct net_bridge *br; 347 348 br = p->br; 349 p->designated_root = br->designated_root; 350 p->designated_cost = br->root_path_cost; 351 p->designated_bridge = br->bridge_id; 352 p->designated_port = p->port_id; 353} 354 355 356/* called under bridge lock */ 357static void br_make_blocking(struct net_bridge_port *p) 358{ 359 if (p->state != BR_STATE_DISABLED && 360 p->state != BR_STATE_BLOCKING) { 361 if (p->state == BR_STATE_FORWARDING || 362 p->state == BR_STATE_LEARNING) 363 br_topology_change_detection(p->br); 364 365 p->state = BR_STATE_BLOCKING; 366 br_log_state(p); 367 del_timer(&p->forward_delay_timer); 368 } 369} 370 371/* called under bridge lock */ 372static void br_make_forwarding(struct net_bridge_port *p) 373{ 374 struct net_bridge *br = p->br; 375 376 if (p->state != BR_STATE_BLOCKING) 377 return; 378 379 if (br->forward_delay == 0) { 380 p->state = BR_STATE_FORWARDING; 381 br_topology_change_detection(br); 382 del_timer(&p->forward_delay_timer); 383 } 384 else if (p->br->stp_enabled == BR_KERNEL_STP) 385 p->state = BR_STATE_LISTENING; 386 else 387 p->state = BR_STATE_LEARNING; 388 389 br_multicast_enable_port(p); 390 391 br_log_state(p); 392 393 if (br->forward_delay != 0) 394 mod_timer(&p->forward_delay_timer, jiffies + br->forward_delay); 395} 396 397/* called under bridge lock */ 398void br_port_state_selection(struct net_bridge *br) 399{ 400 struct net_bridge_port *p; 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 if (p->port_no == br->root_port) { 409 p->config_pending = 0; 410 p->topology_change_ack = 0; 411 br_make_forwarding(p); 412 } else if (br_is_designated_port(p)) { 413 del_timer(&p->message_age_timer); 414 br_make_forwarding(p); 415 } else { 416 p->config_pending = 0; 417 p->topology_change_ack = 0; 418 br_make_blocking(p); 419 } 420 } 421 422 } 423} 424 425/* called under bridge lock */ 426static inline void br_topology_change_acknowledge(struct net_bridge_port *p) 427{ 428 p->topology_change_ack = 1; 429 br_transmit_config(p); 430} 431 432/* called under bridge lock */ 433void br_received_config_bpdu(struct net_bridge_port *p, struct br_config_bpdu *bpdu) 434{ 435 struct net_bridge *br; 436 int was_root; 437 438 br = p->br; 439 was_root = br_is_root_bridge(br); 440 441 if (br_supersedes_port_info(p, bpdu)) { 442 br_record_config_information(p, bpdu); 443 br_configuration_update(br); 444 br_port_state_selection(br); 445 446 if (!br_is_root_bridge(br) && was_root) { 447 del_timer(&br->hello_timer); 448 if (br->topology_change_detected) { 449 del_timer(&br->topology_change_timer); 450 br_transmit_tcn(br); 451 452 mod_timer(&br->tcn_timer, 453 jiffies + br->bridge_hello_time); 454 } 455 } 456 457 if (p->port_no == br->root_port) { 458 br_record_config_timeout_values(br, bpdu); 459 br_config_bpdu_generation(br); 460 if (bpdu->topology_change_ack) 461 br_topology_change_acknowledged(br); 462 } 463 } else if (br_is_designated_port(p)) { 464 br_reply(p); 465 } 466} 467 468/* called under bridge lock */ 469void br_received_tcn_bpdu(struct net_bridge_port *p) 470{ 471 if (br_is_designated_port(p)) { 472 br_info(p->br, "port %u(%s) received tcn bpdu\n", 473 (unsigned) p->port_no, p->dev->name); 474 475 br_topology_change_detection(p->br); 476 br_topology_change_acknowledge(p); 477 } 478} 479