ospf: fix performance of ospf_lsa_maxage

When flushing lots of entries the performance of ospf_lsa_maxage
is terrible because it looks up entry before deleting (N^2).
Use a flag to mark whether entry is already in maxage list.

Bug 4421

2 files changed, 10 insertions, 23 deletions

diff --git a/ospfd/ospf_lsa.c b/ospfd/ospf_lsa.c
index aaf1f484..62a4fb45 100644
--- a/ospfd/ospf_lsa.c
+++ b/ospfd/ospf_lsa.c
@@ -261,14 +261,6 @@ ospf_lsa_free (struct ospf_lsa *lsa)
   XFREE (MTYPE_OSPF_LSA, lsa);
 }
 
-/* Lock LSA. */
-struct ospf_lsa *
-ospf_lsa_lock (struct ospf_lsa *lsa)
-{
-  lsa->lock++;
-  return lsa;
-}
-
 /* Unlock LSA. */
 void
 ospf_lsa_unlock (struct ospf_lsa **lsa)
@@ -3002,19 +2994,6 @@ ospf_maxage_lsa_remover (struct thread *thread)
   return 0;
 }
 
-static int
-ospf_lsa_maxage_exist (struct ospf *ospf, struct ospf_lsa *new)
-{
-  struct listnode *node;
-  struct ospf_lsa *lsa;
-  
-  for (ALL_LIST_ELEMENTS_RO (ospf->maxage_lsa, node, lsa))
-    if (lsa == new)
-      return 1;
-
-  return 0;
-}
-
 void
 ospf_lsa_maxage_delete (struct ospf *ospf, struct ospf_lsa *lsa)
 {
@@ -3032,7 +3011,7 @@ ospf_lsa_maxage (struct ospf *ospf, struct ospf_lsa *lsa)
 {
   /* When we saw a MaxAge LSA flooded to us, we put it on the list
      and schedule the MaxAge LSA remover. */
-  if (ospf_lsa_maxage_exist (ospf, lsa))
+  if (CHECK_FLAG(lsa->flags, OSPF_LSA_MAXAGE))
     {
       if (IS_DEBUG_OSPF (lsa, LSA_FLOODING))
 	zlog_debug ("LSA[Type%d:%s]: %p already exists on MaxAge LSA list",
@@ -3041,6 +3020,7 @@ ospf_lsa_maxage (struct ospf *ospf, struct ospf_lsa *lsa)
     }
 
   listnode_add (ospf->maxage_lsa, ospf_lsa_lock (lsa));
+  SET_FLAG(lsa->flags, OSPF_LSA_MAXAGE);
 
   if (IS_DEBUG_OSPF (lsa, LSA_FLOODING))
     zlog_debug ("LSA[%s]: MaxAge LSA remover scheduled.", dump_lsa_key (lsa));
diff --git a/ospfd/ospf_lsa.h b/ospfd/ospf_lsa.h
index 8dd054c3..bca4c9ef 100644
--- a/ospfd/ospf_lsa.h
+++ b/ospfd/ospf_lsa.h
@@ -80,6 +80,7 @@ struct ospf_lsa
 #define OSPF_LSA_DISCARD	  0x10
 #define OSPF_LSA_LOCAL_XLT	  0x20
 #define OSPF_LSA_PREMATURE_AGE	  0x40
+#define OSPF_LSA_MAXAGE           0x80
 
   /* LSA data. */
   struct lsa_header *data;
@@ -244,7 +245,13 @@ extern struct ospf_neighbor *ospf_nbr_lookup_ptop (struct ospf_interface *);
 extern struct ospf_lsa *ospf_lsa_new (void);
 extern struct ospf_lsa *ospf_lsa_dup (struct ospf_lsa *);
 extern void ospf_lsa_free (struct ospf_lsa *);
-extern struct ospf_lsa *ospf_lsa_lock (struct ospf_lsa *);
+
+static inline struct ospf_lsa *ospf_lsa_lock (struct ospf_lsa *lsa)
+{
+  lsa->lock++;
+  return lsa;
+}
+
 extern void ospf_lsa_unlock (struct ospf_lsa **);
 extern void ospf_lsa_discard (struct ospf_lsa *);