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