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.
Lots of help in narrowing this down from markus@.
Improved comments from claudio@.
OK markus@, claudio@

1 files changed, 16 insertions, 7 deletions

diff --git a/sys/net/radix.c b/sys/net/radix.c
index 9ee6c10dd06..98e7273160c 100644
--- a/sys/net/radix.c
+++ b/sys/net/radix.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: radix.c,v 1.27 2010/06/28 18:50:37 claudio Exp $	*/
+/*	$OpenBSD: radix.c,v 1.28 2010/08/22 17:02:04 mpf Exp $	*/
 /*	$NetBSD: radix.c,v 1.20 2003/08/07 16:32:56 agc Exp $	*/
 
 /*
@@ -472,13 +472,22 @@ rn_lexobetter(void *m_arg, void *n_arg)
 {
 	u_char *mp = m_arg, *np = n_arg, *lim;
 
+	/*
+	 * Longer masks might not really be lexicographically better,
+	 * but longer masks always have precedence since they must be checked
+	 * first. The netmasks were normalized before calling this function and
+	 * don't have unneeded trailing zeros.
+	 */
 	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 *