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