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 	xa_mark_t mark = 0;  in xas_squash_marks()
191 	entry = xa_head(xas->xa);  in xas_start()
208 	void *entry = xa_entry(xas->xa, node, offset);  in xas_descend()
213 		entry = xa_entry(xas->xa, node, offset);  in xas_descend()
247 		if (node->shift == 0)  in xas_load()
306 	if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)  in xas_nomem()
328 	__must_hold(xas->xa->xa_lock)  in __xas_nomem()
330 	unsigned int lock_type = xa_lock_type(xas->xa);  in __xas_nomem()
336 	if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)  in __xas_nomem()
374 		if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)  in xas_alloc()
393 	node->count = 0;  in xas_alloc()
394 	node->nr_values = 0;  in xas_alloc()
396 	node->array = xas->xa;  in xas_alloc()
412  * multi-index entry at index 0, the calculation is a little more complex
435 		return 0;  in max_index()
446 	struct xarray *xa = xas->xa;  in xas_shrink()  local
455 		entry = xa_entry_locked(xa, node, 0);  in xas_shrink()
460 		if (xa_zero_busy(xa))  in xas_shrink()
464 		RCU_INIT_POINTER(xa->xa_head, entry);  in xas_shrink()
465 		if (xa_track_free(xa) && !node_get_mark(node, 0, XA_FREE_MARK))  in xas_shrink()
466 			xa_mark_clear(xa, XA_FREE_MARK);  in xas_shrink()
468 		node->count = 0;  in xas_shrink()
469 		node->nr_values = 0;  in xas_shrink()
471 			RCU_INIT_POINTER(node->slots[0], XA_RETRY_ENTRY);  in xas_shrink()
485  * Attempts to delete the @xas->xa_node.  This will fail if xa->node has
499 		parent = xa_parent_locked(xas->xa, node);  in xas_delete_node()
505 			xas->xa->xa_head = NULL;  in xas_delete_node()
532 	unsigned int offset = 0;  in xas_free_nodes()
536 		void *entry = xa_entry_locked(xas->xa, node, offset);  in xas_free_nodes()
540 			offset = 0;  in xas_free_nodes()
549 			parent = xa_parent_locked(xas->xa, node);  in xas_free_nodes()
551 			node->count = 0;  in xas_free_nodes()
552 			node->nr_values = 0;  in xas_free_nodes()
568 	struct xarray *xa = xas->xa;  in xas_expand()  local
570 	unsigned int shift = 0;  in xas_expand()
574 		if (max == 0)  in xas_expand()
575 			return 0;  in xas_expand()
586 		xa_mark_t mark = 0;  in xas_expand()
596 		RCU_INIT_POINTER(node->slots[0], head);  in xas_expand()
600 			if (xa_track_free(xa) && mark == XA_FREE_MARK) {  in xas_expand()
602 				if (!xa_marked(xa, XA_FREE_MARK)) {  in xas_expand()
603 					node_clear_mark(node, 0, XA_FREE_MARK);  in xas_expand()
604 					xa_mark_set(xa, XA_FREE_MARK);  in xas_expand()
606 			} else if (xa_marked(xa, mark)) {  in xas_expand()
607 				node_set_mark(node, 0, mark);  in xas_expand()
619 			xa_to_node(head)->offset = 0;  in xas_expand()
623 		rcu_assign_pointer(xa->xa_head, head);  in xas_expand()
648 	struct xarray *xa = xas->xa;  in xas_create()  local
656 		entry = xa_head_locked(xa);  in xas_create()
658 		if (!entry && xa_zero_busy(xa))  in xas_create()
661 		if (shift < 0)  in xas_create()
665 		entry = xa_head_locked(xa);  in xas_create()
666 		slot = &xa->xa_head;  in xas_create()
673 		entry = xa_entry_locked(xa, node, offset);  in xas_create()
676 		shift = 0;  in xas_create()
677 		entry = xa_head_locked(xa);  in xas_create()
678 		slot = &xa->xa_head;  in xas_create()
687 			if (xa_track_free(xa))  in xas_create()
720 	xas->xa_shift = 0;  in xas_create_range()
721 	xas->xa_sibs = 0;  in xas_create_range()
735 			xas->xa_node = xa_parent_locked(xas->xa, node);  in xas_create_range()
737 			if (node->offset != 0)  in xas_create_range()
765 	if (count < 0)  in update_node()
785 	void __rcu **slot = &xas->xa->xa_head;  in xas_store()
787 	int count = 0;  in xas_store()
788 	int values = 0;  in xas_store()
803 		xas->xa_sibs = 0;  in xas_store()
842 		next = xa_entry_locked(xas->xa, node, ++offset);  in xas_store()
869 		return xa_marked(xas->xa, mark);  in xas_get_mark()
895 		node = xa_parent_locked(xas->xa, node);  in xas_set_mark()
898 	if (!xa_marked(xas->xa, mark))  in xas_set_mark()
899 		xa_mark_set(xas->xa, mark);  in xas_set_mark()
927 		node = xa_parent_locked(xas->xa, node);  in xas_clear_mark()
930 	if (xa_marked(xas->xa, mark))  in xas_clear_mark()
931 		xa_mark_clear(xas->xa, mark);  in xas_clear_mark()
948 	xa_mark_t mark = 0;  in xas_init_marks()
951 		if (xa_track_free(xas->xa) && mark == XA_FREE_MARK)  in xas_init_marks()
965 	unsigned int marks = 0;  in node_get_marks()
984 	if (sibs == 0)  in node_mark_slots()
987 		for (i = 0; i < XA_CHUNK_SIZE; i += sibs + 1)  in node_mark_slots()
1044 		node->array = xas->xa;  in xas_split_alloc()
1045 		for (i = 0; i < XA_CHUNK_SIZE; i++) {  in xas_split_alloc()
1046 			if ((i & mask) == 0) {  in xas_split_alloc()
1055 	} while (sibs-- > 0);  in xas_split_alloc()
1081 	int values = 0;  in xas_split()
1099 					XA_CHUNK_SIZE : 0;  in xas_split()
1111 			node_set_marks(node, canon, NULL, 0, marks);  in xas_split()
1153 			if (!xa_is_sibling(xa_entry(xas->xa, node, offset)))  in xas_pause()
1156 		xas->xa_index &= ~0UL << node->shift;  in xas_pause()
1158 		if (xas->xa_index == 0)  in xas_pause()
1189 		xas->xa_node = xa_parent(xas->xa, xas->xa_node);  in __xas_prev()
1195 		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);  in __xas_prev()
1228 		xas->xa_node = xa_parent(xas->xa, xas->xa_node);  in __xas_next()
1234 		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);  in __xas_next()
1286 			xas->xa_node = xa_parent(xas->xa, xas->xa_node);  in xas_find()
1290 		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);  in xas_find()
1293 			xas->xa_offset = 0;  in xas_find()
1345 		entry = xa_head(xas->xa);  in xas_find_marked()
1350 			if (xa_marked(xas->xa, mark))  in xas_find_marked()
1362 			xas->xa_node = xa_parent(xas->xa, xas->xa_node);  in xas_find_marked()
1370 			entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);  in xas_find_marked()
1389 		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);  in xas_find_marked()
1390 		if (!entry && !(xa_track_free(xas->xa) && mark == XA_FREE_MARK))  in xas_find_marked()
1450 			xas->xa_node = xa_parent_locked(xas->xa, xas->xa_node);  in xas_find_conflict()
1455 		curr = xa_entry_locked(xas->xa, xas->xa_node, ++xas->xa_offset);  in xas_find_conflict()
1460 			xas->xa_offset = 0;  in xas_find_conflict()
1461 			curr = xa_entry_locked(xas->xa, xas->xa_node, 0);  in xas_find_conflict()
1473  * @xa: XArray.
1477  * Return: The entry at @index in @xa.
1479 void *xa_load(struct xarray *xa, unsigned long index)  in xa_load()  argument
1481 	XA_STATE(xas, xa, index);  in xa_load()
1503  * @xa: XArray.
1513 void *__xa_erase(struct xarray *xa, unsigned long index)  in __xa_erase()  argument
1515 	XA_STATE(xas, xa, index);  in __xa_erase()
1522  * @xa: XArray.
1532 void *xa_erase(struct xarray *xa, unsigned long index)  in xa_erase()  argument
1536 	xa_lock(xa);  in xa_erase()
1537 	entry = __xa_erase(xa, index);  in xa_erase()
1538 	xa_unlock(xa);  in xa_erase()
1546  * @xa: XArray.
1559 void *__xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)  in __xa_store()  argument
1561 	XA_STATE(xas, xa, index);  in __xa_store()
1566 	if (xa_track_free(xa) && !entry)  in __xa_store()
1571 		if (xa_track_free(xa))  in __xa_store()
1581  * @xa: XArray.
1596 void *xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)  in xa_store()  argument
1600 	xa_lock(xa);  in xa_store()
1601 	curr = __xa_store(xa, index, entry, gfp);  in xa_store()
1602 	xa_unlock(xa);  in xa_store()
1608 static inline void *__xa_cmpxchg_raw(struct xarray *xa, unsigned long index,
1613  * @xa: XArray.
1627 void *__xa_cmpxchg(struct xarray *xa, unsigned long index,  in __xa_cmpxchg()  argument
1630 	return xa_zero_to_null(__xa_cmpxchg_raw(xa, index, old, entry, gfp));  in __xa_cmpxchg()
1634 static inline void *__xa_cmpxchg_raw(struct xarray *xa, unsigned long index,  in __xa_cmpxchg_raw()  argument
1637 	XA_STATE(xas, xa, index);  in __xa_cmpxchg_raw()
1647 			if (xa_track_free(xa) && entry && !curr)  in __xa_cmpxchg_raw()
1657  * @xa: XArray.
1668  * Return: 0 if the store succeeded.  -EBUSY if another entry was present.
1671 int __xa_insert(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)  in __xa_insert()  argument
1678 	curr = __xa_cmpxchg_raw(xa, index, NULL, entry, gfp);  in __xa_insert()
1682 	return (curr != NULL) ? -EBUSY : 0;  in __xa_insert()
1690 	unsigned int shift = 0;  in xas_set_range()
1696 	while ((first & XA_CHUNK_MASK) == 0) {  in xas_set_range()
1720  * @xa: XArray.
1736 void *xa_store_range(struct xarray *xa, unsigned long first,  in xa_store_range()  argument
1739 	XA_STATE(xas, xa, 0);  in xa_store_range()
1778  * Return: A number between 0 and 63 indicating the order of the entry.
1782 	int order = 0;  in xas_get_order()
1785 		return 0;  in xas_get_order()
1792 		if (!xa_is_sibling(xa_entry(xas->xa, xas->xa_node, slot)))  in xas_get_order()
1804  * @xa: XArray.
1807  * Return: A number between 0 and 63 indicating the order of the entry.
1809 int xa_get_order(struct xarray *xa, unsigned long index)  in xa_get_order()  argument
1811 	XA_STATE(xas, xa, index);  in xa_get_order()
1812 	int order = 0;  in xa_get_order()
1828  * @xa: XArray.
1834  * Finds an empty entry in @xa between @limit.min and @limit.max,
1843  * Return: 0 on success, -ENOMEM if memory could not be allocated or
1846 int __xa_alloc(struct xarray *xa, u32 *id, void *entry,  in __xa_alloc()  argument
1849 	XA_STATE(xas, xa, 0);  in __xa_alloc()
1853 	if (WARN_ON_ONCE(!xa_track_free(xa)))  in __xa_alloc()
1876  * @xa: XArray.
1883  * Finds an empty entry in @xa between @limit.min and @limit.max,
1894  * Return: 0 if the allocation succeeded without wrapping.  1 if the
1898 int __xa_alloc_cyclic(struct xarray *xa, u32 *id, void *entry,  in __xa_alloc_cyclic()  argument
1905 	ret = __xa_alloc(xa, id, entry, limit, gfp);  in __xa_alloc_cyclic()
1906 	if ((xa->xa_flags & XA_FLAGS_ALLOC_WRAPPED) && ret == 0) {  in __xa_alloc_cyclic()
1907 		xa->xa_flags &= ~XA_FLAGS_ALLOC_WRAPPED;  in __xa_alloc_cyclic()
1911 	if (ret < 0 && limit.min > min) {  in __xa_alloc_cyclic()
1913 		ret = __xa_alloc(xa, id, entry, limit, gfp);  in __xa_alloc_cyclic()
1914 		if (ret == 0)  in __xa_alloc_cyclic()
1918 	if (ret >= 0) {  in __xa_alloc_cyclic()
1920 		if (*next == 0)  in __xa_alloc_cyclic()
1921 			xa->xa_flags |= XA_FLAGS_ALLOC_WRAPPED;  in __xa_alloc_cyclic()
1929  * @xa: XArray.
1937 void __xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)  in __xa_set_mark()  argument
1939 	XA_STATE(xas, xa, index);  in __xa_set_mark()
1949  * @xa: XArray.
1955 void __xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)  in __xa_clear_mark()  argument
1957 	XA_STATE(xas, xa, index);  in __xa_clear_mark()
1967  * @xa: XArray.
1977 bool xa_get_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)  in xa_get_mark()  argument
1979 	XA_STATE(xas, xa, index);  in xa_get_mark()
1999  * @xa: XArray.
2007 void xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)  in xa_set_mark()  argument
2009 	xa_lock(xa);  in xa_set_mark()
2010 	__xa_set_mark(xa, index, mark);  in xa_set_mark()
2011 	xa_unlock(xa);  in xa_set_mark()
2017  * @xa: XArray.
2025 void xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)  in xa_clear_mark()  argument
2027 	xa_lock(xa);  in xa_clear_mark()
2028 	__xa_clear_mark(xa, index, mark);  in xa_clear_mark()
2029 	xa_unlock(xa);  in xa_clear_mark()
2035  * @xa: XArray.
2040  * Finds the entry in @xa which matches the @filter, and has the lowest
2050 void *xa_find(struct xarray *xa, unsigned long *indexp,  in xa_find()  argument
2053 	XA_STATE(xas, xa, *indexp);  in xa_find()
2085  * @xa: XArray.
2090  * Finds the entry in @xa which matches the @filter and has the lowest
2100 void *xa_find_after(struct xarray *xa, unsigned long *indexp,  in xa_find_after()  argument
2103 	XA_STATE(xas, xa, *indexp + 1);  in xa_find_after()
2106 	if (xas.xa_index == 0)  in xa_find_after()
2135 	unsigned int i = 0;  in xas_extract_present()
2154 	unsigned int i = 0;  in xas_extract_marked()
2171  * @xa: The source XArray to copy from.
2197 unsigned int xa_extract(struct xarray *xa, void **dst, unsigned long start,  in xa_extract()  argument
2200 	XA_STATE(xas, xa, start);  in xa_extract()
2203 		return 0;  in xa_extract()
2221 		.xa = node->array,  in xa_delete_node()
2236  * @xa: XArray.
2244 void xa_destroy(struct xarray *xa)  in xa_destroy()  argument
2246 	XA_STATE(xas, xa, 0);  in xa_destroy()
2252 	entry = xa_head_locked(xa);  in xa_destroy()
2253 	RCU_INIT_POINTER(xa->xa_head, NULL);  in xa_destroy()
2255 	if (xa_zero_busy(xa))  in xa_destroy()
2256 		xa_mark_clear(xa, XA_FREE_MARK);  in xa_destroy()
2281 	for (i = 0; i < XA_MAX_MARKS; i++)  in xa_dump_node()
2282 		for (j = 0; j < XA_MARK_LONGS; j++)  in xa_dump_node()
2292 		pr_info("0-%lu: ", ~0UL);  in xa_dump_index()
2305 		if (shift == 0) {  in xa_dump_entry()
2311 			for (i = 0; i < XA_CHUNK_SIZE; i++)  in xa_dump_entry()
2316 		pr_cont("value %ld (0x%lx) [%px]\n", xa_to_value(entry),  in xa_dump_entry()
2330 void xa_dump(const struct xarray *xa)  in xa_dump()  argument
2332 	void *entry = xa->xa_head;  in xa_dump()
2333 	unsigned int shift = 0;  in xa_dump()
2335 	pr_info("xarray: %px head %px flags %x marks %d %d %d\n", xa, entry,  in xa_dump()
2336 			xa->xa_flags, xa_marked(xa, XA_MARK_0),  in xa_dump()
2337 			xa_marked(xa, XA_MARK_1), xa_marked(xa, XA_MARK_2));  in xa_dump()
2340 	xa_dump_entry(entry, 0, shift);  in xa_dump()