Whamcloud - gitweb
b=16776
[fs/lustre-release.git] / lustre / include / class_hash.h
1 /* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*-
2  * vim:expandtab:shiftwidth=8:tabstop=8:
3  *
4  * GPL HEADER START
5  *
6  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
7  *
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.
11  *
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).
17  *
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
21  *
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
24  * have any questions.
25  *
26  * GPL HEADER END
27  */
28 /*
29  * Copyright  2008 Sun Microsystems, Inc. All rights reserved
30  * Use is subject to license terms.
31  */
32 /*
33  * This file is part of Lustre, http://www.lustre.org/
34  * Lustre is a trademark of Sun Microsystems, Inc.
35  */
36
37 #ifndef __CLASS_HASH_H
38 #define __CLASS_HASH_H
39
40 #include <lustre_lib.h>
41
42 struct lustre_hash_ops;
43
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;
49
50 #define LUSTRE_MAX_HASH_NAME 16
51
52 typedef struct lustre_hash {
53         int                         lh_cur_size;    /* current hash size */
54         int                         lh_min_size;    /* min hash size */
55         int                         lh_max_size;    /* max hash size */
56         int                         lh_min_theta;   /* resize min threshold */
57         int                         lh_max_theta;   /* resize max threshold */
58         int                         lh_flags;       /* hash flags */
59         atomic_t                    lh_count;       /* current entries */
60         atomic_t                    lh_rehash_count;/* resize count */
61         struct lustre_hash_bucket  *lh_buckets;     /* hash buckets */
62         struct lustre_hash_ops     *lh_ops;         /* hash operations */
63         rwlock_t                    lh_rwlock;      /* lustre_hash */
64         char                        lh_name[LUSTRE_MAX_HASH_NAME];
65 } lustre_hash_t;
66
67 typedef struct lustre_hash_ops {
68         unsigned (*lh_hash)(lustre_hash_t *lh, void *key, unsigned mask);
69         void *   (*lh_key)(struct hlist_node *hnode);
70         int      (*lh_compare)(void *key, struct hlist_node *hnode);
71         void *   (*lh_get)(struct hlist_node *hnode);
72         void *   (*lh_put)(struct hlist_node *hnode);
73         void     (*lh_exit)(struct hlist_node *hnode);
74 } lustre_hash_ops_t;
75
76 #define LH_DEBUG        0x0001          /* Enable expensive debug checks */
77 #define LH_REHASH       0x0002          /* Enable dynamic hash resizing */
78
79 #define LHO(lh)         (lh)->lh_ops
80 #define LHP(lh, op)     (lh)->lh_ops->lh_ ## op
81
82 static inline unsigned
83 lh_hash(lustre_hash_t *lh, void *key, unsigned mask)
84 {
85         LASSERT(lh);
86         LASSERT(LHO(lh));
87
88         if (LHP(lh, hash))
89                 return LHP(lh, hash)(lh, key, mask);
90
91         return -EOPNOTSUPP;
92 }
93
94 static inline void *
95 lh_key(lustre_hash_t *lh, struct hlist_node *hnode)
96 {
97         LASSERT(lh);
98         LASSERT(hnode);
99         LASSERT(LHO(lh));
100
101         if (LHP(lh, key))
102                 return LHP(lh, key)(hnode);
103
104         return NULL;
105 }
106
107 /**
108  * Returns 1 on a match,
109  * XXX: This would be better if it returned, -1, 0, or 1 for
110  *      <, =, > respectivly.  It could then be used to implement
111  *      a LH_SORT feature flags which could keep each lustre hash
112  *      bucket in order.  This would increase insertion times
113  *      but could reduce lookup times for deep chains.  Ideally,
114  *      the rehash should keep chain depth short but if that
115  *      ends up not being the case this would be a nice feature.
116  */
117 static inline int
118 lh_compare(lustre_hash_t *lh, void *key, struct hlist_node *hnode)
119 {
120         LASSERT(lh);
121         LASSERT(hnode);
122         LASSERT(LHO(lh));
123
124         if (LHP(lh, compare))
125                 return LHP(lh, compare)(key, hnode);
126
127         return -EOPNOTSUPP;
128 }
129
130 static inline void *
131 lh_get(lustre_hash_t *lh, struct hlist_node *hnode)
132 {
133         LASSERT(lh);
134         LASSERT(hnode);
135         LASSERT(LHO(lh));
136
137         if (LHP(lh, get))
138                 return LHP(lh, get)(hnode);
139
140         return NULL;
141 }
142
143 static inline void *
144 lh_put(lustre_hash_t *lh, struct hlist_node *hnode)
145 {
146         LASSERT(lh);
147         LASSERT(hnode);
148         LASSERT(LHO(lh));
149
150         if (LHP(lh, put))
151                 return LHP(lh, put)(hnode);
152
153         return NULL;
154 }
155
156 static inline void
157 lh_exit(lustre_hash_t *lh, struct hlist_node *hnode)
158 {
159         LASSERT(lh);
160         LASSERT(hnode);
161         LASSERT(LHO(lh));
162
163         if (LHP(lh, exit))
164                 return LHP(lh, exit)(hnode);
165 }
166
167 /** 
168  * Validate hnode references the correct key. 
169  */
170 static inline void
171 __lustre_hash_key_validate(lustre_hash_t *lh, void *key,
172                            struct hlist_node *hnode)
173 {
174         if (unlikely(lh->lh_flags & LH_DEBUG))
175                 LASSERT(lh_compare(lh, key, hnode));
176 }
177
178 /** 
179  * Validate hnode is in the correct bucket. 
180  */
181 static inline void
182 __lustre_hash_bucket_validate(lustre_hash_t *lh, lustre_hash_bucket_t *lhb,
183                               struct hlist_node *hnode)
184 {
185         unsigned i;
186
187         if (unlikely(lh->lh_flags & LH_DEBUG)) {
188                 i = lh_hash(lh, lh_key(lh, hnode), lh->lh_cur_size - 1);
189                 LASSERT(&lh->lh_buckets[i] == lhb);
190         }
191 }
192
193 static inline struct hlist_node *
194 __lustre_hash_bucket_lookup(lustre_hash_t *lh,
195                             lustre_hash_bucket_t *lhb, void *key)
196 {
197         struct hlist_node *hnode;
198
199         hlist_for_each(hnode, &lhb->lhb_head)
200                 if (lh_compare(lh, key, hnode))
201                         return hnode;
202
203         return NULL;
204 }
205
206 static inline void *
207 __lustre_hash_bucket_add(lustre_hash_t *lh,
208                          lustre_hash_bucket_t *lhb,
209                          struct hlist_node *hnode)
210 {
211         hlist_add_head(hnode, &(lhb->lhb_head));
212         atomic_inc(&lhb->lhb_count);
213         atomic_inc(&lh->lh_count);
214
215         return lh_get(lh, hnode);
216 }
217
218 static inline void *
219 __lustre_hash_bucket_del(lustre_hash_t *lh,
220                          lustre_hash_bucket_t *lhb,
221                          struct hlist_node *hnode)
222 {
223         hlist_del_init(hnode);
224         LASSERT(atomic_read(&lhb->lhb_count) > 0);
225         atomic_dec(&lhb->lhb_count);
226         LASSERT(atomic_read(&lh->lh_count) > 0);
227         atomic_dec(&lh->lh_count);
228
229         return lh_put(lh, hnode);
230 }
231
232 /* 
233  * Hash init/cleanup functions. 
234  */
235 lustre_hash_t *lustre_hash_init(char *name, unsigned int cur_size, 
236                                 unsigned int max_size,
237                                 lustre_hash_ops_t *ops, int flags);
238 void lustre_hash_exit(lustre_hash_t *lh);
239
240 /* 
241  * Hash addition functions. 
242  */
243 void lustre_hash_add(lustre_hash_t *lh, void *key,
244                      struct hlist_node *hnode);
245 int  lustre_hash_add_unique(lustre_hash_t *lh, void *key,
246                             struct hlist_node *hnode);
247 void *lustre_hash_findadd_unique(lustre_hash_t *lh, void *key,
248                                  struct hlist_node *hnode);
249
250 /* 
251  * Hash deletion functions. 
252  */
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
256 /* 
257  * Hash lookup/for_each functions.
258  */
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);
266
267 /* 
268  * Rehash - Theta is calculated to be the average chained
269  * hash depth assuming a perfectly uniform hash funcion. 
270  */
271 int lustre_hash_rehash(lustre_hash_t *lh, int size);
272 void lustre_hash_rehash_key(lustre_hash_t *lh, void *old_key,
273                             void *new_key, struct hlist_node *hnode);
274
275
276 static inline int
277 __lustre_hash_theta(lustre_hash_t *lh)
278 {
279         return ((atomic_read(&lh->lh_count) * 1000) / lh->lh_cur_size);
280 }
281
282 static inline void
283 __lustre_hash_set_theta(lustre_hash_t *lh, int min, int max)
284 {
285         LASSERT(min < max);
286         lh->lh_min_theta = min;
287         lh->lh_min_theta = max;
288 }
289
290 /* 
291  * Generic debug formatting routines mainly for proc handler. 
292  */
293 int lustre_hash_debug_header(char *str, int size);
294 int lustre_hash_debug_str(lustre_hash_t *lh, char *str, int size);
295
296 /* 
297  * 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 
298  */
299 #define CFS_GOLDEN_RATIO_PRIME_32 0x9e370001UL
300 /* 
301  * 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 
302  */
303 #define CFS_GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001ULL
304
305 /**
306  * Generic djb2 hash algorithm for character arrays.
307  */
308 static inline unsigned
309 lh_djb2_hash(void *key, size_t size, unsigned mask)
310 {
311         unsigned i, hash = 5381;
312
313         LASSERT(key != NULL);
314
315         for (i = 0; i < size; i++)
316                 hash = hash * 33 + ((char *)key)[i];
317
318         return (hash & mask);
319 }
320
321 /**
322  * Generic u32 hash algorithm.
323  */
324 static inline unsigned
325 lh_u32_hash(__u32 key, unsigned mask)
326 {
327         return ((key * CFS_GOLDEN_RATIO_PRIME_32) & mask);
328 }
329
330 /**
331  * Generic u64 hash algorithm.
332  */
333 static inline unsigned
334 lh_u64_hash(__u64 key, unsigned mask)
335 {
336         return ((unsigned)(key * CFS_GOLDEN_RATIO_PRIME_64) & mask);
337 }
338
339 #define lh_for_each_bucket(lh, lhb, pos)         \
340         for (pos = 0;                            \
341              pos < lh->lh_cur_size &&            \
342              ({ lhb = &lh->lh_buckets[i]; 1; }); \
343              pos++)
344
345 #endif /* __CLASS_HASH_H */