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()
307 	if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)  in xas_nomem()
329 	__must_hold(xas->xa->xa_lock)  in __xas_nomem()
331 	unsigned int lock_type = xa_lock_type(xas->xa);  in __xas_nomem()
337 	if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)  in __xas_nomem()
375 		if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)  in xas_alloc()
394 	node->count = 0;  in xas_alloc()
395 	node->nr_values = 0;  in xas_alloc()
397 	node->array = xas->xa;  in xas_alloc()
413  * multi-index entry at index 0, the calculation is a little more complex
436 		return 0;  in max_index()
447 	struct xarray *xa = xas->xa;  in xas_shrink()  local
456 		entry = xa_entry_locked(xa, node, 0);  in xas_shrink()
461 		if (xa_zero_busy(xa))  in xas_shrink()
465 		RCU_INIT_POINTER(xa->xa_head, entry);  in xas_shrink()
466 		if (xa_track_free(xa) && !node_get_mark(node, 0, XA_FREE_MARK))  in xas_shrink()
467 			xa_mark_clear(xa, XA_FREE_MARK);  in xas_shrink()
469 		node->count = 0;  in xas_shrink()
470 		node->nr_values = 0;  in xas_shrink()
472 			RCU_INIT_POINTER(node->slots[0], XA_RETRY_ENTRY);  in xas_shrink()
486  * Attempts to delete the @xas->xa_node.  This will fail if xa->node has
500 		parent = xa_parent_locked(xas->xa, node);  in xas_delete_node()
506 			xas->xa->xa_head = NULL;  in xas_delete_node()
533 	unsigned int offset = 0;  in xas_free_nodes()
537 		void *entry = xa_entry_locked(xas->xa, node, offset);  in xas_free_nodes()
541 			offset = 0;  in xas_free_nodes()
550 			parent = xa_parent_locked(xas->xa, node);  in xas_free_nodes()
552 			node->count = 0;  in xas_free_nodes()
553 			node->nr_values = 0;  in xas_free_nodes()
569 	struct xarray *xa = xas->xa;  in xas_expand()  local
571 	unsigned int shift = 0;  in xas_expand()
575 		if (max == 0)  in xas_expand()
576 			return 0;  in xas_expand()
587 		xa_mark_t mark = 0;  in xas_expand()
597 		RCU_INIT_POINTER(node->slots[0], head);  in xas_expand()
601 			if (xa_track_free(xa) && mark == XA_FREE_MARK) {  in xas_expand()
603 				if (!xa_marked(xa, XA_FREE_MARK)) {  in xas_expand()
604 					node_clear_mark(node, 0, XA_FREE_MARK);  in xas_expand()
605 					xa_mark_set(xa, XA_FREE_MARK);  in xas_expand()
607 			} else if (xa_marked(xa, mark)) {  in xas_expand()
608 				node_set_mark(node, 0, mark);  in xas_expand()
620 			xa_to_node(head)->offset = 0;  in xas_expand()
624 		rcu_assign_pointer(xa->xa_head, head);  in xas_expand()
649 	struct xarray *xa = xas->xa;  in xas_create()  local
657 		entry = xa_head_locked(xa);  in xas_create()
659 		if (!entry && xa_zero_busy(xa))  in xas_create()
662 		if (shift < 0)  in xas_create()
666 		entry = xa_head_locked(xa);  in xas_create()
667 		slot = &xa->xa_head;  in xas_create()
674 		entry = xa_entry_locked(xa, node, offset);  in xas_create()
677 		shift = 0;  in xas_create()
678 		entry = xa_head_locked(xa);  in xas_create()
679 		slot = &xa->xa_head;  in xas_create()
688 			if (xa_track_free(xa))  in xas_create()
721 	xas->xa_shift = 0;  in xas_create_range()
722 	xas->xa_sibs = 0;  in xas_create_range()
736 			xas->xa_node = xa_parent_locked(xas->xa, node);  in xas_create_range()
738 			if (node->offset != 0)  in xas_create_range()
766 	if (count < 0)  in update_node()
786 	void __rcu **slot = &xas->xa->xa_head;  in xas_store()
788 	int count = 0;  in xas_store()
789 	int values = 0;  in xas_store()
804 		xas->xa_sibs = 0;  in xas_store()
843 		next = xa_entry_locked(xas->xa, node, ++offset);  in xas_store()
870 		return xa_marked(xas->xa, mark);  in xas_get_mark()
896 		node = xa_parent_locked(xas->xa, node);  in xas_set_mark()
899 	if (!xa_marked(xas->xa, mark))  in xas_set_mark()
900 		xa_mark_set(xas->xa, mark);  in xas_set_mark()
928 		node = xa_parent_locked(xas->xa, node);  in xas_clear_mark()
931 	if (xa_marked(xas->xa, mark))  in xas_clear_mark()
932 		xa_mark_clear(xas->xa, mark);  in xas_clear_mark()
949 	xa_mark_t mark = 0;  in xas_init_marks()
952 		if (xa_track_free(xas->xa) && mark == XA_FREE_MARK)  in xas_init_marks()
966 	unsigned int marks = 0;  in node_get_marks()
985 	if (sibs == 0)  in node_mark_slots()
988 		for (i = 0; i < XA_CHUNK_SIZE; i += sibs + 1)  in node_mark_slots()
1020 	node->array = xas->xa;  in __xas_init_node_for_split()
1021 	for (i = 0; i < XA_CHUNK_SIZE; i++) {  in __xas_init_node_for_split()
1022 		if ((i & mask) == 0) {  in __xas_init_node_for_split()
1066 	} while (sibs-- > 0);  in xas_split_alloc()
1092 	int values = 0;  in xas_split()
1110 					XA_CHUNK_SIZE : 0;  in xas_split()
1122 			node_set_marks(node, canon, NULL, 0, marks);  in xas_split()
1152 	if (order % XA_CHUNK_SHIFT == 0)  in xas_try_split_min_order()
1153 		return order == 0 ? 0 : order - 1;  in xas_try_split_min_order()
1181 	int values = 0;  in xas_try_split()
1188 	if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)  in xas_try_split()
1230 				XA_CHUNK_SIZE : 0;  in xas_try_split()
1244 			node_set_marks(node, canon, NULL, 0, marks);  in xas_try_split()
1286 			if (!xa_is_sibling(xa_entry(xas->xa, node, offset)))  in xas_pause()
1289 		xas->xa_index &= ~0UL << node->shift;  in xas_pause()
1291 		if (xas->xa_index == 0)  in xas_pause()
1322 		xas->xa_node = xa_parent(xas->xa, xas->xa_node);  in __xas_prev()
1328 		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);  in __xas_prev()
1361 		xas->xa_node = xa_parent(xas->xa, xas->xa_node);  in __xas_next()
1367 		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);  in __xas_next()
1419 			xas->xa_node = xa_parent(xas->xa, xas->xa_node);  in xas_find()
1423 		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);  in xas_find()
1426 			xas->xa_offset = 0;  in xas_find()
1478 		entry = xa_head(xas->xa);  in xas_find_marked()
1483 			if (xa_marked(xas->xa, mark))  in xas_find_marked()
1495 			xas->xa_node = xa_parent(xas->xa, xas->xa_node);  in xas_find_marked()
1503 			entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);  in xas_find_marked()
1522 		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);  in xas_find_marked()
1523 		if (!entry && !(xa_track_free(xas->xa) && mark == XA_FREE_MARK))  in xas_find_marked()
1583 			xas->xa_node = xa_parent_locked(xas->xa, xas->xa_node);  in xas_find_conflict()
1588 		curr = xa_entry_locked(xas->xa, xas->xa_node, ++xas->xa_offset);  in xas_find_conflict()
1593 			xas->xa_offset = 0;  in xas_find_conflict()
1594 			curr = xa_entry_locked(xas->xa, xas->xa_node, 0);  in xas_find_conflict()
1606  * @xa: XArray.
1610  * Return: The entry at @index in @xa.
1612 void *xa_load(struct xarray *xa, unsigned long index)  in xa_load()  argument
1614 	XA_STATE(xas, xa, index);  in xa_load()
1636  * @xa: XArray.
1646 void *__xa_erase(struct xarray *xa, unsigned long index)  in __xa_erase()  argument
1648 	XA_STATE(xas, xa, index);  in __xa_erase()
1655  * @xa: XArray.
1665 void *xa_erase(struct xarray *xa, unsigned long index)  in xa_erase()  argument
1669 	xa_lock(xa);  in xa_erase()
1670 	entry = __xa_erase(xa, index);  in xa_erase()
1671 	xa_unlock(xa);  in xa_erase()
1679  * @xa: XArray.
1692 void *__xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)  in __xa_store()  argument
1694 	XA_STATE(xas, xa, index);  in __xa_store()
1699 	if (xa_track_free(xa) && !entry)  in __xa_store()
1704 		if (xa_track_free(xa))  in __xa_store()
1714  * @xa: XArray.
1729 void *xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)  in xa_store()  argument
1733 	xa_lock(xa);  in xa_store()
1734 	curr = __xa_store(xa, index, entry, gfp);  in xa_store()
1735 	xa_unlock(xa);  in xa_store()
1741 static inline void *__xa_cmpxchg_raw(struct xarray *xa, unsigned long index,
1746  * @xa: XArray.
1763 void *__xa_cmpxchg(struct xarray *xa, unsigned long index,  in __xa_cmpxchg()  argument
1766 	return xa_zero_to_null(__xa_cmpxchg_raw(xa, index, old, entry, gfp));  in __xa_cmpxchg()
1770 static inline void *__xa_cmpxchg_raw(struct xarray *xa, unsigned long index,  in __xa_cmpxchg_raw()  argument
1773 	XA_STATE(xas, xa, index);  in __xa_cmpxchg_raw()
1783 			if (xa_track_free(xa) && entry && !curr)  in __xa_cmpxchg_raw()
1793  * @xa: XArray.
1804  * Return: 0 if the store succeeded.  -EBUSY if another entry was present.
1807 int __xa_insert(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)  in __xa_insert()  argument
1814 	curr = __xa_cmpxchg_raw(xa, index, NULL, entry, gfp);  in __xa_insert()
1818 	return (curr != NULL) ? -EBUSY : 0;  in __xa_insert()
1826 	unsigned int shift = 0;  in xas_set_range()
1832 	while ((first & XA_CHUNK_MASK) == 0) {  in xas_set_range()
1856  * @xa: XArray.
1872 void *xa_store_range(struct xarray *xa, unsigned long first,  in xa_store_range()  argument
1875 	XA_STATE(xas, xa, 0);  in xa_store_range()
1915  * Return: A number between 0 and 63 indicating the order of the entry.
1919 	int order = 0;  in xas_get_order()
1922 		return 0;  in xas_get_order()
1924 	XA_NODE_BUG_ON(xas->xa_node, xa_is_sibling(xa_entry(xas->xa,  in xas_get_order()
1931 		if (!xa_is_sibling(xa_entry(xas->xa, xas->xa_node, slot)))  in xas_get_order()
1943  * @xa: XArray.
1946  * Return: A number between 0 and 63 indicating the order of the entry.
1948 int xa_get_order(struct xarray *xa, unsigned long index)  in xa_get_order()  argument
1950 	XA_STATE(xas, xa, index);  in xa_get_order()
1951 	int order = 0;  in xa_get_order()
1967  * @xa: XArray.
1973  * Finds an empty entry in @xa between @limit.min and @limit.max,
1982  * Return: 0 on success, -ENOMEM if memory could not be allocated or
1985 int __xa_alloc(struct xarray *xa, u32 *id, void *entry,  in __xa_alloc()  argument
1988 	XA_STATE(xas, xa, 0);  in __xa_alloc()
1992 	if (WARN_ON_ONCE(!xa_track_free(xa)))  in __xa_alloc()
2015  * @xa: XArray.
2022  * Finds an empty entry in @xa between @limit.min and @limit.max,
2033  * Return: 0 if the allocation succeeded without wrapping.  1 if the
2037 int __xa_alloc_cyclic(struct xarray *xa, u32 *id, void *entry,  in __xa_alloc_cyclic()  argument
2044 	ret = __xa_alloc(xa, id, entry, limit, gfp);  in __xa_alloc_cyclic()
2045 	if ((xa->xa_flags & XA_FLAGS_ALLOC_WRAPPED) && ret == 0) {  in __xa_alloc_cyclic()
2046 		xa->xa_flags &= ~XA_FLAGS_ALLOC_WRAPPED;  in __xa_alloc_cyclic()
2050 	if (ret < 0 && limit.min > min) {  in __xa_alloc_cyclic()
2052 		ret = __xa_alloc(xa, id, entry, limit, gfp);  in __xa_alloc_cyclic()
2053 		if (ret == 0)  in __xa_alloc_cyclic()
2057 	if (ret >= 0) {  in __xa_alloc_cyclic()
2059 		if (*next == 0)  in __xa_alloc_cyclic()
2060 			xa->xa_flags |= XA_FLAGS_ALLOC_WRAPPED;  in __xa_alloc_cyclic()
2068  * @xa: XArray.
2076 void __xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)  in __xa_set_mark()  argument
2078 	XA_STATE(xas, xa, index);  in __xa_set_mark()
2088  * @xa: XArray.
2094 void __xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)  in __xa_clear_mark()  argument
2096 	XA_STATE(xas, xa, index);  in __xa_clear_mark()
2106  * @xa: XArray.
2116 bool xa_get_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)  in xa_get_mark()  argument
2118 	XA_STATE(xas, xa, index);  in xa_get_mark()
2138  * @xa: XArray.
2146 void xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)  in xa_set_mark()  argument
2148 	xa_lock(xa);  in xa_set_mark()
2149 	__xa_set_mark(xa, index, mark);  in xa_set_mark()
2150 	xa_unlock(xa);  in xa_set_mark()
2156  * @xa: XArray.
2164 void xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)  in xa_clear_mark()  argument
2166 	xa_lock(xa);  in xa_clear_mark()
2167 	__xa_clear_mark(xa, index, mark);  in xa_clear_mark()
2168 	xa_unlock(xa);  in xa_clear_mark()
2174  * @xa: XArray.
2179  * Finds the entry in @xa which matches the @filter, and has the lowest
2189 void *xa_find(struct xarray *xa, unsigned long *indexp,  in xa_find()  argument
2192 	XA_STATE(xas, xa, *indexp);  in xa_find()
2224  * @xa: XArray.
2229  * Finds the entry in @xa which matches the @filter and has the lowest
2239 void *xa_find_after(struct xarray *xa, unsigned long *indexp,  in xa_find_after()  argument
2242 	XA_STATE(xas, xa, *indexp + 1);  in xa_find_after()
2245 	if (xas.xa_index == 0)  in xa_find_after()
2274 	unsigned int i = 0;  in xas_extract_present()
2293 	unsigned int i = 0;  in xas_extract_marked()
2310  * @xa: The source XArray to copy from.
2336 unsigned int xa_extract(struct xarray *xa, void **dst, unsigned long start,  in xa_extract()  argument
2339 	XA_STATE(xas, xa, start);  in xa_extract()
2342 		return 0;  in xa_extract()
2360 		.xa = node->array,  in xa_delete_node()
2375  * @xa: XArray.
2383 void xa_destroy(struct xarray *xa)  in xa_destroy()  argument
2385 	XA_STATE(xas, xa, 0);  in xa_destroy()
2391 	entry = xa_head_locked(xa);  in xa_destroy()
2392 	RCU_INIT_POINTER(xa->xa_head, NULL);  in xa_destroy()
2394 	if (xa_zero_busy(xa))  in xa_destroy()
2395 		xa_mark_clear(xa, XA_FREE_MARK);  in xa_destroy()
2420 	for (i = 0; i < XA_MAX_MARKS; i++)  in xa_dump_node()
2421 		for (j = 0; j < XA_MARK_LONGS; j++)  in xa_dump_node()
2431 		pr_info("0-%lu: ", ~0UL);  in xa_dump_index()
2444 		if (shift == 0) {  in xa_dump_entry()
2450 			for (i = 0; i < XA_CHUNK_SIZE; i++)  in xa_dump_entry()
2455 		pr_cont("value %ld (0x%lx) [%px]\n", xa_to_value(entry),  in xa_dump_entry()
2469 void xa_dump(const struct xarray *xa)  in xa_dump()  argument
2471 	void *entry = xa->xa_head;  in xa_dump()
2472 	unsigned int shift = 0;  in xa_dump()
2474 	pr_info("xarray: %px head %px flags %x marks %d %d %d\n", xa, entry,  in xa_dump()
2475 			xa->xa_flags, xa_marked(xa, XA_MARK_0),  in xa_dump()
2476 			xa_marked(xa, XA_MARK_1), xa_marked(xa, XA_MARK_2));  in xa_dump()
2479 	xa_dump_entry(entry, 0, shift);  in xa_dump()