[PATCH net-next v1] ipvs: fix multiplicative hashing in sh/dh/lblc/lblcr algorithms

[PATCH net-next v1] ipvs: fix multiplicative hashing in sh/dh/lblc/lblcr algorithms

[Vincent Bernat]

The sh/dh/lblc/lblcr algorithms are using Knuth's multiplicative
hashing incorrectly. This results in uneven distribution.

To fix this, the result has to be shifted by a constant. In "Lecture
21: Hash functions" [1], it is said:

   In the fixed-point version, The division by 2^q is crucial. The
   common mistake when doing multiplicative hashing is to forget to do
   it, and in fact you can find web pages highly ranked by Google that
   explain multiplicative hashing without this step. Without this
   division, there is little point to multiplying by a, because ka mod
   m = (k mod m) * (a mod m) mod m . This is no better than modular
   hashing with a modulus of m, and quite possibly worse.

Typing the 2654435761 constant in DuckDuckGo shows many other sources
to confirm this issue. Moreover, doing the multiplication in the 32bit
integer space is enough, hence the change from 2654435761UL to
2654435761U.

[1]: https://www.cs.cornell.edu/courses/cs3110/2008fa/lectures/lec21.html

The following Python program illustrates the bug and its fix:

    import netaddr
    import collections
    import socket
    import statistics

    def run(buggy=False):
        base = netaddr.IPAddress('203.0.113.0')
        count = collections.defaultdict(int)
        for offset in range(100):
            for port in range(10000, 11000):
                r = socket.ntohs(port) + socket.ntohl(int(base) + offset)
                r *= 2654435761
                if buggy:
                    r %= 1 << 64
                else:
                    r %= 1 << 32
                    r >>= 24
                r &= 255
                count[r] += 1

        print(buggy,
              statistics.mean(count.values()),
              statistics.stdev(count.values()))

    run(True)
    run(False)

Its output is:

    True 25000 765.9416862050705
    False 390.625 4.681209831891333

Signed-off-by: Vincent Bernat <vincent@bernat.im>
---
 net/netfilter/ipvs/ip_vs_dh.c    | 4 +++-
 net/netfilter/ipvs/ip_vs_lblc.c  | 4 +++-
 net/netfilter/ipvs/ip_vs_lblcr.c | 4 +++-
 net/netfilter/ipvs/ip_vs_sh.c    | 3 ++-
 4 files changed, 11 insertions(+), 4 deletions(-)

diff --git a/net/netfilter/ipvs/ip_vs_dh.c b/net/netfilter/ipvs/ip_vs_dh.c
index 75f798f8e83b..5638e66dbdd1 100644
--- a/net/netfilter/ipvs/ip_vs_dh.c
+++ b/net/netfilter/ipvs/ip_vs_dh.c
@@ -81,7 +81,9 @@ static inline unsigned int ip_vs_dh_hashkey(int af, const union nf_inet_addr *ad
 		addr_fold = addr->ip6[0]^addr->ip6[1]^
 			    addr->ip6[2]^addr->ip6[3];
 #endif
-	return (ntohl(addr_fold)*2654435761UL) & IP_VS_DH_TAB_MASK;
+	return ((ntohl(addr_fold)*2654435761U) >>
+		(32 - IP_VS_DH_TAB_BITS)) &
+		IP_VS_DH_TAB_MASK;
 }
 
 
diff --git a/net/netfilter/ipvs/ip_vs_lblc.c b/net/netfilter/ipvs/ip_vs_lblc.c
index 3057e453bf31..df32022a2bc4 100644
--- a/net/netfilter/ipvs/ip_vs_lblc.c
+++ b/net/netfilter/ipvs/ip_vs_lblc.c
@@ -160,7 +160,9 @@ ip_vs_lblc_hashkey(int af, const union nf_inet_addr *addr)
 		addr_fold = addr->ip6[0]^addr->ip6[1]^
 			    addr->ip6[2]^addr->ip6[3];
 #endif
-	return (ntohl(addr_fold)*2654435761UL) & IP_VS_LBLC_TAB_MASK;
+	return ((ntohl(addr_fold)*2654435761U) >>
+		(32 - IP_VS_LBLC_TAB_BITS)) &
+		IP_VS_LBLC_TAB_MASK;
 }
 
 
