isisd: add Google's changes to IS-IS

1 files changed, 630 insertions, 443 deletions

diff --git a/isisd/isis_spf.c b/isisd/isis_spf.c
index 5d7e9da42..a91742b62 100644
--- a/isisd/isis_spf.c
+++ b/isisd/isis_spf.c
@@ -36,6 +36,7 @@
 
 #include "isis_constants.h"
 #include "isis_common.h"
+#include "isis_flags.h"
 #include "dict.h"
 #include "isisd.h"
 #include "isis_misc.h"
@@ -49,10 +50,6 @@
 #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);
 
@@ -113,7 +110,6 @@ remove_excess_adjs (struct list *adjs)
   return;
 }
 
-#ifdef EXTREME_DEBUG
 static const char *
 vtype2string (enum vertextype vtype)
 {
@@ -164,12 +160,12 @@ vid2string (struct isis_vertex *vertex, u_char * buff)
     {
     case VTYPE_PSEUDO_IS:
     case VTYPE_PSEUDO_TE_IS:
-      return rawlspid_print (vertex->N.id);
+      return print_sys_hostname (vertex->N.id);
       break;
     case VTYPE_NONPSEUDO_IS:
     case VTYPE_NONPSEUDO_TE_IS:
     case VTYPE_ES:
-      return sysid_print (vertex->N.id);
+      return print_sys_hostname (vertex->N.id);
       break;
     case VTYPE_IPREACH_INTERNAL:
     case VTYPE_IPREACH_EXTERNAL:
@@ -186,149 +182,260 @@ vid2string (struct isis_vertex *vertex, u_char * buff)
 
   return (char *) buff;
 }
-#endif /* EXTREME_DEBUG */
 
-static struct isis_spftree *
-isis_spftree_new ()
+static struct isis_vertex *
+isis_vertex_new (void *id, enum vertextype vtype)
 {
-  struct isis_spftree *tree;
+  struct isis_vertex *vertex;
 
-  tree = XCALLOC (MTYPE_ISIS_SPFTREE, sizeof (struct isis_spftree));
-  if (tree == NULL)
+  vertex = XCALLOC (MTYPE_ISIS_VERTEX, sizeof (struct isis_vertex));
+  if (vertex == NULL)
     {
-      zlog_err ("ISIS-Spf: isis_spftree_new Out of memory!");
+      zlog_err ("isis_vertex_new Out of memory!");
       return NULL;
     }
 
-  tree->tents = list_new ();
-  tree->paths = list_new ();
-  return tree;
+  vertex->type = vtype;
+  switch (vtype)
+    {
+    case VTYPE_ES:
+    case VTYPE_NONPSEUDO_IS:
+    case VTYPE_NONPSEUDO_TE_IS:
+      memcpy (vertex->N.id, (u_char *) id, ISIS_SYS_ID_LEN);
+      break;
+    case VTYPE_PSEUDO_IS:
+    case VTYPE_PSEUDO_TE_IS:
+      memcpy (vertex->N.id, (u_char *) id, ISIS_SYS_ID_LEN + 1);
+      break;
+    case VTYPE_IPREACH_INTERNAL:
+    case VTYPE_IPREACH_EXTERNAL:
+    case VTYPE_IPREACH_TE:
+#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 ();
+  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;
 }
 
-#if 0 /* HT: Not used yet. */
 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->lastrun = 0;
+  tree->runcount = 0;
+  tree->pending = 0;
+  return tree;
+}
+
+void
 isis_spftree_del (struct isis_spftree *spftree)
 {
+  THREAD_TIMER_OFF (spftree->t_spf);
+
   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;
 }
-#endif 
+
+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) && area->spftree[0] == NULL)
-    {
-      area->spftree[0] = isis_spftree_new ();
+  if (area->is_type & IS_LEVEL_1)
+  {
+    if (area->spftree[0] == NULL)
+      area->spftree[0] = isis_spftree_new (area);
 #ifdef HAVE_IPV6
-      area->spftree6[0] = isis_spftree_new ();
+    if (area->spftree6[0] == NULL)
+      area->spftree6[0] = isis_spftree_new (area);
 #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 ();
+  if (area->is_type & IS_LEVEL_2)
+  {
+    if (area->spftree[1] == NULL)
+      area->spftree[1] = isis_spftree_new (area);
 #ifdef HAVE_IPV6
-      area->spftree6[1] = isis_spftree_new ();
+    if (area->spftree6[1] == NULL)
+      area->spftree6[1] = isis_spftree_new (area);
 #endif
-      /*    thread_add_timer (master, isis_run_spf_l2, area, 
-         isis_jitter (PERIODIC_SPF_INTERVAL, 10)); */
-    }
+  }
 
   return;
 }
 
-static struct isis_vertex *
-isis_vertex_new (void *id, enum vertextype vtype)
+void
+spftree_area_del (struct isis_area *area)
 {
-  struct isis_vertex *vertex;
-
-  vertex = XCALLOC (MTYPE_ISIS_VERTEX, sizeof (struct isis_vertex));
-  if (vertex == NULL)
+  if (area->is_type & IS_LEVEL_1)
+  {
+    if (area->spftree[0] != NULL)
     {
-      zlog_err ("isis_vertex_new Out of memory!");
-      return NULL;
+      isis_spftree_del (area->spftree[0]);
+      area->spftree[0] = NULL;
+    }
+#ifdef HAVE_IPV6
+    if (area->spftree6[0])
+    {
+      isis_spftree_del (area->spftree6[0]);
+      area->spftree6[0] = NULL;
     }
+#endif
+  }
 
-  vertex->type = vtype;
-  switch (vtype)
+  if (area->is_type & IS_LEVEL_2)
+  {
+    if (area->spftree[1] != NULL)
     {
-    case VTYPE_ES:
-    case VTYPE_NONPSEUDO_IS:
-    case VTYPE_NONPSEUDO_TE_IS:
-      memcpy (vertex->N.id, (u_char *) id, ISIS_SYS_ID_LEN);
-      break;
-    case VTYPE_PSEUDO_IS:
-    case VTYPE_PSEUDO_TE_IS:
-      memcpy (vertex->N.id, (u_char *) id, ISIS_SYS_ID_LEN + 1);
-      break;
-    case VTYPE_IPREACH_INTERNAL:
-    case VTYPE_IPREACH_EXTERNAL:
-    case VTYPE_IPREACH_TE:
+      isis_spftree_del (area->spftree[1]);
+      area->spftree[1] = NULL;
+    }
 #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!");
+    if (area->spftree[1] != NULL)
+    {
+      isis_spftree_del (area->spftree6[1]);
+      area->spftree6[1] = NULL;
     }
+#endif
+  }
 
-  vertex->Adj_N = list_new ();
+  return;
+}
 
