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