* isis_spf.c: Changing cost from uint16_t to uint32_t. Unset

	  ISIS_ROUTE_FLAG_ACTIVE flag before running SPF.
	* isisd.[ch]: Separate route tables for different levels. SPF is done
	  separately, but in case of L1L2 area they have to be merged.
	* isis_zebra.c: Set/unset ISIS_ROUTE_FLAG_ZEBRA_SYNC flag correctly in
	  case of adding/removing IPv4 routes.
	* zebra_route.c: Rework route validating process. Merging L1 and L2
	  tables in case of L1L2 area.

        In short - many changes to make SPF work more correctly, add/remove
        to/from RIB also works now. It's still very far from perfect though.

7 files changed, 185 insertions, 44 deletions

diff --git a/isisd/ChangeLog b/isisd/ChangeLog
index 7f3cd9da..8687ee75 100644
--- a/isisd/ChangeLog
+++ b/isisd/ChangeLog
@@ -1,5 +1,16 @@
 2005-09-26 Hasso Tepper <hasso at quagga.net>
 
+	* isis_spf.c: Changing cost from uint16_t to uint32_t. Unset
+	  ISIS_ROUTE_FLAG_ACTIVE flag before running SPF.
+	* isisd.[ch]: Separate route tables for different levels. SPF is done
+	  separately, but in case of L1L2 area they have to be merged.
+	* isis_zebra.c: Set/unset ISIS_ROUTE_FLAG_ZEBRA_SYNC flag correctly in
+	  case of adding/removing IPv4 routes.
+	* zebra_route.c: Rework route validating process. Merging L1 and L2
+	  tables in case of L1L2 area.
+
+2005-09-26 Hasso Tepper <hasso at quagga.net>
+
 	* isis_spf.[ch]: Added TE TLVs to the SPF process. It seems to work
 	  mostly, but needs certainly much more testing, especially transition
 	  situation.
diff --git a/isisd/isis_route.c b/isisd/isis_route.c
index 7cee89ee..e4513125 100644
--- a/isisd/isis_route.c
+++ b/isisd/isis_route.c
@@ -451,7 +451,8 @@ isis_route_info_prefer_new (struct isis_route_info *new,
 
 struct isis_route_info *
 isis_route_create (struct prefix *prefix, u_int32_t cost, u_int32_t depth,
-		   struct list *adjacencies, struct isis_area *area)
+		   struct list *adjacencies, struct isis_area *area,
+		   int level)
 {
   struct route_node *route_node;
   struct isis_route_info *rinfo_new, *rinfo_old, *route_info = NULL;
@@ -471,10 +472,10 @@ isis_route_create (struct prefix *prefix, u_int32_t cost, u_int32_t depth,
     }
 
   if (family == AF_INET)
-    route_node = route_node_get (area->route_table, prefix);
+    route_node = route_node_get (area->route_table[level - 1], prefix);
 #ifdef HAVE_IPV6
   else if (family == AF_INET6)
-    route_node = route_node_get (area->route_table6, prefix);
+    route_node = route_node_get (area->route_table6[level - 1], prefix);
 #endif /* HAVE_IPV6 */
   else
     return NULL;
@@ -585,31 +586,23 @@ isis_route_delete (struct prefix *prefix, struct route_table *table)
   return;
 }
 
