31  * Radix tree node cache.
43  * of RADIX_TREE_MAX_PATH size to be created, with only the root node shared.
98 static inline void tag_set(struct radix_tree_node *node, unsigned int tag,  in tag_set()  argument
101 	__set_bit(offset, node->tags[tag]);  in tag_set()
104 static inline void tag_clear(struct radix_tree_node *node, unsigned int tag,  in tag_clear()  argument
107 	__clear_bit(offset, node->tags[tag]);  in tag_clear()
110 static inline int tag_get(const struct radix_tree_node *node, unsigned int tag,  in tag_get()  argument
113 	return test_bit(offset, node->tags[tag]);  in tag_get()
147  * Returns 1 if any slot in the node has this tag set.
150 static inline int any_tag_set(const struct radix_tree_node *node,  in any_tag_set()  argument
155 		if (node->tags[tag][idx])  in any_tag_set()
161 static inline void all_tag_set(struct radix_tree_node *node, unsigned int tag)  in all_tag_set()  argument
163 	bitmap_fill(node->tags[tag], RADIX_TREE_MAP_SIZE);  in all_tag_set()
178 radix_tree_find_next_bit(struct radix_tree_node *node, unsigned int tag,  in radix_tree_find_next_bit()  argument
181 	const unsigned long *addr = node->tags[tag];  in radix_tree_find_next_bit()
214 static inline unsigned long node_maxindex(const struct radix_tree_node *node)  in node_maxindex()  argument
216 	return shift_maxindex(node->shift);  in node_maxindex()
220 				const struct radix_tree_node *node,  in next_index()  argument
223 	return (index & ~node_maxindex(node)) + (offset << node->shift);  in next_index()
248 		 * cache first for the new node to get accounted to the memory  in radix_tree_node_alloc()
258 		 * succeed in getting a node here (and never reach  in radix_tree_node_alloc()
290 	struct radix_tree_node *node =  in radix_tree_node_rcu_free()  local
298 	memset(node->slots, 0, sizeof(node->slots));  in radix_tree_node_rcu_free()
299 	memset(node->tags, 0, sizeof(node->tags));  in radix_tree_node_rcu_free()
300 	INIT_LIST_HEAD(&node->private_list);  in radix_tree_node_rcu_free()
302 	kmem_cache_free(radix_tree_node_cachep, node);  in radix_tree_node_rcu_free()
306 radix_tree_node_free(struct radix_tree_node *node)  in radix_tree_node_free()  argument
308 	call_rcu(&node->rcu_head, radix_tree_node_rcu_free);  in radix_tree_node_free()
323 	struct radix_tree_node *node;  in __radix_tree_preload()  local
336 		node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);  in __radix_tree_preload()
337 		if (node == NULL)  in __radix_tree_preload()
342 			node->parent = rtp->nodes;  in __radix_tree_preload()
343 			rtp->nodes = node;  in __radix_tree_preload()
346 			kmem_cache_free(radix_tree_node_cachep, node);  in __radix_tree_preload()
389 	struct radix_tree_node *node = rcu_dereference_raw(root->xa_head);  in radix_tree_load_root()  local
391 	*nodep = node;  in radix_tree_load_root()
393 	if (likely(radix_tree_is_internal_node(node))) {  in radix_tree_load_root()
394 		node = entry_to_node(node);  in radix_tree_load_root()
395 		*maxindex = node_maxindex(node);  in radix_tree_load_root()
396 		return node->shift + RADIX_TREE_MAP_SHIFT;  in radix_tree_load_root()
423 		struct radix_tree_node *node = radix_tree_node_alloc(gfp, NULL,  in radix_tree_extend()  local
425 		if (!node)  in radix_tree_extend()
429 			all_tag_set(node, IDR_FREE);  in radix_tree_extend()
431 				tag_clear(node, IDR_FREE, 0);  in radix_tree_extend()
438 					tag_set(node, tag, 0);  in radix_tree_extend()
444 			entry_to_node(entry)->parent = node;  in radix_tree_extend()
446 			/* Moving a value entry root->xa_head to a node */  in radix_tree_extend()
447 			node->nr_values = 1;  in radix_tree_extend()
453 		node->slots[0] = (void __rcu *)entry;  in radix_tree_extend()
454 		entry = node_to_entry(node);  in radix_tree_extend()
471 		struct radix_tree_node *node = rcu_dereference_raw(root->xa_head);  in radix_tree_shrink()  local
474 		if (!radix_tree_is_internal_node(node))  in radix_tree_shrink()
476 		node = entry_to_node(node);  in radix_tree_shrink()
479 		 * The candidate node has more than one child, or its child  in radix_tree_shrink()
482 		if (node->count != 1)  in radix_tree_shrink()
484 		child = rcu_dereference_raw(node->slots[0]);  in radix_tree_shrink()
493 		if (!node->shift && is_idr(root))  in radix_tree_shrink()
501 		 * moving the node from one part of the tree to another: if it  in radix_tree_shrink()
503 		 * (node->slots[0]), it will be safe to dereference the new  in radix_tree_shrink()
507 		if (is_idr(root) && !tag_get(node, IDR_FREE, 0))  in radix_tree_shrink()
511 		 * We have a dilemma here. The node's slot[0] must not be  in radix_tree_shrink()
513 		 * find the item. However if this was a bottom-level node,  in radix_tree_shrink()
524 		 * problem (replacing direct root node with an indirect pointer  in radix_tree_shrink()
528 		node->count = 0;  in radix_tree_shrink()
530 			node->slots[0] = (void __rcu *)RADIX_TREE_RETRY;  in radix_tree_shrink()
533 		WARN_ON_ONCE(!list_empty(&node->private_list));  in radix_tree_shrink()
534 		radix_tree_node_free(node);  in radix_tree_shrink()
542 			struct radix_tree_node *node)  in delete_node()  argument
549 		if (node->count) {  in delete_node()
550 			if (node_to_entry(node) ==  in delete_node()
556 		parent = node->parent;  in delete_node()
558 			parent->slots[node->offset] = NULL;  in delete_node()
570 		WARN_ON_ONCE(!list_empty(&node->private_list));  in delete_node()
571 		radix_tree_node_free(node);  in delete_node()
574 		node = parent;  in delete_node()
575 	} while (node);  in delete_node()
584  *	@nodep:		returns node
587  *	Create, if necessary, and return the node and slot for an item
592  *	pointing to a node, in which case *@nodep will be NULL.
600 	struct radix_tree_node *node = NULL, *child;  in __radix_tree_create()  local
621 			/* Have to add a child node.  */  in __radix_tree_create()
622 			child = radix_tree_node_alloc(gfp, node, root, shift,  in __radix_tree_create()
627 			if (node)  in __radix_tree_create()
628 				node->count++;  in __radix_tree_create()
633 		node = entry_to_node(child);  in __radix_tree_create()
634 		offset = radix_tree_descend(node, &child, index);  in __radix_tree_create()
635 		slot = &node->slots[offset];  in __radix_tree_create()
639 		*nodep = node;  in __radix_tree_create()
646  * Free any nodes below this node.  The tree is presumed to not need
654 static void radix_tree_free_nodes(struct radix_tree_node *node)  in radix_tree_free_nodes()  argument
657 	struct radix_tree_node *child = entry_to_node(node);  in radix_tree_free_nodes()
673 			if (old == entry_to_node(node))  in radix_tree_free_nodes()
679 static inline int insert_entries(struct radix_tree_node *node,  in insert_entries()  argument
685 	if (node) {  in insert_entries()
686 		node->count++;  in insert_entries()
688 			node->nr_values++;  in insert_entries()
704 	struct radix_tree_node *node;  in radix_tree_insert()  local
710 	error = __radix_tree_create(root, index, &node, &slot);  in radix_tree_insert()
714 	error = insert_entries(node, slot, item, false);  in radix_tree_insert()
718 	if (node) {  in radix_tree_insert()
719 		unsigned offset = get_slot_offset(node, slot);  in radix_tree_insert()
720 		BUG_ON(tag_get(node, 0, offset));  in radix_tree_insert()
721 		BUG_ON(tag_get(node, 1, offset));  in radix_tree_insert()
722 		BUG_ON(tag_get(node, 2, offset));  in radix_tree_insert()
735  *	@nodep:		returns node
743  *	pointing to a node, in which case *@nodep will be NULL.
749 	struct radix_tree_node *node, *parent;  in __radix_tree_lookup()  local
756 	radix_tree_load_root(root, &node, &maxindex);  in __radix_tree_lookup()
760 	while (radix_tree_is_internal_node(node)) {  in __radix_tree_lookup()
763 		parent = entry_to_node(node);  in __radix_tree_lookup()
764 		offset = radix_tree_descend(parent, &node, index);  in __radix_tree_lookup()
766 		if (node == RADIX_TREE_RETRY)  in __radix_tree_lookup()
776 	return node;  in __radix_tree_lookup()
822 		struct radix_tree_node *node, int count, int values)  in replace_slot()  argument
824 	if (node && (count || values)) {  in replace_slot()
825 		node->count += count;  in replace_slot()
826 		node->nr_values += values;  in replace_slot()
833 				const struct radix_tree_node *node,  in node_tag_get()  argument
836 	if (node)  in node_tag_get()
837 		return tag_get(node, tag, offset);  in node_tag_get()
849 				struct radix_tree_node *node, void __rcu **slot,  in calculate_count()  argument
853 		unsigned offset = get_slot_offset(node, slot);  in calculate_count()
854 		bool free = node_tag_get(root, node, IDR_FREE, offset);  in calculate_count()
866  * @node:		pointer to tree node
867  * @slot:		pointer to slot in @node
874 			  struct radix_tree_node *node,  in __radix_tree_replace()  argument
879 	int count = calculate_count(root, node, slot, item, old);  in __radix_tree_replace()
884 	 * node unless the slot is root->xa_head.  in __radix_tree_replace()
886 	WARN_ON_ONCE(!node && (slot != (void __rcu **)&root->xa_head) &&  in __radix_tree_replace()
888 	replace_slot(slot, item, node, count, values);  in __radix_tree_replace()
890 	if (!node)  in __radix_tree_replace()
893 	delete_node(root, node);  in __radix_tree_replace()
908  * inside the radix tree node. When switching from one type of entry or
932 	__radix_tree_replace(root, iter->node, slot, item);  in radix_tree_iter_replace()
936 				struct radix_tree_node *node,  in node_tag_set()  argument
939 	while (node) {  in node_tag_set()
940 		if (tag_get(node, tag, offset))  in node_tag_set()
942 		tag_set(node, tag, offset);  in node_tag_set()
943 		offset = node->offset;  in node_tag_set()
944 		node = node->parent;  in node_tag_set()
952  *	radix_tree_tag_set - set a tag on a radix tree node
959  *	the root all the way down to the leaf node.
967 	struct radix_tree_node *node, *parent;  in radix_tree_tag_set()  local
970 	radix_tree_load_root(root, &node, &maxindex);  in radix_tree_tag_set()
973 	while (radix_tree_is_internal_node(node)) {  in radix_tree_tag_set()
976 		parent = entry_to_node(node);  in radix_tree_tag_set()
977 		offset = radix_tree_descend(parent, &node, index);  in radix_tree_tag_set()
978 		BUG_ON(!node);  in radix_tree_tag_set()
988 	return node;  in radix_tree_tag_set()
993 				struct radix_tree_node *node,  in node_tag_clear()  argument
996 	while (node) {  in node_tag_clear()
997 		if (!tag_get(node, tag, offset))  in node_tag_clear()
999 		tag_clear(node, tag, offset);  in node_tag_clear()
1000 		if (any_tag_set(node, tag))  in node_tag_clear()
1003 		offset = node->offset;  in node_tag_clear()
1004 		node = node->parent;  in node_tag_clear()
1013  *	radix_tree_tag_clear - clear a tag on a radix tree node
1020  *	the leaf node to have no tags set then clear the tag in the
1021  *	next-to-leaf node, etc.
1029 	struct radix_tree_node *node, *parent;  in radix_tree_tag_clear()  local
1033 	radix_tree_load_root(root, &node, &maxindex);  in radix_tree_tag_clear()
1039 	while (radix_tree_is_internal_node(node)) {  in radix_tree_tag_clear()
1040 		parent = entry_to_node(node);  in radix_tree_tag_clear()
1041 		offset = radix_tree_descend(parent, &node, index);  in radix_tree_tag_clear()
1044 	if (node)  in radix_tree_tag_clear()
1047 	return node;  in radix_tree_tag_clear()
1060 	node_tag_clear(root, iter->node, tag, iter_offset(iter));  in radix_tree_iter_tag_clear()
1064  * radix_tree_tag_get - get a tag on a radix tree node
1075  * the RCU lock is held, unless tag modification and node deletion are excluded
1081 	struct radix_tree_node *node, *parent;  in radix_tree_tag_get()  local
1087 	radix_tree_load_root(root, &node, &maxindex);  in radix_tree_tag_get()
1091 	while (radix_tree_is_internal_node(node)) {  in radix_tree_tag_get()
1094 		parent = entry_to_node(node);  in radix_tree_tag_get()
1095 		offset = radix_tree_descend(parent, &node, index);  in radix_tree_tag_get()
1099 		if (node == RADIX_TREE_RETRY)  in radix_tree_tag_get()
1107 /* Construct iter->tags bit-mask from node->tags[tag] array */
1109 				struct radix_tree_node *node, unsigned offset,  in set_iter_tags()  argument
1115 	if (!node) {  in set_iter_tags()
1120 	iter->tags = node->tags[tag][tag_long] >> tag_bit;  in set_iter_tags()
1126 			iter->tags |= node->tags[tag][tag_long + 1] <<  in set_iter_tags()
1156 	struct radix_tree_node *node, *child;  in radix_tree_next_chunk()  local
1187 		iter->node = NULL;  in radix_tree_next_chunk()
1192 		node = entry_to_node(child);  in radix_tree_next_chunk()
1193 		offset = radix_tree_descend(node, &child, index);  in radix_tree_next_chunk()
1196 				!tag_get(node, tag, offset) : !child) {  in radix_tree_next_chunk()
1202 				offset = radix_tree_find_next_bit(node, tag,  in radix_tree_next_chunk()
1207 							node->slots[offset]);  in radix_tree_next_chunk()
1211 			index &= ~node_maxindex(node);  in radix_tree_next_chunk()
1212 			index += offset << node->shift;  in radix_tree_next_chunk()
1218 			child = rcu_dereference_raw(node->slots[offset]);  in radix_tree_next_chunk()
1225 	} while (node->shift && radix_tree_is_internal_node(child));  in radix_tree_next_chunk()
1228 	iter->index = (index &~ node_maxindex(node)) | offset;  in radix_tree_next_chunk()
1229 	iter->next_index = (index | node_maxindex(node)) + 1;  in radix_tree_next_chunk()
1230 	iter->node = node;  in radix_tree_next_chunk()
1233 		set_iter_tags(iter, node, offset, tag);  in radix_tree_next_chunk()
1235 	return node->slots + offset;  in radix_tree_next_chunk()
1363 				struct radix_tree_node *node, void __rcu **slot)  in __radix_tree_delete()  argument
1367 	unsigned offset = get_slot_offset(node, slot);  in __radix_tree_delete()
1371 		node_tag_set(root, node, IDR_FREE, offset);  in __radix_tree_delete()
1374 			node_tag_clear(root, node, tag, offset);  in __radix_tree_delete()
1376 	replace_slot(slot, NULL, node, -1, values);  in __radix_tree_delete()
1377 	return node && delete_node(root, node);  in __radix_tree_delete()
1387  * This may result in the current node being freed; if it is, the iterator
1395 	if (__radix_tree_delete(root, iter->node, slot))  in radix_tree_iter_delete()
1414 	struct radix_tree_node *node = NULL;  in radix_tree_delete_item()  local
1418 	entry = __radix_tree_lookup(root, index, &node, &slot);  in radix_tree_delete_item()
1421 	if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE,  in radix_tree_delete_item()
1422 						get_slot_offset(node, slot))))  in radix_tree_delete_item()
1428 	__radix_tree_delete(root, node, slot);  in radix_tree_delete_item()
1478 	struct radix_tree_node *node = NULL, *child;  in idr_get_free()  local
1503 			/* Have to add a child node.  */  in idr_get_free()
1504 			child = radix_tree_node_alloc(gfp, node, root, shift,  in idr_get_free()
1510 			if (node)  in idr_get_free()
1511 				node->count++;  in idr_get_free()
1515 		node = entry_to_node(child);  in idr_get_free()
1516 		offset = radix_tree_descend(node, &child, start);  in idr_get_free()
1517 		if (!tag_get(node, IDR_FREE, offset)) {  in idr_get_free()
1518 			offset = radix_tree_find_next_bit(node, IDR_FREE,  in idr_get_free()
1520 			start = next_index(start, node, offset);  in idr_get_free()
1524 				offset = node->offset + 1;  in idr_get_free()
1525 				node = node->parent;  in idr_get_free()
1526 				if (!node)  in idr_get_free()
1528 				shift = node->shift;  in idr_get_free()
1530 			child = rcu_dereference_raw(node->slots[offset]);  in idr_get_free()
1532 		slot = &node->slots[offset];  in idr_get_free()
1536 	if (node)  in idr_get_free()
1537 		iter->next_index = 1 + min(max, (start | node_maxindex(node)));  in idr_get_free()
1540 	iter->node = node;  in idr_get_free()
1541 	set_iter_tags(iter, node, offset, IDR_FREE);  in idr_get_free()
1559 	struct radix_tree_node *node = rcu_dereference_raw(idr->idr_rt.xa_head);  in idr_destroy()  local
1560 	if (radix_tree_is_internal_node(node))  in idr_destroy()
1561 		radix_tree_free_nodes(node);  in idr_destroy()
1570 	struct radix_tree_node *node = arg;  in radix_tree_node_ctor()  local
1572 	memset(node, 0, sizeof(*node));  in radix_tree_node_ctor()
1573 	INIT_LIST_HEAD(&node->private_list);  in radix_tree_node_ctor()
1579 	struct radix_tree_node *node;  in radix_tree_cpu_dead()  local
1584 		node = rtp->nodes;  in radix_tree_cpu_dead()
1585 		rtp->nodes = node->parent;  in radix_tree_cpu_dead()
1586 		kmem_cache_free(radix_tree_node_cachep, node);  in radix_tree_cpu_dead()