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