git.sesse.net Git - bcachefs-tools-debian/blob - include/linux/rhashtable.h

   1 /*
   2  * Resizable, Scalable, Concurrent Hash Table
   3  *
   4  * Copyright (c) 2015 Herbert Xu <herbert@gondor.apana.org.au>
   5  * Copyright (c) 2014-2015 Thomas Graf <tgraf@suug.ch>
   6  * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
   7  *
   8  * Code partially derived from nft_hash
   9  * Rewritten with rehash code from br_multicast plus single list
  10  * pointer as suggested by Josh Triplett
  11  *
  12  * This program is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU General Public License version 2 as
  14  * published by the Free Software Foundation.
  15  */
  16
  17 #ifndef _LINUX_RHASHTABLE_H
  18 #define _LINUX_RHASHTABLE_H
  19
  20 #include <linux/atomic.h>
  21 #include <linux/cache.h>
  22 #include <linux/compiler.h>
  23 #include <linux/err.h>
  24 #include <linux/errno.h>
  25 #include <linux/jhash.h>
  26 #include <linux/workqueue.h>
  27 #include <linux/mutex.h>
  28 #include <linux/spinlock.h>
  29 #include <linux/rcupdate.h>
  30
  31 #define RHT_BASE_BITS           4
  32 #define RHT_HASH_BITS           27
  33 #define RHT_BASE_SHIFT          RHT_HASH_BITS
  34 #define RHT_HASH_RESERVED_SPACE (RHT_BASE_BITS + 1)
  35
  36 struct rhash_head {
  37         struct rhash_head __rcu         *next;
  38 };
  39
  40 struct bucket_table {
  41         unsigned int            size;
  42         unsigned int            rehash;
  43         u32                     hash_rnd;
  44         unsigned int            locks_mask;
  45         spinlock_t              *locks;
  46         struct list_head        walkers;
  47         struct rcu_head         rcu;
  48
  49         struct bucket_table __rcu *future_tbl;
  50
  51         struct rhash_head __rcu *buckets[] ____cacheline_aligned_in_smp;
  52 };
  53
  54 struct rhashtable_compare_arg {
  55         struct rhashtable *ht;
  56         const void *key;
  57 };
  58
  59 typedef u32 (*rht_hashfn_t)(const void *data, u32 len, u32 seed);
  60 typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 len, u32 seed);
  61 typedef int (*rht_obj_cmpfn_t)(struct rhashtable_compare_arg *arg,
  62                                const void *obj);
  63
  64 struct rhashtable_params {
  65         size_t                  nelem_hint;
  66         size_t                  key_len;
  67         size_t                  key_offset;
  68         size_t                  head_offset;
  69         unsigned int            insecure_max_entries;
  70         unsigned int            max_size;
  71         unsigned int            min_size;
  72         u32                     nulls_base;
  73         bool                    insecure_elasticity;
  74         bool                    automatic_shrinking;
  75         size_t                  locks_mul;
  76         rht_hashfn_t            hashfn;
  77         rht_obj_hashfn_t        obj_hashfn;
  78         rht_obj_cmpfn_t         obj_cmpfn;
  79 };
  80
  81 struct rhashtable {
  82         struct bucket_table __rcu       *tbl;
  83         atomic_t                        nelems;
  84         unsigned int                    key_len;
  85         unsigned int                    elasticity;
  86         struct rhashtable_params        p;
  87         struct work_struct              run_work;
  88         struct mutex                    mutex;
  89         spinlock_t                      lock;
  90 };
  91
  92 struct rhashtable_walker {
  93         struct list_head list;
  94         struct bucket_table *tbl;
  95 };
  96
  97 #define NULLS_MARKER(value) (1UL | (((long)value) << 1))
  98
  99 static inline unsigned long rht_marker(const struct rhashtable *ht, u32 hash)
 100 {
 101         return NULLS_MARKER(ht->p.nulls_base + hash);
 102 }
 103
 104 #define INIT_RHT_NULLS_HEAD(ptr, ht, hash) \
 105         ((ptr) = (typeof(ptr)) rht_marker(ht, hash))
 106
 107 static inline bool rht_is_a_nulls(const struct rhash_head *ptr)
 108 {
 109         return ((unsigned long) ptr & 1);
 110 }
 111
 112 static inline void *rht_obj(const struct rhashtable *ht,
 113                             const struct rhash_head *he)
 114 {
 115         return (char *)he - ht->p.head_offset;
 116 }
 117
 118 static inline unsigned int rht_bucket_index(const struct bucket_table *tbl,
 119                                             unsigned int hash)
 120 {
 121         return (hash >> RHT_HASH_RESERVED_SPACE) & (tbl->size - 1);
 122 }
 123
 124 static inline unsigned int rht_key_hashfn(
 125         struct rhashtable *ht, const struct bucket_table *tbl,
 126         const void *key, const struct rhashtable_params params)
 127 {
 128         unsigned int hash;
 129
 130         /* params must be equal to ht->p if it isn't constant. */
 131         if (!__builtin_constant_p(params.key_len))
 132                 hash = ht->p.hashfn(key, ht->key_len, tbl->hash_rnd);
 133         else if (params.key_len) {
 134                 unsigned int key_len = params.key_len;
 135
 136                 if (params.hashfn)
 137                         hash = params.hashfn(key, key_len, tbl->hash_rnd);
 138                 else if (key_len & (sizeof(u32) - 1))
 139                         hash = jhash(key, key_len, tbl->hash_rnd);
 140                 else
 141                         hash = jhash2(key, key_len / sizeof(u32),
 142                                       tbl->hash_rnd);
 143         } else {
 144                 unsigned int key_len = ht->p.key_len;
 145
 146                 if (params.hashfn)
 147                         hash = params.hashfn(key, key_len, tbl->hash_rnd);
 148                 else
 149                         hash = jhash(key, key_len, tbl->hash_rnd);
 150         }
 151
 152         return rht_bucket_index(tbl, hash);
 153 }
 154
 155 static inline unsigned int rht_head_hashfn(
 156         struct rhashtable *ht, const struct bucket_table *tbl,
 157         const struct rhash_head *he, const struct rhashtable_params params)
 158 {
 159         const char *ptr = rht_obj(ht, he);
 160
 161         return likely(params.obj_hashfn) ?
 162                rht_bucket_index(tbl, params.obj_hashfn(ptr, params.key_len ?:
 163                                                             ht->p.key_len,
 164                                                        tbl->hash_rnd)) :
 165                rht_key_hashfn(ht, tbl, ptr + params.key_offset, params);
 166 }
 167
 168 static inline bool rht_grow_above_75(const struct rhashtable *ht,
 169                                      const struct bucket_table *tbl)
 170 {
 171         /* Expand table when exceeding 75% load */
 172         return atomic_read(&ht->nelems) > (tbl->size / 4 * 3) &&
 173                (!ht->p.max_size || tbl->size < ht->p.max_size);
 174 }
 175
 176 static inline bool rht_shrink_below_30(const struct rhashtable *ht,
 177                                        const struct bucket_table *tbl)
 178 {
 179         /* Shrink table beneath 30% load */
 180         return atomic_read(&ht->nelems) < (tbl->size * 3 / 10) &&
 181                tbl->size > ht->p.min_size;
 182 }
 183
 184 static inline bool rht_grow_above_100(const struct rhashtable *ht,
 185                                       const struct bucket_table *tbl)
 186 {
 187         return atomic_read(&ht->nelems) > tbl->size &&
 188                 (!ht->p.max_size || tbl->size < ht->p.max_size);
 189 }
 190
 191 static inline bool rht_grow_above_max(const struct rhashtable *ht,
 192                                       const struct bucket_table *tbl)
 193 {
 194         return ht->p.insecure_max_entries &&
 195                atomic_read(&ht->nelems) >= ht->p.insecure_max_entries;
 196 }
 197
 198 static inline spinlock_t *rht_bucket_lock(const struct bucket_table *tbl,
 199                                           unsigned int hash)
 200 {
 201         return &tbl->locks[hash & tbl->locks_mask];
 202 }
 203
 204 int rhashtable_insert_rehash(struct rhashtable *, struct bucket_table *);
 205 struct bucket_table *rhashtable_insert_slow(struct rhashtable *,
 206                                             const void *,
 207                                             struct rhash_head *,
 208                                             struct bucket_table *);
 209
 210 int rhashtable_init(struct rhashtable *, const struct rhashtable_params *);
 211 void rhashtable_destroy(struct rhashtable *);
 212
 213 #define rht_dereference(p, ht)                  rcu_dereference(p)
 214 #define rht_dereference_rcu(p, ht)              rcu_dereference(p)
 215 #define rht_dereference_bucket(p, tbl, hash)    rcu_dereference(p)
 216 #define rht_dereference_bucket_rcu(p, tbl, hash) rcu_dereference(p)
 217
 218 #define rht_entry(tpos, pos, member) \
 219         ({ tpos = container_of(pos, typeof(*tpos), member); 1; })
 220
 221 #define rht_for_each_continue(pos, head, tbl, hash) \
 222         for (pos = rht_dereference_bucket(head, tbl, hash); \
 223              !rht_is_a_nulls(pos); \
 224              pos = rht_dereference_bucket((pos)->next, tbl, hash))
 225
 226 #define rht_for_each(pos, tbl, hash) \
 227         rht_for_each_continue(pos, (tbl)->buckets[hash], tbl, hash)
 228
 229 #define rht_for_each_rcu_continue(pos, head, tbl, hash)                 \
 230         for (({barrier(); }),                                           \
 231              pos = rht_dereference_bucket_rcu(head, tbl, hash);         \
 232              !rht_is_a_nulls(pos);                                      \
 233              pos = rcu_dereference_raw(pos->next))
 234
 235 #define rht_for_each_rcu(pos, tbl, hash)                                \
 236         rht_for_each_rcu_continue(pos, (tbl)->buckets[hash], tbl, hash)
 237
 238 #define rht_for_each_entry_rcu_continue(tpos, pos, head, tbl, hash, member) \
 239         for (({barrier(); }),                                               \
 240              pos = rht_dereference_bucket_rcu(head, tbl, hash);             \
 241              (!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member);        \
 242              pos = rht_dereference_bucket_rcu(pos->next, tbl, hash))
 243
 244 #define rht_for_each_entry_rcu(tpos, pos, tbl, hash, member)            \
 245         rht_for_each_entry_rcu_continue(tpos, pos, (tbl)->buckets[hash],\
 246                                         tbl, hash, member)
 247
 248 static inline int rhashtable_compare(struct rhashtable_compare_arg *arg,
 249                                      const void *obj)
 250 {
 251         struct rhashtable *ht = arg->ht;
 252         const char *ptr = obj;
 253
 254         return memcmp(ptr + ht->p.key_offset, arg->key, ht->p.key_len);
 255 }
 256
 257 static inline void *rhashtable_lookup_fast(
 258         struct rhashtable *ht, const void *key,
 259         const struct rhashtable_params params)
 260 {
 261         struct rhashtable_compare_arg arg = {
 262                 .ht = ht,
 263                 .key = key,
 264         };
 265         const struct bucket_table *tbl;
 266         struct rhash_head *he;
 267         unsigned int hash;
 268
 269         rcu_read_lock();
 270
 271         tbl = rht_dereference_rcu(ht->tbl, ht);
 272 restart:
 273         hash = rht_key_hashfn(ht, tbl, key, params);
 274         rht_for_each_rcu(he, tbl, hash) {
 275                 if (params.obj_cmpfn ?
 276                     params.obj_cmpfn(&arg, rht_obj(ht, he)) :
 277                     rhashtable_compare(&arg, rht_obj(ht, he)))
 278                         continue;
 279                 rcu_read_unlock();
 280                 return rht_obj(ht, he);
 281         }
 282
 283         /* Ensure we see any new tables. */
 284         smp_rmb();
 285
 286         tbl = rht_dereference_rcu(tbl->future_tbl, ht);
 287         if (unlikely(tbl))
 288                 goto restart;
 289         rcu_read_unlock();
 290
 291         return NULL;
 292 }
 293
 294 static inline int __rhashtable_insert_fast(
 295         struct rhashtable *ht, const void *key, struct rhash_head *obj,
 296         const struct rhashtable_params params)
 297 {
 298         struct rhashtable_compare_arg arg = {
 299                 .ht = ht,
 300                 .key = key,
 301         };
 302         struct bucket_table *tbl, *new_tbl;
 303         struct rhash_head *head;
 304         spinlock_t *lock;
 305         unsigned int elasticity;
 306         unsigned int hash;
 307         int err;
 308
 309 restart:
 310         rcu_read_lock();
 311
 312         tbl = rht_dereference_rcu(ht->tbl, ht);
 313
 314         /* All insertions must grab the oldest table containing
 315          * the hashed bucket that is yet to be rehashed.
 316          */
 317         for (;;) {
 318                 hash = rht_head_hashfn(ht, tbl, obj, params);
 319                 lock = rht_bucket_lock(tbl, hash);
 320                 spin_lock_bh(lock);
 321
 322                 if (tbl->rehash <= hash)
 323                         break;
 324
 325                 spin_unlock_bh(lock);
 326                 tbl = rht_dereference_rcu(tbl->future_tbl, ht);
 327         }
 328
 329         new_tbl = rht_dereference_rcu(tbl->future_tbl, ht);
 330         if (unlikely(new_tbl)) {
 331                 tbl = rhashtable_insert_slow(ht, key, obj, new_tbl);
 332                 if (!IS_ERR_OR_NULL(tbl))
 333                         goto slow_path;
 334
 335                 err = PTR_ERR(tbl);
 336                 goto out;
 337         }
 338
 339         err = -E2BIG;
 340         if (unlikely(rht_grow_above_max(ht, tbl)))
 341                 goto out;
 342
 343         if (unlikely(rht_grow_above_100(ht, tbl))) {
 344 slow_path:
 345                 spin_unlock_bh(lock);
 346                 err = rhashtable_insert_rehash(ht, tbl);
 347                 rcu_read_unlock();
 348                 if (err)
 349                         return err;
 350
 351                 goto restart;
 352         }
 353
 354         err = -EEXIST;
 355         elasticity = ht->elasticity;
 356         rht_for_each(head, tbl, hash) {
 357                 if (key &&
 358                     unlikely(!(params.obj_cmpfn ?
 359                                params.obj_cmpfn(&arg, rht_obj(ht, head)) :
 360                                rhashtable_compare(&arg, rht_obj(ht, head)))))
 361                         goto out;
 362                 if (!--elasticity)
 363                         goto slow_path;
 364         }
 365
 366         err = 0;
 367
 368         head = rht_dereference_bucket(tbl->buckets[hash], tbl, hash);
 369
 370         RCU_INIT_POINTER(obj->next, head);
 371
 372         rcu_assign_pointer(tbl->buckets[hash], obj);
 373
 374         atomic_inc(&ht->nelems);
 375         if (rht_grow_above_75(ht, tbl))
 376                 schedule_work(&ht->run_work);
 377
 378 out:
 379         spin_unlock_bh(lock);
 380         rcu_read_unlock();
 381
 382         return err;
 383 }
 384
 385 static inline int rhashtable_lookup_insert_fast(
 386         struct rhashtable *ht, struct rhash_head *obj,
 387         const struct rhashtable_params params)
 388 {
 389         const char *key = rht_obj(ht, obj);
 390
 391         BUG_ON(ht->p.obj_hashfn);
 392
 393         return __rhashtable_insert_fast(ht, key + ht->p.key_offset, obj,
 394                                         params);
 395 }
 396
 397 static inline int __rhashtable_remove_fast(
 398         struct rhashtable *ht, struct bucket_table *tbl,
 399         struct rhash_head *obj, const struct rhashtable_params params)
 400 {
 401         struct rhash_head __rcu **pprev;
 402         struct rhash_head *he;
 403         spinlock_t * lock;
 404         unsigned int hash;
 405         int err = -ENOENT;
 406
 407         hash = rht_head_hashfn(ht, tbl, obj, params);
 408         lock = rht_bucket_lock(tbl, hash);
 409
 410         spin_lock_bh(lock);
 411
 412         pprev = &tbl->buckets[hash];
 413         rht_for_each(he, tbl, hash) {
 414                 if (he != obj) {
 415                         pprev = &he->next;
 416                         continue;
 417                 }
 418
 419                 rcu_assign_pointer(*pprev, obj->next);
 420                 err = 0;
 421                 break;
 422         }
 423
 424         spin_unlock_bh(lock);
 425
 426         return err;
 427 }
 428
 429 static inline int rhashtable_remove_fast(
 430         struct rhashtable *ht, struct rhash_head *obj,
 431         const struct rhashtable_params params)
 432 {
 433         struct bucket_table *tbl;
 434         int err;
 435
 436         rcu_read_lock();
 437
 438         tbl = rht_dereference_rcu(ht->tbl, ht);
 439
 440         /* Because we have already taken (and released) the bucket
 441          * lock in old_tbl, if we find that future_tbl is not yet
 442          * visible then that guarantees the entry to still be in
 443          * the old tbl if it exists.
 444          */
 445         while ((err = __rhashtable_remove_fast(ht, tbl, obj, params)) &&
 446                (tbl = rht_dereference_rcu(tbl->future_tbl, ht)))
 447                 ;
 448
 449         if (err)
 450                 goto out;
 451
 452         atomic_dec(&ht->nelems);
 453         if (unlikely(ht->p.automatic_shrinking &&
 454                      rht_shrink_below_30(ht, tbl)))
 455                 schedule_work(&ht->run_work);
 456
 457 out:
 458         rcu_read_unlock();
 459
 460         return err;
 461 }
 462
 463 #endif /* _LINUX_RHASHTABLE_H */