From d6978c9faadf9552bcb522d56d40c8aefa2e503e Mon Sep 17 00:00:00 2001 From: "/C=EU/ST=EU/CN=Pablo Neira Ayuso/emailAddress=pablo@netfilter.org" Date: Mon, 31 Dec 2007 20:37:54 +0000 Subject: - hash lookup speedups based on comments from netdev's discussions - minor fix for hash6 in cache.c (however, ipv6 support is still broken - several updates in the TODO file --- src/cache.c | 15 +++++++++++---- 1 file changed, 11 insertions(+), 4 deletions(-) (limited to 'src/cache.c') diff --git a/src/cache.c b/src/cache.c index 80cde01..b92957a 100644 --- a/src/cache.c +++ b/src/cache.c @@ -38,7 +38,14 @@ static u_int32_t hash(const void *data, struct hashtable *table) ((nfct_get_attr_u16(ct, ATTR_ORIG_PORT_SRC) << 16) | (nfct_get_attr_u16(ct, ATTR_ORIG_PORT_DST)))); - return jhash_2words(a, b, 0) % table->hashsize; + /* + * Instead of returning hash % table->hashsize (implying a divide) + * we return the high 32 bits of the (hash * table->hashsize) that will + * give results between [0 and hashsize-1] and same hash distribution, + * but using a multiply, less expensive than a divide. See: + * http://www.mail-archive.com/netdev@vger.kernel.org/msg56623.html + */ + return ((u_int64_t)jhash_2words(a, b, 0) * table->hashsize) >> 32; } static u_int32_t hash6(const void *data, struct hashtable *table) @@ -47,15 +54,15 @@ static u_int32_t hash6(const void *data, struct hashtable *table) const struct us_conntrack *u = data; struct nf_conntrack *ct = u->ct; - a = jhash(nfct_get_attr(ct, ATTR_ORIG_IPV6_SRC), sizeof(u_int32_t), + a = jhash(nfct_get_attr(ct, ATTR_ORIG_IPV6_SRC), sizeof(u_int32_t)*4, ((nfct_get_attr_u8(ct, ATTR_ORIG_L3PROTO) << 16) | (nfct_get_attr_u8(ct, ATTR_ORIG_L4PROTO)))); - b = jhash(nfct_get_attr(ct, ATTR_ORIG_IPV6_DST), sizeof(u_int32_t), + b = jhash(nfct_get_attr(ct, ATTR_ORIG_IPV6_DST), sizeof(u_int32_t)*4, ((nfct_get_attr_u16(ct, ATTR_ORIG_PORT_SRC) << 16) | (nfct_get_attr_u16(ct, ATTR_ORIG_PORT_DST)))); - return jhash_2words(a, b, 0) % table->hashsize; + return ((u_int64_t)jhash_2words(a, b, 0) * table->hashsize) >> 32; } static int __compare(const struct nf_conntrack *ct1, -- cgit v1.2.3