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           4UL
  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         tbl->shift = ilog2(nbuckets);
 166
 167         if (alloc_bucket_locks(ht, tbl) < 0) {
 168                 bucket_table_free(tbl);
 169                 return NULL;
 170         }
 171
 172         INIT_LIST_HEAD(&tbl->walkers);
 173
 174         get_random_bytes(&tbl->hash_rnd, sizeof(tbl->hash_rnd));
 175
 176         for (i = 0; i < nbuckets; i++)
 177                 INIT_RHT_NULLS_HEAD(tbl->buckets[i], ht, i);
 178
 179         return tbl;
 180 }
 181
 182 /**
 183  * rht_grow_above_75 - returns true if nelems > 0.75 * table-size
 184  * @ht:         hash table
 185  * @tbl:        current table
 186  */
 187 static bool rht_grow_above_75(const struct rhashtable *ht,
 188                               const struct bucket_table *tbl)
 189 {
 190         /* Expand table when exceeding 75% load */
 191         return atomic_read(&ht->nelems) > (tbl->size / 4 * 3) &&
 192                (!ht->p.max_shift || tbl->shift < ht->p.max_shift);
 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->shift > ht->p.min_shift;
 206 }
 207
 208 static int rhashtable_rehash_one(struct rhashtable *ht, unsigned old_hash)
 209 {
 210         struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
 211         struct bucket_table *new_tbl =
 212                 rht_dereference(old_tbl->future_tbl, ht) ?: old_tbl;
 213         struct rhash_head __rcu **pprev = &old_tbl->buckets[old_hash];
 214         int err = -ENOENT;
 215         struct rhash_head *head, *next, *entry;
 216         spinlock_t *new_bucket_lock;
 217         unsigned new_hash;
 218
 219         rht_for_each(entry, old_tbl, old_hash) {
 220                 err = 0;
 221                 next = rht_dereference_bucket(entry->next, old_tbl, old_hash);
 222
 223                 if (rht_is_a_nulls(next))
 224                         break;
 225
 226                 pprev = &entry->next;
 227         }
 228
 229         if (err)
 230                 goto out;
 231
 232         new_hash = head_hashfn(ht, new_tbl, entry);
 233
 234         new_bucket_lock = bucket_lock(new_tbl, new_hash);
 235
 236         spin_lock_nested(new_bucket_lock, SINGLE_DEPTH_NESTING);
 237         head = rht_dereference_bucket(new_tbl->buckets[new_hash],
 238                                       new_tbl, new_hash);
 239
 240         if (rht_is_a_nulls(head))
 241                 INIT_RHT_NULLS_HEAD(entry->next, ht, new_hash);
 242         else
 243                 RCU_INIT_POINTER(entry->next, head);
 244
 245         rcu_assign_pointer(new_tbl->buckets[new_hash], entry);
 246         spin_unlock(new_bucket_lock);
 247
 248         rcu_assign_pointer(*pprev, next);
 249
 250 out:
 251         return err;
 252 }
 253
 254 static void rhashtable_rehash_chain(struct rhashtable *ht, unsigned old_hash)
 255 {
 256         struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
 257         spinlock_t *old_bucket_lock;
 258
 259         old_bucket_lock = bucket_lock(old_tbl, old_hash);
 260
 261         spin_lock_bh(old_bucket_lock);
 262         while (!rhashtable_rehash_one(ht, old_hash))
 263                 ;
 264         old_tbl->rehash++;
 265         spin_unlock_bh(old_bucket_lock);
 266 }
 267
 268 static void rhashtable_rehash(struct rhashtable *ht,
 269                               struct bucket_table *new_tbl)
 270 {
 271         struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
 272         struct rhashtable_walker *walker;
 273         unsigned old_hash;
 274
 275         /* Make insertions go into the new, empty table right away. Deletions
 276          * and lookups will be attempted in both tables until we synchronize.
 277          */
 278         rcu_assign_pointer(old_tbl->future_tbl, new_tbl);
 279
 280         /* Ensure the new table is visible to readers. */
 281         smp_wmb();
 282
 283         for (old_hash = 0; old_hash < old_tbl->size; old_hash++)
 284                 rhashtable_rehash_chain(ht, old_hash);
 285
 286         /* Publish the new table pointer. */
 287         rcu_assign_pointer(ht->tbl, new_tbl);
 288
 289         list_for_each_entry(walker, &old_tbl->walkers, list)
 290                 walker->tbl = NULL;
 291
 292         /* Wait for readers. All new readers will see the new
 293          * table, and thus no references to the old table will
 294          * remain.
 295          */
 296         call_rcu(&old_tbl->rcu, bucket_table_free_rcu);
 297 }
 298
 299 /**
 300  * rhashtable_expand - Expand hash table while allowing concurrent lookups
 301  * @ht:         the hash table to expand
 302  *
 303  * A secondary bucket array is allocated and the hash entries are migrated.
 304  *
 305  * This function may only be called in a context where it is safe to call
 306  * synchronize_rcu(), e.g. not within a rcu_read_lock() section.
 307  *
 308  * The caller must ensure that no concurrent resizing occurs by holding
 309  * ht->mutex.
 310  *
 311  * It is valid to have concurrent insertions and deletions protected by per
 312  * bucket locks or concurrent RCU protected lookups and traversals.
 313  */
 314 int rhashtable_expand(struct rhashtable *ht)
 315 {
 316         struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);
 317
 318         ASSERT_RHT_MUTEX(ht);
 319
 320         new_tbl = bucket_table_alloc(ht, old_tbl->size * 2);
 321         if (new_tbl == NULL)
 322                 return -ENOMEM;
 323
 324         rhashtable_rehash(ht, new_tbl);
 325         return 0;
 326 }
 327 EXPORT_SYMBOL_GPL(rhashtable_expand);
 328
 329 /**
 330  * rhashtable_shrink - Shrink hash table while allowing concurrent lookups
 331  * @ht:         the hash table to shrink
 332  *
 333  * This function may only be called in a context where it is safe to call
 334  * synchronize_rcu(), e.g. not within a rcu_read_lock() section.
 335  *
 336  * The caller must ensure that no concurrent resizing occurs by holding
 337  * ht->mutex.
 338  *
 339  * The caller must ensure that no concurrent table mutations take place.
 340  * It is however valid to have concurrent lookups if they are RCU protected.
 341  *
 342  * It is valid to have concurrent insertions and deletions protected by per
 343  * bucket locks or concurrent RCU protected lookups and traversals.
 344  */
 345 int rhashtable_shrink(struct rhashtable *ht)
 346 {
 347         struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);
 348
 349         ASSERT_RHT_MUTEX(ht);
 350
 351         new_tbl = bucket_table_alloc(ht, old_tbl->size / 2);
 352         if (new_tbl == NULL)
 353                 return -ENOMEM;
 354
 355         rhashtable_rehash(ht, new_tbl);
 356         return 0;
 357 }
 358 EXPORT_SYMBOL_GPL(rhashtable_shrink);
 359
 360 static void rht_deferred_worker(struct work_struct *work)
 361 {
 362         struct rhashtable *ht;
 363         struct bucket_table *tbl;
 364
 365         ht = container_of(work, struct rhashtable, run_work);
 366         mutex_lock(&ht->mutex);
 367         if (ht->being_destroyed)
 368                 goto unlock;
 369
 370         tbl = rht_dereference(ht->tbl, ht);
 371
 372         if (rht_grow_above_75(ht, tbl))
 373                 rhashtable_expand(ht);
 374         else if (rht_shrink_below_30(ht, tbl))
 375                 rhashtable_shrink(ht);
 376 unlock:
 377         mutex_unlock(&ht->mutex);
 378 }
 379
 380 static bool __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
 381                                 bool (*compare)(void *, void *), void *arg)
 382 {
 383         struct bucket_table *tbl, *old_tbl;
 384         struct rhash_head *head;
 385         bool no_resize_running;
 386         unsigned hash;
 387         bool success = true;
 388
 389         rcu_read_lock();
 390
 391         old_tbl = rht_dereference_rcu(ht->tbl, ht);
 392         hash = head_hashfn(ht, old_tbl, obj);
 393
 394         spin_lock_bh(bucket_lock(old_tbl, hash));
 395
 396         /* Because we have already taken the bucket lock in old_tbl,
 397          * if we find that future_tbl is not yet visible then that
 398          * guarantees all other insertions of the same entry will
 399          * also grab the bucket lock in old_tbl because until the
 400          * rehash completes ht->tbl won't be changed.
 401          */
 402         tbl = rht_dereference_rcu(old_tbl->future_tbl, ht) ?: old_tbl;
 403         if (tbl != old_tbl) {
 404                 hash = head_hashfn(ht, tbl, obj);
 405                 spin_lock_nested(bucket_lock(tbl, hash), SINGLE_DEPTH_NESTING);
 406         }
 407
 408         if (compare &&
 409             rhashtable_lookup_compare(ht, rht_obj(ht, obj) + ht->p.key_offset,
 410                                       compare, arg)) {
 411                 success = false;
 412                 goto exit;
 413         }
 414
 415         no_resize_running = tbl == old_tbl;
 416
 417         head = rht_dereference_bucket(tbl->buckets[hash], tbl, hash);
 418
 419         if (rht_is_a_nulls(head))
 420                 INIT_RHT_NULLS_HEAD(obj->next, ht, hash);
 421         else
 422                 RCU_INIT_POINTER(obj->next, head);
 423
 424         rcu_assign_pointer(tbl->buckets[hash], obj);
 425
 426         atomic_inc(&ht->nelems);
 427         if (no_resize_running && rht_grow_above_75(ht, tbl))
 428                 schedule_work(&ht->run_work);
 429
 430 exit:
 431         if (tbl != old_tbl) {
 432                 hash = head_hashfn(ht, tbl, obj);
 433                 spin_unlock(bucket_lock(tbl, hash));
 434         }
 435
 436         hash = head_hashfn(ht, old_tbl, obj);
 437         spin_unlock_bh(bucket_lock(old_tbl, hash));
 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                    1UL << params->min_shift);
 879 }
 880
 881 /**
 882  * rhashtable_init - initialize a new hash table
 883  * @ht:         hash table to be initialized
 884  * @params:     configuration parameters
 885  *
 886  * Initializes a new hash table based on the provided configuration
 887  * parameters. A table can be configured either with a variable or
 888  * fixed length key:
 889  *
 890  * Configuration Example 1: Fixed length keys
 891  * struct test_obj {
 892  *      int                     key;
 893  *      void *                  my_member;
 894  *      struct rhash_head       node;
 895  * };
 896  *
 897  * struct rhashtable_params params = {
 898  *      .head_offset = offsetof(struct test_obj, node),
 899  *      .key_offset = offsetof(struct test_obj, key),
 900  *      .key_len = sizeof(int),
 901  *      .hashfn = jhash,
 902  *      .nulls_base = (1U << RHT_BASE_SHIFT),
 903  * };
 904  *
 905  * Configuration Example 2: Variable length keys
 906  * struct test_obj {
 907  *      [...]
 908  *      struct rhash_head       node;
 909  * };
 910  *
 911  * u32 my_hash_fn(const void *data, u32 seed)
 912  * {
 913  *      struct test_obj *obj = data;
 914  *
 915  *      return [... hash ...];
 916  * }
 917  *
 918  * struct rhashtable_params params = {
 919  *      .head_offset = offsetof(struct test_obj, node),
 920  *      .hashfn = jhash,
 921  *      .obj_hashfn = my_hash_fn,
 922  * };
 923  */
 924 int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params)
 925 {
 926         struct bucket_table *tbl;
 927         size_t size;
 928
 929         size = HASH_DEFAULT_SIZE;
 930
 931         if ((params->key_len && !params->hashfn) ||
 932             (!params->key_len && !params->obj_hashfn))
 933                 return -EINVAL;
 934
 935         if (params->nulls_base && params->nulls_base < (1U << RHT_BASE_SHIFT))
 936                 return -EINVAL;
 937
 938         params->min_shift = max_t(size_t, params->min_shift,
 939                                   ilog2(HASH_MIN_SIZE));
 940
 941         if (params->nelem_hint)
 942                 size = rounded_hashtable_size(params);
 943
 944         memset(ht, 0, sizeof(*ht));
 945         mutex_init(&ht->mutex);
 946         memcpy(&ht->p, params, sizeof(*params));
 947
 948         if (params->locks_mul)
 949                 ht->p.locks_mul = roundup_pow_of_two(params->locks_mul);
 950         else
 951                 ht->p.locks_mul = BUCKET_LOCKS_PER_CPU;
 952
 953         tbl = bucket_table_alloc(ht, size);
 954         if (tbl == NULL)
 955                 return -ENOMEM;
 956
 957         atomic_set(&ht->nelems, 0);
 958
 959         RCU_INIT_POINTER(ht->tbl, tbl);
 960
 961         INIT_WORK(&ht->run_work, rht_deferred_worker);
 962
 963         return 0;
 964 }
 965 EXPORT_SYMBOL_GPL(rhashtable_init);
 966
 967 /**
 968  * rhashtable_destroy - destroy hash table
 969  * @ht:         the hash table to destroy
 970  *
 971  * Frees the bucket array. This function is not rcu safe, therefore the caller
 972  * has to make sure that no resizing may happen by unpublishing the hashtable
 973  * and waiting for the quiescent cycle before releasing the bucket array.
 974  */
 975 void rhashtable_destroy(struct rhashtable *ht)
 976 {
 977         ht->being_destroyed = true;
 978
 979         cancel_work_sync(&ht->run_work);
 980
 981         mutex_lock(&ht->mutex);
 982         bucket_table_free(rht_dereference(ht->tbl, ht));
 983         mutex_unlock(&ht->mutex);
 984 }
 985 EXPORT_SYMBOL_GPL(rhashtable_destroy);