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>
diff --git a/ospf6d/ospf6_lsdb.c b/ospf6d/ospf6_lsdb.c
index 0edc7a3..657a579 100644
--- a/ospf6d/ospf6_lsdb.c
+++ b/ospf6d/ospf6_lsdb.c
@@ -54,9 +54,12 @@
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 @@
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,56 +117,26 @@
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)
{
- if (old->prev)
- old->prev->next = lsa;
- if (old->next)
- old->next->prev = lsa;
- lsa->next = old->next;
- lsa->prev = old->prev;
+ lsdb->count++;
+
+ if (OSPF6_LSA_IS_MAXAGE (lsa))
+ {
+ if (lsdb->hook_remove)
+ (*lsdb->hook_remove) (lsa);
+ }
+ else
+ {
+ if (lsdb->hook_add)
+ (*lsdb->hook_add) (lsa);
+ }
}
else
{
- /* 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);
- }
-
- /* prev link */
- prevnode = current;
- route_lock_node (prevnode);
- do {
- prevnode = route_prev (prevnode);
- } while (prevnode && prevnode->info == NULL);
- if (prevnode == NULL)
- lsa->prev = NULL;
- else
- {
- prev = prevnode->info;
- lsa->prev = prev;
- prev->next = lsa;
- route_unlock_node (prevnode);
- }
-
- lsdb->count++;
- }
-
- if (old)
- {
if (OSPF6_LSA_IS_CHANGED (old, lsa))
{
if (OSPF6_LSA_IS_MAXAGE (lsa))
@@ -187,20 +160,8 @@
(*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 @@
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 @@
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 @@
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 @@
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 @@
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;
+
+ 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);
- if (next)
- ospf6_lsa_lock (next);
-
return next;
}
@@ -390,8 +344,6 @@
if (node == NULL)
return NULL;
- else
- route_unlock_node (node);
if (! prefix_match ((struct prefix *) &key, &node->p))
return NULL;
@@ -406,18 +358,19 @@
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 @@
if (node == NULL)
return NULL;
- else
- route_unlock_node (node);
if (! prefix_match ((struct prefix *) &key, &node->p))
return NULL;
@@ -459,17 +410,18 @@
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 @@
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 @@
continue;
if (ntohl (lsa->header->id) > id)
{
- ospf6_lsa_unlock (lsa);
+ ospf6_lsdb_lsa_unlock (lsa);
break;
}
id++;