-  return vertex;
+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);
+#ifdef HAVE_IPV6
+    if (area->spftree6[0] != NULL)
+      isis_spftree_adj_del (area->spftree6[0], adj);
+#endif
+  }
+
+  if (area->is_type & IS_LEVEL_2)
+  {
+    if (area->spftree[1] != NULL)
+      isis_spftree_adj_del (area->spftree[1], adj);
+#ifdef HAVE_IPV6
+    if (area->spftree6[1] != NULL)
+      isis_spftree_adj_del (area->spftree6[1], adj);
+#endif
+  }
+
+  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)
+{
+  u_char lspid[ISIS_SYS_ID_LEN + 2];
+
+  memcpy (lspid, sysid, ISIS_SYS_ID_LEN);
+  LSP_PSEUDO_ID (lspid) = 0;
+  LSP_FRAGMENT (lspid) = 0;
+  return (lsp_search (lspid, area->lspdb[level - 1]));
 }
 
 /*
  * Add this IS to the root of SPT
  */
-static void
-isis_spf_add_self (struct isis_spftree *spftree, struct isis_area *area,
-		   int level)
+static struct isis_vertex *
+isis_spf_add_root (struct isis_spftree *spftree, int level, u_char *sysid)
 {
   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]);
 
+  lsp = isis_root_system_lsp (spftree->area, level, sysid);
   if (lsp == NULL)
     zlog_warn ("ISIS-Spf: could not find own l%d LSP!", level);
 
-  if (!area->oldmetric)
-    vertex = isis_vertex_new (isis->sysid, VTYPE_NONPSEUDO_TE_IS);
+  if (!spftree->area->oldmetric)
+    vertex = isis_vertex_new (sysid, VTYPE_NONPSEUDO_TE_IS);
   else
-    vertex = isis_vertex_new (isis->sysid, VTYPE_NONPSEUDO_IS);
-
-  vertex->lsp = lsp;
+    vertex = isis_vertex_new (sysid, VTYPE_NONPSEUDO_IS);
 
   listnode_add (spftree->paths, vertex);
 
@@ -338,7 +445,7 @@ isis_spf_add_self (struct isis_spftree *spftree, struct isis_area *area,
 	      vertex->depth, vertex->d_N);
 #endif /* EXTREME_DEBUG */
 
-  return;
+  return vertex;
 }
 
 static struct isis_vertex *
@@ -390,34 +497,49 @@ isis_find_vertex (struct list *list, void *id, enum vertextype vtype)
  */
 static struct isis_vertex *
 isis_spf_add2tent (struct isis_spftree *spftree, enum vertextype vtype,
-		   void *id, struct isis_adjacency *adj, u_int32_t cost,
-		   int depth, int family)
+		   void *id, uint32_t cost, int depth, int family,
+		   struct isis_adjacency *adj, struct isis_vertex *parent)
 {
   struct isis_vertex *vertex, *v;
   struct listnode *node;
+  struct isis_adjacency *parent_adj;
 #ifdef EXTREME_DEBUG
   u_char buff[BUFSIZ];
 #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 (adj)
+  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 depth %d dist %d",
+  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),
-	      vertex->depth, vertex->d_N);
+	      vertex->depth, vertex->d_N, listcount(vertex->Adj_N));
 #endif /* EXTREME_DEBUG */
-  listnode_add (spftree->tents, vertex);
+
   if (list_isempty (spftree->tents))
     {
       listnode_add (spftree->tents, vertex);
       return vertex;
     }
-  
-  /* XXX: This cant use the standard ALL_LIST_ELEMENT macro */
+
+  /* XXX: This cant use the standard ALL_LIST_ELEMENTS macro */
   for (node = listhead (spftree->tents); node; node = listnextnode (node))
     {
       v = listgetdata (node);
@@ -426,35 +548,24 @@ isis_spf_add2tent (struct isis_spftree *spftree, enum vertextype vtype,
 	  list_add_node_prev (spftree->tents, node, vertex);
 	  break;
 	}
-      else if (v->d_N == vertex->d_N)
+      else if (v->d_N == vertex->d_N && v->type > vertex->type)
 	{
 	  /*  Tie break, add according to type */
-	  while (v && v->d_N == vertex->d_N && v->type > vertex->type)
-	    {
-	      if (v->type > vertex->type)
-		{
-		  break;
-		}
-              /* XXX: this seems dubious, node is the loop iterator */
-	      node = listnextnode (node);
-	      (node) ? (v = listgetdata (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);
+          list_add_node_prev (spftree->tents, node, vertex);
 	  break;
 	}
     }
+
+  if (node == NULL)
+      listnode_add (spftree->tents, vertex);
+
   return vertex;
 }
 
-static struct isis_vertex *
+static void
 isis_spf_add_local (struct isis_spftree *spftree, enum vertextype vtype,
-		    void *id, struct isis_adjacency *adj, u_int32_t cost,
-		    int family)
+		    void *id, struct isis_adjacency *adj, uint32_t cost,
+		    int family, struct isis_vertex *parent)
 {
   struct isis_vertex *vertex;
 
@@ -470,40 +581,65 @@ isis_spf_add_local (struct isis_spftree *spftree, enum vertextype vtype,
 	  /*       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;
 	}
-      /*         f) */
-      else if (vertex->d_N > cost)
+      else if (vertex->d_N < cost)
 	{
-	  listnode_delete (spftree->tents, vertex);
-	  goto add2tent;
+	  /*       e) do nothing */
+	  return;
 	}
-      /*       e) do nothing */
-      return vertex;
+      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);
+      }
     }
 
