]> 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
lldp: validate a bit more received LLDP frames
[mirror_ovs.git] / lib / rstp-state-machines.c
CommitLineData
9efd308e 1/*
eb1746e6 2 * Copyright (c) 2011-2015 M3S, Srl - Italy
9efd308e
DV		 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>
eb1746e6 24 * Carlo Andreotti <c.andreotti@m3s.it>
9efd308e
DV		 25 *
26 * References to IEEE 802.1D-2004 standard are enclosed in square brackets.
27 * E.g. [17.3], [Table 17-1], etc.
28 *
29 */
30
31#include <config.h>
32#include "rstp.h"
33#include "rstp-state-machines.h"
b2befd5b
BP		 34#include <sys/types.h>
35#include <netinet/in.h>
9efd308e
DV		 36#include <arpa/inet.h>
37#include <inttypes.h>
9efd308e 38#include <stdlib.h>
9efd308e
DV		 39#include "byte-order.h"
40#include "connectivity.h"
64c96779 41#include "openvswitch/ofpbuf.h"
cf62fa4c 42#include "dp-packet.h"
9efd308e
DV		 43#include "packets.h"
44#include "seq.h"
45#include "unixctl.h"
46#include "util.h"
e6211adc 47#include "openvswitch/vlog.h"
9efd308e
DV		 48
49VLOG_DEFINE_THIS_MODULE(rstp_sm);
50
51#define ROLE_FLAG_MASK 0xC
52#define ROLE_FLAG_SHIFT 2
53
54enum port_flag {
55 PORT_UNKN = 0,
56 PORT_ALT_BACK = 1,
57 PORT_ROOT = 2,
58 PORT_DES = 3
59};
60
61enum bpdu_size {
62 CONFIGURATION_BPDU_SIZE = 35,
63 TOPOLOGY_CHANGE_NOTIFICATION_BPDU_SIZE = 4,
64 RAPID_SPANNING_TREE_BPDU_SIZE = 36
65};
66
a0478216
JR		 67/* Same is a subset of SUPERIOR, so can be used as a boolean when the
68 * distinction is not significant. */
9efd308e
DV		 69enum vector_comparison {
70 INFERIOR = 0,
71 SUPERIOR = 1,
72 SAME = 2
73};
74
75static void decrement_timer(uint16_t *);
f025bcb7
JR		 76static void rstp_send_bpdu(struct rstp_port *, const void *, size_t)
77 OVS_REQUIRES(rstp_mutex);
78static int validate_received_bpdu(struct rstp_port *, const void *, size_t)
79 OVS_REQUIRES(rstp_mutex);
9efd308e
DV		 80static ovs_be16 time_encode(uint8_t);
81static uint8_t time_decode(ovs_be16);
82static enum vector_comparison
a0478216
JR		 83compare_rstp_priority_vectors(const struct rstp_priority_vector *,
84 const struct rstp_priority_vector *);
9efd308e
DV		 85static bool rstp_times_equal(struct rstp_times *, struct rstp_times *);
86
87/* Per-Bridge State Machine */
f025bcb7
JR		 88static int port_role_selection_sm(struct rstp *)
89 OVS_REQUIRES(rstp_mutex);
9efd308e 90/* Per-Port State Machines */
f025bcb7
JR		 91static int port_receive_sm(struct rstp_port *)
92 OVS_REQUIRES(rstp_mutex);
93static int port_protocol_migration_sm(struct rstp_port *)
94 OVS_REQUIRES(rstp_mutex);
95static int bridge_detection_sm(struct rstp_port *)
96 OVS_REQUIRES(rstp_mutex);
97static int port_transmit_sm(struct rstp_port *)
98 OVS_REQUIRES(rstp_mutex);
99static int port_information_sm(struct rstp_port *)
100 OVS_REQUIRES(rstp_mutex);
101static int port_role_transition_sm(struct rstp_port *)
102 OVS_REQUIRES(rstp_mutex);
103static int port_state_transition_sm(struct rstp_port *)
104 OVS_REQUIRES(rstp_mutex);
105static int topology_change_sm(struct rstp_port *)
106 OVS_REQUIRES(rstp_mutex);
9efd308e
DV		 107/* port_timers_sm() not defined as a state machine */
108
109void
006f3386 110process_received_bpdu__(struct rstp_port *p, const void *bpdu_,
f025bcb7
JR		 111 size_t bpdu_size)
112 OVS_REQUIRES(rstp_mutex)
9efd308e 113{
006f3386
JR		 114 struct rstp *rstp = p->rstp;
115 struct rstp_bpdu *bpdu = (struct rstp_bpdu *)bpdu_;
9efd308e 116
311fb15b 117 if (!p->port_enabled) {
9efd308e 118 return;
311fb15b
JR		 119 }
120 if (p->rcvd_bpdu) {
9efd308e 121 return;
311fb15b 122 }
006f3386
JR		 123
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.
128 */
129 if (bpdu->bpdu_type == RAPID_SPANNING_TREE_BPDU) {
130 uint8_t role = (bpdu->flags & ROLE_FLAG_MASK) >> ROLE_FLAG_SHIFT;
131
132 if (role == PORT_UNKN) {
133 bpdu->bpdu_type = CONFIGURATION_BPDU;
134 }
135 }
136
9efd308e
DV		 137 if (validate_received_bpdu(p, bpdu, bpdu_size) == 0) {
138 p->rcvd_bpdu = true;
139 p->rx_rstp_bpdu_cnt++;
140
141 memcpy(&p->received_bpdu_buffer, bpdu, sizeof(struct rstp_bpdu));
142
143 rstp->changes = true;
f025bcb7 144 move_rstp__(rstp);
9efd308e 145 } else {
f025bcb7 146 VLOG_DBG("%s, port %u: Bad STP or RSTP BPDU received", p->rstp->name,
4b30ba05 147 p->port_number);
9efd308e
DV		 148 p->error_count++;
149 }
150}
151
311fb15b 152/* Returns 0 on success. */
9efd308e
DV		 153static int
154validate_received_bpdu(struct rstp_port *p, const void *bpdu, size_t bpdu_size)
f025bcb7 155 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 156{
157 /* Validation of received BPDU, see [9.3.4]. */
158 const struct rstp_bpdu *temp;
159
160 temp = bpdu;
161 if (bpdu_size < TOPOLOGY_CHANGE_NOTIFICATION_BPDU_SIZE ||
162 ntohs(temp->protocol_identifier) != 0) {
163 return -1;
164 } else {
311fb15b
JR		 165 if (temp->bpdu_type == CONFIGURATION_BPDU
166 && bpdu_size >= CONFIGURATION_BPDU_SIZE
167 && (time_decode(temp->message_age) < time_decode(temp->max_age))) {
9efd308e 168 if ((ntohll(temp->designated_bridge_id) !=
311fb15b
JR		 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))) {
9efd308e 173 return 0;
311fb15b 174 } else {
9efd308e
DV		 175 return -1;
176 }
177 } else if (temp->bpdu_type == TOPOLOGY_CHANGE_NOTIFICATION_BPDU) {
178 return 0;
179 } else if (temp->bpdu_type == RAPID_SPANNING_TREE_BPDU &&
180 bpdu_size >= RAPID_SPANNING_TREE_BPDU_SIZE) {
181 return 0;
311fb15b 182 } else {
9efd308e
DV		 183 return -1;
184 }
185 }
186}
187
188/*
f025bcb7
JR		 189 * move_rstp__()
190 * This method is invoked to move the State Machines. The SMs move only if the
9efd308e
DV		 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
311fb15b 194 * received, a timer expires or port down event is detected. If a parameter is
9efd308e
DV		 195 * set by management, then 'changes' is set.
196 */
197#define MAX_RSTP_ITERATIONS 1000 /* safeguard */
198int
f025bcb7
JR		 199move_rstp__(struct rstp *rstp)
200 OVS_REQUIRES(rstp_mutex)
9efd308e 201{
9efd308e
DV		 202 int num_iterations;
203 num_iterations = 0;
204
205 while (rstp->changes == true && num_iterations < MAX_RSTP_ITERATIONS) {
311fb15b
JR		 206 struct rstp_port *p;
207
9efd308e 208 VLOG_DBG("%s: move_rstp()", rstp->name);
311fb15b 209
9efd308e
DV		 210 rstp->changes = false;
211 port_role_selection_sm(rstp);
d5f31dc8 212 HMAP_FOR_EACH (p, node, &rstp->ports) {
37db915e
JR		 213 if (p->rstp_state != RSTP_DISABLED) {
214 port_receive_sm(p);
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);
220 port_transmit_sm(p);
221 port_protocol_migration_sm(p);
9efd308e
DV		 222 }
223 }
224 num_iterations++;
225 seq_change(connectivity_seq_get());
226 }
227 if (num_iterations >= MAX_RSTP_ITERATIONS) {
228 VLOG_ERR("%s: move_rstp() reached the iteration safeguard limit!",
229 rstp->name);
230 }
231 return 0;
232}
233
f025bcb7
JR		 234void decrease_rstp_port_timers__(struct rstp *r)
235 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 236{
237 struct rstp_port *p;
238
d5f31dc8 239 HMAP_FOR_EACH (p, node, &r->ports) {
37db915e
JR		 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);
249 p->uptime += 1;
9efd308e
DV		 250 }
251 r->changes = true;
f025bcb7 252 move_rstp__(r);
9efd308e
DV		 253}
254
255static void
256decrement_timer(uint16_t *timer)
257{
258 if (*timer != 0) {
259 *timer -= 1;
260 }
261}
262
263/* Bridge State Machine. */
264/* [17.28] Port Role Selection state machine. */
265
266static void
267updt_role_disabled_tree(struct rstp *r)
f025bcb7 268 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 269{
270 struct rstp_port *p;
271
d5f31dc8 272 HMAP_FOR_EACH (p, node, &r->ports) {
37db915e 273 p->selected_role = ROLE_DISABLED;
9efd308e
DV		 274 }
275}
276
277static void
278clear_reselect_tree(struct rstp *r)
f025bcb7 279 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 280{
281 struct rstp_port *p;
282
d5f31dc8 283 HMAP_FOR_EACH (p, node, &r->ports) {
37db915e 284 p->reselect = false;
9efd308e
DV		 285 }
286}
287
288void
f025bcb7
JR		 289updt_roles_tree__(struct rstp *r)
290 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 291{
292 struct rstp_port *p;
293 int vsel;
294 struct rstp_priority_vector best_vector, candidate_vector;
2372c146
JR		 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;
9efd308e 298
2372c146
JR		 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);
302 }
9efd308e
DV		 303 vsel = -1;
304 best_vector = r->bridge_priority;
305 /* Letter c1) */
306 r->root_times = r->bridge_times;
307 /* Letters a) b) c) */
d5f31dc8 308 HMAP_FOR_EACH (p, node, &r->ports) {
37db915e
JR		 309 uint32_t old_root_path_cost;
310 uint32_t root_path_cost;
311fb15b 311
37db915e
JR		 312 if (p->info_is != INFO_IS_RECEIVED) {
313 continue;
314 }
315 /* [17.6] */
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;
321
322 if ((candidate_vector.designated_bridge_id & 0xffffffffffffULL) ==
323 (r->bridge_priority.designated_bridge_id & 0xffffffffffffULL)) {
55f8993c 324 continue;
37db915e
JR		 325 }
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;
2372c146 332 new_root_old_role = p->role;
9efd308e
DV		 333 }
334 }
335 r->root_priority = best_vector;
336 r->root_port_id = best_vector.bridge_port_id;
4b30ba05 337 VLOG_DBG("%s: new Root is "RSTP_ID_FMT, r->name,
9efd308e 338 RSTP_ID_ARGS(r->root_priority.root_bridge_id));
2372c146
JR		 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);
342 }
343 /* Shift learned MAC addresses from an old Root Port to an existing
344 * Alternate Port. */
345 if (!r->root_changed
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;
351 }
9efd308e 352 /* Letters d) e) */
d5f31dc8 353 HMAP_FOR_EACH (p, node, &r->ports) {
37db915e
JR		 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 =
361 p->port_id;
362 p->designated_times = r->root_times;
363 p->designated_times.hello_time = r->bridge_times.hello_time;
9efd308e 364 }
d5f31dc8 365 HMAP_FOR_EACH (p, node, &r->ports) {
37db915e
JR		 366 switch (p->info_is) {
367 case INFO_IS_DISABLED:
368 p->selected_role = ROLE_DISABLED;
369 break;
370 case INFO_IS_AGED:
371 p->updt_info = true;
372 p->selected_role = ROLE_DESIGNATED;
373 break;
374 case INFO_IS_MINE:
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)) {
9efd308e 379 p->updt_info = true;
37db915e
JR		 380 }
381 break;
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;
9efd308e 392 p->updt_info = false;
9efd308e 393 } else {
37db915e
JR		 394 p->selected_role = ROLE_BACKUP;
395 p->updt_info = false;
9efd308e 396 }
37db915e
JR		 397 } else {
398 p->selected_role = ROLE_DESIGNATED;
399 p->updt_info = true;
9efd308e 400 }
37db915e
JR		 401 break;
402 default:
403 OVS_NOT_REACHED();
73c7216a 404 /* fall through */
9efd308e
DV		 405 }
406 }
407 seq_change(connectivity_seq_get());
408}
409
410static void
411set_selected_tree(struct rstp *r)
f025bcb7 412 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 413{
414 struct rstp_port *p;
415
d5f31dc8 416 HMAP_FOR_EACH (p, node, &r->ports) {
37db915e
JR		 417 if (p->reselect) {
418 return;
9efd308e
DV		 419 }
420 }
d5f31dc8 421 HMAP_FOR_EACH (p, node, &r->ports) {
37db915e
JR		 422 p->selected = true;
423 }
9efd308e
DV		 424}
425
426static int
427port_role_selection_sm(struct rstp *r)
f025bcb7 428 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 429{
430 enum port_role_selection_state_machine old_state;
431 struct rstp_port *p;
432
433 old_state = r->port_role_selection_sm_state;
434
435 switch (r->port_role_selection_sm_state) {
436 case PORT_ROLE_SELECTION_SM_INIT:
311fb15b 437 if (r->begin) {
9efd308e
DV		 438 r->port_role_selection_sm_state =
439 PORT_ROLE_SELECTION_SM_INIT_BRIDGE_EXEC;
311fb15b 440 }
9efd308e
DV		 441 break;
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;
73c7216a 445 /* fall through */
9efd308e
DV		 446 case PORT_ROLE_SELECTION_SM_INIT_BRIDGE:
447 r->port_role_selection_sm_state =
448 PORT_ROLE_SELECTION_SM_ROLE_SELECTION_EXEC;
449 break;
450 case PORT_ROLE_SELECTION_SM_ROLE_SELECTION_EXEC:
451 clear_reselect_tree(r);
f025bcb7 452 updt_roles_tree__(r);
9efd308e
DV		 453 set_selected_tree(r);
454 r->port_role_selection_sm_state =
455 PORT_ROLE_SELECTION_SM_ROLE_SELECTION;
73c7216a 456 /* fall through */
9efd308e 457 case PORT_ROLE_SELECTION_SM_ROLE_SELECTION:
d5f31dc8 458 HMAP_FOR_EACH (p, node, &r->ports) {
37db915e
JR		 459 if (p->reselect) {
460 r->port_role_selection_sm_state =
461 PORT_ROLE_SELECTION_SM_ROLE_SELECTION_EXEC;
462 break;
9efd308e
DV		 463 }
464 }
465 break;
466 default:
467 OVS_NOT_REACHED();
73c7216a 468 /* fall through */
9efd308e
DV		 469 }
470 if (old_state != r->port_role_selection_sm_state) {
471 r->changes = true;
4b30ba05
JR		 472 VLOG_DBG("%s: Port_role_selection_sm %d -> %d", r->name,
473 old_state, r->port_role_selection_sm_state);
9efd308e
DV		 474 }
475 return 0;
476}
477
478/* Port State Machines */
479
480/* [17.23 - Port receive state machine] */
481
482static void
483updt_bpdu_version(struct rstp_port *p) /* [17.21.22] */
f025bcb7 484 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 485{
486 switch (p->received_bpdu_buffer.bpdu_type) {
487 case CONFIGURATION_BPDU:
488 case TOPOLOGY_CHANGE_NOTIFICATION_BPDU:
489 p->rcvd_rstp = false;
490 p->rcvd_stp = true;
491 break;
492 case RAPID_SPANNING_TREE_BPDU:
493 p->rcvd_rstp = true;
494 p->rcvd_stp = false;
495 break;
496 default:
497 OVS_NOT_REACHED();
73c7216a 498 /* fall through */
9efd308e
DV		 499 }
500}
501
502static int
503port_receive_sm(struct rstp_port *p)
f025bcb7 504 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 505{
506 enum port_receive_state_machine old_state;
507 struct rstp *r;
508
509 old_state = p->port_receive_sm_state;
510 r = p->rstp;
511
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;
517 }
518 break;
519 case PORT_RECEIVE_SM_DISCARD_EXEC:
520 p->rcvd_bpdu = p->rcvd_rstp = p->rcvd_stp = false;
521 p->rcvd_msg = false;
522 p->edge_delay_while = r->migrate_time;
523 p->port_receive_sm_state = PORT_RECEIVE_SM_DISCARD;
73c7216a 524 /* fall through */
9efd308e 525 case PORT_RECEIVE_SM_DISCARD:
6448df94
JR		 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) {
9efd308e
DV		 531 p->port_receive_sm_state = PORT_RECEIVE_SM_RECEIVE_EXEC;
532 }
533 break;
534 case PORT_RECEIVE_SM_RECEIVE_EXEC:
535 updt_bpdu_version(p);
536 p->oper_edge = p->rcvd_bpdu = false;
537 p->rcvd_msg = true;
538 p->edge_delay_while = r->migrate_time;
539 p->port_receive_sm_state = PORT_RECEIVE_SM_RECEIVE;
73c7216a 540 /* fall through */
9efd308e 541 case PORT_RECEIVE_SM_RECEIVE:
6448df94
JR		 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) {
9efd308e
DV		 547 p->port_receive_sm_state = PORT_RECEIVE_SM_RECEIVE_EXEC;
548 }
549 break;
550 default:
551 OVS_NOT_REACHED();
73c7216a 552 /* fall through */
9efd308e
DV		 553 }
554 if (old_state != p->port_receive_sm_state) {
555 r->changes = true;
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);
558 }
559 return 0;
560}
561
562/* [17.24 - Port Protocol Migration state machine] */
563static int
564port_protocol_migration_sm(struct rstp_port *p)
f025bcb7 565 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 566{
567 enum port_protocol_migration_state_machine old_state;
568 struct rstp *r;
569
570 old_state = p->port_protocol_migration_sm_state;
571 r = p->rstp;
572
573 switch (p->port_protocol_migration_sm_state) {
574 case PORT_PROTOCOL_MIGRATION_SM_INIT:
311fb15b
JR		 575 p->port_protocol_migration_sm_state =
576 PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP_EXEC;
73c7216a 577 /* fall through */
9efd308e
DV		 578 case PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP_EXEC:
579 p->mcheck = false;
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;
73c7216a 584 /* fall through */
9efd308e
DV		 585 case PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP:
586 if (p->mdelay_while == 0) {
311fb15b
JR		 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) {
9efd308e
DV		 590 p->port_protocol_migration_sm_state =
591 PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP_EXEC;
592 }
593 break;
594 case PORT_PROTOCOL_MIGRATION_SM_SELECTING_STP_EXEC:
311fb15b 595 p->send_rstp = false;
9efd308e
DV		 596 p->mdelay_while = r->migrate_time;
597 p->port_protocol_migration_sm_state =
598 PORT_PROTOCOL_MIGRATION_SM_SELECTING_STP;
73c7216a 599 /* fall through */
9efd308e
DV		 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;
604 }
605 break;
606 case PORT_PROTOCOL_MIGRATION_SM_SENSING_EXEC:
607 p->rcvd_rstp = false;
608 p->rcvd_stp = false;
609 p->port_protocol_migration_sm_state =
610 PORT_PROTOCOL_MIGRATION_SM_SENSING;
73c7216a 611 /* fall through */
9efd308e
DV		 612 case PORT_PROTOCOL_MIGRATION_SM_SENSING:
613 if (!p->port_enabled || p->mcheck || ((r->rstp_version) &&
311fb15b 614 !p->send_rstp && p->rcvd_rstp)) {
9efd308e
DV		 615 p->port_protocol_migration_sm_state =
616 PORT_PROTOCOL_MIGRATION_SM_CHECKING_RSTP_EXEC;
311fb15b 617 } else if (p->send_rstp && p->rcvd_stp) {
9efd308e
DV		 618 p->port_protocol_migration_sm_state =
619 PORT_PROTOCOL_MIGRATION_SM_SELECTING_STP_EXEC;
620 }
621 break;
622 default:
623 OVS_NOT_REACHED();
73c7216a 624 /* fall through */
9efd308e
DV		 625 }
626 if (old_state != p->port_protocol_migration_sm_state) {
627 r->changes = true;
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);
631 }
632
633 return 0;
634}
635
636/* [17.25 - Bridge Detection state machine] */
637static int
638bridge_detection_sm(struct rstp_port *p)
f025bcb7 639 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 640{
641 enum bridge_detection_state_machine old_state;
642 struct rstp *r;
643
644 old_state = p->bridge_detection_sm_state;
645 r = p->rstp;
646
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;
653 }
654 break;
655 case BRIDGE_DETECTION_SM_EDGE_EXEC:
656 p->oper_edge = true;
657 p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_EDGE;
73c7216a 658 /* fall through */
9efd308e
DV		 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;
662 }
663 break;
664 case BRIDGE_DETECTION_SM_NOT_EDGE_EXEC:
665 p->oper_edge = false;
666 p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_NOT_EDGE;
73c7216a 667 /* fall through */
9efd308e 668 case BRIDGE_DETECTION_SM_NOT_EDGE:
311fb15b
JR		 669 if ((!p->port_enabled && p->admin_edge)
670 || ((p->edge_delay_while == 0) && p->auto_edge && p->send_rstp
671 && p->proposing)) {
9efd308e
DV		 672 p->bridge_detection_sm_state = BRIDGE_DETECTION_SM_EDGE_EXEC;
673 }
674 break;
675 default:
676 OVS_NOT_REACHED();
73c7216a 677 /* fall through */
9efd308e
DV		 678 }
679 if (old_state != p->bridge_detection_sm_state) {
680 r->changes = true;
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);
683 }
684 return 0;
685}
686
687/* [17.26 - Port Transmit state machine] */
688static void
689rstp_send_bpdu(struct rstp_port *p, const void *bpdu, size_t bpdu_size)
f025bcb7 690 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 691{
692 struct eth_header *eth;
693 struct llc_header *llc;
cf62fa4c 694 struct dp_packet *pkt;
9efd308e
DV		 695
696 /* Skeleton. */
cf62fa4c
PS		 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);
82eb5b0a 700 dp_packet_reset_offsets(pkt);
cf62fa4c 701 dp_packet_set_l3(pkt, dp_packet_put(pkt, bpdu, bpdu_size));
9efd308e
DV		 702
703 /* 802.2 header. */
74ff3298 704 eth->eth_dst = eth_addr_stp;
9efd308e 705 /* p->rstp->send_bpdu() must fill in source address. */
cf62fa4c 706 eth->eth_type = htons(dp_packet_size(pkt) - ETH_HEADER_LEN);
9efd308e
DV		 707
708 /* LLC header. */
709 llc->llc_dsap = STP_LLC_DSAP;
710 llc->llc_ssap = STP_LLC_SSAP;
711 llc->llc_cntl = STP_LLC_CNTL;
6b90bc57 712 p->rstp->send_bpdu(pkt, p->aux, p->rstp->aux);
9efd308e
DV		 713}
714
715static void
716record_agreement(struct rstp_port *p)
f025bcb7 717 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 718{
719 struct rstp *r;
720
721 r = p->rstp;
722 if (r->rstp_version && p->oper_point_to_point_mac &&
311fb15b 723 ((p->received_bpdu_buffer.flags & BPDU_FLAG_AGREEMENT))) {
9efd308e
DV		 724 p->agreed = true;
725 p->proposing = false;
726 } else {
727 p->agreed = false;
728 }
729}
730
731static void
732set_tc_flags(struct rstp_port *p)
f025bcb7 733 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 734{
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
737 * RST BPDU.
738 */
739 if (p->received_bpdu_buffer.bpdu_type == CONFIGURATION_BPDU ||
311fb15b 740 p->received_bpdu_buffer.bpdu_type == RAPID_SPANNING_TREE_BPDU) {
9efd308e
DV		 741 if ((p->received_bpdu_buffer.flags & BPDU_FLAG_TOPCHANGE) != 0) {
742 p->rcvd_tc = true;
743 }
744 if ((p->received_bpdu_buffer.flags & BPDU_FLAG_TOPCHANGEACK) != 0) {
745 p->rcvd_tc_ack = true;
746 }
747 }
748 /* Sets rcvd_tcn true if the BPDU is a TCN BPDU. */
311fb15b
JR		 749 if (p->received_bpdu_buffer.bpdu_type
750 == TOPOLOGY_CHANGE_NOTIFICATION_BPDU) {
9efd308e
DV		 751 p->rcvd_tcn = true;
752 }
753}
754
755static void
756record_dispute(struct rstp_port *p)
f025bcb7 757 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 758{
759 if ((p->received_bpdu_buffer.flags & BPDU_FLAG_LEARNING) != 0) {
b5ba2490
JR		 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. */
763 p->disputed = true;
764 p->agreed = false;
9efd308e
DV		 765 }
766}
767
768static void
769record_proposal(struct rstp_port *p)
f025bcb7 770 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 771{
772 enum port_flag role =
773 ((p->received_bpdu_buffer.flags) & ROLE_FLAG_MASK) >> ROLE_FLAG_SHIFT;
311fb15b
JR		 774
775 if ((role == PORT_DES)
776 && ((p->received_bpdu_buffer.flags & BPDU_FLAG_PROPOSAL) != 0)) {
9efd308e
DV		 777 p->proposed = true;
778 }
779}
780
781static void
782record_priority(struct rstp_port *p)
f025bcb7 783 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 784{
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;
790}
791
792static void
793record_times(struct rstp_port *p)
f025bcb7 794 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 795{
796 p->port_times = p->msg_times;
797 if (p->msg_times.hello_time == 0) {
798 p->port_times.hello_time = 1;
799 }
800}
801
802static void
803updt_rcvd_info_while(struct rstp_port *p)
f025bcb7 804 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 805{
806 /* [17.21.23]
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.
810 */
811 if (p->port_times.message_age < p->port_times.max_age) {
812 p->rcvd_info_while = p->port_times.hello_time * 3;
311fb15b 813 } else {
9efd308e 814 p->rcvd_info_while = 0;
311fb15b 815 }
9efd308e
DV		 816}
817
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.
821 */
822static ovs_be16
823time_encode(uint8_t value)
824{
825 return htons(value * 256);
826}
827
828static uint8_t
829time_decode(ovs_be16 encoded)
830{
831 return ntohs(encoded) / 256;
832}
833
834/* [17.21.19] */
835static void
836tx_config(struct rstp_port *p)
f025bcb7 837 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 838{
839 struct rstp_bpdu bpdu;
840
36549a91 841 memset(&bpdu, 0, sizeof bpdu);
9efd308e
DV		 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);
855 bpdu.flags = 0;
856 if (p->tc_while != 0) {
857 bpdu.flags |= BPDU_FLAG_TOPCHANGE;
858 }
859 if (p->tc_ack != 0) {
860 bpdu.flags |= BPDU_FLAG_TOPCHANGEACK;
861 }
862 rstp_send_bpdu(p, &bpdu, sizeof(struct rstp_bpdu));
863}
864
865/* [17.21.20] */
866static void
867tx_rstp(struct rstp_port *p)
f025bcb7 868 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 869{
870 struct rstp_bpdu bpdu;
871
36549a91 872 memset(&bpdu, 0, sizeof bpdu);
9efd308e
DV		 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);
886 bpdu.flags = 0;
311fb15b 887
9efd308e
DV		 888 switch (p->role) {
889 case ROLE_ROOT:
890 bpdu.flags = PORT_ROOT << ROLE_FLAG_SHIFT;
891 break;
892 case ROLE_DESIGNATED:
893 bpdu.flags = PORT_DES << ROLE_FLAG_SHIFT;
894 break;
895 case ROLE_ALTERNATE:
896 case ROLE_BACKUP:
897 bpdu.flags = PORT_ALT_BACK << ROLE_FLAG_SHIFT;
898 break;
899 case ROLE_DISABLED:
4b30ba05 900 /* Should not happen! */
9efd308e 901 VLOG_ERR("%s transmitting bpdu in disabled role on port "
4b30ba05 902 RSTP_PORT_ID_FMT, p->rstp->name, p->port_id);
9efd308e
DV		 903 break;
904 }
905 if (p->agree) {
906 bpdu.flags |= BPDU_FLAG_AGREEMENT;
907 }
908 if (p->proposing) {
909 bpdu.flags |= BPDU_FLAG_PROPOSAL;
910 }
911 if (p->tc_while != 0) {
912 bpdu.flags |= BPDU_FLAG_TOPCHANGE;
913 }
914 if (p->learning) {
915 bpdu.flags |= BPDU_FLAG_LEARNING;
916 }
917 if (p->forwarding) {
918 bpdu.flags |= BPDU_FLAG_FORWARDING;
919 }
920 bpdu.version1_length = 0;
921 rstp_send_bpdu(p, &bpdu, sizeof(struct rstp_bpdu));
922}
923
924/* [17.21.21] */
925static void
926tx_tcn(struct rstp_port *p)
f025bcb7 927 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 928{
929 struct rstp_bpdu bpdu;
930
931 memset(&bpdu, 0, sizeof(struct rstp_bpdu));
932
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));
937}
938
939static int
940port_transmit_sm(struct rstp_port *p)
f025bcb7 941 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 942{
943 enum port_transmit_state_machine old_state;
944 struct rstp *r;
945
946 old_state = p->port_transmit_sm_state;
947 r = p->rstp;
948
949 switch (p->port_transmit_sm_state) {
950 case PORT_TRANSMIT_SM_INIT:
951 if (r->begin) {
952 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_INIT_EXEC;
953 }
954 break;
955 case PORT_TRANSMIT_SM_TRANSMIT_INIT_EXEC:
956 p->new_info = true;
957 p->tx_count = 0;
958 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_INIT;
73c7216a 959 /* fall through */
9efd308e
DV		 960 case PORT_TRANSMIT_SM_TRANSMIT_INIT:
961 p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
962 break;
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;
73c7216a 967 /* fall through */
9efd308e
DV		 968 case PORT_TRANSMIT_SM_TRANSMIT_PERIODIC:
969 p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
970 break;
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;
73c7216a 974 /* fall through */
9efd308e
DV		 975 case PORT_TRANSMIT_SM_IDLE:
976 if (p->role == ROLE_DISABLED) {
4b30ba05
JR		 977 VLOG_DBG("%s, port %u: port_transmit_sm ROLE == DISABLED.",
978 p->rstp->name, p->port_number);
9efd308e 979 break;
311fb15b
JR		 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) {
9efd308e 983 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_RSTP_EXEC;
311fb15b 984 } else if (p->hello_when == 0 && p->selected && !p->updt_info) {
9efd308e
DV		 985 p->port_transmit_sm_state =
986 PORT_TRANSMIT_SM_TRANSMIT_PERIODIC_EXEC;
311fb15b
JR		 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) {
9efd308e 990 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_TCN_EXEC;
311fb15b
JR		 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) {
9efd308e
DV		 994 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_CONFIG_EXEC;
995 }
996 break;
997 case PORT_TRANSMIT_SM_TRANSMIT_CONFIG_EXEC:
998 p->new_info = false;
999 tx_config(p);
1000 p->tx_count += 1;
1001 p->tc_ack = false;
1002 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_CONFIG;
73c7216a 1003 /* fall through */
9efd308e
DV		 1004 case PORT_TRANSMIT_SM_TRANSMIT_CONFIG:
1005 p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
1006 break;
1007 case PORT_TRANSMIT_SM_TRANSMIT_TCN_EXEC:
1008 p->new_info = false;
1009 tx_tcn(p);
1010 p->tx_count += 1;
1011 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_TCN;
73c7216a 1012 /* fall through */
9efd308e
DV		 1013 case PORT_TRANSMIT_SM_TRANSMIT_TCN:
1014 p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
1015 break;
1016 case PORT_TRANSMIT_SM_TRANSMIT_RSTP_EXEC:
1017 p->new_info = false;
1018 tx_rstp(p);
1019 p->tx_count += 1;
1020 p->tc_ack = false;
1021 p->port_transmit_sm_state = PORT_TRANSMIT_SM_TRANSMIT_RSTP;
73c7216a 1022 /* fall through */
9efd308e
DV		 1023 case PORT_TRANSMIT_SM_TRANSMIT_RSTP:
1024 p->port_transmit_sm_state = PORT_TRANSMIT_SM_IDLE_EXEC;
1025 break;
1026 default:
1027 OVS_NOT_REACHED();
73c7216a 1028 /* fall through */
9efd308e
DV		 1029 }
1030 if (old_state != p->port_transmit_sm_state) {
1031 r->changes = true;
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);
1034 }
1035 return 0;
1036}
1037
1038/* [17.27 Port Information state machine] */
1039#define RECEIVED 0
1040#define MINE 1
1041
1042static int
1043rcv_info(struct rstp_port *p)
f025bcb7 1044 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1045{
1046 enum vector_comparison cp;
1047 bool ct;
1048 enum port_flag role;
1049
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);
1058
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);
1065
a0478216 1066 cp = compare_rstp_priority_vectors(&p->msg_priority, &p->port_priority);
9efd308e 1067 ct = rstp_times_equal(&p->port_times, &p->msg_times);
12c14838
DV		 1068 /* Configuration BPDU conveys a Designated Port Role. */
1069 if (p->received_bpdu_buffer.bpdu_type == CONFIGURATION_BPDU) {
1070 role = PORT_DES;
1071 } else {
1072 role =
1073 (p->received_bpdu_buffer.flags & ROLE_FLAG_MASK) >> ROLE_FLAG_SHIFT;
1074 }
9efd308e 1075
11d4d408
DV		 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) {
1080 p->rcvd_tcn = true;
1081 return OTHER_INFO;
1082 }
1083
9efd308e
DV		 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
1087 * vector, or
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
1091 * 17.19.22).
1092 * NOTE: Configuration BPDU explicitly conveys a Designated Port Role.
1093 */
12c14838 1094 if (role == PORT_DES && (cp == SUPERIOR || (cp == SAME && ct == false))) {
9efd308e 1095 return SUPERIOR_DESIGNATED_INFO;
9efd308e 1096
311fb15b
JR		 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) {
9efd308e 1102 return REPEATED_DESIGNATED_INFO;
9efd308e 1103
311fb15b
JR		 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) {
9efd308e 1109 return INFERIOR_DESIGNATED_INFO;
9efd308e 1110
311fb15b
JR		 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)) {
9efd308e 1117 return INFERIOR_ROOT_ALTERNATE_INFO;
9efd308e 1118
311fb15b
JR		 1119 /* Otherwise, returns OtherInfo. */
1120 } else {
9efd308e
DV		 1121 return OTHER_INFO;
1122 }
1123}
1124
1125static int
1126better_or_same_info(struct rstp_port *p, int new_info_is)
f025bcb7 1127 OVS_REQUIRES(rstp_mutex)
9efd308e 1128{
311fb15b
JR		 1129 return
1130 (new_info_is == RECEIVED && p->info_is == INFO_IS_RECEIVED
a0478216
JR		 1131 && compare_rstp_priority_vectors(&p->msg_priority,
1132 &p->port_priority))
311fb15b 1133 || (new_info_is == MINE && p->info_is == INFO_IS_MINE
a0478216
JR		 1134 && compare_rstp_priority_vectors(&p->designated_priority_vector,
1135 &p->port_priority));
9efd308e
DV		 1136}
1137
1138static int
1139port_information_sm(struct rstp_port *p)
f025bcb7 1140 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1141{
1142 enum port_information_state_machine old_state;
1143 struct rstp *r;
b5ba2490 1144 struct rstp_port *p1;
9efd308e
DV		 1145
1146 old_state = p->port_information_sm_state;
1147 r = p->rstp;
1148
9efd308e
DV		 1149 switch (p->port_information_sm_state) {
1150 case PORT_INFORMATION_SM_INIT:
6448df94
JR		 1151 if (r->begin
1152 || (!p->port_enabled && p->info_is != INFO_IS_DISABLED)) {
9efd308e
DV		 1153 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
1154 }
1155 break;
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;
1161 p->reselect = true;
1162 p->selected = false;
1163 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED;
73c7216a 1164 /* fall through */
9efd308e 1165 case PORT_INFORMATION_SM_DISABLED:
6448df94
JR		 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) {
9efd308e 1170 p->port_information_sm_state = PORT_INFORMATION_SM_AGED_EXEC;
4b30ba05
JR		 1171 } else if (p->rcvd_msg) {
1172 p->port_information_sm_state = PORT_INFORMATION_SM_DISABLED_EXEC;
9efd308e
DV		 1173 }
1174 break;
1175 case PORT_INFORMATION_SM_AGED_EXEC:
1176 p->info_is = INFO_IS_AGED;
1177 p->reselect = true;
1178 p->selected = false;
1179 p->port_information_sm_state = PORT_INFORMATION_SM_AGED;
73c7216a 1180 /* fall through */
9efd308e 1181 case PORT_INFORMATION_SM_AGED:
6448df94
JR		 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) {
9efd308e
DV		 1186 p->port_information_sm_state = PORT_INFORMATION_SM_UPDATE_EXEC;
1187 }
1188 break;
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;
1205 p->new_info = true;
1206 p->port_information_sm_state = PORT_INFORMATION_SM_UPDATE;
73c7216a 1207 /* fall through */
9efd308e 1208 case PORT_INFORMATION_SM_UPDATE:
6448df94
JR		 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;
1212 } else {
1213 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1214 }
9efd308e
DV		 1215 break;
1216 case PORT_INFORMATION_SM_CURRENT_EXEC:
1217 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT;
73c7216a 1218 /* fall through */
9efd308e 1219 case PORT_INFORMATION_SM_CURRENT:
6448df94
JR		 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) {
9efd308e
DV		 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 &&
1229 !p->rcvd_msg) {
1230 p->port_information_sm_state = PORT_INFORMATION_SM_AGED_EXEC;
1231 }
1232 break;
1233 case PORT_INFORMATION_SM_RECEIVE_EXEC:
1234 p->rcvd_info = rcv_info(p);
1235 p->port_information_sm_state = PORT_INFORMATION_SM_RECEIVE;
73c7216a 1236 /* fall through */
9efd308e 1237 case PORT_INFORMATION_SM_RECEIVE:
6448df94
JR		 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;
1241 } else {
1242 switch (p->rcvd_info) {
1243 case SUPERIOR_DESIGNATED_INFO:
b5ba2490
JR		 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
1249 * is set. */
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) {
1253 p1->agreed = false;
1254 }
1255 }
1256 }
6448df94
JR		 1257 p->port_information_sm_state =
1258 PORT_INFORMATION_SM_SUPERIOR_DESIGNATED_EXEC;
1259 break;
1260 case REPEATED_DESIGNATED_INFO:
1261 p->port_information_sm_state =
1262 PORT_INFORMATION_SM_REPEATED_DESIGNATED_EXEC;
1263 break;
1264 case INFERIOR_DESIGNATED_INFO:
1265 p->port_information_sm_state =
1266 PORT_INFORMATION_SM_INFERIOR_DESIGNATED_EXEC;
1267 break;
1268 case INFERIOR_ROOT_ALTERNATE_INFO:
1269 p->port_information_sm_state =
1270 PORT_INFORMATION_SM_NOT_DESIGNATED_EXEC;
1271 break;
1272 case OTHER_INFO:
1273 p->port_information_sm_state = PORT_INFORMATION_SM_OTHER_EXEC;
1274 break;
1275 default:
1276 OVS_NOT_REACHED();
73c7216a 1277 /* fall through */
6448df94 1278 }
9efd308e
DV		 1279 }
1280 break;
1281 case PORT_INFORMATION_SM_OTHER_EXEC:
1282 p->rcvd_msg = false;
1283 p->port_information_sm_state = PORT_INFORMATION_SM_OTHER;
73c7216a 1284 /* fall through */
9efd308e 1285 case PORT_INFORMATION_SM_OTHER:
6448df94
JR		 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;
1289 } else {
1290 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1291 }
9efd308e
DV		 1292 break;
1293 case PORT_INFORMATION_SM_NOT_DESIGNATED_EXEC:
1294 record_agreement(p);
1295 set_tc_flags(p);
1296 p->rcvd_msg = false;
1297 p->port_information_sm_state = PORT_INFORMATION_SM_NOT_DESIGNATED;
73c7216a 1298 /* fall through */
9efd308e 1299 case PORT_INFORMATION_SM_NOT_DESIGNATED:
6448df94
JR		 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;
1303 } else {
1304 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1305 }
9efd308e
DV		 1306 break;
1307 case PORT_INFORMATION_SM_INFERIOR_DESIGNATED_EXEC:
1308 record_dispute(p);
1309 p->rcvd_msg = false;
1310 p->port_information_sm_state = PORT_INFORMATION_SM_INFERIOR_DESIGNATED;
73c7216a 1311 /* fall through */
9efd308e 1312 case PORT_INFORMATION_SM_INFERIOR_DESIGNATED:
6448df94
JR		 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;
1316 } else {
1317 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1318 }
9efd308e
DV		 1319 break;
1320 case PORT_INFORMATION_SM_REPEATED_DESIGNATED_EXEC:
1321 record_proposal(p);
1322 set_tc_flags(p);
b5ba2490
JR		 1323 /* This record_agreement() is missing in 802.1D-2004, but it's present
1324 * in 802.1q-2008. */
1325 record_agreement(p);
9efd308e
DV		 1326 updt_rcvd_info_while(p);
1327 p->rcvd_msg = false;
1328 p->port_information_sm_state = PORT_INFORMATION_SM_REPEATED_DESIGNATED;
73c7216a 1329 /* fall through */
9efd308e 1330 case PORT_INFORMATION_SM_REPEATED_DESIGNATED:
6448df94
JR		 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;
1334 } else {
1335 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1336 }
9efd308e
DV		 1337 break;
1338 case PORT_INFORMATION_SM_SUPERIOR_DESIGNATED_EXEC:
1339 p->agreed = p->proposing = false;
1340 record_proposal(p);
1341 set_tc_flags(p);
1342 /* RECEIVED is not specified in Standard 802.1D-2004. */
1343 p->agree = p->agree && better_or_same_info(p, RECEIVED);
b5ba2490
JR		 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;
9efd308e
DV		 1348 record_priority(p);
1349 record_times(p);
1350 updt_rcvd_info_while(p);
1351 p->info_is = INFO_IS_RECEIVED;
1352 p->reselect = true;
1353 p->selected = false;
1354 p->rcvd_msg = false;
1355 p->port_information_sm_state = PORT_INFORMATION_SM_SUPERIOR_DESIGNATED;
73c7216a 1356 /* fall through */
9efd308e 1357 case PORT_INFORMATION_SM_SUPERIOR_DESIGNATED:
6448df94
JR		 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;
1361 } else {
1362 p->port_information_sm_state = PORT_INFORMATION_SM_CURRENT_EXEC;
1363 }
9efd308e
DV		 1364 break;
1365 default:
1366 OVS_NOT_REACHED();
73c7216a 1367 /* fall through */
9efd308e
DV		 1368 }
1369 if (old_state != p->port_information_sm_state) {
1370 r->changes = true;
4b30ba05
JR		 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);
9efd308e
DV		 1373 }
1374 return 0;
1375}
1376
1377/* [17.29 Port Role Transitions state machine] */
1378
1379static void
1380set_re_root_tree(struct rstp_port *p)
f025bcb7 1381 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1382{
1383 struct rstp *r;
1384 struct rstp_port *p1;
1385
1386 r = p->rstp;
d5f31dc8 1387 HMAP_FOR_EACH (p1, node, &r->ports) {
37db915e 1388 p1->re_root = true;
9efd308e
DV		 1389 }
1390}
1391
1392static void
1393set_sync_tree(struct rstp_port *p)
f025bcb7 1394 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1395{
1396 struct rstp *r;
1397 struct rstp_port *p1;
1398
1399 r = p->rstp;
d5f31dc8 1400 HMAP_FOR_EACH (p1, node, &r->ports) {
37db915e 1401 p1->sync = true;
9efd308e
DV		 1402 }
1403}
1404
1405static int
1406hello_time(struct rstp_port *p)
f025bcb7 1407 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1408{
1409 return p->designated_times.hello_time;
1410}
1411
1412static int
1413fwd_delay(struct rstp_port *p)
f025bcb7 1414 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1415{
1416 return p->designated_times.forward_delay;
1417}
1418
1419static int
1420forward_delay(struct rstp_port *p)
f025bcb7 1421 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1422{
1423 if (p->send_rstp) {
1424 return hello_time(p);
1425 } else {
1426 return fwd_delay(p);
1427 }
1428}
1429
1430static int
1431edge_delay(struct rstp_port *p)
f025bcb7 1432 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1433{
1434 struct rstp *r;
1435
1436 r = p->rstp;
1437 if (p->oper_point_to_point_mac == 1) {
1438 return r->migrate_time;
1439 } else {
1440 return p->designated_times.max_age;
1441 }
1442}
1443
1444static int
1445check_selected_role_change(struct rstp_port *p, int current_role_state)
f025bcb7 1446 OVS_REQUIRES(rstp_mutex)
9efd308e 1447{
311fb15b
JR		 1448 if (p->selected && !p->updt_info && p->role != p->selected_role
1449 && p->selected_role != current_role_state) {
9efd308e
DV		 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) {
1455 case ROLE_ROOT:
1456 p->port_role_transition_sm_state =
1457 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1458 return true;
1459 case ROLE_DESIGNATED:
1460 p->port_role_transition_sm_state =
1461 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1462 return true;
1463 case ROLE_ALTERNATE:
1464 p->port_role_transition_sm_state =
1465 PORT_ROLE_TRANSITION_SM_BLOCK_PORT_EXEC;
1466 return true;
1467 case ROLE_BACKUP:
1468 p->port_role_transition_sm_state =
1469 PORT_ROLE_TRANSITION_SM_BLOCK_PORT_EXEC;
1470 return true;
1471 case ROLE_DISABLED:
1472 p->port_role_transition_sm_state =
1473 PORT_ROLE_TRANSITION_SM_DISABLE_PORT_EXEC;
1474 return true;
1475 }
1476 }
1477 return false;
1478}
1479
1480static int
1481re_rooted(struct rstp_port *p)
f025bcb7 1482 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1483{
1484 struct rstp *r;
1485 struct rstp_port *p1;
1486
1487 r = p->rstp;
d5f31dc8 1488 HMAP_FOR_EACH (p1, node, &r->ports) {
37db915e
JR		 1489 if ((p1 != p) && (p1->rr_while != 0)) {
1490 return false;
9efd308e
DV		 1491 }
1492 }
1493 return true;
1494}
1495
1496static int
1497all_synced(struct rstp *r)
f025bcb7 1498 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1499{
1500 struct rstp_port *p;
1501
d5f31dc8 1502 HMAP_FOR_EACH (p, node, &r->ports) {
37db915e
JR		 1503 if (!(p->selected && p->role == p->selected_role &&
1504 (p->role == ROLE_ROOT || p->synced == true))) {
1505 return false;
9efd308e
DV		 1506 }
1507 }
1508 return true;
1509}
1510
1511static int
1512port_role_transition_sm(struct rstp_port *p)
f025bcb7 1513 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1514{
1515 enum port_role_transition_state_machine old_state;
1516 struct rstp *r;
1517 enum rstp_port_role last_role;
1518
1519 old_state = p->port_role_transition_sm_state;
1520 r = p->rstp;
1521 last_role = p->role;
1522
1523 switch (p->port_role_transition_sm_state) {
1524 case PORT_ROLE_TRANSITION_SM_INIT:
1525 if (r->begin) {
1526 p->port_role_transition_sm_state =
1527 PORT_ROLE_TRANSITION_SM_INIT_PORT_EXEC;
1528 }
1529 break;
1530 case PORT_ROLE_TRANSITION_SM_INIT_PORT_EXEC:
1531 p->role = ROLE_DISABLED;
1532 p->learn = p->forward = false;
1533 p->synced = 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;
1537 p->rb_while = 0;
1538 p->port_role_transition_sm_state =
1539 PORT_ROLE_TRANSITION_SM_DISABLE_PORT_EXEC;
1540 break;
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;
73c7216a 1546 /* fall through */
9efd308e
DV		 1547 case PORT_ROLE_TRANSITION_SM_DISABLE_PORT:
1548 if (check_selected_role_change(p, ROLE_DISABLED)) {
6448df94 1549 /* Global transition. */
311fb15b
JR		 1550 } else if (p->selected && !p->updt_info && !p->learning
1551 && !p->forwarding) {
9efd308e
DV		 1552 p->port_role_transition_sm_state =
1553 PORT_ROLE_TRANSITION_SM_DISABLED_PORT_EXEC;
1554 }
1555 break;
1556 case PORT_ROLE_TRANSITION_SM_DISABLED_PORT_EXEC:
1557 p->fd_while = p->designated_times.max_age;
1558 p->synced = true;
1559 p->rr_while = 0;
1560 p->sync = p->re_root = false;
1561 p->port_role_transition_sm_state =
1562 PORT_ROLE_TRANSITION_SM_DISABLED_PORT;
73c7216a 1563 /* fall through */
9efd308e
DV		 1564 case PORT_ROLE_TRANSITION_SM_DISABLED_PORT:
1565 if (check_selected_role_change(p, ROLE_DISABLED)) {
6448df94 1566 /* Global transition. */
311fb15b
JR		 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)) {
9efd308e
DV		 1570 p->port_role_transition_sm_state =
1571 PORT_ROLE_TRANSITION_SM_DISABLED_PORT_EXEC;
1572 }
1573 break;
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;
73c7216a 1578 /* fall through */
9efd308e
DV		 1579 case PORT_ROLE_TRANSITION_SM_ROOT_PORT:
1580 if (check_selected_role_change(p, ROLE_ROOT)) {
6448df94 1581 /* Global transition. */
311fb15b 1582 } else if (p->selected && !p->updt_info) {
9efd308e
DV		 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;
1586 break;
311fb15b 1587 } else if (p->re_root && p->forward) {
9efd308e
DV		 1588 p->port_role_transition_sm_state =
1589 PORT_ROLE_TRANSITION_SM_REROOTED_EXEC;
1590 break;
311fb15b
JR		 1591 } else if ((p->fd_while == 0
1592 || ((re_rooted(p) && p->rb_while == 0)
1593 && r->rstp_version)) && !p->learn) {
9efd308e
DV		 1594 p->port_role_transition_sm_state =
1595 PORT_ROLE_TRANSITION_SM_ROOT_LEARN_EXEC;
1596 break;
311fb15b
JR		 1597 } else if ((p->fd_while == 0
1598 || ((re_rooted(p) && p->rb_while == 0)
1599 && r->rstp_version)) && p->learn && !p->forward) {
9efd308e
DV		 1600 p->port_role_transition_sm_state =
1601 PORT_ROLE_TRANSITION_SM_ROOT_FORWARD_EXEC;
1602 break;
311fb15b 1603 } else if (p->proposed && !p->agree) {
9efd308e
DV		 1604 p->port_role_transition_sm_state =
1605 PORT_ROLE_TRANSITION_SM_ROOT_PROPOSED_EXEC;
1606 break;
311fb15b
JR		 1607 } else if ((all_synced(r) && !p->agree) ||
1608 (p->proposed && p->agree)) {
9efd308e
DV		 1609 p->port_role_transition_sm_state =
1610 PORT_ROLE_TRANSITION_SM_ROOT_AGREED_EXEC;
1611 break;
311fb15b 1612 } else if (!p->forward && !p->re_root) {
9efd308e
DV		 1613 p->port_role_transition_sm_state =
1614 PORT_ROLE_TRANSITION_SM_REROOT_EXEC;
1615 break;
1616 }
1617 }
6448df94 1618 break;
9efd308e 1619 case PORT_ROLE_TRANSITION_SM_REROOT_EXEC:
6448df94
JR		 1620 if (check_selected_role_change(p, ROLE_ROOT)) {
1621 /* Global transition. */
1622 } else {
1623 set_re_root_tree(p);
1624 p->port_role_transition_sm_state =
1625 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1626 }
9efd308e
DV		 1627 break;
1628 case PORT_ROLE_TRANSITION_SM_ROOT_AGREED_EXEC:
6448df94
JR		 1629 if (check_selected_role_change(p, ROLE_ROOT)) {
1630 /* Global transition. */
1631 } else {
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;
1636 }
9efd308e
DV		 1637 break;
1638 case PORT_ROLE_TRANSITION_SM_ROOT_PROPOSED_EXEC:
1639 set_sync_tree(p);
1640 p->proposed = false;
6448df94
JR		 1641 if (check_selected_role_change(p, ROLE_ROOT)) {
1642 /* Global transition. */
1643 } else {
1644 p->port_role_transition_sm_state =
1645 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1646 }
9efd308e
DV		 1647 break;
1648 case PORT_ROLE_TRANSITION_SM_ROOT_FORWARD_EXEC:
1649 p->fd_while = 0;
1650 p->forward = true;
6448df94
JR		 1651 if (check_selected_role_change(p, ROLE_ROOT)) {
1652 /* Global transition. */
1653 } else {
1654 p->port_role_transition_sm_state =
1655 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1656 }
9efd308e
DV		 1657 break;
1658 case PORT_ROLE_TRANSITION_SM_ROOT_LEARN_EXEC:
1659 p->fd_while = forward_delay(p);
1660 p->learn = true;
6448df94
JR		 1661 if (check_selected_role_change(p, ROLE_ROOT)) {
1662 /* Global transition. */
1663 } else {
1664 p->port_role_transition_sm_state =
1665 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1666 }
9efd308e
DV		 1667 break;
1668 case PORT_ROLE_TRANSITION_SM_REROOTED_EXEC:
1669 p->re_root = false;
6448df94
JR		 1670 if (check_selected_role_change(p, ROLE_ROOT)) {
1671 /* Global transition. */
1672 } else {
1673 p->port_role_transition_sm_state =
1674 PORT_ROLE_TRANSITION_SM_ROOT_PORT_EXEC;
1675 }
9efd308e
DV		 1676 break;
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;
73c7216a 1681 /* fall through */
9efd308e
DV		 1682 case PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT:
1683 if (check_selected_role_change(p, ROLE_DESIGNATED)) {
6448df94 1684 /* Global transition. */
311fb15b
JR		 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) {
9efd308e
DV		 1694 p->port_role_transition_sm_state =
1695 PORT_ROLE_TRANSITION_SM_DESIGNATED_LEARN_EXEC;
311fb15b
JR		 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)) {
9efd308e
DV		 1699 p->port_role_transition_sm_state =
1700 PORT_ROLE_TRANSITION_SM_DESIGNATED_FORWARD_EXEC;
311fb15b
JR		 1701 } else if (!p->forward && !p->agreed && !p->proposing &&
1702 !p->oper_edge) {
9efd308e
DV		 1703 p->port_role_transition_sm_state =
1704 PORT_ROLE_TRANSITION_SM_DESIGNATED_PROPOSE_EXEC;
311fb15b
JR		 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)) {
9efd308e
DV		 1709 p->port_role_transition_sm_state =
1710 PORT_ROLE_TRANSITION_SM_DESIGNATED_SYNCED_EXEC;
311fb15b 1711 } else if (p->rr_while == 0 && p->re_root) {
9efd308e
DV		 1712 p->port_role_transition_sm_state =
1713 PORT_ROLE_TRANSITION_SM_DESIGNATED_RETIRED_EXEC;
1714 }
1715 }
1716 break;
1717 case PORT_ROLE_TRANSITION_SM_DESIGNATED_RETIRED_EXEC:
1718 p->re_root = false;
6448df94
JR		 1719 if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1720 /* Global transition. */
1721 } else {
1722 p->port_role_transition_sm_state =
1723 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1724 }
9efd308e
DV		 1725 break;
1726 case PORT_ROLE_TRANSITION_SM_DESIGNATED_SYNCED_EXEC:
1727 p->rr_while = 0;
1728 p->synced = true;
1729 p->sync = false;
6448df94
JR		 1730 if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1731 /* Global transition. */
1732 } else {
1733 p->port_role_transition_sm_state =
1734 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1735 }
9efd308e
DV		 1736 break;
1737 case PORT_ROLE_TRANSITION_SM_DESIGNATED_PROPOSE_EXEC:
1738 p->proposing = true;
1739 p->edge_delay_while = edge_delay(p);
1740 p->new_info = true;
6448df94
JR		 1741 if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1742 /* Global transition. */
1743 } else {
1744 p->port_role_transition_sm_state =
1745 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1746 }
9efd308e
DV		 1747 break;
1748 case PORT_ROLE_TRANSITION_SM_DESIGNATED_FORWARD_EXEC:
1749 p->forward = true;
1750 p->fd_while = 0;
1751 p->agreed = p->send_rstp;
6448df94
JR		 1752 if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1753 /* Global transition. */
1754 } else {
1755 p->port_role_transition_sm_state =
1756 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1757 }
9efd308e
DV		 1758 break;
1759 case PORT_ROLE_TRANSITION_SM_DESIGNATED_LEARN_EXEC:
1760 p->learn = true;
1761 p->fd_while = forward_delay(p);
6448df94
JR		 1762 if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1763 /* Global transition. */
1764 } else {
1765 p->port_role_transition_sm_state =
1766 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1767 }
9efd308e
DV		 1768 break;
1769 case PORT_ROLE_TRANSITION_SM_DESIGNATED_DISCARD_EXEC:
1770 p->learn = p->forward = p->disputed = false;
1771 p->fd_while = forward_delay(p);
6448df94
JR		 1772 if (check_selected_role_change(p, ROLE_DESIGNATED)) {
1773 /* Global transition. */
1774 } else {
1775 p->port_role_transition_sm_state =
1776 PORT_ROLE_TRANSITION_SM_DESIGNATED_PORT_EXEC;
1777 }
9efd308e
DV		 1778 break;
1779 case PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC:
1780 p->fd_while = p->designated_times.forward_delay;
1781 p->synced = true;
1782 p->rr_while = 0;
1783 p->sync = p->re_root = false;
1784 p->port_role_transition_sm_state =
1785 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT;
73c7216a 1786 /* fall through */
9efd308e
DV		 1787 case PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT:
1788 if (check_selected_role_change(p, ROLE_ALTERNATE)) {
6448df94 1789 /* Global transition. */
311fb15b
JR		 1790 } else if (p->selected && !p->updt_info) {
1791 if (p->rb_while != 2 * p->designated_times.hello_time
1792 && p->role == ROLE_BACKUP) {
9efd308e
DV		 1793 p->port_role_transition_sm_state =
1794 PORT_ROLE_TRANSITION_SM_BACKUP_PORT_EXEC;
311fb15b
JR		 1795 } else if ((p->fd_while != forward_delay(p)) || p->sync
1796 || p->re_root || !p->synced) {
9efd308e
DV		 1797 p->port_role_transition_sm_state =
1798 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
311fb15b 1799 } else if (p->proposed && !p->agree) {
9efd308e
DV		 1800 p->port_role_transition_sm_state =
1801 PORT_ROLE_TRANSITION_SM_ALTERNATE_PROPOSED_EXEC;
311fb15b
JR		 1802 } else if ((all_synced(r) && !p->agree)
1803 || (p->proposed && p->agree)) {
9efd308e 1804 p->port_role_transition_sm_state =
7ccf8d38 1805 PORT_ROLE_TRANSITION_SM_ALTERNATE_AGREED_EXEC;
9efd308e
DV		 1806 }
1807 }
1808 break;
7ccf8d38 1809 case PORT_ROLE_TRANSITION_SM_ALTERNATE_AGREED_EXEC:
9efd308e
DV		 1810 p->proposed = false;
1811 p->agree = true;
1812 p->new_info = true;
6448df94
JR		 1813 if (check_selected_role_change(p, ROLE_ALTERNATE)) {
1814 /* Global transition. */
1815 } else {
1816 p->port_role_transition_sm_state =
1817 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1818 }
9efd308e
DV		 1819 break;
1820 case PORT_ROLE_TRANSITION_SM_ALTERNATE_PROPOSED_EXEC:
1821 set_sync_tree(p);
1822 p->proposed = false;
6448df94
JR		 1823 if (check_selected_role_change(p, ROLE_ALTERNATE)) {
1824 /* Global transition. */
1825 } else {
1826 p->port_role_transition_sm_state =
1827 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1828 }
9efd308e
DV		 1829 break;
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;
73c7216a 1834 /* fall through */
9efd308e
DV		 1835 case PORT_ROLE_TRANSITION_SM_BLOCK_PORT:
1836 if (check_selected_role_change(p, ROLE_ALTERNATE)) {
6448df94 1837 /* Global transition. */
311fb15b
JR		 1838 } else if (p->selected && !p->updt_info && !p->learning &&
1839 !p->forwarding) {
9efd308e
DV		 1840 p->port_role_transition_sm_state =
1841 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1842 }
1843 break;
1844 case PORT_ROLE_TRANSITION_SM_BACKUP_PORT_EXEC:
1845 p->rb_while = 2 * p->designated_times.hello_time;
6448df94
JR		 1846 if (check_selected_role_change(p, ROLE_ALTERNATE)) {
1847 /* Global transition. */
1848 } else {
1849 p->port_role_transition_sm_state =
1850 PORT_ROLE_TRANSITION_SM_ALTERNATE_PORT_EXEC;
1851 }
9efd308e
DV		 1852 break;
1853 default:
1854 OVS_NOT_REACHED();
73c7216a 1855 /* fall through */
9efd308e
DV		 1856 }
1857 if (old_state != p->port_role_transition_sm_state) {
1858 r->changes = true;
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);
1862 }
1863 if (last_role != p->role) {
9efd308e
DV		 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));
1867 }
1868 return 0;
1869}
1870
1871/* [17.30 - Port state transition state machine] */
1872
1873static void
1874enable_learning(struct rstp_port *p)
f025bcb7 1875 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1876{
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
1880 * enabled.
1881 */
f025bcb7 1882 rstp_port_set_state__(p, RSTP_LEARNING);
9efd308e
DV		 1883}
1884
1885static void
1886enable_forwarding(struct rstp_port *p)
f025bcb7 1887 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1888{
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
1892 * enabled.
1893 */
f025bcb7 1894 rstp_port_set_state__(p, RSTP_FORWARDING);
9efd308e
DV		 1895}
1896
1897static void
1898disable_learning(struct rstp_port *p)
f025bcb7 1899 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1900{
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.
1905 */
f025bcb7 1906 rstp_port_set_state__(p, RSTP_DISCARDING);
9efd308e
DV		 1907}
1908
1909static void
1910disable_forwarding(struct rstp_port *p)
f025bcb7 1911 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1912{
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
1916 * stopped.
1917 */
f025bcb7 1918 rstp_port_set_state__(p, RSTP_DISCARDING);
9efd308e
DV		 1919}
1920
1921static int
1922port_state_transition_sm(struct rstp_port *p)
f025bcb7 1923 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1924{
1925 enum port_state_transition_state_machine old_state;
1926 struct rstp *r;
1927
1928 old_state = p->port_state_transition_sm_state;
1929 r = p->rstp;
1930
1931 switch (p->port_state_transition_sm_state) {
1932 case PORT_STATE_TRANSITION_SM_INIT:
1933 if (r->begin) {
1934 p->port_state_transition_sm_state =
1935 PORT_STATE_TRANSITION_SM_DISCARDING_EXEC;
1936 }
1937 break;
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;
73c7216a 1945 /* fall through */
9efd308e
DV		 1946 case PORT_STATE_TRANSITION_SM_DISCARDING:
1947 if (p->learn) {
1948 p->port_state_transition_sm_state =
1949 PORT_STATE_TRANSITION_SM_LEARNING_EXEC;
1950 }
1951 break;
1952 case PORT_STATE_TRANSITION_SM_LEARNING_EXEC:
1953 enable_learning(p);
1954 p->learning = true;
1955 p->port_state_transition_sm_state = PORT_STATE_TRANSITION_SM_LEARNING;
73c7216a 1956 /* fall through */
9efd308e
DV		 1957 case PORT_STATE_TRANSITION_SM_LEARNING:
1958 if (!p->learn) {
1959 p->port_state_transition_sm_state =
1960 PORT_STATE_TRANSITION_SM_DISCARDING_EXEC;
311fb15b 1961 } else if (p->forward) {
9efd308e
DV		 1962 p->port_state_transition_sm_state =
1963 PORT_STATE_TRANSITION_SM_FORWARDING_EXEC;
1964 }
1965 break;
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;
73c7216a 1971 /* fall through */
9efd308e
DV		 1972 case PORT_STATE_TRANSITION_SM_FORWARDING:
1973 if (!p->forward) {
1974 p->port_state_transition_sm_state =
1975 PORT_STATE_TRANSITION_SM_DISCARDING_EXEC;
1976 }
1977 break;
1978 default:
1979 OVS_NOT_REACHED();
73c7216a 1980 /* fall through */
9efd308e
DV		 1981 }
1982 if (old_state != p->port_state_transition_sm_state) {
1983 r->changes = true;
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);
1987 }
1988 return 0;
1989}
1990
1991/* [17.31 - Topology Change state machine] */
1992
1993static void
1994new_tc_while(struct rstp_port *p)
f025bcb7 1995 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 1996{
1997 struct rstp *r;
1998
1999 r = p->rstp;
2000 if (p->tc_while == 0 && p->send_rstp == true) {
2001 p->tc_while = r->bridge_hello_time + 1;
2002 p->new_info = true;
311fb15b 2003 } else if (p->tc_while == 0 && p->send_rstp == false) {
9efd308e
DV		 2004 p->tc_while = r->bridge_max_age + r->bridge_forward_delay;
2005 }
2006}
2007
2008/* [17.21.18 setTcPropTree()]
2009 * Sets tcprop for all Ports except the Port that called the procedure.
2010 */
2011static void
2012set_tc_prop_tree(struct rstp_port *p)
f025bcb7 2013 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 2014{
2015 struct rstp *r;
2016 struct rstp_port *p1;
2017
2018 r = p->rstp;
d5f31dc8 2019 HMAP_FOR_EACH (p1, node, &r->ports) {
37db915e
JR		 2020 /* Set tc_prop on every port, except the one calling this
2021 * function. */
2022 if (p1->port_number != p->port_number) {
2023 p1->tc_prop = true;
9efd308e
DV		 2024 }
2025 }
2026}
2027
2028static void
2029set_tc_prop_bridge(struct rstp_port *p) /* not specified in 802.1D-2004. */
f025bcb7 2030 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 2031{
2032 set_tc_prop_tree(p); /* see 802.1w-2001. */
2033}
2034
2035static int
2036topology_change_sm(struct rstp_port *p)
f025bcb7 2037 OVS_REQUIRES(rstp_mutex)
9efd308e
DV		 2038{
2039 enum topology_change_state_machine old_state;
2040 struct rstp *r;
2041
2042 old_state = p->topology_change_sm_state;
2043 r = p->rstp;
2044
2045 switch (p->topology_change_sm_state) {
2046 case TOPOLOGY_CHANGE_SM_INIT:
2047 if (r->begin) {
2048 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_INACTIVE_EXEC;
2049 }
2050 break;
2051 case TOPOLOGY_CHANGE_SM_INACTIVE_EXEC:
2052 p->fdb_flush = true;
2053 p->tc_while = 0;
2054 p->tc_ack = false;
2055 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_INACTIVE;
73c7216a 2056 /* fall through */
9efd308e
DV		 2057 case TOPOLOGY_CHANGE_SM_INACTIVE:
2058 if (p->learn && !p->fdb_flush) {
2059 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING_EXEC;
2060 }
2061 break;
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;
73c7216a 2066 /* fall through */
9efd308e 2067 case TOPOLOGY_CHANGE_SM_LEARNING:
311fb15b 2068 if (p->role != ROLE_ROOT && p->role != ROLE_DESIGNATED &&
9efd308e 2069 !(p->learn || p->learning) && !(p->rcvd_tc || p->rcvd_tcn ||
311fb15b 2070 p->rcvd_tc_ack || p->tc_prop)) {
9efd308e 2071 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_INACTIVE_EXEC;
311fb15b 2072 } else if (p->rcvd_tc || p->rcvd_tcn || p->rcvd_tc_ack || p->tc_prop) {
9efd308e 2073 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING_EXEC;
311fb15b
JR		 2074 } else if ((p->role == ROLE_ROOT || p->role == ROLE_DESIGNATED)
2075 && p->forward && !p->oper_edge) {
9efd308e
DV		 2076 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_DETECTED_EXEC;
2077 }
2078 break;
2079 case TOPOLOGY_CHANGE_SM_DETECTED_EXEC:
2080 new_tc_while(p);
2081 set_tc_prop_tree(p);
2082 p->new_info = true;
2083 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE_EXEC;
73c7216a 2084 /* fall through */
9efd308e
DV		 2085 case TOPOLOGY_CHANGE_SM_ACTIVE_EXEC:
2086 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
73c7216a 2087 /* fall through */
9efd308e 2088 case TOPOLOGY_CHANGE_SM_ACTIVE:
311fb15b
JR		 2089 if ((p->role != ROLE_ROOT && p->role != ROLE_DESIGNATED)
2090 || p->oper_edge) {
9efd308e 2091 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_LEARNING_EXEC;
311fb15b 2092 } else if (p->rcvd_tcn) {
9efd308e 2093 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_NOTIFIED_TCN_EXEC;
311fb15b 2094 } else if (p->rcvd_tc) {
9efd308e 2095 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_NOTIFIED_TC_EXEC;
311fb15b 2096 } else if (p->tc_prop && !p->oper_edge) {
9efd308e 2097 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_PROPAGATING_EXEC;
311fb15b 2098 } else if (p->rcvd_tc_ack) {
9efd308e
DV		 2099 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACKNOWLEDGED_EXEC;
2100 }
2101 break;
2102 case TOPOLOGY_CHANGE_SM_ACKNOWLEDGED_EXEC:
2103 p->tc_while = 0;
2104 p->rcvd_tc_ack = false;
2105 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
2106 break;
2107 case TOPOLOGY_CHANGE_SM_PROPAGATING_EXEC:
2108 new_tc_while(p);
2109 p->fdb_flush = true;
2110 p->tc_prop = false;
2111 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
2112 break;
2113 case TOPOLOGY_CHANGE_SM_NOTIFIED_TC_EXEC:
2114 p->rcvd_tcn = p->rcvd_tc = false;
2115 if (p->role == ROLE_DESIGNATED) {
2116 p->tc_ack = true;
2117 }
2118 set_tc_prop_bridge(p);
2119 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_ACTIVE;
2120 break;
2121 case TOPOLOGY_CHANGE_SM_NOTIFIED_TCN_EXEC:
2122 new_tc_while(p);
75735c80 2123 p->topology_change_sm_state = TOPOLOGY_CHANGE_SM_NOTIFIED_TC_EXEC;
9efd308e
DV		 2124 break;
2125 default:
2126 OVS_NOT_REACHED();
73c7216a 2127 /* fall through */
9efd308e
DV		 2128 }
2129 if (old_state != p->topology_change_sm_state) {
2130 r->changes = true;
4b30ba05
JR		 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);
9efd308e
DV		 2133 }
2134 return 0;
2135}
2136
2137/****************************************************************************
2138 * [17.6] Priority vector calculation helper functions
2139 ****************************************************************************/
2140
a0478216
JR		 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.
2144 *
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).
9efd308e
DV		 2148 */
2149static enum vector_comparison
a0478216
JR		 2150compare_rstp_priority_vectors(const struct rstp_priority_vector *v1,
2151 const struct rstp_priority_vector *v2)
9efd308e 2152{
26c0e924 2153 VLOG_DBG("v1: "RSTP_ID_FMT", %u, "RSTP_ID_FMT", %d, %d",
9efd308e 2154 RSTP_ID_ARGS(v1->root_bridge_id), v1->root_path_cost,
26c0e924
DV		 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",
9efd308e 2158 RSTP_ID_ARGS(v2->root_bridge_id), v2->root_path_cost,
26c0e924
DV		 2159 RSTP_ID_ARGS(v2->designated_bridge_id), v2->designated_port_id,
2160 v2->bridge_port_id);
9efd308e 2161
a0478216
JR		 2162 /* [17.6]
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:
2168 *
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))
2177 */
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) {
26c0e924
DV		 2195 if (v1->bridge_port_id < v2->bridge_port_id) {
2196 VLOG_DBG("superior");
2197 return SUPERIOR;
2198 }
2199 else if (v1->bridge_port_id > v2->bridge_port_id) {
2200 VLOG_DBG("inferior");
2201 return INFERIOR;
2202 }
a0478216
JR		 2203 VLOG_DBG("superior_same");
2204 return SAME;
2205 }
2206 VLOG_DBG("superior");
9efd308e
DV		 2207 return SUPERIOR;
2208 }
a0478216
JR		 2209
2210 VLOG_DBG("inferior");
2211 return INFERIOR;
9efd308e
DV		 2212}
2213
2214static bool
311fb15b
JR		 2215rstp_times_equal(struct rstp_times *t1, struct rstp_times *t2)
2216{
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;
9efd308e 2221}
openvswitch mirror