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 <sys/types.h>
35 #include <netinet/in.h>
36 #include <arpa/inet.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 memset(&bpdu
, 0, sizeof bpdu
);
842 bpdu
.protocol_identifier
= htons(0);
843 bpdu
.protocol_version_identifier
= 0;
844 bpdu
.bpdu_type
= CONFIGURATION_BPDU
;
845 bpdu
.root_bridge_id
= htonll(p
->designated_priority_vector
.root_bridge_id
);
846 bpdu
.root_path_cost
= htonl(p
->designated_priority_vector
.root_path_cost
);
847 bpdu
.designated_bridge_id
=
848 htonll(p
->designated_priority_vector
.designated_bridge_id
);
849 bpdu
.designated_port_id
=
850 htons(p
->designated_priority_vector
.designated_port_id
);
851 bpdu
.message_age
= time_encode(p
->designated_times
.message_age
);
852 bpdu
.max_age
= time_encode(p
->designated_times
.max_age
);
853 bpdu
.hello_time
= time_encode(p
->designated_times
.hello_time
);
854 bpdu
.forward_delay
= time_encode(p
->designated_times
.forward_delay
);
856 if (p
->tc_while
!= 0) {
857 bpdu
.flags
|= BPDU_FLAG_TOPCHANGE
;
859 if (p
->tc_ack
!= 0) {
860 bpdu
.flags
|= BPDU_FLAG_TOPCHANGEACK
;
862 rstp_send_bpdu(p
, &bpdu
, sizeof(struct rstp_bpdu
));
867 tx_rstp(struct rstp_port
*p
)
868 OVS_REQUIRES(rstp_mutex
)
870 struct rstp_bpdu bpdu
;
872 memset(&bpdu
, 0, sizeof bpdu
);
873 bpdu
.protocol_identifier
= htons(0);
874 bpdu
.protocol_version_identifier
= 2;
875 bpdu
.bpdu_type
= RAPID_SPANNING_TREE_BPDU
;
876 bpdu
.root_bridge_id
= htonll(p
->designated_priority_vector
.root_bridge_id
);
877 bpdu
.root_path_cost
= htonl(p
->designated_priority_vector
.root_path_cost
);
878 bpdu
.designated_bridge_id
=
879 htonll(p
->designated_priority_vector
.designated_bridge_id
);
880 bpdu
.designated_port_id
=
881 htons(p
->designated_priority_vector
.designated_port_id
);
882 bpdu
.message_age
= time_encode(p
->designated_times
.message_age
);
883 bpdu
.max_age
= time_encode(p
->designated_times
.max_age
);
884 bpdu
.hello_time
= time_encode(p
->designated_times
.hello_time
);
885 bpdu
.forward_delay
= time_encode(p
->designated_times
.forward_delay
);
890 bpdu
.flags
= PORT_ROOT
<< ROLE_FLAG_SHIFT
;
892 case ROLE_DESIGNATED
:
893 bpdu
.flags
= PORT_DES
<< ROLE_FLAG_SHIFT
;
897 bpdu
.flags
= PORT_ALT_BACK
<< ROLE_FLAG_SHIFT
;
900 /* Should not happen! */
901 VLOG_ERR("%s transmitting bpdu in disabled role on port "
902 RSTP_PORT_ID_FMT
, p
->rstp
->name
, p
->port_id
);
906 bpdu
.flags
|= BPDU_FLAG_AGREEMENT
;
909 bpdu
.flags
|= BPDU_FLAG_PROPOSAL
;
911 if (p
->tc_while
!= 0) {
912 bpdu
.flags
|= BPDU_FLAG_TOPCHANGE
;
915 bpdu
.flags
|= BPDU_FLAG_LEARNING
;
918 bpdu
.flags
|= BPDU_FLAG_FORWARDING
;
920 bpdu
.version1_length
= 0;
921 rstp_send_bpdu(p
, &bpdu
, sizeof(struct rstp_bpdu
));
926 tx_tcn(struct rstp_port
*p
)
927 OVS_REQUIRES(rstp_mutex
)
929 struct rstp_bpdu bpdu
;
931 memset(&bpdu
, 0, sizeof(struct rstp_bpdu
));
933 bpdu
.protocol_identifier
= htons(0);
934 bpdu
.protocol_version_identifier
= 0;
935 bpdu
.bpdu_type
= TOPOLOGY_CHANGE_NOTIFICATION_BPDU
;
936 rstp_send_bpdu(p
, &bpdu
, sizeof(struct rstp_bpdu
));
940 port_transmit_sm(struct rstp_port
*p
)
941 OVS_REQUIRES(rstp_mutex
)
943 enum port_transmit_state_machine old_state
;
946 old_state
= p
->port_transmit_sm_state
;
949 switch (p
->port_transmit_sm_state
) {
950 case PORT_TRANSMIT_SM_INIT
:
952 p
->port_transmit_sm_state
= PORT_TRANSMIT_SM_TRANSMIT_INIT_EXEC
;
955 case PORT_TRANSMIT_SM_TRANSMIT_INIT_EXEC
:
958 p
->port_transmit_sm_state
= PORT_TRANSMIT_SM_TRANSMIT_INIT
;
960 case PORT_TRANSMIT_SM_TRANSMIT_INIT
:
961 p
->port_transmit_sm_state
= PORT_TRANSMIT_SM_IDLE_EXEC
;
963 case PORT_TRANSMIT_SM_TRANSMIT_PERIODIC_EXEC
:
964 p
->new_info
= p
->new_info
|| (p
->role
== ROLE_DESIGNATED
||
965 (p
->role
== ROLE_ROOT
&& p
->tc_while
!= 0));
966 p
->port_transmit_sm_state
= PORT_TRANSMIT_SM_TRANSMIT_PERIODIC
;
968 case PORT_TRANSMIT_SM_TRANSMIT_PERIODIC
:
969 p
->port_transmit_sm_state
= PORT_TRANSMIT_SM_IDLE_EXEC
;
971 case PORT_TRANSMIT_SM_IDLE_EXEC
:
972 p
->hello_when
= r
->bridge_hello_time
;
973 p
->port_transmit_sm_state
= PORT_TRANSMIT_SM_IDLE
;
975 case PORT_TRANSMIT_SM_IDLE
:
976 if (p
->role
== ROLE_DISABLED
) {
977 VLOG_DBG("%s, port %u: port_transmit_sm ROLE == DISABLED.",
978 p
->rstp
->name
, p
->port_number
);
980 } else if (p
->send_rstp
&& p
->new_info
981 && p
->tx_count
< r
->transmit_hold_count
982 && p
->hello_when
!= 0 && p
->selected
&& !p
->updt_info
) {
983 p
->port_transmit_sm_state
= PORT_TRANSMIT_SM_TRANSMIT_RSTP_EXEC
;
984 } else if (p
->hello_when
== 0 && p
->selected
&& !p
->updt_info
) {
985 p
->port_transmit_sm_state
=
986 PORT_TRANSMIT_SM_TRANSMIT_PERIODIC_EXEC
;
987 } else if (!p
->send_rstp
&& p
->new_info
&& p
->role
== ROLE_ROOT
988 && p
->tx_count
< r
->transmit_hold_count
989 && p
->hello_when
!= 0 && p
->selected
&& !p
->updt_info
) {
990 p
->port_transmit_sm_state
= PORT_TRANSMIT_SM_TRANSMIT_TCN_EXEC
;
991 } else if (!p
->send_rstp
&& p
->new_info
&& p
->role
== ROLE_DESIGNATED
992 && p
->tx_count
< r
->transmit_hold_count
993 && p
->hello_when
!= 0 && p
->selected
&& !p
->updt_info
) {
994 p
->port_transmit_sm_state
= PORT_TRANSMIT_SM_TRANSMIT_CONFIG_EXEC
;
997 case PORT_TRANSMIT_SM_TRANSMIT_CONFIG_EXEC
:
1002 p
->port_transmit_sm_state
= PORT_TRANSMIT_SM_TRANSMIT_CONFIG
;
1004 case PORT_TRANSMIT_SM_TRANSMIT_CONFIG
:
1005 p
->port_transmit_sm_state
= PORT_TRANSMIT_SM_IDLE_EXEC
;
1007 case PORT_TRANSMIT_SM_TRANSMIT_TCN_EXEC
:
1008 p
->new_info
= false;
1011 p
->port_transmit_sm_state
= PORT_TRANSMIT_SM_TRANSMIT_TCN
;
1013 case PORT_TRANSMIT_SM_TRANSMIT_TCN
:
1014 p
->port_transmit_sm_state
= PORT_TRANSMIT_SM_IDLE_EXEC
;
1016 case PORT_TRANSMIT_SM_TRANSMIT_RSTP_EXEC
:
1017 p
->new_info
= false;
1021 p
->port_transmit_sm_state
= PORT_TRANSMIT_SM_TRANSMIT_RSTP
;
1023 case PORT_TRANSMIT_SM_TRANSMIT_RSTP
:
1024 p
->port_transmit_sm_state
= PORT_TRANSMIT_SM_IDLE_EXEC
;
1030 if (old_state
!= p
->port_transmit_sm_state
) {
1032 VLOG_DBG("%s, port %u: port_transmit_sm %d -> %d", p
->rstp
->name
,
1033 p
->port_number
, old_state
, p
->port_transmit_sm_state
);
1038 /* [17.27 Port Information state machine] */
1043 rcv_info(struct rstp_port
*p
)
1044 OVS_REQUIRES(rstp_mutex
)
1046 enum vector_comparison cp
;
1048 enum port_flag role
;
1050 p
->msg_priority
.root_bridge_id
=
1051 ntohll(p
->received_bpdu_buffer
.root_bridge_id
);
1052 p
->msg_priority
.root_path_cost
=
1053 ntohl(p
->received_bpdu_buffer
.root_path_cost
);
1054 p
->msg_priority
.designated_bridge_id
=
1055 ntohll(p
->received_bpdu_buffer
.designated_bridge_id
);
1056 p
->msg_priority
.designated_port_id
=
1057 ntohs(p
->received_bpdu_buffer
.designated_port_id
);
1059 p
->msg_times
.forward_delay
=
1060 time_decode(p
->received_bpdu_buffer
.forward_delay
);
1061 p
->msg_times
.hello_time
= time_decode(p
->received_bpdu_buffer
.hello_time
);
1062 p
->msg_times
.max_age
= time_decode(p
->received_bpdu_buffer
.max_age
);
1063 p
->msg_times
.message_age
=
1064 time_decode(p
->received_bpdu_buffer
.message_age
);
1066 cp
= compare_rstp_priority_vectors(&p
->msg_priority
, &p
->port_priority
);
1067 ct
= rstp_times_equal(&p
->port_times
, &p
->msg_times
);
1068 /* Configuration BPDU conveys a Designated Port Role. */
1069 if (p
->received_bpdu_buffer
.bpdu_type
== CONFIGURATION_BPDU
) {
1073 (p
->received_bpdu_buffer
.flags
& ROLE_FLAG_MASK
) >> ROLE_FLAG_SHIFT
;
1076 /* 802.1D-2004 does not report this behaviour.
1077 * 802.1Q-2008 says set rcvdTcn. */
1078 if (p
->received_bpdu_buffer
.bpdu_type
==
1079 TOPOLOGY_CHANGE_NOTIFICATION_BPDU
) {
1084 /* Returns SuperiorDesignatedInfo if:
1085 * a) The received message conveys a Designated Port Role, and
1086 * 1) The message priority is superior (17.6) to the Port.s port priority
1088 * 2) The message priority vector is the same as the Port.s port priority
1089 * vector, and any of the received timer parameter values (msg_times.
1090 * 17.19.15) differ from those already held for the Port (port_times
1092 * NOTE: Configuration BPDU explicitly conveys a Designated Port Role.
1094 if (role
== PORT_DES
&& (cp
== SUPERIOR
|| (cp
== SAME
&& ct
== false))) {
1095 return SUPERIOR_DESIGNATED_INFO
;
1097 /* Returns RepeatedDesignatedInfo if:
1098 * b) The received message conveys Designated Port Role, and a message
1099 * priority vector and timer parameters that are the same as the
1100 * Port's port priority vector or timer values. */
1101 } else if (role
== PORT_DES
&& cp
== SAME
&& ct
== true) {
1102 return REPEATED_DESIGNATED_INFO
;
1104 /* Returns InferiorDesignatedInfo if:
1105 * c) The received message conveys a Designated Port Role, and a
1106 * message priority vector that is worse than the Port's port
1107 * priority vector. */
1108 } else if (role
== PORT_DES
&& cp
== INFERIOR
) {
1109 return INFERIOR_DESIGNATED_INFO
;
1111 /* Returns InferiorRootAlternateInfo if:
1112 * d) The received message conveys a Root Port, Alternate Port, or
1113 * Backup Port Role and a message priority that is the same as or
1114 * worse than the port priority vector. */
1115 } else if ((role
== PORT_ROOT
|| role
== PORT_ALT_BACK
) &&
1116 (cp
== INFERIOR
|| cp
== SAME
)) {
1117 return INFERIOR_ROOT_ALTERNATE_INFO
;
1119 /* Otherwise, returns OtherInfo. */
1126 better_or_same_info(struct rstp_port
*p
, int new_info_is
)
1127 OVS_REQUIRES(rstp_mutex
)
1130 (new_info_is
== RECEIVED
&& p
->info_is
== INFO_IS_RECEIVED
1131 && compare_rstp_priority_vectors(&p
->msg_priority
,
1133 || (new_info_is
== MINE
&& p
->info_is
== INFO_IS_MINE
1134 && compare_rstp_priority_vectors(&p
->designated_priority_vector
,
1135 &p
->port_priority
));
1139 port_information_sm(struct rstp_port
*p
)
1140 OVS_REQUIRES(rstp_mutex
)
1142 enum port_information_state_machine old_state
;
1144 struct rstp_port
*p1
;
1146 old_state
= p
->port_information_sm_state
;
1149 switch (p
->port_information_sm_state
) {
1150 case PORT_INFORMATION_SM_INIT
:
1152 || (!p
->port_enabled
&& p
->info_is
!= INFO_IS_DISABLED
)) {
1153 p
->port_information_sm_state
= PORT_INFORMATION_SM_DISABLED_EXEC
;
1156 case PORT_INFORMATION_SM_DISABLED_EXEC
:
1157 p
->rcvd_msg
= false;
1158 p
->proposing
= p
->proposed
= p
->agree
= p
->agreed
= false;
1159 p
->rcvd_info_while
= 0;
1160 p
->info_is
= INFO_IS_DISABLED
;
1162 p
->selected
= false;
1163 p
->port_information_sm_state
= PORT_INFORMATION_SM_DISABLED
;
1165 case PORT_INFORMATION_SM_DISABLED
:
1166 if (!p
->port_enabled
&& p
->info_is
!= INFO_IS_DISABLED
) {
1167 /* Global transition. */
1168 p
->port_information_sm_state
= PORT_INFORMATION_SM_DISABLED_EXEC
;
1169 } else if (p
->port_enabled
) {
1170 p
->port_information_sm_state
= PORT_INFORMATION_SM_AGED_EXEC
;
1171 } else if (p
->rcvd_msg
) {
1172 p
->port_information_sm_state
= PORT_INFORMATION_SM_DISABLED_EXEC
;
1175 case PORT_INFORMATION_SM_AGED_EXEC
:
1176 p
->info_is
= INFO_IS_AGED
;
1178 p
->selected
= false;
1179 p
->port_information_sm_state
= PORT_INFORMATION_SM_AGED
;
1181 case PORT_INFORMATION_SM_AGED
:
1182 if (!p
->port_enabled
&& p
->info_is
!= INFO_IS_DISABLED
) {
1183 /* Global transition. */
1184 p
->port_information_sm_state
= PORT_INFORMATION_SM_DISABLED_EXEC
;
1185 } else if (p
->selected
&& p
->updt_info
) {
1186 p
->port_information_sm_state
= PORT_INFORMATION_SM_UPDATE_EXEC
;
1189 case PORT_INFORMATION_SM_UPDATE_EXEC
:
1190 p
->proposing
= p
->proposed
= false;
1191 /* MINE is not specified in Standard 802.1D-2004. */
1192 p
->agreed
= p
->agreed
&& better_or_same_info(p
, MINE
);
1193 p
->synced
= p
->synced
&& p
->agreed
;
1194 p
->port_priority
.root_bridge_id
=
1195 p
->designated_priority_vector
.root_bridge_id
;
1196 p
->port_priority
.root_path_cost
=
1197 p
->designated_priority_vector
.root_path_cost
;
1198 p
->port_priority
.designated_bridge_id
=
1199 p
->designated_priority_vector
.designated_bridge_id
;
1200 p
->port_priority
.designated_port_id
=
1201 p
->designated_priority_vector
.designated_port_id
;
1202 p
->port_times
= p
->designated_times
;
1203 p
->updt_info
= false;
1204 p
->info_is
= INFO_IS_MINE
;
1206 p
->port_information_sm_state
= PORT_INFORMATION_SM_UPDATE
;
1208 case PORT_INFORMATION_SM_UPDATE
:
1209 if (!p
->port_enabled
&& p
->info_is
!= INFO_IS_DISABLED
) {
1210 /* Global transition. */
1211 p
->port_information_sm_state
= PORT_INFORMATION_SM_DISABLED_EXEC
;
1213 p
->port_information_sm_state
= PORT_INFORMATION_SM_CURRENT_EXEC
;
1216 case PORT_INFORMATION_SM_CURRENT_EXEC
:
1217 p
->port_information_sm_state
= PORT_INFORMATION_SM_CURRENT
;
1219 case PORT_INFORMATION_SM_CURRENT
:
1220 if (!p
->port_enabled
&& p
->info_is
!= INFO_IS_DISABLED
) {
1221 /* Global transition. */
1222 p
->port_information_sm_state
= PORT_INFORMATION_SM_DISABLED_EXEC
;
1223 } else if (p
->rcvd_msg
&& !p
->updt_info
) {
1224 p
->port_information_sm_state
= PORT_INFORMATION_SM_RECEIVE_EXEC
;
1225 } else if (p
->selected
&& p
->updt_info
) {
1226 p
->port_information_sm_state
= PORT_INFORMATION_SM_UPDATE_EXEC
;
1227 } else if ((p
->info_is
== INFO_IS_RECEIVED
) &&
1228 (p
->rcvd_info_while
== 0) && !p
->updt_info
&&
1230 p
->port_information_sm_state
= PORT_INFORMATION_SM_AGED_EXEC
;
1233 case PORT_INFORMATION_SM_RECEIVE_EXEC
:
1234 p
->rcvd_info
= rcv_info(p
);
1235 p
->port_information_sm_state
= PORT_INFORMATION_SM_RECEIVE
;
1237 case PORT_INFORMATION_SM_RECEIVE
:
1238 if (!p
->port_enabled
&& p
->info_is
!= INFO_IS_DISABLED
) {
1239 /* Global transition. */
1240 p
->port_information_sm_state
= PORT_INFORMATION_SM_DISABLED_EXEC
;
1242 switch (p
->rcvd_info
) {
1243 case SUPERIOR_DESIGNATED_INFO
:
1244 /* 802.1q-2008 has a checkBPDUConsistency() function, called on
1245 * a BPDU reception. checkBPDUConsistency() clears the agreed
1246 * variable if the received message priority vector is superior
1247 * to the port priority vector, the BPDU is an ST BPDU or an
1248 * RST BPDU, its port role is Designated and its Learning flag
1250 if (p
->received_bpdu_buffer
.flags
& BPDU_FLAG_LEARNING
) {
1251 HMAP_FOR_EACH (p1
, node
, &r
->ports
) {
1252 if (p1
->port_number
!= p
->port_number
) {
1257 p
->port_information_sm_state
=
1258 PORT_INFORMATION_SM_SUPERIOR_DESIGNATED_EXEC
;
1260 case REPEATED_DESIGNATED_INFO
:
1261 p
->port_information_sm_state
=
1262 PORT_INFORMATION_SM_REPEATED_DESIGNATED_EXEC
;
1264 case INFERIOR_DESIGNATED_INFO
:
1265 p
->port_information_sm_state
=
1266 PORT_INFORMATION_SM_INFERIOR_DESIGNATED_EXEC
;
1268 case INFERIOR_ROOT_ALTERNATE_INFO
:
1269 p
->port_information_sm_state
=
1270 PORT_INFORMATION_SM_NOT_DESIGNATED_EXEC
;
1273 p
->port_information_sm_state
= PORT_INFORMATION_SM_OTHER_EXEC
;
1281 case PORT_INFORMATION_SM_OTHER_EXEC
:
1282 p
->rcvd_msg
= false;
1283 p
->port_information_sm_state
= PORT_INFORMATION_SM_OTHER
;
1285 case PORT_INFORMATION_SM_OTHER
:
1286 if (!p
->port_enabled
&& p
->info_is
!= INFO_IS_DISABLED
) {
1287 /* Global transition. */
1288 p
->port_information_sm_state
= PORT_INFORMATION_SM_DISABLED_EXEC
;
1290 p
->port_information_sm_state
= PORT_INFORMATION_SM_CURRENT_EXEC
;
1293 case PORT_INFORMATION_SM_NOT_DESIGNATED_EXEC
:
1294 record_agreement(p
);
1296 p
->rcvd_msg
= false;
1297 p
->port_information_sm_state
= PORT_INFORMATION_SM_NOT_DESIGNATED
;
1299 case PORT_INFORMATION_SM_NOT_DESIGNATED
:
1300 if (!p
->port_enabled
&& p
->info_is
!= INFO_IS_DISABLED
) {
1301 /* Global transition. */
1302 p
->port_information_sm_state
= PORT_INFORMATION_SM_DISABLED_EXEC
;
1304 p
->port_information_sm_state
= PORT_INFORMATION_SM_CURRENT_EXEC
;
1307 case PORT_INFORMATION_SM_INFERIOR_DESIGNATED_EXEC
:
1309 p
->rcvd_msg
= false;
1310 p
->port_information_sm_state
= PORT_INFORMATION_SM_INFERIOR_DESIGNATED
;
1312 case PORT_INFORMATION_SM_INFERIOR_DESIGNATED
:
1313 if (!p
->port_enabled
&& p
->info_is
!= INFO_IS_DISABLED
) {
1314 /* Global transition. */
1315 p
->port_information_sm_state
= PORT_INFORMATION_SM_DISABLED_EXEC
;
1317 p
->port_information_sm_state
= PORT_INFORMATION_SM_CURRENT_EXEC
;
1320 case PORT_INFORMATION_SM_REPEATED_DESIGNATED_EXEC
:
1323 /* This record_agreement() is missing in 802.1D-2004, but it's present
1324 * in 802.1q-2008. */
1325 record_agreement(p
);
1326 updt_rcvd_info_while(p
);
1327 p
->rcvd_msg
= false;
1328 p
->port_information_sm_state
= PORT_INFORMATION_SM_REPEATED_DESIGNATED
;
1330 case PORT_INFORMATION_SM_REPEATED_DESIGNATED
:
1331 if (!p
->port_enabled
&& p
->info_is
!= INFO_IS_DISABLED
) {
1332 /* Global transition. */
1333 p
->port_information_sm_state
= PORT_INFORMATION_SM_DISABLED_EXEC
;
1335 p
->port_information_sm_state
= PORT_INFORMATION_SM_CURRENT_EXEC
;
1338 case PORT_INFORMATION_SM_SUPERIOR_DESIGNATED_EXEC
:
1339 p
->agreed
= p
->proposing
= false;
1342 /* RECEIVED is not specified in Standard 802.1D-2004. */
1343 p
->agree
= p
->agree
&& better_or_same_info(p
, RECEIVED
);
1344 /* This record_agreement() and the synced assignment are missing in
1345 * 802.1D-2004, but they're present in 802.1q-2008. */
1346 record_agreement(p
);
1347 p
->synced
= p
->synced
&& p
->agreed
;
1350 updt_rcvd_info_while(p
);
1351 p
->info_is
= INFO_IS_RECEIVED
;
1353 p
->selected
= false;
1354 p
->rcvd_msg
= false;
1355 p
->port_information_sm_state
= PORT_INFORMATION_SM_SUPERIOR_DESIGNATED
;
1357 case PORT_INFORMATION_SM_SUPERIOR_DESIGNATED
:
1358 if (!p
->port_enabled
&& p
->info_is
!= INFO_IS_DISABLED
) {
1359 /* Global transition. */
1360 p
->port_information_sm_state
= PORT_INFORMATION_SM_DISABLED_EXEC
;
1362 p
->port_information_sm_state
= PORT_INFORMATION_SM_CURRENT_EXEC
;
1369 if (old_state
!= p
->port_information_sm_state
) {
1371 VLOG_DBG("%s, port %u: Port_information_sm %d -> %d", p
->rstp
->name
,
1372 p
->port_number
, old_state
, p
->port_information_sm_state
);
1377 /* [17.29 Port Role Transitions state machine] */
1380 set_re_root_tree(struct rstp_port
*p
)
1381 OVS_REQUIRES(rstp_mutex
)
1384 struct rstp_port
*p1
;
1387 HMAP_FOR_EACH (p1
, node
, &r
->ports
) {
1393 set_sync_tree(struct rstp_port
*p
)
1394 OVS_REQUIRES(rstp_mutex
)
1397 struct rstp_port
*p1
;
1400 HMAP_FOR_EACH (p1
, node
, &r
->ports
) {
1406 hello_time(struct rstp_port
*p
)
1407 OVS_REQUIRES(rstp_mutex
)
1409 return p
->designated_times
.hello_time
;
1413 fwd_delay(struct rstp_port
*p
)
1414 OVS_REQUIRES(rstp_mutex
)
1416 return p
->designated_times
.forward_delay
;
1420 forward_delay(struct rstp_port
*p
)
1421 OVS_REQUIRES(rstp_mutex
)
1424 return hello_time(p
);
1426 return fwd_delay(p
);
1431 edge_delay(struct rstp_port
*p
)
1432 OVS_REQUIRES(rstp_mutex
)
1437 if (p
->oper_point_to_point_mac
== 1) {
1438 return r
->migrate_time
;
1440 return p
->designated_times
.max_age
;
1445 check_selected_role_change(struct rstp_port
*p
, int current_role_state
)
1446 OVS_REQUIRES(rstp_mutex
)
1448 if (p
->selected
&& !p
->updt_info
&& p
->role
!= p
->selected_role
1449 && p
->selected_role
!= current_role_state
) {
1450 VLOG_DBG("%s, port %u: case: current = %s role = %s selected = %d",
1451 p
->rstp
->name
, p
->port_number
,
1452 rstp_port_role_name(current_role_state
),
1453 rstp_port_role_name(p
->role
), p
->selected_role
);
1454 switch (p
->selected_role
) {
1456 p
->port_role_transition_sm_state
=
1457 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC
;
1459 case ROLE_DESIGNATED
:
1460 p
->port_role_transition_sm_state
=
1461 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC
;
1463 case ROLE_ALTERNATE
:
1464 p
->port_role_transition_sm_state
=
1465 PORT_ROLE_TRANSITION_SM_BLOCK_PORT_EXEC
;
1468 p
->port_role_transition_sm_state
=
1469 PORT_ROLE_TRANSITION_SM_BLOCK_PORT_EXEC
;
1472 p
->port_role_transition_sm_state
=
1473 PORT_ROLE_TRANSITION_SM_DISABLE_PORT_EXEC
;
1481 re_rooted(struct rstp_port
*p
)
1482 OVS_REQUIRES(rstp_mutex
)
1485 struct rstp_port
*p1
;
1488 HMAP_FOR_EACH (p1
, node
, &r
->ports
) {
1489 if ((p1
!= p
) && (p1
->rr_while
!= 0)) {
1497 all_synced(struct rstp
*r
)
1498 OVS_REQUIRES(rstp_mutex
)
1500 struct rstp_port
*p
;
1502 HMAP_FOR_EACH (p
, node
, &r
->ports
) {
1503 if (!(p
->selected
&& p
->role
== p
->selected_role
&&
1504 (p
->role
== ROLE_ROOT
|| p
->synced
== true))) {
1512 port_role_transition_sm(struct rstp_port
*p
)
1513 OVS_REQUIRES(rstp_mutex
)
1515 enum port_role_transition_state_machine old_state
;
1517 enum rstp_port_role last_role
;
1519 old_state
= p
->port_role_transition_sm_state
;
1521 last_role
= p
->role
;
1523 switch (p
->port_role_transition_sm_state
) {
1524 case PORT_ROLE_TRANSITION_SM_INIT
:
1526 p
->port_role_transition_sm_state
=
1527 PORT_ROLE_TRANSITION_SM_INIT_PORT_EXEC
;
1530 case PORT_ROLE_TRANSITION_SM_INIT_PORT_EXEC
:
1531 p
->role
= ROLE_DISABLED
;
1532 p
->learn
= p
->forward
= false;
1534 p
->sync
= p
->re_root
= true;
1535 p
->rr_while
= p
->designated_times
.forward_delay
;
1536 p
->fd_while
= p
->designated_times
.max_age
;
1538 p
->port_role_transition_sm_state
=
1539 PORT_ROLE_TRANSITION_SM_DISABLE_PORT_EXEC
;
1541 case PORT_ROLE_TRANSITION_SM_DISABLE_PORT_EXEC
:
1542 p
->role
= p
->selected_role
;
1543 p
->learn
= p
->forward
= false;
1544 p
->port_role_transition_sm_state
=
1545 PORT_ROLE_TRANSITION_SM_DISABLE_PORT
;
1547 case PORT_ROLE_TRANSITION_SM_DISABLE_PORT
:
1548 if (check_selected_role_change(p
, ROLE_DISABLED
)) {
1549 /* Global transition. */
1550 } else if (p
->selected
&& !p
->updt_info
&& !p
->learning
1551 && !p
->forwarding
) {
1552 p
->port_role_transition_sm_state
=
1553 PORT_ROLE_TRANSITION_SM_DISABLED_PORT_EXEC
;
1556 case PORT_ROLE_TRANSITION_SM_DISABLED_PORT_EXEC
:
1557 p
->fd_while
= p
->designated_times
.max_age
;
1560 p
->sync
= p
->re_root
= false;
1561 p
->port_role_transition_sm_state
=
1562 PORT_ROLE_TRANSITION_SM_DISABLED_PORT
;
1564 case PORT_ROLE_TRANSITION_SM_DISABLED_PORT
:
1565 if (check_selected_role_change(p
, ROLE_DISABLED
)) {
1566 /* Global transition. */
1567 } else if (p
->selected
&& !p
->updt_info
1568 && (p
->fd_while
!= p
->designated_times
.max_age
|| p
->sync
1569 || p
->re_root
|| !p
->synced
)) {
1570 p
->port_role_transition_sm_state
=
1571 PORT_ROLE_TRANSITION_SM_DISABLED_PORT_EXEC
;
1574 case PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC
:
1575 p
->role
= ROLE_ROOT
;
1576 p
->rr_while
= p
->designated_times
.forward_delay
;
1577 p
->port_role_transition_sm_state
= PORT_ROLE_TRANSITION_SM_ROOT_PORT
;
1579 case PORT_ROLE_TRANSITION_SM_ROOT_PORT
:
1580 if (check_selected_role_change(p
, ROLE_ROOT
)) {
1581 /* Global transition. */
1582 } else if (p
->selected
&& !p
->updt_info
) {
1583 if (p
->rr_while
!= p
->designated_times
.forward_delay
) {
1584 p
->port_role_transition_sm_state
=
1585 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC
;
1587 } else if (p
->re_root
&& p
->forward
) {
1588 p
->port_role_transition_sm_state
=
1589 PORT_ROLE_TRANSITION_SM_REROOTED_EXEC
;
1591 } else if ((p
->fd_while
== 0
1592 || ((re_rooted(p
) && p
->rb_while
== 0)
1593 && r
->rstp_version
)) && !p
->learn
) {
1594 p
->port_role_transition_sm_state
=
1595 PORT_ROLE_TRANSITION_SM_ROOT_LEARN_EXEC
;
1597 } else if ((p
->fd_while
== 0
1598 || ((re_rooted(p
) && p
->rb_while
== 0)
1599 && r
->rstp_version
)) && p
->learn
&& !p
->forward
) {
1600 p
->port_role_transition_sm_state
=
1601 PORT_ROLE_TRANSITION_SM_ROOT_FORWARD_EXEC
;
1603 } else if (p
->proposed
&& !p
->agree
) {
1604 p
->port_role_transition_sm_state
=
1605 PORT_ROLE_TRANSITION_SM_ROOT_PROPOSED_EXEC
;
1607 } else if ((all_synced(r
) && !p
->agree
) ||
1608 (p
->proposed
&& p
->agree
)) {
1609 p
->port_role_transition_sm_state
=
1610 PORT_ROLE_TRANSITION_SM_ROOT_AGREED_EXEC
;
1612 } else if (!p
->forward
&& !p
->re_root
) {
1613 p
->port_role_transition_sm_state
=
1614 PORT_ROLE_TRANSITION_SM_REROOT_EXEC
;
1619 case PORT_ROLE_TRANSITION_SM_REROOT_EXEC
:
1620 if (check_selected_role_change(p
, ROLE_ROOT
)) {
1621 /* Global transition. */
1623 set_re_root_tree(p
);
1624 p
->port_role_transition_sm_state
=
1625 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC
;
1628 case PORT_ROLE_TRANSITION_SM_ROOT_AGREED_EXEC
:
1629 if (check_selected_role_change(p
, ROLE_ROOT
)) {
1630 /* Global transition. */
1632 p
->proposed
= p
->sync
= false;
1633 p
->agree
= p
->new_info
= true;
1634 p
->port_role_transition_sm_state
=
1635 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC
;
1638 case PORT_ROLE_TRANSITION_SM_ROOT_PROPOSED_EXEC
:
1640 p
->proposed
= false;
1641 if (check_selected_role_change(p
, ROLE_ROOT
)) {
1642 /* Global transition. */
1644 p
->port_role_transition_sm_state
=
1645 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC
;
1648 case PORT_ROLE_TRANSITION_SM_ROOT_FORWARD_EXEC
:
1651 if (check_selected_role_change(p
, ROLE_ROOT
)) {
1652 /* Global transition. */
1654 p
->port_role_transition_sm_state
=
1655 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC
;
1658 case PORT_ROLE_TRANSITION_SM_ROOT_LEARN_EXEC
:
1659 p
->fd_while
= forward_delay(p
);
1661 if (check_selected_role_change(p
, ROLE_ROOT
)) {
1662 /* Global transition. */
1664 p
->port_role_transition_sm_state
=
1665 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC
;
1668 case PORT_ROLE_TRANSITION_SM_REROOTED_EXEC
:
1670 if (check_selected_role_change(p
, ROLE_ROOT
)) {
1671 /* Global transition. */
1673 p
->port_role_transition_sm_state
=
1674 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC
;
1677 case PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC
:
1678 p
->role
= ROLE_DESIGNATED
;
1679 p
->port_role_transition_sm_state
=
1680 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT
;
1682 case PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT
:
1683 if (check_selected_role_change(p
, ROLE_DESIGNATED
)) {
1684 /* Global transition. */
1685 } else if (p
->selected
&& !p
->updt_info
) {
1686 if (((p
->sync
&& !p
->synced
)
1687 || (p
->re_root
&& p
->rr_while
!= 0) || p
->disputed
)
1688 && !p
->oper_edge
&& (p
->learn
|| p
->forward
)) {
1689 p
->port_role_transition_sm_state
=
1690 PORT_ROLE_TRANSITION_SM_DESIGNATED_DISCARD_EXEC
;
1691 } else if ((p
->fd_while
== 0 || p
->agreed
|| p
->oper_edge
)
1692 && (p
->rr_while
== 0 || !p
->re_root
)
1693 && !p
->sync
&& !p
->learn
) {
1694 p
->port_role_transition_sm_state
=
1695 PORT_ROLE_TRANSITION_SM_DESIGNATED_LEARN_EXEC
;
1696 } else if ((p
->fd_while
== 0 || p
->agreed
|| p
->oper_edge
)
1697 && (p
->rr_while
== 0 || !p
->re_root
)
1698 && !p
->sync
&& (p
->learn
&& !p
->forward
)) {
1699 p
->port_role_transition_sm_state
=
1700 PORT_ROLE_TRANSITION_SM_DESIGNATED_FORWARD_EXEC
;
1701 } else if (!p
->forward
&& !p
->agreed
&& !p
->proposing
&&
1703 p
->port_role_transition_sm_state
=
1704 PORT_ROLE_TRANSITION_SM_DESIGNATED_PROPOSE_EXEC
;
1705 } else if ((!p
->learning
&& !p
->forwarding
&& !p
->synced
)
1706 || (p
->agreed
&& !p
->synced
)
1707 || (p
->oper_edge
&& !p
->synced
)
1708 || (p
->sync
&& p
->synced
)) {
1709 p
->port_role_transition_sm_state
=
1710 PORT_ROLE_TRANSITION_SM_DESIGNATED_SYNCED_EXEC
;
1711 } else if (p
->rr_while
== 0 && p
->re_root
) {
1712 p
->port_role_transition_sm_state
=
1713 PORT_ROLE_TRANSITION_SM_DESIGNATED_RETIRED_EXEC
;
1717 case PORT_ROLE_TRANSITION_SM_DESIGNATED_RETIRED_EXEC
:
1719 if (check_selected_role_change(p
, ROLE_DESIGNATED
)) {
1720 /* Global transition. */
1722 p
->port_role_transition_sm_state
=
1723 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC
;
1726 case PORT_ROLE_TRANSITION_SM_DESIGNATED_SYNCED_EXEC
:
1730 if (check_selected_role_change(p
, ROLE_DESIGNATED
)) {
1731 /* Global transition. */
1733 p
->port_role_transition_sm_state
=
1734 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC
;
1737 case PORT_ROLE_TRANSITION_SM_DESIGNATED_PROPOSE_EXEC
:
1738 p
->proposing
= true;
1739 p
->edge_delay_while
= edge_delay(p
);
1741 if (check_selected_role_change(p
, ROLE_DESIGNATED
)) {
1742 /* Global transition. */
1744 p
->port_role_transition_sm_state
=
1745 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC
;
1748 case PORT_ROLE_TRANSITION_SM_DESIGNATED_FORWARD_EXEC
:
1751 p
->agreed
= p
->send_rstp
;
1752 if (check_selected_role_change(p
, ROLE_DESIGNATED
)) {
1753 /* Global transition. */
1755 p
->port_role_transition_sm_state
=
1756 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC
;
1759 case PORT_ROLE_TRANSITION_SM_DESIGNATED_LEARN_EXEC
:
1761 p
->fd_while
= forward_delay(p
);
1762 if (check_selected_role_change(p
, ROLE_DESIGNATED
)) {
1763 /* Global transition. */
1765 p
->port_role_transition_sm_state
=
1766 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC
;
1769 case PORT_ROLE_TRANSITION_SM_DESIGNATED_DISCARD_EXEC
:
1770 p
->learn
= p
->forward
= p
->disputed
= false;
1771 p
->fd_while
= forward_delay(p
);
1772 if (check_selected_role_change(p
, ROLE_DESIGNATED
)) {
1773 /* Global transition. */
1775 p
->port_role_transition_sm_state
=
1776 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC
;
1779 case PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC
:
1780 p
->fd_while
= p
->designated_times
.forward_delay
;
1783 p
->sync
= p
->re_root
= false;
1784 p
->port_role_transition_sm_state
=
1785 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT
;
1787 case PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT
:
1788 if (check_selected_role_change(p
, ROLE_ALTERNATE
)) {
1789 /* Global transition. */
1790 } else if (p
->selected
&& !p
->updt_info
) {
1791 if (p
->rb_while
!= 2 * p
->designated_times
.hello_time
1792 && p
->role
== ROLE_BACKUP
) {
1793 p
->port_role_transition_sm_state
=
1794 PORT_ROLE_TRANSITION_SM_BACKUP_PORT_EXEC
;
1795 } else if ((p
->fd_while
!= forward_delay(p
)) || p
->sync
1796 || p
->re_root
|| !p
->synced
) {
1797 p
->port_role_transition_sm_state
=
1798 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC
;
1799 } else if (p
->proposed
&& !p
->agree
) {
1800 p
->port_role_transition_sm_state
=
1801 PORT_ROLE_TRANSITION_SM_ALTERNATE_PROPOSED_EXEC
;
1802 } else if ((all_synced(r
) && !p
->agree
)
1803 || (p
->proposed
&& p
->agree
)) {
1804 p
->port_role_transition_sm_state
=
1805 PORT_ROLE_TRANSITION_SM_ALTERNATE_AGREED_EXEC
;
1809 case PORT_ROLE_TRANSITION_SM_ALTERNATE_AGREED_EXEC
:
1810 p
->proposed
= false;
1813 if (check_selected_role_change(p
, ROLE_ALTERNATE
)) {
1814 /* Global transition. */
1816 p
->port_role_transition_sm_state
=
1817 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC
;
1820 case PORT_ROLE_TRANSITION_SM_ALTERNATE_PROPOSED_EXEC
:
1822 p
->proposed
= false;
1823 if (check_selected_role_change(p
, ROLE_ALTERNATE
)) {
1824 /* Global transition. */
1826 p
->port_role_transition_sm_state
=
1827 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC
;
1830 case PORT_ROLE_TRANSITION_SM_BLOCK_PORT_EXEC
:
1831 p
->role
= p
->selected_role
;
1832 p
->learn
= p
->forward
= false;
1833 p
->port_role_transition_sm_state
= PORT_ROLE_TRANSITION_SM_BLOCK_PORT
;
1835 case PORT_ROLE_TRANSITION_SM_BLOCK_PORT
:
1836 if (check_selected_role_change(p
, ROLE_ALTERNATE
)) {
1837 /* Global transition. */
1838 } else if (p
->selected
&& !p
->updt_info
&& !p
->learning
&&
1840 p
->port_role_transition_sm_state
=
1841 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC
;
1844 case PORT_ROLE_TRANSITION_SM_BACKUP_PORT_EXEC
:
1845 p
->rb_while
= 2 * p
->designated_times
.hello_time
;
1846 if (check_selected_role_change(p
, ROLE_ALTERNATE
)) {
1847 /* Global transition. */
1849 p
->port_role_transition_sm_state
=
1850 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC
;
1857 if (old_state
!= p
->port_role_transition_sm_state
) {
1859 VLOG_DBG("%s, port %u: Port_role_transition_sm %d -> %d",
1860 p
->rstp
->name
, p
->port_number
, old_state
,
1861 p
->port_role_transition_sm_state
);
1863 if (last_role
!= p
->role
) {
1864 VLOG_DBG("%s, port %u, port role ["RSTP_PORT_ID_FMT
"] = %s",
1865 p
->rstp
->name
, p
->port_number
, p
->port_id
,
1866 rstp_port_role_name(p
->role
));
1871 /* [17.30 - Port state transition state machine] */
1874 enable_learning(struct rstp_port
*p
)
1875 OVS_REQUIRES(rstp_mutex
)
1877 /* [17.21.6 enableLearning()] An implementation dependent procedure that
1878 * causes the Learning Process (7.8) to start learning from frames received
1879 * on the Port. The procedure does not complete until learning has been
1882 rstp_port_set_state__(p
, RSTP_LEARNING
);
1886 enable_forwarding(struct rstp_port
*p
)
1887 OVS_REQUIRES(rstp_mutex
)
1889 /* [17.21.5 enableForwarding()] An implementation dependent procedure that
1890 * causes the Forwarding Process (7.7) to start forwarding frames through
1891 * the Port. The procedure does not complete until forwarding has been
1894 rstp_port_set_state__(p
, RSTP_FORWARDING
);
1898 disable_learning(struct rstp_port
*p
)
1899 OVS_REQUIRES(rstp_mutex
)
1901 /* [17.21.4 - disableLearning()] An implementation dependent procedure that
1902 * causes the Learning Process (7.8) to stop learning from the source
1903 * address of frames received on the Port. The procedure does not complete
1904 * until learning has stopped.
1906 rstp_port_set_state__(p
, RSTP_DISCARDING
);
1910 disable_forwarding(struct rstp_port
*p
)
1911 OVS_REQUIRES(rstp_mutex
)
1913 /* [17.21.3 - disableForwarding()] An implementation dependent procedure
1914 * that causes the Forwarding Process (7.7) to stop forwarding frames
1915 * through the Port. The procedure does not complete until forwarding has
1918 rstp_port_set_state__(p
, RSTP_DISCARDING
);
1922 port_state_transition_sm(struct rstp_port
*p
)
1923 OVS_REQUIRES(rstp_mutex
)
1925 enum port_state_transition_state_machine old_state
;
1928 old_state
= p
->port_state_transition_sm_state
;
1931 switch (p
->port_state_transition_sm_state
) {
1932 case PORT_STATE_TRANSITION_SM_INIT
:
1934 p
->port_state_transition_sm_state
=
1935 PORT_STATE_TRANSITION_SM_DISCARDING_EXEC
;
1938 case PORT_STATE_TRANSITION_SM_DISCARDING_EXEC
:
1939 disable_learning(p
);
1940 p
->learning
= false;
1941 disable_forwarding(p
);
1942 p
->forwarding
= false;
1943 p
->port_state_transition_sm_state
=
1944 PORT_STATE_TRANSITION_SM_DISCARDING
;
1946 case PORT_STATE_TRANSITION_SM_DISCARDING
:
1948 p
->port_state_transition_sm_state
=
1949 PORT_STATE_TRANSITION_SM_LEARNING_EXEC
;
1952 case PORT_STATE_TRANSITION_SM_LEARNING_EXEC
:
1955 p
->port_state_transition_sm_state
= PORT_STATE_TRANSITION_SM_LEARNING
;
1957 case PORT_STATE_TRANSITION_SM_LEARNING
:
1959 p
->port_state_transition_sm_state
=
1960 PORT_STATE_TRANSITION_SM_DISCARDING_EXEC
;
1961 } else if (p
->forward
) {
1962 p
->port_state_transition_sm_state
=
1963 PORT_STATE_TRANSITION_SM_FORWARDING_EXEC
;
1966 case PORT_STATE_TRANSITION_SM_FORWARDING_EXEC
:
1967 enable_forwarding(p
);
1968 p
->forwarding
= true;
1969 p
->port_state_transition_sm_state
=
1970 PORT_STATE_TRANSITION_SM_FORWARDING
;
1972 case PORT_STATE_TRANSITION_SM_FORWARDING
:
1974 p
->port_state_transition_sm_state
=
1975 PORT_STATE_TRANSITION_SM_DISCARDING_EXEC
;
1982 if (old_state
!= p
->port_state_transition_sm_state
) {
1984 VLOG_DBG("%s, port %u: Port_state_transition_sm %d -> %d",
1985 p
->rstp
->name
, p
->port_number
, old_state
,
1986 p
->port_state_transition_sm_state
);
1991 /* [17.31 - Topology Change state machine] */
1994 new_tc_while(struct rstp_port
*p
)
1995 OVS_REQUIRES(rstp_mutex
)
2000 if (p
->tc_while
== 0 && p
->send_rstp
== true) {
2001 p
->tc_while
= r
->bridge_hello_time
+ 1;
2003 } else if (p
->tc_while
== 0 && p
->send_rstp
== false) {
2004 p
->tc_while
= r
->bridge_max_age
+ r
->bridge_forward_delay
;
2008 /* [17.21.18 setTcPropTree()]
2009 * Sets tcprop for all Ports except the Port that called the procedure.
2012 set_tc_prop_tree(struct rstp_port
*p
)
2013 OVS_REQUIRES(rstp_mutex
)
2016 struct rstp_port
*p1
;
2019 HMAP_FOR_EACH (p1
, node
, &r
->ports
) {
2020 /* Set tc_prop on every port, except the one calling this
2022 if (p1
->port_number
!= p
->port_number
) {
2029 set_tc_prop_bridge(struct rstp_port
*p
) /* not specified in 802.1D-2004. */
2030 OVS_REQUIRES(rstp_mutex
)
2032 set_tc_prop_tree(p
); /* see 802.1w-2001. */
2036 topology_change_sm(struct rstp_port
*p
)
2037 OVS_REQUIRES(rstp_mutex
)
2039 enum topology_change_state_machine old_state
;
2042 old_state
= p
->topology_change_sm_state
;
2045 switch (p
->topology_change_sm_state
) {
2046 case TOPOLOGY_CHANGE_SM_INIT
:
2048 p
->topology_change_sm_state
= TOPOLOGY_CHANGE_SM_INACTIVE_EXEC
;
2051 case TOPOLOGY_CHANGE_SM_INACTIVE_EXEC
:
2052 p
->fdb_flush
= true;
2055 p
->topology_change_sm_state
= TOPOLOGY_CHANGE_SM_INACTIVE
;
2057 case TOPOLOGY_CHANGE_SM_INACTIVE
:
2058 if (p
->learn
&& !p
->fdb_flush
) {
2059 p
->topology_change_sm_state
= TOPOLOGY_CHANGE_SM_LEARNING_EXEC
;
2062 case TOPOLOGY_CHANGE_SM_LEARNING_EXEC
:
2063 p
->rcvd_tc
= p
->rcvd_tcn
= p
->rcvd_tc_ack
= false;
2064 p
->tc_prop
= p
->rcvd_tc_ack
= false;
2065 p
->topology_change_sm_state
= TOPOLOGY_CHANGE_SM_LEARNING
;
2067 case TOPOLOGY_CHANGE_SM_LEARNING
:
2068 if (p
->role
!= ROLE_ROOT
&& p
->role
!= ROLE_DESIGNATED
&&
2069 !(p
->learn
|| p
->learning
) && !(p
->rcvd_tc
|| p
->rcvd_tcn
||
2070 p
->rcvd_tc_ack
|| p
->tc_prop
)) {
2071 p
->topology_change_sm_state
= TOPOLOGY_CHANGE_SM_INACTIVE_EXEC
;
2072 } else if (p
->rcvd_tc
|| p
->rcvd_tcn
|| p
->rcvd_tc_ack
|| p
->tc_prop
) {
2073 p
->topology_change_sm_state
= TOPOLOGY_CHANGE_SM_LEARNING_EXEC
;
2074 } else if ((p
->role
== ROLE_ROOT
|| p
->role
== ROLE_DESIGNATED
)
2075 && p
->forward
&& !p
->oper_edge
) {
2076 p
->topology_change_sm_state
= TOPOLOGY_CHANGE_SM_DETECTED_EXEC
;
2079 case TOPOLOGY_CHANGE_SM_DETECTED_EXEC
:
2081 set_tc_prop_tree(p
);
2083 p
->topology_change_sm_state
= TOPOLOGY_CHANGE_SM_ACTIVE_EXEC
;
2085 case TOPOLOGY_CHANGE_SM_ACTIVE_EXEC
:
2086 p
->topology_change_sm_state
= TOPOLOGY_CHANGE_SM_ACTIVE
;
2088 case TOPOLOGY_CHANGE_SM_ACTIVE
:
2089 if ((p
->role
!= ROLE_ROOT
&& p
->role
!= ROLE_DESIGNATED
)
2091 p
->topology_change_sm_state
= TOPOLOGY_CHANGE_SM_LEARNING_EXEC
;
2092 } else if (p
->rcvd_tcn
) {
2093 p
->topology_change_sm_state
= TOPOLOGY_CHANGE_SM_NOTIFIED_TCN_EXEC
;
2094 } else if (p
->rcvd_tc
) {
2095 p
->topology_change_sm_state
= TOPOLOGY_CHANGE_SM_NOTIFIED_TC_EXEC
;
2096 } else if (p
->tc_prop
&& !p
->oper_edge
) {
2097 p
->topology_change_sm_state
= TOPOLOGY_CHANGE_SM_PROPAGATING_EXEC
;
2098 } else if (p
->rcvd_tc_ack
) {
2099 p
->topology_change_sm_state
= TOPOLOGY_CHANGE_SM_ACKNOWLEDGED_EXEC
;
2102 case TOPOLOGY_CHANGE_SM_ACKNOWLEDGED_EXEC
:
2104 p
->rcvd_tc_ack
= false;
2105 p
->topology_change_sm_state
= TOPOLOGY_CHANGE_SM_ACTIVE
;
2107 case TOPOLOGY_CHANGE_SM_PROPAGATING_EXEC
:
2109 p
->fdb_flush
= true;
2111 p
->topology_change_sm_state
= TOPOLOGY_CHANGE_SM_ACTIVE
;
2113 case TOPOLOGY_CHANGE_SM_NOTIFIED_TC_EXEC
:
2114 p
->rcvd_tcn
= p
->rcvd_tc
= false;
2115 if (p
->role
== ROLE_DESIGNATED
) {
2118 set_tc_prop_bridge(p
);
2119 p
->topology_change_sm_state
= TOPOLOGY_CHANGE_SM_ACTIVE
;
2121 case TOPOLOGY_CHANGE_SM_NOTIFIED_TCN_EXEC
:
2123 p
->topology_change_sm_state
= TOPOLOGY_CHANGE_SM_NOTIFIED_TC_EXEC
;
2129 if (old_state
!= p
->topology_change_sm_state
) {
2131 VLOG_DBG("%s, port %u: Topology_change_sm %d -> %d", p
->rstp
->name
,
2132 p
->port_number
, old_state
, p
->topology_change_sm_state
);
2137 /****************************************************************************
2138 * [17.6] Priority vector calculation helper functions
2139 ****************************************************************************/
2141 /* compare_rstp_priority_vectors() compares two struct rstp_priority_vectors
2142 * and returns a value indicating if the first rstp_priority_vector is
2143 * superior, same or inferior to the second one.
2145 * Zero return value indicates INFERIOR, a non-zero return value indicates
2146 * SUPERIOR. When it makes a difference the non-zero return value SAME
2147 * indicates the priority vectors are identical (a subset of SUPERIOR).
2149 static enum vector_comparison
2150 compare_rstp_priority_vectors(const struct rstp_priority_vector
*v1
,
2151 const struct rstp_priority_vector
*v2
)
2153 VLOG_DBG("v1: "RSTP_ID_FMT
", %u, "RSTP_ID_FMT
", %d, %d",
2154 RSTP_ID_ARGS(v1
->root_bridge_id
), v1
->root_path_cost
,
2155 RSTP_ID_ARGS(v1
->designated_bridge_id
), v1
->designated_port_id
,
2156 v1
->bridge_port_id
);
2157 VLOG_DBG("v2: "RSTP_ID_FMT
", %u, "RSTP_ID_FMT
", %d, %d",
2158 RSTP_ID_ARGS(v2
->root_bridge_id
), v2
->root_path_cost
,
2159 RSTP_ID_ARGS(v2
->designated_bridge_id
), v2
->designated_port_id
,
2160 v2
->bridge_port_id
);
2163 * This message priority vector is superior to the port priority vector and
2164 * will replace it if, and only if, the message priority vector is better
2165 * than the port priority vector, or the message has been transmitted from
2166 * the same Designated Bridge and Designated Port as the port priority
2167 * vector, i.e., if the following is true:
2169 * ((RD < RootBridgeID)) ||
2170 * ((RD == RootBridgeID) && (RPCD < RootPathCost)) ||
2171 * ((RD == RootBridgeID) && (RPCD == RootPathCost) &&
2172 * (D < designated_bridge_id)) ||
2173 * ((RD == RootBridgeID) && (RPCD == RootPathCost) &&
2174 * (D == designated_bridge_id) && (PD < designated_port_id)) ||
2175 * ((D == designated_bridge_id.BridgeAddress) &&
2176 * (PD == designated_port_id.PortNumber))
2178 if ((v1
->root_bridge_id
< v2
->root_bridge_id
)
2179 || (v1
->root_bridge_id
== v2
->root_bridge_id
2180 && v1
->root_path_cost
< v2
->root_path_cost
)
2181 || (v1
->root_bridge_id
== v2
->root_bridge_id
2182 && v1
->root_path_cost
== v2
->root_path_cost
2183 && v1
->designated_bridge_id
< v2
->designated_bridge_id
)
2184 || (v1
->root_bridge_id
== v2
->root_bridge_id
2185 && v1
->root_path_cost
== v2
->root_path_cost
2186 && v1
->designated_bridge_id
== v2
->designated_bridge_id
2187 && v1
->designated_port_id
< v2
->designated_port_id
)
2188 || (v1
->designated_bridge_id
== v2
->designated_bridge_id
2189 && v1
->designated_port_id
== v2
->designated_port_id
)) {
2190 /* SAME is a subset of SUPERIOR. */
2191 if (v1
->root_bridge_id
== v2
->root_bridge_id
2192 && v1
->root_path_cost
== v2
->root_path_cost
2193 && v1
->designated_bridge_id
== v2
->designated_bridge_id
2194 && v1
->designated_port_id
== v2
->designated_port_id
) {
2195 if (v1
->bridge_port_id
< v2
->bridge_port_id
) {
2196 VLOG_DBG("superior");
2199 else if (v1
->bridge_port_id
> v2
->bridge_port_id
) {
2200 VLOG_DBG("inferior");
2203 VLOG_DBG("superior_same");
2206 VLOG_DBG("superior");
2210 VLOG_DBG("inferior");
2215 rstp_times_equal(struct rstp_times
*t1
, struct rstp_times
*t2
)
2217 return t1
->forward_delay
== t2
->forward_delay
2218 && t1
->hello_time
== t2
->hello_time
2219 && t1
->max_age
== t2
->max_age
2220 && t1
->message_age
== t2
->message_age
;