1 /* 2 * Spanning tree protocol; generic parts 3 * Linux ethernet bridge 4 * 5 * Authors: 6 * Lennert Buytenhek <buytenh@gnu.org> 7 * 8 * $Id: br_stp.c,v 1.4 2000/06/19 10:13:35 davem Exp $ 9 * 10 * This program is free software; you can redistribute it and/or 11 * modify it under the terms of the GNU General Public License 12 * as published by the Free Software Foundation; either version 13 * 2 of the License, or (at your option) any later version. 14 */ 15 #include <linux/kernel.h> 16 #include <linux/smp_lock.h> 17 18 #include "br_private.h" 19 #include "br_private_stp.h" 20 21 /* since time values in bpdu are in jiffies and then scaled (1/256) 22 * before sending, make sure that is at least one. 23 */ 24 #define MESSAGE_AGE_INCR ((HZ < 256) ? 1 : (HZ/256)) 25 26 static const char *br_port_state_names[] = { 27 [BR_STATE_DISABLED] = "disabled", 28 [BR_STATE_LISTENING] = "listening", 29 [BR_STATE_LEARNING] = "learning", 30 [BR_STATE_FORWARDING] = "forwarding", 31 [BR_STATE_BLOCKING] = "blocking", 32 }; 33 34 void br_log_state(const struct net_bridge_port *p) 35 { 36 pr_info("%s: port %d(%s) entering %s state\n", 37 p->br->dev->name, p->port_no, p->dev->name, 38 br_port_state_names[p->state]); 39 40 } 41 42 /* called under bridge lock */ 43 struct net_bridge_port *br_get_port(struct net_bridge *br, u16 port_no) 44 { 45 struct net_bridge_port *p; 46 47 list_for_each_entry_rcu(p, &br->port_list, list) { 48 if (p->port_no == port_no) 49 return p; 50 } 51 52 return NULL; 53 } 54 55 /* called under bridge lock */ 56 static int br_should_become_root_port(const struct net_bridge_port *p, 57 u16 root_port) 58 { 59 struct net_bridge *br; 60 struct net_bridge_port *rp; 61 int t; 62 63 br = p->br; 64 if (p->state == BR_STATE_DISABLED || 65 br_is_designated_port(p)) 66 return 0; 67 68 if (memcmp(&br->bridge_id, &p->designated_root, 8) <= 0) 69 return 0; 70 71 if (!root_port) 72 return 1; 73 74 rp = br_get_port(br, root_port); 75 76 t = memcmp(&p->designated_root, &rp->designated_root, 8); 77 if (t < 0) 78 return 1; 79 else if (t > 0) 80 return 0; 81 82 if (p->designated_cost + p->path_cost < 83 rp->designated_cost + rp->path_cost) 84 return 1; 85 else if (p->designated_cost + p->path_cost > 86 rp->designated_cost + rp->path_cost) 87 return 0; 88 89 t = memcmp(&p->designated_bridge, &rp->designated_bridge, 8); 90 if (t < 0) 91 return 1; 92 else if (t > 0) 93 return 0; 94 95 if (p->designated_port < rp->designated_port) 96 return 1; 97 else if (p->designated_port > rp->designated_port) 98 return 0; 99 100 if (p->port_id < rp->port_id) 101 return 1; 102 103 return 0; 104 } 105 106 /* called under bridge lock */ 107 static void br_root_selection(struct net_bridge *br) 108 { 109 struct net_bridge_port *p; 110 u16 root_port = 0; 111 112 list_for_each_entry(p, &br->port_list, list) { 113 if (br_should_become_root_port(p, root_port)) 114 root_port = p->port_no; 115 116 } 117 118 br->root_port = root_port; 119 120 if (!root_port) { 121 br->designated_root = br->bridge_id; 122 br->root_path_cost = 0; 123 } else { 124 p = br_get_port(br, root_port); 125 br->designated_root = p->designated_root; 126 br->root_path_cost = p->designated_cost + p->path_cost; 127 } 128 } 129 130 /* called under bridge lock */ 131 void br_become_root_bridge(struct net_bridge *br) 132 { 133 br->max_age = br->bridge_max_age; 134 br->hello_time = br->bridge_hello_time; 135 br->forward_delay = br->bridge_forward_delay; 136 br_topology_change_detection(br); 137 del_timer(&br->tcn_timer); 138 139 if (br->dev->flags & IFF_UP) { 140 br_config_bpdu_generation(br); 141 mod_timer(&br->hello_timer, jiffies + br->hello_time); 142 } 143 } 144 145 /* called under bridge lock */ 146 void br_transmit_config(struct net_bridge_port *p) 147 { 148 struct br_config_bpdu bpdu; 149 struct net_bridge *br; 150 151 152 if (timer_pending(&p->hold_timer)) { 153 p->config_pending = 1; 154 return; 155 } 156 157 br = p->br; 158 159 bpdu.topology_change = br->topology_change; 160 bpdu.topology_change_ack = p->topology_change_ack; 161 bpdu.root = br->designated_root; 162 bpdu.root_path_cost = br->root_path_cost; 163 bpdu.bridge_id = br->bridge_id; 164 bpdu.port_id = p->port_id; 165 if (br_is_root_bridge(br)) 166 bpdu.message_age = 0; 167 else { 168 struct net_bridge_port *root 169 = br_get_port(br, br->root_port); 170 bpdu.message_age = br->max_age 171 - (root->message_age_timer.expires - jiffies) 172 + MESSAGE_AGE_INCR; 173 } 174 bpdu.max_age = br->max_age; 175 bpdu.hello_time = br->hello_time; 176 bpdu.forward_delay = br->forward_delay; 177 178 if (bpdu.message_age < br->max_age) { 179 br_send_config_bpdu(p, &bpdu); 180 p->topology_change_ack = 0; 181 p->config_pending = 0; 182 mod_timer(&p->hold_timer, jiffies + BR_HOLD_TIME); 183 } 184 } 185 186 /* called under bridge lock */ 187 static inline void br_record_config_information(struct net_bridge_port *p, 188 const struct br_config_bpdu *bpdu) 189 { 190 p->designated_root = bpdu->root; 191 p->designated_cost = bpdu->root_path_cost; 192 p->designated_bridge = bpdu->bridge_id; 193 p->designated_port = bpdu->port_id; 194 195 mod_timer(&p->message_age_timer, jiffies 196 + (p->br->max_age - bpdu->message_age)); 197 } 198 199 /* called under bridge lock */ 200 static inline void br_record_config_timeout_values(struct net_bridge *br, 201 const struct br_config_bpdu *bpdu) 202 { 203 br->max_age = bpdu->max_age; 204 br->hello_time = bpdu->hello_time; 205 br->forward_delay = bpdu->forward_delay; 206 br->topology_change = bpdu->topology_change; 207 } 208 209 /* called under bridge lock */ 210 void br_transmit_tcn(struct net_bridge *br) 211 { 212 br_send_tcn_bpdu(br_get_port(br, br->root_port)); 213 } 214 215 /* called under bridge lock */ 216 static int br_should_become_designated_port(const struct net_bridge_port *p) 217 { 218 struct net_bridge *br; 219 int t; 220 221 br = p->br; 222 if (br_is_designated_port(p)) 223 return 1; 224 225 if (memcmp(&p->designated_root, &br->designated_root, 8)) 226 return 1; 227 228 if (br->root_path_cost < p->designated_cost) 229 return 1; 230 else if (br->root_path_cost > p->designated_cost) 231 return 0; 232 233 t = memcmp(&br->bridge_id, &p->designated_bridge, 8); 234 if (t < 0) 235 return 1; 236 else if (t > 0) 237 return 0; 238 239 if (p->port_id < p->designated_port) 240 return 1; 241 242 return 0; 243 } 244 245 /* called under bridge lock */ 246 static void br_designated_port_selection(struct net_bridge *br) 247 { 248 struct net_bridge_port *p; 249 250 list_for_each_entry(p, &br->port_list, list) { 251 if (p->state != BR_STATE_DISABLED && 252 br_should_become_designated_port(p)) 253 br_become_designated_port(p); 254 255 } 256 } 257 258 /* called under bridge lock */ 259 static int br_supersedes_port_info(struct net_bridge_port *p, struct br_config_bpdu *bpdu) 260 { 261 int t; 262 263 t = memcmp(&bpdu->root, &p->designated_root, 8); 264 if (t < 0) 265 return 1; 266 else if (t > 0) 267 return 0; 268 269 if (bpdu->root_path_cost < p->designated_cost) 270 return 1; 271 else if (bpdu->root_path_cost > p->designated_cost) 272 return 0; 273 274 t = memcmp(&bpdu->bridge_id, &p->designated_bridge, 8); 275 if (t < 0) 276 return 1; 277 else if (t > 0) 278 return 0; 279 280 if (memcmp(&bpdu->bridge_id, &p->br->bridge_id, 8)) 281 return 1; 282 283 if (bpdu->port_id <= p->designated_port) 284 return 1; 285 286 return 0; 287 } 288 289 /* called under bridge lock */ 290 static inline void br_topology_change_acknowledged(struct net_bridge *br) 291 { 292 br->topology_change_detected = 0; 293 del_timer(&br->tcn_timer); 294 } 295 296 /* called under bridge lock */ 297 void br_topology_change_detection(struct net_bridge *br) 298 { 299 int isroot = br_is_root_bridge(br); 300 301 pr_info("%s: topology change detected, %s\n", br->dev->name, 302 isroot ? "propagating" : "sending tcn bpdu"); 303 304 if (isroot) { 305 br->topology_change = 1; 306 mod_timer(&br->topology_change_timer, jiffies 307 + br->bridge_forward_delay + br->bridge_max_age); 308 } else if (!br->topology_change_detected) { 309 br_transmit_tcn(br); 310 mod_timer(&br->tcn_timer, jiffies + br->bridge_hello_time); 311 } 312 313 br->topology_change_detected = 1; 314 } 315 316 /* called under bridge lock */ 317 void br_config_bpdu_generation(struct net_bridge *br) 318 { 319 struct net_bridge_port *p; 320 321 list_for_each_entry(p, &br->port_list, list) { 322 if (p->state != BR_STATE_DISABLED && 323 br_is_designated_port(p)) 324 br_transmit_config(p); 325 } 326 } 327 328 /* called under bridge lock */ 329 static inline void br_reply(struct net_bridge_port *p) 330 { 331 br_transmit_config(p); 332 } 333 334 /* called under bridge lock */ 335 void br_configuration_update(struct net_bridge *br) 336 { 337 br_root_selection(br); 338 br_designated_port_selection(br); 339 } 340 341 /* called under bridge lock */ 342 void br_become_designated_port(struct net_bridge_port *p) 343 { 344 struct net_bridge *br; 345 346 br = p->br; 347 p->designated_root = br->designated_root; 348 p->designated_cost = br->root_path_cost; 349 p->designated_bridge = br->bridge_id; 350 p->designated_port = p->port_id; 351 } 352 353 354 /* called under bridge lock */ 355 static void br_make_blocking(struct net_bridge_port *p) 356 { 357 if (p->state != BR_STATE_DISABLED && 358 p->state != BR_STATE_BLOCKING) { 359 if (p->state == BR_STATE_FORWARDING || 360 p->state == BR_STATE_LEARNING) 361 br_topology_change_detection(p->br); 362 363 p->state = BR_STATE_BLOCKING; 364 br_log_state(p); 365 del_timer(&p->forward_delay_timer); 366 } 367 } 368 369 /* called under bridge lock */ 370 static void br_make_forwarding(struct net_bridge_port *p) 371 { 372 if (p->state == BR_STATE_BLOCKING) { 373 if (p->br->stp_enabled) { 374 p->state = BR_STATE_LISTENING; 375 } else { 376 p->state = BR_STATE_LEARNING; 377 } 378 br_log_state(p); 379 mod_timer(&p->forward_delay_timer, jiffies + p->br->forward_delay); } 380 } 381 382 /* called under bridge lock */ 383 void br_port_state_selection(struct net_bridge *br) 384 { 385 struct net_bridge_port *p; 386 387 list_for_each_entry(p, &br->port_list, list) { 388 if (p->state != BR_STATE_DISABLED) { 389 if (p->port_no == br->root_port) { 390 p->config_pending = 0; 391 p->topology_change_ack = 0; 392 br_make_forwarding(p); 393 } else if (br_is_designated_port(p)) { 394 del_timer(&p->message_age_timer); 395 br_make_forwarding(p); 396 } else { 397 p->config_pending = 0; 398 p->topology_change_ack = 0; 399 br_make_blocking(p); 400 } 401 } 402 403 } 404 } 405 406 /* called under bridge lock */ 407 static inline void br_topology_change_acknowledge(struct net_bridge_port *p) 408 { 409 p->topology_change_ack = 1; 410 br_transmit_config(p); 411 } 412 413 /* called under bridge lock */ 414 void br_received_config_bpdu(struct net_bridge_port *p, struct br_config_bpdu *bpdu) 415 { 416 struct net_bridge *br; 417 int was_root; 418 419 br = p->br; 420 was_root = br_is_root_bridge(br); 421 422 if (br_supersedes_port_info(p, bpdu)) { 423 br_record_config_information(p, bpdu); 424 br_configuration_update(br); 425 br_port_state_selection(br); 426 427 if (!br_is_root_bridge(br) && was_root) { 428 del_timer(&br->hello_timer); 429 if (br->topology_change_detected) { 430 del_timer(&br->topology_change_timer); 431 br_transmit_tcn(br); 432 433 mod_timer(&br->tcn_timer, 434 jiffies + br->bridge_hello_time); 435 } 436 } 437 438 if (p->port_no == br->root_port) { 439 br_record_config_timeout_values(br, bpdu); 440 br_config_bpdu_generation(br); 441 if (bpdu->topology_change_ack) 442 br_topology_change_acknowledged(br); 443 } 444 } else if (br_is_designated_port(p)) { 445 br_reply(p); 446 } 447 } 448 449 /* called under bridge lock */ 450 void br_received_tcn_bpdu(struct net_bridge_port *p) 451 { 452 if (br_is_designated_port(p)) { 453 pr_info("%s: received tcn bpdu on port %i(%s)\n", 454 p->br->dev->name, p->port_no, p->dev->name); 455 456 br_topology_change_detection(p->br); 457 br_topology_change_acknowledge(p); 458 } 459 } 460