80 static inline unsigned long *node_marks(struct xa_node *node, xa_mark_t mark)  in node_marks()  argument
82 	return node->marks[(__force unsigned)mark];  in node_marks()
85 static inline bool node_get_mark(struct xa_node *node,  in node_get_mark()  argument
88 	return test_bit(offset, node_marks(node, mark));  in node_get_mark()
92 static inline bool node_set_mark(struct xa_node *node, unsigned int offset,  in node_set_mark()  argument
95 	return __test_and_set_bit(offset, node_marks(node, mark));  in node_set_mark()
99 static inline bool node_clear_mark(struct xa_node *node, unsigned int offset,  in node_clear_mark()  argument
102 	return __test_and_clear_bit(offset, node_marks(node, mark));  in node_clear_mark()
105 static inline bool node_any_mark(struct xa_node *node, xa_mark_t mark)  in node_any_mark()  argument
107 	return !bitmap_empty(node_marks(node, mark), XA_CHUNK_SIZE);  in node_any_mark()
110 static inline void node_mark_all(struct xa_node *node, xa_mark_t mark)  in node_mark_all()  argument
112 	bitmap_fill(node_marks(node, mark), XA_CHUNK_SIZE);  in node_mark_all()
145 static unsigned int get_offset(unsigned long index, struct xa_node *node)  in get_offset()  argument
147 	return (index >> node->shift) & XA_CHUNK_MASK;  in get_offset()
205 					struct xa_node *node)  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()
214 		if (node->shift && xa_is_node(entry))  in xas_descend()
242 		struct xa_node *node = xa_to_node(entry);  in xas_load()  local
244 		if (xas->xa_shift > node->shift)  in xas_load()
246 		entry = xas_descend(xas, node);  in xas_load()
247 		if (node->shift == 0)  in xas_load()
256 static void xa_node_free(struct xa_node *node)  in xa_node_free()  argument
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()
272 	struct xa_node *next, *node = xas->xa_alloc;  in xas_destroy()  local
274 	while (node) {  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()
354 static void xas_update(struct xa_state *xas, struct xa_node *node)  in xas_update()  argument
357 		xas->xa_update(node);  in xas_update()
359 		XA_NODE_BUG_ON(node, !list_empty(&node->private_list));  in xas_update()
365 	struct xa_node *node = xas->xa_alloc;  in xas_alloc()  local
370 	if (node) {  in xas_alloc()
378 		node = kmem_cache_alloc_lru(radix_tree_node_cachep, xas->xa_lru, gfp);  in xas_alloc()
379 		if (!node) {  in xas_alloc()
386 		node->offset = xas->xa_offset;  in xas_alloc()
388 		XA_NODE_BUG_ON(node, parent->count > XA_CHUNK_SIZE);  in xas_alloc()
391 	XA_NODE_BUG_ON(node, shift > BITS_PER_LONG);  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()
399 	return node;  in xas_alloc()
448 	struct xa_node *node = xas->xa_node;  in xas_shrink()  local
453 		XA_NODE_BUG_ON(node, node->count > XA_CHUNK_SIZE);  in xas_shrink()
454 		if (node->count != 1)  in xas_shrink()
456 		entry = xa_entry_locked(xa, node, 0);  in xas_shrink()
459 		if (!xa_is_node(entry) && node->shift)  in xas_shrink()
466 		if (xa_track_free(xa) && !node_get_mark(node, 0, XA_FREE_MARK))  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()
473 		xas_update(xas, node);  in xas_shrink()
474 		xa_node_free(node);  in xas_shrink()
477 		node = xa_to_node(entry);  in xas_shrink()
478 		node->parent = NULL;  in xas_shrink()
491 	struct xa_node *node = xas->xa_node;  in xas_delete_node()  local
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()
502 		xas->xa_offset = node->offset;  in xas_delete_node()
503 		xa_node_free(node);  in xas_delete_node()
514 		node = parent;  in xas_delete_node()
515 		xas_update(xas, node);  in xas_delete_node()
518 	if (!node->parent)  in xas_delete_node()
534 	struct xa_node *node = top;  in xas_free_nodes()  local
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()
540 			node = xa_to_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()
554 			xas_update(xas, node);  in xas_free_nodes()
555 			xa_node_free(node);  in xas_free_nodes()
556 			if (node == top)  in xas_free_nodes()
558 			node = parent;  in xas_free_nodes()
570 	struct xa_node *node = NULL;  in xas_expand()  local
581 		node = xa_to_node(head);  in xas_expand()
582 		shift = node->shift + XA_CHUNK_SHIFT;  in xas_expand()
589 		XA_NODE_BUG_ON(node, shift > BITS_PER_LONG);  in xas_expand()
590 		node = xas_alloc(xas, shift);  in xas_expand()
591 		if (!node)  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()
602 				node_mark_all(node, XA_FREE_MARK);  in xas_expand()
604 					node_clear_mark(node, 0, XA_FREE_MARK);  in xas_expand()
608 				node_set_mark(node, 0, mark);  in xas_expand()
621 			rcu_assign_pointer(xa_to_node(head)->parent, node);  in xas_expand()
623 		head = xa_mk_node(node);  in xas_expand()
625 		xas_update(xas, node);  in xas_expand()
630 	xas->xa_node = node;  in xas_expand()
652 	struct xa_node *node = xas->xa_node;  in xas_create()  local
656 	if (xas_top(node)) {  in xas_create()
670 	} else if (node) {  in xas_create()
673 		shift = node->shift;  in xas_create()
674 		entry = xa_entry_locked(xa, node, offset);  in xas_create()
675 		slot = &node->slots[offset];  in xas_create()
685 			node = xas_alloc(xas, shift);  in xas_create()
686 			if (!node)  in xas_create()
689 				node_mark_all(node, XA_FREE_MARK);  in xas_create()
690 			rcu_assign_pointer(*slot, xa_mk_node(node));  in xas_create()
692 			node = xa_to_node(entry);  in xas_create()
696 		entry = xas_descend(xas, node);  in xas_create()
697 		slot = &node->slots[xas->xa_offset];  in xas_create()
733 			struct xa_node *node = xas->xa_node;  in xas_create_range()  local
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()
755 static void update_node(struct xa_state *xas, struct xa_node *node,  in update_node()  argument
758 	if (!node || (!count && !values))  in update_node()
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()
765 	xas_update(xas, node);  in update_node()
785 	struct xa_node *node;  in xas_store()  local
802 	node = xas->xa_node;  in xas_store()
803 	if (node && (xas->xa_shift < node->shift))  in xas_store()
811 	if (node) {  in xas_store()
812 		slot = &node->slots[offset];  in xas_store()
828 		if (xa_is_node(next) && (!node || node->shift))  in xas_store()
830 		if (!node)  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()
886 	struct xa_node *node = xas->xa_node;  in xas_set_mark()  local
892 	while (node) {  in xas_set_mark()
893 		if (node_set_mark(node, offset, mark))  in xas_set_mark()
895 		offset = node->offset;  in xas_set_mark()
896 		node = xa_parent_locked(xas->xa, node);  in xas_set_mark()
915 	struct xa_node *node = xas->xa_node;  in xas_clear_mark()  local
921 	while (node) {  in xas_clear_mark()
922 		if (!node_clear_mark(node, offset, mark))  in xas_clear_mark()
924 		if (node_any_mark(node, mark))  in xas_clear_mark()
927 		offset = node->offset;  in xas_clear_mark()
928 		node = xa_parent_locked(xas->xa, node);  in xas_clear_mark()
964 static unsigned int node_get_marks(struct xa_node *node, unsigned int offset)  in node_get_marks()  argument
970 		if (node_get_mark(node, offset, mark))  in node_get_marks()
980 static inline void node_mark_slots(struct xa_node *node, unsigned int sibs,  in node_mark_slots()  argument
986 		node_mark_all(node, mark);  in node_mark_slots()
989 			node_set_mark(node, i, mark);  in node_mark_slots()
993 static void node_set_marks(struct xa_node *node, unsigned int offset,  in node_set_marks()  argument
1001 			node_set_mark(node, offset, mark);  in node_set_marks()
1012 		struct xa_node *node, void *entry)  in __xas_init_node_for_split()  argument
1018 	if (!node)  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()
1057 		struct xa_node *node;  in xas_split_alloc()  local
1059 		node = kmem_cache_alloc_lru(radix_tree_node_cachep, xas->xa_lru, gfp);  in xas_split_alloc()
1060 		if (!node)  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()
1090 	struct xa_node *node;  in xas_split()  local
1094 	node = xas->xa_node;  in xas_split()
1095 	if (xas_top(node))  in xas_split()
1098 	marks = node_get_marks(node, xas->xa_offset);  in xas_split()
1102 		if (xas->xa_shift < node->shift) {  in xas_split()
1106 			child->shift = node->shift - XA_CHUNK_SHIFT;  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()
1122 			node_set_marks(node, canon, NULL, 0, marks);  in xas_split()
1123 			rcu_assign_pointer(node->slots[canon], entry);  in xas_split()
1125 				rcu_assign_pointer(node->slots[offset--],  in xas_split()
1132 	node->nr_values += values;  in xas_split()
1133 	xas_update(xas, node);  in xas_split()
1179 	struct xa_node *node;  in xas_try_split()  local
1184 	node = xas->xa_node;  in xas_try_split()
1185 	if (xas_top(node))  in xas_try_split()
1191 	marks = node_get_marks(node, xas->xa_offset);  in xas_try_split()
1195 	if (xas->xa_shift < node->shift) {  in xas_try_split()
1226 		child->shift = node->shift - XA_CHUNK_SHIFT;  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()
1244 			node_set_marks(node, canon, NULL, 0, marks);  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()
1254 	node->nr_values += values;  in xas_try_split()
1255 	xas_update(xas, node);  in xas_try_split()
1277 	struct xa_node *node = xas->xa_node;  in xas_pause()  local
1283 	if (node) {  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()
1567 			struct xa_node *node = xa_to_node(curr);  in xas_find_conflict()  local
1568 			curr = xas_descend(xas, node);  in xas_find_conflict()
2206 	struct xa_node *node = xas->xa_node;  in xas_sibling()  local
2209 	if (!IS_ENABLED(CONFIG_XARRAY_MULTI) || !node)  in xas_sibling()
2211 	mask = (XA_CHUNK_SIZE << node->shift) - 1;  in xas_sibling()
2213 		((unsigned long)xas->xa_offset << node->shift);  in xas_sibling()
2351 void xa_delete_node(struct xa_node *node, xa_update_node_t update)  in xa_delete_node()  argument
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()
2398 void xa_dump_node(const struct xa_node *node)  in xa_dump_node()  argument
2402 	if (!node)  in xa_dump_node()
2404 	if ((unsigned long)node & 3) {  in xa_dump_node()
2405 		pr_cont("node %px\n", node);  in xa_dump_node()
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()
2442 			struct xa_node *node = xa_to_node(entry);  in xa_dump_entry()  local
2443 			xa_dump_node(node);  in xa_dump_entry()
2445 				xa_dump_entry(node->slots[i],  in xa_dump_entry()
2446 				      index + (i << node->shift), node->shift);  in xa_dump_entry()