| Message ID | ce10d01f0908050041p43c308fav72ac640f665e161f@mail.gmail.com |
|---|---|
| State | Rejected, archived |
| Delegated to: | David Miller |
| Headers | show |
Whoops, line wrapping broke the patch, here's it again. On Wed, Aug 5, 2009 at 10:41 AM, Jussi Mäki<joamaki@gmail.com> wrote: > Hi, > > The current xfrm hash functions perform very poorly when a number of > policies have the same > last byte in source and destination addresses. > > For example with __xfrm_dst_hash, hmask of 0xfff: > > 192.168.0.1-172.16.0.1 hashes to 3258 > 192.168.0.2-172.16.0.2 hashes to 3258 > ... and so on. > > This patch addresses the issue by rewriting the xfrm > hash functions to use the Jenkins' hash function.
From: Jussi Mäki <joamaki@gmail.com> Date: Wed, 5 Aug 2009 10:41:42 +0300 > Hi, > > The current xfrm hash functions perform very poorly when a number of > policies have the same > last byte in source and destination addresses. > > For example with __xfrm_dst_hash, hmask of 0xfff: > > 192.168.0.1-172.16.0.1 hashes to 3258 > 192.168.0.2-172.16.0.2 hashes to 3258 > ... and so on. > > This patch addresses the issue by rewriting the xfrm > hash functions to use the Jenkins' hash function. > > Signed-off-by: Jussi Maki <joamaki@gmail.com> jhash expands to a lot of code, and given your description of the problem, you could have fixed it by adding 2 instructions (see below) instead of 20 or 30 (jhash instruction count) at every hash calculation site. Simply change every instance of: (h >> 16) with ((h >> 16) ^ (h >> 24)) As much as I love jhash, it's overkill for fixing this problem. And if we do end up using jhash, it should get inlined into a seperate non-inline function instead of expanding that monster 4 or 5 times throughout the XFRM code. I'm not applying this, either make the simple one-liner fix I suggested above work or move the jhash into a non-inline expansion. -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Hi David, Changing the (h >> 16) to ((h >> 16) ^ (h >> 24)) still has the same problem as given in the example, that is if you have a set of transports with incrementing addresses (192.168.0.1-172.16.0.1, 192.168.0.2-172.16.0.2,..) they still hash to the same value. The reason to this is that it's doing src^dst in __xfrm4_daddr_saddr_hash. Should I pursue with fixing the inlining issue in my patch or would you have any suggestions how I could fix this by perhaps modifying __xfrm4_daddr_saddr_hash? On Wed, Aug 5, 2009 at 10:08 PM, David Miller<davem@davemloft.net> wrote: > From: Jussi Mäki <joamaki@gmail.com> > Date: Wed, 5 Aug 2009 10:41:42 +0300 > >> Hi, >> >> The current xfrm hash functions perform very poorly when a number of >> policies have the same >> last byte in source and destination addresses. >> >> For example with __xfrm_dst_hash, hmask of 0xfff: >> >> 192.168.0.1-172.16.0.1 hashes to 3258 >> 192.168.0.2-172.16.0.2 hashes to 3258 >> ... and so on. >> >> This patch addresses the issue by rewriting the xfrm >> hash functions to use the Jenkins' hash function. >> >> Signed-off-by: Jussi Maki <joamaki@gmail.com> > > jhash expands to a lot of code, and given your description of the > problem, you could have fixed it by adding 2 instructions (see below) > instead of 20 or 30 (jhash instruction count) at every hash > calculation site. > > Simply change every instance of: > > (h >> 16) > > with > > ((h >> 16) ^ (h >> 24)) > > As much as I love jhash, it's overkill for fixing this problem. > > And if we do end up using jhash, it should get inlined into a > seperate non-inline function instead of expanding that monster > 4 or 5 times throughout the XFRM code. > > I'm not applying this, either make the simple one-liner fix I > suggested above work or move the jhash into a non-inline expansion. > -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
From: Jussi Maki <joamaki@gmail.com> Date: Thu, 6 Aug 2009 09:32:37 +0300 > Should I pursue with fixing the inlining issue in my patch or would > you have any suggestions how I could > fix this by perhaps modifying __xfrm4_daddr_saddr_hash? Do some different mixing in __xfrm4_daddr_saddr_hash(), it's still going to be cheaper than jhash. -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/net/xfrm/xfrm_hash.h b/net/xfrm/xfrm_hash.h index d401dc8..59d4cb6 100644 --- a/net/xfrm/xfrm_hash.h +++ b/net/xfrm/xfrm_hash.h @@ -3,6 +3,7 @@ #include <linux/xfrm.h> #include <linux/socket.h> +#include <linux/jhash.h> static inline unsigned int __xfrm4_addr_hash(xfrm_address_t *addr) { @@ -14,31 +15,27 @@ static inline unsigned int __xfrm6_addr_hash(xfrm_address_t *addr) return ntohl(addr->a6[2] ^ addr->a6[3]); } -static inline unsigned int __xfrm4_daddr_saddr_hash(xfrm_address_t *daddr, xfrm_address_t *saddr) -{ - return ntohl(daddr->a4 ^ saddr->a4); -} - -static inline unsigned int __xfrm6_daddr_saddr_hash(xfrm_address_t *daddr, xfrm_address_t *saddr) -{ - return ntohl(daddr->a6[2] ^ daddr->a6[3] ^ - saddr->a6[2] ^ saddr->a6[3]); -} - -static inline unsigned int __xfrm_dst_hash(xfrm_address_t *daddr, xfrm_address_t *saddr, - u32 reqid, unsigned short family, +static inline unsigned int __xfrm_dst_hash(xfrm_address_t *daddr, + xfrm_address_t *saddr, + u32 reqid, + unsigned short family, unsigned int hmask) { - unsigned int h = family ^ reqid; + unsigned int shash = 0; + unsigned int dhash = 0; + switch (family) { case AF_INET: - h ^= __xfrm4_daddr_saddr_hash(daddr, saddr); + shash = __xfrm4_addr_hash(saddr); + dhash = __xfrm4_addr_hash(daddr); break; case AF_INET6: - h ^= __xfrm6_daddr_saddr_hash(daddr, saddr); - break; + shash = __xfrm6_addr_hash(saddr); + dhash = __xfrm6_addr_hash(daddr); } - return (h ^ (h >> 16)) & hmask; + + return jhash_3words(shash, dhash,
Hi, The current xfrm hash functions perform very poorly when a number of policies have the same last byte in source and destination addresses. For example with __xfrm_dst_hash, hmask of 0xfff: 192.168.0.1-172.16.0.1 hashes to 3258 192.168.0.2-172.16.0.2 hashes to 3258 ... and so on. This patch addresses the issue by rewriting the xfrm hash functions to use the Jenkins' hash function. Signed-off-by: Jussi Maki <joamaki@gmail.com> --- net/xfrm/xfrm_hash.h | 90 ++++++++++++++++++++++++++----------------------- 1 files changed, 48 insertions(+), 42 deletions(-) + reqid, family) & hmask; } static inline unsigned __xfrm_src_hash(xfrm_address_t *daddr, @@ -46,32 +43,37 @@ static inline unsigned __xfrm_src_hash(xfrm_address_t *daddr, unsigned short family, unsigned int hmask) { - unsigned int h = family; + unsigned int shash = 0; + unsigned int dhash = 0; switch (family) { case AF_INET: - h ^= __xfrm4_daddr_saddr_hash(daddr, saddr); + shash = __xfrm4_addr_hash(saddr); + dhash = __xfrm4_addr_hash(daddr); break; case AF_INET6: - h ^= __xfrm6_daddr_saddr_hash(daddr, saddr); - break; - }; - return (h ^ (h >> 16)) & hmask; + shash = __xfrm6_addr_hash(saddr); + dhash = __xfrm6_addr_hash(daddr); + } + return jhash_2words(shash, dhash, family) & hmask; } static inline unsigned int -__xfrm_spi_hash(xfrm_address_t *daddr, __be32 spi, u8 proto, unsigned short family, +__xfrm_spi_hash(xfrm_address_t *daddr, __be32 spi, u8 proto, + unsigned short family, unsigned int hmask) { - unsigned int h = (__force u32)spi ^ proto; + unsigned int h = 0; + switch (family) { case AF_INET: - h ^= __xfrm4_addr_hash(daddr); + h = __xfrm4_addr_hash(daddr); break; case AF_INET6: - h ^= __xfrm6_addr_hash(daddr); + h = __xfrm6_addr_hash(daddr); break; } - return (h ^ (h >> 10) ^ (h >> 20)) & hmask; + + return jhash_3words(h, spi, proto, family) & hmask; } static inline unsigned int __idx_hash(u32 index, unsigned int hmask) @@ -83,7 +85,8 @@ static inline unsigned int __sel_hash(struct xfrm_selector *sel, unsigned short { xfrm_address_t *daddr = &sel->daddr; xfrm_address_t *saddr = &sel->saddr; - unsigned int h = 0; + unsigned int shash = 0; + unsigned int dhash = 0; switch (family) { case AF_INET: @@ -91,7 +94,8 @@ static inline unsigned int __sel_hash(struct xfrm_selector *sel, unsigned short sel->prefixlen_s != 32) return hmask + 1; - h = __xfrm4_daddr_saddr_hash(daddr, saddr); + shash = __xfrm4_addr_hash(saddr); + dhash = __xfrm4_addr_hash(daddr); break; case AF_INET6: @@ -99,28 +103,30 @@ static inline unsigned int __sel_hash(struct xfrm_selector *sel, unsigned short sel->prefixlen_s != 128) return hmask + 1; - h = __xfrm6_daddr_saddr_hash(daddr, saddr); + shash = __xfrm6_addr_hash(saddr); + dhash = __xfrm6_addr_hash(daddr); break; }; - h ^= (h >> 16); - return h & hmask; + + return jhash_2words(shash, dhash, family) & hmask; } static inline unsigned int __addr_hash(xfrm_address_t *daddr, xfrm_address_t *saddr, unsigned short family, unsigned int hmask) { - unsigned int h = 0; + unsigned int shash = 0; + unsigned int dhash = 0; switch (family) { case AF_INET: - h = __xfrm4_daddr_saddr_hash(daddr, saddr); + shash = __xfrm4_addr_hash(saddr); + dhash = __xfrm4_addr_hash(daddr); break; - case AF_INET6: - h = __xfrm6_daddr_saddr_hash(daddr, saddr); - break; - }; - h ^= (h >> 16); - return h & hmask; + shash = __xfrm6_addr_hash(saddr); + dhash = __xfrm6_addr_hash(daddr); + } + + return jhash_2words(shash, dhash, family) & hmask; } extern struct hlist_head *xfrm_hash_alloc(unsigned int sz); -- -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html