eigrpd/eigrp_fsm.c

   1 /*
   2  * EIGRPd Finite State Machine (DUAL).
   3  * Copyright (C) 2013-2014
   4  * Authors:
   5  *   Donnie Savage
   6  *   Jan Janovic
   7  *   Matej Perina
   8  *   Peter Orsag
   9  *   Peter Paluch
  10  *
  11  * This file is part of GNU Zebra.
  12  *
  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
  16  * later version.
  17  *
  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.
  22  *
  23  * You should have received a copy of the GNU General Public License
  24  * along with GNU Zebra; see the file COPYING.  If not, write to the
  25  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  26  * Boston, MA 02111-1307, USA.
  27  *
  28  *
  29  * This file contains functions for executing logic of finite state machine
  30  *
  31  *                                +------------ +
  32  *                                |     (7)     |
  33  *                                |             v
  34  *                    +=====================================+
  35  *                    |                                     |
  36  *                    |              Passive                |
  37  *                    |                                     |
  38  *                    +=====================================+
  39  *                        ^     |     ^     ^     ^    |
  40  *                     (3)|     |  (1)|     |  (1)|    |
  41  *                        |  (0)|     |  (3)|     | (2)|
  42  *                        |     |     |     |     |    +---------------+
  43  *                        |     |     |     |     |                     \
  44  *              +--------+      |     |     |     +-----------------+    \
  45  *            /                /     /      |                        \    \
  46  *          /                /     /        +----+                    \    \
  47  *         |                |     |               |                    |    |
  48  *         |                v     |               |                    |    v
  49  *    +===========+   (6)  +===========+       +===========+   (6)   +===========+
  50  *    |           |------->|           |  (5)  |           |-------->|           |
  51  *    |           |   (4)  |           |------>|           |   (4)   |           |
  52  *    | ACTIVE 0  |<-------| ACTIVE 1  |       | ACTIVE 2  |<--------| ACTIVE 3  |
  53  * +--|           |     +--|           |    +--|           |      +--|           |
  54  * |  +===========+     |  +===========+    |  +===========+      |  +===========+
  55  * |       ^  |(5)      |      ^            |    ^    ^           |         ^
  56  * |       |  +---------|------|------------|----+    |           |         |
  57  * +-------+            +------+            +---------+           +---------+
  58  *    (7)                 (7)                  (7)                   (7)
  59  *
  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
  68  *
  69  */
  70
  71 #include <thread.h>
  72 #include <zebra.h>
  73
  74 #include "prefix.h"
  75 #include "table.h"
  76 #include "memory.h"
  77 #include "log.h"
  78 #include "linklist.h"
  79 #include "vty.h"
  80
  81 #include "eigrpd/eigrp_structs.h"
  82 #include "eigrpd/eigrpd.h"
  83 #include "eigrpd/eigrp_interface.h"
  84 #include "eigrpd/eigrp_neighbor.h"
  85 #include "eigrpd/eigrp_packet.h"
  86 #include "eigrpd/eigrp_zebra.h"
  87 #include "eigrpd/eigrp_vty.h"
  88 #include "eigrpd/eigrp_network.h"
  89 #include "eigrpd/eigrp_dump.h"
  90 #include "eigrpd/eigrp_topology.h"
  91 #include "eigrpd/eigrp_fsm.h"
  92
  93 /*
  94  * Prototypes
  95  */
  96 int
  97 eigrp_fsm_event_keep_state(struct eigrp_fsm_action_message *);
  98 int
  99 eigrp_fsm_event_nq_fcn(struct eigrp_fsm_action_message *);
 100 int
 101 eigrp_fsm_event_q_fcn(struct eigrp_fsm_action_message *);
 102 int
 103 eigrp_fsm_event_lr(struct eigrp_fsm_action_message *);
 104 int
 105 eigrp_fsm_event_dinc(struct eigrp_fsm_action_message *);
 106 int
 107 eigrp_fsm_event_lr_fcs(struct eigrp_fsm_action_message *);
 108 int
 109 eigrp_fsm_event_lr_fcn(struct eigrp_fsm_action_message *);
 110 int
 111 eigrp_fsm_event_qact(struct eigrp_fsm_action_message *);
 112
 113 //---------------------------------------------------------------------
 114
 115 /*
 116  * NSM - field of fields of struct containing one function each.
 117  * Which function is used depends on actual state of FSM and occurred
 118  * event(arrow in diagram). Usage:
 119  * NSM[actual/starting state][occurred event].func
 120  * Functions are should be executed within separate thread.
 121  */
 122 struct {
 123         int
 124         (*func)(struct eigrp_fsm_action_message *);
 125 } NSM[EIGRP_FSM_STATE_MAX][EIGRP_FSM_EVENT_MAX] = { {
 126 //PASSIVE STATE
 127                 { eigrp_fsm_event_nq_fcn }, /* Event 0 */
 128                 { eigrp_fsm_event_keep_state }, /* Event 1 */
 129                 { eigrp_fsm_event_q_fcn }, /* Event 2 */
 130                 { eigrp_fsm_event_keep_state }, /* Event 3 */
 131                 { eigrp_fsm_event_keep_state }, /* Event 4 */
 132                 { eigrp_fsm_event_keep_state }, /* Event 5 */
 133                 { eigrp_fsm_event_keep_state }, /* Event 6 */
 134                 { eigrp_fsm_event_keep_state }, /* Event 7 */
 135 }, {
 136 //Active 0 state
 137                 { eigrp_fsm_event_keep_state }, /* Event 0 */
 138                 { eigrp_fsm_event_keep_state }, /* Event 1 */
 139                 { eigrp_fsm_event_keep_state }, /* Event 2 */
 140                 { eigrp_fsm_event_lr_fcs }, /* Event 3 */
 141                 { eigrp_fsm_event_keep_state }, /* Event 4 */
 142                 { eigrp_fsm_event_qact }, /* Event 5 */
 143                 { eigrp_fsm_event_lr_fcn }, /* Event 6 */
 144                 { eigrp_fsm_event_keep_state }, /* Event 7 */
 145
 146 }, {
 147 //Active 1 state
 148                 { eigrp_fsm_event_keep_state }, /* Event 0 */
 149                 { eigrp_fsm_event_lr }, /* Event 1 */
 150                 { eigrp_fsm_event_keep_state }, /* Event 2 */
 151                 { eigrp_fsm_event_keep_state }, /* Event 3 */
 152                 { eigrp_fsm_event_dinc }, /* Event 4 */
 153                 { eigrp_fsm_event_qact }, /* Event 5 */
 154                 { eigrp_fsm_event_keep_state }, /* Event 6 */
 155                 { eigrp_fsm_event_keep_state }, /* Event 7 */
 156 }, {
 157 //Active 2 state
 158                 { eigrp_fsm_event_keep_state }, /* Event 0 */
 159                 { eigrp_fsm_event_keep_state }, /* Event 1 */
 160                 { eigrp_fsm_event_keep_state }, /* Event 2 */
 161                 { eigrp_fsm_event_lr_fcs }, /* Event 3 */
 162                 { eigrp_fsm_event_keep_state }, /* Event 4 */
 163                 { eigrp_fsm_event_keep_state }, /* Event 5 */
 164                 { eigrp_fsm_event_lr_fcn }, /* Event 6 */
 165                 { eigrp_fsm_event_keep_state }, /* Event 7 */
 166 }, {
 167 //Active 3 state
 168                 { eigrp_fsm_event_keep_state }, /* Event 0 */
 169                 { eigrp_fsm_event_lr }, /* Event 1 */
 170                 { eigrp_fsm_event_keep_state }, /* Event 2 */
 171                 { eigrp_fsm_event_keep_state }, /* Event 3 */
 172                 { eigrp_fsm_event_dinc }, /* Event 4 */
 173                 { eigrp_fsm_event_keep_state }, /* Event 5 */
 174                 { eigrp_fsm_event_keep_state }, /* Event 6 */
 175                 { eigrp_fsm_event_keep_state }, /* Event 7 */
 176 }, };
 177
 178 /*
 179  * Main function in which are make decisions which event occurred.
 180  * msg - argument of type struct eigrp_fsm_action_message contain
 181  * details about what happen
 182  *
 183  * Return number of occurred event (arrow in diagram).
 184  *
 185  */
 186 int eigrp_get_fsm_event(struct eigrp_fsm_action_message *msg) {
 187         // Loading base information from message
 188         //struct eigrp *eigrp = msg->eigrp;
 189         struct eigrp_prefix_entry *prefix = msg->prefix;
 190         struct eigrp_neighbor_entry *entry = msg->entry;
 191         u_char actual_state = prefix->state;
 192
 193         if (entry == NULL) {
 194                 entry = eigrp_neighbor_entry_new();
 195                 entry->adv_router = msg->adv_router;
 196                 entry->ei = msg->adv_router->ei;
 197                 entry->prefix = prefix;
 198                 msg->entry = entry;
 199         }
 200
 201         // Dividing by actual state of prefix's FSM
 202         switch (actual_state) {
 203         case EIGRP_FSM_STATE_PASSIVE: {
 204                 //Calculate resultant metrics and insert to correct position in entries list
 205                 eigrp_topology_update_distance(msg);
 206
 207                 struct eigrp_neighbor_entry * head =
 208                                 (struct eigrp_neighbor_entry *) entry->prefix->entries->head->data;
 209                 //zlog_info ("flag: %d rdist: %u dist: %u pfdist: %u pdist: %u", head->flags, head->reported_distance, head->distance, prefix->fdistance, prefix->distance);
 210                 if (head->reported_distance < prefix->fdistance) {
 211                         return EIGRP_FSM_KEEP_STATE;
 212                 }
 213                 /*
 214                  * if best entry doesn't satisfy feasibility condition it means move to active state
 215                  * dependently if it was query from successor
 216                  */
 217                 else {
 218                         if (msg->packet_type == EIGRP_OPC_QUERY) {
 219                                 return EIGRP_FSM_EVENT_Q_FCN;
 220                         } else {
 221                                 return EIGRP_FSM_EVENT_NQ_FCN;
 222                         }
 223                 }
 224
 225                 break;
 226         }
 227         case EIGRP_FSM_STATE_ACTIVE_0: {
 228                 eigrp_topology_update_distance(msg);
 229
 230                 if (msg->packet_type == EIGRP_OPC_REPLY) {
 231                         listnode_delete(prefix->rij, entry->adv_router);
 232                         if (prefix->rij->count) {
 233                                 return EIGRP_FSM_KEEP_STATE;
 234                         } else {
 235                                 zlog_info("All reply received\n");
 236                                 if (((struct eigrp_neighbor_entry *) prefix->entries->head->data)->reported_distance
 237                                                 < prefix->fdistance) {
 238                                         return EIGRP_FSM_EVENT_LR_FCS;
 239                                 }
 240
 241                                 return EIGRP_FSM_EVENT_LR_FCN;
 242                         }
 243                 } else if (msg->packet_type == EIGRP_OPC_QUERY
 244                                 && (entry->flags & EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG)) {
 245                         return EIGRP_FSM_EVENT_QACT;
 246                 }
 247
 248                 return EIGRP_FSM_KEEP_STATE;
 249
 250                 break;
 251         }
 252         case EIGRP_FSM_STATE_ACTIVE_1: {
 253                 int change = eigrp_topology_update_distance(msg);
 254
 255                 if (msg->packet_type == EIGRP_OPC_QUERY
 256                                 && (entry->flags & EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG)) {
 257                         return EIGRP_FSM_EVENT_QACT;
 258                 } else if (msg->packet_type == EIGRP_OPC_REPLY) {
 259                         listnode_delete(prefix->rij, entry->adv_router);
 260
 261                         if (change == 1
 262                                         && (entry->flags & EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG)) {
 263                                 return EIGRP_FSM_EVENT_DINC;
 264                         } else if (prefix->rij->count) {
 265                                 return EIGRP_FSM_KEEP_STATE;
 266                         } else {
 267                                 zlog_info("All reply received\n");
 268                                 return EIGRP_FSM_EVENT_LR;
 269                         }
 270                 } else if (msg->packet_type == EIGRP_OPC_UPDATE && change == 1
 271                                 && (entry->flags & EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG)) {
 272                         return EIGRP_FSM_EVENT_DINC;
 273                 }
 274                 return EIGRP_FSM_KEEP_STATE;
 275
 276                 break;
 277         }
 278         case EIGRP_FSM_STATE_ACTIVE_2: {
 279
 280                 eigrp_topology_update_distance(msg);
 281
 282                 if (msg->packet_type == EIGRP_OPC_REPLY) {
 283                         listnode_delete(prefix->rij, entry->adv_router);
 284                         if (prefix->rij->count) {
 285                                 return EIGRP_FSM_KEEP_STATE;
 286                         } else {
 287                                 zlog_info("All reply received\n");
 288                                 if (((struct eigrp_neighbor_entry *) prefix->entries->head->data)->reported_distance
 289                                                 < prefix->fdistance) {
 290                                         return EIGRP_FSM_EVENT_LR_FCS;
 291                                 }
 292
 293                                 return EIGRP_FSM_EVENT_LR_FCN;
 294                         }
 295                 }
 296                 return EIGRP_FSM_KEEP_STATE;
 297
 298                 break;
 299         }
 300         case EIGRP_FSM_STATE_ACTIVE_3: {
 301
 302                 int change = eigrp_topology_update_distance(msg);
 303
 304                 if (msg->packet_type == EIGRP_OPC_REPLY) {
 305                         listnode_delete(prefix->rij, entry->adv_router);
 306
 307                         if (change == 1
 308                                         && (entry->flags & EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG)) {
 309                                 return EIGRP_FSM_EVENT_DINC;
 310                         } else if (prefix->rij->count) {
 311                                 return EIGRP_FSM_KEEP_STATE;
 312                         } else {
 313                                 zlog_info("All reply received\n");
 314                                 return EIGRP_FSM_EVENT_LR;
 315                         }
 316                 } else if (msg->packet_type == EIGRP_OPC_UPDATE && change == 1
 317                                 && (entry->flags & EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG)) {
 318                         return EIGRP_FSM_EVENT_DINC;
 319                 }
 320                 return EIGRP_FSM_KEEP_STATE;
 321
 322                 break;
 323         }
 324         }
 325
 326         return EIGRP_FSM_KEEP_STATE;
 327 }
 328
 329 /*
 330  * Function made to execute in separate thread.
 331  * Load argument from thread and execute proper NSM function
 332  */
 333 int eigrp_fsm_event(struct eigrp_fsm_action_message *msg, int event) {
 334
 335         zlog_info("EIGRP AS: %d State: %d  Event: %d Network: %s\n", msg->eigrp->AS,
 336                         msg->prefix->state, event, eigrp_topology_ip_string(msg->prefix));
 337         (*(NSM[msg->prefix->state][event].func))(msg);
 338
 339         return 1;
 340 }
 341 /*
 342  * Function of event 0.
 343  *
 344  */
 345 int eigrp_fsm_event_nq_fcn(struct eigrp_fsm_action_message *msg) {
 346         struct eigrp *eigrp = msg->eigrp;
 347         struct eigrp_prefix_entry *prefix = msg->prefix;
 348         struct list *successors = eigrp_topology_get_successor(prefix);
 349         prefix->state = EIGRP_FSM_STATE_ACTIVE_1;
 350         prefix->rdistance = prefix->distance = prefix->fdistance =
 351                         ((struct eigrp_neighbor_entry *) successors->head->data)->distance;
 352         prefix->reported_metric =
 353                         ((struct eigrp_neighbor_entry *) successors->head->data)->total_metric;
 354
 355         if (eigrp_nbr_count_get()) {
 356                 prefix->req_action |= EIGRP_FSM_NEED_QUERY;
 357                 listnode_add(eigrp->topology_changes_internalIPV4,prefix);
 358         } else {
 359                 eigrp_fsm_event_lr(msg); //in the case that there are no more neighbors left
 360         }
 361
 362         return 1;
 363 }
 364
 365 int eigrp_fsm_event_q_fcn(struct eigrp_fsm_action_message *msg) {
 366         struct eigrp *eigrp = msg->eigrp;
 367         struct eigrp_prefix_entry *prefix = msg->prefix;
 368         struct list *successors = eigrp_topology_get_successor(prefix);
 369         prefix->state = EIGRP_FSM_STATE_ACTIVE_3;
 370         prefix->rdistance = prefix->distance = prefix->fdistance =
 371                         ((struct eigrp_neighbor_entry *) successors->head->data)->distance;
 372         prefix->reported_metric =
 373                         ((struct eigrp_neighbor_entry *) successors->head->data)->total_metric;
 374         if (eigrp_nbr_count_get()) {
 375                         prefix->req_action |= EIGRP_FSM_NEED_QUERY;
 376                         listnode_add(eigrp->topology_changes_internalIPV4,prefix);
 377                 } else {
 378                         eigrp_fsm_event_lr(msg); //in the case that there are no more neighbors left
 379                 }
 380
 381         return 1;
 382 }
 383
 384 int eigrp_fsm_event_keep_state(struct eigrp_fsm_action_message *msg) {
 385
 386         struct eigrp_prefix_entry *prefix = msg->prefix;
 387
 388         if (prefix->state == EIGRP_FSM_STATE_PASSIVE) {
 389                 if (!eigrp_metrics_is_same(&prefix->reported_metric,
 390                                 &((struct eigrp_neighbor_entry *) prefix->entries->head->data)->total_metric)) {
 391                         prefix->rdistance =
 392                                         prefix->fdistance =
 393                                                         prefix->distance =
 394                                                                         ((struct eigrp_neighbor_entry *) prefix->entries->head->data)->distance;
 395                         prefix->reported_metric =
 396                                         ((struct eigrp_neighbor_entry *) prefix->entries->head->data)->total_metric;
 397                         if (msg->packet_type == EIGRP_OPC_QUERY)
 398                                 eigrp_send_reply(msg->adv_router, prefix);
 399                         prefix->req_action |= EIGRP_FSM_NEED_UPDATE;
 400                         listnode_add((eigrp_lookup())->topology_changes_internalIPV4,prefix);
 401                 }
 402                 eigrp_topology_update_node_flags(prefix);
 403                 eigrp_update_routing_table(prefix);
 404         }
 405
 406         if (msg->packet_type == EIGRP_OPC_QUERY)
 407                 eigrp_send_reply(msg->adv_router, prefix);
 408
 409         return 1;
 410 }
 411
 412 int eigrp_fsm_event_lr(struct eigrp_fsm_action_message *msg) {
 413         struct eigrp *eigrp = msg->eigrp;
 414         struct eigrp_prefix_entry *prefix = msg->prefix;
 415         prefix->fdistance =
 416                         prefix->distance =
 417                                         prefix->rdistance =
 418                                                         ((struct eigrp_neighbor_entry *) (prefix->entries->head->data))->distance;
 419         prefix->reported_metric =
 420                         ((struct eigrp_neighbor_entry *) (prefix->entries->head->data))->total_metric;
 421         if (prefix->state == EIGRP_FSM_STATE_ACTIVE_3)
 422                 eigrp_send_reply(
 423                                 ((struct eigrp_neighbor_entry *) (eigrp_topology_get_successor(
 424                                                 prefix)->head->data))->adv_router, prefix);
 425         prefix->state = EIGRP_FSM_STATE_PASSIVE;
 426         prefix->req_action |= EIGRP_FSM_NEED_UPDATE;
 427         listnode_add(eigrp->topology_changes_internalIPV4,prefix);
 428         eigrp_topology_update_node_flags(prefix);
 429         eigrp_update_routing_table(prefix);
 430         eigrp_update_topology_table_prefix(eigrp->topology_table, prefix);
 431
 432         return 1;
 433 }
 434
 435 int eigrp_fsm_event_dinc(struct eigrp_fsm_action_message *msg) {
 436
 437         msg->prefix->state =
 438                         msg->prefix->state == EIGRP_FSM_STATE_ACTIVE_1 ?
 439                                         EIGRP_FSM_STATE_ACTIVE_0 : EIGRP_FSM_STATE_ACTIVE_2;
 440         msg->prefix->distance =
 441                         ((struct eigrp_neighbor_entry *) (eigrp_topology_get_successor(
 442                                         msg->prefix)->head->data))->distance;
 443         if (!msg->prefix->rij->count) {
 444                 (*(NSM[msg->prefix->state][eigrp_get_fsm_event(msg)].func))(msg);
 445         }
 446
 447         return 1;
 448 }
 449
 450 int eigrp_fsm_event_lr_fcs(struct eigrp_fsm_action_message *msg) {
 451         struct eigrp *eigrp = msg->eigrp;
 452         struct eigrp_prefix_entry *prefix = msg->prefix;
 453         prefix->state = EIGRP_FSM_STATE_PASSIVE;
 454         prefix->distance =
 455                         prefix->rdistance =
 456                                         ((struct eigrp_neighbor_entry *) (prefix->entries->head->data))->distance;
 457         prefix->reported_metric =
 458                         ((struct eigrp_neighbor_entry *) (prefix->entries->head->data))->total_metric;
 459         prefix->fdistance =
 460                         prefix->fdistance > prefix->distance ?
 461                                         prefix->distance : prefix->fdistance;
 462         if (prefix->state == EIGRP_FSM_STATE_ACTIVE_2)
 463                 eigrp_send_reply(
 464                                 ((struct eigrp_neighbor_entry *) (eigrp_topology_get_successor(
 465                                                 prefix)->head->data))->adv_router, prefix);
 466         prefix->req_action |= EIGRP_FSM_NEED_UPDATE;
 467         listnode_add(eigrp->topology_changes_internalIPV4,prefix);
 468         eigrp_topology_update_node_flags(prefix);
 469         eigrp_update_routing_table(prefix);
 470         eigrp_update_topology_table_prefix(eigrp->topology_table, prefix);
 471
 472         return 1;
 473 }
 474
 475 int eigrp_fsm_event_lr_fcn(struct eigrp_fsm_action_message *msg) {
 476         struct eigrp *eigrp = msg->eigrp;
 477         struct eigrp_prefix_entry *prefix = msg->prefix;
 478         prefix->state =
 479                         prefix->state == EIGRP_FSM_STATE_ACTIVE_0 ?
 480                                         EIGRP_FSM_STATE_ACTIVE_1 : EIGRP_FSM_STATE_ACTIVE_3;
 481         struct eigrp_neighbor_entry *best_successor =
 482                         ((struct eigrp_neighbor_entry *) (eigrp_topology_get_successor(
 483                                         prefix)->head->data));
 484         prefix->rdistance = prefix->distance = best_successor->distance;
 485         prefix->reported_metric = best_successor->total_metric;
 486         if (eigrp_nbr_count_get()) {
 487                 prefix->req_action |= EIGRP_FSM_NEED_QUERY;
 488                 listnode_add(eigrp->topology_changes_internalIPV4,prefix);
 489         } else {
 490                 eigrp_fsm_event_lr(msg); //in the case that there are no more neighbors left
 491         }
 492
 493         return 1;
 494 }
 495
 496 int eigrp_fsm_event_qact(struct eigrp_fsm_action_message *msg) {
 497         msg->prefix->state = EIGRP_FSM_STATE_ACTIVE_2;
 498         msg->prefix->distance =
 499                         ((struct eigrp_neighbor_entry *) (eigrp_topology_get_successor(
 500                                         msg->prefix)->head->data))->distance;
 501         return 1;
 502 }