blob: 101dac085c62e532d843b74a5856ba35b4b336bb [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
Florian Westphal4cf0b352016-08-12 12:03:52 +020033#define BUCKET_LOCKS_PER_CPU 32UL
Thomas Graf97defe12015-01-02 23:00:20 +010034
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
Florian Westphal4cf0b352016-08-12 12:03:52 +020073 nr_pcpus = min_t(unsigned int, nr_pcpus, 64UL);
Thomas Graf97defe12015-01-02 23:00:20 +010074 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) {
Eric Dumazet9dbeea72016-08-26 08:51:39 -070080 tbl->locks = NULL;
Thomas Graf97defe12015-01-02 23:00:20 +010081#ifdef CONFIG_NUMA
Herbert Xub9ecfda2015-03-24 00:50:27 +110082 if (size * sizeof(spinlock_t) > PAGE_SIZE &&
83 gfp == GFP_KERNEL)
Thomas Graf97defe12015-01-02 23:00:20 +010084 tbl->locks = vmalloc(size * sizeof(spinlock_t));
Thomas Graf97defe12015-01-02 23:00:20 +010085#endif
Florian Westphal4cf0b352016-08-12 12:03:52 +020086 if (gfp != GFP_KERNEL)
87 gfp |= __GFP_NOWARN | __GFP_NORETRY;
88
Eric Dumazet9dbeea72016-08-26 08:51:39 -070089 if (!tbl->locks)
90 tbl->locks = kmalloc_array(size, sizeof(spinlock_t),
91 gfp);
Thomas Graf97defe12015-01-02 23:00:20 +010092 if (!tbl->locks)
93 return -ENOMEM;
94 for (i = 0; i < size; i++)
95 spin_lock_init(&tbl->locks[i]);
96 }
97 tbl->locks_mask = size - 1;
98
99 return 0;
100}
101
102static void bucket_table_free(const struct bucket_table *tbl)
103{
104 if (tbl)
105 kvfree(tbl->locks);
106
107 kvfree(tbl);
108}
109
Herbert Xu9d901bc2015-03-14 13:57:23 +1100110static void bucket_table_free_rcu(struct rcu_head *head)
111{
112 bucket_table_free(container_of(head, struct bucket_table, rcu));
113}
114
Thomas Graf97defe12015-01-02 23:00:20 +0100115static struct bucket_table *bucket_table_alloc(struct rhashtable *ht,
Herbert Xub9ecfda2015-03-24 00:50:27 +1100116 size_t nbuckets,
117 gfp_t gfp)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200118{
Daniel Borkmanneb6d1ab2015-02-20 00:53:38 +0100119 struct bucket_table *tbl = NULL;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200120 size_t size;
Thomas Graff89bd6f2015-01-02 23:00:21 +0100121 int i;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200122
123 size = sizeof(*tbl) + nbuckets * sizeof(tbl->buckets[0]);
Herbert Xub9ecfda2015-03-24 00:50:27 +1100124 if (size <= (PAGE_SIZE << PAGE_ALLOC_COSTLY_ORDER) ||
125 gfp != GFP_KERNEL)
126 tbl = kzalloc(size, gfp | __GFP_NOWARN | __GFP_NORETRY);
127 if (tbl == NULL && gfp == GFP_KERNEL)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200128 tbl = vzalloc(size);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200129 if (tbl == NULL)
130 return NULL;
131
132 tbl->size = nbuckets;
133
Herbert Xub9ecfda2015-03-24 00:50:27 +1100134 if (alloc_bucket_locks(ht, tbl, gfp) < 0) {
Thomas Graf97defe12015-01-02 23:00:20 +0100135 bucket_table_free(tbl);
136 return NULL;
137 }
Thomas Graf7e1e7762014-08-02 11:47:44 +0200138
Herbert Xueddee5ba2015-03-14 13:57:20 +1100139 INIT_LIST_HEAD(&tbl->walkers);
140
Herbert Xu5269b532015-03-14 13:57:22 +1100141 get_random_bytes(&tbl->hash_rnd, sizeof(tbl->hash_rnd));
142
Thomas Graff89bd6f2015-01-02 23:00:21 +0100143 for (i = 0; i < nbuckets; i++)
144 INIT_RHT_NULLS_HEAD(tbl->buckets[i], ht, i);
145
Thomas Graf97defe12015-01-02 23:00:20 +0100146 return tbl;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200147}
148
Herbert Xub8244782015-03-24 00:50:26 +1100149static struct bucket_table *rhashtable_last_table(struct rhashtable *ht,
150 struct bucket_table *tbl)
151{
152 struct bucket_table *new_tbl;
153
154 do {
155 new_tbl = tbl;
156 tbl = rht_dereference_rcu(tbl->future_tbl, ht);
157 } while (tbl);
158
159 return new_tbl;
160}
161
Thomas Graf299e5c32015-03-24 14:18:17 +0100162static int rhashtable_rehash_one(struct rhashtable *ht, unsigned int old_hash)
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100163{
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100164 struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
Herbert Xub8244782015-03-24 00:50:26 +1100165 struct bucket_table *new_tbl = rhashtable_last_table(ht,
166 rht_dereference_rcu(old_tbl->future_tbl, ht));
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100167 struct rhash_head __rcu **pprev = &old_tbl->buckets[old_hash];
168 int err = -ENOENT;
169 struct rhash_head *head, *next, *entry;
170 spinlock_t *new_bucket_lock;
Thomas Graf299e5c32015-03-24 14:18:17 +0100171 unsigned int new_hash;
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100172
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100173 rht_for_each(entry, old_tbl, old_hash) {
174 err = 0;
175 next = rht_dereference_bucket(entry->next, old_tbl, old_hash);
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100176
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100177 if (rht_is_a_nulls(next))
Thomas Graf7e1e7762014-08-02 11:47:44 +0200178 break;
Thomas Graf97defe12015-01-02 23:00:20 +0100179
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100180 pprev = &entry->next;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200181 }
182
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100183 if (err)
184 goto out;
Thomas Graf97defe12015-01-02 23:00:20 +0100185
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100186 new_hash = head_hashfn(ht, new_tbl, entry);
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100187
Herbert Xu02fd97c2015-03-20 21:57:00 +1100188 new_bucket_lock = rht_bucket_lock(new_tbl, new_hash);
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100189
Herbert Xu8f2484b2015-03-14 13:57:21 +1100190 spin_lock_nested(new_bucket_lock, SINGLE_DEPTH_NESTING);
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100191 head = rht_dereference_bucket(new_tbl->buckets[new_hash],
192 new_tbl, new_hash);
193
Dmitriy Vyukov7def0f92015-09-22 10:51:52 +0200194 RCU_INIT_POINTER(entry->next, head);
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100195
196 rcu_assign_pointer(new_tbl->buckets[new_hash], entry);
197 spin_unlock(new_bucket_lock);
198
199 rcu_assign_pointer(*pprev, next);
200
201out:
202 return err;
Thomas Graf97defe12015-01-02 23:00:20 +0100203}
204
Thomas Graf299e5c32015-03-24 14:18:17 +0100205static void rhashtable_rehash_chain(struct rhashtable *ht,
206 unsigned int old_hash)
Thomas Graf97defe12015-01-02 23:00:20 +0100207{
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100208 struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
209 spinlock_t *old_bucket_lock;
Thomas Graf7cd10db2015-02-05 02:03:35 +0100210
Herbert Xu02fd97c2015-03-20 21:57:00 +1100211 old_bucket_lock = rht_bucket_lock(old_tbl, old_hash);
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100212
213 spin_lock_bh(old_bucket_lock);
214 while (!rhashtable_rehash_one(ht, old_hash))
215 ;
Herbert Xu63d512d2015-03-14 13:57:24 +1100216 old_tbl->rehash++;
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100217 spin_unlock_bh(old_bucket_lock);
218}
219
Herbert Xub8244782015-03-24 00:50:26 +1100220static int rhashtable_rehash_attach(struct rhashtable *ht,
221 struct bucket_table *old_tbl,
222 struct bucket_table *new_tbl)
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100223{
Herbert Xub8244782015-03-24 00:50:26 +1100224 /* Protect future_tbl using the first bucket lock. */
225 spin_lock_bh(old_tbl->locks);
226
227 /* Did somebody beat us to it? */
228 if (rcu_access_pointer(old_tbl->future_tbl)) {
229 spin_unlock_bh(old_tbl->locks);
230 return -EEXIST;
231 }
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100232
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100233 /* Make insertions go into the new, empty table right away. Deletions
234 * and lookups will be attempted in both tables until we synchronize.
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100235 */
Herbert Xuc4db8842015-03-14 13:57:25 +1100236 rcu_assign_pointer(old_tbl->future_tbl, new_tbl);
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100237
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);
Vegard Nossum12311952016-08-12 20:10:44 +0200328 unsigned int nelems = atomic_read(&ht->nelems);
329 unsigned int size = 0;
Herbert Xub8244782015-03-24 00:50:26 +1100330 int err;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200331
332 ASSERT_RHT_MUTEX(ht);
333
Vegard Nossum12311952016-08-12 20:10:44 +0200334 if (nelems)
335 size = roundup_pow_of_two(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 Xuca268932016-09-19 19:00:09 +0800381static int rhashtable_insert_rehash(struct rhashtable *ht,
382 struct bucket_table *tbl)
Herbert Xuccd57b12015-03-24 00:50:28 +1100383{
384 struct bucket_table *old_tbl;
385 struct bucket_table *new_tbl;
Herbert Xuccd57b12015-03-24 00:50:28 +1100386 unsigned int size;
387 int err;
388
389 old_tbl = rht_dereference_rcu(ht->tbl, ht);
Herbert Xuccd57b12015-03-24 00:50:28 +1100390
391 size = tbl->size;
392
Herbert Xu3cf92222015-12-03 20:41:29 +0800393 err = -EBUSY;
394
Herbert Xuccd57b12015-03-24 00:50:28 +1100395 if (rht_grow_above_75(ht, tbl))
396 size *= 2;
Thomas Grafa87b9eb2015-04-22 09:41:46 +0200397 /* Do not schedule more than one rehash */
398 else if (old_tbl != tbl)
Herbert Xu3cf92222015-12-03 20:41:29 +0800399 goto fail;
400
401 err = -ENOMEM;
Herbert Xuccd57b12015-03-24 00:50:28 +1100402
403 new_tbl = bucket_table_alloc(ht, size, GFP_ATOMIC);
Herbert Xu3cf92222015-12-03 20:41:29 +0800404 if (new_tbl == NULL)
405 goto fail;
Herbert Xuccd57b12015-03-24 00:50:28 +1100406
407 err = rhashtable_rehash_attach(ht, tbl, new_tbl);
408 if (err) {
409 bucket_table_free(new_tbl);
410 if (err == -EEXIST)
411 err = 0;
412 } else
413 schedule_work(&ht->run_work);
414
415 return err;
Herbert Xu3cf92222015-12-03 20:41:29 +0800416
417fail:
418 /* Do not fail the insert if someone else did a rehash. */
419 if (likely(rcu_dereference_raw(tbl->future_tbl)))
420 return 0;
421
422 /* Schedule async rehash to retry allocation in process context. */
423 if (err == -ENOMEM)
424 schedule_work(&ht->run_work);
425
426 return err;
Herbert Xuccd57b12015-03-24 00:50:28 +1100427}
Herbert Xuccd57b12015-03-24 00:50:28 +1100428
Herbert Xuca268932016-09-19 19:00:09 +0800429static void *rhashtable_lookup_one(struct rhashtable *ht,
430 struct bucket_table *tbl, unsigned int hash,
431 const void *key, struct rhash_head *obj)
Herbert Xu02fd97c2015-03-20 21:57:00 +1100432{
Herbert Xuca268932016-09-19 19:00:09 +0800433 struct rhashtable_compare_arg arg = {
434 .ht = ht,
435 .key = key,
436 };
437 struct rhash_head __rcu **pprev;
Herbert Xu02fd97c2015-03-20 21:57:00 +1100438 struct rhash_head *head;
Herbert Xuca268932016-09-19 19:00:09 +0800439 int elasticity;
Herbert Xu02fd97c2015-03-20 21:57:00 +1100440
Herbert Xuca268932016-09-19 19:00:09 +0800441 elasticity = ht->elasticity;
442 pprev = &tbl->buckets[hash];
443 rht_for_each(head, tbl, hash) {
444 struct rhlist_head *list;
445 struct rhlist_head *plist;
Herbert Xu02fd97c2015-03-20 21:57:00 +1100446
Herbert Xuca268932016-09-19 19:00:09 +0800447 elasticity--;
448 if (!key ||
449 (ht->p.obj_cmpfn ?
450 ht->p.obj_cmpfn(&arg, rht_obj(ht, head)) :
Paul Blakeyad621702018-03-04 17:29:48 +0200451 rhashtable_compare(&arg, rht_obj(ht, head)))) {
452 pprev = &head->next;
Herbert Xuca268932016-09-19 19:00:09 +0800453 continue;
Paul Blakeyad621702018-03-04 17:29:48 +0200454 }
Herbert Xuca268932016-09-19 19:00:09 +0800455
456 if (!ht->rhlist)
457 return rht_obj(ht, head);
458
459 list = container_of(obj, struct rhlist_head, rhead);
460 plist = container_of(head, struct rhlist_head, rhead);
461
462 RCU_INIT_POINTER(list->next, plist);
463 head = rht_dereference_bucket(head->next, tbl, hash);
464 RCU_INIT_POINTER(list->rhead.next, head);
465 rcu_assign_pointer(*pprev, obj);
466
467 return NULL;
Pablo Neira Ayuso5ca8cc52016-08-24 12:31:31 +0200468 }
Herbert Xu02fd97c2015-03-20 21:57:00 +1100469
Herbert Xuca268932016-09-19 19:00:09 +0800470 if (elasticity <= 0)
471 return ERR_PTR(-EAGAIN);
472
473 return ERR_PTR(-ENOENT);
474}
475
476static struct bucket_table *rhashtable_insert_one(struct rhashtable *ht,
477 struct bucket_table *tbl,
478 unsigned int hash,
479 struct rhash_head *obj,
480 void *data)
481{
482 struct bucket_table *new_tbl;
483 struct rhash_head *head;
484
485 if (!IS_ERR_OR_NULL(data))
486 return ERR_PTR(-EEXIST);
487
488 if (PTR_ERR(data) != -EAGAIN && PTR_ERR(data) != -ENOENT)
489 return ERR_CAST(data);
490
491 new_tbl = rcu_dereference(tbl->future_tbl);
492 if (new_tbl)
493 return new_tbl;
494
495 if (PTR_ERR(data) != -ENOENT)
496 return ERR_CAST(data);
497
Herbert Xu07ee0722015-05-15 11:30:47 +0800498 if (unlikely(rht_grow_above_max(ht, tbl)))
Herbert Xuca268932016-09-19 19:00:09 +0800499 return ERR_PTR(-E2BIG);
Herbert Xu07ee0722015-05-15 11:30:47 +0800500
Herbert Xuca268932016-09-19 19:00:09 +0800501 if (unlikely(rht_grow_above_100(ht, tbl)))
502 return ERR_PTR(-EAGAIN);
Herbert Xu02fd97c2015-03-20 21:57:00 +1100503
504 head = rht_dereference_bucket(tbl->buckets[hash], tbl, hash);
505
506 RCU_INIT_POINTER(obj->next, head);
Herbert Xuca268932016-09-19 19:00:09 +0800507 if (ht->rhlist) {
508 struct rhlist_head *list;
509
510 list = container_of(obj, struct rhlist_head, rhead);
511 RCU_INIT_POINTER(list->next, NULL);
512 }
Herbert Xu02fd97c2015-03-20 21:57:00 +1100513
514 rcu_assign_pointer(tbl->buckets[hash], obj);
515
516 atomic_inc(&ht->nelems);
Herbert Xuca268932016-09-19 19:00:09 +0800517 if (rht_grow_above_75(ht, tbl))
518 schedule_work(&ht->run_work);
Herbert Xu02fd97c2015-03-20 21:57:00 +1100519
Herbert Xuca268932016-09-19 19:00:09 +0800520 return NULL;
521}
Herbert Xu02fd97c2015-03-20 21:57:00 +1100522
Herbert Xuca268932016-09-19 19:00:09 +0800523static void *rhashtable_try_insert(struct rhashtable *ht, const void *key,
524 struct rhash_head *obj)
525{
526 struct bucket_table *new_tbl;
527 struct bucket_table *tbl;
528 unsigned int hash;
529 spinlock_t *lock;
530 void *data;
531
532 tbl = rcu_dereference(ht->tbl);
533
534 /* All insertions must grab the oldest table containing
535 * the hashed bucket that is yet to be rehashed.
536 */
537 for (;;) {
538 hash = rht_head_hashfn(ht, tbl, obj, ht->p);
539 lock = rht_bucket_lock(tbl, hash);
540 spin_lock_bh(lock);
541
542 if (tbl->rehash <= hash)
543 break;
544
545 spin_unlock_bh(lock);
546 tbl = rcu_dereference(tbl->future_tbl);
547 }
548
549 data = rhashtable_lookup_one(ht, tbl, hash, key, obj);
550 new_tbl = rhashtable_insert_one(ht, tbl, hash, obj, data);
551 if (PTR_ERR(new_tbl) != -EEXIST)
552 data = ERR_CAST(new_tbl);
553
554 while (!IS_ERR_OR_NULL(new_tbl)) {
555 tbl = new_tbl;
556 hash = rht_head_hashfn(ht, tbl, obj, ht->p);
557 spin_lock_nested(rht_bucket_lock(tbl, hash),
558 SINGLE_DEPTH_NESTING);
559
560 data = rhashtable_lookup_one(ht, tbl, hash, key, obj);
561 new_tbl = rhashtable_insert_one(ht, tbl, hash, obj, data);
562 if (PTR_ERR(new_tbl) != -EEXIST)
563 data = ERR_CAST(new_tbl);
564
565 spin_unlock(rht_bucket_lock(tbl, hash));
566 }
567
568 spin_unlock_bh(lock);
569
570 if (PTR_ERR(data) == -EAGAIN)
571 data = ERR_PTR(rhashtable_insert_rehash(ht, tbl) ?:
572 -EAGAIN);
573
574 return data;
575}
576
577void *rhashtable_insert_slow(struct rhashtable *ht, const void *key,
578 struct rhash_head *obj)
579{
580 void *data;
581
582 do {
583 rcu_read_lock();
584 data = rhashtable_try_insert(ht, key, obj);
585 rcu_read_unlock();
586 } while (PTR_ERR(data) == -EAGAIN);
587
588 return data;
Herbert Xu02fd97c2015-03-20 21:57:00 +1100589}
590EXPORT_SYMBOL_GPL(rhashtable_insert_slow);
591
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100592/**
Herbert Xu246779d2016-08-18 16:50:56 +0800593 * rhashtable_walk_enter - Initialise an iterator
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100594 * @ht: Table to walk over
595 * @iter: Hash table Iterator
596 *
597 * This function prepares a hash table walk.
598 *
599 * Note that if you restart a walk after rhashtable_walk_stop you
600 * may see the same object twice. Also, you may miss objects if
601 * there are removals in between rhashtable_walk_stop and the next
602 * call to rhashtable_walk_start.
603 *
604 * For a completely stable walk you should construct your own data
605 * structure outside the hash table.
606 *
607 * This function may sleep so you must not call it from interrupt
608 * context or with spin locks held.
609 *
Herbert Xu246779d2016-08-18 16:50:56 +0800610 * You must call rhashtable_walk_exit after this function returns.
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100611 */
Herbert Xu246779d2016-08-18 16:50:56 +0800612void rhashtable_walk_enter(struct rhashtable *ht, struct rhashtable_iter *iter)
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100613{
614 iter->ht = ht;
615 iter->p = NULL;
616 iter->slot = 0;
617 iter->skip = 0;
618
Herbert Xuc6ff5262015-12-16 16:45:54 +0800619 spin_lock(&ht->lock);
Herbert Xu246779d2016-08-18 16:50:56 +0800620 iter->walker.tbl =
Herbert Xu179ccc02015-12-19 10:45:28 +0800621 rcu_dereference_protected(ht->tbl, lockdep_is_held(&ht->lock));
Herbert Xu246779d2016-08-18 16:50:56 +0800622 list_add(&iter->walker.list, &iter->walker.tbl->walkers);
Herbert Xuc6ff5262015-12-16 16:45:54 +0800623 spin_unlock(&ht->lock);
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100624}
Herbert Xu246779d2016-08-18 16:50:56 +0800625EXPORT_SYMBOL_GPL(rhashtable_walk_enter);
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100626
627/**
628 * rhashtable_walk_exit - Free an iterator
629 * @iter: Hash table Iterator
630 *
631 * This function frees resources allocated by rhashtable_walk_init.
632 */
633void rhashtable_walk_exit(struct rhashtable_iter *iter)
634{
Herbert Xuc6ff5262015-12-16 16:45:54 +0800635 spin_lock(&iter->ht->lock);
Herbert Xu246779d2016-08-18 16:50:56 +0800636 if (iter->walker.tbl)
637 list_del(&iter->walker.list);
Herbert Xuc6ff5262015-12-16 16:45:54 +0800638 spin_unlock(&iter->ht->lock);
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100639}
640EXPORT_SYMBOL_GPL(rhashtable_walk_exit);
641
642/**
643 * rhashtable_walk_start - Start a hash table walk
644 * @iter: Hash table iterator
645 *
646 * Start a hash table walk. Note that we take the RCU lock in all
647 * cases including when we return an error. So you must always call
648 * rhashtable_walk_stop to clean up.
649 *
650 * Returns zero if successful.
651 *
652 * Returns -EAGAIN if resize event occured. Note that the iterator
653 * will rewind back to the beginning and you may use it immediately
654 * by calling rhashtable_walk_next.
655 */
656int rhashtable_walk_start(struct rhashtable_iter *iter)
Thomas Grafdb4374f2015-03-16 10:42:27 +0100657 __acquires(RCU)
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100658{
Herbert Xueddee5ba2015-03-14 13:57:20 +1100659 struct rhashtable *ht = iter->ht;
660
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100661 rcu_read_lock();
662
Herbert Xuc6ff5262015-12-16 16:45:54 +0800663 spin_lock(&ht->lock);
Herbert Xu246779d2016-08-18 16:50:56 +0800664 if (iter->walker.tbl)
665 list_del(&iter->walker.list);
Herbert Xuc6ff5262015-12-16 16:45:54 +0800666 spin_unlock(&ht->lock);
Herbert Xueddee5ba2015-03-14 13:57:20 +1100667
Herbert Xu246779d2016-08-18 16:50:56 +0800668 if (!iter->walker.tbl) {
669 iter->walker.tbl = rht_dereference_rcu(ht->tbl, ht);
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100670 return -EAGAIN;
671 }
672
673 return 0;
674}
675EXPORT_SYMBOL_GPL(rhashtable_walk_start);
676
677/**
678 * rhashtable_walk_next - Return the next object and advance the iterator
679 * @iter: Hash table iterator
680 *
681 * Note that you must call rhashtable_walk_stop when you are finished
682 * with the walk.
683 *
684 * Returns the next object or NULL when the end of the table is reached.
685 *
686 * Returns -EAGAIN if resize event occured. Note that the iterator
687 * will rewind back to the beginning and you may continue to use it.
688 */
689void *rhashtable_walk_next(struct rhashtable_iter *iter)
690{
Herbert Xu246779d2016-08-18 16:50:56 +0800691 struct bucket_table *tbl = iter->walker.tbl;
Herbert Xuca268932016-09-19 19:00:09 +0800692 struct rhlist_head *list = iter->list;
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100693 struct rhashtable *ht = iter->ht;
694 struct rhash_head *p = iter->p;
Herbert Xuca268932016-09-19 19:00:09 +0800695 bool rhlist = ht->rhlist;
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100696
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100697 if (p) {
Herbert Xuca268932016-09-19 19:00:09 +0800698 if (!rhlist || !(list = rcu_dereference(list->next))) {
699 p = rcu_dereference(p->next);
700 list = container_of(p, struct rhlist_head, rhead);
701 }
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100702 goto next;
703 }
704
705 for (; iter->slot < tbl->size; iter->slot++) {
706 int skip = iter->skip;
707
708 rht_for_each_rcu(p, tbl, iter->slot) {
Herbert Xuca268932016-09-19 19:00:09 +0800709 if (rhlist) {
710 list = container_of(p, struct rhlist_head,
711 rhead);
712 do {
713 if (!skip)
714 goto next;
715 skip--;
716 list = rcu_dereference(list->next);
717 } while (list);
718
719 continue;
720 }
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100721 if (!skip)
722 break;
723 skip--;
724 }
725
726next:
727 if (!rht_is_a_nulls(p)) {
728 iter->skip++;
729 iter->p = p;
Herbert Xuca268932016-09-19 19:00:09 +0800730 iter->list = list;
731 return rht_obj(ht, rhlist ? &list->rhead : p);
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100732 }
733
734 iter->skip = 0;
735 }
736
Phil Sutter142b9422015-07-06 15:51:20 +0200737 iter->p = NULL;
738
Herbert Xud88252f2015-03-24 00:50:19 +1100739 /* Ensure we see any new tables. */
740 smp_rmb();
741
Herbert Xu246779d2016-08-18 16:50:56 +0800742 iter->walker.tbl = rht_dereference_rcu(tbl->future_tbl, ht);
743 if (iter->walker.tbl) {
Herbert Xueddee5ba2015-03-14 13:57:20 +1100744 iter->slot = 0;
745 iter->skip = 0;
746 return ERR_PTR(-EAGAIN);
747 }
748
Thomas Grafc936a792015-05-05 02:22:53 +0200749 return NULL;
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100750}
751EXPORT_SYMBOL_GPL(rhashtable_walk_next);
752
753/**
754 * rhashtable_walk_stop - Finish a hash table walk
755 * @iter: Hash table iterator
756 *
757 * Finish a hash table walk.
758 */
759void rhashtable_walk_stop(struct rhashtable_iter *iter)
Thomas Grafdb4374f2015-03-16 10:42:27 +0100760 __releases(RCU)
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100761{
Herbert Xueddee5ba2015-03-14 13:57:20 +1100762 struct rhashtable *ht;
Herbert Xu246779d2016-08-18 16:50:56 +0800763 struct bucket_table *tbl = iter->walker.tbl;
Herbert Xueddee5ba2015-03-14 13:57:20 +1100764
Herbert Xueddee5ba2015-03-14 13:57:20 +1100765 if (!tbl)
Herbert Xu963ecbd2015-03-15 21:12:04 +1100766 goto out;
Herbert Xueddee5ba2015-03-14 13:57:20 +1100767
768 ht = iter->ht;
769
Herbert Xuba7c95e2015-03-24 09:53:17 +1100770 spin_lock(&ht->lock);
Herbert Xuc4db8842015-03-14 13:57:25 +1100771 if (tbl->rehash < tbl->size)
Herbert Xu246779d2016-08-18 16:50:56 +0800772 list_add(&iter->walker.list, &tbl->walkers);
Herbert Xueddee5ba2015-03-14 13:57:20 +1100773 else
Herbert Xu246779d2016-08-18 16:50:56 +0800774 iter->walker.tbl = NULL;
Herbert Xuba7c95e2015-03-24 09:53:17 +1100775 spin_unlock(&ht->lock);
Herbert Xueddee5ba2015-03-14 13:57:20 +1100776
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100777 iter->p = NULL;
Herbert Xu963ecbd2015-03-15 21:12:04 +1100778
779out:
780 rcu_read_unlock();
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100781}
782EXPORT_SYMBOL_GPL(rhashtable_walk_stop);
783
Herbert Xu488fb86e2015-03-20 21:56:59 +1100784static size_t rounded_hashtable_size(const struct rhashtable_params *params)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200785{
Davidlohr Bueso09ae0082018-07-16 13:26:13 -0700786 size_t retsize;
787
788 if (params->nelem_hint)
789 retsize = max(roundup_pow_of_two(params->nelem_hint * 4 / 3),
790 (unsigned long)params->min_size);
791 else
792 retsize = max(HASH_DEFAULT_SIZE,
793 (unsigned long)params->min_size);
794
795 return retsize;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200796}
797
Herbert Xu31ccde22015-03-24 00:50:21 +1100798static u32 rhashtable_jhash2(const void *key, u32 length, u32 seed)
799{
800 return jhash2(key, length, seed);
801}
802
Thomas Graf7e1e7762014-08-02 11:47:44 +0200803/**
804 * rhashtable_init - initialize a new hash table
805 * @ht: hash table to be initialized
806 * @params: configuration parameters
807 *
808 * Initializes a new hash table based on the provided configuration
809 * parameters. A table can be configured either with a variable or
810 * fixed length key:
811 *
812 * Configuration Example 1: Fixed length keys
813 * struct test_obj {
814 * int key;
815 * void * my_member;
816 * struct rhash_head node;
817 * };
818 *
819 * struct rhashtable_params params = {
820 * .head_offset = offsetof(struct test_obj, node),
821 * .key_offset = offsetof(struct test_obj, key),
822 * .key_len = sizeof(int),
Daniel Borkmann87545892014-12-10 16:33:11 +0100823 * .hashfn = jhash,
Thomas Graff89bd6f2015-01-02 23:00:21 +0100824 * .nulls_base = (1U << RHT_BASE_SHIFT),
Thomas Graf7e1e7762014-08-02 11:47:44 +0200825 * };
826 *
827 * Configuration Example 2: Variable length keys
828 * struct test_obj {
829 * [...]
830 * struct rhash_head node;
831 * };
832 *
Patrick McHardy49f7b332015-03-25 13:07:45 +0000833 * u32 my_hash_fn(const void *data, u32 len, u32 seed)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200834 * {
835 * struct test_obj *obj = data;
836 *
837 * return [... hash ...];
838 * }
839 *
840 * struct rhashtable_params params = {
841 * .head_offset = offsetof(struct test_obj, node),
Daniel Borkmann87545892014-12-10 16:33:11 +0100842 * .hashfn = jhash,
Thomas Graf7e1e7762014-08-02 11:47:44 +0200843 * .obj_hashfn = my_hash_fn,
Thomas Graf7e1e7762014-08-02 11:47:44 +0200844 * };
845 */
Herbert Xu488fb86e2015-03-20 21:56:59 +1100846int rhashtable_init(struct rhashtable *ht,
847 const struct rhashtable_params *params)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200848{
849 struct bucket_table *tbl;
850 size_t size;
851
Herbert Xu31ccde22015-03-24 00:50:21 +1100852 if ((!params->key_len && !params->obj_hashfn) ||
Herbert Xu02fd97c2015-03-20 21:57:00 +1100853 (params->obj_hashfn && !params->obj_cmpfn))
Thomas Graf7e1e7762014-08-02 11:47:44 +0200854 return -EINVAL;
855
Thomas Graff89bd6f2015-01-02 23:00:21 +0100856 if (params->nulls_base && params->nulls_base < (1U << RHT_BASE_SHIFT))
857 return -EINVAL;
858
Thomas Graf97defe12015-01-02 23:00:20 +0100859 memset(ht, 0, sizeof(*ht));
860 mutex_init(&ht->mutex);
Herbert Xuba7c95e2015-03-24 09:53:17 +1100861 spin_lock_init(&ht->lock);
Thomas Graf97defe12015-01-02 23:00:20 +0100862 memcpy(&ht->p, params, sizeof(*params));
863
Thomas Grafa998f712015-03-19 22:31:13 +0000864 if (params->min_size)
865 ht->p.min_size = roundup_pow_of_two(params->min_size);
866
867 if (params->max_size)
868 ht->p.max_size = rounddown_pow_of_two(params->max_size);
869
Herbert Xu07ee0722015-05-15 11:30:47 +0800870 if (params->insecure_max_entries)
871 ht->p.insecure_max_entries =
872 rounddown_pow_of_two(params->insecure_max_entries);
873 else
874 ht->p.insecure_max_entries = ht->p.max_size * 2;
875
Herbert Xu488fb86e2015-03-20 21:56:59 +1100876 ht->p.min_size = max(ht->p.min_size, HASH_MIN_SIZE);
Thomas Grafa998f712015-03-19 22:31:13 +0000877
Davidlohr Bueso09ae0082018-07-16 13:26:13 -0700878 size = rounded_hashtable_size(&ht->p);
Herbert Xu3a324602015-12-16 18:13:14 +0800879
Herbert Xu27ed44a2015-03-24 13:37:30 +1100880 /* The maximum (not average) chain length grows with the
881 * size of the hash table, at a rate of (log N)/(log log N).
882 * The value of 16 is selected so that even if the hash
883 * table grew to 2^32 you would not expect the maximum
884 * chain length to exceed it unless we are under attack
885 * (or extremely unlucky).
886 *
887 * As this limit is only to detect attacks, we don't need
888 * to set it to a lower value as you'd need the chain
889 * length to vastly exceed 16 to have any real effect
890 * on the system.
891 */
Herbert Xuccd57b12015-03-24 00:50:28 +1100892 if (!params->insecure_elasticity)
893 ht->elasticity = 16;
894
Thomas Graf97defe12015-01-02 23:00:20 +0100895 if (params->locks_mul)
896 ht->p.locks_mul = roundup_pow_of_two(params->locks_mul);
897 else
898 ht->p.locks_mul = BUCKET_LOCKS_PER_CPU;
899
Herbert Xu31ccde22015-03-24 00:50:21 +1100900 ht->key_len = ht->p.key_len;
901 if (!params->hashfn) {
902 ht->p.hashfn = jhash;
903
904 if (!(ht->key_len & (sizeof(u32) - 1))) {
905 ht->key_len /= sizeof(u32);
906 ht->p.hashfn = rhashtable_jhash2;
907 }
908 }
909
Herbert Xub9ecfda2015-03-24 00:50:27 +1100910 tbl = bucket_table_alloc(ht, size, GFP_KERNEL);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200911 if (tbl == NULL)
912 return -ENOMEM;
913
Ying Xue545a1482015-01-07 13:41:57 +0800914 atomic_set(&ht->nelems, 0);
Daniel Borkmanna5b68462015-03-12 15:28:40 +0100915
Thomas Graf7e1e7762014-08-02 11:47:44 +0200916 RCU_INIT_POINTER(ht->tbl, tbl);
917
Daniel Borkmann4c4b52d2015-02-25 16:31:54 +0100918 INIT_WORK(&ht->run_work, rht_deferred_worker);
Thomas Graf97defe12015-01-02 23:00:20 +0100919
Thomas Graf7e1e7762014-08-02 11:47:44 +0200920 return 0;
921}
922EXPORT_SYMBOL_GPL(rhashtable_init);
923
924/**
Herbert Xuca268932016-09-19 19:00:09 +0800925 * rhltable_init - initialize a new hash list table
926 * @hlt: hash list table to be initialized
927 * @params: configuration parameters
928 *
929 * Initializes a new hash list table.
930 *
931 * See documentation for rhashtable_init.
932 */
933int rhltable_init(struct rhltable *hlt, const struct rhashtable_params *params)
934{
935 int err;
936
937 /* No rhlist NULLs marking for now. */
938 if (params->nulls_base)
939 return -EINVAL;
940
941 err = rhashtable_init(&hlt->ht, params);
942 hlt->ht.rhlist = true;
943 return err;
944}
945EXPORT_SYMBOL_GPL(rhltable_init);
946
947static void rhashtable_free_one(struct rhashtable *ht, struct rhash_head *obj,
948 void (*free_fn)(void *ptr, void *arg),
949 void *arg)
950{
951 struct rhlist_head *list;
952
953 if (!ht->rhlist) {
954 free_fn(rht_obj(ht, obj), arg);
955 return;
956 }
957
958 list = container_of(obj, struct rhlist_head, rhead);
959 do {
960 obj = &list->rhead;
961 list = rht_dereference(list->next, ht);
962 free_fn(rht_obj(ht, obj), arg);
963 } while (list);
964}
965
966/**
Thomas Graf6b6f3022015-03-24 14:18:20 +0100967 * rhashtable_free_and_destroy - free elements and destroy hash table
Thomas Graf7e1e7762014-08-02 11:47:44 +0200968 * @ht: the hash table to destroy
Thomas Graf6b6f3022015-03-24 14:18:20 +0100969 * @free_fn: callback to release resources of element
970 * @arg: pointer passed to free_fn
Thomas Graf7e1e7762014-08-02 11:47:44 +0200971 *
Thomas Graf6b6f3022015-03-24 14:18:20 +0100972 * Stops an eventual async resize. If defined, invokes free_fn for each
973 * element to releasal resources. Please note that RCU protected
974 * readers may still be accessing the elements. Releasing of resources
975 * must occur in a compatible manner. Then frees the bucket array.
976 *
977 * This function will eventually sleep to wait for an async resize
978 * to complete. The caller is responsible that no further write operations
979 * occurs in parallel.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200980 */
Thomas Graf6b6f3022015-03-24 14:18:20 +0100981void rhashtable_free_and_destroy(struct rhashtable *ht,
982 void (*free_fn)(void *ptr, void *arg),
983 void *arg)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200984{
Thomas Graf6b6f3022015-03-24 14:18:20 +0100985 const struct bucket_table *tbl;
986 unsigned int i;
Thomas Graf97defe12015-01-02 23:00:20 +0100987
Daniel Borkmann4c4b52d2015-02-25 16:31:54 +0100988 cancel_work_sync(&ht->run_work);
Ying Xue57699a42015-01-16 11:13:09 +0800989
Thomas Graf97defe12015-01-02 23:00:20 +0100990 mutex_lock(&ht->mutex);
Thomas Graf6b6f3022015-03-24 14:18:20 +0100991 tbl = rht_dereference(ht->tbl, ht);
992 if (free_fn) {
993 for (i = 0; i < tbl->size; i++) {
994 struct rhash_head *pos, *next;
995
996 for (pos = rht_dereference(tbl->buckets[i], ht),
997 next = !rht_is_a_nulls(pos) ?
998 rht_dereference(pos->next, ht) : NULL;
999 !rht_is_a_nulls(pos);
1000 pos = next,
1001 next = !rht_is_a_nulls(pos) ?
1002 rht_dereference(pos->next, ht) : NULL)
Herbert Xuca268932016-09-19 19:00:09 +08001003 rhashtable_free_one(ht, pos, free_fn, arg);
Thomas Graf6b6f3022015-03-24 14:18:20 +01001004 }
1005 }
1006
1007 bucket_table_free(tbl);
Thomas Graf97defe12015-01-02 23:00:20 +01001008 mutex_unlock(&ht->mutex);
Thomas Graf7e1e7762014-08-02 11:47:44 +02001009}
Thomas Graf6b6f3022015-03-24 14:18:20 +01001010EXPORT_SYMBOL_GPL(rhashtable_free_and_destroy);
1011
1012void rhashtable_destroy(struct rhashtable *ht)
1013{
1014 return rhashtable_free_and_destroy(ht, NULL, NULL);
1015}
Thomas Graf7e1e7762014-08-02 11:47:44 +02001016EXPORT_SYMBOL_GPL(rhashtable_destroy);