blob: e96fc00208bc9f2719cacc2262e506c8045c6c0c [file] [log] [blame]
Thomas Graf7e1e7762014-08-02 11:47:44 +02001/*
2 * Resizable, Scalable, Concurrent Hash Table
3 *
Thomas Grafa5ec68e2015-02-05 02:03:32 +01004 * Copyright (c) 2014-2015 Thomas Graf <tgraf@suug.ch>
Thomas Graf7e1e7762014-08-02 11:47:44 +02005 * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
6 *
7 * Based on the following paper:
8 * https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
9 *
10 * Code partially derived from nft_hash
11 *
12 * This program is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU General Public License version 2 as
14 * published by the Free Software Foundation.
15 */
16
17#include <linux/kernel.h>
18#include <linux/init.h>
19#include <linux/log2.h>
20#include <linux/slab.h>
21#include <linux/vmalloc.h>
22#include <linux/mm.h>
Daniel Borkmann87545892014-12-10 16:33:11 +010023#include <linux/jhash.h>
Thomas Graf7e1e7762014-08-02 11:47:44 +020024#include <linux/random.h>
25#include <linux/rhashtable.h>
Thomas Graf7e1e7762014-08-02 11:47:44 +020026
27#define HASH_DEFAULT_SIZE 64UL
28#define HASH_MIN_SIZE 4UL
Thomas Graf97defe12015-01-02 23:00:20 +010029#define BUCKET_LOCKS_PER_CPU 128UL
30
Thomas Graff89bd6f2015-01-02 23:00:21 +010031/* Base bits plus 1 bit for nulls marker */
32#define HASH_RESERVED_SPACE (RHT_BASE_BITS + 1)
33
Thomas Graf97defe12015-01-02 23:00:20 +010034enum {
35 RHT_LOCK_NORMAL,
36 RHT_LOCK_NESTED,
Thomas Graf97defe12015-01-02 23:00:20 +010037};
38
39/* The bucket lock is selected based on the hash and protects mutations
40 * on a group of hash buckets.
41 *
Thomas Grafa5ec68e2015-02-05 02:03:32 +010042 * A maximum of tbl->size/2 bucket locks is allocated. This ensures that
43 * a single lock always covers both buckets which may both contains
44 * entries which link to the same bucket of the old table during resizing.
45 * This allows to simplify the locking as locking the bucket in both
46 * tables during resize always guarantee protection.
47 *
Thomas Graf97defe12015-01-02 23:00:20 +010048 * IMPORTANT: When holding the bucket lock of both the old and new table
49 * during expansions and shrinking, the old bucket lock must always be
50 * acquired first.
51 */
52static spinlock_t *bucket_lock(const struct bucket_table *tbl, u32 hash)
53{
54 return &tbl->locks[hash & tbl->locks_mask];
55}
Thomas Graf7e1e7762014-08-02 11:47:44 +020056
Thomas Grafc91eee52014-08-13 16:38:30 +020057static void *rht_obj(const struct rhashtable *ht, const struct rhash_head *he)
Thomas Graf7e1e7762014-08-02 11:47:44 +020058{
59 return (void *) he - ht->p.head_offset;
60}
Thomas Graf7e1e7762014-08-02 11:47:44 +020061
Thomas Graf8d24c0b2015-01-02 23:00:14 +010062static u32 rht_bucket_index(const struct bucket_table *tbl, u32 hash)
Thomas Graf7e1e7762014-08-02 11:47:44 +020063{
Thomas Graf8d24c0b2015-01-02 23:00:14 +010064 return hash & (tbl->size - 1);
Thomas Graf7e1e7762014-08-02 11:47:44 +020065}
66
Thomas Graf8d24c0b2015-01-02 23:00:14 +010067static u32 obj_raw_hashfn(const struct rhashtable *ht, const void *ptr)
68{
69 u32 hash;
70
71 if (unlikely(!ht->p.key_len))
72 hash = ht->p.obj_hashfn(ptr, ht->p.hash_rnd);
73 else
74 hash = ht->p.hashfn(ptr + ht->p.key_offset, ht->p.key_len,
75 ht->p.hash_rnd);
76
Thomas Graff89bd6f2015-01-02 23:00:21 +010077 return hash >> HASH_RESERVED_SPACE;
Thomas Graf8d24c0b2015-01-02 23:00:14 +010078}
79
Thomas Graf97defe12015-01-02 23:00:20 +010080static u32 key_hashfn(struct rhashtable *ht, const void *key, u32 len)
Thomas Graf7e1e7762014-08-02 11:47:44 +020081{
Thomas Grafc88455c2015-02-05 02:03:31 +010082 return ht->p.hashfn(key, len, ht->p.hash_rnd) >> HASH_RESERVED_SPACE;
Thomas Graf7e1e7762014-08-02 11:47:44 +020083}
Thomas Graf7e1e7762014-08-02 11:47:44 +020084
85static u32 head_hashfn(const struct rhashtable *ht,
Thomas Graf8d24c0b2015-01-02 23:00:14 +010086 const struct bucket_table *tbl,
87 const struct rhash_head *he)
Thomas Graf7e1e7762014-08-02 11:47:44 +020088{
Thomas Graf8d24c0b2015-01-02 23:00:14 +010089 return rht_bucket_index(tbl, obj_raw_hashfn(ht, rht_obj(ht, he)));
Thomas Graf7e1e7762014-08-02 11:47:44 +020090}
91
Thomas Grafa03eaec2015-02-05 02:03:34 +010092#ifdef CONFIG_PROVE_LOCKING
93static void debug_dump_buckets(const struct rhashtable *ht,
94 const struct bucket_table *tbl)
95{
96 struct rhash_head *he;
97 unsigned int i, hash;
98
99 for (i = 0; i < tbl->size; i++) {
100 pr_warn(" [Bucket %d] ", i);
101 rht_for_each_rcu(he, tbl, i) {
102 hash = head_hashfn(ht, tbl, he);
103 pr_cont("[hash = %#x, lock = %p] ",
104 hash, bucket_lock(tbl, hash));
105 }
106 pr_cont("\n");
107 }
108
109}
110
111static void debug_dump_table(struct rhashtable *ht,
112 const struct bucket_table *tbl,
113 unsigned int hash)
114{
115 struct bucket_table *old_tbl, *future_tbl;
116
117 pr_emerg("BUG: lock for hash %#x in table %p not held\n",
118 hash, tbl);
119
120 rcu_read_lock();
121 future_tbl = rht_dereference_rcu(ht->future_tbl, ht);
122 old_tbl = rht_dereference_rcu(ht->tbl, ht);
123 if (future_tbl != old_tbl) {
124 pr_warn("Future table %p (size: %zd)\n",
125 future_tbl, future_tbl->size);
126 debug_dump_buckets(ht, future_tbl);
127 }
128
129 pr_warn("Table %p (size: %zd)\n", old_tbl, old_tbl->size);
130 debug_dump_buckets(ht, old_tbl);
131
132 rcu_read_unlock();
133}
134
135#define ASSERT_RHT_MUTEX(HT) BUG_ON(!lockdep_rht_mutex_is_held(HT))
136#define ASSERT_BUCKET_LOCK(HT, TBL, HASH) \
137 do { \
138 if (unlikely(!lockdep_rht_bucket_is_held(TBL, HASH))) { \
139 debug_dump_table(HT, TBL, HASH); \
140 BUG(); \
141 } \
142 } while (0)
143
144int lockdep_rht_mutex_is_held(struct rhashtable *ht)
145{
146 return (debug_locks) ? lockdep_is_held(&ht->mutex) : 1;
147}
148EXPORT_SYMBOL_GPL(lockdep_rht_mutex_is_held);
149
150int lockdep_rht_bucket_is_held(const struct bucket_table *tbl, u32 hash)
151{
152 spinlock_t *lock = bucket_lock(tbl, hash);
153
154 return (debug_locks) ? lockdep_is_held(lock) : 1;
155}
156EXPORT_SYMBOL_GPL(lockdep_rht_bucket_is_held);
157#else
158#define ASSERT_RHT_MUTEX(HT)
159#define ASSERT_BUCKET_LOCK(HT, TBL, HASH)
160#endif
161
162
Thomas Grafb8e19432015-01-02 23:00:17 +0100163static struct rhash_head __rcu **bucket_tail(struct bucket_table *tbl, u32 n)
164{
165 struct rhash_head __rcu **pprev;
166
167 for (pprev = &tbl->buckets[n];
Thomas Graff89bd6f2015-01-02 23:00:21 +0100168 !rht_is_a_nulls(rht_dereference_bucket(*pprev, tbl, n));
Thomas Grafb8e19432015-01-02 23:00:17 +0100169 pprev = &rht_dereference_bucket(*pprev, tbl, n)->next)
170 ;
171
172 return pprev;
173}
174
Thomas Graf97defe12015-01-02 23:00:20 +0100175static int alloc_bucket_locks(struct rhashtable *ht, struct bucket_table *tbl)
176{
177 unsigned int i, size;
178#if defined(CONFIG_PROVE_LOCKING)
179 unsigned int nr_pcpus = 2;
180#else
181 unsigned int nr_pcpus = num_possible_cpus();
182#endif
183
184 nr_pcpus = min_t(unsigned int, nr_pcpus, 32UL);
185 size = roundup_pow_of_two(nr_pcpus * ht->p.locks_mul);
186
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100187 /* Never allocate more than 0.5 locks per bucket */
188 size = min_t(unsigned int, size, tbl->size >> 1);
Thomas Graf97defe12015-01-02 23:00:20 +0100189
190 if (sizeof(spinlock_t) != 0) {
191#ifdef CONFIG_NUMA
192 if (size * sizeof(spinlock_t) > PAGE_SIZE)
193 tbl->locks = vmalloc(size * sizeof(spinlock_t));
194 else
195#endif
196 tbl->locks = kmalloc_array(size, sizeof(spinlock_t),
197 GFP_KERNEL);
198 if (!tbl->locks)
199 return -ENOMEM;
200 for (i = 0; i < size; i++)
201 spin_lock_init(&tbl->locks[i]);
202 }
203 tbl->locks_mask = size - 1;
204
205 return 0;
206}
207
208static void bucket_table_free(const struct bucket_table *tbl)
209{
210 if (tbl)
211 kvfree(tbl->locks);
212
213 kvfree(tbl);
214}
215
216static struct bucket_table *bucket_table_alloc(struct rhashtable *ht,
217 size_t nbuckets)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200218{
219 struct bucket_table *tbl;
220 size_t size;
Thomas Graff89bd6f2015-01-02 23:00:21 +0100221 int i;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200222
223 size = sizeof(*tbl) + nbuckets * sizeof(tbl->buckets[0]);
Thomas Graf6eba8222014-11-13 13:45:46 +0100224 tbl = kzalloc(size, GFP_KERNEL | __GFP_NOWARN);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200225 if (tbl == NULL)
226 tbl = vzalloc(size);
227
228 if (tbl == NULL)
229 return NULL;
230
231 tbl->size = nbuckets;
232
Thomas Graf97defe12015-01-02 23:00:20 +0100233 if (alloc_bucket_locks(ht, tbl) < 0) {
234 bucket_table_free(tbl);
235 return NULL;
236 }
Thomas Graf7e1e7762014-08-02 11:47:44 +0200237
Thomas Graff89bd6f2015-01-02 23:00:21 +0100238 for (i = 0; i < nbuckets; i++)
239 INIT_RHT_NULLS_HEAD(tbl->buckets[i], ht, i);
240
Thomas Graf97defe12015-01-02 23:00:20 +0100241 return tbl;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200242}
243
244/**
245 * rht_grow_above_75 - returns true if nelems > 0.75 * table-size
246 * @ht: hash table
247 * @new_size: new table size
248 */
249bool rht_grow_above_75(const struct rhashtable *ht, size_t new_size)
250{
251 /* Expand table when exceeding 75% load */
Ying Xuec0c09bf2015-01-07 13:41:56 +0800252 return atomic_read(&ht->nelems) > (new_size / 4 * 3) &&
253 (ht->p.max_shift && atomic_read(&ht->shift) < ht->p.max_shift);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200254}
255EXPORT_SYMBOL_GPL(rht_grow_above_75);
256
257/**
258 * rht_shrink_below_30 - returns true if nelems < 0.3 * table-size
259 * @ht: hash table
260 * @new_size: new table size
261 */
262bool rht_shrink_below_30(const struct rhashtable *ht, size_t new_size)
263{
264 /* Shrink table beneath 30% load */
Ying Xuec0c09bf2015-01-07 13:41:56 +0800265 return atomic_read(&ht->nelems) < (new_size * 3 / 10) &&
266 (atomic_read(&ht->shift) > ht->p.min_shift);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200267}
268EXPORT_SYMBOL_GPL(rht_shrink_below_30);
269
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100270static void lock_buckets(struct bucket_table *new_tbl,
271 struct bucket_table *old_tbl, unsigned int hash)
272 __acquires(old_bucket_lock)
273{
274 spin_lock_bh(bucket_lock(old_tbl, hash));
275 if (new_tbl != old_tbl)
276 spin_lock_bh_nested(bucket_lock(new_tbl, hash),
277 RHT_LOCK_NESTED);
278}
279
280static void unlock_buckets(struct bucket_table *new_tbl,
281 struct bucket_table *old_tbl, unsigned int hash)
282 __releases(old_bucket_lock)
283{
284 if (new_tbl != old_tbl)
285 spin_unlock_bh(bucket_lock(new_tbl, hash));
286 spin_unlock_bh(bucket_lock(old_tbl, hash));
287}
288
289/**
290 * Unlink entries on bucket which hash to different bucket.
291 *
292 * Returns true if no more work needs to be performed on the bucket.
293 */
Thomas Grafa03eaec2015-02-05 02:03:34 +0100294static bool hashtable_chain_unzip(struct rhashtable *ht,
Thomas Graf7e1e7762014-08-02 11:47:44 +0200295 const struct bucket_table *new_tbl,
Thomas Graf97defe12015-01-02 23:00:20 +0100296 struct bucket_table *old_tbl,
297 size_t old_hash)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200298{
299 struct rhash_head *he, *p, *next;
Thomas Graf97defe12015-01-02 23:00:20 +0100300 unsigned int new_hash, new_hash2;
301
Thomas Grafa03eaec2015-02-05 02:03:34 +0100302 ASSERT_BUCKET_LOCK(ht, old_tbl, old_hash);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200303
304 /* Old bucket empty, no work needed. */
Thomas Graf97defe12015-01-02 23:00:20 +0100305 p = rht_dereference_bucket(old_tbl->buckets[old_hash], old_tbl,
306 old_hash);
Thomas Graff89bd6f2015-01-02 23:00:21 +0100307 if (rht_is_a_nulls(p))
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100308 return false;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200309
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100310 new_hash = head_hashfn(ht, new_tbl, p);
Thomas Grafa03eaec2015-02-05 02:03:34 +0100311 ASSERT_BUCKET_LOCK(ht, new_tbl, new_hash);
Thomas Graf97defe12015-01-02 23:00:20 +0100312
Thomas Graf7e1e7762014-08-02 11:47:44 +0200313 /* Advance the old bucket pointer one or more times until it
314 * reaches a node that doesn't hash to the same bucket as the
315 * previous node p. Call the previous node p;
316 */
Thomas Graf97defe12015-01-02 23:00:20 +0100317 rht_for_each_continue(he, p->next, old_tbl, old_hash) {
318 new_hash2 = head_hashfn(ht, new_tbl, he);
Thomas Grafa03eaec2015-02-05 02:03:34 +0100319 ASSERT_BUCKET_LOCK(ht, new_tbl, new_hash2);
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100320
Thomas Graf97defe12015-01-02 23:00:20 +0100321 if (new_hash != new_hash2)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200322 break;
323 p = he;
324 }
Thomas Graf97defe12015-01-02 23:00:20 +0100325 rcu_assign_pointer(old_tbl->buckets[old_hash], p->next);
326
Thomas Graf7e1e7762014-08-02 11:47:44 +0200327 /* Find the subsequent node which does hash to the same
328 * bucket as node P, or NULL if no such node exists.
329 */
Thomas Graff89bd6f2015-01-02 23:00:21 +0100330 INIT_RHT_NULLS_HEAD(next, ht, old_hash);
331 if (!rht_is_a_nulls(he)) {
Thomas Graf97defe12015-01-02 23:00:20 +0100332 rht_for_each_continue(he, he->next, old_tbl, old_hash) {
333 if (head_hashfn(ht, new_tbl, he) == new_hash) {
Thomas Graf7e1e7762014-08-02 11:47:44 +0200334 next = he;
335 break;
336 }
337 }
338 }
339
340 /* Set p's next pointer to that subsequent node pointer,
341 * bypassing the nodes which do not hash to p's bucket
342 */
Thomas Graf97defe12015-01-02 23:00:20 +0100343 rcu_assign_pointer(p->next, next);
344
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100345 p = rht_dereference_bucket(old_tbl->buckets[old_hash], old_tbl,
346 old_hash);
347
348 return !rht_is_a_nulls(p);
Thomas Graf97defe12015-01-02 23:00:20 +0100349}
350
Thomas Graf7cd10db2015-02-05 02:03:35 +0100351static void link_old_to_new(struct rhashtable *ht, struct bucket_table *new_tbl,
Thomas Graf97defe12015-01-02 23:00:20 +0100352 unsigned int new_hash, struct rhash_head *entry)
353{
Thomas Graf7cd10db2015-02-05 02:03:35 +0100354 ASSERT_BUCKET_LOCK(ht, new_tbl, new_hash);
355
Thomas Graf97defe12015-01-02 23:00:20 +0100356 rcu_assign_pointer(*bucket_tail(new_tbl, new_hash), entry);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200357}
358
359/**
360 * rhashtable_expand - Expand hash table while allowing concurrent lookups
361 * @ht: the hash table to expand
Thomas Graf7e1e7762014-08-02 11:47:44 +0200362 *
363 * A secondary bucket array is allocated and the hash entries are migrated
364 * while keeping them on both lists until the end of the RCU grace period.
365 *
366 * This function may only be called in a context where it is safe to call
367 * synchronize_rcu(), e.g. not within a rcu_read_lock() section.
368 *
Thomas Graf97defe12015-01-02 23:00:20 +0100369 * The caller must ensure that no concurrent resizing occurs by holding
370 * ht->mutex.
371 *
372 * It is valid to have concurrent insertions and deletions protected by per
373 * bucket locks or concurrent RCU protected lookups and traversals.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200374 */
Thomas Graf6eba8222014-11-13 13:45:46 +0100375int rhashtable_expand(struct rhashtable *ht)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200376{
377 struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);
378 struct rhash_head *he;
Thomas Graf97defe12015-01-02 23:00:20 +0100379 unsigned int new_hash, old_hash;
380 bool complete = false;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200381
382 ASSERT_RHT_MUTEX(ht);
383
Thomas Graf97defe12015-01-02 23:00:20 +0100384 new_tbl = bucket_table_alloc(ht, old_tbl->size * 2);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200385 if (new_tbl == NULL)
386 return -ENOMEM;
387
Ying Xuec0c09bf2015-01-07 13:41:56 +0800388 atomic_inc(&ht->shift);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200389
Thomas Graf97defe12015-01-02 23:00:20 +0100390 /* Make insertions go into the new, empty table right away. Deletions
391 * and lookups will be attempted in both tables until we synchronize.
392 * The synchronize_rcu() guarantees for the new table to be picked up
393 * so no new additions go into the old table while we relink.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200394 */
Thomas Graf97defe12015-01-02 23:00:20 +0100395 rcu_assign_pointer(ht->future_tbl, new_tbl);
396 synchronize_rcu();
397
398 /* For each new bucket, search the corresponding old bucket for the
399 * first entry that hashes to the new bucket, and link the end of
400 * newly formed bucket chain (containing entries added to future
401 * table) to that entry. Since all the entries which will end up in
402 * the new bucket appear in the same old bucket, this constructs an
403 * entirely valid new hash table, but with multiple buckets
404 * "zipped" together into a single imprecise chain.
405 */
406 for (new_hash = 0; new_hash < new_tbl->size; new_hash++) {
407 old_hash = rht_bucket_index(old_tbl, new_hash);
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100408 lock_buckets(new_tbl, old_tbl, new_hash);
Thomas Graf97defe12015-01-02 23:00:20 +0100409 rht_for_each(he, old_tbl, old_hash) {
410 if (head_hashfn(ht, new_tbl, he) == new_hash) {
Thomas Graf7cd10db2015-02-05 02:03:35 +0100411 link_old_to_new(ht, new_tbl, new_hash, he);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200412 break;
413 }
414 }
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100415 unlock_buckets(new_tbl, old_tbl, new_hash);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200416 }
417
Thomas Graf7e1e7762014-08-02 11:47:44 +0200418 /* Unzip interleaved hash chains */
Thomas Graf97defe12015-01-02 23:00:20 +0100419 while (!complete && !ht->being_destroyed) {
Thomas Graf7e1e7762014-08-02 11:47:44 +0200420 /* Wait for readers. All new readers will see the new
421 * table, and thus no references to the old table will
422 * remain.
423 */
424 synchronize_rcu();
425
426 /* For each bucket in the old table (each of which
427 * contains items from multiple buckets of the new
428 * table): ...
429 */
430 complete = true;
Thomas Graf97defe12015-01-02 23:00:20 +0100431 for (old_hash = 0; old_hash < old_tbl->size; old_hash++) {
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100432 lock_buckets(new_tbl, old_tbl, old_hash);
Thomas Graff89bd6f2015-01-02 23:00:21 +0100433
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100434 if (hashtable_chain_unzip(ht, new_tbl, old_tbl,
435 old_hash))
Thomas Graf7e1e7762014-08-02 11:47:44 +0200436 complete = false;
Thomas Graf97defe12015-01-02 23:00:20 +0100437
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100438 unlock_buckets(new_tbl, old_tbl, old_hash);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200439 }
Thomas Graf97defe12015-01-02 23:00:20 +0100440 }
Thomas Graf7e1e7762014-08-02 11:47:44 +0200441
Thomas Grafcf52d522015-02-05 02:03:36 +0100442 rcu_assign_pointer(ht->tbl, new_tbl);
Thomas Graf2af4b522015-02-05 02:03:33 +0100443 synchronize_rcu();
444
Thomas Graf7e1e7762014-08-02 11:47:44 +0200445 bucket_table_free(old_tbl);
446 return 0;
447}
448EXPORT_SYMBOL_GPL(rhashtable_expand);
449
450/**
451 * rhashtable_shrink - Shrink hash table while allowing concurrent lookups
452 * @ht: the hash table to shrink
Thomas Graf7e1e7762014-08-02 11:47:44 +0200453 *
454 * This function may only be called in a context where it is safe to call
455 * synchronize_rcu(), e.g. not within a rcu_read_lock() section.
456 *
Thomas Graf97defe12015-01-02 23:00:20 +0100457 * The caller must ensure that no concurrent resizing occurs by holding
458 * ht->mutex.
459 *
Thomas Graf7e1e7762014-08-02 11:47:44 +0200460 * The caller must ensure that no concurrent table mutations take place.
461 * It is however valid to have concurrent lookups if they are RCU protected.
Thomas Graf97defe12015-01-02 23:00:20 +0100462 *
463 * It is valid to have concurrent insertions and deletions protected by per
464 * bucket locks or concurrent RCU protected lookups and traversals.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200465 */
Thomas Graf6eba8222014-11-13 13:45:46 +0100466int rhashtable_shrink(struct rhashtable *ht)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200467{
Thomas Graf97defe12015-01-02 23:00:20 +0100468 struct bucket_table *new_tbl, *tbl = rht_dereference(ht->tbl, ht);
Thomas Graf97defe12015-01-02 23:00:20 +0100469 unsigned int new_hash;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200470
471 ASSERT_RHT_MUTEX(ht);
472
Thomas Graf97defe12015-01-02 23:00:20 +0100473 new_tbl = bucket_table_alloc(ht, tbl->size / 2);
474 if (new_tbl == NULL)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200475 return -ENOMEM;
476
Thomas Graf97defe12015-01-02 23:00:20 +0100477 rcu_assign_pointer(ht->future_tbl, new_tbl);
478 synchronize_rcu();
Thomas Graf7e1e7762014-08-02 11:47:44 +0200479
Thomas Graf97defe12015-01-02 23:00:20 +0100480 /* Link the first entry in the old bucket to the end of the
481 * bucket in the new table. As entries are concurrently being
482 * added to the new table, lock down the new bucket. As we
483 * always divide the size in half when shrinking, each bucket
484 * in the new table maps to exactly two buckets in the old
485 * table.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200486 */
Thomas Graf97defe12015-01-02 23:00:20 +0100487 for (new_hash = 0; new_hash < new_tbl->size; new_hash++) {
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100488 lock_buckets(new_tbl, tbl, new_hash);
Thomas Graf97defe12015-01-02 23:00:20 +0100489
490 rcu_assign_pointer(*bucket_tail(new_tbl, new_hash),
491 tbl->buckets[new_hash]);
Thomas Graf7cd10db2015-02-05 02:03:35 +0100492 ASSERT_BUCKET_LOCK(ht, tbl, new_hash + new_tbl->size);
Thomas Graf97defe12015-01-02 23:00:20 +0100493 rcu_assign_pointer(*bucket_tail(new_tbl, new_hash),
494 tbl->buckets[new_hash + new_tbl->size]);
495
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100496 unlock_buckets(new_tbl, tbl, new_hash);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200497 }
498
499 /* Publish the new, valid hash table */
Thomas Graf97defe12015-01-02 23:00:20 +0100500 rcu_assign_pointer(ht->tbl, new_tbl);
Ying Xuec0c09bf2015-01-07 13:41:56 +0800501 atomic_dec(&ht->shift);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200502
503 /* Wait for readers. No new readers will have references to the
504 * old hash table.
505 */
506 synchronize_rcu();
507
508 bucket_table_free(tbl);
509
510 return 0;
511}
512EXPORT_SYMBOL_GPL(rhashtable_shrink);
513
Thomas Graf97defe12015-01-02 23:00:20 +0100514static void rht_deferred_worker(struct work_struct *work)
515{
516 struct rhashtable *ht;
517 struct bucket_table *tbl;
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100518 struct rhashtable_walker *walker;
Thomas Graf97defe12015-01-02 23:00:20 +0100519
Ying Xue57699a42015-01-16 11:13:09 +0800520 ht = container_of(work, struct rhashtable, run_work);
Thomas Graf97defe12015-01-02 23:00:20 +0100521 mutex_lock(&ht->mutex);
Herbert Xu28134a52015-02-04 07:33:22 +1100522 if (ht->being_destroyed)
523 goto unlock;
524
Thomas Graf97defe12015-01-02 23:00:20 +0100525 tbl = rht_dereference(ht->tbl, ht);
526
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100527 list_for_each_entry(walker, &ht->walkers, list)
528 walker->resize = true;
529
Thomas Graf97defe12015-01-02 23:00:20 +0100530 if (ht->p.grow_decision && ht->p.grow_decision(ht, tbl->size))
531 rhashtable_expand(ht);
532 else if (ht->p.shrink_decision && ht->p.shrink_decision(ht, tbl->size))
533 rhashtable_shrink(ht);
534
Herbert Xu28134a52015-02-04 07:33:22 +1100535unlock:
Thomas Graf97defe12015-01-02 23:00:20 +0100536 mutex_unlock(&ht->mutex);
537}
538
Ying Xue54c5b7d2015-01-07 13:41:53 +0800539static void rhashtable_wakeup_worker(struct rhashtable *ht)
540{
541 struct bucket_table *tbl = rht_dereference_rcu(ht->tbl, ht);
542 struct bucket_table *new_tbl = rht_dereference_rcu(ht->future_tbl, ht);
543 size_t size = tbl->size;
544
545 /* Only adjust the table if no resizing is currently in progress. */
546 if (tbl == new_tbl &&
547 ((ht->p.grow_decision && ht->p.grow_decision(ht, size)) ||
548 (ht->p.shrink_decision && ht->p.shrink_decision(ht, size))))
Ying Xue57699a42015-01-16 11:13:09 +0800549 schedule_work(&ht->run_work);
Ying Xue54c5b7d2015-01-07 13:41:53 +0800550}
551
Ying Xuedb304852015-01-07 13:41:54 +0800552static void __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
553 struct bucket_table *tbl, u32 hash)
554{
Thomas Graf020219a2015-02-06 16:08:43 +0000555 struct rhash_head *head;
556
557 hash = rht_bucket_index(tbl, hash);
558 head = rht_dereference_bucket(tbl->buckets[hash], tbl, hash);
Ying Xuedb304852015-01-07 13:41:54 +0800559
Thomas Graf7cd10db2015-02-05 02:03:35 +0100560 ASSERT_BUCKET_LOCK(ht, tbl, hash);
561
Ying Xuedb304852015-01-07 13:41:54 +0800562 if (rht_is_a_nulls(head))
563 INIT_RHT_NULLS_HEAD(obj->next, ht, hash);
564 else
565 RCU_INIT_POINTER(obj->next, head);
566
567 rcu_assign_pointer(tbl->buckets[hash], obj);
568
569 atomic_inc(&ht->nelems);
570
571 rhashtable_wakeup_worker(ht);
572}
573
Thomas Graf7e1e7762014-08-02 11:47:44 +0200574/**
Ying Xuedb304852015-01-07 13:41:54 +0800575 * rhashtable_insert - insert object into hash table
Thomas Graf7e1e7762014-08-02 11:47:44 +0200576 * @ht: hash table
577 * @obj: pointer to hash head inside object
Thomas Graf7e1e7762014-08-02 11:47:44 +0200578 *
Thomas Graf97defe12015-01-02 23:00:20 +0100579 * Will take a per bucket spinlock to protect against mutual mutations
580 * on the same bucket. Multiple insertions may occur in parallel unless
581 * they map to the same bucket lock.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200582 *
Thomas Graf97defe12015-01-02 23:00:20 +0100583 * It is safe to call this function from atomic context.
584 *
585 * Will trigger an automatic deferred table resizing if the size grows
586 * beyond the watermark indicated by grow_decision() which can be passed
587 * to rhashtable_init().
Thomas Graf7e1e7762014-08-02 11:47:44 +0200588 */
Thomas Graf6eba8222014-11-13 13:45:46 +0100589void rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200590{
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100591 struct bucket_table *tbl, *old_tbl;
Thomas Graf97defe12015-01-02 23:00:20 +0100592 unsigned hash;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200593
Thomas Graf97defe12015-01-02 23:00:20 +0100594 rcu_read_lock();
Thomas Graf7e1e7762014-08-02 11:47:44 +0200595
Thomas Graf97defe12015-01-02 23:00:20 +0100596 tbl = rht_dereference_rcu(ht->future_tbl, ht);
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100597 old_tbl = rht_dereference_rcu(ht->tbl, ht);
Thomas Graf020219a2015-02-06 16:08:43 +0000598 hash = obj_raw_hashfn(ht, rht_obj(ht, obj));
Thomas Graf97defe12015-01-02 23:00:20 +0100599
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100600 lock_buckets(tbl, old_tbl, hash);
Ying Xuedb304852015-01-07 13:41:54 +0800601 __rhashtable_insert(ht, obj, tbl, hash);
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100602 unlock_buckets(tbl, old_tbl, hash);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200603
Thomas Graf97defe12015-01-02 23:00:20 +0100604 rcu_read_unlock();
Thomas Graf7e1e7762014-08-02 11:47:44 +0200605}
606EXPORT_SYMBOL_GPL(rhashtable_insert);
607
608/**
Thomas Graf7e1e7762014-08-02 11:47:44 +0200609 * rhashtable_remove - remove object from hash table
610 * @ht: hash table
611 * @obj: pointer to hash head inside object
Thomas Graf7e1e7762014-08-02 11:47:44 +0200612 *
613 * Since the hash chain is single linked, the removal operation needs to
614 * walk the bucket chain upon removal. The removal operation is thus
615 * considerable slow if the hash table is not correctly sized.
616 *
Ying Xuedb304852015-01-07 13:41:54 +0800617 * Will automatically shrink the table via rhashtable_expand() if the
Thomas Graf7e1e7762014-08-02 11:47:44 +0200618 * shrink_decision function specified at rhashtable_init() returns true.
619 *
620 * The caller must ensure that no concurrent table mutations occur. It is
621 * however valid to have concurrent lookups if they are RCU protected.
622 */
Thomas Graf6eba8222014-11-13 13:45:46 +0100623bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *obj)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200624{
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100625 struct bucket_table *tbl, *new_tbl, *old_tbl;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200626 struct rhash_head __rcu **pprev;
Thomas Grafcf52d522015-02-05 02:03:36 +0100627 struct rhash_head *he, *he2;
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100628 unsigned int hash, new_hash;
Thomas Graffe6a0432015-01-21 11:54:01 +0000629 bool ret = false;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200630
Thomas Graf97defe12015-01-02 23:00:20 +0100631 rcu_read_lock();
Thomas Graf020219a2015-02-06 16:08:43 +0000632 old_tbl = rht_dereference_rcu(ht->tbl, ht);
633 tbl = new_tbl = rht_dereference_rcu(ht->future_tbl, ht);
Thomas Grafcf52d522015-02-05 02:03:36 +0100634 new_hash = obj_raw_hashfn(ht, rht_obj(ht, obj));
Thomas Graf7e1e7762014-08-02 11:47:44 +0200635
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100636 lock_buckets(new_tbl, old_tbl, new_hash);
Thomas Graf97defe12015-01-02 23:00:20 +0100637restart:
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100638 hash = rht_bucket_index(tbl, new_hash);
Thomas Graf97defe12015-01-02 23:00:20 +0100639 pprev = &tbl->buckets[hash];
640 rht_for_each(he, tbl, hash) {
Thomas Graf7e1e7762014-08-02 11:47:44 +0200641 if (he != obj) {
642 pprev = &he->next;
643 continue;
644 }
645
Thomas Graf7cd10db2015-02-05 02:03:35 +0100646 ASSERT_BUCKET_LOCK(ht, tbl, hash);
Thomas Graf897362e2015-01-02 23:00:18 +0100647
Thomas Graf020219a2015-02-06 16:08:43 +0000648 if (old_tbl->size > new_tbl->size && tbl == old_tbl &&
649 !rht_is_a_nulls(obj->next) &&
650 head_hashfn(ht, tbl, obj->next) != hash) {
651 rcu_assign_pointer(*pprev, (struct rhash_head *) rht_marker(ht, hash));
652 } else if (unlikely(old_tbl->size < new_tbl->size && tbl == new_tbl)) {
653 rht_for_each_continue(he2, obj->next, tbl, hash) {
Thomas Grafcf52d522015-02-05 02:03:36 +0100654 if (head_hashfn(ht, tbl, he2) == hash) {
655 rcu_assign_pointer(*pprev, he2);
656 goto found;
657 }
658 }
659
Thomas Graf020219a2015-02-06 16:08:43 +0000660 rcu_assign_pointer(*pprev, (struct rhash_head *) rht_marker(ht, hash));
Thomas Grafcf52d522015-02-05 02:03:36 +0100661 } else {
662 rcu_assign_pointer(*pprev, obj->next);
663 }
664
665found:
Thomas Graffe6a0432015-01-21 11:54:01 +0000666 ret = true;
667 break;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200668 }
669
Thomas Graffe6a0432015-01-21 11:54:01 +0000670 /* The entry may be linked in either 'tbl', 'future_tbl', or both.
671 * 'future_tbl' only exists for a short period of time during
672 * resizing. Thus traversing both is fine and the added cost is
673 * very rare.
674 */
Thomas Graf020219a2015-02-06 16:08:43 +0000675 if (tbl != old_tbl) {
676 tbl = old_tbl;
Thomas Graf97defe12015-01-02 23:00:20 +0100677 goto restart;
678 }
679
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100680 unlock_buckets(new_tbl, old_tbl, new_hash);
Thomas Graffe6a0432015-01-21 11:54:01 +0000681
682 if (ret) {
683 atomic_dec(&ht->nelems);
684 rhashtable_wakeup_worker(ht);
685 }
686
Thomas Graf97defe12015-01-02 23:00:20 +0100687 rcu_read_unlock();
688
Thomas Graffe6a0432015-01-21 11:54:01 +0000689 return ret;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200690}
691EXPORT_SYMBOL_GPL(rhashtable_remove);
692
Ying Xueefb975a62015-01-07 13:41:52 +0800693struct rhashtable_compare_arg {
694 struct rhashtable *ht;
695 const void *key;
696};
697
698static bool rhashtable_compare(void *ptr, void *arg)
699{
700 struct rhashtable_compare_arg *x = arg;
701 struct rhashtable *ht = x->ht;
702
703 return !memcmp(ptr + ht->p.key_offset, x->key, ht->p.key_len);
704}
705
Thomas Graf7e1e7762014-08-02 11:47:44 +0200706/**
707 * rhashtable_lookup - lookup key in hash table
708 * @ht: hash table
709 * @key: pointer to key
710 *
711 * Computes the hash value for the key and traverses the bucket chain looking
712 * for a entry with an identical key. The first matching entry is returned.
713 *
714 * This lookup function may only be used for fixed key hash table (key_len
Ying Xuedb304852015-01-07 13:41:54 +0800715 * parameter set). It will BUG() if used inappropriately.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200716 *
Thomas Graf97defe12015-01-02 23:00:20 +0100717 * Lookups may occur in parallel with hashtable mutations and resizing.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200718 */
Thomas Graf97defe12015-01-02 23:00:20 +0100719void *rhashtable_lookup(struct rhashtable *ht, const void *key)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200720{
Ying Xueefb975a62015-01-07 13:41:52 +0800721 struct rhashtable_compare_arg arg = {
722 .ht = ht,
723 .key = key,
724 };
Thomas Graf7e1e7762014-08-02 11:47:44 +0200725
726 BUG_ON(!ht->p.key_len);
727
Ying Xueefb975a62015-01-07 13:41:52 +0800728 return rhashtable_lookup_compare(ht, key, &rhashtable_compare, &arg);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200729}
730EXPORT_SYMBOL_GPL(rhashtable_lookup);
731
732/**
733 * rhashtable_lookup_compare - search hash table with compare function
734 * @ht: hash table
Thomas Graf8d24c0b2015-01-02 23:00:14 +0100735 * @key: the pointer to the key
Thomas Graf7e1e7762014-08-02 11:47:44 +0200736 * @compare: compare function, must return true on match
737 * @arg: argument passed on to compare function
738 *
739 * Traverses the bucket chain behind the provided hash value and calls the
740 * specified compare function for each entry.
741 *
Thomas Graf97defe12015-01-02 23:00:20 +0100742 * Lookups may occur in parallel with hashtable mutations and resizing.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200743 *
744 * Returns the first entry on which the compare function returned true.
745 */
Thomas Graf97defe12015-01-02 23:00:20 +0100746void *rhashtable_lookup_compare(struct rhashtable *ht, const void *key,
Thomas Graf7e1e7762014-08-02 11:47:44 +0200747 bool (*compare)(void *, void *), void *arg)
748{
Thomas Graf97defe12015-01-02 23:00:20 +0100749 const struct bucket_table *tbl, *old_tbl;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200750 struct rhash_head *he;
Thomas Graf8d24c0b2015-01-02 23:00:14 +0100751 u32 hash;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200752
Thomas Graf97defe12015-01-02 23:00:20 +0100753 rcu_read_lock();
754
755 old_tbl = rht_dereference_rcu(ht->tbl, ht);
756 tbl = rht_dereference_rcu(ht->future_tbl, ht);
Thomas Graf8d24c0b2015-01-02 23:00:14 +0100757 hash = key_hashfn(ht, key, ht->p.key_len);
Thomas Graf97defe12015-01-02 23:00:20 +0100758restart:
759 rht_for_each_rcu(he, tbl, rht_bucket_index(tbl, hash)) {
Thomas Graf7e1e7762014-08-02 11:47:44 +0200760 if (!compare(rht_obj(ht, he), arg))
761 continue;
Thomas Graf97defe12015-01-02 23:00:20 +0100762 rcu_read_unlock();
Thomas Grafa4b18cd2015-01-02 23:00:15 +0100763 return rht_obj(ht, he);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200764 }
765
Thomas Graf97defe12015-01-02 23:00:20 +0100766 if (unlikely(tbl != old_tbl)) {
767 tbl = old_tbl;
768 goto restart;
769 }
770 rcu_read_unlock();
771
Thomas Graf7e1e7762014-08-02 11:47:44 +0200772 return NULL;
773}
774EXPORT_SYMBOL_GPL(rhashtable_lookup_compare);
775
Ying Xuedb304852015-01-07 13:41:54 +0800776/**
777 * rhashtable_lookup_insert - lookup and insert object into hash table
778 * @ht: hash table
779 * @obj: pointer to hash head inside object
780 *
781 * Locks down the bucket chain in both the old and new table if a resize
782 * is in progress to ensure that writers can't remove from the old table
783 * and can't insert to the new table during the atomic operation of search
784 * and insertion. Searches for duplicates in both the old and new table if
785 * a resize is in progress.
786 *
787 * This lookup function may only be used for fixed key hash table (key_len
788 * parameter set). It will BUG() if used inappropriately.
789 *
790 * It is safe to call this function from atomic context.
791 *
792 * Will trigger an automatic deferred table resizing if the size grows
793 * beyond the watermark indicated by grow_decision() which can be passed
794 * to rhashtable_init().
795 */
796bool rhashtable_lookup_insert(struct rhashtable *ht, struct rhash_head *obj)
797{
Ying Xue7a868d12015-01-12 14:52:22 +0800798 struct rhashtable_compare_arg arg = {
799 .ht = ht,
800 .key = rht_obj(ht, obj) + ht->p.key_offset,
801 };
802
803 BUG_ON(!ht->p.key_len);
804
805 return rhashtable_lookup_compare_insert(ht, obj, &rhashtable_compare,
806 &arg);
807}
808EXPORT_SYMBOL_GPL(rhashtable_lookup_insert);
809
810/**
811 * rhashtable_lookup_compare_insert - search and insert object to hash table
812 * with compare function
813 * @ht: hash table
814 * @obj: pointer to hash head inside object
815 * @compare: compare function, must return true on match
816 * @arg: argument passed on to compare function
817 *
818 * Locks down the bucket chain in both the old and new table if a resize
819 * is in progress to ensure that writers can't remove from the old table
820 * and can't insert to the new table during the atomic operation of search
821 * and insertion. Searches for duplicates in both the old and new table if
822 * a resize is in progress.
823 *
824 * Lookups may occur in parallel with hashtable mutations and resizing.
825 *
826 * Will trigger an automatic deferred table resizing if the size grows
827 * beyond the watermark indicated by grow_decision() which can be passed
828 * to rhashtable_init().
829 */
830bool rhashtable_lookup_compare_insert(struct rhashtable *ht,
831 struct rhash_head *obj,
832 bool (*compare)(void *, void *),
833 void *arg)
834{
Ying Xuedb304852015-01-07 13:41:54 +0800835 struct bucket_table *new_tbl, *old_tbl;
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100836 u32 new_hash;
Ying Xuedb304852015-01-07 13:41:54 +0800837 bool success = true;
838
839 BUG_ON(!ht->p.key_len);
840
841 rcu_read_lock();
Ying Xuedb304852015-01-07 13:41:54 +0800842 old_tbl = rht_dereference_rcu(ht->tbl, ht);
Ying Xuedb304852015-01-07 13:41:54 +0800843 new_tbl = rht_dereference_rcu(ht->future_tbl, ht);
Thomas Graf020219a2015-02-06 16:08:43 +0000844 new_hash = obj_raw_hashfn(ht, rht_obj(ht, obj));
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100845
846 lock_buckets(new_tbl, old_tbl, new_hash);
Ying Xuedb304852015-01-07 13:41:54 +0800847
Ying Xue7a868d12015-01-12 14:52:22 +0800848 if (rhashtable_lookup_compare(ht, rht_obj(ht, obj) + ht->p.key_offset,
849 compare, arg)) {
Ying Xuedb304852015-01-07 13:41:54 +0800850 success = false;
851 goto exit;
852 }
853
854 __rhashtable_insert(ht, obj, new_tbl, new_hash);
855
856exit:
Thomas Grafa5ec68e2015-02-05 02:03:32 +0100857 unlock_buckets(new_tbl, old_tbl, new_hash);
Ying Xuedb304852015-01-07 13:41:54 +0800858 rcu_read_unlock();
859
860 return success;
861}
Ying Xue7a868d12015-01-12 14:52:22 +0800862EXPORT_SYMBOL_GPL(rhashtable_lookup_compare_insert);
Ying Xuedb304852015-01-07 13:41:54 +0800863
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100864/**
865 * rhashtable_walk_init - Initialise an iterator
866 * @ht: Table to walk over
867 * @iter: Hash table Iterator
868 *
869 * This function prepares a hash table walk.
870 *
871 * Note that if you restart a walk after rhashtable_walk_stop you
872 * may see the same object twice. Also, you may miss objects if
873 * there are removals in between rhashtable_walk_stop and the next
874 * call to rhashtable_walk_start.
875 *
876 * For a completely stable walk you should construct your own data
877 * structure outside the hash table.
878 *
879 * This function may sleep so you must not call it from interrupt
880 * context or with spin locks held.
881 *
882 * You must call rhashtable_walk_exit if this function returns
883 * successfully.
884 */
885int rhashtable_walk_init(struct rhashtable *ht, struct rhashtable_iter *iter)
886{
887 iter->ht = ht;
888 iter->p = NULL;
889 iter->slot = 0;
890 iter->skip = 0;
891
892 iter->walker = kmalloc(sizeof(*iter->walker), GFP_KERNEL);
893 if (!iter->walker)
894 return -ENOMEM;
895
896 mutex_lock(&ht->mutex);
897 list_add(&iter->walker->list, &ht->walkers);
898 mutex_unlock(&ht->mutex);
899
900 return 0;
901}
902EXPORT_SYMBOL_GPL(rhashtable_walk_init);
903
904/**
905 * rhashtable_walk_exit - Free an iterator
906 * @iter: Hash table Iterator
907 *
908 * This function frees resources allocated by rhashtable_walk_init.
909 */
910void rhashtable_walk_exit(struct rhashtable_iter *iter)
911{
912 mutex_lock(&iter->ht->mutex);
913 list_del(&iter->walker->list);
914 mutex_unlock(&iter->ht->mutex);
915 kfree(iter->walker);
916}
917EXPORT_SYMBOL_GPL(rhashtable_walk_exit);
918
919/**
920 * rhashtable_walk_start - Start a hash table walk
921 * @iter: Hash table iterator
922 *
923 * Start a hash table walk. Note that we take the RCU lock in all
924 * cases including when we return an error. So you must always call
925 * rhashtable_walk_stop to clean up.
926 *
927 * Returns zero if successful.
928 *
929 * Returns -EAGAIN if resize event occured. Note that the iterator
930 * will rewind back to the beginning and you may use it immediately
931 * by calling rhashtable_walk_next.
932 */
933int rhashtable_walk_start(struct rhashtable_iter *iter)
934{
935 rcu_read_lock();
936
937 if (iter->walker->resize) {
938 iter->slot = 0;
939 iter->skip = 0;
940 iter->walker->resize = false;
941 return -EAGAIN;
942 }
943
944 return 0;
945}
946EXPORT_SYMBOL_GPL(rhashtable_walk_start);
947
948/**
949 * rhashtable_walk_next - Return the next object and advance the iterator
950 * @iter: Hash table iterator
951 *
952 * Note that you must call rhashtable_walk_stop when you are finished
953 * with the walk.
954 *
955 * Returns the next object or NULL when the end of the table is reached.
956 *
957 * Returns -EAGAIN if resize event occured. Note that the iterator
958 * will rewind back to the beginning and you may continue to use it.
959 */
960void *rhashtable_walk_next(struct rhashtable_iter *iter)
961{
962 const struct bucket_table *tbl;
963 struct rhashtable *ht = iter->ht;
964 struct rhash_head *p = iter->p;
965 void *obj = NULL;
966
967 tbl = rht_dereference_rcu(ht->tbl, ht);
968
969 if (p) {
970 p = rht_dereference_bucket_rcu(p->next, tbl, iter->slot);
971 goto next;
972 }
973
974 for (; iter->slot < tbl->size; iter->slot++) {
975 int skip = iter->skip;
976
977 rht_for_each_rcu(p, tbl, iter->slot) {
978 if (!skip)
979 break;
980 skip--;
981 }
982
983next:
984 if (!rht_is_a_nulls(p)) {
985 iter->skip++;
986 iter->p = p;
987 obj = rht_obj(ht, p);
988 goto out;
989 }
990
991 iter->skip = 0;
992 }
993
994 iter->p = NULL;
995
996out:
997 if (iter->walker->resize) {
998 iter->p = NULL;
999 iter->slot = 0;
1000 iter->skip = 0;
1001 iter->walker->resize = false;
1002 return ERR_PTR(-EAGAIN);
1003 }
1004
1005 return obj;
1006}
1007EXPORT_SYMBOL_GPL(rhashtable_walk_next);
1008
1009/**
1010 * rhashtable_walk_stop - Finish a hash table walk
1011 * @iter: Hash table iterator
1012 *
1013 * Finish a hash table walk.
1014 */
1015void rhashtable_walk_stop(struct rhashtable_iter *iter)
1016{
1017 rcu_read_unlock();
1018 iter->p = NULL;
1019}
1020EXPORT_SYMBOL_GPL(rhashtable_walk_stop);
1021
Ying Xue94000172014-09-03 09:22:36 +08001022static size_t rounded_hashtable_size(struct rhashtable_params *params)
Thomas Graf7e1e7762014-08-02 11:47:44 +02001023{
Ying Xue94000172014-09-03 09:22:36 +08001024 return max(roundup_pow_of_two(params->nelem_hint * 4 / 3),
1025 1UL << params->min_shift);
Thomas Graf7e1e7762014-08-02 11:47:44 +02001026}
1027
1028/**
1029 * rhashtable_init - initialize a new hash table
1030 * @ht: hash table to be initialized
1031 * @params: configuration parameters
1032 *
1033 * Initializes a new hash table based on the provided configuration
1034 * parameters. A table can be configured either with a variable or
1035 * fixed length key:
1036 *
1037 * Configuration Example 1: Fixed length keys
1038 * struct test_obj {
1039 * int key;
1040 * void * my_member;
1041 * struct rhash_head node;
1042 * };
1043 *
1044 * struct rhashtable_params params = {
1045 * .head_offset = offsetof(struct test_obj, node),
1046 * .key_offset = offsetof(struct test_obj, key),
1047 * .key_len = sizeof(int),
Daniel Borkmann87545892014-12-10 16:33:11 +01001048 * .hashfn = jhash,
Thomas Graff89bd6f2015-01-02 23:00:21 +01001049 * .nulls_base = (1U << RHT_BASE_SHIFT),
Thomas Graf7e1e7762014-08-02 11:47:44 +02001050 * };
1051 *
1052 * Configuration Example 2: Variable length keys
1053 * struct test_obj {
1054 * [...]
1055 * struct rhash_head node;
1056 * };
1057 *
1058 * u32 my_hash_fn(const void *data, u32 seed)
1059 * {
1060 * struct test_obj *obj = data;
1061 *
1062 * return [... hash ...];
1063 * }
1064 *
1065 * struct rhashtable_params params = {
1066 * .head_offset = offsetof(struct test_obj, node),
Daniel Borkmann87545892014-12-10 16:33:11 +01001067 * .hashfn = jhash,
Thomas Graf7e1e7762014-08-02 11:47:44 +02001068 * .obj_hashfn = my_hash_fn,
Thomas Graf7e1e7762014-08-02 11:47:44 +02001069 * };
1070 */
1071int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params)
1072{
1073 struct bucket_table *tbl;
1074 size_t size;
1075
1076 size = HASH_DEFAULT_SIZE;
1077
1078 if ((params->key_len && !params->hashfn) ||
1079 (!params->key_len && !params->obj_hashfn))
1080 return -EINVAL;
1081
Thomas Graff89bd6f2015-01-02 23:00:21 +01001082 if (params->nulls_base && params->nulls_base < (1U << RHT_BASE_SHIFT))
1083 return -EINVAL;
1084
Ying Xue94000172014-09-03 09:22:36 +08001085 params->min_shift = max_t(size_t, params->min_shift,
1086 ilog2(HASH_MIN_SIZE));
1087
Thomas Graf7e1e7762014-08-02 11:47:44 +02001088 if (params->nelem_hint)
Ying Xue94000172014-09-03 09:22:36 +08001089 size = rounded_hashtable_size(params);
Thomas Graf7e1e7762014-08-02 11:47:44 +02001090
Thomas Graf97defe12015-01-02 23:00:20 +01001091 memset(ht, 0, sizeof(*ht));
1092 mutex_init(&ht->mutex);
1093 memcpy(&ht->p, params, sizeof(*params));
Herbert Xuf2dba9c2015-02-04 07:33:23 +11001094 INIT_LIST_HEAD(&ht->walkers);
Thomas Graf97defe12015-01-02 23:00:20 +01001095
1096 if (params->locks_mul)
1097 ht->p.locks_mul = roundup_pow_of_two(params->locks_mul);
1098 else
1099 ht->p.locks_mul = BUCKET_LOCKS_PER_CPU;
1100
1101 tbl = bucket_table_alloc(ht, size);
Thomas Graf7e1e7762014-08-02 11:47:44 +02001102 if (tbl == NULL)
1103 return -ENOMEM;
1104
Ying Xue545a1482015-01-07 13:41:57 +08001105 atomic_set(&ht->nelems, 0);
Ying Xuec0c09bf2015-01-07 13:41:56 +08001106 atomic_set(&ht->shift, ilog2(tbl->size));
Thomas Graf7e1e7762014-08-02 11:47:44 +02001107 RCU_INIT_POINTER(ht->tbl, tbl);
Thomas Graf97defe12015-01-02 23:00:20 +01001108 RCU_INIT_POINTER(ht->future_tbl, tbl);
Thomas Graf7e1e7762014-08-02 11:47:44 +02001109
1110 if (!ht->p.hash_rnd)
1111 get_random_bytes(&ht->p.hash_rnd, sizeof(ht->p.hash_rnd));
1112
Thomas Graf97defe12015-01-02 23:00:20 +01001113 if (ht->p.grow_decision || ht->p.shrink_decision)
Ying Xue57699a42015-01-16 11:13:09 +08001114 INIT_WORK(&ht->run_work, rht_deferred_worker);
Thomas Graf97defe12015-01-02 23:00:20 +01001115
Thomas Graf7e1e7762014-08-02 11:47:44 +02001116 return 0;
1117}
1118EXPORT_SYMBOL_GPL(rhashtable_init);
1119
1120/**
1121 * rhashtable_destroy - destroy hash table
1122 * @ht: the hash table to destroy
1123 *
Pablo Neira Ayusoae82ddc2014-09-02 00:26:05 +02001124 * Frees the bucket array. This function is not rcu safe, therefore the caller
1125 * has to make sure that no resizing may happen by unpublishing the hashtable
1126 * and waiting for the quiescent cycle before releasing the bucket array.
Thomas Graf7e1e7762014-08-02 11:47:44 +02001127 */
Thomas Graf97defe12015-01-02 23:00:20 +01001128void rhashtable_destroy(struct rhashtable *ht)
Thomas Graf7e1e7762014-08-02 11:47:44 +02001129{
Thomas Graf97defe12015-01-02 23:00:20 +01001130 ht->being_destroyed = true;
1131
Ying Xue57699a42015-01-16 11:13:09 +08001132 if (ht->p.grow_decision || ht->p.shrink_decision)
1133 cancel_work_sync(&ht->run_work);
1134
Thomas Graf97defe12015-01-02 23:00:20 +01001135 mutex_lock(&ht->mutex);
Thomas Graf97defe12015-01-02 23:00:20 +01001136 bucket_table_free(rht_dereference(ht->tbl, ht));
Thomas Graf97defe12015-01-02 23:00:20 +01001137 mutex_unlock(&ht->mutex);
Thomas Graf7e1e7762014-08-02 11:47:44 +02001138}
1139EXPORT_SYMBOL_GPL(rhashtable_destroy);