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_lsa.c b/ospf6d/ospf6_lsa.c
index db14731..592aad9 100644
--- a/ospf6d/ospf6_lsa.c
+++ b/ospf6d/ospf6_lsa.c
@@ -450,8 +450,6 @@
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 @@
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 f10ee67..998599b 100644
--- a/ospf6d/ospf6_lsa.h
+++ b/ospf6d/ospf6_lsa.h
@@ -114,8 +114,7 @@
{
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 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++;
diff --git a/ospf6d/ospf6_lsdb.h b/ospf6d/ospf6_lsdb.h
index 2974ffb..a124adb 100644
--- a/ospf6d/ospf6_lsdb.h
+++ b/ospf6d/ospf6_lsdb.h
@@ -64,6 +64,7 @@
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_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 dcbb36b..82d2d34 100644
--- a/ospf6d/ospf6_message.c
+++ b/ospf6d/ospf6_message.c
@@ -1825,7 +1825,7 @@
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 @@
{
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 @@
/* 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 @@
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 @@
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 @@
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 @@
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 @@
oi->thread_send_lsack =
thread_add_event (master, ospf6_lsack_send_interface, oi, 0);
- ospf6_lsa_unlock (lsa);
+ ospf6_lsdb_lsa_unlock (lsa);
break;
}