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 (c) 2007, 2010, Oracle and/or its affiliates. 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         LASSERT(LHP(lh, key));
 100
 101         return LHP(lh, key)(hnode);
 102 }
 103
 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.
 112  */
 113 static inline int
 114 lh_compare(lustre_hash_t *lh, void *key, struct hlist_node *hnode)
 115 {
 116         LASSERT(lh);
 117         LASSERT(hnode);
 118         LASSERT(LHO(lh));
 119
 120         if (LHP(lh, compare))
 121                 return LHP(lh, compare)(key, hnode);
 122
 123         return -EOPNOTSUPP;
 124 }
 125
 126 static inline void *
 127 lh_get(lustre_hash_t *lh, struct hlist_node *hnode)
 128 {
 129         LASSERT(lh);
 130         LASSERT(hnode);
 131         LASSERT(LHO(lh));
 132
 133         if (LHP(lh, get))
 134                 return LHP(lh, get)(hnode);
 135
 136         return NULL;
 137 }
 138
 139 static inline void *
 140 lh_put(lustre_hash_t *lh, struct hlist_node *hnode)
 141 {
 142         LASSERT(lh);
 143         LASSERT(hnode);
 144         LASSERT(LHO(lh));
 145
 146         if (LHP(lh, put))
 147                 return LHP(lh, put)(hnode);
 148
 149         return NULL;
 150 }
 151
 152 static inline void
 153 lh_exit(lustre_hash_t *lh, struct hlist_node *hnode)
 154 {
 155         LASSERT(lh);
 156         LASSERT(hnode);
 157         LASSERT(LHO(lh));
 158
 159         if (LHP(lh, exit))
 160                 LHP(lh, exit)(hnode);
 161 }
 162
 163 /* Validate hnode references the correct key */
 164 static inline void
 165 __lustre_hash_key_validate(lustre_hash_t *lh, void *key,
 166                            struct hlist_node *hnode)
 167 {
 168         if (unlikely(lh->lh_flags & LH_DEBUG))
 169                 LASSERT(lh_compare(lh, key, hnode));
 170 }
 171
 172 /* Validate hnode is in the correct bucket */
 173 static inline void
 174 __lustre_hash_bucket_validate(lustre_hash_t *lh, lustre_hash_bucket_t *lhb,
 175                               struct hlist_node *hnode)
 176 {
 177         unsigned i;
 178
 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);
 182         }
 183 }
 184
 185 static inline struct hlist_node *
 186 __lustre_hash_bucket_lookup(lustre_hash_t *lh,
 187                             lustre_hash_bucket_t *lhb, void *key)
 188 {
 189         struct hlist_node *hnode;
 190
 191         hlist_for_each(hnode, &lhb->lhb_head)
 192                 if (lh_compare(lh, key, hnode))
 193                         return hnode;
 194
 195         return NULL;
 196 }
 197
 198 static inline void *
 199 __lustre_hash_bucket_add(lustre_hash_t *lh,
 200                          lustre_hash_bucket_t *lhb,
 201                          struct hlist_node *hnode)
 202 {
 203         hlist_add_head(hnode, &(lhb->lhb_head));
 204         atomic_inc(&lhb->lhb_count);
 205         atomic_inc(&lh->lh_count);
 206
 207         return lh_get(lh, hnode);
 208 }
 209
 210 static inline void *
 211 __lustre_hash_bucket_del(lustre_hash_t *lh,
 212                          lustre_hash_bucket_t *lhb,
 213                          struct hlist_node *hnode)
 214 {
 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);
 220
 221         return lh_put(lh, hnode);
 222 }
 223
 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
 237
 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);
 243
 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);
 251
 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);
 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[pos]);       \
 350              pos++)
 351
 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]);       \
 356              pos++)
 357
 358 #endif /* __CLASS_HASH_H */