#define LUSTRE_MAX_HASH_NAME 16
typedef struct lustre_hash {
- int lh_cur_size; /* current hash size */
- int lh_min_size; /* min hash size */
- int lh_max_size; /* max hash size */
+ int lh_cur_bits; /* current hash bits */
+ int lh_cur_mask; /* current hash mask */
+ int lh_min_bits; /* min hash bits */
+ int lh_max_bits; /* max hash bits */
int lh_min_theta; /* resize min threshold */
int lh_max_theta; /* resize max threshold */
int lh_flags; /* hash flags */
atomic_t lh_count; /* current entries */
atomic_t lh_rehash_count;/* resize count */
- struct lustre_hash_bucket *lh_buckets; /* hash buckets */
+ struct lustre_hash_bucket **lh_buckets; /* hash buckets */
struct lustre_hash_ops *lh_ops; /* hash operations */
rwlock_t lh_rwlock; /* lustre_hash */
char lh_name[LUSTRE_MAX_HASH_NAME];
{
LASSERT(lh);
LASSERT(LHO(lh));
+ LASSERT(LHP(lh, hash));
- if (LHP(lh, hash))
- return LHP(lh, hash)(lh, key, mask);
-
- return -EOPNOTSUPP;
+ return LHP(lh, hash)(lh, key, mask);
}
static inline void *
LASSERT(lh);
LASSERT(hnode);
LASSERT(LHO(lh));
+ LASSERT(LHP(lh, key));
- if (LHP(lh, key))
- return LHP(lh, key)(hnode);
-
- return NULL;
+ return LHP(lh, key)(hnode);
}
-/**
- * Returns 1 on a match,
+/* Returns 1 on a match,
* XXX: This would be better if it returned, -1, 0, or 1 for
* <, =, > respectivly. It could then be used to implement
* a LH_SORT feature flags which could keep each lustre hash
return LHP(lh, exit)(hnode);
}
-/**
- * Validate hnode references the correct key.
- */
+/* Validate hnode references the correct key */
static inline void
__lustre_hash_key_validate(lustre_hash_t *lh, void *key,
struct hlist_node *hnode)
LASSERT(lh_compare(lh, key, hnode));
}
-/**
- * Validate hnode is in the correct bucket.
- */
+/* Validate hnode is in the correct bucket */
static inline void
__lustre_hash_bucket_validate(lustre_hash_t *lh, lustre_hash_bucket_t *lhb,
struct hlist_node *hnode)
unsigned i;
if (unlikely(lh->lh_flags & LH_DEBUG)) {
- i = lh_hash(lh, lh_key(lh, hnode), lh->lh_cur_size - 1);
- LASSERT(&lh->lh_buckets[i] == lhb);
+ i = lh_hash(lh, lh_key(lh, hnode), lh->lh_cur_mask);
+ LASSERT(lh->lh_buckets[i] == lhb);
}
}
return lh_put(lh, hnode);
}
-/*
- * Hash init/cleanup functions.
- */
-lustre_hash_t *lustre_hash_init(char *name, unsigned int cur_size,
- unsigned int max_size,
+/* Some hash init argument constants */
+#define HASH_POOLS_CUR_BITS 3
+#define HASH_POOLS_MAX_BITS 7
+#define HASH_UUID_CUR_BITS 7
+#define HASH_UUID_MAX_BITS 12
+#define HASH_NID_CUR_BITS 7
+#define HASH_NID_MAX_BITS 12
+#define HASH_NID_STATS_CUR_BITS 7
+#define HASH_NID_STATS_MAX_BITS 12
+#define HASH_LQS_CUR_BITS 7
+#define HASH_LQS_MAX_BITS 12
+#define HASH_CONN_CUR_BITS 5
+#define HASH_CONN_MAX_BITS 15
+
+/* Hash init/cleanup functions */
+lustre_hash_t *lustre_hash_init(char *name, unsigned int cur_bits,
+ unsigned int max_bits,
lustre_hash_ops_t *ops, int flags);
void lustre_hash_exit(lustre_hash_t *lh);
-/*
- * Hash addition functions.
- */
+/* Hash addition functions */
void lustre_hash_add(lustre_hash_t *lh, void *key,
struct hlist_node *hnode);
int lustre_hash_add_unique(lustre_hash_t *lh, void *key,
void *lustre_hash_findadd_unique(lustre_hash_t *lh, void *key,
struct hlist_node *hnode);
-/*
- * Hash deletion functions.
- */
+/* Hash deletion functions */
void *lustre_hash_del(lustre_hash_t *lh, void *key, struct hlist_node *hnode);
void *lustre_hash_del_key(lustre_hash_t *lh, void *key);
+typedef int (*lh_cond_opt_cb)(void *obj, void *data);
+void lustre_hash_cond_del(lustre_hash_t *lh, lh_cond_opt_cb, void *data);
-/*
- * Hash lookup/for_each functions.
- */
+/* Hash lookup/for_each functions */
void *lustre_hash_lookup(lustre_hash_t *lh, void *key);
typedef void (*lh_for_each_cb)(void *obj, void *data);
void lustre_hash_for_each(lustre_hash_t *lh, lh_for_each_cb, void *data);
void lustre_hash_for_each_key(lustre_hash_t *lh, void *key,
lh_for_each_cb, void *data);
-/*
+/*
* Rehash - Theta is calculated to be the average chained
- * hash depth assuming a perfectly uniform hash funcion.
+ * hash depth assuming a perfectly uniform hash funcion.
*/
-int lustre_hash_rehash(lustre_hash_t *lh, int size);
+int lustre_hash_rehash(lustre_hash_t *lh, int bits);
void lustre_hash_rehash_key(lustre_hash_t *lh, void *old_key,
void *new_key, struct hlist_node *hnode);
-static inline int
-__lustre_hash_theta(lustre_hash_t *lh)
+#define LH_THETA_BITS 10
+
+/* Return integer component of theta */
+static inline int __lustre_hash_theta_int(int theta)
{
- return ((atomic_read(&lh->lh_count) * 1000) / lh->lh_cur_size);
+ return (theta >> LH_THETA_BITS);
}
-static inline void
-__lustre_hash_set_theta(lustre_hash_t *lh, int min, int max)
+/* Return a fractional value between 0 and 999 */
+static inline int __lustre_hash_theta_frac(int theta)
+{
+ return ((theta * 1000) >> LH_THETA_BITS) -
+ (__lustre_hash_theta_int(theta) * 1000);
+}
+
+static inline int __lustre_hash_theta(lustre_hash_t *lh)
+{
+ return (atomic_read(&lh->lh_count) << LH_THETA_BITS) >> lh->lh_cur_bits;
+}
+
+static inline void __lustre_hash_set_theta(lustre_hash_t *lh, int min, int max)
{
LASSERT(min < max);
lh->lh_min_theta = min;
lh->lh_max_theta = max;
}
-/*
- * Generic debug formatting routines mainly for proc handler.
- */
+/* Generic debug formatting routines mainly for proc handler */
int lustre_hash_debug_header(char *str, int size);
int lustre_hash_debug_str(lustre_hash_t *lh, char *str, int size);
-/*
- * 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1
- */
+/* 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
- */
+/* 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
#define CFS_GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001ULL
-/**
+/*
* Generic djb2 hash algorithm for character arrays.
*/
static inline unsigned
return (hash & mask);
}
-/**
+/*
* Generic u32 hash algorithm.
*/
static inline unsigned
return ((key * CFS_GOLDEN_RATIO_PRIME_32) & mask);
}
-/**
+/*
* Generic u64 hash algorithm.
*/
static inline unsigned
#define lh_for_each_bucket(lh, lhb, pos) \
for (pos = 0; \
- pos < lh->lh_cur_size && \
- ({ lhb = &lh->lh_buckets[i]; 1; }); \
+ pos <= lh->lh_cur_mask && \
+ (lhb = lh->lh_buckets[pos]); \
+ pos++)
+
+#define lh_for_each_bucket_restart(lh, lhb, pos) \
+ for (/* pos=0 done once by caller */; \
+ pos <= lh->lh_cur_mask && \
+ (lhb = lh->lh_buckets[pos]); \
pos++)
#endif /* __CLASS_HASH_H */
git://git.whamcloud.com / fs / lustre-release.git / blobdiff