-int
-isis_route_validate (struct thread *thread)
+/* Validating routes in particular table. */
+static void
+isis_route_validate_table (struct isis_area *area, struct route_table *table)
 {
-  struct isis_area *area;
-  struct route_table *table;
-  struct route_node *rode;
+  struct route_node *rnode, *drnode;
   struct isis_route_info *rinfo;
   u_char buff[BUFSIZ];
-#ifdef HAVE_IPV6
-  int v6done = 0;
-#endif
-  area = THREAD_ARG (thread);
-  table = area->route_table;
-#ifdef HAVE_IPV6
-again:
-#endif
-  for (rode = route_top (table); rode; rode = route_next (rode))
+
+  for (rnode = route_top (table); rnode; rnode = route_next (rnode))
     {
-      if (rode->info == NULL)
+      if (rnode->info == NULL)
 	continue;
-      rinfo = rode->info;
+      rinfo = rnode->info;
 
       if (isis->debugs & DEBUG_RTE_EVENTS)
 	{
-	  prefix2str (&rode->p, (char *) buff, BUFSIZ);
+	  prefix2str (&rnode->p, (char *) buff, BUFSIZ);
 	  zlog_debug ("ISIS-Rte (%s): route validate: %s %s %s",
 		      area->area_tag,
 		      (CHECK_FLAG (rinfo->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNC) ?
@@ -618,16 +611,131 @@ again:
 		      "active" : "inactive"), buff);
 	}
 
-      isis_zebra_route_update (&rode->p, rinfo);
+      isis_zebra_route_update (&rnode->p, rinfo);
       if (!CHECK_FLAG (rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE))
-	isis_route_delete (&rode->p, area->route_table);
+	{
+	  /* Area is either L1 or L2 => we use level route tables directly for
+	   * validating => no problems with deleting routes. */
+	  if (area->is_type != IS_LEVEL_1_AND_2)
+	    {
+	      isis_route_delete (&rnode->p, table);
+	      continue;
+	    }
+	  /* If area is L1L2, we work with merge table and therefore must
+	   * delete node from level tables as well before deleting route info.
+	   * FIXME: Is it performance problem? There has to be the better way.
+	   * Like not to deal with it here at all (see the next comment)? */
+	  if (rnode->p.family == AF_INET)
+	    {
+	      drnode = route_node_get (area->route_table[0], &rnode->p);
+	      if (drnode->info == rnode->info)
+		drnode->info = NULL;
+	      drnode = route_node_get (area->route_table[1], &rnode->p);
+	      if (drnode->info == rnode->info)
+		drnode->info = NULL;
+	    }
+	  if (rnode->p.family == AF_INET6)
+	    {
+	      drnode = route_node_get (area->route_table6[0], &rnode->p);
+	      if (drnode->info == rnode->info)
+		drnode->info = NULL;
+	      drnode = route_node_get (area->route_table6[1], &rnode->p);
+	      if (drnode->info == rnode->info)
+		drnode->info = NULL;
+	    }
+	      
+	  isis_route_delete (&rnode->p, table);
+	}
+    }
+}
+
+/* Function to validate route tables for L1L2 areas. In this case we can't use
+ * level route tables directly, we have to merge them at first. L1 routes are
+ * preferred over the L2 ones.
+ *
+ * Merge algorithm is trivial (at least for now). All L1 paths are copied into
+ * merge table at first, then L2 paths are added if L1 path for same prefix
+ * doesn't already exists there.
+ *
+ * FIXME: Is it right place to do it at all? Maybe we should push both levels
+ * to the RIB with different zebra route types and let RIB handle this? */
+static void
+isis_route_validate_merge (struct isis_area *area, int family)
+{
+  struct route_table *table = NULL;
+  struct route_table *merge;
+  struct route_node *rnode, *mrnode;
+
+  merge = route_table_init ();
+
+  if (family == AF_INET)
+    table = area->route_table[0];
+  else if (family == AF_INET6)
+    table = area->route_table6[0];
+
+  for (rnode = route_top (table); rnode; rnode = route_next (rnode))
+    {
+      if (rnode->info == NULL)
+        continue;
+      mrnode = route_node_get (merge, &rnode->p);
+      mrnode->info = rnode->info;
     }
+
+  if (family == AF_INET)
+    table = area->route_table[1];
+  else if (family == AF_INET6)
+    table = area->route_table6[1];
+
+  for (rnode = route_top (table); rnode; rnode = route_next (rnode))
+    {
+      if (rnode->info == NULL)
+        continue;
+      mrnode = route_node_get (merge, &rnode->p);
+      if (mrnode->info != NULL)
+        continue;
+      mrnode->info = rnode->info;
+    }
+
+  isis_route_validate_table (area, merge);
+  route_table_finish (merge);
+}
+
+/* Walk through route tables and propagate necessary changes into RIB. In case
+ * of L1L2 area, level tables have to be merged at first. */
+int
+isis_route_validate (struct thread *thread)
+{
+  struct isis_area *area;
+
+  area = THREAD_ARG (thread);
+
+  if (area->is_type == IS_LEVEL_1)
+    { 
+      isis_route_validate_table (area, area->route_table[0]);
+      goto validate_ipv6;
+    }
+  if (area->is_type == IS_LEVEL_2)
+    {
+      isis_route_validate_table (area, area->route_table[1]);
+      goto validate_ipv6;
+    }
+
+  isis_route_validate_merge (area, AF_INET);
+
 #ifdef HAVE_IPV6
-  if (v6done)
-    return ISIS_OK;
-  table = area->route_table6;
-  v6done = 1;
-  goto again;
+validate_ipv6:
+  if (area->is_type == IS_LEVEL_1)
+    {
+      isis_route_validate_table (area, area->route_table6[0]);
+      return ISIS_OK;
+    }
+  if (area->is_type == IS_LEVEL_2)
+    {
+      isis_route_validate_table (area, area->route_table6[1]);
+      return ISIS_OK;
+    }
+
+  isis_route_validate_merge (area, AF_INET6);
 #endif
 
   return ISIS_OK;
diff --git a/isisd/isis_route.h b/isisd/isis_route.h
index 59b6c226..4eac79b8 100644
--- a/isisd/isis_route.h
+++ b/isisd/isis_route.h
@@ -57,7 +57,7 @@ struct isis_route_info
 struct isis_route_info *isis_route_create (struct prefix *prefix,
 					   u_int32_t cost, u_int32_t depth,
 					   struct list *adjacencies,
-					   struct isis_area *area);
+					   struct isis_area *area, int level);
 
 int isis_route_validate (struct thread *thread);
 
