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 #else
  63
  64 #define cfs_hash_32     hash_32
  65 #define cfs_hash_64     hash_64
  66
  67 #endif /* HAVE_BROKEN_HASH_64 */
  68
  69 #ifndef HAVE_RHASHTABLE_WALK_ENTER
  70 static int rhashtable_walk_enter(struct rhashtable *ht,
  71                                  struct rhashtable_iter *iter)
  72 {
  73 #ifdef HAVE_3ARG_RHASHTABLE_WALK_INIT
  74         return rhashtable_walk_init(ht, iter, GFP_KERNEL);
  75 #else
  76         return rhashtable_walk_init(ht, iter);
  77 #endif
  78 }
  79 #endif
  80
  81 #ifndef HAVE_RHLTABLE
  82 struct rhlist_head {
  83         struct rhash_head               rhead;
  84         struct rhlist_head __rcu        *next;
  85 };
  86
  87 struct rhltable {
  88         struct rhashtable ht;
  89 };
  90
  91 #define rhl_for_each_entry_rcu(tpos, pos, list, member)                 \
  92         for (pos = list; pos && rht_entry(tpos, pos, member);           \
  93                 pos = rcu_dereference_raw(pos->next))
  94
  95 static inline int rhltable_init(struct rhltable *hlt,
  96                                 const struct rhashtable_params *params)
  97 {
  98         return rhashtable_init(&hlt->ht, params);
  99 }
 100
 101 static inline struct rhlist_head *rhltable_lookup(
 102         struct rhltable *hlt, const void *key,
 103         const struct rhashtable_params params)
 104 {
 105         struct rhashtable *ht = &hlt->ht;
 106         struct rhashtable_compare_arg arg = {
 107                 .ht = ht,
 108                 .key = key,
 109         };
 110         struct bucket_table *tbl;
 111         struct rhash_head *he;
 112         unsigned int hash;
 113
 114         tbl = rht_dereference_rcu(ht->tbl, ht);
 115 restart:
 116         hash = rht_key_hashfn(ht, tbl, key, params);
 117         rht_for_each_rcu(he, tbl, hash) {
 118                 if (params.obj_cmpfn ?
 119                     params.obj_cmpfn(&arg, rht_obj(ht, he)) :
 120                     rhashtable_compare(&arg, rht_obj(ht, he)))
 121                         continue;
 122                 return he ? container_of(he, struct rhlist_head, rhead) : NULL;
 123         }
 124
 125         /* Ensure we see any new tables. */
 126         smp_rmb();
 127
 128         tbl = rht_dereference_rcu(tbl->future_tbl, ht);
 129         if (unlikely(tbl))
 130                 goto restart;
 131
 132         return NULL;
 133 }
 134
 135 static inline int rhltable_insert_key(
 136         struct rhltable *hlt, const void *key, struct rhlist_head *list,
 137         const struct rhashtable_params params)
 138 {
 139 #ifdef HAVE_HASHTABLE_INSERT_FAST_RETURN_INT
 140         return __rhashtable_insert_fast(&hlt->ht, key, &list->rhead,
 141                                         params);
 142 #else
 143         return PTR_ERR(__rhashtable_insert_fast(&hlt->ht, key, &list->rhead,
 144                                                 params));
 145 #endif
 146 }
 147
 148 static inline int rhltable_remove(
 149         struct rhltable *hlt, struct rhlist_head *list,
 150         const struct rhashtable_params params)
 151 {
 152         return rhashtable_remove_fast(&hlt->ht, &list->rhead, params);
 153 }
 154
 155 static inline void rhltable_free_and_destroy(struct rhltable *hlt,
 156                                              void (*free_fn)(void *ptr,
 157                                                              void *arg),
 158                                              void *arg)
 159 {
 160         rhashtable_free_and_destroy(&hlt->ht, free_fn, arg);
 161 }
 162
 163 static inline void rhltable_destroy(struct rhltable *hlt)
 164 {
 165         rhltable_free_and_destroy(hlt, NULL, NULL);
 166 }
 167
 168 static inline void rhltable_walk_enter(struct rhltable *hlt,
 169                                        struct rhashtable_iter *iter)
 170 {
 171         rhashtable_walk_enter(&hlt->ht, iter);
 172 }
 173 #endif /* !HAVE_RHLTABLE */
 174
 175 #ifndef HAVE_RHASHTABLE_LOOKUP_GET_INSERT_FAST
 176 /**
 177  * rhashtable_lookup_get_insert_fast - lookup and insert object into hash table
 178  * @ht:         hash table
 179  * @obj:        pointer to hash head inside object
 180  * @params:     hash table parameters
 181  *
 182  * Just like rhashtable_lookup_insert_fast(), but this function returns the
 183  * object if it exists, NULL if it did not and the insertion was successful,
 184  * and an ERR_PTR otherwise.
 185  */
 186 static inline void *rhashtable_lookup_get_insert_fast(
 187         struct rhashtable *ht, struct rhash_head *obj,
 188         const struct rhashtable_params params)
 189 {
 190         const char *key;
 191         void *ret;
 192         int rc;
 193
 194         rc = rhashtable_lookup_insert_fast(ht, obj, params);
 195         switch (rc) {
 196         case -EEXIST:
 197                 key = rht_obj(ht, obj);
 198                 ret = rhashtable_lookup_fast(ht, key, params);
 199                 break;
 200         case 0:
 201                 ret = NULL;
 202                 break;
 203         default:
 204                 ret = ERR_PTR(rc);
 205                 break;
 206         }
 207         return ret;
 208 }
 209 #endif /* !HAVE_RHASHTABLE_LOOKUP_GET_INSERT_FAST */
 210
 211 #ifndef HAVE_RHASHTABLE_LOOKUP
 212 /*
 213  * The function rhashtable_lookup() and rhashtable_lookup_fast()
 214  * are almost the same except rhashtable_lookup() doesn't
 215  * take the RCU read lock. Since this is the case and only
 216  * SLES12 SP3 lacks rhashtable_lookup() just duplicate the
 217  * SLES12 SP3 rhashtable_lookup_fast() minus the RCU read lock.
 218  */
 219 static inline void *rhashtable_lookup(
 220         struct rhashtable *ht, const void *key,
 221         const struct rhashtable_params params)
 222 {
 223         struct rhashtable_compare_arg arg = {
 224                 .ht = ht,
 225                 .key = key,
 226         };
 227         const struct bucket_table *tbl;
 228         struct rhash_head *he;
 229         unsigned int hash;
 230
 231         tbl = rht_dereference_rcu(ht->tbl, ht);
 232 restart:
 233         hash = rht_key_hashfn(ht, tbl, key, params);
 234         rht_for_each_rcu(he, tbl, hash) {
 235                 if (params.obj_cmpfn ?
 236                     params.obj_cmpfn(&arg, rht_obj(ht, he)) :
 237                     rhashtable_compare(&arg, rht_obj(ht, he)))
 238                         continue;
 239                 return rht_obj(ht, he);
 240         }
 241
 242         /* Ensure we see any new tables. */
 243         smp_rmb();
 244
 245         tbl = rht_dereference_rcu(tbl->future_tbl, ht);
 246         if (unlikely(tbl))
 247                 goto restart;
 248
 249         return NULL;
 250 }
 251 #endif /* !HAVE_RHASHTABLE_LOOKUP */
 252
 253 #ifndef HAVE_RHT_BUCKET_VAR
 254 static inline struct rhash_head __rcu **rht_bucket_var(
 255         struct bucket_table *tbl, unsigned int hash)
 256 {
 257         return &tbl->buckets[hash];
 258 }
 259 #endif
 260
 261 #ifndef HAVE_RHASHTABLE_REPLACE
 262 /* Internal function, please use rhashtable_replace_fast() instead */
 263 static inline int __rhashtable_replace_fast(
 264         struct rhashtable *ht, struct bucket_table *tbl,
 265         struct rhash_head *obj_old, struct rhash_head *obj_new,
 266         const struct rhashtable_params params)
 267 {
 268         struct rhash_head __rcu **pprev;
 269         struct rhash_head *he;
 270         spinlock_t *lock;
 271         unsigned int hash;
 272         int err = -ENOENT;
 273
 274         /* Minimally, the old and new objects must have same hash
 275          * (which should mean identifiers are the same).
 276          */
 277         hash = rht_head_hashfn(ht, tbl, obj_old, params);
 278         if (hash != rht_head_hashfn(ht, tbl, obj_new, params))
 279                 return -EINVAL;
 280
 281         lock = rht_bucket_lock(tbl, hash);
 282
 283         spin_lock_bh(lock);
 284
 285         pprev = rht_bucket_var(tbl, hash);
 286         rht_for_each_continue(he, *pprev, tbl, hash) {
 287                 if (he != obj_old) {
 288                         pprev = &he->next;
 289                         continue;
 290                 }
 291
 292                 rcu_assign_pointer(obj_new->next, obj_old->next);
 293                 rcu_assign_pointer(*pprev, obj_new);
 294                 err = 0;
 295                 break;
 296         }
 297
 298         spin_unlock_bh(lock);
 299
 300         return err;
 301 }
 302
 303 /**
 304  * rhashtable_replace_fast - replace an object in hash table
 305  * @ht:         hash table
 306  * @obj_old:    pointer to hash head inside object being replaced
 307  * @obj_new:    pointer to hash head inside object which is new
 308  * @params:     hash table parameters
 309  *
 310  * Replacing an object doesn't affect the number of elements in the hash table
 311  * or bucket, so we don't need to worry about shrinking or expanding the
 312  * table here.
 313  *
 314  * Returns zero on success, -ENOENT if the entry could not be found,
 315  * -EINVAL if hash is not the same for the old and new objects.
 316  */
 317 static inline int rhashtable_replace_fast(
 318         struct rhashtable *ht, struct rhash_head *obj_old,
 319         struct rhash_head *obj_new,
 320         const struct rhashtable_params params)
 321 {
 322         struct bucket_table *tbl;
 323         int err;
 324
 325         rcu_read_lock();
 326
 327         tbl = rht_dereference_rcu(ht->tbl, ht);
 328
 329         /* Because we have already taken (and released) the bucket
 330          * lock in old_tbl, if we find that future_tbl is not yet
 331          * visible then that guarantees the entry to still be in
 332          * the old tbl if it exists.
 333          */
 334         while ((err = __rhashtable_replace_fast(ht, tbl, obj_old,
 335                                                 obj_new, params)) &&
 336                (tbl = rht_dereference_rcu(tbl->future_tbl, ht)))
 337                 ;
 338
 339         rcu_read_unlock();
 340
 341         return err;
 342 }
 343 #endif /* HAVE_RHASHTABLE_REPLACE */
 344
 345 #endif /* __LIBCFS_LINUX_HASH_H__ */