lib/rstp.c

   1 /*
   2  * Copyright (c) 2011-2015 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  *         Carlo Andreotti <c.andreotti@m3s.it>
  24  *
  25  * References to IEEE 802.1D-2004 standard are enclosed in square brackets.
  26  * E.g. [17.3], [Table 17-1], etc.
  27  *
  28  */
  29
  30 #include <config.h>
  31
  32 #include "rstp.h"
  33 #include "rstp-common.h"
  34 #include "rstp-state-machines.h"
  35 #include <sys/types.h>
  36 #include <netinet/in.h>
  37 #include <arpa/inet.h>
  38 #include <inttypes.h>
  39 #include <stdlib.h>
  40 #include "byte-order.h"
  41 #include "connectivity.h"
  42 #include "openvswitch/ofpbuf.h"
  43 #include "ofproto/ofproto.h"
  44 #include "dp-packet.h"
  45 #include "packets.h"
  46 #include "seq.h"
  47 #include "unixctl.h"
  48 #include "util.h"
  49 #include "openvswitch/vlog.h"
  50
  51 VLOG_DEFINE_THIS_MODULE(rstp);
  52
  53 struct ovs_mutex rstp_mutex = OVS_MUTEX_INITIALIZER;
  54
  55 static struct ovs_list all_rstps__ = OVS_LIST_INITIALIZER(&all_rstps__);
  56 static struct ovs_list *const all_rstps OVS_GUARDED_BY(rstp_mutex) = &all_rstps__;
  57
  58 /* Internal use only. */
  59 static void rstp_set_bridge_address__(struct rstp *, rstp_identifier)
  60     OVS_REQUIRES(rstp_mutex);
  61 static void rstp_set_bridge_priority__(struct rstp *, int new_priority)
  62     OVS_REQUIRES(rstp_mutex);
  63 static void rstp_set_bridge_ageing_time__(struct rstp *, int new_ageing_time)
  64     OVS_REQUIRES(rstp_mutex);
  65 static void rstp_set_bridge_force_protocol_version__(struct rstp *,
  66                                                      enum rstp_force_protocol_version)
  67     OVS_REQUIRES(rstp_mutex);
  68 static void rstp_set_bridge_hello_time__(struct rstp *)
  69     OVS_REQUIRES(rstp_mutex);
  70 static void rstp_set_bridge_max_age__(struct rstp *, int new_max_age)
  71     OVS_REQUIRES(rstp_mutex);
  72 static void rstp_set_bridge_forward_delay__(struct rstp *, int new_forward_delay)
  73     OVS_REQUIRES(rstp_mutex);
  74 static void rstp_set_bridge_transmit_hold_count__(struct rstp *,
  75                                                   int new_transmit_hold_count)
  76     OVS_REQUIRES(rstp_mutex);
  77 static void rstp_set_bridge_migrate_time__(struct rstp *)
  78     OVS_REQUIRES(rstp_mutex);
  79 static void rstp_set_bridge_times__(struct rstp *, int new_forward_delay,
  80                                     int new_hello_time, int new_max_age,
  81                                     int new_message_age)
  82     OVS_REQUIRES(rstp_mutex);
  83
  84 static struct rstp_port *rstp_get_port__(struct rstp *rstp,
  85                                          uint16_t port_number)
  86     OVS_REQUIRES(rstp_mutex);
  87 static void set_port_id__(struct rstp_port *)
  88     OVS_REQUIRES(rstp_mutex);
  89 static void update_port_enabled__(struct rstp_port *)
  90     OVS_REQUIRES(rstp_mutex);
  91 static void set_bridge_priority__(struct rstp *)
  92     OVS_REQUIRES(rstp_mutex);
  93 static void reinitialize_rstp__(struct rstp *)
  94     OVS_REQUIRES(rstp_mutex);
  95 static bool is_port_number_available__(struct rstp *, int, struct rstp_port *)
  96     OVS_REQUIRES(rstp_mutex);
  97 static uint16_t rstp_first_free_number__(struct rstp *, struct rstp_port *)
  98     OVS_REQUIRES(rstp_mutex);
  99 static void rstp_initialize_port_defaults__(struct rstp_port *)
 100     OVS_REQUIRES(rstp_mutex);
 101 static void rstp_port_set_priority__(struct rstp_port *, int priority)
 102     OVS_REQUIRES(rstp_mutex);
 103 static void rstp_port_set_port_number__(struct rstp_port *,
 104                                         uint16_t port_number)
 105     OVS_REQUIRES(rstp_mutex);
 106 static void rstp_port_set_path_cost__(struct rstp_port *, uint32_t path_cost)
 107     OVS_REQUIRES(rstp_mutex);
 108 static void rstp_port_set_administrative_bridge_port__(struct rstp_port *,
 109                                                        uint8_t admin_port_state,
 110                                                        bool initializing)
 111     OVS_REQUIRES(rstp_mutex);
 112 static void rstp_port_set_admin_edge__(struct rstp_port *, bool admin_edge)
 113     OVS_REQUIRES(rstp_mutex);
 114 static void rstp_port_set_auto_edge__(struct rstp_port *, bool auto_edge)
 115     OVS_REQUIRES(rstp_mutex);
 116 static void rstp_port_set_admin_point_to_point_mac__(struct rstp_port *,
 117         enum rstp_admin_point_to_point_mac_state admin_p2p_mac_state)
 118     OVS_REQUIRES(rstp_mutex);
 119 static void rstp_port_set_mcheck__(struct rstp_port *, bool mcheck)
 120     OVS_REQUIRES(rstp_mutex);
 121 static void reinitialize_port__(struct rstp_port *p)
 122     OVS_REQUIRES(rstp_mutex);
 123 static bool rstp_is_root_bridge__(const struct rstp *rstp)
 124     OVS_REQUIRES(rstp_mutex);
 125 static uint32_t rstp_get_root_path_cost__(const struct rstp *rstp)
 126     OVS_REQUIRES(rstp_mutex);
 127 static struct rstp_port *rstp_get_root_port__(const struct rstp *rstp)
 128     OVS_REQUIRES(rstp_mutex);
 129 static rstp_identifier rstp_get_root_id__(const struct rstp *rstp)
 130     OVS_REQUIRES(rstp_mutex);
 131 static void rstp_unixctl_tcn(struct unixctl_conn *, int argc,
 132                              const char *argv[], void *aux);
 133 static void rstp_unixctl_show(struct unixctl_conn *, int argc,
 134                               const char *argv[], void *aux);
 135
 136 const char *
 137 rstp_state_name(enum rstp_state state)
 138 {
 139     switch (state) {
 140     case RSTP_DISABLED:
 141         return "Disabled";
 142     case RSTP_LEARNING:
 143         return "Learning";
 144     case RSTP_FORWARDING:
 145         return "Forwarding";
 146     case RSTP_DISCARDING:
 147         return "Discarding";
 148     default:
 149         return "Unknown";
 150     }
 151 }
 152
 153 const char *
 154 rstp_port_role_name(enum rstp_port_role role)
 155 {
 156     switch (role) {
 157     case ROLE_ROOT:
 158         return "Root";
 159     case ROLE_DESIGNATED:
 160         return "Designated";
 161     case ROLE_ALTERNATE:
 162         return "Alternate";
 163     case ROLE_BACKUP:
 164         return "Backup";
 165     case ROLE_DISABLED:
 166         return "Disabled";
 167     default:
 168         return "Unknown";
 169     }
 170 }
 171
 172 /* Caller has to hold a reference to prevent 'rstp' from being deleted
 173  * while taking a new reference. */
 174 struct rstp *
 175 rstp_ref(struct rstp *rstp)
 176     OVS_EXCLUDED(rstp_mutex)
 177 {
 178     if (rstp) {
 179         ovs_refcount_ref(&rstp->ref_cnt);
 180     }
 181     return rstp;
 182 }
 183
 184 /* Frees RSTP struct when reference count reaches zero. */
 185 void
 186 rstp_unref(struct rstp *rstp)
 187     OVS_EXCLUDED(rstp_mutex)
 188 {
 189     if (rstp && ovs_refcount_unref_relaxed(&rstp->ref_cnt) == 1) {
 190         ovs_mutex_lock(&rstp_mutex);
 191
 192         /* Each RSTP port points back to struct rstp without holding a
 193          * reference for that pointer.  This is OK as we never move
 194          * ports from one bridge to another, and holders always
 195          * release their ports before releasing the bridge.  This
 196          * means that there should be not ports at this time. */
 197         ovs_assert(hmap_is_empty(&rstp->ports));
 198
 199         ovs_list_remove(&rstp->node);
 200         ovs_mutex_unlock(&rstp_mutex);
 201         hmap_destroy(&rstp->ports);
 202         free(rstp->name);
 203         free(rstp);
 204     }
 205 }
 206
 207 /* Returns the port number.  Mutex is needed to guard against
 208  * concurrent reinitialization (which can temporarily clear the
 209  * port_number). */
 210 int
 211 rstp_port_get_number(const struct rstp_port *p)
 212     OVS_EXCLUDED(rstp_mutex)
 213 {
 214     int number;
 215
 216     ovs_mutex_lock(&rstp_mutex);
 217     number = p->port_number;
 218     ovs_mutex_unlock(&rstp_mutex);
 219
 220     return number;
 221 }
 222
 223 /* Decrements the State Machines' timers. */
 224 void
 225 rstp_tick_timers(struct rstp *rstp)
 226     OVS_EXCLUDED(rstp_mutex)
 227 {
 228     ovs_mutex_lock(&rstp_mutex);
 229     decrease_rstp_port_timers__(rstp);
 230     ovs_mutex_unlock(&rstp_mutex);
 231 }
 232
 233 /* Processes an incoming BPDU. */
 234 void
 235 rstp_port_received_bpdu(struct rstp_port *rp, const void *bpdu,
 236                         size_t bpdu_size)
 237     OVS_EXCLUDED(rstp_mutex)
 238 {
 239     ovs_mutex_lock(&rstp_mutex);
 240     /* Only process packets on ports that have RSTP enabled. */
 241     if (rp && rp->rstp_state != RSTP_DISABLED) {
 242         process_received_bpdu__(rp, bpdu, bpdu_size);
 243     }
 244     ovs_mutex_unlock(&rstp_mutex);
 245 }
 246
 247 void
 248 rstp_init(void)
 249     OVS_EXCLUDED(rstp_mutex)
 250 {
 251     unixctl_command_register("rstp/tcn", "[bridge]", 0, 1, rstp_unixctl_tcn,
 252                              NULL);
 253     unixctl_command_register("rstp/show", "[bridge]", 0, 1, rstp_unixctl_show,
 254                              NULL);
 255 }
 256
 257 /* Creates and returns a new RSTP instance that initially has no ports. */
 258 struct rstp *
 259 rstp_create(const char *name, rstp_identifier bridge_address,
 260             void (*send_bpdu)(struct dp_packet *bpdu, void *port_aux,
 261                               void *rstp_aux),
 262             void *aux)
 263     OVS_EXCLUDED(rstp_mutex)
 264 {
 265     struct rstp *rstp;
 266
 267     VLOG_DBG("Creating RSTP instance");
 268
 269     rstp = xzalloc(sizeof *rstp);
 270     rstp->name = xstrdup(name);
 271
 272     /* Initialize the ports map before calling any setters,
 273      * so that the state machines will see an empty ports map. */
 274     hmap_init(&rstp->ports);
 275
 276     ovs_mutex_lock(&rstp_mutex);
 277     /* Set bridge address. */
 278     rstp_set_bridge_address__(rstp, bridge_address);
 279     /* Set default parameters values. */
 280     rstp_set_bridge_priority__(rstp, RSTP_DEFAULT_PRIORITY);
 281     rstp_set_bridge_ageing_time__(rstp, RSTP_DEFAULT_AGEING_TIME);
 282     rstp_set_bridge_force_protocol_version__(rstp, FPV_DEFAULT);
 283     rstp_set_bridge_forward_delay__(rstp, RSTP_DEFAULT_BRIDGE_FORWARD_DELAY);
 284     rstp_set_bridge_hello_time__(rstp);
 285     rstp_set_bridge_max_age__(rstp, RSTP_DEFAULT_BRIDGE_MAX_AGE);
 286     rstp_set_bridge_migrate_time__(rstp);
 287     rstp_set_bridge_transmit_hold_count__(rstp,
 288                                           RSTP_DEFAULT_TRANSMIT_HOLD_COUNT);
 289     rstp_set_bridge_times__(rstp, RSTP_DEFAULT_BRIDGE_FORWARD_DELAY,
 290                             RSTP_BRIDGE_HELLO_TIME,
 291                             RSTP_DEFAULT_BRIDGE_MAX_AGE, 0);
 292     rstp->send_bpdu = send_bpdu;
 293     rstp->aux = aux;
 294     rstp->changes = false;
 295     rstp->begin = true;
 296     rstp->old_root_aux = NULL;
 297     rstp->new_root_aux = NULL;
 298
 299     ovs_refcount_init(&rstp->ref_cnt);
 300
 301     ovs_list_push_back(all_rstps, &rstp->node);
 302     ovs_mutex_unlock(&rstp_mutex);
 303
 304     VLOG_DBG("RSTP instance creation done");
 305     return rstp;
 306 }
 307
 308 /* Called by rstp_set_bridge_address() and rstp_set_bridge_priority(),
 309  * it updates the bridge priority vector according to the values passed by
 310  * those setters.
 311  */
 312 static void
 313 set_bridge_priority__(struct rstp *rstp)
 314     OVS_REQUIRES(rstp_mutex)
 315 {
 316     struct rstp_port *p;
 317
 318     rstp->bridge_priority.root_bridge_id = rstp->bridge_identifier;
 319     rstp->bridge_priority.designated_bridge_id = rstp->bridge_identifier;
 320     VLOG_DBG("%s: new bridge identifier: "RSTP_ID_FMT"", rstp->name,
 321              RSTP_ID_ARGS(rstp->bridge_identifier));
 322
 323     /* [17.13] When the bridge address changes, recalculates all priority
 324      * vectors.
 325      */
 326     HMAP_FOR_EACH (p, node, &rstp->ports) {
 327         p->selected = false;
 328         p->reselect = true;
 329     }
 330     rstp->changes = true;
 331     updt_roles_tree__(rstp);
 332 }
 333
 334 /* Sets the bridge address. */
 335 static void
 336 rstp_set_bridge_address__(struct rstp *rstp, rstp_identifier bridge_address)
 337     OVS_REQUIRES(rstp_mutex)
 338 {
 339     VLOG_DBG("%s: set bridge address to: "RSTP_ID_FMT"", rstp->name,
 340              RSTP_ID_ARGS(bridge_address));
 341     if (rstp->address != bridge_address) {
 342         rstp->address = bridge_address;
 343         rstp->bridge_identifier &= 0xffff000000000000ULL;
 344         rstp->bridge_identifier |= bridge_address;
 345         set_bridge_priority__(rstp);
 346     }
 347 }
 348
 349 /* Sets the bridge address. */
 350 void
 351 rstp_set_bridge_address(struct rstp *rstp, rstp_identifier bridge_address)
 352     OVS_EXCLUDED(rstp_mutex)
 353 {
 354     ovs_mutex_lock(&rstp_mutex);
 355     rstp_set_bridge_address__(rstp, bridge_address);
 356     ovs_mutex_unlock(&rstp_mutex);
 357 }
 358
 359 const char *
 360 rstp_get_name(const struct rstp *rstp)
 361     OVS_EXCLUDED(rstp_mutex)
 362 {
 363     char *name;
 364
 365     ovs_mutex_lock(&rstp_mutex);
 366     name = rstp->name;
 367     ovs_mutex_unlock(&rstp_mutex);
 368     return name;
 369 }
 370
 371 rstp_identifier
 372 rstp_get_bridge_id(const struct rstp *rstp)
 373     OVS_EXCLUDED(rstp_mutex)
 374 {
 375     rstp_identifier bridge_id;
 376
 377     ovs_mutex_lock(&rstp_mutex);
 378     bridge_id = rstp->bridge_identifier;
 379     ovs_mutex_unlock(&rstp_mutex);
 380
 381     return bridge_id;
 382 }
 383
 384 /* Sets the bridge priority. */
 385 static void
 386 rstp_set_bridge_priority__(struct rstp *rstp, int new_priority)
 387     OVS_REQUIRES(rstp_mutex)
 388 {
 389     new_priority = ROUND_DOWN(new_priority, RSTP_PRIORITY_STEP);
 390
 391     if (rstp->priority != new_priority
 392         && new_priority >= RSTP_MIN_PRIORITY
 393         && new_priority <= RSTP_MAX_PRIORITY) {
 394         VLOG_DBG("%s: set bridge priority to %d", rstp->name, new_priority);
 395
 396         rstp->priority = new_priority;
 397         rstp->bridge_identifier &= 0x0000ffffffffffffULL;
 398         rstp->bridge_identifier |= (uint64_t)new_priority << 48;
 399         set_bridge_priority__(rstp);
 400     }
 401 }
 402
 403 void
 404 rstp_set_bridge_priority(struct rstp *rstp, int new_priority)
 405     OVS_EXCLUDED(rstp_mutex)
 406 {
 407     ovs_mutex_lock(&rstp_mutex);
 408     rstp_set_bridge_priority__(rstp, new_priority);
 409     ovs_mutex_unlock(&rstp_mutex);
 410 }
 411
 412 /* Sets the bridge ageing time. */
 413 static void
 414 rstp_set_bridge_ageing_time__(struct rstp *rstp, int new_ageing_time)
 415     OVS_REQUIRES(rstp_mutex)
 416 {
 417     if (new_ageing_time >= RSTP_MIN_AGEING_TIME
 418         && new_ageing_time <= RSTP_MAX_AGEING_TIME) {
 419         VLOG_DBG("%s: set ageing time to %d", rstp->name, new_ageing_time);
 420
 421         rstp->ageing_time = new_ageing_time;
 422     }
 423 }
 424
 425 void
 426 rstp_set_bridge_ageing_time(struct rstp *rstp, int new_ageing_time)
 427     OVS_EXCLUDED(rstp_mutex)
 428 {
 429     ovs_mutex_lock(&rstp_mutex);
 430     rstp_set_bridge_ageing_time__(rstp, new_ageing_time);
 431     ovs_mutex_unlock(&rstp_mutex);
 432 }
 433
 434 /* Reinitializes RSTP when switching from RSTP mode to STP mode
 435  * or vice versa.
 436  */
 437 static void
 438 reinitialize_rstp__(struct rstp *rstp)
 439     OVS_REQUIRES(rstp_mutex)
 440 {
 441     struct rstp temp;
 442     static struct hmap ports;
 443     struct rstp_port *p;
 444
 445     /* Copy rstp in temp */
 446     temp = *rstp;
 447     ports = rstp->ports;
 448
 449     /* stop and clear rstp */
 450     memset(rstp, 0, sizeof(struct rstp));
 451
 452     /* Initialize rstp. */
 453     rstp->name = temp.name;
 454
 455     /* Initialize the ports hmap before calling any setters,
 456      * so that the state machines will see an empty ports list. */
 457     hmap_init(&rstp->ports);
 458
 459     /* Set bridge address. */
 460     rstp_set_bridge_address__(rstp, temp.address);
 461     /* Set default parameters values. */
 462     rstp_set_bridge_priority__(rstp, RSTP_DEFAULT_PRIORITY);
 463     rstp_set_bridge_ageing_time__(rstp, RSTP_DEFAULT_AGEING_TIME);
 464     rstp_set_bridge_forward_delay__(rstp, RSTP_DEFAULT_BRIDGE_FORWARD_DELAY);
 465     rstp_set_bridge_hello_time__(rstp);
 466     rstp_set_bridge_max_age__(rstp, RSTP_DEFAULT_BRIDGE_MAX_AGE);
 467     rstp_set_bridge_migrate_time__(rstp);
 468     rstp_set_bridge_transmit_hold_count__(rstp,
 469                                           RSTP_DEFAULT_TRANSMIT_HOLD_COUNT);
 470     rstp_set_bridge_times__(rstp, RSTP_DEFAULT_BRIDGE_FORWARD_DELAY,
 471                             RSTP_BRIDGE_HELLO_TIME,
 472                             RSTP_DEFAULT_BRIDGE_MAX_AGE, 0);
 473
 474     rstp->send_bpdu = temp.send_bpdu;
 475     rstp->aux = temp.aux;
 476     rstp->node = temp.node;
 477     rstp->changes = false;
 478     rstp->begin = true;
 479
 480     /* Restore ports. */
 481     rstp->ports = ports;
 482
 483     HMAP_FOR_EACH (p, node, &rstp->ports) {
 484         reinitialize_port__(p);
 485     }
 486
 487     rstp->ref_cnt = temp.ref_cnt;
 488 }
 489
 490 /* Sets the force protocol version parameter. */
 491 static void
 492 rstp_set_bridge_force_protocol_version__(struct rstp *rstp,
 493                 enum rstp_force_protocol_version new_force_protocol_version)
 494     OVS_REQUIRES(rstp_mutex)
 495 {
 496     if (new_force_protocol_version != rstp->force_protocol_version &&
 497             (new_force_protocol_version == FPV_STP_COMPATIBILITY ||
 498              new_force_protocol_version == FPV_DEFAULT)) {
 499         VLOG_DBG("%s: set bridge Force Protocol Version to %d", rstp->name,
 500                  new_force_protocol_version);
 501
 502         /* [17.13] The Spanning Tree Protocol Entity shall be reinitialized,
 503          * as specified by the assertion of BEGIN (17.18.1) in the state
 504          * machine specification.
 505          */
 506         reinitialize_rstp__(rstp);
 507         rstp->force_protocol_version = new_force_protocol_version;
 508         if (rstp->force_protocol_version < 2) {
 509             rstp->stp_version = true;
 510             rstp->rstp_version = false;
 511         } else {
 512             rstp->stp_version = false;
 513             rstp->rstp_version = true;
 514         }
 515         rstp->changes = true;
 516         move_rstp__(rstp);
 517     }
 518 }
 519
 520 void
 521 rstp_set_bridge_force_protocol_version(struct rstp *rstp,
 522                 enum rstp_force_protocol_version new_force_protocol_version)
 523     OVS_EXCLUDED(rstp_mutex)
 524 {
 525     ovs_mutex_lock(&rstp_mutex);
 526     rstp_set_bridge_force_protocol_version__(rstp, new_force_protocol_version);
 527     ovs_mutex_unlock(&rstp_mutex);
 528 }
 529
 530 /* Sets the bridge Hello Time parameter. */
 531 static void
 532 rstp_set_bridge_hello_time__(struct rstp *rstp)
 533     OVS_REQUIRES(rstp_mutex)
 534 {
 535     VLOG_DBG("%s: set RSTP Hello Time to %d", rstp->name,
 536              RSTP_BRIDGE_HELLO_TIME);
 537     /* 2 is the only acceptable value. */
 538     rstp->bridge_hello_time = RSTP_BRIDGE_HELLO_TIME;
 539 }
 540
 541 /* Sets the bridge max age parameter. */
 542 static void
 543 rstp_set_bridge_max_age__(struct rstp *rstp, int new_max_age)
 544     OVS_REQUIRES(rstp_mutex)
 545 {
 546     if (rstp->bridge_max_age != new_max_age
 547         && new_max_age >= RSTP_MIN_BRIDGE_MAX_AGE
 548         && new_max_age <= RSTP_MAX_BRIDGE_MAX_AGE) {
 549         /* [17.13] */
 550         if ((2 * (rstp->bridge_forward_delay - 1) >= new_max_age)
 551             && (new_max_age >= 2 * rstp->bridge_hello_time)) {
 552             VLOG_DBG("%s: set RSTP bridge Max Age to %d", rstp->name,
 553                      new_max_age);
 554
 555             rstp->bridge_max_age = new_max_age;
 556             rstp->bridge_times.max_age = new_max_age;
 557             rstp->changes = true;
 558             updt_roles_tree__(rstp);
 559         }
 560     }
 561 }
 562
 563 void
 564 rstp_set_bridge_max_age(struct rstp *rstp, int new_max_age)
 565     OVS_EXCLUDED(rstp_mutex)
 566 {
 567     ovs_mutex_lock(&rstp_mutex);
 568     rstp_set_bridge_max_age__(rstp, new_max_age);
 569     ovs_mutex_unlock(&rstp_mutex);
 570 }
 571
 572 /* Sets the bridge forward delay parameter. */
 573 static void
 574 rstp_set_bridge_forward_delay__(struct rstp *rstp, int new_forward_delay)
 575     OVS_REQUIRES(rstp_mutex)
 576 {
 577     if (rstp->bridge_forward_delay != new_forward_delay
 578             && new_forward_delay >= RSTP_MIN_BRIDGE_FORWARD_DELAY
 579             && new_forward_delay <= RSTP_MAX_BRIDGE_FORWARD_DELAY) {
 580         if (2 * (new_forward_delay - 1) >= rstp->bridge_max_age) {
 581             VLOG_DBG("%s: set RSTP Forward Delay to %d", rstp->name,
 582                      new_forward_delay);
 583             rstp->bridge_forward_delay = new_forward_delay;
 584             rstp->bridge_times.forward_delay = new_forward_delay;
 585             rstp->changes = true;
 586             updt_roles_tree__(rstp);
 587         }
 588     }
 589 }
 590
 591 void
 592 rstp_set_bridge_forward_delay(struct rstp *rstp, int new_forward_delay)
 593     OVS_EXCLUDED(rstp_mutex)
 594 {
 595     ovs_mutex_lock(&rstp_mutex);
 596     rstp_set_bridge_forward_delay__(rstp, new_forward_delay);
 597     ovs_mutex_unlock(&rstp_mutex);
 598 }
 599
 600 /* Sets the bridge transmit hold count parameter. */
 601 static void
 602 rstp_set_bridge_transmit_hold_count__(struct rstp *rstp,
 603                                       int new_transmit_hold_count)
 604     OVS_REQUIRES(rstp_mutex)
 605 {
 606     if (rstp->transmit_hold_count != new_transmit_hold_count
 607         && new_transmit_hold_count >= RSTP_MIN_TRANSMIT_HOLD_COUNT
 608         && new_transmit_hold_count <= RSTP_MAX_TRANSMIT_HOLD_COUNT) {
 609         struct rstp_port *p;
 610
 611         VLOG_DBG("%s: set RSTP Transmit Hold Count to %d", rstp->name,
 612                  new_transmit_hold_count);
 613         /* Resetting txCount on all ports [17.13]. */
 614
 615         rstp->transmit_hold_count = new_transmit_hold_count;
 616         HMAP_FOR_EACH (p, node, &rstp->ports) {
 617             p->tx_count = 0;
 618         }
 619     }
 620 }
 621
 622 void
 623 rstp_set_bridge_transmit_hold_count(struct rstp *rstp,
 624                                     int new_transmit_hold_count)
 625     OVS_EXCLUDED(rstp_mutex)
 626 {
 627     ovs_mutex_lock(&rstp_mutex);
 628     rstp_set_bridge_transmit_hold_count__(rstp, new_transmit_hold_count);
 629     ovs_mutex_unlock(&rstp_mutex);
 630 }
 631
 632 /* Sets the bridge migrate time parameter. */
 633 static void
 634 rstp_set_bridge_migrate_time__(struct rstp *rstp)
 635     OVS_REQUIRES(rstp_mutex)
 636 {
 637     VLOG_DBG("%s: set RSTP Migrate Time to %d", rstp->name,
 638              RSTP_MIGRATE_TIME);
 639     /* 3 is the only acceptable value */
 640     rstp->migrate_time = RSTP_MIGRATE_TIME;
 641 }
 642
 643 /* Sets the bridge times. */
 644 static void
 645 rstp_set_bridge_times__(struct rstp *rstp, int new_forward_delay,
 646                         int new_hello_time, int new_max_age,
 647                         int new_message_age)
 648     OVS_REQUIRES(rstp_mutex)
 649 {
 650     VLOG_DBG("%s: set RSTP times to (%d, %d, %d, %d)", rstp->name,
 651              new_forward_delay, new_hello_time, new_max_age, new_message_age);
 652     if (new_forward_delay >= RSTP_MIN_BRIDGE_FORWARD_DELAY
 653         && new_forward_delay <= RSTP_MAX_BRIDGE_FORWARD_DELAY) {
 654         rstp->bridge_times.forward_delay = new_forward_delay;
 655     }
 656     if (new_hello_time == RSTP_BRIDGE_HELLO_TIME) {
 657         rstp->bridge_times.hello_time = new_hello_time;
 658     }
 659     if (new_max_age >= RSTP_MIN_BRIDGE_MAX_AGE
 660         && new_max_age <= RSTP_MAX_BRIDGE_MAX_AGE) {
 661         rstp->bridge_times.max_age = new_max_age;
 662     }
 663     rstp->bridge_times.message_age = new_message_age;
 664 }
 665
 666 /* Sets the port id, it is called by rstp_port_set_port_number__() or
 667  * rstp_port_set_priority__().
 668  */
 669 static void
 670 set_port_id__(struct rstp_port *p)
 671     OVS_REQUIRES(rstp_mutex)
 672 {
 673     struct rstp *rstp;
 674
 675     rstp = p->rstp;
 676     /* [9.2.7] Port identifier. */
 677     p->port_id = p->port_number | (p->priority << 8);
 678     VLOG_DBG("%s: new RSTP port id "RSTP_PORT_ID_FMT"", rstp->name,
 679              p->port_id);
 680 }
 681
 682 /* Sets the port priority. */
 683 static void
 684 rstp_port_set_priority__(struct rstp_port *port, int priority)
 685     OVS_REQUIRES(rstp_mutex)
 686 {
 687     if (port->priority != priority
 688         && priority >= RSTP_MIN_PORT_PRIORITY
 689         && priority <= RSTP_MAX_PORT_PRIORITY) {
 690         VLOG_DBG("%s, port %u: set RSTP port priority to %d", port->rstp->name,
 691                  port->port_number, priority);
 692
 693         priority -= priority % RSTP_STEP_PORT_PRIORITY;
 694         port->priority = priority;
 695         set_port_id__(port);
 696         port->selected = false;
 697         port->reselect = true;
 698     }
 699 }
 700
 701 /* Checks if a port number is available. */
 702 static bool
 703 is_port_number_available__(struct rstp *rstp, int n, struct rstp_port *port)
 704     OVS_REQUIRES(rstp_mutex)
 705 {
 706     if (n >= 1 && n <= RSTP_MAX_PORTS) {
 707         struct rstp_port *p = rstp_get_port__(rstp, n);
 708
 709         return p == NULL || p == port;
 710     }
 711     return false;
 712 }
 713
 714 static uint16_t
 715 rstp_first_free_number__(struct rstp *rstp, struct rstp_port *rstp_port)
 716     OVS_REQUIRES(rstp_mutex)
 717 {
 718     int free_number = 1;
 719
 720     while (free_number <= RSTP_MAX_PORTS) {
 721         if (is_port_number_available__(rstp, free_number, rstp_port)) {
 722             return free_number;
 723         }
 724         free_number++;
 725     }
 726     VLOG_DBG("%s, No free port number available.", rstp->name);
 727     return 0;
 728 }
 729
 730 /* Sets the port number. */
 731 static void
 732 rstp_port_set_port_number__(struct rstp_port *port, uint16_t port_number)
 733     OVS_REQUIRES(rstp_mutex)
 734 {
 735     int old_port_number = port->port_number;
 736
 737     /* If new_port_number is available, use it, otherwise use the first free
 738      * available port number. */
 739     if (port->port_number != port_number || port_number == 0) {
 740         port->port_number =
 741             is_port_number_available__(port->rstp, port_number, port)
 742             ? port_number
 743             : rstp_first_free_number__(port->rstp, port);
 744
 745         if (port->port_number != old_port_number) {
 746             set_port_id__(port);
 747             /* [17.13] is not clear. I suppose that a port number change
 748              * should trigger reselection like a port priority change. */
 749             port->selected = false;
 750             port->reselect = true;
 751
 752             /* Adjust the ports hmap. */
 753             if (!hmap_node_is_null(&port->node)) {
 754                 hmap_remove(&port->rstp->ports, &port->node);
 755             }
 756             hmap_insert(&port->rstp->ports, &port->node,
 757                         hash_int(port->port_number, 0));
 758
 759             VLOG_DBG("%s: set new RSTP port number %d", port->rstp->name,
 760                      port->port_number);
 761         }
 762     }
 763 }
 764
 765 static void
 766 rstp_port_set_port_name__(struct rstp_port *port, const char *name)
 767     OVS_REQUIRES(rstp_mutex)
 768 {
 769     free(port->port_name);
 770     port->port_name = xstrdup(name);
 771 }
 772
 773 /* Converts the link speed to a port path cost [Table 17-3]. */
 774 uint32_t
 775 rstp_convert_speed_to_cost(unsigned int speed)
 776 {
 777     uint32_t value;
 778
 779     value = speed >= 10000000 ? 2 /* 10 Tb/s. */
 780           : speed >= 1000000 ? 20 /* 1 Tb/s. */
 781           : speed >= 100000 ? 200 /* 100 Gb/s. */
 782           : speed >= 10000 ? 2000 /* 10 Gb/s. */
 783           : speed >= 1000 ? 20000 /* 1 Gb/s. */
 784           : speed >= 100 ? 200000 /* 100 Mb/s. */
 785           : speed >= 10 ? 2000000 /* 10 Mb/s. */
 786           : speed >= 1 ? 20000000 /* 1 Mb/s. */
 787           : RSTP_DEFAULT_PORT_PATH_COST; /* 100 Mb/s. */
 788
 789     return value;
 790 }
 791
 792 /* Sets the port path cost. */
 793 static void
 794 rstp_port_set_path_cost__(struct rstp_port *port, uint32_t path_cost)
 795     OVS_REQUIRES(rstp_mutex)
 796 {
 797     if (port->port_path_cost != path_cost
 798         && path_cost >= RSTP_MIN_PORT_PATH_COST
 799         && path_cost <= RSTP_MAX_PORT_PATH_COST) {
 800         VLOG_DBG("%s, port %u, set RSTP port path cost to %d",
 801                  port->rstp->name, port->port_number, path_cost);
 802
 803         port->port_path_cost = path_cost;
 804         port->selected = false;
 805         port->reselect = true;
 806     }
 807 }
 808
 809 /* Gets the root path cost. */
 810 static uint32_t
 811 rstp_get_root_path_cost__(const struct rstp *rstp)
 812     OVS_REQUIRES(rstp_mutex)
 813 {
 814     return rstp->root_priority.root_path_cost;
 815 }
 816
 817 uint32_t
 818 rstp_get_root_path_cost(const struct rstp *rstp)
 819     OVS_EXCLUDED(rstp_mutex)
 820 {
 821     uint32_t cost;
 822
 823     ovs_mutex_lock(&rstp_mutex);
 824     cost = rstp_get_root_path_cost__(rstp);
 825     ovs_mutex_unlock(&rstp_mutex);
 826     return cost;
 827 }
 828
 829 /* Finds a port which needs to flush its own MAC learning table.  A NULL
 830  * pointer is returned if no port needs to flush its MAC learning table.
 831  * '*port' needs to be NULL in the first call to start the iteration.  If
 832  * '*port' is passed as non-NULL, it must be the value set by the last
 833  * invocation of this function.
 834  *
 835  * This function may only be called by the thread that creates and deletes
 836  * ports.  Otherwise this function is not thread safe, as the returned
 837  * '*port' could become stale before it is used in the next invocation. */
 838 void *
 839 rstp_check_and_reset_fdb_flush(struct rstp *rstp, struct rstp_port **port)
 840     OVS_EXCLUDED(rstp_mutex)
 841 {
 842     void *aux = NULL;
 843
 844     ovs_mutex_lock(&rstp_mutex);
 845     if (*port == NULL) {
 846         struct rstp_port *p;
 847
 848         HMAP_FOR_EACH (p, node, &rstp->ports) {
 849             if (p->fdb_flush) {
 850                 aux = p->aux;
 851                 *port = p;
 852                 goto out;
 853             }
 854         }
 855     } else { /* continue */
 856         struct rstp_port *p = *port;
 857
 858         HMAP_FOR_EACH_CONTINUE (p, node, &rstp->ports) {
 859             if (p->fdb_flush) {
 860                 aux = p->aux;
 861                 *port = p;
 862                 goto out;
 863             }
 864         }
 865     }
 866     /* No port needs flushing. */
 867     *port = NULL;
 868 out:
 869     /* fdb_flush should be reset by the filtering database
 870      * once the entries are removed if rstp_version is TRUE, and
 871      * immediately if stp_version is TRUE.*/
 872     if (*port != NULL) {
 873         (*port)->fdb_flush = false;
 874     }
 875     ovs_mutex_unlock(&rstp_mutex);
 876
 877     return aux;
 878 }
 879
 880 /* Finds a port whose state has changed, and returns the aux pointer set for
 881  * the port.  A NULL pointer is returned when no changed port is found.  On
 882  * return '*portp' contains the pointer to the rstp port that changed, or NULL
 883  * if no changed port can be found.
 884  *
 885  * If '*portp' is passed as non-NULL, it must be the value set by the last
 886  * invocation of this function.
 887  *
 888  * This function may only be called by the thread that creates and deletes
 889  * ports.  Otherwise this function is not thread safe, as the returned
 890  * '*portp' could become stale before it is used in the next invocation. */
 891 void *
 892 rstp_get_next_changed_port_aux(struct rstp *rstp, struct rstp_port **portp)
 893 {
 894     void *aux = NULL;
 895
 896     ovs_mutex_lock(&rstp_mutex);
 897     if (*portp == NULL) {
 898         struct rstp_port *p;
 899
 900         HMAP_FOR_EACH (p, node, &rstp->ports) {
 901             if (p->state_changed) {
 902                 p->state_changed = false;
 903                 aux = p->aux;
 904                 *portp = p;
 905                 goto out;
 906             }
 907         }
 908     } else { /* continue */
 909         struct rstp_port *p = *portp;
 910
 911         HMAP_FOR_EACH_CONTINUE (p, node, &rstp->ports) {
 912             if (p->state_changed) {
 913                 p->state_changed = false;
 914                 aux = p->aux;
 915                 *portp = p;
 916                 goto out;
 917             }
 918         }
 919     }
 920     /* No changed port found. */
 921     *portp = NULL;
 922 out:
 923     ovs_mutex_unlock(&rstp_mutex);
 924
 925     return aux;
 926 }
 927
 928 bool
 929 rstp_shift_root_learned_address(struct rstp *rstp)
 930 {
 931     bool ret;
 932
 933     ovs_mutex_lock(&rstp_mutex);
 934     ret = rstp->root_changed;
 935     ovs_mutex_unlock(&rstp_mutex);
 936
 937     return ret;
 938 }
 939
 940 void *
 941 rstp_get_old_root_aux(struct rstp *rstp)
 942 {
 943     void *aux;
 944
 945     ovs_mutex_lock(&rstp_mutex);
 946     aux = rstp->old_root_aux;
 947     ovs_mutex_unlock(&rstp_mutex);
 948
 949     return aux;
 950 }
 951
 952 void *
 953 rstp_get_new_root_aux(struct rstp *rstp)
 954 {
 955     void *aux;
 956
 957     ovs_mutex_lock(&rstp_mutex);
 958     aux = rstp->new_root_aux;
 959     ovs_mutex_unlock(&rstp_mutex);
 960
 961     return aux;
 962 }
 963
 964 void
 965 rstp_reset_root_changed(struct rstp *rstp)
 966 {
 967     ovs_mutex_lock(&rstp_mutex);
 968     rstp->root_changed = false;
 969     ovs_mutex_unlock(&rstp_mutex);
 970 }
 971
 972 /* Returns the port in 'rstp' with number 'port_number'.
 973  *
 974  * XXX: May only be called while concurrent deletion of ports is excluded. */
 975 static struct rstp_port *
 976 rstp_get_port__(struct rstp *rstp, uint16_t port_number)
 977     OVS_REQUIRES(rstp_mutex)
 978 {
 979     struct rstp_port *port;
 980
 981     ovs_assert(rstp && port_number > 0 && port_number <= RSTP_MAX_PORTS);
 982
 983     HMAP_FOR_EACH_WITH_HASH (port, node, hash_int(port_number, 0),
 984                              &rstp->ports) {
 985         if (port->port_number == port_number) {
 986             return port;
 987         }
 988     }
 989     return NULL;
 990 }
 991
 992 struct rstp_port *
 993 rstp_get_port(struct rstp *rstp, uint16_t port_number)
 994     OVS_EXCLUDED(rstp_mutex)
 995 {
 996     struct rstp_port *p;
 997
 998     ovs_mutex_lock(&rstp_mutex);
 999     p = rstp_get_port__(rstp, port_number);
1000     ovs_mutex_unlock(&rstp_mutex);
1001     return p;
1002 }
1003
1004 void *
1005 rstp_get_port_aux__(struct rstp *rstp, uint16_t port_number)
1006     OVS_REQUIRES(rstp_mutex)
1007 {
1008     struct rstp_port *p;
1009     p = rstp_get_port__(rstp, port_number);
1010     if (p) {
1011         return p->aux;
1012     }
1013     return NULL;
1014 }
1015
1016 /* Updates the port_enabled parameter. */
1017 static void
1018 update_port_enabled__(struct rstp_port *p)
1019     OVS_REQUIRES(rstp_mutex)
1020 {
1021     if (p->mac_operational && p->is_administrative_bridge_port
1022         == RSTP_ADMIN_BRIDGE_PORT_STATE_ENABLED) {
1023         p->port_enabled = true;
1024     } else {
1025         p->port_enabled = false;
1026     }
1027 }
1028
1029 /* Sets the port MAC_Operational parameter [6.4.2]. */
1030 void
1031 rstp_port_set_mac_operational(struct rstp_port *p, bool new_mac_operational)
1032     OVS_EXCLUDED(rstp_mutex)
1033 {
1034     struct rstp *rstp;
1035
1036     ovs_mutex_lock(&rstp_mutex);
1037     rstp = p->rstp;
1038     if (p->mac_operational != new_mac_operational) {
1039         p->mac_operational = new_mac_operational;
1040         update_port_enabled__(p);
1041         rstp->changes = true;
1042         move_rstp__(rstp);
1043     }
1044     ovs_mutex_unlock(&rstp_mutex);
1045 }
1046
1047 /* Sets the port Administrative Bridge Port parameter. */
1048 static void
1049 rstp_port_set_administrative_bridge_port__(struct rstp_port *p,
1050                                            uint8_t admin_port_state,
1051                                            bool initializing)
1052     OVS_REQUIRES(rstp_mutex)
1053 {
1054     VLOG_DBG("%s, port %u: set RSTP port admin-port-state to %d",
1055              p->rstp->name, p->port_number, admin_port_state);
1056
1057     if (p->is_administrative_bridge_port != admin_port_state
1058         && (admin_port_state == RSTP_ADMIN_BRIDGE_PORT_STATE_DISABLED
1059             || admin_port_state == RSTP_ADMIN_BRIDGE_PORT_STATE_ENABLED)) {
1060         p->is_administrative_bridge_port = admin_port_state;
1061         update_port_enabled__(p);
1062
1063         if (!initializing) {
1064             struct rstp *rstp = p->rstp;
1065
1066             rstp->changes = true;
1067             move_rstp__(rstp);
1068         }
1069     }
1070 }
1071
1072 /* Sets the port oper_point_to_point_mac parameter. */
1073 static void
1074 rstp_port_set_oper_point_to_point_mac__(struct rstp_port *p,
1075                                         uint8_t new_oper_p2p_mac)
1076     OVS_REQUIRES(rstp_mutex)
1077 {
1078     if (p->oper_point_to_point_mac != new_oper_p2p_mac
1079         && (new_oper_p2p_mac == RSTP_OPER_P2P_MAC_STATE_DISABLED
1080             || new_oper_p2p_mac == RSTP_OPER_P2P_MAC_STATE_ENABLED)) {
1081
1082         p->oper_point_to_point_mac = new_oper_p2p_mac;
1083         update_port_enabled__(p);
1084     }
1085 }
1086
1087 /* Initializes a port with the defaults values for its parameters. */
1088 static void
1089 rstp_initialize_port_defaults__(struct rstp_port *p)
1090     OVS_REQUIRES(rstp_mutex)
1091 {
1092     rstp_port_set_administrative_bridge_port__(p,
1093                                                RSTP_ADMIN_BRIDGE_PORT_STATE_ENABLED,
1094                                                true);
1095     rstp_port_set_oper_point_to_point_mac__(p,
1096                                          RSTP_OPER_P2P_MAC_STATE_ENABLED);
1097     rstp_port_set_path_cost__(p, RSTP_DEFAULT_PORT_PATH_COST);
1098     rstp_port_set_admin_edge__(p, false);
1099     rstp_port_set_auto_edge__(p, true);
1100     rstp_port_set_mcheck__(p, false);
1101
1102     /* Initialize state machines. */
1103     p->port_receive_sm_state = PORT_RECEIVE_SM_INIT;
1104     p->port_protocol_migration_sm_state = PORT_PROTOCOL_MIGRATION_SM_INIT;
1105     p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_INIT;
1106     p->port_transmit_sm_state = PORT_TRANSMIT_SM_INIT;
1107     p->port_information_sm_state = PORT_INFORMATION_SM_INIT;
1108     p->port_role_transition_sm_state = PORT_ROLE_TRANSITION_SM_INIT;
1109     p->port_state_transition_sm_state = PORT_STATE_TRANSITION_SM_INIT;
1110     p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_INIT;
1111     p->uptime = 0;
1112
1113 }
1114
1115 static void
1116 reinitialize_port__(struct rstp_port *p)
1117     OVS_REQUIRES(rstp_mutex)
1118 {
1119     struct rstp_port temp_port;
1120     struct rstp *rstp;
1121
1122     rstp = p->rstp;
1123     temp_port = *p;
1124     memset(p, 0, sizeof(struct rstp_port));
1125
1126     p->ref_cnt = temp_port.ref_cnt;
1127     p->rstp = rstp;
1128     p->node = temp_port.node;
1129     p->aux = temp_port.aux;
1130     p->port_number = temp_port.port_number;
1131     p->port_priority = temp_port.port_priority;
1132     p->port_id = temp_port.port_id;
1133     p->rstp_state = RSTP_DISCARDING;
1134
1135     rstp_initialize_port_defaults__(p);
1136
1137     VLOG_DBG("%s: RSTP port "RSTP_PORT_ID_FMT" reinitialized.", rstp->name,
1138              p->port_id);
1139 }
1140
1141 void
1142 reinitialize_port(struct rstp_port *p)
1143     OVS_EXCLUDED(rstp_mutex)
1144 {
1145     ovs_mutex_lock(&rstp_mutex);
1146     reinitialize_port__(p);
1147     ovs_mutex_unlock(&rstp_mutex);
1148 }
1149
1150 /* Sets the port state. */
1151 void
1152 rstp_port_set_state__(struct rstp_port *p, enum rstp_state state)
1153     OVS_REQUIRES(rstp_mutex)
1154 {
1155     struct rstp *rstp;
1156
1157     rstp = p->rstp;
1158     VLOG_DBG("%s, port %u: set RSTP port state %s -> %s", rstp->name,
1159              p->port_number,
1160              rstp_state_name(p->rstp_state), rstp_state_name(state));
1161
1162     if (state != p->rstp_state && !p->state_changed) {
1163         p->state_changed = true;
1164         seq_change(connectivity_seq_get());
1165     }
1166     p->rstp_state = state;
1167 }
1168
1169 void
1170 rstp_port_set_state(struct rstp_port *p, enum rstp_state state)
1171     OVS_EXCLUDED(rstp_mutex)
1172 {
1173     ovs_mutex_lock(&rstp_mutex);
1174     rstp_port_set_state__(p, state);
1175     ovs_mutex_unlock(&rstp_mutex);
1176 }
1177
1178 /* Adds a RSTP port. */
1179 struct rstp_port *
1180 rstp_add_port(struct rstp *rstp)
1181     OVS_EXCLUDED(rstp_mutex)
1182 {
1183     struct rstp_port *p = xzalloc(sizeof *p);
1184
1185     ovs_refcount_init(&p->ref_cnt);
1186     hmap_node_nullify(&p->node);
1187
1188     ovs_mutex_lock(&rstp_mutex);
1189     p->rstp = rstp;
1190     rstp_port_set_priority__(p, RSTP_DEFAULT_PORT_PRIORITY);
1191     rstp_port_set_port_number__(p, 0);
1192     p->aux = NULL;
1193     p->port_name = NULL;
1194     rstp_initialize_port_defaults__(p);
1195     VLOG_DBG("%s: RSTP port "RSTP_PORT_ID_FMT" initialized.", rstp->name,
1196              p->port_id);
1197
1198     rstp_port_set_state__(p, RSTP_DISCARDING);
1199     rstp->changes = true;
1200     move_rstp__(rstp);
1201     VLOG_DBG("%s: added port "RSTP_PORT_ID_FMT"", rstp->name, p->port_id);
1202     ovs_mutex_unlock(&rstp_mutex);
1203     return p;
1204 }
1205
1206 /* Caller has to hold a reference to prevent 'rstp_port' from being deleted
1207  * while taking a new reference. */
1208 struct rstp_port *
1209 rstp_port_ref(const struct rstp_port *rp_)
1210     OVS_EXCLUDED(rstp_mutex)
1211 {
1212     struct rstp_port *rp = CONST_CAST(struct rstp_port *, rp_);
1213
1214     if (rp) {
1215         ovs_refcount_ref(&rp->ref_cnt);
1216     }
1217     return rp;
1218 }
1219
1220 /* Frees RSTP struct.  This can be caller by any thread. */
1221 void
1222 rstp_port_unref(struct rstp_port *rp)
1223     OVS_EXCLUDED(rstp_mutex)
1224 {
1225     if (rp && ovs_refcount_unref_relaxed(&rp->ref_cnt) == 1) {
1226         struct rstp *rstp;
1227
1228         ovs_mutex_lock(&rstp_mutex);
1229         rstp = rp->rstp;
1230         rstp_port_set_state__(rp, RSTP_DISABLED);
1231         free(rp->port_name);
1232         hmap_remove(&rstp->ports, &rp->node);
1233         VLOG_DBG("%s: removed port "RSTP_PORT_ID_FMT"", rstp->name,
1234                  rp->port_id);
1235         ovs_mutex_unlock(&rstp_mutex);
1236         free(rp);
1237     }
1238 }
1239
1240 /* Sets the port Admin Edge parameter. */
1241 static void
1242 rstp_port_set_admin_edge__(struct rstp_port *port, bool admin_edge)
1243      OVS_REQUIRES(rstp_mutex)
1244 {
1245     if (port->admin_edge != admin_edge) {
1246         VLOG_DBG("%s, port %u: set RSTP Admin Edge to %d", port->rstp->name,
1247                  port->port_number, admin_edge);
1248
1249         port->admin_edge = admin_edge;
1250     }
1251 }
1252
1253 /* Sets the port Auto Edge parameter. */
1254 static void
1255 rstp_port_set_auto_edge__(struct rstp_port *port, bool auto_edge)
1256     OVS_REQUIRES(rstp_mutex)
1257 {
1258     if (port->auto_edge != auto_edge) {
1259         VLOG_DBG("%s, port %u: set RSTP Auto Edge to %d", port->rstp->name,
1260                  port->port_number, auto_edge);
1261
1262         port->auto_edge = auto_edge;
1263     }
1264 }
1265
1266 /* Sets the port admin_point_to_point_mac parameter. */
1267 static void rstp_port_set_admin_point_to_point_mac__(struct rstp_port *port,
1268         enum rstp_admin_point_to_point_mac_state admin_p2p_mac_state)
1269     OVS_REQUIRES(rstp_mutex)
1270 {
1271     VLOG_DBG("%s, port %u: set RSTP port admin-point-to-point-mac to %d",
1272             port->rstp->name, port->port_number, admin_p2p_mac_state);
1273     if (port->admin_point_to_point_mac != admin_p2p_mac_state) {
1274         if (admin_p2p_mac_state == RSTP_ADMIN_P2P_MAC_FORCE_TRUE) {
1275             port->admin_point_to_point_mac = admin_p2p_mac_state;
1276             rstp_port_set_oper_point_to_point_mac__(
1277                 port, RSTP_OPER_P2P_MAC_STATE_ENABLED);
1278         } else if (admin_p2p_mac_state == RSTP_ADMIN_P2P_MAC_FORCE_FALSE) {
1279             port->admin_point_to_point_mac = admin_p2p_mac_state;
1280             rstp_port_set_oper_point_to_point_mac__(
1281                 port, RSTP_OPER_P2P_MAC_STATE_DISABLED);
1282         } else if (admin_p2p_mac_state == RSTP_ADMIN_P2P_MAC_AUTO) {
1283             /* If adminPointToPointMAC is set to Auto, then the value of
1284              * operPointToPointMAC is determined in accordance with the
1285              * specific procedures defined for the MAC entity concerned, as
1286              * defined in 6.5. If these procedures determine that the MAC
1287              * entity is connected to a point-to-point LAN, then
1288              * operPointToPointMAC is set TRUE; otherwise it is set FALSE.
1289              * In the absence of a specific definition of how to determine
1290              * whether the MAC is connected to a point-to-point LAN or not,
1291              * the value of operPointToPointMAC shall be FALSE. */
1292             port->admin_point_to_point_mac = admin_p2p_mac_state;
1293             rstp_port_set_oper_point_to_point_mac__(
1294                 port, RSTP_OPER_P2P_MAC_STATE_DISABLED);
1295         }
1296     }
1297 }
1298
1299 /* Sets the port mcheck parameter.
1300  * [17.19.13] May be set by management to force the Port Protocol Migration
1301  * state machine to transmit RST BPDUs for a MigrateTime (17.13.9) period, to
1302  * test whether all STP Bridges (17.4) on the attached LAN have been removed
1303  * and the Port can continue to transmit RSTP BPDUs. Setting mcheck has no
1304  * effect if stpVersion (17.20.12) is TRUE, i.e., the Bridge is operating in
1305  * STP Compatibility mode.
1306  */
1307 static void
1308 rstp_port_set_mcheck__(struct rstp_port *port, bool mcheck)
1309     OVS_REQUIRES(rstp_mutex)
1310 {
1311     if (mcheck == true && port->rstp->force_protocol_version >= 2) {
1312         port->mcheck = true;
1313
1314         VLOG_DBG("%s, port %u: set RSTP mcheck to %d", port->rstp->name,
1315                  port->port_number, mcheck);
1316     }
1317 }
1318
1319 /* Returns the designated bridge id. */
1320 rstp_identifier
1321 rstp_get_designated_id(const struct rstp *rstp)
1322     OVS_EXCLUDED(rstp_mutex)
1323 {
1324     rstp_identifier designated_id;
1325
1326     ovs_mutex_lock(&rstp_mutex);
1327     designated_id = rstp->root_priority.designated_bridge_id;
1328     ovs_mutex_unlock(&rstp_mutex);
1329
1330     return designated_id;
1331 }
1332
1333 /* Returns the root bridge id. */
1334 static rstp_identifier
1335 rstp_get_root_id__(const struct rstp *rstp)
1336     OVS_REQUIRES(rstp_mutex)
1337 {
1338     return rstp->root_priority.root_bridge_id;
1339 }
1340
1341 rstp_identifier
1342 rstp_get_root_id(const struct rstp *rstp)
1343     OVS_EXCLUDED(rstp_mutex)
1344 {
1345     rstp_identifier root_id;
1346
1347     ovs_mutex_lock(&rstp_mutex);
1348     root_id = rstp_get_root_id__(rstp);
1349     ovs_mutex_unlock(&rstp_mutex);
1350
1351     return root_id;
1352 }
1353
1354 /* Returns the designated port id. */
1355 uint16_t
1356 rstp_get_designated_port_id(const struct rstp *rstp)
1357     OVS_EXCLUDED(rstp_mutex)
1358 {
1359     uint16_t designated_port_id;
1360
1361     ovs_mutex_lock(&rstp_mutex);
1362     designated_port_id = rstp->root_priority.designated_port_id;
1363     ovs_mutex_unlock(&rstp_mutex);
1364
1365     return designated_port_id;
1366 }
1367
1368 /* Return the bridge port id. */
1369 uint16_t
1370 rstp_get_bridge_port_id(const struct rstp *rstp)
1371     OVS_EXCLUDED(rstp_mutex)
1372 {
1373     uint16_t bridge_port_id;
1374
1375     ovs_mutex_lock(&rstp_mutex);
1376     bridge_port_id = rstp->root_priority.bridge_port_id;
1377     ovs_mutex_unlock(&rstp_mutex);
1378
1379     return bridge_port_id;
1380 }
1381
1382 /* Returns true if the bridge believes to the be root of the spanning tree,
1383  * false otherwise.
1384  */
1385 static bool
1386 rstp_is_root_bridge__(const struct rstp *rstp)
1387     OVS_REQUIRES(rstp_mutex)
1388 {
1389     return rstp->bridge_identifier ==
1390         rstp->root_priority.designated_bridge_id;
1391 }
1392
1393 bool
1394 rstp_is_root_bridge(const struct rstp *rstp)
1395     OVS_EXCLUDED(rstp_mutex)
1396 {
1397     bool is_root;
1398
1399     ovs_mutex_lock(&rstp_mutex);
1400     is_root = rstp_is_root_bridge__(rstp);
1401     ovs_mutex_unlock(&rstp_mutex);
1402
1403     return is_root;
1404 }
1405
1406 /* Returns the bridge ID of the bridge currently believed to be the root. */
1407 rstp_identifier
1408 rstp_get_designated_root(const struct rstp *rstp)
1409     OVS_EXCLUDED(rstp_mutex)
1410 {
1411     rstp_identifier designated_root;
1412
1413     ovs_mutex_lock(&rstp_mutex);
1414     designated_root = rstp->root_priority.designated_bridge_id;
1415     ovs_mutex_unlock(&rstp_mutex);
1416
1417     return designated_root;
1418 }
1419
1420 /* Returns the port connecting 'rstp' to the root bridge, or a null pointer if
1421  * there is no such port.
1422  */
1423 static struct rstp_port *
1424 rstp_get_root_port__(const struct rstp *rstp)
1425     OVS_REQUIRES(rstp_mutex)
1426 {
1427     struct rstp_port *p;
1428
1429     HMAP_FOR_EACH (p, node, &rstp->ports) {
1430         if (p->port_id == rstp->root_port_id) {
1431             return p;
1432         }
1433     }
1434     return NULL;
1435 }
1436
1437 struct rstp_port *
1438 rstp_get_root_port(const struct rstp *rstp)
1439     OVS_EXCLUDED(rstp_mutex)
1440 {
1441     ovs_mutex_lock(&rstp_mutex);
1442     struct rstp_port *p = rstp_get_root_port__(rstp);
1443     ovs_mutex_unlock(&rstp_mutex);
1444     return p;
1445 }
1446
1447 /* Returns the state of port 'p'. */
1448 enum rstp_state
1449 rstp_port_get_state(const struct rstp_port *p)
1450     OVS_EXCLUDED(rstp_mutex)
1451 {
1452     enum rstp_state state;
1453
1454     ovs_mutex_lock(&rstp_mutex);
1455     state = p->rstp_state;
1456     ovs_mutex_unlock(&rstp_mutex);
1457
1458     return state;
1459 }
1460
1461 /* Retrieves port status. */
1462 void
1463 rstp_port_get_status(const struct rstp_port *p, uint16_t *id,
1464                      enum rstp_state *state, enum rstp_port_role *role,
1465                      rstp_identifier *designated_bridge_id,
1466                      uint16_t *designated_port_id,
1467                      uint32_t *designated_path_cost, int *tx_count,
1468                      int *rx_count, int *error_count, int *uptime)
1469     OVS_EXCLUDED(rstp_mutex)
1470 {
1471     ovs_mutex_lock(&rstp_mutex);
1472     *id = p->port_id;
1473     *state = p->rstp_state;
1474     *role = p->role;
1475
1476     *designated_bridge_id = p->port_priority.designated_bridge_id;
1477     *designated_port_id = p->port_priority.designated_port_id;
1478     *designated_path_cost = p->port_priority.root_path_cost;
1479
1480     *tx_count = p->tx_count;
1481     *rx_count = p->rx_rstp_bpdu_cnt;
1482     *error_count = p->error_count;
1483     *uptime = p->uptime;
1484     ovs_mutex_unlock(&rstp_mutex);
1485 }
1486
1487 void
1488 rstp_port_set(struct rstp_port *port, uint16_t port_num, int priority,
1489               uint32_t path_cost, bool is_admin_edge, bool is_auto_edge,
1490               enum rstp_admin_point_to_point_mac_state admin_p2p_mac_state,
1491               bool admin_port_state, bool do_mcheck, void *aux,
1492               const char *name)
1493     OVS_EXCLUDED(rstp_mutex)
1494 {
1495     ovs_mutex_lock(&rstp_mutex);
1496     port->aux = aux;
1497     rstp_port_set_priority__(port, priority);
1498     rstp_port_set_port_number__(port, port_num);
1499     rstp_port_set_port_name__(port, name);
1500     rstp_port_set_path_cost__(port, path_cost);
1501     rstp_port_set_admin_edge__(port, is_admin_edge);
1502     rstp_port_set_auto_edge__(port, is_auto_edge);
1503     rstp_port_set_admin_point_to_point_mac__(port, admin_p2p_mac_state);
1504     rstp_port_set_administrative_bridge_port__(port, admin_port_state, false);
1505     rstp_port_set_mcheck__(port, do_mcheck);
1506     ovs_mutex_unlock(&rstp_mutex);
1507 }
1508
1509 /* Individual setters only used by test-rstp.c. */
1510 void
1511 rstp_port_set_priority(struct rstp_port *port, int priority)
1512     OVS_EXCLUDED(rstp_mutex)
1513 {
1514     ovs_mutex_lock(&rstp_mutex);
1515     rstp_port_set_priority__(port, priority);
1516     ovs_mutex_unlock(&rstp_mutex);
1517 }
1518
1519 void
1520 rstp_port_set_path_cost(struct rstp_port *port, uint32_t path_cost)
1521     OVS_EXCLUDED(rstp_mutex)
1522 {
1523     ovs_mutex_lock(&rstp_mutex);
1524     rstp_port_set_path_cost__(port, path_cost);
1525     ovs_mutex_unlock(&rstp_mutex);
1526 }
1527
1528 void
1529 rstp_port_set_aux(struct rstp_port *port, void *aux)
1530     OVS_EXCLUDED(rstp_mutex)
1531 {
1532     ovs_mutex_lock(&rstp_mutex);
1533     port->aux = aux;
1534     ovs_mutex_unlock(&rstp_mutex);
1535 }
1536
1537 /* Unixctl. */
1538 static struct rstp *
1539 rstp_find(const char *name)
1540     OVS_REQUIRES(rstp_mutex)
1541 {
1542     struct rstp *rstp;
1543
1544     LIST_FOR_EACH (rstp, node, all_rstps) {
1545         if (!strcmp(rstp->name, name)) {
1546             return rstp;
1547         }
1548     }
1549     return NULL;
1550 }
1551
1552 static void
1553 rstp_unixctl_tcn(struct unixctl_conn *conn, int argc,
1554                  const char *argv[], void *aux OVS_UNUSED)
1555     OVS_EXCLUDED(rstp_mutex)
1556 {
1557     ovs_mutex_lock(&rstp_mutex);
1558     if (argc > 1) {
1559         struct rstp *rstp = rstp_find(argv[1]);
1560         if (!rstp) {
1561             unixctl_command_reply_error(conn, "No such RSTP object");
1562             goto out;
1563         }
1564         rstp->changes = true;
1565         move_rstp__(rstp);
1566     } else {
1567         struct rstp *rstp;
1568         LIST_FOR_EACH (rstp, node, all_rstps) {
1569             rstp->changes = true;
1570             move_rstp__(rstp);
1571         }
1572     }
1573     unixctl_command_reply(conn, "OK");
1574
1575 out:
1576     ovs_mutex_unlock(&rstp_mutex);
1577 }
1578
1579 static void
1580 rstp_bridge_id_details(struct ds *ds, const rstp_identifier bridge_id,
1581                        uint16_t hello_time, uint16_t max_age,
1582                        uint16_t forward_delay)
1583     OVS_REQUIRES(rstp_mutex)
1584 {
1585     uint16_t priority = bridge_id >> 48;
1586     ds_put_format(ds, "  stp-priority    %"PRIu16"\n", priority);
1587
1588     struct eth_addr mac;
1589     const uint64_t mac_bits = (UINT64_C(1) << 48) - 1;
1590     eth_addr_from_uint64(bridge_id & mac_bits, &mac);
1591     ds_put_format(ds, "  stp-system-id   "ETH_ADDR_FMT"\n", ETH_ADDR_ARGS(mac));
1592     ds_put_format(ds, "  stp-hello-time  %"PRIu16"s\n", hello_time);
1593     ds_put_format(ds, "  stp-max-age     %"PRIu16"s\n", max_age);
1594     ds_put_format(ds, "  stp-fwd-delay   %"PRIu16"s\n", forward_delay);
1595 }
1596
1597 static void
1598 rstp_print_details(struct ds *ds, const struct rstp *rstp)
1599     OVS_REQUIRES(rstp_mutex)
1600 {
1601     ds_put_format(ds, "---- %s ----\n", rstp->name);
1602
1603     ds_put_cstr(ds, "Root ID:\n");
1604     if (rstp_is_root_bridge__(rstp)) {
1605         rstp_bridge_id_details(ds, rstp->bridge_identifier,
1606                                rstp->bridge_hello_time,
1607                                rstp->bridge_max_age,
1608                                rstp->bridge_forward_delay);
1609         ds_put_cstr(ds, "  This bridge is the root\n");
1610     } else {
1611         struct rstp_port *root_port = rstp_get_root_port__(rstp);
1612         if (!root_port) {
1613             ds_put_cstr(ds, "unknown root port\n");
1614             return;
1615         }
1616
1617         rstp_bridge_id_details(ds, rstp_get_root_id__(rstp),
1618                                root_port->designated_times.hello_time,
1619                                root_port->designated_times.max_age,
1620                                root_port->designated_times.forward_delay);
1621         ds_put_format(ds, "  root-port       %s\n", root_port->port_name);
1622         ds_put_format(ds, "  root-path-cost  %u\n",
1623                       rstp_get_root_path_cost__(rstp));
1624     }
1625     ds_put_cstr(ds, "\n");
1626
1627     ds_put_cstr(ds, "Bridge ID:\n");
1628     rstp_bridge_id_details(ds, rstp->bridge_identifier,
1629                            rstp->bridge_hello_time,
1630                            rstp->bridge_max_age,
1631                            rstp->bridge_forward_delay);
1632     ds_put_cstr(ds, "\n");
1633
1634     ds_put_format(ds, "  %-11.10s%-11.10s%-11.10s%-9.8s%-8.7s\n",
1635                   "Interface", "Role", "State", "Cost", "Pri.Nbr");
1636     ds_put_cstr(ds, "  ---------- ---------- ---------- -------- -------\n");
1637
1638     struct rstp_port *p;
1639     HMAP_FOR_EACH (p, node, &rstp->ports) {
1640         if (p->rstp_state != RSTP_DISABLED) {
1641             ds_put_format(ds, "  %-11.10s",
1642                           p->port_name ? p->port_name : "null");
1643             ds_put_format(ds, "%-11.10s", rstp_port_role_name(p->role));
1644             ds_put_format(ds, "%-11.10s", rstp_state_name(p->rstp_state));
1645             ds_put_format(ds, "%-9d", p->port_path_cost);
1646             ds_put_format(ds, "%d.%d\n", p->priority, p->port_number);
1647         }
1648     }
1649
1650     ds_put_cstr(ds, "\n");
1651 }
1652
1653 static void
1654 rstp_unixctl_show(struct unixctl_conn *conn, int argc,
1655                   const char *argv[], void *aux OVS_UNUSED)
1656     OVS_EXCLUDED(rstp_mutex)
1657 {
1658     struct ds ds = DS_EMPTY_INITIALIZER;
1659
1660     ovs_mutex_lock(&rstp_mutex);
1661     if (argc > 1) {
1662         struct rstp *rstp = rstp_find(argv[1]);
1663
1664         if (!rstp) {
1665             unixctl_command_reply_error(conn, "No such RSTP object");
1666             goto out;
1667         }
1668
1669         rstp_print_details(&ds, rstp);
1670     } else {
1671         struct rstp *rstp;
1672
1673         LIST_FOR_EACH (rstp, node, all_rstps) {
1674             rstp_print_details(&ds, rstp);
1675         }
1676     }
1677
1678     unixctl_command_reply(conn, ds_cstr(&ds));
1679     ds_destroy(&ds);
1680
1681 out:
1682     ovs_mutex_unlock(&rstp_mutex);
1683 }