blob: 776b3a82d3a178ff3eded9125d090a490a628a2e [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>
Ingo Molnarb2d09102017-02-04 01:27:20 +010022#include <linux/rculist.h>
Thomas Graf7e1e7762014-08-02 11:47:44 +020023#include <linux/slab.h>
24#include <linux/vmalloc.h>
25#include <linux/mm.h>
Daniel Borkmann87545892014-12-10 16:33:11 +010026#include <linux/jhash.h>
Thomas Graf7e1e7762014-08-02 11:47:44 +020027#include <linux/random.h>
28#include <linux/rhashtable.h>
Stephen Rothwell61d7b092015-02-09 14:04:03 +110029#include <linux/err.h>
Hauke Mehrtens6d795412015-06-06 22:07:23 +020030#include <linux/export.h>
Thomas Graf7e1e7762014-08-02 11:47:44 +020031
32#define HASH_DEFAULT_SIZE 64UL
Herbert Xuc2e213c2015-03-18 20:01:16 +110033#define HASH_MIN_SIZE 4U
Florian Westphal4cf0b352016-08-12 12:03:52 +020034#define BUCKET_LOCKS_PER_CPU 32UL
Thomas Graf97defe12015-01-02 23:00:20 +010035
Herbert Xuda204202017-02-11 19:26:47 +080036union nested_table {
37 union nested_table __rcu *table;
38 struct rhash_head __rcu *bucket;
39};
40
Herbert Xu988dfbd2015-03-10 09:27:55 +110041static u32 head_hashfn(struct rhashtable *ht,
Thomas Graf8d24c0b2015-01-02 23:00:14 +010042 const struct bucket_table *tbl,
43 const struct rhash_head *he)
Thomas Graf7e1e7762014-08-02 11:47:44 +020044{
Herbert Xu02fd97c2015-03-20 21:57:00 +110045 return rht_head_hashfn(ht, tbl, he, ht->p);
Thomas Graf7e1e7762014-08-02 11:47:44 +020046}
47
Thomas Grafa03eaec2015-02-05 02:03:34 +010048#ifdef CONFIG_PROVE_LOCKING
Thomas Grafa03eaec2015-02-05 02:03:34 +010049#define ASSERT_RHT_MUTEX(HT) BUG_ON(!lockdep_rht_mutex_is_held(HT))
Thomas Grafa03eaec2015-02-05 02:03:34 +010050
51int lockdep_rht_mutex_is_held(struct rhashtable *ht)
52{
53 return (debug_locks) ? lockdep_is_held(&ht->mutex) : 1;
54}
55EXPORT_SYMBOL_GPL(lockdep_rht_mutex_is_held);
56
57int lockdep_rht_bucket_is_held(const struct bucket_table *tbl, u32 hash)
58{
Herbert Xu02fd97c2015-03-20 21:57:00 +110059 spinlock_t *lock = rht_bucket_lock(tbl, hash);
Thomas Grafa03eaec2015-02-05 02:03:34 +010060
61 return (debug_locks) ? lockdep_is_held(lock) : 1;
62}
63EXPORT_SYMBOL_GPL(lockdep_rht_bucket_is_held);
64#else
65#define ASSERT_RHT_MUTEX(HT)
Thomas Grafa03eaec2015-02-05 02:03:34 +010066#endif
67
Herbert Xuda204202017-02-11 19:26:47 +080068static void nested_table_free(union nested_table *ntbl, unsigned int size)
69{
70 const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *));
71 const unsigned int len = 1 << shift;
72 unsigned int i;
73
74 ntbl = rcu_dereference_raw(ntbl->table);
75 if (!ntbl)
76 return;
77
78 if (size > len) {
79 size >>= shift;
80 for (i = 0; i < len; i++)
81 nested_table_free(ntbl + i, size);
82 }
83
84 kfree(ntbl);
85}
86
87static void nested_bucket_table_free(const struct bucket_table *tbl)
88{
89 unsigned int size = tbl->size >> tbl->nest;
90 unsigned int len = 1 << tbl->nest;
91 union nested_table *ntbl;
92 unsigned int i;
93
94 ntbl = (union nested_table *)rcu_dereference_raw(tbl->buckets[0]);
95
96 for (i = 0; i < len; i++)
97 nested_table_free(ntbl + i, size);
98
99 kfree(ntbl);
100}
101
Thomas Graf97defe12015-01-02 23:00:20 +0100102static void bucket_table_free(const struct bucket_table *tbl)
103{
Herbert Xuda204202017-02-11 19:26:47 +0800104 if (tbl->nest)
105 nested_bucket_table_free(tbl);
106
Tom Herbert64e0cd02017-12-04 10:31:45 -0800107 free_bucket_spinlocks(tbl->locks);
Thomas Graf97defe12015-01-02 23:00:20 +0100108 kvfree(tbl);
109}
110
Herbert Xu9d901bc2015-03-14 13:57:23 +1100111static void bucket_table_free_rcu(struct rcu_head *head)
112{
113 bucket_table_free(container_of(head, struct bucket_table, rcu));
114}
115
Herbert Xuda204202017-02-11 19:26:47 +0800116static union nested_table *nested_table_alloc(struct rhashtable *ht,
117 union nested_table __rcu **prev,
NeilBrown5af68ef2018-06-18 12:52:50 +1000118 bool leaf)
Herbert Xuda204202017-02-11 19:26:47 +0800119{
120 union nested_table *ntbl;
121 int i;
122
123 ntbl = rcu_dereference(*prev);
124 if (ntbl)
125 return ntbl;
126
127 ntbl = kzalloc(PAGE_SIZE, GFP_ATOMIC);
128
NeilBrown5af68ef2018-06-18 12:52:50 +1000129 if (ntbl && leaf) {
130 for (i = 0; i < PAGE_SIZE / sizeof(ntbl[0]); i++)
NeilBrown9b4f64a2018-06-18 12:52:50 +1000131 INIT_RHT_NULLS_HEAD(ntbl[i].bucket);
Herbert Xuda204202017-02-11 19:26:47 +0800132 }
133
134 rcu_assign_pointer(*prev, ntbl);
135
136 return ntbl;
137}
138
139static struct bucket_table *nested_bucket_table_alloc(struct rhashtable *ht,
140 size_t nbuckets,
141 gfp_t gfp)
142{
143 const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *));
144 struct bucket_table *tbl;
145 size_t size;
146
147 if (nbuckets < (1 << (shift + 1)))
148 return NULL;
149
150 size = sizeof(*tbl) + sizeof(tbl->buckets[0]);
151
152 tbl = kzalloc(size, gfp);
153 if (!tbl)
154 return NULL;
155
156 if (!nested_table_alloc(ht, (union nested_table __rcu **)tbl->buckets,
NeilBrown5af68ef2018-06-18 12:52:50 +1000157 false)) {
Herbert Xuda204202017-02-11 19:26:47 +0800158 kfree(tbl);
159 return NULL;
160 }
161
162 tbl->nest = (ilog2(nbuckets) - 1) % shift + 1;
163
164 return tbl;
165}
166
Thomas Graf97defe12015-01-02 23:00:20 +0100167static struct bucket_table *bucket_table_alloc(struct rhashtable *ht,
Herbert Xub9ecfda2015-03-24 00:50:27 +1100168 size_t nbuckets,
169 gfp_t gfp)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200170{
Daniel Borkmanneb6d1ab2015-02-20 00:53:38 +0100171 struct bucket_table *tbl = NULL;
Tom Herbert64e0cd02017-12-04 10:31:45 -0800172 size_t size, max_locks;
Thomas Graff89bd6f2015-01-02 23:00:21 +0100173 int i;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200174
175 size = sizeof(*tbl) + nbuckets * sizeof(tbl->buckets[0]);
Davidlohr Bueso93f976b2018-08-21 22:01:45 -0700176 tbl = kvzalloc(size, gfp);
Herbert Xuda204202017-02-11 19:26:47 +0800177
178 size = nbuckets;
179
Davidlohr Bueso2d22ecf2018-08-21 22:01:48 -0700180 if (tbl == NULL && (gfp & ~__GFP_NOFAIL) != GFP_KERNEL) {
Herbert Xuda204202017-02-11 19:26:47 +0800181 tbl = nested_bucket_table_alloc(ht, nbuckets, gfp);
182 nbuckets = 0;
183 }
Davidlohr Bueso2d22ecf2018-08-21 22:01:48 -0700184
Thomas Graf7e1e7762014-08-02 11:47:44 +0200185 if (tbl == NULL)
186 return NULL;
187
Herbert Xuda204202017-02-11 19:26:47 +0800188 tbl->size = size;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200189
Tom Herbert64e0cd02017-12-04 10:31:45 -0800190 max_locks = size >> 1;
191 if (tbl->nest)
192 max_locks = min_t(size_t, max_locks, 1U << tbl->nest);
193
194 if (alloc_bucket_spinlocks(&tbl->locks, &tbl->locks_mask, max_locks,
195 ht->p.locks_mul, gfp) < 0) {
Thomas Graf97defe12015-01-02 23:00:20 +0100196 bucket_table_free(tbl);
197 return NULL;
198 }
Thomas Graf7e1e7762014-08-02 11:47:44 +0200199
NeilBrown4feb7c72019-03-21 14:42:40 +1100200 rcu_head_init(&tbl->rcu);
Herbert Xueddee5ba2015-03-14 13:57:20 +1100201 INIT_LIST_HEAD(&tbl->walkers);
202
Jason A. Donenfeldd48ad082017-06-07 22:47:13 -0400203 tbl->hash_rnd = get_random_u32();
Herbert Xu5269b532015-03-14 13:57:22 +1100204
Thomas Graff89bd6f2015-01-02 23:00:21 +0100205 for (i = 0; i < nbuckets; i++)
NeilBrown9b4f64a2018-06-18 12:52:50 +1000206 INIT_RHT_NULLS_HEAD(tbl->buckets[i]);
Thomas Graff89bd6f2015-01-02 23:00:21 +0100207
Thomas Graf97defe12015-01-02 23:00:20 +0100208 return tbl;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200209}
210
Herbert Xub8244782015-03-24 00:50:26 +1100211static struct bucket_table *rhashtable_last_table(struct rhashtable *ht,
212 struct bucket_table *tbl)
213{
214 struct bucket_table *new_tbl;
215
216 do {
217 new_tbl = tbl;
218 tbl = rht_dereference_rcu(tbl->future_tbl, ht);
219 } while (tbl);
220
221 return new_tbl;
222}
223
Thomas Graf299e5c32015-03-24 14:18:17 +0100224static int rhashtable_rehash_one(struct rhashtable *ht, unsigned int old_hash)
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100225{
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100226 struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
NeilBrownc0690012018-06-18 12:52:50 +1000227 struct bucket_table *new_tbl = rhashtable_last_table(ht, old_tbl);
Herbert Xuda204202017-02-11 19:26:47 +0800228 struct rhash_head __rcu **pprev = rht_bucket_var(old_tbl, old_hash);
229 int err = -EAGAIN;
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100230 struct rhash_head *head, *next, *entry;
231 spinlock_t *new_bucket_lock;
Thomas Graf299e5c32015-03-24 14:18:17 +0100232 unsigned int new_hash;
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100233
Herbert Xuda204202017-02-11 19:26:47 +0800234 if (new_tbl->nest)
235 goto out;
236
237 err = -ENOENT;
238
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100239 rht_for_each(entry, old_tbl, old_hash) {
240 err = 0;
241 next = rht_dereference_bucket(entry->next, old_tbl, old_hash);
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100242
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100243 if (rht_is_a_nulls(next))
Thomas Graf7e1e7762014-08-02 11:47:44 +0200244 break;
Thomas Graf97defe12015-01-02 23:00:20 +0100245
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100246 pprev = &entry->next;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200247 }
248
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100249 if (err)
250 goto out;
Thomas Graf97defe12015-01-02 23:00:20 +0100251
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100252 new_hash = head_hashfn(ht, new_tbl, entry);
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100253
Herbert Xu02fd97c2015-03-20 21:57:00 +1100254 new_bucket_lock = rht_bucket_lock(new_tbl, new_hash);
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100255
Herbert Xu8f2484b2015-03-14 13:57:21 +1100256 spin_lock_nested(new_bucket_lock, SINGLE_DEPTH_NESTING);
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100257 head = rht_dereference_bucket(new_tbl->buckets[new_hash],
258 new_tbl, new_hash);
259
Dmitriy Vyukov7def0f92015-09-22 10:51:52 +0200260 RCU_INIT_POINTER(entry->next, head);
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100261
262 rcu_assign_pointer(new_tbl->buckets[new_hash], entry);
263 spin_unlock(new_bucket_lock);
264
265 rcu_assign_pointer(*pprev, next);
266
267out:
268 return err;
Thomas Graf97defe12015-01-02 23:00:20 +0100269}
270
Herbert Xuda204202017-02-11 19:26:47 +0800271static int rhashtable_rehash_chain(struct rhashtable *ht,
Thomas Graf299e5c32015-03-24 14:18:17 +0100272 unsigned int old_hash)
Thomas Graf97defe12015-01-02 23:00:20 +0100273{
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100274 struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
275 spinlock_t *old_bucket_lock;
Herbert Xuda204202017-02-11 19:26:47 +0800276 int err;
Thomas Graf7cd10db2015-02-05 02:03:35 +0100277
Herbert Xu02fd97c2015-03-20 21:57:00 +1100278 old_bucket_lock = rht_bucket_lock(old_tbl, old_hash);
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100279
280 spin_lock_bh(old_bucket_lock);
Herbert Xuda204202017-02-11 19:26:47 +0800281 while (!(err = rhashtable_rehash_one(ht, old_hash)))
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100282 ;
Herbert Xuda204202017-02-11 19:26:47 +0800283
NeilBrown4feb7c72019-03-21 14:42:40 +1100284 if (err == -ENOENT)
Herbert Xuda204202017-02-11 19:26:47 +0800285 err = 0;
NeilBrown4feb7c72019-03-21 14:42:40 +1100286
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100287 spin_unlock_bh(old_bucket_lock);
Herbert Xuda204202017-02-11 19:26:47 +0800288
289 return err;
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100290}
291
Herbert Xub8244782015-03-24 00:50:26 +1100292static int rhashtable_rehash_attach(struct rhashtable *ht,
293 struct bucket_table *old_tbl,
294 struct bucket_table *new_tbl)
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100295{
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100296 /* Make insertions go into the new, empty table right away. Deletions
297 * and lookups will be attempted in both tables until we synchronize.
NeilBrown0ad66442018-06-18 12:52:50 +1000298 * As cmpxchg() provides strong barriers, we do not need
299 * rcu_assign_pointer().
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100300 */
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100301
NeilBrown0ad66442018-06-18 12:52:50 +1000302 if (cmpxchg(&old_tbl->future_tbl, NULL, new_tbl) != NULL)
303 return -EEXIST;
Herbert Xub8244782015-03-24 00:50:26 +1100304
305 return 0;
306}
307
308static int rhashtable_rehash_table(struct rhashtable *ht)
309{
310 struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
311 struct bucket_table *new_tbl;
312 struct rhashtable_walker *walker;
Thomas Graf299e5c32015-03-24 14:18:17 +0100313 unsigned int old_hash;
Herbert Xuda204202017-02-11 19:26:47 +0800314 int err;
Herbert Xub8244782015-03-24 00:50:26 +1100315
316 new_tbl = rht_dereference(old_tbl->future_tbl, ht);
317 if (!new_tbl)
318 return 0;
319
Herbert Xuda204202017-02-11 19:26:47 +0800320 for (old_hash = 0; old_hash < old_tbl->size; old_hash++) {
321 err = rhashtable_rehash_chain(ht, old_hash);
322 if (err)
323 return err;
Eric Dumazetae6da1f2018-03-31 12:58:48 -0700324 cond_resched();
Herbert Xuda204202017-02-11 19:26:47 +0800325 }
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100326
327 /* Publish the new table pointer. */
328 rcu_assign_pointer(ht->tbl, new_tbl);
329
Herbert Xuba7c95e2015-03-24 09:53:17 +1100330 spin_lock(&ht->lock);
Herbert Xueddee5ba2015-03-14 13:57:20 +1100331 list_for_each_entry(walker, &old_tbl->walkers, list)
332 walker->tbl = NULL;
333
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100334 /* Wait for readers. All new readers will see the new
335 * table, and thus no references to the old table will
336 * remain.
NeilBrown4feb7c72019-03-21 14:42:40 +1100337 * We do this inside the locked region so that
338 * rhashtable_walk_stop() can use rcu_head_after_call_rcu()
339 * to check if it should not re-link the table.
Herbert Xuaa34a6cb02015-03-11 09:43:48 +1100340 */
Herbert Xu9d901bc2015-03-14 13:57:23 +1100341 call_rcu(&old_tbl->rcu, bucket_table_free_rcu);
NeilBrown4feb7c72019-03-21 14:42:40 +1100342 spin_unlock(&ht->lock);
Herbert Xub8244782015-03-24 00:50:26 +1100343
344 return rht_dereference(new_tbl->future_tbl, ht) ? -EAGAIN : 0;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200345}
346
Herbert Xuda204202017-02-11 19:26:47 +0800347static int rhashtable_rehash_alloc(struct rhashtable *ht,
348 struct bucket_table *old_tbl,
349 unsigned int size)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200350{
Herbert Xuda204202017-02-11 19:26:47 +0800351 struct bucket_table *new_tbl;
Herbert Xub8244782015-03-24 00:50:26 +1100352 int err;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200353
354 ASSERT_RHT_MUTEX(ht);
355
Herbert Xuda204202017-02-11 19:26:47 +0800356 new_tbl = bucket_table_alloc(ht, size, GFP_KERNEL);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200357 if (new_tbl == NULL)
358 return -ENOMEM;
359
Herbert Xub8244782015-03-24 00:50:26 +1100360 err = rhashtable_rehash_attach(ht, old_tbl, new_tbl);
361 if (err)
362 bucket_table_free(new_tbl);
363
364 return err;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200365}
Thomas Graf7e1e7762014-08-02 11:47:44 +0200366
367/**
368 * rhashtable_shrink - Shrink hash table while allowing concurrent lookups
369 * @ht: the hash table to shrink
Thomas Graf7e1e7762014-08-02 11:47:44 +0200370 *
Herbert Xu18093d12015-03-24 00:50:25 +1100371 * This function shrinks the hash table to fit, i.e., the smallest
372 * size would not cause it to expand right away automatically.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200373 *
Thomas Graf97defe12015-01-02 23:00:20 +0100374 * The caller must ensure that no concurrent resizing occurs by holding
375 * ht->mutex.
376 *
Thomas Graf7e1e7762014-08-02 11:47:44 +0200377 * The caller must ensure that no concurrent table mutations take place.
378 * It is however valid to have concurrent lookups if they are RCU protected.
Thomas Graf97defe12015-01-02 23:00:20 +0100379 *
380 * It is valid to have concurrent insertions and deletions protected by per
381 * bucket locks or concurrent RCU protected lookups and traversals.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200382 */
Herbert Xub8244782015-03-24 00:50:26 +1100383static int rhashtable_shrink(struct rhashtable *ht)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200384{
Herbert Xuda204202017-02-11 19:26:47 +0800385 struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
Vegard Nossum12311952016-08-12 20:10:44 +0200386 unsigned int nelems = atomic_read(&ht->nelems);
387 unsigned int size = 0;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200388
Vegard Nossum12311952016-08-12 20:10:44 +0200389 if (nelems)
390 size = roundup_pow_of_two(nelems * 3 / 2);
Herbert Xu18093d12015-03-24 00:50:25 +1100391 if (size < ht->p.min_size)
392 size = ht->p.min_size;
393
394 if (old_tbl->size <= size)
395 return 0;
396
Herbert Xub8244782015-03-24 00:50:26 +1100397 if (rht_dereference(old_tbl->future_tbl, ht))
398 return -EEXIST;
399
Herbert Xuda204202017-02-11 19:26:47 +0800400 return rhashtable_rehash_alloc(ht, old_tbl, size);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200401}
Thomas Graf7e1e7762014-08-02 11:47:44 +0200402
Thomas Graf97defe12015-01-02 23:00:20 +0100403static void rht_deferred_worker(struct work_struct *work)
404{
405 struct rhashtable *ht;
406 struct bucket_table *tbl;
Herbert Xub8244782015-03-24 00:50:26 +1100407 int err = 0;
Thomas Graf97defe12015-01-02 23:00:20 +0100408
Ying Xue57699a42015-01-16 11:13:09 +0800409 ht = container_of(work, struct rhashtable, run_work);
Thomas Graf97defe12015-01-02 23:00:20 +0100410 mutex_lock(&ht->mutex);
Herbert Xu28134a52015-02-04 07:33:22 +1100411
Thomas Graf97defe12015-01-02 23:00:20 +0100412 tbl = rht_dereference(ht->tbl, ht);
Herbert Xub8244782015-03-24 00:50:26 +1100413 tbl = rhashtable_last_table(ht, tbl);
Thomas Graf97defe12015-01-02 23:00:20 +0100414
Daniel Borkmanna5b68462015-03-12 15:28:40 +0100415 if (rht_grow_above_75(ht, tbl))
Herbert Xuda204202017-02-11 19:26:47 +0800416 err = rhashtable_rehash_alloc(ht, tbl, tbl->size * 2);
Thomas Grafb5e2c152015-03-24 20:42:19 +0000417 else if (ht->p.automatic_shrinking && rht_shrink_below_30(ht, tbl))
Herbert Xuda204202017-02-11 19:26:47 +0800418 err = rhashtable_shrink(ht);
419 else if (tbl->nest)
420 err = rhashtable_rehash_alloc(ht, tbl, tbl->size);
Herbert Xub8244782015-03-24 00:50:26 +1100421
Herbert Xuda204202017-02-11 19:26:47 +0800422 if (!err)
423 err = rhashtable_rehash_table(ht);
Herbert Xub8244782015-03-24 00:50:26 +1100424
Thomas Graf97defe12015-01-02 23:00:20 +0100425 mutex_unlock(&ht->mutex);
Herbert Xub8244782015-03-24 00:50:26 +1100426
427 if (err)
428 schedule_work(&ht->run_work);
Thomas Graf97defe12015-01-02 23:00:20 +0100429}
430
Herbert Xuca268932016-09-19 19:00:09 +0800431static int rhashtable_insert_rehash(struct rhashtable *ht,
432 struct bucket_table *tbl)
Herbert Xuccd57b12015-03-24 00:50:28 +1100433{
434 struct bucket_table *old_tbl;
435 struct bucket_table *new_tbl;
Herbert Xuccd57b12015-03-24 00:50:28 +1100436 unsigned int size;
437 int err;
438
439 old_tbl = rht_dereference_rcu(ht->tbl, ht);
Herbert Xuccd57b12015-03-24 00:50:28 +1100440
441 size = tbl->size;
442
Herbert Xu3cf92222015-12-03 20:41:29 +0800443 err = -EBUSY;
444
Herbert Xuccd57b12015-03-24 00:50:28 +1100445 if (rht_grow_above_75(ht, tbl))
446 size *= 2;
Thomas Grafa87b9eb2015-04-22 09:41:46 +0200447 /* Do not schedule more than one rehash */
448 else if (old_tbl != tbl)
Herbert Xu3cf92222015-12-03 20:41:29 +0800449 goto fail;
450
451 err = -ENOMEM;
Herbert Xuccd57b12015-03-24 00:50:28 +1100452
Davidlohr Bueso93f976b2018-08-21 22:01:45 -0700453 new_tbl = bucket_table_alloc(ht, size, GFP_ATOMIC | __GFP_NOWARN);
Herbert Xu3cf92222015-12-03 20:41:29 +0800454 if (new_tbl == NULL)
455 goto fail;
Herbert Xuccd57b12015-03-24 00:50:28 +1100456
457 err = rhashtable_rehash_attach(ht, tbl, new_tbl);
458 if (err) {
459 bucket_table_free(new_tbl);
460 if (err == -EEXIST)
461 err = 0;
462 } else
463 schedule_work(&ht->run_work);
464
465 return err;
Herbert Xu3cf92222015-12-03 20:41:29 +0800466
467fail:
468 /* Do not fail the insert if someone else did a rehash. */
NeilBrownc0690012018-06-18 12:52:50 +1000469 if (likely(rcu_access_pointer(tbl->future_tbl)))
Herbert Xu3cf92222015-12-03 20:41:29 +0800470 return 0;
471
472 /* Schedule async rehash to retry allocation in process context. */
473 if (err == -ENOMEM)
474 schedule_work(&ht->run_work);
475
476 return err;
Herbert Xuccd57b12015-03-24 00:50:28 +1100477}
Herbert Xuccd57b12015-03-24 00:50:28 +1100478
Herbert Xuca268932016-09-19 19:00:09 +0800479static void *rhashtable_lookup_one(struct rhashtable *ht,
480 struct bucket_table *tbl, unsigned int hash,
481 const void *key, struct rhash_head *obj)
Herbert Xu02fd97c2015-03-20 21:57:00 +1100482{
Herbert Xuca268932016-09-19 19:00:09 +0800483 struct rhashtable_compare_arg arg = {
484 .ht = ht,
485 .key = key,
486 };
487 struct rhash_head __rcu **pprev;
Herbert Xu02fd97c2015-03-20 21:57:00 +1100488 struct rhash_head *head;
Herbert Xuca268932016-09-19 19:00:09 +0800489 int elasticity;
Herbert Xu02fd97c2015-03-20 21:57:00 +1100490
Florian Westphal5f8ddea2017-04-16 02:55:09 +0200491 elasticity = RHT_ELASTICITY;
Herbert Xuda204202017-02-11 19:26:47 +0800492 pprev = rht_bucket_var(tbl, hash);
493 rht_for_each_continue(head, *pprev, tbl, hash) {
Herbert Xuca268932016-09-19 19:00:09 +0800494 struct rhlist_head *list;
495 struct rhlist_head *plist;
Herbert Xu02fd97c2015-03-20 21:57:00 +1100496
Herbert Xuca268932016-09-19 19:00:09 +0800497 elasticity--;
498 if (!key ||
499 (ht->p.obj_cmpfn ?
500 ht->p.obj_cmpfn(&arg, rht_obj(ht, head)) :
Paul Blakeyd3dcf8e2018-03-04 17:29:48 +0200501 rhashtable_compare(&arg, rht_obj(ht, head)))) {
502 pprev = &head->next;
Herbert Xuca268932016-09-19 19:00:09 +0800503 continue;
Paul Blakeyd3dcf8e2018-03-04 17:29:48 +0200504 }
Herbert Xuca268932016-09-19 19:00:09 +0800505
506 if (!ht->rhlist)
507 return rht_obj(ht, head);
508
509 list = container_of(obj, struct rhlist_head, rhead);
510 plist = container_of(head, struct rhlist_head, rhead);
511
512 RCU_INIT_POINTER(list->next, plist);
513 head = rht_dereference_bucket(head->next, tbl, hash);
514 RCU_INIT_POINTER(list->rhead.next, head);
515 rcu_assign_pointer(*pprev, obj);
516
517 return NULL;
Pablo Neira Ayuso5ca8cc52016-08-24 12:31:31 +0200518 }
Herbert Xu02fd97c2015-03-20 21:57:00 +1100519
Herbert Xuca268932016-09-19 19:00:09 +0800520 if (elasticity <= 0)
521 return ERR_PTR(-EAGAIN);
522
523 return ERR_PTR(-ENOENT);
524}
525
526static struct bucket_table *rhashtable_insert_one(struct rhashtable *ht,
527 struct bucket_table *tbl,
528 unsigned int hash,
529 struct rhash_head *obj,
530 void *data)
531{
Herbert Xuda204202017-02-11 19:26:47 +0800532 struct rhash_head __rcu **pprev;
Herbert Xuca268932016-09-19 19:00:09 +0800533 struct bucket_table *new_tbl;
534 struct rhash_head *head;
535
536 if (!IS_ERR_OR_NULL(data))
537 return ERR_PTR(-EEXIST);
538
539 if (PTR_ERR(data) != -EAGAIN && PTR_ERR(data) != -ENOENT)
540 return ERR_CAST(data);
541
NeilBrownc0690012018-06-18 12:52:50 +1000542 new_tbl = rht_dereference_rcu(tbl->future_tbl, ht);
Herbert Xuca268932016-09-19 19:00:09 +0800543 if (new_tbl)
544 return new_tbl;
545
546 if (PTR_ERR(data) != -ENOENT)
547 return ERR_CAST(data);
548
Herbert Xu07ee0722015-05-15 11:30:47 +0800549 if (unlikely(rht_grow_above_max(ht, tbl)))
Herbert Xuca268932016-09-19 19:00:09 +0800550 return ERR_PTR(-E2BIG);
Herbert Xu07ee0722015-05-15 11:30:47 +0800551
Herbert Xuca268932016-09-19 19:00:09 +0800552 if (unlikely(rht_grow_above_100(ht, tbl)))
553 return ERR_PTR(-EAGAIN);
Herbert Xu02fd97c2015-03-20 21:57:00 +1100554
Herbert Xuda204202017-02-11 19:26:47 +0800555 pprev = rht_bucket_insert(ht, tbl, hash);
556 if (!pprev)
557 return ERR_PTR(-ENOMEM);
558
559 head = rht_dereference_bucket(*pprev, tbl, hash);
Herbert Xu02fd97c2015-03-20 21:57:00 +1100560
561 RCU_INIT_POINTER(obj->next, head);
Herbert Xuca268932016-09-19 19:00:09 +0800562 if (ht->rhlist) {
563 struct rhlist_head *list;
564
565 list = container_of(obj, struct rhlist_head, rhead);
566 RCU_INIT_POINTER(list->next, NULL);
567 }
Herbert Xu02fd97c2015-03-20 21:57:00 +1100568
Herbert Xuda204202017-02-11 19:26:47 +0800569 rcu_assign_pointer(*pprev, obj);
Herbert Xu02fd97c2015-03-20 21:57:00 +1100570
571 atomic_inc(&ht->nelems);
Herbert Xuca268932016-09-19 19:00:09 +0800572 if (rht_grow_above_75(ht, tbl))
573 schedule_work(&ht->run_work);
Herbert Xu02fd97c2015-03-20 21:57:00 +1100574
Herbert Xuca268932016-09-19 19:00:09 +0800575 return NULL;
576}
Herbert Xu02fd97c2015-03-20 21:57:00 +1100577
Herbert Xuca268932016-09-19 19:00:09 +0800578static void *rhashtable_try_insert(struct rhashtable *ht, const void *key,
579 struct rhash_head *obj)
580{
581 struct bucket_table *new_tbl;
582 struct bucket_table *tbl;
583 unsigned int hash;
Herbert Xuca268932016-09-19 19:00:09 +0800584 void *data;
585
NeilBrown4feb7c72019-03-21 14:42:40 +1100586 new_tbl = rcu_dereference(ht->tbl);
Herbert Xuca268932016-09-19 19:00:09 +0800587
NeilBrown4feb7c72019-03-21 14:42:40 +1100588 do {
Herbert Xuca268932016-09-19 19:00:09 +0800589 tbl = new_tbl;
590 hash = rht_head_hashfn(ht, tbl, obj, ht->p);
NeilBrown4feb7c72019-03-21 14:42:40 +1100591 spin_lock_bh(rht_bucket_lock(tbl, hash));
Herbert Xuca268932016-09-19 19:00:09 +0800592
593 data = rhashtable_lookup_one(ht, tbl, hash, key, obj);
594 new_tbl = rhashtable_insert_one(ht, tbl, hash, obj, data);
595 if (PTR_ERR(new_tbl) != -EEXIST)
596 data = ERR_CAST(new_tbl);
597
NeilBrown4feb7c72019-03-21 14:42:40 +1100598 spin_unlock_bh(rht_bucket_lock(tbl, hash));
599 } while (!IS_ERR_OR_NULL(new_tbl));
Herbert Xuca268932016-09-19 19:00:09 +0800600
601 if (PTR_ERR(data) == -EAGAIN)
602 data = ERR_PTR(rhashtable_insert_rehash(ht, tbl) ?:
603 -EAGAIN);
604
605 return data;
606}
607
608void *rhashtable_insert_slow(struct rhashtable *ht, const void *key,
609 struct rhash_head *obj)
610{
611 void *data;
612
613 do {
614 rcu_read_lock();
615 data = rhashtable_try_insert(ht, key, obj);
616 rcu_read_unlock();
617 } while (PTR_ERR(data) == -EAGAIN);
618
619 return data;
Herbert Xu02fd97c2015-03-20 21:57:00 +1100620}
621EXPORT_SYMBOL_GPL(rhashtable_insert_slow);
622
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100623/**
Herbert Xu246779d2016-08-18 16:50:56 +0800624 * rhashtable_walk_enter - Initialise an iterator
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100625 * @ht: Table to walk over
626 * @iter: Hash table Iterator
627 *
628 * This function prepares a hash table walk.
629 *
630 * Note that if you restart a walk after rhashtable_walk_stop you
631 * may see the same object twice. Also, you may miss objects if
632 * there are removals in between rhashtable_walk_stop and the next
633 * call to rhashtable_walk_start.
634 *
635 * For a completely stable walk you should construct your own data
636 * structure outside the hash table.
637 *
NeilBrown82266e92018-04-24 08:29:13 +1000638 * This function may be called from any process context, including
639 * non-preemptable context, but cannot be called from softirq or
640 * hardirq context.
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100641 *
Herbert Xu246779d2016-08-18 16:50:56 +0800642 * You must call rhashtable_walk_exit after this function returns.
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100643 */
Herbert Xu246779d2016-08-18 16:50:56 +0800644void rhashtable_walk_enter(struct rhashtable *ht, struct rhashtable_iter *iter)
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100645{
646 iter->ht = ht;
647 iter->p = NULL;
648 iter->slot = 0;
649 iter->skip = 0;
Tom Herbert2db54b42017-12-04 10:31:42 -0800650 iter->end_of_table = 0;
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100651
Herbert Xuc6ff5262015-12-16 16:45:54 +0800652 spin_lock(&ht->lock);
Herbert Xu246779d2016-08-18 16:50:56 +0800653 iter->walker.tbl =
Herbert Xu179ccc02015-12-19 10:45:28 +0800654 rcu_dereference_protected(ht->tbl, lockdep_is_held(&ht->lock));
Herbert Xu246779d2016-08-18 16:50:56 +0800655 list_add(&iter->walker.list, &iter->walker.tbl->walkers);
Herbert Xuc6ff5262015-12-16 16:45:54 +0800656 spin_unlock(&ht->lock);
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100657}
Herbert Xu246779d2016-08-18 16:50:56 +0800658EXPORT_SYMBOL_GPL(rhashtable_walk_enter);
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100659
660/**
661 * rhashtable_walk_exit - Free an iterator
662 * @iter: Hash table Iterator
663 *
Herbert Xu6c4128f2019-02-14 22:03:27 +0800664 * This function frees resources allocated by rhashtable_walk_enter.
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100665 */
666void rhashtable_walk_exit(struct rhashtable_iter *iter)
667{
Herbert Xuc6ff5262015-12-16 16:45:54 +0800668 spin_lock(&iter->ht->lock);
Herbert Xu246779d2016-08-18 16:50:56 +0800669 if (iter->walker.tbl)
670 list_del(&iter->walker.list);
Herbert Xuc6ff5262015-12-16 16:45:54 +0800671 spin_unlock(&iter->ht->lock);
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100672}
673EXPORT_SYMBOL_GPL(rhashtable_walk_exit);
674
675/**
Tom Herbert97a6ec42017-12-04 10:31:41 -0800676 * rhashtable_walk_start_check - Start a hash table walk
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100677 * @iter: Hash table iterator
678 *
Andreas Gruenbacher06471692017-09-19 12:41:37 +0200679 * Start a hash table walk at the current iterator position. Note that we take
680 * the RCU lock in all cases including when we return an error. So you must
681 * always call rhashtable_walk_stop to clean up.
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100682 *
683 * Returns zero if successful.
684 *
685 * Returns -EAGAIN if resize event occured. Note that the iterator
686 * will rewind back to the beginning and you may use it immediately
687 * by calling rhashtable_walk_next.
Tom Herbert97a6ec42017-12-04 10:31:41 -0800688 *
689 * rhashtable_walk_start is defined as an inline variant that returns
690 * void. This is preferred in cases where the caller would ignore
691 * resize events and always continue.
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100692 */
Tom Herbert97a6ec42017-12-04 10:31:41 -0800693int rhashtable_walk_start_check(struct rhashtable_iter *iter)
Thomas Grafdb4374f2015-03-16 10:42:27 +0100694 __acquires(RCU)
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100695{
Herbert Xueddee5ba2015-03-14 13:57:20 +1100696 struct rhashtable *ht = iter->ht;
NeilBrown5d240a82018-04-24 08:29:13 +1000697 bool rhlist = ht->rhlist;
Herbert Xueddee5ba2015-03-14 13:57:20 +1100698
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100699 rcu_read_lock();
700
Herbert Xuc6ff5262015-12-16 16:45:54 +0800701 spin_lock(&ht->lock);
Herbert Xu246779d2016-08-18 16:50:56 +0800702 if (iter->walker.tbl)
703 list_del(&iter->walker.list);
Herbert Xuc6ff5262015-12-16 16:45:54 +0800704 spin_unlock(&ht->lock);
Herbert Xueddee5ba2015-03-14 13:57:20 +1100705
NeilBrown5d240a82018-04-24 08:29:13 +1000706 if (iter->end_of_table)
707 return 0;
708 if (!iter->walker.tbl) {
Herbert Xu246779d2016-08-18 16:50:56 +0800709 iter->walker.tbl = rht_dereference_rcu(ht->tbl, ht);
NeilBrownb41cc042018-04-24 08:29:13 +1000710 iter->slot = 0;
711 iter->skip = 0;
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100712 return -EAGAIN;
713 }
714
NeilBrown5d240a82018-04-24 08:29:13 +1000715 if (iter->p && !rhlist) {
716 /*
717 * We need to validate that 'p' is still in the table, and
718 * if so, update 'skip'
719 */
720 struct rhash_head *p;
721 int skip = 0;
722 rht_for_each_rcu(p, iter->walker.tbl, iter->slot) {
723 skip++;
724 if (p == iter->p) {
725 iter->skip = skip;
726 goto found;
727 }
728 }
729 iter->p = NULL;
730 } else if (iter->p && rhlist) {
731 /* Need to validate that 'list' is still in the table, and
732 * if so, update 'skip' and 'p'.
733 */
734 struct rhash_head *p;
735 struct rhlist_head *list;
736 int skip = 0;
737 rht_for_each_rcu(p, iter->walker.tbl, iter->slot) {
738 for (list = container_of(p, struct rhlist_head, rhead);
739 list;
740 list = rcu_dereference(list->next)) {
741 skip++;
742 if (list == iter->list) {
743 iter->p = p;
Rishabh Bhatnagarc643ecf2018-07-02 09:35:34 -0700744 iter->skip = skip;
NeilBrown5d240a82018-04-24 08:29:13 +1000745 goto found;
746 }
747 }
748 }
749 iter->p = NULL;
750 }
751found:
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100752 return 0;
753}
Tom Herbert97a6ec42017-12-04 10:31:41 -0800754EXPORT_SYMBOL_GPL(rhashtable_walk_start_check);
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100755
756/**
Tom Herbert2db54b42017-12-04 10:31:42 -0800757 * __rhashtable_walk_find_next - Find the next element in a table (or the first
758 * one in case of a new walk).
759 *
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100760 * @iter: Hash table iterator
761 *
Tom Herbert2db54b42017-12-04 10:31:42 -0800762 * Returns the found object or NULL when the end of the table is reached.
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100763 *
Tom Herbert2db54b42017-12-04 10:31:42 -0800764 * Returns -EAGAIN if resize event occurred.
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100765 */
Tom Herbert2db54b42017-12-04 10:31:42 -0800766static void *__rhashtable_walk_find_next(struct rhashtable_iter *iter)
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100767{
Herbert Xu246779d2016-08-18 16:50:56 +0800768 struct bucket_table *tbl = iter->walker.tbl;
Herbert Xuca268932016-09-19 19:00:09 +0800769 struct rhlist_head *list = iter->list;
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100770 struct rhashtable *ht = iter->ht;
771 struct rhash_head *p = iter->p;
Herbert Xuca268932016-09-19 19:00:09 +0800772 bool rhlist = ht->rhlist;
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100773
Tom Herbert2db54b42017-12-04 10:31:42 -0800774 if (!tbl)
775 return NULL;
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100776
777 for (; iter->slot < tbl->size; iter->slot++) {
778 int skip = iter->skip;
779
780 rht_for_each_rcu(p, tbl, iter->slot) {
Herbert Xuca268932016-09-19 19:00:09 +0800781 if (rhlist) {
782 list = container_of(p, struct rhlist_head,
783 rhead);
784 do {
785 if (!skip)
786 goto next;
787 skip--;
788 list = rcu_dereference(list->next);
789 } while (list);
790
791 continue;
792 }
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100793 if (!skip)
794 break;
795 skip--;
796 }
797
798next:
799 if (!rht_is_a_nulls(p)) {
800 iter->skip++;
801 iter->p = p;
Herbert Xuca268932016-09-19 19:00:09 +0800802 iter->list = list;
803 return rht_obj(ht, rhlist ? &list->rhead : p);
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100804 }
805
806 iter->skip = 0;
807 }
808
Phil Sutter142b9422015-07-06 15:51:20 +0200809 iter->p = NULL;
810
Herbert Xud88252f2015-03-24 00:50:19 +1100811 /* Ensure we see any new tables. */
812 smp_rmb();
813
Herbert Xu246779d2016-08-18 16:50:56 +0800814 iter->walker.tbl = rht_dereference_rcu(tbl->future_tbl, ht);
815 if (iter->walker.tbl) {
Herbert Xueddee5ba2015-03-14 13:57:20 +1100816 iter->slot = 0;
817 iter->skip = 0;
818 return ERR_PTR(-EAGAIN);
Tom Herbert2db54b42017-12-04 10:31:42 -0800819 } else {
820 iter->end_of_table = true;
Herbert Xueddee5ba2015-03-14 13:57:20 +1100821 }
822
Thomas Grafc936a792015-05-05 02:22:53 +0200823 return NULL;
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100824}
Tom Herbert2db54b42017-12-04 10:31:42 -0800825
826/**
827 * rhashtable_walk_next - Return the next object and advance the iterator
828 * @iter: Hash table iterator
829 *
830 * Note that you must call rhashtable_walk_stop when you are finished
831 * with the walk.
832 *
833 * Returns the next object or NULL when the end of the table is reached.
834 *
835 * Returns -EAGAIN if resize event occurred. Note that the iterator
836 * will rewind back to the beginning and you may continue to use it.
837 */
838void *rhashtable_walk_next(struct rhashtable_iter *iter)
839{
840 struct rhlist_head *list = iter->list;
841 struct rhashtable *ht = iter->ht;
842 struct rhash_head *p = iter->p;
843 bool rhlist = ht->rhlist;
844
845 if (p) {
846 if (!rhlist || !(list = rcu_dereference(list->next))) {
847 p = rcu_dereference(p->next);
848 list = container_of(p, struct rhlist_head, rhead);
849 }
850 if (!rht_is_a_nulls(p)) {
851 iter->skip++;
852 iter->p = p;
853 iter->list = list;
854 return rht_obj(ht, rhlist ? &list->rhead : p);
855 }
856
857 /* At the end of this slot, switch to next one and then find
858 * next entry from that point.
859 */
860 iter->skip = 0;
861 iter->slot++;
862 }
863
864 return __rhashtable_walk_find_next(iter);
865}
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100866EXPORT_SYMBOL_GPL(rhashtable_walk_next);
867
868/**
Tom Herbert2db54b42017-12-04 10:31:42 -0800869 * rhashtable_walk_peek - Return the next object but don't advance the iterator
870 * @iter: Hash table iterator
871 *
872 * Returns the next object or NULL when the end of the table is reached.
873 *
874 * Returns -EAGAIN if resize event occurred. Note that the iterator
875 * will rewind back to the beginning and you may continue to use it.
876 */
877void *rhashtable_walk_peek(struct rhashtable_iter *iter)
878{
879 struct rhlist_head *list = iter->list;
880 struct rhashtable *ht = iter->ht;
881 struct rhash_head *p = iter->p;
882
883 if (p)
884 return rht_obj(ht, ht->rhlist ? &list->rhead : p);
885
886 /* No object found in current iter, find next one in the table. */
887
888 if (iter->skip) {
889 /* A nonzero skip value points to the next entry in the table
890 * beyond that last one that was found. Decrement skip so
891 * we find the current value. __rhashtable_walk_find_next
892 * will restore the original value of skip assuming that
893 * the table hasn't changed.
894 */
895 iter->skip--;
896 }
897
898 return __rhashtable_walk_find_next(iter);
899}
900EXPORT_SYMBOL_GPL(rhashtable_walk_peek);
901
902/**
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100903 * rhashtable_walk_stop - Finish a hash table walk
904 * @iter: Hash table iterator
905 *
Andreas Gruenbacher06471692017-09-19 12:41:37 +0200906 * Finish a hash table walk. Does not reset the iterator to the start of the
907 * hash table.
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100908 */
909void rhashtable_walk_stop(struct rhashtable_iter *iter)
Thomas Grafdb4374f2015-03-16 10:42:27 +0100910 __releases(RCU)
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100911{
Herbert Xueddee5ba2015-03-14 13:57:20 +1100912 struct rhashtable *ht;
Herbert Xu246779d2016-08-18 16:50:56 +0800913 struct bucket_table *tbl = iter->walker.tbl;
Herbert Xueddee5ba2015-03-14 13:57:20 +1100914
Herbert Xueddee5ba2015-03-14 13:57:20 +1100915 if (!tbl)
Herbert Xu963ecbd2015-03-15 21:12:04 +1100916 goto out;
Herbert Xueddee5ba2015-03-14 13:57:20 +1100917
918 ht = iter->ht;
919
Herbert Xuba7c95e2015-03-24 09:53:17 +1100920 spin_lock(&ht->lock);
NeilBrown4feb7c72019-03-21 14:42:40 +1100921 if (rcu_head_after_call_rcu(&tbl->rcu, bucket_table_free_rcu))
922 /* This bucket table is being freed, don't re-link it. */
Herbert Xu246779d2016-08-18 16:50:56 +0800923 iter->walker.tbl = NULL;
NeilBrown4feb7c72019-03-21 14:42:40 +1100924 else
925 list_add(&iter->walker.list, &tbl->walkers);
Herbert Xuba7c95e2015-03-24 09:53:17 +1100926 spin_unlock(&ht->lock);
Herbert Xueddee5ba2015-03-14 13:57:20 +1100927
Herbert Xu963ecbd2015-03-15 21:12:04 +1100928out:
929 rcu_read_unlock();
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100930}
931EXPORT_SYMBOL_GPL(rhashtable_walk_stop);
932
Herbert Xu488fb86e2015-03-20 21:56:59 +1100933static size_t rounded_hashtable_size(const struct rhashtable_params *params)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200934{
Davidlohr Bueso107d01f2018-07-16 13:26:13 -0700935 size_t retsize;
936
937 if (params->nelem_hint)
938 retsize = max(roundup_pow_of_two(params->nelem_hint * 4 / 3),
939 (unsigned long)params->min_size);
940 else
941 retsize = max(HASH_DEFAULT_SIZE,
942 (unsigned long)params->min_size);
943
944 return retsize;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200945}
946
Herbert Xu31ccde22015-03-24 00:50:21 +1100947static u32 rhashtable_jhash2(const void *key, u32 length, u32 seed)
948{
949 return jhash2(key, length, seed);
950}
951
Thomas Graf7e1e7762014-08-02 11:47:44 +0200952/**
953 * rhashtable_init - initialize a new hash table
954 * @ht: hash table to be initialized
955 * @params: configuration parameters
956 *
957 * Initializes a new hash table based on the provided configuration
958 * parameters. A table can be configured either with a variable or
959 * fixed length key:
960 *
961 * Configuration Example 1: Fixed length keys
962 * struct test_obj {
963 * int key;
964 * void * my_member;
965 * struct rhash_head node;
966 * };
967 *
968 * struct rhashtable_params params = {
969 * .head_offset = offsetof(struct test_obj, node),
970 * .key_offset = offsetof(struct test_obj, key),
971 * .key_len = sizeof(int),
Daniel Borkmann87545892014-12-10 16:33:11 +0100972 * .hashfn = jhash,
Thomas Graf7e1e7762014-08-02 11:47:44 +0200973 * };
974 *
975 * Configuration Example 2: Variable length keys
976 * struct test_obj {
977 * [...]
978 * struct rhash_head node;
979 * };
980 *
Patrick McHardy49f7b332015-03-25 13:07:45 +0000981 * u32 my_hash_fn(const void *data, u32 len, u32 seed)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200982 * {
983 * struct test_obj *obj = data;
984 *
985 * return [... hash ...];
986 * }
987 *
988 * struct rhashtable_params params = {
989 * .head_offset = offsetof(struct test_obj, node),
Daniel Borkmann87545892014-12-10 16:33:11 +0100990 * .hashfn = jhash,
Thomas Graf7e1e7762014-08-02 11:47:44 +0200991 * .obj_hashfn = my_hash_fn,
Thomas Graf7e1e7762014-08-02 11:47:44 +0200992 * };
993 */
Herbert Xu488fb86e2015-03-20 21:56:59 +1100994int rhashtable_init(struct rhashtable *ht,
995 const struct rhashtable_params *params)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200996{
997 struct bucket_table *tbl;
998 size_t size;
999
Herbert Xu31ccde22015-03-24 00:50:21 +11001000 if ((!params->key_len && !params->obj_hashfn) ||
Herbert Xu02fd97c2015-03-20 21:57:00 +11001001 (params->obj_hashfn && !params->obj_cmpfn))
Thomas Graf7e1e7762014-08-02 11:47:44 +02001002 return -EINVAL;
1003
Thomas Graf97defe12015-01-02 23:00:20 +01001004 memset(ht, 0, sizeof(*ht));
1005 mutex_init(&ht->mutex);
Herbert Xuba7c95e2015-03-24 09:53:17 +11001006 spin_lock_init(&ht->lock);
Thomas Graf97defe12015-01-02 23:00:20 +01001007 memcpy(&ht->p, params, sizeof(*params));
1008
Thomas Grafa998f712015-03-19 22:31:13 +00001009 if (params->min_size)
1010 ht->p.min_size = roundup_pow_of_two(params->min_size);
1011
Herbert Xu6d684e52017-04-27 13:44:51 +08001012 /* Cap total entries at 2^31 to avoid nelems overflow. */
1013 ht->max_elems = 1u << 31;
Herbert Xu2d2ab652017-04-28 14:10:48 +08001014
1015 if (params->max_size) {
1016 ht->p.max_size = rounddown_pow_of_two(params->max_size);
1017 if (ht->p.max_size < ht->max_elems / 2)
1018 ht->max_elems = ht->p.max_size * 2;
1019 }
Herbert Xu6d684e52017-04-27 13:44:51 +08001020
Florian Westphal48e75b432017-05-01 22:18:01 +02001021 ht->p.min_size = max_t(u16, ht->p.min_size, HASH_MIN_SIZE);
Thomas Grafa998f712015-03-19 22:31:13 +00001022
Davidlohr Bueso107d01f2018-07-16 13:26:13 -07001023 size = rounded_hashtable_size(&ht->p);
Herbert Xu3a324602015-12-16 18:13:14 +08001024
Thomas Graf97defe12015-01-02 23:00:20 +01001025 if (params->locks_mul)
1026 ht->p.locks_mul = roundup_pow_of_two(params->locks_mul);
1027 else
1028 ht->p.locks_mul = BUCKET_LOCKS_PER_CPU;
1029
Herbert Xu31ccde22015-03-24 00:50:21 +11001030 ht->key_len = ht->p.key_len;
1031 if (!params->hashfn) {
1032 ht->p.hashfn = jhash;
1033
1034 if (!(ht->key_len & (sizeof(u32) - 1))) {
1035 ht->key_len /= sizeof(u32);
1036 ht->p.hashfn = rhashtable_jhash2;
1037 }
1038 }
1039
Davidlohr Bueso2d22ecf2018-08-21 22:01:48 -07001040 /*
1041 * This is api initialization and thus we need to guarantee the
1042 * initial rhashtable allocation. Upon failure, retry with the
1043 * smallest possible size with __GFP_NOFAIL semantics.
1044 */
Herbert Xub9ecfda2015-03-24 00:50:27 +11001045 tbl = bucket_table_alloc(ht, size, GFP_KERNEL);
Davidlohr Bueso2d22ecf2018-08-21 22:01:48 -07001046 if (unlikely(tbl == NULL)) {
1047 size = max_t(u16, ht->p.min_size, HASH_MIN_SIZE);
1048 tbl = bucket_table_alloc(ht, size, GFP_KERNEL | __GFP_NOFAIL);
1049 }
Thomas Graf7e1e7762014-08-02 11:47:44 +02001050
Ying Xue545a1482015-01-07 13:41:57 +08001051 atomic_set(&ht->nelems, 0);
Daniel Borkmanna5b68462015-03-12 15:28:40 +01001052
Thomas Graf7e1e7762014-08-02 11:47:44 +02001053 RCU_INIT_POINTER(ht->tbl, tbl);
1054
Daniel Borkmann4c4b52d2015-02-25 16:31:54 +01001055 INIT_WORK(&ht->run_work, rht_deferred_worker);
Thomas Graf97defe12015-01-02 23:00:20 +01001056
Thomas Graf7e1e7762014-08-02 11:47:44 +02001057 return 0;
1058}
1059EXPORT_SYMBOL_GPL(rhashtable_init);
1060
1061/**
Herbert Xuca268932016-09-19 19:00:09 +08001062 * rhltable_init - initialize a new hash list table
1063 * @hlt: hash list table to be initialized
1064 * @params: configuration parameters
1065 *
1066 * Initializes a new hash list table.
1067 *
1068 * See documentation for rhashtable_init.
1069 */
1070int rhltable_init(struct rhltable *hlt, const struct rhashtable_params *params)
1071{
1072 int err;
1073
Herbert Xuca268932016-09-19 19:00:09 +08001074 err = rhashtable_init(&hlt->ht, params);
1075 hlt->ht.rhlist = true;
1076 return err;
1077}
1078EXPORT_SYMBOL_GPL(rhltable_init);
1079
1080static void rhashtable_free_one(struct rhashtable *ht, struct rhash_head *obj,
1081 void (*free_fn)(void *ptr, void *arg),
1082 void *arg)
1083{
1084 struct rhlist_head *list;
1085
1086 if (!ht->rhlist) {
1087 free_fn(rht_obj(ht, obj), arg);
1088 return;
1089 }
1090
1091 list = container_of(obj, struct rhlist_head, rhead);
1092 do {
1093 obj = &list->rhead;
1094 list = rht_dereference(list->next, ht);
1095 free_fn(rht_obj(ht, obj), arg);
1096 } while (list);
1097}
1098
1099/**
Thomas Graf6b6f3022015-03-24 14:18:20 +01001100 * rhashtable_free_and_destroy - free elements and destroy hash table
Thomas Graf7e1e7762014-08-02 11:47:44 +02001101 * @ht: the hash table to destroy
Thomas Graf6b6f3022015-03-24 14:18:20 +01001102 * @free_fn: callback to release resources of element
1103 * @arg: pointer passed to free_fn
Thomas Graf7e1e7762014-08-02 11:47:44 +02001104 *
Thomas Graf6b6f3022015-03-24 14:18:20 +01001105 * Stops an eventual async resize. If defined, invokes free_fn for each
1106 * element to releasal resources. Please note that RCU protected
1107 * readers may still be accessing the elements. Releasing of resources
1108 * must occur in a compatible manner. Then frees the bucket array.
1109 *
1110 * This function will eventually sleep to wait for an async resize
1111 * to complete. The caller is responsible that no further write operations
1112 * occurs in parallel.
Thomas Graf7e1e7762014-08-02 11:47:44 +02001113 */
Thomas Graf6b6f3022015-03-24 14:18:20 +01001114void rhashtable_free_and_destroy(struct rhashtable *ht,
1115 void (*free_fn)(void *ptr, void *arg),
1116 void *arg)
Thomas Graf7e1e7762014-08-02 11:47:44 +02001117{
Taehee Yoo00261292018-07-08 11:55:51 +09001118 struct bucket_table *tbl, *next_tbl;
Thomas Graf6b6f3022015-03-24 14:18:20 +01001119 unsigned int i;
Thomas Graf97defe12015-01-02 23:00:20 +01001120
Daniel Borkmann4c4b52d2015-02-25 16:31:54 +01001121 cancel_work_sync(&ht->run_work);
Ying Xue57699a42015-01-16 11:13:09 +08001122
Thomas Graf97defe12015-01-02 23:00:20 +01001123 mutex_lock(&ht->mutex);
Thomas Graf6b6f3022015-03-24 14:18:20 +01001124 tbl = rht_dereference(ht->tbl, ht);
Taehee Yoo00261292018-07-08 11:55:51 +09001125restart:
Thomas Graf6b6f3022015-03-24 14:18:20 +01001126 if (free_fn) {
1127 for (i = 0; i < tbl->size; i++) {
1128 struct rhash_head *pos, *next;
1129
Eric Dumazetae6da1f2018-03-31 12:58:48 -07001130 cond_resched();
Herbert Xuda204202017-02-11 19:26:47 +08001131 for (pos = rht_dereference(*rht_bucket(tbl, i), ht),
Thomas Graf6b6f3022015-03-24 14:18:20 +01001132 next = !rht_is_a_nulls(pos) ?
1133 rht_dereference(pos->next, ht) : NULL;
1134 !rht_is_a_nulls(pos);
1135 pos = next,
1136 next = !rht_is_a_nulls(pos) ?
1137 rht_dereference(pos->next, ht) : NULL)
Herbert Xuca268932016-09-19 19:00:09 +08001138 rhashtable_free_one(ht, pos, free_fn, arg);
Thomas Graf6b6f3022015-03-24 14:18:20 +01001139 }
1140 }
1141
Taehee Yoo00261292018-07-08 11:55:51 +09001142 next_tbl = rht_dereference(tbl->future_tbl, ht);
Thomas Graf6b6f3022015-03-24 14:18:20 +01001143 bucket_table_free(tbl);
Taehee Yoo00261292018-07-08 11:55:51 +09001144 if (next_tbl) {
1145 tbl = next_tbl;
1146 goto restart;
1147 }
Thomas Graf97defe12015-01-02 23:00:20 +01001148 mutex_unlock(&ht->mutex);
Thomas Graf7e1e7762014-08-02 11:47:44 +02001149}
Thomas Graf6b6f3022015-03-24 14:18:20 +01001150EXPORT_SYMBOL_GPL(rhashtable_free_and_destroy);
1151
1152void rhashtable_destroy(struct rhashtable *ht)
1153{
1154 return rhashtable_free_and_destroy(ht, NULL, NULL);
1155}
Thomas Graf7e1e7762014-08-02 11:47:44 +02001156EXPORT_SYMBOL_GPL(rhashtable_destroy);
Herbert Xuda204202017-02-11 19:26:47 +08001157
1158struct rhash_head __rcu **rht_bucket_nested(const struct bucket_table *tbl,
1159 unsigned int hash)
1160{
1161 const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *));
NeilBrown82208d0d2018-11-30 10:26:50 +11001162 static struct rhash_head __rcu *rhnull;
Herbert Xuda204202017-02-11 19:26:47 +08001163 unsigned int index = hash & ((1 << tbl->nest) - 1);
1164 unsigned int size = tbl->size >> tbl->nest;
1165 unsigned int subhash = hash;
1166 union nested_table *ntbl;
1167
1168 ntbl = (union nested_table *)rcu_dereference_raw(tbl->buckets[0]);
Herbert Xuc4d26032017-02-25 22:39:50 +08001169 ntbl = rht_dereference_bucket_rcu(ntbl[index].table, tbl, hash);
Herbert Xuda204202017-02-11 19:26:47 +08001170 subhash >>= tbl->nest;
1171
1172 while (ntbl && size > (1 << shift)) {
1173 index = subhash & ((1 << shift) - 1);
Herbert Xuc4d26032017-02-25 22:39:50 +08001174 ntbl = rht_dereference_bucket_rcu(ntbl[index].table,
1175 tbl, hash);
Herbert Xuda204202017-02-11 19:26:47 +08001176 size >>= shift;
1177 subhash >>= shift;
1178 }
1179
NeilBrown82208d0d2018-11-30 10:26:50 +11001180 if (!ntbl) {
1181 if (!rhnull)
1182 INIT_RHT_NULLS_HEAD(rhnull);
Herbert Xuda204202017-02-11 19:26:47 +08001183 return &rhnull;
NeilBrown82208d0d2018-11-30 10:26:50 +11001184 }
Herbert Xuda204202017-02-11 19:26:47 +08001185
1186 return &ntbl[subhash].bucket;
1187
1188}
1189EXPORT_SYMBOL_GPL(rht_bucket_nested);
1190
1191struct rhash_head __rcu **rht_bucket_nested_insert(struct rhashtable *ht,
1192 struct bucket_table *tbl,
1193 unsigned int hash)
1194{
1195 const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *));
1196 unsigned int index = hash & ((1 << tbl->nest) - 1);
1197 unsigned int size = tbl->size >> tbl->nest;
1198 union nested_table *ntbl;
Herbert Xuda204202017-02-11 19:26:47 +08001199
1200 ntbl = (union nested_table *)rcu_dereference_raw(tbl->buckets[0]);
1201 hash >>= tbl->nest;
Herbert Xuda204202017-02-11 19:26:47 +08001202 ntbl = nested_table_alloc(ht, &ntbl[index].table,
NeilBrown5af68ef2018-06-18 12:52:50 +10001203 size <= (1 << shift));
Herbert Xuda204202017-02-11 19:26:47 +08001204
1205 while (ntbl && size > (1 << shift)) {
1206 index = hash & ((1 << shift) - 1);
1207 size >>= shift;
1208 hash >>= shift;
Herbert Xuda204202017-02-11 19:26:47 +08001209 ntbl = nested_table_alloc(ht, &ntbl[index].table,
NeilBrown5af68ef2018-06-18 12:52:50 +10001210 size <= (1 << shift));
Herbert Xuda204202017-02-11 19:26:47 +08001211 }
1212
1213 if (!ntbl)
1214 return NULL;
1215
1216 return &ntbl[hash].bucket;
1217
1218}
1219EXPORT_SYMBOL_GPL(rht_bucket_nested_insert);