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 */
173 static const char *packet_type2str(uint8_t packet_type
)
175 if (packet_type
== EIGRP_OPC_UPDATE
)
177 if (packet_type
== EIGRP_OPC_REQUEST
)
179 if (packet_type
== EIGRP_OPC_QUERY
)
181 if (packet_type
== EIGRP_OPC_REPLY
)
183 if (packet_type
== EIGRP_OPC_HELLO
)
185 if (packet_type
== EIGRP_OPC_IPXSAP
)
187 if (packet_type
== EIGRP_OPC_ACK
)
189 if (packet_type
== EIGRP_OPC_SIAQUERY
)
191 if (packet_type
== EIGRP_OPC_SIAREPLY
)
197 static const char *prefix_state2str(enum eigrp_fsm_states state
)
200 case EIGRP_FSM_STATE_PASSIVE
:
202 case EIGRP_FSM_STATE_ACTIVE_0
:
203 return "Active oij0";
204 case EIGRP_FSM_STATE_ACTIVE_1
:
205 return "Active oij1";
206 case EIGRP_FSM_STATE_ACTIVE_2
:
207 return "Active oij2";
208 case EIGRP_FSM_STATE_ACTIVE_3
:
209 return "Active oij3";
215 static const char *fsm_state2str(enum eigrp_fsm_events event
)
218 case EIGRP_FSM_KEEP_STATE
:
219 return "Keep State Event";
220 case EIGRP_FSM_EVENT_NQ_FCN
:
221 return "Non Query Event Feasability not satisfied";
222 case EIGRP_FSM_EVENT_LR
:
223 return "Last Reply Event";
224 case EIGRP_FSM_EVENT_Q_FCN
:
225 return "Query Event Feasability not satisfied";
226 case EIGRP_FSM_EVENT_LR_FCS
:
227 return "Last Reply Event Feasability satisfied";
228 case EIGRP_FSM_EVENT_DINC
:
229 return "Distance Increase Event";
230 case EIGRP_FSM_EVENT_QACT
:
231 return "Query from Successor while in active state";
232 case EIGRP_FSM_EVENT_LR_FCN
:
233 return "Last Reply Event, Feasibility not satisfied";
239 static const char *change2str(enum metric_change change
)
242 case METRIC_DECREASE
:
246 case METRIC_INCREASE
:
253 * Main function in which are make decisions which event occurred.
254 * msg - argument of type struct eigrp_fsm_action_message contain
255 * details about what happen
257 * Return number of occurred event (arrow in diagram).
260 static enum eigrp_fsm_events
261 eigrp_get_fsm_event(struct eigrp_fsm_action_message
*msg
)
263 // Loading base information from message
264 // struct eigrp *eigrp = msg->eigrp;
265 struct eigrp_prefix_entry
*prefix
= msg
->prefix
;
266 struct eigrp_nexthop_entry
*entry
= msg
->entry
;
267 uint8_t actual_state
= prefix
->state
;
268 enum metric_change change
;
271 entry
= eigrp_nexthop_entry_new();
272 entry
->adv_router
= msg
->adv_router
;
273 entry
->ei
= msg
->adv_router
->ei
;
274 entry
->prefix
= prefix
;
279 * Calculate resultant metrics and insert to correct position
282 change
= eigrp_topology_update_distance(msg
);
284 /* Store for display later */
285 msg
->change
= change
;
287 switch (actual_state
) {
288 case EIGRP_FSM_STATE_PASSIVE
: {
289 struct eigrp_nexthop_entry
*head
=
290 listnode_head(prefix
->entries
);
292 if (head
->reported_distance
< prefix
->fdistance
) {
293 return EIGRP_FSM_KEEP_STATE
;
296 * if best entry doesn't satisfy feasibility condition it means
297 * move to active state
298 * dependently if it was query from successor
300 if (msg
->packet_type
== EIGRP_OPC_QUERY
) {
301 return EIGRP_FSM_EVENT_Q_FCN
;
303 return EIGRP_FSM_EVENT_NQ_FCN
;
308 case EIGRP_FSM_STATE_ACTIVE_0
: {
309 if (msg
->packet_type
== EIGRP_OPC_REPLY
) {
310 struct eigrp_nexthop_entry
*head
=
311 listnode_head(prefix
->entries
);
313 listnode_delete(prefix
->rij
, entry
->adv_router
);
314 if (prefix
->rij
->count
)
315 return EIGRP_FSM_KEEP_STATE
;
317 zlog_info("All reply received");
318 if (head
->reported_distance
< prefix
->fdistance
) {
319 return EIGRP_FSM_EVENT_LR_FCS
;
322 return EIGRP_FSM_EVENT_LR_FCN
;
323 } else if (msg
->packet_type
== EIGRP_OPC_QUERY
325 & EIGRP_NEXTHOP_ENTRY_SUCCESSOR_FLAG
)) {
326 return EIGRP_FSM_EVENT_QACT
;
329 return EIGRP_FSM_KEEP_STATE
;
333 case EIGRP_FSM_STATE_ACTIVE_1
: {
334 if (msg
->packet_type
== EIGRP_OPC_QUERY
335 && (entry
->flags
& EIGRP_NEXTHOP_ENTRY_SUCCESSOR_FLAG
)) {
336 return EIGRP_FSM_EVENT_QACT
;
337 } else if (msg
->packet_type
== EIGRP_OPC_REPLY
) {
338 listnode_delete(prefix
->rij
, entry
->adv_router
);
340 if (change
== METRIC_INCREASE
342 & EIGRP_NEXTHOP_ENTRY_SUCCESSOR_FLAG
)) {
343 return EIGRP_FSM_EVENT_DINC
;
344 } else if (prefix
->rij
->count
) {
345 return EIGRP_FSM_KEEP_STATE
;
347 zlog_info("All reply received");
348 return EIGRP_FSM_EVENT_LR
;
350 } else if (msg
->packet_type
== EIGRP_OPC_UPDATE
351 && change
== METRIC_INCREASE
353 & EIGRP_NEXTHOP_ENTRY_SUCCESSOR_FLAG
)) {
354 return EIGRP_FSM_EVENT_DINC
;
356 return EIGRP_FSM_KEEP_STATE
;
360 case EIGRP_FSM_STATE_ACTIVE_2
: {
361 if (msg
->packet_type
== EIGRP_OPC_REPLY
) {
362 struct eigrp_nexthop_entry
*head
=
363 listnode_head(prefix
->entries
);
365 listnode_delete(prefix
->rij
, entry
->adv_router
);
366 if (prefix
->rij
->count
) {
367 return EIGRP_FSM_KEEP_STATE
;
369 zlog_info("All reply received");
370 if (head
->reported_distance
371 < prefix
->fdistance
) {
372 return EIGRP_FSM_EVENT_LR_FCS
;
375 return EIGRP_FSM_EVENT_LR_FCN
;
378 return EIGRP_FSM_KEEP_STATE
;
382 case EIGRP_FSM_STATE_ACTIVE_3
: {
383 if (msg
->packet_type
== EIGRP_OPC_REPLY
) {
384 listnode_delete(prefix
->rij
, entry
->adv_router
);
386 if (change
== METRIC_INCREASE
388 & EIGRP_NEXTHOP_ENTRY_SUCCESSOR_FLAG
)) {
389 return EIGRP_FSM_EVENT_DINC
;
390 } else if (prefix
->rij
->count
) {
391 return EIGRP_FSM_KEEP_STATE
;
393 zlog_info("All reply received");
394 return EIGRP_FSM_EVENT_LR
;
396 } else if (msg
->packet_type
== EIGRP_OPC_UPDATE
397 && change
== METRIC_INCREASE
399 & EIGRP_NEXTHOP_ENTRY_SUCCESSOR_FLAG
)) {
400 return EIGRP_FSM_EVENT_DINC
;
402 return EIGRP_FSM_KEEP_STATE
;
408 return EIGRP_FSM_KEEP_STATE
;
412 * Function made to execute in separate thread.
413 * Load argument from thread and execute proper NSM function
415 int eigrp_fsm_event(struct eigrp_fsm_action_message
*msg
)
417 enum eigrp_fsm_events event
= eigrp_get_fsm_event(msg
);
420 "EIGRP AS: %d State: %s Event: %s Network: %pI4 Packet Type: %s Reply RIJ Count: %d change: %s",
421 msg
->eigrp
->AS
, prefix_state2str(msg
->prefix
->state
),
422 fsm_state2str(event
), &msg
->prefix
->destination
->u
.prefix4
,
423 packet_type2str(msg
->packet_type
), msg
->prefix
->rij
->count
,
424 change2str(msg
->change
));
425 (*(NSM
[msg
->prefix
->state
][event
].func
))(msg
);
431 * Function of event 0.
434 int eigrp_fsm_event_nq_fcn(struct eigrp_fsm_action_message
*msg
)
436 struct eigrp
*eigrp
= msg
->eigrp
;
437 struct eigrp_prefix_entry
*prefix
= msg
->prefix
;
438 struct list
*successors
= eigrp_topology_get_successor(prefix
);
439 struct eigrp_nexthop_entry
*ne
;
441 assert(successors
); // If this is NULL we have shit the bed, fun huh?
443 ne
= listnode_head(successors
);
444 prefix
->state
= EIGRP_FSM_STATE_ACTIVE_1
;
445 prefix
->rdistance
= prefix
->distance
= prefix
->fdistance
= ne
->distance
;
446 prefix
->reported_metric
= ne
->total_metric
;
448 if (eigrp_nbr_count_get(eigrp
)) {
449 prefix
->req_action
|= EIGRP_FSM_NEED_QUERY
;
450 listnode_add(eigrp
->topology_changes_internalIPV4
, prefix
);
452 eigrp_fsm_event_lr(msg
); // in the case that there are no more
456 list_delete(&successors
);
461 int eigrp_fsm_event_q_fcn(struct eigrp_fsm_action_message
*msg
)
463 struct eigrp
*eigrp
= msg
->eigrp
;
464 struct eigrp_prefix_entry
*prefix
= msg
->prefix
;
465 struct list
*successors
= eigrp_topology_get_successor(prefix
);
466 struct eigrp_nexthop_entry
*ne
;
468 assert(successors
); // If this is NULL somebody poked us in the eye.
470 ne
= listnode_head(successors
);
471 prefix
->state
= EIGRP_FSM_STATE_ACTIVE_3
;
472 prefix
->rdistance
= prefix
->distance
= prefix
->fdistance
= ne
->distance
;
473 prefix
->reported_metric
= ne
->total_metric
;
474 if (eigrp_nbr_count_get(eigrp
)) {
475 prefix
->req_action
|= EIGRP_FSM_NEED_QUERY
;
476 listnode_add(eigrp
->topology_changes_internalIPV4
, prefix
);
478 eigrp_fsm_event_lr(msg
); // in the case that there are no more
482 list_delete(&successors
);
487 int eigrp_fsm_event_keep_state(struct eigrp_fsm_action_message
*msg
)
489 struct eigrp
*eigrp
= msg
->eigrp
;
490 struct eigrp_prefix_entry
*prefix
= msg
->prefix
;
491 struct eigrp_nexthop_entry
*ne
= listnode_head(prefix
->entries
);
493 if (prefix
->state
== EIGRP_FSM_STATE_PASSIVE
) {
494 if (!eigrp_metrics_is_same(prefix
->reported_metric
,
496 prefix
->rdistance
= prefix
->fdistance
=
497 prefix
->distance
= ne
->distance
;
498 prefix
->reported_metric
= ne
->total_metric
;
499 if (msg
->packet_type
== EIGRP_OPC_QUERY
)
500 eigrp_send_reply(msg
->adv_router
, prefix
);
501 prefix
->req_action
|= EIGRP_FSM_NEED_UPDATE
;
502 listnode_add(eigrp
->topology_changes_internalIPV4
,
505 eigrp_topology_update_node_flags(eigrp
, prefix
);
506 eigrp_update_routing_table(eigrp
, prefix
);
509 if (msg
->packet_type
== EIGRP_OPC_QUERY
)
510 eigrp_send_reply(msg
->adv_router
, prefix
);
515 int eigrp_fsm_event_lr(struct eigrp_fsm_action_message
*msg
)
517 struct eigrp
*eigrp
= msg
->eigrp
;
518 struct eigrp_prefix_entry
*prefix
= msg
->prefix
;
519 struct eigrp_nexthop_entry
*ne
= listnode_head(prefix
->entries
);
521 prefix
->fdistance
= prefix
->distance
= prefix
->rdistance
= ne
->distance
;
522 prefix
->reported_metric
= ne
->total_metric
;
524 if (prefix
->state
== EIGRP_FSM_STATE_ACTIVE_3
) {
525 struct list
*successors
= eigrp_topology_get_successor(prefix
);
527 assert(successors
); // It's like Napolean and Waterloo
529 ne
= listnode_head(successors
);
530 eigrp_send_reply(ne
->adv_router
, prefix
);
531 list_delete(&successors
);
534 prefix
->state
= EIGRP_FSM_STATE_PASSIVE
;
535 prefix
->req_action
|= EIGRP_FSM_NEED_UPDATE
;
536 listnode_add(eigrp
->topology_changes_internalIPV4
, prefix
);
537 eigrp_topology_update_node_flags(eigrp
, prefix
);
538 eigrp_update_routing_table(eigrp
, prefix
);
539 eigrp_update_topology_table_prefix(eigrp
, eigrp
->topology_table
,
545 int eigrp_fsm_event_dinc(struct eigrp_fsm_action_message
*msg
)
547 struct list
*successors
= eigrp_topology_get_successor(msg
->prefix
);
548 struct eigrp_nexthop_entry
*ne
;
550 assert(successors
); // Trump and his big hands
552 ne
= listnode_head(successors
);
553 msg
->prefix
->state
= msg
->prefix
->state
== EIGRP_FSM_STATE_ACTIVE_1
554 ? EIGRP_FSM_STATE_ACTIVE_0
555 : EIGRP_FSM_STATE_ACTIVE_2
;
556 msg
->prefix
->distance
= ne
->distance
;
557 if (!msg
->prefix
->rij
->count
)
558 (*(NSM
[msg
->prefix
->state
][eigrp_get_fsm_event(msg
)].func
))(
562 list_delete(&successors
);
566 int eigrp_fsm_event_lr_fcs(struct eigrp_fsm_action_message
*msg
)
568 struct eigrp
*eigrp
= msg
->eigrp
;
569 struct eigrp_prefix_entry
*prefix
= msg
->prefix
;
570 struct eigrp_nexthop_entry
*ne
= listnode_head(prefix
->entries
);
572 prefix
->state
= EIGRP_FSM_STATE_PASSIVE
;
573 prefix
->distance
= prefix
->rdistance
= ne
->distance
;
574 prefix
->reported_metric
= ne
->total_metric
;
575 prefix
->fdistance
= prefix
->fdistance
> prefix
->distance
578 if (prefix
->state
== EIGRP_FSM_STATE_ACTIVE_2
) {
579 struct list
*successors
= eigrp_topology_get_successor(prefix
);
581 assert(successors
); // Having a spoon and all you need is a
583 ne
= listnode_head(successors
);
584 eigrp_send_reply(ne
->adv_router
, prefix
);
586 list_delete(&successors
);
588 prefix
->req_action
|= EIGRP_FSM_NEED_UPDATE
;
589 listnode_add(eigrp
->topology_changes_internalIPV4
, prefix
);
590 eigrp_topology_update_node_flags(eigrp
, prefix
);
591 eigrp_update_routing_table(eigrp
, prefix
);
592 eigrp_update_topology_table_prefix(eigrp
, eigrp
->topology_table
,
598 int eigrp_fsm_event_lr_fcn(struct eigrp_fsm_action_message
*msg
)
600 struct eigrp
*eigrp
= msg
->eigrp
;
601 struct eigrp_prefix_entry
*prefix
= msg
->prefix
;
602 struct eigrp_nexthop_entry
*best_successor
;
603 struct list
*successors
= eigrp_topology_get_successor(prefix
);
605 assert(successors
); // Routing without a stack
607 prefix
->state
= prefix
->state
== EIGRP_FSM_STATE_ACTIVE_0
608 ? EIGRP_FSM_STATE_ACTIVE_1
609 : EIGRP_FSM_STATE_ACTIVE_3
;
611 best_successor
= listnode_head(successors
);
612 prefix
->rdistance
= prefix
->distance
= best_successor
->distance
;
613 prefix
->reported_metric
= best_successor
->total_metric
;
615 if (eigrp_nbr_count_get(eigrp
)) {
616 prefix
->req_action
|= EIGRP_FSM_NEED_QUERY
;
617 listnode_add(eigrp
->topology_changes_internalIPV4
, prefix
);
619 eigrp_fsm_event_lr(msg
); // in the case that there are no more
623 list_delete(&successors
);
628 int eigrp_fsm_event_qact(struct eigrp_fsm_action_message
*msg
)
630 struct list
*successors
= eigrp_topology_get_successor(msg
->prefix
);
631 struct eigrp_nexthop_entry
*ne
;
633 assert(successors
); // Cats and no Dogs
635 ne
= listnode_head(successors
);
636 msg
->prefix
->state
= EIGRP_FSM_STATE_ACTIVE_2
;
637 msg
->prefix
->distance
= ne
->distance
;
639 list_delete(&successors
);