-add2tent:
-  return isis_spf_add2tent (spftree, vtype, id, adj, cost, 1, family);
+  isis_spf_add2tent (spftree, vtype, id, cost, 1, family, adj, parent);
+  return;
 }
 
 static 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)
+	   uint32_t dist, uint16_t depth, int family,
+	   struct isis_vertex *parent)
 {
   struct isis_vertex *vertex;
 #ifdef EXTREME_DEBUG
   u_char buff[255];
 #endif
 
+  assert (spftree && parent);
+
+  /* RFC3787 section 5.1 */
+  if (spftree->area->newmetric == 1)
+    {
+      if (dist > MAX_WIDE_PATH_METRIC)
+        return;
+    }
   /* C.2.6 b)    */
-  if (dist > MAX_PATH_METRIC)
-    return;
+  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 dist %d already found from PATH",
+      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), dist);
 #endif /* EXTREME_DEBUG */
       assert (dist >= vertex->d_N);
@@ -516,16 +652,26 @@ process_N (struct isis_spftree *spftree, enum vertextype vtype, void *id,
     {
       /*        1) */
 #ifdef EXTREME_DEBUG
-      zlog_debug ("ISIS-Spf: process_N  %s %s dist %d",
-		  vtype2string (vtype), vid2string (vertex, buff), dist);
+      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), dist,
+                  (parent ? print_sys_hostname (parent->N.id) : "null"),
+                  (parent ? listcount (parent->Adj_N) : 0));
 #endif /* EXTREME_DEBUG */
       if (vertex->d_N == dist)
 	{
-	  if (adj)
-	    listnode_add (vertex->Adj_N, adj);
+	  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;
 	}
@@ -536,11 +682,23 @@ process_N (struct isis_spftree *spftree, enum vertextype vtype, void *id,
 	}
       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);
 	}
     }
 
-  isis_spf_add2tent (spftree, vtype, id, adj, dist, depth, family);
+#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, family, NULL, parent);
   return;
 }
 
@@ -549,10 +707,11 @@ process_N (struct isis_spftree *spftree, enum vertextype vtype, void *id,
  */
 static int
 isis_spf_process_lsp (struct isis_spftree *spftree, struct isis_lsp *lsp,
-		      uint32_t cost, uint16_t depth, int family)
+		      uint32_t cost, uint16_t depth, int family,
+		      u_char *root_sysid, struct isis_vertex *parent)
 {
   struct listnode *node, *fragnode = NULL;
-  u_int16_t dist;
+  uint32_t dist;
   struct is_neigh *is_neigh;
   struct te_is_neigh *te_is_neigh;
   struct ipv4_reachability *ipreach;
@@ -562,117 +721,121 @@ isis_spf_process_lsp (struct isis_spftree *spftree, struct isis_lsp *lsp,
 #ifdef HAVE_IPV6
   struct ipv6_reachability *ip6reach;
 #endif /* HAVE_IPV6 */
+  static const u_char null_sysid[ISIS_SYS_ID_LEN];
 
-
-  if (!lsp->adj)
-    return ISIS_WARNING;
-  if (lsp->tlv_data.nlpids == NULL || !speaks (lsp->tlv_data.nlpids, family))
+  if (!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");
+      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 */
+
   if (!ISIS_MASK_LSP_OL_BIT (lsp->lsp_header->lsp_bits))
+  {
+    if (lsp->tlv_data.is_neighs)
     {
-      if (lsp->tlv_data.is_neighs)
-	{
-          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, 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 (lsp->tlv_data.te_is_neighs)
-	{
-	  for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.te_is_neighs, node,
-				     te_is_neigh))
-	    {
-	      uint32_t metric;
-	      if (!memcmp (te_is_neigh->neigh_id, isis->sysid, ISIS_SYS_ID_LEN))
-		continue;
-	      memcpy (&metric, te_is_neigh->te_metric, 3);
-	      dist = cost + ntohl (metric << 8);
-	      vtype = LSP_PSEUDO_ID (te_is_neigh->neigh_id) ? VTYPE_PSEUDO_TE_IS
-		: VTYPE_NONPSEUDO_TE_IS;
-	      process_N (spftree, vtype, (void *) te_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 (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.ipv4_int_reachs, 
-                                     node, ipreach))
-	    {
-	      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);
-	    }
-	}
+      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 (!memcmp (is_neigh->neigh_id, null_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, family, parent);
+      }
+    }
+    if (lsp->tlv_data.te_is_neighs)
+    {
+      for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.te_is_neighs, node,
+            te_is_neigh))
+      {
+        if (!memcmp (te_is_neigh->neigh_id, root_sysid, ISIS_SYS_ID_LEN))
+          continue;
+        if (!memcmp (te_is_neigh->neigh_id, null_sysid, ISIS_SYS_ID_LEN))
+          continue;
+        dist = cost + GET_TE_METRIC(te_is_neigh);
+        vtype = LSP_PSEUDO_ID (te_is_neigh->neigh_id) ? VTYPE_PSEUDO_TE_IS
+          : VTYPE_NONPSEUDO_TE_IS;
+        process_N (spftree, vtype, (void *) te_is_neigh->neigh_id, dist,
+            depth + 1, family, parent);
+      }
+    }
+  }
 
