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 /* Some hash init argument constants */
 227 #define HASH_POOLS_CUR_BITS 3
 228 #define HASH_POOLS_MAX_BITS 7
 229 #define HASH_UUID_CUR_BITS 7
 230 #define HASH_UUID_MAX_BITS 12
 231 #define HASH_NID_CUR_BITS 7
 232 #define HASH_NID_MAX_BITS 12
 233 #define HASH_NID_STATS_CUR_BITS 7
 234 #define HASH_NID_STATS_MAX_BITS 12
 235 #define HASH_LQS_CUR_BITS 7
 236 #define HASH_LQS_MAX_BITS 12
 237 #define HASH_CONN_CUR_BITS 5
 238 #define HASH_CONN_MAX_BITS 15
 239
 240 /* Hash init/cleanup functions */
 241 lustre_hash_t *lustre_hash_init(char *name, unsigned int cur_bits,
 242                                 unsigned int max_bits,
 243                                 lustre_hash_ops_t *ops, int flags);
 244 void lustre_hash_exit(lustre_hash_t *lh);
 245
 246 /* Hash addition functions */
 247 void lustre_hash_add(lustre_hash_t *lh, void *key,
 248                      struct hlist_node *hnode);
 249 int lustre_hash_add_unique(lustre_hash_t *lh, void *key,
 250                            struct hlist_node *hnode);
 251 void *lustre_hash_findadd_unique(lustre_hash_t *lh, void *key,
 252                                  struct hlist_node *hnode);
 253
 254 /* Hash deletion functions */
 255 void *lustre_hash_del(lustre_hash_t *lh, void *key, struct hlist_node *hnode);
 256 void *lustre_hash_del_key(lustre_hash_t *lh, void *key);
 257
 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);
 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 bits);
 272 void lustre_hash_rehash_key(lustre_hash_t *lh, void *old_key,
 273                             void *new_key, struct hlist_node *hnode);
 274
 275
 276 #define LH_THETA_BITS  10
 277
 278 /* Return integer component of theta */
 279 static inline int __lustre_hash_theta_int(int theta)
 280 {
 281         return (theta >> LH_THETA_BITS);
 282 }
 283
 284 /* Return a fractional value between 0 and 999 */
 285 static inline int __lustre_hash_theta_frac(int theta)
 286 {
 287         return ((theta * 1000) >> LH_THETA_BITS) -
 288                (__lustre_hash_theta_int(theta) * 1000);
 289 }
 290
 291 static inline int __lustre_hash_theta(lustre_hash_t *lh)
 292 {
 293         return (atomic_read(&lh->lh_count) << LH_THETA_BITS) >> lh->lh_cur_bits;
 294 }
 295
 296 static inline void __lustre_hash_set_theta(lustre_hash_t *lh, int min, int max)
 297 {
 298         LASSERT(min < max);
 299         lh->lh_min_theta = min;
 300         lh->lh_max_theta = max;
 301 }
 302
 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);
 306
 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
 311
 312 /*
 313  * Generic djb2 hash algorithm for character arrays.
 314  */
 315 static inline unsigned
 316 lh_djb2_hash(void *key, size_t size, unsigned mask)
 317 {
 318         unsigned i, hash = 5381;
 319
 320         LASSERT(key != NULL);
 321
 322         for (i = 0; i < size; i++)
 323                 hash = hash * 33 + ((char *)key)[i];
 324
 325         return (hash & mask);
 326 }
 327
 328 /*
 329  * Generic u32 hash algorithm.
 330  */
 331 static inline unsigned
 332 lh_u32_hash(__u32 key, unsigned mask)
 333 {
 334         return ((key * CFS_GOLDEN_RATIO_PRIME_32) & mask);
 335 }
 336
 337 /*
 338  * Generic u64 hash algorithm.
 339  */
 340 static inline unsigned
 341 lh_u64_hash(__u64 key, unsigned mask)
 342 {
 343         return ((unsigned)(key * CFS_GOLDEN_RATIO_PRIME_64) & mask);
 344 }
 345
 346 #define lh_for_each_bucket(lh, lhb, pos)         \
 347         for (pos = 0;                            \
 348              pos <= lh->lh_cur_mask &&           \
 349              ({ lhb = &lh->lh_buckets[i]; 1; }); \
 350              pos++)
 351
 352 #endif /* __CLASS_HASH_H */