include/linux/rhashtable.h

   1 /*
   2  * Resizable, Scalable, Concurrent Hash Table
   3  *
   4  * Copyright (c) 2014 Thomas Graf <tgraf@suug.ch>
   5  * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
   6  *
   7  * Based on the following paper by Josh Triplett, Paul E. McKenney
   8  * and Jonathan Walpole:
   9  * https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
  10  *
  11  * Code partially derived from nft_hash
  12  *
  13  * This program is free software; you can redistribute it and/or modify
  14  * it under the terms of the GNU General Public License version 2 as
  15  * published by the Free Software Foundation.
  16  */
  17
  18 #ifndef _LINUX_RHASHTABLE_H
  19 #define _LINUX_RHASHTABLE_H
  20
  21 #include <linux/compiler.h>
  22 #include <linux/list_nulls.h>
  23 #include <linux/workqueue.h>
  24 #include <linux/mutex.h>
  25 #include <linux/rcupdate.h>
  26
  27 /*
  28  * The end of the chain is marked with a special nulls marks which has
  29  * the following format:
  30  *
  31  * +-------+-----------------------------------------------------+-+
  32  * | Base  |                      Hash                           |1|
  33  * +-------+-----------------------------------------------------+-+
  34  *
  35  * Base (4 bits) : Reserved to distinguish between multiple tables.
  36  *                 Specified via &struct rhashtable_params.nulls_base.
  37  * Hash (27 bits): Full hash (unmasked) of first element added to bucket
  38  * 1 (1 bit)     : Nulls marker (always set)
  39  *
  40  * The remaining bits of the next pointer remain unused for now.
  41  */
  42 #define RHT_BASE_BITS           4
  43 #define RHT_HASH_BITS           27
  44 #define RHT_BASE_SHIFT          RHT_HASH_BITS
  45
  46 /* Base bits plus 1 bit for nulls marker */
  47 #define RHT_HASH_RESERVED_SPACE (RHT_BASE_BITS + 1)
  48
  49 struct rhash_head {
  50         struct rhash_head __rcu         *next;
  51 };
  52
  53 /**
  54  * struct bucket_table - Table of hash buckets
  55  * @size: Number of hash buckets
  56  * @rehash: Current bucket being rehashed
  57  * @hash_rnd: Random seed to fold into hash
  58  * @locks_mask: Mask to apply before accessing locks[]
  59  * @locks: Array of spinlocks protecting individual buckets
  60  * @walkers: List of active walkers
  61  * @rcu: RCU structure for freeing the table
  62  * @future_tbl: Table under construction during rehashing
  63  * @buckets: size * hash buckets
  64  */
  65 struct bucket_table {
  66         unsigned int            size;
  67         unsigned int            rehash;
  68         u32                     hash_rnd;
  69         unsigned int            locks_mask;
  70         spinlock_t              *locks;
  71         struct list_head        walkers;
  72         struct rcu_head         rcu;
  73
  74         struct bucket_table __rcu *future_tbl;
  75
  76         struct rhash_head __rcu *buckets[] ____cacheline_aligned_in_smp;
  77 };
  78
  79 /**
  80  * struct rhashtable_compare_arg - Key for the function rhashtable_compare
  81  * @ht: Hash table
  82  * @key: Key to compare against
  83  */
  84 struct rhashtable_compare_arg {
  85         struct rhashtable *ht;
  86         const void *key;
  87 };
  88
  89 typedef u32 (*rht_hashfn_t)(const void *data, u32 len, u32 seed);
  90 typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 seed);
  91 typedef int (*rht_obj_cmpfn_t)(struct rhashtable_compare_arg *arg,
  92                                const void *obj);
  93
  94 struct rhashtable;
  95
  96 /**
  97  * struct rhashtable_params - Hash table construction parameters
  98  * @nelem_hint: Hint on number of elements, should be 75% of desired size
  99  * @key_len: Length of key
 100  * @key_offset: Offset of key in struct to be hashed
 101  * @head_offset: Offset of rhash_head in struct to be hashed
 102  * @max_size: Maximum size while expanding
 103  * @min_size: Minimum size while shrinking
 104  * @nulls_base: Base value to generate nulls marker
 105  * @locks_mul: Number of bucket locks to allocate per cpu (default: 128)
 106  * @hashfn: Function to hash key
 107  * @obj_hashfn: Function to hash object
 108  * @obj_cmpfn: Function to compare key with object
 109  */
 110 struct rhashtable_params {
 111         size_t                  nelem_hint;
 112         size_t                  key_len;
 113         size_t                  key_offset;
 114         size_t                  head_offset;
 115         unsigned int            max_size;
 116         unsigned int            min_size;
 117         u32                     nulls_base;
 118         size_t                  locks_mul;
 119         rht_hashfn_t            hashfn;
 120         rht_obj_hashfn_t        obj_hashfn;
 121         rht_obj_cmpfn_t         obj_cmpfn;
 122 };
 123
 124 /**
 125  * struct rhashtable - Hash table handle
 126  * @tbl: Bucket table
 127  * @nelems: Number of elements in table
 128  * @p: Configuration parameters
 129  * @run_work: Deferred worker to expand/shrink asynchronously
 130  * @mutex: Mutex to protect current/future table swapping
 131  * @being_destroyed: True if table is set up for destruction
 132  */
 133 struct rhashtable {
 134         struct bucket_table __rcu       *tbl;
 135         atomic_t                        nelems;
 136         bool                            being_destroyed;
 137         struct rhashtable_params        p;
 138         struct work_struct              run_work;
 139         struct mutex                    mutex;
 140 };
 141
 142 /**
 143  * struct rhashtable_walker - Hash table walker
 144  * @list: List entry on list of walkers
 145  * @tbl: The table that we were walking over
 146  */
 147 struct rhashtable_walker {
 148         struct list_head list;
 149         struct bucket_table *tbl;
 150 };
 151
 152 /**
 153  * struct rhashtable_iter - Hash table iterator, fits into netlink cb
 154  * @ht: Table to iterate through
 155  * @p: Current pointer
 156  * @walker: Associated rhashtable walker
 157  * @slot: Current slot
 158  * @skip: Number of entries to skip in slot
 159  */
 160 struct rhashtable_iter {
 161         struct rhashtable *ht;
 162         struct rhash_head *p;
 163         struct rhashtable_walker *walker;
 164         unsigned int slot;
 165         unsigned int skip;
 166 };
 167
 168 static inline unsigned long rht_marker(const struct rhashtable *ht, u32 hash)
 169 {
 170         return NULLS_MARKER(ht->p.nulls_base + hash);
 171 }
 172
 173 #define INIT_RHT_NULLS_HEAD(ptr, ht, hash) \
 174         ((ptr) = (typeof(ptr)) rht_marker(ht, hash))
 175
 176 static inline bool rht_is_a_nulls(const struct rhash_head *ptr)
 177 {
 178         return ((unsigned long) ptr & 1);
 179 }
 180
 181 static inline unsigned long rht_get_nulls_value(const struct rhash_head *ptr)
 182 {
 183         return ((unsigned long) ptr) >> 1;
 184 }
 185
 186 static inline void *rht_obj(const struct rhashtable *ht,
 187                             const struct rhash_head *he)
 188 {
 189         return (char *)he - ht->p.head_offset;
 190 }
 191
 192 static inline unsigned int rht_bucket_index(const struct bucket_table *tbl,
 193                                             unsigned int hash)
 194 {
 195         return (hash >> RHT_HASH_RESERVED_SPACE) & (tbl->size - 1);
 196 }
 197
 198 static inline unsigned int rht_key_hashfn(
 199         struct rhashtable *ht, const struct bucket_table *tbl,
 200         const void *key, const struct rhashtable_params params)
 201 {
 202         return rht_bucket_index(tbl, params.hashfn(key, params.key_len ?:
 203                                                         ht->p.key_len,
 204                                                    tbl->hash_rnd));
 205 }
 206
 207 static inline unsigned int rht_head_hashfn(
 208         struct rhashtable *ht, const struct bucket_table *tbl,
 209         const struct rhash_head *he, const struct rhashtable_params params)
 210 {
 211         const char *ptr = rht_obj(ht, he);
 212
 213         return likely(params.obj_hashfn) ?
 214                rht_bucket_index(tbl, params.obj_hashfn(ptr, tbl->hash_rnd)) :
 215                rht_key_hashfn(ht, tbl, ptr + params.key_offset, params);
 216 }
 217
 218 /**
 219  * rht_grow_above_75 - returns true if nelems > 0.75 * table-size
 220  * @ht:         hash table
 221  * @tbl:        current table
 222  */
 223 static inline bool rht_grow_above_75(const struct rhashtable *ht,
 224                                      const struct bucket_table *tbl)
 225 {
 226         /* Expand table when exceeding 75% load */
 227         return atomic_read(&ht->nelems) > (tbl->size / 4 * 3) &&
 228                (!ht->p.max_size || tbl->size < ht->p.max_size);
 229 }
 230
 231 /**
 232  * rht_shrink_below_30 - returns true if nelems < 0.3 * table-size
 233  * @ht:         hash table
 234  * @tbl:        current table
 235  */
 236 static inline bool rht_shrink_below_30(const struct rhashtable *ht,
 237                                        const struct bucket_table *tbl)
 238 {
 239         /* Shrink table beneath 30% load */
 240         return atomic_read(&ht->nelems) < (tbl->size * 3 / 10) &&
 241                tbl->size > ht->p.min_size;
 242 }
 243
 244 /* The bucket lock is selected based on the hash and protects mutations
 245  * on a group of hash buckets.
 246  *
 247  * A maximum of tbl->size/2 bucket locks is allocated. This ensures that
 248  * a single lock always covers both buckets which may both contains
 249  * entries which link to the same bucket of the old table during resizing.
 250  * This allows to simplify the locking as locking the bucket in both
 251  * tables during resize always guarantee protection.
 252  *
 253  * IMPORTANT: When holding the bucket lock of both the old and new table
 254  * during expansions and shrinking, the old bucket lock must always be
 255  * acquired first.
 256  */
 257 static inline spinlock_t *rht_bucket_lock(const struct bucket_table *tbl,
 258                                           unsigned int hash)
 259 {
 260         return &tbl->locks[hash & tbl->locks_mask];
 261 }
 262
 263 #ifdef CONFIG_PROVE_LOCKING
 264 int lockdep_rht_mutex_is_held(struct rhashtable *ht);
 265 int lockdep_rht_bucket_is_held(const struct bucket_table *tbl, u32 hash);
 266 #else
 267 static inline int lockdep_rht_mutex_is_held(struct rhashtable *ht)
 268 {
 269         return 1;
 270 }
 271
 272 static inline int lockdep_rht_bucket_is_held(const struct bucket_table *tbl,
 273                                              u32 hash)
 274 {
 275         return 1;
 276 }
 277 #endif /* CONFIG_PROVE_LOCKING */
 278
 279 int rhashtable_init(struct rhashtable *ht,
 280                     const struct rhashtable_params *params);
 281
 282 int rhashtable_insert_slow(struct rhashtable *ht, const void *key,
 283                            struct rhash_head *obj,
 284                            struct bucket_table *old_tbl);
 285 void rhashtable_insert(struct rhashtable *ht, struct rhash_head *node);
 286 bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *node);
 287
 288 int rhashtable_expand(struct rhashtable *ht);
 289 int rhashtable_shrink(struct rhashtable *ht);
 290
 291 void *rhashtable_lookup(struct rhashtable *ht, const void *key);
 292 void *rhashtable_lookup_compare(struct rhashtable *ht, const void *key,
 293                                 bool (*compare)(void *, void *), void *arg);
 294
 295 bool rhashtable_lookup_insert(struct rhashtable *ht, struct rhash_head *obj);
 296 bool rhashtable_lookup_compare_insert(struct rhashtable *ht,
 297                                       struct rhash_head *obj,
 298                                       bool (*compare)(void *, void *),
 299                                       void *arg);
 300
 301 int rhashtable_walk_init(struct rhashtable *ht, struct rhashtable_iter *iter);
 302 void rhashtable_walk_exit(struct rhashtable_iter *iter);
 303 int rhashtable_walk_start(struct rhashtable_iter *iter) __acquires(RCU);
 304 void *rhashtable_walk_next(struct rhashtable_iter *iter);
 305 void rhashtable_walk_stop(struct rhashtable_iter *iter) __releases(RCU);
 306
 307 void rhashtable_destroy(struct rhashtable *ht);
 308
 309 #define rht_dereference(p, ht) \
 310         rcu_dereference_protected(p, lockdep_rht_mutex_is_held(ht))
 311
 312 #define rht_dereference_rcu(p, ht) \
 313         rcu_dereference_check(p, lockdep_rht_mutex_is_held(ht))
 314
 315 #define rht_dereference_bucket(p, tbl, hash) \
 316         rcu_dereference_protected(p, lockdep_rht_bucket_is_held(tbl, hash))
 317
 318 #define rht_dereference_bucket_rcu(p, tbl, hash) \
 319         rcu_dereference_check(p, lockdep_rht_bucket_is_held(tbl, hash))
 320
 321 #define rht_entry(tpos, pos, member) \
 322         ({ tpos = container_of(pos, typeof(*tpos), member); 1; })
 323
 324 /**
 325  * rht_for_each_continue - continue iterating over hash chain
 326  * @pos:        the &struct rhash_head to use as a loop cursor.
 327  * @head:       the previous &struct rhash_head to continue from
 328  * @tbl:        the &struct bucket_table
 329  * @hash:       the hash value / bucket index
 330  */
 331 #define rht_for_each_continue(pos, head, tbl, hash) \
 332         for (pos = rht_dereference_bucket(head, tbl, hash); \
 333              !rht_is_a_nulls(pos); \
 334              pos = rht_dereference_bucket((pos)->next, tbl, hash))
 335
 336 /**
 337  * rht_for_each - iterate over hash chain
 338  * @pos:        the &struct rhash_head to use as a loop cursor.
 339  * @tbl:        the &struct bucket_table
 340  * @hash:       the hash value / bucket index
 341  */
 342 #define rht_for_each(pos, tbl, hash) \
 343         rht_for_each_continue(pos, (tbl)->buckets[hash], tbl, hash)
 344
 345 /**
 346  * rht_for_each_entry_continue - continue iterating over hash chain
 347  * @tpos:       the type * to use as a loop cursor.
 348  * @pos:        the &struct rhash_head to use as a loop cursor.
 349  * @head:       the previous &struct rhash_head to continue from
 350  * @tbl:        the &struct bucket_table
 351  * @hash:       the hash value / bucket index
 352  * @member:     name of the &struct rhash_head within the hashable struct.
 353  */
 354 #define rht_for_each_entry_continue(tpos, pos, head, tbl, hash, member) \
 355         for (pos = rht_dereference_bucket(head, tbl, hash);             \
 356              (!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member);    \
 357              pos = rht_dereference_bucket((pos)->next, tbl, hash))
 358
 359 /**
 360  * rht_for_each_entry - iterate over hash chain of given type
 361  * @tpos:       the type * to use as a loop cursor.
 362  * @pos:        the &struct rhash_head to use as a loop cursor.
 363  * @tbl:        the &struct bucket_table
 364  * @hash:       the hash value / bucket index
 365  * @member:     name of the &struct rhash_head within the hashable struct.
 366  */
 367 #define rht_for_each_entry(tpos, pos, tbl, hash, member)                \
 368         rht_for_each_entry_continue(tpos, pos, (tbl)->buckets[hash],    \
 369                                     tbl, hash, member)
 370
 371 /**
 372  * rht_for_each_entry_safe - safely iterate over hash chain of given type
 373  * @tpos:       the type * to use as a loop cursor.
 374  * @pos:        the &struct rhash_head to use as a loop cursor.
 375  * @next:       the &struct rhash_head to use as next in loop cursor.
 376  * @tbl:        the &struct bucket_table
 377  * @hash:       the hash value / bucket index
 378  * @member:     name of the &struct rhash_head within the hashable struct.
 379  *
 380  * This hash chain list-traversal primitive allows for the looped code to
 381  * remove the loop cursor from the list.
 382  */
 383 #define rht_for_each_entry_safe(tpos, pos, next, tbl, hash, member)         \
 384         for (pos = rht_dereference_bucket((tbl)->buckets[hash], tbl, hash), \
 385              next = !rht_is_a_nulls(pos) ?                                  \
 386                        rht_dereference_bucket(pos->next, tbl, hash) : NULL; \
 387              (!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member);        \
 388              pos = next,                                                    \
 389              next = !rht_is_a_nulls(pos) ?                                  \
 390                        rht_dereference_bucket(pos->next, tbl, hash) : NULL)
 391
 392 /**
 393  * rht_for_each_rcu_continue - continue iterating over rcu hash chain
 394  * @pos:        the &struct rhash_head to use as a loop cursor.
 395  * @head:       the previous &struct rhash_head to continue from
 396  * @tbl:        the &struct bucket_table
 397  * @hash:       the hash value / bucket index
 398  *
 399  * This hash chain list-traversal primitive may safely run concurrently with
 400  * the _rcu mutation primitives such as rhashtable_insert() as long as the
 401  * traversal is guarded by rcu_read_lock().
 402  */
 403 #define rht_for_each_rcu_continue(pos, head, tbl, hash)                 \
 404         for (({barrier(); }),                                           \
 405              pos = rht_dereference_bucket_rcu(head, tbl, hash);         \
 406              !rht_is_a_nulls(pos);                                      \
 407              pos = rcu_dereference_raw(pos->next))
 408
 409 /**
 410  * rht_for_each_rcu - iterate over rcu hash chain
 411  * @pos:        the &struct rhash_head to use as a loop cursor.
 412  * @tbl:        the &struct bucket_table
 413  * @hash:       the hash value / bucket index
 414  *
 415  * This hash chain list-traversal primitive may safely run concurrently with
 416  * the _rcu mutation primitives such as rhashtable_insert() as long as the
 417  * traversal is guarded by rcu_read_lock().
 418  */
 419 #define rht_for_each_rcu(pos, tbl, hash)                                \
 420         rht_for_each_rcu_continue(pos, (tbl)->buckets[hash], tbl, hash)
 421
 422 /**
 423  * rht_for_each_entry_rcu_continue - continue iterating over rcu hash chain
 424  * @tpos:       the type * to use as a loop cursor.
 425  * @pos:        the &struct rhash_head to use as a loop cursor.
 426  * @head:       the previous &struct rhash_head to continue from
 427  * @tbl:        the &struct bucket_table
 428  * @hash:       the hash value / bucket index
 429  * @member:     name of the &struct rhash_head within the hashable struct.
 430  *
 431  * This hash chain list-traversal primitive may safely run concurrently with
 432  * the _rcu mutation primitives such as rhashtable_insert() as long as the
 433  * traversal is guarded by rcu_read_lock().
 434  */
 435 #define rht_for_each_entry_rcu_continue(tpos, pos, head, tbl, hash, member) \
 436         for (({barrier(); }),                                               \
 437              pos = rht_dereference_bucket_rcu(head, tbl, hash);             \
 438              (!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member);        \
 439              pos = rht_dereference_bucket_rcu(pos->next, tbl, hash))
 440
 441 /**
 442  * rht_for_each_entry_rcu - iterate over rcu hash chain of given type
 443  * @tpos:       the type * to use as a loop cursor.
 444  * @pos:        the &struct rhash_head to use as a loop cursor.
 445  * @tbl:        the &struct bucket_table
 446  * @hash:       the hash value / bucket index
 447  * @member:     name of the &struct rhash_head within the hashable struct.
 448  *
 449  * This hash chain list-traversal primitive may safely run concurrently with
 450  * the _rcu mutation primitives such as rhashtable_insert() as long as the
 451  * traversal is guarded by rcu_read_lock().
 452  */
 453 #define rht_for_each_entry_rcu(tpos, pos, tbl, hash, member)            \
 454         rht_for_each_entry_rcu_continue(tpos, pos, (tbl)->buckets[hash],\
 455                                         tbl, hash, member)
 456
 457 static inline int rhashtable_compare(struct rhashtable_compare_arg *arg,
 458                                      const void *obj)
 459 {
 460         struct rhashtable *ht = arg->ht;
 461         const char *ptr = obj;
 462
 463         return memcmp(ptr + ht->p.key_offset, arg->key, ht->p.key_len);
 464 }
 465
 466 /**
 467  * rhashtable_lookup_fast - search hash table, inlined version
 468  * @ht:         hash table
 469  * @key:        the pointer to the key
 470  * @params:     hash table parameters
 471  *
 472  * Computes the hash value for the key and traverses the bucket chain looking
 473  * for a entry with an identical key. The first matching entry is returned.
 474  *
 475  * Returns the first entry on which the compare function returned true.
 476  */
 477 static inline void *rhashtable_lookup_fast(
 478         struct rhashtable *ht, const void *key,
 479         const struct rhashtable_params params)
 480 {
 481         struct rhashtable_compare_arg arg = {
 482                 .ht = ht,
 483                 .key = key,
 484         };
 485         const struct bucket_table *tbl;
 486         struct rhash_head *he;
 487         unsigned hash;
 488
 489         rcu_read_lock();
 490
 491         tbl = rht_dereference_rcu(ht->tbl, ht);
 492 restart:
 493         hash = rht_key_hashfn(ht, tbl, key, params);
 494         rht_for_each_rcu(he, tbl, hash) {
 495                 if (params.obj_cmpfn ?
 496                     params.obj_cmpfn(&arg, rht_obj(ht, he)) :
 497                     rhashtable_compare(&arg, rht_obj(ht, he)))
 498                         continue;
 499                 rcu_read_unlock();
 500                 return rht_obj(ht, he);
 501         }
 502
 503         /* Ensure we see any new tables. */
 504         smp_rmb();
 505
 506         tbl = rht_dereference_rcu(tbl->future_tbl, ht);
 507         if (unlikely(tbl))
 508                 goto restart;
 509         rcu_read_unlock();
 510
 511         return NULL;
 512 }
 513
 514 static inline int __rhashtable_insert_fast(
 515         struct rhashtable *ht, const void *key, struct rhash_head *obj,
 516         const struct rhashtable_params params)
 517 {
 518         struct rhashtable_compare_arg arg = {
 519                 .ht = ht,
 520                 .key = key,
 521         };
 522         int err = -EEXIST;
 523         struct bucket_table *tbl, *new_tbl;
 524         struct rhash_head *head;
 525         spinlock_t *lock;
 526         unsigned hash;
 527
 528         rcu_read_lock();
 529
 530         tbl = rht_dereference_rcu(ht->tbl, ht);
 531         hash = rht_head_hashfn(ht, tbl, obj, params);
 532         lock = rht_bucket_lock(tbl, hash);
 533
 534         spin_lock_bh(lock);
 535
 536         /* Because we have already taken the bucket lock in tbl,
 537          * if we find that future_tbl is not yet visible then
 538          * that guarantees all other insertions of the same entry
 539          * will also grab the bucket lock in tbl because until
 540          * the rehash completes ht->tbl won't be changed.
 541          */
 542         new_tbl = rht_dereference_rcu(tbl->future_tbl, ht);
 543         if (unlikely(new_tbl)) {
 544                 err = rhashtable_insert_slow(ht, key, obj, new_tbl);
 545                 goto out;
 546         }
 547
 548         if (!key)
 549                 goto skip_lookup;
 550
 551         rht_for_each(head, tbl, hash) {
 552                 if (unlikely(!(params.obj_cmpfn ?
 553                                params.obj_cmpfn(&arg, rht_obj(ht, head)) :
 554                                rhashtable_compare(&arg, rht_obj(ht, head)))))
 555                         goto out;
 556         }
 557
 558 skip_lookup:
 559         err = 0;
 560
 561         head = rht_dereference_bucket(tbl->buckets[hash], tbl, hash);
 562
 563         RCU_INIT_POINTER(obj->next, head);
 564
 565         rcu_assign_pointer(tbl->buckets[hash], obj);
 566
 567         atomic_inc(&ht->nelems);
 568         if (rht_grow_above_75(ht, tbl))
 569                 schedule_work(&ht->run_work);
 570
 571 out:
 572         spin_unlock_bh(lock);
 573         rcu_read_unlock();
 574
 575         return err;
 576 }
 577
 578 /**
 579  * rhashtable_insert_fast - insert object into hash table
 580  * @ht:         hash table
 581  * @obj:        pointer to hash head inside object
 582  * @params:     hash table parameters
 583  *
 584  * Will take a per bucket spinlock to protect against mutual mutations
 585  * on the same bucket. Multiple insertions may occur in parallel unless
 586  * they map to the same bucket lock.
 587  *
 588  * It is safe to call this function from atomic context.
 589  *
 590  * Will trigger an automatic deferred table resizing if the size grows
 591  * beyond the watermark indicated by grow_decision() which can be passed
 592  * to rhashtable_init().
 593  */
 594 static inline int rhashtable_insert_fast(
 595         struct rhashtable *ht, struct rhash_head *obj,
 596         const struct rhashtable_params params)
 597 {
 598         return __rhashtable_insert_fast(ht, NULL, obj, params);
 599 }
 600
 601 /**
 602  * rhashtable_lookup_insert_fast - lookup and insert object into hash table
 603  * @ht:         hash table
 604  * @obj:        pointer to hash head inside object
 605  * @params:     hash table parameters
 606  *
 607  * Locks down the bucket chain in both the old and new table if a resize
 608  * is in progress to ensure that writers can't remove from the old table
 609  * and can't insert to the new table during the atomic operation of search
 610  * and insertion. Searches for duplicates in both the old and new table if
 611  * a resize is in progress.
 612  *
 613  * This lookup function may only be used for fixed key hash table (key_len
 614  * parameter set). It will BUG() if used inappropriately.
 615  *
 616  * It is safe to call this function from atomic context.
 617  *
 618  * Will trigger an automatic deferred table resizing if the size grows
 619  * beyond the watermark indicated by grow_decision() which can be passed
 620  * to rhashtable_init().
 621  */
 622 static inline int rhashtable_lookup_insert_fast(
 623         struct rhashtable *ht, struct rhash_head *obj,
 624         const struct rhashtable_params params)
 625 {
 626         const char *key = rht_obj(ht, obj);
 627
 628         BUG_ON(ht->p.obj_hashfn);
 629
 630         return __rhashtable_insert_fast(ht, key + ht->p.key_offset, obj,
 631                                         params);
 632 }
 633
 634 /**
 635  * rhashtable_lookup_insert_key - search and insert object to hash table
 636  *                                with explicit key
 637  * @ht:         hash table
 638  * @key:        key
 639  * @obj:        pointer to hash head inside object
 640  * @params:     hash table parameters
 641  *
 642  * Locks down the bucket chain in both the old and new table if a resize
 643  * is in progress to ensure that writers can't remove from the old table
 644  * and can't insert to the new table during the atomic operation of search
 645  * and insertion. Searches for duplicates in both the old and new table if
 646  * a resize is in progress.
 647  *
 648  * Lookups may occur in parallel with hashtable mutations and resizing.
 649  *
 650  * Will trigger an automatic deferred table resizing if the size grows
 651  * beyond the watermark indicated by grow_decision() which can be passed
 652  * to rhashtable_init().
 653  *
 654  * Returns zero on success.
 655  */
 656 static inline int rhashtable_lookup_insert_key(
 657         struct rhashtable *ht, const void *key, struct rhash_head *obj,
 658         const struct rhashtable_params params)
 659 {
 660         BUG_ON(!ht->p.obj_hashfn || !key);
 661
 662         return __rhashtable_insert_fast(ht, key, obj, params);
 663 }
 664
 665 static inline int __rhashtable_remove_fast(
 666         struct rhashtable *ht, struct bucket_table *tbl,
 667         struct rhash_head *obj, const struct rhashtable_params params)
 668 {
 669         struct rhash_head __rcu **pprev;
 670         struct rhash_head *he;
 671         spinlock_t * lock;
 672         unsigned hash;
 673         int err = -ENOENT;
 674
 675         hash = rht_head_hashfn(ht, tbl, obj, params);
 676         lock = rht_bucket_lock(tbl, hash);
 677
 678         spin_lock_bh(lock);
 679
 680         pprev = &tbl->buckets[hash];
 681         rht_for_each(he, tbl, hash) {
 682                 if (he != obj) {
 683                         pprev = &he->next;
 684                         continue;
 685                 }
 686
 687                 rcu_assign_pointer(*pprev, obj->next);
 688                 err = 0;
 689                 break;
 690         }
 691
 692         spin_unlock_bh(lock);
 693
 694         return err;
 695 }
 696
 697 /**
 698  * rhashtable_remove_fast - remove object from hash table
 699  * @ht:         hash table
 700  * @obj:        pointer to hash head inside object
 701  * @params:     hash table parameters
 702  *
 703  * Since the hash chain is single linked, the removal operation needs to
 704  * walk the bucket chain upon removal. The removal operation is thus
 705  * considerable slow if the hash table is not correctly sized.
 706  *
 707  * Will automatically shrink the table via rhashtable_expand() if the
 708  * shrink_decision function specified at rhashtable_init() returns true.
 709  *
 710  * Returns zero on success, -ENOENT if the entry could not be found.
 711  */
 712 static inline int rhashtable_remove_fast(
 713         struct rhashtable *ht, struct rhash_head *obj,
 714         const struct rhashtable_params params)
 715 {
 716         struct bucket_table *tbl;
 717         int err;
 718
 719         rcu_read_lock();
 720
 721         tbl = rht_dereference_rcu(ht->tbl, ht);
 722
 723         /* Because we have already taken (and released) the bucket
 724          * lock in old_tbl, if we find that future_tbl is not yet
 725          * visible then that guarantees the entry to still be in
 726          * the old tbl if it exists.
 727          */
 728         while ((err = __rhashtable_remove_fast(ht, tbl, obj, params)) &&
 729                (tbl = rht_dereference_rcu(tbl->future_tbl, ht)))
 730                 ;
 731
 732         if (err)
 733                 goto out;
 734
 735         atomic_dec(&ht->nelems);
 736         if (rht_shrink_below_30(ht, tbl))
 737                 schedule_work(&ht->run_work);
 738
 739 out:
 740         rcu_read_unlock();
 741
 742         return err;
 743 }
 744
 745 #endif /* _LINUX_RHASHTABLE_H */