-      if (family == AF_INET && lsp->tlv_data.ipv4_ext_reachs)
-	{
-	  prefix.family = AF_INET;
-          for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.ipv4_ext_reachs,
-                                     node, ipreach))
-	    {
-	      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);
-	    }
-	}
-      if (family == AF_INET && lsp->tlv_data.te_ipv4_reachs)
-	{
-	  prefix.family = AF_INET;
-	  for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.te_ipv4_reachs,
-				     node, te_ipv4_reach))
-	    {
-	      dist = cost + ntohl (te_ipv4_reach->te_metric);
-	      vtype = VTYPE_IPREACH_TE;
-	      prefix.u.prefix4 = newprefix2inaddr (&te_ipv4_reach->prefix_start,
-						   te_ipv4_reach->control);
-	      prefix.prefixlen = (te_ipv4_reach->control & 0x3F);
-	      process_N (spftree, vtype, (void *) &prefix, dist, depth + 1,
-			 lsp->adj, family);
-	    }
-	}
+  if (family == AF_INET && lsp->tlv_data.ipv4_int_reachs)
+  {
+    prefix.family = AF_INET;
+    for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.ipv4_int_reachs, node, ipreach))
+    {
+      dist = cost + ipreach->metrics.metric_default;
+      vtype = VTYPE_IPREACH_INTERNAL;
+      prefix.u.prefix4 = ipreach->prefix;
+      prefix.prefixlen = ip_masklen (ipreach->mask);
+      apply_mask (&prefix);
+      process_N (spftree, vtype, (void *) &prefix, dist, depth + 1,
+                 family, parent);
+    }
+  }
+  if (family == AF_INET && lsp->tlv_data.ipv4_ext_reachs)
+  {
+    prefix.family = AF_INET;
+    for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.ipv4_ext_reachs, node, ipreach))
+    {
+      dist = cost + ipreach->metrics.metric_default;
+      vtype = VTYPE_IPREACH_EXTERNAL;
+      prefix.u.prefix4 = ipreach->prefix;
+      prefix.prefixlen = ip_masklen (ipreach->mask);
+      apply_mask (&prefix);
+      process_N (spftree, vtype, (void *) &prefix, dist, depth + 1,
+                 family, parent);
+    }
+  }
+  if (family == AF_INET && lsp->tlv_data.te_ipv4_reachs)
+  {
+    prefix.family = AF_INET;
+    for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.te_ipv4_reachs,
+                               node, te_ipv4_reach))
+    {
+      dist = cost + ntohl (te_ipv4_reach->te_metric);
+      vtype = VTYPE_IPREACH_TE;
+      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, (void *) &prefix, dist, depth + 1,
+                 family, parent);
+    }
+  }
 #ifdef HAVE_IPV6
-      if (family == AF_INET6 && lsp->tlv_data.ipv6_reachs)
-	{
-	  prefix.family = AF_INET6;
-          for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.ipv6_reachs, 
-                                     node, ip6reach))
-	    {
-	      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 (family == AF_INET6 && lsp->tlv_data.ipv6_reachs)
+  {
+    prefix.family = AF_INET6;
+    for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.ipv6_reachs, node, ip6reach))
+    {
+      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));
+      apply_mask (&prefix);
+      process_N (spftree, vtype, (void *) &prefix, dist, depth + 1,
+                 family, parent);
     }
+  }
+#endif /* HAVE_IPV6 */
 
   if (fragnode == NULL)
     fragnode = listhead (lsp->lspu.frags);
@@ -690,13 +853,16 @@ lspfragloop:
 
 static int
 isis_spf_process_pseudo_lsp (struct isis_spftree *spftree,
-			     struct isis_lsp *lsp, uint16_t cost,
-			     uint16_t depth, int family)
+			     struct isis_lsp *lsp, uint32_t cost,
+			     uint16_t depth, int family,
+			     u_char *root_sysid,
+			     struct isis_vertex *parent)
 {
   struct listnode *node, *fragnode = NULL;
   struct is_neigh *is_neigh;
   struct te_is_neigh *te_is_neigh;
   enum vertextype vtype;
+  uint32_t dist;
 
 pseudofragloop:
 
@@ -707,41 +873,36 @@ pseudofragloop:
       return ISIS_WARNING;
     }
 
+#ifdef EXTREME_DEBUG
+      zlog_debug ("ISIS-Spf: process_pseudo_lsp %s",
+                  print_sys_hostname(lsp->lsp_header->lsp_id));
+#endif /* EXTREME_DEBUG */
+
+  /* RFC3787 section 4 SHOULD ignore overload bit in pseudo LSPs */
+
   if (lsp->tlv_data.is_neighs)
     for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.is_neighs, node, is_neigh))
       {
-	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))
+	if (!memcmp (is_neigh->neigh_id, root_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);
-	  }
+        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, family, parent);
       }
   if (lsp->tlv_data.te_is_neighs)
     for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.te_is_neighs, node, te_is_neigh))
       {
-	vtype = LSP_PSEUDO_ID (te_is_neigh->neigh_id) ? VTYPE_PSEUDO_TE_IS
-	  : VTYPE_NONPSEUDO_TE_IS;
 	/* Two way connectivity */
-	if (!memcmp (te_is_neigh->neigh_id, isis->sysid, ISIS_SYS_ID_LEN))
+	if (!memcmp (te_is_neigh->neigh_id, root_sysid, ISIS_SYS_ID_LEN))
 	  continue;
-	if (isis_find_vertex
-	    (spftree->tents, (void *) te_is_neigh->neigh_id, vtype) == NULL
-	    && isis_find_vertex (spftree->paths, (void *) te_is_neigh->neigh_id,
-				 vtype) == NULL)
-	  {
-	    /* C.2.5 i) */
-	    isis_spf_add2tent (spftree, vtype, te_is_neigh->neigh_id, lsp->adj,
-			       cost, depth, family);
-	  }
+        dist = cost + GET_TE_METRIC(te_is_neigh);
+        vtype = LSP_PSEUDO_ID (te_is_neigh->neigh_id) ? VTYPE_PSEUDO_TE_IS
+          : VTYPE_NONPSEUDO_TE_IS;
+        process_N (spftree, vtype, (void *) te_is_neigh->neigh_id, dist,
+            depth + 1, family, parent);
       }
 
   if (fragnode == NULL)
