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