2 * Copyright (c) 2011-2014 M3S, Srl - Italy
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
18 * Rapid Spanning Tree Protocol (IEEE 802.1D-2004) state machines
22 * Martino Fornasa <mf@fornasa.it>
23 * Daniele Venturino <daniele.venturino@m3s.it>
25 * References to IEEE 802.1D-2004 standard are enclosed in square brackets.
26 * E.g. [17.3], [Table 17-1], etc.
32 #include "rstp-state-machines.h"
33 #include <arpa/inet.h>
35 #include <netinet/in.h>
37 #include <sys/types.h>
38 #include "byte-order.h"
39 #include "connectivity.h"
47 VLOG_DEFINE_THIS_MODULE(rstp_sm);
49 #define ROLE_FLAG_MASK 0xC
50 #define ROLE_FLAG_SHIFT 2
60 CONFIGURATION_BPDU_SIZE = 35,
61 TOPOLOGY_CHANGE_NOTIFICATION_BPDU_SIZE = 4,
62 RAPID_SPANNING_TREE_BPDU_SIZE = 36
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 {
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 *);
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 */
108 process_received_bpdu__(struct rstp_port *p, const void *bpdu,
110 OVS_REQUIRES(rstp_mutex)
112 struct rstp *rstp = p->rstp;
114 if (!p->port_enabled) {
120 if (validate_received_bpdu(p, bpdu, bpdu_size) == 0) {
122 p->rx_rstp_bpdu_cnt++;
124 memcpy(&p->received_bpdu_buffer, bpdu, sizeof(struct rstp_bpdu));
126 rstp->changes = true;
129 VLOG_DBG("%s, port %u: Bad STP or RSTP BPDU received", p->rstp->name,
135 /* Returns 0 on success. */
137 validate_received_bpdu(struct rstp_port *p, const void *bpdu, size_t bpdu_size)
138 OVS_REQUIRES(rstp_mutex)
140 /* Validation of received BPDU, see [9.3.4]. */
141 const struct rstp_bpdu *temp;
144 if (bpdu_size < TOPOLOGY_CHANGE_NOTIFICATION_BPDU_SIZE ||
145 ntohs(temp->protocol_identifier) != 0) {
148 if (temp->bpdu_type == CONFIGURATION_BPDU
149 && bpdu_size >= CONFIGURATION_BPDU_SIZE
150 && (time_decode(temp->message_age) < time_decode(temp->max_age))) {
151 if ((ntohll(temp->designated_bridge_id) !=
152 p->rstp->bridge_identifier)
153 || ((ntohll(temp->designated_bridge_id) ==
154 p->rstp->bridge_identifier)
155 && (ntohs(temp->designated_port_id) != p->port_id))) {
160 } else if (temp->bpdu_type == TOPOLOGY_CHANGE_NOTIFICATION_BPDU) {
162 } else if (temp->bpdu_type == RAPID_SPANNING_TREE_BPDU &&
163 bpdu_size >= RAPID_SPANNING_TREE_BPDU_SIZE) {
173 * This method is invoked to move the State Machines. The SMs move only if the
174 * boolean 'changes' is true, meaning that something changed and the SMs need
175 * to work to process this change.
176 * The boolean 'changes' is set every time a SM modifies its state, a BPDU is
177 * received, a timer expires or port down event is detected. If a parameter is
178 * set by management, then 'changes' is set.
180 #define MAX_RSTP_ITERATIONS 1000 /* safeguard */
182 move_rstp__(struct rstp *rstp)
183 OVS_REQUIRES(rstp_mutex)
188 while (rstp->changes == true && num_iterations < MAX_RSTP_ITERATIONS) {
191 VLOG_DBG("%s: move_rstp()", rstp->name);
193 rstp->changes = false;
194 port_role_selection_sm(rstp);
195 HMAP_FOR_EACH (p, node, &rstp->ports) {
196 if (p->rstp_state != RSTP_DISABLED) {
198 bridge_detection_sm(p);
199 port_information_sm(p);
200 port_role_transition_sm(p);
201 port_state_transition_sm(p);
202 topology_change_sm(p);
204 port_protocol_migration_sm(p);
208 seq_change(connectivity_seq_get());
210 if (num_iterations >= MAX_RSTP_ITERATIONS) {
211 VLOG_ERR("%s: move_rstp() reached the iteration safeguard limit!",
217 void decrease_rstp_port_timers__(struct rstp *r)
218 OVS_REQUIRES(rstp_mutex)
222 HMAP_FOR_EACH (p, node, &r->ports) {
223 decrement_timer(&p->hello_when);
224 decrement_timer(&p->tc_while);
225 decrement_timer(&p->fd_while);
226 decrement_timer(&p->rcvd_info_while);
227 decrement_timer(&p->rr_while);
228 decrement_timer(&p->rb_while);
229 decrement_timer(&p->mdelay_while);
230 decrement_timer(&p->edge_delay_while);
231 decrement_timer(&p->tx_count);
239 decrement_timer(uint16_t *timer)
246 /* Bridge State Machine. */
247 /* [17.28] Port Role Selection state machine. */
250 updt_role_disabled_tree(struct rstp *r)
251 OVS_REQUIRES(rstp_mutex)
255 HMAP_FOR_EACH (p, node, &r->ports) {
256 p->selected_role = ROLE_DISABLED;
261 clear_reselect_tree(struct rstp *r)
262 OVS_REQUIRES(rstp_mutex)
266 HMAP_FOR_EACH (p, node, &r->ports) {
272 updt_roles_tree__(struct rstp *r)
273 OVS_REQUIRES(rstp_mutex)
277 struct rstp_priority_vector best_vector, candidate_vector;
280 best_vector = r->bridge_priority;
282 r->root_times = r->bridge_times;
283 /* Letters a) b) c) */
284 HMAP_FOR_EACH (p, node, &r->ports) {
285 uint32_t old_root_path_cost;
286 uint32_t root_path_cost;
288 if (p->info_is != INFO_IS_RECEIVED) {
292 candidate_vector = p->port_priority;
293 candidate_vector.bridge_port_id = p->port_id;
294 old_root_path_cost = candidate_vector.root_path_cost;
295 root_path_cost = old_root_path_cost + p->port_path_cost;
296 candidate_vector.root_path_cost = root_path_cost;
298 if ((candidate_vector.designated_bridge_id & 0xffffffffffffULL) ==
299 (r->bridge_priority.designated_bridge_id & 0xffffffffffffULL)) {
302 if (compare_rstp_priority_vectors(&candidate_vector,
303 &best_vector) == SUPERIOR) {
304 best_vector = candidate_vector;
305 r->root_times = p->port_times;
306 r->root_times.message_age++;
307 vsel = p->port_number;
310 r->root_priority = best_vector;
311 r->root_port_id = best_vector.bridge_port_id;
312 VLOG_DBG("%s: new Root is "RSTP_ID_FMT, r->name,
313 RSTP_ID_ARGS(r->root_priority.root_bridge_id));
315 HMAP_FOR_EACH (p, node, &r->ports) {
316 p->designated_priority_vector.root_bridge_id =
317 r->root_priority.root_bridge_id;
318 p->designated_priority_vector.root_path_cost =
319 r->root_priority.root_path_cost;
320 p->designated_priority_vector.designated_bridge_id =
321 r->bridge_identifier;
322 p->designated_priority_vector.designated_port_id =
324 p->designated_times = r->root_times;
325 p->designated_times.hello_time = r->bridge_times.hello_time;
327 HMAP_FOR_EACH (p, node, &r->ports) {
328 switch (p->info_is) {
329 case INFO_IS_DISABLED:
330 p->selected_role = ROLE_DISABLED;
334 p->selected_role = ROLE_DESIGNATED;
337 p->selected_role = ROLE_DESIGNATED;
338 if (compare_rstp_priority_vectors(
339 &p->port_priority, &p->designated_priority_vector) != SAME
340 || !rstp_times_equal(&p->designated_times, &r->root_times)) {
344 case INFO_IS_RECEIVED:
345 if (vsel == p->port_number) { /* Letter i) */
346 p->selected_role = ROLE_ROOT;
347 p->updt_info = false;
348 } else if (compare_rstp_priority_vectors(
349 &p->designated_priority_vector,
350 &p->port_priority) == INFERIOR) {
351 if (p->port_priority.designated_bridge_id !=
352 r->bridge_identifier) {
353 p->selected_role = ROLE_ALTERNATE;
354 p->updt_info = false;
356 p->selected_role = ROLE_BACKUP;
357 p->updt_info = false;
360 p->selected_role = ROLE_DESIGNATED;
369 seq_change(connectivity_seq_get());
373 set_selected_tree(struct rstp *r)
374 OVS_REQUIRES(rstp_mutex)
378 HMAP_FOR_EACH (p, node, &r->ports) {
383 HMAP_FOR_EACH (p, node, &r->ports) {
389 port_role_selection_sm(struct rstp *r)
390 OVS_REQUIRES(rstp_mutex)
392 enum port_role_selection_state_machine old_state;
395 old_state = r->port_role_selection_sm_state;
397 switch (r->port_role_selection_sm_state) {
398 case PORT_ROLE_SELECTION_SM_INIT:
400 r->port_role_selection_sm_state =
401 PORT_ROLE_SELECTION_SM_INIT_BRIDGE_EXEC;
404 case PORT_ROLE_SELECTION_SM_INIT_BRIDGE_EXEC:
405 updt_role_disabled_tree(r);
406 r->port_role_selection_sm_state = PORT_ROLE_SELECTION_SM_INIT_BRIDGE;
408 case PORT_ROLE_SELECTION_SM_INIT_BRIDGE:
409 r->port_role_selection_sm_state =
410 PORT_ROLE_SELECTION_SM_ROLE_SELECTION_EXEC;
412 case PORT_ROLE_SELECTION_SM_ROLE_SELECTION_EXEC:
413 clear_reselect_tree(r);
414 updt_roles_tree__(r);
415 set_selected_tree(r);
416 r->port_role_selection_sm_state =
417 PORT_ROLE_SELECTION_SM_ROLE_SELECTION;
419 case PORT_ROLE_SELECTION_SM_ROLE_SELECTION:
420 HMAP_FOR_EACH (p, node, &r->ports) {
422 r->port_role_selection_sm_state =
423 PORT_ROLE_SELECTION_SM_ROLE_SELECTION_EXEC;
432 if (old_state != r->port_role_selection_sm_state) {
434 VLOG_DBG("%s: Port_role_selection_sm %d -> %d", r->name,
435 old_state, r->port_role_selection_sm_state);
440 /* Port State Machines */
442 /* [17.23 - Port receive state machine] */
445 updt_bpdu_version(struct rstp_port *p) /* [17.21.22] */
446 OVS_REQUIRES(rstp_mutex)
448 switch (p->received_bpdu_buffer.bpdu_type) {
449 case CONFIGURATION_BPDU:
450 case TOPOLOGY_CHANGE_NOTIFICATION_BPDU:
451 p->rcvd_rstp = false;
454 case RAPID_SPANNING_TREE_BPDU:
465 port_receive_sm(struct rstp_port *p)
466 OVS_REQUIRES(rstp_mutex)
468 enum port_receive_state_machine old_state;
471 old_state = p->port_receive_sm_state;
474 switch (p->port_receive_sm_state) {
475 case PORT_RECEIVE_SM_INIT:
476 if (r->begin || ((p->rcvd_bpdu || (p->edge_delay_while !=
477 r->migrate_time)) && !p->port_enabled)) {
478 p->port_receive_sm_state = PORT_RECEIVE_SM_DISCARD_EXEC;
481 case PORT_RECEIVE_SM_DISCARD_EXEC:
482 p->rcvd_bpdu = p->rcvd_rstp = p->rcvd_stp = false;
484 p->edge_delay_while = r->migrate_time;
485 p->port_receive_sm_state = PORT_RECEIVE_SM_DISCARD;
487 case PORT_RECEIVE_SM_DISCARD:
488 if (p->rcvd_bpdu && p->port_enabled) {
489 p->port_receive_sm_state = PORT_RECEIVE_SM_RECEIVE_EXEC;
492 case PORT_RECEIVE_SM_RECEIVE_EXEC:
493 updt_bpdu_version(p);
494 p->oper_edge = p->rcvd_bpdu = false;
496 p->edge_delay_while = r->migrate_time;
497 p->port_receive_sm_state = PORT_RECEIVE_SM_RECEIVE;
499 case PORT_RECEIVE_SM_RECEIVE:
500 if (p->rcvd_bpdu && p->port_enabled && !p->rcvd_msg) {
501 p->port_receive_sm_state = PORT_RECEIVE_SM_RECEIVE_EXEC;
508 if (old_state != p->port_receive_sm_state) {
510 VLOG_DBG("%s, port %u: Port_receive_sm %d -> %d", p->rstp->name,
511 p->port_number, old_state, p->port_receive_sm_state);
516 /* [17.24 - Port Protocol Migration state machine] */
518 port_protocol_migration_sm(struct rstp_port *p)
519 OVS_REQUIRES(rstp_mutex)
521 enum port_protocol_migration_state_machine old_state;
524 old_state = p->port_protocol_migration_sm_state;
527 switch (p->port_protocol_migration_sm_state) {
528 case PORT_PROTOCOL_MIGRATION_SM_INIT:
529 p->port_protocol_migration_sm_state =
530 PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP_EXEC;
532 case PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP_EXEC:
534 p->send_rstp = r->rstp_version;
535 p->mdelay_while = r->migrate_time;
536 p->port_protocol_migration_sm_state =
537 PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP;
539 case PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP:
540 if (p->mdelay_while == 0) {
541 p->port_protocol_migration_sm_state =
542 PORT_PROTOCOL_MIGRATION_SM_SENSING_EXEC;
543 } else if ((p->mdelay_while != r->migrate_time) && !p->port_enabled) {
544 p->port_protocol_migration_sm_state =
545 PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP_EXEC;
548 case PORT_PROTOCOL_MIGRATION_SM_SELECTING_STP_EXEC:
549 p->send_rstp = false;
550 p->mdelay_while = r->migrate_time;
551 p->port_protocol_migration_sm_state =
552 PORT_PROTOCOL_MIGRATION_SM_SELECTING_STP;
554 case PORT_PROTOCOL_MIGRATION_SM_SELECTING_STP:
555 if ((p->mdelay_while == 0) || (!p->port_enabled) || p->mcheck) {
556 p->port_protocol_migration_sm_state =
557 PORT_PROTOCOL_MIGRATION_SM_SENSING_EXEC;
560 case PORT_PROTOCOL_MIGRATION_SM_SENSING_EXEC:
561 p->rcvd_rstp = false;
563 p->port_protocol_migration_sm_state =
564 PORT_PROTOCOL_MIGRATION_SM_SENSING;
566 case PORT_PROTOCOL_MIGRATION_SM_SENSING:
567 if (!p->port_enabled || p->mcheck || ((r->rstp_version) &&
568 !p->send_rstp && p->rcvd_rstp)) {
569 p->port_protocol_migration_sm_state =
570 PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP_EXEC;
571 } else if (p->send_rstp && p->rcvd_stp) {
572 p->port_protocol_migration_sm_state =
573 PORT_PROTOCOL_MIGRATION_SM_SELECTING_STP_EXEC;
580 if (old_state != p->port_protocol_migration_sm_state) {
582 VLOG_DBG("%s, port %u: port_protocol_migration_sm %d -> %d",
583 p->rstp->name, p->port_number, old_state,
584 p->port_protocol_migration_sm_state);
590 /* [17.25 - Bridge Detection state machine] */
592 bridge_detection_sm(struct rstp_port *p)
593 OVS_REQUIRES(rstp_mutex)
595 enum bridge_detection_state_machine old_state;
598 old_state = p->bridge_detection_sm_state;
601 switch (p->bridge_detection_sm_state) {
602 case BRIDGE_DETECTION_SM_INIT:
603 if (r->begin && p->admin_edge) {
604 p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_EDGE_EXEC;
605 } else if (r->begin && !p->admin_edge) {
606 p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_NOT_EDGE_EXEC;
609 case BRIDGE_DETECTION_SM_EDGE_EXEC:
611 p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_EDGE;
613 case BRIDGE_DETECTION_SM_EDGE:
614 if ((!p->port_enabled && !p->admin_edge) || !p->oper_edge) {
615 p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_NOT_EDGE_EXEC;
618 case BRIDGE_DETECTION_SM_NOT_EDGE_EXEC:
619 p->oper_edge = false;
620 p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_NOT_EDGE;
622 case BRIDGE_DETECTION_SM_NOT_EDGE:
623 if ((!p->port_enabled && p->admin_edge)
624 || ((p->edge_delay_while == 0) && p->auto_edge && p->send_rstp
626 p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_EDGE_EXEC;
633 if (old_state != p->bridge_detection_sm_state) {
635 VLOG_DBG("%s, port %u: bridge_detection_sm %d -> %d", p->rstp->name,
636 p->port_number, old_state, p->bridge_detection_sm_state);
641 /* [17.26 - Port Transmit state machine] */
643 rstp_send_bpdu(struct rstp_port *p, const void *bpdu, size_t bpdu_size)
644 OVS_REQUIRES(rstp_mutex)
646 struct eth_header *eth;
647 struct llc_header *llc;
651 pkt = ofpbuf_new(ETH_HEADER_LEN + LLC_HEADER_LEN + bpdu_size);
652 eth = ofpbuf_put_zeros(pkt, sizeof *eth);
653 llc = ofpbuf_put_zeros(pkt, sizeof *llc);
654 ofpbuf_set_frame(pkt, eth);
655 ofpbuf_set_l3(pkt, ofpbuf_put(pkt, bpdu, bpdu_size));
658 memcpy(eth->eth_dst, eth_addr_stp, ETH_ADDR_LEN);
659 /* p->rstp->send_bpdu() must fill in source address. */
660 eth->eth_type = htons(ofpbuf_size(pkt) - ETH_HEADER_LEN);
663 llc->llc_dsap = STP_LLC_DSAP;
664 llc->llc_ssap = STP_LLC_SSAP;
665 llc->llc_cntl = STP_LLC_CNTL;
666 p->rstp->send_bpdu(pkt, p->aux, p->rstp->aux);
670 record_agreement(struct rstp_port *p)
671 OVS_REQUIRES(rstp_mutex)
676 if (r->rstp_version && p->oper_point_to_point_mac &&
677 ((p->received_bpdu_buffer.flags & BPDU_FLAG_AGREEMENT))) {
679 p->proposing = false;
686 set_tc_flags(struct rstp_port *p)
687 OVS_REQUIRES(rstp_mutex)
689 /* Sets rcvd_tc and/or rcvd_tc_ack if the Topology Change and/or Topology
690 * Change Acknowledgment flags, respectively, are set in a ConfigBPDU or
693 if (p->received_bpdu_buffer.bpdu_type == CONFIGURATION_BPDU ||
694 p->received_bpdu_buffer.bpdu_type == RAPID_SPANNING_TREE_BPDU) {
695 if ((p->received_bpdu_buffer.flags & BPDU_FLAG_TOPCHANGE) != 0) {
698 if ((p->received_bpdu_buffer.flags & BPDU_FLAG_TOPCHANGEACK) != 0) {
699 p->rcvd_tc_ack = true;
702 /* Sets rcvd_tcn true if the BPDU is a TCN BPDU. */
703 if (p->received_bpdu_buffer.bpdu_type
704 == TOPOLOGY_CHANGE_NOTIFICATION_BPDU) {
710 record_dispute(struct rstp_port *p)
711 OVS_REQUIRES(rstp_mutex)
713 if ((p->received_bpdu_buffer.flags & BPDU_FLAG_LEARNING) != 0) {
715 p->proposing = false;
720 record_proposal(struct rstp_port *p)
721 OVS_REQUIRES(rstp_mutex)
723 enum port_flag role =
724 ((p->received_bpdu_buffer.flags) & ROLE_FLAG_MASK) >> ROLE_FLAG_SHIFT;
726 if ((role == PORT_DES)
727 && ((p->received_bpdu_buffer.flags & BPDU_FLAG_PROPOSAL) != 0)) {
733 record_priority(struct rstp_port *p)
734 OVS_REQUIRES(rstp_mutex)
736 p->port_priority.root_bridge_id = p->msg_priority.root_bridge_id;
737 p->port_priority.root_path_cost = p->msg_priority.root_path_cost;
738 p->port_priority.designated_bridge_id =
739 p->msg_priority.designated_bridge_id;
740 p->port_priority.designated_port_id = p->msg_priority.designated_port_id;
744 record_times(struct rstp_port *p)
745 OVS_REQUIRES(rstp_mutex)
747 p->port_times = p->msg_times;
748 if (p->msg_times.hello_time == 0) {
749 p->port_times.hello_time = 1;
754 updt_rcvd_info_while(struct rstp_port *p)
755 OVS_REQUIRES(rstp_mutex)
758 * The value assigned to rcvdInfoWhile is the three times the Hello Time,
759 * if Message Age, incremented by 1 second and rounded to the nearest whole
760 * second, does not exceed Max Age, and is zero otherwise.
762 if (p->port_times.message_age < p->port_times.max_age) {
763 p->rcvd_info_while = p->port_times.hello_time * 3;
765 p->rcvd_info_while = 0;
769 /* Times are internally held in seconds, while the protocol uses 1/256 seconds.
770 * time_encode() is used to convert time values sent in bpdus, while
771 * time_decode() is used to convert time values received in bpdus.
774 time_encode(uint8_t value)
776 return htons(value * 256);
780 time_decode(ovs_be16 encoded)
782 return ntohs(encoded) / 256;
787 tx_config(struct rstp_port *p)
788 OVS_REQUIRES(rstp_mutex)
790 struct rstp_bpdu bpdu;
792 bpdu.protocol_identifier = htons(0);
793 bpdu.protocol_version_identifier = 0;
794 bpdu.bpdu_type = CONFIGURATION_BPDU;
795 bpdu.root_bridge_id = htonll(p->designated_priority_vector.root_bridge_id);
796 bpdu.root_path_cost = htonl(p->designated_priority_vector.root_path_cost);
797 bpdu.designated_bridge_id =
798 htonll(p->designated_priority_vector.designated_bridge_id);
799 bpdu.designated_port_id =
800 htons(p->designated_priority_vector.designated_port_id);
801 bpdu.message_age = time_encode(p->designated_times.message_age);
802 bpdu.max_age = time_encode(p->designated_times.max_age);
803 bpdu.hello_time = time_encode(p->designated_times.hello_time);
804 bpdu.forward_delay = time_encode(p->designated_times.forward_delay);
806 if (p->tc_while != 0) {
807 bpdu.flags |= BPDU_FLAG_TOPCHANGE;
809 if (p->tc_ack != 0) {
810 bpdu.flags |= BPDU_FLAG_TOPCHANGEACK;
812 rstp_send_bpdu(p, &bpdu, sizeof(struct rstp_bpdu));
817 tx_rstp(struct rstp_port *p)
818 OVS_REQUIRES(rstp_mutex)
820 struct rstp_bpdu bpdu;
822 bpdu.protocol_identifier = htons(0);
823 bpdu.protocol_version_identifier = 2;
824 bpdu.bpdu_type = RAPID_SPANNING_TREE_BPDU;
825 bpdu.root_bridge_id = htonll(p->designated_priority_vector.root_bridge_id);
826 bpdu.root_path_cost = htonl(p->designated_priority_vector.root_path_cost);
827 bpdu.designated_bridge_id =
828 htonll(p->designated_priority_vector.designated_bridge_id);
829 bpdu.designated_port_id =
830 htons(p->designated_priority_vector.designated_port_id);
831 bpdu.message_age = time_encode(p->designated_times.message_age);
832 bpdu.max_age = time_encode(p->designated_times.max_age);
833 bpdu.hello_time = time_encode(p->designated_times.hello_time);
834 bpdu.forward_delay = time_encode(p->designated_times.forward_delay);
839 bpdu.flags = PORT_ROOT << ROLE_FLAG_SHIFT;
841 case ROLE_DESIGNATED:
842 bpdu.flags = PORT_DES << ROLE_FLAG_SHIFT;
846 bpdu.flags = PORT_ALT_BACK << ROLE_FLAG_SHIFT;
849 /* Should not happen! */
850 VLOG_ERR("%s transmitting bpdu in disabled role on port "
851 RSTP_PORT_ID_FMT, p->rstp->name, p->port_id);
855 bpdu.flags |= BPDU_FLAG_AGREEMENT;
858 bpdu.flags |= BPDU_FLAG_PROPOSAL;
860 if (p->tc_while != 0) {
861 bpdu.flags |= BPDU_FLAG_TOPCHANGE;
864 bpdu.flags |= BPDU_FLAG_LEARNING;
867 bpdu.flags |= BPDU_FLAG_FORWARDING;
869 bpdu.version1_length = 0;
870 rstp_send_bpdu(p, &bpdu, sizeof(struct rstp_bpdu));
875 tx_tcn(struct rstp_port *p)
876 OVS_REQUIRES(rstp_mutex)
878 struct rstp_bpdu bpdu;
880 memset(&bpdu, 0, sizeof(struct rstp_bpdu));
882 bpdu.protocol_identifier = htons(0);
883 bpdu.protocol_version_identifier = 0;
884 bpdu.bpdu_type = TOPOLOGY_CHANGE_NOTIFICATION_BPDU;
885 rstp_send_bpdu(p, &bpdu, sizeof(struct rstp_bpdu));
889 port_transmit_sm(struct rstp_port *p)
890 OVS_REQUIRES(rstp_mutex)
892 enum port_transmit_state_machine old_state;
895 old_state = p->port_transmit_sm_state;
898 switch (p->port_transmit_sm_state) {
899 case PORT_TRANSMIT_SM_INIT:
901 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_INIT_EXEC;
904 case PORT_TRANSMIT_SM_TRANSMIT_INIT_EXEC:
907 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_INIT;
909 case PORT_TRANSMIT_SM_TRANSMIT_INIT:
910 p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
912 case PORT_TRANSMIT_SM_TRANSMIT_PERIODIC_EXEC:
913 p->new_info = p->new_info || (p->role == ROLE_DESIGNATED ||
914 (p->role == ROLE_ROOT && p->tc_while != 0));
915 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_PERIODIC;
917 case PORT_TRANSMIT_SM_TRANSMIT_PERIODIC:
918 p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
920 case PORT_TRANSMIT_SM_IDLE_EXEC:
921 p->hello_when = r->bridge_hello_time;
922 p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE;
924 case PORT_TRANSMIT_SM_IDLE:
925 if (p->role == ROLE_DISABLED) {
926 VLOG_DBG("%s, port %u: port_transmit_sm ROLE == DISABLED.",
927 p->rstp->name, p->port_number);
929 } else if (p->send_rstp && p->new_info
930 && p->tx_count < r->transmit_hold_count
931 && p->hello_when != 0 && p->selected && !p->updt_info) {
932 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_RSTP_EXEC;
933 } else if (p->hello_when == 0 && p->selected && !p->updt_info) {
934 p->port_transmit_sm_state =
935 PORT_TRANSMIT_SM_TRANSMIT_PERIODIC_EXEC;
936 } else if (!p->send_rstp && p->new_info && p->role == ROLE_ROOT
937 && p->tx_count < r->transmit_hold_count
938 && p->hello_when != 0 && p->selected && !p->updt_info) {
939 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_TCN_EXEC;
940 } else if (!p->send_rstp && p->new_info && p->role == ROLE_DESIGNATED
941 && p->tx_count < r->transmit_hold_count
942 && p->hello_when != 0 && p->selected && !p->updt_info) {
943 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_CONFIG_EXEC;
946 case PORT_TRANSMIT_SM_TRANSMIT_CONFIG_EXEC:
951 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_CONFIG;
953 case PORT_TRANSMIT_SM_TRANSMIT_CONFIG:
954 p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
956 case PORT_TRANSMIT_SM_TRANSMIT_TCN_EXEC:
960 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_TCN;
962 case PORT_TRANSMIT_SM_TRANSMIT_TCN:
963 p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
965 case PORT_TRANSMIT_SM_TRANSMIT_RSTP_EXEC:
970 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_RSTP;
972 case PORT_TRANSMIT_SM_TRANSMIT_RSTP:
973 p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
979 if (old_state != p->port_transmit_sm_state) {
981 VLOG_DBG("%s, port %u: port_transmit_sm %d -> %d", p->rstp->name,
982 p->port_number, old_state, p->port_transmit_sm_state);
987 /* [17.27 Port Information state machine] */
992 rcv_info(struct rstp_port *p)
993 OVS_REQUIRES(rstp_mutex)
995 enum vector_comparison cp;
999 p->msg_priority.root_bridge_id =
1000 ntohll(p->received_bpdu_buffer.root_bridge_id);
1001 p->msg_priority.root_path_cost =
1002 ntohl(p->received_bpdu_buffer.root_path_cost);
1003 p->msg_priority.designated_bridge_id =
1004 ntohll(p->received_bpdu_buffer.designated_bridge_id);
1005 p->msg_priority.designated_port_id =
1006 ntohs(p->received_bpdu_buffer.designated_port_id);
1008 p->msg_times.forward_delay =
1009 time_decode(p->received_bpdu_buffer.forward_delay);
1010 p->msg_times.hello_time = time_decode(p->received_bpdu_buffer.hello_time);
1011 p->msg_times.max_age = time_decode(p->received_bpdu_buffer.max_age);
1012 p->msg_times.message_age =
1013 time_decode(p->received_bpdu_buffer.message_age);
1015 cp = compare_rstp_priority_vectors(&p->msg_priority, &p->port_priority);
1016 ct = rstp_times_equal(&p->port_times, &p->msg_times);
1018 (p->received_bpdu_buffer.flags & ROLE_FLAG_MASK) >> ROLE_FLAG_SHIFT;
1020 /* Returns SuperiorDesignatedInfo if:
1021 * a) The received message conveys a Designated Port Role, and
1022 * 1) The message priority is superior (17.6) to the Port.s port priority
1024 * 2) The message priority vector is the same as the Port.s port priority
1025 * vector, and any of the received timer parameter values (msg_times.
1026 * 17.19.15) differ from those already held for the Port (port_times
1028 * NOTE: Configuration BPDU explicitly conveys a Designated Port Role.
1030 if ((role == PORT_DES
1031 || p->received_bpdu_buffer.bpdu_type == CONFIGURATION_BPDU)
1032 && (cp == SUPERIOR || (cp == SAME && ct == false))) {
1033 return SUPERIOR_DESIGNATED_INFO;
1035 /* Returns RepeatedDesignatedInfo if:
1036 * b) The received message conveys Designated Port Role, and a message
1037 * priority vector and timer parameters that are the same as the
1038 * Port's port priority vector or timer values. */
1039 } else if (role == PORT_DES && cp == SAME && ct == true) {
1040 return REPEATED_DESIGNATED_INFO;
1042 /* Returns InferiorDesignatedInfo if:
1043 * c) The received message conveys a Designated Port Role, and a
1044 * message priority vector that is worse than the Port's port
1045 * priority vector. */
1046 } else if (role == PORT_DES && cp == INFERIOR) {
1047 return INFERIOR_DESIGNATED_INFO;
1049 /* Returns InferiorRootAlternateInfo if:
1050 * d) The received message conveys a Root Port, Alternate Port, or
1051 * Backup Port Role and a message priority that is the same as or
1052 * worse than the port priority vector. */
1053 } else if ((role == PORT_ROOT || role == PORT_ALT_BACK) &&
1054 (cp == INFERIOR || cp == SAME)) {
1055 return INFERIOR_ROOT_ALTERNATE_INFO;
1057 /* Otherwise, returns OtherInfo. */
1064 better_or_same_info(struct rstp_port *p, int new_info_is)
1065 OVS_REQUIRES(rstp_mutex)
1068 (new_info_is == RECEIVED && p->info_is == INFO_IS_RECEIVED
1069 && compare_rstp_priority_vectors(&p->msg_priority,
1071 || (new_info_is == MINE && p->info_is == INFO_IS_MINE
1072 && compare_rstp_priority_vectors(&p->designated_priority_vector,
1073 &p->port_priority));
1077 port_information_sm(struct rstp_port *p)
1078 OVS_REQUIRES(rstp_mutex)
1080 enum port_information_state_machine old_state;
1083 old_state = p->port_information_sm_state;
1086 if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1087 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1089 switch (p->port_information_sm_state) {
1090 case PORT_INFORMATION_SM_INIT:
1092 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1095 case PORT_INFORMATION_SM_DISABLED_EXEC:
1096 p->rcvd_msg = false;
1097 p->proposing = p->proposed = p->agree = p->agreed = false;
1098 p->rcvd_info_while = 0;
1099 p->info_is = INFO_IS_DISABLED;
1101 p->selected = false;
1102 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED;
1104 case PORT_INFORMATION_SM_DISABLED:
1105 if (p->port_enabled) {
1106 p->port_information_sm_state = PORT_INFORMATION_SM_AGED_EXEC;
1107 } else if (p->rcvd_msg) {
1108 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1111 case PORT_INFORMATION_SM_AGED_EXEC:
1112 p->info_is = INFO_IS_AGED;
1114 p->selected = false;
1115 p->port_information_sm_state = PORT_INFORMATION_SM_AGED;
1117 case PORT_INFORMATION_SM_AGED:
1118 if (p->selected && p->updt_info) {
1119 p->port_information_sm_state = PORT_INFORMATION_SM_UPDATE_EXEC;
1122 case PORT_INFORMATION_SM_UPDATE_EXEC:
1123 p->proposing = p->proposed = false;
1124 /* MINE is not specified in Standard 802.1D-2004. */
1125 p->agreed = p->agreed && better_or_same_info(p, MINE);
1126 p->synced = p->synced && p->agreed;
1127 p->port_priority.root_bridge_id =
1128 p->designated_priority_vector.root_bridge_id;
1129 p->port_priority.root_path_cost =
1130 p->designated_priority_vector.root_path_cost;
1131 p->port_priority.designated_bridge_id =
1132 p->designated_priority_vector.designated_bridge_id;
1133 p->port_priority.designated_port_id =
1134 p->designated_priority_vector.designated_port_id;
1135 p->port_times = p->designated_times;
1136 p->updt_info = false;
1137 p->info_is = INFO_IS_MINE;
1139 p->port_information_sm_state = PORT_INFORMATION_SM_UPDATE;
1141 case PORT_INFORMATION_SM_UPDATE:
1142 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1144 case PORT_INFORMATION_SM_CURRENT_EXEC:
1145 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT;
1147 case PORT_INFORMATION_SM_CURRENT:
1148 if (p->rcvd_msg && !p->updt_info) {
1149 p->port_information_sm_state = PORT_INFORMATION_SM_RECEIVE_EXEC;
1150 } else if (p->selected && p->updt_info) {
1151 p->port_information_sm_state = PORT_INFORMATION_SM_UPDATE_EXEC;
1152 } else if ((p->info_is == INFO_IS_RECEIVED) &&
1153 (p->rcvd_info_while == 0) && !p->updt_info &&
1155 p->port_information_sm_state = PORT_INFORMATION_SM_AGED_EXEC;
1158 case PORT_INFORMATION_SM_RECEIVE_EXEC:
1159 p->rcvd_info = rcv_info(p);
1160 p->port_information_sm_state = PORT_INFORMATION_SM_RECEIVE;
1162 case PORT_INFORMATION_SM_RECEIVE:
1163 switch (p->rcvd_info) {
1164 case SUPERIOR_DESIGNATED_INFO:
1165 p->port_information_sm_state =
1166 PORT_INFORMATION_SM_SUPERIOR_DESIGNATED_EXEC;
1168 case REPEATED_DESIGNATED_INFO:
1169 p->port_information_sm_state =
1170 PORT_INFORMATION_SM_REPEATED_DESIGNATED_EXEC;
1172 case INFERIOR_DESIGNATED_INFO:
1173 p->port_information_sm_state =
1174 PORT_INFORMATION_SM_INFERIOR_DESIGNATED_EXEC;
1176 case INFERIOR_ROOT_ALTERNATE_INFO:
1177 p->port_information_sm_state =
1178 PORT_INFORMATION_SM_NOT_DESIGNATED_EXEC;
1181 p->port_information_sm_state = PORT_INFORMATION_SM_OTHER_EXEC;
1188 case PORT_INFORMATION_SM_OTHER_EXEC:
1189 p->rcvd_msg = false;
1190 p->port_information_sm_state = PORT_INFORMATION_SM_OTHER;
1192 case PORT_INFORMATION_SM_OTHER:
1193 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1195 case PORT_INFORMATION_SM_NOT_DESIGNATED_EXEC:
1196 record_agreement(p);
1198 p->rcvd_msg = false;
1199 p->port_information_sm_state = PORT_INFORMATION_SM_NOT_DESIGNATED;
1201 case PORT_INFORMATION_SM_NOT_DESIGNATED:
1202 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1204 case PORT_INFORMATION_SM_INFERIOR_DESIGNATED_EXEC:
1206 p->rcvd_msg = false;
1207 p->port_information_sm_state = PORT_INFORMATION_SM_INFERIOR_DESIGNATED;
1209 case PORT_INFORMATION_SM_INFERIOR_DESIGNATED:
1210 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1212 case PORT_INFORMATION_SM_REPEATED_DESIGNATED_EXEC:
1215 updt_rcvd_info_while(p);
1216 p->rcvd_msg = false;
1217 p->port_information_sm_state = PORT_INFORMATION_SM_REPEATED_DESIGNATED;
1219 case PORT_INFORMATION_SM_REPEATED_DESIGNATED:
1220 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1222 case PORT_INFORMATION_SM_SUPERIOR_DESIGNATED_EXEC:
1223 p->agreed = p->proposing = false;
1226 /* RECEIVED is not specified in Standard 802.1D-2004. */
1227 p->agree = p->agree && better_or_same_info(p, RECEIVED);
1230 updt_rcvd_info_while(p);
1231 p->info_is = INFO_IS_RECEIVED;
1233 p->selected = false;
1234 p->rcvd_msg = false;
1235 p->port_information_sm_state = PORT_INFORMATION_SM_SUPERIOR_DESIGNATED;
1237 case PORT_INFORMATION_SM_SUPERIOR_DESIGNATED:
1238 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1244 if (old_state != p->port_information_sm_state) {
1246 VLOG_DBG("%s, port %u: Port_information_sm %d -> %d", p->rstp->name,
1247 p->port_number, old_state, p->port_information_sm_state);
1252 /* [17.29 Port Role Transitions state machine] */
1255 set_re_root_tree(struct rstp_port *p)
1256 OVS_REQUIRES(rstp_mutex)
1259 struct rstp_port *p1;
1262 HMAP_FOR_EACH (p1, node, &r->ports) {
1268 set_sync_tree(struct rstp_port *p)
1269 OVS_REQUIRES(rstp_mutex)
1272 struct rstp_port *p1;
1275 HMAP_FOR_EACH (p1, node, &r->ports) {
1281 hello_time(struct rstp_port *p)
1282 OVS_REQUIRES(rstp_mutex)
1284 return p->designated_times.hello_time;
1288 fwd_delay(struct rstp_port *p)
1289 OVS_REQUIRES(rstp_mutex)
1291 return p->designated_times.forward_delay;
1295 forward_delay(struct rstp_port *p)
1296 OVS_REQUIRES(rstp_mutex)
1299 return hello_time(p);
1301 return fwd_delay(p);
1306 edge_delay(struct rstp_port *p)
1307 OVS_REQUIRES(rstp_mutex)
1312 if (p->oper_point_to_point_mac == 1) {
1313 return r->migrate_time;
1315 return p->designated_times.max_age;
1320 check_selected_role_change(struct rstp_port *p, int current_role_state)
1321 OVS_REQUIRES(rstp_mutex)
1323 if (p->selected && !p->updt_info && p->role != p->selected_role
1324 && p->selected_role != current_role_state) {
1325 VLOG_DBG("%s, port %u: case: current = %s role = %s selected = %d",
1326 p->rstp->name, p->port_number,
1327 rstp_port_role_name(current_role_state),
1328 rstp_port_role_name(p->role), p->selected_role);
1329 switch (p->selected_role) {
1331 p->port_role_transition_sm_state =
1332 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1334 case ROLE_DESIGNATED:
1335 p->port_role_transition_sm_state =
1336 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1338 case ROLE_ALTERNATE:
1339 p->port_role_transition_sm_state =
1340 PORT_ROLE_TRANSITION_SM_BLOCK_PORT_EXEC;
1343 p->port_role_transition_sm_state =
1344 PORT_ROLE_TRANSITION_SM_BLOCK_PORT_EXEC;
1347 p->port_role_transition_sm_state =
1348 PORT_ROLE_TRANSITION_SM_DISABLE_PORT_EXEC;
1356 re_rooted(struct rstp_port *p)
1357 OVS_REQUIRES(rstp_mutex)
1360 struct rstp_port *p1;
1363 HMAP_FOR_EACH (p1, node, &r->ports) {
1364 if ((p1 != p) && (p1->rr_while != 0)) {
1372 all_synced(struct rstp *r)
1373 OVS_REQUIRES(rstp_mutex)
1375 struct rstp_port *p;
1377 HMAP_FOR_EACH (p, node, &r->ports) {
1378 if (!(p->selected && p->role == p->selected_role &&
1379 (p->role == ROLE_ROOT || p->synced == true))) {
1387 port_role_transition_sm(struct rstp_port *p)
1388 OVS_REQUIRES(rstp_mutex)
1390 enum port_role_transition_state_machine old_state;
1392 enum rstp_port_role last_role;
1394 old_state = p->port_role_transition_sm_state;
1396 last_role = p->role;
1398 switch (p->port_role_transition_sm_state) {
1399 case PORT_ROLE_TRANSITION_SM_INIT:
1401 p->port_role_transition_sm_state =
1402 PORT_ROLE_TRANSITION_SM_INIT_PORT_EXEC;
1405 case PORT_ROLE_TRANSITION_SM_INIT_PORT_EXEC:
1406 p->role = ROLE_DISABLED;
1407 p->learn = p->forward = false;
1409 p->sync = p->re_root = true;
1410 p->rr_while = p->designated_times.forward_delay;
1411 p->fd_while = p->designated_times.max_age;
1413 p->port_role_transition_sm_state =
1414 PORT_ROLE_TRANSITION_SM_DISABLE_PORT_EXEC;
1416 case PORT_ROLE_TRANSITION_SM_DISABLE_PORT_EXEC:
1417 p->role = p->selected_role;
1418 p->learn = p->forward = false;
1419 p->port_role_transition_sm_state =
1420 PORT_ROLE_TRANSITION_SM_DISABLE_PORT;
1422 case PORT_ROLE_TRANSITION_SM_DISABLE_PORT:
1423 if (check_selected_role_change(p, ROLE_DISABLED)) {
1425 } else if (p->selected && !p->updt_info && !p->learning
1426 && !p->forwarding) {
1427 p->port_role_transition_sm_state =
1428 PORT_ROLE_TRANSITION_SM_DISABLED_PORT_EXEC;
1431 case PORT_ROLE_TRANSITION_SM_DISABLED_PORT_EXEC:
1432 p->fd_while = p->designated_times.max_age;
1435 p->sync = p->re_root = false;
1436 p->port_role_transition_sm_state =
1437 PORT_ROLE_TRANSITION_SM_DISABLED_PORT;
1439 case PORT_ROLE_TRANSITION_SM_DISABLED_PORT:
1440 if (check_selected_role_change(p, ROLE_DISABLED)) {
1442 } else if (p->selected && !p->updt_info
1443 && (p->fd_while != p->designated_times.max_age || p->sync
1444 || p->re_root || !p->synced)) {
1445 p->port_role_transition_sm_state =
1446 PORT_ROLE_TRANSITION_SM_DISABLED_PORT_EXEC;
1449 case PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC:
1450 p->role = ROLE_ROOT;
1451 p->rr_while = p->designated_times.forward_delay;
1452 p->port_role_transition_sm_state = PORT_ROLE_TRANSITION_SM_ROOT_PORT;
1454 case PORT_ROLE_TRANSITION_SM_ROOT_PORT:
1455 if (check_selected_role_change(p, ROLE_ROOT)) {
1457 } else if (p->selected && !p->updt_info) {
1458 if (p->rr_while != p->designated_times.forward_delay) {
1459 p->port_role_transition_sm_state =
1460 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1462 } else if (p->re_root && p->forward) {
1463 p->port_role_transition_sm_state =
1464 PORT_ROLE_TRANSITION_SM_REROOTED_EXEC;
1466 } else if ((p->fd_while == 0
1467 || ((re_rooted(p) && p->rb_while == 0)
1468 && r->rstp_version)) && !p->learn) {
1469 p->port_role_transition_sm_state =
1470 PORT_ROLE_TRANSITION_SM_ROOT_LEARN_EXEC;
1472 } else if ((p->fd_while == 0
1473 || ((re_rooted(p) && p->rb_while == 0)
1474 && r->rstp_version)) && p->learn && !p->forward) {
1475 p->port_role_transition_sm_state =
1476 PORT_ROLE_TRANSITION_SM_ROOT_FORWARD_EXEC;
1478 } else if (p->proposed && !p->agree) {
1479 p->port_role_transition_sm_state =
1480 PORT_ROLE_TRANSITION_SM_ROOT_PROPOSED_EXEC;
1482 } else if ((all_synced(r) && !p->agree) ||
1483 (p->proposed && p->agree)) {
1484 p->port_role_transition_sm_state =
1485 PORT_ROLE_TRANSITION_SM_ROOT_AGREED_EXEC;
1487 } else if (!p->forward && !p->re_root) {
1488 p->port_role_transition_sm_state =
1489 PORT_ROLE_TRANSITION_SM_REROOT_EXEC;
1494 case PORT_ROLE_TRANSITION_SM_REROOT_EXEC:
1495 set_re_root_tree(p);
1496 p->port_role_transition_sm_state =
1497 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1499 case PORT_ROLE_TRANSITION_SM_ROOT_AGREED_EXEC:
1500 p->proposed = p->sync = false;
1501 p->agree = p->new_info = true;
1502 p->port_role_transition_sm_state =
1503 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1505 case PORT_ROLE_TRANSITION_SM_ROOT_PROPOSED_EXEC:
1507 p->proposed = false;
1508 p->port_role_transition_sm_state =
1509 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1511 case PORT_ROLE_TRANSITION_SM_ROOT_FORWARD_EXEC:
1514 p->port_role_transition_sm_state =
1515 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1517 case PORT_ROLE_TRANSITION_SM_ROOT_LEARN_EXEC:
1518 p->fd_while = forward_delay(p);
1520 p->port_role_transition_sm_state =
1521 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1523 case PORT_ROLE_TRANSITION_SM_REROOTED_EXEC:
1525 p->port_role_transition_sm_state =
1526 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1528 case PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC:
1529 p->role = ROLE_DESIGNATED;
1530 p->port_role_transition_sm_state =
1531 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT;
1533 case PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT:
1534 if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1536 } else if (p->selected && !p->updt_info) {
1537 if (((p->sync && !p->synced)
1538 || (p->re_root && p->rr_while != 0) || p->disputed)
1539 && !p->oper_edge && (p->learn || p->forward)) {
1540 p->port_role_transition_sm_state =
1541 PORT_ROLE_TRANSITION_SM_DESIGNATED_DISCARD_EXEC;
1542 } else if ((p->fd_while == 0 || p->agreed || p->oper_edge)
1543 && (p->rr_while == 0 || !p->re_root)
1544 && !p->sync && !p->learn) {
1545 p->port_role_transition_sm_state =
1546 PORT_ROLE_TRANSITION_SM_DESIGNATED_LEARN_EXEC;
1547 } else if ((p->fd_while == 0 || p->agreed || p->oper_edge)
1548 && (p->rr_while == 0 || !p->re_root)
1549 && !p->sync && (p->learn && !p->forward)) {
1550 p->port_role_transition_sm_state =
1551 PORT_ROLE_TRANSITION_SM_DESIGNATED_FORWARD_EXEC;
1552 } else if (!p->forward && !p->agreed && !p->proposing &&
1554 p->port_role_transition_sm_state =
1555 PORT_ROLE_TRANSITION_SM_DESIGNATED_PROPOSE_EXEC;
1556 } else if ((!p->learning && !p->forwarding && !p->synced)
1557 || (p->agreed && !p->synced)
1558 || (p->oper_edge && !p->synced)
1559 || (p->sync && p->synced)) {
1560 p->port_role_transition_sm_state =
1561 PORT_ROLE_TRANSITION_SM_DESIGNATED_SYNCED_EXEC;
1562 } else if (p->rr_while == 0 && p->re_root) {
1563 p->port_role_transition_sm_state =
1564 PORT_ROLE_TRANSITION_SM_DESIGNATED_RETIRED_EXEC;
1568 case PORT_ROLE_TRANSITION_SM_DESIGNATED_RETIRED_EXEC:
1570 p->port_role_transition_sm_state =
1571 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1573 case PORT_ROLE_TRANSITION_SM_DESIGNATED_SYNCED_EXEC:
1577 p->port_role_transition_sm_state =
1578 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1580 case PORT_ROLE_TRANSITION_SM_DESIGNATED_PROPOSE_EXEC:
1581 p->proposing = true;
1582 p->edge_delay_while = edge_delay(p);
1584 p->port_role_transition_sm_state =
1585 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1587 case PORT_ROLE_TRANSITION_SM_DESIGNATED_FORWARD_EXEC:
1590 p->agreed = p->send_rstp;
1591 p->port_role_transition_sm_state =
1592 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1594 case PORT_ROLE_TRANSITION_SM_DESIGNATED_LEARN_EXEC:
1596 p->fd_while = forward_delay(p);
1597 p->port_role_transition_sm_state =
1598 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1600 case PORT_ROLE_TRANSITION_SM_DESIGNATED_DISCARD_EXEC:
1601 p->learn = p->forward = p->disputed = false;
1602 p->fd_while = forward_delay(p);
1603 p->port_role_transition_sm_state =
1604 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1606 case PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC:
1607 p->fd_while = p->designated_times.forward_delay;
1610 p->sync = p->re_root = false;
1611 p->port_role_transition_sm_state =
1612 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT;
1614 case PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT:
1615 if (check_selected_role_change(p, ROLE_ALTERNATE)) {
1617 } else if (p->selected && !p->updt_info) {
1618 if (p->rb_while != 2 * p->designated_times.hello_time
1619 && p->role == ROLE_BACKUP) {
1620 p->port_role_transition_sm_state =
1621 PORT_ROLE_TRANSITION_SM_BACKUP_PORT_EXEC;
1622 } else if ((p->fd_while != forward_delay(p)) || p->sync
1623 || p->re_root || !p->synced) {
1624 p->port_role_transition_sm_state =
1625 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1626 } else if (p->proposed && !p->agree) {
1627 p->port_role_transition_sm_state =
1628 PORT_ROLE_TRANSITION_SM_ALTERNATE_PROPOSED_EXEC;
1629 } else if ((all_synced(r) && !p->agree)
1630 || (p->proposed && p->agree)) {
1631 p->port_role_transition_sm_state =
1632 PORT_ROLE_TRANSITION_SM_ALTERNATE_AGREED;
1636 case PORT_ROLE_TRANSITION_SM_ALTERNATE_AGREED:
1637 p->proposed = false;
1640 p->port_role_transition_sm_state =
1641 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1643 case PORT_ROLE_TRANSITION_SM_ALTERNATE_PROPOSED_EXEC:
1645 p->proposed = false;
1646 p->port_role_transition_sm_state =
1647 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1649 case PORT_ROLE_TRANSITION_SM_BLOCK_PORT_EXEC:
1650 p->role = p->selected_role;
1651 p->learn = p->forward = false;
1652 p->port_role_transition_sm_state = PORT_ROLE_TRANSITION_SM_BLOCK_PORT;
1654 case PORT_ROLE_TRANSITION_SM_BLOCK_PORT:
1655 if (check_selected_role_change(p, ROLE_ALTERNATE)) {
1657 } else if (p->selected && !p->updt_info && !p->learning &&
1659 p->port_role_transition_sm_state =
1660 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1663 case PORT_ROLE_TRANSITION_SM_BACKUP_PORT_EXEC:
1664 p->rb_while = 2 * p->designated_times.hello_time;
1665 p->port_role_transition_sm_state =
1666 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1672 if (old_state != p->port_role_transition_sm_state) {
1674 VLOG_DBG("%s, port %u: Port_role_transition_sm %d -> %d",
1675 p->rstp->name, p->port_number, old_state,
1676 p->port_role_transition_sm_state);
1678 if (last_role != p->role) {
1679 last_role = p->role;
1680 VLOG_DBG("%s, port %u, port role ["RSTP_PORT_ID_FMT"] = %s",
1681 p->rstp->name, p->port_number, p->port_id,
1682 rstp_port_role_name(p->role));
1687 /* [17.30 - Port state transition state machine] */
1690 enable_learning(struct rstp_port *p)
1691 OVS_REQUIRES(rstp_mutex)
1693 /* [17.21.6 enableLearning()] An implementation dependent procedure that
1694 * causes the Learning Process (7.8) to start learning from frames received
1695 * on the Port. The procedure does not complete until learning has been
1698 rstp_port_set_state__(p, RSTP_LEARNING);
1702 enable_forwarding(struct rstp_port *p)
1703 OVS_REQUIRES(rstp_mutex)
1705 /* [17.21.5 enableForwarding()] An implementation dependent procedure that
1706 * causes the Forwarding Process (7.7) to start forwarding frames through
1707 * the Port. The procedure does not complete until forwarding has been
1710 rstp_port_set_state__(p, RSTP_FORWARDING);
1714 disable_learning(struct rstp_port *p)
1715 OVS_REQUIRES(rstp_mutex)
1717 /* [17.21.4 - disableLearning()] An implementation dependent procedure that
1718 * causes the Learning Process (7.8) to stop learning from the source
1719 * address of frames received on the Port. The procedure does not complete
1720 * until learning has stopped.
1722 rstp_port_set_state__(p, RSTP_DISCARDING);
1726 disable_forwarding(struct rstp_port *p)
1727 OVS_REQUIRES(rstp_mutex)
1729 /* [17.21.3 - disableForwarding()] An implementation dependent procedure
1730 * that causes the Forwarding Process (7.7) to stop forwarding frames
1731 * through the Port. The procedure does not complete until forwarding has
1734 rstp_port_set_state__(p, RSTP_DISCARDING);
1738 port_state_transition_sm(struct rstp_port *p)
1739 OVS_REQUIRES(rstp_mutex)
1741 enum port_state_transition_state_machine old_state;
1744 old_state = p->port_state_transition_sm_state;
1747 switch (p->port_state_transition_sm_state) {
1748 case PORT_STATE_TRANSITION_SM_INIT:
1750 p->port_state_transition_sm_state =
1751 PORT_STATE_TRANSITION_SM_DISCARDING_EXEC;
1754 case PORT_STATE_TRANSITION_SM_DISCARDING_EXEC:
1755 disable_learning(p);
1756 p->learning = false;
1757 disable_forwarding(p);
1758 p->forwarding = false;
1759 p->port_state_transition_sm_state =
1760 PORT_STATE_TRANSITION_SM_DISCARDING;
1762 case PORT_STATE_TRANSITION_SM_DISCARDING:
1764 p->port_state_transition_sm_state =
1765 PORT_STATE_TRANSITION_SM_LEARNING_EXEC;
1768 case PORT_STATE_TRANSITION_SM_LEARNING_EXEC:
1771 p->port_state_transition_sm_state = PORT_STATE_TRANSITION_SM_LEARNING;
1773 case PORT_STATE_TRANSITION_SM_LEARNING:
1775 p->port_state_transition_sm_state =
1776 PORT_STATE_TRANSITION_SM_DISCARDING_EXEC;
1777 } else if (p->forward) {
1778 p->port_state_transition_sm_state =
1779 PORT_STATE_TRANSITION_SM_FORWARDING_EXEC;
1782 case PORT_STATE_TRANSITION_SM_FORWARDING_EXEC:
1783 enable_forwarding(p);
1784 p->forwarding = true;
1785 p->port_state_transition_sm_state =
1786 PORT_STATE_TRANSITION_SM_FORWARDING;
1788 case PORT_STATE_TRANSITION_SM_FORWARDING:
1790 p->port_state_transition_sm_state =
1791 PORT_STATE_TRANSITION_SM_DISCARDING_EXEC;
1798 if (old_state != p->port_state_transition_sm_state) {
1800 VLOG_DBG("%s, port %u: Port_state_transition_sm %d -> %d",
1801 p->rstp->name, p->port_number, old_state,
1802 p->port_state_transition_sm_state);
1807 /* [17.31 - Topology Change state machine] */
1810 new_tc_while(struct rstp_port *p)
1811 OVS_REQUIRES(rstp_mutex)
1816 if (p->tc_while == 0 && p->send_rstp == true) {
1817 p->tc_while = r->bridge_hello_time + 1;
1819 } else if (p->tc_while == 0 && p->send_rstp == false) {
1820 p->tc_while = r->bridge_max_age + r->bridge_forward_delay;
1824 /* [17.21.18 setTcPropTree()]
1825 * Sets tcprop for all Ports except the Port that called the procedure.
1828 set_tc_prop_tree(struct rstp_port *p)
1829 OVS_REQUIRES(rstp_mutex)
1832 struct rstp_port *p1;
1835 HMAP_FOR_EACH (p1, node, &r->ports) {
1836 /* Set tc_prop on every port, except the one calling this
1838 if (p1->port_number != p->port_number) {
1845 set_tc_prop_bridge(struct rstp_port *p) /* not specified in 802.1D-2004. */
1846 OVS_REQUIRES(rstp_mutex)
1848 set_tc_prop_tree(p); /* see 802.1w-2001. */
1852 topology_change_sm(struct rstp_port *p)
1853 OVS_REQUIRES(rstp_mutex)
1855 enum topology_change_state_machine old_state;
1858 old_state = p->topology_change_sm_state;
1861 switch (p->topology_change_sm_state) {
1862 case TOPOLOGY_CHANGE_SM_INIT:
1864 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_INACTIVE_EXEC;
1867 case TOPOLOGY_CHANGE_SM_INACTIVE_EXEC:
1868 p->fdb_flush = true;
1871 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_INACTIVE;
1873 case TOPOLOGY_CHANGE_SM_INACTIVE:
1874 if (p->learn && !p->fdb_flush) {
1875 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING_EXEC;
1878 case TOPOLOGY_CHANGE_SM_LEARNING_EXEC:
1879 p->rcvd_tc = p->rcvd_tcn = p->rcvd_tc_ack = false;
1880 p->tc_prop = p->rcvd_tc_ack = false;
1881 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING;
1883 case TOPOLOGY_CHANGE_SM_LEARNING:
1884 if (p->role != ROLE_ROOT && p->role != ROLE_DESIGNATED &&
1885 !(p->learn || p->learning) && !(p->rcvd_tc || p->rcvd_tcn ||
1886 p->rcvd_tc_ack || p->tc_prop)) {
1887 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_INACTIVE_EXEC;
1888 } else if (p->rcvd_tc || p->rcvd_tcn || p->rcvd_tc_ack || p->tc_prop) {
1889 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING_EXEC;
1890 } else if ((p->role == ROLE_ROOT || p->role == ROLE_DESIGNATED)
1891 && p->forward && !p->oper_edge) {
1892 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_DETECTED_EXEC;
1895 case TOPOLOGY_CHANGE_SM_DETECTED_EXEC:
1897 set_tc_prop_tree(p);
1899 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE_EXEC;
1901 case TOPOLOGY_CHANGE_SM_ACTIVE_EXEC:
1902 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
1904 case TOPOLOGY_CHANGE_SM_ACTIVE:
1905 if ((p->role != ROLE_ROOT && p->role != ROLE_DESIGNATED)
1907 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING_EXEC;
1908 } else if (p->rcvd_tcn) {
1909 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_NOTIFIED_TCN_EXEC;
1910 } else if (p->rcvd_tc) {
1911 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_NOTIFIED_TC_EXEC;
1912 } else if (p->tc_prop && !p->oper_edge) {
1913 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_PROPAGATING_EXEC;
1914 } else if (p->rcvd_tc_ack) {
1915 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACKNOWLEDGED_EXEC;
1918 case TOPOLOGY_CHANGE_SM_ACKNOWLEDGED_EXEC:
1920 p->rcvd_tc_ack = false;
1921 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
1923 case TOPOLOGY_CHANGE_SM_PROPAGATING_EXEC:
1925 p->fdb_flush = true;
1927 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
1929 case TOPOLOGY_CHANGE_SM_NOTIFIED_TC_EXEC:
1930 p->rcvd_tcn = p->rcvd_tc = false;
1931 if (p->role == ROLE_DESIGNATED) {
1934 set_tc_prop_bridge(p);
1935 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
1937 case TOPOLOGY_CHANGE_SM_NOTIFIED_TCN_EXEC:
1939 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
1945 if (old_state != p->topology_change_sm_state) {
1947 VLOG_DBG("%s, port %u: Topology_change_sm %d -> %d", p->rstp->name,
1948 p->port_number, old_state, p->topology_change_sm_state);
1953 /****************************************************************************
1954 * [17.6] Priority vector calculation helper functions
1955 ****************************************************************************/
1957 /* compare_rstp_priority_vectors() compares two struct rstp_priority_vectors
1958 * and returns a value indicating if the first rstp_priority_vector is
1959 * superior, same or inferior to the second one.
1961 * Zero return value indicates INFERIOR, a non-zero return value indicates
1962 * SUPERIOR. When it makes a difference the non-zero return value SAME
1963 * indicates the priority vectors are identical (a subset of SUPERIOR).
1965 static enum vector_comparison
1966 compare_rstp_priority_vectors(const struct rstp_priority_vector *v1,
1967 const struct rstp_priority_vector *v2)
1969 VLOG_DBG("v1: "RSTP_ID_FMT", %u, "RSTP_ID_FMT", %d",
1970 RSTP_ID_ARGS(v1->root_bridge_id), v1->root_path_cost,
1971 RSTP_ID_ARGS(v1->designated_bridge_id), v1->designated_port_id);
1972 VLOG_DBG("v2: "RSTP_ID_FMT", %u, "RSTP_ID_FMT", %d",
1973 RSTP_ID_ARGS(v2->root_bridge_id), v2->root_path_cost,
1974 RSTP_ID_ARGS(v2->designated_bridge_id), v2->designated_port_id);
1977 * This message priority vector is superior to the port priority vector and
1978 * will replace it if, and only if, the message priority vector is better
1979 * than the port priority vector, or the message has been transmitted from
1980 * the same Designated Bridge and Designated Port as the port priority
1981 * vector, i.e., if the following is true:
1983 * ((RD < RootBridgeID)) ||
1984 * ((RD == RootBridgeID) && (RPCD < RootPathCost)) ||
1985 * ((RD == RootBridgeID) && (RPCD == RootPathCost) &&
1986 * (D < designated_bridge_id)) ||
1987 * ((RD == RootBridgeID) && (RPCD == RootPathCost) &&
1988 * (D == designated_bridge_id) && (PD < designated_port_id)) ||
1989 * ((D == designated_bridge_id.BridgeAddress) &&
1990 * (PD == designated_port_id.PortNumber))
1992 if ((v1->root_bridge_id < v2->root_bridge_id)
1993 || (v1->root_bridge_id == v2->root_bridge_id
1994 && v1->root_path_cost < v2->root_path_cost)
1995 || (v1->root_bridge_id == v2->root_bridge_id
1996 && v1->root_path_cost == v2->root_path_cost
1997 && v1->designated_bridge_id < v2->designated_bridge_id)
1998 || (v1->root_bridge_id == v2->root_bridge_id
1999 && v1->root_path_cost == v2->root_path_cost
2000 && v1->designated_bridge_id == v2->designated_bridge_id
2001 && v1->designated_port_id < v2->designated_port_id)
2002 || (v1->designated_bridge_id == v2->designated_bridge_id
2003 && v1->designated_port_id == v2->designated_port_id)) {
2004 /* SAME is a subset of SUPERIOR. */
2005 if (v1->root_bridge_id == v2->root_bridge_id
2006 && v1->root_path_cost == v2->root_path_cost
2007 && v1->designated_bridge_id == v2->designated_bridge_id
2008 && v1->designated_port_id == v2->designated_port_id) {
2009 VLOG_DBG("superior_same");
2012 VLOG_DBG("superior");
2016 VLOG_DBG("inferior");
2021 rstp_times_equal(struct rstp_times *t1, struct rstp_times *t2)
2023 return t1->forward_delay == t2->forward_delay
2024 && t1->hello_time == t2->hello_time
2025 && t1->max_age == t2->max_age
2026 && t1->message_age == t2->message_age;