Initial revision

1 files changed, 1293 insertions, 0 deletions

diff --git a/isisd/isis_spf.c b/isisd/isis_spf.c
new file mode 100644
index 00000000..d6949817
--- /dev/null
+++ b/isisd/isis_spf.c
@@ -0,0 +1,1293 @@
+/*
+ * 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
+ *
+ * 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; if not, write to the Free Software Foundation, Inc., 
+ * 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ */
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <zebra.h>
+#include <net/ethernet.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 "isis_constants.h"
+#include "isis_common.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"
+
+extern struct isis *isis;
+extern struct thread_master *master;
+extern struct host host;
+
+int isis_run_spf_l1 (struct thread *thread);
+int isis_run_spf_l2 (struct thread *thread);
+
+/* performace issue ???? */
+void
+union_adjlist( struct list *target, struct list *source )
+{
+  struct isis_adjacency *adj, *adj2;
+  struct listnode *node, *node2;
+  
+  zlog_info ("Union adjlist!");
+  for (node = listhead (source); node; nextnode (node)) {
+    adj = getdata (node);
+    
+    /* lookup adjacency in the source list */
+    for (node2 = listhead (target); node2; nextnode (node2)) {
+      adj2 = getdata(node2);
+      if (adj == adj2) break;
+    }
+    
+    if (!node2) listnode_add (target, adj);
+  }
+}
+
+
+/* 7.2.7 */
+void      
+remove_excess_adjs (struct list *adjs)
+{
+  struct listnode *node, *excess = NULL;
+  struct isis_adjacency *adj, *candidate = NULL;
+  int comp;
+
+  for (node = listhead (adjs); node; nextnode (node)) {
+    if (excess == NULL) 
+      excess = node;
+    candidate = getdata (excess);
+    adj = getdata (node);
+    if (candidate->sys_type < adj->sys_type) {
+      excess = node;
+      candidate = adj;
+      continue;
+    } 
+    if (candidate->sys_type > adj->sys_type)
+      continue;
+    
+    comp = memcmp (candidate->sysid, adj->sysid, ISIS_SYS_ID_LEN);
+    if (comp > 0) {
+      excess = node;
+      candidate = adj;
+      continue;
+    }
+    if (comp < 0)
+      continue;
+    
+    if (candidate->circuit->circuit_id > adj->circuit->circuit_id) {
+      excess = node;
+      candidate = adj;
+      continue;
+    }
+
+    if (candidate->circuit->circuit_id < adj->circuit->circuit_id)
+      continue;
+    
+    comp = memcmp (candidate->snpa, adj->snpa, ETH_ALEN);
+    if (comp > 0) {
+      excess = node;
+      candidate = adj;
+      continue;
+    }
+  }
+  
+  list_delete_node (adjs, excess);
+
+  return;
+}
+
+const char *
+vtype2string (enum vertextype vtype)
+{
+  switch (vtype) {
+  case  VTYPE_PSEUDO_IS:
+    return "pseudo_IS";
+    break;
+  case VTYPE_NONPSEUDO_IS:
+    return "IS";
+    break;
+  case VTYPE_ES:
+    return "ES";
+    break;
+  case VTYPE_IPREACH_INTERNAL:
+    return "IP internal";
+    break;
+  case VTYPE_IPREACH_EXTERNAL:
+    return "IP external";
+    break;
+#ifdef HAVE_IPV6
+  case VTYPE_IP6REACH_INTERNAL:
+    return "IP6 internal";
+    break;
+  case VTYPE_IP6REACH_EXTERNAL:
+    return "IP6 external";
+    break;
+#endif /* HAVE_IPV6 */ 
+  default:
+    return "UNKNOWN";
+  }
+  return NULL; /* Not reached */
+}
+
+char *
+vid2string (struct isis_vertex *vertex, u_char *buff)
+{
+  switch (vertex->type) {
+  case  VTYPE_PSEUDO_IS:
+    return rawlspid_print (vertex->N.id);
+    break;
+  case VTYPE_NONPSEUDO_IS:
+  case VTYPE_ES:
+    return sysid_print (vertex->N.id);
+    break;
+  case VTYPE_IPREACH_INTERNAL:
+  case VTYPE_IPREACH_EXTERNAL:
+#ifdef HAVE_IPV6
+  case VTYPE_IP6REACH_INTERNAL:
+  case VTYPE_IP6REACH_EXTERNAL:
+#endif /* HAVE_IPV6 */ 
+    prefix2str ((struct prefix *)&vertex->N.prefix, buff, BUFSIZ);
+    break;
+  default:
+    return "UNKNOWN";
+  }
+  
+  return buff;
+}
+
+struct isis_spftree *
+isis_spftree_new ()
+{
+  struct isis_spftree *tree;
+
+  tree = XMALLOC (MTYPE_ISIS_SPFTREE, sizeof (struct isis_spftree));
+  if (tree == NULL) {
+    zlog_err ("ISIS-Spf: isis_spftree_new Out of memory!");
+    return NULL;
+  } 
+  memset (tree, 0, sizeof (struct isis_spftree));
+
+  tree->tents = list_new ();
+  tree->paths  = list_new ();
+  return tree;
+}
+
+void
+isis_vertex_del (struct isis_vertex *vertex)
+{
+  
+  list_delete (vertex->Adj_N);
+
+  XFREE (MTYPE_ISIS_VERTEX, vertex);
+  
+  return;
+}
+
+void
+isis_spftree_del (struct isis_spftree *spftree)
+{
+
+  spftree->tents->del = (void *)isis_vertex_del;
+  list_delete (spftree->tents);
+  
+  spftree->paths->del = (void *)isis_vertex_del;
+  list_delete (spftree->paths);
+
+  XFREE (MTYPE_ISIS_SPFTREE, spftree);
+
+  return;
+}
+
+void 
+spftree_area_init (struct isis_area *area)
+{
+
+  if ((area->is_type & IS_LEVEL_1) && area->spftree[0] == NULL) {
+    area->spftree[0] = isis_spftree_new ();
+#ifdef HAVE_IPV6
+    area->spftree6[0] = isis_spftree_new ();
+#endif
+
+    /*    thread_add_timer (master, isis_run_spf_l1, area, 
+          isis_jitter (PERIODIC_SPF_INTERVAL, 10)); */
+  }
+  
+  if ((area->is_type & IS_LEVEL_2) && area->spftree[1] == NULL) {
+    area->spftree[1] = isis_spftree_new ();
+#ifdef HAVE_IPV6
+    area->spftree6[1] = isis_spftree_new ();
+#endif
+    /*    thread_add_timer (master, isis_run_spf_l2, area, 
+          isis_jitter (PERIODIC_SPF_INTERVAL, 10)); */
+  }
+
+  return;
+}
+
+struct isis_vertex *
+isis_vertex_new (void *id, enum vertextype vtype)
+{
+  struct isis_vertex *vertex;
+
+  vertex = XMALLOC (MTYPE_ISIS_VERTEX, sizeof (struct isis_vertex));
+  if (vertex == NULL) {
+    zlog_err ("isis_vertex_new Out of memory!");
+    return NULL;
+  } 
+  
+  memset (vertex, 0, sizeof (struct isis_vertex));
+  vertex->type = vtype;
+  switch (vtype) {
+  case VTYPE_ES:
+  case VTYPE_NONPSEUDO_IS:
+    memcpy (vertex->N.id, (u_char *)id, ISIS_SYS_ID_LEN);
+    break;
+  case VTYPE_PSEUDO_IS:
+    memcpy (vertex->N.id, (u_char *)id, ISIS_SYS_ID_LEN + 1);
+    break;
+  case VTYPE_IPREACH_INTERNAL:
+  case VTYPE_IPREACH_EXTERNAL:
+#ifdef HAVE_IPV6
+  case VTYPE_IP6REACH_INTERNAL:
+  case VTYPE_IP6REACH_EXTERNAL:
+#endif /* HAVE_IPV6 */ 
+    memcpy (&vertex->N.prefix, (struct prefix *)id, 
+            sizeof (struct prefix));
+    break;
+  default:
+    zlog_err ("WTF!");
+  }
+
+  vertex->Adj_N = list_new ();
+  
+  return vertex;
+}
+
+/*
+ * Add this IS to the root of SPT
+ */
+void
+isis_spf_add_self (struct isis_spftree *spftree, struct isis_area *area,
+                   int level)
+{
+  struct isis_vertex *vertex;
+  struct isis_lsp *lsp;
+  u_char lspid[ISIS_SYS_ID_LEN + 2];
+#ifdef EXTREME_DEBUG
+  u_char buff[BUFSIZ];
+#endif /* EXTREME_DEBUG */
+  memcpy (lspid, isis->sysid, ISIS_SYS_ID_LEN);
+  LSP_PSEUDO_ID(lspid) = 0;
+  LSP_FRAGMENT(lspid) = 0;
+  
+  lsp = lsp_search (lspid, area->lspdb[level - 1]);
+  
+  if (lsp == NULL)
+    zlog_warn ("ISIS-Spf: could not find own l%d LSP!", level);
+  
+  vertex = isis_vertex_new (isis->sysid, VTYPE_NONPSEUDO_IS);
+  vertex->lsp = lsp;
+
+  listnode_add (spftree->paths, vertex);
+
+#ifdef EXTREME_DEBUG
+  zlog_info ("ISIS-Spf: added this IS  %s %s depth %d dist %d to PATHS",
+             vtype2string(vertex->type), vid2string(vertex, buff),
+             vertex->depth, vertex->d_N);
+#endif /* EXTREME_DEBUG */
+
+  return;
+}
+
+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 (node = listhead (list); node; nextnode (node)) {
+    vertex = getdata (node);
+    if (vertex->type != vtype)
+      continue;
+    switch (vtype) {
+    case VTYPE_ES:
+    case VTYPE_NONPSEUDO_IS:
+      if (memcmp ((u_char *)id, vertex->N.id, ISIS_SYS_ID_LEN) == 0)
+        return vertex;
+      break;
+    case VTYPE_PSEUDO_IS:
+      if (memcmp ((u_char *)id, vertex->N.id, ISIS_SYS_ID_LEN + 1) == 0)
+        return vertex;
+      break;
+    case VTYPE_IPREACH_INTERNAL:
+    case VTYPE_IPREACH_EXTERNAL:
+#ifdef HAVE_IPV6
+    case VTYPE_IP6REACH_INTERNAL:
+    case VTYPE_IP6REACH_EXTERNAL:
+#endif /* HAVE_IPV6 */
+      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)) == 0)
+        return vertex;
+      break;
+    }
+  }
+
+  return NULL;
+}
+
+
+
+/*
+ * Add a vertex to TENT sorted by cost and by vertextype on tie break situation
+ */
+struct isis_vertex *
+isis_spf_add2tent (struct isis_spftree *spftree, enum vertextype vtype, 
+                   void *id, struct isis_adjacency *adj, u_int16_t cost,
+                   int depth, int family)
+{
+  struct isis_vertex *vertex, *v;
+  struct listnode *node;
+#ifdef EXTREME_DEBUG 
+  u_char buff[BUFSIZ];
+#endif
+
+  vertex = isis_vertex_new (id, vtype);
+  vertex->d_N = cost;
+  vertex->depth = depth;
+  
+  if (adj)
+    listnode_add (vertex->Adj_N, adj);
+#ifdef EXTREME_DEBUG 
+  zlog_info ("ISIS-Spf: add to TENT  %s %s depth %d dist %d",
+             vtype2string(vertex->type), vid2string(vertex, buff),
+             vertex->depth, vertex->d_N);
+#endif /* EXTREME_DEBUG */
+  listnode_add (spftree->tents, vertex); 
+  if (list_isempty (spftree->tents)) {
+    listnode_add (spftree->tents, vertex); 
+    return vertex;
+  }
+  for (node = listhead (spftree->tents); node; nextnode (node)) {
+    v = getdata (node);
+    if (v->d_N > vertex->d_N) {
+      list_add_node_prev (spftree->tents, node, vertex);
+      break;
+    } else if (v->d_N == vertex->d_N) {
+      /*  Tie break, add according to type */
+      while (v  && v->d_N == vertex->d_N && v->type > vertex->type) {
+        if (v->type > vertex->type) {
+          break;
+        }
+        nextnode (node);
+        (node) ? (v = getdata (node)) : (v = NULL);
+      }
+      list_add_node_prev (spftree->tents, node, vertex);
+      break; 
+    } else  if (node->next == NULL) {
+      list_add_node_next (spftree->tents, node, vertex);
+      break;
+    }
+  }
+  return vertex;
+}
+
+struct isis_vertex *
+isis_spf_add_local (struct isis_spftree *spftree, enum vertextype vtype, 
+                    void *id, struct isis_adjacency *adj, u_int16_t cost,
+                    int family)
+{
+  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);
+    }
+    /*         f) */
+    else if (vertex->d_N > cost) {
+      listnode_delete (spftree->tents, vertex);
+      goto add2tent;
+    }
+    /*       e) do nothing */
+    return vertex;
+  }
+
+ add2tent:
+  return isis_spf_add2tent (spftree, vtype, id, adj, cost, 1, family);
+}
+
+void
+process_N (struct isis_spftree *spftree, enum vertextype vtype, void *id, 
+           u_int16_t dist, u_int16_t depth, struct isis_adjacency *adj,  
+           int family) 
+{
+  struct isis_vertex *vertex;
+#ifdef EXTREME_DEBUG
+  u_char buff[255];
+#endif
+
+  /* C.2.6 b)    */
+  if (dist > MAX_PATH_METRIC)
+    return;
+  /*       c)    */
+  vertex = isis_find_vertex (spftree->paths, id, vtype);
+  if (vertex) {
+#ifdef EXTREME_DEBUG
+    zlog_info ("ISIS-Spf: process_N  %s %s dist %d already found from PATH",
+	       vtype2string(vtype), vid2string(vertex, 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_info ("ISIS-Spf: process_N  %s %s dist %d",
+	       vtype2string(vtype), vid2string(vertex, buff), dist);
+#endif /* EXTREME_DEBUG */
+    if (vertex->d_N == dist) {
+      if (adj)
+        listnode_add (vertex->Adj_N, adj);
+      /*      2) */
+      if (listcount(vertex->Adj_N) > ISIS_MAX_PATH_SPLITS)
+        remove_excess_adjs (vertex->Adj_N);
+      /*      3) */
+      return;
+    } else if (vertex->d_N < dist) {
+      return;
+      /*      4) */
+    } else {
+      listnode_delete (spftree->tents, vertex);
+    }
+  }
+  
+  isis_spf_add2tent (spftree, vtype, id, adj, dist, depth, family);
+  return;
+}
+
+/*
+ * C.2.6 Step 1
+ */
+int
+isis_spf_process_lsp (struct isis_spftree *spftree, struct isis_lsp *lsp, 
+                      uint16_t cost, uint16_t depth, int family)
+{
+  struct listnode *node, *fragnode = NULL;
+  u_int16_t dist;
+  struct is_neigh *is_neigh;
+  struct ipv4_reachability *ipreach;
+  enum vertextype vtype;
+  struct prefix prefix;
+#ifdef HAVE_IPV6
+  struct ipv6_reachability *ip6reach;
+#endif /* HAVE_IPV6 */
+  
+
+  if (!lsp->adj)
+    return ISIS_WARNING;
+  if (lsp->tlv_data.nlpids == NULL || 
+      !speaks (lsp->tlv_data.nlpids, family))
+    return ISIS_OK;
+
+ lspfragloop:
+  if (lsp->lsp_header->seq_num == 0) {
+    zlog_warn ("isis_spf_process_lsp(): lsp with 0 seq_num"
+	       " - do not process");
+    return ISIS_WARNING;
+  }
+
+  if (!ISIS_MASK_LSP_OL_BIT(lsp->lsp_header->lsp_bits)) {
+    if (lsp->tlv_data.is_neighs) {
+      for (node = listhead (lsp->tlv_data.is_neighs); node; nextnode (node)) {
+        is_neigh = getdata (node);
+        /* C.2.6 a) */       
+	/* Two way connectivity */
+	if (!memcmp (is_neigh->neigh_id, isis->sysid, ISIS_SYS_ID_LEN))
+	  continue;
+        dist = cost + is_neigh->metrics.metric_default;
+        vtype = LSP_PSEUDO_ID(is_neigh->neigh_id) ? VTYPE_PSEUDO_IS 
+                                                  : VTYPE_NONPSEUDO_IS;
+        process_N (spftree, vtype, (void *)is_neigh->neigh_id, dist, depth+1, 
+                   lsp->adj, family);
+      }
+    }
+    if (family == AF_INET && lsp->tlv_data.ipv4_int_reachs) {
+      prefix.family = AF_INET;
+      for (node = listhead (lsp->tlv_data.ipv4_int_reachs); node; 
+           nextnode (node)) {
+        ipreach = getdata (node);
+        dist = cost + ipreach->metrics.metric_default;
+        vtype = VTYPE_IPREACH_INTERNAL;
+        prefix.u.prefix4 = ipreach->prefix;
+        prefix.prefixlen = ip_masklen (ipreach->mask);
+        process_N (spftree, vtype, (void *)&prefix, dist, depth + 1,
+                   lsp->adj, family);
+      }
+    }
+    
+    if (family == AF_INET && lsp->tlv_data.ipv4_ext_reachs) {
+      prefix.family = AF_INET;
+      for (node = listhead (lsp->tlv_data.ipv4_ext_reachs); node; 
+           nextnode (node)) {
+        ipreach = getdata (node);
+        dist = cost + ipreach->metrics.metric_default;
+        vtype = VTYPE_IPREACH_EXTERNAL;
+        prefix.u.prefix4 = ipreach->prefix;
+        prefix.prefixlen = ip_masklen (ipreach->mask);
+        process_N (spftree, vtype, (void *)&prefix, dist, depth + 1,
+                   lsp->adj, family);
+      }
+    }
+#ifdef HAVE_IPV6
+    if (family == AF_INET6 && lsp->tlv_data.ipv6_reachs) {
+      prefix.family = AF_INET6;
+      for (node = listhead (lsp->tlv_data.ipv6_reachs); node; 
+           nextnode (node)) {
+        ip6reach = getdata (node);
+        dist = cost + 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));
+        process_N (spftree, vtype, (void *)&prefix, dist, depth + 1,
+                   lsp->adj, family);
+      }
+    }
+#endif /* HAVE_IPV6 */
+  }
+  
+  if (fragnode == NULL)
+    fragnode = listhead (lsp->lspu.frags);
+  else 
+    fragnode = nextnode (fragnode);
+
+  if (fragnode) {
+    lsp = getdata (fragnode);
+    goto lspfragloop;
+  }
+  
+  return ISIS_OK;
+}
+
+int
+isis_spf_process_pseudo_lsp (struct isis_spftree *spftree,struct isis_lsp *lsp,
+                             uint16_t cost, uint16_t depth, int family)
+{
+  struct listnode *node, *fragnode = NULL;
+  struct is_neigh *is_neigh;
+  enum vertextype vtype;
+  
+ pseudofragloop:
+  
+  if (lsp->lsp_header->seq_num == 0) {
+    zlog_warn ("isis_spf_process_pseudo_lsp(): lsp with 0 seq_num"
+	       " - do not process");
+    return ISIS_WARNING;
+  }
+    
+  for (node = (lsp->tlv_data.is_neighs ? 
+               listhead (lsp->tlv_data.is_neighs) : NULL); 
+       node; nextnode (node)) {
+    is_neigh = getdata (node);
+    vtype = LSP_PSEUDO_ID(is_neigh->neigh_id) ? VTYPE_PSEUDO_IS 
+                                              : VTYPE_NONPSEUDO_IS;
+    /* Two way connectivity */
+    if (!memcmp (is_neigh->neigh_id, isis->sysid, ISIS_SYS_ID_LEN))
+      continue;
+    if (isis_find_vertex (spftree->tents, (void *)is_neigh->neigh_id, vtype) 
+	== NULL &&
+        isis_find_vertex (spftree->paths, (void *)is_neigh->neigh_id, vtype)
+        == NULL) {
+        /* C.2.5 i) */
+        isis_spf_add2tent (spftree, vtype, is_neigh->neigh_id, lsp->adj, 
+                           cost, depth, family);
+    }
+  }
+  
+  if (fragnode == NULL)
+    fragnode = listhead (lsp->lspu.frags);
+  else 
+    fragnode = nextnode (fragnode);
+
+  if (fragnode) {
+    lsp = getdata (fragnode);
+    goto pseudofragloop;
+  }
+
+  
+  return ISIS_OK;
+}
+      
+int
+isis_spf_preload_tent (struct isis_spftree *spftree, 
+                       struct isis_area *area, int level, int family)
+{
+  struct isis_vertex *vertex;
+  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];
+#ifdef HAVE_IPV6
+  struct prefix_ipv6 *ipv6;
+#endif /* HAVE_IPV6 */
+  
+  for (cnode = listhead (area->circuit_list); cnode; nextnode (cnode)) {
+    circuit = getdata (cnode);
+    if (circuit->state != C_STATE_UP)
+      continue;
+    if (!(circuit->circuit_is_type & level))
+      continue;
+    if (family == AF_INET && !circuit->ip_router)
+      continue;
+#ifdef HAVE_IPV6
+    if (family == AF_INET6 && !circuit->ipv6_router)
+      continue;
+#endif /* HAVE_IPV6 */
+    /* 
+     * Add IP(v6) addresses of this circuit
+     */
+    if (family == AF_INET) {
+      prefix.family = AF_INET;
+      for (ipnode = (circuit->ip_addrs ? listhead (circuit->ip_addrs) : NULL); 
+           ipnode; nextnode (ipnode)) {
+        ipv4 = getdata (ipnode);
+        prefix.u.prefix4 = ipv4->prefix;
+        prefix.prefixlen = ipv4->prefixlen;
+        isis_spf_add_local (spftree, VTYPE_IPREACH_INTERNAL, &prefix, NULL, 0,
+                            family);
+      }
+    }
+#ifdef HAVE_IPV6
+    if (family == AF_INET6) {
+      prefix.family = AF_INET6;
+      for (ipnode = (circuit->ipv6_non_link ? listhead 
+                     (circuit->ipv6_non_link) : NULL); ipnode; 
+           nextnode (ipnode)) {
+        ipv6 = getdata (ipnode);
+        prefix.prefixlen = ipv6->prefixlen;
+        prefix.u.prefix6 = ipv6->prefix;
+        isis_spf_add_local (spftree, VTYPE_IP6REACH_INTERNAL, 
+                            &prefix, NULL, 0, family);
+      }
+    }
+#endif /* HAVE_IPV6 */
+    if (circuit->circ_type == CIRCUIT_T_BROADCAST ) {
+      /*
+       * Add the adjacencies
+       */
+      adj_list = list_new ();
+      adjdb = circuit->u.bc.adjdb[level - 1];
+      isis_adj_build_up_list (adjdb, adj_list);
+      if (listcount (adj_list) == 0) {
+        list_delete (adj_list);
+        zlog_warn ("ISIS-Spf: no L%d adjacencies on circuit %s",
+                   level, circuit->interface->name);
+	continue;
+      }
+      anode = listhead (adj_list);
+      while (anode) {
+        adj = getdata (anode);
+        if (!speaks (&adj->nlpids, family))
+          continue;
+        switch (adj->sys_type) {
+        case ISIS_SYSTYPE_ES:
+          isis_spf_add_local (spftree, VTYPE_ES, adj->sysid, adj, 
+                              circuit->metrics[level - 1].metric_default,
+                              family);
+        break;
+        case ISIS_SYSTYPE_IS:
+        case ISIS_SYSTYPE_L1_IS:
+        case ISIS_SYSTYPE_L2_IS:
+          vertex = 
+            isis_spf_add_local (spftree, VTYPE_NONPSEUDO_IS, 
+                                adj->sysid, adj,
+                                circuit->metrics[level - 1].metric_default,
+                                family);
+          memcpy (lsp_id, adj->sysid, ISIS_SYS_ID_LEN);
+          LSP_PSEUDO_ID(lsp_id) = 0;
+          LSP_FRAGMENT(lsp_id) = 0;
+          lsp = lsp_search (lsp_id, area->lspdb[level - 1]);
+          if (!lsp)
+            zlog_warn ("No lsp found for IS adjacency");
+          /*          else {
+	    isis_spf_process_lsp (spftree, lsp, vertex->d_N, 1, family);
+            } */
+          break;
+        case ISIS_SYSTYPE_UNKNOWN:
+        default:
+          zlog_warn ("isis_spf_preload_tent unknow adj type");
+        }
+        anode = nextnode (anode); 
+      }
+      list_delete (adj_list);
+      /*
+       * Add the pseudonode 
+       */
+      if (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);
+      lsp = lsp_search (lsp_id, area->lspdb[level - 1]);
+      adj = isis_adj_lookup (lsp_id,  adjdb);
+      /* if no adj, we are the dis or error */
+      if (!adj && !circuit->u.bc.is_dr[level - 1]) {
+        zlog_warn ("ISIS-Spf: No adjacency found for DR");
+      }
+      if (lsp ==  NULL || lsp->lsp_header->rem_lifetime == 0) {
+        zlog_warn ("ISIS-Spf: No lsp found for DR");
+      } else {
+        isis_spf_process_pseudo_lsp 
+          (spftree, lsp, circuit->metrics[level - 1].metric_default, 0,
+           family);
+        
+      }
+    } else if (circuit->circ_type == CIRCUIT_T_P2P ) {
+      adj = circuit->u.p2p.neighbor;
+      if (!adj)
+	continue;
+      switch (adj->sys_type) {
+      case ISIS_SYSTYPE_ES:
+        isis_spf_add_local (spftree, VTYPE_ES, adj->sysid, adj, 
+                            circuit->metrics[level - 1].metric_default,
+                            family);
+        break;
+      case ISIS_SYSTYPE_IS:
+      case ISIS_SYSTYPE_L1_IS:
+      case ISIS_SYSTYPE_L2_IS:
+        if (speaks (&adj->nlpids, family))
+          isis_spf_add_local (spftree, VTYPE_NONPSEUDO_IS, adj->sysid, adj,
+                              circuit->metrics[level - 1].metric_default,
+                              family);
+        break;
+      case ISIS_SYSTYPE_UNKNOWN:
+      default:
+        zlog_warn ("isis_spf_preload_tent unknow adj type");
+        break;
+      }
+    } 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
+ */
+void
+add_to_paths (struct isis_spftree *spftree, struct isis_vertex *vertex,
+              struct isis_area *area)
+{
+
+#ifdef EXTREME_DEBUG
+  u_char buff[BUFSIZ];
+#endif /* EXTREME_DEBUG */
+  listnode_add (spftree->paths, vertex);
+
+#ifdef EXTREME_DEBUG  
+  zlog_info ("ISIS-Spf: added  %s %s depth %d dist %d to PATHS",
+             vtype2string(vertex->type), vid2string(vertex, buff),
+             vertex->depth, vertex->d_N);
+#endif /* EXTREME_DEBUG */  
+  if (vertex->type > VTYPE_ES) {
+    if (listcount(vertex->Adj_N) > 0)
+      isis_route_create ((struct prefix *)&vertex->N.prefix,
+                         vertex->d_N, vertex->depth, vertex->Adj_N, area);
+    else if (isis->debugs & DEBUG_SPF_EVENTS)
+      zlog_info ("ISIS-Spf: no adjacencies do not install route");
+  }
+  
+  return;
+}
+
+
+void
+init_spt (struct isis_spftree *spftree)
+{
+  spftree->tents->del = spftree->paths->del = (void *)isis_vertex_del;
+  list_delete_all_node (spftree->tents);
+  list_delete_all_node (spftree->paths);
+  spftree->tents->del = spftree->paths->del = NULL;
+  
+  return;
+}
+
+int
+isis_run_spf (struct isis_area *area, int level, int family)
+{
+  int retval = ISIS_OK;
+  struct listnode *node;
+  struct isis_vertex *vertex;
+  struct isis_spftree *spftree = NULL; 
+  u_char lsp_id[ISIS_SYS_ID_LEN + 2];
+  struct isis_lsp *lsp;
+  
+  if (family == AF_INET)
+    spftree = area->spftree[level - 1];
+#ifdef HAVE_IPV6
+  else if (family == AF_INET6)
+    spftree = area->spftree6[level - 1];
+#endif
+  
+  assert (spftree);
+
+  /*
+   * C.2.5 Step 0
+   */
+  init_spt (spftree);
+  /*              a) */
+  isis_spf_add_self (spftree, area, level);
+  /*              b) */
+  retval = isis_spf_preload_tent (spftree, area, level, family);
+  
+  /*
+   * C.2.7 Step 2
+   */
+  if (listcount (spftree->tents) == 0) {
+    zlog_warn ("ISIS-Spf: TENT is empty");
+    spftree->lastrun = time (NULL);
+    return retval;
+  }
+
+  while (listcount (spftree->tents) > 0) {
+    node = listhead (spftree->tents);
+    vertex = getdata (node);
+    /* Remove from tent list */
+    list_delete_node (spftree->tents, node);
+    if (isis_find_vertex (spftree->paths, vertex->N.id, vertex->type))
+      continue;
+    add_to_paths (spftree, vertex, area);
+    if (vertex->type == VTYPE_PSEUDO_IS || 
+        vertex->type == VTYPE_NONPSEUDO_IS) {
+      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) {
+	if (LSP_PSEUDO_ID (lsp_id)) {
+          isis_spf_process_pseudo_lsp (spftree, lsp, vertex->d_N, 
+                                       vertex->depth, family);
+        
+        } else {
+	  isis_spf_process_lsp (spftree, lsp, vertex->d_N, vertex->depth, 
+                                family);
+	}
+      } else {
+        zlog_warn ("ISIS-Spf: No LSP found for %s", rawlspid_print (lsp_id));
+      }
+    }
+  }
+  
+  thread_add_event (master, isis_route_validate, area, 0);
+  spftree->lastrun = time (NULL);
+  spftree->pending = 0;
+  
+  if (level == 1)
+    spftree->t_spf_periodic =  thread_add_timer (master, 
+						 isis_run_spf_l1, area, 
+						 isis_jitter 
+						 (PERIODIC_SPF_INTERVAL, 10));
+  else 
+    spftree->t_spf_periodic =  thread_add_timer (master, 
+						 isis_run_spf_l2, area, 
+						 isis_jitter 
+						 (PERIODIC_SPF_INTERVAL, 10));
+
+  return retval;
+}
+
+int
+isis_run_spf_l1 (struct thread *thread)
+{
+  struct isis_area *area;
+  int retval = ISIS_OK;
+
+  area = THREAD_ARG(thread);
+  assert (area);
+
+  if (!(area->is_type & IS_LEVEL_1)) {
+    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_info ("ISIS-Spf (%s) L1 SPF needed, periodic SPF",
+               area->area_tag);
+  }
+  
+  if (area->ip_circuits)
+    retval = isis_run_spf (area, 1, AF_INET);
+#ifdef HAVE_IPV6
+  if (area->ipv6_circuits)
+    retval = isis_run_spf (area, 1, AF_INET6);
+#endif
+  return retval;
+}
+
+int
+isis_run_spf_l2 (struct thread *thread)
+{
+  struct isis_area *area;
+  int retval = ISIS_OK;
+
+  area = THREAD_ARG(thread);
+  assert (area);
+  
+  if (!(area->is_type & IS_LEVEL_2)) {
+    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_info ("ISIS-Spf (%s) L2 SPF needed, periodic SPF",
+               area->area_tag);
+  }
+
+  if (area->ip_circuits)
+    retval = isis_run_spf (area, 2, AF_INET);
+#ifdef HAVE_IPV6
+  if (area->ipv6_circuits)
+    retval = isis_run_spf (area, 2, AF_INET6);
+#endif
+
+  return retval;
+}
+
+int 
+isis_spf_schedule (struct isis_area *area, int level)
+{
+  int retval = ISIS_OK;
+  struct isis_spftree *spftree = area->spftree[level - 1];
+  time_t diff, now = time (NULL);
+
+  if (spftree->pending)
+    return retval;
+
+  diff = now - spftree->lastrun; 
+
+  /* FIXME: let's wait a minute before doing the SPF */
+  if (now - isis->uptime < 60 || isis->uptime == 0) {
+    if (level == 1)
+      thread_add_timer (master, isis_run_spf_l1, area, 
+                        60);
+    else
+      thread_add_timer (master, isis_run_spf_l2, area, 
+                        60);
+
+    spftree->pending = 1;
+    return retval;
+  }
+  if (spftree->t_spf_periodic)
+    thread_cancel (spftree->t_spf_periodic);
+
+  if (diff < MINIMUM_SPF_INTERVAL) {
+    if (level == 1)
+      thread_add_timer (master, isis_run_spf_l1, area, 
+                        MINIMUM_SPF_INTERVAL - diff);
+    else
+      thread_add_timer (master, isis_run_spf_l2, area, 
+                        MINIMUM_SPF_INTERVAL - diff);
+
+    spftree->pending = 1;
+  } else {
+    spftree->pending = 0;
+    retval = isis_run_spf (area, level, AF_INET);
+  }
+
+  return retval;
+}
+
+#ifdef HAVE_IPV6
+int 
+isis_spf_schedule6 (struct isis_area *area, int level)
+{
+  int retval = ISIS_OK;
+  struct isis_spftree *spftree = area->spftree6[level - 1];
+  time_t diff, now = time (NULL);
+
+  if (spftree->pending)
+    return retval;
+
+  diff = now - spftree->lastrun; 
+  
+  if (spftree->t_spf_periodic)
+    thread_cancel (spftree->t_spf_periodic);
+  
+  /* FIXME: let's wait a minute before doing the SPF */
+  if (now - isis->uptime < 60 || isis->uptime == 0) {
+    if (level == 1)
+      thread_add_timer (master, isis_run_spf_l1, area, 
+                        60);
+    else
+      thread_add_timer (master, isis_run_spf_l2, area, 
+                        60);
+
+    spftree->pending = 1;
+    return retval;
+  }
+
+
+  if (diff < MINIMUM_SPF_INTERVAL) {
+    if (level == 1)
+      thread_add_timer (master, isis_run_spf_l1, area, 
+                        MINIMUM_SPF_INTERVAL - diff);
+    else
+      thread_add_timer (master, isis_run_spf_l2, area, 
+                        MINIMUM_SPF_INTERVAL - diff);
+
+    spftree->pending = 1;
+  } else {
+    spftree->pending = 0;
+    retval = isis_run_spf (area, level, AF_INET6);
+  }
+
+  return retval;
+}
+
+#endif
+
+void
+isis_print_paths (struct vty *vty, struct list *paths)
+{
+  struct listnode *node, *anode;
+  struct isis_vertex *vertex;
+  struct isis_dynhn *dyn, *nh_dyn = NULL;
+  struct isis_adjacency *adj;
+#ifdef EXTREME_DEBUG
+  u_char buff[255];
+#endif 
+
+  vty_out (vty, "System Id            Metric     Next-Hop"
+           "             Interface   SNPA%s", VTY_NEWLINE);
+  for (node = listhead (paths); node; nextnode (node)) {
+    vertex = getdata (node);
+    if (vertex->type != VTYPE_NONPSEUDO_IS)
+      continue;
+    if (memcmp (vertex->N.id, isis->sysid, ISIS_SYS_ID_LEN) == 0) {
+      vty_out (vty, "%s             --%s", host.name, VTY_NEWLINE);
+    } else {
+      dyn = dynhn_find_by_id ((u_char *)vertex->N.id);
+      anode = listhead (vertex->Adj_N);
+      adj = getdata (anode);
+      if (adj) {
+        nh_dyn = dynhn_find_by_id (adj->sysid);
+        vty_out (vty, "%-20s %-10u %-20s %-11s %-5s%s", 
+                 (dyn != NULL) ? dyn->name.name : 
+                 (u_char *)rawlspid_print ((u_char *)vertex->N.id),
+                 vertex->d_N, (nh_dyn != NULL) ? nh_dyn->name.name : 
+                 (u_char *)rawlspid_print (adj->sysid), 
+                 adj->circuit->interface->name,
+                 snpa_print (adj->snpa), VTY_NEWLINE);
+      } else {
+        vty_out (vty, "%s              %u %s", dyn ? dyn->name.name : 
+                 (u_char *)rawlspid_print (vertex->N.id), 
+                 vertex->d_N, VTY_NEWLINE);
+      }
+        
+    }
+#if 0
+    vty_out (vty, "%s %s %u %s", vtype2string(vertex->type), 
+             vid2string(vertex, buff), vertex->d_N, VTY_NEWLINE);
+#endif
+  }
+
+  
+}
+
+DEFUN (show_isis_topology,
+       show_isis_topology_cmd,
+       "show isis topology",
+       SHOW_STR
+       "IS-IS information\n"
+       "IS-IS paths to Intermediate Systems\n")
+{
+  struct listnode *node;
+  struct isis_area *area;
+  int level;
+  
+  if (!isis->area_list || isis->area_list->count == 0)
+    return CMD_SUCCESS;
+
+  for (node = listhead (isis->area_list); node; nextnode (node)) {
+    area = getdata (node);
+
+    vty_out (vty, "Area %s:%s", area->area_tag ? area->area_tag : "null",
+             VTY_NEWLINE);
+    
+    for (level=0; level < ISIS_LEVELS; level++) {
+      if (area->ip_circuits > 0 && area->spftree[level] 
+          && area->spftree[level]->paths->count > 0) {
+        vty_out (vty, "IS-IS paths to level-%d routers that speak IP%s", 
+                 level+1, VTY_NEWLINE);
+        isis_print_paths (vty, area->spftree[level]->paths);
+      }
+#ifdef HAVE_IPV6
+      if (area->ipv6_circuits > 0 && area->spftree6[level] 
+          && area->spftree6[level]->paths->count > 0) {
+        vty_out (vty, "IS-IS paths to level-%d routers that speak IPv6%s", 
+                 level+1, VTY_NEWLINE);
+        isis_print_paths (vty, area->spftree6[level]->paths);
+      }
+#endif /* HAVE_IPV6 */
+    }
+  }
+
+  return CMD_SUCCESS;
+} 
+
+
+DEFUN (show_isis_topology_l1,
+       show_isis_topology_l1_cmd,
+       "show isis topology level-1",
+       SHOW_STR
+       "IS-IS information\n"
+       "IS-IS paths to Intermediate Systems\n"
+       "Paths to all level-1 routers in the area\n")
+{
+  struct listnode *node;
+  struct isis_area *area;
+  
+  if (!isis->area_list || isis->area_list->count == 0)
+    return CMD_SUCCESS;
+
+  for (node = listhead (isis->area_list); node; nextnode (node)) {
+    area = getdata (node);
+
+    vty_out (vty, "Area %s:%s", area->area_tag ? area->area_tag : "null",
+             VTY_NEWLINE);
+    
+    if (area->ip_circuits > 0 && area->spftree[0] 
+        && area->spftree[0]->paths->count > 0) {
+      vty_out (vty, "IS-IS paths to level-1 routers that speak IP%s", 
+               VTY_NEWLINE);
+      isis_print_paths (vty, area->spftree[0]->paths);
+    }
+#ifdef HAVE_IPV6
+      if (area->ipv6_circuits > 0 && area->spftree6[0] 
+          && area->spftree6[0]->paths->count > 0) {
+        vty_out (vty, "IS-IS paths to level-1 routers that speak IPv6%s", 
+                 VTY_NEWLINE);
+        isis_print_paths (vty, area->spftree6[0]->paths);
+      }
+#endif /* HAVE_IPV6 */
+    }
+
+
+  return CMD_SUCCESS;
+} 
+
+DEFUN (show_isis_topology_l2,
+       show_isis_topology_l2_cmd,
+       "show isis topology level-2",
+       SHOW_STR
+       "IS-IS information\n"
+       "IS-IS paths to Intermediate Systems\n"
+       "Paths to all level-2 routers in the domain\n")
+{
+  struct listnode *node;
+  struct isis_area *area;
+  
+  if (!isis->area_list || isis->area_list->count == 0)
+    return CMD_SUCCESS;
+
+  for (node = listhead (isis->area_list); node; nextnode (node)) {
+    area = getdata (node);
+
+    vty_out (vty, "Area %s:%s", area->area_tag ? area->area_tag : "null",
+             VTY_NEWLINE);
+    
+    if (area->ip_circuits > 0 && area->spftree[1] 
+        && area->spftree[1]->paths->count > 0) {
+      vty_out (vty, "IS-IS paths to level-2 routers that speak IP%s", 
+               VTY_NEWLINE);
+      isis_print_paths (vty, area->spftree[1]->paths);
+    }
+#ifdef HAVE_IPV6
+      if (area->ipv6_circuits > 0 && area->spftree6[1] 
+          && area->spftree6[1]->paths->count > 0) {
+        vty_out (vty, "IS-IS paths to level-2 routers that speak IPv6%s", 
+                 VTY_NEWLINE);
+        isis_print_paths (vty, area->spftree6[1]->paths);
+      }
+#endif /* HAVE_IPV6 */
+    }
+
+
+  return CMD_SUCCESS;
+} 
+
+
+void
+isis_spf_cmds_init ()
+{
+  install_element (VIEW_NODE, &show_isis_topology_cmd);
+  install_element (VIEW_NODE, &show_isis_topology_l1_cmd);
+  install_element (VIEW_NODE, &show_isis_topology_l2_cmd);
+
+  install_element (ENABLE_NODE, &show_isis_topology_cmd);
+  install_element (ENABLE_NODE, &show_isis_topology_l1_cmd);
+  install_element (ENABLE_NODE, &show_isis_topology_l2_cmd);
+}