isisd/isis_route.c

   1 /*
   2  * IS-IS Rout(e)ing protocol               - isis_route.c
   3  * Copyright (C) 2001,2002   Sampo Saaristo
   4  *                           Tampere University of Technology
   5  *                           Institute of Communications Engineering
   6  *
   7  *                                         based on ../ospf6d/ospf6_route.[ch]
   8  *                                         by Yasuhiro Ohara
   9  *
  10  * This program is free software; you can redistribute it and/or modify it
  11  * under the terms of the GNU General Public Licenseas published by the Free
  12  * Software Foundation; either version 2 of the License, or (at your option)
  13  * any later version.
  14  *
  15  * This program is distributed in the hope that it will be useful,but WITHOUT
  16  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  17  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  18  * more details.
  19  *
  20  * You should have received a copy of the GNU General Public License along
  21  * with this program; see the file COPYING; if not, write to the Free Software
  22  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  23  */
  24
  25 #include <zebra.h>
  26
  27 #include "thread.h"
  28 #include "linklist.h"
  29 #include "vty.h"
  30 #include "log.h"
  31 #include "lib_errors.h"
  32 #include "memory.h"
  33 #include "prefix.h"
  34 #include "hash.h"
  35 #include "if.h"
  36 #include "table.h"
  37 #include "srcdest_table.h"
  38
  39 #include "isis_constants.h"
  40 #include "isis_common.h"
  41 #include "isis_flags.h"
  42 #include "isisd.h"
  43 #include "isis_misc.h"
  44 #include "isis_adjacency.h"
  45 #include "isis_circuit.h"
  46 #include "isis_pdu.h"
  47 #include "isis_lsp.h"
  48 #include "isis_spf.h"
  49 #include "isis_spf_private.h"
  50 #include "isis_route.h"
  51 #include "isis_zebra.h"
  52
  53 DEFINE_HOOK(isis_route_update_hook,
  54             (struct isis_area * area, struct prefix *prefix,
  55              struct isis_route_info *route_info),
  56             (area, prefix, route_info))
  57
  58 static struct isis_nexthop *nexthoplookup(struct list *nexthops, int family,
  59                                           union g_addr *ip, ifindex_t ifindex);
  60 static void isis_route_update(struct isis_area *area, struct prefix *prefix,
  61                               struct prefix_ipv6 *src_p,
  62                               struct isis_route_info *route_info);
  63
  64 static struct isis_nexthop *isis_nexthop_create(int family, union g_addr *ip,
  65                                                 ifindex_t ifindex)
  66 {
  67         struct isis_nexthop *nexthop;
  68
  69         nexthop = XCALLOC(MTYPE_ISIS_NEXTHOP, sizeof(struct isis_nexthop));
  70
  71         nexthop->family = family;
  72         nexthop->ifindex = ifindex;
  73         nexthop->ip = *ip;
  74         isis_sr_nexthop_reset(&nexthop->sr);
  75
  76         return nexthop;
  77 }
  78
  79 static void isis_nexthop_delete(struct isis_nexthop *nexthop)
  80 {
  81         XFREE(MTYPE_ISIS_NEXTHOP, nexthop);
  82 }
  83
  84 static struct isis_nexthop *nexthoplookup(struct list *nexthops, int family,
  85                                           union g_addr *ip, ifindex_t ifindex)
  86 {
  87         struct listnode *node;
  88         struct isis_nexthop *nh;
  89
  90         for (ALL_LIST_ELEMENTS_RO(nexthops, node, nh)) {
  91                 if (nh->family != family)
  92                         continue;
  93                 if (nh->ifindex != ifindex)
  94                         continue;
  95
  96                 switch (family) {
  97                 case AF_INET:
  98                         if (IPV4_ADDR_CMP(&nh->ip.ipv4, &ip->ipv4))
  99                                 continue;
 100                         break;
 101                 case AF_INET6:
 102                         if (IPV6_ADDR_CMP(&nh->ip.ipv6, &ip->ipv6))
 103                                 continue;
 104                         break;
 105                 default:
 106                         flog_err(EC_LIB_DEVELOPMENT,
 107                                  "%s: unknown address family [%d]", __func__,
 108                                  family);
 109                         exit(1);
 110                 }
 111
 112                 return nh;
 113         }
 114
 115         return NULL;
 116 }
 117
 118 static void adjinfo2nexthop(int family, struct list *nexthops,
 119                             struct isis_adjacency *adj)
 120 {
 121         struct isis_nexthop *nh;
 122         union g_addr ip = {};
 123
 124         switch (family) {
 125         case AF_INET:
 126                 for (unsigned int i = 0; i < adj->ipv4_address_count; i++) {
 127                         ip.ipv4 = adj->ipv4_addresses[i];
 128
 129                         if (!nexthoplookup(nexthops, AF_INET, &ip,
 130                                            adj->circuit->interface->ifindex)) {
 131                                 nh = isis_nexthop_create(
 132                                         AF_INET, &ip,
 133                                         adj->circuit->interface->ifindex);
 134                                 memcpy(nh->sysid, adj->sysid, sizeof(nh->sysid));
 135                                 listnode_add(nexthops, nh);
 136                                 break;
 137                         }
 138                 }
 139                 break;
 140         case AF_INET6:
 141                 for (unsigned int i = 0; i < adj->ipv6_address_count; i++) {
 142                         ip.ipv6 = adj->ipv6_addresses[i];
 143
 144                         if (!nexthoplookup(nexthops, AF_INET6, &ip,
 145                                            adj->circuit->interface->ifindex)) {
 146                                 nh = isis_nexthop_create(
 147                                         AF_INET6, &ip,
 148                                         adj->circuit->interface->ifindex);
 149                                 memcpy(nh->sysid, adj->sysid, sizeof(nh->sysid));
 150                                 listnode_add(nexthops, nh);
 151                                 break;
 152                         }
 153                 }
 154                 break;
 155         default:
 156                 flog_err(EC_LIB_DEVELOPMENT, "%s: unknown address family [%d]",
 157                          __func__, family);
 158                 exit(1);
 159         }
 160 }
 161
 162 static void isis_route_add_dummy_nexthops(struct isis_route_info *rinfo,
 163                                           const uint8_t *sysid)
 164 {
 165         struct isis_nexthop *nh;
 166
 167         nh = XCALLOC(MTYPE_ISIS_NEXTHOP, sizeof(struct isis_nexthop));
 168         memcpy(nh->sysid, sysid, sizeof(nh->sysid));
 169         isis_sr_nexthop_reset(&nh->sr);
 170         listnode_add(rinfo->nexthops, nh);
 171 }
 172
 173 static struct isis_route_info *isis_route_info_new(struct prefix *prefix,
 174                                                    struct prefix_ipv6 *src_p,
 175                                                    uint32_t cost,
 176                                                    uint32_t depth,
 177                                                    struct list *adjacencies)
 178 {
 179         struct isis_route_info *rinfo;
 180         struct isis_vertex_adj *vadj;
 181         struct listnode *node;
 182
 183         rinfo = XCALLOC(MTYPE_ISIS_ROUTE_INFO, sizeof(struct isis_route_info));
 184
 185         rinfo->nexthops = list_new();
 186         for (ALL_LIST_ELEMENTS_RO(adjacencies, node, vadj)) {
 187                 struct isis_spf_adj *sadj = vadj->sadj;
 188                 struct isis_adjacency *adj = sadj->adj;
 189
 190                 /*
 191                  * Create dummy nexthops when running SPF on a testing
 192                  * environment.
 193                  */
 194                 if (CHECK_FLAG(im->options, F_ISIS_UNIT_TEST)) {
 195                         isis_route_add_dummy_nexthops(rinfo, sadj->id);
 196                         continue;
 197                 }
 198
 199                 /* check for force resync this route */
 200                 if (CHECK_FLAG(adj->circuit->flags,
 201                                ISIS_CIRCUIT_FLAPPED_AFTER_SPF))
 202                         SET_FLAG(rinfo->flag, ISIS_ROUTE_FLAG_ZEBRA_RESYNC);
 203
 204                 /* update neighbor router address */
 205                 switch (prefix->family) {
 206                 case AF_INET:
 207                         if (depth == 2 && prefix->prefixlen == 32)
 208                                 adj->router_address = prefix->u.prefix4;
 209                         break;
 210                 case AF_INET6:
 211                         if (depth == 2 && prefix->prefixlen == 128
 212                             && (!src_p || !src_p->prefixlen)) {
 213                                 adj->router_address6 = prefix->u.prefix6;
 214                         }
 215                         break;
 216                 default:
 217                         flog_err(EC_LIB_DEVELOPMENT,
 218                                  "%s: unknown address family [%d]", __func__,
 219                                  prefix->family);
 220                         exit(1);
 221                 }
 222                 adjinfo2nexthop(prefix->family, rinfo->nexthops, adj);
 223         }
 224
 225         rinfo->cost = cost;
 226         rinfo->depth = depth;
 227
 228         return rinfo;
 229 }
 230
 231 static void isis_route_info_delete(struct isis_route_info *route_info)
 232 {
 233         if (route_info->nexthops) {
 234                 route_info->nexthops->del =
 235                         (void (*)(void *))isis_nexthop_delete;
 236                 list_delete(&route_info->nexthops);
 237         }
 238
 239         XFREE(MTYPE_ISIS_ROUTE_INFO, route_info);
 240 }
 241
 242 static int isis_route_info_same(struct isis_route_info *new,
 243                                 struct isis_route_info *old, char *buf,
 244                                 size_t buf_size)
 245 {
 246         struct listnode *node;
 247         struct isis_nexthop *nexthop;
 248
 249         if (new->cost != old->cost) {
 250                 if (buf)
 251                         snprintf(buf, buf_size, "cost (old: %u, new: %u)",
 252                                  old->cost, new->cost);
 253                 return 0;
 254         }
 255
 256         if (new->depth != old->depth) {
 257                 if (buf)
 258                         snprintf(buf, buf_size, "depth (old: %u, new: %u)",
 259                                  old->depth, new->depth);
 260                 return 0;
 261         }
 262
 263         if (new->nexthops->count != old->nexthops->count) {
 264                 if (buf)
 265                         snprintf(buf, buf_size, "nhops num (old: %u, new: %u)",
 266                                  old->nexthops->count, new->nexthops->count);
 267                 return 0;
 268         }
 269
 270         for (ALL_LIST_ELEMENTS_RO(new->nexthops, node, nexthop)) {
 271                 if (!nexthoplookup(old->nexthops, nexthop->family, &nexthop->ip,
 272                                    nexthop->ifindex)) {
 273                         if (buf)
 274                                 snprintf(buf, buf_size,
 275                                          "new nhop"); /* TODO: print nhop */
 276                         return 0;
 277                 }
 278         }
 279
 280         /* only the resync flag needs to be checked */
 281         if (CHECK_FLAG(new->flag, ISIS_ROUTE_FLAG_ZEBRA_RESYNC)
 282             != CHECK_FLAG(old->flag, ISIS_ROUTE_FLAG_ZEBRA_RESYNC)) {
 283                 if (buf)
 284                         snprintf(buf, buf_size, "resync flag");
 285                 return 0;
 286         }
 287
 288         return 1;
 289 }
 290
 291 struct isis_route_info *isis_route_create(struct prefix *prefix,
 292                                           struct prefix_ipv6 *src_p,
 293                                           uint32_t cost,
 294                                           uint32_t depth,
 295                                           struct list *adjacencies,
 296                                           struct isis_area *area,
 297                                           struct route_table *table)
 298 {
 299         struct route_node *route_node;
 300         struct isis_route_info *rinfo_new, *rinfo_old, *route_info = NULL;
 301         char buff[PREFIX2STR_BUFFER];
 302         char change_buf[64];
 303
 304         /* for debugs */
 305         prefix2str(prefix, buff, sizeof(buff));
 306
 307         if (!table)
 308                 return NULL;
 309
 310         rinfo_new = isis_route_info_new(prefix, src_p, cost,
 311                                         depth, adjacencies);
 312         route_node = srcdest_rnode_get(table, prefix, src_p);
 313
 314         rinfo_old = route_node->info;
 315         if (!rinfo_old) {
 316                 if (IS_DEBUG_RTE_EVENTS)
 317                         zlog_debug("ISIS-Rte (%s) route created: %s",
 318                                    area->area_tag, buff);
 319                 route_info = rinfo_new;
 320                 UNSET_FLAG(route_info->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED);
 321         } else {
 322                 route_unlock_node(route_node);
 323 #ifdef EXTREME_DEBUG
 324                 if (IS_DEBUG_RTE_EVENTS)
 325                         zlog_debug("ISIS-Rte (%s) route already exists: %s",
 326                                    area->area_tag, buff);
 327 #endif /* EXTREME_DEBUG */
 328                 if (isis_route_info_same(rinfo_new, rinfo_old, change_buf,
 329                                          sizeof(change_buf))) {
 330 #ifdef EXTREME_DEBUG
 331                         if (IS_DEBUG_RTE_EVENTS)
 332                                 zlog_debug("ISIS-Rte (%s) route unchanged: %s",
 333                                            area->area_tag, buff);
 334 #endif /* EXTREME_DEBUG */
 335                         isis_route_info_delete(rinfo_new);
 336                         route_info = rinfo_old;
 337                 } else {
 338                         if (IS_DEBUG_RTE_EVENTS)
 339                                 zlog_debug(
 340                                         "ISIS-Rte (%s): route changed: %s, change: %s",
 341                                         area->area_tag, buff, change_buf);
 342                         isis_route_info_delete(rinfo_old);
 343                         route_info = rinfo_new;
 344                         UNSET_FLAG(route_info->flag,
 345                                    ISIS_ROUTE_FLAG_ZEBRA_SYNCED);
 346                 }
 347         }
 348
 349         SET_FLAG(route_info->flag, ISIS_ROUTE_FLAG_ACTIVE);
 350         route_node->info = route_info;
 351
 352         return route_info;
 353 }
 354
 355 static void isis_route_delete(struct isis_area *area, struct route_node *rode,
 356                               struct route_table *table)
 357 {
 358         struct isis_route_info *rinfo;
 359         char buff[SRCDEST2STR_BUFFER];
 360         struct prefix *prefix;
 361         struct prefix_ipv6 *src_p;
 362
 363         /* for log */
 364         srcdest_rnode2str(rode, buff, sizeof(buff));
 365
 366         srcdest_rnode_prefixes(rode, (const struct prefix **)&prefix,
 367                                (const struct prefix **)&src_p);
 368
 369         rinfo = rode->info;
 370         if (rinfo == NULL) {
 371                 if (IS_DEBUG_RTE_EVENTS)
 372                         zlog_debug(
 373                                 "ISIS-Rte: tried to delete non-existant route %s",
 374                                 buff);
 375                 return;
 376         }
 377
 378         if (CHECK_FLAG(rinfo->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED)) {
 379                 UNSET_FLAG(rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE);
 380                 if (IS_DEBUG_RTE_EVENTS)
 381                         zlog_debug("ISIS-Rte: route delete  %s", buff);
 382                 isis_route_update(area, prefix, src_p, rinfo);
 383         }
 384         isis_route_info_delete(rinfo);
 385         rode->info = NULL;
 386         route_unlock_node(rode);
 387 }
 388
 389 static void isis_route_update(struct isis_area *area, struct prefix *prefix,
 390                               struct prefix_ipv6 *src_p,
 391                               struct isis_route_info *route_info)
 392 {
 393         if (CHECK_FLAG(route_info->flag, ISIS_ROUTE_FLAG_ACTIVE)) {
 394                 if (CHECK_FLAG(route_info->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED))
 395                         return;
 396
 397                 isis_zebra_route_add_route(area->isis, prefix, src_p, route_info);
 398                 hook_call(isis_route_update_hook, area, prefix, route_info);
 399
 400                 SET_FLAG(route_info->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED);
 401                 UNSET_FLAG(route_info->flag, ISIS_ROUTE_FLAG_ZEBRA_RESYNC);
 402         } else {
 403                 if (!CHECK_FLAG(route_info->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED))
 404                         return;
 405
 406                 isis_zebra_route_del_route(area->isis, prefix, src_p, route_info);
 407                 hook_call(isis_route_update_hook, area, prefix, route_info);
 408
 409                 UNSET_FLAG(route_info->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED);
 410         }
 411 }
 412
 413 static void _isis_route_verify_table(struct isis_area *area,
 414                                      struct route_table *table,
 415                                      struct route_table **tables)
 416 {
 417         struct route_node *rnode, *drnode;
 418         struct isis_route_info *rinfo;
 419 #ifdef EXTREME_DEBUG
 420         char buff[SRCDEST2STR_BUFFER];
 421 #endif /* EXTREME_DEBUG */
 422
 423         for (rnode = route_top(table); rnode;
 424              rnode = srcdest_route_next(rnode)) {
 425                 if (rnode->info == NULL)
 426                         continue;
 427                 rinfo = rnode->info;
 428
 429                 struct prefix *dst_p;
 430                 struct prefix_ipv6 *src_p;
 431
 432                 srcdest_rnode_prefixes(rnode,
 433                                        (const struct prefix **)&dst_p,
 434                                        (const struct prefix **)&src_p);
 435
 436 #ifdef EXTREME_DEBUG
 437                 if (IS_DEBUG_RTE_EVENTS) {
 438                         srcdest2str(dst_p, src_p, buff, sizeof(buff));
 439                         zlog_debug(
 440                                 "ISIS-Rte (%s): route validate: %s %s %s %s",
 441                                 area->area_tag,
 442                                 (CHECK_FLAG(rinfo->flag,
 443                                             ISIS_ROUTE_FLAG_ZEBRA_SYNCED)
 444                                          ? "synced"
 445                                          : "not-synced"),
 446                                 (CHECK_FLAG(rinfo->flag,
 447                                             ISIS_ROUTE_FLAG_ZEBRA_RESYNC)
 448                                          ? "resync"
 449                                          : "not-resync"),
 450                                 (CHECK_FLAG(rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE)
 451                                          ? "active"
 452                                          : "inactive"),
 453                                 buff);
 454                 }
 455 #endif /* EXTREME_DEBUG */
 456
 457                 isis_route_update(area, dst_p, src_p, rinfo);
 458
 459                 if (CHECK_FLAG(rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE))
 460                         continue;
 461
 462                 /* Area is either L1 or L2 => we use level route tables
 463                  * directly for
 464                  * validating => no problems with deleting routes. */
 465                 if (!tables) {
 466                         isis_route_delete(area, rnode, table);
 467                         continue;
 468                 }
 469
 470                 /* If area is L1L2, we work with merge table and
 471                  * therefore must
 472                  * delete node from level tables as well before deleting
 473                  * route info. */
 474                 for (int level = ISIS_LEVEL1; level <= ISIS_LEVEL2; level++) {
 475                         drnode = srcdest_rnode_lookup(tables[level - 1],
 476                                                       dst_p, src_p);
 477                         if (!drnode)
 478                                 continue;
 479
 480                         route_unlock_node(drnode);
 481
 482                         if (drnode->info != rnode->info)
 483                                 continue;
 484
 485                         drnode->info = NULL;
 486                         route_unlock_node(drnode);
 487                 }
 488
 489                 isis_route_delete(area, rnode, table);
 490         }
 491 }
 492
 493 void isis_route_verify_table(struct isis_area *area, struct route_table *table)
 494 {
 495         _isis_route_verify_table(area, table, NULL);
 496 }
 497
 498 /* Function to validate route tables for L1L2 areas. In this case we can't use
 499  * level route tables directly, we have to merge them at first. L1 routes are
 500  * preferred over the L2 ones.
 501  *
 502  * Merge algorithm is trivial (at least for now). All L1 paths are copied into
 503  * merge table at first, then L2 paths are added if L1 path for same prefix
 504  * doesn't already exists there.
 505  *
 506  * FIXME: Is it right place to do it at all? Maybe we should push both levels
 507  * to the RIB with different zebra route types and let RIB handle this? */
 508 void isis_route_verify_merge(struct isis_area *area,
 509                              struct route_table *level1_table,
 510                              struct route_table *level2_table)
 511 {
 512         struct route_table *tables[] = { level1_table, level2_table };
 513         struct route_table *merge;
 514         struct route_node *rnode, *mrnode;
 515
 516         merge = srcdest_table_init();
 517
 518         for (int level = ISIS_LEVEL1; level <= ISIS_LEVEL2; level++) {
 519                 for (rnode = route_top(tables[level - 1]); rnode;
 520                      rnode = srcdest_route_next(rnode)) {
 521                         struct isis_route_info *rinfo = rnode->info;
 522                         if (!rinfo)
 523                                 continue;
 524
 525                         struct prefix *prefix;
 526                         struct prefix_ipv6 *src_p;
 527
 528                         srcdest_rnode_prefixes(rnode,
 529                                                (const struct prefix **)&prefix,
 530                                                (const struct prefix **)&src_p);
 531                         mrnode = srcdest_rnode_get(merge, prefix, src_p);
 532                         struct isis_route_info *mrinfo = mrnode->info;
 533                         if (mrinfo) {
 534                                 route_unlock_node(mrnode);
 535                                 if (CHECK_FLAG(mrinfo->flag,
 536                                                ISIS_ROUTE_FLAG_ACTIVE)) {
 537                                         /* Clear the ZEBRA_SYNCED flag on the
 538                                          * L2 route when L1 wins, otherwise L2
 539                                          * won't get reinstalled when L1
 540                                          * disappears.
 541                                          */
 542                                         UNSET_FLAG(
 543                                                 rinfo->flag,
 544                                                 ISIS_ROUTE_FLAG_ZEBRA_SYNCED
 545                                         );
 546                                         continue;
 547                                 } else if (CHECK_FLAG(rinfo->flag,
 548                                                       ISIS_ROUTE_FLAG_ACTIVE)) {
 549                                         /* Clear the ZEBRA_SYNCED flag on the L1
 550                                          * route when L2 wins, otherwise L1
 551                                          * won't get reinstalled when it
 552                                          * reappears.
 553                                          */
 554                                         UNSET_FLAG(
 555                                                 mrinfo->flag,
 556                                                 ISIS_ROUTE_FLAG_ZEBRA_SYNCED
 557                                         );
 558                                 } else if (
 559                                         CHECK_FLAG(
 560                                                 mrinfo->flag,
 561                                                 ISIS_ROUTE_FLAG_ZEBRA_SYNCED)) {
 562                                         continue;
 563                                 }
 564                         }
 565                         mrnode->info = rnode->info;
 566                 }
 567         }
 568
 569         _isis_route_verify_table(area, merge, tables);
 570         route_table_finish(merge);
 571 }
 572
 573 void isis_route_invalidate_table(struct isis_area *area,
 574                                  struct route_table *table)
 575 {
 576         struct route_node *rode;
 577         struct isis_route_info *rinfo;
 578         for (rode = route_top(table); rode; rode = srcdest_route_next(rode)) {
 579                 if (rode->info == NULL)
 580                         continue;
 581                 rinfo = rode->info;
 582
 583                 UNSET_FLAG(rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE);
 584         }
 585 }