1 // SPDX-License-Identifier: GPL-2.0-or-later
3 * EIGRPd Finite State Machine (DUAL).
4 * Copyright (C) 2013-2014
12 * This file contains functions for executing logic of finite state machine
17 * +=====================================+
21 * +=====================================+
23 * (3)| | (1)| | (1)| |
24 * | (0)| | (3)| | (2)|
25 * | | | | | +---------------+
27 * +--------+ | | | +-----------------+ \
32 * +===========+ (6) +===========+ +===========+ (6) +===========+
33 * | |------->| | (5) | |-------->| |
34 * | | (4) | |------>| | (4) | |
35 * | ACTIVE 0 |<-------| ACTIVE 1 | | ACTIVE 2 |<--------| ACTIVE 3
37 * +--| | +--| | +--| | +--| |
38 * | +===========+ | +===========+ | +===========+ |
40 * | ^ |(5) | ^ | ^ ^ | ^
41 * | | +---------|------|------------|----+ | | |
42 * +-------+ +------+ +---------+ +---------+
45 * 0- input event other than query from successor, FC not satisfied
46 * 1- last reply, FD is reset
47 * 2- query from successor, FC not satisfied
48 * 3- last reply, FC satisfied with current value of FDij
49 * 4- distance increase while in active state
50 * 5- query from successor while in active state
51 * 6- last reply, FC not satisfied with current value of FDij
52 * 7- state not changed, usually by receiving not last reply
65 #include "eigrpd/eigrp_types.h"
66 #include "eigrpd/eigrp_structs.h"
67 #include "eigrpd/eigrpd.h"
68 #include "eigrpd/eigrp_interface.h"
69 #include "eigrpd/eigrp_neighbor.h"
70 #include "eigrpd/eigrp_packet.h"
71 #include "eigrpd/eigrp_zebra.h"
72 #include "eigrpd/eigrp_vty.h"
73 #include "eigrpd/eigrp_network.h"
74 #include "eigrpd/eigrp_dump.h"
75 #include "eigrpd/eigrp_topology.h"
76 #include "eigrpd/eigrp_fsm.h"
77 #include "eigrpd/eigrp_metric.h"
82 int eigrp_fsm_event_keep_state(struct eigrp_fsm_action_message
*);
83 int eigrp_fsm_event_nq_fcn(struct eigrp_fsm_action_message
*);
84 int eigrp_fsm_event_q_fcn(struct eigrp_fsm_action_message
*);
85 int eigrp_fsm_event_lr(struct eigrp_fsm_action_message
*);
86 int eigrp_fsm_event_dinc(struct eigrp_fsm_action_message
*);
87 int eigrp_fsm_event_lr_fcs(struct eigrp_fsm_action_message
*);
88 int eigrp_fsm_event_lr_fcn(struct eigrp_fsm_action_message
*);
89 int eigrp_fsm_event_qact(struct eigrp_fsm_action_message
*);
91 //---------------------------------------------------------------------
94 * NSM - field of fields of struct containing one function each.
95 * Which function is used depends on actual state of FSM and occurred
96 * event(arrow in diagram). Usage:
97 * NSM[actual/starting state][occurred event].func
98 * Functions are should be executed within separate thread.
101 int (*func
)(struct eigrp_fsm_action_message
*);
102 } NSM
[EIGRP_FSM_STATE_MAX
][EIGRP_FSM_EVENT_MAX
] = {
105 {eigrp_fsm_event_nq_fcn
}, /* Event 0 */
106 {eigrp_fsm_event_keep_state
}, /* Event 1 */
107 {eigrp_fsm_event_q_fcn
}, /* Event 2 */
108 {eigrp_fsm_event_keep_state
}, /* Event 3 */
109 {eigrp_fsm_event_keep_state
}, /* Event 4 */
110 {eigrp_fsm_event_keep_state
}, /* Event 5 */
111 {eigrp_fsm_event_keep_state
}, /* Event 6 */
112 {eigrp_fsm_event_keep_state
}, /* Event 7 */
116 {eigrp_fsm_event_keep_state
}, /* Event 0 */
117 {eigrp_fsm_event_keep_state
}, /* Event 1 */
118 {eigrp_fsm_event_keep_state
}, /* Event 2 */
119 {eigrp_fsm_event_lr_fcs
}, /* Event 3 */
120 {eigrp_fsm_event_keep_state
}, /* Event 4 */
121 {eigrp_fsm_event_qact
}, /* Event 5 */
122 {eigrp_fsm_event_lr_fcn
}, /* Event 6 */
123 {eigrp_fsm_event_keep_state
}, /* Event 7 */
127 {eigrp_fsm_event_keep_state
}, /* Event 0 */
128 {eigrp_fsm_event_lr
}, /* Event 1 */
129 {eigrp_fsm_event_keep_state
}, /* Event 2 */
130 {eigrp_fsm_event_keep_state
}, /* Event 3 */
131 {eigrp_fsm_event_dinc
}, /* Event 4 */
132 {eigrp_fsm_event_qact
}, /* Event 5 */
133 {eigrp_fsm_event_keep_state
}, /* Event 6 */
134 {eigrp_fsm_event_keep_state
}, /* Event 7 */
138 {eigrp_fsm_event_keep_state
}, /* Event 0 */
139 {eigrp_fsm_event_keep_state
}, /* Event 1 */
140 {eigrp_fsm_event_keep_state
}, /* Event 2 */
141 {eigrp_fsm_event_lr_fcs
}, /* Event 3 */
142 {eigrp_fsm_event_keep_state
}, /* Event 4 */
143 {eigrp_fsm_event_keep_state
}, /* Event 5 */
144 {eigrp_fsm_event_lr_fcn
}, /* Event 6 */
145 {eigrp_fsm_event_keep_state
}, /* Event 7 */
149 {eigrp_fsm_event_keep_state
}, /* Event 0 */
150 {eigrp_fsm_event_lr
}, /* Event 1 */
151 {eigrp_fsm_event_keep_state
}, /* Event 2 */
152 {eigrp_fsm_event_keep_state
}, /* Event 3 */
153 {eigrp_fsm_event_dinc
}, /* Event 4 */
154 {eigrp_fsm_event_keep_state
}, /* Event 5 */
155 {eigrp_fsm_event_keep_state
}, /* Event 6 */
156 {eigrp_fsm_event_keep_state
}, /* Event 7 */
160 static const char *packet_type2str(uint8_t packet_type
)
162 if (packet_type
== EIGRP_OPC_UPDATE
)
164 if (packet_type
== EIGRP_OPC_REQUEST
)
166 if (packet_type
== EIGRP_OPC_QUERY
)
168 if (packet_type
== EIGRP_OPC_REPLY
)
170 if (packet_type
== EIGRP_OPC_HELLO
)
172 if (packet_type
== EIGRP_OPC_IPXSAP
)
174 if (packet_type
== EIGRP_OPC_ACK
)
176 if (packet_type
== EIGRP_OPC_SIAQUERY
)
178 if (packet_type
== EIGRP_OPC_SIAREPLY
)
184 static const char *prefix_state2str(enum eigrp_fsm_states state
)
187 case EIGRP_FSM_STATE_PASSIVE
:
189 case EIGRP_FSM_STATE_ACTIVE_0
:
190 return "Active oij0";
191 case EIGRP_FSM_STATE_ACTIVE_1
:
192 return "Active oij1";
193 case EIGRP_FSM_STATE_ACTIVE_2
:
194 return "Active oij2";
195 case EIGRP_FSM_STATE_ACTIVE_3
:
196 return "Active oij3";
202 static const char *fsm_state2str(enum eigrp_fsm_events event
)
205 case EIGRP_FSM_KEEP_STATE
:
206 return "Keep State Event";
207 case EIGRP_FSM_EVENT_NQ_FCN
:
208 return "Non Query Event Feasability not satisfied";
209 case EIGRP_FSM_EVENT_LR
:
210 return "Last Reply Event";
211 case EIGRP_FSM_EVENT_Q_FCN
:
212 return "Query Event Feasability not satisfied";
213 case EIGRP_FSM_EVENT_LR_FCS
:
214 return "Last Reply Event Feasability satisfied";
215 case EIGRP_FSM_EVENT_DINC
:
216 return "Distance Increase Event";
217 case EIGRP_FSM_EVENT_QACT
:
218 return "Query from Successor while in active state";
219 case EIGRP_FSM_EVENT_LR_FCN
:
220 return "Last Reply Event, Feasibility not satisfied";
226 static const char *change2str(enum metric_change change
)
229 case METRIC_DECREASE
:
233 case METRIC_INCREASE
:
240 * Main function in which are make decisions which event occurred.
241 * msg - argument of type struct eigrp_fsm_action_message contain
242 * details about what happen
244 * Return number of occurred event (arrow in diagram).
247 static enum eigrp_fsm_events
248 eigrp_get_fsm_event(struct eigrp_fsm_action_message
*msg
)
250 // Loading base information from message
251 // struct eigrp *eigrp = msg->eigrp;
252 struct eigrp_prefix_descriptor
*prefix
= msg
->prefix
;
253 struct eigrp_route_descriptor
*entry
= msg
->entry
;
254 uint8_t actual_state
= prefix
->state
;
255 enum metric_change change
;
258 entry
= eigrp_route_descriptor_new();
259 entry
->adv_router
= msg
->adv_router
;
260 entry
->ei
= msg
->adv_router
->ei
;
261 entry
->prefix
= prefix
;
266 * Calculate resultant metrics and insert to correct position
269 change
= eigrp_topology_update_distance(msg
);
271 /* Store for display later */
272 msg
->change
= change
;
274 switch (actual_state
) {
275 case EIGRP_FSM_STATE_PASSIVE
: {
276 struct eigrp_route_descriptor
*head
=
277 listnode_head(prefix
->entries
);
279 if (head
->reported_distance
< prefix
->fdistance
) {
280 return EIGRP_FSM_KEEP_STATE
;
283 * if best entry doesn't satisfy feasibility condition it means
284 * move to active state
285 * dependently if it was query from successor
287 if (msg
->packet_type
== EIGRP_OPC_QUERY
) {
288 return EIGRP_FSM_EVENT_Q_FCN
;
290 return EIGRP_FSM_EVENT_NQ_FCN
;
295 case EIGRP_FSM_STATE_ACTIVE_0
: {
296 if (msg
->packet_type
== EIGRP_OPC_REPLY
) {
297 struct eigrp_route_descriptor
*head
=
298 listnode_head(prefix
->entries
);
300 listnode_delete(prefix
->rij
, entry
->adv_router
);
301 if (prefix
->rij
->count
)
302 return EIGRP_FSM_KEEP_STATE
;
304 zlog_info("All reply received");
305 if (head
->reported_distance
< prefix
->fdistance
) {
306 return EIGRP_FSM_EVENT_LR_FCS
;
309 return EIGRP_FSM_EVENT_LR_FCN
;
310 } else if (msg
->packet_type
== EIGRP_OPC_QUERY
312 & EIGRP_ROUTE_DESCRIPTOR_SUCCESSOR_FLAG
)) {
313 return EIGRP_FSM_EVENT_QACT
;
316 return EIGRP_FSM_KEEP_STATE
;
320 case EIGRP_FSM_STATE_ACTIVE_1
: {
321 if (msg
->packet_type
== EIGRP_OPC_QUERY
322 && (entry
->flags
& EIGRP_ROUTE_DESCRIPTOR_SUCCESSOR_FLAG
)) {
323 return EIGRP_FSM_EVENT_QACT
;
324 } else if (msg
->packet_type
== EIGRP_OPC_REPLY
) {
325 listnode_delete(prefix
->rij
, entry
->adv_router
);
327 if (change
== METRIC_INCREASE
329 & EIGRP_ROUTE_DESCRIPTOR_SUCCESSOR_FLAG
)) {
330 return EIGRP_FSM_EVENT_DINC
;
331 } else if (prefix
->rij
->count
) {
332 return EIGRP_FSM_KEEP_STATE
;
334 zlog_info("All reply received");
335 return EIGRP_FSM_EVENT_LR
;
337 } else if (msg
->packet_type
== EIGRP_OPC_UPDATE
338 && change
== METRIC_INCREASE
340 & EIGRP_ROUTE_DESCRIPTOR_SUCCESSOR_FLAG
)) {
341 return EIGRP_FSM_EVENT_DINC
;
343 return EIGRP_FSM_KEEP_STATE
;
347 case EIGRP_FSM_STATE_ACTIVE_2
: {
348 if (msg
->packet_type
== EIGRP_OPC_REPLY
) {
349 struct eigrp_route_descriptor
*head
=
350 listnode_head(prefix
->entries
);
352 listnode_delete(prefix
->rij
, entry
->adv_router
);
353 if (prefix
->rij
->count
) {
354 return EIGRP_FSM_KEEP_STATE
;
356 zlog_info("All reply received");
357 if (head
->reported_distance
358 < prefix
->fdistance
) {
359 return EIGRP_FSM_EVENT_LR_FCS
;
362 return EIGRP_FSM_EVENT_LR_FCN
;
365 return EIGRP_FSM_KEEP_STATE
;
369 case EIGRP_FSM_STATE_ACTIVE_3
: {
370 if (msg
->packet_type
== EIGRP_OPC_REPLY
) {
371 listnode_delete(prefix
->rij
, entry
->adv_router
);
373 if (change
== METRIC_INCREASE
375 & EIGRP_ROUTE_DESCRIPTOR_SUCCESSOR_FLAG
)) {
376 return EIGRP_FSM_EVENT_DINC
;
377 } else if (prefix
->rij
->count
) {
378 return EIGRP_FSM_KEEP_STATE
;
380 zlog_info("All reply received");
381 return EIGRP_FSM_EVENT_LR
;
383 } else if (msg
->packet_type
== EIGRP_OPC_UPDATE
384 && change
== METRIC_INCREASE
386 & EIGRP_ROUTE_DESCRIPTOR_SUCCESSOR_FLAG
)) {
387 return EIGRP_FSM_EVENT_DINC
;
389 return EIGRP_FSM_KEEP_STATE
;
395 return EIGRP_FSM_KEEP_STATE
;
399 * Function made to execute in separate thread.
400 * Load argument from thread and execute proper NSM function
402 int eigrp_fsm_event(struct eigrp_fsm_action_message
*msg
)
404 enum eigrp_fsm_events event
= eigrp_get_fsm_event(msg
);
407 "EIGRP AS: %d State: %s Event: %s Network: %pI4 Packet Type: %s Reply RIJ Count: %d change: %s",
408 msg
->eigrp
->AS
, prefix_state2str(msg
->prefix
->state
),
409 fsm_state2str(event
), &msg
->prefix
->destination
->u
.prefix4
,
410 packet_type2str(msg
->packet_type
), msg
->prefix
->rij
->count
,
411 change2str(msg
->change
));
412 (*(NSM
[msg
->prefix
->state
][event
].func
))(msg
);
418 * Function of event 0.
421 int eigrp_fsm_event_nq_fcn(struct eigrp_fsm_action_message
*msg
)
423 struct eigrp
*eigrp
= msg
->eigrp
;
424 struct eigrp_prefix_descriptor
*prefix
= msg
->prefix
;
425 struct list
*successors
= eigrp_topology_get_successor(prefix
);
426 struct eigrp_route_descriptor
*ne
;
428 assert(successors
); // If this is NULL we have shit the bed, fun huh?
430 ne
= listnode_head(successors
);
431 prefix
->state
= EIGRP_FSM_STATE_ACTIVE_1
;
432 prefix
->rdistance
= prefix
->distance
= prefix
->fdistance
= ne
->distance
;
433 prefix
->reported_metric
= ne
->total_metric
;
435 if (eigrp_nbr_count_get(eigrp
)) {
436 prefix
->req_action
|= EIGRP_FSM_NEED_QUERY
;
437 listnode_add(eigrp
->topology_changes_internalIPV4
, prefix
);
439 eigrp_fsm_event_lr(msg
); // in the case that there are no more
443 list_delete(&successors
);
448 int eigrp_fsm_event_q_fcn(struct eigrp_fsm_action_message
*msg
)
450 struct eigrp
*eigrp
= msg
->eigrp
;
451 struct eigrp_prefix_descriptor
*prefix
= msg
->prefix
;
452 struct list
*successors
= eigrp_topology_get_successor(prefix
);
453 struct eigrp_route_descriptor
*ne
;
455 assert(successors
); // If this is NULL somebody poked us in the eye.
457 ne
= listnode_head(successors
);
458 prefix
->state
= EIGRP_FSM_STATE_ACTIVE_3
;
459 prefix
->rdistance
= prefix
->distance
= prefix
->fdistance
= ne
->distance
;
460 prefix
->reported_metric
= ne
->total_metric
;
461 if (eigrp_nbr_count_get(eigrp
)) {
462 prefix
->req_action
|= EIGRP_FSM_NEED_QUERY
;
463 listnode_add(eigrp
->topology_changes_internalIPV4
, prefix
);
465 eigrp_fsm_event_lr(msg
); // in the case that there are no more
469 list_delete(&successors
);
474 int eigrp_fsm_event_keep_state(struct eigrp_fsm_action_message
*msg
)
476 struct eigrp
*eigrp
= msg
->eigrp
;
477 struct eigrp_prefix_descriptor
*prefix
= msg
->prefix
;
478 struct eigrp_route_descriptor
*ne
= listnode_head(prefix
->entries
);
480 if (prefix
->state
== EIGRP_FSM_STATE_PASSIVE
) {
481 if (!eigrp_metrics_is_same(prefix
->reported_metric
,
483 prefix
->rdistance
= prefix
->fdistance
=
484 prefix
->distance
= ne
->distance
;
485 prefix
->reported_metric
= ne
->total_metric
;
486 if (msg
->packet_type
== EIGRP_OPC_QUERY
)
487 eigrp_send_reply(msg
->adv_router
, prefix
);
488 prefix
->req_action
|= EIGRP_FSM_NEED_UPDATE
;
489 listnode_add(eigrp
->topology_changes_internalIPV4
,
492 eigrp_topology_update_node_flags(eigrp
, prefix
);
493 eigrp_update_routing_table(eigrp
, prefix
);
496 if (msg
->packet_type
== EIGRP_OPC_QUERY
)
497 eigrp_send_reply(msg
->adv_router
, prefix
);
502 int eigrp_fsm_event_lr(struct eigrp_fsm_action_message
*msg
)
504 struct eigrp
*eigrp
= msg
->eigrp
;
505 struct eigrp_prefix_descriptor
*prefix
= msg
->prefix
;
506 struct eigrp_route_descriptor
*ne
= listnode_head(prefix
->entries
);
508 prefix
->fdistance
= prefix
->distance
= prefix
->rdistance
= ne
->distance
;
509 prefix
->reported_metric
= ne
->total_metric
;
511 if (prefix
->state
== EIGRP_FSM_STATE_ACTIVE_3
) {
512 struct list
*successors
= eigrp_topology_get_successor(prefix
);
514 assert(successors
); // It's like Napolean and Waterloo
516 ne
= listnode_head(successors
);
517 eigrp_send_reply(ne
->adv_router
, prefix
);
518 list_delete(&successors
);
521 prefix
->state
= EIGRP_FSM_STATE_PASSIVE
;
522 prefix
->req_action
|= EIGRP_FSM_NEED_UPDATE
;
523 listnode_add(eigrp
->topology_changes_internalIPV4
, prefix
);
524 eigrp_topology_update_node_flags(eigrp
, prefix
);
525 eigrp_update_routing_table(eigrp
, prefix
);
526 eigrp_update_topology_table_prefix(eigrp
, eigrp
->topology_table
,
532 int eigrp_fsm_event_dinc(struct eigrp_fsm_action_message
*msg
)
534 struct list
*successors
= eigrp_topology_get_successor(msg
->prefix
);
535 struct eigrp_route_descriptor
*ne
;
537 assert(successors
); // Trump and his big hands
539 ne
= listnode_head(successors
);
540 msg
->prefix
->state
= msg
->prefix
->state
== EIGRP_FSM_STATE_ACTIVE_1
541 ? EIGRP_FSM_STATE_ACTIVE_0
542 : EIGRP_FSM_STATE_ACTIVE_2
;
543 msg
->prefix
->distance
= ne
->distance
;
544 if (!msg
->prefix
->rij
->count
)
545 (*(NSM
[msg
->prefix
->state
][eigrp_get_fsm_event(msg
)].func
))(
549 list_delete(&successors
);
553 int eigrp_fsm_event_lr_fcs(struct eigrp_fsm_action_message
*msg
)
555 struct eigrp
*eigrp
= msg
->eigrp
;
556 struct eigrp_prefix_descriptor
*prefix
= msg
->prefix
;
557 struct eigrp_route_descriptor
*ne
= listnode_head(prefix
->entries
);
559 prefix
->state
= EIGRP_FSM_STATE_PASSIVE
;
560 prefix
->distance
= prefix
->rdistance
= ne
->distance
;
561 prefix
->reported_metric
= ne
->total_metric
;
562 prefix
->fdistance
= prefix
->fdistance
> prefix
->distance
565 if (prefix
->state
== EIGRP_FSM_STATE_ACTIVE_2
) {
566 struct list
*successors
= eigrp_topology_get_successor(prefix
);
568 assert(successors
); // Having a spoon and all you need is a
570 ne
= listnode_head(successors
);
571 eigrp_send_reply(ne
->adv_router
, prefix
);
573 list_delete(&successors
);
575 prefix
->req_action
|= EIGRP_FSM_NEED_UPDATE
;
576 listnode_add(eigrp
->topology_changes_internalIPV4
, prefix
);
577 eigrp_topology_update_node_flags(eigrp
, prefix
);
578 eigrp_update_routing_table(eigrp
, prefix
);
579 eigrp_update_topology_table_prefix(eigrp
, eigrp
->topology_table
,
585 int eigrp_fsm_event_lr_fcn(struct eigrp_fsm_action_message
*msg
)
587 struct eigrp
*eigrp
= msg
->eigrp
;
588 struct eigrp_prefix_descriptor
*prefix
= msg
->prefix
;
589 struct eigrp_route_descriptor
*best_successor
;
590 struct list
*successors
= eigrp_topology_get_successor(prefix
);
592 assert(successors
); // Routing without a stack
594 prefix
->state
= prefix
->state
== EIGRP_FSM_STATE_ACTIVE_0
595 ? EIGRP_FSM_STATE_ACTIVE_1
596 : EIGRP_FSM_STATE_ACTIVE_3
;
598 best_successor
= listnode_head(successors
);
599 prefix
->rdistance
= prefix
->distance
= best_successor
->distance
;
600 prefix
->reported_metric
= best_successor
->total_metric
;
602 if (eigrp_nbr_count_get(eigrp
)) {
603 prefix
->req_action
|= EIGRP_FSM_NEED_QUERY
;
604 listnode_add(eigrp
->topology_changes_internalIPV4
, prefix
);
606 eigrp_fsm_event_lr(msg
); // in the case that there are no more
610 list_delete(&successors
);
615 int eigrp_fsm_event_qact(struct eigrp_fsm_action_message
*msg
)
617 struct list
*successors
= eigrp_topology_get_successor(msg
->prefix
);
618 struct eigrp_route_descriptor
*ne
;
620 assert(successors
); // Cats and no Dogs
622 ne
= listnode_head(successors
);
623 msg
->prefix
->state
= EIGRP_FSM_STATE_ACTIVE_2
;
624 msg
->prefix
->distance
= ne
->distance
;
626 list_delete(&successors
);