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