Lines Matching +full:filter +full:- +full:order
1 // SPDX-License-Identifier: GPL-2.0+
4 * Copyright (c) 2017-2018 Microsoft Corporation
5 * Copyright (c) 2018-2020 Oracle
15 #include "radix-tree.h"
35 return (__force unsigned int)xa->xa_flags & 3; in xa_lock_type()
60 return xa->xa_flags & XA_FLAGS_TRACK_FREE; in xa_track_free()
65 return xa->xa_flags & XA_FLAGS_ZERO_BUSY; in xa_zero_busy()
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()
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()
82 return node->marks[(__force unsigned)mark]; in node_marks()
120 * xas_squash_marks() - Merge all marks to the first entry
129 unsigned int limit = xas->xa_offset + xas->xa_sibs + 1; in xas_squash_marks()
132 unsigned long *marks = node_marks(xas->xa_node, mark); in xas_squash_marks()
134 if (find_next_bit(marks, limit, xas->xa_offset + 1) != limit) { in xas_squash_marks()
135 __set_bit(xas->xa_offset, marks); in xas_squash_marks()
136 bitmap_clear(marks, xas->xa_offset + 1, xas->xa_sibs); in xas_squash_marks()
147 return (index >> node->shift) & XA_CHUNK_MASK; in get_offset()
152 xas->xa_offset = get_offset(xas->xa_index, xas->xa_node); in xas_set_offset()
158 unsigned int shift = xas->xa_node->shift; in xas_move_index()
159 xas->xa_index &= ~XA_CHUNK_MASK << shift; in xas_move_index()
160 xas->xa_index += offset << shift; in xas_move_index()
165 xas->xa_offset++; in xas_next_offset()
166 xas_move_index(xas, xas->xa_offset); in xas_next_offset()
171 xas->xa_node = XAS_BOUNDS; in set_bounds()
179 * of the xarray, return NULL without changing @xas->xa_node. Otherwise
180 * set @xas->xa_node to NULL and return the current head of the array.
191 entry = xa_head(xas->xa); in xas_start()
193 if (xas->xa_index) in xas_start()
196 if ((xas->xa_index >> xa_to_node(entry)->shift) > XA_CHUNK_MASK) in xas_start()
200 xas->xa_node = NULL; in xas_start()
207 unsigned int offset = get_offset(xas->xa_index, node); in xas_descend()
208 void *entry = xa_entry(xas->xa, node, offset); in xas_descend()
210 xas->xa_node = node; 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()
218 xas->xa_offset = offset; in xas_descend()
223 * xas_load() - Load an entry from the XArray (advanced).
230 * If the xa_state is set up to operate on a multi-index entry, xas_load()
244 if (xas->xa_shift > node->shift) in xas_load()
247 if (node->shift == 0) in xas_load()
258 XA_NODE_BUG_ON(node, !list_empty(&node->private_list)); in xa_node_free()
259 node->array = XA_RCU_FREE; in xa_node_free()
260 call_rcu(&node->rcu_head, radix_tree_node_rcu_free); in xa_node_free()
264 * xas_destroy() - Free any resources allocated during the XArray operation.
272 struct xa_node *next, *node = xas->xa_alloc; in xas_destroy()
275 XA_NODE_BUG_ON(node, !list_empty(&node->private_list)); in xas_destroy()
276 next = rcu_dereference_raw(node->parent); in xas_destroy()
277 radix_tree_node_rcu_free(&node->rcu_head); in xas_destroy()
278 xas->xa_alloc = node = next; in xas_destroy()
284 * xas_nomem() - Allocate memory if needed.
303 if (xas->xa_node != XA_ERROR(-ENOMEM)) { in xas_nomem()
307 if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT) in xas_nomem()
309 xas->xa_alloc = kmem_cache_alloc_lru(radix_tree_node_cachep, xas->xa_lru, gfp); in xas_nomem()
310 if (!xas->xa_alloc) in xas_nomem()
312 xas->xa_alloc->parent = NULL; in xas_nomem()
313 XA_NODE_BUG_ON(xas->xa_alloc, !list_empty(&xas->xa_alloc->private_list)); in xas_nomem()
314 xas->xa_node = XAS_RESTART; in xas_nomem()
320 * __xas_nomem() - Drop locks and allocate memory if needed.
329 __must_hold(xas->xa->xa_lock) in __xas_nomem()
331 unsigned int lock_type = xa_lock_type(xas->xa); in __xas_nomem()
333 if (xas->xa_node != XA_ERROR(-ENOMEM)) { in __xas_nomem()
337 if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT) in __xas_nomem()
341 xas->xa_alloc = kmem_cache_alloc_lru(radix_tree_node_cachep, xas->xa_lru, gfp); in __xas_nomem()
344 xas->xa_alloc = kmem_cache_alloc_lru(radix_tree_node_cachep, xas->xa_lru, gfp); in __xas_nomem()
346 if (!xas->xa_alloc) in __xas_nomem()
348 xas->xa_alloc->parent = NULL; in __xas_nomem()
349 XA_NODE_BUG_ON(xas->xa_alloc, !list_empty(&xas->xa_alloc->private_list)); in __xas_nomem()
350 xas->xa_node = XAS_RESTART; in __xas_nomem()
356 if (xas->xa_update) in xas_update()
357 xas->xa_update(node); in xas_update()
359 XA_NODE_BUG_ON(node, !list_empty(&node->private_list)); in xas_update()
364 struct xa_node *parent = xas->xa_node; in xas_alloc()
365 struct xa_node *node = xas->xa_alloc; in xas_alloc()
371 xas->xa_alloc = NULL; in xas_alloc()
375 if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT) in xas_alloc()
378 node = kmem_cache_alloc_lru(radix_tree_node_cachep, xas->xa_lru, gfp); in xas_alloc()
380 xas_set_err(xas, -ENOMEM); in xas_alloc()
386 node->offset = xas->xa_offset; in xas_alloc()
387 parent->count++; in xas_alloc()
388 XA_NODE_BUG_ON(node, parent->count > XA_CHUNK_SIZE); in xas_alloc()
392 XA_NODE_BUG_ON(node, !list_empty(&node->private_list)); in xas_alloc()
393 node->shift = shift; in xas_alloc()
394 node->count = 0; in xas_alloc()
395 node->nr_values = 0; in xas_alloc()
396 RCU_INIT_POINTER(node->parent, xas->xa_node); in xas_alloc()
397 node->array = xas->xa; in xas_alloc()
406 return (xas->xa_sibs + 1UL) << xas->xa_shift; in xas_size()
412 * in order to add the entry described by @xas. Because we cannot store a
413 * multi-index entry at index 0, the calculation is a little more complex
418 unsigned long max = xas->xa_index; in xas_max()
421 if (xas->xa_shift || xas->xa_sibs) { in xas_max()
422 unsigned long mask = xas_size(xas) - 1; in xas_max()
437 return (XA_CHUNK_SIZE << xa_to_node(entry)->shift) - 1; in max_index()
447 struct xarray *xa = xas->xa; in xas_shrink()
448 struct xa_node *node = xas->xa_node; in xas_shrink()
453 XA_NODE_BUG_ON(node, node->count > XA_CHUNK_SIZE); in xas_shrink()
454 if (node->count != 1) in xas_shrink()
459 if (!xa_is_node(entry) && node->shift) in xas_shrink()
463 xas->xa_node = XAS_BOUNDS; in xas_shrink()
465 RCU_INIT_POINTER(xa->xa_head, entry); 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()
478 node->parent = NULL; in xas_shrink()
483 * xas_delete_node() - Attempt to delete an xa_node
486 * Attempts to delete the @xas->xa_node. This will fail if xa->node has
487 * a non-zero reference count.
491 struct xa_node *node = xas->xa_node; in xas_delete_node()
496 XA_NODE_BUG_ON(node, node->count > XA_CHUNK_SIZE); in xas_delete_node()
497 if (node->count) in xas_delete_node()
500 parent = xa_parent_locked(xas->xa, node); in xas_delete_node()
501 xas->xa_node = parent; in xas_delete_node()
502 xas->xa_offset = node->offset; in xas_delete_node()
506 xas->xa->xa_head = NULL; in xas_delete_node()
507 xas->xa_node = XAS_BOUNDS; in xas_delete_node()
511 parent->slots[xas->xa_offset] = NULL; in xas_delete_node()
512 parent->count--; in xas_delete_node()
513 XA_NODE_BUG_ON(parent, parent->count > XA_CHUNK_SIZE); in xas_delete_node()
518 if (!node->parent) in xas_delete_node()
523 * xas_free_nodes() - Free this node and all nodes that it references
537 void *entry = xa_entry_locked(xas->xa, node, offset); in xas_free_nodes()
539 if (node->shift && xa_is_node(entry)) { in xas_free_nodes()
545 RCU_INIT_POINTER(node->slots[offset], XA_RETRY_ENTRY); in xas_free_nodes()
550 parent = xa_parent_locked(xas->xa, node); in xas_free_nodes()
551 offset = node->offset + 1; in xas_free_nodes()
552 node->count = 0; in xas_free_nodes()
553 node->nr_values = 0; in xas_free_nodes()
565 * sufficient height to be able to contain @xas->xa_index
569 struct xarray *xa = xas->xa; in xas_expand()
582 shift = node->shift + XA_CHUNK_SHIFT; in xas_expand()
584 xas->xa_node = NULL; in xas_expand()
592 return -ENOMEM; in xas_expand()
594 node->count = 1; in xas_expand()
596 node->nr_values = 1; in xas_expand()
597 RCU_INIT_POINTER(node->slots[0], head); in xas_expand()
620 xa_to_node(head)->offset = 0; in xas_expand()
621 rcu_assign_pointer(xa_to_node(head)->parent, node); in xas_expand()
624 rcu_assign_pointer(xa->xa_head, head); in xas_expand()
630 xas->xa_node = node; in xas_expand()
635 * xas_create() - Create a slot to store an entry in.
649 struct xarray *xa = xas->xa; in xas_create()
652 struct xa_node *node = xas->xa_node; in xas_create()
654 unsigned int order = xas->xa_shift; in xas_create() local
658 xas->xa_node = NULL; in xas_create()
667 slot = &xa->xa_head; in xas_create()
671 unsigned int offset = xas->xa_offset; in xas_create()
673 shift = node->shift; in xas_create()
675 slot = &node->slots[offset]; in xas_create()
679 slot = &xa->xa_head; in xas_create()
682 while (shift > order) { in xas_create()
683 shift -= XA_CHUNK_SHIFT; in xas_create()
697 slot = &node->slots[xas->xa_offset]; in xas_create()
704 * xas_create_range() - Ensure that stores to this range will succeed
708 * create single-index entries and positions it at the beginning of the
710 * converted to use multi-index entries.
714 unsigned long index = xas->xa_index; in xas_create_range()
715 unsigned char shift = xas->xa_shift; in xas_create_range()
716 unsigned char sibs = xas->xa_sibs; in xas_create_range()
718 xas->xa_index |= ((sibs + 1UL) << shift) - 1; in xas_create_range()
719 if (xas_is_node(xas) && xas->xa_node->shift == xas->xa_shift) in xas_create_range()
720 xas->xa_offset |= sibs; in xas_create_range()
721 xas->xa_shift = 0; in xas_create_range()
722 xas->xa_sibs = 0; in xas_create_range()
728 if (xas->xa_index <= (index | XA_CHUNK_MASK)) in xas_create_range()
730 xas->xa_index -= XA_CHUNK_SIZE; in xas_create_range()
733 struct xa_node *node = xas->xa_node; in xas_create_range()
734 if (node->shift >= shift) in xas_create_range()
736 xas->xa_node = xa_parent_locked(xas->xa, node); in xas_create_range()
737 xas->xa_offset = node->offset - 1; in xas_create_range()
738 if (node->offset != 0) in xas_create_range()
744 xas->xa_shift = shift; in xas_create_range()
745 xas->xa_sibs = sibs; in xas_create_range()
746 xas->xa_index = index; in xas_create_range()
749 xas->xa_index = index; in xas_create_range()
750 if (xas->xa_node) in xas_create_range()
761 node->count += count; in update_node()
762 node->nr_values += values; in update_node()
763 XA_NODE_BUG_ON(node, node->count > XA_CHUNK_SIZE); in update_node()
764 XA_NODE_BUG_ON(node, node->nr_values > XA_CHUNK_SIZE); in update_node()
771 * xas_store() - Store this entry in the XArray.
775 * If @xas is operating on a multi-index entry, the entry returned by this
777 * may be %NULL, even if there are non-NULL entries at some of the indices
786 void __rcu **slot = &xas->xa->xa_head; in xas_store()
802 node = xas->xa_node; in xas_store()
803 if (node && (xas->xa_shift < node->shift)) in xas_store()
804 xas->xa_sibs = 0; in xas_store()
805 if ((first == entry) && !xas->xa_sibs) in xas_store()
809 offset = xas->xa_offset; in xas_store()
810 max = xas->xa_offset + xas->xa_sibs; in xas_store()
812 slot = &node->slots[offset]; in xas_store()
813 if (xas->xa_sibs) in xas_store()
828 if (xa_is_node(next) && (!node || node->shift)) in xas_store()
832 count += !next - !entry; in xas_store()
833 values += !xa_is_value(first) - !value; in xas_store()
838 entry = xa_mk_sibling(xas->xa_offset); in xas_store()
843 next = xa_entry_locked(xas->xa, node, ++offset); in xas_store()
858 * xas_get_mark() - Returns the state of this mark.
869 if (!xas->xa_node) in xas_get_mark()
870 return xa_marked(xas->xa, mark); in xas_get_mark()
871 return node_get_mark(xas->xa_node, xas->xa_offset, mark); in xas_get_mark()
876 * xas_set_mark() - Sets the mark on this entry and its parents.
886 struct xa_node *node = xas->xa_node; in xas_set_mark()
887 unsigned int offset = xas->xa_offset; in xas_set_mark()
895 offset = node->offset; in xas_set_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()
905 * xas_clear_mark() - Clears the mark on this entry and its parents.
915 struct xa_node *node = xas->xa_node; in xas_clear_mark()
916 unsigned int offset = xas->xa_offset; in xas_clear_mark()
927 offset = node->offset; in xas_clear_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()
937 * xas_init_marks() - Initialise all marks for the entry
952 if (xa_track_free(xas->xa) && mark == XA_FREE_MARK) in xas_init_marks()
1016 unsigned int mask = xas->xa_sibs; in __xas_init_node_for_split()
1020 node->array = xas->xa; in __xas_init_node_for_split()
1023 RCU_INIT_POINTER(node->slots[i], entry); in __xas_init_node_for_split()
1026 RCU_INIT_POINTER(node->slots[i], sibling); in __xas_init_node_for_split()
1032 * xas_split_alloc() - Allocate memory for splitting an entry.
1035 * @order: Current entry order.
1040 * to prepare for the upcoming split of an entry of @order size into
1041 * entries of the order stored in the @xas.
1045 void xas_split_alloc(struct xa_state *xas, void *entry, unsigned int order, in xas_split_alloc() argument
1048 unsigned int sibs = (1 << (order % XA_CHUNK_SHIFT)) - 1; in xas_split_alloc()
1051 if (WARN_ON(xas->xa_shift + 2 * XA_CHUNK_SHIFT <= order)) in xas_split_alloc()
1053 if (xas->xa_shift + XA_CHUNK_SHIFT > order) in xas_split_alloc()
1059 node = kmem_cache_alloc_lru(radix_tree_node_cachep, xas->xa_lru, gfp); in xas_split_alloc()
1064 RCU_INIT_POINTER(node->parent, xas->xa_alloc); in xas_split_alloc()
1065 xas->xa_alloc = node; in xas_split_alloc()
1066 } while (sibs-- > 0); in xas_split_alloc()
1071 xas_set_err(xas, -ENOMEM); in xas_split_alloc()
1076 * xas_split() - Split a multi-index entry into smaller entries.
1079 * @order: Current entry order.
1086 void xas_split(struct xa_state *xas, void *entry, unsigned int order) in xas_split() argument
1088 unsigned int sibs = (1 << (order % XA_CHUNK_SHIFT)) - 1; in xas_split()
1094 node = xas->xa_node; in xas_split()
1098 marks = node_get_marks(node, xas->xa_offset); in xas_split()
1100 offset = xas->xa_offset + sibs; in xas_split()
1102 if (xas->xa_shift < node->shift) { in xas_split()
1103 struct xa_node *child = xas->xa_alloc; in xas_split()
1105 xas->xa_alloc = rcu_dereference_raw(child->parent); in xas_split()
1106 child->shift = node->shift - XA_CHUNK_SHIFT; in xas_split()
1107 child->offset = offset; in xas_split()
1108 child->count = XA_CHUNK_SIZE; in xas_split()
1109 child->nr_values = xa_is_value(entry) ? in xas_split()
1111 RCU_INIT_POINTER(child->parent, node); in xas_split()
1112 node_set_marks(node, offset, child, xas->xa_sibs, in xas_split()
1114 rcu_assign_pointer(node->slots[offset], in xas_split()
1117 values--; in xas_split()
1120 unsigned int canon = offset - xas->xa_sibs; in xas_split()
1123 rcu_assign_pointer(node->slots[canon], entry); in xas_split()
1125 rcu_assign_pointer(node->slots[offset--], in xas_split()
1127 values += (xa_is_value(entry) - xa_is_value(curr)) * in xas_split()
1128 (xas->xa_sibs + 1); in xas_split()
1130 } while (offset-- > xas->xa_offset); in xas_split()
1132 node->nr_values += values; in xas_split()
1138 * xas_try_split_min_order() - Minimal split order xas_try_split() can accept
1139 * @order: Current entry order.
1141 * xas_try_split() can split a multi-index entry to smaller than @order - 1 if
1142 * no new xa_node is needed. This function provides the minimal order
1145 * Return: the minimal order xas_try_split() supports
1150 unsigned int xas_try_split_min_order(unsigned int order) in xas_try_split_min_order() argument
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()
1155 return order - (order % XA_CHUNK_SHIFT); in xas_try_split_min_order()
1160 * xas_try_split() - Try to split a multi-index entry.
1163 * @order: Current entry order.
1167 * needed, the function will use GFP_NOWAIT to get one if xas->xa_alloc is
1170 * NOTE: use xas_try_split_min_order() to get next split order instead of
1171 * @order - 1 if you want to minmize xas_try_split() calls.
1175 void xas_try_split(struct xa_state *xas, void *entry, unsigned int order) in xas_try_split() argument
1177 unsigned int sibs = (1 << (order % XA_CHUNK_SHIFT)) - 1; in xas_try_split()
1184 node = xas->xa_node; in xas_try_split()
1188 if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT) in xas_try_split()
1191 marks = node_get_marks(node, xas->xa_offset); in xas_try_split()
1193 offset = xas->xa_offset + sibs; in xas_try_split()
1195 if (xas->xa_shift < node->shift) { in xas_try_split()
1196 struct xa_node *child = xas->xa_alloc; in xas_try_split()
1198 (1 << ((order - 1) % XA_CHUNK_SHIFT)) - 1; in xas_try_split()
1207 if (sibs || xas->xa_sibs != expected_sibs) { in xas_try_split()
1209 xas_set_err(xas, -EINVAL); in xas_try_split()
1215 xas->xa_lru, gfp); in xas_try_split()
1218 xas_set_err(xas, -ENOMEM); in xas_try_split()
1221 RCU_INIT_POINTER(child->parent, xas->xa_alloc); in xas_try_split()
1225 xas->xa_alloc = rcu_dereference_raw(child->parent); in xas_try_split()
1226 child->shift = node->shift - XA_CHUNK_SHIFT; in xas_try_split()
1227 child->offset = offset; in xas_try_split()
1228 child->count = XA_CHUNK_SIZE; in xas_try_split()
1229 child->nr_values = xa_is_value(entry) ? in xas_try_split()
1231 RCU_INIT_POINTER(child->parent, node); in xas_try_split()
1232 node_set_marks(node, offset, child, xas->xa_sibs, in xas_try_split()
1234 rcu_assign_pointer(node->slots[offset], in xas_try_split()
1237 values--; in xas_try_split()
1242 unsigned int canon = offset - xas->xa_sibs; in xas_try_split()
1245 rcu_assign_pointer(node->slots[canon], entry); in xas_try_split()
1247 rcu_assign_pointer(node->slots[offset--], in xas_try_split()
1249 values += (xa_is_value(entry) - xa_is_value(curr)) * in xas_try_split()
1250 (xas->xa_sibs + 1); in xas_try_split()
1251 } while (offset-- > xas->xa_offset); in xas_try_split()
1254 node->nr_values += values; in xas_try_split()
1261 * xas_pause() - Pause a walk to drop a lock.
1265 * order to yield to a higher priority thread or carry out an operation
1277 struct xa_node *node = xas->xa_node; in xas_pause()
1282 xas->xa_node = XAS_RESTART; in xas_pause()
1284 unsigned long offset = xas->xa_offset; in xas_pause()
1286 if (!xa_is_sibling(xa_entry(xas->xa, node, offset))) in xas_pause()
1289 xas->xa_index &= ~0UL << node->shift; in xas_pause()
1290 xas->xa_index += (offset - xas->xa_offset) << node->shift; in xas_pause()
1291 if (xas->xa_index == 0) in xas_pause()
1292 xas->xa_node = XAS_BOUNDS; in xas_pause()
1294 xas->xa_index++; in xas_pause()
1300 * __xas_prev() - Find the previous entry in the XArray.
1310 if (!xas_frozen(xas->xa_node)) in __xas_prev()
1311 xas->xa_index--; in __xas_prev()
1312 if (!xas->xa_node) in __xas_prev()
1314 if (xas_not_node(xas->xa_node)) in __xas_prev()
1317 if (xas->xa_offset != get_offset(xas->xa_index, xas->xa_node)) in __xas_prev()
1318 xas->xa_offset--; in __xas_prev()
1320 while (xas->xa_offset == 255) { in __xas_prev()
1321 xas->xa_offset = xas->xa_node->offset - 1; in __xas_prev()
1322 xas->xa_node = xa_parent(xas->xa, xas->xa_node); in __xas_prev()
1323 if (!xas->xa_node) in __xas_prev()
1328 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in __xas_prev()
1332 xas->xa_node = xa_to_node(entry); in __xas_prev()
1339 * __xas_next() - Find the next entry in the XArray.
1349 if (!xas_frozen(xas->xa_node)) in __xas_next()
1350 xas->xa_index++; in __xas_next()
1351 if (!xas->xa_node) in __xas_next()
1353 if (xas_not_node(xas->xa_node)) in __xas_next()
1356 if (xas->xa_offset != get_offset(xas->xa_index, xas->xa_node)) in __xas_next()
1357 xas->xa_offset++; in __xas_next()
1359 while (xas->xa_offset == XA_CHUNK_SIZE) { in __xas_next()
1360 xas->xa_offset = xas->xa_node->offset + 1; in __xas_next()
1361 xas->xa_node = xa_parent(xas->xa, xas->xa_node); in __xas_next()
1362 if (!xas->xa_node) in __xas_next()
1367 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in __xas_next()
1371 xas->xa_node = xa_to_node(entry); in __xas_next()
1378 * xas_find() - Find the next present entry in the XArray.
1397 if (xas_error(xas) || xas->xa_node == XAS_BOUNDS) in xas_find()
1399 if (xas->xa_index > max) in xas_find()
1402 if (!xas->xa_node) { in xas_find()
1403 xas->xa_index = 1; in xas_find()
1405 } else if (xas->xa_node == XAS_RESTART) { in xas_find()
1407 if (entry || xas_not_node(xas->xa_node)) in xas_find()
1409 } else if (!xas->xa_node->shift && in xas_find()
1410 xas->xa_offset != (xas->xa_index & XA_CHUNK_MASK)) { in xas_find()
1411 xas->xa_offset = ((xas->xa_index - 1) & XA_CHUNK_MASK) + 1; in xas_find()
1416 while (xas->xa_node && (xas->xa_index <= max)) { in xas_find()
1417 if (unlikely(xas->xa_offset == XA_CHUNK_SIZE)) { in xas_find()
1418 xas->xa_offset = xas->xa_node->offset + 1; in xas_find()
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()
1425 xas->xa_node = xa_to_node(entry); in xas_find()
1426 xas->xa_offset = 0; in xas_find()
1435 if (!xas->xa_node) in xas_find()
1436 xas->xa_node = XAS_BOUNDS; in xas_find()
1442 * xas_find_marked() - Find the next marked entry in the XArray.
1453 * set to the bounds state and xas->xa_index is set to the smallest index
1470 if (xas->xa_index > max) in xas_find_marked()
1473 if (!xas->xa_node) { in xas_find_marked()
1474 xas->xa_index = 1; in xas_find_marked()
1476 } else if (xas_top(xas->xa_node)) { in xas_find_marked()
1478 entry = xa_head(xas->xa); in xas_find_marked()
1479 xas->xa_node = NULL; in xas_find_marked()
1480 if (xas->xa_index > max_index(entry)) in xas_find_marked()
1483 if (xa_marked(xas->xa, mark)) in xas_find_marked()
1485 xas->xa_index = 1; in xas_find_marked()
1488 xas->xa_node = xa_to_node(entry); in xas_find_marked()
1489 xas->xa_offset = xas->xa_index >> xas->xa_node->shift; in xas_find_marked()
1492 while (xas->xa_index <= max) { in xas_find_marked()
1493 if (unlikely(xas->xa_offset == XA_CHUNK_SIZE)) { in xas_find_marked()
1494 xas->xa_offset = xas->xa_node->offset + 1; in xas_find_marked()
1495 xas->xa_node = xa_parent(xas->xa, xas->xa_node); in xas_find_marked()
1496 if (!xas->xa_node) in xas_find_marked()
1503 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in xas_find_marked()
1505 xas->xa_offset = xa_to_sibling(entry); in xas_find_marked()
1506 xas_move_index(xas, xas->xa_offset); in xas_find_marked()
1511 if (offset > xas->xa_offset) { in xas_find_marked()
1515 if ((xas->xa_index - 1) >= max) in xas_find_marked()
1517 xas->xa_offset = 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()
1529 xas->xa_node = xa_to_node(entry); in xas_find_marked()
1534 if (xas->xa_index > max) in xas_find_marked()
1538 xas->xa_node = XAS_RESTART; in xas_find_marked()
1544 * xas_find_conflict() - Find the next present entry in a range.
1559 if (!xas->xa_node) in xas_find_conflict()
1562 if (xas_top(xas->xa_node)) { in xas_find_conflict()
1574 if (xas->xa_node->shift > xas->xa_shift) in xas_find_conflict()
1578 if (xas->xa_node->shift == xas->xa_shift) { in xas_find_conflict()
1579 if ((xas->xa_offset & xas->xa_sibs) == xas->xa_sibs) in xas_find_conflict()
1581 } else if (xas->xa_offset == XA_CHUNK_MASK) { in xas_find_conflict()
1582 xas->xa_offset = xas->xa_node->offset; in xas_find_conflict()
1583 xas->xa_node = xa_parent_locked(xas->xa, xas->xa_node); in xas_find_conflict()
1584 if (!xas->xa_node) in xas_find_conflict()
1588 curr = xa_entry_locked(xas->xa, xas->xa_node, ++xas->xa_offset); in xas_find_conflict()
1592 xas->xa_node = xa_to_node(curr); 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()
1599 xas->xa_offset -= xas->xa_sibs; in xas_find_conflict()
1605 * xa_load() - Load an entry from an XArray.
1630 curr = xas->xa_node; in xas_result()
1635 * __xa_erase() - Erase this entry from the XArray while locked.
1640 * If the index is part of a multi-index entry, all indices will be erased
1641 * and none of the entries will be part of a multi-index entry.
1654 * xa_erase() - Erase this entry from the XArray.
1659 * If the index is part of a multi-index entry, all indices will be erased
1660 * and none of the entries will be part of a multi-index entry.
1678 * __xa_store() - Store this entry in the XArray.
1698 return XA_ERROR(-EINVAL); in __xa_store()
1713 * xa_store() - Store this entry in the XArray.
1720 * Storing into an existing multi-index entry updates the entry of every index.
1725 * Return: The old entry at this index on success, xa_err(-EINVAL) if @entry
1726 * cannot be stored in an XArray, or xa_err(-ENOMEM) if memory allocation
1745 * __xa_cmpxchg() - Store this entry in the XArray.
1774 return XA_ERROR(-EINVAL); in __xa_cmpxchg_raw()
1789 * __xa_insert() - Store this entry in the XArray if no entry is present.
1801 * Return: 0 if the store succeeded. -EBUSY if another entry was present.
1802 * -ENOMEM if memory could not be allocated.
1815 return (curr != NULL) ? -EBUSY : 0; in __xa_insert()
1824 unsigned long sibs = last - first; in xas_set_range()
1843 sibs = XA_CHUNK_MASK - offset; in xas_set_range()
1844 if ((((first + sibs + 1) << shift) - 1) > last) in xas_set_range()
1845 sibs -= 1; in xas_set_range()
1847 xas->xa_shift = shift; in xas_set_range()
1848 xas->xa_sibs = sibs; in xas_set_range()
1852 * xa_store_range() - Store this entry at a range of indices in the XArray.
1861 * Storing into an existing multi-index entry updates the entry of every index.
1866 * Return: %NULL on success, xa_err(-EINVAL) if @entry cannot be stored in
1867 * an XArray, or xa_err(-ENOMEM) if memory allocation failed.
1875 return XA_ERROR(-EINVAL); in xa_store_range()
1877 return XA_ERROR(-EINVAL); in xa_store_range()
1882 unsigned int order = BITS_PER_LONG; in xa_store_range() local
1884 order = __ffs(last + 1); in xa_store_range()
1885 xas_set_order(&xas, last, order); in xa_store_range()
1906 * xas_get_order() - Get the order of an entry.
1911 * Return: A number between 0 and 63 indicating the order of the entry.
1915 int order = 0; in xas_get_order() local
1917 if (!xas->xa_node) in xas_get_order()
1921 unsigned int slot = xas->xa_offset + (1 << order); in xas_get_order()
1925 if (!xa_is_sibling(xa_entry(xas->xa, xas->xa_node, slot))) in xas_get_order()
1927 order++; in xas_get_order()
1930 order += xas->xa_node->shift; in xas_get_order()
1931 return order; in xas_get_order()
1936 * xa_get_order() - Get the order of an entry.
1940 * Return: A number between 0 and 63 indicating the order of the entry.
1945 int order = 0; in xa_get_order() local
1951 order = xas_get_order(&xas); in xa_get_order()
1954 return order; in xa_get_order()
1960 * __xa_alloc() - Find somewhere to store this entry in the XArray.
1976 * Return: 0 on success, -ENOMEM if memory could not be allocated or
1977 * -EBUSY if there are no free entries in @limit.
1985 return -EINVAL; in __xa_alloc()
1987 return -EINVAL; in __xa_alloc()
1996 xas_set_err(&xas, -EBUSY); in __xa_alloc()
2008 * __xa_alloc_cyclic() - Find somewhere to store this entry in the XArray.
2028 * allocation succeeded after wrapping, -ENOMEM if memory could not be
2029 * allocated or -EBUSY if there are no free entries in @limit.
2039 if ((xa->xa_flags & XA_FLAGS_ALLOC_WRAPPED) && ret == 0) { in __xa_alloc_cyclic()
2040 xa->xa_flags &= ~XA_FLAGS_ALLOC_WRAPPED; in __xa_alloc_cyclic()
2054 xa->xa_flags |= XA_FLAGS_ALLOC_WRAPPED; in __xa_alloc_cyclic()
2061 * __xa_set_mark() - Set this mark on this entry while locked.
2081 * __xa_clear_mark() - Clear this mark on this entry while locked.
2099 * xa_get_mark() - Inquire whether this mark is set on this entry.
2131 * xa_set_mark() - Set this mark on this entry.
2149 * xa_clear_mark() - Clear this mark on this entry.
2167 * xa_find() - Search the XArray for an entry.
2171 * @filter: Selection criterion.
2173 * Finds the entry in @xa which matches the @filter, and has the lowest
2184 unsigned long max, xa_mark_t filter) in xa_find() argument
2191 if ((__force unsigned int)filter < XA_MAX_MARKS) in xa_find()
2192 entry = xas_find_marked(&xas, max, filter); in xa_find()
2206 struct xa_node *node = xas->xa_node; in xas_sibling()
2211 mask = (XA_CHUNK_SIZE << node->shift) - 1; in xas_sibling()
2212 return (xas->xa_index & mask) > in xas_sibling()
2213 ((unsigned long)xas->xa_offset << node->shift); in xas_sibling()
2217 * xa_find_after() - Search the XArray for a present entry.
2221 * @filter: Selection criterion.
2223 * Finds the entry in @xa which matches the @filter and has the lowest
2234 unsigned long max, xa_mark_t filter) in xa_find_after() argument
2244 if ((__force unsigned int)filter < XA_MAX_MARKS) in xa_find_after()
2245 entry = xas_find_marked(&xas, max, filter); in xa_find_after()
2303 * xa_extract() - Copy selected entries from the XArray into a normal array.
2309 * @filter: Selection criterion.
2311 * Copies up to @n entries that match @filter from the XArray. The
2314 * The @filter may be an XArray mark value, in which case entries which are
2331 unsigned long max, unsigned int n, xa_mark_t filter) in xa_extract() argument
2338 if ((__force unsigned int)filter < XA_MAX_MARKS) in xa_extract()
2339 return xas_extract_marked(&xas, dst, max, n, filter); in xa_extract()
2345 * xa_delete_node() - Private interface for workingset code.
2354 .xa = node->array, in xa_delete_node()
2355 .xa_index = (unsigned long)node->offset << in xa_delete_node()
2356 (node->shift + XA_CHUNK_SHIFT), in xa_delete_node()
2357 .xa_shift = node->shift + XA_CHUNK_SHIFT, in xa_delete_node()
2358 .xa_offset = node->offset, in xa_delete_node()
2359 .xa_node = xa_parent_locked(node->array, node), in xa_delete_node()
2368 * xa_destroy() - Free all internal data structures.
2375 * Context: Any context. Takes and releases the xa_lock, interrupt-safe.
2386 RCU_INIT_POINTER(xa->xa_head, NULL); in xa_destroy()
2411 node, node->parent ? "offset" : "max", node->offset, in xa_dump_node()
2412 node->parent, node->shift, node->count, node->nr_values, in xa_dump_node()
2413 node->array, node->private_list.prev, node->private_list.next); in xa_dump_node()
2416 pr_cont(" %lx", node->marks[i][j]); in xa_dump_node()
2425 pr_info("0-%lu: ", ~0UL); in xa_dump_index()
2427 pr_info("%lu-%lu: ", index, index | ((1UL << shift) - 1)); in xa_dump_index()
2445 xa_dump_entry(node->slots[i], in xa_dump_entry()
2446 index + (i << node->shift), node->shift); in xa_dump_entry()
2465 void *entry = xa->xa_head; in xa_dump()
2469 xa->xa_flags, xa_marked(xa, XA_MARK_0), in xa_dump()
2472 shift = xa_to_node(entry)->shift + XA_CHUNK_SHIFT; in xa_dump()