lib/rstp-state-machines.c

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