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