1 /* SPDX-License-Identifier: GPL-2.0+ */
9  * See Documentation/core-api/xarray.rst for how to use the XArray.
36  * 0-62: Sibling entries
41  * space (-4094 to -2).  They're never stored in the slots array; only
45 #define BITS_PER_XA_VALUE	(BITS_PER_LONG - 1)
48  * xa_mk_value() - Create an XArray entry from an integer.
61  * xa_to_value() - Get value stored in an XArray entry.
73  * xa_is_value() - Determine if an entry is a value.
85  * xa_tag_pointer() - Create an XArray entry for a tagged pointer.
103  * xa_untag_pointer() - Turn an XArray entry into a plain pointer.
118  * xa_pointer_tag() - Get the tag stored in an XArray entry.
133  * xa_mk_internal() - Create an internal entry.
136  * Internal entries are used for a number of purposes.  Entries 0-255 are
137  * used for sibling entries (only 0-62 are used by the current code).  256
151  * xa_to_internal() - Extract the value from an internal entry.
163  * xa_is_internal() - Is the entry an internal entry?
177  * xa_is_zero() - Is the entry a zero entry?
191  * xa_is_err() - Report whether an XArray operation returned an error
204 			entry >= xa_mk_internal(-MAX_ERRNO));  in xa_is_err()
208  * xa_err() - Turn an XArray result into an errno.
228  * struct xa_limit - Represents a range of IDs.
235  * * xa_limit_32b	- [0 - UINT_MAX]
236  * * xa_limit_31b	- [0 - INT_MAX]
237  * * xa_limit_16b	- [0 - USHRT_MAX]
276 /* ALLOC is for a normal 0-based alloc.  ALLOC1 is for an 1-based alloc */
281  * struct xarray - The anchor of the XArray.
292  * If the only non-NULL entry in the array is at index 0, @xa_head is that
293  * entry.  If any other entry in the array is non-NULL, @xa_head points
310  * DEFINE_XARRAY_FLAGS() - Define an XArray with custom flags.
323  * DEFINE_XARRAY() - Define an XArray.
334  * DEFINE_XARRAY_ALLOC() - Define an XArray which allocates IDs starting at 0.
343  * DEFINE_XARRAY_ALLOC1() - Define an XArray which allocates IDs starting at 1.
368  * xa_init_flags() - Initialise an empty XArray with flags.
380 	spin_lock_init(&xa->xa_lock);  in xa_init_flags()
381 	xa->xa_flags = flags;  in xa_init_flags()
382 	xa->xa_head = NULL;  in xa_init_flags()
386  * xa_init() - Initialise an empty XArray.
399  * xa_empty() - Determine if an array has any present entries.
407 	return xa->xa_head == NULL;  in xa_empty()
411  * xa_marked() - Inquire whether any entry in this array has a mark set
420 	return xa->xa_flags & XA_FLAGS_MARK(mark);  in xa_marked()
424  * xa_for_each_range() - Iterate over a portion of an XArray.
454  * xa_for_each_start() - Iterate over a portion of an XArray.
480  * xa_for_each() - Iterate over present entries in an XArray.
504  * xa_for_each_marked() - Iterate over marked entries in an XArray.
531 #define xa_trylock(xa)		spin_trylock(&(xa)->xa_lock)
532 #define xa_lock(xa)		spin_lock(&(xa)->xa_lock)
533 #define xa_unlock(xa)		spin_unlock(&(xa)->xa_lock)
534 #define xa_lock_bh(xa)		spin_lock_bh(&(xa)->xa_lock)
535 #define xa_unlock_bh(xa)	spin_unlock_bh(&(xa)->xa_lock)
536 #define xa_lock_irq(xa)		spin_lock_irq(&(xa)->xa_lock)
537 #define xa_unlock_irq(xa)	spin_unlock_irq(&(xa)->xa_lock)
539 				spin_lock_irqsave(&(xa)->xa_lock, flags)
541 				spin_unlock_irqrestore(&(xa)->xa_lock, flags)
543 				spin_lock_nested(&(xa)->xa_lock, subclass)
545 				spin_lock_bh_nested(&(xa)->xa_lock, subclass)
547 				spin_lock_irq_nested(&(xa)->xa_lock, subclass)
549 		spin_lock_irqsave_nested(&(xa)->xa_lock, flags, subclass)
555  * may also re-enable interrupts if the XArray flags indicate the
572  * xa_store_bh() - Store this entry in the XArray.
599  * xa_store_irq() - Store this entry in the XArray.
626  * xa_erase_bh() - Erase this entry from the XArray.
631  * If the index is part of a multi-index entry, all indices will be erased
632  * and none of the entries will be part of a multi-index entry.
650  * xa_erase_irq() - Erase this entry from the XArray.
655  * If the index is part of a multi-index entry, all indices will be erased
656  * and none of the entries will be part of a multi-index entry.
674  * xa_cmpxchg() - Conditionally replace an entry in the XArray.
685  * if the @gfp flags permit.
702  * xa_cmpxchg_bh() - Conditionally replace an entry in the XArray.
713  * disabling softirqs.  May sleep if the @gfp flags permit.
730  * xa_cmpxchg_irq() - Conditionally replace an entry in the XArray.
741  * disabling interrupts.  May sleep if the @gfp flags permit.
758  * xa_insert() - Store this entry in the XArray unless another entry is
770  * the @gfp flags permit.
771  * Return: 0 if the store succeeded.  -EBUSY if another entry was present.
772  * -ENOMEM if memory could not be allocated.
788  * xa_insert_bh() - Store this entry in the XArray unless another entry is
800  * disabling softirqs.  May sleep if the @gfp flags permit.
801  * Return: 0 if the store succeeded.  -EBUSY if another entry was present.
802  * -ENOMEM if memory could not be allocated.
818  * xa_insert_irq() - Store this entry in the XArray unless another entry is
830  * disabling interrupts.  May sleep if the @gfp flags permit.
831  * Return: 0 if the store succeeded.  -EBUSY if another entry was present.
832  * -ENOMEM if memory could not be allocated.
848  * xa_alloc() - Find somewhere to store this entry in the XArray.
863  * the @gfp flags permit.
864  * Return: 0 on success, -ENOMEM if memory could not be allocated or
865  * -EBUSY if there are no free entries in @limit.
881  * xa_alloc_bh() - Find somewhere to store this entry in the XArray.
896  * disabling softirqs.  May sleep if the @gfp flags permit.
897  * Return: 0 on success, -ENOMEM if memory could not be allocated or
898  * -EBUSY if there are no free entries in @limit.
914  * xa_alloc_irq() - Find somewhere to store this entry in the XArray.
929  * disabling interrupts.  May sleep if the @gfp flags permit.
930  * Return: 0 on success, -ENOMEM if memory could not be allocated or
931  * -EBUSY if there are no free entries in @limit.
947  * xa_alloc_cyclic() - Find somewhere to store this entry in the XArray.
965  * the @gfp flags permit.
967  * allocation succeeded after wrapping, -ENOMEM if memory could not be
968  * allocated or -EBUSY if there are no free entries in @limit.
984  * xa_alloc_cyclic_bh() - Find somewhere to store this entry in the XArray.
1002  * disabling softirqs.  May sleep if the @gfp flags permit.
1004  * allocation succeeded after wrapping, -ENOMEM if memory could not be
1005  * allocated or -EBUSY if there are no free entries in @limit.
1021  * xa_alloc_cyclic_irq() - Find somewhere to store this entry in the XArray.
1039  * disabling interrupts.  May sleep if the @gfp flags permit.
1041  * allocation succeeded after wrapping, -ENOMEM if memory could not be
1042  * allocated or -EBUSY if there are no free entries in @limit.
1058  * xa_reserve() - Reserve this index in the XArray.
1072  * May sleep if the @gfp flags permit.
1073  * Return: 0 if the reservation succeeded or -ENOMEM if it failed.
1082  * xa_reserve_bh() - Reserve this index in the XArray.
1087  * A softirq-disabling version of xa_reserve().
1091  * Return: 0 if the reservation succeeded or -ENOMEM if it failed.
1100  * xa_reserve_irq() - Reserve this index in the XArray.
1105  * An interrupt-disabling version of xa_reserve().
1109  * Return: 0 if the reservation succeeded or -ENOMEM if it failed.
1118  * xa_release() - Release a reserved entry.
1139  * balanced against the memory consumption of each node.  On a 64-bit system,
1147 #define XA_CHUNK_MASK		(XA_CHUNK_SIZE - 1)
1152  * @count is the count of every non-NULL element in the ->slots array
1155  * @nr_values is the count of every element in ->slots which is
1200 	return rcu_dereference_check(xa->xa_head,  in xa_head()
1201 						lockdep_is_held(&xa->xa_lock));  in xa_head()
1207 	return rcu_dereference_protected(xa->xa_head,  in xa_head_locked()
1208 						lockdep_is_held(&xa->xa_lock));  in xa_head_locked()
1216 	return rcu_dereference_check(node->slots[offset],  in xa_entry()
1217 						lockdep_is_held(&xa->xa_lock));  in xa_entry()
1225 	return rcu_dereference_protected(node->slots[offset],  in xa_entry_locked()
1226 						lockdep_is_held(&xa->xa_lock));  in xa_entry_locked()
1233 	return rcu_dereference_check(node->parent,  in xa_parent()
1234 						lockdep_is_held(&xa->xa_lock));  in xa_parent()
1241 	return rcu_dereference_protected(node->parent,  in xa_parent_locked()
1242 						lockdep_is_held(&xa->xa_lock));  in xa_parent_locked()
1254 	return (struct xa_node *)((unsigned long)entry - 2);  in xa_to_node()
1276  * xa_is_sibling() - Is the entry a sibling entry?
1284 		(entry < xa_mk_sibling(XA_CHUNK_SIZE - 1));  in xa_is_sibling()
1290  * xa_is_retry() - Is the entry a retry entry?
1301  * xa_is_advanced() - Is the entry only permitted for the advanced API?
1312  * typedef xa_update_node_t - A callback function from the XArray.
1320  *	    Implementations should not drop the xa_lock, nor re-enable
1358  * We encode errnos in the xas->xa_node.  If an error has happened, we need to
1379  * XA_STATE() - Declare an XArray operation state.
1390  * XA_STATE_ORDER() - Declare an XArray operation state.
1403 			order - (order % XA_CHUNK_SHIFT),	\
1404 			(1U << (order % XA_CHUNK_SHIFT)) - 1)
1406 #define xas_marked(xas, mark)	xa_marked((xas)->xa, (mark))
1407 #define xas_trylock(xas)	xa_trylock((xas)->xa)
1408 #define xas_lock(xas)		xa_lock((xas)->xa)
1409 #define xas_unlock(xas)		xa_unlock((xas)->xa)
1410 #define xas_lock_bh(xas)	xa_lock_bh((xas)->xa)
1411 #define xas_unlock_bh(xas)	xa_unlock_bh((xas)->xa)
1412 #define xas_lock_irq(xas)	xa_lock_irq((xas)->xa)
1413 #define xas_unlock_irq(xas)	xa_unlock_irq((xas)->xa)
1415 				xa_lock_irqsave((xas)->xa, flags)
1417 				xa_unlock_irqrestore((xas)->xa, flags)
1420  * xas_error() - Return an errno stored in the xa_state.
1427 	return xa_err(xas->xa_node);  in xas_error()
1431  * xas_set_err() - Note an error in the xa_state.
1441 	xas->xa_node = XA_ERROR(err);  in xas_set_err()
1445  * xas_invalid() - Is the xas in a retry or error state?
1452 	return (unsigned long)xas->xa_node & 3;  in xas_invalid()
1456  * xas_valid() - Is the xas a valid cursor into the array?
1467  * xas_is_node() - Does the xas point to a node?
1474 	return xas_valid(xas) && xas->xa_node;  in xas_is_node()
1489 /* True if the node represents head-of-tree, RESTART or BOUNDS */
1496  * xas_reset() - Reset an XArray operation state.
1507 	xas->xa_node = XAS_RESTART;  in xas_reset()
1511  * xas_retry() - Retry the operation if appropriate.
1572  * xas_reload() - Refetch an entry from the xarray.
1587 	struct xa_node *node = xas->xa_node;  in xas_reload()
1592 		return xa_head(xas->xa);  in xas_reload()
1594 		offset = (xas->xa_index >> node->shift) & XA_CHUNK_MASK;  in xas_reload()
1595 		entry = xa_entry(xas->xa, node, offset);  in xas_reload()
1600 		offset = xas->xa_offset;  in xas_reload()
1602 	return xa_entry(xas->xa, node, offset);  in xas_reload()
1606  * xas_set() - Set up XArray operation state for a different index.
1616 	xas->xa_index = index;  in xas_set()
1617 	xas->xa_node = XAS_RESTART;  in xas_set()
1621  * xas_advance() - Skip over sibling entries.
1632 	unsigned char shift = xas_is_node(xas) ? xas->xa_node->shift : 0;  in xas_advance()
1634 	xas->xa_index = index;  in xas_advance()
1635 	xas->xa_offset = (index >> shift) & XA_CHUNK_MASK;  in xas_advance()
1639  * xas_set_order() - Set up XArray operation state for a multislot entry.
1648 	xas->xa_index = order < BITS_PER_LONG ? (index >> order) << order : 0;  in xas_set_order()
1649 	xas->xa_shift = order - (order % XA_CHUNK_SHIFT);  in xas_set_order()
1650 	xas->xa_sibs = (1 << (order % XA_CHUNK_SHIFT)) - 1;  in xas_set_order()
1651 	xas->xa_node = XAS_RESTART;  in xas_set_order()
1659  * xas_set_update() - Set up XArray operation state for a callback.
1669 	xas->xa_update = update;  in xas_set_update()
1674 	xas->xa_lru = lru;  in xas_set_lru()
1678  * xas_next_entry() - Advance iterator to next present entry.
1690 	struct xa_node *node = xas->xa_node;  in xas_next_entry()
1693 	if (unlikely(xas_not_node(node) || node->shift ||  in xas_next_entry()
1694 			xas->xa_offset != (xas->xa_index & XA_CHUNK_MASK)))  in xas_next_entry()
1698 		if (unlikely(xas->xa_index >= max))  in xas_next_entry()
1700 		if (unlikely(xas->xa_offset == XA_CHUNK_MASK))  in xas_next_entry()
1702 		entry = xa_entry(xas->xa, node, xas->xa_offset + 1);  in xas_next_entry()
1705 		xas->xa_offset++;  in xas_next_entry()
1706 		xas->xa_index++;  in xas_next_entry()
1716 	unsigned long *addr = xas->xa_node->marks[(__force unsigned)mark];  in xas_find_chunk()
1717 	unsigned int offset = xas->xa_offset;  in xas_find_chunk()
1734  * xas_next_marked() - Advance iterator to next marked entry.
1748 	struct xa_node *node = xas->xa_node;  in xas_next_marked()
1752 	if (unlikely(xas_not_node(node) || node->shift))  in xas_next_marked()
1755 	xas->xa_offset = offset;  in xas_next_marked()
1756 	xas->xa_index = (xas->xa_index & ~XA_CHUNK_MASK) + offset;  in xas_next_marked()
1757 	if (xas->xa_index > max)  in xas_next_marked()
1761 	entry = xa_entry(xas->xa, node, offset);  in xas_next_marked()
1776  * xas_for_each() - Iterate over a range of an XArray.
1793  * xas_for_each_marked() - Iterate over a range of an XArray.
1811  * xas_for_each_conflict() - Iterate over a range of an XArray.
1829  * xas_prev() - Move iterator to previous index.
1846 	struct xa_node *node = xas->xa_node;  in xas_prev()
1848 	if (unlikely(xas_not_node(node) || node->shift ||  in xas_prev()
1849 				xas->xa_offset == 0))  in xas_prev()
1852 	xas->xa_index--;  in xas_prev()
1853 	xas->xa_offset--;  in xas_prev()
1854 	return xa_entry(xas->xa, node, xas->xa_offset);  in xas_prev()
1858  * xas_next() - Move state to next index.
1875 	struct xa_node *node = xas->xa_node;  in xas_next()
1877 	if (unlikely(xas_not_node(node) || node->shift ||  in xas_next()
1878 				xas->xa_offset == XA_CHUNK_MASK))  in xas_next()
1881 	xas->xa_index++;  in xas_next()
1882 	xas->xa_offset++;  in xas_next()
1883 	return xa_entry(xas->xa, node, xas->xa_offset);  in xas_next()