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>

1 files changed, 66 insertions, 99 deletions

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++;