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_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];
  66 } lustre_hash_t;
  67
  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);
  75 } lustre_hash_ops_t;
  76
  77 #define LH_DEBUG        0x0001          /* Enable expensive debug checks */
  78 #define LH_REHASH       0x0002          /* Enable dynamic hash resizing */
  79
  80 #define LHO(lh)         (lh)->lh_ops
  81 #define LHP(lh, op)     (lh)->lh_ops->lh_ ## op
  82
  83 static inline unsigned
  84 lh_hash(lustre_hash_t *lh, void *key, unsigned mask)
  85 {
  86         LASSERT(lh);
  87         LASSERT(LHO(lh));
  88
  89         if (LHP(lh, hash))
  90                 return LHP(lh, hash)(lh, key, mask);
  91
  92         return -EOPNOTSUPP;
  93 }
  94
  95 static inline void *
  96 lh_key(lustre_hash_t *lh, struct hlist_node *hnode)
  97 {
  98         LASSERT(lh);
  99         LASSERT(hnode);
 100         LASSERT(LHO(lh));
 101
 102         if (LHP(lh, key))
 103                 return LHP(lh, key)(hnode);
 104
 105         return NULL;
 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 /* Validate hnode references the correct key */
 168 static inline void
 169 __lustre_hash_key_validate(lustre_hash_t *lh, void *key,
 170                            struct hlist_node *hnode)
 171 {
 172         if (unlikely(lh->lh_flags & LH_DEBUG))
 173                 LASSERT(lh_compare(lh, key, hnode) > 0);
 174 }
 175
 176 /* Validate hnode is in the correct bucket */
 177 static inline void
 178 __lustre_hash_bucket_validate(lustre_hash_t *lh, lustre_hash_bucket_t *lhb,
 179                               struct hlist_node *hnode)
 180 {
 181         unsigned i;
 182
 183         if (unlikely(lh->lh_flags & LH_DEBUG)) {
 184                 i = lh_hash(lh, lh_key(lh, hnode), lh->lh_cur_mask);
 185                 LASSERT(&lh->lh_buckets[i] == lhb);
 186         }
 187 }
 188
 189 static inline struct hlist_node *
 190 __lustre_hash_bucket_lookup(lustre_hash_t *lh,
 191                             lustre_hash_bucket_t *lhb, void *key)
 192 {
 193         struct hlist_node *hnode;
 194
 195         hlist_for_each(hnode, &lhb->lhb_head)
 196                 if (lh_compare(lh, key, hnode) > 0)
 197                         return hnode;
 198
 199         return NULL;
 200 }
 201
 202 static inline void *
 203 __lustre_hash_bucket_add(lustre_hash_t *lh,
 204                          lustre_hash_bucket_t *lhb,
 205                          struct hlist_node *hnode)
 206 {
 207         hlist_add_head(hnode, &(lhb->lhb_head));
 208         atomic_inc(&lhb->lhb_count);
 209         atomic_inc(&lh->lh_count);
 210
 211         return lh_get(lh, hnode);
 212 }
 213
 214 static inline void *
 215 __lustre_hash_bucket_del(lustre_hash_t *lh,
 216                          lustre_hash_bucket_t *lhb,
 217                          struct hlist_node *hnode)
 218 {
 219         hlist_del_init(hnode);
 220         LASSERT(atomic_read(&lhb->lhb_count) > 0);
 221         atomic_dec(&lhb->lhb_count);
 222         LASSERT(atomic_read(&lh->lh_count) > 0);
 223         atomic_dec(&lh->lh_count);
 224
 225         return lh_put(lh, hnode);
 226 }
 227
 228 /* Hash init/cleanup functions */
 229 lustre_hash_t *lustre_hash_init(char *name, unsigned int cur_bits,
 230                                 unsigned int max_bits,
 231                                 lustre_hash_ops_t *ops, int flags);
 232 void lustre_hash_exit(lustre_hash_t *lh);
 233
 234 /* Hash addition functions */
 235 void lustre_hash_add(lustre_hash_t *lh, void *key,
 236                      struct hlist_node *hnode);
 237 int lustre_hash_add_unique(lustre_hash_t *lh, void *key,
 238                            struct hlist_node *hnode);
 239 void *lustre_hash_findadd_unique(lustre_hash_t *lh, void *key,
 240                                  struct hlist_node *hnode);
 241
 242 /* Hash deletion functions */
 243 void *lustre_hash_del(lustre_hash_t *lh, void *key, struct hlist_node *hnode);
 244 void *lustre_hash_del_key(lustre_hash_t *lh, void *key);
 245
 246 /* Hash lookup/for_each functions */
 247 void *lustre_hash_lookup(lustre_hash_t *lh, void *key);
 248 typedef void (*lh_for_each_cb)(void *obj, void *data);
 249 void lustre_hash_for_each(lustre_hash_t *lh, lh_for_each_cb, void *data);
 250 void lustre_hash_for_each_safe(lustre_hash_t *lh, lh_for_each_cb, void *data);
 251 void lustre_hash_for_each_empty(lustre_hash_t *lh, lh_for_each_cb, void *data);
 252 void lustre_hash_for_each_key(lustre_hash_t *lh, void *key,
 253                               lh_for_each_cb, void *data);
 254
 255 /*
 256  * Rehash - Theta is calculated to be the average chained
 257  * hash depth assuming a perfectly uniform hash funcion.
 258  */
 259 int lustre_hash_rehash(lustre_hash_t *lh, int bits);
 260 void lustre_hash_rehash_key(lustre_hash_t *lh, void *old_key,
 261                             void *new_key, struct hlist_node *hnode);
 262
 263
 264 #define LH_THETA_BITS  10
 265
 266 /* Return integer component of theta */
 267 static inline int __lustre_hash_theta_int(int theta)
 268 {
 269         return (theta >> LH_THETA_BITS);
 270 }
 271
 272 /* Return a fractional value between 0 and 999 */
 273 static inline int __lustre_hash_theta_frac(int theta)
 274 {
 275         return ((theta * 1000) >> LH_THETA_BITS) -
 276                (__lustre_hash_theta_int(theta) * 1000);
 277 }
 278
 279 static inline int __lustre_hash_theta(lustre_hash_t *lh)
 280 {
 281         return (atomic_read(&lh->lh_count) << LH_THETA_BITS) >> lh->lh_cur_bits;
 282 }
 283
 284 static inline void __lustre_hash_set_theta(lustre_hash_t *lh, int min, int max)
 285 {
 286         LASSERT(min < max);
 287         lh->lh_min_theta = min;
 288         lh->lh_max_theta = max;
 289 }
 290
 291 /* Generic debug formatting routines mainly for proc handler */
 292 int lustre_hash_debug_header(char *str, int size);
 293 int lustre_hash_debug_str(lustre_hash_t *lh, char *str, int size);
 294
 295 /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
 296 #define CFS_GOLDEN_RATIO_PRIME_32 0x9e370001UL
 297 /*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
 298 #define CFS_GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001ULL
 299
 300 /*
 301  * Generic djb2 hash algorithm for character arrays.
 302  */
 303 static inline unsigned
 304 lh_djb2_hash(void *key, size_t size, unsigned mask)
 305 {
 306         unsigned i, hash = 5381;
 307
 308         LASSERT(key != NULL);
 309
 310         for (i = 0; i < size; i++)
 311                 hash = hash * 33 + ((char *)key)[i];
 312
 313         return (hash & mask);
 314 }
 315
 316 /*
 317  * Generic u32 hash algorithm.
 318  */
 319 static inline unsigned
 320 lh_u32_hash(__u32 key, unsigned mask)
 321 {
 322         return ((key * CFS_GOLDEN_RATIO_PRIME_32) & mask);
 323 }
 324
 325 /*
 326  * Generic u64 hash algorithm.
 327  */
 328 static inline unsigned
 329 lh_u64_hash(__u64 key, unsigned mask)
 330 {
 331         return ((unsigned)(key * CFS_GOLDEN_RATIO_PRIME_64) & mask);
 332 }
 333
 334 #define lh_for_each_bucket(lh, lhb, pos)         \
 335         for (pos = 0;                            \
 336              pos <= lh->lh_cur_mask &&           \
 337              ({ lhb = &lh->lh_buckets[i]; 1; }); \
 338              pos++)
 339
 340 #endif /* __CLASS_HASH_H */