Branch data Line data Source code
1 : : // SPDX-License-Identifier: GPL-2.0-only
2 : : /*
3 : : * Resizable, Scalable, Concurrent Hash Table
4 : : *
5 : : * Copyright (c) 2015 Herbert Xu <herbert@gondor.apana.org.au>
6 : : * Copyright (c) 2014-2015 Thomas Graf <tgraf@suug.ch>
7 : : * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
8 : : *
9 : : * Code partially derived from nft_hash
10 : : * Rewritten with rehash code from br_multicast plus single list
11 : : * pointer as suggested by Josh Triplett
12 : : */
13 : :
14 : : #include <linux/atomic.h>
15 : : #include <linux/kernel.h>
16 : : #include <linux/init.h>
17 : : #include <linux/log2.h>
18 : : #include <linux/sched.h>
19 : : #include <linux/rculist.h>
20 : : #include <linux/slab.h>
21 : : #include <linux/vmalloc.h>
22 : : #include <linux/mm.h>
23 : : #include <linux/jhash.h>
24 : : #include <linux/random.h>
25 : : #include <linux/rhashtable.h>
26 : : #include <linux/err.h>
27 : : #include <linux/export.h>
28 : :
29 : : #define HASH_DEFAULT_SIZE 64UL
30 : : #define HASH_MIN_SIZE 4U
31 : :
32 : : union nested_table {
33 : : union nested_table __rcu *table;
34 : : struct rhash_lock_head *bucket;
35 : : };
36 : :
37 : : static u32 head_hashfn(struct rhashtable *ht,
38 : : const struct bucket_table *tbl,
39 : : const struct rhash_head *he)
40 : : {
41 : 3 : return rht_head_hashfn(ht, tbl, he, ht->p);
42 : : }
43 : :
44 : : #ifdef CONFIG_PROVE_LOCKING
45 : : #define ASSERT_RHT_MUTEX(HT) BUG_ON(!lockdep_rht_mutex_is_held(HT))
46 : :
47 : : int lockdep_rht_mutex_is_held(struct rhashtable *ht)
48 : : {
49 : : return (debug_locks) ? lockdep_is_held(&ht->mutex) : 1;
50 : : }
51 : : EXPORT_SYMBOL_GPL(lockdep_rht_mutex_is_held);
52 : :
53 : : int lockdep_rht_bucket_is_held(const struct bucket_table *tbl, u32 hash)
54 : : {
55 : : if (!debug_locks)
56 : : return 1;
57 : : if (unlikely(tbl->nest))
58 : : return 1;
59 : : return bit_spin_is_locked(0, (unsigned long *)&tbl->buckets[hash]);
60 : : }
61 : : EXPORT_SYMBOL_GPL(lockdep_rht_bucket_is_held);
62 : : #else
63 : : #define ASSERT_RHT_MUTEX(HT)
64 : : #endif
65 : :
66 : 0 : static void nested_table_free(union nested_table *ntbl, unsigned int size)
67 : : {
68 : : const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *));
69 : : const unsigned int len = 1 << shift;
70 : : unsigned int i;
71 : :
72 : 0 : ntbl = rcu_dereference_raw(ntbl->table);
73 : 0 : if (!ntbl)
74 : 0 : return;
75 : :
76 : 0 : if (size > len) {
77 : 0 : size >>= shift;
78 : 0 : for (i = 0; i < len; i++)
79 : 0 : nested_table_free(ntbl + i, size);
80 : : }
81 : :
82 : 0 : kfree(ntbl);
83 : : }
84 : :
85 : 0 : static void nested_bucket_table_free(const struct bucket_table *tbl)
86 : : {
87 : 0 : unsigned int size = tbl->size >> tbl->nest;
88 : 0 : unsigned int len = 1 << tbl->nest;
89 : : union nested_table *ntbl;
90 : : unsigned int i;
91 : :
92 : 0 : ntbl = (union nested_table *)rcu_dereference_raw(tbl->buckets[0]);
93 : :
94 : 0 : for (i = 0; i < len; i++)
95 : 0 : nested_table_free(ntbl + i, size);
96 : :
97 : 0 : kfree(ntbl);
98 : 0 : }
99 : :
100 : 3 : static void bucket_table_free(const struct bucket_table *tbl)
101 : : {
102 : 3 : if (tbl->nest)
103 : 0 : nested_bucket_table_free(tbl);
104 : :
105 : 3 : kvfree(tbl);
106 : 3 : }
107 : :
108 : 3 : static void bucket_table_free_rcu(struct rcu_head *head)
109 : : {
110 : 3 : bucket_table_free(container_of(head, struct bucket_table, rcu));
111 : 3 : }
112 : :
113 : 0 : static union nested_table *nested_table_alloc(struct rhashtable *ht,
114 : : union nested_table __rcu **prev,
115 : : bool leaf)
116 : : {
117 : : union nested_table *ntbl;
118 : : int i;
119 : :
120 : 0 : ntbl = rcu_dereference(*prev);
121 : 0 : if (ntbl)
122 : : return ntbl;
123 : :
124 : 0 : ntbl = kzalloc(PAGE_SIZE, GFP_ATOMIC);
125 : :
126 : 0 : if (ntbl && leaf) {
127 : 0 : for (i = 0; i < PAGE_SIZE / sizeof(ntbl[0]); i++)
128 : 0 : INIT_RHT_NULLS_HEAD(ntbl[i].bucket);
129 : : }
130 : :
131 : 0 : if (cmpxchg((union nested_table **)prev, NULL, ntbl) == NULL)
132 : : return ntbl;
133 : : /* Raced with another thread. */
134 : 0 : kfree(ntbl);
135 : 0 : return rcu_dereference(*prev);
136 : : }
137 : :
138 : 0 : static struct bucket_table *nested_bucket_table_alloc(struct rhashtable *ht,
139 : : size_t nbuckets,
140 : : gfp_t gfp)
141 : : {
142 : : const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *));
143 : : struct bucket_table *tbl;
144 : : size_t size;
145 : :
146 : 0 : if (nbuckets < (1 << (shift + 1)))
147 : : return NULL;
148 : :
149 : : size = sizeof(*tbl) + sizeof(tbl->buckets[0]);
150 : :
151 : 0 : tbl = kzalloc(size, gfp);
152 : 0 : if (!tbl)
153 : : return NULL;
154 : :
155 : 0 : if (!nested_table_alloc(ht, (union nested_table __rcu **)tbl->buckets,
156 : : false)) {
157 : 0 : kfree(tbl);
158 : 0 : return NULL;
159 : : }
160 : :
161 : 0 : tbl->nest = (ilog2(nbuckets) - 1) % shift + 1;
162 : :
163 : 0 : return tbl;
164 : : }
165 : :
166 : 3 : static struct bucket_table *bucket_table_alloc(struct rhashtable *ht,
167 : : size_t nbuckets,
168 : : gfp_t gfp)
169 : : {
170 : : struct bucket_table *tbl = NULL;
171 : : size_t size;
172 : : int i;
173 : : static struct lock_class_key __key;
174 : :
175 : 3 : tbl = kvzalloc(struct_size(tbl, buckets, nbuckets), gfp);
176 : :
177 : : size = nbuckets;
178 : :
179 : 3 : if (tbl == NULL && (gfp & ~__GFP_NOFAIL) != GFP_KERNEL) {
180 : 0 : tbl = nested_bucket_table_alloc(ht, nbuckets, gfp);
181 : : nbuckets = 0;
182 : : }
183 : :
184 : 3 : if (tbl == NULL)
185 : : return NULL;
186 : :
187 : : lockdep_init_map(&tbl->dep_map, "rhashtable_bucket", &__key, 0);
188 : :
189 : 3 : tbl->size = size;
190 : :
191 : : rcu_head_init(&tbl->rcu);
192 : 3 : INIT_LIST_HEAD(&tbl->walkers);
193 : :
194 : 3 : tbl->hash_rnd = get_random_u32();
195 : :
196 : 3 : for (i = 0; i < nbuckets; i++)
197 : 3 : INIT_RHT_NULLS_HEAD(tbl->buckets[i]);
198 : :
199 : : return tbl;
200 : : }
201 : :
202 : : static struct bucket_table *rhashtable_last_table(struct rhashtable *ht,
203 : : struct bucket_table *tbl)
204 : : {
205 : : struct bucket_table *new_tbl;
206 : :
207 : : do {
208 : : new_tbl = tbl;
209 : 3 : tbl = rht_dereference_rcu(tbl->future_tbl, ht);
210 : 3 : } while (tbl);
211 : :
212 : 3 : return new_tbl;
213 : : }
214 : :
215 : 3 : static int rhashtable_rehash_one(struct rhashtable *ht,
216 : : struct rhash_lock_head **bkt,
217 : : unsigned int old_hash)
218 : : {
219 : 3 : struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
220 : : struct bucket_table *new_tbl = rhashtable_last_table(ht, old_tbl);
221 : : int err = -EAGAIN;
222 : : struct rhash_head *head, *next, *entry;
223 : : struct rhash_head __rcu **pprev = NULL;
224 : : unsigned int new_hash;
225 : :
226 : 3 : if (new_tbl->nest)
227 : : goto out;
228 : :
229 : : err = -ENOENT;
230 : :
231 : 3 : rht_for_each_from(entry, rht_ptr(bkt, old_tbl, old_hash),
232 : : old_tbl, old_hash) {
233 : : err = 0;
234 : 3 : next = rht_dereference_bucket(entry->next, old_tbl, old_hash);
235 : :
236 : 3 : if (rht_is_a_nulls(next))
237 : : break;
238 : :
239 : 3 : pprev = &entry->next;
240 : : }
241 : :
242 : 3 : if (err)
243 : : goto out;
244 : :
245 : : new_hash = head_hashfn(ht, new_tbl, entry);
246 : :
247 : 3 : rht_lock_nested(new_tbl, &new_tbl->buckets[new_hash], SINGLE_DEPTH_NESTING);
248 : :
249 : : head = rht_ptr(new_tbl->buckets + new_hash, new_tbl, new_hash);
250 : :
251 : : RCU_INIT_POINTER(entry->next, head);
252 : :
253 : : rht_assign_unlock(new_tbl, &new_tbl->buckets[new_hash], entry);
254 : :
255 : 3 : if (pprev)
256 : 3 : rcu_assign_pointer(*pprev, next);
257 : : else
258 : : /* Need to preserved the bit lock. */
259 : : rht_assign_locked(bkt, next);
260 : :
261 : : out:
262 : 3 : return err;
263 : : }
264 : :
265 : 3 : static int rhashtable_rehash_chain(struct rhashtable *ht,
266 : : unsigned int old_hash)
267 : : {
268 : 3 : struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
269 : : struct rhash_lock_head **bkt = rht_bucket_var(old_tbl, old_hash);
270 : : int err;
271 : :
272 : 3 : if (!bkt)
273 : : return 0;
274 : : rht_lock(old_tbl, bkt);
275 : :
276 : 3 : while (!(err = rhashtable_rehash_one(ht, bkt, old_hash)))
277 : : ;
278 : :
279 : 3 : if (err == -ENOENT)
280 : : err = 0;
281 : : rht_unlock(old_tbl, bkt);
282 : :
283 : 3 : return err;
284 : : }
285 : :
286 : : static int rhashtable_rehash_attach(struct rhashtable *ht,
287 : : struct bucket_table *old_tbl,
288 : : struct bucket_table *new_tbl)
289 : : {
290 : : /* Make insertions go into the new, empty table right away. Deletions
291 : : * and lookups will be attempted in both tables until we synchronize.
292 : : * As cmpxchg() provides strong barriers, we do not need
293 : : * rcu_assign_pointer().
294 : : */
295 : :
296 : 3 : if (cmpxchg((struct bucket_table **)&old_tbl->future_tbl, NULL,
297 : : new_tbl) != NULL)
298 : : return -EEXIST;
299 : :
300 : : return 0;
301 : : }
302 : :
303 : 3 : static int rhashtable_rehash_table(struct rhashtable *ht)
304 : : {
305 : 3 : struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
306 : : struct bucket_table *new_tbl;
307 : : struct rhashtable_walker *walker;
308 : : unsigned int old_hash;
309 : : int err;
310 : :
311 : 3 : new_tbl = rht_dereference(old_tbl->future_tbl, ht);
312 : 3 : if (!new_tbl)
313 : : return 0;
314 : :
315 : 3 : for (old_hash = 0; old_hash < old_tbl->size; old_hash++) {
316 : 3 : err = rhashtable_rehash_chain(ht, old_hash);
317 : 3 : if (err)
318 : 0 : return err;
319 : 3 : cond_resched();
320 : : }
321 : :
322 : : /* Publish the new table pointer. */
323 : 3 : rcu_assign_pointer(ht->tbl, new_tbl);
324 : :
325 : : spin_lock(&ht->lock);
326 : 3 : list_for_each_entry(walker, &old_tbl->walkers, list)
327 : 0 : walker->tbl = NULL;
328 : :
329 : : /* Wait for readers. All new readers will see the new
330 : : * table, and thus no references to the old table will
331 : : * remain.
332 : : * We do this inside the locked region so that
333 : : * rhashtable_walk_stop() can use rcu_head_after_call_rcu()
334 : : * to check if it should not re-link the table.
335 : : */
336 : 3 : call_rcu(&old_tbl->rcu, bucket_table_free_rcu);
337 : : spin_unlock(&ht->lock);
338 : :
339 : 3 : return rht_dereference(new_tbl->future_tbl, ht) ? -EAGAIN : 0;
340 : : }
341 : :
342 : 3 : static int rhashtable_rehash_alloc(struct rhashtable *ht,
343 : : struct bucket_table *old_tbl,
344 : : unsigned int size)
345 : : {
346 : : struct bucket_table *new_tbl;
347 : : int err;
348 : :
349 : : ASSERT_RHT_MUTEX(ht);
350 : :
351 : 3 : new_tbl = bucket_table_alloc(ht, size, GFP_KERNEL);
352 : 3 : if (new_tbl == NULL)
353 : : return -ENOMEM;
354 : :
355 : : err = rhashtable_rehash_attach(ht, old_tbl, new_tbl);
356 : 3 : if (err)
357 : 0 : bucket_table_free(new_tbl);
358 : :
359 : 3 : return err;
360 : : }
361 : :
362 : : /**
363 : : * rhashtable_shrink - Shrink hash table while allowing concurrent lookups
364 : : * @ht: the hash table to shrink
365 : : *
366 : : * This function shrinks the hash table to fit, i.e., the smallest
367 : : * size would not cause it to expand right away automatically.
368 : : *
369 : : * The caller must ensure that no concurrent resizing occurs by holding
370 : : * ht->mutex.
371 : : *
372 : : * The caller must ensure that no concurrent table mutations take place.
373 : : * It is however valid to have concurrent lookups if they are RCU protected.
374 : : *
375 : : * It is valid to have concurrent insertions and deletions protected by per
376 : : * bucket locks or concurrent RCU protected lookups and traversals.
377 : : */
378 : 3 : static int rhashtable_shrink(struct rhashtable *ht)
379 : : {
380 : 3 : struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
381 : : unsigned int nelems = atomic_read(&ht->nelems);
382 : : unsigned int size = 0;
383 : :
384 : 3 : if (nelems)
385 : 3 : size = roundup_pow_of_two(nelems * 3 / 2);
386 : 3 : if (size < ht->p.min_size)
387 : : size = ht->p.min_size;
388 : :
389 : 3 : if (old_tbl->size <= size)
390 : : return 0;
391 : :
392 : 3 : if (rht_dereference(old_tbl->future_tbl, ht))
393 : : return -EEXIST;
394 : :
395 : 3 : return rhashtable_rehash_alloc(ht, old_tbl, size);
396 : : }
397 : :
398 : 3 : static void rht_deferred_worker(struct work_struct *work)
399 : : {
400 : : struct rhashtable *ht;
401 : : struct bucket_table *tbl;
402 : : int err = 0;
403 : :
404 : 3 : ht = container_of(work, struct rhashtable, run_work);
405 : 3 : mutex_lock(&ht->mutex);
406 : :
407 : 3 : tbl = rht_dereference(ht->tbl, ht);
408 : : tbl = rhashtable_last_table(ht, tbl);
409 : :
410 : 3 : if (rht_grow_above_75(ht, tbl))
411 : 3 : err = rhashtable_rehash_alloc(ht, tbl, tbl->size * 2);
412 : 3 : else if (ht->p.automatic_shrinking && rht_shrink_below_30(ht, tbl))
413 : 3 : err = rhashtable_shrink(ht);
414 : 3 : else if (tbl->nest)
415 : 0 : err = rhashtable_rehash_alloc(ht, tbl, tbl->size);
416 : :
417 : 3 : if (!err || err == -EEXIST) {
418 : : int nerr;
419 : :
420 : 3 : nerr = rhashtable_rehash_table(ht);
421 : 3 : err = err ?: nerr;
422 : : }
423 : :
424 : 3 : mutex_unlock(&ht->mutex);
425 : :
426 : 3 : if (err)
427 : 1 : schedule_work(&ht->run_work);
428 : 3 : }
429 : :
430 : 1 : static int rhashtable_insert_rehash(struct rhashtable *ht,
431 : : struct bucket_table *tbl)
432 : : {
433 : : struct bucket_table *old_tbl;
434 : : struct bucket_table *new_tbl;
435 : : unsigned int size;
436 : : int err;
437 : :
438 : 1 : old_tbl = rht_dereference_rcu(ht->tbl, ht);
439 : :
440 : 1 : size = tbl->size;
441 : :
442 : : err = -EBUSY;
443 : :
444 : 1 : if (rht_grow_above_75(ht, tbl))
445 : 1 : size *= 2;
446 : : /* Do not schedule more than one rehash */
447 : 0 : else if (old_tbl != tbl)
448 : : goto fail;
449 : :
450 : : err = -ENOMEM;
451 : :
452 : 1 : new_tbl = bucket_table_alloc(ht, size, GFP_ATOMIC | __GFP_NOWARN);
453 : 1 : if (new_tbl == NULL)
454 : : goto fail;
455 : :
456 : : err = rhashtable_rehash_attach(ht, tbl, new_tbl);
457 : 1 : if (err) {
458 : 0 : bucket_table_free(new_tbl);
459 : 0 : if (err == -EEXIST)
460 : : err = 0;
461 : : } else
462 : 1 : schedule_work(&ht->run_work);
463 : :
464 : 1 : return err;
465 : :
466 : : fail:
467 : : /* Do not fail the insert if someone else did a rehash. */
468 : 0 : if (likely(rcu_access_pointer(tbl->future_tbl)))
469 : : return 0;
470 : :
471 : : /* Schedule async rehash to retry allocation in process context. */
472 : 0 : if (err == -ENOMEM)
473 : 0 : schedule_work(&ht->run_work);
474 : :
475 : 0 : return err;
476 : : }
477 : :
478 : 1 : static void *rhashtable_lookup_one(struct rhashtable *ht,
479 : : struct rhash_lock_head **bkt,
480 : : struct bucket_table *tbl, unsigned int hash,
481 : : const void *key, struct rhash_head *obj)
482 : : {
483 : 1 : struct rhashtable_compare_arg arg = {
484 : : .ht = ht,
485 : : .key = key,
486 : : };
487 : : struct rhash_head __rcu **pprev = NULL;
488 : : struct rhash_head *head;
489 : : int elasticity;
490 : :
491 : : elasticity = RHT_ELASTICITY;
492 : 1 : rht_for_each_from(head, rht_ptr(bkt, tbl, hash), tbl, hash) {
493 : : struct rhlist_head *list;
494 : : struct rhlist_head *plist;
495 : :
496 : 1 : elasticity--;
497 : 1 : if (!key ||
498 : 1 : (ht->p.obj_cmpfn ?
499 : 1 : ht->p.obj_cmpfn(&arg, rht_obj(ht, head)) :
500 : : rhashtable_compare(&arg, rht_obj(ht, head)))) {
501 : 1 : pprev = &head->next;
502 : 1 : continue;
503 : : }
504 : :
505 : 0 : if (!ht->rhlist)
506 : 0 : return rht_obj(ht, head);
507 : :
508 : : list = container_of(obj, struct rhlist_head, rhead);
509 : : plist = container_of(head, struct rhlist_head, rhead);
510 : :
511 : 0 : RCU_INIT_POINTER(list->next, plist);
512 : 0 : head = rht_dereference_bucket(head->next, tbl, hash);
513 : 0 : RCU_INIT_POINTER(list->rhead.next, head);
514 : 0 : if (pprev)
515 : 0 : rcu_assign_pointer(*pprev, obj);
516 : : else
517 : : /* Need to preserve the bit lock */
518 : : rht_assign_locked(bkt, obj);
519 : :
520 : : return NULL;
521 : : }
522 : :
523 : 1 : if (elasticity <= 0)
524 : : return ERR_PTR(-EAGAIN);
525 : :
526 : 1 : return ERR_PTR(-ENOENT);
527 : : }
528 : :
529 : 1 : static struct bucket_table *rhashtable_insert_one(struct rhashtable *ht,
530 : : struct rhash_lock_head **bkt,
531 : : struct bucket_table *tbl,
532 : : unsigned int hash,
533 : : struct rhash_head *obj,
534 : : void *data)
535 : : {
536 : : struct bucket_table *new_tbl;
537 : : struct rhash_head *head;
538 : :
539 : 1 : if (!IS_ERR_OR_NULL(data))
540 : : return ERR_PTR(-EEXIST);
541 : :
542 : 1 : if (PTR_ERR(data) != -EAGAIN && PTR_ERR(data) != -ENOENT)
543 : : return ERR_CAST(data);
544 : :
545 : 1 : new_tbl = rht_dereference_rcu(tbl->future_tbl, ht);
546 : 1 : if (new_tbl)
547 : : return new_tbl;
548 : :
549 : 1 : if (PTR_ERR(data) != -ENOENT)
550 : : return ERR_CAST(data);
551 : :
552 : 1 : if (unlikely(rht_grow_above_max(ht, tbl)))
553 : : return ERR_PTR(-E2BIG);
554 : :
555 : 1 : if (unlikely(rht_grow_above_100(ht, tbl)))
556 : : return ERR_PTR(-EAGAIN);
557 : :
558 : : head = rht_ptr(bkt, tbl, hash);
559 : :
560 : : RCU_INIT_POINTER(obj->next, head);
561 : 1 : if (ht->rhlist) {
562 : : struct rhlist_head *list;
563 : :
564 : : list = container_of(obj, struct rhlist_head, rhead);
565 : : RCU_INIT_POINTER(list->next, NULL);
566 : : }
567 : :
568 : : /* bkt is always the head of the list, so it holds
569 : : * the lock, which we need to preserve
570 : : */
571 : : rht_assign_locked(bkt, obj);
572 : :
573 : 1 : atomic_inc(&ht->nelems);
574 : 1 : if (rht_grow_above_75(ht, tbl))
575 : 1 : schedule_work(&ht->run_work);
576 : :
577 : : return NULL;
578 : : }
579 : :
580 : 1 : static void *rhashtable_try_insert(struct rhashtable *ht, const void *key,
581 : : struct rhash_head *obj)
582 : : {
583 : : struct bucket_table *new_tbl;
584 : : struct bucket_table *tbl;
585 : : struct rhash_lock_head **bkt;
586 : : unsigned int hash;
587 : : void *data;
588 : :
589 : 1 : new_tbl = rcu_dereference(ht->tbl);
590 : :
591 : : do {
592 : : tbl = new_tbl;
593 : 1 : hash = rht_head_hashfn(ht, tbl, obj, ht->p);
594 : 1 : if (rcu_access_pointer(tbl->future_tbl))
595 : : /* Failure is OK */
596 : : bkt = rht_bucket_var(tbl, hash);
597 : : else
598 : : bkt = rht_bucket_insert(ht, tbl, hash);
599 : 1 : if (bkt == NULL) {
600 : 0 : new_tbl = rht_dereference_rcu(tbl->future_tbl, ht);
601 : : data = ERR_PTR(-EAGAIN);
602 : : } else {
603 : : rht_lock(tbl, bkt);
604 : 1 : data = rhashtable_lookup_one(ht, bkt, tbl,
605 : : hash, key, obj);
606 : 1 : new_tbl = rhashtable_insert_one(ht, bkt, tbl,
607 : : hash, obj, data);
608 : 1 : if (PTR_ERR(new_tbl) != -EEXIST)
609 : : data = ERR_CAST(new_tbl);
610 : :
611 : : rht_unlock(tbl, bkt);
612 : : }
613 : 1 : } while (!IS_ERR_OR_NULL(new_tbl));
614 : :
615 : 1 : if (PTR_ERR(data) == -EAGAIN)
616 : 1 : data = ERR_PTR(rhashtable_insert_rehash(ht, tbl) ?:
617 : : -EAGAIN);
618 : :
619 : 1 : return data;
620 : : }
621 : :
622 : 1 : void *rhashtable_insert_slow(struct rhashtable *ht, const void *key,
623 : : struct rhash_head *obj)
624 : : {
625 : : void *data;
626 : :
627 : : do {
628 : : rcu_read_lock();
629 : 1 : data = rhashtable_try_insert(ht, key, obj);
630 : : rcu_read_unlock();
631 : 1 : } while (PTR_ERR(data) == -EAGAIN);
632 : :
633 : 1 : return data;
634 : : }
635 : : EXPORT_SYMBOL_GPL(rhashtable_insert_slow);
636 : :
637 : : /**
638 : : * rhashtable_walk_enter - Initialise an iterator
639 : : * @ht: Table to walk over
640 : : * @iter: Hash table Iterator
641 : : *
642 : : * This function prepares a hash table walk.
643 : : *
644 : : * Note that if you restart a walk after rhashtable_walk_stop you
645 : : * may see the same object twice. Also, you may miss objects if
646 : : * there are removals in between rhashtable_walk_stop and the next
647 : : * call to rhashtable_walk_start.
648 : : *
649 : : * For a completely stable walk you should construct your own data
650 : : * structure outside the hash table.
651 : : *
652 : : * This function may be called from any process context, including
653 : : * non-preemptable context, but cannot be called from softirq or
654 : : * hardirq context.
655 : : *
656 : : * You must call rhashtable_walk_exit after this function returns.
657 : : */
658 : 0 : void rhashtable_walk_enter(struct rhashtable *ht, struct rhashtable_iter *iter)
659 : : {
660 : 0 : iter->ht = ht;
661 : 0 : iter->p = NULL;
662 : 0 : iter->slot = 0;
663 : 0 : iter->skip = 0;
664 : 0 : iter->end_of_table = 0;
665 : :
666 : : spin_lock(&ht->lock);
667 : 0 : iter->walker.tbl =
668 : 0 : rcu_dereference_protected(ht->tbl, lockdep_is_held(&ht->lock));
669 : 0 : list_add(&iter->walker.list, &iter->walker.tbl->walkers);
670 : : spin_unlock(&ht->lock);
671 : 0 : }
672 : : EXPORT_SYMBOL_GPL(rhashtable_walk_enter);
673 : :
674 : : /**
675 : : * rhashtable_walk_exit - Free an iterator
676 : : * @iter: Hash table Iterator
677 : : *
678 : : * This function frees resources allocated by rhashtable_walk_enter.
679 : : */
680 : 0 : void rhashtable_walk_exit(struct rhashtable_iter *iter)
681 : : {
682 : 0 : spin_lock(&iter->ht->lock);
683 : 0 : if (iter->walker.tbl)
684 : : list_del(&iter->walker.list);
685 : 0 : spin_unlock(&iter->ht->lock);
686 : 0 : }
687 : : EXPORT_SYMBOL_GPL(rhashtable_walk_exit);
688 : :
689 : : /**
690 : : * rhashtable_walk_start_check - Start a hash table walk
691 : : * @iter: Hash table iterator
692 : : *
693 : : * Start a hash table walk at the current iterator position. Note that we take
694 : : * the RCU lock in all cases including when we return an error. So you must
695 : : * always call rhashtable_walk_stop to clean up.
696 : : *
697 : : * Returns zero if successful.
698 : : *
699 : : * Returns -EAGAIN if resize event occured. Note that the iterator
700 : : * will rewind back to the beginning and you may use it immediately
701 : : * by calling rhashtable_walk_next.
702 : : *
703 : : * rhashtable_walk_start is defined as an inline variant that returns
704 : : * void. This is preferred in cases where the caller would ignore
705 : : * resize events and always continue.
706 : : */
707 : 0 : int rhashtable_walk_start_check(struct rhashtable_iter *iter)
708 : : __acquires(RCU)
709 : : {
710 : 0 : struct rhashtable *ht = iter->ht;
711 : 0 : bool rhlist = ht->rhlist;
712 : :
713 : : rcu_read_lock();
714 : :
715 : : spin_lock(&ht->lock);
716 : 0 : if (iter->walker.tbl)
717 : : list_del(&iter->walker.list);
718 : : spin_unlock(&ht->lock);
719 : :
720 : 0 : if (iter->end_of_table)
721 : : return 0;
722 : 0 : if (!iter->walker.tbl) {
723 : 0 : iter->walker.tbl = rht_dereference_rcu(ht->tbl, ht);
724 : 0 : iter->slot = 0;
725 : 0 : iter->skip = 0;
726 : 0 : return -EAGAIN;
727 : : }
728 : :
729 : 0 : if (iter->p && !rhlist) {
730 : : /*
731 : : * We need to validate that 'p' is still in the table, and
732 : : * if so, update 'skip'
733 : : */
734 : : struct rhash_head *p;
735 : : int skip = 0;
736 : 0 : rht_for_each_rcu(p, iter->walker.tbl, iter->slot) {
737 : 0 : skip++;
738 : 0 : if (p == iter->p) {
739 : 0 : iter->skip = skip;
740 : 0 : goto found;
741 : : }
742 : : }
743 : 0 : iter->p = NULL;
744 : 0 : } else if (iter->p && rhlist) {
745 : : /* Need to validate that 'list' is still in the table, and
746 : : * if so, update 'skip' and 'p'.
747 : : */
748 : : struct rhash_head *p;
749 : : struct rhlist_head *list;
750 : : int skip = 0;
751 : 0 : rht_for_each_rcu(p, iter->walker.tbl, iter->slot) {
752 : 0 : for (list = container_of(p, struct rhlist_head, rhead);
753 : : list;
754 : 0 : list = rcu_dereference(list->next)) {
755 : 0 : skip++;
756 : 0 : if (list == iter->list) {
757 : 0 : iter->p = p;
758 : 0 : iter->skip = skip;
759 : 0 : goto found;
760 : : }
761 : : }
762 : : }
763 : 0 : iter->p = NULL;
764 : : }
765 : : found:
766 : : return 0;
767 : : }
768 : : EXPORT_SYMBOL_GPL(rhashtable_walk_start_check);
769 : :
770 : : /**
771 : : * __rhashtable_walk_find_next - Find the next element in a table (or the first
772 : : * one in case of a new walk).
773 : : *
774 : : * @iter: Hash table iterator
775 : : *
776 : : * Returns the found object or NULL when the end of the table is reached.
777 : : *
778 : : * Returns -EAGAIN if resize event occurred.
779 : : */
780 : 0 : static void *__rhashtable_walk_find_next(struct rhashtable_iter *iter)
781 : : {
782 : 0 : struct bucket_table *tbl = iter->walker.tbl;
783 : 0 : struct rhlist_head *list = iter->list;
784 : 0 : struct rhashtable *ht = iter->ht;
785 : : struct rhash_head *p = iter->p;
786 : 0 : bool rhlist = ht->rhlist;
787 : :
788 : 0 : if (!tbl)
789 : : return NULL;
790 : :
791 : 0 : for (; iter->slot < tbl->size; iter->slot++) {
792 : 0 : int skip = iter->skip;
793 : :
794 : 0 : rht_for_each_rcu(p, tbl, iter->slot) {
795 : 0 : if (rhlist) {
796 : : list = container_of(p, struct rhlist_head,
797 : : rhead);
798 : : do {
799 : 0 : if (!skip)
800 : : goto next;
801 : 0 : skip--;
802 : 0 : list = rcu_dereference(list->next);
803 : 0 : } while (list);
804 : :
805 : 0 : continue;
806 : : }
807 : 0 : if (!skip)
808 : : break;
809 : 0 : skip--;
810 : : }
811 : :
812 : : next:
813 : 0 : if (!rht_is_a_nulls(p)) {
814 : 0 : iter->skip++;
815 : 0 : iter->p = p;
816 : 0 : iter->list = list;
817 : 0 : return rht_obj(ht, rhlist ? &list->rhead : p);
818 : : }
819 : :
820 : 0 : iter->skip = 0;
821 : : }
822 : :
823 : 0 : iter->p = NULL;
824 : :
825 : : /* Ensure we see any new tables. */
826 : 0 : smp_rmb();
827 : :
828 : 0 : iter->walker.tbl = rht_dereference_rcu(tbl->future_tbl, ht);
829 : 0 : if (iter->walker.tbl) {
830 : 0 : iter->slot = 0;
831 : 0 : iter->skip = 0;
832 : 0 : return ERR_PTR(-EAGAIN);
833 : : } else {
834 : 0 : iter->end_of_table = true;
835 : : }
836 : :
837 : 0 : return NULL;
838 : : }
839 : :
840 : : /**
841 : : * rhashtable_walk_next - Return the next object and advance the iterator
842 : : * @iter: Hash table iterator
843 : : *
844 : : * Note that you must call rhashtable_walk_stop when you are finished
845 : : * with the walk.
846 : : *
847 : : * Returns the next object or NULL when the end of the table is reached.
848 : : *
849 : : * Returns -EAGAIN if resize event occurred. Note that the iterator
850 : : * will rewind back to the beginning and you may continue to use it.
851 : : */
852 : 0 : void *rhashtable_walk_next(struct rhashtable_iter *iter)
853 : : {
854 : 0 : struct rhlist_head *list = iter->list;
855 : 0 : struct rhashtable *ht = iter->ht;
856 : 0 : struct rhash_head *p = iter->p;
857 : 0 : bool rhlist = ht->rhlist;
858 : :
859 : 0 : if (p) {
860 : 0 : if (!rhlist || !(list = rcu_dereference(list->next))) {
861 : 0 : p = rcu_dereference(p->next);
862 : : list = container_of(p, struct rhlist_head, rhead);
863 : : }
864 : 0 : if (!rht_is_a_nulls(p)) {
865 : 0 : iter->skip++;
866 : 0 : iter->p = p;
867 : 0 : iter->list = list;
868 : 0 : return rht_obj(ht, rhlist ? &list->rhead : p);
869 : : }
870 : :
871 : : /* At the end of this slot, switch to next one and then find
872 : : * next entry from that point.
873 : : */
874 : 0 : iter->skip = 0;
875 : 0 : iter->slot++;
876 : : }
877 : :
878 : 0 : return __rhashtable_walk_find_next(iter);
879 : : }
880 : : EXPORT_SYMBOL_GPL(rhashtable_walk_next);
881 : :
882 : : /**
883 : : * rhashtable_walk_peek - Return the next object but don't advance the iterator
884 : : * @iter: Hash table iterator
885 : : *
886 : : * Returns the next object or NULL when the end of the table is reached.
887 : : *
888 : : * Returns -EAGAIN if resize event occurred. Note that the iterator
889 : : * will rewind back to the beginning and you may continue to use it.
890 : : */
891 : 0 : void *rhashtable_walk_peek(struct rhashtable_iter *iter)
892 : : {
893 : 0 : struct rhlist_head *list = iter->list;
894 : 0 : struct rhashtable *ht = iter->ht;
895 : 0 : struct rhash_head *p = iter->p;
896 : :
897 : 0 : if (p)
898 : 0 : return rht_obj(ht, ht->rhlist ? &list->rhead : p);
899 : :
900 : : /* No object found in current iter, find next one in the table. */
901 : :
902 : 0 : if (iter->skip) {
903 : : /* A nonzero skip value points to the next entry in the table
904 : : * beyond that last one that was found. Decrement skip so
905 : : * we find the current value. __rhashtable_walk_find_next
906 : : * will restore the original value of skip assuming that
907 : : * the table hasn't changed.
908 : : */
909 : 0 : iter->skip--;
910 : : }
911 : :
912 : 0 : return __rhashtable_walk_find_next(iter);
913 : : }
914 : : EXPORT_SYMBOL_GPL(rhashtable_walk_peek);
915 : :
916 : : /**
917 : : * rhashtable_walk_stop - Finish a hash table walk
918 : : * @iter: Hash table iterator
919 : : *
920 : : * Finish a hash table walk. Does not reset the iterator to the start of the
921 : : * hash table.
922 : : */
923 : 0 : void rhashtable_walk_stop(struct rhashtable_iter *iter)
924 : : __releases(RCU)
925 : : {
926 : : struct rhashtable *ht;
927 : 0 : struct bucket_table *tbl = iter->walker.tbl;
928 : :
929 : 0 : if (!tbl)
930 : : goto out;
931 : :
932 : 0 : ht = iter->ht;
933 : :
934 : : spin_lock(&ht->lock);
935 : 0 : if (rcu_head_after_call_rcu(&tbl->rcu, bucket_table_free_rcu))
936 : : /* This bucket table is being freed, don't re-link it. */
937 : 0 : iter->walker.tbl = NULL;
938 : : else
939 : 0 : list_add(&iter->walker.list, &tbl->walkers);
940 : : spin_unlock(&ht->lock);
941 : :
942 : : out:
943 : : rcu_read_unlock();
944 : 0 : }
945 : : EXPORT_SYMBOL_GPL(rhashtable_walk_stop);
946 : :
947 : 3 : static size_t rounded_hashtable_size(const struct rhashtable_params *params)
948 : : {
949 : : size_t retsize;
950 : :
951 : 3 : if (params->nelem_hint)
952 : 3 : retsize = max(roundup_pow_of_two(params->nelem_hint * 4 / 3),
953 : : (unsigned long)params->min_size);
954 : : else
955 : 3 : retsize = max(HASH_DEFAULT_SIZE,
956 : : (unsigned long)params->min_size);
957 : :
958 : 3 : return retsize;
959 : : }
960 : :
961 : 3 : static u32 rhashtable_jhash2(const void *key, u32 length, u32 seed)
962 : : {
963 : 3 : return jhash2(key, length, seed);
964 : : }
965 : :
966 : : /**
967 : : * rhashtable_init - initialize a new hash table
968 : : * @ht: hash table to be initialized
969 : : * @params: configuration parameters
970 : : *
971 : : * Initializes a new hash table based on the provided configuration
972 : : * parameters. A table can be configured either with a variable or
973 : : * fixed length key:
974 : : *
975 : : * Configuration Example 1: Fixed length keys
976 : : * struct test_obj {
977 : : * int key;
978 : : * void * my_member;
979 : : * struct rhash_head node;
980 : : * };
981 : : *
982 : : * struct rhashtable_params params = {
983 : : * .head_offset = offsetof(struct test_obj, node),
984 : : * .key_offset = offsetof(struct test_obj, key),
985 : : * .key_len = sizeof(int),
986 : : * .hashfn = jhash,
987 : : * };
988 : : *
989 : : * Configuration Example 2: Variable length keys
990 : : * struct test_obj {
991 : : * [...]
992 : : * struct rhash_head node;
993 : : * };
994 : : *
995 : : * u32 my_hash_fn(const void *data, u32 len, u32 seed)
996 : : * {
997 : : * struct test_obj *obj = data;
998 : : *
999 : : * return [... hash ...];
1000 : : * }
1001 : : *
1002 : : * struct rhashtable_params params = {
1003 : : * .head_offset = offsetof(struct test_obj, node),
1004 : : * .hashfn = jhash,
1005 : : * .obj_hashfn = my_hash_fn,
1006 : : * };
1007 : : */
1008 : 3 : int rhashtable_init(struct rhashtable *ht,
1009 : : const struct rhashtable_params *params)
1010 : : {
1011 : : struct bucket_table *tbl;
1012 : : size_t size;
1013 : :
1014 : 3 : if ((!params->key_len && !params->obj_hashfn) ||
1015 : 3 : (params->obj_hashfn && !params->obj_cmpfn))
1016 : : return -EINVAL;
1017 : :
1018 : 3 : memset(ht, 0, sizeof(*ht));
1019 : 3 : mutex_init(&ht->mutex);
1020 : 3 : spin_lock_init(&ht->lock);
1021 : 3 : memcpy(&ht->p, params, sizeof(*params));
1022 : :
1023 : 3 : if (params->min_size)
1024 : 0 : ht->p.min_size = roundup_pow_of_two(params->min_size);
1025 : :
1026 : : /* Cap total entries at 2^31 to avoid nelems overflow. */
1027 : 3 : ht->max_elems = 1u << 31;
1028 : :
1029 : 3 : if (params->max_size) {
1030 : 0 : ht->p.max_size = rounddown_pow_of_two(params->max_size);
1031 : 0 : if (ht->p.max_size < ht->max_elems / 2)
1032 : 0 : ht->max_elems = ht->p.max_size * 2;
1033 : : }
1034 : :
1035 : 3 : ht->p.min_size = max_t(u16, ht->p.min_size, HASH_MIN_SIZE);
1036 : :
1037 : 3 : size = rounded_hashtable_size(&ht->p);
1038 : :
1039 : 3 : ht->key_len = ht->p.key_len;
1040 : 3 : if (!params->hashfn) {
1041 : 3 : ht->p.hashfn = jhash;
1042 : :
1043 : 3 : if (!(ht->key_len & (sizeof(u32) - 1))) {
1044 : 3 : ht->key_len /= sizeof(u32);
1045 : 3 : ht->p.hashfn = rhashtable_jhash2;
1046 : : }
1047 : : }
1048 : :
1049 : : /*
1050 : : * This is api initialization and thus we need to guarantee the
1051 : : * initial rhashtable allocation. Upon failure, retry with the
1052 : : * smallest possible size with __GFP_NOFAIL semantics.
1053 : : */
1054 : 3 : tbl = bucket_table_alloc(ht, size, GFP_KERNEL);
1055 : 3 : if (unlikely(tbl == NULL)) {
1056 : 0 : size = max_t(u16, ht->p.min_size, HASH_MIN_SIZE);
1057 : 0 : tbl = bucket_table_alloc(ht, size, GFP_KERNEL | __GFP_NOFAIL);
1058 : : }
1059 : :
1060 : : atomic_set(&ht->nelems, 0);
1061 : :
1062 : 3 : RCU_INIT_POINTER(ht->tbl, tbl);
1063 : :
1064 : 3 : INIT_WORK(&ht->run_work, rht_deferred_worker);
1065 : :
1066 : 3 : return 0;
1067 : : }
1068 : : EXPORT_SYMBOL_GPL(rhashtable_init);
1069 : :
1070 : : /**
1071 : : * rhltable_init - initialize a new hash list table
1072 : : * @hlt: hash list table to be initialized
1073 : : * @params: configuration parameters
1074 : : *
1075 : : * Initializes a new hash list table.
1076 : : *
1077 : : * See documentation for rhashtable_init.
1078 : : */
1079 : 3 : int rhltable_init(struct rhltable *hlt, const struct rhashtable_params *params)
1080 : : {
1081 : : int err;
1082 : :
1083 : 3 : err = rhashtable_init(&hlt->ht, params);
1084 : 3 : hlt->ht.rhlist = true;
1085 : 3 : return err;
1086 : : }
1087 : : EXPORT_SYMBOL_GPL(rhltable_init);
1088 : :
1089 : 0 : static void rhashtable_free_one(struct rhashtable *ht, struct rhash_head *obj,
1090 : : void (*free_fn)(void *ptr, void *arg),
1091 : : void *arg)
1092 : : {
1093 : : struct rhlist_head *list;
1094 : :
1095 : 0 : if (!ht->rhlist) {
1096 : 0 : free_fn(rht_obj(ht, obj), arg);
1097 : 0 : return;
1098 : : }
1099 : :
1100 : : list = container_of(obj, struct rhlist_head, rhead);
1101 : : do {
1102 : 0 : obj = &list->rhead;
1103 : 0 : list = rht_dereference(list->next, ht);
1104 : 0 : free_fn(rht_obj(ht, obj), arg);
1105 : 0 : } while (list);
1106 : : }
1107 : :
1108 : : /**
1109 : : * rhashtable_free_and_destroy - free elements and destroy hash table
1110 : : * @ht: the hash table to destroy
1111 : : * @free_fn: callback to release resources of element
1112 : : * @arg: pointer passed to free_fn
1113 : : *
1114 : : * Stops an eventual async resize. If defined, invokes free_fn for each
1115 : : * element to releasal resources. Please note that RCU protected
1116 : : * readers may still be accessing the elements. Releasing of resources
1117 : : * must occur in a compatible manner. Then frees the bucket array.
1118 : : *
1119 : : * This function will eventually sleep to wait for an async resize
1120 : : * to complete. The caller is responsible that no further write operations
1121 : : * occurs in parallel.
1122 : : */
1123 : 1 : void rhashtable_free_and_destroy(struct rhashtable *ht,
1124 : : void (*free_fn)(void *ptr, void *arg),
1125 : : void *arg)
1126 : : {
1127 : : struct bucket_table *tbl, *next_tbl;
1128 : : unsigned int i;
1129 : :
1130 : 1 : cancel_work_sync(&ht->run_work);
1131 : :
1132 : 1 : mutex_lock(&ht->mutex);
1133 : 1 : tbl = rht_dereference(ht->tbl, ht);
1134 : : restart:
1135 : 1 : if (free_fn) {
1136 : 1 : for (i = 0; i < tbl->size; i++) {
1137 : : struct rhash_head *pos, *next;
1138 : :
1139 : 1 : cond_resched();
1140 : 1 : for (pos = rht_ptr_exclusive(rht_bucket(tbl, i)),
1141 : : next = !rht_is_a_nulls(pos) ?
1142 : 1 : rht_dereference(pos->next, ht) : NULL;
1143 : : !rht_is_a_nulls(pos);
1144 : : pos = next,
1145 : : next = !rht_is_a_nulls(pos) ?
1146 : 0 : rht_dereference(pos->next, ht) : NULL)
1147 : 0 : rhashtable_free_one(ht, pos, free_fn, arg);
1148 : : }
1149 : : }
1150 : :
1151 : 1 : next_tbl = rht_dereference(tbl->future_tbl, ht);
1152 : 1 : bucket_table_free(tbl);
1153 : 1 : if (next_tbl) {
1154 : : tbl = next_tbl;
1155 : : goto restart;
1156 : : }
1157 : 1 : mutex_unlock(&ht->mutex);
1158 : 1 : }
1159 : : EXPORT_SYMBOL_GPL(rhashtable_free_and_destroy);
1160 : :
1161 : 0 : void rhashtable_destroy(struct rhashtable *ht)
1162 : : {
1163 : 0 : return rhashtable_free_and_destroy(ht, NULL, NULL);
1164 : : }
1165 : : EXPORT_SYMBOL_GPL(rhashtable_destroy);
1166 : :
1167 : 0 : struct rhash_lock_head **__rht_bucket_nested(const struct bucket_table *tbl,
1168 : : unsigned int hash)
1169 : : {
1170 : : const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *));
1171 : 0 : unsigned int index = hash & ((1 << tbl->nest) - 1);
1172 : 0 : unsigned int size = tbl->size >> tbl->nest;
1173 : : unsigned int subhash = hash;
1174 : : union nested_table *ntbl;
1175 : :
1176 : 0 : ntbl = (union nested_table *)rcu_dereference_raw(tbl->buckets[0]);
1177 : 0 : ntbl = rht_dereference_bucket_rcu(ntbl[index].table, tbl, hash);
1178 : 0 : subhash >>= tbl->nest;
1179 : :
1180 : 0 : while (ntbl && size > (1 << shift)) {
1181 : 0 : index = subhash & ((1 << shift) - 1);
1182 : 0 : ntbl = rht_dereference_bucket_rcu(ntbl[index].table,
1183 : : tbl, hash);
1184 : 0 : size >>= shift;
1185 : 0 : subhash >>= shift;
1186 : : }
1187 : :
1188 : 0 : if (!ntbl)
1189 : : return NULL;
1190 : :
1191 : 0 : return &ntbl[subhash].bucket;
1192 : :
1193 : : }
1194 : : EXPORT_SYMBOL_GPL(__rht_bucket_nested);
1195 : :
1196 : 0 : struct rhash_lock_head **rht_bucket_nested(const struct bucket_table *tbl,
1197 : : unsigned int hash)
1198 : : {
1199 : : static struct rhash_lock_head *rhnull;
1200 : :
1201 : 0 : if (!rhnull)
1202 : 0 : INIT_RHT_NULLS_HEAD(rhnull);
1203 : 0 : return __rht_bucket_nested(tbl, hash) ?: &rhnull;
1204 : : }
1205 : : EXPORT_SYMBOL_GPL(rht_bucket_nested);
1206 : :
1207 : 0 : struct rhash_lock_head **rht_bucket_nested_insert(struct rhashtable *ht,
1208 : : struct bucket_table *tbl,
1209 : : unsigned int hash)
1210 : : {
1211 : : const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *));
1212 : 0 : unsigned int index = hash & ((1 << tbl->nest) - 1);
1213 : 0 : unsigned int size = tbl->size >> tbl->nest;
1214 : : union nested_table *ntbl;
1215 : :
1216 : 0 : ntbl = (union nested_table *)rcu_dereference_raw(tbl->buckets[0]);
1217 : 0 : hash >>= tbl->nest;
1218 : 0 : ntbl = nested_table_alloc(ht, &ntbl[index].table,
1219 : : size <= (1 << shift));
1220 : :
1221 : 0 : while (ntbl && size > (1 << shift)) {
1222 : 0 : index = hash & ((1 << shift) - 1);
1223 : 0 : size >>= shift;
1224 : 0 : hash >>= shift;
1225 : 0 : ntbl = nested_table_alloc(ht, &ntbl[index].table,
1226 : : size <= (1 << shift));
1227 : : }
1228 : :
1229 : 0 : if (!ntbl)
1230 : : return NULL;
1231 : :
1232 : 0 : return &ntbl[hash].bucket;
1233 : :
1234 : : }
1235 : : EXPORT_SYMBOL_GPL(rht_bucket_nested_insert);
|