diff --git a/isisd/isis_spf.c b/isisd/isis_spf.c
index ac4c71f3..4cbc2cd1 100644
--- a/isisd/isis_spf.c
+++ b/isisd/isis_spf.c
@@ -394,7 +394,7 @@ 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_int16_t cost,
+		   void *id, struct isis_adjacency *adj, u_int32_t cost,
 		   int depth, int family)
 {
   struct isis_vertex *vertex, *v;
@@ -457,7 +457,7 @@ isis_spf_add2tent (struct isis_spftree *spftree, enum vertextype vtype,
 
 static struct isis_vertex *
 isis_spf_add_local (struct isis_spftree *spftree, enum vertextype vtype,
-		    void *id, struct isis_adjacency *adj, u_int16_t cost,
+		    void *id, struct isis_adjacency *adj, u_int32_t cost,
 		    int family)
 {
   struct isis_vertex *vertex;
@@ -553,7 +553,7 @@ 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,
-		      uint16_t cost, uint16_t depth, int family)
+		      uint32_t cost, uint16_t depth, int family)
 {
   struct listnode *node, *fragnode = NULL;
   u_int16_t dist;
@@ -945,7 +945,7 @@ 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)
+	      struct isis_area *area, int level)
 {
 #ifdef EXTREME_DEBUG
   u_char buff[BUFSIZ];
@@ -960,8 +960,8 @@ add_to_paths (struct isis_spftree *spftree, struct isis_vertex *vertex,
   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);
+	isis_route_create ((struct prefix *) &vertex->N.prefix, vertex->d_N,
+			   vertex->depth, vertex->Adj_N, area, level);
       else if (isis->debugs & DEBUG_SPF_EVENTS)
 	zlog_debug ("ISIS-Spf: no adjacencies do not install route");
     }
@@ -989,6 +989,9 @@ isis_run_spf (struct isis_area *area, int level, int family)
   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];
@@ -999,6 +1002,21 @@ isis_run_spf (struct isis_area *area, int level, int family)
 
   assert (spftree);
 
