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