1
2
3
4
5
6
7
8
9
10
11
12#include <linux/bitmap.h>
13#include <linux/bitops.h>
14#include <linux/bug.h>
15#include <linux/cpu.h>
16#include <linux/errno.h>
17#include <linux/export.h>
18#include <linux/idr.h>
19#include <linux/init.h>
20#include <linux/kernel.h>
21#include <linux/kmemleak.h>
22#include <linux/percpu.h>
23#include <linux/preempt.h>
24#include <linux/radix-tree.h>
25#include <linux/rcupdate.h>
26#include <linux/slab.h>
27#include <linux/string.h>
28#include <linux/xarray.h>
29
30
31
32
33
34struct kmem_cache *radix_tree_node_cachep;
35
36
37
38
39
40
41
42
43
44
45
46
47#define RADIX_TREE_PRELOAD_SIZE (RADIX_TREE_MAX_PATH * 2 - 1)
48
49
50
51
52
53#define IDR_INDEX_BITS (8 * sizeof(int) - 1)
54#define IDR_MAX_PATH (DIV_ROUND_UP(IDR_INDEX_BITS, \
55 RADIX_TREE_MAP_SHIFT))
56#define IDR_PRELOAD_SIZE (IDR_MAX_PATH * 2 - 1)
57
58
59
60
61struct radix_tree_preload {
62 unsigned nr;
63
64 struct radix_tree_node *nodes;
65};
66static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };
67
68static inline struct radix_tree_node *entry_to_node(void *ptr)
69{
70 return (void *)((unsigned long)ptr & ~RADIX_TREE_INTERNAL_NODE);
71}
72
73static inline void *node_to_entry(void *ptr)
74{
75 return (void *)((unsigned long)ptr | RADIX_TREE_INTERNAL_NODE);
76}
77
78#define RADIX_TREE_RETRY XA_RETRY_ENTRY
79
80static inline unsigned long
81get_slot_offset(const struct radix_tree_node *parent, void __rcu **slot)
82{
83 return parent ? slot - parent->slots : 0;
84}
85
86static unsigned int radix_tree_descend(const struct radix_tree_node *parent,
87 struct radix_tree_node **nodep, unsigned long index)
88{
89 unsigned int offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK;
90 void __rcu **entry = rcu_dereference_raw(parent->slots[offset]);
91
92 *nodep = (void *)entry;
93 return offset;
94}
95
96static inline gfp_t root_gfp_mask(const struct radix_tree_root *root)
97{
98 return root->xa_flags & (__GFP_BITS_MASK & ~GFP_ZONEMASK);
99}
100
101static inline void tag_set(struct radix_tree_node *node, unsigned int tag,
102 int offset)
103{
104 __set_bit(offset, node->tags[tag]);
105}
106
107static inline void tag_clear(struct radix_tree_node *node, unsigned int tag,
108 int offset)
109{
110 __clear_bit(offset, node->tags[tag]);
111}
112
113static inline int tag_get(const struct radix_tree_node *node, unsigned int tag,
114 int offset)
115{
116 return test_bit(offset, node->tags[tag]);
117}
118
119static inline void root_tag_set(struct radix_tree_root *root, unsigned tag)
120{
121 root->xa_flags |= (__force gfp_t)(1 << (tag + ROOT_TAG_SHIFT));
122}
123
124static inline void root_tag_clear(struct radix_tree_root *root, unsigned tag)
125{
126 root->xa_flags &= (__force gfp_t)~(1 << (tag + ROOT_TAG_SHIFT));
127}
128
129static inline void root_tag_clear_all(struct radix_tree_root *root)
130{
131 root->xa_flags &= (__force gfp_t)((1 << ROOT_TAG_SHIFT) - 1);
132}
133
134static inline int root_tag_get(const struct radix_tree_root *root, unsigned tag)
135{
136 return (__force int)root->xa_flags & (1 << (tag + ROOT_TAG_SHIFT));
137}
138
139static inline unsigned root_tags_get(const struct radix_tree_root *root)
140{
141 return (__force unsigned)root->xa_flags >> ROOT_TAG_SHIFT;
142}
143
144static inline bool is_idr(const struct radix_tree_root *root)
145{
146 return !!(root->xa_flags & ROOT_IS_IDR);
147}
148
149
150
151
152
153static inline int any_tag_set(const struct radix_tree_node *node,
154 unsigned int tag)
155{
156 unsigned idx;
157 for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
158 if (node->tags[tag][idx])
159 return 1;
160 }
161 return 0;
162}
163
164static inline void all_tag_set(struct radix_tree_node *node, unsigned int tag)
165{
166 bitmap_fill(node->tags[tag], RADIX_TREE_MAP_SIZE);
167}
168
169
170
171
172
173
174
175
176
177
178
179
180static __always_inline unsigned long
181radix_tree_find_next_bit(struct radix_tree_node *node, unsigned int tag,
182 unsigned long offset)
183{
184 const unsigned long *addr = node->tags[tag];
185
186 if (offset < RADIX_TREE_MAP_SIZE) {
187 unsigned long tmp;
188
189 addr += offset / BITS_PER_LONG;
190 tmp = *addr >> (offset % BITS_PER_LONG);
191 if (tmp)
192 return __ffs(tmp) + offset;
193 offset = (offset + BITS_PER_LONG) & ~(BITS_PER_LONG - 1);
194 while (offset < RADIX_TREE_MAP_SIZE) {
195 tmp = *++addr;
196 if (tmp)
197 return __ffs(tmp) + offset;
198 offset += BITS_PER_LONG;
199 }
200 }
201 return RADIX_TREE_MAP_SIZE;
202}
203
204static unsigned int iter_offset(const struct radix_tree_iter *iter)
205{
206 return iter->index & RADIX_TREE_MAP_MASK;
207}
208
209
210
211
212static inline unsigned long shift_maxindex(unsigned int shift)
213{
214 return (RADIX_TREE_MAP_SIZE << shift) - 1;
215}
216
217static inline unsigned long node_maxindex(const struct radix_tree_node *node)
218{
219 return shift_maxindex(node->shift);
220}
221
222static unsigned long next_index(unsigned long index,
223 const struct radix_tree_node *node,
224 unsigned long offset)
225{
226 return (index & ~node_maxindex(node)) + (offset << node->shift);
227}
228
229
230
231
232
233static struct radix_tree_node *
234radix_tree_node_alloc(gfp_t gfp_mask, struct radix_tree_node *parent,
235 struct radix_tree_root *root,
236 unsigned int shift, unsigned int offset,
237 unsigned int count, unsigned int nr_values)
238{
239 struct radix_tree_node *ret = NULL;
240
241
242
243
244
245
246 if (!gfpflags_allow_blocking(gfp_mask) && !in_interrupt()) {
247 struct radix_tree_preload *rtp;
248
249
250
251
252
253
254 ret = kmem_cache_alloc(radix_tree_node_cachep,
255 gfp_mask | __GFP_NOWARN);
256 if (ret)
257 goto out;
258
259
260
261
262
263
264 rtp = this_cpu_ptr(&radix_tree_preloads);
265 if (rtp->nr) {
266 ret = rtp->nodes;
267 rtp->nodes = ret->parent;
268 rtp->nr--;
269 }
270
271
272
273
274 kmemleak_update_trace(ret);
275 goto out;
276 }
277 ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
278out:
279 BUG_ON(radix_tree_is_internal_node(ret));
280 if (ret) {
281 ret->shift = shift;
282 ret->offset = offset;
283 ret->count = count;
284 ret->nr_values = nr_values;
285 ret->parent = parent;
286 ret->array = root;
287 }
288 return ret;
289}
290
291void radix_tree_node_rcu_free(struct rcu_head *head)
292{
293 struct radix_tree_node *node =
294 container_of(head, struct radix_tree_node, rcu_head);
295
296
297
298
299
300
301 memset(node->slots, 0, sizeof(node->slots));
302 memset(node->tags, 0, sizeof(node->tags));
303 INIT_LIST_HEAD(&node->private_list);
304
305 kmem_cache_free(radix_tree_node_cachep, node);
306}
307
308static inline void
309radix_tree_node_free(struct radix_tree_node *node)
310{
311 call_rcu(&node->rcu_head, radix_tree_node_rcu_free);
312}
313
314
315
316
317
318
319
320
321
322
323static __must_check int __radix_tree_preload(gfp_t gfp_mask, unsigned nr)
324{
325 struct radix_tree_preload *rtp;
326 struct radix_tree_node *node;
327 int ret = -ENOMEM;
328
329
330
331
332
333 gfp_mask &= ~__GFP_ACCOUNT;
334
335 preempt_disable();
336 rtp = this_cpu_ptr(&radix_tree_preloads);
337 while (rtp->nr < nr) {
338 preempt_enable();
339 node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
340 if (node == NULL)
341 goto out;
342 preempt_disable();
343 rtp = this_cpu_ptr(&radix_tree_preloads);
344 if (rtp->nr < nr) {
345 node->parent = rtp->nodes;
346 rtp->nodes = node;
347 rtp->nr++;
348 } else {
349 kmem_cache_free(radix_tree_node_cachep, node);
350 }
351 }
352 ret = 0;
353out:
354 return ret;
355}
356
357
358
359
360
361
362
363
364
365
366int radix_tree_preload(gfp_t gfp_mask)
367{
368
369 WARN_ON_ONCE(!gfpflags_allow_blocking(gfp_mask));
370 return __radix_tree_preload(gfp_mask, RADIX_TREE_PRELOAD_SIZE);
371}
372EXPORT_SYMBOL(radix_tree_preload);
373
374
375
376
377
378
379int radix_tree_maybe_preload(gfp_t gfp_mask)
380{
381 if (gfpflags_allow_blocking(gfp_mask))
382 return __radix_tree_preload(gfp_mask, RADIX_TREE_PRELOAD_SIZE);
383
384 preempt_disable();
385 return 0;
386}
387EXPORT_SYMBOL(radix_tree_maybe_preload);
388
389static unsigned radix_tree_load_root(const struct radix_tree_root *root,
390 struct radix_tree_node **nodep, unsigned long *maxindex)
391{
392 struct radix_tree_node *node = rcu_dereference_raw(root->xa_head);
393
394 *nodep = node;
395
396 if (likely(radix_tree_is_internal_node(node))) {
397 node = entry_to_node(node);
398 *maxindex = node_maxindex(node);
399 return node->shift + RADIX_TREE_MAP_SHIFT;
400 }
401
402 *maxindex = 0;
403 return 0;
404}
405
406
407
408
409static int radix_tree_extend(struct radix_tree_root *root, gfp_t gfp,
410 unsigned long index, unsigned int shift)
411{
412 void *entry;
413 unsigned int maxshift;
414 int tag;
415
416
417 maxshift = shift;
418 while (index > shift_maxindex(maxshift))
419 maxshift += RADIX_TREE_MAP_SHIFT;
420
421 entry = rcu_dereference_raw(root->xa_head);
422 if (!entry && (!is_idr(root) || root_tag_get(root, IDR_FREE)))
423 goto out;
424
425 do {
426 struct radix_tree_node *node = radix_tree_node_alloc(gfp, NULL,
427 root, shift, 0, 1, 0);
428 if (!node)
429 return -ENOMEM;
430
431 if (is_idr(root)) {
432 all_tag_set(node, IDR_FREE);
433 if (!root_tag_get(root, IDR_FREE)) {
434 tag_clear(node, IDR_FREE, 0);
435 root_tag_set(root, IDR_FREE);
436 }
437 } else {
438
439 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
440 if (root_tag_get(root, tag))
441 tag_set(node, tag, 0);
442 }
443 }
444
445 BUG_ON(shift > BITS_PER_LONG);
446 if (radix_tree_is_internal_node(entry)) {
447 entry_to_node(entry)->parent = node;
448 } else if (xa_is_value(entry)) {
449
450 node->nr_values = 1;
451 }
452
453
454
455
456 node->slots[0] = (void __rcu *)entry;
457 entry = node_to_entry(node);
458 rcu_assign_pointer(root->xa_head, entry);
459 shift += RADIX_TREE_MAP_SHIFT;
460 } while (shift <= maxshift);
461out:
462 return maxshift + RADIX_TREE_MAP_SHIFT;
463}
464
465
466
467
468
469static inline bool radix_tree_shrink(struct radix_tree_root *root)
470{
471 bool shrunk = false;
472
473 for (;;) {
474 struct radix_tree_node *node = rcu_dereference_raw(root->xa_head);
475 struct radix_tree_node *child;
476
477 if (!radix_tree_is_internal_node(node))
478 break;
479 node = entry_to_node(node);
480
481
482
483
484
485 if (node->count != 1)
486 break;
487 child = rcu_dereference_raw(node->slots[0]);
488 if (!child)
489 break;
490
491
492
493
494
495
496 if (!node->shift && is_idr(root))
497 break;
498
499 if (radix_tree_is_internal_node(child))
500 entry_to_node(child)->parent = NULL;
501
502
503
504
505
506
507
508
509 root->xa_head = (void __rcu *)child;
510 if (is_idr(root) && !tag_get(node, IDR_FREE, 0))
511 root_tag_clear(root, IDR_FREE);
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531 node->count = 0;
532 if (!radix_tree_is_internal_node(child)) {
533 node->slots[0] = (void __rcu *)RADIX_TREE_RETRY;
534 }
535
536 WARN_ON_ONCE(!list_empty(&node->private_list));
537 radix_tree_node_free(node);
538 shrunk = true;
539 }
540
541 return shrunk;
542}
543
544static bool delete_node(struct radix_tree_root *root,
545 struct radix_tree_node *node)
546{
547 bool deleted = false;
548
549 do {
550 struct radix_tree_node *parent;
551
552 if (node->count) {
553 if (node_to_entry(node) ==
554 rcu_dereference_raw(root->xa_head))
555 deleted |= radix_tree_shrink(root);
556 return deleted;
557 }
558
559 parent = node->parent;
560 if (parent) {
561 parent->slots[node->offset] = NULL;
562 parent->count--;
563 } else {
564
565
566
567
568 if (!is_idr(root))
569 root_tag_clear_all(root);
570 root->xa_head = NULL;
571 }
572
573 WARN_ON_ONCE(!list_empty(&node->private_list));
574 radix_tree_node_free(node);
575 deleted = true;
576
577 node = parent;
578 } while (node);
579
580 return deleted;
581}
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599static int __radix_tree_create(struct radix_tree_root *root,
600 unsigned long index, struct radix_tree_node **nodep,
601 void __rcu ***slotp)
602{
603 struct radix_tree_node *node = NULL, *child;
604 void __rcu **slot = (void __rcu **)&root->xa_head;
605 unsigned long maxindex;
606 unsigned int shift, offset = 0;
607 unsigned long max = index;
608 gfp_t gfp = root_gfp_mask(root);
609
610 shift = radix_tree_load_root(root, &child, &maxindex);
611
612
613 if (max > maxindex) {
614 int error = radix_tree_extend(root, gfp, max, shift);
615 if (error < 0)
616 return error;
617 shift = error;
618 child = rcu_dereference_raw(root->xa_head);
619 }
620
621 while (shift > 0) {
622 shift -= RADIX_TREE_MAP_SHIFT;
623 if (child == NULL) {
624
625 child = radix_tree_node_alloc(gfp, node, root, shift,
626 offset, 0, 0);
627 if (!child)
628 return -ENOMEM;
629 rcu_assign_pointer(*slot, node_to_entry(child));
630 if (node)
631 node->count++;
632 } else if (!radix_tree_is_internal_node(child))
633 break;
634
635
636 node = entry_to_node(child);
637 offset = radix_tree_descend(node, &child, index);
638 slot = &node->slots[offset];
639 }
640
641 if (nodep)
642 *nodep = node;
643 if (slotp)
644 *slotp = slot;
645 return 0;
646}
647
648
649
650
651
652
653
654
655
656
657static void radix_tree_free_nodes(struct radix_tree_node *node)
658{
659 unsigned offset = 0;
660 struct radix_tree_node *child = entry_to_node(node);
661
662 for (;;) {
663 void *entry = rcu_dereference_raw(child->slots[offset]);
664 if (xa_is_node(entry) && child->shift) {
665 child = entry_to_node(entry);
666 offset = 0;
667 continue;
668 }
669 offset++;
670 while (offset == RADIX_TREE_MAP_SIZE) {
671 struct radix_tree_node *old = child;
672 offset = child->offset + 1;
673 child = child->parent;
674 WARN_ON_ONCE(!list_empty(&old->private_list));
675 radix_tree_node_free(old);
676 if (old == entry_to_node(node))
677 return;
678 }
679 }
680}
681
682static inline int insert_entries(struct radix_tree_node *node,
683 void __rcu **slot, void *item, bool replace)
684{
685 if (*slot)
686 return -EEXIST;
687 rcu_assign_pointer(*slot, item);
688 if (node) {
689 node->count++;
690 if (xa_is_value(item))
691 node->nr_values++;
692 }
693 return 1;
694}
695
696
697
698
699
700
701
702
703
704int radix_tree_insert(struct radix_tree_root *root, unsigned long index,
705 void *item)
706{
707 struct radix_tree_node *node;
708 void __rcu **slot;
709 int error;
710
711 BUG_ON(radix_tree_is_internal_node(item));
712
713 error = __radix_tree_create(root, index, &node, &slot);
714 if (error)
715 return error;
716
717 error = insert_entries(node, slot, item, false);
718 if (error < 0)
719 return error;
720
721 if (node) {
722 unsigned offset = get_slot_offset(node, slot);
723 BUG_ON(tag_get(node, 0, offset));
724 BUG_ON(tag_get(node, 1, offset));
725 BUG_ON(tag_get(node, 2, offset));
726 } else {
727 BUG_ON(root_tags_get(root));
728 }
729
730 return 0;
731}
732EXPORT_SYMBOL(radix_tree_insert);
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748void *__radix_tree_lookup(const struct radix_tree_root *root,
749 unsigned long index, struct radix_tree_node **nodep,
750 void __rcu ***slotp)
751{
752 struct radix_tree_node *node, *parent;
753 unsigned long maxindex;
754 void __rcu **slot;
755
756 restart:
757 parent = NULL;
758 slot = (void __rcu **)&root->xa_head;
759 radix_tree_load_root(root, &node, &maxindex);
760 if (index > maxindex)
761 return NULL;
762
763 while (radix_tree_is_internal_node(node)) {
764 unsigned offset;
765
766 parent = entry_to_node(node);
767 offset = radix_tree_descend(parent, &node, index);
768 slot = parent->slots + offset;
769 if (node == RADIX_TREE_RETRY)
770 goto restart;
771 if (parent->shift == 0)
772 break;
773 }
774
775 if (nodep)
776 *nodep = parent;
777 if (slotp)
778 *slotp = slot;
779 return node;
780}
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795void __rcu **radix_tree_lookup_slot(const struct radix_tree_root *root,
796 unsigned long index)
797{
798 void __rcu **slot;
799
800 if (!__radix_tree_lookup(root, index, NULL, &slot))
801 return NULL;
802 return slot;
803}
804EXPORT_SYMBOL(radix_tree_lookup_slot);
805
806
807
808
809
810
811
812
813
814
815
816
817
818void *radix_tree_lookup(const struct radix_tree_root *root, unsigned long index)
819{
820 return __radix_tree_lookup(root, index, NULL, NULL);
821}
822EXPORT_SYMBOL(radix_tree_lookup);
823
824static void replace_slot(void __rcu **slot, void *item,
825 struct radix_tree_node *node, int count, int values)
826{
827 if (node && (count || values)) {
828 node->count += count;
829 node->nr_values += values;
830 }
831
832 rcu_assign_pointer(*slot, item);
833}
834
835static bool node_tag_get(const struct radix_tree_root *root,
836 const struct radix_tree_node *node,
837 unsigned int tag, unsigned int offset)
838{
839 if (node)
840 return tag_get(node, tag, offset);
841 return root_tag_get(root, tag);
842}
843
844
845
846
847
848
849
850
851static int calculate_count(struct radix_tree_root *root,
852 struct radix_tree_node *node, void __rcu **slot,
853 void *item, void *old)
854{
855 if (is_idr(root)) {
856 unsigned offset = get_slot_offset(node, slot);
857 bool free = node_tag_get(root, node, IDR_FREE, offset);
858 if (!free)
859 return 0;
860 if (!old)
861 return 1;
862 }
863 return !!item - !!old;
864}
865
866
867
868
869
870
871
872
873
874
875
876void __radix_tree_replace(struct radix_tree_root *root,
877 struct radix_tree_node *node,
878 void __rcu **slot, void *item)
879{
880 void *old = rcu_dereference_raw(*slot);
881 int values = !!xa_is_value(item) - !!xa_is_value(old);
882 int count = calculate_count(root, node, slot, item, old);
883
884
885
886
887
888
889 WARN_ON_ONCE(!node && (slot != (void __rcu **)&root->xa_head) &&
890 (count || values));
891 replace_slot(slot, item, node, count, values);
892
893 if (!node)
894 return;
895
896 delete_node(root, node);
897}
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915void radix_tree_replace_slot(struct radix_tree_root *root,
916 void __rcu **slot, void *item)
917{
918 __radix_tree_replace(root, NULL, slot, item);
919}
920EXPORT_SYMBOL(radix_tree_replace_slot);
921
922
923
924
925
926
927
928
929
930
931void radix_tree_iter_replace(struct radix_tree_root *root,
932 const struct radix_tree_iter *iter,
933 void __rcu **slot, void *item)
934{
935 __radix_tree_replace(root, iter->node, slot, item);
936}
937
938static void node_tag_set(struct radix_tree_root *root,
939 struct radix_tree_node *node,
940 unsigned int tag, unsigned int offset)
941{
942 while (node) {
943 if (tag_get(node, tag, offset))
944 return;
945 tag_set(node, tag, offset);
946 offset = node->offset;
947 node = node->parent;
948 }
949
950 if (!root_tag_get(root, tag))
951 root_tag_set(root, tag);
952}
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967void *radix_tree_tag_set(struct radix_tree_root *root,
968 unsigned long index, unsigned int tag)
969{
970 struct radix_tree_node *node, *parent;
971 unsigned long maxindex;
972
973 radix_tree_load_root(root, &node, &maxindex);
974 BUG_ON(index > maxindex);
975
976 while (radix_tree_is_internal_node(node)) {
977 unsigned offset;
978
979 parent = entry_to_node(node);
980 offset = radix_tree_descend(parent, &node, index);
981 BUG_ON(!node);
982
983 if (!tag_get(parent, tag, offset))
984 tag_set(parent, tag, offset);
985 }
986
987
988 if (!root_tag_get(root, tag))
989 root_tag_set(root, tag);
990
991 return node;
992}
993EXPORT_SYMBOL(radix_tree_tag_set);
994
995static void node_tag_clear(struct radix_tree_root *root,
996 struct radix_tree_node *node,
997 unsigned int tag, unsigned int offset)
998{
999 while (node) {
1000 if (!tag_get(node, tag, offset))
1001 return;
1002 tag_clear(node, tag, offset);
1003 if (any_tag_set(node, tag))
1004 return;
1005
1006 offset = node->offset;
1007 node = node->parent;
1008 }
1009
1010
1011 if (root_tag_get(root, tag))
1012 root_tag_clear(root, tag);
1013}
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029void *radix_tree_tag_clear(struct radix_tree_root *root,
1030 unsigned long index, unsigned int tag)
1031{
1032 struct radix_tree_node *node, *parent;
1033 unsigned long maxindex;
1034 int uninitialized_var(offset);
1035
1036 radix_tree_load_root(root, &node, &maxindex);
1037 if (index > maxindex)
1038 return NULL;
1039
1040 parent = NULL;
1041
1042 while (radix_tree_is_internal_node(node)) {
1043 parent = entry_to_node(node);
1044 offset = radix_tree_descend(parent, &node, index);
1045 }
1046
1047 if (node)
1048 node_tag_clear(root, parent, tag, offset);
1049
1050 return node;
1051}
1052EXPORT_SYMBOL(radix_tree_tag_clear);
1053
1054
1055
1056
1057
1058
1059
1060void radix_tree_iter_tag_clear(struct radix_tree_root *root,
1061 const struct radix_tree_iter *iter, unsigned int tag)
1062{
1063 node_tag_clear(root, iter->node, tag, iter_offset(iter));
1064}
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081int radix_tree_tag_get(const struct radix_tree_root *root,
1082 unsigned long index, unsigned int tag)
1083{
1084 struct radix_tree_node *node, *parent;
1085 unsigned long maxindex;
1086
1087 if (!root_tag_get(root, tag))
1088 return 0;
1089
1090 radix_tree_load_root(root, &node, &maxindex);
1091 if (index > maxindex)
1092 return 0;
1093
1094 while (radix_tree_is_internal_node(node)) {
1095 unsigned offset;
1096
1097 parent = entry_to_node(node);
1098 offset = radix_tree_descend(parent, &node, index);
1099
1100 if (!tag_get(parent, tag, offset))
1101 return 0;
1102 if (node == RADIX_TREE_RETRY)
1103 break;
1104 }
1105
1106 return 1;
1107}
1108EXPORT_SYMBOL(radix_tree_tag_get);
1109
1110
1111static void set_iter_tags(struct radix_tree_iter *iter,
1112 struct radix_tree_node *node, unsigned offset,
1113 unsigned tag)
1114{
1115 unsigned tag_long = offset / BITS_PER_LONG;
1116 unsigned tag_bit = offset % BITS_PER_LONG;
1117
1118 if (!node) {
1119 iter->tags = 1;
1120 return;
1121 }
1122
1123 iter->tags = node->tags[tag][tag_long] >> tag_bit;
1124
1125
1126 if (tag_long < RADIX_TREE_TAG_LONGS - 1) {
1127
1128 if (tag_bit)
1129 iter->tags |= node->tags[tag][tag_long + 1] <<
1130 (BITS_PER_LONG - tag_bit);
1131
1132 iter->next_index = __radix_tree_iter_add(iter, BITS_PER_LONG);
1133 }
1134}
1135
1136void __rcu **radix_tree_iter_resume(void __rcu **slot,
1137 struct radix_tree_iter *iter)
1138{
1139 slot++;
1140 iter->index = __radix_tree_iter_add(iter, 1);
1141 iter->next_index = iter->index;
1142 iter->tags = 0;
1143 return NULL;
1144}
1145EXPORT_SYMBOL(radix_tree_iter_resume);
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155void __rcu **radix_tree_next_chunk(const struct radix_tree_root *root,
1156 struct radix_tree_iter *iter, unsigned flags)
1157{
1158 unsigned tag = flags & RADIX_TREE_ITER_TAG_MASK;
1159 struct radix_tree_node *node, *child;
1160 unsigned long index, offset, maxindex;
1161
1162 if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag))
1163 return NULL;
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174 index = iter->next_index;
1175 if (!index && iter->index)
1176 return NULL;
1177
1178 restart:
1179 radix_tree_load_root(root, &child, &maxindex);
1180 if (index > maxindex)
1181 return NULL;
1182 if (!child)
1183 return NULL;
1184
1185 if (!radix_tree_is_internal_node(child)) {
1186
1187 iter->index = index;
1188 iter->next_index = maxindex + 1;
1189 iter->tags = 1;
1190 iter->node = NULL;
1191 return (void __rcu **)&root->xa_head;
1192 }
1193
1194 do {
1195 node = entry_to_node(child);
1196 offset = radix_tree_descend(node, &child, index);
1197
1198 if ((flags & RADIX_TREE_ITER_TAGGED) ?
1199 !tag_get(node, tag, offset) : !child) {
1200
1201 if (flags & RADIX_TREE_ITER_CONTIG)
1202 return NULL;
1203
1204 if (flags & RADIX_TREE_ITER_TAGGED)
1205 offset = radix_tree_find_next_bit(node, tag,
1206 offset + 1);
1207 else
1208 while (++offset < RADIX_TREE_MAP_SIZE) {
1209 void *slot = rcu_dereference_raw(
1210 node->slots[offset]);
1211 if (slot)
1212 break;
1213 }
1214 index &= ~node_maxindex(node);
1215 index += offset << node->shift;
1216
1217 if (!index)
1218 return NULL;
1219 if (offset == RADIX_TREE_MAP_SIZE)
1220 goto restart;
1221 child = rcu_dereference_raw(node->slots[offset]);
1222 }
1223
1224 if (!child)
1225 goto restart;
1226 if (child == RADIX_TREE_RETRY)
1227 break;
1228 } while (node->shift && radix_tree_is_internal_node(child));
1229
1230
1231 iter->index = (index &~ node_maxindex(node)) | offset;
1232 iter->next_index = (index | node_maxindex(node)) + 1;
1233 iter->node = node;
1234
1235 if (flags & RADIX_TREE_ITER_TAGGED)
1236 set_iter_tags(iter, node, offset, tag);
1237
1238 return node->slots + offset;
1239}
1240EXPORT_SYMBOL(radix_tree_next_chunk);
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262unsigned int
1263radix_tree_gang_lookup(const struct radix_tree_root *root, void **results,
1264 unsigned long first_index, unsigned int max_items)
1265{
1266 struct radix_tree_iter iter;
1267 void __rcu **slot;
1268 unsigned int ret = 0;
1269
1270 if (unlikely(!max_items))
1271 return 0;
1272
1273 radix_tree_for_each_slot(slot, root, &iter, first_index) {
1274 results[ret] = rcu_dereference_raw(*slot);
1275 if (!results[ret])
1276 continue;
1277 if (radix_tree_is_internal_node(results[ret])) {
1278 slot = radix_tree_iter_retry(&iter);
1279 continue;
1280 }
1281 if (++ret == max_items)
1282 break;
1283 }
1284
1285 return ret;
1286}
1287EXPORT_SYMBOL(radix_tree_gang_lookup);
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302unsigned int
1303radix_tree_gang_lookup_tag(const struct radix_tree_root *root, void **results,
1304 unsigned long first_index, unsigned int max_items,
1305 unsigned int tag)
1306{
1307 struct radix_tree_iter iter;
1308 void __rcu **slot;
1309 unsigned int ret = 0;
1310
1311 if (unlikely(!max_items))
1312 return 0;
1313
1314 radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) {
1315 results[ret] = rcu_dereference_raw(*slot);
1316 if (!results[ret])
1317 continue;
1318 if (radix_tree_is_internal_node(results[ret])) {
1319 slot = radix_tree_iter_retry(&iter);
1320 continue;
1321 }
1322 if (++ret == max_items)
1323 break;
1324 }
1325
1326 return ret;
1327}
1328EXPORT_SYMBOL(radix_tree_gang_lookup_tag);
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343unsigned int
1344radix_tree_gang_lookup_tag_slot(const struct radix_tree_root *root,
1345 void __rcu ***results, unsigned long first_index,
1346 unsigned int max_items, unsigned int tag)
1347{
1348 struct radix_tree_iter iter;
1349 void __rcu **slot;
1350 unsigned int ret = 0;
1351
1352 if (unlikely(!max_items))
1353 return 0;
1354
1355 radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) {
1356 results[ret] = slot;
1357 if (++ret == max_items)
1358 break;
1359 }
1360
1361 return ret;
1362}
1363EXPORT_SYMBOL(radix_tree_gang_lookup_tag_slot);
1364
1365static bool __radix_tree_delete(struct radix_tree_root *root,
1366 struct radix_tree_node *node, void __rcu **slot)
1367{
1368 void *old = rcu_dereference_raw(*slot);
1369 int values = xa_is_value(old) ? -1 : 0;
1370 unsigned offset = get_slot_offset(node, slot);
1371 int tag;
1372
1373 if (is_idr(root))
1374 node_tag_set(root, node, IDR_FREE, offset);
1375 else
1376 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
1377 node_tag_clear(root, node, tag, offset);
1378
1379 replace_slot(slot, NULL, node, -1, values);
1380 return node && delete_node(root, node);
1381}
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395void radix_tree_iter_delete(struct radix_tree_root *root,
1396 struct radix_tree_iter *iter, void __rcu **slot)
1397{
1398 if (__radix_tree_delete(root, iter->node, slot))
1399 iter->index = iter->next_index;
1400}
1401EXPORT_SYMBOL(radix_tree_iter_delete);
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414void *radix_tree_delete_item(struct radix_tree_root *root,
1415 unsigned long index, void *item)
1416{
1417 struct radix_tree_node *node = NULL;
1418 void __rcu **slot = NULL;
1419 void *entry;
1420
1421 entry = __radix_tree_lookup(root, index, &node, &slot);
1422 if (!slot)
1423 return NULL;
1424 if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE,
1425 get_slot_offset(node, slot))))
1426 return NULL;
1427
1428 if (item && entry != item)
1429 return NULL;
1430
1431 __radix_tree_delete(root, node, slot);
1432
1433 return entry;
1434}
1435EXPORT_SYMBOL(radix_tree_delete_item);
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
1447{
1448 return radix_tree_delete_item(root, index, NULL);
1449}
1450EXPORT_SYMBOL(radix_tree_delete);
1451
1452
1453
1454
1455
1456
1457int radix_tree_tagged(const struct radix_tree_root *root, unsigned int tag)
1458{
1459 return root_tag_get(root, tag);
1460}
1461EXPORT_SYMBOL(radix_tree_tagged);
1462
1463
1464
1465
1466
1467
1468
1469
1470void idr_preload(gfp_t gfp_mask)
1471{
1472 if (__radix_tree_preload(gfp_mask, IDR_PRELOAD_SIZE))
1473 preempt_disable();
1474}
1475EXPORT_SYMBOL(idr_preload);
1476
1477void __rcu **idr_get_free(struct radix_tree_root *root,
1478 struct radix_tree_iter *iter, gfp_t gfp,
1479 unsigned long max)
1480{
1481 struct radix_tree_node *node = NULL, *child;
1482 void __rcu **slot = (void __rcu **)&root->xa_head;
1483 unsigned long maxindex, start = iter->next_index;
1484 unsigned int shift, offset = 0;
1485
1486 grow:
1487 shift = radix_tree_load_root(root, &child, &maxindex);
1488 if (!radix_tree_tagged(root, IDR_FREE))
1489 start = max(start, maxindex + 1);
1490 if (start > max)
1491 return ERR_PTR(-ENOSPC);
1492
1493 if (start > maxindex) {
1494 int error = radix_tree_extend(root, gfp, start, shift);
1495 if (error < 0)
1496 return ERR_PTR(error);
1497 shift = error;
1498 child = rcu_dereference_raw(root->xa_head);
1499 }
1500 if (start == 0 && shift == 0)
1501 shift = RADIX_TREE_MAP_SHIFT;
1502
1503 while (shift) {
1504 shift -= RADIX_TREE_MAP_SHIFT;
1505 if (child == NULL) {
1506
1507 child = radix_tree_node_alloc(gfp, node, root, shift,
1508 offset, 0, 0);
1509 if (!child)
1510 return ERR_PTR(-ENOMEM);
1511 all_tag_set(child, IDR_FREE);
1512 rcu_assign_pointer(*slot, node_to_entry(child));
1513 if (node)
1514 node->count++;
1515 } else if (!radix_tree_is_internal_node(child))
1516 break;
1517
1518 node = entry_to_node(child);
1519 offset = radix_tree_descend(node, &child, start);
1520 if (!tag_get(node, IDR_FREE, offset)) {
1521 offset = radix_tree_find_next_bit(node, IDR_FREE,
1522 offset + 1);
1523 start = next_index(start, node, offset);
1524 if (start > max || start == 0)
1525 return ERR_PTR(-ENOSPC);
1526 while (offset == RADIX_TREE_MAP_SIZE) {
1527 offset = node->offset + 1;
1528 node = node->parent;
1529 if (!node)
1530 goto grow;
1531 shift = node->shift;
1532 }
1533 child = rcu_dereference_raw(node->slots[offset]);
1534 }
1535 slot = &node->slots[offset];
1536 }
1537
1538 iter->index = start;
1539 if (node)
1540 iter->next_index = 1 + min(max, (start | node_maxindex(node)));
1541 else
1542 iter->next_index = 1;
1543 iter->node = node;
1544 set_iter_tags(iter, node, offset, IDR_FREE);
1545
1546 return slot;
1547}
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560void idr_destroy(struct idr *idr)
1561{
1562 struct radix_tree_node *node = rcu_dereference_raw(idr->idr_rt.xa_head);
1563 if (radix_tree_is_internal_node(node))
1564 radix_tree_free_nodes(node);
1565 idr->idr_rt.xa_head = NULL;
1566 root_tag_set(&idr->idr_rt, IDR_FREE);
1567}
1568EXPORT_SYMBOL(idr_destroy);
1569
1570static void
1571radix_tree_node_ctor(void *arg)
1572{
1573 struct radix_tree_node *node = arg;
1574
1575 memset(node, 0, sizeof(*node));
1576 INIT_LIST_HEAD(&node->private_list);
1577}
1578
1579static int radix_tree_cpu_dead(unsigned int cpu)
1580{
1581 struct radix_tree_preload *rtp;
1582 struct radix_tree_node *node;
1583
1584
1585 rtp = &per_cpu(radix_tree_preloads, cpu);
1586 while (rtp->nr) {
1587 node = rtp->nodes;
1588 rtp->nodes = node->parent;
1589 kmem_cache_free(radix_tree_node_cachep, node);
1590 rtp->nr--;
1591 }
1592 return 0;
1593}
1594
1595void __init radix_tree_init(void)
1596{
1597 int ret;
1598
1599 BUILD_BUG_ON(RADIX_TREE_MAX_TAGS + __GFP_BITS_SHIFT > 32);
1600 BUILD_BUG_ON(ROOT_IS_IDR & ~GFP_ZONEMASK);
1601 BUILD_BUG_ON(XA_CHUNK_SIZE > 255);
1602 radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
1603 sizeof(struct radix_tree_node), 0,
1604 SLAB_PANIC | SLAB_RECLAIM_ACCOUNT,
1605 radix_tree_node_ctor);
1606 ret = cpuhp_setup_state_nocalls(CPUHP_RADIX_DEAD, "lib/radix:dead",
1607 NULL, radix_tree_cpu_dead);
1608 WARN_ON(ret < 0);
1609}
1610