X-Git-Url: https://git.whamcloud.com/?a=blobdiff_plain;f=lustre%2Finclude%2Fclass_hash.h;h=613060dee0dc5ee564aefe044c1c0e28a44d87c7;hb=577e7fc5c4e1795edddb1e9c33ec16d1b0b46f24;hp=70349cb09226a892bc1ab652baec15715a6f2545;hpb=cb84e877a145717c060d6f4813862ab537858592;p=fs%2Flustre-release.git diff --git a/lustre/include/class_hash.h b/lustre/include/class_hash.h index 70349cb..613060d 100644 --- a/lustre/include/class_hash.h +++ b/lustre/include/class_hash.h @@ -50,9 +50,10 @@ typedef struct lustre_hash_bucket { #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 */ @@ -84,11 +85,9 @@ lh_hash(lustre_hash_t *lh, void *key, unsigned mask) { 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 * @@ -104,8 +103,7 @@ lh_key(lustre_hash_t *lh, struct hlist_node *hnode) return NULL; } -/** - * 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 @@ -164,20 +162,16 @@ lh_exit(lustre_hash_t *lh, struct hlist_node *hnode) 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) { if (unlikely(lh->lh_flags & LH_DEBUG)) - LASSERT(lh_compare(lh, key, hnode)); + LASSERT(lh_compare(lh, key, hnode) > 0); } -/** - * 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) @@ -185,7 +179,7 @@ __lustre_hash_bucket_validate(lustre_hash_t *lh, lustre_hash_bucket_t *lhb, unsigned i; if (unlikely(lh->lh_flags & LH_DEBUG)) { - i = lh_hash(lh, lh_key(lh, hnode), lh->lh_cur_size - 1); + i = lh_hash(lh, lh_key(lh, hnode), lh->lh_cur_mask); LASSERT(&lh->lh_buckets[i] == lhb); } } @@ -197,7 +191,7 @@ __lustre_hash_bucket_lookup(lustre_hash_t *lh, struct hlist_node *hnode; hlist_for_each(hnode, &lhb->lhb_head) - if (lh_compare(lh, key, hnode)) + if (lh_compare(lh, key, hnode) > 0) return hnode; return NULL; @@ -229,33 +223,39 @@ __lustre_hash_bucket_del(lustre_hash_t *lh, 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, - struct hlist_node *hnode); +int lustre_hash_add_unique(lustre_hash_t *lh, void *key, + struct hlist_node *hnode); 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); -/* - * 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); @@ -264,45 +264,52 @@ void lustre_hash_for_each_empty(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_min_theta = max; + 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 @@ -318,7 +325,7 @@ lh_djb2_hash(void *key, size_t size, unsigned mask) return (hash & mask); } -/** +/* * Generic u32 hash algorithm. */ static inline unsigned @@ -327,7 +334,7 @@ lh_u32_hash(__u32 key, unsigned mask) return ((key * CFS_GOLDEN_RATIO_PRIME_32) & mask); } -/** +/* * Generic u64 hash algorithm. */ static inline unsigned @@ -338,7 +345,7 @@ lh_u64_hash(__u64 key, unsigned mask) #define lh_for_each_bucket(lh, lhb, pos) \ for (pos = 0; \ - pos < lh->lh_cur_size && \ + pos <= lh->lh_cur_mask && \ ({ lhb = &lh->lh_buckets[i]; 1; }); \ pos++)