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 "memory.h"
  32 #include "prefix.h"
  33 #include "hash.h"
  34 #include "if.h"
  35 #include "table.h"
  36 #include "srcdest_table.h"
  37
  38 #include "isis_constants.h"
  39 #include "isis_common.h"
  40 #include "isis_flags.h"
  41 #include "dict.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_route.h"
  50 #include "isis_zebra.h"
  51
  52 static struct isis_nexthop *isis_nexthop_create(struct in_addr *ip,
  53                                                 ifindex_t ifindex)
  54 {
  55         struct listnode *node;
  56         struct isis_nexthop *nexthop;
  57
  58         for (ALL_LIST_ELEMENTS_RO(isis->nexthops, node, nexthop)) {
  59                 if (nexthop->ifindex != ifindex)
  60                         continue;
  61                 if (ip && memcmp(&nexthop->ip, ip, sizeof(struct in_addr)) != 0)
  62                         continue;
  63
  64                 nexthop->lock++;
  65                 return nexthop;
  66         }
  67
  68         nexthop = XCALLOC(MTYPE_ISIS_NEXTHOP, sizeof(struct isis_nexthop));
  69
  70         nexthop->ifindex = ifindex;
  71         memcpy(&nexthop->ip, ip, sizeof(struct in_addr));
  72         listnode_add(isis->nexthops, nexthop);
  73         nexthop->lock++;
  74
  75         return nexthop;
  76 }
  77
  78 static void isis_nexthop_delete(struct isis_nexthop *nexthop)
  79 {
  80         nexthop->lock--;
  81         if (nexthop->lock == 0) {
  82                 listnode_delete(isis->nexthops, nexthop);
  83                 XFREE(MTYPE_ISIS_NEXTHOP, nexthop);
  84         }
  85
  86         return;
  87 }
  88
  89 static int nexthoplookup(struct list *nexthops, struct in_addr *ip,
  90                          ifindex_t ifindex)
  91 {
  92         struct listnode *node;
  93         struct isis_nexthop *nh;
  94
  95         for (ALL_LIST_ELEMENTS_RO(nexthops, node, nh)) {
  96                 if (!(memcmp(ip, &nh->ip, sizeof(struct in_addr)))
  97                     && ifindex == nh->ifindex)
  98                         return 1;
  99         }
 100
 101         return 0;
 102 }
 103
 104 static struct isis_nexthop6 *isis_nexthop6_new(struct in6_addr *ip6,
 105                                                ifindex_t ifindex)
 106 {
 107         struct isis_nexthop6 *nexthop6;
 108
 109         nexthop6 = XCALLOC(MTYPE_ISIS_NEXTHOP6, sizeof(struct isis_nexthop6));
 110
 111         nexthop6->ifindex = ifindex;
 112         memcpy(&nexthop6->ip6, ip6, sizeof(struct in6_addr));
 113         nexthop6->lock++;
 114
 115         return nexthop6;
 116 }
 117
 118 static struct isis_nexthop6 *isis_nexthop6_create(struct in6_addr *ip6,
 119                                                   ifindex_t ifindex)
 120 {
 121         struct listnode *node;
 122         struct isis_nexthop6 *nexthop6;
 123
 124         for (ALL_LIST_ELEMENTS_RO(isis->nexthops6, node, nexthop6)) {
 125                 if (nexthop6->ifindex != ifindex)
 126                         continue;
 127                 if (ip6
 128                     && memcmp(&nexthop6->ip6, ip6, sizeof(struct in6_addr))
 129                                != 0)
 130                         continue;
 131
 132                 nexthop6->lock++;
 133                 return nexthop6;
 134         }
 135
 136         nexthop6 = isis_nexthop6_new(ip6, ifindex);
 137
 138         return nexthop6;
 139 }
 140
 141 static void isis_nexthop6_delete(struct isis_nexthop6 *nexthop6)
 142 {
 143
 144         nexthop6->lock--;
 145         if (nexthop6->lock == 0) {
 146                 listnode_delete(isis->nexthops6, nexthop6);
 147                 XFREE(MTYPE_ISIS_NEXTHOP6, nexthop6);
 148         }
 149
 150         return;
 151 }
 152
 153 static int nexthop6lookup(struct list *nexthops6, struct in6_addr *ip6,
 154                           ifindex_t ifindex)
 155 {
 156         struct listnode *node;
 157         struct isis_nexthop6 *nh6;
 158
 159         for (ALL_LIST_ELEMENTS_RO(nexthops6, node, nh6)) {
 160                 if (!(memcmp(ip6, &nh6->ip6, sizeof(struct in6_addr)))
 161                     && ifindex == nh6->ifindex)
 162                         return 1;
 163         }
 164
 165         return 0;
 166 }
 167
 168 static void adjinfo2nexthop(struct list *nexthops, struct isis_adjacency *adj)
 169 {
 170         struct isis_nexthop *nh;
 171
 172         for (unsigned int i = 0; i < adj->ipv4_address_count; i++) {
 173                 struct in_addr *ipv4_addr = &adj->ipv4_addresses[i];
 174                 if (!nexthoplookup(nexthops, ipv4_addr,
 175                                    adj->circuit->interface->ifindex)) {
 176                         nh = isis_nexthop_create(
 177                                 ipv4_addr, adj->circuit->interface->ifindex);
 178                         nh->router_address = adj->router_address;
 179                         listnode_add(nexthops, nh);
 180                         return;
 181                 }
 182         }
 183 }
 184
 185 static void adjinfo2nexthop6(struct list *nexthops6, struct isis_adjacency *adj)
 186 {
 187         struct isis_nexthop6 *nh6;
 188
 189         for (unsigned int i = 0; i < adj->ipv6_address_count; i++) {
 190                 struct in6_addr *ipv6_addr = &adj->ipv6_addresses[i];
 191                 if (!nexthop6lookup(nexthops6, ipv6_addr,
 192                                     adj->circuit->interface->ifindex)) {
 193                         nh6 = isis_nexthop6_create(
 194                                 ipv6_addr, adj->circuit->interface->ifindex);
 195                         nh6->router_address6 = adj->router_address6;
 196                         listnode_add(nexthops6, nh6);
 197                         return;
 198                 }
 199         }
 200 }
 201
 202 static struct isis_route_info *isis_route_info_new(struct prefix *prefix,
 203                                                    struct prefix_ipv6 *src_p,
 204                                                    uint32_t cost,
 205                                                    uint32_t depth,
 206                                                    struct list *adjacencies)
 207 {
 208         struct isis_route_info *rinfo;
 209         struct isis_adjacency *adj;
 210         struct listnode *node;
 211
 212         rinfo = XCALLOC(MTYPE_ISIS_ROUTE_INFO, sizeof(struct isis_route_info));
 213
 214         if (prefix->family == AF_INET) {
 215                 rinfo->nexthops = list_new();
 216                 for (ALL_LIST_ELEMENTS_RO(adjacencies, node, adj)) {
 217                         /* check for force resync this route */
 218                         if (CHECK_FLAG(adj->circuit->flags,
 219                                        ISIS_CIRCUIT_FLAPPED_AFTER_SPF))
 220                                 SET_FLAG(rinfo->flag,
 221                                          ISIS_ROUTE_FLAG_ZEBRA_RESYNC);
 222                         /* update neighbor router address */
 223                         if (depth == 2 && prefix->prefixlen == 32)
 224                                 adj->router_address = prefix->u.prefix4;
 225                         adjinfo2nexthop(rinfo->nexthops, adj);
 226                 }
 227         }
 228         if (prefix->family == AF_INET6) {
 229                 rinfo->nexthops6 = list_new();
 230                 for (ALL_LIST_ELEMENTS_RO(adjacencies, node, adj)) {
 231                         /* check for force resync this route */
 232                         if (CHECK_FLAG(adj->circuit->flags,
 233                                        ISIS_CIRCUIT_FLAPPED_AFTER_SPF))
 234                                 SET_FLAG(rinfo->flag,
 235                                          ISIS_ROUTE_FLAG_ZEBRA_RESYNC);
 236                         /* update neighbor router address */
 237                         if (depth == 2 && prefix->prefixlen == 128
 238                             && (!src_p || !src_p->prefixlen)) {
 239                                 adj->router_address6 = prefix->u.prefix6;
 240                         }
 241                         adjinfo2nexthop6(rinfo->nexthops6, adj);
 242                 }
 243         }
 244
 245         rinfo->cost = cost;
 246         rinfo->depth = depth;
 247
 248         return rinfo;
 249 }
 250
 251 static void isis_route_info_delete(struct isis_route_info *route_info)
 252 {
 253         if (route_info->nexthops) {
 254                 route_info->nexthops->del =
 255                         (void (*)(void *))isis_nexthop_delete;
 256                 list_delete(&route_info->nexthops);
 257         }
 258
 259         if (route_info->nexthops6) {
 260                 route_info->nexthops6->del =
 261                         (void (*)(void *))isis_nexthop6_delete;
 262                 list_delete(&route_info->nexthops6);
 263         }
 264
 265         XFREE(MTYPE_ISIS_ROUTE_INFO, route_info);
 266 }
 267
 268 static int isis_route_info_same_attrib(struct isis_route_info *new,
 269                                        struct isis_route_info *old)
 270 {
 271         if (new->cost != old->cost)
 272                 return 0;
 273         if (new->depth != old->depth)
 274                 return 0;
 275
 276         return 1;
 277 }
 278
 279 static int isis_route_info_same(struct isis_route_info *new,
 280                                 struct isis_route_info *old, uint8_t family)
 281 {
 282         struct listnode *node;
 283         struct isis_nexthop *nexthop;
 284         struct isis_nexthop6 *nexthop6;
 285
 286         if (!CHECK_FLAG(old->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED))
 287                 return 0;
 288
 289         if (CHECK_FLAG(new->flag, ISIS_ROUTE_FLAG_ZEBRA_RESYNC))
 290                 return 0;
 291
 292         if (!isis_route_info_same_attrib(new, old))
 293                 return 0;
 294
 295         if (family == AF_INET) {
 296                 for (ALL_LIST_ELEMENTS_RO(new->nexthops, node, nexthop))
 297                         if (nexthoplookup(old->nexthops, &nexthop->ip,
 298                                           nexthop->ifindex)
 299                             == 0)
 300                                 return 0;
 301
 302                 for (ALL_LIST_ELEMENTS_RO(old->nexthops, node, nexthop))
 303                         if (nexthoplookup(new->nexthops, &nexthop->ip,
 304                                           nexthop->ifindex)
 305                             == 0)
 306                                 return 0;
 307         } else if (family == AF_INET6) {
 308                 for (ALL_LIST_ELEMENTS_RO(new->nexthops6, node, nexthop6))
 309                         if (nexthop6lookup(old->nexthops6, &nexthop6->ip6,
 310                                            nexthop6->ifindex)
 311                             == 0)
 312                                 return 0;
 313
 314                 for (ALL_LIST_ELEMENTS_RO(old->nexthops6, node, nexthop6))
 315                         if (nexthop6lookup(new->nexthops6, &nexthop6->ip6,
 316                                            nexthop6->ifindex)
 317                             == 0)
 318                                 return 0;
 319         }
 320
 321         return 1;
 322 }
 323
 324 struct isis_route_info *isis_route_create(struct prefix *prefix,
 325                                           struct prefix_ipv6 *src_p,
 326                                           uint32_t cost,
 327                                           uint32_t depth,
 328                                           struct list *adjacencies,
 329                                           struct isis_area *area,
 330                                           struct route_table *table)
 331 {
 332         struct route_node *route_node;
 333         struct isis_route_info *rinfo_new, *rinfo_old, *route_info = NULL;
 334         char buff[PREFIX2STR_BUFFER];
 335         uint8_t family;
 336
 337         family = prefix->family;
 338         /* for debugs */
 339         prefix2str(prefix, buff, sizeof(buff));
 340
 341         if (!table)
 342                 return NULL;
 343
 344         rinfo_new = isis_route_info_new(prefix, src_p, cost,
 345                                         depth, adjacencies);
 346         route_node = srcdest_rnode_get(table, prefix, src_p);
 347
 348         rinfo_old = route_node->info;
 349         if (!rinfo_old) {
 350                 if (isis->debugs & DEBUG_RTE_EVENTS)
 351                         zlog_debug("ISIS-Rte (%s) route created: %s",
 352                                    area->area_tag, buff);
 353                 route_info = rinfo_new;
 354                 UNSET_FLAG(route_info->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED);
 355         } else {
 356                 route_unlock_node(route_node);
 357                 if (isis->debugs & DEBUG_RTE_EVENTS)
 358                         zlog_debug("ISIS-Rte (%s) route already exists: %s",
 359                                    area->area_tag, buff);
 360                 if (isis_route_info_same(rinfo_new, rinfo_old, family)) {
 361                         if (isis->debugs & DEBUG_RTE_EVENTS)
 362                                 zlog_debug("ISIS-Rte (%s) route unchanged: %s",
 363                                            area->area_tag, buff);
 364                         isis_route_info_delete(rinfo_new);
 365                         route_info = rinfo_old;
 366                 } else {
 367                         if (isis->debugs & DEBUG_RTE_EVENTS)
 368                                 zlog_debug("ISIS-Rte (%s) route changed: %s",
 369                                            area->area_tag, buff);
 370                         isis_route_info_delete(rinfo_old);
 371                         route_info = rinfo_new;
 372                         UNSET_FLAG(route_info->flag,
 373                                    ISIS_ROUTE_FLAG_ZEBRA_SYNCED);
 374                 }
 375         }
 376
 377         SET_FLAG(route_info->flag, ISIS_ROUTE_FLAG_ACTIVE);
 378         route_node->info = route_info;
 379
 380         return route_info;
 381 }
 382
 383 static void isis_route_delete(struct route_node *rode,
 384                               struct route_table *table)
 385 {
 386         struct isis_route_info *rinfo;
 387         char buff[SRCDEST2STR_BUFFER];
 388         struct prefix *prefix;
 389         struct prefix_ipv6 *src_p;
 390
 391         /* for log */
 392         srcdest_rnode2str(rode, buff, sizeof(buff));
 393
 394         srcdest_rnode_prefixes(rode, (const struct prefix **)&prefix,
 395                                (const struct prefix **)&src_p);
 396
 397         rinfo = rode->info;
 398         if (rinfo == NULL) {
 399                 if (isis->debugs & DEBUG_RTE_EVENTS)
 400                         zlog_debug(
 401                                 "ISIS-Rte: tried to delete non-existant route %s",
 402                                 buff);
 403                 return;
 404         }
 405
 406         if (CHECK_FLAG(rinfo->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED)) {
 407                 UNSET_FLAG(rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE);
 408                 if (isis->debugs & DEBUG_RTE_EVENTS)
 409                         zlog_debug("ISIS-Rte: route delete  %s", buff);
 410                 isis_zebra_route_update(prefix, src_p, rinfo);
 411         }
 412         isis_route_info_delete(rinfo);
 413         rode->info = NULL;
 414         route_unlock_node(rode);
 415 }
 416
 417 static void _isis_route_verify_table(struct isis_area *area,
 418                                      struct route_table *table,
 419                                      struct route_table **tables)
 420 {
 421         struct route_node *rnode, *drnode;
 422         struct isis_route_info *rinfo;
 423         char buff[SRCDEST2STR_BUFFER];
 424
 425         for (rnode = route_top(table); rnode;
 426              rnode = srcdest_route_next(rnode)) {
 427                 if (rnode->info == NULL)
 428                         continue;
 429                 rinfo = rnode->info;
 430
 431                 struct prefix *dst_p;
 432                 struct prefix_ipv6 *src_p;
 433
 434                 srcdest_rnode_prefixes(rnode,
 435                                        (const struct prefix **)&dst_p,
 436                                        (const struct prefix **)&src_p);
 437
 438                 if (isis->debugs & DEBUG_RTE_EVENTS) {
 439                         srcdest2str(dst_p, src_p, buff, sizeof(buff));
 440                         zlog_debug(
 441                                 "ISIS-Rte (%s): route validate: %s %s %s %s",
 442                                 area->area_tag,
 443                                 (CHECK_FLAG(rinfo->flag,
 444                                             ISIS_ROUTE_FLAG_ZEBRA_SYNCED)
 445                                          ? "synced"
 446                                          : "not-synced"),
 447                                 (CHECK_FLAG(rinfo->flag,
 448                                             ISIS_ROUTE_FLAG_ZEBRA_RESYNC)
 449                                          ? "resync"
 450                                          : "not-resync"),
 451                                 (CHECK_FLAG(rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE)
 452                                          ? "active"
 453                                          : "inactive"),
 454                                 buff);
 455                 }
 456
 457                 isis_zebra_route_update(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(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(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 {
 548                                         /* Clear the ZEBRA_SYNCED flag on the L1
 549                                          * route when L2 wins, otherwise L1
 550                                          * won't get reinstalled when it
 551                                          * reappears.
 552                                          */
 553                                         UNSET_FLAG(
 554                                                 mrinfo->flag,
 555                                                 ISIS_ROUTE_FLAG_ZEBRA_SYNCED
 556                                         );
 557                                 }
 558                         }
 559                         mrnode->info = rnode->info;
 560                 }
 561         }
 562
 563         _isis_route_verify_table(area, merge, tables);
 564         route_table_finish(merge);
 565 }
 566
 567 void isis_route_invalidate_table(struct isis_area *area,
 568                                  struct route_table *table)
 569 {
 570         struct route_node *rode;
 571         struct isis_route_info *rinfo;
 572         for (rode = route_top(table); rode; rode = srcdest_route_next(rode)) {
 573                 if (rode->info == NULL)
 574                         continue;
 575                 rinfo = rode->info;
 576
 577                 UNSET_FLAG(rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE);
 578         }
 579 }