2 * EIGRPd Finite State Machine (DUAL).
3 * Copyright (C) 2013-2014
11 * This file is part of GNU Zebra.
13 * GNU Zebra is free software; you can redistribute it and/or modify it
14 * under the terms of the GNU General Public License as published by the
15 * Free Software Foundation; either version 2, or (at your option) any
18 * GNU Zebra is distributed in the hope that it will be useful, but
19 * WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
21 * General Public License for more details.
23 * You should have received a copy of the GNU General Public License along
24 * with this program; see the file COPYING; if not, write to the Free Software
25 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
27 * This file contains functions for executing logic of finite state machine
32 * +=====================================+
36 * +=====================================+
38 * (3)| | (1)| | (1)| |
39 * | (0)| | (3)| | (2)|
40 * | | | | | +---------------+
42 * +--------+ | | | +-----------------+ \
47 * +===========+ (6) +===========+ +===========+ (6) +===========+
48 * | |------->| | (5) | |-------->| |
49 * | | (4) | |------>| | (4) | |
50 * | ACTIVE 0 |<-------| ACTIVE 1 | | ACTIVE 2 |<--------| ACTIVE 3
52 * +--| | +--| | +--| | +--| |
53 * | +===========+ | +===========+ | +===========+ |
55 * | ^ |(5) | ^ | ^ ^ | ^
56 * | | +---------|------|------------|----+ | | |
57 * +-------+ +------+ +---------+ +---------+
60 * 0- input event other than query from successor, FC not satisfied
61 * 1- last reply, FD is reset
62 * 2- query from successor, FC not satisfied
63 * 3- last reply, FC satisfied with current value of FDij
64 * 4- distance increase while in active state
65 * 5- query from successor while in active state
66 * 6- last reply, FC not satisfied with current value of FDij
67 * 7- state not changed, usually by receiving not last reply
80 #include "eigrpd/eigrp_structs.h"
81 #include "eigrpd/eigrpd.h"
82 #include "eigrpd/eigrp_interface.h"
83 #include "eigrpd/eigrp_neighbor.h"
84 #include "eigrpd/eigrp_packet.h"
85 #include "eigrpd/eigrp_zebra.h"
86 #include "eigrpd/eigrp_vty.h"
87 #include "eigrpd/eigrp_network.h"
88 #include "eigrpd/eigrp_dump.h"
89 #include "eigrpd/eigrp_topology.h"
90 #include "eigrpd/eigrp_fsm.h"
95 int eigrp_fsm_event_keep_state(struct eigrp_fsm_action_message
*);
96 int eigrp_fsm_event_nq_fcn(struct eigrp_fsm_action_message
*);
97 int eigrp_fsm_event_q_fcn(struct eigrp_fsm_action_message
*);
98 int eigrp_fsm_event_lr(struct eigrp_fsm_action_message
*);
99 int eigrp_fsm_event_dinc(struct eigrp_fsm_action_message
*);
100 int eigrp_fsm_event_lr_fcs(struct eigrp_fsm_action_message
*);
101 int eigrp_fsm_event_lr_fcn(struct eigrp_fsm_action_message
*);
102 int eigrp_fsm_event_qact(struct eigrp_fsm_action_message
*);
104 //---------------------------------------------------------------------
107 * NSM - field of fields of struct containing one function each.
108 * Which function is used depends on actual state of FSM and occurred
109 * event(arrow in diagram). Usage:
110 * NSM[actual/starting state][occurred event].func
111 * Functions are should be executed within separate thread.
114 int (*func
)(struct eigrp_fsm_action_message
*);
115 } NSM
[EIGRP_FSM_STATE_MAX
][EIGRP_FSM_EVENT_MAX
] = {
118 {eigrp_fsm_event_nq_fcn
}, /* Event 0 */
119 {eigrp_fsm_event_keep_state
}, /* Event 1 */
120 {eigrp_fsm_event_q_fcn
}, /* Event 2 */
121 {eigrp_fsm_event_keep_state
}, /* Event 3 */
122 {eigrp_fsm_event_keep_state
}, /* Event 4 */
123 {eigrp_fsm_event_keep_state
}, /* Event 5 */
124 {eigrp_fsm_event_keep_state
}, /* Event 6 */
125 {eigrp_fsm_event_keep_state
}, /* Event 7 */
129 {eigrp_fsm_event_keep_state
}, /* Event 0 */
130 {eigrp_fsm_event_keep_state
}, /* Event 1 */
131 {eigrp_fsm_event_keep_state
}, /* Event 2 */
132 {eigrp_fsm_event_lr_fcs
}, /* Event 3 */
133 {eigrp_fsm_event_keep_state
}, /* Event 4 */
134 {eigrp_fsm_event_qact
}, /* Event 5 */
135 {eigrp_fsm_event_lr_fcn
}, /* Event 6 */
136 {eigrp_fsm_event_keep_state
}, /* Event 7 */
140 {eigrp_fsm_event_keep_state
}, /* Event 0 */
141 {eigrp_fsm_event_lr
}, /* Event 1 */
142 {eigrp_fsm_event_keep_state
}, /* Event 2 */
143 {eigrp_fsm_event_keep_state
}, /* Event 3 */
144 {eigrp_fsm_event_dinc
}, /* Event 4 */
145 {eigrp_fsm_event_qact
}, /* Event 5 */
146 {eigrp_fsm_event_keep_state
}, /* Event 6 */
147 {eigrp_fsm_event_keep_state
}, /* Event 7 */
151 {eigrp_fsm_event_keep_state
}, /* Event 0 */
152 {eigrp_fsm_event_keep_state
}, /* Event 1 */
153 {eigrp_fsm_event_keep_state
}, /* Event 2 */
154 {eigrp_fsm_event_lr_fcs
}, /* Event 3 */
155 {eigrp_fsm_event_keep_state
}, /* Event 4 */
156 {eigrp_fsm_event_keep_state
}, /* Event 5 */
157 {eigrp_fsm_event_lr_fcn
}, /* Event 6 */
158 {eigrp_fsm_event_keep_state
}, /* Event 7 */
162 {eigrp_fsm_event_keep_state
}, /* Event 0 */
163 {eigrp_fsm_event_lr
}, /* Event 1 */
164 {eigrp_fsm_event_keep_state
}, /* Event 2 */
165 {eigrp_fsm_event_keep_state
}, /* Event 3 */
166 {eigrp_fsm_event_dinc
}, /* Event 4 */
167 {eigrp_fsm_event_keep_state
}, /* Event 5 */
168 {eigrp_fsm_event_keep_state
}, /* Event 6 */
169 {eigrp_fsm_event_keep_state
}, /* Event 7 */
174 * Main function in which are make decisions which event occurred.
175 * msg - argument of type struct eigrp_fsm_action_message contain
176 * details about what happen
178 * Return number of occurred event (arrow in diagram).
181 static int eigrp_get_fsm_event(struct eigrp_fsm_action_message
*msg
)
183 // Loading base information from message
184 // struct eigrp *eigrp = msg->eigrp;
185 struct eigrp_prefix_entry
*prefix
= msg
->prefix
;
186 struct eigrp_nexthop_entry
*entry
= msg
->entry
;
187 u_char actual_state
= prefix
->state
;
188 enum metric_change change
;
191 entry
= eigrp_nexthop_entry_new();
192 entry
->adv_router
= msg
->adv_router
;
193 entry
->ei
= msg
->adv_router
->ei
;
194 entry
->prefix
= prefix
;
199 * Calculate resultant metrics and insert to correct position
202 change
= eigrp_topology_update_distance(msg
);
204 switch (actual_state
) {
205 case EIGRP_FSM_STATE_PASSIVE
: {
206 struct eigrp_nexthop_entry
*head
=
207 listnode_head(prefix
->entries
);
209 if (head
->reported_distance
< prefix
->fdistance
) {
210 return EIGRP_FSM_KEEP_STATE
;
213 * if best entry doesn't satisfy feasibility condition it means
214 * move to active state
215 * dependently if it was query from successor
217 if (msg
->packet_type
== EIGRP_OPC_QUERY
) {
218 return EIGRP_FSM_EVENT_Q_FCN
;
220 return EIGRP_FSM_EVENT_NQ_FCN
;
225 case EIGRP_FSM_STATE_ACTIVE_0
: {
226 if (msg
->packet_type
== EIGRP_OPC_REPLY
) {
227 struct eigrp_nexthop_entry
*head
=
228 listnode_head(prefix
->entries
);
230 listnode_delete(prefix
->rij
, entry
->adv_router
);
231 if (prefix
->rij
->count
)
232 return EIGRP_FSM_KEEP_STATE
;
234 zlog_info("All reply received\n");
235 if (head
->reported_distance
236 < prefix
->fdistance
) {
237 return EIGRP_FSM_EVENT_LR_FCS
;
240 return EIGRP_FSM_EVENT_LR_FCN
;
241 } else if (msg
->packet_type
== EIGRP_OPC_QUERY
243 & EIGRP_NEXTHOP_ENTRY_SUCCESSOR_FLAG
)) {
244 return EIGRP_FSM_EVENT_QACT
;
247 return EIGRP_FSM_KEEP_STATE
;
251 case EIGRP_FSM_STATE_ACTIVE_1
: {
252 if (msg
->packet_type
== EIGRP_OPC_QUERY
253 && (entry
->flags
& EIGRP_NEXTHOP_ENTRY_SUCCESSOR_FLAG
)) {
254 return EIGRP_FSM_EVENT_QACT
;
255 } else if (msg
->packet_type
== EIGRP_OPC_REPLY
) {
256 listnode_delete(prefix
->rij
, entry
->adv_router
);
258 if (change
== METRIC_INCREASE
260 & EIGRP_NEXTHOP_ENTRY_SUCCESSOR_FLAG
)) {
261 return EIGRP_FSM_EVENT_DINC
;
262 } else if (prefix
->rij
->count
) {
263 return EIGRP_FSM_KEEP_STATE
;
265 zlog_info("All reply received\n");
266 return EIGRP_FSM_EVENT_LR
;
268 } else if (msg
->packet_type
== EIGRP_OPC_UPDATE
&& change
== 1
270 & EIGRP_NEXTHOP_ENTRY_SUCCESSOR_FLAG
)) {
271 return EIGRP_FSM_EVENT_DINC
;
273 return EIGRP_FSM_KEEP_STATE
;
277 case EIGRP_FSM_STATE_ACTIVE_2
: {
278 if (msg
->packet_type
== EIGRP_OPC_REPLY
) {
279 struct eigrp_nexthop_entry
*head
=
280 listnode_head(prefix
->entries
);
282 listnode_delete(prefix
->rij
, entry
->adv_router
);
283 if (prefix
->rij
->count
) {
284 return EIGRP_FSM_KEEP_STATE
;
286 zlog_info("All reply received\n");
287 if (head
->reported_distance
288 < prefix
->fdistance
) {
289 return EIGRP_FSM_EVENT_LR_FCS
;
292 return EIGRP_FSM_EVENT_LR_FCN
;
295 return EIGRP_FSM_KEEP_STATE
;
299 case EIGRP_FSM_STATE_ACTIVE_3
: {
300 if (msg
->packet_type
== EIGRP_OPC_REPLY
) {
301 listnode_delete(prefix
->rij
, entry
->adv_router
);
303 if (change
== METRIC_INCREASE
305 & EIGRP_NEXTHOP_ENTRY_SUCCESSOR_FLAG
)) {
306 return EIGRP_FSM_EVENT_DINC
;
307 } else if (prefix
->rij
->count
) {
308 return EIGRP_FSM_KEEP_STATE
;
310 zlog_info("All reply received\n");
311 return EIGRP_FSM_EVENT_LR
;
313 } else if (msg
->packet_type
== EIGRP_OPC_UPDATE
&& change
== 1
315 & EIGRP_NEXTHOP_ENTRY_SUCCESSOR_FLAG
)) {
316 return EIGRP_FSM_EVENT_DINC
;
318 return EIGRP_FSM_KEEP_STATE
;
324 return EIGRP_FSM_KEEP_STATE
;
328 * Function made to execute in separate thread.
329 * Load argument from thread and execute proper NSM function
331 int eigrp_fsm_event(struct eigrp_fsm_action_message
*msg
)
333 int event
= eigrp_get_fsm_event(msg
);
334 zlog_info("EIGRP AS: %d State: %d Event: %d Network: %s",
335 msg
->eigrp
->AS
, msg
->prefix
->state
, event
,
336 eigrp_topology_ip_string(msg
->prefix
));
337 (*(NSM
[msg
->prefix
->state
][event
].func
))(msg
);
343 * Function of event 0.
346 int eigrp_fsm_event_nq_fcn(struct eigrp_fsm_action_message
*msg
)
348 struct eigrp
*eigrp
= msg
->eigrp
;
349 struct eigrp_prefix_entry
*prefix
= msg
->prefix
;
350 struct list
*successors
= eigrp_topology_get_successor(prefix
);
351 struct eigrp_nexthop_entry
*ne
;
353 assert(successors
); // If this is NULL we have shit the bed, fun huh?
355 ne
= listnode_head(successors
);
356 prefix
->state
= EIGRP_FSM_STATE_ACTIVE_1
;
357 prefix
->rdistance
= prefix
->distance
= prefix
->fdistance
=
359 prefix
->reported_metric
= ne
->total_metric
;
361 if (eigrp_nbr_count_get()) {
362 prefix
->req_action
|= EIGRP_FSM_NEED_QUERY
;
363 listnode_add(eigrp
->topology_changes_internalIPV4
, prefix
);
365 eigrp_fsm_event_lr(msg
); // in the case that there are no more
369 list_delete_and_null(&successors
);
374 int eigrp_fsm_event_q_fcn(struct eigrp_fsm_action_message
*msg
)
376 struct eigrp
*eigrp
= msg
->eigrp
;
377 struct eigrp_prefix_entry
*prefix
= msg
->prefix
;
378 struct list
*successors
= eigrp_topology_get_successor(prefix
);
379 struct eigrp_nexthop_entry
*ne
;
381 assert(successors
); // If this is NULL somebody poked us in the eye.
383 ne
= listnode_head(successors
);
384 prefix
->state
= EIGRP_FSM_STATE_ACTIVE_3
;
385 prefix
->rdistance
= prefix
->distance
= prefix
->fdistance
=
387 prefix
->reported_metric
= ne
->total_metric
;
388 if (eigrp_nbr_count_get()) {
389 prefix
->req_action
|= EIGRP_FSM_NEED_QUERY
;
390 listnode_add(eigrp
->topology_changes_internalIPV4
, prefix
);
392 eigrp_fsm_event_lr(msg
); // in the case that there are no more
396 list_delete_and_null(&successors
);
401 int eigrp_fsm_event_keep_state(struct eigrp_fsm_action_message
*msg
)
403 struct eigrp_prefix_entry
*prefix
= msg
->prefix
;
404 struct eigrp_nexthop_entry
*ne
= listnode_head(prefix
->entries
);
406 if (prefix
->state
== EIGRP_FSM_STATE_PASSIVE
) {
407 if (!eigrp_metrics_is_same(prefix
->reported_metric
,
409 prefix
->rdistance
= prefix
->fdistance
=
410 prefix
->distance
= ne
->distance
;
411 prefix
->reported_metric
=
413 if (msg
->packet_type
== EIGRP_OPC_QUERY
)
414 eigrp_send_reply(msg
->adv_router
, prefix
);
415 prefix
->req_action
|= EIGRP_FSM_NEED_UPDATE
;
417 (eigrp_lookup())->topology_changes_internalIPV4
,
420 eigrp_topology_update_node_flags(prefix
);
421 eigrp_update_routing_table(prefix
);
424 if (msg
->packet_type
== EIGRP_OPC_QUERY
)
425 eigrp_send_reply(msg
->adv_router
, prefix
);
430 int eigrp_fsm_event_lr(struct eigrp_fsm_action_message
*msg
)
432 struct eigrp
*eigrp
= msg
->eigrp
;
433 struct eigrp_prefix_entry
*prefix
= msg
->prefix
;
434 struct eigrp_nexthop_entry
*ne
= listnode_head(prefix
->entries
);
436 prefix
->fdistance
= prefix
->distance
= prefix
->rdistance
=
438 prefix
->reported_metric
= ne
->total_metric
;
440 if (prefix
->state
== EIGRP_FSM_STATE_ACTIVE_3
) {
441 struct list
*successors
= eigrp_topology_get_successor(prefix
);
443 assert(successors
); // It's like Napolean and Waterloo
445 ne
= listnode_head(successors
);
446 eigrp_send_reply(ne
->adv_router
,
448 list_delete_and_null(&successors
);
451 prefix
->state
= EIGRP_FSM_STATE_PASSIVE
;
452 prefix
->req_action
|= EIGRP_FSM_NEED_UPDATE
;
453 listnode_add(eigrp
->topology_changes_internalIPV4
, prefix
);
454 eigrp_topology_update_node_flags(prefix
);
455 eigrp_update_routing_table(prefix
);
456 eigrp_update_topology_table_prefix(eigrp
->topology_table
, prefix
);
461 int eigrp_fsm_event_dinc(struct eigrp_fsm_action_message
*msg
)
463 struct list
*successors
= eigrp_topology_get_successor(msg
->prefix
);
464 struct eigrp_nexthop_entry
*ne
;
466 assert(successors
); // Trump and his big hands
468 ne
= listnode_head(successors
);
469 msg
->prefix
->state
= msg
->prefix
->state
== EIGRP_FSM_STATE_ACTIVE_1
470 ? EIGRP_FSM_STATE_ACTIVE_0
471 : EIGRP_FSM_STATE_ACTIVE_2
;
472 msg
->prefix
->distance
= ne
->distance
;
473 if (!msg
->prefix
->rij
->count
)
474 (*(NSM
[msg
->prefix
->state
][eigrp_get_fsm_event(msg
)].func
))(
478 list_delete_and_null(&successors
);
482 int eigrp_fsm_event_lr_fcs(struct eigrp_fsm_action_message
*msg
)
484 struct eigrp
*eigrp
= msg
->eigrp
;
485 struct eigrp_prefix_entry
*prefix
= msg
->prefix
;
486 struct eigrp_nexthop_entry
*ne
= listnode_head(prefix
->entries
);
488 prefix
->state
= EIGRP_FSM_STATE_PASSIVE
;
489 prefix
->distance
= prefix
->rdistance
= ne
->distance
;
490 prefix
->reported_metric
= ne
->total_metric
;
491 prefix
->fdistance
= prefix
->fdistance
> prefix
->distance
494 if (prefix
->state
== EIGRP_FSM_STATE_ACTIVE_2
) {
495 struct list
*successors
= eigrp_topology_get_successor(prefix
);
497 assert(successors
); // Having a spoon and all you need is a
499 ne
= listnode_head(successors
);
500 eigrp_send_reply(ne
->adv_router
,
503 list_delete_and_null(&successors
);
505 prefix
->req_action
|= EIGRP_FSM_NEED_UPDATE
;
506 listnode_add(eigrp
->topology_changes_internalIPV4
, prefix
);
507 eigrp_topology_update_node_flags(prefix
);
508 eigrp_update_routing_table(prefix
);
509 eigrp_update_topology_table_prefix(eigrp
->topology_table
, prefix
);
514 int eigrp_fsm_event_lr_fcn(struct eigrp_fsm_action_message
*msg
)
516 struct eigrp
*eigrp
= msg
->eigrp
;
517 struct eigrp_prefix_entry
*prefix
= msg
->prefix
;
518 struct eigrp_nexthop_entry
*best_successor
;
519 struct list
*successors
= eigrp_topology_get_successor(prefix
);
521 assert(successors
); // Routing without a stack
523 prefix
->state
= prefix
->state
== EIGRP_FSM_STATE_ACTIVE_0
524 ? EIGRP_FSM_STATE_ACTIVE_1
525 : EIGRP_FSM_STATE_ACTIVE_3
;
527 best_successor
= listnode_head(successors
);
528 prefix
->rdistance
= prefix
->distance
= best_successor
->distance
;
529 prefix
->reported_metric
= best_successor
->total_metric
;
531 if (eigrp_nbr_count_get()) {
532 prefix
->req_action
|= EIGRP_FSM_NEED_QUERY
;
533 listnode_add(eigrp
->topology_changes_internalIPV4
, prefix
);
535 eigrp_fsm_event_lr(msg
); // in the case that there are no more
539 list_delete_and_null(&successors
);
544 int eigrp_fsm_event_qact(struct eigrp_fsm_action_message
*msg
)
546 struct list
*successors
= eigrp_topology_get_successor(msg
->prefix
);
547 struct eigrp_nexthop_entry
*ne
;
549 assert(successors
); // Cats and no Dogs
551 ne
= listnode_head(successors
);
552 msg
->prefix
->state
= EIGRP_FSM_STATE_ACTIVE_2
;
553 msg
->prefix
->distance
= ne
->distance
;
555 list_delete_and_null(&successors
);