From ce404bd07c37f45d8c8fe0cf3e3ecf6e18740f43 Mon Sep 17 00:00:00 2001 From: Alexey Lyashkov Date: Tue, 10 Oct 2023 11:38:21 +0300 Subject: [PATCH] LU-17174 misc: fix hash functions 1) LU-16518 landing caused a bug which visible with debug kernel UBSAN: Undefined behaviour in include/linux/hash.h:81:31 shift exponent 64 is too large for 64-bit type 'long long unsigned int' Call Trace: dump_stack+0x8e/0xd0 ubsan_epilogue+0x5/0x21 ldlm_export_lock_hash+0x49/0x4d [ptlrpc] cfs_hash_bd_from_key+0x88/0x2e0 [libcfs] 2) use a high bits unstead of low as it more accurate. HPe-bug-id: LUS-11925 Fixes: 239e8268 (LU-16518 misc: use fixed hash code) Signed-off-by: Alexey Lyashkov Change-Id: Ie1c531ad220f44e55fbf80674a49472fb6024252 Reviewed-on: https://review.whamcloud.com/c/fs/lustre-release/+/52611 Tested-by: jenkins Tested-by: Maloo Reviewed-by: James Simmons Reviewed-by: Oleg Drokin Reviewed-by: Timothy Day --- libcfs/include/libcfs/libcfs_hash.h | 21 +++++++++++---------- libcfs/libcfs/hash.c | 8 ++++---- lustre/ldlm/ldlm_flock.c | 7 ++++--- lustre/ldlm/ldlm_lockd.c | 5 +++-- lustre/mdt/mdt_hsm_cdt_actions.c | 5 +++-- lustre/mdt/mdt_hsm_cdt_requests.c | 5 +++-- lustre/obdclass/jobid.c | 6 +++--- lustre/obdclass/lprocfs_jobstats.c | 6 +++--- lustre/obdclass/obd_config.c | 13 +++++++------ lustre/ptlrpc/nodemap_handler.c | 7 ++++--- lustre/ptlrpc/nrs_tbf.c | 36 +++++++++++++++++++++--------------- lustre/quota/lquota_entry.c | 4 ++-- 12 files changed, 68 insertions(+), 55 deletions(-) diff --git a/libcfs/include/libcfs/libcfs_hash.h b/libcfs/include/libcfs/libcfs_hash.h index b10ad5a..64feebf 100644 --- a/libcfs/include/libcfs/libcfs_hash.h +++ b/libcfs/include/libcfs/libcfs_hash.h @@ -280,7 +280,8 @@ struct cfs_hash_hlist_ops { struct cfs_hash_ops { /** return hashed value from @key */ - unsigned (*hs_hash)(struct cfs_hash *hs, const void *key, unsigned mask); + unsigned int (*hs_hash)(struct cfs_hash *hs, const void *key, + const unsigned int bits); /** return key address of @hnode */ void * (*hs_key)(struct hlist_node *hnode); /** copy key from @hnode to @key */ @@ -443,10 +444,10 @@ cfs_hash_bkt_size(struct cfs_hash *hs) hs->hs_extra_bytes; } -static inline unsigned -cfs_hash_id(struct cfs_hash *hs, const void *key, unsigned mask) +static inline unsigned int +cfs_hash_id(struct cfs_hash *hs, const void *key, const unsigned int bits) { - return hs->hs_ops->hs_hash(hs, key, mask); + return hs->hs_ops->hs_hash(hs, key, bits); } static inline void * @@ -803,16 +804,16 @@ void cfs_hash_debug_str(struct cfs_hash *hs, struct seq_file *m); * Generic djb2 hash algorithm for character arrays. */ static inline unsigned -cfs_hash_djb2_hash(const void *key, size_t size, unsigned mask) +cfs_hash_djb2_hash(const void *key, size_t size, const unsigned int bits) { - unsigned i, hash = 5381; + unsigned int i, hash = 5381; - LASSERT(key != NULL); + LASSERT(key != NULL); - for (i = 0; i < size; i++) - hash = hash * 33 + ((char *)key)[i]; + for (i = 0; i < size; i++) + hash = hash * 33 + ((char *)key)[i]; - return (hash & mask); + return (hash & ((1U << bits) - 1)); } /** iterate over all buckets in @bds (array of struct cfs_hash_bd) */ diff --git a/libcfs/libcfs/hash.c b/libcfs/libcfs/hash.c index f191e53..972baef 100644 --- a/libcfs/libcfs/hash.c +++ b/libcfs/libcfs/hash.c @@ -519,12 +519,12 @@ static void cfs_hash_bd_from_key(struct cfs_hash *hs, struct cfs_hash_bucket **bkts, unsigned int bits, const void *key, struct cfs_hash_bd *bd) { - unsigned int index = cfs_hash_id(hs, key, (1U << bits) - 1); + unsigned int index = cfs_hash_id(hs, key, bits); - LASSERT(bits == hs->hs_cur_bits || bits == hs->hs_rehash_bits); + LASSERT(bits == hs->hs_cur_bits || bits == hs->hs_rehash_bits); - bd->bd_bucket = bkts[index & ((1U << (bits - hs->hs_bkt_bits)) - 1)]; - bd->bd_offset = index >> (bits - hs->hs_bkt_bits); + bd->bd_bucket = bkts[index & ((1U << (bits - hs->hs_bkt_bits)) - 1)]; + bd->bd_offset = index >> (bits - hs->hs_bkt_bits); } void diff --git a/lustre/ldlm/ldlm_flock.c b/lustre/ldlm/ldlm_flock.c index 8eee9ff..c2da61a 100644 --- a/lustre/ldlm/ldlm_flock.c +++ b/lustre/ldlm/ldlm_flock.c @@ -853,10 +853,11 @@ void ldlm_flock_policy_local_to_wire(const union ldlm_policy_data *lpolicy, /* * Export handle<->flock hash operations. */ -static unsigned -ldlm_export_flock_hash(struct cfs_hash *hs, const void *key, unsigned mask) +static unsigned int +ldlm_export_flock_hash(struct cfs_hash *hs, const void *key, + const unsigned int bits) { - return cfs_hash_64(*(__u64 *)key, 0) & mask; + return cfs_hash_64(*(__u64 *)key, bits); } static void * diff --git a/lustre/ldlm/ldlm_lockd.c b/lustre/ldlm/ldlm_lockd.c index e76e04a..8651412 100644 --- a/lustre/ldlm/ldlm_lockd.c +++ b/lustre/ldlm/ldlm_lockd.c @@ -3120,9 +3120,10 @@ void ldlm_put_ref(void) * Export handle<->lock hash operations. */ static unsigned -ldlm_export_lock_hash(struct cfs_hash *hs, const void *key, unsigned int mask) +ldlm_export_lock_hash(struct cfs_hash *hs, const void *key, + const unsigned int bits) { - return cfs_hash_64(((struct lustre_handle *)key)->cookie, 0) & mask; + return cfs_hash_64(((struct lustre_handle *)key)->cookie, bits); } static void * diff --git a/lustre/mdt/mdt_hsm_cdt_actions.c b/lustre/mdt/mdt_hsm_cdt_actions.c index 4cf0f11..c50ccee 100644 --- a/lustre/mdt/mdt_hsm_cdt_actions.c +++ b/lustre/mdt/mdt_hsm_cdt_actions.c @@ -73,9 +73,10 @@ static inline void cdt_agent_record_loc_put(struct cdt_agent_record_loc *carl) } static unsigned int -cdt_agent_record_hash(struct cfs_hash *hs, const void *key, unsigned int mask) +cdt_agent_record_hash(struct cfs_hash *hs, const void *key, + const unsigned int bits) { - return cfs_hash_djb2_hash(key, sizeof(u64), mask); + return cfs_hash_djb2_hash(key, sizeof(u64), bits); } static void *cdt_agent_record_object(struct hlist_node *hnode) diff --git a/lustre/mdt/mdt_hsm_cdt_requests.c b/lustre/mdt/mdt_hsm_cdt_requests.c index 66b8191..7c7880f 100644 --- a/lustre/mdt/mdt_hsm_cdt_requests.c +++ b/lustre/mdt/mdt_hsm_cdt_requests.c @@ -44,9 +44,10 @@ #include "mdt_internal.h" static unsigned int -cdt_request_cookie_hash(struct cfs_hash *hs, const void *key, unsigned int mask) +cdt_request_cookie_hash(struct cfs_hash *hs, const void *key, + const unsigned int bits) { - return cfs_hash_djb2_hash(key, sizeof(u64), mask); + return cfs_hash_djb2_hash(key, sizeof(u64), bits); } static void *cdt_request_cookie_object(struct hlist_node *hnode) diff --git a/lustre/obdclass/jobid.c b/lustre/obdclass/jobid.c index 1fccfdd..422d85c 100644 --- a/lustre/obdclass/jobid.c +++ b/lustre/obdclass/jobid.c @@ -807,10 +807,10 @@ EXPORT_SYMBOL(jobid_cache_fini); /* * Hash operations for pid<->jobid */ -static unsigned jobid_hashfn(struct cfs_hash *hs, const void *key, - unsigned mask) +static unsigned int +jobid_hashfn(struct cfs_hash *hs, const void *key, const unsigned int bits) { - return cfs_hash_djb2_hash(key, sizeof(pid_t), mask); + return cfs_hash_djb2_hash(key, sizeof(pid_t), bits); } static void *jobid_key(struct hlist_node *hnode) diff --git a/lustre/obdclass/lprocfs_jobstats.c b/lustre/obdclass/lprocfs_jobstats.c index 870f0d8..2d40d14 100644 --- a/lustre/obdclass/lprocfs_jobstats.c +++ b/lustre/obdclass/lprocfs_jobstats.c @@ -73,10 +73,10 @@ struct job_stat { struct rcu_head js_rcu; /* RCU head for job_reclaim_rcu*/ }; -static unsigned -job_stat_hash(struct cfs_hash *hs, const void *key, unsigned mask) +static unsigned int +job_stat_hash(struct cfs_hash *hs, const void *key, const unsigned int bits) { - return cfs_hash_djb2_hash(key, strlen(key), mask); + return cfs_hash_djb2_hash(key, strlen(key), bits); } static void *job_stat_key(struct hlist_node *hnode) diff --git a/lustre/obdclass/obd_config.c b/lustre/obdclass/obd_config.c index eec745f..d6dbf85 100644 --- a/lustre/obdclass/obd_config.c +++ b/lustre/obdclass/obd_config.c @@ -2373,10 +2373,10 @@ EXPORT_SYMBOL(class_manual_cleanup); /* * nid<->nidstats hash operations */ -static unsigned -nidstats_hash(struct cfs_hash *hs, const void *key, unsigned int mask) +static unsigned int +nidstats_hash(struct cfs_hash *hs, const void *key, const unsigned int bits) { - return cfs_hash_djb2_hash(key, sizeof(struct lnet_nid), mask); + return cfs_hash_djb2_hash(key, sizeof(struct lnet_nid), bits); } static void * @@ -2433,10 +2433,11 @@ static struct cfs_hash_ops nid_stat_hash_ops = { * client_generation<->export hash operations */ -static unsigned -gen_hash(struct cfs_hash *hs, const void *key, unsigned mask) +static unsigned int +gen_hash(struct cfs_hash *hs, const void *key, const unsigned int bits) { - return cfs_hash_djb2_hash(key, sizeof(__u32), mask); + /* XXX did hash needs ? */ + return cfs_hash_djb2_hash(key, sizeof(__u32), bits); } static void * diff --git a/lustre/ptlrpc/nodemap_handler.c b/lustre/ptlrpc/nodemap_handler.c index 97ea82d..10fc259 100644 --- a/lustre/ptlrpc/nodemap_handler.c +++ b/lustre/ptlrpc/nodemap_handler.c @@ -118,10 +118,11 @@ void nodemap_putref(struct lu_nodemap *nodemap) } EXPORT_SYMBOL(nodemap_putref); -static __u32 nodemap_hashfn(struct cfs_hash *hash_body, - const void *key, unsigned mask) +static unsigned int +nodemap_hashfn(struct cfs_hash *hash_body, + const void *key, const unsigned int bits) { - return cfs_hash_djb2_hash(key, strlen(key), mask); + return cfs_hash_djb2_hash(key, strlen(key), bits); } static void *nodemap_hs_key(struct hlist_node *hnode) diff --git a/lustre/ptlrpc/nrs_tbf.c b/lustre/ptlrpc/nrs_tbf.c index e4a9875..43fa946 100644 --- a/lustre/ptlrpc/nrs_tbf.c +++ b/lustre/ptlrpc/nrs_tbf.c @@ -544,10 +544,11 @@ static struct binheap_ops nrs_tbf_heap_ops = { .hop_compare = tbf_cli_compare, }; -static unsigned nrs_tbf_jobid_hop_hash(struct cfs_hash *hs, const void *key, - unsigned mask) +static unsigned int +nrs_tbf_jobid_hop_hash(struct cfs_hash *hs, const void *key, + const unsigned int bits) { - return cfs_hash_djb2_hash(key, strlen(key), mask); + return cfs_hash_djb2_hash(key, strlen(key), bits); } static int nrs_tbf_jobid_hop_keycmp(const void *key, struct hlist_node *hnode) @@ -1043,10 +1044,11 @@ static struct nrs_tbf_ops nrs_tbf_jobid_ops = { #define NRS_TBF_NID_BKT_BITS 8 #define NRS_TBF_NID_BITS 16 -static unsigned nrs_tbf_nid_hop_hash(struct cfs_hash *hs, const void *key, - unsigned mask) +static unsigned int +nrs_tbf_nid_hop_hash(struct cfs_hash *hs, const void *key, + const unsigned int bits) { - return cfs_hash_djb2_hash(key, sizeof(lnet_nid_t), mask); + return cfs_hash_djb2_hash(key, sizeof(lnet_nid_t), bits); } static int nrs_tbf_nid_hop_keycmp(const void *key, struct hlist_node *hnode) @@ -1273,10 +1275,11 @@ static struct nrs_tbf_ops nrs_tbf_nid_ops = { .o_rule_fini = nrs_tbf_nid_rule_fini, }; -static unsigned nrs_tbf_hop_hash(struct cfs_hash *hs, const void *key, - unsigned mask) +static unsigned int +nrs_tbf_hop_hash(struct cfs_hash *hs, const void *key, + const unsigned int bits) { - return cfs_hash_djb2_hash(key, strlen(key), mask); + return cfs_hash_djb2_hash(key, strlen(key), bits); } static int nrs_tbf_hop_keycmp(const void *key, struct hlist_node *hnode) @@ -2079,10 +2082,12 @@ static void nrs_tbf_opcode_rule_fini(struct nrs_tbf_rule *rule) OBD_FREE(rule->tr_opcodes_str, strlen(rule->tr_opcodes_str) + 1); } -static unsigned nrs_tbf_opcode_hop_hash(struct cfs_hash *hs, const void *key, - unsigned mask) +static unsigned int +nrs_tbf_opcode_hop_hash(struct cfs_hash *hs, const void *key, + const unsigned int bits) { - return cfs_hash_djb2_hash(key, sizeof(__u32), mask); + /* XXX did hash needs ? */ + return cfs_hash_djb2_hash(key, sizeof(__u32), bits); } static int nrs_tbf_opcode_hop_keycmp(const void *key, struct hlist_node *hnode) @@ -2345,10 +2350,11 @@ struct nrs_tbf_ops nrs_tbf_opcode_ops = { .o_rule_fini = nrs_tbf_opcode_rule_fini, }; -static unsigned nrs_tbf_id_hop_hash(struct cfs_hash *hs, const void *key, - unsigned mask) +static unsigned int +nrs_tbf_id_hop_hash(struct cfs_hash *hs, const void *key, + const unsigned int bits) { - return cfs_hash_djb2_hash(key, sizeof(struct tbf_id), mask); + return cfs_hash_djb2_hash(key, sizeof(struct tbf_id), bits); } static int nrs_tbf_id_hop_keycmp(const void *key, struct hlist_node *hnode) diff --git a/lustre/quota/lquota_entry.c b/lustre/quota/lquota_entry.c index 54b5966..e1e55c7 100644 --- a/lustre/quota/lquota_entry.c +++ b/lustre/quota/lquota_entry.c @@ -39,9 +39,9 @@ module_param(hash_lqs_cur_bits, int, 0444); 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) +lqe64_hash_hash(struct cfs_hash *hs, const void *key, const unsigned int bits) { - return cfs_hash_64(*((__u64 *)key), 0) & mask; + return cfs_hash_64(*((__u64 *)key), bits); } static void *lqe64_hash_key(struct hlist_node *hnode) -- 1.8.3.1