From 15db0a3070ec42228d0ac666b4ff089c645f9a46 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 Lustre-change: https://review.whamcloud.com/33789 Lustre-commit: 1658ae30a0e97e7f4018d8cba67e459078470d1a Test-Parameters: trivial Change-Id: Id2436ba8be2d3ed482c5386b79710f594d5b3e59 Signed-off-by: James Simmons Reviewed-by: Alexey Lyashkov Reviewed-by: Yang Sheng Signed-off-by: Minh Diep Reviewed-on: https://review.whamcloud.com/35179 Tested-by: jenkins Tested-by: Maloo Reviewed-by: Andreas Dilger Reviewed-by: Oleg Drokin --- libcfs/autoconf/lustre-libcfs.m4 | 17 +++++++++++++++++ libcfs/include/libcfs/linux/linux-hash.h | 28 ++++++++++++++++++++++++++++ 2 files changed, 45 insertions(+) diff --git a/libcfs/autoconf/lustre-libcfs.m4 b/libcfs/autoconf/lustre-libcfs.m4 index 06b6502..cc346b6 100644 --- a/libcfs/autoconf/lustre-libcfs.m4 +++ b/libcfs/autoconf/lustre-libcfs.m4 @@ -685,6 +685,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 @@ -1050,6 +1066,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 ea4ecbe..2721655 100644 --- a/libcfs/include/libcfs/linux/linux-hash.h +++ b/libcfs/include/libcfs/linux/linux-hash.h @@ -134,6 +134,34 @@ static inline void rhltable_walk_enter(struct rhltable *hlt, } #endif /* !HAVE_RHLTABLE */ +#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 -- 1.8.3.1