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_max_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 */