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()
131 	if (!xas->xa_sibs)  in xas_squash_marks()
135 		unsigned long *marks = xas->xa_node->marks[mark];  in xas_squash_marks()
136 		if (find_next_bit(marks, limit, xas->xa_offset + 1) == limit)  in xas_squash_marks()
138 		__set_bit(xas->xa_offset, marks);  in xas_squash_marks()
139 		bitmap_clear(marks, xas->xa_offset + 1, xas->xa_sibs);  in xas_squash_marks()
149 static void xas_set_offset(struct xa_state *xas)  in xas_set_offset()  argument
151 	xas->xa_offset = get_offset(xas->xa_index, xas->xa_node);  in xas_set_offset()
155 static void xas_move_index(struct xa_state *xas, unsigned long offset)  in xas_move_index()  argument
157 	unsigned int shift = xas->xa_node->shift;  in xas_move_index()
158 	xas->xa_index &= ~XA_CHUNK_MASK << shift;  in xas_move_index()
159 	xas->xa_index += offset << shift;  in xas_move_index()
162 static void xas_next_offset(struct xa_state *xas)  in xas_next_offset()  argument
164 	xas->xa_offset++;  in xas_next_offset()
165 	xas_move_index(xas, xas->xa_offset);  in xas_next_offset()
168 static void *set_bounds(struct xa_state *xas)  in set_bounds()  argument
170 	xas->xa_node = XAS_BOUNDS;  in set_bounds()
181 static void *xas_start(struct xa_state *xas)  in xas_start()  argument
185 	if (xas_valid(xas))  in xas_start()
186 		return xas_reload(xas);  in xas_start()
187 	if (xas_error(xas))  in xas_start()
190 	entry = xa_head(xas->xa);  in xas_start()
192 		if (xas->xa_index)  in xas_start()
193 			return set_bounds(xas);  in xas_start()
195 		if ((xas->xa_index >> xa_to_node(entry)->shift) > XA_CHUNK_MASK)  in xas_start()
196 			return set_bounds(xas);  in xas_start()
199 	xas->xa_node = NULL;  in xas_start()
203 static void *xas_descend(struct xa_state *xas, struct xa_node *node)  in xas_descend()  argument
205 	unsigned int offset = get_offset(xas->xa_index, node);  in xas_descend()
206 	void *entry = xa_entry(xas->xa, node, offset);  in xas_descend()
208 	xas->xa_node = node;  in xas_descend()
211 		entry = xa_entry(xas->xa, node, offset);  in xas_descend()
216 	xas->xa_offset = offset;  in xas_descend()
235 void *xas_load(struct xa_state *xas)  in xas_load()  argument
237 	void *entry = xas_start(xas);  in xas_load()
242 		if (xas->xa_shift > node->shift)  in xas_load()
244 		entry = xas_descend(xas, node);  in xas_load()
268 void xas_destroy(struct xa_state *xas)  in xas_destroy()  argument
270 	struct xa_node *next, *node = xas->xa_alloc;  in xas_destroy()
276 		xas->xa_alloc = node = next;  in xas_destroy()
298 bool xas_nomem(struct xa_state *xas, gfp_t gfp)  in xas_nomem()  argument
300 	if (xas->xa_node != XA_ERROR(-ENOMEM)) {  in xas_nomem()
301 		xas_destroy(xas);  in xas_nomem()
304 	if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)  in xas_nomem()
306 	xas->xa_alloc = kmem_cache_alloc_lru(radix_tree_node_cachep, xas->xa_lru, gfp);  in xas_nomem()
307 	if (!xas->xa_alloc)  in xas_nomem()
309 	xas->xa_alloc->parent = NULL;  in xas_nomem()
310 	XA_NODE_BUG_ON(xas->xa_alloc, !list_empty(&xas->xa_alloc->private_list));  in xas_nomem()
311 	xas->xa_node = XAS_RESTART;  in xas_nomem()
325 static bool __xas_nomem(struct xa_state *xas, gfp_t gfp)  in __xas_nomem()  argument
326 	__must_hold(xas->xa->xa_lock)  in __xas_nomem()
328 	unsigned int lock_type = xa_lock_type(xas->xa);  in __xas_nomem()
330 	if (xas->xa_node != XA_ERROR(-ENOMEM)) {  in __xas_nomem()
331 		xas_destroy(xas);  in __xas_nomem()
334 	if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)  in __xas_nomem()
337 		xas_unlock_type(xas, lock_type);  in __xas_nomem()
338 		xas->xa_alloc = kmem_cache_alloc_lru(radix_tree_node_cachep, xas->xa_lru, gfp);  in __xas_nomem()
339 		xas_lock_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()
343 	if (!xas->xa_alloc)  in __xas_nomem()
345 	xas->xa_alloc->parent = NULL;  in __xas_nomem()
346 	XA_NODE_BUG_ON(xas->xa_alloc, !list_empty(&xas->xa_alloc->private_list));  in __xas_nomem()
347 	xas->xa_node = XAS_RESTART;  in __xas_nomem()
351 static void xas_update(struct xa_state *xas, struct xa_node *node)  in xas_update()  argument
353 	if (xas->xa_update)  in xas_update()
354 		xas->xa_update(node);  in xas_update()
359 static void *xas_alloc(struct xa_state *xas, unsigned int shift)  in xas_alloc()  argument
361 	struct xa_node *parent = xas->xa_node;  in xas_alloc()
362 	struct xa_node *node = xas->xa_alloc;  in xas_alloc()
364 	if (xas_invalid(xas))  in xas_alloc()
368 		xas->xa_alloc = NULL;  in xas_alloc()
372 		if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)  in xas_alloc()
375 		node = kmem_cache_alloc_lru(radix_tree_node_cachep, xas->xa_lru, gfp);  in xas_alloc()
377 			xas_set_err(xas, -ENOMEM);  in xas_alloc()
383 		node->offset = xas->xa_offset;  in xas_alloc()
386 		xas_update(xas, parent);  in xas_alloc()
393 	RCU_INIT_POINTER(node->parent, xas->xa_node);  in xas_alloc()
394 	node->array = xas->xa;  in xas_alloc()
401 static unsigned long xas_size(const struct xa_state *xas)  in xas_size()  argument
403 	return (xas->xa_sibs + 1UL) << xas->xa_shift;  in xas_size()
413 static unsigned long xas_max(struct xa_state *xas)  in xas_max()  argument
415 	unsigned long max = xas->xa_index;  in xas_max()
418 	if (xas->xa_shift || xas->xa_sibs) {  in xas_max()
419 		unsigned long mask = xas_size(xas) - 1;  in xas_max()
437 static void xas_shrink(struct xa_state *xas)  in xas_shrink()  argument
439 	struct xarray *xa = xas->xa;  in xas_shrink()
440 	struct xa_node *node = xas->xa_node;  in xas_shrink()
455 		xas->xa_node = XAS_BOUNDS;  in xas_shrink()
465 		xas_update(xas, node);  in xas_shrink()
481 static void xas_delete_node(struct xa_state *xas)  in xas_delete_node()  argument
483 	struct xa_node *node = xas->xa_node;  in xas_delete_node()
492 		parent = xa_parent_locked(xas->xa, node);  in xas_delete_node()
493 		xas->xa_node = parent;  in xas_delete_node()
494 		xas->xa_offset = node->offset;  in xas_delete_node()
498 			xas->xa->xa_head = NULL;  in xas_delete_node()
499 			xas->xa_node = XAS_BOUNDS;  in xas_delete_node()
503 		parent->slots[xas->xa_offset] = NULL;  in xas_delete_node()
507 		xas_update(xas, node);  in xas_delete_node()
511 		xas_shrink(xas);  in xas_delete_node()
523 static void xas_free_nodes(struct xa_state *xas, struct xa_node *top)  in xas_free_nodes()  argument
529 		void *entry = xa_entry_locked(xas->xa, node, offset);  in xas_free_nodes()
542 			parent = xa_parent_locked(xas->xa, node);  in xas_free_nodes()
546 			xas_update(xas, node);  in xas_free_nodes()
559 static int xas_expand(struct xa_state *xas, void *head)  in xas_expand()  argument
561 	struct xarray *xa = xas->xa;  in xas_expand()
564 	unsigned long max = xas_max(xas);  in xas_expand()
576 	xas->xa_node = NULL;  in xas_expand()
582 		node = xas_alloc(xas, shift);  in xas_expand()
617 		xas_update(xas, node);  in xas_expand()
622 	xas->xa_node = node;  in xas_expand()
639 static void *xas_create(struct xa_state *xas, bool allow_root)  in xas_create()  argument
641 	struct xarray *xa = xas->xa;  in xas_create()
644 	struct xa_node *node = xas->xa_node;  in xas_create()
646 	unsigned int order = xas->xa_shift;  in xas_create()
650 		xas->xa_node = NULL;  in xas_create()
653 		shift = xas_expand(xas, entry);  in xas_create()
660 	} else if (xas_error(xas)) {  in xas_create()
663 		unsigned int offset = xas->xa_offset;  in xas_create()
677 			node = xas_alloc(xas, shift);  in xas_create()
688 		entry = xas_descend(xas, node);  in xas_create()
689 		slot = &node->slots[xas->xa_offset];  in xas_create()
704 void xas_create_range(struct xa_state *xas)  in xas_create_range()  argument
706 	unsigned long index = xas->xa_index;  in xas_create_range()
707 	unsigned char shift = xas->xa_shift;  in xas_create_range()
708 	unsigned char sibs = xas->xa_sibs;  in xas_create_range()
710 	xas->xa_index |= ((sibs + 1UL) << shift) - 1;  in xas_create_range()
711 	if (xas_is_node(xas) && xas->xa_node->shift == xas->xa_shift)  in xas_create_range()
712 		xas->xa_offset |= sibs;  in xas_create_range()
713 	xas->xa_shift = 0;  in xas_create_range()
714 	xas->xa_sibs = 0;  in xas_create_range()
717 		xas_create(xas, true);  in xas_create_range()
718 		if (xas_error(xas))  in xas_create_range()
720 		if (xas->xa_index <= (index | XA_CHUNK_MASK))  in xas_create_range()
722 		xas->xa_index -= XA_CHUNK_SIZE;  in xas_create_range()
725 			struct xa_node *node = xas->xa_node;  in xas_create_range()
728 			xas->xa_node = xa_parent_locked(xas->xa, node);  in xas_create_range()
729 			xas->xa_offset = node->offset - 1;  in xas_create_range()
736 	xas->xa_shift = shift;  in xas_create_range()
737 	xas->xa_sibs = sibs;  in xas_create_range()
738 	xas->xa_index = index;  in xas_create_range()
741 	xas->xa_index = index;  in xas_create_range()
742 	if (xas->xa_node)  in xas_create_range()
743 		xas_set_offset(xas);  in xas_create_range()
747 static void update_node(struct xa_state *xas, struct xa_node *node,  in update_node()  argument
757 	xas_update(xas, node);  in update_node()
759 		xas_delete_node(xas);  in update_node()
775 void *xas_store(struct xa_state *xas, void *entry)  in xas_store()  argument
778 	void __rcu **slot = &xas->xa->xa_head;  in xas_store()
787 		first = xas_create(xas, allow_root);  in xas_store()
789 		first = xas_load(xas);  in xas_store()
792 	if (xas_invalid(xas))  in xas_store()
794 	node = xas->xa_node;  in xas_store()
795 	if (node && (xas->xa_shift < node->shift))  in xas_store()
796 		xas->xa_sibs = 0;  in xas_store()
797 	if ((first == entry) && !xas->xa_sibs)  in xas_store()
801 	offset = xas->xa_offset;  in xas_store()
802 	max = xas->xa_offset + xas->xa_sibs;  in xas_store()
805 		if (xas->xa_sibs)  in xas_store()
806 			xas_squash_marks(xas);  in xas_store()
809 		xas_init_marks(xas);  in xas_store()
821 			xas_free_nodes(xas, xa_to_node(next));  in xas_store()
830 				entry = xa_mk_sibling(xas->xa_offset);  in xas_store()
835 		next = xa_entry_locked(xas->xa, node, ++offset);  in xas_store()
844 	update_node(xas, node, count, values);  in xas_store()
857 bool xas_get_mark(const struct xa_state *xas, xa_mark_t mark)  in xas_get_mark()  argument
859 	if (xas_invalid(xas))  in xas_get_mark()
861 	if (!xas->xa_node)  in xas_get_mark()
862 		return xa_marked(xas->xa, mark);  in xas_get_mark()
863 	return node_get_mark(xas->xa_node, xas->xa_offset, mark);  in xas_get_mark()
876 void xas_set_mark(const struct xa_state *xas, xa_mark_t mark)  in xas_set_mark()  argument
878 	struct xa_node *node = xas->xa_node;  in xas_set_mark()
879 	unsigned int offset = xas->xa_offset;  in xas_set_mark()
881 	if (xas_invalid(xas))  in xas_set_mark()
888 		node = xa_parent_locked(xas->xa, node);  in xas_set_mark()
891 	if (!xa_marked(xas->xa, mark))  in xas_set_mark()
892 		xa_mark_set(xas->xa, mark);  in xas_set_mark()
905 void xas_clear_mark(const struct xa_state *xas, xa_mark_t mark)  in xas_clear_mark()  argument
907 	struct xa_node *node = xas->xa_node;  in xas_clear_mark()
908 	unsigned int offset = xas->xa_offset;  in xas_clear_mark()
910 	if (xas_invalid(xas))  in xas_clear_mark()
920 		node = xa_parent_locked(xas->xa, node);  in xas_clear_mark()
923 	if (xa_marked(xas->xa, mark))  in xas_clear_mark()
924 		xa_mark_clear(xas->xa, mark);  in xas_clear_mark()
939 void xas_init_marks(const struct xa_state *xas)  in xas_init_marks()  argument
944 		if (xa_track_free(xas->xa) && mark == XA_FREE_MARK)  in xas_init_marks()
945 			xas_set_mark(xas, mark);  in xas_init_marks()
947 			xas_clear_mark(xas, mark);  in xas_init_marks()
1003 void xas_split_alloc(struct xa_state *xas, void *entry, unsigned int order,  in xas_split_alloc()  argument
1007 	unsigned int mask = xas->xa_sibs;  in xas_split_alloc()
1010 	if (WARN_ON(xas->xa_shift + 2 * XA_CHUNK_SHIFT < order))  in xas_split_alloc()
1012 	if (xas->xa_shift + XA_CHUNK_SHIFT > order)  in xas_split_alloc()
1020 		node = kmem_cache_alloc_lru(radix_tree_node_cachep, xas->xa_lru, gfp);  in xas_split_alloc()
1023 		node->array = xas->xa;  in xas_split_alloc()
1032 		RCU_INIT_POINTER(node->parent, xas->xa_alloc);  in xas_split_alloc()
1033 		xas->xa_alloc = node;  in xas_split_alloc()
1038 	xas_destroy(xas);  in xas_split_alloc()
1039 	xas_set_err(xas, -ENOMEM);  in xas_split_alloc()
1054 void xas_split(struct xa_state *xas, void *entry, unsigned int order)  in xas_split()  argument
1059 	void *curr = xas_load(xas);  in xas_split()
1062 	node = xas->xa_node;  in xas_split()
1066 	marks = node_get_marks(node, xas->xa_offset);  in xas_split()
1068 	offset = xas->xa_offset + sibs;  in xas_split()
1070 		if (xas->xa_shift < node->shift) {  in xas_split()
1071 			struct xa_node *child = xas->xa_alloc;  in xas_split()
1073 			xas->xa_alloc = rcu_dereference_raw(child->parent);  in xas_split()
1085 			xas_update(xas, child);  in xas_split()
1087 			unsigned int canon = offset - xas->xa_sibs;  in xas_split()
1095 					(xas->xa_sibs + 1);  in xas_split()
1097 	} while (offset-- > xas->xa_offset);  in xas_split()
1100 	xas_update(xas, node);  in xas_split()
1120 void xas_pause(struct xa_state *xas)  in xas_pause()  argument
1122 	struct xa_node *node = xas->xa_node;  in xas_pause()
1124 	if (xas_invalid(xas))  in xas_pause()
1127 	xas->xa_node = XAS_RESTART;  in xas_pause()
1129 		unsigned long offset = xas->xa_offset;  in xas_pause()
1131 			if (!xa_is_sibling(xa_entry(xas->xa, node, offset)))  in xas_pause()
1134 		xas->xa_index += (offset - xas->xa_offset) << node->shift;  in xas_pause()
1135 		if (xas->xa_index == 0)  in xas_pause()
1136 			xas->xa_node = XAS_BOUNDS;  in xas_pause()
1138 		xas->xa_index++;  in xas_pause()
1150 void *__xas_prev(struct xa_state *xas)  in __xas_prev()  argument
1154 	if (!xas_frozen(xas->xa_node))  in __xas_prev()
1155 		xas->xa_index--;  in __xas_prev()
1156 	if (!xas->xa_node)  in __xas_prev()
1157 		return set_bounds(xas);  in __xas_prev()
1158 	if (xas_not_node(xas->xa_node))  in __xas_prev()
1159 		return xas_load(xas);  in __xas_prev()
1161 	if (xas->xa_offset != get_offset(xas->xa_index, xas->xa_node))  in __xas_prev()
1162 		xas->xa_offset--;  in __xas_prev()
1164 	while (xas->xa_offset == 255) {  in __xas_prev()
1165 		xas->xa_offset = xas->xa_node->offset - 1;  in __xas_prev()
1166 		xas->xa_node = xa_parent(xas->xa, xas->xa_node);  in __xas_prev()
1167 		if (!xas->xa_node)  in __xas_prev()
1168 			return set_bounds(xas);  in __xas_prev()
1172 		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);  in __xas_prev()
1176 		xas->xa_node = xa_to_node(entry);  in __xas_prev()
1177 		xas_set_offset(xas);  in __xas_prev()
1189 void *__xas_next(struct xa_state *xas)  in __xas_next()  argument
1193 	if (!xas_frozen(xas->xa_node))  in __xas_next()
1194 		xas->xa_index++;  in __xas_next()
1195 	if (!xas->xa_node)  in __xas_next()
1196 		return set_bounds(xas);  in __xas_next()
1197 	if (xas_not_node(xas->xa_node))  in __xas_next()
1198 		return xas_load(xas);  in __xas_next()
1200 	if (xas->xa_offset != get_offset(xas->xa_index, xas->xa_node))  in __xas_next()
1201 		xas->xa_offset++;  in __xas_next()
1203 	while (xas->xa_offset == XA_CHUNK_SIZE) {  in __xas_next()
1204 		xas->xa_offset = xas->xa_node->offset + 1;  in __xas_next()
1205 		xas->xa_node = xa_parent(xas->xa, xas->xa_node);  in __xas_next()
1206 		if (!xas->xa_node)  in __xas_next()
1207 			return set_bounds(xas);  in __xas_next()
1211 		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);  in __xas_next()
1215 		xas->xa_node = xa_to_node(entry);  in __xas_next()
1216 		xas_set_offset(xas);  in __xas_next()
1237 void *xas_find(struct xa_state *xas, unsigned long max)  in xas_find()  argument
1241 	if (xas_error(xas) || xas->xa_node == XAS_BOUNDS)  in xas_find()
1243 	if (xas->xa_index > max)  in xas_find()
1244 		return set_bounds(xas);  in xas_find()
1246 	if (!xas->xa_node) {  in xas_find()
1247 		xas->xa_index = 1;  in xas_find()
1248 		return set_bounds(xas);  in xas_find()
1249 	} else if (xas->xa_node == XAS_RESTART) {  in xas_find()
1250 		entry = xas_load(xas);  in xas_find()
1251 		if (entry || xas_not_node(xas->xa_node))  in xas_find()
1253 	} else if (!xas->xa_node->shift &&  in xas_find()
1254 		    xas->xa_offset != (xas->xa_index & XA_CHUNK_MASK)) {  in xas_find()
1255 		xas->xa_offset = ((xas->xa_index - 1) & XA_CHUNK_MASK) + 1;  in xas_find()
1258 	xas_next_offset(xas);  in xas_find()
1260 	while (xas->xa_node && (xas->xa_index <= max)) {  in xas_find()
1261 		if (unlikely(xas->xa_offset == XA_CHUNK_SIZE)) {  in xas_find()
1262 			xas->xa_offset = xas->xa_node->offset + 1;  in xas_find()
1263 			xas->xa_node = xa_parent(xas->xa, xas->xa_node);  in xas_find()
1267 		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);  in xas_find()
1269 			xas->xa_node = xa_to_node(entry);  in xas_find()
1270 			xas->xa_offset = 0;  in xas_find()
1276 		xas_next_offset(xas);  in xas_find()
1279 	if (!xas->xa_node)  in xas_find()
1280 		xas->xa_node = XAS_BOUNDS;  in xas_find()
1306 void *xas_find_marked(struct xa_state *xas, unsigned long max, xa_mark_t mark)  in xas_find_marked()  argument
1312 	if (xas_error(xas))  in xas_find_marked()
1314 	if (xas->xa_index > max)  in xas_find_marked()
1317 	if (!xas->xa_node) {  in xas_find_marked()
1318 		xas->xa_index = 1;  in xas_find_marked()
1320 	} else if (xas_top(xas->xa_node)) {  in xas_find_marked()
1322 		entry = xa_head(xas->xa);  in xas_find_marked()
1323 		xas->xa_node = NULL;  in xas_find_marked()
1324 		if (xas->xa_index > max_index(entry))  in xas_find_marked()
1327 			if (xa_marked(xas->xa, mark))  in xas_find_marked()
1329 			xas->xa_index = 1;  in xas_find_marked()
1332 		xas->xa_node = xa_to_node(entry);  in xas_find_marked()
1333 		xas->xa_offset = xas->xa_index >> xas->xa_node->shift;  in xas_find_marked()
1336 	while (xas->xa_index <= max) {  in xas_find_marked()
1337 		if (unlikely(xas->xa_offset == XA_CHUNK_SIZE)) {  in xas_find_marked()
1338 			xas->xa_offset = xas->xa_node->offset + 1;  in xas_find_marked()
1339 			xas->xa_node = xa_parent(xas->xa, xas->xa_node);  in xas_find_marked()
1340 			if (!xas->xa_node)  in xas_find_marked()
1347 			entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);  in xas_find_marked()
1349 				xas->xa_offset = xa_to_sibling(entry);  in xas_find_marked()
1350 				xas_move_index(xas, xas->xa_offset);  in xas_find_marked()
1354 		offset = xas_find_chunk(xas, advance, mark);  in xas_find_marked()
1355 		if (offset > xas->xa_offset) {  in xas_find_marked()
1357 			xas_move_index(xas, offset);  in xas_find_marked()
1359 			if ((xas->xa_index - 1) >= max)  in xas_find_marked()
1361 			xas->xa_offset = offset;  in xas_find_marked()
1366 		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);  in xas_find_marked()
1367 		if (!entry && !(xa_track_free(xas->xa) && mark == XA_FREE_MARK))  in xas_find_marked()
1371 		xas->xa_node = xa_to_node(entry);  in xas_find_marked()
1372 		xas_set_offset(xas);  in xas_find_marked()
1376 	if (xas->xa_index > max)  in xas_find_marked()
1378 	return set_bounds(xas);  in xas_find_marked()
1380 	xas->xa_node = XAS_RESTART;  in xas_find_marked()
1394 void *xas_find_conflict(struct xa_state *xas)  in xas_find_conflict()  argument
1398 	if (xas_error(xas))  in xas_find_conflict()
1401 	if (!xas->xa_node)  in xas_find_conflict()
1404 	if (xas_top(xas->xa_node)) {  in xas_find_conflict()
1405 		curr = xas_start(xas);  in xas_find_conflict()
1410 			curr = xas_descend(xas, node);  in xas_find_conflict()
1416 	if (xas->xa_node->shift > xas->xa_shift)  in xas_find_conflict()
1420 		if (xas->xa_node->shift == xas->xa_shift) {  in xas_find_conflict()
1421 			if ((xas->xa_offset & xas->xa_sibs) == xas->xa_sibs)  in xas_find_conflict()
1423 		} else if (xas->xa_offset == XA_CHUNK_MASK) {  in xas_find_conflict()
1424 			xas->xa_offset = xas->xa_node->offset;  in xas_find_conflict()
1425 			xas->xa_node = xa_parent_locked(xas->xa, xas->xa_node);  in xas_find_conflict()
1426 			if (!xas->xa_node)  in xas_find_conflict()
1430 		curr = xa_entry_locked(xas->xa, xas->xa_node, ++xas->xa_offset);  in xas_find_conflict()
1434 			xas->xa_node = xa_to_node(curr);  in xas_find_conflict()
1435 			xas->xa_offset = 0;  in xas_find_conflict()
1436 			curr = xa_entry_locked(xas->xa, xas->xa_node, 0);  in xas_find_conflict()
1441 	xas->xa_offset -= xas->xa_sibs;  in xas_find_conflict()
1456 	XA_STATE(xas, xa, index);  in xa_load()
1461 		entry = xas_load(&xas);  in xa_load()
1464 	} while (xas_retry(&xas, entry));  in xa_load()
1471 static void *xas_result(struct xa_state *xas, void *curr)  in xas_result()  argument
1475 	if (xas_error(xas))  in xas_result()
1476 		curr = xas->xa_node;  in xas_result()
1494 	XA_STATE(xas, xa, index);  in __xa_erase()
1495 	return xas_result(&xas, xas_store(&xas, NULL));  in __xa_erase()
1540 	XA_STATE(xas, xa, index);  in __xa_store()
1549 		curr = xas_store(&xas, entry);  in __xa_store()
1551 			xas_clear_mark(&xas, XA_FREE_MARK);  in __xa_store()
1552 	} while (__xas_nomem(&xas, gfp));  in __xa_store()
1554 	return xas_result(&xas, curr);  in __xa_store()
1606 	XA_STATE(xas, xa, index);  in __xa_cmpxchg()
1613 		curr = xas_load(&xas);  in __xa_cmpxchg()
1615 			xas_store(&xas, entry);  in __xa_cmpxchg()
1617 				xas_clear_mark(&xas, XA_FREE_MARK);  in __xa_cmpxchg()
1619 	} while (__xas_nomem(&xas, gfp));  in __xa_cmpxchg()
1621 	return xas_result(&xas, curr);  in __xa_cmpxchg()
1643 	XA_STATE(xas, xa, index);  in __xa_insert()
1652 		curr = xas_load(&xas);  in __xa_insert()
1654 			xas_store(&xas, entry);  in __xa_insert()
1656 				xas_clear_mark(&xas, XA_FREE_MARK);  in __xa_insert()
1658 			xas_set_err(&xas, -EBUSY);  in __xa_insert()
1660 	} while (__xas_nomem(&xas, gfp));  in __xa_insert()
1662 	return xas_error(&xas);  in __xa_insert()
1667 static void xas_set_range(struct xa_state *xas, unsigned long first,  in xas_set_range()  argument
1674 	xas_set(xas, first);  in xas_set_range()
1694 	xas->xa_shift = shift;  in xas_set_range()
1695 	xas->xa_sibs = sibs;  in xas_set_range()
1719 	XA_STATE(xas, xa, 0);  in xa_store_range()
1727 		xas_lock(&xas);  in xa_store_range()
1732 			xas_set_order(&xas, last, order);  in xa_store_range()
1733 			xas_create(&xas, true);  in xa_store_range()
1734 			if (xas_error(&xas))  in xa_store_range()
1738 			xas_set_range(&xas, first, last);  in xa_store_range()
1739 			xas_store(&xas, entry);  in xa_store_range()
1740 			if (xas_error(&xas))  in xa_store_range()
1742 			first += xas_size(&xas);  in xa_store_range()
1745 		xas_unlock(&xas);  in xa_store_range()
1746 	} while (xas_nomem(&xas, gfp));  in xa_store_range()
1748 	return xas_result(&xas, NULL);  in xa_store_range()
1761 	XA_STATE(xas, xa, index);  in xa_get_order()
1766 	entry = xas_load(&xas);  in xa_get_order()
1771 	if (!xas.xa_node)  in xa_get_order()
1775 		unsigned int slot = xas.xa_offset + (1 << order);  in xa_get_order()
1779 		if (!xa_is_sibling(xas.xa_node->slots[slot]))  in xa_get_order()
1784 	order += xas.xa_node->shift;  in xa_get_order()
1816 	XA_STATE(xas, xa, 0);  in __xa_alloc()
1827 		xas.xa_index = limit.min;  in __xa_alloc()
1828 		xas_find_marked(&xas, limit.max, XA_FREE_MARK);  in __xa_alloc()
1829 		if (xas.xa_node == XAS_RESTART)  in __xa_alloc()
1830 			xas_set_err(&xas, -EBUSY);  in __xa_alloc()
1832 			*id = xas.xa_index;  in __xa_alloc()
1833 		xas_store(&xas, entry);  in __xa_alloc()
1834 		xas_clear_mark(&xas, XA_FREE_MARK);  in __xa_alloc()
1835 	} while (__xas_nomem(&xas, gfp));  in __xa_alloc()
1837 	return xas_error(&xas);  in __xa_alloc()
1906 	XA_STATE(xas, xa, index);  in __xa_set_mark()
1907 	void *entry = xas_load(&xas);  in __xa_set_mark()
1910 		xas_set_mark(&xas, mark);  in __xa_set_mark()
1924 	XA_STATE(xas, xa, index);  in __xa_clear_mark()
1925 	void *entry = xas_load(&xas);  in __xa_clear_mark()
1928 		xas_clear_mark(&xas, mark);  in __xa_clear_mark()
1946 	XA_STATE(xas, xa, index);  in xa_get_mark()
1950 	entry = xas_start(&xas);  in xa_get_mark()
1951 	while (xas_get_mark(&xas, mark)) {  in xa_get_mark()
1954 		entry = xas_descend(&xas, xa_to_node(entry));  in xa_get_mark()
2020 	XA_STATE(xas, xa, *indexp);  in xa_find()
2026 			entry = xas_find_marked(&xas, max, filter);  in xa_find()
2028 			entry = xas_find(&xas, max);  in xa_find()
2029 	} while (xas_retry(&xas, entry));  in xa_find()
2033 		*indexp = xas.xa_index;  in xa_find()
2038 static bool xas_sibling(struct xa_state *xas)  in xas_sibling()  argument
2040 	struct xa_node *node = xas->xa_node;  in xas_sibling()
2046 	return (xas->xa_index & mask) >  in xas_sibling()
2047 		((unsigned long)xas->xa_offset << node->shift);  in xas_sibling()
2070 	XA_STATE(xas, xa, *indexp + 1);  in xa_find_after()
2073 	if (xas.xa_index == 0)  in xa_find_after()
2079 			entry = xas_find_marked(&xas, max, filter);  in xa_find_after()
2081 			entry = xas_find(&xas, max);  in xa_find_after()
2083 		if (xas_invalid(&xas))  in xa_find_after()
2085 		if (xas_sibling(&xas))  in xa_find_after()
2087 		if (!xas_retry(&xas, entry))  in xa_find_after()
2093 		*indexp = xas.xa_index;  in xa_find_after()
2098 static unsigned int xas_extract_present(struct xa_state *xas, void **dst,  in xas_extract_present()  argument
2105 	xas_for_each(xas, entry, max) {  in xas_extract_present()
2106 		if (xas_retry(xas, entry))  in xas_extract_present()
2117 static unsigned int xas_extract_marked(struct xa_state *xas, void **dst,  in xas_extract_marked()  argument
2124 	xas_for_each_marked(xas, entry, max, mark) {  in xas_extract_marked()
2125 		if (xas_retry(xas, entry))  in xas_extract_marked()
2167 	XA_STATE(xas, xa, start);  in xa_extract()
2173 		return xas_extract_marked(&xas, dst, max, n, filter);  in xa_extract()
2174 	return xas_extract_present(&xas, dst, max, n);  in xa_extract()
2187 	struct xa_state xas = {  in xa_delete_node()  local
2197 	xas_store(&xas, NULL);  in xa_delete_node()
2213 	XA_STATE(xas, xa, 0);  in xa_destroy()
2217 	xas.xa_node = NULL;  in xa_destroy()
2218 	xas_lock_irqsave(&xas, flags);  in xa_destroy()
2221 	xas_init_marks(&xas);  in xa_destroy()
2226 		xas_free_nodes(&xas, xa_to_node(entry));  in xa_destroy()
2227 	xas_unlock_irqrestore(&xas, flags);  in xa_destroy()