diff --git a/net/netfilter/ipvs/ip_vs_lblcr.c b/net/netfilter/ipvs/ip_vs_lblcr.c
index 92adc04557ed..3d0d278d4901 100644
--- a/net/netfilter/ipvs/ip_vs_lblcr.c
+++ b/net/netfilter/ipvs/ip_vs_lblcr.c
@@ -323,7 +323,9 @@ ip_vs_lblcr_hashkey(int af, const union nf_inet_addr *addr)
 		addr_fold = addr->ip6[0]^addr->ip6[1]^
 			    addr->ip6[2]^addr->ip6[3];
 #endif
-	return (ntohl(addr_fold)*2654435761UL) & IP_VS_LBLCR_TAB_MASK;
+	return ((ntohl(addr_fold)*2654435761U) >>
+		(32 - IP_VS_LBLCR_TAB_BITS)) &
+		IP_VS_LBLCR_TAB_MASK;
 }
 
 
diff --git a/net/netfilter/ipvs/ip_vs_sh.c b/net/netfilter/ipvs/ip_vs_sh.c
index 16aaac6eedc9..d2d6cdfae86e 100644
--- a/net/netfilter/ipvs/ip_vs_sh.c
+++ b/net/netfilter/ipvs/ip_vs_sh.c
@@ -96,7 +96,8 @@ ip_vs_sh_hashkey(int af, const union nf_inet_addr *addr,
 		addr_fold = addr->ip6[0]^addr->ip6[1]^
 			    addr->ip6[2]^addr->ip6[3];
 #endif
-	return (offset + (ntohs(port) + ntohl(addr_fold))*2654435761UL) &
+	return ((offset + (ntohs(port) + ntohl(addr_fold))*2654435761U) >>
+		(32 - IP_VS_SH_TAB_BITS)) &
 		IP_VS_SH_TAB_MASK;
 }
 
-- 
2.16.3

Re: [PATCH net-next v1] ipvs: fix multiplicative hashing in sh/dh/lblc/lblcr algorithms

[Julian Anastasov]

	Hello,

On Sun, 1 Apr 2018, Vincent Bernat wrote:

> The sh/dh/lblc/lblcr algorithms are using Knuth's multiplicative
> hashing incorrectly. This results in uneven distribution.

	Good catch.

