[quagga-dev 9493] Re: [RFC] AgentX support for Quagga

Stephen Hemminger shemminger at vyatta.com
Tue Jun 26 18:59:13 BST 2012


On Tue, 26 Jun 2012 14:47:52 -0300
Renato Westphal <renatowestphal at gmail.com> wrote:

> 2012/6/26 David Lamparter <equinox at opensourcerouting.org>:
> > 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.com> wrote:
> >>
> >> > 2012/6/25 Vincent Bernat <bernat at luffy.cx>:
> >> > > 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.com>
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.




More information about the Quagga-dev mailing list