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