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"
41 #include "openvswitch/ofpbuf.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
;