From 23d5254c8d607a0ae1065853011ecfc82f0543a2 Mon Sep 17 00:00:00 2001 From: Liang Zhen Date: Tue, 29 Mar 2011 16:44:41 +0800 Subject: [PATCH] LU-143 fid hash improvements Current hash function of fid is not good enough for lu_site and ldlm_namespace. We have to use two totally different hash functions to hash fid into hash table with millions of entries. Change-Id: I6261e63a406118a93d578210c31e67fc7f9e389c Signed-off-by: Liang Zhen Reviewed-on: http://review.whamcloud.com/374 Tested-by: Hudson Tested-by: Maloo Reviewed-by: Fan Yong Reviewed-by: Oleg Drokin --- libcfs/libcfs/hash.c | 2 +- lustre/ldlm/ldlm_resource.c | 22 ++++++++++++++-------- lustre/obdclass/lu_object.c | 24 +++++++++++++++++------- 3 files changed, 32 insertions(+), 16 deletions(-) diff --git a/libcfs/libcfs/hash.c b/libcfs/libcfs/hash.c index db30f8c..2c6df47 100644 --- a/libcfs/libcfs/hash.c +++ b/libcfs/libcfs/hash.c @@ -110,7 +110,7 @@ #include #if CFS_HASH_DEBUG_LEVEL >= CFS_HASH_DEBUG_1 -static unsigned int warn_on_depth = 0; +static unsigned int warn_on_depth = 8; CFS_MODULE_PARM(warn_on_depth, "i", uint, 0644, "warning when hash depth is high."); #endif diff --git a/lustre/ldlm/ldlm_resource.c b/lustre/ldlm/ldlm_resource.c index 99e77dd..eb28062 100644 --- a/lustre/ldlm/ldlm_resource.c +++ b/lustre/ldlm/ldlm_resource.c @@ -400,19 +400,25 @@ static unsigned ldlm_res_hop_fid_hash(cfs_hash_t *hs, { const struct ldlm_res_id *id = key; struct lu_fid fid; - __u64 hash; + __u32 hash; + __u32 val; fid.f_seq = id->name[LUSTRE_RES_ID_SEQ_OFF]; fid.f_oid = (__u32)id->name[LUSTRE_RES_ID_OID_OFF]; fid.f_ver = (__u32)id->name[LUSTRE_RES_ID_VER_OFF]; - hash = fid_flatten(&fid); + hash = fid_flatten32(&fid); + hash += (hash >> 4) + (hash << 12); /* mixing oid and seq */ + if (id->name[LUSTRE_RES_ID_HSH_OFF] != 0) { + val = id->name[LUSTRE_RES_ID_HSH_OFF]; + hash += (val >> 5) + (val << 11); + } else { + val = fid_oid(&fid); + } hash = cfs_hash_long(hash, hs->hs_bkt_bits); - /* ignore a few low bits */ - if (id->name[LUSTRE_RES_ID_HSH_OFF] != 0) - hash += id->name[LUSTRE_RES_ID_HSH_OFF] >> 5; - else - hash = hash >> 5; + /* give me another random factor */ + hash -= cfs_hash_long((unsigned long)hs, val % 11 + 3); + hash <<= hs->hs_cur_bits - hs->hs_bkt_bits; hash |= ldlm_res_hop_hash(hs, key, CFS_HASH_NBKT(hs) - 1); @@ -506,7 +512,7 @@ ldlm_ns_hash_def_t ldlm_ns_hash_defs[] = { .nsd_type = LDLM_NS_TYPE_MDC, .nsd_bkt_bits = 11, - .nsd_all_bits = 15, + .nsd_all_bits = 16, .nsd_hops = &ldlm_ns_fid_hash_ops, }, { diff --git a/lustre/obdclass/lu_object.c b/lustre/obdclass/lu_object.c index c5e4c29..7768ec6 100644 --- a/lustre/obdclass/lu_object.c +++ b/lustre/obdclass/lu_object.c @@ -829,10 +829,18 @@ static unsigned lu_obj_hop_hash(cfs_hash_t *hs, const void *key, unsigned mask) { struct lu_fid *fid = (struct lu_fid *)key; - unsigned hash; + __u32 hash; + + hash = fid_flatten32(fid); + hash += (hash >> 4) + (hash << 12); /* mixing oid and seq */ + hash = cfs_hash_long(hash, hs->hs_bkt_bits); + + /* give me another random factor */ + hash -= cfs_hash_long((unsigned long)hs, fid_oid(fid) % 11 + 3); + + hash <<= hs->hs_cur_bits - hs->hs_bkt_bits; + hash |= (fid_seq(fid) + fid_oid(fid)) & (CFS_HASH_NBKT(hs) - 1); - hash = (fid_seq(fid) + fid_oid(fid)) & (CFS_HASH_NBKT(hs) - 1); - hash += fid_hash(fid, hs->hs_bkt_bits) << hs->hs_bkt_bits; return hash & mask; } @@ -890,27 +898,29 @@ cfs_hash_ops_t lu_site_hash_ops = { * Initialize site \a s, with \a d as the top level device. */ #define LU_SITE_BITS_MIN 12 -#define LU_SITE_BITS_MAX 23 +#define LU_SITE_BITS_MAX 24 /** - * total 128 buckets, we don't want too many buckets because: + * total 256 buckets, we don't want too many buckets because: * - consume too much memory * - avoid unbalanced LRU list */ -#define LU_SITE_BKT_BITS 7 +#define LU_SITE_BKT_BITS 8 int lu_site_init(struct lu_site *s, struct lu_device *top) { struct lu_site_bkt_data *bkt; cfs_hash_bd_t bd; + char name[16]; int bits; int i; ENTRY; memset(s, 0, sizeof *s); bits = lu_htable_order(); + snprintf(name, 16, "lu_site_%s", top->ld_type->ldt_name); for (bits = min(max(LU_SITE_BITS_MIN, bits), LU_SITE_BITS_MAX); bits >= LU_SITE_BITS_MIN; bits--) { - s->ls_obj_hash = cfs_hash_create("lu_site", bits, bits, + s->ls_obj_hash = cfs_hash_create(name, bits, bits, bits - LU_SITE_BKT_BITS, sizeof(*bkt), 0, 0, &lu_site_hash_ops, -- 1.8.3.1