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