22  * The bottom two bits of the entry determine how the XArray interprets
25  * 00: Pointer entry
26  * 10: Internal entry
27  * x1: Value entry or tagged pointer
35  * 256: Retry entry
36  * 257: Zero entry
46  * xa_mk_value() - Create an XArray entry from an integer.
50  * Return: An entry suitable for storing in the XArray.
59  * xa_to_value() - Get value stored in an XArray entry.
60  * @entry: XArray entry.
63  * Return: The value stored in the XArray entry.
65 static inline unsigned long xa_to_value(const void *entry)  in xa_to_value()  argument
67 	return (unsigned long)entry >> 1;  in xa_to_value()
71  * xa_is_value() - Determine if an entry is a value.
72  * @entry: XArray entry.
75  * Return: True if the entry is a value, false if it is a pointer.
77 static inline bool xa_is_value(const void *entry)  in xa_is_value()  argument
79 	return (unsigned long)entry & 1;  in xa_is_value()
83  * xa_tag_pointer() - Create an XArray entry for a tagged pointer.
93  * Return: An XArray entry.
101  * xa_untag_pointer() - Turn an XArray entry into a plain pointer.
102  * @entry: XArray entry.
110 static inline void *xa_untag_pointer(void *entry)  in xa_untag_pointer()  argument
112 	return (void *)((unsigned long)entry & ~3UL);  in xa_untag_pointer()
116  * xa_pointer_tag() - Get the tag stored in an XArray entry.
117  * @entry: XArray entry.
125 static inline unsigned int xa_pointer_tag(void *entry)  in xa_pointer_tag()  argument
127 	return (unsigned long)entry & 3UL;  in xa_pointer_tag()
131  * xa_mk_internal() - Create an internal entry.
132  * @v: Value to turn into an internal entry.
136  * is used for the retry entry.  257 is used for the reserved / zero entry.
141  * Return: An XArray internal entry corresponding to this value.
149  * xa_to_internal() - Extract the value from an internal entry.
150  * @entry: XArray entry.
153  * Return: The value which was stored in the internal entry.
155 static inline unsigned long xa_to_internal(const void *entry)  in xa_to_internal()  argument
157 	return (unsigned long)entry >> 2;  in xa_to_internal()
161  * xa_is_internal() - Is the entry an internal entry?
162  * @entry: XArray entry.
165  * Return: %true if the entry is an internal entry.
167 static inline bool xa_is_internal(const void *entry)  in xa_is_internal()  argument
169 	return ((unsigned long)entry & 3) == 2;  in xa_is_internal()
175  * xa_is_zero() - Is the entry a zero entry?
176  * @entry: Entry retrieved from the XArray
179  * a zero entry.  You can only see zero entries by using the advanced API.
181  * Return: %true if the entry is a zero entry.
183 static inline bool xa_is_zero(const void *entry)  in xa_is_zero()  argument
185 	return unlikely(entry == XA_ZERO_ENTRY);  in xa_is_zero()
190  * @entry: Result from calling an XArray function
197  * Return: %true if the entry indicates an error.
199 static inline bool xa_is_err(const void *entry)  in xa_is_err()  argument
201 	return unlikely(xa_is_internal(entry) &&  in xa_is_err()
202 			entry >= xa_mk_internal(-MAX_ERRNO));  in xa_is_err()
207  * @entry: Result from calling an XArray function.
217 static inline int xa_err(void *entry)  in xa_err()  argument
220 	if (xa_is_err(entry))  in xa_err()
221 		return (long)entry >> 2;  in xa_err()
288  * If the only non-NULL entry in the array is at index 0, @xa_head is that
289  * entry.  If any other entry in the array is non-NULL, @xa_head points
348 void *xa_store(struct xarray *, unsigned long index, void *entry, gfp_t);
351 			void *entry, gfp_t);
407  * xa_marked() - Inquire whether any entry in this array has a mark set
412  * Return: %true if any entry has this mark set.
422  * @index: Index of @entry.
423  * @entry: Entry retrieved from array.
427  * During the iteration, @entry will have the value of the entry stored
430  * during the iteration.  At the end of the iteration, @entry will be set
436  * xa_for_each_range() will spin if it hits a retry entry; if you intend to
443 #define xa_for_each_range(xa, index, entry, start, last)		\  argument
445 	     entry = xa_find(xa, &index, last, XA_PRESENT);		\
446 	     entry;							\
447 	     entry = xa_find_after(xa, &index, last, XA_PRESENT))
452  * @index: Index of @entry.
453  * @entry: Entry retrieved from array.
456  * During the iteration, @entry will have the value of the entry stored
459  * during the iteration.  At the end of the iteration, @entry will be set
465  * xa_for_each_start() will spin if it hits a retry entry; if you intend to
472 #define xa_for_each_start(xa, index, entry, start) \  argument
473 	xa_for_each_range(xa, index, entry, start, ULONG_MAX)
478  * @index: Index of @entry.
479  * @entry: Entry retrieved from array.
481  * During the iteration, @entry will have the value of the entry stored
484  * iteration.  At the end of the iteration, @entry will be set to NULL and
490  * will spin if it hits a retry entry; if you intend to see retry entries,
496 #define xa_for_each(xa, index, entry) \  argument
497 	xa_for_each_start(xa, index, entry, 0)
502  * @index: Index of @entry.
503  * @entry: Entry retrieved from array.
506  * During the iteration, @entry will have the value of the entry stored
510  * during the iteration.  At the end of the iteration, @entry will be set to
516  * xa_for_each_marked() will spin if it hits a retry entry; if you intend to
523 #define xa_for_each_marked(xa, index, entry, filter) \  argument
524 	for (index = 0, entry = xa_find(xa, &index, ULONG_MAX, filter); \
525 	     entry; entry = xa_find_after(xa, &index, ULONG_MAX, filter))
555 void *__xa_store(struct xarray *, unsigned long index, void *entry, gfp_t);
557 		void *entry, gfp_t);
559 		void *entry, gfp_t);
560 int __must_check __xa_alloc(struct xarray *, u32 *id, void *entry,
562 int __must_check __xa_alloc_cyclic(struct xarray *, u32 *id, void *entry,
568  * xa_store_bh() - Store this entry in the XArray.
571  * @entry: New entry.
579  * Return: The old entry at this index or xa_err() if an error happened.
582 		void *entry, gfp_t gfp)  in xa_store_bh()  argument
587 	curr = __xa_store(xa, index, entry, gfp);  in xa_store_bh()
594  * xa_store_irq() - Store this entry in the XArray.
597  * @entry: New entry.
605  * Return: The old entry at this index or xa_err() if an error happened.
608 		void *entry, gfp_t gfp)  in xa_store_irq()  argument
613 	curr = __xa_store(xa, index, entry, gfp);  in xa_store_irq()
620  * xa_erase_bh() - Erase this entry from the XArray.
622  * @index: Index of entry.
625  * If the index is part of a multi-index entry, all indices will be erased
626  * and none of the entries will be part of a multi-index entry.
630  * Return: The entry which used to be at this index.
634 	void *entry;  in xa_erase_bh()  local
637 	entry = __xa_erase(xa, index);  in xa_erase_bh()
640 	return entry;  in xa_erase_bh()
644  * xa_erase_irq() - Erase this entry from the XArray.
646  * @index: Index of entry.
649  * If the index is part of a multi-index entry, all indices will be erased
650  * and none of the entries will be part of a multi-index entry.
654  * Return: The entry which used to be at this index.
658 	void *entry;  in xa_erase_irq()  local
661 	entry = __xa_erase(xa, index);  in xa_erase_irq()
664 	return entry;  in xa_erase_irq()
668  * xa_cmpxchg() - Conditionally replace an entry in the XArray.
672  * @entry: New value to place in array.
675  * If the entry at @index is the same as @old, replace it with @entry.
683 			void *old, void *entry, gfp_t gfp)  in xa_cmpxchg()  argument
688 	curr = __xa_cmpxchg(xa, index, old, entry, gfp);  in xa_cmpxchg()
695  * xa_cmpxchg_bh() - Conditionally replace an entry in the XArray.
699  * @entry: New value to place in array.
710 			void *old, void *entry, gfp_t gfp)  in xa_cmpxchg_bh()  argument
715 	curr = __xa_cmpxchg(xa, index, old, entry, gfp);  in xa_cmpxchg_bh()
722  * xa_cmpxchg_irq() - Conditionally replace an entry in the XArray.
726  * @entry: New value to place in array.
737 			void *old, void *entry, gfp_t gfp)  in xa_cmpxchg_irq()  argument
742 	curr = __xa_cmpxchg(xa, index, old, entry, gfp);  in xa_cmpxchg_irq()
749  * xa_insert() - Store this entry in the XArray unless another entry is
753  * @entry: New entry.
756  * Inserting a NULL entry will store a reserved entry (like xa_reserve())
757  * if no entry is present.  Inserting will fail if a reserved entry is
762  * Return: 0 if the store succeeded.  -EBUSY if another entry was present.
766 		unsigned long index, void *entry, gfp_t gfp)  in xa_insert()  argument
771 	err = __xa_insert(xa, index, entry, gfp);  in xa_insert()
778  * xa_insert_bh() - Store this entry in the XArray unless another entry is
782  * @entry: New entry.
785  * Inserting a NULL entry will store a reserved entry (like xa_reserve())
786  * if no entry is present.  Inserting will fail if a reserved entry is
791  * Return: 0 if the store succeeded.  -EBUSY if another entry was present.
795 		unsigned long index, void *entry, gfp_t gfp)  in xa_insert_bh()  argument
800 	err = __xa_insert(xa, index, entry, gfp);  in xa_insert_bh()
807  * xa_insert_irq() - Store this entry in the XArray unless another entry is
811  * @entry: New entry.
814  * Inserting a NULL entry will store a reserved entry (like xa_reserve())
815  * if no entry is present.  Inserting will fail if a reserved entry is
820  * Return: 0 if the store succeeded.  -EBUSY if another entry was present.
824 		unsigned long index, void *entry, gfp_t gfp)  in xa_insert_irq()  argument
829 	err = __xa_insert(xa, index, entry, gfp);  in xa_insert_irq()
836  * xa_alloc() - Find somewhere to store this entry in the XArray.
839  * @entry: New entry.
843  * Finds an empty entry in @xa between @limit.min and @limit.max,
844  * stores the index into the @id pointer, then stores the entry at
853 		void *entry, struct xa_limit limit, gfp_t gfp)  in xa_alloc()  argument
858 	err = __xa_alloc(xa, id, entry, limit, gfp);  in xa_alloc()
865  * xa_alloc_bh() - Find somewhere to store this entry in the XArray.
868  * @entry: New entry.
872  * Finds an empty entry in @xa between @limit.min and @limit.max,
873  * stores the index into the @id pointer, then stores the entry at
882 		void *entry, struct xa_limit limit, gfp_t gfp)  in xa_alloc_bh()  argument
887 	err = __xa_alloc(xa, id, entry, limit, gfp);  in xa_alloc_bh()
894  * xa_alloc_irq() - Find somewhere to store this entry in the XArray.
897  * @entry: New entry.
901  * Finds an empty entry in @xa between @limit.min and @limit.max,
902  * stores the index into the @id pointer, then stores the entry at
911 		void *entry, struct xa_limit limit, gfp_t gfp)  in xa_alloc_irq()  argument
916 	err = __xa_alloc(xa, id, entry, limit, gfp);  in xa_alloc_irq()
923  * xa_alloc_cyclic() - Find somewhere to store this entry in the XArray.
926  * @entry: New entry.
931  * Finds an empty entry in @xa between @limit.min and @limit.max,
932  * stores the index into the @id pointer, then stores the entry at
934  * The search for an empty entry will start at @next and will wrap
943 static inline int xa_alloc_cyclic(struct xarray *xa, u32 *id, void *entry,  in xa_alloc_cyclic()  argument
949 	err = __xa_alloc_cyclic(xa, id, entry, limit, next, gfp);  in xa_alloc_cyclic()
956  * xa_alloc_cyclic_bh() - Find somewhere to store this entry in the XArray.
959  * @entry: New entry.
964  * Finds an empty entry in @xa between @limit.min and @limit.max,
965  * stores the index into the @id pointer, then stores the entry at
967  * The search for an empty entry will start at @next and will wrap
976 static inline int xa_alloc_cyclic_bh(struct xarray *xa, u32 *id, void *entry,  in xa_alloc_cyclic_bh()  argument
982 	err = __xa_alloc_cyclic(xa, id, entry, limit, next, gfp);  in xa_alloc_cyclic_bh()
989  * xa_alloc_cyclic_irq() - Find somewhere to store this entry in the XArray.
992  * @entry: New entry.
997  * Finds an empty entry in @xa between @limit.min and @limit.max,
998  * stores the index into the @id pointer, then stores the entry at
1000  * The search for an empty entry will start at @next and will wrap
1009 static inline int xa_alloc_cyclic_irq(struct xarray *xa, u32 *id, void *entry,  in xa_alloc_cyclic_irq()  argument
1015 	err = __xa_alloc_cyclic(xa, id, entry, limit, next, gfp);  in xa_alloc_cyclic_irq()
1027  * Ensures there is somewhere to store an entry at @index in the array.
1029  * nothing.  If there was nothing there, the entry is marked as reserved.
1030  * Loading from a reserved entry returns a %NULL pointer.
1032  * If you do not use the entry that you have reserved, call xa_release()
1082  * xa_release() - Release a reserved entry.
1084  * @index: Index of entry.
1087  * reservation.  If the entry at @index has been stored to, this function
1117  * whether that is a value entry, a retry entry, a user pointer,
1118  * a sibling entry or a pointer to the next level of the tree.
1120  * either a value entry or a sibling of a value entry.
1125 	unsigned char	count;		/* Total entry count */
1126 	unsigned char	nr_values;	/* Value entry count */
1216 static inline struct xa_node *xa_to_node(const void *entry)  in xa_to_node()  argument
1218 	return (struct xa_node *)((unsigned long)entry - 2);  in xa_to_node()
1222 static inline bool xa_is_node(const void *entry)  in xa_is_node()  argument
1224 	return xa_is_internal(entry) && (unsigned long)entry > 4096;  in xa_is_node()
1234 static inline unsigned long xa_to_sibling(const void *entry)  in xa_to_sibling()  argument
1236 	return xa_to_internal(entry);  in xa_to_sibling()
1240  * xa_is_sibling() - Is the entry a sibling entry?
1241  * @entry: Entry retrieved from the XArray
1243  * Return: %true if the entry is a sibling entry.
1245 static inline bool xa_is_sibling(const void *entry)  in xa_is_sibling()  argument
1247 	return IS_ENABLED(CONFIG_XARRAY_MULTI) && xa_is_internal(entry) &&  in xa_is_sibling()
1248 		(entry < xa_mk_sibling(XA_CHUNK_SIZE - 1));  in xa_is_sibling()
1254  * xa_is_retry() - Is the entry a retry entry?
1255  * @entry: Entry retrieved from the XArray
1257  * Return: %true if the entry is a retry entry.
1259 static inline bool xa_is_retry(const void *entry)  in xa_is_retry()  argument
1261 	return unlikely(entry == XA_RETRY_ENTRY);  in xa_is_retry()
1265  * xa_is_advanced() - Is the entry only permitted for the advanced API?
1266  * @entry: Entry to be stored in the XArray.
1268  * Return: %true if the entry cannot be stored by the normal API.
1270 static inline bool xa_is_advanced(const void *entry)  in xa_is_advanced()  argument
1272 	return xa_is_internal(entry) && (entry <= XA_RETRY_ENTRY);  in xa_is_advanced()
1301  * single entry in the array at index 0, there are no allocated xa_nodes to
1356  * @order: Order of entry.
1475  * @entry: Entry from xarray.
1477  * The advanced functions may sometimes return an internal entry, such as
1478  * a retry entry or a zero entry.  This function sets up the @xas to restart
1484 static inline bool xas_retry(struct xa_state *xas, const void *entry)  in xas_retry()  argument
1486 	if (xa_is_zero(entry))  in xas_retry()
1488 	if (!xa_is_retry(entry))  in xas_retry()
1495 void *xas_store(struct xa_state *, void *entry);
1512 void xas_split(struct xa_state *, void *entry, unsigned int order);
1513 void xas_split_alloc(struct xa_state *, void *entry, unsigned int order, gfp_t);
1520 static inline void xas_split(struct xa_state *xas, void *entry,  in xas_split()  argument
1523 	xas_store(xas, entry);  in xas_split()
1526 static inline void xas_split_alloc(struct xa_state *xas, void *entry,  in xas_split_alloc()  argument
1533  * xas_reload() - Refetch an entry from the xarray.
1536  * Use this function to check that a previously loaded entry still has
1544  * Return: The entry at this location in the xarray.
1549 	void *entry;  in xas_reload()  local
1556 		entry = xa_entry(xas->xa, node, offset);  in xas_reload()
1557 		if (!xa_is_sibling(entry))  in xas_reload()
1558 			return entry;  in xas_reload()
1559 		offset = xa_to_sibling(entry);  in xas_reload()
1582  * xas_set_order() - Set up XArray operation state for a multislot entry.
1585  * @order: Entry occupies 2^@order indices.
1615  * xas_next_entry() - Advance iterator to next present entry.
1623  * Return: The next present entry after the one currently referred to by @xas.
1628 	void *entry;  in xas_next_entry()  local
1639 		entry = xa_entry(xas->xa, node, xas->xa_offset + 1);  in xas_next_entry()
1640 		if (unlikely(xa_is_internal(entry)))  in xas_next_entry()
1644 	} while (!entry);  in xas_next_entry()
1646 	return entry;  in xas_next_entry()
1671  * xas_next_marked() - Advance iterator to next marked entry.
1680  * Return: The next marked entry after the one currently referred to by @xas.
1686 	void *entry;  in xas_next_marked()  local
1698 	entry = xa_entry(xas->xa, node, offset);  in xas_next_marked()
1699 	if (!entry)  in xas_next_marked()
1701 	return entry;  in xas_next_marked()
1715  * @entry: Entry retrieved from the array.
1718  * The loop body will be executed for each entry present in the xarray
1719  * between the current xas position and @max.  @entry will be set to
1720  * the entry retrieved from the xarray.  It is safe to delete entries
1725 #define xas_for_each(xas, entry, max) \  argument
1726 	for (entry = xas_find(xas, max); entry; \
1727 	     entry = xas_next_entry(xas, max))
1732  * @entry: Entry retrieved from the array.
1736  * The loop body will be executed for each marked entry in the xarray
1737  * between the current xas position and @max.  @entry will be set to
1738  * the entry retrieved from the xarray.  It is safe to delete entries
1743 #define xas_for_each_marked(xas, entry, max, mark) \  argument
1744 	for (entry = xas_find_marked(xas, max, mark); entry; \
1745 	     entry = xas_next_marked(xas, max, mark))
1750  * @entry: Entry retrieved from the array.
1752  * The loop body will be executed for each entry in the XArray that
1754  * normally, @entry will be %NULL.  The user may break out of the loop,
1755  * which will leave @entry set to the conflicting entry.  The caller
1759 #define xas_for_each_conflict(xas, entry) \  argument
1760 	while ((entry = xas_find_conflict(xas)))
1778  * Return: The entry at the new index.  This may be %NULL or an internal
1779  * entry.
1807  * Return: The entry at the new index.  This may be %NULL or an internal
1808  * entry.