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