[mirror_frr.git] / isisd / isis_spf.c

/*
 * IS-IS Rout(e)ing protocol                  - isis_spf.c
 *                                              The SPT algorithm
 *
 * Copyright (C) 2001,2002   Sampo Saaristo
 *                           Tampere University of Technology      
 *                           Institute of Communications Engineering
 * Copyright (C) 2017        Christian Franke <chris@opensourcerouting.org>
 *
 * This program is free software; you can redistribute it and/or modify it 
 * under the terms of the GNU General Public Licenseas published by the Free 
 * Software Foundation; either version 2 of the License, or (at your option) 
 * any later version.
 *
 * This program is distributed in the hope that it will be useful,but WITHOUT 
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for 
 * more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; see the file COPYING; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
 */

#include <zebra.h>

#include "thread.h"
#include "linklist.h"
#include "vty.h"
#include "log.h"
#include "command.h"
#include "memory.h"
#include "prefix.h"
#include "hash.h"
#include "if.h"
#include "table.h"
#include "spf_backoff.h"

#include "isis_constants.h"
#include "isis_common.h"
#include "isis_flags.h"
#include "dict.h"
#include "isisd.h"
#include "isis_misc.h"
#include "isis_adjacency.h"
#include "isis_circuit.h"
#include "isis_tlv.h"
#include "isis_pdu.h"
#include "isis_lsp.h"
#include "isis_dynhn.h"
#include "isis_spf.h"
#include "isis_route.h"
#include "isis_csm.h"
#include "isis_mt.h"

DEFINE_MTYPE_STATIC(ISISD, ISIS_SPF_RUN, "ISIS SPF Run Info");

struct isis_spf_run {
    struct isis_area *area;
    int level;
};

/* 7.2.7 */
static void
remove_excess_adjs (struct list *adjs)
{
  struct listnode *node, *excess = NULL;
  struct isis_adjacency *adj, *candidate = NULL;
  int comp;

  for (ALL_LIST_ELEMENTS_RO (adjs, node, adj)) 
    {
      if (excess == NULL)
        excess = node;
      candidate = listgetdata (excess);

      if (candidate->sys_type < adj->sys_type)
        {
          excess = node;
          continue;
        }
      if (candidate->sys_type > adj->sys_type)
        continue;

      comp = memcmp (candidate->sysid, adj->sysid, ISIS_SYS_ID_LEN);
      if (comp > 0)
        {
          excess = node;
          continue;
        }
      if (comp < 0)
        continue;

      if (candidate->circuit->circuit_id > adj->circuit->circuit_id)
        {
          excess = node;
          continue;
        }

      if (candidate->circuit->circuit_id < adj->circuit->circuit_id)
        continue;

      comp = memcmp (candidate->snpa, adj->snpa, ETH_ALEN);
      if (comp > 0)
        {
          excess = node;
          continue;
        }
    }

  list_delete_node (adjs, excess);

  return;
}

static const char *
vtype2string (enum vertextype vtype)
{
  switch (vtype)
    {
    case VTYPE_PSEUDO_IS:
      return "pseudo_IS";
      break;
    case VTYPE_PSEUDO_TE_IS:
      return "pseudo_TE-IS";
      break;
    case VTYPE_NONPSEUDO_IS:
      return "IS";
      break;
    case VTYPE_NONPSEUDO_TE_IS:
      return "TE-IS";
      break;
    case VTYPE_ES:
      return "ES";
      break;
    case VTYPE_IPREACH_INTERNAL:
      return "IP internal";
      break;
    case VTYPE_IPREACH_EXTERNAL:
      return "IP external";
      break;
    case VTYPE_IPREACH_TE:
      return "IP TE";
      break;
    case VTYPE_IP6REACH_INTERNAL:
      return "IP6 internal";
      break;
    case VTYPE_IP6REACH_EXTERNAL:
      return "IP6 external";
      break;
    default:
      return "UNKNOWN";
    }
  return NULL; /* Not reached */
}

static const char *
vid2string (struct isis_vertex *vertex, char * buff, int size)
{
  if (VTYPE_IS(vertex->type) || VTYPE_ES(vertex->type))
    {
      return print_sys_hostname (vertex->N.id);
    }

  if (VTYPE_IP(vertex->type))
    {
      prefix2str ((struct prefix *) &vertex->N.prefix, buff, size);
      return buff;
    }

  return "UNKNOWN";
}

static struct isis_vertex *
isis_vertex_new (void *id, enum vertextype vtype)
{
  struct isis_vertex *vertex;

  vertex = XCALLOC (MTYPE_ISIS_VERTEX, sizeof (struct isis_vertex));

  vertex->type = vtype;

  if (VTYPE_IS(vtype) || VTYPE_ES(vtype))
    {
      memcpy (vertex->N.id, (u_char *) id, ISIS_SYS_ID_LEN + 1);
    }
  else if (VTYPE_IP(vtype))
    {
      memcpy (&vertex->N.prefix, (struct prefix *) id, sizeof (struct prefix));
    }
  else
    {
      zlog_err ("WTF!");
    }

  vertex->Adj_N = list_new ();
  vertex->parents = list_new ();
  vertex->children = list_new ();

  return vertex;
}

static void
isis_vertex_del (struct isis_vertex *vertex)
{
  list_delete (vertex->Adj_N);
  vertex->Adj_N = NULL;
  list_delete (vertex->parents);
  vertex->parents = NULL;
  list_delete (vertex->children);
  vertex->children = NULL;

  memset(vertex, 0, sizeof(struct isis_vertex));
  XFREE (MTYPE_ISIS_VERTEX, vertex);

  return;
}

static void
isis_vertex_adj_del (struct isis_vertex *vertex, struct isis_adjacency *adj)
{
  struct listnode *node, *nextnode;
  if (!vertex)
    return;
  for (node = listhead (vertex->Adj_N); node; node = nextnode)
  {
    nextnode = listnextnode(node);
    if (listgetdata(node) == adj)
      list_delete_node(vertex->Adj_N, node);
  }
  return;
}