> To fix this, the result has to be shifted by a constant. In "Lecture
> 21: Hash functions" [1], it is said:
> 
>    In the fixed-point version, The division by 2^q is crucial. The
>    common mistake when doing multiplicative hashing is to forget to do
>    it, and in fact you can find web pages highly ranked by Google that
>    explain multiplicative hashing without this step. Without this
>    division, there is little point to multiplying by a, because ka mod
>    m = (k mod m) * (a mod m) mod m . This is no better than modular
>    hashing with a modulus of m, and quite possibly worse.
> 
> Typing the 2654435761 constant in DuckDuckGo shows many other sources
> to confirm this issue. Moreover, doing the multiplication in the 32bit
> integer space is enough, hence the change from 2654435761UL to
> 2654435761U.
> 
> [1]: https://www.cs.cornell.edu/courses/cs3110/2008fa/lectures/lec21.html
> 
> The following Python program illustrates the bug and its fix:
> 
>     import netaddr
>     import collections
>     import socket
>     import statistics
> 
>     def run(buggy=False):
>         base = netaddr.IPAddress('203.0.113.0')
>         count = collections.defaultdict(int)
>         for offset in range(100):
>             for port in range(10000, 11000):
>                 r = socket.ntohs(port) + socket.ntohl(int(base) + offset)
>                 r *= 2654435761
>                 if buggy:
>                     r %= 1 << 64
>                 else:
>                     r %= 1 << 32
>                     r >>= 24
>                 r &= 255
>                 count[r] += 1
> 
>         print(buggy,
>               statistics.mean(count.values()),
>               statistics.stdev(count.values()))
> 
>     run(True)
>     run(False)
> 
> Its output is:
> 
>     True 25000 765.9416862050705
>     False 390.625 4.681209831891333
> 
> Signed-off-by: Vincent Bernat <vincent@bernat.im>
> ---
>  net/netfilter/ipvs/ip_vs_dh.c    | 4 +++-
>  net/netfilter/ipvs/ip_vs_lblc.c  | 4 +++-
>  net/netfilter/ipvs/ip_vs_lblcr.c | 4 +++-
>  net/netfilter/ipvs/ip_vs_sh.c    | 3 ++-
>  4 files changed, 11 insertions(+), 4 deletions(-)
> 
> diff --git a/net/netfilter/ipvs/ip_vs_dh.c b/net/netfilter/ipvs/ip_vs_dh.c
> index 75f798f8e83b..5638e66dbdd1 100644
> --- a/net/netfilter/ipvs/ip_vs_dh.c
> +++ b/net/netfilter/ipvs/ip_vs_dh.c
> @@ -81,7 +81,9 @@ static inline unsigned int ip_vs_dh_hashkey(int af, const union nf_inet_addr *ad
>  		addr_fold = addr->ip6[0]^addr->ip6[1]^
>  			    addr->ip6[2]^addr->ip6[3];
>  #endif
> -	return (ntohl(addr_fold)*2654435761UL) & IP_VS_DH_TAB_MASK;
> +	return ((ntohl(addr_fold)*2654435761U) >>
> +		(32 - IP_VS_DH_TAB_BITS)) &
> +		IP_VS_DH_TAB_MASK;

	Looks like the '& mask' part is not needed, still,
it does not generate extra code. I see that other code uses
hash_32(val, bits) from include/linux/hash.h but note that it
used different ratio before Linux 4.7, in case someone backports
this patch on old kernels. So, I don't have preference what should
be used, may be return hash_32(ntohl(addr_fold), IP_VS_DH_TAB_BITS)
is better.

Regards

Re: [PATCH net-next v1] ipvs: fix multiplicative hashing in sh/dh/lblc/lblcr algorithms

[Vincent Bernat]

 ❦  1 avril 2018 11:11 +0300, Julian Anastasov <ja@ssi.bg> :

>> -	return (ntohl(addr_fold)*2654435761UL) & IP_VS_DH_TAB_MASK;
>> +	return ((ntohl(addr_fold)*2654435761U) >>
>> +		(32 - IP_VS_DH_TAB_BITS)) &
>> +		IP_VS_DH_TAB_MASK;
>
> 	Looks like the '& mask' part is not needed, still,
> it does not generate extra code. I see that other code uses
> hash_32(val, bits) from include/linux/hash.h but note that it
> used different ratio before Linux 4.7, in case someone backports
> this patch on old kernels. So, I don't have preference what should
> be used, may be return hash_32(ntohl(addr_fold), IP_VS_DH_TAB_BITS)
> is better.

I didn't notice this macro. I think this is a better option. Let me
amend the patch.
-- 
Don't stop with your first draft.
            - The Elements of Programming Style (Kernighan & Plauger)

[PATCH net-next v2] ipvs: fix multiplicative hashing in sh/dh/lblc/lblcr algorithms

[Vincent Bernat]

The sh/dh/lblc/lblcr algorithms are using Knuth's multiplicative
hashing incorrectly. Replace its use by the hash_32() macro, which
correctly implements this algorithm. It doesn't use the same constant,
but it shouldn't matter.

Signed-off-by: Vincent Bernat <vincent@bernat.im>
---
 net/netfilter/ipvs/ip_vs_dh.c    | 3 ++-
 net/netfilter/ipvs/ip_vs_lblc.c  | 3 ++-
 net/netfilter/ipvs/ip_vs_lblcr.c | 3 ++-
 net/netfilter/ipvs/ip_vs_sh.c    | 3 ++-
 4 files changed, 8 insertions(+), 4 deletions(-)

diff --git a/net/netfilter/ipvs/ip_vs_dh.c b/net/netfilter/ipvs/ip_vs_dh.c
index 75f798f8e83b..dfea31fb10c5 100644
--- a/net/netfilter/ipvs/ip_vs_dh.c
+++ b/net/netfilter/ipvs/ip_vs_dh.c
@@ -43,6 +43,7 @@
 #include <linux/module.h>
 #include <linux/kernel.h>
 #include <linux/skbuff.h>
+#include <linux/hash.h>
 
 #include <net/ip_vs.h>
 
@@ -81,7 +82,7 @@ static inline unsigned int ip_vs_dh_hashkey(int af, const union nf_inet_addr *ad
 		addr_fold = addr->ip6[0]^addr->ip6[1]^
 			    addr->ip6[2]^addr->ip6[3];
 #endif
-	return (ntohl(addr_fold)*2654435761UL) & IP_VS_DH_TAB_MASK;
+	return hash_32(ntohl(addr_fold),  IP_VS_DH_TAB_BITS);
 }
 
 
diff --git a/net/netfilter/ipvs/ip_vs_lblc.c b/net/netfilter/ipvs/ip_vs_lblc.c
index 3057e453bf31..08147fc6400c 100644
--- a/net/netfilter/ipvs/ip_vs_lblc.c
+++ b/net/netfilter/ipvs/ip_vs_lblc.c
@@ -48,6 +48,7 @@
 #include <linux/kernel.h>
 #include <linux/skbuff.h>
 #include <linux/jiffies.h>
+#include <linux/hash.h>
 
 /* for sysctl */
 #include <linux/fs.h>
@@ -160,7 +161,7 @@ ip_vs_lblc_hashkey(int af, const union nf_inet_addr *addr)
 		addr_fold = addr->ip6[0]^addr->ip6[1]^
 			    addr->ip6[2]^addr->ip6[3];
 #endif
-	return (ntohl(addr_fold)*2654435761UL) & IP_VS_LBLC_TAB_MASK;
+	return hash_32(ntohl(addr_fold), IP_VS_LBLC_TAB_BITS);
 }
 
 
