Lines Matching +full:root +full:- +full:node
1 // SPDX-License-Identifier: GPL-2.0-or-later
24 #include <linux/radix-tree.h>
30 #include "radix-tree.h"
33 * Radix tree node cache.
38 * The radix tree is variable-height, so an insert operation not only has
45 * of RADIX_TREE_MAX_PATH size to be created, with only the root node shared.
48 #define RADIX_TREE_PRELOAD_SIZE (RADIX_TREE_MAX_PATH * 2 - 1)
54 #define IDR_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(int) - 1)
57 #define IDR_PRELOAD_SIZE (IDR_MAX_PATH * 2 - 1)
60 * Per-cpu pool of preloaded nodes
82 return parent ? slot - parent->slots : 0; in get_slot_offset()
88 unsigned int offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK; in radix_tree_descend()
89 void __rcu **entry = rcu_dereference_raw(parent->slots[offset]); in radix_tree_descend()
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()
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()
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()
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()
169 * radix_tree_find_next_bit - find the next set bit in a memory region
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()
192 offset = (offset + BITS_PER_LONG) & ~(BITS_PER_LONG - 1); in radix_tree_find_next_bit()
205 return iter->index & RADIX_TREE_MAP_MASK; in iter_offset()
213 return (RADIX_TREE_MAP_SIZE << shift) - 1; in shift_maxindex()
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()
234 struct radix_tree_root *root, in radix_tree_node_alloc() argument
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()
264 if (rtp->nr) { in radix_tree_node_alloc()
265 ret = rtp->nodes; in radix_tree_node_alloc()
266 rtp->nodes = ret->parent; in radix_tree_node_alloc()
267 rtp->nr--; in radix_tree_node_alloc()
280 ret->shift = shift; in radix_tree_node_alloc()
281 ret->offset = offset; in radix_tree_node_alloc()
282 ret->count = count; in radix_tree_node_alloc()
283 ret->nr_values = nr_values; in radix_tree_node_alloc()
284 ret->parent = parent; in radix_tree_node_alloc()
285 ret->array = root; in radix_tree_node_alloc()
292 struct radix_tree_node *node = in radix_tree_node_rcu_free() local
297 * non-NULL entries by radix_tree_free_nodes, so clear the entries in radix_tree_node_rcu_free()
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()
316 * success, return zero, with preemption disabled. On error, return -ENOMEM
325 struct radix_tree_node *node; in __radix_tree_preload() local
326 int ret = -ENOMEM; in __radix_tree_preload()
336 while (rtp->nr < nr) { in __radix_tree_preload()
338 node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask); in __radix_tree_preload()
339 if (node == NULL) in __radix_tree_preload()
343 if (rtp->nr < nr) { in __radix_tree_preload()
344 node->parent = rtp->nodes; in __radix_tree_preload()
345 rtp->nodes = node; in __radix_tree_preload()
346 rtp->nr++; in __radix_tree_preload()
348 kmem_cache_free(radix_tree_node_cachep, node); in __radix_tree_preload()
359 * success, return zero, with preemption disabled. On error, return -ENOMEM
367 /* Warn on non-sensical use... */ in radix_tree_preload()
376 * disabled. On error, return -ENOMEM with preemption not disabled.
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() 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()
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()
425 struct radix_tree_node *node = radix_tree_node_alloc(gfp, NULL, in radix_tree_extend() local
426 root, shift, 0, 1, 0); in radix_tree_extend()
427 if (!node) in radix_tree_extend()
428 return -ENOMEM; in radix_tree_extend()
430 if (is_idr(root)) { in radix_tree_extend()
431 all_tag_set(node, IDR_FREE); in radix_tree_extend()
432 if (!root_tag_get(root, IDR_FREE)) { in radix_tree_extend()
433 tag_clear(node, IDR_FREE, 0); 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()
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()
457 rcu_assign_pointer(root->xa_head, entry); in radix_tree_extend()
465 * radix_tree_shrink - shrink radix tree to minimum height
466 * @root: radix tree root
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() 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()
491 * For an IDR, we must not shrink entry 0 into the root in in radix_tree_shrink()
495 if (!node->shift && is_idr(root)) in radix_tree_shrink()
499 entry_to_node(child)->parent = NULL; 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()
506 * one (root->xa_head) as far as dependent read barriers go. 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()
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()
525 * to retry the entire slot lookup -- the indirect pointer 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()
543 static bool delete_node(struct radix_tree_root *root, in delete_node() argument
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()
553 rcu_dereference_raw(root->xa_head)) in delete_node()
554 deleted |= radix_tree_shrink(root); in delete_node()
558 parent = node->parent; in delete_node()
560 parent->slots[node->offset] = NULL; in delete_node()
561 parent->count--; 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()
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()
583 * __radix_tree_create - create a slot in a radix tree
584 * @root: radix tree root
586 * @nodep: returns node
589 * Create, if necessary, and return the node and slot for an item
590 * at position @index in the radix tree @root.
593 * allocated and @root->xa_head is used as a direct slot instead of
594 * pointing to a node, in which case *@nodep will be NULL.
596 * Returns -ENOMEM, or 0 for success.
598 static int __radix_tree_create(struct radix_tree_root *root, in __radix_tree_create() argument
602 struct radix_tree_node *node = NULL, *child; in __radix_tree_create() local
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()
621 shift -= RADIX_TREE_MAP_SHIFT; in __radix_tree_create()
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()
627 return -ENOMEM; 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()
662 void *entry = rcu_dereference_raw(child->slots[offset]); in radix_tree_free_nodes()
663 if (xa_is_node(entry) && child->shift) { in radix_tree_free_nodes()
671 offset = child->offset + 1; in radix_tree_free_nodes()
672 child = child->parent; in radix_tree_free_nodes()
673 WARN_ON_ONCE(!list_empty(&old->private_list)); 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
685 return -EEXIST; in insert_entries()
687 if (node) { in insert_entries()
688 node->count++; in insert_entries()
690 node->nr_values++; in insert_entries()
696 * radix_tree_insert - insert into a radix tree
697 * @root: radix tree root
703 int radix_tree_insert(struct radix_tree_root *root, unsigned long index, in radix_tree_insert() argument
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()
726 BUG_ON(root_tags_get(root)); in radix_tree_insert()
734 * __radix_tree_lookup - lookup an item in a radix tree
735 * @root: radix tree root
737 * @nodep: returns node
741 * tree @root.
744 * allocated and @root->xa_head is used as a direct slot instead of
745 * pointing to a node, in which case *@nodep will be NULL.
747 void *__radix_tree_lookup(const struct radix_tree_root *root, in __radix_tree_lookup() argument
751 struct radix_tree_node *node, *parent; in __radix_tree_lookup() local
757 slot = (void __rcu **)&root->xa_head; in __radix_tree_lookup()
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()
767 slot = parent->slots + offset; in __radix_tree_lookup()
768 if (node == RADIX_TREE_RETRY) in __radix_tree_lookup()
770 if (parent->shift == 0) in __radix_tree_lookup()
778 return node; in __radix_tree_lookup()
782 * radix_tree_lookup_slot - lookup a slot in a radix tree
783 * @root: radix tree root
787 * radix tree @root. This is useful for update-if-exists operations.
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()
806 * radix_tree_lookup - perform lookup operation on a radix tree
807 * @root: radix tree root
810 * Lookup the item at the position @index in the radix tree @root.
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()
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()
834 static bool node_tag_get(const struct radix_tree_root *root, in node_tag_get() argument
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()
840 return root_tag_get(root, tag); in node_tag_get()
846 * non-NULL. For the IDA, we mark slots as being IDR_FREE while they still
850 static int calculate_count(struct radix_tree_root *root, in calculate_count() argument
851 struct radix_tree_node *node, void __rcu **slot, in calculate_count() argument
854 if (is_idr(root)) { in calculate_count()
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()
862 return !!item - !!old; in calculate_count()
866 * __radix_tree_replace - replace item in a slot
867 * @root: radix tree root
868 * @node: pointer to tree node
869 * @slot: pointer to slot in @node
875 void __radix_tree_replace(struct radix_tree_root *root, in __radix_tree_replace() argument
876 struct radix_tree_node *node, in __radix_tree_replace() argument
880 int values = !!xa_is_value(item) - !!xa_is_value(old); in __radix_tree_replace()
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()
899 * radix_tree_replace_slot - replace item in a slot
900 * @root: radix tree root
908 * NOTE: This cannot be used to switch between non-entries (empty slots),
910 * inside the radix tree node. When switching from one type of entry or
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()
922 * radix_tree_iter_replace - replace item in a slot
923 * @root: radix tree root
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
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()
950 if (!root_tag_get(root, tag)) in node_tag_set()
951 root_tag_set(root, tag); in node_tag_set()
955 * radix_tree_tag_set - set a tag on a radix tree node
956 * @root: radix tree root
962 * the root all the way down to the leaf node.
964 * Returns the address of the tagged item. Setting a tag on a not-present
967 void *radix_tree_tag_set(struct radix_tree_root *root, in radix_tree_tag_set() argument
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()
987 /* set the root's tag bit */ 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()
991 return node; in radix_tree_tag_set()
995 static void node_tag_clear(struct radix_tree_root *root, in node_tag_clear() argument
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()
1010 /* clear the root's tag bit */ in node_tag_clear()
1011 if (root_tag_get(root, tag)) in node_tag_clear()
1012 root_tag_clear(root, tag); in node_tag_clear()
1016 * radix_tree_tag_clear - clear a tag on a radix tree node
1017 * @root: radix tree root
1023 * the leaf node to have no tags set then clear the tag in the
1024 * next-to-leaf node, etc.
1029 void *radix_tree_tag_clear(struct radix_tree_root *root, in radix_tree_tag_clear() argument
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()
1048 node_tag_clear(root, parent, tag, offset); in radix_tree_tag_clear()
1050 return node; in radix_tree_tag_clear()
1055 * radix_tree_iter_tag_clear - clear a tag on the current iterator entry
1056 * @root: radix tree root
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()
1067 * radix_tree_tag_get - get a tag on a radix tree node
1068 * @root: radix tree root
1078 * the RCU lock is held, unless tag modification and node deletion are excluded
1081 int radix_tree_tag_get(const struct radix_tree_root *root, in radix_tree_tag_get() argument
1084 struct radix_tree_node *node, *parent; in radix_tree_tag_get() local
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()
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()
1119 iter->tags = 1; in set_iter_tags()
1123 iter->tags = node->tags[tag][tag_long] >> tag_bit; in set_iter_tags()
1126 if (tag_long < RADIX_TREE_TAG_LONGS - 1) { in set_iter_tags()
1129 iter->tags |= node->tags[tag][tag_long + 1] << in set_iter_tags()
1130 (BITS_PER_LONG - tag_bit); in set_iter_tags()
1132 iter->next_index = __radix_tree_iter_add(iter, BITS_PER_LONG); in set_iter_tags()
1139 iter->index = __radix_tree_iter_add(iter, 1); in radix_tree_iter_resume()
1140 iter->next_index = iter->index; in radix_tree_iter_resume()
1141 iter->tags = 0; in radix_tree_iter_resume()
1147 * radix_tree_next_chunk - find next chunk of slots for iteration
1149 * @root: radix tree root
1154 void __rcu **radix_tree_next_chunk(const struct radix_tree_root *root, in radix_tree_next_chunk() argument
1158 struct radix_tree_node *node, *child; in radix_tree_next_chunk() local
1161 if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag)) in radix_tree_next_chunk()
1165 * Catch next_index overflow after ~0UL. iter->index never overflows in radix_tree_next_chunk()
1167 * And we cannot overflow iter->next_index in a single step, in radix_tree_next_chunk()
1173 index = iter->next_index; in radix_tree_next_chunk()
1174 if (!index && iter->index) in radix_tree_next_chunk()
1178 radix_tree_load_root(root, &child, &maxindex); in radix_tree_next_chunk()
1185 /* Single-slot tree */ in radix_tree_next_chunk()
1186 iter->index = index; in radix_tree_next_chunk()
1187 iter->next_index = maxindex + 1; in radix_tree_next_chunk()
1188 iter->tags = 1; in radix_tree_next_chunk()
1189 iter->node = NULL; in radix_tree_next_chunk()
1190 return (void __rcu **)&root->xa_head; 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()
1242 * radix_tree_gang_lookup - perform multiple lookup on a radix tree
1243 * @root: radix tree root
1248 * Performs an index-ascending scan of the tree for present items. Places
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()
1289 * radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree
1291 * @root: radix tree root
1297 * Performs an index-ascending scan of the tree for present items which
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()
1330 * radix_tree_gang_lookup_tag_slot - perform multiple slot lookup on a
1332 * @root: radix tree root
1338 * Performs an index-ascending scan of the tree for present items which
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
1365 struct radix_tree_node *node, void __rcu **slot) in __radix_tree_delete() argument
1368 int values = xa_is_value(old) ? -1 : 0; in __radix_tree_delete()
1369 unsigned offset = get_slot_offset(node, slot); in __radix_tree_delete()
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()
1378 replace_slot(slot, NULL, node, -1, values); in __radix_tree_delete()
1379 return node && delete_node(root, node); in __radix_tree_delete()
1383 * radix_tree_iter_delete - delete the entry at this iterator position
1384 * @root: radix tree root
1389 * This may result in the current node being freed; if it is, the iterator
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()
1398 iter->index = iter->next_index; in radix_tree_iter_delete()
1403 * radix_tree_delete_item - delete an item from a radix tree
1404 * @root: radix tree root
1408 * Remove @item at @index from the radix tree rooted at @root.
1413 void *radix_tree_delete_item(struct radix_tree_root *root, in radix_tree_delete_item() argument
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()
1437 * radix_tree_delete - delete an entry from a radix tree
1438 * @root: radix tree root
1441 * Remove the entry at @index from the radix tree rooted at @root.
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()
1452 * radix_tree_tagged - test whether any items in the tree are tagged
1453 * @root: radix tree root
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()
1463 * idr_preload - preload for idr_alloc()
1476 void __rcu **idr_get_free(struct radix_tree_root *root, in idr_get_free() argument
1480 struct radix_tree_node *node = NULL, *child; in idr_get_free() local
1481 void __rcu **slot = (void __rcu **)&root->xa_head; in idr_get_free()
1482 unsigned long maxindex, start = iter->next_index; 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()
1490 return ERR_PTR(-ENOSPC); 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()
1503 shift -= RADIX_TREE_MAP_SHIFT; in idr_get_free()
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()
1509 return ERR_PTR(-ENOMEM); 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()
1524 return ERR_PTR(-ENOSPC); 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()
1537 iter->index = start; 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()
1541 iter->next_index = 1; 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()
1549 * idr_destroy - release all internal memory from an IDR
1555 * A typical clean-up sequence for objects stored in an idr tree will use
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()
1564 idr->idr_rt.xa_head = NULL; in idr_destroy()
1565 root_tag_set(&idr->idr_rt, IDR_FREE); 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
1583 /* Free per-cpu pool of preloaded nodes */ in radix_tree_cpu_dead()
1585 while (rtp->nr) { in radix_tree_cpu_dead()
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()
1589 rtp->nr--; in radix_tree_cpu_dead()