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