diff --git a/net/netfilter/ipvs/ip_vs_lblcr.c b/net/netfilter/ipvs/ip_vs_lblcr.c
index 92adc04557ed..9b6a6c9e9cfa 100644
--- a/net/netfilter/ipvs/ip_vs_lblcr.c
+++ b/net/netfilter/ipvs/ip_vs_lblcr.c
@@ -47,6 +47,7 @@
 #include <linux/jiffies.h>
 #include <linux/list.h>
 #include <linux/slab.h>
+#include <linux/hash.h>
 
 /* for sysctl */
 #include <linux/fs.h>
@@ -323,7 +324,7 @@ ip_vs_lblcr_hashkey(int af, const union nf_inet_addr *addr)
 		addr_fold = addr->ip6[0]^addr->ip6[1]^
 			    addr->ip6[2]^addr->ip6[3];
 #endif
-	return (ntohl(addr_fold)*2654435761UL) & IP_VS_LBLCR_TAB_MASK;
+	return hash_32(ntohl(addr_fold), IP_VS_LBLCR_TAB_BITS);
 }
 
 
diff --git a/net/netfilter/ipvs/ip_vs_sh.c b/net/netfilter/ipvs/ip_vs_sh.c
index 16aaac6eedc9..1e01c782583a 100644
--- a/net/netfilter/ipvs/ip_vs_sh.c
+++ b/net/netfilter/ipvs/ip_vs_sh.c
@@ -96,7 +96,8 @@ ip_vs_sh_hashkey(int af, const union nf_inet_addr *addr,
 		addr_fold = addr->ip6[0]^addr->ip6[1]^
 			    addr->ip6[2]^addr->ip6[3];
 #endif
-	return (offset + (ntohs(port) + ntohl(addr_fold))*2654435761UL) &
+	return (offset + hash_32(ntohs(port) + ntohl(addr_fold),
+				 IP_VS_SH_TAB_BITS)) &
 		IP_VS_SH_TAB_MASK;
 }
 
-- 
2.16.3

Re: [PATCH net-next v2] ipvs: fix multiplicative hashing in sh/dh/lblc/lblcr algorithms

[Julian Anastasov]

	Hello,

On Sun, 1 Apr 2018, Vincent Bernat wrote:

> The sh/dh/lblc/lblcr algorithms are using Knuth's multiplicative
> hashing incorrectly. Replace its use by the hash_32() macro, which
> correctly implements this algorithm. It doesn't use the same constant,
> but it shouldn't matter.
> 
> Signed-off-by: Vincent Bernat <vincent@bernat.im>

	Looks good to me, thanks! Simon, please apply, if possible
with the extra space removed, see below...

Acked-by: Julian Anastasov <ja@ssi.bg>

