20  * @xa is used to refer to the entire xarray.
33 static inline unsigned int xa_lock_type(const struct xarray *xa)  in xa_lock_type()  argument
35 	return (__force unsigned int)xa->xa_flags & 3;  in xa_lock_type()
58 static inline bool xa_track_free(const struct xarray *xa)  in xa_track_free()  argument
60 	return xa->xa_flags & XA_FLAGS_TRACK_FREE;  in xa_track_free()
63 static inline bool xa_zero_busy(const struct xarray *xa)  in xa_zero_busy()  argument
65 	return xa->xa_flags & XA_FLAGS_ZERO_BUSY;  in xa_zero_busy()
68 static inline void xa_mark_set(struct xarray *xa, xa_mark_t mark)  in xa_mark_set()  argument
70 	if (!(xa->xa_flags & XA_FLAGS_MARK(mark)))  in xa_mark_set()
71 		xa->xa_flags |= XA_FLAGS_MARK(mark);  in xa_mark_set()
74 static inline void xa_mark_clear(struct xarray *xa, xa_mark_t mark)  in xa_mark_clear()  argument
76 	if (xa->xa_flags & XA_FLAGS_MARK(mark))  in xa_mark_clear()
77 		xa->xa_flags &= ~(XA_FLAGS_MARK(mark));  in xa_mark_clear()
117 } while (0)
128 	unsigned int mark = 0;  in xas_squash_marks()
190 	entry = xa_head(xas->xa);  in xas_start()
207 	void *entry = xa_entry(xas->xa, node, offset);  in xas_descend()
212 		entry = xa_entry(xas->xa, node, offset);  in xas_descend()
246 		if (node->shift == 0)  in xas_load()
305 	if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)  in xas_nomem()
327 	__must_hold(xas->xa->xa_lock)  in __xas_nomem()
329 	unsigned int lock_type = xa_lock_type(xas->xa);  in __xas_nomem()
335 	if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)  in __xas_nomem()
373 		if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)  in xas_alloc()
392 	node->count = 0;  in xas_alloc()
393 	node->nr_values = 0;  in xas_alloc()
395 	node->array = xas->xa;  in xas_alloc()
411  * multi-index entry at index 0, the calculation is a little more complex
434 		return 0;  in max_index()
440 	struct xarray *xa = xas->xa;  in xas_shrink()  local
449 		entry = xa_entry_locked(xa, node, 0);  in xas_shrink()
454 		if (xa_is_zero(entry) && xa_zero_busy(xa))  in xas_shrink()
458 		RCU_INIT_POINTER(xa->xa_head, entry);  in xas_shrink()
459 		if (xa_track_free(xa) && !node_get_mark(node, 0, XA_FREE_MARK))  in xas_shrink()
460 			xa_mark_clear(xa, XA_FREE_MARK);  in xas_shrink()
462 		node->count = 0;  in xas_shrink()
463 		node->nr_values = 0;  in xas_shrink()
465 			RCU_INIT_POINTER(node->slots[0], XA_RETRY_ENTRY);  in xas_shrink()
479  * Attempts to delete the @xas->xa_node.  This will fail if xa->node has
493 		parent = xa_parent_locked(xas->xa, node);  in xas_delete_node()
499 			xas->xa->xa_head = NULL;  in xas_delete_node()
526 	unsigned int offset = 0;  in xas_free_nodes()
530 		void *entry = xa_entry_locked(xas->xa, node, offset);  in xas_free_nodes()
534 			offset = 0;  in xas_free_nodes()
543 			parent = xa_parent_locked(xas->xa, node);  in xas_free_nodes()
545 			node->count = 0;  in xas_free_nodes()
546 			node->nr_values = 0;  in xas_free_nodes()
562 	struct xarray *xa = xas->xa;  in xas_expand()  local
564 	unsigned int shift = 0;  in xas_expand()
568 		if (max == 0)  in xas_expand()
569 			return 0;  in xas_expand()
580 		xa_mark_t mark = 0;  in xas_expand()
590 		RCU_INIT_POINTER(node->slots[0], head);  in xas_expand()
594 			if (xa_track_free(xa) && mark == XA_FREE_MARK) {  in xas_expand()
596 				if (!xa_marked(xa, XA_FREE_MARK)) {  in xas_expand()
597 					node_clear_mark(node, 0, XA_FREE_MARK);  in xas_expand()
598 					xa_mark_set(xa, XA_FREE_MARK);  in xas_expand()
600 			} else if (xa_marked(xa, mark)) {  in xas_expand()
601 				node_set_mark(node, 0, mark);  in xas_expand()
613 			xa_to_node(head)->offset = 0;  in xas_expand()
617 		rcu_assign_pointer(xa->xa_head, head);  in xas_expand()
642 	struct xarray *xa = xas->xa;  in xas_create()  local
650 		entry = xa_head_locked(xa);  in xas_create()
652 		if (!entry && xa_zero_busy(xa))  in xas_create()
655 		if (shift < 0)  in xas_create()
659 		entry = xa_head_locked(xa);  in xas_create()
660 		slot = &xa->xa_head;  in xas_create()
667 		entry = xa_entry_locked(xa, node, offset);  in xas_create()
670 		shift = 0;  in xas_create()
671 		entry = xa_head_locked(xa);  in xas_create()
672 		slot = &xa->xa_head;  in xas_create()
681 			if (xa_track_free(xa))  in xas_create()
714 	xas->xa_shift = 0;  in xas_create_range()
715 	xas->xa_sibs = 0;  in xas_create_range()
729 			xas->xa_node = xa_parent_locked(xas->xa, node);  in xas_create_range()
731 			if (node->offset != 0)  in xas_create_range()
759 	if (count < 0)  in update_node()
779 	void __rcu **slot = &xas->xa->xa_head;  in xas_store()
781 	int count = 0;  in xas_store()
782 	int values = 0;  in xas_store()
797 		xas->xa_sibs = 0;  in xas_store()
836 		next = xa_entry_locked(xas->xa, node, ++offset);  in xas_store()
863 		return xa_marked(xas->xa, mark);  in xas_get_mark()
889 		node = xa_parent_locked(xas->xa, node);  in xas_set_mark()
892 	if (!xa_marked(xas->xa, mark))  in xas_set_mark()
893 		xa_mark_set(xas->xa, mark);  in xas_set_mark()
921 		node = xa_parent_locked(xas->xa, node);  in xas_clear_mark()
924 	if (xa_marked(xas->xa, mark))  in xas_clear_mark()
925 		xa_mark_clear(xas->xa, mark);  in xas_clear_mark()
942 	xa_mark_t mark = 0;  in xas_init_marks()
945 		if (xa_track_free(xas->xa) && mark == XA_FREE_MARK)  in xas_init_marks()
959 	unsigned int marks = 0;  in node_get_marks()
978 	if (sibs == 0)  in node_mark_slots()
981 		for (i = 0; i < XA_CHUNK_SIZE; i += sibs + 1)  in node_mark_slots()
1038 		node->array = xas->xa;  in xas_split_alloc()
1039 		for (i = 0; i < XA_CHUNK_SIZE; i++) {  in xas_split_alloc()
1040 			if ((i & mask) == 0) {  in xas_split_alloc()
1049 	} while (sibs-- > 0);  in xas_split_alloc()
1075 	int values = 0;  in xas_split()
1093 					XA_CHUNK_SIZE : 0;  in xas_split()
1105 			node_set_marks(node, canon, NULL, 0, marks);  in xas_split()
1147 			if (!xa_is_sibling(xa_entry(xas->xa, node, offset)))  in xas_pause()
1151 		if (xas->xa_index == 0)  in xas_pause()
1182 		xas->xa_node = xa_parent(xas->xa, xas->xa_node);  in __xas_prev()
1188 		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);  in __xas_prev()
1221 		xas->xa_node = xa_parent(xas->xa, xas->xa_node);  in __xas_next()
1227 		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);  in __xas_next()
1279 			xas->xa_node = xa_parent(xas->xa, xas->xa_node);  in xas_find()
1283 		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);  in xas_find()
1286 			xas->xa_offset = 0;  in xas_find()
1338 		entry = xa_head(xas->xa);  in xas_find_marked()
1343 			if (xa_marked(xas->xa, mark))  in xas_find_marked()
1355 			xas->xa_node = xa_parent(xas->xa, xas->xa_node);  in xas_find_marked()
1363 			entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);  in xas_find_marked()
1382 		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);  in xas_find_marked()
1383 		if (!entry && !(xa_track_free(xas->xa) && mark == XA_FREE_MARK))  in xas_find_marked()
1441 			xas->xa_node = xa_parent_locked(xas->xa, xas->xa_node);  in xas_find_conflict()
1446 		curr = xa_entry_locked(xas->xa, xas->xa_node, ++xas->xa_offset);  in xas_find_conflict()
1451 			xas->xa_offset = 0;  in xas_find_conflict()
1452 			curr = xa_entry_locked(xas->xa, xas->xa_node, 0);  in xas_find_conflict()
1464  * @xa: XArray.
1468  * Return: The entry at @index in @xa.
1470 void *xa_load(struct xarray *xa, unsigned long index)  in xa_load()  argument
1472 	XA_STATE(xas, xa, index);  in xa_load()
1498  * @xa: XArray.
1508 void *__xa_erase(struct xarray *xa, unsigned long index)  in __xa_erase()  argument
1510 	XA_STATE(xas, xa, index);  in __xa_erase()
1517  * @xa: XArray.
1527 void *xa_erase(struct xarray *xa, unsigned long index)  in xa_erase()  argument
1531 	xa_lock(xa);  in xa_erase()
1532 	entry = __xa_erase(xa, index);  in xa_erase()
1533 	xa_unlock(xa);  in xa_erase()
1541  * @xa: XArray.
1554 void *__xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)  in __xa_store()  argument
1556 	XA_STATE(xas, xa, index);  in __xa_store()
1561 	if (xa_track_free(xa) && !entry)  in __xa_store()
1566 		if (xa_track_free(xa))  in __xa_store()
1576  * @xa: XArray.
1591 void *xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)  in xa_store()  argument
1595 	xa_lock(xa);  in xa_store()
1596 	curr = __xa_store(xa, index, entry, gfp);  in xa_store()
1597 	xa_unlock(xa);  in xa_store()
1605  * @xa: XArray.
1619 void *__xa_cmpxchg(struct xarray *xa, unsigned long index,  in __xa_cmpxchg()  argument
1622 	XA_STATE(xas, xa, index);  in __xa_cmpxchg()
1632 			if (xa_track_free(xa) && entry && !curr)  in __xa_cmpxchg()
1643  * @xa: XArray.
1654  * Return: 0 if the store succeeded.  -EBUSY if another entry was present.
1657 int __xa_insert(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)  in __xa_insert()  argument
1659 	XA_STATE(xas, xa, index);  in __xa_insert()
1671 			if (xa_track_free(xa))  in __xa_insert()
1686 	unsigned int shift = 0;  in xas_set_range()
1692 	while ((first & XA_CHUNK_MASK) == 0) {  in xas_set_range()
1716  * @xa: XArray.
1732 void *xa_store_range(struct xarray *xa, unsigned long first,  in xa_store_range()  argument
1735 	XA_STATE(xas, xa, 0);  in xa_store_range()
1774  * Return: A number between 0 and 63 indicating the order of the entry.
1778 	int order = 0;  in xas_get_order()
1781 		return 0;  in xas_get_order()
1788 		if (!xa_is_sibling(xa_entry(xas->xa, xas->xa_node, slot)))  in xas_get_order()
1800  * @xa: XArray.
1803  * Return: A number between 0 and 63 indicating the order of the entry.
1805 int xa_get_order(struct xarray *xa, unsigned long index)  in xa_get_order()  argument
1807 	XA_STATE(xas, xa, index);  in xa_get_order()
1808 	int order = 0;  in xa_get_order()
1824  * @xa: XArray.
1830  * Finds an empty entry in @xa between @limit.min and @limit.max,
1839  * Return: 0 on success, -ENOMEM if memory could not be allocated or
1842 int __xa_alloc(struct xarray *xa, u32 *id, void *entry,  in __xa_alloc()  argument
1845 	XA_STATE(xas, xa, 0);  in __xa_alloc()
1849 	if (WARN_ON_ONCE(!xa_track_free(xa)))  in __xa_alloc()
1872  * @xa: XArray.
1879  * Finds an empty entry in @xa between @limit.min and @limit.max,
1890  * Return: 0 if the allocation succeeded without wrapping.  1 if the
1894 int __xa_alloc_cyclic(struct xarray *xa, u32 *id, void *entry,  in __xa_alloc_cyclic()  argument
1901 	ret = __xa_alloc(xa, id, entry, limit, gfp);  in __xa_alloc_cyclic()
1902 	if ((xa->xa_flags & XA_FLAGS_ALLOC_WRAPPED) && ret == 0) {  in __xa_alloc_cyclic()
1903 		xa->xa_flags &= ~XA_FLAGS_ALLOC_WRAPPED;  in __xa_alloc_cyclic()
1907 	if (ret < 0 && limit.min > min) {  in __xa_alloc_cyclic()
1909 		ret = __xa_alloc(xa, id, entry, limit, gfp);  in __xa_alloc_cyclic()
1910 		if (ret == 0)  in __xa_alloc_cyclic()
1914 	if (ret >= 0) {  in __xa_alloc_cyclic()
1916 		if (*next == 0)  in __xa_alloc_cyclic()
1917 			xa->xa_flags |= XA_FLAGS_ALLOC_WRAPPED;  in __xa_alloc_cyclic()
1925  * @xa: XArray.
1933 void __xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)  in __xa_set_mark()  argument
1935 	XA_STATE(xas, xa, index);  in __xa_set_mark()
1945  * @xa: XArray.
1951 void __xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)  in __xa_clear_mark()  argument
1953 	XA_STATE(xas, xa, index);  in __xa_clear_mark()
1963  * @xa: XArray.
1973 bool xa_get_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)  in xa_get_mark()  argument
1975 	XA_STATE(xas, xa, index);  in xa_get_mark()
1995  * @xa: XArray.
2003 void xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)  in xa_set_mark()  argument
2005 	xa_lock(xa);  in xa_set_mark()
2006 	__xa_set_mark(xa, index, mark);  in xa_set_mark()
2007 	xa_unlock(xa);  in xa_set_mark()
2013  * @xa: XArray.
2021 void xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)  in xa_clear_mark()  argument
2023 	xa_lock(xa);  in xa_clear_mark()
2024 	__xa_clear_mark(xa, index, mark);  in xa_clear_mark()
2025 	xa_unlock(xa);  in xa_clear_mark()
2031  * @xa: XArray.
2036  * Finds the entry in @xa which matches the @filter, and has the lowest
2046 void *xa_find(struct xarray *xa, unsigned long *indexp,  in xa_find()  argument
2049 	XA_STATE(xas, xa, *indexp);  in xa_find()
2081  * @xa: XArray.
2086  * Finds the entry in @xa which matches the @filter and has the lowest
2096 void *xa_find_after(struct xarray *xa, unsigned long *indexp,  in xa_find_after()  argument
2099 	XA_STATE(xas, xa, *indexp + 1);  in xa_find_after()
2102 	if (xas.xa_index == 0)  in xa_find_after()
2131 	unsigned int i = 0;  in xas_extract_present()
2150 	unsigned int i = 0;  in xas_extract_marked()
2167  * @xa: The source XArray to copy from.
2193 unsigned int xa_extract(struct xarray *xa, void **dst, unsigned long start,  in xa_extract()  argument
2196 	XA_STATE(xas, xa, start);  in xa_extract()
2199 		return 0;  in xa_extract()
2217 		.xa = node->array,  in xa_delete_node()
2232  * @xa: XArray.
2240 void xa_destroy(struct xarray *xa)  in xa_destroy()  argument
2242 	XA_STATE(xas, xa, 0);  in xa_destroy()
2248 	entry = xa_head_locked(xa);  in xa_destroy()
2249 	RCU_INIT_POINTER(xa->xa_head, NULL);  in xa_destroy()
2251 	if (xa_zero_busy(xa))  in xa_destroy()
2252 		xa_mark_clear(xa, XA_FREE_MARK);  in xa_destroy()
2277 	for (i = 0; i < XA_MAX_MARKS; i++)  in xa_dump_node()
2278 		for (j = 0; j < XA_MARK_LONGS; j++)  in xa_dump_node()
2288 		pr_info("0-%lu: ", ~0UL);  in xa_dump_index()
2301 		if (shift == 0) {  in xa_dump_entry()
2307 			for (i = 0; i < XA_CHUNK_SIZE; i++)  in xa_dump_entry()
2312 		pr_cont("value %ld (0x%lx) [%px]\n", xa_to_value(entry),  in xa_dump_entry()
2326 void xa_dump(const struct xarray *xa)  in xa_dump()  argument
2328 	void *entry = xa->xa_head;  in xa_dump()
2329 	unsigned int shift = 0;  in xa_dump()
2331 	pr_info("xarray: %px head %px flags %x marks %d %d %d\n", xa, entry,  in xa_dump()
2332 			xa->xa_flags, xa_marked(xa, XA_MARK_0),  in xa_dump()
2333 			xa_marked(xa, XA_MARK_1), xa_marked(xa, XA_MARK_2));  in xa_dump()
2336 	xa_dump_entry(entry, 0, shift);  in xa_dump()