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_attrib(struct isis_route_info *new,
 243                                        struct isis_route_info *old)
 244 {
 245         if (new->cost != old->cost)
 246                 return 0;
 247         if (new->depth != old->depth)
 248                 return 0;
 249
 250         return 1;
 251 }
 252
 253 static int isis_route_info_same(struct isis_route_info *new,
 254                                 struct isis_route_info *old, uint8_t family)
 255 {
 256         struct listnode *node;
 257         struct isis_nexthop *nexthop;
 258
 259         if (!CHECK_FLAG(old->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED))
 260                 return 0;
 261
 262         if (CHECK_FLAG(new->flag, ISIS_ROUTE_FLAG_ZEBRA_RESYNC))
 263                 return 0;
 264
 265         if (!isis_route_info_same_attrib(new, old))
 266                 return 0;
 267
 268         for (ALL_LIST_ELEMENTS_RO(new->nexthops, node, nexthop))
 269                 if (!nexthoplookup(old->nexthops, nexthop->family, &nexthop->ip,
 270                                    nexthop->ifindex))
 271                         return 0;
 272
 273         for (ALL_LIST_ELEMENTS_RO(old->nexthops, node, nexthop))
 274                 if (!nexthoplookup(new->nexthops, nexthop->family, &nexthop->ip,
 275                                    nexthop->ifindex))
 276                         return 0;
 277
 278         return 1;
 279 }
 280
 281 struct isis_route_info *isis_route_create(struct prefix *prefix,
 282                                           struct prefix_ipv6 *src_p,
 283                                           uint32_t cost,
 284                                           uint32_t depth,
 285                                           struct list *adjacencies,
 286                                           struct isis_area *area,
 287                                           struct route_table *table)
 288 {
 289         struct route_node *route_node;
 290         struct isis_route_info *rinfo_new, *rinfo_old, *route_info = NULL;
 291         char buff[PREFIX2STR_BUFFER];
 292         uint8_t family;
 293
 294         family = prefix->family;
 295         /* for debugs */
 296         prefix2str(prefix, buff, sizeof(buff));
 297
 298         if (!table)
 299                 return NULL;
 300
 301         rinfo_new = isis_route_info_new(prefix, src_p, cost,
 302                                         depth, adjacencies);
 303         route_node = srcdest_rnode_get(table, prefix, src_p);
 304
 305         rinfo_old = route_node->info;
 306         if (!rinfo_old) {
 307                 if (IS_DEBUG_RTE_EVENTS)
 308                         zlog_debug("ISIS-Rte (%s) route created: %s",
 309                                    area->area_tag, buff);
 310                 route_info = rinfo_new;
 311                 UNSET_FLAG(route_info->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED);
 312         } else {
 313                 route_unlock_node(route_node);
 314                 if (IS_DEBUG_RTE_EVENTS)
 315                         zlog_debug("ISIS-Rte (%s) route already exists: %s",
 316                                    area->area_tag, buff);
 317                 if (isis_route_info_same(rinfo_new, rinfo_old, family)) {
 318                         if (IS_DEBUG_RTE_EVENTS)
 319                                 zlog_debug("ISIS-Rte (%s) route unchanged: %s",
 320                                            area->area_tag, buff);
 321                         isis_route_info_delete(rinfo_new);
 322                         route_info = rinfo_old;
 323                 } else {
 324                         if (IS_DEBUG_RTE_EVENTS)
 325                                 zlog_debug("ISIS-Rte (%s) route changed: %s",
 326                                            area->area_tag, buff);
 327                         isis_route_info_delete(rinfo_old);
 328                         route_info = rinfo_new;
 329                         UNSET_FLAG(route_info->flag,
 330                                    ISIS_ROUTE_FLAG_ZEBRA_SYNCED);
 331                 }
 332         }
 333
 334         SET_FLAG(route_info->flag, ISIS_ROUTE_FLAG_ACTIVE);
 335         route_node->info = route_info;
 336
 337         return route_info;
 338 }
 339
 340 static void isis_route_delete(struct isis_area *area, struct route_node *rode,
 341                               struct route_table *table)
 342 {
 343         struct isis_route_info *rinfo;
 344         char buff[SRCDEST2STR_BUFFER];
 345         struct prefix *prefix;
 346         struct prefix_ipv6 *src_p;
 347
 348         /* for log */
 349         srcdest_rnode2str(rode, buff, sizeof(buff));
 350
 351         srcdest_rnode_prefixes(rode, (const struct prefix **)&prefix,
 352                                (const struct prefix **)&src_p);
 353
 354         rinfo = rode->info;
 355         if (rinfo == NULL) {
 356                 if (IS_DEBUG_RTE_EVENTS)
 357                         zlog_debug(
 358                                 "ISIS-Rte: tried to delete non-existant route %s",
 359                                 buff);
 360                 return;
 361         }
 362
 363         if (CHECK_FLAG(rinfo->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED)) {
 364                 UNSET_FLAG(rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE);
 365                 if (IS_DEBUG_RTE_EVENTS)
 366                         zlog_debug("ISIS-Rte: route delete  %s", buff);
 367                 isis_route_update(area, prefix, src_p, rinfo);
 368         }
 369         isis_route_info_delete(rinfo);
 370         rode->info = NULL;
 371         route_unlock_node(rode);
 372 }
 373
 374 static void isis_route_update(struct isis_area *area, struct prefix *prefix,
 375                               struct prefix_ipv6 *src_p,
 376                               struct isis_route_info *route_info)
 377 {
 378         if (CHECK_FLAG(route_info->flag, ISIS_ROUTE_FLAG_ACTIVE)) {
 379                 if (CHECK_FLAG(route_info->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED))
 380                         return;
 381
 382                 isis_zebra_route_add_route(area->isis, prefix, src_p, route_info);
 383                 hook_call(isis_route_update_hook, area, prefix, route_info);
 384
 385                 SET_FLAG(route_info->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED);
 386                 UNSET_FLAG(route_info->flag, ISIS_ROUTE_FLAG_ZEBRA_RESYNC);
 387         } else {
 388                 if (!CHECK_FLAG(route_info->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED))
 389                         return;
 390
 391                 isis_zebra_route_del_route(area->isis, prefix, src_p, route_info);
 392                 hook_call(isis_route_update_hook, area, prefix, route_info);
 393
 394                 UNSET_FLAG(route_info->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED);
 395         }
 396 }
 397
 398 static void _isis_route_verify_table(struct isis_area *area,
 399                                      struct route_table *table,
 400                                      struct route_table **tables)
 401 {
 402         struct route_node *rnode, *drnode;
 403         struct isis_route_info *rinfo;
 404         char buff[SRCDEST2STR_BUFFER];
 405
 406         for (rnode = route_top(table); rnode;
 407              rnode = srcdest_route_next(rnode)) {
 408                 if (rnode->info == NULL)
 409                         continue;
 410                 rinfo = rnode->info;
 411
 412                 struct prefix *dst_p;
 413                 struct prefix_ipv6 *src_p;
 414
 415                 srcdest_rnode_prefixes(rnode,
 416                                        (const struct prefix **)&dst_p,
 417                                        (const struct prefix **)&src_p);
 418
 419                 if (IS_DEBUG_RTE_EVENTS) {
 420                         srcdest2str(dst_p, src_p, buff, sizeof(buff));
 421                         zlog_debug(
 422                                 "ISIS-Rte (%s): route validate: %s %s %s %s",
 423                                 area->area_tag,
 424                                 (CHECK_FLAG(rinfo->flag,
 425                                             ISIS_ROUTE_FLAG_ZEBRA_SYNCED)
 426                                          ? "synced"
 427                                          : "not-synced"),
 428                                 (CHECK_FLAG(rinfo->flag,
 429                                             ISIS_ROUTE_FLAG_ZEBRA_RESYNC)
 430                                          ? "resync"
 431                                          : "not-resync"),
 432                                 (CHECK_FLAG(rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE)
 433                                          ? "active"
 434                                          : "inactive"),
 435                                 buff);
 436                 }
 437
 438                 isis_route_update(area, dst_p, src_p, rinfo);
 439
 440                 if (CHECK_FLAG(rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE))
 441                         continue;
 442
 443                 /* Area is either L1 or L2 => we use level route tables
 444                  * directly for
 445                  * validating => no problems with deleting routes. */
 446                 if (!tables) {
 447                         isis_route_delete(area, rnode, table);
 448                         continue;
 449                 }
 450
 451                 /* If area is L1L2, we work with merge table and
 452                  * therefore must
 453                  * delete node from level tables as well before deleting
 454                  * route info. */
 455                 for (int level = ISIS_LEVEL1; level <= ISIS_LEVEL2; level++) {
 456                         drnode = srcdest_rnode_lookup(tables[level - 1],
 457                                                       dst_p, src_p);
 458                         if (!drnode)
 459                                 continue;
 460
 461                         route_unlock_node(drnode);
 462
 463                         if (drnode->info != rnode->info)
 464                                 continue;
 465
 466                         drnode->info = NULL;
 467                         route_unlock_node(drnode);
 468                 }
 469
 470                 isis_route_delete(area, rnode, table);
 471         }
 472 }
 473
 474 void isis_route_verify_table(struct isis_area *area, struct route_table *table)
 475 {
 476         _isis_route_verify_table(area, table, NULL);
 477 }
 478
 479 /* Function to validate route tables for L1L2 areas. In this case we can't use
 480  * level route tables directly, we have to merge them at first. L1 routes are
 481  * preferred over the L2 ones.
 482  *
 483  * Merge algorithm is trivial (at least for now). All L1 paths are copied into
 484  * merge table at first, then L2 paths are added if L1 path for same prefix
 485  * doesn't already exists there.
 486  *
 487  * FIXME: Is it right place to do it at all? Maybe we should push both levels
 488  * to the RIB with different zebra route types and let RIB handle this? */
 489 void isis_route_verify_merge(struct isis_area *area,
 490                              struct route_table *level1_table,
 491                              struct route_table *level2_table)
 492 {
 493         struct route_table *tables[] = { level1_table, level2_table };
 494         struct route_table *merge;
 495         struct route_node *rnode, *mrnode;
 496
 497         merge = srcdest_table_init();
 498
 499         for (int level = ISIS_LEVEL1; level <= ISIS_LEVEL2; level++) {
 500                 for (rnode = route_top(tables[level - 1]); rnode;
 501                      rnode = srcdest_route_next(rnode)) {
 502                         struct isis_route_info *rinfo = rnode->info;
 503                         if (!rinfo)
 504                                 continue;
 505
 506                         struct prefix *prefix;
 507                         struct prefix_ipv6 *src_p;
 508
 509                         srcdest_rnode_prefixes(rnode,
 510                                                (const struct prefix **)&prefix,
 511                                                (const struct prefix **)&src_p);
 512                         mrnode = srcdest_rnode_get(merge, prefix, src_p);
 513                         struct isis_route_info *mrinfo = mrnode->info;
 514                         if (mrinfo) {
 515                                 route_unlock_node(mrnode);
 516                                 if (CHECK_FLAG(mrinfo->flag,
 517                                                ISIS_ROUTE_FLAG_ACTIVE)) {
 518                                         /* Clear the ZEBRA_SYNCED flag on the
 519                                          * L2 route when L1 wins, otherwise L2
 520                                          * won't get reinstalled when L1
 521                                          * disappears.
 522                                          */
 523                                         UNSET_FLAG(
 524                                                 rinfo->flag,
 525                                                 ISIS_ROUTE_FLAG_ZEBRA_SYNCED
 526                                         );
 527                                         continue;
 528                                 } else if (CHECK_FLAG(rinfo->flag,
 529                                                       ISIS_ROUTE_FLAG_ACTIVE)) {
 530                                         /* Clear the ZEBRA_SYNCED flag on the L1
 531                                          * route when L2 wins, otherwise L1
 532                                          * won't get reinstalled when it
 533                                          * reappears.
 534                                          */
 535                                         UNSET_FLAG(
 536                                                 mrinfo->flag,
 537                                                 ISIS_ROUTE_FLAG_ZEBRA_SYNCED
 538                                         );
 539                                 } else if (
 540                                         CHECK_FLAG(
 541                                                 mrinfo->flag,
 542                                                 ISIS_ROUTE_FLAG_ZEBRA_SYNCED)) {
 543                                         continue;
 544                                 }
 545                         }
 546                         mrnode->info = rnode->info;
 547                 }
 548         }
 549
 550         _isis_route_verify_table(area, merge, tables);
 551         route_table_finish(merge);
 552 }
 553
 554 void isis_route_invalidate_table(struct isis_area *area,
 555                                  struct route_table *table)
 556 {
 557         struct route_node *rode;
 558         struct isis_route_info *rinfo;
 559         for (rode = route_top(table); rode; rode = srcdest_route_next(rode)) {
 560                 if (rode->info == NULL)
 561                         continue;
 562                 rinfo = rode->info;
 563
 564                 UNSET_FLAG(rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE);
 565         }
 566 }