diff options
Diffstat (limited to '')
-rw-r--r-- | eigrpd/eigrp_fsm.c | 643 |
1 files changed, 643 insertions, 0 deletions
diff --git a/eigrpd/eigrp_fsm.c b/eigrpd/eigrp_fsm.c new file mode 100644 index 0000000..d2d435b --- /dev/null +++ b/eigrpd/eigrp_fsm.c @@ -0,0 +1,643 @@ +/* + * EIGRPd Finite State Machine (DUAL). + * Copyright (C) 2013-2014 + * Authors: + * Donnie Savage + * Jan Janovic + * Matej Perina + * Peter Orsag + * Peter Paluch + * + * This file is part of GNU Zebra. + * + * GNU Zebra is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the + * Free Software Foundation; either version 2, or (at your option) any + * later version. + * + * GNU Zebra is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; see the file COPYING; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + * + * This file contains functions for executing logic of finite state machine + * + * +------------ + + * | (7) | + * | v + * +=====================================+ + * | | + * | Passive | + * | | + * +=====================================+ + * ^ | ^ ^ ^ | + * (3)| | (1)| | (1)| | + * | (0)| | (3)| | (2)| + * | | | | | +---------------+ + * | | | | | \ + * +--------+ | | | +-----------------+ \ + * / / / | \ \ + * / / / +----+ \ \ + * | | | | | | + * | v | | | v + * +===========+ (6) +===========+ +===========+ (6) +===========+ + * | |------->| | (5) | |-------->| | + * | | (4) | |------>| | (4) | | + * | ACTIVE 0 |<-------| ACTIVE 1 | | ACTIVE 2 |<--------| ACTIVE 3 + * | + * +--| | +--| | +--| | +--| | + * | +===========+ | +===========+ | +===========+ | + * +===========+ + * | ^ |(5) | ^ | ^ ^ | ^ + * | | +---------|------|------------|----+ | | | + * +-------+ +------+ +---------+ +---------+ + * (7) (7) (7) (7) + * + * 0- input event other than query from successor, FC not satisfied + * 1- last reply, FD is reset + * 2- query from successor, FC not satisfied + * 3- last reply, FC satisfied with current value of FDij + * 4- distance increase while in active state + * 5- query from successor while in active state + * 6- last reply, FC not satisfied with current value of FDij + * 7- state not changed, usually by receiving not last reply + */ + +#include <zebra.h> +#include <thread.h> + +#include "prefix.h" +#include "table.h" +#include "memory.h" +#include "log.h" +#include "linklist.h" +#include "vty.h" + +#include "eigrpd/eigrp_types.h" +#include "eigrpd/eigrp_structs.h" +#include "eigrpd/eigrpd.h" +#include "eigrpd/eigrp_interface.h" +#include "eigrpd/eigrp_neighbor.h" +#include "eigrpd/eigrp_packet.h" +#include "eigrpd/eigrp_zebra.h" +#include "eigrpd/eigrp_vty.h" +#include "eigrpd/eigrp_network.h" +#include "eigrpd/eigrp_dump.h" +#include "eigrpd/eigrp_topology.h" +#include "eigrpd/eigrp_fsm.h" +#include "eigrpd/eigrp_metric.h" + +/* + * Prototypes + */ +int eigrp_fsm_event_keep_state(struct eigrp_fsm_action_message *); +int eigrp_fsm_event_nq_fcn(struct eigrp_fsm_action_message *); +int eigrp_fsm_event_q_fcn(struct eigrp_fsm_action_message *); +int eigrp_fsm_event_lr(struct eigrp_fsm_action_message *); +int eigrp_fsm_event_dinc(struct eigrp_fsm_action_message *); +int eigrp_fsm_event_lr_fcs(struct eigrp_fsm_action_message *); +int eigrp_fsm_event_lr_fcn(struct eigrp_fsm_action_message *); +int eigrp_fsm_event_qact(struct eigrp_fsm_action_message *); + +//--------------------------------------------------------------------- + +/* + * NSM - field of fields of struct containing one function each. + * Which function is used depends on actual state of FSM and occurred + * event(arrow in diagram). Usage: + * NSM[actual/starting state][occurred event].func + * Functions are should be executed within separate thread. + */ +const struct { + int (*func)(struct eigrp_fsm_action_message *); +} NSM[EIGRP_FSM_STATE_MAX][EIGRP_FSM_EVENT_MAX] = { + { + // PASSIVE STATE + {eigrp_fsm_event_nq_fcn}, /* Event 0 */ + {eigrp_fsm_event_keep_state}, /* Event 1 */ + {eigrp_fsm_event_q_fcn}, /* Event 2 */ + {eigrp_fsm_event_keep_state}, /* Event 3 */ + {eigrp_fsm_event_keep_state}, /* Event 4 */ + {eigrp_fsm_event_keep_state}, /* Event 5 */ + {eigrp_fsm_event_keep_state}, /* Event 6 */ + {eigrp_fsm_event_keep_state}, /* Event 7 */ + }, + { + // Active 0 state + {eigrp_fsm_event_keep_state}, /* Event 0 */ + {eigrp_fsm_event_keep_state}, /* Event 1 */ + {eigrp_fsm_event_keep_state}, /* Event 2 */ + {eigrp_fsm_event_lr_fcs}, /* Event 3 */ + {eigrp_fsm_event_keep_state}, /* Event 4 */ + {eigrp_fsm_event_qact}, /* Event 5 */ + {eigrp_fsm_event_lr_fcn}, /* Event 6 */ + {eigrp_fsm_event_keep_state}, /* Event 7 */ + }, + { + // Active 1 state + {eigrp_fsm_event_keep_state}, /* Event 0 */ + {eigrp_fsm_event_lr}, /* Event 1 */ + {eigrp_fsm_event_keep_state}, /* Event 2 */ + {eigrp_fsm_event_keep_state}, /* Event 3 */ + {eigrp_fsm_event_dinc}, /* Event 4 */ + {eigrp_fsm_event_qact}, /* Event 5 */ + {eigrp_fsm_event_keep_state}, /* Event 6 */ + {eigrp_fsm_event_keep_state}, /* Event 7 */ + }, + { + // Active 2 state + {eigrp_fsm_event_keep_state}, /* Event 0 */ + {eigrp_fsm_event_keep_state}, /* Event 1 */ + {eigrp_fsm_event_keep_state}, /* Event 2 */ + {eigrp_fsm_event_lr_fcs}, /* Event 3 */ + {eigrp_fsm_event_keep_state}, /* Event 4 */ + {eigrp_fsm_event_keep_state}, /* Event 5 */ + {eigrp_fsm_event_lr_fcn}, /* Event 6 */ + {eigrp_fsm_event_keep_state}, /* Event 7 */ + }, + { + // Active 3 state + {eigrp_fsm_event_keep_state}, /* Event 0 */ + {eigrp_fsm_event_lr}, /* Event 1 */ + {eigrp_fsm_event_keep_state}, /* Event 2 */ + {eigrp_fsm_event_keep_state}, /* Event 3 */ + {eigrp_fsm_event_dinc}, /* Event 4 */ + {eigrp_fsm_event_keep_state}, /* Event 5 */ + {eigrp_fsm_event_keep_state}, /* Event 6 */ + {eigrp_fsm_event_keep_state}, /* Event 7 */ + }, +}; + +static const char *packet_type2str(uint8_t packet_type) +{ + if (packet_type == EIGRP_OPC_UPDATE) + return "Update"; + if (packet_type == EIGRP_OPC_REQUEST) + return "Request"; + if (packet_type == EIGRP_OPC_QUERY) + return "Query"; + if (packet_type == EIGRP_OPC_REPLY) + return "Reply"; + if (packet_type == EIGRP_OPC_HELLO) + return "Hello"; + if (packet_type == EIGRP_OPC_IPXSAP) + return "IPXSAP"; + if (packet_type == EIGRP_OPC_ACK) + return "Ack"; + if (packet_type == EIGRP_OPC_SIAQUERY) + return "SIA Query"; + if (packet_type == EIGRP_OPC_SIAREPLY) + return "SIA Reply"; + + return "Unknown"; +} + +static const char *prefix_state2str(enum eigrp_fsm_states state) +{ + switch (state) { + case EIGRP_FSM_STATE_PASSIVE: + return "Passive"; + case EIGRP_FSM_STATE_ACTIVE_0: + return "Active oij0"; + case EIGRP_FSM_STATE_ACTIVE_1: + return "Active oij1"; + case EIGRP_FSM_STATE_ACTIVE_2: + return "Active oij2"; + case EIGRP_FSM_STATE_ACTIVE_3: + return "Active oij3"; + } + + return "Unknown"; +} + +static const char *fsm_state2str(enum eigrp_fsm_events event) +{ + switch (event) { + case EIGRP_FSM_KEEP_STATE: + return "Keep State Event"; + case EIGRP_FSM_EVENT_NQ_FCN: + return "Non Query Event Feasability not satisfied"; + case EIGRP_FSM_EVENT_LR: + return "Last Reply Event"; + case EIGRP_FSM_EVENT_Q_FCN: + return "Query Event Feasability not satisfied"; + case EIGRP_FSM_EVENT_LR_FCS: + return "Last Reply Event Feasability satisfied"; + case EIGRP_FSM_EVENT_DINC: + return "Distance Increase Event"; + case EIGRP_FSM_EVENT_QACT: + return "Query from Successor while in active state"; + case EIGRP_FSM_EVENT_LR_FCN: + return "Last Reply Event, Feasibility not satisfied"; + } + + return "Unknown"; +} + +static const char *change2str(enum metric_change change) +{ + switch (change) { + case METRIC_DECREASE: + return "Decrease"; + case METRIC_SAME: + return "Same"; + case METRIC_INCREASE: + return "Increase"; + } + + return "Unknown"; +} +/* + * Main function in which are make decisions which event occurred. + * msg - argument of type struct eigrp_fsm_action_message contain + * details about what happen + * + * Return number of occurred event (arrow in diagram). + * + */ +static enum eigrp_fsm_events +eigrp_get_fsm_event(struct eigrp_fsm_action_message *msg) +{ + // Loading base information from message + // struct eigrp *eigrp = msg->eigrp; + struct eigrp_prefix_descriptor *prefix = msg->prefix; + struct eigrp_route_descriptor *entry = msg->entry; + uint8_t actual_state = prefix->state; + enum metric_change change; + + if (entry == NULL) { + entry = eigrp_route_descriptor_new(); + entry->adv_router = msg->adv_router; + entry->ei = msg->adv_router->ei; + entry->prefix = prefix; + msg->entry = entry; + } + + /* + * Calculate resultant metrics and insert to correct position + * in entries list + */ + change = eigrp_topology_update_distance(msg); + + /* Store for display later */ + msg->change = change; + + switch (actual_state) { + case EIGRP_FSM_STATE_PASSIVE: { + struct eigrp_route_descriptor *head = + listnode_head(prefix->entries); + + if (head->reported_distance < prefix->fdistance) { + return EIGRP_FSM_KEEP_STATE; + } + /* + * if best entry doesn't satisfy feasibility condition it means + * move to active state + * dependently if it was query from successor + */ + if (msg->packet_type == EIGRP_OPC_QUERY) { + return EIGRP_FSM_EVENT_Q_FCN; + } else { + return EIGRP_FSM_EVENT_NQ_FCN; + } + + break; + } + case EIGRP_FSM_STATE_ACTIVE_0: { + if (msg->packet_type == EIGRP_OPC_REPLY) { + struct eigrp_route_descriptor *head = + listnode_head(prefix->entries); + + listnode_delete(prefix->rij, entry->adv_router); + if (prefix->rij->count) + return EIGRP_FSM_KEEP_STATE; + + zlog_info("All reply received"); + if (head->reported_distance < prefix->fdistance) { + return EIGRP_FSM_EVENT_LR_FCS; + } + + return EIGRP_FSM_EVENT_LR_FCN; + } else if (msg->packet_type == EIGRP_OPC_QUERY + && (entry->flags + & EIGRP_ROUTE_DESCRIPTOR_SUCCESSOR_FLAG)) { + return EIGRP_FSM_EVENT_QACT; + } + + return EIGRP_FSM_KEEP_STATE; + + break; + } + case EIGRP_FSM_STATE_ACTIVE_1: { + if (msg->packet_type == EIGRP_OPC_QUERY + && (entry->flags & EIGRP_ROUTE_DESCRIPTOR_SUCCESSOR_FLAG)) { + return EIGRP_FSM_EVENT_QACT; + } else if (msg->packet_type == EIGRP_OPC_REPLY) { + listnode_delete(prefix->rij, entry->adv_router); + + if (change == METRIC_INCREASE + && (entry->flags + & EIGRP_ROUTE_DESCRIPTOR_SUCCESSOR_FLAG)) { + return EIGRP_FSM_EVENT_DINC; + } else if (prefix->rij->count) { + return EIGRP_FSM_KEEP_STATE; + } else { + zlog_info("All reply received"); + return EIGRP_FSM_EVENT_LR; + } + } else if (msg->packet_type == EIGRP_OPC_UPDATE + && change == METRIC_INCREASE + && (entry->flags + & EIGRP_ROUTE_DESCRIPTOR_SUCCESSOR_FLAG)) { + return EIGRP_FSM_EVENT_DINC; + } + return EIGRP_FSM_KEEP_STATE; + + break; + } + case EIGRP_FSM_STATE_ACTIVE_2: { + if (msg->packet_type == EIGRP_OPC_REPLY) { + struct eigrp_route_descriptor *head = + listnode_head(prefix->entries); + + listnode_delete(prefix->rij, entry->adv_router); + if (prefix->rij->count) { + return EIGRP_FSM_KEEP_STATE; + } else { + zlog_info("All reply received"); + if (head->reported_distance + < prefix->fdistance) { + return EIGRP_FSM_EVENT_LR_FCS; + } + + return EIGRP_FSM_EVENT_LR_FCN; + } + } + return EIGRP_FSM_KEEP_STATE; + + break; + } + case EIGRP_FSM_STATE_ACTIVE_3: { + if (msg->packet_type == EIGRP_OPC_REPLY) { + listnode_delete(prefix->rij, entry->adv_router); + + if (change == METRIC_INCREASE + && (entry->flags + & EIGRP_ROUTE_DESCRIPTOR_SUCCESSOR_FLAG)) { + return EIGRP_FSM_EVENT_DINC; + } else if (prefix->rij->count) { + return EIGRP_FSM_KEEP_STATE; + } else { + zlog_info("All reply received"); + return EIGRP_FSM_EVENT_LR; + } + } else if (msg->packet_type == EIGRP_OPC_UPDATE + && change == METRIC_INCREASE + && (entry->flags + & EIGRP_ROUTE_DESCRIPTOR_SUCCESSOR_FLAG)) { + return EIGRP_FSM_EVENT_DINC; + } + return EIGRP_FSM_KEEP_STATE; + + break; + } + } + + return EIGRP_FSM_KEEP_STATE; +} + +/* + * Function made to execute in separate thread. + * Load argument from thread and execute proper NSM function + */ +int eigrp_fsm_event(struct eigrp_fsm_action_message *msg) +{ + enum eigrp_fsm_events event = eigrp_get_fsm_event(msg); + + zlog_info( + "EIGRP AS: %d State: %s Event: %s Network: %pI4 Packet Type: %s Reply RIJ Count: %d change: %s", + msg->eigrp->AS, prefix_state2str(msg->prefix->state), + fsm_state2str(event), &msg->prefix->destination->u.prefix4, + packet_type2str(msg->packet_type), msg->prefix->rij->count, + change2str(msg->change)); + (*(NSM[msg->prefix->state][event].func))(msg); + + return 1; +} + +/* + * Function of event 0. + * + */ +int eigrp_fsm_event_nq_fcn(struct eigrp_fsm_action_message *msg) +{ + struct eigrp *eigrp = msg->eigrp; + struct eigrp_prefix_descriptor *prefix = msg->prefix; + struct list *successors = eigrp_topology_get_successor(prefix); + struct eigrp_route_descriptor *ne; + + assert(successors); // If this is NULL we have shit the bed, fun huh? + + ne = listnode_head(successors); + prefix->state = EIGRP_FSM_STATE_ACTIVE_1; + prefix->rdistance = prefix->distance = prefix->fdistance = ne->distance; + prefix->reported_metric = ne->total_metric; + + if (eigrp_nbr_count_get(eigrp)) { + prefix->req_action |= EIGRP_FSM_NEED_QUERY; + listnode_add(eigrp->topology_changes_internalIPV4, prefix); + } else { + eigrp_fsm_event_lr(msg); // in the case that there are no more + // neighbors left + } + + list_delete(&successors); + + return 1; +} + +int eigrp_fsm_event_q_fcn(struct eigrp_fsm_action_message *msg) +{ + struct eigrp *eigrp = msg->eigrp; + struct eigrp_prefix_descriptor *prefix = msg->prefix; + struct list *successors = eigrp_topology_get_successor(prefix); + struct eigrp_route_descriptor *ne; + + assert(successors); // If this is NULL somebody poked us in the eye. + + ne = listnode_head(successors); + prefix->state = EIGRP_FSM_STATE_ACTIVE_3; + prefix->rdistance = prefix->distance = prefix->fdistance = ne->distance; + prefix->reported_metric = ne->total_metric; + if (eigrp_nbr_count_get(eigrp)) { + prefix->req_action |= EIGRP_FSM_NEED_QUERY; + listnode_add(eigrp->topology_changes_internalIPV4, prefix); + } else { + eigrp_fsm_event_lr(msg); // in the case that there are no more + // neighbors left + } + + list_delete(&successors); + + return 1; +} + +int eigrp_fsm_event_keep_state(struct eigrp_fsm_action_message *msg) +{ + struct eigrp *eigrp = msg->eigrp; + struct eigrp_prefix_descriptor *prefix = msg->prefix; + struct eigrp_route_descriptor *ne = listnode_head(prefix->entries); + + if (prefix->state == EIGRP_FSM_STATE_PASSIVE) { + if (!eigrp_metrics_is_same(prefix->reported_metric, + ne->total_metric)) { + prefix->rdistance = prefix->fdistance = + prefix->distance = ne->distance; + prefix->reported_metric = ne->total_metric; + if (msg->packet_type == EIGRP_OPC_QUERY) + eigrp_send_reply(msg->adv_router, prefix); + prefix->req_action |= EIGRP_FSM_NEED_UPDATE; + listnode_add(eigrp->topology_changes_internalIPV4, + prefix); + } + eigrp_topology_update_node_flags(eigrp, prefix); + eigrp_update_routing_table(eigrp, prefix); + } + + if (msg->packet_type == EIGRP_OPC_QUERY) + eigrp_send_reply(msg->adv_router, prefix); + + return 1; +} + +int eigrp_fsm_event_lr(struct eigrp_fsm_action_message *msg) +{ + struct eigrp *eigrp = msg->eigrp; + struct eigrp_prefix_descriptor *prefix = msg->prefix; + struct eigrp_route_descriptor *ne = listnode_head(prefix->entries); + + prefix->fdistance = prefix->distance = prefix->rdistance = ne->distance; + prefix->reported_metric = ne->total_metric; + + if (prefix->state == EIGRP_FSM_STATE_ACTIVE_3) { + struct list *successors = eigrp_topology_get_successor(prefix); + + assert(successors); // It's like Napolean and Waterloo + + ne = listnode_head(successors); + eigrp_send_reply(ne->adv_router, prefix); + list_delete(&successors); + } + + prefix->state = EIGRP_FSM_STATE_PASSIVE; + prefix->req_action |= EIGRP_FSM_NEED_UPDATE; + listnode_add(eigrp->topology_changes_internalIPV4, prefix); + eigrp_topology_update_node_flags(eigrp, prefix); + eigrp_update_routing_table(eigrp, prefix); + eigrp_update_topology_table_prefix(eigrp, eigrp->topology_table, + prefix); + + return 1; +} + +int eigrp_fsm_event_dinc(struct eigrp_fsm_action_message *msg) +{ + struct list *successors = eigrp_topology_get_successor(msg->prefix); + struct eigrp_route_descriptor *ne; + + assert(successors); // Trump and his big hands + + ne = listnode_head(successors); + msg->prefix->state = msg->prefix->state == EIGRP_FSM_STATE_ACTIVE_1 + ? EIGRP_FSM_STATE_ACTIVE_0 + : EIGRP_FSM_STATE_ACTIVE_2; + msg->prefix->distance = ne->distance; + if (!msg->prefix->rij->count) + (*(NSM[msg->prefix->state][eigrp_get_fsm_event(msg)].func))( + msg); + + + list_delete(&successors); + return 1; +} + +int eigrp_fsm_event_lr_fcs(struct eigrp_fsm_action_message *msg) +{ + struct eigrp *eigrp = msg->eigrp; + struct eigrp_prefix_descriptor *prefix = msg->prefix; + struct eigrp_route_descriptor *ne = listnode_head(prefix->entries); + + prefix->state = EIGRP_FSM_STATE_PASSIVE; + prefix->distance = prefix->rdistance = ne->distance; + prefix->reported_metric = ne->total_metric; + prefix->fdistance = prefix->fdistance > prefix->distance + ? prefix->distance + : prefix->fdistance; + if (prefix->state == EIGRP_FSM_STATE_ACTIVE_2) { + struct list *successors = eigrp_topology_get_successor(prefix); + + assert(successors); // Having a spoon and all you need is a + // knife + ne = listnode_head(successors); + eigrp_send_reply(ne->adv_router, prefix); + + list_delete(&successors); + } + prefix->req_action |= EIGRP_FSM_NEED_UPDATE; + listnode_add(eigrp->topology_changes_internalIPV4, prefix); + eigrp_topology_update_node_flags(eigrp, prefix); + eigrp_update_routing_table(eigrp, prefix); + eigrp_update_topology_table_prefix(eigrp, eigrp->topology_table, + prefix); + + return 1; +} + +int eigrp_fsm_event_lr_fcn(struct eigrp_fsm_action_message *msg) +{ + struct eigrp *eigrp = msg->eigrp; + struct eigrp_prefix_descriptor *prefix = msg->prefix; + struct eigrp_route_descriptor *best_successor; + struct list *successors = eigrp_topology_get_successor(prefix); + + assert(successors); // Routing without a stack + + prefix->state = prefix->state == EIGRP_FSM_STATE_ACTIVE_0 + ? EIGRP_FSM_STATE_ACTIVE_1 + : EIGRP_FSM_STATE_ACTIVE_3; + + best_successor = listnode_head(successors); + prefix->rdistance = prefix->distance = best_successor->distance; + prefix->reported_metric = best_successor->total_metric; + + if (eigrp_nbr_count_get(eigrp)) { + prefix->req_action |= EIGRP_FSM_NEED_QUERY; + listnode_add(eigrp->topology_changes_internalIPV4, prefix); + } else { + eigrp_fsm_event_lr(msg); // in the case that there are no more + // neighbors left + } + + list_delete(&successors); + + return 1; +} + +int eigrp_fsm_event_qact(struct eigrp_fsm_action_message *msg) +{ + struct list *successors = eigrp_topology_get_successor(msg->prefix); + struct eigrp_route_descriptor *ne; + + assert(successors); // Cats and no Dogs + + ne = listnode_head(successors); + msg->prefix->state = EIGRP_FSM_STATE_ACTIVE_2; + msg->prefix->distance = ne->distance; + + list_delete(&successors); + return 1; +} |