tech-net archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

16 year old bug



... has been found by OpenBSD:

Their commit message:
--------------------------------------------
Fix a 16 year old bug in the sorting routine for non-contiguous netmasks.
For masks of identical length rn_lexobetter() did not stop on the
first non-equal byte. This leads rn_addroute() to not detecting
duplicate entries and thus we might create a very long list of masks
to check for each node.
This can have a huge impact on IPsec performance, where non-contiguous
masks are used for the flow lookup.  In a setup with 1300 flows we
saw 400 duplicate masks and only a third of the expected throughput.
--------------------------------------------

The patch is attached. Any comments?

Christoph
Index: sys/net/radix.c
===================================================================
RCS file: /cvsroot/src/sys/net/radix.c,v
retrieving revision 1.43
diff -u -p -r1.43 radix.c
--- sys/net/radix.c     27 May 2009 17:46:50 -0000      1.43
+++ sys/net/radix.c     23 Aug 2010 11:50:07 -0000
@@ -559,12 +559,15 @@ rn_lexobetter(
        const u_char *lim;
 
        if (*mp > *np)
-               return 1;  /* not really, but need to check longer one first */
-       if (*mp == *np)
-               for (lim = mp + *mp; mp < lim;)
-                       if (*mp++ > *np++)
-                               return 1;
-       return 0;
+               return 1;
+       if (*mp < *np)
+               return 0;
+       /*
+        * Must return the first difference between the masks
+        * to ensure deterministic sorting.
+        */
+       lim = mp + *mp;
+       return (memcmp(mp, np, *lim) > 0);
 }
 
 static struct radix_mask *


Home | Main Index | Thread Index | Old Index