Lines Matching +full:child +full:- +full:node
37 #include <linux/radix-tree.h>
47 * Radix tree node cache.
52 * The radix tree is variable-height, so an insert operation not only has
59 * of RADIX_TREE_MAX_PATH size to be created, with only the root node shared.
62 #define RADIX_TREE_PRELOAD_SIZE (RADIX_TREE_MAX_PATH * 2 - 1)
68 #define IDR_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(int) - 1)
71 #define IDR_PRELOAD_SIZE (IDR_MAX_PATH * 2 - 1)
76 #define IDA_INDEX_BITS (8 * sizeof(int) - 1 - ilog2(IDA_BITMAP_BITS))
79 #define IDA_PRELOAD_SIZE (IDA_MAX_PATH * 2 - 1)
82 * Per-cpu pool of preloaded nodes
86 /* nodes->parent points to next preallocated node */
104 /* Sibling slots point directly to another slot in the same node */
106 bool is_sibling_entry(const struct radix_tree_node *parent, void *node) in is_sibling_entry() argument
108 void __rcu **ptr = node; in is_sibling_entry()
109 return (parent->slots <= ptr) && in is_sibling_entry()
110 (ptr < parent->slots + RADIX_TREE_MAP_SIZE); in is_sibling_entry()
114 bool is_sibling_entry(const struct radix_tree_node *parent, void *node) in is_sibling_entry() argument
123 return parent ? slot - parent->slots : 0; in get_slot_offset()
129 unsigned int offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK; in radix_tree_descend()
130 void __rcu **entry = rcu_dereference_raw(parent->slots[offset]); in radix_tree_descend()
149 return root->gfp_mask & (__GFP_BITS_MASK & ~GFP_ZONEMASK); in root_gfp_mask()
152 static inline void tag_set(struct radix_tree_node *node, unsigned int tag, in tag_set() argument
155 __set_bit(offset, node->tags[tag]); in tag_set()
158 static inline void tag_clear(struct radix_tree_node *node, unsigned int tag, in tag_clear() argument
161 __clear_bit(offset, node->tags[tag]); in tag_clear()
164 static inline int tag_get(const struct radix_tree_node *node, unsigned int tag, in tag_get() argument
167 return test_bit(offset, node->tags[tag]); in tag_get()
172 root->gfp_mask |= (__force gfp_t)(1 << (tag + ROOT_TAG_SHIFT)); in root_tag_set()
177 root->gfp_mask &= (__force gfp_t)~(1 << (tag + ROOT_TAG_SHIFT)); in root_tag_clear()
182 root->gfp_mask &= (1 << ROOT_TAG_SHIFT) - 1; in root_tag_clear_all()
187 return (__force int)root->gfp_mask & (1 << (tag + ROOT_TAG_SHIFT)); in root_tag_get()
192 return (__force unsigned)root->gfp_mask >> ROOT_TAG_SHIFT; in root_tags_get()
197 return !!(root->gfp_mask & ROOT_IS_IDR); in is_idr()
201 * Returns 1 if any slot in the node has this tag set.
204 static inline int any_tag_set(const struct radix_tree_node *node, in any_tag_set() argument
209 if (node->tags[tag][idx]) in any_tag_set()
215 static inline void all_tag_set(struct radix_tree_node *node, unsigned int tag) in all_tag_set() argument
217 bitmap_fill(node->tags[tag], RADIX_TREE_MAP_SIZE); in all_tag_set()
221 * radix_tree_find_next_bit - find the next set bit in a memory region
232 radix_tree_find_next_bit(struct radix_tree_node *node, unsigned int tag, in radix_tree_find_next_bit() argument
235 const unsigned long *addr = node->tags[tag]; in radix_tree_find_next_bit()
244 offset = (offset + BITS_PER_LONG) & ~(BITS_PER_LONG - 1); in radix_tree_find_next_bit()
257 return (iter->index >> iter_shift(iter)) & RADIX_TREE_MAP_MASK; in iter_offset()
265 return (RADIX_TREE_MAP_SIZE << shift) - 1; in shift_maxindex()
268 static inline unsigned long node_maxindex(const struct radix_tree_node *node) in node_maxindex() argument
270 return shift_maxindex(node->shift); in node_maxindex()
274 const struct radix_tree_node *node, in next_index() argument
277 return (index & ~node_maxindex(node)) + (offset << node->shift); in next_index()
281 static void dump_node(struct radix_tree_node *node, unsigned long index) in dump_node() argument
285 …pr_debug("radix node: %p offset %d indices %lu-%lu parent %p tags %lx %lx %lx shift %d count %d ex… in dump_node()
286 node, node->offset, index, index | node_maxindex(node), in dump_node()
287 node->parent, in dump_node()
288 node->tags[0][0], node->tags[1][0], node->tags[2][0], in dump_node()
289 node->shift, node->count, node->exceptional); in dump_node()
292 unsigned long first = index | (i << node->shift); in dump_node()
293 unsigned long last = first | ((1UL << node->shift) - 1); in dump_node()
294 void *entry = node->slots[i]; in dump_node()
298 pr_debug("radix retry offset %ld indices %lu-%lu parent %p\n", in dump_node()
299 i, first, last, node); in dump_node()
301 pr_debug("radix entry %p offset %ld indices %lu-%lu parent %p\n", in dump_node()
302 entry, i, first, last, node); in dump_node()
303 } else if (is_sibling_entry(node, entry)) { in dump_node()
304 pr_debug("radix sblng %p offset %ld indices %lu-%lu parent %p val %p\n", in dump_node()
305 entry, i, first, last, node, in dump_node()
317 root, root->rnode, in radix_tree_dump()
318 root->gfp_mask >> ROOT_TAG_SHIFT); in radix_tree_dump()
319 if (!radix_tree_is_internal_node(root->rnode)) in radix_tree_dump()
321 dump_node(entry_to_node(root->rnode), 0); in radix_tree_dump()
332 struct radix_tree_node *node = entry_to_node(entry); in dump_ida_node() local
334 pr_debug("ida node: %p offset %d indices %lu-%lu parent %p free %lx shift %d count %d\n", in dump_ida_node()
335 node, node->offset, index * IDA_BITMAP_BITS, in dump_ida_node()
336 ((index | node_maxindex(node)) + 1) * in dump_ida_node()
337 IDA_BITMAP_BITS - 1, in dump_ida_node()
338 node->parent, node->tags[0][0], node->shift, in dump_ida_node()
339 node->count); in dump_ida_node()
341 dump_ida_node(node->slots[i], in dump_ida_node()
342 index | (i << node->shift)); in dump_ida_node()
344 pr_debug("ida excp: %p offset %d indices %lu-%lu data %lx\n", in dump_ida_node()
347 index * IDA_BITMAP_BITS + BITS_PER_LONG - in dump_ida_node()
354 pr_debug("ida btmp: %p offset %d indices %lu-%lu data", bitmap, in dump_ida_node()
357 (index + 1) * IDA_BITMAP_BITS - 1); in dump_ida_node()
359 pr_cont(" %lx", bitmap->bitmap[i]); in dump_ida_node()
366 struct radix_tree_root *root = &ida->ida_rt; in ida_dump()
367 pr_debug("ida: %p node %p free %d\n", ida, root->rnode, in ida_dump()
368 root->gfp_mask >> ROOT_TAG_SHIFT); in ida_dump()
369 dump_ida_node(root->rnode, 0); in ida_dump()
395 * cache first for the new node to get accounted to the memory in radix_tree_node_alloc()
405 * succeed in getting a node here (and never reach in radix_tree_node_alloc()
409 if (rtp->nr) { in radix_tree_node_alloc()
410 ret = rtp->nodes; in radix_tree_node_alloc()
411 rtp->nodes = ret->parent; in radix_tree_node_alloc()
412 rtp->nr--; in radix_tree_node_alloc()
425 ret->shift = shift; in radix_tree_node_alloc()
426 ret->offset = offset; in radix_tree_node_alloc()
427 ret->count = count; in radix_tree_node_alloc()
428 ret->exceptional = exceptional; in radix_tree_node_alloc()
429 ret->parent = parent; in radix_tree_node_alloc()
430 ret->root = root; in radix_tree_node_alloc()
437 struct radix_tree_node *node = in radix_tree_node_rcu_free() local
442 * non-NULL entries by radix_tree_free_nodes, so clear the entries in radix_tree_node_rcu_free()
445 memset(node->slots, 0, sizeof(node->slots)); in radix_tree_node_rcu_free()
446 memset(node->tags, 0, sizeof(node->tags)); in radix_tree_node_rcu_free()
447 INIT_LIST_HEAD(&node->private_list); in radix_tree_node_rcu_free()
449 kmem_cache_free(radix_tree_node_cachep, node); in radix_tree_node_rcu_free()
453 radix_tree_node_free(struct radix_tree_node *node) in radix_tree_node_free() argument
455 call_rcu(&node->rcu_head, radix_tree_node_rcu_free); in radix_tree_node_free()
461 * success, return zero, with preemption disabled. On error, return -ENOMEM
470 struct radix_tree_node *node; in __radix_tree_preload() local
471 int ret = -ENOMEM; in __radix_tree_preload()
481 while (rtp->nr < nr) { in __radix_tree_preload()
483 node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask); in __radix_tree_preload()
484 if (node == NULL) in __radix_tree_preload()
488 if (rtp->nr < nr) { in __radix_tree_preload()
489 node->parent = rtp->nodes; in __radix_tree_preload()
490 rtp->nodes = node; in __radix_tree_preload()
491 rtp->nr++; in __radix_tree_preload()
493 kmem_cache_free(radix_tree_node_cachep, node); in __radix_tree_preload()
504 * success, return zero, with preemption disabled. On error, return -ENOMEM
512 /* Warn on non-sensical use... */ in radix_tree_preload()
521 * disabled. On error, return -ENOMEM with preemption not disabled.
542 unsigned layers = (old_order / RADIX_TREE_MAP_SHIFT) - in radix_tree_split_preload()
549 while (layers--) in radix_tree_split_preload()
557 * (1 << order) continuous naturally-aligned elements.
581 * then inserting items starting at ULONG_MAX - (1 << order). in radix_tree_maybe_preload_order()
584 * 0-index item. in radix_tree_maybe_preload_order()
589 nr_nodes += RADIX_TREE_MAX_PATH - subtree_height; in radix_tree_maybe_preload_order()
591 /* Root node is shared. */ in radix_tree_maybe_preload_order()
592 nr_nodes--; in radix_tree_maybe_preload_order()
603 struct radix_tree_node *node = rcu_dereference_raw(root->rnode); in radix_tree_load_root() local
605 *nodep = node; in radix_tree_load_root()
607 if (likely(radix_tree_is_internal_node(node))) { in radix_tree_load_root()
608 node = entry_to_node(node); in radix_tree_load_root()
609 *maxindex = node_maxindex(node); in radix_tree_load_root()
610 return node->shift + RADIX_TREE_MAP_SHIFT; in radix_tree_load_root()
632 entry = rcu_dereference_raw(root->rnode); in radix_tree_extend()
637 struct radix_tree_node *node = radix_tree_node_alloc(gfp, NULL, in radix_tree_extend() local
639 if (!node) in radix_tree_extend()
640 return -ENOMEM; in radix_tree_extend()
643 all_tag_set(node, IDR_FREE); in radix_tree_extend()
645 tag_clear(node, IDR_FREE, 0); in radix_tree_extend()
649 /* Propagate the aggregated tag info to the new child */ in radix_tree_extend()
652 tag_set(node, tag, 0); in radix_tree_extend()
658 entry_to_node(entry)->parent = node; in radix_tree_extend()
660 /* Moving an exceptional root->rnode to a node */ in radix_tree_extend()
661 node->exceptional = 1; in radix_tree_extend()
667 node->slots[0] = (void __rcu *)entry; in radix_tree_extend()
668 entry = node_to_entry(node); in radix_tree_extend()
669 rcu_assign_pointer(root->rnode, entry); in radix_tree_extend()
677 * radix_tree_shrink - shrink radix tree to minimum height
686 struct radix_tree_node *node = rcu_dereference_raw(root->rnode); in radix_tree_shrink() local
687 struct radix_tree_node *child; in radix_tree_shrink() local
689 if (!radix_tree_is_internal_node(node)) in radix_tree_shrink()
691 node = entry_to_node(node); in radix_tree_shrink()
694 * The candidate node has more than one child, or its child in radix_tree_shrink()
695 * is not at the leftmost slot, or the child is a multiorder in radix_tree_shrink()
698 if (node->count != 1) in radix_tree_shrink()
700 child = rcu_dereference_raw(node->slots[0]); in radix_tree_shrink()
701 if (!child) in radix_tree_shrink()
703 if (!radix_tree_is_internal_node(child) && node->shift) in radix_tree_shrink()
706 if (radix_tree_is_internal_node(child)) in radix_tree_shrink()
707 entry_to_node(child)->parent = NULL; in radix_tree_shrink()
711 * moving the node from one part of the tree to another: if it in radix_tree_shrink()
713 * (node->slots[0]), it will be safe to dereference the new in radix_tree_shrink()
714 * one (root->rnode) as far as dependent read barriers go. in radix_tree_shrink()
716 root->rnode = (void __rcu *)child; in radix_tree_shrink()
717 if (is_idr(root) && !tag_get(node, IDR_FREE, 0)) in radix_tree_shrink()
721 * We have a dilemma here. The node's slot[0] must not be in radix_tree_shrink()
723 * find the item. However if this was a bottom-level node, in radix_tree_shrink()
733 * to retry the entire slot lookup -- the indirect pointer in radix_tree_shrink()
734 * problem (replacing direct root node with an indirect pointer in radix_tree_shrink()
738 node->count = 0; in radix_tree_shrink()
739 if (!radix_tree_is_internal_node(child)) { in radix_tree_shrink()
740 node->slots[0] = (void __rcu *)RADIX_TREE_RETRY; in radix_tree_shrink()
742 update_node(node); in radix_tree_shrink()
745 WARN_ON_ONCE(!list_empty(&node->private_list)); in radix_tree_shrink()
746 radix_tree_node_free(node); in radix_tree_shrink()
754 struct radix_tree_node *node, in delete_node() argument
762 if (node->count) { in delete_node()
763 if (node_to_entry(node) == in delete_node()
764 rcu_dereference_raw(root->rnode)) in delete_node()
770 parent = node->parent; in delete_node()
772 parent->slots[node->offset] = NULL; in delete_node()
773 parent->count--; in delete_node()
781 root->rnode = NULL; in delete_node()
784 WARN_ON_ONCE(!list_empty(&node->private_list)); in delete_node()
785 radix_tree_node_free(node); in delete_node()
788 node = parent; in delete_node()
789 } while (node); in delete_node()
795 * __radix_tree_create - create a slot in a radix tree
799 * @nodep: returns node
802 * Create, if necessary, and return the node and slot for an item
806 * allocated and @root->rnode is used as a direct slot instead of
807 * pointing to a node, in which case *@nodep will be NULL.
809 * Returns -ENOMEM, or 0 for success.
815 struct radix_tree_node *node = NULL, *child; in __radix_tree_create() local
816 void __rcu **slot = (void __rcu **)&root->rnode; in __radix_tree_create()
819 unsigned long max = index | ((1UL << order) - 1); in __radix_tree_create()
822 shift = radix_tree_load_root(root, &child, &maxindex); in __radix_tree_create()
825 if (order > 0 && max == ((1UL << order) - 1)) in __radix_tree_create()
832 child = rcu_dereference_raw(root->rnode); in __radix_tree_create()
836 shift -= RADIX_TREE_MAP_SHIFT; in __radix_tree_create()
837 if (child == NULL) { in __radix_tree_create()
838 /* Have to add a child node. */ in __radix_tree_create()
839 child = radix_tree_node_alloc(gfp, node, root, shift, in __radix_tree_create()
841 if (!child) in __radix_tree_create()
842 return -ENOMEM; in __radix_tree_create()
843 rcu_assign_pointer(*slot, node_to_entry(child)); in __radix_tree_create()
844 if (node) in __radix_tree_create()
845 node->count++; in __radix_tree_create()
846 } else if (!radix_tree_is_internal_node(child)) in __radix_tree_create()
850 node = entry_to_node(child); in __radix_tree_create()
851 offset = radix_tree_descend(node, &child, index); in __radix_tree_create()
852 slot = &node->slots[offset]; in __radix_tree_create()
856 *nodep = node; in __radix_tree_create()
863 * Free any nodes below this node. The tree is presumed to not need
871 static void radix_tree_free_nodes(struct radix_tree_node *node) in radix_tree_free_nodes() argument
874 struct radix_tree_node *child = entry_to_node(node); in radix_tree_free_nodes() local
877 void *entry = rcu_dereference_raw(child->slots[offset]); in radix_tree_free_nodes()
879 !is_sibling_entry(child, entry)) { in radix_tree_free_nodes()
880 child = entry_to_node(entry); in radix_tree_free_nodes()
886 struct radix_tree_node *old = child; in radix_tree_free_nodes()
887 offset = child->offset + 1; in radix_tree_free_nodes()
888 child = child->parent; in radix_tree_free_nodes()
889 WARN_ON_ONCE(!list_empty(&old->private_list)); in radix_tree_free_nodes()
891 if (old == entry_to_node(node)) in radix_tree_free_nodes()
898 static inline int insert_entries(struct radix_tree_node *node, in insert_entries() argument
901 struct radix_tree_node *child; in insert_entries() local
904 if (node) { in insert_entries()
905 if (order > node->shift) in insert_entries()
906 n = 1 << (order - node->shift); in insert_entries()
909 offset = get_slot_offset(node, slot); in insert_entries()
916 offset = offset & ~(n - 1); in insert_entries()
917 slot = &node->slots[offset]; in insert_entries()
919 child = node_to_entry(slot); in insert_entries()
924 node->count--; in insert_entries()
926 if (tag_get(node, tag, offset + i)) in insert_entries()
929 return -EEXIST; in insert_entries()
936 rcu_assign_pointer(slot[i], child); in insert_entries()
939 tag_clear(node, tag, offset + i); in insert_entries()
944 tag_set(node, tag, offset); in insert_entries()
947 !is_sibling_entry(node, old) && in insert_entries()
951 node->exceptional--; in insert_entries()
953 if (node) { in insert_entries()
954 node->count += n; in insert_entries()
956 node->exceptional += n; in insert_entries()
961 static inline int insert_entries(struct radix_tree_node *node, in insert_entries() argument
965 return -EEXIST; in insert_entries()
967 if (node) { in insert_entries()
968 node->count++; in insert_entries()
970 node->exceptional++; in insert_entries()
977 * __radix_tree_insert - insert into a radix tree
988 struct radix_tree_node *node; in __radix_tree_insert() local
994 error = __radix_tree_create(root, index, order, &node, &slot); in __radix_tree_insert()
998 error = insert_entries(node, slot, item, order, false); in __radix_tree_insert()
1002 if (node) { in __radix_tree_insert()
1003 unsigned offset = get_slot_offset(node, slot); in __radix_tree_insert()
1004 BUG_ON(tag_get(node, 0, offset)); in __radix_tree_insert()
1005 BUG_ON(tag_get(node, 1, offset)); in __radix_tree_insert()
1006 BUG_ON(tag_get(node, 2, offset)); in __radix_tree_insert()
1016 * __radix_tree_lookup - lookup an item in a radix tree
1019 * @nodep: returns node
1026 * allocated and @root->rnode is used as a direct slot instead of
1027 * pointing to a node, in which case *@nodep will be NULL.
1033 struct radix_tree_node *node, *parent; in __radix_tree_lookup() local
1039 slot = (void __rcu **)&root->rnode; in __radix_tree_lookup()
1040 radix_tree_load_root(root, &node, &maxindex); in __radix_tree_lookup()
1044 while (radix_tree_is_internal_node(node)) { in __radix_tree_lookup()
1047 if (node == RADIX_TREE_RETRY) in __radix_tree_lookup()
1049 parent = entry_to_node(node); in __radix_tree_lookup()
1050 offset = radix_tree_descend(parent, &node, index); in __radix_tree_lookup()
1051 slot = parent->slots + offset; in __radix_tree_lookup()
1058 return node; in __radix_tree_lookup()
1062 * radix_tree_lookup_slot - lookup a slot in a radix tree
1067 * radix tree @root. This is useful for update-if-exists operations.
1086 * radix_tree_lookup - perform lookup operation on a radix tree
1103 static inline void replace_sibling_entries(struct radix_tree_node *node, in replace_sibling_entries() argument
1108 unsigned offset = get_slot_offset(node, slot) + 1; in replace_sibling_entries()
1111 if (rcu_dereference_raw(node->slots[offset]) != ptr) in replace_sibling_entries()
1114 node->slots[offset] = NULL; in replace_sibling_entries()
1115 node->count--; in replace_sibling_entries()
1117 node->exceptional += exceptional; in replace_sibling_entries()
1124 struct radix_tree_node *node, int count, int exceptional) in replace_slot() argument
1129 if (node && (count || exceptional)) { in replace_slot()
1130 node->count += count; in replace_slot()
1131 node->exceptional += exceptional; in replace_slot()
1132 replace_sibling_entries(node, slot, count, exceptional); in replace_slot()
1139 const struct radix_tree_node *node, in node_tag_get() argument
1142 if (node) in node_tag_get()
1143 return tag_get(node, tag, offset); in node_tag_get()
1150 * non-NULL. For the IDA, we mark slots as being IDR_FREE while they still
1155 struct radix_tree_node *node, void __rcu **slot, in calculate_count() argument
1159 unsigned offset = get_slot_offset(node, slot); in calculate_count()
1160 bool free = node_tag_get(root, node, IDR_FREE, offset); in calculate_count()
1166 return !!item - !!old; in calculate_count()
1170 * __radix_tree_replace - replace item in a slot
1172 * @node: pointer to tree node
1173 * @slot: pointer to slot in @node
1181 struct radix_tree_node *node, in __radix_tree_replace() argument
1186 int exceptional = !!radix_tree_exceptional_entry(item) - in __radix_tree_replace()
1188 int count = calculate_count(root, node, slot, item, old); in __radix_tree_replace()
1193 * node unless the slot is root->rnode. in __radix_tree_replace()
1195 WARN_ON_ONCE(!node && (slot != (void __rcu **)&root->rnode) && in __radix_tree_replace()
1197 replace_slot(slot, item, node, count, exceptional); in __radix_tree_replace()
1199 if (!node) in __radix_tree_replace()
1203 update_node(node); in __radix_tree_replace()
1205 delete_node(root, node, update_node); in __radix_tree_replace()
1209 * radix_tree_replace_slot - replace item in a slot
1218 * NOTE: This cannot be used to switch between non-entries (empty slots),
1220 * inside the radix tree node. When switching from one type of entry or
1232 * radix_tree_iter_replace - replace item in a slot
1244 __radix_tree_replace(root, iter->node, slot, item, NULL); in radix_tree_iter_replace()
1249 * radix_tree_join - replace multiple entries with one multiorder entry
1265 struct radix_tree_node *node; in radix_tree_join() local
1271 error = __radix_tree_create(root, index, order, &node, &slot); in radix_tree_join()
1273 error = insert_entries(node, slot, item, order, true); in radix_tree_join()
1281 * radix_tree_split - Split an entry into smaller entries
1294 * replacement operation. Lock-free lookups will see RADIX_TREE_RETRY which
1300 struct radix_tree_node *parent, *node, *child; in radix_tree_split() local
1307 return -ENOENT; in radix_tree_split()
1309 return -ENOENT; in radix_tree_split()
1319 rcu_dereference_raw(parent->slots[end]))) in radix_tree_split()
1325 rcu_assign_pointer(parent->slots[end], RADIX_TREE_RETRY); in radix_tree_split()
1327 rcu_assign_pointer(parent->slots[offset], RADIX_TREE_RETRY); in radix_tree_split()
1328 parent->exceptional -= (end - offset); in radix_tree_split()
1330 if (order == parent->shift) in radix_tree_split()
1332 if (order > parent->shift) { in radix_tree_split()
1334 offset += insert_entries(parent, &parent->slots[offset], in radix_tree_split()
1339 node = parent; in radix_tree_split()
1342 if (node->shift > order) { in radix_tree_split()
1343 child = radix_tree_node_alloc(gfp, node, root, in radix_tree_split()
1344 node->shift - RADIX_TREE_MAP_SHIFT, in radix_tree_split()
1346 if (!child) in radix_tree_split()
1348 if (node != parent) { in radix_tree_split()
1349 node->count++; in radix_tree_split()
1350 rcu_assign_pointer(node->slots[offset], in radix_tree_split()
1351 node_to_entry(child)); in radix_tree_split()
1354 tag_set(node, tag, offset); in radix_tree_split()
1357 node = child; in radix_tree_split()
1362 n = insert_entries(node, &node->slots[offset], in radix_tree_split()
1368 tag_set(node, tag, offset); in radix_tree_split()
1372 if (node == parent) in radix_tree_split()
1374 offset = node->offset; in radix_tree_split()
1375 child = node; in radix_tree_split()
1376 node = node->parent; in radix_tree_split()
1377 rcu_assign_pointer(node->slots[offset], in radix_tree_split()
1378 node_to_entry(child)); in radix_tree_split()
1381 if ((node == parent) && (offset == end)) in radix_tree_split()
1389 return -ENOMEM; in radix_tree_split()
1394 struct radix_tree_node *node, in node_tag_set() argument
1397 while (node) { in node_tag_set()
1398 if (tag_get(node, tag, offset)) in node_tag_set()
1400 tag_set(node, tag, offset); in node_tag_set()
1401 offset = node->offset; in node_tag_set()
1402 node = node->parent; in node_tag_set()
1410 * radix_tree_tag_set - set a tag on a radix tree node
1417 * the root all the way down to the leaf node.
1419 * Returns the address of the tagged item. Setting a tag on a not-present
1425 struct radix_tree_node *node, *parent; in radix_tree_tag_set() local
1428 radix_tree_load_root(root, &node, &maxindex); in radix_tree_tag_set()
1431 while (radix_tree_is_internal_node(node)) { in radix_tree_tag_set()
1434 parent = entry_to_node(node); in radix_tree_tag_set()
1435 offset = radix_tree_descend(parent, &node, index); in radix_tree_tag_set()
1436 BUG_ON(!node); in radix_tree_tag_set()
1446 return node; in radix_tree_tag_set()
1451 * radix_tree_iter_tag_set - set a tag on the current iterator entry
1459 node_tag_set(root, iter->node, tag, iter_offset(iter)); in radix_tree_iter_tag_set()
1463 struct radix_tree_node *node, in node_tag_clear() argument
1466 while (node) { in node_tag_clear()
1467 if (!tag_get(node, tag, offset)) in node_tag_clear()
1469 tag_clear(node, tag, offset); in node_tag_clear()
1470 if (any_tag_set(node, tag)) in node_tag_clear()
1473 offset = node->offset; in node_tag_clear()
1474 node = node->parent; in node_tag_clear()
1483 * radix_tree_tag_clear - clear a tag on a radix tree node
1490 * the leaf node to have no tags set then clear the tag in the
1491 * next-to-leaf node, etc.
1499 struct radix_tree_node *node, *parent; in radix_tree_tag_clear() local
1503 radix_tree_load_root(root, &node, &maxindex); in radix_tree_tag_clear()
1509 while (radix_tree_is_internal_node(node)) { in radix_tree_tag_clear()
1510 parent = entry_to_node(node); in radix_tree_tag_clear()
1511 offset = radix_tree_descend(parent, &node, index); in radix_tree_tag_clear()
1514 if (node) in radix_tree_tag_clear()
1517 return node; in radix_tree_tag_clear()
1522 * radix_tree_iter_tag_clear - clear a tag on the current iterator entry
1530 node_tag_clear(root, iter->node, tag, iter_offset(iter)); in radix_tree_iter_tag_clear()
1534 * radix_tree_tag_get - get a tag on a radix tree node
1545 * the RCU lock is held, unless tag modification and node deletion are excluded
1551 struct radix_tree_node *node, *parent; in radix_tree_tag_get() local
1557 radix_tree_load_root(root, &node, &maxindex); in radix_tree_tag_get()
1561 while (radix_tree_is_internal_node(node)) { in radix_tree_tag_get()
1564 parent = entry_to_node(node); in radix_tree_tag_get()
1565 offset = radix_tree_descend(parent, &node, index); in radix_tree_tag_get()
1569 if (node == RADIX_TREE_RETRY) in radix_tree_tag_get()
1581 iter->shift = shift; in __set_iter_shift()
1585 /* Construct iter->tags bit-mask from node->tags[tag] array */
1587 struct radix_tree_node *node, unsigned offset, in set_iter_tags() argument
1593 if (!node) { in set_iter_tags()
1594 iter->tags = 1; in set_iter_tags()
1598 iter->tags = node->tags[tag][tag_long] >> tag_bit; in set_iter_tags()
1601 if (tag_long < RADIX_TREE_TAG_LONGS - 1) { in set_iter_tags()
1604 iter->tags |= node->tags[tag][tag_long + 1] << in set_iter_tags()
1605 (BITS_PER_LONG - tag_bit); in set_iter_tags()
1607 iter->next_index = __radix_tree_iter_add(iter, BITS_PER_LONG); in set_iter_tags()
1615 while (iter->index < iter->next_index) { in skip_siblings()
1617 if (*nodep && !is_sibling_entry(iter->node, *nodep)) in skip_siblings()
1620 iter->index = __radix_tree_iter_add(iter, 1); in skip_siblings()
1621 iter->tags >>= 1; in skip_siblings()
1632 struct radix_tree_node *node; in __radix_tree_next_slot() local
1634 slot = skip_siblings(&node, slot, iter); in __radix_tree_next_slot()
1636 while (radix_tree_is_internal_node(node)) { in __radix_tree_next_slot()
1640 if (node == RADIX_TREE_RETRY) in __radix_tree_next_slot()
1642 node = entry_to_node(node); in __radix_tree_next_slot()
1643 iter->node = node; in __radix_tree_next_slot()
1644 iter->shift = node->shift; in __radix_tree_next_slot()
1647 offset = radix_tree_find_next_bit(node, tag, 0); in __radix_tree_next_slot()
1650 slot = &node->slots[offset]; in __radix_tree_next_slot()
1651 iter->index = __radix_tree_iter_add(iter, offset); in __radix_tree_next_slot()
1652 set_iter_tags(iter, node, offset, tag); in __radix_tree_next_slot()
1653 node = rcu_dereference_raw(*slot); in __radix_tree_next_slot()
1656 slot = &node->slots[0]; in __radix_tree_next_slot()
1658 node = rcu_dereference_raw(*slot); in __radix_tree_next_slot()
1659 if (node) in __radix_tree_next_slot()
1666 iter->index = __radix_tree_iter_add(iter, offset); in __radix_tree_next_slot()
1670 next_index = (iter->index | shift_maxindex(iter->shift)) + 1; in __radix_tree_next_slot()
1671 if (next_index < iter->next_index) in __radix_tree_next_slot()
1672 iter->next_index = next_index; in __radix_tree_next_slot()
1677 iter->next_index = 0; in __radix_tree_next_slot()
1692 struct radix_tree_node *node; in radix_tree_iter_resume() local
1695 iter->index = __radix_tree_iter_add(iter, 1); in radix_tree_iter_resume()
1696 skip_siblings(&node, slot, iter); in radix_tree_iter_resume()
1697 iter->next_index = iter->index; in radix_tree_iter_resume()
1698 iter->tags = 0; in radix_tree_iter_resume()
1704 * radix_tree_next_chunk - find next chunk of slots for iteration
1715 struct radix_tree_node *node, *child; in radix_tree_next_chunk() local
1722 * Catch next_index overflow after ~0UL. iter->index never overflows in radix_tree_next_chunk()
1724 * And we cannot overflow iter->next_index in a single step, in radix_tree_next_chunk()
1730 index = iter->next_index; in radix_tree_next_chunk()
1731 if (!index && iter->index) in radix_tree_next_chunk()
1735 radix_tree_load_root(root, &child, &maxindex); in radix_tree_next_chunk()
1738 if (!child) in radix_tree_next_chunk()
1741 if (!radix_tree_is_internal_node(child)) { in radix_tree_next_chunk()
1742 /* Single-slot tree */ in radix_tree_next_chunk()
1743 iter->index = index; in radix_tree_next_chunk()
1744 iter->next_index = maxindex + 1; in radix_tree_next_chunk()
1745 iter->tags = 1; in radix_tree_next_chunk()
1746 iter->node = NULL; in radix_tree_next_chunk()
1748 return (void __rcu **)&root->rnode; in radix_tree_next_chunk()
1752 node = entry_to_node(child); in radix_tree_next_chunk()
1753 offset = radix_tree_descend(node, &child, index); in radix_tree_next_chunk()
1756 !tag_get(node, tag, offset) : !child) { in radix_tree_next_chunk()
1762 offset = radix_tree_find_next_bit(node, tag, in radix_tree_next_chunk()
1767 node->slots[offset]); in radix_tree_next_chunk()
1768 if (is_sibling_entry(node, slot)) in radix_tree_next_chunk()
1773 index &= ~node_maxindex(node); in radix_tree_next_chunk()
1774 index += offset << node->shift; in radix_tree_next_chunk()
1780 child = rcu_dereference_raw(node->slots[offset]); in radix_tree_next_chunk()
1783 if (!child) in radix_tree_next_chunk()
1785 if (child == RADIX_TREE_RETRY) in radix_tree_next_chunk()
1787 } while (radix_tree_is_internal_node(child)); in radix_tree_next_chunk()
1790 iter->index = (index &~ node_maxindex(node)) | (offset << node->shift); in radix_tree_next_chunk()
1791 iter->next_index = (index | node_maxindex(node)) + 1; in radix_tree_next_chunk()
1792 iter->node = node; in radix_tree_next_chunk()
1793 __set_iter_shift(iter, node->shift); in radix_tree_next_chunk()
1796 set_iter_tags(iter, node, offset, tag); in radix_tree_next_chunk()
1798 return node->slots + offset; in radix_tree_next_chunk()
1803 * radix_tree_gang_lookup - perform multiple lookup on a radix tree
1809 * Performs an index-ascending scan of the tree for present items. Places
1850 * radix_tree_gang_lookup_slot - perform multiple slot lookup on radix tree
1857 * Performs an index-ascending scan of the tree for present items. Places
1892 * radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree
1900 * Performs an index-ascending scan of the tree for present items which
1933 * radix_tree_gang_lookup_tag_slot - perform multiple slot lookup on a
1941 * Performs an index-ascending scan of the tree for present items which
1968 * __radix_tree_delete_node - try to free node after clearing a slot
1970 * @node: node containing @index
1973 * After clearing the slot at @index in @node from radix tree
1975 * node and shrinking the tree.
1978 struct radix_tree_node *node, in __radix_tree_delete_node() argument
1981 delete_node(root, node, update_node); in __radix_tree_delete_node()
1985 struct radix_tree_node *node, void __rcu **slot) in __radix_tree_delete() argument
1988 int exceptional = radix_tree_exceptional_entry(old) ? -1 : 0; in __radix_tree_delete()
1989 unsigned offset = get_slot_offset(node, slot); in __radix_tree_delete()
1993 node_tag_set(root, node, IDR_FREE, offset); in __radix_tree_delete()
1996 node_tag_clear(root, node, tag, offset); in __radix_tree_delete()
1998 replace_slot(slot, NULL, node, -1, exceptional); in __radix_tree_delete()
1999 return node && delete_node(root, node, NULL); in __radix_tree_delete()
2003 * radix_tree_iter_delete - delete the entry at this iterator position
2009 * This may result in the current node being freed; if it is, the iterator
2017 if (__radix_tree_delete(root, iter->node, slot)) in radix_tree_iter_delete()
2018 iter->index = iter->next_index; in radix_tree_iter_delete()
2023 * radix_tree_delete_item - delete an item from a radix tree
2036 struct radix_tree_node *node = NULL; in radix_tree_delete_item() local
2040 entry = __radix_tree_lookup(root, index, &node, &slot); in radix_tree_delete_item()
2043 if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE, in radix_tree_delete_item()
2044 get_slot_offset(node, slot)))) in radix_tree_delete_item()
2050 __radix_tree_delete(root, node, slot); in radix_tree_delete_item()
2057 * radix_tree_delete - delete an entry from a radix tree
2072 struct radix_tree_node *node, in radix_tree_clear_tags() argument
2075 if (node) { in radix_tree_clear_tags()
2076 unsigned int tag, offset = get_slot_offset(node, slot); in radix_tree_clear_tags()
2078 node_tag_clear(root, node, tag, offset); in radix_tree_clear_tags()
2085 * radix_tree_tagged - test whether any items in the tree are tagged
2096 * idr_preload - preload for idr_alloc()
2113 * ida_get_new() can return -EAGAIN, prompting the caller in ida_pre_get()
2134 struct radix_tree_node *node = NULL, *child; in idr_get_free() local
2135 void __rcu **slot = (void __rcu **)&root->rnode; in idr_get_free()
2136 unsigned long maxindex, start = iter->next_index; in idr_get_free()
2140 shift = radix_tree_load_root(root, &child, &maxindex); in idr_get_free()
2144 return ERR_PTR(-ENOSPC); in idr_get_free()
2151 child = rcu_dereference_raw(root->rnode); in idr_get_free()
2155 shift -= RADIX_TREE_MAP_SHIFT; in idr_get_free()
2156 if (child == NULL) { in idr_get_free()
2157 /* Have to add a child node. */ in idr_get_free()
2158 child = radix_tree_node_alloc(gfp, node, root, shift, in idr_get_free()
2160 if (!child) in idr_get_free()
2161 return ERR_PTR(-ENOMEM); in idr_get_free()
2162 all_tag_set(child, IDR_FREE); in idr_get_free()
2163 rcu_assign_pointer(*slot, node_to_entry(child)); in idr_get_free()
2164 if (node) in idr_get_free()
2165 node->count++; in idr_get_free()
2166 } else if (!radix_tree_is_internal_node(child)) in idr_get_free()
2169 node = entry_to_node(child); in idr_get_free()
2170 offset = radix_tree_descend(node, &child, start); in idr_get_free()
2171 if (!tag_get(node, IDR_FREE, offset)) { in idr_get_free()
2172 offset = radix_tree_find_next_bit(node, IDR_FREE, in idr_get_free()
2174 start = next_index(start, node, offset); in idr_get_free()
2176 return ERR_PTR(-ENOSPC); in idr_get_free()
2178 offset = node->offset + 1; in idr_get_free()
2179 node = node->parent; in idr_get_free()
2180 if (!node) in idr_get_free()
2182 shift = node->shift; in idr_get_free()
2184 child = rcu_dereference_raw(node->slots[offset]); in idr_get_free()
2186 slot = &node->slots[offset]; in idr_get_free()
2189 iter->index = start; in idr_get_free()
2190 if (node) in idr_get_free()
2191 iter->next_index = 1 + min(max, (start | node_maxindex(node))); in idr_get_free()
2193 iter->next_index = 1; in idr_get_free()
2194 iter->node = node; in idr_get_free()
2196 set_iter_tags(iter, node, offset, IDR_FREE); in idr_get_free()
2202 * idr_destroy - release all internal memory from an IDR
2208 * A typical clean-up sequence for objects stored in an idr tree will use
2214 struct radix_tree_node *node = rcu_dereference_raw(idr->idr_rt.rnode); in idr_destroy() local
2215 if (radix_tree_is_internal_node(node)) in idr_destroy()
2216 radix_tree_free_nodes(node); in idr_destroy()
2217 idr->idr_rt.rnode = NULL; in idr_destroy()
2218 root_tag_set(&idr->idr_rt, IDR_FREE); in idr_destroy()
2225 struct radix_tree_node *node = arg; in radix_tree_node_ctor() local
2227 memset(node, 0, sizeof(*node)); in radix_tree_node_ctor()
2228 INIT_LIST_HEAD(&node->private_list); in radix_tree_node_ctor()
2234 int shift = RADIX_TREE_INDEX_BITS - width; in __maxindex()
2251 for (j = i; j > 0; j--) in radix_tree_init_maxnodes()
2252 height_to_maxnodes[i] += height_to_maxindex[j - 1] + 1; in radix_tree_init_maxnodes()
2259 struct radix_tree_node *node; in radix_tree_cpu_dead() local
2261 /* Free per-cpu pool of preloaded nodes */ in radix_tree_cpu_dead()
2263 while (rtp->nr) { in radix_tree_cpu_dead()
2264 node = rtp->nodes; in radix_tree_cpu_dead()
2265 rtp->nodes = node->parent; in radix_tree_cpu_dead()
2266 kmem_cache_free(radix_tree_node_cachep, node); in radix_tree_cpu_dead()
2267 rtp->nr--; in radix_tree_cpu_dead()