2 * Copyright (c) 2011-2015 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>
24 * Carlo Andreotti <c.andreotti@m3s.it>
26 * References to IEEE 802.1D-2004 standard are enclosed in square brackets.
27 * E.g. [17.3], [Table 17-1], etc.
33 #include "rstp-state-machines.h"
34 #include <arpa/inet.h>
36 #include <netinet/in.h>
38 #include <sys/types.h>
39 #include "byte-order.h"
40 #include "connectivity.h"
42 #include "dp-packet.h"
47 #include "openvswitch/vlog.h"
49 VLOG_DEFINE_THIS_MODULE(rstp_sm);
51 #define ROLE_FLAG_MASK 0xC
52 #define ROLE_FLAG_SHIFT 2
62 CONFIGURATION_BPDU_SIZE = 35,
63 TOPOLOGY_CHANGE_NOTIFICATION_BPDU_SIZE = 4,
64 RAPID_SPANNING_TREE_BPDU_SIZE = 36
67 /* Same is a subset of SUPERIOR, so can be used as a boolean when the
68 * distinction is not significant. */
69 enum vector_comparison {
75 static void decrement_timer(uint16_t *);
76 static void rstp_send_bpdu(struct rstp_port *, const void *, size_t)
77 OVS_REQUIRES(rstp_mutex);
78 static int validate_received_bpdu(struct rstp_port *, const void *, size_t)
79 OVS_REQUIRES(rstp_mutex);
80 static ovs_be16 time_encode(uint8_t);
81 static uint8_t time_decode(ovs_be16);
82 static enum vector_comparison
83 compare_rstp_priority_vectors(const struct rstp_priority_vector *,
84 const struct rstp_priority_vector *);
85 static bool rstp_times_equal(struct rstp_times *, struct rstp_times *);
87 /* Per-Bridge State Machine */
88 static int port_role_selection_sm(struct rstp *)
89 OVS_REQUIRES(rstp_mutex);
90 /* Per-Port State Machines */
91 static int port_receive_sm(struct rstp_port *)
92 OVS_REQUIRES(rstp_mutex);
93 static int port_protocol_migration_sm(struct rstp_port *)
94 OVS_REQUIRES(rstp_mutex);
95 static int bridge_detection_sm(struct rstp_port *)
96 OVS_REQUIRES(rstp_mutex);
97 static int port_transmit_sm(struct rstp_port *)
98 OVS_REQUIRES(rstp_mutex);
99 static int port_information_sm(struct rstp_port *)
100 OVS_REQUIRES(rstp_mutex);
101 static int port_role_transition_sm(struct rstp_port *)
102 OVS_REQUIRES(rstp_mutex);
103 static int port_state_transition_sm(struct rstp_port *)
104 OVS_REQUIRES(rstp_mutex);
105 static int topology_change_sm(struct rstp_port *)
106 OVS_REQUIRES(rstp_mutex);
107 /* port_timers_sm() not defined as a state machine */
110 process_received_bpdu__(struct rstp_port *p, const void *bpdu_,
112 OVS_REQUIRES(rstp_mutex)
114 struct rstp *rstp = p->rstp;
115 struct rstp_bpdu *bpdu = (struct rstp_bpdu *)bpdu_;
117 if (!p->port_enabled) {
124 /* [9.2.9 Encoding of Port Role values]
125 * NOTE. If the Unknown value of the Port Role parameter is received, the
126 * state machines will effectively treat the RST BPDU as if it were a
127 * Configuration BPDU.
129 if (bpdu->bpdu_type == RAPID_SPANNING_TREE_BPDU) {
130 uint8_t role = (bpdu->flags & ROLE_FLAG_MASK) >> ROLE_FLAG_SHIFT;
132 if (role == PORT_UNKN) {
133 bpdu->bpdu_type = CONFIGURATION_BPDU;
137 if (validate_received_bpdu(p, bpdu, bpdu_size) == 0) {
139 p->rx_rstp_bpdu_cnt++;
141 memcpy(&p->received_bpdu_buffer, bpdu, sizeof(struct rstp_bpdu));
143 rstp->changes = true;
146 VLOG_DBG("%s, port %u: Bad STP or RSTP BPDU received", p->rstp->name,
152 /* Returns 0 on success. */
154 validate_received_bpdu(struct rstp_port *p, const void *bpdu, size_t bpdu_size)
155 OVS_REQUIRES(rstp_mutex)
157 /* Validation of received BPDU, see [9.3.4]. */
158 const struct rstp_bpdu *temp;
161 if (bpdu_size < TOPOLOGY_CHANGE_NOTIFICATION_BPDU_SIZE ||
162 ntohs(temp->protocol_identifier) != 0) {
165 if (temp->bpdu_type == CONFIGURATION_BPDU
166 && bpdu_size >= CONFIGURATION_BPDU_SIZE
167 && (time_decode(temp->message_age) < time_decode(temp->max_age))) {
168 if ((ntohll(temp->designated_bridge_id) !=
169 p->rstp->bridge_identifier)
170 || ((ntohll(temp->designated_bridge_id) ==
171 p->rstp->bridge_identifier)
172 && (ntohs(temp->designated_port_id) != p->port_id))) {
177 } else if (temp->bpdu_type == TOPOLOGY_CHANGE_NOTIFICATION_BPDU) {
179 } else if (temp->bpdu_type == RAPID_SPANNING_TREE_BPDU &&
180 bpdu_size >= RAPID_SPANNING_TREE_BPDU_SIZE) {
190 * This method is invoked to move the State Machines. The SMs move only if the
191 * boolean 'changes' is true, meaning that something changed and the SMs need
192 * to work to process this change.
193 * The boolean 'changes' is set every time a SM modifies its state, a BPDU is
194 * received, a timer expires or port down event is detected. If a parameter is
195 * set by management, then 'changes' is set.
197 #define MAX_RSTP_ITERATIONS 1000 /* safeguard */
199 move_rstp__(struct rstp *rstp)
200 OVS_REQUIRES(rstp_mutex)
205 while (rstp->changes == true && num_iterations < MAX_RSTP_ITERATIONS) {
208 VLOG_DBG("%s: move_rstp()", rstp->name);
210 rstp->changes = false;
211 port_role_selection_sm(rstp);
212 HMAP_FOR_EACH (p, node, &rstp->ports) {
213 if (p->rstp_state != RSTP_DISABLED) {
215 bridge_detection_sm(p);
216 port_information_sm(p);
217 port_role_transition_sm(p);
218 port_state_transition_sm(p);
219 topology_change_sm(p);
221 port_protocol_migration_sm(p);
225 seq_change(connectivity_seq_get());
227 if (num_iterations >= MAX_RSTP_ITERATIONS) {
228 VLOG_ERR("%s: move_rstp() reached the iteration safeguard limit!",
234 void decrease_rstp_port_timers__(struct rstp *r)
235 OVS_REQUIRES(rstp_mutex)
239 HMAP_FOR_EACH (p, node, &r->ports) {
240 decrement_timer(&p->hello_when);
241 decrement_timer(&p->tc_while);
242 decrement_timer(&p->fd_while);
243 decrement_timer(&p->rcvd_info_while);
244 decrement_timer(&p->rr_while);
245 decrement_timer(&p->rb_while);
246 decrement_timer(&p->mdelay_while);
247 decrement_timer(&p->edge_delay_while);
248 decrement_timer(&p->tx_count);
256 decrement_timer(uint16_t *timer)
263 /* Bridge State Machine. */
264 /* [17.28] Port Role Selection state machine. */
267 updt_role_disabled_tree(struct rstp *r)
268 OVS_REQUIRES(rstp_mutex)
272 HMAP_FOR_EACH (p, node, &r->ports) {
273 p->selected_role = ROLE_DISABLED;
278 clear_reselect_tree(struct rstp *r)
279 OVS_REQUIRES(rstp_mutex)
283 HMAP_FOR_EACH (p, node, &r->ports) {
289 updt_roles_tree__(struct rstp *r)
290 OVS_REQUIRES(rstp_mutex)
294 struct rstp_priority_vector best_vector, candidate_vector;
295 enum rstp_port_role new_root_old_role = ROLE_DESIGNATED;
296 uint16_t old_root_port_number = 0;
297 uint16_t new_root_port_number = 0;
299 old_root_port_number = r->root_port_id & 0x00ff;
300 if (old_root_port_number) {
301 r->old_root_aux = rstp_get_port_aux__(r, old_root_port_number);
304 best_vector = r->bridge_priority;
306 r->root_times = r->bridge_times;
307 /* Letters a) b) c) */
308 HMAP_FOR_EACH (p, node, &r->ports) {
309 uint32_t old_root_path_cost;
310 uint32_t root_path_cost;
312 if (p->info_is != INFO_IS_RECEIVED) {
316 candidate_vector = p->port_priority;
317 candidate_vector.bridge_port_id = p->port_id;
318 old_root_path_cost = candidate_vector.root_path_cost;
319 root_path_cost = old_root_path_cost + p->port_path_cost;
320 candidate_vector.root_path_cost = root_path_cost;
322 if ((candidate_vector.designated_bridge_id & 0xffffffffffffULL) ==
323 (r->bridge_priority.designated_bridge_id & 0xffffffffffffULL)) {
326 if (compare_rstp_priority_vectors(&candidate_vector,
327 &best_vector) == SUPERIOR) {
328 best_vector = candidate_vector;
329 r->root_times = p->port_times;
330 r->root_times.message_age++;
331 vsel = p->port_number;
332 new_root_old_role = p->role;
335 r->root_priority = best_vector;
336 r->root_port_id = best_vector.bridge_port_id;
337 VLOG_DBG("%s: new Root is "RSTP_ID_FMT, r->name,
338 RSTP_ID_ARGS(r->root_priority.root_bridge_id));
339 new_root_port_number = r->root_port_id & 0x00ff;
340 if (new_root_port_number) {
341 r->new_root_aux = rstp_get_port_aux__(r, new_root_port_number);
343 /* Shift learned MAC addresses from an old Root Port to an existing
346 && new_root_old_role == ROLE_ALTERNATE
347 && new_root_port_number
348 && old_root_port_number
349 && new_root_port_number != old_root_port_number) {
350 r->root_changed = true;
353 HMAP_FOR_EACH (p, node, &r->ports) {
354 p->designated_priority_vector.root_bridge_id =
355 r->root_priority.root_bridge_id;
356 p->designated_priority_vector.root_path_cost =
357 r->root_priority.root_path_cost;
358 p->designated_priority_vector.designated_bridge_id =
359 r->bridge_identifier;
360 p->designated_priority_vector.designated_port_id =
362 p->designated_times = r->root_times;
363 p->designated_times.hello_time = r->bridge_times.hello_time;
365 HMAP_FOR_EACH (p, node, &r->ports) {
366 switch (p->info_is) {
367 case INFO_IS_DISABLED:
368 p->selected_role = ROLE_DISABLED;
372 p->selected_role = ROLE_DESIGNATED;
375 p->selected_role = ROLE_DESIGNATED;
376 if (compare_rstp_priority_vectors(
377 &p->port_priority, &p->designated_priority_vector) != SAME
378 || !rstp_times_equal(&p->designated_times, &r->root_times)) {
382 case INFO_IS_RECEIVED:
383 if (vsel == p->port_number) { /* Letter i) */
384 p->selected_role = ROLE_ROOT;
385 p->updt_info = false;
386 } else if (compare_rstp_priority_vectors(
387 &p->designated_priority_vector,
388 &p->port_priority) == INFERIOR) {
389 if (p->port_priority.designated_bridge_id !=
390 r->bridge_identifier) {
391 p->selected_role = ROLE_ALTERNATE;
392 p->updt_info = false;
394 p->selected_role = ROLE_BACKUP;
395 p->updt_info = false;
398 p->selected_role = ROLE_DESIGNATED;
407 seq_change(connectivity_seq_get());
411 set_selected_tree(struct rstp *r)
412 OVS_REQUIRES(rstp_mutex)
416 HMAP_FOR_EACH (p, node, &r->ports) {
421 HMAP_FOR_EACH (p, node, &r->ports) {
427 port_role_selection_sm(struct rstp *r)
428 OVS_REQUIRES(rstp_mutex)
430 enum port_role_selection_state_machine old_state;
433 old_state = r->port_role_selection_sm_state;
435 switch (r->port_role_selection_sm_state) {
436 case PORT_ROLE_SELECTION_SM_INIT:
438 r->port_role_selection_sm_state =
439 PORT_ROLE_SELECTION_SM_INIT_BRIDGE_EXEC;
442 case PORT_ROLE_SELECTION_SM_INIT_BRIDGE_EXEC:
443 updt_role_disabled_tree(r);
444 r->port_role_selection_sm_state = PORT_ROLE_SELECTION_SM_INIT_BRIDGE;
446 case PORT_ROLE_SELECTION_SM_INIT_BRIDGE:
447 r->port_role_selection_sm_state =
448 PORT_ROLE_SELECTION_SM_ROLE_SELECTION_EXEC;
450 case PORT_ROLE_SELECTION_SM_ROLE_SELECTION_EXEC:
451 clear_reselect_tree(r);
452 updt_roles_tree__(r);
453 set_selected_tree(r);
454 r->port_role_selection_sm_state =
455 PORT_ROLE_SELECTION_SM_ROLE_SELECTION;
457 case PORT_ROLE_SELECTION_SM_ROLE_SELECTION:
458 HMAP_FOR_EACH (p, node, &r->ports) {
460 r->port_role_selection_sm_state =
461 PORT_ROLE_SELECTION_SM_ROLE_SELECTION_EXEC;
470 if (old_state != r->port_role_selection_sm_state) {
472 VLOG_DBG("%s: Port_role_selection_sm %d -> %d", r->name,
473 old_state, r->port_role_selection_sm_state);
478 /* Port State Machines */
480 /* [17.23 - Port receive state machine] */
483 updt_bpdu_version(struct rstp_port *p) /* [17.21.22] */
484 OVS_REQUIRES(rstp_mutex)
486 switch (p->received_bpdu_buffer.bpdu_type) {
487 case CONFIGURATION_BPDU:
488 case TOPOLOGY_CHANGE_NOTIFICATION_BPDU:
489 p->rcvd_rstp = false;
492 case RAPID_SPANNING_TREE_BPDU:
503 port_receive_sm(struct rstp_port *p)
504 OVS_REQUIRES(rstp_mutex)
506 enum port_receive_state_machine old_state;
509 old_state = p->port_receive_sm_state;
512 switch (p->port_receive_sm_state) {
513 case PORT_RECEIVE_SM_INIT:
514 if (r->begin || ((p->rcvd_bpdu || (p->edge_delay_while !=
515 r->migrate_time)) && !p->port_enabled)) {
516 p->port_receive_sm_state = PORT_RECEIVE_SM_DISCARD_EXEC;
519 case PORT_RECEIVE_SM_DISCARD_EXEC:
520 p->rcvd_bpdu = p->rcvd_rstp = p->rcvd_stp = false;
522 p->edge_delay_while = r->migrate_time;
523 p->port_receive_sm_state = PORT_RECEIVE_SM_DISCARD;
525 case PORT_RECEIVE_SM_DISCARD:
526 if ((p->rcvd_bpdu || (p->edge_delay_while != r->migrate_time))
527 && !p->port_enabled) {
528 /* Global transition. */
529 p->port_receive_sm_state = PORT_RECEIVE_SM_DISCARD_EXEC;
530 } else if (p->rcvd_bpdu && p->port_enabled) {
531 p->port_receive_sm_state = PORT_RECEIVE_SM_RECEIVE_EXEC;
534 case PORT_RECEIVE_SM_RECEIVE_EXEC:
535 updt_bpdu_version(p);
536 p->oper_edge = p->rcvd_bpdu = false;
538 p->edge_delay_while = r->migrate_time;
539 p->port_receive_sm_state = PORT_RECEIVE_SM_RECEIVE;
541 case PORT_RECEIVE_SM_RECEIVE:
542 if ((p->rcvd_bpdu || (p->edge_delay_while != r->migrate_time))
543 && !p->port_enabled) {
544 /* Global transition. */
545 p->port_receive_sm_state = PORT_RECEIVE_SM_DISCARD_EXEC;
546 } else if (p->rcvd_bpdu && p->port_enabled && !p->rcvd_msg) {
547 p->port_receive_sm_state = PORT_RECEIVE_SM_RECEIVE_EXEC;
554 if (old_state != p->port_receive_sm_state) {
556 VLOG_DBG("%s, port %u: Port_receive_sm %d -> %d", p->rstp->name,
557 p->port_number, old_state, p->port_receive_sm_state);
562 /* [17.24 - Port Protocol Migration state machine] */
564 port_protocol_migration_sm(struct rstp_port *p)
565 OVS_REQUIRES(rstp_mutex)
567 enum port_protocol_migration_state_machine old_state;
570 old_state = p->port_protocol_migration_sm_state;
573 switch (p->port_protocol_migration_sm_state) {
574 case PORT_PROTOCOL_MIGRATION_SM_INIT:
575 p->port_protocol_migration_sm_state =
576 PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP_EXEC;
578 case PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP_EXEC:
580 p->send_rstp = r->rstp_version;
581 p->mdelay_while = r->migrate_time;
582 p->port_protocol_migration_sm_state =
583 PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP;
585 case PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP:
586 if (p->mdelay_while == 0) {
587 p->port_protocol_migration_sm_state =
588 PORT_PROTOCOL_MIGRATION_SM_SENSING_EXEC;
589 } else if ((p->mdelay_while != r->migrate_time) && !p->port_enabled) {
590 p->port_protocol_migration_sm_state =
591 PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP_EXEC;
594 case PORT_PROTOCOL_MIGRATION_SM_SELECTING_STP_EXEC:
595 p->send_rstp = false;
596 p->mdelay_while = r->migrate_time;
597 p->port_protocol_migration_sm_state =
598 PORT_PROTOCOL_MIGRATION_SM_SELECTING_STP;
600 case PORT_PROTOCOL_MIGRATION_SM_SELECTING_STP:
601 if ((p->mdelay_while == 0) || (!p->port_enabled) || p->mcheck) {
602 p->port_protocol_migration_sm_state =
603 PORT_PROTOCOL_MIGRATION_SM_SENSING_EXEC;
606 case PORT_PROTOCOL_MIGRATION_SM_SENSING_EXEC:
607 p->rcvd_rstp = false;
609 p->port_protocol_migration_sm_state =
610 PORT_PROTOCOL_MIGRATION_SM_SENSING;
612 case PORT_PROTOCOL_MIGRATION_SM_SENSING:
613 if (!p->port_enabled || p->mcheck || ((r->rstp_version) &&
614 !p->send_rstp && p->rcvd_rstp)) {
615 p->port_protocol_migration_sm_state =
616 PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP_EXEC;
617 } else if (p->send_rstp && p->rcvd_stp) {
618 p->port_protocol_migration_sm_state =
619 PORT_PROTOCOL_MIGRATION_SM_SELECTING_STP_EXEC;
626 if (old_state != p->port_protocol_migration_sm_state) {
628 VLOG_DBG("%s, port %u: port_protocol_migration_sm %d -> %d",
629 p->rstp->name, p->port_number, old_state,
630 p->port_protocol_migration_sm_state);
636 /* [17.25 - Bridge Detection state machine] */
638 bridge_detection_sm(struct rstp_port *p)
639 OVS_REQUIRES(rstp_mutex)
641 enum bridge_detection_state_machine old_state;
644 old_state = p->bridge_detection_sm_state;
647 switch (p->bridge_detection_sm_state) {
648 case BRIDGE_DETECTION_SM_INIT:
649 if (r->begin && p->admin_edge) {
650 p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_EDGE_EXEC;
651 } else if (r->begin && !p->admin_edge) {
652 p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_NOT_EDGE_EXEC;
655 case BRIDGE_DETECTION_SM_EDGE_EXEC:
657 p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_EDGE;
659 case BRIDGE_DETECTION_SM_EDGE:
660 if ((!p->port_enabled && !p->admin_edge) || !p->oper_edge) {
661 p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_NOT_EDGE_EXEC;
664 case BRIDGE_DETECTION_SM_NOT_EDGE_EXEC:
665 p->oper_edge = false;
666 p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_NOT_EDGE;
668 case BRIDGE_DETECTION_SM_NOT_EDGE:
669 if ((!p->port_enabled && p->admin_edge)
670 || ((p->edge_delay_while == 0) && p->auto_edge && p->send_rstp
672 p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_EDGE_EXEC;
679 if (old_state != p->bridge_detection_sm_state) {
681 VLOG_DBG("%s, port %u: bridge_detection_sm %d -> %d", p->rstp->name,
682 p->port_number, old_state, p->bridge_detection_sm_state);
687 /* [17.26 - Port Transmit state machine] */
689 rstp_send_bpdu(struct rstp_port *p, const void *bpdu, size_t bpdu_size)
690 OVS_REQUIRES(rstp_mutex)
692 struct eth_header *eth;
693 struct llc_header *llc;
694 struct dp_packet *pkt;
697 pkt = dp_packet_new(ETH_HEADER_LEN + LLC_HEADER_LEN + bpdu_size);
698 eth = dp_packet_put_zeros(pkt, sizeof *eth);
699 llc = dp_packet_put_zeros(pkt, sizeof *llc);
700 dp_packet_reset_offsets(pkt);
701 dp_packet_set_l3(pkt, dp_packet_put(pkt, bpdu, bpdu_size));
704 eth->eth_dst = eth_addr_stp;
705 /* p->rstp->send_bpdu() must fill in source address. */
706 eth->eth_type = htons(dp_packet_size(pkt) - ETH_HEADER_LEN);
709 llc->llc_dsap = STP_LLC_DSAP;
710 llc->llc_ssap = STP_LLC_SSAP;
711 llc->llc_cntl = STP_LLC_CNTL;
712 p->rstp->send_bpdu(pkt, p->aux, p->rstp->aux);
716 record_agreement(struct rstp_port *p)
717 OVS_REQUIRES(rstp_mutex)
722 if (r->rstp_version && p->oper_point_to_point_mac &&
723 ((p->received_bpdu_buffer.flags & BPDU_FLAG_AGREEMENT))) {
725 p->proposing = false;
732 set_tc_flags(struct rstp_port *p)
733 OVS_REQUIRES(rstp_mutex)
735 /* Sets rcvd_tc and/or rcvd_tc_ack if the Topology Change and/or Topology
736 * Change Acknowledgment flags, respectively, are set in a ConfigBPDU or
739 if (p->received_bpdu_buffer.bpdu_type == CONFIGURATION_BPDU ||
740 p->received_bpdu_buffer.bpdu_type == RAPID_SPANNING_TREE_BPDU) {
741 if ((p->received_bpdu_buffer.flags & BPDU_FLAG_TOPCHANGE) != 0) {
744 if ((p->received_bpdu_buffer.flags & BPDU_FLAG_TOPCHANGEACK) != 0) {
745 p->rcvd_tc_ack = true;
748 /* Sets rcvd_tcn true if the BPDU is a TCN BPDU. */
749 if (p->received_bpdu_buffer.bpdu_type
750 == TOPOLOGY_CHANGE_NOTIFICATION_BPDU) {
756 record_dispute(struct rstp_port *p)
757 OVS_REQUIRES(rstp_mutex)
759 if ((p->received_bpdu_buffer.flags & BPDU_FLAG_LEARNING) != 0) {
760 /* 802.1D-2004 says to set the agreed flag and to clear the proposing
761 * flag. 802.1q-2008 instead says to set the disputed variable and to
762 * clear the agreed variable. */
769 record_proposal(struct rstp_port *p)
770 OVS_REQUIRES(rstp_mutex)
772 enum port_flag role =
773 ((p->received_bpdu_buffer.flags) & ROLE_FLAG_MASK) >> ROLE_FLAG_SHIFT;
775 if ((role == PORT_DES)
776 && ((p->received_bpdu_buffer.flags & BPDU_FLAG_PROPOSAL) != 0)) {
782 record_priority(struct rstp_port *p)
783 OVS_REQUIRES(rstp_mutex)
785 p->port_priority.root_bridge_id = p->msg_priority.root_bridge_id;
786 p->port_priority.root_path_cost = p->msg_priority.root_path_cost;
787 p->port_priority.designated_bridge_id =
788 p->msg_priority.designated_bridge_id;
789 p->port_priority.designated_port_id = p->msg_priority.designated_port_id;
793 record_times(struct rstp_port *p)
794 OVS_REQUIRES(rstp_mutex)
796 p->port_times = p->msg_times;
797 if (p->msg_times.hello_time == 0) {
798 p->port_times.hello_time = 1;
803 updt_rcvd_info_while(struct rstp_port *p)
804 OVS_REQUIRES(rstp_mutex)
807 * The value assigned to rcvdInfoWhile is the three times the Hello Time,
808 * if Message Age, incremented by 1 second and rounded to the nearest whole
809 * second, does not exceed Max Age, and is zero otherwise.
811 if (p->port_times.message_age < p->port_times.max_age) {
812 p->rcvd_info_while = p->port_times.hello_time * 3;
814 p->rcvd_info_while = 0;
818 /* Times are internally held in seconds, while the protocol uses 1/256 seconds.
819 * time_encode() is used to convert time values sent in bpdus, while
820 * time_decode() is used to convert time values received in bpdus.
823 time_encode(uint8_t value)
825 return htons(value * 256);
829 time_decode(ovs_be16 encoded)
831 return ntohs(encoded) / 256;
836 tx_config(struct rstp_port *p)
837 OVS_REQUIRES(rstp_mutex)
839 struct rstp_bpdu bpdu;
841 bpdu.protocol_identifier = htons(0);
842 bpdu.protocol_version_identifier = 0;
843 bpdu.bpdu_type = CONFIGURATION_BPDU;
844 bpdu.root_bridge_id = htonll(p->designated_priority_vector.root_bridge_id);
845 bpdu.root_path_cost = htonl(p->designated_priority_vector.root_path_cost);
846 bpdu.designated_bridge_id =
847 htonll(p->designated_priority_vector.designated_bridge_id);
848 bpdu.designated_port_id =
849 htons(p->designated_priority_vector.designated_port_id);
850 bpdu.message_age = time_encode(p->designated_times.message_age);
851 bpdu.max_age = time_encode(p->designated_times.max_age);
852 bpdu.hello_time = time_encode(p->designated_times.hello_time);
853 bpdu.forward_delay = time_encode(p->designated_times.forward_delay);
855 if (p->tc_while != 0) {
856 bpdu.flags |= BPDU_FLAG_TOPCHANGE;
858 if (p->tc_ack != 0) {
859 bpdu.flags |= BPDU_FLAG_TOPCHANGEACK;
861 rstp_send_bpdu(p, &bpdu, sizeof(struct rstp_bpdu));
866 tx_rstp(struct rstp_port *p)
867 OVS_REQUIRES(rstp_mutex)
869 struct rstp_bpdu bpdu;
871 bpdu.protocol_identifier = htons(0);
872 bpdu.protocol_version_identifier = 2;
873 bpdu.bpdu_type = RAPID_SPANNING_TREE_BPDU;
874 bpdu.root_bridge_id = htonll(p->designated_priority_vector.root_bridge_id);
875 bpdu.root_path_cost = htonl(p->designated_priority_vector.root_path_cost);
876 bpdu.designated_bridge_id =
877 htonll(p->designated_priority_vector.designated_bridge_id);
878 bpdu.designated_port_id =
879 htons(p->designated_priority_vector.designated_port_id);
880 bpdu.message_age = time_encode(p->designated_times.message_age);
881 bpdu.max_age = time_encode(p->designated_times.max_age);
882 bpdu.hello_time = time_encode(p->designated_times.hello_time);
883 bpdu.forward_delay = time_encode(p->designated_times.forward_delay);
888 bpdu.flags = PORT_ROOT << ROLE_FLAG_SHIFT;
890 case ROLE_DESIGNATED:
891 bpdu.flags = PORT_DES << ROLE_FLAG_SHIFT;
895 bpdu.flags = PORT_ALT_BACK << ROLE_FLAG_SHIFT;
898 /* Should not happen! */
899 VLOG_ERR("%s transmitting bpdu in disabled role on port "
900 RSTP_PORT_ID_FMT, p->rstp->name, p->port_id);
904 bpdu.flags |= BPDU_FLAG_AGREEMENT;
907 bpdu.flags |= BPDU_FLAG_PROPOSAL;
909 if (p->tc_while != 0) {
910 bpdu.flags |= BPDU_FLAG_TOPCHANGE;
913 bpdu.flags |= BPDU_FLAG_LEARNING;
916 bpdu.flags |= BPDU_FLAG_FORWARDING;
918 bpdu.version1_length = 0;
919 rstp_send_bpdu(p, &bpdu, sizeof(struct rstp_bpdu));
924 tx_tcn(struct rstp_port *p)
925 OVS_REQUIRES(rstp_mutex)
927 struct rstp_bpdu bpdu;
929 memset(&bpdu, 0, sizeof(struct rstp_bpdu));
931 bpdu.protocol_identifier = htons(0);
932 bpdu.protocol_version_identifier = 0;
933 bpdu.bpdu_type = TOPOLOGY_CHANGE_NOTIFICATION_BPDU;
934 rstp_send_bpdu(p, &bpdu, sizeof(struct rstp_bpdu));
938 port_transmit_sm(struct rstp_port *p)
939 OVS_REQUIRES(rstp_mutex)
941 enum port_transmit_state_machine old_state;
944 old_state = p->port_transmit_sm_state;
947 switch (p->port_transmit_sm_state) {
948 case PORT_TRANSMIT_SM_INIT:
950 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_INIT_EXEC;
953 case PORT_TRANSMIT_SM_TRANSMIT_INIT_EXEC:
956 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_INIT;
958 case PORT_TRANSMIT_SM_TRANSMIT_INIT:
959 p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
961 case PORT_TRANSMIT_SM_TRANSMIT_PERIODIC_EXEC:
962 p->new_info = p->new_info || (p->role == ROLE_DESIGNATED ||
963 (p->role == ROLE_ROOT && p->tc_while != 0));
964 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_PERIODIC;
966 case PORT_TRANSMIT_SM_TRANSMIT_PERIODIC:
967 p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
969 case PORT_TRANSMIT_SM_IDLE_EXEC:
970 p->hello_when = r->bridge_hello_time;
971 p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE;
973 case PORT_TRANSMIT_SM_IDLE:
974 if (p->role == ROLE_DISABLED) {
975 VLOG_DBG("%s, port %u: port_transmit_sm ROLE == DISABLED.",
976 p->rstp->name, p->port_number);
978 } else if (p->send_rstp && p->new_info
979 && p->tx_count < r->transmit_hold_count
980 && p->hello_when != 0 && p->selected && !p->updt_info) {
981 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_RSTP_EXEC;
982 } else if (p->hello_when == 0 && p->selected && !p->updt_info) {
983 p->port_transmit_sm_state =
984 PORT_TRANSMIT_SM_TRANSMIT_PERIODIC_EXEC;
985 } else if (!p->send_rstp && p->new_info && p->role == ROLE_ROOT
986 && p->tx_count < r->transmit_hold_count
987 && p->hello_when != 0 && p->selected && !p->updt_info) {
988 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_TCN_EXEC;
989 } else if (!p->send_rstp && p->new_info && p->role == ROLE_DESIGNATED
990 && p->tx_count < r->transmit_hold_count
991 && p->hello_when != 0 && p->selected && !p->updt_info) {
992 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_CONFIG_EXEC;
995 case PORT_TRANSMIT_SM_TRANSMIT_CONFIG_EXEC:
1000 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_CONFIG;
1002 case PORT_TRANSMIT_SM_TRANSMIT_CONFIG:
1003 p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
1005 case PORT_TRANSMIT_SM_TRANSMIT_TCN_EXEC:
1006 p->new_info = false;
1009 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_TCN;
1011 case PORT_TRANSMIT_SM_TRANSMIT_TCN:
1012 p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
1014 case PORT_TRANSMIT_SM_TRANSMIT_RSTP_EXEC:
1015 p->new_info = false;
1019 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_RSTP;
1021 case PORT_TRANSMIT_SM_TRANSMIT_RSTP:
1022 p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
1028 if (old_state != p->port_transmit_sm_state) {
1030 VLOG_DBG("%s, port %u: port_transmit_sm %d -> %d", p->rstp->name,
1031 p->port_number, old_state, p->port_transmit_sm_state);
1036 /* [17.27 Port Information state machine] */
1041 rcv_info(struct rstp_port *p)
1042 OVS_REQUIRES(rstp_mutex)
1044 enum vector_comparison cp;
1046 enum port_flag role;
1048 p->msg_priority.root_bridge_id =
1049 ntohll(p->received_bpdu_buffer.root_bridge_id);
1050 p->msg_priority.root_path_cost =
1051 ntohl(p->received_bpdu_buffer.root_path_cost);
1052 p->msg_priority.designated_bridge_id =
1053 ntohll(p->received_bpdu_buffer.designated_bridge_id);
1054 p->msg_priority.designated_port_id =
1055 ntohs(p->received_bpdu_buffer.designated_port_id);
1057 p->msg_times.forward_delay =
1058 time_decode(p->received_bpdu_buffer.forward_delay);
1059 p->msg_times.hello_time = time_decode(p->received_bpdu_buffer.hello_time);
1060 p->msg_times.max_age = time_decode(p->received_bpdu_buffer.max_age);
1061 p->msg_times.message_age =
1062 time_decode(p->received_bpdu_buffer.message_age);
1064 cp = compare_rstp_priority_vectors(&p->msg_priority, &p->port_priority);
1065 ct = rstp_times_equal(&p->port_times, &p->msg_times);
1066 /* Configuration BPDU conveys a Designated Port Role. */
1067 if (p->received_bpdu_buffer.bpdu_type == CONFIGURATION_BPDU) {
1071 (p->received_bpdu_buffer.flags & ROLE_FLAG_MASK) >> ROLE_FLAG_SHIFT;
1074 /* 802.1D-2004 does not report this behaviour.
1075 * 802.1Q-2008 says set rcvdTcn. */
1076 if (p->received_bpdu_buffer.bpdu_type ==
1077 TOPOLOGY_CHANGE_NOTIFICATION_BPDU) {
1082 /* Returns SuperiorDesignatedInfo if:
1083 * a) The received message conveys a Designated Port Role, and
1084 * 1) The message priority is superior (17.6) to the Port.s port priority
1086 * 2) The message priority vector is the same as the Port.s port priority
1087 * vector, and any of the received timer parameter values (msg_times.
1088 * 17.19.15) differ from those already held for the Port (port_times
1090 * NOTE: Configuration BPDU explicitly conveys a Designated Port Role.
1092 if (role == PORT_DES && (cp == SUPERIOR || (cp == SAME && ct == false))) {
1093 return SUPERIOR_DESIGNATED_INFO;
1095 /* Returns RepeatedDesignatedInfo if:
1096 * b) The received message conveys Designated Port Role, and a message
1097 * priority vector and timer parameters that are the same as the
1098 * Port's port priority vector or timer values. */
1099 } else if (role == PORT_DES && cp == SAME && ct == true) {
1100 return REPEATED_DESIGNATED_INFO;
1102 /* Returns InferiorDesignatedInfo if:
1103 * c) The received message conveys a Designated Port Role, and a
1104 * message priority vector that is worse than the Port's port
1105 * priority vector. */
1106 } else if (role == PORT_DES && cp == INFERIOR) {
1107 return INFERIOR_DESIGNATED_INFO;
1109 /* Returns InferiorRootAlternateInfo if:
1110 * d) The received message conveys a Root Port, Alternate Port, or
1111 * Backup Port Role and a message priority that is the same as or
1112 * worse than the port priority vector. */
1113 } else if ((role == PORT_ROOT || role == PORT_ALT_BACK) &&
1114 (cp == INFERIOR || cp == SAME)) {
1115 return INFERIOR_ROOT_ALTERNATE_INFO;
1117 /* Otherwise, returns OtherInfo. */
1124 better_or_same_info(struct rstp_port *p, int new_info_is)
1125 OVS_REQUIRES(rstp_mutex)
1128 (new_info_is == RECEIVED && p->info_is == INFO_IS_RECEIVED
1129 && compare_rstp_priority_vectors(&p->msg_priority,
1131 || (new_info_is == MINE && p->info_is == INFO_IS_MINE
1132 && compare_rstp_priority_vectors(&p->designated_priority_vector,
1133 &p->port_priority));
1137 port_information_sm(struct rstp_port *p)
1138 OVS_REQUIRES(rstp_mutex)
1140 enum port_information_state_machine old_state;
1142 struct rstp_port *p1;
1144 old_state = p->port_information_sm_state;
1147 switch (p->port_information_sm_state) {
1148 case PORT_INFORMATION_SM_INIT:
1150 || (!p->port_enabled && p->info_is != INFO_IS_DISABLED)) {
1151 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1154 case PORT_INFORMATION_SM_DISABLED_EXEC:
1155 p->rcvd_msg = false;
1156 p->proposing = p->proposed = p->agree = p->agreed = false;
1157 p->rcvd_info_while = 0;
1158 p->info_is = INFO_IS_DISABLED;
1160 p->selected = false;
1161 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED;
1163 case PORT_INFORMATION_SM_DISABLED:
1164 if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1165 /* Global transition. */
1166 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1167 } else if (p->port_enabled) {
1168 p->port_information_sm_state = PORT_INFORMATION_SM_AGED_EXEC;
1169 } else if (p->rcvd_msg) {
1170 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1173 case PORT_INFORMATION_SM_AGED_EXEC:
1174 p->info_is = INFO_IS_AGED;
1176 p->selected = false;
1177 p->port_information_sm_state = PORT_INFORMATION_SM_AGED;
1179 case PORT_INFORMATION_SM_AGED:
1180 if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1181 /* Global transition. */
1182 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1183 } else if (p->selected && p->updt_info) {
1184 p->port_information_sm_state = PORT_INFORMATION_SM_UPDATE_EXEC;
1187 case PORT_INFORMATION_SM_UPDATE_EXEC:
1188 p->proposing = p->proposed = false;
1189 /* MINE is not specified in Standard 802.1D-2004. */
1190 p->agreed = p->agreed && better_or_same_info(p, MINE);
1191 p->synced = p->synced && p->agreed;
1192 p->port_priority.root_bridge_id =
1193 p->designated_priority_vector.root_bridge_id;
1194 p->port_priority.root_path_cost =
1195 p->designated_priority_vector.root_path_cost;
1196 p->port_priority.designated_bridge_id =
1197 p->designated_priority_vector.designated_bridge_id;
1198 p->port_priority.designated_port_id =
1199 p->designated_priority_vector.designated_port_id;
1200 p->port_times = p->designated_times;
1201 p->updt_info = false;
1202 p->info_is = INFO_IS_MINE;
1204 p->port_information_sm_state = PORT_INFORMATION_SM_UPDATE;
1206 case PORT_INFORMATION_SM_UPDATE:
1207 if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1208 /* Global transition. */
1209 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1211 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1214 case PORT_INFORMATION_SM_CURRENT_EXEC:
1215 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT;
1217 case PORT_INFORMATION_SM_CURRENT:
1218 if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1219 /* Global transition. */
1220 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1221 } else if (p->rcvd_msg && !p->updt_info) {
1222 p->port_information_sm_state = PORT_INFORMATION_SM_RECEIVE_EXEC;
1223 } else if (p->selected && p->updt_info) {
1224 p->port_information_sm_state = PORT_INFORMATION_SM_UPDATE_EXEC;
1225 } else if ((p->info_is == INFO_IS_RECEIVED) &&
1226 (p->rcvd_info_while == 0) && !p->updt_info &&
1228 p->port_information_sm_state = PORT_INFORMATION_SM_AGED_EXEC;
1231 case PORT_INFORMATION_SM_RECEIVE_EXEC:
1232 p->rcvd_info = rcv_info(p);
1233 p->port_information_sm_state = PORT_INFORMATION_SM_RECEIVE;
1235 case PORT_INFORMATION_SM_RECEIVE:
1236 if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1237 /* Global transition. */
1238 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1240 switch (p->rcvd_info) {
1241 case SUPERIOR_DESIGNATED_INFO:
1242 /* 802.1q-2008 has a checkBPDUConsistency() function, called on
1243 * a BPDU reception. checkBPDUConsistency() clears the agreed
1244 * variable if the received message priority vector is superior
1245 * to the port priority vector, the BPDU is an ST BPDU or an
1246 * RST BPDU, its port role is Designated and its Learning flag
1248 if (p->received_bpdu_buffer.flags & BPDU_FLAG_LEARNING) {
1249 HMAP_FOR_EACH (p1, node, &r->ports) {
1250 if (p1->port_number != p->port_number) {
1255 p->port_information_sm_state =
1256 PORT_INFORMATION_SM_SUPERIOR_DESIGNATED_EXEC;
1258 case REPEATED_DESIGNATED_INFO:
1259 p->port_information_sm_state =
1260 PORT_INFORMATION_SM_REPEATED_DESIGNATED_EXEC;
1262 case INFERIOR_DESIGNATED_INFO:
1263 p->port_information_sm_state =
1264 PORT_INFORMATION_SM_INFERIOR_DESIGNATED_EXEC;
1266 case INFERIOR_ROOT_ALTERNATE_INFO:
1267 p->port_information_sm_state =
1268 PORT_INFORMATION_SM_NOT_DESIGNATED_EXEC;
1271 p->port_information_sm_state = PORT_INFORMATION_SM_OTHER_EXEC;
1279 case PORT_INFORMATION_SM_OTHER_EXEC:
1280 p->rcvd_msg = false;
1281 p->port_information_sm_state = PORT_INFORMATION_SM_OTHER;
1283 case PORT_INFORMATION_SM_OTHER:
1284 if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1285 /* Global transition. */
1286 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1288 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1291 case PORT_INFORMATION_SM_NOT_DESIGNATED_EXEC:
1292 record_agreement(p);
1294 p->rcvd_msg = false;
1295 p->port_information_sm_state = PORT_INFORMATION_SM_NOT_DESIGNATED;
1297 case PORT_INFORMATION_SM_NOT_DESIGNATED:
1298 if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1299 /* Global transition. */
1300 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1302 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1305 case PORT_INFORMATION_SM_INFERIOR_DESIGNATED_EXEC:
1307 p->rcvd_msg = false;
1308 p->port_information_sm_state = PORT_INFORMATION_SM_INFERIOR_DESIGNATED;
1310 case PORT_INFORMATION_SM_INFERIOR_DESIGNATED:
1311 if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1312 /* Global transition. */
1313 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1315 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1318 case PORT_INFORMATION_SM_REPEATED_DESIGNATED_EXEC:
1321 /* This record_agreement() is missing in 802.1D-2004, but it's present
1322 * in 802.1q-2008. */
1323 record_agreement(p);
1324 updt_rcvd_info_while(p);
1325 p->rcvd_msg = false;
1326 p->port_information_sm_state = PORT_INFORMATION_SM_REPEATED_DESIGNATED;
1328 case PORT_INFORMATION_SM_REPEATED_DESIGNATED:
1329 if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1330 /* Global transition. */
1331 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1333 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1336 case PORT_INFORMATION_SM_SUPERIOR_DESIGNATED_EXEC:
1337 p->agreed = p->proposing = false;
1340 /* RECEIVED is not specified in Standard 802.1D-2004. */
1341 p->agree = p->agree && better_or_same_info(p, RECEIVED);
1342 /* This record_agreement() and the synced assignment are missing in
1343 * 802.1D-2004, but they're present in 802.1q-2008. */
1344 record_agreement(p);
1345 p->synced = p->synced && p->agreed;
1348 updt_rcvd_info_while(p);
1349 p->info_is = INFO_IS_RECEIVED;
1351 p->selected = false;
1352 p->rcvd_msg = false;
1353 p->port_information_sm_state = PORT_INFORMATION_SM_SUPERIOR_DESIGNATED;
1355 case PORT_INFORMATION_SM_SUPERIOR_DESIGNATED:
1356 if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1357 /* Global transition. */
1358 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1360 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1367 if (old_state != p->port_information_sm_state) {
1369 VLOG_DBG("%s, port %u: Port_information_sm %d -> %d", p->rstp->name,
1370 p->port_number, old_state, p->port_information_sm_state);
1375 /* [17.29 Port Role Transitions state machine] */
1378 set_re_root_tree(struct rstp_port *p)
1379 OVS_REQUIRES(rstp_mutex)
1382 struct rstp_port *p1;
1385 HMAP_FOR_EACH (p1, node, &r->ports) {
1391 set_sync_tree(struct rstp_port *p)
1392 OVS_REQUIRES(rstp_mutex)
1395 struct rstp_port *p1;
1398 HMAP_FOR_EACH (p1, node, &r->ports) {
1404 hello_time(struct rstp_port *p)
1405 OVS_REQUIRES(rstp_mutex)
1407 return p->designated_times.hello_time;
1411 fwd_delay(struct rstp_port *p)
1412 OVS_REQUIRES(rstp_mutex)
1414 return p->designated_times.forward_delay;
1418 forward_delay(struct rstp_port *p)
1419 OVS_REQUIRES(rstp_mutex)
1422 return hello_time(p);
1424 return fwd_delay(p);
1429 edge_delay(struct rstp_port *p)
1430 OVS_REQUIRES(rstp_mutex)
1435 if (p->oper_point_to_point_mac == 1) {
1436 return r->migrate_time;
1438 return p->designated_times.max_age;
1443 check_selected_role_change(struct rstp_port *p, int current_role_state)
1444 OVS_REQUIRES(rstp_mutex)
1446 if (p->selected && !p->updt_info && p->role != p->selected_role
1447 && p->selected_role != current_role_state) {
1448 VLOG_DBG("%s, port %u: case: current = %s role = %s selected = %d",
1449 p->rstp->name, p->port_number,
1450 rstp_port_role_name(current_role_state),
1451 rstp_port_role_name(p->role), p->selected_role);
1452 switch (p->selected_role) {
1454 p->port_role_transition_sm_state =
1455 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1457 case ROLE_DESIGNATED:
1458 p->port_role_transition_sm_state =
1459 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1461 case ROLE_ALTERNATE:
1462 p->port_role_transition_sm_state =
1463 PORT_ROLE_TRANSITION_SM_BLOCK_PORT_EXEC;
1466 p->port_role_transition_sm_state =
1467 PORT_ROLE_TRANSITION_SM_BLOCK_PORT_EXEC;
1470 p->port_role_transition_sm_state =
1471 PORT_ROLE_TRANSITION_SM_DISABLE_PORT_EXEC;
1479 re_rooted(struct rstp_port *p)
1480 OVS_REQUIRES(rstp_mutex)
1483 struct rstp_port *p1;
1486 HMAP_FOR_EACH (p1, node, &r->ports) {
1487 if ((p1 != p) && (p1->rr_while != 0)) {
1495 all_synced(struct rstp *r)
1496 OVS_REQUIRES(rstp_mutex)
1498 struct rstp_port *p;
1500 HMAP_FOR_EACH (p, node, &r->ports) {
1501 if (!(p->selected && p->role == p->selected_role &&
1502 (p->role == ROLE_ROOT || p->synced == true))) {
1510 port_role_transition_sm(struct rstp_port *p)
1511 OVS_REQUIRES(rstp_mutex)
1513 enum port_role_transition_state_machine old_state;
1515 enum rstp_port_role last_role;
1517 old_state = p->port_role_transition_sm_state;
1519 last_role = p->role;
1521 switch (p->port_role_transition_sm_state) {
1522 case PORT_ROLE_TRANSITION_SM_INIT:
1524 p->port_role_transition_sm_state =
1525 PORT_ROLE_TRANSITION_SM_INIT_PORT_EXEC;
1528 case PORT_ROLE_TRANSITION_SM_INIT_PORT_EXEC:
1529 p->role = ROLE_DISABLED;
1530 p->learn = p->forward = false;
1532 p->sync = p->re_root = true;
1533 p->rr_while = p->designated_times.forward_delay;
1534 p->fd_while = p->designated_times.max_age;
1536 p->port_role_transition_sm_state =
1537 PORT_ROLE_TRANSITION_SM_DISABLE_PORT_EXEC;
1539 case PORT_ROLE_TRANSITION_SM_DISABLE_PORT_EXEC:
1540 p->role = p->selected_role;
1541 p->learn = p->forward = false;
1542 p->port_role_transition_sm_state =
1543 PORT_ROLE_TRANSITION_SM_DISABLE_PORT;
1545 case PORT_ROLE_TRANSITION_SM_DISABLE_PORT:
1546 if (check_selected_role_change(p, ROLE_DISABLED)) {
1547 /* Global transition. */
1548 } else if (p->selected && !p->updt_info && !p->learning
1549 && !p->forwarding) {
1550 p->port_role_transition_sm_state =
1551 PORT_ROLE_TRANSITION_SM_DISABLED_PORT_EXEC;
1554 case PORT_ROLE_TRANSITION_SM_DISABLED_PORT_EXEC:
1555 p->fd_while = p->designated_times.max_age;
1558 p->sync = p->re_root = false;
1559 p->port_role_transition_sm_state =
1560 PORT_ROLE_TRANSITION_SM_DISABLED_PORT;
1562 case PORT_ROLE_TRANSITION_SM_DISABLED_PORT:
1563 if (check_selected_role_change(p, ROLE_DISABLED)) {
1564 /* Global transition. */
1565 } else if (p->selected && !p->updt_info
1566 && (p->fd_while != p->designated_times.max_age || p->sync
1567 || p->re_root || !p->synced)) {
1568 p->port_role_transition_sm_state =
1569 PORT_ROLE_TRANSITION_SM_DISABLED_PORT_EXEC;
1572 case PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC:
1573 p->role = ROLE_ROOT;
1574 p->rr_while = p->designated_times.forward_delay;
1575 p->port_role_transition_sm_state = PORT_ROLE_TRANSITION_SM_ROOT_PORT;
1577 case PORT_ROLE_TRANSITION_SM_ROOT_PORT:
1578 if (check_selected_role_change(p, ROLE_ROOT)) {
1579 /* Global transition. */
1580 } else if (p->selected && !p->updt_info) {
1581 if (p->rr_while != p->designated_times.forward_delay) {
1582 p->port_role_transition_sm_state =
1583 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1585 } else if (p->re_root && p->forward) {
1586 p->port_role_transition_sm_state =
1587 PORT_ROLE_TRANSITION_SM_REROOTED_EXEC;
1589 } else if ((p->fd_while == 0
1590 || ((re_rooted(p) && p->rb_while == 0)
1591 && r->rstp_version)) && !p->learn) {
1592 p->port_role_transition_sm_state =
1593 PORT_ROLE_TRANSITION_SM_ROOT_LEARN_EXEC;
1595 } else if ((p->fd_while == 0
1596 || ((re_rooted(p) && p->rb_while == 0)
1597 && r->rstp_version)) && p->learn && !p->forward) {
1598 p->port_role_transition_sm_state =
1599 PORT_ROLE_TRANSITION_SM_ROOT_FORWARD_EXEC;
1601 } else if (p->proposed && !p->agree) {
1602 p->port_role_transition_sm_state =
1603 PORT_ROLE_TRANSITION_SM_ROOT_PROPOSED_EXEC;
1605 } else if ((all_synced(r) && !p->agree) ||
1606 (p->proposed && p->agree)) {
1607 p->port_role_transition_sm_state =
1608 PORT_ROLE_TRANSITION_SM_ROOT_AGREED_EXEC;
1610 } else if (!p->forward && !p->re_root) {
1611 p->port_role_transition_sm_state =
1612 PORT_ROLE_TRANSITION_SM_REROOT_EXEC;
1617 case PORT_ROLE_TRANSITION_SM_REROOT_EXEC:
1618 if (check_selected_role_change(p, ROLE_ROOT)) {
1619 /* Global transition. */
1621 set_re_root_tree(p);
1622 p->port_role_transition_sm_state =
1623 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1626 case PORT_ROLE_TRANSITION_SM_ROOT_AGREED_EXEC:
1627 if (check_selected_role_change(p, ROLE_ROOT)) {
1628 /* Global transition. */
1630 p->proposed = p->sync = false;
1631 p->agree = p->new_info = true;
1632 p->port_role_transition_sm_state =
1633 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1636 case PORT_ROLE_TRANSITION_SM_ROOT_PROPOSED_EXEC:
1638 p->proposed = false;
1639 if (check_selected_role_change(p, ROLE_ROOT)) {
1640 /* Global transition. */
1642 p->port_role_transition_sm_state =
1643 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1646 case PORT_ROLE_TRANSITION_SM_ROOT_FORWARD_EXEC:
1649 if (check_selected_role_change(p, ROLE_ROOT)) {
1650 /* Global transition. */
1652 p->port_role_transition_sm_state =
1653 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1656 case PORT_ROLE_TRANSITION_SM_ROOT_LEARN_EXEC:
1657 p->fd_while = forward_delay(p);
1659 if (check_selected_role_change(p, ROLE_ROOT)) {
1660 /* Global transition. */
1662 p->port_role_transition_sm_state =
1663 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1666 case PORT_ROLE_TRANSITION_SM_REROOTED_EXEC:
1668 if (check_selected_role_change(p, ROLE_ROOT)) {
1669 /* Global transition. */
1671 p->port_role_transition_sm_state =
1672 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1675 case PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC:
1676 p->role = ROLE_DESIGNATED;
1677 p->port_role_transition_sm_state =
1678 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT;
1680 case PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT:
1681 if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1682 /* Global transition. */
1683 } else if (p->selected && !p->updt_info) {
1684 if (((p->sync && !p->synced)
1685 || (p->re_root && p->rr_while != 0) || p->disputed)
1686 && !p->oper_edge && (p->learn || p->forward)) {
1687 p->port_role_transition_sm_state =
1688 PORT_ROLE_TRANSITION_SM_DESIGNATED_DISCARD_EXEC;
1689 } else if ((p->fd_while == 0 || p->agreed || p->oper_edge)
1690 && (p->rr_while == 0 || !p->re_root)
1691 && !p->sync && !p->learn) {
1692 p->port_role_transition_sm_state =
1693 PORT_ROLE_TRANSITION_SM_DESIGNATED_LEARN_EXEC;
1694 } else if ((p->fd_while == 0 || p->agreed || p->oper_edge)
1695 && (p->rr_while == 0 || !p->re_root)
1696 && !p->sync && (p->learn && !p->forward)) {
1697 p->port_role_transition_sm_state =
1698 PORT_ROLE_TRANSITION_SM_DESIGNATED_FORWARD_EXEC;
1699 } else if (!p->forward && !p->agreed && !p->proposing &&
1701 p->port_role_transition_sm_state =
1702 PORT_ROLE_TRANSITION_SM_DESIGNATED_PROPOSE_EXEC;
1703 } else if ((!p->learning && !p->forwarding && !p->synced)
1704 || (p->agreed && !p->synced)
1705 || (p->oper_edge && !p->synced)
1706 || (p->sync && p->synced)) {
1707 p->port_role_transition_sm_state =
1708 PORT_ROLE_TRANSITION_SM_DESIGNATED_SYNCED_EXEC;
1709 } else if (p->rr_while == 0 && p->re_root) {
1710 p->port_role_transition_sm_state =
1711 PORT_ROLE_TRANSITION_SM_DESIGNATED_RETIRED_EXEC;
1715 case PORT_ROLE_TRANSITION_SM_DESIGNATED_RETIRED_EXEC:
1717 if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1718 /* Global transition. */
1720 p->port_role_transition_sm_state =
1721 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1724 case PORT_ROLE_TRANSITION_SM_DESIGNATED_SYNCED_EXEC:
1728 if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1729 /* Global transition. */
1731 p->port_role_transition_sm_state =
1732 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1735 case PORT_ROLE_TRANSITION_SM_DESIGNATED_PROPOSE_EXEC:
1736 p->proposing = true;
1737 p->edge_delay_while = edge_delay(p);
1739 if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1740 /* Global transition. */
1742 p->port_role_transition_sm_state =
1743 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1746 case PORT_ROLE_TRANSITION_SM_DESIGNATED_FORWARD_EXEC:
1749 p->agreed = p->send_rstp;
1750 if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1751 /* Global transition. */
1753 p->port_role_transition_sm_state =
1754 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1757 case PORT_ROLE_TRANSITION_SM_DESIGNATED_LEARN_EXEC:
1759 p->fd_while = forward_delay(p);
1760 if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1761 /* Global transition. */
1763 p->port_role_transition_sm_state =
1764 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1767 case PORT_ROLE_TRANSITION_SM_DESIGNATED_DISCARD_EXEC:
1768 p->learn = p->forward = p->disputed = false;
1769 p->fd_while = forward_delay(p);
1770 if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1771 /* Global transition. */
1773 p->port_role_transition_sm_state =
1774 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1777 case PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC:
1778 p->fd_while = p->designated_times.forward_delay;
1781 p->sync = p->re_root = false;
1782 p->port_role_transition_sm_state =
1783 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT;
1785 case PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT:
1786 if (check_selected_role_change(p, ROLE_ALTERNATE)) {
1787 /* Global transition. */
1788 } else if (p->selected && !p->updt_info) {
1789 if (p->rb_while != 2 * p->designated_times.hello_time
1790 && p->role == ROLE_BACKUP) {
1791 p->port_role_transition_sm_state =
1792 PORT_ROLE_TRANSITION_SM_BACKUP_PORT_EXEC;
1793 } else if ((p->fd_while != forward_delay(p)) || p->sync
1794 || p->re_root || !p->synced) {
1795 p->port_role_transition_sm_state =
1796 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1797 } else if (p->proposed && !p->agree) {
1798 p->port_role_transition_sm_state =
1799 PORT_ROLE_TRANSITION_SM_ALTERNATE_PROPOSED_EXEC;
1800 } else if ((all_synced(r) && !p->agree)
1801 || (p->proposed && p->agree)) {
1802 p->port_role_transition_sm_state =
1803 PORT_ROLE_TRANSITION_SM_ALTERNATE_AGREED_EXEC;
1807 case PORT_ROLE_TRANSITION_SM_ALTERNATE_AGREED_EXEC:
1808 p->proposed = false;
1811 if (check_selected_role_change(p, ROLE_ALTERNATE)) {
1812 /* Global transition. */
1814 p->port_role_transition_sm_state =
1815 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1818 case PORT_ROLE_TRANSITION_SM_ALTERNATE_PROPOSED_EXEC:
1820 p->proposed = false;
1821 if (check_selected_role_change(p, ROLE_ALTERNATE)) {
1822 /* Global transition. */
1824 p->port_role_transition_sm_state =
1825 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1828 case PORT_ROLE_TRANSITION_SM_BLOCK_PORT_EXEC:
1829 p->role = p->selected_role;
1830 p->learn = p->forward = false;
1831 p->port_role_transition_sm_state = PORT_ROLE_TRANSITION_SM_BLOCK_PORT;
1833 case PORT_ROLE_TRANSITION_SM_BLOCK_PORT:
1834 if (check_selected_role_change(p, ROLE_ALTERNATE)) {
1835 /* Global transition. */
1836 } else if (p->selected && !p->updt_info && !p->learning &&
1838 p->port_role_transition_sm_state =
1839 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1842 case PORT_ROLE_TRANSITION_SM_BACKUP_PORT_EXEC:
1843 p->rb_while = 2 * p->designated_times.hello_time;
1844 if (check_selected_role_change(p, ROLE_ALTERNATE)) {
1845 /* Global transition. */
1847 p->port_role_transition_sm_state =
1848 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1855 if (old_state != p->port_role_transition_sm_state) {
1857 VLOG_DBG("%s, port %u: Port_role_transition_sm %d -> %d",
1858 p->rstp->name, p->port_number, old_state,
1859 p->port_role_transition_sm_state);
1861 if (last_role != p->role) {
1862 VLOG_DBG("%s, port %u, port role ["RSTP_PORT_ID_FMT"] = %s",
1863 p->rstp->name, p->port_number, p->port_id,
1864 rstp_port_role_name(p->role));
1869 /* [17.30 - Port state transition state machine] */
1872 enable_learning(struct rstp_port *p)
1873 OVS_REQUIRES(rstp_mutex)
1875 /* [17.21.6 enableLearning()] An implementation dependent procedure that
1876 * causes the Learning Process (7.8) to start learning from frames received
1877 * on the Port. The procedure does not complete until learning has been
1880 rstp_port_set_state__(p, RSTP_LEARNING);
1884 enable_forwarding(struct rstp_port *p)
1885 OVS_REQUIRES(rstp_mutex)
1887 /* [17.21.5 enableForwarding()] An implementation dependent procedure that
1888 * causes the Forwarding Process (7.7) to start forwarding frames through
1889 * the Port. The procedure does not complete until forwarding has been
1892 rstp_port_set_state__(p, RSTP_FORWARDING);
1896 disable_learning(struct rstp_port *p)
1897 OVS_REQUIRES(rstp_mutex)
1899 /* [17.21.4 - disableLearning()] An implementation dependent procedure that
1900 * causes the Learning Process (7.8) to stop learning from the source
1901 * address of frames received on the Port. The procedure does not complete
1902 * until learning has stopped.
1904 rstp_port_set_state__(p, RSTP_DISCARDING);
1908 disable_forwarding(struct rstp_port *p)
1909 OVS_REQUIRES(rstp_mutex)
1911 /* [17.21.3 - disableForwarding()] An implementation dependent procedure
1912 * that causes the Forwarding Process (7.7) to stop forwarding frames
1913 * through the Port. The procedure does not complete until forwarding has
1916 rstp_port_set_state__(p, RSTP_DISCARDING);
1920 port_state_transition_sm(struct rstp_port *p)
1921 OVS_REQUIRES(rstp_mutex)
1923 enum port_state_transition_state_machine old_state;
1926 old_state = p->port_state_transition_sm_state;
1929 switch (p->port_state_transition_sm_state) {
1930 case PORT_STATE_TRANSITION_SM_INIT:
1932 p->port_state_transition_sm_state =
1933 PORT_STATE_TRANSITION_SM_DISCARDING_EXEC;
1936 case PORT_STATE_TRANSITION_SM_DISCARDING_EXEC:
1937 disable_learning(p);
1938 p->learning = false;
1939 disable_forwarding(p);
1940 p->forwarding = false;
1941 p->port_state_transition_sm_state =
1942 PORT_STATE_TRANSITION_SM_DISCARDING;
1944 case PORT_STATE_TRANSITION_SM_DISCARDING:
1946 p->port_state_transition_sm_state =
1947 PORT_STATE_TRANSITION_SM_LEARNING_EXEC;
1950 case PORT_STATE_TRANSITION_SM_LEARNING_EXEC:
1953 p->port_state_transition_sm_state = PORT_STATE_TRANSITION_SM_LEARNING;
1955 case PORT_STATE_TRANSITION_SM_LEARNING:
1957 p->port_state_transition_sm_state =
1958 PORT_STATE_TRANSITION_SM_DISCARDING_EXEC;
1959 } else if (p->forward) {
1960 p->port_state_transition_sm_state =
1961 PORT_STATE_TRANSITION_SM_FORWARDING_EXEC;
1964 case PORT_STATE_TRANSITION_SM_FORWARDING_EXEC:
1965 enable_forwarding(p);
1966 p->forwarding = true;
1967 p->port_state_transition_sm_state =
1968 PORT_STATE_TRANSITION_SM_FORWARDING;
1970 case PORT_STATE_TRANSITION_SM_FORWARDING:
1972 p->port_state_transition_sm_state =
1973 PORT_STATE_TRANSITION_SM_DISCARDING_EXEC;
1980 if (old_state != p->port_state_transition_sm_state) {
1982 VLOG_DBG("%s, port %u: Port_state_transition_sm %d -> %d",
1983 p->rstp->name, p->port_number, old_state,
1984 p->port_state_transition_sm_state);
1989 /* [17.31 - Topology Change state machine] */
1992 new_tc_while(struct rstp_port *p)
1993 OVS_REQUIRES(rstp_mutex)
1998 if (p->tc_while == 0 && p->send_rstp == true) {
1999 p->tc_while = r->bridge_hello_time + 1;
2001 } else if (p->tc_while == 0 && p->send_rstp == false) {
2002 p->tc_while = r->bridge_max_age + r->bridge_forward_delay;
2006 /* [17.21.18 setTcPropTree()]
2007 * Sets tcprop for all Ports except the Port that called the procedure.
2010 set_tc_prop_tree(struct rstp_port *p)
2011 OVS_REQUIRES(rstp_mutex)
2014 struct rstp_port *p1;
2017 HMAP_FOR_EACH (p1, node, &r->ports) {
2018 /* Set tc_prop on every port, except the one calling this
2020 if (p1->port_number != p->port_number) {
2027 set_tc_prop_bridge(struct rstp_port *p) /* not specified in 802.1D-2004. */
2028 OVS_REQUIRES(rstp_mutex)
2030 set_tc_prop_tree(p); /* see 802.1w-2001. */
2034 topology_change_sm(struct rstp_port *p)
2035 OVS_REQUIRES(rstp_mutex)
2037 enum topology_change_state_machine old_state;
2040 old_state = p->topology_change_sm_state;
2043 switch (p->topology_change_sm_state) {
2044 case TOPOLOGY_CHANGE_SM_INIT:
2046 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_INACTIVE_EXEC;
2049 case TOPOLOGY_CHANGE_SM_INACTIVE_EXEC:
2050 p->fdb_flush = true;
2053 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_INACTIVE;
2055 case TOPOLOGY_CHANGE_SM_INACTIVE:
2056 if (p->learn && !p->fdb_flush) {
2057 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING_EXEC;
2060 case TOPOLOGY_CHANGE_SM_LEARNING_EXEC:
2061 p->rcvd_tc = p->rcvd_tcn = p->rcvd_tc_ack = false;
2062 p->tc_prop = p->rcvd_tc_ack = false;
2063 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING;
2065 case TOPOLOGY_CHANGE_SM_LEARNING:
2066 if (p->role != ROLE_ROOT && p->role != ROLE_DESIGNATED &&
2067 !(p->learn || p->learning) && !(p->rcvd_tc || p->rcvd_tcn ||
2068 p->rcvd_tc_ack || p->tc_prop)) {
2069 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_INACTIVE_EXEC;
2070 } else if (p->rcvd_tc || p->rcvd_tcn || p->rcvd_tc_ack || p->tc_prop) {
2071 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING_EXEC;
2072 } else if ((p->role == ROLE_ROOT || p->role == ROLE_DESIGNATED)
2073 && p->forward && !p->oper_edge) {
2074 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_DETECTED_EXEC;
2077 case TOPOLOGY_CHANGE_SM_DETECTED_EXEC:
2079 set_tc_prop_tree(p);
2081 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE_EXEC;
2083 case TOPOLOGY_CHANGE_SM_ACTIVE_EXEC:
2084 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
2086 case TOPOLOGY_CHANGE_SM_ACTIVE:
2087 if ((p->role != ROLE_ROOT && p->role != ROLE_DESIGNATED)
2089 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING_EXEC;
2090 } else if (p->rcvd_tcn) {
2091 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_NOTIFIED_TCN_EXEC;
2092 } else if (p->rcvd_tc) {
2093 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_NOTIFIED_TC_EXEC;
2094 } else if (p->tc_prop && !p->oper_edge) {
2095 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_PROPAGATING_EXEC;
2096 } else if (p->rcvd_tc_ack) {
2097 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACKNOWLEDGED_EXEC;
2100 case TOPOLOGY_CHANGE_SM_ACKNOWLEDGED_EXEC:
2102 p->rcvd_tc_ack = false;
2103 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
2105 case TOPOLOGY_CHANGE_SM_PROPAGATING_EXEC:
2107 p->fdb_flush = true;
2109 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
2111 case TOPOLOGY_CHANGE_SM_NOTIFIED_TC_EXEC:
2112 p->rcvd_tcn = p->rcvd_tc = false;
2113 if (p->role == ROLE_DESIGNATED) {
2116 set_tc_prop_bridge(p);
2117 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
2119 case TOPOLOGY_CHANGE_SM_NOTIFIED_TCN_EXEC:
2121 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_NOTIFIED_TC_EXEC;
2127 if (old_state != p->topology_change_sm_state) {
2129 VLOG_DBG("%s, port %u: Topology_change_sm %d -> %d", p->rstp->name,
2130 p->port_number, old_state, p->topology_change_sm_state);
2135 /****************************************************************************
2136 * [17.6] Priority vector calculation helper functions
2137 ****************************************************************************/
2139 /* compare_rstp_priority_vectors() compares two struct rstp_priority_vectors
2140 * and returns a value indicating if the first rstp_priority_vector is
2141 * superior, same or inferior to the second one.
2143 * Zero return value indicates INFERIOR, a non-zero return value indicates
2144 * SUPERIOR. When it makes a difference the non-zero return value SAME
2145 * indicates the priority vectors are identical (a subset of SUPERIOR).
2147 static enum vector_comparison
2148 compare_rstp_priority_vectors(const struct rstp_priority_vector *v1,
2149 const struct rstp_priority_vector *v2)
2151 VLOG_DBG("v1: "RSTP_ID_FMT", %u, "RSTP_ID_FMT", %d, %d",
2152 RSTP_ID_ARGS(v1->root_bridge_id), v1->root_path_cost,
2153 RSTP_ID_ARGS(v1->designated_bridge_id), v1->designated_port_id,
2154 v1->bridge_port_id);
2155 VLOG_DBG("v2: "RSTP_ID_FMT", %u, "RSTP_ID_FMT", %d, %d",
2156 RSTP_ID_ARGS(v2->root_bridge_id), v2->root_path_cost,
2157 RSTP_ID_ARGS(v2->designated_bridge_id), v2->designated_port_id,
2158 v2->bridge_port_id);
2161 * This message priority vector is superior to the port priority vector and
2162 * will replace it if, and only if, the message priority vector is better
2163 * than the port priority vector, or the message has been transmitted from
2164 * the same Designated Bridge and Designated Port as the port priority
2165 * vector, i.e., if the following is true:
2167 * ((RD < RootBridgeID)) ||
2168 * ((RD == RootBridgeID) && (RPCD < RootPathCost)) ||
2169 * ((RD == RootBridgeID) && (RPCD == RootPathCost) &&
2170 * (D < designated_bridge_id)) ||
2171 * ((RD == RootBridgeID) && (RPCD == RootPathCost) &&
2172 * (D == designated_bridge_id) && (PD < designated_port_id)) ||
2173 * ((D == designated_bridge_id.BridgeAddress) &&
2174 * (PD == designated_port_id.PortNumber))
2176 if ((v1->root_bridge_id < v2->root_bridge_id)
2177 || (v1->root_bridge_id == v2->root_bridge_id
2178 && v1->root_path_cost < v2->root_path_cost)
2179 || (v1->root_bridge_id == v2->root_bridge_id
2180 && v1->root_path_cost == v2->root_path_cost
2181 && v1->designated_bridge_id < v2->designated_bridge_id)
2182 || (v1->root_bridge_id == v2->root_bridge_id
2183 && v1->root_path_cost == v2->root_path_cost
2184 && v1->designated_bridge_id == v2->designated_bridge_id
2185 && v1->designated_port_id < v2->designated_port_id)
2186 || (v1->designated_bridge_id == v2->designated_bridge_id
2187 && v1->designated_port_id == v2->designated_port_id)) {
2188 /* SAME is a subset of SUPERIOR. */
2189 if (v1->root_bridge_id == v2->root_bridge_id
2190 && v1->root_path_cost == v2->root_path_cost
2191 && v1->designated_bridge_id == v2->designated_bridge_id
2192 && v1->designated_port_id == v2->designated_port_id) {
2193 if (v1->bridge_port_id < v2->bridge_port_id) {
2194 VLOG_DBG("superior");
2197 else if (v1->bridge_port_id > v2->bridge_port_id) {
2198 VLOG_DBG("inferior");
2201 VLOG_DBG("superior_same");
2204 VLOG_DBG("superior");
2208 VLOG_DBG("inferior");
2213 rstp_times_equal(struct rstp_times *t1, struct rstp_times *t2)
2215 return t1->forward_delay == t2->forward_delay
2216 && t1->hello_time == t2->hello_time
2217 && t1->max_age == t2->max_age
2218 && t1->message_age == t2->message_age;