net/bridge/br_stp.c

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