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