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