struct isis_spftree *
isis_spftree_new (struct isis_area *area)
{
  struct isis_spftree *tree;

  tree = XCALLOC (MTYPE_ISIS_SPFTREE, sizeof (struct isis_spftree));
  if (tree == NULL)
    {
      zlog_err ("ISIS-Spf: isis_spftree_new Out of memory!");
      return NULL;
    }

  tree->tents = list_new ();
  tree->paths = list_new ();
  tree->area = area;
  tree->last_run_timestamp = 0;
  tree->last_run_duration = 0;
  tree->runcount = 0;
  return tree;
}

void
isis_spftree_del (struct isis_spftree *spftree)
{

  spftree->tents->del = (void (*)(void *)) isis_vertex_del;
  list_delete (spftree->tents);
  spftree->tents = NULL;

  spftree->paths->del = (void (*)(void *)) isis_vertex_del;
  list_delete (spftree->paths);
  spftree->paths = NULL;

  XFREE (MTYPE_ISIS_SPFTREE, spftree);

  return;
}

static void
isis_spftree_adj_del (struct isis_spftree *spftree, struct isis_adjacency *adj)
{
  struct listnode *node;
  if (!adj)
    return;
  for (node = listhead (spftree->tents); node; node = listnextnode (node))
    isis_vertex_adj_del (listgetdata (node), adj);
  for (node = listhead (spftree->paths); node; node = listnextnode (node))
    isis_vertex_adj_del (listgetdata (node), adj);
  return;
}

void
spftree_area_init (struct isis_area *area)
{
  if (area->is_type & IS_LEVEL_1)
  {
    if (area->spftree[0] == NULL)
      area->spftree[0] = isis_spftree_new (area);
    if (area->spftree6[0] == NULL)
      area->spftree6[0] = isis_spftree_new (area);
  }

  if (area->is_type & IS_LEVEL_2)
  {
    if (area->spftree[1] == NULL)
      area->spftree[1] = isis_spftree_new (area);
    if (area->spftree6[1] == NULL)
      area->spftree6[1] = isis_spftree_new (area);
  }

  return;
}

void
spftree_area_del (struct isis_area *area)
{
  if (area->is_type & IS_LEVEL_1)
  {
    if (area->spftree[0] != NULL)
    {
      isis_spftree_del (area->spftree[0]);
      area->spftree[0] = NULL;
    }
    if (area->spftree6[0])
    {
      isis_spftree_del (area->spftree6[0]);
      area->spftree6[0] = NULL;
    }
  }

  if (area->is_type & IS_LEVEL_2)
  {
    if (area->spftree[1] != NULL)
    {
      isis_spftree_del (area->spftree[1]);
      area->spftree[1] = NULL;
    }
    if (area->spftree6[1] != NULL)
    {
      isis_spftree_del (area->spftree6[1]);
      area->spftree6[1] = NULL;
    }
  }

  return;
}

void
spftree_area_adj_del (struct isis_area *area, struct isis_adjacency *adj)
{
  if (area->is_type & IS_LEVEL_1)
  {
    if (area->spftree[0] != NULL)
      isis_spftree_adj_del (area->spftree[0], adj);
    if (area->spftree6[0] != NULL)
      isis_spftree_adj_del (area->spftree6[0], adj);
  }

  if (area->is_type & IS_LEVEL_2)
  {
    if (area->spftree[1] != NULL)
      isis_spftree_adj_del (area->spftree[1], adj);
    if (area->spftree6[1] != NULL)
      isis_spftree_adj_del (area->spftree6[1], adj);
  }

  return;
}

/* 
 * Find the system LSP: returns the LSP in our LSP database 
 * associated with the given system ID.
 */
static struct isis_lsp *
isis_root_system_lsp (struct isis_area *area, int level, u_char *sysid)
{
  struct isis_lsp *lsp;
  u_char lspid[ISIS_SYS_ID_LEN + 2];

  memcpy (lspid, sysid, ISIS_SYS_ID_LEN);
  LSP_PSEUDO_ID (lspid) = 0;
  LSP_FRAGMENT (lspid) = 0;
  lsp = lsp_search (lspid, area->lspdb[level - 1]);
  if (lsp && lsp->lsp_header->rem_lifetime != 0)
    return lsp;
  return NULL;
}

/*
 * Add this IS to the root of SPT
 */
static struct isis_vertex *
isis_spf_add_root (struct isis_spftree *spftree, u_char *sysid)
{
  struct isis_vertex *vertex;
  struct isis_lsp *lsp;
#ifdef EXTREME_DEBUG
  char buff[PREFIX2STR_BUFFER];
#endif /* EXTREME_DEBUG */
  u_char id[ISIS_SYS_ID_LEN + 1];

  memcpy(id, sysid, ISIS_SYS_ID_LEN);
  LSP_PSEUDO_ID(id) = 0;

  lsp = isis_root_system_lsp (spftree->area, spftree->level, sysid);
  if (lsp == NULL)
    zlog_warn ("ISIS-Spf: could not find own l%d LSP!", spftree->level);

  vertex = isis_vertex_new (id, spftree->area->oldmetric ? VTYPE_NONPSEUDO_IS
                                                         : VTYPE_NONPSEUDO_TE_IS);
  listnode_add (spftree->paths, vertex);

#ifdef EXTREME_DEBUG
  zlog_debug ("ISIS-Spf: added this IS  %s %s depth %d dist %d to PATHS",
              vtype2string (vertex->type), vid2string (vertex, buff, sizeof (buff)),
              vertex->depth, vertex->d_N);
#endif /* EXTREME_DEBUG */

  return vertex;
}

static struct isis_vertex *
isis_find_vertex (struct list *list, void *id, enum vertextype vtype)
{
  struct listnode *node;
  struct isis_vertex *vertex;
  struct prefix *p1, *p2;

  for (ALL_LIST_ELEMENTS_RO (list, node, vertex))
    {
      if (vertex->type != vtype)
        continue;
      if (VTYPE_IS(vertex->type) || VTYPE_ES(vertex->type))
        {
          if (memcmp ((u_char *) id, vertex->N.id, ISIS_SYS_ID_LEN + 1) == 0)
            return vertex;
        }
      if (VTYPE_IP(vertex->type))
        {
          p1 = (struct prefix *) id;
          p2 = (struct prefix *) &vertex->N.id;
          if (p1->family == p2->family
              && p1->prefixlen == p2->prefixlen
              && !memcmp(&p1->u.prefix, &p2->u.prefix, PSIZE (p1->prefixlen)))
            {
              return vertex;
            }
        }
    }

  return NULL;
}

