blob: 51282f5797606545330a29e93b3728d843616ea9 [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);
David S. Millera90099d92015-12-05 22:47:11 -0500123 if (tbl == NULL && gfp == GFP_KERNEL)
124 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
Dmitriy Vyukov7def0f92015-09-22 10:51:52 +0200190 RCU_INIT_POINTER(entry->next, head);
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100191
192 rcu_assign_pointer(new_tbl->buckets[new_hash], entry);
193 spin_unlock(new_bucket_lock);
194
195 rcu_assign_pointer(*pprev, next);
196
197out:
198 return err;
Thomas Graf97defe12015-01-02 23:00:20 +0100199}
200
Thomas Graf299e5c32015-03-24 14:18:17 +0100201static void rhashtable_rehash_chain(struct rhashtable *ht,
202 unsigned int old_hash)
Thomas Graf97defe12015-01-02 23:00:20 +0100203{
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100204 struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
205 spinlock_t *old_bucket_lock;
Thomas Graf7cd10db2015-02-05 02:03:35 +0100206
Herbert Xu02fd97c2015-03-20 21:57:00 +1100207 old_bucket_lock = rht_bucket_lock(old_tbl, old_hash);
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100208
209 spin_lock_bh(old_bucket_lock);
210 while (!rhashtable_rehash_one(ht, old_hash))
211 ;
Herbert Xu63d512d2015-03-14 13:57:24 +1100212 old_tbl->rehash++;
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100213 spin_unlock_bh(old_bucket_lock);
214}
215
Herbert Xub8244782015-03-24 00:50:26 +1100216static int rhashtable_rehash_attach(struct rhashtable *ht,
217 struct bucket_table *old_tbl,
218 struct bucket_table *new_tbl)
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100219{
Herbert Xub8244782015-03-24 00:50:26 +1100220 /* Protect future_tbl using the first bucket lock. */
221 spin_lock_bh(old_tbl->locks);
222
223 /* Did somebody beat us to it? */
224 if (rcu_access_pointer(old_tbl->future_tbl)) {
225 spin_unlock_bh(old_tbl->locks);
226 return -EEXIST;
227 }
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100228
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100229 /* Make insertions go into the new, empty table right away. Deletions
230 * and lookups will be attempted in both tables until we synchronize.
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100231 */
Herbert Xuc4db8842015-03-14 13:57:25 +1100232 rcu_assign_pointer(old_tbl->future_tbl, new_tbl);
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100233
Herbert Xu9497df82015-03-12 22:07:49 +1100234 /* Ensure the new table is visible to readers. */
235 smp_wmb();
236
Herbert Xub8244782015-03-24 00:50:26 +1100237 spin_unlock_bh(old_tbl->locks);
238
239 return 0;
240}
241
242static int rhashtable_rehash_table(struct rhashtable *ht)
243{
244 struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
245 struct bucket_table *new_tbl;
246 struct rhashtable_walker *walker;
Thomas Graf299e5c32015-03-24 14:18:17 +0100247 unsigned int old_hash;
Herbert Xub8244782015-03-24 00:50:26 +1100248
249 new_tbl = rht_dereference(old_tbl->future_tbl, ht);
250 if (!new_tbl)
251 return 0;
252
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100253 for (old_hash = 0; old_hash < old_tbl->size; old_hash++)
254 rhashtable_rehash_chain(ht, old_hash);
255
256 /* Publish the new table pointer. */
257 rcu_assign_pointer(ht->tbl, new_tbl);
258
Herbert Xuba7c95e2015-03-24 09:53:17 +1100259 spin_lock(&ht->lock);
Herbert Xueddee5ba2015-03-14 13:57:20 +1100260 list_for_each_entry(walker, &old_tbl->walkers, list)
261 walker->tbl = NULL;
Herbert Xuba7c95e2015-03-24 09:53:17 +1100262 spin_unlock(&ht->lock);
Herbert Xueddee5ba2015-03-14 13:57:20 +1100263
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100264 /* Wait for readers. All new readers will see the new
265 * table, and thus no references to the old table will
266 * remain.
267 */
Herbert Xu9d901bc2015-03-14 13:57:23 +1100268 call_rcu(&old_tbl->rcu, bucket_table_free_rcu);
Herbert Xub8244782015-03-24 00:50:26 +1100269
270 return rht_dereference(new_tbl->future_tbl, ht) ? -EAGAIN : 0;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200271}
272
273/**
274 * rhashtable_expand - Expand hash table while allowing concurrent lookups
275 * @ht: the hash table to expand
Thomas Graf7e1e7762014-08-02 11:47:44 +0200276 *
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100277 * A secondary bucket array is allocated and the hash entries are migrated.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200278 *
279 * This function may only be called in a context where it is safe to call
280 * synchronize_rcu(), e.g. not within a rcu_read_lock() section.
281 *
Thomas Graf97defe12015-01-02 23:00:20 +0100282 * The caller must ensure that no concurrent resizing occurs by holding
283 * ht->mutex.
284 *
285 * It is valid to have concurrent insertions and deletions protected by per
286 * bucket locks or concurrent RCU protected lookups and traversals.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200287 */
Herbert Xub8244782015-03-24 00:50:26 +1100288static int rhashtable_expand(struct rhashtable *ht)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200289{
290 struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);
Herbert Xub8244782015-03-24 00:50:26 +1100291 int err;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200292
293 ASSERT_RHT_MUTEX(ht);
294
Herbert Xub8244782015-03-24 00:50:26 +1100295 old_tbl = rhashtable_last_table(ht, old_tbl);
296
Herbert Xub9ecfda2015-03-24 00:50:27 +1100297 new_tbl = bucket_table_alloc(ht, old_tbl->size * 2, GFP_KERNEL);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200298 if (new_tbl == NULL)
299 return -ENOMEM;
300
Herbert Xub8244782015-03-24 00:50:26 +1100301 err = rhashtable_rehash_attach(ht, old_tbl, new_tbl);
302 if (err)
303 bucket_table_free(new_tbl);
304
305 return err;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200306}
Thomas Graf7e1e7762014-08-02 11:47:44 +0200307
308/**
309 * rhashtable_shrink - Shrink hash table while allowing concurrent lookups
310 * @ht: the hash table to shrink
Thomas Graf7e1e7762014-08-02 11:47:44 +0200311 *
Herbert Xu18093d12015-03-24 00:50:25 +1100312 * This function shrinks the hash table to fit, i.e., the smallest
313 * size would not cause it to expand right away automatically.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200314 *
Thomas Graf97defe12015-01-02 23:00:20 +0100315 * The caller must ensure that no concurrent resizing occurs by holding
316 * ht->mutex.
317 *
Thomas Graf7e1e7762014-08-02 11:47:44 +0200318 * The caller must ensure that no concurrent table mutations take place.
319 * It is however valid to have concurrent lookups if they are RCU protected.
Thomas Graf97defe12015-01-02 23:00:20 +0100320 *
321 * It is valid to have concurrent insertions and deletions protected by per
322 * bucket locks or concurrent RCU protected lookups and traversals.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200323 */
Herbert Xub8244782015-03-24 00:50:26 +1100324static int rhashtable_shrink(struct rhashtable *ht)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200325{
Daniel Borkmanna5b68462015-03-12 15:28:40 +0100326 struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);
Thomas Graf299e5c32015-03-24 14:18:17 +0100327 unsigned int size;
Herbert Xub8244782015-03-24 00:50:26 +1100328 int err;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200329
330 ASSERT_RHT_MUTEX(ht);
331
Thomas Graf299e5c32015-03-24 14:18:17 +0100332 size = roundup_pow_of_two(atomic_read(&ht->nelems) * 3 / 2);
Herbert Xu18093d12015-03-24 00:50:25 +1100333 if (size < ht->p.min_size)
334 size = ht->p.min_size;
335
336 if (old_tbl->size <= size)
337 return 0;
338
Herbert Xub8244782015-03-24 00:50:26 +1100339 if (rht_dereference(old_tbl->future_tbl, ht))
340 return -EEXIST;
341
Herbert Xub9ecfda2015-03-24 00:50:27 +1100342 new_tbl = bucket_table_alloc(ht, size, GFP_KERNEL);
Thomas Graf97defe12015-01-02 23:00:20 +0100343 if (new_tbl == NULL)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200344 return -ENOMEM;
345
Herbert Xub8244782015-03-24 00:50:26 +1100346 err = rhashtable_rehash_attach(ht, old_tbl, new_tbl);
347 if (err)
348 bucket_table_free(new_tbl);
349
350 return err;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200351}
Thomas Graf7e1e7762014-08-02 11:47:44 +0200352
Thomas Graf97defe12015-01-02 23:00:20 +0100353static void rht_deferred_worker(struct work_struct *work)
354{
355 struct rhashtable *ht;
356 struct bucket_table *tbl;
Herbert Xub8244782015-03-24 00:50:26 +1100357 int err = 0;
Thomas Graf97defe12015-01-02 23:00:20 +0100358
Ying Xue57699a42015-01-16 11:13:09 +0800359 ht = container_of(work, struct rhashtable, run_work);
Thomas Graf97defe12015-01-02 23:00:20 +0100360 mutex_lock(&ht->mutex);
Herbert Xu28134a52015-02-04 07:33:22 +1100361
Thomas Graf97defe12015-01-02 23:00:20 +0100362 tbl = rht_dereference(ht->tbl, ht);
Herbert Xub8244782015-03-24 00:50:26 +1100363 tbl = rhashtable_last_table(ht, tbl);
Thomas Graf97defe12015-01-02 23:00:20 +0100364
Daniel Borkmanna5b68462015-03-12 15:28:40 +0100365 if (rht_grow_above_75(ht, tbl))
Thomas Graf97defe12015-01-02 23:00:20 +0100366 rhashtable_expand(ht);
Thomas Grafb5e2c152015-03-24 20:42:19 +0000367 else if (ht->p.automatic_shrinking && rht_shrink_below_30(ht, tbl))
Thomas Graf97defe12015-01-02 23:00:20 +0100368 rhashtable_shrink(ht);
Herbert Xub8244782015-03-24 00:50:26 +1100369
370 err = rhashtable_rehash_table(ht);
371
Thomas Graf97defe12015-01-02 23:00:20 +0100372 mutex_unlock(&ht->mutex);
Herbert Xub8244782015-03-24 00:50:26 +1100373
374 if (err)
375 schedule_work(&ht->run_work);
Thomas Graf97defe12015-01-02 23:00:20 +0100376}
377
Herbert Xuccd57b12015-03-24 00:50:28 +1100378static bool rhashtable_check_elasticity(struct rhashtable *ht,
379 struct bucket_table *tbl,
Thomas Graf299e5c32015-03-24 14:18:17 +0100380 unsigned int hash)
Herbert Xuccd57b12015-03-24 00:50:28 +1100381{
Thomas Graf299e5c32015-03-24 14:18:17 +0100382 unsigned int elasticity = ht->elasticity;
Herbert Xuccd57b12015-03-24 00:50:28 +1100383 struct rhash_head *head;
384
385 rht_for_each(head, tbl, hash)
386 if (!--elasticity)
387 return true;
388
389 return false;
390}
391
Herbert Xu3cf92222015-12-03 20:41:29 +0800392int rhashtable_insert_rehash(struct rhashtable *ht,
393 struct bucket_table *tbl)
Herbert Xuccd57b12015-03-24 00:50:28 +1100394{
395 struct bucket_table *old_tbl;
396 struct bucket_table *new_tbl;
Herbert Xuccd57b12015-03-24 00:50:28 +1100397 unsigned int size;
398 int err;
399
400 old_tbl = rht_dereference_rcu(ht->tbl, ht);
Herbert Xuccd57b12015-03-24 00:50:28 +1100401
402 size = tbl->size;
403
Herbert Xu3cf92222015-12-03 20:41:29 +0800404 err = -EBUSY;
405
Herbert Xuccd57b12015-03-24 00:50:28 +1100406 if (rht_grow_above_75(ht, tbl))
407 size *= 2;
Thomas Grafa87b9eb2015-04-22 09:41:46 +0200408 /* Do not schedule more than one rehash */
409 else if (old_tbl != tbl)
Herbert Xu3cf92222015-12-03 20:41:29 +0800410 goto fail;
411
412 err = -ENOMEM;
Herbert Xuccd57b12015-03-24 00:50:28 +1100413
414 new_tbl = bucket_table_alloc(ht, size, GFP_ATOMIC);
Herbert Xu3cf92222015-12-03 20:41:29 +0800415 if (new_tbl == NULL)
416 goto fail;
Herbert Xuccd57b12015-03-24 00:50:28 +1100417
418 err = rhashtable_rehash_attach(ht, tbl, new_tbl);
419 if (err) {
420 bucket_table_free(new_tbl);
421 if (err == -EEXIST)
422 err = 0;
423 } else
424 schedule_work(&ht->run_work);
425
426 return err;
Herbert Xu3cf92222015-12-03 20:41:29 +0800427
428fail:
429 /* Do not fail the insert if someone else did a rehash. */
430 if (likely(rcu_dereference_raw(tbl->future_tbl)))
431 return 0;
432
433 /* Schedule async rehash to retry allocation in process context. */
434 if (err == -ENOMEM)
435 schedule_work(&ht->run_work);
436
437 return err;
Herbert Xuccd57b12015-03-24 00:50:28 +1100438}
439EXPORT_SYMBOL_GPL(rhashtable_insert_rehash);
440
Herbert Xu3cf92222015-12-03 20:41:29 +0800441struct bucket_table *rhashtable_insert_slow(struct rhashtable *ht,
442 const void *key,
443 struct rhash_head *obj,
444 struct bucket_table *tbl)
Herbert Xu02fd97c2015-03-20 21:57:00 +1100445{
446 struct rhash_head *head;
Thomas Graf299e5c32015-03-24 14:18:17 +0100447 unsigned int hash;
Herbert Xuccd57b12015-03-24 00:50:28 +1100448 int err;
Herbert Xu02fd97c2015-03-20 21:57:00 +1100449
Herbert Xub8244782015-03-24 00:50:26 +1100450 tbl = rhashtable_last_table(ht, tbl);
Herbert Xu02fd97c2015-03-20 21:57:00 +1100451 hash = head_hashfn(ht, tbl, obj);
452 spin_lock_nested(rht_bucket_lock(tbl, hash), SINGLE_DEPTH_NESTING);
453
Herbert Xuccd57b12015-03-24 00:50:28 +1100454 err = -EEXIST;
Herbert Xu02fd97c2015-03-20 21:57:00 +1100455 if (key && rhashtable_lookup_fast(ht, key, ht->p))
456 goto exit;
457
Herbert Xu07ee0722015-05-15 11:30:47 +0800458 err = -E2BIG;
459 if (unlikely(rht_grow_above_max(ht, tbl)))
460 goto exit;
461
Herbert Xuccd57b12015-03-24 00:50:28 +1100462 err = -EAGAIN;
463 if (rhashtable_check_elasticity(ht, tbl, hash) ||
464 rht_grow_above_100(ht, tbl))
465 goto exit;
466
Herbert Xu02fd97c2015-03-20 21:57:00 +1100467 err = 0;
468
469 head = rht_dereference_bucket(tbl->buckets[hash], tbl, hash);
470
471 RCU_INIT_POINTER(obj->next, head);
472
473 rcu_assign_pointer(tbl->buckets[hash], obj);
474
475 atomic_inc(&ht->nelems);
476
477exit:
478 spin_unlock(rht_bucket_lock(tbl, hash));
479
Herbert Xu3cf92222015-12-03 20:41:29 +0800480 if (err == 0)
481 return NULL;
482 else if (err == -EAGAIN)
483 return tbl;
484 else
485 return ERR_PTR(err);
Herbert Xu02fd97c2015-03-20 21:57:00 +1100486}
487EXPORT_SYMBOL_GPL(rhashtable_insert_slow);
488
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100489/**
490 * rhashtable_walk_init - Initialise an iterator
491 * @ht: Table to walk over
492 * @iter: Hash table Iterator
493 *
494 * This function prepares a hash table walk.
495 *
496 * Note that if you restart a walk after rhashtable_walk_stop you
497 * may see the same object twice. Also, you may miss objects if
498 * there are removals in between rhashtable_walk_stop and the next
499 * call to rhashtable_walk_start.
500 *
501 * For a completely stable walk you should construct your own data
502 * structure outside the hash table.
503 *
504 * This function may sleep so you must not call it from interrupt
505 * context or with spin locks held.
506 *
507 * You must call rhashtable_walk_exit if this function returns
508 * successfully.
509 */
510int rhashtable_walk_init(struct rhashtable *ht, struct rhashtable_iter *iter)
511{
512 iter->ht = ht;
513 iter->p = NULL;
514 iter->slot = 0;
515 iter->skip = 0;
516
517 iter->walker = kmalloc(sizeof(*iter->walker), GFP_KERNEL);
518 if (!iter->walker)
519 return -ENOMEM;
520
Herbert Xuc6ff5262015-12-16 16:45:54 +0800521 spin_lock(&ht->lock);
Herbert Xu179ccc02015-12-19 10:45:28 +0800522 iter->walker->tbl =
523 rcu_dereference_protected(ht->tbl, lockdep_is_held(&ht->lock));
Herbert Xueddee5ba2015-03-14 13:57:20 +1100524 list_add(&iter->walker->list, &iter->walker->tbl->walkers);
Herbert Xuc6ff5262015-12-16 16:45:54 +0800525 spin_unlock(&ht->lock);
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100526
527 return 0;
528}
529EXPORT_SYMBOL_GPL(rhashtable_walk_init);
530
531/**
532 * rhashtable_walk_exit - Free an iterator
533 * @iter: Hash table Iterator
534 *
535 * This function frees resources allocated by rhashtable_walk_init.
536 */
537void rhashtable_walk_exit(struct rhashtable_iter *iter)
538{
Herbert Xuc6ff5262015-12-16 16:45:54 +0800539 spin_lock(&iter->ht->lock);
Herbert Xueddee5ba2015-03-14 13:57:20 +1100540 if (iter->walker->tbl)
541 list_del(&iter->walker->list);
Herbert Xuc6ff5262015-12-16 16:45:54 +0800542 spin_unlock(&iter->ht->lock);
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100543 kfree(iter->walker);
544}
545EXPORT_SYMBOL_GPL(rhashtable_walk_exit);
546
547/**
548 * rhashtable_walk_start - Start a hash table walk
549 * @iter: Hash table iterator
550 *
551 * Start a hash table walk. Note that we take the RCU lock in all
552 * cases including when we return an error. So you must always call
553 * rhashtable_walk_stop to clean up.
554 *
555 * Returns zero if successful.
556 *
557 * Returns -EAGAIN if resize event occured. Note that the iterator
558 * will rewind back to the beginning and you may use it immediately
559 * by calling rhashtable_walk_next.
560 */
561int rhashtable_walk_start(struct rhashtable_iter *iter)
Thomas Grafdb4374f2015-03-16 10:42:27 +0100562 __acquires(RCU)
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100563{
Herbert Xueddee5ba2015-03-14 13:57:20 +1100564 struct rhashtable *ht = iter->ht;
565
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100566 rcu_read_lock();
567
Herbert Xuc6ff5262015-12-16 16:45:54 +0800568 spin_lock(&ht->lock);
569 if (iter->walker->tbl)
570 list_del(&iter->walker->list);
571 spin_unlock(&ht->lock);
Herbert Xueddee5ba2015-03-14 13:57:20 +1100572
573 if (!iter->walker->tbl) {
574 iter->walker->tbl = rht_dereference_rcu(ht->tbl, ht);
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100575 return -EAGAIN;
576 }
577
578 return 0;
579}
580EXPORT_SYMBOL_GPL(rhashtable_walk_start);
581
582/**
583 * rhashtable_walk_next - Return the next object and advance the iterator
584 * @iter: Hash table iterator
585 *
586 * Note that you must call rhashtable_walk_stop when you are finished
587 * with the walk.
588 *
589 * Returns the next object or NULL when the end of the table is reached.
590 *
591 * Returns -EAGAIN if resize event occured. Note that the iterator
592 * will rewind back to the beginning and you may continue to use it.
593 */
594void *rhashtable_walk_next(struct rhashtable_iter *iter)
595{
Herbert Xueddee5ba2015-03-14 13:57:20 +1100596 struct bucket_table *tbl = iter->walker->tbl;
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100597 struct rhashtable *ht = iter->ht;
598 struct rhash_head *p = iter->p;
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100599
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100600 if (p) {
601 p = rht_dereference_bucket_rcu(p->next, tbl, iter->slot);
602 goto next;
603 }
604
605 for (; iter->slot < tbl->size; iter->slot++) {
606 int skip = iter->skip;
607
608 rht_for_each_rcu(p, tbl, iter->slot) {
609 if (!skip)
610 break;
611 skip--;
612 }
613
614next:
615 if (!rht_is_a_nulls(p)) {
616 iter->skip++;
617 iter->p = p;
Thomas Grafc936a792015-05-05 02:22:53 +0200618 return rht_obj(ht, p);
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100619 }
620
621 iter->skip = 0;
622 }
623
Phil Sutter142b9422015-07-06 15:51:20 +0200624 iter->p = NULL;
625
Herbert Xud88252f2015-03-24 00:50:19 +1100626 /* Ensure we see any new tables. */
627 smp_rmb();
628
Herbert Xuc4db8842015-03-14 13:57:25 +1100629 iter->walker->tbl = rht_dereference_rcu(tbl->future_tbl, ht);
630 if (iter->walker->tbl) {
Herbert Xueddee5ba2015-03-14 13:57:20 +1100631 iter->slot = 0;
632 iter->skip = 0;
633 return ERR_PTR(-EAGAIN);
634 }
635
Thomas Grafc936a792015-05-05 02:22:53 +0200636 return NULL;
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100637}
638EXPORT_SYMBOL_GPL(rhashtable_walk_next);
639
640/**
641 * rhashtable_walk_stop - Finish a hash table walk
642 * @iter: Hash table iterator
643 *
644 * Finish a hash table walk.
645 */
646void rhashtable_walk_stop(struct rhashtable_iter *iter)
Thomas Grafdb4374f2015-03-16 10:42:27 +0100647 __releases(RCU)
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100648{
Herbert Xueddee5ba2015-03-14 13:57:20 +1100649 struct rhashtable *ht;
650 struct bucket_table *tbl = iter->walker->tbl;
651
Herbert Xueddee5ba2015-03-14 13:57:20 +1100652 if (!tbl)
Herbert Xu963ecbd2015-03-15 21:12:04 +1100653 goto out;
Herbert Xueddee5ba2015-03-14 13:57:20 +1100654
655 ht = iter->ht;
656
Herbert Xuba7c95e2015-03-24 09:53:17 +1100657 spin_lock(&ht->lock);
Herbert Xuc4db8842015-03-14 13:57:25 +1100658 if (tbl->rehash < tbl->size)
Herbert Xueddee5ba2015-03-14 13:57:20 +1100659 list_add(&iter->walker->list, &tbl->walkers);
660 else
661 iter->walker->tbl = NULL;
Herbert Xuba7c95e2015-03-24 09:53:17 +1100662 spin_unlock(&ht->lock);
Herbert Xueddee5ba2015-03-14 13:57:20 +1100663
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100664 iter->p = NULL;
Herbert Xu963ecbd2015-03-15 21:12:04 +1100665
666out:
667 rcu_read_unlock();
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100668}
669EXPORT_SYMBOL_GPL(rhashtable_walk_stop);
670
Herbert Xu488fb86e2015-03-20 21:56:59 +1100671static size_t rounded_hashtable_size(const struct rhashtable_params *params)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200672{
Ying Xue94000172014-09-03 09:22:36 +0800673 return max(roundup_pow_of_two(params->nelem_hint * 4 / 3),
Herbert Xue2e21c12015-03-18 20:01:21 +1100674 (unsigned long)params->min_size);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200675}
676
Herbert Xu31ccde22015-03-24 00:50:21 +1100677static u32 rhashtable_jhash2(const void *key, u32 length, u32 seed)
678{
679 return jhash2(key, length, seed);
680}
681
Thomas Graf7e1e7762014-08-02 11:47:44 +0200682/**
683 * rhashtable_init - initialize a new hash table
684 * @ht: hash table to be initialized
685 * @params: configuration parameters
686 *
687 * Initializes a new hash table based on the provided configuration
688 * parameters. A table can be configured either with a variable or
689 * fixed length key:
690 *
691 * Configuration Example 1: Fixed length keys
692 * struct test_obj {
693 * int key;
694 * void * my_member;
695 * struct rhash_head node;
696 * };
697 *
698 * struct rhashtable_params params = {
699 * .head_offset = offsetof(struct test_obj, node),
700 * .key_offset = offsetof(struct test_obj, key),
701 * .key_len = sizeof(int),
Daniel Borkmann87545892014-12-10 16:33:11 +0100702 * .hashfn = jhash,
Thomas Graff89bd6f2015-01-02 23:00:21 +0100703 * .nulls_base = (1U << RHT_BASE_SHIFT),
Thomas Graf7e1e7762014-08-02 11:47:44 +0200704 * };
705 *
706 * Configuration Example 2: Variable length keys
707 * struct test_obj {
708 * [...]
709 * struct rhash_head node;
710 * };
711 *
Patrick McHardy49f7b332015-03-25 13:07:45 +0000712 * u32 my_hash_fn(const void *data, u32 len, u32 seed)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200713 * {
714 * struct test_obj *obj = data;
715 *
716 * return [... hash ...];
717 * }
718 *
719 * struct rhashtable_params params = {
720 * .head_offset = offsetof(struct test_obj, node),
Daniel Borkmann87545892014-12-10 16:33:11 +0100721 * .hashfn = jhash,
Thomas Graf7e1e7762014-08-02 11:47:44 +0200722 * .obj_hashfn = my_hash_fn,
Thomas Graf7e1e7762014-08-02 11:47:44 +0200723 * };
724 */
Herbert Xu488fb86e2015-03-20 21:56:59 +1100725int rhashtable_init(struct rhashtable *ht,
726 const struct rhashtable_params *params)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200727{
728 struct bucket_table *tbl;
729 size_t size;
730
731 size = HASH_DEFAULT_SIZE;
732
Herbert Xu31ccde22015-03-24 00:50:21 +1100733 if ((!params->key_len && !params->obj_hashfn) ||
Herbert Xu02fd97c2015-03-20 21:57:00 +1100734 (params->obj_hashfn && !params->obj_cmpfn))
Thomas Graf7e1e7762014-08-02 11:47:44 +0200735 return -EINVAL;
736
Thomas Graff89bd6f2015-01-02 23:00:21 +0100737 if (params->nulls_base && params->nulls_base < (1U << RHT_BASE_SHIFT))
738 return -EINVAL;
739
Thomas Graf97defe12015-01-02 23:00:20 +0100740 memset(ht, 0, sizeof(*ht));
741 mutex_init(&ht->mutex);
Herbert Xuba7c95e2015-03-24 09:53:17 +1100742 spin_lock_init(&ht->lock);
Thomas Graf97defe12015-01-02 23:00:20 +0100743 memcpy(&ht->p, params, sizeof(*params));
744
Thomas Grafa998f712015-03-19 22:31:13 +0000745 if (params->min_size)
746 ht->p.min_size = roundup_pow_of_two(params->min_size);
747
748 if (params->max_size)
749 ht->p.max_size = rounddown_pow_of_two(params->max_size);
750
Herbert Xu07ee0722015-05-15 11:30:47 +0800751 if (params->insecure_max_entries)
752 ht->p.insecure_max_entries =
753 rounddown_pow_of_two(params->insecure_max_entries);
754 else
755 ht->p.insecure_max_entries = ht->p.max_size * 2;
756
Herbert Xu488fb86e2015-03-20 21:56:59 +1100757 ht->p.min_size = max(ht->p.min_size, HASH_MIN_SIZE);
Thomas Grafa998f712015-03-19 22:31:13 +0000758
Herbert Xu3a324602015-12-16 18:13:14 +0800759 if (params->nelem_hint)
760 size = rounded_hashtable_size(&ht->p);
761
Herbert Xu27ed44a2015-03-24 13:37:30 +1100762 /* The maximum (not average) chain length grows with the
763 * size of the hash table, at a rate of (log N)/(log log N).
764 * The value of 16 is selected so that even if the hash
765 * table grew to 2^32 you would not expect the maximum
766 * chain length to exceed it unless we are under attack
767 * (or extremely unlucky).
768 *
769 * As this limit is only to detect attacks, we don't need
770 * to set it to a lower value as you'd need the chain
771 * length to vastly exceed 16 to have any real effect
772 * on the system.
773 */
Herbert Xuccd57b12015-03-24 00:50:28 +1100774 if (!params->insecure_elasticity)
775 ht->elasticity = 16;
776
Thomas Graf97defe12015-01-02 23:00:20 +0100777 if (params->locks_mul)
778 ht->p.locks_mul = roundup_pow_of_two(params->locks_mul);
779 else
780 ht->p.locks_mul = BUCKET_LOCKS_PER_CPU;
781
Herbert Xu31ccde22015-03-24 00:50:21 +1100782 ht->key_len = ht->p.key_len;
783 if (!params->hashfn) {
784 ht->p.hashfn = jhash;
785
786 if (!(ht->key_len & (sizeof(u32) - 1))) {
787 ht->key_len /= sizeof(u32);
788 ht->p.hashfn = rhashtable_jhash2;
789 }
790 }
791
Herbert Xub9ecfda2015-03-24 00:50:27 +1100792 tbl = bucket_table_alloc(ht, size, GFP_KERNEL);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200793 if (tbl == NULL)
794 return -ENOMEM;
795
Ying Xue545a1482015-01-07 13:41:57 +0800796 atomic_set(&ht->nelems, 0);
Daniel Borkmanna5b68462015-03-12 15:28:40 +0100797
Thomas Graf7e1e7762014-08-02 11:47:44 +0200798 RCU_INIT_POINTER(ht->tbl, tbl);
799
Daniel Borkmann4c4b52d2015-02-25 16:31:54 +0100800 INIT_WORK(&ht->run_work, rht_deferred_worker);
Thomas Graf97defe12015-01-02 23:00:20 +0100801
Thomas Graf7e1e7762014-08-02 11:47:44 +0200802 return 0;
803}
804EXPORT_SYMBOL_GPL(rhashtable_init);
805
806/**
Thomas Graf6b6f3022015-03-24 14:18:20 +0100807 * rhashtable_free_and_destroy - free elements and destroy hash table
Thomas Graf7e1e7762014-08-02 11:47:44 +0200808 * @ht: the hash table to destroy
Thomas Graf6b6f3022015-03-24 14:18:20 +0100809 * @free_fn: callback to release resources of element
810 * @arg: pointer passed to free_fn
Thomas Graf7e1e7762014-08-02 11:47:44 +0200811 *
Thomas Graf6b6f3022015-03-24 14:18:20 +0100812 * Stops an eventual async resize. If defined, invokes free_fn for each
813 * element to releasal resources. Please note that RCU protected
814 * readers may still be accessing the elements. Releasing of resources
815 * must occur in a compatible manner. Then frees the bucket array.
816 *
817 * This function will eventually sleep to wait for an async resize
818 * to complete. The caller is responsible that no further write operations
819 * occurs in parallel.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200820 */
Thomas Graf6b6f3022015-03-24 14:18:20 +0100821void rhashtable_free_and_destroy(struct rhashtable *ht,
822 void (*free_fn)(void *ptr, void *arg),
823 void *arg)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200824{
Thomas Graf6b6f3022015-03-24 14:18:20 +0100825 const struct bucket_table *tbl;
826 unsigned int i;
Thomas Graf97defe12015-01-02 23:00:20 +0100827
Daniel Borkmann4c4b52d2015-02-25 16:31:54 +0100828 cancel_work_sync(&ht->run_work);
Ying Xue57699a42015-01-16 11:13:09 +0800829
Thomas Graf97defe12015-01-02 23:00:20 +0100830 mutex_lock(&ht->mutex);
Thomas Graf6b6f3022015-03-24 14:18:20 +0100831 tbl = rht_dereference(ht->tbl, ht);
832 if (free_fn) {
833 for (i = 0; i < tbl->size; i++) {
834 struct rhash_head *pos, *next;
835
836 for (pos = rht_dereference(tbl->buckets[i], ht),
837 next = !rht_is_a_nulls(pos) ?
838 rht_dereference(pos->next, ht) : NULL;
839 !rht_is_a_nulls(pos);
840 pos = next,
841 next = !rht_is_a_nulls(pos) ?
842 rht_dereference(pos->next, ht) : NULL)
843 free_fn(rht_obj(ht, pos), arg);
844 }
845 }
846
847 bucket_table_free(tbl);
Thomas Graf97defe12015-01-02 23:00:20 +0100848 mutex_unlock(&ht->mutex);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200849}
Thomas Graf6b6f3022015-03-24 14:18:20 +0100850EXPORT_SYMBOL_GPL(rhashtable_free_and_destroy);
851
852void rhashtable_destroy(struct rhashtable *ht)
853{
854 return rhashtable_free_and_destroy(ht, NULL, NULL);
855}
Thomas Graf7e1e7762014-08-02 11:47:44 +0200856EXPORT_SYMBOL_GPL(rhashtable_destroy);