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
  37 #include "isis_constants.h"
  38 #include "isis_common.h"
  39 #include "isis_flags.h"
  40 #include "dict.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                                                    uint32_t cost,
 203                                                    uint32_t depth,
 204                                                    struct list *adjacencies)
 205 {
 206         struct isis_route_info *rinfo;
 207         struct isis_adjacency *adj;
 208         struct listnode *node;
 209
 210         rinfo = XCALLOC(MTYPE_ISIS_ROUTE_INFO, sizeof(struct isis_route_info));
 211
 212         if (prefix->family == AF_INET) {
 213                 rinfo->nexthops = list_new();
 214                 for (ALL_LIST_ELEMENTS_RO(adjacencies, node, adj)) {
 215                         /* check for force resync this route */
 216                         if (CHECK_FLAG(adj->circuit->flags,
 217                                        ISIS_CIRCUIT_FLAPPED_AFTER_SPF))
 218                                 SET_FLAG(rinfo->flag,
 219                                          ISIS_ROUTE_FLAG_ZEBRA_RESYNC);
 220                         /* update neighbor router address */
 221                         if (depth == 2 && prefix->prefixlen == 32)
 222                                 adj->router_address = prefix->u.prefix4;
 223                         adjinfo2nexthop(rinfo->nexthops, adj);
 224                 }
 225         }
 226         if (prefix->family == AF_INET6) {
 227                 rinfo->nexthops6 = list_new();
 228                 for (ALL_LIST_ELEMENTS_RO(adjacencies, node, adj)) {
 229                         /* check for force resync this route */
 230                         if (CHECK_FLAG(adj->circuit->flags,
 231                                        ISIS_CIRCUIT_FLAPPED_AFTER_SPF))
 232                                 SET_FLAG(rinfo->flag,
 233                                          ISIS_ROUTE_FLAG_ZEBRA_RESYNC);
 234                         /* update neighbor router address */
 235                         if (depth == 2 && prefix->prefixlen == 128)
 236                                 adj->router_address6 = prefix->u.prefix6;
 237                         adjinfo2nexthop6(rinfo->nexthops6, adj);
 238                 }
 239         }
 240
 241         rinfo->cost = cost;
 242         rinfo->depth = depth;
 243
 244         return rinfo;
 245 }
 246
 247 static void isis_route_info_delete(struct isis_route_info *route_info)
 248 {
 249         if (route_info->nexthops) {
 250                 route_info->nexthops->del =
 251                         (void (*)(void *))isis_nexthop_delete;
 252                 list_delete_and_null(&route_info->nexthops);
 253         }
 254
 255         if (route_info->nexthops6) {
 256                 route_info->nexthops6->del =
 257                         (void (*)(void *))isis_nexthop6_delete;
 258                 list_delete_and_null(&route_info->nexthops6);
 259         }
 260
 261         XFREE(MTYPE_ISIS_ROUTE_INFO, route_info);
 262 }
 263
 264 static int isis_route_info_same_attrib(struct isis_route_info *new,
 265                                        struct isis_route_info *old)
 266 {
 267         if (new->cost != old->cost)
 268                 return 0;
 269         if (new->depth != old->depth)
 270                 return 0;
 271
 272         return 1;
 273 }
 274
 275 static int isis_route_info_same(struct isis_route_info *new,
 276                                 struct isis_route_info *old, uint8_t family)
 277 {
 278         struct listnode *node;
 279         struct isis_nexthop *nexthop;
 280         struct isis_nexthop6 *nexthop6;
 281
 282         if (!CHECK_FLAG(old->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED))
 283                 return 0;
 284
 285         if (CHECK_FLAG(new->flag, ISIS_ROUTE_FLAG_ZEBRA_RESYNC))
 286                 return 0;
 287
 288         if (!isis_route_info_same_attrib(new, old))
 289                 return 0;
 290
 291         if (family == AF_INET) {
 292                 for (ALL_LIST_ELEMENTS_RO(new->nexthops, node, nexthop))
 293                         if (nexthoplookup(old->nexthops, &nexthop->ip,
 294                                           nexthop->ifindex)
 295                             == 0)
 296                                 return 0;
 297
 298                 for (ALL_LIST_ELEMENTS_RO(old->nexthops, node, nexthop))
 299                         if (nexthoplookup(new->nexthops, &nexthop->ip,
 300                                           nexthop->ifindex)
 301                             == 0)
 302                                 return 0;
 303         } else if (family == AF_INET6) {
 304                 for (ALL_LIST_ELEMENTS_RO(new->nexthops6, node, nexthop6))
 305                         if (nexthop6lookup(old->nexthops6, &nexthop6->ip6,
 306                                            nexthop6->ifindex)
 307                             == 0)
 308                                 return 0;
 309
 310                 for (ALL_LIST_ELEMENTS_RO(old->nexthops6, node, nexthop6))
 311                         if (nexthop6lookup(new->nexthops6, &nexthop6->ip6,
 312                                            nexthop6->ifindex)
 313                             == 0)
 314                                 return 0;
 315         }
 316
 317         return 1;
 318 }
 319
 320 struct isis_route_info *isis_route_create(struct prefix *prefix, uint32_t cost,
 321                                           uint32_t depth,
 322                                           struct list *adjacencies,
 323                                           struct isis_area *area, int level)
 324 {
 325         struct route_node *route_node;
 326         struct isis_route_info *rinfo_new, *rinfo_old, *route_info = NULL;
 327         char buff[PREFIX2STR_BUFFER];
 328         uint8_t family;
 329
 330         family = prefix->family;
 331         /* for debugs */
 332         prefix2str(prefix, buff, sizeof(buff));
 333
 334         rinfo_new = isis_route_info_new(prefix, cost, depth, adjacencies);
 335
 336         if (family == AF_INET)
 337                 route_node =
 338                         route_node_get(area->route_table[level - 1], prefix);
 339         else if (family == AF_INET6)
 340                 route_node =
 341                         route_node_get(area->route_table6[level - 1], prefix);
 342         else {
 343                 isis_route_info_delete(rinfo_new);
 344                 return NULL;
 345         }
 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                 if (isis->debugs & DEBUG_RTE_EVENTS)
 356                         zlog_debug("ISIS-Rte (%s) route already exists: %s",
 357                                    area->area_tag, buff);
 358                 if (isis_route_info_same(rinfo_new, rinfo_old, family)) {
 359                         if (isis->debugs & DEBUG_RTE_EVENTS)
 360                                 zlog_debug("ISIS-Rte (%s) route unchanged: %s",
 361                                            area->area_tag, buff);
 362                         isis_route_info_delete(rinfo_new);
 363                         route_info = rinfo_old;
 364                 } else {
 365                         if (isis->debugs & DEBUG_RTE_EVENTS)
 366                                 zlog_debug("ISIS-Rte (%s) route changed: %s",
 367                                            area->area_tag, buff);
 368                         isis_route_info_delete(rinfo_old);
 369                         route_info = rinfo_new;
 370                         UNSET_FLAG(route_info->flag,
 371                                    ISIS_ROUTE_FLAG_ZEBRA_SYNCED);
 372                 }
 373         }
 374
 375         SET_FLAG(route_info->flag, ISIS_ROUTE_FLAG_ACTIVE);
 376         route_node->info = route_info;
 377
 378         return route_info;
 379 }
 380
 381 static void isis_route_delete(struct prefix *prefix, struct route_table *table)
 382 {
 383         struct route_node *rode;
 384         struct isis_route_info *rinfo;
 385         char buff[PREFIX2STR_BUFFER];
 386
 387         /* for log */
 388         prefix2str(prefix, buff, sizeof(buff));
 389
 390
 391         rode = route_node_get(table, prefix);
 392         rinfo = rode->info;
 393
 394         if (rinfo == NULL) {
 395                 if (isis->debugs & DEBUG_RTE_EVENTS)
 396                         zlog_debug(
 397                                 "ISIS-Rte: tried to delete non-existant route %s",
 398                                 buff);
 399                 return;
 400         }
 401
 402         if (CHECK_FLAG(rinfo->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED)) {
 403                 UNSET_FLAG(rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE);
 404                 if (isis->debugs & DEBUG_RTE_EVENTS)
 405                         zlog_debug("ISIS-Rte: route delete  %s", buff);
 406                 isis_zebra_route_update(prefix, rinfo);
 407         }
 408         isis_route_info_delete(rinfo);
 409         rode->info = NULL;
 410
 411         return;
 412 }
 413
 414 /* Validating routes in particular table. */
 415 static void isis_route_validate_table(struct isis_area *area,
 416                                       struct route_table *table)
 417 {
 418         struct route_node *rnode, *drnode;
 419         struct isis_route_info *rinfo;
 420         char buff[PREFIX2STR_BUFFER];
 421
 422         for (rnode = route_top(table); rnode; rnode = route_next(rnode)) {
 423                 if (rnode->info == NULL)
 424                         continue;
 425                 rinfo = rnode->info;
 426
 427                 if (isis->debugs & DEBUG_RTE_EVENTS) {
 428                         prefix2str(&rnode->p, buff, sizeof(buff));
 429                         zlog_debug(
 430                                 "ISIS-Rte (%s): route validate: %s %s %s %s",
 431                                 area->area_tag,
 432                                 (CHECK_FLAG(rinfo->flag,
 433                                             ISIS_ROUTE_FLAG_ZEBRA_SYNCED)
 434                                          ? "synced"
 435                                          : "not-synced"),
 436                                 (CHECK_FLAG(rinfo->flag,
 437                                             ISIS_ROUTE_FLAG_ZEBRA_RESYNC)
 438                                          ? "resync"
 439                                          : "not-resync"),
 440                                 (CHECK_FLAG(rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE)
 441                                          ? "active"
 442                                          : "inactive"),
 443                                 buff);
 444                 }
 445
 446                 isis_zebra_route_update(&rnode->p, rinfo);
 447                 if (!CHECK_FLAG(rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE)) {
 448                         /* Area is either L1 or L2 => we use level route tables
 449                          * directly for
 450                          * validating => no problems with deleting routes. */
 451                         if (area->is_type != IS_LEVEL_1_AND_2) {
 452                                 isis_route_delete(&rnode->p, table);
 453                                 continue;
 454                         }
 455                         /* If area is L1L2, we work with merge table and
 456                          * therefore must
 457                          * delete node from level tables as well before deleting
 458                          * route info.
 459                          * FIXME: Is it performance problem? There has to be the
 460                          * better way.
 461                          * Like not to deal with it here at all (see the next
 462                          * comment)? */
 463                         if (rnode->p.family == AF_INET) {
 464                                 drnode = route_node_get(area->route_table[0],
 465                                                         &rnode->p);
 466                                 if (drnode->info == rnode->info)
 467                                         drnode->info = NULL;
 468                                 drnode = route_node_get(area->route_table[1],
 469                                                         &rnode->p);
 470                                 if (drnode->info == rnode->info)
 471                                         drnode->info = NULL;
 472                         }
 473
 474                         if (rnode->p.family == AF_INET6) {
 475                                 drnode = route_node_get(area->route_table6[0],
 476                                                         &rnode->p);
 477                                 if (drnode->info == rnode->info)
 478                                         drnode->info = NULL;
 479                                 drnode = route_node_get(area->route_table6[1],
 480                                                         &rnode->p);
 481                                 if (drnode->info == rnode->info)
 482                                         drnode->info = NULL;
 483                         }
 484
 485                         isis_route_delete(&rnode->p, table);
 486                 }
 487         }
 488 }
 489
 490 /* Function to validate route tables for L1L2 areas. In this case we can't use
 491  * level route tables directly, we have to merge them at first. L1 routes are
 492  * preferred over the L2 ones.
 493  *
 494  * Merge algorithm is trivial (at least for now). All L1 paths are copied into
 495  * merge table at first, then L2 paths are added if L1 path for same prefix
 496  * doesn't already exists there.
 497  *
 498  * FIXME: Is it right place to do it at all? Maybe we should push both levels
 499  * to the RIB with different zebra route types and let RIB handle this? */
 500 static void isis_route_validate_merge(struct isis_area *area, int family)
 501 {
 502         struct route_table *table = NULL;
 503         struct route_table *merge;
 504         struct route_node *rnode, *mrnode;
 505
 506         merge = route_table_init();
 507
 508         if (family == AF_INET)
 509                 table = area->route_table[0];
 510         else if (family == AF_INET6)
 511                 table = area->route_table6[0];
 512         else {
 513                 zlog_warn("ISIS-Rte (%s) %s called for unknown family %d",
 514                           area->area_tag, __func__, family);
 515                 route_table_finish(merge);
 516                 return;
 517         }
 518
 519         for (rnode = route_top(table); rnode; rnode = route_next(rnode)) {
 520                 if (rnode->info == NULL)
 521                         continue;
 522                 mrnode = route_node_get(merge, &rnode->p);
 523                 mrnode->info = rnode->info;
 524         }
 525
 526         if (family == AF_INET)
 527                 table = area->route_table[1];
 528         else if (family == AF_INET6)
 529                 table = area->route_table6[1];
 530
 531         for (rnode = route_top(table); rnode; rnode = route_next(rnode)) {
 532                 if (rnode->info == NULL)
 533                         continue;
 534                 mrnode = route_node_get(merge, &rnode->p);
 535                 if (mrnode->info != NULL)
 536                         continue;
 537                 mrnode->info = rnode->info;
 538         }
 539
 540         isis_route_validate_table(area, merge);
 541         route_table_finish(merge);
 542 }
 543
 544 /* Walk through route tables and propagate necessary changes into RIB. In case
 545  * of L1L2 area, level tables have to be merged at first. */
 546 void isis_route_validate(struct isis_area *area)
 547 {
 548         struct listnode *node;
 549         struct isis_circuit *circuit;
 550
 551         if (area->is_type == IS_LEVEL_1)
 552                 isis_route_validate_table(area, area->route_table[0]);
 553         else if (area->is_type == IS_LEVEL_2)
 554                 isis_route_validate_table(area, area->route_table[1]);
 555         else
 556                 isis_route_validate_merge(area, AF_INET);
 557
 558         if (area->is_type == IS_LEVEL_1)
 559                 isis_route_validate_table(area, area->route_table6[0]);
 560         else if (area->is_type == IS_LEVEL_2)
 561                 isis_route_validate_table(area, area->route_table6[1]);
 562         else
 563                 isis_route_validate_merge(area, AF_INET6);
 564
 565         if (!area->circuit_list) {
 566                 return;
 567         }
 568         /* walk all circuits and reset any spf specific flags */
 569         for (ALL_LIST_ELEMENTS_RO(area->circuit_list, node, circuit))
 570                 UNSET_FLAG(circuit->flags, ISIS_CIRCUIT_FLAPPED_AFTER_SPF);
 571
 572         return;
 573 }
 574
 575 void isis_route_invalidate_table(struct isis_area *area,
 576                                  struct route_table *table)
 577 {
 578         struct route_node *rode;
 579         struct isis_route_info *rinfo;
 580         for (rode = route_top(table); rode; rode = route_next(rode)) {
 581                 if (rode->info == NULL)
 582                         continue;
 583                 rinfo = rode->info;
 584
 585                 UNSET_FLAG(rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE);
 586         }
 587 }
 588
 589 void isis_route_invalidate(struct isis_area *area)
 590 {
 591         if (area->is_type & IS_LEVEL_1)
 592                 isis_route_invalidate_table(area, area->route_table[0]);
 593         if (area->is_type & IS_LEVEL_2)
 594                 isis_route_invalidate_table(area, area->route_table[1]);
 595 }