shemminger at vyatta
Jun 26, 2012, 10:59 AM
Post #14 of 19
(1175 views)
Permalink
|
On Tue, 26 Jun 2012 14:47:52 -0300
Renato Westphal <renatowestphal [at] gmail> wrote:
> 2012/6/26 David Lamparter <equinox [at] opensourcerouting>:
> > On Tue, Jun 26, 2012 at 08:06:12AM -0700, Stephen Hemminger wrote:
> >> On Tue, 26 Jun 2012 11:01:18 -0300
> >> Renato Westphal <renatowestphal [at] gmail> wrote:
> >>
> >> > 2012/6/25 Vincent Bernat <bernat [at] luffy>:
> >> > > The upgrade is already done. The specific code to each daemon is
> >> > > compatible (and already was) with both SMUX and AgentX (except the trap
> >> > > part but I have already upgraded it). This is also why SMUX/AgentX is a
> >> > > compile time option.
> >> >
> >> > Thanks for the clarification. Everything makes sense for me now.
> >> >
> >> > Just one note. I have to run Quagga (any daemon) with root privileges
> >> > in order to use agentx. Otherwise I get an "snmp[warning]: Warning:
> >> > Failed to connect to the agentx master agent ([NIL]):".
> >> >
> >> > > AgentX won't improve the situation from the performance point of view.
> >> > >
> >> > > For bgpd, I suspect the problem to be fairly simple: snmpwalk is a serie
> >> > > of GETNEXT requests. For each GETNEXT request, we need to locate the
> >> > > appropriate element to return and for this, we need to walk each route
> >> > > table from the beginning.
> >> > >
> >> > > An easy fix would be to remember where we were the last time we got a
> >> > > GETNEXT.
> >> >
> >> > I don't think that's the problem. I did some profiling with
> >> > callgrind[1] and found out that the libnetsnmp is inherently slow. I
> >> > did a snmpwalk over a table with 10k routes and only a small
> >> > percentage of the execution time (~ 1.3%) was to gather information
> >> > from the BGP table (in the bgp4PathAttrTable function). I might be
> >> > wrong, but I think there's nothing we can do about this problem.
> >> >
> >> > [1] http://www.inf.ufrgs.br/~rwestphal/files/callgrind.png
> >> >
> >> > > I will try to work on this. Is there some way to get a huge BGP
> >> > > table (with exabgp maybe?)?
> >> >
> >> > I'm using the bgp_simple.pl script. I followed this tutorial to get
> >> > started with it:
> >> > http://evilrouters.net/2009/08/21/getting-bgp-routes-into-dynamips-with-video/
> >> >
> >> > > You are right, I didn't retest SMUX when I added trap support. I have
> >> > > added your patch and rebased my stack of patches (to make all patches
> >> > > compile, since David did not merge them yet). I have therefore "broken"
> >> > > your tree. You can get it right with something like (assuming the remote
> >> > > name for my repository is "rvincent")
> >> > >
> >> > > git fetch rvincent
> >> > > git rebase --onto rvincent/feature/agentx vincent~1 vincent
> >> > >
> >> > > (or you can just start a new branch and cherry-pick your last commit)
> >> >
> >> > Perfect. I hope your patches will be merged in a few days.
> >> >
> >> > > Your patch seems fine. I don't have a testbed to actually test it but I
> >> > > don't see any problem with it.
> >> >
> >> > Thanks for looking into it. I'll review this patch next week and then
> >> > send it to quagga-dev.
> >> >
> >> > Regards,
> >>
> >> I did some work to speed up SNMP and it's handling of large tables.
> >> A lot of the problem was N^2 insertion into tables, combined with cache
> >> timeout being less than the load time.
> >
> > Do these changes conflict with Vincent's AgentX support? Could you
> > (re-)post them to the list?
> >
> > Thanks in advance,
> >
> > -David
>
> His changes are in the net-snmp, not quagga:
> http://git.vyatta.com/git/?p=net-snmp.git;a=shortlog;h=refs/heads/oxnard
>
> I'm testing them now.
>
There is one more in our Vyatta version. Net-snmp project seems to be
one of those "hard to get patches accepted" projects so I stopped bothering
commit a4768cfe125f1481e05be8d2f0dece546b1083b6
Author: Stephen Hemminger <shemminger [at] vyatta>
Date: Mon Feb 20 12:11:15 2012 -0800
optimize insertion of binary array container
The binary array is one of the most common container types in net-snmp
but each insert causes a lookup and a resort of the whole array.
Instead, of sorting use the lookup process to determine the location
in the array to insert, and optimize for the most common case.
Most containers insert items in order, so it makes sense to optimize
for the case of appending. This especially important for huge tables
like the route table on a router.
---
snmplib/container_binary_array.c | 54 ++++++++++++++++++++++++++-----------
1 files changed, 38 insertions(+), 16 deletions(-)
diff --git a/snmplib/container_binary_array.c b/snmplib/container_binary_array.c
index 91298b3..5828670 100644
--- a/snmplib/container_binary_array.c
+++ b/snmplib/container_binary_array.c
@@ -36,7 +36,6 @@
typedef struct binary_array_table_s {
size_t max_size; /* Size of the current data table */
size_t count; /* Index of the next free entry */
- int dirty;
void **data; /* The table itself */
} binary_array_table;
@@ -48,75 +47,6 @@ typedef struct binary_array_iterator_s {
static netsnmp_iterator *_ba_iterator_get(netsnmp_container *c);
-/**********************************************************************
- *
- *
- *
- */
-static void
-array_qsort(void **data, int first, int last, netsnmp_container_compare *f)
-{
- int i, j;
- void *mid, *tmp;
-
- i = first;
- j = last;
- mid = data[first + ((last - first) >> 1)];
-
- do {
- while (i < last && (*f)(data[i], mid) < 0)
- ++i;
- while (j > first && (*f)(mid, data[j]) < 0)
- --j;
-
- if(i < j) {
- tmp = data[i];
- data[i] = data[j];
- data[j] = tmp;
- ++i;
- --j;
- }
- else if (i == j) {
- ++i;
- --j;
- break;
- }
- } while(i <= j);
-
- if (j > first)
- array_qsort(data, first, j, f);
-
- if (i < last)
- array_qsort(data, i, last, f);
-}
-
-static int
-Sort_Array(netsnmp_container *c)
-{
- binary_array_table *t = (binary_array_table*)c->container_data;
- netsnmp_assert(t!=NULL);
- netsnmp_assert(c->compare!=NULL);
-
- if (c->flags & CONTAINER_KEY_UNSORTED)
- return 0;
-
- if (t->dirty) {
- /*
- * Sort the table
- */
- if (t->count > 1)
- array_qsort(t->data, 0, t->count - 1, c->compare);
- t->dirty = 0;
-
- /*
- * no way to know if it actually changed... just assume so.
- */
- ++c->sync;
- }
-
- return 1;
-}
-
static int
linear_search(const void *val, netsnmp_container *c)
{
@@ -165,9 +95,6 @@ binary_search(const void *val, netsnmp_container *c, int exact)
return linear_search(val, c);
}
- if (t->dirty)
- Sort_Array(c);
-
while (len > 0) {
half = len >> 1;
middle = first;
@@ -219,7 +146,6 @@ netsnmp_binary_array_initialize(void)
t->max_size = 0;
t->count = 0;
- t->dirty = 0;
t->data = NULL;
return t;
@@ -275,12 +201,6 @@ netsnmp_binary_array_get(netsnmp_container *c, const void *key, int exact)
return NULL;
/*
- * if the table is dirty, sort it.
- */
- if (t->dirty)
- Sort_Array(c);
-
- /*
* if there is a key, search. Otherwise default is 0;
*/
if (key) {
@@ -343,12 +263,6 @@ netsnmp_binary_array_remove(netsnmp_container *c, const void *key, void **save)
return 0;
/*
- * if the table is dirty, sort it.
- */
- if (t->dirty)
- Sort_Array(c);
-
- /*
* search
*/
if ((index = binary_search(key, c, 1)) == -1)
@@ -365,9 +279,6 @@ netsnmp_binary_array_for_each(netsnmp_container *c,
binary_array_table *t = (binary_array_table*)c->container_data;
size_t i;
- if (sort && t->dirty)
- Sort_Array(c);
-
for (i = 0; i < t->count; ++i)
(*fe) (t->data[i], context);
}
@@ -387,7 +298,6 @@ netsnmp_binary_array_clear(netsnmp_container *c,
}
t->count = 0;
- t->dirty = 0;
++c->sync;
}
@@ -395,25 +305,51 @@ NETSNMP_STATIC_INLINE int
netsnmp_binary_array_insert(netsnmp_container *c, const void *entry)
{
binary_array_table *t = (binary_array_table*)c->container_data;
- int new_max, was_dirty = 0;
- void *new_data; /* Used for * a) extending the data table
- * * b) the next entry to use */
- /*
- * check for duplicates
- */
- if (! (c->flags & CONTAINER_KEY_ALLOW_DUPLICATES)) {
- was_dirty = t->dirty;
- new_data = netsnmp_binary_array_get(c, entry, 1);
- if (NULL != new_data) {
- DEBUGMSGTL(("container","not inserting duplicate key\n"));
- return -1;
+ int new_max;
+ int index = -1; /* append */
+
+ if (t->count == 0)
+ ; /* Trivial case of empty list */
+ else if (c->flags & CONTAINER_KEY_UNSORTED) {
+ /* Unsorted list, always append but check for dups */
+ if ( !(c->flags & CONTAINER_KEY_ALLOW_DUPLICATES) &&
+ linear_search(entry, c) != -1)
+ goto duplicate;
+
+ } else {
+ int last = t->count - 1;
+ int result;
+
+ /* Optimize for case of appending to end of array. */
+ if ( (result = c->compare(t->data[last], entry)) <= 0) {
+ /* and check for duplicate */
+ if ( !(c->flags & CONTAINER_KEY_ALLOW_DUPLICATES) &&
+ result == 0)
+ goto duplicate;
+ } else {
+ /* Find nearest match.
+ * Returns the index of the entry to put after this one.
+ * -1 means put at the end.
+ */
+ index = binary_search(entry, c, 0);
+
+ /*
+ * If key is duplicate then the entry before it
+ * will be the same.
+ */
+ if ( !(c->flags & CONTAINER_KEY_ALLOW_DUPLICATES) &&
+ index > 0 &&
+ c->compare(t->data[index - 1], entry) == 0)
+ goto duplicate;
}
}
-
+
/*
* check if we need to resize the array
*/
if (t->max_size <= t->count) {
+ void **new_data;
+
/*
* Table is full, so extend it to double the size
*/
@@ -425,25 +361,29 @@ netsnmp_binary_array_insert(netsnmp_container *c, const void *entry)
if (new_data == NULL)
return -1;
- t->data = (void**)new_data;
+ t->data = new_data;
t->max_size = new_max;
}
/*
* Insert the new entry into the data array
*/
- t->data[t->count++] = NETSNMP_REMOVE_CONST(void *, entry);
- t->dirty = 1;
+ if (index == -1)
+ index = t->count;
+ else
+ memmove(&t->data[index+1], &t->data[index],
+ sizeof(void *) * (t->count - index));
- /*
- * if array was dirty before we called get, sync was incremented when
- * get called SortArray. If we didn't call get or the array wasn't dirty,
- * bump sync now.
- */
- if (!was_dirty)
- ++c->sync;
+ t->data[index] = NETSNMP_REMOVE_CONST(void *, entry);
+ t->count++;
+
+ ++c->sync;
return 0;
+
+duplicate:
+ DEBUGMSGTL(("container","not inserting duplicate key\n"));
+ return -1;
}
/**********************************************************************
@@ -464,9 +404,6 @@ binary_search_for_start(netsnmp_index *val, netsnmp_container *c)
if (!len)
return -1;
- if (t->dirty)
- Sort_Array(c);
-
while (len > 0) {
half = len >> 1;
middle = first;
@@ -506,12 +443,6 @@ netsnmp_binary_array_get_subset(netsnmp_container *c, void *key, int *len)
return NULL;
/*
- * if the table is dirty, sort it.
- */
- if (t->dirty)
- Sort_Array(c);
-
- /*
* find matching items
*/
start = end = binary_search_for_start((netsnmp_index *)key, c);
@@ -649,7 +580,6 @@ _ba_duplicate(netsnmp_container *c, void *ctx, u_int flags)
dupt->max_size = t->max_size;
dupt->count = t->count;
- dupt->dirty = t->dirty;
/*
* shallow copy
@@ -831,9 +761,6 @@ _ba_iterator_reset(binary_array_iterator *it)
return -1;
}
- if (t->dirty)
- Sort_Array(it->base.container);
-
/*
* save sync count, to make sure container doesn't change while
* iterator is in use.
_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev
|
signature.asc
0001-ospf6d-fix-segfault-when-requesting-inexistant-inter.patch