/*
 * Compares vertizes for sorting in the TENT list. Returns true
 * if candidate should be considered before current, false otherwise.
 */
static bool
tent_cmp (struct isis_vertex *current, struct isis_vertex *candidate)
{
  if (current->d_N > candidate->d_N)
    return true;

  if (current->d_N == candidate->d_N
      && current->type > candidate->type)
    return true;

  return false;
}

/*
 * Add a vertex to TENT sorted by cost and by vertextype on tie break situation
 */
static struct isis_vertex *
isis_spf_add2tent (struct isis_spftree *spftree, enum vertextype vtype,
                   void *id, uint32_t cost, int depth,
                   struct isis_adjacency *adj, struct isis_vertex *parent)
{
  struct isis_vertex *vertex, *v;
  struct listnode *node;
  struct isis_adjacency *parent_adj;
#ifdef EXTREME_DEBUG
  char buff[PREFIX2STR_BUFFER];
#endif

  assert (isis_find_vertex (spftree->paths, id, vtype) == NULL);
  assert (isis_find_vertex (spftree->tents, id, vtype) == NULL);
  vertex = isis_vertex_new (id, vtype);
  vertex->d_N = cost;
  vertex->depth = depth;

  if (parent) {
    listnode_add (vertex->parents, parent);
    if (listnode_lookup (parent->children, vertex) == NULL)
      listnode_add (parent->children, vertex);
  }

  if (parent && parent->Adj_N && listcount(parent->Adj_N) > 0) {
    for (ALL_LIST_ELEMENTS_RO (parent->Adj_N, node, parent_adj))
      listnode_add (vertex->Adj_N, parent_adj);
  } else if (adj) {
    listnode_add (vertex->Adj_N, adj);
  }

#ifdef EXTREME_DEBUG
  zlog_debug ("ISIS-Spf: add to TENT %s %s %s depth %d dist %d adjcount %d",
              print_sys_hostname (vertex->N.id),
              vtype2string (vertex->type), vid2string (vertex, buff, sizeof (buff)),
              vertex->depth, vertex->d_N, listcount(vertex->Adj_N));
#endif /* EXTREME_DEBUG */

  if (list_isempty (spftree->tents))
    {
      listnode_add (spftree->tents, vertex);
      return vertex;
    }

  /* XXX: This cant use the standard ALL_LIST_ELEMENTS macro */
  for (node = listhead (spftree->tents); node; node = listnextnode (node))
    {
      v = listgetdata (node);
      if (tent_cmp(v, vertex))
        {
          listnode_add_before (spftree->tents, node, vertex);
          break;
        }
    }

  if (node == NULL)
      listnode_add (spftree->tents, vertex);

  return vertex;
}

static void
isis_spf_add_local (struct isis_spftree *spftree, enum vertextype vtype,
                    void *id, struct isis_adjacency *adj, uint32_t cost,
                    struct isis_vertex *parent)
{
  struct isis_vertex *vertex;

  vertex = isis_find_vertex (spftree->tents, id, vtype);

  if (vertex)
    {
      /* C.2.5   c) */
      if (vertex->d_N == cost)
        {
          if (adj)
            listnode_add (vertex->Adj_N, adj);
          /*       d) */
          if (listcount (vertex->Adj_N) > ISIS_MAX_PATH_SPLITS)
            remove_excess_adjs (vertex->Adj_N);
          if (parent && (listnode_lookup (vertex->parents, parent) == NULL))
            listnode_add (vertex->parents, parent);
          if (parent && (listnode_lookup (parent->children, vertex) == NULL))
            listnode_add (parent->children, vertex);
          return;
        }
      else if (vertex->d_N < cost)
        {
          /*       e) do nothing */
          return;
        }
      else {  /* vertex->d_N > cost */
          /*         f) */
          struct listnode *pnode, *pnextnode;
          struct isis_vertex *pvertex;
          listnode_delete (spftree->tents, vertex);
          assert (listcount (vertex->children) == 0);
          for (ALL_LIST_ELEMENTS (vertex->parents, pnode, pnextnode, pvertex))
            listnode_delete(pvertex->children, vertex);
          isis_vertex_del (vertex);
      }
    }

  isis_spf_add2tent (spftree, vtype, id, cost, 1, adj, parent);
  return;
}

static void
process_N (struct isis_spftree *spftree, enum vertextype vtype, void *id,
           uint32_t dist, uint16_t depth,
           struct isis_vertex *parent)
{
  struct isis_vertex *vertex;
#ifdef EXTREME_DEBUG
  char buff[PREFIX2STR_BUFFER];
#endif

  assert (spftree && parent);

  /* RFC3787 section 5.1 */
  if (spftree->area->newmetric == 1)
    {
      if (dist > MAX_WIDE_PATH_METRIC)
        return;
    }
  /* C.2.6 b)    */
  else if (spftree->area->oldmetric == 1)
    {
      if (dist > MAX_NARROW_PATH_METRIC)
        return;
    }

  /*       c)    */
  vertex = isis_find_vertex (spftree->paths, id, vtype);
  if (vertex)
    {
#ifdef EXTREME_DEBUG
      zlog_debug ("ISIS-Spf: process_N %s %s %s dist %d already found from PATH",
                  print_sys_hostname (vertex->N.id),
                  vtype2string (vtype), vid2string (vertex, buff, sizeof (buff)), dist);
#endif /* EXTREME_DEBUG */
      assert (dist >= vertex->d_N);
      return;
    }

