include/linux/rhashtable.h

   1 /* SPDX-License-Identifier: GPL-2.0 */
   2 /*
   3  * Resizable, Scalable, Concurrent Hash Table
   4  *
   5  * Copyright (c) 2015-2016 Herbert Xu <herbert@gondor.apana.org.au>
   6  * Copyright (c) 2014-2015 Thomas Graf <tgraf@suug.ch>
   7  * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
   8  *
   9  * Code partially derived from nft_hash
  10  * Rewritten with rehash code from br_multicast plus single list
  11  * pointer as suggested by Josh Triplett
  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/err.h>
  22 #include <linux/errno.h>
  23 #include <linux/jhash.h>
  24 #include <linux/list_nulls.h>
  25 #include <linux/workqueue.h>
  26 #include <linux/rculist.h>
  27
  28 #include <linux/rhashtable-types.h>
  29 /*
  30  * The end of the chain is marked with a special nulls marks which has
  31  * the least significant bit set.
  32  */
  33
  34 /* Maximum chain length before rehash
  35  *
  36  * The maximum (not average) chain length grows with the size of the hash
  37  * table, at a rate of (log N)/(log log N).
  38  *
  39  * The value of 16 is selected so that even if the hash table grew to
  40  * 2^32 you would not expect the maximum chain length to exceed it
  41  * unless we are under attack (or extremely unlucky).
  42  *
  43  * As this limit is only to detect attacks, we don't need to set it to a
  44  * lower value as you'd need the chain length to vastly exceed 16 to have
  45  * any real effect on the system.
  46  */
  47 #define RHT_ELASTICITY  16u
  48
  49 /**
  50  * struct bucket_table - Table of hash buckets
  51  * @size: Number of hash buckets
  52  * @nest: Number of bits of first-level nested table.
  53  * @rehash: Current bucket being rehashed
  54  * @hash_rnd: Random seed to fold into hash
  55  * @locks_mask: Mask to apply before accessing locks[]
  56  * @locks: Array of spinlocks protecting individual buckets
  57  * @walkers: List of active walkers
  58  * @rcu: RCU structure for freeing the table
  59  * @future_tbl: Table under construction during rehashing
  60  * @ntbl: Nested table used when out of memory.
  61  * @buckets: size * hash buckets
  62  */
  63 struct bucket_table {
  64         unsigned int            size;
  65         unsigned int            nest;
  66         unsigned int            rehash;
  67         u32                     hash_rnd;
  68         unsigned int            locks_mask;
  69         spinlock_t              *locks;
  70         struct list_head        walkers;
  71         struct rcu_head         rcu;
  72
  73         struct bucket_table __rcu *future_tbl;
  74
  75         struct rhash_head __rcu *buckets[] ____cacheline_aligned_in_smp;
  76 };
  77
  78 /*
  79  * NULLS_MARKER() expects a hash value with the low
  80  * bits mostly likely to be significant, and it discards
  81  * the msb.
  82  * We git it an address, in which the bottom 2 bits are
  83  * always 0, and the msb might be significant.
  84  * So we shift the address down one bit to align with
  85  * expectations and avoid losing a significant bit.
  86  */
  87 #define RHT_NULLS_MARKER(ptr)   \
  88         ((void *)NULLS_MARKER(((unsigned long) (ptr)) >> 1))
  89 #define INIT_RHT_NULLS_HEAD(ptr)        \
  90         ((ptr) = RHT_NULLS_MARKER(&(ptr)))
  91
  92 static inline bool rht_is_a_nulls(const struct rhash_head *ptr)
  93 {
  94         return ((unsigned long) ptr & 1);
  95 }
  96
  97 static inline void *rht_obj(const struct rhashtable *ht,
  98                             const struct rhash_head *he)
  99 {
 100         return (char *)he - ht->p.head_offset;
 101 }
 102
 103 static inline unsigned int rht_bucket_index(const struct bucket_table *tbl,
 104                                             unsigned int hash)
 105 {
 106         return hash & (tbl->size - 1);
 107 }
 108
 109 static inline unsigned int rht_key_get_hash(struct rhashtable *ht,
 110         const void *key, const struct rhashtable_params params,
 111         unsigned int hash_rnd)
 112 {
 113         unsigned int hash;
 114
 115         /* params must be equal to ht->p if it isn't constant. */
 116         if (!__builtin_constant_p(params.key_len))
 117                 hash = ht->p.hashfn(key, ht->key_len, hash_rnd);
 118         else if (params.key_len) {
 119                 unsigned int key_len = params.key_len;
 120
 121                 if (params.hashfn)
 122                         hash = params.hashfn(key, key_len, hash_rnd);
 123                 else if (key_len & (sizeof(u32) - 1))
 124                         hash = jhash(key, key_len, hash_rnd);
 125                 else
 126                         hash = jhash2(key, key_len / sizeof(u32), hash_rnd);
 127         } else {
 128                 unsigned int key_len = ht->p.key_len;
 129
 130                 if (params.hashfn)
 131                         hash = params.hashfn(key, key_len, hash_rnd);
 132                 else
 133                         hash = jhash(key, key_len, hash_rnd);
 134         }
 135
 136         return hash;
 137 }
 138
 139 static inline unsigned int rht_key_hashfn(
 140         struct rhashtable *ht, const struct bucket_table *tbl,
 141         const void *key, const struct rhashtable_params params)
 142 {
 143         unsigned int hash = rht_key_get_hash(ht, key, params, tbl->hash_rnd);
 144
 145         return rht_bucket_index(tbl, hash);
 146 }
 147
 148 static inline unsigned int rht_head_hashfn(
 149         struct rhashtable *ht, const struct bucket_table *tbl,
 150         const struct rhash_head *he, const struct rhashtable_params params)
 151 {
 152         const char *ptr = rht_obj(ht, he);
 153
 154         return likely(params.obj_hashfn) ?
 155                rht_bucket_index(tbl, params.obj_hashfn(ptr, params.key_len ?:
 156                                                             ht->p.key_len,
 157                                                        tbl->hash_rnd)) :
 158                rht_key_hashfn(ht, tbl, ptr + params.key_offset, params);
 159 }
 160
 161 /**
 162  * rht_grow_above_75 - returns true if nelems > 0.75 * table-size
 163  * @ht:         hash table
 164  * @tbl:        current table
 165  */
 166 static inline bool rht_grow_above_75(const struct rhashtable *ht,
 167                                      const struct bucket_table *tbl)
 168 {
 169         /* Expand table when exceeding 75% load */
 170         return atomic_read(&ht->nelems) > (tbl->size / 4 * 3) &&
 171                (!ht->p.max_size || tbl->size < ht->p.max_size);
 172 }
 173
 174 /**
 175  * rht_shrink_below_30 - returns true if nelems < 0.3 * table-size
 176  * @ht:         hash table
 177  * @tbl:        current table
 178  */
 179 static inline bool rht_shrink_below_30(const struct rhashtable *ht,
 180                                        const struct bucket_table *tbl)
 181 {
 182         /* Shrink table beneath 30% load */
 183         return atomic_read(&ht->nelems) < (tbl->size * 3 / 10) &&
 184                tbl->size > ht->p.min_size;
 185 }
 186
 187 /**
 188  * rht_grow_above_100 - returns true if nelems > table-size
 189  * @ht:         hash table
 190  * @tbl:        current table
 191  */
 192 static inline bool rht_grow_above_100(const struct rhashtable *ht,
 193                                       const struct bucket_table *tbl)
 194 {
 195         return atomic_read(&ht->nelems) > tbl->size &&
 196                 (!ht->p.max_size || tbl->size < ht->p.max_size);
 197 }
 198
 199 /**
 200  * rht_grow_above_max - returns true if table is above maximum
 201  * @ht:         hash table
 202  * @tbl:        current table
 203  */
 204 static inline bool rht_grow_above_max(const struct rhashtable *ht,
 205                                       const struct bucket_table *tbl)
 206 {
 207         return atomic_read(&ht->nelems) >= ht->max_elems;
 208 }
 209
 210 /* The bucket lock is selected based on the hash and protects mutations
 211  * on a group of hash buckets.
 212  *
 213  * A maximum of tbl->size/2 bucket locks is allocated. This ensures that
 214  * a single lock always covers both buckets which may both contains
 215  * entries which link to the same bucket of the old table during resizing.
 216  * This allows to simplify the locking as locking the bucket in both
 217  * tables during resize always guarantee protection.
 218  *
 219  * IMPORTANT: When holding the bucket lock of both the old and new table
 220  * during expansions and shrinking, the old bucket lock must always be
 221  * acquired first.
 222  */
 223 static inline spinlock_t *rht_bucket_lock(const struct bucket_table *tbl,
 224                                           unsigned int hash)
 225 {
 226         return &tbl->locks[hash & tbl->locks_mask];
 227 }
 228
 229 #ifdef CONFIG_PROVE_LOCKING
 230 int lockdep_rht_mutex_is_held(struct rhashtable *ht);
 231 int lockdep_rht_bucket_is_held(const struct bucket_table *tbl, u32 hash);
 232 #else
 233 static inline int lockdep_rht_mutex_is_held(struct rhashtable *ht)
 234 {
 235         return 1;
 236 }
 237
 238 static inline int lockdep_rht_bucket_is_held(const struct bucket_table *tbl,
 239                                              u32 hash)
 240 {
 241         return 1;
 242 }
 243 #endif /* CONFIG_PROVE_LOCKING */
 244
 245 void *rhashtable_insert_slow(struct rhashtable *ht, const void *key,
 246                              struct rhash_head *obj);
 247
 248 void rhashtable_walk_enter(struct rhashtable *ht,
 249                            struct rhashtable_iter *iter);
 250 void rhashtable_walk_exit(struct rhashtable_iter *iter);
 251 int rhashtable_walk_start_check(struct rhashtable_iter *iter) __acquires(RCU);
 252
 253 static inline void rhashtable_walk_start(struct rhashtable_iter *iter)
 254 {
 255         (void)rhashtable_walk_start_check(iter);
 256 }
 257
 258 void *rhashtable_walk_next(struct rhashtable_iter *iter);
 259 void *rhashtable_walk_peek(struct rhashtable_iter *iter);
 260 void rhashtable_walk_stop(struct rhashtable_iter *iter) __releases(RCU);
 261
 262 void rhashtable_free_and_destroy(struct rhashtable *ht,
 263                                  void (*free_fn)(void *ptr, void *arg),
 264                                  void *arg);
 265 void rhashtable_destroy(struct rhashtable *ht);
 266
 267 struct rhash_head __rcu **rht_bucket_nested(const struct bucket_table *tbl,
 268                                             unsigned int hash);
 269 struct rhash_head __rcu **rht_bucket_nested_insert(struct rhashtable *ht,
 270                                                    struct bucket_table *tbl,
 271                                                    unsigned int hash);
 272
 273 #define rht_dereference(p, ht) \
 274         rcu_dereference_protected(p, lockdep_rht_mutex_is_held(ht))
 275
 276 #define rht_dereference_rcu(p, ht) \
 277         rcu_dereference_check(p, lockdep_rht_mutex_is_held(ht))
 278
 279 #define rht_dereference_bucket(p, tbl, hash) \
 280         rcu_dereference_protected(p, lockdep_rht_bucket_is_held(tbl, hash))
 281
 282 #define rht_dereference_bucket_rcu(p, tbl, hash) \
 283         rcu_dereference_check(p, lockdep_rht_bucket_is_held(tbl, hash))
 284
 285 #define rht_entry(tpos, pos, member) \
 286         ({ tpos = container_of(pos, typeof(*tpos), member); 1; })
 287
 288 static inline struct rhash_head __rcu *const *rht_bucket(
 289         const struct bucket_table *tbl, unsigned int hash)
 290 {
 291         return unlikely(tbl->nest) ? rht_bucket_nested(tbl, hash) :
 292                                      &tbl->buckets[hash];
 293 }
 294
 295 static inline struct rhash_head __rcu **rht_bucket_var(
 296         struct bucket_table *tbl, unsigned int hash)
 297 {
 298         return unlikely(tbl->nest) ? rht_bucket_nested(tbl, hash) :
 299                                      &tbl->buckets[hash];
 300 }
 301
 302 static inline struct rhash_head __rcu **rht_bucket_insert(
 303         struct rhashtable *ht, struct bucket_table *tbl, unsigned int hash)
 304 {
 305         return unlikely(tbl->nest) ? rht_bucket_nested_insert(ht, tbl, hash) :
 306                                      &tbl->buckets[hash];
 307 }
 308
 309 /**
 310  * rht_for_each_continue - continue iterating over hash chain
 311  * @pos:        the &struct rhash_head to use as a loop cursor.
 312  * @head:       the previous &struct rhash_head to continue from
 313  * @tbl:        the &struct bucket_table
 314  * @hash:       the hash value / bucket index
 315  */
 316 #define rht_for_each_continue(pos, head, tbl, hash) \
 317         for (pos = rht_dereference_bucket(head, tbl, hash); \
 318              !rht_is_a_nulls(pos); \
 319              pos = rht_dereference_bucket((pos)->next, tbl, hash))
 320
 321 /**
 322  * rht_for_each - iterate over hash chain
 323  * @pos:        the &struct rhash_head to use as a loop cursor.
 324  * @tbl:        the &struct bucket_table
 325  * @hash:       the hash value / bucket index
 326  */
 327 #define rht_for_each(pos, tbl, hash) \
 328         rht_for_each_continue(pos, *rht_bucket(tbl, hash), tbl, hash)
 329
 330 /**
 331  * rht_for_each_entry_continue - continue iterating over hash chain
 332  * @tpos:       the type * to use as a loop cursor.
 333  * @pos:        the &struct rhash_head to use as a loop cursor.
 334  * @head:       the previous &struct rhash_head to continue from
 335  * @tbl:        the &struct bucket_table
 336  * @hash:       the hash value / bucket index
 337  * @member:     name of the &struct rhash_head within the hashable struct.
 338  */
 339 #define rht_for_each_entry_continue(tpos, pos, head, tbl, hash, member) \
 340         for (pos = rht_dereference_bucket(head, tbl, hash);             \
 341              (!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member);    \
 342              pos = rht_dereference_bucket((pos)->next, tbl, hash))
 343
 344 /**
 345  * rht_for_each_entry - iterate over hash chain of given type
 346  * @tpos:       the type * to use as a loop cursor.
 347  * @pos:        the &struct rhash_head to use as a loop cursor.
 348  * @tbl:        the &struct bucket_table
 349  * @hash:       the hash value / bucket index
 350  * @member:     name of the &struct rhash_head within the hashable struct.
 351  */
 352 #define rht_for_each_entry(tpos, pos, tbl, hash, member)                \
 353         rht_for_each_entry_continue(tpos, pos, *rht_bucket(tbl, hash),  \
 354                                     tbl, hash, member)
 355
 356 /**
 357  * rht_for_each_entry_safe - safely iterate over hash chain of given type
 358  * @tpos:       the type * to use as a loop cursor.
 359  * @pos:        the &struct rhash_head to use as a loop cursor.
 360  * @next:       the &struct rhash_head to use as next in loop cursor.
 361  * @tbl:        the &struct bucket_table
 362  * @hash:       the hash value / bucket index
 363  * @member:     name of the &struct rhash_head within the hashable struct.
 364  *
 365  * This hash chain list-traversal primitive allows for the looped code to
 366  * remove the loop cursor from the list.
 367  */
 368 #define rht_for_each_entry_safe(tpos, pos, next, tbl, hash, member)           \
 369         for (pos = rht_dereference_bucket(*rht_bucket(tbl, hash), tbl, hash), \
 370              next = !rht_is_a_nulls(pos) ?                                    \
 371                        rht_dereference_bucket(pos->next, tbl, hash) : NULL;   \
 372              (!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member);          \
 373              pos = next,                                                      \
 374              next = !rht_is_a_nulls(pos) ?                                    \
 375                        rht_dereference_bucket(pos->next, tbl, hash) : NULL)
 376
 377 /**
 378  * rht_for_each_rcu_continue - continue iterating over rcu hash chain
 379  * @pos:        the &struct rhash_head to use as a loop cursor.
 380  * @head:       the previous &struct rhash_head to continue from
 381  * @tbl:        the &struct bucket_table
 382  * @hash:       the hash value / bucket index
 383  *
 384  * This hash chain list-traversal primitive may safely run concurrently with
 385  * the _rcu mutation primitives such as rhashtable_insert() as long as the
 386  * traversal is guarded by rcu_read_lock().
 387  */
 388 #define rht_for_each_rcu_continue(pos, head, tbl, hash)                 \
 389         for (({barrier(); }),                                           \
 390              pos = rht_dereference_bucket_rcu(head, tbl, hash);         \
 391              !rht_is_a_nulls(pos);                                      \
 392              pos = rcu_dereference_raw(pos->next))
 393
 394 /**
 395  * rht_for_each_rcu - iterate over rcu hash chain
 396  * @pos:        the &struct rhash_head to use as a loop cursor.
 397  * @tbl:        the &struct bucket_table
 398  * @hash:       the hash value / bucket index
 399  *
 400  * This hash chain list-traversal primitive may safely run concurrently with
 401  * the _rcu mutation primitives such as rhashtable_insert() as long as the
 402  * traversal is guarded by rcu_read_lock().
 403  */
 404 #define rht_for_each_rcu(pos, tbl, hash)                                \
 405         rht_for_each_rcu_continue(pos, *rht_bucket(tbl, hash), tbl, hash)
 406
 407 /**
 408  * rht_for_each_entry_rcu_continue - continue iterating over rcu hash chain
 409  * @tpos:       the type * to use as a loop cursor.
 410  * @pos:        the &struct rhash_head to use as a loop cursor.
 411  * @head:       the previous &struct rhash_head to continue from
 412  * @tbl:        the &struct bucket_table
 413  * @hash:       the hash value / bucket index
 414  * @member:     name of the &struct rhash_head within the hashable struct.
 415  *
 416  * This hash chain list-traversal primitive may safely run concurrently with
 417  * the _rcu mutation primitives such as rhashtable_insert() as long as the
 418  * traversal is guarded by rcu_read_lock().
 419  */
 420 #define rht_for_each_entry_rcu_continue(tpos, pos, head, tbl, hash, member) \
 421         for (({barrier(); }),                                               \
 422              pos = rht_dereference_bucket_rcu(head, tbl, hash);             \
 423              (!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member);        \
 424              pos = rht_dereference_bucket_rcu(pos->next, tbl, hash))
 425
 426 /**
 427  * rht_for_each_entry_rcu - iterate over rcu hash chain of given type
 428  * @tpos:       the type * to use as a loop cursor.
 429  * @pos:        the &struct rhash_head to use as a loop cursor.
 430  * @tbl:        the &struct bucket_table
 431  * @hash:       the hash value / bucket index
 432  * @member:     name of the &struct rhash_head within the hashable struct.
 433  *
 434  * This hash chain list-traversal primitive may safely run concurrently with
 435  * the _rcu mutation primitives such as rhashtable_insert() as long as the
 436  * traversal is guarded by rcu_read_lock().
 437  */
 438 #define rht_for_each_entry_rcu(tpos, pos, tbl, hash, member)               \
 439         rht_for_each_entry_rcu_continue(tpos, pos, *rht_bucket(tbl, hash), \
 440                                         tbl, hash, member)
 441
 442 /**
 443  * rhl_for_each_rcu - iterate over rcu hash table list
 444  * @pos:        the &struct rlist_head to use as a loop cursor.
 445  * @list:       the head of the list
 446  *
 447  * This hash chain list-traversal primitive should be used on the
 448  * list returned by rhltable_lookup.
 449  */
 450 #define rhl_for_each_rcu(pos, list)                                     \
 451         for (pos = list; pos; pos = rcu_dereference_raw(pos->next))
 452
 453 /**
 454  * rhl_for_each_entry_rcu - iterate over rcu hash table list of given type
 455  * @tpos:       the type * to use as a loop cursor.
 456  * @pos:        the &struct rlist_head to use as a loop cursor.
 457  * @list:       the head of the list
 458  * @member:     name of the &struct rlist_head within the hashable struct.
 459  *
 460  * This hash chain list-traversal primitive should be used on the
 461  * list returned by rhltable_lookup.
 462  */
 463 #define rhl_for_each_entry_rcu(tpos, pos, list, member)                 \
 464         for (pos = list; pos && rht_entry(tpos, pos, member);           \
 465              pos = rcu_dereference_raw(pos->next))
 466
 467 static inline int rhashtable_compare(struct rhashtable_compare_arg *arg,
 468                                      const void *obj)
 469 {
 470         struct rhashtable *ht = arg->ht;
 471         const char *ptr = obj;
 472
 473         return memcmp(ptr + ht->p.key_offset, arg->key, ht->p.key_len);
 474 }
 475
 476 /* Internal function, do not use. */
 477 static inline struct rhash_head *__rhashtable_lookup(
 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         struct rhash_head __rcu * const *head;
 486         struct bucket_table *tbl;
 487         struct rhash_head *he;
 488         unsigned int hash;
 489
 490         tbl = rht_dereference_rcu(ht->tbl, ht);
 491 restart:
 492         hash = rht_key_hashfn(ht, tbl, key, params);
 493         head = rht_bucket(tbl, hash);
 494         do {
 495                 rht_for_each_rcu_continue(he, *head, tbl, hash) {
 496                         if (params.obj_cmpfn ?
 497                             params.obj_cmpfn(&arg, rht_obj(ht, he)) :
 498                             rhashtable_compare(&arg, rht_obj(ht, he)))
 499                                 continue;
 500                         return he;
 501                 }
 502                 /* An object might have been moved to a different hash chain,
 503                  * while we walk along it - better check and retry.
 504                  */
 505         } while (he != RHT_NULLS_MARKER(head));
 506
 507         /* Ensure we see any new tables. */
 508         smp_rmb();
 509
 510         tbl = rht_dereference_rcu(tbl->future_tbl, ht);
 511         if (unlikely(tbl))
 512                 goto restart;
 513
 514         return NULL;
 515 }
 516
 517 /**
 518  * rhashtable_lookup - search hash table
 519  * @ht:         hash table
 520  * @key:        the pointer to the key
 521  * @params:     hash table parameters
 522  *
 523  * Computes the hash value for the key and traverses the bucket chain looking
 524  * for a entry with an identical key. The first matching entry is returned.
 525  *
 526  * This must only be called under the RCU read lock.
 527  *
 528  * Returns the first entry on which the compare function returned true.
 529  */
 530 static inline void *rhashtable_lookup(
 531         struct rhashtable *ht, const void *key,
 532         const struct rhashtable_params params)
 533 {
 534         struct rhash_head *he = __rhashtable_lookup(ht, key, params);
 535
 536         return he ? rht_obj(ht, he) : NULL;
 537 }
 538
 539 /**
 540  * rhashtable_lookup_fast - search hash table, without RCU read lock
 541  * @ht:         hash table
 542  * @key:        the pointer to the key
 543  * @params:     hash table parameters
 544  *
 545  * Computes the hash value for the key and traverses the bucket chain looking
 546  * for a entry with an identical key. The first matching entry is returned.
 547  *
 548  * Only use this function when you have other mechanisms guaranteeing
 549  * that the object won't go away after the RCU read lock is released.
 550  *
 551  * Returns the first entry on which the compare function returned true.
 552  */
 553 static inline void *rhashtable_lookup_fast(
 554         struct rhashtable *ht, const void *key,
 555         const struct rhashtable_params params)
 556 {
 557         void *obj;
 558
 559         rcu_read_lock();
 560         obj = rhashtable_lookup(ht, key, params);
 561         rcu_read_unlock();
 562
 563         return obj;
 564 }
 565
 566 /**
 567  * rhltable_lookup - search hash list table
 568  * @hlt:        hash table
 569  * @key:        the pointer to the key
 570  * @params:     hash table parameters
 571  *
 572  * Computes the hash value for the key and traverses the bucket chain looking
 573  * for a entry with an identical key.  All matching entries are returned
 574  * in a list.
 575  *
 576  * This must only be called under the RCU read lock.
 577  *
 578  * Returns the list of entries that match the given key.
 579  */
 580 static inline struct rhlist_head *rhltable_lookup(
 581         struct rhltable *hlt, const void *key,
 582         const struct rhashtable_params params)
 583 {
 584         struct rhash_head *he = __rhashtable_lookup(&hlt->ht, key, params);
 585
 586         return he ? container_of(he, struct rhlist_head, rhead) : NULL;
 587 }
 588
 589 /* Internal function, please use rhashtable_insert_fast() instead. This
 590  * function returns the existing element already in hashes in there is a clash,
 591  * otherwise it returns an error via ERR_PTR().
 592  */
 593 static inline void *__rhashtable_insert_fast(
 594         struct rhashtable *ht, const void *key, struct rhash_head *obj,
 595         const struct rhashtable_params params, bool rhlist)
 596 {
 597         struct rhashtable_compare_arg arg = {
 598                 .ht = ht,
 599                 .key = key,
 600         };
 601         struct rhash_head __rcu **pprev;
 602         struct bucket_table *tbl;
 603         struct rhash_head *head;
 604         spinlock_t *lock;
 605         unsigned int hash;
 606         int elasticity;
 607         void *data;
 608
 609         rcu_read_lock();
 610
 611         tbl = rht_dereference_rcu(ht->tbl, ht);
 612         hash = rht_head_hashfn(ht, tbl, obj, params);
 613         lock = rht_bucket_lock(tbl, hash);
 614         spin_lock_bh(lock);
 615
 616         if (unlikely(rcu_access_pointer(tbl->future_tbl))) {
 617 slow_path:
 618                 spin_unlock_bh(lock);
 619                 rcu_read_unlock();
 620                 return rhashtable_insert_slow(ht, key, obj);
 621         }
 622
 623         elasticity = RHT_ELASTICITY;
 624         pprev = rht_bucket_insert(ht, tbl, hash);
 625         data = ERR_PTR(-ENOMEM);
 626         if (!pprev)
 627                 goto out;
 628
 629         rht_for_each_continue(head, *pprev, tbl, hash) {
 630                 struct rhlist_head *plist;
 631                 struct rhlist_head *list;
 632
 633                 elasticity--;
 634                 if (!key ||
 635                     (params.obj_cmpfn ?
 636                      params.obj_cmpfn(&arg, rht_obj(ht, head)) :
 637                      rhashtable_compare(&arg, rht_obj(ht, head)))) {
 638                         pprev = &head->next;
 639                         continue;
 640                 }
 641
 642                 data = rht_obj(ht, head);
 643
 644                 if (!rhlist)
 645                         goto out;
 646
 647
 648                 list = container_of(obj, struct rhlist_head, rhead);
 649                 plist = container_of(head, struct rhlist_head, rhead);
 650
 651                 RCU_INIT_POINTER(list->next, plist);
 652                 head = rht_dereference_bucket(head->next, tbl, hash);
 653                 RCU_INIT_POINTER(list->rhead.next, head);
 654                 rcu_assign_pointer(*pprev, obj);
 655
 656                 goto good;
 657         }
 658
 659         if (elasticity <= 0)
 660                 goto slow_path;
 661
 662         data = ERR_PTR(-E2BIG);
 663         if (unlikely(rht_grow_above_max(ht, tbl)))
 664                 goto out;
 665
 666         if (unlikely(rht_grow_above_100(ht, tbl)))
 667                 goto slow_path;
 668
 669         head = rht_dereference_bucket(*pprev, tbl, hash);
 670
 671         RCU_INIT_POINTER(obj->next, head);
 672         if (rhlist) {
 673                 struct rhlist_head *list;
 674
 675                 list = container_of(obj, struct rhlist_head, rhead);
 676                 RCU_INIT_POINTER(list->next, NULL);
 677         }
 678
 679         rcu_assign_pointer(*pprev, obj);
 680
 681         atomic_inc(&ht->nelems);
 682         if (rht_grow_above_75(ht, tbl))
 683                 schedule_work(&ht->run_work);
 684
 685 good:
 686         data = NULL;
 687
 688 out:
 689         spin_unlock_bh(lock);
 690         rcu_read_unlock();
 691
 692         return data;
 693 }
 694
 695 /**
 696  * rhashtable_insert_fast - insert object into hash table
 697  * @ht:         hash table
 698  * @obj:        pointer to hash head inside object
 699  * @params:     hash table parameters
 700  *
 701  * Will take a per bucket spinlock to protect against mutual mutations
 702  * on the same bucket. Multiple insertions may occur in parallel unless
 703  * they map to the same bucket lock.
 704  *
 705  * It is safe to call this function from atomic context.
 706  *
 707  * Will trigger an automatic deferred table resizing if residency in the
 708  * table grows beyond 70%.
 709  */
 710 static inline int rhashtable_insert_fast(
 711         struct rhashtable *ht, struct rhash_head *obj,
 712         const struct rhashtable_params params)
 713 {
 714         void *ret;
 715
 716         ret = __rhashtable_insert_fast(ht, NULL, obj, params, false);
 717         if (IS_ERR(ret))
 718                 return PTR_ERR(ret);
 719
 720         return ret == NULL ? 0 : -EEXIST;
 721 }
 722
 723 /**
 724  * rhltable_insert_key - insert object into hash list table
 725  * @hlt:        hash list table
 726  * @key:        the pointer to the key
 727  * @list:       pointer to hash list head inside object
 728  * @params:     hash table parameters
 729  *
 730  * Will take a per bucket spinlock to protect against mutual mutations
 731  * on the same bucket. Multiple insertions may occur in parallel unless
 732  * they map to the same bucket lock.
 733  *
 734  * It is safe to call this function from atomic context.
 735  *
 736  * Will trigger an automatic deferred table resizing if residency in the
 737  * table grows beyond 70%.
 738  */
 739 static inline int rhltable_insert_key(
 740         struct rhltable *hlt, const void *key, struct rhlist_head *list,
 741         const struct rhashtable_params params)
 742 {
 743         return PTR_ERR(__rhashtable_insert_fast(&hlt->ht, key, &list->rhead,
 744                                                 params, true));
 745 }
 746
 747 /**
 748  * rhltable_insert - insert object into hash list table
 749  * @hlt:        hash list table
 750  * @list:       pointer to hash list head inside object
 751  * @params:     hash table parameters
 752  *
 753  * Will take a per bucket spinlock to protect against mutual mutations
 754  * on the same bucket. Multiple insertions may occur in parallel unless
 755  * they map to the same bucket lock.
 756  *
 757  * It is safe to call this function from atomic context.
 758  *
 759  * Will trigger an automatic deferred table resizing if residency in the
 760  * table grows beyond 70%.
 761  */
 762 static inline int rhltable_insert(
 763         struct rhltable *hlt, struct rhlist_head *list,
 764         const struct rhashtable_params params)
 765 {
 766         const char *key = rht_obj(&hlt->ht, &list->rhead);
 767
 768         key += params.key_offset;
 769
 770         return rhltable_insert_key(hlt, key, list, params);
 771 }
 772
 773 /**
 774  * rhashtable_lookup_insert_fast - lookup and insert object into hash table
 775  * @ht:         hash table
 776  * @obj:        pointer to hash head inside object
 777  * @params:     hash table parameters
 778  *
 779  * Locks down the bucket chain in both the old and new table if a resize
 780  * is in progress to ensure that writers can't remove from the old table
 781  * and can't insert to the new table during the atomic operation of search
 782  * and insertion. Searches for duplicates in both the old and new table if
 783  * a resize is in progress.
 784  *
 785  * This lookup function may only be used for fixed key hash table (key_len
 786  * parameter set). It will BUG() if used inappropriately.
 787  *
 788  * It is safe to call this function from atomic context.
 789  *
 790  * Will trigger an automatic deferred table resizing if residency in the
 791  * table grows beyond 70%.
 792  */
 793 static inline int rhashtable_lookup_insert_fast(
 794         struct rhashtable *ht, struct rhash_head *obj,
 795         const struct rhashtable_params params)
 796 {
 797         const char *key = rht_obj(ht, obj);
 798         void *ret;
 799
 800         BUG_ON(ht->p.obj_hashfn);
 801
 802         ret = __rhashtable_insert_fast(ht, key + ht->p.key_offset, obj, params,
 803                                        false);
 804         if (IS_ERR(ret))
 805                 return PTR_ERR(ret);
 806
 807         return ret == NULL ? 0 : -EEXIST;
 808 }
 809
 810 /**
 811  * rhashtable_lookup_get_insert_fast - lookup and insert object into hash table
 812  * @ht:         hash table
 813  * @obj:        pointer to hash head inside object
 814  * @params:     hash table parameters
 815  *
 816  * Just like rhashtable_lookup_insert_fast(), but this function returns the
 817  * object if it exists, NULL if it did not and the insertion was successful,
 818  * and an ERR_PTR otherwise.
 819  */
 820 static inline void *rhashtable_lookup_get_insert_fast(
 821         struct rhashtable *ht, struct rhash_head *obj,
 822         const struct rhashtable_params params)
 823 {
 824         const char *key = rht_obj(ht, obj);
 825
 826         BUG_ON(ht->p.obj_hashfn);
 827
 828         return __rhashtable_insert_fast(ht, key + ht->p.key_offset, obj, params,
 829                                         false);
 830 }
 831
 832 /**
 833  * rhashtable_lookup_insert_key - search and insert object to hash table
 834  *                                with explicit key
 835  * @ht:         hash table
 836  * @key:        key
 837  * @obj:        pointer to hash head inside object
 838  * @params:     hash table parameters
 839  *
 840  * Locks down the bucket chain in both the old and new table if a resize
 841  * is in progress to ensure that writers can't remove from the old table
 842  * and can't insert to the new table during the atomic operation of search
 843  * and insertion. Searches for duplicates in both the old and new table if
 844  * a resize is in progress.
 845  *
 846  * Lookups may occur in parallel with hashtable mutations and resizing.
 847  *
 848  * Will trigger an automatic deferred table resizing if residency in the
 849  * table grows beyond 70%.
 850  *
 851  * Returns zero on success.
 852  */
 853 static inline int rhashtable_lookup_insert_key(
 854         struct rhashtable *ht, const void *key, struct rhash_head *obj,
 855         const struct rhashtable_params params)
 856 {
 857         void *ret;
 858
 859         BUG_ON(!ht->p.obj_hashfn || !key);
 860
 861         ret = __rhashtable_insert_fast(ht, key, obj, params, false);
 862         if (IS_ERR(ret))
 863                 return PTR_ERR(ret);
 864
 865         return ret == NULL ? 0 : -EEXIST;
 866 }
 867
 868 /**
 869  * rhashtable_lookup_get_insert_key - lookup and insert object into hash table
 870  * @ht:         hash table
 871  * @obj:        pointer to hash head inside object
 872  * @params:     hash table parameters
 873  * @data:       pointer to element data already in hashes
 874  *
 875  * Just like rhashtable_lookup_insert_key(), but this function returns the
 876  * object if it exists, NULL if it does not and the insertion was successful,
 877  * and an ERR_PTR otherwise.
 878  */
 879 static inline void *rhashtable_lookup_get_insert_key(
 880         struct rhashtable *ht, const void *key, struct rhash_head *obj,
 881         const struct rhashtable_params params)
 882 {
 883         BUG_ON(!ht->p.obj_hashfn || !key);
 884
 885         return __rhashtable_insert_fast(ht, key, obj, params, false);
 886 }
 887
 888 /* Internal function, please use rhashtable_remove_fast() instead */
 889 static inline int __rhashtable_remove_fast_one(
 890         struct rhashtable *ht, struct bucket_table *tbl,
 891         struct rhash_head *obj, const struct rhashtable_params params,
 892         bool rhlist)
 893 {
 894         struct rhash_head __rcu **pprev;
 895         struct rhash_head *he;
 896         spinlock_t * lock;
 897         unsigned int hash;
 898         int err = -ENOENT;
 899
 900         hash = rht_head_hashfn(ht, tbl, obj, params);
 901         lock = rht_bucket_lock(tbl, hash);
 902
 903         spin_lock_bh(lock);
 904
 905         pprev = rht_bucket_var(tbl, hash);
 906         rht_for_each_continue(he, *pprev, tbl, hash) {
 907                 struct rhlist_head *list;
 908
 909                 list = container_of(he, struct rhlist_head, rhead);
 910
 911                 if (he != obj) {
 912                         struct rhlist_head __rcu **lpprev;
 913
 914                         pprev = &he->next;
 915
 916                         if (!rhlist)
 917                                 continue;
 918
 919                         do {
 920                                 lpprev = &list->next;
 921                                 list = rht_dereference_bucket(list->next,
 922                                                               tbl, hash);
 923                         } while (list && obj != &list->rhead);
 924
 925                         if (!list)
 926                                 continue;
 927
 928                         list = rht_dereference_bucket(list->next, tbl, hash);
 929                         RCU_INIT_POINTER(*lpprev, list);
 930                         err = 0;
 931                         break;
 932                 }
 933
 934                 obj = rht_dereference_bucket(obj->next, tbl, hash);
 935                 err = 1;
 936
 937                 if (rhlist) {
 938                         list = rht_dereference_bucket(list->next, tbl, hash);
 939                         if (list) {
 940                                 RCU_INIT_POINTER(list->rhead.next, obj);
 941                                 obj = &list->rhead;
 942                                 err = 0;
 943                         }
 944                 }
 945
 946                 rcu_assign_pointer(*pprev, obj);
 947                 break;
 948         }
 949
 950         spin_unlock_bh(lock);
 951
 952         if (err > 0) {
 953                 atomic_dec(&ht->nelems);
 954                 if (unlikely(ht->p.automatic_shrinking &&
 955                              rht_shrink_below_30(ht, tbl)))
 956                         schedule_work(&ht->run_work);
 957                 err = 0;
 958         }
 959
 960         return err;
 961 }
 962
 963 /* Internal function, please use rhashtable_remove_fast() instead */
 964 static inline int __rhashtable_remove_fast(
 965         struct rhashtable *ht, struct rhash_head *obj,
 966         const struct rhashtable_params params, bool rhlist)
 967 {
 968         struct bucket_table *tbl;
 969         int err;
 970
 971         rcu_read_lock();
 972
 973         tbl = rht_dereference_rcu(ht->tbl, ht);
 974
 975         /* Because we have already taken (and released) the bucket
 976          * lock in old_tbl, if we find that future_tbl is not yet
 977          * visible then that guarantees the entry to still be in
 978          * the old tbl if it exists.
 979          */
 980         while ((err = __rhashtable_remove_fast_one(ht, tbl, obj, params,
 981                                                    rhlist)) &&
 982                (tbl = rht_dereference_rcu(tbl->future_tbl, ht)))
 983                 ;
 984
 985         rcu_read_unlock();
 986
 987         return err;
 988 }
 989
 990 /**
 991  * rhashtable_remove_fast - remove object from hash table
 992  * @ht:         hash table
 993  * @obj:        pointer to hash head inside object
 994  * @params:     hash table parameters
 995  *
 996  * Since the hash chain is single linked, the removal operation needs to
 997  * walk the bucket chain upon removal. The removal operation is thus
 998  * considerable slow if the hash table is not correctly sized.
 999  *
1000  * Will automatically shrink the table if permitted when residency drops
1001  * below 30%.
1002  *
1003  * Returns zero on success, -ENOENT if the entry could not be found.
1004  */
1005 static inline int rhashtable_remove_fast(
1006         struct rhashtable *ht, struct rhash_head *obj,
1007         const struct rhashtable_params params)
1008 {
1009         return __rhashtable_remove_fast(ht, obj, params, false);
1010 }
1011
1012 /**
1013  * rhltable_remove - remove object from hash list table
1014  * @hlt:        hash list table
1015  * @list:       pointer to hash list head inside object
1016  * @params:     hash table parameters
1017  *
1018  * Since the hash chain is single linked, the removal operation needs to
1019  * walk the bucket chain upon removal. The removal operation is thus
1020  * considerable slow if the hash table is not correctly sized.
1021  *
1022  * Will automatically shrink the table if permitted when residency drops
1023  * below 30%
1024  *
1025  * Returns zero on success, -ENOENT if the entry could not be found.
1026  */
1027 static inline int rhltable_remove(
1028         struct rhltable *hlt, struct rhlist_head *list,
1029         const struct rhashtable_params params)
1030 {
1031         return __rhashtable_remove_fast(&hlt->ht, &list->rhead, params, true);
1032 }
1033
1034 /* Internal function, please use rhashtable_replace_fast() instead */
1035 static inline int __rhashtable_replace_fast(
1036         struct rhashtable *ht, struct bucket_table *tbl,
1037         struct rhash_head *obj_old, struct rhash_head *obj_new,
1038         const struct rhashtable_params params)
1039 {
1040         struct rhash_head __rcu **pprev;
1041         struct rhash_head *he;
1042         spinlock_t *lock;
1043         unsigned int hash;
1044         int err = -ENOENT;
1045
1046         /* Minimally, the old and new objects must have same hash
1047          * (which should mean identifiers are the same).
1048          */
1049         hash = rht_head_hashfn(ht, tbl, obj_old, params);
1050         if (hash != rht_head_hashfn(ht, tbl, obj_new, params))
1051                 return -EINVAL;
1052
1053         lock = rht_bucket_lock(tbl, hash);
1054
1055         spin_lock_bh(lock);
1056
1057         pprev = rht_bucket_var(tbl, hash);
1058         rht_for_each_continue(he, *pprev, tbl, hash) {
1059                 if (he != obj_old) {
1060                         pprev = &he->next;
1061                         continue;
1062                 }
1063
1064                 rcu_assign_pointer(obj_new->next, obj_old->next);
1065                 rcu_assign_pointer(*pprev, obj_new);
1066                 err = 0;
1067                 break;
1068         }
1069
1070         spin_unlock_bh(lock);
1071
1072         return err;
1073 }
1074
1075 /**
1076  * rhashtable_replace_fast - replace an object in hash table
1077  * @ht:         hash table
1078  * @obj_old:    pointer to hash head inside object being replaced
1079  * @obj_new:    pointer to hash head inside object which is new
1080  * @params:     hash table parameters
1081  *
1082  * Replacing an object doesn't affect the number of elements in the hash table
1083  * or bucket, so we don't need to worry about shrinking or expanding the
1084  * table here.
1085  *
1086  * Returns zero on success, -ENOENT if the entry could not be found,
1087  * -EINVAL if hash is not the same for the old and new objects.
1088  */
1089 static inline int rhashtable_replace_fast(
1090         struct rhashtable *ht, struct rhash_head *obj_old,
1091         struct rhash_head *obj_new,
1092         const struct rhashtable_params params)
1093 {
1094         struct bucket_table *tbl;
1095         int err;
1096
1097         rcu_read_lock();
1098
1099         tbl = rht_dereference_rcu(ht->tbl, ht);
1100
1101         /* Because we have already taken (and released) the bucket
1102          * lock in old_tbl, if we find that future_tbl is not yet
1103          * visible then that guarantees the entry to still be in
1104          * the old tbl if it exists.
1105          */
1106         while ((err = __rhashtable_replace_fast(ht, tbl, obj_old,
1107                                                 obj_new, params)) &&
1108                (tbl = rht_dereference_rcu(tbl->future_tbl, ht)))
1109                 ;
1110
1111         rcu_read_unlock();
1112
1113         return err;
1114 }
1115
1116 /**
1117  * rhltable_walk_enter - Initialise an iterator
1118  * @hlt:        Table to walk over
1119  * @iter:       Hash table Iterator
1120  *
1121  * This function prepares a hash table walk.
1122  *
1123  * Note that if you restart a walk after rhashtable_walk_stop you
1124  * may see the same object twice.  Also, you may miss objects if
1125  * there are removals in between rhashtable_walk_stop and the next
1126  * call to rhashtable_walk_start.
1127  *
1128  * For a completely stable walk you should construct your own data
1129  * structure outside the hash table.
1130  *
1131  * This function may be called from any process context, including
1132  * non-preemptable context, but cannot be called from softirq or
1133  * hardirq context.
1134  *
1135  * You must call rhashtable_walk_exit after this function returns.
1136  */
1137 static inline void rhltable_walk_enter(struct rhltable *hlt,
1138                                        struct rhashtable_iter *iter)
1139 {
1140         return rhashtable_walk_enter(&hlt->ht, iter);
1141 }
1142
1143 /**
1144  * rhltable_free_and_destroy - free elements and destroy hash list table
1145  * @hlt:        the hash list table to destroy
1146  * @free_fn:    callback to release resources of element
1147  * @arg:        pointer passed to free_fn
1148  *
1149  * See documentation for rhashtable_free_and_destroy.
1150  */
1151 static inline void rhltable_free_and_destroy(struct rhltable *hlt,
1152                                              void (*free_fn)(void *ptr,
1153                                                              void *arg),
1154                                              void *arg)
1155 {
1156         return rhashtable_free_and_destroy(&hlt->ht, free_fn, arg);
1157 }
1158
1159 static inline void rhltable_destroy(struct rhltable *hlt)
1160 {
1161         return rhltable_free_and_destroy(hlt, NULL, NULL);
1162 }
1163
1164 #endif /* _LINUX_RHASHTABLE_H */