Lines Matching full:root
59 * of RADIX_TREE_MAX_PATH size to be created, with only the root node shared.
147 static inline gfp_t root_gfp_mask(const struct radix_tree_root *root) in root_gfp_mask() argument
149 return root->gfp_mask & (__GFP_BITS_MASK & ~GFP_ZONEMASK); in root_gfp_mask()
170 static inline void root_tag_set(struct radix_tree_root *root, unsigned tag) in root_tag_set() argument
172 root->gfp_mask |= (__force gfp_t)(1 << (tag + ROOT_TAG_SHIFT)); in root_tag_set()
175 static inline void root_tag_clear(struct radix_tree_root *root, unsigned tag) in root_tag_clear() argument
177 root->gfp_mask &= (__force gfp_t)~(1 << (tag + ROOT_TAG_SHIFT)); in root_tag_clear()
180 static inline void root_tag_clear_all(struct radix_tree_root *root) in root_tag_clear_all() argument
182 root->gfp_mask &= (1 << ROOT_TAG_SHIFT) - 1; in root_tag_clear_all()
185 static inline int root_tag_get(const struct radix_tree_root *root, unsigned tag) in root_tag_get() argument
187 return (__force int)root->gfp_mask & (1 << (tag + ROOT_TAG_SHIFT)); in root_tag_get()
190 static inline unsigned root_tags_get(const struct radix_tree_root *root) in root_tags_get() argument
192 return (__force unsigned)root->gfp_mask >> ROOT_TAG_SHIFT; in root_tags_get()
195 static inline bool is_idr(const struct radix_tree_root *root) in is_idr() argument
197 return !!(root->gfp_mask & ROOT_IS_IDR); in is_idr()
314 static void radix_tree_dump(struct radix_tree_root *root) in radix_tree_dump() argument
316 pr_debug("radix root: %p rnode %p tags %x\n", in radix_tree_dump()
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()
366 struct radix_tree_root *root = &ida->ida_rt; in ida_dump() local
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()
379 struct radix_tree_root *root, in radix_tree_node_alloc() argument
430 ret->root = root; in radix_tree_node_alloc()
583 * This requires RADIX_TREE_MAX_PATH nodes to build branch from root to in radix_tree_maybe_preload_order()
591 /* Root node is shared. */ in radix_tree_maybe_preload_order()
600 static unsigned radix_tree_load_root(const struct radix_tree_root *root, in radix_tree_load_root() argument
603 struct radix_tree_node *node = rcu_dereference_raw(root->rnode); in radix_tree_load_root()
620 static int radix_tree_extend(struct radix_tree_root *root, gfp_t gfp, in radix_tree_extend() argument
632 entry = rcu_dereference_raw(root->rnode); in radix_tree_extend()
633 if (!entry && (!is_idr(root) || root_tag_get(root, IDR_FREE))) in radix_tree_extend()
638 root, shift, 0, 1, 0); in radix_tree_extend()
642 if (is_idr(root)) { in radix_tree_extend()
644 if (!root_tag_get(root, IDR_FREE)) { in radix_tree_extend()
646 root_tag_set(root, IDR_FREE); in radix_tree_extend()
651 if (root_tag_get(root, tag)) in radix_tree_extend()
660 /* Moving an exceptional root->rnode to a node */ in radix_tree_extend()
669 rcu_assign_pointer(root->rnode, entry); in radix_tree_extend()
678 * @root radix tree root
680 static inline bool radix_tree_shrink(struct radix_tree_root *root, in radix_tree_shrink() argument
686 struct radix_tree_node *node = rcu_dereference_raw(root->rnode); 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()
718 root_tag_clear(root, IDR_FREE); in radix_tree_shrink()
734 * problem (replacing direct root node with an indirect pointer in radix_tree_shrink()
753 static bool delete_node(struct radix_tree_root *root, in delete_node() argument
764 rcu_dereference_raw(root->rnode)) in delete_node()
765 deleted |= radix_tree_shrink(root, in delete_node()
779 if (!is_idr(root)) in delete_node()
780 root_tag_clear_all(root); in delete_node()
781 root->rnode = NULL; in delete_node()
796 * @root: radix tree root
803 * at position @index in the radix tree @root.
806 * allocated and @root->rnode is used as a direct slot instead of
811 int __radix_tree_create(struct radix_tree_root *root, unsigned long index, in __radix_tree_create() argument
816 void __rcu **slot = (void __rcu **)&root->rnode; in __radix_tree_create()
820 gfp_t gfp = root_gfp_mask(root); in __radix_tree_create()
822 shift = radix_tree_load_root(root, &child, &maxindex); in __radix_tree_create()
828 int error = radix_tree_extend(root, gfp, max, shift); in __radix_tree_create()
832 child = rcu_dereference_raw(root->rnode); in __radix_tree_create()
839 child = radix_tree_node_alloc(gfp, node, root, shift, in __radix_tree_create()
978 * @root: radix tree root
985 int __radix_tree_insert(struct radix_tree_root *root, unsigned long index, in __radix_tree_insert() argument
994 error = __radix_tree_create(root, index, order, &node, &slot); in __radix_tree_insert()
1008 BUG_ON(root_tags_get(root)); in __radix_tree_insert()
1017 * @root: radix tree root
1023 * tree @root.
1026 * allocated and @root->rnode is used as a direct slot instead of
1029 void *__radix_tree_lookup(const struct radix_tree_root *root, in __radix_tree_lookup() argument
1039 slot = (void __rcu **)&root->rnode; in __radix_tree_lookup()
1040 radix_tree_load_root(root, &node, &maxindex); in __radix_tree_lookup()
1063 * @root: radix tree root
1067 * radix tree @root. This is useful for update-if-exists operations.
1074 void __rcu **radix_tree_lookup_slot(const struct radix_tree_root *root, in radix_tree_lookup_slot() argument
1079 if (!__radix_tree_lookup(root, index, NULL, &slot)) in radix_tree_lookup_slot()
1087 * @root: radix tree root
1090 * Lookup the item at the position @index in the radix tree @root.
1097 void *radix_tree_lookup(const struct radix_tree_root *root, unsigned long index) in radix_tree_lookup() argument
1099 return __radix_tree_lookup(root, index, NULL, NULL); in radix_tree_lookup()
1138 static bool node_tag_get(const struct radix_tree_root *root, in node_tag_get() argument
1144 return root_tag_get(root, tag); in node_tag_get()
1154 static int calculate_count(struct radix_tree_root *root, in calculate_count() argument
1158 if (is_idr(root)) { in calculate_count()
1160 bool free = node_tag_get(root, node, IDR_FREE, offset); in calculate_count()
1171 * @root: radix tree root
1180 void __radix_tree_replace(struct radix_tree_root *root, in __radix_tree_replace() argument
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()
1205 delete_node(root, node, update_node); in __radix_tree_replace()
1210 * @root: radix tree root
1224 void radix_tree_replace_slot(struct radix_tree_root *root, in radix_tree_replace_slot() argument
1227 __radix_tree_replace(root, NULL, slot, item, NULL); in radix_tree_replace_slot()
1233 * @root: radix tree root
1240 void radix_tree_iter_replace(struct radix_tree_root *root, in radix_tree_iter_replace() argument
1244 __radix_tree_replace(root, iter->node, slot, item, NULL); in radix_tree_iter_replace()
1250 * @root: radix tree root
1262 int radix_tree_join(struct radix_tree_root *root, unsigned long index, in radix_tree_join() argument
1271 error = __radix_tree_create(root, index, order, &node, &slot); in radix_tree_join()
1282 * @root: radix tree root
1295 * should prompt RCU walkers to restart the lookup from the root.
1297 int radix_tree_split(struct radix_tree_root *root, unsigned long index, in radix_tree_split() argument
1304 gfp_t gfp = root_gfp_mask(root); in radix_tree_split()
1306 if (!__radix_tree_lookup(root, index, &parent, &slot)) in radix_tree_split()
1343 child = radix_tree_node_alloc(gfp, node, root, in radix_tree_split()
1393 static void node_tag_set(struct radix_tree_root *root, in node_tag_set() argument
1405 if (!root_tag_get(root, tag)) in node_tag_set()
1406 root_tag_set(root, tag); in node_tag_set()
1411 * @root: radix tree root
1417 * the root all the way down to the leaf node.
1422 void *radix_tree_tag_set(struct radix_tree_root *root, in radix_tree_tag_set() argument
1428 radix_tree_load_root(root, &node, &maxindex); in radix_tree_tag_set()
1442 /* set the root's tag bit */ in radix_tree_tag_set()
1443 if (!root_tag_get(root, tag)) in radix_tree_tag_set()
1444 root_tag_set(root, tag); in radix_tree_tag_set()
1452 * @root: radix tree root
1456 void radix_tree_iter_tag_set(struct radix_tree_root *root, in radix_tree_iter_tag_set() argument
1459 node_tag_set(root, iter->node, tag, iter_offset(iter)); in radix_tree_iter_tag_set()
1462 static void node_tag_clear(struct radix_tree_root *root, in node_tag_clear() argument
1477 /* clear the root's tag bit */ in node_tag_clear()
1478 if (root_tag_get(root, tag)) in node_tag_clear()
1479 root_tag_clear(root, tag); in node_tag_clear()
1484 * @root: radix tree root
1496 void *radix_tree_tag_clear(struct radix_tree_root *root, in radix_tree_tag_clear() argument
1503 radix_tree_load_root(root, &node, &maxindex); in radix_tree_tag_clear()
1515 node_tag_clear(root, parent, tag, offset); in radix_tree_tag_clear()
1523 * @root: radix tree root
1527 void radix_tree_iter_tag_clear(struct radix_tree_root *root, in radix_tree_iter_tag_clear() argument
1530 node_tag_clear(root, iter->node, tag, iter_offset(iter)); in radix_tree_iter_tag_clear()
1535 * @root: radix tree root
1548 int radix_tree_tag_get(const struct radix_tree_root *root, in radix_tree_tag_get() argument
1554 if (!root_tag_get(root, tag)) in radix_tree_tag_get()
1557 radix_tree_load_root(root, &node, &maxindex); in radix_tree_tag_get()
1706 * @root: radix tree root
1711 void __rcu **radix_tree_next_chunk(const struct radix_tree_root *root, in radix_tree_next_chunk() argument
1718 if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag)) in radix_tree_next_chunk()
1735 radix_tree_load_root(root, &child, &maxindex); in radix_tree_next_chunk()
1748 return (void __rcu **)&root->rnode; in radix_tree_next_chunk()
1804 * @root: radix tree root
1823 radix_tree_gang_lookup(const struct radix_tree_root *root, void **results, in radix_tree_gang_lookup() argument
1833 radix_tree_for_each_slot(slot, root, &iter, first_index) { in radix_tree_gang_lookup()
1851 * @root: radix tree root
1868 radix_tree_gang_lookup_slot(const struct radix_tree_root *root, in radix_tree_gang_lookup_slot() argument
1879 radix_tree_for_each_slot(slot, root, &iter, first_index) { in radix_tree_gang_lookup_slot()
1894 * @root: radix tree root
1905 radix_tree_gang_lookup_tag(const struct radix_tree_root *root, void **results, in radix_tree_gang_lookup_tag() argument
1916 radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) { in radix_tree_gang_lookup_tag()
1935 * @root: radix tree root
1946 radix_tree_gang_lookup_tag_slot(const struct radix_tree_root *root, in radix_tree_gang_lookup_tag_slot() argument
1957 radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) { in radix_tree_gang_lookup_tag_slot()
1969 * @root: radix tree root
1974 * rooted at @root, call this function to attempt freeing the
1977 void __radix_tree_delete_node(struct radix_tree_root *root, in __radix_tree_delete_node() argument
1981 delete_node(root, node, update_node); in __radix_tree_delete_node()
1984 static bool __radix_tree_delete(struct radix_tree_root *root, in __radix_tree_delete() argument
1992 if (is_idr(root)) 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()
1999 return node && delete_node(root, node, NULL); in __radix_tree_delete()
2004 * @root: radix tree root
2014 void radix_tree_iter_delete(struct radix_tree_root *root, in radix_tree_iter_delete() argument
2017 if (__radix_tree_delete(root, iter->node, slot)) in radix_tree_iter_delete()
2024 * @root: radix tree root
2028 * Remove @item at @index from the radix tree rooted at @root.
2033 void *radix_tree_delete_item(struct radix_tree_root *root, in radix_tree_delete_item() argument
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()
2050 __radix_tree_delete(root, node, slot); in radix_tree_delete_item()
2058 * @root: radix tree root
2061 * Remove the entry at @index from the radix tree rooted at @root.
2065 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) in radix_tree_delete() argument
2067 return radix_tree_delete_item(root, index, NULL); in radix_tree_delete()
2071 void radix_tree_clear_tags(struct radix_tree_root *root, in radix_tree_clear_tags() argument
2078 node_tag_clear(root, node, tag, offset); in radix_tree_clear_tags()
2080 root_tag_clear_all(root); in radix_tree_clear_tags()
2086 * @root: radix tree root
2089 int radix_tree_tagged(const struct radix_tree_root *root, unsigned int tag) in radix_tree_tagged() argument
2091 return root_tag_get(root, tag); in radix_tree_tagged()
2130 void __rcu **idr_get_free(struct radix_tree_root *root, in idr_get_free() argument
2135 void __rcu **slot = (void __rcu **)&root->rnode; in idr_get_free()
2140 shift = radix_tree_load_root(root, &child, &maxindex); in idr_get_free()
2141 if (!radix_tree_tagged(root, IDR_FREE)) in idr_get_free()
2147 int error = radix_tree_extend(root, gfp, start, shift); in idr_get_free()
2151 child = rcu_dereference_raw(root->rnode); in idr_get_free()
2158 child = radix_tree_node_alloc(gfp, node, root, shift, in idr_get_free()