  vertex = isis_find_vertex (spftree->tents, id, vtype);
  /*       d)    */
  if (vertex)
    {
      /*        1) */
#ifdef EXTREME_DEBUG
      zlog_debug ("ISIS-Spf: process_N %s %s %s dist %d parent %s adjcount %d",
                  print_sys_hostname (vertex->N.id),
                  vtype2string (vtype), vid2string (vertex, buff, sizeof (buff)), dist,
                  (parent ? print_sys_hostname (parent->N.id) : "null"),
                  (parent ? listcount (parent->Adj_N) : 0));
#endif /* EXTREME_DEBUG */
      if (vertex->d_N == dist)
        {
          struct listnode *node;
          struct isis_adjacency *parent_adj;
          for (ALL_LIST_ELEMENTS_RO (parent->Adj_N, node, parent_adj))
            if (listnode_lookup(vertex->Adj_N, parent_adj) == NULL)
              listnode_add (vertex->Adj_N, parent_adj);
          /*      2) */
          if (listcount (vertex->Adj_N) > ISIS_MAX_PATH_SPLITS)
            remove_excess_adjs (vertex->Adj_N);
          if (listnode_lookup (vertex->parents, parent) == NULL)
            listnode_add (vertex->parents, parent);
          if (listnode_lookup (parent->children, vertex) == NULL)
            listnode_add (parent->children, vertex);
          /*      3) */
          return;
        }
      else if (vertex->d_N < dist)
        {
          return;
          /*      4) */
        }
      else
        {
          struct listnode *pnode, *pnextnode;
          struct isis_vertex *pvertex;
          listnode_delete (spftree->tents, vertex);
          assert (listcount (vertex->children) == 0);
          for (ALL_LIST_ELEMENTS (vertex->parents, pnode, pnextnode, pvertex))
            listnode_delete(pvertex->children, vertex);
          isis_vertex_del (vertex);
        }
    }

#ifdef EXTREME_DEBUG
  zlog_debug ("ISIS-Spf: process_N add2tent %s %s dist %d parent %s",
              print_sys_hostname(id), vtype2string (vtype), dist,
              (parent ? print_sys_hostname (parent->N.id) : "null"));
#endif /* EXTREME_DEBUG */

  isis_spf_add2tent (spftree, vtype, id, dist, depth, NULL, parent);
  return;
}

/*
 * C.2.6 Step 1
 */
static int
isis_spf_process_lsp (struct isis_spftree *spftree, struct isis_lsp *lsp,
                      uint32_t cost, uint16_t depth,
                      u_char *root_sysid, struct isis_vertex *parent)
{
  bool pseudo_lsp = LSP_PSEUDO_ID(lsp->lsp_header->lsp_id);
  struct listnode *node, *fragnode = NULL;
  uint32_t dist;
  struct is_neigh *is_neigh;
  struct te_is_neigh *te_is_neigh;
  struct ipv4_reachability *ipreach;
  struct te_ipv4_reachability *te_ipv4_reach;
  enum vertextype vtype;
  struct prefix prefix;
  struct ipv6_reachability *ip6reach;
  static const u_char null_sysid[ISIS_SYS_ID_LEN];
  struct mt_router_info *mt_router_info = NULL;

  if (spftree->mtid != ISIS_MT_IPV4_UNICAST)
    mt_router_info = tlvs_lookup_mt_router_info(&lsp->tlv_data, spftree->mtid);

  if (!pseudo_lsp
      && (spftree->mtid == ISIS_MT_IPV4_UNICAST && !speaks(lsp->tlv_data.nlpids, spftree->family))
      && !mt_router_info)
    return ISIS_OK;

lspfragloop:
  if (lsp->lsp_header->seq_num == 0)
    {
      zlog_warn ("isis_spf_process_lsp(): lsp with 0 seq_num - ignore");
      return ISIS_WARNING;
    }

#ifdef EXTREME_DEBUG
      zlog_debug ("ISIS-Spf: process_lsp %s", print_sys_hostname(lsp->lsp_header->lsp_id));
#endif /* EXTREME_DEBUG */

  /* RFC3787 section 4 SHOULD ignore overload bit in pseudo LSPs */
  if (pseudo_lsp
      || (spftree->mtid == ISIS_MT_IPV4_UNICAST && !ISIS_MASK_LSP_OL_BIT (lsp->lsp_header->lsp_bits))
      || (mt_router_info && !mt_router_info->overload))

  {
    if (pseudo_lsp || spftree->mtid == ISIS_MT_IPV4_UNICAST)
    {
      for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.is_neighs, node, is_neigh))
      {
        /* C.2.6 a) */
        /* Two way connectivity */
        if (!memcmp (is_neigh->neigh_id, root_sysid, ISIS_SYS_ID_LEN))
          continue;
        if (!pseudo_lsp && !memcmp (is_neigh->neigh_id, null_sysid, ISIS_SYS_ID_LEN))
          continue;
        dist = cost + is_neigh->metrics.metric_default;
        process_N (spftree, LSP_PSEUDO_ID(is_neigh->neigh_id) ? VTYPE_PSEUDO_IS
                                                              : VTYPE_NONPSEUDO_IS,
                   (void *) is_neigh->neigh_id, dist, depth + 1, parent);
      }
    }

    struct list *te_is_neighs = NULL;
    if (pseudo_lsp || spftree->mtid == ISIS_MT_IPV4_UNICAST)
      {
        te_is_neighs = lsp->tlv_data.te_is_neighs;
      }
    else
      {
        struct tlv_mt_neighbors *mt_neighbors;
        mt_neighbors = tlvs_lookup_mt_neighbors(&lsp->tlv_data, spftree->mtid);
        if (mt_neighbors)
          te_is_neighs = mt_neighbors->list;
      }
    for (ALL_LIST_ELEMENTS_RO (te_is_neighs, node, te_is_neigh))
      {
        if (!memcmp (te_is_neigh->neigh_id, root_sysid, ISIS_SYS_ID_LEN))
          continue;
        if (!pseudo_lsp && !memcmp (te_is_neigh->neigh_id, null_sysid, ISIS_SYS_ID_LEN))
          continue;
        dist = cost + GET_TE_METRIC(te_is_neigh);
        process_N (spftree, LSP_PSEUDO_ID(te_is_neigh->neigh_id) ? VTYPE_PSEUDO_TE_IS
                                                                 : VTYPE_NONPSEUDO_TE_IS,
                   (void *) te_is_neigh->neigh_id, dist, depth + 1, parent);
      }
  }

  if (!pseudo_lsp
      && spftree->family == AF_INET
      && spftree->mtid == ISIS_MT_IPV4_UNICAST)
  {
    struct list *reachs[] = {lsp->tlv_data.ipv4_int_reachs,
                              lsp->tlv_data.ipv4_ext_reachs};

    prefix.family = AF_INET;
    for (unsigned int i = 0; i < array_size(reachs); i++)
      {
        vtype = (reachs[i] == lsp->tlv_data.ipv4_int_reachs) ? VTYPE_IPREACH_INTERNAL
                                                             : VTYPE_IPREACH_EXTERNAL;
        for (ALL_LIST_ELEMENTS_RO (reachs[i], node, ipreach))
          {
            dist = cost + ipreach->metrics.metric_default;
            prefix.u.prefix4 = ipreach->prefix;
            prefix.prefixlen = ip_masklen (ipreach->mask);
            apply_mask (&prefix);
            process_N (spftree, vtype, (void *) &prefix, dist, depth + 1,
                       parent);
          }
      }
  }

  if (!pseudo_lsp && spftree->family == AF_INET)
  {
    struct list *ipv4reachs = NULL;

    if (spftree->mtid == ISIS_MT_IPV4_UNICAST)
      {
        ipv4reachs = lsp->tlv_data.te_ipv4_reachs;
      }
    else
      {
        struct tlv_mt_ipv4_reachs *mt_reachs;
        mt_reachs = tlvs_lookup_mt_ipv4_reachs(&lsp->tlv_data, spftree->mtid);
        if (mt_reachs)
          ipv4reachs = mt_reachs->list;
      }

    prefix.family = AF_INET;
    for (ALL_LIST_ELEMENTS_RO (ipv4reachs, node, te_ipv4_reach))
    {
      assert ((te_ipv4_reach->control & 0x3F) <= IPV4_MAX_BITLEN);

      dist = cost + ntohl (te_ipv4_reach->te_metric);
      prefix.u.prefix4 = newprefix2inaddr (&te_ipv4_reach->prefix_start,
                                           te_ipv4_reach->control);
      prefix.prefixlen = (te_ipv4_reach->control & 0x3F);
      apply_mask (&prefix);
      process_N (spftree, VTYPE_IPREACH_TE, (void *) &prefix, dist, depth + 1,
                 parent);
    }
  }

  if (!pseudo_lsp
      && spftree->family == AF_INET6)
  {
    struct list *ipv6reachs = NULL;

    if (spftree->mtid == ISIS_MT_IPV4_UNICAST)
      {
        ipv6reachs = lsp->tlv_data.ipv6_reachs;
      }
    else
      {
        struct tlv_mt_ipv6_reachs *mt_reachs;
        mt_reachs = tlvs_lookup_mt_ipv6_reachs(&lsp->tlv_data, spftree->mtid);
        if (mt_reachs)
          ipv6reachs = mt_reachs->list;
      }

    prefix.family = AF_INET6;
    for (ALL_LIST_ELEMENTS_RO (ipv6reachs, node, ip6reach))
    {
      assert (ip6reach->prefix_len <= IPV6_MAX_BITLEN);

      dist = cost + ntohl(ip6reach->metric);
      vtype = (ip6reach->control_info & CTRL_INFO_DISTRIBUTION) ?
              VTYPE_IP6REACH_EXTERNAL : VTYPE_IP6REACH_INTERNAL;
      prefix.prefixlen = ip6reach->prefix_len;
      memcpy (&prefix.u.prefix6.s6_addr, ip6reach->prefix,
              PSIZE (ip6reach->prefix_len));
      apply_mask (&prefix);
      process_N (spftree, vtype, (void *) &prefix, dist, depth + 1,
                 parent);
    }
  }

  if (fragnode == NULL)
    fragnode = listhead (lsp->lspu.frags);
  else
    fragnode = listnextnode (fragnode);

  if (fragnode)
    {
      lsp = listgetdata (fragnode);
      goto lspfragloop;
    }

  return ISIS_OK;
}

