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