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 <liang@whamcloud.com>
Reviewed-on: http://review.whamcloud.com/374
Tested-by: Hudson
Tested-by: Maloo <whamcloud.maloo@gmail.com>
Reviewed-by: Fan Yong <yong.fan@whamcloud.com>
Reviewed-by: Oleg Drokin <green@whamcloud.com>

diff --git a/libcfs/libcfs/hash.c b/libcfs/libcfs/hash.c
index db30f8c..2c6df47 100644 (file)
--- a/libcfs/libcfs/hash.c
+++ b/libcfs/libcfs/hash.c
@@ -110,7 +110,7 @@
 #include <libcfs/libcfs.h>
 
 #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 (file)
--- 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 (file)
--- 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,