static int
isis_spf_preload_tent (struct isis_spftree *spftree,
                       u_char *root_sysid,
                       struct isis_vertex *parent)
{
  struct isis_circuit *circuit;
  struct listnode *cnode, *anode, *ipnode;
  struct isis_adjacency *adj;
  struct isis_lsp *lsp;
  struct list *adj_list;
  struct list *adjdb;
  struct prefix_ipv4 *ipv4;
  struct prefix prefix;
  int retval = ISIS_OK;
  u_char lsp_id[ISIS_SYS_ID_LEN + 2];
  static u_char null_lsp_id[ISIS_SYS_ID_LEN + 2];
  struct prefix_ipv6 *ipv6;
  struct isis_circuit_mt_setting *circuit_mt;

  for (ALL_LIST_ELEMENTS_RO (spftree->area->circuit_list, cnode, circuit))
    {
      circuit_mt = circuit_lookup_mt_setting(circuit, spftree->mtid);
      if (circuit_mt && !circuit_mt->enabled)
        continue;
      if (circuit->state != C_STATE_UP)
        continue;
      if (!(circuit->is_type & spftree->level))
        continue;
      if (spftree->family == AF_INET && !circuit->ip_router)
        continue;
      if (spftree->family == AF_INET6 && !circuit->ipv6_router)
        continue;
      /* 
       * Add IP(v6) addresses of this circuit
       */
      if (spftree->family == AF_INET)
        {
          prefix.family = AF_INET;
          for (ALL_LIST_ELEMENTS_RO (circuit->ip_addrs, ipnode, ipv4))
            {
              prefix.u.prefix4 = ipv4->prefix;
              prefix.prefixlen = ipv4->prefixlen;
              apply_mask (&prefix);
              isis_spf_add_local (spftree, VTYPE_IPREACH_INTERNAL, &prefix,
                                  NULL, 0, parent);
            }
        }
      if (spftree->family == AF_INET6)
        {
          prefix.family = AF_INET6;
          for (ALL_LIST_ELEMENTS_RO (circuit->ipv6_non_link, ipnode, ipv6))
            {
              prefix.prefixlen = ipv6->prefixlen;
              prefix.u.prefix6 = ipv6->prefix;
              apply_mask (&prefix);
              isis_spf_add_local (spftree, VTYPE_IP6REACH_INTERNAL,
                                  &prefix, NULL, 0, parent);
            }
        }
      if (circuit->circ_type == CIRCUIT_T_BROADCAST)
        {
          /*
           * Add the adjacencies
           */
          adj_list = list_new ();
          adjdb = circuit->u.bc.adjdb[spftree->level - 1];
          isis_adj_build_up_list (adjdb, adj_list);
          if (listcount (adj_list) == 0)
            {
              list_delete (adj_list);
              if (isis->debugs & DEBUG_SPF_EVENTS)
                zlog_debug ("ISIS-Spf: no L%d adjacencies on circuit %s",
                            spftree->level, circuit->interface->name);
              continue;
            }
          for (ALL_LIST_ELEMENTS_RO (adj_list, anode, adj))
            {
              if (!adj_has_mt(adj, spftree->mtid))
                continue;
              if (spftree->mtid == ISIS_MT_IPV4_UNICAST && !speaks (&adj->nlpids, spftree->family))
                continue;
              switch (adj->sys_type)
                {
                case ISIS_SYSTYPE_ES:
                  memcpy(lsp_id, adj->sysid, ISIS_SYS_ID_LEN);
                  LSP_PSEUDO_ID (lsp_id) = 0;
                  isis_spf_add_local (spftree, VTYPE_ES, lsp_id, adj,
                                      circuit->te_metric[spftree->level - 1],
                                      parent);
                  break;
                case ISIS_SYSTYPE_IS:
                case ISIS_SYSTYPE_L1_IS:
                case ISIS_SYSTYPE_L2_IS:
                  memcpy (lsp_id, adj->sysid, ISIS_SYS_ID_LEN);
                  LSP_PSEUDO_ID (lsp_id) = 0;
                  LSP_FRAGMENT (lsp_id) = 0;
                  isis_spf_add_local (spftree,
                                      spftree->area->oldmetric ? VTYPE_NONPSEUDO_IS
                                                               : VTYPE_NONPSEUDO_TE_IS,
                                      lsp_id, adj,
                                      circuit->te_metric[spftree->level - 1],
                                      parent);
                  lsp = lsp_search (lsp_id, spftree->area->lspdb[spftree->level - 1]);
                  if (lsp == NULL || lsp->lsp_header->rem_lifetime == 0)
                    zlog_warn ("ISIS-Spf: No LSP %s found for IS adjacency "
                        "L%d on %s (ID %u)",
                        rawlspid_print (lsp_id), spftree->level,
                        circuit->interface->name, circuit->circuit_id);
                  break;
                case ISIS_SYSTYPE_UNKNOWN:
                default:
                  zlog_warn ("isis_spf_preload_tent unknow adj type");
                }
            }
          list_delete (adj_list);
          /*
           * Add the pseudonode 
           */
          if (spftree->level == 1)
            memcpy (lsp_id, circuit->u.bc.l1_desig_is, ISIS_SYS_ID_LEN + 1);
          else
            memcpy (lsp_id, circuit->u.bc.l2_desig_is, ISIS_SYS_ID_LEN + 1);
          /* can happen during DR reboot */
          if (memcmp (lsp_id, null_lsp_id, ISIS_SYS_ID_LEN + 1) == 0)
            {
              if (isis->debugs & DEBUG_SPF_EVENTS)
                zlog_debug ("ISIS-Spf: No L%d DR on %s (ID %d)",
                    spftree->level, circuit->interface->name, circuit->circuit_id);
              continue;
            }
          adj = isis_adj_lookup (lsp_id, adjdb);
          /* if no adj, we are the dis or error */
          if (!adj && !circuit->u.bc.is_dr[spftree->level - 1])
            {
              zlog_warn ("ISIS-Spf: No adjacency found from root "
                  "to L%d DR %s on %s (ID %d)",
                  spftree->level, rawlspid_print (lsp_id),
                  circuit->interface->name, circuit->circuit_id);
              continue;
            }
          lsp = lsp_search (lsp_id, spftree->area->lspdb[spftree->level - 1]);
          if (lsp == NULL || lsp->lsp_header->rem_lifetime == 0)
            {
              zlog_warn ("ISIS-Spf: No lsp (%p) found from root "
                  "to L%d DR %s on %s (ID %d)",
                  (void *)lsp, spftree->level, rawlspid_print (lsp_id),
                  circuit->interface->name, circuit->circuit_id);
              continue;
            }
          isis_spf_process_lsp (spftree, lsp,
                                circuit->te_metric[spftree->level - 1], 0,
                                root_sysid, parent);
        }
      else if (circuit->circ_type == CIRCUIT_T_P2P)
        {
          adj = circuit->u.p2p.neighbor;
          if (!adj)
            continue;
          if (!adj_has_mt(adj, spftree->mtid))
            continue;
          switch (adj->sys_type)
            {
            case ISIS_SYSTYPE_ES:
              memcpy (lsp_id, adj->sysid, ISIS_SYS_ID_LEN);
              LSP_PSEUDO_ID (lsp_id) = 0;
              isis_spf_add_local (spftree, VTYPE_ES, lsp_id, adj,
                                  circuit->te_metric[spftree->level - 1],
                                  parent);
              break;
            case ISIS_SYSTYPE_IS:
            case ISIS_SYSTYPE_L1_IS:
            case ISIS_SYSTYPE_L2_IS:
              memcpy (lsp_id, adj->sysid, ISIS_SYS_ID_LEN);
              LSP_PSEUDO_ID (lsp_id) = 0;
              LSP_FRAGMENT (lsp_id) = 0;
              if (spftree->mtid != ISIS_MT_IPV4_UNICAST || speaks (&adj->nlpids, spftree->family))
                isis_spf_add_local (spftree,
                                    spftree->area->oldmetric ? VTYPE_NONPSEUDO_IS
                                                             : VTYPE_NONPSEUDO_TE_IS,
                                    lsp_id,
                                    adj, circuit->te_metric[spftree->level - 1],
                                    parent);
              break;
            case ISIS_SYSTYPE_UNKNOWN:
            default:
              zlog_warn ("isis_spf_preload_tent unknown adj type");
              break;
            }
        }
      else if (circuit->circ_type == CIRCUIT_T_LOOPBACK)
        {
          continue;
        }
      else
        {
          zlog_warn ("isis_spf_preload_tent unsupported media");
          retval = ISIS_WARNING;
        }
    }

