lib/rhashtable.c

   1 /*
   2  * Resizable, Scalable, Concurrent Hash Table
   3  *
   4  * Copyright (c) 2014 Thomas Graf <tgraf@suug.ch>
   5  * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
   6  *
   7  * Based on the following paper:
   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/slab.h>
  21 #include <linux/vmalloc.h>
  22 #include <linux/mm.h>
  23 #include <linux/hash.h>
  24 #include <linux/random.h>
  25 #include <linux/rhashtable.h>
  26
  27 #define HASH_DEFAULT_SIZE       64UL
  28 #define HASH_MIN_SIZE           4UL
  29
  30 #define ASSERT_RHT_MUTEX(HT) BUG_ON(!lockdep_rht_mutex_is_held(HT))
  31
  32 #ifdef CONFIG_PROVE_LOCKING
  33 int lockdep_rht_mutex_is_held(const struct rhashtable *ht)
  34 {
  35         return ht->p.mutex_is_held();
  36 }
  37 EXPORT_SYMBOL_GPL(lockdep_rht_mutex_is_held);
  38 #endif
  39
  40 static void *rht_obj(const struct rhashtable *ht, const struct rhash_head *he)
  41 {
  42         return (void *) he - ht->p.head_offset;
  43 }
  44
  45 static u32 __hashfn(const struct rhashtable *ht, const void *key,
  46                       u32 len, u32 hsize)
  47 {
  48         u32 h;
  49
  50         h = ht->p.hashfn(key, len, ht->p.hash_rnd);
  51
  52         return h & (hsize - 1);
  53 }
  54
  55 /**
  56  * rhashtable_hashfn - compute hash for key of given length
  57  * @ht:         hash table to compute for
  58  * @key:        pointer to key
  59  * @len:        length of key
  60  *
  61  * Computes the hash value using the hash function provided in the 'hashfn'
  62  * of struct rhashtable_params. The returned value is guaranteed to be
  63  * smaller than the number of buckets in the hash table.
  64  *
  65  * The caller must ensure that no concurrent table mutations occur.
  66  */
  67 u32 rhashtable_hashfn(const struct rhashtable *ht, const void *key, u32 len)
  68 {
  69         struct bucket_table *tbl = rht_dereference_rcu(ht->tbl, ht);
  70
  71         return __hashfn(ht, key, len, tbl->size);
  72 }
  73 EXPORT_SYMBOL_GPL(rhashtable_hashfn);
  74
  75 static u32 obj_hashfn(const struct rhashtable *ht, const void *ptr, u32 hsize)
  76 {
  77         if (unlikely(!ht->p.key_len)) {
  78                 u32 h;
  79
  80                 h = ht->p.obj_hashfn(ptr, ht->p.hash_rnd);
  81
  82                 return h & (hsize - 1);
  83         }
  84
  85         return __hashfn(ht, ptr + ht->p.key_offset, ht->p.key_len, hsize);
  86 }
  87
  88 /**
  89  * rhashtable_obj_hashfn - compute hash for hashed object
  90  * @ht:         hash table to compute for
  91  * @ptr:        pointer to hashed object
  92  *
  93  * Computes the hash value using the hash function `hashfn` respectively
  94  * 'obj_hashfn' depending on whether the hash table is set up to work with
  95  * a fixed length key. The returned value is guaranteed to be smaller than
  96  * the number of buckets in the hash table.
  97  *
  98  * The caller must ensure that no concurrent table mutations occur.
  99  */
 100 u32 rhashtable_obj_hashfn(const struct rhashtable *ht, void *ptr)
 101 {
 102         struct bucket_table *tbl = rht_dereference_rcu(ht->tbl, ht);
 103
 104         return obj_hashfn(ht, ptr, tbl->size);
 105 }
 106 EXPORT_SYMBOL_GPL(rhashtable_obj_hashfn);
 107
 108 static u32 head_hashfn(const struct rhashtable *ht,
 109                        const struct rhash_head *he, u32 hsize)
 110 {
 111         return obj_hashfn(ht, rht_obj(ht, he), hsize);
 112 }
 113
 114 static struct bucket_table *bucket_table_alloc(size_t nbuckets, gfp_t flags)
 115 {
 116         struct bucket_table *tbl;
 117         size_t size;
 118
 119         size = sizeof(*tbl) + nbuckets * sizeof(tbl->buckets[0]);
 120         tbl = kzalloc(size, flags);
 121         if (tbl == NULL)
 122                 tbl = vzalloc(size);
 123
 124         if (tbl == NULL)
 125                 return NULL;
 126
 127         tbl->size = nbuckets;
 128
 129         return tbl;
 130 }
 131
 132 static void bucket_table_free(const struct bucket_table *tbl)
 133 {
 134         kvfree(tbl);
 135 }
 136
 137 /**
 138  * rht_grow_above_75 - returns true if nelems > 0.75 * table-size
 139  * @ht:         hash table
 140  * @new_size:   new table size
 141  */
 142 bool rht_grow_above_75(const struct rhashtable *ht, size_t new_size)
 143 {
 144         /* Expand table when exceeding 75% load */
 145         return ht->nelems > (new_size / 4 * 3);
 146 }
 147 EXPORT_SYMBOL_GPL(rht_grow_above_75);
 148
 149 /**
 150  * rht_shrink_below_30 - returns true if nelems < 0.3 * table-size
 151  * @ht:         hash table
 152  * @new_size:   new table size
 153  */
 154 bool rht_shrink_below_30(const struct rhashtable *ht, size_t new_size)
 155 {
 156         /* Shrink table beneath 30% load */
 157         return ht->nelems < (new_size * 3 / 10);
 158 }
 159 EXPORT_SYMBOL_GPL(rht_shrink_below_30);
 160
 161 static void hashtable_chain_unzip(const struct rhashtable *ht,
 162                                   const struct bucket_table *new_tbl,
 163                                   struct bucket_table *old_tbl, size_t n)
 164 {
 165         struct rhash_head *he, *p, *next;
 166         unsigned int h;
 167
 168         /* Old bucket empty, no work needed. */
 169         p = rht_dereference(old_tbl->buckets[n], ht);
 170         if (!p)
 171                 return;
 172
 173         /* Advance the old bucket pointer one or more times until it
 174          * reaches a node that doesn't hash to the same bucket as the
 175          * previous node p. Call the previous node p;
 176          */
 177         h = head_hashfn(ht, p, new_tbl->size);
 178         rht_for_each(he, p->next, ht) {
 179                 if (head_hashfn(ht, he, new_tbl->size) != h)
 180                         break;
 181                 p = he;
 182         }
 183         RCU_INIT_POINTER(old_tbl->buckets[n], p->next);
 184
 185         /* Find the subsequent node which does hash to the same
 186          * bucket as node P, or NULL if no such node exists.
 187          */
 188         next = NULL;
 189         if (he) {
 190                 rht_for_each(he, he->next, ht) {
 191                         if (head_hashfn(ht, he, new_tbl->size) == h) {
 192                                 next = he;
 193                                 break;
 194                         }
 195                 }
 196         }
 197
 198         /* Set p's next pointer to that subsequent node pointer,
 199          * bypassing the nodes which do not hash to p's bucket
 200          */
 201         RCU_INIT_POINTER(p->next, next);
 202 }
 203
 204 /**
 205  * rhashtable_expand - Expand hash table while allowing concurrent lookups
 206  * @ht:         the hash table to expand
 207  * @flags:      allocation flags
 208  *
 209  * A secondary bucket array is allocated and the hash entries are migrated
 210  * while keeping them on both lists until the end of the RCU grace period.
 211  *
 212  * This function may only be called in a context where it is safe to call
 213  * synchronize_rcu(), e.g. not within a rcu_read_lock() section.
 214  *
 215  * The caller must ensure that no concurrent table mutations take place.
 216  * It is however valid to have concurrent lookups if they are RCU protected.
 217  */
 218 int rhashtable_expand(struct rhashtable *ht, gfp_t flags)
 219 {
 220         struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);
 221         struct rhash_head *he;
 222         unsigned int i, h;
 223         bool complete;
 224
 225         ASSERT_RHT_MUTEX(ht);
 226
 227         if (ht->p.max_shift && ht->shift >= ht->p.max_shift)
 228                 return 0;
 229
 230         new_tbl = bucket_table_alloc(old_tbl->size * 2, flags);
 231         if (new_tbl == NULL)
 232                 return -ENOMEM;
 233
 234         ht->shift++;
 235
 236         /* For each new bucket, search the corresponding old bucket
 237          * for the first entry that hashes to the new bucket, and
 238          * link the new bucket to that entry. Since all the entries
 239          * which will end up in the new bucket appear in the same
 240          * old bucket, this constructs an entirely valid new hash
 241          * table, but with multiple buckets "zipped" together into a
 242          * single imprecise chain.
 243          */
 244         for (i = 0; i < new_tbl->size; i++) {
 245                 h = i & (old_tbl->size - 1);
 246                 rht_for_each(he, old_tbl->buckets[h], ht) {
 247                         if (head_hashfn(ht, he, new_tbl->size) == i) {
 248                                 RCU_INIT_POINTER(new_tbl->buckets[i], he);
 249                                 break;
 250                         }
 251                 }
 252         }
 253
 254         /* Publish the new table pointer. Lookups may now traverse
 255          * the new table, but they will not benefit from any
 256          * additional efficiency until later steps unzip the buckets.
 257          */
 258         rcu_assign_pointer(ht->tbl, new_tbl);
 259
 260         /* Unzip interleaved hash chains */
 261         do {
 262                 /* Wait for readers. All new readers will see the new
 263                  * table, and thus no references to the old table will
 264                  * remain.
 265                  */
 266                 synchronize_rcu();
 267
 268                 /* For each bucket in the old table (each of which
 269                  * contains items from multiple buckets of the new
 270                  * table): ...
 271                  */
 272                 complete = true;
 273                 for (i = 0; i < old_tbl->size; i++) {
 274                         hashtable_chain_unzip(ht, new_tbl, old_tbl, i);
 275                         if (old_tbl->buckets[i] != NULL)
 276                                 complete = false;
 277                 }
 278         } while (!complete);
 279
 280         bucket_table_free(old_tbl);
 281         return 0;
 282 }
 283 EXPORT_SYMBOL_GPL(rhashtable_expand);
 284
 285 /**
 286  * rhashtable_shrink - Shrink hash table while allowing concurrent lookups
 287  * @ht:         the hash table to shrink
 288  * @flags:      allocation flags
 289  *
 290  * This function may only be called in a context where it is safe to call
 291  * synchronize_rcu(), e.g. not within a rcu_read_lock() section.
 292  *
 293  * The caller must ensure that no concurrent table mutations take place.
 294  * It is however valid to have concurrent lookups if they are RCU protected.
 295  */
 296 int rhashtable_shrink(struct rhashtable *ht, gfp_t flags)
 297 {
 298         struct bucket_table *ntbl, *tbl = rht_dereference(ht->tbl, ht);
 299         struct rhash_head __rcu **pprev;
 300         unsigned int i;
 301
 302         ASSERT_RHT_MUTEX(ht);
 303
 304         if (ht->shift <= ht->p.min_shift)
 305                 return 0;
 306
 307         ntbl = bucket_table_alloc(tbl->size / 2, flags);
 308         if (ntbl == NULL)
 309                 return -ENOMEM;
 310
 311         ht->shift--;
 312
 313         /* Link each bucket in the new table to the first bucket
 314          * in the old table that contains entries which will hash
 315          * to the new bucket.
 316          */
 317         for (i = 0; i < ntbl->size; i++) {
 318                 ntbl->buckets[i] = tbl->buckets[i];
 319
 320                 /* Link each bucket in the new table to the first bucket
 321                  * in the old table that contains entries which will hash
 322                  * to the new bucket.
 323                  */
 324                 for (pprev = &ntbl->buckets[i]; *pprev != NULL;
 325                      pprev = &rht_dereference(*pprev, ht)->next)
 326                         ;
 327                 RCU_INIT_POINTER(*pprev, tbl->buckets[i + ntbl->size]);
 328         }
 329
 330         /* Publish the new, valid hash table */
 331         rcu_assign_pointer(ht->tbl, ntbl);
 332
 333         /* Wait for readers. No new readers will have references to the
 334          * old hash table.
 335          */
 336         synchronize_rcu();
 337
 338         bucket_table_free(tbl);
 339
 340         return 0;
 341 }
 342 EXPORT_SYMBOL_GPL(rhashtable_shrink);
 343
 344 /**
 345  * rhashtable_insert - insert object into hash hash table
 346  * @ht:         hash table
 347  * @obj:        pointer to hash head inside object
 348  * @flags:      allocation flags (table expansion)
 349  *
 350  * Will automatically grow the table via rhashtable_expand() if the the
 351  * grow_decision function specified at rhashtable_init() returns true.
 352  *
 353  * The caller must ensure that no concurrent table mutations occur. It is
 354  * however valid to have concurrent lookups if they are RCU protected.
 355  */
 356 void rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
 357                        gfp_t flags)
 358 {
 359         struct bucket_table *tbl = rht_dereference(ht->tbl, ht);
 360         u32 hash;
 361
 362         ASSERT_RHT_MUTEX(ht);
 363
 364         hash = head_hashfn(ht, obj, tbl->size);
 365         RCU_INIT_POINTER(obj->next, tbl->buckets[hash]);
 366         rcu_assign_pointer(tbl->buckets[hash], obj);
 367         ht->nelems++;
 368
 369         if (ht->p.grow_decision && ht->p.grow_decision(ht, tbl->size))
 370                 rhashtable_expand(ht, flags);
 371 }
 372 EXPORT_SYMBOL_GPL(rhashtable_insert);
 373
 374 /**
 375  * rhashtable_remove_pprev - remove object from hash table given previous element
 376  * @ht:         hash table
 377  * @obj:        pointer to hash head inside object
 378  * @pprev:      pointer to previous element
 379  * @flags:      allocation flags (table expansion)
 380  *
 381  * Identical to rhashtable_remove() but caller is alreayd aware of the element
 382  * in front of the element to be deleted. This is in particular useful for
 383  * deletion when combined with walking or lookup.
 384  */
 385 void rhashtable_remove_pprev(struct rhashtable *ht, struct rhash_head *obj,
 386                              struct rhash_head __rcu **pprev, gfp_t flags)
 387 {
 388         struct bucket_table *tbl = rht_dereference(ht->tbl, ht);
 389
 390         ASSERT_RHT_MUTEX(ht);
 391
 392         RCU_INIT_POINTER(*pprev, obj->next);
 393         ht->nelems--;
 394
 395         if (ht->p.shrink_decision &&
 396             ht->p.shrink_decision(ht, tbl->size))
 397                 rhashtable_shrink(ht, flags);
 398 }
 399 EXPORT_SYMBOL_GPL(rhashtable_remove_pprev);
 400
 401 /**
 402  * rhashtable_remove - remove object from hash table
 403  * @ht:         hash table
 404  * @obj:        pointer to hash head inside object
 405  * @flags:      allocation flags (table expansion)
 406  *
 407  * Since the hash chain is single linked, the removal operation needs to
 408  * walk the bucket chain upon removal. The removal operation is thus
 409  * considerable slow if the hash table is not correctly sized.
 410  *
 411  * Will automatically shrink the table via rhashtable_expand() if the the
 412  * shrink_decision function specified at rhashtable_init() returns true.
 413  *
 414  * The caller must ensure that no concurrent table mutations occur. It is
 415  * however valid to have concurrent lookups if they are RCU protected.
 416  */
 417 bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *obj,
 418                        gfp_t flags)
 419 {
 420         struct bucket_table *tbl = rht_dereference(ht->tbl, ht);
 421         struct rhash_head __rcu **pprev;
 422         struct rhash_head *he;
 423         u32 h;
 424
 425         ASSERT_RHT_MUTEX(ht);
 426
 427         h = head_hashfn(ht, obj, tbl->size);
 428
 429         pprev = &tbl->buckets[h];
 430         rht_for_each(he, tbl->buckets[h], ht) {
 431                 if (he != obj) {
 432                         pprev = &he->next;
 433                         continue;
 434                 }
 435
 436                 rhashtable_remove_pprev(ht, he, pprev, flags);
 437                 return true;
 438         }
 439
 440         return false;
 441 }
 442 EXPORT_SYMBOL_GPL(rhashtable_remove);
 443
 444 /**
 445  * rhashtable_lookup - lookup key in hash table
 446  * @ht:         hash table
 447  * @key:        pointer to key
 448  *
 449  * Computes the hash value for the key and traverses the bucket chain looking
 450  * for a entry with an identical key. The first matching entry is returned.
 451  *
 452  * This lookup function may only be used for fixed key hash table (key_len
 453  * paramter set). It will BUG() if used inappropriately.
 454  *
 455  * Lookups may occur in parallel with hash mutations as long as the lookup is
 456  * guarded by rcu_read_lock(). The caller must take care of this.
 457  */
 458 void *rhashtable_lookup(const struct rhashtable *ht, const void *key)
 459 {
 460         const struct bucket_table *tbl = rht_dereference_rcu(ht->tbl, ht);
 461         struct rhash_head *he;
 462         u32 h;
 463
 464         BUG_ON(!ht->p.key_len);
 465
 466         h = __hashfn(ht, key, ht->p.key_len, tbl->size);
 467         rht_for_each_rcu(he, tbl->buckets[h], ht) {
 468                 if (memcmp(rht_obj(ht, he) + ht->p.key_offset, key,
 469                            ht->p.key_len))
 470                         continue;
 471                 return (void *) he - ht->p.head_offset;
 472         }
 473
 474         return NULL;
 475 }
 476 EXPORT_SYMBOL_GPL(rhashtable_lookup);
 477
 478 /**
 479  * rhashtable_lookup_compare - search hash table with compare function
 480  * @ht:         hash table
 481  * @key:        pointer to key
 482  * @compare:    compare function, must return true on match
 483  * @arg:        argument passed on to compare function
 484  *
 485  * Traverses the bucket chain behind the provided hash value and calls the
 486  * specified compare function for each entry.
 487  *
 488  * Lookups may occur in parallel with hash mutations as long as the lookup is
 489  * guarded by rcu_read_lock(). The caller must take care of this.
 490  *
 491  * Returns the first entry on which the compare function returned true.
 492  */
 493 void *rhashtable_lookup_compare(const struct rhashtable *ht, void *key,
 494                                 bool (*compare)(void *, void *), void *arg)
 495 {
 496         const struct bucket_table *tbl = rht_dereference_rcu(ht->tbl, ht);
 497         struct rhash_head *he;
 498         u32 hash;
 499
 500         hash = __hashfn(ht, key, ht->p.key_len, tbl->size);
 501
 502         rht_for_each_rcu(he, tbl->buckets[hash], ht) {
 503                 if (!compare(rht_obj(ht, he), arg))
 504                         continue;
 505                 return (void *) he - ht->p.head_offset;
 506         }
 507
 508         return NULL;
 509 }
 510 EXPORT_SYMBOL_GPL(rhashtable_lookup_compare);
 511
 512 static size_t rounded_hashtable_size(struct rhashtable_params *params)
 513 {
 514         return max(roundup_pow_of_two(params->nelem_hint * 4 / 3),
 515                    1UL << params->min_shift);
 516 }
 517
 518 /**
 519  * rhashtable_init - initialize a new hash table
 520  * @ht:         hash table to be initialized
 521  * @params:     configuration parameters
 522  *
 523  * Initializes a new hash table based on the provided configuration
 524  * parameters. A table can be configured either with a variable or
 525  * fixed length key:
 526  *
 527  * Configuration Example 1: Fixed length keys
 528  * struct test_obj {
 529  *      int                     key;
 530  *      void *                  my_member;
 531  *      struct rhash_head       node;
 532  * };
 533  *
 534  * struct rhashtable_params params = {
 535  *      .head_offset = offsetof(struct test_obj, node),
 536  *      .key_offset = offsetof(struct test_obj, key),
 537  *      .key_len = sizeof(int),
 538  *      .hashfn = arch_fast_hash,
 539  *      .mutex_is_held = &my_mutex_is_held,
 540  * };
 541  *
 542  * Configuration Example 2: Variable length keys
 543  * struct test_obj {
 544  *      [...]
 545  *      struct rhash_head       node;
 546  * };
 547  *
 548  * u32 my_hash_fn(const void *data, u32 seed)
 549  * {
 550  *      struct test_obj *obj = data;
 551  *
 552  *      return [... hash ...];
 553  * }
 554  *
 555  * struct rhashtable_params params = {
 556  *      .head_offset = offsetof(struct test_obj, node),
 557  *      .hashfn = arch_fast_hash,
 558  *      .obj_hashfn = my_hash_fn,
 559  *      .mutex_is_held = &my_mutex_is_held,
 560  * };
 561  */
 562 int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params)
 563 {
 564         struct bucket_table *tbl;
 565         size_t size;
 566
 567         size = HASH_DEFAULT_SIZE;
 568
 569         if ((params->key_len && !params->hashfn) ||
 570             (!params->key_len && !params->obj_hashfn))
 571                 return -EINVAL;
 572
 573         params->min_shift = max_t(size_t, params->min_shift,
 574                                   ilog2(HASH_MIN_SIZE));
 575
 576         if (params->nelem_hint)
 577                 size = rounded_hashtable_size(params);
 578
 579         tbl = bucket_table_alloc(size, GFP_KERNEL);
 580         if (tbl == NULL)
 581                 return -ENOMEM;
 582
 583         memset(ht, 0, sizeof(*ht));
 584         ht->shift = ilog2(tbl->size);
 585         memcpy(&ht->p, params, sizeof(*params));
 586         RCU_INIT_POINTER(ht->tbl, tbl);
 587
 588         if (!ht->p.hash_rnd)
 589                 get_random_bytes(&ht->p.hash_rnd, sizeof(ht->p.hash_rnd));
 590
 591         return 0;
 592 }
 593 EXPORT_SYMBOL_GPL(rhashtable_init);
 594
 595 /**
 596  * rhashtable_destroy - destroy hash table
 597  * @ht:         the hash table to destroy
 598  *
 599  * Frees the bucket array. This function is not rcu safe, therefore the caller
 600  * has to make sure that no resizing may happen by unpublishing the hashtable
 601  * and waiting for the quiescent cycle before releasing the bucket array.
 602  */
 603 void rhashtable_destroy(const struct rhashtable *ht)
 604 {
 605         bucket_table_free(ht->tbl);
 606 }
 607 EXPORT_SYMBOL_GPL(rhashtable_destroy);
 608
 609 /**************************************************************************
 610  * Self Test
 611  **************************************************************************/
 612
 613 #ifdef CONFIG_TEST_RHASHTABLE
 614
 615 #define TEST_HT_SIZE    8
 616 #define TEST_ENTRIES    2048
 617 #define TEST_PTR        ((void *) 0xdeadbeef)
 618 #define TEST_NEXPANDS   4
 619
 620 static int test_mutex_is_held(void)
 621 {
 622         return 1;
 623 }
 624
 625 struct test_obj {
 626         void                    *ptr;
 627         int                     value;
 628         struct rhash_head       node;
 629 };
 630
 631 static int __init test_rht_lookup(struct rhashtable *ht)
 632 {
 633         unsigned int i;
 634
 635         for (i = 0; i < TEST_ENTRIES * 2; i++) {
 636                 struct test_obj *obj;
 637                 bool expected = !(i % 2);
 638                 u32 key = i;
 639
 640                 obj = rhashtable_lookup(ht, &key);
 641
 642                 if (expected && !obj) {
 643                         pr_warn("Test failed: Could not find key %u\n", key);
 644                         return -ENOENT;
 645                 } else if (!expected && obj) {
 646                         pr_warn("Test failed: Unexpected entry found for key %u\n",
 647                                 key);
 648                         return -EEXIST;
 649                 } else if (expected && obj) {
 650                         if (obj->ptr != TEST_PTR || obj->value != i) {
 651                                 pr_warn("Test failed: Lookup value mismatch %p!=%p, %u!=%u\n",
 652                                         obj->ptr, TEST_PTR, obj->value, i);
 653                                 return -EINVAL;
 654                         }
 655                 }
 656         }
 657
 658         return 0;
 659 }
 660
 661 static void test_bucket_stats(struct rhashtable *ht,
 662                                      struct bucket_table *tbl,
 663                                      bool quiet)
 664 {
 665         unsigned int cnt, i, total = 0;
 666         struct test_obj *obj;
 667
 668         for (i = 0; i < tbl->size; i++) {
 669                 cnt = 0;
 670
 671                 if (!quiet)
 672                         pr_info(" [%#4x/%zu]", i, tbl->size);
 673
 674                 rht_for_each_entry_rcu(obj, tbl->buckets[i], node) {
 675                         cnt++;
 676                         total++;
 677                         if (!quiet)
 678                                 pr_cont(" [%p],", obj);
 679                 }
 680
 681                 if (!quiet)
 682                         pr_cont("\n  [%#x] first element: %p, chain length: %u\n",
 683                                 i, tbl->buckets[i], cnt);
 684         }
 685
 686         pr_info("  Traversal complete: counted=%u, nelems=%zu, entries=%d\n",
 687                 total, ht->nelems, TEST_ENTRIES);
 688 }
 689
 690 static int __init test_rhashtable(struct rhashtable *ht)
 691 {
 692         struct bucket_table *tbl;
 693         struct test_obj *obj, *next;
 694         int err;
 695         unsigned int i;
 696
 697         /*
 698          * Insertion Test:
 699          * Insert TEST_ENTRIES into table with all keys even numbers
 700          */
 701         pr_info("  Adding %d keys\n", TEST_ENTRIES);
 702         for (i = 0; i < TEST_ENTRIES; i++) {
 703                 struct test_obj *obj;
 704
 705                 obj = kzalloc(sizeof(*obj), GFP_KERNEL);
 706                 if (!obj) {
 707                         err = -ENOMEM;
 708                         goto error;
 709                 }
 710
 711                 obj->ptr = TEST_PTR;
 712                 obj->value = i * 2;
 713
 714                 rhashtable_insert(ht, &obj->node, GFP_KERNEL);
 715         }
 716
 717         rcu_read_lock();
 718         tbl = rht_dereference_rcu(ht->tbl, ht);
 719         test_bucket_stats(ht, tbl, true);
 720         test_rht_lookup(ht);
 721         rcu_read_unlock();
 722
 723         for (i = 0; i < TEST_NEXPANDS; i++) {
 724                 pr_info("  Table expansion iteration %u...\n", i);
 725                 rhashtable_expand(ht, GFP_KERNEL);
 726
 727                 rcu_read_lock();
 728                 pr_info("  Verifying lookups...\n");
 729                 test_rht_lookup(ht);
 730                 rcu_read_unlock();
 731         }
 732
 733         for (i = 0; i < TEST_NEXPANDS; i++) {
 734                 pr_info("  Table shrinkage iteration %u...\n", i);
 735                 rhashtable_shrink(ht, GFP_KERNEL);
 736
 737                 rcu_read_lock();
 738                 pr_info("  Verifying lookups...\n");
 739                 test_rht_lookup(ht);
 740                 rcu_read_unlock();
 741         }
 742
 743         pr_info("  Deleting %d keys\n", TEST_ENTRIES);
 744         for (i = 0; i < TEST_ENTRIES; i++) {
 745                 u32 key = i * 2;
 746
 747                 obj = rhashtable_lookup(ht, &key);
 748                 BUG_ON(!obj);
 749
 750                 rhashtable_remove(ht, &obj->node, GFP_KERNEL);
 751                 kfree(obj);
 752         }
 753
 754         return 0;
 755
 756 error:
 757         tbl = rht_dereference_rcu(ht->tbl, ht);
 758         for (i = 0; i < tbl->size; i++)
 759                 rht_for_each_entry_safe(obj, next, tbl->buckets[i], ht, node)
 760                         kfree(obj);
 761
 762         return err;
 763 }
 764
 765 static int __init test_rht_init(void)
 766 {
 767         struct rhashtable ht;
 768         struct rhashtable_params params = {
 769                 .nelem_hint = TEST_HT_SIZE,
 770                 .head_offset = offsetof(struct test_obj, node),
 771                 .key_offset = offsetof(struct test_obj, value),
 772                 .key_len = sizeof(int),
 773                 .hashfn = arch_fast_hash,
 774                 .mutex_is_held = &test_mutex_is_held,
 775                 .grow_decision = rht_grow_above_75,
 776                 .shrink_decision = rht_shrink_below_30,
 777         };
 778         int err;
 779
 780         pr_info("Running resizable hashtable tests...\n");
 781
 782         err = rhashtable_init(&ht, &params);
 783         if (err < 0) {
 784                 pr_warn("Test failed: Unable to initialize hashtable: %d\n",
 785                         err);
 786                 return err;
 787         }
 788
 789         err = test_rhashtable(&ht);
 790
 791         rhashtable_destroy(&ht);
 792
 793         return err;
 794 }
 795
 796 subsys_initcall(test_rht_init);
 797
 798 #endif /* CONFIG_TEST_RHASHTABLE */