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 --- ChangeLog | 1 + TODO | 5 +++-- src/cache.c | 15 +++++++++++---- 3 files changed, 15 insertions(+), 6 deletions(-) diff --git a/ChangeLog b/ChangeLog index bbc2819..bf79b6a 100644 --- a/ChangeLog +++ b/ChangeLog @@ -24,6 +24,7 @@ o Now default synchronization mode is ftfw instead of alarm o rename `examples' directory to `doc' o add support for related conntracks (requires Linux kernel >= 2.6.22) o show error and warning messages to stderr +o hash lookup speedups based on comments from netdev's discussions version 0.9.5 (2007/07/29) ------------------------------ diff --git a/TODO b/TODO index 61f7e69..ff74c12 100644 --- a/TODO +++ b/TODO @@ -11,9 +11,10 @@ by dificulty levels: [X] ignorepool with unlimited size and ignore networks [ ] selective conntracks removal [ ] debian/rpm packages - [ ] improve website - [ ] Dumazet improvement hashtable (multiply vs. divide) + [X] improve website + [X] Dumazet improvement hashtable (multiply vs. divide) [X] add secmark support + [ ] logging support for the statistics mode = Requires some work = [ ] study better keepalived transitions 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