lib/rstp.c

   1 /*
   2  * Copyright (c) 2011-2014 M3S, Srl - Italy
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 /*
  18  * Rapid Spanning Tree Protocol (IEEE 802.1D-2004) public interface.
  19  *
  20  * Authors:
  21  *         Martino Fornasa <mf@fornasa.it>
  22  *         Daniele Venturino <daniele.venturino@m3s.it>
  23  *
  24  * References to IEEE 802.1D-2004 standard are enclosed in square brackets.
  25  * E.g. [17.3], [Table 17-1], etc.
  26  *
  27  */
  28
  29 #include <config.h>
  30
  31 #include "rstp.h"
  32 #include "rstp-common.h"
  33 #include "rstp-state-machines.h"
  34 #include <arpa/inet.h>
  35 #include <inttypes.h>
  36 #include <netinet/in.h>
  37 #include <stdlib.h>
  38 #include <sys/types.h>
  39 #include "byte-order.h"
  40 #include "connectivity.h"
  41 #include "ofpbuf.h"
  42 #include "ofproto/ofproto.h"
  43 #include "packets.h"
  44 #include "seq.h"
  45 #include "unixctl.h"
  46 #include "util.h"
  47 #include "vlog.h"
  48
  49 VLOG_DEFINE_THIS_MODULE(rstp);
  50
  51 static struct ovs_mutex mutex;
  52 static struct list all_rstps__ = LIST_INITIALIZER(&all_rstps__);
  53 static struct list *const all_rstps OVS_GUARDED_BY(mutex) = &all_rstps__;
  54
  55 /* Internal use only */
  56 static void set_port_id__(struct rstp_port *);
  57 static void update_port_enabled__(struct rstp_port *);
  58 static void set_bridge_priority__(struct rstp *);
  59 static void reinitialize_rstp__(struct rstp *);
  60 static bool is_port_number_available__(struct rstp *, int, struct rstp_port *);
  61 static uint16_t rstp_first_free_number__(struct rstp *, struct rstp_port *);
  62 static void rstp_initialize_port_defaults__(struct rstp_port *);
  63 static void reinitialize_port__(struct rstp_port *);
  64
  65 const char *
  66 rstp_state_name(enum rstp_state state)
  67 {
  68     switch (state) {
  69     case RSTP_DISABLED:
  70         return "Disabled";
  71     case RSTP_LEARNING:
  72         return "Learning";
  73     case RSTP_FORWARDING:
  74         return "Forwarding";
  75     case RSTP_DISCARDING:
  76         return "Discarding";
  77     default:
  78         return "Unknown";
  79     }
  80 }
  81
  82 const char *
  83 rstp_port_role_name(enum rstp_port_role role)
  84 {
  85     switch (role) {
  86     case ROLE_ROOT:
  87         return "Root";
  88     case ROLE_DESIGNATED:
  89         return "Designated";
  90     case ROLE_ALTERNATE:
  91         return "Alternate";
  92     case ROLE_BACKUP:
  93         return "Backup";
  94     case ROLE_DISABLED:
  95         return "Disabled";
  96     default:
  97         return "Unknown";
  98     }
  99 }
 100
 101 /* Caller has to hold a reference to prevent 'rstp' from being deleted
 102  * while we are taking a new reference. */
 103 struct rstp *
 104 rstp_ref(struct rstp *rstp)
 105 {
 106     if (rstp) {
 107         ovs_refcount_ref(&rstp->ref_cnt);
 108     }
 109     return rstp;
 110 }
 111
 112 /* Frees RSTP struct */
 113 void
 114 rstp_unref(struct rstp *rstp)
 115 {
 116     if (rstp && ovs_refcount_unref(&rstp->ref_cnt) == 1) {
 117         ovs_mutex_lock(&mutex);
 118         if (rstp->ports_count > 0) {
 119             struct rstp_port *p;
 120
 121             LIST_FOR_EACH (p, node, &rstp->ports) {
 122                 rstp_delete_port(p);
 123             }
 124         }
 125         list_remove(&rstp->node);
 126         ovs_mutex_unlock(&mutex);
 127         free(rstp->name);
 128         free(rstp);
 129     }
 130 }
 131
 132 /* Returns the port number.  Mutex is needed to guard against
 133  * concurrent reinitialization (which can temporarily clear the
 134  * port_number). */
 135 int
 136 rstp_port_number(const struct rstp_port *p)
 137 {
 138     int number;
 139
 140     ovs_mutex_lock(&mutex);
 141     number = p->port_number;
 142     ovs_mutex_unlock(&mutex);
 143     return number;
 144 }
 145
 146 static void rstp_unixctl_tcn(struct unixctl_conn *, int argc,
 147                              const char *argv[], void *aux);
 148
 149 /* Decrements the State Machines' timers. */
 150 void
 151 rstp_tick_timers(struct rstp *rstp)
 152 {
 153     ovs_mutex_lock(&mutex);
 154     decrease_rstp_port_timers(rstp);
 155     ovs_mutex_unlock(&mutex);
 156 }
 157
 158 /* Processes an incoming BPDU. */
 159 void
 160 rstp_received_bpdu(struct rstp_port *p, const void *bpdu, size_t bpdu_size)
 161 {
 162     ovs_mutex_lock(&mutex);
 163     process_received_bpdu(p, bpdu, bpdu_size);
 164     ovs_mutex_unlock(&mutex);
 165 }
 166
 167 void
 168 rstp_init(void)
 169 {
 170     unixctl_command_register("rstp/tcn", "[bridge]", 0, 1, rstp_unixctl_tcn,
 171                              NULL);
 172 }
 173
 174 /* Creates and returns a new RSTP instance that initially has no ports. */
 175 struct rstp *
 176 rstp_create(const char *name, rstp_identifier bridge_address,
 177             void (*send_bpdu)(struct ofpbuf *bpdu, int port_no, void *aux),
 178             void *aux)
 179 {
 180     static struct ovsthread_once once = OVSTHREAD_ONCE_INITIALIZER;
 181     struct rstp *rstp;
 182
 183     VLOG_DBG("Creating RSTP instance");
 184     if (ovsthread_once_start(&once)) {
 185         ovs_mutex_init_recursive(&mutex);
 186         ovsthread_once_done(&once);
 187     }
 188
 189     rstp = xzalloc(sizeof *rstp);
 190     rstp->name = xstrdup(name);
 191     /* Set bridge address. */
 192     rstp_set_bridge_address(rstp, bridge_address);
 193     /* Set default parameters values. */
 194     rstp_set_bridge_priority(rstp, RSTP_DEFAULT_PRIORITY);
 195     rstp_set_bridge_ageing_time(rstp, RSTP_DEFAULT_AGEING_TIME);
 196     rstp_set_bridge_force_protocol_version(rstp, FPV_DEFAULT);
 197     rstp_set_bridge_forward_delay(rstp, RSTP_DEFAULT_BRIDGE_FORWARD_DELAY);
 198     rstp_set_bridge_hello_time(rstp);
 199     rstp_set_bridge_max_age(rstp, RSTP_DEFAULT_BRIDGE_MAX_AGE);
 200     rstp_set_bridge_migrate_time(rstp);
 201     rstp_set_bridge_transmit_hold_count(rstp,
 202                                         RSTP_DEFAULT_TRANSMIT_HOLD_COUNT);
 203     rstp_set_bridge_times(rstp, RSTP_DEFAULT_BRIDGE_FORWARD_DELAY,
 204                           RSTP_BRIDGE_HELLO_TIME, RSTP_DEFAULT_BRIDGE_MAX_AGE,
 205                           0);
 206     rstp->send_bpdu = send_bpdu;
 207     rstp->aux = aux;
 208     rstp->changes = false;
 209     rstp->begin = true;
 210
 211     /* Initialize the ports list. */
 212     list_init(&rstp->ports);
 213     ovs_refcount_init(&rstp->ref_cnt);
 214
 215     ovs_mutex_lock(&mutex);
 216     list_push_back(all_rstps, &rstp->node);
 217     ovs_mutex_unlock(&mutex);
 218
 219     VLOG_DBG("RSTP instance creation done");
 220     return rstp;
 221 }
 222
 223 /* Called by rstp_set_bridge_address() and rstp_set_bridge_priority(),
 224  * it updates the bridge priority vector according to the values passed by
 225  * those setters.
 226  */
 227 static void
 228 set_bridge_priority__(struct rstp *rstp)
 229     OVS_REQUIRES(mutex)
 230 {
 231     rstp->bridge_priority.root_bridge_id = rstp->bridge_identifier;
 232     rstp->bridge_priority.designated_bridge_id = rstp->bridge_identifier;
 233     VLOG_DBG("%s: new bridge identifier: "RSTP_ID_FMT"", rstp->name,
 234              RSTP_ID_ARGS(rstp->bridge_identifier));
 235
 236     /* [17.13] When the bridge address changes, recalculates all priority
 237      * vectors.
 238      */
 239     if (rstp->ports_count > 0) {
 240         struct rstp_port *p;
 241
 242         LIST_FOR_EACH (p, node, &rstp->ports) {
 243             p->selected = false;
 244             p->reselect = true;
 245         }
 246     }
 247     rstp->changes = true;
 248     updt_roles_tree(rstp);
 249 }
 250
 251 /* Sets the bridge address. */
 252 void
 253 rstp_set_bridge_address(struct rstp *rstp, rstp_identifier bridge_address)
 254 {
 255     VLOG_DBG("%s: set bridge address to: "RSTP_ID_FMT"", rstp->name,
 256              RSTP_ID_ARGS(bridge_address));
 257
 258     ovs_mutex_lock(&mutex);
 259     rstp->address = bridge_address;
 260     rstp->bridge_identifier = bridge_address;
 261     set_bridge_priority__(rstp);
 262     ovs_mutex_unlock(&mutex);
 263 }
 264
 265 const char *
 266 rstp_get_name(const struct rstp *rstp)
 267 {
 268     char *name;
 269
 270     ovs_mutex_lock(&mutex);
 271     name = rstp->name;
 272     ovs_mutex_unlock(&mutex);
 273     return name;
 274 }
 275
 276 rstp_identifier
 277 rstp_get_bridge_id(const struct rstp *rstp)
 278 {
 279     rstp_identifier bridge_id;
 280
 281     ovs_mutex_lock(&mutex);
 282     bridge_id = rstp->bridge_identifier;
 283     ovs_mutex_unlock(&mutex);
 284     return bridge_id;
 285 }
 286
 287 /* Sets the bridge priority. */
 288 void
 289 rstp_set_bridge_priority(struct rstp *rstp, int new_priority)
 290 {
 291     new_priority = ROUND_DOWN(new_priority, RSTP_PRIORITY_STEP);
 292
 293     if (new_priority >= RSTP_MIN_PRIORITY
 294         && new_priority <= RSTP_MAX_PRIORITY) {
 295         VLOG_DBG("%s: set bridge priority to %d", rstp->name, new_priority);
 296
 297         ovs_mutex_lock(&mutex);
 298         rstp->priority = new_priority;
 299         rstp->bridge_identifier &= 0x0000ffffffffffffULL;
 300         rstp->bridge_identifier |= (uint64_t)new_priority << 48;
 301         set_bridge_priority__(rstp);
 302         ovs_mutex_unlock(&mutex);
 303     }
 304 }
 305
 306 /* Sets the bridge ageing time. */
 307 void
 308 rstp_set_bridge_ageing_time(struct rstp *rstp, int new_ageing_time)
 309 {
 310     if (new_ageing_time >= RSTP_MIN_AGEING_TIME
 311         && new_ageing_time <= RSTP_MAX_AGEING_TIME) {
 312         VLOG_DBG("%s: set ageing time to %d", rstp->name, new_ageing_time);
 313
 314         ovs_mutex_lock(&mutex);
 315         rstp->ageing_time = new_ageing_time;
 316         ovs_mutex_unlock(&mutex);
 317     }
 318 }
 319
 320 /* Reinitializes RSTP when switching from RSTP mode to STP mode
 321  * or vice versa.
 322  */
 323 static void
 324 reinitialize_rstp__(struct rstp *rstp)
 325     OVS_REQUIRES(mutex)
 326 {
 327     struct rstp temp;
 328     static struct list ports;
 329
 330     /* Copy rstp in temp */
 331     temp = *rstp;
 332     ports = rstp->ports;
 333
 334     /* stop and clear rstp */
 335     memset(rstp, 0, sizeof(struct rstp));
 336
 337     /* Initialize rstp. */
 338     rstp->name = temp.name;
 339     /* Set bridge address. */
 340     rstp_set_bridge_address(rstp, temp.address);
 341     /* Set default parameters values. */
 342     rstp_set_bridge_priority(rstp, RSTP_DEFAULT_PRIORITY);
 343     rstp_set_bridge_ageing_time(rstp, RSTP_DEFAULT_AGEING_TIME);
 344     rstp_set_bridge_forward_delay(rstp, RSTP_DEFAULT_BRIDGE_FORWARD_DELAY);
 345     rstp_set_bridge_hello_time(rstp);
 346     rstp_set_bridge_max_age(rstp, RSTP_DEFAULT_BRIDGE_MAX_AGE);
 347     rstp_set_bridge_migrate_time(rstp);
 348     rstp_set_bridge_transmit_hold_count(rstp,
 349                                         RSTP_DEFAULT_TRANSMIT_HOLD_COUNT);
 350     rstp_set_bridge_times(rstp, RSTP_DEFAULT_BRIDGE_FORWARD_DELAY,
 351                           RSTP_BRIDGE_HELLO_TIME, RSTP_DEFAULT_BRIDGE_MAX_AGE,
 352                           0);
 353
 354     rstp->send_bpdu = temp.send_bpdu;
 355     rstp->aux = temp.aux;
 356     rstp->node = temp.node;
 357     rstp->changes = false;
 358     rstp->begin = true;
 359     rstp->ports = ports;
 360     rstp->ports_count = temp.ports_count;
 361
 362     if (rstp->ports_count > 0) {
 363         struct rstp_port *p;
 364
 365         LIST_FOR_EACH (p, node, &rstp->ports) {
 366             reinitialize_port__(p);
 367         }
 368     }
 369     rstp->ref_cnt = temp.ref_cnt;
 370 }
 371
 372 /* Sets the force protocol version parameter. */
 373 void
 374 rstp_set_bridge_force_protocol_version(struct rstp *rstp,
 375                 enum rstp_force_protocol_version new_force_protocol_version)
 376 {
 377     if (new_force_protocol_version != rstp->force_protocol_version &&
 378             (new_force_protocol_version == FPV_STP_COMPATIBILITY ||
 379              new_force_protocol_version == FPV_DEFAULT)) {
 380         VLOG_DBG("%s: set bridge Force Protocol Version to %d", rstp->name,
 381                  new_force_protocol_version);
 382         ovs_mutex_lock(&mutex);
 383         /* [17.13] The Spanning Tree Protocol Entity shall be reinitialized,
 384          * as specified by the assertion of BEGIN (17.18.1) in the state
 385          * machine specification.
 386          */
 387         reinitialize_rstp__(rstp);
 388         rstp->force_protocol_version = new_force_protocol_version;
 389         if (rstp->force_protocol_version < 2) {
 390             rstp->stp_version = true;
 391             rstp->rstp_version = false;
 392         } else {
 393             rstp->stp_version = false;
 394             rstp->rstp_version = true;
 395         }
 396         rstp->changes = true;
 397         move_rstp(rstp);
 398         ovs_mutex_unlock(&mutex);
 399     }
 400 }
 401
 402 /* Sets the bridge Hello Time parameter. */
 403 void
 404 rstp_set_bridge_hello_time(struct rstp *rstp)
 405 {
 406     VLOG_DBG("%s: set RSTP Hello Time to %d", rstp->name,
 407              RSTP_BRIDGE_HELLO_TIME);
 408     /* 2 is the only acceptable value. */
 409     ovs_mutex_lock(&mutex);
 410     rstp->bridge_hello_time = RSTP_BRIDGE_HELLO_TIME;
 411     ovs_mutex_unlock(&mutex);
 412 }
 413
 414 /* Sets the bridge max age parameter. */
 415 void
 416 rstp_set_bridge_max_age(struct rstp *rstp, int new_max_age)
 417 {
 418     if (new_max_age >= RSTP_MIN_BRIDGE_MAX_AGE &&
 419         new_max_age <= RSTP_MAX_BRIDGE_MAX_AGE) {
 420         /* [17.13] */
 421         if ((2 * (rstp->bridge_forward_delay - 1) >= new_max_age)
 422             && (new_max_age >= 2 * rstp->bridge_hello_time)) {
 423             VLOG_DBG("%s: set RSTP bridge Max Age to %d", rstp->name,
 424                      new_max_age);
 425             ovs_mutex_lock(&mutex);
 426             rstp->bridge_max_age = new_max_age;
 427             rstp->bridge_times.max_age = new_max_age;
 428             ovs_mutex_unlock(&mutex);
 429         }
 430     }
 431 }
 432
 433 /* Sets the bridge forward delay parameter. */
 434 void
 435 rstp_set_bridge_forward_delay(struct rstp *rstp, int new_forward_delay)
 436 {
 437     if (new_forward_delay >= RSTP_MIN_BRIDGE_FORWARD_DELAY
 438         && new_forward_delay <= RSTP_MAX_BRIDGE_FORWARD_DELAY) {
 439         if (2 * (new_forward_delay - 1) >= rstp->bridge_max_age) {
 440             VLOG_DBG("%s: set RSTP Forward Delay to %d", rstp->name,
 441                      new_forward_delay);
 442             ovs_mutex_lock(&mutex);
 443             rstp->bridge_forward_delay = new_forward_delay;
 444             rstp->bridge_times.forward_delay = new_forward_delay;
 445             ovs_mutex_unlock(&mutex);
 446         }
 447     }
 448 }
 449
 450 /* Sets the bridge transmit hold count parameter. */
 451 void
 452 rstp_set_bridge_transmit_hold_count(struct rstp *rstp,
 453                                     int new_transmit_hold_count)
 454 {
 455     struct rstp_port *p;
 456
 457     if (new_transmit_hold_count >= RSTP_MIN_TRANSMIT_HOLD_COUNT
 458         && new_transmit_hold_count <= RSTP_MAX_TRANSMIT_HOLD_COUNT) {
 459         VLOG_DBG("%s: set RSTP Transmit Hold Count to %d", rstp->name,
 460                  new_transmit_hold_count);
 461         /* Resetting txCount on all ports [17.13]. */
 462         ovs_mutex_lock(&mutex);
 463         rstp->transmit_hold_count = new_transmit_hold_count;
 464         if (rstp->ports_count > 0) {
 465             LIST_FOR_EACH (p, node, &rstp->ports) {
 466                 p->tx_count = 0;
 467             }
 468         }
 469         ovs_mutex_unlock(&mutex);
 470     }
 471 }
 472
 473 /* Sets the bridge migrate time parameter. */
 474 void
 475 rstp_set_bridge_migrate_time(struct rstp *rstp)
 476 {
 477     VLOG_DBG("%s: set RSTP Migrate Time to %d", rstp->name,
 478              RSTP_MIGRATE_TIME);
 479     /* 3 is the only acceptable value */
 480     ovs_mutex_lock(&mutex);
 481     rstp->migrate_time = RSTP_MIGRATE_TIME;
 482     ovs_mutex_unlock(&mutex);
 483 }
 484
 485 /* Sets the bridge times. */
 486 void
 487 rstp_set_bridge_times(struct rstp *rstp, int new_forward_delay,
 488                       int new_hello_time, int new_max_age,
 489                       int new_message_age)
 490 {
 491     VLOG_DBG("%s: set RSTP times to (%d, %d, %d, %d)", rstp->name,
 492              new_forward_delay, new_hello_time, new_max_age, new_message_age);
 493     if (new_forward_delay >= RSTP_MIN_BRIDGE_FORWARD_DELAY
 494         && new_forward_delay <= RSTP_MAX_BRIDGE_FORWARD_DELAY) {
 495         rstp->bridge_times.forward_delay = new_forward_delay;
 496     }
 497     if (new_hello_time == RSTP_BRIDGE_HELLO_TIME) {
 498         rstp->bridge_times.hello_time = new_hello_time;
 499     }
 500     if (new_max_age >= RSTP_MIN_BRIDGE_MAX_AGE
 501         && new_max_age <= RSTP_MAX_BRIDGE_MAX_AGE) {
 502         rstp->bridge_times.max_age = new_max_age;
 503     }
 504     rstp->bridge_times.message_age = new_message_age;
 505 }
 506
 507 /* Sets the port id, it is called by rstp_port_set_port_number() or
 508  * rstp_port_set_priority().
 509  */
 510 static void
 511 set_port_id__(struct rstp_port *p)
 512 {
 513     struct rstp *rstp;
 514
 515     rstp = p->rstp;
 516     /* [9.2.7] Port identifier. */
 517     p->port_id = p->port_number | (p->priority << 8);
 518     VLOG_DBG("%s: new RSTP port id "RSTP_PORT_ID_FMT"", rstp->name,
 519              p->port_id);
 520 }
 521
 522 /* Sets the port priority. */
 523 void
 524 rstp_port_set_priority(struct rstp_port *rstp_port, int new_port_priority)
 525 {
 526     struct rstp *rstp;
 527
 528     rstp = rstp_port->rstp;
 529     if (new_port_priority >= RSTP_MIN_PORT_PRIORITY
 530         && new_port_priority <= RSTP_MAX_PORT_PRIORITY) {
 531         VLOG_DBG("%s, port %u: set RSTP port priority to %d", rstp->name,
 532                  rstp_port->port_number, new_port_priority);
 533         ovs_mutex_lock(&mutex);
 534         new_port_priority -= new_port_priority % RSTP_STEP_PORT_PRIORITY;
 535         rstp_port->priority = new_port_priority;
 536         set_port_id__(rstp_port);
 537         rstp_port->selected = false;
 538         rstp_port->reselect = true;
 539         ovs_mutex_unlock(&mutex);
 540     }
 541 }
 542
 543 /* Checks if a port number is available. */
 544 static bool
 545 is_port_number_available__(struct rstp *rstp, int n, struct rstp_port *port)
 546 {
 547     if (n >= 1 && n <= RSTP_MAX_PORTS) {
 548         struct rstp_port *p = rstp_get_port(rstp, n);
 549
 550         return p == NULL || p == port;
 551     }
 552     return false;
 553 }
 554
 555 static uint16_t
 556 rstp_first_free_number__(struct rstp *rstp, struct rstp_port *rstp_port)
 557 {
 558     int free_number = 1;
 559
 560     ovs_mutex_lock(&mutex);
 561     while (free_number <= RSTP_MAX_PORTS) {
 562         if (is_port_number_available__(rstp, free_number, rstp_port)) {
 563             ovs_mutex_unlock(&mutex);
 564             return free_number;
 565         }
 566         free_number++;
 567     }
 568     ovs_mutex_unlock(&mutex);
 569     VLOG_DBG("%s, No free port number available.", rstp->name);
 570     return 0;
 571 }
 572
 573 /* Sets the port number. */
 574 void
 575 rstp_port_set_port_number(struct rstp_port *rstp_port,
 576                           uint16_t new_port_number)
 577 {
 578     struct rstp *rstp;
 579
 580     ovs_mutex_lock(&mutex);
 581     rstp = rstp_port->rstp;
 582     /* If new_port_number is available, use it, otherwise use the first free
 583      * available port number. */
 584     rstp_port->port_number =
 585         is_port_number_available__(rstp_port->rstp, new_port_number, rstp_port)
 586         ? new_port_number
 587         : rstp_first_free_number__(rstp, rstp_port);
 588
 589     set_port_id__(rstp_port);
 590     /* [17.13] is not clear. I suppose that a port number change
 591      * should trigger reselection like a port priority change. */
 592     rstp_port->selected = false;
 593     rstp_port->reselect = true;
 594     ovs_mutex_unlock(&mutex);
 595     VLOG_DBG("%s: set new RSTP port number %d", rstp->name,
 596              rstp_port->port_number);
 597 }
 598
 599 /* Converts the link speed to a port path cost [Table 17-3]. */
 600 uint32_t
 601 rstp_convert_speed_to_cost(unsigned int speed)
 602 {
 603     uint32_t value;
 604
 605     value = speed >= 10000000 ? 2 /* 10 Tb/s. */
 606           : speed >= 1000000 ? 20 /* 1 Tb/s. */
 607           : speed >= 100000 ? 200 /* 100 Gb/s. */
 608           : speed >= 10000 ? 2000 /* 10 Gb/s. */
 609           : speed >= 1000 ? 20000 /* 1 Gb/s. */
 610           : speed >= 100 ? 200000 /* 100 Mb/s. */
 611           : speed >= 10 ? 2000000 /* 10 Mb/s. */
 612           : speed >= 1 ? 20000000 /* 1 Mb/s. */
 613           : RSTP_DEFAULT_PORT_PATH_COST; /* 100 Mb/s. */
 614
 615     return value;
 616 }
 617
 618 /* Sets the port path cost. */
 619 void
 620 rstp_port_set_path_cost(struct rstp_port *rstp_port,
 621                         uint32_t new_port_path_cost)
 622 {
 623     if (new_port_path_cost >= RSTP_MIN_PORT_PATH_COST &&
 624             new_port_path_cost <= RSTP_MAX_PORT_PATH_COST) {
 625         struct rstp *rstp;
 626
 627         ovs_mutex_lock(&mutex);
 628         rstp = rstp_port->rstp;
 629         VLOG_DBG("%s, port %u, set RSTP port path cost to %d", rstp->name,
 630                  rstp_port->port_number, new_port_path_cost);
 631         rstp_port->port_path_cost = new_port_path_cost;
 632         rstp_port->selected = false;
 633         rstp_port->reselect = true;
 634         ovs_mutex_unlock(&mutex);
 635     }
 636 }
 637
 638 /* Gets the root path cost. */
 639 uint32_t
 640 rstp_get_root_path_cost(const struct rstp *rstp)
 641 {
 642     uint32_t cost;
 643
 644     ovs_mutex_lock(&mutex);
 645     cost = rstp->root_priority.root_path_cost;
 646     ovs_mutex_unlock(&mutex);
 647     return cost;
 648 }
 649
 650 /* Returns true if something has happened to 'rstp' which necessitates
 651  * flushing the client's MAC learning table.
 652  */
 653 bool
 654 rstp_check_and_reset_fdb_flush(struct rstp *rstp)
 655 {
 656     bool needs_flush;
 657     struct rstp_port *p;
 658
 659     needs_flush = false;
 660
 661     ovs_mutex_lock(&mutex);
 662     if (rstp->ports_count > 0){
 663         LIST_FOR_EACH (p, node, &rstp->ports) {
 664             if (p->fdb_flush) {
 665                 needs_flush = true;
 666                 /* fdb_flush should be reset by the filtering database
 667                  * once the entries are removed if rstp_version is TRUE, and
 668                  * immediately if stp_version is TRUE.*/
 669                 p->fdb_flush = false;
 670             }
 671         }
 672     }
 673     ovs_mutex_unlock(&mutex);
 674     return needs_flush;
 675 }
 676
 677 /* Finds a port whose state has changed.  If successful, stores the port whose
 678  * state changed in '*portp' and returns true.  If no port has changed, stores
 679  * NULL in '*portp' and returns false.
 680  *
 681  * XXX: This function is only called by the main thread, which is also the one
 682  * that creates and deletes ports.  Otherwise this function is not thread safe,
 683  * as the returned '*portp' could become stale before it is referenced by the
 684  * caller. */
 685 bool
 686 rstp_get_changed_port(struct rstp *rstp, struct rstp_port **portp)
 687 {
 688     bool changed = false;
 689
 690     ovs_mutex_lock(&mutex);
 691     if (rstp->ports_count > 0) {
 692         struct rstp_port *p;
 693
 694         LIST_FOR_EACH (p, node, &rstp->ports) {
 695             if (p->state_changed) {
 696                 p->state_changed = false;
 697                 *portp = p;
 698                 changed = true;
 699                 ovs_mutex_unlock(&mutex);
 700                 return changed;
 701             }
 702         }
 703     }
 704     *portp = NULL;
 705     ovs_mutex_unlock(&mutex);
 706     return changed;
 707 }
 708
 709 /* Returns the port in 'rstp' with number 'port_number'.
 710  *
 711  * XXX: May only be called while concurrent deletion of ports is excluded. */
 712 struct rstp_port *
 713 rstp_get_port(struct rstp *rstp, int port_number)
 714 {
 715     struct rstp_port *port;
 716
 717     ovs_mutex_lock(&mutex);
 718     if (rstp->ports_count > 0) {
 719         LIST_FOR_EACH (port, node, &rstp->ports) {
 720             if (port->port_number == port_number) {
 721                 ovs_mutex_unlock(&mutex);
 722                 return port;
 723             }
 724         }
 725     }
 726     ovs_mutex_unlock(&mutex);
 727     return NULL;
 728 }
 729
 730 /* Updates the port_enabled parameter. */
 731 static void
 732 update_port_enabled__(struct rstp_port *p)
 733     OVS_REQUIRES(mutex)
 734 {
 735     if (p->mac_operational && p->is_administrative_bridge_port
 736         == RSTP_ADMIN_BRIDGE_PORT_STATE_ENABLED) {
 737         p->port_enabled = true;
 738     } else {
 739         p->port_enabled = false;
 740     }
 741 }
 742
 743 /* Sets the port MAC_Operational parameter [6.4.2]. */
 744 void
 745 rstp_port_set_mac_operational(struct rstp_port *p, bool new_mac_operational)
 746 {
 747     struct rstp *rstp;
 748
 749     ovs_mutex_lock(&mutex);
 750     rstp = p->rstp;
 751     p->mac_operational = new_mac_operational;
 752     update_port_enabled__(p);
 753     rstp->changes = true;
 754     move_rstp(rstp);
 755     ovs_mutex_unlock(&mutex);
 756 }
 757
 758 /* Gets the port MAC_Operational parameter [6.4.2]. */
 759 bool
 760 rstp_port_get_mac_operational(struct rstp_port *p)
 761 {
 762     bool value;
 763
 764     ovs_mutex_lock(&mutex);
 765     value = p->mac_operational;
 766     ovs_mutex_unlock(&mutex);
 767     return value;
 768 }
 769
 770 /* Sets the port Administrative Bridge Port parameter. */
 771 void
 772 rstp_port_set_administrative_bridge_port(struct rstp_port *p,
 773                                          uint8_t new_admin_port_state)
 774 {
 775     if (new_admin_port_state == RSTP_ADMIN_BRIDGE_PORT_STATE_DISABLED
 776         || new_admin_port_state == RSTP_ADMIN_BRIDGE_PORT_STATE_ENABLED) {
 777         ovs_mutex_lock(&mutex);
 778         p->is_administrative_bridge_port = new_admin_port_state;
 779         update_port_enabled__(p);
 780         ovs_mutex_unlock(&mutex);
 781     }
 782 }
 783
 784 /* Sets the port oper_point_to_point_mac parameter. */
 785 void
 786 rstp_port_set_oper_point_to_point_mac(struct rstp_port *p,
 787                                       uint8_t new_oper_p2p_mac)
 788 {
 789     if (new_oper_p2p_mac == RSTP_OPER_P2P_MAC_STATE_DISABLED
 790         || new_oper_p2p_mac == RSTP_OPER_P2P_MAC_STATE_ENABLED) {
 791         ovs_mutex_lock(&mutex);
 792         p->oper_point_to_point_mac = new_oper_p2p_mac;
 793         update_port_enabled__(p);
 794         ovs_mutex_unlock(&mutex);
 795     }
 796 }
 797
 798 /* Initializes a port with the defaults values for its parameters. */
 799 static void
 800 rstp_initialize_port_defaults__(struct rstp_port *p)
 801     OVS_REQUIRES(mutex)
 802 {
 803     rstp_port_set_administrative_bridge_port(p,
 804         RSTP_ADMIN_BRIDGE_PORT_STATE_ENABLED);
 805     rstp_port_set_oper_point_to_point_mac(p, 1);
 806     rstp_port_set_path_cost(p, RSTP_DEFAULT_PORT_PATH_COST);
 807     rstp_port_set_auto_edge(p, true);
 808
 809     /* Initialize state machines. */
 810     p->port_receive_sm_state = PORT_RECEIVE_SM_INIT;
 811     p->port_protocol_migration_sm_state = PORT_PROTOCOL_MIGRATION_SM_INIT;
 812     p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_INIT;
 813     p->port_transmit_sm_state = PORT_TRANSMIT_SM_INIT;
 814     p->port_information_sm_state = PORT_INFORMATION_SM_INIT;
 815     p->port_role_transition_sm_state = PORT_ROLE_TRANSITION_SM_INIT;
 816     p->port_state_transition_sm_state = PORT_STATE_TRANSITION_SM_INIT;
 817     p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_INIT;
 818     p->uptime = 0;
 819
 820 }
 821
 822 static void
 823 reinitialize_port__(struct rstp_port *p)
 824     OVS_REQUIRES(mutex)
 825 {
 826     struct rstp_port temp_port;
 827     struct rstp *rstp;
 828
 829     rstp = p->rstp;
 830     temp_port = *p;
 831     memset(p, 0, sizeof(struct rstp_port));
 832     p->rstp = rstp;
 833     p->node = temp_port.node;
 834     p->aux = temp_port.aux;
 835     p->port_number = temp_port.port_number;
 836     p->port_priority = temp_port.port_priority;
 837     p->port_id = temp_port.port_id;
 838     p->rstp_state = RSTP_DISCARDING;
 839
 840     rstp_initialize_port_defaults__(p);
 841
 842     VLOG_DBG("%s: RSTP port "RSTP_PORT_ID_FMT" reinitialized.", rstp->name,
 843              p->port_id);
 844 }
 845
 846 void
 847 reinitialize_port(struct rstp_port *p)
 848 {
 849     ovs_mutex_lock(&mutex);
 850     reinitialize_port__(p);
 851     ovs_mutex_unlock(&mutex);
 852 }
 853
 854 /* Sets the port state. */
 855 void
 856 rstp_port_set_state(struct rstp_port *p, enum rstp_state state)
 857 OVS_REQUIRES(mutex)
 858 {
 859     struct rstp *rstp;
 860
 861     rstp = p->rstp;
 862     VLOG_DBG("%s, port %u: set RSTP port state %s -> %s", rstp->name,
 863              p->port_number,
 864              rstp_state_name(p->rstp_state), rstp_state_name(state));
 865
 866     if (state != p->rstp_state && !p->state_changed) {
 867         p->state_changed = true;
 868         seq_change(connectivity_seq_get());
 869     }
 870     p->rstp_state = state;
 871 }
 872
 873 /* Adds a RSTP port. */
 874 struct rstp_port *
 875 rstp_add_port(struct rstp *rstp)
 876 {
 877     struct rstp_port *p = xzalloc(sizeof *p);
 878
 879     ovs_mutex_lock(&mutex);
 880     p->rstp = rstp;
 881     rstp_port_set_priority(p, RSTP_DEFAULT_PORT_PRIORITY);
 882     rstp_port_set_port_number(p, 0);
 883     p->aux = NULL;
 884     rstp_initialize_port_defaults__(p);
 885     VLOG_DBG("%s: RSTP port "RSTP_PORT_ID_FMT" initialized.", rstp->name,
 886              p->port_id);
 887
 888     rstp_port_set_state(p, RSTP_DISCARDING);
 889     list_push_back(&rstp->ports, &p->node);
 890     rstp->ports_count++;
 891     rstp->changes = true;
 892     move_rstp(rstp);
 893     ovs_mutex_unlock(&mutex);
 894     VLOG_DBG("%s: added port "RSTP_PORT_ID_FMT"", rstp->name, p->port_id);
 895     return p;
 896 }
 897
 898 /* Deletes a RSTP port. */
 899 void
 900 rstp_delete_port(struct rstp_port *p)
 901 {
 902     struct rstp *rstp;
 903
 904     ovs_mutex_lock(&mutex);
 905     rstp = p->rstp;
 906     rstp_port_set_state(p, RSTP_DISABLED);
 907     list_remove(&p->node);
 908     rstp->ports_count--;
 909     VLOG_DBG("%s: removed port "RSTP_PORT_ID_FMT"", rstp->name, p->port_id);
 910     ovs_mutex_unlock(&mutex);
 911     free(p);
 912 }
 913
 914 /* Sets the port Admin Edge parameter. */
 915 void
 916 rstp_port_set_admin_edge(struct rstp_port *rstp_port, bool new_admin_edge)
 917 {
 918     if (rstp_port->admin_edge != new_admin_edge) {
 919         struct rstp *rstp;
 920
 921         ovs_mutex_lock(&mutex);
 922         rstp = rstp_port->rstp;
 923         VLOG_DBG("%s, port %u: set RSTP Admin Edge to %d", rstp->name,
 924                  rstp_port->port_number, new_admin_edge);
 925         rstp_port->admin_edge = new_admin_edge;
 926         ovs_mutex_unlock(&mutex);
 927     }
 928 }
 929
 930 /* Sets the port Auto Edge parameter. */
 931 void
 932 rstp_port_set_auto_edge(struct rstp_port *rstp_port, bool new_auto_edge)
 933 {
 934     if (rstp_port->auto_edge != new_auto_edge) {
 935         struct rstp *rstp;
 936
 937         ovs_mutex_lock(&mutex);
 938         rstp = rstp_port->rstp;
 939         VLOG_DBG("%s, port %u: set RSTP Auto Edge to %d", rstp->name,
 940                  rstp_port->port_number, new_auto_edge);
 941         rstp_port->auto_edge = new_auto_edge;
 942         ovs_mutex_unlock(&mutex);
 943     }
 944 }
 945
 946 /* Sets the port mcheck parameter.
 947  * [17.19.13] May be set by management to force the Port Protocol Migration
 948  * state machine to transmit RST BPDUs for a MigrateTime (17.13.9) period, to
 949  * test whether all STP Bridges (17.4) on the attached LAN have been removed
 950  * and the Port can continue to transmit RSTP BPDUs. Setting mcheck has no
 951  * effect if stpVersion (17.20.12) is TRUE, i.e., the Bridge is operating in
 952  * STP Compatibility. mode.
 953  */
 954 void
 955 rstp_port_set_mcheck(struct rstp_port *rstp_port, bool new_mcheck)
 956 {
 957     struct rstp *rstp;
 958
 959     ovs_mutex_lock(&mutex);
 960     rstp = rstp_port->rstp;
 961     if (new_mcheck == true && rstp_port->rstp->force_protocol_version >= 2) {
 962         rstp_port->mcheck = true;
 963     }
 964     VLOG_DBG("%s, port %u: set RSTP mcheck to %d", rstp->name,
 965              rstp_port->port_number, new_mcheck);
 966     ovs_mutex_unlock(&mutex);
 967 }
 968
 969 /* Returns the designated bridge id. */
 970 rstp_identifier
 971 rstp_get_designated_id(const struct rstp *rstp)
 972 {
 973     rstp_identifier designated_id;
 974
 975     ovs_mutex_lock(&mutex);
 976     designated_id = rstp->root_priority.designated_bridge_id;
 977     ovs_mutex_unlock(&mutex);
 978
 979     return designated_id;
 980 }
 981
 982 /* Returns the root bridge id. */
 983 rstp_identifier
 984 rstp_get_root_id(const struct rstp *rstp)
 985 {
 986     rstp_identifier root_id;
 987
 988     ovs_mutex_lock(&mutex);
 989     root_id = rstp->root_priority.root_bridge_id;
 990     ovs_mutex_unlock(&mutex);
 991
 992     return root_id;
 993 }
 994
 995 /* Returns the designated port id. */
 996 uint16_t
 997 rstp_get_designated_port_id(const struct rstp *rstp)
 998 {
 999     uint16_t designated_port_id;
1000
1001     ovs_mutex_lock(&mutex);
1002     designated_port_id = rstp->root_priority.designated_port_id;
1003     ovs_mutex_unlock(&mutex);
1004
1005     return designated_port_id;
1006 }
1007
1008 /* Return the bridge port id. */
1009 uint16_t
1010 rstp_get_bridge_port_id(const struct rstp *rstp)
1011 {
1012     uint16_t bridge_port_id;
1013
1014     ovs_mutex_lock(&mutex);
1015     bridge_port_id = rstp->root_priority.bridge_port_id;
1016     ovs_mutex_unlock(&mutex);
1017
1018     return bridge_port_id;
1019 }
1020
1021 /* Returns true if the bridge believes to the be root of the spanning tree,
1022  * false otherwise.
1023  */
1024 bool
1025 rstp_is_root_bridge(const struct rstp *rstp)
1026 {
1027     bool is_root;
1028
1029     ovs_mutex_lock(&mutex);
1030     is_root = rstp->bridge_identifier ==
1031                 rstp->root_priority.designated_bridge_id;
1032     ovs_mutex_unlock(&mutex);
1033
1034     return is_root;
1035 }
1036
1037 /* Returns the bridge ID of the bridge currently believed to be the root. */
1038 rstp_identifier
1039 rstp_get_designated_root(const struct rstp *rstp)
1040 {
1041     rstp_identifier designated_root;
1042
1043     ovs_mutex_lock(&mutex);
1044     designated_root = rstp->root_priority.designated_bridge_id;
1045     ovs_mutex_unlock(&mutex);
1046
1047     return designated_root;
1048 }
1049
1050 /* Returns the port connecting 'rstp' to the root bridge, or a null pointer if
1051  * there is no such port.
1052  */
1053 struct rstp_port *
1054 rstp_get_root_port(struct rstp *rstp)
1055 {
1056     struct rstp_port *p;
1057
1058     ovs_mutex_lock(&mutex);
1059     if (rstp->ports_count > 0){
1060         LIST_FOR_EACH (p, node, &rstp->ports) {
1061             if (p->port_id == rstp->root_port_id) {
1062                 ovs_mutex_unlock(&mutex);
1063                 return p;
1064             }
1065         }
1066     }
1067     ovs_mutex_unlock(&mutex);
1068     return NULL;
1069 }
1070
1071 /* Returns the port ID for 'p'. */
1072 uint16_t
1073 rstp_port_get_id(const struct rstp_port *p)
1074 {
1075     uint16_t port_id;
1076
1077     ovs_mutex_lock(&mutex);
1078     port_id = p->port_id;
1079     ovs_mutex_unlock(&mutex);
1080
1081     return port_id;
1082 }
1083
1084 /* Returns the state of port 'p'. */
1085 enum rstp_state
1086 rstp_port_get_state(const struct rstp_port *p)
1087 {
1088     enum rstp_state state;
1089
1090     ovs_mutex_lock(&mutex);
1091     state = p->rstp_state;
1092     ovs_mutex_unlock(&mutex);
1093
1094     return state;
1095 }
1096
1097 /* Returns the role of port 'p'. */
1098 enum rstp_port_role
1099 rstp_port_get_role(const struct rstp_port *p)
1100 {
1101     enum rstp_port_role role;
1102
1103     ovs_mutex_lock(&mutex);
1104     role = p->role;
1105     ovs_mutex_unlock(&mutex);
1106
1107     return role;
1108 }
1109
1110 /* Retrieves BPDU transmit and receive counts for 'p'. */
1111 void
1112 rstp_port_get_counts(const struct rstp_port *p,
1113         int *tx_count, int *rx_count, int *error_count, int *uptime)
1114 {
1115     ovs_mutex_lock(&mutex);
1116     *tx_count = p->tx_count;
1117     *rx_count = p->rx_rstp_bpdu_cnt;
1118     *error_count = p->error_count;
1119     *uptime = p->uptime;
1120     ovs_mutex_unlock(&mutex);
1121 }
1122
1123 void
1124 rstp_port_set_aux(struct rstp_port *p, void *aux)
1125 {
1126     ovs_mutex_lock(&mutex);
1127     p->aux = aux;
1128     ovs_mutex_unlock(&mutex);
1129 }
1130
1131 void *
1132 rstp_port_get_aux(struct rstp_port *p)
1133 {
1134     void *aux;
1135
1136     ovs_mutex_lock(&mutex);
1137     aux = p->aux;
1138     ovs_mutex_unlock(&mutex);
1139
1140     return aux;
1141 }
1142
1143 /* Unixctl. */
1144 static struct rstp *
1145 rstp_find(const char *name)
1146     OVS_REQUIRES(mutex)
1147 {
1148     struct rstp *rstp;
1149
1150     LIST_FOR_EACH (rstp, node, all_rstps) {
1151         if (!strcmp(rstp->name, name)) {
1152             return rstp;
1153         }
1154     }
1155     return NULL;
1156 }
1157
1158 static void
1159 rstp_unixctl_tcn(struct unixctl_conn *conn, int argc,
1160                  const char *argv[], void *aux OVS_UNUSED)
1161 {
1162     ovs_mutex_lock(&mutex);
1163     if (argc > 1) {
1164         struct rstp *rstp = rstp_find(argv[1]);
1165         if (!rstp) {
1166             unixctl_command_reply_error(conn, "No such RSTP object");
1167             goto out;
1168         }
1169         rstp->changes = true;
1170         move_rstp(rstp);
1171     } else {
1172         struct rstp *rstp;
1173         LIST_FOR_EACH (rstp, node, all_rstps) {
1174             rstp->changes = true;
1175             move_rstp(rstp);
1176         }
1177     }
1178     unixctl_command_reply(conn, "OK");
1179
1180 out:
1181     ovs_mutex_unlock(&mutex);
1182 }