linux-master/lib/xarray.c

20  * @xa is used to refer to the entire xarray.
33 static inline unsigned int xa_lock_type(const struct xarray *xa)
35 	return (__force unsigned int)xa->xa_flags & 3;
58 static inline bool xa_track_free(const struct xarray *xa)
60 	return xa->xa_flags & XA_FLAGS_TRACK_FREE;
63 static inline bool xa_zero_busy(const struct xarray *xa)
65 	return xa->xa_flags & XA_FLAGS_ZERO_BUSY;
68 static inline void xa_mark_set(struct xarray *xa, xa_mark_t mark)
70 	if (!(xa->xa_flags & XA_FLAGS_MARK(mark)))
71 		xa->xa_flags |= XA_FLAGS_MARK(mark);
74 static inline void xa_mark_clear(struct xarray *xa, xa_mark_t mark)
76 	if (xa->xa_flags & XA_FLAGS_MARK(mark))
77 		xa->xa_flags &= ~(XA_FLAGS_MARK(mark));
190 	entry = xa_head(xas->xa);
206 	void *entry = xa_entry(xas->xa, node, offset);
211 		entry = xa_entry(xas->xa, node, offset);
304 	if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)
326 	__must_hold(xas->xa->xa_lock)
328 	unsigned int lock_type = xa_lock_type(xas->xa);
334 	if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)
372 		if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)
394 	node->array = xas->xa;
439 	struct xarray *xa = xas->xa;
448 		entry = xa_entry_locked(xa, node, 0);
453 		if (xa_is_zero(entry) && xa_zero_busy(xa))
457 		RCU_INIT_POINTER(xa->xa_head, entry);
458 		if (xa_track_free(xa) && !node_get_mark(node, 0, XA_FREE_MARK))
459 			xa_mark_clear(xa, XA_FREE_MARK);
478  * Attempts to delete the @xas->xa_node.  This will fail if xa->node has
492 		parent = xa_parent_locked(xas->xa, node);
498 			xas->xa->xa_head = NULL;
529 		void *entry = xa_entry_locked(xas->xa, node, offset);
542 			parent = xa_parent_locked(xas->xa, node);
561 	struct xarray *xa = xas->xa;
593 			if (xa_track_free(xa) && mark == XA_FREE_MARK) {
595 				if (!xa_marked(xa, XA_FREE_MARK)) {
597 					xa_mark_set(xa, XA_FREE_MARK);
599 			} else if (xa_marked(xa, mark)) {
616 		rcu_assign_pointer(xa->xa_head, head);
641 	struct xarray *xa = xas->xa;
649 		entry = xa_head_locked(xa);
651 		if (!entry && xa_zero_busy(xa))
658 		entry = xa_head_locked(xa);
659 		slot = &xa->xa_head;
666 		entry = xa_entry_locked(xa, node, offset);
670 		entry = xa_head_locked(xa);
671 		slot = &xa->xa_head;
680 			if (xa_track_free(xa))
728 			xas->xa_node = xa_parent_locked(xas->xa, node);
778 	void __rcu **slot = &xas->xa->xa_head;
835 		next = xa_entry_locked(xas->xa, node, ++offset);
862 		return xa_marked(xas->xa, mark);
888 		node = xa_parent_locked(xas->xa, node);
891 	if (!xa_marked(xas->xa, mark))
892 		xa_mark_set(xas->xa, mark);
920 		node = xa_parent_locked(xas->xa, node);
923 	if (xa_marked(xas->xa, mark))
924 		xa_mark_clear(xas->xa, mark);
944 		if (xa_track_free(xas->xa) && mark == XA_FREE_MARK)
1037 		node->array = xas->xa;
1146 			if (!xa_is_sibling(xa_entry(xas->xa, node, offset)))
1181 		xas->xa_node = xa_parent(xas->xa, xas->xa_node);
1187 		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
1220 		xas->xa_node = xa_parent(xas->xa, xas->xa_node);
1226 		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
1278 			xas->xa_node = xa_parent(xas->xa, xas->xa_node);
1282 		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
1337 		entry = xa_head(xas->xa);
1342 			if (xa_marked(xas->xa, mark))
1354 			xas->xa_node = xa_parent(xas->xa, xas->xa_node);
1362 			entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
1381 		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
1382 		if (!entry && !(xa_track_free(xas->xa) && mark == XA_FREE_MARK))
1440 			xas->xa_node = xa_parent_locked(xas->xa, xas->xa_node);
1445 		curr = xa_entry_locked(xas->xa, xas->xa_node, ++xas->xa_offset);
1451 			curr = xa_entry_locked(xas->xa, xas->xa_node, 0);
1463  * @xa: XArray.
1467  * Return: The entry at @index in @xa.
1469 void *xa_load(struct xarray *xa, unsigned long index)
1471 	XA_STATE(xas, xa, index);
1497  * @xa: XArray.
1507 void *__xa_erase(struct xarray *xa, unsigned long index)
1509 	XA_STATE(xas, xa, index);
1516  * @xa: XArray.
1526 void *xa_erase(struct xarray *xa, unsigned long index)
1530 	xa_lock(xa);
1531 	entry = __xa_erase(xa, index);
1532 	xa_unlock(xa);
1540  * @xa: XArray.
1553 void *__xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)
1555 	XA_STATE(xas, xa, index);
1560 	if (xa_track_free(xa) && !entry)
1565 		if (xa_track_free(xa))
1575  * @xa: XArray.
1590 void *xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)
1594 	xa_lock(xa);
1595 	curr = __xa_store(xa, index, entry, gfp);
1596 	xa_unlock(xa);
1604  * @xa: XArray.
1618 void *__xa_cmpxchg(struct xarray *xa, unsigned long index,
1621 	XA_STATE(xas, xa, index);
1631 			if (xa_track_free(xa) && entry && !curr)
1642  * @xa: XArray.
1656 int __xa_insert(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)
1658 	XA_STATE(xas, xa, index);
1670 			if (xa_track_free(xa))
1715  * @xa: XArray.
1731 void *xa_store_range(struct xarray *xa, unsigned long first,
1734 	XA_STATE(xas, xa, 0);
1769  * @xa: XArray.
1774 int xa_get_order(struct xarray *xa, unsigned long index)
1776 	XA_STATE(xas, xa, index);
1810  * @xa: XArray.
1816  * Finds an empty entry in @xa between @limit.min and @limit.max,
1828 int __xa_alloc(struct xarray *xa, u32 *id, void *entry,
1831 	XA_STATE(xas, xa, 0);
1835 	if (WARN_ON_ONCE(!xa_track_free(xa)))
1858  * @xa: XArray.
1865  * Finds an empty entry in @xa between @limit.min and @limit.max,
1880 int __xa_alloc_cyclic(struct xarray *xa, u32 *id, void *entry,
1887 	ret = __xa_alloc(xa, id, entry, limit, gfp);
1888 	if ((xa->xa_flags & XA_FLAGS_ALLOC_WRAPPED) && ret == 0) {
1889 		xa->xa_flags &= ~XA_FLAGS_ALLOC_WRAPPED;
1895 		ret = __xa_alloc(xa, id, entry, limit, gfp);
1903 			xa->xa_flags |= XA_FLAGS_ALLOC_WRAPPED;
1911  * @xa: XArray.
1919 void __xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
1921 	XA_STATE(xas, xa, index);
1931  * @xa: XArray.
1937 void __xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
1939 	XA_STATE(xas, xa, index);
1949  * @xa: XArray.
1959 bool xa_get_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
1961 	XA_STATE(xas, xa, index);
1981  * @xa: XArray.
1989 void xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
1991 	xa_lock(xa);
1992 	__xa_set_mark(xa, index, mark);
1993 	xa_unlock(xa);
1999  * @xa: XArray.
2007 void xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
2009 	xa_lock(xa);
2010 	__xa_clear_mark(xa, index, mark);
2011 	xa_unlock(xa);
2017  * @xa: XArray.
2022  * Finds the entry in @xa which matches the @filter, and has the lowest
2032 void *xa_find(struct xarray *xa, unsigned long *indexp,
2035 	XA_STATE(xas, xa, *indexp);
2067  * @xa: XArray.
2072  * Finds the entry in @xa which matches the @filter and has the lowest
2082 void *xa_find_after(struct xarray *xa, unsigned long *indexp,
2085 	XA_STATE(xas, xa, *indexp + 1);
2153  * @xa: The source XArray to copy from.
2179 unsigned int xa_extract(struct xarray *xa, void **dst, unsigned long start,
2182 	XA_STATE(xas, xa, start);
2203 		.xa = node->array,
2218  * @xa: XArray.
2226 void xa_destroy(struct xarray *xa)
2228 	XA_STATE(xas, xa, 0);
2234 	entry = xa_head_locked(xa);
2235 	RCU_INIT_POINTER(xa->xa_head, NULL);
2237 	if (xa_zero_busy(xa))
2238 		xa_mark_clear(xa, XA_FREE_MARK);
2312 void xa_dump(const struct xarray *xa)
2314 	void *entry = xa->xa_head;
2317 	pr_info("xarray: %px head %px flags %x marks %d %d %d\n", xa, entry,
2318 			xa->xa_flags, xa_marked(xa, XA_MARK_0),
2319 			xa_marked(xa, XA_MARK_1), xa_marked(xa, XA_MARK_2));