From 239e826876e5e20405e14a180a8fd4377d6553b2 Mon Sep 17 00:00:00 2001 From: Timothy Day Date: Mon, 6 Feb 2023 20:02:15 +0000 Subject: [PATCH] LU-16518 misc: use fixed hash code There is a configure check to avoid using broken hashing code. All calls to 'hash_*' are replace by the 'cfs_hash_*' equivalents, to make use of this check. Two functions which hash then apply a mask are removed. The calls are replaced with 'cfs_hash_*' and manually applying the mask. Signed-off-by: Timothy Day Change-Id: Ia4b27cb6fb1329b9df45c00f748a8d22178b0654 Reviewed-on: https://review.whamcloud.com/c/fs/lustre-release/+/49916 Tested-by: jenkins Tested-by: Maloo Reviewed-by: jsimmons Reviewed-by: Oleg Drokin Reviewed-by: Andreas Dilger --- libcfs/include/libcfs/libcfs_hash.h | 35 +------------------------------- libcfs/include/libcfs/linux/linux-hash.h | 14 +++++++++++-- libcfs/libcfs/linux/linux-wait.c | 2 +- lnet/include/lnet/lib-lnet.h | 4 ++-- lnet/lnet/api-ni.c | 4 ++-- lnet/lnet/lib-ptl.c | 2 +- lustre/include/lustre_fid.h | 2 +- lustre/ldlm/ldlm_flock.c | 2 +- lustre/ldlm/ldlm_lockd.c | 2 +- lustre/lov/lov_object.c | 2 +- lustre/obdclass/lu_tgt_descs.c | 1 - lustre/osc/osc_quota.c | 2 +- lustre/ptlrpc/gss/gss_svc_upcall.c | 4 ++-- lustre/quota/lquota_entry.c | 2 +- 14 files changed, 27 insertions(+), 51 deletions(-) diff --git a/libcfs/include/libcfs/libcfs_hash.h b/libcfs/include/libcfs/libcfs_hash.h index bdf3cdd..34ffdb1 100644 --- a/libcfs/include/libcfs/libcfs_hash.h +++ b/libcfs/include/libcfs/libcfs_hash.h @@ -37,24 +37,9 @@ #ifndef __LIBCFS_HASH_H__ #define __LIBCFS_HASH_H__ -#include #include #include - -/* - * Knuth recommends primes in approximately golden ratio to the maximum - * integer representable by a machine word for multiplicative hashing. - * Chuck Lever verified the effectiveness of this technique: - * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf - * - * These primes are chosen to be bit-sparse, that is operations on - * them can use shifts and additions instead of multiplications for - * machines where multiplications are slow. - */ -/* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */ -#define CFS_GOLDEN_RATIO_PRIME_32 0x9e370001UL -/* 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */ -#define CFS_GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001ULL +#include /** disable debug */ #define CFS_HASH_DEBUG_NONE 0 @@ -830,24 +815,6 @@ cfs_hash_djb2_hash(const void *key, size_t size, unsigned mask) return (hash & mask); } -/* - * Generic u32 hash algorithm. - */ -static inline unsigned -cfs_hash_u32_hash(const __u32 key, unsigned mask) -{ - return ((key * CFS_GOLDEN_RATIO_PRIME_32) & mask); -} - -/* - * Generic u64 hash algorithm. - */ -static inline unsigned -cfs_hash_u64_hash(const __u64 key, unsigned mask) -{ - return ((unsigned)(key * CFS_GOLDEN_RATIO_PRIME_64) & mask); -} - /** iterate over all buckets in @bds (array of struct cfs_hash_bd) */ #define cfs_hash_for_each_bd(bds, n, i) \ for (i = 0; i < n && (bds)[i].bd_bucket != NULL; i++) diff --git a/libcfs/include/libcfs/linux/linux-hash.h b/libcfs/include/libcfs/linux/linux-hash.h index 3c615bd..c7a04bc 100644 --- a/libcfs/include/libcfs/linux/linux-hash.h +++ b/libcfs/include/libcfs/linux/linux-hash.h @@ -59,10 +59,20 @@ static __always_inline u32 cfs_hash_64(u64 val, unsigned int bits) return cfs_hash_32(((u32)val ^ ((val >> 32) * GOLDEN_RATIO_32)), bits); #endif } + +#if BITS_PER_LONG == 32 +#define cfs_hash_long(val, bits) cfs_hash_32(val, bits) +#elif BITS_PER_LONG == 64 +#define cfs_hash_long(val, bits) cfs_hash_64(val, bits) +#else +#error Wordsize not 32 or 64 +#endif + #else -#define cfs_hash_32 hash_32 -#define cfs_hash_64 hash_64 +#define cfs_hash_32 hash_32 +#define cfs_hash_64 hash_64 +#define cfs_hash_long hash_long #endif /* HAVE_BROKEN_HASH_64 */ diff --git a/libcfs/libcfs/linux/linux-wait.c b/libcfs/libcfs/linux/linux-wait.c index 33117c2..94467b9 100644 --- a/libcfs/libcfs/linux/linux-wait.c +++ b/libcfs/libcfs/linux/linux-wait.c @@ -1,7 +1,7 @@ /* * The implementation of the wait_bit*() and related waiting APIs: */ -#include +#include #include #ifdef HAVE_SCHED_HEADERS #include diff --git a/lnet/include/lnet/lib-lnet.h b/lnet/include/lnet/lib-lnet.h index 68dfc5c..7dd5148 100644 --- a/lnet/include/lnet/lib-lnet.h +++ b/lnet/include/lnet/lib-lnet.h @@ -513,8 +513,8 @@ lnet_nid2peerhash(struct lnet_nid *nid) int i; for (i = 0; i < 4; i++) - h = hash_32(nid->nid_addr[i]^h, 32); - return hash_32(LNET_NID_NET(nid) ^ h, LNET_PEER_HASH_BITS); + h = cfs_hash_32(nid->nid_addr[i]^h, 32); + return cfs_hash_32(LNET_NID_NET(nid) ^ h, LNET_PEER_HASH_BITS); } static inline struct list_head * diff --git a/lnet/lnet/api-ni.c b/lnet/lnet/api-ni.c index fd2da64..c0ce984 100644 --- a/lnet/lnet/api-ni.c +++ b/lnet/lnet/api-ni.c @@ -1635,8 +1635,8 @@ lnet_nid_cpt_hash(struct lnet_nid *nid, unsigned int number) return lnet_nid4_cpt_hash(lnet_nid_to_nid4(nid), number); for (i = 0; i < 4; i++) - h = hash_32(nid->nid_addr[i]^h, 32); - val = hash_32(LNET_NID_NET(nid) ^ h, LNET_CPT_BITS); + h = cfs_hash_32(nid->nid_addr[i]^h, 32); + val = cfs_hash_32(LNET_NID_NET(nid) ^ h, LNET_CPT_BITS); if (val < number) return val; return (unsigned int)(h + val + (val >> 1)) % number; diff --git a/lnet/lnet/lib-ptl.c b/lnet/lnet/lib-ptl.c index 40f7214..df065e2 100644 --- a/lnet/lnet/lib-ptl.c +++ b/lnet/lnet/lib-ptl.c @@ -365,7 +365,7 @@ lnet_mt_match_head(struct lnet_match_table *mtable, unsigned long hash = mbits + nidhash(&id->nid) + id->pid; LASSERT(lnet_ptl_is_unique(ptl)); - hash = hash_long(hash, LNET_MT_HASH_BITS); + hash = cfs_hash_long(hash, LNET_MT_HASH_BITS); return &mtable->mt_mhash[hash & LNET_MT_HASH_MASK]; } } diff --git a/lustre/include/lustre_fid.h b/lustre/include/lustre_fid.h index 86e5986..251d962 100644 --- a/lustre/include/lustre_fid.h +++ b/lustre/include/lustre_fid.h @@ -818,7 +818,7 @@ static inline __u32 fid_hash(const struct lu_fid *f, int bits) { /* all objects with same id and different versions will belong to same * collisions list. */ - return hash_long(fid_flatten(f), bits); + return cfs_hash_long(fid_flatten(f), bits); } /** diff --git a/lustre/ldlm/ldlm_flock.c b/lustre/ldlm/ldlm_flock.c index 770cf94..d7572a2 100644 --- a/lustre/ldlm/ldlm_flock.c +++ b/lustre/ldlm/ldlm_flock.c @@ -853,7 +853,7 @@ void ldlm_flock_policy_local_to_wire(const union ldlm_policy_data *lpolicy, static unsigned ldlm_export_flock_hash(struct cfs_hash *hs, const void *key, unsigned mask) { - return cfs_hash_u64_hash(*(__u64 *)key, mask); + return cfs_hash_64(*(__u64 *)key, 0) & mask; } static void * diff --git a/lustre/ldlm/ldlm_lockd.c b/lustre/ldlm/ldlm_lockd.c index 47915b2..cb85fac 100644 --- a/lustre/ldlm/ldlm_lockd.c +++ b/lustre/ldlm/ldlm_lockd.c @@ -3101,7 +3101,7 @@ void ldlm_put_ref(void) static unsigned ldlm_export_lock_hash(struct cfs_hash *hs, const void *key, unsigned int mask) { - return cfs_hash_u64_hash(((struct lustre_handle *)key)->cookie, mask); + return cfs_hash_64(((struct lustre_handle *)key)->cookie, 0) & mask; } static void * diff --git a/lustre/lov/lov_object.c b/lustre/lov/lov_object.c index db6a7f3..57ce475 100644 --- a/lustre/lov/lov_object.c +++ b/lustre/lov/lov_object.c @@ -758,7 +758,7 @@ static int lov_init_composite(const struct lu_env *env, struct lov_device *dev, * so that different clients would use different mirrors for read. */ mirror_count = 0; preference = -1; - seq = hash_long((unsigned long)lov, 8); + seq = cfs_hash_long((unsigned long)lov, 8); for (i = 0; i < comp->lo_mirror_count; i++) { unsigned int idx = (i + seq) % comp->lo_mirror_count; diff --git a/lustre/obdclass/lu_tgt_descs.c b/lustre/obdclass/lu_tgt_descs.c index f2cffcc..57d93c9 100644 --- a/lustre/obdclass/lu_tgt_descs.c +++ b/lustre/obdclass/lu_tgt_descs.c @@ -36,7 +36,6 @@ #include #include #include -#include /* hash_long() */ #include #include #include diff --git a/lustre/osc/osc_quota.c b/lustre/osc/osc_quota.c index e1606c5..36af9d7 100644 --- a/lustre/osc/osc_quota.c +++ b/lustre/osc/osc_quota.c @@ -177,7 +177,7 @@ out_unlock: static unsigned oqi_hashfn(struct cfs_hash *hs, const void *key, unsigned mask) { - return cfs_hash_u32_hash(*((__u32*)key), mask); + return cfs_hash_32(*((__u32 *)key), 0) & mask; } static int diff --git a/lustre/ptlrpc/gss/gss_svc_upcall.c b/lustre/ptlrpc/gss/gss_svc_upcall.c index 07b8b2e..f535042 100644 --- a/lustre/ptlrpc/gss/gss_svc_upcall.c +++ b/lustre/ptlrpc/gss/gss_svc_upcall.c @@ -53,7 +53,6 @@ #include #include #include -#include #include #include #include @@ -65,6 +64,7 @@ #include #include #include +#include #include "gss_err.h" #include "gss_internal.h" @@ -107,7 +107,7 @@ static inline unsigned long hash_mem(char *buf, int length, int bits) len++; if ((len & (BITS_PER_LONG/8-1)) == 0) - hash = hash_long(hash^l, BITS_PER_LONG); + hash = cfs_hash_long(hash^l, BITS_PER_LONG); } while (len); return hash >> (BITS_PER_LONG - bits); diff --git a/lustre/quota/lquota_entry.c b/lustre/quota/lquota_entry.c index 7e2b62b..54b5966 100644 --- a/lustre/quota/lquota_entry.c +++ b/lustre/quota/lquota_entry.c @@ -41,7 +41,7 @@ MODULE_PARM_DESC(hash_lqs_cur_bits, "the current bits of lqe hash"); static unsigned lqe64_hash_hash(struct cfs_hash *hs, const void *key, unsigned mask) { - return cfs_hash_u64_hash(*((__u64 *)key), mask); + return cfs_hash_64(*((__u64 *)key), 0) & mask; } static void *lqe64_hash_key(struct hlist_node *hnode) -- 1.8.3.1