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.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 static const char *br_port_state_names[] = {
  22         [BR_STATE_DISABLED] = "disabled",
  23         [BR_STATE_LISTENING] = "listening",
  24         [BR_STATE_LEARNING] = "learning",
  25         [BR_STATE_FORWARDING] = "forwarding",
  26         [BR_STATE_BLOCKING] = "blocking",
  27 };
  28
  29 void br_log_state(const struct net_bridge_port *p)
  30 {
  31         pr_info("%s: port %d(%s) entering %s state\n",
  32                 p->br->dev->name, p->port_no, p->dev->name,
  33                 br_port_state_names[p->state]);
  34
  35 }
  36
  37 /* called under bridge lock */
  38 struct net_bridge_port *br_get_port(struct net_bridge *br, u16 port_no)
  39 {
  40         struct net_bridge_port *p;
  41
  42         list_for_each_entry_rcu(p, &br->port_list, list) {
  43                 if (p->port_no == port_no)
  44                         return p;
  45         }
  46
  47         return NULL;
  48 }
  49
  50 /* called under bridge lock */
  51 static int br_should_become_root_port(const struct net_bridge_port *p,
  52                                       u16 root_port)
  53 {
  54         struct net_bridge *br;
  55         struct net_bridge_port *rp;
  56         int t;
  57
  58         br = p->br;
  59         if (p->state == BR_STATE_DISABLED ||
  60             br_is_designated_port(p))
  61                 return 0;
  62
  63         if (memcmp(&br->bridge_id, &p->designated_root, 8) <= 0)
  64                 return 0;
  65
  66         if (!root_port)
  67                 return 1;
  68
  69         rp = br_get_port(br, root_port);
  70
  71         t = memcmp(&p->designated_root, &rp->designated_root, 8);
  72         if (t < 0)
  73                 return 1;
  74         else if (t > 0)
  75                 return 0;
  76
  77         if (p->designated_cost + p->path_cost <
  78             rp->designated_cost + rp->path_cost)
  79                 return 1;
  80         else if (p->designated_cost + p->path_cost >
  81                  rp->designated_cost + rp->path_cost)
  82                 return 0;
  83
  84         t = memcmp(&p->designated_bridge, &rp->designated_bridge, 8);
  85         if (t < 0)
  86                 return 1;
  87         else if (t > 0)
  88                 return 0;
  89
  90         if (p->designated_port < rp->designated_port)
  91                 return 1;
  92         else if (p->designated_port > rp->designated_port)
  93                 return 0;
  94
  95         if (p->port_id < rp->port_id)
  96                 return 1;
  97
  98         return 0;
  99 }
 100
 101 /* called under bridge lock */
 102 static void br_root_selection(struct net_bridge *br)
 103 {
 104         struct net_bridge_port *p;
 105         u16 root_port = 0;
 106
 107         list_for_each_entry(p, &br->port_list, list) {
 108                 if (br_should_become_root_port(p, root_port))
 109                         root_port = p->port_no;
 110
 111         }
 112
 113         br->root_port = root_port;
 114
 115         if (!root_port) {
 116                 br->designated_root = br->bridge_id;
 117                 br->root_path_cost = 0;
 118         } else {
 119                 p = br_get_port(br, root_port);
 120                 br->designated_root = p->designated_root;
 121                 br->root_path_cost = p->designated_cost + p->path_cost;
 122         }
 123 }
 124
 125 /* called under bridge lock */
 126 void br_become_root_bridge(struct net_bridge *br)
 127 {
 128         br->max_age = br->bridge_max_age;
 129         br->hello_time = br->bridge_hello_time;
 130         br->forward_delay = br->bridge_forward_delay;
 131         br_topology_change_detection(br);
 132         del_timer(&br->tcn_timer);
 133
 134         if (br->dev->flags & IFF_UP) {
 135                 br_config_bpdu_generation(br);
 136                 mod_timer(&br->hello_timer, jiffies + br->hello_time);
 137         }
 138 }
 139
 140 /* called under bridge lock */
 141 void br_transmit_config(struct net_bridge_port *p)
 142 {
 143         struct br_config_bpdu bpdu;
 144         struct net_bridge *br;
 145
 146
 147         if (timer_pending(&p->hold_timer)) {
 148                 p->config_pending = 1;
 149                 return;
 150         }
 151
 152         br = p->br;
 153
 154         bpdu.topology_change = br->topology_change;
 155         bpdu.topology_change_ack = p->topology_change_ack;
 156         bpdu.root = br->designated_root;
 157         bpdu.root_path_cost = br->root_path_cost;
 158         bpdu.bridge_id = br->bridge_id;
 159         bpdu.port_id = p->port_id;
 160         bpdu.message_age = 0;
 161         if (!br_is_root_bridge(br)) {
 162                 struct net_bridge_port *root
 163                         = br_get_port(br, br->root_port);
 164                 bpdu.max_age = root->message_age_timer.expires - jiffies;
 165
 166                 if (bpdu.max_age <= 0) bpdu.max_age = 1;
 167         }
 168         bpdu.max_age = br->max_age;
 169         bpdu.hello_time = br->hello_time;
 170         bpdu.forward_delay = br->forward_delay;
 171
 172         br_send_config_bpdu(p, &bpdu);
 173
 174         p->topology_change_ack = 0;
 175         p->config_pending = 0;
 176
 177         mod_timer(&p->hold_timer, jiffies + BR_HOLD_TIME);
 178 }
 179
 180 /* called under bridge lock */
 181 static inline void br_record_config_information(struct net_bridge_port *p,
 182                                                 const struct br_config_bpdu *bpdu)
 183 {
 184         p->designated_root = bpdu->root;
 185         p->designated_cost = bpdu->root_path_cost;
 186         p->designated_bridge = bpdu->bridge_id;
 187         p->designated_port = bpdu->port_id;
 188
 189         mod_timer(&p->message_age_timer, jiffies
 190                   + (p->br->max_age - bpdu->message_age));
 191 }
 192
 193 /* called under bridge lock */
 194 static inline void br_record_config_timeout_values(struct net_bridge *br,
 195                                             const 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(const 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         list_for_each_entry(p, &br->port_list, list) {
 245                 if (p->state != BR_STATE_DISABLED &&
 246                     br_should_become_designated_port(p))
 247                         br_become_designated_port(p);
 248
 249         }
 250 }
 251
 252 /* called under bridge lock */
 253 static int br_supersedes_port_info(struct net_bridge_port *p, struct br_config_bpdu *bpdu)
 254 {
 255         int t;
 256
 257         t = memcmp(&bpdu->root, &p->designated_root, 8);
 258         if (t < 0)
 259                 return 1;
 260         else if (t > 0)
 261                 return 0;
 262
 263         if (bpdu->root_path_cost < p->designated_cost)
 264                 return 1;
 265         else if (bpdu->root_path_cost > p->designated_cost)
 266                 return 0;
 267
 268         t = memcmp(&bpdu->bridge_id, &p->designated_bridge, 8);
 269         if (t < 0)
 270                 return 1;
 271         else if (t > 0)
 272                 return 0;
 273
 274         if (memcmp(&bpdu->bridge_id, &p->br->bridge_id, 8))
 275                 return 1;
 276
 277         if (bpdu->port_id <= p->designated_port)
 278                 return 1;
 279
 280         return 0;
 281 }
 282
 283 /* called under bridge lock */
 284 static inline void br_topology_change_acknowledged(struct net_bridge *br)
 285 {
 286         br->topology_change_detected = 0;
 287         del_timer(&br->tcn_timer);
 288 }
 289
 290 /* called under bridge lock */
 291 void br_topology_change_detection(struct net_bridge *br)
 292 {
 293         int isroot = br_is_root_bridge(br);
 294
 295         pr_info("%s: topology change detected, %s\n", br->dev->name,
 296                 isroot ? "propgating" : "sending tcn bpdu");
 297
 298         if (isroot) {
 299                 br->topology_change = 1;
 300                 mod_timer(&br->topology_change_timer, jiffies
 301                           + br->bridge_forward_delay + br->bridge_max_age);
 302         } else if (!br->topology_change_detected) {
 303                 br_transmit_tcn(br);
 304                 mod_timer(&br->tcn_timer, jiffies + br->bridge_hello_time);
 305         }
 306
 307         br->topology_change_detected = 1;
 308 }
 309
 310 /* called under bridge lock */
 311 void br_config_bpdu_generation(struct net_bridge *br)
 312 {
 313         struct net_bridge_port *p;
 314
 315         list_for_each_entry(p, &br->port_list, list) {
 316                 if (p->state != BR_STATE_DISABLED &&
 317                     br_is_designated_port(p))
 318                         br_transmit_config(p);
 319         }
 320 }
 321
 322 /* called under bridge lock */
 323 static inline void br_reply(struct net_bridge_port *p)
 324 {
 325         br_transmit_config(p);
 326 }
 327
 328 /* called under bridge lock */
 329 void br_configuration_update(struct net_bridge *br)
 330 {
 331         br_root_selection(br);
 332         br_designated_port_selection(br);
 333 }
 334
 335 /* called under bridge lock */
 336 void br_become_designated_port(struct net_bridge_port *p)
 337 {
 338         struct net_bridge *br;
 339
 340         br = p->br;
 341         p->designated_root = br->designated_root;
 342         p->designated_cost = br->root_path_cost;
 343         p->designated_bridge = br->bridge_id;
 344         p->designated_port = p->port_id;
 345 }
 346
 347
 348 /* called under bridge lock */
 349 static void br_make_blocking(struct net_bridge_port *p)
 350 {
 351         if (p->state != BR_STATE_DISABLED &&
 352             p->state != BR_STATE_BLOCKING) {
 353                 if (p->state == BR_STATE_FORWARDING ||
 354                     p->state == BR_STATE_LEARNING)
 355                         br_topology_change_detection(p->br);
 356
 357                 p->state = BR_STATE_BLOCKING;
 358                 br_log_state(p);
 359                 del_timer(&p->forward_delay_timer);
 360         }
 361 }
 362
 363 /* called under bridge lock */
 364 static void br_make_forwarding(struct net_bridge_port *p)
 365 {
 366         if (p->state == BR_STATE_BLOCKING) {
 367                 if (p->br->stp_enabled) {
 368                         p->state = BR_STATE_LISTENING;
 369                 } else {
 370                         p->state = BR_STATE_LEARNING;
 371                 }
 372                 br_log_state(p);
 373                 mod_timer(&p->forward_delay_timer, jiffies + p->br->forward_delay);     }
 374 }
 375
 376 /* called under bridge lock */
 377 void br_port_state_selection(struct net_bridge *br)
 378 {
 379         struct net_bridge_port *p;
 380
 381         list_for_each_entry(p, &br->port_list, list) {
 382                 if (p->state != BR_STATE_DISABLED) {
 383                         if (p->port_no == br->root_port) {
 384                                 p->config_pending = 0;
 385                                 p->topology_change_ack = 0;
 386                                 br_make_forwarding(p);
 387                         } else if (br_is_designated_port(p)) {
 388                                 del_timer(&p->message_age_timer);
 389                                 br_make_forwarding(p);
 390                         } else {
 391                                 p->config_pending = 0;
 392                                 p->topology_change_ack = 0;
 393                                 br_make_blocking(p);
 394                         }
 395                 }
 396
 397         }
 398 }
 399
 400 /* called under bridge lock */
 401 static inline void br_topology_change_acknowledge(struct net_bridge_port *p)
 402 {
 403         p->topology_change_ack = 1;
 404         br_transmit_config(p);
 405 }
 406
 407 /* called under bridge lock */
 408 void br_received_config_bpdu(struct net_bridge_port *p, struct br_config_bpdu *bpdu)
 409 {
 410         struct net_bridge *br;
 411         int was_root;
 412
 413         br = p->br;
 414         was_root = br_is_root_bridge(br);
 415
 416         if (br_supersedes_port_info(p, bpdu)) {
 417                 br_record_config_information(p, bpdu);
 418                 br_configuration_update(br);
 419                 br_port_state_selection(br);
 420
 421                 if (!br_is_root_bridge(br) && was_root) {
 422                         del_timer(&br->hello_timer);
 423                         if (br->topology_change_detected) {
 424                                 del_timer(&br->topology_change_timer);
 425                                 br_transmit_tcn(br);
 426
 427                                 mod_timer(&br->tcn_timer,
 428                                           jiffies + br->bridge_hello_time);
 429                         }
 430                 }
 431
 432                 if (p->port_no == br->root_port) {
 433                         br_record_config_timeout_values(br, bpdu);
 434                         br_config_bpdu_generation(br);
 435                         if (bpdu->topology_change_ack)
 436                                 br_topology_change_acknowledged(br);
 437                 }
 438         } else if (br_is_designated_port(p)) {
 439                 br_reply(p);
 440         }
 441 }
 442
 443 /* called under bridge lock */
 444 void br_received_tcn_bpdu(struct net_bridge_port *p)
 445 {
 446         if (br_is_designated_port(p)) {
 447                 pr_info("%s: received tcn bpdu on port %i(%s)\n",
 448                        p->br->dev->name, p->port_no, p->dev->name);
 449
 450                 br_topology_change_detection(p->br);
 451                 br_topology_change_acknowledge(p);
 452         }
 453 }