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