blob: c7654b6f5f64e9ba6eb7c49770b456067f0ccd3f [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
233 * for the first entry that hashes to the new bucket, and
234 * 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
251 * the new table, but they will not benefit from any
252 * additional efficiency until later steps unzip the buckets.
253 */
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
309 /* Link each bucket in the new table to the first bucket
310 * 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
316 /* Link each bucket in the new table to the first bucket
317 * 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,
Herbert Xu1b2f3092014-11-13 18:11:20 +0800535 * #ifdef CONFIG_PROVE_LOCKING
Thomas Graf7e1e7762014-08-02 11:47:44 +0200536 * .mutex_is_held = &my_mutex_is_held,
Herbert Xu1b2f3092014-11-13 18:11:20 +0800537 * #endif
Thomas Graf7e1e7762014-08-02 11:47:44 +0200538 * };
539 *
540 * Configuration Example 2: Variable length keys
541 * struct test_obj {
542 * [...]
543 * struct rhash_head node;
544 * };
545 *
546 * u32 my_hash_fn(const void *data, u32 seed)
547 * {
548 * struct test_obj *obj = data;
549 *
550 * return [... hash ...];
551 * }
552 *
553 * struct rhashtable_params params = {
554 * .head_offset = offsetof(struct test_obj, node),
555 * .hashfn = arch_fast_hash,
556 * .obj_hashfn = my_hash_fn,
Herbert Xu1b2f3092014-11-13 18:11:20 +0800557 * #ifdef CONFIG_PROVE_LOCKING
Thomas Graf7e1e7762014-08-02 11:47:44 +0200558 * .mutex_is_held = &my_mutex_is_held,
Herbert Xu1b2f3092014-11-13 18:11:20 +0800559 * #endif
Thomas Graf7e1e7762014-08-02 11:47:44 +0200560 * };
561 */
562int 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
Ying Xue94000172014-09-03 09:22:36 +0800573 params->min_shift = max_t(size_t, params->min_shift,
574 ilog2(HASH_MIN_SIZE));
575
Thomas Graf7e1e7762014-08-02 11:47:44 +0200576 if (params->nelem_hint)
Ying Xue94000172014-09-03 09:22:36 +0800577 size = rounded_hashtable_size(params);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200578
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}
593EXPORT_SYMBOL_GPL(rhashtable_init);
594
595/**
596 * rhashtable_destroy - destroy hash table
597 * @ht: the hash table to destroy
598 *
Pablo Neira Ayusoae82ddc2014-09-02 00:26:05 +0200599 * 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.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200602 */
603void rhashtable_destroy(const struct rhashtable *ht)
604{
Pablo Neira Ayusoae82ddc2014-09-02 00:26:05 +0200605 bucket_table_free(ht->tbl);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200606}
607EXPORT_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
Herbert Xu1b2f3092014-11-13 18:11:20 +0800620#ifdef CONFIG_PROVE_LOCKING
Thomas Graf7e1e7762014-08-02 11:47:44 +0200621static int test_mutex_is_held(void)
622{
623 return 1;
624}
Herbert Xu1b2f3092014-11-13 18:11:20 +0800625#endif
Thomas Graf7e1e7762014-08-02 11:47:44 +0200626
627struct test_obj {
628 void *ptr;
629 int value;
630 struct rhash_head node;
631};
632
633static int __init test_rht_lookup(struct rhashtable *ht)
634{
635 unsigned int i;
636
637 for (i = 0; i < TEST_ENTRIES * 2; i++) {
638 struct test_obj *obj;
639 bool expected = !(i % 2);
640 u32 key = i;
641
642 obj = rhashtable_lookup(ht, &key);
643
644 if (expected && !obj) {
645 pr_warn("Test failed: Could not find key %u\n", key);
646 return -ENOENT;
647 } else if (!expected && obj) {
648 pr_warn("Test failed: Unexpected entry found for key %u\n",
649 key);
650 return -EEXIST;
651 } else if (expected && obj) {
652 if (obj->ptr != TEST_PTR || obj->value != i) {
653 pr_warn("Test failed: Lookup value mismatch %p!=%p, %u!=%u\n",
654 obj->ptr, TEST_PTR, obj->value, i);
655 return -EINVAL;
656 }
657 }
658 }
659
660 return 0;
661}
662
663static void test_bucket_stats(struct rhashtable *ht,
664 struct bucket_table *tbl,
665 bool quiet)
666{
667 unsigned int cnt, i, total = 0;
668 struct test_obj *obj;
669
670 for (i = 0; i < tbl->size; i++) {
671 cnt = 0;
672
673 if (!quiet)
674 pr_info(" [%#4x/%zu]", i, tbl->size);
675
676 rht_for_each_entry_rcu(obj, tbl->buckets[i], node) {
677 cnt++;
678 total++;
679 if (!quiet)
680 pr_cont(" [%p],", obj);
681 }
682
683 if (!quiet)
684 pr_cont("\n [%#x] first element: %p, chain length: %u\n",
685 i, tbl->buckets[i], cnt);
686 }
687
688 pr_info(" Traversal complete: counted=%u, nelems=%zu, entries=%d\n",
689 total, ht->nelems, TEST_ENTRIES);
690}
691
692static int __init test_rhashtable(struct rhashtable *ht)
693{
694 struct bucket_table *tbl;
695 struct test_obj *obj, *next;
696 int err;
697 unsigned int i;
698
699 /*
700 * Insertion Test:
701 * Insert TEST_ENTRIES into table with all keys even numbers
702 */
703 pr_info(" Adding %d keys\n", TEST_ENTRIES);
704 for (i = 0; i < TEST_ENTRIES; i++) {
705 struct test_obj *obj;
706
707 obj = kzalloc(sizeof(*obj), GFP_KERNEL);
708 if (!obj) {
709 err = -ENOMEM;
710 goto error;
711 }
712
713 obj->ptr = TEST_PTR;
714 obj->value = i * 2;
715
716 rhashtable_insert(ht, &obj->node, GFP_KERNEL);
717 }
718
719 rcu_read_lock();
720 tbl = rht_dereference_rcu(ht->tbl, ht);
721 test_bucket_stats(ht, tbl, true);
722 test_rht_lookup(ht);
723 rcu_read_unlock();
724
725 for (i = 0; i < TEST_NEXPANDS; i++) {
726 pr_info(" Table expansion iteration %u...\n", i);
727 rhashtable_expand(ht, GFP_KERNEL);
728
729 rcu_read_lock();
730 pr_info(" Verifying lookups...\n");
731 test_rht_lookup(ht);
732 rcu_read_unlock();
733 }
734
735 for (i = 0; i < TEST_NEXPANDS; i++) {
736 pr_info(" Table shrinkage iteration %u...\n", i);
737 rhashtable_shrink(ht, GFP_KERNEL);
738
739 rcu_read_lock();
740 pr_info(" Verifying lookups...\n");
741 test_rht_lookup(ht);
742 rcu_read_unlock();
743 }
744
745 pr_info(" Deleting %d keys\n", TEST_ENTRIES);
746 for (i = 0; i < TEST_ENTRIES; i++) {
747 u32 key = i * 2;
748
749 obj = rhashtable_lookup(ht, &key);
750 BUG_ON(!obj);
751
752 rhashtable_remove(ht, &obj->node, GFP_KERNEL);
753 kfree(obj);
754 }
755
756 return 0;
757
758error:
759 tbl = rht_dereference_rcu(ht->tbl, ht);
760 for (i = 0; i < tbl->size; i++)
761 rht_for_each_entry_safe(obj, next, tbl->buckets[i], ht, node)
762 kfree(obj);
763
764 return err;
765}
766
767static int __init test_rht_init(void)
768{
769 struct rhashtable ht;
770 struct rhashtable_params params = {
771 .nelem_hint = TEST_HT_SIZE,
772 .head_offset = offsetof(struct test_obj, node),
773 .key_offset = offsetof(struct test_obj, value),
774 .key_len = sizeof(int),
775 .hashfn = arch_fast_hash,
Herbert Xu1b2f3092014-11-13 18:11:20 +0800776#ifdef CONFIG_PROVE_LOCKING
Thomas Graf7e1e7762014-08-02 11:47:44 +0200777 .mutex_is_held = &test_mutex_is_held,
Herbert Xu1b2f3092014-11-13 18:11:20 +0800778#endif
Thomas Graf7e1e7762014-08-02 11:47:44 +0200779 .grow_decision = rht_grow_above_75,
780 .shrink_decision = rht_shrink_below_30,
781 };
782 int err;
783
784 pr_info("Running resizable hashtable tests...\n");
785
786 err = rhashtable_init(&ht, &params);
787 if (err < 0) {
788 pr_warn("Test failed: Unable to initialize hashtable: %d\n",
789 err);
790 return err;
791 }
792
793 err = test_rhashtable(&ht);
794
795 rhashtable_destroy(&ht);
796
797 return err;
798}
799
800subsys_initcall(test_rht_init);
801
802#endif /* CONFIG_TEST_RHASHTABLE */