1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18#ifndef _LINUX_RHASHTABLE_H
19#define _LINUX_RHASHTABLE_H
20
21#include <linux/err.h>
22#include <linux/errno.h>
23#include <linux/jhash.h>
24#include <linux/list_nulls.h>
25#include <linux/workqueue.h>
26#include <linux/rculist.h>
27#include <linux/bit_spinlock.h>
28
29#include <linux/rhashtable-types.h>
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47struct rhash_lock_head {};
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62#define RHT_ELASTICITY 16u
63
64
65
66
67
68
69
70
71
72
73
74
75
76struct bucket_table {
77 unsigned int size;
78 unsigned int nest;
79 u32 hash_rnd;
80 struct list_head walkers;
81 struct rcu_head rcu;
82
83 struct bucket_table __rcu *future_tbl;
84
85 struct lockdep_map dep_map;
86
87 struct rhash_lock_head __rcu *buckets[] ____cacheline_aligned_in_smp;
88};
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103#define RHT_NULLS_MARKER(ptr) \
104 ((void *)NULLS_MARKER(((unsigned long) (ptr)) >> 1))
105#define INIT_RHT_NULLS_HEAD(ptr) \
106 ((ptr) = NULL)
107
108static inline bool rht_is_a_nulls(const struct rhash_head *ptr)
109{
110 return ((unsigned long) ptr & 1);
111}
112
113static inline void *rht_obj(const struct rhashtable *ht,
114 const struct rhash_head *he)
115{
116 return (char *)he - ht->p.head_offset;
117}
118
119static inline unsigned int rht_bucket_index(const struct bucket_table *tbl,
120 unsigned int hash)
121{
122 return hash & (tbl->size - 1);
123}
124
125static inline unsigned int rht_key_get_hash(struct rhashtable *ht,
126 const void *key, const struct rhashtable_params params,
127 unsigned int hash_rnd)
128{
129 unsigned int hash;
130
131
132 if (!__builtin_constant_p(params.key_len))
133 hash = ht->p.hashfn(key, ht->key_len, hash_rnd);
134 else if (params.key_len) {
135 unsigned int key_len = params.key_len;
136
137 if (params.hashfn)
138 hash = params.hashfn(key, key_len, hash_rnd);
139 else if (key_len & (sizeof(u32) - 1))
140 hash = jhash(key, key_len, hash_rnd);
141 else
142 hash = jhash2(key, key_len / sizeof(u32), hash_rnd);
143 } else {
144 unsigned int key_len = ht->p.key_len;
145
146 if (params.hashfn)
147 hash = params.hashfn(key, key_len, hash_rnd);
148 else
149 hash = jhash(key, key_len, hash_rnd);
150 }
151
152 return hash;
153}
154
155static inline unsigned int rht_key_hashfn(
156 struct rhashtable *ht, const struct bucket_table *tbl,
157 const void *key, const struct rhashtable_params params)
158{
159 unsigned int hash = rht_key_get_hash(ht, key, params, tbl->hash_rnd);
160
161 return rht_bucket_index(tbl, hash);
162}
163
164static inline unsigned int rht_head_hashfn(
165 struct rhashtable *ht, const struct bucket_table *tbl,
166 const struct rhash_head *he, const struct rhashtable_params params)
167{
168 const char *ptr = rht_obj(ht, he);
169
170 return likely(params.obj_hashfn) ?
171 rht_bucket_index(tbl, params.obj_hashfn(ptr, params.key_len ?:
172 ht->p.key_len,
173 tbl->hash_rnd)) :
174 rht_key_hashfn(ht, tbl, ptr + params.key_offset, params);
175}
176
177
178
179
180
181
182static inline bool rht_grow_above_75(const struct rhashtable *ht,
183 const struct bucket_table *tbl)
184{
185
186 return atomic_read(&ht->nelems) > (tbl->size / 4 * 3) &&
187 (!ht->p.max_size || tbl->size < ht->p.max_size);
188}
189
190
191
192
193
194
195static inline bool rht_shrink_below_30(const struct rhashtable *ht,
196 const struct bucket_table *tbl)
197{
198
199 return atomic_read(&ht->nelems) < (tbl->size * 3 / 10) &&
200 tbl->size > ht->p.min_size;
201}
202
203
204
205
206
207
208static inline bool rht_grow_above_100(const struct rhashtable *ht,
209 const struct bucket_table *tbl)
210{
211 return atomic_read(&ht->nelems) > tbl->size &&
212 (!ht->p.max_size || tbl->size < ht->p.max_size);
213}
214
215
216
217
218
219
220static inline bool rht_grow_above_max(const struct rhashtable *ht,
221 const struct bucket_table *tbl)
222{
223 return atomic_read(&ht->nelems) >= ht->max_elems;
224}
225
226#ifdef CONFIG_PROVE_LOCKING
227int lockdep_rht_mutex_is_held(struct rhashtable *ht);
228int lockdep_rht_bucket_is_held(const struct bucket_table *tbl, u32 hash);
229#else
230static inline int lockdep_rht_mutex_is_held(struct rhashtable *ht)
231{
232 return 1;
233}
234
235static inline int lockdep_rht_bucket_is_held(const struct bucket_table *tbl,
236 u32 hash)
237{
238 return 1;
239}
240#endif
241
242void *rhashtable_insert_slow(struct rhashtable *ht, const void *key,
243 struct rhash_head *obj);
244
245void rhashtable_walk_enter(struct rhashtable *ht,
246 struct rhashtable_iter *iter);
247void rhashtable_walk_exit(struct rhashtable_iter *iter);
248int rhashtable_walk_start_check(struct rhashtable_iter *iter) __acquires(RCU);
249
250static inline void rhashtable_walk_start(struct rhashtable_iter *iter)
251{
252 (void)rhashtable_walk_start_check(iter);
253}
254
255void *rhashtable_walk_next(struct rhashtable_iter *iter);
256void *rhashtable_walk_peek(struct rhashtable_iter *iter);
257void rhashtable_walk_stop(struct rhashtable_iter *iter) __releases(RCU);
258
259void rhashtable_free_and_destroy(struct rhashtable *ht,
260 void (*free_fn)(void *ptr, void *arg),
261 void *arg);
262void rhashtable_destroy(struct rhashtable *ht);
263
264struct rhash_lock_head __rcu **rht_bucket_nested(
265 const struct bucket_table *tbl, unsigned int hash);
266struct rhash_lock_head __rcu **__rht_bucket_nested(
267 const struct bucket_table *tbl, unsigned int hash);
268struct rhash_lock_head __rcu **rht_bucket_nested_insert(
269 struct rhashtable *ht, struct bucket_table *tbl, unsigned int hash);
270
271#define rht_dereference(p, ht) \
272 rcu_dereference_protected(p, lockdep_rht_mutex_is_held(ht))
273
274#define rht_dereference_rcu(p, ht) \
275 rcu_dereference_check(p, lockdep_rht_mutex_is_held(ht))
276
277#define rht_dereference_bucket(p, tbl, hash) \
278 rcu_dereference_protected(p, lockdep_rht_bucket_is_held(tbl, hash))
279
280#define rht_dereference_bucket_rcu(p, tbl, hash) \
281 rcu_dereference_check(p, lockdep_rht_bucket_is_held(tbl, hash))
282
283#define rht_entry(tpos, pos, member) \
284 ({ tpos = container_of(pos, typeof(*tpos), member); 1; })
285
286static inline struct rhash_lock_head __rcu *const *rht_bucket(
287 const struct bucket_table *tbl, unsigned int hash)
288{
289 return unlikely(tbl->nest) ? rht_bucket_nested(tbl, hash) :
290 &tbl->buckets[hash];
291}
292
293static inline struct rhash_lock_head __rcu **rht_bucket_var(
294 struct bucket_table *tbl, unsigned int hash)
295{
296 return unlikely(tbl->nest) ? __rht_bucket_nested(tbl, hash) :
297 &tbl->buckets[hash];
298}
299
300static inline struct rhash_lock_head __rcu **rht_bucket_insert(
301 struct rhashtable *ht, struct bucket_table *tbl, unsigned int hash)
302{
303 return unlikely(tbl->nest) ? rht_bucket_nested_insert(ht, tbl, hash) :
304 &tbl->buckets[hash];
305}
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326static inline void rht_lock(struct bucket_table *tbl,
327 struct rhash_lock_head __rcu **bkt)
328{
329 local_bh_disable();
330 bit_spin_lock(0, (unsigned long *)bkt);
331 lock_map_acquire(&tbl->dep_map);
332}
333
334static inline void rht_lock_nested(struct bucket_table *tbl,
335 struct rhash_lock_head __rcu **bucket,
336 unsigned int subclass)
337{
338 local_bh_disable();
339 bit_spin_lock(0, (unsigned long *)bucket);
340 lock_acquire_exclusive(&tbl->dep_map, subclass, 0, NULL, _THIS_IP_);
341}
342
343static inline void rht_unlock(struct bucket_table *tbl,
344 struct rhash_lock_head __rcu **bkt)
345{
346 lock_map_release(&tbl->dep_map);
347 bit_spin_unlock(0, (unsigned long *)bkt);
348 local_bh_enable();
349}
350
351static inline struct rhash_head *__rht_ptr(
352 struct rhash_lock_head *p, struct rhash_lock_head __rcu *const *bkt)
353{
354 return (struct rhash_head *)
355 ((unsigned long)p & ~BIT(0) ?:
356 (unsigned long)RHT_NULLS_MARKER(bkt));
357}
358
359
360
361
362
363
364
365
366static inline struct rhash_head *rht_ptr_rcu(
367 struct rhash_lock_head __rcu *const *bkt)
368{
369 return __rht_ptr(rcu_dereference(*bkt), bkt);
370}
371
372static inline struct rhash_head *rht_ptr(
373 struct rhash_lock_head __rcu *const *bkt,
374 struct bucket_table *tbl,
375 unsigned int hash)
376{
377 return __rht_ptr(rht_dereference_bucket(*bkt, tbl, hash), bkt);
378}
379
380static inline struct rhash_head *rht_ptr_exclusive(
381 struct rhash_lock_head __rcu *const *bkt)
382{
383 return __rht_ptr(rcu_dereference_protected(*bkt, 1), bkt);
384}
385
386static inline void rht_assign_locked(struct rhash_lock_head __rcu **bkt,
387 struct rhash_head *obj)
388{
389 if (rht_is_a_nulls(obj))
390 obj = NULL;
391 rcu_assign_pointer(*bkt, (void *)((unsigned long)obj | BIT(0)));
392}
393
394static inline void rht_assign_unlock(struct bucket_table *tbl,
395 struct rhash_lock_head __rcu **bkt,
396 struct rhash_head *obj)
397{
398 if (rht_is_a_nulls(obj))
399 obj = NULL;
400 lock_map_release(&tbl->dep_map);
401 rcu_assign_pointer(*bkt, (void *)obj);
402 preempt_enable();
403 __release(bitlock);
404 local_bh_enable();
405}
406
407
408
409
410
411
412
413
414#define rht_for_each_from(pos, head, tbl, hash) \
415 for (pos = head; \
416 !rht_is_a_nulls(pos); \
417 pos = rht_dereference_bucket((pos)->next, tbl, hash))
418
419
420
421
422
423
424
425#define rht_for_each(pos, tbl, hash) \
426 rht_for_each_from(pos, rht_ptr(rht_bucket(tbl, hash), tbl, hash), \
427 tbl, hash)
428
429
430
431
432
433
434
435
436
437
438#define rht_for_each_entry_from(tpos, pos, head, tbl, hash, member) \
439 for (pos = head; \
440 (!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member); \
441 pos = rht_dereference_bucket((pos)->next, tbl, hash))
442
443
444
445
446
447
448
449
450
451#define rht_for_each_entry(tpos, pos, tbl, hash, member) \
452 rht_for_each_entry_from(tpos, pos, \
453 rht_ptr(rht_bucket(tbl, hash), tbl, hash), \
454 tbl, hash, member)
455
456
457
458
459
460
461
462
463
464
465
466
467
468#define rht_for_each_entry_safe(tpos, pos, next, tbl, hash, member) \
469 for (pos = rht_ptr(rht_bucket(tbl, hash), tbl, hash), \
470 next = !rht_is_a_nulls(pos) ? \
471 rht_dereference_bucket(pos->next, tbl, hash) : NULL; \
472 (!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member); \
473 pos = next, \
474 next = !rht_is_a_nulls(pos) ? \
475 rht_dereference_bucket(pos->next, tbl, hash) : NULL)
476
477
478
479
480
481
482
483
484
485
486
487
488#define rht_for_each_rcu_from(pos, head, tbl, hash) \
489 for (({barrier(); }), \
490 pos = head; \
491 !rht_is_a_nulls(pos); \
492 pos = rcu_dereference_raw(pos->next))
493
494
495
496
497
498
499
500
501
502
503
504#define rht_for_each_rcu(pos, tbl, hash) \
505 for (({barrier(); }), \
506 pos = rht_ptr_rcu(rht_bucket(tbl, hash)); \
507 !rht_is_a_nulls(pos); \
508 pos = rcu_dereference_raw(pos->next))
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523#define rht_for_each_entry_rcu_from(tpos, pos, head, tbl, hash, member) \
524 for (({barrier(); }), \
525 pos = head; \
526 (!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member); \
527 pos = rht_dereference_bucket_rcu(pos->next, tbl, hash))
528
529
530
531
532
533
534
535
536
537
538
539
540
541#define rht_for_each_entry_rcu(tpos, pos, tbl, hash, member) \
542 rht_for_each_entry_rcu_from(tpos, pos, \
543 rht_ptr_rcu(rht_bucket(tbl, hash)), \
544 tbl, hash, member)
545
546
547
548
549
550
551
552
553
554#define rhl_for_each_rcu(pos, list) \
555 for (pos = list; pos; pos = rcu_dereference_raw(pos->next))
556
557
558
559
560
561
562
563
564
565
566
567#define rhl_for_each_entry_rcu(tpos, pos, list, member) \
568 for (pos = list; pos && rht_entry(tpos, pos, member); \
569 pos = rcu_dereference_raw(pos->next))
570
571static inline int rhashtable_compare(struct rhashtable_compare_arg *arg,
572 const void *obj)
573{
574 struct rhashtable *ht = arg->ht;
575 const char *ptr = obj;
576
577 return memcmp(ptr + ht->p.key_offset, arg->key, ht->p.key_len);
578}
579
580
581static inline struct rhash_head *__rhashtable_lookup(
582 struct rhashtable *ht, const void *key,
583 const struct rhashtable_params params)
584{
585 struct rhashtable_compare_arg arg = {
586 .ht = ht,
587 .key = key,
588 };
589 struct rhash_lock_head __rcu *const *bkt;
590 struct bucket_table *tbl;
591 struct rhash_head *he;
592 unsigned int hash;
593
594 tbl = rht_dereference_rcu(ht->tbl, ht);
595restart:
596 hash = rht_key_hashfn(ht, tbl, key, params);
597 bkt = rht_bucket(tbl, hash);
598 do {
599 rht_for_each_rcu_from(he, rht_ptr_rcu(bkt), tbl, hash) {
600 if (params.obj_cmpfn ?
601 params.obj_cmpfn(&arg, rht_obj(ht, he)) :
602 rhashtable_compare(&arg, rht_obj(ht, he)))
603 continue;
604 return he;
605 }
606
607
608
609 } while (he != RHT_NULLS_MARKER(bkt));
610
611
612 smp_rmb();
613
614 tbl = rht_dereference_rcu(tbl->future_tbl, ht);
615 if (unlikely(tbl))
616 goto restart;
617
618 return NULL;
619}
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634static inline void *rhashtable_lookup(
635 struct rhashtable *ht, const void *key,
636 const struct rhashtable_params params)
637{
638 struct rhash_head *he = __rhashtable_lookup(ht, key, params);
639
640 return he ? rht_obj(ht, he) : NULL;
641}
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657static inline void *rhashtable_lookup_fast(
658 struct rhashtable *ht, const void *key,
659 const struct rhashtable_params params)
660{
661 void *obj;
662
663 rcu_read_lock();
664 obj = rhashtable_lookup(ht, key, params);
665 rcu_read_unlock();
666
667 return obj;
668}
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684static inline struct rhlist_head *rhltable_lookup(
685 struct rhltable *hlt, const void *key,
686 const struct rhashtable_params params)
687{
688 struct rhash_head *he = __rhashtable_lookup(&hlt->ht, key, params);
689
690 return he ? container_of(he, struct rhlist_head, rhead) : NULL;
691}
692
693
694
695
696
697static inline void *__rhashtable_insert_fast(
698 struct rhashtable *ht, const void *key, struct rhash_head *obj,
699 const struct rhashtable_params params, bool rhlist)
700{
701 struct rhashtable_compare_arg arg = {
702 .ht = ht,
703 .key = key,
704 };
705 struct rhash_lock_head __rcu **bkt;
706 struct rhash_head __rcu **pprev;
707 struct bucket_table *tbl;
708 struct rhash_head *head;
709 unsigned int hash;
710 int elasticity;
711 void *data;
712
713 rcu_read_lock();
714
715 tbl = rht_dereference_rcu(ht->tbl, ht);
716 hash = rht_head_hashfn(ht, tbl, obj, params);
717 elasticity = RHT_ELASTICITY;
718 bkt = rht_bucket_insert(ht, tbl, hash);
719 data = ERR_PTR(-ENOMEM);
720 if (!bkt)
721 goto out;
722 pprev = NULL;
723 rht_lock(tbl, bkt);
724
725 if (unlikely(rcu_access_pointer(tbl->future_tbl))) {
726slow_path:
727 rht_unlock(tbl, bkt);
728 rcu_read_unlock();
729 return rhashtable_insert_slow(ht, key, obj);
730 }
731
732 rht_for_each_from(head, rht_ptr(bkt, tbl, hash), tbl, hash) {
733 struct rhlist_head *plist;
734 struct rhlist_head *list;
735
736 elasticity--;
737 if (!key ||
738 (params.obj_cmpfn ?
739 params.obj_cmpfn(&arg, rht_obj(ht, head)) :
740 rhashtable_compare(&arg, rht_obj(ht, head)))) {
741 pprev = &head->next;
742 continue;
743 }
744
745 data = rht_obj(ht, head);
746
747 if (!rhlist)
748 goto out_unlock;
749
750
751 list = container_of(obj, struct rhlist_head, rhead);
752 plist = container_of(head, struct rhlist_head, rhead);
753
754 RCU_INIT_POINTER(list->next, plist);
755 head = rht_dereference_bucket(head->next, tbl, hash);
756 RCU_INIT_POINTER(list->rhead.next, head);
757 if (pprev) {
758 rcu_assign_pointer(*pprev, obj);
759 rht_unlock(tbl, bkt);
760 } else
761 rht_assign_unlock(tbl, bkt, obj);
762 data = NULL;
763 goto out;
764 }
765
766 if (elasticity <= 0)
767 goto slow_path;
768
769 data = ERR_PTR(-E2BIG);
770 if (unlikely(rht_grow_above_max(ht, tbl)))
771 goto out_unlock;
772
773 if (unlikely(rht_grow_above_100(ht, tbl)))
774 goto slow_path;
775
776
777 head = rht_ptr(bkt, tbl, hash);
778
779 RCU_INIT_POINTER(obj->next, head);
780 if (rhlist) {
781 struct rhlist_head *list;
782
783 list = container_of(obj, struct rhlist_head, rhead);
784 RCU_INIT_POINTER(list->next, NULL);
785 }
786
787 atomic_inc(&ht->nelems);
788 rht_assign_unlock(tbl, bkt, obj);
789
790 if (rht_grow_above_75(ht, tbl))
791 schedule_work(&ht->run_work);
792
793 data = NULL;
794out:
795 rcu_read_unlock();
796
797 return data;
798
799out_unlock:
800 rht_unlock(tbl, bkt);
801 goto out;
802}
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819static inline int rhashtable_insert_fast(
820 struct rhashtable *ht, struct rhash_head *obj,
821 const struct rhashtable_params params)
822{
823 void *ret;
824
825 ret = __rhashtable_insert_fast(ht, NULL, obj, params, false);
826 if (IS_ERR(ret))
827 return PTR_ERR(ret);
828
829 return ret == NULL ? 0 : -EEXIST;
830}
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848static inline int rhltable_insert_key(
849 struct rhltable *hlt, const void *key, struct rhlist_head *list,
850 const struct rhashtable_params params)
851{
852 return PTR_ERR(__rhashtable_insert_fast(&hlt->ht, key, &list->rhead,
853 params, true));
854}
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871static inline int rhltable_insert(
872 struct rhltable *hlt, struct rhlist_head *list,
873 const struct rhashtable_params params)
874{
875 const char *key = rht_obj(&hlt->ht, &list->rhead);
876
877 key += params.key_offset;
878
879 return rhltable_insert_key(hlt, key, list, params);
880}
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896static inline int rhashtable_lookup_insert_fast(
897 struct rhashtable *ht, struct rhash_head *obj,
898 const struct rhashtable_params params)
899{
900 const char *key = rht_obj(ht, obj);
901 void *ret;
902
903 BUG_ON(ht->p.obj_hashfn);
904
905 ret = __rhashtable_insert_fast(ht, key + ht->p.key_offset, obj, params,
906 false);
907 if (IS_ERR(ret))
908 return PTR_ERR(ret);
909
910 return ret == NULL ? 0 : -EEXIST;
911}
912
913
914
915
916
917
918
919
920
921
922
923static inline void *rhashtable_lookup_get_insert_fast(
924 struct rhashtable *ht, struct rhash_head *obj,
925 const struct rhashtable_params params)
926{
927 const char *key = rht_obj(ht, obj);
928
929 BUG_ON(ht->p.obj_hashfn);
930
931 return __rhashtable_insert_fast(ht, key + ht->p.key_offset, obj, params,
932 false);
933}
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950static inline int rhashtable_lookup_insert_key(
951 struct rhashtable *ht, const void *key, struct rhash_head *obj,
952 const struct rhashtable_params params)
953{
954 void *ret;
955
956 BUG_ON(!ht->p.obj_hashfn || !key);
957
958 ret = __rhashtable_insert_fast(ht, key, obj, params, false);
959 if (IS_ERR(ret))
960 return PTR_ERR(ret);
961
962 return ret == NULL ? 0 : -EEXIST;
963}
964
965
966
967
968
969
970
971
972
973
974
975
976static inline void *rhashtable_lookup_get_insert_key(
977 struct rhashtable *ht, const void *key, struct rhash_head *obj,
978 const struct rhashtable_params params)
979{
980 BUG_ON(!ht->p.obj_hashfn || !key);
981
982 return __rhashtable_insert_fast(ht, key, obj, params, false);
983}
984
985
986static inline int __rhashtable_remove_fast_one(
987 struct rhashtable *ht, struct bucket_table *tbl,
988 struct rhash_head *obj, const struct rhashtable_params params,
989 bool rhlist)
990{
991 struct rhash_lock_head __rcu **bkt;
992 struct rhash_head __rcu **pprev;
993 struct rhash_head *he;
994 unsigned int hash;
995 int err = -ENOENT;
996
997 hash = rht_head_hashfn(ht, tbl, obj, params);
998 bkt = rht_bucket_var(tbl, hash);
999 if (!bkt)
1000 return -ENOENT;
1001 pprev = NULL;
1002 rht_lock(tbl, bkt);
1003
1004 rht_for_each_from(he, rht_ptr(bkt, tbl, hash), tbl, hash) {
1005 struct rhlist_head *list;
1006
1007 list = container_of(he, struct rhlist_head, rhead);
1008
1009 if (he != obj) {
1010 struct rhlist_head __rcu **lpprev;
1011
1012 pprev = &he->next;
1013
1014 if (!rhlist)
1015 continue;
1016
1017 do {
1018 lpprev = &list->next;
1019 list = rht_dereference_bucket(list->next,
1020 tbl, hash);
1021 } while (list && obj != &list->rhead);
1022
1023 if (!list)
1024 continue;
1025
1026 list = rht_dereference_bucket(list->next, tbl, hash);
1027 RCU_INIT_POINTER(*lpprev, list);
1028 err = 0;
1029 break;
1030 }
1031
1032 obj = rht_dereference_bucket(obj->next, tbl, hash);
1033 err = 1;
1034
1035 if (rhlist) {
1036 list = rht_dereference_bucket(list->next, tbl, hash);
1037 if (list) {
1038 RCU_INIT_POINTER(list->rhead.next, obj);
1039 obj = &list->rhead;
1040 err = 0;
1041 }
1042 }
1043
1044 if (pprev) {
1045 rcu_assign_pointer(*pprev, obj);
1046 rht_unlock(tbl, bkt);
1047 } else {
1048 rht_assign_unlock(tbl, bkt, obj);
1049 }
1050 goto unlocked;
1051 }
1052
1053 rht_unlock(tbl, bkt);
1054unlocked:
1055 if (err > 0) {
1056 atomic_dec(&ht->nelems);
1057 if (unlikely(ht->p.automatic_shrinking &&
1058 rht_shrink_below_30(ht, tbl)))
1059 schedule_work(&ht->run_work);
1060 err = 0;
1061 }
1062
1063 return err;
1064}
1065
1066
1067static inline int __rhashtable_remove_fast(
1068 struct rhashtable *ht, struct rhash_head *obj,
1069 const struct rhashtable_params params, bool rhlist)
1070{
1071 struct bucket_table *tbl;
1072 int err;
1073
1074 rcu_read_lock();
1075
1076 tbl = rht_dereference_rcu(ht->tbl, ht);
1077
1078
1079
1080
1081
1082
1083 while ((err = __rhashtable_remove_fast_one(ht, tbl, obj, params,
1084 rhlist)) &&
1085 (tbl = rht_dereference_rcu(tbl->future_tbl, ht)))
1086 ;
1087
1088 rcu_read_unlock();
1089
1090 return err;
1091}
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108static inline int rhashtable_remove_fast(
1109 struct rhashtable *ht, struct rhash_head *obj,
1110 const struct rhashtable_params params)
1111{
1112 return __rhashtable_remove_fast(ht, obj, params, false);
1113}
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130static inline int rhltable_remove(
1131 struct rhltable *hlt, struct rhlist_head *list,
1132 const struct rhashtable_params params)
1133{
1134 return __rhashtable_remove_fast(&hlt->ht, &list->rhead, params, true);
1135}
1136
1137
1138static inline int __rhashtable_replace_fast(
1139 struct rhashtable *ht, struct bucket_table *tbl,
1140 struct rhash_head *obj_old, struct rhash_head *obj_new,
1141 const struct rhashtable_params params)
1142{
1143 struct rhash_lock_head __rcu **bkt;
1144 struct rhash_head __rcu **pprev;
1145 struct rhash_head *he;
1146 unsigned int hash;
1147 int err = -ENOENT;
1148
1149
1150
1151
1152 hash = rht_head_hashfn(ht, tbl, obj_old, params);
1153 if (hash != rht_head_hashfn(ht, tbl, obj_new, params))
1154 return -EINVAL;
1155
1156 bkt = rht_bucket_var(tbl, hash);
1157 if (!bkt)
1158 return -ENOENT;
1159
1160 pprev = NULL;
1161 rht_lock(tbl, bkt);
1162
1163 rht_for_each_from(he, rht_ptr(bkt, tbl, hash), tbl, hash) {
1164 if (he != obj_old) {
1165 pprev = &he->next;
1166 continue;
1167 }
1168
1169 rcu_assign_pointer(obj_new->next, obj_old->next);
1170 if (pprev) {
1171 rcu_assign_pointer(*pprev, obj_new);
1172 rht_unlock(tbl, bkt);
1173 } else {
1174 rht_assign_unlock(tbl, bkt, obj_new);
1175 }
1176 err = 0;
1177 goto unlocked;
1178 }
1179
1180 rht_unlock(tbl, bkt);
1181
1182unlocked:
1183 return err;
1184}
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200static inline int rhashtable_replace_fast(
1201 struct rhashtable *ht, struct rhash_head *obj_old,
1202 struct rhash_head *obj_new,
1203 const struct rhashtable_params params)
1204{
1205 struct bucket_table *tbl;
1206 int err;
1207
1208 rcu_read_lock();
1209
1210 tbl = rht_dereference_rcu(ht->tbl, ht);
1211
1212
1213
1214
1215
1216
1217 while ((err = __rhashtable_replace_fast(ht, tbl, obj_old,
1218 obj_new, params)) &&
1219 (tbl = rht_dereference_rcu(tbl->future_tbl, ht)))
1220 ;
1221
1222 rcu_read_unlock();
1223
1224 return err;
1225}
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248static inline void rhltable_walk_enter(struct rhltable *hlt,
1249 struct rhashtable_iter *iter)
1250{
1251 return rhashtable_walk_enter(&hlt->ht, iter);
1252}
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262static inline void rhltable_free_and_destroy(struct rhltable *hlt,
1263 void (*free_fn)(void *ptr,
1264 void *arg),
1265 void *arg)
1266{
1267 return rhashtable_free_and_destroy(&hlt->ht, free_fn, arg);
1268}
1269
1270static inline void rhltable_destroy(struct rhltable *hlt)
1271{
1272 return rhltable_free_and_destroy(hlt, NULL, NULL);
1273}
1274
1275#endif
1276