... 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 *