@@ -759,10 +920,10 @@ pseudofragloop:
 }
 
 static int
-isis_spf_preload_tent (struct isis_spftree *spftree,
-		       struct isis_area *area, int level, int family)
+isis_spf_preload_tent (struct isis_spftree *spftree, int level,
+		       int family, u_char *root_sysid,
+		       struct isis_vertex *parent)
 {
-  struct isis_vertex *vertex;
   struct isis_circuit *circuit;
   struct listnode *cnode, *anode, *ipnode;
   struct isis_adjacency *adj;
@@ -773,15 +934,16 @@ isis_spf_preload_tent (struct isis_spftree *spftree,
   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];
 #ifdef HAVE_IPV6
   struct prefix_ipv6 *ipv6;
 #endif /* HAVE_IPV6 */
 
-  for (ALL_LIST_ELEMENTS_RO (area->circuit_list, cnode, circuit))
+  for (ALL_LIST_ELEMENTS_RO (spftree->area->circuit_list, cnode, circuit))
     {
       if (circuit->state != C_STATE_UP)
 	continue;
-      if (!(circuit->circuit_is_type & level))
+      if (!(circuit->is_type & level))
 	continue;
       if (family == AF_INET && !circuit->ip_router)
 	continue;
@@ -799,8 +961,9 @@ isis_spf_preload_tent (struct isis_spftree *spftree,
 	    {
 	      prefix.u.prefix4 = ipv4->prefix;
 	      prefix.prefixlen = ipv4->prefixlen;
+              apply_mask (&prefix);
 	      isis_spf_add_local (spftree, VTYPE_IPREACH_INTERNAL, &prefix,
-				  NULL, 0, family);
+				  NULL, 0, family, parent);
 	    }
 	}
 #ifdef HAVE_IPV6
@@ -811,8 +974,9 @@ isis_spf_preload_tent (struct isis_spftree *spftree,
 	    {
 	      prefix.prefixlen = ipv6->prefixlen;
 	      prefix.u.prefix6 = ipv6->prefix;
+              apply_mask (&prefix);
 	      isis_spf_add_local (spftree, VTYPE_IP6REACH_INTERNAL,
-				  &prefix, NULL, 0, family);
+				  &prefix, NULL, 0, family, parent);
 	    }
 	}
 #endif /* HAVE_IPV6 */
@@ -832,43 +996,41 @@ isis_spf_preload_tent (struct isis_spftree *spftree,
 			    level, circuit->interface->name);
 	      continue;
 	    }
-	  anode = listhead (adj_list);
-	  while (anode)
+          for (ALL_LIST_ELEMENTS_RO (adj_list, anode, adj))
 	    {
-	      adj = listgetdata (anode);
 	      if (!speaks (&adj->nlpids, family))
-		{
-		  anode = listnextnode (anode);
 		  continue;
-		}
 	      switch (adj->sys_type)
 		{
 		case ISIS_SYSTYPE_ES:
 		  isis_spf_add_local (spftree, VTYPE_ES, adj->sysid, adj,
-				      circuit->te_metric[level - 1], family);
+				      circuit->te_metric[level - 1],
+				      family, parent);
 		  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->te_metric[level - 1], family);
+		  isis_spf_add_local (spftree,
+                                      spftree->area->oldmetric ?
+                                      VTYPE_NONPSEUDO_IS :
+                                      VTYPE_NONPSEUDO_TE_IS,
+                                      adj->sysid, adj,
+                                      circuit->te_metric[level - 1],
+                                      family, parent);
 		  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]);
+		  lsp = lsp_search (lsp_id, spftree->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);
-		     } */
+                    zlog_warn ("ISIS-Spf: No LSP %s found for IS adjacency "
+                        "L%d on %s (ID %u)",
+			rawlspid_print (lsp_id), level,
+			circuit->interface->name, circuit->circuit_id);
 		  break;
 		case ISIS_SYSTYPE_UNKNOWN:
 		default:
 		  zlog_warn ("isis_spf_preload_tent unknow adj type");
 		}
-	      anode = listnextnode (anode);
 	    }
 	  list_delete (adj_list);
 	  /*
@@ -878,23 +1040,36 @@ isis_spf_preload_tent (struct isis_spftree *spftree,
 	    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]);
+	  /* 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)",
+		    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[level - 1])
 	    {
-	      zlog_warn ("ISIS-Spf: No adjacency found for DR");
+              zlog_warn ("ISIS-Spf: No adjacency found from root "
+                  "to L%d DR %s on %s (ID %d)",
+		  level, rawlspid_print (lsp_id),
+		  circuit->interface->name, circuit->circuit_id);
+              continue;
 	    }
+	  lsp = lsp_search (lsp_id, spftree->area->lspdb[level - 1]);
 	  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->te_metric[level - 1], 0, family);
-
+	      zlog_warn ("ISIS-Spf: No lsp (%p) found from root "
+                  "to L%d DR %s on %s (ID %d)",
+		  lsp, level, rawlspid_print (lsp_id), 
+		  circuit->interface->name, circuit->circuit_id);
+              continue;
 	    }
+	  isis_spf_process_pseudo_lsp (spftree, lsp,
+                                       circuit->te_metric[level - 1], 0,
+                                       family, root_sysid, parent);
 	}
       else if (circuit->circ_type == CIRCUIT_T_P2P)
 	{
@@ -905,28 +1080,36 @@ isis_spf_preload_tent (struct isis_spftree *spftree,
 	    {
 	    case ISIS_SYSTYPE_ES:
 	      isis_spf_add_local (spftree, VTYPE_ES, adj->sysid, adj,
-				  circuit->te_metric[level - 1], family);
+				  circuit->te_metric[level - 1], family,
+				  parent);
 	      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,
+		isis_spf_add_local (spftree,
+				    spftree->area->oldmetric ?
+                                    VTYPE_NONPSEUDO_IS :
+				    VTYPE_NONPSEUDO_TE_IS,
+                                    adj->sysid,
 				    adj, circuit->te_metric[level - 1],
-				    family);
+				    family, parent);
 	      break;
 	    case ISIS_SYSTYPE_UNKNOWN:
 	    default:
-	      zlog_warn ("isis_spf_preload_tent unknow adj type");
+	      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;
@@ -938,25 +1121,30 @@ isis_spf_preload_tent (struct isis_spftree *spftree,
  */
 static void
 add_to_paths (struct isis_spftree *spftree, struct isis_vertex *vertex,
-	      struct isis_area *area, int level)
+	      int level)
 {
-#ifdef EXTREME_DEBUG
   u_char buff[BUFSIZ];
-#endif /* EXTREME_DEBUG */
+
+  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 depth %d dist %d to PATHS",
+  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),
 	      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, level);
