Lines Matching refs:xas
38 static inline void xas_lock_type(struct xa_state *xas, unsigned int lock_type) in xas_lock_type() argument
41 xas_lock_irq(xas); in xas_lock_type()
43 xas_lock_bh(xas); in xas_lock_type()
45 xas_lock(xas); in xas_lock_type()
48 static inline void xas_unlock_type(struct xa_state *xas, unsigned int lock_type) in xas_unlock_type() argument
51 xas_unlock_irq(xas); in xas_unlock_type()
53 xas_unlock_bh(xas); in xas_unlock_type()
55 xas_unlock(xas); in xas_unlock_type()
126 static void xas_squash_marks(const struct xa_state *xas) in xas_squash_marks() argument
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()
150 static void xas_set_offset(struct xa_state *xas) in xas_set_offset() argument
152 xas->xa_offset = get_offset(xas->xa_index, xas->xa_node); in xas_set_offset()
156 static void xas_move_index(struct xa_state *xas, unsigned long offset) in xas_move_index() argument
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()
163 static void xas_next_offset(struct xa_state *xas) in xas_next_offset() argument
165 xas->xa_offset++; in xas_next_offset()
166 xas_move_index(xas, xas->xa_offset); in xas_next_offset()
169 static void *set_bounds(struct xa_state *xas) in set_bounds() argument
171 xas->xa_node = XAS_BOUNDS; in set_bounds()
182 static void *xas_start(struct xa_state *xas) in xas_start() argument
186 if (xas_valid(xas)) in xas_start()
187 return xas_reload(xas); in xas_start()
188 if (xas_error(xas)) in xas_start()
191 entry = xa_head(xas->xa); in xas_start()
193 if (xas->xa_index) in xas_start()
194 return set_bounds(xas); in xas_start()
196 if ((xas->xa_index >> xa_to_node(entry)->shift) > XA_CHUNK_MASK) in xas_start()
197 return set_bounds(xas); in xas_start()
200 xas->xa_node = NULL; in xas_start()
204 static __always_inline void *xas_descend(struct xa_state *xas, in xas_descend() argument
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()
218 xas->xa_offset = offset; in xas_descend()
237 void *xas_load(struct xa_state *xas) in xas_load() argument
239 void *entry = xas_start(xas); in xas_load()
244 if (xas->xa_shift > node->shift) in xas_load()
246 entry = xas_descend(xas, node); in xas_load()
270 void xas_destroy(struct xa_state *xas) in xas_destroy() argument
272 struct xa_node *next, *node = xas->xa_alloc; in xas_destroy()
278 xas->xa_alloc = node = next; in xas_destroy()
301 bool xas_nomem(struct xa_state *xas, gfp_t gfp) in xas_nomem() argument
303 if (xas->xa_node != XA_ERROR(-ENOMEM)) { in xas_nomem()
304 xas_destroy(xas); 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()
328 static bool __xas_nomem(struct xa_state *xas, gfp_t gfp) in __xas_nomem() argument
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()
334 xas_destroy(xas); in __xas_nomem()
337 if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT) in __xas_nomem()
340 xas_unlock_type(xas, lock_type); in __xas_nomem()
341 xas->xa_alloc = kmem_cache_alloc_lru(radix_tree_node_cachep, xas->xa_lru, gfp); in __xas_nomem()
342 xas_lock_type(xas, lock_type); 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()
354 static void xas_update(struct xa_state *xas, struct xa_node *node) in xas_update() argument
356 if (xas->xa_update) in xas_update()
357 xas->xa_update(node); in xas_update()
362 static void *xas_alloc(struct xa_state *xas, unsigned int shift) in xas_alloc() argument
364 struct xa_node *parent = xas->xa_node; in xas_alloc()
365 struct xa_node *node = xas->xa_alloc; in xas_alloc()
367 if (xas_invalid(xas)) 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()
389 xas_update(xas, parent); in xas_alloc()
396 RCU_INIT_POINTER(node->parent, xas->xa_node); in xas_alloc()
397 node->array = xas->xa; in xas_alloc()
404 static unsigned long xas_size(const struct xa_state *xas) in xas_size() argument
406 return (xas->xa_sibs + 1UL) << xas->xa_shift; in xas_size()
416 static unsigned long xas_max(struct xa_state *xas) in xas_max() argument
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()
445 static void xas_shrink(struct xa_state *xas) in xas_shrink() argument
447 struct xarray *xa = xas->xa; in xas_shrink()
448 struct xa_node *node = xas->xa_node; in xas_shrink()
463 xas->xa_node = XAS_BOUNDS; in xas_shrink()
473 xas_update(xas, node); in xas_shrink()
489 static void xas_delete_node(struct xa_state *xas) in xas_delete_node() argument
491 struct xa_node *node = xas->xa_node; 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()
515 xas_update(xas, node); in xas_delete_node()
519 xas_shrink(xas); in xas_delete_node()
531 static void xas_free_nodes(struct xa_state *xas, struct xa_node *top) in xas_free_nodes() argument
537 void *entry = xa_entry_locked(xas->xa, node, offset); in xas_free_nodes()
550 parent = xa_parent_locked(xas->xa, node); in xas_free_nodes()
554 xas_update(xas, node); in xas_free_nodes()
567 static int xas_expand(struct xa_state *xas, void *head) in xas_expand() argument
569 struct xarray *xa = xas->xa; in xas_expand()
572 unsigned long max = xas_max(xas); in xas_expand()
584 xas->xa_node = NULL; in xas_expand()
590 node = xas_alloc(xas, shift); in xas_expand()
625 xas_update(xas, node); in xas_expand()
630 xas->xa_node = node; in xas_expand()
647 static void *xas_create(struct xa_state *xas, bool allow_root) in xas_create() argument
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()
658 xas->xa_node = NULL; in xas_create()
661 shift = xas_expand(xas, entry); in xas_create()
668 } else if (xas_error(xas)) { in xas_create()
671 unsigned int offset = xas->xa_offset; in xas_create()
685 node = xas_alloc(xas, shift); in xas_create()
696 entry = xas_descend(xas, node); in xas_create()
697 slot = &node->slots[xas->xa_offset]; in xas_create()
712 void xas_create_range(struct xa_state *xas) in xas_create_range() argument
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()
725 xas_create(xas, true); in xas_create_range()
726 if (xas_error(xas)) 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()
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()
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()
751 xas_set_offset(xas); in xas_create_range()
755 static void update_node(struct xa_state *xas, struct xa_node *node, in update_node() argument
765 xas_update(xas, node); in update_node()
767 xas_delete_node(xas); in update_node()
783 void *xas_store(struct xa_state *xas, void *entry) in xas_store() argument
786 void __rcu **slot = &xas->xa->xa_head; in xas_store()
795 first = xas_create(xas, allow_root); in xas_store()
797 first = xas_load(xas); in xas_store()
800 if (xas_invalid(xas)) 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()
813 if (xas->xa_sibs) in xas_store()
814 xas_squash_marks(xas); in xas_store()
817 xas_init_marks(xas); in xas_store()
829 xas_free_nodes(xas, xa_to_node(next)); 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()
852 update_node(xas, node, count, values); in xas_store()
865 bool xas_get_mark(const struct xa_state *xas, xa_mark_t mark) in xas_get_mark() argument
867 if (xas_invalid(xas)) in xas_get_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()
884 void xas_set_mark(const struct xa_state *xas, xa_mark_t mark) in xas_set_mark() argument
886 struct xa_node *node = xas->xa_node; in xas_set_mark()
887 unsigned int offset = xas->xa_offset; in xas_set_mark()
889 if (xas_invalid(xas)) 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()
913 void xas_clear_mark(const struct xa_state *xas, xa_mark_t mark) in xas_clear_mark() argument
915 struct xa_node *node = xas->xa_node; in xas_clear_mark()
916 unsigned int offset = xas->xa_offset; in xas_clear_mark()
918 if (xas_invalid(xas)) 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()
947 void xas_init_marks(const struct xa_state *xas) in xas_init_marks() argument
952 if (xa_track_free(xas->xa) && mark == XA_FREE_MARK) in xas_init_marks()
953 xas_set_mark(xas, mark); in xas_init_marks()
955 xas_clear_mark(xas, mark); in xas_init_marks()
1011 static void __xas_init_node_for_split(struct xa_state *xas, in __xas_init_node_for_split() argument
1016 unsigned int mask = xas->xa_sibs; in __xas_init_node_for_split()
1020 node->array = xas->xa; in __xas_init_node_for_split()
1045 void xas_split_alloc(struct xa_state *xas, void *entry, unsigned int order, in xas_split_alloc() argument
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()
1063 __xas_init_node_for_split(xas, node, entry); 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()
1070 xas_destroy(xas); in xas_split_alloc()
1071 xas_set_err(xas, -ENOMEM); in xas_split_alloc()
1086 void xas_split(struct xa_state *xas, void *entry, unsigned int order) in xas_split() argument
1091 void *curr = xas_load(xas); 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()
1112 node_set_marks(node, offset, child, xas->xa_sibs, in xas_split()
1118 xas_update(xas, child); in xas_split()
1120 unsigned int canon = offset - xas->xa_sibs; in xas_split()
1128 (xas->xa_sibs + 1); in xas_split()
1130 } while (offset-- > xas->xa_offset); in xas_split()
1133 xas_update(xas, node); in xas_split()
1175 void xas_try_split(struct xa_state *xas, void *entry, unsigned int order) in xas_try_split() argument
1180 void *curr = xas_load(xas); 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()
1207 if (sibs || xas->xa_sibs != expected_sibs) { in xas_try_split()
1208 xas_destroy(xas); in xas_try_split()
1209 xas_set_err(xas, -EINVAL); in xas_try_split()
1215 xas->xa_lru, gfp); in xas_try_split()
1217 xas_destroy(xas); 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()
1223 __xas_init_node_for_split(xas, child, entry); in xas_try_split()
1225 xas->xa_alloc = rcu_dereference_raw(child->parent); in xas_try_split()
1232 node_set_marks(node, offset, child, xas->xa_sibs, in xas_try_split()
1238 xas_update(xas, child); in xas_try_split()
1242 unsigned int canon = offset - xas->xa_sibs; in xas_try_split()
1250 (xas->xa_sibs + 1); in xas_try_split()
1251 } while (offset-- > xas->xa_offset); in xas_try_split()
1255 xas_update(xas, node); in xas_try_split()
1275 void xas_pause(struct xa_state *xas) in xas_pause() argument
1277 struct xa_node *node = xas->xa_node; in xas_pause()
1279 if (xas_invalid(xas)) 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()
1306 void *__xas_prev(struct xa_state *xas) in __xas_prev() argument
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()
1313 return set_bounds(xas); in __xas_prev()
1314 if (xas_not_node(xas->xa_node)) in __xas_prev()
1315 return xas_load(xas); 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()
1324 return set_bounds(xas); 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()
1333 xas_set_offset(xas); in __xas_prev()
1345 void *__xas_next(struct xa_state *xas) in __xas_next() argument
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()
1352 return set_bounds(xas); in __xas_next()
1353 if (xas_not_node(xas->xa_node)) in __xas_next()
1354 return xas_load(xas); 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()
1363 return set_bounds(xas); 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()
1372 xas_set_offset(xas); in __xas_next()
1393 void *xas_find(struct xa_state *xas, unsigned long max) in xas_find() argument
1397 if (xas_error(xas) || xas->xa_node == XAS_BOUNDS) in xas_find()
1399 if (xas->xa_index > max) in xas_find()
1400 return set_bounds(xas); in xas_find()
1402 if (!xas->xa_node) { in xas_find()
1403 xas->xa_index = 1; in xas_find()
1404 return set_bounds(xas); in xas_find()
1405 } else if (xas->xa_node == XAS_RESTART) { in xas_find()
1406 entry = xas_load(xas); 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()
1414 xas_next_offset(xas); 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()
1432 xas_next_offset(xas); in xas_find()
1435 if (!xas->xa_node) in xas_find()
1436 xas->xa_node = XAS_BOUNDS; in xas_find()
1462 void *xas_find_marked(struct xa_state *xas, unsigned long max, xa_mark_t mark) in xas_find_marked() argument
1468 if (xas_error(xas)) in xas_find_marked()
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()
1510 offset = xas_find_chunk(xas, advance, mark); in xas_find_marked()
1511 if (offset > xas->xa_offset) { in xas_find_marked()
1513 xas_move_index(xas, 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()
1530 xas_set_offset(xas); in xas_find_marked()
1534 if (xas->xa_index > max) in xas_find_marked()
1536 return set_bounds(xas); in xas_find_marked()
1538 xas->xa_node = XAS_RESTART; in xas_find_marked()
1552 void *xas_find_conflict(struct xa_state *xas) in xas_find_conflict() argument
1556 if (xas_error(xas)) in xas_find_conflict()
1559 if (!xas->xa_node) in xas_find_conflict()
1562 if (xas_top(xas->xa_node)) { in xas_find_conflict()
1563 curr = xas_start(xas); in xas_find_conflict()
1568 curr = xas_descend(xas, 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()
1614 XA_STATE(xas, xa, index); in xa_load()
1619 entry = xa_zero_to_null(xas_load(&xas)); in xa_load()
1620 } while (xas_retry(&xas, entry)); in xa_load()
1627 static void *xas_result(struct xa_state *xas, void *curr) in xas_result() argument
1629 if (xas_error(xas)) in xas_result()
1630 curr = xas->xa_node; in xas_result()
1648 XA_STATE(xas, xa, index); in __xa_erase()
1649 return xas_result(&xas, xa_zero_to_null(xas_store(&xas, NULL))); in __xa_erase()
1694 XA_STATE(xas, xa, index); in __xa_store()
1703 curr = xas_store(&xas, entry); in __xa_store()
1705 xas_clear_mark(&xas, XA_FREE_MARK); in __xa_store()
1706 } while (__xas_nomem(&xas, gfp)); in __xa_store()
1708 return xas_result(&xas, xa_zero_to_null(curr)); in __xa_store()
1773 XA_STATE(xas, xa, index); in __xa_cmpxchg_raw()
1780 curr = xas_load(&xas); in __xa_cmpxchg_raw()
1782 xas_store(&xas, entry); in __xa_cmpxchg_raw()
1784 xas_clear_mark(&xas, XA_FREE_MARK); in __xa_cmpxchg_raw()
1786 } while (__xas_nomem(&xas, gfp)); in __xa_cmpxchg_raw()
1788 return xas_result(&xas, curr); in __xa_cmpxchg_raw()
1823 static void xas_set_range(struct xa_state *xas, unsigned long first, in xas_set_range() argument
1830 xas_set(xas, first); in xas_set_range()
1850 xas->xa_shift = shift; in xas_set_range()
1851 xas->xa_sibs = sibs; in xas_set_range()
1875 XA_STATE(xas, xa, 0); in xa_store_range()
1883 xas_lock(&xas); in xa_store_range()
1888 xas_set_order(&xas, last, order); in xa_store_range()
1889 xas_create(&xas, true); in xa_store_range()
1890 if (xas_error(&xas)) in xa_store_range()
1894 xas_set_range(&xas, first, last); in xa_store_range()
1895 xas_store(&xas, entry); in xa_store_range()
1896 if (xas_error(&xas)) in xa_store_range()
1898 first += xas_size(&xas); in xa_store_range()
1901 xas_unlock(&xas); in xa_store_range()
1902 } while (xas_nomem(&xas, gfp)); in xa_store_range()
1904 return xas_result(&xas, NULL); in xa_store_range()
1917 int xas_get_order(struct xa_state *xas) in xas_get_order() argument
1921 if (!xas->xa_node) in xas_get_order()
1924 XA_NODE_BUG_ON(xas->xa_node, xa_is_sibling(xa_entry(xas->xa, in xas_get_order()
1925 xas->xa_node, xas->xa_offset))); in xas_get_order()
1927 unsigned int slot = xas->xa_offset + (1 << order); in xas_get_order()
1931 if (!xa_is_sibling(xa_entry(xas->xa, xas->xa_node, slot))) in xas_get_order()
1936 order += xas->xa_node->shift; in xas_get_order()
1950 XA_STATE(xas, xa, index); in xa_get_order()
1955 entry = xas_load(&xas); in xa_get_order()
1957 order = xas_get_order(&xas); in xa_get_order()
1988 XA_STATE(xas, xa, 0); in __xa_alloc()
1999 xas.xa_index = limit.min; in __xa_alloc()
2000 xas_find_marked(&xas, limit.max, XA_FREE_MARK); in __xa_alloc()
2001 if (xas.xa_node == XAS_RESTART) in __xa_alloc()
2002 xas_set_err(&xas, -EBUSY); in __xa_alloc()
2004 *id = xas.xa_index; in __xa_alloc()
2005 xas_store(&xas, entry); in __xa_alloc()
2006 xas_clear_mark(&xas, XA_FREE_MARK); in __xa_alloc()
2007 } while (__xas_nomem(&xas, gfp)); in __xa_alloc()
2009 return xas_error(&xas); in __xa_alloc()
2078 XA_STATE(xas, xa, index); in __xa_set_mark()
2079 void *entry = xas_load(&xas); in __xa_set_mark()
2082 xas_set_mark(&xas, mark); in __xa_set_mark()
2096 XA_STATE(xas, xa, index); in __xa_clear_mark()
2097 void *entry = xas_load(&xas); in __xa_clear_mark()
2100 xas_clear_mark(&xas, mark); in __xa_clear_mark()
2118 XA_STATE(xas, xa, index); in xa_get_mark()
2122 entry = xas_start(&xas); in xa_get_mark()
2123 while (xas_get_mark(&xas, mark)) { in xa_get_mark()
2126 entry = xas_descend(&xas, xa_to_node(entry)); in xa_get_mark()
2192 XA_STATE(xas, xa, *indexp); in xa_find()
2198 entry = xas_find_marked(&xas, max, filter); in xa_find()
2200 entry = xas_find(&xas, max); in xa_find()
2201 } while (xas_retry(&xas, entry)); in xa_find()
2205 *indexp = xas.xa_index; in xa_find()
2210 static bool xas_sibling(struct xa_state *xas) in xas_sibling() argument
2212 struct xa_node *node = xas->xa_node; in xas_sibling()
2218 return (xas->xa_index & mask) > in xas_sibling()
2219 ((unsigned long)xas->xa_offset << node->shift); in xas_sibling()
2242 XA_STATE(xas, xa, *indexp + 1); in xa_find_after()
2245 if (xas.xa_index == 0) in xa_find_after()
2251 entry = xas_find_marked(&xas, max, filter); in xa_find_after()
2253 entry = xas_find(&xas, max); in xa_find_after()
2255 if (xas_invalid(&xas)) in xa_find_after()
2257 if (xas_sibling(&xas)) in xa_find_after()
2259 if (!xas_retry(&xas, entry)) in xa_find_after()
2265 *indexp = xas.xa_index; in xa_find_after()
2270 static unsigned int xas_extract_present(struct xa_state *xas, void **dst, in xas_extract_present() argument
2277 xas_for_each(xas, entry, max) { in xas_extract_present()
2278 if (xas_retry(xas, entry)) in xas_extract_present()
2289 static unsigned int xas_extract_marked(struct xa_state *xas, void **dst, in xas_extract_marked() argument
2296 xas_for_each_marked(xas, entry, max, mark) { in xas_extract_marked()
2297 if (xas_retry(xas, entry)) in xas_extract_marked()
2339 XA_STATE(xas, xa, start); in xa_extract()
2345 return xas_extract_marked(&xas, dst, max, n, filter); in xa_extract()
2346 return xas_extract_present(&xas, dst, max, n); in xa_extract()
2359 struct xa_state xas = { in xa_delete_node() local
2369 xas_store(&xas, NULL); in xa_delete_node()
2385 XA_STATE(xas, xa, 0); in xa_destroy()
2389 xas.xa_node = NULL; in xa_destroy()
2390 xas_lock_irqsave(&xas, flags); in xa_destroy()
2393 xas_init_marks(&xas); in xa_destroy()
2398 xas_free_nodes(&xas, xa_to_node(entry)); in xa_destroy()
2399 xas_unlock_irqrestore(&xas, flags); in xa_destroy()