eigrpd/eigrp_topology.c

   1 /*
   2  * EIGRP Topology Table.
   3  * Copyright (C) 2013-2016
   4  * Authors:
   5  *   Donnie Savage
   6  *   Jan Janovic
   7  *   Matej Perina
   8  *   Peter Orsag
   9  *   Peter Paluch
  10  *   Frantisek Gazo
  11  *   Tomas Hvorkovy
  12  *   Martin Kontsek
  13  *   Lukas Koribsky
  14  *
  15  * This file is part of GNU Zebra.
  16  *
  17  * GNU Zebra is free software; you can redistribute it and/or modify it
  18  * under the terms of the GNU General Public License as published by the
  19  * Free Software Foundation; either version 2, or (at your option) any
  20  * later version.
  21  *
  22  * GNU Zebra is distributed in the hope that it will be useful, but
  23  * WITHOUT ANY WARRANTY; without even the implied warranty of
  24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  25  * General Public License for more details.
  26  *
  27  * You should have received a copy of the GNU General Public License
  28  * along with GNU Zebra; see the file COPYING.  If not, write to the Free
  29  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  30  * 02111-1307, USA.
  31  */
  32
  33 #include <zebra.h>
  34
  35 #include "prefix.h"
  36 #include "table.h"
  37 #include "memory.h"
  38 #include "log.h"
  39 #include "linklist.h"
  40 #include "vty.h"
  41
  42 #include "eigrpd/eigrp_structs.h"
  43 #include "eigrpd/eigrpd.h"
  44 #include "eigrpd/eigrp_interface.h"
  45 #include "eigrpd/eigrp_neighbor.h"
  46 #include "eigrpd/eigrp_packet.h"
  47 #include "eigrpd/eigrp_zebra.h"
  48 #include "eigrpd/eigrp_vty.h"
  49 #include "eigrpd/eigrp_network.h"
  50 #include "eigrpd/eigrp_dump.h"
  51 #include "eigrpd/eigrp_topology.h"
  52 #include "eigrpd/eigrp_fsm.h"
  53 #include "eigrpd/eigrp_memory.h"
  54
  55 static int eigrp_prefix_entry_cmp(struct eigrp_prefix_entry *, struct eigrp_prefix_entry *);
  56 static void eigrp_prefix_entry_del(struct eigrp_prefix_entry *);
  57 static int eigrp_neighbor_entry_cmp(struct eigrp_neighbor_entry *,
  58                                     struct eigrp_neighbor_entry *);
  59
  60 /*
  61  * Returns linkedlist used as topology table
  62  * cmp - assigned function for comparing topology nodes
  63  * del - assigned function executed before deleting topology node by list function
  64  */
  65 struct list *
  66 eigrp_topology_new()
  67 {
  68   struct list* new = list_new();
  69   new->cmp = (int
  70               (*)(void *, void *)) eigrp_prefix_entry_cmp;
  71   new->del = (void
  72               (*)(void *)) eigrp_prefix_entry_del;
  73
  74   return new;
  75 }
  76
  77 /*
  78  * Topology node comparison
  79  */
  80
  81 static int
  82 eigrp_prefix_entry_cmp(struct eigrp_prefix_entry *node1,
  83                        struct eigrp_prefix_entry *node2)
  84 {
  85   if (node1->af == AF_INET)
  86     {
  87       if (node2->af == AF_INET)
  88         {
  89           if (node1->destination_ipv4->prefix.s_addr
  90               < node2->destination_ipv4->prefix.s_addr)
  91             {
  92               return -1; // if it belong above node2
  93             }
  94           else
  95             {
  96               if (node1->destination_ipv4->prefix.s_addr
  97                   > node2->destination_ipv4->prefix.s_addr)
  98                 {
  99                   return 1; //if it belongs under node2
 100                 }
 101               else
 102                 {
 103                   return 0; // same value... ERROR...in case of adding same prefix again
 104                 }
 105             }
 106         }
 107       else
 108         {
 109           return 1;
 110         }
 111     }
 112   else
 113     { // TODO check if the prefix dont exists
 114       return 1; // add to end
 115     }
 116 }
 117
 118 /*
 119  * Topology node delete
 120  */
 121
 122 static void
 123 eigrp_prefix_entry_del(struct eigrp_prefix_entry *node)
 124 {
 125   list_delete_all_node(node->entries);
 126   list_free(node->entries);
 127 }
 128
 129 /*
 130  * Returns new created toplogy node
 131  * cmp - assigned function for comparing topology entry
 132  */
 133 struct eigrp_prefix_entry *
 134 eigrp_prefix_entry_new()
 135 {
 136   struct eigrp_prefix_entry *new;
 137   new = XCALLOC(MTYPE_EIGRP_PREFIX_ENTRY, sizeof(struct eigrp_prefix_entry));
 138   new->entries = list_new();
 139   new->rij = list_new();
 140   new->entries->cmp = (int (*)(void *, void *))eigrp_neighbor_entry_cmp;
 141   new->distance = new->fdistance = new->rdistance = EIGRP_MAX_METRIC;
 142   new->destination_ipv4 = NULL;
 143   new->destination_ipv6 = NULL;
 144
 145   return new;
 146 }
 147
 148 /*
 149  * Topology entry comparison
 150  */
 151 static int
 152 eigrp_neighbor_entry_cmp(struct eigrp_neighbor_entry *entry1,
 153                          struct eigrp_neighbor_entry *entry2)
 154 {
 155   if (entry1->distance < entry2->distance) // parameter used in list_add_sort ()
 156     return -1; // actually set to sort by distance
 157   if (entry1->distance > entry2->distance)
 158     return 1;
 159
 160   return 0;
 161 }
 162
 163 /*
 164  * Returns new topology entry
 165  */
 166
 167 struct eigrp_neighbor_entry *
 168 eigrp_neighbor_entry_new()
 169 {
 170   struct eigrp_neighbor_entry *new;
 171
 172   new = XCALLOC(MTYPE_EIGRP_NEIGHBOR_ENTRY,
 173                 sizeof(struct eigrp_neighbor_entry));
 174   new->reported_distance = EIGRP_MAX_METRIC;
 175   new->distance = EIGRP_MAX_METRIC;
 176
 177   return new;
 178 }
 179
 180 /*
 181  * Freeing topology table list
 182  */
 183 void
 184 eigrp_topology_free(struct list *list)
 185 {
 186   list_free(list);
 187 }
 188
 189 /*
 190  * Deleting all topology nodes in table
 191  */
 192 void
 193 eigrp_topology_cleanup(struct list *topology)
 194 {
 195   assert(topology);
 196
 197   eigrp_topology_delete_all(topology);
 198 }
 199
 200 /*
 201  * Adding topology node to topology table
 202  */
 203 void
 204 eigrp_prefix_entry_add(struct list *topology, struct eigrp_prefix_entry *node)
 205 {
 206   if (listnode_lookup(topology, node) == NULL)
 207     {
 208       listnode_add_sort(topology, node);
 209     }
 210 }
 211
 212 /*
 213  * Adding topology entry to topology node
 214  */
 215 void
 216 eigrp_neighbor_entry_add(struct eigrp_prefix_entry *node,
 217                          struct eigrp_neighbor_entry *entry)
 218 {
 219   if (listnode_lookup(node->entries, entry) == NULL)
 220     {
 221       listnode_add_sort(node->entries, entry);
 222       entry->prefix = node;
 223     }
 224 }
 225
 226 /*
 227  * Deleting topology node from topology table
 228  */
 229 void
 230 eigrp_prefix_entry_delete(struct list *topology,
 231                           struct eigrp_prefix_entry *node)
 232 {
 233   struct eigrp *eigrp = eigrp_lookup ();
 234
 235   /*
 236    * Emergency removal of the node from this list.
 237    * Whatever it is.
 238    */
 239   listnode_delete(eigrp->topology_changes_internalIPV4, node);
 240
 241   if (listnode_lookup(topology, node) != NULL)
 242     {
 243       list_delete_all_node(node->entries);
 244       list_free(node->entries);
 245       list_free(node->rij);
 246       listnode_delete(topology, node);
 247       XFREE(MTYPE_EIGRP_PREFIX_ENTRY,node);
 248     }
 249 }
 250
 251 /*
 252  * Deleting topology entry from topology node
 253  */
 254 void
 255 eigrp_neighbor_entry_delete(struct eigrp_prefix_entry *node,
 256                             struct eigrp_neighbor_entry *entry)
 257 {
 258   if (listnode_lookup(node->entries, entry) != NULL)
 259     {
 260       listnode_delete(node->entries, entry);
 261       XFREE(MTYPE_EIGRP_NEIGHBOR_ENTRY,entry);
 262     }
 263 }
 264
 265 /*
 266  * Deleting all nodes from topology table
 267  */
 268 void
 269 eigrp_topology_delete_all(struct list *topology)
 270 {
 271   list_delete_all_node(topology);
 272 }
 273
 274 /*
 275  * Return 0 if topology is not empty
 276  * otherwise return 1
 277  */
 278 unsigned int
 279 eigrp_topology_table_isempty(struct list *topology)
 280 {
 281   if (topology->count)
 282     return 1;
 283   else
 284     return 0;
 285 }
 286
 287 struct eigrp_prefix_entry *
 288 eigrp_topology_table_lookup_ipv4(struct list *topology_table,
 289                                  struct prefix_ipv4 * address)
 290 {
 291   struct eigrp_prefix_entry *data;
 292   struct listnode *node;
 293   for (ALL_LIST_ELEMENTS_RO(topology_table, node, data))
 294     {
 295       if ((data->af == AF_INET)
 296           && (data->destination_ipv4->prefix.s_addr == address->prefix.s_addr)
 297           && (data->destination_ipv4->prefixlen == address->prefixlen))
 298         return data;
 299     }
 300
 301   return NULL;
 302 }
 303
 304 /*
 305  * For a future optimization, put the successor list into it's
 306  * own separate list from the full list?
 307  *
 308  * That way we can clean up all the list_new and list_delete's
 309  * that we are doing.  DBS
 310  */
 311 struct list *
 312 eigrp_topology_get_successor(struct eigrp_prefix_entry *table_node)
 313 {
 314   struct list *successors = list_new();
 315   struct eigrp_neighbor_entry *data;
 316   struct listnode *node1, *node2;
 317
 318   for (ALL_LIST_ELEMENTS(table_node->entries, node1, node2, data))
 319     {
 320       if (data->flags & EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG)
 321         {
 322           listnode_add(successors, data);
 323         }
 324     }
 325
 326   /*
 327    * If we have no successors return NULL
 328    */
 329   if (!successors->count)
 330     {
 331       list_delete(successors);
 332       successors = NULL;
 333     }
 334
 335   return successors;
 336 }
 337
 338 struct list *
 339 eigrp_topology_get_successor_max(struct eigrp_prefix_entry *table_node,
 340                                  unsigned int maxpaths)
 341 {
 342   struct list *successors = eigrp_topology_get_successor(table_node);
 343
 344   if (successors && successors->count > maxpaths)
 345     {
 346       do
 347         {
 348           struct listnode *node = listtail(successors);
 349
 350           list_delete_node(successors, node);
 351
 352         } while (successors->count > maxpaths);
 353     }
 354
 355   return successors;
 356 }
 357
 358 struct eigrp_neighbor_entry *
 359 eigrp_prefix_entry_lookup(struct list *entries, struct eigrp_neighbor *nbr)
 360 {
 361   struct eigrp_neighbor_entry *data;
 362   struct listnode *node, *nnode;
 363   for (ALL_LIST_ELEMENTS(entries, node, nnode, data))
 364     {
 365       if (data->adv_router == nbr)
 366         {
 367           return data;
 368         }
 369     }
 370
 371   return NULL;
 372 }
 373
 374 /* Lookup all prefixes from specified neighbor */
 375 struct list *
 376 eigrp_neighbor_prefixes_lookup(struct eigrp *eigrp, struct eigrp_neighbor *nbr)
 377 {
 378   struct listnode *node1, *node11, *node2, *node22;
 379   struct eigrp_prefix_entry *prefix;
 380   struct eigrp_neighbor_entry *entry;
 381
 382   /* create new empty list for prefixes storage */
 383   struct list *prefixes = list_new();
 384
 385   /* iterate over all prefixes in topology table */
 386   for (ALL_LIST_ELEMENTS(eigrp->topology_table, node1, node11, prefix))
 387     {
 388       /* iterate over all neighbor entry in prefix */
 389       for (ALL_LIST_ELEMENTS(prefix->entries, node2, node22, entry))
 390         {
 391           /* if entry is from specified neighbor, add to list */
 392           if (entry->adv_router == nbr)
 393             {
 394               listnode_add(prefixes, prefix);
 395             }
 396         }
 397     }
 398
 399   /* return list of prefixes from specified neighbor */
 400   return prefixes;
 401 }
 402
 403 int
 404 eigrp_topology_update_distance(struct eigrp_fsm_action_message *msg)
 405 {
 406   struct eigrp *eigrp = msg->eigrp;
 407   struct eigrp_prefix_entry *prefix = msg->prefix;
 408   struct eigrp_neighbor_entry *entry = msg->entry;
 409   int change = 0;
 410   assert(entry);
 411
 412   struct TLV_IPv4_External_type *ext_data = NULL;
 413   struct TLV_IPv4_Internal_type *int_data = NULL;
 414   if (msg->data_type == EIGRP_TLV_IPv4_INT)
 415     {
 416       int_data = msg->data.ipv4_int_type;
 417       if (eigrp_metrics_is_same(&int_data->metric,&entry->reported_metric))
 418         {
 419           return 0; // No change
 420         }
 421       change =
 422         entry->reported_distance
 423         < eigrp_calculate_metrics(eigrp, &int_data->metric) ? 1 :
 424           entry->reported_distance
 425         > eigrp_calculate_metrics(eigrp, &int_data->metric) ? 2 : 3; // Increase : Decrease : No change
 426       entry->reported_metric = int_data->metric;
 427       entry->reported_distance =
 428         eigrp_calculate_metrics(eigrp, &int_data->metric);
 429       entry->distance = eigrp_calculate_total_metrics(eigrp, entry);
 430     }
 431   else
 432     {
 433       ext_data = msg->data.ipv4_ext_data;
 434       if (eigrp_metrics_is_same (&ext_data->metric, &entry->reported_metric))
 435         return 0;
 436     }
 437   /*
 438    * Move to correct position in list according to new distance
 439    */
 440   listnode_delete(prefix->entries, entry);
 441   listnode_add_sort(prefix->entries, entry);
 442
 443   return change;
 444 }
 445
 446 void
 447 eigrp_topology_update_all_node_flags(struct eigrp *eigrp)
 448 {
 449   struct list *table = eigrp->topology_table;
 450   struct eigrp_prefix_entry *data;
 451   struct listnode *node, *nnode;
 452   for (ALL_LIST_ELEMENTS(table, node, nnode, data))
 453     {
 454       eigrp_topology_update_node_flags(data);
 455     }
 456 }
 457
 458 void
 459 eigrp_topology_update_node_flags(struct eigrp_prefix_entry *dest)
 460 {
 461   struct listnode *node;
 462   struct eigrp_neighbor_entry *entry;
 463   struct eigrp * eigrp = eigrp_lookup();
 464
 465   for (ALL_LIST_ELEMENTS_RO(dest->entries, node, entry))
 466     {
 467       if ((entry->distance <= (u_int64_t)(dest->distance*eigrp->variance)) &&
 468           entry->distance != EIGRP_MAX_METRIC) // is successor
 469         {
 470           entry->flags |= EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG;
 471           entry->flags &= ~EIGRP_NEIGHBOR_ENTRY_FSUCCESSOR_FLAG;
 472         }
 473       else if (entry->reported_distance < dest->fdistance) // is feasible successor
 474         {
 475           entry->flags |= EIGRP_NEIGHBOR_ENTRY_FSUCCESSOR_FLAG;
 476           entry->flags &= ~EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG;
 477         }
 478       else
 479         {
 480           entry->flags &= ~EIGRP_NEIGHBOR_ENTRY_FSUCCESSOR_FLAG;
 481           entry->flags &= ~EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG;
 482         }
 483     }
 484 }
 485
 486 void
 487 eigrp_update_routing_table(struct eigrp_prefix_entry * prefix)
 488 {
 489   struct eigrp *eigrp = eigrp_lookup();
 490   struct list *successors = eigrp_topology_get_successor_max(prefix, eigrp->max_paths);
 491   struct listnode *node;
 492   struct eigrp_neighbor_entry *entry;
 493
 494   if (successors)
 495     {
 496       eigrp_zebra_route_add(prefix->destination_ipv4, successors);
 497       for (ALL_LIST_ELEMENTS_RO (successors, node, entry))
 498         entry->flags |= EIGRP_NEIGHBOR_ENTRY_INTABLE_FLAG;
 499
 500       list_delete(successors);
 501     }
 502   else
 503     {
 504       eigrp_zebra_route_delete(prefix->destination_ipv4);
 505       for (ALL_LIST_ELEMENTS_RO (prefix->entries, node, entry))
 506         entry->flags &= ~EIGRP_NEIGHBOR_ENTRY_INTABLE_FLAG;
 507     }
 508 }
 509
 510 void
 511 eigrp_topology_neighbor_down(struct eigrp *eigrp, struct eigrp_neighbor * nbr)
 512 {
 513   struct listnode *node1, *node11, *node2, *node22;
 514   struct eigrp_prefix_entry *prefix;
 515   struct eigrp_neighbor_entry *entry;
 516
 517   for (ALL_LIST_ELEMENTS(eigrp->topology_table, node1, node11, prefix))
 518     {
 519       for (ALL_LIST_ELEMENTS(prefix->entries, node2, node22, entry))
 520         {
 521           if (entry->adv_router == nbr)
 522             {
 523               struct eigrp_fsm_action_message *msg;
 524               msg = XCALLOC(MTYPE_EIGRP_FSM_MSG,
 525                             sizeof(struct eigrp_fsm_action_message));
 526               struct TLV_IPv4_Internal_type * tlv = eigrp_IPv4_InternalTLV_new();
 527               tlv->metric.delay = EIGRP_MAX_METRIC;
 528               msg->packet_type = EIGRP_OPC_UPDATE;
 529               msg->eigrp = eigrp;
 530               msg->data_type = EIGRP_TLV_IPv4_INT;
 531               msg->adv_router = nbr;
 532               msg->data.ipv4_int_type = tlv;
 533               msg->entry = entry;
 534               msg->prefix = prefix;
 535               int event = eigrp_get_fsm_event(msg);
 536               eigrp_fsm_event(msg, event);
 537             }
 538         }
 539     }
 540
 541   eigrp_query_send_all(eigrp);
 542   eigrp_update_send_all(eigrp,nbr->ei);
 543
 544 }
 545
 546 void
 547 eigrp_update_topology_table_prefix(struct list * table, struct eigrp_prefix_entry * prefix)
 548 {
 549   struct listnode *node1, *node2;
 550
 551   struct eigrp_neighbor_entry *entry;
 552   for (ALL_LIST_ELEMENTS(prefix->entries, node1, node2, entry))
 553     {
 554       if(entry->distance == EIGRP_MAX_METRIC)
 555         {
 556           eigrp_neighbor_entry_delete(prefix,entry);
 557         }
 558     }
 559   if(prefix->distance == EIGRP_MAX_METRIC && prefix->nt != EIGRP_TOPOLOGY_TYPE_CONNECTED)
 560     {
 561       eigrp_prefix_entry_delete(table,prefix);
 562     }
 563 }