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