#ifndef __LIBCFS_HASH_H__
#define __LIBCFS_HASH_H__
-#include <linux/hash.h>
#include <linux/spinlock.h>
#include <linux/workqueue.h>
-
-/*
- * 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 <libcfs/linux/linux-hash.h>
/** disable debug */
#define CFS_HASH_DEBUG_NONE 0
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++)
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 */
/*
* The implementation of the wait_bit*() and related waiting APIs:
*/
-#include <linux/hash.h>
+#include <libcfs/linux/linux-hash.h>
#include <linux/sched.h>
#ifdef HAVE_SCHED_HEADERS
#include <linux/sched/signal.h>
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 *
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;
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];
}
}
{
/* 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);
}
/**
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 *
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 *
* 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;
#include <linux/list.h>
#include <linux/random.h>
#include <libcfs/libcfs.h>
-#include <libcfs/libcfs_hash.h> /* hash_long() */
#include <libcfs/linux/linux-mem.h>
#include <obd_class.h>
#include <obd_support.h>
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
#include <linux/module.h>
#include <linux/random.h>
#include <linux/slab.h>
-#include <linux/hash.h>
#include <linux/mutex.h>
#include <linux/sunrpc/cache.h>
#include <net/sock.h>
#include <lustre_net.h>
#include <lustre_nodemap.h>
#include <lustre_sec.h>
+#include <libcfs/linux/linux-hash.h>
#include "gss_err.h"
#include "gss_internal.h"
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);
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)
git://git.whamcloud.com / fs / lustre-release.git / commitdiff