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