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