Merge branch 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/hid/hid
[linux-2.6-microblaze.git] / lib / xarray.c
1 // SPDX-License-Identifier: GPL-2.0+
2 /*
3  * XArray implementation
4  * Copyright (c) 2017 Microsoft Corporation
5  * Author: Matthew Wilcox <willy@infradead.org>
6  */
7
8 #include <linux/bitmap.h>
9 #include <linux/export.h>
10 #include <linux/list.h>
11 #include <linux/slab.h>
12 #include <linux/xarray.h>
13
14 /*
15  * Coding conventions in this file:
16  *
17  * @xa is used to refer to the entire xarray.
18  * @xas is the 'xarray operation state'.  It may be either a pointer to
19  * an xa_state, or an xa_state stored on the stack.  This is an unfortunate
20  * ambiguity.
21  * @index is the index of the entry being operated on
22  * @mark is an xa_mark_t; a small number indicating one of the mark bits.
23  * @node refers to an xa_node; usually the primary one being operated on by
24  * this function.
25  * @offset is the index into the slots array inside an xa_node.
26  * @parent refers to the @xa_node closer to the head than @node.
27  * @entry refers to something stored in a slot in the xarray
28  */
29
30 static inline unsigned int xa_lock_type(const struct xarray *xa)
31 {
32         return (__force unsigned int)xa->xa_flags & 3;
33 }
34
35 static inline void xas_lock_type(struct xa_state *xas, unsigned int lock_type)
36 {
37         if (lock_type == XA_LOCK_IRQ)
38                 xas_lock_irq(xas);
39         else if (lock_type == XA_LOCK_BH)
40                 xas_lock_bh(xas);
41         else
42                 xas_lock(xas);
43 }
44
45 static inline void xas_unlock_type(struct xa_state *xas, unsigned int lock_type)
46 {
47         if (lock_type == XA_LOCK_IRQ)
48                 xas_unlock_irq(xas);
49         else if (lock_type == XA_LOCK_BH)
50                 xas_unlock_bh(xas);
51         else
52                 xas_unlock(xas);
53 }
54
55 static inline bool xa_track_free(const struct xarray *xa)
56 {
57         return xa->xa_flags & XA_FLAGS_TRACK_FREE;
58 }
59
60 static inline void xa_mark_set(struct xarray *xa, xa_mark_t mark)
61 {
62         if (!(xa->xa_flags & XA_FLAGS_MARK(mark)))
63                 xa->xa_flags |= XA_FLAGS_MARK(mark);
64 }
65
66 static inline void xa_mark_clear(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
72 static inline unsigned long *node_marks(struct xa_node *node, xa_mark_t mark)
73 {
74         return node->marks[(__force unsigned)mark];
75 }
76
77 static inline bool node_get_mark(struct xa_node *node,
78                 unsigned int offset, xa_mark_t mark)
79 {
80         return test_bit(offset, node_marks(node, mark));
81 }
82
83 /* returns true if the bit was set */
84 static inline bool node_set_mark(struct xa_node *node, unsigned int offset,
85                                 xa_mark_t mark)
86 {
87         return __test_and_set_bit(offset, node_marks(node, mark));
88 }
89
90 /* returns true if the bit was set */
91 static inline bool node_clear_mark(struct xa_node *node, unsigned int offset,
92                                 xa_mark_t mark)
93 {
94         return __test_and_clear_bit(offset, node_marks(node, mark));
95 }
96
97 static inline bool node_any_mark(struct xa_node *node, xa_mark_t mark)
98 {
99         return !bitmap_empty(node_marks(node, mark), XA_CHUNK_SIZE);
100 }
101
102 static inline void node_mark_all(struct xa_node *node, xa_mark_t mark)
103 {
104         bitmap_fill(node_marks(node, mark), XA_CHUNK_SIZE);
105 }
106
107 #define mark_inc(mark) do { \
108         mark = (__force xa_mark_t)((__force unsigned)(mark) + 1); \
109 } while (0)
110
111 /*
112  * xas_squash_marks() - Merge all marks to the first entry
113  * @xas: Array operation state.
114  *
115  * Set a mark on the first entry if any entry has it set.  Clear marks on
116  * all sibling entries.
117  */
118 static void xas_squash_marks(const struct xa_state *xas)
119 {
120         unsigned int mark = 0;
121         unsigned int limit = xas->xa_offset + xas->xa_sibs + 1;
122
123         if (!xas->xa_sibs)
124                 return;
125
126         do {
127                 unsigned long *marks = xas->xa_node->marks[mark];
128                 if (find_next_bit(marks, limit, xas->xa_offset + 1) == limit)
129                         continue;
130                 __set_bit(xas->xa_offset, marks);
131                 bitmap_clear(marks, xas->xa_offset + 1, xas->xa_sibs);
132         } while (mark++ != (__force unsigned)XA_MARK_MAX);
133 }
134
135 /* extracts the offset within this node from the index */
136 static unsigned int get_offset(unsigned long index, struct xa_node *node)
137 {
138         return (index >> node->shift) & XA_CHUNK_MASK;
139 }
140
141 static void xas_set_offset(struct xa_state *xas)
142 {
143         xas->xa_offset = get_offset(xas->xa_index, xas->xa_node);
144 }
145
146 /* move the index either forwards (find) or backwards (sibling slot) */
147 static void xas_move_index(struct xa_state *xas, unsigned long offset)
148 {
149         unsigned int shift = xas->xa_node->shift;
150         xas->xa_index &= ~XA_CHUNK_MASK << shift;
151         xas->xa_index += offset << shift;
152 }
153
154 static void xas_advance(struct xa_state *xas)
155 {
156         xas->xa_offset++;
157         xas_move_index(xas, xas->xa_offset);
158 }
159
160 static void *set_bounds(struct xa_state *xas)
161 {
162         xas->xa_node = XAS_BOUNDS;
163         return NULL;
164 }
165
166 /*
167  * Starts a walk.  If the @xas is already valid, we assume that it's on
168  * the right path and just return where we've got to.  If we're in an
169  * error state, return NULL.  If the index is outside the current scope
170  * of the xarray, return NULL without changing @xas->xa_node.  Otherwise
171  * set @xas->xa_node to NULL and return the current head of the array.
172  */
173 static void *xas_start(struct xa_state *xas)
174 {
175         void *entry;
176
177         if (xas_valid(xas))
178                 return xas_reload(xas);
179         if (xas_error(xas))
180                 return NULL;
181
182         entry = xa_head(xas->xa);
183         if (!xa_is_node(entry)) {
184                 if (xas->xa_index)
185                         return set_bounds(xas);
186         } else {
187                 if ((xas->xa_index >> xa_to_node(entry)->shift) > XA_CHUNK_MASK)
188                         return set_bounds(xas);
189         }
190
191         xas->xa_node = NULL;
192         return entry;
193 }
194
195 static void *xas_descend(struct xa_state *xas, struct xa_node *node)
196 {
197         unsigned int offset = get_offset(xas->xa_index, node);
198         void *entry = xa_entry(xas->xa, node, offset);
199
200         xas->xa_node = node;
201         if (xa_is_sibling(entry)) {
202                 offset = xa_to_sibling(entry);
203                 entry = xa_entry(xas->xa, node, offset);
204         }
205
206         xas->xa_offset = offset;
207         return entry;
208 }
209
210 /**
211  * xas_load() - Load an entry from the XArray (advanced).
212  * @xas: XArray operation state.
213  *
214  * Usually walks the @xas to the appropriate state to load the entry
215  * stored at xa_index.  However, it will do nothing and return %NULL if
216  * @xas is in an error state.  xas_load() will never expand the tree.
217  *
218  * If the xa_state is set up to operate on a multi-index entry, xas_load()
219  * may return %NULL or an internal entry, even if there are entries
220  * present within the range specified by @xas.
221  *
222  * Context: Any context.  The caller should hold the xa_lock or the RCU lock.
223  * Return: Usually an entry in the XArray, but see description for exceptions.
224  */
225 void *xas_load(struct xa_state *xas)
226 {
227         void *entry = xas_start(xas);
228
229         while (xa_is_node(entry)) {
230                 struct xa_node *node = xa_to_node(entry);
231
232                 if (xas->xa_shift > node->shift)
233                         break;
234                 entry = xas_descend(xas, node);
235                 if (node->shift == 0)
236                         break;
237         }
238         return entry;
239 }
240 EXPORT_SYMBOL_GPL(xas_load);
241
242 /* Move the radix tree node cache here */
243 extern struct kmem_cache *radix_tree_node_cachep;
244 extern void radix_tree_node_rcu_free(struct rcu_head *head);
245
246 #define XA_RCU_FREE     ((struct xarray *)1)
247
248 static void xa_node_free(struct xa_node *node)
249 {
250         XA_NODE_BUG_ON(node, !list_empty(&node->private_list));
251         node->array = XA_RCU_FREE;
252         call_rcu(&node->rcu_head, radix_tree_node_rcu_free);
253 }
254
255 /*
256  * xas_destroy() - Free any resources allocated during the XArray operation.
257  * @xas: XArray operation state.
258  *
259  * This function is now internal-only.
260  */
261 static void xas_destroy(struct xa_state *xas)
262 {
263         struct xa_node *node = xas->xa_alloc;
264
265         if (!node)
266                 return;
267         XA_NODE_BUG_ON(node, !list_empty(&node->private_list));
268         kmem_cache_free(radix_tree_node_cachep, node);
269         xas->xa_alloc = NULL;
270 }
271
272 /**
273  * xas_nomem() - Allocate memory if needed.
274  * @xas: XArray operation state.
275  * @gfp: Memory allocation flags.
276  *
277  * If we need to add new nodes to the XArray, we try to allocate memory
278  * with GFP_NOWAIT while holding the lock, which will usually succeed.
279  * If it fails, @xas is flagged as needing memory to continue.  The caller
280  * should drop the lock and call xas_nomem().  If xas_nomem() succeeds,
281  * the caller should retry the operation.
282  *
283  * Forward progress is guaranteed as one node is allocated here and
284  * stored in the xa_state where it will be found by xas_alloc().  More
285  * nodes will likely be found in the slab allocator, but we do not tie
286  * them up here.
287  *
288  * Return: true if memory was needed, and was successfully allocated.
289  */
290 bool xas_nomem(struct xa_state *xas, gfp_t gfp)
291 {
292         if (xas->xa_node != XA_ERROR(-ENOMEM)) {
293                 xas_destroy(xas);
294                 return false;
295         }
296         xas->xa_alloc = kmem_cache_alloc(radix_tree_node_cachep, gfp);
297         if (!xas->xa_alloc)
298                 return false;
299         XA_NODE_BUG_ON(xas->xa_alloc, !list_empty(&xas->xa_alloc->private_list));
300         xas->xa_node = XAS_RESTART;
301         return true;
302 }
303 EXPORT_SYMBOL_GPL(xas_nomem);
304
305 /*
306  * __xas_nomem() - Drop locks and allocate memory if needed.
307  * @xas: XArray operation state.
308  * @gfp: Memory allocation flags.
309  *
310  * Internal variant of xas_nomem().
311  *
312  * Return: true if memory was needed, and was successfully allocated.
313  */
314 static bool __xas_nomem(struct xa_state *xas, gfp_t gfp)
315         __must_hold(xas->xa->xa_lock)
316 {
317         unsigned int lock_type = xa_lock_type(xas->xa);
318
319         if (xas->xa_node != XA_ERROR(-ENOMEM)) {
320                 xas_destroy(xas);
321                 return false;
322         }
323         if (gfpflags_allow_blocking(gfp)) {
324                 xas_unlock_type(xas, lock_type);
325                 xas->xa_alloc = kmem_cache_alloc(radix_tree_node_cachep, gfp);
326                 xas_lock_type(xas, lock_type);
327         } else {
328                 xas->xa_alloc = kmem_cache_alloc(radix_tree_node_cachep, gfp);
329         }
330         if (!xas->xa_alloc)
331                 return false;
332         XA_NODE_BUG_ON(xas->xa_alloc, !list_empty(&xas->xa_alloc->private_list));
333         xas->xa_node = XAS_RESTART;
334         return true;
335 }
336
337 static void xas_update(struct xa_state *xas, struct xa_node *node)
338 {
339         if (xas->xa_update)
340                 xas->xa_update(node);
341         else
342                 XA_NODE_BUG_ON(node, !list_empty(&node->private_list));
343 }
344
345 static void *xas_alloc(struct xa_state *xas, unsigned int shift)
346 {
347         struct xa_node *parent = xas->xa_node;
348         struct xa_node *node = xas->xa_alloc;
349
350         if (xas_invalid(xas))
351                 return NULL;
352
353         if (node) {
354                 xas->xa_alloc = NULL;
355         } else {
356                 node = kmem_cache_alloc(radix_tree_node_cachep,
357                                         GFP_NOWAIT | __GFP_NOWARN);
358                 if (!node) {
359                         xas_set_err(xas, -ENOMEM);
360                         return NULL;
361                 }
362         }
363
364         if (parent) {
365                 node->offset = xas->xa_offset;
366                 parent->count++;
367                 XA_NODE_BUG_ON(node, parent->count > XA_CHUNK_SIZE);
368                 xas_update(xas, parent);
369         }
370         XA_NODE_BUG_ON(node, shift > BITS_PER_LONG);
371         XA_NODE_BUG_ON(node, !list_empty(&node->private_list));
372         node->shift = shift;
373         node->count = 0;
374         node->nr_values = 0;
375         RCU_INIT_POINTER(node->parent, xas->xa_node);
376         node->array = xas->xa;
377
378         return node;
379 }
380
381 #ifdef CONFIG_XARRAY_MULTI
382 /* Returns the number of indices covered by a given xa_state */
383 static unsigned long xas_size(const struct xa_state *xas)
384 {
385         return (xas->xa_sibs + 1UL) << xas->xa_shift;
386 }
387 #endif
388
389 /*
390  * Use this to calculate the maximum index that will need to be created
391  * in order to add the entry described by @xas.  Because we cannot store a
392  * multiple-index entry at index 0, the calculation is a little more complex
393  * than you might expect.
394  */
395 static unsigned long xas_max(struct xa_state *xas)
396 {
397         unsigned long max = xas->xa_index;
398
399 #ifdef CONFIG_XARRAY_MULTI
400         if (xas->xa_shift || xas->xa_sibs) {
401                 unsigned long mask = xas_size(xas) - 1;
402                 max |= mask;
403                 if (mask == max)
404                         max++;
405         }
406 #endif
407
408         return max;
409 }
410
411 /* The maximum index that can be contained in the array without expanding it */
412 static unsigned long max_index(void *entry)
413 {
414         if (!xa_is_node(entry))
415                 return 0;
416         return (XA_CHUNK_SIZE << xa_to_node(entry)->shift) - 1;
417 }
418
419 static void xas_shrink(struct xa_state *xas)
420 {
421         struct xarray *xa = xas->xa;
422         struct xa_node *node = xas->xa_node;
423
424         for (;;) {
425                 void *entry;
426
427                 XA_NODE_BUG_ON(node, node->count > XA_CHUNK_SIZE);
428                 if (node->count != 1)
429                         break;
430                 entry = xa_entry_locked(xa, node, 0);
431                 if (!entry)
432                         break;
433                 if (!xa_is_node(entry) && node->shift)
434                         break;
435                 xas->xa_node = XAS_BOUNDS;
436
437                 RCU_INIT_POINTER(xa->xa_head, entry);
438                 if (xa_track_free(xa) && !node_get_mark(node, 0, XA_FREE_MARK))
439                         xa_mark_clear(xa, XA_FREE_MARK);
440
441                 node->count = 0;
442                 node->nr_values = 0;
443                 if (!xa_is_node(entry))
444                         RCU_INIT_POINTER(node->slots[0], XA_RETRY_ENTRY);
445                 xas_update(xas, node);
446                 xa_node_free(node);
447                 if (!xa_is_node(entry))
448                         break;
449                 node = xa_to_node(entry);
450                 node->parent = NULL;
451         }
452 }
453
454 /*
455  * xas_delete_node() - Attempt to delete an xa_node
456  * @xas: Array operation state.
457  *
458  * Attempts to delete the @xas->xa_node.  This will fail if xa->node has
459  * a non-zero reference count.
460  */
461 static void xas_delete_node(struct xa_state *xas)
462 {
463         struct xa_node *node = xas->xa_node;
464
465         for (;;) {
466                 struct xa_node *parent;
467
468                 XA_NODE_BUG_ON(node, node->count > XA_CHUNK_SIZE);
469                 if (node->count)
470                         break;
471
472                 parent = xa_parent_locked(xas->xa, node);
473                 xas->xa_node = parent;
474                 xas->xa_offset = node->offset;
475                 xa_node_free(node);
476
477                 if (!parent) {
478                         xas->xa->xa_head = NULL;
479                         xas->xa_node = XAS_BOUNDS;
480                         return;
481                 }
482
483                 parent->slots[xas->xa_offset] = NULL;
484                 parent->count--;
485                 XA_NODE_BUG_ON(parent, parent->count > XA_CHUNK_SIZE);
486                 node = parent;
487                 xas_update(xas, node);
488         }
489
490         if (!node->parent)
491                 xas_shrink(xas);
492 }
493
494 /**
495  * xas_free_nodes() - Free this node and all nodes that it references
496  * @xas: Array operation state.
497  * @top: Node to free
498  *
499  * This node has been removed from the tree.  We must now free it and all
500  * of its subnodes.  There may be RCU walkers with references into the tree,
501  * so we must replace all entries with retry markers.
502  */
503 static void xas_free_nodes(struct xa_state *xas, struct xa_node *top)
504 {
505         unsigned int offset = 0;
506         struct xa_node *node = top;
507
508         for (;;) {
509                 void *entry = xa_entry_locked(xas->xa, node, offset);
510
511                 if (node->shift && xa_is_node(entry)) {
512                         node = xa_to_node(entry);
513                         offset = 0;
514                         continue;
515                 }
516                 if (entry)
517                         RCU_INIT_POINTER(node->slots[offset], XA_RETRY_ENTRY);
518                 offset++;
519                 while (offset == XA_CHUNK_SIZE) {
520                         struct xa_node *parent;
521
522                         parent = xa_parent_locked(xas->xa, node);
523                         offset = node->offset + 1;
524                         node->count = 0;
525                         node->nr_values = 0;
526                         xas_update(xas, node);
527                         xa_node_free(node);
528                         if (node == top)
529                                 return;
530                         node = parent;
531                 }
532         }
533 }
534
535 /*
536  * xas_expand adds nodes to the head of the tree until it has reached
537  * sufficient height to be able to contain @xas->xa_index
538  */
539 static int xas_expand(struct xa_state *xas, void *head)
540 {
541         struct xarray *xa = xas->xa;
542         struct xa_node *node = NULL;
543         unsigned int shift = 0;
544         unsigned long max = xas_max(xas);
545
546         if (!head) {
547                 if (max == 0)
548                         return 0;
549                 while ((max >> shift) >= XA_CHUNK_SIZE)
550                         shift += XA_CHUNK_SHIFT;
551                 return shift + XA_CHUNK_SHIFT;
552         } else if (xa_is_node(head)) {
553                 node = xa_to_node(head);
554                 shift = node->shift + XA_CHUNK_SHIFT;
555         }
556         xas->xa_node = NULL;
557
558         while (max > max_index(head)) {
559                 xa_mark_t mark = 0;
560
561                 XA_NODE_BUG_ON(node, shift > BITS_PER_LONG);
562                 node = xas_alloc(xas, shift);
563                 if (!node)
564                         return -ENOMEM;
565
566                 node->count = 1;
567                 if (xa_is_value(head))
568                         node->nr_values = 1;
569                 RCU_INIT_POINTER(node->slots[0], head);
570
571                 /* Propagate the aggregated mark info to the new child */
572                 for (;;) {
573                         if (xa_track_free(xa) && mark == XA_FREE_MARK) {
574                                 node_mark_all(node, XA_FREE_MARK);
575                                 if (!xa_marked(xa, XA_FREE_MARK)) {
576                                         node_clear_mark(node, 0, XA_FREE_MARK);
577                                         xa_mark_set(xa, XA_FREE_MARK);
578                                 }
579                         } else if (xa_marked(xa, mark)) {
580                                 node_set_mark(node, 0, mark);
581                         }
582                         if (mark == XA_MARK_MAX)
583                                 break;
584                         mark_inc(mark);
585                 }
586
587                 /*
588                  * Now that the new node is fully initialised, we can add
589                  * it to the tree
590                  */
591                 if (xa_is_node(head)) {
592                         xa_to_node(head)->offset = 0;
593                         rcu_assign_pointer(xa_to_node(head)->parent, node);
594                 }
595                 head = xa_mk_node(node);
596                 rcu_assign_pointer(xa->xa_head, head);
597                 xas_update(xas, node);
598
599                 shift += XA_CHUNK_SHIFT;
600         }
601
602         xas->xa_node = node;
603         return shift;
604 }
605
606 /*
607  * xas_create() - Create a slot to store an entry in.
608  * @xas: XArray operation state.
609  * @allow_root: %true if we can store the entry in the root directly
610  *
611  * Most users will not need to call this function directly, as it is called
612  * by xas_store().  It is useful for doing conditional store operations
613  * (see the xa_cmpxchg() implementation for an example).
614  *
615  * Return: If the slot already existed, returns the contents of this slot.
616  * If the slot was newly created, returns %NULL.  If it failed to create the
617  * slot, returns %NULL and indicates the error in @xas.
618  */
619 static void *xas_create(struct xa_state *xas, bool allow_root)
620 {
621         struct xarray *xa = xas->xa;
622         void *entry;
623         void __rcu **slot;
624         struct xa_node *node = xas->xa_node;
625         int shift;
626         unsigned int order = xas->xa_shift;
627
628         if (xas_top(node)) {
629                 entry = xa_head_locked(xa);
630                 xas->xa_node = NULL;
631                 shift = xas_expand(xas, entry);
632                 if (shift < 0)
633                         return NULL;
634                 if (!shift && !allow_root)
635                         shift = XA_CHUNK_SHIFT;
636                 entry = xa_head_locked(xa);
637                 slot = &xa->xa_head;
638         } else if (xas_error(xas)) {
639                 return NULL;
640         } else if (node) {
641                 unsigned int offset = xas->xa_offset;
642
643                 shift = node->shift;
644                 entry = xa_entry_locked(xa, node, offset);
645                 slot = &node->slots[offset];
646         } else {
647                 shift = 0;
648                 entry = xa_head_locked(xa);
649                 slot = &xa->xa_head;
650         }
651
652         while (shift > order) {
653                 shift -= XA_CHUNK_SHIFT;
654                 if (!entry) {
655                         node = xas_alloc(xas, shift);
656                         if (!node)
657                                 break;
658                         if (xa_track_free(xa))
659                                 node_mark_all(node, XA_FREE_MARK);
660                         rcu_assign_pointer(*slot, xa_mk_node(node));
661                 } else if (xa_is_node(entry)) {
662                         node = xa_to_node(entry);
663                 } else {
664                         break;
665                 }
666                 entry = xas_descend(xas, node);
667                 slot = &node->slots[xas->xa_offset];
668         }
669
670         return entry;
671 }
672
673 /**
674  * xas_create_range() - Ensure that stores to this range will succeed
675  * @xas: XArray operation state.
676  *
677  * Creates all of the slots in the range covered by @xas.  Sets @xas to
678  * create single-index entries and positions it at the beginning of the
679  * range.  This is for the benefit of users which have not yet been
680  * converted to use multi-index entries.
681  */
682 void xas_create_range(struct xa_state *xas)
683 {
684         unsigned long index = xas->xa_index;
685         unsigned char shift = xas->xa_shift;
686         unsigned char sibs = xas->xa_sibs;
687
688         xas->xa_index |= ((sibs + 1) << shift) - 1;
689         if (xas_is_node(xas) && xas->xa_node->shift == xas->xa_shift)
690                 xas->xa_offset |= sibs;
691         xas->xa_shift = 0;
692         xas->xa_sibs = 0;
693
694         for (;;) {
695                 xas_create(xas, true);
696                 if (xas_error(xas))
697                         goto restore;
698                 if (xas->xa_index <= (index | XA_CHUNK_MASK))
699                         goto success;
700                 xas->xa_index -= XA_CHUNK_SIZE;
701
702                 for (;;) {
703                         struct xa_node *node = xas->xa_node;
704                         xas->xa_node = xa_parent_locked(xas->xa, node);
705                         xas->xa_offset = node->offset - 1;
706                         if (node->offset != 0)
707                                 break;
708                 }
709         }
710
711 restore:
712         xas->xa_shift = shift;
713         xas->xa_sibs = sibs;
714         xas->xa_index = index;
715         return;
716 success:
717         xas->xa_index = index;
718         if (xas->xa_node)
719                 xas_set_offset(xas);
720 }
721 EXPORT_SYMBOL_GPL(xas_create_range);
722
723 static void update_node(struct xa_state *xas, struct xa_node *node,
724                 int count, int values)
725 {
726         if (!node || (!count && !values))
727                 return;
728
729         node->count += count;
730         node->nr_values += values;
731         XA_NODE_BUG_ON(node, node->count > XA_CHUNK_SIZE);
732         XA_NODE_BUG_ON(node, node->nr_values > XA_CHUNK_SIZE);
733         xas_update(xas, node);
734         if (count < 0)
735                 xas_delete_node(xas);
736 }
737
738 /**
739  * xas_store() - Store this entry in the XArray.
740  * @xas: XArray operation state.
741  * @entry: New entry.
742  *
743  * If @xas is operating on a multi-index entry, the entry returned by this
744  * function is essentially meaningless (it may be an internal entry or it
745  * may be %NULL, even if there are non-NULL entries at some of the indices
746  * covered by the range).  This is not a problem for any current users,
747  * and can be changed if needed.
748  *
749  * Return: The old entry at this index.
750  */
751 void *xas_store(struct xa_state *xas, void *entry)
752 {
753         struct xa_node *node;
754         void __rcu **slot = &xas->xa->xa_head;
755         unsigned int offset, max;
756         int count = 0;
757         int values = 0;
758         void *first, *next;
759         bool value = xa_is_value(entry);
760
761         if (entry)
762                 first = xas_create(xas, !xa_is_node(entry));
763         else
764                 first = xas_load(xas);
765
766         if (xas_invalid(xas))
767                 return first;
768         node = xas->xa_node;
769         if (node && (xas->xa_shift < node->shift))
770                 xas->xa_sibs = 0;
771         if ((first == entry) && !xas->xa_sibs)
772                 return first;
773
774         next = first;
775         offset = xas->xa_offset;
776         max = xas->xa_offset + xas->xa_sibs;
777         if (node) {
778                 slot = &node->slots[offset];
779                 if (xas->xa_sibs)
780                         xas_squash_marks(xas);
781         }
782         if (!entry)
783                 xas_init_marks(xas);
784
785         for (;;) {
786                 /*
787                  * Must clear the marks before setting the entry to NULL,
788                  * otherwise xas_for_each_marked may find a NULL entry and
789                  * stop early.  rcu_assign_pointer contains a release barrier
790                  * so the mark clearing will appear to happen before the
791                  * entry is set to NULL.
792                  */
793                 rcu_assign_pointer(*slot, entry);
794                 if (xa_is_node(next))
795                         xas_free_nodes(xas, xa_to_node(next));
796                 if (!node)
797                         break;
798                 count += !next - !entry;
799                 values += !xa_is_value(first) - !value;
800                 if (entry) {
801                         if (offset == max)
802                                 break;
803                         if (!xa_is_sibling(entry))
804                                 entry = xa_mk_sibling(xas->xa_offset);
805                 } else {
806                         if (offset == XA_CHUNK_MASK)
807                                 break;
808                 }
809                 next = xa_entry_locked(xas->xa, node, ++offset);
810                 if (!xa_is_sibling(next)) {
811                         if (!entry && (offset > max))
812                                 break;
813                         first = next;
814                 }
815                 slot++;
816         }
817
818         update_node(xas, node, count, values);
819         return first;
820 }
821 EXPORT_SYMBOL_GPL(xas_store);
822
823 /**
824  * xas_get_mark() - Returns the state of this mark.
825  * @xas: XArray operation state.
826  * @mark: Mark number.
827  *
828  * Return: true if the mark is set, false if the mark is clear or @xas
829  * is in an error state.
830  */
831 bool xas_get_mark(const struct xa_state *xas, xa_mark_t mark)
832 {
833         if (xas_invalid(xas))
834                 return false;
835         if (!xas->xa_node)
836                 return xa_marked(xas->xa, mark);
837         return node_get_mark(xas->xa_node, xas->xa_offset, mark);
838 }
839 EXPORT_SYMBOL_GPL(xas_get_mark);
840
841 /**
842  * xas_set_mark() - Sets the mark on this entry and its parents.
843  * @xas: XArray operation state.
844  * @mark: Mark number.
845  *
846  * Sets the specified mark on this entry, and walks up the tree setting it
847  * on all the ancestor entries.  Does nothing if @xas has not been walked to
848  * an entry, or is in an error state.
849  */
850 void xas_set_mark(const struct xa_state *xas, xa_mark_t mark)
851 {
852         struct xa_node *node = xas->xa_node;
853         unsigned int offset = xas->xa_offset;
854
855         if (xas_invalid(xas))
856                 return;
857
858         while (node) {
859                 if (node_set_mark(node, offset, mark))
860                         return;
861                 offset = node->offset;
862                 node = xa_parent_locked(xas->xa, node);
863         }
864
865         if (!xa_marked(xas->xa, mark))
866                 xa_mark_set(xas->xa, mark);
867 }
868 EXPORT_SYMBOL_GPL(xas_set_mark);
869
870 /**
871  * xas_clear_mark() - Clears the mark on this entry and its parents.
872  * @xas: XArray operation state.
873  * @mark: Mark number.
874  *
875  * Clears the specified mark on this entry, and walks back to the head
876  * attempting to clear it on all the ancestor entries.  Does nothing if
877  * @xas has not been walked to an entry, or is in an error state.
878  */
879 void xas_clear_mark(const struct xa_state *xas, xa_mark_t mark)
880 {
881         struct xa_node *node = xas->xa_node;
882         unsigned int offset = xas->xa_offset;
883
884         if (xas_invalid(xas))
885                 return;
886
887         while (node) {
888                 if (!node_clear_mark(node, offset, mark))
889                         return;
890                 if (node_any_mark(node, mark))
891                         return;
892
893                 offset = node->offset;
894                 node = xa_parent_locked(xas->xa, node);
895         }
896
897         if (xa_marked(xas->xa, mark))
898                 xa_mark_clear(xas->xa, mark);
899 }
900 EXPORT_SYMBOL_GPL(xas_clear_mark);
901
902 /**
903  * xas_init_marks() - Initialise all marks for the entry
904  * @xas: Array operations state.
905  *
906  * Initialise all marks for the entry specified by @xas.  If we're tracking
907  * free entries with a mark, we need to set it on all entries.  All other
908  * marks are cleared.
909  *
910  * This implementation is not as efficient as it could be; we may walk
911  * up the tree multiple times.
912  */
913 void xas_init_marks(const struct xa_state *xas)
914 {
915         xa_mark_t mark = 0;
916
917         for (;;) {
918                 if (xa_track_free(xas->xa) && mark == XA_FREE_MARK)
919                         xas_set_mark(xas, mark);
920                 else
921                         xas_clear_mark(xas, mark);
922                 if (mark == XA_MARK_MAX)
923                         break;
924                 mark_inc(mark);
925         }
926 }
927 EXPORT_SYMBOL_GPL(xas_init_marks);
928
929 /**
930  * xas_pause() - Pause a walk to drop a lock.
931  * @xas: XArray operation state.
932  *
933  * Some users need to pause a walk and drop the lock they're holding in
934  * order to yield to a higher priority thread or carry out an operation
935  * on an entry.  Those users should call this function before they drop
936  * the lock.  It resets the @xas to be suitable for the next iteration
937  * of the loop after the user has reacquired the lock.  If most entries
938  * found during a walk require you to call xas_pause(), the xa_for_each()
939  * iterator may be more appropriate.
940  *
941  * Note that xas_pause() only works for forward iteration.  If a user needs
942  * to pause a reverse iteration, we will need a xas_pause_rev().
943  */
944 void xas_pause(struct xa_state *xas)
945 {
946         struct xa_node *node = xas->xa_node;
947
948         if (xas_invalid(xas))
949                 return;
950
951         if (node) {
952                 unsigned int offset = xas->xa_offset;
953                 while (++offset < XA_CHUNK_SIZE) {
954                         if (!xa_is_sibling(xa_entry(xas->xa, node, offset)))
955                                 break;
956                 }
957                 xas->xa_index += (offset - xas->xa_offset) << node->shift;
958         } else {
959                 xas->xa_index++;
960         }
961         xas->xa_node = XAS_RESTART;
962 }
963 EXPORT_SYMBOL_GPL(xas_pause);
964
965 /*
966  * __xas_prev() - Find the previous entry in the XArray.
967  * @xas: XArray operation state.
968  *
969  * Helper function for xas_prev() which handles all the complex cases
970  * out of line.
971  */
972 void *__xas_prev(struct xa_state *xas)
973 {
974         void *entry;
975
976         if (!xas_frozen(xas->xa_node))
977                 xas->xa_index--;
978         if (xas_not_node(xas->xa_node))
979                 return xas_load(xas);
980
981         if (xas->xa_offset != get_offset(xas->xa_index, xas->xa_node))
982                 xas->xa_offset--;
983
984         while (xas->xa_offset == 255) {
985                 xas->xa_offset = xas->xa_node->offset - 1;
986                 xas->xa_node = xa_parent(xas->xa, xas->xa_node);
987                 if (!xas->xa_node)
988                         return set_bounds(xas);
989         }
990
991         for (;;) {
992                 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
993                 if (!xa_is_node(entry))
994                         return entry;
995
996                 xas->xa_node = xa_to_node(entry);
997                 xas_set_offset(xas);
998         }
999 }
1000 EXPORT_SYMBOL_GPL(__xas_prev);
1001
1002 /*
1003  * __xas_next() - Find the next entry in the XArray.
1004  * @xas: XArray operation state.
1005  *
1006  * Helper function for xas_next() which handles all the complex cases
1007  * out of line.
1008  */
1009 void *__xas_next(struct xa_state *xas)
1010 {
1011         void *entry;
1012
1013         if (!xas_frozen(xas->xa_node))
1014                 xas->xa_index++;
1015         if (xas_not_node(xas->xa_node))
1016                 return xas_load(xas);
1017
1018         if (xas->xa_offset != get_offset(xas->xa_index, xas->xa_node))
1019                 xas->xa_offset++;
1020
1021         while (xas->xa_offset == XA_CHUNK_SIZE) {
1022                 xas->xa_offset = xas->xa_node->offset + 1;
1023                 xas->xa_node = xa_parent(xas->xa, xas->xa_node);
1024                 if (!xas->xa_node)
1025                         return set_bounds(xas);
1026         }
1027
1028         for (;;) {
1029                 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
1030                 if (!xa_is_node(entry))
1031                         return entry;
1032
1033                 xas->xa_node = xa_to_node(entry);
1034                 xas_set_offset(xas);
1035         }
1036 }
1037 EXPORT_SYMBOL_GPL(__xas_next);
1038
1039 /**
1040  * xas_find() - Find the next present entry in the XArray.
1041  * @xas: XArray operation state.
1042  * @max: Highest index to return.
1043  *
1044  * If the @xas has not yet been walked to an entry, return the entry
1045  * which has an index >= xas.xa_index.  If it has been walked, the entry
1046  * currently being pointed at has been processed, and so we move to the
1047  * next entry.
1048  *
1049  * If no entry is found and the array is smaller than @max, the iterator
1050  * is set to the smallest index not yet in the array.  This allows @xas
1051  * to be immediately passed to xas_store().
1052  *
1053  * Return: The entry, if found, otherwise %NULL.
1054  */
1055 void *xas_find(struct xa_state *xas, unsigned long max)
1056 {
1057         void *entry;
1058
1059         if (xas_error(xas))
1060                 return NULL;
1061
1062         if (!xas->xa_node) {
1063                 xas->xa_index = 1;
1064                 return set_bounds(xas);
1065         } else if (xas_top(xas->xa_node)) {
1066                 entry = xas_load(xas);
1067                 if (entry || xas_not_node(xas->xa_node))
1068                         return entry;
1069         } else if (!xas->xa_node->shift &&
1070                     xas->xa_offset != (xas->xa_index & XA_CHUNK_MASK)) {
1071                 xas->xa_offset = ((xas->xa_index - 1) & XA_CHUNK_MASK) + 1;
1072         }
1073
1074         xas_advance(xas);
1075
1076         while (xas->xa_node && (xas->xa_index <= max)) {
1077                 if (unlikely(xas->xa_offset == XA_CHUNK_SIZE)) {
1078                         xas->xa_offset = xas->xa_node->offset + 1;
1079                         xas->xa_node = xa_parent(xas->xa, xas->xa_node);
1080                         continue;
1081                 }
1082
1083                 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
1084                 if (xa_is_node(entry)) {
1085                         xas->xa_node = xa_to_node(entry);
1086                         xas->xa_offset = 0;
1087                         continue;
1088                 }
1089                 if (entry && !xa_is_sibling(entry))
1090                         return entry;
1091
1092                 xas_advance(xas);
1093         }
1094
1095         if (!xas->xa_node)
1096                 xas->xa_node = XAS_BOUNDS;
1097         return NULL;
1098 }
1099 EXPORT_SYMBOL_GPL(xas_find);
1100
1101 /**
1102  * xas_find_marked() - Find the next marked entry in the XArray.
1103  * @xas: XArray operation state.
1104  * @max: Highest index to return.
1105  * @mark: Mark number to search for.
1106  *
1107  * If the @xas has not yet been walked to an entry, return the marked entry
1108  * which has an index >= xas.xa_index.  If it has been walked, the entry
1109  * currently being pointed at has been processed, and so we return the
1110  * first marked entry with an index > xas.xa_index.
1111  *
1112  * If no marked entry is found and the array is smaller than @max, @xas is
1113  * set to the bounds state and xas->xa_index is set to the smallest index
1114  * not yet in the array.  This allows @xas to be immediately passed to
1115  * xas_store().
1116  *
1117  * If no entry is found before @max is reached, @xas is set to the restart
1118  * state.
1119  *
1120  * Return: The entry, if found, otherwise %NULL.
1121  */
1122 void *xas_find_marked(struct xa_state *xas, unsigned long max, xa_mark_t mark)
1123 {
1124         bool advance = true;
1125         unsigned int offset;
1126         void *entry;
1127
1128         if (xas_error(xas))
1129                 return NULL;
1130
1131         if (!xas->xa_node) {
1132                 xas->xa_index = 1;
1133                 goto out;
1134         } else if (xas_top(xas->xa_node)) {
1135                 advance = false;
1136                 entry = xa_head(xas->xa);
1137                 xas->xa_node = NULL;
1138                 if (xas->xa_index > max_index(entry))
1139                         goto out;
1140                 if (!xa_is_node(entry)) {
1141                         if (xa_marked(xas->xa, mark))
1142                                 return entry;
1143                         xas->xa_index = 1;
1144                         goto out;
1145                 }
1146                 xas->xa_node = xa_to_node(entry);
1147                 xas->xa_offset = xas->xa_index >> xas->xa_node->shift;
1148         }
1149
1150         while (xas->xa_index <= max) {
1151                 if (unlikely(xas->xa_offset == XA_CHUNK_SIZE)) {
1152                         xas->xa_offset = xas->xa_node->offset + 1;
1153                         xas->xa_node = xa_parent(xas->xa, xas->xa_node);
1154                         if (!xas->xa_node)
1155                                 break;
1156                         advance = false;
1157                         continue;
1158                 }
1159
1160                 if (!advance) {
1161                         entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
1162                         if (xa_is_sibling(entry)) {
1163                                 xas->xa_offset = xa_to_sibling(entry);
1164                                 xas_move_index(xas, xas->xa_offset);
1165                         }
1166                 }
1167
1168                 offset = xas_find_chunk(xas, advance, mark);
1169                 if (offset > xas->xa_offset) {
1170                         advance = false;
1171                         xas_move_index(xas, offset);
1172                         /* Mind the wrap */
1173                         if ((xas->xa_index - 1) >= max)
1174                                 goto max;
1175                         xas->xa_offset = offset;
1176                         if (offset == XA_CHUNK_SIZE)
1177                                 continue;
1178                 }
1179
1180                 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
1181                 if (!xa_is_node(entry))
1182                         return entry;
1183                 xas->xa_node = xa_to_node(entry);
1184                 xas_set_offset(xas);
1185         }
1186
1187 out:
1188         if (xas->xa_index > max)
1189                 goto max;
1190         return set_bounds(xas);
1191 max:
1192         xas->xa_node = XAS_RESTART;
1193         return NULL;
1194 }
1195 EXPORT_SYMBOL_GPL(xas_find_marked);
1196
1197 /**
1198  * xas_find_conflict() - Find the next present entry in a range.
1199  * @xas: XArray operation state.
1200  *
1201  * The @xas describes both a range and a position within that range.
1202  *
1203  * Context: Any context.  Expects xa_lock to be held.
1204  * Return: The next entry in the range covered by @xas or %NULL.
1205  */
1206 void *xas_find_conflict(struct xa_state *xas)
1207 {
1208         void *curr;
1209
1210         if (xas_error(xas))
1211                 return NULL;
1212
1213         if (!xas->xa_node)
1214                 return NULL;
1215
1216         if (xas_top(xas->xa_node)) {
1217                 curr = xas_start(xas);
1218                 if (!curr)
1219                         return NULL;
1220                 while (xa_is_node(curr)) {
1221                         struct xa_node *node = xa_to_node(curr);
1222                         curr = xas_descend(xas, node);
1223                 }
1224                 if (curr)
1225                         return curr;
1226         }
1227
1228         if (xas->xa_node->shift > xas->xa_shift)
1229                 return NULL;
1230
1231         for (;;) {
1232                 if (xas->xa_node->shift == xas->xa_shift) {
1233                         if ((xas->xa_offset & xas->xa_sibs) == xas->xa_sibs)
1234                                 break;
1235                 } else if (xas->xa_offset == XA_CHUNK_MASK) {
1236                         xas->xa_offset = xas->xa_node->offset;
1237                         xas->xa_node = xa_parent_locked(xas->xa, xas->xa_node);
1238                         if (!xas->xa_node)
1239                                 break;
1240                         continue;
1241                 }
1242                 curr = xa_entry_locked(xas->xa, xas->xa_node, ++xas->xa_offset);
1243                 if (xa_is_sibling(curr))
1244                         continue;
1245                 while (xa_is_node(curr)) {
1246                         xas->xa_node = xa_to_node(curr);
1247                         xas->xa_offset = 0;
1248                         curr = xa_entry_locked(xas->xa, xas->xa_node, 0);
1249                 }
1250                 if (curr)
1251                         return curr;
1252         }
1253         xas->xa_offset -= xas->xa_sibs;
1254         return NULL;
1255 }
1256 EXPORT_SYMBOL_GPL(xas_find_conflict);
1257
1258 /**
1259  * xa_load() - Load an entry from an XArray.
1260  * @xa: XArray.
1261  * @index: index into array.
1262  *
1263  * Context: Any context.  Takes and releases the RCU lock.
1264  * Return: The entry at @index in @xa.
1265  */
1266 void *xa_load(struct xarray *xa, unsigned long index)
1267 {
1268         XA_STATE(xas, xa, index);
1269         void *entry;
1270
1271         rcu_read_lock();
1272         do {
1273                 entry = xas_load(&xas);
1274                 if (xa_is_zero(entry))
1275                         entry = NULL;
1276         } while (xas_retry(&xas, entry));
1277         rcu_read_unlock();
1278
1279         return entry;
1280 }
1281 EXPORT_SYMBOL(xa_load);
1282
1283 static void *xas_result(struct xa_state *xas, void *curr)
1284 {
1285         if (xa_is_zero(curr))
1286                 return NULL;
1287         if (xas_error(xas))
1288                 curr = xas->xa_node;
1289         return curr;
1290 }
1291
1292 /**
1293  * __xa_erase() - Erase this entry from the XArray while locked.
1294  * @xa: XArray.
1295  * @index: Index into array.
1296  *
1297  * If the entry at this index is a multi-index entry then all indices will
1298  * be erased, and the entry will no longer be a multi-index entry.
1299  * This function expects the xa_lock to be held on entry.
1300  *
1301  * Context: Any context.  Expects xa_lock to be held on entry.  May
1302  * release and reacquire xa_lock if @gfp flags permit.
1303  * Return: The old entry at this index.
1304  */
1305 void *__xa_erase(struct xarray *xa, unsigned long index)
1306 {
1307         XA_STATE(xas, xa, index);
1308         return xas_result(&xas, xas_store(&xas, NULL));
1309 }
1310 EXPORT_SYMBOL(__xa_erase);
1311
1312 /**
1313  * xa_erase() - Erase this entry from the XArray.
1314  * @xa: XArray.
1315  * @index: Index of entry.
1316  *
1317  * This function is the equivalent of calling xa_store() with %NULL as
1318  * the third argument.  The XArray does not need to allocate memory, so
1319  * the user does not need to provide GFP flags.
1320  *
1321  * Context: Any context.  Takes and releases the xa_lock.
1322  * Return: The entry which used to be at this index.
1323  */
1324 void *xa_erase(struct xarray *xa, unsigned long index)
1325 {
1326         void *entry;
1327
1328         xa_lock(xa);
1329         entry = __xa_erase(xa, index);
1330         xa_unlock(xa);
1331
1332         return entry;
1333 }
1334 EXPORT_SYMBOL(xa_erase);
1335
1336 /**
1337  * __xa_store() - Store this entry in the XArray.
1338  * @xa: XArray.
1339  * @index: Index into array.
1340  * @entry: New entry.
1341  * @gfp: Memory allocation flags.
1342  *
1343  * You must already be holding the xa_lock when calling this function.
1344  * It will drop the lock if needed to allocate memory, and then reacquire
1345  * it afterwards.
1346  *
1347  * Context: Any context.  Expects xa_lock to be held on entry.  May
1348  * release and reacquire xa_lock if @gfp flags permit.
1349  * Return: The old entry at this index or xa_err() if an error happened.
1350  */
1351 void *__xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)
1352 {
1353         XA_STATE(xas, xa, index);
1354         void *curr;
1355
1356         if (WARN_ON_ONCE(xa_is_advanced(entry)))
1357                 return XA_ERROR(-EINVAL);
1358         if (xa_track_free(xa) && !entry)
1359                 entry = XA_ZERO_ENTRY;
1360
1361         do {
1362                 curr = xas_store(&xas, entry);
1363                 if (xa_track_free(xa))
1364                         xas_clear_mark(&xas, XA_FREE_MARK);
1365         } while (__xas_nomem(&xas, gfp));
1366
1367         return xas_result(&xas, curr);
1368 }
1369 EXPORT_SYMBOL(__xa_store);
1370
1371 /**
1372  * xa_store() - Store this entry in the XArray.
1373  * @xa: XArray.
1374  * @index: Index into array.
1375  * @entry: New entry.
1376  * @gfp: Memory allocation flags.
1377  *
1378  * After this function returns, loads from this index will return @entry.
1379  * Storing into an existing multislot entry updates the entry of every index.
1380  * The marks associated with @index are unaffected unless @entry is %NULL.
1381  *
1382  * Context: Any context.  Takes and releases the xa_lock.
1383  * May sleep if the @gfp flags permit.
1384  * Return: The old entry at this index on success, xa_err(-EINVAL) if @entry
1385  * cannot be stored in an XArray, or xa_err(-ENOMEM) if memory allocation
1386  * failed.
1387  */
1388 void *xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)
1389 {
1390         void *curr;
1391
1392         xa_lock(xa);
1393         curr = __xa_store(xa, index, entry, gfp);
1394         xa_unlock(xa);
1395
1396         return curr;
1397 }
1398 EXPORT_SYMBOL(xa_store);
1399
1400 /**
1401  * __xa_cmpxchg() - Store this entry in the XArray.
1402  * @xa: XArray.
1403  * @index: Index into array.
1404  * @old: Old value to test against.
1405  * @entry: New entry.
1406  * @gfp: Memory allocation flags.
1407  *
1408  * You must already be holding the xa_lock when calling this function.
1409  * It will drop the lock if needed to allocate memory, and then reacquire
1410  * it afterwards.
1411  *
1412  * Context: Any context.  Expects xa_lock to be held on entry.  May
1413  * release and reacquire xa_lock if @gfp flags permit.
1414  * Return: The old entry at this index or xa_err() if an error happened.
1415  */
1416 void *__xa_cmpxchg(struct xarray *xa, unsigned long index,
1417                         void *old, void *entry, gfp_t gfp)
1418 {
1419         XA_STATE(xas, xa, index);
1420         void *curr;
1421
1422         if (WARN_ON_ONCE(xa_is_advanced(entry)))
1423                 return XA_ERROR(-EINVAL);
1424         if (xa_track_free(xa) && !entry)
1425                 entry = XA_ZERO_ENTRY;
1426
1427         do {
1428                 curr = xas_load(&xas);
1429                 if (curr == XA_ZERO_ENTRY)
1430                         curr = NULL;
1431                 if (curr == old) {
1432                         xas_store(&xas, entry);
1433                         if (xa_track_free(xa))
1434                                 xas_clear_mark(&xas, XA_FREE_MARK);
1435                 }
1436         } while (__xas_nomem(&xas, gfp));
1437
1438         return xas_result(&xas, curr);
1439 }
1440 EXPORT_SYMBOL(__xa_cmpxchg);
1441
1442 /**
1443  * __xa_insert() - Store this entry in the XArray if no entry is present.
1444  * @xa: XArray.
1445  * @index: Index into array.
1446  * @entry: New entry.
1447  * @gfp: Memory allocation flags.
1448  *
1449  * Inserting a NULL entry will store a reserved entry (like xa_reserve())
1450  * if no entry is present.  Inserting will fail if a reserved entry is
1451  * present, even though loading from this index will return NULL.
1452  *
1453  * Context: Any context.  Expects xa_lock to be held on entry.  May
1454  * release and reacquire xa_lock if @gfp flags permit.
1455  * Return: 0 if the store succeeded.  -EEXIST if another entry was present.
1456  * -ENOMEM if memory could not be allocated.
1457  */
1458 int __xa_insert(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)
1459 {
1460         XA_STATE(xas, xa, index);
1461         void *curr;
1462
1463         if (WARN_ON_ONCE(xa_is_advanced(entry)))
1464                 return -EINVAL;
1465         if (!entry)
1466                 entry = XA_ZERO_ENTRY;
1467
1468         do {
1469                 curr = xas_load(&xas);
1470                 if (!curr) {
1471                         xas_store(&xas, entry);
1472                         if (xa_track_free(xa))
1473                                 xas_clear_mark(&xas, XA_FREE_MARK);
1474                 } else {
1475                         xas_set_err(&xas, -EEXIST);
1476                 }
1477         } while (__xas_nomem(&xas, gfp));
1478
1479         return xas_error(&xas);
1480 }
1481 EXPORT_SYMBOL(__xa_insert);
1482
1483 /**
1484  * __xa_reserve() - Reserve this index in the XArray.
1485  * @xa: XArray.
1486  * @index: Index into array.
1487  * @gfp: Memory allocation flags.
1488  *
1489  * Ensures there is somewhere to store an entry at @index in the array.
1490  * If there is already something stored at @index, this function does
1491  * nothing.  If there was nothing there, the entry is marked as reserved.
1492  * Loading from a reserved entry returns a %NULL pointer.
1493  *
1494  * If you do not use the entry that you have reserved, call xa_release()
1495  * or xa_erase() to free any unnecessary memory.
1496  *
1497  * Context: Any context.  Expects the xa_lock to be held on entry.  May
1498  * release the lock, sleep and reacquire the lock if the @gfp flags permit.
1499  * Return: 0 if the reservation succeeded or -ENOMEM if it failed.
1500  */
1501 int __xa_reserve(struct xarray *xa, unsigned long index, gfp_t gfp)
1502 {
1503         XA_STATE(xas, xa, index);
1504         void *curr;
1505
1506         do {
1507                 curr = xas_load(&xas);
1508                 if (!curr) {
1509                         xas_store(&xas, XA_ZERO_ENTRY);
1510                         if (xa_track_free(xa))
1511                                 xas_clear_mark(&xas, XA_FREE_MARK);
1512                 }
1513         } while (__xas_nomem(&xas, gfp));
1514
1515         return xas_error(&xas);
1516 }
1517 EXPORT_SYMBOL(__xa_reserve);
1518
1519 #ifdef CONFIG_XARRAY_MULTI
1520 static void xas_set_range(struct xa_state *xas, unsigned long first,
1521                 unsigned long last)
1522 {
1523         unsigned int shift = 0;
1524         unsigned long sibs = last - first;
1525         unsigned int offset = XA_CHUNK_MASK;
1526
1527         xas_set(xas, first);
1528
1529         while ((first & XA_CHUNK_MASK) == 0) {
1530                 if (sibs < XA_CHUNK_MASK)
1531                         break;
1532                 if ((sibs == XA_CHUNK_MASK) && (offset < XA_CHUNK_MASK))
1533                         break;
1534                 shift += XA_CHUNK_SHIFT;
1535                 if (offset == XA_CHUNK_MASK)
1536                         offset = sibs & XA_CHUNK_MASK;
1537                 sibs >>= XA_CHUNK_SHIFT;
1538                 first >>= XA_CHUNK_SHIFT;
1539         }
1540
1541         offset = first & XA_CHUNK_MASK;
1542         if (offset + sibs > XA_CHUNK_MASK)
1543                 sibs = XA_CHUNK_MASK - offset;
1544         if ((((first + sibs + 1) << shift) - 1) > last)
1545                 sibs -= 1;
1546
1547         xas->xa_shift = shift;
1548         xas->xa_sibs = sibs;
1549 }
1550
1551 /**
1552  * xa_store_range() - Store this entry at a range of indices in the XArray.
1553  * @xa: XArray.
1554  * @first: First index to affect.
1555  * @last: Last index to affect.
1556  * @entry: New entry.
1557  * @gfp: Memory allocation flags.
1558  *
1559  * After this function returns, loads from any index between @first and @last,
1560  * inclusive will return @entry.
1561  * Storing into an existing multislot entry updates the entry of every index.
1562  * The marks associated with @index are unaffected unless @entry is %NULL.
1563  *
1564  * Context: Process context.  Takes and releases the xa_lock.  May sleep
1565  * if the @gfp flags permit.
1566  * Return: %NULL on success, xa_err(-EINVAL) if @entry cannot be stored in
1567  * an XArray, or xa_err(-ENOMEM) if memory allocation failed.
1568  */
1569 void *xa_store_range(struct xarray *xa, unsigned long first,
1570                 unsigned long last, void *entry, gfp_t gfp)
1571 {
1572         XA_STATE(xas, xa, 0);
1573
1574         if (WARN_ON_ONCE(xa_is_internal(entry)))
1575                 return XA_ERROR(-EINVAL);
1576         if (last < first)
1577                 return XA_ERROR(-EINVAL);
1578
1579         do {
1580                 xas_lock(&xas);
1581                 if (entry) {
1582                         unsigned int order = BITS_PER_LONG;
1583                         if (last + 1)
1584                                 order = __ffs(last + 1);
1585                         xas_set_order(&xas, last, order);
1586                         xas_create(&xas, true);
1587                         if (xas_error(&xas))
1588                                 goto unlock;
1589                 }
1590                 do {
1591                         xas_set_range(&xas, first, last);
1592                         xas_store(&xas, entry);
1593                         if (xas_error(&xas))
1594                                 goto unlock;
1595                         first += xas_size(&xas);
1596                 } while (first <= last);
1597 unlock:
1598                 xas_unlock(&xas);
1599         } while (xas_nomem(&xas, gfp));
1600
1601         return xas_result(&xas, NULL);
1602 }
1603 EXPORT_SYMBOL(xa_store_range);
1604 #endif /* CONFIG_XARRAY_MULTI */
1605
1606 /**
1607  * __xa_alloc() - Find somewhere to store this entry in the XArray.
1608  * @xa: XArray.
1609  * @id: Pointer to ID.
1610  * @max: Maximum ID to allocate (inclusive).
1611  * @entry: New entry.
1612  * @gfp: Memory allocation flags.
1613  *
1614  * Allocates an unused ID in the range specified by @id and @max.
1615  * Updates the @id pointer with the index, then stores the entry at that
1616  * index.  A concurrent lookup will not see an uninitialised @id.
1617  *
1618  * Context: Any context.  Expects xa_lock to be held on entry.  May
1619  * release and reacquire xa_lock if @gfp flags permit.
1620  * Return: 0 on success, -ENOMEM if memory allocation fails or -ENOSPC if
1621  * there is no more space in the XArray.
1622  */
1623 int __xa_alloc(struct xarray *xa, u32 *id, u32 max, void *entry, gfp_t gfp)
1624 {
1625         XA_STATE(xas, xa, 0);
1626         int err;
1627
1628         if (WARN_ON_ONCE(xa_is_advanced(entry)))
1629                 return -EINVAL;
1630         if (WARN_ON_ONCE(!xa_track_free(xa)))
1631                 return -EINVAL;
1632
1633         if (!entry)
1634                 entry = XA_ZERO_ENTRY;
1635
1636         do {
1637                 xas.xa_index = *id;
1638                 xas_find_marked(&xas, max, XA_FREE_MARK);
1639                 if (xas.xa_node == XAS_RESTART)
1640                         xas_set_err(&xas, -ENOSPC);
1641                 xas_store(&xas, entry);
1642                 xas_clear_mark(&xas, XA_FREE_MARK);
1643         } while (__xas_nomem(&xas, gfp));
1644
1645         err = xas_error(&xas);
1646         if (!err)
1647                 *id = xas.xa_index;
1648         return err;
1649 }
1650 EXPORT_SYMBOL(__xa_alloc);
1651
1652 /**
1653  * __xa_set_mark() - Set this mark on this entry while locked.
1654  * @xa: XArray.
1655  * @index: Index of entry.
1656  * @mark: Mark number.
1657  *
1658  * Attempting to set a mark on a %NULL entry does not succeed.
1659  *
1660  * Context: Any context.  Expects xa_lock to be held on entry.
1661  */
1662 void __xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
1663 {
1664         XA_STATE(xas, xa, index);
1665         void *entry = xas_load(&xas);
1666
1667         if (entry)
1668                 xas_set_mark(&xas, mark);
1669 }
1670 EXPORT_SYMBOL(__xa_set_mark);
1671
1672 /**
1673  * __xa_clear_mark() - Clear this mark on this entry while locked.
1674  * @xa: XArray.
1675  * @index: Index of entry.
1676  * @mark: Mark number.
1677  *
1678  * Context: Any context.  Expects xa_lock to be held on entry.
1679  */
1680 void __xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
1681 {
1682         XA_STATE(xas, xa, index);
1683         void *entry = xas_load(&xas);
1684
1685         if (entry)
1686                 xas_clear_mark(&xas, mark);
1687 }
1688 EXPORT_SYMBOL(__xa_clear_mark);
1689
1690 /**
1691  * xa_get_mark() - Inquire whether this mark is set on this entry.
1692  * @xa: XArray.
1693  * @index: Index of entry.
1694  * @mark: Mark number.
1695  *
1696  * This function uses the RCU read lock, so the result may be out of date
1697  * by the time it returns.  If you need the result to be stable, use a lock.
1698  *
1699  * Context: Any context.  Takes and releases the RCU lock.
1700  * Return: True if the entry at @index has this mark set, false if it doesn't.
1701  */
1702 bool xa_get_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
1703 {
1704         XA_STATE(xas, xa, index);
1705         void *entry;
1706
1707         rcu_read_lock();
1708         entry = xas_start(&xas);
1709         while (xas_get_mark(&xas, mark)) {
1710                 if (!xa_is_node(entry))
1711                         goto found;
1712                 entry = xas_descend(&xas, xa_to_node(entry));
1713         }
1714         rcu_read_unlock();
1715         return false;
1716  found:
1717         rcu_read_unlock();
1718         return true;
1719 }
1720 EXPORT_SYMBOL(xa_get_mark);
1721
1722 /**
1723  * xa_set_mark() - Set this mark on this entry.
1724  * @xa: XArray.
1725  * @index: Index of entry.
1726  * @mark: Mark number.
1727  *
1728  * Attempting to set a mark on a %NULL entry does not succeed.
1729  *
1730  * Context: Process context.  Takes and releases the xa_lock.
1731  */
1732 void xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
1733 {
1734         xa_lock(xa);
1735         __xa_set_mark(xa, index, mark);
1736         xa_unlock(xa);
1737 }
1738 EXPORT_SYMBOL(xa_set_mark);
1739
1740 /**
1741  * xa_clear_mark() - Clear this mark on this entry.
1742  * @xa: XArray.
1743  * @index: Index of entry.
1744  * @mark: Mark number.
1745  *
1746  * Clearing a mark always succeeds.
1747  *
1748  * Context: Process context.  Takes and releases the xa_lock.
1749  */
1750 void xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
1751 {
1752         xa_lock(xa);
1753         __xa_clear_mark(xa, index, mark);
1754         xa_unlock(xa);
1755 }
1756 EXPORT_SYMBOL(xa_clear_mark);
1757
1758 /**
1759  * xa_find() - Search the XArray for an entry.
1760  * @xa: XArray.
1761  * @indexp: Pointer to an index.
1762  * @max: Maximum index to search to.
1763  * @filter: Selection criterion.
1764  *
1765  * Finds the entry in @xa which matches the @filter, and has the lowest
1766  * index that is at least @indexp and no more than @max.
1767  * If an entry is found, @indexp is updated to be the index of the entry.
1768  * This function is protected by the RCU read lock, so it may not find
1769  * entries which are being simultaneously added.  It will not return an
1770  * %XA_RETRY_ENTRY; if you need to see retry entries, use xas_find().
1771  *
1772  * Context: Any context.  Takes and releases the RCU lock.
1773  * Return: The entry, if found, otherwise %NULL.
1774  */
1775 void *xa_find(struct xarray *xa, unsigned long *indexp,
1776                         unsigned long max, xa_mark_t filter)
1777 {
1778         XA_STATE(xas, xa, *indexp);
1779         void *entry;
1780
1781         rcu_read_lock();
1782         do {
1783                 if ((__force unsigned int)filter < XA_MAX_MARKS)
1784                         entry = xas_find_marked(&xas, max, filter);
1785                 else
1786                         entry = xas_find(&xas, max);
1787         } while (xas_retry(&xas, entry));
1788         rcu_read_unlock();
1789
1790         if (entry)
1791                 *indexp = xas.xa_index;
1792         return entry;
1793 }
1794 EXPORT_SYMBOL(xa_find);
1795
1796 /**
1797  * xa_find_after() - Search the XArray for a present entry.
1798  * @xa: XArray.
1799  * @indexp: Pointer to an index.
1800  * @max: Maximum index to search to.
1801  * @filter: Selection criterion.
1802  *
1803  * Finds the entry in @xa which matches the @filter and has the lowest
1804  * index that is above @indexp and no more than @max.
1805  * If an entry is found, @indexp is updated to be the index of the entry.
1806  * This function is protected by the RCU read lock, so it may miss entries
1807  * which are being simultaneously added.  It will not return an
1808  * %XA_RETRY_ENTRY; if you need to see retry entries, use xas_find().
1809  *
1810  * Context: Any context.  Takes and releases the RCU lock.
1811  * Return: The pointer, if found, otherwise %NULL.
1812  */
1813 void *xa_find_after(struct xarray *xa, unsigned long *indexp,
1814                         unsigned long max, xa_mark_t filter)
1815 {
1816         XA_STATE(xas, xa, *indexp + 1);
1817         void *entry;
1818
1819         rcu_read_lock();
1820         for (;;) {
1821                 if ((__force unsigned int)filter < XA_MAX_MARKS)
1822                         entry = xas_find_marked(&xas, max, filter);
1823                 else
1824                         entry = xas_find(&xas, max);
1825                 if (xas.xa_node == XAS_BOUNDS)
1826                         break;
1827                 if (xas.xa_shift) {
1828                         if (xas.xa_index & ((1UL << xas.xa_shift) - 1))
1829                                 continue;
1830                 } else {
1831                         if (xas.xa_offset < (xas.xa_index & XA_CHUNK_MASK))
1832                                 continue;
1833                 }
1834                 if (!xas_retry(&xas, entry))
1835                         break;
1836         }
1837         rcu_read_unlock();
1838
1839         if (entry)
1840                 *indexp = xas.xa_index;
1841         return entry;
1842 }
1843 EXPORT_SYMBOL(xa_find_after);
1844
1845 static unsigned int xas_extract_present(struct xa_state *xas, void **dst,
1846                         unsigned long max, unsigned int n)
1847 {
1848         void *entry;
1849         unsigned int i = 0;
1850
1851         rcu_read_lock();
1852         xas_for_each(xas, entry, max) {
1853                 if (xas_retry(xas, entry))
1854                         continue;
1855                 dst[i++] = entry;
1856                 if (i == n)
1857                         break;
1858         }
1859         rcu_read_unlock();
1860
1861         return i;
1862 }
1863
1864 static unsigned int xas_extract_marked(struct xa_state *xas, void **dst,
1865                         unsigned long max, unsigned int n, xa_mark_t mark)
1866 {
1867         void *entry;
1868         unsigned int i = 0;
1869
1870         rcu_read_lock();
1871         xas_for_each_marked(xas, entry, max, mark) {
1872                 if (xas_retry(xas, entry))
1873                         continue;
1874                 dst[i++] = entry;
1875                 if (i == n)
1876                         break;
1877         }
1878         rcu_read_unlock();
1879
1880         return i;
1881 }
1882
1883 /**
1884  * xa_extract() - Copy selected entries from the XArray into a normal array.
1885  * @xa: The source XArray to copy from.
1886  * @dst: The buffer to copy entries into.
1887  * @start: The first index in the XArray eligible to be selected.
1888  * @max: The last index in the XArray eligible to be selected.
1889  * @n: The maximum number of entries to copy.
1890  * @filter: Selection criterion.
1891  *
1892  * Copies up to @n entries that match @filter from the XArray.  The
1893  * copied entries will have indices between @start and @max, inclusive.
1894  *
1895  * The @filter may be an XArray mark value, in which case entries which are
1896  * marked with that mark will be copied.  It may also be %XA_PRESENT, in
1897  * which case all entries which are not %NULL will be copied.
1898  *
1899  * The entries returned may not represent a snapshot of the XArray at a
1900  * moment in time.  For example, if another thread stores to index 5, then
1901  * index 10, calling xa_extract() may return the old contents of index 5
1902  * and the new contents of index 10.  Indices not modified while this
1903  * function is running will not be skipped.
1904  *
1905  * If you need stronger guarantees, holding the xa_lock across calls to this
1906  * function will prevent concurrent modification.
1907  *
1908  * Context: Any context.  Takes and releases the RCU lock.
1909  * Return: The number of entries copied.
1910  */
1911 unsigned int xa_extract(struct xarray *xa, void **dst, unsigned long start,
1912                         unsigned long max, unsigned int n, xa_mark_t filter)
1913 {
1914         XA_STATE(xas, xa, start);
1915
1916         if (!n)
1917                 return 0;
1918
1919         if ((__force unsigned int)filter < XA_MAX_MARKS)
1920                 return xas_extract_marked(&xas, dst, max, n, filter);
1921         return xas_extract_present(&xas, dst, max, n);
1922 }
1923 EXPORT_SYMBOL(xa_extract);
1924
1925 /**
1926  * xa_destroy() - Free all internal data structures.
1927  * @xa: XArray.
1928  *
1929  * After calling this function, the XArray is empty and has freed all memory
1930  * allocated for its internal data structures.  You are responsible for
1931  * freeing the objects referenced by the XArray.
1932  *
1933  * Context: Any context.  Takes and releases the xa_lock, interrupt-safe.
1934  */
1935 void xa_destroy(struct xarray *xa)
1936 {
1937         XA_STATE(xas, xa, 0);
1938         unsigned long flags;
1939         void *entry;
1940
1941         xas.xa_node = NULL;
1942         xas_lock_irqsave(&xas, flags);
1943         entry = xa_head_locked(xa);
1944         RCU_INIT_POINTER(xa->xa_head, NULL);
1945         xas_init_marks(&xas);
1946         /* lockdep checks we're still holding the lock in xas_free_nodes() */
1947         if (xa_is_node(entry))
1948                 xas_free_nodes(&xas, xa_to_node(entry));
1949         xas_unlock_irqrestore(&xas, flags);
1950 }
1951 EXPORT_SYMBOL(xa_destroy);
1952
1953 #ifdef XA_DEBUG
1954 void xa_dump_node(const struct xa_node *node)
1955 {
1956         unsigned i, j;
1957
1958         if (!node)
1959                 return;
1960         if ((unsigned long)node & 3) {
1961                 pr_cont("node %px\n", node);
1962                 return;
1963         }
1964
1965         pr_cont("node %px %s %d parent %px shift %d count %d values %d "
1966                 "array %px list %px %px marks",
1967                 node, node->parent ? "offset" : "max", node->offset,
1968                 node->parent, node->shift, node->count, node->nr_values,
1969                 node->array, node->private_list.prev, node->private_list.next);
1970         for (i = 0; i < XA_MAX_MARKS; i++)
1971                 for (j = 0; j < XA_MARK_LONGS; j++)
1972                         pr_cont(" %lx", node->marks[i][j]);
1973         pr_cont("\n");
1974 }
1975
1976 void xa_dump_index(unsigned long index, unsigned int shift)
1977 {
1978         if (!shift)
1979                 pr_info("%lu: ", index);
1980         else if (shift >= BITS_PER_LONG)
1981                 pr_info("0-%lu: ", ~0UL);
1982         else
1983                 pr_info("%lu-%lu: ", index, index | ((1UL << shift) - 1));
1984 }
1985
1986 void xa_dump_entry(const void *entry, unsigned long index, unsigned long shift)
1987 {
1988         if (!entry)
1989                 return;
1990
1991         xa_dump_index(index, shift);
1992
1993         if (xa_is_node(entry)) {
1994                 if (shift == 0) {
1995                         pr_cont("%px\n", entry);
1996                 } else {
1997                         unsigned long i;
1998                         struct xa_node *node = xa_to_node(entry);
1999                         xa_dump_node(node);
2000                         for (i = 0; i < XA_CHUNK_SIZE; i++)
2001                                 xa_dump_entry(node->slots[i],
2002                                       index + (i << node->shift), node->shift);
2003                 }
2004         } else if (xa_is_value(entry))
2005                 pr_cont("value %ld (0x%lx) [%px]\n", xa_to_value(entry),
2006                                                 xa_to_value(entry), entry);
2007         else if (!xa_is_internal(entry))
2008                 pr_cont("%px\n", entry);
2009         else if (xa_is_retry(entry))
2010                 pr_cont("retry (%ld)\n", xa_to_internal(entry));
2011         else if (xa_is_sibling(entry))
2012                 pr_cont("sibling (slot %ld)\n", xa_to_sibling(entry));
2013         else if (xa_is_zero(entry))
2014                 pr_cont("zero (%ld)\n", xa_to_internal(entry));
2015         else
2016                 pr_cont("UNKNOWN ENTRY (%px)\n", entry);
2017 }
2018
2019 void xa_dump(const struct xarray *xa)
2020 {
2021         void *entry = xa->xa_head;
2022         unsigned int shift = 0;
2023
2024         pr_info("xarray: %px head %px flags %x marks %d %d %d\n", xa, entry,
2025                         xa->xa_flags, xa_marked(xa, XA_MARK_0),
2026                         xa_marked(xa, XA_MARK_1), xa_marked(xa, XA_MARK_2));
2027         if (xa_is_node(entry))
2028                 shift = xa_to_node(entry)->shift + XA_CHUNK_SHIFT;
2029         xa_dump_entry(entry, 0, shift);
2030 }
2031 #endif