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; if not, write to the Free Software Foundation, Inc.,
  22  * 59 Temple Place - Suite 330, Boston, MA  02111-1307, 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_tlv.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 *
  53 isis_nexthop_create (struct in_addr *ip, 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     {
  60       if (nexthop->ifindex != ifindex)
  61         continue;
  62       if (ip && memcmp (&nexthop->ip, ip, sizeof (struct in_addr)) != 0)
  63         continue;
  64
  65       nexthop->lock++;
  66       return nexthop;
  67     }
  68
  69   nexthop = XCALLOC (MTYPE_ISIS_NEXTHOP, sizeof (struct isis_nexthop));
  70
  71   nexthop->ifindex = ifindex;
  72   memcpy (&nexthop->ip, ip, sizeof (struct in_addr));
  73   listnode_add (isis->nexthops, nexthop);
  74   nexthop->lock++;
  75
  76   return nexthop;
  77 }
  78
  79 static void
  80 isis_nexthop_delete (struct isis_nexthop *nexthop)
  81 {
  82   nexthop->lock--;
  83   if (nexthop->lock == 0)
  84     {
  85       listnode_delete (isis->nexthops, nexthop);
  86       XFREE (MTYPE_ISIS_NEXTHOP, nexthop);
  87     }
  88
  89   return;
  90 }
  91
  92 static int
  93 nexthoplookup (struct list *nexthops, struct in_addr *ip,
  94                ifindex_t ifindex)
  95 {
  96   struct listnode *node;
  97   struct isis_nexthop *nh;
  98
  99   for (ALL_LIST_ELEMENTS_RO (nexthops, node, nh))
 100     {
 101       if (!(memcmp (ip, &nh->ip, sizeof (struct in_addr))) &&
 102           ifindex == nh->ifindex)
 103         return 1;
 104     }
 105
 106   return 0;
 107 }
 108
 109 #ifdef EXTREME_DEBUG
 110 static void
 111 nexthop_print (struct isis_nexthop *nh)
 112 {
 113   u_char buf[BUFSIZ];
 114
 115   inet_ntop (AF_INET, &nh->ip, (char *) buf, BUFSIZ);
 116
 117   zlog_debug ("      %s %u", buf, nh->ifindex);
 118 }
 119
 120 static void
 121 nexthops_print (struct list *nhs)
 122 {
 123   struct listnode *node;
 124   struct isis_nexthop *nh;
 125
 126   for (ALL_LIST_ELEMENTS_RO (nhs, node, nh))
 127     nexthop_print (nh);
 128 }
 129 #endif /* EXTREME_DEBUG */
 130
 131 static struct isis_nexthop6 *
 132 isis_nexthop6_new (struct in6_addr *ip6, ifindex_t ifindex)
 133 {
 134   struct isis_nexthop6 *nexthop6;
 135
 136   nexthop6 = XCALLOC (MTYPE_ISIS_NEXTHOP6, sizeof (struct isis_nexthop6));
 137
 138   nexthop6->ifindex = ifindex;
 139   memcpy (&nexthop6->ip6, ip6, sizeof (struct in6_addr));
 140   nexthop6->lock++;
 141
 142   return nexthop6;
 143 }
 144
 145 static struct isis_nexthop6 *
 146 isis_nexthop6_create (struct in6_addr *ip6, ifindex_t ifindex)
 147 {
 148   struct listnode *node;
 149   struct isis_nexthop6 *nexthop6;
 150
 151   for (ALL_LIST_ELEMENTS_RO (isis->nexthops6, node, nexthop6))
 152     {
 153       if (nexthop6->ifindex != ifindex)
 154         continue;
 155       if (ip6 && memcmp (&nexthop6->ip6, ip6, sizeof (struct in6_addr)) != 0)
 156         continue;
 157
 158       nexthop6->lock++;
 159       return nexthop6;
 160     }
 161
 162   nexthop6 = isis_nexthop6_new (ip6, ifindex);
 163
 164   return nexthop6;
 165 }
 166
 167 static void
 168 isis_nexthop6_delete (struct isis_nexthop6 *nexthop6)
 169 {
 170
 171   nexthop6->lock--;
 172   if (nexthop6->lock == 0)
 173     {
 174       listnode_delete (isis->nexthops6, nexthop6);
 175       XFREE (MTYPE_ISIS_NEXTHOP6, nexthop6);
 176     }
 177
 178   return;
 179 }
 180
 181 static int
 182 nexthop6lookup (struct list *nexthops6, struct in6_addr *ip6,
 183                 ifindex_t ifindex)
 184 {
 185   struct listnode *node;
 186   struct isis_nexthop6 *nh6;
 187
 188   for (ALL_LIST_ELEMENTS_RO (nexthops6, node, nh6))
 189     {
 190       if (!(memcmp (ip6, &nh6->ip6, sizeof (struct in6_addr))) &&
 191           ifindex == nh6->ifindex)
 192         return 1;
 193     }
 194
 195   return 0;
 196 }
 197
 198 #ifdef EXTREME_DEBUG
 199 static void
 200 nexthop6_print (struct isis_nexthop6 *nh6)
 201 {
 202   u_char buf[BUFSIZ];
 203
 204   inet_ntop (AF_INET6, &nh6->ip6, (char *) buf, BUFSIZ);
 205
 206   zlog_debug ("      %s %u", buf, nh6->ifindex);
 207 }
 208
 209 static void
 210 nexthops6_print (struct list *nhs6)
 211 {
 212   struct listnode *node;
 213   struct isis_nexthop6 *nh6;
 214
 215   for (ALL_LIST_ELEMENTS_RO (nhs6, node, nh6))
 216     nexthop6_print (nh6);
 217 }
 218 #endif /* EXTREME_DEBUG */
 219
 220 static void
 221 adjinfo2nexthop (struct list *nexthops, struct isis_adjacency *adj)
 222 {
 223   struct isis_nexthop *nh;
 224   struct listnode *node;
 225   struct in_addr *ipv4_addr;
 226
 227   if (adj->ipv4_addrs == NULL)
 228     return;
 229
 230   for (ALL_LIST_ELEMENTS_RO (adj->ipv4_addrs, node, ipv4_addr))
 231     {
 232       if (!nexthoplookup (nexthops, ipv4_addr,
 233                           adj->circuit->interface->ifindex))
 234         {
 235           nh = isis_nexthop_create (ipv4_addr,
 236                                     adj->circuit->interface->ifindex);
 237           nh->router_address = adj->router_address;
 238           listnode_add (nexthops, nh);
 239         }
 240     }
 241 }
 242
 243 static void
 244 adjinfo2nexthop6 (struct list *nexthops6, struct isis_adjacency *adj)
 245 {
 246   struct listnode *node;
 247   struct in6_addr *ipv6_addr;
 248   struct isis_nexthop6 *nh6;
 249
 250   if (!adj->ipv6_addrs)
 251     return;
 252
 253   for (ALL_LIST_ELEMENTS_RO (adj->ipv6_addrs, node, ipv6_addr))
 254     {
 255       if (!nexthop6lookup (nexthops6, ipv6_addr,
 256                            adj->circuit->interface->ifindex))
 257         {
 258           nh6 = isis_nexthop6_create (ipv6_addr,
 259                                       adj->circuit->interface->ifindex);
 260           nh6->router_address6 = adj->router_address6;
 261           listnode_add (nexthops6, nh6);
 262         }
 263     }
 264 }
 265
 266 static struct isis_route_info *
 267 isis_route_info_new (struct prefix *prefix, uint32_t cost, uint32_t depth,
 268                      struct list *adjacencies)
 269 {
 270   struct isis_route_info *rinfo;
 271   struct isis_adjacency *adj;
 272   struct listnode *node;
 273
 274   rinfo = XCALLOC (MTYPE_ISIS_ROUTE_INFO, sizeof (struct isis_route_info));
 275
 276   if (prefix->family == AF_INET)
 277     {
 278       rinfo->nexthops = list_new ();
 279       for (ALL_LIST_ELEMENTS_RO (adjacencies, node, adj))
 280         {
 281           /* check for force resync this route */
 282           if (CHECK_FLAG (adj->circuit->flags, ISIS_CIRCUIT_FLAPPED_AFTER_SPF))
 283             SET_FLAG (rinfo->flag, ISIS_ROUTE_FLAG_ZEBRA_RESYNC);
 284           /* update neighbor router address */
 285           if (depth == 2 && prefix->prefixlen == 32)
 286             adj->router_address = prefix->u.prefix4;
 287           adjinfo2nexthop (rinfo->nexthops, adj);
 288         }
 289     }
 290   if (prefix->family == AF_INET6)
 291     {
 292       rinfo->nexthops6 = list_new ();
 293       for (ALL_LIST_ELEMENTS_RO (adjacencies, node, adj))
 294         {
 295           /* check for force resync this route */
 296           if (CHECK_FLAG (adj->circuit->flags, ISIS_CIRCUIT_FLAPPED_AFTER_SPF))
 297             SET_FLAG (rinfo->flag, ISIS_ROUTE_FLAG_ZEBRA_RESYNC);
 298           /* update neighbor router address */
 299           if (depth == 2 && prefix->prefixlen == 128)
 300             adj->router_address6 = prefix->u.prefix6;
 301           adjinfo2nexthop6 (rinfo->nexthops6, adj);
 302         }
 303     }
 304
 305   rinfo->cost = cost;
 306   rinfo->depth = depth;
 307
 308   return rinfo;
 309 }
 310
 311 static void
 312 isis_route_info_delete (struct isis_route_info *route_info)
 313 {
 314   if (route_info->nexthops)
 315     {
 316       route_info->nexthops->del = (void (*)(void *)) isis_nexthop_delete;
 317       list_delete (route_info->nexthops);
 318     }
 319
 320   if (route_info->nexthops6)
 321     {
 322       route_info->nexthops6->del = (void (*)(void *)) isis_nexthop6_delete;
 323       list_delete (route_info->nexthops6);
 324     }
 325
 326   XFREE (MTYPE_ISIS_ROUTE_INFO, route_info);
 327 }
 328
 329 static int
 330 isis_route_info_same_attrib (struct isis_route_info *new,
 331                              struct isis_route_info *old)
 332 {
 333   if (new->cost != old->cost)
 334     return 0;
 335   if (new->depth != old->depth)
 336     return 0;
 337
 338   return 1;
 339 }
 340
 341 static int
 342 isis_route_info_same (struct isis_route_info *new,
 343                       struct isis_route_info *old, u_char family)
 344 {
 345   struct listnode *node;
 346   struct isis_nexthop *nexthop;
 347   struct isis_nexthop6 *nexthop6;
 348
 349   if (!CHECK_FLAG (old->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED))
 350     return 0;
 351
 352   if (CHECK_FLAG (new->flag, ISIS_ROUTE_FLAG_ZEBRA_RESYNC))
 353     return 0;
 354
 355   if (!isis_route_info_same_attrib (new, old))
 356     return 0;
 357
 358   if (family == AF_INET)
 359     {
 360       for (ALL_LIST_ELEMENTS_RO (new->nexthops, node, nexthop))
 361         if (nexthoplookup (old->nexthops, &nexthop->ip, nexthop->ifindex)
 362               == 0)
 363           return 0;
 364
 365       for (ALL_LIST_ELEMENTS_RO (old->nexthops, node, nexthop))
 366         if (nexthoplookup (new->nexthops, &nexthop->ip, nexthop->ifindex)
 367              == 0)
 368           return 0;
 369     }
 370   else if (family == AF_INET6)
 371     {
 372       for (ALL_LIST_ELEMENTS_RO (new->nexthops6, node, nexthop6))
 373         if (nexthop6lookup (old->nexthops6, &nexthop6->ip6,
 374                             nexthop6->ifindex) == 0)
 375           return 0;
 376
 377       for (ALL_LIST_ELEMENTS_RO (old->nexthops6, node, nexthop6))
 378         if (nexthop6lookup (new->nexthops6, &nexthop6->ip6,
 379                             nexthop6->ifindex) == 0)
 380           return 0;
 381     }
 382
 383   return 1;
 384 }
 385
 386 struct isis_route_info *
 387 isis_route_create (struct prefix *prefix, u_int32_t cost, u_int32_t depth,
 388                    struct list *adjacencies, struct isis_area *area,
 389                    int level)
 390 {
 391   struct route_node *route_node;
 392   struct isis_route_info *rinfo_new, *rinfo_old, *route_info = NULL;
 393   char buff[PREFIX2STR_BUFFER];
 394   u_char family;
 395
 396   family = prefix->family;
 397   /* for debugs */
 398   prefix2str (prefix, buff, sizeof (buff));
 399
 400   rinfo_new = isis_route_info_new (prefix, cost, depth, adjacencies);
 401
 402   if (family == AF_INET)
 403     route_node = route_node_get (area->route_table[level - 1], prefix);
 404   else if (family == AF_INET6)
 405     route_node = route_node_get (area->route_table6[level - 1], prefix);
 406   else
 407     {
 408       isis_route_info_delete (rinfo_new);
 409       return NULL;
 410     }
 411
 412   rinfo_old = route_node->info;
 413   if (!rinfo_old)
 414     {
 415       if (isis->debugs & DEBUG_RTE_EVENTS)
 416         zlog_debug ("ISIS-Rte (%s) route created: %s", area->area_tag, buff);
 417       route_info = rinfo_new;
 418       UNSET_FLAG (route_info->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED);
 419     }
 420   else
 421     {
 422       if (isis->debugs & DEBUG_RTE_EVENTS)
 423         zlog_debug ("ISIS-Rte (%s) route already exists: %s", area->area_tag,
 424                    buff);
 425       if (isis_route_info_same (rinfo_new, rinfo_old, family))
 426         {
 427           if (isis->debugs & DEBUG_RTE_EVENTS)
 428             zlog_debug ("ISIS-Rte (%s) route unchanged: %s", area->area_tag,
 429                         buff);
 430           isis_route_info_delete (rinfo_new);
 431           route_info = rinfo_old;
 432         }
 433       else
 434         {
 435           if (isis->debugs & DEBUG_RTE_EVENTS)
 436             zlog_debug ("ISIS-Rte (%s) route changed: %s", area->area_tag,
 437                         buff);
 438           isis_route_info_delete (rinfo_old);
 439           route_info = rinfo_new;
 440           UNSET_FLAG (route_info->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED);
 441         }
 442     }
 443
 444   SET_FLAG (route_info->flag, ISIS_ROUTE_FLAG_ACTIVE);
 445   route_node->info = route_info;
 446
 447   return route_info;
 448 }
 449
 450 static void
 451 isis_route_delete (struct prefix *prefix, struct route_table *table)
 452 {
 453   struct route_node *rode;
 454   struct isis_route_info *rinfo;
 455   char buff[PREFIX2STR_BUFFER];
 456
 457   /* for log */
 458   prefix2str (prefix, buff, sizeof (buff));
 459
 460
 461   rode = route_node_get (table, prefix);
 462   rinfo = rode->info;
 463
 464   if (rinfo == NULL)
 465     {
 466       if (isis->debugs & DEBUG_RTE_EVENTS)
 467         zlog_debug ("ISIS-Rte: tried to delete non-existant route %s", buff);
 468       return;
 469     }
 470
 471   if (CHECK_FLAG (rinfo->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED))
 472     {
 473       UNSET_FLAG (rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE);
 474       if (isis->debugs & DEBUG_RTE_EVENTS)
 475         zlog_debug ("ISIS-Rte: route delete  %s", buff);
 476       isis_zebra_route_update (prefix, rinfo);
 477     }
 478   isis_route_info_delete (rinfo);
 479   rode->info = NULL;
 480
 481   return;
 482 }
 483
 484 /* Validating routes in particular table. */
 485 static void
 486 isis_route_validate_table (struct isis_area *area, struct route_table *table)
 487 {
 488   struct route_node *rnode, *drnode;
 489   struct isis_route_info *rinfo;
 490   char buff[PREFIX2STR_BUFFER];
 491
 492   for (rnode = route_top (table); rnode; rnode = route_next (rnode))
 493     {
 494       if (rnode->info == NULL)
 495         continue;
 496       rinfo = rnode->info;
 497
 498       if (isis->debugs & DEBUG_RTE_EVENTS)
 499         {
 500           prefix2str (&rnode->p, buff, sizeof (buff));
 501           zlog_debug ("ISIS-Rte (%s): route validate: %s %s %s %s",
 502                       area->area_tag,
 503                       (CHECK_FLAG (rinfo->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED) ?
 504                       "synced" : "not-synced"),
 505                       (CHECK_FLAG (rinfo->flag, ISIS_ROUTE_FLAG_ZEBRA_RESYNC) ?
 506                       "resync" : "not-resync"),
 507                       (CHECK_FLAG (rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE) ?
 508                       "active" : "inactive"), buff);
 509         }
 510
 511       isis_zebra_route_update (&rnode->p, rinfo);
 512       if (!CHECK_FLAG (rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE))
 513         {
 514           /* Area is either L1 or L2 => we use level route tables directly for
 515            * validating => no problems with deleting routes. */
 516           if (area->is_type != IS_LEVEL_1_AND_2)
 517             {
 518               isis_route_delete (&rnode->p, table);
 519               continue;
 520             }
 521           /* If area is L1L2, we work with merge table and therefore must
 522            * delete node from level tables as well before deleting route info.
 523            * FIXME: Is it performance problem? There has to be the better way.
 524            * Like not to deal with it here at all (see the next comment)? */
 525           if (rnode->p.family == AF_INET)
 526             {
 527               drnode = route_node_get (area->route_table[0], &rnode->p);
 528               if (drnode->info == rnode->info)
 529                 drnode->info = NULL;
 530               drnode = route_node_get (area->route_table[1], &rnode->p);
 531               if (drnode->info == rnode->info)
 532                 drnode->info = NULL;
 533             }
 534
 535           if (rnode->p.family == AF_INET6)
 536             {
 537               drnode = route_node_get (area->route_table6[0], &rnode->p);
 538               if (drnode->info == rnode->info)
 539                 drnode->info = NULL;
 540               drnode = route_node_get (area->route_table6[1], &rnode->p);
 541               if (drnode->info == rnode->info)
 542                 drnode->info = NULL;
 543             }
 544
 545           isis_route_delete (&rnode->p, table);
 546         }
 547     }
 548 }
 549
 550 /* Function to validate route tables for L1L2 areas. In this case we can't use
 551  * level route tables directly, we have to merge them at first. L1 routes are
 552  * preferred over the L2 ones.
 553  *
 554  * Merge algorithm is trivial (at least for now). All L1 paths are copied into
 555  * merge table at first, then L2 paths are added if L1 path for same prefix
 556  * doesn't already exists there.
 557  *
 558  * FIXME: Is it right place to do it at all? Maybe we should push both levels
 559  * to the RIB with different zebra route types and let RIB handle this? */
 560 static void
 561 isis_route_validate_merge (struct isis_area *area, int family)
 562 {
 563   struct route_table *table = NULL;
 564   struct route_table *merge;
 565   struct route_node *rnode, *mrnode;
 566
 567   merge = route_table_init ();
 568
 569   if (family == AF_INET)
 570     table = area->route_table[0];
 571   else if (family == AF_INET6)
 572     table = area->route_table6[0];
 573   else
 574     {
 575       zlog_warn ("ISIS-Rte (%s) %s called for unknown family %d",
 576                  area->area_tag, __func__, family);
 577       route_table_finish(merge);
 578       return;
 579     }
 580
 581   for (rnode = route_top (table); rnode; rnode = route_next (rnode))
 582     {
 583       if (rnode->info == NULL)
 584         continue;
 585       mrnode = route_node_get (merge, &rnode->p);
 586       mrnode->info = rnode->info;
 587     }
 588
 589   if (family == AF_INET)
 590     table = area->route_table[1];
 591   else if (family == AF_INET6)
 592     table = area->route_table6[1];
 593
 594   for (rnode = route_top (table); rnode; rnode = route_next (rnode))
 595     {
 596       if (rnode->info == NULL)
 597         continue;
 598       mrnode = route_node_get (merge, &rnode->p);
 599       if (mrnode->info != NULL)
 600         continue;
 601       mrnode->info = rnode->info;
 602     }
 603
 604   isis_route_validate_table (area, merge);
 605   route_table_finish (merge);
 606 }
 607
 608 /* Walk through route tables and propagate necessary changes into RIB. In case
 609  * of L1L2 area, level tables have to be merged at first. */
 610 void
 611 isis_route_validate (struct isis_area *area)
 612 {
 613   struct listnode *node;
 614   struct isis_circuit *circuit;
 615
 616   if (area->is_type == IS_LEVEL_1)
 617     isis_route_validate_table (area, area->route_table[0]);
 618   else if (area->is_type == IS_LEVEL_2)
 619     isis_route_validate_table (area, area->route_table[1]);
 620   else
 621     isis_route_validate_merge (area, AF_INET);
 622
 623   if (area->is_type == IS_LEVEL_1)
 624     isis_route_validate_table (area, area->route_table6[0]);
 625   else if (area->is_type == IS_LEVEL_2)
 626     isis_route_validate_table (area, area->route_table6[1]);
 627   else
 628     isis_route_validate_merge (area, AF_INET6);
 629
 630   if (!area->circuit_list) {
 631     return;
 632   }
 633   /* walk all circuits and reset any spf specific flags */
 634   for (ALL_LIST_ELEMENTS_RO (area->circuit_list, node, circuit))
 635     UNSET_FLAG(circuit->flags, ISIS_CIRCUIT_FLAPPED_AFTER_SPF);
 636
 637   return;
 638 }
 639
 640 void
 641 isis_route_invalidate_table (struct isis_area *area, struct route_table *table)
 642 {
 643   struct route_node *rode;
 644   struct isis_route_info *rinfo;
 645   for (rode = route_top (table); rode; rode = route_next (rode))
 646     {
 647       if (rode->info == NULL)
 648         continue;
 649       rinfo = rode->info;
 650
 651       UNSET_FLAG (rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE);
 652     }
 653 }
 654
 655 void
 656 isis_route_invalidate (struct isis_area *area)
 657 {
 658   if (area->is_type & IS_LEVEL_1)
 659     isis_route_invalidate_table (area, area->route_table[0]);
 660   if (area->is_type & IS_LEVEL_2)
 661     isis_route_invalidate_table (area, area->route_table[1]);
 662 }