+			   vertex->depth, vertex->Adj_N, spftree->area, level);
       else if (isis->debugs & DEBUG_SPF_EVENTS)
-	zlog_debug ("ISIS-Spf: no adjacencies do not install route");
+	zlog_debug ("ISIS-Spf: no adjacencies do not install route for "
+                    "%s depth %d dist %d", vid2string (vertex, buff),
+                    vertex->depth, vertex->d_N);
     }
 
   return;
@@ -969,22 +1157,20 @@ init_spt (struct isis_spftree *spftree)
   list_delete_all_node (spftree->tents);
   list_delete_all_node (spftree->paths);
   spftree->tents->del = spftree->paths->del = NULL;
-
   return;
 }
 
 static int
-isis_run_spf (struct isis_area *area, int level, int family)
+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 route_node *rode;
-  struct isis_route_info *rinfo;
 
   if (family == AF_INET)
     spftree = area->spftree[level - 1];
@@ -992,8 +1178,8 @@ isis_run_spf (struct isis_area *area, int level, int family)
   else if (family == AF_INET6)
     spftree = area->spftree6[level - 1];
 #endif
-
   assert (spftree);
+  assert (sysid);
 
   /* Make all routes in current route table inactive. */
   if (family == AF_INET)
@@ -1003,30 +1189,28 @@ isis_run_spf (struct isis_area *area, int level, int family)
     table = area->route_table6[level - 1];
 #endif
 
-  for (rode = route_top (table); rode; rode = route_next (rode))
-    {
-      if (rode->info == NULL)
-        continue;
-      rinfo = rode->info;
-
-      UNSET_FLAG (rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE);
-    }
+  isis_route_invalidate_table (area, table);
 
   /*
    * C.2.5 Step 0
    */
   init_spt (spftree);
   /*              a) */
-  isis_spf_add_self (spftree, area, level);
+  root_vertex = isis_spf_add_root (spftree, level, sysid);
   /*              b) */
-  retval = isis_spf_preload_tent (spftree, area, level, family);
+  retval = isis_spf_preload_tent (spftree, level, family, 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");
+      zlog_warn ("ISIS-Spf: TENT is empty SPF-root:%s", print_sys_hostname(sysid));
       goto out;
     }
 
@@ -1034,14 +1218,22 @@ isis_run_spf (struct isis_area *area, int level, int family)
     {
       node = listhead (spftree->tents);
       vertex = listgetdata (node);
-      /* Remove from tent list */
+
+#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);
-      if (isis_find_vertex (spftree->paths, vertex->N.id, vertex->type))
-	continue;
-      add_to_paths (spftree, vertex, area, level);
-      if (vertex->type == VTYPE_PSEUDO_IS ||
-	  vertex->type == VTYPE_NONPSEUDO_IS)
-	{
+      add_to_paths (spftree, vertex, level);
+      switch (vertex->type)
+        {
+	case VTYPE_PSEUDO_IS:
+	case VTYPE_NONPSEUDO_IS:
+	case VTYPE_PSEUDO_TE_IS:
+	case VTYPE_NONPSEUDO_TE_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]);
@@ -1050,13 +1242,13 @@ isis_run_spf (struct isis_area *area, int level, int family)
 	      if (LSP_PSEUDO_ID (lsp_id))
 		{
 		  isis_spf_process_pseudo_lsp (spftree, lsp, vertex->d_N,
-					       vertex->depth, family);
-
+					       vertex->depth, family, sysid,
+					       vertex);
 		}
 	      else
 		{
 		  isis_spf_process_lsp (spftree, lsp, vertex->d_N,
-					vertex->depth, family);
+					vertex->depth, family, sysid, vertex);
 		}
 	    }
 	  else
@@ -1064,12 +1256,15 @@ isis_run_spf (struct isis_area *area, int level, int family)
 	      zlog_warn ("ISIS-Spf: No LSP found for %s",
 			 rawlspid_print (lsp_id));
 	    }
+	  break;
+	default:;
 	}
     }
 
 out:
-  thread_add_event (master, isis_route_validate, area, 0);
+  isis_route_validate (area);
   spftree->lastrun = time (NULL);
+  spftree->runcount++;
   spftree->pending = 0;
 
   return retval;
@@ -1085,6 +1280,7 @@ isis_run_spf_l1 (struct thread *thread)
   assert (area);
 
   area->spftree[0]->t_spf = NULL;
+  area->spftree[0]->pending = 0;
 
   if (!(area->is_type & IS_LEVEL_1))
     {
@@ -1098,10 +1294,7 @@ isis_run_spf_l1 (struct thread *thread)
     zlog_debug ("ISIS-Spf (%s) L1 SPF needed, periodic SPF", area->area_tag);
 
   if (area->ip_circuits)
-    retval = isis_run_spf (area, 1, AF_INET);
-
-  THREAD_TIMER_ON (master, area->spftree[0]->t_spf, isis_run_spf_l1, area,
-		   isis_jitter (PERIODIC_SPF_INTERVAL, 10));
+    retval = isis_run_spf (area, 1, AF_INET, isis->sysid);
 
   return retval;
 }
