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