33  * Radix tree node cache.
45  * of RADIX_TREE_MAX_PATH size to be created, with only the root node shared.
100 static inline void tag_set(struct radix_tree_node *node, unsigned int tag,  in tag_set()  argument
103 	__set_bit(offset, node->tags[tag]);  in tag_set()
106 static inline void tag_clear(struct radix_tree_node *node, unsigned int tag,  in tag_clear()  argument
109 	__clear_bit(offset, node->tags[tag]);  in tag_clear()
112 static inline int tag_get(const struct radix_tree_node *node, unsigned int tag,  in tag_get()  argument
115 	return test_bit(offset, node->tags[tag]);  in tag_get()
149  * Returns 1 if any slot in the node has this tag set.
152 static inline int any_tag_set(const struct radix_tree_node *node,  in any_tag_set()  argument
157 		if (node->tags[tag][idx])  in any_tag_set()
163 static inline void all_tag_set(struct radix_tree_node *node, unsigned int tag)  in all_tag_set()  argument
165 	bitmap_fill(node->tags[tag], RADIX_TREE_MAP_SIZE);  in all_tag_set()
171  * @node: where to begin the search
180 radix_tree_find_next_bit(struct radix_tree_node *node, unsigned int tag,  in radix_tree_find_next_bit()  argument
183 	const unsigned long *addr = node->tags[tag];  in radix_tree_find_next_bit()
216 static inline unsigned long node_maxindex(const struct radix_tree_node *node)  in node_maxindex()  argument
218 	return shift_maxindex(node->shift);  in node_maxindex()
222 				const struct radix_tree_node *node,  in next_index()  argument
225 	return (index & ~node_maxindex(node)) + (offset << node->shift);  in next_index()
250 		 * cache first for the new node to get accounted to the memory  in radix_tree_node_alloc()
260 		 * succeed in getting a node here (and never reach  in radix_tree_node_alloc()
292 	struct radix_tree_node *node =  in radix_tree_node_rcu_free()  local
300 	memset(node->slots, 0, sizeof(node->slots));  in radix_tree_node_rcu_free()
301 	memset(node->tags, 0, sizeof(node->tags));  in radix_tree_node_rcu_free()
302 	INIT_LIST_HEAD(&node->private_list);  in radix_tree_node_rcu_free()
304 	kmem_cache_free(radix_tree_node_cachep, node);  in radix_tree_node_rcu_free()
308 radix_tree_node_free(struct radix_tree_node *node)  in radix_tree_node_free()  argument
310 	call_rcu(&node->rcu_head, radix_tree_node_rcu_free);  in radix_tree_node_free()
325 	struct radix_tree_node *node;  in __radix_tree_preload()  local
338 		node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);  in __radix_tree_preload()
339 		if (node == NULL)  in __radix_tree_preload()
344 			node->parent = rtp->nodes;  in __radix_tree_preload()
345 			rtp->nodes = node;  in __radix_tree_preload()
348 			kmem_cache_free(radix_tree_node_cachep, node);  in __radix_tree_preload()
391 	struct radix_tree_node *node = rcu_dereference_raw(root->xa_head);  in radix_tree_load_root()  local
393 	*nodep = node;  in radix_tree_load_root()
395 	if (likely(radix_tree_is_internal_node(node))) {  in radix_tree_load_root()
396 		node = entry_to_node(node);  in radix_tree_load_root()
397 		*maxindex = node_maxindex(node);  in radix_tree_load_root()
398 		return node->shift + RADIX_TREE_MAP_SHIFT;  in radix_tree_load_root()
425 		struct radix_tree_node *node = radix_tree_node_alloc(gfp, NULL,  in radix_tree_extend()  local
427 		if (!node)  in radix_tree_extend()
431 			all_tag_set(node, IDR_FREE);  in radix_tree_extend()
433 				tag_clear(node, IDR_FREE, 0);  in radix_tree_extend()
440 					tag_set(node, tag, 0);  in radix_tree_extend()
446 			entry_to_node(entry)->parent = node;  in radix_tree_extend()
448 			/* Moving a value entry root->xa_head to a node */  in radix_tree_extend()
449 			node->nr_values = 1;  in radix_tree_extend()
455 		node->slots[0] = (void __rcu *)entry;  in radix_tree_extend()
456 		entry = node_to_entry(node);  in radix_tree_extend()
473 		struct radix_tree_node *node = rcu_dereference_raw(root->xa_head);  in radix_tree_shrink()  local
476 		if (!radix_tree_is_internal_node(node))  in radix_tree_shrink()
478 		node = entry_to_node(node);  in radix_tree_shrink()
481 		 * The candidate node has more than one child, or its child  in radix_tree_shrink()
484 		if (node->count != 1)  in radix_tree_shrink()
486 		child = rcu_dereference_raw(node->slots[0]);  in radix_tree_shrink()
495 		if (!node->shift && is_idr(root))  in radix_tree_shrink()
503 		 * moving the node from one part of the tree to another: if it  in radix_tree_shrink()
505 		 * (node->slots[0]), it will be safe to dereference the new  in radix_tree_shrink()
509 		if (is_idr(root) && !tag_get(node, IDR_FREE, 0))  in radix_tree_shrink()
513 		 * We have a dilemma here. The node's slot[0] must not be  in radix_tree_shrink()
515 		 * find the item. However if this was a bottom-level node,  in radix_tree_shrink()
526 		 * problem (replacing direct root node with an indirect pointer  in radix_tree_shrink()
530 		node->count = 0;  in radix_tree_shrink()
532 			node->slots[0] = (void __rcu *)RADIX_TREE_RETRY;  in radix_tree_shrink()
535 		WARN_ON_ONCE(!list_empty(&node->private_list));  in radix_tree_shrink()
536 		radix_tree_node_free(node);  in radix_tree_shrink()
544 			struct radix_tree_node *node)  in delete_node()  argument
551 		if (node->count) {  in delete_node()
552 			if (node_to_entry(node) ==  in delete_node()
558 		parent = node->parent;  in delete_node()
560 			parent->slots[node->offset] = NULL;  in delete_node()
572 		WARN_ON_ONCE(!list_empty(&node->private_list));  in delete_node()
573 		radix_tree_node_free(node);  in delete_node()
576 		node = parent;  in delete_node()
577 	} while (node);  in delete_node()
586  *	@nodep:		returns node
589  *	Create, if necessary, and return the node and slot for an item
594  *	pointing to a node, in which case *@nodep will be NULL.
602 	struct radix_tree_node *node = NULL, *child;  in __radix_tree_create()  local
623 			/* Have to add a child node.  */  in __radix_tree_create()
624 			child = radix_tree_node_alloc(gfp, node, root, shift,  in __radix_tree_create()
629 			if (node)  in __radix_tree_create()
630 				node->count++;  in __radix_tree_create()
635 		node = entry_to_node(child);  in __radix_tree_create()
636 		offset = radix_tree_descend(node, &child, index);  in __radix_tree_create()
637 		slot = &node->slots[offset];  in __radix_tree_create()
641 		*nodep = node;  in __radix_tree_create()
648  * Free any nodes below this node.  The tree is presumed to not need
656 static void radix_tree_free_nodes(struct radix_tree_node *node)  in radix_tree_free_nodes()  argument
659 	struct radix_tree_node *child = entry_to_node(node);  in radix_tree_free_nodes()
675 			if (old == entry_to_node(node))  in radix_tree_free_nodes()
681 static inline int insert_entries(struct radix_tree_node *node,  in insert_entries()  argument
687 	if (node) {  in insert_entries()
688 		node->count++;  in insert_entries()
690 			node->nr_values++;  in insert_entries()
706 	struct radix_tree_node *node;  in radix_tree_insert()  local
712 	error = __radix_tree_create(root, index, &node, &slot);  in radix_tree_insert()
716 	error = insert_entries(node, slot, item);  in radix_tree_insert()
720 	if (node) {  in radix_tree_insert()
721 		unsigned offset = get_slot_offset(node, slot);  in radix_tree_insert()
722 		BUG_ON(tag_get(node, 0, offset));  in radix_tree_insert()
723 		BUG_ON(tag_get(node, 1, offset));  in radix_tree_insert()
724 		BUG_ON(tag_get(node, 2, offset));  in radix_tree_insert()
737  *	@nodep:		returns node
745  *	pointing to a node, in which case *@nodep will be NULL.
751 	struct radix_tree_node *node, *parent;  in __radix_tree_lookup()  local
758 	radix_tree_load_root(root, &node, &maxindex);  in __radix_tree_lookup()
762 	while (radix_tree_is_internal_node(node)) {  in __radix_tree_lookup()
765 		parent = entry_to_node(node);  in __radix_tree_lookup()
766 		offset = radix_tree_descend(parent, &node, index);  in __radix_tree_lookup()
768 		if (node == RADIX_TREE_RETRY)  in __radix_tree_lookup()
778 	return node;  in __radix_tree_lookup()
824 		struct radix_tree_node *node, int count, int values)  in replace_slot()  argument
826 	if (node && (count || values)) {  in replace_slot()
827 		node->count += count;  in replace_slot()
828 		node->nr_values += values;  in replace_slot()
835 				const struct radix_tree_node *node,  in node_tag_get()  argument
838 	if (node)  in node_tag_get()
839 		return tag_get(node, tag, offset);  in node_tag_get()
851 				struct radix_tree_node *node, void __rcu **slot,  in calculate_count()  argument
855 		unsigned offset = get_slot_offset(node, slot);  in calculate_count()
856 		bool free = node_tag_get(root, node, IDR_FREE, offset);  in calculate_count()
868  * @node:		pointer to tree node
869  * @slot:		pointer to slot in @node
876 			  struct radix_tree_node *node,  in __radix_tree_replace()  argument
881 	int count = calculate_count(root, node, slot, item, old);  in __radix_tree_replace()
886 	 * node unless the slot is root->xa_head.  in __radix_tree_replace()
888 	WARN_ON_ONCE(!node && (slot != (void __rcu **)&root->xa_head) &&  in __radix_tree_replace()
890 	replace_slot(slot, item, node, count, values);  in __radix_tree_replace()
892 	if (!node)  in __radix_tree_replace()
895 	delete_node(root, node);  in __radix_tree_replace()
910  * inside the radix tree node. When switching from one type of entry or
935 	__radix_tree_replace(root, iter->node, slot, item);  in radix_tree_iter_replace()
939 				struct radix_tree_node *node,  in node_tag_set()  argument
942 	while (node) {  in node_tag_set()
943 		if (tag_get(node, tag, offset))  in node_tag_set()
945 		tag_set(node, tag, offset);  in node_tag_set()
946 		offset = node->offset;  in node_tag_set()
947 		node = node->parent;  in node_tag_set()
955  *	radix_tree_tag_set - set a tag on a radix tree node
962  *	the root all the way down to the leaf node.
970 	struct radix_tree_node *node, *parent;  in radix_tree_tag_set()  local
973 	radix_tree_load_root(root, &node, &maxindex);  in radix_tree_tag_set()
976 	while (radix_tree_is_internal_node(node)) {  in radix_tree_tag_set()
979 		parent = entry_to_node(node);  in radix_tree_tag_set()
980 		offset = radix_tree_descend(parent, &node, index);  in radix_tree_tag_set()
981 		BUG_ON(!node);  in radix_tree_tag_set()
991 	return node;  in radix_tree_tag_set()
996 				struct radix_tree_node *node,  in node_tag_clear()  argument
999 	while (node) {  in node_tag_clear()
1000 		if (!tag_get(node, tag, offset))  in node_tag_clear()
1002 		tag_clear(node, tag, offset);  in node_tag_clear()
1003 		if (any_tag_set(node, tag))  in node_tag_clear()
1006 		offset = node->offset;  in node_tag_clear()
1007 		node = node->parent;  in node_tag_clear()
1016  *	radix_tree_tag_clear - clear a tag on a radix tree node
1023  *	the leaf node to have no tags set then clear the tag in the
1024  *	next-to-leaf node, etc.
1032 	struct radix_tree_node *node, *parent;  in radix_tree_tag_clear()  local
1036 	radix_tree_load_root(root, &node, &maxindex);  in radix_tree_tag_clear()
1042 	while (radix_tree_is_internal_node(node)) {  in radix_tree_tag_clear()
1043 		parent = entry_to_node(node);  in radix_tree_tag_clear()
1044 		offset = radix_tree_descend(parent, &node, index);  in radix_tree_tag_clear()
1047 	if (node)  in radix_tree_tag_clear()
1050 	return node;  in radix_tree_tag_clear()
1063 	node_tag_clear(root, iter->node, tag, iter_offset(iter));  in radix_tree_iter_tag_clear()
1067  * radix_tree_tag_get - get a tag on a radix tree node
1078  * the RCU lock is held, unless tag modification and node deletion are excluded
1084 	struct radix_tree_node *node, *parent;  in radix_tree_tag_get()  local
1090 	radix_tree_load_root(root, &node, &maxindex);  in radix_tree_tag_get()
1094 	while (radix_tree_is_internal_node(node)) {  in radix_tree_tag_get()
1097 		parent = entry_to_node(node);  in radix_tree_tag_get()
1098 		offset = radix_tree_descend(parent, &node, index);  in radix_tree_tag_get()
1102 		if (node == RADIX_TREE_RETRY)  in radix_tree_tag_get()
1110 /* Construct iter->tags bit-mask from node->tags[tag] array */
1112 				struct radix_tree_node *node, unsigned offset,  in set_iter_tags()  argument
1118 	if (!node) {  in set_iter_tags()
1123 	iter->tags = node->tags[tag][tag_long] >> tag_bit;  in set_iter_tags()
1129 			iter->tags |= node->tags[tag][tag_long + 1] <<  in set_iter_tags()
1158 	struct radix_tree_node *node, *child;  in radix_tree_next_chunk()  local
1189 		iter->node = NULL;  in radix_tree_next_chunk()
1194 		node = entry_to_node(child);  in radix_tree_next_chunk()
1195 		offset = radix_tree_descend(node, &child, index);  in radix_tree_next_chunk()
1198 				!tag_get(node, tag, offset) : !child) {  in radix_tree_next_chunk()
1204 				offset = radix_tree_find_next_bit(node, tag,  in radix_tree_next_chunk()
1209 							node->slots[offset]);  in radix_tree_next_chunk()
1213 			index &= ~node_maxindex(node);  in radix_tree_next_chunk()
1214 			index += offset << node->shift;  in radix_tree_next_chunk()
1220 			child = rcu_dereference_raw(node->slots[offset]);  in radix_tree_next_chunk()
1227 	} while (node->shift && radix_tree_is_internal_node(child));  in radix_tree_next_chunk()
1230 	iter->index = (index &~ node_maxindex(node)) | offset;  in radix_tree_next_chunk()
1231 	iter->next_index = (index | node_maxindex(node)) + 1;  in radix_tree_next_chunk()
1232 	iter->node = node;  in radix_tree_next_chunk()
1235 		set_iter_tags(iter, node, offset, tag);  in radix_tree_next_chunk()
1237 	return node->slots + offset;  in radix_tree_next_chunk()
1365 				struct radix_tree_node *node, void __rcu **slot)  in __radix_tree_delete()  argument
1369 	unsigned offset = get_slot_offset(node, slot);  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()
1378 	replace_slot(slot, NULL, node, -1, values);  in __radix_tree_delete()
1379 	return node && delete_node(root, node);  in __radix_tree_delete()
1389  * This may result in the current node being freed; if it is, the iterator
1397 	if (__radix_tree_delete(root, iter->node, slot))  in radix_tree_iter_delete()
1416 	struct radix_tree_node *node = NULL;  in radix_tree_delete_item()  local
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()
1424 						get_slot_offset(node, slot))))  in radix_tree_delete_item()
1430 	__radix_tree_delete(root, node, slot);  in radix_tree_delete_item()
1480 	struct radix_tree_node *node = NULL, *child;  in idr_get_free()  local
1505 			/* Have to add a child node.  */  in idr_get_free()
1506 			child = radix_tree_node_alloc(gfp, node, root, shift,  in idr_get_free()
1512 			if (node)  in idr_get_free()
1513 				node->count++;  in idr_get_free()
1517 		node = entry_to_node(child);  in idr_get_free()
1518 		offset = radix_tree_descend(node, &child, start);  in idr_get_free()
1519 		if (!tag_get(node, IDR_FREE, offset)) {  in idr_get_free()
1520 			offset = radix_tree_find_next_bit(node, IDR_FREE,  in idr_get_free()
1522 			start = next_index(start, node, offset);  in idr_get_free()
1526 				offset = node->offset + 1;  in idr_get_free()
1527 				node = node->parent;  in idr_get_free()
1528 				if (!node)  in idr_get_free()
1530 				shift = node->shift;  in idr_get_free()
1532 			child = rcu_dereference_raw(node->slots[offset]);  in idr_get_free()
1534 		slot = &node->slots[offset];  in idr_get_free()
1538 	if (node)  in idr_get_free()
1539 		iter->next_index = 1 + min(max, (start | node_maxindex(node)));  in idr_get_free()
1542 	iter->node = node;  in idr_get_free()
1543 	set_iter_tags(iter, node, offset, IDR_FREE);  in idr_get_free()
1561 	struct radix_tree_node *node = rcu_dereference_raw(idr->idr_rt.xa_head);  in idr_destroy()  local
1562 	if (radix_tree_is_internal_node(node))  in idr_destroy()
1563 		radix_tree_free_nodes(node);  in idr_destroy()
1572 	struct radix_tree_node *node = arg;  in radix_tree_node_ctor()  local
1574 	memset(node, 0, sizeof(*node));  in radix_tree_node_ctor()
1575 	INIT_LIST_HEAD(&node->private_list);  in radix_tree_node_ctor()
1581 	struct radix_tree_node *node;  in radix_tree_cpu_dead()  local
1586 		node = rtp->nodes;  in radix_tree_cpu_dead()
1587 		rtp->nodes = node->parent;  in radix_tree_cpu_dead()
1588 		kmem_cache_free(radix_tree_node_cachep, node);  in radix_tree_cpu_dead()