blob: 7fb474b18f1b8d7168315e2eb688c57aef4a2ecb [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>
Daniel Borkmann87545892014-12-10 16:33:11 +010023#include <linux/jhash.h>
Thomas Graf7e1e7762014-08-02 11:47:44 +020024#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
Thomas Graf97defe12015-01-02 23:00:20 +010029#define BUCKET_LOCKS_PER_CPU 128UL
30
Thomas Graff89bd6f2015-01-02 23:00:21 +010031/* Base bits plus 1 bit for nulls marker */
32#define HASH_RESERVED_SPACE (RHT_BASE_BITS + 1)
33
Thomas Graf97defe12015-01-02 23:00:20 +010034enum {
35 RHT_LOCK_NORMAL,
36 RHT_LOCK_NESTED,
37 RHT_LOCK_NESTED2,
38};
39
40/* The bucket lock is selected based on the hash and protects mutations
41 * on a group of hash buckets.
42 *
43 * IMPORTANT: When holding the bucket lock of both the old and new table
44 * during expansions and shrinking, the old bucket lock must always be
45 * acquired first.
46 */
47static spinlock_t *bucket_lock(const struct bucket_table *tbl, u32 hash)
48{
49 return &tbl->locks[hash & tbl->locks_mask];
50}
Thomas Graf7e1e7762014-08-02 11:47:44 +020051
52#define ASSERT_RHT_MUTEX(HT) BUG_ON(!lockdep_rht_mutex_is_held(HT))
Thomas Graf97defe12015-01-02 23:00:20 +010053#define ASSERT_BUCKET_LOCK(TBL, HASH) \
54 BUG_ON(!lockdep_rht_bucket_is_held(TBL, HASH))
Thomas Graf7e1e7762014-08-02 11:47:44 +020055
56#ifdef CONFIG_PROVE_LOCKING
Thomas Graf97defe12015-01-02 23:00:20 +010057int lockdep_rht_mutex_is_held(struct rhashtable *ht)
Thomas Graf7e1e7762014-08-02 11:47:44 +020058{
Thomas Graf97defe12015-01-02 23:00:20 +010059 return (debug_locks) ? lockdep_is_held(&ht->mutex) : 1;
Thomas Graf7e1e7762014-08-02 11:47:44 +020060}
61EXPORT_SYMBOL_GPL(lockdep_rht_mutex_is_held);
Thomas Graf88d6ed12015-01-02 23:00:16 +010062
63int lockdep_rht_bucket_is_held(const struct bucket_table *tbl, u32 hash)
64{
Thomas Graf97defe12015-01-02 23:00:20 +010065 spinlock_t *lock = bucket_lock(tbl, hash);
66
67 return (debug_locks) ? lockdep_is_held(lock) : 1;
Thomas Graf88d6ed12015-01-02 23:00:16 +010068}
69EXPORT_SYMBOL_GPL(lockdep_rht_bucket_is_held);
Thomas Graf7e1e7762014-08-02 11:47:44 +020070#endif
71
Thomas Grafc91eee52014-08-13 16:38:30 +020072static void *rht_obj(const struct rhashtable *ht, const struct rhash_head *he)
Thomas Graf7e1e7762014-08-02 11:47:44 +020073{
74 return (void *) he - ht->p.head_offset;
75}
Thomas Graf7e1e7762014-08-02 11:47:44 +020076
Thomas Graf8d24c0b2015-01-02 23:00:14 +010077static u32 rht_bucket_index(const struct bucket_table *tbl, u32 hash)
Thomas Graf7e1e7762014-08-02 11:47:44 +020078{
Thomas Graf8d24c0b2015-01-02 23:00:14 +010079 return hash & (tbl->size - 1);
Thomas Graf7e1e7762014-08-02 11:47:44 +020080}
81
Thomas Graf8d24c0b2015-01-02 23:00:14 +010082static u32 obj_raw_hashfn(const struct rhashtable *ht, const void *ptr)
83{
84 u32 hash;
85
86 if (unlikely(!ht->p.key_len))
87 hash = ht->p.obj_hashfn(ptr, ht->p.hash_rnd);
88 else
89 hash = ht->p.hashfn(ptr + ht->p.key_offset, ht->p.key_len,
90 ht->p.hash_rnd);
91
Thomas Graff89bd6f2015-01-02 23:00:21 +010092 return hash >> HASH_RESERVED_SPACE;
Thomas Graf8d24c0b2015-01-02 23:00:14 +010093}
94
Thomas Graf97defe12015-01-02 23:00:20 +010095static u32 key_hashfn(struct rhashtable *ht, const void *key, u32 len)
Thomas Graf7e1e7762014-08-02 11:47:44 +020096{
97 struct bucket_table *tbl = rht_dereference_rcu(ht->tbl, ht);
Thomas Graf8d24c0b2015-01-02 23:00:14 +010098 u32 hash;
Thomas Graf7e1e7762014-08-02 11:47:44 +020099
Thomas Graf8d24c0b2015-01-02 23:00:14 +0100100 hash = ht->p.hashfn(key, len, ht->p.hash_rnd);
Thomas Graff89bd6f2015-01-02 23:00:21 +0100101 hash >>= HASH_RESERVED_SPACE;
Thomas Graf8d24c0b2015-01-02 23:00:14 +0100102
103 return rht_bucket_index(tbl, hash);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200104}
Thomas Graf7e1e7762014-08-02 11:47:44 +0200105
106static u32 head_hashfn(const struct rhashtable *ht,
Thomas Graf8d24c0b2015-01-02 23:00:14 +0100107 const struct bucket_table *tbl,
108 const struct rhash_head *he)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200109{
Thomas Graf8d24c0b2015-01-02 23:00:14 +0100110 return rht_bucket_index(tbl, obj_raw_hashfn(ht, rht_obj(ht, he)));
Thomas Graf7e1e7762014-08-02 11:47:44 +0200111}
112
Thomas Grafb8e19432015-01-02 23:00:17 +0100113static struct rhash_head __rcu **bucket_tail(struct bucket_table *tbl, u32 n)
114{
115 struct rhash_head __rcu **pprev;
116
117 for (pprev = &tbl->buckets[n];
Thomas Graff89bd6f2015-01-02 23:00:21 +0100118 !rht_is_a_nulls(rht_dereference_bucket(*pprev, tbl, n));
Thomas Grafb8e19432015-01-02 23:00:17 +0100119 pprev = &rht_dereference_bucket(*pprev, tbl, n)->next)
120 ;
121
122 return pprev;
123}
124
Thomas Graf97defe12015-01-02 23:00:20 +0100125static int alloc_bucket_locks(struct rhashtable *ht, struct bucket_table *tbl)
126{
127 unsigned int i, size;
128#if defined(CONFIG_PROVE_LOCKING)
129 unsigned int nr_pcpus = 2;
130#else
131 unsigned int nr_pcpus = num_possible_cpus();
132#endif
133
134 nr_pcpus = min_t(unsigned int, nr_pcpus, 32UL);
135 size = roundup_pow_of_two(nr_pcpus * ht->p.locks_mul);
136
137 /* Never allocate more than one lock per bucket */
138 size = min_t(unsigned int, size, tbl->size);
139
140 if (sizeof(spinlock_t) != 0) {
141#ifdef CONFIG_NUMA
142 if (size * sizeof(spinlock_t) > PAGE_SIZE)
143 tbl->locks = vmalloc(size * sizeof(spinlock_t));
144 else
145#endif
146 tbl->locks = kmalloc_array(size, sizeof(spinlock_t),
147 GFP_KERNEL);
148 if (!tbl->locks)
149 return -ENOMEM;
150 for (i = 0; i < size; i++)
151 spin_lock_init(&tbl->locks[i]);
152 }
153 tbl->locks_mask = size - 1;
154
155 return 0;
156}
157
158static void bucket_table_free(const struct bucket_table *tbl)
159{
160 if (tbl)
161 kvfree(tbl->locks);
162
163 kvfree(tbl);
164}
165
166static struct bucket_table *bucket_table_alloc(struct rhashtable *ht,
167 size_t nbuckets)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200168{
169 struct bucket_table *tbl;
170 size_t size;
Thomas Graff89bd6f2015-01-02 23:00:21 +0100171 int i;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200172
173 size = sizeof(*tbl) + nbuckets * sizeof(tbl->buckets[0]);
Thomas Graf6eba8222014-11-13 13:45:46 +0100174 tbl = kzalloc(size, GFP_KERNEL | __GFP_NOWARN);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200175 if (tbl == NULL)
176 tbl = vzalloc(size);
177
178 if (tbl == NULL)
179 return NULL;
180
181 tbl->size = nbuckets;
182
Thomas Graf97defe12015-01-02 23:00:20 +0100183 if (alloc_bucket_locks(ht, tbl) < 0) {
184 bucket_table_free(tbl);
185 return NULL;
186 }
Thomas Graf7e1e7762014-08-02 11:47:44 +0200187
Thomas Graff89bd6f2015-01-02 23:00:21 +0100188 for (i = 0; i < nbuckets; i++)
189 INIT_RHT_NULLS_HEAD(tbl->buckets[i], ht, i);
190
Thomas Graf97defe12015-01-02 23:00:20 +0100191 return tbl;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200192}
193
194/**
195 * rht_grow_above_75 - returns true if nelems > 0.75 * table-size
196 * @ht: hash table
197 * @new_size: new table size
198 */
199bool rht_grow_above_75(const struct rhashtable *ht, size_t new_size)
200{
201 /* Expand table when exceeding 75% load */
Ying Xuec0c09bf2015-01-07 13:41:56 +0800202 return atomic_read(&ht->nelems) > (new_size / 4 * 3) &&
203 (ht->p.max_shift && atomic_read(&ht->shift) < ht->p.max_shift);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200204}
205EXPORT_SYMBOL_GPL(rht_grow_above_75);
206
207/**
208 * rht_shrink_below_30 - returns true if nelems < 0.3 * table-size
209 * @ht: hash table
210 * @new_size: new table size
211 */
212bool rht_shrink_below_30(const struct rhashtable *ht, size_t new_size)
213{
214 /* Shrink table beneath 30% load */
Ying Xuec0c09bf2015-01-07 13:41:56 +0800215 return atomic_read(&ht->nelems) < (new_size * 3 / 10) &&
216 (atomic_read(&ht->shift) > ht->p.min_shift);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200217}
218EXPORT_SYMBOL_GPL(rht_shrink_below_30);
219
220static void hashtable_chain_unzip(const struct rhashtable *ht,
221 const struct bucket_table *new_tbl,
Thomas Graf97defe12015-01-02 23:00:20 +0100222 struct bucket_table *old_tbl,
223 size_t old_hash)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200224{
225 struct rhash_head *he, *p, *next;
Thomas Graf97defe12015-01-02 23:00:20 +0100226 spinlock_t *new_bucket_lock, *new_bucket_lock2 = NULL;
227 unsigned int new_hash, new_hash2;
228
229 ASSERT_BUCKET_LOCK(old_tbl, old_hash);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200230
231 /* Old bucket empty, no work needed. */
Thomas Graf97defe12015-01-02 23:00:20 +0100232 p = rht_dereference_bucket(old_tbl->buckets[old_hash], old_tbl,
233 old_hash);
Thomas Graff89bd6f2015-01-02 23:00:21 +0100234 if (rht_is_a_nulls(p))
Thomas Graf7e1e7762014-08-02 11:47:44 +0200235 return;
236
Thomas Graf97defe12015-01-02 23:00:20 +0100237 new_hash = new_hash2 = head_hashfn(ht, new_tbl, p);
238 new_bucket_lock = bucket_lock(new_tbl, new_hash);
239
Thomas Graf7e1e7762014-08-02 11:47:44 +0200240 /* Advance the old bucket pointer one or more times until it
241 * reaches a node that doesn't hash to the same bucket as the
242 * previous node p. Call the previous node p;
243 */
Thomas Graf97defe12015-01-02 23:00:20 +0100244 rht_for_each_continue(he, p->next, old_tbl, old_hash) {
245 new_hash2 = head_hashfn(ht, new_tbl, he);
246 if (new_hash != new_hash2)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200247 break;
248 p = he;
249 }
Thomas Graf97defe12015-01-02 23:00:20 +0100250 rcu_assign_pointer(old_tbl->buckets[old_hash], p->next);
251
252 spin_lock_bh_nested(new_bucket_lock, RHT_LOCK_NESTED);
253
254 /* If we have encountered an entry that maps to a different bucket in
255 * the new table, lock down that bucket as well as we might cut off
256 * the end of the chain.
257 */
258 new_bucket_lock2 = bucket_lock(new_tbl, new_hash);
259 if (new_bucket_lock != new_bucket_lock2)
260 spin_lock_bh_nested(new_bucket_lock2, RHT_LOCK_NESTED2);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200261
262 /* Find the subsequent node which does hash to the same
263 * bucket as node P, or NULL if no such node exists.
264 */
Thomas Graff89bd6f2015-01-02 23:00:21 +0100265 INIT_RHT_NULLS_HEAD(next, ht, old_hash);
266 if (!rht_is_a_nulls(he)) {
Thomas Graf97defe12015-01-02 23:00:20 +0100267 rht_for_each_continue(he, he->next, old_tbl, old_hash) {
268 if (head_hashfn(ht, new_tbl, he) == new_hash) {
Thomas Graf7e1e7762014-08-02 11:47:44 +0200269 next = he;
270 break;
271 }
272 }
273 }
274
275 /* Set p's next pointer to that subsequent node pointer,
276 * bypassing the nodes which do not hash to p's bucket
277 */
Thomas Graf97defe12015-01-02 23:00:20 +0100278 rcu_assign_pointer(p->next, next);
279
280 if (new_bucket_lock != new_bucket_lock2)
281 spin_unlock_bh(new_bucket_lock2);
282 spin_unlock_bh(new_bucket_lock);
283}
284
285static void link_old_to_new(struct bucket_table *new_tbl,
286 unsigned int new_hash, struct rhash_head *entry)
287{
288 spinlock_t *new_bucket_lock;
289
290 new_bucket_lock = bucket_lock(new_tbl, new_hash);
291
292 spin_lock_bh_nested(new_bucket_lock, RHT_LOCK_NESTED);
293 rcu_assign_pointer(*bucket_tail(new_tbl, new_hash), entry);
294 spin_unlock_bh(new_bucket_lock);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200295}
296
297/**
298 * rhashtable_expand - Expand hash table while allowing concurrent lookups
299 * @ht: the hash table to expand
Thomas Graf7e1e7762014-08-02 11:47:44 +0200300 *
301 * A secondary bucket array is allocated and the hash entries are migrated
302 * while keeping them on both lists until the end of the RCU grace period.
303 *
304 * This function may only be called in a context where it is safe to call
305 * synchronize_rcu(), e.g. not within a rcu_read_lock() section.
306 *
Thomas Graf97defe12015-01-02 23:00:20 +0100307 * The caller must ensure that no concurrent resizing occurs by holding
308 * ht->mutex.
309 *
310 * It is valid to have concurrent insertions and deletions protected by per
311 * bucket locks or concurrent RCU protected lookups and traversals.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200312 */
Thomas Graf6eba8222014-11-13 13:45:46 +0100313int rhashtable_expand(struct rhashtable *ht)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200314{
315 struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);
316 struct rhash_head *he;
Thomas Graf97defe12015-01-02 23:00:20 +0100317 spinlock_t *old_bucket_lock;
318 unsigned int new_hash, old_hash;
319 bool complete = false;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200320
321 ASSERT_RHT_MUTEX(ht);
322
Thomas Graf97defe12015-01-02 23:00:20 +0100323 new_tbl = bucket_table_alloc(ht, old_tbl->size * 2);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200324 if (new_tbl == NULL)
325 return -ENOMEM;
326
Ying Xuec0c09bf2015-01-07 13:41:56 +0800327 atomic_inc(&ht->shift);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200328
Thomas Graf97defe12015-01-02 23:00:20 +0100329 /* Make insertions go into the new, empty table right away. Deletions
330 * and lookups will be attempted in both tables until we synchronize.
331 * The synchronize_rcu() guarantees for the new table to be picked up
332 * so no new additions go into the old table while we relink.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200333 */
Thomas Graf97defe12015-01-02 23:00:20 +0100334 rcu_assign_pointer(ht->future_tbl, new_tbl);
335 synchronize_rcu();
336
337 /* For each new bucket, search the corresponding old bucket for the
338 * first entry that hashes to the new bucket, and link the end of
339 * newly formed bucket chain (containing entries added to future
340 * table) to that entry. Since all the entries which will end up in
341 * the new bucket appear in the same old bucket, this constructs an
342 * entirely valid new hash table, but with multiple buckets
343 * "zipped" together into a single imprecise chain.
344 */
345 for (new_hash = 0; new_hash < new_tbl->size; new_hash++) {
346 old_hash = rht_bucket_index(old_tbl, new_hash);
347 old_bucket_lock = bucket_lock(old_tbl, old_hash);
348
349 spin_lock_bh(old_bucket_lock);
350 rht_for_each(he, old_tbl, old_hash) {
351 if (head_hashfn(ht, new_tbl, he) == new_hash) {
352 link_old_to_new(new_tbl, new_hash, he);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200353 break;
354 }
355 }
Thomas Graf97defe12015-01-02 23:00:20 +0100356 spin_unlock_bh(old_bucket_lock);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200357 }
358
359 /* Publish the new table pointer. Lookups may now traverse
Herbert Xu0c828f22014-11-13 13:10:48 +0800360 * the new table, but they will not benefit from any
361 * additional efficiency until later steps unzip the buckets.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200362 */
363 rcu_assign_pointer(ht->tbl, new_tbl);
364
365 /* Unzip interleaved hash chains */
Thomas Graf97defe12015-01-02 23:00:20 +0100366 while (!complete && !ht->being_destroyed) {
Thomas Graf7e1e7762014-08-02 11:47:44 +0200367 /* Wait for readers. All new readers will see the new
368 * table, and thus no references to the old table will
369 * remain.
370 */
371 synchronize_rcu();
372
373 /* For each bucket in the old table (each of which
374 * contains items from multiple buckets of the new
375 * table): ...
376 */
377 complete = true;
Thomas Graf97defe12015-01-02 23:00:20 +0100378 for (old_hash = 0; old_hash < old_tbl->size; old_hash++) {
Thomas Graff89bd6f2015-01-02 23:00:21 +0100379 struct rhash_head *head;
380
Thomas Graf97defe12015-01-02 23:00:20 +0100381 old_bucket_lock = bucket_lock(old_tbl, old_hash);
382 spin_lock_bh(old_bucket_lock);
383
384 hashtable_chain_unzip(ht, new_tbl, old_tbl, old_hash);
Thomas Graff89bd6f2015-01-02 23:00:21 +0100385 head = rht_dereference_bucket(old_tbl->buckets[old_hash],
386 old_tbl, old_hash);
387 if (!rht_is_a_nulls(head))
Thomas Graf7e1e7762014-08-02 11:47:44 +0200388 complete = false;
Thomas Graf97defe12015-01-02 23:00:20 +0100389
390 spin_unlock_bh(old_bucket_lock);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200391 }
Thomas Graf97defe12015-01-02 23:00:20 +0100392 }
Thomas Graf7e1e7762014-08-02 11:47:44 +0200393
394 bucket_table_free(old_tbl);
395 return 0;
396}
397EXPORT_SYMBOL_GPL(rhashtable_expand);
398
399/**
400 * rhashtable_shrink - Shrink hash table while allowing concurrent lookups
401 * @ht: the hash table to shrink
Thomas Graf7e1e7762014-08-02 11:47:44 +0200402 *
403 * This function may only be called in a context where it is safe to call
404 * synchronize_rcu(), e.g. not within a rcu_read_lock() section.
405 *
Thomas Graf97defe12015-01-02 23:00:20 +0100406 * The caller must ensure that no concurrent resizing occurs by holding
407 * ht->mutex.
408 *
Thomas Graf7e1e7762014-08-02 11:47:44 +0200409 * The caller must ensure that no concurrent table mutations take place.
410 * It is however valid to have concurrent lookups if they are RCU protected.
Thomas Graf97defe12015-01-02 23:00:20 +0100411 *
412 * It is valid to have concurrent insertions and deletions protected by per
413 * bucket locks or concurrent RCU protected lookups and traversals.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200414 */
Thomas Graf6eba8222014-11-13 13:45:46 +0100415int rhashtable_shrink(struct rhashtable *ht)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200416{
Thomas Graf97defe12015-01-02 23:00:20 +0100417 struct bucket_table *new_tbl, *tbl = rht_dereference(ht->tbl, ht);
418 spinlock_t *new_bucket_lock, *old_bucket_lock1, *old_bucket_lock2;
419 unsigned int new_hash;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200420
421 ASSERT_RHT_MUTEX(ht);
422
Thomas Graf97defe12015-01-02 23:00:20 +0100423 new_tbl = bucket_table_alloc(ht, tbl->size / 2);
424 if (new_tbl == NULL)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200425 return -ENOMEM;
426
Thomas Graf97defe12015-01-02 23:00:20 +0100427 rcu_assign_pointer(ht->future_tbl, new_tbl);
428 synchronize_rcu();
Thomas Graf7e1e7762014-08-02 11:47:44 +0200429
Thomas Graf97defe12015-01-02 23:00:20 +0100430 /* Link the first entry in the old bucket to the end of the
431 * bucket in the new table. As entries are concurrently being
432 * added to the new table, lock down the new bucket. As we
433 * always divide the size in half when shrinking, each bucket
434 * in the new table maps to exactly two buckets in the old
435 * table.
436 *
437 * As removals can occur concurrently on the old table, we need
438 * to lock down both matching buckets in the old table.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200439 */
Thomas Graf97defe12015-01-02 23:00:20 +0100440 for (new_hash = 0; new_hash < new_tbl->size; new_hash++) {
441 old_bucket_lock1 = bucket_lock(tbl, new_hash);
442 old_bucket_lock2 = bucket_lock(tbl, new_hash + new_tbl->size);
443 new_bucket_lock = bucket_lock(new_tbl, new_hash);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200444
Thomas Graf97defe12015-01-02 23:00:20 +0100445 spin_lock_bh(old_bucket_lock1);
446 spin_lock_bh_nested(old_bucket_lock2, RHT_LOCK_NESTED);
447 spin_lock_bh_nested(new_bucket_lock, RHT_LOCK_NESTED2);
448
449 rcu_assign_pointer(*bucket_tail(new_tbl, new_hash),
450 tbl->buckets[new_hash]);
451 rcu_assign_pointer(*bucket_tail(new_tbl, new_hash),
452 tbl->buckets[new_hash + new_tbl->size]);
453
454 spin_unlock_bh(new_bucket_lock);
455 spin_unlock_bh(old_bucket_lock2);
456 spin_unlock_bh(old_bucket_lock1);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200457 }
458
459 /* Publish the new, valid hash table */
Thomas Graf97defe12015-01-02 23:00:20 +0100460 rcu_assign_pointer(ht->tbl, new_tbl);
Ying Xuec0c09bf2015-01-07 13:41:56 +0800461 atomic_dec(&ht->shift);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200462
463 /* Wait for readers. No new readers will have references to the
464 * old hash table.
465 */
466 synchronize_rcu();
467
468 bucket_table_free(tbl);
469
470 return 0;
471}
472EXPORT_SYMBOL_GPL(rhashtable_shrink);
473
Thomas Graf97defe12015-01-02 23:00:20 +0100474static void rht_deferred_worker(struct work_struct *work)
475{
476 struct rhashtable *ht;
477 struct bucket_table *tbl;
478
479 ht = container_of(work, struct rhashtable, run_work.work);
480 mutex_lock(&ht->mutex);
481 tbl = rht_dereference(ht->tbl, ht);
482
483 if (ht->p.grow_decision && ht->p.grow_decision(ht, tbl->size))
484 rhashtable_expand(ht);
485 else if (ht->p.shrink_decision && ht->p.shrink_decision(ht, tbl->size))
486 rhashtable_shrink(ht);
487
488 mutex_unlock(&ht->mutex);
489}
490
Ying Xue54c5b7d2015-01-07 13:41:53 +0800491static void rhashtable_wakeup_worker(struct rhashtable *ht)
492{
493 struct bucket_table *tbl = rht_dereference_rcu(ht->tbl, ht);
494 struct bucket_table *new_tbl = rht_dereference_rcu(ht->future_tbl, ht);
495 size_t size = tbl->size;
496
497 /* Only adjust the table if no resizing is currently in progress. */
498 if (tbl == new_tbl &&
499 ((ht->p.grow_decision && ht->p.grow_decision(ht, size)) ||
500 (ht->p.shrink_decision && ht->p.shrink_decision(ht, size))))
501 schedule_delayed_work(&ht->run_work, 0);
502}
503
Ying Xuedb304852015-01-07 13:41:54 +0800504static void __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
505 struct bucket_table *tbl, u32 hash)
506{
507 struct rhash_head *head = rht_dereference_bucket(tbl->buckets[hash],
508 tbl, hash);
509
510 if (rht_is_a_nulls(head))
511 INIT_RHT_NULLS_HEAD(obj->next, ht, hash);
512 else
513 RCU_INIT_POINTER(obj->next, head);
514
515 rcu_assign_pointer(tbl->buckets[hash], obj);
516
517 atomic_inc(&ht->nelems);
518
519 rhashtable_wakeup_worker(ht);
520}
521
Thomas Graf7e1e7762014-08-02 11:47:44 +0200522/**
Ying Xuedb304852015-01-07 13:41:54 +0800523 * rhashtable_insert - insert object into hash table
Thomas Graf7e1e7762014-08-02 11:47:44 +0200524 * @ht: hash table
525 * @obj: pointer to hash head inside object
Thomas Graf7e1e7762014-08-02 11:47:44 +0200526 *
Thomas Graf97defe12015-01-02 23:00:20 +0100527 * Will take a per bucket spinlock to protect against mutual mutations
528 * on the same bucket. Multiple insertions may occur in parallel unless
529 * they map to the same bucket lock.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200530 *
Thomas Graf97defe12015-01-02 23:00:20 +0100531 * It is safe to call this function from atomic context.
532 *
533 * Will trigger an automatic deferred table resizing if the size grows
534 * beyond the watermark indicated by grow_decision() which can be passed
535 * to rhashtable_init().
Thomas Graf7e1e7762014-08-02 11:47:44 +0200536 */
Thomas Graf6eba8222014-11-13 13:45:46 +0100537void rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200538{
Thomas Graf97defe12015-01-02 23:00:20 +0100539 struct bucket_table *tbl;
540 spinlock_t *lock;
541 unsigned hash;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200542
Thomas Graf97defe12015-01-02 23:00:20 +0100543 rcu_read_lock();
Thomas Graf7e1e7762014-08-02 11:47:44 +0200544
Thomas Graf97defe12015-01-02 23:00:20 +0100545 tbl = rht_dereference_rcu(ht->future_tbl, ht);
Thomas Graf8d24c0b2015-01-02 23:00:14 +0100546 hash = head_hashfn(ht, tbl, obj);
Thomas Graf97defe12015-01-02 23:00:20 +0100547 lock = bucket_lock(tbl, hash);
548
549 spin_lock_bh(lock);
Ying Xuedb304852015-01-07 13:41:54 +0800550 __rhashtable_insert(ht, obj, tbl, hash);
Thomas Graf97defe12015-01-02 23:00:20 +0100551 spin_unlock_bh(lock);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200552
Thomas Graf97defe12015-01-02 23:00:20 +0100553 rcu_read_unlock();
Thomas Graf7e1e7762014-08-02 11:47:44 +0200554}
555EXPORT_SYMBOL_GPL(rhashtable_insert);
556
557/**
Thomas Graf7e1e7762014-08-02 11:47:44 +0200558 * rhashtable_remove - remove object from hash table
559 * @ht: hash table
560 * @obj: pointer to hash head inside object
Thomas Graf7e1e7762014-08-02 11:47:44 +0200561 *
562 * Since the hash chain is single linked, the removal operation needs to
563 * walk the bucket chain upon removal. The removal operation is thus
564 * considerable slow if the hash table is not correctly sized.
565 *
Ying Xuedb304852015-01-07 13:41:54 +0800566 * Will automatically shrink the table via rhashtable_expand() if the
Thomas Graf7e1e7762014-08-02 11:47:44 +0200567 * shrink_decision function specified at rhashtable_init() returns true.
568 *
569 * The caller must ensure that no concurrent table mutations occur. It is
570 * however valid to have concurrent lookups if they are RCU protected.
571 */
Thomas Graf6eba8222014-11-13 13:45:46 +0100572bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *obj)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200573{
Thomas Graf97defe12015-01-02 23:00:20 +0100574 struct bucket_table *tbl;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200575 struct rhash_head __rcu **pprev;
576 struct rhash_head *he;
Thomas Graf97defe12015-01-02 23:00:20 +0100577 spinlock_t *lock;
578 unsigned int hash;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200579
Thomas Graf97defe12015-01-02 23:00:20 +0100580 rcu_read_lock();
581 tbl = rht_dereference_rcu(ht->tbl, ht);
582 hash = head_hashfn(ht, tbl, obj);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200583
Thomas Graf97defe12015-01-02 23:00:20 +0100584 lock = bucket_lock(tbl, hash);
585 spin_lock_bh(lock);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200586
Thomas Graf97defe12015-01-02 23:00:20 +0100587restart:
588 pprev = &tbl->buckets[hash];
589 rht_for_each(he, tbl, hash) {
Thomas Graf7e1e7762014-08-02 11:47:44 +0200590 if (he != obj) {
591 pprev = &he->next;
592 continue;
593 }
594
Thomas Graf97defe12015-01-02 23:00:20 +0100595 rcu_assign_pointer(*pprev, obj->next);
596 atomic_dec(&ht->nelems);
Thomas Graf897362e2015-01-02 23:00:18 +0100597
Thomas Graf97defe12015-01-02 23:00:20 +0100598 spin_unlock_bh(lock);
599
Ying Xue54c5b7d2015-01-07 13:41:53 +0800600 rhashtable_wakeup_worker(ht);
Thomas Graf97defe12015-01-02 23:00:20 +0100601
602 rcu_read_unlock();
Thomas Graf897362e2015-01-02 23:00:18 +0100603
Thomas Graf7e1e7762014-08-02 11:47:44 +0200604 return true;
605 }
606
Ying Xuebd6d4db2015-01-07 13:41:55 +0800607 if (tbl != rht_dereference_rcu(ht->future_tbl, ht)) {
Thomas Graf97defe12015-01-02 23:00:20 +0100608 spin_unlock_bh(lock);
609
Ying Xuebd6d4db2015-01-07 13:41:55 +0800610 tbl = rht_dereference_rcu(ht->future_tbl, ht);
Thomas Graf97defe12015-01-02 23:00:20 +0100611 hash = head_hashfn(ht, tbl, obj);
612
613 lock = bucket_lock(tbl, hash);
614 spin_lock_bh(lock);
615 goto restart;
616 }
617
618 spin_unlock_bh(lock);
619 rcu_read_unlock();
620
Thomas Graf7e1e7762014-08-02 11:47:44 +0200621 return false;
622}
623EXPORT_SYMBOL_GPL(rhashtable_remove);
624
Ying Xueefb975a62015-01-07 13:41:52 +0800625struct rhashtable_compare_arg {
626 struct rhashtable *ht;
627 const void *key;
628};
629
630static bool rhashtable_compare(void *ptr, void *arg)
631{
632 struct rhashtable_compare_arg *x = arg;
633 struct rhashtable *ht = x->ht;
634
635 return !memcmp(ptr + ht->p.key_offset, x->key, ht->p.key_len);
636}
637
Thomas Graf7e1e7762014-08-02 11:47:44 +0200638/**
639 * rhashtable_lookup - lookup key in hash table
640 * @ht: hash table
641 * @key: pointer to key
642 *
643 * Computes the hash value for the key and traverses the bucket chain looking
644 * for a entry with an identical key. The first matching entry is returned.
645 *
646 * This lookup function may only be used for fixed key hash table (key_len
Ying Xuedb304852015-01-07 13:41:54 +0800647 * parameter set). It will BUG() if used inappropriately.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200648 *
Thomas Graf97defe12015-01-02 23:00:20 +0100649 * Lookups may occur in parallel with hashtable mutations and resizing.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200650 */
Thomas Graf97defe12015-01-02 23:00:20 +0100651void *rhashtable_lookup(struct rhashtable *ht, const void *key)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200652{
Ying Xueefb975a62015-01-07 13:41:52 +0800653 struct rhashtable_compare_arg arg = {
654 .ht = ht,
655 .key = key,
656 };
Thomas Graf7e1e7762014-08-02 11:47:44 +0200657
658 BUG_ON(!ht->p.key_len);
659
Ying Xueefb975a62015-01-07 13:41:52 +0800660 return rhashtable_lookup_compare(ht, key, &rhashtable_compare, &arg);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200661}
662EXPORT_SYMBOL_GPL(rhashtable_lookup);
663
664/**
665 * rhashtable_lookup_compare - search hash table with compare function
666 * @ht: hash table
Thomas Graf8d24c0b2015-01-02 23:00:14 +0100667 * @key: the pointer to the key
Thomas Graf7e1e7762014-08-02 11:47:44 +0200668 * @compare: compare function, must return true on match
669 * @arg: argument passed on to compare function
670 *
671 * Traverses the bucket chain behind the provided hash value and calls the
672 * specified compare function for each entry.
673 *
Thomas Graf97defe12015-01-02 23:00:20 +0100674 * Lookups may occur in parallel with hashtable mutations and resizing.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200675 *
676 * Returns the first entry on which the compare function returned true.
677 */
Thomas Graf97defe12015-01-02 23:00:20 +0100678void *rhashtable_lookup_compare(struct rhashtable *ht, const void *key,
Thomas Graf7e1e7762014-08-02 11:47:44 +0200679 bool (*compare)(void *, void *), void *arg)
680{
Thomas Graf97defe12015-01-02 23:00:20 +0100681 const struct bucket_table *tbl, *old_tbl;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200682 struct rhash_head *he;
Thomas Graf8d24c0b2015-01-02 23:00:14 +0100683 u32 hash;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200684
Thomas Graf97defe12015-01-02 23:00:20 +0100685 rcu_read_lock();
686
687 old_tbl = rht_dereference_rcu(ht->tbl, ht);
688 tbl = rht_dereference_rcu(ht->future_tbl, ht);
Thomas Graf8d24c0b2015-01-02 23:00:14 +0100689 hash = key_hashfn(ht, key, ht->p.key_len);
Thomas Graf97defe12015-01-02 23:00:20 +0100690restart:
691 rht_for_each_rcu(he, tbl, rht_bucket_index(tbl, hash)) {
Thomas Graf7e1e7762014-08-02 11:47:44 +0200692 if (!compare(rht_obj(ht, he), arg))
693 continue;
Thomas Graf97defe12015-01-02 23:00:20 +0100694 rcu_read_unlock();
Thomas Grafa4b18cd2015-01-02 23:00:15 +0100695 return rht_obj(ht, he);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200696 }
697
Thomas Graf97defe12015-01-02 23:00:20 +0100698 if (unlikely(tbl != old_tbl)) {
699 tbl = old_tbl;
700 goto restart;
701 }
702 rcu_read_unlock();
703
Thomas Graf7e1e7762014-08-02 11:47:44 +0200704 return NULL;
705}
706EXPORT_SYMBOL_GPL(rhashtable_lookup_compare);
707
Ying Xuedb304852015-01-07 13:41:54 +0800708/**
709 * rhashtable_lookup_insert - lookup and insert object into hash table
710 * @ht: hash table
711 * @obj: pointer to hash head inside object
712 *
713 * Locks down the bucket chain in both the old and new table if a resize
714 * is in progress to ensure that writers can't remove from the old table
715 * and can't insert to the new table during the atomic operation of search
716 * and insertion. Searches for duplicates in both the old and new table if
717 * a resize is in progress.
718 *
719 * This lookup function may only be used for fixed key hash table (key_len
720 * parameter set). It will BUG() if used inappropriately.
721 *
722 * It is safe to call this function from atomic context.
723 *
724 * Will trigger an automatic deferred table resizing if the size grows
725 * beyond the watermark indicated by grow_decision() which can be passed
726 * to rhashtable_init().
727 */
728bool rhashtable_lookup_insert(struct rhashtable *ht, struct rhash_head *obj)
729{
730 struct bucket_table *new_tbl, *old_tbl;
731 spinlock_t *new_bucket_lock, *old_bucket_lock;
732 u32 new_hash, old_hash;
733 bool success = true;
734
735 BUG_ON(!ht->p.key_len);
736
737 rcu_read_lock();
738
739 old_tbl = rht_dereference_rcu(ht->tbl, ht);
740 old_hash = head_hashfn(ht, old_tbl, obj);
741 old_bucket_lock = bucket_lock(old_tbl, old_hash);
742 spin_lock_bh(old_bucket_lock);
743
744 new_tbl = rht_dereference_rcu(ht->future_tbl, ht);
745 new_hash = head_hashfn(ht, new_tbl, obj);
746 new_bucket_lock = bucket_lock(new_tbl, new_hash);
747 if (unlikely(old_tbl != new_tbl))
748 spin_lock_bh_nested(new_bucket_lock, RHT_LOCK_NESTED);
749
750 if (rhashtable_lookup(ht, rht_obj(ht, obj) + ht->p.key_offset)) {
751 success = false;
752 goto exit;
753 }
754
755 __rhashtable_insert(ht, obj, new_tbl, new_hash);
756
757exit:
758 if (unlikely(old_tbl != new_tbl))
759 spin_unlock_bh(new_bucket_lock);
760 spin_unlock_bh(old_bucket_lock);
761
762 rcu_read_unlock();
763
764 return success;
765}
766EXPORT_SYMBOL_GPL(rhashtable_lookup_insert);
767
Ying Xue94000172014-09-03 09:22:36 +0800768static size_t rounded_hashtable_size(struct rhashtable_params *params)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200769{
Ying Xue94000172014-09-03 09:22:36 +0800770 return max(roundup_pow_of_two(params->nelem_hint * 4 / 3),
771 1UL << params->min_shift);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200772}
773
774/**
775 * rhashtable_init - initialize a new hash table
776 * @ht: hash table to be initialized
777 * @params: configuration parameters
778 *
779 * Initializes a new hash table based on the provided configuration
780 * parameters. A table can be configured either with a variable or
781 * fixed length key:
782 *
783 * Configuration Example 1: Fixed length keys
784 * struct test_obj {
785 * int key;
786 * void * my_member;
787 * struct rhash_head node;
788 * };
789 *
790 * struct rhashtable_params params = {
791 * .head_offset = offsetof(struct test_obj, node),
792 * .key_offset = offsetof(struct test_obj, key),
793 * .key_len = sizeof(int),
Daniel Borkmann87545892014-12-10 16:33:11 +0100794 * .hashfn = jhash,
Thomas Graff89bd6f2015-01-02 23:00:21 +0100795 * .nulls_base = (1U << RHT_BASE_SHIFT),
Thomas Graf7e1e7762014-08-02 11:47:44 +0200796 * };
797 *
798 * Configuration Example 2: Variable length keys
799 * struct test_obj {
800 * [...]
801 * struct rhash_head node;
802 * };
803 *
804 * u32 my_hash_fn(const void *data, u32 seed)
805 * {
806 * struct test_obj *obj = data;
807 *
808 * return [... hash ...];
809 * }
810 *
811 * struct rhashtable_params params = {
812 * .head_offset = offsetof(struct test_obj, node),
Daniel Borkmann87545892014-12-10 16:33:11 +0100813 * .hashfn = jhash,
Thomas Graf7e1e7762014-08-02 11:47:44 +0200814 * .obj_hashfn = my_hash_fn,
Thomas Graf7e1e7762014-08-02 11:47:44 +0200815 * };
816 */
817int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params)
818{
819 struct bucket_table *tbl;
820 size_t size;
821
822 size = HASH_DEFAULT_SIZE;
823
824 if ((params->key_len && !params->hashfn) ||
825 (!params->key_len && !params->obj_hashfn))
826 return -EINVAL;
827
Thomas Graff89bd6f2015-01-02 23:00:21 +0100828 if (params->nulls_base && params->nulls_base < (1U << RHT_BASE_SHIFT))
829 return -EINVAL;
830
Ying Xue94000172014-09-03 09:22:36 +0800831 params->min_shift = max_t(size_t, params->min_shift,
832 ilog2(HASH_MIN_SIZE));
833
Thomas Graf7e1e7762014-08-02 11:47:44 +0200834 if (params->nelem_hint)
Ying Xue94000172014-09-03 09:22:36 +0800835 size = rounded_hashtable_size(params);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200836
Thomas Graf97defe12015-01-02 23:00:20 +0100837 memset(ht, 0, sizeof(*ht));
838 mutex_init(&ht->mutex);
839 memcpy(&ht->p, params, sizeof(*params));
840
841 if (params->locks_mul)
842 ht->p.locks_mul = roundup_pow_of_two(params->locks_mul);
843 else
844 ht->p.locks_mul = BUCKET_LOCKS_PER_CPU;
845
846 tbl = bucket_table_alloc(ht, size);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200847 if (tbl == NULL)
848 return -ENOMEM;
849
Ying Xuec0c09bf2015-01-07 13:41:56 +0800850 atomic_set(&ht->shift, ilog2(tbl->size));
Thomas Graf7e1e7762014-08-02 11:47:44 +0200851 RCU_INIT_POINTER(ht->tbl, tbl);
Thomas Graf97defe12015-01-02 23:00:20 +0100852 RCU_INIT_POINTER(ht->future_tbl, tbl);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200853
854 if (!ht->p.hash_rnd)
855 get_random_bytes(&ht->p.hash_rnd, sizeof(ht->p.hash_rnd));
856
Thomas Graf97defe12015-01-02 23:00:20 +0100857 if (ht->p.grow_decision || ht->p.shrink_decision)
858 INIT_DEFERRABLE_WORK(&ht->run_work, rht_deferred_worker);
859
Thomas Graf7e1e7762014-08-02 11:47:44 +0200860 return 0;
861}
862EXPORT_SYMBOL_GPL(rhashtable_init);
863
864/**
865 * rhashtable_destroy - destroy hash table
866 * @ht: the hash table to destroy
867 *
Pablo Neira Ayusoae82ddc2014-09-02 00:26:05 +0200868 * Frees the bucket array. This function is not rcu safe, therefore the caller
869 * has to make sure that no resizing may happen by unpublishing the hashtable
870 * and waiting for the quiescent cycle before releasing the bucket array.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200871 */
Thomas Graf97defe12015-01-02 23:00:20 +0100872void rhashtable_destroy(struct rhashtable *ht)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200873{
Thomas Graf97defe12015-01-02 23:00:20 +0100874 ht->being_destroyed = true;
875
876 mutex_lock(&ht->mutex);
877
878 cancel_delayed_work(&ht->run_work);
879 bucket_table_free(rht_dereference(ht->tbl, ht));
880
881 mutex_unlock(&ht->mutex);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200882}
883EXPORT_SYMBOL_GPL(rhashtable_destroy);
884
885/**************************************************************************
886 * Self Test
887 **************************************************************************/
888
889#ifdef CONFIG_TEST_RHASHTABLE
890
891#define TEST_HT_SIZE 8
892#define TEST_ENTRIES 2048
893#define TEST_PTR ((void *) 0xdeadbeef)
894#define TEST_NEXPANDS 4
895
Thomas Graf7e1e7762014-08-02 11:47:44 +0200896struct test_obj {
897 void *ptr;
898 int value;
899 struct rhash_head node;
900};
901
902static int __init test_rht_lookup(struct rhashtable *ht)
903{
904 unsigned int i;
905
906 for (i = 0; i < TEST_ENTRIES * 2; i++) {
907 struct test_obj *obj;
908 bool expected = !(i % 2);
909 u32 key = i;
910
911 obj = rhashtable_lookup(ht, &key);
912
913 if (expected && !obj) {
914 pr_warn("Test failed: Could not find key %u\n", key);
915 return -ENOENT;
916 } else if (!expected && obj) {
917 pr_warn("Test failed: Unexpected entry found for key %u\n",
918 key);
919 return -EEXIST;
920 } else if (expected && obj) {
921 if (obj->ptr != TEST_PTR || obj->value != i) {
922 pr_warn("Test failed: Lookup value mismatch %p!=%p, %u!=%u\n",
923 obj->ptr, TEST_PTR, obj->value, i);
924 return -EINVAL;
925 }
926 }
927 }
928
929 return 0;
930}
931
Thomas Graf3e7b2ec2014-11-24 12:37:58 +0100932static void test_bucket_stats(struct rhashtable *ht, bool quiet)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200933{
Thomas Graf3e7b2ec2014-11-24 12:37:58 +0100934 unsigned int cnt, rcu_cnt, i, total = 0;
Thomas Graf88d6ed12015-01-02 23:00:16 +0100935 struct rhash_head *pos;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200936 struct test_obj *obj;
Thomas Graf3e7b2ec2014-11-24 12:37:58 +0100937 struct bucket_table *tbl;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200938
Thomas Graf3e7b2ec2014-11-24 12:37:58 +0100939 tbl = rht_dereference_rcu(ht->tbl, ht);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200940 for (i = 0; i < tbl->size; i++) {
Thomas Graf3e7b2ec2014-11-24 12:37:58 +0100941 rcu_cnt = cnt = 0;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200942
943 if (!quiet)
944 pr_info(" [%#4x/%zu]", i, tbl->size);
945
Thomas Graf88d6ed12015-01-02 23:00:16 +0100946 rht_for_each_entry_rcu(obj, pos, tbl, i, node) {
Thomas Graf7e1e7762014-08-02 11:47:44 +0200947 cnt++;
948 total++;
949 if (!quiet)
950 pr_cont(" [%p],", obj);
951 }
952
Thomas Graf88d6ed12015-01-02 23:00:16 +0100953 rht_for_each_entry_rcu(obj, pos, tbl, i, node)
Thomas Graf3e7b2ec2014-11-24 12:37:58 +0100954 rcu_cnt++;
955
956 if (rcu_cnt != cnt)
957 pr_warn("Test failed: Chain count mismach %d != %d",
958 cnt, rcu_cnt);
959
Thomas Graf7e1e7762014-08-02 11:47:44 +0200960 if (!quiet)
961 pr_cont("\n [%#x] first element: %p, chain length: %u\n",
962 i, tbl->buckets[i], cnt);
963 }
964
Thomas Graf97defe12015-01-02 23:00:20 +0100965 pr_info(" Traversal complete: counted=%u, nelems=%u, entries=%d\n",
966 total, atomic_read(&ht->nelems), TEST_ENTRIES);
Thomas Graf3e7b2ec2014-11-24 12:37:58 +0100967
Thomas Graf97defe12015-01-02 23:00:20 +0100968 if (total != atomic_read(&ht->nelems) || total != TEST_ENTRIES)
Thomas Graf3e7b2ec2014-11-24 12:37:58 +0100969 pr_warn("Test failed: Total count mismatch ^^^");
Thomas Graf7e1e7762014-08-02 11:47:44 +0200970}
971
972static int __init test_rhashtable(struct rhashtable *ht)
973{
974 struct bucket_table *tbl;
Thomas Graf88d6ed12015-01-02 23:00:16 +0100975 struct test_obj *obj;
976 struct rhash_head *pos, *next;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200977 int err;
978 unsigned int i;
979
980 /*
981 * Insertion Test:
982 * Insert TEST_ENTRIES into table with all keys even numbers
983 */
984 pr_info(" Adding %d keys\n", TEST_ENTRIES);
985 for (i = 0; i < TEST_ENTRIES; i++) {
986 struct test_obj *obj;
987
988 obj = kzalloc(sizeof(*obj), GFP_KERNEL);
989 if (!obj) {
990 err = -ENOMEM;
991 goto error;
992 }
993
994 obj->ptr = TEST_PTR;
995 obj->value = i * 2;
996
Thomas Graf6eba8222014-11-13 13:45:46 +0100997 rhashtable_insert(ht, &obj->node);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200998 }
999
1000 rcu_read_lock();
Thomas Graf3e7b2ec2014-11-24 12:37:58 +01001001 test_bucket_stats(ht, true);
Thomas Graf7e1e7762014-08-02 11:47:44 +02001002 test_rht_lookup(ht);
1003 rcu_read_unlock();
1004
1005 for (i = 0; i < TEST_NEXPANDS; i++) {
1006 pr_info(" Table expansion iteration %u...\n", i);
Thomas Graf97defe12015-01-02 23:00:20 +01001007 mutex_lock(&ht->mutex);
Thomas Graf6eba8222014-11-13 13:45:46 +01001008 rhashtable_expand(ht);
Thomas Graf97defe12015-01-02 23:00:20 +01001009 mutex_unlock(&ht->mutex);
Thomas Graf7e1e7762014-08-02 11:47:44 +02001010
1011 rcu_read_lock();
1012 pr_info(" Verifying lookups...\n");
1013 test_rht_lookup(ht);
1014 rcu_read_unlock();
1015 }
1016
1017 for (i = 0; i < TEST_NEXPANDS; i++) {
1018 pr_info(" Table shrinkage iteration %u...\n", i);
Thomas Graf97defe12015-01-02 23:00:20 +01001019 mutex_lock(&ht->mutex);
Thomas Graf6eba8222014-11-13 13:45:46 +01001020 rhashtable_shrink(ht);
Thomas Graf97defe12015-01-02 23:00:20 +01001021 mutex_unlock(&ht->mutex);
Thomas Graf7e1e7762014-08-02 11:47:44 +02001022
1023 rcu_read_lock();
1024 pr_info(" Verifying lookups...\n");
1025 test_rht_lookup(ht);
1026 rcu_read_unlock();
1027 }
1028
Thomas Graf3e7b2ec2014-11-24 12:37:58 +01001029 rcu_read_lock();
1030 test_bucket_stats(ht, true);
1031 rcu_read_unlock();
1032
Thomas Graf7e1e7762014-08-02 11:47:44 +02001033 pr_info(" Deleting %d keys\n", TEST_ENTRIES);
1034 for (i = 0; i < TEST_ENTRIES; i++) {
1035 u32 key = i * 2;
1036
1037 obj = rhashtable_lookup(ht, &key);
1038 BUG_ON(!obj);
1039
Thomas Graf6eba8222014-11-13 13:45:46 +01001040 rhashtable_remove(ht, &obj->node);
Thomas Graf7e1e7762014-08-02 11:47:44 +02001041 kfree(obj);
1042 }
1043
1044 return 0;
1045
1046error:
1047 tbl = rht_dereference_rcu(ht->tbl, ht);
1048 for (i = 0; i < tbl->size; i++)
Thomas Graf88d6ed12015-01-02 23:00:16 +01001049 rht_for_each_entry_safe(obj, pos, next, tbl, i, node)
Thomas Graf7e1e7762014-08-02 11:47:44 +02001050 kfree(obj);
1051
1052 return err;
1053}
1054
1055static int __init test_rht_init(void)
1056{
1057 struct rhashtable ht;
1058 struct rhashtable_params params = {
1059 .nelem_hint = TEST_HT_SIZE,
1060 .head_offset = offsetof(struct test_obj, node),
1061 .key_offset = offsetof(struct test_obj, value),
1062 .key_len = sizeof(int),
Daniel Borkmann87545892014-12-10 16:33:11 +01001063 .hashfn = jhash,
Thomas Graff89bd6f2015-01-02 23:00:21 +01001064 .nulls_base = (3U << RHT_BASE_SHIFT),
Thomas Graf7e1e7762014-08-02 11:47:44 +02001065 .grow_decision = rht_grow_above_75,
1066 .shrink_decision = rht_shrink_below_30,
1067 };
1068 int err;
1069
1070 pr_info("Running resizable hashtable tests...\n");
1071
1072 err = rhashtable_init(&ht, &params);
1073 if (err < 0) {
1074 pr_warn("Test failed: Unable to initialize hashtable: %d\n",
1075 err);
1076 return err;
1077 }
1078
1079 err = test_rhashtable(&ht);
1080
1081 rhashtable_destroy(&ht);
1082
1083 return err;
1084}
1085
1086subsys_initcall(test_rht_init);
1087
1088#endif /* CONFIG_TEST_RHASHTABLE */