95 static inline gfp_t root_gfp_mask(const struct radix_tree_root *root)  in root_gfp_mask()  argument
97 	return root->xa_flags & (__GFP_BITS_MASK & ~GFP_ZONEMASK);  in root_gfp_mask()
118 static inline void root_tag_set(struct radix_tree_root *root, unsigned tag)  in root_tag_set()  argument
120 	root->xa_flags |= (__force gfp_t)(1 << (tag + ROOT_TAG_SHIFT));  in root_tag_set()
123 static inline void root_tag_clear(struct radix_tree_root *root, unsigned tag)  in root_tag_clear()  argument
125 	root->xa_flags &= (__force gfp_t)~(1 << (tag + ROOT_TAG_SHIFT));  in root_tag_clear()
128 static inline void root_tag_clear_all(struct radix_tree_root *root)  in root_tag_clear_all()  argument
130 	root->xa_flags &= (__force gfp_t)((1 << ROOT_TAG_SHIFT) - 1);  in root_tag_clear_all()
133 static inline int root_tag_get(const struct radix_tree_root *root, unsigned tag)  in root_tag_get()  argument
135 	return (__force int)root->xa_flags & (1 << (tag + ROOT_TAG_SHIFT));  in root_tag_get()
138 static inline unsigned root_tags_get(const struct radix_tree_root *root)  in root_tags_get()  argument
140 	return (__force unsigned)root->xa_flags >> ROOT_TAG_SHIFT;  in root_tags_get()
143 static inline bool is_idr(const struct radix_tree_root *root)  in is_idr()  argument
145 	return !!(root->xa_flags & ROOT_IS_IDR);  in is_idr()
234 			struct radix_tree_root *root,  in radix_tree_node_alloc()  argument
285 		ret->array = root;  in radix_tree_node_alloc()
388 static unsigned radix_tree_load_root(const struct radix_tree_root *root,  in radix_tree_load_root()  argument
391 	struct radix_tree_node *node = rcu_dereference_raw(root->xa_head);  in radix_tree_load_root()
408 static int radix_tree_extend(struct radix_tree_root *root, gfp_t gfp,  in radix_tree_extend()  argument
420 	entry = rcu_dereference_raw(root->xa_head);  in radix_tree_extend()
421 	if (!entry && (!is_idr(root) || root_tag_get(root, IDR_FREE)))  in radix_tree_extend()
426 							root, shift, 0, 1, 0);  in radix_tree_extend()
430 		if (is_idr(root)) {  in radix_tree_extend()
432 			if (!root_tag_get(root, IDR_FREE)) {  in radix_tree_extend()
434 				root_tag_set(root, IDR_FREE);  in radix_tree_extend()
439 				if (root_tag_get(root, tag))  in radix_tree_extend()
457 		rcu_assign_pointer(root->xa_head, entry);  in radix_tree_extend()
468 static inline bool radix_tree_shrink(struct radix_tree_root *root)  in radix_tree_shrink()  argument
473 		struct radix_tree_node *node = rcu_dereference_raw(root->xa_head);  in radix_tree_shrink()
495 		if (!node->shift && is_idr(root))  in radix_tree_shrink()
508 		root->xa_head = (void __rcu *)child;  in radix_tree_shrink()
509 		if (is_idr(root) && !tag_get(node, IDR_FREE, 0))  in radix_tree_shrink()
510 			root_tag_clear(root, IDR_FREE);  in radix_tree_shrink()
543 static bool delete_node(struct radix_tree_root *root,  in delete_node()  argument
553 					rcu_dereference_raw(root->xa_head))  in delete_node()
554 				deleted |= radix_tree_shrink(root);  in delete_node()
567 			if (!is_idr(root))  in delete_node()
568 				root_tag_clear_all(root);  in delete_node()
569 			root->xa_head = NULL;  in delete_node()
598 static int __radix_tree_create(struct radix_tree_root *root,  in __radix_tree_create()  argument
603 	void __rcu **slot = (void __rcu **)&root->xa_head;  in __radix_tree_create()
607 	gfp_t gfp = root_gfp_mask(root);  in __radix_tree_create()
609 	shift = radix_tree_load_root(root, &child, &maxindex);  in __radix_tree_create()
613 		int error = radix_tree_extend(root, gfp, max, shift);  in __radix_tree_create()
617 		child = rcu_dereference_raw(root->xa_head);  in __radix_tree_create()
624 			child = radix_tree_node_alloc(gfp, node, root, shift,  in __radix_tree_create()
703 int radix_tree_insert(struct radix_tree_root *root, unsigned long index,  in radix_tree_insert()  argument
712 	error = __radix_tree_create(root, index, &node, &slot);  in radix_tree_insert()
726 		BUG_ON(root_tags_get(root));  in radix_tree_insert()
747 void *__radix_tree_lookup(const struct radix_tree_root *root,  in __radix_tree_lookup()  argument
757 	slot = (void __rcu **)&root->xa_head;  in __radix_tree_lookup()
758 	radix_tree_load_root(root, &node, &maxindex);  in __radix_tree_lookup()
794 void __rcu **radix_tree_lookup_slot(const struct radix_tree_root *root,  in radix_tree_lookup_slot()  argument
799 	if (!__radix_tree_lookup(root, index, NULL, &slot))  in radix_tree_lookup_slot()
817 void *radix_tree_lookup(const struct radix_tree_root *root, unsigned long index)  in radix_tree_lookup()  argument
819 	return __radix_tree_lookup(root, index, NULL, NULL);  in radix_tree_lookup()
834 static bool node_tag_get(const struct radix_tree_root *root,  in node_tag_get()  argument
840 	return root_tag_get(root, tag);  in node_tag_get()
850 static int calculate_count(struct radix_tree_root *root,  in calculate_count()  argument
854 	if (is_idr(root)) {  in calculate_count()
856 		bool free = node_tag_get(root, node, IDR_FREE, offset);  in calculate_count()
875 void __radix_tree_replace(struct radix_tree_root *root,  in __radix_tree_replace()  argument
881 	int count = calculate_count(root, node, slot, item, old);  in __radix_tree_replace()
888 	WARN_ON_ONCE(!node && (slot != (void __rcu **)&root->xa_head) &&  in __radix_tree_replace()
895 	delete_node(root, node);  in __radix_tree_replace()
914 void radix_tree_replace_slot(struct radix_tree_root *root,  in radix_tree_replace_slot()  argument
917 	__radix_tree_replace(root, NULL, slot, item);  in radix_tree_replace_slot()
931 void radix_tree_iter_replace(struct radix_tree_root *root,  in radix_tree_iter_replace()  argument
935 	__radix_tree_replace(root, iter->node, slot, item);  in radix_tree_iter_replace()
938 static void node_tag_set(struct radix_tree_root *root,  in node_tag_set()  argument
950 	if (!root_tag_get(root, tag))  in node_tag_set()
951 		root_tag_set(root, tag);  in node_tag_set()
967 void *radix_tree_tag_set(struct radix_tree_root *root,  in radix_tree_tag_set()  argument
973 	radix_tree_load_root(root, &node, &maxindex);  in radix_tree_tag_set()
988 	if (!root_tag_get(root, tag))  in radix_tree_tag_set()
989 		root_tag_set(root, tag);  in radix_tree_tag_set()
995 static void node_tag_clear(struct radix_tree_root *root,  in node_tag_clear()  argument
1011 	if (root_tag_get(root, tag))  in node_tag_clear()
1012 		root_tag_clear(root, tag);  in node_tag_clear()
1029 void *radix_tree_tag_clear(struct radix_tree_root *root,  in radix_tree_tag_clear()  argument
1036 	radix_tree_load_root(root, &node, &maxindex);  in radix_tree_tag_clear()
1048 		node_tag_clear(root, parent, tag, offset);  in radix_tree_tag_clear()
1060 void radix_tree_iter_tag_clear(struct radix_tree_root *root,  in radix_tree_iter_tag_clear()  argument
1063 	node_tag_clear(root, iter->node, tag, iter_offset(iter));  in radix_tree_iter_tag_clear()
1081 int radix_tree_tag_get(const struct radix_tree_root *root,  in radix_tree_tag_get()  argument
1087 	if (!root_tag_get(root, tag))  in radix_tree_tag_get()
1090 	radix_tree_load_root(root, &node, &maxindex);  in radix_tree_tag_get()
1154 void __rcu **radix_tree_next_chunk(const struct radix_tree_root *root,  in radix_tree_next_chunk()  argument
1161 	if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag))  in radix_tree_next_chunk()
1178 	radix_tree_load_root(root, &child, &maxindex);  in radix_tree_next_chunk()
1190 		return (void __rcu **)&root->xa_head;  in radix_tree_next_chunk()
1262 radix_tree_gang_lookup(const struct radix_tree_root *root, void **results,  in radix_tree_gang_lookup()  argument
1272 	radix_tree_for_each_slot(slot, root, &iter, first_index) {  in radix_tree_gang_lookup()
1302 radix_tree_gang_lookup_tag(const struct radix_tree_root *root, void **results,  in radix_tree_gang_lookup_tag()  argument
1313 	radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) {  in radix_tree_gang_lookup_tag()
1343 radix_tree_gang_lookup_tag_slot(const struct radix_tree_root *root,  in radix_tree_gang_lookup_tag_slot()  argument
1354 	radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) {  in radix_tree_gang_lookup_tag_slot()
1364 static bool __radix_tree_delete(struct radix_tree_root *root,  in __radix_tree_delete()  argument
1372 	if (is_idr(root))  in __radix_tree_delete()
1373 		node_tag_set(root, node, IDR_FREE, offset);  in __radix_tree_delete()
1376 			node_tag_clear(root, node, tag, offset);  in __radix_tree_delete()
1379 	return node && delete_node(root, node);  in __radix_tree_delete()
1394 void radix_tree_iter_delete(struct radix_tree_root *root,  in radix_tree_iter_delete()  argument
1397 	if (__radix_tree_delete(root, iter->node, slot))  in radix_tree_iter_delete()
1413 void *radix_tree_delete_item(struct radix_tree_root *root,  in radix_tree_delete_item()  argument
1420 	entry = __radix_tree_lookup(root, index, &node, &slot);  in radix_tree_delete_item()
1423 	if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE,  in radix_tree_delete_item()
1430 	__radix_tree_delete(root, node, slot);  in radix_tree_delete_item()
1445 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)  in radix_tree_delete()  argument
1447 	return radix_tree_delete_item(root, index, NULL);  in radix_tree_delete()
1456 int radix_tree_tagged(const struct radix_tree_root *root, unsigned int tag)  in radix_tree_tagged()  argument
1458 	return root_tag_get(root, tag);  in radix_tree_tagged()
1476 void __rcu **idr_get_free(struct radix_tree_root *root,  in idr_get_free()  argument
1481 	void __rcu **slot = (void __rcu **)&root->xa_head;  in idr_get_free()
1486 	shift = radix_tree_load_root(root, &child, &maxindex);  in idr_get_free()
1487 	if (!radix_tree_tagged(root, IDR_FREE))  in idr_get_free()
1493 		int error = radix_tree_extend(root, gfp, start, shift);  in idr_get_free()
1497 		child = rcu_dereference_raw(root->xa_head);  in idr_get_free()
1506 			child = radix_tree_node_alloc(gfp, node, root, shift,  in idr_get_free()