1
2
3
4
5
6
7
8
9#include <linux/bitmap.h>
10#include <linux/export.h>
11#include <linux/list.h>
12#include <linux/slab.h>
13#include <linux/xarray.h>
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31static inline unsigned int xa_lock_type(const struct xarray *xa)
32{
33 return (__force unsigned int)xa->xa_flags & 3;
34}
35
36static inline void xas_lock_type(struct xa_state *xas, unsigned int lock_type)
37{
38 if (lock_type == XA_LOCK_IRQ)
39 xas_lock_irq(xas);
40 else if (lock_type == XA_LOCK_BH)
41 xas_lock_bh(xas);
42 else
43 xas_lock(xas);
44}
45
46static inline void xas_unlock_type(struct xa_state *xas, unsigned int lock_type)
47{
48 if (lock_type == XA_LOCK_IRQ)
49 xas_unlock_irq(xas);
50 else if (lock_type == XA_LOCK_BH)
51 xas_unlock_bh(xas);
52 else
53 xas_unlock(xas);
54}
55
56static inline bool xa_track_free(const struct xarray *xa)
57{
58 return xa->xa_flags & XA_FLAGS_TRACK_FREE;
59}
60
61static inline bool xa_zero_busy(const struct xarray *xa)
62{
63 return xa->xa_flags & XA_FLAGS_ZERO_BUSY;
64}
65
66static inline void xa_mark_set(struct xarray *xa, xa_mark_t mark)
67{
68 if (!(xa->xa_flags & XA_FLAGS_MARK(mark)))
69 xa->xa_flags |= XA_FLAGS_MARK(mark);
70}
71
72static inline void xa_mark_clear(struct xarray *xa, xa_mark_t mark)
73{
74 if (xa->xa_flags & XA_FLAGS_MARK(mark))
75 xa->xa_flags &= ~(XA_FLAGS_MARK(mark));
76}
77
78static inline unsigned long *node_marks(struct xa_node *node, xa_mark_t mark)
79{
80 return node->marks[(__force unsigned)mark];
81}
82
83static inline bool node_get_mark(struct xa_node *node,
84 unsigned int offset, xa_mark_t mark)
85{
86 return test_bit(offset, node_marks(node, mark));
87}
88
89
90static inline bool node_set_mark(struct xa_node *node, unsigned int offset,
91 xa_mark_t mark)
92{
93 return __test_and_set_bit(offset, node_marks(node, mark));
94}
95
96
97static inline bool node_clear_mark(struct xa_node *node, unsigned int offset,
98 xa_mark_t mark)
99{
100 return __test_and_clear_bit(offset, node_marks(node, mark));
101}
102
103static inline bool node_any_mark(struct xa_node *node, xa_mark_t mark)
104{
105 return !bitmap_empty(node_marks(node, mark), XA_CHUNK_SIZE);
106}
107
108static inline void node_mark_all(struct xa_node *node, xa_mark_t mark)
109{
110 bitmap_fill(node_marks(node, mark), XA_CHUNK_SIZE);
111}
112
113#define mark_inc(mark) do { \
114 mark = (__force xa_mark_t)((__force unsigned)(mark) + 1); \
115} while (0)
116
117
118
119
120
121
122
123
124static void xas_squash_marks(const struct xa_state *xas)
125{
126 unsigned int mark = 0;
127 unsigned int limit = xas->xa_offset + xas->xa_sibs + 1;
128
129 if (!xas->xa_sibs)
130 return;
131
132 do {
133 unsigned long *marks = xas->xa_node->marks[mark];
134 if (find_next_bit(marks, limit, xas->xa_offset + 1) == limit)
135 continue;
136 __set_bit(xas->xa_offset, marks);
137 bitmap_clear(marks, xas->xa_offset + 1, xas->xa_sibs);
138 } while (mark++ != (__force unsigned)XA_MARK_MAX);
139}
140
141
142static unsigned int get_offset(unsigned long index, struct xa_node *node)
143{
144 return (index >> node->shift) & XA_CHUNK_MASK;
145}
146
147static void xas_set_offset(struct xa_state *xas)
148{
149 xas->xa_offset = get_offset(xas->xa_index, xas->xa_node);
150}
151
152
153static void xas_move_index(struct xa_state *xas, unsigned long offset)
154{
155 unsigned int shift = xas->xa_node->shift;
156 xas->xa_index &= ~XA_CHUNK_MASK << shift;
157 xas->xa_index += offset << shift;
158}
159
160static void xas_advance(struct xa_state *xas)
161{
162 xas->xa_offset++;
163 xas_move_index(xas, xas->xa_offset);
164}
165
166static void *set_bounds(struct xa_state *xas)
167{
168 xas->xa_node = XAS_BOUNDS;
169 return NULL;
170}
171
172
173
174
175
176
177
178
179static void *xas_start(struct xa_state *xas)
180{
181 void *entry;
182
183 if (xas_valid(xas))
184 return xas_reload(xas);
185 if (xas_error(xas))
186 return NULL;
187
188 entry = xa_head(xas->xa);
189 if (!xa_is_node(entry)) {
190 if (xas->xa_index)
191 return set_bounds(xas);
192 } else {
193 if ((xas->xa_index >> xa_to_node(entry)->shift) > XA_CHUNK_MASK)
194 return set_bounds(xas);
195 }
196
197 xas->xa_node = NULL;
198 return entry;
199}
200
201static void *xas_descend(struct xa_state *xas, struct xa_node *node)
202{
203 unsigned int offset = get_offset(xas->xa_index, node);
204 void *entry = xa_entry(xas->xa, node, offset);
205
206 xas->xa_node = node;
207 if (xa_is_sibling(entry)) {
208 offset = xa_to_sibling(entry);
209 entry = xa_entry(xas->xa, node, offset);
210 }
211
212 xas->xa_offset = offset;
213 return entry;
214}
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231void *xas_load(struct xa_state *xas)
232{
233 void *entry = xas_start(xas);
234
235 while (xa_is_node(entry)) {
236 struct xa_node *node = xa_to_node(entry);
237
238 if (xas->xa_shift > node->shift)
239 break;
240 entry = xas_descend(xas, node);
241 if (node->shift == 0)
242 break;
243 }
244 return entry;
245}
246EXPORT_SYMBOL_GPL(xas_load);
247
248
249extern struct kmem_cache *radix_tree_node_cachep;
250extern void radix_tree_node_rcu_free(struct rcu_head *head);
251
252#define XA_RCU_FREE ((struct xarray *)1)
253
254static void xa_node_free(struct xa_node *node)
255{
256 XA_NODE_BUG_ON(node, !list_empty(&node->private_list));
257 node->array = XA_RCU_FREE;
258 call_rcu(&node->rcu_head, radix_tree_node_rcu_free);
259}
260
261
262
263
264
265
266
267static void xas_destroy(struct xa_state *xas)
268{
269 struct xa_node *next, *node = xas->xa_alloc;
270
271 while (node) {
272 XA_NODE_BUG_ON(node, !list_empty(&node->private_list));
273 next = rcu_dereference_raw(node->parent);
274 radix_tree_node_rcu_free(&node->rcu_head);
275 xas->xa_alloc = node = next;
276 }
277}
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297bool xas_nomem(struct xa_state *xas, gfp_t gfp)
298{
299 if (xas->xa_node != XA_ERROR(-ENOMEM)) {
300 xas_destroy(xas);
301 return false;
302 }
303 if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)
304 gfp |= __GFP_ACCOUNT;
305 xas->xa_alloc = kmem_cache_alloc(radix_tree_node_cachep, gfp);
306 if (!xas->xa_alloc)
307 return false;
308 xas->xa_alloc->parent = NULL;
309 XA_NODE_BUG_ON(xas->xa_alloc, !list_empty(&xas->xa_alloc->private_list));
310 xas->xa_node = XAS_RESTART;
311 return true;
312}
313EXPORT_SYMBOL_GPL(xas_nomem);
314
315
316
317
318
319
320
321
322
323
324static bool __xas_nomem(struct xa_state *xas, gfp_t gfp)
325 __must_hold(xas->xa->xa_lock)
326{
327 unsigned int lock_type = xa_lock_type(xas->xa);
328
329 if (xas->xa_node != XA_ERROR(-ENOMEM)) {
330 xas_destroy(xas);
331 return false;
332 }
333 if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)
334 gfp |= __GFP_ACCOUNT;
335 if (gfpflags_allow_blocking(gfp)) {
336 xas_unlock_type(xas, lock_type);
337 xas->xa_alloc = kmem_cache_alloc(radix_tree_node_cachep, gfp);
338 xas_lock_type(xas, lock_type);
339 } else {
340 xas->xa_alloc = kmem_cache_alloc(radix_tree_node_cachep, gfp);
341 }
342 if (!xas->xa_alloc)
343 return false;
344 xas->xa_alloc->parent = NULL;
345 XA_NODE_BUG_ON(xas->xa_alloc, !list_empty(&xas->xa_alloc->private_list));
346 xas->xa_node = XAS_RESTART;
347 return true;
348}
349
350static void xas_update(struct xa_state *xas, struct xa_node *node)
351{
352 if (xas->xa_update)
353 xas->xa_update(node);
354 else
355 XA_NODE_BUG_ON(node, !list_empty(&node->private_list));
356}
357
358static void *xas_alloc(struct xa_state *xas, unsigned int shift)
359{
360 struct xa_node *parent = xas->xa_node;
361 struct xa_node *node = xas->xa_alloc;
362
363 if (xas_invalid(xas))
364 return NULL;
365
366 if (node) {
367 xas->xa_alloc = NULL;
368 } else {
369 gfp_t gfp = GFP_NOWAIT | __GFP_NOWARN;
370
371 if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)
372 gfp |= __GFP_ACCOUNT;
373
374 node = kmem_cache_alloc(radix_tree_node_cachep, gfp);
375 if (!node) {
376 xas_set_err(xas, -ENOMEM);
377 return NULL;
378 }
379 }
380
381 if (parent) {
382 node->offset = xas->xa_offset;
383 parent->count++;
384 XA_NODE_BUG_ON(node, parent->count > XA_CHUNK_SIZE);
385 xas_update(xas, parent);
386 }
387 XA_NODE_BUG_ON(node, shift > BITS_PER_LONG);
388 XA_NODE_BUG_ON(node, !list_empty(&node->private_list));
389 node->shift = shift;
390 node->count = 0;
391 node->nr_values = 0;
392 RCU_INIT_POINTER(node->parent, xas->xa_node);
393 node->array = xas->xa;
394
395 return node;
396}
397
398#ifdef CONFIG_XARRAY_MULTI
399
400static unsigned long xas_size(const struct xa_state *xas)
401{
402 return (xas->xa_sibs + 1UL) << xas->xa_shift;
403}
404#endif
405
406
407
408
409
410
411
412static unsigned long xas_max(struct xa_state *xas)
413{
414 unsigned long max = xas->xa_index;
415
416#ifdef CONFIG_XARRAY_MULTI
417 if (xas->xa_shift || xas->xa_sibs) {
418 unsigned long mask = xas_size(xas) - 1;
419 max |= mask;
420 if (mask == max)
421 max++;
422 }
423#endif
424
425 return max;
426}
427
428
429static unsigned long max_index(void *entry)
430{
431 if (!xa_is_node(entry))
432 return 0;
433 return (XA_CHUNK_SIZE << xa_to_node(entry)->shift) - 1;
434}
435
436static void xas_shrink(struct xa_state *xas)
437{
438 struct xarray *xa = xas->xa;
439 struct xa_node *node = xas->xa_node;
440
441 for (;;) {
442 void *entry;
443
444 XA_NODE_BUG_ON(node, node->count > XA_CHUNK_SIZE);
445 if (node->count != 1)
446 break;
447 entry = xa_entry_locked(xa, node, 0);
448 if (!entry)
449 break;
450 if (!xa_is_node(entry) && node->shift)
451 break;
452 if (xa_is_zero(entry) && xa_zero_busy(xa))
453 entry = NULL;
454 xas->xa_node = XAS_BOUNDS;
455
456 RCU_INIT_POINTER(xa->xa_head, entry);
457 if (xa_track_free(xa) && !node_get_mark(node, 0, XA_FREE_MARK))
458 xa_mark_clear(xa, XA_FREE_MARK);
459
460 node->count = 0;
461 node->nr_values = 0;
462 if (!xa_is_node(entry))
463 RCU_INIT_POINTER(node->slots[0], XA_RETRY_ENTRY);
464 xas_update(xas, node);
465 xa_node_free(node);
466 if (!xa_is_node(entry))
467 break;
468 node = xa_to_node(entry);
469 node->parent = NULL;
470 }
471}
472
473
474
475
476
477
478
479
480static void xas_delete_node(struct xa_state *xas)
481{
482 struct xa_node *node = xas->xa_node;
483
484 for (;;) {
485 struct xa_node *parent;
486
487 XA_NODE_BUG_ON(node, node->count > XA_CHUNK_SIZE);
488 if (node->count)
489 break;
490
491 parent = xa_parent_locked(xas->xa, node);
492 xas->xa_node = parent;
493 xas->xa_offset = node->offset;
494 xa_node_free(node);
495
496 if (!parent) {
497 xas->xa->xa_head = NULL;
498 xas->xa_node = XAS_BOUNDS;
499 return;
500 }
501
502 parent->slots[xas->xa_offset] = NULL;
503 parent->count--;
504 XA_NODE_BUG_ON(parent, parent->count > XA_CHUNK_SIZE);
505 node = parent;
506 xas_update(xas, node);
507 }
508
509 if (!node->parent)
510 xas_shrink(xas);
511}
512
513
514
515
516
517
518
519
520
521
522static void xas_free_nodes(struct xa_state *xas, struct xa_node *top)
523{
524 unsigned int offset = 0;
525 struct xa_node *node = top;
526
527 for (;;) {
528 void *entry = xa_entry_locked(xas->xa, node, offset);
529
530 if (node->shift && xa_is_node(entry)) {
531 node = xa_to_node(entry);
532 offset = 0;
533 continue;
534 }
535 if (entry)
536 RCU_INIT_POINTER(node->slots[offset], XA_RETRY_ENTRY);
537 offset++;
538 while (offset == XA_CHUNK_SIZE) {
539 struct xa_node *parent;
540
541 parent = xa_parent_locked(xas->xa, node);
542 offset = node->offset + 1;
543 node->count = 0;
544 node->nr_values = 0;
545 xas_update(xas, node);
546 xa_node_free(node);
547 if (node == top)
548 return;
549 node = parent;
550 }
551 }
552}
553
554
555
556
557
558static int xas_expand(struct xa_state *xas, void *head)
559{
560 struct xarray *xa = xas->xa;
561 struct xa_node *node = NULL;
562 unsigned int shift = 0;
563 unsigned long max = xas_max(xas);
564
565 if (!head) {
566 if (max == 0)
567 return 0;
568 while ((max >> shift) >= XA_CHUNK_SIZE)
569 shift += XA_CHUNK_SHIFT;
570 return shift + XA_CHUNK_SHIFT;
571 } else if (xa_is_node(head)) {
572 node = xa_to_node(head);
573 shift = node->shift + XA_CHUNK_SHIFT;
574 }
575 xas->xa_node = NULL;
576
577 while (max > max_index(head)) {
578 xa_mark_t mark = 0;
579
580 XA_NODE_BUG_ON(node, shift > BITS_PER_LONG);
581 node = xas_alloc(xas, shift);
582 if (!node)
583 return -ENOMEM;
584
585 node->count = 1;
586 if (xa_is_value(head))
587 node->nr_values = 1;
588 RCU_INIT_POINTER(node->slots[0], head);
589
590
591 for (;;) {
592 if (xa_track_free(xa) && mark == XA_FREE_MARK) {
593 node_mark_all(node, XA_FREE_MARK);
594 if (!xa_marked(xa, XA_FREE_MARK)) {
595 node_clear_mark(node, 0, XA_FREE_MARK);
596 xa_mark_set(xa, XA_FREE_MARK);
597 }
598 } else if (xa_marked(xa, mark)) {
599 node_set_mark(node, 0, mark);
600 }
601 if (mark == XA_MARK_MAX)
602 break;
603 mark_inc(mark);
604 }
605
606
607
608
609
610 if (xa_is_node(head)) {
611 xa_to_node(head)->offset = 0;
612 rcu_assign_pointer(xa_to_node(head)->parent, node);
613 }
614 head = xa_mk_node(node);
615 rcu_assign_pointer(xa->xa_head, head);
616 xas_update(xas, node);
617
618 shift += XA_CHUNK_SHIFT;
619 }
620
621 xas->xa_node = node;
622 return shift;
623}
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638static void *xas_create(struct xa_state *xas, bool allow_root)
639{
640 struct xarray *xa = xas->xa;
641 void *entry;
642 void __rcu **slot;
643 struct xa_node *node = xas->xa_node;
644 int shift;
645 unsigned int order = xas->xa_shift;
646
647 if (xas_top(node)) {
648 entry = xa_head_locked(xa);
649 xas->xa_node = NULL;
650 if (!entry && xa_zero_busy(xa))
651 entry = XA_ZERO_ENTRY;
652 shift = xas_expand(xas, entry);
653 if (shift < 0)
654 return NULL;
655 if (!shift && !allow_root)
656 shift = XA_CHUNK_SHIFT;
657 entry = xa_head_locked(xa);
658 slot = &xa->xa_head;
659 } else if (xas_error(xas)) {
660 return NULL;
661 } else if (node) {
662 unsigned int offset = xas->xa_offset;
663
664 shift = node->shift;
665 entry = xa_entry_locked(xa, node, offset);
666 slot = &node->slots[offset];
667 } else {
668 shift = 0;
669 entry = xa_head_locked(xa);
670 slot = &xa->xa_head;
671 }
672
673 while (shift > order) {
674 shift -= XA_CHUNK_SHIFT;
675 if (!entry) {
676 node = xas_alloc(xas, shift);
677 if (!node)
678 break;
679 if (xa_track_free(xa))
680 node_mark_all(node, XA_FREE_MARK);
681 rcu_assign_pointer(*slot, xa_mk_node(node));
682 } else if (xa_is_node(entry)) {
683 node = xa_to_node(entry);
684 } else {
685 break;
686 }
687 entry = xas_descend(xas, node);
688 slot = &node->slots[xas->xa_offset];
689 }
690
691 return entry;
692}
693
694
695
696
697
698
699
700
701
702
703void xas_create_range(struct xa_state *xas)
704{
705 unsigned long index = xas->xa_index;
706 unsigned char shift = xas->xa_shift;
707 unsigned char sibs = xas->xa_sibs;
708
709 xas->xa_index |= ((sibs + 1UL) << shift) - 1;
710 if (xas_is_node(xas) && xas->xa_node->shift == xas->xa_shift)
711 xas->xa_offset |= sibs;
712 xas->xa_shift = 0;
713 xas->xa_sibs = 0;
714
715 for (;;) {
716 xas_create(xas, true);
717 if (xas_error(xas))
718 goto restore;
719 if (xas->xa_index <= (index | XA_CHUNK_MASK))
720 goto success;
721 xas->xa_index -= XA_CHUNK_SIZE;
722
723 for (;;) {
724 struct xa_node *node = xas->xa_node;
725 xas->xa_node = xa_parent_locked(xas->xa, node);
726 xas->xa_offset = node->offset - 1;
727 if (node->offset != 0)
728 break;
729 }
730 }
731
732restore:
733 xas->xa_shift = shift;
734 xas->xa_sibs = sibs;
735 xas->xa_index = index;
736 return;
737success:
738 xas->xa_index = index;
739 if (xas->xa_node)
740 xas_set_offset(xas);
741}
742EXPORT_SYMBOL_GPL(xas_create_range);
743
744static void update_node(struct xa_state *xas, struct xa_node *node,
745 int count, int values)
746{
747 if (!node || (!count && !values))
748 return;
749
750 node->count += count;
751 node->nr_values += values;
752 XA_NODE_BUG_ON(node, node->count > XA_CHUNK_SIZE);
753 XA_NODE_BUG_ON(node, node->nr_values > XA_CHUNK_SIZE);
754 xas_update(xas, node);
755 if (count < 0)
756 xas_delete_node(xas);
757}
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772void *xas_store(struct xa_state *xas, void *entry)
773{
774 struct xa_node *node;
775 void __rcu **slot = &xas->xa->xa_head;
776 unsigned int offset, max;
777 int count = 0;
778 int values = 0;
779 void *first, *next;
780 bool value = xa_is_value(entry);
781
782 if (entry) {
783 bool allow_root = !xa_is_node(entry) && !xa_is_zero(entry);
784 first = xas_create(xas, allow_root);
785 } else {
786 first = xas_load(xas);
787 }
788
789 if (xas_invalid(xas))
790 return first;
791 node = xas->xa_node;
792 if (node && (xas->xa_shift < node->shift))
793 xas->xa_sibs = 0;
794 if ((first == entry) && !xas->xa_sibs)
795 return first;
796
797 next = first;
798 offset = xas->xa_offset;
799 max = xas->xa_offset + xas->xa_sibs;
800 if (node) {
801 slot = &node->slots[offset];
802 if (xas->xa_sibs)
803 xas_squash_marks(xas);
804 }
805 if (!entry)
806 xas_init_marks(xas);
807
808 for (;;) {
809
810
811
812
813
814
815
816 rcu_assign_pointer(*slot, entry);
817 if (xa_is_node(next) && (!node || node->shift))
818 xas_free_nodes(xas, xa_to_node(next));
819 if (!node)
820 break;
821 count += !next - !entry;
822 values += !xa_is_value(first) - !value;
823 if (entry) {
824 if (offset == max)
825 break;
826 if (!xa_is_sibling(entry))
827 entry = xa_mk_sibling(xas->xa_offset);
828 } else {
829 if (offset == XA_CHUNK_MASK)
830 break;
831 }
832 next = xa_entry_locked(xas->xa, node, ++offset);
833 if (!xa_is_sibling(next)) {
834 if (!entry && (offset > max))
835 break;
836 first = next;
837 }
838 slot++;
839 }
840
841 update_node(xas, node, count, values);
842 return first;
843}
844EXPORT_SYMBOL_GPL(xas_store);
845
846
847
848
849
850
851
852
853
854bool xas_get_mark(const struct xa_state *xas, xa_mark_t mark)
855{
856 if (xas_invalid(xas))
857 return false;
858 if (!xas->xa_node)
859 return xa_marked(xas->xa, mark);
860 return node_get_mark(xas->xa_node, xas->xa_offset, mark);
861}
862EXPORT_SYMBOL_GPL(xas_get_mark);
863
864
865
866
867
868
869
870
871
872
873void xas_set_mark(const struct xa_state *xas, xa_mark_t mark)
874{
875 struct xa_node *node = xas->xa_node;
876 unsigned int offset = xas->xa_offset;
877
878 if (xas_invalid(xas))
879 return;
880
881 while (node) {
882 if (node_set_mark(node, offset, mark))
883 return;
884 offset = node->offset;
885 node = xa_parent_locked(xas->xa, node);
886 }
887
888 if (!xa_marked(xas->xa, mark))
889 xa_mark_set(xas->xa, mark);
890}
891EXPORT_SYMBOL_GPL(xas_set_mark);
892
893
894
895
896
897
898
899
900
901
902void xas_clear_mark(const struct xa_state *xas, xa_mark_t mark)
903{
904 struct xa_node *node = xas->xa_node;
905 unsigned int offset = xas->xa_offset;
906
907 if (xas_invalid(xas))
908 return;
909
910 while (node) {
911 if (!node_clear_mark(node, offset, mark))
912 return;
913 if (node_any_mark(node, mark))
914 return;
915
916 offset = node->offset;
917 node = xa_parent_locked(xas->xa, node);
918 }
919
920 if (xa_marked(xas->xa, mark))
921 xa_mark_clear(xas->xa, mark);
922}
923EXPORT_SYMBOL_GPL(xas_clear_mark);
924
925
926
927
928
929
930
931
932
933
934
935
936void xas_init_marks(const struct xa_state *xas)
937{
938 xa_mark_t mark = 0;
939
940 for (;;) {
941 if (xa_track_free(xas->xa) && mark == XA_FREE_MARK)
942 xas_set_mark(xas, mark);
943 else
944 xas_clear_mark(xas, mark);
945 if (mark == XA_MARK_MAX)
946 break;
947 mark_inc(mark);
948 }
949}
950EXPORT_SYMBOL_GPL(xas_init_marks);
951
952#ifdef CONFIG_XARRAY_MULTI
953static unsigned int node_get_marks(struct xa_node *node, unsigned int offset)
954{
955 unsigned int marks = 0;
956 xa_mark_t mark = XA_MARK_0;
957
958 for (;;) {
959 if (node_get_mark(node, offset, mark))
960 marks |= 1 << (__force unsigned int)mark;
961 if (mark == XA_MARK_MAX)
962 break;
963 mark_inc(mark);
964 }
965
966 return marks;
967}
968
969static void node_set_marks(struct xa_node *node, unsigned int offset,
970 struct xa_node *child, unsigned int marks)
971{
972 xa_mark_t mark = XA_MARK_0;
973
974 for (;;) {
975 if (marks & (1 << (__force unsigned int)mark)) {
976 node_set_mark(node, offset, mark);
977 if (child)
978 node_mark_all(child, mark);
979 }
980 if (mark == XA_MARK_MAX)
981 break;
982 mark_inc(mark);
983 }
984}
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000void xas_split_alloc(struct xa_state *xas, void *entry, unsigned int order,
1001 gfp_t gfp)
1002{
1003 unsigned int sibs = (1 << (order % XA_CHUNK_SHIFT)) - 1;
1004 unsigned int mask = xas->xa_sibs;
1005
1006
1007 if (WARN_ON(xas->xa_shift + 2 * XA_CHUNK_SHIFT < order))
1008 goto nomem;
1009 if (xas->xa_shift + XA_CHUNK_SHIFT > order)
1010 return;
1011
1012 do {
1013 unsigned int i;
1014 void *sibling = NULL;
1015 struct xa_node *node;
1016
1017 node = kmem_cache_alloc(radix_tree_node_cachep, gfp);
1018 if (!node)
1019 goto nomem;
1020 node->array = xas->xa;
1021 for (i = 0; i < XA_CHUNK_SIZE; i++) {
1022 if ((i & mask) == 0) {
1023 RCU_INIT_POINTER(node->slots[i], entry);
1024 sibling = xa_mk_sibling(i);
1025 } else {
1026 RCU_INIT_POINTER(node->slots[i], sibling);
1027 }
1028 }
1029 RCU_INIT_POINTER(node->parent, xas->xa_alloc);
1030 xas->xa_alloc = node;
1031 } while (sibs-- > 0);
1032
1033 return;
1034nomem:
1035 xas_destroy(xas);
1036 xas_set_err(xas, -ENOMEM);
1037}
1038EXPORT_SYMBOL_GPL(xas_split_alloc);
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051void xas_split(struct xa_state *xas, void *entry, unsigned int order)
1052{
1053 unsigned int sibs = (1 << (order % XA_CHUNK_SHIFT)) - 1;
1054 unsigned int offset, marks;
1055 struct xa_node *node;
1056 void *curr = xas_load(xas);
1057 int values = 0;
1058
1059 node = xas->xa_node;
1060 if (xas_top(node))
1061 return;
1062
1063 marks = node_get_marks(node, xas->xa_offset);
1064
1065 offset = xas->xa_offset + sibs;
1066 do {
1067 if (xas->xa_shift < node->shift) {
1068 struct xa_node *child = xas->xa_alloc;
1069
1070 xas->xa_alloc = rcu_dereference_raw(child->parent);
1071 child->shift = node->shift - XA_CHUNK_SHIFT;
1072 child->offset = offset;
1073 child->count = XA_CHUNK_SIZE;
1074 child->nr_values = xa_is_value(entry) ?
1075 XA_CHUNK_SIZE : 0;
1076 RCU_INIT_POINTER(child->parent, node);
1077 node_set_marks(node, offset, child, marks);
1078 rcu_assign_pointer(node->slots[offset],
1079 xa_mk_node(child));
1080 if (xa_is_value(curr))
1081 values--;
1082 } else {
1083 unsigned int canon = offset - xas->xa_sibs;
1084
1085 node_set_marks(node, canon, NULL, marks);
1086 rcu_assign_pointer(node->slots[canon], entry);
1087 while (offset > canon)
1088 rcu_assign_pointer(node->slots[offset--],
1089 xa_mk_sibling(canon));
1090 values += (xa_is_value(entry) - xa_is_value(curr)) *
1091 (xas->xa_sibs + 1);
1092 }
1093 } while (offset-- > xas->xa_offset);
1094
1095 node->nr_values += values;
1096}
1097EXPORT_SYMBOL_GPL(xas_split);
1098#endif
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115void xas_pause(struct xa_state *xas)
1116{
1117 struct xa_node *node = xas->xa_node;
1118
1119 if (xas_invalid(xas))
1120 return;
1121
1122 xas->xa_node = XAS_RESTART;
1123 if (node) {
1124 unsigned long offset = xas->xa_offset;
1125 while (++offset < XA_CHUNK_SIZE) {
1126 if (!xa_is_sibling(xa_entry(xas->xa, node, offset)))
1127 break;
1128 }
1129 xas->xa_index += (offset - xas->xa_offset) << node->shift;
1130 if (xas->xa_index == 0)
1131 xas->xa_node = XAS_BOUNDS;
1132 } else {
1133 xas->xa_index++;
1134 }
1135}
1136EXPORT_SYMBOL_GPL(xas_pause);
1137
1138
1139
1140
1141
1142
1143
1144
1145void *__xas_prev(struct xa_state *xas)
1146{
1147 void *entry;
1148
1149 if (!xas_frozen(xas->xa_node))
1150 xas->xa_index--;
1151 if (!xas->xa_node)
1152 return set_bounds(xas);
1153 if (xas_not_node(xas->xa_node))
1154 return xas_load(xas);
1155
1156 if (xas->xa_offset != get_offset(xas->xa_index, xas->xa_node))
1157 xas->xa_offset--;
1158
1159 while (xas->xa_offset == 255) {
1160 xas->xa_offset = xas->xa_node->offset - 1;
1161 xas->xa_node = xa_parent(xas->xa, xas->xa_node);
1162 if (!xas->xa_node)
1163 return set_bounds(xas);
1164 }
1165
1166 for (;;) {
1167 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
1168 if (!xa_is_node(entry))
1169 return entry;
1170
1171 xas->xa_node = xa_to_node(entry);
1172 xas_set_offset(xas);
1173 }
1174}
1175EXPORT_SYMBOL_GPL(__xas_prev);
1176
1177
1178
1179
1180
1181
1182
1183
1184void *__xas_next(struct xa_state *xas)
1185{
1186 void *entry;
1187
1188 if (!xas_frozen(xas->xa_node))
1189 xas->xa_index++;
1190 if (!xas->xa_node)
1191 return set_bounds(xas);
1192 if (xas_not_node(xas->xa_node))
1193 return xas_load(xas);
1194
1195 if (xas->xa_offset != get_offset(xas->xa_index, xas->xa_node))
1196 xas->xa_offset++;
1197
1198 while (xas->xa_offset == XA_CHUNK_SIZE) {
1199 xas->xa_offset = xas->xa_node->offset + 1;
1200 xas->xa_node = xa_parent(xas->xa, xas->xa_node);
1201 if (!xas->xa_node)
1202 return set_bounds(xas);
1203 }
1204
1205 for (;;) {
1206 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
1207 if (!xa_is_node(entry))
1208 return entry;
1209
1210 xas->xa_node = xa_to_node(entry);
1211 xas_set_offset(xas);
1212 }
1213}
1214EXPORT_SYMBOL_GPL(__xas_next);
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232void *xas_find(struct xa_state *xas, unsigned long max)
1233{
1234 void *entry;
1235
1236 if (xas_error(xas) || xas->xa_node == XAS_BOUNDS)
1237 return NULL;
1238 if (xas->xa_index > max)
1239 return set_bounds(xas);
1240
1241 if (!xas->xa_node) {
1242 xas->xa_index = 1;
1243 return set_bounds(xas);
1244 } else if (xas->xa_node == XAS_RESTART) {
1245 entry = xas_load(xas);
1246 if (entry || xas_not_node(xas->xa_node))
1247 return entry;
1248 } else if (!xas->xa_node->shift &&
1249 xas->xa_offset != (xas->xa_index & XA_CHUNK_MASK)) {
1250 xas->xa_offset = ((xas->xa_index - 1) & XA_CHUNK_MASK) + 1;
1251 }
1252
1253 xas_advance(xas);
1254
1255 while (xas->xa_node && (xas->xa_index <= max)) {
1256 if (unlikely(xas->xa_offset == XA_CHUNK_SIZE)) {
1257 xas->xa_offset = xas->xa_node->offset + 1;
1258 xas->xa_node = xa_parent(xas->xa, xas->xa_node);
1259 continue;
1260 }
1261
1262 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
1263 if (xa_is_node(entry)) {
1264 xas->xa_node = xa_to_node(entry);
1265 xas->xa_offset = 0;
1266 continue;
1267 }
1268 if (entry && !xa_is_sibling(entry))
1269 return entry;
1270
1271 xas_advance(xas);
1272 }
1273
1274 if (!xas->xa_node)
1275 xas->xa_node = XAS_BOUNDS;
1276 return NULL;
1277}
1278EXPORT_SYMBOL_GPL(xas_find);
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301void *xas_find_marked(struct xa_state *xas, unsigned long max, xa_mark_t mark)
1302{
1303 bool advance = true;
1304 unsigned int offset;
1305 void *entry;
1306
1307 if (xas_error(xas))
1308 return NULL;
1309 if (xas->xa_index > max)
1310 goto max;
1311
1312 if (!xas->xa_node) {
1313 xas->xa_index = 1;
1314 goto out;
1315 } else if (xas_top(xas->xa_node)) {
1316 advance = false;
1317 entry = xa_head(xas->xa);
1318 xas->xa_node = NULL;
1319 if (xas->xa_index > max_index(entry))
1320 goto out;
1321 if (!xa_is_node(entry)) {
1322 if (xa_marked(xas->xa, mark))
1323 return entry;
1324 xas->xa_index = 1;
1325 goto out;
1326 }
1327 xas->xa_node = xa_to_node(entry);
1328 xas->xa_offset = xas->xa_index >> xas->xa_node->shift;
1329 }
1330
1331 while (xas->xa_index <= max) {
1332 if (unlikely(xas->xa_offset == XA_CHUNK_SIZE)) {
1333 xas->xa_offset = xas->xa_node->offset + 1;
1334 xas->xa_node = xa_parent(xas->xa, xas->xa_node);
1335 if (!xas->xa_node)
1336 break;
1337 advance = false;
1338 continue;
1339 }
1340
1341 if (!advance) {
1342 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
1343 if (xa_is_sibling(entry)) {
1344 xas->xa_offset = xa_to_sibling(entry);
1345 xas_move_index(xas, xas->xa_offset);
1346 }
1347 }
1348
1349 offset = xas_find_chunk(xas, advance, mark);
1350 if (offset > xas->xa_offset) {
1351 advance = false;
1352 xas_move_index(xas, offset);
1353
1354 if ((xas->xa_index - 1) >= max)
1355 goto max;
1356 xas->xa_offset = offset;
1357 if (offset == XA_CHUNK_SIZE)
1358 continue;
1359 }
1360
1361 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
1362 if (!entry && !(xa_track_free(xas->xa) && mark == XA_FREE_MARK))
1363 continue;
1364 if (!xa_is_node(entry))
1365 return entry;
1366 xas->xa_node = xa_to_node(entry);
1367 xas_set_offset(xas);
1368 }
1369
1370out:
1371 if (xas->xa_index > max)
1372 goto max;
1373 return set_bounds(xas);
1374max:
1375 xas->xa_node = XAS_RESTART;
1376 return NULL;
1377}
1378EXPORT_SYMBOL_GPL(xas_find_marked);
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389void *xas_find_conflict(struct xa_state *xas)
1390{
1391 void *curr;
1392
1393 if (xas_error(xas))
1394 return NULL;
1395
1396 if (!xas->xa_node)
1397 return NULL;
1398
1399 if (xas_top(xas->xa_node)) {
1400 curr = xas_start(xas);
1401 if (!curr)
1402 return NULL;
1403 while (xa_is_node(curr)) {
1404 struct xa_node *node = xa_to_node(curr);
1405 curr = xas_descend(xas, node);
1406 }
1407 if (curr)
1408 return curr;
1409 }
1410
1411 if (xas->xa_node->shift > xas->xa_shift)
1412 return NULL;
1413
1414 for (;;) {
1415 if (xas->xa_node->shift == xas->xa_shift) {
1416 if ((xas->xa_offset & xas->xa_sibs) == xas->xa_sibs)
1417 break;
1418 } else if (xas->xa_offset == XA_CHUNK_MASK) {
1419 xas->xa_offset = xas->xa_node->offset;
1420 xas->xa_node = xa_parent_locked(xas->xa, xas->xa_node);
1421 if (!xas->xa_node)
1422 break;
1423 continue;
1424 }
1425 curr = xa_entry_locked(xas->xa, xas->xa_node, ++xas->xa_offset);
1426 if (xa_is_sibling(curr))
1427 continue;
1428 while (xa_is_node(curr)) {
1429 xas->xa_node = xa_to_node(curr);
1430 xas->xa_offset = 0;
1431 curr = xa_entry_locked(xas->xa, xas->xa_node, 0);
1432 }
1433 if (curr)
1434 return curr;
1435 }
1436 xas->xa_offset -= xas->xa_sibs;
1437 return NULL;
1438}
1439EXPORT_SYMBOL_GPL(xas_find_conflict);
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449void *xa_load(struct xarray *xa, unsigned long index)
1450{
1451 XA_STATE(xas, xa, index);
1452 void *entry;
1453
1454 rcu_read_lock();
1455 do {
1456 entry = xas_load(&xas);
1457 if (xa_is_zero(entry))
1458 entry = NULL;
1459 } while (xas_retry(&xas, entry));
1460 rcu_read_unlock();
1461
1462 return entry;
1463}
1464EXPORT_SYMBOL(xa_load);
1465
1466static void *xas_result(struct xa_state *xas, void *curr)
1467{
1468 if (xa_is_zero(curr))
1469 return NULL;
1470 if (xas_error(xas))
1471 curr = xas->xa_node;
1472 return curr;
1473}
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487void *__xa_erase(struct xarray *xa, unsigned long index)
1488{
1489 XA_STATE(xas, xa, index);
1490 return xas_result(&xas, xas_store(&xas, NULL));
1491}
1492EXPORT_SYMBOL(__xa_erase);
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506void *xa_erase(struct xarray *xa, unsigned long index)
1507{
1508 void *entry;
1509
1510 xa_lock(xa);
1511 entry = __xa_erase(xa, index);
1512 xa_unlock(xa);
1513
1514 return entry;
1515}
1516EXPORT_SYMBOL(xa_erase);
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533void *__xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)
1534{
1535 XA_STATE(xas, xa, index);
1536 void *curr;
1537
1538 if (WARN_ON_ONCE(xa_is_advanced(entry)))
1539 return XA_ERROR(-EINVAL);
1540 if (xa_track_free(xa) && !entry)
1541 entry = XA_ZERO_ENTRY;
1542
1543 do {
1544 curr = xas_store(&xas, entry);
1545 if (xa_track_free(xa))
1546 xas_clear_mark(&xas, XA_FREE_MARK);
1547 } while (__xas_nomem(&xas, gfp));
1548
1549 return xas_result(&xas, curr);
1550}
1551EXPORT_SYMBOL(__xa_store);
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570void *xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)
1571{
1572 void *curr;
1573
1574 xa_lock(xa);
1575 curr = __xa_store(xa, index, entry, gfp);
1576 xa_unlock(xa);
1577
1578 return curr;
1579}
1580EXPORT_SYMBOL(xa_store);
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598void *__xa_cmpxchg(struct xarray *xa, unsigned long index,
1599 void *old, void *entry, gfp_t gfp)
1600{
1601 XA_STATE(xas, xa, index);
1602 void *curr;
1603
1604 if (WARN_ON_ONCE(xa_is_advanced(entry)))
1605 return XA_ERROR(-EINVAL);
1606
1607 do {
1608 curr = xas_load(&xas);
1609 if (curr == old) {
1610 xas_store(&xas, entry);
1611 if (xa_track_free(xa) && entry && !curr)
1612 xas_clear_mark(&xas, XA_FREE_MARK);
1613 }
1614 } while (__xas_nomem(&xas, gfp));
1615
1616 return xas_result(&xas, curr);
1617}
1618EXPORT_SYMBOL(__xa_cmpxchg);
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636int __xa_insert(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)
1637{
1638 XA_STATE(xas, xa, index);
1639 void *curr;
1640
1641 if (WARN_ON_ONCE(xa_is_advanced(entry)))
1642 return -EINVAL;
1643 if (!entry)
1644 entry = XA_ZERO_ENTRY;
1645
1646 do {
1647 curr = xas_load(&xas);
1648 if (!curr) {
1649 xas_store(&xas, entry);
1650 if (xa_track_free(xa))
1651 xas_clear_mark(&xas, XA_FREE_MARK);
1652 } else {
1653 xas_set_err(&xas, -EBUSY);
1654 }
1655 } while (__xas_nomem(&xas, gfp));
1656
1657 return xas_error(&xas);
1658}
1659EXPORT_SYMBOL(__xa_insert);
1660
1661#ifdef CONFIG_XARRAY_MULTI
1662static void xas_set_range(struct xa_state *xas, unsigned long first,
1663 unsigned long last)
1664{
1665 unsigned int shift = 0;
1666 unsigned long sibs = last - first;
1667 unsigned int offset = XA_CHUNK_MASK;
1668
1669 xas_set(xas, first);
1670
1671 while ((first & XA_CHUNK_MASK) == 0) {
1672 if (sibs < XA_CHUNK_MASK)
1673 break;
1674 if ((sibs == XA_CHUNK_MASK) && (offset < XA_CHUNK_MASK))
1675 break;
1676 shift += XA_CHUNK_SHIFT;
1677 if (offset == XA_CHUNK_MASK)
1678 offset = sibs & XA_CHUNK_MASK;
1679 sibs >>= XA_CHUNK_SHIFT;
1680 first >>= XA_CHUNK_SHIFT;
1681 }
1682
1683 offset = first & XA_CHUNK_MASK;
1684 if (offset + sibs > XA_CHUNK_MASK)
1685 sibs = XA_CHUNK_MASK - offset;
1686 if ((((first + sibs + 1) << shift) - 1) > last)
1687 sibs -= 1;
1688
1689 xas->xa_shift = shift;
1690 xas->xa_sibs = sibs;
1691}
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711void *xa_store_range(struct xarray *xa, unsigned long first,
1712 unsigned long last, void *entry, gfp_t gfp)
1713{
1714 XA_STATE(xas, xa, 0);
1715
1716 if (WARN_ON_ONCE(xa_is_internal(entry)))
1717 return XA_ERROR(-EINVAL);
1718 if (last < first)
1719 return XA_ERROR(-EINVAL);
1720
1721 do {
1722 xas_lock(&xas);
1723 if (entry) {
1724 unsigned int order = BITS_PER_LONG;
1725 if (last + 1)
1726 order = __ffs(last + 1);
1727 xas_set_order(&xas, last, order);
1728 xas_create(&xas, true);
1729 if (xas_error(&xas))
1730 goto unlock;
1731 }
1732 do {
1733 xas_set_range(&xas, first, last);
1734 xas_store(&xas, entry);
1735 if (xas_error(&xas))
1736 goto unlock;
1737 first += xas_size(&xas);
1738 } while (first <= last);
1739unlock:
1740 xas_unlock(&xas);
1741 } while (xas_nomem(&xas, gfp));
1742
1743 return xas_result(&xas, NULL);
1744}
1745EXPORT_SYMBOL(xa_store_range);
1746
1747
1748
1749
1750
1751
1752
1753
1754int xa_get_order(struct xarray *xa, unsigned long index)
1755{
1756 XA_STATE(xas, xa, index);
1757 void *entry;
1758 int order = 0;
1759
1760 rcu_read_lock();
1761 entry = xas_load(&xas);
1762
1763 if (!entry)
1764 goto unlock;
1765
1766 if (!xas.xa_node)
1767 goto unlock;
1768
1769 for (;;) {
1770 unsigned int slot = xas.xa_offset + (1 << order);
1771
1772 if (slot >= XA_CHUNK_SIZE)
1773 break;
1774 if (!xa_is_sibling(xas.xa_node->slots[slot]))
1775 break;
1776 order++;
1777 }
1778
1779 order += xas.xa_node->shift;
1780unlock:
1781 rcu_read_unlock();
1782
1783 return order;
1784}
1785EXPORT_SYMBOL(xa_get_order);
1786#endif
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805int __xa_alloc(struct xarray *xa, u32 *id, void *entry,
1806 struct xa_limit limit, gfp_t gfp)
1807{
1808 XA_STATE(xas, xa, 0);
1809
1810 if (WARN_ON_ONCE(xa_is_advanced(entry)))
1811 return -EINVAL;
1812 if (WARN_ON_ONCE(!xa_track_free(xa)))
1813 return -EINVAL;
1814
1815 if (!entry)
1816 entry = XA_ZERO_ENTRY;
1817
1818 do {
1819 xas.xa_index = limit.min;
1820 xas_find_marked(&xas, limit.max, XA_FREE_MARK);
1821 if (xas.xa_node == XAS_RESTART)
1822 xas_set_err(&xas, -EBUSY);
1823 else
1824 *id = xas.xa_index;
1825 xas_store(&xas, entry);
1826 xas_clear_mark(&xas, XA_FREE_MARK);
1827 } while (__xas_nomem(&xas, gfp));
1828
1829 return xas_error(&xas);
1830}
1831EXPORT_SYMBOL(__xa_alloc);
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854int __xa_alloc_cyclic(struct xarray *xa, u32 *id, void *entry,
1855 struct xa_limit limit, u32 *next, gfp_t gfp)
1856{
1857 u32 min = limit.min;
1858 int ret;
1859
1860 limit.min = max(min, *next);
1861 ret = __xa_alloc(xa, id, entry, limit, gfp);
1862 if ((xa->xa_flags & XA_FLAGS_ALLOC_WRAPPED) && ret == 0) {
1863 xa->xa_flags &= ~XA_FLAGS_ALLOC_WRAPPED;
1864 ret = 1;
1865 }
1866
1867 if (ret < 0 && limit.min > min) {
1868 limit.min = min;
1869 ret = __xa_alloc(xa, id, entry, limit, gfp);
1870 if (ret == 0)
1871 ret = 1;
1872 }
1873
1874 if (ret >= 0) {
1875 *next = *id + 1;
1876 if (*next == 0)
1877 xa->xa_flags |= XA_FLAGS_ALLOC_WRAPPED;
1878 }
1879 return ret;
1880}
1881EXPORT_SYMBOL(__xa_alloc_cyclic);
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893void __xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
1894{
1895 XA_STATE(xas, xa, index);
1896 void *entry = xas_load(&xas);
1897
1898 if (entry)
1899 xas_set_mark(&xas, mark);
1900}
1901EXPORT_SYMBOL(__xa_set_mark);
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911void __xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
1912{
1913 XA_STATE(xas, xa, index);
1914 void *entry = xas_load(&xas);
1915
1916 if (entry)
1917 xas_clear_mark(&xas, mark);
1918}
1919EXPORT_SYMBOL(__xa_clear_mark);
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933bool xa_get_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
1934{
1935 XA_STATE(xas, xa, index);
1936 void *entry;
1937
1938 rcu_read_lock();
1939 entry = xas_start(&xas);
1940 while (xas_get_mark(&xas, mark)) {
1941 if (!xa_is_node(entry))
1942 goto found;
1943 entry = xas_descend(&xas, xa_to_node(entry));
1944 }
1945 rcu_read_unlock();
1946 return false;
1947 found:
1948 rcu_read_unlock();
1949 return true;
1950}
1951EXPORT_SYMBOL(xa_get_mark);
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963void xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
1964{
1965 xa_lock(xa);
1966 __xa_set_mark(xa, index, mark);
1967 xa_unlock(xa);
1968}
1969EXPORT_SYMBOL(xa_set_mark);
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981void xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
1982{
1983 xa_lock(xa);
1984 __xa_clear_mark(xa, index, mark);
1985 xa_unlock(xa);
1986}
1987EXPORT_SYMBOL(xa_clear_mark);
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006void *xa_find(struct xarray *xa, unsigned long *indexp,
2007 unsigned long max, xa_mark_t filter)
2008{
2009 XA_STATE(xas, xa, *indexp);
2010 void *entry;
2011
2012 rcu_read_lock();
2013 do {
2014 if ((__force unsigned int)filter < XA_MAX_MARKS)
2015 entry = xas_find_marked(&xas, max, filter);
2016 else
2017 entry = xas_find(&xas, max);
2018 } while (xas_retry(&xas, entry));
2019 rcu_read_unlock();
2020
2021 if (entry)
2022 *indexp = xas.xa_index;
2023 return entry;
2024}
2025EXPORT_SYMBOL(xa_find);
2026
2027static bool xas_sibling(struct xa_state *xas)
2028{
2029 struct xa_node *node = xas->xa_node;
2030 unsigned long mask;
2031
2032 if (!IS_ENABLED(CONFIG_XARRAY_MULTI) || !node)
2033 return false;
2034 mask = (XA_CHUNK_SIZE << node->shift) - 1;
2035 return (xas->xa_index & mask) >
2036 ((unsigned long)xas->xa_offset << node->shift);
2037}
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056void *xa_find_after(struct xarray *xa, unsigned long *indexp,
2057 unsigned long max, xa_mark_t filter)
2058{
2059 XA_STATE(xas, xa, *indexp + 1);
2060 void *entry;
2061
2062 if (xas.xa_index == 0)
2063 return NULL;
2064
2065 rcu_read_lock();
2066 for (;;) {
2067 if ((__force unsigned int)filter < XA_MAX_MARKS)
2068 entry = xas_find_marked(&xas, max, filter);
2069 else
2070 entry = xas_find(&xas, max);
2071
2072 if (xas_invalid(&xas))
2073 break;
2074 if (xas_sibling(&xas))
2075 continue;
2076 if (!xas_retry(&xas, entry))
2077 break;
2078 }
2079 rcu_read_unlock();
2080
2081 if (entry)
2082 *indexp = xas.xa_index;
2083 return entry;
2084}
2085EXPORT_SYMBOL(xa_find_after);
2086
2087static unsigned int xas_extract_present(struct xa_state *xas, void **dst,
2088 unsigned long max, unsigned int n)
2089{
2090 void *entry;
2091 unsigned int i = 0;
2092
2093 rcu_read_lock();
2094 xas_for_each(xas, entry, max) {
2095 if (xas_retry(xas, entry))
2096 continue;
2097 dst[i++] = entry;
2098 if (i == n)
2099 break;
2100 }
2101 rcu_read_unlock();
2102
2103 return i;
2104}
2105
2106static unsigned int xas_extract_marked(struct xa_state *xas, void **dst,
2107 unsigned long max, unsigned int n, xa_mark_t mark)
2108{
2109 void *entry;
2110 unsigned int i = 0;
2111
2112 rcu_read_lock();
2113 xas_for_each_marked(xas, entry, max, mark) {
2114 if (xas_retry(xas, entry))
2115 continue;
2116 dst[i++] = entry;
2117 if (i == n)
2118 break;
2119 }
2120 rcu_read_unlock();
2121
2122 return i;
2123}
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153unsigned int xa_extract(struct xarray *xa, void **dst, unsigned long start,
2154 unsigned long max, unsigned int n, xa_mark_t filter)
2155{
2156 XA_STATE(xas, xa, start);
2157
2158 if (!n)
2159 return 0;
2160
2161 if ((__force unsigned int)filter < XA_MAX_MARKS)
2162 return xas_extract_marked(&xas, dst, max, n, filter);
2163 return xas_extract_present(&xas, dst, max, n);
2164}
2165EXPORT_SYMBOL(xa_extract);
2166
2167
2168
2169
2170
2171
2172
2173
2174void xa_delete_node(struct xa_node *node, xa_update_node_t update)
2175{
2176 struct xa_state xas = {
2177 .xa = node->array,
2178 .xa_index = (unsigned long)node->offset <<
2179 (node->shift + XA_CHUNK_SHIFT),
2180 .xa_shift = node->shift + XA_CHUNK_SHIFT,
2181 .xa_offset = node->offset,
2182 .xa_node = xa_parent_locked(node->array, node),
2183 .xa_update = update,
2184 };
2185
2186 xas_store(&xas, NULL);
2187}
2188EXPORT_SYMBOL_GPL(xa_delete_node);
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200void xa_destroy(struct xarray *xa)
2201{
2202 XA_STATE(xas, xa, 0);
2203 unsigned long flags;
2204 void *entry;
2205
2206 xas.xa_node = NULL;
2207 xas_lock_irqsave(&xas, flags);
2208 entry = xa_head_locked(xa);
2209 RCU_INIT_POINTER(xa->xa_head, NULL);
2210 xas_init_marks(&xas);
2211 if (xa_zero_busy(xa))
2212 xa_mark_clear(xa, XA_FREE_MARK);
2213
2214 if (xa_is_node(entry))
2215 xas_free_nodes(&xas, xa_to_node(entry));
2216 xas_unlock_irqrestore(&xas, flags);
2217}
2218EXPORT_SYMBOL(xa_destroy);
2219
2220#ifdef XA_DEBUG
2221void xa_dump_node(const struct xa_node *node)
2222{
2223 unsigned i, j;
2224
2225 if (!node)
2226 return;
2227 if ((unsigned long)node & 3) {
2228 pr_cont("node %px\n", node);
2229 return;
2230 }
2231
2232 pr_cont("node %px %s %d parent %px shift %d count %d values %d "
2233 "array %px list %px %px marks",
2234 node, node->parent ? "offset" : "max", node->offset,
2235 node->parent, node->shift, node->count, node->nr_values,
2236 node->array, node->private_list.prev, node->private_list.next);
2237 for (i = 0; i < XA_MAX_MARKS; i++)
2238 for (j = 0; j < XA_MARK_LONGS; j++)
2239 pr_cont(" %lx", node->marks[i][j]);
2240 pr_cont("\n");
2241}
2242
2243void xa_dump_index(unsigned long index, unsigned int shift)
2244{
2245 if (!shift)
2246 pr_info("%lu: ", index);
2247 else if (shift >= BITS_PER_LONG)
2248 pr_info("0-%lu: ", ~0UL);
2249 else
2250 pr_info("%lu-%lu: ", index, index | ((1UL << shift) - 1));
2251}
2252
2253void xa_dump_entry(const void *entry, unsigned long index, unsigned long shift)
2254{
2255 if (!entry)
2256 return;
2257
2258 xa_dump_index(index, shift);
2259
2260 if (xa_is_node(entry)) {
2261 if (shift == 0) {
2262 pr_cont("%px\n", entry);
2263 } else {
2264 unsigned long i;
2265 struct xa_node *node = xa_to_node(entry);
2266 xa_dump_node(node);
2267 for (i = 0; i < XA_CHUNK_SIZE; i++)
2268 xa_dump_entry(node->slots[i],
2269 index + (i << node->shift), node->shift);
2270 }
2271 } else if (xa_is_value(entry))
2272 pr_cont("value %ld (0x%lx) [%px]\n", xa_to_value(entry),
2273 xa_to_value(entry), entry);
2274 else if (!xa_is_internal(entry))
2275 pr_cont("%px\n", entry);
2276 else if (xa_is_retry(entry))
2277 pr_cont("retry (%ld)\n", xa_to_internal(entry));
2278 else if (xa_is_sibling(entry))
2279 pr_cont("sibling (slot %ld)\n", xa_to_sibling(entry));
2280 else if (xa_is_zero(entry))
2281 pr_cont("zero (%ld)\n", xa_to_internal(entry));
2282 else
2283 pr_cont("UNKNOWN ENTRY (%px)\n", entry);
2284}
2285
2286void xa_dump(const struct xarray *xa)
2287{
2288 void *entry = xa->xa_head;
2289 unsigned int shift = 0;
2290
2291 pr_info("xarray: %px head %px flags %x marks %d %d %d\n", xa, entry,
2292 xa->xa_flags, xa_marked(xa, XA_MARK_0),
2293 xa_marked(xa, XA_MARK_1), xa_marked(xa, XA_MARK_2));
2294 if (xa_is_node(entry))
2295 shift = xa_to_node(entry)->shift + XA_CHUNK_SHIFT;
2296 xa_dump_entry(entry, 0, shift);
2297}
2298#endif
2299