> ---
>  net/netfilter/ipvs/ip_vs_dh.c    | 3 ++-
>  net/netfilter/ipvs/ip_vs_lblc.c  | 3 ++-
>  net/netfilter/ipvs/ip_vs_lblcr.c | 3 ++-
>  net/netfilter/ipvs/ip_vs_sh.c    | 3 ++-
>  4 files changed, 8 insertions(+), 4 deletions(-)
> 
> diff --git a/net/netfilter/ipvs/ip_vs_dh.c b/net/netfilter/ipvs/ip_vs_dh.c
> index 75f798f8e83b..dfea31fb10c5 100644
> --- a/net/netfilter/ipvs/ip_vs_dh.c
> +++ b/net/netfilter/ipvs/ip_vs_dh.c
> @@ -43,6 +43,7 @@
>  #include <linux/module.h>
>  #include <linux/kernel.h>
>  #include <linux/skbuff.h>
> +#include <linux/hash.h>
>  
>  #include <net/ip_vs.h>
>  
> @@ -81,7 +82,7 @@ static inline unsigned int ip_vs_dh_hashkey(int af, const union nf_inet_addr *ad
>  		addr_fold = addr->ip6[0]^addr->ip6[1]^
>  			    addr->ip6[2]^addr->ip6[3];
>  #endif
> -	return (ntohl(addr_fold)*2654435761UL) & IP_VS_DH_TAB_MASK;
> +	return hash_32(ntohl(addr_fold),  IP_VS_DH_TAB_BITS);

	Extra space above

>  }
>  
>  
> diff --git a/net/netfilter/ipvs/ip_vs_lblc.c b/net/netfilter/ipvs/ip_vs_lblc.c
> index 3057e453bf31..08147fc6400c 100644
> --- a/net/netfilter/ipvs/ip_vs_lblc.c
> +++ b/net/netfilter/ipvs/ip_vs_lblc.c
> @@ -48,6 +48,7 @@
>  #include <linux/kernel.h>
>  #include <linux/skbuff.h>
>  #include <linux/jiffies.h>
> +#include <linux/hash.h>
>  
>  /* for sysctl */
>  #include <linux/fs.h>
> @@ -160,7 +161,7 @@ ip_vs_lblc_hashkey(int af, const union nf_inet_addr *addr)
>  		addr_fold = addr->ip6[0]^addr->ip6[1]^
>  			    addr->ip6[2]^addr->ip6[3];
>  #endif
> -	return (ntohl(addr_fold)*2654435761UL) & IP_VS_LBLC_TAB_MASK;
> +	return hash_32(ntohl(addr_fold), IP_VS_LBLC_TAB_BITS);
>  }
>  
>  
> diff --git a/net/netfilter/ipvs/ip_vs_lblcr.c b/net/netfilter/ipvs/ip_vs_lblcr.c
> index 92adc04557ed..9b6a6c9e9cfa 100644
> --- a/net/netfilter/ipvs/ip_vs_lblcr.c
> +++ b/net/netfilter/ipvs/ip_vs_lblcr.c
> @@ -47,6 +47,7 @@
>  #include <linux/jiffies.h>
>  #include <linux/list.h>
>  #include <linux/slab.h>
> +#include <linux/hash.h>
>  
>  /* for sysctl */
>  #include <linux/fs.h>
> @@ -323,7 +324,7 @@ ip_vs_lblcr_hashkey(int af, const union nf_inet_addr *addr)
>  		addr_fold = addr->ip6[0]^addr->ip6[1]^
>  			    addr->ip6[2]^addr->ip6[3];
>  #endif
> -	return (ntohl(addr_fold)*2654435761UL) & IP_VS_LBLCR_TAB_MASK;
> +	return hash_32(ntohl(addr_fold), IP_VS_LBLCR_TAB_BITS);
>  }
>  
>  
> diff --git a/net/netfilter/ipvs/ip_vs_sh.c b/net/netfilter/ipvs/ip_vs_sh.c
> index 16aaac6eedc9..1e01c782583a 100644
> --- a/net/netfilter/ipvs/ip_vs_sh.c
> +++ b/net/netfilter/ipvs/ip_vs_sh.c
> @@ -96,7 +96,8 @@ ip_vs_sh_hashkey(int af, const union nf_inet_addr *addr,
>  		addr_fold = addr->ip6[0]^addr->ip6[1]^
>  			    addr->ip6[2]^addr->ip6[3];
>  #endif
> -	return (offset + (ntohs(port) + ntohl(addr_fold))*2654435761UL) &
> +	return (offset + hash_32(ntohs(port) + ntohl(addr_fold),
> +				 IP_VS_SH_TAB_BITS)) &
>  		IP_VS_SH_TAB_MASK;
>  }
>  
> -- 
> 2.16.3

Regards

Re: [PATCH net-next v2] ipvs: fix multiplicative hashing in sh/dh/lblc/lblcr algorithms

[Simon Horman]

On Sun, Apr 01, 2018 at 02:11:51PM +0300, Julian Anastasov wrote:
> 
> 	Hello,
> 
> On Sun, 1 Apr 2018, Vincent Bernat wrote:
> 
> > The sh/dh/lblc/lblcr algorithms are using Knuth's multiplicative
> > hashing incorrectly. Replace its use by the hash_32() macro, which
> > correctly implements this algorithm. It doesn't use the same constant,
> > but it shouldn't matter.
> > 
> > Signed-off-by: Vincent Bernat <vincent@bernat.im>
> 
> 	Looks good to me, thanks! Simon, please apply, if possible
> with the extra space removed, see below...
> 
> Acked-by: Julian Anastasov <ja@ssi.bg>

Thanks, I have applied this with the extra space removed.
I will submit it for inclusion in v4.18.