From 3106a03215f5f09c2c0d427fa706fff52ef3cb37 Mon Sep 17 00:00:00 2001 From: Stephen Hemminger Date: Thu, 6 Aug 2009 12:58:05 -0700 Subject: ospfd: fix performance problem with redistribute delete Doing redistribute delete with full BGP table was taking 30 minutes, this drops it down to less than a second. * ospf_lsa.c: (ospf_lsa_maxage) When flushing lots of entries the performance is terrible because it looks up each LSA entry through ospf_lsa_maxage_exist before deleting causing O(N^2) performance. Use a new OSPF_LSA_MAXAGE flag instead of scan - and maintain it. (ospf_lsa_maxage_exist) removed (ospf_lsa_maxage_delete) maintain OSPF_LSA_MAXAGE flag --- ospfd/ospf_lsa.c | 17 +++-------------- ospfd/ospf_lsa.h | 1 + 2 files changed, 4 insertions(+), 14 deletions(-) (limited to 'ospfd') diff --git a/ospfd/ospf_lsa.c b/ospfd/ospf_lsa.c index 9e80664b..e708d5e2 100644 --- a/ospfd/ospf_lsa.c +++ b/ospfd/ospf_lsa.c @@ -2958,19 +2958,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) { @@ -2979,6 +2966,7 @@ ospf_lsa_maxage_delete (struct ospf *ospf, struct ospf_lsa *lsa) if ((n = listnode_lookup (ospf->maxage_lsa, lsa))) { list_delete_node (ospf->maxage_lsa, n); + UNSET_FLAG(lsa->flags, OSPF_LSA_IN_MAXAGE); ospf_lsa_unlock (&lsa); /* maxage_lsa */ } } @@ -2988,7 +2976,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_IN_MAXAGE)) { if (IS_DEBUG_OSPF (lsa, LSA_FLOODING)) zlog_debug ("LSA[Type%d:%s]: %p already exists on MaxAge LSA list", @@ -2997,6 +2985,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_IN_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..251d4731 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_IN_MAXAGE 0x80 /* LSA data. */ struct lsa_header *data; -- cgit v1.2.1