lib/rstp-state-machines.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) state machines
  19  * implementation.
  20  *
  21  * Authors:
  22  *         Martino Fornasa <mf@fornasa.it>
  23  *         Daniele Venturino <daniele.venturino@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 #include "rstp.h"
  32 #include "rstp-state-machines.h"
  33 #include <arpa/inet.h>
  34 #include <inttypes.h>
  35 #include <netinet/in.h>
  36 #include <stdlib.h>
  37 #include <sys/types.h>
  38 #include "byte-order.h"
  39 #include "connectivity.h"
  40 #include "ofpbuf.h"
  41 #include "packets.h"
  42 #include "seq.h"
  43 #include "unixctl.h"
  44 #include "util.h"
  45 #include "vlog.h"
  46
  47 VLOG_DEFINE_THIS_MODULE(rstp_sm);
  48
  49 #define ROLE_FLAG_MASK 0xC
  50 #define ROLE_FLAG_SHIFT 2
  51
  52 enum port_flag {
  53     PORT_UNKN = 0,
  54     PORT_ALT_BACK = 1,
  55     PORT_ROOT = 2,
  56     PORT_DES = 3
  57 };
  58
  59 enum bpdu_size {
  60     CONFIGURATION_BPDU_SIZE = 35,
  61     TOPOLOGY_CHANGE_NOTIFICATION_BPDU_SIZE = 4,
  62     RAPID_SPANNING_TREE_BPDU_SIZE = 36
  63 };
  64
  65 /* Same is a subset of SUPERIOR, so can be used as a boolean when the
  66  * distinction is not significant. */
  67 enum vector_comparison {
  68     INFERIOR = 0,
  69     SUPERIOR = 1,
  70     SAME = 2
  71 };
  72
  73 static void decrement_timer(uint16_t *);
  74 static void rstp_send_bpdu(struct rstp_port *, const void *, size_t)
  75     OVS_REQUIRES(rstp_mutex);
  76 static int validate_received_bpdu(struct rstp_port *, const void *, size_t)
  77     OVS_REQUIRES(rstp_mutex);
  78 static ovs_be16 time_encode(uint8_t);
  79 static uint8_t time_decode(ovs_be16);
  80 static enum vector_comparison
  81 compare_rstp_priority_vectors(const struct rstp_priority_vector *,
  82                               const struct rstp_priority_vector *);
  83 static bool rstp_times_equal(struct rstp_times *, struct rstp_times *);
  84
  85 /* Per-Bridge State Machine */
  86 static int port_role_selection_sm(struct rstp *)
  87     OVS_REQUIRES(rstp_mutex);
  88 /* Per-Port State Machines */
  89 static int port_receive_sm(struct rstp_port *)
  90     OVS_REQUIRES(rstp_mutex);
  91 static int port_protocol_migration_sm(struct rstp_port *)
  92     OVS_REQUIRES(rstp_mutex);
  93 static int bridge_detection_sm(struct rstp_port *)
  94     OVS_REQUIRES(rstp_mutex);
  95 static int port_transmit_sm(struct rstp_port *)
  96     OVS_REQUIRES(rstp_mutex);
  97 static int port_information_sm(struct rstp_port *)
  98     OVS_REQUIRES(rstp_mutex);
  99 static int port_role_transition_sm(struct rstp_port *)
 100     OVS_REQUIRES(rstp_mutex);
 101 static int port_state_transition_sm(struct rstp_port *)
 102     OVS_REQUIRES(rstp_mutex);
 103 static int topology_change_sm(struct rstp_port *)
 104     OVS_REQUIRES(rstp_mutex);
 105 /* port_timers_sm() not defined as a state machine */
 106
 107 void
 108 process_received_bpdu__(struct rstp_port *p, const void *bpdu_,
 109                         size_t bpdu_size)
 110     OVS_REQUIRES(rstp_mutex)
 111 {
 112     struct rstp *rstp = p->rstp;
 113     struct rstp_bpdu *bpdu = (struct rstp_bpdu *)bpdu_;
 114
 115     if (!p->port_enabled) {
 116         return;
 117     }
 118     if (p->rcvd_bpdu) {
 119         return;
 120     }
 121
 122     /* [9.2.9 Encoding of Port Role values]
 123      * NOTE. If the Unknown value of the Port Role parameter is received, the
 124      * state machines will effectively treat the RST BPDU as if it were a
 125      * Configuration BPDU.
 126      */
 127     if (bpdu->bpdu_type == RAPID_SPANNING_TREE_BPDU) {
 128         uint8_t role = (bpdu->flags & ROLE_FLAG_MASK) >> ROLE_FLAG_SHIFT;
 129
 130         if (role == PORT_UNKN) {
 131             bpdu->bpdu_type = CONFIGURATION_BPDU;
 132         }
 133     }
 134
 135     if (validate_received_bpdu(p, bpdu, bpdu_size) == 0) {
 136         p->rcvd_bpdu = true;
 137         p->rx_rstp_bpdu_cnt++;
 138
 139         memcpy(&p->received_bpdu_buffer, bpdu, sizeof(struct rstp_bpdu));
 140
 141         rstp->changes = true;
 142         move_rstp__(rstp);
 143     } else {
 144         VLOG_DBG("%s, port %u: Bad STP or RSTP BPDU received", p->rstp->name,
 145                  p->port_number);
 146         p->error_count++;
 147     }
 148 }
 149
 150 /* Returns 0 on success. */
 151 static int
 152 validate_received_bpdu(struct rstp_port *p, const void *bpdu, size_t bpdu_size)
 153     OVS_REQUIRES(rstp_mutex)
 154 {
 155     /* Validation of received BPDU, see [9.3.4]. */
 156     const struct rstp_bpdu *temp;
 157
 158     temp = bpdu;
 159     if (bpdu_size < TOPOLOGY_CHANGE_NOTIFICATION_BPDU_SIZE ||
 160             ntohs(temp->protocol_identifier) != 0) {
 161         return -1;
 162     } else {
 163         if (temp->bpdu_type == CONFIGURATION_BPDU
 164             && bpdu_size >= CONFIGURATION_BPDU_SIZE
 165             && (time_decode(temp->message_age) <  time_decode(temp->max_age))) {
 166             if ((ntohll(temp->designated_bridge_id) !=
 167                  p->rstp->bridge_identifier)
 168                 || ((ntohll(temp->designated_bridge_id) ==
 169                      p->rstp->bridge_identifier)
 170                     && (ntohs(temp->designated_port_id) != p->port_id))) {
 171                 return 0;
 172             } else {
 173                 return -1;
 174             }
 175         } else if (temp->bpdu_type == TOPOLOGY_CHANGE_NOTIFICATION_BPDU) {
 176             return 0;
 177         } else if (temp->bpdu_type == RAPID_SPANNING_TREE_BPDU &&
 178                    bpdu_size >= RAPID_SPANNING_TREE_BPDU_SIZE) {
 179             return 0;
 180         } else {
 181             return -1;
 182         }
 183     }
 184 }
 185
 186 /*
 187  * move_rstp__()
 188  * This method is invoked to move the State Machines.  The SMs move only if the
 189  * boolean 'changes' is true, meaning that something changed and the SMs need
 190  * to work to process this change.
 191  * The boolean 'changes' is set every time a SM modifies its state, a BPDU is
 192  * received, a timer expires or port down event is detected.  If a parameter is
 193  * set by management, then 'changes' is set.
 194  */
 195 #define MAX_RSTP_ITERATIONS 1000 /* safeguard */
 196 int
 197 move_rstp__(struct rstp *rstp)
 198     OVS_REQUIRES(rstp_mutex)
 199 {
 200     int num_iterations;
 201     num_iterations = 0;
 202
 203     while (rstp->changes == true && num_iterations < MAX_RSTP_ITERATIONS) {
 204         struct rstp_port *p;
 205
 206         VLOG_DBG("%s: move_rstp()", rstp->name);
 207
 208         rstp->changes = false;
 209         port_role_selection_sm(rstp);
 210         HMAP_FOR_EACH (p, node, &rstp->ports) {
 211             if (p->rstp_state != RSTP_DISABLED) {
 212                 port_receive_sm(p);
 213                 bridge_detection_sm(p);
 214                 port_information_sm(p);
 215                 port_role_transition_sm(p);
 216                 port_state_transition_sm(p);
 217                 topology_change_sm(p);
 218                 port_transmit_sm(p);
 219                 port_protocol_migration_sm(p);
 220             }
 221         }
 222         num_iterations++;
 223         seq_change(connectivity_seq_get());
 224     }
 225     if (num_iterations >= MAX_RSTP_ITERATIONS) {
 226         VLOG_ERR("%s: move_rstp() reached the iteration safeguard limit!",
 227                  rstp->name);
 228     }
 229     return 0;
 230 }
 231
 232 void decrease_rstp_port_timers__(struct rstp *r)
 233     OVS_REQUIRES(rstp_mutex)
 234 {
 235     struct rstp_port *p;
 236
 237     HMAP_FOR_EACH (p, node, &r->ports) {
 238         decrement_timer(&p->hello_when);
 239         decrement_timer(&p->tc_while);
 240         decrement_timer(&p->fd_while);
 241         decrement_timer(&p->rcvd_info_while);
 242         decrement_timer(&p->rr_while);
 243         decrement_timer(&p->rb_while);
 244         decrement_timer(&p->mdelay_while);
 245         decrement_timer(&p->edge_delay_while);
 246         decrement_timer(&p->tx_count);
 247         p->uptime += 1;
 248     }
 249     r->changes = true;
 250     move_rstp__(r);
 251 }
 252
 253 static void
 254 decrement_timer(uint16_t *timer)
 255 {
 256     if (*timer != 0) {
 257         *timer -= 1;
 258     }
 259 }
 260
 261 /* Bridge State Machine. */
 262 /* [17.28] Port Role Selection state machine. */
 263
 264 static void
 265 updt_role_disabled_tree(struct rstp *r)
 266     OVS_REQUIRES(rstp_mutex)
 267 {
 268     struct rstp_port *p;
 269
 270     HMAP_FOR_EACH (p, node, &r->ports) {
 271         p->selected_role = ROLE_DISABLED;
 272     }
 273 }
 274
 275 static void
 276 clear_reselect_tree(struct rstp *r)
 277     OVS_REQUIRES(rstp_mutex)
 278 {
 279     struct rstp_port *p;
 280
 281     HMAP_FOR_EACH (p, node, &r->ports) {
 282         p->reselect = false;
 283     }
 284 }
 285
 286 void
 287 updt_roles_tree__(struct rstp *r)
 288     OVS_REQUIRES(rstp_mutex)
 289 {
 290     struct rstp_port *p;
 291     int vsel;
 292     struct rstp_priority_vector best_vector, candidate_vector;
 293     enum rstp_port_role new_root_old_role = ROLE_DESIGNATED;
 294     uint16_t old_root_port_number = 0;
 295     uint16_t new_root_port_number = 0;
 296
 297     old_root_port_number = r->root_port_id & 0x00ff;
 298     if (old_root_port_number) {
 299         r->old_root_aux = rstp_get_port_aux__(r, old_root_port_number);
 300     }
 301     vsel = -1;
 302     best_vector = r->bridge_priority;
 303     /* Letter c1) */
 304     r->root_times = r->bridge_times;
 305     /* Letters a) b) c) */
 306     HMAP_FOR_EACH (p, node, &r->ports) {
 307         uint32_t old_root_path_cost;
 308         uint32_t root_path_cost;
 309
 310         if (p->info_is != INFO_IS_RECEIVED) {
 311             continue;
 312         }
 313         /* [17.6] */
 314         candidate_vector = p->port_priority;
 315         candidate_vector.bridge_port_id = p->port_id;
 316         old_root_path_cost = candidate_vector.root_path_cost;
 317         root_path_cost = old_root_path_cost + p->port_path_cost;
 318         candidate_vector.root_path_cost = root_path_cost;
 319
 320         if ((candidate_vector.designated_bridge_id & 0xffffffffffffULL) ==
 321             (r->bridge_priority.designated_bridge_id & 0xffffffffffffULL)) {
 322             continue;
 323         }
 324         if (compare_rstp_priority_vectors(&candidate_vector,
 325                                           &best_vector) == SUPERIOR) {
 326             best_vector = candidate_vector;
 327             r->root_times = p->port_times;
 328             r->root_times.message_age++;
 329             vsel = p->port_number;
 330             new_root_old_role = p->role;
 331         }
 332     }
 333     r->root_priority = best_vector;
 334     r->root_port_id = best_vector.bridge_port_id;
 335     VLOG_DBG("%s: new Root is "RSTP_ID_FMT, r->name,
 336              RSTP_ID_ARGS(r->root_priority.root_bridge_id));
 337     new_root_port_number = r->root_port_id & 0x00ff;
 338     if (new_root_port_number) {
 339         r->new_root_aux = rstp_get_port_aux__(r, new_root_port_number);
 340     }
 341     /* Shift learned MAC addresses from an old Root Port to an existing
 342      * Alternate Port. */
 343     if (!r->root_changed
 344         && new_root_old_role == ROLE_ALTERNATE
 345         && new_root_port_number
 346         && old_root_port_number
 347         && new_root_port_number != old_root_port_number) {
 348         r->root_changed = true;
 349     }
 350     /* Letters d) e) */
 351     HMAP_FOR_EACH (p, node, &r->ports) {
 352         p->designated_priority_vector.root_bridge_id =
 353             r->root_priority.root_bridge_id;
 354         p->designated_priority_vector.root_path_cost =
 355             r->root_priority.root_path_cost;
 356         p->designated_priority_vector.designated_bridge_id =
 357             r->bridge_identifier;
 358         p->designated_priority_vector.designated_port_id =
 359             p->port_id;
 360         p->designated_times = r->root_times;
 361         p->designated_times.hello_time = r->bridge_times.hello_time;
 362     }
 363     HMAP_FOR_EACH (p, node, &r->ports) {
 364         switch (p->info_is) {
 365         case INFO_IS_DISABLED:
 366             p->selected_role = ROLE_DISABLED;
 367             break;
 368         case INFO_IS_AGED:
 369             p->updt_info = true;
 370             p->selected_role = ROLE_DESIGNATED;
 371             break;
 372         case INFO_IS_MINE:
 373             p->selected_role = ROLE_DESIGNATED;
 374             if (compare_rstp_priority_vectors(
 375                     &p->port_priority, &p->designated_priority_vector) != SAME
 376                 || !rstp_times_equal(&p->designated_times, &r->root_times)) {
 377                 p->updt_info = true;
 378             }
 379             break;
 380         case INFO_IS_RECEIVED:
 381             if (vsel == p->port_number) { /* Letter i) */
 382                 p->selected_role = ROLE_ROOT;
 383                 p->updt_info = false;
 384             } else if (compare_rstp_priority_vectors(
 385                            &p->designated_priority_vector,
 386                            &p->port_priority) == INFERIOR) {
 387                 if (p->port_priority.designated_bridge_id !=
 388                     r->bridge_identifier) {
 389                     p->selected_role = ROLE_ALTERNATE;
 390                     p->updt_info = false;
 391                 } else {
 392                     p->selected_role = ROLE_BACKUP;
 393                     p->updt_info = false;
 394                 }
 395             } else {
 396                 p->selected_role = ROLE_DESIGNATED;
 397                 p->updt_info = true;
 398             }
 399             break;
 400         default:
 401             OVS_NOT_REACHED();
 402             /* no break */
 403         }
 404     }
 405     seq_change(connectivity_seq_get());
 406 }
 407
 408 static void
 409 set_selected_tree(struct rstp *r)
 410     OVS_REQUIRES(rstp_mutex)
 411 {
 412     struct rstp_port *p;
 413
 414     HMAP_FOR_EACH (p, node, &r->ports) {
 415         if (p->reselect) {
 416             return;
 417         }
 418     }
 419     HMAP_FOR_EACH (p, node, &r->ports) {
 420         p->selected = true;
 421     }
 422 }
 423
 424 static int
 425 port_role_selection_sm(struct rstp *r)
 426     OVS_REQUIRES(rstp_mutex)
 427 {
 428     enum port_role_selection_state_machine old_state;
 429     struct rstp_port *p;
 430
 431     old_state = r->port_role_selection_sm_state;
 432
 433     switch (r->port_role_selection_sm_state) {
 434     case PORT_ROLE_SELECTION_SM_INIT:
 435         if (r->begin) {
 436             r->port_role_selection_sm_state =
 437                 PORT_ROLE_SELECTION_SM_INIT_BRIDGE_EXEC;
 438         }
 439         break;
 440     case PORT_ROLE_SELECTION_SM_INIT_BRIDGE_EXEC:
 441         updt_role_disabled_tree(r);
 442         r->port_role_selection_sm_state = PORT_ROLE_SELECTION_SM_INIT_BRIDGE;
 443         /* no break */
 444     case PORT_ROLE_SELECTION_SM_INIT_BRIDGE:
 445         r->port_role_selection_sm_state =
 446             PORT_ROLE_SELECTION_SM_ROLE_SELECTION_EXEC;
 447         break;
 448     case PORT_ROLE_SELECTION_SM_ROLE_SELECTION_EXEC:
 449         clear_reselect_tree(r);
 450         updt_roles_tree__(r);
 451         set_selected_tree(r);
 452         r->port_role_selection_sm_state =
 453             PORT_ROLE_SELECTION_SM_ROLE_SELECTION;
 454         /* no break */
 455     case PORT_ROLE_SELECTION_SM_ROLE_SELECTION:
 456         HMAP_FOR_EACH (p, node, &r->ports) {
 457             if (p->reselect) {
 458                 r->port_role_selection_sm_state =
 459                     PORT_ROLE_SELECTION_SM_ROLE_SELECTION_EXEC;
 460                 break;
 461             }
 462         }
 463         break;
 464     default:
 465         OVS_NOT_REACHED();
 466         /* no break */
 467     }
 468     if (old_state != r->port_role_selection_sm_state) {
 469         r->changes = true;
 470         VLOG_DBG("%s: Port_role_selection_sm %d -> %d", r->name,
 471                  old_state, r->port_role_selection_sm_state);
 472     }
 473     return 0;
 474 }
 475
 476 /* Port State Machines */
 477
 478 /* [17.23 - Port receive state machine] */
 479
 480 static void
 481 updt_bpdu_version(struct rstp_port *p)  /* [17.21.22] */
 482     OVS_REQUIRES(rstp_mutex)
 483 {
 484     switch (p->received_bpdu_buffer.bpdu_type) {
 485     case CONFIGURATION_BPDU:
 486     case TOPOLOGY_CHANGE_NOTIFICATION_BPDU:
 487         p->rcvd_rstp = false;
 488         p->rcvd_stp = true;
 489         break;
 490     case RAPID_SPANNING_TREE_BPDU:
 491         p->rcvd_rstp = true;
 492         p->rcvd_stp = false;
 493         break;
 494     default:
 495         OVS_NOT_REACHED();
 496         /* no break */
 497     }
 498 }
 499
 500 static int
 501 port_receive_sm(struct rstp_port *p)
 502     OVS_REQUIRES(rstp_mutex)
 503 {
 504     enum port_receive_state_machine old_state;
 505     struct rstp *r;
 506
 507     old_state = p->port_receive_sm_state;
 508     r = p->rstp;
 509
 510     switch (p->port_receive_sm_state) {
 511     case PORT_RECEIVE_SM_INIT:
 512         if (r->begin || ((p->rcvd_bpdu || (p->edge_delay_while !=
 513                             r->migrate_time)) && !p->port_enabled)) {
 514             p->port_receive_sm_state = PORT_RECEIVE_SM_DISCARD_EXEC;
 515         }
 516         break;
 517     case PORT_RECEIVE_SM_DISCARD_EXEC:
 518         p->rcvd_bpdu = p->rcvd_rstp = p->rcvd_stp = false;
 519         p->rcvd_msg = false;
 520         p->edge_delay_while = r->migrate_time;
 521         p->port_receive_sm_state = PORT_RECEIVE_SM_DISCARD;
 522         /* no break */
 523     case PORT_RECEIVE_SM_DISCARD:
 524         if ((p->rcvd_bpdu || (p->edge_delay_while != r->migrate_time))
 525             && !p->port_enabled) {
 526             /* Global transition. */
 527             p->port_receive_sm_state = PORT_RECEIVE_SM_DISCARD_EXEC;
 528         } else if (p->rcvd_bpdu && p->port_enabled) {
 529             p->port_receive_sm_state = PORT_RECEIVE_SM_RECEIVE_EXEC;
 530         }
 531         break;
 532     case PORT_RECEIVE_SM_RECEIVE_EXEC:
 533         updt_bpdu_version(p);
 534         p->oper_edge = p->rcvd_bpdu = false;
 535         p->rcvd_msg = true;
 536         p->edge_delay_while = r->migrate_time;
 537         p->port_receive_sm_state = PORT_RECEIVE_SM_RECEIVE;
 538         /* no break */
 539     case PORT_RECEIVE_SM_RECEIVE:
 540         if ((p->rcvd_bpdu || (p->edge_delay_while != r->migrate_time))
 541             && !p->port_enabled) {
 542             /* Global transition. */
 543             p->port_receive_sm_state = PORT_RECEIVE_SM_DISCARD_EXEC;
 544         } else if (p->rcvd_bpdu && p->port_enabled && !p->rcvd_msg) {
 545             p->port_receive_sm_state = PORT_RECEIVE_SM_RECEIVE_EXEC;
 546         }
 547         break;
 548     default:
 549         OVS_NOT_REACHED();
 550         /* no break */
 551     }
 552     if (old_state != p->port_receive_sm_state) {
 553         r->changes = true;
 554         VLOG_DBG("%s, port %u: Port_receive_sm %d -> %d", p->rstp->name,
 555                  p->port_number, old_state, p->port_receive_sm_state);
 556     }
 557     return 0;
 558 }
 559
 560 /* [17.24 - Port Protocol Migration state machine] */
 561 static int
 562 port_protocol_migration_sm(struct rstp_port *p)
 563     OVS_REQUIRES(rstp_mutex)
 564 {
 565     enum port_protocol_migration_state_machine old_state;
 566     struct rstp *r;
 567
 568     old_state = p->port_protocol_migration_sm_state;
 569     r = p->rstp;
 570
 571     switch (p->port_protocol_migration_sm_state) {
 572     case PORT_PROTOCOL_MIGRATION_SM_INIT:
 573         p->port_protocol_migration_sm_state =
 574             PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP_EXEC;
 575         /* no break */
 576     case PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP_EXEC:
 577         p->mcheck = false;
 578         p->send_rstp = r->rstp_version;
 579         p->mdelay_while = r->migrate_time;
 580         p->port_protocol_migration_sm_state =
 581             PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP;
 582         /* no break */
 583     case PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP:
 584         if (p->mdelay_while == 0) {
 585             p->port_protocol_migration_sm_state =
 586                 PORT_PROTOCOL_MIGRATION_SM_SENSING_EXEC;
 587         } else if ((p->mdelay_while != r->migrate_time) && !p->port_enabled) {
 588             p->port_protocol_migration_sm_state =
 589                 PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP_EXEC;
 590         }
 591         break;
 592     case PORT_PROTOCOL_MIGRATION_SM_SELECTING_STP_EXEC:
 593         p->send_rstp = false;
 594         p->mdelay_while = r->migrate_time;
 595         p->port_protocol_migration_sm_state =
 596             PORT_PROTOCOL_MIGRATION_SM_SELECTING_STP;
 597         /* no break */
 598     case PORT_PROTOCOL_MIGRATION_SM_SELECTING_STP:
 599         if ((p->mdelay_while == 0) || (!p->port_enabled) || p->mcheck) {
 600             p->port_protocol_migration_sm_state =
 601                 PORT_PROTOCOL_MIGRATION_SM_SENSING_EXEC;
 602         }
 603         break;
 604     case PORT_PROTOCOL_MIGRATION_SM_SENSING_EXEC:
 605         p->rcvd_rstp = false;
 606         p->rcvd_stp = false;
 607         p->port_protocol_migration_sm_state =
 608             PORT_PROTOCOL_MIGRATION_SM_SENSING;
 609         /* no break */
 610     case PORT_PROTOCOL_MIGRATION_SM_SENSING:
 611         if (!p->port_enabled || p->mcheck || ((r->rstp_version) &&
 612                                               !p->send_rstp && p->rcvd_rstp)) {
 613             p->port_protocol_migration_sm_state =
 614                 PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP_EXEC;
 615         } else if (p->send_rstp && p->rcvd_stp) {
 616             p->port_protocol_migration_sm_state =
 617                 PORT_PROTOCOL_MIGRATION_SM_SELECTING_STP_EXEC;
 618         }
 619         break;
 620     default:
 621         OVS_NOT_REACHED();
 622         /* no break */
 623     }
 624     if (old_state != p->port_protocol_migration_sm_state) {
 625         r->changes = true;
 626         VLOG_DBG("%s, port %u: port_protocol_migration_sm %d -> %d",
 627                  p->rstp->name, p->port_number, old_state,
 628                  p->port_protocol_migration_sm_state);
 629     }
 630
 631     return 0;
 632 }
 633
 634 /* [17.25 - Bridge Detection state machine] */
 635 static int
 636 bridge_detection_sm(struct rstp_port *p)
 637     OVS_REQUIRES(rstp_mutex)
 638 {
 639     enum bridge_detection_state_machine old_state;
 640     struct rstp *r;
 641
 642     old_state = p->bridge_detection_sm_state;
 643     r = p->rstp;
 644
 645     switch (p->bridge_detection_sm_state) {
 646     case BRIDGE_DETECTION_SM_INIT:
 647         if (r->begin && p->admin_edge) {
 648             p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_EDGE_EXEC;
 649         } else if (r->begin && !p->admin_edge) {
 650             p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_NOT_EDGE_EXEC;
 651         }
 652         break;
 653     case BRIDGE_DETECTION_SM_EDGE_EXEC:
 654         p->oper_edge = true;
 655         p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_EDGE;
 656         /* no break */
 657     case BRIDGE_DETECTION_SM_EDGE:
 658         if ((!p->port_enabled && !p->admin_edge) || !p->oper_edge) {
 659             p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_NOT_EDGE_EXEC;
 660         }
 661         break;
 662     case BRIDGE_DETECTION_SM_NOT_EDGE_EXEC:
 663         p->oper_edge = false;
 664         p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_NOT_EDGE;
 665         /* no break */
 666     case BRIDGE_DETECTION_SM_NOT_EDGE:
 667         if ((!p->port_enabled && p->admin_edge)
 668             || ((p->edge_delay_while == 0) && p->auto_edge && p->send_rstp
 669                 && p->proposing)) {
 670             p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_EDGE_EXEC;
 671         }
 672         break;
 673     default:
 674         OVS_NOT_REACHED();
 675         /* no break */
 676     }
 677     if (old_state != p->bridge_detection_sm_state) {
 678         r->changes = true;
 679         VLOG_DBG("%s, port %u: bridge_detection_sm %d -> %d", p->rstp->name,
 680                  p->port_number, old_state, p->bridge_detection_sm_state);
 681     }
 682     return 0;
 683 }
 684
 685 /* [17.26 - Port Transmit state machine] */
 686 static void
 687 rstp_send_bpdu(struct rstp_port *p, const void *bpdu, size_t bpdu_size)
 688     OVS_REQUIRES(rstp_mutex)
 689 {
 690     struct eth_header *eth;
 691     struct llc_header *llc;
 692     struct ofpbuf *pkt;
 693
 694     /* Skeleton. */
 695     pkt = ofpbuf_new(ETH_HEADER_LEN + LLC_HEADER_LEN + bpdu_size);
 696     eth = ofpbuf_put_zeros(pkt, sizeof *eth);
 697     llc = ofpbuf_put_zeros(pkt, sizeof *llc);
 698     ofpbuf_set_frame(pkt, eth);
 699     ofpbuf_set_l3(pkt, ofpbuf_put(pkt, bpdu, bpdu_size));
 700
 701     /* 802.2 header. */
 702     memcpy(eth->eth_dst, eth_addr_stp, ETH_ADDR_LEN);
 703     /* p->rstp->send_bpdu() must fill in source address. */
 704     eth->eth_type = htons(ofpbuf_size(pkt) - ETH_HEADER_LEN);
 705
 706     /* LLC header. */
 707     llc->llc_dsap = STP_LLC_DSAP;
 708     llc->llc_ssap = STP_LLC_SSAP;
 709     llc->llc_cntl = STP_LLC_CNTL;
 710     p->rstp->send_bpdu(pkt, p->aux, p->rstp->aux);
 711 }
 712
 713 static void
 714 record_agreement(struct rstp_port *p)
 715     OVS_REQUIRES(rstp_mutex)
 716 {
 717     struct rstp *r;
 718
 719     r = p->rstp;
 720     if (r->rstp_version && p->oper_point_to_point_mac &&
 721         ((p->received_bpdu_buffer.flags & BPDU_FLAG_AGREEMENT))) {
 722         p->agreed = true;
 723         p->proposing = false;
 724     } else {
 725         p->agreed = false;
 726     }
 727 }
 728
 729 static void
 730 set_tc_flags(struct rstp_port *p)
 731     OVS_REQUIRES(rstp_mutex)
 732 {
 733     /* Sets rcvd_tc and/or rcvd_tc_ack if the Topology Change and/or Topology
 734      * Change Acknowledgment flags, respectively, are set in a ConfigBPDU or
 735      * RST BPDU.
 736      */
 737     if (p->received_bpdu_buffer.bpdu_type == CONFIGURATION_BPDU ||
 738         p->received_bpdu_buffer.bpdu_type == RAPID_SPANNING_TREE_BPDU) {
 739         if ((p->received_bpdu_buffer.flags & BPDU_FLAG_TOPCHANGE) != 0) {
 740             p->rcvd_tc = true;
 741         }
 742         if ((p->received_bpdu_buffer.flags & BPDU_FLAG_TOPCHANGEACK) != 0) {
 743             p->rcvd_tc_ack = true;
 744         }
 745     }
 746     /* Sets rcvd_tcn true if the BPDU is a TCN BPDU. */
 747     if (p->received_bpdu_buffer.bpdu_type
 748         == TOPOLOGY_CHANGE_NOTIFICATION_BPDU) {
 749         p->rcvd_tcn = true;
 750     }
 751 }
 752
 753 static void
 754 record_dispute(struct rstp_port *p)
 755     OVS_REQUIRES(rstp_mutex)
 756 {
 757     if ((p->received_bpdu_buffer.flags & BPDU_FLAG_LEARNING) != 0) {
 758         /* 802.1D-2004 says to set the agreed flag and to clear the proposing
 759          * flag. 802.1q-2008 instead says to set the disputed variable and to
 760          * clear the agreed variable. */
 761         p->disputed = true;
 762         p->agreed = false;
 763     }
 764 }
 765
 766 static void
 767 record_proposal(struct rstp_port *p)
 768     OVS_REQUIRES(rstp_mutex)
 769 {
 770     enum port_flag role =
 771         ((p->received_bpdu_buffer.flags) & ROLE_FLAG_MASK) >> ROLE_FLAG_SHIFT;
 772
 773     if ((role == PORT_DES)
 774         && ((p->received_bpdu_buffer.flags & BPDU_FLAG_PROPOSAL) != 0)) {
 775         p->proposed = true;
 776     }
 777 }
 778
 779 static void
 780 record_priority(struct rstp_port *p)
 781     OVS_REQUIRES(rstp_mutex)
 782 {
 783     p->port_priority.root_bridge_id = p->msg_priority.root_bridge_id;
 784     p->port_priority.root_path_cost = p->msg_priority.root_path_cost;
 785     p->port_priority.designated_bridge_id =
 786         p->msg_priority.designated_bridge_id;
 787     p->port_priority.designated_port_id = p->msg_priority.designated_port_id;
 788 }
 789
 790 static void
 791 record_times(struct rstp_port *p)
 792     OVS_REQUIRES(rstp_mutex)
 793 {
 794     p->port_times = p->msg_times;
 795     if (p->msg_times.hello_time == 0) {
 796         p->port_times.hello_time = 1;
 797     }
 798 }
 799
 800 static void
 801 updt_rcvd_info_while(struct rstp_port *p)
 802     OVS_REQUIRES(rstp_mutex)
 803 {
 804     /* [17.21.23]
 805      * The value assigned to rcvdInfoWhile is the three times the Hello Time,
 806      * if Message Age, incremented by 1 second and rounded to the nearest whole
 807      * second, does not exceed Max Age, and is zero otherwise.
 808      */
 809     if (p->port_times.message_age < p->port_times.max_age) {
 810         p->rcvd_info_while = p->port_times.hello_time * 3;
 811     } else {
 812         p->rcvd_info_while = 0;
 813     }
 814 }
 815
 816 /* Times are internally held in seconds, while the protocol uses 1/256 seconds.
 817  * time_encode() is used to convert time values sent in bpdus, while
 818  * time_decode() is used to convert time values received in bpdus.
 819  */
 820 static ovs_be16
 821 time_encode(uint8_t value)
 822 {
 823     return htons(value * 256);
 824 }
 825
 826 static uint8_t
 827 time_decode(ovs_be16 encoded)
 828 {
 829     return ntohs(encoded) / 256;
 830 }
 831
 832 /* [17.21.19] */
 833 static void
 834 tx_config(struct rstp_port *p)
 835     OVS_REQUIRES(rstp_mutex)
 836 {
 837     struct rstp_bpdu bpdu;
 838
 839     bpdu.protocol_identifier = htons(0);
 840     bpdu.protocol_version_identifier = 0;
 841     bpdu.bpdu_type = CONFIGURATION_BPDU;
 842     bpdu.root_bridge_id = htonll(p->designated_priority_vector.root_bridge_id);
 843     bpdu.root_path_cost = htonl(p->designated_priority_vector.root_path_cost);
 844     bpdu.designated_bridge_id =
 845         htonll(p->designated_priority_vector.designated_bridge_id);
 846     bpdu.designated_port_id =
 847         htons(p->designated_priority_vector.designated_port_id);
 848     bpdu.message_age = time_encode(p->designated_times.message_age);
 849     bpdu.max_age = time_encode(p->designated_times.max_age);
 850     bpdu.hello_time = time_encode(p->designated_times.hello_time);
 851     bpdu.forward_delay = time_encode(p->designated_times.forward_delay);
 852     bpdu.flags = 0;
 853     if (p->tc_while != 0) {
 854         bpdu.flags |= BPDU_FLAG_TOPCHANGE;
 855     }
 856     if (p->tc_ack != 0) {
 857         bpdu.flags |= BPDU_FLAG_TOPCHANGEACK;
 858     }
 859     rstp_send_bpdu(p, &bpdu, sizeof(struct rstp_bpdu));
 860 }
 861
 862 /* [17.21.20] */
 863 static void
 864 tx_rstp(struct rstp_port *p)
 865     OVS_REQUIRES(rstp_mutex)
 866 {
 867     struct rstp_bpdu bpdu;
 868
 869     bpdu.protocol_identifier = htons(0);
 870     bpdu.protocol_version_identifier = 2;
 871     bpdu.bpdu_type = RAPID_SPANNING_TREE_BPDU;
 872     bpdu.root_bridge_id = htonll(p->designated_priority_vector.root_bridge_id);
 873     bpdu.root_path_cost = htonl(p->designated_priority_vector.root_path_cost);
 874     bpdu.designated_bridge_id =
 875         htonll(p->designated_priority_vector.designated_bridge_id);
 876     bpdu.designated_port_id =
 877         htons(p->designated_priority_vector.designated_port_id);
 878     bpdu.message_age = time_encode(p->designated_times.message_age);
 879     bpdu.max_age = time_encode(p->designated_times.max_age);
 880     bpdu.hello_time = time_encode(p->designated_times.hello_time);
 881     bpdu.forward_delay = time_encode(p->designated_times.forward_delay);
 882     bpdu.flags = 0;
 883
 884     switch (p->role) {
 885     case ROLE_ROOT:
 886         bpdu.flags = PORT_ROOT << ROLE_FLAG_SHIFT;
 887         break;
 888     case ROLE_DESIGNATED:
 889         bpdu.flags = PORT_DES << ROLE_FLAG_SHIFT;
 890         break;
 891     case ROLE_ALTERNATE:
 892     case ROLE_BACKUP:
 893         bpdu.flags = PORT_ALT_BACK << ROLE_FLAG_SHIFT;
 894         break;
 895     case ROLE_DISABLED:
 896         /* Should not happen! */
 897         VLOG_ERR("%s transmitting bpdu in disabled role on port "
 898                  RSTP_PORT_ID_FMT, p->rstp->name, p->port_id);
 899         break;
 900     }
 901     if (p->agree) {
 902         bpdu.flags |= BPDU_FLAG_AGREEMENT;
 903     }
 904     if (p->proposing) {
 905         bpdu.flags |= BPDU_FLAG_PROPOSAL;
 906     }
 907     if (p->tc_while != 0) {
 908         bpdu.flags |= BPDU_FLAG_TOPCHANGE;
 909     }
 910     if (p->learning) {
 911         bpdu.flags |= BPDU_FLAG_LEARNING;
 912     }
 913     if (p->forwarding) {
 914         bpdu.flags |= BPDU_FLAG_FORWARDING;
 915     }
 916     bpdu.version1_length = 0;
 917     rstp_send_bpdu(p, &bpdu, sizeof(struct rstp_bpdu));
 918 }
 919
 920 /* [17.21.21] */
 921 static void
 922 tx_tcn(struct rstp_port *p)
 923     OVS_REQUIRES(rstp_mutex)
 924 {
 925     struct rstp_bpdu bpdu;
 926
 927     memset(&bpdu, 0, sizeof(struct rstp_bpdu));
 928
 929     bpdu.protocol_identifier = htons(0);
 930     bpdu.protocol_version_identifier = 0;
 931     bpdu.bpdu_type = TOPOLOGY_CHANGE_NOTIFICATION_BPDU;
 932     rstp_send_bpdu(p, &bpdu, sizeof(struct rstp_bpdu));
 933 }
 934
 935 static int
 936 port_transmit_sm(struct rstp_port *p)
 937     OVS_REQUIRES(rstp_mutex)
 938 {
 939     enum port_transmit_state_machine old_state;
 940     struct rstp *r;
 941
 942     old_state = p->port_transmit_sm_state;
 943     r = p->rstp;
 944
 945     switch (p->port_transmit_sm_state) {
 946     case PORT_TRANSMIT_SM_INIT:
 947         if (r->begin) {
 948             p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_INIT_EXEC;
 949         }
 950         break;
 951     case PORT_TRANSMIT_SM_TRANSMIT_INIT_EXEC:
 952         p->new_info = true;
 953         p->tx_count = 0;
 954         p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_INIT;
 955         /* no break */
 956     case PORT_TRANSMIT_SM_TRANSMIT_INIT:
 957         p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
 958         break;
 959     case PORT_TRANSMIT_SM_TRANSMIT_PERIODIC_EXEC:
 960         p->new_info = p->new_info || (p->role == ROLE_DESIGNATED ||
 961                       (p->role == ROLE_ROOT && p->tc_while != 0));
 962         p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_PERIODIC;
 963         /* no break */
 964     case PORT_TRANSMIT_SM_TRANSMIT_PERIODIC:
 965         p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
 966         break;
 967     case PORT_TRANSMIT_SM_IDLE_EXEC:
 968         p->hello_when = r->bridge_hello_time;
 969         p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE;
 970         /* no break */
 971     case PORT_TRANSMIT_SM_IDLE:
 972         if (p->role == ROLE_DISABLED) {
 973             VLOG_DBG("%s, port %u: port_transmit_sm ROLE == DISABLED.",
 974                      p->rstp->name, p->port_number);
 975             break;
 976         } else if (p->send_rstp && p->new_info
 977                    && p->tx_count < r->transmit_hold_count
 978                    && p->hello_when != 0 && p->selected && !p->updt_info) {
 979             p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_RSTP_EXEC;
 980         } else if (p->hello_when == 0 && p->selected && !p->updt_info) {
 981             p->port_transmit_sm_state =
 982                 PORT_TRANSMIT_SM_TRANSMIT_PERIODIC_EXEC;
 983         } else if (!p->send_rstp && p->new_info && p->role == ROLE_ROOT
 984                    && p->tx_count < r->transmit_hold_count
 985                    && p->hello_when != 0 && p->selected && !p->updt_info) {
 986             p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_TCN_EXEC;
 987         } else if (!p->send_rstp && p->new_info && p->role == ROLE_DESIGNATED
 988                    && p->tx_count < r->transmit_hold_count
 989                    && p->hello_when != 0 && p->selected && !p->updt_info) {
 990             p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_CONFIG_EXEC;
 991         }
 992         break;
 993     case PORT_TRANSMIT_SM_TRANSMIT_CONFIG_EXEC:
 994         p->new_info = false;
 995         tx_config(p);
 996         p->tx_count += 1;
 997         p->tc_ack = false;
 998         p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_CONFIG;
 999         /* no break */
1000     case PORT_TRANSMIT_SM_TRANSMIT_CONFIG:
1001         p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
1002         break;
1003     case PORT_TRANSMIT_SM_TRANSMIT_TCN_EXEC:
1004         p->new_info = false;
1005         tx_tcn(p);
1006         p->tx_count += 1;
1007         p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_TCN;
1008         /* no break */
1009     case PORT_TRANSMIT_SM_TRANSMIT_TCN:
1010         p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
1011         break;
1012     case PORT_TRANSMIT_SM_TRANSMIT_RSTP_EXEC:
1013         p->new_info = false;
1014         tx_rstp(p);
1015         p->tx_count += 1;
1016         p->tc_ack = false;
1017         p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_RSTP;
1018         /* no break */
1019     case PORT_TRANSMIT_SM_TRANSMIT_RSTP:
1020         p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
1021         break;
1022     default:
1023         OVS_NOT_REACHED();
1024         /* no break */
1025     }
1026     if (old_state != p->port_transmit_sm_state) {
1027         r->changes = true;
1028         VLOG_DBG("%s, port %u: port_transmit_sm %d -> %d", p->rstp->name,
1029                  p->port_number, old_state, p->port_transmit_sm_state);
1030     }
1031     return 0;
1032 }
1033
1034 /* [17.27 Port Information state machine] */
1035 #define RECEIVED 0
1036 #define MINE 1
1037
1038 static int
1039 rcv_info(struct rstp_port *p)
1040     OVS_REQUIRES(rstp_mutex)
1041 {
1042     enum vector_comparison cp;
1043     bool ct;
1044     enum port_flag role;
1045
1046     p->msg_priority.root_bridge_id =
1047         ntohll(p->received_bpdu_buffer.root_bridge_id);
1048     p->msg_priority.root_path_cost =
1049         ntohl(p->received_bpdu_buffer.root_path_cost);
1050     p->msg_priority.designated_bridge_id =
1051         ntohll(p->received_bpdu_buffer.designated_bridge_id);
1052     p->msg_priority.designated_port_id =
1053         ntohs(p->received_bpdu_buffer.designated_port_id);
1054
1055     p->msg_times.forward_delay =
1056         time_decode(p->received_bpdu_buffer.forward_delay);
1057     p->msg_times.hello_time = time_decode(p->received_bpdu_buffer.hello_time);
1058     p->msg_times.max_age = time_decode(p->received_bpdu_buffer.max_age);
1059     p->msg_times.message_age =
1060         time_decode(p->received_bpdu_buffer.message_age);
1061
1062     cp = compare_rstp_priority_vectors(&p->msg_priority, &p->port_priority);
1063     ct = rstp_times_equal(&p->port_times, &p->msg_times);
1064     /* Configuration BPDU conveys a Designated Port Role. */
1065     if (p->received_bpdu_buffer.bpdu_type == CONFIGURATION_BPDU) {
1066         role = PORT_DES;
1067     } else {
1068         role =
1069             (p->received_bpdu_buffer.flags & ROLE_FLAG_MASK) >> ROLE_FLAG_SHIFT;
1070     }
1071
1072     /* 802.1D-2004 does not report this behaviour.
1073      * 802.1Q-2008 says set rcvdTcn. */
1074     if (p->received_bpdu_buffer.bpdu_type ==
1075             TOPOLOGY_CHANGE_NOTIFICATION_BPDU) {
1076         p->rcvd_tcn = true;
1077         return OTHER_INFO;
1078     }
1079
1080     /* Returns SuperiorDesignatedInfo if:
1081      * a) The received message conveys a Designated Port Role, and
1082      *  1) The message priority is superior (17.6) to the Port.s port priority
1083      *     vector, or
1084      *  2) The message priority vector is the same as the Port.s port priority
1085      *     vector, and any of the received timer parameter values (msg_times.
1086      *     17.19.15) differ from those already held for the Port (port_times
1087      *     17.19.22).
1088      * NOTE: Configuration BPDU explicitly conveys a Designated Port Role.
1089      */
1090     if (role == PORT_DES && (cp == SUPERIOR || (cp == SAME && ct == false))) {
1091         return SUPERIOR_DESIGNATED_INFO;
1092
1093         /* Returns RepeatedDesignatedInfo if:
1094          * b) The received message conveys Designated Port Role, and a message
1095          *     priority vector and timer parameters that are the same as the
1096          *     Port's port priority vector or timer values. */
1097     } else if (role == PORT_DES && cp == SAME && ct == true) {
1098         return REPEATED_DESIGNATED_INFO;
1099
1100         /* Returns InferiorDesignatedInfo if:
1101          * c) The received message conveys a Designated Port Role, and a
1102          *    message priority vector that is worse than the Port's port
1103          *    priority vector. */
1104     } else if (role == PORT_DES && cp == INFERIOR) {
1105         return INFERIOR_DESIGNATED_INFO;
1106
1107         /* Returns InferiorRootAlternateInfo if:
1108          * d) The received message conveys a Root Port, Alternate Port, or
1109          *    Backup Port Role and a message priority that is the same as or
1110          *    worse than the port priority vector. */
1111     } else if ((role == PORT_ROOT || role == PORT_ALT_BACK) &&
1112                (cp == INFERIOR || cp == SAME)) {
1113         return INFERIOR_ROOT_ALTERNATE_INFO;
1114
1115         /* Otherwise, returns OtherInfo. */
1116     } else {
1117         return OTHER_INFO;
1118     }
1119 }
1120
1121 static int
1122 better_or_same_info(struct rstp_port *p, int new_info_is)
1123     OVS_REQUIRES(rstp_mutex)
1124 {
1125     return
1126         (new_info_is == RECEIVED && p->info_is == INFO_IS_RECEIVED
1127          && compare_rstp_priority_vectors(&p->msg_priority,
1128                                           &p->port_priority))
1129         || (new_info_is == MINE && p->info_is == INFO_IS_MINE
1130             && compare_rstp_priority_vectors(&p->designated_priority_vector,
1131                                              &p->port_priority));
1132 }
1133
1134 static int
1135 port_information_sm(struct rstp_port *p)
1136     OVS_REQUIRES(rstp_mutex)
1137 {
1138     enum port_information_state_machine old_state;
1139     struct rstp *r;
1140     struct rstp_port *p1;
1141
1142     old_state = p->port_information_sm_state;
1143     r = p->rstp;
1144
1145     switch (p->port_information_sm_state) {
1146     case PORT_INFORMATION_SM_INIT:
1147         if (r->begin
1148             || (!p->port_enabled && p->info_is != INFO_IS_DISABLED)) {
1149             p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1150         }
1151         break;
1152     case PORT_INFORMATION_SM_DISABLED_EXEC:
1153         p->rcvd_msg = false;
1154         p->proposing = p->proposed = p->agree = p->agreed = false;
1155         p->rcvd_info_while = 0;
1156         p->info_is = INFO_IS_DISABLED;
1157         p->reselect = true;
1158         p->selected = false;
1159         p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED;
1160         /* no break */
1161     case PORT_INFORMATION_SM_DISABLED:
1162         if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1163             /* Global transition. */
1164             p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1165         } else if (p->port_enabled) {
1166             p->port_information_sm_state = PORT_INFORMATION_SM_AGED_EXEC;
1167         } else if (p->rcvd_msg) {
1168             p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1169         }
1170         break;
1171     case PORT_INFORMATION_SM_AGED_EXEC:
1172         p->info_is = INFO_IS_AGED;
1173         p->reselect = true;
1174         p->selected = false;
1175         p->port_information_sm_state = PORT_INFORMATION_SM_AGED;
1176         /* no break */
1177     case PORT_INFORMATION_SM_AGED:
1178         if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1179             /* Global transition. */
1180             p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1181         } else if (p->selected && p->updt_info) {
1182             p->port_information_sm_state = PORT_INFORMATION_SM_UPDATE_EXEC;
1183         }
1184         break;
1185     case PORT_INFORMATION_SM_UPDATE_EXEC:
1186         p->proposing = p->proposed = false;
1187         /* MINE is not specified in Standard 802.1D-2004. */
1188         p->agreed = p->agreed && better_or_same_info(p, MINE);
1189         p->synced = p->synced && p->agreed;
1190         p->port_priority.root_bridge_id =
1191             p->designated_priority_vector.root_bridge_id;
1192         p->port_priority.root_path_cost =
1193             p->designated_priority_vector.root_path_cost;
1194         p->port_priority.designated_bridge_id =
1195             p->designated_priority_vector.designated_bridge_id;
1196         p->port_priority.designated_port_id =
1197             p->designated_priority_vector.designated_port_id;
1198         p->port_times = p->designated_times;
1199         p->updt_info = false;
1200         p->info_is = INFO_IS_MINE;
1201         p->new_info = true;
1202         p->port_information_sm_state = PORT_INFORMATION_SM_UPDATE;
1203         /* no break */
1204     case PORT_INFORMATION_SM_UPDATE:
1205         if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1206             /* Global transition. */
1207             p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1208         } else {
1209             p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1210         }
1211         break;
1212     case PORT_INFORMATION_SM_CURRENT_EXEC:
1213         p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT;
1214         /* no break */
1215     case PORT_INFORMATION_SM_CURRENT:
1216         if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1217             /* Global transition. */
1218             p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1219         } else if (p->rcvd_msg && !p->updt_info) {
1220             p->port_information_sm_state = PORT_INFORMATION_SM_RECEIVE_EXEC;
1221         } else if (p->selected && p->updt_info) {
1222             p->port_information_sm_state = PORT_INFORMATION_SM_UPDATE_EXEC;
1223         } else if ((p->info_is == INFO_IS_RECEIVED) &&
1224                    (p->rcvd_info_while == 0) && !p->updt_info &&
1225                    !p->rcvd_msg) {
1226             p->port_information_sm_state = PORT_INFORMATION_SM_AGED_EXEC;
1227         }
1228         break;
1229     case PORT_INFORMATION_SM_RECEIVE_EXEC:
1230         p->rcvd_info = rcv_info(p);
1231         p->port_information_sm_state = PORT_INFORMATION_SM_RECEIVE;
1232         /* no break */
1233     case PORT_INFORMATION_SM_RECEIVE:
1234         if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1235             /* Global transition. */
1236             p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1237         } else {
1238             switch (p->rcvd_info) {
1239             case SUPERIOR_DESIGNATED_INFO:
1240                 /* 802.1q-2008 has a checkBPDUConsistency() function, called on
1241                  * a BPDU reception.  checkBPDUConsistency() clears the agreed
1242                  * variable if the received message priority vector is superior
1243                  * to the port priority vector, the BPDU is an ST BPDU or an
1244                  * RST BPDU, its port role is Designated and its Learning flag
1245                  * is set. */
1246                 if (p->received_bpdu_buffer.flags & BPDU_FLAG_LEARNING) {
1247                     HMAP_FOR_EACH (p1, node, &r->ports) {
1248                         if (p1->port_number != p->port_number) {
1249                             p1->agreed = false;
1250                         }
1251                     }
1252                 }
1253                 p->port_information_sm_state =
1254                     PORT_INFORMATION_SM_SUPERIOR_DESIGNATED_EXEC;
1255                 break;
1256             case REPEATED_DESIGNATED_INFO:
1257                 p->port_information_sm_state =
1258                     PORT_INFORMATION_SM_REPEATED_DESIGNATED_EXEC;
1259                 break;
1260             case INFERIOR_DESIGNATED_INFO:
1261                 p->port_information_sm_state =
1262                     PORT_INFORMATION_SM_INFERIOR_DESIGNATED_EXEC;
1263                 break;
1264             case INFERIOR_ROOT_ALTERNATE_INFO:
1265                 p->port_information_sm_state =
1266                     PORT_INFORMATION_SM_NOT_DESIGNATED_EXEC;
1267                 break;
1268             case OTHER_INFO:
1269                 p->port_information_sm_state = PORT_INFORMATION_SM_OTHER_EXEC;
1270                 break;
1271             default:
1272                 OVS_NOT_REACHED();
1273                 /* no break */
1274             }
1275         }
1276         break;
1277     case PORT_INFORMATION_SM_OTHER_EXEC:
1278         p->rcvd_msg = false;
1279         p->port_information_sm_state = PORT_INFORMATION_SM_OTHER;
1280         /* no break */
1281     case PORT_INFORMATION_SM_OTHER:
1282         if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1283             /* Global transition. */
1284             p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1285         } else {
1286             p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1287         }
1288         break;
1289     case PORT_INFORMATION_SM_NOT_DESIGNATED_EXEC:
1290         record_agreement(p);
1291         set_tc_flags(p);
1292         p->rcvd_msg = false;
1293         p->port_information_sm_state = PORT_INFORMATION_SM_NOT_DESIGNATED;
1294         /* no break */
1295     case PORT_INFORMATION_SM_NOT_DESIGNATED:
1296         if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1297             /* Global transition. */
1298             p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1299         } else {
1300             p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1301         }
1302         break;
1303     case PORT_INFORMATION_SM_INFERIOR_DESIGNATED_EXEC:
1304         record_dispute(p);
1305         p->rcvd_msg = false;
1306         p->port_information_sm_state = PORT_INFORMATION_SM_INFERIOR_DESIGNATED;
1307         /* no break */
1308     case PORT_INFORMATION_SM_INFERIOR_DESIGNATED:
1309         if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1310             /* Global transition. */
1311             p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1312         } else {
1313             p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1314         }
1315         break;
1316     case PORT_INFORMATION_SM_REPEATED_DESIGNATED_EXEC:
1317         record_proposal(p);
1318         set_tc_flags(p);
1319         /* This record_agreement() is missing in 802.1D-2004, but it's present
1320          * in 802.1q-2008. */
1321         record_agreement(p);
1322         updt_rcvd_info_while(p);
1323         p->rcvd_msg = false;
1324         p->port_information_sm_state = PORT_INFORMATION_SM_REPEATED_DESIGNATED;
1325         /* no break */
1326     case PORT_INFORMATION_SM_REPEATED_DESIGNATED:
1327         if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1328             /* Global transition. */
1329             p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1330         } else {
1331             p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1332         }
1333         break;
1334     case PORT_INFORMATION_SM_SUPERIOR_DESIGNATED_EXEC:
1335         p->agreed = p->proposing = false;
1336         record_proposal(p);
1337         set_tc_flags(p);
1338         /* RECEIVED is not specified in Standard 802.1D-2004. */
1339         p->agree = p->agree && better_or_same_info(p, RECEIVED);
1340         /* This record_agreement() and the synced assignment are  missing in
1341          * 802.1D-2004, but they're present in 802.1q-2008. */
1342         record_agreement(p);
1343         p->synced = p->synced && p->agreed;
1344         record_priority(p);
1345         record_times(p);
1346         updt_rcvd_info_while(p);
1347         p->info_is = INFO_IS_RECEIVED;
1348         p->reselect = true;
1349         p->selected = false;
1350         p->rcvd_msg = false;
1351         p->port_information_sm_state = PORT_INFORMATION_SM_SUPERIOR_DESIGNATED;
1352         /* no break */
1353     case PORT_INFORMATION_SM_SUPERIOR_DESIGNATED:
1354         if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1355             /* Global transition. */
1356             p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1357         } else {
1358             p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1359         }
1360         break;
1361     default:
1362         OVS_NOT_REACHED();
1363         /* no break */
1364     }
1365     if (old_state != p->port_information_sm_state) {
1366         r->changes = true;
1367         VLOG_DBG("%s, port %u: Port_information_sm %d -> %d", p->rstp->name,
1368                  p->port_number, old_state, p->port_information_sm_state);
1369     }
1370     return 0;
1371 }
1372
1373 /* [17.29 Port Role Transitions state machine] */
1374
1375 static void
1376 set_re_root_tree(struct rstp_port *p)
1377     OVS_REQUIRES(rstp_mutex)
1378 {
1379     struct rstp *r;
1380     struct rstp_port *p1;
1381
1382     r = p->rstp;
1383     HMAP_FOR_EACH (p1, node, &r->ports) {
1384         p1->re_root = true;
1385     }
1386 }
1387
1388 static void
1389 set_sync_tree(struct rstp_port *p)
1390     OVS_REQUIRES(rstp_mutex)
1391 {
1392     struct rstp *r;
1393     struct rstp_port *p1;
1394
1395     r = p->rstp;
1396     HMAP_FOR_EACH (p1, node, &r->ports) {
1397         p1->sync = true;
1398     }
1399 }
1400
1401 static int
1402 hello_time(struct rstp_port *p)
1403     OVS_REQUIRES(rstp_mutex)
1404 {
1405     return p->designated_times.hello_time;
1406 }
1407
1408 static int
1409 fwd_delay(struct rstp_port *p)
1410     OVS_REQUIRES(rstp_mutex)
1411 {
1412     return p->designated_times.forward_delay;
1413 }
1414
1415 static int
1416 forward_delay(struct rstp_port *p)
1417     OVS_REQUIRES(rstp_mutex)
1418 {
1419     if (p->send_rstp) {
1420         return hello_time(p);
1421     } else {
1422         return fwd_delay(p);
1423     }
1424 }
1425
1426 static int
1427 edge_delay(struct rstp_port *p)
1428     OVS_REQUIRES(rstp_mutex)
1429 {
1430     struct rstp *r;
1431
1432     r = p->rstp;
1433     if (p->oper_point_to_point_mac == 1) {
1434         return r->migrate_time;
1435     } else {
1436         return p->designated_times.max_age;
1437     }
1438 }
1439
1440 static int
1441 check_selected_role_change(struct rstp_port *p, int current_role_state)
1442     OVS_REQUIRES(rstp_mutex)
1443 {
1444     if (p->selected && !p->updt_info && p->role != p->selected_role
1445         && p->selected_role != current_role_state) {
1446         VLOG_DBG("%s, port %u: case: current = %s role =  %s selected =  %d",
1447                  p->rstp->name, p->port_number,
1448                  rstp_port_role_name(current_role_state),
1449                  rstp_port_role_name(p->role), p->selected_role);
1450         switch (p->selected_role) {
1451         case ROLE_ROOT:
1452             p->port_role_transition_sm_state =
1453                 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1454             return true;
1455         case ROLE_DESIGNATED:
1456             p->port_role_transition_sm_state =
1457                 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1458             return true;
1459         case ROLE_ALTERNATE:
1460             p->port_role_transition_sm_state =
1461                 PORT_ROLE_TRANSITION_SM_BLOCK_PORT_EXEC;
1462             return true;
1463         case ROLE_BACKUP:
1464             p->port_role_transition_sm_state =
1465                 PORT_ROLE_TRANSITION_SM_BLOCK_PORT_EXEC;
1466             return true;
1467         case ROLE_DISABLED:
1468             p->port_role_transition_sm_state =
1469                 PORT_ROLE_TRANSITION_SM_DISABLE_PORT_EXEC;
1470             return true;
1471         }
1472     }
1473     return false;
1474 }
1475
1476 static int
1477 re_rooted(struct rstp_port *p)
1478     OVS_REQUIRES(rstp_mutex)
1479 {
1480     struct rstp *r;
1481     struct rstp_port *p1;
1482
1483     r = p->rstp;
1484     HMAP_FOR_EACH (p1, node, &r->ports) {
1485         if ((p1 != p) && (p1->rr_while != 0)) {
1486             return false;
1487         }
1488     }
1489     return true;
1490 }
1491
1492 static int
1493 all_synced(struct rstp *r)
1494     OVS_REQUIRES(rstp_mutex)
1495 {
1496     struct rstp_port *p;
1497
1498     HMAP_FOR_EACH (p, node, &r->ports) {
1499         if (!(p->selected && p->role == p->selected_role &&
1500               (p->role == ROLE_ROOT || p->synced == true))) {
1501             return false;
1502         }
1503     }
1504     return true;
1505 }
1506
1507 static int
1508 port_role_transition_sm(struct rstp_port *p)
1509     OVS_REQUIRES(rstp_mutex)
1510 {
1511     enum port_role_transition_state_machine old_state;
1512     struct rstp *r;
1513     enum rstp_port_role last_role;
1514
1515     old_state = p->port_role_transition_sm_state;
1516     r = p->rstp;
1517     last_role = p->role;
1518
1519     switch (p->port_role_transition_sm_state) {
1520     case PORT_ROLE_TRANSITION_SM_INIT:
1521         if (r->begin) {
1522             p->port_role_transition_sm_state =
1523                 PORT_ROLE_TRANSITION_SM_INIT_PORT_EXEC;
1524         }
1525         break;
1526     case PORT_ROLE_TRANSITION_SM_INIT_PORT_EXEC:
1527         p->role = ROLE_DISABLED;
1528         p->learn = p->forward = false;
1529         p->synced = false;
1530         p->sync = p->re_root = true;
1531         p->rr_while = p->designated_times.forward_delay;
1532         p->fd_while = p->designated_times.max_age;
1533         p->rb_while = 0;
1534         p->port_role_transition_sm_state =
1535             PORT_ROLE_TRANSITION_SM_DISABLE_PORT_EXEC;
1536         break;
1537     case PORT_ROLE_TRANSITION_SM_DISABLE_PORT_EXEC:
1538         p->role = p->selected_role;
1539         p->learn = p->forward = false;
1540         p->port_role_transition_sm_state =
1541             PORT_ROLE_TRANSITION_SM_DISABLE_PORT;
1542         /* no break */
1543     case PORT_ROLE_TRANSITION_SM_DISABLE_PORT:
1544         if (check_selected_role_change(p, ROLE_DISABLED)) {
1545             /* Global transition. */
1546         } else if (p->selected && !p->updt_info && !p->learning
1547                    && !p->forwarding) {
1548             p->port_role_transition_sm_state =
1549                 PORT_ROLE_TRANSITION_SM_DISABLED_PORT_EXEC;
1550         }
1551         break;
1552     case PORT_ROLE_TRANSITION_SM_DISABLED_PORT_EXEC:
1553         p->fd_while = p->designated_times.max_age;
1554         p->synced = true;
1555         p->rr_while = 0;
1556         p->sync = p->re_root = false;
1557         p->port_role_transition_sm_state =
1558             PORT_ROLE_TRANSITION_SM_DISABLED_PORT;
1559         /* no break */
1560     case PORT_ROLE_TRANSITION_SM_DISABLED_PORT:
1561         if (check_selected_role_change(p, ROLE_DISABLED)) {
1562             /* Global transition. */
1563         } else if (p->selected && !p->updt_info
1564                    && (p->fd_while != p->designated_times.max_age || p->sync
1565                        || p->re_root || !p->synced)) {
1566             p->port_role_transition_sm_state =
1567                 PORT_ROLE_TRANSITION_SM_DISABLED_PORT_EXEC;
1568         }
1569         break;
1570     case PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC:
1571         p->role = ROLE_ROOT;
1572         p->rr_while = p->designated_times.forward_delay;
1573         p->port_role_transition_sm_state = PORT_ROLE_TRANSITION_SM_ROOT_PORT;
1574         /* no break */
1575     case PORT_ROLE_TRANSITION_SM_ROOT_PORT:
1576         if (check_selected_role_change(p, ROLE_ROOT)) {
1577             /* Global transition. */
1578         } else if (p->selected && !p->updt_info) {
1579             if (p->rr_while != p->designated_times.forward_delay) {
1580                 p->port_role_transition_sm_state =
1581                     PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1582                 break;
1583             } else if (p->re_root && p->forward) {
1584                 p->port_role_transition_sm_state =
1585                     PORT_ROLE_TRANSITION_SM_REROOTED_EXEC;
1586                 break;
1587             } else if ((p->fd_while == 0
1588                         || ((re_rooted(p) && p->rb_while == 0)
1589                             && r->rstp_version)) && !p->learn) {
1590                 p->port_role_transition_sm_state =
1591                     PORT_ROLE_TRANSITION_SM_ROOT_LEARN_EXEC;
1592                 break;
1593             } else if ((p->fd_while == 0
1594                         || ((re_rooted(p) && p->rb_while == 0)
1595                             && r->rstp_version)) && p->learn && !p->forward) {
1596                 p->port_role_transition_sm_state =
1597                     PORT_ROLE_TRANSITION_SM_ROOT_FORWARD_EXEC;
1598                 break;
1599             } else if (p->proposed && !p->agree) {
1600                 p->port_role_transition_sm_state =
1601                     PORT_ROLE_TRANSITION_SM_ROOT_PROPOSED_EXEC;
1602                 break;
1603             } else if ((all_synced(r) && !p->agree) ||
1604                        (p->proposed && p->agree)) {
1605                 p->port_role_transition_sm_state =
1606                     PORT_ROLE_TRANSITION_SM_ROOT_AGREED_EXEC;
1607                 break;
1608             } else if (!p->forward && !p->re_root) {
1609                 p->port_role_transition_sm_state =
1610                     PORT_ROLE_TRANSITION_SM_REROOT_EXEC;
1611                 break;
1612             }
1613         }
1614         break;
1615     case PORT_ROLE_TRANSITION_SM_REROOT_EXEC:
1616         if (check_selected_role_change(p, ROLE_ROOT)) {
1617             /* Global transition. */
1618         } else {
1619             set_re_root_tree(p);
1620             p->port_role_transition_sm_state =
1621                 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1622         }
1623         break;
1624     case PORT_ROLE_TRANSITION_SM_ROOT_AGREED_EXEC:
1625         if (check_selected_role_change(p, ROLE_ROOT)) {
1626             /* Global transition. */
1627         } else {
1628             p->proposed = p->sync = false;
1629             p->agree = p->new_info = true;
1630             p->port_role_transition_sm_state =
1631                 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1632         }
1633         break;
1634     case PORT_ROLE_TRANSITION_SM_ROOT_PROPOSED_EXEC:
1635         set_sync_tree(p);
1636         p->proposed = false;
1637         if (check_selected_role_change(p, ROLE_ROOT)) {
1638             /* Global transition. */
1639         } else {
1640             p->port_role_transition_sm_state =
1641                 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1642         }
1643         break;
1644     case PORT_ROLE_TRANSITION_SM_ROOT_FORWARD_EXEC:
1645         p->fd_while = 0;
1646         p->forward = true;
1647         if (check_selected_role_change(p, ROLE_ROOT)) {
1648             /* Global transition. */
1649         } else {
1650             p->port_role_transition_sm_state =
1651                 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1652         }
1653         break;
1654     case PORT_ROLE_TRANSITION_SM_ROOT_LEARN_EXEC:
1655         p->fd_while = forward_delay(p);
1656         p->learn = true;
1657         if (check_selected_role_change(p, ROLE_ROOT)) {
1658             /* Global transition. */
1659         } else {
1660             p->port_role_transition_sm_state =
1661                 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1662         }
1663         break;
1664     case PORT_ROLE_TRANSITION_SM_REROOTED_EXEC:
1665         p->re_root = false;
1666         if (check_selected_role_change(p, ROLE_ROOT)) {
1667             /* Global transition. */
1668         } else {
1669             p->port_role_transition_sm_state =
1670                 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1671         }
1672         break;
1673     case PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC:
1674         p->role = ROLE_DESIGNATED;
1675         p->port_role_transition_sm_state =
1676             PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT;
1677         /* no break */
1678     case PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT:
1679         if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1680             /* Global transition. */
1681         } else if (p->selected && !p->updt_info) {
1682             if (((p->sync && !p->synced)
1683                  || (p->re_root && p->rr_while != 0) || p->disputed)
1684                 && !p->oper_edge && (p->learn || p->forward)) {
1685                 p->port_role_transition_sm_state =
1686                     PORT_ROLE_TRANSITION_SM_DESIGNATED_DISCARD_EXEC;
1687             } else if ((p->fd_while == 0 || p->agreed || p->oper_edge)
1688                        && (p->rr_while == 0 || !p->re_root)
1689                        && !p->sync && !p->learn) {
1690                 p->port_role_transition_sm_state =
1691                     PORT_ROLE_TRANSITION_SM_DESIGNATED_LEARN_EXEC;
1692             } else if ((p->fd_while == 0 || p->agreed || p->oper_edge)
1693                        && (p->rr_while == 0 || !p->re_root)
1694                        && !p->sync && (p->learn && !p->forward)) {
1695                 p->port_role_transition_sm_state =
1696                     PORT_ROLE_TRANSITION_SM_DESIGNATED_FORWARD_EXEC;
1697             } else if (!p->forward && !p->agreed && !p->proposing &&
1698                        !p->oper_edge) {
1699                 p->port_role_transition_sm_state =
1700                     PORT_ROLE_TRANSITION_SM_DESIGNATED_PROPOSE_EXEC;
1701             } else if ((!p->learning && !p->forwarding && !p->synced)
1702                        || (p->agreed && !p->synced)
1703                        || (p->oper_edge && !p->synced)
1704                        || (p->sync && p->synced)) {
1705                 p->port_role_transition_sm_state =
1706                     PORT_ROLE_TRANSITION_SM_DESIGNATED_SYNCED_EXEC;
1707             } else if (p->rr_while == 0 && p->re_root) {
1708                 p->port_role_transition_sm_state =
1709                     PORT_ROLE_TRANSITION_SM_DESIGNATED_RETIRED_EXEC;
1710             }
1711         }
1712         break;
1713     case PORT_ROLE_TRANSITION_SM_DESIGNATED_RETIRED_EXEC:
1714         p->re_root = false;
1715         if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1716             /* Global transition. */
1717         } else {
1718             p->port_role_transition_sm_state =
1719                 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1720         }
1721         break;
1722     case PORT_ROLE_TRANSITION_SM_DESIGNATED_SYNCED_EXEC:
1723         p->rr_while = 0;
1724         p->synced = true;
1725         p->sync = false;
1726         if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1727             /* Global transition. */
1728         } else {
1729             p->port_role_transition_sm_state =
1730                 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1731         }
1732         break;
1733     case PORT_ROLE_TRANSITION_SM_DESIGNATED_PROPOSE_EXEC:
1734         p->proposing = true;
1735         p->edge_delay_while = edge_delay(p);
1736         p->new_info = true;
1737         if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1738             /* Global transition. */
1739         } else {
1740             p->port_role_transition_sm_state =
1741                 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1742         }
1743         break;
1744     case PORT_ROLE_TRANSITION_SM_DESIGNATED_FORWARD_EXEC:
1745         p->forward = true;
1746         p->fd_while = 0;
1747         p->agreed = p->send_rstp;
1748         if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1749             /* Global transition. */
1750         } else {
1751             p->port_role_transition_sm_state =
1752                 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1753         }
1754         break;
1755     case PORT_ROLE_TRANSITION_SM_DESIGNATED_LEARN_EXEC:
1756         p->learn = true;
1757         p->fd_while = forward_delay(p);
1758         if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1759             /* Global transition. */
1760         } else {
1761             p->port_role_transition_sm_state =
1762                 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1763         }
1764         break;
1765     case PORT_ROLE_TRANSITION_SM_DESIGNATED_DISCARD_EXEC:
1766         p->learn = p->forward = p->disputed = false;
1767         p->fd_while = forward_delay(p);
1768         if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1769             /* Global transition. */
1770         } else {
1771             p->port_role_transition_sm_state =
1772                 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1773         }
1774         break;
1775     case PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC:
1776         p->fd_while = p->designated_times.forward_delay;
1777         p->synced = true;
1778         p->rr_while = 0;
1779         p->sync = p->re_root = false;
1780         p->port_role_transition_sm_state =
1781             PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT;
1782         /* no break */
1783     case PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT:
1784         if (check_selected_role_change(p, ROLE_ALTERNATE)) {
1785             /* Global transition. */
1786         } else if (p->selected && !p->updt_info) {
1787             if (p->rb_while != 2 * p->designated_times.hello_time
1788                 && p->role == ROLE_BACKUP) {
1789                 p->port_role_transition_sm_state =
1790                     PORT_ROLE_TRANSITION_SM_BACKUP_PORT_EXEC;
1791             } else if ((p->fd_while != forward_delay(p)) || p->sync
1792                        || p->re_root || !p->synced) {
1793                 p->port_role_transition_sm_state =
1794                     PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1795             } else if (p->proposed && !p->agree) {
1796                 p->port_role_transition_sm_state =
1797                     PORT_ROLE_TRANSITION_SM_ALTERNATE_PROPOSED_EXEC;
1798             } else if ((all_synced(r) && !p->agree)
1799                        || (p->proposed && p->agree)) {
1800                 p->port_role_transition_sm_state =
1801                     PORT_ROLE_TRANSITION_SM_ALTERNATE_AGREED_EXEC;
1802             }
1803         }
1804         break;
1805     case PORT_ROLE_TRANSITION_SM_ALTERNATE_AGREED_EXEC:
1806         p->proposed = false;
1807         p->agree = true;
1808         p->new_info = true;
1809         if (check_selected_role_change(p, ROLE_ALTERNATE)) {
1810             /* Global transition. */
1811         } else {
1812             p->port_role_transition_sm_state =
1813                 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1814         }
1815         break;
1816     case PORT_ROLE_TRANSITION_SM_ALTERNATE_PROPOSED_EXEC:
1817         set_sync_tree(p);
1818         p->proposed = false;
1819         if (check_selected_role_change(p, ROLE_ALTERNATE)) {
1820             /* Global transition. */
1821         } else {
1822             p->port_role_transition_sm_state =
1823                 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1824         }
1825         break;
1826     case PORT_ROLE_TRANSITION_SM_BLOCK_PORT_EXEC:
1827         p->role = p->selected_role;
1828         p->learn = p->forward = false;
1829         p->port_role_transition_sm_state = PORT_ROLE_TRANSITION_SM_BLOCK_PORT;
1830         /* no break */
1831     case PORT_ROLE_TRANSITION_SM_BLOCK_PORT:
1832         if (check_selected_role_change(p, ROLE_ALTERNATE)) {
1833             /* Global transition. */
1834         } else if (p->selected && !p->updt_info && !p->learning &&
1835                    !p->forwarding) {
1836             p->port_role_transition_sm_state =
1837                 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1838         }
1839         break;
1840     case PORT_ROLE_TRANSITION_SM_BACKUP_PORT_EXEC:
1841         p->rb_while = 2 * p->designated_times.hello_time;
1842         if (check_selected_role_change(p, ROLE_ALTERNATE)) {
1843             /* Global transition. */
1844         } else {
1845             p->port_role_transition_sm_state =
1846                 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1847         }
1848         break;
1849     default:
1850         OVS_NOT_REACHED();
1851         /* no break */
1852     }
1853     if (old_state != p->port_role_transition_sm_state) {
1854         r->changes = true;
1855         VLOG_DBG("%s, port %u: Port_role_transition_sm %d -> %d",
1856                  p->rstp->name, p->port_number, old_state,
1857                  p->port_role_transition_sm_state);
1858     }
1859     if (last_role != p->role) {
1860         last_role = p->role;
1861         VLOG_DBG("%s, port %u, port role ["RSTP_PORT_ID_FMT"] = %s",
1862                  p->rstp->name, p->port_number, p->port_id,
1863                  rstp_port_role_name(p->role));
1864     }
1865     return 0;
1866 }
1867
1868 /* [17.30 - Port state transition state machine] */
1869
1870 static void
1871 enable_learning(struct rstp_port *p)
1872     OVS_REQUIRES(rstp_mutex)
1873 {
1874     /* [17.21.6 enableLearning()] An implementation dependent procedure that
1875      * causes the Learning Process (7.8) to start learning from frames received
1876      * on the Port. The procedure does not complete until learning has been
1877      * enabled.
1878      */
1879     rstp_port_set_state__(p, RSTP_LEARNING);
1880 }
1881
1882 static void
1883 enable_forwarding(struct rstp_port *p)
1884     OVS_REQUIRES(rstp_mutex)
1885 {
1886     /* [17.21.5 enableForwarding()] An implementation dependent procedure that
1887      * causes the Forwarding Process (7.7) to start forwarding frames through
1888      * the Port. The procedure does not complete until forwarding has been
1889      * enabled.
1890      */
1891     rstp_port_set_state__(p, RSTP_FORWARDING);
1892 }
1893
1894 static void
1895 disable_learning(struct rstp_port *p)
1896     OVS_REQUIRES(rstp_mutex)
1897 {
1898     /* [17.21.4 - disableLearning()] An implementation dependent procedure that
1899      * causes the Learning Process (7.8) to stop learning from the source
1900      * address of frames received on the Port. The procedure does not complete
1901      * until learning has stopped.
1902      */
1903     rstp_port_set_state__(p, RSTP_DISCARDING);
1904 }
1905
1906 static void
1907 disable_forwarding(struct rstp_port *p)
1908     OVS_REQUIRES(rstp_mutex)
1909 {
1910     /* [17.21.3 - disableForwarding()] An implementation dependent procedure
1911      *  that causes the Forwarding Process (7.7) to stop forwarding frames
1912      * through the Port. The procedure does not complete until forwarding has
1913      * stopped.
1914      */
1915     rstp_port_set_state__(p, RSTP_DISCARDING);
1916 }
1917
1918 static int
1919 port_state_transition_sm(struct rstp_port *p)
1920     OVS_REQUIRES(rstp_mutex)
1921 {
1922     enum port_state_transition_state_machine old_state;
1923     struct rstp *r;
1924
1925     old_state = p->port_state_transition_sm_state;
1926     r = p->rstp;
1927
1928     switch (p->port_state_transition_sm_state) {
1929     case PORT_STATE_TRANSITION_SM_INIT:
1930         if (r->begin) {
1931             p->port_state_transition_sm_state =
1932                 PORT_STATE_TRANSITION_SM_DISCARDING_EXEC;
1933         }
1934         break;
1935     case PORT_STATE_TRANSITION_SM_DISCARDING_EXEC:
1936         disable_learning(p);
1937         p->learning = false;
1938         disable_forwarding(p);
1939         p->forwarding = false;
1940         p->port_state_transition_sm_state =
1941             PORT_STATE_TRANSITION_SM_DISCARDING;
1942         /* no break */
1943     case PORT_STATE_TRANSITION_SM_DISCARDING:
1944         if (p->learn) {
1945             p->port_state_transition_sm_state =
1946                 PORT_STATE_TRANSITION_SM_LEARNING_EXEC;
1947         }
1948         break;
1949     case PORT_STATE_TRANSITION_SM_LEARNING_EXEC:
1950         enable_learning(p);
1951         p->learning = true;
1952         p->port_state_transition_sm_state = PORT_STATE_TRANSITION_SM_LEARNING;
1953         /* no break */
1954     case PORT_STATE_TRANSITION_SM_LEARNING:
1955         if (!p->learn) {
1956             p->port_state_transition_sm_state =
1957                 PORT_STATE_TRANSITION_SM_DISCARDING_EXEC;
1958         } else if (p->forward) {
1959             p->port_state_transition_sm_state =
1960                 PORT_STATE_TRANSITION_SM_FORWARDING_EXEC;
1961         }
1962         break;
1963     case PORT_STATE_TRANSITION_SM_FORWARDING_EXEC:
1964         enable_forwarding(p);
1965         p->forwarding = true;
1966         p->port_state_transition_sm_state =
1967             PORT_STATE_TRANSITION_SM_FORWARDING;
1968         /* no break */
1969     case PORT_STATE_TRANSITION_SM_FORWARDING:
1970         if (!p->forward) {
1971             p->port_state_transition_sm_state =
1972                 PORT_STATE_TRANSITION_SM_DISCARDING_EXEC;
1973         }
1974         break;
1975     default:
1976         OVS_NOT_REACHED();
1977         /* no break */
1978     }
1979     if (old_state != p->port_state_transition_sm_state) {
1980         r->changes = true;
1981         VLOG_DBG("%s, port %u: Port_state_transition_sm %d -> %d",
1982                  p->rstp->name, p->port_number, old_state,
1983                  p->port_state_transition_sm_state);
1984     }
1985     return 0;
1986 }
1987
1988 /* [17.31 - Topology Change state machine] */
1989
1990 static void
1991 new_tc_while(struct rstp_port *p)
1992     OVS_REQUIRES(rstp_mutex)
1993 {
1994     struct rstp *r;
1995
1996     r = p->rstp;
1997     if (p->tc_while == 0 && p->send_rstp == true) {
1998         p->tc_while = r->bridge_hello_time + 1;
1999         p->new_info = true;
2000     } else if (p->tc_while == 0 && p->send_rstp == false) {
2001         p->tc_while = r->bridge_max_age + r->bridge_forward_delay;
2002     }
2003 }
2004
2005 /* [17.21.18 setTcPropTree()]
2006  * Sets tcprop for all Ports except the Port that called the procedure.
2007  */
2008 static void
2009 set_tc_prop_tree(struct rstp_port *p)
2010     OVS_REQUIRES(rstp_mutex)
2011 {
2012     struct rstp *r;
2013     struct rstp_port *p1;
2014
2015     r = p->rstp;
2016     HMAP_FOR_EACH (p1, node, &r->ports) {
2017         /* Set tc_prop on every port, except the one calling this
2018          * function. */
2019         if (p1->port_number != p->port_number) {
2020             p1->tc_prop = true;
2021         }
2022     }
2023 }
2024
2025 static void
2026 set_tc_prop_bridge(struct rstp_port *p)  /* not specified in 802.1D-2004. */
2027     OVS_REQUIRES(rstp_mutex)
2028 {
2029     set_tc_prop_tree(p); /* see 802.1w-2001. */
2030 }
2031
2032 static int
2033 topology_change_sm(struct rstp_port *p)
2034     OVS_REQUIRES(rstp_mutex)
2035 {
2036     enum topology_change_state_machine old_state;
2037     struct rstp *r;
2038
2039     old_state = p->topology_change_sm_state;
2040     r = p->rstp;
2041
2042     switch (p->topology_change_sm_state) {
2043     case TOPOLOGY_CHANGE_SM_INIT:
2044         if (r->begin) {
2045             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_INACTIVE_EXEC;
2046         }
2047         break;
2048     case TOPOLOGY_CHANGE_SM_INACTIVE_EXEC:
2049         p->fdb_flush = true;
2050         p->tc_while = 0;
2051         p->tc_ack = false;
2052         p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_INACTIVE;
2053         /* no break */
2054     case TOPOLOGY_CHANGE_SM_INACTIVE:
2055         if (p->learn && !p->fdb_flush) {
2056             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING_EXEC;
2057         }
2058         break;
2059     case TOPOLOGY_CHANGE_SM_LEARNING_EXEC:
2060         p->rcvd_tc = p->rcvd_tcn = p->rcvd_tc_ack = false;
2061         p->tc_prop = p->rcvd_tc_ack = false;
2062         p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING;
2063         /* no break */
2064     case TOPOLOGY_CHANGE_SM_LEARNING:
2065         if (p->role != ROLE_ROOT && p->role != ROLE_DESIGNATED &&
2066             !(p->learn || p->learning) && !(p->rcvd_tc || p->rcvd_tcn ||
2067                                             p->rcvd_tc_ack || p->tc_prop)) {
2068             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_INACTIVE_EXEC;
2069         } else if (p->rcvd_tc || p->rcvd_tcn || p->rcvd_tc_ack || p->tc_prop) {
2070             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING_EXEC;
2071         } else if ((p->role == ROLE_ROOT || p->role == ROLE_DESIGNATED)
2072                    && p->forward && !p->oper_edge) {
2073             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_DETECTED_EXEC;
2074         }
2075         break;
2076     case TOPOLOGY_CHANGE_SM_DETECTED_EXEC:
2077         new_tc_while(p);
2078         set_tc_prop_tree(p);
2079         p->new_info = true;
2080         p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE_EXEC;
2081         /* no break */
2082     case TOPOLOGY_CHANGE_SM_ACTIVE_EXEC:
2083         p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
2084         /* no break */
2085     case TOPOLOGY_CHANGE_SM_ACTIVE:
2086         if ((p->role != ROLE_ROOT && p->role != ROLE_DESIGNATED)
2087             || p->oper_edge) {
2088             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING_EXEC;
2089         } else if (p->rcvd_tcn) {
2090             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_NOTIFIED_TCN_EXEC;
2091         } else if (p->rcvd_tc) {
2092             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_NOTIFIED_TC_EXEC;
2093         } else if (p->tc_prop && !p->oper_edge) {
2094             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_PROPAGATING_EXEC;
2095         } else if (p->rcvd_tc_ack) {
2096             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACKNOWLEDGED_EXEC;
2097         }
2098         break;
2099     case TOPOLOGY_CHANGE_SM_ACKNOWLEDGED_EXEC:
2100         p->tc_while = 0;
2101         p->rcvd_tc_ack = false;
2102         p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
2103         break;
2104     case TOPOLOGY_CHANGE_SM_PROPAGATING_EXEC:
2105         new_tc_while(p);
2106         p->fdb_flush = true;
2107         p->tc_prop = false;
2108         p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
2109         break;
2110     case TOPOLOGY_CHANGE_SM_NOTIFIED_TC_EXEC:
2111         p->rcvd_tcn = p->rcvd_tc = false;
2112         if (p->role == ROLE_DESIGNATED) {
2113             p->tc_ack = true;
2114         }
2115         set_tc_prop_bridge(p);
2116         p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
2117         break;
2118     case TOPOLOGY_CHANGE_SM_NOTIFIED_TCN_EXEC:
2119         new_tc_while(p);
2120         p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_NOTIFIED_TC_EXEC;
2121         break;
2122     default:
2123         OVS_NOT_REACHED();
2124         /* no break */
2125     }
2126     if (old_state != p->topology_change_sm_state) {
2127         r->changes = true;
2128         VLOG_DBG("%s, port %u: Topology_change_sm %d -> %d", p->rstp->name,
2129                  p->port_number, old_state, p->topology_change_sm_state);
2130     }
2131     return 0;
2132 }
2133
2134 /****************************************************************************
2135  * [17.6] Priority vector calculation helper functions
2136  ****************************************************************************/
2137
2138 /* compare_rstp_priority_vectors() compares two struct rstp_priority_vectors
2139  * and returns a value indicating if the first rstp_priority_vector is
2140  * superior, same or inferior to the second one.
2141  *
2142  * Zero return value indicates INFERIOR, a non-zero return value indicates
2143  * SUPERIOR.  When it makes a difference the non-zero return value SAME
2144  * indicates the priority vectors are identical (a subset of SUPERIOR).
2145  */
2146 static enum vector_comparison
2147 compare_rstp_priority_vectors(const struct rstp_priority_vector *v1,
2148                              const struct rstp_priority_vector *v2)
2149 {
2150     VLOG_DBG("v1: "RSTP_ID_FMT", %u, "RSTP_ID_FMT", %d, %d",
2151              RSTP_ID_ARGS(v1->root_bridge_id), v1->root_path_cost,
2152              RSTP_ID_ARGS(v1->designated_bridge_id), v1->designated_port_id,
2153              v1->bridge_port_id);
2154     VLOG_DBG("v2: "RSTP_ID_FMT", %u, "RSTP_ID_FMT", %d, %d",
2155              RSTP_ID_ARGS(v2->root_bridge_id), v2->root_path_cost,
2156              RSTP_ID_ARGS(v2->designated_bridge_id), v2->designated_port_id,
2157              v2->bridge_port_id);
2158
2159     /* [17.6]
2160      * This message priority vector is superior to the port priority vector and
2161      * will replace it if, and only if, the message priority vector is better
2162      * than the port priority vector, or the message has been transmitted from
2163      * the same Designated Bridge and Designated Port as the port priority
2164      * vector, i.e., if the following is true:
2165      *
2166      *    ((RD  < RootBridgeID)) ||
2167      *    ((RD == RootBridgeID) && (RPCD < RootPathCost)) ||
2168      *    ((RD == RootBridgeID) && (RPCD == RootPathCost) &&
2169      *         (D < designated_bridge_id)) ||
2170      *    ((RD == RootBridgeID) && (RPCD == RootPathCost) &&
2171      *         (D == designated_bridge_id) && (PD < designated_port_id)) ||
2172      *    ((D  == designated_bridge_id.BridgeAddress) &&
2173      *         (PD == designated_port_id.PortNumber))
2174      */
2175     if ((v1->root_bridge_id < v2->root_bridge_id)
2176         || (v1->root_bridge_id == v2->root_bridge_id
2177             && v1->root_path_cost < v2->root_path_cost)
2178         || (v1->root_bridge_id == v2->root_bridge_id
2179             && v1->root_path_cost == v2->root_path_cost
2180             && v1->designated_bridge_id < v2->designated_bridge_id)
2181         || (v1->root_bridge_id == v2->root_bridge_id
2182             && v1->root_path_cost == v2->root_path_cost
2183             && v1->designated_bridge_id == v2->designated_bridge_id
2184             && v1->designated_port_id < v2->designated_port_id)
2185         || (v1->designated_bridge_id == v2->designated_bridge_id
2186             && v1->designated_port_id == v2->designated_port_id)) {
2187         /* SAME is a subset of SUPERIOR. */
2188         if (v1->root_bridge_id == v2->root_bridge_id
2189             && v1->root_path_cost == v2->root_path_cost
2190             && v1->designated_bridge_id == v2->designated_bridge_id
2191             && v1->designated_port_id == v2->designated_port_id) {
2192             if (v1->bridge_port_id < v2->bridge_port_id) {
2193                 VLOG_DBG("superior");
2194                 return SUPERIOR;
2195             }
2196             else if (v1->bridge_port_id > v2->bridge_port_id) {
2197                 VLOG_DBG("inferior");
2198                 return INFERIOR;
2199             }
2200             VLOG_DBG("superior_same");
2201             return SAME;
2202         }
2203         VLOG_DBG("superior");
2204         return SUPERIOR;
2205     }
2206
2207     VLOG_DBG("inferior");
2208     return INFERIOR;
2209 }
2210
2211 static bool
2212 rstp_times_equal(struct rstp_times *t1, struct rstp_times *t2)
2213 {
2214     return t1->forward_delay == t2->forward_delay
2215         && t1->hello_time == t2->hello_time
2216         && t1->max_age == t2->max_age
2217         && t1->message_age == t2->message_age;
2218 }