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