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