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     /* Configuration BPDU conveys a Designated Port Role. */
1033     if (p->received_bpdu_buffer.bpdu_type == CONFIGURATION_BPDU) {
1034         role = PORT_DES;
1035     } else {
1036         role =
1037             (p->received_bpdu_buffer.flags & ROLE_FLAG_MASK) >> ROLE_FLAG_SHIFT;
1038     }
1039
1040     /* 802.1D-2004 does not report this behaviour.
1041      * 802.1Q-2008 says set rcvdTcn. */
1042     if (p->received_bpdu_buffer.bpdu_type ==
1043             TOPOLOGY_CHANGE_NOTIFICATION_BPDU) {
1044         p->rcvd_tcn = true;
1045         return OTHER_INFO;
1046     }
1047
1048     /* Returns SuperiorDesignatedInfo if:
1049      * a) The received message conveys a Designated Port Role, and
1050      *  1) The message priority is superior (17.6) to the Port.s port priority
1051      *     vector, or
1052      *  2) The message priority vector is the same as the Port.s port priority
1053      *     vector, and any of the received timer parameter values (msg_times.
1054      *     17.19.15) differ from those already held for the Port (port_times
1055      *     17.19.22).
1056      * NOTE: Configuration BPDU explicitly conveys a Designated Port Role.
1057      */
1058     if (role == PORT_DES && (cp == SUPERIOR || (cp == SAME && ct == false))) {
1059         return SUPERIOR_DESIGNATED_INFO;
1060
1061         /* Returns RepeatedDesignatedInfo if:
1062          * b) The received message conveys Designated Port Role, and a message
1063          *     priority vector and timer parameters that are the same as the
1064          *     Port's port priority vector or timer values. */
1065     } else if (role == PORT_DES && cp == SAME && ct == true) {
1066         return REPEATED_DESIGNATED_INFO;
1067
1068         /* Returns InferiorDesignatedInfo if:
1069          * c) The received message conveys a Designated Port Role, and a
1070          *    message priority vector that is worse than the Port's port
1071          *    priority vector. */
1072     } else if (role == PORT_DES && cp == INFERIOR) {
1073         return INFERIOR_DESIGNATED_INFO;
1074
1075         /* Returns InferiorRootAlternateInfo if:
1076          * d) The received message conveys a Root Port, Alternate Port, or
1077          *    Backup Port Role and a message priority that is the same as or
1078          *    worse than the port priority vector. */
1079     } else if ((role == PORT_ROOT || role == PORT_ALT_BACK) &&
1080                (cp == INFERIOR || cp == SAME)) {
1081         return INFERIOR_ROOT_ALTERNATE_INFO;
1082
1083         /* Otherwise, returns OtherInfo. */
1084     } else {
1085         return OTHER_INFO;
1086     }
1087 }
1088
1089 static int
1090 better_or_same_info(struct rstp_port *p, int new_info_is)
1091     OVS_REQUIRES(rstp_mutex)
1092 {
1093     return
1094         (new_info_is == RECEIVED && p->info_is == INFO_IS_RECEIVED
1095          && compare_rstp_priority_vectors(&p->msg_priority,
1096                                           &p->port_priority))
1097         || (new_info_is == MINE && p->info_is == INFO_IS_MINE
1098             && compare_rstp_priority_vectors(&p->designated_priority_vector,
1099                                              &p->port_priority));
1100 }
1101
1102 static int
1103 port_information_sm(struct rstp_port *p)
1104     OVS_REQUIRES(rstp_mutex)
1105 {
1106     enum port_information_state_machine old_state;
1107     struct rstp *r;
1108
1109     old_state = p->port_information_sm_state;
1110     r = p->rstp;
1111
1112     if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1113         p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1114     }
1115     switch (p->port_information_sm_state) {
1116     case PORT_INFORMATION_SM_INIT:
1117         if (r->begin) {
1118             p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1119         }
1120         break;
1121     case PORT_INFORMATION_SM_DISABLED_EXEC:
1122         p->rcvd_msg = false;
1123         p->proposing = p->proposed = p->agree = p->agreed = false;
1124         p->rcvd_info_while = 0;
1125         p->info_is = INFO_IS_DISABLED;
1126         p->reselect = true;
1127         p->selected = false;
1128         p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED;
1129         /* no break */
1130     case PORT_INFORMATION_SM_DISABLED:
1131         if (p->port_enabled) {
1132             p->port_information_sm_state = PORT_INFORMATION_SM_AGED_EXEC;
1133         } else if (p->rcvd_msg) {
1134             p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1135         }
1136         break;
1137     case PORT_INFORMATION_SM_AGED_EXEC:
1138         p->info_is = INFO_IS_AGED;
1139         p->reselect = true;
1140         p->selected = false;
1141         p->port_information_sm_state = PORT_INFORMATION_SM_AGED;
1142         /* no break */
1143     case PORT_INFORMATION_SM_AGED:
1144         if (p->selected && p->updt_info) {
1145             p->port_information_sm_state = PORT_INFORMATION_SM_UPDATE_EXEC;
1146         }
1147         break;
1148     case PORT_INFORMATION_SM_UPDATE_EXEC:
1149         p->proposing = p->proposed = false;
1150         /* MINE is not specified in Standard 802.1D-2004. */
1151         p->agreed = p->agreed && better_or_same_info(p, MINE);
1152         p->synced = p->synced && p->agreed;
1153         p->port_priority.root_bridge_id =
1154             p->designated_priority_vector.root_bridge_id;
1155         p->port_priority.root_path_cost =
1156             p->designated_priority_vector.root_path_cost;
1157         p->port_priority.designated_bridge_id =
1158             p->designated_priority_vector.designated_bridge_id;
1159         p->port_priority.designated_port_id =
1160             p->designated_priority_vector.designated_port_id;
1161         p->port_times = p->designated_times;
1162         p->updt_info = false;
1163         p->info_is = INFO_IS_MINE;
1164         p->new_info = true;
1165         p->port_information_sm_state = PORT_INFORMATION_SM_UPDATE;
1166         /* no break */
1167     case PORT_INFORMATION_SM_UPDATE:
1168         p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1169         break;
1170     case PORT_INFORMATION_SM_CURRENT_EXEC:
1171         p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT;
1172         /* no break */
1173     case PORT_INFORMATION_SM_CURRENT:
1174         if (p->rcvd_msg && !p->updt_info) {
1175             p->port_information_sm_state = PORT_INFORMATION_SM_RECEIVE_EXEC;
1176         } else if (p->selected && p->updt_info) {
1177             p->port_information_sm_state = PORT_INFORMATION_SM_UPDATE_EXEC;
1178         } else if ((p->info_is == INFO_IS_RECEIVED) &&
1179                    (p->rcvd_info_while == 0) && !p->updt_info &&
1180                    !p->rcvd_msg) {
1181             p->port_information_sm_state = PORT_INFORMATION_SM_AGED_EXEC;
1182         }
1183         break;
1184     case PORT_INFORMATION_SM_RECEIVE_EXEC:
1185         p->rcvd_info = rcv_info(p);
1186         p->port_information_sm_state = PORT_INFORMATION_SM_RECEIVE;
1187         /* no break */
1188     case PORT_INFORMATION_SM_RECEIVE:
1189         switch (p->rcvd_info) {
1190         case SUPERIOR_DESIGNATED_INFO:
1191             p->port_information_sm_state =
1192                 PORT_INFORMATION_SM_SUPERIOR_DESIGNATED_EXEC;
1193             break;
1194         case REPEATED_DESIGNATED_INFO:
1195             p->port_information_sm_state =
1196                 PORT_INFORMATION_SM_REPEATED_DESIGNATED_EXEC;
1197             break;
1198         case INFERIOR_DESIGNATED_INFO:
1199             p->port_information_sm_state =
1200                 PORT_INFORMATION_SM_INFERIOR_DESIGNATED_EXEC;
1201             break;
1202         case INFERIOR_ROOT_ALTERNATE_INFO:
1203             p->port_information_sm_state =
1204                 PORT_INFORMATION_SM_NOT_DESIGNATED_EXEC;
1205             break;
1206         case OTHER_INFO:
1207             p->port_information_sm_state = PORT_INFORMATION_SM_OTHER_EXEC;
1208             break;
1209         default:
1210             OVS_NOT_REACHED();
1211             /* no break */
1212         }
1213         break;
1214     case PORT_INFORMATION_SM_OTHER_EXEC:
1215         p->rcvd_msg = false;
1216         p->port_information_sm_state = PORT_INFORMATION_SM_OTHER;
1217         /* no break */
1218     case PORT_INFORMATION_SM_OTHER:
1219         p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1220         break;
1221     case PORT_INFORMATION_SM_NOT_DESIGNATED_EXEC:
1222         record_agreement(p);
1223         set_tc_flags(p);
1224         p->rcvd_msg = false;
1225         p->port_information_sm_state = PORT_INFORMATION_SM_NOT_DESIGNATED;
1226         /* no break */
1227     case PORT_INFORMATION_SM_NOT_DESIGNATED:
1228         p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1229         break;
1230     case PORT_INFORMATION_SM_INFERIOR_DESIGNATED_EXEC:
1231         record_dispute(p);
1232         p->rcvd_msg = false;
1233         p->port_information_sm_state = PORT_INFORMATION_SM_INFERIOR_DESIGNATED;
1234         /* no break */
1235     case PORT_INFORMATION_SM_INFERIOR_DESIGNATED:
1236         p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1237         break;
1238     case PORT_INFORMATION_SM_REPEATED_DESIGNATED_EXEC:
1239         record_proposal(p);
1240         set_tc_flags(p);
1241         updt_rcvd_info_while(p);
1242         p->rcvd_msg = false;
1243         p->port_information_sm_state = PORT_INFORMATION_SM_REPEATED_DESIGNATED;
1244         /* no break */
1245     case PORT_INFORMATION_SM_REPEATED_DESIGNATED:
1246         p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1247         break;
1248     case PORT_INFORMATION_SM_SUPERIOR_DESIGNATED_EXEC:
1249         p->agreed = p->proposing = false;
1250         record_proposal(p);
1251         set_tc_flags(p);
1252         /* RECEIVED is not specified in Standard 802.1D-2004. */
1253         p->agree = p->agree && better_or_same_info(p, RECEIVED);
1254         record_priority(p);
1255         record_times(p);
1256         updt_rcvd_info_while(p);
1257         p->info_is = INFO_IS_RECEIVED;
1258         p->reselect = true;
1259         p->selected = false;
1260         p->rcvd_msg = false;
1261         p->port_information_sm_state = PORT_INFORMATION_SM_SUPERIOR_DESIGNATED;
1262         /* no break */
1263     case PORT_INFORMATION_SM_SUPERIOR_DESIGNATED:
1264         p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1265         break;
1266     default:
1267         OVS_NOT_REACHED();
1268         /* no break */
1269     }
1270     if (old_state != p->port_information_sm_state) {
1271         r->changes = true;
1272         VLOG_DBG("%s, port %u: Port_information_sm %d -> %d", p->rstp->name,
1273                  p->port_number, old_state, p->port_information_sm_state);
1274     }
1275     return 0;
1276 }
1277
1278 /* [17.29 Port Role Transitions state machine] */
1279
1280 static void
1281 set_re_root_tree(struct rstp_port *p)
1282     OVS_REQUIRES(rstp_mutex)
1283 {
1284     struct rstp *r;
1285     struct rstp_port *p1;
1286
1287     r = p->rstp;
1288     HMAP_FOR_EACH (p1, node, &r->ports) {
1289         p1->re_root = true;
1290     }
1291 }
1292
1293 static void
1294 set_sync_tree(struct rstp_port *p)
1295     OVS_REQUIRES(rstp_mutex)
1296 {
1297     struct rstp *r;
1298     struct rstp_port *p1;
1299
1300     r = p->rstp;
1301     HMAP_FOR_EACH (p1, node, &r->ports) {
1302         p1->sync = true;
1303     }
1304 }
1305
1306 static int
1307 hello_time(struct rstp_port *p)
1308     OVS_REQUIRES(rstp_mutex)
1309 {
1310     return p->designated_times.hello_time;
1311 }
1312
1313 static int
1314 fwd_delay(struct rstp_port *p)
1315     OVS_REQUIRES(rstp_mutex)
1316 {
1317     return p->designated_times.forward_delay;
1318 }
1319
1320 static int
1321 forward_delay(struct rstp_port *p)
1322     OVS_REQUIRES(rstp_mutex)
1323 {
1324     if (p->send_rstp) {
1325         return hello_time(p);
1326     } else {
1327         return fwd_delay(p);
1328     }
1329 }
1330
1331 static int
1332 edge_delay(struct rstp_port *p)
1333     OVS_REQUIRES(rstp_mutex)
1334 {
1335     struct rstp *r;
1336
1337     r = p->rstp;
1338     if (p->oper_point_to_point_mac == 1) {
1339         return r->migrate_time;
1340     } else {
1341         return p->designated_times.max_age;
1342     }
1343 }
1344
1345 static int
1346 check_selected_role_change(struct rstp_port *p, int current_role_state)
1347     OVS_REQUIRES(rstp_mutex)
1348 {
1349     if (p->selected && !p->updt_info && p->role != p->selected_role
1350         && p->selected_role != current_role_state) {
1351         VLOG_DBG("%s, port %u: case: current = %s role =  %s selected =  %d",
1352                  p->rstp->name, p->port_number,
1353                  rstp_port_role_name(current_role_state),
1354                  rstp_port_role_name(p->role), p->selected_role);
1355         switch (p->selected_role) {
1356         case ROLE_ROOT:
1357             p->port_role_transition_sm_state =
1358                 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1359             return true;
1360         case ROLE_DESIGNATED:
1361             p->port_role_transition_sm_state =
1362                 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1363             return true;
1364         case ROLE_ALTERNATE:
1365             p->port_role_transition_sm_state =
1366                 PORT_ROLE_TRANSITION_SM_BLOCK_PORT_EXEC;
1367             return true;
1368         case ROLE_BACKUP:
1369             p->port_role_transition_sm_state =
1370                 PORT_ROLE_TRANSITION_SM_BLOCK_PORT_EXEC;
1371             return true;
1372         case ROLE_DISABLED:
1373             p->port_role_transition_sm_state =
1374                 PORT_ROLE_TRANSITION_SM_DISABLE_PORT_EXEC;
1375             return true;
1376         }
1377     }
1378     return false;
1379 }
1380
1381 static int
1382 re_rooted(struct rstp_port *p)
1383     OVS_REQUIRES(rstp_mutex)
1384 {
1385     struct rstp *r;
1386     struct rstp_port *p1;
1387
1388     r = p->rstp;
1389     HMAP_FOR_EACH (p1, node, &r->ports) {
1390         if ((p1 != p) && (p1->rr_while != 0)) {
1391             return false;
1392         }
1393     }
1394     return true;
1395 }
1396
1397 static int
1398 all_synced(struct rstp *r)
1399     OVS_REQUIRES(rstp_mutex)
1400 {
1401     struct rstp_port *p;
1402
1403     HMAP_FOR_EACH (p, node, &r->ports) {
1404         if (!(p->selected && p->role == p->selected_role &&
1405               (p->role == ROLE_ROOT || p->synced == true))) {
1406             return false;
1407         }
1408     }
1409     return true;
1410 }
1411
1412 static int
1413 port_role_transition_sm(struct rstp_port *p)
1414     OVS_REQUIRES(rstp_mutex)
1415 {
1416     enum port_role_transition_state_machine old_state;
1417     struct rstp *r;
1418     enum rstp_port_role last_role;
1419
1420     old_state = p->port_role_transition_sm_state;
1421     r = p->rstp;
1422     last_role = p->role;
1423
1424     switch (p->port_role_transition_sm_state) {
1425     case PORT_ROLE_TRANSITION_SM_INIT:
1426         if (r->begin) {
1427             p->port_role_transition_sm_state =
1428                 PORT_ROLE_TRANSITION_SM_INIT_PORT_EXEC;
1429         }
1430         break;
1431     case PORT_ROLE_TRANSITION_SM_INIT_PORT_EXEC:
1432         p->role = ROLE_DISABLED;
1433         p->learn = p->forward = false;
1434         p->synced = false;
1435         p->sync = p->re_root = true;
1436         p->rr_while = p->designated_times.forward_delay;
1437         p->fd_while = p->designated_times.max_age;
1438         p->rb_while = 0;
1439         p->port_role_transition_sm_state =
1440             PORT_ROLE_TRANSITION_SM_DISABLE_PORT_EXEC;
1441         break;
1442     case PORT_ROLE_TRANSITION_SM_DISABLE_PORT_EXEC:
1443         p->role = p->selected_role;
1444         p->learn = p->forward = false;
1445         p->port_role_transition_sm_state =
1446             PORT_ROLE_TRANSITION_SM_DISABLE_PORT;
1447         /* no break */
1448     case PORT_ROLE_TRANSITION_SM_DISABLE_PORT:
1449         if (check_selected_role_change(p, ROLE_DISABLED)) {
1450             break;
1451         } else if (p->selected && !p->updt_info && !p->learning
1452                    && !p->forwarding) {
1453             p->port_role_transition_sm_state =
1454                 PORT_ROLE_TRANSITION_SM_DISABLED_PORT_EXEC;
1455         }
1456         break;
1457     case PORT_ROLE_TRANSITION_SM_DISABLED_PORT_EXEC:
1458         p->fd_while = p->designated_times.max_age;
1459         p->synced = true;
1460         p->rr_while = 0;
1461         p->sync = p->re_root = false;
1462         p->port_role_transition_sm_state =
1463             PORT_ROLE_TRANSITION_SM_DISABLED_PORT;
1464         /* no break */
1465     case PORT_ROLE_TRANSITION_SM_DISABLED_PORT:
1466         if (check_selected_role_change(p, ROLE_DISABLED)) {
1467             break;
1468         } else if (p->selected && !p->updt_info
1469                    && (p->fd_while != p->designated_times.max_age || p->sync
1470                        || p->re_root || !p->synced)) {
1471             p->port_role_transition_sm_state =
1472                 PORT_ROLE_TRANSITION_SM_DISABLED_PORT_EXEC;
1473         }
1474         break;
1475     case PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC:
1476         p->role = ROLE_ROOT;
1477         p->rr_while = p->designated_times.forward_delay;
1478         p->port_role_transition_sm_state = PORT_ROLE_TRANSITION_SM_ROOT_PORT;
1479         /* no break */
1480     case PORT_ROLE_TRANSITION_SM_ROOT_PORT:
1481         if (check_selected_role_change(p, ROLE_ROOT)) {
1482             break;
1483         } else if (p->selected && !p->updt_info) {
1484             if (p->rr_while != p->designated_times.forward_delay) {
1485                 p->port_role_transition_sm_state =
1486                     PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1487                 break;
1488             } else if (p->re_root && p->forward) {
1489                 p->port_role_transition_sm_state =
1490                     PORT_ROLE_TRANSITION_SM_REROOTED_EXEC;
1491                 break;
1492             } else if ((p->fd_while == 0
1493                         || ((re_rooted(p) && p->rb_while == 0)
1494                             && r->rstp_version)) && !p->learn) {
1495                 p->port_role_transition_sm_state =
1496                     PORT_ROLE_TRANSITION_SM_ROOT_LEARN_EXEC;
1497                 break;
1498             } else if ((p->fd_while == 0
1499                         || ((re_rooted(p) && p->rb_while == 0)
1500                             && r->rstp_version)) && p->learn && !p->forward) {
1501                 p->port_role_transition_sm_state =
1502                     PORT_ROLE_TRANSITION_SM_ROOT_FORWARD_EXEC;
1503                 break;
1504             } else if (p->proposed && !p->agree) {
1505                 p->port_role_transition_sm_state =
1506                     PORT_ROLE_TRANSITION_SM_ROOT_PROPOSED_EXEC;
1507                 break;
1508             } else if ((all_synced(r) && !p->agree) ||
1509                        (p->proposed && p->agree)) {
1510                 p->port_role_transition_sm_state =
1511                     PORT_ROLE_TRANSITION_SM_ROOT_AGREED_EXEC;
1512                 break;
1513             } else if (!p->forward && !p->re_root) {
1514                 p->port_role_transition_sm_state =
1515                     PORT_ROLE_TRANSITION_SM_REROOT_EXEC;
1516                 break;
1517             }
1518         }
1519     break;
1520     case PORT_ROLE_TRANSITION_SM_REROOT_EXEC:
1521         set_re_root_tree(p);
1522         p->port_role_transition_sm_state =
1523             PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1524         break;
1525     case PORT_ROLE_TRANSITION_SM_ROOT_AGREED_EXEC:
1526         p->proposed = p->sync = false;
1527         p->agree = p->new_info = true;
1528         p->port_role_transition_sm_state =
1529             PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1530         break;
1531     case PORT_ROLE_TRANSITION_SM_ROOT_PROPOSED_EXEC:
1532         set_sync_tree(p);
1533         p->proposed = false;
1534         p->port_role_transition_sm_state =
1535             PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1536         break;
1537     case PORT_ROLE_TRANSITION_SM_ROOT_FORWARD_EXEC:
1538         p->fd_while = 0;
1539         p->forward = true;
1540         p->port_role_transition_sm_state =
1541             PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1542         break;
1543     case PORT_ROLE_TRANSITION_SM_ROOT_LEARN_EXEC:
1544         p->fd_while = forward_delay(p);
1545         p->learn = true;
1546         p->port_role_transition_sm_state =
1547             PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1548         break;
1549     case PORT_ROLE_TRANSITION_SM_REROOTED_EXEC:
1550         p->re_root = false;
1551         p->port_role_transition_sm_state =
1552             PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1553         break;
1554     case PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC:
1555         p->role = ROLE_DESIGNATED;
1556         p->port_role_transition_sm_state =
1557             PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT;
1558         /* no break */
1559     case PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT:
1560         if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1561             break;
1562         } else if (p->selected && !p->updt_info) {
1563             if (((p->sync && !p->synced)
1564                  || (p->re_root && p->rr_while != 0) || p->disputed)
1565                 && !p->oper_edge && (p->learn || p->forward)) {
1566                 p->port_role_transition_sm_state =
1567                     PORT_ROLE_TRANSITION_SM_DESIGNATED_DISCARD_EXEC;
1568             } else if ((p->fd_while == 0 || p->agreed || p->oper_edge)
1569                        && (p->rr_while == 0 || !p->re_root)
1570                        && !p->sync && !p->learn) {
1571                 p->port_role_transition_sm_state =
1572                     PORT_ROLE_TRANSITION_SM_DESIGNATED_LEARN_EXEC;
1573             } else if ((p->fd_while == 0 || p->agreed || p->oper_edge)
1574                        && (p->rr_while == 0 || !p->re_root)
1575                        && !p->sync && (p->learn && !p->forward)) {
1576                 p->port_role_transition_sm_state =
1577                     PORT_ROLE_TRANSITION_SM_DESIGNATED_FORWARD_EXEC;
1578             } else if (!p->forward && !p->agreed && !p->proposing &&
1579                        !p->oper_edge) {
1580                 p->port_role_transition_sm_state =
1581                     PORT_ROLE_TRANSITION_SM_DESIGNATED_PROPOSE_EXEC;
1582             } else if ((!p->learning && !p->forwarding && !p->synced)
1583                        || (p->agreed && !p->synced)
1584                        || (p->oper_edge && !p->synced)
1585                        || (p->sync && p->synced)) {
1586                 p->port_role_transition_sm_state =
1587                     PORT_ROLE_TRANSITION_SM_DESIGNATED_SYNCED_EXEC;
1588             } else if (p->rr_while == 0 && p->re_root) {
1589                 p->port_role_transition_sm_state =
1590                     PORT_ROLE_TRANSITION_SM_DESIGNATED_RETIRED_EXEC;
1591             }
1592         }
1593         break;
1594     case PORT_ROLE_TRANSITION_SM_DESIGNATED_RETIRED_EXEC:
1595         p->re_root = false;
1596         p->port_role_transition_sm_state =
1597             PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1598         break;
1599     case PORT_ROLE_TRANSITION_SM_DESIGNATED_SYNCED_EXEC:
1600         p->rr_while = 0;
1601         p->synced = true;
1602         p->sync = false;
1603         p->port_role_transition_sm_state =
1604             PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1605         break;
1606     case PORT_ROLE_TRANSITION_SM_DESIGNATED_PROPOSE_EXEC:
1607         p->proposing = true;
1608         p->edge_delay_while = edge_delay(p);
1609         p->new_info = true;
1610         p->port_role_transition_sm_state =
1611             PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1612         break;
1613     case PORT_ROLE_TRANSITION_SM_DESIGNATED_FORWARD_EXEC:
1614         p->forward = true;
1615         p->fd_while = 0;
1616         p->agreed = p->send_rstp;
1617         p->port_role_transition_sm_state =
1618             PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1619         break;
1620     case PORT_ROLE_TRANSITION_SM_DESIGNATED_LEARN_EXEC:
1621         p->learn = true;
1622         p->fd_while = forward_delay(p);
1623         p->port_role_transition_sm_state =
1624             PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1625         break;
1626     case PORT_ROLE_TRANSITION_SM_DESIGNATED_DISCARD_EXEC:
1627         p->learn = p->forward = p->disputed = false;
1628         p->fd_while = forward_delay(p);
1629         p->port_role_transition_sm_state =
1630             PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1631         break;
1632     case PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC:
1633         p->fd_while = p->designated_times.forward_delay;
1634         p->synced = true;
1635         p->rr_while = 0;
1636         p->sync = p->re_root = false;
1637         p->port_role_transition_sm_state =
1638             PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT;
1639         /* no break */
1640     case PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT:
1641         if (check_selected_role_change(p, ROLE_ALTERNATE)) {
1642             break;
1643         } else if (p->selected && !p->updt_info) {
1644             if (p->rb_while != 2 * p->designated_times.hello_time
1645                 && p->role == ROLE_BACKUP) {
1646                 p->port_role_transition_sm_state =
1647                     PORT_ROLE_TRANSITION_SM_BACKUP_PORT_EXEC;
1648             } else if ((p->fd_while != forward_delay(p)) || p->sync
1649                        || p->re_root || !p->synced) {
1650                 p->port_role_transition_sm_state =
1651                     PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1652             } else if (p->proposed && !p->agree) {
1653                 p->port_role_transition_sm_state =
1654                     PORT_ROLE_TRANSITION_SM_ALTERNATE_PROPOSED_EXEC;
1655             } else if ((all_synced(r) && !p->agree)
1656                        || (p->proposed && p->agree)) {
1657                 p->port_role_transition_sm_state =
1658                     PORT_ROLE_TRANSITION_SM_ALTERNATE_AGREED_EXEC;
1659             }
1660         }
1661         break;
1662     case PORT_ROLE_TRANSITION_SM_ALTERNATE_AGREED_EXEC:
1663         p->proposed = false;
1664         p->agree = true;
1665         p->new_info = true;
1666         p->port_role_transition_sm_state =
1667             PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1668         break;
1669     case PORT_ROLE_TRANSITION_SM_ALTERNATE_PROPOSED_EXEC:
1670         set_sync_tree(p);
1671         p->proposed = false;
1672         p->port_role_transition_sm_state =
1673             PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1674         break;
1675     case PORT_ROLE_TRANSITION_SM_BLOCK_PORT_EXEC:
1676         p->role = p->selected_role;
1677         p->learn = p->forward = false;
1678         p->port_role_transition_sm_state = PORT_ROLE_TRANSITION_SM_BLOCK_PORT;
1679         /* no break */
1680     case PORT_ROLE_TRANSITION_SM_BLOCK_PORT:
1681         if (check_selected_role_change(p, ROLE_ALTERNATE)) {
1682             break;
1683         } else if (p->selected && !p->updt_info && !p->learning &&
1684                    !p->forwarding) {
1685             p->port_role_transition_sm_state =
1686                 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1687         }
1688         break;
1689     case PORT_ROLE_TRANSITION_SM_BACKUP_PORT_EXEC:
1690         p->rb_while = 2 * p->designated_times.hello_time;
1691         p->port_role_transition_sm_state =
1692             PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1693         break;
1694     default:
1695         OVS_NOT_REACHED();
1696         /* no break */
1697     }
1698     if (old_state != p->port_role_transition_sm_state) {
1699         r->changes = true;
1700         VLOG_DBG("%s, port %u: Port_role_transition_sm %d -> %d",
1701                  p->rstp->name, p->port_number, old_state,
1702                  p->port_role_transition_sm_state);
1703     }
1704     if (last_role != p->role) {
1705         last_role = p->role;
1706         VLOG_DBG("%s, port %u, port role ["RSTP_PORT_ID_FMT"] = %s",
1707                  p->rstp->name, p->port_number, p->port_id,
1708                  rstp_port_role_name(p->role));
1709     }
1710     return 0;
1711 }
1712
1713 /* [17.30 - Port state transition state machine] */
1714
1715 static void
1716 enable_learning(struct rstp_port *p)
1717     OVS_REQUIRES(rstp_mutex)
1718 {
1719     /* [17.21.6 enableLearning()] An implementation dependent procedure that
1720      * causes the Learning Process (7.8) to start learning from frames received
1721      * on the Port. The procedure does not complete until learning has been
1722      * enabled.
1723      */
1724     rstp_port_set_state__(p, RSTP_LEARNING);
1725 }
1726
1727 static void
1728 enable_forwarding(struct rstp_port *p)
1729     OVS_REQUIRES(rstp_mutex)
1730 {
1731     /* [17.21.5 enableForwarding()] An implementation dependent procedure that
1732      * causes the Forwarding Process (7.7) to start forwarding frames through
1733      * the Port. The procedure does not complete until forwarding has been
1734      * enabled.
1735      */
1736     rstp_port_set_state__(p, RSTP_FORWARDING);
1737 }
1738
1739 static void
1740 disable_learning(struct rstp_port *p)
1741     OVS_REQUIRES(rstp_mutex)
1742 {
1743     /* [17.21.4 - disableLearning()] An implementation dependent procedure that
1744      * causes the Learning Process (7.8) to stop learning from the source
1745      * address of frames received on the Port. The procedure does not complete
1746      * until learning has stopped.
1747      */
1748     rstp_port_set_state__(p, RSTP_DISCARDING);
1749 }
1750
1751 static void
1752 disable_forwarding(struct rstp_port *p)
1753     OVS_REQUIRES(rstp_mutex)
1754 {
1755     /* [17.21.3 - disableForwarding()] An implementation dependent procedure
1756      *  that causes the Forwarding Process (7.7) to stop forwarding frames
1757      * through the Port. The procedure does not complete until forwarding has
1758      * stopped.
1759      */
1760     rstp_port_set_state__(p, RSTP_DISCARDING);
1761 }
1762
1763 static int
1764 port_state_transition_sm(struct rstp_port *p)
1765     OVS_REQUIRES(rstp_mutex)
1766 {
1767     enum port_state_transition_state_machine old_state;
1768     struct rstp *r;
1769
1770     old_state = p->port_state_transition_sm_state;
1771     r = p->rstp;
1772
1773     switch (p->port_state_transition_sm_state) {
1774     case PORT_STATE_TRANSITION_SM_INIT:
1775         if (r->begin) {
1776             p->port_state_transition_sm_state =
1777                 PORT_STATE_TRANSITION_SM_DISCARDING_EXEC;
1778         }
1779         break;
1780     case PORT_STATE_TRANSITION_SM_DISCARDING_EXEC:
1781         disable_learning(p);
1782         p->learning = false;
1783         disable_forwarding(p);
1784         p->forwarding = false;
1785         p->port_state_transition_sm_state =
1786             PORT_STATE_TRANSITION_SM_DISCARDING;
1787         /* no break */
1788     case PORT_STATE_TRANSITION_SM_DISCARDING:
1789         if (p->learn) {
1790             p->port_state_transition_sm_state =
1791                 PORT_STATE_TRANSITION_SM_LEARNING_EXEC;
1792         }
1793         break;
1794     case PORT_STATE_TRANSITION_SM_LEARNING_EXEC:
1795         enable_learning(p);
1796         p->learning = true;
1797         p->port_state_transition_sm_state = PORT_STATE_TRANSITION_SM_LEARNING;
1798         /* no break */
1799     case PORT_STATE_TRANSITION_SM_LEARNING:
1800         if (!p->learn) {
1801             p->port_state_transition_sm_state =
1802                 PORT_STATE_TRANSITION_SM_DISCARDING_EXEC;
1803         } else if (p->forward) {
1804             p->port_state_transition_sm_state =
1805                 PORT_STATE_TRANSITION_SM_FORWARDING_EXEC;
1806         }
1807         break;
1808     case PORT_STATE_TRANSITION_SM_FORWARDING_EXEC:
1809         enable_forwarding(p);
1810         p->forwarding = true;
1811         p->port_state_transition_sm_state =
1812             PORT_STATE_TRANSITION_SM_FORWARDING;
1813         /* no break */
1814     case PORT_STATE_TRANSITION_SM_FORWARDING:
1815         if (!p->forward) {
1816             p->port_state_transition_sm_state =
1817                 PORT_STATE_TRANSITION_SM_DISCARDING_EXEC;
1818         }
1819         break;
1820     default:
1821         OVS_NOT_REACHED();
1822         /* no break */
1823     }
1824     if (old_state != p->port_state_transition_sm_state) {
1825         r->changes = true;
1826         VLOG_DBG("%s, port %u: Port_state_transition_sm %d -> %d",
1827                  p->rstp->name, p->port_number, old_state,
1828                  p->port_state_transition_sm_state);
1829     }
1830     return 0;
1831 }
1832
1833 /* [17.31 - Topology Change state machine] */
1834
1835 static void
1836 new_tc_while(struct rstp_port *p)
1837     OVS_REQUIRES(rstp_mutex)
1838 {
1839     struct rstp *r;
1840
1841     r = p->rstp;
1842     if (p->tc_while == 0 && p->send_rstp == true) {
1843         p->tc_while = r->bridge_hello_time + 1;
1844         p->new_info = true;
1845     } else if (p->tc_while == 0 && p->send_rstp == false) {
1846         p->tc_while = r->bridge_max_age + r->bridge_forward_delay;
1847     }
1848 }
1849
1850 /* [17.21.18 setTcPropTree()]
1851  * Sets tcprop for all Ports except the Port that called the procedure.
1852  */
1853 static void
1854 set_tc_prop_tree(struct rstp_port *p)
1855     OVS_REQUIRES(rstp_mutex)
1856 {
1857     struct rstp *r;
1858     struct rstp_port *p1;
1859
1860     r = p->rstp;
1861     HMAP_FOR_EACH (p1, node, &r->ports) {
1862         /* Set tc_prop on every port, except the one calling this
1863          * function. */
1864         if (p1->port_number != p->port_number) {
1865             p1->tc_prop = true;
1866         }
1867     }
1868 }
1869
1870 static void
1871 set_tc_prop_bridge(struct rstp_port *p)  /* not specified in 802.1D-2004. */
1872     OVS_REQUIRES(rstp_mutex)
1873 {
1874     set_tc_prop_tree(p); /* see 802.1w-2001. */
1875 }
1876
1877 static int
1878 topology_change_sm(struct rstp_port *p)
1879     OVS_REQUIRES(rstp_mutex)
1880 {
1881     enum topology_change_state_machine old_state;
1882     struct rstp *r;
1883
1884     old_state = p->topology_change_sm_state;
1885     r = p->rstp;
1886
1887     switch (p->topology_change_sm_state) {
1888     case TOPOLOGY_CHANGE_SM_INIT:
1889         if (r->begin) {
1890             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_INACTIVE_EXEC;
1891         }
1892         break;
1893     case TOPOLOGY_CHANGE_SM_INACTIVE_EXEC:
1894         p->fdb_flush = true;
1895         p->tc_while = 0;
1896         p->tc_ack = false;
1897         p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_INACTIVE;
1898         /* no break */
1899     case TOPOLOGY_CHANGE_SM_INACTIVE:
1900         if (p->learn && !p->fdb_flush) {
1901             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING_EXEC;
1902         }
1903         break;
1904     case TOPOLOGY_CHANGE_SM_LEARNING_EXEC:
1905         p->rcvd_tc = p->rcvd_tcn = p->rcvd_tc_ack = false;
1906         p->tc_prop = p->rcvd_tc_ack = false;
1907         p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING;
1908         /* no break */
1909     case TOPOLOGY_CHANGE_SM_LEARNING:
1910         if (p->role != ROLE_ROOT && p->role != ROLE_DESIGNATED &&
1911             !(p->learn || p->learning) && !(p->rcvd_tc || p->rcvd_tcn ||
1912                                             p->rcvd_tc_ack || p->tc_prop)) {
1913             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_INACTIVE_EXEC;
1914         } else if (p->rcvd_tc || p->rcvd_tcn || p->rcvd_tc_ack || p->tc_prop) {
1915             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING_EXEC;
1916         } else if ((p->role == ROLE_ROOT || p->role == ROLE_DESIGNATED)
1917                    && p->forward && !p->oper_edge) {
1918             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_DETECTED_EXEC;
1919         }
1920         break;
1921     case TOPOLOGY_CHANGE_SM_DETECTED_EXEC:
1922         new_tc_while(p);
1923         set_tc_prop_tree(p);
1924         p->new_info = true;
1925         p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE_EXEC;
1926         /* no break */
1927     case TOPOLOGY_CHANGE_SM_ACTIVE_EXEC:
1928         p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
1929         /* no break */
1930     case TOPOLOGY_CHANGE_SM_ACTIVE:
1931         if ((p->role != ROLE_ROOT && p->role != ROLE_DESIGNATED)
1932             || p->oper_edge) {
1933             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING_EXEC;
1934         } else if (p->rcvd_tcn) {
1935             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_NOTIFIED_TCN_EXEC;
1936         } else if (p->rcvd_tc) {
1937             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_NOTIFIED_TC_EXEC;
1938         } else if (p->tc_prop && !p->oper_edge) {
1939             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_PROPAGATING_EXEC;
1940         } else if (p->rcvd_tc_ack) {
1941             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACKNOWLEDGED_EXEC;
1942         }
1943         break;
1944     case TOPOLOGY_CHANGE_SM_ACKNOWLEDGED_EXEC:
1945         p->tc_while = 0;
1946         p->rcvd_tc_ack = false;
1947         p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
1948         break;
1949     case TOPOLOGY_CHANGE_SM_PROPAGATING_EXEC:
1950         new_tc_while(p);
1951         p->fdb_flush = true;
1952         p->tc_prop = false;
1953         p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
1954         break;
1955     case TOPOLOGY_CHANGE_SM_NOTIFIED_TC_EXEC:
1956         p->rcvd_tcn = p->rcvd_tc = false;
1957         if (p->role == ROLE_DESIGNATED) {
1958             p->tc_ack = true;
1959         }
1960         set_tc_prop_bridge(p);
1961         p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
1962         break;
1963     case TOPOLOGY_CHANGE_SM_NOTIFIED_TCN_EXEC:
1964         new_tc_while(p);
1965         p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_NOTIFIED_TC_EXEC;
1966         break;
1967     default:
1968         OVS_NOT_REACHED();
1969         /* no break */
1970     }
1971     if (old_state != p->topology_change_sm_state) {
1972         r->changes = true;
1973         VLOG_DBG("%s, port %u: Topology_change_sm %d -> %d", p->rstp->name,
1974                  p->port_number, old_state, p->topology_change_sm_state);
1975     }
1976     return 0;
1977 }
1978
1979 /****************************************************************************
1980  * [17.6] Priority vector calculation helper functions
1981  ****************************************************************************/
1982
1983 /* compare_rstp_priority_vectors() compares two struct rstp_priority_vectors
1984  * and returns a value indicating if the first rstp_priority_vector is
1985  * superior, same or inferior to the second one.
1986  *
1987  * Zero return value indicates INFERIOR, a non-zero return value indicates
1988  * SUPERIOR.  When it makes a difference the non-zero return value SAME
1989  * indicates the priority vectors are identical (a subset of SUPERIOR).
1990  */
1991 static enum vector_comparison
1992 compare_rstp_priority_vectors(const struct rstp_priority_vector *v1,
1993                              const struct rstp_priority_vector *v2)
1994 {
1995     VLOG_DBG("v1: "RSTP_ID_FMT", %u, "RSTP_ID_FMT", %d, %d",
1996              RSTP_ID_ARGS(v1->root_bridge_id), v1->root_path_cost,
1997              RSTP_ID_ARGS(v1->designated_bridge_id), v1->designated_port_id,
1998              v1->bridge_port_id);
1999     VLOG_DBG("v2: "RSTP_ID_FMT", %u, "RSTP_ID_FMT", %d, %d",
2000              RSTP_ID_ARGS(v2->root_bridge_id), v2->root_path_cost,
2001              RSTP_ID_ARGS(v2->designated_bridge_id), v2->designated_port_id,
2002              v2->bridge_port_id);
2003
2004     /* [17.6]
2005      * This message priority vector is superior to the port priority vector and
2006      * will replace it if, and only if, the message priority vector is better
2007      * than the port priority vector, or the message has been transmitted from
2008      * the same Designated Bridge and Designated Port as the port priority
2009      * vector, i.e., if the following is true:
2010      *
2011      *    ((RD  < RootBridgeID)) ||
2012      *    ((RD == RootBridgeID) && (RPCD < RootPathCost)) ||
2013      *    ((RD == RootBridgeID) && (RPCD == RootPathCost) &&
2014      *         (D < designated_bridge_id)) ||
2015      *    ((RD == RootBridgeID) && (RPCD == RootPathCost) &&
2016      *         (D == designated_bridge_id) && (PD < designated_port_id)) ||
2017      *    ((D  == designated_bridge_id.BridgeAddress) &&
2018      *         (PD == designated_port_id.PortNumber))
2019      */
2020     if ((v1->root_bridge_id < v2->root_bridge_id)
2021         || (v1->root_bridge_id == v2->root_bridge_id
2022             && v1->root_path_cost < v2->root_path_cost)
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->root_bridge_id == v2->root_bridge_id
2027             && v1->root_path_cost == v2->root_path_cost
2028             && v1->designated_bridge_id == v2->designated_bridge_id
2029             && v1->designated_port_id < v2->designated_port_id)
2030         || (v1->designated_bridge_id == v2->designated_bridge_id
2031             && v1->designated_port_id == v2->designated_port_id)) {
2032         /* SAME is a subset of SUPERIOR. */
2033         if (v1->root_bridge_id == v2->root_bridge_id
2034             && v1->root_path_cost == v2->root_path_cost
2035             && v1->designated_bridge_id == v2->designated_bridge_id
2036             && v1->designated_port_id == v2->designated_port_id) {
2037             if (v1->bridge_port_id < v2->bridge_port_id) {
2038                 VLOG_DBG("superior");
2039                 return SUPERIOR;
2040             }
2041             else if (v1->bridge_port_id > v2->bridge_port_id) {
2042                 VLOG_DBG("inferior");
2043                 return INFERIOR;
2044             }
2045             VLOG_DBG("superior_same");
2046             return SAME;
2047         }
2048         VLOG_DBG("superior");
2049         return SUPERIOR;
2050     }
2051
2052     VLOG_DBG("inferior");
2053     return INFERIOR;
2054 }
2055
2056 static bool
2057 rstp_times_equal(struct rstp_times *t1, struct rstp_times *t2)
2058 {
2059     return t1->forward_delay == t2->forward_delay
2060         && t1->hello_time == t2->hello_time
2061         && t1->max_age == t2->max_age
2062         && t1->message_age == t2->message_age;
2063 }