blob: 4898442b837fbd715f8d5079a1060e43c4b7a367 [file] [log] [blame]
Thomas Graf7e1e7762014-08-02 11:47:44 +02001/*
2 * Resizable, Scalable, Concurrent Hash Table
3 *
Herbert Xu02fd97c2015-03-20 21:57:00 +11004 * Copyright (c) 2015 Herbert Xu <herbert@gondor.apana.org.au>
Thomas Grafa5ec68e2015-02-05 02:03:32 +01005 * Copyright (c) 2014-2015 Thomas Graf <tgraf@suug.ch>
Thomas Graf7e1e7762014-08-02 11:47:44 +02006 * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
7 *
Thomas Graf7e1e7762014-08-02 11:47:44 +02008 * Code partially derived from nft_hash
Herbert Xu02fd97c2015-03-20 21:57:00 +11009 * Rewritten with rehash code from br_multicast plus single list
10 * pointer as suggested by Josh Triplett
Thomas Graf7e1e7762014-08-02 11:47:44 +020011 *
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>
Eric Dumazet5beb5c92015-02-26 07:20:34 -080020#include <linux/sched.h>
Thomas Graf7e1e7762014-08-02 11:47:44 +020021#include <linux/slab.h>
22#include <linux/vmalloc.h>
23#include <linux/mm.h>
Daniel Borkmann87545892014-12-10 16:33:11 +010024#include <linux/jhash.h>
Thomas Graf7e1e7762014-08-02 11:47:44 +020025#include <linux/random.h>
26#include <linux/rhashtable.h>
Stephen Rothwell61d7b092015-02-09 14:04:03 +110027#include <linux/err.h>
Thomas Graf7e1e7762014-08-02 11:47:44 +020028
29#define HASH_DEFAULT_SIZE 64UL
Herbert Xuc2e213c2015-03-18 20:01:16 +110030#define HASH_MIN_SIZE 4U
Thomas Graf97defe12015-01-02 23:00:20 +010031#define BUCKET_LOCKS_PER_CPU 128UL
32
Herbert Xu988dfbd2015-03-10 09:27:55 +110033static u32 head_hashfn(struct rhashtable *ht,
Thomas Graf8d24c0b2015-01-02 23:00:14 +010034 const struct bucket_table *tbl,
35 const struct rhash_head *he)
Thomas Graf7e1e7762014-08-02 11:47:44 +020036{
Herbert Xu02fd97c2015-03-20 21:57:00 +110037 return rht_head_hashfn(ht, tbl, he, ht->p);
Thomas Graf7e1e7762014-08-02 11:47:44 +020038}
39
Thomas Grafa03eaec2015-02-05 02:03:34 +010040#ifdef CONFIG_PROVE_LOCKING
Thomas Grafa03eaec2015-02-05 02:03:34 +010041#define ASSERT_RHT_MUTEX(HT) BUG_ON(!lockdep_rht_mutex_is_held(HT))
Thomas Grafa03eaec2015-02-05 02:03:34 +010042
43int lockdep_rht_mutex_is_held(struct rhashtable *ht)
44{
45 return (debug_locks) ? lockdep_is_held(&ht->mutex) : 1;
46}
47EXPORT_SYMBOL_GPL(lockdep_rht_mutex_is_held);
48
49int lockdep_rht_bucket_is_held(const struct bucket_table *tbl, u32 hash)
50{
Herbert Xu02fd97c2015-03-20 21:57:00 +110051 spinlock_t *lock = rht_bucket_lock(tbl, hash);
Thomas Grafa03eaec2015-02-05 02:03:34 +010052
53 return (debug_locks) ? lockdep_is_held(lock) : 1;
54}
55EXPORT_SYMBOL_GPL(lockdep_rht_bucket_is_held);
56#else
57#define ASSERT_RHT_MUTEX(HT)
Thomas Grafa03eaec2015-02-05 02:03:34 +010058#endif
59
60
Herbert Xub9ecfda2015-03-24 00:50:27 +110061static int alloc_bucket_locks(struct rhashtable *ht, struct bucket_table *tbl,
62 gfp_t gfp)
Thomas Graf97defe12015-01-02 23:00:20 +010063{
64 unsigned int i, size;
65#if defined(CONFIG_PROVE_LOCKING)
66 unsigned int nr_pcpus = 2;
67#else
68 unsigned int nr_pcpus = num_possible_cpus();
69#endif
70
71 nr_pcpus = min_t(unsigned int, nr_pcpus, 32UL);
72 size = roundup_pow_of_two(nr_pcpus * ht->p.locks_mul);
73
Thomas Grafa5ec68e2015-02-05 02:03:32 +010074 /* Never allocate more than 0.5 locks per bucket */
75 size = min_t(unsigned int, size, tbl->size >> 1);
Thomas Graf97defe12015-01-02 23:00:20 +010076
77 if (sizeof(spinlock_t) != 0) {
78#ifdef CONFIG_NUMA
Herbert Xub9ecfda2015-03-24 00:50:27 +110079 if (size * sizeof(spinlock_t) > PAGE_SIZE &&
80 gfp == GFP_KERNEL)
Thomas Graf97defe12015-01-02 23:00:20 +010081 tbl->locks = vmalloc(size * sizeof(spinlock_t));
82 else
83#endif
84 tbl->locks = kmalloc_array(size, sizeof(spinlock_t),
Herbert Xub9ecfda2015-03-24 00:50:27 +110085 gfp);
Thomas Graf97defe12015-01-02 23:00:20 +010086 if (!tbl->locks)
87 return -ENOMEM;
88 for (i = 0; i < size; i++)
89 spin_lock_init(&tbl->locks[i]);
90 }
91 tbl->locks_mask = size - 1;
92
93 return 0;
94}
95
96static void bucket_table_free(const struct bucket_table *tbl)
97{
98 if (tbl)
99 kvfree(tbl->locks);
100
101 kvfree(tbl);
102}
103
Herbert Xu9d901bc2015-03-14 13:57:23 +1100104static void bucket_table_free_rcu(struct rcu_head *head)
105{
106 bucket_table_free(container_of(head, struct bucket_table, rcu));
107}
108
Thomas Graf97defe12015-01-02 23:00:20 +0100109static struct bucket_table *bucket_table_alloc(struct rhashtable *ht,
Herbert Xub9ecfda2015-03-24 00:50:27 +1100110 size_t nbuckets,
111 gfp_t gfp)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200112{
Daniel Borkmanneb6d1ab2015-02-20 00:53:38 +0100113 struct bucket_table *tbl = NULL;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200114 size_t size;
Thomas Graff89bd6f2015-01-02 23:00:21 +0100115 int i;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200116
117 size = sizeof(*tbl) + nbuckets * sizeof(tbl->buckets[0]);
Herbert Xub9ecfda2015-03-24 00:50:27 +1100118 if (size <= (PAGE_SIZE << PAGE_ALLOC_COSTLY_ORDER) ||
119 gfp != GFP_KERNEL)
120 tbl = kzalloc(size, gfp | __GFP_NOWARN | __GFP_NORETRY);
121 if (tbl == NULL && gfp == GFP_KERNEL)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200122 tbl = vzalloc(size);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200123 if (tbl == NULL)
124 return NULL;
125
126 tbl->size = nbuckets;
127
Herbert Xub9ecfda2015-03-24 00:50:27 +1100128 if (alloc_bucket_locks(ht, tbl, gfp) < 0) {
Thomas Graf97defe12015-01-02 23:00:20 +0100129 bucket_table_free(tbl);
130 return NULL;
131 }
Thomas Graf7e1e7762014-08-02 11:47:44 +0200132
Herbert Xueddee5ba2015-03-14 13:57:20 +1100133 INIT_LIST_HEAD(&tbl->walkers);
134
Herbert Xu5269b532015-03-14 13:57:22 +1100135 get_random_bytes(&tbl->hash_rnd, sizeof(tbl->hash_rnd));
136
Thomas Graff89bd6f2015-01-02 23:00:21 +0100137 for (i = 0; i < nbuckets; i++)
138 INIT_RHT_NULLS_HEAD(tbl->buckets[i], ht, i);
139
Thomas Graf97defe12015-01-02 23:00:20 +0100140 return tbl;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200141}
142
Herbert Xub8244782015-03-24 00:50:26 +1100143static struct bucket_table *rhashtable_last_table(struct rhashtable *ht,
144 struct bucket_table *tbl)
145{
146 struct bucket_table *new_tbl;
147
148 do {
149 new_tbl = tbl;
150 tbl = rht_dereference_rcu(tbl->future_tbl, ht);
151 } while (tbl);
152
153 return new_tbl;
154}
155
Thomas Graf299e5c32015-03-24 14:18:17 +0100156static int rhashtable_rehash_one(struct rhashtable *ht, unsigned int old_hash)
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100157{
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100158 struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
Herbert Xub8244782015-03-24 00:50:26 +1100159 struct bucket_table *new_tbl = rhashtable_last_table(ht,
160 rht_dereference_rcu(old_tbl->future_tbl, ht));
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100161 struct rhash_head __rcu **pprev = &old_tbl->buckets[old_hash];
162 int err = -ENOENT;
163 struct rhash_head *head, *next, *entry;
164 spinlock_t *new_bucket_lock;
Thomas Graf299e5c32015-03-24 14:18:17 +0100165 unsigned int new_hash;
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100166
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100167 rht_for_each(entry, old_tbl, old_hash) {
168 err = 0;
169 next = rht_dereference_bucket(entry->next, old_tbl, old_hash);
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100170
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100171 if (rht_is_a_nulls(next))
Thomas Graf7e1e7762014-08-02 11:47:44 +0200172 break;
Thomas Graf97defe12015-01-02 23:00:20 +0100173
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100174 pprev = &entry->next;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200175 }
176
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100177 if (err)
178 goto out;
Thomas Graf97defe12015-01-02 23:00:20 +0100179
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100180 new_hash = head_hashfn(ht, new_tbl, entry);
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100181
Herbert Xu02fd97c2015-03-20 21:57:00 +1100182 new_bucket_lock = rht_bucket_lock(new_tbl, new_hash);
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100183
Herbert Xu8f2484b2015-03-14 13:57:21 +1100184 spin_lock_nested(new_bucket_lock, SINGLE_DEPTH_NESTING);
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100185 head = rht_dereference_bucket(new_tbl->buckets[new_hash],
186 new_tbl, new_hash);
187
188 if (rht_is_a_nulls(head))
189 INIT_RHT_NULLS_HEAD(entry->next, ht, new_hash);
190 else
191 RCU_INIT_POINTER(entry->next, head);
192
193 rcu_assign_pointer(new_tbl->buckets[new_hash], entry);
194 spin_unlock(new_bucket_lock);
195
196 rcu_assign_pointer(*pprev, next);
197
198out:
199 return err;
Thomas Graf97defe12015-01-02 23:00:20 +0100200}
201
Thomas Graf299e5c32015-03-24 14:18:17 +0100202static void rhashtable_rehash_chain(struct rhashtable *ht,
203 unsigned int old_hash)
Thomas Graf97defe12015-01-02 23:00:20 +0100204{
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100205 struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
206 spinlock_t *old_bucket_lock;
Thomas Graf7cd10db2015-02-05 02:03:35 +0100207
Herbert Xu02fd97c2015-03-20 21:57:00 +1100208 old_bucket_lock = rht_bucket_lock(old_tbl, old_hash);
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100209
210 spin_lock_bh(old_bucket_lock);
211 while (!rhashtable_rehash_one(ht, old_hash))
212 ;
Herbert Xu63d512d2015-03-14 13:57:24 +1100213 old_tbl->rehash++;
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100214 spin_unlock_bh(old_bucket_lock);
215}
216
Herbert Xub8244782015-03-24 00:50:26 +1100217static int rhashtable_rehash_attach(struct rhashtable *ht,
218 struct bucket_table *old_tbl,
219 struct bucket_table *new_tbl)
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100220{
Herbert Xub8244782015-03-24 00:50:26 +1100221 /* Protect future_tbl using the first bucket lock. */
222 spin_lock_bh(old_tbl->locks);
223
224 /* Did somebody beat us to it? */
225 if (rcu_access_pointer(old_tbl->future_tbl)) {
226 spin_unlock_bh(old_tbl->locks);
227 return -EEXIST;
228 }
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100229
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100230 /* Make insertions go into the new, empty table right away. Deletions
231 * and lookups will be attempted in both tables until we synchronize.
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100232 */
Herbert Xuc4db8842015-03-14 13:57:25 +1100233 rcu_assign_pointer(old_tbl->future_tbl, new_tbl);
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100234
Herbert Xu9497df82015-03-12 22:07:49 +1100235 /* Ensure the new table is visible to readers. */
236 smp_wmb();
237
Herbert Xub8244782015-03-24 00:50:26 +1100238 spin_unlock_bh(old_tbl->locks);
239
240 return 0;
241}
242
243static int rhashtable_rehash_table(struct rhashtable *ht)
244{
245 struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
246 struct bucket_table *new_tbl;
247 struct rhashtable_walker *walker;
Thomas Graf299e5c32015-03-24 14:18:17 +0100248 unsigned int old_hash;
Herbert Xub8244782015-03-24 00:50:26 +1100249
250 new_tbl = rht_dereference(old_tbl->future_tbl, ht);
251 if (!new_tbl)
252 return 0;
253
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100254 for (old_hash = 0; old_hash < old_tbl->size; old_hash++)
255 rhashtable_rehash_chain(ht, old_hash);
256
257 /* Publish the new table pointer. */
258 rcu_assign_pointer(ht->tbl, new_tbl);
259
Herbert Xuba7c95e2015-03-24 09:53:17 +1100260 spin_lock(&ht->lock);
Herbert Xueddee5ba2015-03-14 13:57:20 +1100261 list_for_each_entry(walker, &old_tbl->walkers, list)
262 walker->tbl = NULL;
Herbert Xuba7c95e2015-03-24 09:53:17 +1100263 spin_unlock(&ht->lock);
Herbert Xueddee5ba2015-03-14 13:57:20 +1100264
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100265 /* Wait for readers. All new readers will see the new
266 * table, and thus no references to the old table will
267 * remain.
268 */
Herbert Xu9d901bc2015-03-14 13:57:23 +1100269 call_rcu(&old_tbl->rcu, bucket_table_free_rcu);
Herbert Xub8244782015-03-24 00:50:26 +1100270
271 return rht_dereference(new_tbl->future_tbl, ht) ? -EAGAIN : 0;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200272}
273
274/**
275 * rhashtable_expand - Expand hash table while allowing concurrent lookups
276 * @ht: the hash table to expand
Thomas Graf7e1e7762014-08-02 11:47:44 +0200277 *
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100278 * A secondary bucket array is allocated and the hash entries are migrated.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200279 *
280 * This function may only be called in a context where it is safe to call
281 * synchronize_rcu(), e.g. not within a rcu_read_lock() section.
282 *
Thomas Graf97defe12015-01-02 23:00:20 +0100283 * The caller must ensure that no concurrent resizing occurs by holding
284 * ht->mutex.
285 *
286 * It is valid to have concurrent insertions and deletions protected by per
287 * bucket locks or concurrent RCU protected lookups and traversals.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200288 */
Herbert Xub8244782015-03-24 00:50:26 +1100289static int rhashtable_expand(struct rhashtable *ht)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200290{
291 struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);
Herbert Xub8244782015-03-24 00:50:26 +1100292 int err;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200293
294 ASSERT_RHT_MUTEX(ht);
295
Herbert Xub8244782015-03-24 00:50:26 +1100296 old_tbl = rhashtable_last_table(ht, old_tbl);
297
Herbert Xub9ecfda2015-03-24 00:50:27 +1100298 new_tbl = bucket_table_alloc(ht, old_tbl->size * 2, GFP_KERNEL);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200299 if (new_tbl == NULL)
300 return -ENOMEM;
301
Herbert Xub8244782015-03-24 00:50:26 +1100302 err = rhashtable_rehash_attach(ht, old_tbl, new_tbl);
303 if (err)
304 bucket_table_free(new_tbl);
305
306 return err;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200307}
Thomas Graf7e1e7762014-08-02 11:47:44 +0200308
309/**
310 * rhashtable_shrink - Shrink hash table while allowing concurrent lookups
311 * @ht: the hash table to shrink
Thomas Graf7e1e7762014-08-02 11:47:44 +0200312 *
Herbert Xu18093d12015-03-24 00:50:25 +1100313 * This function shrinks the hash table to fit, i.e., the smallest
314 * size would not cause it to expand right away automatically.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200315 *
Thomas Graf97defe12015-01-02 23:00:20 +0100316 * The caller must ensure that no concurrent resizing occurs by holding
317 * ht->mutex.
318 *
Thomas Graf7e1e7762014-08-02 11:47:44 +0200319 * The caller must ensure that no concurrent table mutations take place.
320 * It is however valid to have concurrent lookups if they are RCU protected.
Thomas Graf97defe12015-01-02 23:00:20 +0100321 *
322 * It is valid to have concurrent insertions and deletions protected by per
323 * bucket locks or concurrent RCU protected lookups and traversals.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200324 */
Herbert Xub8244782015-03-24 00:50:26 +1100325static int rhashtable_shrink(struct rhashtable *ht)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200326{
Daniel Borkmanna5b68462015-03-12 15:28:40 +0100327 struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);
Thomas Graf299e5c32015-03-24 14:18:17 +0100328 unsigned int size;
Herbert Xub8244782015-03-24 00:50:26 +1100329 int err;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200330
331 ASSERT_RHT_MUTEX(ht);
332
Thomas Graf299e5c32015-03-24 14:18:17 +0100333 size = roundup_pow_of_two(atomic_read(&ht->nelems) * 3 / 2);
Herbert Xu18093d12015-03-24 00:50:25 +1100334 if (size < ht->p.min_size)
335 size = ht->p.min_size;
336
337 if (old_tbl->size <= size)
338 return 0;
339
Herbert Xub8244782015-03-24 00:50:26 +1100340 if (rht_dereference(old_tbl->future_tbl, ht))
341 return -EEXIST;
342
Herbert Xub9ecfda2015-03-24 00:50:27 +1100343 new_tbl = bucket_table_alloc(ht, size, GFP_KERNEL);
Thomas Graf97defe12015-01-02 23:00:20 +0100344 if (new_tbl == NULL)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200345 return -ENOMEM;
346
Herbert Xub8244782015-03-24 00:50:26 +1100347 err = rhashtable_rehash_attach(ht, old_tbl, new_tbl);
348 if (err)
349 bucket_table_free(new_tbl);
350
351 return err;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200352}
Thomas Graf7e1e7762014-08-02 11:47:44 +0200353
Thomas Graf97defe12015-01-02 23:00:20 +0100354static void rht_deferred_worker(struct work_struct *work)
355{
356 struct rhashtable *ht;
357 struct bucket_table *tbl;
Herbert Xub8244782015-03-24 00:50:26 +1100358 int err = 0;
Thomas Graf97defe12015-01-02 23:00:20 +0100359
Ying Xue57699a42015-01-16 11:13:09 +0800360 ht = container_of(work, struct rhashtable, run_work);
Thomas Graf97defe12015-01-02 23:00:20 +0100361 mutex_lock(&ht->mutex);
Herbert Xu28134a52015-02-04 07:33:22 +1100362
Thomas Graf97defe12015-01-02 23:00:20 +0100363 tbl = rht_dereference(ht->tbl, ht);
Herbert Xub8244782015-03-24 00:50:26 +1100364 tbl = rhashtable_last_table(ht, tbl);
Thomas Graf97defe12015-01-02 23:00:20 +0100365
Daniel Borkmanna5b68462015-03-12 15:28:40 +0100366 if (rht_grow_above_75(ht, tbl))
Thomas Graf97defe12015-01-02 23:00:20 +0100367 rhashtable_expand(ht);
Thomas Grafb5e2c152015-03-24 20:42:19 +0000368 else if (ht->p.automatic_shrinking && rht_shrink_below_30(ht, tbl))
Thomas Graf97defe12015-01-02 23:00:20 +0100369 rhashtable_shrink(ht);
Herbert Xub8244782015-03-24 00:50:26 +1100370
371 err = rhashtable_rehash_table(ht);
372
Thomas Graf97defe12015-01-02 23:00:20 +0100373 mutex_unlock(&ht->mutex);
Herbert Xub8244782015-03-24 00:50:26 +1100374
375 if (err)
376 schedule_work(&ht->run_work);
Thomas Graf97defe12015-01-02 23:00:20 +0100377}
378
Herbert Xuccd57b12015-03-24 00:50:28 +1100379static bool rhashtable_check_elasticity(struct rhashtable *ht,
380 struct bucket_table *tbl,
Thomas Graf299e5c32015-03-24 14:18:17 +0100381 unsigned int hash)
Herbert Xuccd57b12015-03-24 00:50:28 +1100382{
Thomas Graf299e5c32015-03-24 14:18:17 +0100383 unsigned int elasticity = ht->elasticity;
Herbert Xuccd57b12015-03-24 00:50:28 +1100384 struct rhash_head *head;
385
386 rht_for_each(head, tbl, hash)
387 if (!--elasticity)
388 return true;
389
390 return false;
391}
392
393int rhashtable_insert_rehash(struct rhashtable *ht)
394{
395 struct bucket_table *old_tbl;
396 struct bucket_table *new_tbl;
397 struct bucket_table *tbl;
398 unsigned int size;
399 int err;
400
401 old_tbl = rht_dereference_rcu(ht->tbl, ht);
402 tbl = rhashtable_last_table(ht, old_tbl);
403
404 size = tbl->size;
405
406 if (rht_grow_above_75(ht, tbl))
407 size *= 2;
408 /* More than two rehashes (not resizes) detected. */
409 else if (WARN_ON(old_tbl != tbl && old_tbl->size == size))
410 return -EBUSY;
411
412 new_tbl = bucket_table_alloc(ht, size, GFP_ATOMIC);
413 if (new_tbl == NULL)
414 return -ENOMEM;
415
416 err = rhashtable_rehash_attach(ht, tbl, new_tbl);
417 if (err) {
418 bucket_table_free(new_tbl);
419 if (err == -EEXIST)
420 err = 0;
421 } else
422 schedule_work(&ht->run_work);
423
424 return err;
425}
426EXPORT_SYMBOL_GPL(rhashtable_insert_rehash);
427
Herbert Xu02fd97c2015-03-20 21:57:00 +1100428int rhashtable_insert_slow(struct rhashtable *ht, const void *key,
429 struct rhash_head *obj,
430 struct bucket_table *tbl)
431{
432 struct rhash_head *head;
Thomas Graf299e5c32015-03-24 14:18:17 +0100433 unsigned int hash;
Herbert Xuccd57b12015-03-24 00:50:28 +1100434 int err;
Herbert Xu02fd97c2015-03-20 21:57:00 +1100435
Herbert Xub8244782015-03-24 00:50:26 +1100436 tbl = rhashtable_last_table(ht, tbl);
Herbert Xu02fd97c2015-03-20 21:57:00 +1100437 hash = head_hashfn(ht, tbl, obj);
438 spin_lock_nested(rht_bucket_lock(tbl, hash), SINGLE_DEPTH_NESTING);
439
Herbert Xuccd57b12015-03-24 00:50:28 +1100440 err = -EEXIST;
Herbert Xu02fd97c2015-03-20 21:57:00 +1100441 if (key && rhashtable_lookup_fast(ht, key, ht->p))
442 goto exit;
443
Herbert Xuccd57b12015-03-24 00:50:28 +1100444 err = -EAGAIN;
445 if (rhashtable_check_elasticity(ht, tbl, hash) ||
446 rht_grow_above_100(ht, tbl))
447 goto exit;
448
Herbert Xu02fd97c2015-03-20 21:57:00 +1100449 err = 0;
450
451 head = rht_dereference_bucket(tbl->buckets[hash], tbl, hash);
452
453 RCU_INIT_POINTER(obj->next, head);
454
455 rcu_assign_pointer(tbl->buckets[hash], obj);
456
457 atomic_inc(&ht->nelems);
458
459exit:
460 spin_unlock(rht_bucket_lock(tbl, hash));
461
462 return err;
463}
464EXPORT_SYMBOL_GPL(rhashtable_insert_slow);
465
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100466/**
467 * rhashtable_walk_init - Initialise an iterator
468 * @ht: Table to walk over
469 * @iter: Hash table Iterator
470 *
471 * This function prepares a hash table walk.
472 *
473 * Note that if you restart a walk after rhashtable_walk_stop you
474 * may see the same object twice. Also, you may miss objects if
475 * there are removals in between rhashtable_walk_stop and the next
476 * call to rhashtable_walk_start.
477 *
478 * For a completely stable walk you should construct your own data
479 * structure outside the hash table.
480 *
481 * This function may sleep so you must not call it from interrupt
482 * context or with spin locks held.
483 *
484 * You must call rhashtable_walk_exit if this function returns
485 * successfully.
486 */
487int rhashtable_walk_init(struct rhashtable *ht, struct rhashtable_iter *iter)
488{
489 iter->ht = ht;
490 iter->p = NULL;
491 iter->slot = 0;
492 iter->skip = 0;
493
494 iter->walker = kmalloc(sizeof(*iter->walker), GFP_KERNEL);
495 if (!iter->walker)
496 return -ENOMEM;
497
498 mutex_lock(&ht->mutex);
Herbert Xueddee5ba2015-03-14 13:57:20 +1100499 iter->walker->tbl = rht_dereference(ht->tbl, ht);
500 list_add(&iter->walker->list, &iter->walker->tbl->walkers);
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100501 mutex_unlock(&ht->mutex);
502
503 return 0;
504}
505EXPORT_SYMBOL_GPL(rhashtable_walk_init);
506
507/**
508 * rhashtable_walk_exit - Free an iterator
509 * @iter: Hash table Iterator
510 *
511 * This function frees resources allocated by rhashtable_walk_init.
512 */
513void rhashtable_walk_exit(struct rhashtable_iter *iter)
514{
515 mutex_lock(&iter->ht->mutex);
Herbert Xueddee5ba2015-03-14 13:57:20 +1100516 if (iter->walker->tbl)
517 list_del(&iter->walker->list);
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100518 mutex_unlock(&iter->ht->mutex);
519 kfree(iter->walker);
520}
521EXPORT_SYMBOL_GPL(rhashtable_walk_exit);
522
523/**
524 * rhashtable_walk_start - Start a hash table walk
525 * @iter: Hash table iterator
526 *
527 * Start a hash table walk. Note that we take the RCU lock in all
528 * cases including when we return an error. So you must always call
529 * rhashtable_walk_stop to clean up.
530 *
531 * Returns zero if successful.
532 *
533 * Returns -EAGAIN if resize event occured. Note that the iterator
534 * will rewind back to the beginning and you may use it immediately
535 * by calling rhashtable_walk_next.
536 */
537int rhashtable_walk_start(struct rhashtable_iter *iter)
Thomas Grafdb4374f2015-03-16 10:42:27 +0100538 __acquires(RCU)
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100539{
Herbert Xueddee5ba2015-03-14 13:57:20 +1100540 struct rhashtable *ht = iter->ht;
541
542 mutex_lock(&ht->mutex);
543
544 if (iter->walker->tbl)
545 list_del(&iter->walker->list);
546
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100547 rcu_read_lock();
548
Herbert Xueddee5ba2015-03-14 13:57:20 +1100549 mutex_unlock(&ht->mutex);
550
551 if (!iter->walker->tbl) {
552 iter->walker->tbl = rht_dereference_rcu(ht->tbl, ht);
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100553 return -EAGAIN;
554 }
555
556 return 0;
557}
558EXPORT_SYMBOL_GPL(rhashtable_walk_start);
559
560/**
561 * rhashtable_walk_next - Return the next object and advance the iterator
562 * @iter: Hash table iterator
563 *
564 * Note that you must call rhashtable_walk_stop when you are finished
565 * with the walk.
566 *
567 * Returns the next object or NULL when the end of the table is reached.
568 *
569 * Returns -EAGAIN if resize event occured. Note that the iterator
570 * will rewind back to the beginning and you may continue to use it.
571 */
572void *rhashtable_walk_next(struct rhashtable_iter *iter)
573{
Herbert Xueddee5ba2015-03-14 13:57:20 +1100574 struct bucket_table *tbl = iter->walker->tbl;
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100575 struct rhashtable *ht = iter->ht;
576 struct rhash_head *p = iter->p;
577 void *obj = NULL;
578
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100579 if (p) {
580 p = rht_dereference_bucket_rcu(p->next, tbl, iter->slot);
581 goto next;
582 }
583
584 for (; iter->slot < tbl->size; iter->slot++) {
585 int skip = iter->skip;
586
587 rht_for_each_rcu(p, tbl, iter->slot) {
588 if (!skip)
589 break;
590 skip--;
591 }
592
593next:
594 if (!rht_is_a_nulls(p)) {
595 iter->skip++;
596 iter->p = p;
597 obj = rht_obj(ht, p);
598 goto out;
599 }
600
601 iter->skip = 0;
602 }
603
Herbert Xud88252f2015-03-24 00:50:19 +1100604 /* Ensure we see any new tables. */
605 smp_rmb();
606
Herbert Xuc4db8842015-03-14 13:57:25 +1100607 iter->walker->tbl = rht_dereference_rcu(tbl->future_tbl, ht);
608 if (iter->walker->tbl) {
Herbert Xueddee5ba2015-03-14 13:57:20 +1100609 iter->slot = 0;
610 iter->skip = 0;
611 return ERR_PTR(-EAGAIN);
612 }
613
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100614 iter->p = NULL;
615
616out:
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100617
618 return obj;
619}
620EXPORT_SYMBOL_GPL(rhashtable_walk_next);
621
622/**
623 * rhashtable_walk_stop - Finish a hash table walk
624 * @iter: Hash table iterator
625 *
626 * Finish a hash table walk.
627 */
628void rhashtable_walk_stop(struct rhashtable_iter *iter)
Thomas Grafdb4374f2015-03-16 10:42:27 +0100629 __releases(RCU)
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100630{
Herbert Xueddee5ba2015-03-14 13:57:20 +1100631 struct rhashtable *ht;
632 struct bucket_table *tbl = iter->walker->tbl;
633
Herbert Xueddee5ba2015-03-14 13:57:20 +1100634 if (!tbl)
Herbert Xu963ecbd2015-03-15 21:12:04 +1100635 goto out;
Herbert Xueddee5ba2015-03-14 13:57:20 +1100636
637 ht = iter->ht;
638
Herbert Xuba7c95e2015-03-24 09:53:17 +1100639 spin_lock(&ht->lock);
Herbert Xuc4db8842015-03-14 13:57:25 +1100640 if (tbl->rehash < tbl->size)
Herbert Xueddee5ba2015-03-14 13:57:20 +1100641 list_add(&iter->walker->list, &tbl->walkers);
642 else
643 iter->walker->tbl = NULL;
Herbert Xuba7c95e2015-03-24 09:53:17 +1100644 spin_unlock(&ht->lock);
Herbert Xueddee5ba2015-03-14 13:57:20 +1100645
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100646 iter->p = NULL;
Herbert Xu963ecbd2015-03-15 21:12:04 +1100647
648out:
649 rcu_read_unlock();
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100650}
651EXPORT_SYMBOL_GPL(rhashtable_walk_stop);
652
Herbert Xu488fb86e2015-03-20 21:56:59 +1100653static size_t rounded_hashtable_size(const struct rhashtable_params *params)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200654{
Ying Xue94000172014-09-03 09:22:36 +0800655 return max(roundup_pow_of_two(params->nelem_hint * 4 / 3),
Herbert Xue2e21c12015-03-18 20:01:21 +1100656 (unsigned long)params->min_size);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200657}
658
Herbert Xu31ccde22015-03-24 00:50:21 +1100659static u32 rhashtable_jhash2(const void *key, u32 length, u32 seed)
660{
661 return jhash2(key, length, seed);
662}
663
Thomas Graf7e1e7762014-08-02 11:47:44 +0200664/**
665 * rhashtable_init - initialize a new hash table
666 * @ht: hash table to be initialized
667 * @params: configuration parameters
668 *
669 * Initializes a new hash table based on the provided configuration
670 * parameters. A table can be configured either with a variable or
671 * fixed length key:
672 *
673 * Configuration Example 1: Fixed length keys
674 * struct test_obj {
675 * int key;
676 * void * my_member;
677 * struct rhash_head node;
678 * };
679 *
680 * struct rhashtable_params params = {
681 * .head_offset = offsetof(struct test_obj, node),
682 * .key_offset = offsetof(struct test_obj, key),
683 * .key_len = sizeof(int),
Daniel Borkmann87545892014-12-10 16:33:11 +0100684 * .hashfn = jhash,
Thomas Graff89bd6f2015-01-02 23:00:21 +0100685 * .nulls_base = (1U << RHT_BASE_SHIFT),
Thomas Graf7e1e7762014-08-02 11:47:44 +0200686 * };
687 *
688 * Configuration Example 2: Variable length keys
689 * struct test_obj {
690 * [...]
691 * struct rhash_head node;
692 * };
693 *
Patrick McHardy49f7b332015-03-25 13:07:45 +0000694 * u32 my_hash_fn(const void *data, u32 len, u32 seed)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200695 * {
696 * struct test_obj *obj = data;
697 *
698 * return [... hash ...];
699 * }
700 *
701 * struct rhashtable_params params = {
702 * .head_offset = offsetof(struct test_obj, node),
Daniel Borkmann87545892014-12-10 16:33:11 +0100703 * .hashfn = jhash,
Thomas Graf7e1e7762014-08-02 11:47:44 +0200704 * .obj_hashfn = my_hash_fn,
Thomas Graf7e1e7762014-08-02 11:47:44 +0200705 * };
706 */
Herbert Xu488fb86e2015-03-20 21:56:59 +1100707int rhashtable_init(struct rhashtable *ht,
708 const struct rhashtable_params *params)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200709{
710 struct bucket_table *tbl;
711 size_t size;
712
713 size = HASH_DEFAULT_SIZE;
714
Herbert Xu31ccde22015-03-24 00:50:21 +1100715 if ((!params->key_len && !params->obj_hashfn) ||
Herbert Xu02fd97c2015-03-20 21:57:00 +1100716 (params->obj_hashfn && !params->obj_cmpfn))
Thomas Graf7e1e7762014-08-02 11:47:44 +0200717 return -EINVAL;
718
Thomas Graff89bd6f2015-01-02 23:00:21 +0100719 if (params->nulls_base && params->nulls_base < (1U << RHT_BASE_SHIFT))
720 return -EINVAL;
721
Thomas Graf7e1e7762014-08-02 11:47:44 +0200722 if (params->nelem_hint)
Ying Xue94000172014-09-03 09:22:36 +0800723 size = rounded_hashtable_size(params);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200724
Thomas Graf97defe12015-01-02 23:00:20 +0100725 memset(ht, 0, sizeof(*ht));
726 mutex_init(&ht->mutex);
Herbert Xuba7c95e2015-03-24 09:53:17 +1100727 spin_lock_init(&ht->lock);
Thomas Graf97defe12015-01-02 23:00:20 +0100728 memcpy(&ht->p, params, sizeof(*params));
729
Thomas Grafa998f712015-03-19 22:31:13 +0000730 if (params->min_size)
731 ht->p.min_size = roundup_pow_of_two(params->min_size);
732
733 if (params->max_size)
734 ht->p.max_size = rounddown_pow_of_two(params->max_size);
735
Herbert Xu488fb86e2015-03-20 21:56:59 +1100736 ht->p.min_size = max(ht->p.min_size, HASH_MIN_SIZE);
Thomas Grafa998f712015-03-19 22:31:13 +0000737
Herbert Xu27ed44a2015-03-24 13:37:30 +1100738 /* The maximum (not average) chain length grows with the
739 * size of the hash table, at a rate of (log N)/(log log N).
740 * The value of 16 is selected so that even if the hash
741 * table grew to 2^32 you would not expect the maximum
742 * chain length to exceed it unless we are under attack
743 * (or extremely unlucky).
744 *
745 * As this limit is only to detect attacks, we don't need
746 * to set it to a lower value as you'd need the chain
747 * length to vastly exceed 16 to have any real effect
748 * on the system.
749 */
Herbert Xuccd57b12015-03-24 00:50:28 +1100750 if (!params->insecure_elasticity)
751 ht->elasticity = 16;
752
Thomas Graf97defe12015-01-02 23:00:20 +0100753 if (params->locks_mul)
754 ht->p.locks_mul = roundup_pow_of_two(params->locks_mul);
755 else
756 ht->p.locks_mul = BUCKET_LOCKS_PER_CPU;
757
Herbert Xu31ccde22015-03-24 00:50:21 +1100758 ht->key_len = ht->p.key_len;
759 if (!params->hashfn) {
760 ht->p.hashfn = jhash;
761
762 if (!(ht->key_len & (sizeof(u32) - 1))) {
763 ht->key_len /= sizeof(u32);
764 ht->p.hashfn = rhashtable_jhash2;
765 }
766 }
767
Herbert Xub9ecfda2015-03-24 00:50:27 +1100768 tbl = bucket_table_alloc(ht, size, GFP_KERNEL);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200769 if (tbl == NULL)
770 return -ENOMEM;
771
Ying Xue545a1482015-01-07 13:41:57 +0800772 atomic_set(&ht->nelems, 0);
Daniel Borkmanna5b68462015-03-12 15:28:40 +0100773
Thomas Graf7e1e7762014-08-02 11:47:44 +0200774 RCU_INIT_POINTER(ht->tbl, tbl);
775
Daniel Borkmann4c4b52d2015-02-25 16:31:54 +0100776 INIT_WORK(&ht->run_work, rht_deferred_worker);
Thomas Graf97defe12015-01-02 23:00:20 +0100777
Thomas Graf7e1e7762014-08-02 11:47:44 +0200778 return 0;
779}
780EXPORT_SYMBOL_GPL(rhashtable_init);
781
782/**
Thomas Graf6b6f3022015-03-24 14:18:20 +0100783 * rhashtable_free_and_destroy - free elements and destroy hash table
Thomas Graf7e1e7762014-08-02 11:47:44 +0200784 * @ht: the hash table to destroy
Thomas Graf6b6f3022015-03-24 14:18:20 +0100785 * @free_fn: callback to release resources of element
786 * @arg: pointer passed to free_fn
Thomas Graf7e1e7762014-08-02 11:47:44 +0200787 *
Thomas Graf6b6f3022015-03-24 14:18:20 +0100788 * Stops an eventual async resize. If defined, invokes free_fn for each
789 * element to releasal resources. Please note that RCU protected
790 * readers may still be accessing the elements. Releasing of resources
791 * must occur in a compatible manner. Then frees the bucket array.
792 *
793 * This function will eventually sleep to wait for an async resize
794 * to complete. The caller is responsible that no further write operations
795 * occurs in parallel.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200796 */
Thomas Graf6b6f3022015-03-24 14:18:20 +0100797void rhashtable_free_and_destroy(struct rhashtable *ht,
798 void (*free_fn)(void *ptr, void *arg),
799 void *arg)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200800{
Thomas Graf6b6f3022015-03-24 14:18:20 +0100801 const struct bucket_table *tbl;
802 unsigned int i;
Thomas Graf97defe12015-01-02 23:00:20 +0100803
Daniel Borkmann4c4b52d2015-02-25 16:31:54 +0100804 cancel_work_sync(&ht->run_work);
Ying Xue57699a42015-01-16 11:13:09 +0800805
Thomas Graf97defe12015-01-02 23:00:20 +0100806 mutex_lock(&ht->mutex);
Thomas Graf6b6f3022015-03-24 14:18:20 +0100807 tbl = rht_dereference(ht->tbl, ht);
808 if (free_fn) {
809 for (i = 0; i < tbl->size; i++) {
810 struct rhash_head *pos, *next;
811
812 for (pos = rht_dereference(tbl->buckets[i], ht),
813 next = !rht_is_a_nulls(pos) ?
814 rht_dereference(pos->next, ht) : NULL;
815 !rht_is_a_nulls(pos);
816 pos = next,
817 next = !rht_is_a_nulls(pos) ?
818 rht_dereference(pos->next, ht) : NULL)
819 free_fn(rht_obj(ht, pos), arg);
820 }
821 }
822
823 bucket_table_free(tbl);
Thomas Graf97defe12015-01-02 23:00:20 +0100824 mutex_unlock(&ht->mutex);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200825}
Thomas Graf6b6f3022015-03-24 14:18:20 +0100826EXPORT_SYMBOL_GPL(rhashtable_free_and_destroy);
827
828void rhashtable_destroy(struct rhashtable *ht)
829{
830 return rhashtable_free_and_destroy(ht, NULL, NULL);
831}
Thomas Graf7e1e7762014-08-02 11:47:44 +0200832EXPORT_SYMBOL_GPL(rhashtable_destroy);