1 /* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*-
2 * vim:expandtab:shiftwidth=8:tabstop=8:
6 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License version 2 only,
10 * as published by the Free Software Foundation.
12 * This program is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * General Public License version 2 for more details (a copy is included
16 * in the LICENSE file that accompanied this code).
18 * You should have received a copy of the GNU General Public License
19 * version 2 along with this program; If not, see
20 * http://www.sun.com/software/products/lustre/docs/GPLv2.pdf
22 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
23 * CA 95054 USA or visit www.sun.com if you need additional information or
29 * Copyright (c) 2007, 2010, Oracle and/or its affiliates. All rights reserved.
30 * Use is subject to license terms.
33 * This file is part of Lustre, http://www.lustre.org/
34 * Lustre is a trademark of Sun Microsystems, Inc.
37 #ifndef __CLASS_HASH_H
38 #define __CLASS_HASH_H
40 #include <lustre_lib.h>
42 struct lustre_hash_ops;
44 typedef struct lustre_hash_bucket {
45 struct hlist_head lhb_head; /* entries list */
46 atomic_t lhb_count; /* current entries */
47 rwlock_t lhb_rwlock; /* lustre_hash_bucket */
48 } lustre_hash_bucket_t;
50 #define LUSTRE_MAX_HASH_NAME 16
52 typedef struct lustre_hash {
53 int lh_cur_bits; /* current hash bits */
54 int lh_cur_mask; /* current hash mask */
55 int lh_min_bits; /* min hash bits */
56 int lh_max_bits; /* max hash bits */
57 int lh_min_theta; /* resize min threshold */
58 int lh_max_theta; /* resize max threshold */
59 int lh_flags; /* hash flags */
60 atomic_t lh_count; /* current entries */
61 atomic_t lh_rehash_count;/* resize count */
62 struct lustre_hash_bucket **lh_buckets; /* hash buckets */
63 struct lustre_hash_ops *lh_ops; /* hash operations */
64 rwlock_t lh_rwlock; /* lustre_hash */
65 char lh_name[LUSTRE_MAX_HASH_NAME];
68 typedef struct lustre_hash_ops {
69 unsigned (*lh_hash)(lustre_hash_t *lh, void *key, unsigned mask);
70 void * (*lh_key)(struct hlist_node *hnode);
71 int (*lh_compare)(void *key, struct hlist_node *hnode);
72 void * (*lh_get)(struct hlist_node *hnode);
73 void * (*lh_put)(struct hlist_node *hnode);
74 void (*lh_exit)(struct hlist_node *hnode);
77 #define LH_DEBUG 0x0001 /* Enable expensive debug checks */
78 #define LH_REHASH 0x0002 /* Enable dynamic hash resizing */
80 #define LHO(lh) (lh)->lh_ops
81 #define LHP(lh, op) (lh)->lh_ops->lh_ ## op
83 static inline unsigned
84 lh_hash(lustre_hash_t *lh, void *key, unsigned mask)
88 LASSERT(LHP(lh, hash));
90 return LHP(lh, hash)(lh, key, mask);
94 lh_key(lustre_hash_t *lh, struct hlist_node *hnode)
99 LASSERT(LHP(lh, key));
101 return LHP(lh, key)(hnode);
104 /* Returns 1 on a match,
105 * XXX: This would be better if it returned, -1, 0, or 1 for
106 * <, =, > respectivly. It could then be used to implement
107 * a LH_SORT feature flags which could keep each lustre hash
108 * bucket in order. This would increase insertion times
109 * but could reduce lookup times for deep chains. Ideally,
110 * the rehash should keep chain depth short but if that
111 * ends up not being the case this would be a nice feature.
114 lh_compare(lustre_hash_t *lh, void *key, struct hlist_node *hnode)
120 if (LHP(lh, compare))
121 return LHP(lh, compare)(key, hnode);
127 lh_get(lustre_hash_t *lh, struct hlist_node *hnode)
134 return LHP(lh, get)(hnode);
140 lh_put(lustre_hash_t *lh, struct hlist_node *hnode)
147 return LHP(lh, put)(hnode);
153 lh_exit(lustre_hash_t *lh, struct hlist_node *hnode)
160 LHP(lh, exit)(hnode);
163 /* Validate hnode references the correct key */
165 __lustre_hash_key_validate(lustre_hash_t *lh, void *key,
166 struct hlist_node *hnode)
168 if (unlikely(lh->lh_flags & LH_DEBUG))
169 LASSERT(lh_compare(lh, key, hnode));
172 /* Validate hnode is in the correct bucket */
174 __lustre_hash_bucket_validate(lustre_hash_t *lh, lustre_hash_bucket_t *lhb,
175 struct hlist_node *hnode)
179 if (unlikely(lh->lh_flags & LH_DEBUG)) {
180 i = lh_hash(lh, lh_key(lh, hnode), lh->lh_cur_mask);
181 LASSERT(lh->lh_buckets[i] == lhb);
185 static inline struct hlist_node *
186 __lustre_hash_bucket_lookup(lustre_hash_t *lh,
187 lustre_hash_bucket_t *lhb, void *key)
189 struct hlist_node *hnode;
191 hlist_for_each(hnode, &lhb->lhb_head)
192 if (lh_compare(lh, key, hnode))
199 __lustre_hash_bucket_add(lustre_hash_t *lh,
200 lustre_hash_bucket_t *lhb,
201 struct hlist_node *hnode)
203 hlist_add_head(hnode, &(lhb->lhb_head));
204 atomic_inc(&lhb->lhb_count);
205 atomic_inc(&lh->lh_count);
207 return lh_get(lh, hnode);
211 __lustre_hash_bucket_del(lustre_hash_t *lh,
212 lustre_hash_bucket_t *lhb,
213 struct hlist_node *hnode)
215 hlist_del_init(hnode);
216 LASSERT(atomic_read(&lhb->lhb_count) > 0);
217 atomic_dec(&lhb->lhb_count);
218 LASSERT(atomic_read(&lh->lh_count) > 0);
219 atomic_dec(&lh->lh_count);
221 return lh_put(lh, hnode);
224 /* Some hash init argument constants */
225 #define HASH_POOLS_CUR_BITS 3
226 #define HASH_POOLS_MAX_BITS 7
227 #define HASH_UUID_CUR_BITS 7
228 #define HASH_UUID_MAX_BITS 12
229 #define HASH_NID_CUR_BITS 7
230 #define HASH_NID_MAX_BITS 12
231 #define HASH_NID_STATS_CUR_BITS 7
232 #define HASH_NID_STATS_MAX_BITS 12
233 #define HASH_LQS_CUR_BITS 7
234 #define HASH_LQS_MAX_BITS 12
235 #define HASH_CONN_CUR_BITS 5
236 #define HASH_CONN_MAX_BITS 15
238 /* Hash init/cleanup functions */
239 lustre_hash_t *lustre_hash_init(char *name, unsigned int cur_bits,
240 unsigned int max_bits,
241 lustre_hash_ops_t *ops, int flags);
242 void lustre_hash_exit(lustre_hash_t *lh);
244 /* Hash addition functions */
245 void lustre_hash_add(lustre_hash_t *lh, void *key,
246 struct hlist_node *hnode);
247 int lustre_hash_add_unique(lustre_hash_t *lh, void *key,
248 struct hlist_node *hnode);
249 void *lustre_hash_findadd_unique(lustre_hash_t *lh, void *key,
250 struct hlist_node *hnode);
252 /* Hash deletion functions */
253 void *lustre_hash_del(lustre_hash_t *lh, void *key, struct hlist_node *hnode);
254 void *lustre_hash_del_key(lustre_hash_t *lh, void *key);
255 typedef int (*lh_cond_opt_cb)(void *obj, void *data);
256 void lustre_hash_cond_del(lustre_hash_t *lh, lh_cond_opt_cb, void *data);
258 /* Hash lookup/for_each functions */
259 void *lustre_hash_lookup(lustre_hash_t *lh, void *key);
260 typedef void (*lh_for_each_cb)(void *obj, void *data);
261 void lustre_hash_for_each(lustre_hash_t *lh, lh_for_each_cb, void *data);
262 void lustre_hash_for_each_safe(lustre_hash_t *lh, lh_for_each_cb, void *data);
263 void lustre_hash_for_each_empty(lustre_hash_t *lh, lh_for_each_cb, void *data);
264 void lustre_hash_for_each_key(lustre_hash_t *lh, void *key,
265 lh_for_each_cb, void *data);
268 * Rehash - Theta is calculated to be the average chained
269 * hash depth assuming a perfectly uniform hash funcion.
271 int lustre_hash_rehash(lustre_hash_t *lh, int bits);
272 void lustre_hash_rehash_key(lustre_hash_t *lh, void *old_key,
273 void *new_key, struct hlist_node *hnode);
276 #define LH_THETA_BITS 10
278 /* Return integer component of theta */
279 static inline int __lustre_hash_theta_int(int theta)
281 return (theta >> LH_THETA_BITS);
284 /* Return a fractional value between 0 and 999 */
285 static inline int __lustre_hash_theta_frac(int theta)
287 return ((theta * 1000) >> LH_THETA_BITS) -
288 (__lustre_hash_theta_int(theta) * 1000);
291 static inline int __lustre_hash_theta(lustre_hash_t *lh)
293 return (atomic_read(&lh->lh_count) << LH_THETA_BITS) >> lh->lh_cur_bits;
296 static inline void __lustre_hash_set_theta(lustre_hash_t *lh, int min, int max)
299 lh->lh_min_theta = min;
300 lh->lh_max_theta = max;
303 /* Generic debug formatting routines mainly for proc handler */
304 int lustre_hash_debug_header(char *str, int size);
305 int lustre_hash_debug_str(lustre_hash_t *lh, char *str, int size);
307 /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
308 #define CFS_GOLDEN_RATIO_PRIME_32 0x9e370001UL
309 /* 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
310 #define CFS_GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001ULL
313 * Generic djb2 hash algorithm for character arrays.
315 static inline unsigned
316 lh_djb2_hash(void *key, size_t size, unsigned mask)
318 unsigned i, hash = 5381;
320 LASSERT(key != NULL);
322 for (i = 0; i < size; i++)
323 hash = hash * 33 + ((char *)key)[i];
325 return (hash & mask);
329 * Generic u32 hash algorithm.
331 static inline unsigned
332 lh_u32_hash(__u32 key, unsigned mask)
334 return ((key * CFS_GOLDEN_RATIO_PRIME_32) & mask);
338 * Generic u64 hash algorithm.
340 static inline unsigned
341 lh_u64_hash(__u64 key, unsigned mask)
343 return ((unsigned)(key * CFS_GOLDEN_RATIO_PRIME_64) & mask);
346 #define lh_for_each_bucket(lh, lhb, pos) \
348 pos <= lh->lh_cur_mask && \
349 (lhb = lh->lh_buckets[pos]); \
352 #define lh_for_each_bucket_restart(lh, lhb, pos) \
353 for (/* pos=0 done once by caller */; \
354 pos <= lh->lh_cur_mask && \
355 (lhb = lh->lh_buckets[pos]); \
358 #endif /* __CLASS_HASH_H */