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