@@ -1116,6 +1309,7 @@ isis_run_spf_l2 (struct thread *thread)
   assert (area);
 
   area->spftree[1]->t_spf = NULL;
+  area->spftree[1]->pending = 0;
 
   if (!(area->is_type & IS_LEVEL_2))
     {
@@ -1128,10 +1322,7 @@ isis_run_spf_l2 (struct thread *thread)
     zlog_debug ("ISIS-Spf (%s) L2 SPF needed, periodic SPF", area->area_tag);
 
   if (area->ip_circuits)
-    retval = isis_run_spf (area, 2, AF_INET);
-
-  THREAD_TIMER_ON (master, area->spftree[1]->t_spf, isis_run_spf_l2, area,
-		   isis_jitter (PERIODIC_SPF_INTERVAL, 10));
+    retval = isis_run_spf (area, 2, AF_INET, isis->sysid);
 
   return retval;
 }
@@ -1139,53 +1330,40 @@ isis_run_spf_l2 (struct thread *thread)
 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;
+  time_t now = time (NULL);
+  int diff = now - spftree->lastrun;
 
-  diff = now - spftree->lastrun;
+  assert (diff >= 0);
+  assert (area->is_type & level);
 
-  /* FIXME: let's wait a minute before doing the SPF */
-  if (now - isis->uptime < 60 || isis->uptime == 0)
-    {
-      if (level == 1)
-	THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l1, area, 60);
-      else
-	THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l2, area, 60);
+  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);
 
-      spftree->pending = 1;
-      return retval;
-    }
+  if (spftree->pending)
+    return ISIS_OK;
 
   THREAD_TIMER_OFF (spftree->t_spf);
 
-  if (diff < MINIMUM_SPF_INTERVAL)
-    {
-      if (level == 1)
-	THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l1, area,
-			 MINIMUM_SPF_INTERVAL - diff);
-      else
-	THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l2, area,
-			 MINIMUM_SPF_INTERVAL - diff);
+  /* wait MINIMUM_SPF_INTERVAL before doing the SPF */
+  if (diff >= MINIMUM_SPF_INTERVAL)
+      return isis_run_spf (area, level, AF_INET, isis->sysid);
 
-      spftree->pending = 1;
-    }
+  if (level == 1)
+    THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l1, area,
+                     MINIMUM_SPF_INTERVAL - diff);
   else
-    {
-      spftree->pending = 0;
-      retval = isis_run_spf (area, level, AF_INET);
-      if (level == 1)
-	THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l1, area,
-			 isis_jitter (PERIODIC_SPF_INTERVAL, 10));
-      else
-	THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l2, area,
-			 isis_jitter (PERIODIC_SPF_INTERVAL, 10));
-    }
+    THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l2, area,
+                     MINIMUM_SPF_INTERVAL - diff);
 
-  return retval;
+  if (isis->debugs & DEBUG_SPF_EVENTS)
+    zlog_debug ("ISIS-Spf (%s) L%d SPF scheduled %d sec from now",
+                area->area_tag, level, MINIMUM_SPF_INTERVAL - diff);
+
+  spftree->pending = 1;
+
+  return ISIS_OK;
 }
 
 #ifdef HAVE_IPV6
@@ -1199,11 +1377,12 @@ isis_run_spf6_l1 (struct thread *thread)
   assert (area);
 
   area->spftree6[0]->t_spf = NULL;
+  area->spftree6[0]->pending = 0;
 
   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);
+        zlog_warn ("ISIS-SPF (%s) area does not share level", area->area_tag);
       return ISIS_WARNING;
     }
 
@@ -1211,10 +1390,7 @@ isis_run_spf6_l1 (struct thread *thread)
     zlog_debug ("ISIS-Spf (%s) L1 SPF needed, periodic SPF", area->area_tag);
 
   if (area->ipv6_circuits)
-    retval = isis_run_spf (area, 1, AF_INET6);
-
-  THREAD_TIMER_ON (master, area->spftree6[0]->t_spf, isis_run_spf6_l1, area,
-		   isis_jitter (PERIODIC_SPF_INTERVAL, 10));
+    retval = isis_run_spf (area, 1, AF_INET6, isis->sysid);
 
   return retval;
 }
@@ -1229,6 +1405,7 @@ isis_run_spf6_l2 (struct thread *thread)
   assert (area);
 
   area->spftree6[1]->t_spf = NULL;
+  area->spftree6[1]->pending = 0;
 
   if (!(area->is_type & IS_LEVEL_2))
     {
@@ -1241,10 +1418,7 @@ isis_run_spf6_l2 (struct thread *thread)
     zlog_debug ("ISIS-Spf (%s) L2 SPF needed, periodic SPF.", area->area_tag);
 
   if (area->ipv6_circuits)
-    retval = isis_run_spf (area, 2, AF_INET6);
-
-  THREAD_TIMER_ON (master, area->spftree6[1]->t_spf, isis_run_spf6_l2, area,
-		   isis_jitter (PERIODIC_SPF_INTERVAL, 10));
+    retval = isis_run_spf (area, 2, AF_INET6, isis->sysid);
 
   return retval;
 }
@@ -1259,22 +1433,14 @@ isis_spf_schedule6 (struct isis_area *area, int level)
   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_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l1, area, 60);
-      else
-	THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l2, area, 60);
-
-      spftree->pending = 1;
-      return retval;
-    }
-  
   THREAD_TIMER_OFF (spftree->t_spf);
 
+  /* FIXME: let's wait MINIMUM_SPF_INTERVAL before doing the SPF */
+  if (now - isis->uptime < MINIMUM_SPF_INTERVAL || isis->uptime == 0)
+      diff = 0;
+  else
+      diff = now - spftree->lastrun;
+
   if (diff < MINIMUM_SPF_INTERVAL)
     {
       if (level == 1)
@@ -1288,15 +1454,7 @@ isis_spf_schedule6 (struct isis_area *area, int level)
     }
   else
     {
-      spftree->pending = 0;
-      retval = isis_run_spf (area, level, AF_INET6);
-
-      if (level == 1)
-	THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l1, area,
-			 isis_jitter (PERIODIC_SPF_INTERVAL, 10));
-      else
-	THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l2, area,
-			 isis_jitter (PERIODIC_SPF_INTERVAL, 10));
+      retval = isis_run_spf (area, level, AF_INET6, isis->sysid);
     }
 
   return retval;
