libcfs/include/libcfs/linux/linux-hash.h

   1 /*
   2  * GPL HEADER START
   3  *
   4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   5  *
   6  * This program is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License version 2 only,
   8  * as published by the Free Software Foundation.
   9  *
  10  * This program is distributed in the hope that it will be useful, but
  11  * WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * General Public License version 2 for more details (a copy is included
  14  * in the LICENSE file that accompanied this code).
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * version 2 along with this program; If not, see
  18  * http://www.gnu.org/licenses/gpl-2.0.html
  19  *
  20  * GPL HEADER END
  21  */
  22
  23 #ifndef __LIBCFS_LINUX_HASH_H__
  24 #define __LIBCFS_LINUX_HASH_H__
  25
  26 #include <linux/dcache.h>
  27 #include <linux/rhashtable.h>
  28
  29 u64 cfs_hashlen_string(const void *salt, const char *name);
  30
  31 #ifndef hashlen_hash
  32 #define hashlen_hash(hashlen) ((u32)(hashlen))
  33 #endif
  34
  35 #ifndef HAVE_STRINGHASH
  36 #ifndef hashlen_create
  37 #define hashlen_create(hash, len) ((u64)(len)<<32 | (u32)(hash))
  38 #endif
  39 #endif /* !HAVE_STRINGHASH */
  40
  41 #ifdef HAVE_BROKEN_HASH_64
  42
  43 #define GOLDEN_RATIO_32 0x61C88647
  44 #define GOLDEN_RATIO_64 0x61C8864680B583EBull
  45
  46 static inline u32 cfs_hash_32(u32 val, unsigned int bits)
  47 {
  48         /* High bits are more random, so use them. */
  49         return (val * GOLDEN_RATIO_32) >> (32 - bits);
  50 }
  51
  52 static __always_inline u32 cfs_hash_64(u64 val, unsigned int bits)
  53 {
  54 #if BITS_PER_LONG == 64
  55         /* 64x64-bit multiply is efficient on all 64-bit processors */
  56         return val * GOLDEN_RATIO_64 >> (64 - bits);
  57 #else
  58         /* Hash 64 bits using only 32x32-bit multiply. */
  59         return cfs_hash_32(((u32)val ^ ((val >> 32) * GOLDEN_RATIO_32)), bits);
  60 #endif
  61 }
  62
  63 #if BITS_PER_LONG == 32
  64 #define cfs_hash_long(val, bits) cfs_hash_32(val, bits)
  65 #elif BITS_PER_LONG == 64
  66 #define cfs_hash_long(val, bits) cfs_hash_64(val, bits)
  67 #else
  68 #error Wordsize not 32 or 64
  69 #endif
  70
  71 #else
  72
  73 #define cfs_hash_32 hash_32
  74 #define cfs_hash_64 hash_64
  75 #define cfs_hash_long hash_long
  76
  77 #endif /* HAVE_BROKEN_HASH_64 */
  78
  79 #ifndef HAVE_RHASHTABLE_WALK_ENTER
  80 static int rhashtable_walk_enter(struct rhashtable *ht,
  81                                  struct rhashtable_iter *iter)
  82 {
  83 #ifdef HAVE_3ARG_RHASHTABLE_WALK_INIT
  84         return rhashtable_walk_init(ht, iter, GFP_KERNEL);
  85 #else
  86         return rhashtable_walk_init(ht, iter);
  87 #endif
  88 }
  89 #endif
  90
  91 #ifndef HAVE_RHLTABLE
  92 struct rhlist_head {
  93         struct rhash_head               rhead;
  94         struct rhlist_head __rcu        *next;
  95 };
  96
  97 struct rhltable {
  98         struct rhashtable ht;
  99 };
 100
 101 #define rhl_for_each_entry_rcu(tpos, pos, list, member)                 \
 102         for (pos = list; pos && rht_entry(tpos, pos, member);           \
 103                 pos = rcu_dereference_raw(pos->next))
 104
 105 static inline int rhltable_init(struct rhltable *hlt,
 106                                 const struct rhashtable_params *params)
 107 {
 108         return rhashtable_init(&hlt->ht, params);
 109 }
 110
 111 static inline struct rhlist_head *rhltable_lookup(
 112         struct rhltable *hlt, const void *key,
 113         const struct rhashtable_params params)
 114 {
 115         struct rhashtable *ht = &hlt->ht;
 116         struct rhashtable_compare_arg arg = {
 117                 .ht = ht,
 118                 .key = key,
 119         };
 120         struct bucket_table *tbl;
 121         struct rhash_head *he;
 122         unsigned int hash;
 123
 124         tbl = rht_dereference_rcu(ht->tbl, ht);
 125 restart:
 126         hash = rht_key_hashfn(ht, tbl, key, params);
 127         rht_for_each_rcu(he, tbl, hash) {
 128                 if (params.obj_cmpfn ?
 129                     params.obj_cmpfn(&arg, rht_obj(ht, he)) :
 130                     rhashtable_compare(&arg, rht_obj(ht, he)))
 131                         continue;
 132                 return he ? container_of(he, struct rhlist_head, rhead) : NULL;
 133         }
 134
 135         /* Ensure we see any new tables. */
 136         smp_rmb();
 137
 138         tbl = rht_dereference_rcu(tbl->future_tbl, ht);
 139         if (unlikely(tbl))
 140                 goto restart;
 141
 142         return NULL;
 143 }
 144
 145 static inline int rhltable_insert_key(
 146         struct rhltable *hlt, const void *key, struct rhlist_head *list,
 147         const struct rhashtable_params params)
 148 {
 149 #ifdef HAVE_HASHTABLE_INSERT_FAST_RETURN_INT
 150         return __rhashtable_insert_fast(&hlt->ht, key, &list->rhead,
 151                                         params);
 152 #else
 153         return PTR_ERR(__rhashtable_insert_fast(&hlt->ht, key, &list->rhead,
 154                                                 params));
 155 #endif
 156 }
 157
 158 static inline int rhltable_remove(
 159         struct rhltable *hlt, struct rhlist_head *list,
 160         const struct rhashtable_params params)
 161 {
 162         return rhashtable_remove_fast(&hlt->ht, &list->rhead, params);
 163 }
 164
 165 static inline void rhltable_free_and_destroy(struct rhltable *hlt,
 166                                              void (*free_fn)(void *ptr,
 167                                                              void *arg),
 168                                              void *arg)
 169 {
 170         rhashtable_free_and_destroy(&hlt->ht, free_fn, arg);
 171 }
 172
 173 static inline void rhltable_destroy(struct rhltable *hlt)
 174 {
 175         rhltable_free_and_destroy(hlt, NULL, NULL);
 176 }
 177
 178 static inline void rhltable_walk_enter(struct rhltable *hlt,
 179                                        struct rhashtable_iter *iter)
 180 {
 181         rhashtable_walk_enter(&hlt->ht, iter);
 182 }
 183 #endif /* !HAVE_RHLTABLE */
 184
 185 #ifndef HAVE_RHASHTABLE_LOOKUP_GET_INSERT_FAST
 186 /**
 187  * rhashtable_lookup_get_insert_fast - lookup and insert object into hash table
 188  * @ht:         hash table
 189  * @obj:        pointer to hash head inside object
 190  * @params:     hash table parameters
 191  *
 192  * Just like rhashtable_lookup_insert_fast(), but this function returns the
 193  * object if it exists, NULL if it did not and the insertion was successful,
 194  * and an ERR_PTR otherwise.
 195  */
 196 static inline void *rhashtable_lookup_get_insert_fast(
 197         struct rhashtable *ht, struct rhash_head *obj,
 198         const struct rhashtable_params params)
 199 {
 200         const char *key;
 201         void *ret;
 202         int rc;
 203
 204         rc = rhashtable_lookup_insert_fast(ht, obj, params);
 205         switch (rc) {
 206         case -EEXIST:
 207                 key = rht_obj(ht, obj);
 208                 ret = rhashtable_lookup_fast(ht, key, params);
 209                 break;
 210         case 0:
 211                 ret = NULL;
 212                 break;
 213         default:
 214                 ret = ERR_PTR(rc);
 215                 break;
 216         }
 217         return ret;
 218 }
 219 #endif /* !HAVE_RHASHTABLE_LOOKUP_GET_INSERT_FAST */
 220
 221 #ifndef HAVE_RHASHTABLE_LOOKUP
 222 /*
 223  * The function rhashtable_lookup() and rhashtable_lookup_fast()
 224  * are almost the same except rhashtable_lookup() doesn't
 225  * take the RCU read lock. Since this is the case and only
 226  * SLES12 SP3 lacks rhashtable_lookup() just duplicate the
 227  * SLES12 SP3 rhashtable_lookup_fast() minus the RCU read lock.
 228  */
 229 static inline void *rhashtable_lookup(
 230         struct rhashtable *ht, const void *key,
 231         const struct rhashtable_params params)
 232 {
 233         struct rhashtable_compare_arg arg = {
 234                 .ht = ht,
 235                 .key = key,
 236         };
 237         const struct bucket_table *tbl;
 238         struct rhash_head *he;
 239         unsigned int hash;
 240
 241         tbl = rht_dereference_rcu(ht->tbl, ht);
 242 restart:
 243         hash = rht_key_hashfn(ht, tbl, key, params);
 244         rht_for_each_rcu(he, tbl, hash) {
 245                 if (params.obj_cmpfn ?
 246                     params.obj_cmpfn(&arg, rht_obj(ht, he)) :
 247                     rhashtable_compare(&arg, rht_obj(ht, he)))
 248                         continue;
 249                 return rht_obj(ht, he);
 250         }
 251
 252         /* Ensure we see any new tables. */
 253         smp_rmb();
 254
 255         tbl = rht_dereference_rcu(tbl->future_tbl, ht);
 256         if (unlikely(tbl))
 257                 goto restart;
 258
 259         return NULL;
 260 }
 261 #endif /* !HAVE_RHASHTABLE_LOOKUP */
 262
 263 #ifndef HAVE_RHT_BUCKET_VAR
 264 static inline struct rhash_head __rcu **rht_bucket_var(
 265         struct bucket_table *tbl, unsigned int hash)
 266 {
 267         return &tbl->buckets[hash];
 268 }
 269 #endif
 270
 271 #ifndef HAVE_RHASHTABLE_REPLACE
 272 /* Internal function, please use rhashtable_replace_fast() instead */
 273 static inline int __rhashtable_replace_fast(
 274         struct rhashtable *ht, struct bucket_table *tbl,
 275         struct rhash_head *obj_old, struct rhash_head *obj_new,
 276         const struct rhashtable_params params)
 277 {
 278         struct rhash_head __rcu **pprev;
 279         struct rhash_head *he;
 280         spinlock_t *lock;
 281         unsigned int hash;
 282         int err = -ENOENT;
 283
 284         /* Minimally, the old and new objects must have same hash
 285          * (which should mean identifiers are the same).
 286          */
 287         hash = rht_head_hashfn(ht, tbl, obj_old, params);
 288         if (hash != rht_head_hashfn(ht, tbl, obj_new, params))
 289                 return -EINVAL;
 290
 291         lock = rht_bucket_lock(tbl, hash);
 292
 293         spin_lock_bh(lock);
 294
 295         pprev = rht_bucket_var(tbl, hash);
 296         rht_for_each_continue(he, *pprev, tbl, hash) {
 297                 if (he != obj_old) {
 298                         pprev = &he->next;
 299                         continue;
 300                 }
 301
 302                 rcu_assign_pointer(obj_new->next, obj_old->next);
 303                 rcu_assign_pointer(*pprev, obj_new);
 304                 err = 0;
 305                 break;
 306         }
 307
 308         spin_unlock_bh(lock);
 309
 310         return err;
 311 }
 312
 313 /**
 314  * rhashtable_replace_fast - replace an object in hash table
 315  * @ht:         hash table
 316  * @obj_old:    pointer to hash head inside object being replaced
 317  * @obj_new:    pointer to hash head inside object which is new
 318  * @params:     hash table parameters
 319  *
 320  * Replacing an object doesn't affect the number of elements in the hash table
 321  * or bucket, so we don't need to worry about shrinking or expanding the
 322  * table here.
 323  *
 324  * Returns zero on success, -ENOENT if the entry could not be found,
 325  * -EINVAL if hash is not the same for the old and new objects.
 326  */
 327 static inline int rhashtable_replace_fast(
 328         struct rhashtable *ht, struct rhash_head *obj_old,
 329         struct rhash_head *obj_new,
 330         const struct rhashtable_params params)
 331 {
 332         struct bucket_table *tbl;
 333         int err;
 334
 335         rcu_read_lock();
 336
 337         tbl = rht_dereference_rcu(ht->tbl, ht);
 338
 339         /* Because we have already taken (and released) the bucket
 340          * lock in old_tbl, if we find that future_tbl is not yet
 341          * visible then that guarantees the entry to still be in
 342          * the old tbl if it exists.
 343          */
 344         while ((err = __rhashtable_replace_fast(ht, tbl, obj_old,
 345                                                 obj_new, params)) &&
 346                (tbl = rht_dereference_rcu(tbl->future_tbl, ht)))
 347                 ;
 348
 349         rcu_read_unlock();
 350
 351         return err;
 352 }
 353 #endif /* HAVE_RHASHTABLE_REPLACE */
 354
 355 #endif /* __LIBCFS_LINUX_HASH_H__ */