lib/rhashtable.c

   1 /*
   2  * Resizable, Scalable, Concurrent Hash Table
   3  *
   4  * Copyright (c) 2014-2015 Thomas Graf <tgraf@suug.ch>
   5  * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
   6  *
   7  * Based on the following paper:
   8  * https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
   9  *
  10  * Code partially derived from nft_hash
  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 #include <linux/kernel.h>
  18 #include <linux/init.h>
  19 #include <linux/log2.h>
  20 #include <linux/sched.h>
  21 #include <linux/slab.h>
  22 #include <linux/vmalloc.h>
  23 #include <linux/mm.h>
  24 #include <linux/jhash.h>
  25 #include <linux/random.h>
  26 #include <linux/rhashtable.h>
  27 #include <linux/err.h>
  28
  29 #define HASH_DEFAULT_SIZE       64UL
  30 #define HASH_MIN_SIZE           4U
  31 #define BUCKET_LOCKS_PER_CPU   128UL
  32
  33 /* Base bits plus 1 bit for nulls marker */
  34 #define HASH_RESERVED_SPACE     (RHT_BASE_BITS + 1)
  35
  36 /* The bucket lock is selected based on the hash and protects mutations
  37  * on a group of hash buckets.
  38  *
  39  * A maximum of tbl->size/2 bucket locks is allocated. This ensures that
  40  * a single lock always covers both buckets which may both contains
  41  * entries which link to the same bucket of the old table during resizing.
  42  * This allows to simplify the locking as locking the bucket in both
  43  * tables during resize always guarantee protection.
  44  *
  45  * IMPORTANT: When holding the bucket lock of both the old and new table
  46  * during expansions and shrinking, the old bucket lock must always be
  47  * acquired first.
  48  */
  49 static spinlock_t *bucket_lock(const struct bucket_table *tbl, u32 hash)
  50 {
  51         return &tbl->locks[hash & tbl->locks_mask];
  52 }
  53
  54 static void *rht_obj(const struct rhashtable *ht, const struct rhash_head *he)
  55 {
  56         return (void *) he - ht->p.head_offset;
  57 }
  58
  59 static u32 rht_bucket_index(const struct bucket_table *tbl, u32 hash)
  60 {
  61         return (hash >> HASH_RESERVED_SPACE) & (tbl->size - 1);
  62 }
  63
  64 static u32 key_hashfn(struct rhashtable *ht, const struct bucket_table *tbl,
  65                       const void *key)
  66 {
  67         return rht_bucket_index(tbl, ht->p.hashfn(key, ht->p.key_len,
  68                                                   tbl->hash_rnd));
  69 }
  70
  71 static u32 head_hashfn(struct rhashtable *ht,
  72                        const struct bucket_table *tbl,
  73                        const struct rhash_head *he)
  74 {
  75         const char *ptr = rht_obj(ht, he);
  76
  77         return likely(ht->p.key_len) ?
  78                key_hashfn(ht, tbl, ptr + ht->p.key_offset) :
  79                rht_bucket_index(tbl, ht->p.obj_hashfn(ptr, tbl->hash_rnd));
  80 }
  81
  82 #ifdef CONFIG_PROVE_LOCKING
  83 #define ASSERT_RHT_MUTEX(HT) BUG_ON(!lockdep_rht_mutex_is_held(HT))
  84
  85 int lockdep_rht_mutex_is_held(struct rhashtable *ht)
  86 {
  87         return (debug_locks) ? lockdep_is_held(&ht->mutex) : 1;
  88 }
  89 EXPORT_SYMBOL_GPL(lockdep_rht_mutex_is_held);
  90
  91 int lockdep_rht_bucket_is_held(const struct bucket_table *tbl, u32 hash)
  92 {
  93         spinlock_t *lock = bucket_lock(tbl, hash);
  94
  95         return (debug_locks) ? lockdep_is_held(lock) : 1;
  96 }
  97 EXPORT_SYMBOL_GPL(lockdep_rht_bucket_is_held);
  98 #else
  99 #define ASSERT_RHT_MUTEX(HT)
 100 #endif
 101
 102
 103 static int alloc_bucket_locks(struct rhashtable *ht, struct bucket_table *tbl)
 104 {
 105         unsigned int i, size;
 106 #if defined(CONFIG_PROVE_LOCKING)
 107         unsigned int nr_pcpus = 2;
 108 #else
 109         unsigned int nr_pcpus = num_possible_cpus();
 110 #endif
 111
 112         nr_pcpus = min_t(unsigned int, nr_pcpus, 32UL);
 113         size = roundup_pow_of_two(nr_pcpus * ht->p.locks_mul);
 114
 115         /* Never allocate more than 0.5 locks per bucket */
 116         size = min_t(unsigned int, size, tbl->size >> 1);
 117
 118         if (sizeof(spinlock_t) != 0) {
 119 #ifdef CONFIG_NUMA
 120                 if (size * sizeof(spinlock_t) > PAGE_SIZE)
 121                         tbl->locks = vmalloc(size * sizeof(spinlock_t));
 122                 else
 123 #endif
 124                 tbl->locks = kmalloc_array(size, sizeof(spinlock_t),
 125                                            GFP_KERNEL);
 126                 if (!tbl->locks)
 127                         return -ENOMEM;
 128                 for (i = 0; i < size; i++)
 129                         spin_lock_init(&tbl->locks[i]);
 130         }
 131         tbl->locks_mask = size - 1;
 132
 133         return 0;
 134 }
 135
 136 static void bucket_table_free(const struct bucket_table *tbl)
 137 {
 138         if (tbl)
 139                 kvfree(tbl->locks);
 140
 141         kvfree(tbl);
 142 }
 143
 144 static void bucket_table_free_rcu(struct rcu_head *head)
 145 {
 146         bucket_table_free(container_of(head, struct bucket_table, rcu));
 147 }
 148
 149 static struct bucket_table *bucket_table_alloc(struct rhashtable *ht,
 150                                                size_t nbuckets)
 151 {
 152         struct bucket_table *tbl = NULL;
 153         size_t size;
 154         int i;
 155
 156         size = sizeof(*tbl) + nbuckets * sizeof(tbl->buckets[0]);
 157         if (size <= (PAGE_SIZE << PAGE_ALLOC_COSTLY_ORDER))
 158                 tbl = kzalloc(size, GFP_KERNEL | __GFP_NOWARN | __GFP_NORETRY);
 159         if (tbl == NULL)
 160                 tbl = vzalloc(size);
 161         if (tbl == NULL)
 162                 return NULL;
 163
 164         tbl->size = nbuckets;
 165
 166         if (alloc_bucket_locks(ht, tbl) < 0) {
 167                 bucket_table_free(tbl);
 168                 return NULL;
 169         }
 170
 171         INIT_LIST_HEAD(&tbl->walkers);
 172
 173         get_random_bytes(&tbl->hash_rnd, sizeof(tbl->hash_rnd));
 174
 175         for (i = 0; i < nbuckets; i++)
 176                 INIT_RHT_NULLS_HEAD(tbl->buckets[i], ht, i);
 177
 178         return tbl;
 179 }
 180
 181 /**
 182  * rht_grow_above_75 - returns true if nelems > 0.75 * table-size
 183  * @ht:         hash table
 184  * @tbl:        current table
 185  */
 186 static bool rht_grow_above_75(const struct rhashtable *ht,
 187                               const struct bucket_table *tbl)
 188 {
 189         /* Expand table when exceeding 75% load */
 190         return atomic_read(&ht->nelems) > (tbl->size / 4 * 3) &&
 191                (!ht->p.max_shift || tbl->size < (1 << ht->p.max_shift)) &&
 192                (!ht->p.max_size || tbl->size < ht->p.max_size);
 193 }
 194
 195 /**
 196  * rht_shrink_below_30 - returns true if nelems < 0.3 * table-size
 197  * @ht:         hash table
 198  * @tbl:        current table
 199  */
 200 static bool rht_shrink_below_30(const struct rhashtable *ht,
 201                                 const struct bucket_table *tbl)
 202 {
 203         /* Shrink table beneath 30% load */
 204         return atomic_read(&ht->nelems) < (tbl->size * 3 / 10) &&
 205                tbl->size > (1 << ht->p.min_shift) &&
 206                tbl->size > ht->p.min_size;
 207 }
 208
 209 static int rhashtable_rehash_one(struct rhashtable *ht, unsigned old_hash)
 210 {
 211         struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
 212         struct bucket_table *new_tbl =
 213                 rht_dereference(old_tbl->future_tbl, ht) ?: old_tbl;
 214         struct rhash_head __rcu **pprev = &old_tbl->buckets[old_hash];
 215         int err = -ENOENT;
 216         struct rhash_head *head, *next, *entry;
 217         spinlock_t *new_bucket_lock;
 218         unsigned new_hash;
 219
 220         rht_for_each(entry, old_tbl, old_hash) {
 221                 err = 0;
 222                 next = rht_dereference_bucket(entry->next, old_tbl, old_hash);
 223
 224                 if (rht_is_a_nulls(next))
 225                         break;
 226
 227                 pprev = &entry->next;
 228         }
 229
 230         if (err)
 231                 goto out;
 232
 233         new_hash = head_hashfn(ht, new_tbl, entry);
 234
 235         new_bucket_lock = bucket_lock(new_tbl, new_hash);
 236
 237         spin_lock_nested(new_bucket_lock, SINGLE_DEPTH_NESTING);
 238         head = rht_dereference_bucket(new_tbl->buckets[new_hash],
 239                                       new_tbl, new_hash);
 240
 241         if (rht_is_a_nulls(head))
 242                 INIT_RHT_NULLS_HEAD(entry->next, ht, new_hash);
 243         else
 244                 RCU_INIT_POINTER(entry->next, head);
 245
 246         rcu_assign_pointer(new_tbl->buckets[new_hash], entry);
 247         spin_unlock(new_bucket_lock);
 248
 249         rcu_assign_pointer(*pprev, next);
 250
 251 out:
 252         return err;
 253 }
 254
 255 static void rhashtable_rehash_chain(struct rhashtable *ht, unsigned old_hash)
 256 {
 257         struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
 258         spinlock_t *old_bucket_lock;
 259
 260         old_bucket_lock = bucket_lock(old_tbl, old_hash);
 261
 262         spin_lock_bh(old_bucket_lock);
 263         while (!rhashtable_rehash_one(ht, old_hash))
 264                 ;
 265         old_tbl->rehash++;
 266         spin_unlock_bh(old_bucket_lock);
 267 }
 268
 269 static void rhashtable_rehash(struct rhashtable *ht,
 270                               struct bucket_table *new_tbl)
 271 {
 272         struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
 273         struct rhashtable_walker *walker;
 274         unsigned old_hash;
 275
 276         /* Make insertions go into the new, empty table right away. Deletions
 277          * and lookups will be attempted in both tables until we synchronize.
 278          */
 279         rcu_assign_pointer(old_tbl->future_tbl, new_tbl);
 280
 281         /* Ensure the new table is visible to readers. */
 282         smp_wmb();
 283
 284         for (old_hash = 0; old_hash < old_tbl->size; old_hash++)
 285                 rhashtable_rehash_chain(ht, old_hash);
 286
 287         /* Publish the new table pointer. */
 288         rcu_assign_pointer(ht->tbl, new_tbl);
 289
 290         list_for_each_entry(walker, &old_tbl->walkers, list)
 291                 walker->tbl = NULL;
 292
 293         /* Wait for readers. All new readers will see the new
 294          * table, and thus no references to the old table will
 295          * remain.
 296          */
 297         call_rcu(&old_tbl->rcu, bucket_table_free_rcu);
 298 }
 299
 300 /**
 301  * rhashtable_expand - Expand hash table while allowing concurrent lookups
 302  * @ht:         the hash table to expand
 303  *
 304  * A secondary bucket array is allocated and the hash entries are migrated.
 305  *
 306  * This function may only be called in a context where it is safe to call
 307  * synchronize_rcu(), e.g. not within a rcu_read_lock() section.
 308  *
 309  * The caller must ensure that no concurrent resizing occurs by holding
 310  * ht->mutex.
 311  *
 312  * It is valid to have concurrent insertions and deletions protected by per
 313  * bucket locks or concurrent RCU protected lookups and traversals.
 314  */
 315 int rhashtable_expand(struct rhashtable *ht)
 316 {
 317         struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);
 318
 319         ASSERT_RHT_MUTEX(ht);
 320
 321         new_tbl = bucket_table_alloc(ht, old_tbl->size * 2);
 322         if (new_tbl == NULL)
 323                 return -ENOMEM;
 324
 325         rhashtable_rehash(ht, new_tbl);
 326         return 0;
 327 }
 328 EXPORT_SYMBOL_GPL(rhashtable_expand);
 329
 330 /**
 331  * rhashtable_shrink - Shrink hash table while allowing concurrent lookups
 332  * @ht:         the hash table to shrink
 333  *
 334  * This function may only be called in a context where it is safe to call
 335  * synchronize_rcu(), e.g. not within a rcu_read_lock() section.
 336  *
 337  * The caller must ensure that no concurrent resizing occurs by holding
 338  * ht->mutex.
 339  *
 340  * The caller must ensure that no concurrent table mutations take place.
 341  * It is however valid to have concurrent lookups if they are RCU protected.
 342  *
 343  * It is valid to have concurrent insertions and deletions protected by per
 344  * bucket locks or concurrent RCU protected lookups and traversals.
 345  */
 346 int rhashtable_shrink(struct rhashtable *ht)
 347 {
 348         struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);
 349
 350         ASSERT_RHT_MUTEX(ht);
 351
 352         new_tbl = bucket_table_alloc(ht, old_tbl->size / 2);
 353         if (new_tbl == NULL)
 354                 return -ENOMEM;
 355
 356         rhashtable_rehash(ht, new_tbl);
 357         return 0;
 358 }
 359 EXPORT_SYMBOL_GPL(rhashtable_shrink);
 360
 361 static void rht_deferred_worker(struct work_struct *work)
 362 {
 363         struct rhashtable *ht;
 364         struct bucket_table *tbl;
 365
 366         ht = container_of(work, struct rhashtable, run_work);
 367         mutex_lock(&ht->mutex);
 368         if (ht->being_destroyed)
 369                 goto unlock;
 370
 371         tbl = rht_dereference(ht->tbl, ht);
 372
 373         if (rht_grow_above_75(ht, tbl))
 374                 rhashtable_expand(ht);
 375         else if (rht_shrink_below_30(ht, tbl))
 376                 rhashtable_shrink(ht);
 377 unlock:
 378         mutex_unlock(&ht->mutex);
 379 }
 380
 381 static bool __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
 382                                 bool (*compare)(void *, void *), void *arg)
 383 {
 384         struct bucket_table *tbl, *old_tbl;
 385         struct rhash_head *head;
 386         bool no_resize_running;
 387         unsigned hash;
 388         spinlock_t *old_lock;
 389         bool success = true;
 390
 391         rcu_read_lock();
 392
 393         old_tbl = rht_dereference_rcu(ht->tbl, ht);
 394         hash = head_hashfn(ht, old_tbl, obj);
 395         old_lock = bucket_lock(old_tbl, hash);
 396
 397         spin_lock_bh(old_lock);
 398
 399         /* Because we have already taken the bucket lock in old_tbl,
 400          * if we find that future_tbl is not yet visible then that
 401          * guarantees all other insertions of the same entry will
 402          * also grab the bucket lock in old_tbl because until the
 403          * rehash completes ht->tbl won't be changed.
 404          */
 405         tbl = rht_dereference_rcu(old_tbl->future_tbl, ht) ?: old_tbl;
 406         if (tbl != old_tbl) {
 407                 hash = head_hashfn(ht, tbl, obj);
 408                 spin_lock_nested(bucket_lock(tbl, hash), SINGLE_DEPTH_NESTING);
 409         }
 410
 411         if (compare &&
 412             rhashtable_lookup_compare(ht, rht_obj(ht, obj) + ht->p.key_offset,
 413                                       compare, arg)) {
 414                 success = false;
 415                 goto exit;
 416         }
 417
 418         no_resize_running = tbl == old_tbl;
 419
 420         head = rht_dereference_bucket(tbl->buckets[hash], tbl, hash);
 421
 422         if (rht_is_a_nulls(head))
 423                 INIT_RHT_NULLS_HEAD(obj->next, ht, hash);
 424         else
 425                 RCU_INIT_POINTER(obj->next, head);
 426
 427         rcu_assign_pointer(tbl->buckets[hash], obj);
 428
 429         atomic_inc(&ht->nelems);
 430         if (no_resize_running && rht_grow_above_75(ht, tbl))
 431                 schedule_work(&ht->run_work);
 432
 433 exit:
 434         if (tbl != old_tbl)
 435                 spin_unlock(bucket_lock(tbl, hash));
 436
 437         spin_unlock_bh(old_lock);
 438
 439         rcu_read_unlock();
 440
 441         return success;
 442 }
 443
 444 /**
 445  * rhashtable_insert - insert object into hash table
 446  * @ht:         hash table
 447  * @obj:        pointer to hash head inside object
 448  *
 449  * Will take a per bucket spinlock to protect against mutual mutations
 450  * on the same bucket. Multiple insertions may occur in parallel unless
 451  * they map to the same bucket lock.
 452  *
 453  * It is safe to call this function from atomic context.
 454  *
 455  * Will trigger an automatic deferred table resizing if the size grows
 456  * beyond the watermark indicated by grow_decision() which can be passed
 457  * to rhashtable_init().
 458  */
 459 void rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj)
 460 {
 461         __rhashtable_insert(ht, obj, NULL, NULL);
 462 }
 463 EXPORT_SYMBOL_GPL(rhashtable_insert);
 464
 465 static bool __rhashtable_remove(struct rhashtable *ht,
 466                                 struct bucket_table *tbl,
 467                                 struct rhash_head *obj)
 468 {
 469         struct rhash_head __rcu **pprev;
 470         struct rhash_head *he;
 471         spinlock_t * lock;
 472         unsigned hash;
 473         bool ret = false;
 474
 475         hash = head_hashfn(ht, tbl, obj);
 476         lock = bucket_lock(tbl, hash);
 477
 478         spin_lock_bh(lock);
 479
 480         pprev = &tbl->buckets[hash];
 481         rht_for_each(he, tbl, hash) {
 482                 if (he != obj) {
 483                         pprev = &he->next;
 484                         continue;
 485                 }
 486
 487                 rcu_assign_pointer(*pprev, obj->next);
 488                 ret = true;
 489                 break;
 490         }
 491
 492         spin_unlock_bh(lock);
 493
 494         return ret;
 495 }
 496
 497 /**
 498  * rhashtable_remove - remove object from hash table
 499  * @ht:         hash table
 500  * @obj:        pointer to hash head inside object
 501  *
 502  * Since the hash chain is single linked, the removal operation needs to
 503  * walk the bucket chain upon removal. The removal operation is thus
 504  * considerable slow if the hash table is not correctly sized.
 505  *
 506  * Will automatically shrink the table via rhashtable_expand() if the
 507  * shrink_decision function specified at rhashtable_init() returns true.
 508  *
 509  * The caller must ensure that no concurrent table mutations occur. It is
 510  * however valid to have concurrent lookups if they are RCU protected.
 511  */
 512 bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *obj)
 513 {
 514         struct bucket_table *tbl;
 515         bool ret;
 516
 517         rcu_read_lock();
 518
 519         tbl = rht_dereference_rcu(ht->tbl, ht);
 520
 521         /* Because we have already taken (and released) the bucket
 522          * lock in old_tbl, if we find that future_tbl is not yet
 523          * visible then that guarantees the entry to still be in
 524          * the old tbl if it exists.
 525          */
 526         while (!(ret = __rhashtable_remove(ht, tbl, obj)) &&
 527                (tbl = rht_dereference_rcu(tbl->future_tbl, ht)))
 528                 ;
 529
 530         if (ret) {
 531                 atomic_dec(&ht->nelems);
 532                 if (rht_shrink_below_30(ht, tbl))
 533                         schedule_work(&ht->run_work);
 534         }
 535
 536         rcu_read_unlock();
 537
 538         return ret;
 539 }
 540 EXPORT_SYMBOL_GPL(rhashtable_remove);
 541
 542 struct rhashtable_compare_arg {
 543         struct rhashtable *ht;
 544         const void *key;
 545 };
 546
 547 static bool rhashtable_compare(void *ptr, void *arg)
 548 {
 549         struct rhashtable_compare_arg *x = arg;
 550         struct rhashtable *ht = x->ht;
 551
 552         return !memcmp(ptr + ht->p.key_offset, x->key, ht->p.key_len);
 553 }
 554
 555 /**
 556  * rhashtable_lookup - lookup key in hash table
 557  * @ht:         hash table
 558  * @key:        pointer to key
 559  *
 560  * Computes the hash value for the key and traverses the bucket chain looking
 561  * for a entry with an identical key. The first matching entry is returned.
 562  *
 563  * This lookup function may only be used for fixed key hash table (key_len
 564  * parameter set). It will BUG() if used inappropriately.
 565  *
 566  * Lookups may occur in parallel with hashtable mutations and resizing.
 567  */
 568 void *rhashtable_lookup(struct rhashtable *ht, const void *key)
 569 {
 570         struct rhashtable_compare_arg arg = {
 571                 .ht = ht,
 572                 .key = key,
 573         };
 574
 575         BUG_ON(!ht->p.key_len);
 576
 577         return rhashtable_lookup_compare(ht, key, &rhashtable_compare, &arg);
 578 }
 579 EXPORT_SYMBOL_GPL(rhashtable_lookup);
 580
 581 /**
 582  * rhashtable_lookup_compare - search hash table with compare function
 583  * @ht:         hash table
 584  * @key:        the pointer to the key
 585  * @compare:    compare function, must return true on match
 586  * @arg:        argument passed on to compare function
 587  *
 588  * Traverses the bucket chain behind the provided hash value and calls the
 589  * specified compare function for each entry.
 590  *
 591  * Lookups may occur in parallel with hashtable mutations and resizing.
 592  *
 593  * Returns the first entry on which the compare function returned true.
 594  */
 595 void *rhashtable_lookup_compare(struct rhashtable *ht, const void *key,
 596                                 bool (*compare)(void *, void *), void *arg)
 597 {
 598         const struct bucket_table *tbl;
 599         struct rhash_head *he;
 600         u32 hash;
 601
 602         rcu_read_lock();
 603
 604         tbl = rht_dereference_rcu(ht->tbl, ht);
 605 restart:
 606         hash = key_hashfn(ht, tbl, key);
 607         rht_for_each_rcu(he, tbl, hash) {
 608                 if (!compare(rht_obj(ht, he), arg))
 609                         continue;
 610                 rcu_read_unlock();
 611                 return rht_obj(ht, he);
 612         }
 613
 614         /* Ensure we see any new tables. */
 615         smp_rmb();
 616
 617         tbl = rht_dereference_rcu(tbl->future_tbl, ht);
 618         if (unlikely(tbl))
 619                 goto restart;
 620         rcu_read_unlock();
 621
 622         return NULL;
 623 }
 624 EXPORT_SYMBOL_GPL(rhashtable_lookup_compare);
 625
 626 /**
 627  * rhashtable_lookup_insert - lookup and insert object into hash table
 628  * @ht:         hash table
 629  * @obj:        pointer to hash head inside object
 630  *
 631  * Locks down the bucket chain in both the old and new table if a resize
 632  * is in progress to ensure that writers can't remove from the old table
 633  * and can't insert to the new table during the atomic operation of search
 634  * and insertion. Searches for duplicates in both the old and new table if
 635  * a resize is in progress.
 636  *
 637  * This lookup function may only be used for fixed key hash table (key_len
 638  * parameter set). It will BUG() if used inappropriately.
 639  *
 640  * It is safe to call this function from atomic context.
 641  *
 642  * Will trigger an automatic deferred table resizing if the size grows
 643  * beyond the watermark indicated by grow_decision() which can be passed
 644  * to rhashtable_init().
 645  */
 646 bool rhashtable_lookup_insert(struct rhashtable *ht, struct rhash_head *obj)
 647 {
 648         struct rhashtable_compare_arg arg = {
 649                 .ht = ht,
 650                 .key = rht_obj(ht, obj) + ht->p.key_offset,
 651         };
 652
 653         BUG_ON(!ht->p.key_len);
 654
 655         return rhashtable_lookup_compare_insert(ht, obj, &rhashtable_compare,
 656                                                 &arg);
 657 }
 658 EXPORT_SYMBOL_GPL(rhashtable_lookup_insert);
 659
 660 /**
 661  * rhashtable_lookup_compare_insert - search and insert object to hash table
 662  *                                    with compare function
 663  * @ht:         hash table
 664  * @obj:        pointer to hash head inside object
 665  * @compare:    compare function, must return true on match
 666  * @arg:        argument passed on to compare function
 667  *
 668  * Locks down the bucket chain in both the old and new table if a resize
 669  * is in progress to ensure that writers can't remove from the old table
 670  * and can't insert to the new table during the atomic operation of search
 671  * and insertion. Searches for duplicates in both the old and new table if
 672  * a resize is in progress.
 673  *
 674  * Lookups may occur in parallel with hashtable mutations and resizing.
 675  *
 676  * Will trigger an automatic deferred table resizing if the size grows
 677  * beyond the watermark indicated by grow_decision() which can be passed
 678  * to rhashtable_init().
 679  */
 680 bool rhashtable_lookup_compare_insert(struct rhashtable *ht,
 681                                       struct rhash_head *obj,
 682                                       bool (*compare)(void *, void *),
 683                                       void *arg)
 684 {
 685         BUG_ON(!ht->p.key_len);
 686
 687         return __rhashtable_insert(ht, obj, compare, arg);
 688 }
 689 EXPORT_SYMBOL_GPL(rhashtable_lookup_compare_insert);
 690
 691 /**
 692  * rhashtable_walk_init - Initialise an iterator
 693  * @ht:         Table to walk over
 694  * @iter:       Hash table Iterator
 695  *
 696  * This function prepares a hash table walk.
 697  *
 698  * Note that if you restart a walk after rhashtable_walk_stop you
 699  * may see the same object twice.  Also, you may miss objects if
 700  * there are removals in between rhashtable_walk_stop and the next
 701  * call to rhashtable_walk_start.
 702  *
 703  * For a completely stable walk you should construct your own data
 704  * structure outside the hash table.
 705  *
 706  * This function may sleep so you must not call it from interrupt
 707  * context or with spin locks held.
 708  *
 709  * You must call rhashtable_walk_exit if this function returns
 710  * successfully.
 711  */
 712 int rhashtable_walk_init(struct rhashtable *ht, struct rhashtable_iter *iter)
 713 {
 714         iter->ht = ht;
 715         iter->p = NULL;
 716         iter->slot = 0;
 717         iter->skip = 0;
 718
 719         iter->walker = kmalloc(sizeof(*iter->walker), GFP_KERNEL);
 720         if (!iter->walker)
 721                 return -ENOMEM;
 722
 723         mutex_lock(&ht->mutex);
 724         iter->walker->tbl = rht_dereference(ht->tbl, ht);
 725         list_add(&iter->walker->list, &iter->walker->tbl->walkers);
 726         mutex_unlock(&ht->mutex);
 727
 728         return 0;
 729 }
 730 EXPORT_SYMBOL_GPL(rhashtable_walk_init);
 731
 732 /**
 733  * rhashtable_walk_exit - Free an iterator
 734  * @iter:       Hash table Iterator
 735  *
 736  * This function frees resources allocated by rhashtable_walk_init.
 737  */
 738 void rhashtable_walk_exit(struct rhashtable_iter *iter)
 739 {
 740         mutex_lock(&iter->ht->mutex);
 741         if (iter->walker->tbl)
 742                 list_del(&iter->walker->list);
 743         mutex_unlock(&iter->ht->mutex);
 744         kfree(iter->walker);
 745 }
 746 EXPORT_SYMBOL_GPL(rhashtable_walk_exit);
 747
 748 /**
 749  * rhashtable_walk_start - Start a hash table walk
 750  * @iter:       Hash table iterator
 751  *
 752  * Start a hash table walk.  Note that we take the RCU lock in all
 753  * cases including when we return an error.  So you must always call
 754  * rhashtable_walk_stop to clean up.
 755  *
 756  * Returns zero if successful.
 757  *
 758  * Returns -EAGAIN if resize event occured.  Note that the iterator
 759  * will rewind back to the beginning and you may use it immediately
 760  * by calling rhashtable_walk_next.
 761  */
 762 int rhashtable_walk_start(struct rhashtable_iter *iter)
 763         __acquires(RCU)
 764 {
 765         struct rhashtable *ht = iter->ht;
 766
 767         mutex_lock(&ht->mutex);
 768
 769         if (iter->walker->tbl)
 770                 list_del(&iter->walker->list);
 771
 772         rcu_read_lock();
 773
 774         mutex_unlock(&ht->mutex);
 775
 776         if (!iter->walker->tbl) {
 777                 iter->walker->tbl = rht_dereference_rcu(ht->tbl, ht);
 778                 return -EAGAIN;
 779         }
 780
 781         return 0;
 782 }
 783 EXPORT_SYMBOL_GPL(rhashtable_walk_start);
 784
 785 /**
 786  * rhashtable_walk_next - Return the next object and advance the iterator
 787  * @iter:       Hash table iterator
 788  *
 789  * Note that you must call rhashtable_walk_stop when you are finished
 790  * with the walk.
 791  *
 792  * Returns the next object or NULL when the end of the table is reached.
 793  *
 794  * Returns -EAGAIN if resize event occured.  Note that the iterator
 795  * will rewind back to the beginning and you may continue to use it.
 796  */
 797 void *rhashtable_walk_next(struct rhashtable_iter *iter)
 798 {
 799         struct bucket_table *tbl = iter->walker->tbl;
 800         struct rhashtable *ht = iter->ht;
 801         struct rhash_head *p = iter->p;
 802         void *obj = NULL;
 803
 804         if (p) {
 805                 p = rht_dereference_bucket_rcu(p->next, tbl, iter->slot);
 806                 goto next;
 807         }
 808
 809         for (; iter->slot < tbl->size; iter->slot++) {
 810                 int skip = iter->skip;
 811
 812                 rht_for_each_rcu(p, tbl, iter->slot) {
 813                         if (!skip)
 814                                 break;
 815                         skip--;
 816                 }
 817
 818 next:
 819                 if (!rht_is_a_nulls(p)) {
 820                         iter->skip++;
 821                         iter->p = p;
 822                         obj = rht_obj(ht, p);
 823                         goto out;
 824                 }
 825
 826                 iter->skip = 0;
 827         }
 828
 829         iter->walker->tbl = rht_dereference_rcu(tbl->future_tbl, ht);
 830         if (iter->walker->tbl) {
 831                 iter->slot = 0;
 832                 iter->skip = 0;
 833                 return ERR_PTR(-EAGAIN);
 834         }
 835
 836         iter->p = NULL;
 837
 838 out:
 839
 840         return obj;
 841 }
 842 EXPORT_SYMBOL_GPL(rhashtable_walk_next);
 843
 844 /**
 845  * rhashtable_walk_stop - Finish a hash table walk
 846  * @iter:       Hash table iterator
 847  *
 848  * Finish a hash table walk.
 849  */
 850 void rhashtable_walk_stop(struct rhashtable_iter *iter)
 851         __releases(RCU)
 852 {
 853         struct rhashtable *ht;
 854         struct bucket_table *tbl = iter->walker->tbl;
 855
 856         if (!tbl)
 857                 goto out;
 858
 859         ht = iter->ht;
 860
 861         mutex_lock(&ht->mutex);
 862         if (tbl->rehash < tbl->size)
 863                 list_add(&iter->walker->list, &tbl->walkers);
 864         else
 865                 iter->walker->tbl = NULL;
 866         mutex_unlock(&ht->mutex);
 867
 868         iter->p = NULL;
 869
 870 out:
 871         rcu_read_unlock();
 872 }
 873 EXPORT_SYMBOL_GPL(rhashtable_walk_stop);
 874
 875 static size_t rounded_hashtable_size(struct rhashtable_params *params)
 876 {
 877         return max(roundup_pow_of_two(params->nelem_hint * 4 / 3),
 878                    max(1UL << params->min_shift,
 879                        (unsigned long)params->min_size));
 880 }
 881
 882 /**
 883  * rhashtable_init - initialize a new hash table
 884  * @ht:         hash table to be initialized
 885  * @params:     configuration parameters
 886  *
 887  * Initializes a new hash table based on the provided configuration
 888  * parameters. A table can be configured either with a variable or
 889  * fixed length key:
 890  *
 891  * Configuration Example 1: Fixed length keys
 892  * struct test_obj {
 893  *      int                     key;
 894  *      void *                  my_member;
 895  *      struct rhash_head       node;
 896  * };
 897  *
 898  * struct rhashtable_params params = {
 899  *      .head_offset = offsetof(struct test_obj, node),
 900  *      .key_offset = offsetof(struct test_obj, key),
 901  *      .key_len = sizeof(int),
 902  *      .hashfn = jhash,
 903  *      .nulls_base = (1U << RHT_BASE_SHIFT),
 904  * };
 905  *
 906  * Configuration Example 2: Variable length keys
 907  * struct test_obj {
 908  *      [...]
 909  *      struct rhash_head       node;
 910  * };
 911  *
 912  * u32 my_hash_fn(const void *data, u32 seed)
 913  * {
 914  *      struct test_obj *obj = data;
 915  *
 916  *      return [... hash ...];
 917  * }
 918  *
 919  * struct rhashtable_params params = {
 920  *      .head_offset = offsetof(struct test_obj, node),
 921  *      .hashfn = jhash,
 922  *      .obj_hashfn = my_hash_fn,
 923  * };
 924  */
 925 int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params)
 926 {
 927         struct bucket_table *tbl;
 928         size_t size;
 929
 930         size = HASH_DEFAULT_SIZE;
 931
 932         if ((params->key_len && !params->hashfn) ||
 933             (!params->key_len && !params->obj_hashfn))
 934                 return -EINVAL;
 935
 936         if (params->nulls_base && params->nulls_base < (1U << RHT_BASE_SHIFT))
 937                 return -EINVAL;
 938
 939         params->min_shift = max_t(size_t, params->min_shift,
 940                                   ilog2(HASH_MIN_SIZE));
 941         params->min_size = max(params->min_size, HASH_MIN_SIZE);
 942
 943         if (params->nelem_hint)
 944                 size = rounded_hashtable_size(params);
 945
 946         memset(ht, 0, sizeof(*ht));
 947         mutex_init(&ht->mutex);
 948         memcpy(&ht->p, params, sizeof(*params));
 949
 950         if (params->locks_mul)
 951                 ht->p.locks_mul = roundup_pow_of_two(params->locks_mul);
 952         else
 953                 ht->p.locks_mul = BUCKET_LOCKS_PER_CPU;
 954
 955         tbl = bucket_table_alloc(ht, size);
 956         if (tbl == NULL)
 957                 return -ENOMEM;
 958
 959         atomic_set(&ht->nelems, 0);
 960
 961         RCU_INIT_POINTER(ht->tbl, tbl);
 962
 963         INIT_WORK(&ht->run_work, rht_deferred_worker);
 964
 965         return 0;
 966 }
 967 EXPORT_SYMBOL_GPL(rhashtable_init);
 968
 969 /**
 970  * rhashtable_destroy - destroy hash table
 971  * @ht:         the hash table to destroy
 972  *
 973  * Frees the bucket array. This function is not rcu safe, therefore the caller
 974  * has to make sure that no resizing may happen by unpublishing the hashtable
 975  * and waiting for the quiescent cycle before releasing the bucket array.
 976  */
 977 void rhashtable_destroy(struct rhashtable *ht)
 978 {
 979         ht->being_destroyed = true;
 980
 981         cancel_work_sync(&ht->run_work);
 982
 983         mutex_lock(&ht->mutex);
 984         bucket_table_free(rht_dereference(ht->tbl, ht));
 985         mutex_unlock(&ht->mutex);
 986 }
 987 EXPORT_SYMBOL_GPL(rhashtable_destroy);