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_RHLTABLE
  70 struct rhlist_head {
  71         struct rhash_head               rhead;
  72         struct rhlist_head __rcu        *next;
  73 };
  74
  75 struct rhltable {
  76         struct rhashtable ht;
  77 };
  78
  79 #define rhl_for_each_entry_rcu(tpos, pos, list, member)                 \
  80         for (pos = list; pos && rht_entry(tpos, pos, member);           \
  81                 pos = rcu_dereference_raw(pos->next))
  82
  83 static inline int rhltable_init(struct rhltable *hlt,
  84                                 const struct rhashtable_params *params)
  85 {
  86         return rhashtable_init(&hlt->ht, params);
  87 }
  88
  89 static inline struct rhlist_head *rhltable_lookup(
  90         struct rhltable *hlt, const void *key,
  91         const struct rhashtable_params params)
  92 {
  93         struct rhashtable *ht = &hlt->ht;
  94         struct rhashtable_compare_arg arg = {
  95                 .ht = ht,
  96                 .key = key,
  97         };
  98         struct bucket_table *tbl;
  99         struct rhash_head *he;
 100         unsigned int hash;
 101
 102         tbl = rht_dereference_rcu(ht->tbl, ht);
 103 restart:
 104         hash = rht_key_hashfn(ht, tbl, key, params);
 105         rht_for_each_rcu(he, tbl, hash) {
 106                 if (params.obj_cmpfn ?
 107                     params.obj_cmpfn(&arg, rht_obj(ht, he)) :
 108                     rhashtable_compare(&arg, rht_obj(ht, he)))
 109                         continue;
 110                 return he ? container_of(he, struct rhlist_head, rhead) : NULL;
 111         }
 112
 113         /* Ensure we see any new tables. */
 114         smp_rmb();
 115
 116         tbl = rht_dereference_rcu(tbl->future_tbl, ht);
 117         if (unlikely(tbl))
 118                 goto restart;
 119
 120         return NULL;
 121 }
 122
 123 static inline int rhltable_insert_key(
 124         struct rhltable *hlt, const void *key, struct rhlist_head *list,
 125         const struct rhashtable_params params)
 126 {
 127 #ifdef HAVE_HASHTABLE_INSERT_FAST_RETURN_INT
 128         return __rhashtable_insert_fast(&hlt->ht, key, &list->rhead,
 129                                         params);
 130 #else
 131         return PTR_ERR(__rhashtable_insert_fast(&hlt->ht, key, &list->rhead,
 132                                                 params));
 133 #endif
 134 }
 135
 136 static inline int rhltable_remove(
 137         struct rhltable *hlt, struct rhlist_head *list,
 138         const struct rhashtable_params params)
 139 {
 140         return rhashtable_remove_fast(&hlt->ht, &list->rhead, params);
 141 }
 142
 143 static inline void rhltable_free_and_destroy(struct rhltable *hlt,
 144                                              void (*free_fn)(void *ptr,
 145                                                              void *arg),
 146                                              void *arg)
 147 {
 148         rhashtable_free_and_destroy(&hlt->ht, free_fn, arg);
 149 }
 150
 151 static inline void rhltable_destroy(struct rhltable *hlt)
 152 {
 153         rhltable_free_and_destroy(hlt, NULL, NULL);
 154 }
 155
 156 static inline void rhltable_walk_enter(struct rhltable *hlt,
 157                                        struct rhashtable_iter *iter)
 158 {
 159         rhashtable_walk_init(&hlt->ht, iter);
 160 }
 161 #endif /* !HAVE_RHLTABLE */
 162
 163 #ifndef HAVE_RHASHTABLE_LOOKUP_GET_INSERT_FAST
 164 /**
 165  * rhashtable_lookup_get_insert_fast - lookup and insert object into hash table
 166  * @ht:         hash table
 167  * @obj:        pointer to hash head inside object
 168  * @params:     hash table parameters
 169  *
 170  * Just like rhashtable_lookup_insert_fast(), but this function returns the
 171  * object if it exists, NULL if it did not and the insertion was successful,
 172  * and an ERR_PTR otherwise.
 173  */
 174 static inline void *rhashtable_lookup_get_insert_fast(
 175         struct rhashtable *ht, struct rhash_head *obj,
 176         const struct rhashtable_params params)
 177 {
 178         const char *key;
 179         void *ret;
 180         int rc;
 181
 182         rc = rhashtable_lookup_insert_fast(ht, obj, params);
 183         switch (rc) {
 184         case -EEXIST:
 185                 key = rht_obj(ht, obj);
 186                 ret = rhashtable_lookup_fast(ht, key, params);
 187                 break;
 188         case 0:
 189                 ret = NULL;
 190                 break;
 191         default:
 192                 ret = ERR_PTR(rc);
 193                 break;
 194         }
 195         return ret;
 196 }
 197 #endif /* !HAVE_RHASHTABLE_LOOKUP_GET_INSERT_FAST */
 198
 199 #ifndef HAVE_RHASHTABLE_LOOKUP
 200 /*
 201  * The function rhashtable_lookup() and rhashtable_lookup_fast()
 202  * are almost the same except rhashtable_lookup() doesn't
 203  * take the RCU read lock. Since this is the case and only
 204  * SLES12 SP3 lacks rhashtable_lookup() just duplicate the
 205  * SLES12 SP3 rhashtable_lookup_fast() minus the RCU read lock.
 206  */
 207 static inline void *rhashtable_lookup(
 208         struct rhashtable *ht, const void *key,
 209         const struct rhashtable_params params)
 210 {
 211         struct rhashtable_compare_arg arg = {
 212                 .ht = ht,
 213                 .key = key,
 214         };
 215         const struct bucket_table *tbl;
 216         struct rhash_head *he;
 217         unsigned int hash;
 218
 219         tbl = rht_dereference_rcu(ht->tbl, ht);
 220 restart:
 221         hash = rht_key_hashfn(ht, tbl, key, params);
 222         rht_for_each_rcu(he, tbl, hash) {
 223                 if (params.obj_cmpfn ?
 224                     params.obj_cmpfn(&arg, rht_obj(ht, he)) :
 225                     rhashtable_compare(&arg, rht_obj(ht, he)))
 226                         continue;
 227                 return rht_obj(ht, he);
 228         }
 229
 230         /* Ensure we see any new tables. */
 231         smp_rmb();
 232
 233         tbl = rht_dereference_rcu(tbl->future_tbl, ht);
 234         if (unlikely(tbl))
 235                 goto restart;
 236
 237         return NULL;
 238 }
 239 #endif /* !HAVE_RHASHTABLE_LOOKUP */
 240
 241 #endif /* __LIBCFS_LINUX_HASH_H__ */