|
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@xxxxxxxxx>
> ---
> 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
--
Julian Anastasov <ja@xxxxxx>
--
To unsubscribe from this list: send the line "unsubscribe lvs-devel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
|
