isisd/isis_spf.c

   1 /*
   2  * IS-IS Rout(e)ing protocol                  - isis_spf.c
   3  *                                              The SPT algorithm
   4  *
   5  * Copyright (C) 2001,2002   Sampo Saaristo
   6  *                           Tampere University of Technology
   7  *                           Institute of Communications Engineering
   8  *
   9  * This program is free software; you can redistribute it and/or modify it
  10  * under the terms of the GNU General Public Licenseas published by the Free
  11  * Software Foundation; either version 2 of the License, or (at your option)
  12  * any later version.
  13  *
  14  * This program is distributed in the hope that it will be useful,but WITHOUT
  15  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  16  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  17  * more details.
  18
  19  * You should have received a copy of the GNU General Public License along
  20  * with this program; if not, write to the Free Software Foundation, Inc.,
  21  * 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  22  */
  23
  24 #include <zebra.h>
  25
  26 #include "thread.h"
  27 #include "linklist.h"
  28 #include "vty.h"
  29 #include "log.h"
  30 #include "command.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 "dict.h"
  40 #include "isisd.h"
  41 #include "isis_misc.h"
  42 #include "isis_adjacency.h"
  43 #include "isis_circuit.h"
  44 #include "isis_tlv.h"
  45 #include "isis_pdu.h"
  46 #include "isis_lsp.h"
  47 #include "isis_dynhn.h"
  48 #include "isis_spf.h"
  49 #include "isis_route.h"
  50 #include "isis_csm.h"
  51
  52 extern struct isis *isis;
  53 extern struct thread_master *master;
  54 extern struct host host;
  55
  56 int isis_run_spf_l1 (struct thread *thread);
  57 int isis_run_spf_l2 (struct thread *thread);
  58
  59 /* 7.2.7 */
  60 static void
  61 remove_excess_adjs (struct list *adjs)
  62 {
  63   struct listnode *node, *excess = NULL;
  64   struct isis_adjacency *adj, *candidate = NULL;
  65   int comp;
  66
  67   for (ALL_LIST_ELEMENTS_RO (adjs, node, adj))
  68     {
  69       if (excess == NULL)
  70         excess = node;
  71       candidate = listgetdata (excess);
  72
  73       if (candidate->sys_type < adj->sys_type)
  74         {
  75           excess = node;
  76           candidate = adj;
  77           continue;
  78         }
  79       if (candidate->sys_type > adj->sys_type)
  80         continue;
  81
  82       comp = memcmp (candidate->sysid, adj->sysid, ISIS_SYS_ID_LEN);
  83       if (comp > 0)
  84         {
  85           excess = node;
  86           candidate = adj;
  87           continue;
  88         }
  89       if (comp < 0)
  90         continue;
  91
  92       if (candidate->circuit->circuit_id > adj->circuit->circuit_id)
  93         {
  94           excess = node;
  95           candidate = adj;
  96           continue;
  97         }
  98
  99       if (candidate->circuit->circuit_id < adj->circuit->circuit_id)
 100         continue;
 101
 102       comp = memcmp (candidate->snpa, adj->snpa, ETH_ALEN);
 103       if (comp > 0)
 104         {
 105           excess = node;
 106           candidate = adj;
 107           continue;
 108         }
 109     }
 110
 111   list_delete_node (adjs, excess);
 112
 113   return;
 114 }
 115
 116 #ifdef EXTREME_DEBUG
 117 static const char *
 118 vtype2string (enum vertextype vtype)
 119 {
 120   switch (vtype)
 121     {
 122     case VTYPE_PSEUDO_IS:
 123       return "pseudo_IS";
 124       break;
 125     case VTYPE_PSEUDO_TE_IS:
 126       return "pseudo_TE-IS";
 127       break;
 128     case VTYPE_NONPSEUDO_IS:
 129       return "IS";
 130       break;
 131     case VTYPE_NONPSEUDO_TE_IS:
 132       return "TE-IS";
 133       break;
 134     case VTYPE_ES:
 135       return "ES";
 136       break;
 137     case VTYPE_IPREACH_INTERNAL:
 138       return "IP internal";
 139       break;
 140     case VTYPE_IPREACH_EXTERNAL:
 141       return "IP external";
 142       break;
 143     case VTYPE_IPREACH_TE:
 144       return "IP TE";
 145       break;
 146 #ifdef HAVE_IPV6
 147     case VTYPE_IP6REACH_INTERNAL:
 148       return "IP6 internal";
 149       break;
 150     case VTYPE_IP6REACH_EXTERNAL:
 151       return "IP6 external";
 152       break;
 153 #endif /* HAVE_IPV6 */
 154     default:
 155       return "UNKNOWN";
 156     }
 157   return NULL;                  /* Not reached */
 158 }
 159
 160 static const char *
 161 vid2string (struct isis_vertex *vertex, u_char * buff)
 162 {
 163   switch (vertex->type)
 164     {
 165     case VTYPE_PSEUDO_IS:
 166     case VTYPE_PSEUDO_TE_IS:
 167       return rawlspid_print (vertex->N.id);
 168       break;
 169     case VTYPE_NONPSEUDO_IS:
 170     case VTYPE_NONPSEUDO_TE_IS:
 171     case VTYPE_ES:
 172       return sysid_print (vertex->N.id);
 173       break;
 174     case VTYPE_IPREACH_INTERNAL:
 175     case VTYPE_IPREACH_EXTERNAL:
 176     case VTYPE_IPREACH_TE:
 177 #ifdef HAVE_IPV6
 178     case VTYPE_IP6REACH_INTERNAL:
 179     case VTYPE_IP6REACH_EXTERNAL:
 180 #endif /* HAVE_IPV6 */
 181       prefix2str ((struct prefix *) &vertex->N.prefix, (char *) buff, BUFSIZ);
 182       break;
 183     default:
 184       return "UNKNOWN";
 185     }
 186
 187   return (char *) buff;
 188 }
 189 #endif /* EXTREME_DEBUG */
 190
 191 static struct isis_spftree *
 192 isis_spftree_new ()
 193 {
 194   struct isis_spftree *tree;
 195
 196   tree = XCALLOC (MTYPE_ISIS_SPFTREE, sizeof (struct isis_spftree));
 197   if (tree == NULL)
 198     {
 199       zlog_err ("ISIS-Spf: isis_spftree_new Out of memory!");
 200       return NULL;
 201     }
 202
 203   tree->tents = list_new ();
 204   tree->paths = list_new ();
 205   return tree;
 206 }
 207
 208 static void
 209 isis_vertex_del (struct isis_vertex *vertex)
 210 {
 211   list_delete (vertex->Adj_N);
 212
 213   XFREE (MTYPE_ISIS_VERTEX, vertex);
 214
 215   return;
 216 }
 217
 218 #if 0 /* HT: Not used yet. */
 219 static void
 220 isis_spftree_del (struct isis_spftree *spftree)
 221 {
 222   spftree->tents->del = (void (*)(void *)) isis_vertex_del;
 223   list_delete (spftree->tents);
 224
 225   spftree->paths->del = (void (*)(void *)) isis_vertex_del;
 226   list_delete (spftree->paths);
 227
 228   XFREE (MTYPE_ISIS_SPFTREE, spftree);
 229
 230   return;
 231 }
 232 #endif
 233
 234 void
 235 spftree_area_init (struct isis_area *area)
 236 {
 237   if ((area->is_type & IS_LEVEL_1) && area->spftree[0] == NULL)
 238     {
 239       area->spftree[0] = isis_spftree_new ();
 240 #ifdef HAVE_IPV6
 241       area->spftree6[0] = isis_spftree_new ();
 242 #endif
 243
 244       /*    thread_add_timer (master, isis_run_spf_l1, area,
 245          isis_jitter (PERIODIC_SPF_INTERVAL, 10)); */
 246     }
 247
 248   if ((area->is_type & IS_LEVEL_2) && area->spftree[1] == NULL)
 249     {
 250       area->spftree[1] = isis_spftree_new ();
 251 #ifdef HAVE_IPV6
 252       area->spftree6[1] = isis_spftree_new ();
 253 #endif
 254       /*    thread_add_timer (master, isis_run_spf_l2, area,
 255          isis_jitter (PERIODIC_SPF_INTERVAL, 10)); */
 256     }
 257
 258   return;
 259 }
 260
 261 static struct isis_vertex *
 262 isis_vertex_new (void *id, enum vertextype vtype)
 263 {
 264   struct isis_vertex *vertex;
 265
 266   vertex = XCALLOC (MTYPE_ISIS_VERTEX, sizeof (struct isis_vertex));
 267   if (vertex == NULL)
 268     {
 269       zlog_err ("isis_vertex_new Out of memory!");
 270       return NULL;
 271     }
 272
 273   vertex->type = vtype;
 274   switch (vtype)
 275     {
 276     case VTYPE_ES:
 277     case VTYPE_NONPSEUDO_IS:
 278     case VTYPE_NONPSEUDO_TE_IS:
 279       memcpy (vertex->N.id, (u_char *) id, ISIS_SYS_ID_LEN);
 280       break;
 281     case VTYPE_PSEUDO_IS:
 282     case VTYPE_PSEUDO_TE_IS:
 283       memcpy (vertex->N.id, (u_char *) id, ISIS_SYS_ID_LEN + 1);
 284       break;
 285     case VTYPE_IPREACH_INTERNAL:
 286     case VTYPE_IPREACH_EXTERNAL:
 287     case VTYPE_IPREACH_TE:
 288 #ifdef HAVE_IPV6
 289     case VTYPE_IP6REACH_INTERNAL:
 290     case VTYPE_IP6REACH_EXTERNAL:
 291 #endif /* HAVE_IPV6 */
 292       memcpy (&vertex->N.prefix, (struct prefix *) id,
 293               sizeof (struct prefix));
 294       break;
 295     default:
 296       zlog_err ("WTF!");
 297     }
 298
 299   vertex->Adj_N = list_new ();
 300
 301   return vertex;
 302 }
 303
 304 /*
 305  * Add this IS to the root of SPT
 306  */
 307 static void
 308 isis_spf_add_self (struct isis_spftree *spftree, struct isis_area *area,
 309                    int level)
 310 {
 311   struct isis_vertex *vertex;
 312   struct isis_lsp *lsp;
 313   u_char lspid[ISIS_SYS_ID_LEN + 2];
 314 #ifdef EXTREME_DEBUG
 315   u_char buff[BUFSIZ];
 316 #endif /* EXTREME_DEBUG */
 317   memcpy (lspid, isis->sysid, ISIS_SYS_ID_LEN);
 318   LSP_PSEUDO_ID (lspid) = 0;
 319   LSP_FRAGMENT (lspid) = 0;
 320
 321   lsp = lsp_search (lspid, area->lspdb[level - 1]);
 322
 323   if (lsp == NULL)
 324     zlog_warn ("ISIS-Spf: could not find own l%d LSP!", level);
 325
 326   if (!area->oldmetric)
 327     vertex = isis_vertex_new (isis->sysid, VTYPE_NONPSEUDO_TE_IS);
 328   else
 329     vertex = isis_vertex_new (isis->sysid, VTYPE_NONPSEUDO_IS);
 330
 331   vertex->lsp = lsp;
 332
 333   listnode_add (spftree->paths, vertex);
 334
 335 #ifdef EXTREME_DEBUG
 336   zlog_debug ("ISIS-Spf: added this IS  %s %s depth %d dist %d to PATHS",
 337               vtype2string (vertex->type), vid2string (vertex, buff),
 338               vertex->depth, vertex->d_N);
 339 #endif /* EXTREME_DEBUG */
 340
 341   return;
 342 }
 343
 344 static struct isis_vertex *
 345 isis_find_vertex (struct list *list, void *id, enum vertextype vtype)
 346 {
 347   struct listnode *node;
 348   struct isis_vertex *vertex;
 349   struct prefix *p1, *p2;
 350
 351   for (ALL_LIST_ELEMENTS_RO (list, node, vertex))
 352     {
 353       if (vertex->type != vtype)
 354         continue;
 355       switch (vtype)
 356         {
 357         case VTYPE_ES:
 358         case VTYPE_NONPSEUDO_IS:
 359         case VTYPE_NONPSEUDO_TE_IS:
 360           if (memcmp ((u_char *) id, vertex->N.id, ISIS_SYS_ID_LEN) == 0)
 361             return vertex;
 362           break;
 363         case VTYPE_PSEUDO_IS:
 364         case VTYPE_PSEUDO_TE_IS:
 365           if (memcmp ((u_char *) id, vertex->N.id, ISIS_SYS_ID_LEN + 1) == 0)
 366             return vertex;
 367           break;
 368         case VTYPE_IPREACH_INTERNAL:
 369         case VTYPE_IPREACH_EXTERNAL:
 370         case VTYPE_IPREACH_TE:
 371 #ifdef HAVE_IPV6
 372         case VTYPE_IP6REACH_INTERNAL:
 373         case VTYPE_IP6REACH_EXTERNAL:
 374 #endif /* HAVE_IPV6 */
 375           p1 = (struct prefix *) id;
 376           p2 = (struct prefix *) &vertex->N.id;
 377           if (p1->family == p2->family && p1->prefixlen == p2->prefixlen &&
 378               memcmp (&p1->u.prefix, &p2->u.prefix,
 379                       PSIZE (p1->prefixlen)) == 0)
 380             return vertex;
 381           break;
 382         }
 383     }
 384
 385   return NULL;
 386 }
 387
 388 /*
 389  * Add a vertex to TENT sorted by cost and by vertextype on tie break situation
 390  */
 391 static struct isis_vertex *
 392 isis_spf_add2tent (struct isis_spftree *spftree, enum vertextype vtype,
 393                    void *id, struct isis_adjacency *adj, u_int32_t cost,
 394                    int depth, int family)
 395 {
 396   struct isis_vertex *vertex, *v;
 397   struct listnode *node;
 398 #ifdef EXTREME_DEBUG
 399   u_char buff[BUFSIZ];
 400 #endif
 401
 402   vertex = isis_vertex_new (id, vtype);
 403   vertex->d_N = cost;
 404   vertex->depth = depth;
 405
 406   if (adj)
 407     listnode_add (vertex->Adj_N, adj);
 408 #ifdef EXTREME_DEBUG
 409   zlog_debug ("ISIS-Spf: add to TENT  %s %s depth %d dist %d",
 410               vtype2string (vertex->type), vid2string (vertex, buff),
 411               vertex->depth, vertex->d_N);
 412 #endif /* EXTREME_DEBUG */
 413   listnode_add (spftree->tents, vertex);
 414   if (list_isempty (spftree->tents))
 415     {
 416       listnode_add (spftree->tents, vertex);
 417       return vertex;
 418     }
 419
 420   /* XXX: This cant use the standard ALL_LIST_ELEMENT macro */
 421   for (node = listhead (spftree->tents); node; node = listnextnode (node))
 422     {
 423       v = listgetdata (node);
 424       if (v->d_N > vertex->d_N)
 425         {
 426           list_add_node_prev (spftree->tents, node, vertex);
 427           break;
 428         }
 429       else if (v->d_N == vertex->d_N)
 430         {
 431           /*  Tie break, add according to type */
 432           while (v && v->d_N == vertex->d_N && v->type > vertex->type)
 433             {
 434               if (v->type > vertex->type)
 435                 {
 436                   break;
 437                 }
 438               /* XXX: this seems dubious, node is the loop iterator */
 439               node = listnextnode (node);
 440               (node) ? (v = listgetdata (node)) : (v = NULL);
 441             }
 442           list_add_node_prev (spftree->tents, node, vertex);
 443           break;
 444         }
 445       else if (node->next == NULL)
 446         {
 447           list_add_node_next (spftree->tents, node, vertex);
 448           break;
 449         }
 450     }
 451   return vertex;
 452 }
 453
 454 static struct isis_vertex *
 455 isis_spf_add_local (struct isis_spftree *spftree, enum vertextype vtype,
 456                     void *id, struct isis_adjacency *adj, u_int32_t cost,
 457                     int family)
 458 {
 459   struct isis_vertex *vertex;
 460
 461   vertex = isis_find_vertex (spftree->tents, id, vtype);
 462
 463   if (vertex)
 464     {
 465       /* C.2.5   c) */
 466       if (vertex->d_N == cost)
 467         {
 468           if (adj)
 469             listnode_add (vertex->Adj_N, adj);
 470           /*       d) */
 471           if (listcount (vertex->Adj_N) > ISIS_MAX_PATH_SPLITS)
 472             remove_excess_adjs (vertex->Adj_N);
 473         }
 474       /*         f) */
 475       else if (vertex->d_N > cost)
 476         {
 477           listnode_delete (spftree->tents, vertex);
 478           goto add2tent;
 479         }
 480       /*       e) do nothing */
 481       return vertex;
 482     }
 483
 484 add2tent:
 485   return isis_spf_add2tent (spftree, vtype, id, adj, cost, 1, family);
 486 }
 487
 488 static void
 489 process_N (struct isis_spftree *spftree, enum vertextype vtype, void *id,
 490            u_int16_t dist, u_int16_t depth, struct isis_adjacency *adj,
 491            int family)
 492 {
 493   struct isis_vertex *vertex;
 494 #ifdef EXTREME_DEBUG
 495   u_char buff[255];
 496 #endif
 497
 498   /* C.2.6 b)    */
 499   if (dist > MAX_PATH_METRIC)
 500     return;
 501   /*       c)    */
 502   vertex = isis_find_vertex (spftree->paths, id, vtype);
 503   if (vertex)
 504     {
 505 #ifdef EXTREME_DEBUG
 506       zlog_debug ("ISIS-Spf: process_N  %s %s dist %d already found from PATH",
 507                   vtype2string (vtype), vid2string (vertex, buff), dist);
 508 #endif /* EXTREME_DEBUG */
 509       assert (dist >= vertex->d_N);
 510       return;
 511     }
 512
 513   vertex = isis_find_vertex (spftree->tents, id, vtype);
 514   /*       d)    */
 515   if (vertex)
 516     {
 517       /*        1) */
 518 #ifdef EXTREME_DEBUG
 519       zlog_debug ("ISIS-Spf: process_N  %s %s dist %d",
 520                   vtype2string (vtype), vid2string (vertex, buff), dist);
 521 #endif /* EXTREME_DEBUG */
 522       if (vertex->d_N == dist)
 523         {
 524           if (adj)
 525             listnode_add (vertex->Adj_N, adj);
 526           /*      2) */
 527           if (listcount (vertex->Adj_N) > ISIS_MAX_PATH_SPLITS)
 528             remove_excess_adjs (vertex->Adj_N);
 529           /*      3) */
 530           return;
 531         }
 532       else if (vertex->d_N < dist)
 533         {
 534           return;
 535           /*      4) */
 536         }
 537       else
 538         {
 539           listnode_delete (spftree->tents, vertex);
 540         }
 541     }
 542
 543   isis_spf_add2tent (spftree, vtype, id, adj, dist, depth, family);
 544   return;
 545 }
 546
 547 /*
 548  * C.2.6 Step 1
 549  */
 550 static int
 551 isis_spf_process_lsp (struct isis_spftree *spftree, struct isis_lsp *lsp,
 552                       uint32_t cost, uint16_t depth, int family)
 553 {
 554   struct listnode *node, *fragnode = NULL;
 555   u_int16_t dist;
 556   struct is_neigh *is_neigh;
 557   struct te_is_neigh *te_is_neigh;
 558   struct ipv4_reachability *ipreach;
 559   struct te_ipv4_reachability *te_ipv4_reach;
 560   enum vertextype vtype;
 561   struct prefix prefix;
 562 #ifdef HAVE_IPV6
 563   struct ipv6_reachability *ip6reach;
 564 #endif /* HAVE_IPV6 */
 565
 566
 567   if (!lsp->adj)
 568     return ISIS_WARNING;
 569   if (lsp->tlv_data.nlpids == NULL || !speaks (lsp->tlv_data.nlpids, family))
 570     return ISIS_OK;
 571
 572 lspfragloop:
 573   if (lsp->lsp_header->seq_num == 0)
 574     {
 575       zlog_warn ("isis_spf_process_lsp(): lsp with 0 seq_num"
 576                  " - do not process");
 577       return ISIS_WARNING;
 578     }
 579
 580   if (!ISIS_MASK_LSP_OL_BIT (lsp->lsp_header->lsp_bits))
 581     {
 582       if (lsp->tlv_data.is_neighs)
 583         {
 584           for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.is_neighs, node, is_neigh))
 585             {
 586               /* C.2.6 a) */
 587               /* Two way connectivity */
 588               if (!memcmp (is_neigh->neigh_id, isis->sysid, ISIS_SYS_ID_LEN))
 589                 continue;
 590               dist = cost + is_neigh->metrics.metric_default;
 591               vtype = LSP_PSEUDO_ID (is_neigh->neigh_id) ? VTYPE_PSEUDO_IS
 592                 : VTYPE_NONPSEUDO_IS;
 593               process_N (spftree, vtype, (void *) is_neigh->neigh_id, dist,
 594                          depth + 1, lsp->adj, family);
 595             }
 596         }
 597       if (lsp->tlv_data.te_is_neighs)
 598         {
 599           for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.te_is_neighs, node,
 600                                      te_is_neigh))
 601             {
 602               uint32_t metric;
 603               if (!memcmp (te_is_neigh->neigh_id, isis->sysid, ISIS_SYS_ID_LEN))
 604                 continue;
 605               memcpy (&metric, te_is_neigh->te_metric, 3);
 606               dist = cost + ntohl (metric << 8);
 607               vtype = LSP_PSEUDO_ID (te_is_neigh->neigh_id) ? VTYPE_PSEUDO_TE_IS
 608                 : VTYPE_NONPSEUDO_TE_IS;
 609               process_N (spftree, vtype, (void *) te_is_neigh->neigh_id, dist,
 610                          depth + 1, lsp->adj, family);
 611             }
 612         }
 613       if (family == AF_INET && lsp->tlv_data.ipv4_int_reachs)
 614         {
 615           prefix.family = AF_INET;
 616           for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.ipv4_int_reachs,
 617                                      node, ipreach))
 618             {
 619               dist = cost + ipreach->metrics.metric_default;
 620               vtype = VTYPE_IPREACH_INTERNAL;
 621               prefix.u.prefix4 = ipreach->prefix;
 622               prefix.prefixlen = ip_masklen (ipreach->mask);
 623               process_N (spftree, vtype, (void *) &prefix, dist, depth + 1,
 624                          lsp->adj, family);
 625             }
 626         }
 627
 628       if (family == AF_INET && lsp->tlv_data.ipv4_ext_reachs)
 629         {
 630           prefix.family = AF_INET;
 631           for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.ipv4_ext_reachs,
 632                                      node, ipreach))
 633             {
 634               dist = cost + ipreach->metrics.metric_default;
 635               vtype = VTYPE_IPREACH_EXTERNAL;
 636               prefix.u.prefix4 = ipreach->prefix;
 637               prefix.prefixlen = ip_masklen (ipreach->mask);
 638               process_N (spftree, vtype, (void *) &prefix, dist, depth + 1,
 639                          lsp->adj, family);
 640             }
 641         }
 642       if (family == AF_INET && lsp->tlv_data.te_ipv4_reachs)
 643         {
 644           prefix.family = AF_INET;
 645           for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.te_ipv4_reachs,
 646                                      node, te_ipv4_reach))
 647             {
 648               dist = cost + ntohl (te_ipv4_reach->te_metric);
 649               vtype = VTYPE_IPREACH_TE;
 650               prefix.u.prefix4 = newprefix2inaddr (&te_ipv4_reach->prefix_start,
 651                                                    te_ipv4_reach->control);
 652               prefix.prefixlen = (te_ipv4_reach->control & 0x3F);
 653               process_N (spftree, vtype, (void *) &prefix, dist, depth + 1,
 654                          lsp->adj, family);
 655             }
 656         }
 657 #ifdef HAVE_IPV6
 658       if (family == AF_INET6 && lsp->tlv_data.ipv6_reachs)
 659         {
 660           prefix.family = AF_INET6;
 661           for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.ipv6_reachs,
 662                                      node, ip6reach))
 663             {
 664               dist = cost + ip6reach->metric;
 665               vtype = (ip6reach->control_info & CTRL_INFO_DISTRIBUTION) ?
 666                 VTYPE_IP6REACH_EXTERNAL : VTYPE_IP6REACH_INTERNAL;
 667               prefix.prefixlen = ip6reach->prefix_len;
 668               memcpy (&prefix.u.prefix6.s6_addr, ip6reach->prefix,
 669                       PSIZE (ip6reach->prefix_len));
 670               process_N (spftree, vtype, (void *) &prefix, dist, depth + 1,
 671                          lsp->adj, family);
 672             }
 673         }
 674 #endif /* HAVE_IPV6 */
 675     }
 676
 677   if (fragnode == NULL)
 678     fragnode = listhead (lsp->lspu.frags);
 679   else
 680     fragnode = listnextnode (fragnode);
 681
 682   if (fragnode)
 683     {
 684       lsp = listgetdata (fragnode);
 685       goto lspfragloop;
 686     }
 687
 688   return ISIS_OK;
 689 }
 690
 691 static int
 692 isis_spf_process_pseudo_lsp (struct isis_spftree *spftree,
 693                              struct isis_lsp *lsp, uint16_t cost,
 694                              uint16_t depth, int family)
 695 {
 696   struct listnode *node, *fragnode = NULL;
 697   struct is_neigh *is_neigh;
 698   struct te_is_neigh *te_is_neigh;
 699   enum vertextype vtype;
 700
 701 pseudofragloop:
 702
 703   if (lsp->lsp_header->seq_num == 0)
 704     {
 705       zlog_warn ("isis_spf_process_pseudo_lsp(): lsp with 0 seq_num"
 706                  " - do not process");
 707       return ISIS_WARNING;
 708     }
 709
 710   if (lsp->tlv_data.is_neighs)
 711     for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.is_neighs, node, is_neigh))
 712       {
 713         vtype = LSP_PSEUDO_ID (is_neigh->neigh_id) ? VTYPE_PSEUDO_IS
 714           : VTYPE_NONPSEUDO_IS;
 715         /* Two way connectivity */
 716         if (!memcmp (is_neigh->neigh_id, isis->sysid, ISIS_SYS_ID_LEN))
 717           continue;
 718         if (isis_find_vertex
 719             (spftree->tents, (void *) is_neigh->neigh_id, vtype) == NULL
 720             && isis_find_vertex (spftree->paths, (void *) is_neigh->neigh_id,
 721                                vtype) == NULL)
 722           {
 723             /* C.2.5 i) */
 724             isis_spf_add2tent (spftree, vtype, is_neigh->neigh_id, lsp->adj,
 725                              cost, depth, family);
 726           }
 727       }
 728   if (lsp->tlv_data.te_is_neighs)
 729     for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.te_is_neighs, node, te_is_neigh))
 730       {
 731         vtype = LSP_PSEUDO_ID (te_is_neigh->neigh_id) ? VTYPE_PSEUDO_TE_IS
 732           : VTYPE_NONPSEUDO_TE_IS;
 733         /* Two way connectivity */
 734         if (!memcmp (te_is_neigh->neigh_id, isis->sysid, ISIS_SYS_ID_LEN))
 735           continue;
 736         if (isis_find_vertex
 737             (spftree->tents, (void *) te_is_neigh->neigh_id, vtype) == NULL
 738             && isis_find_vertex (spftree->paths, (void *) te_is_neigh->neigh_id,
 739                                  vtype) == NULL)
 740           {
 741             /* C.2.5 i) */
 742             isis_spf_add2tent (spftree, vtype, te_is_neigh->neigh_id, lsp->adj,
 743                                cost, depth, family);
 744           }
 745       }
 746
 747   if (fragnode == NULL)
 748     fragnode = listhead (lsp->lspu.frags);
 749   else
 750     fragnode = listnextnode (fragnode);
 751
 752   if (fragnode)
 753     {
 754       lsp = listgetdata (fragnode);
 755       goto pseudofragloop;
 756     }
 757
 758   return ISIS_OK;
 759 }
 760
 761 static int
 762 isis_spf_preload_tent (struct isis_spftree *spftree,
 763                        struct isis_area *area, int level, int family)
 764 {
 765   struct isis_vertex *vertex;
 766   struct isis_circuit *circuit;
 767   struct listnode *cnode, *anode, *ipnode;
 768   struct isis_adjacency *adj;
 769   struct isis_lsp *lsp;
 770   struct list *adj_list;
 771   struct list *adjdb;
 772   struct prefix_ipv4 *ipv4;
 773   struct prefix prefix;
 774   int retval = ISIS_OK;
 775   u_char lsp_id[ISIS_SYS_ID_LEN + 2];
 776 #ifdef HAVE_IPV6
 777   struct prefix_ipv6 *ipv6;
 778 #endif /* HAVE_IPV6 */
 779
 780   for (ALL_LIST_ELEMENTS_RO (area->circuit_list, cnode, circuit))
 781     {
 782       if (circuit->state != C_STATE_UP)
 783         continue;
 784       if (!(circuit->circuit_is_type & level))
 785         continue;
 786       if (family == AF_INET && !circuit->ip_router)
 787         continue;
 788 #ifdef HAVE_IPV6
 789       if (family == AF_INET6 && !circuit->ipv6_router)
 790         continue;
 791 #endif /* HAVE_IPV6 */
 792       /*
 793        * Add IP(v6) addresses of this circuit
 794        */
 795       if (family == AF_INET)
 796         {
 797           prefix.family = AF_INET;
 798           for (ALL_LIST_ELEMENTS_RO (circuit->ip_addrs, ipnode, ipv4))
 799             {
 800               prefix.u.prefix4 = ipv4->prefix;
 801               prefix.prefixlen = ipv4->prefixlen;
 802               isis_spf_add_local (spftree, VTYPE_IPREACH_INTERNAL, &prefix,
 803                                   NULL, 0, family);
 804             }
 805         }
 806 #ifdef HAVE_IPV6
 807       if (family == AF_INET6)
 808         {
 809           prefix.family = AF_INET6;
 810           for (ALL_LIST_ELEMENTS_RO (circuit->ipv6_non_link, ipnode, ipv6))
 811             {
 812               prefix.prefixlen = ipv6->prefixlen;
 813               prefix.u.prefix6 = ipv6->prefix;
 814               isis_spf_add_local (spftree, VTYPE_IP6REACH_INTERNAL,
 815                                   &prefix, NULL, 0, family);
 816             }
 817         }
 818 #endif /* HAVE_IPV6 */
 819       if (circuit->circ_type == CIRCUIT_T_BROADCAST)
 820         {
 821           /*
 822            * Add the adjacencies
 823            */
 824           adj_list = list_new ();
 825           adjdb = circuit->u.bc.adjdb[level - 1];
 826           isis_adj_build_up_list (adjdb, adj_list);
 827           if (listcount (adj_list) == 0)
 828             {
 829               list_delete (adj_list);
 830               if (isis->debugs & DEBUG_SPF_EVENTS)
 831                 zlog_debug ("ISIS-Spf: no L%d adjacencies on circuit %s",
 832                             level, circuit->interface->name);
 833               continue;
 834             }
 835           anode = listhead (adj_list);
 836           while (anode)
 837             {
 838               adj = listgetdata (anode);
 839               if (!speaks (&adj->nlpids, family))
 840                 {
 841                   anode = listnextnode (anode);
 842                   continue;
 843                 }
 844               switch (adj->sys_type)
 845                 {
 846                 case ISIS_SYSTYPE_ES:
 847                   isis_spf_add_local (spftree, VTYPE_ES, adj->sysid, adj,
 848                                       circuit->te_metric[level - 1], family);
 849                   break;
 850                 case ISIS_SYSTYPE_IS:
 851                 case ISIS_SYSTYPE_L1_IS:
 852                 case ISIS_SYSTYPE_L2_IS:
 853                   vertex =
 854                     isis_spf_add_local (spftree, VTYPE_NONPSEUDO_IS,
 855                                         adj->sysid, adj,
 856                                         circuit->te_metric[level - 1], family);
 857                   memcpy (lsp_id, adj->sysid, ISIS_SYS_ID_LEN);
 858                   LSP_PSEUDO_ID (lsp_id) = 0;
 859                   LSP_FRAGMENT (lsp_id) = 0;
 860                   lsp = lsp_search (lsp_id, area->lspdb[level - 1]);
 861                   if (!lsp)
 862                     zlog_warn ("No lsp found for IS adjacency");
 863                   /*          else {
 864                      isis_spf_process_lsp (spftree, lsp, vertex->d_N, 1, family);
 865                      } */
 866                   break;
 867                 case ISIS_SYSTYPE_UNKNOWN:
 868                 default:
 869                   zlog_warn ("isis_spf_preload_tent unknow adj type");
 870                 }
 871               anode = listnextnode (anode);
 872             }
 873           list_delete (adj_list);
 874           /*
 875            * Add the pseudonode
 876            */
 877           if (level == 1)
 878             memcpy (lsp_id, circuit->u.bc.l1_desig_is, ISIS_SYS_ID_LEN + 1);
 879           else
 880             memcpy (lsp_id, circuit->u.bc.l2_desig_is, ISIS_SYS_ID_LEN + 1);
 881           lsp = lsp_search (lsp_id, area->lspdb[level - 1]);
 882           adj = isis_adj_lookup (lsp_id, adjdb);
 883           /* if no adj, we are the dis or error */
 884           if (!adj && !circuit->u.bc.is_dr[level - 1])
 885             {
 886               zlog_warn ("ISIS-Spf: No adjacency found for DR");
 887             }
 888           if (lsp == NULL || lsp->lsp_header->rem_lifetime == 0)
 889             {
 890               zlog_warn ("ISIS-Spf: No lsp found for DR");
 891             }
 892           else
 893             {
 894               isis_spf_process_pseudo_lsp (spftree, lsp,
 895                                   circuit->te_metric[level - 1], 0, family);
 896
 897             }
 898         }
 899       else if (circuit->circ_type == CIRCUIT_T_P2P)
 900         {
 901           adj = circuit->u.p2p.neighbor;
 902           if (!adj)
 903             continue;
 904           switch (adj->sys_type)
 905             {
 906             case ISIS_SYSTYPE_ES:
 907               isis_spf_add_local (spftree, VTYPE_ES, adj->sysid, adj,
 908                                   circuit->te_metric[level - 1], family);
 909               break;
 910             case ISIS_SYSTYPE_IS:
 911             case ISIS_SYSTYPE_L1_IS:
 912             case ISIS_SYSTYPE_L2_IS:
 913               if (speaks (&adj->nlpids, family))
 914                 isis_spf_add_local (spftree, VTYPE_NONPSEUDO_IS, adj->sysid,
 915                                     adj, circuit->te_metric[level - 1],
 916                                     family);
 917               break;
 918             case ISIS_SYSTYPE_UNKNOWN:
 919             default:
 920               zlog_warn ("isis_spf_preload_tent unknow adj type");
 921               break;
 922             }
 923         }
 924       else
 925         {
 926           zlog_warn ("isis_spf_preload_tent unsupported media");
 927           retval = ISIS_WARNING;
 928         }
 929
 930     }
 931
 932   return retval;
 933 }
 934
 935 /*
 936  * The parent(s) for vertex is set when added to TENT list
 937  * now we just put the child pointer(s) in place
 938  */
 939 static void
 940 add_to_paths (struct isis_spftree *spftree, struct isis_vertex *vertex,
 941               struct isis_area *area, int level)
 942 {
 943 #ifdef EXTREME_DEBUG
 944   u_char buff[BUFSIZ];
 945 #endif /* EXTREME_DEBUG */
 946   listnode_add (spftree->paths, vertex);
 947
 948 #ifdef EXTREME_DEBUG
 949   zlog_debug ("ISIS-Spf: added  %s %s depth %d dist %d to PATHS",
 950               vtype2string (vertex->type), vid2string (vertex, buff),
 951               vertex->depth, vertex->d_N);
 952 #endif /* EXTREME_DEBUG */
 953   if (vertex->type > VTYPE_ES)
 954     {
 955       if (listcount (vertex->Adj_N) > 0)
 956         isis_route_create ((struct prefix *) &vertex->N.prefix, vertex->d_N,
 957                            vertex->depth, vertex->Adj_N, area, level);
 958       else if (isis->debugs & DEBUG_SPF_EVENTS)
 959         zlog_debug ("ISIS-Spf: no adjacencies do not install route");
 960     }
 961
 962   return;
 963 }
 964
 965 static void
 966 init_spt (struct isis_spftree *spftree)
 967 {
 968   spftree->tents->del = spftree->paths->del = (void (*)(void *)) isis_vertex_del;
 969   list_delete_all_node (spftree->tents);
 970   list_delete_all_node (spftree->paths);
 971   spftree->tents->del = spftree->paths->del = NULL;
 972
 973   return;
 974 }
 975
 976 static int
 977 isis_run_spf (struct isis_area *area, int level, int family)
 978 {
 979   int retval = ISIS_OK;
 980   struct listnode *node;
 981   struct isis_vertex *vertex;
 982   struct isis_spftree *spftree = NULL;
 983   u_char lsp_id[ISIS_SYS_ID_LEN + 2];
 984   struct isis_lsp *lsp;
 985   struct route_table *table = NULL;
 986   struct route_node *rode;
 987   struct isis_route_info *rinfo;
 988
 989   if (family == AF_INET)
 990     spftree = area->spftree[level - 1];
 991 #ifdef HAVE_IPV6
 992   else if (family == AF_INET6)
 993     spftree = area->spftree6[level - 1];
 994 #endif
 995
 996   assert (spftree);
 997
 998   /* Make all routes in current route table inactive. */
 999   if (family == AF_INET)
1000     table = area->route_table[level - 1];
1001 #ifdef HAVE_IPV6
1002   else if (family == AF_INET6)
1003     table = area->route_table6[level - 1];
1004 #endif
1005
1006   for (rode = route_top (table); rode; rode = route_next (rode))
1007     {
1008       if (rode->info == NULL)
1009         continue;
1010       rinfo = rode->info;
1011
1012       UNSET_FLAG (rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE);
1013     }
1014
1015   /*
1016    * C.2.5 Step 0
1017    */
1018   init_spt (spftree);
1019   /*              a) */
1020   isis_spf_add_self (spftree, area, level);
1021   /*              b) */
1022   retval = isis_spf_preload_tent (spftree, area, level, family);
1023
1024   /*
1025    * C.2.7 Step 2
1026    */
1027   if (listcount (spftree->tents) == 0)
1028     {
1029       zlog_warn ("ISIS-Spf: TENT is empty");
1030       goto out;
1031     }
1032
1033   while (listcount (spftree->tents) > 0)
1034     {
1035       node = listhead (spftree->tents);
1036       vertex = listgetdata (node);
1037       /* Remove from tent list */
1038       list_delete_node (spftree->tents, node);
1039       if (isis_find_vertex (spftree->paths, vertex->N.id, vertex->type))
1040         continue;
1041       add_to_paths (spftree, vertex, area, level);
1042       if (vertex->type == VTYPE_PSEUDO_IS ||
1043           vertex->type == VTYPE_NONPSEUDO_IS)
1044         {
1045           memcpy (lsp_id, vertex->N.id, ISIS_SYS_ID_LEN + 1);
1046           LSP_FRAGMENT (lsp_id) = 0;
1047           lsp = lsp_search (lsp_id, area->lspdb[level - 1]);
1048           if (lsp)
1049             {
1050               if (LSP_PSEUDO_ID (lsp_id))
1051                 {
1052                   isis_spf_process_pseudo_lsp (spftree, lsp, vertex->d_N,
1053                                                vertex->depth, family);
1054
1055                 }
1056               else
1057                 {
1058                   isis_spf_process_lsp (spftree, lsp, vertex->d_N,
1059                                         vertex->depth, family);
1060                 }
1061             }
1062           else
1063             {
1064               zlog_warn ("ISIS-Spf: No LSP found for %s",
1065                          rawlspid_print (lsp_id));
1066             }
1067         }
1068     }
1069
1070 out:
1071   thread_add_event (master, isis_route_validate, area, 0);
1072   spftree->lastrun = time (NULL);
1073   spftree->pending = 0;
1074
1075   return retval;
1076 }
1077
1078 int
1079 isis_run_spf_l1 (struct thread *thread)
1080 {
1081   struct isis_area *area;
1082   int retval = ISIS_OK;
1083
1084   area = THREAD_ARG (thread);
1085   assert (area);
1086
1087   area->spftree[0]->t_spf = NULL;
1088
1089   if (!(area->is_type & IS_LEVEL_1))
1090     {
1091       if (isis->debugs & DEBUG_SPF_EVENTS)
1092         zlog_warn ("ISIS-SPF (%s) area does not share level",
1093                    area->area_tag);
1094       return ISIS_WARNING;
1095     }
1096
1097   if (isis->debugs & DEBUG_SPF_EVENTS)
1098     zlog_debug ("ISIS-Spf (%s) L1 SPF needed, periodic SPF", area->area_tag);
1099
1100   if (area->ip_circuits)
1101     retval = isis_run_spf (area, 1, AF_INET);
1102
1103   THREAD_TIMER_ON (master, area->spftree[0]->t_spf, isis_run_spf_l1, area,
1104                    isis_jitter (PERIODIC_SPF_INTERVAL, 10));
1105
1106   return retval;
1107 }
1108
1109 int
1110 isis_run_spf_l2 (struct thread *thread)
1111 {
1112   struct isis_area *area;
1113   int retval = ISIS_OK;
1114
1115   area = THREAD_ARG (thread);
1116   assert (area);
1117
1118   area->spftree[1]->t_spf = NULL;
1119
1120   if (!(area->is_type & IS_LEVEL_2))
1121     {
1122       if (isis->debugs & DEBUG_SPF_EVENTS)
1123         zlog_warn ("ISIS-SPF (%s) area does not share level", area->area_tag);
1124       return ISIS_WARNING;
1125     }
1126
1127   if (isis->debugs & DEBUG_SPF_EVENTS)
1128     zlog_debug ("ISIS-Spf (%s) L2 SPF needed, periodic SPF", area->area_tag);
1129
1130   if (area->ip_circuits)
1131     retval = isis_run_spf (area, 2, AF_INET);
1132
1133   THREAD_TIMER_ON (master, area->spftree[1]->t_spf, isis_run_spf_l2, area,
1134                    isis_jitter (PERIODIC_SPF_INTERVAL, 10));
1135
1136   return retval;
1137 }
1138
1139 int
1140 isis_spf_schedule (struct isis_area *area, int level)
1141 {
1142   int retval = ISIS_OK;
1143   struct isis_spftree *spftree = area->spftree[level - 1];
1144   time_t diff, now = time (NULL);
1145
1146   if (spftree->pending)
1147     return retval;
1148
1149   diff = now - spftree->lastrun;
1150
1151   /* FIXME: let's wait a minute before doing the SPF */
1152   if (now - isis->uptime < 60 || isis->uptime == 0)
1153     {
1154       if (level == 1)
1155         THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l1, area, 60);
1156       else
1157         THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l2, area, 60);
1158
1159       spftree->pending = 1;
1160       return retval;
1161     }
1162
1163   THREAD_TIMER_OFF (spftree->t_spf);
1164
1165   if (diff < MINIMUM_SPF_INTERVAL)
1166     {
1167       if (level == 1)
1168         THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l1, area,
1169                          MINIMUM_SPF_INTERVAL - diff);
1170       else
1171         THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l2, area,
1172                          MINIMUM_SPF_INTERVAL - diff);
1173
1174       spftree->pending = 1;
1175     }
1176   else
1177     {
1178       spftree->pending = 0;
1179       retval = isis_run_spf (area, level, AF_INET);
1180       if (level == 1)
1181         THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l1, area,
1182                          isis_jitter (PERIODIC_SPF_INTERVAL, 10));
1183       else
1184         THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l2, area,
1185                          isis_jitter (PERIODIC_SPF_INTERVAL, 10));
1186     }
1187
1188   return retval;
1189 }
1190
1191 #ifdef HAVE_IPV6
1192 static int
1193 isis_run_spf6_l1 (struct thread *thread)
1194 {
1195   struct isis_area *area;
1196   int retval = ISIS_OK;
1197
1198   area = THREAD_ARG (thread);
1199   assert (area);
1200
1201   area->spftree6[0]->t_spf = NULL;
1202
1203   if (!(area->is_type & IS_LEVEL_1))
1204     {
1205       if (isis->debugs & DEBUG_SPF_EVENTS)
1206         zlog_warn ("ISIS-SPF (%s) area does not share level", area->area_tag);
1207       return ISIS_WARNING;
1208     }
1209
1210   if (isis->debugs & DEBUG_SPF_EVENTS)
1211     zlog_debug ("ISIS-Spf (%s) L1 SPF needed, periodic SPF", area->area_tag);
1212
1213   if (area->ipv6_circuits)
1214     retval = isis_run_spf (area, 1, AF_INET6);
1215
1216   THREAD_TIMER_ON (master, area->spftree6[0]->t_spf, isis_run_spf6_l1, area,
1217                    isis_jitter (PERIODIC_SPF_INTERVAL, 10));
1218
1219   return retval;
1220 }
1221
1222 static int
1223 isis_run_spf6_l2 (struct thread *thread)
1224 {
1225   struct isis_area *area;
1226   int retval = ISIS_OK;
1227
1228   area = THREAD_ARG (thread);
1229   assert (area);
1230
1231   area->spftree6[1]->t_spf = NULL;
1232
1233   if (!(area->is_type & IS_LEVEL_2))
1234     {
1235       if (isis->debugs & DEBUG_SPF_EVENTS)
1236         zlog_warn ("ISIS-SPF (%s) area does not share level", area->area_tag);
1237       return ISIS_WARNING;
1238     }
1239
1240   if (isis->debugs & DEBUG_SPF_EVENTS)
1241     zlog_debug ("ISIS-Spf (%s) L2 SPF needed, periodic SPF.", area->area_tag);
1242
1243   if (area->ipv6_circuits)
1244     retval = isis_run_spf (area, 2, AF_INET6);
1245
1246   THREAD_TIMER_ON (master, area->spftree6[1]->t_spf, isis_run_spf6_l2, area,
1247                    isis_jitter (PERIODIC_SPF_INTERVAL, 10));
1248
1249   return retval;
1250 }
1251
1252 int
1253 isis_spf_schedule6 (struct isis_area *area, int level)
1254 {
1255   int retval = ISIS_OK;
1256   struct isis_spftree *spftree = area->spftree6[level - 1];
1257   time_t diff, now = time (NULL);
1258
1259   if (spftree->pending)
1260     return retval;
1261
1262   diff = now - spftree->lastrun;
1263
1264   /* FIXME: let's wait a minute before doing the SPF */
1265   if (now - isis->uptime < 60 || isis->uptime == 0)
1266     {
1267       if (level == 1)
1268         THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l1, area, 60);
1269       else
1270         THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l2, area, 60);
1271
1272       spftree->pending = 1;
1273       return retval;
1274     }
1275
1276   THREAD_TIMER_OFF (spftree->t_spf);
1277
1278   if (diff < MINIMUM_SPF_INTERVAL)
1279     {
1280       if (level == 1)
1281         THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l1, area,
1282                          MINIMUM_SPF_INTERVAL - diff);
1283       else
1284         THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l2, area,
1285                          MINIMUM_SPF_INTERVAL - diff);
1286
1287       spftree->pending = 1;
1288     }
1289   else
1290     {
1291       spftree->pending = 0;
1292       retval = isis_run_spf (area, level, AF_INET6);
1293
1294       if (level == 1)
1295         THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l1, area,
1296                          isis_jitter (PERIODIC_SPF_INTERVAL, 10));
1297       else
1298         THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l2, area,
1299                          isis_jitter (PERIODIC_SPF_INTERVAL, 10));
1300     }
1301
1302   return retval;
1303 }
1304 #endif
1305
1306 static void
1307 isis_print_paths (struct vty *vty, struct list *paths)
1308 {
1309   struct listnode *node;
1310   struct isis_vertex *vertex;
1311   struct isis_dynhn *dyn, *nh_dyn = NULL;
1312   struct isis_adjacency *adj;
1313 #if 0
1314   u_char buff[255];
1315 #endif /* 0 */
1316
1317   vty_out (vty, "System Id            Metric     Next-Hop"
1318            "             Interface   SNPA%s", VTY_NEWLINE);
1319
1320   for (ALL_LIST_ELEMENTS_RO (paths, node, vertex))
1321     {
1322       if (vertex->type != VTYPE_NONPSEUDO_IS)
1323         continue;
1324       if (memcmp (vertex->N.id, isis->sysid, ISIS_SYS_ID_LEN) == 0)
1325         {
1326           vty_out (vty, "%s             --%s", host.name?host.name:"",
1327                    VTY_NEWLINE);
1328         }
1329       else
1330         {
1331           dyn = dynhn_find_by_id ((u_char *) vertex->N.id);
1332           adj = listgetdata (listhead (vertex->Adj_N));
1333           if (adj)
1334             {
1335               nh_dyn = dynhn_find_by_id (adj->sysid);
1336               vty_out (vty, "%-20s %-10u %-20s %-11s %-5s%s",
1337                        (dyn != NULL) ? dyn->name.name :
1338                        (const u_char *)rawlspid_print ((u_char *) vertex->N.id),
1339                        vertex->d_N, (nh_dyn != NULL) ? nh_dyn->name.name :
1340                        (const u_char *)rawlspid_print (adj->sysid),
1341                        adj->circuit->interface->name,
1342                        snpa_print (adj->snpa), VTY_NEWLINE);
1343             }
1344           else
1345             {
1346               vty_out (vty, "%s              %u %s", dyn ? dyn->name.name :
1347                        (const u_char *) rawlspid_print (vertex->N.id),
1348                        vertex->d_N, VTY_NEWLINE);
1349             }
1350         }
1351 #if 0
1352       vty_out (vty, "%s %s %u %s", vtype2string (vertex->type),
1353                vid2string (vertex, buff), vertex->d_N, VTY_NEWLINE);
1354 #endif
1355     }
1356 }
1357
1358 DEFUN (show_isis_topology,
1359        show_isis_topology_cmd,
1360        "show isis topology",
1361        SHOW_STR
1362        "IS-IS information\n"
1363        "IS-IS paths to Intermediate Systems\n")
1364 {
1365   struct listnode *node;
1366   struct isis_area *area;
1367   int level;
1368
1369   if (!isis->area_list || isis->area_list->count == 0)
1370     return CMD_SUCCESS;
1371
1372   for (ALL_LIST_ELEMENTS_RO (isis->area_list, node, area))
1373     {
1374       vty_out (vty, "Area %s:%s", area->area_tag ? area->area_tag : "null",
1375                VTY_NEWLINE);
1376
1377       for (level = 0; level < ISIS_LEVELS; level++)
1378         {
1379           if (area->ip_circuits > 0 && area->spftree[level]
1380               && area->spftree[level]->paths->count > 0)
1381             {
1382               vty_out (vty, "IS-IS paths to level-%d routers that speak IP%s",
1383                        level + 1, VTY_NEWLINE);
1384               isis_print_paths (vty, area->spftree[level]->paths);
1385             }
1386 #ifdef HAVE_IPV6
1387           if (area->ipv6_circuits > 0 && area->spftree6[level]
1388               && area->spftree6[level]->paths->count > 0)
1389             {
1390               vty_out (vty,
1391                        "IS-IS paths to level-%d routers that speak IPv6%s",
1392                        level + 1, VTY_NEWLINE);
1393               isis_print_paths (vty, area->spftree6[level]->paths);
1394             }
1395 #endif /* HAVE_IPV6 */
1396         }
1397     }
1398
1399   return CMD_SUCCESS;
1400 }
1401
1402 DEFUN (show_isis_topology_l1,
1403        show_isis_topology_l1_cmd,
1404        "show isis topology level-1",
1405        SHOW_STR
1406        "IS-IS information\n"
1407        "IS-IS paths to Intermediate Systems\n"
1408        "Paths to all level-1 routers in the area\n")
1409 {
1410   struct listnode *node;
1411   struct isis_area *area;
1412
1413   if (!isis->area_list || isis->area_list->count == 0)
1414     return CMD_SUCCESS;
1415
1416   for (ALL_LIST_ELEMENTS_RO (isis->area_list, node, area))
1417     {
1418       vty_out (vty, "Area %s:%s", area->area_tag ? area->area_tag : "null",
1419                VTY_NEWLINE);
1420
1421       if (area->ip_circuits > 0 && area->spftree[0]
1422           && area->spftree[0]->paths->count > 0)
1423         {
1424           vty_out (vty, "IS-IS paths to level-1 routers that speak IP%s",
1425                    VTY_NEWLINE);
1426           isis_print_paths (vty, area->spftree[0]->paths);
1427         }
1428 #ifdef HAVE_IPV6
1429       if (area->ipv6_circuits > 0 && area->spftree6[0]
1430           && area->spftree6[0]->paths->count > 0)
1431         {
1432           vty_out (vty, "IS-IS paths to level-1 routers that speak IPv6%s",
1433                    VTY_NEWLINE);
1434           isis_print_paths (vty, area->spftree6[0]->paths);
1435         }
1436 #endif /* HAVE_IPV6 */
1437     }
1438
1439   return CMD_SUCCESS;
1440 }
1441
1442 DEFUN (show_isis_topology_l2,
1443        show_isis_topology_l2_cmd,
1444        "show isis topology level-2",
1445        SHOW_STR
1446        "IS-IS information\n"
1447        "IS-IS paths to Intermediate Systems\n"
1448        "Paths to all level-2 routers in the domain\n")
1449 {
1450   struct listnode *node;
1451   struct isis_area *area;
1452
1453   if (!isis->area_list || isis->area_list->count == 0)
1454     return CMD_SUCCESS;
1455
1456   for (ALL_LIST_ELEMENTS_RO (isis->area_list, node, area))
1457     {
1458       vty_out (vty, "Area %s:%s", area->area_tag ? area->area_tag : "null",
1459                VTY_NEWLINE);
1460
1461       if (area->ip_circuits > 0 && area->spftree[1]
1462           && area->spftree[1]->paths->count > 0)
1463         {
1464           vty_out (vty, "IS-IS paths to level-2 routers that speak IP%s",
1465                    VTY_NEWLINE);
1466           isis_print_paths (vty, area->spftree[1]->paths);
1467         }
1468 #ifdef HAVE_IPV6
1469       if (area->ipv6_circuits > 0 && area->spftree6[1]
1470           && area->spftree6[1]->paths->count > 0)
1471         {
1472           vty_out (vty, "IS-IS paths to level-2 routers that speak IPv6%s",
1473                    VTY_NEWLINE);
1474           isis_print_paths (vty, area->spftree6[1]->paths);
1475         }
1476 #endif /* HAVE_IPV6 */
1477     }
1478
1479   return CMD_SUCCESS;
1480 }
1481
1482 void
1483 isis_spf_cmds_init ()
1484 {
1485   install_element (VIEW_NODE, &show_isis_topology_cmd);
1486   install_element (VIEW_NODE, &show_isis_topology_l1_cmd);
1487   install_element (VIEW_NODE, &show_isis_topology_l2_cmd);
1488
1489   install_element (ENABLE_NODE, &show_isis_topology_cmd);
1490   install_element (ENABLE_NODE, &show_isis_topology_l1_cmd);
1491   install_element (ENABLE_NODE, &show_isis_topology_l2_cmd);
1492 }