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