Initial revision

1 files changed, 1088 insertions, 0 deletions

diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c
new file mode 100644
index 00000000..d6254717
--- /dev/null
+++ b/ospfd/ospf_spf.c
@@ -0,0 +1,1088 @@
+/* OSPF SPF calculation.
+   Copyright (C) 1999, 2000 Kunihiro Ishiguro, Toshiaki Takada
+
+This file is part of GNU Zebra.
+
+GNU Zebra is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by the
+Free Software Foundation; either version 2, or (at your option) any
+later version.
+
+GNU Zebra 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 GNU Zebra; see the file COPYING.  If not, write to the Free
+Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA.  */
+
+#include <zebra.h>
+
+#include "thread.h"
+#include "memory.h"
+#include "hash.h"
+#include "linklist.h"
+#include "prefix.h"
+#include "if.h"
+#include "table.h"
+#include "log.h"
+#include "sockunion.h"          /* for inet_ntop () */
+
+#include "ospfd/ospfd.h"
+#include "ospfd/ospf_interface.h"
+#include "ospfd/ospf_ism.h"
+#include "ospfd/ospf_asbr.h"
+#include "ospfd/ospf_lsa.h"
+#include "ospfd/ospf_lsdb.h"
+#include "ospfd/ospf_neighbor.h"
+#include "ospfd/ospf_nsm.h"
+#include "ospfd/ospf_spf.h"
+#include "ospfd/ospf_route.h"
+#include "ospfd/ospf_ia.h"
+#include "ospfd/ospf_ase.h"
+#include "ospfd/ospf_abr.h"
+#include "ospfd/ospf_dump.h"
+
+#define DEBUG
+
+struct vertex_nexthop *
+vertex_nexthop_new (struct vertex *parent)
+{
+  struct vertex_nexthop *new;
+
+  new = XCALLOC (MTYPE_OSPF_NEXTHOP, sizeof (struct vertex_nexthop));
+  new->parent = parent;
+
+  return new;
+}
+
+void
+vertex_nexthop_free (struct vertex_nexthop *nh)
+{
+  XFREE (MTYPE_OSPF_NEXTHOP, nh);
+}
+
+struct vertex_nexthop *
+vertex_nexthop_dup (struct vertex_nexthop *nh)
+{
+  struct vertex_nexthop *new;
+
+  new = vertex_nexthop_new (nh->parent);
+
+  new->oi = nh->oi;
+  new->router = nh->router;
+
+  return new;
+}
+
+
+struct vertex *
+ospf_vertex_new (struct ospf_lsa *lsa)
+{
+  struct vertex *new;
+
+  new = XMALLOC (MTYPE_OSPF_VERTEX, sizeof (struct vertex));
+  memset (new, 0, sizeof (struct vertex));
+
+  new->flags = 0;
+  new->type = lsa->data->type;
+  new->id = lsa->data->id;
+  new->lsa = lsa->data;
+  new->distance = 0;
+  new->child = list_new ();
+  new->nexthop = list_new ();
+
+  return new;
+}
+
+void
+ospf_vertex_free (struct vertex *v)
+{
+  listnode node;
+
+  list_delete (v->child);
+
+  if (listcount (v->nexthop) > 0)
+    for (node = listhead (v->nexthop); node; nextnode (node))
+      vertex_nexthop_free (node->data);
+
+  list_delete (v->nexthop);
+
+  XFREE (MTYPE_OSPF_VERTEX, v);
+}
+
+void
+ospf_vertex_add_parent (struct vertex *v)
+{
+  struct vertex_nexthop *nh;
+  listnode node;
+
+  for (node = listhead (v->nexthop); node; nextnode (node))
+    {
+      nh = (struct vertex_nexthop *) getdata (node);
+
+      /* No need to add two links from the same parent. */
+      if (listnode_lookup (nh->parent->child, v) == NULL)
+	listnode_add (nh->parent->child, v);
+    }
+}
+
+void
+ospf_spf_init (struct ospf_area *area)
+{
+  struct vertex *v;
+
+  /* Create root node. */
+  v = ospf_vertex_new (area->router_lsa_self);
+
+  area->spf = v;
+
+  /* Reset ABR and ASBR router counts. */
+  area->abr_count = 0;
+  area->asbr_count = 0;
+}
+
+int
+ospf_spf_has_vertex (struct route_table *rv, struct route_table *nv,
+                     struct lsa_header *lsa)
+{
+  struct prefix p;
+  struct route_node *rn;
+
+  p.family = AF_INET;
+  p.prefixlen = IPV4_MAX_BITLEN;
+  p.u.prefix4 = lsa->id;
+
+  if (lsa->type == OSPF_ROUTER_LSA)
+    rn = route_node_get (rv, &p);
+  else
+    rn = route_node_get (nv, &p);
+
+  if (rn->info != NULL)
+    {
+      route_unlock_node (rn);
+      return 1;
+    }
+  return 0;
+}
+
+listnode
+ospf_vertex_lookup (list vlist, struct in_addr id, int type)
+{
+  listnode node;
+  struct vertex *v;
+
+  for (node = listhead (vlist); node; nextnode (node))
+    {
+      v = (struct vertex *) getdata (node);
+      if (IPV4_ADDR_SAME (&id, &v->id) && type == v->type)
+        return node;
+    }
+
+  return NULL;
+}
+
+int
+ospf_lsa_has_link (struct lsa_header *w, struct lsa_header *v)
+{
+  int i;
+  int length;
+  struct router_lsa *rl;
+  struct network_lsa *nl;
+
+  /* In case of W is Network LSA. */
+  if (w->type == OSPF_NETWORK_LSA)
+    {
+      if (v->type == OSPF_NETWORK_LSA)
+        return 0;
+
+      nl = (struct network_lsa *) w;
+      length = (ntohs (w->length) - OSPF_LSA_HEADER_SIZE - 4) / 4;
+      
+      for (i = 0; i < length; i++)
+        if (IPV4_ADDR_SAME (&nl->routers[i], &v->id))
+          return 1;
+      return 0;
+    }
+
+  /* In case of W is Router LSA. */
+  if (w->type == OSPF_ROUTER_LSA)
+    {
+      rl = (struct router_lsa *) w;
+
+      length = ntohs (w->length);
+
+      for (i = 0;
+	   i < ntohs (rl->links) && length >= sizeof (struct router_lsa);
+	   i++, length -= 12)
+        {
+          switch (rl->link[i].type)
+            {
+            case LSA_LINK_TYPE_POINTOPOINT:
+            case LSA_LINK_TYPE_VIRTUALLINK:
+              /* Router LSA ID. */
+              if (v->type == OSPF_ROUTER_LSA &&
+                  IPV4_ADDR_SAME (&rl->link[i].link_id, &v->id))
+                {
+                  return 1;
+                }
+              break;
+            case LSA_LINK_TYPE_TRANSIT:
+              /* Network LSA ID. */
+              if (v->type == OSPF_NETWORK_LSA &&
+                  IPV4_ADDR_SAME (&rl->link[i].link_id, &v->id))
+                {
+                  return 1;
+		}
+              break;
+            case LSA_LINK_TYPE_STUB:
+              /* Not take into count? */
+              continue;
+            default:
+              break;
+            }
+        }
+    }
+  return 0;
+}
+
+/* Add the nexthop to the list, only if it is unique.
+ * If it's not unique, free the nexthop entry.
+ */
+void
+ospf_nexthop_add_unique (struct vertex_nexthop *new, list nexthop)
+{
+  struct vertex_nexthop *nh;
+  listnode node;
+  int match;
+
+  match = 0;
+  for (node = listhead (nexthop); node; nextnode (node))
+    {
+      nh = node->data;
+
+      /* Compare the two entries. */
+      /* XXX
+       * Comparing the parent preserves the shortest path tree
+       * structure even when the nexthops are identical.
+       */
+      if (nh->oi == new->oi &&
+	  IPV4_ADDR_SAME (&nh->router, &new->router) &&
+	  nh->parent == new->parent)
+	{
+	  match = 1;
+	  break;
+	}
+    }
+
+  if (!match)
+    listnode_add (nexthop, new);
+  else
+    vertex_nexthop_free (new);
+}
+
+/* Merge entries in list b into list a. */
+void
+ospf_nexthop_merge (list a, list b)
+{
+  struct listnode *n;
+
+  for (n = listhead (b); n; nextnode (n))
+    {
+      ospf_nexthop_add_unique (n->data, a);
+    }
+}
+
+#define ROUTER_LSA_MIN_SIZE 12
+#define ROUTER_LSA_TOS_SIZE 4
+
+struct router_lsa_link *
+ospf_get_next_link (struct vertex *v, struct vertex *w,
+		    struct router_lsa_link *prev_link)
+{
+  u_char *p;
+  u_char *lim;
+  struct router_lsa_link *l;
+
+  if (prev_link == NULL)
+    p = ((u_char *) v->lsa) + 24;
+  else
+    {
+      p = (u_char *)prev_link;
+      p += (ROUTER_LSA_MIN_SIZE +
+            (prev_link->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
+    }
+  
+  lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
+
+  while (p < lim)
+    {
+      l = (struct router_lsa_link *) p;
+
+      p += (ROUTER_LSA_MIN_SIZE +
+            (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
+
+      if (l->m[0].type == LSA_LINK_TYPE_STUB)
+        continue;
+
+      /* Defer NH calculation via VLs until summaries from
+         transit areas area confidered             */
+
+      if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK)
+        continue; 
+
+      if (IPV4_ADDR_SAME (&l->link_id, &w->id))
+          return l;
+    }
+
+  return NULL;
+}
+
+/* Calculate nexthop from root to vertex W. */
+void
+ospf_nexthop_calculation (struct ospf_area *area,
+                          struct vertex *v, struct vertex *w)
+{
+  listnode node;
+  struct vertex_nexthop *nh, *x;
+  struct ospf_interface *oi = NULL;
+  struct router_lsa_link *l = NULL;
+	  
+    
+  if (IS_DEBUG_OSPF_EVENT)
+    zlog_info ("ospf_nexthop_calculation(): Start");
+
+  /* W's parent is root. */
+  if (v == area->spf)
+    {
+      if (w->type == OSPF_VERTEX_ROUTER)
+	{
+	  while ((l = ospf_get_next_link (v, w, l)))
+	    {
+	      struct router_lsa_link *l2 = NULL;
+	      
+	      if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT)
+		{
+		  while ((l2 = ospf_get_next_link (w, v, l2)))
+		    {
+		      oi = ospf_if_is_configured (&(l2->link_data));
+		      
+		      if (oi == NULL)
+			continue;
+		      
+		      if (! IPV4_ADDR_SAME (&oi->address->u.prefix4,
+					    &l->link_data))
+			continue;
+		      
+		      break;
+		    }
+		  
+		  if (oi && l2)
+		    {
+		      nh = vertex_nexthop_new (v);
+		      nh->oi = oi;
+		      nh->router = l2->link_data;
+		      listnode_add (w->nexthop, nh);
+		    }
+		}
+	    }
+	}
+      else
+	{
+	  while ((l = ospf_get_next_link (v, w, l)))
+	    {
+	      oi = ospf_if_is_configured (&(l->link_data));
+	      if (oi)
+		{
+		  nh = vertex_nexthop_new (v);
+		  nh->oi = oi;
+		  nh->router.s_addr = 0;
+		  listnode_add (w->nexthop, nh);
+		}
+	    }
+	}
+      return;
+    }
+  /* In case of W's parent is network connected to root. */
+  else if (v->type == OSPF_VERTEX_NETWORK)
+    {
+      for (node = listhead (v->nexthop); node; nextnode (node))
+        {
+          x = (struct vertex_nexthop *) getdata (node);
+          if (x->parent == area->spf)
+            {
+	      while ((l = ospf_get_next_link (w, v, l)))
+		{
+		  nh = vertex_nexthop_new (v);
+		  nh->oi = x->oi;
+		  nh->router = l->link_data;
+		  listnode_add (w->nexthop, nh);
+		}
+	      return;
+	    }
+        }
+    }
+
+  /* Inherit V's nexthop. */
+  for (node = listhead (v->nexthop); node; nextnode (node))
+    {
+      nh = vertex_nexthop_dup (node->data);
+      nh->parent = v;
+      ospf_nexthop_add_unique (nh, w->nexthop);
+    }
+}
+
+void
+ospf_install_candidate (list candidate, struct vertex *w)
+{
+  listnode node;
+  struct vertex *cw;
+
+  if (list_isempty (candidate))
+    {
+      listnode_add (candidate, w);
+      return;
+    }
+
+  /* Install vertex with sorting by distance. */
+  for (node = listhead (candidate); node; nextnode (node))
+    {
+      cw = (struct vertex *) getdata (node);
+      if (cw->distance > w->distance)
+        {
+          list_add_node_prev (candidate, node, w);
+          break;
+        }
+      else if (node->next == NULL)
+        {
+          list_add_node_next (candidate, node, w);
+          break;
+        }
+    }
+}
+
+/* RFC2328 Section 16.1 (2). */
+void
+ospf_spf_next (struct vertex *v, struct ospf_area *area,
+               list candidate, struct route_table *rv,
+               struct route_table *nv)
+{
+  struct ospf_lsa *w_lsa = NULL;
+  struct vertex *w, *cw;
+  u_char *p;
+  u_char *lim;
+  struct router_lsa_link *l = NULL;
+  struct in_addr *r;
+  listnode node;
+  int type = 0;
+
+  /* If this is a router-LSA, and bit V of the router-LSA (see Section
+     A.4.2:RFC2328) is set, set Area A's TransitCapability to TRUE.  */
+  if (v->type == OSPF_VERTEX_ROUTER)
+    {
+      if (IS_ROUTER_LSA_VIRTUAL ((struct router_lsa *) v->lsa))
+        area->transit = OSPF_TRANSIT_TRUE;
+    }
+
+  p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
+  lim =  ((u_char *) v->lsa) + ntohs (v->lsa->length);
+    
+  while (p < lim)
+    {
+      /* In case of V is Router-LSA. */
+      if (v->lsa->type == OSPF_ROUTER_LSA)
+        {
+          l = (struct router_lsa_link *) p;
+
+          p += (ROUTER_LSA_MIN_SIZE + 
+                (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
+
+          /* (a) If this is a link to a stub network, examine the next
+             link in V's LSA.  Links to stub networks will be
+             considered in the second stage of the shortest path
+             calculation. */
+          if ((type = l->m[0].type) == LSA_LINK_TYPE_STUB)
+            continue;
+
+          /* (b) Otherwise, W is a transit vertex (router or transit
+             network).  Look up the vertex W's LSA (router-LSA or
+             network-LSA) in Area A's link state database. */
+          switch (type)
+            {
+            case LSA_LINK_TYPE_POINTOPOINT:
+            case LSA_LINK_TYPE_VIRTUALLINK:
+              if (type == LSA_LINK_TYPE_VIRTUALLINK)
+		{
+		  if (IS_DEBUG_OSPF_EVENT)
+		    zlog_info ("looking up LSA through VL: %s",
+			       inet_ntoa (l->link_id));
+		}
+
+              w_lsa = ospf_lsa_lookup (area, OSPF_ROUTER_LSA, l->link_id,
+                                       l->link_id);
+              if (w_lsa)
+		{
+		  if (IS_DEBUG_OSPF_EVENT)
+		  zlog_info("found the LSA");
+		}
+              break;
+            case LSA_LINK_TYPE_TRANSIT:
+		  if (IS_DEBUG_OSPF_EVENT)
+
+              zlog_info ("Looking up Network LSA, ID: %s",
+                         inet_ntoa(l->link_id));
+              w_lsa = ospf_lsa_lookup_by_id (area, OSPF_NETWORK_LSA,
+					     l->link_id);
+              if (w_lsa)
+		  if (IS_DEBUG_OSPF_EVENT)
+                zlog_info("found the LSA");
+              break;
+            default:
+	      zlog_warn ("Invalid LSA link type %d", type);
+              continue;
+            }
+        }
+      else
+        {
+          /* In case of V is Network-LSA. */
+          r = (struct in_addr *) p ;
+          p += sizeof (struct in_addr);
+
+          /* Lookup the vertex W's LSA. */
+          w_lsa = ospf_lsa_lookup_by_id (area, OSPF_ROUTER_LSA, *r);
+        }
+
+      /* (b cont.) If the LSA does not exist, or its LS age is equal
+         to MaxAge, or it does not have a link back to vertex V,
+         examine the next link in V's LSA.[23] */
+      if (w_lsa == NULL)
+        continue;
+
+      if (IS_LSA_MAXAGE (w_lsa))
+        continue;
+
+      if (! ospf_lsa_has_link (w_lsa->data, v->lsa))
+        {
+		  if (IS_DEBUG_OSPF_EVENT)
+	  zlog_info ("The LSA doesn't have a link back");
+          continue;
+        }
+
+      /* (c) If vertex W is already on the shortest-path tree, examine
+         the next link in the LSA. */
+      if (ospf_spf_has_vertex (rv, nv, w_lsa->data))
+        {
+		  if (IS_DEBUG_OSPF_EVENT)
+          zlog_info ("The LSA is already in SPF");
+          continue;
+        }
+
+      /* (d) Calculate the link state cost D of the resulting path
+         from the root to vertex W.  D is equal to the sum of the link
+         state cost of the (already calculated) shortest path to
+         vertex V and the advertised cost of the link between vertices
+         V and W.  If D is: */
+
+      /* prepare vertex W. */
+      w = ospf_vertex_new (w_lsa);
+
+      /* calculate link cost D. */
+      if (v->lsa->type == OSPF_ROUTER_LSA)
+        w->distance = v->distance + ntohs (l->m[0].metric);
+      else
+        w->distance = v->distance;
+
+      /* Is there already vertex W in candidate list? */
+      node = ospf_vertex_lookup (candidate, w->id, w->type);
+      if (node == NULL)
+        {
+          /* Calculate nexthop to W. */
+          ospf_nexthop_calculation (area, v, w);
+
+          ospf_install_candidate (candidate, w);
+        }
+      else
+        {
+          cw = (struct vertex *) getdata (node);
+
+          /* if D is greater than. */
+          if (cw->distance < w->distance)
+            {
+              ospf_vertex_free (w);
+              continue;
+            }
+          /* equal to. */
+          else if (cw->distance == w->distance)
+            {
+              /* Calculate nexthop to W. */
+              ospf_nexthop_calculation (area, v, w);
+              ospf_nexthop_merge (cw->nexthop, w->nexthop);
+              list_delete_all_node (w->nexthop);
+              ospf_vertex_free (w);
+            }
+          /* less than. */
+          else
+            {
+              /* Calculate nexthop. */
+              ospf_nexthop_calculation (area, v, w);
+
+              /* Remove old vertex from candidate list. */
+              ospf_vertex_free (cw);
+              listnode_delete (candidate, cw);
+
+              /* Install new to candidate. */
+              ospf_install_candidate (candidate, w);
+            }
+        }
+    }
+}
+
+/* Add vertex V to SPF tree. */
+void
+ospf_spf_register (struct vertex *v, struct route_table *rv,
+		   struct route_table *nv)
+{
+  struct prefix p;
+  struct route_node *rn;
+
+  p.family = AF_INET;
+  p.prefixlen = IPV4_MAX_BITLEN;
+  p.u.prefix4 = v->id;
+
+  if (v->type == OSPF_VERTEX_ROUTER)
+    rn = route_node_get (rv, &p);
+  else
+    rn = route_node_get (nv, &p);
+
+  rn->info = v;
+}
+
+void
+ospf_spf_route_free (struct route_table *table)
+{
+  struct route_node *rn;
+  struct vertex *v;
+
+  for (rn = route_top (table); rn; rn = route_next (rn))
+    {
+      if ((v = rn->info))
+	{
+	  ospf_vertex_free (v);
+	  rn->info = NULL;
+	}
+
+      route_unlock_node (rn);
+    }
+
+  route_table_finish (table);
+}
+
+void
+ospf_spf_dump (struct vertex *v, int i)
+{
+  listnode cnode;
+  listnode nnode;
+  struct vertex_nexthop *nexthop;
+
+  if (v->type == OSPF_VERTEX_ROUTER)
+    {
+      if (IS_DEBUG_OSPF_EVENT)
+	zlog_info ("SPF Result: %d [R] %s", i, inet_ntoa (v->lsa->id));
+    }
+  else
+    {
+      struct network_lsa *lsa = (struct network_lsa *) v->lsa;
+      if (IS_DEBUG_OSPF_EVENT)
+	zlog_info ("SPF Result: %d [N] %s/%d", i, inet_ntoa (v->lsa->id),
+		   ip_masklen (lsa->mask));
+
+      for (nnode = listhead (v->nexthop); nnode; nextnode (nnode))
+        {
+          nexthop = getdata (nnode);
+	  if (IS_DEBUG_OSPF_EVENT)
+	    zlog_info (" nexthop %s", inet_ntoa (nexthop->router));
+        }
+    }
+
+  i++;
+
+  for (cnode = listhead (v->child); cnode; nextnode (cnode))
+    {
+      v = getdata (cnode);
+      ospf_spf_dump (v, i);
+    }
+}
+
+/* Second stage of SPF calculation. */
+void
+ospf_spf_process_stubs (struct ospf_area *area, struct vertex * v,
+                        struct route_table *rt)
+{
+  listnode cnode;
+  struct vertex *child;
+
+  if (IS_DEBUG_OSPF_EVENT)
+    zlog_info ("ospf_process_stub():processing stubs for area %s",
+	       inet_ntoa (area->area_id));
+  if (v->type == OSPF_VERTEX_ROUTER)
+    {
+      u_char *p;
+      u_char *lim;
+      struct router_lsa_link *l;
+      struct router_lsa *rlsa;
+
+  if (IS_DEBUG_OSPF_EVENT)
+      zlog_info ("ospf_process_stub():processing router LSA, id: %s",
+                 inet_ntoa (v->lsa->id));
+      rlsa = (struct router_lsa *) v->lsa;
+
+
+  if (IS_DEBUG_OSPF_EVENT)
+      zlog_info ("ospf_process_stub(): we have %d links to process",
+                 ntohs (rlsa->links));
+      p = ((u_char *) v->lsa) + 24;
+      lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
+
+      while (p < lim)
+        {
+          l = (struct router_lsa_link *) p;
+
+          p += (ROUTER_LSA_MIN_SIZE +
+                (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
+
+          if (l->m[0].type == LSA_LINK_TYPE_STUB)
+            ospf_intra_add_stub (rt, l, v, area);
+        }
+    }
+
+  if (IS_DEBUG_OSPF_EVENT)
+  zlog_info ("children of V:");
+  for (cnode = listhead (v->child); cnode; nextnode (cnode))
+    {
+      child = getdata (cnode);
+  if (IS_DEBUG_OSPF_EVENT)
+      zlog_info (" child : %s", inet_ntoa (child->id));
+    }
+
+  for (cnode = listhead (v->child); cnode; nextnode (cnode))
+    {
+      child = getdata (cnode);
+
+      if (CHECK_FLAG (child->flags, OSPF_VERTEX_PROCESSED))
+	continue;
+
+      ospf_spf_process_stubs (area, child, rt);
+
+      SET_FLAG (child->flags, OSPF_VERTEX_PROCESSED);
+    }
+}
+
+void
+ospf_rtrs_free (struct route_table *rtrs)
+{
+  struct route_node *rn;
+  list or_list;
+  listnode node;
+
+  if (IS_DEBUG_OSPF_EVENT)
+  zlog_info ("Route: Router Routing Table free");
+
+  for (rn = route_top (rtrs); rn; rn = route_next (rn))
+    if ((or_list = rn->info) != NULL)
+      {
+	for (node = listhead (or_list); node; nextnode (node))
+	  ospf_route_free (node->data);
+
+	list_delete (or_list);
+
+	/* Unlock the node. */
+	rn->info = NULL;
+	route_unlock_node (rn);
+      }
+  route_table_finish (rtrs);
+}
+
+void
+ospf_rtrs_print (struct route_table *rtrs)
+{
+  struct route_node *rn;
+  list or_list;
+  listnode ln;
+  listnode pnode;
+  struct ospf_route *or;
+  struct ospf_path *path;
+  char buf1[BUFSIZ];
+  char buf2[BUFSIZ];
+
+  if (IS_DEBUG_OSPF_EVENT)
+    zlog_info ("ospf_rtrs_print() start");
+
+  for (rn = route_top (rtrs); rn; rn = route_next (rn))
+    if ((or_list = rn->info) != NULL)
+      for (ln = listhead (or_list); ln; nextnode (ln))
+        {
+          or = getdata (ln);
+
+          switch (or->path_type)
+            {
+            case OSPF_PATH_INTRA_AREA:
+	      if (IS_DEBUG_OSPF_EVENT)
+		zlog_info ("%s   [%d] area: %s", 
+			   inet_ntop (AF_INET, &or->id, buf1, BUFSIZ), or->cost,
+			   inet_ntop (AF_INET, &or->u.std.area_id,
+				      buf2, BUFSIZ));
+              break;
+            case OSPF_PATH_INTER_AREA:
+	      if (IS_DEBUG_OSPF_EVENT)
+		zlog_info ("%s IA [%d] area: %s", 
+			   inet_ntop (AF_INET, &or->id, buf1, BUFSIZ), or->cost,
+			   inet_ntop (AF_INET, &or->u.std.area_id,
+				      buf2, BUFSIZ));
+              break;
+            default:
+              break;
+            }
+
+          for (pnode = listhead (or->path); pnode; nextnode (pnode))
+            {
+              path = getdata (pnode);
+              if (path->nexthop.s_addr == 0)
+		{
+		  if (IS_DEBUG_OSPF_EVENT)
+		    zlog_info ("   directly attached to %s\r\n",
+			       IF_NAME (path->oi));
+		}
+              else 
+		{
+		  if (IS_DEBUG_OSPF_EVENT)
+		    zlog_info ("   via %s, %s\r\n",
+			       inet_ntoa (path->nexthop), IF_NAME (path->oi));
+		}
+            }
+        }
+
+  zlog_info ("ospf_rtrs_print() end");
+}
+
+/* Calculating the shortest-path tree for an area. */
+void
+ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table, 
+                    struct route_table *new_rtrs)
+{
+  list candidate;
+  listnode node;
+  struct vertex *v;
+  struct route_table *rv;
+  struct route_table *nv;
+
+  if (IS_DEBUG_OSPF_EVENT)
+    {
+      zlog_info ("ospf_spf_calculate: Start");
+      zlog_info ("ospf_spf_calculate: running Dijkstra for area %s", 
+		 inet_ntoa (area->area_id));
+    }
+
+  /* Check router-lsa-self.  If self-router-lsa is not yet allocated,
+     return this area's calculation. */
+  if (! area->router_lsa_self)
+    {
+      if (IS_DEBUG_OSPF_EVENT)
+	zlog_info ("ospf_spf_calculate: "
+		   "Skip area %s's calculation due to empty router_lsa_self",
+		   inet_ntoa (area->area_id));
+      return;
+    }
+
+  /* RFC2328 16.1. (1). */
+  /* Initialize the algorithm's data structures. */ 
+  rv = route_table_init ();
+  nv = route_table_init ();
+
+  /* Clear the list of candidate vertices. */ 
+  candidate = list_new ();
+
+  /* Initialize the shortest-path tree to only the root (which is the
+     router doing the calculation). */
+  ospf_spf_init (area);
+  v = area->spf;
+  ospf_spf_register (v, rv, nv);
+
+  /* Set Area A's TransitCapability to FALSE. */
+  area->transit = OSPF_TRANSIT_FALSE;
+  area->shortcut_capability = 1;
+
+  for (;;)
+    {
+      /* RFC2328 16.1. (2). */
+      ospf_spf_next (v, area, candidate, rv, nv);
+
+      /* RFC2328 16.1. (3). */
+      /* If at this step the candidate list is empty, the shortest-
+         path tree (of transit vertices) has been completely built and
+         this stage of the procedure terminates. */
+      if (listcount (candidate) == 0)
+        break;
+
+      /* Otherwise, choose the vertex belonging to the candidate list
+         that is closest to the root, and add it to the shortest-path
+         tree (removing it from the candidate list in the
+         process). */ 
+      node = listhead (candidate);
+      v = getdata (node);
+      ospf_vertex_add_parent (v);
+
+      /* Reveve from the candidate list. */
+      listnode_delete (candidate, v);
+
+      /* Add to SPF tree. */
+      ospf_spf_register (v, rv, nv);
+
+      /* Note that when there is a choice of vertices closest to the
+         root, network vertices must be chosen before router vertices
+         in order to necessarily find all equal-cost paths. */
+      /* We don't do this at this moment, we should add the treatment
+         above codes. -- kunihiro. */
+
+      /* RFC2328 16.1. (4). */
+      if (v->type == OSPF_VERTEX_ROUTER)
+        ospf_intra_add_router (new_rtrs, v, area);
+      else 
+        ospf_intra_add_transit (new_table, v, area);
+
+      /* RFC2328 16.1. (5). */
+      /* Iterate the algorithm by returning to Step 2. */
+    }
+
+  if (IS_DEBUG_OSPF_EVENT)
+    {
+      ospf_spf_dump (area->spf, 0);
+      ospf_route_table_dump (new_table);
+    }
+
+  /* Second stage of SPF calculation procedure's  */
+  ospf_spf_process_stubs (area, area->spf, new_table);
+
+  /* Free all vertices which allocated for SPF calculation */
+  ospf_spf_route_free (rv);
+  ospf_spf_route_free (nv);
+
+  /* Free candidate list */
+  list_free (candidate);
+
+  /* Increment SPF Calculation Counter. */
+  area->spf_calculation++;
+
+  ospf_top->ts_spf = time (NULL);
+
+  if (IS_DEBUG_OSPF_EVENT)
+    zlog_info ("ospf_spf_calculate: Stop");
+}
+
+/* Timer for SPF calculation. */
+int
+ospf_spf_calculate_timer (struct thread *t)
+{
+  struct route_table *new_table, *new_rtrs;
+  struct ospf *ospf;
+  /* struct ospf_area *area; */
+  listnode node;
+
+  if (IS_DEBUG_OSPF_EVENT)
+    zlog_info ("SPF: Timer (SPF calculation expire)");
+  
+  ospf = THREAD_ARG (t);
+  ospf->t_spf_calc = NULL;
+
+  /* Allocate new table tree. */
+  new_table = route_table_init ();
+  new_rtrs  = route_table_init ();
+
+  ospf_vl_unapprove ();
+
+  /* Calculate SPF for each area. */
+  for (node = listhead (ospf->areas); node; node = nextnode (node))
+    ospf_spf_calculate (node->data, new_table, new_rtrs);
+
+  ospf_vl_shut_unapproved ();
+
+  ospf_ia_routing (new_table, new_rtrs);
+
+  ospf_prune_unreachable_networks (new_table);
+  ospf_prune_unreachable_routers (new_rtrs);
+
+  /* AS-external-LSA calculation should not be performed here. */
+
+  /* If new Router Route is installed,
+     then schedule re-calculate External routes. */
+  if (1)
+    ospf_ase_calculate_schedule ();
+
+  ospf_ase_calculate_timer_add ();
+
+  /* Update routing table. */
+  ospf_route_install (new_table);
+
+  /* Update ABR/ASBR routing table */
+  if (ospf_top->old_rtrs)
+    {
+      /* old_rtrs's node holds linked list of ospf_route. --kunihiro. */
+      /* ospf_route_delete (ospf_top->old_rtrs); */
+      ospf_rtrs_free (ospf_top->old_rtrs);
+    }
+
+  ospf_top->old_rtrs = ospf_top->new_rtrs;
+  ospf_top->new_rtrs = new_rtrs;
+
+  if (OSPF_IS_ABR) 
+    ospf_abr_task (new_table, new_rtrs);
+
+  if (IS_DEBUG_OSPF_EVENT)
+    zlog_info ("SPF: calculation complete");
+
+  return 0;
+}
+
+/* Add schedule for SPF calculation.  To avoid frequenst SPF calc, we
+   set timer for SPF calc. */
+void
+ospf_spf_calculate_schedule ()
+{
+  time_t ht, delay;
+
+  if (IS_DEBUG_OSPF_EVENT)
+    zlog_info ("SPF: calculation timer scheduled");
+
+  /* OSPF instance does not exist. */
+  if (!ospf_top)
+    return;
+
+  /* SPF calculation timer is already scheduled. */
+  if (ospf_top->t_spf_calc)
+    {
+      if (IS_DEBUG_OSPF_EVENT)
+	zlog_info ("SPF: calculation timer is already scheduled: %p",
+		   ospf_top->t_spf_calc);
+      return;
+    }
+
+  ht = time (NULL) - ospf_top->ts_spf;
+
+  /* Get SPF calculation delay time. */
+  if (ht < ospf_top->spf_holdtime)
+    {
+      if (ospf_top->spf_holdtime - ht < ospf_top->spf_delay)
+	delay = ospf_top->spf_delay;
+      else
+	delay = ospf_top->spf_holdtime - ht;
+    }
+  else
+    delay = ospf_top->spf_delay;
+
+  if (IS_DEBUG_OSPF_EVENT)
+    zlog_info ("SPF: calculation timer delay = %ld", delay);
+  ospf_top->t_spf_calc =
+    thread_add_timer (master, ospf_spf_calculate_timer, ospf_top, delay);
+}
+