  return retval;
}

/*
 * The parent(s) for vertex is set when added to TENT list
 * now we just put the child pointer(s) in place
 */
static void
add_to_paths (struct isis_spftree *spftree, struct isis_vertex *vertex)
{
  char buff[PREFIX2STR_BUFFER];

  if (isis_find_vertex (spftree->paths, vertex->N.id, vertex->type))
    return;
  listnode_add (spftree->paths, vertex);

#ifdef EXTREME_DEBUG
  zlog_debug ("ISIS-Spf: added %s %s %s depth %d dist %d to PATHS",
              print_sys_hostname (vertex->N.id),
              vtype2string (vertex->type), vid2string (vertex, buff, sizeof (buff)),
              vertex->depth, vertex->d_N);
#endif /* EXTREME_DEBUG */

  if (VTYPE_IP(vertex->type))
    {
      if (listcount (vertex->Adj_N) > 0)
        isis_route_create ((struct prefix *) &vertex->N.prefix, vertex->d_N,
                           vertex->depth, vertex->Adj_N, spftree->area, spftree->level);
      else if (isis->debugs & DEBUG_SPF_EVENTS)
        zlog_debug ("ISIS-Spf: no adjacencies do not install route for "
                    "%s depth %d dist %d", vid2string (vertex, buff, sizeof (buff)),
                    vertex->depth, vertex->d_N);
    }

  return;
}

