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 enum vector_comparison {
  66     INFERIOR = 0,
  67     SUPERIOR = 1,
  68     SAME = 2
  69 };
  70
  71 static void decrement_timer(uint16_t *);
  72 static void rstp_send_bpdu(struct rstp_port *, const void *, size_t)
  73     OVS_REQUIRES(rstp_mutex);
  74 static int validate_received_bpdu(struct rstp_port *, const void *, size_t)
  75     OVS_REQUIRES(rstp_mutex);
  76 static ovs_be16 time_encode(uint8_t);
  77 static uint8_t time_decode(ovs_be16);
  78 static enum vector_comparison
  79 compare_rstp_priority_vector(struct rstp_priority_vector *,
  80                              struct rstp_priority_vector *);
  81 static bool rstp_times_equal(struct rstp_times *, struct rstp_times *);
  82
  83 /* Per-Bridge State Machine */
  84 static int port_role_selection_sm(struct rstp *)
  85     OVS_REQUIRES(rstp_mutex);
  86 /* Per-Port State Machines */
  87 static int port_receive_sm(struct rstp_port *)
  88     OVS_REQUIRES(rstp_mutex);
  89 static int port_protocol_migration_sm(struct rstp_port *)
  90     OVS_REQUIRES(rstp_mutex);
  91 static int bridge_detection_sm(struct rstp_port *)
  92     OVS_REQUIRES(rstp_mutex);
  93 static int port_transmit_sm(struct rstp_port *)
  94     OVS_REQUIRES(rstp_mutex);
  95 static int port_information_sm(struct rstp_port *)
  96     OVS_REQUIRES(rstp_mutex);
  97 static int port_role_transition_sm(struct rstp_port *)
  98     OVS_REQUIRES(rstp_mutex);
  99 static int port_state_transition_sm(struct rstp_port *)
 100     OVS_REQUIRES(rstp_mutex);
 101 static int topology_change_sm(struct rstp_port *)
 102     OVS_REQUIRES(rstp_mutex);
 103 /* port_timers_sm() not defined as a state machine */
 104
 105 void
 106 process_received_bpdu__(struct rstp_port *p, const void *bpdu,
 107                         size_t bpdu_size)
 108     OVS_REQUIRES(rstp_mutex)
 109 {
 110     struct rstp *rstp =  p->rstp;
 111
 112     if (!p->port_enabled) {
 113         return;
 114     }
 115     if (p->rcvd_bpdu) {
 116         return;
 117     }
 118     if (validate_received_bpdu(p, bpdu, bpdu_size) == 0) {
 119         p->rcvd_bpdu = true;
 120         p->rx_rstp_bpdu_cnt++;
 121
 122         memcpy(&p->received_bpdu_buffer, bpdu, sizeof(struct rstp_bpdu));
 123
 124         rstp->changes = true;
 125         move_rstp__(rstp);
 126     } else {
 127         VLOG_DBG("%s, port %u: Bad STP or RSTP BPDU received", p->rstp->name,
 128                  p->port_number);
 129         p->error_count++;
 130     }
 131 }
 132
 133 /* Returns 0 on success. */
 134 static int
 135 validate_received_bpdu(struct rstp_port *p, const void *bpdu, size_t bpdu_size)
 136     OVS_REQUIRES(rstp_mutex)
 137 {
 138     /* Validation of received BPDU, see [9.3.4]. */
 139     const struct rstp_bpdu *temp;
 140
 141     temp = bpdu;
 142     if (bpdu_size < TOPOLOGY_CHANGE_NOTIFICATION_BPDU_SIZE ||
 143             ntohs(temp->protocol_identifier) != 0) {
 144         return -1;
 145     } else {
 146         if (temp->bpdu_type == CONFIGURATION_BPDU
 147             && bpdu_size >= CONFIGURATION_BPDU_SIZE
 148             && (time_decode(temp->message_age) <  time_decode(temp->max_age))) {
 149             if ((ntohll(temp->designated_bridge_id) !=
 150                  p->rstp->bridge_identifier)
 151                 || ((ntohll(temp->designated_bridge_id) ==
 152                      p->rstp->bridge_identifier)
 153                     && (ntohs(temp->designated_port_id) != p->port_id))) {
 154                 return 0;
 155             } else {
 156                 return -1;
 157             }
 158         } else if (temp->bpdu_type == TOPOLOGY_CHANGE_NOTIFICATION_BPDU) {
 159             return 0;
 160         } else if (temp->bpdu_type == RAPID_SPANNING_TREE_BPDU &&
 161                    bpdu_size >= RAPID_SPANNING_TREE_BPDU_SIZE) {
 162             return 0;
 163         } else {
 164             return -1;
 165         }
 166     }
 167 }
 168
 169 /*
 170  * move_rstp__()
 171  * This method is invoked to move the State Machines.  The SMs move only if the
 172  * boolean 'changes' is true, meaning that something changed and the SMs need
 173  * to work to process this change.
 174  * The boolean 'changes' is set every time a SM modifies its state, a BPDU is
 175  * received, a timer expires or port down event is detected.  If a parameter is
 176  * set by management, then 'changes' is set.
 177  */
 178 #define MAX_RSTP_ITERATIONS 1000 /* safeguard */
 179 int
 180 move_rstp__(struct rstp *rstp)
 181     OVS_REQUIRES(rstp_mutex)
 182 {
 183     int num_iterations;
 184     num_iterations = 0;
 185
 186     while (rstp->changes == true && num_iterations < MAX_RSTP_ITERATIONS) {
 187         struct rstp_port *p;
 188
 189         VLOG_DBG("%s: move_rstp()", rstp->name);
 190
 191         rstp->changes = false;
 192         port_role_selection_sm(rstp);
 193         if (rstp->ports_count > 0) {
 194             LIST_FOR_EACH (p, node, &rstp->ports) {
 195                 if (p->rstp_state != RSTP_DISABLED) {
 196                     port_receive_sm(p);
 197                     bridge_detection_sm(p);
 198                     port_information_sm(p);
 199                     port_role_transition_sm(p);
 200                     port_state_transition_sm(p);
 201                     topology_change_sm(p);
 202                     port_transmit_sm(p);
 203                     port_protocol_migration_sm(p);
 204                 }
 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     if (r->ports_count > 0) {
 223         LIST_FOR_EACH (p, node, &r->ports) {
 224             decrement_timer(&p->hello_when);
 225             decrement_timer(&p->tc_while);
 226             decrement_timer(&p->fd_while);
 227             decrement_timer(&p->rcvd_info_while);
 228             decrement_timer(&p->rr_while);
 229             decrement_timer(&p->rb_while);
 230             decrement_timer(&p->mdelay_while);
 231             decrement_timer(&p->edge_delay_while);
 232             decrement_timer(&p->tx_count);
 233             p->uptime += 1;
 234         }
 235     }
 236     r->changes = true;
 237     move_rstp__(r);
 238 }
 239
 240 static void
 241 decrement_timer(uint16_t *timer)
 242 {
 243     if (*timer != 0) {
 244         *timer -= 1;
 245     }
 246 }
 247
 248 /* Bridge State Machine. */
 249 /* [17.28] Port Role Selection state machine. */
 250
 251 static void
 252 updt_role_disabled_tree(struct rstp *r)
 253     OVS_REQUIRES(rstp_mutex)
 254 {
 255     struct rstp_port *p;
 256
 257     if (r->ports_count > 0) {
 258         LIST_FOR_EACH (p, node, &r->ports) {
 259             p->selected_role = ROLE_DISABLED;
 260         }
 261     }
 262 }
 263
 264 static void
 265 clear_reselect_tree(struct rstp *r)
 266     OVS_REQUIRES(rstp_mutex)
 267 {
 268     struct rstp_port *p;
 269
 270     if (r->ports_count > 0) {
 271         LIST_FOR_EACH (p, node, &r->ports) {
 272             p->reselect = false;
 273         }
 274     }
 275 }
 276
 277 void
 278 updt_roles_tree__(struct rstp *r)
 279     OVS_REQUIRES(rstp_mutex)
 280 {
 281     struct rstp_port *p;
 282     int vsel;
 283     struct rstp_priority_vector best_vector, candidate_vector;
 284
 285     vsel = -1;
 286     best_vector = r->bridge_priority;
 287     /* Letter c1) */
 288     r->root_times = r->bridge_times;
 289     /* Letters a) b) c) */
 290     if (r->ports_count > 0) {
 291         LIST_FOR_EACH (p, node, &r->ports) {
 292             uint32_t old_root_path_cost;
 293             uint32_t root_path_cost;
 294
 295             if (p->info_is != INFO_IS_RECEIVED) {
 296                 continue;
 297             }
 298             /* [17.6] */
 299             candidate_vector = p->port_priority;
 300             candidate_vector.bridge_port_id = p->port_id;
 301             old_root_path_cost = candidate_vector.root_path_cost;
 302             root_path_cost = old_root_path_cost + p->port_path_cost;
 303             candidate_vector.root_path_cost = root_path_cost;
 304
 305             if ((candidate_vector.designated_bridge_id & 0xffffffffffffULL) ==
 306                 (r->bridge_priority.designated_bridge_id & 0xffffffffffffULL)) {
 307                 break;
 308             }
 309             if (compare_rstp_priority_vector(&candidate_vector, &best_vector)
 310                 == SUPERIOR) {
 311                 best_vector = candidate_vector;
 312                 r->root_times = p->port_times;
 313                 r->root_times.message_age++;
 314                 vsel = p->port_number;
 315             }
 316         }
 317     }
 318     r->root_priority = best_vector;
 319     r->root_port_id = best_vector.bridge_port_id;
 320     VLOG_DBG("%s: new Root is "RSTP_ID_FMT, r->name,
 321              RSTP_ID_ARGS(r->root_priority.root_bridge_id));
 322     /* Letters d) e) */
 323     if (r->ports_count > 0) {
 324         LIST_FOR_EACH (p, node, &r->ports) {
 325             p->designated_priority_vector.root_bridge_id =
 326                 r->root_priority.root_bridge_id;
 327             p->designated_priority_vector.root_path_cost =
 328                 r->root_priority.root_path_cost;
 329             p->designated_priority_vector.designated_bridge_id =
 330                 r->bridge_identifier;
 331             p->designated_priority_vector.designated_port_id =
 332                 p->port_id;
 333             p->designated_times = r->root_times;
 334             p->designated_times.hello_time = r->bridge_times.hello_time;
 335         }
 336     }
 337     if (r->ports_count > 0) {
 338         LIST_FOR_EACH (p, node, &r->ports) {
 339             switch (p->info_is) {
 340             case INFO_IS_DISABLED:
 341                 p->selected_role = ROLE_DISABLED;
 342                 break;
 343             case INFO_IS_AGED:
 344                 p->updt_info = true;
 345                 p->selected_role = ROLE_DESIGNATED;
 346                 break;
 347             case INFO_IS_MINE:
 348                 p->selected_role = ROLE_DESIGNATED;
 349                 if (compare_rstp_priority_vector(&p->port_priority,
 350                                                  &p->designated_priority_vector)
 351                      != SAME
 352                     || !rstp_times_equal(&p->designated_times, &r->root_times)) {
 353                     p->updt_info = true;
 354                 }
 355                 break;
 356             case INFO_IS_RECEIVED:
 357                 if (vsel == p->port_number) { /* Letter i) */
 358                     p->selected_role = ROLE_ROOT;
 359                     p->updt_info = false;
 360                 } else if (compare_rstp_priority_vector(
 361                             &p->designated_priority_vector, &p->port_priority)
 362                             == INFERIOR) {
 363                     if (p->port_priority.designated_bridge_id !=
 364                             r->bridge_identifier) {
 365                         p->selected_role = ROLE_ALTERNATE;
 366                         p->updt_info = false;
 367                     } else {
 368                         p->selected_role = ROLE_BACKUP;
 369                         p->updt_info = false;
 370                     }
 371                 } else {
 372                     p->selected_role = ROLE_DESIGNATED;
 373                     p->updt_info = true;
 374                 }
 375                 break;
 376             default:
 377                 OVS_NOT_REACHED();
 378                 /* no break */
 379             }
 380         }
 381     }
 382     seq_change(connectivity_seq_get());
 383 }
 384
 385 static void
 386 set_selected_tree(struct rstp *r)
 387     OVS_REQUIRES(rstp_mutex)
 388 {
 389     struct rstp_port *p;
 390
 391     if (r->ports_count > 0) {
 392         LIST_FOR_EACH (p, node, &r->ports) {
 393             if (p->reselect) {
 394                 return;
 395             }
 396         }
 397         LIST_FOR_EACH (p, node, &r->ports) {
 398             p->selected = true;
 399         }
 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         if (r->ports_count > 0) {
 436             LIST_FOR_EACH (p, node, &r->ports) {
 437                 if (p->reselect) {
 438                     r->port_role_selection_sm_state =
 439                         PORT_ROLE_SELECTION_SM_ROLE_SELECTION_EXEC;
 440                     break;
 441                 }
 442             }
 443         }
 444         break;
 445     default:
 446         OVS_NOT_REACHED();
 447         /* no break */
 448     }
 449     if (old_state != r->port_role_selection_sm_state) {
 450         r->changes = true;
 451         VLOG_DBG("%s: Port_role_selection_sm %d -> %d", r->name,
 452                  old_state, r->port_role_selection_sm_state);
 453     }
 454     return 0;
 455 }
 456
 457 /* Port State Machines */
 458
 459 /* [17.23 - Port receive state machine] */
 460
 461 static void
 462 updt_bpdu_version(struct rstp_port *p)  /* [17.21.22] */
 463     OVS_REQUIRES(rstp_mutex)
 464 {
 465     switch (p->received_bpdu_buffer.bpdu_type) {
 466     case CONFIGURATION_BPDU:
 467     case TOPOLOGY_CHANGE_NOTIFICATION_BPDU:
 468         p->rcvd_rstp = false;
 469         p->rcvd_stp = true;
 470         break;
 471     case RAPID_SPANNING_TREE_BPDU:
 472         p->rcvd_rstp = true;
 473         p->rcvd_stp = false;
 474         break;
 475     default:
 476         OVS_NOT_REACHED();
 477         /* no break */
 478     }
 479 }
 480
 481 static int
 482 port_receive_sm(struct rstp_port *p)
 483     OVS_REQUIRES(rstp_mutex)
 484 {
 485     enum port_receive_state_machine old_state;
 486     struct rstp *r;
 487
 488     old_state = p->port_receive_sm_state;
 489     r = p->rstp;
 490
 491     switch (p->port_receive_sm_state) {
 492     case PORT_RECEIVE_SM_INIT:
 493         if (r->begin || ((p->rcvd_bpdu || (p->edge_delay_while !=
 494                             r->migrate_time)) && !p->port_enabled)) {
 495             p->port_receive_sm_state = PORT_RECEIVE_SM_DISCARD_EXEC;
 496         }
 497         break;
 498     case PORT_RECEIVE_SM_DISCARD_EXEC:
 499         p->rcvd_bpdu = p->rcvd_rstp = p->rcvd_stp = false;
 500         p->rcvd_msg = false;
 501         p->edge_delay_while = r->migrate_time;
 502         p->port_receive_sm_state = PORT_RECEIVE_SM_DISCARD;
 503         /* no break */
 504     case PORT_RECEIVE_SM_DISCARD:
 505         if (p->rcvd_bpdu && p->port_enabled) {
 506             p->port_receive_sm_state = PORT_RECEIVE_SM_RECEIVE_EXEC;
 507         }
 508         break;
 509     case PORT_RECEIVE_SM_RECEIVE_EXEC:
 510         updt_bpdu_version(p);
 511         p->oper_edge = p->rcvd_bpdu = false;
 512         p->rcvd_msg = true;
 513         p->edge_delay_while = r->migrate_time;
 514         p->port_receive_sm_state = PORT_RECEIVE_SM_RECEIVE;
 515         /* no break */
 516     case PORT_RECEIVE_SM_RECEIVE:
 517         if (p->rcvd_bpdu && p->port_enabled && !p->rcvd_msg) {
 518             p->port_receive_sm_state = PORT_RECEIVE_SM_RECEIVE_EXEC;
 519         }
 520         break;
 521     default:
 522         OVS_NOT_REACHED();
 523         /* no break */
 524     }
 525     if (old_state != p->port_receive_sm_state) {
 526         r->changes = true;
 527         VLOG_DBG("%s, port %u: Port_receive_sm %d -> %d", p->rstp->name,
 528                  p->port_number, old_state, p->port_receive_sm_state);
 529     }
 530     return 0;
 531 }
 532
 533 /* [17.24 - Port Protocol Migration state machine] */
 534 static int
 535 port_protocol_migration_sm(struct rstp_port *p)
 536     OVS_REQUIRES(rstp_mutex)
 537 {
 538     enum port_protocol_migration_state_machine old_state;
 539     struct rstp *r;
 540
 541     old_state = p->port_protocol_migration_sm_state;
 542     r = p->rstp;
 543
 544     switch (p->port_protocol_migration_sm_state) {
 545     case PORT_PROTOCOL_MIGRATION_SM_INIT:
 546         p->port_protocol_migration_sm_state =
 547             PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP_EXEC;
 548         /* no break */
 549     case PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP_EXEC:
 550         p->mcheck = false;
 551         p->send_rstp = r->rstp_version;
 552         p->mdelay_while = r->migrate_time;
 553         p->port_protocol_migration_sm_state =
 554             PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP;
 555         /* no break */
 556     case PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP:
 557         if (p->mdelay_while == 0) {
 558             p->port_protocol_migration_sm_state =
 559                 PORT_PROTOCOL_MIGRATION_SM_SENSING_EXEC;
 560         } else if ((p->mdelay_while != r->migrate_time) && !p->port_enabled) {
 561             p->port_protocol_migration_sm_state =
 562                 PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP_EXEC;
 563         }
 564         break;
 565     case PORT_PROTOCOL_MIGRATION_SM_SELECTING_STP_EXEC:
 566         p->send_rstp = false;
 567         p->mdelay_while = r->migrate_time;
 568         p->port_protocol_migration_sm_state =
 569             PORT_PROTOCOL_MIGRATION_SM_SELECTING_STP;
 570         /* no break */
 571     case PORT_PROTOCOL_MIGRATION_SM_SELECTING_STP:
 572         if ((p->mdelay_while == 0) || (!p->port_enabled) || p->mcheck) {
 573             p->port_protocol_migration_sm_state =
 574                 PORT_PROTOCOL_MIGRATION_SM_SENSING_EXEC;
 575         }
 576         break;
 577     case PORT_PROTOCOL_MIGRATION_SM_SENSING_EXEC:
 578         p->rcvd_rstp = false;
 579         p->rcvd_stp = false;
 580         p->port_protocol_migration_sm_state =
 581             PORT_PROTOCOL_MIGRATION_SM_SENSING;
 582         /* no break */
 583     case PORT_PROTOCOL_MIGRATION_SM_SENSING:
 584         if (!p->port_enabled || p->mcheck || ((r->rstp_version) &&
 585                                               !p->send_rstp && p->rcvd_rstp)) {
 586             p->port_protocol_migration_sm_state =
 587                 PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP_EXEC;
 588         } else if (p->send_rstp && p->rcvd_stp) {
 589             p->port_protocol_migration_sm_state =
 590                 PORT_PROTOCOL_MIGRATION_SM_SELECTING_STP_EXEC;
 591         }
 592         break;
 593     default:
 594         OVS_NOT_REACHED();
 595         /* no break */
 596     }
 597     if (old_state != p->port_protocol_migration_sm_state) {
 598         r->changes = true;
 599         VLOG_DBG("%s, port %u: port_protocol_migration_sm %d -> %d",
 600                  p->rstp->name, p->port_number, old_state,
 601                  p->port_protocol_migration_sm_state);
 602     }
 603
 604     return 0;
 605 }
 606
 607 /* [17.25 - Bridge Detection state machine] */
 608 static int
 609 bridge_detection_sm(struct rstp_port *p)
 610     OVS_REQUIRES(rstp_mutex)
 611 {
 612     enum bridge_detection_state_machine old_state;
 613     struct rstp *r;
 614
 615     old_state = p->bridge_detection_sm_state;
 616     r = p->rstp;
 617
 618     switch (p->bridge_detection_sm_state) {
 619     case BRIDGE_DETECTION_SM_INIT:
 620         if (r->begin && p->admin_edge) {
 621             p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_EDGE_EXEC;
 622         } else if (r->begin && !p->admin_edge) {
 623             p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_NOT_EDGE_EXEC;
 624         }
 625         break;
 626     case BRIDGE_DETECTION_SM_EDGE_EXEC:
 627         p->oper_edge = true;
 628         p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_EDGE;
 629         /* no break */
 630     case BRIDGE_DETECTION_SM_EDGE:
 631         if ((!p->port_enabled && !p->admin_edge) || !p->oper_edge) {
 632             p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_NOT_EDGE_EXEC;
 633         }
 634         break;
 635     case BRIDGE_DETECTION_SM_NOT_EDGE_EXEC:
 636         p->oper_edge = false;
 637         p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_NOT_EDGE;
 638         /* no break */
 639     case BRIDGE_DETECTION_SM_NOT_EDGE:
 640         if ((!p->port_enabled && p->admin_edge)
 641             || ((p->edge_delay_while == 0) && p->auto_edge && p->send_rstp
 642                 && p->proposing)) {
 643             p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_EDGE_EXEC;
 644         }
 645         break;
 646     default:
 647         OVS_NOT_REACHED();
 648         /* no break */
 649     }
 650     if (old_state != p->bridge_detection_sm_state) {
 651         r->changes = true;
 652         VLOG_DBG("%s, port %u: bridge_detection_sm %d -> %d", p->rstp->name,
 653                  p->port_number, old_state, p->bridge_detection_sm_state);
 654     }
 655     return 0;
 656 }
 657
 658 /* [17.26 - Port Transmit state machine] */
 659 static void
 660 rstp_send_bpdu(struct rstp_port *p, const void *bpdu, size_t bpdu_size)
 661     OVS_REQUIRES(rstp_mutex)
 662 {
 663     struct eth_header *eth;
 664     struct llc_header *llc;
 665     struct ofpbuf *pkt;
 666
 667     /* Skeleton. */
 668     pkt = ofpbuf_new(ETH_HEADER_LEN + LLC_HEADER_LEN + bpdu_size);
 669     eth = ofpbuf_put_zeros(pkt, sizeof *eth);
 670     llc = ofpbuf_put_zeros(pkt, sizeof *llc);
 671     ofpbuf_set_frame(pkt, eth);
 672     ofpbuf_set_l3(pkt, ofpbuf_put(pkt, bpdu, bpdu_size));
 673
 674     /* 802.2 header. */
 675     memcpy(eth->eth_dst, eth_addr_stp, ETH_ADDR_LEN);
 676     /* p->rstp->send_bpdu() must fill in source address. */
 677     eth->eth_type = htons(ofpbuf_size(pkt) - ETH_HEADER_LEN);
 678
 679     /* LLC header. */
 680     llc->llc_dsap = STP_LLC_DSAP;
 681     llc->llc_ssap = STP_LLC_SSAP;
 682     llc->llc_cntl = STP_LLC_CNTL;
 683     p->rstp->send_bpdu(pkt, p->aux, p->rstp->aux);
 684 }
 685
 686 static void
 687 record_agreement(struct rstp_port *p)
 688     OVS_REQUIRES(rstp_mutex)
 689 {
 690     struct rstp *r;
 691
 692     r = p->rstp;
 693     if (r->rstp_version && p->oper_point_to_point_mac &&
 694         ((p->received_bpdu_buffer.flags & BPDU_FLAG_AGREEMENT))) {
 695         p->agreed = true;
 696         p->proposing = false;
 697     } else {
 698         p->agreed = false;
 699     }
 700 }
 701
 702 static void
 703 set_tc_flags(struct rstp_port *p)
 704     OVS_REQUIRES(rstp_mutex)
 705 {
 706     /* Sets rcvd_tc and/or rcvd_tc_ack if the Topology Change and/or Topology
 707      * Change Acknowledgment flags, respectively, are set in a ConfigBPDU or
 708      * RST BPDU.
 709      */
 710     if (p->received_bpdu_buffer.bpdu_type == CONFIGURATION_BPDU ||
 711         p->received_bpdu_buffer.bpdu_type == RAPID_SPANNING_TREE_BPDU) {
 712         if ((p->received_bpdu_buffer.flags & BPDU_FLAG_TOPCHANGE) != 0) {
 713             p->rcvd_tc = true;
 714         }
 715         if ((p->received_bpdu_buffer.flags & BPDU_FLAG_TOPCHANGEACK) != 0) {
 716             p->rcvd_tc_ack = true;
 717         }
 718     }
 719     /* Sets rcvd_tcn true if the BPDU is a TCN BPDU. */
 720     if (p->received_bpdu_buffer.bpdu_type
 721         == TOPOLOGY_CHANGE_NOTIFICATION_BPDU) {
 722         p->rcvd_tcn = true;
 723     }
 724 }
 725
 726 static void
 727 record_dispute(struct rstp_port *p)
 728     OVS_REQUIRES(rstp_mutex)
 729 {
 730     if ((p->received_bpdu_buffer.flags & BPDU_FLAG_LEARNING) != 0) {
 731         p->agreed = true;
 732         p->proposing = false;
 733     }
 734 }
 735
 736 static void
 737 record_proposal(struct rstp_port *p)
 738     OVS_REQUIRES(rstp_mutex)
 739 {
 740     enum port_flag role =
 741         ((p->received_bpdu_buffer.flags) & ROLE_FLAG_MASK) >> ROLE_FLAG_SHIFT;
 742
 743     if ((role == PORT_DES)
 744         && ((p->received_bpdu_buffer.flags & BPDU_FLAG_PROPOSAL) != 0)) {
 745         p->proposed = true;
 746     }
 747 }
 748
 749 static void
 750 record_priority(struct rstp_port *p)
 751     OVS_REQUIRES(rstp_mutex)
 752 {
 753     p->port_priority.root_bridge_id = p->msg_priority.root_bridge_id;
 754     p->port_priority.root_path_cost = p->msg_priority.root_path_cost;
 755     p->port_priority.designated_bridge_id =
 756         p->msg_priority.designated_bridge_id;
 757     p->port_priority.designated_port_id = p->msg_priority.designated_port_id;
 758 }
 759
 760 static void
 761 record_times(struct rstp_port *p)
 762     OVS_REQUIRES(rstp_mutex)
 763 {
 764     p->port_times = p->msg_times;
 765     if (p->msg_times.hello_time == 0) {
 766         p->port_times.hello_time = 1;
 767     }
 768 }
 769
 770 static void
 771 updt_rcvd_info_while(struct rstp_port *p)
 772     OVS_REQUIRES(rstp_mutex)
 773 {
 774     /* [17.21.23]
 775      * The value assigned to rcvdInfoWhile is the three times the Hello Time,
 776      * if Message Age, incremented by 1 second and rounded to the nearest whole
 777      * second, does not exceed Max Age, and is zero otherwise.
 778      */
 779     if (p->port_times.message_age < p->port_times.max_age) {
 780         p->rcvd_info_while = p->port_times.hello_time * 3;
 781     } else {
 782         p->rcvd_info_while = 0;
 783     }
 784 }
 785
 786 /* Times are internally held in seconds, while the protocol uses 1/256 seconds.
 787  * time_encode() is used to convert time values sent in bpdus, while
 788  * time_decode() is used to convert time values received in bpdus.
 789  */
 790 static ovs_be16
 791 time_encode(uint8_t value)
 792 {
 793     return htons(value * 256);
 794 }
 795
 796 static uint8_t
 797 time_decode(ovs_be16 encoded)
 798 {
 799     return ntohs(encoded) / 256;
 800 }
 801
 802 /* [17.21.19] */
 803 static void
 804 tx_config(struct rstp_port *p)
 805     OVS_REQUIRES(rstp_mutex)
 806 {
 807     struct rstp_bpdu bpdu;
 808
 809     bpdu.protocol_identifier = htons(0);
 810     bpdu.protocol_version_identifier = 0;
 811     bpdu.bpdu_type = CONFIGURATION_BPDU;
 812     bpdu.root_bridge_id = htonll(p->designated_priority_vector.root_bridge_id);
 813     bpdu.root_path_cost = htonl(p->designated_priority_vector.root_path_cost);
 814     bpdu.designated_bridge_id =
 815         htonll(p->designated_priority_vector.designated_bridge_id);
 816     bpdu.designated_port_id =
 817         htons(p->designated_priority_vector.designated_port_id);
 818     bpdu.message_age = time_encode(p->designated_times.message_age);
 819     bpdu.max_age = time_encode(p->designated_times.max_age);
 820     bpdu.hello_time = time_encode(p->designated_times.hello_time);
 821     bpdu.forward_delay = time_encode(p->designated_times.forward_delay);
 822     bpdu.flags = 0;
 823     if (p->tc_while != 0) {
 824         bpdu.flags |= BPDU_FLAG_TOPCHANGE;
 825     }
 826     if (p->tc_ack != 0) {
 827         bpdu.flags |= BPDU_FLAG_TOPCHANGEACK;
 828     }
 829     rstp_send_bpdu(p, &bpdu, sizeof(struct rstp_bpdu));
 830 }
 831
 832 /* [17.21.20] */
 833 static void
 834 tx_rstp(struct rstp_port *p)
 835     OVS_REQUIRES(rstp_mutex)
 836 {
 837     struct rstp_bpdu bpdu;
 838
 839     bpdu.protocol_identifier = htons(0);
 840     bpdu.protocol_version_identifier = 2;
 841     bpdu.bpdu_type = RAPID_SPANNING_TREE_BPDU;
 842     bpdu.root_bridge_id = htonll(p->designated_priority_vector.root_bridge_id);
 843     bpdu.root_path_cost = htonl(p->designated_priority_vector.root_path_cost);
 844     bpdu.designated_bridge_id =
 845         htonll(p->designated_priority_vector.designated_bridge_id);
 846     bpdu.designated_port_id =
 847         htons(p->designated_priority_vector.designated_port_id);
 848     bpdu.message_age = time_encode(p->designated_times.message_age);
 849     bpdu.max_age = time_encode(p->designated_times.max_age);
 850     bpdu.hello_time = time_encode(p->designated_times.hello_time);
 851     bpdu.forward_delay = time_encode(p->designated_times.forward_delay);
 852     bpdu.flags = 0;
 853
 854     switch (p->role) {
 855     case ROLE_ROOT:
 856         bpdu.flags = PORT_ROOT << ROLE_FLAG_SHIFT;
 857         break;
 858     case ROLE_DESIGNATED:
 859         bpdu.flags = PORT_DES << ROLE_FLAG_SHIFT;
 860         break;
 861     case ROLE_ALTERNATE:
 862     case ROLE_BACKUP:
 863         bpdu.flags = PORT_ALT_BACK << ROLE_FLAG_SHIFT;
 864         break;
 865     case ROLE_DISABLED:
 866         /* Should not happen! */
 867         VLOG_ERR("%s transmitting bpdu in disabled role on port "
 868                  RSTP_PORT_ID_FMT, p->rstp->name, p->port_id);
 869         break;
 870     }
 871     if (p->agree) {
 872         bpdu.flags |= BPDU_FLAG_AGREEMENT;
 873     }
 874     if (p->proposing) {
 875         bpdu.flags |= BPDU_FLAG_PROPOSAL;
 876     }
 877     if (p->tc_while != 0) {
 878         bpdu.flags |= BPDU_FLAG_TOPCHANGE;
 879     }
 880     if (p->learning) {
 881         bpdu.flags |= BPDU_FLAG_LEARNING;
 882     }
 883     if (p->forwarding) {
 884         bpdu.flags |= BPDU_FLAG_FORWARDING;
 885     }
 886     bpdu.version1_length = 0;
 887     rstp_send_bpdu(p, &bpdu, sizeof(struct rstp_bpdu));
 888 }
 889
 890 /* [17.21.21] */
 891 static void
 892 tx_tcn(struct rstp_port *p)
 893     OVS_REQUIRES(rstp_mutex)
 894 {
 895     struct rstp_bpdu bpdu;
 896
 897     memset(&bpdu, 0, sizeof(struct rstp_bpdu));
 898
 899     bpdu.protocol_identifier = htons(0);
 900     bpdu.protocol_version_identifier = 0;
 901     bpdu.bpdu_type = TOPOLOGY_CHANGE_NOTIFICATION_BPDU;
 902     rstp_send_bpdu(p, &bpdu, sizeof(struct rstp_bpdu));
 903 }
 904
 905 static int
 906 port_transmit_sm(struct rstp_port *p)
 907     OVS_REQUIRES(rstp_mutex)
 908 {
 909     enum port_transmit_state_machine old_state;
 910     struct rstp *r;
 911
 912     old_state = p->port_transmit_sm_state;
 913     r = p->rstp;
 914
 915     switch (p->port_transmit_sm_state) {
 916     case PORT_TRANSMIT_SM_INIT:
 917         if (r->begin) {
 918             p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_INIT_EXEC;
 919         }
 920         break;
 921     case PORT_TRANSMIT_SM_TRANSMIT_INIT_EXEC:
 922         p->new_info = true;
 923         p->tx_count = 0;
 924         p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_INIT;
 925         /* no break */
 926     case PORT_TRANSMIT_SM_TRANSMIT_INIT:
 927         p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
 928         break;
 929     case PORT_TRANSMIT_SM_TRANSMIT_PERIODIC_EXEC:
 930         p->new_info = p->new_info || (p->role == ROLE_DESIGNATED ||
 931                       (p->role == ROLE_ROOT && p->tc_while != 0));
 932         p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_PERIODIC;
 933         /* no break */
 934     case PORT_TRANSMIT_SM_TRANSMIT_PERIODIC:
 935         p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
 936         break;
 937     case PORT_TRANSMIT_SM_IDLE_EXEC:
 938         p->hello_when = r->bridge_hello_time;
 939         p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE;
 940         /* no break */
 941     case PORT_TRANSMIT_SM_IDLE:
 942         if (p->role == ROLE_DISABLED) {
 943             VLOG_DBG("%s, port %u: port_transmit_sm ROLE == DISABLED.",
 944                      p->rstp->name, p->port_number);
 945             break;
 946         } else if (p->send_rstp && p->new_info
 947                    && p->tx_count < r->transmit_hold_count
 948                    && p->hello_when != 0 && p->selected && !p->updt_info) {
 949             p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_RSTP_EXEC;
 950         } else if (p->hello_when == 0 && p->selected && !p->updt_info) {
 951             p->port_transmit_sm_state =
 952                 PORT_TRANSMIT_SM_TRANSMIT_PERIODIC_EXEC;
 953         } else if (!p->send_rstp && p->new_info && p->role == ROLE_ROOT
 954                    && p->tx_count < r->transmit_hold_count
 955                    && p->hello_when != 0 && p->selected && !p->updt_info) {
 956             p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_TCN_EXEC;
 957         } else if (!p->send_rstp && p->new_info && p->role == ROLE_DESIGNATED
 958                    && p->tx_count < r->transmit_hold_count
 959                    && p->hello_when != 0 && p->selected && !p->updt_info) {
 960             p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_CONFIG_EXEC;
 961         }
 962         break;
 963     case PORT_TRANSMIT_SM_TRANSMIT_CONFIG_EXEC:
 964         p->new_info = false;
 965         tx_config(p);
 966         p->tx_count += 1;
 967         p->tc_ack = false;
 968         p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_CONFIG;
 969         /* no break */
 970     case PORT_TRANSMIT_SM_TRANSMIT_CONFIG:
 971         p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
 972         break;
 973     case PORT_TRANSMIT_SM_TRANSMIT_TCN_EXEC:
 974         p->new_info = false;
 975         tx_tcn(p);
 976         p->tx_count += 1;
 977         p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_TCN;
 978         /* no break */
 979     case PORT_TRANSMIT_SM_TRANSMIT_TCN:
 980         p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
 981         break;
 982     case PORT_TRANSMIT_SM_TRANSMIT_RSTP_EXEC:
 983         p->new_info = false;
 984         tx_rstp(p);
 985         p->tx_count += 1;
 986         p->tc_ack = false;
 987         p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_RSTP;
 988         /* no break */
 989     case PORT_TRANSMIT_SM_TRANSMIT_RSTP:
 990         p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
 991         break;
 992     default:
 993         OVS_NOT_REACHED();
 994         /* no break */
 995     }
 996     if (old_state != p->port_transmit_sm_state) {
 997         r->changes = true;
 998         VLOG_DBG("%s, port %u: port_transmit_sm %d -> %d", p->rstp->name,
 999                  p->port_number, old_state, p->port_transmit_sm_state);
1000     }
1001     return 0;
1002 }
1003
1004 /* [17.27 Port Information state machine] */
1005 #define RECEIVED 0
1006 #define MINE 1
1007
1008 static int
1009 rcv_info(struct rstp_port *p)
1010     OVS_REQUIRES(rstp_mutex)
1011 {
1012     enum vector_comparison cp;
1013     bool ct;
1014     enum port_flag role;
1015
1016     p->msg_priority.root_bridge_id =
1017         ntohll(p->received_bpdu_buffer.root_bridge_id);
1018     p->msg_priority.root_path_cost =
1019         ntohl(p->received_bpdu_buffer.root_path_cost);
1020     p->msg_priority.designated_bridge_id =
1021         ntohll(p->received_bpdu_buffer.designated_bridge_id);
1022     p->msg_priority.designated_port_id =
1023         ntohs(p->received_bpdu_buffer.designated_port_id);
1024
1025     p->msg_times.forward_delay =
1026         time_decode(p->received_bpdu_buffer.forward_delay);
1027     p->msg_times.hello_time = time_decode(p->received_bpdu_buffer.hello_time);
1028     p->msg_times.max_age = time_decode(p->received_bpdu_buffer.max_age);
1029     p->msg_times.message_age =
1030         time_decode(p->received_bpdu_buffer.message_age);
1031
1032     cp = compare_rstp_priority_vector(&p->msg_priority, &p->port_priority);
1033     ct = rstp_times_equal(&p->port_times, &p->msg_times);
1034     role =
1035         (p->received_bpdu_buffer.flags & ROLE_FLAG_MASK) >> ROLE_FLAG_SHIFT;
1036
1037     /* Returns SuperiorDesignatedInfo if:
1038      * a) The received message conveys a Designated Port Role, and
1039      *  1) The message priority is superior (17.6) to the Port.s port priority
1040      *     vector, or
1041      *  2) The message priority vector is the same as the Port.s port priority
1042      *     vector, and any of the received timer parameter values (msg_times.
1043      *     17.19.15) differ from those already held for the Port (port_times
1044      *     17.19.22).
1045      * NOTE: Configuration BPDU explicitly conveys a Designated Port Role.
1046      */
1047     if ((role == PORT_DES
1048          || p->received_bpdu_buffer.bpdu_type == CONFIGURATION_BPDU)
1049         && (cp == SUPERIOR || (cp == SAME && ct == false))) {
1050         return SUPERIOR_DESIGNATED_INFO;
1051
1052         /* Returns RepeatedDesignatedInfo if:
1053          * b) The received message conveys Designated Port Role, and a message
1054          *     priority vector and timer parameters that are the same as the
1055          *     Port's port priority vector or timer values. */
1056     } else if (role == PORT_DES && cp == SAME && ct == true) {
1057         return REPEATED_DESIGNATED_INFO;
1058
1059         /* Returns InferiorDesignatedInfo if:
1060          * c) The received message conveys a Designated Port Role, and a
1061          *    message priority vector that is worse than the Port's port
1062          *    priority vector. */
1063     } else if (role == PORT_DES && cp == INFERIOR) {
1064         return INFERIOR_DESIGNATED_INFO;
1065
1066         /* Returns InferiorRootAlternateInfo if:
1067          * d) The received message conveys a Root Port, Alternate Port, or
1068          *    Backup Port Role and a message priority that is the same as or
1069          *    worse than the port priority vector. */
1070     } else if ((role == PORT_ROOT || role == PORT_ALT_BACK) &&
1071                (cp == INFERIOR || cp == SAME)) {
1072         return INFERIOR_ROOT_ALTERNATE_INFO;
1073
1074         /* Otherwise, returns OtherInfo. */
1075     } else {
1076         return OTHER_INFO;
1077     }
1078 }
1079
1080 static int
1081 better_or_same_info(struct rstp_port *p, int new_info_is)
1082     OVS_REQUIRES(rstp_mutex)
1083 {
1084     /* >= SUPERIOR means that the vector is better or the same. */
1085     return
1086         (new_info_is == RECEIVED && p->info_is == INFO_IS_RECEIVED
1087          && compare_rstp_priority_vector(&p->msg_priority,
1088                                          &p->port_priority) >= SUPERIOR)
1089         || (new_info_is == MINE && p->info_is == INFO_IS_MINE
1090             && compare_rstp_priority_vector(&p->designated_priority_vector,
1091                                             &p->port_priority) >= SUPERIOR);
1092 }
1093
1094 static int
1095 port_information_sm(struct rstp_port *p)
1096     OVS_REQUIRES(rstp_mutex)
1097 {
1098     enum port_information_state_machine old_state;
1099     struct rstp *r;
1100
1101     old_state = p->port_information_sm_state;
1102     r = p->rstp;
1103
1104     if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1105         p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1106     }
1107     switch (p->port_information_sm_state) {
1108     case PORT_INFORMATION_SM_INIT:
1109         if (r->begin) {
1110             p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1111         }
1112         break;
1113     case PORT_INFORMATION_SM_DISABLED_EXEC:
1114         p->rcvd_msg = false;
1115         p->proposing = p->proposed = p->agree = p->agreed = false;
1116         p->rcvd_info_while = 0;
1117         p->info_is = INFO_IS_DISABLED;
1118         p->reselect = true;
1119         p->selected = false;
1120         p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED;
1121         /* no break */
1122     case PORT_INFORMATION_SM_DISABLED:
1123         if (p->port_enabled) {
1124             p->port_information_sm_state = PORT_INFORMATION_SM_AGED_EXEC;
1125         } else if (p->rcvd_msg) {
1126             p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1127         }
1128         break;
1129     case PORT_INFORMATION_SM_AGED_EXEC:
1130         p->info_is = INFO_IS_AGED;
1131         p->reselect = true;
1132         p->selected = false;
1133         p->port_information_sm_state = PORT_INFORMATION_SM_AGED;
1134         /* no break */
1135     case PORT_INFORMATION_SM_AGED:
1136         if (p->selected && p->updt_info) {
1137             p->port_information_sm_state = PORT_INFORMATION_SM_UPDATE_EXEC;
1138         }
1139         break;
1140     case PORT_INFORMATION_SM_UPDATE_EXEC:
1141         p->proposing = p->proposed = false;
1142         /* MINE is not specified in Standard 802.1D-2004. */
1143         p->agreed = p->agreed && better_or_same_info(p, MINE);
1144         p->synced = p->synced && p->agreed;
1145         p->port_priority.root_bridge_id =
1146             p->designated_priority_vector.root_bridge_id;
1147         p->port_priority.root_path_cost =
1148             p->designated_priority_vector.root_path_cost;
1149         p->port_priority.designated_bridge_id =
1150             p->designated_priority_vector.designated_bridge_id;
1151         p->port_priority.designated_port_id =
1152             p->designated_priority_vector.designated_port_id;
1153         p->port_times = p->designated_times;
1154         p->updt_info = false;
1155         p->info_is = INFO_IS_MINE;
1156         p->new_info = true;
1157         p->port_information_sm_state = PORT_INFORMATION_SM_UPDATE;
1158         /* no break */
1159     case PORT_INFORMATION_SM_UPDATE:
1160         p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1161         break;
1162     case PORT_INFORMATION_SM_CURRENT_EXEC:
1163         p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT;
1164         /* no break */
1165     case PORT_INFORMATION_SM_CURRENT:
1166         if (p->rcvd_msg && !p->updt_info) {
1167             p->port_information_sm_state = PORT_INFORMATION_SM_RECEIVE_EXEC;
1168         } else if (p->selected && p->updt_info) {
1169             p->port_information_sm_state = PORT_INFORMATION_SM_UPDATE_EXEC;
1170         } else if ((p->info_is == INFO_IS_RECEIVED) &&
1171                    (p->rcvd_info_while == 0) && !p->updt_info &&
1172                    !p->rcvd_msg) {
1173             p->port_information_sm_state = PORT_INFORMATION_SM_AGED_EXEC;
1174         }
1175         break;
1176     case PORT_INFORMATION_SM_RECEIVE_EXEC:
1177         p->rcvd_info = rcv_info(p);
1178         p->port_information_sm_state = PORT_INFORMATION_SM_RECEIVE;
1179         /* no break */
1180     case PORT_INFORMATION_SM_RECEIVE:
1181         switch (p->rcvd_info) {
1182         case SUPERIOR_DESIGNATED_INFO:
1183             p->port_information_sm_state =
1184                 PORT_INFORMATION_SM_SUPERIOR_DESIGNATED_EXEC;
1185             break;
1186         case REPEATED_DESIGNATED_INFO:
1187             p->port_information_sm_state =
1188                 PORT_INFORMATION_SM_REPEATED_DESIGNATED_EXEC;
1189             break;
1190         case INFERIOR_DESIGNATED_INFO:
1191             p->port_information_sm_state =
1192                 PORT_INFORMATION_SM_INFERIOR_DESIGNATED_EXEC;
1193             break;
1194         case INFERIOR_ROOT_ALTERNATE_INFO:
1195             p->port_information_sm_state =
1196                 PORT_INFORMATION_SM_NOT_DESIGNATED_EXEC;
1197             break;
1198         case OTHER_INFO:
1199             p->port_information_sm_state = PORT_INFORMATION_SM_OTHER_EXEC;
1200             break;
1201         default:
1202             OVS_NOT_REACHED();
1203             /* no break */
1204         }
1205         break;
1206     case PORT_INFORMATION_SM_OTHER_EXEC:
1207         p->rcvd_msg = false;
1208         p->port_information_sm_state = PORT_INFORMATION_SM_OTHER;
1209         /* no break */
1210     case PORT_INFORMATION_SM_OTHER:
1211         p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1212         break;
1213     case PORT_INFORMATION_SM_NOT_DESIGNATED_EXEC:
1214         record_agreement(p);
1215         set_tc_flags(p);
1216         p->rcvd_msg = false;
1217         p->port_information_sm_state = PORT_INFORMATION_SM_NOT_DESIGNATED;
1218         /* no break */
1219     case PORT_INFORMATION_SM_NOT_DESIGNATED:
1220         p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1221         break;
1222     case PORT_INFORMATION_SM_INFERIOR_DESIGNATED_EXEC:
1223         record_dispute(p);
1224         p->rcvd_msg = false;
1225         p->port_information_sm_state = PORT_INFORMATION_SM_INFERIOR_DESIGNATED;
1226         /* no break */
1227     case PORT_INFORMATION_SM_INFERIOR_DESIGNATED:
1228         p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1229         break;
1230     case PORT_INFORMATION_SM_REPEATED_DESIGNATED_EXEC:
1231         record_proposal(p);
1232         set_tc_flags(p);
1233         updt_rcvd_info_while(p);
1234         p->rcvd_msg = false;
1235         p->port_information_sm_state = PORT_INFORMATION_SM_REPEATED_DESIGNATED;
1236         /* no break */
1237     case PORT_INFORMATION_SM_REPEATED_DESIGNATED:
1238         p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1239         break;
1240     case PORT_INFORMATION_SM_SUPERIOR_DESIGNATED_EXEC:
1241         p->agreed = p->proposing = false;
1242         record_proposal(p);
1243         set_tc_flags(p);
1244         /* RECEIVED is not specified in Standard 802.1D-2004. */
1245         p->agree = p->agree && better_or_same_info(p, RECEIVED);
1246         record_priority(p);
1247         record_times(p);
1248         updt_rcvd_info_while(p);
1249         p->info_is = INFO_IS_RECEIVED;
1250         p->reselect = true;
1251         p->selected = false;
1252         p->rcvd_msg = false;
1253         p->port_information_sm_state = PORT_INFORMATION_SM_SUPERIOR_DESIGNATED;
1254         /* no break */
1255     case PORT_INFORMATION_SM_SUPERIOR_DESIGNATED:
1256         p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1257         break;
1258     default:
1259         OVS_NOT_REACHED();
1260         /* no break */
1261     }
1262     if (old_state != p->port_information_sm_state) {
1263         r->changes = true;
1264         VLOG_DBG("%s, port %u: Port_information_sm %d -> %d", p->rstp->name,
1265                  p->port_number, old_state, p->port_information_sm_state);
1266     }
1267     return 0;
1268 }
1269
1270 /* [17.29 Port Role Transitions state machine] */
1271
1272 static void
1273 set_re_root_tree(struct rstp_port *p)
1274     OVS_REQUIRES(rstp_mutex)
1275 {
1276     struct rstp *r;
1277     struct rstp_port *p1;
1278
1279     r = p->rstp;
1280     if (r->ports_count > 0) {
1281         LIST_FOR_EACH (p1, node, &r->ports) {
1282             p1->re_root = true;
1283         }
1284     }
1285 }
1286
1287 static void
1288 set_sync_tree(struct rstp_port *p)
1289     OVS_REQUIRES(rstp_mutex)
1290 {
1291     struct rstp *r;
1292     struct rstp_port *p1;
1293
1294     r = p->rstp;
1295     if (r->ports_count > 0) {
1296         LIST_FOR_EACH (p1, node, &r->ports) {
1297             p1->sync = true;
1298         }
1299     }
1300 }
1301
1302 static int
1303 hello_time(struct rstp_port *p)
1304     OVS_REQUIRES(rstp_mutex)
1305 {
1306     return p->designated_times.hello_time;
1307 }
1308
1309 static int
1310 fwd_delay(struct rstp_port *p)
1311     OVS_REQUIRES(rstp_mutex)
1312 {
1313     return p->designated_times.forward_delay;
1314 }
1315
1316 static int
1317 forward_delay(struct rstp_port *p)
1318     OVS_REQUIRES(rstp_mutex)
1319 {
1320     if (p->send_rstp) {
1321         return hello_time(p);
1322     } else {
1323         return fwd_delay(p);
1324     }
1325 }
1326
1327 static int
1328 edge_delay(struct rstp_port *p)
1329     OVS_REQUIRES(rstp_mutex)
1330 {
1331     struct rstp *r;
1332
1333     r = p->rstp;
1334     if (p->oper_point_to_point_mac == 1) {
1335         return r->migrate_time;
1336     } else {
1337         return p->designated_times.max_age;
1338     }
1339 }
1340
1341 static int
1342 check_selected_role_change(struct rstp_port *p, int current_role_state)
1343     OVS_REQUIRES(rstp_mutex)
1344 {
1345     if (p->selected && !p->updt_info && p->role != p->selected_role
1346         && p->selected_role != current_role_state) {
1347         VLOG_DBG("%s, port %u: case: current = %s role =  %s selected =  %d",
1348                  p->rstp->name, p->port_number,
1349                  rstp_port_role_name(current_role_state),
1350                  rstp_port_role_name(p->role), p->selected_role);
1351         switch (p->selected_role) {
1352         case ROLE_ROOT:
1353             p->port_role_transition_sm_state =
1354                 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1355             return true;
1356         case ROLE_DESIGNATED:
1357             p->port_role_transition_sm_state =
1358                 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1359             return true;
1360         case ROLE_ALTERNATE:
1361             p->port_role_transition_sm_state =
1362                 PORT_ROLE_TRANSITION_SM_BLOCK_PORT_EXEC;
1363             return true;
1364         case ROLE_BACKUP:
1365             p->port_role_transition_sm_state =
1366                 PORT_ROLE_TRANSITION_SM_BLOCK_PORT_EXEC;
1367             return true;
1368         case ROLE_DISABLED:
1369             p->port_role_transition_sm_state =
1370                 PORT_ROLE_TRANSITION_SM_DISABLE_PORT_EXEC;
1371             return true;
1372         }
1373     }
1374     return false;
1375 }
1376
1377 static int
1378 re_rooted(struct rstp_port *p)
1379     OVS_REQUIRES(rstp_mutex)
1380 {
1381     struct rstp *r;
1382     struct rstp_port *p1;
1383
1384     r = p->rstp;
1385     if (r->ports_count > 0) {
1386         LIST_FOR_EACH (p1, node, &r->ports) {
1387             if ((p1 != p) && (p1->rr_while != 0)) {
1388                 return false;
1389             }
1390         }
1391     }
1392     return true;
1393 }
1394
1395 static int
1396 all_synced(struct rstp *r)
1397     OVS_REQUIRES(rstp_mutex)
1398 {
1399     struct rstp_port *p;
1400
1401     if (r->ports_count > 0) {
1402         LIST_FOR_EACH (p, node, &r->ports) {
1403             if (!(p->selected && p->role == p->selected_role &&
1404                         (p->role == ROLE_ROOT || p->synced == true))) {
1405                 return false;
1406             }
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;
1659             }
1660         }
1661         break;
1662     case PORT_ROLE_TRANSITION_SM_ALTERNATE_AGREED:
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     if (r->ports_count > 0) {
1862         LIST_FOR_EACH (p1, node, &r->ports) {
1863             /* Set tc_prop on every port, except the one calling this
1864              * function.
1865              */
1866             if (p1->port_number != p->port_number) {
1867                 p1->tc_prop = true;
1868             }
1869         }
1870     }
1871 }
1872
1873 static void
1874 set_tc_prop_bridge(struct rstp_port *p)  /* not specified in 802.1D-2004. */
1875     OVS_REQUIRES(rstp_mutex)
1876 {
1877     set_tc_prop_tree(p); /* see 802.1w-2001. */
1878 }
1879
1880 static int
1881 topology_change_sm(struct rstp_port *p)
1882     OVS_REQUIRES(rstp_mutex)
1883 {
1884     enum topology_change_state_machine old_state;
1885     struct rstp *r;
1886
1887     old_state = p->topology_change_sm_state;
1888     r = p->rstp;
1889
1890     switch (p->topology_change_sm_state) {
1891     case TOPOLOGY_CHANGE_SM_INIT:
1892         if (r->begin) {
1893             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_INACTIVE_EXEC;
1894         }
1895         break;
1896     case TOPOLOGY_CHANGE_SM_INACTIVE_EXEC:
1897         p->fdb_flush = true;
1898         p->tc_while = 0;
1899         p->tc_ack = false;
1900         p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_INACTIVE;
1901         /* no break */
1902     case TOPOLOGY_CHANGE_SM_INACTIVE:
1903         if (p->learn && !p->fdb_flush) {
1904             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING_EXEC;
1905         }
1906         break;
1907     case TOPOLOGY_CHANGE_SM_LEARNING_EXEC:
1908         p->rcvd_tc = p->rcvd_tcn = p->rcvd_tc_ack = false;
1909         p->tc_prop = p->rcvd_tc_ack = false;
1910         p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING;
1911         /* no break */
1912     case TOPOLOGY_CHANGE_SM_LEARNING:
1913         if (p->role != ROLE_ROOT && p->role != ROLE_DESIGNATED &&
1914             !(p->learn || p->learning) && !(p->rcvd_tc || p->rcvd_tcn ||
1915                                             p->rcvd_tc_ack || p->tc_prop)) {
1916             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_INACTIVE_EXEC;
1917         } else if (p->rcvd_tc || p->rcvd_tcn || p->rcvd_tc_ack || p->tc_prop) {
1918             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING_EXEC;
1919         } else if ((p->role == ROLE_ROOT || p->role == ROLE_DESIGNATED)
1920                    && p->forward && !p->oper_edge) {
1921             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_DETECTED_EXEC;
1922         }
1923         break;
1924     case TOPOLOGY_CHANGE_SM_DETECTED_EXEC:
1925         new_tc_while(p);
1926         set_tc_prop_tree(p);
1927         p->new_info = true;
1928         p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE_EXEC;
1929         /* no break */
1930     case TOPOLOGY_CHANGE_SM_ACTIVE_EXEC:
1931         p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
1932         /* no break */
1933     case TOPOLOGY_CHANGE_SM_ACTIVE:
1934         if ((p->role != ROLE_ROOT && p->role != ROLE_DESIGNATED)
1935             || p->oper_edge) {
1936             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING_EXEC;
1937         } else if (p->rcvd_tcn) {
1938             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_NOTIFIED_TCN_EXEC;
1939         } else if (p->rcvd_tc) {
1940             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_NOTIFIED_TC_EXEC;
1941         } else if (p->tc_prop && !p->oper_edge) {
1942             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_PROPAGATING_EXEC;
1943         } else if (p->rcvd_tc_ack) {
1944             p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACKNOWLEDGED_EXEC;
1945         }
1946         break;
1947     case TOPOLOGY_CHANGE_SM_ACKNOWLEDGED_EXEC:
1948         p->tc_while = 0;
1949         p->rcvd_tc_ack = false;
1950         p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
1951         break;
1952     case TOPOLOGY_CHANGE_SM_PROPAGATING_EXEC:
1953         new_tc_while(p);
1954         p->fdb_flush = true;
1955         p->tc_prop = false;
1956         p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
1957         break;
1958     case TOPOLOGY_CHANGE_SM_NOTIFIED_TC_EXEC:
1959         p->rcvd_tcn = p->rcvd_tc = false;
1960         if (p->role == ROLE_DESIGNATED) {
1961             p->tc_ack = true;
1962         }
1963         set_tc_prop_bridge(p);
1964         p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
1965         break;
1966     case TOPOLOGY_CHANGE_SM_NOTIFIED_TCN_EXEC:
1967         new_tc_while(p);
1968         p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
1969         break;
1970     default:
1971         OVS_NOT_REACHED();
1972         /* no break */
1973     }
1974     if (old_state != p->topology_change_sm_state) {
1975         r->changes = true;
1976         VLOG_DBG("%s, port %u: Topology_change_sm %d -> %d", p->rstp->name,
1977                  p->port_number, old_state, p->topology_change_sm_state);
1978     }
1979     return 0;
1980 }
1981
1982 /****************************************************************************
1983  * [17.6] Priority vector calculation helper functions
1984  ****************************************************************************/
1985
1986 /* [17.6]
1987  * This message priority vector is superior to the port priority vector and
1988  * will replace it if, and only if, the message priority vector is better
1989  * than the port priority vector, or the message has been transmitted from the
1990  * same Designated Bridge and Designated Port as the port priority vector,
1991  * i.e.,if the following is true:
1992  *    ((RD  < RootBridgeID)) ||
1993  *    ((RD == RootBridgeID) && (RPCD < RootPathCost)) ||
1994  *    ((RD == RootBridgeID) && (RPCD == RootPathCost) &&
1995  *         (D < designated_bridge_id)) ||
1996  *    ((RD == RootBridgeID) && (RPCD == RootPathCost) &&
1997  *         (D == designated_bridge_id) && (PD < designated_port_id)) ||
1998  *    ((D  == designated_bridge_id.BridgeAddress) &&
1999  *         (PD == designated_port_id.PortNumber))
2000  */
2001
2002 /* compare_rstp_priority_vector() compares two struct rstp_priority_vector and
2003  * returns a value indicating if the first rstp_priority_vector is superior,
2004  * same or inferior to the second one.
2005  */
2006 static enum vector_comparison
2007 compare_rstp_priority_vector(struct rstp_priority_vector *v1,
2008                              struct rstp_priority_vector *v2)
2009 {
2010     VLOG_DBG("v1: "RSTP_ID_FMT", %u, "RSTP_ID_FMT", %d",
2011              RSTP_ID_ARGS(v1->root_bridge_id), v1->root_path_cost,
2012              RSTP_ID_ARGS(v1->designated_bridge_id), v1->designated_port_id);
2013     VLOG_DBG("v2: "RSTP_ID_FMT", %u, "RSTP_ID_FMT", %d",
2014              RSTP_ID_ARGS(v2->root_bridge_id), v2->root_path_cost,
2015              RSTP_ID_ARGS(v2->designated_bridge_id), v2->designated_port_id);
2016
2017     if ((v1->root_bridge_id < v2->root_bridge_id) ||
2018         ((v1->root_bridge_id == v2->root_bridge_id) &&
2019          (v1->root_path_cost < v2->root_path_cost)) ||
2020         ((v1->root_bridge_id == v2->root_bridge_id) &&
2021          (v1->root_path_cost == v2->root_path_cost) &&
2022          (v1->designated_bridge_id < v2->designated_bridge_id)) ||
2023         ((v1->root_bridge_id == v2->root_bridge_id) &&
2024          (v1->root_path_cost == v2->root_path_cost) &&
2025          (v1->designated_bridge_id == v2->designated_bridge_id) &&
2026             (v1->designated_port_id < v2->designated_port_id))) {
2027         VLOG_DBG("superior_absolute");
2028         return SUPERIOR;
2029     }
2030     else if (((v1->root_bridge_id > v2->root_bridge_id) ||
2031                 ((v1->root_bridge_id == v2->root_bridge_id) &&
2032                  (v1->root_path_cost > v2->root_path_cost)) ||
2033                 ((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->root_bridge_id == v2->root_bridge_id) &&
2037                  (v1->root_path_cost == v2->root_path_cost) &&
2038                  (v1->designated_bridge_id == v2->designated_bridge_id) &&
2039                  (v1->designated_port_id > v2->designated_port_id))) &&
2040             (v1->designated_bridge_id == v2->designated_bridge_id) &&
2041             (v1->designated_port_id == v2->designated_port_id)) {
2042         VLOG_DBG("superior_same_des");
2043         return SUPERIOR;
2044     }
2045     else if ((v1->root_bridge_id == v2->root_bridge_id) &&
2046              (v1->root_path_cost == v2->root_path_cost) &&
2047              (v1->designated_bridge_id == v2->designated_bridge_id) &&
2048              (v1->designated_port_id == v2->designated_port_id)) {
2049         VLOG_DBG("same");
2050         return SAME;
2051     }
2052     else {
2053         VLOG_DBG("inferior");
2054         return INFERIOR;
2055     }
2056 }
2057
2058 static bool
2059 rstp_times_equal(struct rstp_times *t1, struct rstp_times *t2)
2060 {
2061     return t1->forward_delay == t2->forward_delay
2062         && t1->hello_time == t2->hello_time
2063         && t1->max_age == t2->max_age
2064         && t1->message_age == t2->message_age;
2065 }