ospf6d: convert LSDB to use route_node, improve performance

the performance in the presence of a large number of LSAs. I also verified
that the performance improvements stayed in the presence of a large number
of peers (I tested upto 128).

Signed-off-by: Dinesh G Dutt <ddutt at cumulusnetworks.com>
Reviewed-by: Scott Feldman <sfeldma at cumulusnetworks.com>Summary:
Reviewed-by: James Li <jli at cumulusnetworks.com>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

5 files changed, 78 insertions, 111 deletions

diff --git a/ospf6d/ospf6_lsa.c b/ospf6d/ospf6_lsa.c
index db14731f..592aad9b 100644
--- a/ospf6d/ospf6_lsa.c
+++ b/ospf6d/ospf6_lsa.c
@@ -450,8 +450,6 @@ ospf6_lsa_show_internal (struct vty *vty, struct ospf6_lsa *lsa)
   vty_out (vty, "CheckSum: %#06hx Length: %hu%s",
            ntohs (lsa->header->checksum),
            ntohs (lsa->header->length), VNL);
-  vty_out (vty, "    Prev: %p This: %p Next: %p%s",
-           lsa->prev, lsa, lsa->next, VNL);
   vty_out (vty, "Flag: %x %s", lsa->flag, VNL);
   vty_out (vty, "Lock: %d %s", lsa->lock, VNL);
   vty_out (vty, "ReTx Count: %d%s", lsa->retrans_count, VNL);
@@ -586,6 +584,7 @@ ospf6_lsa_copy (struct ospf6_lsa *lsa)
   copy->received = lsa->received;
   copy->installed = lsa->installed;
   copy->lsdb = lsa->lsdb;
+  copy->rn = NULL;
 
   return copy;
 }
diff --git a/ospf6d/ospf6_lsa.h b/ospf6d/ospf6_lsa.h
index f10ee671..998599ba 100644
--- a/ospf6d/ospf6_lsa.h
+++ b/ospf6d/ospf6_lsa.h
@@ -114,8 +114,7 @@ struct ospf6_lsa
 {
   char              name[64];   /* dump string */
 
-  struct ospf6_lsa *prev;
-  struct ospf6_lsa *next;
+  struct route_node *rn;
 
   unsigned char     lock;           /* reference counter */
   unsigned char     flag;           /* special meaning (e.g. floodback) */
diff --git a/ospf6d/ospf6_lsdb.c b/ospf6d/ospf6_lsdb.c
index 0edc7a34..657a5799 100644
--- a/ospf6d/ospf6_lsdb.c
+++ b/ospf6d/ospf6_lsdb.c
@@ -54,9 +54,12 @@ ospf6_lsdb_create (void *data)
 void
 ospf6_lsdb_delete (struct ospf6_lsdb *lsdb)
 {
-  ospf6_lsdb_remove_all (lsdb);
-  route_table_finish (lsdb->table);
-  XFREE (MTYPE_OSPF6_LSDB, lsdb);
+  if (lsdb != NULL)
+    {
+      ospf6_lsdb_remove_all (lsdb);
+      route_table_finish (lsdb->table);
+      XFREE (MTYPE_OSPF6_LSDB, lsdb);
+    }
 }
 
 static void
@@ -102,8 +105,8 @@ void
 ospf6_lsdb_add (struct ospf6_lsa *lsa, struct ospf6_lsdb *lsdb)
 {
   struct prefix_ipv6 key;
-  struct route_node *current, *nextnode, *prevnode;
-  struct ospf6_lsa *next, *prev, *old = NULL;
+  struct route_node *current;
+  struct ospf6_lsa *old = NULL;
 
   memset (&key, 0, sizeof (key));
   ospf6_lsdb_set_key (&key, &lsa->header->type, sizeof (lsa->header->type));
@@ -114,55 +117,25 @@ ospf6_lsdb_add (struct ospf6_lsa *lsa, struct ospf6_lsdb *lsdb)
   current = route_node_get (lsdb->table, (struct prefix *) &key);
   old = current->info;
   current->info = lsa;
+  lsa->rn = current;
   ospf6_lsa_lock (lsa);
 
-  if (old)
-    {
-      if (old->prev)
-        old->prev->next = lsa;
-      if (old->next)
-        old->next->prev = lsa;
-      lsa->next = old->next;
-      lsa->prev = old->prev;
-    }
-  else
+  if (!old)
     {
-      /* next link */
-      nextnode = current;
-      route_lock_node (nextnode);
-      do {
-        nextnode = route_next (nextnode);
-      } while (nextnode && nextnode->info == NULL);
-      if (nextnode == NULL)
-        lsa->next = NULL;
-      else
-        {
-          next = nextnode->info;
-          lsa->next = next;
-          next->prev = lsa;
-          route_unlock_node (nextnode);
-        }
+      lsdb->count++;
 
-      /* prev link */
-      prevnode = current;
-      route_lock_node (prevnode);
-      do {
-        prevnode = route_prev (prevnode);
-      } while (prevnode && prevnode->info == NULL);
-      if (prevnode == NULL)
-        lsa->prev = NULL;
+      if (OSPF6_LSA_IS_MAXAGE (lsa))
+	{
+	  if (lsdb->hook_remove)
+	    (*lsdb->hook_remove) (lsa);
+	}
       else
-        {
-          prev = prevnode->info;
-          lsa->prev = prev;
-          prev->next = lsa;
-          route_unlock_node (prevnode);
-        }
-
-      lsdb->count++;
+	{
+	  if (lsdb->hook_add)
+	    (*lsdb->hook_add) (lsa);
+	}
     }
-
-  if (old)
+  else
     {
       if (OSPF6_LSA_IS_CHANGED (old, lsa))
         {
@@ -187,20 +160,8 @@ ospf6_lsdb_add (struct ospf6_lsa *lsa, struct ospf6_lsdb *lsdb)
                 (*lsdb->hook_add) (lsa);
             }
         }
+      ospf6_lsa_unlock (old);
     }
-  else if (OSPF6_LSA_IS_MAXAGE (lsa))
-    {
-      if (lsdb->hook_remove)
-        (*lsdb->hook_remove) (lsa);
-    }
-  else
-    {
-      if (lsdb->hook_add)
-        (*lsdb->hook_add) (lsa);
-    }
-
-  if (old)
-    ospf6_lsa_unlock (old);
 
   ospf6_lsdb_count_assert (lsdb);
 }
