28  * The bottom two bits of the entry determine how the XArray interprets
31  * 00: Pointer entry
32  * 10: Internal entry
33  * x1: Value entry or tagged pointer
41  * 256: Retry entry
42  * 257: Zero entry
52  * xa_mk_value() - Create an XArray entry from an integer.
56  * Return: An entry suitable for storing in the XArray.
65  * xa_to_value() - Get value stored in an XArray entry.
66  * @entry: XArray entry.
69  * Return: The value stored in the XArray entry.
71 static inline unsigned long xa_to_value(const void *entry)  in xa_to_value()  argument
73 	return (unsigned long)entry >> 1;  in xa_to_value()
77  * xa_is_value() - Determine if an entry is a value.
78  * @entry: XArray entry.
81  * Return: True if the entry is a value, false if it is a pointer.
83 static inline bool xa_is_value(const void *entry)  in xa_is_value()  argument
85 	return (unsigned long)entry & 1;  in xa_is_value()
89  * xa_tag_pointer() - Create an XArray entry for a tagged pointer.
99  * Return: An XArray entry.
107  * xa_untag_pointer() - Turn an XArray entry into a plain pointer.
108  * @entry: XArray entry.
116 static inline void *xa_untag_pointer(void *entry)  in xa_untag_pointer()  argument
118 	return (void *)((unsigned long)entry & ~3UL);  in xa_untag_pointer()
122  * xa_pointer_tag() - Get the tag stored in an XArray entry.
123  * @entry: XArray entry.
131 static inline unsigned int xa_pointer_tag(void *entry)  in xa_pointer_tag()  argument
133 	return (unsigned long)entry & 3UL;  in xa_pointer_tag()
137  * xa_mk_internal() - Create an internal entry.
138  * @v: Value to turn into an internal entry.
142  * is used for the retry entry.  257 is used for the reserved / zero entry.
147  * Return: An XArray internal entry corresponding to this value.
155  * xa_to_internal() - Extract the value from an internal entry.
156  * @entry: XArray entry.
159  * Return: The value which was stored in the internal entry.
161 static inline unsigned long xa_to_internal(const void *entry)  in xa_to_internal()  argument
163 	return (unsigned long)entry >> 2;  in xa_to_internal()
167  * xa_is_internal() - Is the entry an internal entry?
168  * @entry: XArray entry.
171  * Return: %true if the entry is an internal entry.
173 static inline bool xa_is_internal(const void *entry)  in xa_is_internal()  argument
175 	return ((unsigned long)entry & 3) == 2;  in xa_is_internal()
181  * xa_is_zero() - Is the entry a zero entry?
182  * @entry: Entry retrieved from the XArray
185  * a zero entry.  You can only see zero entries by using the advanced API.
187  * Return: %true if the entry is a zero entry.
189 static inline bool xa_is_zero(const void *entry)  in xa_is_zero()  argument
191 	return unlikely(entry == XA_ZERO_ENTRY);  in xa_is_zero()
196  * @entry: Result from calling an XArray function
203  * Return: %true if the entry indicates an error.
205 static inline bool xa_is_err(const void *entry)  in xa_is_err()  argument
207 	return unlikely(xa_is_internal(entry) &&  in xa_is_err()
208 			entry >= xa_mk_internal(-MAX_ERRNO));  in xa_is_err()
213  * @entry: Result from calling an XArray function.
223 static inline int xa_err(void *entry)  in xa_err()  argument
226 	if (xa_is_err(entry))  in xa_err()
227 		return (long)entry >> 2;  in xa_err()
296  * If the only non-NULL entry in the array is at index 0, @xa_head is that
297  * entry.  If any other entry in the array is non-NULL, @xa_head points
356 void *xa_store(struct xarray *, unsigned long index, void *entry, gfp_t);
359 			void *entry, gfp_t);
415  * xa_marked() - Inquire whether any entry in this array has a mark set
420  * Return: %true if any entry has this mark set.
430  * @index: Index of @entry.
431  * @entry: Entry retrieved from array.
435  * During the iteration, @entry will have the value of the entry stored
438  * during the iteration.  At the end of the iteration, @entry will be set
444  * xa_for_each_range() will spin if it hits a retry entry; if you intend to
451 #define xa_for_each_range(xa, index, entry, start, last)		\  argument
453 	     entry = xa_find(xa, &index, last, XA_PRESENT);		\
454 	     entry;							\
455 	     entry = xa_find_after(xa, &index, last, XA_PRESENT))
460  * @index: Index of @entry.
461  * @entry: Entry retrieved from array.
464  * During the iteration, @entry will have the value of the entry stored
467  * during the iteration.  At the end of the iteration, @entry will be set
473  * xa_for_each_start() will spin if it hits a retry entry; if you intend to
480 #define xa_for_each_start(xa, index, entry, start) \  argument
481 	xa_for_each_range(xa, index, entry, start, ULONG_MAX)
486  * @index: Index of @entry.
487  * @entry: Entry retrieved from array.
489  * During the iteration, @entry will have the value of the entry stored
492  * iteration.  At the end of the iteration, @entry will be set to NULL and
498  * will spin if it hits a retry entry; if you intend to see retry entries,
504 #define xa_for_each(xa, index, entry) \  argument
505 	xa_for_each_start(xa, index, entry, 0)
510  * @index: Index of @entry.
511  * @entry: Entry retrieved from array.
514  * During the iteration, @entry will have the value of the entry stored
518  * during the iteration.  At the end of the iteration, @entry will be set to
524  * xa_for_each_marked() will spin if it hits a retry entry; if you intend to
531 #define xa_for_each_marked(xa, index, entry, filter) \  argument
532 	for (index = 0, entry = xa_find(xa, &index, ULONG_MAX, filter); \
533 	     entry; entry = xa_find_after(xa, &index, ULONG_MAX, filter))
563 void *__xa_store(struct xarray *, unsigned long index, void *entry, gfp_t);
565 		void *entry, gfp_t);
567 		void *entry, gfp_t);
568 int __must_check __xa_alloc(struct xarray *, u32 *id, void *entry,
570 int __must_check __xa_alloc_cyclic(struct xarray *, u32 *id, void *entry,
576  * xa_store_bh() - Store this entry in the XArray.
579  * @entry: New entry.
587  * Return: The old entry at this index or xa_err() if an error happened.
590 		void *entry, gfp_t gfp)  in xa_store_bh()  argument
596 	curr = __xa_store(xa, index, entry, gfp);  in xa_store_bh()
603  * xa_store_irq() - Store this entry in the XArray.
606  * @entry: New entry.
614  * Return: The old entry at this index or xa_err() if an error happened.
617 		void *entry, gfp_t gfp)  in xa_store_irq()  argument
623 	curr = __xa_store(xa, index, entry, gfp);  in xa_store_irq()
630  * xa_erase_bh() - Erase this entry from the XArray.
632  * @index: Index of entry.
635  * If the index is part of a multi-index entry, all indices will be erased
636  * and none of the entries will be part of a multi-index entry.
640  * Return: The entry which used to be at this index.
644 	void *entry;  in xa_erase_bh()  local
647 	entry = __xa_erase(xa, index);  in xa_erase_bh()
650 	return entry;  in xa_erase_bh()
654  * xa_erase_irq() - Erase this entry from the XArray.
656  * @index: Index of entry.
659  * If the index is part of a multi-index entry, all indices will be erased
660  * and none of the entries will be part of a multi-index entry.
664  * Return: The entry which used to be at this index.
668 	void *entry;  in xa_erase_irq()  local
671 	entry = __xa_erase(xa, index);  in xa_erase_irq()
674 	return entry;  in xa_erase_irq()
678  * xa_cmpxchg() - Conditionally replace an entry in the XArray.
682  * @entry: New value to place in array.
685  * If the entry at @index is the same as @old, replace it with @entry.
693 			void *old, void *entry, gfp_t gfp)  in xa_cmpxchg()  argument
699 	curr = __xa_cmpxchg(xa, index, old, entry, gfp);  in xa_cmpxchg()
706  * xa_cmpxchg_bh() - Conditionally replace an entry in the XArray.
710  * @entry: New value to place in array.
721 			void *old, void *entry, gfp_t gfp)  in xa_cmpxchg_bh()  argument
727 	curr = __xa_cmpxchg(xa, index, old, entry, gfp);  in xa_cmpxchg_bh()
734  * xa_cmpxchg_irq() - Conditionally replace an entry in the XArray.
738  * @entry: New value to place in array.
749 			void *old, void *entry, gfp_t gfp)  in xa_cmpxchg_irq()  argument
755 	curr = __xa_cmpxchg(xa, index, old, entry, gfp);  in xa_cmpxchg_irq()
762  * xa_insert() - Store this entry in the XArray unless another entry is
766  * @entry: New entry.
769  * Inserting a NULL entry will store a reserved entry (like xa_reserve())
770  * if no entry is present.  Inserting will fail if a reserved entry is
775  * Return: 0 if the store succeeded.  -EBUSY if another entry was present.
779 		unsigned long index, void *entry, gfp_t gfp)  in xa_insert()  argument
785 	err = __xa_insert(xa, index, entry, gfp);  in xa_insert()
792  * xa_insert_bh() - Store this entry in the XArray unless another entry is
796  * @entry: New entry.
799  * Inserting a NULL entry will store a reserved entry (like xa_reserve())
800  * if no entry is present.  Inserting will fail if a reserved entry is
805  * Return: 0 if the store succeeded.  -EBUSY if another entry was present.
809 		unsigned long index, void *entry, gfp_t gfp)  in xa_insert_bh()  argument
815 	err = __xa_insert(xa, index, entry, gfp);  in xa_insert_bh()
822  * xa_insert_irq() - Store this entry in the XArray unless another entry is
826  * @entry: New entry.
829  * Inserting a NULL entry will store a reserved entry (like xa_reserve())
830  * if no entry is present.  Inserting will fail if a reserved entry is
835  * Return: 0 if the store succeeded.  -EBUSY if another entry was present.
839 		unsigned long index, void *entry, gfp_t gfp)  in xa_insert_irq()  argument
845 	err = __xa_insert(xa, index, entry, gfp);  in xa_insert_irq()
852  * xa_alloc() - Find somewhere to store this entry in the XArray.
855  * @entry: New entry.
859  * Finds an empty entry in @xa between @limit.min and @limit.max,
860  * stores the index into the @id pointer, then stores the entry at
872 		void *entry, struct xa_limit limit, gfp_t gfp)  in xa_alloc()  argument
878 	err = __xa_alloc(xa, id, entry, limit, gfp);  in xa_alloc()
885  * xa_alloc_bh() - Find somewhere to store this entry in the XArray.
888  * @entry: New entry.
892  * Finds an empty entry in @xa between @limit.min and @limit.max,
893  * stores the index into the @id pointer, then stores the entry at
905 		void *entry, struct xa_limit limit, gfp_t gfp)  in xa_alloc_bh()  argument
911 	err = __xa_alloc(xa, id, entry, limit, gfp);  in xa_alloc_bh()
918  * xa_alloc_irq() - Find somewhere to store this entry in the XArray.
921  * @entry: New entry.
925  * Finds an empty entry in @xa between @limit.min and @limit.max,
926  * stores the index into the @id pointer, then stores the entry at
938 		void *entry, struct xa_limit limit, gfp_t gfp)  in xa_alloc_irq()  argument
944 	err = __xa_alloc(xa, id, entry, limit, gfp);  in xa_alloc_irq()
951  * xa_alloc_cyclic() - Find somewhere to store this entry in the XArray.
954  * @entry: New entry.
959  * Finds an empty entry in @xa between @limit.min and @limit.max,
960  * stores the index into the @id pointer, then stores the entry at
962  * The search for an empty entry will start at @next and will wrap
976 static inline int xa_alloc_cyclic(struct xarray *xa, u32 *id, void *entry,  in xa_alloc_cyclic()  argument
983 	err = __xa_alloc_cyclic(xa, id, entry, limit, next, gfp);  in xa_alloc_cyclic()
990  * xa_alloc_cyclic_bh() - Find somewhere to store this entry in the XArray.
993  * @entry: New entry.
998  * Finds an empty entry in @xa between @limit.min and @limit.max,
999  * stores the index into the @id pointer, then stores the entry at
1001  * The search for an empty entry will start at @next and will wrap
1015 static inline int xa_alloc_cyclic_bh(struct xarray *xa, u32 *id, void *entry,  in xa_alloc_cyclic_bh()  argument
1022 	err = __xa_alloc_cyclic(xa, id, entry, limit, next, gfp);  in xa_alloc_cyclic_bh()
1029  * xa_alloc_cyclic_irq() - Find somewhere to store this entry in the XArray.
1032  * @entry: New entry.
1037  * Finds an empty entry in @xa between @limit.min and @limit.max,
1038  * stores the index into the @id pointer, then stores the entry at
1040  * The search for an empty entry will start at @next and will wrap
1054 static inline int xa_alloc_cyclic_irq(struct xarray *xa, u32 *id, void *entry,  in xa_alloc_cyclic_irq()  argument
1061 	err = __xa_alloc_cyclic(xa, id, entry, limit, next, gfp);  in xa_alloc_cyclic_irq()
1073  * Ensures there is somewhere to store an entry at @index in the array.
1075  * nothing.  If there was nothing there, the entry is marked as reserved.
1076  * Loading from a reserved entry returns a %NULL pointer.
1078  * If you do not use the entry that you have reserved, call xa_release()
1128  * xa_release() - Release a reserved entry.
1130  * @index: Index of entry.
1133  * reservation.  If the entry at @index has been stored to, this function
1163  * whether that is a value entry, a retry entry, a user pointer,
1164  * a sibling entry or a pointer to the next level of the tree.
1166  * either a value entry or a sibling of a value entry.
1171 	unsigned char	count;		/* Total entry count */
1172 	unsigned char	nr_values;	/* Value entry count */
1262 static inline struct xa_node *xa_to_node(const void *entry)  in xa_to_node()  argument
1264 	return (struct xa_node *)((unsigned long)entry - 2);  in xa_to_node()
1268 static inline bool xa_is_node(const void *entry)  in xa_is_node()  argument
1270 	return xa_is_internal(entry) && (unsigned long)entry > 4096;  in xa_is_node()
1280 static inline unsigned long xa_to_sibling(const void *entry)  in xa_to_sibling()  argument
1282 	return xa_to_internal(entry);  in xa_to_sibling()
1286  * xa_is_sibling() - Is the entry a sibling entry?
1287  * @entry: Entry retrieved from the XArray
1289  * Return: %true if the entry is a sibling entry.
1291 static inline bool xa_is_sibling(const void *entry)  in xa_is_sibling()  argument
1293 	return IS_ENABLED(CONFIG_XARRAY_MULTI) && xa_is_internal(entry) &&  in xa_is_sibling()
1294 		(entry < xa_mk_sibling(XA_CHUNK_SIZE - 1));  in xa_is_sibling()
1300  * xa_is_retry() - Is the entry a retry entry?
1301  * @entry: Entry retrieved from the XArray
1303  * Return: %true if the entry is a retry entry.
1305 static inline bool xa_is_retry(const void *entry)  in xa_is_retry()  argument
1307 	return unlikely(entry == XA_RETRY_ENTRY);  in xa_is_retry()
1311  * xa_is_advanced() - Is the entry only permitted for the advanced API?
1312  * @entry: Entry to be stored in the XArray.
1314  * Return: %true if the entry cannot be stored by the normal API.
1316 static inline bool xa_is_advanced(const void *entry)  in xa_is_advanced()  argument
1318 	return xa_is_internal(entry) && (entry <= XA_RETRY_ENTRY);  in xa_is_advanced()
1347  * single entry in the array at index 0, there are no allocated xa_nodes to
1404  * @order: Order of entry.
1523  * @entry: Entry from xarray.
1525  * The advanced functions may sometimes return an internal entry, such as
1526  * a retry entry or a zero entry.  This function sets up the @xas to restart
1532 static inline bool xas_retry(struct xa_state *xas, const void *entry)  in xas_retry()  argument
1534 	if (xa_is_zero(entry))  in xas_retry()
1536 	if (!xa_is_retry(entry))  in xas_retry()
1543 void *xas_store(struct xa_state *, void *entry);
1562 void xas_split(struct xa_state *, void *entry, unsigned int order);
1563 void xas_split_alloc(struct xa_state *, void *entry, unsigned int order, gfp_t);
1564 void xas_try_split(struct xa_state *xas, void *entry, unsigned int order);
1577 static inline void xas_split(struct xa_state *xas, void *entry,  in xas_split()  argument
1580 	xas_store(xas, entry);  in xas_split()
1583 static inline void xas_split_alloc(struct xa_state *xas, void *entry,  in xas_split_alloc()  argument
1588 static inline void xas_try_split(struct xa_state *xas, void *entry,  in xas_try_split()  argument
1601  * xas_reload() - Refetch an entry from the xarray.
1604  * Use this function to check that a previously loaded entry still has
1612  * Return: The entry at this location in the xarray.
1617 	void *entry;  in xas_reload()  local
1624 		entry = xa_entry(xas->xa, node, offset);  in xas_reload()
1625 		if (!xa_is_sibling(entry))  in xas_reload()
1626 			return entry;  in xas_reload()
1627 		offset = xa_to_sibling(entry);  in xas_reload()
1652  * @index: Index of last sibling entry.
1654  * Move the operation state to refer to the last sibling entry.
1657  * want to move to an index which is not part of this entry.
1668  * xas_set_order() - Set up XArray operation state for a multislot entry.
1671  * @order: Entry occupies 2^@order indices.
1707  * xas_next_entry() - Advance iterator to next present entry.
1715  * Return: The next present entry after the one currently referred to by @xas.
1720 	void *entry;  in xas_next_entry()  local
1731 		entry = xa_entry(xas->xa, node, xas->xa_offset + 1);  in xas_next_entry()
1732 		if (unlikely(xa_is_internal(entry)))  in xas_next_entry()
1736 	} while (!entry);  in xas_next_entry()
1738 	return entry;  in xas_next_entry()
1763  * xas_next_marked() - Advance iterator to next marked entry.
1772  * Return: The next marked entry after the one currently referred to by @xas.
1778 	void *entry;  in xas_next_marked()  local
1790 	entry = xa_entry(xas->xa, node, offset);  in xas_next_marked()
1791 	if (!entry)  in xas_next_marked()
1793 	return entry;  in xas_next_marked()
1807  * @entry: Entry retrieved from the array.
1810  * The loop body will be executed for each entry present in the xarray
1811  * between the current xas position and @max.  @entry will be set to
1812  * the entry retrieved from the xarray.  It is safe to delete entries
1817 #define xas_for_each(xas, entry, max) \  argument
1818 	for (entry = xas_find(xas, max); entry; \
1819 	     entry = xas_next_entry(xas, max))
1824  * @entry: Entry retrieved from the array.
1828  * The loop body will be executed for each marked entry in the xarray
1829  * between the current xas position and @max.  @entry will be set to
1830  * the entry retrieved from the xarray.  It is safe to delete entries
1835 #define xas_for_each_marked(xas, entry, max, mark) \  argument
1836 	for (entry = xas_find_marked(xas, max, mark); entry; \
1837 	     entry = xas_next_marked(xas, max, mark))
1842  * @entry: Entry retrieved from the array.
1844  * The loop body will be executed for each entry in the XArray that
1846  * normally, @entry will be %NULL.  The user may break out of the loop,
1847  * which will leave @entry set to the conflicting entry.  The caller
1851 #define xas_for_each_conflict(xas, entry) \  argument
1852 	while ((entry = xas_find_conflict(xas)))
1870  * Return: The entry at the new index.  This may be %NULL or an internal
1871  * entry.
1899  * Return: The entry at the new index.  This may be %NULL or an internal
1900  * entry.