From 1658ae30a0e97e7f4018d8cba67e459078470d1a Mon Sep 17 00:00:00 2001 From: James Simmons Date: Tue, 15 Jan 2019 11:25:54 -0500 Subject: [PATCH] LU-8130 libcfs: port working hash from upstream The hash_[32|64] function in pre-4.6 kernels produce hashes with poor distributions which result in high collision rates. Backport those improvements for the pre-4.6 kernels Lustre supports. Details can be read here: https://lwn.net/Articles/687494 Test-Parameters: trivial Change-Id: Id2436ba8be2d3ed482c5386b79710f594d5b3e59 Signed-off-by: James Simmons Reviewed-on: https://review.whamcloud.com/33789 Tested-by: Jenkins Tested-by: Maloo Reviewed-by: Alexey Lyashkov Reviewed-by: Yang Sheng Reviewed-by: Oleg Drokin --- libcfs/autoconf/lustre-libcfs.m4 | 17 +++++++++++++++++ libcfs/include/libcfs/linux/linux-hash.h | 30 +++++++++++++++++++++++++++++- 2 files changed, 46 insertions(+), 1 deletion(-) diff --git a/libcfs/autoconf/lustre-libcfs.m4 b/libcfs/autoconf/lustre-libcfs.m4 index d437331..2763748 100644 --- a/libcfs/autoconf/lustre-libcfs.m4 +++ b/libcfs/autoconf/lustre-libcfs.m4 @@ -712,6 +712,22 @@ LB_CHECK_EXPORT([kset_find_obj], [lib/kobject.c], ]) # LIBCFS_EXPORT_KSET_FIND_OBJ # +# Kernel version 4.6+ commit ef703f49a6c5b909a85149bb6625c4ed0d697186 +# fixed the brokenness of hash_64(). The fix removed GOLDEN_RATIO_PRIME_64 +# since it was a poor prime value. +# +AC_DEFUN([LIBCFS_BROKEN_HASH_64], [ +LB_CHECK_COMPILE([kernel has fixed hash_64()], +broken_hash_64, [ + #include +],[ + int tmp = GOLDEN_RATIO_PRIME_64; +],[ + AC_DEFINE(HAVE_BROKEN_HASH_64, 1, [kernel hash_64() is broken]) +]) +]) # LIBCFS_BROKEN_HASH_64 + +# # LIBCFS_STACKTRACE_OPS_ADDRESS_RETURN_INT # # linux 4.6 kernel changed stacktrace_ops address to return an int @@ -995,6 +1011,7 @@ LIBCFS_KSTRTOBOOL_FROM_USER LIBCFS_CRYPTO_HASH_HELPERS LIBCFS_EXPORT_KSET_FIND_OBJ # 4.6 +LIBCFS_BROKEN_HASH_64 LIBCFS_STACKTRACE_OPS_ADDRESS_RETURN_INT LIBCFS_GET_USER_PAGES_6ARG LIBCFS_STRINGHASH diff --git a/libcfs/include/libcfs/linux/linux-hash.h b/libcfs/include/libcfs/linux/linux-hash.h index 1227ec8..7c3de9e 100644 --- a/libcfs/include/libcfs/linux/linux-hash.h +++ b/libcfs/include/libcfs/linux/linux-hash.h @@ -38,6 +38,34 @@ u64 cfs_hashlen_string(const void *salt, const char *name); #endif #endif /* !HAVE_STRINGHASH */ +#ifdef HAVE_BROKEN_HASH_64 + +#define GOLDEN_RATIO_32 0x61C88647 +#define GOLDEN_RATIO_64 0x61C8864680B583EBull + +static inline u32 cfs_hash_32(u32 val, unsigned int bits) +{ + /* High bits are more random, so use them. */ + return (val * GOLDEN_RATIO_32) >> (32 - bits); +} + +static __always_inline u32 cfs_hash_64(u64 val, unsigned int bits) +{ +#if BITS_PER_LONG == 64 + /* 64x64-bit multiply is efficient on all 64-bit processors */ + return val * GOLDEN_RATIO_64 >> (64 - bits); +#else + /* Hash 64 bits using only 32x32-bit multiply. */ + return cfs_hash_32(((u32)val ^ ((val >> 32) * GOLDEN_RATIO_32)), bits); +#endif +} +#else + +#define cfs_hash_32 hash_32 +#define cfs_hash_64 hash_64 + +#endif /* HAVE_BROKEN_HASH_64 */ + #ifndef HAVE_RHASHTABLE_LOOKUP_GET_INSERT_FAST /** * rhashtable_lookup_get_insert_fast - lookup and insert object into hash table @@ -74,4 +102,4 @@ static inline void *rhashtable_lookup_get_insert_fast( } #endif /* !HAVE_RHASHTABLE_LOOKUP_GET_INSERT_FAST */ -#endif /* __LIBCFS_LINUX_MISC_H__ */ +#endif /* __LIBCFS_LINUX_HASH_H__ */ -- 1.8.3.1