@@ -220,19 +181,15 @@ ospf6_lsdb_remove (struct ospf6_lsa *lsa, struct ospf6_lsdb *lsdb)
   node = route_node_lookup (lsdb->table, (struct prefix *) &key);
   assert (node && node->info == lsa);
 
-  if (lsa->prev)
-    lsa->prev->next = lsa->next;
-  if (lsa->next)
-    lsa->next->prev = lsa->prev;
-
   node->info = NULL;
   lsdb->count--;
 
   if (lsdb->hook_remove)
     (*lsdb->hook_remove) (lsa);
 
+  route_unlock_node (node);	/* to free the lookup lock */
+  route_unlock_node (node);	/* to free the original lock */
   ospf6_lsa_unlock (lsa);
-  route_unlock_node (node);
 
   ospf6_lsdb_count_assert (lsdb);
 }
@@ -255,6 +212,8 @@ ospf6_lsdb_lookup (u_int16_t type, u_int32_t id, u_int32_t adv_router,
   node = route_node_lookup (lsdb->table, (struct prefix *) &key);
   if (node == NULL || node->info == NULL)
     return NULL;
+
+  route_unlock_node (node);
   return (struct ospf6_lsa *) node->info;
 }
 
@@ -306,21 +265,9 @@ ospf6_lsdb_lookup_next (u_int16_t type, u_int32_t id, u_int32_t adv_router,
 
   if (prefix_same (&node->p, p))
     {
-      struct route_node *prev = node;
-      struct ospf6_lsa *lsa_prev;
-      struct ospf6_lsa *lsa_next;
-
       node = route_next (node);
       while (node && node->info == NULL)
         node = route_next (node);
-
-      lsa_prev = prev->info;
-      lsa_next = (node ? node->info : NULL);
-      assert (lsa_prev);
-      assert (lsa_prev->next == lsa_next);
-      if (lsa_next)
-        assert (lsa_next->prev == lsa_prev);
-      zlog_debug ("lsdb_lookup_next: assert OK with previous LSA");
     }
 
   if (! node)
@@ -346,7 +293,6 @@ ospf6_lsdb_head (struct ospf6_lsdb *lsdb)
   if (node == NULL)
     return NULL;
 
-  route_unlock_node (node);
   if (node->info)
     ospf6_lsa_lock ((struct ospf6_lsa *) node->info);
   return (struct ospf6_lsa *) node->info;
@@ -355,12 +301,20 @@ ospf6_lsdb_head (struct ospf6_lsdb *lsdb)
 struct ospf6_lsa *
 ospf6_lsdb_next (struct ospf6_lsa *lsa)
 {
-  struct ospf6_lsa *next = lsa->next;
+  struct route_node *node = lsa->rn;
+  struct ospf6_lsa *next = NULL;
 
-  ospf6_lsa_unlock (lsa);
-  if (next)
-    ospf6_lsa_lock (next);
+  do {
+    node = route_next (node);
+  } while (node && node->info == NULL);
+
+  if ((node != NULL) && (node->info != NULL))
+    {
+      next = node->info;
+      ospf6_lsa_lock (next);
+    }
 
+  ospf6_lsa_unlock (lsa);
   return next;
 }
 
@@ -390,8 +344,6 @@ ospf6_lsdb_type_router_head (u_int16_t type, u_int32_t adv_router,
 
   if (node == NULL)
     return NULL;
-  else
-    route_unlock_node (node);
 
   if (! prefix_match ((struct prefix *) &key, &node->p))
     return NULL;
@@ -406,18 +358,19 @@ struct ospf6_lsa *
 ospf6_lsdb_type_router_next (u_int16_t type, u_int32_t adv_router,
                              struct ospf6_lsa *lsa)
 {
-  struct ospf6_lsa *next = lsa->next;
+  struct ospf6_lsa *next = ospf6_lsdb_next(lsa);
 
   if (next)
     {
       if (next->header->type != type ||
           next->header->adv_router != adv_router)
-        next = NULL;
+	{
+	  route_unlock_node (next->rn);
+	  ospf6_lsa_unlock (next);
+	  next = NULL;
+	}
     }
 
-  if (next)
-    ospf6_lsa_lock (next);
-  ospf6_lsa_unlock (lsa);
   return next;
 }
 
@@ -444,8 +397,6 @@ ospf6_lsdb_type_head (u_int16_t type, struct ospf6_lsdb *lsdb)
 
   if (node == NULL)
     return NULL;
-  else
-    route_unlock_node (node);
 
   if (! prefix_match ((struct prefix *) &key, &node->p))
     return NULL;
@@ -459,17 +410,18 @@ ospf6_lsdb_type_head (u_int16_t type, struct ospf6_lsdb *lsdb)
 struct ospf6_lsa *
 ospf6_lsdb_type_next (u_int16_t type, struct ospf6_lsa *lsa)
 {
-  struct ospf6_lsa *next = lsa->next;
+  struct ospf6_lsa *next = ospf6_lsdb_next (lsa);
 
   if (next)
     {
       if (next->header->type != type)
-        next = NULL;
+	{
+	  route_unlock_node (next->rn);
+	  ospf6_lsa_unlock (next);
+	  next = NULL;
+	}
     }
 
-  if (next)
-    ospf6_lsa_lock (next);
-  ospf6_lsa_unlock (lsa);
   return next;
 }
 
@@ -477,10 +429,25 @@ void
 ospf6_lsdb_remove_all (struct ospf6_lsdb *lsdb)
 {
   struct ospf6_lsa *lsa;
+
+  if (lsdb == NULL)
+    return;
+
   for (lsa = ospf6_lsdb_head (lsdb); lsa; lsa = ospf6_lsdb_next (lsa))
     ospf6_lsdb_remove (lsa, lsdb);
 }
 
+void
+ospf6_lsdb_lsa_unlock (struct ospf6_lsa *lsa)
+{
+  if (lsa != NULL)
+    {
+      if (lsa->rn != NULL)
+	route_unlock_node (lsa->rn);
+      ospf6_lsa_unlock (lsa);
+    }
+}
+
 int
 ospf6_lsdb_maxage_remover (struct ospf6_lsdb *lsdb)
 {
@@ -574,7 +541,7 @@ ospf6_new_ls_id (u_int16_t type, u_int32_t adv_router,
         continue;
       if (ntohl (lsa->header->id) > id)
       {
-        ospf6_lsa_unlock (lsa);
+	ospf6_lsdb_lsa_unlock (lsa);
         break;
       }
       id++;
diff --git a/ospf6d/ospf6_lsdb.h b/ospf6d/ospf6_lsdb.h
index 2974ffb1..a124adbf 100644
--- a/ospf6d/ospf6_lsdb.h
+++ b/ospf6d/ospf6_lsdb.h
@@ -64,6 +64,7 @@ extern struct ospf6_lsa *ospf6_lsdb_type_next (u_int16_t type,
                                                struct ospf6_lsa *lsa);
 
 extern void ospf6_lsdb_remove_all (struct ospf6_lsdb *lsdb);
+extern void ospf6_lsdb_lsa_unlock (struct ospf6_lsa *lsa);
 
 #define OSPF6_LSDB_SHOW_LEVEL_NORMAL   0
 #define OSPF6_LSDB_SHOW_LEVEL_DETAIL   1
@@ -79,5 +80,6 @@ extern u_int32_t ospf6_new_ls_id (u_int16_t type, u_int32_t adv_router,
 extern u_int32_t ospf6_new_ls_seqnum (u_int16_t type, u_int32_t id,
                                       u_int32_t adv_router,
                                       struct ospf6_lsdb *lsdb);
+extern int ospf6_lsdb_maxage_remover (struct ospf6_lsdb *lsdb);
 
 #endif /* OSPF6_LSDB_H */
diff --git a/ospf6d/ospf6_message.c b/ospf6d/ospf6_message.c
index dcbb36bf..82d2d340 100644
--- a/ospf6d/ospf6_message.c
+++ b/ospf6d/ospf6_message.c
@@ -1825,7 +1825,7 @@ ospf6_dbdesc_send (struct thread *thread)
           if (p - sendbuf + sizeof (struct ospf6_lsa_header) >
               ospf6_packet_max(on->ospf6_if))
             {
-              ospf6_lsa_unlock (lsa);
+              ospf6_lsdb_lsa_unlock (lsa);
               break;
             }
           memcpy (p, lsa->header, sizeof (struct ospf6_lsa_header));
@@ -1865,7 +1865,7 @@ ospf6_dbdesc_send_newone (struct thread *thread)
     {
       if (size + sizeof (struct ospf6_lsa_header) > ospf6_packet_max(on->ospf6_if))
         {
-          ospf6_lsa_unlock (lsa);
+          ospf6_lsdb_lsa_unlock (lsa);
           break;
         }
 
@@ -1928,7 +1928,7 @@ ospf6_lsreq_send (struct thread *thread)
       /* MTU check */
       if (p - sendbuf + sizeof (struct ospf6_lsreq_entry) > ospf6_packet_max(on->ospf6_if))
         {
-          ospf6_lsa_unlock (lsa);
+          ospf6_lsdb_lsa_unlock (lsa);
           break;
         }
 
@@ -2012,7 +2012,7 @@ ospf6_lsupdate_send_neighbor (struct thread *thread)
       if ( (p - sendbuf + (unsigned int)OSPF6_LSA_SIZE (lsa->header))
 	   > ospf6_packet_max(on->ospf6_if))
 	{
-	  ospf6_lsa_unlock (lsa);
+	  ospf6_lsdb_lsa_unlock (lsa);
 	  break;
 	}
 
@@ -2058,7 +2058,7 @@ ospf6_lsupdate_send_neighbor (struct thread *thread)
       if ( (p - sendbuf + (unsigned int)OSPF6_LSA_SIZE (lsa->header))
 	   > ospf6_packet_max(on->ospf6_if))
 	{
-	  ospf6_lsa_unlock (lsa);
+	  ospf6_lsdb_lsa_unlock (lsa);
 	  break;
 	}
 
@@ -2132,7 +2132,7 @@ ospf6_lsupdate_send_interface (struct thread *thread)
       if ( (p - sendbuf + ((unsigned int)OSPF6_LSA_SIZE (lsa->header)))
 	   > ospf6_packet_max(oi))
 	{
-	  ospf6_lsa_unlock (lsa);
+	  ospf6_lsdb_lsa_unlock (lsa);
 	  break;
 	}
 
@@ -2211,7 +2211,7 @@ ospf6_lsack_send_neighbor (struct thread *thread)
 	  on->thread_send_lsack =
 	    thread_add_event (master, ospf6_lsack_send_neighbor, on, 0);
 
-	  ospf6_lsa_unlock (lsa);
+	  ospf6_lsdb_lsa_unlock (lsa);
 	  break;
 	}
 
@@ -2283,7 +2283,7 @@ ospf6_lsack_send_interface (struct thread *thread)
 	  oi->thread_send_lsack =
 	    thread_add_event (master, ospf6_lsack_send_interface, oi, 0);
 
-	  ospf6_lsa_unlock (lsa);
+	  ospf6_lsdb_lsa_unlock (lsa);
 	  break;
 	}