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         /**
  46          * Entries list.
  47          */
  48         struct hlist_head           lhb_head;
  49         /**
  50          * Current entries.
  51          */
  52         atomic_t                    lhb_count;
  53         /**
  54          * Lustre_hash_bucket.
  55          */
  56         rwlock_t                    lhb_rwlock;
  57 } lustre_hash_bucket_t;
  58
  59 typedef struct lustre_hash {
  60         /**
  61          * Hash name.
  62          */
  63         char                       *lh_name;
  64         /**
  65          * Hash name size.
  66          */
  67         unsigned int                lh_name_size;
  68         /**
  69          * Current hash size.
  70          */
  71         unsigned int                lh_cur_size;
  72         /**
  73          * Min hash size.
  74          */
  75         unsigned int                lh_min_size;
  76         /**
  77          * Max hash size.
  78          */
  79         unsigned int                lh_max_size;
  80         /**
  81          * Resize min threshold.
  82          */
  83         unsigned int                lh_min_theta;
  84         /**
  85          * Resize max threshold.
  86          */
  87         unsigned int                lh_max_theta;
  88         /**
  89          * Hash flags.
  90          */
  91         int                         lh_flags;
  92         /**
  93          * Current entries.
  94          */
  95         atomic_t                    lh_count;
  96         /**
  97          * Resize count.
  98          */
  99         atomic_t                    lh_rehash_count;
 100         /**
 101          * Hash buckets.
 102          */
 103         struct lustre_hash_bucket  *lh_buckets;
 104         /**
 105          * Hash operations.
 106          */
 107         struct lustre_hash_ops     *lh_ops;
 108         /**
 109          * Protects lustre_hash.
 110          */
 111         rwlock_t                    lh_rwlock;
 112 } lustre_hash_t;
 113
 114 typedef struct lustre_hash_ops {
 115         unsigned (*lh_hash)(lustre_hash_t *lh, void *key, unsigned mask);
 116         void *   (*lh_key)(struct hlist_node *hnode);
 117         int      (*lh_compare)(void *key, struct hlist_node *hnode);
 118         void *   (*lh_get)(struct hlist_node *hnode);
 119         void *   (*lh_put)(struct hlist_node *hnode);
 120         void     (*lh_exit)(struct hlist_node *hnode);
 121 } lustre_hash_ops_t;
 122
 123 /**
 124  * Enable expensive debug checks.
 125  */
 126 #define LH_DEBUG        0x0001
 127 /**
 128  * Enable dynamic hash resizing.
 129  */
 130 #define LH_REHASH       0x0002
 131
 132 #define LHO(lh)         (lh)->lh_ops
 133 #define LHP(lh, op)     (lh)->lh_ops->lh_ ## op
 134
 135 static inline unsigned
 136 lh_hash(lustre_hash_t *lh, void *key, unsigned mask)
 137 {
 138         LASSERT(lh);
 139
 140         if (LHO(lh) && LHP(lh, hash))
 141                 return LHP(lh, hash)(lh, key, mask);
 142
 143         return -EOPNOTSUPP;
 144 }
 145
 146 static inline void *
 147 lh_key(lustre_hash_t *lh, struct hlist_node *hnode)
 148 {
 149         LASSERT(lh);
 150         LASSERT(hnode);
 151
 152         if (LHO(lh) && LHP(lh, key))
 153                 return LHP(lh, key)(hnode);
 154
 155         return NULL;
 156 }
 157
 158 /**
 159  * Returns 1 on a match,
 160  * XXX: This would be better if it returned, -1, 0, or 1 for
 161  *      <, =, > respectivly.  It could then be used to implement
 162  *      a LH_SORT feature flags which could keep each lustre hash
 163  *      bucket in order.  This would increase insertion times
 164  *      but could reduce lookup times for deep chains.  Ideally,
 165  *      the rehash should keep chain depth short but if that
 166  *      ends up not being the case this would be a nice feature.
 167  */
 168 static inline int
 169 lh_compare(lustre_hash_t *lh, void *key, struct hlist_node *hnode)
 170 {
 171         LASSERT(lh);
 172         LASSERT(hnode);
 173
 174         if (LHO(lh) && LHP(lh, compare))
 175                 return LHP(lh, compare)(key, hnode);
 176
 177         return -EOPNOTSUPP;
 178 }
 179
 180 static inline void *
 181 lh_get(lustre_hash_t *lh, struct hlist_node *hnode)
 182 {
 183         LASSERT(lh);
 184         LASSERT(hnode);
 185
 186         if (LHO(lh) && LHP(lh, get))
 187                 return LHP(lh, get)(hnode);
 188
 189         return NULL;
 190 }
 191
 192 static inline void *
 193 lh_put(lustre_hash_t *lh, struct hlist_node *hnode)
 194 {
 195         LASSERT(lh);
 196         LASSERT(hnode);
 197
 198         if (LHO(lh) && LHP(lh, put))
 199                 return LHP(lh, put)(hnode);
 200
 201         return NULL;
 202 }
 203
 204 static inline void
 205 lh_exit(lustre_hash_t *lh, struct hlist_node *hnode)
 206 {
 207         LASSERT(lh);
 208         LASSERT(hnode);
 209
 210         if (LHO(lh) && LHP(lh, exit))
 211                 return LHP(lh, exit)(hnode);
 212 }
 213
 214 /**
 215  * Validate hnode references the correct key.
 216  */
 217 static inline void
 218 __lustre_hash_key_validate(lustre_hash_t *lh, void *key,
 219                            struct hlist_node *hnode)
 220 {
 221         if (unlikely(lh->lh_flags & LH_DEBUG))
 222                 LASSERT(lh_compare(lh, key, hnode));
 223 }
 224
 225 /*
 226  * Validate hnode is in the correct bucket.
 227  */
 228 static inline void
 229 __lustre_hash_bucket_validate(lustre_hash_t *lh, lustre_hash_bucket_t *lhb,
 230                               struct hlist_node *hnode)
 231 {
 232         unsigned i;
 233
 234         if (unlikely(lh->lh_flags & LH_DEBUG)) {
 235                 i = lh_hash(lh, lh_key(lh, hnode), lh->lh_cur_size - 1);
 236                 LASSERT(&lh->lh_buckets[i] == lhb);
 237           }
 238   }
 239
 240 static inline struct hlist_node *
 241 __lustre_hash_bucket_lookup(lustre_hash_t *lh,
 242                             lustre_hash_bucket_t *lhb, void *key)
 243 {
 244         struct hlist_node *hnode;
 245
 246         hlist_for_each(hnode, &lhb->lhb_head)
 247                 if (lh_compare(lh, key, hnode))
 248                         return hnode;
 249
 250         return NULL;
 251 }
 252
 253 static inline void *
 254 __lustre_hash_bucket_add(lustre_hash_t *lh,
 255                          lustre_hash_bucket_t *lhb,
 256                          struct hlist_node *hnode)
 257 {
 258         hlist_add_head(hnode, &(lhb->lhb_head));
 259         atomic_inc(&lhb->lhb_count);
 260         atomic_inc(&lh->lh_count);
 261
 262         return lh_get(lh, hnode);
 263 }
 264
 265 static inline void *
 266 __lustre_hash_bucket_del(lustre_hash_t *lh,
 267                          lustre_hash_bucket_t *lhb,
 268                          struct hlist_node *hnode)
 269 {
 270         hlist_del_init(hnode);
 271         atomic_dec(&lhb->lhb_count);
 272         atomic_dec(&lh->lh_count);
 273
 274         return lh_put(lh, hnode);
 275 }
 276
 277 /*
 278  * Hash init/cleanup functions.
 279  */
 280 lustre_hash_t *lustre_hash_init(char *name, unsigned int cur_size,
 281                                 unsigned int max_size,
 282                                 lustre_hash_ops_t *ops, int flags);
 283 void lustre_hash_exit(lustre_hash_t *lh);
 284
 285 /*
 286  * Hash addition functions.
 287  */
 288 void lustre_hash_add(lustre_hash_t *lh, void *key,
 289                      struct hlist_node *hnode);
 290 int  lustre_hash_add_unique(lustre_hash_t *lh, void *key,
 291                             struct hlist_node *hnode);
 292 void *lustre_hash_findadd_unique(lustre_hash_t *lh, void *key,
 293                                  struct hlist_node *hnode);
 294
 295 /*
 296  * Hash deletion functions.
 297  */
 298 void *lustre_hash_del(lustre_hash_t *lh, void *key, struct hlist_node *hnode);
 299 void *lustre_hash_del_key(lustre_hash_t *lh, void *key);
 300
 301 /*
 302  * Hash lookup/for_each functions.
 303  */
 304 void *lustre_hash_lookup(lustre_hash_t *lh, void *key);
 305 typedef void (*lh_for_each_cb)(void *obj, void *data);
 306 void lustre_hash_for_each(lustre_hash_t *lh, lh_for_each_cb, void *data);
 307 void lustre_hash_for_each_safe(lustre_hash_t *lh, lh_for_each_cb, void *data);
 308 void lustre_hash_for_each_empty(lustre_hash_t *lh, lh_for_each_cb, void *data);
 309 void lustre_hash_for_each_key(lustre_hash_t *lh, void *key,
 310                               lh_for_each_cb, void *data);
 311
 312 /*
 313  * Rehash - theta is calculated to be the average chained
 314  * hash depth assuming a perfectly uniform hash funcion.
 315  */
 316 int lustre_hash_rehash(lustre_hash_t *lh, int size);
 317 void lustre_hash_rehash_key(lustre_hash_t *lh, void *old_key,
 318                             void *new_key, struct hlist_node *hnode);
 319
 320
 321 static inline int
 322 __lustre_hash_theta(lustre_hash_t *lh)
 323 {
 324         return ((atomic_read(&lh->lh_count) * 1000) / lh->lh_cur_size);
 325 }
 326
 327 static inline void
 328 __lustre_hash_set_theta(lustre_hash_t *lh, int min, int max)
 329 {
 330         LASSERT(min < max);
 331         lh->lh_min_theta = min;
 332         lh->lh_min_theta = max;
 333 }
 334
 335 /*
 336  * Generic debug formatting routines mainly for proc handler.
 337  */
 338 int lustre_hash_debug_header(char *str, int size);
 339 int lustre_hash_debug_str(lustre_hash_t *lh, char *str, int size);
 340
 341
 342 /**
 343  * 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1
 344  */
 345 #define GOLDEN_RATIO_PRIME_32 0x9e370001UL
 346 /**
 347  * 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1
 348  */
 349 #define GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001ULL
 350
 351
 352 /**
 353  * Generic djb2 hash algorithm for character arrays.
 354  */
 355 static inline unsigned
 356 lh_djb2_hash(void *key, size_t size, unsigned mask)
 357 {
 358         unsigned i, hash = 5381;
 359
 360         LASSERT(key != NULL);
 361
 362         for (i = 0; i < size; i++)
 363                 hash = hash * 33 + ((char *)key)[i];
 364
 365         RETURN(hash & mask);
 366 }
 367
 368 /**
 369  * Generic u32 hash algorithm.
 370  */
 371 static inline unsigned
 372 lh_u32_hash(__u32 key, unsigned mask)
 373 {
 374         RETURN((key * GOLDEN_RATIO_PRIME_32) & mask);
 375 }
 376
 377 /**
 378  * Generic u64 hash algorithm.
 379  */
 380 static inline unsigned
 381 lh_u64_hash(__u64 key, unsigned mask)
 382 {
 383         RETURN((unsigned)(key * GOLDEN_RATIO_PRIME_64) & mask);
 384 }
 385
 386 #define lh_for_each_bucket(lh, lhb, pos)         \
 387         for (pos = 0;                            \
 388              pos < lh->lh_cur_size &&            \
 389              ({ lhb = &lh->lh_buckets[i]; 1; }); \
 390              pos++)
 391
 392 #endif /* __CLASS_HASH_H */