static void
init_spt (struct isis_spftree *spftree, int mtid, int level, int family)
{
  spftree->tents->del = spftree->paths->del = (void (*)(void *)) isis_vertex_del;
  list_delete_all_node (spftree->tents);
  list_delete_all_node (spftree->paths);
  spftree->tents->del = spftree->paths->del = NULL;

  spftree->mtid = mtid;
  spftree->level = level;
  spftree->family = family;
  return;
}

static int
isis_run_spf (struct isis_area *area, int level, int family, u_char *sysid)
{
  int retval = ISIS_OK;
  struct listnode *node;
  struct isis_vertex *vertex;
  struct isis_vertex *root_vertex;
  struct isis_spftree *spftree = NULL;
  u_char lsp_id[ISIS_SYS_ID_LEN + 2];
  struct isis_lsp *lsp;
  struct route_table *table = NULL;
  struct timeval time_now;
  unsigned long long start_time, end_time;
  uint16_t mtid;

  /* Get time that can't roll backwards. */
  monotime(&time_now);
  start_time = time_now.tv_sec;
  start_time = (start_time * 1000000) + time_now.tv_usec;

  if (family == AF_INET)
    spftree = area->spftree[level - 1];
  else if (family == AF_INET6)
    spftree = area->spftree6[level - 1];
  assert (spftree);
  assert (sysid);

  /* Make all routes in current route table inactive. */
  if (family == AF_INET)
    table = area->route_table[level - 1];
  else if (family == AF_INET6)
    table = area->route_table6[level - 1];

  isis_route_invalidate_table (area, table);

  /* We only support ipv4-unicast and ipv6-unicast as topologies for now */
  if (family == AF_INET6)
    mtid = isis_area_ipv6_topology(area);
  else
    mtid = ISIS_MT_IPV4_UNICAST;

  /*
   * C.2.5 Step 0
   */
  init_spt (spftree, mtid, level, family);
  /*              a) */
  root_vertex = isis_spf_add_root (spftree, sysid);
  /*              b) */
  retval = isis_spf_preload_tent (spftree, sysid, root_vertex);
  if (retval != ISIS_OK)
    {
      zlog_warn ("ISIS-Spf: failed to load TENT SPF-root:%s", print_sys_hostname(sysid));
      goto out;
    }

  /*
   * C.2.7 Step 2
   */
  if (listcount (spftree->tents) == 0)
    {
      zlog_warn ("ISIS-Spf: TENT is empty SPF-root:%s", print_sys_hostname(sysid));
      goto out;
    }

  while (listcount (spftree->tents) > 0)
    {
      node = listhead (spftree->tents);
      vertex = listgetdata (node);

#ifdef EXTREME_DEBUG
  zlog_debug ("ISIS-Spf: get TENT node %s %s depth %d dist %d to PATHS",
              print_sys_hostname (vertex->N.id),
              vtype2string (vertex->type), vertex->depth, vertex->d_N);
#endif /* EXTREME_DEBUG */

      /* Remove from tent list and add to paths list */
      list_delete_node (spftree->tents, node);
      add_to_paths (spftree, vertex);
      if (VTYPE_IS(vertex->type))
        {
          memcpy (lsp_id, vertex->N.id, ISIS_SYS_ID_LEN + 1);
          LSP_FRAGMENT (lsp_id) = 0;
          lsp = lsp_search (lsp_id, area->lspdb[level - 1]);
          if (lsp && lsp->lsp_header->rem_lifetime != 0)
            {
              isis_spf_process_lsp (spftree, lsp, vertex->d_N,
                                    vertex->depth, sysid, vertex);
            }
          else
            {
              zlog_warn ("ISIS-Spf: No LSP found for %s",
                         rawlspid_print (lsp_id));
            }
        }
    }

out:
  isis_route_validate (area);
  spftree->runcount++;
  spftree->last_run_timestamp = time (NULL);
  monotime(&time_now);
  end_time = time_now.tv_sec;
  end_time = (end_time * 1000000) + time_now.tv_usec;
  spftree->last_run_duration = end_time - start_time;

  return retval;
}

static int
isis_run_spf_cb (struct thread *thread)
{
  struct isis_spf_run *run = THREAD_ARG (thread);
  struct isis_area *area = run->area;
  int level = run->level;
  int retval = ISIS_OK;

  XFREE(MTYPE_ISIS_SPF_RUN, run);
  area->spf_timer[level - 1] = NULL;

  if (!(area->is_type & level))
    {
      if (isis->debugs & DEBUG_SPF_EVENTS)
        zlog_warn ("ISIS-SPF (%s) area does not share level",
                   area->area_tag);
      return ISIS_WARNING;
    }

  if (isis->debugs & DEBUG_SPF_EVENTS)
    zlog_debug ("ISIS-Spf (%s) L%d SPF needed, periodic SPF",
                area->area_tag, level);

  if (area->ip_circuits)
    retval = isis_run_spf (area, level, AF_INET, isis->sysid);
  if (area->ipv6_circuits)
    retval = isis_run_spf (area, level, AF_INET6, isis->sysid);

  return retval;
}

static struct isis_spf_run*
isis_run_spf_arg(struct isis_area *area, int level)
{
  struct isis_spf_run *run = XMALLOC(MTYPE_ISIS_SPF_RUN, sizeof(*run));

  run->area = area;
  run->level = level;

  return run;
}

