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