]> git.proxmox.com Git - mirror_ovs.git/blame - lib/rstp-state-machines.c
projects / mirror_ovs.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
openflow: Table maintenance commands for Geneve options.
[mirror_ovs.git] / lib / rstp-state-machines.c
CommitLineData
9efd308e
DV		 1/*
2 * Copyright (c) 2011-2014 M3S, Srl - Italy
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at:
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17/*
18 * Rapid Spanning Tree Protocol (IEEE 802.1D-2004) state machines
19 * implementation.
20 *
21 * Authors:
22 * Martino Fornasa <mf@fornasa.it>
23 * Daniele Venturino <daniele.venturino@m3s.it>
24 *
25 * References to IEEE 802.1D-2004 standard are enclosed in square brackets.
26 * E.g. [17.3], [Table 17-1], etc.
27 *
28 */
29
30#include <config.h>
31#include "rstp.h"
32#include "rstp-state-machines.h"
33#include <arpa/inet.h>
34#include <inttypes.h>
35#include <netinet/in.h>
36#include <stdlib.h>
37#include <sys/types.h>
38#include "byte-order.h"
39#include "connectivity.h"
40#include "ofpbuf.h"
cf62fa4c 41#include "dp-packet.h"
9efd308e
DV		 42#include "packets.h"
43#include "seq.h"
44#include "unixctl.h"
45#include "util.h"
e6211adc 46#include "openvswitch/vlog.h"
9efd308e
DV		 47
48VLOG_DEFINE_THIS_MODULE(rstp_sm);
49
50#define ROLE_FLAG_MASK 0xC
51#define ROLE_FLAG_SHIFT 2
52
53enum port_flag {
54 PORT_UNKN = 0,
55 PORT_ALT_BACK = 1,
56 PORT_ROOT = 2,
57 PORT_DES = 3
58};
59
60enum bpdu_size {
61 CONFIGURATION_BPDU_SIZE = 35,
62 TOPOLOGY_CHANGE_NOTIFICATION_BPDU_SIZE = 4,
63 RAPID_SPANNING_TREE_BPDU_SIZE = 36
64};
65
a0478216
JR		 66/* Same is a subset of SUPERIOR, so can be used as a boolean when the
67 * distinction is not significant. */
9efd308e
DV		 68enum vector_comparison {
69 INFERIOR = 0,
70 SUPERIOR = 1,
71 SAME = 2
72};
73
74static void decrement_timer(uint16_t *);
f025bcb7
JR		 75static void rstp_send_bpdu(struct rstp_port *, const void *, size_t)
76 OVS_REQUIRES(rstp_mutex);
77static int validate_received_bpdu(struct rstp_port *, const void *, size_t)
78 OVS_REQUIRES(rstp_mutex);
9efd308e
DV		 79static ovs_be16 time_encode(uint8_t);
80static uint8_t time_decode(ovs_be16);
81static enum vector_comparison
a0478216
JR		 82compare_rstp_priority_vectors(const struct rstp_priority_vector *,
83 const struct rstp_priority_vector *);
9efd308e
DV		 84static bool rstp_times_equal(struct rstp_times *, struct rstp_times *);
85
86/* Per-Bridge State Machine */
f025bcb7
JR		 87static int port_role_selection_sm(struct rstp *)
88 OVS_REQUIRES(rstp_mutex);
9efd308e 89/* Per-Port State Machines */
f025bcb7
JR		 90static int port_receive_sm(struct rstp_port *)
91 OVS_REQUIRES(rstp_mutex);
92static int port_protocol_migration_sm(struct rstp_port *)
93 OVS_REQUIRES(rstp_mutex);
94static int bridge_detection_sm(struct rstp_port *)
95 OVS_REQUIRES(rstp_mutex);
96static int port_transmit_sm(struct rstp_port *)
97 OVS_REQUIRES(rstp_mutex);
98static int port_information_sm(struct rstp_port *)
99 OVS_REQUIRES(rstp_mutex);
100static int port_role_transition_sm(struct rstp_port *)
101 OVS_REQUIRES(rstp_mutex);
102static int port_state_transition_sm(struct rstp_port *)
103 OVS_REQUIRES(rstp_mutex);
104static int topology_change_sm(struct rstp_port *)
105 OVS_REQUIRES(rstp_mutex);
9efd308e
DV		 106/* port_timers_sm() not defined as a state machine */
107
108void
006f3386 109process_received_bpdu__(struct rstp_port *p, const void *bpdu_,
f025bcb7
JR		 110 size_t bpdu_size)
111 OVS_REQUIRES(rstp_mutex)
9efd308e 112{
006f3386
JR		 113 struct rstp *rstp = p->rstp;
114 struct rstp_bpdu *bpdu = (struct rstp_bpdu *)bpdu_;
9efd308e 115
311fb15b 116 if (!p->port_enabled) {
9efd308e 117 return;
311fb15b
JR		 118 }
119 if (p->rcvd_bpdu) {
9efd308e 120 return;
311fb15b 121 }
006f3386
JR		 122
123 /* [9.2.9 Encoding of Port Role values]
124 * NOTE. If the Unknown value of the Port Role parameter is received, the
125 * state machines will effectively treat the RST BPDU as if it were a
126 * Configuration BPDU.
127 */
128 if (bpdu->bpdu_type == RAPID_SPANNING_TREE_BPDU) {
129 uint8_t role = (bpdu->flags & ROLE_FLAG_MASK) >> ROLE_FLAG_SHIFT;
130
131 if (role == PORT_UNKN) {
132 bpdu->bpdu_type = CONFIGURATION_BPDU;
133 }
134 }
135
9efd308e
DV		 136 if (validate_received_bpdu(p, bpdu, bpdu_size) == 0) {
137 p->rcvd_bpdu = true;
138 p->rx_rstp_bpdu_cnt++;
139
140 memcpy(&p->received_bpdu_buffer, bpdu, sizeof(struct rstp_bpdu));
141
142 rstp->changes = true;
f025bcb7 143 move_rstp__(rstp);
9efd308e 144 } else {
f025bcb7 145 VLOG_DBG("%s, port %u: Bad STP or RSTP BPDU received", p->rstp->name,
4b30ba05 146 p->port_number);
9efd308e
DV		 147 p->error_count++;
148 }
149}
150
311fb15b 151/* Returns 0 on success. */
9efd308e
DV		 152static int
153validate_received_bpdu(struct rstp_port *p, const void *bpdu, size_t bpdu_size)
f025bcb7 154 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 155{
156 /* Validation of received BPDU, see [9.3.4]. */
157 const struct rstp_bpdu *temp;
158
159 temp = bpdu;
160 if (bpdu_size < TOPOLOGY_CHANGE_NOTIFICATION_BPDU_SIZE ||
161 ntohs(temp->protocol_identifier) != 0) {
162 return -1;
163 } else {
311fb15b
JR		 164 if (temp->bpdu_type == CONFIGURATION_BPDU
165 && bpdu_size >= CONFIGURATION_BPDU_SIZE
166 && (time_decode(temp->message_age) < time_decode(temp->max_age))) {
9efd308e 167 if ((ntohll(temp->designated_bridge_id) !=
311fb15b
JR		 168 p->rstp->bridge_identifier)
169 || ((ntohll(temp->designated_bridge_id) ==
170 p->rstp->bridge_identifier)
171 && (ntohs(temp->designated_port_id) != p->port_id))) {
9efd308e 172 return 0;
311fb15b 173 } else {
9efd308e
DV		 174 return -1;
175 }
176 } else if (temp->bpdu_type == TOPOLOGY_CHANGE_NOTIFICATION_BPDU) {
177 return 0;
178 } else if (temp->bpdu_type == RAPID_SPANNING_TREE_BPDU &&
179 bpdu_size >= RAPID_SPANNING_TREE_BPDU_SIZE) {
180 return 0;
311fb15b 181 } else {
9efd308e
DV		 182 return -1;
183 }
184 }
185}
186
187/*
f025bcb7
JR		 188 * move_rstp__()
189 * This method is invoked to move the State Machines. The SMs move only if the
9efd308e
DV		 190 * boolean 'changes' is true, meaning that something changed and the SMs need
191 * to work to process this change.
192 * The boolean 'changes' is set every time a SM modifies its state, a BPDU is
311fb15b 193 * received, a timer expires or port down event is detected. If a parameter is
9efd308e
DV		 194 * set by management, then 'changes' is set.
195 */
196#define MAX_RSTP_ITERATIONS 1000 /* safeguard */
197int
f025bcb7
JR		 198move_rstp__(struct rstp *rstp)
199 OVS_REQUIRES(rstp_mutex)
9efd308e 200{
9efd308e
DV		 201 int num_iterations;
202 num_iterations = 0;
203
204 while (rstp->changes == true && num_iterations < MAX_RSTP_ITERATIONS) {
311fb15b
JR		 205 struct rstp_port *p;
206
9efd308e 207 VLOG_DBG("%s: move_rstp()", rstp->name);
311fb15b 208
9efd308e
DV		 209 rstp->changes = false;
210 port_role_selection_sm(rstp);
d5f31dc8 211 HMAP_FOR_EACH (p, node, &rstp->ports) {
37db915e
JR		 212 if (p->rstp_state != RSTP_DISABLED) {
213 port_receive_sm(p);
214 bridge_detection_sm(p);
215 port_information_sm(p);
216 port_role_transition_sm(p);
217 port_state_transition_sm(p);
218 topology_change_sm(p);
219 port_transmit_sm(p);
220 port_protocol_migration_sm(p);
9efd308e
DV		 221 }
222 }
223 num_iterations++;
224 seq_change(connectivity_seq_get());
225 }
226 if (num_iterations >= MAX_RSTP_ITERATIONS) {
227 VLOG_ERR("%s: move_rstp() reached the iteration safeguard limit!",
228 rstp->name);
229 }
230 return 0;
231}
232
f025bcb7
JR		 233void decrease_rstp_port_timers__(struct rstp *r)
234 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 235{
236 struct rstp_port *p;
237
d5f31dc8 238 HMAP_FOR_EACH (p, node, &r->ports) {
37db915e
JR		 239 decrement_timer(&p->hello_when);
240 decrement_timer(&p->tc_while);
241 decrement_timer(&p->fd_while);
242 decrement_timer(&p->rcvd_info_while);
243 decrement_timer(&p->rr_while);
244 decrement_timer(&p->rb_while);
245 decrement_timer(&p->mdelay_while);
246 decrement_timer(&p->edge_delay_while);
247 decrement_timer(&p->tx_count);
248 p->uptime += 1;
9efd308e
DV		 249 }
250 r->changes = true;
f025bcb7 251 move_rstp__(r);
9efd308e
DV		 252}
253
254static void
255decrement_timer(uint16_t *timer)
256{
257 if (*timer != 0) {
258 *timer -= 1;
259 }
260}
261
262/* Bridge State Machine. */
263/* [17.28] Port Role Selection state machine. */
264
265static void
266updt_role_disabled_tree(struct rstp *r)
f025bcb7 267 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 268{
269 struct rstp_port *p;
270
d5f31dc8 271 HMAP_FOR_EACH (p, node, &r->ports) {
37db915e 272 p->selected_role = ROLE_DISABLED;
9efd308e
DV		 273 }
274}
275
276static void
277clear_reselect_tree(struct rstp *r)
f025bcb7 278 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 279{
280 struct rstp_port *p;
281
d5f31dc8 282 HMAP_FOR_EACH (p, node, &r->ports) {
37db915e 283 p->reselect = false;
9efd308e
DV		 284 }
285}
286
287void
f025bcb7
JR		 288updt_roles_tree__(struct rstp *r)
289 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 290{
291 struct rstp_port *p;
292 int vsel;
293 struct rstp_priority_vector best_vector, candidate_vector;
2372c146
JR		 294 enum rstp_port_role new_root_old_role = ROLE_DESIGNATED;
295 uint16_t old_root_port_number = 0;
296 uint16_t new_root_port_number = 0;
9efd308e 297
2372c146
JR		 298 old_root_port_number = r->root_port_id & 0x00ff;
299 if (old_root_port_number) {
300 r->old_root_aux = rstp_get_port_aux__(r, old_root_port_number);
301 }
9efd308e
DV		 302 vsel = -1;
303 best_vector = r->bridge_priority;
304 /* Letter c1) */
305 r->root_times = r->bridge_times;
306 /* Letters a) b) c) */
d5f31dc8 307 HMAP_FOR_EACH (p, node, &r->ports) {
37db915e
JR		 308 uint32_t old_root_path_cost;
309 uint32_t root_path_cost;
311fb15b 310
37db915e
JR		 311 if (p->info_is != INFO_IS_RECEIVED) {
312 continue;
313 }
314 /* [17.6] */
315 candidate_vector = p->port_priority;
316 candidate_vector.bridge_port_id = p->port_id;
317 old_root_path_cost = candidate_vector.root_path_cost;
318 root_path_cost = old_root_path_cost + p->port_path_cost;
319 candidate_vector.root_path_cost = root_path_cost;
320
321 if ((candidate_vector.designated_bridge_id & 0xffffffffffffULL) ==
322 (r->bridge_priority.designated_bridge_id & 0xffffffffffffULL)) {
55f8993c 323 continue;
37db915e
JR		 324 }
325 if (compare_rstp_priority_vectors(&candidate_vector,
326 &best_vector) == SUPERIOR) {
327 best_vector = candidate_vector;
328 r->root_times = p->port_times;
329 r->root_times.message_age++;
330 vsel = p->port_number;
2372c146 331 new_root_old_role = p->role;
9efd308e
DV		 332 }
333 }
334 r->root_priority = best_vector;
335 r->root_port_id = best_vector.bridge_port_id;
4b30ba05 336 VLOG_DBG("%s: new Root is "RSTP_ID_FMT, r->name,
9efd308e 337 RSTP_ID_ARGS(r->root_priority.root_bridge_id));
2372c146
JR		 338 new_root_port_number = r->root_port_id & 0x00ff;
339 if (new_root_port_number) {
340 r->new_root_aux = rstp_get_port_aux__(r, new_root_port_number);
341 }
342 /* Shift learned MAC addresses from an old Root Port to an existing
343 * Alternate Port. */
344 if (!r->root_changed
345 && new_root_old_role == ROLE_ALTERNATE
346 && new_root_port_number
347 && old_root_port_number
348 && new_root_port_number != old_root_port_number) {
349 r->root_changed = true;
350 }
9efd308e 351 /* Letters d) e) */
d5f31dc8 352 HMAP_FOR_EACH (p, node, &r->ports) {
37db915e
JR		 353 p->designated_priority_vector.root_bridge_id =
354 r->root_priority.root_bridge_id;
355 p->designated_priority_vector.root_path_cost =
356 r->root_priority.root_path_cost;
357 p->designated_priority_vector.designated_bridge_id =
358 r->bridge_identifier;
359 p->designated_priority_vector.designated_port_id =
360 p->port_id;
361 p->designated_times = r->root_times;
362 p->designated_times.hello_time = r->bridge_times.hello_time;
9efd308e 363 }
d5f31dc8 364 HMAP_FOR_EACH (p, node, &r->ports) {
37db915e
JR		 365 switch (p->info_is) {
366 case INFO_IS_DISABLED:
367 p->selected_role = ROLE_DISABLED;
368 break;
369 case INFO_IS_AGED:
370 p->updt_info = true;
371 p->selected_role = ROLE_DESIGNATED;
372 break;
373 case INFO_IS_MINE:
374 p->selected_role = ROLE_DESIGNATED;
375 if (compare_rstp_priority_vectors(
376 &p->port_priority, &p->designated_priority_vector) != SAME
377 || !rstp_times_equal(&p->designated_times, &r->root_times)) {
9efd308e 378 p->updt_info = true;
37db915e
JR		 379 }
380 break;
381 case INFO_IS_RECEIVED:
382 if (vsel == p->port_number) { /* Letter i) */
383 p->selected_role = ROLE_ROOT;
384 p->updt_info = false;
385 } else if (compare_rstp_priority_vectors(
386 &p->designated_priority_vector,
387 &p->port_priority) == INFERIOR) {
388 if (p->port_priority.designated_bridge_id !=
389 r->bridge_identifier) {
390 p->selected_role = ROLE_ALTERNATE;
9efd308e 391 p->updt_info = false;
9efd308e 392 } else {
37db915e
JR		 393 p->selected_role = ROLE_BACKUP;
394 p->updt_info = false;
9efd308e 395 }
37db915e
JR		 396 } else {
397 p->selected_role = ROLE_DESIGNATED;
398 p->updt_info = true;
9efd308e 399 }
37db915e
JR		 400 break;
401 default:
402 OVS_NOT_REACHED();
403 /* no break */
9efd308e
DV		 404 }
405 }
406 seq_change(connectivity_seq_get());
407}
408
409static void
410set_selected_tree(struct rstp *r)
f025bcb7 411 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 412{
413 struct rstp_port *p;
414
d5f31dc8 415 HMAP_FOR_EACH (p, node, &r->ports) {
37db915e
JR		 416 if (p->reselect) {
417 return;
9efd308e
DV		 418 }
419 }
d5f31dc8 420 HMAP_FOR_EACH (p, node, &r->ports) {
37db915e
JR		 421 p->selected = true;
422 }
9efd308e
DV		 423}
424
425static int
426port_role_selection_sm(struct rstp *r)
f025bcb7 427 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 428{
429 enum port_role_selection_state_machine old_state;
430 struct rstp_port *p;
431
432 old_state = r->port_role_selection_sm_state;
433
434 switch (r->port_role_selection_sm_state) {
435 case PORT_ROLE_SELECTION_SM_INIT:
311fb15b 436 if (r->begin) {
9efd308e
DV		 437 r->port_role_selection_sm_state =
438 PORT_ROLE_SELECTION_SM_INIT_BRIDGE_EXEC;
311fb15b 439 }
9efd308e
DV		 440 break;
441 case PORT_ROLE_SELECTION_SM_INIT_BRIDGE_EXEC:
442 updt_role_disabled_tree(r);
443 r->port_role_selection_sm_state = PORT_ROLE_SELECTION_SM_INIT_BRIDGE;
444 /* no break */
445 case PORT_ROLE_SELECTION_SM_INIT_BRIDGE:
446 r->port_role_selection_sm_state =
447 PORT_ROLE_SELECTION_SM_ROLE_SELECTION_EXEC;
448 break;
449 case PORT_ROLE_SELECTION_SM_ROLE_SELECTION_EXEC:
450 clear_reselect_tree(r);
f025bcb7 451 updt_roles_tree__(r);
9efd308e
DV		 452 set_selected_tree(r);
453 r->port_role_selection_sm_state =
454 PORT_ROLE_SELECTION_SM_ROLE_SELECTION;
455 /* no break */
456 case PORT_ROLE_SELECTION_SM_ROLE_SELECTION:
d5f31dc8 457 HMAP_FOR_EACH (p, node, &r->ports) {
37db915e
JR		 458 if (p->reselect) {
459 r->port_role_selection_sm_state =
460 PORT_ROLE_SELECTION_SM_ROLE_SELECTION_EXEC;
461 break;
9efd308e
DV		 462 }
463 }
464 break;
465 default:
466 OVS_NOT_REACHED();
467 /* no break */
468 }
469 if (old_state != r->port_role_selection_sm_state) {
470 r->changes = true;
4b30ba05
JR		 471 VLOG_DBG("%s: Port_role_selection_sm %d -> %d", r->name,
472 old_state, r->port_role_selection_sm_state);
9efd308e
DV		 473 }
474 return 0;
475}
476
477/* Port State Machines */
478
479/* [17.23 - Port receive state machine] */
480
481static void
482updt_bpdu_version(struct rstp_port *p) /* [17.21.22] */
f025bcb7 483 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 484{
485 switch (p->received_bpdu_buffer.bpdu_type) {
486 case CONFIGURATION_BPDU:
487 case TOPOLOGY_CHANGE_NOTIFICATION_BPDU:
488 p->rcvd_rstp = false;
489 p->rcvd_stp = true;
490 break;
491 case RAPID_SPANNING_TREE_BPDU:
492 p->rcvd_rstp = true;
493 p->rcvd_stp = false;
494 break;
495 default:
496 OVS_NOT_REACHED();
497 /* no break */
498 }
499}
500
501static int
502port_receive_sm(struct rstp_port *p)
f025bcb7 503 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 504{
505 enum port_receive_state_machine old_state;
506 struct rstp *r;
507
508 old_state = p->port_receive_sm_state;
509 r = p->rstp;
510
511 switch (p->port_receive_sm_state) {
512 case PORT_RECEIVE_SM_INIT:
513 if (r->begin || ((p->rcvd_bpdu || (p->edge_delay_while !=
514 r->migrate_time)) && !p->port_enabled)) {
515 p->port_receive_sm_state = PORT_RECEIVE_SM_DISCARD_EXEC;
516 }
517 break;
518 case PORT_RECEIVE_SM_DISCARD_EXEC:
519 p->rcvd_bpdu = p->rcvd_rstp = p->rcvd_stp = false;
520 p->rcvd_msg = false;
521 p->edge_delay_while = r->migrate_time;
522 p->port_receive_sm_state = PORT_RECEIVE_SM_DISCARD;
523 /* no break */
524 case PORT_RECEIVE_SM_DISCARD:
6448df94
JR		 525 if ((p->rcvd_bpdu || (p->edge_delay_while != r->migrate_time))
526 && !p->port_enabled) {
527 /* Global transition. */
528 p->port_receive_sm_state = PORT_RECEIVE_SM_DISCARD_EXEC;
529 } else if (p->rcvd_bpdu && p->port_enabled) {
9efd308e
DV		 530 p->port_receive_sm_state = PORT_RECEIVE_SM_RECEIVE_EXEC;
531 }
532 break;
533 case PORT_RECEIVE_SM_RECEIVE_EXEC:
534 updt_bpdu_version(p);
535 p->oper_edge = p->rcvd_bpdu = false;
536 p->rcvd_msg = true;
537 p->edge_delay_while = r->migrate_time;
538 p->port_receive_sm_state = PORT_RECEIVE_SM_RECEIVE;
539 /* no break */
540 case PORT_RECEIVE_SM_RECEIVE:
6448df94
JR		 541 if ((p->rcvd_bpdu || (p->edge_delay_while != r->migrate_time))
542 && !p->port_enabled) {
543 /* Global transition. */
544 p->port_receive_sm_state = PORT_RECEIVE_SM_DISCARD_EXEC;
545 } else if (p->rcvd_bpdu && p->port_enabled && !p->rcvd_msg) {
9efd308e
DV		 546 p->port_receive_sm_state = PORT_RECEIVE_SM_RECEIVE_EXEC;
547 }
548 break;
549 default:
550 OVS_NOT_REACHED();
551 /* no break */
552 }
553 if (old_state != p->port_receive_sm_state) {
554 r->changes = true;
555 VLOG_DBG("%s, port %u: Port_receive_sm %d -> %d", p->rstp->name,
556 p->port_number, old_state, p->port_receive_sm_state);
557 }
558 return 0;
559}
560
561/* [17.24 - Port Protocol Migration state machine] */
562static int
563port_protocol_migration_sm(struct rstp_port *p)
f025bcb7 564 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 565{
566 enum port_protocol_migration_state_machine old_state;
567 struct rstp *r;
568
569 old_state = p->port_protocol_migration_sm_state;
570 r = p->rstp;
571
572 switch (p->port_protocol_migration_sm_state) {
573 case PORT_PROTOCOL_MIGRATION_SM_INIT:
311fb15b
JR		 574 p->port_protocol_migration_sm_state =
575 PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP_EXEC;
9efd308e
DV		 576 /* no break */
577 case PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP_EXEC:
578 p->mcheck = false;
579 p->send_rstp = r->rstp_version;
580 p->mdelay_while = r->migrate_time;
581 p->port_protocol_migration_sm_state =
582 PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP;
583 /* no break */
584 case PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP:
585 if (p->mdelay_while == 0) {
311fb15b
JR		 586 p->port_protocol_migration_sm_state =
587 PORT_PROTOCOL_MIGRATION_SM_SENSING_EXEC;
588 } else if ((p->mdelay_while != r->migrate_time) && !p->port_enabled) {
9efd308e
DV		 589 p->port_protocol_migration_sm_state =
590 PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP_EXEC;
591 }
592 break;
593 case PORT_PROTOCOL_MIGRATION_SM_SELECTING_STP_EXEC:
311fb15b 594 p->send_rstp = false;
9efd308e
DV		 595 p->mdelay_while = r->migrate_time;
596 p->port_protocol_migration_sm_state =
597 PORT_PROTOCOL_MIGRATION_SM_SELECTING_STP;
598 /* no break */
599 case PORT_PROTOCOL_MIGRATION_SM_SELECTING_STP:
600 if ((p->mdelay_while == 0) || (!p->port_enabled) || p->mcheck) {
601 p->port_protocol_migration_sm_state =
602 PORT_PROTOCOL_MIGRATION_SM_SENSING_EXEC;
603 }
604 break;
605 case PORT_PROTOCOL_MIGRATION_SM_SENSING_EXEC:
606 p->rcvd_rstp = false;
607 p->rcvd_stp = false;
608 p->port_protocol_migration_sm_state =
609 PORT_PROTOCOL_MIGRATION_SM_SENSING;
610 /* no break */
611 case PORT_PROTOCOL_MIGRATION_SM_SENSING:
612 if (!p->port_enabled || p->mcheck || ((r->rstp_version) &&
311fb15b 613 !p->send_rstp && p->rcvd_rstp)) {
9efd308e
DV		 614 p->port_protocol_migration_sm_state =
615 PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP_EXEC;
311fb15b 616 } else if (p->send_rstp && p->rcvd_stp) {
9efd308e
DV		 617 p->port_protocol_migration_sm_state =
618 PORT_PROTOCOL_MIGRATION_SM_SELECTING_STP_EXEC;
619 }
620 break;
621 default:
622 OVS_NOT_REACHED();
623 /* no break */
624 }
625 if (old_state != p->port_protocol_migration_sm_state) {
626 r->changes = true;
627 VLOG_DBG("%s, port %u: port_protocol_migration_sm %d -> %d",
628 p->rstp->name, p->port_number, old_state,
629 p->port_protocol_migration_sm_state);
630 }
631
632 return 0;
633}
634
635/* [17.25 - Bridge Detection state machine] */
636static int
637bridge_detection_sm(struct rstp_port *p)
f025bcb7 638 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 639{
640 enum bridge_detection_state_machine old_state;
641 struct rstp *r;
642
643 old_state = p->bridge_detection_sm_state;
644 r = p->rstp;
645
646 switch (p->bridge_detection_sm_state) {
647 case BRIDGE_DETECTION_SM_INIT:
648 if (r->begin && p->admin_edge) {
649 p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_EDGE_EXEC;
650 } else if (r->begin && !p->admin_edge) {
651 p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_NOT_EDGE_EXEC;
652 }
653 break;
654 case BRIDGE_DETECTION_SM_EDGE_EXEC:
655 p->oper_edge = true;
656 p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_EDGE;
657 /* no break */
658 case BRIDGE_DETECTION_SM_EDGE:
659 if ((!p->port_enabled && !p->admin_edge) || !p->oper_edge) {
660 p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_NOT_EDGE_EXEC;
661 }
662 break;
663 case BRIDGE_DETECTION_SM_NOT_EDGE_EXEC:
664 p->oper_edge = false;
665 p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_NOT_EDGE;
666 /* no break */
667 case BRIDGE_DETECTION_SM_NOT_EDGE:
311fb15b
JR		 668 if ((!p->port_enabled && p->admin_edge)
669 || ((p->edge_delay_while == 0) && p->auto_edge && p->send_rstp
670 && p->proposing)) {
9efd308e
DV		 671 p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_EDGE_EXEC;
672 }
673 break;
674 default:
675 OVS_NOT_REACHED();
676 /* no break */
677 }
678 if (old_state != p->bridge_detection_sm_state) {
679 r->changes = true;
680 VLOG_DBG("%s, port %u: bridge_detection_sm %d -> %d", p->rstp->name,
681 p->port_number, old_state, p->bridge_detection_sm_state);
682 }
683 return 0;
684}
685
686/* [17.26 - Port Transmit state machine] */
687static void
688rstp_send_bpdu(struct rstp_port *p, const void *bpdu, size_t bpdu_size)
f025bcb7 689 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 690{
691 struct eth_header *eth;
692 struct llc_header *llc;
cf62fa4c 693 struct dp_packet *pkt;
9efd308e
DV		 694
695 /* Skeleton. */
cf62fa4c
PS		 696 pkt = dp_packet_new(ETH_HEADER_LEN + LLC_HEADER_LEN + bpdu_size);
697 eth = dp_packet_put_zeros(pkt, sizeof *eth);
698 llc = dp_packet_put_zeros(pkt, sizeof *llc);
82eb5b0a 699 dp_packet_reset_offsets(pkt);
cf62fa4c 700 dp_packet_set_l3(pkt, dp_packet_put(pkt, bpdu, bpdu_size));
9efd308e
DV		 701
702 /* 802.2 header. */
703 memcpy(eth->eth_dst, eth_addr_stp, ETH_ADDR_LEN);
704 /* p->rstp->send_bpdu() must fill in source address. */
cf62fa4c 705 eth->eth_type = htons(dp_packet_size(pkt) - ETH_HEADER_LEN);
9efd308e
DV		 706
707 /* LLC header. */
708 llc->llc_dsap = STP_LLC_DSAP;
709 llc->llc_ssap = STP_LLC_SSAP;
710 llc->llc_cntl = STP_LLC_CNTL;
6b90bc57 711 p->rstp->send_bpdu(pkt, p->aux, p->rstp->aux);
9efd308e
DV		 712}
713
714static void
715record_agreement(struct rstp_port *p)
f025bcb7 716 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 717{
718 struct rstp *r;
719
720 r = p->rstp;
721 if (r->rstp_version && p->oper_point_to_point_mac &&
311fb15b 722 ((p->received_bpdu_buffer.flags & BPDU_FLAG_AGREEMENT))) {
9efd308e
DV		 723 p->agreed = true;
724 p->proposing = false;
725 } else {
726 p->agreed = false;
727 }
728}
729
730static void
731set_tc_flags(struct rstp_port *p)
f025bcb7 732 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 733{
734 /* Sets rcvd_tc and/or rcvd_tc_ack if the Topology Change and/or Topology
735 * Change Acknowledgment flags, respectively, are set in a ConfigBPDU or
736 * RST BPDU.
737 */
738 if (p->received_bpdu_buffer.bpdu_type == CONFIGURATION_BPDU ||
311fb15b 739 p->received_bpdu_buffer.bpdu_type == RAPID_SPANNING_TREE_BPDU) {
9efd308e
DV		 740 if ((p->received_bpdu_buffer.flags & BPDU_FLAG_TOPCHANGE) != 0) {
741 p->rcvd_tc = true;
742 }
743 if ((p->received_bpdu_buffer.flags & BPDU_FLAG_TOPCHANGEACK) != 0) {
744 p->rcvd_tc_ack = true;
745 }
746 }
747 /* Sets rcvd_tcn true if the BPDU is a TCN BPDU. */
311fb15b
JR		 748 if (p->received_bpdu_buffer.bpdu_type
749 == TOPOLOGY_CHANGE_NOTIFICATION_BPDU) {
9efd308e
DV		 750 p->rcvd_tcn = true;
751 }
752}
753
754static void
755record_dispute(struct rstp_port *p)
f025bcb7 756 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 757{
758 if ((p->received_bpdu_buffer.flags & BPDU_FLAG_LEARNING) != 0) {
b5ba2490
JR		 759 /* 802.1D-2004 says to set the agreed flag and to clear the proposing
760 * flag. 802.1q-2008 instead says to set the disputed variable and to
761 * clear the agreed variable. */
762 p->disputed = true;
763 p->agreed = false;
9efd308e
DV		 764 }
765}
766
767static void
768record_proposal(struct rstp_port *p)
f025bcb7 769 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 770{
771 enum port_flag role =
772 ((p->received_bpdu_buffer.flags) & ROLE_FLAG_MASK) >> ROLE_FLAG_SHIFT;
311fb15b
JR		 773
774 if ((role == PORT_DES)
775 && ((p->received_bpdu_buffer.flags & BPDU_FLAG_PROPOSAL) != 0)) {
9efd308e
DV		 776 p->proposed = true;
777 }
778}
779
780static void
781record_priority(struct rstp_port *p)
f025bcb7 782 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 783{
784 p->port_priority.root_bridge_id = p->msg_priority.root_bridge_id;
785 p->port_priority.root_path_cost = p->msg_priority.root_path_cost;
786 p->port_priority.designated_bridge_id =
787 p->msg_priority.designated_bridge_id;
788 p->port_priority.designated_port_id = p->msg_priority.designated_port_id;
789}
790
791static void
792record_times(struct rstp_port *p)
f025bcb7 793 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 794{
795 p->port_times = p->msg_times;
796 if (p->msg_times.hello_time == 0) {
797 p->port_times.hello_time = 1;
798 }
799}
800
801static void
802updt_rcvd_info_while(struct rstp_port *p)
f025bcb7 803 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 804{
805 /* [17.21.23]
806 * The value assigned to rcvdInfoWhile is the three times the Hello Time,
807 * if Message Age, incremented by 1 second and rounded to the nearest whole
808 * second, does not exceed Max Age, and is zero otherwise.
809 */
810 if (p->port_times.message_age < p->port_times.max_age) {
811 p->rcvd_info_while = p->port_times.hello_time * 3;
311fb15b 812 } else {
9efd308e 813 p->rcvd_info_while = 0;
311fb15b 814 }
9efd308e
DV		 815}
816
817/* Times are internally held in seconds, while the protocol uses 1/256 seconds.
818 * time_encode() is used to convert time values sent in bpdus, while
819 * time_decode() is used to convert time values received in bpdus.
820 */
821static ovs_be16
822time_encode(uint8_t value)
823{
824 return htons(value * 256);
825}
826
827static uint8_t
828time_decode(ovs_be16 encoded)
829{
830 return ntohs(encoded) / 256;
831}
832
833/* [17.21.19] */
834static void
835tx_config(struct rstp_port *p)
f025bcb7 836 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 837{
838 struct rstp_bpdu bpdu;
839
840 bpdu.protocol_identifier = htons(0);
841 bpdu.protocol_version_identifier = 0;
842 bpdu.bpdu_type = CONFIGURATION_BPDU;
843 bpdu.root_bridge_id = htonll(p->designated_priority_vector.root_bridge_id);
844 bpdu.root_path_cost = htonl(p->designated_priority_vector.root_path_cost);
845 bpdu.designated_bridge_id =
846 htonll(p->designated_priority_vector.designated_bridge_id);
847 bpdu.designated_port_id =
848 htons(p->designated_priority_vector.designated_port_id);
849 bpdu.message_age = time_encode(p->designated_times.message_age);
850 bpdu.max_age = time_encode(p->designated_times.max_age);
851 bpdu.hello_time = time_encode(p->designated_times.hello_time);
852 bpdu.forward_delay = time_encode(p->designated_times.forward_delay);
853 bpdu.flags = 0;
854 if (p->tc_while != 0) {
855 bpdu.flags |= BPDU_FLAG_TOPCHANGE;
856 }
857 if (p->tc_ack != 0) {
858 bpdu.flags |= BPDU_FLAG_TOPCHANGEACK;
859 }
860 rstp_send_bpdu(p, &bpdu, sizeof(struct rstp_bpdu));
861}
862
863/* [17.21.20] */
864static void
865tx_rstp(struct rstp_port *p)
f025bcb7 866 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 867{
868 struct rstp_bpdu bpdu;
869
870 bpdu.protocol_identifier = htons(0);
871 bpdu.protocol_version_identifier = 2;
872 bpdu.bpdu_type = RAPID_SPANNING_TREE_BPDU;
873 bpdu.root_bridge_id = htonll(p->designated_priority_vector.root_bridge_id);
874 bpdu.root_path_cost = htonl(p->designated_priority_vector.root_path_cost);
875 bpdu.designated_bridge_id =
876 htonll(p->designated_priority_vector.designated_bridge_id);
877 bpdu.designated_port_id =
878 htons(p->designated_priority_vector.designated_port_id);
879 bpdu.message_age = time_encode(p->designated_times.message_age);
880 bpdu.max_age = time_encode(p->designated_times.max_age);
881 bpdu.hello_time = time_encode(p->designated_times.hello_time);
882 bpdu.forward_delay = time_encode(p->designated_times.forward_delay);
883 bpdu.flags = 0;
311fb15b 884
9efd308e
DV		 885 switch (p->role) {
886 case ROLE_ROOT:
887 bpdu.flags = PORT_ROOT << ROLE_FLAG_SHIFT;
888 break;
889 case ROLE_DESIGNATED:
890 bpdu.flags = PORT_DES << ROLE_FLAG_SHIFT;
891 break;
892 case ROLE_ALTERNATE:
893 case ROLE_BACKUP:
894 bpdu.flags = PORT_ALT_BACK << ROLE_FLAG_SHIFT;
895 break;
896 case ROLE_DISABLED:
4b30ba05 897 /* Should not happen! */
9efd308e 898 VLOG_ERR("%s transmitting bpdu in disabled role on port "
4b30ba05 899 RSTP_PORT_ID_FMT, p->rstp->name, p->port_id);
9efd308e
DV		 900 break;
901 }
902 if (p->agree) {
903 bpdu.flags |= BPDU_FLAG_AGREEMENT;
904 }
905 if (p->proposing) {
906 bpdu.flags |= BPDU_FLAG_PROPOSAL;
907 }
908 if (p->tc_while != 0) {
909 bpdu.flags |= BPDU_FLAG_TOPCHANGE;
910 }
911 if (p->learning) {
912 bpdu.flags |= BPDU_FLAG_LEARNING;
913 }
914 if (p->forwarding) {
915 bpdu.flags |= BPDU_FLAG_FORWARDING;
916 }
917 bpdu.version1_length = 0;
918 rstp_send_bpdu(p, &bpdu, sizeof(struct rstp_bpdu));
919}
920
921/* [17.21.21] */
922static void
923tx_tcn(struct rstp_port *p)
f025bcb7 924 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 925{
926 struct rstp_bpdu bpdu;
927
928 memset(&bpdu, 0, sizeof(struct rstp_bpdu));
929
930 bpdu.protocol_identifier = htons(0);
931 bpdu.protocol_version_identifier = 0;
932 bpdu.bpdu_type = TOPOLOGY_CHANGE_NOTIFICATION_BPDU;
933 rstp_send_bpdu(p, &bpdu, sizeof(struct rstp_bpdu));
934}
935
936static int
937port_transmit_sm(struct rstp_port *p)
f025bcb7 938 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 939{
940 enum port_transmit_state_machine old_state;
941 struct rstp *r;
942
943 old_state = p->port_transmit_sm_state;
944 r = p->rstp;
945
946 switch (p->port_transmit_sm_state) {
947 case PORT_TRANSMIT_SM_INIT:
948 if (r->begin) {
949 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_INIT_EXEC;
950 }
951 break;
952 case PORT_TRANSMIT_SM_TRANSMIT_INIT_EXEC:
953 p->new_info = true;
954 p->tx_count = 0;
955 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_INIT;
956 /* no break */
957 case PORT_TRANSMIT_SM_TRANSMIT_INIT:
958 p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
959 break;
960 case PORT_TRANSMIT_SM_TRANSMIT_PERIODIC_EXEC:
961 p->new_info = p->new_info || (p->role == ROLE_DESIGNATED ||
962 (p->role == ROLE_ROOT && p->tc_while != 0));
963 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_PERIODIC;
964 /* no break */
965 case PORT_TRANSMIT_SM_TRANSMIT_PERIODIC:
966 p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
967 break;
968 case PORT_TRANSMIT_SM_IDLE_EXEC:
969 p->hello_when = r->bridge_hello_time;
970 p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE;
971 /* no break */
972 case PORT_TRANSMIT_SM_IDLE:
973 if (p->role == ROLE_DISABLED) {
4b30ba05
JR		 974 VLOG_DBG("%s, port %u: port_transmit_sm ROLE == DISABLED.",
975 p->rstp->name, p->port_number);
9efd308e 976 break;
311fb15b
JR		 977 } else if (p->send_rstp && p->new_info
978 && p->tx_count < r->transmit_hold_count
979 && p->hello_when != 0 && p->selected && !p->updt_info) {
9efd308e 980 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_RSTP_EXEC;
311fb15b 981 } else if (p->hello_when == 0 && p->selected && !p->updt_info) {
9efd308e
DV		 982 p->port_transmit_sm_state =
983 PORT_TRANSMIT_SM_TRANSMIT_PERIODIC_EXEC;
311fb15b
JR		 984 } else if (!p->send_rstp && p->new_info && p->role == ROLE_ROOT
985 && p->tx_count < r->transmit_hold_count
986 && p->hello_when != 0 && p->selected && !p->updt_info) {
9efd308e 987 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_TCN_EXEC;
311fb15b
JR		 988 } else if (!p->send_rstp && p->new_info && p->role == ROLE_DESIGNATED
989 && p->tx_count < r->transmit_hold_count
990 && p->hello_when != 0 && p->selected && !p->updt_info) {
9efd308e
DV		 991 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_CONFIG_EXEC;
992 }
993 break;
994 case PORT_TRANSMIT_SM_TRANSMIT_CONFIG_EXEC:
995 p->new_info = false;
996 tx_config(p);
997 p->tx_count += 1;
998 p->tc_ack = false;
999 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_CONFIG;
1000 /* no break */
1001 case PORT_TRANSMIT_SM_TRANSMIT_CONFIG:
1002 p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
1003 break;
1004 case PORT_TRANSMIT_SM_TRANSMIT_TCN_EXEC:
1005 p->new_info = false;
1006 tx_tcn(p);
1007 p->tx_count += 1;
1008 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_TCN;
1009 /* no break */
1010 case PORT_TRANSMIT_SM_TRANSMIT_TCN:
1011 p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
1012 break;
1013 case PORT_TRANSMIT_SM_TRANSMIT_RSTP_EXEC:
1014 p->new_info = false;
1015 tx_rstp(p);
1016 p->tx_count += 1;
1017 p->tc_ack = false;
1018 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_RSTP;
1019 /* no break */
1020 case PORT_TRANSMIT_SM_TRANSMIT_RSTP:
1021 p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
1022 break;
1023 default:
1024 OVS_NOT_REACHED();
1025 /* no break */
1026 }
1027 if (old_state != p->port_transmit_sm_state) {
1028 r->changes = true;
1029 VLOG_DBG("%s, port %u: port_transmit_sm %d -> %d", p->rstp->name,
1030 p->port_number, old_state, p->port_transmit_sm_state);
1031 }
1032 return 0;
1033}
1034
1035/* [17.27 Port Information state machine] */
1036#define RECEIVED 0
1037#define MINE 1
1038
1039static int
1040rcv_info(struct rstp_port *p)
f025bcb7 1041 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1042{
1043 enum vector_comparison cp;
1044 bool ct;
1045 enum port_flag role;
1046
1047 p->msg_priority.root_bridge_id =
1048 ntohll(p->received_bpdu_buffer.root_bridge_id);
1049 p->msg_priority.root_path_cost =
1050 ntohl(p->received_bpdu_buffer.root_path_cost);
1051 p->msg_priority.designated_bridge_id =
1052 ntohll(p->received_bpdu_buffer.designated_bridge_id);
1053 p->msg_priority.designated_port_id =
1054 ntohs(p->received_bpdu_buffer.designated_port_id);
1055
1056 p->msg_times.forward_delay =
1057 time_decode(p->received_bpdu_buffer.forward_delay);
1058 p->msg_times.hello_time = time_decode(p->received_bpdu_buffer.hello_time);
1059 p->msg_times.max_age = time_decode(p->received_bpdu_buffer.max_age);
1060 p->msg_times.message_age =
1061 time_decode(p->received_bpdu_buffer.message_age);
1062
a0478216 1063 cp = compare_rstp_priority_vectors(&p->msg_priority, &p->port_priority);
9efd308e 1064 ct = rstp_times_equal(&p->port_times, &p->msg_times);
12c14838
DV		 1065 /* Configuration BPDU conveys a Designated Port Role. */
1066 if (p->received_bpdu_buffer.bpdu_type == CONFIGURATION_BPDU) {
1067 role = PORT_DES;
1068 } else {
1069 role =
1070 (p->received_bpdu_buffer.flags & ROLE_FLAG_MASK) >> ROLE_FLAG_SHIFT;
1071 }
9efd308e 1072
11d4d408
DV		 1073 /* 802.1D-2004 does not report this behaviour.
1074 * 802.1Q-2008 says set rcvdTcn. */
1075 if (p->received_bpdu_buffer.bpdu_type ==
1076 TOPOLOGY_CHANGE_NOTIFICATION_BPDU) {
1077 p->rcvd_tcn = true;
1078 return OTHER_INFO;
1079 }
1080
9efd308e
DV		 1081 /* Returns SuperiorDesignatedInfo if:
1082 * a) The received message conveys a Designated Port Role, and
1083 * 1) The message priority is superior (17.6) to the Port.s port priority
1084 * vector, or
1085 * 2) The message priority vector is the same as the Port.s port priority
1086 * vector, and any of the received timer parameter values (msg_times.
1087 * 17.19.15) differ from those already held for the Port (port_times
1088 * 17.19.22).
1089 * NOTE: Configuration BPDU explicitly conveys a Designated Port Role.
1090 */
12c14838 1091 if (role == PORT_DES && (cp == SUPERIOR || (cp == SAME && ct == false))) {
9efd308e 1092 return SUPERIOR_DESIGNATED_INFO;
9efd308e 1093
311fb15b
JR		 1094 /* Returns RepeatedDesignatedInfo if:
1095 * b) The received message conveys Designated Port Role, and a message
1096 * priority vector and timer parameters that are the same as the
1097 * Port's port priority vector or timer values. */
1098 } else if (role == PORT_DES && cp == SAME && ct == true) {
9efd308e 1099 return REPEATED_DESIGNATED_INFO;
9efd308e 1100
311fb15b
JR		 1101 /* Returns InferiorDesignatedInfo if:
1102 * c) The received message conveys a Designated Port Role, and a
1103 * message priority vector that is worse than the Port's port
1104 * priority vector. */
1105 } else if (role == PORT_DES && cp == INFERIOR) {
9efd308e 1106 return INFERIOR_DESIGNATED_INFO;
9efd308e 1107
311fb15b
JR		 1108 /* Returns InferiorRootAlternateInfo if:
1109 * d) The received message conveys a Root Port, Alternate Port, or
1110 * Backup Port Role and a message priority that is the same as or
1111 * worse than the port priority vector. */
1112 } else if ((role == PORT_ROOT || role == PORT_ALT_BACK) &&
1113 (cp == INFERIOR || cp == SAME)) {
9efd308e 1114 return INFERIOR_ROOT_ALTERNATE_INFO;
9efd308e 1115
311fb15b
JR		 1116 /* Otherwise, returns OtherInfo. */
1117 } else {
9efd308e
DV		 1118 return OTHER_INFO;
1119 }
1120}
1121
1122static int
1123better_or_same_info(struct rstp_port *p, int new_info_is)
f025bcb7 1124 OVS_REQUIRES(rstp_mutex)
9efd308e 1125{
311fb15b
JR		 1126 return
1127 (new_info_is == RECEIVED && p->info_is == INFO_IS_RECEIVED
a0478216
JR		 1128 && compare_rstp_priority_vectors(&p->msg_priority,
1129 &p->port_priority))
311fb15b 1130 || (new_info_is == MINE && p->info_is == INFO_IS_MINE
a0478216
JR		 1131 && compare_rstp_priority_vectors(&p->designated_priority_vector,
1132 &p->port_priority));
9efd308e
DV		 1133}
1134
1135static int
1136port_information_sm(struct rstp_port *p)
f025bcb7 1137 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1138{
1139 enum port_information_state_machine old_state;
1140 struct rstp *r;
b5ba2490 1141 struct rstp_port *p1;
9efd308e
DV		 1142
1143 old_state = p->port_information_sm_state;
1144 r = p->rstp;
1145
9efd308e
DV		 1146 switch (p->port_information_sm_state) {
1147 case PORT_INFORMATION_SM_INIT:
6448df94
JR		 1148 if (r->begin
1149 || (!p->port_enabled && p->info_is != INFO_IS_DISABLED)) {
9efd308e
DV		 1150 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1151 }
1152 break;
1153 case PORT_INFORMATION_SM_DISABLED_EXEC:
1154 p->rcvd_msg = false;
1155 p->proposing = p->proposed = p->agree = p->agreed = false;
1156 p->rcvd_info_while = 0;
1157 p->info_is = INFO_IS_DISABLED;
1158 p->reselect = true;
1159 p->selected = false;
1160 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED;
1161 /* no break */
1162 case PORT_INFORMATION_SM_DISABLED:
6448df94
JR		 1163 if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1164 /* Global transition. */
1165 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1166 } else if (p->port_enabled) {
9efd308e 1167 p->port_information_sm_state = PORT_INFORMATION_SM_AGED_EXEC;
4b30ba05
JR		 1168 } else if (p->rcvd_msg) {
1169 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
9efd308e
DV		 1170 }
1171 break;
1172 case PORT_INFORMATION_SM_AGED_EXEC:
1173 p->info_is = INFO_IS_AGED;
1174 p->reselect = true;
1175 p->selected = false;
1176 p->port_information_sm_state = PORT_INFORMATION_SM_AGED;
1177 /* no break */
1178 case PORT_INFORMATION_SM_AGED:
6448df94
JR		 1179 if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1180 /* Global transition. */
1181 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1182 } else if (p->selected && p->updt_info) {
9efd308e
DV		 1183 p->port_information_sm_state = PORT_INFORMATION_SM_UPDATE_EXEC;
1184 }
1185 break;
1186 case PORT_INFORMATION_SM_UPDATE_EXEC:
1187 p->proposing = p->proposed = false;
1188 /* MINE is not specified in Standard 802.1D-2004. */
1189 p->agreed = p->agreed && better_or_same_info(p, MINE);
1190 p->synced = p->synced && p->agreed;
1191 p->port_priority.root_bridge_id =
1192 p->designated_priority_vector.root_bridge_id;
1193 p->port_priority.root_path_cost =
1194 p->designated_priority_vector.root_path_cost;
1195 p->port_priority.designated_bridge_id =
1196 p->designated_priority_vector.designated_bridge_id;
1197 p->port_priority.designated_port_id =
1198 p->designated_priority_vector.designated_port_id;
1199 p->port_times = p->designated_times;
1200 p->updt_info = false;
1201 p->info_is = INFO_IS_MINE;
1202 p->new_info = true;
1203 p->port_information_sm_state = PORT_INFORMATION_SM_UPDATE;
1204 /* no break */
1205 case PORT_INFORMATION_SM_UPDATE:
6448df94
JR		 1206 if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1207 /* Global transition. */
1208 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1209 } else {
1210 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1211 }
9efd308e
DV		 1212 break;
1213 case PORT_INFORMATION_SM_CURRENT_EXEC:
1214 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT;
1215 /* no break */
1216 case PORT_INFORMATION_SM_CURRENT:
6448df94
JR		 1217 if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1218 /* Global transition. */
1219 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1220 } else if (p->rcvd_msg && !p->updt_info) {
9efd308e
DV		 1221 p->port_information_sm_state = PORT_INFORMATION_SM_RECEIVE_EXEC;
1222 } else if (p->selected && p->updt_info) {
1223 p->port_information_sm_state = PORT_INFORMATION_SM_UPDATE_EXEC;
1224 } else if ((p->info_is == INFO_IS_RECEIVED) &&
1225 (p->rcvd_info_while == 0) && !p->updt_info &&
1226 !p->rcvd_msg) {
1227 p->port_information_sm_state = PORT_INFORMATION_SM_AGED_EXEC;
1228 }
1229 break;
1230 case PORT_INFORMATION_SM_RECEIVE_EXEC:
1231 p->rcvd_info = rcv_info(p);
1232 p->port_information_sm_state = PORT_INFORMATION_SM_RECEIVE;
1233 /* no break */
1234 case PORT_INFORMATION_SM_RECEIVE:
6448df94
JR		 1235 if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1236 /* Global transition. */
1237 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1238 } else {
1239 switch (p->rcvd_info) {
1240 case SUPERIOR_DESIGNATED_INFO:
b5ba2490
JR		 1241 /* 802.1q-2008 has a checkBPDUConsistency() function, called on
1242 * a BPDU reception. checkBPDUConsistency() clears the agreed
1243 * variable if the received message priority vector is superior
1244 * to the port priority vector, the BPDU is an ST BPDU or an
1245 * RST BPDU, its port role is Designated and its Learning flag
1246 * is set. */
1247 if (p->received_bpdu_buffer.flags & BPDU_FLAG_LEARNING) {
1248 HMAP_FOR_EACH (p1, node, &r->ports) {
1249 if (p1->port_number != p->port_number) {
1250 p1->agreed = false;
1251 }
1252 }
1253 }
6448df94
JR		 1254 p->port_information_sm_state =
1255 PORT_INFORMATION_SM_SUPERIOR_DESIGNATED_EXEC;
1256 break;
1257 case REPEATED_DESIGNATED_INFO:
1258 p->port_information_sm_state =
1259 PORT_INFORMATION_SM_REPEATED_DESIGNATED_EXEC;
1260 break;
1261 case INFERIOR_DESIGNATED_INFO:
1262 p->port_information_sm_state =
1263 PORT_INFORMATION_SM_INFERIOR_DESIGNATED_EXEC;
1264 break;
1265 case INFERIOR_ROOT_ALTERNATE_INFO:
1266 p->port_information_sm_state =
1267 PORT_INFORMATION_SM_NOT_DESIGNATED_EXEC;
1268 break;
1269 case OTHER_INFO:
1270 p->port_information_sm_state = PORT_INFORMATION_SM_OTHER_EXEC;
1271 break;
1272 default:
1273 OVS_NOT_REACHED();
1274 /* no break */
1275 }
9efd308e
DV		 1276 }
1277 break;
1278 case PORT_INFORMATION_SM_OTHER_EXEC:
1279 p->rcvd_msg = false;
1280 p->port_information_sm_state = PORT_INFORMATION_SM_OTHER;
1281 /* no break */
1282 case PORT_INFORMATION_SM_OTHER:
6448df94
JR		 1283 if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1284 /* Global transition. */
1285 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1286 } else {
1287 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1288 }
9efd308e
DV		 1289 break;
1290 case PORT_INFORMATION_SM_NOT_DESIGNATED_EXEC:
1291 record_agreement(p);
1292 set_tc_flags(p);
1293 p->rcvd_msg = false;
1294 p->port_information_sm_state = PORT_INFORMATION_SM_NOT_DESIGNATED;
1295 /* no break */
1296 case PORT_INFORMATION_SM_NOT_DESIGNATED:
6448df94
JR		 1297 if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1298 /* Global transition. */
1299 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1300 } else {
1301 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1302 }
9efd308e
DV		 1303 break;
1304 case PORT_INFORMATION_SM_INFERIOR_DESIGNATED_EXEC:
1305 record_dispute(p);
1306 p->rcvd_msg = false;
1307 p->port_information_sm_state = PORT_INFORMATION_SM_INFERIOR_DESIGNATED;
1308 /* no break */
1309 case PORT_INFORMATION_SM_INFERIOR_DESIGNATED:
6448df94
JR		 1310 if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1311 /* Global transition. */
1312 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1313 } else {
1314 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1315 }
9efd308e
DV		 1316 break;
1317 case PORT_INFORMATION_SM_REPEATED_DESIGNATED_EXEC:
1318 record_proposal(p);
1319 set_tc_flags(p);
b5ba2490
JR		 1320 /* This record_agreement() is missing in 802.1D-2004, but it's present
1321 * in 802.1q-2008. */
1322 record_agreement(p);
9efd308e
DV		 1323 updt_rcvd_info_while(p);
1324 p->rcvd_msg = false;
1325 p->port_information_sm_state = PORT_INFORMATION_SM_REPEATED_DESIGNATED;
1326 /* no break */
1327 case PORT_INFORMATION_SM_REPEATED_DESIGNATED:
6448df94
JR		 1328 if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1329 /* Global transition. */
1330 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1331 } else {
1332 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1333 }
9efd308e
DV		 1334 break;
1335 case PORT_INFORMATION_SM_SUPERIOR_DESIGNATED_EXEC:
1336 p->agreed = p->proposing = false;
1337 record_proposal(p);
1338 set_tc_flags(p);
1339 /* RECEIVED is not specified in Standard 802.1D-2004. */
1340 p->agree = p->agree && better_or_same_info(p, RECEIVED);
b5ba2490
JR		 1341 /* This record_agreement() and the synced assignment are missing in
1342 * 802.1D-2004, but they're present in 802.1q-2008. */
1343 record_agreement(p);
1344 p->synced = p->synced && p->agreed;
9efd308e
DV		 1345 record_priority(p);
1346 record_times(p);
1347 updt_rcvd_info_while(p);
1348 p->info_is = INFO_IS_RECEIVED;
1349 p->reselect = true;
1350 p->selected = false;
1351 p->rcvd_msg = false;
1352 p->port_information_sm_state = PORT_INFORMATION_SM_SUPERIOR_DESIGNATED;
1353 /* no break */
1354 case PORT_INFORMATION_SM_SUPERIOR_DESIGNATED:
6448df94
JR		 1355 if (!p->port_enabled && p->info_is != INFO_IS_DISABLED) {
1356 /* Global transition. */
1357 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1358 } else {
1359 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1360 }
9efd308e
DV		 1361 break;
1362 default:
1363 OVS_NOT_REACHED();
1364 /* no break */
1365 }
1366 if (old_state != p->port_information_sm_state) {
1367 r->changes = true;
4b30ba05
JR		 1368 VLOG_DBG("%s, port %u: Port_information_sm %d -> %d", p->rstp->name,
1369 p->port_number, old_state, p->port_information_sm_state);
9efd308e
DV		 1370 }
1371 return 0;
1372}
1373
1374/* [17.29 Port Role Transitions state machine] */
1375
1376static void
1377set_re_root_tree(struct rstp_port *p)
f025bcb7 1378 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1379{
1380 struct rstp *r;
1381 struct rstp_port *p1;
1382
1383 r = p->rstp;
d5f31dc8 1384 HMAP_FOR_EACH (p1, node, &r->ports) {
37db915e 1385 p1->re_root = true;
9efd308e
DV		 1386 }
1387}
1388
1389static void
1390set_sync_tree(struct rstp_port *p)
f025bcb7 1391 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1392{
1393 struct rstp *r;
1394 struct rstp_port *p1;
1395
1396 r = p->rstp;
d5f31dc8 1397 HMAP_FOR_EACH (p1, node, &r->ports) {
37db915e 1398 p1->sync = true;
9efd308e
DV		 1399 }
1400}
1401
1402static int
1403hello_time(struct rstp_port *p)
f025bcb7 1404 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1405{
1406 return p->designated_times.hello_time;
1407}
1408
1409static int
1410fwd_delay(struct rstp_port *p)
f025bcb7 1411 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1412{
1413 return p->designated_times.forward_delay;
1414}
1415
1416static int
1417forward_delay(struct rstp_port *p)
f025bcb7 1418 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1419{
1420 if (p->send_rstp) {
1421 return hello_time(p);
1422 } else {
1423 return fwd_delay(p);
1424 }
1425}
1426
1427static int
1428edge_delay(struct rstp_port *p)
f025bcb7 1429 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1430{
1431 struct rstp *r;
1432
1433 r = p->rstp;
1434 if (p->oper_point_to_point_mac == 1) {
1435 return r->migrate_time;
1436 } else {
1437 return p->designated_times.max_age;
1438 }
1439}
1440
1441static int
1442check_selected_role_change(struct rstp_port *p, int current_role_state)
f025bcb7 1443 OVS_REQUIRES(rstp_mutex)
9efd308e 1444{
311fb15b
JR		 1445 if (p->selected && !p->updt_info && p->role != p->selected_role
1446 && p->selected_role != current_role_state) {
9efd308e
DV		 1447 VLOG_DBG("%s, port %u: case: current = %s role = %s selected = %d",
1448 p->rstp->name, p->port_number,
1449 rstp_port_role_name(current_role_state),
1450 rstp_port_role_name(p->role), p->selected_role);
1451 switch (p->selected_role) {
1452 case ROLE_ROOT:
1453 p->port_role_transition_sm_state =
1454 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1455 return true;
1456 case ROLE_DESIGNATED:
1457 p->port_role_transition_sm_state =
1458 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1459 return true;
1460 case ROLE_ALTERNATE:
1461 p->port_role_transition_sm_state =
1462 PORT_ROLE_TRANSITION_SM_BLOCK_PORT_EXEC;
1463 return true;
1464 case ROLE_BACKUP:
1465 p->port_role_transition_sm_state =
1466 PORT_ROLE_TRANSITION_SM_BLOCK_PORT_EXEC;
1467 return true;
1468 case ROLE_DISABLED:
1469 p->port_role_transition_sm_state =
1470 PORT_ROLE_TRANSITION_SM_DISABLE_PORT_EXEC;
1471 return true;
1472 }
1473 }
1474 return false;
1475}
1476
1477static int
1478re_rooted(struct rstp_port *p)
f025bcb7 1479 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1480{
1481 struct rstp *r;
1482 struct rstp_port *p1;
1483
1484 r = p->rstp;
d5f31dc8 1485 HMAP_FOR_EACH (p1, node, &r->ports) {
37db915e
JR		 1486 if ((p1 != p) && (p1->rr_while != 0)) {
1487 return false;
9efd308e
DV		 1488 }
1489 }
1490 return true;
1491}
1492
1493static int
1494all_synced(struct rstp *r)
f025bcb7 1495 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1496{
1497 struct rstp_port *p;
1498
d5f31dc8 1499 HMAP_FOR_EACH (p, node, &r->ports) {
37db915e
JR		 1500 if (!(p->selected && p->role == p->selected_role &&
1501 (p->role == ROLE_ROOT || p->synced == true))) {
1502 return false;
9efd308e
DV		 1503 }
1504 }
1505 return true;
1506}
1507
1508static int
1509port_role_transition_sm(struct rstp_port *p)
f025bcb7 1510 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1511{
1512 enum port_role_transition_state_machine old_state;
1513 struct rstp *r;
1514 enum rstp_port_role last_role;
1515
1516 old_state = p->port_role_transition_sm_state;
1517 r = p->rstp;
1518 last_role = p->role;
1519
1520 switch (p->port_role_transition_sm_state) {
1521 case PORT_ROLE_TRANSITION_SM_INIT:
1522 if (r->begin) {
1523 p->port_role_transition_sm_state =
1524 PORT_ROLE_TRANSITION_SM_INIT_PORT_EXEC;
1525 }
1526 break;
1527 case PORT_ROLE_TRANSITION_SM_INIT_PORT_EXEC:
1528 p->role = ROLE_DISABLED;
1529 p->learn = p->forward = false;
1530 p->synced = false;
1531 p->sync = p->re_root = true;
1532 p->rr_while = p->designated_times.forward_delay;
1533 p->fd_while = p->designated_times.max_age;
1534 p->rb_while = 0;
1535 p->port_role_transition_sm_state =
1536 PORT_ROLE_TRANSITION_SM_DISABLE_PORT_EXEC;
1537 break;
1538 case PORT_ROLE_TRANSITION_SM_DISABLE_PORT_EXEC:
1539 p->role = p->selected_role;
1540 p->learn = p->forward = false;
1541 p->port_role_transition_sm_state =
1542 PORT_ROLE_TRANSITION_SM_DISABLE_PORT;
1543 /* no break */
1544 case PORT_ROLE_TRANSITION_SM_DISABLE_PORT:
1545 if (check_selected_role_change(p, ROLE_DISABLED)) {
6448df94 1546 /* Global transition. */
311fb15b
JR		 1547 } else if (p->selected && !p->updt_info && !p->learning
1548 && !p->forwarding) {
9efd308e
DV		 1549 p->port_role_transition_sm_state =
1550 PORT_ROLE_TRANSITION_SM_DISABLED_PORT_EXEC;
1551 }
1552 break;
1553 case PORT_ROLE_TRANSITION_SM_DISABLED_PORT_EXEC:
1554 p->fd_while = p->designated_times.max_age;
1555 p->synced = true;
1556 p->rr_while = 0;
1557 p->sync = p->re_root = false;
1558 p->port_role_transition_sm_state =
1559 PORT_ROLE_TRANSITION_SM_DISABLED_PORT;
1560 /* no break */
1561 case PORT_ROLE_TRANSITION_SM_DISABLED_PORT:
1562 if (check_selected_role_change(p, ROLE_DISABLED)) {
6448df94 1563 /* Global transition. */
311fb15b
JR		 1564 } else if (p->selected && !p->updt_info
1565 && (p->fd_while != p->designated_times.max_age || p->sync
1566 || p->re_root || !p->synced)) {
9efd308e
DV		 1567 p->port_role_transition_sm_state =
1568 PORT_ROLE_TRANSITION_SM_DISABLED_PORT_EXEC;
1569 }
1570 break;
1571 case PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC:
1572 p->role = ROLE_ROOT;
1573 p->rr_while = p->designated_times.forward_delay;
1574 p->port_role_transition_sm_state = PORT_ROLE_TRANSITION_SM_ROOT_PORT;
1575 /* no break */
1576 case PORT_ROLE_TRANSITION_SM_ROOT_PORT:
1577 if (check_selected_role_change(p, ROLE_ROOT)) {
6448df94 1578 /* Global transition. */
311fb15b 1579 } else if (p->selected && !p->updt_info) {
9efd308e
DV		 1580 if (p->rr_while != p->designated_times.forward_delay) {
1581 p->port_role_transition_sm_state =
1582 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1583 break;
311fb15b 1584 } else if (p->re_root && p->forward) {
9efd308e
DV		 1585 p->port_role_transition_sm_state =
1586 PORT_ROLE_TRANSITION_SM_REROOTED_EXEC;
1587 break;
311fb15b
JR		 1588 } else if ((p->fd_while == 0
1589 || ((re_rooted(p) && p->rb_while == 0)
1590 && r->rstp_version)) && !p->learn) {
9efd308e
DV		 1591 p->port_role_transition_sm_state =
1592 PORT_ROLE_TRANSITION_SM_ROOT_LEARN_EXEC;
1593 break;
311fb15b
JR		 1594 } else if ((p->fd_while == 0
1595 || ((re_rooted(p) && p->rb_while == 0)
1596 && r->rstp_version)) && p->learn && !p->forward) {
9efd308e
DV		 1597 p->port_role_transition_sm_state =
1598 PORT_ROLE_TRANSITION_SM_ROOT_FORWARD_EXEC;
1599 break;
311fb15b 1600 } else if (p->proposed && !p->agree) {
9efd308e
DV		 1601 p->port_role_transition_sm_state =
1602 PORT_ROLE_TRANSITION_SM_ROOT_PROPOSED_EXEC;
1603 break;
311fb15b
JR		 1604 } else if ((all_synced(r) && !p->agree) ||
1605 (p->proposed && p->agree)) {
9efd308e
DV		 1606 p->port_role_transition_sm_state =
1607 PORT_ROLE_TRANSITION_SM_ROOT_AGREED_EXEC;
1608 break;
311fb15b 1609 } else if (!p->forward && !p->re_root) {
9efd308e
DV		 1610 p->port_role_transition_sm_state =
1611 PORT_ROLE_TRANSITION_SM_REROOT_EXEC;
1612 break;
1613 }
1614 }
6448df94 1615 break;
9efd308e 1616 case PORT_ROLE_TRANSITION_SM_REROOT_EXEC:
6448df94
JR		 1617 if (check_selected_role_change(p, ROLE_ROOT)) {
1618 /* Global transition. */
1619 } else {
1620 set_re_root_tree(p);
1621 p->port_role_transition_sm_state =
1622 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1623 }
9efd308e
DV		 1624 break;
1625 case PORT_ROLE_TRANSITION_SM_ROOT_AGREED_EXEC:
6448df94
JR		 1626 if (check_selected_role_change(p, ROLE_ROOT)) {
1627 /* Global transition. */
1628 } else {
1629 p->proposed = p->sync = false;
1630 p->agree = p->new_info = true;
1631 p->port_role_transition_sm_state =
1632 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1633 }
9efd308e
DV		 1634 break;
1635 case PORT_ROLE_TRANSITION_SM_ROOT_PROPOSED_EXEC:
1636 set_sync_tree(p);
1637 p->proposed = false;
6448df94
JR		 1638 if (check_selected_role_change(p, ROLE_ROOT)) {
1639 /* Global transition. */
1640 } else {
1641 p->port_role_transition_sm_state =
1642 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1643 }
9efd308e
DV		 1644 break;
1645 case PORT_ROLE_TRANSITION_SM_ROOT_FORWARD_EXEC:
1646 p->fd_while = 0;
1647 p->forward = true;
6448df94
JR		 1648 if (check_selected_role_change(p, ROLE_ROOT)) {
1649 /* Global transition. */
1650 } else {
1651 p->port_role_transition_sm_state =
1652 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1653 }
9efd308e
DV		 1654 break;
1655 case PORT_ROLE_TRANSITION_SM_ROOT_LEARN_EXEC:
1656 p->fd_while = forward_delay(p);
1657 p->learn = true;
6448df94
JR		 1658 if (check_selected_role_change(p, ROLE_ROOT)) {
1659 /* Global transition. */
1660 } else {
1661 p->port_role_transition_sm_state =
1662 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1663 }
9efd308e
DV		 1664 break;
1665 case PORT_ROLE_TRANSITION_SM_REROOTED_EXEC:
1666 p->re_root = false;
6448df94
JR		 1667 if (check_selected_role_change(p, ROLE_ROOT)) {
1668 /* Global transition. */
1669 } else {
1670 p->port_role_transition_sm_state =
1671 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1672 }
9efd308e
DV		 1673 break;
1674 case PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC:
1675 p->role = ROLE_DESIGNATED;
1676 p->port_role_transition_sm_state =
1677 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT;
1678 /* no break */
1679 case PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT:
1680 if (check_selected_role_change(p, ROLE_DESIGNATED)) {
6448df94 1681 /* Global transition. */
311fb15b
JR		 1682 } else if (p->selected && !p->updt_info) {
1683 if (((p->sync && !p->synced)
1684 || (p->re_root && p->rr_while != 0) || p->disputed)
1685 && !p->oper_edge && (p->learn || p->forward)) {
1686 p->port_role_transition_sm_state =
1687 PORT_ROLE_TRANSITION_SM_DESIGNATED_DISCARD_EXEC;
1688 } else if ((p->fd_while == 0 || p->agreed || p->oper_edge)
1689 && (p->rr_while == 0 || !p->re_root)
1690 && !p->sync && !p->learn) {
9efd308e
DV		 1691 p->port_role_transition_sm_state =
1692 PORT_ROLE_TRANSITION_SM_DESIGNATED_LEARN_EXEC;
311fb15b
JR		 1693 } else if ((p->fd_while == 0 || p->agreed || p->oper_edge)
1694 && (p->rr_while == 0 || !p->re_root)
1695 && !p->sync && (p->learn && !p->forward)) {
9efd308e
DV		 1696 p->port_role_transition_sm_state =
1697 PORT_ROLE_TRANSITION_SM_DESIGNATED_FORWARD_EXEC;
311fb15b
JR		 1698 } else if (!p->forward && !p->agreed && !p->proposing &&
1699 !p->oper_edge) {
9efd308e
DV		 1700 p->port_role_transition_sm_state =
1701 PORT_ROLE_TRANSITION_SM_DESIGNATED_PROPOSE_EXEC;
311fb15b
JR		 1702 } else if ((!p->learning && !p->forwarding && !p->synced)
1703 || (p->agreed && !p->synced)
1704 || (p->oper_edge && !p->synced)
1705 || (p->sync && p->synced)) {
9efd308e
DV		 1706 p->port_role_transition_sm_state =
1707 PORT_ROLE_TRANSITION_SM_DESIGNATED_SYNCED_EXEC;
311fb15b 1708 } else if (p->rr_while == 0 && p->re_root) {
9efd308e
DV		 1709 p->port_role_transition_sm_state =
1710 PORT_ROLE_TRANSITION_SM_DESIGNATED_RETIRED_EXEC;
1711 }
1712 }
1713 break;
1714 case PORT_ROLE_TRANSITION_SM_DESIGNATED_RETIRED_EXEC:
1715 p->re_root = false;
6448df94
JR		 1716 if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1717 /* Global transition. */
1718 } else {
1719 p->port_role_transition_sm_state =
1720 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1721 }
9efd308e
DV		 1722 break;
1723 case PORT_ROLE_TRANSITION_SM_DESIGNATED_SYNCED_EXEC:
1724 p->rr_while = 0;
1725 p->synced = true;
1726 p->sync = false;
6448df94
JR		 1727 if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1728 /* Global transition. */
1729 } else {
1730 p->port_role_transition_sm_state =
1731 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1732 }
9efd308e
DV		 1733 break;
1734 case PORT_ROLE_TRANSITION_SM_DESIGNATED_PROPOSE_EXEC:
1735 p->proposing = true;
1736 p->edge_delay_while = edge_delay(p);
1737 p->new_info = true;
6448df94
JR		 1738 if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1739 /* Global transition. */
1740 } else {
1741 p->port_role_transition_sm_state =
1742 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1743 }
9efd308e
DV		 1744 break;
1745 case PORT_ROLE_TRANSITION_SM_DESIGNATED_FORWARD_EXEC:
1746 p->forward = true;
1747 p->fd_while = 0;
1748 p->agreed = p->send_rstp;
6448df94
JR		 1749 if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1750 /* Global transition. */
1751 } else {
1752 p->port_role_transition_sm_state =
1753 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1754 }
9efd308e
DV		 1755 break;
1756 case PORT_ROLE_TRANSITION_SM_DESIGNATED_LEARN_EXEC:
1757 p->learn = true;
1758 p->fd_while = forward_delay(p);
6448df94
JR		 1759 if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1760 /* Global transition. */
1761 } else {
1762 p->port_role_transition_sm_state =
1763 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1764 }
9efd308e
DV		 1765 break;
1766 case PORT_ROLE_TRANSITION_SM_DESIGNATED_DISCARD_EXEC:
1767 p->learn = p->forward = p->disputed = false;
1768 p->fd_while = forward_delay(p);
6448df94
JR		 1769 if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1770 /* Global transition. */
1771 } else {
1772 p->port_role_transition_sm_state =
1773 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1774 }
9efd308e
DV		 1775 break;
1776 case PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC:
1777 p->fd_while = p->designated_times.forward_delay;
1778 p->synced = true;
1779 p->rr_while = 0;
1780 p->sync = p->re_root = false;
1781 p->port_role_transition_sm_state =
1782 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT;
1783 /* no break */
1784 case PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT:
1785 if (check_selected_role_change(p, ROLE_ALTERNATE)) {
6448df94 1786 /* Global transition. */
311fb15b
JR		 1787 } else if (p->selected && !p->updt_info) {
1788 if (p->rb_while != 2 * p->designated_times.hello_time
1789 && p->role == ROLE_BACKUP) {
9efd308e
DV		 1790 p->port_role_transition_sm_state =
1791 PORT_ROLE_TRANSITION_SM_BACKUP_PORT_EXEC;
311fb15b
JR		 1792 } else if ((p->fd_while != forward_delay(p)) || p->sync
1793 || p->re_root || !p->synced) {
9efd308e
DV		 1794 p->port_role_transition_sm_state =
1795 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
311fb15b 1796 } else if (p->proposed && !p->agree) {
9efd308e
DV		 1797 p->port_role_transition_sm_state =
1798 PORT_ROLE_TRANSITION_SM_ALTERNATE_PROPOSED_EXEC;
311fb15b
JR		 1799 } else if ((all_synced(r) && !p->agree)
1800 || (p->proposed && p->agree)) {
9efd308e 1801 p->port_role_transition_sm_state =
7ccf8d38 1802 PORT_ROLE_TRANSITION_SM_ALTERNATE_AGREED_EXEC;
9efd308e
DV		 1803 }
1804 }
1805 break;
7ccf8d38 1806 case PORT_ROLE_TRANSITION_SM_ALTERNATE_AGREED_EXEC:
9efd308e
DV		 1807 p->proposed = false;
1808 p->agree = true;
1809 p->new_info = true;
6448df94
JR		 1810 if (check_selected_role_change(p, ROLE_ALTERNATE)) {
1811 /* Global transition. */
1812 } else {
1813 p->port_role_transition_sm_state =
1814 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1815 }
9efd308e
DV		 1816 break;
1817 case PORT_ROLE_TRANSITION_SM_ALTERNATE_PROPOSED_EXEC:
1818 set_sync_tree(p);
1819 p->proposed = false;
6448df94
JR		 1820 if (check_selected_role_change(p, ROLE_ALTERNATE)) {
1821 /* Global transition. */
1822 } else {
1823 p->port_role_transition_sm_state =
1824 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1825 }
9efd308e
DV		 1826 break;
1827 case PORT_ROLE_TRANSITION_SM_BLOCK_PORT_EXEC:
1828 p->role = p->selected_role;
1829 p->learn = p->forward = false;
1830 p->port_role_transition_sm_state = PORT_ROLE_TRANSITION_SM_BLOCK_PORT;
1831 /* no break */
1832 case PORT_ROLE_TRANSITION_SM_BLOCK_PORT:
1833 if (check_selected_role_change(p, ROLE_ALTERNATE)) {
6448df94 1834 /* Global transition. */
311fb15b
JR		 1835 } else if (p->selected && !p->updt_info && !p->learning &&
1836 !p->forwarding) {
9efd308e
DV		 1837 p->port_role_transition_sm_state =
1838 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1839 }
1840 break;
1841 case PORT_ROLE_TRANSITION_SM_BACKUP_PORT_EXEC:
1842 p->rb_while = 2 * p->designated_times.hello_time;
6448df94
JR		 1843 if (check_selected_role_change(p, ROLE_ALTERNATE)) {
1844 /* Global transition. */
1845 } else {
1846 p->port_role_transition_sm_state =
1847 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1848 }
9efd308e
DV		 1849 break;
1850 default:
1851 OVS_NOT_REACHED();
1852 /* no break */
1853 }
1854 if (old_state != p->port_role_transition_sm_state) {
1855 r->changes = true;
1856 VLOG_DBG("%s, port %u: Port_role_transition_sm %d -> %d",
1857 p->rstp->name, p->port_number, old_state,
1858 p->port_role_transition_sm_state);
1859 }
1860 if (last_role != p->role) {
9efd308e
DV		 1861 VLOG_DBG("%s, port %u, port role ["RSTP_PORT_ID_FMT"] = %s",
1862 p->rstp->name, p->port_number, p->port_id,
1863 rstp_port_role_name(p->role));
1864 }
1865 return 0;
1866}
1867
1868/* [17.30 - Port state transition state machine] */
1869
1870static void
1871enable_learning(struct rstp_port *p)
f025bcb7 1872 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1873{
1874 /* [17.21.6 enableLearning()] An implementation dependent procedure that
1875 * causes the Learning Process (7.8) to start learning from frames received
1876 * on the Port. The procedure does not complete until learning has been
1877 * enabled.
1878 */
f025bcb7 1879 rstp_port_set_state__(p, RSTP_LEARNING);
9efd308e
DV		 1880}
1881
1882static void
1883enable_forwarding(struct rstp_port *p)
f025bcb7 1884 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1885{
1886 /* [17.21.5 enableForwarding()] An implementation dependent procedure that
1887 * causes the Forwarding Process (7.7) to start forwarding frames through
1888 * the Port. The procedure does not complete until forwarding has been
1889 * enabled.
1890 */
f025bcb7 1891 rstp_port_set_state__(p, RSTP_FORWARDING);
9efd308e
DV		 1892}
1893
1894static void
1895disable_learning(struct rstp_port *p)
f025bcb7 1896 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1897{
1898 /* [17.21.4 - disableLearning()] An implementation dependent procedure that
1899 * causes the Learning Process (7.8) to stop learning from the source
1900 * address of frames received on the Port. The procedure does not complete
1901 * until learning has stopped.
1902 */
f025bcb7 1903 rstp_port_set_state__(p, RSTP_DISCARDING);
9efd308e
DV		 1904}
1905
1906static void
1907disable_forwarding(struct rstp_port *p)
f025bcb7 1908 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1909{
1910 /* [17.21.3 - disableForwarding()] An implementation dependent procedure
1911 * that causes the Forwarding Process (7.7) to stop forwarding frames
1912 * through the Port. The procedure does not complete until forwarding has
1913 * stopped.
1914 */
f025bcb7 1915 rstp_port_set_state__(p, RSTP_DISCARDING);
9efd308e
DV		 1916}
1917
1918static int
1919port_state_transition_sm(struct rstp_port *p)
f025bcb7 1920 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1921{
1922 enum port_state_transition_state_machine old_state;
1923 struct rstp *r;
1924
1925 old_state = p->port_state_transition_sm_state;
1926 r = p->rstp;
1927
1928 switch (p->port_state_transition_sm_state) {
1929 case PORT_STATE_TRANSITION_SM_INIT:
1930 if (r->begin) {
1931 p->port_state_transition_sm_state =
1932 PORT_STATE_TRANSITION_SM_DISCARDING_EXEC;
1933 }
1934 break;
1935 case PORT_STATE_TRANSITION_SM_DISCARDING_EXEC:
1936 disable_learning(p);
1937 p->learning = false;
1938 disable_forwarding(p);
1939 p->forwarding = false;
1940 p->port_state_transition_sm_state =
1941 PORT_STATE_TRANSITION_SM_DISCARDING;
1942 /* no break */
1943 case PORT_STATE_TRANSITION_SM_DISCARDING:
1944 if (p->learn) {
1945 p->port_state_transition_sm_state =
1946 PORT_STATE_TRANSITION_SM_LEARNING_EXEC;
1947 }
1948 break;
1949 case PORT_STATE_TRANSITION_SM_LEARNING_EXEC:
1950 enable_learning(p);
1951 p->learning = true;
1952 p->port_state_transition_sm_state = PORT_STATE_TRANSITION_SM_LEARNING;
1953 /* no break */
1954 case PORT_STATE_TRANSITION_SM_LEARNING:
1955 if (!p->learn) {
1956 p->port_state_transition_sm_state =
1957 PORT_STATE_TRANSITION_SM_DISCARDING_EXEC;
311fb15b 1958 } else if (p->forward) {
9efd308e
DV		 1959 p->port_state_transition_sm_state =
1960 PORT_STATE_TRANSITION_SM_FORWARDING_EXEC;
1961 }
1962 break;
1963 case PORT_STATE_TRANSITION_SM_FORWARDING_EXEC:
1964 enable_forwarding(p);
1965 p->forwarding = true;
1966 p->port_state_transition_sm_state =
1967 PORT_STATE_TRANSITION_SM_FORWARDING;
1968 /* no break */
1969 case PORT_STATE_TRANSITION_SM_FORWARDING:
1970 if (!p->forward) {
1971 p->port_state_transition_sm_state =
1972 PORT_STATE_TRANSITION_SM_DISCARDING_EXEC;
1973 }
1974 break;
1975 default:
1976 OVS_NOT_REACHED();
1977 /* no break */
1978 }
1979 if (old_state != p->port_state_transition_sm_state) {
1980 r->changes = true;
1981 VLOG_DBG("%s, port %u: Port_state_transition_sm %d -> %d",
1982 p->rstp->name, p->port_number, old_state,
1983 p->port_state_transition_sm_state);
1984 }
1985 return 0;
1986}
1987
1988/* [17.31 - Topology Change state machine] */
1989
1990static void
1991new_tc_while(struct rstp_port *p)
f025bcb7 1992 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1993{
1994 struct rstp *r;
1995
1996 r = p->rstp;
1997 if (p->tc_while == 0 && p->send_rstp == true) {
1998 p->tc_while = r->bridge_hello_time + 1;
1999 p->new_info = true;
311fb15b 2000 } else if (p->tc_while == 0 && p->send_rstp == false) {
9efd308e
DV		 2001 p->tc_while = r->bridge_max_age + r->bridge_forward_delay;
2002 }
2003}
2004
2005/* [17.21.18 setTcPropTree()]
2006 * Sets tcprop for all Ports except the Port that called the procedure.
2007 */
2008static void
2009set_tc_prop_tree(struct rstp_port *p)
f025bcb7 2010 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 2011{
2012 struct rstp *r;
2013 struct rstp_port *p1;
2014
2015 r = p->rstp;
d5f31dc8 2016 HMAP_FOR_EACH (p1, node, &r->ports) {
37db915e
JR		 2017 /* Set tc_prop on every port, except the one calling this
2018 * function. */
2019 if (p1->port_number != p->port_number) {
2020 p1->tc_prop = true;
9efd308e
DV		 2021 }
2022 }
2023}
2024
2025static void
2026set_tc_prop_bridge(struct rstp_port *p) /* not specified in 802.1D-2004. */
f025bcb7 2027 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 2028{
2029 set_tc_prop_tree(p); /* see 802.1w-2001. */
2030}
2031
2032static int
2033topology_change_sm(struct rstp_port *p)
f025bcb7 2034 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 2035{
2036 enum topology_change_state_machine old_state;
2037 struct rstp *r;
2038
2039 old_state = p->topology_change_sm_state;
2040 r = p->rstp;
2041
2042 switch (p->topology_change_sm_state) {
2043 case TOPOLOGY_CHANGE_SM_INIT:
2044 if (r->begin) {
2045 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_INACTIVE_EXEC;
2046 }
2047 break;
2048 case TOPOLOGY_CHANGE_SM_INACTIVE_EXEC:
2049 p->fdb_flush = true;
2050 p->tc_while = 0;
2051 p->tc_ack = false;
2052 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_INACTIVE;
2053 /* no break */
2054 case TOPOLOGY_CHANGE_SM_INACTIVE:
2055 if (p->learn && !p->fdb_flush) {
2056 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING_EXEC;
2057 }
2058 break;
2059 case TOPOLOGY_CHANGE_SM_LEARNING_EXEC:
2060 p->rcvd_tc = p->rcvd_tcn = p->rcvd_tc_ack = false;
2061 p->tc_prop = p->rcvd_tc_ack = false;
2062 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING;
2063 /* no break */
2064 case TOPOLOGY_CHANGE_SM_LEARNING:
311fb15b 2065 if (p->role != ROLE_ROOT && p->role != ROLE_DESIGNATED &&
9efd308e 2066 !(p->learn || p->learning) && !(p->rcvd_tc || p->rcvd_tcn ||
311fb15b 2067 p->rcvd_tc_ack || p->tc_prop)) {
9efd308e 2068 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_INACTIVE_EXEC;
311fb15b 2069 } else if (p->rcvd_tc || p->rcvd_tcn || p->rcvd_tc_ack || p->tc_prop) {
9efd308e 2070 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING_EXEC;
311fb15b
JR		 2071 } else if ((p->role == ROLE_ROOT || p->role == ROLE_DESIGNATED)
2072 && p->forward && !p->oper_edge) {
9efd308e
DV		 2073 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_DETECTED_EXEC;
2074 }
2075 break;
2076 case TOPOLOGY_CHANGE_SM_DETECTED_EXEC:
2077 new_tc_while(p);
2078 set_tc_prop_tree(p);
2079 p->new_info = true;
2080 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE_EXEC;
2081 /* no break */
2082 case TOPOLOGY_CHANGE_SM_ACTIVE_EXEC:
2083 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
2084 /* no break */
2085 case TOPOLOGY_CHANGE_SM_ACTIVE:
311fb15b
JR		 2086 if ((p->role != ROLE_ROOT && p->role != ROLE_DESIGNATED)
2087 || p->oper_edge) {
9efd308e 2088 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING_EXEC;
311fb15b 2089 } else if (p->rcvd_tcn) {
9efd308e 2090 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_NOTIFIED_TCN_EXEC;
311fb15b 2091 } else if (p->rcvd_tc) {
9efd308e 2092 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_NOTIFIED_TC_EXEC;
311fb15b 2093 } else if (p->tc_prop && !p->oper_edge) {
9efd308e 2094 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_PROPAGATING_EXEC;
311fb15b 2095 } else if (p->rcvd_tc_ack) {
9efd308e
DV		 2096 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACKNOWLEDGED_EXEC;
2097 }
2098 break;
2099 case TOPOLOGY_CHANGE_SM_ACKNOWLEDGED_EXEC:
2100 p->tc_while = 0;
2101 p->rcvd_tc_ack = false;
2102 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
2103 break;
2104 case TOPOLOGY_CHANGE_SM_PROPAGATING_EXEC:
2105 new_tc_while(p);
2106 p->fdb_flush = true;
2107 p->tc_prop = false;
2108 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
2109 break;
2110 case TOPOLOGY_CHANGE_SM_NOTIFIED_TC_EXEC:
2111 p->rcvd_tcn = p->rcvd_tc = false;
2112 if (p->role == ROLE_DESIGNATED) {
2113 p->tc_ack = true;
2114 }
2115 set_tc_prop_bridge(p);
2116 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
2117 break;
2118 case TOPOLOGY_CHANGE_SM_NOTIFIED_TCN_EXEC:
2119 new_tc_while(p);
75735c80 2120 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_NOTIFIED_TC_EXEC;
9efd308e
DV		 2121 break;
2122 default:
2123 OVS_NOT_REACHED();
2124 /* no break */
2125 }
2126 if (old_state != p->topology_change_sm_state) {
2127 r->changes = true;
4b30ba05
JR		 2128 VLOG_DBG("%s, port %u: Topology_change_sm %d -> %d", p->rstp->name,
2129 p->port_number, old_state, p->topology_change_sm_state);
9efd308e
DV		 2130 }
2131 return 0;
2132}
2133
2134/****************************************************************************
2135 * [17.6] Priority vector calculation helper functions
2136 ****************************************************************************/
2137
a0478216
JR		 2138/* compare_rstp_priority_vectors() compares two struct rstp_priority_vectors
2139 * and returns a value indicating if the first rstp_priority_vector is
2140 * superior, same or inferior to the second one.
2141 *
2142 * Zero return value indicates INFERIOR, a non-zero return value indicates
2143 * SUPERIOR. When it makes a difference the non-zero return value SAME
2144 * indicates the priority vectors are identical (a subset of SUPERIOR).
9efd308e
DV		 2145 */
2146static enum vector_comparison
a0478216
JR		 2147compare_rstp_priority_vectors(const struct rstp_priority_vector *v1,
2148 const struct rstp_priority_vector *v2)
9efd308e 2149{
26c0e924 2150 VLOG_DBG("v1: "RSTP_ID_FMT", %u, "RSTP_ID_FMT", %d, %d",
9efd308e 2151 RSTP_ID_ARGS(v1->root_bridge_id), v1->root_path_cost,
26c0e924
DV		 2152 RSTP_ID_ARGS(v1->designated_bridge_id), v1->designated_port_id,
2153 v1->bridge_port_id);
2154 VLOG_DBG("v2: "RSTP_ID_FMT", %u, "RSTP_ID_FMT", %d, %d",
9efd308e 2155 RSTP_ID_ARGS(v2->root_bridge_id), v2->root_path_cost,
26c0e924
DV		 2156 RSTP_ID_ARGS(v2->designated_bridge_id), v2->designated_port_id,
2157 v2->bridge_port_id);
9efd308e 2158
a0478216
JR		 2159 /* [17.6]
2160 * This message priority vector is superior to the port priority vector and
2161 * will replace it if, and only if, the message priority vector is better
2162 * than the port priority vector, or the message has been transmitted from
2163 * the same Designated Bridge and Designated Port as the port priority
2164 * vector, i.e., if the following is true:
2165 *
2166 * ((RD < RootBridgeID)) ||
2167 * ((RD == RootBridgeID) && (RPCD < RootPathCost)) ||
2168 * ((RD == RootBridgeID) && (RPCD == RootPathCost) &&
2169 * (D < designated_bridge_id)) ||
2170 * ((RD == RootBridgeID) && (RPCD == RootPathCost) &&
2171 * (D == designated_bridge_id) && (PD < designated_port_id)) ||
2172 * ((D == designated_bridge_id.BridgeAddress) &&
2173 * (PD == designated_port_id.PortNumber))
2174 */
2175 if ((v1->root_bridge_id < v2->root_bridge_id)
2176 || (v1->root_bridge_id == v2->root_bridge_id
2177 && v1->root_path_cost < v2->root_path_cost)
2178 || (v1->root_bridge_id == v2->root_bridge_id
2179 && v1->root_path_cost == v2->root_path_cost
2180 && v1->designated_bridge_id < v2->designated_bridge_id)
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->designated_port_id < v2->designated_port_id)
2185 || (v1->designated_bridge_id == v2->designated_bridge_id
2186 && v1->designated_port_id == v2->designated_port_id)) {
2187 /* SAME is a subset of SUPERIOR. */
2188 if (v1->root_bridge_id == v2->root_bridge_id
2189 && v1->root_path_cost == v2->root_path_cost
2190 && v1->designated_bridge_id == v2->designated_bridge_id
2191 && v1->designated_port_id == v2->designated_port_id) {
26c0e924
DV		 2192 if (v1->bridge_port_id < v2->bridge_port_id) {
2193 VLOG_DBG("superior");
2194 return SUPERIOR;
2195 }
2196 else if (v1->bridge_port_id > v2->bridge_port_id) {
2197 VLOG_DBG("inferior");
2198 return INFERIOR;
2199 }
a0478216
JR		 2200 VLOG_DBG("superior_same");
2201 return SAME;
2202 }
2203 VLOG_DBG("superior");
9efd308e
DV		 2204 return SUPERIOR;
2205 }
a0478216
JR		 2206
2207 VLOG_DBG("inferior");
2208 return INFERIOR;
9efd308e
DV		 2209}
2210
2211static bool
311fb15b
JR		 2212rstp_times_equal(struct rstp_times *t1, struct rstp_times *t2)
2213{
2214 return t1->forward_delay == t2->forward_delay
2215 && t1->hello_time == t2->hello_time
2216 && t1->max_age == t2->max_age
2217 && t1->message_age == t2->message_age;
9efd308e 2218}
openvswitch mirror