int
isis_spf_schedule (struct isis_area *area, int level)
{
  struct isis_spftree *spftree = area->spftree[level - 1];
  time_t now = time (NULL);
  int diff = now - spftree->last_run_timestamp;

  assert (diff >= 0);
  assert (area->is_type & level);

  if (isis->debugs & DEBUG_SPF_EVENTS)
    zlog_debug ("ISIS-Spf (%s) L%d SPF schedule called, lastrun %d sec ago",
                area->area_tag, level, diff);

  if (area->spf_delay_ietf[level - 1])
    {
      /* Need to call schedule function also if spf delay is running to
       * restart holdoff timer - compare draft-ietf-rtgwg-backoff-algo-04 */
      long delay = spf_backoff_schedule(area->spf_delay_ietf[level -1]);
      if (area->spf_timer[level - 1])
        return ISIS_OK;

      thread_add_timer_msec (master, isis_run_spf_cb,
                             isis_run_spf_arg(area, level),
                             delay, &area->spf_timer[level-1]);
      return ISIS_OK;
    }

  if (area->spf_timer[level -1])
    return ISIS_OK;

  /* wait configured min_spf_interval before doing the SPF */
  if (diff >= area->min_spf_interval[level-1])
    {
      int retval = ISIS_OK;

      if (area->ip_circuits)
        retval = isis_run_spf (area, level, AF_INET, isis->sysid);
      if (area->ipv6_circuits)
        retval = isis_run_spf (area, level, AF_INET6, isis->sysid);

      return retval;
    }

  thread_add_timer (master, isis_run_spf_cb, isis_run_spf_arg(area, level),
                    area->min_spf_interval[level-1] - diff,
                    &area->spf_timer[level-1]);

  if (isis->debugs & DEBUG_SPF_EVENTS)
    zlog_debug ("ISIS-Spf (%s) L%d SPF scheduled %d sec from now",
                area->area_tag, level, area->min_spf_interval[level-1] - diff);

  return ISIS_OK;
}

static void
isis_print_paths (struct vty *vty, struct list *paths, u_char *root_sysid)
{
  struct listnode *node;
  struct listnode *anode;
  struct isis_vertex *vertex;
  struct isis_adjacency *adj;
  char buff[PREFIX2STR_BUFFER];

  vty_out (vty, "Vertex               Type         Metric "
                "Next-Hop             Interface Parent%s", VTY_NEWLINE);

  for (ALL_LIST_ELEMENTS_RO (paths, node, vertex)) {
      if (memcmp (vertex->N.id, root_sysid, ISIS_SYS_ID_LEN) == 0) {
        vty_out (vty, "%-20s %-12s %-6s", print_sys_hostname (root_sysid),
                 "", "");
        vty_out (vty, "%-30s", "");
      } else {
        int rows = 0;
        vty_out (vty, "%-20s %-12s %-6u ", vid2string (vertex, buff, sizeof (buff)),
                 vtype2string (vertex->type), vertex->d_N);
        for (ALL_LIST_ELEMENTS_RO (vertex->Adj_N, anode, adj)) {
          if (adj) {
            if (rows) {
                vty_out (vty, "%s", VTY_NEWLINE);
                vty_out (vty, "%-20s %-12s %-6s ", "", "", "");
            }
            vty_out (vty, "%-20s %-9s ",
                     print_sys_hostname (adj->sysid),
                     adj->circuit->interface->name);
            ++rows;
          }
        }
        if (rows == 0)
          vty_out (vty, "%-30s ", "");
      }

      /* Print list of parents for the ECMP DAG */
      if (listcount (vertex->parents) > 0) {
        struct listnode *pnode;
        struct isis_vertex *pvertex;
        int rows = 0;
        for (ALL_LIST_ELEMENTS_RO (vertex->parents, pnode, pvertex)) {
          if (rows) {
            vty_out (vty, "%s", VTY_NEWLINE);
            vty_out (vty, "%-72s", "");
          }
          vty_out (vty, "%s(%d)",
                   vid2string (pvertex, buff, sizeof (buff)), pvertex->type);
          ++rows;
        }
      } else {
        vty_out (vty, "  NULL ");
      }

      vty_out (vty, "%s", VTY_NEWLINE);
    }
}

DEFUN (show_isis_topology,
       show_isis_topology_cmd,
       "show isis topology [<level-1|level-2>]",
       SHOW_STR
       "IS-IS information\n"
       "IS-IS paths to Intermediate Systems\n"
       "Paths to all level-1 routers in the area\n"
       "Paths to all level-2 routers in the domain\n")
{
  int levels;
  struct listnode *node;
  struct isis_area *area;

  if (argc < 4)
    levels = ISIS_LEVEL1|ISIS_LEVEL2;
  else if (!strcmp(argv[3]->arg, "level-1"))
    levels = ISIS_LEVEL1;
  else
    levels = ISIS_LEVEL2;

  if (!isis->area_list || isis->area_list->count == 0)
    return CMD_SUCCESS;

  for (ALL_LIST_ELEMENTS_RO (isis->area_list, node, area))
    {
      vty_out (vty, "Area %s:%s", area->area_tag ? area->area_tag : "null",
               VTY_NEWLINE);

      for (int level = ISIS_LEVEL1; level <= ISIS_LEVELS; level++)
        {
          if ((level & levels) == 0)
            continue;

          if (area->ip_circuits > 0 && area->spftree[level-1]
              && area->spftree[level-1]->paths->count > 0)
            {
              vty_out (vty, "IS-IS paths to level-%d routers that speak IP%s",
                       level, VTY_NEWLINE);
              isis_print_paths (vty, area->spftree[level-1]->paths, isis->sysid);
              vty_out (vty, "%s", VTY_NEWLINE);
            }
          if (area->ipv6_circuits > 0 && area->spftree6[level-1]
              && area->spftree6[level-1]->paths->count > 0)
            {
              vty_out (vty,
                       "IS-IS paths to level-%d routers that speak IPv6%s",
                       level, VTY_NEWLINE);
              isis_print_paths (vty, area->spftree6[level-1]->paths, isis->sysid);
              vty_out (vty, "%s", VTY_NEWLINE);
            }
        }

      vty_out (vty, "%s", VTY_NEWLINE);
    }

  return CMD_SUCCESS;
}

void
isis_spf_cmds_init ()
{
  install_element (VIEW_NODE, &show_isis_topology_cmd);
}