+  /* Make all routes in current route table inactive. */
+  if (family == AF_INET)
+    table = area->route_table[level - 1];
+  else if (family == AF_INET6)
+    table = area->route_table6[level - 1];
+
+  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);
+    }
+
   /*
    * C.2.5 Step 0
    */
@@ -1026,7 +1044,7 @@ isis_run_spf (struct isis_area *area, int level, int family)
       list_delete_node (spftree->tents, node);
       if (isis_find_vertex (spftree->paths, vertex->N.id, vertex->type))
 	continue;
-      add_to_paths (spftree, vertex, area);
+      add_to_paths (spftree, vertex, area, level);
       if (vertex->type == VTYPE_PSEUDO_IS ||
 	  vertex->type == VTYPE_NONPSEUDO_IS)
 	{
@@ -1225,7 +1243,7 @@ isis_run_spf6_l2 (struct thread *thread)
     }
 
   if (isis->debugs & DEBUG_SPF_EVENTS)
-    zlog_debug ("ISIS-Spf (%s) L2 SPF needed, periodic SPF", area->area_tag);
+    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);
diff --git a/isisd/isis_zebra.c b/isisd/isis_zebra.c
index a385e6b5..aff6a716 100644
--- a/isisd/isis_zebra.c
+++ b/isisd/isis_zebra.c
@@ -308,6 +308,7 @@ isis_zebra_route_add_ipv4 (struct prefix *prefix,
 
       stream_putw_at (stream, 0, stream_get_endp (stream));
       zclient_send_message(zclient);
+      SET_FLAG (route_info->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNC);
     }
 }
 
@@ -328,6 +329,7 @@ isis_zebra_route_del_ipv4 (struct prefix *prefix,
       prefix4.prefix = prefix->u.prefix4;
       zapi_ipv4_route (ZEBRA_IPV4_ROUTE_DELETE, zclient, &prefix4, &api);
     }
+  UNSET_FLAG (route_info->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNC);
 
   return;
 }
diff --git a/isisd/isisd.c b/isisd/isisd.c
index 2a60b889..dbaae8a8 100644
--- a/isisd/isisd.c
+++ b/isisd/isisd.c
@@ -106,9 +106,11 @@ isis_area_create ()
   area->lspdb[1] = lsp_db_init ();
 
   spftree_area_init (area);
-  area->route_table = route_table_init ();
+  area->route_table[0] = route_table_init ();
+  area->route_table[1] = route_table_init ();
 #ifdef HAVE_IPV6
-  area->route_table6 = route_table_init ();
+  area->route_table6[0] = route_table_init ();
+  area->route_table6[1] = route_table_init ();
 #endif /* HAVE_IPV6 */
   area->circuit_list = list_new ();
   area->area_addrs = list_new ();
diff --git a/isisd/isisd.h b/isisd/isisd.h
index e61376e5..4e716405 100644
--- a/isisd/isisd.h
+++ b/isisd/isisd.h
@@ -79,13 +79,13 @@ struct isis
 
 struct isis_area
 {
-  struct isis *isis;		/* back pointer */
-  dict_t *lspdb[ISIS_LEVELS];	/* link-state dbs */
-  struct isis_spftree *spftree[ISIS_LEVELS];	/* The v4 SPTs */
-  struct route_table *route_table;	/* IPv4 routes */
+  struct isis *isis;				  /* back pointer */
+  dict_t *lspdb[ISIS_LEVELS];			  /* link-state dbs */
+  struct isis_spftree *spftree[ISIS_LEVELS];	  /* The v4 SPTs */
+  struct route_table *route_table[ISIS_LEVELS];	  /* IPv4 routes */
 #ifdef HAVE_IPV6
-  struct isis_spftree *spftree6[ISIS_LEVELS];	/* The v4 SPTs */
-  struct route_table *route_table6;	/* IPv6 routes */
+  struct isis_spftree *spftree6[ISIS_LEVELS];	  /* The v6 SPTs */
+  struct route_table *route_table6[ISIS_LEVELS];  /* IPv6 routes */
 #endif
   unsigned int min_bcast_mtu;
   struct list *circuit_list;	/* IS-IS circuits */