eigrpd/eigrp_topology.c

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