24  * @index is the index of the entry being operated on
30  * @entry refers to something stored in a slot in the xarray
120  * xas_squash_marks() - Merge all marks to the first entry
123  * Set a mark on the first entry if any entry has it set.  Clear marks on
184 	void *entry;  in xas_start()  local
191 	entry = xa_head(xas->xa);  in xas_start()
192 	if (!xa_is_node(entry)) {  in xas_start()
196 		if ((xas->xa_index >> xa_to_node(entry)->shift) > XA_CHUNK_MASK)  in xas_start()
201 	return entry;  in xas_start()
208 	void *entry = xa_entry(xas->xa, node, offset);  in xas_descend()  local
211 	while (xa_is_sibling(entry)) {  in xas_descend()
212 		offset = xa_to_sibling(entry);  in xas_descend()
213 		entry = xa_entry(xas->xa, node, offset);  in xas_descend()
214 		if (node->shift && xa_is_node(entry))  in xas_descend()
215 			entry = XA_RETRY_ENTRY;  in xas_descend()
219 	return entry;  in xas_descend()
223  * xas_load() - Load an entry from the XArray (advanced).
226  * Usually walks the @xas to the appropriate state to load the entry
230  * If the xa_state is set up to operate on a multi-index entry, xas_load()
231  * may return %NULL or an internal entry, even if there are entries
235  * Return: Usually an entry in the XArray, but see description for exceptions.
239 	void *entry = xas_start(xas);  in xas_load()  local
241 	while (xa_is_node(entry)) {  in xas_load()
242 		struct xa_node *node = xa_to_node(entry);  in xas_load()
246 		entry = xas_descend(xas, node);  in xas_load()
250 	return entry;  in xas_load()
411  * in order to add the entry described by @xas.  Because we cannot store a
412  * multi-index entry at index 0, the calculation is a little more complex
432 static unsigned long max_index(void *entry)  in max_index()  argument
434 	if (!xa_is_node(entry))  in max_index()
436 	return (XA_CHUNK_SIZE << xa_to_node(entry)->shift) - 1;  in max_index()
439 static inline void *xa_zero_to_null(void *entry)  in xa_zero_to_null()  argument
441 	return xa_is_zero(entry) ? NULL : entry;  in xa_zero_to_null()
450 		void *entry;  in xas_shrink()  local
455 		entry = xa_entry_locked(xa, node, 0);  in xas_shrink()
456 		if (!entry)  in xas_shrink()
458 		if (!xa_is_node(entry) && node->shift)  in xas_shrink()
461 			entry = xa_zero_to_null(entry);  in xas_shrink()
464 		RCU_INIT_POINTER(xa->xa_head, entry);  in xas_shrink()
470 		if (!xa_is_node(entry))  in xas_shrink()
474 		if (!xa_is_node(entry))  in xas_shrink()
476 		node = xa_to_node(entry);  in xas_shrink()
536 		void *entry = xa_entry_locked(xas->xa, node, offset);  in xas_free_nodes()  local
538 		if (node->shift && xa_is_node(entry)) {  in xas_free_nodes()
539 			node = xa_to_node(entry);  in xas_free_nodes()
543 		if (entry)  in xas_free_nodes()
634  * xas_create() - Create a slot to store an entry in.
636  * @allow_root: %true if we can store the entry in the root directly
649 	void *entry;  in xas_create()  local
656 		entry = xa_head_locked(xa);  in xas_create()
658 		if (!entry && xa_zero_busy(xa))  in xas_create()
659 			entry = XA_ZERO_ENTRY;  in xas_create()
660 		shift = xas_expand(xas, entry);  in xas_create()
665 		entry = xa_head_locked(xa);  in xas_create()
673 		entry = xa_entry_locked(xa, node, offset);  in xas_create()
677 		entry = xa_head_locked(xa);  in xas_create()
683 		if (!entry) {  in xas_create()
690 		} else if (xa_is_node(entry)) {  in xas_create()
691 			node = xa_to_node(entry);  in xas_create()
695 		entry = xas_descend(xas, node);  in xas_create()
699 	return entry;  in xas_create()
770  * xas_store() - Store this entry in the XArray.
772  * @entry: New entry.
774  * If @xas is operating on a multi-index entry, the entry returned by this
775  * function is essentially meaningless (it may be an internal entry or it
780  * Return: The old entry at this index.
782 void *xas_store(struct xa_state *xas, void *entry)  in xas_store()  argument
790 	bool value = xa_is_value(entry);  in xas_store()
792 	if (entry) {  in xas_store()
793 		bool allow_root = !xa_is_node(entry) && !xa_is_zero(entry);  in xas_store()
804 	if ((first == entry) && !xas->xa_sibs)  in xas_store()
815 	if (!entry)  in xas_store()
820 		 * Must clear the marks before setting the entry to NULL,  in xas_store()
821 		 * otherwise xas_for_each_marked may find a NULL entry and  in xas_store()
824 		 * entry is set to NULL.  in xas_store()
826 		rcu_assign_pointer(*slot, entry);  in xas_store()
831 		count += !next - !entry;  in xas_store()
833 		if (entry) {  in xas_store()
836 			if (!xa_is_sibling(entry))  in xas_store()
837 				entry = xa_mk_sibling(xas->xa_offset);  in xas_store()
844 			if (!entry && (offset > max))  in xas_store()
875  * xas_set_mark() - Sets the mark on this entry and its parents.
879  * Sets the specified mark on this entry, and walks up the tree setting it
881  * an entry, or is in an error state.
904  * xas_clear_mark() - Clears the mark on this entry and its parents.
908  * Clears the specified mark on this entry, and walks back to the head
910  * @xas has not been walked to an entry, or is in an error state.
936  * xas_init_marks() - Initialise all marks for the entry
939  * Initialise all marks for the entry specified by @xas.  If we're tracking
1011  * xas_split_alloc() - Allocate memory for splitting an entry.
1013  * @entry: New entry which will be stored in the array.
1014  * @order: Current entry order.
1018  * If necessary, it will allocate new nodes (and fill them with @entry)
1019  * to prepare for the upcoming split of an entry of @order size into
1024 void xas_split_alloc(struct xa_state *xas, void *entry, unsigned int order,  in xas_split_alloc()  argument
1047 				RCU_INIT_POINTER(node->slots[i], entry);  in xas_split_alloc()
1065  * xas_split() - Split a multi-index entry into smaller entries.
1067  * @entry: New entry to store in the array.
1068  * @order: Current entry order.
1070  * The size of the new entries is set in @xas.  The value in @entry is
1075 void xas_split(struct xa_state *xas, void *entry, unsigned int order)  in xas_split()  argument
1098 			child->nr_values = xa_is_value(entry) ?  in xas_split()
1112 			rcu_assign_pointer(node->slots[canon], entry);  in xas_split()
1116 			values += (xa_is_value(entry) - xa_is_value(curr)) *  in xas_split()
1133  * on an entry.  Those users should call this function before they drop
1167  * __xas_prev() - Find the previous entry in the XArray.
1175 	void *entry;  in __xas_prev()  local
1195 		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);  in __xas_prev()
1196 		if (!xa_is_node(entry))  in __xas_prev()
1197 			return entry;  in __xas_prev()
1199 		xas->xa_node = xa_to_node(entry);  in __xas_prev()
1206  * __xas_next() - Find the next entry in the XArray.
1214 	void *entry;  in __xas_next()  local
1234 		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);  in __xas_next()
1235 		if (!xa_is_node(entry))  in __xas_next()
1236 			return entry;  in __xas_next()
1238 		xas->xa_node = xa_to_node(entry);  in __xas_next()
1245  * xas_find() - Find the next present entry in the XArray.
1249  * If the @xas has not yet been walked to an entry, return the entry
1250  * which has an index >= xas.xa_index.  If it has been walked, the entry
1252  * next entry.
1254  * If no entry is found and the array is smaller than @max, the iterator
1258  * Return: The entry, if found, otherwise %NULL.
1262 	void *entry;  in xas_find()  local
1273 		entry = xas_load(xas);  in xas_find()
1274 		if (entry || xas_not_node(xas->xa_node))  in xas_find()
1275 			return entry;  in xas_find()
1290 		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);  in xas_find()
1291 		if (xa_is_node(entry)) {  in xas_find()
1292 			xas->xa_node = xa_to_node(entry);  in xas_find()
1296 		if (entry && !xa_is_sibling(entry))  in xas_find()
1297 			return entry;  in xas_find()
1309  * xas_find_marked() - Find the next marked entry in the XArray.
1314  * If the @xas has not yet been walked to an entry, return the marked entry
1315  * which has an index >= xas.xa_index.  If it has been walked, the entry
1317  * first marked entry with an index > xas.xa_index.
1319  * If no marked entry is found and the array is smaller than @max, @xas is
1324  * If no entry is found before @max is reached, @xas is set to the restart
1327  * Return: The entry, if found, otherwise %NULL.
1333 	void *entry;  in xas_find_marked()  local
1345 		entry = xa_head(xas->xa);  in xas_find_marked()
1347 		if (xas->xa_index > max_index(entry))  in xas_find_marked()
1349 		if (!xa_is_node(entry)) {  in xas_find_marked()
1351 				return entry;  in xas_find_marked()
1355 		xas->xa_node = xa_to_node(entry);  in xas_find_marked()
1370 			entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);  in xas_find_marked()
1371 			if (xa_is_sibling(entry)) {  in xas_find_marked()
1372 				xas->xa_offset = xa_to_sibling(entry);  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()
1392 		if (xa_is_sibling(entry))  in xas_find_marked()
1394 		if (!xa_is_node(entry))  in xas_find_marked()
1395 			return entry;  in xas_find_marked()
1396 		xas->xa_node = xa_to_node(entry);  in xas_find_marked()
1411  * xas_find_conflict() - Find the next present entry in a range.
1417  * Return: The next entry in the range covered by @xas or %NULL.
1472  * xa_load() - Load an entry from an XArray.
1477  * Return: The entry at @index in @xa.
1482 	void *entry;  in xa_load()  local
1486 		entry = xa_zero_to_null(xas_load(&xas));  in xa_load()
1487 	} while (xas_retry(&xas, entry));  in xa_load()
1490 	return entry;  in xa_load()
1502  * __xa_erase() - Erase this entry from the XArray while locked.
1507  * If the index is part of a multi-index entry, all indices will be erased
1508  * and none of the entries will be part of a multi-index entry.
1510  * Context: Any context.  Expects xa_lock to be held on entry.
1511  * Return: The entry which used to be at this index.
1521  * xa_erase() - Erase this entry from the XArray.
1523  * @index: Index of entry.
1526  * If the index is part of a multi-index entry, all indices will be erased
1527  * and none of the entries will be part of a multi-index entry.
1530  * Return: The entry which used to be at this index.
1534 	void *entry;  in xa_erase()  local
1537 	entry = __xa_erase(xa, index);  in xa_erase()
1540 	return entry;  in xa_erase()
1545  * __xa_store() - Store this entry in the XArray.
1548  * @entry: New entry.
1555  * Context: Any context.  Expects xa_lock to be held on entry.  May
1557  * Return: The old entry at this index or xa_err() if an error happened.
1559 void *__xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)  in __xa_store()  argument
1564 	if (WARN_ON_ONCE(xa_is_advanced(entry)))  in __xa_store()
1566 	if (xa_track_free(xa) && !entry)  in __xa_store()
1567 		entry = XA_ZERO_ENTRY;  in __xa_store()
1570 		curr = xas_store(&xas, entry);  in __xa_store()
1580  * xa_store() - Store this entry in the XArray.
1583  * @entry: New entry.
1586  * After this function returns, loads from this index will return @entry.
1587  * Storing into an existing multi-index entry updates the entry of every index.
1588  * The marks associated with @index are unaffected unless @entry is %NULL.
1592  * Return: The old entry at this index on success, xa_err(-EINVAL) if @entry
1596 void *xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)  in xa_store()  argument
1601 	curr = __xa_store(xa, index, entry, gfp);  in xa_store()
1609 			void *old, void *entry, gfp_t gfp);
1612  * __xa_cmpxchg() - Store this entry in the XArray.
1616  * @entry: New entry.
1623  * Context: Any context.  Expects xa_lock to be held on entry.  May
1625  * Return: The old entry at this index or xa_err() if an error happened.
1628 			void *old, void *entry, gfp_t gfp)  in __xa_cmpxchg()  argument
1630 	return xa_zero_to_null(__xa_cmpxchg_raw(xa, index, old, entry, gfp));  in __xa_cmpxchg()
1635 			void *old, void *entry, gfp_t gfp)  in __xa_cmpxchg_raw()  argument
1640 	if (WARN_ON_ONCE(xa_is_advanced(entry)))  in __xa_cmpxchg_raw()
1646 			xas_store(&xas, entry);  in __xa_cmpxchg_raw()
1647 			if (xa_track_free(xa) && entry && !curr)  in __xa_cmpxchg_raw()
1656  * __xa_insert() - Store this entry in the XArray if no entry is present.
1659  * @entry: New entry.
1662  * Inserting a NULL entry will store a reserved entry (like xa_reserve())
1663  * if no entry is present.  Inserting will fail if a reserved entry is
1666  * Context: Any context.  Expects xa_lock to be held on entry.  May
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
1676 	if (!entry)  in __xa_insert()
1677 		entry = XA_ZERO_ENTRY;  in __xa_insert()
1678 	curr = __xa_cmpxchg_raw(xa, index, NULL, entry, gfp);  in __xa_insert()
1719  * xa_store_range() - Store this entry at a range of indices in the XArray.
1723  * @entry: New entry.
1727  * inclusive will return @entry.
1728  * Storing into an existing multi-index entry updates the entry of every index.
1729  * The marks associated with @index are unaffected unless @entry is %NULL.
1733  * Return: %NULL on success, xa_err(-EINVAL) if @entry cannot be stored in
1737 		unsigned long last, void *entry, gfp_t gfp)  in xa_store_range()  argument
1741 	if (WARN_ON_ONCE(xa_is_internal(entry)))  in xa_store_range()
1748 		if (entry) {  in xa_store_range()
1759 			xas_store(&xas, entry);  in xa_store_range()
1773  * xas_get_order() - Get the order of an entry.
1778  * Return: A number between 0 and 63 indicating the order of the entry.
1803  * xa_get_order() - Get the order of an entry.
1805  * @index: Index of the entry.
1807  * Return: A number between 0 and 63 indicating the order of the entry.
1813 	void *entry;  in xa_get_order()  local
1816 	entry = xas_load(&xas);  in xa_get_order()
1817 	if (entry)  in xa_get_order()
1827  * __xa_alloc() - Find somewhere to store this entry in the XArray.
1831  * @entry: New entry.
1834  * Finds an empty entry in @xa between @limit.min and @limit.max,
1835  * stores the index into the @id pointer, then stores the entry at
1841  * Context: Any context.  Expects xa_lock to be held on entry.  May
1846 int __xa_alloc(struct xarray *xa, u32 *id, void *entry,  in __xa_alloc()  argument
1851 	if (WARN_ON_ONCE(xa_is_advanced(entry)))  in __xa_alloc()
1856 	if (!entry)  in __xa_alloc()
1857 		entry = XA_ZERO_ENTRY;  in __xa_alloc()
1866 		xas_store(&xas, entry);  in __xa_alloc()
1875  * __xa_alloc_cyclic() - Find somewhere to store this entry in the XArray.
1878  * @entry: New entry.
1883  * Finds an empty entry in @xa between @limit.min and @limit.max,
1884  * stores the index into the @id pointer, then stores the entry at
1886  * The search for an empty entry will start at @next and will wrap
1892  * Context: Any context.  Expects xa_lock to be held on entry.  May
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()
1913 		ret = __xa_alloc(xa, id, entry, limit, gfp);  in __xa_alloc_cyclic()
1928  * __xa_set_mark() - Set this mark on this entry while locked.
1930  * @index: Index of entry.
1933  * Attempting to set a mark on a %NULL entry does not succeed.
1935  * Context: Any context.  Expects xa_lock to be held on entry.
1940 	void *entry = xas_load(&xas);  in __xa_set_mark()  local
1942 	if (entry)  in __xa_set_mark()
1948  * __xa_clear_mark() - Clear this mark on this entry while locked.
1950  * @index: Index of entry.
1953  * Context: Any context.  Expects xa_lock to be held on entry.
1958 	void *entry = xas_load(&xas);  in __xa_clear_mark()  local
1960 	if (entry)  in __xa_clear_mark()
1966  * xa_get_mark() - Inquire whether this mark is set on this entry.
1968  * @index: Index of entry.
1975  * Return: True if the entry at @index has this mark set, false if it doesn't.
1980 	void *entry;  in xa_get_mark()  local
1983 	entry = xas_start(&xas);  in xa_get_mark()
1985 		if (!xa_is_node(entry))  in xa_get_mark()
1987 		entry = xas_descend(&xas, xa_to_node(entry));  in xa_get_mark()
1998  * xa_set_mark() - Set this mark on this entry.
2000  * @index: Index of entry.
2003  * Attempting to set a mark on a %NULL entry does not succeed.
2016  * xa_clear_mark() - Clear this mark on this entry.
2018  * @index: Index of entry.
2034  * xa_find() - Search the XArray for an entry.
2040  * Finds the entry in @xa which matches the @filter, and has the lowest
2042  * If an entry is found, @indexp is updated to be the index of the entry.
2048  * Return: The entry, if found, otherwise %NULL.
2054 	void *entry;  in xa_find()  local
2059 			entry = xas_find_marked(&xas, max, filter);  in xa_find()
2061 			entry = xas_find(&xas, max);  in xa_find()
2062 	} while (xas_retry(&xas, entry));  in xa_find()
2065 	if (entry)  in xa_find()
2067 	return entry;  in xa_find()
2084  * xa_find_after() - Search the XArray for a present entry.
2090  * Finds the entry in @xa which matches the @filter and has the lowest
2092  * If an entry is found, @indexp is updated to be the index of the entry.
2104 	void *entry;  in xa_find_after()  local
2112 			entry = xas_find_marked(&xas, max, filter);  in xa_find_after()
2114 			entry = xas_find(&xas, max);  in xa_find_after()
2120 		if (!xas_retry(&xas, entry))  in xa_find_after()
2125 	if (entry)  in xa_find_after()
2127 	return entry;  in xa_find_after()
2134 	void *entry;  in xas_extract_present()  local
2138 	xas_for_each(xas, entry, max) {  in xas_extract_present()
2139 		if (xas_retry(xas, entry))  in xas_extract_present()
2141 		dst[i++] = entry;  in xas_extract_present()
2153 	void *entry;  in xas_extract_marked()  local
2157 	xas_for_each_marked(xas, entry, max, mark) {  in xas_extract_marked()
2158 		if (xas_retry(xas, entry))  in xas_extract_marked()
2160 		dst[i++] = entry;  in xas_extract_marked()
2216  * Context: xa_lock must be held on entry and will not be released.
2248 	void *entry;  in xa_destroy()  local
2252 	entry = xa_head_locked(xa);  in xa_destroy()
2258 	if (xa_is_node(entry))  in xa_destroy()
2259 		xas_free_nodes(&xas, xa_to_node(entry));  in xa_destroy()
2297 void xa_dump_entry(const void *entry, unsigned long index, unsigned long shift)  in xa_dump_entry()  argument
2299 	if (!entry)  in xa_dump_entry()
2304 	if (xa_is_node(entry)) {  in xa_dump_entry()
2306 			pr_cont("%px\n", entry);  in xa_dump_entry()
2309 			struct xa_node *node = xa_to_node(entry);  in xa_dump_entry()
2315 	} else if (xa_is_value(entry))  in xa_dump_entry()
2316 		pr_cont("value %ld (0x%lx) [%px]\n", xa_to_value(entry),  in xa_dump_entry()
2317 						xa_to_value(entry), entry);  in xa_dump_entry()
2318 	else if (!xa_is_internal(entry))  in xa_dump_entry()
2319 		pr_cont("%px\n", entry);  in xa_dump_entry()
2320 	else if (xa_is_retry(entry))  in xa_dump_entry()
2321 		pr_cont("retry (%ld)\n", xa_to_internal(entry));  in xa_dump_entry()
2322 	else if (xa_is_sibling(entry))  in xa_dump_entry()
2323 		pr_cont("sibling (slot %ld)\n", xa_to_sibling(entry));  in xa_dump_entry()
2324 	else if (xa_is_zero(entry))  in xa_dump_entry()
2325 		pr_cont("zero (%ld)\n", xa_to_internal(entry));  in xa_dump_entry()
2327 		pr_cont("UNKNOWN ENTRY (%px)\n", entry);  in xa_dump_entry()
2332 	void *entry = xa->xa_head;  in xa_dump()  local
2335 	pr_info("xarray: %px head %px flags %x marks %d %d %d\n", xa, entry,  in xa_dump()
2338 	if (xa_is_node(entry))  in xa_dump()
2339 		shift = xa_to_node(entry)->shift + XA_CHUNK_SHIFT;  in xa_dump()
2340 	xa_dump_entry(entry, 0, shift);  in xa_dump()