34  * 0-62: Sibling entries
54 	WARN_ON((long)v < 0);  in xa_mk_value()
85  * @tag: Tag value (0, 1 or 3).
88  * of storing value entries.  Three tags are available (0, 1 and 3).
134  * Internal entries are used for a number of purposes.  Entries 0-255 are
135  * used for sibling entries (only 0-62 are used by the current code).  256
211  * the errno from the pointer value, or returns 0 if the pointer does not
215  * Return: A negative errno or 0.
222 	return 0;  in xa_err()
233  * * xa_limit_32b	- [0 - UINT_MAX]
234  * * xa_limit_31b	- [0 - INT_MAX]
243 #define xa_limit_32b	XA_LIMIT(0, UINT_MAX)
244 #define xa_limit_31b	XA_LIMIT(0, INT_MAX)
247 #define XA_MARK_0		((__force xa_mark_t)0U)
272 /* ALLOC is for a normal 0-based alloc.  ALLOC1 is for an 1-based alloc */
288  * If the only non-NULL entry in the array is at index 0, @xa_head is that
327 #define DEFINE_XARRAY(name) DEFINE_XARRAY_FLAGS(name, 0)
330  * DEFINE_XARRAY_ALLOC() - Define an XArray which allocates IDs starting at 0.
355 void *xa_find(struct xarray *xa, unsigned long *index,
357 void *xa_find_after(struct xarray *xa, unsigned long *index,
365  * @xa: XArray.
374 static inline void xa_init_flags(struct xarray *xa, gfp_t flags)  in xa_init_flags()  argument
376 	spin_lock_init(&xa->xa_lock);  in xa_init_flags()
377 	xa->xa_flags = flags;  in xa_init_flags()
378 	xa->xa_head = NULL;  in xa_init_flags()
383  * @xa: XArray.
389 static inline void xa_init(struct xarray *xa)  in xa_init()  argument
391 	xa_init_flags(xa, 0);  in xa_init()
396  * @xa: XArray.
401 static inline bool xa_empty(const struct xarray *xa)  in xa_empty()  argument
403 	return xa->xa_head == NULL;  in xa_empty()
408  * @xa: Array
414 static inline bool xa_marked(const struct xarray *xa, xa_mark_t mark)  in xa_marked()  argument
416 	return xa->xa_flags & XA_FLAGS_MARK(mark);  in xa_marked()
421  * @xa: XArray.
428  * in @xa at @index.  You may modify @index during the iteration if you
443 #define xa_for_each_range(xa, index, entry, start, last)		\  argument
445 	     entry = xa_find(xa, &index, last, XA_PRESENT);		\
447 	     entry = xa_find_after(xa, &index, last, XA_PRESENT))
451  * @xa: XArray.
457  * in @xa at @index.  You may modify @index during the iteration if you
472 #define xa_for_each_start(xa, index, entry, start) \  argument
473 	xa_for_each_range(xa, index, entry, start, ULONG_MAX)
477  * @xa: XArray.
482  * in @xa at @index.  You may modify @index during the iteration if you want
496 #define xa_for_each(xa, index, entry) \  argument
497 	xa_for_each_start(xa, index, entry, 0)
501  * @xa: XArray.
507  * in @xa at @index.  The iteration will skip all entries in the array
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))
527 #define xa_trylock(xa)		spin_trylock(&(xa)->xa_lock)  argument
528 #define xa_lock(xa)		spin_lock(&(xa)->xa_lock)  argument
529 #define xa_unlock(xa)		spin_unlock(&(xa)->xa_lock)  argument
530 #define xa_lock_bh(xa)		spin_lock_bh(&(xa)->xa_lock)  argument
531 #define xa_unlock_bh(xa)	spin_unlock_bh(&(xa)->xa_lock)  argument
532 #define xa_lock_irq(xa)		spin_lock_irq(&(xa)->xa_lock)  argument
533 #define xa_unlock_irq(xa)	spin_unlock_irq(&(xa)->xa_lock)  argument
534 #define xa_lock_irqsave(xa, flags) \  argument
535 				spin_lock_irqsave(&(xa)->xa_lock, flags)
536 #define xa_unlock_irqrestore(xa, flags) \  argument
537 				spin_unlock_irqrestore(&(xa)->xa_lock, flags)
538 #define xa_lock_nested(xa, subclass) \  argument
539 				spin_lock_nested(&(xa)->xa_lock, subclass)
540 #define xa_lock_bh_nested(xa, subclass) \  argument
541 				spin_lock_bh_nested(&(xa)->xa_lock, subclass)
542 #define xa_lock_irq_nested(xa, subclass) \  argument
543 				spin_lock_irq_nested(&(xa)->xa_lock, subclass)
544 #define xa_lock_irqsave_nested(xa, flags, subclass) \  argument
545 		spin_lock_irqsave_nested(&(xa)->xa_lock, flags, subclass)
569  * @xa: XArray.
581 static inline void *xa_store_bh(struct xarray *xa, unsigned long index,  in xa_store_bh()  argument
586 	xa_lock_bh(xa);  in xa_store_bh()
587 	curr = __xa_store(xa, index, entry, gfp);  in xa_store_bh()
588 	xa_unlock_bh(xa);  in xa_store_bh()
595  * @xa: XArray.
607 static inline void *xa_store_irq(struct xarray *xa, unsigned long index,  in xa_store_irq()  argument
612 	xa_lock_irq(xa);  in xa_store_irq()
613 	curr = __xa_store(xa, index, entry, gfp);  in xa_store_irq()
614 	xa_unlock_irq(xa);  in xa_store_irq()
621  * @xa: XArray.
632 static inline void *xa_erase_bh(struct xarray *xa, unsigned long index)  in xa_erase_bh()  argument
636 	xa_lock_bh(xa);  in xa_erase_bh()
637 	entry = __xa_erase(xa, index);  in xa_erase_bh()
638 	xa_unlock_bh(xa);  in xa_erase_bh()
645  * @xa: XArray.
656 static inline void *xa_erase_irq(struct xarray *xa, unsigned long index)  in xa_erase_irq()  argument
660 	xa_lock_irq(xa);  in xa_erase_irq()
661 	entry = __xa_erase(xa, index);  in xa_erase_irq()
662 	xa_unlock_irq(xa);  in xa_erase_irq()
669  * @xa: XArray.
682 static inline void *xa_cmpxchg(struct xarray *xa, unsigned long index,  in xa_cmpxchg()  argument
687 	xa_lock(xa);  in xa_cmpxchg()
688 	curr = __xa_cmpxchg(xa, index, old, entry, gfp);  in xa_cmpxchg()
689 	xa_unlock(xa);  in xa_cmpxchg()
696  * @xa: XArray.
709 static inline void *xa_cmpxchg_bh(struct xarray *xa, unsigned long index,  in xa_cmpxchg_bh()  argument
714 	xa_lock_bh(xa);  in xa_cmpxchg_bh()
715 	curr = __xa_cmpxchg(xa, index, old, entry, gfp);  in xa_cmpxchg_bh()
716 	xa_unlock_bh(xa);  in xa_cmpxchg_bh()
723  * @xa: XArray.
736 static inline void *xa_cmpxchg_irq(struct xarray *xa, unsigned long index,  in xa_cmpxchg_irq()  argument
741 	xa_lock_irq(xa);  in xa_cmpxchg_irq()
742 	curr = __xa_cmpxchg(xa, index, old, entry, gfp);  in xa_cmpxchg_irq()
743 	xa_unlock_irq(xa);  in xa_cmpxchg_irq()
751  * @xa: XArray.
762  * Return: 0 if the store succeeded.  -EBUSY if another entry was present.
765 static inline int __must_check xa_insert(struct xarray *xa,  in xa_insert()  argument
770 	xa_lock(xa);  in xa_insert()
771 	err = __xa_insert(xa, index, entry, gfp);  in xa_insert()
772 	xa_unlock(xa);  in xa_insert()
780  * @xa: XArray.
791  * Return: 0 if the store succeeded.  -EBUSY if another entry was present.
794 static inline int __must_check xa_insert_bh(struct xarray *xa,  in xa_insert_bh()  argument
799 	xa_lock_bh(xa);  in xa_insert_bh()
800 	err = __xa_insert(xa, index, entry, gfp);  in xa_insert_bh()
801 	xa_unlock_bh(xa);  in xa_insert_bh()
809  * @xa: XArray.
820  * Return: 0 if the store succeeded.  -EBUSY if another entry was present.
823 static inline int __must_check xa_insert_irq(struct xarray *xa,  in xa_insert_irq()  argument
828 	xa_lock_irq(xa);  in xa_insert_irq()
829 	err = __xa_insert(xa, index, entry, gfp);  in xa_insert_irq()
830 	xa_unlock_irq(xa);  in xa_insert_irq()
837  * @xa: XArray.
843  * Finds an empty entry in @xa between @limit.min and @limit.max,
849  * Return: 0 on success, -ENOMEM if memory could not be allocated or
852 static inline __must_check int xa_alloc(struct xarray *xa, u32 *id,  in xa_alloc()  argument
857 	xa_lock(xa);  in xa_alloc()
858 	err = __xa_alloc(xa, id, entry, limit, gfp);  in xa_alloc()
859 	xa_unlock(xa);  in xa_alloc()
866  * @xa: XArray.
872  * Finds an empty entry in @xa between @limit.min and @limit.max,
878  * Return: 0 on success, -ENOMEM if memory could not be allocated or
881 static inline int __must_check xa_alloc_bh(struct xarray *xa, u32 *id,  in xa_alloc_bh()  argument
886 	xa_lock_bh(xa);  in xa_alloc_bh()
887 	err = __xa_alloc(xa, id, entry, limit, gfp);  in xa_alloc_bh()
888 	xa_unlock_bh(xa);  in xa_alloc_bh()
895  * @xa: XArray.
901  * Finds an empty entry in @xa between @limit.min and @limit.max,
907  * Return: 0 on success, -ENOMEM if memory could not be allocated or
910 static inline int __must_check xa_alloc_irq(struct xarray *xa, u32 *id,  in xa_alloc_irq()  argument
915 	xa_lock_irq(xa);  in xa_alloc_irq()
916 	err = __xa_alloc(xa, id, entry, limit, gfp);  in xa_alloc_irq()
917 	xa_unlock_irq(xa);  in xa_alloc_irq()
924  * @xa: XArray.
931  * Finds an empty entry in @xa between @limit.min and @limit.max,
939  * Return: 0 if the allocation succeeded without wrapping.  1 if the
943 static inline int xa_alloc_cyclic(struct xarray *xa, u32 *id, void *entry,  in xa_alloc_cyclic()  argument
948 	xa_lock(xa);  in xa_alloc_cyclic()
949 	err = __xa_alloc_cyclic(xa, id, entry, limit, next, gfp);  in xa_alloc_cyclic()
950 	xa_unlock(xa);  in xa_alloc_cyclic()
957  * @xa: XArray.
964  * Finds an empty entry in @xa between @limit.min and @limit.max,
972  * Return: 0 if the allocation succeeded without wrapping.  1 if the
976 static inline int xa_alloc_cyclic_bh(struct xarray *xa, u32 *id, void *entry,  in xa_alloc_cyclic_bh()  argument
981 	xa_lock_bh(xa);  in xa_alloc_cyclic_bh()
982 	err = __xa_alloc_cyclic(xa, id, entry, limit, next, gfp);  in xa_alloc_cyclic_bh()
983 	xa_unlock_bh(xa);  in xa_alloc_cyclic_bh()
990  * @xa: XArray.
997  * Finds an empty entry in @xa between @limit.min and @limit.max,
1005  * Return: 0 if the allocation succeeded without wrapping.  1 if the
1009 static inline int xa_alloc_cyclic_irq(struct xarray *xa, u32 *id, void *entry,  in xa_alloc_cyclic_irq()  argument
1014 	xa_lock_irq(xa);  in xa_alloc_cyclic_irq()
1015 	err = __xa_alloc_cyclic(xa, id, entry, limit, next, gfp);  in xa_alloc_cyclic_irq()
1016 	xa_unlock_irq(xa);  in xa_alloc_cyclic_irq()
1023  * @xa: XArray.
1037  * Return: 0 if the reservation succeeded or -ENOMEM if it failed.
1040 int xa_reserve(struct xarray *xa, unsigned long index, gfp_t gfp)  in xa_reserve()  argument
1042 	return xa_err(xa_cmpxchg(xa, index, NULL, XA_ZERO_ENTRY, gfp));  in xa_reserve()
1047  * @xa: XArray.
1055  * Return: 0 if the reservation succeeded or -ENOMEM if it failed.
1058 int xa_reserve_bh(struct xarray *xa, unsigned long index, gfp_t gfp)  in xa_reserve_bh()  argument
1060 	return xa_err(xa_cmpxchg_bh(xa, index, NULL, XA_ZERO_ENTRY, gfp));  in xa_reserve_bh()
1065  * @xa: XArray.
1073  * Return: 0 if the reservation succeeded or -ENOMEM if it failed.
1076 int xa_reserve_irq(struct xarray *xa, unsigned long index, gfp_t gfp)  in xa_reserve_irq()  argument
1078 	return xa_err(xa_cmpxchg_irq(xa, index, NULL, XA_ZERO_ENTRY, gfp));  in xa_reserve_irq()
1083  * @xa: XArray.
1090 static inline void xa_release(struct xarray *xa, unsigned long index)  in xa_release()  argument
1092 	xa_cmpxchg(xa, index, XA_ZERO_ENTRY, NULL, 0);  in xa_release()
1144 #define XA_BUG_ON(xa, x) do {					\  argument
1146 			xa_dump(xa);				\
1149 	} while (0)
1155 	} while (0)
1157 #define XA_BUG_ON(xa, x)	do { } while (0)  argument
1158 #define XA_NODE_BUG_ON(node, x)	do { } while (0)
1162 static inline void *xa_head(const struct xarray *xa)  in xa_head()  argument
1164 	return rcu_dereference_check(xa->xa_head,  in xa_head()
1165 						lockdep_is_held(&xa->xa_lock));  in xa_head()
1169 static inline void *xa_head_locked(const struct xarray *xa)  in xa_head_locked()  argument
1171 	return rcu_dereference_protected(xa->xa_head,  in xa_head_locked()
1172 						lockdep_is_held(&xa->xa_lock));  in xa_head_locked()
1176 static inline void *xa_entry(const struct xarray *xa,  in xa_entry()  argument
1181 						lockdep_is_held(&xa->xa_lock));  in xa_entry()
1185 static inline void *xa_entry_locked(const struct xarray *xa,  in xa_entry_locked()  argument
1190 						lockdep_is_held(&xa->xa_lock));  in xa_entry_locked()
1194 static inline struct xa_node *xa_parent(const struct xarray *xa,  in xa_parent()  argument
1198 						lockdep_is_held(&xa->xa_lock));  in xa_parent()
1202 static inline struct xa_node *xa_parent_locked(const struct xarray *xa,  in xa_parent_locked()  argument
1206 						lockdep_is_held(&xa->xa_lock));  in xa_parent_locked()
1301  * single entry in the array at index 0, there are no allocated xa_nodes to
1309 	struct xarray *xa;  member
1329 	.xa = array,					\
1333 	.xa_offset = 0,					\
1334 	.xa_pad = 0,					\
1349 	struct xa_state name = __XA_STATE(array, index, 0, 0)
1368 #define xas_marked(xas, mark)	xa_marked((xas)->xa, (mark))
1369 #define xas_trylock(xas)	xa_trylock((xas)->xa)
1370 #define xas_lock(xas)		xa_lock((xas)->xa)
1371 #define xas_unlock(xas)		xa_unlock((xas)->xa)
1372 #define xas_lock_bh(xas)	xa_lock_bh((xas)->xa)
1373 #define xas_unlock_bh(xas)	xa_unlock_bh((xas)->xa)
1374 #define xas_lock_irq(xas)	xa_lock_irq((xas)->xa)
1375 #define xas_unlock_irq(xas)	xa_unlock_irq((xas)->xa)
1377 				xa_lock_irqsave((xas)->xa, flags)
1379 				xa_unlock_irqrestore((xas)->xa, flags)
1385  * Return: 0 if no error has been noted.  A negative errno if one has.
1515 static inline int xa_get_order(struct xarray *xa, unsigned long index)  in xa_get_order()  argument
1517 	return 0;  in xa_get_order()
1553 		return xa_head(xas->xa);  in xas_reload()
1556 		entry = xa_entry(xas->xa, node, offset);  in xas_reload()
1563 	return xa_entry(xas->xa, node, offset);  in xas_reload()
1591 	xas->xa_index = order < BITS_PER_LONG ? (index >> order) << order : 0;  in xas_set_order()
1596 	BUG_ON(order > 0);  in xas_set_order()
1639 		entry = xa_entry(xas->xa, node, xas->xa_offset + 1);  in xas_next_entry()
1660 			unsigned long data = *addr & (~0UL << offset);  in xas_find_chunk()
1698 	entry = xa_entry(xas->xa, node, offset);  in xas_next_marked()
1775  * If the iterator was referencing index 0, this function wraps
1786 				xas->xa_offset == 0))  in xas_prev()
1791 	return xa_entry(xas->xa, node, xas->xa_offset);  in xas_prev()
1805  * around to 0.
1820 	return xa_entry(xas->xa, node, xas->xa_offset);  in xas_next()