1 // SPDX-License-Identifier: GPL-2.0-or-later
24 #include <linux/radix-tree.h>
36  * The radix tree is variable-height, so an insert operation not only has
46 #define RADIX_TREE_PRELOAD_SIZE (RADIX_TREE_MAX_PATH * 2 - 1)
52 #define IDR_INDEX_BITS		(8 /* CHAR_BIT */ * sizeof(int) - 1)
55 #define IDR_PRELOAD_SIZE	(IDR_MAX_PATH * 2 - 1)
58  * Per-cpu pool of preloaded nodes
78 get_slot_offset(const struct radix_tree_node *parent, void __rcu **slot)  in get_slot_offset()  argument
80 	return parent ? slot - parent->slots : 0;  in get_slot_offset()
83 static unsigned int radix_tree_descend(const struct radix_tree_node *parent,  in radix_tree_descend()  argument
86 	unsigned int offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK;  in radix_tree_descend()
87 	void __rcu **entry = rcu_dereference_raw(parent->slots[offset]);  in radix_tree_descend()
95 	return root->xa_flags & (__GFP_BITS_MASK & ~GFP_ZONEMASK);  in root_gfp_mask()
101 	__set_bit(offset, node->tags[tag]);  in tag_set()
107 	__clear_bit(offset, node->tags[tag]);  in tag_clear()
113 	return test_bit(offset, node->tags[tag]);  in tag_get()
118 	root->xa_flags |= (__force gfp_t)(1 << (tag + ROOT_TAG_SHIFT));  in root_tag_set()
123 	root->xa_flags &= (__force gfp_t)~(1 << (tag + ROOT_TAG_SHIFT));  in root_tag_clear()
128 	root->xa_flags &= (__force gfp_t)((1 << ROOT_TAG_SHIFT) - 1);  in root_tag_clear_all()
133 	return (__force int)root->xa_flags & (1 << (tag + ROOT_TAG_SHIFT));  in root_tag_get()
138 	return (__force unsigned)root->xa_flags >> ROOT_TAG_SHIFT;  in root_tags_get()
143 	return !!(root->xa_flags & ROOT_IS_IDR);  in is_idr()
155 		if (node->tags[tag][idx])  in any_tag_set()
163 	bitmap_fill(node->tags[tag], RADIX_TREE_MAP_SIZE);  in all_tag_set()
167  * radix_tree_find_next_bit - find the next set bit in a memory region
181 	const unsigned long *addr = node->tags[tag];  in radix_tree_find_next_bit()
190 		offset = (offset + BITS_PER_LONG) & ~(BITS_PER_LONG - 1);  in radix_tree_find_next_bit()
203 	return iter->index & RADIX_TREE_MAP_MASK;  in iter_offset()
211 	return (RADIX_TREE_MAP_SIZE << shift) - 1;  in shift_maxindex()
216 	return shift_maxindex(node->shift);  in node_maxindex()
223 	return (index & ~node_maxindex(node)) + (offset << node->shift);  in next_index()
231 radix_tree_node_alloc(gfp_t gfp_mask, struct radix_tree_node *parent,  in radix_tree_node_alloc()  argument
262 		if (rtp->nr) {  in radix_tree_node_alloc()
263 			ret = rtp->nodes;  in radix_tree_node_alloc()
264 			rtp->nodes = ret->parent;  in radix_tree_node_alloc()
265 			rtp->nr--;  in radix_tree_node_alloc()
278 		ret->shift = shift;  in radix_tree_node_alloc()
279 		ret->offset = offset;  in radix_tree_node_alloc()
280 		ret->count = count;  in radix_tree_node_alloc()
281 		ret->nr_values = nr_values;  in radix_tree_node_alloc()
282 		ret->parent = parent;  in radix_tree_node_alloc()
283 		ret->array = root;  in radix_tree_node_alloc()
295 	 * non-NULL entries by radix_tree_free_nodes, so clear the entries  in radix_tree_node_rcu_free()
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()
308 	call_rcu(&node->rcu_head, radix_tree_node_rcu_free);  in radix_tree_node_free()
314  * success, return zero, with preemption disabled.  On error, return -ENOMEM
324 	int ret = -ENOMEM;  in __radix_tree_preload()
334 	while (rtp->nr < nr) {  in __radix_tree_preload()
341 		if (rtp->nr < nr) {  in __radix_tree_preload()
342 			node->parent = rtp->nodes;  in __radix_tree_preload()
343 			rtp->nodes = node;  in __radix_tree_preload()
344 			rtp->nr++;  in __radix_tree_preload()
357  * success, return zero, with preemption disabled.  On error, return -ENOMEM
365 	/* Warn on non-sensical use... */  in radix_tree_preload()
374  * disabled. On error, return -ENOMEM with preemption not disabled.
389 	struct radix_tree_node *node = rcu_dereference_raw(root->xa_head);  in radix_tree_load_root()
396 		return node->shift + RADIX_TREE_MAP_SHIFT;  in radix_tree_load_root()
418 	entry = rcu_dereference_raw(root->xa_head);  in radix_tree_extend()
426 			return -ENOMEM;  in radix_tree_extend()
435 			/* Propagate the aggregated tag info to the new child */  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()
455 		rcu_assign_pointer(root->xa_head, entry);  in radix_tree_extend()
463  *	radix_tree_shrink    -    shrink radix tree to minimum height
471 		struct radix_tree_node *node = rcu_dereference_raw(root->xa_head);  in radix_tree_shrink()
472 		struct radix_tree_node *child;  in radix_tree_shrink()  local
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()
485 		if (!child)  in radix_tree_shrink()
493 		if (!node->shift && is_idr(root))  in radix_tree_shrink()
496 		if (radix_tree_is_internal_node(child))  in radix_tree_shrink()
497 			entry_to_node(child)->parent = NULL;  in radix_tree_shrink()
503 		 * (node->slots[0]), it will be safe to dereference the new  in radix_tree_shrink()
504 		 * one (root->xa_head) as far as dependent read barriers go.  in radix_tree_shrink()
506 		root->xa_head = (void __rcu *)child;  in radix_tree_shrink()
513 		 * find the item. However if this was a bottom-level node,  in radix_tree_shrink()
523 		 * to retry the entire slot lookup -- the indirect pointer  in radix_tree_shrink()
528 		node->count = 0;  in radix_tree_shrink()
529 		if (!radix_tree_is_internal_node(child)) {  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()
547 		struct radix_tree_node *parent;  in delete_node()  local
549 		if (node->count) {  in delete_node()
551 					rcu_dereference_raw(root->xa_head))  in delete_node()
556 		parent = node->parent;  in delete_node()
557 		if (parent) {  in delete_node()
558 			parent->slots[node->offset] = NULL;  in delete_node()
559 			parent->count--;  in delete_node()
567 			root->xa_head = NULL;  in delete_node()
570 		WARN_ON_ONCE(!list_empty(&node->private_list));  in delete_node()
574 		node = parent;  in delete_node()
581  *	__radix_tree_create	-	create a slot in a radix tree
591  *	allocated and @root->xa_head is used as a direct slot instead of
594  *	Returns -ENOMEM, or 0 for success.
600 	struct radix_tree_node *node = NULL, *child;  in __radix_tree_create()  local
601 	void __rcu **slot = (void __rcu **)&root->xa_head;  in __radix_tree_create()
607 	shift = radix_tree_load_root(root, &child, &maxindex);  in __radix_tree_create()
615 		child = rcu_dereference_raw(root->xa_head);  in __radix_tree_create()
619 		shift -= RADIX_TREE_MAP_SHIFT;  in __radix_tree_create()
620 		if (child == NULL) {  in __radix_tree_create()
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()
624 			if (!child)  in __radix_tree_create()
625 				return -ENOMEM;  in __radix_tree_create()
626 			rcu_assign_pointer(*slot, node_to_entry(child));  in __radix_tree_create()
628 				node->count++;  in __radix_tree_create()
629 		} else if (!radix_tree_is_internal_node(child))  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()
657 	struct radix_tree_node *child = entry_to_node(node);  in radix_tree_free_nodes()  local
660 		void *entry = rcu_dereference_raw(child->slots[offset]);  in radix_tree_free_nodes()
661 		if (xa_is_node(entry) && child->shift) {  in radix_tree_free_nodes()
662 			child = entry_to_node(entry);  in radix_tree_free_nodes()
668 			struct radix_tree_node *old = child;  in radix_tree_free_nodes()
669 			offset = child->offset + 1;  in radix_tree_free_nodes()
670 			child = child->parent;  in radix_tree_free_nodes()
671 			WARN_ON_ONCE(!list_empty(&old->private_list));  in radix_tree_free_nodes()
683 		return -EEXIST;  in insert_entries()
686 		node->count++;  in insert_entries()
688 			node->nr_values++;  in insert_entries()
694  *	__radix_tree_insert    -    insert into a radix tree
732  *	__radix_tree_lookup	-	lookup an item in a radix tree
742  *	allocated and @root->xa_head is used as a direct slot instead of
749 	struct radix_tree_node *node, *parent;  in __radix_tree_lookup()  local
754 	parent = NULL;  in __radix_tree_lookup()
755 	slot = (void __rcu **)&root->xa_head;  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()
765 		slot = parent->slots + offset;  in __radix_tree_lookup()
768 		if (parent->shift == 0)  in __radix_tree_lookup()
773 		*nodep = parent;  in __radix_tree_lookup()
780  *	radix_tree_lookup_slot    -    lookup a slot in a radix tree
785  *	radix tree @root. This is useful for update-if-exists operations.
804  *	radix_tree_lookup    -    perform lookup operation on a radix tree
825 		node->count += count;  in replace_slot()
826 		node->nr_values += values;  in replace_slot()
844  * non-NULL.  For the IDA, we mark slots as being IDR_FREE while they still
860 	return !!item - !!old;  in calculate_count()
864  * __radix_tree_replace		- replace item in a slot
878 	int values = !!xa_is_value(item) - !!xa_is_value(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()
897  * radix_tree_replace_slot	- replace item in a slot
906  * NOTE: This cannot be used to switch between non-entries (empty slots),
920  * radix_tree_iter_replace - replace item in a slot
932 	__radix_tree_replace(root, iter->node, slot, item);  in radix_tree_iter_replace()
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
961  *	Returns the address of the tagged item.  Setting a tag on a not-present
967 	struct radix_tree_node *node, *parent;  in radix_tree_tag_set()  local
976 		parent = entry_to_node(node);  in radix_tree_tag_set()
977 		offset = radix_tree_descend(parent, &node, index);  in radix_tree_tag_set()
980 		if (!tag_get(parent, tag, offset))  in radix_tree_tag_set()
981 			tag_set(parent, tag, offset);  in radix_tree_tag_set()
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
1021  *	next-to-leaf node, etc.
1029 	struct radix_tree_node *node, *parent;  in radix_tree_tag_clear()  local
1037 	parent = NULL;  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()
1045 		node_tag_clear(root, parent, tag, offset);  in radix_tree_tag_clear()
1052   * radix_tree_iter_tag_clear - clear a tag on the current iterator entry
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
1081 	struct radix_tree_node *node, *parent;  in radix_tree_tag_get()  local
1094 		parent = entry_to_node(node);  in radix_tree_tag_get()
1095 		offset = radix_tree_descend(parent, &node, index);  in radix_tree_tag_get()
1097 		if (!tag_get(parent, tag, offset))  in radix_tree_tag_get()
1107 /* Construct iter->tags bit-mask from node->tags[tag] array */
1116 		iter->tags = 1;  in set_iter_tags()
1120 	iter->tags = node->tags[tag][tag_long] >> tag_bit;  in set_iter_tags()
1123 	if (tag_long < RADIX_TREE_TAG_LONGS - 1) {  in set_iter_tags()
1126 			iter->tags |= node->tags[tag][tag_long + 1] <<  in set_iter_tags()
1127 						(BITS_PER_LONG - tag_bit);  in set_iter_tags()
1129 		iter->next_index = __radix_tree_iter_add(iter, BITS_PER_LONG);  in set_iter_tags()
1137 	iter->index = __radix_tree_iter_add(iter, 1);  in radix_tree_iter_resume()
1138 	iter->next_index = iter->index;  in radix_tree_iter_resume()
1139 	iter->tags = 0;  in radix_tree_iter_resume()
1145  * radix_tree_next_chunk - find next chunk of slots for iteration
1156 	struct radix_tree_node *node, *child;  in radix_tree_next_chunk()  local
1163 	 * Catch next_index overflow after ~0UL. iter->index never overflows  in radix_tree_next_chunk()
1165 	 * And we cannot overflow iter->next_index in a single step,  in radix_tree_next_chunk()
1171 	index = iter->next_index;  in radix_tree_next_chunk()
1172 	if (!index && iter->index)  in radix_tree_next_chunk()
1176 	radix_tree_load_root(root, &child, &maxindex);  in radix_tree_next_chunk()
1179 	if (!child)  in radix_tree_next_chunk()
1182 	if (!radix_tree_is_internal_node(child)) {  in radix_tree_next_chunk()
1183 		/* Single-slot tree */  in radix_tree_next_chunk()
1184 		iter->index = index;  in radix_tree_next_chunk()
1185 		iter->next_index = maxindex + 1;  in radix_tree_next_chunk()
1186 		iter->tags = 1;  in radix_tree_next_chunk()
1187 		iter->node = NULL;  in radix_tree_next_chunk()
1188 		return (void __rcu **)&root->xa_head;  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()
1207 							node->slots[offset]);  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()
1221 		if (!child)  in radix_tree_next_chunk()
1223 		if (child == RADIX_TREE_RETRY)  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()
1235 	return node->slots + offset;  in radix_tree_next_chunk()
1240  *	radix_tree_gang_lookup - perform multiple lookup on a radix tree
1246  *	Performs an index-ascending scan of the tree for present items.  Places
1287  *	radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree
1295  *	Performs an index-ascending scan of the tree for present items which
1328  *	radix_tree_gang_lookup_tag_slot - perform multiple slot lookup on a
1336  *	Performs an index-ascending scan of the tree for present items which
1366 	int values = xa_is_value(old) ? -1 : 0;  in __radix_tree_delete()
1376 	replace_slot(slot, NULL, node, -1, values);  in __radix_tree_delete()
1381  * radix_tree_iter_delete - delete the entry at this iterator position
1395 	if (__radix_tree_delete(root, iter->node, slot))  in radix_tree_iter_delete()
1396 		iter->index = iter->next_index;  in radix_tree_iter_delete()
1401  * radix_tree_delete_item - delete an item from a radix tree
1435  * radix_tree_delete - delete an entry from a radix tree
1450  *	radix_tree_tagged - test whether any items in the tree are tagged
1461  * idr_preload - preload for idr_alloc()
1478 	struct radix_tree_node *node = NULL, *child;  in idr_get_free()  local
1479 	void __rcu **slot = (void __rcu **)&root->xa_head;  in idr_get_free()
1480 	unsigned long maxindex, start = iter->next_index;  in idr_get_free()
1484 	shift = radix_tree_load_root(root, &child, &maxindex);  in idr_get_free()
1488 		return ERR_PTR(-ENOSPC);  in idr_get_free()
1495 		child = rcu_dereference_raw(root->xa_head);  in idr_get_free()
1501 		shift -= RADIX_TREE_MAP_SHIFT;  in idr_get_free()
1502 		if (child == NULL) {  in idr_get_free()
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()
1506 			if (!child)  in idr_get_free()
1507 				return ERR_PTR(-ENOMEM);  in idr_get_free()
1508 			all_tag_set(child, IDR_FREE);  in idr_get_free()
1509 			rcu_assign_pointer(*slot, node_to_entry(child));  in idr_get_free()
1511 				node->count++;  in idr_get_free()
1512 		} else if (!radix_tree_is_internal_node(child))  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()
1522 				return ERR_PTR(-ENOSPC);  in idr_get_free()
1524 				offset = node->offset + 1;  in idr_get_free()
1525 				node = node->parent;  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()
1535 	iter->index = start;  in idr_get_free()
1537 		iter->next_index = 1 + min(max, (start | node_maxindex(node)));  in idr_get_free()
1539 		iter->next_index = 1;  in idr_get_free()
1540 	iter->node = node;  in idr_get_free()
1547  * idr_destroy - release all internal memory from an IDR
1553  * A typical clean-up sequence for objects stored in an idr tree will use
1559 	struct radix_tree_node *node = rcu_dereference_raw(idr->idr_rt.xa_head);  in idr_destroy()
1562 	idr->idr_rt.xa_head = NULL;  in idr_destroy()
1563 	root_tag_set(&idr->idr_rt, IDR_FREE);  in idr_destroy()
1573 	INIT_LIST_HEAD(&node->private_list);  in radix_tree_node_ctor()
1581 	/* Free per-cpu pool of preloaded nodes */  in radix_tree_cpu_dead()
1583 	while (rtp->nr) {  in radix_tree_cpu_dead()
1584 		node = rtp->nodes;  in radix_tree_cpu_dead()
1585 		rtp->nodes = node->parent;  in radix_tree_cpu_dead()
1587 		rtp->nr--;  in radix_tree_cpu_dead()