From 2f3261e08f312980102806912ec735174e2a0b94 Mon Sep 17 00:00:00 2001 From: Marco Pfatschbacher Date: Sun, 22 Aug 2010 17:02:05 +0000 Subject: 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@ --- sys/net/radix.c | 23 ++++++++++++++++------- 1 file changed, 16 insertions(+), 7 deletions(-) (limited to 'sys') 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 * -- cgit v1.2.3