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         LASSERT(LHP(lh, hash));
  89
  90         return LHP(lh, hash)(lh, key, mask);
  91 }
  92
  93 static inline void *
  94 lh_key(lustre_hash_t *lh, struct hlist_node *hnode)
  95 {
  96         LASSERT(lh);
  97         LASSERT(hnode);
  98         LASSERT(LHO(lh));
  99
 100         if (LHP(lh, key))
 101                 return LHP(lh, key)(hnode);
 102
 103         return NULL;
 104 }
 105
 106 /* Returns 1 on a match,
 107  * XXX: This would be better if it returned, -1, 0, or 1 for
 108  *      <, =, > respectivly.  It could then be used to implement
 109  *      a LH_SORT feature flags which could keep each lustre hash
 110  *      bucket in order.  This would increase insertion times
 111  *      but could reduce lookup times for deep chains.  Ideally,
 112  *      the rehash should keep chain depth short but if that
 113  *      ends up not being the case this would be a nice feature.
 114  */
 115 static inline int
 116 lh_compare(lustre_hash_t *lh, void *key, struct hlist_node *hnode)
 117 {
 118         LASSERT(lh);
 119         LASSERT(hnode);
 120         LASSERT(LHO(lh));
 121
 122         if (LHP(lh, compare))
 123                 return LHP(lh, compare)(key, hnode);
 124
 125         return -EOPNOTSUPP;
 126 }
 127
 128 static inline void *
 129 lh_get(lustre_hash_t *lh, struct hlist_node *hnode)
 130 {
 131         LASSERT(lh);
 132         LASSERT(hnode);
 133         LASSERT(LHO(lh));
 134
 135         if (LHP(lh, get))
 136                 return LHP(lh, get)(hnode);
 137
 138         return NULL;
 139 }
 140
 141 static inline void *
 142 lh_put(lustre_hash_t *lh, struct hlist_node *hnode)
 143 {
 144         LASSERT(lh);
 145         LASSERT(hnode);
 146         LASSERT(LHO(lh));
 147
 148         if (LHP(lh, put))
 149                 return LHP(lh, put)(hnode);
 150
 151         return NULL;
 152 }
 153
 154 static inline void
 155 lh_exit(lustre_hash_t *lh, struct hlist_node *hnode)
 156 {
 157         LASSERT(lh);
 158         LASSERT(hnode);
 159         LASSERT(LHO(lh));
 160
 161         if (LHP(lh, exit))
 162                 return LHP(lh, exit)(hnode);
 163 }
 164
 165 /* Validate hnode references the correct key */
 166 static inline void
 167 __lustre_hash_key_validate(lustre_hash_t *lh, void *key,
 168                            struct hlist_node *hnode)
 169 {
 170         if (unlikely(lh->lh_flags & LH_DEBUG))
 171                 LASSERT(lh_compare(lh, key, hnode) > 0);
 172 }
 173
 174 /* Validate hnode is in the correct bucket */
 175 static inline void
 176 __lustre_hash_bucket_validate(lustre_hash_t *lh, lustre_hash_bucket_t *lhb,
 177                               struct hlist_node *hnode)
 178 {
 179         unsigned i;
 180
 181         if (unlikely(lh->lh_flags & LH_DEBUG)) {
 182                 i = lh_hash(lh, lh_key(lh, hnode), lh->lh_cur_mask);
 183                 LASSERT(&lh->lh_buckets[i] == lhb);
 184         }
 185 }
 186
 187 static inline struct hlist_node *
 188 __lustre_hash_bucket_lookup(lustre_hash_t *lh,
 189                             lustre_hash_bucket_t *lhb, void *key)
 190 {
 191         struct hlist_node *hnode;
 192
 193         hlist_for_each(hnode, &lhb->lhb_head)
 194                 if (lh_compare(lh, key, hnode) > 0)
 195                         return hnode;
 196
 197         return NULL;
 198 }
 199
 200 static inline void *
 201 __lustre_hash_bucket_add(lustre_hash_t *lh,
 202                          lustre_hash_bucket_t *lhb,
 203                          struct hlist_node *hnode)
 204 {
 205         hlist_add_head(hnode, &(lhb->lhb_head));
 206         atomic_inc(&lhb->lhb_count);
 207         atomic_inc(&lh->lh_count);
 208
 209         return lh_get(lh, hnode);
 210 }
 211
 212 static inline void *
 213 __lustre_hash_bucket_del(lustre_hash_t *lh,
 214                          lustre_hash_bucket_t *lhb,
 215                          struct hlist_node *hnode)
 216 {
 217         hlist_del_init(hnode);
 218         LASSERT(atomic_read(&lhb->lhb_count) > 0);
 219         atomic_dec(&lhb->lhb_count);
 220         LASSERT(atomic_read(&lh->lh_count) > 0);
 221         atomic_dec(&lh->lh_count);
 222
 223         return lh_put(lh, hnode);
 224 }
 225
 226 /* Hash init/cleanup functions */
 227 lustre_hash_t *lustre_hash_init(char *name, unsigned int cur_bits,
 228                                 unsigned int max_bits,
 229                                 lustre_hash_ops_t *ops, int flags);
 230 void lustre_hash_exit(lustre_hash_t *lh);
 231
 232 /* Hash addition functions */
 233 void lustre_hash_add(lustre_hash_t *lh, void *key,
 234                      struct hlist_node *hnode);
 235 int lustre_hash_add_unique(lustre_hash_t *lh, void *key,
 236                            struct hlist_node *hnode);
 237 void *lustre_hash_findadd_unique(lustre_hash_t *lh, void *key,
 238                                  struct hlist_node *hnode);
 239
 240 /* Hash deletion functions */
 241 void *lustre_hash_del(lustre_hash_t *lh, void *key, struct hlist_node *hnode);
 242 void *lustre_hash_del_key(lustre_hash_t *lh, void *key);
 243
 244 /* Hash lookup/for_each functions */
 245 void *lustre_hash_lookup(lustre_hash_t *lh, void *key);
 246 typedef void (*lh_for_each_cb)(void *obj, void *data);
 247 void lustre_hash_for_each(lustre_hash_t *lh, lh_for_each_cb, void *data);
 248 void lustre_hash_for_each_safe(lustre_hash_t *lh, lh_for_each_cb, void *data);
 249 void lustre_hash_for_each_empty(lustre_hash_t *lh, lh_for_each_cb, void *data);
 250 void lustre_hash_for_each_key(lustre_hash_t *lh, void *key,
 251                               lh_for_each_cb, void *data);
 252
 253 /*
 254  * Rehash - Theta is calculated to be the average chained
 255  * hash depth assuming a perfectly uniform hash funcion.
 256  */
 257 int lustre_hash_rehash(lustre_hash_t *lh, int bits);
 258 void lustre_hash_rehash_key(lustre_hash_t *lh, void *old_key,
 259                             void *new_key, struct hlist_node *hnode);
 260
 261
 262 #define LH_THETA_BITS  10
 263
 264 /* Return integer component of theta */
 265 static inline int __lustre_hash_theta_int(int theta)
 266 {
 267         return (theta >> LH_THETA_BITS);
 268 }
 269
 270 /* Return a fractional value between 0 and 999 */
 271 static inline int __lustre_hash_theta_frac(int theta)
 272 {
 273         return ((theta * 1000) >> LH_THETA_BITS) -
 274                (__lustre_hash_theta_int(theta) * 1000);
 275 }
 276
 277 static inline int __lustre_hash_theta(lustre_hash_t *lh)
 278 {
 279         return (atomic_read(&lh->lh_count) << LH_THETA_BITS) >> lh->lh_cur_bits;
 280 }
 281
 282 static inline void __lustre_hash_set_theta(lustre_hash_t *lh, int min, int max)
 283 {
 284         LASSERT(min < max);
 285         lh->lh_min_theta = min;
 286         lh->lh_max_theta = max;
 287 }
 288
 289 /* Generic debug formatting routines mainly for proc handler */
 290 int lustre_hash_debug_header(char *str, int size);
 291 int lustre_hash_debug_str(lustre_hash_t *lh, char *str, int size);
 292
 293 /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
 294 #define CFS_GOLDEN_RATIO_PRIME_32 0x9e370001UL
 295 /*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
 296 #define CFS_GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001ULL
 297
 298 /*
 299  * Generic djb2 hash algorithm for character arrays.
 300  */
 301 static inline unsigned
 302 lh_djb2_hash(void *key, size_t size, unsigned mask)
 303 {
 304         unsigned i, hash = 5381;
 305
 306         LASSERT(key != NULL);
 307
 308         for (i = 0; i < size; i++)
 309                 hash = hash * 33 + ((char *)key)[i];
 310
 311         return (hash & mask);
 312 }
 313
 314 /*
 315  * Generic u32 hash algorithm.
 316  */
 317 static inline unsigned
 318 lh_u32_hash(__u32 key, unsigned mask)
 319 {
 320         return ((key * CFS_GOLDEN_RATIO_PRIME_32) & mask);
 321 }
 322
 323 /*
 324  * Generic u64 hash algorithm.
 325  */
 326 static inline unsigned
 327 lh_u64_hash(__u64 key, unsigned mask)
 328 {
 329         return ((unsigned)(key * CFS_GOLDEN_RATIO_PRIME_64) & mask);
 330 }
 331
 332 #define lh_for_each_bucket(lh, lhb, pos)         \
 333         for (pos = 0;                            \
 334              pos <= lh->lh_cur_mask &&           \
 335              ({ lhb = &lh->lh_buckets[i]; 1; }); \
 336              pos++)
 337
 338 #endif /* __CLASS_HASH_H */