@@ -1304,54 +1462,73 @@ isis_spf_schedule6 (struct isis_area *area, int level)
 #endif
 
 static void
-isis_print_paths (struct vty *vty, struct list *paths)
+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_dynhn *dyn, *nh_dyn = NULL;
   struct isis_adjacency *adj;
-#if 0
   u_char buff[255];
-#endif /* 0 */
 
-  vty_out (vty, "System Id            Metric     Next-Hop"
-	   "             Interface   SNPA%s", VTY_NEWLINE);
+  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),
+	         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 ", "");
+      }
 
-  for (ALL_LIST_ELEMENTS_RO (paths, node, vertex))
-    {
-      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?host.name:"",
-		   VTY_NEWLINE);
+      /* 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), pvertex->type);
+	  ++rows;
 	}
-      else
-	{
-	  dyn = dynhn_find_by_id ((u_char *) vertex->N.id);
-	  adj = listgetdata (listhead (vertex->Adj_N));
-	  if (adj)
-	    {
-	      nh_dyn = dynhn_find_by_id (adj->sysid);
-	      vty_out (vty, "%-20s %-10u %-20s %-11s %-5s%s",
-		       (dyn != NULL) ? dyn->name.name :
-		       (const u_char *)rawlspid_print ((u_char *) vertex->N.id),
-		       vertex->d_N, (nh_dyn != NULL) ? nh_dyn->name.name :
-		       (const 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 :
-		       (const u_char *) rawlspid_print (vertex->N.id),
-		       vertex->d_N, VTY_NEWLINE);
+      } else {
+	vty_out (vty, "  NULL ");
+      }
+
+#if 0
+      if (listcount (vertex->children) > 0) {
+	  struct listnode *cnode;
+	  struct isis_vertex *cvertex;
+	  for (ALL_LIST_ELEMENTS_RO (vertex->children, cnode, cvertex)) {
+	      vty_out (vty, "%s", VTY_NEWLINE);
+	      vty_out (vty, "%-72s", "");
+	      vty_out (vty, "%s(%d) ", 
+	               vid2string (cvertex, buff), cvertex->type);
 	    }
 	}
-#if 0
-      vty_out (vty, "%s %s %u %s", vtype2string (vertex->type),
-	       vid2string (vertex, buff), vertex->d_N, VTY_NEWLINE);
 #endif
+      vty_out (vty, "%s", VTY_NEWLINE);
     }
 }
 
@@ -1381,7 +1558,8 @@ DEFUN (show_isis_topology,
 	    {
 	      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);
+	      isis_print_paths (vty, area->spftree[level]->paths, isis->sysid);
+	      vty_out (vty, "%s", VTY_NEWLINE);
 	    }
 #ifdef HAVE_IPV6
 	  if (area->ipv6_circuits > 0 && area->spftree6[level]
@@ -1390,10 +1568,13 @@ DEFUN (show_isis_topology,
 	      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);
+	      isis_print_paths (vty, area->spftree6[level]->paths, isis->sysid);
+	      vty_out (vty, "%s", VTY_NEWLINE);
 	    }
 #endif /* HAVE_IPV6 */
 	}
+
+      vty_out (vty, "%s", VTY_NEWLINE);
     }
 
   return CMD_SUCCESS;
@@ -1423,7 +1604,8 @@ DEFUN (show_isis_topology_l1,
 	{
 	  vty_out (vty, "IS-IS paths to level-1 routers that speak IP%s",
 		   VTY_NEWLINE);
-	  isis_print_paths (vty, area->spftree[0]->paths);
+	  isis_print_paths (vty, area->spftree[0]->paths, isis->sysid);
+	  vty_out (vty, "%s", VTY_NEWLINE);
 	}
 #ifdef HAVE_IPV6
       if (area->ipv6_circuits > 0 && area->spftree6[0]
@@ -1431,9 +1613,11 @@ DEFUN (show_isis_topology_l1,
 	{
 	  vty_out (vty, "IS-IS paths to level-1 routers that speak IPv6%s",
 		   VTY_NEWLINE);
-	  isis_print_paths (vty, area->spftree6[0]->paths);
+	  isis_print_paths (vty, area->spftree6[0]->paths, isis->sysid);
+	  vty_out (vty, "%s", VTY_NEWLINE);
 	}
 #endif /* HAVE_IPV6 */
+      vty_out (vty, "%s", VTY_NEWLINE);
     }
 
   return CMD_SUCCESS;
@@ -1463,7 +1647,8 @@ DEFUN (show_isis_topology_l2,
 	{
 	  vty_out (vty, "IS-IS paths to level-2 routers that speak IP%s",
 		   VTY_NEWLINE);
-	  isis_print_paths (vty, area->spftree[1]->paths);
+	  isis_print_paths (vty, area->spftree[1]->paths, isis->sysid);
+	  vty_out (vty, "%s", VTY_NEWLINE);
 	}
 #ifdef HAVE_IPV6
       if (area->ipv6_circuits > 0 && area->spftree6[1]
@@ -1471,9 +1656,11 @@ DEFUN (show_isis_topology_l2,
 	{
 	  vty_out (vty, "IS-IS paths to level-2 routers that speak IPv6%s",
 		   VTY_NEWLINE);
-	  isis_print_paths (vty, area->spftree6[1]->paths);
+	  isis_print_paths (vty, area->spftree6[1]->paths, isis->sysid);
+	  vty_out (vty, "%s", VTY_NEWLINE);
 	}
 #endif /* HAVE_IPV6 */
+      vty_out (vty, "%s", VTY_NEWLINE);
     }
 
   return CMD_SUCCESS;