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 "isisd.h"
  42 #include "isis_misc.h"
  43 #include "isis_adjacency.h"
  44 #include "isis_circuit.h"
  45 #include "isis_pdu.h"
  46 #include "isis_lsp.h"
  47 #include "isis_spf.h"
  48 #include "isis_route.h"
  49 #include "isis_zebra.h"
  50
  51 static struct isis_nexthop *isis_nexthop_create(struct in_addr *ip,
  52                                                 ifindex_t ifindex)
  53 {
  54         struct listnode *node;
  55         struct isis_nexthop *nexthop;
  56
  57         for (ALL_LIST_ELEMENTS_RO(isis->nexthops, node, nexthop)) {
  58                 if (nexthop->ifindex != ifindex)
  59                         continue;
  60                 if (ip && memcmp(&nexthop->ip, ip, sizeof(struct in_addr)) != 0)
  61                         continue;
  62
  63                 nexthop->lock++;
  64                 return nexthop;
  65         }
  66
  67         nexthop = XCALLOC(MTYPE_ISIS_NEXTHOP, sizeof(struct isis_nexthop));
  68
  69         nexthop->ifindex = ifindex;
  70         memcpy(&nexthop->ip, ip, sizeof(struct in_addr));
  71         listnode_add(isis->nexthops, nexthop);
  72         nexthop->lock++;
  73
  74         return nexthop;
  75 }
  76
  77 static void isis_nexthop_delete(struct isis_nexthop *nexthop)
  78 {
  79         nexthop->lock--;
  80         if (nexthop->lock == 0) {
  81                 listnode_delete(isis->nexthops, nexthop);
  82                 XFREE(MTYPE_ISIS_NEXTHOP, nexthop);
  83         }
  84
  85         return;
  86 }
  87
  88 static int nexthoplookup(struct list *nexthops, struct in_addr *ip,
  89                          ifindex_t ifindex)
  90 {
  91         struct listnode *node;
  92         struct isis_nexthop *nh;
  93
  94         for (ALL_LIST_ELEMENTS_RO(nexthops, node, nh)) {
  95                 if (!(memcmp(ip, &nh->ip, sizeof(struct in_addr)))
  96                     && ifindex == nh->ifindex)
  97                         return 1;
  98         }
  99
 100         return 0;
 101 }
 102
 103 static struct isis_nexthop6 *isis_nexthop6_new(struct in6_addr *ip6,
 104                                                ifindex_t ifindex)
 105 {
 106         struct isis_nexthop6 *nexthop6;
 107
 108         nexthop6 = XCALLOC(MTYPE_ISIS_NEXTHOP6, sizeof(struct isis_nexthop6));
 109
 110         nexthop6->ifindex = ifindex;
 111         memcpy(&nexthop6->ip6, ip6, sizeof(struct in6_addr));
 112         nexthop6->lock++;
 113
 114         return nexthop6;
 115 }
 116
 117 static struct isis_nexthop6 *isis_nexthop6_create(struct in6_addr *ip6,
 118                                                   ifindex_t ifindex)
 119 {
 120         struct listnode *node;
 121         struct isis_nexthop6 *nexthop6;
 122
 123         for (ALL_LIST_ELEMENTS_RO(isis->nexthops6, node, nexthop6)) {
 124                 if (nexthop6->ifindex != ifindex)
 125                         continue;
 126                 if (ip6
 127                     && memcmp(&nexthop6->ip6, ip6, sizeof(struct in6_addr))
 128                                != 0)
 129                         continue;
 130
 131                 nexthop6->lock++;
 132                 return nexthop6;
 133         }
 134
 135         nexthop6 = isis_nexthop6_new(ip6, ifindex);
 136
 137         return nexthop6;
 138 }
 139
 140 static void isis_nexthop6_delete(struct isis_nexthop6 *nexthop6)
 141 {
 142
 143         nexthop6->lock--;
 144         if (nexthop6->lock == 0) {
 145                 listnode_delete(isis->nexthops6, nexthop6);
 146                 XFREE(MTYPE_ISIS_NEXTHOP6, nexthop6);
 147         }
 148
 149         return;
 150 }
 151
 152 static int nexthop6lookup(struct list *nexthops6, struct in6_addr *ip6,
 153                           ifindex_t ifindex)
 154 {
 155         struct listnode *node;
 156         struct isis_nexthop6 *nh6;
 157
 158         for (ALL_LIST_ELEMENTS_RO(nexthops6, node, nh6)) {
 159                 if (!(memcmp(ip6, &nh6->ip6, sizeof(struct in6_addr)))
 160                     && ifindex == nh6->ifindex)
 161                         return 1;
 162         }
 163
 164         return 0;
 165 }
 166
 167 static void adjinfo2nexthop(struct list *nexthops, struct isis_adjacency *adj)
 168 {
 169         struct isis_nexthop *nh;
 170
 171         for (unsigned int i = 0; i < adj->ipv4_address_count; i++) {
 172                 struct in_addr *ipv4_addr = &adj->ipv4_addresses[i];
 173                 if (!nexthoplookup(nexthops, ipv4_addr,
 174                                    adj->circuit->interface->ifindex)) {
 175                         nh = isis_nexthop_create(
 176                                 ipv4_addr, adj->circuit->interface->ifindex);
 177                         nh->router_address = adj->router_address;
 178                         listnode_add(nexthops, nh);
 179                         return;
 180                 }
 181         }
 182 }
 183
 184 static void adjinfo2nexthop6(struct list *nexthops6, struct isis_adjacency *adj)
 185 {
 186         struct isis_nexthop6 *nh6;
 187
 188         for (unsigned int i = 0; i < adj->ipv6_address_count; i++) {
 189                 struct in6_addr *ipv6_addr = &adj->ipv6_addresses[i];
 190                 if (!nexthop6lookup(nexthops6, ipv6_addr,
 191                                     adj->circuit->interface->ifindex)) {
 192                         nh6 = isis_nexthop6_create(
 193                                 ipv6_addr, adj->circuit->interface->ifindex);
 194                         nh6->router_address6 = adj->router_address6;
 195                         listnode_add(nexthops6, nh6);
 196                         return;
 197                 }
 198         }
 199 }
 200
 201 static struct isis_route_info *isis_route_info_new(struct prefix *prefix,
 202                                                    struct prefix_ipv6 *src_p,
 203                                                    uint32_t cost,
 204                                                    uint32_t depth,
 205                                                    struct list *adjacencies)
 206 {
 207         struct isis_route_info *rinfo;
 208         struct isis_adjacency *adj;
 209         struct listnode *node;
 210
 211         rinfo = XCALLOC(MTYPE_ISIS_ROUTE_INFO, sizeof(struct isis_route_info));
 212
 213         if (prefix->family == AF_INET) {
 214                 rinfo->nexthops = list_new();
 215                 for (ALL_LIST_ELEMENTS_RO(adjacencies, node, adj)) {
 216                         /* check for force resync this route */
 217                         if (CHECK_FLAG(adj->circuit->flags,
 218                                        ISIS_CIRCUIT_FLAPPED_AFTER_SPF))
 219                                 SET_FLAG(rinfo->flag,
 220                                          ISIS_ROUTE_FLAG_ZEBRA_RESYNC);
 221                         /* update neighbor router address */
 222                         if (depth == 2 && prefix->prefixlen == 32)
 223                                 adj->router_address = prefix->u.prefix4;
 224                         adjinfo2nexthop(rinfo->nexthops, adj);
 225                 }
 226         }
 227         if (prefix->family == AF_INET6) {
 228                 rinfo->nexthops6 = list_new();
 229                 for (ALL_LIST_ELEMENTS_RO(adjacencies, node, adj)) {
 230                         /* check for force resync this route */
 231                         if (CHECK_FLAG(adj->circuit->flags,
 232                                        ISIS_CIRCUIT_FLAPPED_AFTER_SPF))
 233                                 SET_FLAG(rinfo->flag,
 234                                          ISIS_ROUTE_FLAG_ZEBRA_RESYNC);
 235                         /* update neighbor router address */
 236                         if (depth == 2 && prefix->prefixlen == 128
 237                             && (!src_p || !src_p->prefixlen)) {
 238                                 adj->router_address6 = prefix->u.prefix6;
 239                         }
 240                         adjinfo2nexthop6(rinfo->nexthops6, adj);
 241                 }
 242         }
 243
 244         rinfo->cost = cost;
 245         rinfo->depth = depth;
 246
 247         return rinfo;
 248 }
 249
 250 static void isis_route_info_delete(struct isis_route_info *route_info)
 251 {
 252         if (route_info->nexthops) {
 253                 route_info->nexthops->del =
 254                         (void (*)(void *))isis_nexthop_delete;
 255                 list_delete(&route_info->nexthops);
 256         }
 257
 258         if (route_info->nexthops6) {
 259                 route_info->nexthops6->del =
 260                         (void (*)(void *))isis_nexthop6_delete;
 261                 list_delete(&route_info->nexthops6);
 262         }
 263
 264         XFREE(MTYPE_ISIS_ROUTE_INFO, route_info);
 265 }
 266
 267 static int isis_route_info_same_attrib(struct isis_route_info *new,
 268                                        struct isis_route_info *old)
 269 {
 270         if (new->cost != old->cost)
 271                 return 0;
 272         if (new->depth != old->depth)
 273                 return 0;
 274
 275         return 1;
 276 }
 277
 278 static int isis_route_info_same(struct isis_route_info *new,
 279                                 struct isis_route_info *old, uint8_t family)
 280 {
 281         struct listnode *node;
 282         struct isis_nexthop *nexthop;
 283         struct isis_nexthop6 *nexthop6;
 284
 285         if (!CHECK_FLAG(old->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED))
 286                 return 0;
 287
 288         if (CHECK_FLAG(new->flag, ISIS_ROUTE_FLAG_ZEBRA_RESYNC))
 289                 return 0;
 290
 291         if (!isis_route_info_same_attrib(new, old))
 292                 return 0;
 293
 294         if (family == AF_INET) {
 295                 for (ALL_LIST_ELEMENTS_RO(new->nexthops, node, nexthop))
 296                         if (nexthoplookup(old->nexthops, &nexthop->ip,
 297                                           nexthop->ifindex)
 298                             == 0)
 299                                 return 0;
 300
 301                 for (ALL_LIST_ELEMENTS_RO(old->nexthops, node, nexthop))
 302                         if (nexthoplookup(new->nexthops, &nexthop->ip,
 303                                           nexthop->ifindex)
 304                             == 0)
 305                                 return 0;
 306         } else if (family == AF_INET6) {
 307                 for (ALL_LIST_ELEMENTS_RO(new->nexthops6, node, nexthop6))
 308                         if (nexthop6lookup(old->nexthops6, &nexthop6->ip6,
 309                                            nexthop6->ifindex)
 310                             == 0)
 311                                 return 0;
 312
 313                 for (ALL_LIST_ELEMENTS_RO(old->nexthops6, node, nexthop6))
 314                         if (nexthop6lookup(new->nexthops6, &nexthop6->ip6,
 315                                            nexthop6->ifindex)
 316                             == 0)
 317                                 return 0;
 318         }
 319
 320         return 1;
 321 }
 322
 323 struct isis_route_info *isis_route_create(struct prefix *prefix,
 324                                           struct prefix_ipv6 *src_p,
 325                                           uint32_t cost,
 326                                           uint32_t depth,
 327                                           struct list *adjacencies,
 328                                           struct isis_area *area,
 329                                           struct route_table *table)
 330 {
 331         struct route_node *route_node;
 332         struct isis_route_info *rinfo_new, *rinfo_old, *route_info = NULL;
 333         char buff[PREFIX2STR_BUFFER];
 334         uint8_t family;
 335
 336         family = prefix->family;
 337         /* for debugs */
 338         prefix2str(prefix, buff, sizeof(buff));
 339
 340         if (!table)
 341                 return NULL;
 342
 343         rinfo_new = isis_route_info_new(prefix, src_p, cost,
 344                                         depth, adjacencies);
 345         route_node = srcdest_rnode_get(table, prefix, src_p);
 346
 347         rinfo_old = route_node->info;
 348         if (!rinfo_old) {
 349                 if (isis->debugs & DEBUG_RTE_EVENTS)
 350                         zlog_debug("ISIS-Rte (%s) route created: %s",
 351                                    area->area_tag, buff);
 352                 route_info = rinfo_new;
 353                 UNSET_FLAG(route_info->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED);
 354         } else {
 355                 route_unlock_node(route_node);
 356                 if (isis->debugs & DEBUG_RTE_EVENTS)
 357                         zlog_debug("ISIS-Rte (%s) route already exists: %s",
 358                                    area->area_tag, buff);
 359                 if (isis_route_info_same(rinfo_new, rinfo_old, family)) {
 360                         if (isis->debugs & DEBUG_RTE_EVENTS)
 361                                 zlog_debug("ISIS-Rte (%s) route unchanged: %s",
 362                                            area->area_tag, buff);
 363                         isis_route_info_delete(rinfo_new);
 364                         route_info = rinfo_old;
 365                 } else {
 366                         if (isis->debugs & DEBUG_RTE_EVENTS)
 367                                 zlog_debug("ISIS-Rte (%s) route changed: %s",
 368                                            area->area_tag, buff);
 369                         isis_route_info_delete(rinfo_old);
 370                         route_info = rinfo_new;
 371                         UNSET_FLAG(route_info->flag,
 372                                    ISIS_ROUTE_FLAG_ZEBRA_SYNCED);
 373                 }
 374         }
 375
 376         SET_FLAG(route_info->flag, ISIS_ROUTE_FLAG_ACTIVE);
 377         route_node->info = route_info;
 378
 379         return route_info;
 380 }
 381
 382 static void isis_route_delete(struct route_node *rode,
 383                               struct route_table *table)
 384 {
 385         struct isis_route_info *rinfo;
 386         char buff[SRCDEST2STR_BUFFER];
 387         struct prefix *prefix;
 388         struct prefix_ipv6 *src_p;
 389
 390         /* for log */
 391         srcdest_rnode2str(rode, buff, sizeof(buff));
 392
 393         srcdest_rnode_prefixes(rode, (const struct prefix **)&prefix,
 394                                (const struct prefix **)&src_p);
 395
 396         rinfo = rode->info;
 397         if (rinfo == NULL) {
 398                 if (isis->debugs & DEBUG_RTE_EVENTS)
 399                         zlog_debug(
 400                                 "ISIS-Rte: tried to delete non-existant route %s",
 401                                 buff);
 402                 return;
 403         }
 404
 405         if (CHECK_FLAG(rinfo->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED)) {
 406                 UNSET_FLAG(rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE);
 407                 if (isis->debugs & DEBUG_RTE_EVENTS)
 408                         zlog_debug("ISIS-Rte: route delete  %s", buff);
 409                 isis_zebra_route_update(prefix, src_p, rinfo);
 410         }
 411         isis_route_info_delete(rinfo);
 412         rode->info = NULL;
 413         route_unlock_node(rode);
 414 }
 415
 416 static void _isis_route_verify_table(struct isis_area *area,
 417                                      struct route_table *table,
 418                                      struct route_table **tables)
 419 {
 420         struct route_node *rnode, *drnode;
 421         struct isis_route_info *rinfo;
 422         char buff[SRCDEST2STR_BUFFER];
 423
 424         for (rnode = route_top(table); rnode;
 425              rnode = srcdest_route_next(rnode)) {
 426                 if (rnode->info == NULL)
 427                         continue;
 428                 rinfo = rnode->info;
 429
 430                 struct prefix *dst_p;
 431                 struct prefix_ipv6 *src_p;
 432
 433                 srcdest_rnode_prefixes(rnode,
 434                                        (const struct prefix **)&dst_p,
 435                                        (const struct prefix **)&src_p);
 436
 437                 if (isis->debugs & 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
 456                 isis_zebra_route_update(dst_p, src_p, rinfo);
 457
 458                 if (CHECK_FLAG(rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE))
 459                         continue;
 460
 461                 /* Area is either L1 or L2 => we use level route tables
 462                  * directly for
 463                  * validating => no problems with deleting routes. */
 464                 if (!tables) {
 465                         isis_route_delete(rnode, table);
 466                         continue;
 467                 }
 468
 469                 /* If area is L1L2, we work with merge table and
 470                  * therefore must
 471                  * delete node from level tables as well before deleting
 472                  * route info. */
 473                 for (int level = ISIS_LEVEL1; level <= ISIS_LEVEL2; level++) {
 474                         drnode = srcdest_rnode_lookup(tables[level - 1],
 475                                                       dst_p, src_p);
 476                         if (!drnode)
 477                                 continue;
 478
 479                         route_unlock_node(drnode);
 480
 481                         if (drnode->info != rnode->info)
 482                                 continue;
 483
 484                         drnode->info = NULL;
 485                         route_unlock_node(drnode);
 486                 }
 487
 488                 isis_route_delete(rnode, table);
 489         }
 490 }
 491
 492 void isis_route_verify_table(struct isis_area *area, struct route_table *table)
 493 {
 494         _isis_route_verify_table(area, table, NULL);
 495 }
 496
 497 /* Function to validate route tables for L1L2 areas. In this case we can't use
 498  * level route tables directly, we have to merge them at first. L1 routes are
 499  * preferred over the L2 ones.
 500  *
 501  * Merge algorithm is trivial (at least for now). All L1 paths are copied into
 502  * merge table at first, then L2 paths are added if L1 path for same prefix
 503  * doesn't already exists there.
 504  *
 505  * FIXME: Is it right place to do it at all? Maybe we should push both levels
 506  * to the RIB with different zebra route types and let RIB handle this? */
 507 void isis_route_verify_merge(struct isis_area *area,
 508                              struct route_table *level1_table,
 509                              struct route_table *level2_table)
 510 {
 511         struct route_table *tables[] = { level1_table, level2_table };
 512         struct route_table *merge;
 513         struct route_node *rnode, *mrnode;
 514
 515         merge = srcdest_table_init();
 516
 517         for (int level = ISIS_LEVEL1; level <= ISIS_LEVEL2; level++) {
 518                 for (rnode = route_top(tables[level - 1]); rnode;
 519                      rnode = srcdest_route_next(rnode)) {
 520                         struct isis_route_info *rinfo = rnode->info;
 521                         if (!rinfo)
 522                                 continue;
 523
 524                         struct prefix *prefix;
 525                         struct prefix_ipv6 *src_p;
 526
 527                         srcdest_rnode_prefixes(rnode,
 528                                                (const struct prefix **)&prefix,
 529                                                (const struct prefix **)&src_p);
 530                         mrnode = srcdest_rnode_get(merge, prefix, src_p);
 531                         struct isis_route_info *mrinfo = mrnode->info;
 532                         if (mrinfo) {
 533                                 route_unlock_node(mrnode);
 534                                 if (CHECK_FLAG(mrinfo->flag,
 535                                                ISIS_ROUTE_FLAG_ACTIVE)) {
 536                                         /* Clear the ZEBRA_SYNCED flag on the
 537                                          * L2 route when L1 wins, otherwise L2
 538                                          * won't get reinstalled when L1
 539                                          * disappears.
 540                                          */
 541                                         UNSET_FLAG(
 542                                                 rinfo->flag,
 543                                                 ISIS_ROUTE_FLAG_ZEBRA_SYNCED
 544                                         );
 545                                         continue;
 546                                 } else {
 547                                         /* Clear the ZEBRA_SYNCED flag on the L1
 548                                          * route when L2 wins, otherwise L1
 549                                          * won't get reinstalled when it
 550                                          * reappears.
 551                                          */
 552                                         UNSET_FLAG(
 553                                                 mrinfo->flag,
 554                                                 ISIS_ROUTE_FLAG_ZEBRA_SYNCED
 555                                         );
 556                                 }
 557                         }
 558                         mrnode->info = rnode->info;
 559                 }
 560         }
 561
 562         _isis_route_verify_table(area, merge, tables);
 563         route_table_finish(merge);
 564 }
 565
 566 void isis_route_invalidate_table(struct isis_area *area,
 567                                  struct route_table *table)
 568 {
 569         struct route_node *rode;
 570         struct isis_route_info *rinfo;
 571         for (rode = route_top(table); rode; rode = srcdest_route_next(rode)) {
 572                 if (rode->info == NULL)
 573                         continue;
 574                 rinfo = rode->info;
 575
 576                 UNSET_FLAG(rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE);
 577         }
 578 }