blob: a60a6d335a91a6aa90f019f77062e7be069939fd [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
Herbert Xu07ee0722015-05-15 11:30:47 +080017#include <linux/atomic.h>
Thomas Graf7e1e7762014-08-02 11:47:44 +020018#include <linux/kernel.h>
19#include <linux/init.h>
20#include <linux/log2.h>
Eric Dumazet5beb5c92015-02-26 07:20:34 -080021#include <linux/sched.h>
Thomas Graf7e1e7762014-08-02 11:47:44 +020022#include <linux/slab.h>
23#include <linux/vmalloc.h>
24#include <linux/mm.h>
Daniel Borkmann87545892014-12-10 16:33:11 +010025#include <linux/jhash.h>
Thomas Graf7e1e7762014-08-02 11:47:44 +020026#include <linux/random.h>
27#include <linux/rhashtable.h>
Stephen Rothwell61d7b092015-02-09 14:04:03 +110028#include <linux/err.h>
Hauke Mehrtens6d795412015-06-06 22:07:23 +020029#include <linux/export.h>
Thomas Graf7e1e7762014-08-02 11:47:44 +020030
31#define HASH_DEFAULT_SIZE 64UL
Herbert Xuc2e213c2015-03-18 20:01:16 +110032#define HASH_MIN_SIZE 4U
Thomas Graf97defe12015-01-02 23:00:20 +010033#define BUCKET_LOCKS_PER_CPU 128UL
34
Herbert Xu988dfbd2015-03-10 09:27:55 +110035static u32 head_hashfn(struct rhashtable *ht,
Thomas Graf8d24c0b2015-01-02 23:00:14 +010036 const struct bucket_table *tbl,
37 const struct rhash_head *he)
Thomas Graf7e1e7762014-08-02 11:47:44 +020038{
Herbert Xu02fd97c2015-03-20 21:57:00 +110039 return rht_head_hashfn(ht, tbl, he, ht->p);
Thomas Graf7e1e7762014-08-02 11:47:44 +020040}
41
Thomas Grafa03eaec2015-02-05 02:03:34 +010042#ifdef CONFIG_PROVE_LOCKING
Thomas Grafa03eaec2015-02-05 02:03:34 +010043#define ASSERT_RHT_MUTEX(HT) BUG_ON(!lockdep_rht_mutex_is_held(HT))
Thomas Grafa03eaec2015-02-05 02:03:34 +010044
45int lockdep_rht_mutex_is_held(struct rhashtable *ht)
46{
47 return (debug_locks) ? lockdep_is_held(&ht->mutex) : 1;
48}
49EXPORT_SYMBOL_GPL(lockdep_rht_mutex_is_held);
50
51int lockdep_rht_bucket_is_held(const struct bucket_table *tbl, u32 hash)
52{
Herbert Xu02fd97c2015-03-20 21:57:00 +110053 spinlock_t *lock = rht_bucket_lock(tbl, hash);
Thomas Grafa03eaec2015-02-05 02:03:34 +010054
55 return (debug_locks) ? lockdep_is_held(lock) : 1;
56}
57EXPORT_SYMBOL_GPL(lockdep_rht_bucket_is_held);
58#else
59#define ASSERT_RHT_MUTEX(HT)
Thomas Grafa03eaec2015-02-05 02:03:34 +010060#endif
61
62
Herbert Xub9ecfda2015-03-24 00:50:27 +110063static int alloc_bucket_locks(struct rhashtable *ht, struct bucket_table *tbl,
64 gfp_t gfp)
Thomas Graf97defe12015-01-02 23:00:20 +010065{
66 unsigned int i, size;
67#if defined(CONFIG_PROVE_LOCKING)
68 unsigned int nr_pcpus = 2;
69#else
70 unsigned int nr_pcpus = num_possible_cpus();
71#endif
72
73 nr_pcpus = min_t(unsigned int, nr_pcpus, 32UL);
74 size = roundup_pow_of_two(nr_pcpus * ht->p.locks_mul);
75
Thomas Grafa5ec68e2015-02-05 02:03:32 +010076 /* Never allocate more than 0.5 locks per bucket */
77 size = min_t(unsigned int, size, tbl->size >> 1);
Thomas Graf97defe12015-01-02 23:00:20 +010078
79 if (sizeof(spinlock_t) != 0) {
80#ifdef CONFIG_NUMA
Herbert Xub9ecfda2015-03-24 00:50:27 +110081 if (size * sizeof(spinlock_t) > PAGE_SIZE &&
82 gfp == GFP_KERNEL)
Thomas Graf97defe12015-01-02 23:00:20 +010083 tbl->locks = vmalloc(size * sizeof(spinlock_t));
84 else
85#endif
86 tbl->locks = kmalloc_array(size, sizeof(spinlock_t),
Herbert Xub9ecfda2015-03-24 00:50:27 +110087 gfp);
Thomas Graf97defe12015-01-02 23:00:20 +010088 if (!tbl->locks)
89 return -ENOMEM;
90 for (i = 0; i < size; i++)
91 spin_lock_init(&tbl->locks[i]);
92 }
93 tbl->locks_mask = size - 1;
94
95 return 0;
96}
97
98static void bucket_table_free(const struct bucket_table *tbl)
99{
100 if (tbl)
101 kvfree(tbl->locks);
102
103 kvfree(tbl);
104}
105
Herbert Xu9d901bc2015-03-14 13:57:23 +1100106static void bucket_table_free_rcu(struct rcu_head *head)
107{
108 bucket_table_free(container_of(head, struct bucket_table, rcu));
109}
110
Thomas Graf97defe12015-01-02 23:00:20 +0100111static struct bucket_table *bucket_table_alloc(struct rhashtable *ht,
Herbert Xub9ecfda2015-03-24 00:50:27 +1100112 size_t nbuckets,
113 gfp_t gfp)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200114{
Daniel Borkmanneb6d1ab2015-02-20 00:53:38 +0100115 struct bucket_table *tbl = NULL;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200116 size_t size;
Thomas Graff89bd6f2015-01-02 23:00:21 +0100117 int i;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200118
119 size = sizeof(*tbl) + nbuckets * sizeof(tbl->buckets[0]);
Herbert Xub9ecfda2015-03-24 00:50:27 +1100120 if (size <= (PAGE_SIZE << PAGE_ALLOC_COSTLY_ORDER) ||
121 gfp != GFP_KERNEL)
122 tbl = kzalloc(size, gfp | __GFP_NOWARN | __GFP_NORETRY);
123 if (tbl == NULL && gfp == GFP_KERNEL)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200124 tbl = vzalloc(size);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200125 if (tbl == NULL)
126 return NULL;
127
128 tbl->size = nbuckets;
129
Herbert Xub9ecfda2015-03-24 00:50:27 +1100130 if (alloc_bucket_locks(ht, tbl, gfp) < 0) {
Thomas Graf97defe12015-01-02 23:00:20 +0100131 bucket_table_free(tbl);
132 return NULL;
133 }
Thomas Graf7e1e7762014-08-02 11:47:44 +0200134
Herbert Xueddee5ba2015-03-14 13:57:20 +1100135 INIT_LIST_HEAD(&tbl->walkers);
136
Herbert Xu5269b532015-03-14 13:57:22 +1100137 get_random_bytes(&tbl->hash_rnd, sizeof(tbl->hash_rnd));
138
Thomas Graff89bd6f2015-01-02 23:00:21 +0100139 for (i = 0; i < nbuckets; i++)
140 INIT_RHT_NULLS_HEAD(tbl->buckets[i], ht, i);
141
Thomas Graf97defe12015-01-02 23:00:20 +0100142 return tbl;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200143}
144
Herbert Xub8244782015-03-24 00:50:26 +1100145static struct bucket_table *rhashtable_last_table(struct rhashtable *ht,
146 struct bucket_table *tbl)
147{
148 struct bucket_table *new_tbl;
149
150 do {
151 new_tbl = tbl;
152 tbl = rht_dereference_rcu(tbl->future_tbl, ht);
153 } while (tbl);
154
155 return new_tbl;
156}
157
Thomas Graf299e5c32015-03-24 14:18:17 +0100158static int rhashtable_rehash_one(struct rhashtable *ht, unsigned int old_hash)
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100159{
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100160 struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
Herbert Xub8244782015-03-24 00:50:26 +1100161 struct bucket_table *new_tbl = rhashtable_last_table(ht,
162 rht_dereference_rcu(old_tbl->future_tbl, ht));
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100163 struct rhash_head __rcu **pprev = &old_tbl->buckets[old_hash];
164 int err = -ENOENT;
165 struct rhash_head *head, *next, *entry;
166 spinlock_t *new_bucket_lock;
Thomas Graf299e5c32015-03-24 14:18:17 +0100167 unsigned int new_hash;
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100168
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100169 rht_for_each(entry, old_tbl, old_hash) {
170 err = 0;
171 next = rht_dereference_bucket(entry->next, old_tbl, old_hash);
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100172
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100173 if (rht_is_a_nulls(next))
Thomas Graf7e1e7762014-08-02 11:47:44 +0200174 break;
Thomas Graf97defe12015-01-02 23:00:20 +0100175
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100176 pprev = &entry->next;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200177 }
178
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100179 if (err)
180 goto out;
Thomas Graf97defe12015-01-02 23:00:20 +0100181
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100182 new_hash = head_hashfn(ht, new_tbl, entry);
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100183
Herbert Xu02fd97c2015-03-20 21:57:00 +1100184 new_bucket_lock = rht_bucket_lock(new_tbl, new_hash);
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100185
Herbert Xu8f2484b2015-03-14 13:57:21 +1100186 spin_lock_nested(new_bucket_lock, SINGLE_DEPTH_NESTING);
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100187 head = rht_dereference_bucket(new_tbl->buckets[new_hash],
188 new_tbl, new_hash);
189
190 if (rht_is_a_nulls(head))
191 INIT_RHT_NULLS_HEAD(entry->next, ht, new_hash);
192 else
193 RCU_INIT_POINTER(entry->next, head);
194
195 rcu_assign_pointer(new_tbl->buckets[new_hash], entry);
196 spin_unlock(new_bucket_lock);
197
198 rcu_assign_pointer(*pprev, next);
199
200out:
201 return err;
Thomas Graf97defe12015-01-02 23:00:20 +0100202}
203
Thomas Graf299e5c32015-03-24 14:18:17 +0100204static void rhashtable_rehash_chain(struct rhashtable *ht,
205 unsigned int old_hash)
Thomas Graf97defe12015-01-02 23:00:20 +0100206{
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100207 struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
208 spinlock_t *old_bucket_lock;
Thomas Graf7cd10db2015-02-05 02:03:35 +0100209
Herbert Xu02fd97c2015-03-20 21:57:00 +1100210 old_bucket_lock = rht_bucket_lock(old_tbl, old_hash);
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100211
212 spin_lock_bh(old_bucket_lock);
213 while (!rhashtable_rehash_one(ht, old_hash))
214 ;
Herbert Xu63d512d2015-03-14 13:57:24 +1100215 old_tbl->rehash++;
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100216 spin_unlock_bh(old_bucket_lock);
217}
218
Herbert Xub8244782015-03-24 00:50:26 +1100219static int rhashtable_rehash_attach(struct rhashtable *ht,
220 struct bucket_table *old_tbl,
221 struct bucket_table *new_tbl)
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100222{
Herbert Xub8244782015-03-24 00:50:26 +1100223 /* Protect future_tbl using the first bucket lock. */
224 spin_lock_bh(old_tbl->locks);
225
226 /* Did somebody beat us to it? */
227 if (rcu_access_pointer(old_tbl->future_tbl)) {
228 spin_unlock_bh(old_tbl->locks);
229 return -EEXIST;
230 }
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100231
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100232 /* Make insertions go into the new, empty table right away. Deletions
233 * and lookups will be attempted in both tables until we synchronize.
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100234 */
Herbert Xuc4db8842015-03-14 13:57:25 +1100235 rcu_assign_pointer(old_tbl->future_tbl, new_tbl);
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100236
Herbert Xu9497df82015-03-12 22:07:49 +1100237 /* Ensure the new table is visible to readers. */
238 smp_wmb();
239
Herbert Xub8244782015-03-24 00:50:26 +1100240 spin_unlock_bh(old_tbl->locks);
241
242 return 0;
243}
244
245static int rhashtable_rehash_table(struct rhashtable *ht)
246{
247 struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
248 struct bucket_table *new_tbl;
249 struct rhashtable_walker *walker;
Thomas Graf299e5c32015-03-24 14:18:17 +0100250 unsigned int old_hash;
Herbert Xub8244782015-03-24 00:50:26 +1100251
252 new_tbl = rht_dereference(old_tbl->future_tbl, ht);
253 if (!new_tbl)
254 return 0;
255
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100256 for (old_hash = 0; old_hash < old_tbl->size; old_hash++)
257 rhashtable_rehash_chain(ht, old_hash);
258
259 /* Publish the new table pointer. */
260 rcu_assign_pointer(ht->tbl, new_tbl);
261
Herbert Xuba7c95e2015-03-24 09:53:17 +1100262 spin_lock(&ht->lock);
Herbert Xueddee5ba2015-03-14 13:57:20 +1100263 list_for_each_entry(walker, &old_tbl->walkers, list)
264 walker->tbl = NULL;
Herbert Xuba7c95e2015-03-24 09:53:17 +1100265 spin_unlock(&ht->lock);
Herbert Xueddee5ba2015-03-14 13:57:20 +1100266
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100267 /* Wait for readers. All new readers will see the new
268 * table, and thus no references to the old table will
269 * remain.
270 */
Herbert Xu9d901bc2015-03-14 13:57:23 +1100271 call_rcu(&old_tbl->rcu, bucket_table_free_rcu);
Herbert Xub8244782015-03-24 00:50:26 +1100272
273 return rht_dereference(new_tbl->future_tbl, ht) ? -EAGAIN : 0;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200274}
275
276/**
277 * rhashtable_expand - Expand hash table while allowing concurrent lookups
278 * @ht: the hash table to expand
Thomas Graf7e1e7762014-08-02 11:47:44 +0200279 *
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100280 * A secondary bucket array is allocated and the hash entries are migrated.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200281 *
282 * This function may only be called in a context where it is safe to call
283 * synchronize_rcu(), e.g. not within a rcu_read_lock() section.
284 *
Thomas Graf97defe12015-01-02 23:00:20 +0100285 * The caller must ensure that no concurrent resizing occurs by holding
286 * ht->mutex.
287 *
288 * It is valid to have concurrent insertions and deletions protected by per
289 * bucket locks or concurrent RCU protected lookups and traversals.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200290 */
Herbert Xub8244782015-03-24 00:50:26 +1100291static int rhashtable_expand(struct rhashtable *ht)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200292{
293 struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);
Herbert Xub8244782015-03-24 00:50:26 +1100294 int err;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200295
296 ASSERT_RHT_MUTEX(ht);
297
Herbert Xub8244782015-03-24 00:50:26 +1100298 old_tbl = rhashtable_last_table(ht, old_tbl);
299
Herbert Xub9ecfda2015-03-24 00:50:27 +1100300 new_tbl = bucket_table_alloc(ht, old_tbl->size * 2, GFP_KERNEL);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200301 if (new_tbl == NULL)
302 return -ENOMEM;
303
Herbert Xub8244782015-03-24 00:50:26 +1100304 err = rhashtable_rehash_attach(ht, old_tbl, new_tbl);
305 if (err)
306 bucket_table_free(new_tbl);
307
308 return err;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200309}
Thomas Graf7e1e7762014-08-02 11:47:44 +0200310
311/**
312 * rhashtable_shrink - Shrink hash table while allowing concurrent lookups
313 * @ht: the hash table to shrink
Thomas Graf7e1e7762014-08-02 11:47:44 +0200314 *
Herbert Xu18093d12015-03-24 00:50:25 +1100315 * This function shrinks the hash table to fit, i.e., the smallest
316 * size would not cause it to expand right away automatically.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200317 *
Thomas Graf97defe12015-01-02 23:00:20 +0100318 * The caller must ensure that no concurrent resizing occurs by holding
319 * ht->mutex.
320 *
Thomas Graf7e1e7762014-08-02 11:47:44 +0200321 * The caller must ensure that no concurrent table mutations take place.
322 * It is however valid to have concurrent lookups if they are RCU protected.
Thomas Graf97defe12015-01-02 23:00:20 +0100323 *
324 * It is valid to have concurrent insertions and deletions protected by per
325 * bucket locks or concurrent RCU protected lookups and traversals.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200326 */
Herbert Xub8244782015-03-24 00:50:26 +1100327static int rhashtable_shrink(struct rhashtable *ht)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200328{
Daniel Borkmanna5b68462015-03-12 15:28:40 +0100329 struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);
Thomas Graf299e5c32015-03-24 14:18:17 +0100330 unsigned int size;
Herbert Xub8244782015-03-24 00:50:26 +1100331 int err;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200332
333 ASSERT_RHT_MUTEX(ht);
334
Thomas Graf299e5c32015-03-24 14:18:17 +0100335 size = roundup_pow_of_two(atomic_read(&ht->nelems) * 3 / 2);
Herbert Xu18093d12015-03-24 00:50:25 +1100336 if (size < ht->p.min_size)
337 size = ht->p.min_size;
338
339 if (old_tbl->size <= size)
340 return 0;
341
Herbert Xub8244782015-03-24 00:50:26 +1100342 if (rht_dereference(old_tbl->future_tbl, ht))
343 return -EEXIST;
344
Herbert Xub9ecfda2015-03-24 00:50:27 +1100345 new_tbl = bucket_table_alloc(ht, size, GFP_KERNEL);
Thomas Graf97defe12015-01-02 23:00:20 +0100346 if (new_tbl == NULL)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200347 return -ENOMEM;
348
Herbert Xub8244782015-03-24 00:50:26 +1100349 err = rhashtable_rehash_attach(ht, old_tbl, new_tbl);
350 if (err)
351 bucket_table_free(new_tbl);
352
353 return err;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200354}
Thomas Graf7e1e7762014-08-02 11:47:44 +0200355
Thomas Graf97defe12015-01-02 23:00:20 +0100356static void rht_deferred_worker(struct work_struct *work)
357{
358 struct rhashtable *ht;
359 struct bucket_table *tbl;
Herbert Xub8244782015-03-24 00:50:26 +1100360 int err = 0;
Thomas Graf97defe12015-01-02 23:00:20 +0100361
Ying Xue57699a42015-01-16 11:13:09 +0800362 ht = container_of(work, struct rhashtable, run_work);
Thomas Graf97defe12015-01-02 23:00:20 +0100363 mutex_lock(&ht->mutex);
Herbert Xu28134a52015-02-04 07:33:22 +1100364
Thomas Graf97defe12015-01-02 23:00:20 +0100365 tbl = rht_dereference(ht->tbl, ht);
Herbert Xub8244782015-03-24 00:50:26 +1100366 tbl = rhashtable_last_table(ht, tbl);
Thomas Graf97defe12015-01-02 23:00:20 +0100367
Daniel Borkmanna5b68462015-03-12 15:28:40 +0100368 if (rht_grow_above_75(ht, tbl))
Thomas Graf97defe12015-01-02 23:00:20 +0100369 rhashtable_expand(ht);
Thomas Grafb5e2c152015-03-24 20:42:19 +0000370 else if (ht->p.automatic_shrinking && rht_shrink_below_30(ht, tbl))
Thomas Graf97defe12015-01-02 23:00:20 +0100371 rhashtable_shrink(ht);
Herbert Xub8244782015-03-24 00:50:26 +1100372
373 err = rhashtable_rehash_table(ht);
374
Thomas Graf97defe12015-01-02 23:00:20 +0100375 mutex_unlock(&ht->mutex);
Herbert Xub8244782015-03-24 00:50:26 +1100376
377 if (err)
378 schedule_work(&ht->run_work);
Thomas Graf97defe12015-01-02 23:00:20 +0100379}
380
Herbert Xuccd57b12015-03-24 00:50:28 +1100381static bool rhashtable_check_elasticity(struct rhashtable *ht,
382 struct bucket_table *tbl,
Thomas Graf299e5c32015-03-24 14:18:17 +0100383 unsigned int hash)
Herbert Xuccd57b12015-03-24 00:50:28 +1100384{
Thomas Graf299e5c32015-03-24 14:18:17 +0100385 unsigned int elasticity = ht->elasticity;
Herbert Xuccd57b12015-03-24 00:50:28 +1100386 struct rhash_head *head;
387
388 rht_for_each(head, tbl, hash)
389 if (!--elasticity)
390 return true;
391
392 return false;
393}
394
395int rhashtable_insert_rehash(struct rhashtable *ht)
396{
397 struct bucket_table *old_tbl;
398 struct bucket_table *new_tbl;
399 struct bucket_table *tbl;
400 unsigned int size;
401 int err;
402
403 old_tbl = rht_dereference_rcu(ht->tbl, ht);
404 tbl = rhashtable_last_table(ht, old_tbl);
405
406 size = tbl->size;
407
408 if (rht_grow_above_75(ht, tbl))
409 size *= 2;
Thomas Grafa87b9eb2015-04-22 09:41:46 +0200410 /* Do not schedule more than one rehash */
411 else if (old_tbl != tbl)
Herbert Xuccd57b12015-03-24 00:50:28 +1100412 return -EBUSY;
413
414 new_tbl = bucket_table_alloc(ht, size, GFP_ATOMIC);
Thomas Grafe2307ed2015-04-22 09:41:45 +0200415 if (new_tbl == NULL) {
416 /* Schedule async resize/rehash to try allocation
417 * non-atomic context.
418 */
419 schedule_work(&ht->run_work);
Herbert Xuccd57b12015-03-24 00:50:28 +1100420 return -ENOMEM;
Thomas Grafe2307ed2015-04-22 09:41:45 +0200421 }
Herbert Xuccd57b12015-03-24 00:50:28 +1100422
423 err = rhashtable_rehash_attach(ht, tbl, new_tbl);
424 if (err) {
425 bucket_table_free(new_tbl);
426 if (err == -EEXIST)
427 err = 0;
428 } else
429 schedule_work(&ht->run_work);
430
431 return err;
432}
433EXPORT_SYMBOL_GPL(rhashtable_insert_rehash);
434
Herbert Xu02fd97c2015-03-20 21:57:00 +1100435int rhashtable_insert_slow(struct rhashtable *ht, const void *key,
436 struct rhash_head *obj,
437 struct bucket_table *tbl)
438{
439 struct rhash_head *head;
Thomas Graf299e5c32015-03-24 14:18:17 +0100440 unsigned int hash;
Herbert Xuccd57b12015-03-24 00:50:28 +1100441 int err;
Herbert Xu02fd97c2015-03-20 21:57:00 +1100442
Herbert Xub8244782015-03-24 00:50:26 +1100443 tbl = rhashtable_last_table(ht, tbl);
Herbert Xu02fd97c2015-03-20 21:57:00 +1100444 hash = head_hashfn(ht, tbl, obj);
445 spin_lock_nested(rht_bucket_lock(tbl, hash), SINGLE_DEPTH_NESTING);
446
Herbert Xuccd57b12015-03-24 00:50:28 +1100447 err = -EEXIST;
Herbert Xu02fd97c2015-03-20 21:57:00 +1100448 if (key && rhashtable_lookup_fast(ht, key, ht->p))
449 goto exit;
450
Herbert Xu07ee0722015-05-15 11:30:47 +0800451 err = -E2BIG;
452 if (unlikely(rht_grow_above_max(ht, tbl)))
453 goto exit;
454
Herbert Xuccd57b12015-03-24 00:50:28 +1100455 err = -EAGAIN;
456 if (rhashtable_check_elasticity(ht, tbl, hash) ||
457 rht_grow_above_100(ht, tbl))
458 goto exit;
459
Herbert Xu02fd97c2015-03-20 21:57:00 +1100460 err = 0;
461
462 head = rht_dereference_bucket(tbl->buckets[hash], tbl, hash);
463
464 RCU_INIT_POINTER(obj->next, head);
465
466 rcu_assign_pointer(tbl->buckets[hash], obj);
467
468 atomic_inc(&ht->nelems);
469
470exit:
471 spin_unlock(rht_bucket_lock(tbl, hash));
472
473 return err;
474}
475EXPORT_SYMBOL_GPL(rhashtable_insert_slow);
476
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100477/**
478 * rhashtable_walk_init - Initialise an iterator
479 * @ht: Table to walk over
480 * @iter: Hash table Iterator
481 *
482 * This function prepares a hash table walk.
483 *
484 * Note that if you restart a walk after rhashtable_walk_stop you
485 * may see the same object twice. Also, you may miss objects if
486 * there are removals in between rhashtable_walk_stop and the next
487 * call to rhashtable_walk_start.
488 *
489 * For a completely stable walk you should construct your own data
490 * structure outside the hash table.
491 *
492 * This function may sleep so you must not call it from interrupt
493 * context or with spin locks held.
494 *
495 * You must call rhashtable_walk_exit if this function returns
496 * successfully.
497 */
498int rhashtable_walk_init(struct rhashtable *ht, struct rhashtable_iter *iter)
499{
500 iter->ht = ht;
501 iter->p = NULL;
502 iter->slot = 0;
503 iter->skip = 0;
504
505 iter->walker = kmalloc(sizeof(*iter->walker), GFP_KERNEL);
506 if (!iter->walker)
507 return -ENOMEM;
508
509 mutex_lock(&ht->mutex);
Herbert Xueddee5ba2015-03-14 13:57:20 +1100510 iter->walker->tbl = rht_dereference(ht->tbl, ht);
511 list_add(&iter->walker->list, &iter->walker->tbl->walkers);
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100512 mutex_unlock(&ht->mutex);
513
514 return 0;
515}
516EXPORT_SYMBOL_GPL(rhashtable_walk_init);
517
518/**
519 * rhashtable_walk_exit - Free an iterator
520 * @iter: Hash table Iterator
521 *
522 * This function frees resources allocated by rhashtable_walk_init.
523 */
524void rhashtable_walk_exit(struct rhashtable_iter *iter)
525{
526 mutex_lock(&iter->ht->mutex);
Herbert Xueddee5ba2015-03-14 13:57:20 +1100527 if (iter->walker->tbl)
528 list_del(&iter->walker->list);
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100529 mutex_unlock(&iter->ht->mutex);
530 kfree(iter->walker);
531}
532EXPORT_SYMBOL_GPL(rhashtable_walk_exit);
533
534/**
535 * rhashtable_walk_start - Start a hash table walk
536 * @iter: Hash table iterator
537 *
538 * Start a hash table walk. Note that we take the RCU lock in all
539 * cases including when we return an error. So you must always call
540 * rhashtable_walk_stop to clean up.
541 *
542 * Returns zero if successful.
543 *
544 * Returns -EAGAIN if resize event occured. Note that the iterator
545 * will rewind back to the beginning and you may use it immediately
546 * by calling rhashtable_walk_next.
547 */
548int rhashtable_walk_start(struct rhashtable_iter *iter)
Thomas Grafdb4374f2015-03-16 10:42:27 +0100549 __acquires(RCU)
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100550{
Herbert Xueddee5ba2015-03-14 13:57:20 +1100551 struct rhashtable *ht = iter->ht;
552
553 mutex_lock(&ht->mutex);
554
555 if (iter->walker->tbl)
556 list_del(&iter->walker->list);
557
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100558 rcu_read_lock();
559
Herbert Xueddee5ba2015-03-14 13:57:20 +1100560 mutex_unlock(&ht->mutex);
561
562 if (!iter->walker->tbl) {
563 iter->walker->tbl = rht_dereference_rcu(ht->tbl, ht);
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100564 return -EAGAIN;
565 }
566
567 return 0;
568}
569EXPORT_SYMBOL_GPL(rhashtable_walk_start);
570
571/**
572 * rhashtable_walk_next - Return the next object and advance the iterator
573 * @iter: Hash table iterator
574 *
575 * Note that you must call rhashtable_walk_stop when you are finished
576 * with the walk.
577 *
578 * Returns the next object or NULL when the end of the table is reached.
579 *
580 * Returns -EAGAIN if resize event occured. Note that the iterator
581 * will rewind back to the beginning and you may continue to use it.
582 */
583void *rhashtable_walk_next(struct rhashtable_iter *iter)
584{
Herbert Xueddee5ba2015-03-14 13:57:20 +1100585 struct bucket_table *tbl = iter->walker->tbl;
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100586 struct rhashtable *ht = iter->ht;
587 struct rhash_head *p = iter->p;
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100588
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100589 if (p) {
590 p = rht_dereference_bucket_rcu(p->next, tbl, iter->slot);
591 goto next;
592 }
593
594 for (; iter->slot < tbl->size; iter->slot++) {
595 int skip = iter->skip;
596
597 rht_for_each_rcu(p, tbl, iter->slot) {
598 if (!skip)
599 break;
600 skip--;
601 }
602
603next:
604 if (!rht_is_a_nulls(p)) {
605 iter->skip++;
606 iter->p = p;
Thomas Grafc936a792015-05-05 02:22:53 +0200607 return rht_obj(ht, p);
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100608 }
609
610 iter->skip = 0;
611 }
612
Herbert Xud88252f2015-03-24 00:50:19 +1100613 /* Ensure we see any new tables. */
614 smp_rmb();
615
Herbert Xuc4db8842015-03-14 13:57:25 +1100616 iter->walker->tbl = rht_dereference_rcu(tbl->future_tbl, ht);
617 if (iter->walker->tbl) {
Herbert Xueddee5ba2015-03-14 13:57:20 +1100618 iter->slot = 0;
619 iter->skip = 0;
620 return ERR_PTR(-EAGAIN);
621 }
622
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100623 iter->p = NULL;
624
Thomas Grafc936a792015-05-05 02:22:53 +0200625 return NULL;
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100626}
627EXPORT_SYMBOL_GPL(rhashtable_walk_next);
628
629/**
630 * rhashtable_walk_stop - Finish a hash table walk
631 * @iter: Hash table iterator
632 *
633 * Finish a hash table walk.
634 */
635void rhashtable_walk_stop(struct rhashtable_iter *iter)
Thomas Grafdb4374f2015-03-16 10:42:27 +0100636 __releases(RCU)
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100637{
Herbert Xueddee5ba2015-03-14 13:57:20 +1100638 struct rhashtable *ht;
639 struct bucket_table *tbl = iter->walker->tbl;
640
Herbert Xueddee5ba2015-03-14 13:57:20 +1100641 if (!tbl)
Herbert Xu963ecbd2015-03-15 21:12:04 +1100642 goto out;
Herbert Xueddee5ba2015-03-14 13:57:20 +1100643
644 ht = iter->ht;
645
Herbert Xuba7c95e2015-03-24 09:53:17 +1100646 spin_lock(&ht->lock);
Herbert Xuc4db8842015-03-14 13:57:25 +1100647 if (tbl->rehash < tbl->size)
Herbert Xueddee5ba2015-03-14 13:57:20 +1100648 list_add(&iter->walker->list, &tbl->walkers);
649 else
650 iter->walker->tbl = NULL;
Herbert Xuba7c95e2015-03-24 09:53:17 +1100651 spin_unlock(&ht->lock);
Herbert Xueddee5ba2015-03-14 13:57:20 +1100652
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100653 iter->p = NULL;
Herbert Xu963ecbd2015-03-15 21:12:04 +1100654
655out:
656 rcu_read_unlock();
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100657}
658EXPORT_SYMBOL_GPL(rhashtable_walk_stop);
659
Herbert Xu488fb86e2015-03-20 21:56:59 +1100660static size_t rounded_hashtable_size(const struct rhashtable_params *params)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200661{
Ying Xue94000172014-09-03 09:22:36 +0800662 return max(roundup_pow_of_two(params->nelem_hint * 4 / 3),
Herbert Xue2e21c12015-03-18 20:01:21 +1100663 (unsigned long)params->min_size);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200664}
665
Herbert Xu31ccde22015-03-24 00:50:21 +1100666static u32 rhashtable_jhash2(const void *key, u32 length, u32 seed)
667{
668 return jhash2(key, length, seed);
669}
670
Thomas Graf7e1e7762014-08-02 11:47:44 +0200671/**
672 * rhashtable_init - initialize a new hash table
673 * @ht: hash table to be initialized
674 * @params: configuration parameters
675 *
676 * Initializes a new hash table based on the provided configuration
677 * parameters. A table can be configured either with a variable or
678 * fixed length key:
679 *
680 * Configuration Example 1: Fixed length keys
681 * struct test_obj {
682 * int key;
683 * void * my_member;
684 * struct rhash_head node;
685 * };
686 *
687 * struct rhashtable_params params = {
688 * .head_offset = offsetof(struct test_obj, node),
689 * .key_offset = offsetof(struct test_obj, key),
690 * .key_len = sizeof(int),
Daniel Borkmann87545892014-12-10 16:33:11 +0100691 * .hashfn = jhash,
Thomas Graff89bd6f2015-01-02 23:00:21 +0100692 * .nulls_base = (1U << RHT_BASE_SHIFT),
Thomas Graf7e1e7762014-08-02 11:47:44 +0200693 * };
694 *
695 * Configuration Example 2: Variable length keys
696 * struct test_obj {
697 * [...]
698 * struct rhash_head node;
699 * };
700 *
Patrick McHardy49f7b332015-03-25 13:07:45 +0000701 * u32 my_hash_fn(const void *data, u32 len, u32 seed)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200702 * {
703 * struct test_obj *obj = data;
704 *
705 * return [... hash ...];
706 * }
707 *
708 * struct rhashtable_params params = {
709 * .head_offset = offsetof(struct test_obj, node),
Daniel Borkmann87545892014-12-10 16:33:11 +0100710 * .hashfn = jhash,
Thomas Graf7e1e7762014-08-02 11:47:44 +0200711 * .obj_hashfn = my_hash_fn,
Thomas Graf7e1e7762014-08-02 11:47:44 +0200712 * };
713 */
Herbert Xu488fb86e2015-03-20 21:56:59 +1100714int rhashtable_init(struct rhashtable *ht,
715 const struct rhashtable_params *params)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200716{
717 struct bucket_table *tbl;
718 size_t size;
719
720 size = HASH_DEFAULT_SIZE;
721
Herbert Xu31ccde22015-03-24 00:50:21 +1100722 if ((!params->key_len && !params->obj_hashfn) ||
Herbert Xu02fd97c2015-03-20 21:57:00 +1100723 (params->obj_hashfn && !params->obj_cmpfn))
Thomas Graf7e1e7762014-08-02 11:47:44 +0200724 return -EINVAL;
725
Thomas Graff89bd6f2015-01-02 23:00:21 +0100726 if (params->nulls_base && params->nulls_base < (1U << RHT_BASE_SHIFT))
727 return -EINVAL;
728
Thomas Graf7e1e7762014-08-02 11:47:44 +0200729 if (params->nelem_hint)
Ying Xue94000172014-09-03 09:22:36 +0800730 size = rounded_hashtable_size(params);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200731
Thomas Graf97defe12015-01-02 23:00:20 +0100732 memset(ht, 0, sizeof(*ht));
733 mutex_init(&ht->mutex);
Herbert Xuba7c95e2015-03-24 09:53:17 +1100734 spin_lock_init(&ht->lock);
Thomas Graf97defe12015-01-02 23:00:20 +0100735 memcpy(&ht->p, params, sizeof(*params));
736
Thomas Grafa998f712015-03-19 22:31:13 +0000737 if (params->min_size)
738 ht->p.min_size = roundup_pow_of_two(params->min_size);
739
740 if (params->max_size)
741 ht->p.max_size = rounddown_pow_of_two(params->max_size);
742
Herbert Xu07ee0722015-05-15 11:30:47 +0800743 if (params->insecure_max_entries)
744 ht->p.insecure_max_entries =
745 rounddown_pow_of_two(params->insecure_max_entries);
746 else
747 ht->p.insecure_max_entries = ht->p.max_size * 2;
748
Herbert Xu488fb86e2015-03-20 21:56:59 +1100749 ht->p.min_size = max(ht->p.min_size, HASH_MIN_SIZE);
Thomas Grafa998f712015-03-19 22:31:13 +0000750
Herbert Xu27ed44a2015-03-24 13:37:30 +1100751 /* The maximum (not average) chain length grows with the
752 * size of the hash table, at a rate of (log N)/(log log N).
753 * The value of 16 is selected so that even if the hash
754 * table grew to 2^32 you would not expect the maximum
755 * chain length to exceed it unless we are under attack
756 * (or extremely unlucky).
757 *
758 * As this limit is only to detect attacks, we don't need
759 * to set it to a lower value as you'd need the chain
760 * length to vastly exceed 16 to have any real effect
761 * on the system.
762 */
Herbert Xuccd57b12015-03-24 00:50:28 +1100763 if (!params->insecure_elasticity)
764 ht->elasticity = 16;
765
Thomas Graf97defe12015-01-02 23:00:20 +0100766 if (params->locks_mul)
767 ht->p.locks_mul = roundup_pow_of_two(params->locks_mul);
768 else
769 ht->p.locks_mul = BUCKET_LOCKS_PER_CPU;
770
Herbert Xu31ccde22015-03-24 00:50:21 +1100771 ht->key_len = ht->p.key_len;
772 if (!params->hashfn) {
773 ht->p.hashfn = jhash;
774
775 if (!(ht->key_len & (sizeof(u32) - 1))) {
776 ht->key_len /= sizeof(u32);
777 ht->p.hashfn = rhashtable_jhash2;
778 }
779 }
780
Herbert Xub9ecfda2015-03-24 00:50:27 +1100781 tbl = bucket_table_alloc(ht, size, GFP_KERNEL);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200782 if (tbl == NULL)
783 return -ENOMEM;
784
Ying Xue545a1482015-01-07 13:41:57 +0800785 atomic_set(&ht->nelems, 0);
Daniel Borkmanna5b68462015-03-12 15:28:40 +0100786
Thomas Graf7e1e7762014-08-02 11:47:44 +0200787 RCU_INIT_POINTER(ht->tbl, tbl);
788
Daniel Borkmann4c4b52d2015-02-25 16:31:54 +0100789 INIT_WORK(&ht->run_work, rht_deferred_worker);
Thomas Graf97defe12015-01-02 23:00:20 +0100790
Thomas Graf7e1e7762014-08-02 11:47:44 +0200791 return 0;
792}
793EXPORT_SYMBOL_GPL(rhashtable_init);
794
795/**
Thomas Graf6b6f3022015-03-24 14:18:20 +0100796 * rhashtable_free_and_destroy - free elements and destroy hash table
Thomas Graf7e1e7762014-08-02 11:47:44 +0200797 * @ht: the hash table to destroy
Thomas Graf6b6f3022015-03-24 14:18:20 +0100798 * @free_fn: callback to release resources of element
799 * @arg: pointer passed to free_fn
Thomas Graf7e1e7762014-08-02 11:47:44 +0200800 *
Thomas Graf6b6f3022015-03-24 14:18:20 +0100801 * Stops an eventual async resize. If defined, invokes free_fn for each
802 * element to releasal resources. Please note that RCU protected
803 * readers may still be accessing the elements. Releasing of resources
804 * must occur in a compatible manner. Then frees the bucket array.
805 *
806 * This function will eventually sleep to wait for an async resize
807 * to complete. The caller is responsible that no further write operations
808 * occurs in parallel.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200809 */
Thomas Graf6b6f3022015-03-24 14:18:20 +0100810void rhashtable_free_and_destroy(struct rhashtable *ht,
811 void (*free_fn)(void *ptr, void *arg),
812 void *arg)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200813{
Thomas Graf6b6f3022015-03-24 14:18:20 +0100814 const struct bucket_table *tbl;
815 unsigned int i;
Thomas Graf97defe12015-01-02 23:00:20 +0100816
Daniel Borkmann4c4b52d2015-02-25 16:31:54 +0100817 cancel_work_sync(&ht->run_work);
Ying Xue57699a42015-01-16 11:13:09 +0800818
Thomas Graf97defe12015-01-02 23:00:20 +0100819 mutex_lock(&ht->mutex);
Thomas Graf6b6f3022015-03-24 14:18:20 +0100820 tbl = rht_dereference(ht->tbl, ht);
821 if (free_fn) {
822 for (i = 0; i < tbl->size; i++) {
823 struct rhash_head *pos, *next;
824
825 for (pos = rht_dereference(tbl->buckets[i], ht),
826 next = !rht_is_a_nulls(pos) ?
827 rht_dereference(pos->next, ht) : NULL;
828 !rht_is_a_nulls(pos);
829 pos = next,
830 next = !rht_is_a_nulls(pos) ?
831 rht_dereference(pos->next, ht) : NULL)
832 free_fn(rht_obj(ht, pos), arg);
833 }
834 }
835
836 bucket_table_free(tbl);
Thomas Graf97defe12015-01-02 23:00:20 +0100837 mutex_unlock(&ht->mutex);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200838}
Thomas Graf6b6f3022015-03-24 14:18:20 +0100839EXPORT_SYMBOL_GPL(rhashtable_free_and_destroy);
840
841void rhashtable_destroy(struct rhashtable *ht)
842{
843 return rhashtable_free_and_destroy(ht, NULL, NULL);
844}
Thomas Graf7e1e7762014-08-02 11:47:44 +0200845EXPORT_SYMBOL_GPL(rhashtable_destroy);